（通信与信息系统专业论文）ad+hoc网线中基于路径稳定性的组路由算法研究.pdf

重庆邮电大学硕士论文摘要 摘要 随着现代无线通信技术和因特网的发展与进步，逐渐出现了移动视频会议、应 急通信、g p s 定位导航等组播业务，这些组播业务都是基于组播协议的，由于是实 时业务，所以人们对其传输的稳定质量要求很高。但是在移动a dh o c 网络中，节 点经常不可预测地移动，导致网络拓扑频繁、快速、任意变化，而且无线链路相对 于有线信道带宽较窄，每个节点传输距离以及能量有限，导致了传输路径中断的概 率增大，所有这些都使得移动a dh o e 网络的组播路由技术更加复杂，而且现有的 组播路由协议没有考虑构成路由的各条链路状态，很多采用的都是最短跳数的路径 度量机制来选择路由，这样不仅增加了使用潜在不可靠路由的可能，而且有可能会 导致频繁的路由失效，这对于这些实时业务来说是不能接受的。 因此提高a dh o c 网路由动态拓扑适应性，减少动态拓扑造成的路径中断次数， 对a dh o e 网性能提高、规模的扩展具有非常重要的意义。本文首先对a dh o c 网络 中经典的组播路由协议进行了分类比较，然后介绍了移动自组网中基于稳定性的路 由算法的研究现状，在此基础上提出了一种基于路径稳定性的路由选择机制r s ： 该机制研究了移动自组网网中影响节点稳定性状态的因素，从而系统地将节点的运 动状态划分为自身节点的稳定尺度和邻居之间的相互稳定尺度。这两种度量分别对 节点自身的运动状态以及节点周边的运动情况加以评价度量，充分地反映了不同链 路的稳定性程度，并结合数学上的加权思想，节点能量等因素得到链路的稳定度量， 最后采用将链路稳定尺度累积的计算方法得到路径稳定度度量，根据此度量值选取 最稳定的路径进行数据转发。最后本文将此机制应用到m a o d v 路由算法中，得 到了一种改进的算法r s m a o d v ，并且在文章中进行了相应的数学理论分析和详 细的算法流程设计。改进的路由算法选择的路由不仅稳定性较好，路由跳数小，而 且能有效的避免网络拥塞和信道竞争，并且该算法只需要周期性获得邻居节点的位 置信息，与以往的路径稳定性选择算法相比，具有计算简单，更符合实际应用的特 点。 本文给出了该算法的具体实现，并设计了两种仿真模型，分别通过增加节点的 移动速度和增加组播组接收节点的数量来对r s m a o d v 和m a o d v 路由算法进行 仿真对比，给出了两种路由算法在端到端延迟、分组投递率、路由控制开销等方面 仿真图。仿真结果证明了改进方案的有效性。 关键词： a dh o e ，m a o d v ，路径稳定性，组播 重庆邮电大学硕士论文 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，t h er a p i dd e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o n sa n di n t e m e th a v e o 删v a r i o u ss e r v i c e so fm u l t i c a s tw h i c hb a s e do nt h em u l t i c a s tp r o t o c o l ，s u c h 嬲 w i r e l e s sc o n f e r e n c e sf o r l a l g 争s c a l em e 舐n g 芦，e m e r g e n c yc o m m u n i c a t i o n , g p s n a v i g a t i o n a n dp o s i t i o n i n g t h e s er e a l - t i m e a p p l i c a t i o n s n e e dh i g l l s t a b i l i t yo f c o m m u n i c a t i o nq u a l i t y h o w e v e r , a nu n p r e d i c t a b l em o v e m e n to fn o d e sw o u l dc a u s et h e t o p o l o g yo fn e t w o r k sf r e q u e n t l y , r a p i d l ya n dr a n d o m l yc h a n g e b e c a u s et h ew i r e l e s sl i n k i sn a l t o w e rt h a nw i r e dc h a n n e l ，t h et r a n s m i s s i o nd i s t a n c ea n dt h ee n e r g yi sr e s t r i c t e d a m o n ge a c hn o d e t h e s ei n c r e a s et h ep r o b a b i l i t yo ft h ed i s c o n n e c t i o nt r a n s m i s s i o np a t h a n dc a u s et h em o b i l ea dh o en e tm u l t i c a s tt e c h n i q u eb e c o m em o r ec o m p l i c a t e d f u r t h e r m o r e , n o wa v m l a b l em u l t i c a s tr o u t i n gp r o t o c o l sd on o tc o n s i d e ra b o u tt h ec o n d i t i o no f e a c hl i n ki nr o u t i n ga n dc h o o s et h es h o r t e s th o pc o u n t sm e c h a n i s m t h e s ei n c r e a s et h e p r o b a b i l i t yo fu s i n gt h eu n r e l i a b l er o u t i n g , a n dm a yc a u s et h ef r e q u e n ti n v a l i d a t i o n t h e s ed i s a d v a n t a g e sa l eu n a c c e p t e db yt h er e a l t i m ea p p l i c a t i o n s t h e r e f o r e , i ti si m p o r t a n tt oi m p r o v et h ed y n a m i ct o p o l o g ya p p l i c a b i l i t yo ft h ea d h o en e t w o r k sa n dt od e c r e a s et h ed i s c o n n e c t i o nf r e q u e n c yo ft h ep a t h s ot h a tc o u l d i m p r o v et h ep e r f o r m a n c ea n de x p e n dt h es c a l eo ft h ea dh o e n e t w o r k s i nt h i sp a p e r , w e c o m p a l e dt h ec l a s s i c a lm u l t i c a s tr o u t i n gp r o t o c o l si na dh o cn e t w o r k sa n di n t r o d u c e d t h ec u r r e n tr e s e a r c hs i t u a t i o no ft h e r o u t i n ga l g o r i t h mb a s e do nt h es t a b i l i t y f u r t h e r m o r e , w ep r o p o s e dam u t i n gs e l e c t i o nm e c h a n i s mw h i c hb a s e do nt h ep a t hs t a b i l i t y t h i s m e c h a n i s ms t u d i e dt h ed e m e n t si n f l u e n c i n gt h en o d e ss t a b i l i t yi nm o b i l ea dh o c n e t w o r k s i tc l a s s i f i e st h ew o r k i n gc o n d i t i o no ft h en o d e si n t os e l f - n o d ea n dn e i g h b o ri n s t a b l es c a l e t h e s et w o m e a s u r e m e n t sc a l c u l a t e dt h ed y n a m i co f t h en o d es e l fa n da r o u n d i t t h i sr e f l e c t e dt h ed i f f e r e n ts t a b i l i t yo ft h el i n kp a t h w h e ni tc o m b i n e dt h ew e i g h t i n g a n a l y s i so nm a t h e m a t i c sa n dn o d ee n e r g yi n 幻m e a s u r i n gt h es t a b i l i t yo f t h el i n kp a t h , w e f i n a l l yc h o s eo n e m e t h o db yc a l c u l a t i n gt h ec o m m u n i c a t i o no ft h el i n kp a t hs t a b l es c a l e i tw o u l dt r a n s m i tt h ed a t at h r o u g hs e l e c t i n gt h em o s ts t a b l em 或姗r n l i sm e c h a n i s mi s a p p l i e di n t om a o d vr o u t i n ga l g o r i t h m t h i si m p r o v i n ga l g o r i t h mi sc a l l e d a s r s m a o d v w eh a v ea p p r o p r i a t ea n a l y s e so nt h et h e o r yo f m a t ha n dd e t a i l e dd e s i g n i n g o na l g o r i t h mp r o c e d u r e t h ei m p r o v i n gr o u t i n ga l g o r i t h mr s m a o d vc o u l da v o i dt h e c o n g e s t i o na n dc o m p e t i t i o no nn e t w o r k s ，b e c a u s ei ti sm o r es t a b l ea n dl e s sh o p t h i s a l g o r i t h mo n l yn e e d st h el o c a t i o ni n f o r m a t i o na b o u tt h en e i g h b o rn o d e si np e r i o d t h e r e f o r ei ti se a s i e rt h a nt h ep e r v i o u sc o m p u t a t i o n s a b o v ea d v a n t a g e sa l em u e h 重庆邮电大学硕士论文 a b s t r a c t s u i t a b l ef o rt h ea p p l i c a t i o n t 1 1 i sa r t i c l eh a sg i v e nt h i sa l g o r i t h mc o n c r e t er e a l i z a t i o na n dh a sd e s i g n e dt w ok i n d s o fs i m u l a t i o nm o d e l s i tc a r r i e so nt h es i m u l a t i o nc o n t r a s to fr s m a o d va n dt h e m a o d v r o u t i n ga l g o r i t h mt h r o u g hi n c r e a s i n gt h en o d em o v i n gs p e e da n di n c r e a s i n gt h e m u l t i c a s tg r o u pr e c 溺v i n gn o d eq u a n t i t y i th a sg i v e nt w ok i n d so fr o u t i n ga l g o r i t h m s s i m u l a t i o nc h a r t s i ne n d - t o e n dd e l a y , g r o u p i n gd e l i v e r yr a t e , a n dn o r m a l i z e dr o u t e o v e r l o a da n ds oo n t h es i m u l a t i o nr e s u l th a sp r o v e nt h ei m p r o v e m e n to fa l g o r i t h m v a l i d i t y k e y w o r d s ：a dh o c , m a o d v , 1 i n ks t a b i l i t y , m u l t i c a s t i i i 重庆邮电大学硕士论文第一章绪论 1 1 研究背景 第一章绪论 近年来，随着计算机网络技术的快速发展以及网络应用的不断拓展，各种无线 网络技术得到越来越广泛的普及和应用。作为无线网络的重要研究领域之一，a dh o c 网络也得到越来越多的关注与研究。 移动自组织网络，又称a dh o c 网络n 儿帅儿铂，是由一组无限移动节点组成，是 一种不需要依靠现有固定通信网络基础设施、能够迅速展开使用的网络提示。所需 人工干预最少，是没有任何中心实体、自组织、自愈的网络；各个网络节点相互协 作，通过无线链路进行通信、交换信息，实现信息和服务共享，而且网络节点能够 动态地、随意地、频繁地进入和离开网络。移动a dh o e 网络中的每个网络节点可 以快速的移动，必须既作为路由器又作为主机，能够通过数据分组的发送和接收而 进行无线通信。而且在a dh o c 网络中，节点间的路由通常由多个网段( 多跳) 组 成，由于节点的无线传输范围有限，两个无法直接通信的终端节点往往要通过多个 中间节点的转发来实现通信。如图1 所示为典型的a dh o c 网络拓扑。 屹 衫 厂、 u b 图1 1a dh o e 网络拓扑图 a dh o c 网络的研究自2 0 世纪7 0 年代以来，到现在已有三十多年了，但其仍然 是当前研究的热点，这是因为与其他通信网相比，移动自组网有许多优良的特性， 其特性可以总结如下： 网络的自组织性 相对其他通信网络而言，a dh o c 网最大的区别就是可以在任何时刻和任何地 点，不需要任意固定基础网络硬件设施支持的情况下，快速构建起一个移动通信网 络。它的建立不过于依赖已经有的通信网络设施，具有比较强的独立特性。 动态变化的网络拓扑结构 在移动a dh o c 网中，节点可以以任意速度和任意方式在网络中移动，同时， 再加上节点自身能量、发送功率变化、无线信道干扰等综合因素的影响，这必然导 致网络拓扑结构随即、迅速、不可预测的发生变化。 分布式控制 由于移动a dh o c 网络节点不能够依靠固定基础设计或者中心管理，所以移动 重庆邮电大学硕士论文第一章绪论 a dh o c 网络节点必然是分布式的。所以在a dh o c 网络中节点的地位都是相互平等 的，因此具有较强的鲁棒性和抗毁性 传输信道基于无线信道，且带宽有限 a dh o c 网采用无线传输技术作为底层通信手段，由于无线信道本身的物理特 性，它所能提供的网络带宽相对有线信道要低得多。同时考虑到竞争共享无线信道 产生的碰撞、信号衰减、噪音干扰、信道间干扰等多种因素，节点可用的实际带宽 远远小于理论上的最大带宽值。 网络安全性较差 a dh o c 网络是一种特殊的无线移动网络，由于采用无线信道，网络的控制方 式多为分布式控制，因此更加容易受到被动窃听、主动入侵、拒绝服务、剥夺“睡 眠 ( 终端无法进入睡眠模式) 、伪造等各种网络攻击。 近年来，组播路由问题是a dh o c 网络研究中一个热点研究问题。在传统的 i n t e m e t 中，组播协议包括组管理协议( i g m p ) 和组播路由协议( d 心、m o s p f 、 p i m 等) 。i g m p 负责本地路由器到直接与它相连的子网的组播分组的发送，并不关 心路由器间或跨越中间网络的组播分组转发。组播路由协议则完成路由器间和跨越 网络的组播分组的转发任务。 但是在移动自组网中，由于节点具有可移动性，网络拓扑频繁改变，且节点具 有有限的带宽和能量，为有线网络设计的组播路由协议不再适用。a dh o c 网络中的 组播是指将数据分组发送给由一个目的地址指定的一组主机。组播用于面向节点组 的计算。越来越多的应用必须是点对多点传输，组播服务对于团队密切协作应用非 常重要，要求共享文本和图片，召开音频和视频会议。网络中采用组播传输技术有 许多好处：对于需要将同一个分组发送给多个接收点的应用，采用组播传输技术替 代采用单目标传输针对每个接受节点单独发送，链路带宽消耗最小；发送节点、转 发节点的处理最少，分组交付时延最短，因而能降低通信开销。 如在图1 1 中，我们给出了一个单播的例子；在图1 2 中，我们给出了一个组 播的例子，这两张图表明就算网络中只有三个接收节点，使用组播方式路由器之间 的带宽也能节约三分之二。 2 重庆邮电大学硕士论文第一章绪论 图1 2 单播图1 3 组播 但是在研究组播问题的同时，我们必须考虑移动自组网的动态性。动态拓扑是 a dh o c 网的主要特征，拓扑的动态变化导致a dh o e 网路由中断频繁，使得网络性 能下降、网络规模扩展受限【5 】。已经建立的数据传输路径经常因为网络拓扑的频繁 变换而中断，频繁的路由修复，消耗了a dh o c 网络有限的网络资源。上游节点丢 弃路由修复超时的数据分组，降低了数据分组投递率路由修复时延加大了整个端 到端分组传输时延。路径中断概率随转发跳数增加而变大，引起网络性能进一步恶 化，影响了网络规模的扩展。近几年来，随着无线通信和移动终端技术的发展，包 含大量移动节点的a dh o c 网络的商业应用需求已经成为可能。因此，尽可能地减 少节点移动造成的路径中断次数，提高路径的稳定性，对网络性能提高，尤其是大 规模a dh o c 网络扩展具有非常重要的意义。 1 2 研究现状 近年来，随着多媒体应用的普及和a dh o e 网络在商业应用中的进展，人们对在 a dh o e 上传送多媒体业务有了更多需求。因此在在移动a dh o e 网络提供高质量，稳 定的q o s 路由协议和算法越来越迫切和重要。然而在a dh o e 网络中路由研究将面临 许多问题和挑战：比如无线信道的复杂性和随机性、终端节点的移动性、共享的无 线信道之间的干扰等，这就要求在物理层、m a c 层、路由层、跨层设计等各方面 设计和研究新的路由机制保障机制，从而为m a n e t 中的端到端多媒体传输提供相应 的一定级别的服务质量保证嘲。其中，有关路由层的路径稳定性研究也逐渐受到关 注，相关研究也逐渐深入广泛。 但由于移动自组网自身无中心节点的特点，而且节点之间的通信经常需要多跳 路由才能实现，再加上a dh o e 中节点移动性较高，导致了网络拓扑的频繁变换， 从而引起节点之间路由信息失效。针对这样的情况，基于稳定性的路由算法吸引了 3 重庆邮电大学硕士论文 第一章绪论 广泛关注和研究，旨在找出源节点到目地节点之间具有较高稳定度的路径。目前已 经提出的路径度量算法大致分为以下几种：基于路径跳数的路径度量，基于信号强 度的路径度量，基于移动预测模型的路径度量，基于剩余生命时间的路径度量。 基于路径跳数的路径度量评价路径稳定与否的依据是跳数的大小，认为跳数最 小的路由即为最优路由，现在常用的a dh o c 协议，比如单播协议a o d v ，d s r 协议m a o d v 叫，o d m r p n 们等都是采取的这种稳定判据。但是基于路径跳数的路径 度量只适合在节点移动速度较低和业务数据传输量较小的情况，因为在真实场景 中，最短路径并不一定为最优路径，所以在考虑路由选择的时候，应该将此度量结 合其他度量使用。 基于信号强度的路径度量是根据节点接收到的信号强度判断路径稳定性。s s a 算法n 妇( s i g n a ls t a b i l i t y - b a s o da d a p t i v er o u t i n g ) 是最早的基于信号强度的自适应稳定 路由协议。该协议各个节点根据与邻居节点的信号强度，将其通信信道分为“强信 道 和“弱信道 。其中信号强度通过通过接收邻居节点链路层发出的周期性信标 获得。在文献n 2 1 中，g e u n h w il i m 等人提出了一种s s a 改进算法，该算法是一种 基于信号强度的链路稳定性估算方法。文献n 3 1 提出了一种随即无线电传播模型，利 用该模型可以预测楚相邻节点的接收信号强度。l b r n 郇提出了一种无线传播模型， 该模型可以将信号强度转化为链路间距离，并利用以前距离的抽样值预测楚链路寿 命。在这类算法设计中，均需要交叉层功能的支持，因此在实际环境中，有时难以 从底层协议获取接收信号强度信息。 基于移动预测模型的路径度量即通过建立移动预测模型根据以往节点的位 置，移动速度和移动方向等相关信息对将来节点的运动状态进行预测，从而来估算 出整条路径的稳定度。基于格网的组播路由协议o d m r p 就依赖两个节点的当前移 动速度，方位，然后利用位置信息的链路连续可用时间d f 的预测公式来预测链路的 过期时间。该公式描述如下： d：-(ab+cd)+、(a2+c2)r2-(ad-be)2 式( 1 1 )，j = - ，- - - - - - - - - - - - - - - - 一1 、， 一 a 2 + 6 2 a = b c 0 8 幺一，c o s 9 ，b = 而一工，c = 一s i n o , 一v j s i n o j ，d = 乃一乃 其中( 毛， ) 和( x ，y ，) 分别为节点f 和j 和位置，为信号传输距离，速度为k 和y ， 相对移动方向为谚和p ；。 a b h y a n k a r 等人口5 3 提出了评估运动算法和概率预测机制模型，节点利用该模型 分布式的计算出各自的运动方向和大小，从而来预测该条路径的稳定度大小。文献 n 旬根据节点位置的不确定性，提出了一种以熵的思想用于评估一个网络或者局部的 不确定性，从而得到判断路径稳定度量的模型。该文的作者提出了以相邻两个节点 的相对速度的变化程度来表示网络的不确定性程度，但是该文仅仅以节点的相对速 4 重庆邮电大学硕士论文第一章绪论 度变化程度来评价网络局部拓扑的变化程度是不够准确的，而且该算法对于熵的计 算过程过于复杂，这样会带来极大的开销，对节点的负载要求较高。文献n 小埔埘盈1 3 都属于利用节点位置移动预测路径稳定性的方法。 基于剩余生命时间的路径度量是根据某种数学模型或者方法来计算出链路的 剩余生命时间来预测路径的稳定度程度。例如，y u - c h o et s c n g 等人提出了一种随 机游走、离散时间模型( r a n d o m - w a l k 、d i s c r 既e - t i m em o d e l ) ，并在此的基础上得到 出一个指定链路寿命的概率分布嘲。然而，该种方法由于需要大量的前期节点数据 才能统计分析得到基于链路寿命的概率分布，实现的过程相当复杂，所以不适合用 于实际环境中。文献一3 的作者提出了利用直方图的方法来计算链路的剩余生命， 该方法由于实现过程较简单，其计算公式如下： 兄= ( 掌d e ) 一g 式( 1 2 ) d gd g 其中为某一链路其生命时间d 秒的次数，g 为该链路当前的年龄。因此被多 篇文献所采用删。目前基于剩余生命时间的路径度量的链路选择算法研究比较多， 但该类算法不适合在节点快速移动的环境，在拓扑变化比较频繁的时候，算法性能 会大为降低。 随着i n t e r n a 的发展，出现了移动视频会议、应急通信、g p s 定位导航等组播 业务，这些组播业务都是基于组播协议的，由于是实时业务，所以人们对其传输的稳 定质量要求很高。但是在移动a dh o e 网络中，节点经常不可预测地移动，导致网 络拓扑频繁、快速、任意变化，无线链路相对于有线信道带宽较窄；每个节点传输 距离有限；由于信道误码、传输碰撞、多径衰落、多址干扰等原因，并不是所有的 消息都能够传输到达预定接受节点，为了提供跨越整个网络的通信，从源节点到目 的节点的路由可能需要经过若干个中间相邻节点。所有这些都使得移动a dh o c 网 络的组播路由技术更加复杂。而且现有的组播路由协议没有考虑构成路由的各条链 路状态，很多采用的都是最短跳数的路径度量机制来选择路由，这样不仅增加了使 用潜在不可靠路由的可能，而且有可能会导致频繁的路由失效。同时，协议只有在 确定原有路由失效后才进行路由重建，这样大大增加了分组发送的延时，对于这些 实时业务来说是不能接受的。所以研究移动自组网中基于稳定性组播路由协议有一 定的实用性，本文的初步想法就是将稳定的路由选择机制应用到组播路由算法中 去，构建稳定的路由以及组播树。 5 重庆邮电大学硕士论文第一章绪论 1 3 研究内容 本论文的目标是提出以路径稳定性作为度量的路由选择机制，使得选择的路由 具有稳定性好，且路由跳数少的特点，同时在选择转发节点的时候，考虑了信道竞 争和数据拥塞的影响。这样就可以减少路径中断的可能，提高网络性能，改进网络 q o s 能力。针对以上目标，本论文的研究内容可以分为以下几个方面： 本文对现阶段a dh o e 网络中组播路由协议进行了研究和总结，为进一步优 化和设计移动自组网中的组播路由算法提供一定的依据。 深入的研究了移动自组网中基于稳定性的路由选择算法，提出了一种针对 a dh o c 网络中基于路径稳定性的路由选择机制r s 。该机制研究了移动自组网网中 影响节点稳定性状态的因素，从而系统地将节点的运行状态划分为自身节点的稳定 尺度和邻居之间的相互稳定尺度。这两种度量分别对节点自身的运动状态以及节点 周边的运行情况加以评价度量，充分地反映了了不同链路的稳定性程度，并结合数 学上的加权思想，节点能量等因素得到链路的稳定度量。最后，路径稳定度度量采 用把链路稳定尺度累积的计算方法，这使得算法倾向于选择转发跳数较少的路径形 成路由，从而这也从另一个方面提高了路由的稳定性( 路径跳数变长，路由的中断 概率也随之变大) 。 将该机制应用到组播路由协议m a o d v 中，提出了改进的路由算法 r s m l 气o d v 。 最后通过大量的实验和仿真模拟，将改进后的组播路由算法r s m a o d v 。 与m a o d v 路由算法进行全面仿真比较和性能分析，最后验证得出该机制可行性。 1 4 论文的组织结构 本文共分六章，各章的内容安排如下： 第一章绪论先对a dh o c 网络进行了简单的介绍，然后阐述了在移动自组织网 络中组播路由协议的研究背景和意义，阐明了a dh o e 网络中基于稳定性的路由协议 的研究现状和实用价值。 第二章介绍和比较了a dh o c 网络中现有组播路由协议。 第三章提出了一种在a dh o c 网络中基于路径稳定性的路由选择机制，重点描 述了单一节点稳定尺度，邻居相互稳定尺度，链路稳定度量，路径稳定度量的构建 方法。 第四章将上述的路由选择机制( r s ) 应用到组播路由算法m a o d v 中。 第五章介绍了仿真环境，并将改进的路由算法r s m a o d v 与m a o d v 路由算 6 重庆邮电大学硕士论文 第一章绪论 法在同样的仿真环境中进行仿真比较。 第六章总结了本文所做工作，并探讨了进一步的研究方向。 7 重庆邮电大学硕士论文 第二章a dh o c 网络组播路由协议的分析 第二章a dh o e 网络组播路由协议的分析 a dh o e 网络中的组播是指将数据分组发送给由一个目的地址指定的组主 机。组播用于面向节点组的计算。越来越多的应用必须是点对多点传输，组播服 务对于团队密切协作应用非常重要，要求共享文本和图片，召开音频和视频会议。 网络中采用组播传输技术有许多好处：对于需要将同一个分组发送给多个接收点 的应用，采用组播传输技术替代采用单目标传输针对每个接受节点单独发送，链 路带宽消耗最小；发送节点、转发节点的处理最少，分组交付时延最短，因而能 降低通信开销。 即使在有线网络中，维护组播组成员信息和构建最佳组播树也是一个复杂的 任务，在移动a dh o e 网络中，节点经常不可预测地移动，导致网络拓扑频繁、 快速、任意变化。无线链路相对于有线信道带宽较窄；每个节点传输距离有限； 由于信道误码、传输碰撞、多径衰落、多址干扰等原因，并不是所有的消息都能 够传输到达预定接受节点，为了提供跨越整个网络的通信，从源节点到目的节点 的路由可能需要经过若干个中间相邻节点。所有这些都使得移动a dh o e 网络的 组播路由技术更加复杂。而且现有的组播路由协议没有考虑构成路由的各条链路 状态，这样不仅增加了使用潜在不可靠路由的可能，而且有可能会导致频繁的路 由失效。同时，协议只有在确定原有路由失效后才进行路由重建，这样大大增加 了分组发送的延时，对于有些实时业务。如实时视频、音频、应急通信等来说是 不能接受的。 相似与单播路由协议，a dh o e 组播路由协议可以根据不同的策略有两种分 类方法：一种是按路由建立和维护时机分为先验式路由和按需路由，一种根据网 络拓扑结构的不同，可以分为以下三种类型：基于树的组播路由协议，基于网的 组播路由协议，混合组播路由协议叼儿矧。本文将根据网络拓扑结构分类来对组播 路由协议进行介绍。 2 1 基于树的组播路由协议 基于树的组播路由协议中，组播组成员节点的网络拓扑结构是一棵连接所有 组播组成员的最小代价生成树，而且该结构需要建立、维护树型的拓扑结构，用 于组播数据的转发。移动自组网中可分为基于共享树( s h a r et r e e ) 的协议和基于 源树( s o u r c et r e e ) 的协议。基于组播组成员共享一棵组播树，这种协议扩展性好， 存储开销小，但是源节点的改变反应慢，路径可能是非最优的。而基于源树的组 播路由协议，每个源节点都有一棵以自己为根节点的组播树，该树连接组播组中 重庆邮电大学硕士论文第二章a dh o c 网络组播路由协议的分析 所有的成员节点。这种结构的优点是源节点到其它组播组成员节点的路径均是最 短路径，通信量分散，缺点是不易扩展，开销太大。 基于树的组播路由协议其主要有传输效率高、路由决策简单等优点，但受自 组网的拓扑结构动态变化的影响，鲁棒性不好，组播树中的任何一段链路有故障 或不可用都将导致组播树的重构，维护树结构的开销比较大，协议的健壮性不佳 【2 7 】【嚣】 o 现阶段基于树的组播路由典型协议有以下几种：利用递增序号的a dh o c 组 播路由协议舢v l r i s 、按需距离矢量的a dh o c 组播路由协议m a o d v 等 2 1 1m a o d v m a o d v ( m u l t i c a s ta 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 0 1 ) m a o d v 呻3 是一种基于共享树的按需组播路由协议，同样采取了a o d v 协议的 r r e q r r e p 消息，但是引入了m a c t ( m u l t i c a s ta c t i v a t i o n ) 消息机制，用于路由确 认，该协议是a o d v 协议的组播扩展。当节点加入组播组的时候，建立一棵组播 树，组播树由组播成员和连接组播成员的节点组成，组播组成员可以在任何时候 加入组播组，也可以在任何时候脱离所在的组播组，一个组播组有一个组长节点， 负责维护本组的组播组序列号。而且组播组成员必须同意作为组播组树上的路由 器。组播树建立后，使用g p r h ( g r o u ph e l l o ) 消息对组播树进行维护。m a o d v 协议包括了以下几个关键过程：组播树构建、组播树的维护、组播树的合并等。 当一个节点a 在需要加入一个组播组时，或者有数据需要发送给目前还没 有到达路由的组播组发送一条路由请求( r o u t er e q u e s t ，r r e q ) 消息。r r e q 消 息的各个组成域设置如下：将目地节点的地址域设为所需组播组g 的口地址； 目的节点的序列号域设为所知道的组播组g 的最新序列号；假如节点a 需要加 入组播组g 则将鼬也q 消息的jn a g 标志置“l ”，否则将jf l a g 标记清“0 。 将这样的r r e q 消息称为加入r r e q j 消息。根据源节点a 的可以用信息可以 去定是广播r r e q 消息还是单播传输r r e q 消息，图2 1 为m a o d v 非组播树 成员节点申请加入组播树请求的过程。 9 重庆邮电大学硕士论文第二章a dh o e 网络组播路由协议的分析 o o 事树成员 来来组播树成员 姐措树成员 组措村成员 图2 1m a o d v 成员加入请求 如果源节点a 有另一个节点b ( 组播组g 的组长节点) 的记录，节点b 先 前请求了一条到达组播组g 的路由，并且假定源节点a 有一条有效路由到达节 点b ，那么r r e q 消息扩展包含了一个扩展域；扩展域包含了组播组g 组长节 点b 的d 地址；然后源节点按照单目标的方式，沿着已知路由将r r e q 消息传 输给组播组g 的组长节点b 。否则如果源节点a 不知道组播组g 的组长节点。 或者源节点a 虽然知道组播组g 的组长节点却没有到达组长节点的路由，那么 源节点a 广播r r e q 消息。 只有组播组树上的某个成员节点( 即组播组g 上的某个路由器) 才可以响应 r r e q j 消息。如果所收r r e q 消息不是r r e q j 消息，那么任何节点只有足够 新的路由到达组播组g ，则可以响应该r r e q 消息。如果一个节点d 接收到发 送给组播组g 的一条r r e q j 消息，但是自己目前还不是组播组g 的成员节点， 或者节点d 接收到一条r r e q 消息，但是目前还没有到达组播组g 的路由，那 么节点d 将r r e q 消息重新广播给自己的相邻节点。 源节点a 若是在超时结束前没有接收到r r e p 的应答消息，则重新广播一 条r r e q 消息，在广播之前将r r e q 消息的b r o a d c a s ti d ( 广播识别码) j n1 。源 节点a 若是在超时结束前仍然没有接收到r r e p 应答消息，则继续广播r r e q 消息，每次广播之前将r r e q 消息的b r o a d c a s ti d ( 广播识别码) 加1 ，最多重复 广播r r e qr e t r i s e s 条r r e q 消息。源节点a 广播r r e qr e t r i s e s 条r r e q 消息后仍然没有接收到r r e p 的应答消息，则假定组播组g 为不可达，或者组 播组g 内没有其他成员节点。在这种情况下，源节点a 成为组播组g 的组长节 点，初始化组播组序列号( 即设为1 ) 。如果起始的r r e q 消息是按照单播方式 传输给组播组g 的组长节点，并有接收到其相应的r r e p 消息，那么随后的全 部r r e q 消息按照广播方式发送，这是因为组播组g 的组长节点可能不可达， 或者单目标r r e q 消息中指定节点可能不在是组播组g 的组长节点。将每条广 播r r e q 消息中的目地节点地址域设为组播组g 的口地址，取消包含组播组g 1 0 重庆邮电大学硕士论文第二章a dh o e 网络组播路由协议的分析 的组长节点的m 地址扩展域。 接收到r r e q - j 的节点p 检查其路由请求表，查找是否存在所请求组播组g 的条目。如果路由请求表中没有组播组g 的条目，那么节点p 在路由请求表中 记录组播组g 的地址，以及请求节点的m 地址。如果路由请求表中不存在组播 组g 的前一跳条目，那么请求节点就可能成为组播组g 的组长节点。想加入一 个组播组的节点可以通过查询其路由请求表来决定改组的组长节点。 随着r r e q 消息在网络中的广播，各个节点设置用于建立反向路由的指针。 发送给组播组的r r e q 消息的传播类似于a o d v 协议中反向路由建立中r r e q 消息的传播。但是，r r e q - j 消息需要做一些不同于r r e q 消息的处理，一个节 点接收到一条r r e q - j 消息后，除了维护其单播路由表以外，还要在其组播路由 表中维护一个相应的路由条目，将该条目中的使能标志( e a n b l e df l a g ) 设置为 假( f a k s e ) ，如果随后将这条路由添加到组播树上，则将使能标志设置为真 ( t r u e ) 。一个节点若是组播组成员，则只能响应r r e q j 消息。 组播树组的第一个成员节点成为该组的组长节点。该节点负责定期向整个网 络广播包含本组最新序列号的g r o u ph e l l o 消息来维护本组播组的信息，组长节 点不但负责维护组的序号，还负责将这个序列号通知给所有的组成员节点。组播 树h e l l o 消息包含了几个扩展域，用于记录组播组的疋地址，及其该节点作 为组长及节点的所有组播组的相应序列号，组播组组长节点每广播一条组播 h e l l o 消息的时候，就将该消息中的组播序列号加l 。组播组h e l l o 消息中的 跳数域初始化为0 ，每个节点接收到一条组播组h e l l o 消息后就将该消息中的 跳数域加l ，因此，跳数域表示组播组h e l l o 消息当前接收节点与组播组组长 节点之前的跳数距离。 如果节点欲离开组播组，只须向最近的组播成员发送设置了”p r u n e 标志的 m a c t 消息。如果组播链路中断，为防止出现回路，规定由下游节点负责发起 链路修复，如无法修复，则下游组播树部分需选出新首领节点，形成新组播树。 当组播组成员节点收到其他组播组的g r o u ph e l l o 消息，并且本组播组首领口 a d d r e s s 较低，则此节点向本组首领单播置有r e p a i r 标志的r r e q 消息，首领节 点收到r r e q 消息后，发送r e e p 消息授权此节点完成组播树的合并，合并后 i pa d d r e s s 较高的组首领成为新的组播树首领节点。m a o d v 协议容易实现，且 支持单播，组播，广播。组播组成员的加人和离开都需发送控制消息，当节点多， 移动快时维护组播树较困难，协议的鲁棒性，扩展性较差。 重庆邮电大学硕士论文 第二章a dh o e 网络组播路由协议的分析 2 1 2a m rls a m r i s ( a dh o cm u l t i c a s tr o u t i n gp r o t o c o lu t i l i z i n gi n c r e a s i n gi d n u m b e r s ) t 3 0 j 是 一种基于共享树的按需组播路由协议。这种组播方式按需求建立一棵组播树，用 来支撑多个发送端和接收端。该协议主要采用了一种m s m 。i d 概念，在每次组播 对话中，该协议会按需为所有节点动态分配一个i n s m i d 。在一次组播会话中可 能会有多个发起者，a m r i s 将从中选出一个作为s i d ( s m a l l e s t i dn o d e ) ，它拥有 最小的m s m - i d ，根据这个i d 号，一个根为s i d 组播树被建立起来，当树在被完善 的过程中，m 号也逐渐的增大。一般来讲，s i d 为源节点或者是组播对话开始时 候的那个节点。 协议的最开始是对s i d 这个特定节点进行选择，当这个节点被确定下来的 时候，就会根据组播会话的需要向其邻居节点广播n e w - s e s s i o n 消息，该消息包 s i d 的m s m i d 值，n e w s e s s i o n 标识和路由信息。邻居节点收至l j