（通信与信息系统专业论文）移动ad+hoc网络中基于qos的多径路由算法研究.pdf

摘要 移动a dh o c 网络是一种不依赖于网络基础设施，移动节点之间通过无线通信 相互进行路由，临时组网的一种多跳无线通信网络。这种网络具机动性高，部署 快等诸多特点，可应用于现代战场、救灾、会议等许多临时场合。 在移动a dh o e 网络中，由于其网络拓扑频繁变化以及自身节点能量有限的特 点，许多考虑能量的协议并不能满足q o s 需求。为了保证能量节省和q o s 需求， 本文在a o m d v 协议的基础上，实现一种基于跨层优化的节能多径路由算法。算 法把网络层能量信息、数据链路层分组队列缓存长度信息协同起来，加权形成了 一个新的综合代价函数作为选路标准。同时，利用缓存和定时技术，将到达目的 节点的r r e q 信息缓存起来。当定时器到时，利用综合代价函数作为选路标准， 形成多条路径。仿真表明，算法在网络负载较重的情况下，保证网络端到端迟延 迟的降低，网络吞吐量增加了1 3 8 ，而随着发包速率增加，网络寿命也增加了 l5 。 关键宇：多径路由跨层设计q o s 网络寿命端到端迟延吞吐量 a b s t r a c t am o b i l ea dh o cn e t w o r k ( m a n e t ) i sac o l l e c t i o no fm o b i l en o d e sw i t h o u ta n y b a s es t 2 l t i o no ri n f r a s t r u c t u r es u p p o r t m o b i l en o d e sc o m m u n i c a t ew i t ho t h e rn o d e s d i r e c t l yw i t h i naw i r e l e s sc o v e r a g e ，o t h e r w i s et h e yc o m m u n i c a t e v i am u l t i 。h o pr o u t e s - b e c a u s ea dh o cn e t w o r k sc a nb ee a s i l yd e p l o y e d ，t h e yh a v eb e e na p p l i e di nm a n y s u c c e s s f u lf i e l d ss u c ha sm i l i t a r y ，d i s a s t e rr e c o v e r y , c o n f e r e n c e e ta l i na dh o cn e t 、o r l ( s ，h o w e v e r ，m a n yp r o t o c o l sa l en o tf l e x i b l ee n o u g ht oc o p ew i t h t h ed y n a m i c so fn e t w o r ke n v i r o n m e n t ，t h u si tw i l lp r e v e n tp e r f o r m a n c eo p t i m i z a t i o n m a j o r i t vo fr o u t i n gp r o t o c o l sc o n s i d e r i n ge n e r g ye f f i c i e n c ya st h em a i no b j e c t i v e c a l l n o ta s s t i r eq o sr e q u i r e m e n t s i no r d e rt os a v ee n e r g ya n de n s u r eq o sa s s u r a n c e ，t h e i n f o n n a t i o no fd a t al i n kl a y e rm u s tb ea d d e dt od e s i g nar o u t ep r o t o c o l s o ，an e w m u l t i p a t hp r o t o c o lc a l l e dq o s s u p p o r ta o m d vp r o t o c o lb a s e do n c r o s sl a y e rd e s i g ni n a dh o cn e t w o r k ( q o s a o m d v ) i sp r o p o s e dw h i c hi sb a s e do ne n e r g ys a v i n ga n d t h e s h o r t e s tq u e u el e n g t ho fb u f f e ri nd a t al i n kl a y e r i tc o o p e r a t et h ei n f o r m a t i o no ft h e n e t w o r kl a y e rw i t ht h a to fd a t al i n kl a y e rt om a k e ag e n e r a lc r i t e r i o no nr o u t es e l e c t i o n b yu s i n gt h et e c h n o l o g yo fb u f f e ra n dt i m i n g ，i ts a v e st h er r e q sa r r i v i n g a tt h e d e s t i n a t i o n s w h e nt h et i m e ri se x p i r e d ，i tb u i l d sm u l t i p l ep a t h so nt h ec r i t e r i o no f g e n e r a lf u n c t i 0 1 1 t h ep e r f o r m a n c ei sc o m p a r e db e t w e e nq o s - a o m d v a n da o m d v b yn s 2 i ti ss h o w nt h a tq o s a o m d vi s a b l et od e c r e a s et h ee n dt oe n dd e l a y s i g n i f i c a n t l yi nh e a v y t r a f f i cl o a d s i ti sa l s os h o w nt h a tt h en e t w o r kt h r o u g h p u ti n c r e a s e n o1 e s st h a n13 8 a n dt h en e t w o r kl i f e t i m ei n c r e a s ea b o u t1 5 w i t ht h ei n c r e a s eo f p a c k e tr a t e k e y w o r d s ： m u l t i p a t hr o u t i n g n e t w o r kl i f e t i m e c r o s s - l a y e rd e s i g n e n dt oe n dd e l a y q o s t h r o u g h p u t 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：塑垒互丝 日期： 型! ：墨：f ! 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在一年解密后适用本授权书。 本人签名： 导师签名：日期：塑竺：主：! !二 第一章绪论 第一章绪论 随着人们对随时随地可以进行自由通信的需求，近几年来，无线通信网络无 论在技术上还是在商业上都获得了飞速的发展，并且已经在世界范围内被广泛地 应用。目前主要的无线通信网络可以分为两大类，一类是由目前第2 代数字蜂窝 移动通信系统发展而来的第2 5 g 和3 g 移动通信。另一类是应用了国际电气和电 子工程师协会( i e e e ) 开发的8 0 2 系列无线协议的无线通信系统。传统的无线通 信技术一般是有中心的，需要依赖预先部署的网络基础设施才能运行1 1 1 。对于有些 特殊的场合来说，当没有这种预先部署的固定设施可以使用时，比如，在战场上 指挥快速展开的部队，发生地震或水灾等大型灾害后的营救等。在这些应用场景 中，不能依赖于任何预设的基础设施，在此情况下，移动a dh o e 网络应运而生， 并且迅速成为了移动通信技术的一个重要分支，将在未来的通信技术中占据重要 地位。 1 1 移动a dh o e 网络研究背景 移动a dh o e 网络，是一种没有有线基础设施支持的移动网络，网络中的节点 均由移动节点构成。移动a dh o e 网络可以独立工作，也可以与i n t e m e t 或蜂窝无 线网络连接。在后一种情况中，移动a dh o e 网络通常是以末端子网的形式接入现 有的网络。考虑到带宽和功率的限制，移动a dh o e 网络一般不适合作为中间传输 网络，它只允许目的地是网络内部节点的信息进出，而不让其他信息穿越本网络， 从而大大减少了与现存i n t e m e t 互操作的路由开销1 2 j 。 在移动a dh o e 网络中，节点可能处在不停的移动状态下，网络的拓扑结构处 于动态的变化之中，而节点一般采用电池供电，当前电池提供的能量有限，也不 能随时充电或更换电池，导致节点的工作时间比较短。网络中部分节点电量耗尽， 不仅致使这些节点本身不能工作，而且有可能影响网络的整体性能，造成网络的 分裂，严重时导致大部分生存下来的节点不能相互通信。传统的基于距离矢量和 链路状态的路由协议并不适用于拓扑结构高度动态变化的移动a dh o e 网络。因此， 需要采用节能机制减少接点的能量消耗，有效延长节点的工作时间和网络的整体 寿命，开发良好的路由协议是建立移动a dh o e 网络的首要问题，同时也是主要的 热点和难点问题之一。 近年来，随着无线移动环境多媒体业务的发展，检测环境日趋复杂多变，迫 切需要将信息量丰富的图像、音频、视频等多媒体引入到无线a dh o e 网络为基础 的检测环境活动中来，实现细粒度，精准信息的环境监n t 3 1 。目前，网络体系结构， 2 移动a dh o e 网络中基于q o s 多径路算法研究 节点硬件平台，通信协议设计，协同信息处理，能量节省策略等方面积累了一些 成果。然而，无线a dh o c 网络中服务质量( q o s ) 这一重要的研究领域尚未受到广 泛的关注。无线a dh o e 网络具有的感知多媒体丰富，处理任务复杂等显著特点， 使得无线a dh o c 网络中q o s 路由保障问题已经成为a dh o c 网络研究领域一个重 要课题。 综上所述，移动a dh o c 网络技术已经在全球很多领域内都得到了应用，而且 随着a dh o c 网络技术的不断成熟和进步，它将得到更广泛的应用空间。因此，研 究移动a dh o c 网络及其涉及的关键技术具有非常重要的实际意义。本文正是在此 背景下，开展了对移动a dh o c 网络中路由协议的研究工作。研究工作对移动a d h o c 网络节能进行了深入展开，同时在节能的设计方案中，考虑了跨层设计的思想， 消除了网络端到端迟延对q o s 的制约，保证了能量节省和公平性。 1 2 移动a dh o c 网络路由技术研究现状 路由协议是a dh o c 网络研究中的热点问题之一，i e t f 为此还特别成立了 m a n e t 工作组，提出了一系列的保证网络连接性的路由协议【4 】。从功能上讲， 路由协议是通信网络中的一套将业务数据从源节点指引到目的节点的机制。路由 协议的主要设计目标是满足应用需求的同时尽量降低网络开销，取得资源利用的 整体有效性，扩大网络吞吐量。 移动a dh o c 路由协议需要实现一下功能( 1 ) 能感知网络拓扑结构的变化：移 动a dh o c 路由协议要能够检测到拓扑的动态变化。因为移动a dh o c 网络需要进 行多跳通信，所以路由协议必须确保路径中的链路具有很强的连接性。移动a dh o c 网络的节点必须知道它周围环境以及与它直接进行通信的节点。( 2 ) 维护网络拓扑 的链接：因为每个移动主机可能随时改变位置，所以网络拓扑是频繁变化的，这 样移动a dh o c 路由协议为了使节点之间的链路具有较强的连接性，它必须动态的 更新链路状态和对自己重新配置，如果采用中心控制的路由算法，为把节点链路 状态的变化传输到所有节点，就会消耗过多的时间和精力，显然是不合适的。所 以采用一种全分布式的路由算法。( 3 ) 高度自适应路由：移动a dh o c 网络中，节 点的高速移动，要求一个高度自适应的路由机制来处理快速的拓扑变化。 1 9 9 4 年，c e p e r k i n s 和p r a v i nb h a g w a t 提出的目的节点序列号距离矢量路由 协议d s d v ( 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 r o u t i n g ) 5 j 是基于传统 b e l l m a n f o r d 路由选择算法改良而发展出米的，其特点是利用目的节点序列号解决 了d b f ( d i s t r i b u t e db e l l m a n f o r d ) 算法的路由环路和无穷技术问题。d s d v 属于 主动路由协议，它能迅速为节点建立路由并发送数据，在任何情况下都能避免产 生路由环路。虽然在网络拓扑结构频繁变化的情况下，d s d v 协议的收敛性能并 第一章绪论 不好，但是在一般情况下，收敛速度很快。当网络的规模扩大的时候，路由表容 量、开销和带宽也相应增加。 1 9 9 6 年，d b j o h s o n 和d a m a l t z 提出可移动a dh o c 网络源动态路由协议 d s r ( d y n a m i cs o u r c er o u t i n g ) 引，d s r 使用源路由而不是逐跳路由，每一个数据分 组在其头部携带了完整的必经节点的顺序列表，每个节点有一个高速缓存，用来 存放到目的节点的所有路由。d s r 路由协议缺点是数据分组的额外开销较大，路 由缓存技术使得过期路由影响了选择的准确性。 在d s d v 和d s r 协议的基础上，1 9 9 9 年，c e p e r k i n s 和e m r o y e r 提出了 按需距离矢量路由协议a o d v ( a dh o c o n d e m a n dd i s t a n c ev e c t o rr o u t i n g p r o t o c 0 1 ) 7 1 ，a o d v 协议本质上是d s d v 和d s r 的结合，它是在d s d v 的基础 上，结合d s r 的按需路由机制改进而提出的，不同之处在于它采用了逐跳转发的 方式而不是d s r 的源路由方式以提高带宽利用率。 随着a dh o c 网络技术的不断发展，有限的节点能量成为制约a dh o c 网络发 展的瓶颈。移动a dh o c 网络的节点能源主要由电池提供，而节点电池更换或充电 都是不可能的。因此，针对移动a dh o c 网络有能源有限的特点，许多文献提出了 移动a dh o c 网络的节能路由协议的研究目前已经取得的重要的研究成果。 在国外，节能和q o s 多径路由研究起步比较早，2 0 0 4 年，s m s e n o u c i 和g p u j o l l e 提出了l e a r a o d v ，p a r a o d v 和l p r a o d v 三种节能协议懈j 。 l e a r a o d v 协议中每个移动节点依靠本地节点的剩余能量信息来决定自己是否 加入路径，剩余能量低的节点不加入路径，避免了网络的提前分裂。p a r a o d v 力图使总能耗函数最小化。l p r - a o d v 使网络的生存期寿命最大化，也就是说尽 量避免能量较低的节点加入链路。但是，这些协议都单一从能量角度考虑节点是 否加入路径，可能导致路径含有很多跳数，如果建立这样的路径，网络总体的能 耗就会很大，反而不利于网络寿命的提高。2 0 0 8 年，r o b e r t a 提出了一种基于拓扑 控制和能量控制的路由协议】，协议实现了网络节能。v i n a y 等人提出的将节点按 照剩余能量分为三级，针对节点剩余能量所处的级别，选择不同的处理方法，同 时目的节点选择路由按照作者提出的链路状态比f l2 1 ，该协议有很好的节能性能。 在国内，q o s 多径节能技术也取得了不小的进展，文献【3 3 】提出了一种基于缓存 技术的节能多径路由方案，该方案虽然节约了能量，但是增加了网络迟延。秦颖 等人提出了种基于节能和流量均衡的a dh o e 网络协议1 1 0 1 ，它同时考虑了能量和 网络流量两方面的因素，并将二者结合形成了新的代价函数并为选路标准，代替 已有协议最短迟延选路标准，但该算法没有考虑其他q o s 参数的制约。2 0 0 7 年，陈 筱蕾等人研究了基于迟延的多径路由技术，该协议把节点最短队列长度作为选路 标准，实现了网络迟延和网络开销的降低【4 引。 以上协议都是针对移动a dh o e 网络能量有限的缺点进行的改进，随着无线移 移动a dh o c 网络中基于q o s 多径路算法研究 动环境中多媒体业务的发展，检测环境日趋复杂多变，迫切需要将信息量丰富的 图像、音频、视频等多媒体引入到无线a dh o e 网络为基础的检测环境活动中来， 实现细粒度，精准信息的环境监测。目前，网络体系结构、节点硬件平台、通信 协议设计、协同信息处理、能量节省策略等方面积累了一些成果。然而，无线a d h o e 网络中服务质量( q o s ) 这一重要的领域尚未受到广泛的关注。无线a dh o c 网络具有的感知多媒体丰富，处理任务复杂等显著特点，使得无线a dh o e 网络中 q o s 路由保障问题已经成为a dh o c 网络研究领域一个重要课题。 1 3 本文的研究内容和组织结构 本文在节省移动a dh o e 网络的能量消耗的同时保证网络的q o s ，以网络生存 期、网络的端到端迟延以及网络的总体吞吐量为研究目标，着重研究了在数据链 路层和网络层上的节能算法。在跨层设计思想的基础上，联合这两个层的相关信 息，并结合无线链路的特点，实现了行之有效的基于跨层设计的节能多径路由算 法。以n s 作为仿真平台，仿真证明了本文所改进算法的优越性，对于移动网络的 节能算法研究以及实现具有一定的参考价值。 本文的结构组织结构如下： 第一章阐述了论文的研究背景，以及移动a dh o e 网中路由技术的国内外发展 研究现状，以及在此背景下，阐述了基于节能的q o s 多径路由协议的目的和意义。 第二章阐述移动a dh o c 网络中的关键技术之一路由协议，开始阐述了几个典 型的路由协议，本文重点关注的多径路由协议( a o m d v ) 。 第三章研究了多媒体业务中基于跨层设计的多径节能路由技术，主要结合节 能的路由技术可跨层设计技术，在路由发下阶段重新制定了新的选路标准，该标 准结合网络层的节点的剩余能量信息和数据链路层分组缓存队列长度信息，组成 综合选路标准。形成改进的多径路由协议( q o s a o m d v ) ，最后是对新协议的仿 真比较。 第四章主要阐述了移动a dh o e 网络的仿真平台n s 2 ，以及在对第三章改进的 协议进行的分析比较。仿真结果表明改进算法具有一定的优越性。 最后一章是总结了本文的全部内容，同时对所涉及的技术进行了展望。 第二章移动a dh o e 网络的基本结构及协议 第二章移动a dh o c 网络的基本结构及协议 在移动a dh o e 网络中，移动节点可以在网络中随意移动。节点的移动会导致 节点之间的链路增加或消失，节点之间的关系不断发生变化。在自组网中，节点 可能同时还是路由器，移动会使网络拓扑结构不断发生变化，而且变化的方式和 速度都是不可预测的。因此，移动a dh o e 网络的体系结构和网络中采用的协议变 得尤为重要。 2 1 移动a dh o c 网络的体系结构 移动a dh o e 网络一般有两种结构：平面结构和分簇结构。 平面结构如图2 1 所示，这种结构采用全分布式控制，所有节点地位平等，又 称为对等式结构。 、，、- ，。，一一一一一，- ，7 图2 1 平面网络结构 分簇结构如图2 2 所示。在分簇结构中，节点被划分成簇，每一个簇节点产生 一个簇首，负责本簇中节点的管理，这些簇首形成了高一层次的网络，在高一层 次的网络中又可以分簇，再次形成高一层次的网络，直至最高层次。在不同的簇 中可以使用不同的工作频率，在簇内可以采用高效的多地址协议，如u p m a | 1 3 】， t d m a ，f d m a ，c d m a 等。在分簇结构中，需要采用自组织的算法【1 4 】来产生簇 头，计算最佳路径和进行动态资源分配。簇头结点负责簇间数据的转发。在图2 2 中，当节点1 要与节点1 4 通信时，节点l 先把数据发给本簇的簇首，即节点4 ， 节点4 发现节点1 4 在别的簇中，就把数据转发给节点1 4 的簇首，即节点1 6 。节 点1 6 收到数据后，发现节点1 4 是自己的簇成员，把数据发给节点1 4 。 平面结构的网络比较简单，网络中所有节点是完全对等的，原则上不存在瓶 颈，所以比较健壮，但其缺点是网络规模受限，当网络的规模增加到某个程度时， 所有的带宽都可能被路由协议消耗掉【i5 ，网络的可扩展性较差，因此在此情况下 应优先考虑分簇结构。然而，分簇结构也有其缺点，即需要复杂的簇首选择算法 和簇维护算法，簇首节点的任务相对较重，可能成为网络的瓶颈，簇问路由不一 移动a dh o e 网络巾基于q o s 多径路算法研究 定是最优路由。总之，当网络规模较小时，应当采用简单的平面结构，而当网络 规模较大时应当采用分簇结构。当前，移动a dh o c 网络主要以一种末端网络形式 存在，应用规模都较小，分簇的思想不明显，这在一定程度上抑制了分簇思想在 移动a dh o c 网络的研究。因此，除非特殊说明，本文在后续章节讨论的移动网络 都是指采用平面结构的网络。 图2 2 分簇网络结构 2 2 路由协议概述 2 2 1 移动a dh o e 网络协议的参考模型 与有线网络相比，移动a dh o e 网络的工作环境有诸多的不同，所选择的技术 上也有较大的差异，主要体现在网络的底三层【1 1 ，即物理层，数据链路层和网络层， 其中网络层的差异最大。其协议栈结构如表2 1 所示。 表2 1 移动a dh o c 网络协议栈 应用服务 应用层 传输服务 传输层 分组转发和路由网络层 链路控n 信道接入链路层 无线信道物理层 物理层是一组低功耗，高能力，能在运动中工作的物理传输设备，提供无线 传输能力，完成无线信号的编码译码发送接收等工作，以支持移动组网。实际应 第二章移动a dh o e 网络的基本结构及协议 用中，移动a dh o e 网络物理层的设计根据实际需求而定。一般而言，移动a dh o e 都是基于无线通信，目前大家一致采用的是基于2 4 g 的i s m 频段。同时，物理层 的设备可提供多频段，多模式的传输方式。 链路层控制是对共享无线信道的访问和对逻辑链路的控制，提供可靠的无线 通信逻辑链路，以支持有效的逻辑访问。移动a dh o e 链路层又可分为m a c 层和 l l c 层，m a c 层决定了绝大部分的功能如数据的传输、同步、纠错、以及流量控 制等。 网络层是移动a dh o c 技术的重点，也是其与其他现有网络的主要区别所在， 支持网络工作的传输协议，移动组网算法和动态路由协议。正是由于移动a dh o e 网络层路由协议基于移动a dh o e 网络的重要性，使之成为一个研究的热点。一个 好的移动a dh o c 网络层路由协议应该满足以下要求：分布式运行方式，提供无环 路由，按需进行协议操作，具有可靠的安全性，提供设备休眠操作和单信道到的 支持技术等。而对移动a dh o e 网络层路由协议进行定量衡量的标准包括端到端的 平均迟延，网络的生存期，网络的吞吐量，分组的平均递交率路由协议的开销等。 传输层主要完成端到端通信的建立，因为无线差错和节点的移动性，t c p 将 所有的分组丢失都归因于拥塞并启用拥塞控制和避免算法，所以，传统的t c p u d p 会使无线移动a dh o e 网络分组丢失很严重。若在a dh o c 网络中直接采用t c p 会 导致端到端吞吐量无谓的降低。目前一般是对传统网络中的t c p u d p 协议进行改 造，使之适应无线环境完成传输层的功能。针对u d p 的改进和t c p 的相似。 移动a dh o e 的高层主要包括建立在移动a dh o e 之上的无线应用以及接入移 动通信核心网的各种技术。基于移动a dh o e 网络所承载的业务和其他各种类型的 网络一样，主要是传统的业务和人们寄予厚望盼无线宽带数据业务”。移动a dh o e 网络自身的特性使得网络在承载同类业务时，要考虑更多的问题，克服更多的困 难。 2 2 2 移动a dh o e 网络路由协议简介 路由器的功能在网络层实现，路由器可以将子网连接在一起，它依赖于网络 层将子网的流量进行路由。设置网络层的主要目的就是要为数据分组，以最佳的 路径通过通信子网到达目的节点提供服务，而网络用户不必关心网络的拓扑结构 和通信介质。本文在第一章中提到过移动a dh o c 网络没有专门的路由器，每个节 点有双重的身份，即路由器和主机。这使得路由协议成为移动a dh o c 网络中的难 点和热点问题。下面主要阐述移动a dh o e 网络中的路由协议。 1 路由协议的组成 路由包含两个最基本的动作：确定最佳路径和数据交换。 移动a dh o c 网络中基于q o s 多径路算法研究 ( 1 ) 路由选择 跳数( m e t r i c ) 是路由算法中用以确定到达目的节点最佳的计量标准，如路径长 度。为了帮助选择路径路由算法初始化并维护包含路径信息的路由表，路径信息 根据使用的路由算法的不同而不同。路由算法根据许多信息来填充路由表。目的 下一跳地址对告知路由器到达该目的的最佳方式是把分组发送给代表下一跳的路 由器。当路由器接收到一个分组，它就检查其目的地址，尝试将此地址与“下一 跳”相联系。 通常，路由表通过比较跳数( m e t r i c ) 确定最佳路径。路由器彼此通信，通过交 换路由信息维护其路由表，路由更新信息通常包含全部或部分路由表，通过分析 来自其他路由器的路由更新信息该路由器可以建立网络的拓扑细图。路由器问发 送的另一个信息例子是链接状态广播信息，他通知其他路由器发送者的链接状态， 连接信息用以建立完整的拓扑图，使路由器可以确定最佳路径。 ( 2 ) 数据交换 数据交换对于大多路由来说基本相同，即源节点决定向目的节点发送数据， 通过某些方法获取路由器的地址后，源节点发送指向该路由器的物理地址( m a c ) 的数据分组，其协议地址是指向目的节点的。路由器查看了数据分组的目的地址 后，确定是否知道如何转发该包，如果路由器不知道如何转发，通常将其丢弃。 如果知道如何转发，就把目的物理地址变成下一跳的物理地址并向之发送。下一 跳可能就是最终的目的节点，如果不是，通常为另一个路由器，他将执行同样的 步骤。当分组在网络中流动时，它的物理地址在改变，但其协议地址始终不变。 2 路由协议设计目标 路由算法可以根据多个特性加以区分。首先，算法设计者的特定目标影响了 该路由协议的操作；其次存在多种路由算法，每种算法对网络和路由器资源的影 响不同；最后，路由算法使用多种跳数( m e t r i c ) ，影响最佳路径的计算。 通常路由算法的设计目标包括优化、简单低耗、健壮稳定、快速收敛、灵活 性。优化指路由算法选择最佳路径的能力，根据跳数( m e t r i c ) 的值和权值来计算。 路南算法尽量设计的简单，即路由协议必须高效的提供其功能，尽量减少软件和 应用的开销。路由算法的健壮性要求网络出现不正常或不可预见的事件时仍能够 正常处理。路由算法收敛性必须快收敛，这是所有路由器对最佳路径达成的一致 性的过程。路由算法还应该灵活，即算法能准确的适应各种环境。 2 2 3 移动a dh o c 网络协议面临的问题 常规的路由协议主要有两种，一种是基于距离矢量的路由协议，一种是基于 链路状态的路由协议，这两种协议都是针对有限固定网络而设计的，他们的拓扑 第二章移动a dh o e 网络的基本结构及协议 9 结构固定且不会出现大的网络结构的变化。移动a dh o c 网络由于节点的任意移动 性导致拓扑结构的动态的随机的且较快的变化，这样常规路由在拓扑结构变化时 花费很大的代价重新路由，而且协议状态始终处于不收敛的状态，占用大量的网 络资源，致使信息无法实现传输。 另外移动a dh o c 不能采用常规的路由协议主要由于以下几种因素。首先，移 动a dh o c 网络中无线传输设备功率的差异以及无线信道中的大量干扰导致单向信 道的存在。其次，无线信道的广播特性使得常规路由的网络选路过程产生许多冗 余的链路。再次，常规路由的周期性广播路由更新会消耗大量的带宽，同时常规 路由的周期性的更新分组会消耗大量的节点能量。此外，常规路由需要的复杂的 计算使得c p u 始终处于高负载下，这也同样消耗的大量的能源，并对有限的节电 能源带来了的压力。因此需要适用于a dh o c 网络自身的路由协议。 近年来人们提出了许多路由协议的方案，但基本的原理都是基于以下主要几 点：网络的自组性、动态变化的拓扑结构、有限的无线传输带宽、无线移动终端 的局限性、单向信道的存在、分布式的控制网络、有限的网络安全、网络的生存 时间较短等。 2 3 移动a dh o c 网络协议 2 3 1 移动a dh o e 网络路由协议的分类 传统的路由协议已经无法适应移动a dh o c 网络的需要，因此必须选择或设计 适用于移动a dh o c 网络环境特点的路由协议。目前，已存在数十种以移动a dh o c 网络为网络环境的路由协议，其中较为基础和常见的有目的节点序列距离矢量协 议( d e s t i n a t i o ns e q u e n c e dd i s t a n c ev e c t o r , d s d v ) 、无线路由协议( w i r l e s sr o u t i n g p r o t o c o l ，w r p ) 、系统容量自适应路6 1 ( s y s t e ma n dt r a f f i cd e p e n d i n ga d a p t i v e r o u t i n ga l g o r i t h m ，s t a r a ) 、鱼眼状态路6 1 ( f i s h e y es t a t er o u t i n g ，f s r ) 、优化的链 路状态协议( o p t i m i z e dl i n ks t a t er o u t i n g ，o l s r ) 、信号状态自适应路由s s r ( s i g n a l s t a b i l i t y b a s e da d a p t i v er o u t i n gp r o t o c 0 1 ) 、层次路由( h i e r a r c h i c a ls t a t er o u t i n g h s r ) 、分群网关交换路6 1 ( c l u s t e rb a s e dg a t e w a ys w i c hr o u t i n g ，c g s r ) 、区域路由 ( z o n er o u t i n gp r o t o c o l ，z r p ) 、按需距离矢量路由协议( a dh o co n d e m a n dd i s t a n c e v e c t o rr o u t i n gp r o t o c o l ，a o d v ) 、源动态路由协议( d y n a m i cs o u r c er o u t i n g ，d s r ) 、 目标定位路由协议( l o c a t e da i d e dr o u t i n g ，e a r ) 、移动距离有效路由( d i s t a n c e r o u t i n ge f f e c ta l g o r i t h mf o rm o b i l i t y , d r e a m ) 、 基于散列方法的地理位置路由 协议( g r e e d yp e r i m e t e rs t a t e l e s sr o u t i n g ，g p s r ) 等。 对于已经提出的移动a dh o c 网络路由协议，根据不同的角度可以进行不同的 1 0 移动a dh o c 网络中基于q o s 多径路算法研究 分类。根据路由发现的策略，可以将其分为主动路由协议和按需路由协议；根据 网络的逻辑结构可以分为平面结构和分级结构两种。如图2 3 和表2 2 所示。 d s ra o d vs s r d s d v0 l s rf r s 图2 3 路由协议分类 表2 2 移动a dh o c 网络中的路由协议的比较 分类 路由 优点缺点 典型协议 角度类型 当节点需要发送数据分花费开销较大，应尽可能使路由更d s d v 从主 组时，只要到目的节点的新紧随拓扑结构的变化，但动态变 o l s r f s r 路动 路由存在，所需的延时很化的拓扑结构可能使路由更新信g s r h s r 由路 发由 小。 息变的过时，路由协议始终处于不 w r p z h i s 现 策 收敛状态。s 1 a r a 略 的 无需周期性路由信息广发送数据时，若没有到目的节点的 a o d vs s r 角 按 度 需 路 播，节省了一定的网络资 路由，需进行路由发现，增加数据 d s r t o r a 由 源。分组的迟延。c b r p a b r 无特殊节点，网络中业务可扩展性较差，研制了网络的规 a o d v 皿 面 流平均分散，路由协议鲁模。d s rt o r a 从路 棒性较好，无需进行节点d s d v 网由 络 移动性管理。w r p l a r 逻 辑 网络有多个分群组成，可群首节点的可靠性和稳定性对网c g s r 视 分 图 群 的 路 扩展性较好，适合大规模络性能的影响较大，为支持节点在c e d a r 角 由 的自组网环境。不同分群之间漫游所进行的移动z r pc b i t p 度 管理将产生一定的协议开销。 第二章移动a dh o c 网络的基本结构及协议 1 1 表2 2 中的路由协议都是单路由协议，针对移动a dh o c 网络拓扑变化频繁的 环境和传递实时业务的需求，又出现了多径路由协议。如a o d v - b r 、s m r 、 a o m d v 等。另外，从是否使用g p s 系统作为路由辅助条件的角度出发，还可以 分为地理定位辅助路由和无地理定位辅助路由。 2 3 2 主动路由协议 主动路由协议出现在移动a dh o e 网络路由协议的研究初期，其主要思路是修 改有线网络的路由协议以适应在移动a dh o c 网络环境中运行，这些路由协议大多 属于表驱动路由协议。这种协议的基本特点是无论有无通信需求，网络中所有节 点总是主动发现路由，试图维护到所有己知目的节点的路由表，为此节点之间定 期或者在网络拓扑改变时交换路由信息。常用的表驱动路由协议有d s d v 、 o l s r 16 1 、w r p 1 7 1 、s t a r a 1 8 】等。 1 d s d v 协议【5 】 d s d v 协议是在距离矢量算法基础上进行改进设计的，被认为是最早的自组 网路由协议，它的特点是采用了序列号机制以区分路由的有效和过期，防止可能 产生的路由环路。其路由表信息交换采用时间驱动和事件驱动两种模式，每个节 点周期性地将本地路由表传送给相邻节点；或者当节点的路由表发生变化时，也 会将自己的路由信息传给相邻节点。它的路由表更新有两种方式一种是全部更新， 即拓扑更新( f u l ld u m p ) 消息中包含整个路由表另一种是增量更新( i n c r e m e n t a l u p d a t e ) ，更新消息中仅包含变化的路由部分。d s d v 的每条路由具有序列号，它 只使用序列号最大的路由，而当两条路由具有相同的序列号时，将以其它原则( 如 跳数最短) 选择最优路由。但是，d s d v 不支持单向信道。 d s d v 路由协议能迅速为节点建立路由并发送数据，在任何情况下都能避免 产生路由环路。虽然在网络拓扑变化频繁的情况下，d s d v 协议的收敛性能并不 好，但在一般情况下，收敛还是相当快的。但是，无论网络流量如何以及节点是 否需要发送数据，d s d v 都要求节点定期地广播更新信息。当加入网络的节点越 来越多，路由表容量、开销和带宽也相应增加，这是d s d v 的主要缺点。此外， d s d v 要求每个节点保存到网络中所有节点的路由，这样多余的路由条目就会造 成资源浪费。 2 o l s r 协议 1 6 1 o l s r 协议是种链路状态路由协议。在运行o l s r 协议的网络中，节点通过 周期性的控制信息交换和分布式计算，更新和建立网络拓扑图。为了减少相同区 域内的重传冗余和限制网络中的路由信息的广播，o l s r 协议引入了多点中继集 ( m r p ：m u i t i p o i n tr e l a y s ) 的思想：每个节点在它的一跳邻居节点集中选择一个子集 1 2 移动a dh o c 网络中基于q o s 多径路算法研究 作为m r p 集，不在m r p 集中的节点仅接收和处理广播消息不转发他们；节点的 m r p 集的选择策略必须使得节点通过它的m r p 集可以覆盖所有的两跳邻节点， 任何m r p 集选择策略只要满足这一点均可以应用。这样带来的好处有二：( 1 ) 只有 m r p 中的节点才产生链路状态信息，减轻了广播风暴带来的路由开销；( 2 ) 参与链 路状态交换的节点规模减小，而且网络只需要关心m r p 节点间的链路状态，因此 更新报文也相应减小了。 2 3 3 按需路由协议 按需路由协议又称为反应式路由协议。顾名思义，所谓“按需”指节点平时 没有通信需求的时候不维护网络的全局拓扑信息和自身到网络中所有节点的路由 信息，而只在有通信需求，即有报文需要转发的时候才“按需”地发起路由发现 过程以寻找到目的节点的可用路由，并且，这些按需的路由信息在长时间没有通 信时，将过期而被自动删除。运行按需路由协议的节点所感知的网络拓扑结构和 路由表内容是按需建立的，并且可能仅仅是整个拓扑结构信息的一部分按需路由 的代表协议有d s r 、a o d v 等。 1 d s r 协议【6 】 d s r 协议是一个典型的按需路由协议，也是最早采用按需路由思想的协议。 d s r 是基于源路由概念的按需自适应路由协议。移动节点需要保留存储节点所知 的源路由的路由缓冲器。当新的路由被发现时，缓冲器内的条目随之更新。它最 大的特点是使用了源路由机制，每一个分组的头部都包含整个链路的信息。这种 t d l n 最初被i e e e 8 0 2 5 协议采用在有网桥互联的多个令牌环网络中寻找路由。d s r 借鉴该机制，并结合按需路由的思想。d s r 协议使用源路由，采用c a c h e ( 缓冲 器) 存放路由信息，且中间节点不必存储转发分组所需要的路由信息，网络开销 较少，但存在陈旧路由。 d s r 包括两个过程：路由发现和路由维护 路由发现，当一个节点欲发送数据到目的节点的时候，它首先查询路由缓存 器，看是否有到目的节点的路由。若果有，则采用此路由发送数据。如果没有， 源节点就开始启动路由发现程序。路由发现过程使用泛洪路由机制。 路由维护过程，d s r 支持主动应答和被动应答两种链路状态检测方法，路由 维护通过路由错误分组和确认分组来实现。一旦节点在发送数据的时候发现需要 使用的邻节点断开，它发送路由出错分组给这些断开路由的源节点，源节点收到 分组后，将失效路由从路由表中删除。沿途转发出错路由的节点也从自己的路由 表中删除包含该断开链路的所有路由。而确认分组可以用来验证路由分组的正确 运行。 第二章移动a dh o c 网络的基本结构及协议 1 3 2 a o d v 协议1 7 1 a o d v 协议本质上是d s d v 和d s r 的结合，它是在d s d v 的基础上，结合 d s r 的按需路由机制改进而提出的，不同之处在于它采用了逐跳转发的方式而不 是d s r 的源路由方式以提高带宽利用率。a o d v 协议的假设无线链路是双向的 本文将a o d v 协议规范概括为路由发现和路由维护两个主要机制。 ( 1 ) a o d v 的路由发现机制 a o d v 使用广播路由发现机制，它依赖中间节点