（计算机软件与理论专业论文）移动自组网中基于位置和节能的路由算法研究.pdf

中国科学技术大学硕士学位论文摘要 摘要 移动自组网是由移动主机组成的一种多跳步无线网络，刚络中不存在任何固 定的通信基础设施，移动主机之间协同工作，在共享无线介质中以多跳步方式传 输数据，每个主机既是终端又是路由器。移动自组网不需要预先建立通信基础设 旋，而且部署起来非常方便。 移动自组网中需要解决的最关键问题是网络路由，而可扩展性是衡量路由算 法的重要指标之一。在移动自组网中，节点的移动性、节点资源的受限性以及网 络中可能包含大量的节点，都给路由带来极大的困难；路由算法的好坏对整个网 络通信质量的影响至关重要。 本文综合考虑了移动自组网中分组投递成功率及网络连通寿命两项性能指 标，提出了一种基于位置和节能的路由算法，该算法根据下一跳节点所处区域的 节点稠密度、下一跳节点的剩余能源、转发功耗和转发效果决定分组转发路由。 基于位置和节能的路由算法尽量避免将分组转发到节点稀疏的区域以提高 分组投递成功率，尽量避免将分组转发给剩余能源不多的中间节点、尽量减少本 次分组转发的功耗以优化整个网络的连通寿命；并能根据具体情况区分出各影响 因素的主次，很好的反应了各个因素在路径选择中所起的作用，从而实现了对分 组转发策略的优化。 本文随后讨论了实现该路由算法所需要的局部信息收集机制，分组转发失败 预防机制和恢复机制。局部信息收集机制让节点在小范围内定期交换位置信息及 剩余能源信息，然后基于这些局部信息做出分组转发的决策。当然，这种信息获 取机制必须是简单、有效和不会消耗太多能源的。通过尽量将分组转发到节点稠 密的区域以实现分组转发失败预防机制，通过发送端记录分组转发失败的方向和 次数并及时调准路由方向以实现分组转发失败恢复机制。 在本文的最后给出了该算法的仿真实验及测试结果。我们对仿真平台1 1 s 进 行了扩展：在原有的基础上( 版本为n s - a l l i n o n e 一2 2 7 一g c c 3 2 ) 在节点处增加 了邻居节点表和转发失败表；修改了原有的路由模块，分别实现了需要进行性能 比较的三种路由算法；扩展了a g e n t 对象的发包机制，实现了分组转发失败的恢 复机制。接着给出了仿真实验的测试方案和实验结果，并对实验结果进行分析。 2 中国科学技术大学硕士学位论文摘要 实验证明，在能源受限的移动自组网中，本文提出的路由算法在分组投递成功率 和网络连通寿命方面均取得很好的效果。 本文得到8 6 3 课题( n o 2 0 0 2 a a l 2 1 0 6 6 ) 和安徽省自然科学基金 ( n o 0 3 0 4 2 2 1 1 ) 的资助。 关键字：移动自组网；基于位置的路由算法；基于节能的路由算法：转发策略 投递成功率；连通寿命；网络仿真。 中国科学技术大学硕士学位论文a b s t r a c t a b s t r a c t m o b i l ea dh o cn e t w o r k si sa m u l t i - h o pw i r e l e s sn e t w o r kc o n s i s t i n ge n t i r e l yo f m o b i l eh o s t st h a tc o m m u n i c a t eo n t h e m o v ew i t h o u tb a s es t a t i o n s n o d e si nt h i s n e t w o r ka g r e et or e l a ye a c ho t h e r s p a c k e t st o w a r dt h e i ru l t i m a t ed e s t i n a t i o n s ， a u t o m a t i c a l l yf o r m i n gt h e i ro w nc o o p e r a t i v ei n f r a s t r u c t u r e s u c hn e t w o r kn e e d sn o p r i o rf i x e di n f r a s t r u c t u r ea n di se a s yt od e p l o y t h ek e yi nm o b i l ea dh o cn e t w o r k si s r o u t i n g ，w h i l et h ei m p o r t a n ti n d e xi n e v a l u a t i n gt h ew a yo fc a l c u l a t i n gr o u t i n gi sw h e t h e ri tc a l lb ee x p a n d e d i nm o b i l ea d h o cn e t w o r k s ，t h em o v a b i l i t yo fn o d e ，t h el i m i t a t i o no fn o d er e s o u r c e s ，a n dt h e p o s s i b l eb i ga m o u n to fn o d e sa l lt h e s ec a u s eg r e a td i f f i c u l t yt or o u t i n g h o w e v e r , t h e w a yo fc a l c u l a t i n gr o u t i n gh a sas i g n i f i c a n ti m p a c to nt h eq u a l i t yo fn e t w o r k c o m m u n i c a t i o n t a k i n gi n t oa c c o u n tb o t ht h et r a n s m i s s i o ns u c c e s sr a t ea n dc o n n e c t i o nl o n g e v i t y o fm o b i l ea dh o cn e t w o r k sa sp e r f o r m a n c ei n d e x e s ，t h i sp a p e rp r o p o s e sp b e c r , a r o u t i n gb a s i n go np o s i t i o na sw e l la se n e r g yc o n s e r v i n g p b e c rf o r w a r d st h ep a c k e t 4 c c o r d i n gt ot h en o d ed e n s i t yo fn e x th o pa r e a , t h ea v a i l a b l ee n e r g yo ft h en e x th o p n o d e ，t h ef o r w a r de n e r g yc o n s u m p t i o na n dt h ef o r w a r d i n ge f f e c t t h er o u t i n gb a s e do np o s i t i o n i sw e l la se n e r g yc o n s e r v i n ga v o i da sm u c ha s p o s s i b l et ot r a n s f e rp a c k e t st ot h ea r e a sw h e r en o d e sa r ei s o l a t e dw i t ht h ea i mo f r a i s i n gt h er a t eo ft r a n s f e r r i n gt h e ms u c c e s s f u la n dp a c k e t ss h o u l db ea v o i d e dt o t r a n s f e r r e dt om i d d l en o d e sw h e r el i t t l ee n e r g yi sl e f t a n dt h ee n e r g yc o n s u m e di n t h ep r o c e s ss h o u l db em i n i m i z e dt oo p t i m i z et h ew h o l en e t w o r kt h ei m p o r t a n c eo f t h ef a c t o r ss h o u l db ed e c i d e di nl i g h tw i t ht h ea c t u a ls i t u a t i o n ，t h u st h er o l e so ft h e s e f a c t o r si nt h ep r o c e s so fc h o o s i n gr o u t i n gc a nb ed e m o n s t r a t e d 。a sar e s u l t ，t h e s t r a t e g yo f o p t i m i z i n gt h ep a c k e t sc a l lb ec a r r i e do u t t h e nt h ep a p e rd i s c u s s e st h em e c h a n i s mo fc o l l e c t i n gp a r t i a ls t a t ei n f o r m a t i o n n e e d e di nc a r r y i n go u tt h er o u t i n ga n dt h em e c h a n i s mo f p r e v e n t i n gf a i l u r ei np a c k e t s t r a n s f e ra n dr e s t o r i n gt h e m i nt h i sm e c h a n i s mt h ei n f o r m a t i o no fn o d e sa n dl e f t 4 中国科学技术大学硕士学位论文 a b s t r a c t e n e r g yc a nb ee x c h a n g e dr e g u l a r l ya n dt h e nt h es t r a t e g yo f t r a n s f e r r i n gp a c k e t sc a nb e m a d ei t i sc e r t a i nt h a tt h i sm e c h a n i s ms h o u l db es i m p l e ，e f f e c t i v ea n de n e r g y - f r i e n d l y t h ef a i l u r ec a nb ep r e v e n t e db yt r a n s f e r r i n gt h ep a c k e t st on o d e s d e n s e da r e a s a n d t h ef a i l u r ecanb er e s t o r e db yr e c o r d i n gt h ea r e a sa n dt i m e so ff a i l u r ea n dr e a d j u s t i n g t h ed i r e c t i o n so f t r a n s f e r r i n gt h ep a c k e t s i nt h ee n dt h ep a p e rp r e s e n t st h ee x p e r i m e n ta n dr e s u l t so f t h er o u t i n gt h en so f p l a t f o r mh a sb e e ne x p a n d e do nt h eb a s eo fo r i g i n a lv e r s i o n ( u s - a l l i n o n e - 2 2 7 - g c c 3 2 ) t h el i s to fn e i g h b o r i n gn o d e s ( n e i g h b o r t a b l e ) a n dt h er e c o r do ff a i l u r e ( l o s t t a b l e ) a r ea d d e di nn o d e sa r e a s t h eo r i g i n a lr o u t i n gi sr e v i s e da n dt h r e ek i n d so fr o u t i n g w h i c ha r ec o m p a r e dd u et ot h ep o s s i b i l i t yo fe x p a n d i n gc a nb ec a r r i e do u t a l s ot h e p a c k e tf o r w a r d i n gm e c h a n i s mc o n c e r n e da g e n ti sr e v i s e d t h e nt h e r e s t o r i n g m e c h a n i s mi sr e a l i z e d f u r t h e r m o r et h ep l a na n dr e s u l t so fe x p e r i m e n ta r ep r e s e n ta n d t h er e s u l t sa r ea n a l y z e da n dt h es i m u l a t i o ns h o w st h a tc o m p a r e dw i t hp o s i t i o n - b a s e d r o u t i n go fe n e r g y c o n s e r v i n gr o u t i n g ，p b e c ra c h i e v e st h eb e a e rp e r f o r m a n c e i n e n e r g y l i m i t e dm o b i l ea dh o cn e t w o r k s t h i sr e s e a r c h p r o j e c t i s s u p p o r t e db y n a t i o n a l8 6 3s c i e n c ef o u n d a t i o n ( n o 2 0 0 2 a a l 2 1 0 6 6 ) a n da n h u i p r o v i n c e n a t u r a ls c i e n c ef o u n d a t i o n ( n o 0 3 0 4 2 2 1 1 ) k e yw o r d s ：m o b i l ea dh o cn e t w o r k s , p o s i t i o n b a s e dr o u t i n g ，e n e r g y c o n s e r v i n g r o u t i n g ，f o r w a r d i n gs t r a t e g y , f o r w a r d i n gs u c c e s sr a t e ，c o n n e c t i o n l o n g e v i t y ，s i m u l a t i o ne x p e r i m e n t 5 中国科学技术大学硕士学位论文 第1 章绪论 1 1 研究背景和意义 第1 章绪论 近年来，随着无线通信技术的发展和体积小巧、性能优越的计算与通信设备 ( 如带有无线收发器的膝上机及p d a ) 的广泛普及，一种新型的网络一移动自组 网逐渐引起了人们的关注。移动自组网是由移动主机组成的一种多跳步无线网 络，网络中不存在任何固定的通信基础设施，移动主机之间协同工作，在共享无 线介质中以多跳步方式传输数据，每个主机既是终端又是路由器。移动自组网因 其部署起来方便快捷且小需要预先建立通信基础设施，特别适用于战场及救灾现 场的通信，同时在会议中心、电子教室等场合也有重要作用。 移动自组网中需要解决的最关键问题是网络路由，而可扩展性是衡量路由算 法的重要指标之一。节点的移动性、节点资源的受跟性阱及网络中可能包含大量 的节点，都给路由带来极大的困难；路由算法的好坏对通信质量的影响至关重要。 在众多已提出的移动自组网络路由算法中，基于位置的路由算法因其扩展性好而 日益受到人们的重视。但研究也表明，目前已提出的基于位置的路由算法虽然在 密集网络中能够获得很高的投递成功率，但在稀疏网络中投递常常失败 1 。同 时，由于大多数移动自组网中节点能源非常有限且不易更换，人们认为在分组路 由的时候还应考虑能源消耗的问题，提出了多种基于节能的路由算法，以优化整 个网络的使用寿命及连通性。 本论文的研究目标是将基于位置和基于节能的路由算法有机结合，并研究在 稀疏网络中也能适用的路由算法。 移动自组网的研究在我国刚刚起步，现有的研究工作大多集中在基于拓扑的 路由算法方面，基于位置的路由算法很少见研究报道，而基于位置的路由算法由 于其算法的本地化和对拓扑变化的适应性，被认为是最有希望的通用移动自组网 路由算法 2 。同时，在分组路由时采取一定的节能策略能大大的优化整个网络 的使用寿命及连通性。因此，将基于位置和基于节能的路由算法有机结合，可取 得更好的通信性能。本论文对于移动自组网的研究与应川有着重要和积极的作 用。 中周科学技术大学硕士学位论文第1 章绪论 i 2 移动自组网中路由算法简介 目前已提出的各种移动自组网路由算法可以分为两大类：基于拓扑的路由算 法和熬于位置的路由算法 1 。 基于拓扑的路由算法使用网络中的链路信息进行分组转发，这一类算法进 步地又可以分为主动方法、反应方法和混合方法三种。实验已经证实，仅使用拓 扑信息的路由算法在网络规模很大时，都存在可扩展性差的问题 2 。 随着全球定位系统( g p s ) 的发展，以及小巧、廉价和低功耗的g p s 接收机 的出现，在移动白组网中利用节点的位嚣信息进行路由成为了可能，从而产生出 了一类基于位置的路由算法。在基于位置的路由算法中，节点仅根据自己的位置、 距其一跳距离的邻居的位置以及目的节点的位置，就可以进行分组转发。由于不 需要维护显式的路由，这种算法即使在网络拓扑变化很快的情况下仍然能够保持 很好的扩展性，这是它在高度动态的移动自组网中的主要优势。另外，相邻节点 的距离信息有助于节点优化发射功率，实现各种能够优化功率消耗和延长系统寿 命的路由策略。 此外，由于移动节点多采用电池供电，能源非常有限，因而节能成为移动自 组网中各类算法在设计时需要重点考虑的问题。目前人们己提出了多种基于节能 的转发策略，它们的优化目标不外乎是以下两种：( 1 ) 总功率最小化，即整条通信 路径的耗能最小；( 2 ) 网络连通寿命最大化，即均衡使用网络中各节点的能源。目 前人们倾向于认为节能并不只是单纯地追求总功耗的最小化，而是应当追求网络 连通寿命的最大化 3 】。 1 - 3 本文主要工作和创新点 本文研究的重点是提出一种基于位置和节能的路由算法，该算法将基于位置 和基于节能的路由算法有机结合，达到既提高投递成功率又均衡能源消耗的目 的。涉及的内容主要包括对移动自组网中影响路由选择的各种因素进行分析、以 此为基础提出基于位置和节能的路由算法、实现该路由算法并对其性能进行测 试。我们是通过网络仿真来实现该路由算法，并在网络仿真平台n s 2 上进行性 能测试，所以本文的工作还包括对网络仿真工具n s 2 的使用说明和相关功能模 中国科学技术大学硕士学位论文 第1 章绪论 块的修改扩展。 在研究过程中，笔者对大量相关研究文献进行了理解分析，根据移动自组网 的特点提出了影响分组转发的四个因素。随后详细的分析了这四个影响因素在分 组路由时所起的作用，给出了一个综合评估方法，并以此为基础提出了一种基于 位置和节能的分组转发策略。接着给出了实现该路由算法需要的局部信息收集机 制、转发失败预防机制和恢复机制。最后在网络仿真上实现该算法并进行性能测 试。 本文的章节安排、具体工作和创新点如下： 第一章阐述了移动自组网中路由算法研究的背景和意义，简单介绍了一下 当前出现的各种路由算法。说明了在移动自组网中，相对于基于拓扑的路由算法， 基于位置的路由算法能取得更好的性能，同时也提出了在路由选择的时候，还需 考虑熬个系统能源的消耗。 第二章详细的分析了当前移动自组网中路由算法的研究现状，重点分析了 基于位置的各种路由算法，对其中具有较大影响力的几种分组转发策略进行了介 绍和分析。对各路由算法进行概括和总结，以此做为本文研究工作的基础。 第三章根据移动自组网的特点提出了影响路由算法性能的四个因素：下一 跳节点的节点稠密度、下一跳节点的能源剩余情况、该路径分组转发功耗和该路 径分组转发的效果，分别对四个影响因素进行分析并以此为根据提出了一种基于 位置和节能的路由算法。本章的最后给出了该算法的理论基础支持。 第四章为了支持本文提出的基于位置和节能的路由算法，本章提出了一套 简单有效的局部信息收集机制，用来提高稀疏网络中的分组投递成功率，并且控 制和均衡网络中各个节点的能量消耗。在本章的后半部分给出了此路由算法的分 组转发失败预防机制和分组转发失败恢复机制。 第：h 章本章开始介绍了网络仿真工具n s 2 ，简单说明了一下它的工作机制 及各模块的功能。在此基础上，我们对各功能模块进行了扩展，对路由模块进行 更改以实现我们所需要的路由算法，对节点对象功能进行扩展以实现局部信息收 集机制，对a g e n t 对象功能进行以扩展实现转发失败恢复机制。我们分别实现了 三种不同的路由算法，并用几组不同的测试例子对它们进行性能测试，最后对实 验结果进行了分析。 l o 中国科学技术大学硕士学位论文第2 章移动自组网中路由算法的研究现状 第2 章移动自组网中路由算法的研究现状 2 1 引言 针对移动自组网的特点，目前人们已提i 山了的多种路由算法。通过对移动自 组网的特点分析和对现有各种路由算法的研究和比较，可找出性能较好的几种路 由算法作为我们研究：亡作的基础。 本章第一节分析了移动自组网的特点。第二节简单介绍了一下基于拓扑的路 由算法。第三节详细介绍了各种基于位置的路由算法，分析了当前几种比较通用 的转发策略及其性能。第四节介绍了一下基于节能的路由算法。最后总结得出分 组路由时我们希望采用的策略。 2 2 移动自组网的特点 在移动自组网中，每个节点都是自由移动的，网络中不存在任何固定的通信 基础设施；由于节点移动的不可确定性和随机性，导致了整个网络的拓扑结构的 是不可预知的，因此，移动自组网最大的一个特点就是节点的移动性并由此导致 整个网络拓扑的易变性。 相对于固定网络的通信，移动自组网中节点之间无线通信的带宽显然要小很 多；节点的移动性、通信时间的延迟和无线通信最远传送能力，也会导致通信质 量的降低，因此宽带受限且易变的通信能力是移动自组网的第二个特点。 由于移动节点多采用电池供电，能源非常有限，而整个网是由各个移动节点 协同工作的，一旦某些节点能源耗尽，很可能导致整个网络的瘫痪，均衡的使用 整个网络的能源至关重要，因此能源的受限性是移动自组网的第三个特点。 由于整个网络的节点都是自由移动的，因此可能会导致某些区域在一定的时 间内节点减少，出现稀疏网络。因此，局部容易出现稀疏网络是移动自组网的第 四个特点。 此外，移动自组网中不存在任何固定的通信基础设施，移动主机之间协同工 作，在共享无线介质中以多跳步方式传输数据，每个主机既是终端又是路由器， 中国科学技术大学硕士学位论文第2 章移动自组网中骼由算法的研究现状 节点之问无线通信容易被窃听修改，因此还存在着安全性较差的问题。 从移动自组网自身的这些特点可以看出，路由问题是移动自组网中最具挑战 性的问题。节点的移动性、节点资源的受限性以及网络中可能包含大量的节点， 都给路由带来极大的困难。针对移动网的特点，目前人们已经提出了多种路由算 法，主要分为两大类：基于拓扑的路由算法和基于位置的路由算法。此外，考虑 到节点资源的受限性，人们提出在分组路由的时候还需考虑节能的问题。 2 3 基于拓扑的路由算法 基于拓扑的路由算法使用网络中的链路信息进行分组转发，这一类算法进一 步地又可以分为主动方法、反应方法和混合方法三种。主动方法采用经典的路由 策略，如距离矢量路由算法或链路状态路由算法，它维护到网络中所有可达节点 的路由信息，包括那些当前没有被使用的路由，因此可扩展性差，其典型代表是 d s d v 4 1 。反应方法只发现和维护当前正在使用的路由，因此可扩展性好，但转 发第一个分组的延迟大，其典型代表是d s r 【5 】和a o d v 6 】。混合方法结合了 前两种方法的优点，将网络划分成区域，区域内采用主动方法，区域间采用反应 方法。这种方法的可扩展性和效率较前两者为好，但是仍然至少要维护当前正在 使用的路由，从而降低了对网络拓扑变化的适应能力，其典型代表是z r p 7 。 实验已经证实，仅使用拓扑信息的路由算法在网络规模很大时，都存在可扩展性 差的问题【2 j 。 2 4 基于位置的路由算法 在基于位置的路由算法中，节点仅根据自己的位置、距其一跳距离的邻居的 位置以及目的节点的位置，就可以进行分组转发。由于不需要维护显式的路由， 这种算法即使在网络拓扑变化很快的情况下仍然能够保持很好的扩展性，这是它 在高度动态的移动自组网中的主要优势。另外，相邻节点的距离信息有助于节点 优化发射功率实现各种能够优化功率消耗和延长系统寿命的路由策略。 目前提出的基于位置的转发策略主要有三种，第一种是贪婪转发，将分组转 发到离目的节点最“近”的邻居，在这里不同的算法对于“近”的解释不同，这 一类算法的典型代表是g p s r 8 ；第二种是限制方向扩散，只允许某个区域内的 中围科学技术大学硕士学位论文第2 章移动自组嗣中路由算法的研究现状 节点继续转发分组，其典型代表是d r e a m 9 和l a r 1 0 ；第三种是分层转发，对 于远处的节点采用贪婪转发，而在本地使用非基于位置的转发，目的是使分组转 发能够容忍不精确的位置信息，其典型代表是t e r m in o d e s 1 1 和g r i d r o u t i n g 1 2 】。目前来看，贪婪转发策略由于它的有效性以及对网络拓扑变化的适 应性而成为首选的转发模式 1 ，但是研究表明，贪婪模武的路由虽然在密集部 署的网络中有很高的数据投递成功率，它在稀疏网络中却常常投递失败 2 ，另 外它对不精确的位置信息的适应能力也有待提高。下面对这三种路由算法进行详 细的分析与比较。 2 4 1 贪婪转发 分组发送者把接收者的近似地址放在分组中，当一个中闻节点收到分组的时 候，它就把该分组转发到大致位于接收者所在方向上的邻居节点，理论上，这个 过程会一直重复到到达接收节点为止。一般的，有很多种策略可以供节点决定把 分组转发到哪个邻居。 图2 1 贪婪转发的路径示意图 以上图为例。s 和d 分别表示分组的源节点和目的结点，半径为1 的圆表示 s 的最大传输范围一种直观的策略就是把分组转发到离目的节点最近的邻居节 点，在这个例子中就是c 这种策略叫做m o s t f o r w a r d w i t h i nr ( m f r ) ，i v l f r 尽 量最小化到达d 的跳数。在分组不能根据发送者和接收者之间的距离而调整传 输信号强度的情况下，m f r 是一个很好的策略，但是在发送者可以调节信号强 中国科学技术大学硕士学位论文第2 章移动自组网中路由算法的研究现状 度时，有一个更好的策略。 此策略将分组转发到比本节点更接近目的节点的邻居节点中最靠近本节点 的邻居节点，这种策略叫做n e a r e s t w i t h f o r w a r dp r o g r e s s ( n f p ) 。在上图中就应 该是节点a 。如果所有结点都用n f p ，分组冲突的概率就会大大降低 1 。 另外一种转发策略是c o m p a s sr o u t i n g ，选择最接近发送者与接收者之间的直 线的邻居，在上图中就应该是b 。c o m p a s sr o u t i n g 展小化分组经过的空间距离。 最后，还可以让发送者随机的选择一个比它自己离目的节点近的节点，把分 组转发给它，这样做的好处是：可以最小化对邻居位置信息的精确性的要求，减 少转发分组需要的操作的数目。 但是，贪婪转发也可能找不到一条从源节点到目的节点的路径，即使它们之 间确实存在一条路径。s ( 源节点) 如果在它的传输范围之内找不到一个节点离 d ( 目的节点) 更近，此时贪婪转发就会失败，这就是局部最大( 1 0 c a l m a x i m u m ) ， 贪婪转发不能够从中恢复。 为了解决这个问题，有些研究人员提出可以把分组转发到一个后退距离最小 的节点，但是这会引起循环分组的问题。如果只把分组转发到前进方向上的节点 时是不会发生分组循环的。有些研究人员则提出，遇到局部最大情况时根本不要 转发分组。 f a c e 2 算法和g p s r 的周界路由策略( t h ep e r i m e t e rr o u t i n gs t r a t e g y ) 是两个非 常相似的基于平面图的恢复方法。这两种方法都是在每个分组的基础上( o na p e r - p a c k e tb a s i s ) 执行的，并且不要求节点存储额外的信息。当分组遇到局部最 大时就进入恢复模式，当分组到达一个离目的节点更近的节点时( 比分组进入恢 复模式时所在的节点离目的节点的距离近) ，它就返回到贪婪模式。下面简单介 绍一下基于平面图的恢复方法。 平面图( p l a n a r g r a p h ) 是没有相交边的图。a dh o e 网络可以被看成是一个图， 节点是图中的顶点，如果两个节点之间可以直接通信，那么相对应的顶点之间就 存在一条边，这样形成的图通常不是平面图。 为了从上面形成的图中构造一个连通的平面子图( c o n n e c t e dp l a n a r g r a p h ) ， 有一个很有名的算法：节点a 与b 之间的边如果被包含在该平面子图中，当且 仅当以a 为圆心的圆与以b 为圆心的圆( 两个圆的半径等于a 与b 之间的距离) d 中国科学技术大学硕士学位论文第2 章移动自组网中路由算法的研究现状 的交集中不包含任何节点。由于每个节点知道它所有邻居的位置，因此，一条边 是否被包括在子图中可以由每个节点自己局部的作出决定。 基于平面子图，可以简单的遍历平面子图来找到一条到达目的节点的路径， 一般想法是：在子图的面( f a c e ) 上逐步的将分组转发到离目的节点更近。当分 组处于恢复模式时，在每个面上，用右手定则沿着面的内部转发分组。如果源节 点和目的节点之间的连线与该分组转发的边界相交，就要检查这个交点是否比之 前碰到的交点离目的节点近，如果是，就转到以这条边( 分组将要遍历的边) 为 边界的新面上去，然后分组就会沿着新的边( c o u n t e r c l o c k w i s et ot h ee d g ei tw a s a b o u tt ob ef o r w a r d e da l o n gb e f o r es w i t c h i n gf a c e s ) 被转发。如果在原来的非平面 图中确实存在至少一条从源节点到目的节点的路径，这个算法就可以保证找到一 条。 分组头中包含有额外的信息，比如，进入恢复模式时所在节点的位置，引起 面改变( f a c ec h a n g e ) 的最后一个交点的位置，在当前面上遍历的第一条边，因 此，每个节点都可以仅仅根据关于它的本地邻居的信息作出所有的路由决定，包 括当分组第二次遍历当前面上的第一条边时发现目的节点不可达。 2 4 2 限制方向扩散路由算法 1d r e a m 路由算法： 在d r e a m 中，分组的发送者s 会把分组转发到所有的位于分组的目的地d 的方向上的下一跳邻居节点。为了确定这个方向，节点计算一个很可能包含d 的区域，叫做“期待区域”。 “期待区域”是一个以d 的位置( s 已知的) 为中心的圆，由于d 的位置很 可能已经过时，因此，“期待区域”的半径就设为( f 1 ，o ) u 。，f 1 是当前时间，t o 是s 中关于d 的位置信息的时间戳，v t 。是d 的最大速度。给定了“期待区域”， 通往目的节点的路径( d i r e c t i o n a lt o w a r dd ) 就由s 与d 之间的连线与一个角度 由来定义。接下来的邻居节点就使用自己知道的d 的位置信息重复这个过程。 如果某个节点在要求的方向上没有邻居，这时候就必须启动一个通信恢复过程 f 9 1 。如下图所示： 中稠科学技术大学硕十学位论文第2 章移动岛甜l 聃中路由算法的研究现状 图2 - 2d r e a m 分组转发的路径示意图 2l o c a t i o na i d e dr o u t i n g ( l a r ) ： l a r 没有定义基于位置的路由协议，但是它提出了利用位置信息来增强移动 自组反应路由方法的路由发现。移动自组反应路由经常使用分组流( f l o o d i n g ) 发现路由，假设节点有关于其它节点的位黄信息，这些位置信息就可以被l a r 用来把分组流( f l o o d i n g ) 限制到一个特定的区域，这与d r e a m 方法中所采用 的方式很像。 2 4 3 分层转发路由算法 在传统的网络中，可以通过建立某种形式的层次从而大大的减少每个节点必 须处理的复杂度，层次路由可以让网络扩展到拥有大量的节点。 lt r e m i n o d e sr o u t i n g ： t r e m i n o d e sr o u t i n g 算法结合了层次路由和基于位置路由，是t e r m i n o d e s 项 目的一部分。在分层转发路由算法中提出了一个2 级层次。如果目的节点离发送 节点很近，就根据一个距离矢量方案路由分组：对于长距离路由，就使用一个基 于位置的贪婪转发方法，一旦分组到达离接收者很近的区域时，就会用局部路由 协议转发该分组。实验表明，引入层次可以大大提高成功发送分组的概率，并且 与移动自组反应路由算法比起来大大减少了路由代价 1 1 。 1 6 中国科学技术大学硕士学位论文第2 章移动自组啊中路由算法的研究现状 为了防止用于长距离路由的贪婪转发遇到局部最大问题，发送者在分组头中 包含了一个位置列袁，分组必须经过包含这些位置的区域，区域之间的分组转发 是纯粹的贪婪转发。分层转发路由算法可以被看成是一个基于位置的源路由 ( p o s i t i o n b a s e ds o u r c er o u t i n g ) ，它要求发送者知道到达目的地所要经过的大致的 位置。在t e r m i n o d e s 路由中，发送者是从它已经与之取得联系( i nc o n t a c t w i t h ) 的节点处获得这个信息的，比如用局部路由协议可以到达的节点。一旦发送者获 得了这个信息，它就会定期的检查这条路径( t h ep a t ho fp o s i t i o n s ) 是否仍然有 效或者是否可以改善，因此，t e r m i n o d e s 长距离路由包含移动自组网反应路由方 法的因素。 2g r i dr o u t i n g ： g r i dr o u t i n g 是一种移动自组网中基于位置的路由算法，包含h i e r a r c h i c a l e l e m e n t s ，在g r i d 项目中提出。在g r i d 路由中，层次不仅用于提高可扩展性 ( s c a l a b i l i t y ) ，而且可以让那些不知道自己的位置的节点也加入到移动自组网中 【1 2 】。主要思想是，在每个使用p r o a c t i v e 距离矢量协议【2 2 】的区域中至少有一个 p o s i t i o n a w a r e 节点，每个区域中的p o s i t i o n - a w a r e 节点就可以被用作为代理 ( p r o x y ) ：p o s i t i o n u n a w a r e 节点用一个p o s i t i o n a w a r e 节点作为它的地址。如果 分组的目的地是一个p o s i t i o n - u n a w a r e 节点，那么它首先会被转发到一个 p o s i t i o n a w a r ep r o x y 然后再用p r o a c t i v ed i s t a n c ev e c t o rp r o t o c o l ( p r o a c t i v e 距离 矢量协议) 的信息转发该分组。 作为对长距离路由机制的一个补偿( r e p a i r ) ，提出了一个叫做i n t e r m e d i a t e n o d ef o r w a r d i n g ( 玎师) 的机制。就像在t e r m i n o d e sr o u t i n g 中一样，i n f 的思想是 执行一个p o s i t i o n b a s e ds o u r g er o u t i n g 。如果一个转发节点没有邻居可以转发，它 就把分组丢弃，然后向分组的发送者发送一个通知，分组的发送者收到通知之后， 就随机的为选择一个中间位置( 是一个圆心在发送者与接收者之间的连线的中点 的圆) ? ，分组必须经过这个中间位置，如果分组再次被丢弃，就增加圆的半径， 再次随机的选择一个位置，这个过程一直重复到分组到达目的节点，或者已经达 到一个预定义的值，发送者可以认为目的节点是不可达的。 1 7 中国科学技术丈学硕士学位论文第2 章移动自组网中路由算法的研究现状 2 4 4 以上各路由算法性能比较 分别对前面提到的五种基于不同转发策略的路由算法进行比较。考虑的主要 是随着移动移动自组网络中节点数的增加各种方法的性能变化。这里假设节点数 增加的时候节点密度保持不变，因此，随着节点数的增加，网络覆盖的面积也在 增加。由于在一个a * a 的正方形内两个均匀抽样点之间的期望距离随着a 变化， 因此两个均匀抽样点之间的h o p 数与增加的节点数的平方根成正比。 表2 1五种基于不同转发策略的路由算法性能比较 c r i t e r i o ng r e e d y d r e a ml a r t e r m i n o d e sg r i d g r e e d yr e s t r i e t e dr e s t r i c t e dh i e l a g e h i c a lh i e r a r o h i e a l t y p e d i r e c t i o n a ld i r e c t i o n a l f l o o d i n gf l o o d i n g c o m m u n i e a t i o n o ( 石)0 0 )0 0 1 )o ( 石)d ( 石) c o m p i e x i t y t o l e r a b l e t r a n s m i s s i o n e x p e c t e de x p e c t e d s g o r t - d i s t a n c e s h o r t - d i s h 2 i n c e p o s l t i o m n gr a n g er e g i o nr e g m nr o u t i n gr a n g er o u t i n gr a n g e a c c u r a c y r e q u i r e s a 1 1 f o r - a l ln oy e sn on on o l o c a t i o ns e r v i c e r o b u s t n e s s m e d i u m h i g hh i g h m e d i u mm e d i u r u i m p l e m e n t a t i o n m e d i u ml e v el o w h i g l ih i g h c o m p l e x i t y t y p e 描述分组转发的基本策略：c o m m u n i c a t i o nc o m p l e x i t y 表示在假设目的节 点的位置已知的情况下，把分组从一个节点发送到另一个节点需要的一步传输 ( o n e h o pt r a n s m i s s i o n ) 的平均数；转发策略能够容忍关于接收节点的位置的不 同程度的误差，用t o l e r a b l ep o s k i o ni n a c c u r a c y 表示；r e q u i r e sa l l - f o r - a ul o c a t i o n s e r v i c e 表示转发策略为了正确工作是否需要一个a 1 1 f o r - a l l 的位置服务 1 3 3 ；如果 单个中间节点的失败并不能阻止分组到达目的节点，那么这个方法的r o b u s t n e s s 中国科学技术大学硕士学位论文第2 章移动自组网中路由算法的研究现状 就很高，如果单个中问节点的失败导致分组的丢失，但是不需要重建一条新的路 由，这个方法的r o b u s t n e s s 就是中等的，如果单个中间节点的失败导致分组的丢 失，并且需要重建一条新的路由，这个方法的r o b u s t n e s s 就是很低的，这里介绍 的基于位置的分组转发策略都没有