（计算机应用技术专业论文）基于网络生存时间的ad+hoc网络节能路由研究.pdf

摘要 在移动终端电池能量有限的无线a dh o e 网络中，设计一个能量有效的延长 网路生存时间的节能路由协议已经成为当前研究的重点和热点。目前提出的节能 协议大都基于理想的无线信道模型，能量代价函数也不考虑可靠链路层的重传耗 能问题。一些协议片面地追求总能量消耗最小化或网络生存时间最大化，部分协 议即使综合考虑将这两方面，也只是涉及到节点的剩余电池能量，并没有综合考 虑节点的耗干率，从而在网络负载比较大时，可能由于能量消耗速度过快而导致 节点甚至网络的瘫痪。 针对可靠链路的重传耗能问题，本文提出了一种基于表驱式路由的综合考虑 总能量消耗最小和剩余电池能量的节能路由协议r e a r p 。该协议在衡量节点能 量代价时，若节点的剩余电池能量大于阂值，代价函数只考虑总能量消耗；反之， 还要考虑剩余电池能量的影响。同时，该协议还通过动态功率控制d p a 算法选 择每一跳的最优发送功率，使得每一跳总能量消耗和路由总能量消耗都达到最 小。仿真结果表明，与d s d v 协议相比，r e a r p 协议能延长网络的生存时间， 降低每个包的总能量消耗，有效地节省能量。 基于r e a r p 协议的按需式路由版本r e a r po d 协议，本文提出了一种综 合考虑总能量消耗最小，剩余电池能量和节点耗干率的节能路由l t e u r 。该协 议在考虑节点能量代价时，利用节点的剩余电池能量和耗干率预测在当时能量消 耗速度下的节点生存时间。当生存时间大于阈值时，代价函数只考虑总能量消耗 部分，否则，还要考虑节点生存时间的影响。仿真结果表明，与r e a r po d 协 议相比，在网络负载比较大的情况下，l t e u r 协议能够有效地均衡负载，延长 网络的生存时间，提高能量的有效性。 关键词：无线a dh o c 网络节能路由网络生存时间功率控制能量有效 a b s t r a c t h o wt od e s i g na l le f f i c i e n te n e r g y - a w a r er o u t i n ga l g o r i t h mh a sb e c o m eah o t t o p i ci nt h er e s e a r c ha r e ao fm o b i l ea dh o cn e t w o r k s ( m a n e t ) i nm a n e t , t h e e n e r g yl i m i t a t i o no fm o b i l en o d e sa l w a y sr e s u l t si np o o rn e t w o r kp e r f o r m a n c e t o l e n g t h e nn e t w o r k l i f e t i m ea n di m p r o v et h ep e r f o r m a n c e ，s o m ee n e r g y - a w a r e p r o t o c o l sh a v eb e e np r o p o s e d h o w e v e r , m o s to f t h e mb a s eo ni d e a lw i r e l e s sc h a n n e l a n di g n o r et h ee n e r g yc o n s u m e db yt h em a cl a y e rr e t r a n s m i s s i o n m o r e o v e r ，t h e s e p r o t o c o l so n l yd e p e n do nr e s i d u a le n e r g yi n s t e a do fd r a i nr a t e ，a n da i ma te i t h e r m i n i m i z i n 。gt o t a le n e r g yc o n s u m p t i o no rm a x i m i z i n gn e t w o r kl i f e t i m e t h e r e f o r e ，t h e p e r f o r m a n c eo ft h e s ep r o t o c o l sm a y b ep o o rw h e nt r a f f i cl o a di sh e a v y i nt h i st h e s i s ，w ep r o p o s e da l le n e r g ye f f i c i e n tr o u t i n g p r o t o c o lc a l l e dr e a r p r e a r pw a sd e s i g n e db a s e do nt a b l e d r i v e nr o u t i n gd s d v , w h i c ha i m e dt om i n i m i z e t o t a le n e r g yc o n s u m p t i o na c c o r d i n gt or e s i d u a lb a t t e r y w h e nt h er e s i d u a le n e r g yw a s m o r et h a nat h r e s h o l d ，r e a r po n l yf o c u s e do nm i n i m i z i n gt o t a lt r a n s m i s s i o np o w e r o t h e r w i s e ，t h en o d e sw h i c hh a dh i g h r e s i d u a l e n e r g yw o u l db e s e l e c t e d a s i n t e r m e d i a t en o d e s t om i n i m i z et h et o t a lt r a n s m i s s i o np o w e r , r e a r pa d o p t e da d y n a m i cp o w e rc o n t r o la l g o r i t h mt o d e t e r m i n et h eo p t i m a lt r a n s m i s s i o np o w e r m a s s i v es i m u l a t i o nr e s u l t ss h o w e dt h a tr e a r pc o u l ds i g n i f i c a n t l yl e n g t h e nt h e n e t w o r kl i f e t i m ea n dd e c r e a s et h et o t a le n e r g yc o n s u m p t i o n b a s e do nr e a r p , w ep r o p o s e da n o t h e re n e r g y - a w a r er o u t i n gp r o t o c o ln a m e d l t e u r l t e u rw a sd e s i g n e dt om i n i m i z et h et o t a le n e r g yc o n s u m p t i o na c c o r d i n gt o r e s i d u a le n e r g ya n dd r a i nr a t e t h i sr o u t i n ga l g o r i t h mu t i l i z e dt h er e s i d u a le n e r g ya n d t h ed r a i nr a t et op r e d i c tt h er e m a i n i n gn o d el i f e t i m e s i m i l a rt or e a r p , t h i sp r o t o c o l o n l yf o c u s e do nt o t a le n e r g yc o n s u m p t i o nw h e nt h en o d el i f e t i m ew a sl a r g e rt h a nt h e t h r e s h o l d o t h e r w i s e t h ei n f l u e n c eo ft h el i f e t i m ew a st a k e ni n t o c o n s i d e r a t i o n c o m p a r e dw i t hr e a r p , l t e u rc o u l de f f e c t i v e l yb a l a n c e t h et r a 仟i cl o a da n d l e n g t h e nt h en e t w o r kl i f e t i m e t h es i m u l a t i o nr e s u l ts h o w e dt h a tl t e u r c o u l do b t a i n b e t t e rp e r f o r m a n c ew h e nt r a f f i cl o a dw a sh e a v y k e yw o r d s ：w i r e l e s sa dh o cn e t w o r k s ，e n e r g y - a w a r er o u t i n g ，n e t w o r k l i f e t i m e ，p o w e rc o n t r o l l ，e n e r g ye f f i c i e n t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位蝴：小、 替醐：1 年日 学位论文版权使用授权书 本学位论文作者完全了解墨盗盘鲎有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 签字日期： ：乃毯占l 年。月 2 只 铬芡忝 导师签名： 磐脯：1 “肫日f 第一章绪论 第一章绪论 1 1 无线a dh o e 网络节能机制 无线a dh o c 网络是一种没有基础设施的多跳移动自组织网络。在该网络中， 每个节点既可以作为源和目的节点发送和接收数据，同时又可以作为路由器转发 来自邻居节点的数据包。所有节点地位平等，无中心主机，因此具有很强的抗毁 性，能够随时随地为我们搭建一个临时的网络通信环境，不仅可以应用于军用领 域如战争，还可用于灾难恢复、紧急通信等民用领域。但无线a dh o c 网络中的 每个节点都是由电池供电的，而电池只能提供有限的能量】，由于能量耗竭而引 起的某个关键节点的失效会导致整条路径的中断，甚至会引起网络的分割而从而 导致整个网络的瘫痪，这将大大缩短了整个网络的生存时间，降低了网络的服务 质量。因此，在无线a dh o e 网络中，如何有效地节能从而延长节点和网络的生 存时间，成为一个备受关注的焦剧2 1 。能量的消耗涉及到了无线a dh o c 网络中 的各个层面，包含物理层、数据链路层、网络层、传输层和应用层，因此针对各 种不同层面的节能机制也相应的被提出。 1 1 1 物理层节能机制 表面上来看，节点的通信能量消耗主要花费在物理层的硬件网卡上，所以过 去人们一直关注研究物理层的节能机制。物理层的节能策略主要集中在两个方 面：电池容量的增大和节点能量消耗的降低1 3 j 。长久以来，制造技术方面的限制 使得电池技术很难有较大的突破，单位重量的电池容量并没有获得本质的增多， 因此，依靠电池容量的增大来达到节能的策略不容乐观。物理层的节能策略主要 集中在降低节点的能耗方面。目前关于此方面的方法和技术已经被提出并趋向成 熟，如采用支持s p i n d o w n 模式的磁盘，使用快速的存储设备f l a s h 闪存i 4 | ，应用 不同时钟频率的c p u t5 1 ，设计节能的c m o s 数字电路【6 j 等。 以上提到的方法都是只涉及到物理层，还有一类方案是和其它协议层如 m a c 层或网络层进行跨层优化以达到降低能耗的目的，这就是功率控制方法。 在这种策略中，节点在发送数据包之前先根据信道的噪声和干扰，通过某种算法 调节网卡的发送功率，这个功率不仅保证目的节点能够刚好正确接收数据包，即 接收功率和接收信噪比同时达到闽值的要求，同时还不会对网络中的其它节点造 第一章绪论 成千扰。功率控制方式有两种，基于g p s 的功率控制和基本的功率控制。前者 要求节点能够通过g p s 获得其它节点的地理位置信息，然后根据位置信息确定 发送功率，使得数据能够刚好正确的被接收，在基于c s m a c a 的数据链路层中， 这种方式不仅能够降低节点的能耗，还能提高无线信道的利用率，但可能会带来 信道访问冲突的问题，同时g p s 也会消耗一定的能量。后者是在节点不能获得 其它节点的位置信息的情况下，以最大功率来发送控制包，根据控制包的发送和 接收功率以及信噪比来确定数据包的发送功率，这种机制下，信道利用率不如前 者，但是可以避免信道的访问冲突。 1 1 2 数据链路层节能机制 数据链路层包括媒体介入控制子层m a c ( m e d i u ma c c e s sc o n t r 0 1 ) 和逻辑 链路控制子层l l c ( l o g i c a ll i n kc o n t r 0 1 ) 。前者位于数据链路层的下半部分， 负责控制与连接物理层的物理介质，判断何时发送数据并进行信道分配【7 1 ，为物 理层协议提供上层可靠保证；后者进行数据包的分段和重组，流量控制，帧同步 等。目前针对m a c 层的节能策略主要有以下几种： ( 一) i e e e8 0 2 11m a c 节能模式 i e e e8 0 2 1 1 jm a c 有两种工作模式：功率节省模式p s m ( p o w e r - s a v i n g m o d e ) 1 9 】和活动模式a m ( a c t i v em o d e ) ，这两种模式是可以互相转换的。p s m 模式的工作机制如下：p s m 以若干连续的固定长度的b e a c o n 为单位，将时间分 为若干周期，在一个b e a c o n 周期开始时，所有设置为p s m 的节点都会在一个被 叫做a t i m ( a dh o ct r a f f i ci n d i c a t i o nm e s s a g e ) 窗口的时间内，一直保持活跃状 态。在a t i m 窗口内，如果节点有数据包要发送，就首先通过r t s c t s 的方式 竞争信道，接着发送a t i m 包，目的节点收到a t i m 包后，会反馈一个a t i m a c k 包给源节点，这样就完成了一个a t i m 握手的过程。所有在a t i m 窗口内完成 a t i m 握手过程的节点将在整个b e a c o n 周期内一直处于活跃状态，未完成握手 过程的节点在a t i m 窗口内处于活跃状态，但a t i m 窗口结束后就进入休眠状态 以减少能耗。活跃的节点将在a t i m 窗口结束后，以r t c c t s d a t a a c k 的方 式进行收发数据。p s m 的缺点在于它的a t i m 窗口大小是不变的，不能根据网 络负载动态的进行调整。当网络负载比较轻的时候，大部分节点不会进行a t i m 握手过程，但在a t i m 窗口内一直处于活跃状态，只有在a t i m 窗口结束后才能 进行睡眠，不利于节能：而当网络负载很重的时候，很容易导致有通信需求的节 点在a t i m 窗口内a t i m 握手失败，不得不进行休眠，严重降低了投递率。 第一章绪论 ( 二) e c m a c 协议 e c m a c ( e n e r g yc o n s e r v i n gm e d i u ma c c e s sc o n t r 0 1 ) 【1 0 】是一种特殊的应用于 w l a n 的m a c 层协议，设计它的主要目的就是节能，虽然w l a n 和a dh o c 网络有很多不同，但这种节能思想是对a dh o c 网络的节能，是有一定借鉴意义 的。 ( 三) p a m a s 协议 p a m a s ( p o w e ra w a r em u l t i 。a c c e s sp r o t o c o lw i t hs i g n a l i n gf o ra dh o c n e t w o r k s ) i i 】协议是由s i n g h 等人专门为a dh o c 网络节能设计的一种m a c 层 协议，该协议在传统的m a c a 基础上利用一个独立于数据信道的控制信道来实 现节能的目的。当节点既没有数据要发送也没有数据要接收时，就会智能地关闭 网卡接1 2 1 以节省能量。在这个独立的控制信道上能够传输诸如r t s 、c t s 、b u s y t o n e 等控制信号，从而可以使节点能够决定将网卡关闭的时刻以及休眠多长时 间等。当源节点在控制信道上向目的节点发送一个r t s 后，如果有邻居节点正 在数据信道上进行数据的发生或接收，那么邻居节点就立即给控制信道发一个 b u s yt o n e ，这个b u s yt o n e 的长度要大于目的节点发送的c t s ，源节点收到b u s y t o n e 后，就不会在控制信道上接收由目的节点发送的c t s ，同时也不会在数据 信道上发送任何数据。仿真和实验表明，p a m a s 协议动态关闭无线网卡以处于 睡眠状态的方式不仅大大降低了能量的消耗，同时也不影响协议的其它性能指标 如投递率和延迟等。 ( 四) p c m a 协议 在基于能量管理的c s m a c a 信道接入模式中，r t s 和c t s 用来预留信道， 收到r t s 或c t s 的非源非目的的节点会通过关闭无线网卡进入休眠状态用来减 少节点能耗。如果每个节点的功率是可调整的，这种节能机制会严重降低无线信 道的利用率，m o n k s 等提出了p c m a ( p o w e rc o n t r o l l e dm u t i p l ea c c e s s ) 1 2 1 协 议。在该协议中，控制信道和数据信道也是分开独立的，同时r t s 和c t s 分别 被r p t s ( r e q u e s tp o w e rt os e n d ) 和a p t s ( a c c e p t a b l ep o w e rt os e n d ) 所代替， 控制信道能够传输控制信号如r p t s ，a p t s ，b u s yt o n e 等，如果节点收到了r p t s 或a p t s ，并不是盲目地将网络接1 2 1 关闭，而是根据控制信道上的b u s yt o n e 强 弱，也就是当前数据信道上正在进行的数据传输所能容忍的噪音余额，用来调整 该节点的发送功率，该功率不能对正在进行的数据传输造成干扰，然后开始发送 第章绪论 数据。如果以上过程成功完成，就可以进行数据传输，否则就关闭无线接口。因 此p c m a 在节省能量消耗的基础上，还能够有效提高无线信道的利用率，大大 改善了系统的投递率。 ( 五) 其它m a c 层节能协议 c h e n 1 3 等人提出了一种基于网络拓扑维护与协调的能量感知的m a c 层协 议，在该协议中，节点睡眠与否是由邻居节点的稀疏程度来确定的。仿真表明， 该协议能够在维护一定q o s 如系统投递率和网络连通性的前提下，明显降低能 量的消耗。 针对l l c 层的节能方案主要有： 逻辑链路控制子层的节能机制主要体现在尽量减少重传的次数方面，这会涉 及到差错控制中的自动重传请求( a u t o m a t i cr e p e a tr e q u e s t ) 1 1 4 l 。当前提出的节 能协议中，自适应差错控制自动重传请求机制( a d a p t i v ee r r o rc o n t r o lw i t ha r q ) i l5 】是在自动重传请求基础上对差错控制进行改进，使之能够自适应的进行差错控 制，从而减少重传的次数。基于a r q 和f e c 的自适应差错控制【1 6 】综合考虑了目 前的信道情况，为特定的连接要求提供一个最佳的能量效率。自适应功率控制编 码协测7 】是对系统的投递率，电池的生命周期和信道状况进行分析并合理的调 整，用来节省能量。 1 1 3 网络层路由节能机制 a dh o c 网络中，节能路由协议的研究是节能机制中的关键部分，目前已经 提出很多能量有效的路由算法及协议。传统的a dh o c 路由只是考虑延迟这一指 标，所寻找的路径是从源节点到目的节点跳数最少也就是延迟最小的路由，这就 使得每一跳的发送功率很大，从而造成能量的过度消耗。而且由于传统的路由算 法也不考虑节点的剩余能量以及能量消耗情况，所有的数据包均选择该路径进行 传播，可能导致该路径上的某个关键节点过早的耗尽能量，从而导致节点甚至整 个网络的瘫痪。而节能路由算法一般都是提出了一个新的节点代价函数和路径代 价函数，这些代价函数一般不考虑跳数，而是基于节点的能量或功率信息。节能 路由算法按照代价函数一般分为两类，即最小化总能量消耗和最大化网络生存时 间，部分算法将两类代价函数结合起来进行衡量，还有其他解决方案比如最小化 路由协议的开销，路由可靠性等。关于本部分内容，1 2 节会进行详细介绍。 第。章绪论 1 1 4 传输层节能机制 传统的t c p 协议在有线网络中性能很好，但并不直接适应于无线网络，因 为无线信道容易受路径衰减，阴影衰减，多径衰落，噪声干扰等的影响，使得无 线信道的带宽比有线信道要低很多，而无线信道的误码率比有线信道要高很多， 所以，t c p 在无线网络中，由于高误码率而导致数据包的大量重传，从而使得链 路冲突更加频繁，大大消耗了能量资源。目前的无线传输层协议一般都是在传统 的t c p 如t a h o e ，r e n o ，n e wr e n o 等基础上，综合考虑无线环境的特点和节点 的能量消耗代价函数，进行了不同程度的改进以适应于无线环境。这些改进的协 议包括m t c p 18 1 ，i n d i r e c t t c p 1 9 1 ，s n o o pm o d u l e 2 0 1 等。t c p p r o b i n g 2 1 1 是一种 采用探测方法的t c p 协议，当数据包的丢失或者超时被节点发现后，不是像传 统t c p 那样立即进行拥塞控制，而是发送两个探测包进行探测。如果这两个探 测包被成功接收，说明数据包的丢失或者超时不是由网络拥塞导致的，而是由其 他因素如干扰噪声等无线环境造成的，这时节点就可以继续传输数据；相反如果 探测包丢失，就进行拥塞控制。还有一种协议是专门针对无线环境而提出的传输 层协议如w w p ( w a v ea n dw a i tp r o t o c 0 1 ) 1 2 l j 协议，具有比较高的能量效率。 1 1 5 应用层节能机制 应用层位于t c p i p 协议栈的最上层，它同时负责对各种数据流进行分类。 在a dh o e 网络中，为了使移动节点提高能量消耗效率，目前在应用层已经有多 种方法被提出【2 2 】，比如对数据流进行自适应的压缩编码，这种压缩编码机制能够 随着当前节点的能量变化和无线信道的变化而自动调整，从而减少了能量的消 耗。还有一种称为复合分散算法的应用层节能协议 2 3 j ，它是将无线终端的计算任 务分离出来，交给一个类似于基站的中心节点完成，中心节点任务完成后会将计 算结果反馈给无线终端，从而降低了无线终端的能量消耗。 1 2 无线a dh o c 网络节能路由概述 1 2 1 无线a dh o e 网络路由问题 目前适应于a dh o e 网络的路由协议一般分为三类：表驱动路由( t a b l e d r i v e n ) ，也被称为先应式路由( p r o a c t i v e ) ；按需路由( o nd e m a n ) ，也被称为 反应式路由( r e a c t i v e ) ；混合式路由( h y b r i d ) 。 表驱动路由一般是基于无线a dh o c 网络特性，对有线的路由协议进行改进 而得到的。这类路由的特点是，网络中每个移动终端都实时地精确地维护一张全 第一章绪论 局路由表，该路由表包含了到网络中其它任何节点的路由信息。当需要发送数据 时，查找路由表可以立即获得一条路由进行传输，不必等待查找建立路由的时间， 没有延迟，但是为了维持精确实时的路由表，各个节点需要周期性地向邻居节点 广播路由更新包，而无线带宽是非常有限的，这些更新包会占据很多带宽，也会 消耗节点有限的能量资源。同时，无线a dh o c 网络中节点移动速度快，网络拓 扑变化迅速，不仅需要频繁的广播更新包，而且新建立的路由很容易会马上失效。 所以在无线a dh o c 网络中，表驱动路由并不是很适合。典型的表驱动路由是 p e r k i n s 等提出的d s d v ( d y n a m i cd e s t i n a t i o n s e q u e n c e dd i s t a n c ev e c t o r ) 。该协 议在b e l l m a n f o r d 算法的基础上，主要利用目标节点确定的序列号来对路由进行 标识，从而不会造成回路。 和表驱动路由不同，按需路由是当节点有数据要发送，而路由缓存表中暂时 没有到目的节点的路由时，源节点就会首先触发路由查找过程，将最新获得的路 由添加到路由缓存表中，再进行数据的传输。节点间不需要周期性地广播路由更 新包，这能够大大减少无线带宽的消耗，由于无线网络的拓扑变化很快，路由缓 存表会周期性地对路由表项进行无效化标记并从缓存中清除，因此所建立的路由 都是基于网络最新拓扑。按需路由会造成由路由建立而带来的延迟，同时，新建 立的路由只是全局拓扑中的一部分，并不一定是最优路由。典型的按需路由协议 有d s r l 2 4 j 和a o d v l 2 5 j 等。 随着网络规模的扩大和节点移动速度的变快，表驱动路由没有较好的可扩展 性，周期性的路由更新包会占据大量的带宽，但是它维护的是全局路由信息，发 送数据时不会引进延迟，而按需路由虽然不必占用带宽和能量资源去维护无用的 路由，但是发送数据时会带来不可预测的延迟。因此，混合式路由协议应运而生， 最著名的足i - l a s s 等人提出的z r p ( z o n er o u t i n gp r o t o c 0 1 ) 1 26 l ，该协议规定每个 节点维护一个以自己为中心某个跳数范围之内的局部区域，区域内使用表驱动路 由，时刻维护着路由信息以便无延迟的发送数据，区域外采用按需路由，用来减 少协议的代价，从而达到更好的性能。 1 2 2 无线a dh o c 网络节能路由分类 传统的无线a dh o c 网络路由协议无论是表驱动还是按需路由，在寻找路由 时，均不考虑传输数据包的能量消耗，也不考虑节点的剩余能量情况和能量消耗 速度，最终所寻找的路由是从源节点到目的节点延迟最小也就是总跳数最小的路 由，这就使得每一跳所需要的传输功率一般都很高。对于能量资源有限的无线移 动终端来说，这种以延迟作为路由代价函数的方式很容易耗尽节点的能量，从而 导致节点甚至整个网络的瘫痪。因此，设计节省能量的路由协议就变得非常重要。 第一章绪论 目前基于节能的路由协议的路由代价函数可以分为两大类：总能量消耗的最小化 和网络生存时间的最大化。 总能量消耗的最小化指的是，在所有可选路径中，寻找从源节点到目的节点 传输一个数据包所消耗的总的能量最小的那条路由作为最终路径，这个总能量包 含从源节点经过中间转发节点一直到目的节点发送一个数据包所消耗的能量之 和，而每个节点所消耗的能量既有发送数据所消耗的传输功率，也有接收数据包 所消耗的接收功率。这种节能机制趋于寻找更多跳数而不是最小跳数的路由。 s i n g h 等最早提出关于最小化总能量消耗的节能路由算法。m e r ( m i n i m i z e e n e r g yc o n s u m e d p a c k e tr o u t i n g ) 【2 7 是该种机制中的一个基本算法，该算法工 作原理是以传输功率作为节点代价，以路径中各个节点的传输功率之和作为路由 代价，在所有可选路径中选择路由代价最小的路由。该机制的另外一种算法是 m t p r ( m i n i m u mt o t a lt r a n s m i s s i o np o w e rr o u t i n g ) 2 8 1 ，该算法也是在所有可选 路径中，以传输功率为节点代价，寻找总传输功率最小的那条路由。具体考虑两 种情况，传输功率是固定的和传输功率是动态可调整的。当传输功率是固定的情 况下，中间节点为转发一个数据包所消耗的能量包括发送功率，接收功率，以及 广播和丢弃所消耗的功率，用公式( 1 1 ) 表示： 目阳础砑) = 6 半】a c k e t s z e + c ( 1 1 ) 系数6 代表与包长度有关的能量消耗，c 代表固定的代价如竞争信道和m a c 层控制协商所消耗的能量，路径选择依赖于包的大小。 当传输功率是动态可调整时，这种情况被研究地更为广泛。在调整每一跳的 传输功率时，可以基于g p s 进行功率调整，也可以基于基本的功率调整，前者 根据g p s 提供的位置信息计算节点之间的距离，然后根据距离和无线信道情况 计算需要调整的发送功率，但g p s 本身会消耗一定的能量，后者不需要g p s 的 辅助，但需要控制包以最大功率来发送，以便根据最大功率，接收功率和接收信 噪比来调整数据包的发送功率。 另外一种基于总能耗最小的节能路由是p a r o ( p o w e r - a w a r er o u t i n g o p t i m i z a t i o n ) 1 2 9 j ，它是由b a n e r j e e 等人提出的。该协议工作如下：首先假设源 节点和目的节点是可达的，此时的总能耗必定不是最小，如果有其他节点进行转 发数据包，并且该节点加入后的路由的总能耗变小，则该节点就被加入到路由中， 这样反复循环，直到要添加的节点不能再使总能耗变小为止，迭代过程结束。该 算法有一个前提就足要求网络中的任何节点互相之间都是可直通的。 总能量消耗最小化的节能算法不考虑当前节点的剩余能量情况，也不考虑网 络的负载。如果网络负载较大，所有的负载均通过所选取的路由进行传输，很容 易导致该路由中某些关键节点由于能量的快速消耗而死亡，而其他节点虽然能量 第章绪论 充足，但由于不在选中的路由上，也不会参与数据的转发，造成网络中能量资源 使用的严重不均衡。死亡的关键节点很容易导致网络产生分区，从而减少了网络 的生存时间，降低了网络的服务质量。因此，设计能够最大化网络生存时间的节 能路由成为研究的热点。一般来说，最大化网络的生存时间可以从两个方面来考 虑：最大化网络生存时间直到第一个节点死亡和最大化网络生存时间直到网络产 生分区，后者关注整个网络的连通性，而前者更关心网络中的每个节点。下一节 会针对该部分进行详细论述。 关于节能路由机制，除了以上两大类，还有一些其他解决方案，如最小化路 由协议开销和考虑路由的可靠性等。前者指的是在路由发现的过程中，尽量减少 能量的消耗，l a p a r 是其中的一个代表，它根据节点的位置信息进行局部的路 由选择。后者主要是尽量选择可靠性比较高的路由，以减少重发的次数来节省能 量。其他方案如考虑信噪比对路由算法的影响，在路由算法中应用方向天线等， 也能得到较好的能量使用效率。 1 2 3 基于网络生存时间的节能路由协议 1 2 3 1 基于剩余电池能量的路由 无线a dh o c 网络中基于节点剩余电池能量的节能路由主要有两种：m b c r 和m m b c r 。 m b c r ( m i n i m u mb a t t e r yc o s tr o u t i n g ) 1 2 8 】节能机制如下：定义节点的能量 代价函数为该节点剩余电池能量的倒数，定义路由的能量代价函数为该路径中各 个节点的能量代价函数之和，也就是各个节点剩余电池能量的倒数和，目的节点 选择路由能量代价函数最小的路由反馈给源节点。该算法尽量使用网络中剩余电 池能量比较充足的节点，从而达到网络中各个节点的能量资源使用均衡的目标， 从而延长网络的生存时间。如果各个节点能量资源比较均衡，则该算法趋向于选 择跳数最少的路由。该算法的不足是它是以各个节点的剩余电池能量的倒数之和 作为代价，所选择的最终路由中，可能会含有当前网络中剩余电池能量最小的节 点，也就是瓶颈节点可能会仍被选择参与数据包的转发，从而导致瓶颈节点由于 能耗过快而死亡，可能引起整个网络的分区或者瘫痪，缩短了网络的生存时间。 m m b c r ( m i n m a xb a t t e r yc o s tr o u t i n g ) 2 4 j 是针对m b c r 的不足而由s i n g h 等人提出的。它的算法如下：和m b c r 一样，首先定义节点的能量代价函数为 该节点剩余电池能量的倒数，但路由的能量代价函数定义为该路径中各个节点的 能量代价函数的最大值，最大值所对应的那个节点称为该路径的关键节点，目的 节点选择路径能量代价函数最小的路由，也就是关键节点的节点能量代价函数最 小的路由作为最终路由，然后反馈给源节点。该算法尽量避免使用网络中剩余电 第章绪论 池能量最小的那个节点，也就是瓶颈节点，能够延缓第一个节点死亡的时间，能 够更加均衡各个节点的能量使用。 以上两种算法在定义节点和路由能量代价函数的时候，仅仅考虑了节点的剩 余电池能量。如果网络负载非常大的情况下，这两种算法所选择的路由中，开始 包含了剩余电池能量相对较多的节点，但高负载使得最终路由上的这些节点的能 量消耗的速度非常快，这些节点很快就变成了剩余电池能量较少的节点，不再适 合参与数据包的转发，所以仅考虑节点的剩余电池能量，而不结合网络的负载情 况考虑节点的能量消耗速度，也就是节点的耗干率，不利于延长网络的生存时间， 同时，这些算法也没有考虑每个数据包总能量消耗的最小化，所选的最终路由可 能会使得总能量消耗不是最小，和基于总能量消耗最小的节能路由相比，消耗了 过多的能量，从而导致网络的生存时间实际变短。 1 2 3 2 基于节点生存时间的路由 基于节点生存时间的节能路由算法按照节点能量代价函数的意义可以分为 两类：基于关键节点的剩余时间和基于关键节点最多可发送的数据包的数目。前 者的典型代表有k o n g k y u n 等人提出的m d r 算法和m a l e k i 等人提出的l p r 算法， 后者的典型代表有m i s r a 等人提出的m r p c 算法。 m d r ( m i n i m u md r a i nr a t e ) 【3 0 j 算法的工作机制如下：定义节点的能量代价 函数为该节点的剩余电池能量和能量耗干率的比值，该比值代表了该节点在此耗 干率下可以保持生存的最大剩余时间。定义路由的能量代价函数为该路由中各个 节点的能量代价函数的最小值，最小值所对应的那个节点称为该路径的关键节 点，路由的能量代价函数也就是关键节点的能量代价函数即关键节点的剩余时 间。源节点在所有可选路由中选择路由代价函数最大的路由，也就是关键节点的 剩余时间最多的路由。该算法的关键是节点耗干率的计算，计算方法是每隔一定 的周期对节点的剩余电池能量进行采样，用最近两次采样的差值除以采样周期可 以得到最近的耗干率，同时对最新的和历史的耗干率用指数平均移动法进行平 滑，以平滑掉过去能耗所带来的影响，同时也给最新的耗干率以比较高的优先级， 更好地反映最近的能耗情况。该算法考虑了通信所带来的开销，如发送，接收以 及偷听所消耗的能量均被考虑。 l p r ( l i f e t i m ep r e d i c t i o nr o u t i n g ) 3 1 - 1 - _ 作原理和m d r 基本一样，只是耗干 率的计算方法不同。它是利用历史平均值计算耗干率的：当发送每一个数据包时， 就对该节点的剩余电池能量和当前时刻进行采样，利用最近两次采样的剩余电池 能量的差值和采样时刻的差值，将这两个差值做比值，结果是最近采样间隔内节 点的耗干率。假设历史值个数为n ，每相邻两个历史值就会得到一个耗干率，总 共可以获得n 1 个耗干率，将之取平均值就得到了该节点的耗干率。该算泫没有 第章绪论 采用指数平均移动，以平滑过去能耗所带来的影响，也不能给最新的耗干率比较 高的优先级，不能更好的反映最近的能耗情况。同时它只考虑发送数据包时的能 量消耗情况，事实上接收数据包和监听数据包所消耗的能量也是不容忽视的，所 以这种算法预测的能量的耗干率并不是很精确，但是原理简单，比较容易实现。 m r p c ( m a x i m u mr e s i d u a lp a c k e tc a p a c i t y ) 3 2 j 和m d r ，l p r 算法不同， 它定义节点的能量代价甬数不是剩余电池能量和耗干率的比值，而是剩余电池能 量和节点传输功率的比值，这个比值反映了节点在当前能量状态下还可以发送的 数据包的最大数目，定义路由的能量代价函数为各个节点的代价函数的最小值， 最小值所对应的节点称为该路由的关键节点，源节点在所有可选路径中选择路径 代价函数最大的路由，也就是关键节点发送数据包数目最多的那条路由。 基于节点生存时间的节能路由算法不仅考虑了节点的剩余电池能量，同时还 考虑了节点的能量消耗的具体情况。仿真和实验表明，该种机制比单纯基于剩余 电池能量的算法，具有更好的能量使用效率，能够在网络负载比较大的情况下， 有效地延长网络的生存时间。但是这些算法所选出的路由并不能保证它的总能量 消耗是最小的。有人证明，在总能量消耗的最小化和瓶颈节点的能量资源使用之 间有一个t r a d e o f f , 设计一个比较好的能量优化的路由算法，关键是在这两者中 间设法找到一个平衡点，但是这是一个n p 难问题。 1 2 3 3 综合剩余电池能量和总能耗最小的路由 基于综合剩余电池能量和总能量消耗最小化的节能路由主要有两个：m a l e k i 等人提出的p s r 算法和s i n g h 等人提出的c m m b c r 算法。 p s r ( p o w e r - a w a r es o u r c er o u t i n g ) 1 3 3 j 算法定义节点的能量代价函数为两部 分的乘积，第一部分是节点的传输功率，用来体现总能量消耗最小化的，第二部 分是节点的初始能量和当前剩余能量的比值的n 次方，用来体现剩余电池能量 的，定义路径的能量代价函数为该路径中各个节点的能量代价函数的总和。在节 点代价函数中，n 是一个权衡因子，当初始能量和剩余能量的比值大到一定比值 时，则权衡因子就相应地增加，它是一个上述比值的函数，是可变的，从而可以 使得很少能量的节点对节点路径代价函数的贡献非常大，因此就会避免使用包含 最小剩余电池能量的节点的路由。 c m m b c r ( c o n d i t i o n a lm a x m i nb a t t e r yc o s tr o u t i n g ) 算法是在m m b c r 算法基础上改进而来的。它的工作原理如下：它定义路由能量代价函数为该路由 中各个节点的剩余电池能量的最小值，然后定义一个标志电池能量大小的阈值， 当路由的代价函数大于阈值的时候，也就是路由中所有的节点的剩余电池能量都 大于这个阈值，所有这样的路由所构成的集合如果不为空，则算法就在这些路由 中选择总能量消耗最小的路由，否则如果为空，也就是所有可选的路由中，没有 第一章绪论 一条路由的代价函数大于阈值，则该算法降为m m b c r 算法，即在可选路由中 避免选择含有最小剩余能量节点的路由。该算法的一个缺点是闽值不能够有效地 确定，阈值的选择对结果的影响很大。 以上这两种算法在考虑节点和路由能量代价函数的时候，综合考虑总能量消 耗的最小化和剩余电池能量的情况，或者选择各个节点能量代价函数之和最小的 路由，或者用阈值来帮助路由选择，能够避开瓶颈节点，但是它们没有反映能量 消耗的变化情况，不能实时地反映网络的负载情况。 1 2 3 4 综合节点生存时间和总能耗最小的路由 基于节点生存时间和总能量消耗最小化的节能路由主要有c m d r 和 c m r p c 。下面分别做介绍： c m d r ( c o n d i t i o n a lm i n i m u md r a i nr a t e ) 算法是在m d r 算法的基础上发 展而来，它的工作机制如下：定义路由的能量代价函数为该路径中各个节点的能 量代价函数的最小值，同时设定一个闽值，路由代价函数大于阈值的所有路由构 成一个集合，根据m d r 算法所有可选的路由构成另外一个集合，若两个集合有 交集，则在第一个集合中选择总能量消耗最小的路由，否则该算法退化为m d r 算法，即在第二个集合中选择路由。该算法同样面临的问题是阈值的选择，它不 能被有效的确定，而且对实验的结果有很大的影响。 c m r p