（计算机应用技术专业论文）无线多跳网络中吞吐量优化的多播路由算法.pdf

摘要 无线多跳网络是一种有特殊用途的对等式网络，具有无中心、自 组织、可快速展开等特点。多播在无线多跳网络中扮演着重要的角色， 目前已成为研究热点之一，本文主要分析和研究了无线多跳网络中多 播路由算法吞吐量问题。 本文对无线多跳网络和其路由算法进行了介绍，总结和分析了无 线多跳网络多播路由算法。并将其按路由的建立分为基于树型、基于 m e s h 结构及其它结构路由算法；按解决问题的角度分为基于链路特 性、基于能量优化和基于提高吞吐量的多播路由算法。本文着重研究 了无线多跳网络中多播吞吐量最优化问题。现有的多播吞吐量最优化 近似算法，通常是以提高链路速率为目的，但单纯地提高链路速率而 忽略多播树的度限制了多播吞吐量的提高。本文通过深入分析无线多 跳网络特点，在综合考虑链路速率和多播树度对多播吞吐量影响的基 础上，提出了应用于不同模型下的多播吞吐量近似最优化算法。 对于无线多跳网络中m a c 层采用单播传输的情况，本文分别提 出了应用于节点发射功率相同环境下的u u pm t o a 算法和应用于 节点发射功率不同环境下的u n pm t o a 算法；对于无线多跳网络中 m a c 层采用广播传输的情况，本文提出了应用于节点发射功率不同 环境下的b n pm t o a 算法。通过仿真实验与同类近似最优化算法相 比较，u u pm t o a 算法、u n pm t o a 算法以及b n pm t o a 算法 能够获得更高的吞吐量，更适用于无线多跳网络络环境。 关键字：无线多跳网络，多播，吞吐量 a b s t r a c t w i r e l e s sm u l t i - h o pn e t w o r k sa r eas p e c i a lp e e r - t o 。p e e rn e t w o r k w h i c hi s s e l f - o r g a n i z i n g ，d y n a m i c a l l y a n d r e c o n f i g u r a t i n g e f f i c i e n t s u p p o r to fm u l t i c a s tg r o u pc o m m u n i c a t i o n s i sc r i t i c a lf o rw i r e l e s s m u l t i h o pn e t w o r k s ，t h i sp a p e rm a i n l yd i s c u s s e sm u l t i c a s tt h r o u g h p u t o p t i m i z a t i o np r o b l e mi nw i r e l e s sm u l t i - h o p t h ep a p e ri n t r o d u c e sw i r e l e s sm u l t i h o pn e t w o r k sa n ds u m m a r i z e s i t sr o u t i n gp r o t o c o l s m u l t i c a s tr o u t i n gp r o t o c o l si nw i r e l e s sm u l t i - h o p n e t w o r k sa r ec a t e g o r i z e di n t ot h r e ek i n d sb a s e do nt h er o u t i n gb u i l d i n g ， w h i c ha r et r e e b a s e d ，m e s h - b a s e da n do t h e rs t r u c t u r e a n di ta l s oc a nb e c a t e g o r i z e di n t ot h r e ek i n d sb a s e do nt h ep e r s p e c t i v eo fs l o v i n gp r o b l e m ， w h i c ha r e l i n k c h a r a c t e r i s t i c b a s e d ， e n e r g y - e f f i c i e n t - b a s e d a n d t h r o u g h p u t o p t i m i z a t i o n - b a s e d i nt h i sp a p e rw es t u d yt h em u l t i c a s t t h r o u g h p u to p t i m i z a t i o np r o b l e m t h ec u r r e n ta l g o r i t h m so fi n c r e a s i n g m u l t i c a s tt h r o u g h p u tu s u a l l ya i ma ti m p r o v i n gt h el i n kr a t e ，r e g a r d l e s so f t h ed e g r e e so ft h em u l t i c a s tt r e e ，w h i c hi st h em a i nf a c t o rt h a tr e s t r i c t st h e m u l t i c a s tt h r o u g h p u t i nt h i sp a p e rw ea n a l y z et h ec h a r a c t e r i s t i c so f w i r e l e s sn e t w o r k s o nt h eb a s i so fc o n s i d e r i n gt h ee f f e c t sp r o d u c e db y b o t ht h el i n kr a t ea n dd e g r e e st ot h em u l t i c a s tt h r o u g h p u t ，w ep r e s e n t s o m ea l g o r i t h m sa p p l i e di nd i f f e r e n tw i r e l e s s m u l t i h o p n e t w o r k s e n t i r o n m e n t w h e nt h em a c l a y e r t r a n s m i t sw i t hu n i c a s t ，w e p r e s e n t u u p m t o aa l g o r i t h m ，w h i c hi sa p p l i e di nn e t w o r k sw i t ht h eu n i f o r m t r a n s m i s s i o np o w e r , a n du n p m t o aa l g o r i t h m ，w h i c hi sa p p l i e di n t h o s ew i t hn o n - u n i f o r mt r a n s m i s s i o np o w e r a n dw ea l s o p r e s e n t b n p m t o aa l g o r i t h ma p p l i e d i nn e t w o r k sw i t ht h en o n - u n i f o r m t r a n s m i s s i o np o w e ra n dt h em a cl a y e rt r a n s m i t sw i t hm u l t i c a s t b y c o m p a r i n gt h e s ea l g o r i t h m sw i t hs i m i l a ro p t i m i z a t i o na l g o r i t h m s i n s i m u l a t i o n ，w ec o m et oac o n c l u s i o nt h a tu u p _ m t o a ，b n p _ m t o a a n d u n p m t o aa l g o r i t h m sc a l la c h i e v eh i g h e rt h r o u g h p u t ，a n di sa v a i l a b l e w i t h i nd i s t i l b u t e ds y s t e ms u c ha sw i r e l e s sm u l t i h o pn e t w o r kc o m p l e t e l y k e yw o r d s ：w i r e l e s s m u l t i h o pn e t w o r k s ，m u l t i c a s t ，t h r o u g h p u t 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 蚯至日期：皇吐年上月丝日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：年翩签名坶吼皿年上月监日 硕l ：学位论文第一章绪论 第一章绪论 随着信息技术的不断发展，人们对移动通信的需求越来越强。近年来，蜂 窝移动通信系统飞速发展，无线局域网、蓝牙( b l u e t o o t h ) 和家庭无线网( h o m e r f ) 等移动通信新技术也不断涌现。但是在某些特殊场合，这些集中式控制的移动通 信技术并不能胜任，如战场上部队的快速展丌和推进，地震或水灾后的营救，野 外考察，偏远矿山作业及临时性组织的大型会议等。这些场合的通信不能依赖于 任何预先架设的网络设施，或者预先架设的网络基础设施已经因灾害损毁而失 效，而是需要一种能临时快速自动组网的移动通信技术，无线多跳网络技术可以 满足这些特殊场合的要求。 无线多跳网络是一种新兴的无线网络，具有无中心、自组织、可快速展开 等特点，这与传统网络有很大不同，从理论到具体应用技术方面都有很多需要解 决的问题。因而在网络理论研究乃至整个计算机与网络通信理论研究中引起了广 泛的关注，成为近几年来的研究热点【l ，2 1 。 本章主要介绍无线多跳网络、无线多跳网络路由算法及无线多跳网络多播路 由算法的来源及研究背景。最后主要阐述了论文的主要组织情况。 1 1 无线多跳网络的概述 无线多跳网络( w i r e l e s sn u l t i h o pn e t w o r k s ) 是一种无线移动通信网络。它 是由一系列带有无线收发装置的动态节点所形成的一个多跳、临时性的自治系统 3 1 。它前身为分组无线网( p a c k e tr a d i o ) ，是由美国国防部远景规划局( d a r p a ) 在2 0 世纪7 0 年代启动的一个研究项目。该网络技术的研究起初是为了满足军事 应用的需要，故研究结果一直处于封闭状态。经过多年的储备，d a r p a 在联合 战术无线系统( j t r s ) 中扩大技术规模，并计划在今后投入使用。近几年来， 无线多跳网络的商业价值逐渐受到重视。由于它特别能满足野外活动与救灾时的 通信需求，可被用于战斗单位之间、救灾工作系统之间及城市车辆之间的通信， 还可用于某些需要临时快速建立一个通信网络的场合。无线多跳网络的设计思路 也由传统的单一技术体系过渡到基于i p 的多技术体系，从而使其更具有开放性、 适应性及灵活性，提高了开发速度。因此，民问对无线多跳网络的研究也开始升 温。在国外，特别是在网络层的路由算法方面，无线多跳网络研究已经进行了一 些工作。近几年，国内的民用研究也开始起步。 无线多跳网络是一种特定的无线网络结构，是指一组无线节点组成的多跳 硕l 学位论文 第一章绪论 的临时性的无基础设施支持的无中心网络。在无线多跳网络中，节点具有报文转 发能力，节点间的通信可能要经过多个中间节点的转发，即经过多尉l ( m u l t i h o p ) ， 这是无线多跳网络与其他移动网络的最根本区别。节点通过分层的网络协议和分 布式算法相互协调，实现了网络的自动组织和运行。因此它也被称为移动自组网 m a n e t ( m o b i l e a d h o c n e t w o r k ) 、自组织网络( s e l f o r g a n i z e d n e t w o r k ) 或无 基础设施的网络( i n f f a s tr u c t u r e l e s sn e t w o r k ) 。图1 1 描述了一个简单的无线多 跳网络。 图1 - 1 一个简单的无线多跳网络 与其它网络相比，无线多跳网络具有以下主要特点【4 l ： ( 1 ) 易于建网。由于无线多跳网络不需要固定的基干网设施，当需要时将一系 列带有收发装置的节点主机置于某一特定区域这些节点主机就形成了一个无线 多跳网络。 ( 2 ) 顽存性强。因为无线多跳网络无集中的控制中心，故当某一节点出现故障 时，并不一定会使整个网络瘫痪。 ( 3 ) 移动方便。无线多跳网络仅由一些充当主机与路由器的节点组成，无固定 的基本设施，网络的搬迁非常方便。 ( 4 ) 生存时间短。无线多跳网络一般是为了满足临时需要而建立的，当任务完 成后将被撤除。 ( 5 ) 可能存在单向通信。例如，当主机节点a 、b 的发射功率不同，a 发射的信 号b 能接收到，但b 发射的信号a 却接收不到。 ( 6 ) 主机能源受限。由于节点主机都是依靠锂电池供电，故其主机能源有限。 ( 7 ) 有限的无线传输带宽。由于无线信道本身的物理特性，它的网络带宽比有 线信道要低得多。另外考虑到竞争共享、无线信道将产生碰撞、信号衰解及噪 音干扰等因素，主机节点可得到的实际带宽远小于理论上的最大带宽值。 硕十学位论文第一章绪论 1 2 无线多跳网络路由算法 由于无线多跳网络是没有固定的网络设施的多跳网络，因此与传统的移动 通信网络在路由选择方面有很大的差异，例如在蜂窝移动通信系统中移动节点之 间呼叫的路由选择及建立主要是通过固定网络设施，如交换机等完成。在无线局 域网中，配备有无线局域网网卡的移动节点通过无线接入点连接到固定网络，其 主要研究内容集中在物理层和数据链路层，即信道接入控制上。传统的i n t e r n e t 网络的路由算法如距离向量算法d v a ( d i s t a n c e v e c t o r a l g o r i t h m ) 【5 6 l 和链路状态 算法l s a ( l i n ks t a t e a l g o r i t h m ) p 】都是针对固定网络设计的，都需要周期性地 交换信息来维护网络正确的路由表或网络拓扑结构图。而无线多跳网络带宽有 限，拓扑变化频繁，所以必须采用不同于传统的路由算法的策略来解决网络中的 路由选择问题。 无线多跳网络固有的特性为路由算法的设计提出了新的问题与挑战，主要包 括1 8 】： ( 1 ) 单向信道的存在。常规路由算法通常认为底层的通信信道是双向的。但 在采用无线通信的无线多跳网络中，由于发射功率或地理位置等因素的影响，可 能存在单向信道。它为常规路由算法带来以下几个严重影响：路由单向性和汇点 不可达性等。 ( 2 ) 有限的无线传输带宽。由于无线信道本身物理特性，它所能提供的网络 带宽相对有线信道要低得多。此外，考虑到竞争共享无线信道产生的碰撞、信号 衰减及噪音干扰等多种因素，节点可得到的实际带宽远小于理论上最大带宽值。 带宽受限对l s a 与d v a 在无线多跳网络中运行产生了一定的阻碍作用。 ( 3 ) 无线移动终端的局限性。移动终端在带来移动性、灵巧及轻便等好处的 同时，其固有的特性，例如采用电池一类可耗尽能源提供电源，内存较小，c p u 性能较低等，要求路由算法简单有效，实现的程序代码短小精悍，需要考虑如何 节省能源等。而常规路由算法通常基于高性能路由器作为运行的硬件平台，没有 上述限制。 目前无线多跳网络的路由通信模式主要分u n i c a s t ( 单播) 、m u l t i c a s t ( 多播) 、 a n y c a s t ( 任播) 及b r o a d c a s t ( 广播) 四大类。u n i c a s t 是指主机之间“一对一” 的通讯模式；m u l t i c a s t 是指主机之间“一对一组”的通讯模式，也就是加入了同一 个组的主机可以接受到此组内的所有数据；a n y c a s t 是指访问者与a n y c a s t 组中 的某一台服务器进行通信的模式。而且事先不知道会访问哪一台服务器； b r o a d c a s t 是主机之间“一对所有”的通讯模式。 研究无线多跳网络上的各种通信模式的路由算法成为了研究热点，目前研究 3 硕i ：学位论文第一章绪论 者己提出一些路由算法，我们对所提出的路由算法可基于不同角度进行不同的分 类。常见的几种分类方式为【，i ： ( 1 ) 根据网络逻辑视图分类。从这个角度可分为平面结构和集群结构两种。 对于平面结构的路由算法，网络的逻辑视图是平面结构，移动节点具有平等的地 位。其优点是网络中没有特殊节点，节点移动性较为简单且易于管理。如d s r 算法和a b r 算法等。对于层次结构的路由算法，网络的逻辑视图是层次性的。 在两级网络中，骨干网由较为稳定和综合性能较好的骨干节点组成。其优点是适 合大规模无线多跳网络络，扩展性较强。如c e d a r 算法【1 0 1 和c g s r 算法1 等。 ( 2 ) 根据驱动方式分类。按照路由发现策略的角度，可分为表驱动和按需驱 动两种路由算法。表驱动路由算法采用周期性的路由分组广播来交换路由信息， 如d s d v ”1 等。按需驱动路由算法是根据发送数据分组需要按需进行路由发现， 建立传输路径，从而实现信息传送，如a o d v 算法f 1 3 j 和t o r a 算法【1 等。 ( 3 ) 根据支持链路方向分类。无线多跳网络中可能存在单向信道，也可能存 在双向链路。按照对链路的支持方式，可分为支持单向链路的路由算法，如u a o r 算法【1 5 1 ，以及支持双向链路的路由算法，如s s r 算法【1 6 】等。 目前无线多跳网络由算法的最常见分类方式是基于路由发现策略的角度，将 路由算法按驱动方式分为先应式( p r o a c t i v e ) 和反应式( r e a c t i v e ) 两种算法 1 7 , 1 8 1 。 先应式路由算法又被称为表驱动( t a b l ed r i v e n ) 路由算法，是一种基于表 格的路由算法。在这种路由算法中，每个节点维护一或多张表格，这些表格包含 到达网络中其它所有节点的路由信息。当检测到网络拓扑结构发生变化时，节点 在网络中发送更新消息。收到更新消息的节点更新自己的表格，以维护一致的、 及时的和准确的路由信息。不同的先应式路由算法的区别在于拓扑更新消息在网 络中传播的方式和需要存储的表的类型。先应式路由算法不断地检测网络拓扑和 链路质量的变化，根据变化更新路由表，所以路由表可以准确地反映网络的拓扑 结构。源点一旦要发送报文，可以立即得到到达目的地的路由。典型的表驱动路 由算法有d s d v 算法、c g s r 算法和w r p 算法等。 d s d v ( 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 ) 算法 1 2 1 是基于传统 b e l l m a n - f o r d 算法经改良发展出来的，每个节点维护一张路由表，该路由表表项 包括目的节点、跳数、下一跳节点和目的节点序号。其中目的节点序号由目的节 点分配，主要用于避免因使用过时路由信息而产生无效路径和防止路由环路的产 生。在该算法实现过程中，每个节点周期性地向邻居节点广播一个报文，报文内 容为节点路由表或表中发生改变的表项，相关节点根据收到的报文更新路由表。 d s d v 算法最大的优点是解决了传统距离矢量路由算法中的无穷环路问题，同 时通过使用触发性路由更新，在网络链路状态改变时收敛较快。d s d v 算法中 4 硕j 。学位论文第一章绪论 节点维护着整个网络的路由信息，这样在有数据发送要求时可以立即执行，因而 适用于一些对实时性要求较高的业务和网络环境。缺点是周期的广播报文增大了 网络丌销，不适应网络拓扑变化频繁的网络环境，而且不支持单向信道。 c g s r ( c l u s t e r e dg a t e w a ys w i t c hr o u t i n g ) 是利用d s d v 算法作为下层路 由选择机制，使用分级路由结构和启发式路由选择机制的一种路由算法。网络内 有群首节点、网关节点和群内部节点。c g s r 采用l c c ( l e a s tc l u s t e rc h a n g e ) 算法形成集群结构，可能形成多个群，每个群有一个群首节点。而位于群首节点 的通信范围内的节点为群内部节点，同时位于多个群首节点的通信范围之内的节 点为网关节点。网络内每个节点维持两种数据结构：集群成员表和路由表。集群 成员表描述了每个目标节点所在集群的群酋。节点使用d s d v 算法周期性地与 邻居节点交换集群成员表，更新表项内容。当节点需要发送一个分组时，首先在 集群成员表中查找距自己最近的群首，然后根据路由表寻找到此群首的下一跳节 点。当移动导致集群结构被破坏时，c g s r 通过集群维护算法重新构造集群结 构。这种算法的优点是易于扩展，便于构建大规模网络。缺点是网络的功能相对 集中，顽存性较差。 w r p ( w i r e l e s s r o u t i n g p r o t o c o l s ) 算法本质上是一个距离向量路由算法，是 在路径发现算法p f a ( p a t hf i n d i n g a l g o r i t h m ) 基础上改进设计的。它利用去往 目的节点的路径长度和相应路径的倒数第二跳节点信息加速路由算法收敛速度， 改善d v a 中路由环路问题。在这个算法中的每个节点都保持路由表、距离表、 链路费用表和信息重传列表，并通过其邻节点的最短路径生成树s s t ( s h o r t e s p a t h s p a n n i n g t r e e ) ，生成自己的s s t ，然后再向邻节点传递更新信息。优点是通过对 接收到的所有信息的检测，消除了路由环问题，加快了算法的收敛速度。缺点是 需要更新的信息较多，占用较多资源。 主动路由算法还有g s r ( g i o b a ls t a t er o u t i n g ) 、f s r ( f i s h e y es t a t e r o u t i n g ) 、o l s r ( o f l t i m i z e dl i n ks t a t er o u t i n g ) 、h s r 、m m w n 、l a n m a r 、 t b r p f 、s t a r 和d r e a m 等i 捌。主动路由的优点是获取路由的延时小，因为每 个节点都保存着到其他节点的路由信息。这非常适合有实时要求的应用。但由于 主动路由中节点之间要不断地交互路由信息，当网络规模较大、移动速度较高时， 将消耗大量带宽，并且消耗大量的节点能量。由于带宽和电池容量都是移动节点 宝贵的紧缺资源，这将造成严重的局限性。当网络规模和移动性增加到一定程度 时( 超过某个闽值) ，大部分主动路由方案将不可行。 在表驱动路由算法中，由于每个节点需要实时地维护路由信息，这样在网 络规模较大、拓扑变化较快的环境中，大量的拓扑更新消息会占用过多的信道资 源，使得系统效率下降。为此，人们提出了一种反应式路由算法，又称为按需路 5 硕士学位论文 第一章绪论 由算法。反应式路由算法中，节点平时并不实时地维护网络路由，仅在移动主机 节点有数据要发送时才激活路由发现机制寻找到达目的地的路由，且仅在通信过 程中才维持路由，通信完毕后路由将被拆除。一般说来，按需路由包括三个过程： 路由发现，路由维持和路由折除。各算法的不同之处主要体现在这三个过程当中。 典型的反应式路由算法包括d s r 算法、a o d v 算法、t o r a 算法、a b r 算法、 s s r 算法和l a r 算法等。 d s r ( d y n a m i cs o u r c er o u t i n g ) 算法 2 0 1 是最早采用按需路由思想的基于源 路由方式的路由算法。在d s r 算法中，数据报文头部中携带有到达目的节点的整 条路由的信息。d s r 算法主要出路由发现与路由维持两个部分组成。在路由发 现阶段采用f l o o d i n g 法。为减少路由发现过程的开销，每个节点都包含一个 c a c h e ，存放已有路由信息。路由维持用来监测当l j i 路由的可用情况，当拓扑发 生变化，源路由产生中断时，源节点将收到一个路由错误信息，并通过查找c a c h e 中信息获得新的路由。如果不通，则重新启动路由寻找过程。d s r 算法的优点 是中间节点不必存储转发报文所需的路由信息，减少了网络开销。采用了路由缓 冲技术，进一步减少路由发现的代价，并提供到达目的节点的冗余路径，而且支 持非对称传输信道模式。缺点是增加了报文长度，存在陈旧路由问题，以及“路 由响应风暴”( r o u t er e p l ys t o r m ) 问题。 a o d v ( a dh o co nd e m a n dd i s t a n c ev e c t o r ) 算法【2 1 1 是一种改进了的距离向 量路由算法，它是在d s d v 基础上结合类似d s r 中的按需路由机制进行改进 的，借用了d s r 中路由发现和路由维持机制，利用了d s d v 中按跳( h o p - b y - h o p ) 路由、顺序编号和周期更新的机制。网络中节点不需要实时维护网络拓扑信息， 只是在发送报文且没有到达目的节点的路由时才启动路由选择过程，因而大大降 低了路由维持的开销。它优点是使用目的端顺序号可以避免路由环，利用按需方 式减少了网络开销，加入了多播路由算法扩展，并支持q o s 。缺点是该算法是基 于双向链路的假设，当出现单向链路时将产生无效路径，同时周期性广播h e l l o 信息，具有较大的网络开销。 t o r a ( t e m p o r a l l yo r d e r e dr o u t i n g a l g o r i t h m l 算法是在有向无环图( d a g ， d i r e c t e da c y c t i cg r a p h i c ) 算法的基础上提出的一种按需路由算法。其路由过程由 路由发现、路由维护和路由消除三个阶段组成。t o r a 的路由发现过程与其它 按需路由算法一样，首先在网中扩散路由请求分组，但在路由回复中采纳了d a g 算法。其机理为：每个节点有一个相对于目的节点的“高度值”，目的节点“高度 值”最低，并且相邻节点之间的“高度值”的比较形成一条或多条有向路径，方向 是从“高度值”大的节点指向“高度值”小的节点。算法的具体实现是通过路由回答 分组在回到源节点的过程中完成的。当路由断裂时，t o r a 仍采用上述算法重 6 硕士学位论丈第一章绪论 新构造失效的d a g 。这种算法的优点是算法的分布性好，没有周期性的广播操 作。缺点是依赖于i m e p ( i n t e m e tm a n e te n c a p s u l a t i o np r o t o c 0 1 ) 为其提供邻居 节点信息和底层可靠的按序传输服务，不支持单向链路。 a b r ( a s s o c i a t i v i t y - b a s e dr o u t i n g ) 算法的设计主要考虑到了无线多跳网络 动态拓扑的特点，引进了能表征链接持久性和传输质量的相关性稳定度 ( a s s o c i a t i v i t ys t a b i l i t y ) 概念。a b r 通过向相邻节点间定期产生信标( b e a c o n ) 来表示自己的存在。当一个节点收到邻近节点发送过来的信标时，本节点就会对 相关性表( a s s o c i a t i v i t y t a b l e ) 进行更新。对于相邻的每一个节点相关性表中都 有其相关性计数，表示着该节点相对于本节点的稳定程度。这个相关性计数为路 由选择中路由的稳定度提供了一个重要的参考。该路由算法把所选路径的稳定性 考虑在内，在一定程度上避免了路由在传输过程中发生中断，选择的路由持久性 较好，质量也较高；同时由于节点不能长时间保持静默，需周期性产生标志，占 用较多网络资源，而且由于节点运算量比较大，源节点需要等待比较长的时间。 目前，无线多跳网络理想的路由算法主要包括以下几个方面的考虑，分别是： 分布式运行、提供无环路由、按需进行算法操作、对单向信道的支持、提供节能 策略、可扩展性及安全性 9 2 2 1 。 ( 1 ) 分布式操作。对于集中式路由算法，通常存在一个中心节点，收集整个 网络拓扑结构，计算全网的最短路由，并将结果分发到其它节点。这种机制难于 适应动态变化的无线多跳网络，且开销过大。其次，作为无线多跳网络的重要应 用背景，军事通信系统要求很高的鲁棒性，所以理想路由算法应当采用分布式操 作。 ( 2 ) 提供无环路由。这一点是路由算法应当具备的基本特征。路由算法主要 通过以下机制保证这一点：a ) 使用有目的节点产生的路由序号机制，反映路由 状态的新旧程度，例如d s d v 和a o d v 算法。b ) 使用路径发现算法，如w r p 算法。c ) 使用源路由机制，如d s r 算法。d ) 使用面向目标的d a g 算法，如 t o r a 算法。 ( 3 ) 提供节省能源策吲2 2 】。大多数情况下，移动节点采用电池一类的可耗尽 能源提供电源。然而要在几年内将目前电池的可供电时间提高3 0 是很困难的。 暂时的解决方案仅有诸如设备“睡眠”机制，这种策略的实现需要底层设备提供功 能支持。因此，在路由算法的设计过程中，应注意节省能源的问题。 ( 4 ) 提供安全机制【2 。路由算法通过交换拓扑信息建立去往网中各个节点的 路由。攻击者对这些没有受到保护的路由信息可进行各种形式的攻击。可采用数 据安全中各种加密机制( 如数字签名) 防止来自网络外部的攻击。但由于无线多 跳网络内部节点可能被攻击者占领，并使用合法的私有密匙进行路由信息的数字 7 硕士学位论文第一章绪论 签名，因此须对路由算法加以改进以适应该环境的需求。 ( 5 ) 可扩展性。无线多跳网络本身具有组网灵活的特点。在该网络的应用过 程中，随时可能有新节点的加入和退出。为适应无线多跳网络的发展，对路由算 法进行设计时必须对其可扩展性进行适当考虑。 ( 6 ) 对单向信道的支持。在无线多跳网络中可能存在单向信道，对路由算法 的设计仅满足双向链路的需求是不切实际的。要全面考虑该环境下路由算法的应 用，所设计的路由算法应能支持单向链路。 ( 7 ) 按需进行算法操作。定时周期性地对网络信息进行不断更新必将带来大 量网络开销。按需操作这种驱动方式在很大程度上解决了这个问题，也是将束无 线多跳网络环境下路由算法的发展方向。 与此同时，我们对于无线多跳网络网络路由算法的设计还需要考虑主要的一 个问题：不同的路由算法在不同的环境中，其性能好坏可能有很大的差异。即使 是同一路由算法，在不同的网络环境中，其性能指标也可能会有很大的差异。无 线多跳网络组网环境主要涉及的内容有：网络的规模大小，即网络中节点个数的 多少；网络的拓扑结构变化速度；信道的传输带宽和单向信道的比率等。因此， 我们要根据具体环境因素设计无线多跳网络路由算法。 1 3 课题来源及研究意义 无线多跳网络是一种有特殊用途的对等式网络，具有无中心、自组织、可 快速展开等特点，这些特点使得它作为一种新型的移动通信网络，在军事应用领 域和商业应用方面都有广阔的发展空间。无线多跳网络起源于军事应用，其特有 的无需固定的网络设施、可快速展开和顽存性强等特点使得它成为数字化战场通 信的首选技术。无线多跳网络的一个重要分支传感器网络是无线多跳网络技术应 用的另一个大领域，它在军事应用、道路交通、工业控制、生物医药、环境科学、 医疗健康、空间探索以及各种安全场合都有非常广阔的应用前景。无线多跳网络 还可以应用在没有固定网络设施的情况下，如在偏远或野外探险考察、边远矿山 作业及边远地区执行任务，或者已有的网络设施遭到破坏而瘫痪的情况下，如地 震、水灾、火灾或遭受其他灾难后的抢险和救灾工作，或者需临时动态组网的情 况下，如会议、庆典、展览或高速公路上车队间的通信。个人局域网是无线多跳 网络的又一大应用领域，用于实现p d a 、手机和掌上电脑等个人电子通信设备间 的通信，并可以构建虚拟教师和讨论组等崭新的移动对等应用。此外，无线多跳 网络也可用于某些商业应用。如可以组建家庭无线网络、移动医疗监护系统，开 展移动和可携带计算等。 8 硕j 学位论文 第一章绪论 多播是一种实现从源节点同时向多个目标节点发送信息而仅在分叉的节点 转发数据包复本的通信形式。这一技术有效地解决了单( 多) 点发送，多点接收 的通信问题，在多媒体会议、数据分发、分布式并行处理和分布式交互仿真等方 面得到了广泛的应用。采用多播通信方式，能够有效利用网络带宽，减少网络拥 塞。随着高性能网络技术的迅速发展，多播在各种网络应用中发挥着越来越重要 的作用，而关于多播的研究近几年也成为国际上个广泛研究的热点问题【2 3 1 。 由于无线多跳网络具有无固定的基础设施、带宽有限等特点，使得固定网络 中的多播路由算法，如距离矢量多播路由算法d v m r p 、开放的最短路径多播 m o s p f 、基于核心的树c b t 及算法独立的多播p i m 等，不适合无线多跳网络中 运行。对于多播路由算法的设计与方法的研究，国内外许多学者均提出了不同多 播路由算法和算法。但是，对无线多跳网络而言，要实现多播通信，不仅要处理 多播中相对独立的组成员关系，还要处理由于移动主机自身特点所引起的单向链 路问题。特别是无线多跳网络本身具有通信带宽有限、能量受限等特征，更加限 制了多播通信技术在无线多跳网络中的应用。因此研究和设计有效的无线多跳网 络多播路由算法具有重要意义，它能有效地提供无线多跳网络组群通信，相比于 广播节约了带宽，具有重要的研究价值和应用背景。 目前关于无线多跳网络多播路由算法的研究方向主要可分为以下几类：一类 是设计高效快速的多播路由算法，处理多跳无线网络中通信带宽受限、链路单向 性等问题；另一类是以减少单位数据传输的能量损耗为目的；还有一类通过分析 研究多播树可获得的最大吞吐量来改进多播路由算法，这种方法叫做多播吞吐量 最优化问题m t o p ( m u l t i c a s t t h r o u g h p u to p t i m i z a t i o np r o b l e m ) 。 本文主要研究了无线多跳网络中多播吞吐量最优化问题，深入分析了无线多 跳网络特点，在不同网络模型下提出了相应的多播树吞吐量最优化算法。通过仿 真实验与同类近似最优化算法相比较，本文提出的算法能够获得更高的吞吐量， 更适用于无线多跳网络环境。 1 4 论文组织 论文全文共分六章： 第一章为绪论。这一章主要概述了无线多跳网络，并介绍了无线多跳网络由 算法，包括其面临的挑战、分类及设计目标。最后阐述无线多跳网络多播路由算 法研究的必要性和其重要意义。 第二章主要总结和分析了无线多跳网络多播路由算法的研究现状，将其按路 由的建立分为基于树型、基于m e s h 结构及其它结构路由算法；按解决问题的角 9 硕_ 1 学位论文 第一章绪论 度分为基于链路特性、基于能量优化和基于提高吞吐量的多播路由算法。并且介 绍了相应的较典型算法算法，给出了比较和分析。 第三章分析了多播吞吐量最优化问题，提出了一种分布式多播树构建算法 u u pm t o 魄，适用于自组网u u pm t o p 模式，并介绍了同类的吞吐量最优化 算法5 近似算法。通过对模拟仿真结果分析和比较，验证了u u pm t o a 能更有 效地提高多播吞吐量，且更适合无线多跳网络环境。 第四章主要提出了一种应用于u n pm t o p 模式下的分布式多播树构建算法 u n pm t o a ，并介绍了同类的吞吐量最优化算法2 4 近似算法。通过对模拟仿真 结果分析和比较，验证了u n pm t o a 能更有效地提高多播吞吐量，且更适合无 线多跳网络环境。 第五章介绍了b u pm t o p 模式下的多播吞吐量最优化算法2 一近似算法。并 通过深入分析无线多跳网络络的特点，针对b n pm t o p 模型提出了一种分布式 多播树构建算法b n pm t o a 。b n pm t o a 算法能较好地提高多播吞吐量，且 适用于无线多跳网络这样的分布式系统。 第六章为结束语。对所做的研究与设计工作进行了总结，并阐述了将来进一 步的工作计划。 l o 硕l ：学位论文第一二章无线多跳网络中多播路由算法 第二章无线多跳网络中多播路由算法 无线多跳网络中节点是独立的，传统的多播路由算法不再能适合无线多跳网 络的需要。主要的原因是：分布式的网络拓扑结构使多播树容易破碎，从而带来 了频繁地维护路由和需要很大的丌销。而且无线多跳网络中的能源消耗问题也不 同于普通网络。因此无线多跳网络中多播路由面临着很大的挑战。以下主要介绍 i i 前存在的一些典型的多播路由算法，并进行了分析和比较。 2 1 概述 多播是一种实现从源节点同时向多个目标节点发送信息，而仅在分叉的节 点转发数据包复本的通信形式。它以求利用最小的带宽、最小的服务器负载和网 络负载，一次向许多加入的接收者传递相同的内容。这一技术有效地解决了单 ( 多) 点发送，多点接收的通信问题，在多媒体会议、数据分发、分布式并行处 理和分布式交互仿真等方面得到了广泛的应用。采用多播通信方式，能够有效利 用网络带宽，减少网络拥塞。随着高性能网络技术的迅速发展，多播在各种网络 应用中发挥着越来越重要的作用。 在无线多跳网络中，多播算法有着很广阔的用武之地。无线多跳网络的广 播特性，以及典型的无线多跳网络中的节点通常以群组的方式执行给定的任务这 些事实，都使无线多跳网络非常适合于部署多播。然而，在无线多跳网络中使用 多播并非易事。受无线多跳网络的带宽有限，节点传播范围有限，节点能量有限， 单向链路问题，以及网络拓扑会改变等因素的影响，传统路由算法所采用的工作 机制在无线多跳网络中非常低效并且代价高昂。 在无线多跳网络环境下实现多播算法是一件非常具有挑战性的工作。设计 无线多跳网络多播路由算法和算法时，可在以下几个方面研究： 能源问题：无线多跳网络不同于普通网络，网络中节点的能量有限，而且在 多播算法中，对基于核心和源端的方法都使单个节点的能源消耗较大，单个能源 的失效将导致整个多播群无法工作。因此如何合理有效地分配网络中通信，防止 单个节点能源过早耗尽，延长网络的生存时间，降低整个网络能源消耗量将成为 成为了无线多跳网络多播算法的关键问题。 安全问题：由于无线多跳网络的广播特性，安全问题则相对于普通网络更困 难。而多播中成员动态加入和退出多播组，多播内所有成员都接收多播数据，这 给无线多跳网络的多播路由算法的安全性带来了很大的挑战，所以如何防止入侵 硕l ：学位论文 第二章无线多跳网络中多播路由算法 者加入多播组和接收多播数据将成安全主要的问题。 可扩展性：无线多跳网络中基于树和基于m e s h 结构路由算法都需要洪泛控 制信息，所以当节点的数目和多播成员数目增加和节点移动剧烈等情况时，洪泛 控制信息将带来很大开销，使算法性能大大降低。如何通过限制洪泛控制信息等 方法提高算法的可扩展性也将是一个研究热点。 多播服务( q o s ) ：在无线多跳网络中，如何合理地、有效地利用无线网络 资源，提高数据传输性能，进而为各种多媒体业务的服务质量提供保障，已成为 一个十分突出的问题，如何保证带宽和延时要求的多播服务( q o s ) 也是将来多 播算法的一个研究方向。 异构网络中的多播路由算法：对于由无线多跳网络、有基础设施的移动网络 及i n t e m e t 网络组成的异构网络，设计兼容的多播路出算法使其保持良好的适应 性、互操作性及开放性等方面都值得研究。 利用节点位置信息：无线多跳网络节点运动频繁，网络中链路频繁断裂，从 而对算法的健壮性提出了很高要求，因此倘若能够利用g p s 提供的位置信息， 设计有效的基于位置信息的多播算法将更适用于无线多跳网络运动的情况，也将 是研究的热点。 无线多跳网络中，多播能够有效地满足需要协同工作的计算机群组服务， 相比于广播节约了带宽，具有广阔的研究价值和应用背景。无线多跳网络的多播 路由算法在能源、安全、q o s 、扩展性、通用性及利用节点位置信息等方向具有 广阔的研究前景。 2 2 基于路由建立的多播算法分类 按路由的建立分类，目前研究的多播算法主要可分为三大类型，分别为f 2 4 】 ( 1 ) 基于树型的多播算法 ( 2 ) 基于m e s h 结构的多播算法 ( 3 ) 其它结构的多播算法 2 2 1 基于树型的多播算法 目前计算机网络实现多播通信的方式主要是采用多播树的方法来转发数据 包。多播树分为源组树( s o u r c e - b a s e dt r e e ) 和共享组树( g r o u p -