（计算机应用技术专业论文）ad+hoc网络节能路由研究.pdf

中国科学技术人学母il ：学位论文 a dh o c 鹤络节能龉由研究 摘要 移动a dh o c 网络( m a n e t ) 是由一组带有无线收发装景的移动节点所组成的 多跳临时性自治系统。与其它移动通信网络相比，它没有固定的基础设施，两个 无法直接通信的移动节点可以借助其它节点的分组转发进行数据通信。网络中所 有节点既是主机，又是路由器，它们可以任意移动且地位平等。网络具有自组织 性、拓扑结构动态变化、移动节点能量和计算能力有限等特点。传统的路由协议 无法适应它的需求，必须为它设计专门的路由协议。 在a d h o c 网络环境中，移动节点通常为笔记本电脑或车载终端，节点能量 主要依赖于电池供电，而电池的再次充电十分困难，其能量难以补充，因此，能 耗问题是a dh o c 网络能否大规模应用的核心问题。在设计路由算法时，必须考 虑能量有限性因素，以功耗作为约束条件选择最佳路由，使网络负载能够平均分 配到各个节点，同时应尽量让没有参与数据转发的节点转入睡眠状态以节省能量 消耗，延长网络寿命。 本文在对现有a dh o c 网络路由协议与节能机制进行深入研究的基础上，提 出了一种新的基于节点能量消耗速度的节能路由算法：该算法属于混合路由协 议。它通过域发现机制确定节点的域，每个节点域的大小不同且可变。路出发现 时，域内实行主动路由算法，域间实行按需路由算法。该算法中定义了一个有关 节点剩余生命期与路由路径跳数的函数，并以浚函数值作为路由选择参数进行最 优路径的选择，从而使能量充足的节点承担更多通信任务。另外，它还提出了一 种基于潜在网络分割检测的节点睡眠机制。部分没有参与数据转发的节点如果能 够确认不会因为它的睡眠丽造成网络分割，则进入睡眠状态以降低能量消耗。基 于n s 2 网络模拟器，对该算法与同类的z r p 协议进行了仿真实验，实验结果表 明，垓算法的数据传输延迟小，节点死亡个数少，网络路由负载小，网络运行时 阳j 长。 主题词：a dh o c 网络混合路由节能分割检测 第l 页 中周科学技术入学碗i ：学位论义 a dh o c 阔络节能路由研究 a b s t r a c t m o b i l ea dh o cn e t w o r k ( m a n e t ) i sas e to fw i r e l e s sm o b i l en o d e sw i t h w i r e l e s st r a n s m i t t e rd e v i c e s d y n a m i c a l l yf o r m i n g a m u l t i - h o p a n d t e m p o r a r y n e t w o r k c o m p a r i n g w i t ho t h e rm o b i l en e t w o r k ，m a n e td o e s n t d e p e n d o n e x i s t i n g f i x e di n f r a s t r u c t u r e n o d e s b e l o n g i n g t oam a n e tc a l lc o m m u n i c a t e d e p e n d i n go nt r a n s m i t t a b i l i t y o fo t h e rn o d e sw h e nt h et w oe n d - p o i n t sa r en o t d i r e c t l yw i t h i nt h e i rr a d i or a n g e i ns u c han e t w o r k ，e a c h m o b i l en o d ea c t sn o to n l y a sah o s t , b u ta l s oa sar o u t e r t h e yc a r lm o v eo p t i o n a l l ya n dh a v ee q u a ls t a t u s c h a r a c t e r i s t i c so fm a n e tl i m i tt h eu s eo fe x i s t i n gr o u t i n gp r o t o c o l ，i n c l u d i n g s e l f - o r g a n i z a t i o n ，d y n a m i c a l l yv a r y i n gt o p o l o g ya n dn o d e sl i m i t e da b i l i t y s p e c i a l r o u t i n gp r o t o c o ln e e d t ob ed e s i g n e d t h ee n e r g yo fm o b i l en o d et h a ti sn o t e b o o kp co rt e r m i n a li n v e h i c l ei n m a n e t , u s u a l l yd e p e n do nb a a e r y r e c h a r g i n gb a t t e r y i sv e r yd i f f i c u l t e n e r g y c o n s u m p t i o no f m o b i l en o d el i m i te x t e n s i v ea p p l i c a t i o no fm a n e t t h er o u t i n g p r o t o c o ln e e ds e l e c t b e s tr o u t eb a s e de n e r g y r o u t eo v e r h e a dn e e db ea v e r a g e l y d i s t r i b u t e dt oa l ln o d e s t h en o d ew i t h o u tp a r t i c i p a t i o no fc o m m u n i c a t ej u s ts l e e pt o e c o n o m i z ee n e r g ya n d p r o l o n g l i f e t i m eo f n e t w o r k av a r i a b l ez o n eh y b r i dr o u t i n g p r o t o c o lb a s e d o nt h ee n e r g yc o n s u m p t i o n s p e e d o fn o d e si nm o b i l ea d - h o cn e t w o r k si sp r e s e n t e di nt h i sp a p e ne v e r yn o d em a i n t a i na z o n et h r o u g haz o n ed i s c o v e r i n gm e c h a n i s m w h i l ed i s c o v e r i n gr o u t e ，t h ep r o t o c o l i m p l e m e n t sp r o a c t i v er o u t i n ga l g o r i t h m s i nz o n ea n dr e a c t i v e r o u t i n ga l g o r i t h m s o u t s i d ez o n e ar o u t es e l e c tp a r a m e t e rc o m p u t e db yr e s i d u a ll i f e t i m eo f n o d e sa n dh o p c o u n to fr o u t ei su s e dt ob es e l e c t e dt h eb e s tr o u t e ，t h en o d e st h a th a v em o r ee n e r g y h a v em o r ep r o b a b i l i t yo fc h o s e n o t h e r w i s e ，am e c h a n i s mo fn o d es l e e p i n gb a s e do n p o t e n t i a ln e t w o r kp a r t i t i o nc h e c k i n ga l g o r i t h m i s p r e s e n t e d s o m en o d e sw i t h o u t p a r t i c i p a t i o no fc o m m u n i c a t ej u s ts l e e p ，i fo n l yt h en e t w o r ki s n tp a r t i t i o n e dd u et o t h en o d e s s l e e p i n g s i m u l a t i o nr e s u l tc o m p a r i n gw i mz o n er o u t i n gp r o t o c o li nn s 一2 s h o w se v z r ph a sl e s sd e l a yo fd a t at r a f f i ct i m e ，l e s sn u m b e ro fd e a t hn o d e s ，l o w e r r o u t i n go v e r h e a d ，a n dl o n g e rl i f e t i m eo f n e t w o r k k e y w o r d s ：m a n e t ，h y b r i dm u t i n g ，e n e r g ys a v i n g ，p a r t i t i o nc h e c k i n g 第2 负 中国科学技术人学颂i ：学位论文a dh o c 刚络节能路由研究 第1 章概论 随着信息技术的不断发展，互联网已成为人们生活中不可或缺的一部分， 人们对它的依赖性越来越强。然而在很多情况f ，普通的互联网技术却无法满足 我们的需求。例如当发生自然灾害时，如何来应用网络? 当进行科学考察、探险 时，没有可用的网络，又如何进行通信联络? 在战场上，如何实现动态过程中的 协同通信? 这些环境对通信有一个共同的要求，即动态的、可以快速部署的、不 依赖于或很少依赖现有的有线网络。满足这种环境的网络就是移动a dh o c 网络 ( m a n e t ) 。 1 1a dh o c 网络简介 1 1 1a dh o c 网络的产生 移动a dh o c 网络( 姒n e t ) 【l ，2 】是指一组带有无线收发装置的移动节点组 成的一个多跳临时性的自治系统。在这种环境中，由于节点的无线通信覆盖范围 的有限性，两个无法直接通信的移动节点呵以借助其他节点的分组转发进行数据 通信。 a dh o c 网络的前身是分组无线网( p a c k elr a d i 0n e t w o r k ) ，对分组无线网 的研究源于军事通信的需要，并已经持续了近2 0 年。早在1 9 7 2 年，美国国防部高 级研究计划局d a r p a 【3 】( d e f e n s ea d a v a n c e dr e s e a r c hp r o j e c ta g e n c y ) 就启 动了分组无线网( p r n e t ，p a c k e tr a d i on e t w o r k ) 项目，研究分组无线网在战场 环境下数据通信中的应用。为了将p r n e t 的成果加以扩展，以支持更大规模的网 络，在1 9 8 3 年又启动了高残存性自适应网络( s u r a n ，s u r v i v a b l ea d a p t i v e n e t w o r k ) 项目【4 】，开发能够适应战场快速变化环境需要的自适应网络协议。 并于1 9 9 4 年启动了全球移动信息系统( g l o m o ，g l o b em o b i l ei n f o r m a t i o ns y s t e m ) 项目【5 】，对能够满足军事应用需要的、可快速展开、高抗毁性的移动信息系 ，统进行全面深入的研究。在此基础上，i e e e 8 0 2 “标准委员会采用“a dh o c 网络” 词来描述这种特殊的自组织、对等式、多跳无线移动通信网络。由于a dh o c 网络所具有的广泛应用前景，互联网工程任务组( i n t e m e t e n g i n e e r i n g t a s kf o r c e ， i e t f ) 于1 9 9 7 年成立了专门的m a n e t ：e 作组集中从事m a n e t 网络的研究。 第5 页， 中图科学技术夫学坝 ：学位论文 a dh o c 嘲络节能路由研究 1 1 2a dh o e 网络的结构 如图1 1 所示，在a dh o c 网络中，既不需要个固定的网络结构，也没 有专用的固定的基站或路由器作为网络的管理中心。网络中的每个节点都相当予 一个移动的路由器，这些节点作为同等实体相互连接，实现信息包的转发，它 们都参与路由的发现和维护过程，从而构成了个a dh o c 网络。与有中心网络 相比，a dh o c 网络更坚固、更耐用，而且不需要提供固定的骨干设施，用户 就可以布置和操作分组无线网。 一l 图1 1 a dh o c 网络结构 1 1 3a dh o e 网络的特点 由于a dh o c 网络是种移动、多跳、自组式的网络，因此相对于传统的有 线固定网络和无线局域网，a dh o c 网络具有以下特点： 1 ) 网络系统的自组织性：每个网络节点可以动态的加入或退出网络系统， 同时不需要无线通信基站的支持。 2 ) 拓扑结构的动态性：由于网络节点的移动性和无线发送装置信道、功率 等方面的影响，导致了网络拓扑结构总是动念变化，而且这个变化通常是不可预 测的。 3 ) 无线传输带宽的有限性：由于无线信道本身的限制，以及噪声干扰、信 号衰减等因素，使无线传输带宽十分有限，无法达到有线网络带宽的水平。 4 ) 无线移动终端能量和计算能力的有限性：由于移动终端通常是便携式或 车载设备。节点一般依靠电池供电，其供电量和供电时间均受到限制，另外移动 第6 页 中国科学技术人学碗l 学位论文 a dh o c 喇络节能路由研究 终端的处理能力通常也较低。 5 ) 网络安全性差：由于a dh o c 网络采用无线信道、有限电源、分布式控制 等技术，因此更容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络 攻击。另外，由于节点本身又是路由器，不存在命名服务器和目录服务器等网络 设施，也不存在网络边界的概念，这使得a dh o c 网络中的安全问题更加复杂。 6 ) 网络管理的分布式：a dh o c 网络采用无中心结构，各个节点的地位平等， 共同参与整个网络系统的管理，任意节点的退出不会影响整个网络的运行。 7 ) 存在单向的无线传输信道：由于无线信道本身的特性，地形或发射功率 等因素，使得a dh o c 网络可能存在单向的无线传输信道。 1 1 4a dh o e 网络的应用 由p a dh o c 网络的这些特性，因此具有与普通无线网络不同的广阔应用前 景。a dh o c 网络最初的应用是在军事领域。在恶劣的战场环境下，通信设备不可 能依赖已经敷设的通信基础设旋，一方面这些设施可能根本不存在，另一方面， 这些设施会随时遭到破坏。在近年来得到迅速发展的美军战术互联网中。a d h o c 网络已成为它的核心技术，并在2 0 0 3 年的伊拉克战争中，得到了有效的应用。传 感器网络是a dh o c 网络技术应用的另一大领域。分散的传感器通过a dh o c 网络技 术组成一个网络，实现传感器之间及与控制中心之问的通信。由于a dh o c 网络不 依赖任何固定网络设施又能快速布设，使得它非常适合在地震、海啸、洪水等遭 受灾难打击后的紧急场合，这对于抢险救灾工作具有重要意义。移动会议等临时 场合是a dh o c 网络的又重要应用领域，它可以免去布线和部署网络设备的工 作，使得组网变得更为容易。另外，a dh o c 网络还在野外科考、家庭无线网络、 个人通信、商业应用等场合发挥了重要作用。 1 2a dh o c 网络的研究现状及重点 9 0 年代以束，随着移动a dh o c 网络的商业价值逐步被人们所认识，其研究 在世界范围内成为了一个热点，已经从无线通信领域中的一个小分支逐渐扩大到 相对较独立的领域。目阿，无论在国际七，还是在区域上( 欧洲和弧洲等地区) ， 周期性的a dh o c 网络学术会议h 益增多。总结国内外研究现状，a dh o c 网络技 术研究的重点主要集中在以下几个方面： 1 ) 信道接入技术：信道接入技术是a dh o c 网络协议的基础，它控制着节点 第7 页。 中冈科学技术大学硕t ：学位论史 a dh o c 嘲络节能路由研究 如何接入无线信道，对a dh o e 网络的性能起着决定性的作用。a dh o c 网络的无 线信道不同于普通网络的共享，“播信道、点对点无线信道和蜂窝移动通信系统中 由基站控制的无线信道，它是多跳共享的多点信道。即一个节点发送信息时，邻 居节点( 也只有邻居节点) 可以收到。此外，a dh o c 网络还存在独特的隐终端和 暴露终端问题，这些问题都需要通过专门设计的信道接入技术彳能解决。目前已 提出了数十种a dh o c 网络的信道接入协议，根据所使用的信道数目，可分为单 信道接入协议、双信道接入协议、多信道接入协议三大类。单信道接入协议是目 前应用最广泛的，如m a c a 协议【6 】，k a c a w 协议【7 】等，通过使用r t s c t s 控制报文握手机制部分地解决了隐终端问题。双信道接入协议，如d b t m a 协议 【8 】，d c m a 协议 9 1 等，在不同的信道上传送控制报文与数据报文，提高了 信道的利用率和频率空间复用度，同时也解决了隐终端和暴露终端问题。随着硬 件技术的发展，多信道接入协议成为了可能，如多信道c s m a 【1 0 1 ，d c a p c 【l1 】 等，在解决了隐终端和暴露终端问题的同时，也提高了系统的吞吐量。 2 ) 路由协议：路由协议是a dh o c 网络的重要组成部分。要实现多跳路由， 必须要有路由协议的支持。i e t f 成立的m a n e t 工作组目前就主要负责a dh o c 网 络i p 层路由的标准化工作。针对路由协议目前已开展了多项研究工作，并取得 了不少成果。根据发现路由的驱动模式的不同，可以将这些协议分为主动式路由 协议，d s d v 【1 2 l 和w r p 【1 3 】，按需路由协议，如d s r 【1 4 】和a o d v 【1 5 1 ， 混合路由协议，如，z r p 【】6 】和z h l s 【1 7 】。根据网络拓扑结构的差异，又 可以将它们分为平面结构的路出协议和分簇路由协议，如c e d a r 【1 8 】和h s r 【1 9 】。不过，从实现的难度来看，这些协议离实用性还有一定的距离。 3 ) 广播和多播；由于a dh o c 网络的特殊性，广播和多播问题也变得非常复 杂，它们需要链路层和网络层的支持。目前，国内一些大学和研究单位已经开始 研究a dh o e 网络中的广播和多播问题，并已经取得了阶段性进展。按照结构的 差异，可将它们分为无转发结构、m e s h 转发结构、树形转发结构三类。d d m 【2 0 】 是一种典型的无转发结构的多播路由协议，只用于单源多播业务。c a m p 【2 l 】是 一种采用m e s h 转发结构的多播路由协议，它引入了中心节点，采取成员发起转 发结构的建立和维护。a b f r i s 【2 2 】是一种树形转发结构的多播路由协议，它有 一个全网络的核心节点，共享的多播树树根都是离核心节点最近的节点。 4 ) 服务质量保证：a dh o c 网络出现的初期，主要用于传输少量的数据信息。 随着应用的不断扩展，需要在a dh o e 网络中传输话音、图像等多媒体信息。多 媒体信息对带宽、时延、时延抖动等都提出了很高的要求，这就需要提供一定的 服务质量保证。a dh o e 网络中的服务质量保证是个系统性问题，不同层都要提 供相应的机制。比如应用层要提供自适应编码和压缩技术，网络层要提供o o s 第8 负 中国科学技术大学硕士学位论文 a dh o c 网络节能路由研究 路由，链路层要提供资源预留策略等。因此，针对服务质量保证要基于某个特定 的网络和应用环境进行系统的研究。f q a m 【1 1 】是一种适用于a dh o c 网络的q o s 体系结构，协议栈的各层都提供了相应的服务质量保障。i n s i g n i a 【2 3 是一种 基于i p 的集成了软状态资源管理并支持q o s 的带内信令机制。 5 ) 安全问题：相比于传统的网络，a dh o c 网络更易受到各种安全的威胁和 攻击。由于移动节点有可能漫游到敌对环境中或者被攻击者所占领，因而攻击不 仅来自网络的外部，而且也有可能来自被攻破的内部移动节点，攻击者容易通过 无线链路窃听、假冒、重放和篡改所传输的信息，另外，由于网络的拓扑结构和 节点数目随时都在变化，因而节点之间的信任关系也经常改变。因此安全性较差 始终是制约a dh o c 网络应用的一个重要问题。s a o d v 【2 4 】改进了a 0 0 v 协议， 通过h a s h 链与数字签名保护a o d v 中的路由信息。l i d o n gz h o u 【2 5 】提出了一 种异步分布式密钥管理策略，由在一定阈值下的多个节点所组成的节点集作为认 证机构( c a ) ，共同完成密钥的分配与管理。 6 ) 能量节省机制：能耗问题是无线通信系统，特别是h dh o c 网络能否大规 模应用的核心问题之一。这一点对军事应用和传感器网络尤为重要。可以采用自 动功率控制机制来调整移动节点的功率，以便在传输范围和干扰之间进行折衷； 还可以通过智能休眠机制、采用合适的路由算法、使用功耗小的硬件来减少节点 的能量消耗。目前，a dh o c 网络中的节能机制主要包括两大类，一类是无线网 卡动念关闭机制，另一类是功率控制机制。无线网卡动态关闭机制又分为m a c 层节能机制与2 5 层节能机制，如p a m a s 协议【2 6 】与s p a n 协议 2 7 】等， 主要适用于由携带无线网卡的移动节点等构成的通信距离较近、信号发射功率较 小的网络，通常其收发功耗差别不是太大，发送功耗不到接收功耗的2 倍。功率 控制机制主要包括网络层的功率控制与链路层的功率控制，如c o m p 0 w 协议 【2 8 与p a r o 协议【2 9 】等，主要适用于由携带无线电台的移动节点等构成 的通信距离较远、信号发射功率较大的网络，通常其收发功耗差别非常大，发送 功耗可能比接收功耗高出一个数量级以上。 7 ) 网络互联技术：在很多场合下，a dh o c 网络要与其它网络互联。比如在 军事应用中，采用a dh o c 网络技术的战斗网要接入更高级的战场通信系统或区 域通信系统。在有的情况下，a dh o c 网络还要作为末端子网接入因特网。由于 a dh o c 网络采用了不同的路由协议和传输层服务，在网络互联时需要进行相应 的转换工作。s tj e a n 【3 0 1 提出了一种在蜂窝网上覆盖一个无线多跳网络的方案， 用一些无线路由器来代替蜂窝网络中的一些节点，以实现a dh o c 网络与蜂窝刚 的互联。 - 第9 页 中囡科学技术人学颤上学位论文a dh o c | q 络节能路由研究 1 3 本文工作与内容组织 a dh o c 网络路由协议的研究，作为其研究领域的热点之一，一直受到了广 泛的关注。已有的a dh o c 网络路由协议从不同的角度对无线多跳路由问题进行 了研究，对某一个或几个指标进行了优化，适用于不同的应用环境，但要设计一 个在所有情况下都普遍适用的a dh o c 网络路由协议基本上是不太可能的。 另外在a dh o c 网络中，移动节点一般使用电池供电，丽受技术的限制，电 池的容量在短期内很难得到大规模的提高。节点能量是有限的，它在使用过程中 的再充电是非常困难的，因此如何减少节点的能量消耗，最大化网络的生命期是 对a dh o c 网络的又一新挑战。 本文在对a dh o e 网络中路由协议与节能机制进行了大量研究的基础、卜，提 出了一个新的基于节点能量消耗速度的域可变路由协议，与同类的z r p 协议相比， 增加了一个域发现的过程，每个节点域的大小都不同且可变。另外该协议用一个 有关节点剩余生命期与路由路径跳数的函数作为路由选择参数进行最优路径的 选择，每个节点根据自身及周围节点能量的情况确定自己参与通信的机会，平衡 了整个网络中节点的能量消耗，延长了网络的生命期。另外，它还提出了一种基 于网络分割检测的节点睡眠机制，使得没有参与数据转发的节点能够通过转入睡 眠以降低能量消耗，同时义不至f 因为节点的睡眠而造成网络的分割。 本文在接下柬的部分里是这样组织的： 第二章对目前的a dh o c 网络路由协议进行了简要的介绍；第三章介绍了a d h o c 网络的节能机制；第四章详细介绍了所提出的域可变路由协议与基于能量消 耗模型的域可变路出协议；第五章是对全文的总结与展望。 第l o 蜓。 中国科学技术人学秧i ：学位论文 a dh o cl 叫络节能路由研究 第2 章a dh o e 路由协议介绍 现有的路由协议无论是基于距离矢量的路由协议，如r i p ，还是基于链路状 态的路由协议，如o s p f 等，都是为有线固定网络而设计的，它们的拓扑结构是固 定的，并需要周期性地交换信息来维护网络正确的路由表或网络拓扑结构图。由 于h dh o c 网络的拓扑结构是动态变化的，而且无线信道的带宽有限，还有可能山 于环境与发射功率等因素存在单向链路，因此，传统的路由协议是无法适应a d h o c 网络要求的。另外，a dh o c 网络中的节点通常使用电池供电，其能量有限， 且难以补充，因此路由算法应该将功耗作为。一个约束条件来选择最佳路由，并能 使空闲的节点自动进入休眠，以节省节点能量，延长网络寿命。针对a dh o c 网络 的这些特点，要求路由协议必须采用分布式操作，能够尽量支持单向链路，同时 应避免路由环路现象。考虑到无线节点特性，路由协议还应尽量简单，能够支持 节点的“休眠”操作以节省电源，能够提供安全性保护等机制。 为了解决无线a dh o c 网络中的路出问题，i e t f 特别成立了m a n e t ( m o b i l e a dh o cn e t w o r k s ) 工作组来研究无线a dh o c 网络中的路由协议。到目前为止， 已经提出了许多基于各种不同策略的路由协议，根据发现路由的驱动模式的小 同，可以将这些协议分为主动式路由协议( p r o a c t i v ep r o t o c 0 1 ) 和按需路由 协议( r e a c t j v ep r o t o c 0 1 ) 。根据网络拓扑结构的差异，又可以将它们分为平 面结构的路由协议( f l a tp r o t o c 0 1 ) 和分簇路由协议( c l u s t e r e dp r o t o c 0 1 ) 【1l ，3 l 】。下猫分别介绍不同类型路由协议的特点。 2 。1主动式路由协议与按需路由协议 2 1 1 主动式路由协议 主动式( 或先验式) 路出协议( p r o a c t i v ep r o t o c o l s ) 又称为表驱动路出 协议( t a b l ed r i v e np r o t o c o l s ) ，是一种基于路由表的路由协议，每个节点都 维护一张或几张到网络中其它节点的路由信息表。当网络拓扑结构发生变化时， 节点通过交互信息来实时地维护网络路由信息表。 主动路由的路由发现策略与传统路由协议类似，节点通过周期性地广播路 由信息分组，交换路由信息，主动发现路由。同时，节点必须维护去往全网所有 节点的路由。它的优点是当节点需要发送数捌分组时，只要去往目的节点的路由 存在，所需的延时很小。缺点是主动路由需要花费较大开销，尽可能使得路出更 中国科学技术大学硕，l ：学位论史 a dh o c 刚络节能路由研究 新能够紧随当前拓扑结构的变化。然而，动态变化的拓扑结构可能使得这些路由 更新变成过时信息，路由协议始终处于不收敛状态。在a dh o c 网络路由协议的研 究初期，主要思路是修改有线网络的路由协议以适应在a dh o e 网络环境中运行。 这些路由协议大多属于主动路由，如d s d v 【1 2 和w r p 【1 3 】。 由c e p e r k i n s 等人在1 9 9 4 年提出的d s d v 【1 2 1 ( d e s t i n a t i o n - s e q u e n c e d d i s t a n c e v e c t o r ) 协议是个典型的主动式路由协议，它是基于传统b e l l m a n f o r d 路由选择算法经改良而发展出来的，它采用序列号机制用于区分路由的新旧程 度，鳃决了传统距离矢量路由中的无穷环路问题，但它不能适应拓扑变化速度快 的a dh o c 网络，也不能支持单向信道。 在d s d v 路由协议中，每个节点都维护一张路由表，该路由表表项包括目的 节点、跳数，下一跳节点和目的节点序列号。其中目的节点序列号由目的节点分 配，主要用于判别是否过时，并可防止路由环路的产生。 每个节点必须周期性地与邻节点交换路出信息，当然也可以根据路由表的 改变来触发路由更新。路由表更新的两种方式：一种是全部更新( f u l ld u m p ) ， 即拓扑更新消息中将包括整个路由表，主要应用于网络变化较快的情况；另一种 方式是部分更新( i n c r e m e n t a lu p d a t e ) ，更新消息中仅包含变化的路由部分，通 常适用于网络变化较慢的情况。在d s d v 中只使用序列号最高的路由，如果两个路 由具有相同的序列号，那么将选择最优的路由( 如跳数最短) 。 如图2 1 所示，源节点a 在网络中广播一个找寻目的节点d 的路由请示，目的 节点d 在接收到这个路由请求后，向a 返回路由应答，即通过d f g a 的路径向 源节点a 发送一个序列号n 的路由应答，但在a 接收到这个序列号为n 的信息之i j ， d 又通过c 向a 发送了一个序列号为( n + 1 ) 的应答信息，由于( n + 1 ) f i ，a 就选择通 过c 的路由。这种方法可以避免路由环路的产生，但是，这种周期性的广播机制 必然带来网络负载的增加，因此，不能适应变化较快的a dh o e 网络，同时也不支 持单向信道。 。第j 2 页 中国科学技术大学坝l 学位论文 a dh o c 瑚络节能路由研究 图2 1d s d v 的序列号机制 d s d v 只能在给定的源节点和目的节点之问提供单条路径，协议需要选择以 下参数：定时更新的周期、最大的“沉淀时间”( s e t t l i n gt i m e ) 和路由失效 间隔时| 、日j ，以平衡路由的有效性和网络通信开销。 d s d v 路由协议中，节点维护着整个网络的路由信息，这样在有数据报文需 要发送时，可以立即进行传送，因而适用于一些对实时性要求较高的业务和网络 环境。但是在拓扑结构变化频繁的无线网络环境中，d s d v 可能存在以下问题，一 是节点维护准确路由信息的代价高，要频繁地交换拓扑更新信息：二是有的时候 町能刚得到的路由信息随即又失效了。因此，d s d v 协议主要用于网络规模不是很 大，网络拓扑变化相对不是很频繁的网络环境，而在拓扑变化频繁的网络中必须 采用其它的方法。 一种最简单的方法是“洪泛”方式，即节点在发送的报文头部携带目的节 点地址，向其邻节点广播，中问节点收到报文后根据目的节点地址判断自己是应 该转发报文还是接收报文。洪泛法的特点是简单，在某些情况下，如网络拓扑变 化异常频繁，路由发现和维护的代价很高时，洪泛法可能比其它路由协议的效率 更高；由于报文在多条途径中传输，因此数据的传输可靠率可能更高。但它的最 大问题是由于网络中很多非目的节点都参与了报文的转发，因此网络耗费太高。 2 2 2 按需路由 按需路由协议又称为反应式路由协议( r e a c t i v ep r o t o c o l s ) 。它是。种 被动式的路由协议，与主动式路由协议相比，在这类协议中，节点平时并不实时 第1 3 孤 中国科学技术大学硕士学位论文a dh o e 同络节能路由研究 地维护网络路由，只有在节点有数据要发送时，才激活路由发现机制寻找到达目 的地的路由。 与主动路由相反，按需路由认为在动态变化的自组网环境中，没有必要维 护去往其他所有节点的路由。它仅在没有去往目的节点路由的时候才“按需”进 行路由发现。因此，拓扑结构和路由表内容是按需建立的，它可能仅仅是整个拓 扑结构信息的一部分。它的优点是不需要周期性的路由信息广播，节省了一定的 网络资源。缺点是发送数据分组时，如果没有去往目的节点的路由，因需要路由 发现而引起一定的延时。 按需路由协议通常由路由发现和路由维护两个过程组成，如d s r 【1 4 】和 a o d v 【1 5 】。当源节点发现没有去往目的节点的路由时，触发路由发现过程。 这个过程类似于有线网络中建立电路连接的协商过程。图2 2 所示是一个典型的 路由请求过程。源节点a 在网络中广播路由请求分组，邻居节点b 和f 收到路由请 求分组后，记录分组经过了该节点，然后继续转发，直到到达了目的节点e 。节 点e 将会收到来自两条不同路径的路由请求分组，每个路由请求分组中包含有相 应的路径信息。节点e 根据一定的选择原则选取一条从源节点到目标节点的最优 路径，并将该信息附在向源节点a 发送的路由应答分组中，作为对路由请求的 响应。源节点a 根据收到的路由应答分组更新路由信息，从而获得去往目的节点 e 的路由。当拓扑结构发生变化时，通过路由维护过程删除失效路由，重新发起 路由请求过程。路由维护通常依靠底层提供的链路失效检测机制触发。 路径1 ： 路径2 ： a ，b ，c ，d ，e 图2 2 按需路由请求示例 ，c a o d v 【1 5 】( a dh o co nd e m a n dd i s t a n c ev e c t o r ) 协议是在d s d v 协议基础 上结合类似d s r 中的按需路由机制进行改进后提出的，它借浆了d s r 协议的路由发 第1 4 页 中国科学技术人学坝 ：学位论史a dh o c 嘲络节能路由埘f 究 现和维护机制，同时使用d s d v 的逐跳路出转发方法和序列号机制。相对于d s d v ， a o d v 通过建立按需路由表减少了广播包的数量。在a o d v 协议中，路由中的每个节 点都维护路由表，因而数据报文头部不再需要携带完整的路由信息，从而提高了 协议的效率。 路由发现过程 a o d v 协议采用与d s r 协议类似的广播式路由发现机制。与d s r 协议相比，a o d v 的路由依赖于中间节点建立和维护的动态路由表。a o d v 的路由发现过程由反向路 由的建立和前向路由的建立两部分组成。 反向路由指从目的节点到源节点的路由，用于将路由响应报文回送至源节 点。反向路由是源节点在广播路由请求报文的过程中建立起来的。如图2 3 ( a ) 所示，反向路由可能会有多条。 前向路由指从源节点到目的节点方向的路由，用于以后数据报文的传送。 前向路由是在节点回送路由晌应报文的过程中建立起来的，如图2 3 ( b ) 所示。 字段： ( a ) 反向路由的建立 一前向路由 反向路由 ( b ) 前向路由的建立 图2 3a o d v 的路由建立过程 a o d v 的路由发现过程如下： 1 ) 源节点首先发起路由请求过程，在发起的路由请求报文中携带以下信息 潺地址，源穿确号f 播i d , 黾的地址目的亭确s 碜数计数器 第1 5 页 中陶科学技术人学硕：学位论文 a dh o c 。i j 络节能路由研究 其中，序列对 唯一标识1 个路由请求。 2 ) 中间节点在收到路由请求报文时，比较本节点和目的节点的地址， 如果自己是目的节点，则回复路由响应报文。否则转步骤2 ； 根据 判断是否收到过该请求消息，如果收到过受l j 丢弃该 请求消息，否则转向步骤3 ； 记录相应的信息，以形成反向路由。记录的信息包括：上游节点地址( 即 向本节点发送路由请求消息的节点) 、目的地址、源地址、广播i d 、反向路由 超时时长和源序列号等。同时跳数计数器加l ，向邻节点转发该路由请求报文。 与d s d v 协议相似，在a o d v 协议中也引入了序列号，包括源序列号和目的序 列号。不同的是在a o d v 中，这些序列号都是单调递增的，它们主要用于避免过时 的缓冲路由对系统带来负面的影响。其中源序列号用在路由请求广播过程中保证 反向路由的有效性，而目的序列号则用来维护的向路由的有效性。 路由表管理及维护 a o d v 路由协议中的路出表主要包括目的节点、下一跳节点、距离目的节点 的跳数、目的节点序列号、本路由的活跃邻节点和本路由的超期时长等信息。 同时，在a o d v 协议中，节点还存储一些与路由表相关的信息，如： l ) 路由请求超时定时器：和反向路由相关的定时器，当定时器超期后，节 点仍未收到路由响应报文时。节点则认为该反向路由无效，删除该反向路出。 2 ) 活跃超时时长：和前向路由相关的时长。当超过活跃时长时间后，节点 仍然无数据利用该路由发送时，删除该路由( 即使该路由可能有效) 。 当节点使用路由表中的某项路由发送数据时，该路出的超期时长更新为当 前时问+ 活跃超时时长。当节点收到一条新的路由时，选择新路由和本节点存储 路由中目的节点序列号大的路由为有效路由。当序列号一样时，则选择跳数小的 路由。 节点的移动可能会造成现有路由的失效，根据节点的不同，a o d v 路由协议 的处理方法不同。 当由于源节点移动而造成路由失效时，此时只能由源节点再次发起路由请 求过程。 当出于中间节点或目的节点的移动而造成路由失效时，检测到路由中断的 节点主动向其上游节点发送路由响应报文，该报文中将到目的节点的跳数置为无 穷大，同时将目的节点的序列号加1 。这样，上游节点在收到该路由响应报文时， 会及时更新本地相关路由。 中国科学技术大学硕上学位论文 a dh o e 网络节能路由研究 a o d v 协议还引入了一种邻接探测机制，节点周期性的发送h e l l o 分组，通告 其相邻节点自身的存在性。但在无线链路条件下，h e l l o 分组不是通告邻接性的 唯一手段。节点可以通过监听邻接节点对信息分组的转发来确定自己是否在其通 信范围内。如果没监听到这种转发，还可以通过h e l l o 分组等手段来确定邻接信 息。但总的来说，h e l l o 分组为在无线通信范围内的其他节点掌握雕鲁连通性信 息提供了方便。 a o d v 协议由于通往目的节点路径中的节点建立和维护路由表，数据报文头 部不需要携带完整路径，减少了数据报文头部路由信息对信道的占用，提高了系 统效率，因此协议的带宽利用率高，能够及时对网络拓扑结构变化作出响应，同 时也避免了路由环路现象的发生。但它也存在以下问题： 1 ) a o d v 协议仅适用于双向传输信道的网络坏境。由于在路由请求消息的广 播过程中建立了反向路由，供路由响应报文寻路，因此网络要满足双向传输信道 的要求； 2 ) 由于a o d v 协议采用了超时删除路由的机制，因此即使路由未失效，在超 过时限后也将被删除。 2 1 3 混合路由 在主动路由协议中，节点通过周期性地广播路由信息分组来维护去往全网 所有节点的路由。它的优点是当节点需要发送数据分组时，只要去往目的节点的 路由存在，所需的延迟很小。缺点是主动路由需要花费较大的开销，尽可能使得 路由更新能够紧随当前拓扑结构的变化。然而，动态变化的拓扑结构可能使这些 路由更新变成过时信息，使路由协议始终处于不收敛状态。 在按需路由协议中，节点没有必要维护去往其它所有节点的路由，仅在没 有去往目的节点路由的时候才“按需”进行路由发现。因此，它的优点是不需要 周期性的踌由信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果 没有去往目的节点的路由，数据分组需要等待因路由发现引入的延时。 由此可见，主动路由和按需路由策略由于对路由发现的不同处理方式，使 得它们的优缺点可以互为补充。同时使用主动与按需路由簸略的混合路由协议成 为最能适应a dh o e 网络的路由策略，如z r p 【1 6 1 和z h l s 【1 7 1 。 z r p ( z o n e r o u t i n g p r o t o c 0 1 ) 【1 6 1 是第一个利用集群结构，混合使用按需和 主动路由策略的a dh o c 网络路由协议。一方面，它将主动路由程序范围限制在 节点的邻近区域内。这些邻近的路由信息，是节点最常用到的，它最小化了主动 路由机制中路由请求的相关资源浪费。另一方面，对于贯穿整个网络( 可能是全 - 第1 7 页 中国科学技术人学硕士学位论文h dh o c 网络节能路由研究 球性的) 的搜索，通过有效地询问网络中有选择的节点来完成，而无需询问所有 的网络节点。协议中每个节点都有一个路由域，路由发现过程分为域内路由与域 问路由二部分。 路由域概念与域内路由( i a r p ，i n t r a z o n er o u t i n gp r o t o c 0 1 ) 网络中的每个节点都定义了一个路由域(