（计算机软件与理论专业论文）无线自组网中多播问题的研究.pdf

摘要 出于广泛的应用前景，无线自组网已经成为通信，网络，系统等研究领域的 一个热点。在无线自组网中，组通信模式的应用更为常见，比如：战地通信， 视频会议，路出搜索，数据采集等，而多播被公认为可以很好地解决组通信问 题。本文将研究无线自组网中的多播问题，具体的研究内容与研究成果包括： ( 1 ) 最小化多播中的传送节点的数目 本文使用u n i t - d i s kg r a p h q a 的最小s t e 磁通支配集合问题来刻画无线自组 网中的最优的虚拟骨干网的问题，目标是最小化多播骨干网中的节点数目即传 送节点的数目本文将给出一个集中式的近似算法，并通过理论分析证明其近 似比可以任意地接近2 c + 1 ，其中c 是边加权的s t e i n e r 树算法的近似比，目前c = 1 5 5 改进了原有最好的、近似比为1 0 的近似算法。 ( 2 ) 两跳内的广播调度问惠 本文研究了两跳内的广播( 多播的一个特例) 问题，目标是最小化广播需要 的时隙数本文将这个优化问题归约为最少时隙传送问题( m t s f ) ，并证明在一 般图中m t s f 是n p 完全的。对于m t s f 问题，本文中提出了两个启发式算法。理 论以及模拟实验的分析表明广播所需要的平均时隙数是l n l p 的一个线性函数， 其中p 是源节点j 两跳以内的邻居节点的集合。模拟实验的结果表明这两个算法 的性能都优于洪泛方法。 关键字：无线自组网多播，最小s t e i n e r 连通支配集，u n i t - d i s k g r a p h ，最小 延时广播，近似算法。 中固科学技术人学预i ：学位论文无线白纰喇中多捕问题的研究 a b s t r a c t i nr e c e n ty e a r s ，w i r e l e s sa dh o en e t w o r k sh a v er e c e i v e dg r e a ta t t e n t i o n , d u et o i t s a p p l i c a t i o n si nm a n ya r e a s t h i sp a p e rf o c u s e so nt h em u l t i c a s tp r o b l e mi n w i r e l e s sa dh o en e t w o r k s w h i c hi sag e n e r a lc 跚o f g r o u pc o m m u n i c a t i o na n dh a s s e v e r a la p p l i c a t i o n ss u c ha sb a t t l e f i e l dc o m m u n i c a t i o n , v i d e oc o n f e r e n c i n g , r o u t i n g q u e r y ，d a t ag a t h e r i n g , a n d s oo i lb e l o ww eg i v ead a s e r i p t i o no ft h e s p e c i f i c p r o b l e m s ，m a j o rc o n t r i b u t i o n sa n di n n o v a t i o n se n d e a v o r e di nt h i sp a p e r ( 1 ) m i n i m i z i n g t h en u m b e ro ff o r w a r d i n gn o d e si nm u l t i e n s t t h i sp a p e ru s e sm s c d s ( m i n i m u ms t e i n e rc o n n e c t e dd o m i n a t i n g s e oi nu d g ( u n i td i s kg r a p h ) t om o d e lt h eo p t i n l a lv m bp r o b l e m , w h i c ha i m sa tm i n i m i z i n g t h en u m b e ro ff o r w a r d i n gn o d e s w ew i l lp r e s e mac e n t r a l i z e d a p p r o x i m a t i o n a l g o r i t h mw i t hap r ( p e r f o r m a n c er a t i o ) a p p r o a c h i n g2 e + l ，w h e r eei st h ep ro f e d g e w e i g h t e d s t e i n e r t r e e a l g o r i t h m , c u r r e n t l y 谢t l l c = 1 5 5 i t i sa n i m p r o v e m e n t o f t h ep r e v i o u sb e s ta p p r o x i m a t i o ng u a r a n t e e1 0 ( 2 ) s c h e d u l i n gt h et r a n s m i s s i o nf o rt w o - h o pb r o a d c a s t t h i sp a p e rf o e a s e so nt h eb r o a d c a s tp r o b l e mi nt w o - h o pn e i g h b o r h o o d sa n dt h e o b j e c t i v ei s t om i n i m i z et h en u m b e ro ft i m es l o t s w em o d e li ta st h em i n i m u m t i m e s l o tf o r w a r d i n g ( m t s f ) p r o b l e m , a n dp r o v et h a tm t s fi sn p - c o m p l e t ei n g e n e r a lg r a p h t w oh e u r i s t i c sa 靶p r o p o s e dt os o l v em t s f a n dt h e o r e t i c a la n a l y s i s a sw e l la s t h es i m u l a t i o nr e s u l t ss h o w st h a tt h ea v e r a g et i m es l o tn e e d e df o r b r o a d c a s t i n gi sal i n e a ro fl l lj p ，w h e r ep i st h es e to ft w oh o pn e i g h b o r so fs o u l 吣e n o d es w ea l s oc o m p a r et h ep e r f o m m o ：o ft h eh e u r i s t i c sp r o p o s e dw i t ht h a to f f l o o d i n g , a n dt h es i m u l a t i o nr e s u l t ss h o wt h a tb o t ho ft h e m 讲刑o 蛳b e t t e rt h a n f l o o d i n g n 中目科学技术人学稍l ：学位论史光线自纽埘中多播姆题的研究 k e yw o r d s ：m u l t i c a s ti nw i r e l e s sa dh o cn e t w o r k s , m i n i m u ms t e i n e r c o n n e c t e dd o m i n a t i n gs e t ( m s c d s ) ，u n i t - d i s kc , r a p h , m i n i m u md e l a yb r o a d c a s l a p p r o x i m a t i o na l g o r i t h m 中国科学技术人学颈i 学位论文 无线舀组铷嘻中多捂褐题的研究 插图索引 图2 1 主动式路由协议1 0 图2 2 反应式路出协议 图2 3 一些经典路由协议的选路策略及其特点1 4 图2 4 无线自组网多播算法协议分类1 5 图2 5d d m 的转发计算数据结构 图2 6 几种组播路由协议的关键特征2 2 图2 7s t e i n e r 树2 3 图2 8 连通支配集2 5 图3 1m s c d s 和v m b 图3 2m s c d s 与最优的v m b 3l 图3 3 划分的一个例子，l = 3 ，p a r t i t i o n ( 2 ，1 ) 3 4 图3 4 p a r t i t i o n ( ，纠拘分界线3 6 图4 1 分时隙转发的一个例子4 2 图4 2 跳节点的覆盖4 6 图4 | 3 算法1 的模拟结果一4 8 图4 4 算法l 和算法2 的比较4 9 图4 5 和洪泛进行比较s o v i 中周科学技术人学坝i j 学位论文 无线臼组【州中多播问题的研究 1 绪论 本章摘耍本章首先将概述无线自组网的基础知识，发展，以及特点 接着将讨论无线自组织网络中多播问题的研究现状然后提出本文的 研究内客，并综述取得的研究成果最后将给出全文的组织结构 1 1 关于无线自组网 1 1 1 无线自组网简介 无线自组网( w i r e l e s s a d h o c n e t w o r k s ) 【1 ，2 ，3 ，5 1 是一组移动节点( 如带 无线网卡的笔记本、具有无线功能的p d a 等) 的集合，网中所有节点都可以任 意移动，并互相作为其邻居节点的路由器，通过无线通信技术，根据适当的路 由协议，实现网内节点白j 和网内节点与网外主机闻的通信。移动自组网中的通 信依靠节点之问的相互协作来完成，不依赖于任何固定设施，当通信请求的源 节点和目的节点不在相互的无线传输范围之内时，它们之间的通信要在其他节 点的帮助下以多跳的方式进行。 一般认为，没有基础设施的网络出现在2 0 世纪7 0 年代，在最初开发报文 交换技术( 后来发展成因特网) 不久，美国国防部高级研究规划署( d a 脞a ) 资助了一项特别的研究一分组无线网络( p a c k e t r a d i o n e t w o r k ) ，即让报文交换 技术在不受固定或有线的基础设施限制的环境下运行。最初的动机之一就是满 足战场生存的军事需求。在战场恶劣的环境下，通信设备不可能依赖已经敷设 的通信基础设施，一方面这些设施可能根本不存在，另一方面，这些设施会随 时遭到破坏。因此，能快速装备、自组织的移动基础设施是这种网络区别于其 他商业蜂窝系统的基本要素。在结构上，这种网络是出一系列移动结点组成， 是一种自组织的网络，它不依赖于任何已有的网络基础设施。蜂窝移动通信网 络和无线局域网都属于现有网络基础设施范畴，它们需要类似基站或访问服务 点这样的中心控制设备。而自组网是一种无中心的分布式控制网络。网络中的 中目科学技术入学颂i ：学位论文七线白纽嘲中多插问题的研究 结点动态且任意分布，结点之间通过无线方式互连，它将分组交换网络的概念 引仲到广播网络的范畴。这项工作丌辟了移动自组网( m o b i l e a d h o c n e t w o r k ， 简称a dh o c 网络或m a n e t ) 研发的先河。不过，这些研究内容在当时并没有 公开。由于自组网可以广泛地应用于战场通信指挥与控制、警察与医疗部门的 抢险救灾、传感器网络、课堂教育等众多领域，其战略意义非常重要。9 0 年代 中期，随着一些技术的公| 丌，a dh o c 网络开始成为移动通信领域一个公丌的研 究热点。 1 1 2 a dh o c 无线网络的特点 a dh o c 无线网络是一种移动通信和计算机网络相结合的网络，网络中的每 个节点都兼有路由器和主机两种功能。a dh o c 网络的特点主要体现在以下6 方 面【1 ，2 ，3 】： 1 )无中央控制和自组织性 移动自组网采用无中心结构，网络中没有绝对的控制中心。所有节点地位 平等，通过分层的网络协议和分向式算法协调彼此的行为。因其中任意节 点的故障不会影响整个网络的运行，所以与有中央控制网络相比移动自组 网有很强的抗毁性。 2 )动态变化的拓扑结构 在移动自组网中，终端可以任意移动，并且可以随时关闭其无线接口。同 时终端之间在信道上的相互干扰，环境地形等因素对无线信道的影响等都 使得移动自组网通过无线信道构成的网络拓扑结构会发生动态变化。 3 ) 。多跳路由的通信方式 由于节点发射功率的限制，其无线传输的范围是有限的。当要与其传输范 围以外的节点通信时，需要中间节点的转发，即要通过多跳路由来完成。 因为可以使用多跳路由的方式，所以节点的发射功率可以被调节，从而达 到节省电能，延长电池工作时间的目的。 4 )无线传输 2 中目科学技术人学颂i ：学位论文 光线白组【h 中多捕问题的柙f 究 移动自组网采用无线传输技术。出于无线信道自身的特性，它所能提供的 网络带宽与有线信道相比要低得多，并且其信道质量也较差。考虑到节点 在对共享无线信道的竞争中产生的冲突，信号衰减，噪声等因素，移动终 端能够获得的实际带宽远低于理论上的最高带宽，并且会随时间动态变 化。由于其采用无线信道，移动自组网更容易受到如被动窃听，主动攻击， 拒绝服务，剥夺“睡眠”等网络攻击。 5 )便携性和节能需求 移动终端具有携带方便，轻巧灵便等优点，但也存在固有缺陷，如计算和 存储能力较低等。同时，因为移动设备一般由电池供电，所以如何高效地 使用节点的电能，延长节点的工作时间就是移动自组网上一个很重要的课 题。 1 1 3 无线自组网的应用前景 由于其具有的许多优良特性，移动自组网已经在民用和军用通信领域占据 了一席之地。目前移动自组网的应用有： 1 1 军事应用 军事应用是移动自组网技术最早的应用领域之。因其特有的无需架设网 络设施，可快速展开，抗毁性强等特点，它是战场数字化通信的首选技术， 并且已经成为战术互联网的核心技术。 2 1 传感器网络 传感器网络是自组网技术应用的另一个领域。传感器的发射功率很小，大 量地理分散的传感器通过自组网技术组成网络，可以实现传感器之自j 以及 与控制中心之间的通信。传感器网络可以用于目标区域内信息的收集，对 象跟踪，环境监测等，因此在军用和民用上均有非常广泛的应用前景。 3 ) 紧急和突发事件场合 地震、洪涝等突发性自然灾害后，固定的通信设施很可能无法工作。此时， 移动自组网能够快速地提供通信支持这对抢险救灾工作具有非常重要的 中目科学技术人学硕l ：学位论文光线臼纰纠中多播问题的研究 意义。 4 1 临时场合通信 自组网的快速简便的组网能力使得它适用于临时场合的通信，例如大型会 议、庆典，展览等，并可以免去布线和部署网络设备的工作。 5 ) 个人通信 自组网技术可以用于个人网络( p a n ) 来实现p d a 、手机，喾汜本电脑等 个人通信设备之问的通信，并可以构造虚拟教室和讨论组等崭新的移动对 等应用( m p 2 p ) 。考虑到电磁波辐射的问题，个人网络通信设备的无线发 射功率应尽量小，这种情况下自组网技术的多跳通信特点将再次展现它的 优势。 6 1 商业应用 自组网技术的商业应用包括组建家庭无线网络、移动医疗监护系统、车载 移动自组网等。另外，在解决宽带互联网接入的“最后一公里”问题中自组 阿技术也被认为是非常有前景的解决方案之一。 1 2 无线自组网多播问题研究现状 随着便携计算机，掌上电脑等移动终端的广泛应用，无线通信和个人通信 系统的不断发展，未来的互联网络将向固定网络，基础结构移动网络和非基础 机构无线网络组成的集成网络发展。同时，面向组计算和组通信的需求比如移 动视频会议，视频点播，和无线网络会议，也在不断增长。多播是提供组通信 的一种理想的技术【6 】，适应于面向组的通信。随着无线技术的发展，以视频点 播、新闻发布、视频会议等业务为代表的组通信应用不断涌现，这些组通信应 用迫切需要提供一个更好的路由方案【4 】。这类业务的特点是，信息在一个组内 以一对多或者多对多的形式进行传输。例如新闻发布信息是由一个服务器发布， 大量不固定的无线接收终端接收。如果采用单播方式来传播这些信息，那么发 送源必须维护每个节点的信息。当移动节点数目很多时，对于发送源来说还需 要很高的传输速率和传输带宽。而且要求其接收的终端节点的拓扑结构保持不 4 中国科学技术人学坝i j 学位论文光线臼鲺上h 中多捕问题的研究 变。另外，相同的数据可能在同一个链路上传输多次，消耗大量的网络带宽。 因此，需要一种专门的组传输机制，这就是多播。到目前为止，业界已经提出 了好多无线自组网的多播通信协议。由于多播通信的重要性，对有线网络中多 播问题的模型，算法，协议的研究早已成为热点。在有线网络中，通常采用s t e i n e r 树 2 9 ，3 0 ，3 1 ，3 2 ，或者最短路径树作为多播子网的模型；并根据求解这些 图论问题的算法，设计相应的多播协议，主要包括：距离矢量多播路由协议 ( d v i v i r p ) ，s t e i n e r 树路径张- s p h ) ，多播最短路径优先( m o s p f ) ，核心树( c b t ) ， 和独立协议多播( p i m ) 等。 然而无线自组网不同于传统的有线网，或者无线局域网( w l a n d ，它是一 种通过无线连接的，易交的网络。它的无线链路，移动终端，多髟6 ( m u l t i - h o p ) 等特点给多播的实现带来了诸多困难，使得很多在有线网络中性能优良的多播 路由协议在无线自组网中使用时性能却很差【6 1 。实际上，在无线自组网中，路 径长度优化不再是唯一的要求，而路由迅速收敛，灵敏反应拓扑的变化，节省 带宽以及减少节点的资源歼销业成为路由设计的重要目标【5 】。在无线自组网中 实现有效地的多播路由协议，需要应对的主要难点有： 1 )适应无线通信特点，设计新的模型。无线自组网不同于有线网络， 它有独特的广播特性，在网络中能量的消耗，发生在节点上，而不 是发生在边上。因此，再用s t e i n c r 树，或者最短路径树已经不能再 转用于无线自组网，需要设计新的多播模型。 2 )适应动态拓扑。动态变化的拓扑是无线自组网的显著特点，由于用 户终端的随机移动，无线发信装置发送功率的变化，无线通道间互 相干扰，无线自组网的拓扑及结构可能随时发生变化，并且这种不 变化使人意的，方式和速度难以预测，当拓扑变化时，协议要花很 长时自j 和很大代价才能恢复。 3 )节省带宽资源。无线自组网采用无线传输技术作为通信手段。无线 信道的物理特性决定了它所能提供的网络带宽相对于有线信道要低 很多。使用多播的主要目的和优点是节省带宽，但是多播路由过程 中国科学技术人学i 葶 i ：学位论文无线臼纰喇中多播问题的研究 本身又会占用一部分带宽，可以被进一步优化。 维持多播结构。多播路由的实现，需要形成一定的拓扑结构，较为 准确，相对稳定的组成员关系。但在无线自组网中多播组成员会移 动，因而妨碍了固定多播拓扑的使用。在无线自组网中，及时更新 并动态地维持多播结构和多播组成员关系，具有相当的难度。 减轻终端负担。无线自组网中的移动终端具有灵巧，轻便移动好 的特点，但是这些优点是以能量和重量受到限制为代价的。而多播 中的终端通常身兼数职，即要维持多播结构，还有转发多播信包， 还要完成主机工作，因此如何减少路出开销以延长中断工作实践， 是一个无法回避的闯题。 可靠性与效率。自组网大多数是应用在军事上( 如战场) 和其它紧急 场合( 如灾难恢复) ，在这种紧急环境下，高可靠性和高q o s 是首要考 虑的因素，不能提供高转发保证( 无论在其它方面多么有吸引力) 的 多播机制都是不合适的。因此，m a n e t 多播技术强调快速、可靠 的转发。 7 )分布式控制。无线自组网中不存在中心控制点，用户终端的地位平 等，网络路由协议通常采用分布式控制方式。因而要比中心结构网 络具有更强的鲁棒性和抗毁性。 8 )多跳通信。由于无线收发机的信号传输范围的限制，无线自组网要 求支持多跳通信。这种多跳通信也带来了隐藏终端，暴露终端和公 平性等问题。 安全性。无线自组网由于采用无线信道，有限电源，分布式控制等 原因，容易受到安全性的威胁，如窃听，电子欺骗和拒绝服务等攻 击手段。 近年来，国外不少专家已经对无线自组网的多播路出协议进行了深入研究 和探讨，提出了一系列的协议，如：o d m r p 1 0 ，c a m p i l l ，a m r o u t e 1 3 。 a m p d s 8 i 等。在这其中，多数已有的多播协议如a m r o u t e ，o d m r p ，c a m p 6 中罔科学技术人学颂i 。学位论文 光线臼纰嘲中多捕问题的研究 ( 比如在o d m r p 中，前传组节点就够成了一个v m b ) 都是通过构建一个虚拟 多播骨干网( v m av i r t u a lm u l t i e a s tb a c k b o n e ) 来提供多播服务，在多播过程中只 需要v m b 上的节点进行转发，这可以很大程度上减小能量，带宽的消耗，并 减少通信时冲突发生的机会。无线自组网多播的已有工作中，还有很多复杂的 算法或者协议被用来解决节能多播问题 4 5 ，5 1 ，5 2 ，5 4 ，5 5 ，5 7 ，5 9 6 6 ，6 9 ， 这是因为对于无线自组网的两个非常重要的应用场景传感器网络和移动自组网 络，终端一般靠电池供电【7 】，对能量比较敏感，节能路由问题是最重要的问题 之一。而这些已有工作主要是通过构建多播树，并通过调节多播树上传送节点 的功率来优化多播过程中的能量消耗。 作为多播的一个特例，广播同样有着广泛的应用背景。洪泛是一个简单而 通用的广播策略【1 5 】，它的基本思想是让节点的每一个一跳邻居进行转发，但 是它有一个很严重的缺点，它会导致严重的冗余与重传，称为广播风暴【4 6 】。 在多跳的场景下，基于虚拟骨干网的广播是一个很适用的方法，在这种方法中， 只有在虚拟骨干上的节点需要进行转发，这大大减少了冗余的信息传送。当前 的工作主要集中在最小化虚拟骨干的问题上 1 6 ，1 7 ，2 0 ，2 2 ，2 4 ，2 5 ，3 4 ，3 5 ， 3 7 3 9 ，6 7 ，它可以被规约为最小连通支配集( m c d s ) i 司题。此外还有一些方法 4 7 ，4 9 ，5 3 通过在局部选择特定的转发节点集合，或者通过一些数学方法( 比 如整数规划) 来合理的调度广播过程中的节点传送，以达到减小延迟，减少冲 突，提高网络吞吐量的目的。 本文第二章将给出无线自组网已有单播，多播，广播协议的主要思想、并 对主要的几个多播协议优缺点和仿真效果进行详细的剖析和比较。 1 3 本文的主要研究工作和贡献 本文研究了无线自组网中的多播问题，主要的内容有：本文首先调研了无 线自组网中具有代表性的单播，广播，多播协议，介绍了自组网多播路由的主 要难点及研究现状，分类描述和比较了已有的主要协议，并对各个协议之间的 关系进行了阐述，最后分析了现有协议的不足。 7 中国科学技术人学颂i ：学位论文 尤线自纰州中多播问题的研究 通过分析无线自组网的多播特点，本文将使用已有的无线自组网最优多播 问题的模型最小s t e i n e r 连通支配集模型，接着会指出s t e i n e r 连通支配集模型 在刻画最优多播问题时的不足之处，并证明了最小s t e i n e r 连通支配集在理论上 最多比最优的虚拟多播骨干网( v m b v i r t u a l m u l l i c a s t b a c k b o n e ) 多一个节点。 对于最小s t e i n e r 连通支配集问题，本文提出了单元支配算法( c e l l d o m i n a t i n g ) ， 并理论上证明单元支配算法是一个近似比为4 1 的近似方案，改进了目前已有 的近似比最好的算法( 近似比为l o ) 。 本文还研究了无线自组网中的多播调度问题。作为起点，本文集中研究其 中一个特例，即两跳内的广播调度。本文将证明两跳广播的完美调度问题是一 个n p 完全问题，从而多跳广播的完美调度也是n p - 完全f 司题。对于两跳广播 问题，本文设计了两个近似算法，理论与模拟实验的分析表明：平均情况下， 经过这两个近似算法调度后，广播所需要的时蜘片的数目跟节点的对数成线性 关系。模拟实验表明这两个算法的性能都要优于洪泛算法。 1 4 本文的组织 本文剩下部分组织如下：本文的第二章将综述现有的无线自组网路由协议， 并着重分析了无线自组网中的多播算法和协议。本文的第三章将讨论最优多播 问题，引出最小s t e i n e r 连通支配集问题，提出单元支配算法，并对算法进行理 论分析。本文的第四章将研究无线自组网中的最优广播调度问题，分析问题的 计算复杂性，提出两个近似算法，并通过模拟实验分析其性能。第五章将作为 全文的总结。 1 5 本章小结 本章首先概述了无线自组网的基础知识，发展，以及特点。接着讨论了无 线自组织网络中多播问题的研究现状。然后概述了本文的研究内容，以及取得 的研究成果。最后给出了全文的组织结构。 8 中圈科学技术人学硬i j 学位论文光线臼纰h 中多椭问题的研究 2 无线自组网路由协议的研究现状 本章瘸要t 本章将介绍无线自组网中的各种路由算法与协议，并着重介 绍无线自组网多播路由的已有研究成果接着，本章将分类i e 较各种已 有的多播协议，最后壤分析现痔多播协议存在的幂足和空白奉章还会 给出无线自组网多播的两个常用模型，并简要分析其特点 2 1 无线鑫组两中韵单播路由协谈 在无线自组网中，节点的功率，传输半径有限，两个在对方传输半径以外 的节点要想逢行通信。必须要经过串弼节点僚转发( f o r w a r l t i n g ) 。无线台组网中 的单播路由就是通过控制包的传送来找到一条从源节点到目的节点的路径，从 恧。源节点的信息可以通过这条路径上的节点螅传送到达鼠的节点， 2 1 1 无线a dh o e 网络的路由分类 a d h o e 无线网络的路出可分为3 大类：主动式路出，反应式路由，混合式警备 由( h y b d d ) 。主动式路由协议是表驱动路由( t a b l e d r i v e n ) 协议，需要维护从 每小节点到所有其他节点的最新的、一致的路径信息。是一种基于表的路电协 议。主动式路由协议中的每个节点维护一张或多张表格，这些表格包含到达网 络中其它所有节点的路由信息。当源节点需要发送数据包时可以立即得到至 目的节点的下一跳路由。当检测到网络拓扑结构发生变化时，节点在网络中发 送更新消息。收到更新消息的节点更新自己的表格，以维护及时准确的路由信 息。典型的主动式路由协议包括：d s d v ，c g s r ，w p r ，g s r ，f s r ，r s r ， z h l s ，它们之问的继承关系如图2 1 。反应式路由协议是按需路由( o n ，d e m a n d ) 协议。仅在源节点需要传送数掇时力寻找并怠f j 建路由。当源节点需要得到到达 某个目标的一条路径时，就在网络中发起路径搜索，一旦找到某条路径，或者 每一条可能的路径都棱捡溺过后。搜索结束。在踌趣建立之后，再由路由维护 进程来维持找到的路径，直到从源节点出发的每一条路径都不能到达目的节点 9 中罔科学技术人学硕i ：学位论文 无线白组嘲中多播问题的研究 或源节点不再需要该条路径为止。典型的反应式路由协议包a o d v ，d s r 4 4 ， t o r a ，a b r ，s s r ，c b r p ，它们之白j 的继承关系如图2 2 所示。混合路由协议 是主动式路由协议和反应式路由协议选路策略的有机结合，它结合了两种路山 的优点，其代表就是z r p 协议。文献【6 8 】中给出了d s d v ，t o r a ，d s r ，a o d v 这几个经典路由协议的性能比较。 幽2 1 主动式路由协议 幽2 2 反斑式路亡西泌 2 1 2 几种经典路由协议介绍 ( 1 ) d s d v ：d s d v 是主动式的距离矢量路由协议，他需要每一个节直周 期地广播路由更新。d s d v 相对于传统的距离矢量协议的优越性在于他保证了 网络中无环路。在这种路由机制中，网络中每个节点都保存了一个路由表。路 由表中含有所有可能的目的节点以及到他们的距离信息。这些路由表以在网络 周期性的广播中来维持网络中节点的连通性。 1 0 中国科学技术人学顾i ：学位论文无线臼纽嘲中多捕勰题的研究 ( 2 ) c g s r ：c g s r 与d s d v 类似，但是c g s r 具有层次性。c g s r 指定 了簇首节点和网关节点，其中，簇首节点用来控制一组节点和网关节点，而网 关节点是2 个簇之间的节点。当一个节点要发送分组时，这个分组首先到达该 发送节点的簇首结点，然后，簇首节点把这个分组通过网关节点转发给另一个 簇首节点。不断重复这个过程直到分组到达目的节点。因此，每个节点都必须 有其簇成员的路由表。当一个节点不在任何簇的范围内时或是两个或多个簇首 节点在彼此的范围内时，就产生一个新的簇首节点。虽然c g s r 用d s d v 作为 其底层的协议，但是由于在c g s r 中寻路是通过簇首节点和网关节点来完成的， 所以他比d s d v 更具有可扩展性。此外在c g s r 中还可以采用启发式的方法如 优先级令牌的调度、网关编码调度和通路预约来改善其性能。 ( 3 ) w r p ：作为一种主动式路由协议，在w r p 中，每个节点保存在路由 表中的信息如下：距离、路由、链路开销和重传消息的列表( m i u ) 。m r l 记录关于消息序列号、重传计数器、每一个邻节点正确应答所需的标识和更新 消息的更新列表等信息。这就使得节点可以决定何时发送更新消息以及发送给 哪个节点。更新消息包括目的节点的地址、到目的节点的距离和目的节点的上 游节点。然后邻节点就修改自己的路由表并试图通过预备的节点建立新的路由。 w r p 的优点就是当一个节点试图执行路径计划算法时，可以通过目的节点的上 游节点所保存的信息和邻节点所保存的信息来限制算法，使得算法收敛得更快 并避免路由当中的环路。由于w r p 需要保存4 个路由表，所以比大多数的协 议需要更大的内存。w r p 还依赖于周期性的h e l l o 消息，这也要占用带宽。 ( 4 ) d s r ：d s r 是源节点按需点路由，每一个寻路的分组在其头部都携 带了完整的分组所必须经过的节点的顺序列表。在d s r 中，节点有一个高速缓 冲区用来存放所知道的目的节点的所有路由。当要发送分组时，节点首先查询 路由表。如果目的节点和所需要的路由在路由表中，则使用这条路由；否则， 就广播路由请求分组进行寻路。当路由请求分组在网络中传输时，他到达的每 一个节点都检查自己的路由表看他们是否有到达目的节点的路由。如果这些节 点的路由表中有到达目的节点的路由，就应答这个请求并提交这条路由。当路 中国科学技术人学颂i ：学位论文 光线白纽嗍中多播问题的研究 由请求分组到达了目的节点时，中转接点就查看路由请求分组经过的这条路径 是否在高速缓冲区中。如果高速缓冲区中没有这条路由，就把这个目的节点和 路由加到自己的高速缓冲区中以备将来使用。d s r 的优点在于中间节点无需维 持更新的路由信息为他们的转发分组寻路，因为分组本身已经包含了所有的路 由决定。事实上，这个协议和按需相结合消除了周期路由广播和其他协议中所 出现的邻节点的检测分组；它也不依赖于其他节点的保持有效的消息，这就减 少了带宽的占用和所需的能量。而且，由于节点的高速缓冲区储存了到目的节 点的多条路由，所以如果当一条路由断开时，节点可以在高速缓冲区中找到预 备的路出。缺点是在d s r 中的分组比较大，因为携带了整个路由信息。 ( 5 ) a o d v ：a o d v 是基于距离矢量的按需路由算法。a o d v 和像d s d v 一样的前摄协议不同，他是反向的。a o d v 只保持需要的路由，而不需要节点 维持通信过程中未激活的目的节点的路由。当节点s 需要到某个节点d 的路由 时，它就广播一个路由请求消息给它的邻节点，其中还包含了那个目的节点的 序列号。路由请求消息以一种控制的方式在网络中进行泛洪直到他到达了一个 节点，并且这个节点知道到目的节点的路由。每一个转发路出请求的节点就为 自身创建一条到节点s 的反向路由。当路由请求分组到达有路出到节点d 的节 点时，这个节点就产生一个包含到达节点d 所必需的跳数和此节点最近所知道 的节点d 的路由应答分组的序列号。每一个参与转发应答分组给产生路由请求 原始节点的转发节点都建立一条到节点d 的转发路由。从节点s 到节点d 路由 上的每个节点的链路状态是逐跳状念。也就是说，每一个节点仅仅是记住下一 跳而不是像源节点路由那样记住整个路由。除此之外，a o d v 为了维护路由还 周期性地发送h e l l o 分组。从本质上来说，a o d v 是d s r 和d s d v 的结合。他 借用了路由发现的基本的按需机制和d s r 中的路由维护，再加上逐条路由，序 列号和d s d v 中的周期性的信标。因此，a o d v 的优点是他可以利用多播的优 势，这正是所有其他协议所缺少的；而缺点则是他依赖于对称性的链路，而不 能处理非对称性链路的网络。 ( 6 ) t o r a ：t o r a 是基于逆向路由算法的分布式按需路由协议。它能提 1 2 中周科学技术人学硕i ：学位论文 无线白组嘲中多插问题的研究 供到目的节点的多条路由，快速建立路由和可能时通过拓扑变化的局部算法反 应来减小通信开销。路由的优化( 最短路径路由) 是次要的，我们通常采用更 长的路由来避免发现新路由时的开销。t o r a 协议是通过不同的属性来给每个 节点分配一个突发的高度来实现的。这种方法建立了一种始于源节点终于目的 节点的体制。从本质上来说，分组就是通过这种体制从源节点到达目的节点的。 t o k a 的优点是可以处理高密度的网络，它还支持保存2 个节点牺j 的多条路由 以及广播。然而，t o r a 算法是基于同步时钟的，所以时钟时间的不同可以导 致路由故障。并且这种算法还有潜在的振荡性，这可能影响路由的建立时间。 ( 7 ) a b r ：a b r 协议是一种比较特别的路由协议。在a b r 中每个节点周 期性的发送信标。所有收到这个信标的节点更新关联表。信标被一个节点收到 所需的时白j 越长，这个节点的移动性就越小。这个协议通过移动性差的节点( 更 稳定的，更可靠的节点) 建立生存期较长的节点。当一个节点收到这个消息时， 他就把这个地址和关联性计数添加到路由中并转发这条消息。因此，当发现多 条路由时，发送节点可以选择最可靠或最短的路由。 2 1 3 经典单播路由协议的选路策略总结 针对移动自组网的网络拓扑变化频繁、无线链路带宽有限、网络规模动态 变化等特点，经典路由协议主要采用基于跳数的最短路径( s h o r t e s t - p a t h ) 、链 路质量( 1 i n kq u a l i t y ) 等选路策略，试图得到最优路由。所谓最短路径选路策略 是指：路由协议选择路由时，以源节点与目的节点间的跳数为标准，选择跳数 最小的路由。d s r 、d s d v 、t o r a ，w r p 等路由协议采用了最短路径选路策 略。所谓链路质量选路策略是指：选路时以信道的信号质量( s i g n a lq u a l i t y ) 为 标准。s s a 等路由协议采用链路质量选路策略。图2 3 对一些经典路由协议的 选路策略及其特点进行了总结。 中国科学技术人学坝i ：学位论文无线自g t 蝌中多播问题的研兜 幽2 3 一些经典路由协议的选路策略及其特点 2 2 无线自组网多播路由协议 多播( m u l t i c a s t ) 有别于单播( u n i c a s t ) 和广播( b r o a d c a s t ) ，是一种一点 对多点或者多点对多点的致力于面各群组计算机的通信传播方式，它使用单一 的目的地址把数据发给一组主机。多播是一种非常实用的技术，它最突出的优 点是节省带宽，并且能显著减少分组传送丌销，因此在无线自组网这种带宽资 源紧张、系统资源有限的网络环境中具有重要的应用价值。在无线自组网中， 利用无线介质的广播特性，多播能够提高无线链路的传输效率，因而可以有效 地支持以紧密协作为特点的多种应用，如移动视频会议、视频点播( v i d e oo n d e m a n d ) 和无线群体游戏等。因此，多播具有重要意义。 在无线自组网中，多播协议通过一定的算法寻找源节点到每个目的节点的 路径，并由此建立一种特定的虚拟多播骨干网( v i r t u a lm u l t i c a s tb a c k b o n e ) 结构， 比如树，网格等。在多播过程中，源节点发出的信息通过这个特定的结构上的 节点的传送最终到达所有的目的节点。 多播路出算法是实现多播的基础，其功能主要是形成一定的机制( 如构造 多播树或形成多播网格等) 来完成多播路由任务。迄今为止，人们已经提出了 多种以无线自组网为应用环境的多播路由算法和协议，它们在寻路机制和多播 结构上各有不同，可以根据虚拟多播骨干网结构的不同把它们分为四类( 如图 2 4 ) ：基本树的多播路由协议；基于网络的多播路由协议；混合型多播路由协 议；无状念多播路由协议。 1 4 中圈科学技术人学顾i j 学位论文无线白纽州中多播问题的研究 移葫 d 弛睇冯锺t 蓐出协议 。厂t j - 1 芦= 胥；巴无r 酗2 4 无线臼纽网多橘算法协议分类 2 2 1 基于树的多播路由算法和协议 基于树的多播在有线网中是一个经过了精心设计的概念。有线网中的大多 数多播路由方案都是基于源节点树或共享树的。研究人员已经致力于把基于树 的方法扩展到无线自组网中来构造树形虚拟多播骨干网以支持多播通信。本节 内容是一些基于树的多播路由算法和协议的介绍。 a m m s i s l 利用增加i d 号的自组网多播路由协议( a dh o em u l t i c a s tr o u t i n g p 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 ，a m p a s ) q 】，一个多播会议中的各 节点被分配一个i d 。要发送包的节点有最小i d ，它发起形成包传送树的初 始过程。有最小i d 的节点叫鼬节点。i d 值随着到节点的距离而增加。 通过使用i d 节点能够快速适应网络拓扑的变化。 m a o d v 9 】 多播自组网按需距离矢量路由协议( m u l t i e a s ta dh o co n - d e m a n d d i s t a n c ev e c t o rr o u t i n gr o t o c o l ，m a o d v ) 是一种基于树的按需路由协议。 它为每一路由表项使用了目的序列号。序列号确保了没有路由坏路，并解 决了计数到无穷问题。其路由发现基于路由请求( r r e q ) 和路由答复 ( 黜也p ) 。当一个多播源要求一个到多播组的路由时，它广播一个带有加入 标志和多播组地址的r r e q 包。可达多播树的一员用一个r r e p 包响应。 非成员重新广播r r e q 包。收到m 江q 的每个节点更新路由表并记录序列 号和到源节点的下一跳信息。这个信息用于单播r r e p 到源节点。如果源 中固科学技术人学坝i ：学位论文 无线臼纰嘲中多播问题的研究 节点接收到对它路由请求的多个答复，它选择具有最少跳数或最新序列号 的。 l g t 7 2 l l o c a t i o ng u i d e dt r e ec o n s t r u c t i o na l g o r i t h mf o rs m a l lg r o u p 是一 种基于分组封装技术的小型组多播方案。它在底层单播路由协议的顶端用 覆盖的方式建立了一个多播分组分发树。多播分组封装在单播分组中，只 在组节点间传送。l g t 建立了两种树；位置引导k 列树( l g k ： l o e a t i o n - g u i d e dk a r r a y ) 和位置引导s t e i n e r 树( l g s ：l o c a t i o n - g u i d e d s t e i n e r ) 。目的节点的几何位置信息被用于建立分组分发树而无需知道全网 拓扑信息。可以推断：源节点到目的节点的几何距离越远，网络级的跳数 就越多。因此，l g t 努力创建几何边缘更短的树。它也支持一种基于路由 缓冲的优化机制，这种机制允许节点缓存已得路由并在目的节点集相同时 再次使用。在l g k 树方式中，发送者首先选择距离最近的k 个目的节点 作为子节点，然后按照“归入几何距离近的子节点”的原则将其余