（计算机应用技术专业论文）一种基于最小能量路径的无线自组网络路由协议.pdf

硕士论文 一种基于最小能量路径的无线自组网络路由协议 摘要 无线自组网( a dh o c 网络) 是一种具有自组织能力的移动分布式多跳无线网络。 它可以快速部署和配置，适用于一些临时的、应急的场合，具有广阔的发展前景。该种 网络中节点一般靠电池供电，能量是非常稀缺的资源，因此能量控制逐渐成为自组网研 究的一个突出问题。 传统的能量控制方法主要都是采用某种拓扑控制算法，在尽量保证网络连通性的前 提下降低单个节点的发射功率，是一种介于链路层和网络层之间的能量控制方法。通过 拓扑控制算法可以使得每对节点间保留一条最短能量权值的路径，然而节点发送数据时 是通过多跳转发机制进行数据传输，需要路由协议进行分组转发决策，因此拓扑结构的 改变并不能保证在真实环境下的能量最优路径。而目前满足移动a dh o c 网络环境的经 典路由协议都不能基于能量最低原则选择路径，网络的能量管理无法由某一层单独来实 现，需要整个协议栈中不同的层协作来完成，因此，设计一种建立在综合的网络构架基 础之上的能量最优的路由算法是改善网络性能的需要。 本文在参考大量中英文资料，研究了a dh o c 网络体系机构、前人提出的典型的拓 扑控制算法以及经典路由协议的基础上，对现有拓扑控制算法的结果拓扑在路由时对最 小能量路径特性的保留进行了可行性分析。针对特定的网络模型，在二冗余范围内给出 了能量最优路径的生成算法，并给出了一种可行的能量最优路径的附加路由方案，使得 路由算法可以通过该方案达到对消息传输路径上的能量优化。这种路由协议将在一定程 度上降低节点的能量消耗，从而延长节点的生存时间。 在仿真平台上，设计了特定的网络模型，实现基于最小能量特性的分布式控制算法 的综合网络构架，理论分析和实验结果均表明，优化过的网络构架在保留了优化前网络 的连通性、平面性以及功率的支撑性，并在功率、能耗和网络生存能力等方面有了明显 改善。 关键字：a dh o c 网络，能量控制，拓扑控制，路由算法 硕士论文 竺壁! 璺 一一一一 a b s t r a c t m o b i l ea dh o cn e t w o r k ( m a n e t ) i ss e l f - o r g a n i z e d m o b i l ed i s t r i b u t em u l t i - h o p w i r e l e s sn e 艄，o r k ，u s e di ne m e 唱e n c yo rs o m et e m p o r a r yo c c a s i o n ，f o r i t ss t r o n g p o i n tmq u l c k 咖g e m e n ta n dc o n f i g u r a t i o n a dh o e n e t w o r kh a sw i d ea p p l i c a t i o no u t l o o k ，w h l l ee n e r g y i ss c 锄钾r e s 0 u r c es i n c et h em o b i l en o d e si n i tt a k eb a r e r ya st h e i re n e r g ys o u r c e ，s o e n e r g y c o n t r o lh a sb e c o m eac r i t i c a lp r o b l e mi nm a n e t r e s e a r c h 1 1 1 ec o m m o ne n e 唧c o n 仃0 1m e t h o d sm o s t l ya d o p t s o m et o p o l o g y 。c o n t r o la l g o r i 恤 b e t w e e n 眦觚dn e t w o r kl a y e r , t oc u td o w ne a c hn o d e st r a n s m i tp o w e rg u a r a n t e e m g a c o 衄e c t i v i t yo ft h ew h o l en e t w o r k e v e r yt w on o d e sk e e pam i n i m u m - e n e r g yp r o p e n y p 础 撕t h et o p o l o g yc o n t r o l ，w h i l e ，i ti st h em u t i n gp r o t o c o lw h i c h d e t e r m i n e st h ep a t ht 0s e n d p a c k e t sb e c a u s ei ti sac o m p l i c a t ec o g l s et of o r w a r d i n gp a c k e t si nm u l t i - h o p m e c h a n i s m ，s o c h a l l g i n go n l yt o p o l o g yc a n n o te n s u r et h em i n i m u m 。e n e r g yp r o p e r t yp a t hu s e d e v e 巧c l a s s l c r o u t i n gp r o t o c 0 1a p p l y i n gt oa dh o e n e t w o r kd o e s f f tc h o o s ep a t hb a s e do nt h el o we n e r g y 耐n c i p l e t h e r e f o r ei t i sn o tf e a s i b l et oi m p l e m e n tt h ee n e r g yc o n t r o li no n el a y e r ，d e s l g na n e we n e r 酣o p t i m i z a t i o nm u t i n gp r o t o c o lb a s e do nai n t e g r a t i v e n e t w o r ka r c h i t c c t u r ei s t h i st h e s i sr e s e a r c h e st h ea dh o en e t w o r ks y s t e m ，p r e s e n tt o p o l o g y 。c o n t r o l 出g o r i t h m s a n dc l a s s i cr o u t i n gp r o t o c o l s ，b ys t u d y i n ga l o to fc h i n e s eo re n g l i s ha r t i c l e s i ta n a l y s e st h e f e a s i b i l i t yo fr o u t i n gi nt h ec o n t r o l l e dt o p o l o g ys t r u c t u r e ，a n dp r o p o s e s ar e a l i z a b l es u b j 0 1 n e d r o u t i n gs c h e m eo nt h el o we n e r g yp r i n c i p l e b yu s i n gt h i s s u b j o i n e dm u t i n gs c h e m e ，i t o p t i m i z e st h ee n e r g yo fm e s s a g et r a n s m i t , r e d u c et h ee n e r g yc o n s u m p t i o n ，a n dp r o l o n g t h e 1 i v et i m eo f an o d e t h j st h e s i sc a r r i e so u tt h i sk i n do fi n t e g r a t i v e n e t w o r ka r c h i t e c t u r ei ns p e c i a la dh o e n e t 、0 r km o d e lo ne m u l a t o rp l a t f o r m t h et h e o r y a n de x p e r i m e n tb o t hs h o w st h a tt h e o p t i m i z e da r c h i t e c t u r ep r e s e r v e st h en e t w o r kc o n n e c t i v i t y , i e h n o g r a p h y a 1 1 dp o 嘣s p 锄 a 1 1 di m p r o v e st h ee n e r g yc o n s u m p t i o na n dt h en e t w o r kv i a b i l i t yr e m a r k a b l y k e y w o r d ：a dh o c ，e n e r g yc o n t r o l ，t o p o l o g yc o n t r o l ，r o u t i n ga l g o r i t h m i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名：盔兰刍1 年乡月勿日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名：姿堑伊c i 年6 月如日 硕- t 论文 一种基于最小能量路径的无线自组网络路由协议 1 绪论 无线a dh o e 网络是一种没有固定基础设备支持的自组织通信系统。它由具有无线 通信功能的节点进行自组织而成，组成的系统具有多跳，无中心等特点l lj 。无线a dh o e 网络适用于一些临时的、应急的场合，正因其能够十分迅捷的配置和部署而拥有十分广 阔的发展前景。在a dh o e 网络研究中，能量控制始终是众多关键问题中的一个。由于 每个节点都只有有限的能量资源，数据包会在能量的供应被限制时被阻止传送。因此， 基于各个节点能量的路由阻塞是区别路由协议持久性的一个重要手段。优化过的跨层路 由算法结合一定的拓扑控制可以有效的改善网络系统的性能，具有延长网络的存活时 间、降低通信干扰、提高数据链路层协议和路由协议的效率等重要的意义。 1 1 研究背景 1 1 1a dh o e 网络的概念 a dh o c 网络是一种网络中的所有节点都由移动终端设备组成，没有任何有线的基 础设备支撑的自组织网络。在一个a dh o c 网络中，如果两个移动终端设备相互之间都 在对方通讯信号的覆盖范围之内，那么它们就能够直接通讯。但是如果这两个设备之间 的距离比较远时需要进行通信，由于移动设备的信号覆盖范围有一定的距离限定，只有 通过这两个设备之间的另一个移动设备b 来进行转发才可以实现通信。所以在a dh o c 网络里，每一台终端设备同时也具有路由功能，各自承担着寻找路由以及中转数据报文 的工作。在a dh o e 网络中，每一台终端的信号覆盖范围都有限，因此一个数据报文通 常只有经过多台终端的中转才会到达目标终端。这样的路由信息一般都是由多次跳转组 成，所以a dh o c 网络又被称为多跳无线网络。 a dh o c 网络和当前的因特网环境里的移动i p 网络不一样。a dh o e 网络里，只存在 无线链路接入作为唯一的一种连接方式；而在移动i p 网络中，移动设备能够通过拨号 线路、固定有线网络以及无线链路等多种手段连接网络。在移动i p 网络里，移动设备 通过附近的基站等固定的有线设备的支持才可以保持通信，而在基站与基站之间仍然采 用了有线网络，保持着因特网的传统标准路由协议；而a dh o c 网络完全没有这些有线 设备的支撑。除此之外，在移动i p 网络中，移动设备只是一台拥有无线通信功能的普 通终端，其本身并不具有路由功能。当移动设备从一个区移动到另一个区时，整体网络 的拓扑结构并不会因此而变化；而a dh o e 网络里，移动设备的位置改变将会直接引发 网络拓扑结构的变化。 l l 绪论 硕一 ：论文 1 1 2a dh o e 网络的特性 a dh o e 网络作为一种新型的组网方式，具备如下特性【2 1 。 ( 1 ) 无中心和自组织 a dh o c 网络中节点的地位都是平等的，没有严格的控制中心，是一个对等的网络。 节点随时可以加入或离开网络，和有线网络相比，a dh o e 网络最大的区别就是可以在 任何时刻、任何地点快速构建起一个移动通信网而不需要构架硬件基础网络设施。a d h o c 网络的灵活特点很适合抢险救灾、偏远地区通信等应用。 ( 2 ) 网络拓扑结构动态变化 作为一个动态的网络，a dh o c 网络中的主机可以随处移动，也可以随时加入或离 开，这些都会引起网络拓扑结构的变化，而且变化方式和速度都是难以预测的。而常规 网络的拓扑结构则相对较为稳定。 ( 3 ) 能源的局限性 在a dh o c 网络中，终端均是一些移动设备，如p d a 、便携计算机或掌上电脑。由 于终端可能处在不停地移动状态下，并且无需有线基础设施的支持，主机的能源主要由 电池提供，因此a dh o c 网络有能源有限的特点。 ( 4 ) 网络的分布式特性 在a dh o c 网络中节点地位平等，主机通过分布式协议互联。一旦网络的某个或某 些节点发生故障，剩下的节点仍然能正常工作。a dh o c 网络中的通信终端同时具备路由 和主机功能，网络中使用的通信协议和路由算法通常采用分布式控制方式，因而抗毁性 比采用集中式控制方式的网络要强。 ( 5 ) 通信带宽有限 a dh o c 网络中没有有线基础设施的支持，节点之间的通信通过无线信道传输，而无 线信道本身所提供的带宽较有线网络低许多，这是由其物理特性决定的。此外，由于无 线信号有路径衰减，并且会受到信号干扰和噪声影响，无线链路的状态很容易发生变化， 链路的实际有效吞吐量远不如理论结算出的最大传输带宽。 ( 6 ) 有限的物理安全 同构无线信道传输的网络通常比有线网络更容易受到物理安全攻击，易于遭受窃 听、欺骗和拒绝服务等攻击。现有的链路安全技术有些己应用于无线网络中来减小安全 攻击。不过a dh o c 网络的分布式特性相对于集中式的网络具有更佳的抗毁性。 ( 7 ) 生存周期短 a dh o c 网络主要用于临时的通信需求，相对与有线网络，它的生存时间一般比较短。 ( 8 ) 可动态分配资源 包括无线信道、信道速率、功率、路由等。 硕士论文一种基于最小能量路径的无线白纽网络路由协议 1 1 3a dh o e 网络的应用 无线a dh o e 网络是一种自创造、自组织和自管理的网络，由于具有组网快速、灵 活机动，节点易于分布等诸多优点，在战争、抗灾等特殊领域有着不可替代的作用【3 】。 同时，它可以作为3 g 的补充，解决接入网的瓶颈问题，例如可以利用a dh o c 网络快 速建立一个规模较大的接入网，提供高速接入。它的商用化有巨大大的市场价值【4 】，其 应用场合主要有以下几类： ( 1 ) 军事应用 军事应用是a dh o c 络技术的重要应用领域【5 】。在现代战场上，各种军事车辆间、 士兵间、士兵与军事车辆之间都需要保持密切的联系，以完成指挥、部署和协调作战。 a dh o c 网络因其独有的无需网络设施支持、可快速布设、抗毁性强等特点而成为数字化 战场上首选的通信技术。如今，a dh o c 网络技术已成为美军战术互联网的核心技术。为 了满足信息战和数字化战场的需要，美军研制了大量的无线自组织网络设备，用于单兵、 车载、指挥所等不同的场合，并大量装备部队。 ( 2 ) 紧急突发场合的应用 在一些特殊场合或紧急情况下，有线的移动通信技术不能胜任。比如，发生地震、 洪水等自然灾害后，基础通信设施可能遭受破坏，但是在抢险救灾过程中救援人员间的 通信仍需要得到保证，这时a dh o c 网络这种不依赖任何固定网络设施又能快速展开的自 组织网络技术【6 】是一种最佳选择。类似地，边远或偏僻野外地区的环境下，同样无法依 赖固定或预设的网络设施进行通信。a dh o c 网络技术的独立组网能力和自组织特点，是 这些场合通信的首选。 ( 3 ) 传感器网络 传感器网络是a dh o c 网络技术的另一大应用领域【引。在很多应用环境中，传感器网 络只能使用无线通信技术，并且传感器的发射功率都不能很大，这是由体积和节能等因 素决定的，因此使用a dh o c 网络实现多跳通信是非常实用的解决办法。通过分散在各处 的传感器组成的a dh o c 网络，传感器可以实现相互之间以及与控制中心的通信，这在爆 炸残留物检测等领域具有非常广阔的应用前景。 ( 4 ) 个人局域网 个人局域网( p a n ，p e r s o n a la r e an e t w o r k ) 是a dh o c 网络技术的一大应用领域【7 1 ， 不仅可用于实现p d a 、手机、便携计算机等个人电子通信设备之间的通信，还可用于个 i 绪论硕士论文 人局域网之间的多跳通信，蓝牙技术中的超网( s c a t t e r n e t ) 就是一个典型的例子。 1 1 4a dh o c 网络的能量节约问题 在a dh o c 网络中的节点的能量是十分珍贵的资源，这些能量一般都是由有限容量 的电池所提供。移动a dh o c 网络所具有的“a n yw h e r ea n da n yw h e n ”的巨大潜力的 主要来源也只在于可以随意进行移动但只携带有限电能的无线通信设备。由于目前的计 算技术以及通信技术的发展远远超过了现有的电池技术，移动a dh o c 网络需要更多地 依赖于协议层中所定下的一系列节能策略，以此来增加各个节点的存货时间。能量保护 策略已经成为了移动网络中所有路由协议层的设计中都会关注的问题。 出于以下的两点原因，要在移动a dh o c 网络里设计出一套能量保护策略，会比在 普通的无线网络中设计更加复杂：第一，在一个移动a dh o c 网络中，单个节点有可能 是一个数据源宿，也有可能成为其它节点在高层路由控制协议罩的协助者，同时成为 向其他节点转发报文的路由器，两种角色有可能同时扮演也有可能按照需求相互随机转 换；第二，移动a dh o c 网络中既没有类似于传统的蜂窝式网络中的定点基站，也没有 类似于传统的w l a n 网络中的接入点，要想为每一个网络节点定制并且动态调整能量 保护策略会需要面对更大的困难1 9 j 。 1 2 课题来源及本文主要工作 1 2 i 课题来源 本课题来源于“十一五 预先研究项目“无线自组网构架与性能分析”和“机动节 点自组织架构与安全技术研究”。项目对无线自组织网络的体系结构、性能保持、安全 防护等方面开展研究，研究内容涵盖移动自组网自适应分布式体系结构、自主组件管理 技术、动态拓扑交互技术、能量高效的自组织策略和速率控制方法、服务安全和认证体 系等。 1 2 2 本文主要工作 ( 1 ) 对无线a dh o e 网络定义、特点、体系结构、应用领域和研究现状以及相关技 术成果进行了详细阐述。给出了相关的网络和能量模型，研究了网络各协议层的能量保 护措施，重点分析了目前的功率控制算法和能量约束的路由协议。 ( 2 ) 研究了节点传输能量问题，分析和实现了基于闭域模型的节点能量最优转发集 的求解算法1 1 引。在对算法的可行性及性能进行深入分析的基础上，提出了实现细节和改 进措施，消除原算法中因单向链路和邻居分布不均匀带来的能量效率降低问题，并详细 4 硕士论文一种甚于最小能量路径的无线自组网络路由协议 阐述了改进思想以及具体的实现流程和详细的理论分析和性质证明，在保持其原有拓扑 优秀性质的基础上，进一步降低节点功率，减少能耗，延长网络生存时间，优化网络的 生存能力。 ( 3 ) 研究了无线a dh o e 的路由协议，着重研究了目前研究人员提出的能量约束的 路由协议，对实现跨层能量保护路由协议做出了可行性分析，并给出一种基于前文所述 的改进后的拓扑控制算法的屉小能量路径的路由协议。详细阐明了路由算法的实现流程 和性质证明。 ( 4 ) 研究n s 2 仿真平台，将设计的路由协议在该平台上进行仿真，并和其他路由协 议在网络拓扑结构、功率、网络生存时间、能耗等多个方面进行对比实验，并分析实验 结果。 1 3 章节安排 本文第一章叙述了本学位论文的研究背景及意义，主要介绍了无线a dh o c 网络的 定义及研究现状以及能量节约的研究意义和难点，并对本文的研究工作和论文组织进行 了说明。 第二章介绍了a dh o c 网络的能量保护措施，例举了各协议层节约能量的手段，分 析了其性能，由此提出了跨层设计的最小能量路由协议的必要性。 第三章对拓扑控制机制进行了比较深入和全面的研究，给出了拓扑控制算法相关的 网络模型和能量模型，总结了现有拓扑控制算法的设计目标，重点研究了一种基于最低 能量路径的算法的原理和性质。对该算法在实际路由中的可行性和效率进行论证。 第四章针对第三章中原有最低能量路径算法的问题给出解决方案何改进措施，由此 提出了一种改进后的最低能量路径算法及其具体实现方法，并提出了基于此的路由改进 方案。 第五章研究并总结了现有的几种经典无线网络路由协议的原理和机制，给出了一种 可行的能量最优路径的附加路由方案，使得路由算法可以通过该方案达到对消息传输路 径上的能量优化。 第六章，在n s 2 仿真平台上实现本文设计的路由协议，在多个性能指标上进行了实 验，并对仿真结果进行了分析。 第七章对本课题所作的工作及实验结果进行了全面总结，并指出了尚待解决的问题 和今后进一步的工作方向。 最后，对本文成文过程中给予指导、协助和支持的组织和个人致谢。 5 2a dh o c 网络的能量保护策略硕上论文 2a dh o c 网络的能量保护策略 2 1a dh o e 各协议层能量保护策略的特点 a dh o c 网络协议设计是基于传统的分层结构的，作为今年来a dh o c 网络的一个研 究热点，目前已经针对各个网络层提出了多种提高能量效率的方法【1 0 1 。 2 1 1m a c 层能量保护 ( a p p l i c a t i o nl a y c r ) o i t e i i 疆t f t p j d 瞎h f t p ， ( t r a n s p o al a y e r ) t c p 叨p ( n e t w o r kl a y e r ) ：臼伊i j 工p ( n e t w o r ki n t e r f a c el a y c r ) 8 0 2 1 1 8 0 2 3 x ，x 2 5 ， 图2 1a d h 0 c 网络体系结构 研究表明为了减少能量的消耗，无线网络接口卡要尽可能地处于休眠模式。在此基 础上提出的基于休眠机制的m a c 层协议研究成为近年来a dh o c 网络能量问题研究的一 个热点。m a c 协议中能量保护策略最常用的手段是调度节点的休眠状态，以及对信道 接入协议进行改进，其中最具代表性的有i e e e8 0 2 。1 1i b s s ( i n f r a s t r u c t u r e l e s sb b s ) 功率 节省协议【l l 】、p a m a s ( p o w e ra w a r em u l t ia c c e s sp r o t o c 0 1 ) 协谢1 2 1 以及s p a n 协谢13 1 ，可 以建立有效的协调机制，尽量避免冲突、减少重传。 调度节点的休眠状态是功率管理的一种方式，主要适用于传感器网络，但对a dh o e 网络效果不甚理想( 对此，本文在2 2 1 节有详细说明) 。仅仅在m a c 层采用节点休眠 唤醒机制是无法满足节点分布规律复杂、移动频繁的a dh o c 网络。 2 1 2 网络层能量保护 网络层是a dh o c 网络中最重要的一层，其主要任务是邻居发现和实现路由协议。 路由请求报文、路由应答报文和路由出错报文等均在此层进行传输。大量具有a dh o c 特点的功能都要在网络层实现。a dh o c 网络路由协议设计需要考虑到能量利用率和负载 均衡。 6 硕f ：论文 一种基于最小能量路径的无线白纽网络路由协汉 能量利用律的路由算法有功率度量路由算法、能量度量路由算法和混合路由算法三 类。功率度量路由算法【1 4 】在路由选择时选取总的传输功率最小的路径，使得数据在该路 径上传输所需的功率是所有可选路径中最小的；能量度量路由【3 8 】算法主要考虑到均衡节 点能耗，路由时避免使用剩余能量低的节点，这样可以延长节点的平均生存时间；混合 度量路由是上述两种的综合考虑。 基于负载均衡的路由协议的主要思想是：如果所有报文都在某几条最优路径传输， 会造成该路径相关节点能量很快被耗尽的情况，于是在建立路由的过程中，同时建立多 条次优路径和概率模型，根据每条路径对应的概率值进行报文转发以初步实现网络负载 均衡，从而延长网络整体的生命期。根据源节点和目的节点之间的路由采用的路径数的 不同，可将现有的负载均衡路由协议分为单径路由协议、替代路径路由协议和多径路由 协测”j 。单径路由协议的业务流在一条路由上传输，多径路由协议可将业务流分配到多 条路由上同时传输，而替代路径路由协议则是添加冗余路径以增强路由的稳健性。总而 言之，负载均衡的主要思想是在路由选择时减少经过拥塞节点，或在多径路由存在的情 况下对负载进行合理分流，通过避开选择经过重负载中间节点的不利路由，使得网络中 负载分布均匀1 1 6 1 。 在m a c 层和网络层之间，有研究者提出一个“2 5 层”的概念【 】。该层的作用是 收集m a c 层和网络层的信息，通过改变发射功率来动态调整网络的拓扑结构，一般根 据节点的分布情况自动调节发射功率，有选择地与邻居节点建立通信链路。由于2 5 层 协议可比m a c 层或网络层协议得到更多的信息，所以在2 5 层采取一些节能机制在节 能的同时往往还可以得到更好的整体性能( 如时延、公平性等) 。路由协议在调整后的拓 扑上运行，这是优化网络性能，实现低冲突、低功耗、高吞吐率等的一种有效方法。 拓扑信息的来源不只是网络层，而拓扑结构的改变通常影响的也不只是网络层，因 此，本文提出一种广义上的拓扑控制。 2 1 3 传输层能量保护 传输层负责排序接收数据并将其送交相应的应用程序，检测分组的错误和重传分 组。通常，在传输层没有专门的节能措施，而总是通过其他层的设置，减少信息的重传 和控制报文的数量，降低能量的浪费，本文在设计算法时，也考虑到了此类因素。 2 1 4 应用层能量保护 应用层的关注重点是网络效率。目前a dh o c 网络要确保能够应用的q o s ，几乎是 不可能的。尽管链路层和网络层的自适应机制能够为应用提供一定的q o s 保障，但是这 种q o s 会随着信道条件、网络拓扑和用户要求的变化而变化，因此应用需要根据网络提 供的q o s 进行变化。节点的有限能量要求网络性能和网络寿命的折衷，这些折衷也是在 7 2a dh o c 网络的能量保护策略 硕1 ：论文 随着网络的变化而动态变化的。 应用层的节能协议【1 8 】主要关注多媒体处理和传输，因为它们需要消耗较多的能量， 常用的方法有：对多媒体数据进行编码压缩以减少字节数、在保证多媒体质量可以容忍 的范围内的前提下，适当地丢弃某些多媒体帧。字节的压缩不是a dh o e 网络的特有问 题，不在本文研究范畴。 a dh o c 网络的路由协议位于应用层，路由请求报文、路由应答报文和路由出错报 文等的传送，均通过u d p 协议及其下层的i p 协议进行，因此，路由协议设计本身就是 跨层的。 节点的能量和q o s 是一对矛盾体，通过拓扑控制、功率调节、休眠机制达到了降低 节点功率的目的，却不可避免地要破坏网络其他各方面的性能，比如传输时延、丢包率 等。如何协调网络能量和网络性能问题，是应用层要考虑的一个重要问题，因此，如果 在设计能量保护机制的同时不考虑服务质量的话，这样的机制是没有实际应用意义的。 2 2 常用的能量保护机制 功率管理和功率控制是两种常用的能量节约机制，前者通过被动地关闭无线网络接 口来节省能量，也称为被动能量保护机制，后者主动地对自身功率进行调节，也称为主 动能量保护机制【1 9 1 。 2 2 1 功率管理 功率管理( p o w e rm a n a g e m e n t ) 2 0 j 也称为节点休眠唤醒机制，即在保证网络的覆 盖度和连通性的前提下，使某些冗余节点进入休眠状态以节省能量。它主要基于以下考 虑：当网络中节点的密度达到一定程度时，不论从信息传输还是获取的角度来看，节点 的冗余对网络的能量消耗都带来非常不利的影响，因此通过功率管理策略将网络接口从 空闲状态转入休眠状态可以明显地节省能量的消耗。依照该机制，节点在空闲时设置为 休眠状态以节约能量，而在需要时唤醒以构成数据转发的拓扑结构。功率管理研究的重 点在于如何调度节点在休眠及唤醒状态间的转换，在基于分时复用的接入调度中，节点 之间保证严格时间同步的情况下，休眠问题很容易解决，但在竞争的方式下，不能保证 发送数据时目的节点处于活动状态。当前主要有三种解决方法：发送节点主动唤醒接收 节点，称为主动唤醒机制；发送节点等待接收节点的自动唤醒，称为等待机制；邻居节 点问协调唤醒休眠周期，称为同步机制。 功率管理可以在链路层和网络层上实施。在链路层，节点无数据收发或监听道信道 忙时，可以关闭无线网络接口，在需要时再重新唤醒；在网络层，可以选取部分节点形 成虚拟的骨干网，通过少数骨干节点完成整个网络的选路和数据传输，而另外一些节点 8 硕上论文 种基于最小能量路径的无线臼纽网络路由协议 可以进入休眠状态，当有通信任务时才将其唤醒。 功率管理在传感器网络中应用得比较岁2 1 】【2 2 】，其中许多策略都基于一个假设：节点 密度足够大，使得任何时候都只有少部分节点开机也不会影响通信及网络的连通。但是， 这可能不适用于无线a dh o e 网络，因为通常a dh o c 网络节点数比较少，不能达到足够 大的密度，在节点稀疏区域关闭节点将会不能保证网络的性能甚至使得网络分割；另外， 在无线a dh o c 网络应用场景中，节点的频繁移动使得其担任的业务及所处的通信环境 在不断地变化，如果采用节点休眠唤醒机制将会使得节点不断地在各种状态间转换，反 而浪费了计算丌销，增加了拓扑管理的复杂性。因此，功率管理一般不适用于无线a dh o c 网络。 2 2 2 功率控制 功率控$ 1 j ( p o w e rc o n t r 0 1 ) 2 3 是在维护网络连通性和覆盖度的前提下，调整节点的发 射功率，以减少不必要的能量消耗，延长节点生存时间，提高信道的空间复用度，降低 对邻居节点的干扰，提高网络的容量。目前功率控制技术一般在链路层和网络层上实施。 链路层的功率控制一般通过m a c 协议来完成，主要方法是通过利用冲突避免类型协议 中的r t s c t s 控制信息来获取链路有关的参数信息，节点根据到报文的下一跳节点的 距离、信道状况等条件动态地调整发射功率。具体过程为：发送节点在r t s 中带上发射 功率等参数信息，接收节点根据r t s 的接收强度以及其中携带的参数信息来决定本节点 发送响应报文( c t s 、a c k ) 时所需的功率，响应报文中可以附带本节点的信噪比等信 息。一般来说，链路层的功率控制中，控制报文和广播报文可以用最大功率发送，而数 据分组、a c k 可根据控制信道上交互的信息以最小必需功率发送。链路层的功率控制 是经常性的，每发送一个数据报文都有可能要进行功率控制。事实上，实时的、连续功 率调节的理论模型在实际应用中是不可达到的，这造成了链路层上功率调节应用的局限 性。 网络层的功率控制所关心的问题是如何通过改变发射功率来动态调整网络的拓扑 结构，一般根据节点的分布情况自动调节发射功率，有选择地与邻居节点建立通信链路。 路由协议在调整后的拓扑上运行，这是优化网络性能，如低冲突、低功耗、高吞吐率等 的一种有效方法。相对于链路层的功率控制，网络层的功率控制要在较长的时间内才进 行一次，调整频率比较低。后面我们提到的功率控制一般是指网络层的功率控制。 如果说功率管理更多关注的是有效节约节点冗余能耗的话，那么功率控制是在节约 能耗的基础上关注网络的整体性能。在发送代价较大的a dh o c 网络中，采用功率控制 机制可以有效节约宝贵的能量资源，同时因为功率控制能减少节点间的相互干扰，使得 单位面积内能同时通信的节点对增多，因此能够提高网络的通信容量。本文所采用的算 法就是一种基于功率控制的拓扑之上的单径路由算法。 9 2a dh o c 网络的能量保护策略 硕j ：论文 2 3 基于跨层协同的功率控制系统构架 a dh o c 无线网络无中心控制节点，传统的集中控制模式显然无法适应该网络的需 求，而分布式控制增加了网络的复杂性和节点的处理负担【2 4 。a dh o c 无线网络必须采用 特殊的方法减少节点资源的消费，适应网络控制算法的复杂性。 如前文所述，不论逻辑上是否直接相邻，移动a dh o c 网络每一个协议层的功能都 是互相关联的，链路层需要在当前信道和网络状况下通过调节速率、功率和编码来满足 应用的需要：路由协议需要根据当前的链路网络和通信状况自适应；应用层应根据下面 任意一层的状态利用软q o s 得到最高的应用质量。另一方面，每一个协议层面对着同样 的能量约束问题，传统的分层协议栈只能在某一层对能量保护得到局部的解决和优化。 由于局限于某一层的能量保护方案的狭隘性，事实上网络的的能量管理无法由某一层单 独来实现，需要整个协议栈中不同的层协作来完成，同时，网络中节点间相互协作也需 要应用跨层设计技术提高效率【2 引。 l i 等证明了最小能量路由是n p 完全问题【2 6 1 。本文提出一种跨层设计的路由算法， 以支持多层联合能量优化和白适应。该算法运行在最小能量拓扑之上，结合现有的经典 路由算法，实现了可应用于实际中的最低能量路径路由的次优方案。该方案的构架如图 2 2 所示。 l o 图2 2 基丁跨层协同的能量保护构架 硕1 ：论文一种皋于最小能量路径的无线白纽网络路由协议 3 最小能量特性的拓扑控制 3 1 相关概念及模型 3 1 1 无线自组网相关定义 ( 1 ) v = v l ，v 2 ，v 3 ，v n ，表示网络中节点的集合。 ( 2 ) e 表示网络中边的集合。 ( 3 ) 定义节点v 的最大传输半径用r ( v ) 表示，当前传输半径用r ( v ) 表示。 ( 4 ) d ( u ，v ) = l u v l 表示从节点u 到节点v 的欧几罩德距离。 ( 5 ) e ( ) 表示节点u 的边集。 ( 6 ) e ( u ，v ) 表示连接u 、v 两点的边，e ( u ，v ) 和e ( u ，v ) 在e 中等价。 ( 7 ) 一个图g 定义为一个二元组g = ( ve ) ，其中v ( 或v ( g ) ) 是顶点集，e ( 或e ( g ) ) 是边集。图g 的顶点数用i v i 表示，边的数目用l e | 表示。一个具有i v l 个项点的图称为n 阶图。如果顶点v 是边e 的一个端点，则称边e 和顶点v 相关联( i n c i d e n t ) ；若( “，1 ，) e ， 则称u 和v 是邻接( a d j a c e n t ) 的。 ( 8 ) 对于图g 和h ，如果v ( h ) c v ( g ) ，e ( h ) e ( g ) ，那么称h 是g 的子i 羽( s u b g r a p h ) 记作h c - g 。若子图h 满足v ( h ) = v ( g ) 且e ( h ) c e ( g ) ，则称h 为g 的生成子图。 ( 9 ) 若一条途径上除了起点和终点可能相同外。所有顶点均不相同( 所有边也必然都 不相同) 的途径称为路径( p a t h ) 。一条闭路径称为圈( c y c l e ) 。 ( 1 0 ) 设u ，v 是图g 中的两个顶点，若在g 中存在一条( u ，v ) 路径，则称顶点u 和v 是连通的( c o n n e c t e d ) 。如果图g 中每一对不同的顶点u ，v 都有一条( u ，v ) 路径，则称图g 是连通的。 ( 11 ) 可见邻居孵是u 使用它的最大发射功率能够达到的节点的集合， n ：2 vv ( g ) l ( u ，v ) e ( g ) ) 0 2 ) 节点v 是节点u 的邻居，记为甜一v ，当且仅当e ( u ，v ) e ( l ) 。无线a dh o e 网络中节点v 是节点u 的邻居的条件是：d ( u ，v ) “u ) 。 ( 1 3 ) 若存在e ( u ，v ) e ( 瓦) ，且存在e ( v ，u ) e ( 瓦) ，则称节点u ，v 之间存在一条双 向链路，也称双向边：若存在e ( u ，1 ，) e ( 瓦) ，但不存在e ( u ，1 ，) ( 瓦) ，则称节点u ，v 之间存在一条u 到v 的单向链路，也称单向边。 ( 1 4 ) a dh o c 网络中u d g ( u n i td i s kg r a p h ) 图的定义是：当且仅当图中的两个点之间 的距离小于或等于源节点v 最大发射功率勰( v ) 对应的最大发射半径为r ( v ) 时，这两 3 最小能量特性的拓扑控制 硕上论文 点可通过一条边相连。记所得的图为g ( y ) = g ( y ，e ) ，e2 ( ”，v ) ld ( 甜，v ) r ( “) ) 。 3 1 2 网络模型 v = v iv 2o g n ) 为a dh o c 网络中节点集，假设所有节点均匀分布在一个二维平面 上，每个节点被分配一定的功率，节点的发射半径由其功率及路径损耗模型和信噪比决 定，两个节点问能否直接通信取决于是否相互处于对方的信号覆盖范围内。 假设如下条件： ( 1 ) 每个节点被赋予了一个唯一的标号i d ，取值区间为【1 n ，n = i v i ； ( 2 ) 节点以全向天线收发数据包； ( 3 ) 无线信道不考虑地理因素、网络环境中无障碍： ( 4 ) 每个节点可通过g p s 定位系统获得自己的位置信息； ( 5 ) 所有节点具有相同的最大发射功率，表示为戤，并且可以动态调整自身发射 功率，即可在【0 ，】之间连续调节。 a dh o c 网络通过二维平面上的单位圆图( u d g u n i td i s kg r a p h ) 来建模。如图3 1 所示，节点集v = a ，b ，c ，d ) ，根据节点之间的距离和发射半径，可以得出可以互相 直接通信的节点对，也即该节点的u d g ( v ) 图的边集为e = ( a ，b ) ，( a ，c ) ，( b ，c ) ，( a ， d ) ，( d ，e ) ) 。由条件( 5 ) 可知，u d g 图中的边都是双向边。 图3 1u d g 模型 在a dh o c 网络中，节点u 发送的信号节点v 可以j 下确接收则称u 可达v ，两个节 点u ，v 间存在双向链路的条件是u 和v 相互可达，若u 可达v 而v 不可达u 则u 到v 产生了一条单向链路。如果网络中各节点的功率不全相同，则有可能出现单向链路，拓 扑控制的结果是让每个节点以自己需要的功率传输信号，因而会带来单向边的问题，现 有的大部分拓扑控制算法都不考虑单向链路的问题，或者直接假设去掉所有单向链路后 拓扑图仍是连通的，对于不考虑单向边问题对算法实际结果带来的影响本文有详细的讨 论。本文设计的算法建立在承认单向链路的存在之上。 1 2 硕j ：论文一种基于最小能量路径的无线白纽网络路由协议 3 1 3 能量模型 a dh o c 网络中，节点的能耗主要来源于通信能耗，即数据发送、接收的能耗。节 点需要发送控制消息包、本地数据包和其它节点发来的中继数据包，接收控制消息包、 目的为自身的数据包和目的为其它节点的中继数据包。另外在基于竞争的信道接入机制 中，还有部分能量消耗在空闲状态下的信道侦听和数据包碰撞过程中。一般的无线网卡 有发送( t r a n s m i t ) 、接收( r e c e i v e ) 、空闲( i d l e ) 和睡眠( s l e e p ) 四种工作模式，其中 前三种模式都会消耗能量，发送状态具有较高的能耗，但睡眠模式的能耗远小于前三种 模式。节点的能量消耗取决于工作模式所需功率及持续时l 百j 1 2 7 】： e m = e 中+ e 七e t 如l = p 【rx t 涫七p 唧x t 唧+ p m lx l j 出t q ? b 其中，办、耽、，分别为发送、接收、空闲侦听的功率，f f ，、t 一分别三种 工作模式所持续的时间。根据参考文献 2 8 】，空闲状态与接收状态的能量消耗非常接近， 因此节点在接收一个分组时与空闲状态相比并不会给节点本身带来很大的额外能量消 耗，所以本文中不考虑节点接收分组的能量消耗，也即假设节点仅仅在发送或转发分组 时其能量才会减少。后面提到的节点功率即节点的发送功率陬，简单地，用p 表示。 a dh o c 网络中，节点的无线通信范围与无线电发送设备的发送信号强度、无线接 收设备的接收能力、环境的干扰因素有关。在没有任何环境干扰的理想状况下，节点的 发送信号强度