（信号与信息处理专业论文）3g环境下无线自组织网节能组播算法研究.pdf

重庆邮电大学硕士毕业论文摘要 摘要 随着世界范围内第三代移动通信( 简称3 g ) 进入规模发展阶段，尤其是我国提出 的t d s c d m a 标准其商用的日趋成熟，为不断扩大的移动通信用户群提供完善的 3 g 服务，满足其快速增长的数据业务需求，是通信业急待解决的问题。 无线自组网是一种自治的无线多跳网，整个网络没有固定的基础设施，可以在 不能利用或不便利用现有网络基础设施的情况下，提供一种通信支撑环境，拓宽了 移动网络的应用场合。自组网中也没有固定的路由器，所有节点都是移动的，并且 都能以任意方式动态地保持与其他节点的联系。在这种环境中，由于终端的无线覆 盖范围的有限性，两个无法直接进行通信的用户终端可以借助于其他节点进行分组 转发。每个节点都可以说是一个路由器，它们要都能完成发现和维持到其他节点路 由的功能。出于无线自组网组网灵活，抗毁性高的特点考虑，目前将其融合进3 g 网络的趋势已经越来越明显。 而组播技术具有网络利用率高、节约主机资源等优点，能够支持- n 多或多到 多的数据通信，因此，在视频会议、远程教育、文件分发、实时信息发布等无线自 组织网络应用中发挥着巨大的作用。由于在无线自组织网中，节点运行时所需要的 能量来自于电池的有限供给。这种移动自组网特殊的无线通讯条件不仅给组播路由 算法的设计带来诸多挑战，也大大降低了无线自组网的各种性能指标。 本文在无线自组织网组播算法m a o d v 的基础上，通过分析无线网络的能量损 耗模型和网络生存时间等要素，指出了m a o d v 算法在路由建立和选择过程中的弊 端，并提出了基于r r e q 发送数据包、多播路由选择及激活的改进算法 m a o d v - p p e f 。m a o d v - p p e f 算法在构造多播树前引进了能量预测机制，同时在 路由应答选择阶段考虑了链路的生存时间及跳数两方面，这样比单纯只从跳数上来 选择大大提高组播树的稳定性，避免了可能造成的断链危险。最后在3 g 环境下进 行相关仿真，仿真结果表明m a o d v - p p e f 在降低网络死亡节点数，延长网络生存 时间，控制能量耗损上有良好的效果，从而到达了提高无线自组网组播性能的目的。 同时在改进性能的同时，m a o d v - p p e f 的路由控制开销也未发生明显变化，并相 对m a o d v 算法略有改善，这是因为改进的算法在维护路由的时效性上更为有效。 【关键词】：无线白组织网，组播路由算法，节能，m a o d v ，m a o d v - p p e f 重庆邮电大学硕士毕业论文 a b s t r a c t a bs t r a c t w i t ht h ed e v e l o p m e n to ft h et h i r d - g e n e r a t i o nm o b i l ec o m m u n i c a t i o n ，e s p e c i a l l yt h e c h i n a st d s c d m as t a n d a r dc o m e si n t om a t u r e s t a g e i t i sa p r o b l e m f o r c o m m u n i c a t i o ni n d u s t r yt om e e tt h er a p i dg r o w t ho fd a t ao p e r a t i o na n do n e rt h ep r e f e c t s e r v i c eo f3gt ol a r g en u m b e ro fm o b i l eu s e r s t h ea dh o cn e t w o r k si sam u l t i - h o pa u t o n o m yn e t w o r k t h ee n t i r en e th a sn of i x e d i n f r a s t r u c t u r e ，w h i c hc a l ls u p p o r tac o m m u n i c a t i o ne n v i r o n m e n tt oi n c r e a s et h e a p p l i c a t i o no c c a s i o n so fm o b i l en e t w o r k si nn ou s i n go fe x i s t e n c en e t w o r k s m e a n w h i l e ， t h ea dh o cn e t w o r k sa l s oh a sr i of i x e dr o u t e r s ，a l lt h en o d e sc a nm o b i l ea n dt a k ed y n a m i c a r b i t r a r yw a yt ok e 印c o n t a c t 谢t ho t h e rn o d e s i ns u c he n v i r o n m e n t ，o w i n gt ot h el i m i t e d c o v e r a g eo fw i r e l e s st e r m i n a l ，t h et w on o d e sw i l lt r a n s m i tt h ep a c k e t sd i r e c t l yb yo t h e r n o d e s e a c hn o d ei sar o u t e r , t h e ya l la r ea b l et oc o m p l e t et h ef u n c t i o n so fm a i n t e n a n c e a n df m d i n gr o u t e s c o n s i d e r i n go ft h ef l e x i b i l i t yi na dh o cn e t w o r k s ，t h et r e n dt h a t i n t e g r a t i n gt h e3 gi na d h o cn e t w o r k sb e c o m em o r ea n dm o r ee v i d e n t l y r n l et e c h n o l o g yo fm u l t i c a s th a sm o r ea d v a n t a g e s ，s u c ha so w n i n gt h eh i g hr a ：t eo f n e t w o r ku t i l i z a t i o n ，s a v i n gt h er e s o u r c e so fh o s tc o m p u t e ra n ds oo n t h e r e f o r ei tc a n s u p p o r tt h eo n e t oo n eo ro n et om o r ed a t ac o m m u n i c a t i o n i tp l a y sai m p o r t a n tr o l ei n v i d e oc o n f e r e n c e ，d o c u m e n td i s t r i b u t i o n , r e a l t i m ei n f o r m a t i o nd i s s e m i n a t i o n b e c a u s e o ft h ee n e r g yw h i c hn o d e sn e e d e dc o m i n gf r o mt h eb a t t e r yi nt h ea dh o en e t w o r k s ，s oi t n o to n l yg i v e su st h eb i gc h a l l e n g et od e s i g nt h em u l t i c a s tp r o t o c o l s ，b u ta l s or e d u c e st h e p e r f o r m a n c eo f a dh o cn e t w o r k s i nt h i sp a p e r , t h ea u t h o ra n a l y s e st h em o d e lo fe n e r g yc o n s u m p t i o na n ds u r v i v a l t i m ei nw i r e l e s sn e tb a s e do nt h em a o d v p r o t o c 0 1 h ep o i n t so u tt h ed r a w b a c k sa b o u t t h er o u t e se s t a b l i s h m e n ta n dr o u t e ss e l e c t i o ni nm a o d v , b r i n g i n gf o r w a r dan e wt h e o r y c a l l e dm a o d v - p p e ft om o d i f yt h ep r o c e s so fr r e qs e n d i n gd a t a 、m u l t i c a s tr o u t e s s e l e c t i o n sa n ds oo n 1 1 圮【a o d v 二p p e fb r i n g st h ee n e r g yf o r e c a s t i n gm e c h a n i s mi n t o t h ee s t a b l i s h m e n to fm u l t i c a s tt r e ea n dt a k e si n t oa c c o u n te n e r g yc o n s u m p t i o na n d n o d e h o p s ，t h i sw a yw o u l db eb e t t e rt h a ns e l e c t i n go n l yb yc h o i c e so ft h eh o p so fm u l t i c a s t t r e e a tl a s t , t h ea u t h o rs i m u l a t e st h ei m p r o v e dp r o t o c o li nt h e3 ge n v i r o n m e n t ，n l c s i m u l a t i o nr e s u l t ss h o wt h a t t h em a o d v - p p e fi sg o o da tr e d u c i n gt h ed e a dn o d e s ， i i 重庆邮电大学硕士毕业论文 a b s t r a c t p r o l o n g i n gt h es u r v i v a l t i m e o fn e t w o r ka n dc o n t r o l l i n gt h e e n e r g yc o n s u m p t i o n a c c o r d i n g l y , i tc a nr e a c ht h ea i mo fi m p r o v i n gt h ep e r f o r m a n c eo fa dh o cn e t w o r k s b e s i d e st h e s e ，t h ec o n t r o lo v e r h e a do fm a o d v - p p e fc h a n g e sl i t t l e c o n t r a s t i n gt o m a o d v , b e c a u s et h em a o d v - p p e fi m p r o v et h et i m e l i n e s so fr o u t i n gm a i n t e n a n c e m o r ee f f e c t i v e 【k e yw o r d s 】a dh o cn e t w o k s ，m u l t i c a s tp r o t o c o l ，e n e r g y - s a v i n g ，m a o d v ， m a o d v - p p e f m 重庆邮电大学硕士毕业论文第一章绪论 1 1项目背景 第一章绪论 随着人们对随时随地地自由通讯的渴望，近几年来无线网络通信得到了迅速的 发展。当代的便携计算机或者个人助理都配有无线接口，通过无线网络人们满足了 自由通讯的梦。目前的无线通信大多需要有线基础设施( 如基站) 的支持才能实现。 一种新的网络技术一无线自组织网技术( a d h o cn e t w o r k s ) 应运而生。 a d h o c 网络是由一组由移动主机通过无线链路组成的一个自治系统，这些移动 主机构成了拓扑结构动态变化的通信网络。该网络不同于蜂窝移动网络，在蜂窝移 动网络中，移动主机间的通信必须依赖于有线骨干网和固定基站。而a dh o c 网络 没有这些基础设施的支持。由于建立a dh o c 网络快捷、灵活，不受有线网络约束， 因此它可以广泛应用于灾难救助、偏远地区等无法得到有线网络支持、或只是临时 需要通信的环境。同时a dh o c 网络也是一种无中心的网络，这种结构的网络要求 其中的节点通过运行分布式算法( 如信道接入、路由等) 来协调它们的行为。由于 使用多跳的通信方式，因此a dh o c 网络还面临着一些新的问题，例如网络路由组 播、广播、发现和维护，地址分配和自路由等。 由于a dh o c 网络是个不断变化的网络，在这个移动环境中，移动节点常常使 用无线链路。因此最明显的特征就是受限的链路带宽和较高的错误率，同时，移动 节点的体积通常都比较小，拥有的能量供应、处理器能力以及存储能力等都比较低， 在这种情况下，引进组播技术就能达到高效利用资源的目的。 组播的概念是在8 0 年代末期由s t e v ed e e r i n g 1 j 提出来的。组播是一种有效支持 网络中多点通信的的机制，也是一种数据包传输方式。当有多台主机同时成为一个 数据包的接受者时，出于对带宽和c p u 负担的考虑，组播成了一种最佳选择。组 播技术发展到现在，网络的基本模型并没有改变。现在互联网中使用的组播算法， 如d v m r p l 2 1 ，c b t 3 ，m o s p f 4 1 ，p i m l 5 , 6 】等，通常使用本地组播路由器对组成员 的状态进行管理。而目前由i e t f ( 互联网工程任务组) 制定的一个新的组播算法 s m f i t ( 简单多播转发算法) 正越来越引起人们的注意。s m f 能够提供适合于无线 网格和移动自组织网使用的m 多播转发包。同时它独特的多播复制数据检测技术 对于转发过程也起到一定的辅助作用。在网格拓扑中，s m f 算法利用减少继电器组 的方法提高自组网多播数据的转发效率，它的核心技术并不只是通过使用组和成员 节点的特殊信息字段来减少算法复杂性，而主要运用特殊且有效的中继算法对网络 重庆邮电大学硕士毕业论文第一章绪论 路由提前进行设计。综合上述关于组播的介绍可见a dh o c 网络中的组播技术是一 个值得深入研究的问题。 而随着3 g 技术的发展，信道控制技术的相对成熟，基于3 g 的自组织网络组 播应用慢慢成为一个崭新的研究领域。利用自组网技术和3 g 通信网的相互融合使 得实现高速移动状态下远距离话音业务和分组多媒体业务的多跳通信成为可能。 本论文所反映的研究工作的研究背景是重庆市自然科学基金计划项目：“基于 3 g 的自组织网络组播路由算法研究”。正因为考虑到世界范围内第三代移动通信( 简 称3 g ) 的蓬勃发展以及无线自组织网络应用范围的逐步扩大，因此在3 g 环境下研 究自组织网技术已成为国内外研究的热点。同时也由于自组网的相关特性，使得组 播路由算法在该网中扮演了重要的角色。本论文所反映的主题正是“3 g 环境下无 线自组织网节能组播算法研究”。 1 2a dh o c 网络研究 无线自组织网( a dh o cn e t w o r k s ) 作为一种新型的移动多跳无线网络，与传统 的无线网络有很大不同，它不依赖于任何固定的基础设施和管理中心，而是通过传 输范围受限的移动节点间的相互协作和自我组织来保持网络连接和实现其他功能。 因此这种网络也叫做无基础设施网络( i n f r a s t r u c t u r e l e s sn e t w o r k ) 1 2 1a dh o c 网络概述 自组织网是利用多跳无线网构建一个基于p 的移动互联网，并通过i p 实现与 固定互联网的无线连接以完成通信的网络。 按照移动通信系统是否具有基础设施，可以把移动无线网络分成两类。 第一种是具有基础设施的网络，节点借助于通信范围内最近的基站实现通信。 移动节点相当于移动终端，它不具备路由功能，而只有移动交换机负责路由切换功 能。 第二种类型是一种无基础设施的移动网络，也就是无线自组网( a dh o c n e t w o r k s ) ，也被称为多跳无线网【8 1 。无线自组网由一组带有无线通信收发装置的移 动终端节点组成，是一个多跳的临时性无中心网络，可以在任何时刻、任何地点快 速构建一个移动网络，并且不需要现有信息基础网络设施的支持，网中的每个终端 可以自由移动，地位相等。 “自组网”最初是应用于军事领域的，它采用分组无线网( p 鼢厄t ，p a c k e t r a d i o n e t ) 进行数据通信。a dh o c 技术就是取了p r e n t 的组网思想，从而产生的一种 2 重庆邮电大学硕士毕业论文第一章绪论 新型的网络构架技术。目前a dh o e 网络继承和发扬了d a r p a 资助无线分组数据 网的思想，特别是p r n e t 。p r n e t 强调的是在一个广阔的区域实现多跳的无线 通信，基于这种多跳的无线信道特点，p r n e t 面临着诸如介质接入、寻址、路由、 网络初始化和控制等难题。但p r n e t 所倡导的系统自组织特性似的p r n e t 网络 系统组建灵活，网络的抗破坏性强。 1 2 2a dh o c 网络特点 一般而言，无线自组织网络主要有以下特点： 网络的自主性。无线自组织网络可以在任何时间、任何地点不依赖现有网络 基础设施，通过节点之间的自我组织快速构建一个移动通信网络。 动态变化的网络拓扑。动态拓扑是无线自组织网络最明显的特点。在无线自 组织网络中，由于用户终端的随机移动、无线发信装置发送成功率的变化、无线信 道间的互相干扰以及地形等综合因素的影响。网络的拓扑结构可能随时发生变化。 有限的无线传输带宽。无线自组网采用的无线信道的物理特性决定了它所能 提供的网络带宽相对有线信道要低很多，再加上竞争共享无线信道所带来的碰撞、 干扰、信号衰减等因素，不仅使移动终端可得到的实际带宽远小于理论上的最大带 宽，而且也导致无线链路容量的不稳定。 单向信道的存在。由于各个无线终端发射功率的不同以及地形环境的影响， 无线自组织网络中可能产生单向信道。单向信道为常规路由算法带来三个严重影 响：认知单向性、路由单向性和目的节点不可达。 分布式的控制。无线自组织网络中的用户终端地位平等，不存在中心控制节 点，网络路由算法通常采用分布式控制方式，因此它应比采用集中式控制的网络具 有更强的抗毁性和健壮性。 有限的网络安全。与有线网络相比，无线自组织网络存在更加严重的安全性 问题。在设计网络时，需要仔细考虑切听、欺骗和拒绝服务攻击等。 较短的生存时间。无线自组网通常是临时构件而成的，多用于战场、救灾等 特殊场合。因此，相对固定网络而言，无线自组网的生存周期较为短暂b 1 0 。 1 2 3a dh o e 网络的应用范围 与其它网络相比较，a dh o e 网络的研究具有相当大的复杂性和挑战性，其应用 范围也更加广泛i n , t 2 。 移动会议：在室外临时环境中，工作团体的所有成员可以通过a dh o c 方式 重庆邮电大学硕士毕业论文第一章绪论 组成一个临时网络来协同完成一项大的任务，或协同完成某个计算任务。在室内办 公环境中，办公人员携带的包含a dh o c 收发器的p d a 可以通过无线方式自动从台 式机上下载电子邮件，更新工作日程表等。 家庭网：通过移动联网的方式把办公室的办公环境延伸到家庭，必要时在家 庭办公。或者利用我们随身携带的个人无线a dh o c 设备与装备了a dh o c 收发器的 家庭电器通信，自动完成开锁、开灯、打开娱乐设备、调节空调等操作。 紧急服务：由于停电或其他灾害出现，网络基础设施遭到破坏时，组建一个 a dh o c 网络帮助紧急救援人员完成必要的通信工作。 传感器网络：最近，人们开始关注大量分布的传感器协调工作问题。传感器 可以工作在危险的环境，通过在传感器上装备位置指示器、a dh o e 收发器等，将 传感器所在现场的信息传送到危险现场以外，收集和辨别事故信息，避免救援人员 进入现场。 个人域网络：通过a dh o c 网络把个人通信、娱乐、办公等设备联网，这些 设备可以与互联网网相连，也可以不与互联网相连，但在执行用户的某项活动时肯 定需要彼此通信。在这种情况下，移动性不是主要问题。 军事无线通信：在现代化战场上，各种军事车辆之间、士兵之间、士兵与军 事车辆之间都需要保持密切的联系，以实现集中统一指挥，协同作战。这是一种典 型的a dh o c 网络。 从以上各种无线自组网的应用不难可以看出在a dh o c 网络中，无线传输环境 和节点的自由移动为a dh o c 路由算法提出了一系列新的问题和挑战；首先，节点 的随机运动使得网络拓扑动态地变化，这就要求路由算法的收敛速度快。其次，无 线信道所能提供的吞吐率低、误码率高，这就要求路由算法的路由开销要尽量小， 并且还有具有较强的容错能力。最后，移动终端多数以电池为电源，因此必须保证 每个节点电量充足，如果某个节点因电池量不足而无法工作，它不仅影响本节点无 法工作，同时会造成信号不能转发，从而影响整个a dh o c 网络的正常运转。 1 3 3 g 蜂窝系统与a dh o c 网络整合的必要性 首先，a dh o c 网络能够对3 g 蜂窝系统中的盲区起到覆盖作用。在一些基站覆 盖不到或者信号很弱的地区，通过其他处于基站与移动台终端中间的中继节点转 发，将有效提高信号的覆盖。 其次，可以对网络的负载起到均衡作用。3 g 蜂窝系统中，各蜂窝小区话务量 不平衡且动态变化，引入自组网的动态中继，将一个小区的流量分流到周边小区， 有效地缓解了由于容量饱和而造成的呼叫阻塞和切断链。 4 重庆邮电大学硕士毕业论文第一章绪论 再次，对于距离比较近的移动节点，可以通过自组网直接通信，不占用蜂窝网 的资源，减少蜂窝系统的负担，提高系统的总容量。 最后，提高移动节点接入蜂窝系统的速率。在多跳多速率的网络中，采用多跳 高速率的路由代替一跳低速率的路由，只要能够有效地减少信道的占用时间，就能 提高系统总的吞吐量。g p r s 每时隙可提供的传输速率为c s 2 1 ( 9 0 5k b i t s ) 、c s 2 2 ( 1 3 4k b i t s ) 、c s 2 3 ( 1 5 6k b i t s ) 及c s 2 4 ( 2 1 4k b i t s ) ，其中c s 2 3 、c s 2 4 只有在 距离基站较近且信号较好的地区才能够使用，目前普遍采用的是c s 2 1 和c s 2 2 信 道编码方案。c d m al x 网络的情况与g p r s 类似，提供3 8 4 2 4 5 7 6k b i t s 的各种数 据速率，但达不到较高的接入速率。因此，3 g 蜂窝系统中引入自组网方式使移动 节点都能采用较高的接入速率，将提高整个系统的吞吐量。 1 4 研究目的和意义 与有线网络相比，自组网具有许多独特之处。如网络拓扑结构动态变化剧烈、 无线传输带宽有限、移动节点的能力有限、安全性差、存在单向无线信道以及生存 时间短等。这些都对自组网的网络性能，如能量损耗、控制开销等都带来一定影响。 尤其在能量问题上，由于无线自组织网中移动终端本身由电池供电，人们一般 希望移动终端( 如笔记本电脑) 在不充电的情况下能连续工作4 到6 小时。但目前 要达到这一目标还存在一定困难，这主要是受电池容量限制的缘故。而有关研究表 明在未来1 0 年电池的容量只能提高2 0 左右。同时随着移动终端性能的提升和功 能的加强，使其对电能的需求不断提高，因此在移动终端上采用各种节能机制成为 延长其工作时间的一种主要手段，节能问题也成为影响a dh o e 网络性能的重要因 素之一。 为了达到通过节约能量来提高自组网性能的目的，设计节能的组播路由算法就 显的非常有意义。目前针对节能这个大的研究方向，国内外学者先后提出一系列节 约能量的自组网组播路由算法，主要包括t 1 、基于能级分类的路由算法研究【1 3 1 。例如，一种通过保护能量偏低的节点来 延长网络可操控时间的新机制。该算法考虑当路由上的节点可用能量下限低到某一 域值就拒绝服务，某一中间值时则设定延迟以避免被选择，然后选择所通过节点能 量都比较充足的路由，从而延长整个网络可用路由的持续时间。 2 、基于路由创建和中继组维护的路由算法研究【1 4 1 。例如，自组网节能组播算 法e 2 m p r 在创建和维护中继组的过程中交替采用分组平均能量消耗最少和最大节 点花费最小两种标准，同时采用了基于图的组播结构，仿真表明较一般的组播选路 算法降低了节点的能量消耗，特别是在节点移动性较低，组播成员较少时更是如此。 5 重庆邮电大学硕士毕业论文第一章绪论 3 、基于自组网单向链路的节能算法研究【1 5 1 。例如，一种在组播路由选择过程 中利用节点电池能量感知的路由策略。通过把路径上节点的剩余能量作为路径选择 的度量，尽量地避开那些处于低能量的节点。 4 、基于结合功率控制的节能路由算法研裂1 6 1 。例如，在拓扑控制中使用v o r o n o i 图和最小领接图理论可以尽量排除长的边而留下短的边，同时优化跳半径并保护网 络的连通性。 5 、基于自组网非理想状态路径的节能路由算法研究【1 7 1 。例如，一种针对自组 网中节点能量有限的弊端，对路径进行优化的节能策略。该方法认为自组网的网络 生存时间是衡量路由算法性能最有效的指标，不能只寻找一条最佳路径来作为通信 路由，而是在保持一组优化路径的基础上通过概率的方式来进行选择。这样不仅可 以在节点加入或者离开自组网时做出更及时的反应，而且能够带来更小的路由开 销。 6 、基于自稳定最短路径树的节能路由算法研究【l 羽。例如，一种基于节点能量 的新模型。在这种模型中，运用了自稳定最短路径生成树来达到较低的能量损耗。 自稳定最短路径算法通过构建组播树来减小根节点与叶子节点之间的跳数。组播树 被维持在拓扑结构未发生变化之前的状态，这种状态通过节点间周期性发送组播树 信息来实现。树中所有的节点通过彼此交换邻节点的有效消息来维护组播树的状 态。一旦网络发生拓扑改变，节点就采取必要措施在局部重新建立新的最短路径树 来适应这样的变化。仿真结果证明这种自稳定最短路径树在多播组成员多的情况 下，能有效延长网络的工作时间并维持较低的能量损耗。 本文在研究基于树的无线自组织网组播路由算法的关键技术和实现流程的基 础上，研究了一种基于m a o d v 的节能组播路由算法，使之能降低自组织网的能量 损耗，减少链路拥塞。最后在3 g 环境下对改进算法进行了仿真，结果证明该改进 算法是能够有效改善3 g 环境下自组织网的能量损失。 本文选择的无线自组织网络组播路由算法是目前发展已比较成熟的m a o d v ( m u l t i c a s ta dh o co n - d e m a n dv e c t o r ) 。之所以要选择这个算法来作为节能研究的对 象。一是由于m a o d v 算法是应用按需路由技术的一种基于树的多播路由算法。目 前无线自组网路由算法根据路由建立的时间和方式一般分为表驱动路由和按需路 由两大类。基于表驱动路由的组播路由算法的缺点是节点要通过路由信息的周期性 交换来维持路由，这样将会对移动终端造成存储和计算负担，浪费了网络带宽和能 量。因此不利于运用到节能算法的研究中去。而按需路由算法不是一直保持到每一 目的的路由，而是根据路由源的需要建立相应的路由，因此能有效减轻网络信道中 算法控制包的负载，提高信道利用率。 同时还因为m a o d v 算法也是基于组播树的多播算法，分组被多播发送者以最 6 重庆邮电大学硕士毕业论文第一章绪论 少的拷贝分发到各个组接收者。如果是包括n 个节点的网络，只需要n 1 条链路来 传送相同的分组到所有的节点。相对于基于网格的组播算法而言，数据包所经过的 节点数目明显要少很多，因此也能够节省网络整体的能量消耗。 但m a o d v 算法在组播树建立及路由选择等环节上并没有考虑能量因素，针对 这些弊端进行相关改进，不仅延长了网络生存时间，有效的控制能量耗损，而且对 于今后进一步研究无线自组网中组播算法的性能具有重大意义。 1 5 作者工作及贡献 本文的主要工作是学习和总结无线自组网按需路由算法m a o d v 的算法流程， 分析并改进了算法中存在的对网络能量不利的影响因素。 l 、本文介绍了无线自组网的各种节能策略，阐述了这些策略对3 g 网络能量的 改善具有重要影响，并从基于树和基于网格的自组网组播算法出发，针对节能指标 进行分析，从而确定了下一步所选的能量改进算法。 2 、对基于树的无线自组网组播路由算法m a o d v 的特点及在节能弊端上的问 题进行了总结，并深入分析了m a o d v 算法的实现过程。 3 、本文在前述路由算法理论的基础上，针对m a o d v 算法在路由建立和选择 阶段存在的能量问题，提出了基于能量预测的组播路由改进算法m a o d v - p p e f 。 这种算法一方面在构造多播树前引进了能量预测机制，同时在路由应答选择阶段从 节点的能量消耗量及跳数两方面来进行选择，有效改善了自组网的组播性能。 4 、对仿真软件n s 2 进行了深入的学习和研究，并在无线网络环境下对m a o d v 和m a o d v - p p e f 算法在不同的3 g 速率下进行仿真，各项指标均说明引进 m a o d v - p p e f 算法，可以较好的改善自组网能量有限，各节点耗能不均等弊端。 1 6 论文结构 本论文共分七个章节，各章节安排如下：第一章阐述本文的项目背景、研究目 的及本人所做的工作。第二章着重介绍了无线自组网的各种节能策略并分析了3 g 网络与无线自组网技术的融合对节能的巨大影响，为今后的节能研究开拓了新思 路。第三章对a dh o c 网络中的组播路由算法从基于树型和基于网格型两个方向上 进行了比较。并针对各种节能指标对两个具体算法进行了相关仿真，为下一步的节 能算法改进奠定了理论基础。第四章对自组网中比较成熟的组播算法m a o d v 的基 础知识和运行机制进行描述并对m a o d v 在节能方向上的弊端进行了分析。第五章 则针对上一章提到的m a o d v 算法中的节能弊端从多个角度进行了相关改进。第六 7 重庆邮电大学硕士毕业论文 第一章绪论 章则对该改进算法在3 g 环境下进行仿真，通过多个参数的统计，说明改进算法是 能够降低网络控制开销，节省网络能量，提高整个网络性能的。最后一章对本论文 的工作进行了总结，并展望了今后进一步研究的工作。 重庆邮电大学硕士毕业论文第二章a dh o c 网络中的节能路由算法研究 第二章a dh o c 网络中的节能路由算法研究 移动a dh o c 网络是由一组具有路由功能的移动节点自组织成的无线多跳系 统。由于网络规模小、无基础设施和构建快速等特点，而广泛应用于野外考察、作 战现场、灾难救助等场合。其中由于网络中的节点通常是以有限能量的电池供电的， 限制了节点生存时间，从而使得节能策略成为当前一个研究热点。目前研究较多的 是在路由算法上实现节能控制。 2 1基于能量保护的路由节能策略 s i n g h 等人1 9 9 8 年首次明确地提出了无线自组织网中的路由算法必须考虑节能 策略【1 9 】，并且提出了若干初步的能耗度量参数，即( 1 ) 传送每个报文消耗的最小能量， ( 2 ) 网络分区时间最短，( 3 ) 节点能量级的最小变化，( 4 ) 每个报文的代价最小，( 5 ) 最 大的最小节点代价。 2 1 1最小传送功率的路由策略 最小传送功率路由策略就是在源节点和目的节点之间找到一条总的传送功率 最少的路径，这个问题可以通过式( 2 1 ) 来表示： f ，、1 肋加7 = a r g m i nl f 三【他，n i + ljf n l ，n n 依次是路径p 所经过的所有节点) ( 2 1 ) 其中a 表示所有的可选路径集合，p f ，叫n i , n i + 1 ) 表示在相继的两个节点n i ，酥l 之间的传送能耗。由于传送信号功率满足无线电信号的衰减方程，即 ( d ) = k d ”，i l 2 其中n 为衰减系统。 ( 2 2 ) 根据式( 2 2 ) ，当一个节点n j 出现在n i ，脚l 之间时，由于 ( 七) + 只。( d k ) ( d ) ( 2 3 ) 所以会选用路径( ，i l i ，n j ，n i + l ，) 代替( ，n i , n i + l ，) 。因此基于最小传送能耗 的路由策略通常都会选择那些拥有更多更短“跳”的路径。 m p r ( 最小能耗算法) 是基于最小传送功率的表驱动路由算法。在m p r 中， 每条链路上计算进行可靠通信所需要的最小发射功率并将此作为该链路的代价函 数，通过分布式的b e l l m a n - f o r d 算法，即将传统的链路距离替代为新的代价函数。 k o 等人提出的l a p a r l 2 0 ( 地理位置辅助路由算法) 是个g p s 辅助型的分布 9 重庆邮电大学硕士毕业论文第二章a dh o e 网络中的节能路由算法研究 式的能量路由算法，节点在转发数据包时，依靠其邻居节点的位置信息做出下一跳 的决定，然后使用递归的贪婪算法通过局部最优获得全局次优的路由。l a p a r 的 优势表现为：有效的能量路由；容易嫁接到现有的算法上；由于采用了仅基于邻居 信息的平面图，减少了拥塞现象；需要的开销有最小的变化。 而p a d s r ( 节能d s r 路由算法) 则是通过在d s r 算法的基础上运行l a p a r 算法进行节能控制来实现的。选择d s r 的原因是它在以下方面的优秀性能：非常 低的传输带宽；最小的路由表更新次数；选择最短路径的简单方法等。l a p a r 算 法能够在现有的任何路由算法上运行。 基于最小传送功率的路由策略算法简单并且可以很好地嫁接到原有的按需路 由算法或者表驱动路由算法中，但它包含两个缺点。一方面，这类算法使得一些关 键节点频繁地落入最小传送功率路径上，这些节点过早地耗尽能量将很容易产生雪 崩效应【2 l 】，从而缩短网络的生存时间；另一方面，由于产生大量的跳( h o p ) ，在时 变和衰减的无线链路上必将导致大量的重传，研究表明重传所带来的能耗有时甚至 超过策略本身所减少的能耗圈。 2 1 2 基于节点电池能量感知的路由策略 ( d m b c r ( 最小电池开销路由算法) 。 m b c r 算法是以总传输能量作为衡量标准的。在此算法中定义了节点电池开销 函数，从而计算出包含1 1 个节点的路径m 的总电池开销，而最大剩余电池能量的路 径即是拥有最小电池开销的那条路径。 ( 至) m m b c r ( 最小最大电池开销路由算法) 由于m b c r 考虑的仅仅是电池开销函数的总和，因此也可能将剩余很少电量 的节点选近来。为了避免节点使用过度，在m b c r 的基础上进行了改进，重新定 义了路径m 的电池开销，即选出电池开销最大的路径，然后再在这些路径中选出相 对开销最小的路径，这种路由策略会尽量避免每条可能路径上所有节点中拥有最少 电池容量的节点，较之m b c r 路由算法更公平一些。 c m m b c r ( 有条件最大最小电池容量路由算法) 。 c m m b c r 也是对m b c r 的改进，设计c m m b c r 的出发点是希望算法能够使 整个网络的生命周期最大，同时又公平地使用每个节点。其基本思想是首先找出源 节点到目的节点的所有电量充足的路径，然后从中选择出总传输能量最小的那条路 径作为路由选择的最终结果。 m r p c ( 最大剩余分组容量路由算法) m r p c 算法不仅考虑了节点的相关因素，如节点的剩余能量等，它还考虑到了 l o 重庆邮电大学硕士毕业论文第二章a dh o c 网络中的节能路由算法研究 与链路有关的参数。在概念上与m m b c r 算法类似，即要寻找那条最小容量最大的 路径，但容量的考虑因素和衡量方法不同。 m r e p ( 最大最小剩余能量路由算法) 。 m r e p 目的是工作在网络层，其中所有的节点以一个统一的发射功率工作。在 此算法中并不考虑节点的拓扑信息，从而避免了额外的开销。m r e p 也基于按需路 由的思想，自适应地选择出一组中间节点来转发自己的r r e q s 分组。因此m r e p 需要维护一种路由选择机制，来控制通信开销和所选路径的优劣。其中选择中间节 点的标准是根据节点的剩余能量决定的，m r e p 的路由选择机制逐渐减小此能量 值，直到找到一条路由，或者是能量值减小到零或最小。 m l r p ( 最小最大链路功率路由算法) 。 m l r p 算法旨在寻找一条低功率的路由，其中每个节点都能根据自己要进行通 信的邻近节点自适应地调整发射功率。m l r p 的路由发现思想和m r e p 基本是一致 的，但测量标准不同，相应地采用的方法也不同。在此算法中，路由寻找的发起者 决定转发r r e q s 请求的中间节点的统一发射功率，当路由建立尝试失败时，就相 应地减小此功率值。因此，此路由进程主要考虑最小化每个参与节点消耗的能量， 以及减小所选路径消耗的能量。这两种路由算法都延长了网络生存时间，同时也极 大地减小了所选路由上的通信开销。 ( p m a d s r ( 基于能量和移动性感知的自适应动态源路由算法) 。 在此算法中，设置有两个极限值f l ，r 2 ( r l t a ，则链路l l 的最小 节点生命周期被更新为t a ，同时a 节点路由表项中的最小生命周期字段也被更新 为t a 。如果在能量预测的过程中，1 2 所在的r r e q 也恰好到达a 节点，此时如果 它的最小节点生命周期t 2 m 删 r a ，意味着1 2 上的最小生命周期将保持不变，仍然维 持t 2 删，显然前后路径的生命周期相比较为t 2 m 小 t a t l 心，此时选择1 2 作为转发对象。当t 2 1 恻 t i 删 保持t i m 烈的值不变并在自 身路由表中记录下该t i 删 以后的节点作相同处理，直到遇到组播 树成员或有到组播树成员的路由转发 节点为止。在r r e p 单播到源节点的过 程中，将该链路最后的最小生命周期 t i 删记录在r r e p 中 当源节点收到所有r r e p 后，设 每条反馈路由的跳数为n i ，将 t i m 除以n i 后得到一权值) ( i 源节点通过比较x i 的大小， 选择其值较大的r r e p 信息 来更新自己的路由 习戮瓣 图5 5 基于m a o d v 路由选择的改进 图5 5 通过流程图的形式反映了基于m a o d v 路由选择的改进方法。 3 8 重庆邮电大学硕士毕业论文第五章基于m a o d v 的节能组播路由算法m a o d v - p p e f 5 2本章小结 无线自组织网络多播路由算法m a o d v 是应用按需路由技术的一种基于树的 多播路由算法。由于按需的路由算法不是一直保持到每一目的的路由，而是根据路 由源的需要建立相应的路由，因此能有效减轻网络信道中算法控制包的负载，提高 信道利用率。同时还因为m a o d v 算法也是基于组播树的多播算法，分组被多播发 送者以最少的拷贝分发到各个组接收者。如果是包括n 个节点的网络，只需要n 1 条链路来传送相同的分组到所有的节点。相对于基于网格的组播算法而言，数据包 所经过的节点数目明显要少很多，因此也能够节省网络整体的能量消耗，提高网络 的各项性能。但由于m a o d v 在路由建立和选择阶段没有考虑到节点的能量因素， 因此有可能造成网络因为能量消耗过快等原因造成断裂，从而严重影响自组网性 能。针对这些问题对m a o d v 算法进行了改进，提出了m a o d v - p p e f 算法。不仅 在构造多播树前引进了能量预测机制，同时在路由应答选择阶段考虑了节点能量消 耗量及跳数两方面。在第六章将通过进一步仿真来验证改进算法的优越性。 3 9 重庆邮电大学硕士毕业论文第六章m a o d v - p p e f 算法的仿真实现及性能分析 第六章m a o d v p p e f 算法的仿真实现及性能分析 6 1仿真工具n s 2 介绍 n e t w o r ks i m u l a t o r 仿真软件是位于美国加州的l a w r e n c eb e r k e l e y 国家实验室 于1 9 8 9 年开始开发的软件，简称n s 软件【4 5 l 。n s 是一