（系统分析与集成专业论文）ad+hoc网络能量有效性的研究.pdf

摘要 摘要 本论文主要研究a dh o c 网络中的能量效率问题。a dh o c 网络是一种无固定结构的分布 式多跳网络，由于节点的移动性，网络中的节点一般依靠电池供电，而电池的存储能量有 限，这使得能量问题成为a d h o e 网络中的突出问题。 论文对a dh o c 网络各层存在的能量问题进行了阐述，给出了a dh o e 网络模型，定义 了网络均衡度，以及根据实际测量结果得到的能量消耗模型。论文提出了链路层和路由层 的解决方案，分别是p e m a c 链路协议、t b e r 路由度量算法。 大量的研究文献表明，节点处于休眠状态的时候其能量消耗非常小，基于节点休眠模 式的p e m a c 协议正是利用了节点的这特性，使节点可以在休眠、空闲和传输状态中切 换。采用p e m a c 协议，节点处于空闲状态一段时间后如果没有数据发送或者节点收到目 的地址为其它节点的r t s c t s 消息后将进入休眠状态，从而节省了能量。论文对p e m a c 协议进行了建模分析，给出了该协议的离散m m k o v 链模型，并通过该模型求得在一定参 数条件下的节点最佳休眠时间的公式。分析和仿真结果表明，采用该协议可以有效地延长 网络生存时间，提高网络的吞吐量。 r b e r 路由度量与目前所提出的各种基于能量的路由度量不同，该度量从流量的角度 出发，综合考虑了节点当前能量以及节点链路层的拥塞情况，是一种兼顾整体( 整个网络) 与局部( 单个节点) 的能量路由度量方案。该路由度量方法可以使网络中节点的能量被更 加均匀、合理地利用，同时也均衡了网络的流量，提高了网络的吞吐量和能量效率，延长 了网络的生存时间。 本论文指出网络各层次间协议相适配，可以进一步提高网络的性能，如延长网络生存 时间、提高网络吞吐量等。论文对链路层与路由层的能量问题进行了综合分析，分析和仿 真表明，在链路层采用p e m a c a 协议的同时在路由层采用t b e r 路由度量可以进一步提 高a dh o c 网络生存时间和网络吞吐量，提高网络的能量效率。 关键词：a dh o c 网络，能量，休眠，媒体接入控制，均衡流量，路由，路由度量，路由建 立 a b s l l u c t a b s t r a c t a dh o cn e t w o r k sa r cm u l t i h o pw i r e l e s sn e t w o r k sw i t h o u tf i x e di n f r a s t r u c t u r e b e c a u s en o d e s s t r o n gd e p e n d e n c y o nb a t t e r i e s ，t h ea dh o cn e t w o r k sa r e e n e r g y - c o n s t r a i n e d h o wt oi m p r o v ee n e r g ye f f i c i e n c yi sa l li m p o r t a n td e s i g ni s s u e d u et ot h el i m i t e db a t t e r y 陆 t h i sp a p e rp r e s e n t sas u m m a r yo fr e c e n tw o r ko ne n e r g ye f f i c i e n c ya m o n ga l l l a y e r so fa dh o cn e t w o r k s ，d e f i u e sam o d e lo fa d h o en e t w o r ku s i n gr a n d o mg r a p h t h e o r e m ，a n dg i v e sa ne n e r g yc o n s u m p t i o nm o d e lb yr e a l i s t i ct e s t o u rr e s e a r c h e s f o c u so ne n e r g ye f f i c i e n c yo f t h em a cl a y e ra n dt h en e t w o r kl a y e n i nt h em a cl a y e r , w ed e v e l o pan e we n e r g ye f f i c i e n c ym a cp r o t o c o lc a l l e d p e m a c t h i sp r o t o c o lr e d u c e st h ee n e r g yc o n s u m p t i o no fn o d e u s i n gp e m a c ，a n o d ew i t hp a c k e tt ot r a n s m i ts e n d sa nr t sm e s s a g e ，a n dt h ed e s t i n a t i o nn o d er e t u r n s ac t s t h en o d es h o u l ds w i t c hi n t ot h es l e e ps t a t ew h e n ：( 1 ) i ft h e r ei sn op a c k e tt o t r a n s m i ta f t e ra ni d l ep e r i o d , o r ( 2 ) i tr e c e i v e sa nr t s c t sm e s s a g ed e s t i n e dt oo t h e r n o d e am 赶k o vd 忸i nm o d e lf o rp e m a ci sp r e s e n t e dt oo b t a i z lt h eo p t i m a ls l e e p i n g t i m eo ft h en o d e s i m u l a t i 0 1 1r e s u l t ss h o wt h a t , c o m p a r e dw i t ht r a d i t i o n a li e e e 8 0 2 1 1a dh u en e t w o r k s ，p e m a co u t p e r f o r m si nt e r m so fn e t w o r kl i f e t i m ea n d n e t w o r kt h r o u g h p u t t b e ri san & we n e r g y - e f f i c i e n c ym e t r i cf o rd e t e r m i n i n gr o u t e si na dh o c n e t w o r k s w i t h 羽3 e i 乙t h en o d e sr e s i d u a le n e r g y ( r e m a i n i n gb a t t e r yc a p a c i t y ) a n d m a ci o a da r ct a k e ni n t oa c c o u n t a sar e s u l t , a ne s t a b l i s h e dr o n t ea v o i d su s i n g n o d e sw i t hm i n i r f l t l r ne n e r g yo rh e a v yl o a d ac o m p a r i s o no fm p t rr o u t i n ga n d t b e rr o u t i n gm e t r i ci sc o n d u c t e d t h ea n a l y s i sa n ds i m u l a t i o nr e s u l t ss h o wt h a t t b e rr o u t i n gm e t r i cc a np r o l o n gt h en e t w o r kl i f e t i m ea n di n c r e a s en e t w o r k t h r o u g h p u tw h e nt h e r ea r ee n o u g hr o u t e st ob es e l e c t e d r e s u l t sa l s os h o w t h a tt h e i m p r o v e m e n ti sl i m i t e dd u e t oo v e r h e a r i n g w ea l s oc o m b i n e dt h ep e m a cw i t ht b e ra n d g e t t h ec o n c l u s i o nt h a t i n c o r p o r a t i o no fe n e r g ye f f i c i e n c ym e t h o d sa p p r o p r i a t e l y c a l lf b r t h e ri m p r o v e n e t w o r kl i f e t i m ea n dt h r o u g h p u t k e y w o r d s ：a dh o en e t w o r k s ，e n e r g y , s l e e p i n g ，m a c ，t r a f f i cb a l a n c e ，r o u t e ，r o u t e a b s t r a c t m e t r i c ，r o u t es e t u p i l l 学位论文独创性声明 本人郑重声明： 1 、坚持以。求实、创新的科学精神从事研究工作。 2 、本论文是我个人在导师指导下进行的研究工作和取得的研究 成果。 3 、本论文中除引文外，所有实验、数据和有关材料均是真实的 4 ，本论文中除引文和致谢的内容外，不包含其他人或其它机构 已经发表或撰写过的研究成果。 5 、其他同志对本研究所做的贡献均已在论文中作了声明并表示 了谢意。 作者签名：盆圣! 幽 日 期；z 蝴：皇：珥 学位论文使用授权声明 本人完全了解南京信息工程大学有关保留、使用学位论文的规 定，学校有权保留学位论文并向国家主管部门或其指定机构送交论 文的电子版和纸质版；有权将学位论文用于非赢利目的的少量复制 并允许论文进入学校图书馆被查阅；有权将学位论文的内容编入有 关数据库进行检索；有权将学位论文的标题和摘要汇编出版保密 的学位论文在解密后适用本规定 作者签名：i 釜逝! 盟 日 期：纽妇：2i 第一章绪论 第一章绪论 当今世界已经进入了飞速发展的信息时代，通信成为了信息产业中发展最为迅速， 进步最快的行业。其中，移动通信作为快速、便携、可靠方便的通信方式更是倍受关注， 成为未来通信的基础。在此基础上的a dh o c 网络，由于其不需要固定网络结构、组网灵 活等特点，将会得到越来越广泛的应用。能量问题是a dh o c 网络中一个非常重要的问题， 本论文从链路层和网络层对这一问题进行了深入研究，本章简要介绍了a dh o c 网络以及 其中的能量问题。 1 1a dh o c 网络简介 信息技术的革命把世界连为一体，网络改变了人们的学习方式、工作方式、娱乐方 式，以至于彻底改变了人们的生活方式。未来的网络将是一种什么样的网络昵? 对此， 一种普遍的观点是未来的网络由有线网络以及无线网络组成，将在任何时候、任何地方， 为任何人提供所需要的任何服务( “a n y t h i n g , a n y t i m e ，a n da n y w h e r e ”) 。 在微电子技术和信息技术的推动下，随着各种便携式终端的大量使用，无线通信技 术的极大发展，以及用户对移动业务需求的不断增大，无线网络得到了广泛的应用。目 前，主要的无线网络有蜂窝网、无线局域网、卫星厨和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 网络具有如此巨大的应用前景，因此成为了国内外各高校以及研究机构 的研究热点，如加州大学洛杉矶分校的“无线自适应移动性实验室”( w i r e l e s s a d a p t i v em o b i l i t yl a b o r a t o r y ) ，马里兰大学的“移动计算与多媒体实验室”( t h e m o b i l ec o m p u t i n ga n dm u l t i m e d i al a b o r a t o r y ) ，美国d a r p a 研究协会，朗讯科技和 贝尔实验室等。此外，i g r f ( t h ei n t e r n e te n g i n e e r i n gt a s kf o r c e ) 还于1 9 9 6 年成立 了m 埘e t ( m o b i l ea dh o en e t w o r k i n g ) 工作组 1 2 3 ，主要研究a dh o c 网络中基于i p 的路由协议规范及其接口设计，并对提出的各种路由协议进行性能研究评判。 a dh o c 网络主要具有以下几个特点 3 ： 1 动态拓扑结构：在a de i o c 网络中由于节点的移动性，节点收发信机功率的调整 以及信道的变化，使得网络的拓扑结构不断发生变化。 2 带宽受限且变容量连接：与有线网络相比较，无线信道的频率资源有限，信道的 多径衰落和干扰较严重，因此a dh o c 网络不仅带宽有限，而且网络的实际容量往往低子 最大网络容量。 第一章绪论 3 节点能量受限：大多数移动节点是通过电池供电，由于电池能量有限，网络可能 提供的范围和活动性以及网络的存在时间受到很大的限制，因此对于这样的移动节点， 一个最重要的系统设计指标就是其耗能特性。 4 安全性较差：与有线连接相比无线连接具有发散性和自由性，不受空间和网络基 础的限制，有线网络的固定物理访问点数量有限，而无线网络中位于天线辐射范围内的 任何一点都可以使用无线网络，因此采用了无线连接的a d l l o c 存在着更多的安全性问题。 1 2a dh o c 网络中的能量问题 a dh o e 网络是一种不需要固定基站支持的、具有高度动态拓扑结构的网络，组成a d h o c 网络的节点是一些移动节点，这些移动节点的能量供应不可能像基站或其它固定设备 那样通过有线电源供电。在a dh o c 网络中，由于网络节点的移动特征，大多数节点以电 池作为动力，因而，在进行系统设计时能量效率就成为一个非常重要的指标陆7 】。 作为一种能量受限的网络。与固定有源节点相比，a dh o c 网络中节点能量供给具有 高成本或短时特性，其网络特性与能量消耗密切相关。文献f 7 】中指出由于a dh o e 网络从 各个方面充分体现了无线网络的特征，因此研究无线网络的能量问题可以重点研究a d h o c 网络的能量问题。 如图i 1 所示，a dh o c 网络中的无线节点主要处于三种状态 7 ，8 】，分别是发送、接收 和空闲状态： 图1 ia dh o e 网络中节点状态图 在不同的状态下，节点消耗的能量不同。当节点处于发送状态时，其能量消耗一般 包括用于提供射频传输功率的前端放大器所需的能量以及节点产生信号和处理信号的能 量，包括编码、调制和存取等。当节点处于接收状态时其能量的消耗主要包括有低噪声 信号放大器的能量消耗以及信号解码和存储等消耗的能量。当节点处于空闲状态时，其 能量的消耗除了保持电路正常工作所需的能量外，还包括由于串音所引起的能量消耗。 1 3a dh o c 网络中能量问题的研究现状 作为近年来a dh o e 网络的一个研究热点，目前已经提出了多种提高能量效率的方 法。增加移动节点的工作时间最直接和有效的方法就是采用高容量的电池，但是近三十 年来用于移动设备的电池技术都没有取得明显的改进，因此如果电池技术没有突破性的 进展，能量问题的解决就只能从节点能量消耗方面着手 7 - 9 】。能量消耗问题涉及至 j a d h o c 2 第一章绪论 网络的各个方面，不仅仅包括物理层，同时也涉及到了媒体接入控制层( m a c ) 、逻辑 链路控制层( l l c ) 、网络层、传输层以及应用层【6 1 4 】，其协议栈如图1 2 所示。目前 a dh o e 网络能量问题的研究主要是针对不同网络层次提出相应的解决方法。 源节点 目的节点 应用层 应用层 传输层 中间节点 传输层 网络层 网络层 网络层 网络层 逻辑链路 逻辑链路逻辑链路 逻辑链路 控制层 控制层 控制层 控制层 媒体接入 媒体接入媒体接入 媒体接入 控制层 控制层控制层 控制层 物理层 物理层物理层 物理层 图1 2a d h o e 瞬络协议栈模型 1 3 。l 物理层能量问题 物理层的主要功能是在信道上传输原始比特流。过去对移动节点能量问题的研究 主要集中在物理层，包括选择适合的硬件以及编码调制方式等。在超大规模集成电路发 展的基础上，采用不同时钟频率的c p u 、快速的数据存取设备( 如闪存) 等【1 1 ，1 2 ，可 以减少节点能量消耗。在此基础上，将硬件技术与不同的调制解调方式和编，解码方式， 以及信号压缩方式相结合可以进一步节约能量 1 3 】。此外也可采用发射功率等级可变的 无线网卡，也可以根据收发信机之间的距离，结合节点运动预测，采用自适应天线改变 发射功率的大小，以及根据信道特性合理分配功率等，提高能量的利用率 1 4 2 0 。但是 目前一方面功率可变的无线网卡种类很少，并且这些无线网卡虽然发射功率可变，但是 其可变功率的等级十分有限，另一方面节点采用可变功率也会产生一些新的问题，如图 1 3 所示： 图1 3 采用不同发射功率等级的a dh o e 网络 3 第一章绪论 图1 3 中节点a 检测到目的节点b 在其附近，因此采用低的发射功率传输数据。此时， 如果节点c 欲发送数据至节点d ，由于c 位于节点a 发射功率范围外，因此不能侦听到a 和b 之间正在进行的通信，节点c 认为信道空闲，由于d e 离c 比较远，因此节点c 将采用一个 较大的发射功率，从而会对节点a 和b 之间的通信造成干扰。针对这一问题提出了很多解 决方法，如文献 1 5 】中提出在节点发送数据前，采用最大功率发送一个控制帧，通知其 最大传输范围内的节点有通信正在进行，这样虽然可以避免节点c 干扰节点a 和b 之间的通 信，但是降低了空间的利用率也降低了网络的吞吐量。 1 3 2 媒体接入控制层( m a c ) 能量问题 媒体接入控制层的主要功能是决定信道的分配，不同的接入方式对能量效率也有影 响，比如采用时分多址接入和采用频分多址接入具有不同的能量效率 7 】。此外还可以根 据所采用的链路层协议，通过改变节点的状态来减少耗能，文献 8 中，采用支持节点可 以在不同状态下切换的m a c 层协议来提高能量利用率，其链路层协议采用了可以在激活模 式( a c t i v em o d e ) 和功率节省模式( p o w e r - s a v em o d e ) 之间转换的i e e e8 0 2 1 1 姒c 层协议 2 1 来节省能量。当节点处于激活模式时，可以收发数据；当节点处于功率节省 模式时，节点将处于休眠状态，在该状态下。节点能量损耗非常低。文献 2 2 中给出的 称为p a m a s ( p o w e r - a w a r em u l t i p l ea c c e s sp r o t o c o lw i t hs i g n a li n g ) 的m a c 层协议，利 用r t s c t s ( r e q u e s tt os e n t c l e a rt os e n d ) 消息来确定节点休眠的时间，当在其传 输范围内有其它节点发送或接收数据时节点进入休眠状态。在本论文第三章中将详细 的分析舭c 层能量效率问题。 1 3 3 逻辑链路控制层能量阎题 逻辑链路控制层的功能主要是处理错误控制、流控制、帧同步和m a c 子层寻址。主 要采用自动重传请求( a u t o m a t i cr e p e a t 阳u e s tm 硷) 和前向纠错( f o r w a r de r r o r c o r r e l a t i o nf e c ) 两种方式来实现差错控制。采用前向纠错是为了减少重传的次数，降低 数据传输负载，但是纠错能量越强，则译码设备越复杂，并且附加码元所占比例更大， 降低了传送数据的效率。自动重传请求需要重新发送数据，数据包比较大的时候，重传 所需要的资源消耗就更大。因此无论是自动重传请求还是前向纠错都需要消耗带宽资源 和能量资源。为此，文献【2 3 】中提出了一种提高能量效率的自适应差错控制自动请求重 传机制( a d a p t i v ee r r o rc o n 廿o lw i t h a r q ) ，其结果表明减少重传的次数或者降低传输功 率，可以提高协议的整个网络的能量效率。文献 2 4 】中提出了一种综合a r q 和f e c 机制 的自适应差错控制机制，其原理是将差错控制方案与特定的传输需求以及当前信道状况 相结合以获得针对每个特定连接的最佳能量效率。 1 3 4 网络层能量问题 网络层为通信端点闻提供建立、保持和终止网络连接的手段并使得不同的物理层对 4 第一章绪论 上层透明，其作用在于确定分组从源端到目的端路由的选择。对于无线网络，其网络层 除了传统意义上的功能外，还有在节点移动以及信道变化的情况下维护和更新路由的功 能。网络层能量效率问题是a dh o c 网络能量问题的研究的一个热点。在网络层，常见的 有采用不同的路由度量方式以及定位路由方式来提高能量效率 2 5 - 3 1 。本论文主要研究 通过路由度量方式和均衡流量方式来提高网络的能量效率。目前与能量有关的度量方式 可以分为三种，分别是功率度量路由算法，能量度量路由算法和混合路由算法f 2 5 ，2 6 。 功率度量路由算法以传输功率( t r a n s m i s s i o np o w e r ) 作为选择路由的度量，路由选择时 选取可选路径中总的传输功率最小的路径。功率度量路由算法适用于发射功率可以调整 的情况，在发射功率固定的情况下，功率度量路由算法等同于最小跳数路由算法。文献 【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 r r o u t i n g ) 就是一种典型的功率路由算法，节点数为d 的路径上的总的传输功率为： d - - i e c r d ) = yt ( n 。+ n 。) ，路由选择时选取p p 印最小的路径。能量度量路由算法主要考 智 虑网络中节点的剩余能董。选择路由时避免使用剩余能量低的节点，这样可以保持网络 的连通度，延长网络的生存时间，文献 2 8 】中给出的m m b c r ( m i n - m a xb a t t e r yc o s t r o u t i n g ) 算法在选择路由时将每条可选路径中剩余能量最小的节点的能量进行比较，选 择其中剩余能量最大的节点所在的路径。混合度量路由算法综合考虑了发射功率和剩余 能量问题，在路由选取的同时考虑了两者对网络性能的影响，文献 2 9 】中给出的 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 a p a c i t yr o u t i n g ) 算法综合了m t p r 算法和 h m l b c r 算法，既考虑到了总的传输能量又考虑到了网络中节点的剩余能量。第四章中 将提出一种新的基于a dh o c 网络中移动节点当前传输负荷和节点剩余能量的能量效率路 由选择算法。 1 3 5 传输层能量问题 传输层为源节点和目的节点提供可靠的端到端数据传输。广泛使用的传统的传输层 协议是专门为有线网络设计的，这些协议在无线环境下性能下降明显，如t c p ( t r a n s m i s s i o nc o n t r o lp r o t o c 0 1 ) 协议 3 2 】在无线环境下可能会引起大量的重传并且带来 更加频繁的链路冲突，这样不仅会降低网络的吞吐量、增加时延。同时也会消耗有限的 带宽与电池能量。可以通过减少端到端的重传来提高无线网络传输层能量效率，文献i t 4 1 中a dh o c 网络在链路层进行本地重传和差错控制，使得链路层的差错对传输层而言是透 明的，避免端到端的重传。文献 3 3 】中给出了一种采用探询机制的t c p 协议 ( t c p p r o b i n g ) ，采用该协议，如果无线节点监测到数据包丢失或者延时较大时，并不 直接进行阻塞控制。而是停止发送数据并开始探询过程。在探询过程中，源节点向目的 节点发送探询分组，该分组由t c p 报头的扩展实现并且不携带数据。如果在接下来的两 个往返时间( r o u n dt r i pt i m er t t ) 内没有包丢失，则探询过程结束，节点认为探询 前数据包的丢失是由偶然因素造成，此时节点将继续传输数据。否则，如果在探询过程 5 第一章绪论 中探询分组丢失，则进行传统的t c p 阻塞控制。其仿真结果表明该协议在获得更高的吞 吐量的同时降低了能量消耗。 1 3 6 应用层能量问题 应用层包含了所有的高层协议，如虚拟终端协议( t e l n e t ) 、文件传输协议( f r p ) ， 在无线网络中应用层还负责对业务进行分类。目前已经提出了多种方法用于提高移动节 点的能量效率，如文献 3 4 中提出用于无线网络的负荷分散算法，将移动节点的计算任 务交与基站完成，然后将计算结果返回移动节点，但这些方法大多需要有基站或者是有 源节点支持，对无固定结构的a dh o c 网络而言，并不适合。对于a dh o c 网络，可以根据 节点当前的能量状况以及无线链路状况，采用适合的压缩编码方法，或者对业务进行取 舍( 如在低功率或低带宽的情况下压缩视频业务仅允许音频业务) 来减少能量消耗。 1 4 论文的研究工作与主要贡献 a dh o c 网络的能量效率问题非常复杂，涉及到网络的各个层次，如何利用各层次的 特点，采取适当的方法提高网络的能量效率并进而提高网络的吞吐量，是一个非常值得 研究的问题。在我们的研究分析中发现，能量问题在a dh o c 网络中不是一个独立于各个 层次的问题，综合考虑网络中各层之间的相互影响，可以更好地利用有限的无线资源， 提高网络的效率。本论文主要研究全分布式a dh o c 网络媒体接入层和路由层的能量效率 问题。 第一章中对a dh o c 网络以及其中存在的能量问题进行了概要介绍。 在第二章中我们采用随机图论，建立了a dh o c 网络模型并对其性能进行了分析，指 出能量效率问题对网络性能的影响。推导出a dh o c 网络容量的计算公式和网络中节点重 要性的计算方法，定义了用于衡量路由算法性能的网络均衡度，并给出了节点的能量模 型。 第三章中提出了一种基于节点体眠模式的无线m a c 协议p e m a c ( p o w e r - e f f i c i e n c ym a c ) 协议，并建立了一个以正e e8 0 2 1 1 协议中定义的时间片为时间单 位的p e m a c 协议m a r k o v 链模型，并通过该模型推导出节点的最佳休眠时间。采用该协 议节点在收到发往其它节点的r t s 或者c t s 消息，或者经过一段空闲时间后如果没有数 据传输将进入休眠状态，从而降低了a dh o c 网络能量的消耗。仿真结果表明p e m a c 协议 可以大幅度的增加网络的生存时间，提高网络总的吞吐量。 第四章提出了一种新的路由度量均衡流量的能量路由度量( t r a 伍c b a l a n c e d e n e r g yr o u t i n g 。t b e r ) 。该路由度量综合考虑了节点剩余能量以及节点链路层的拥塞情 况，兼顾了整体( 整个网络) 与局部( 单个节点) 的能量分配。使得网络中节点的能量 被更均匀、合理地利用，同时也均衡了网络的流量，提高了网络的吞吐量。同时，本章 还指出，由于串音( o v e r h e a r i n g ) 的存在，单纯的通过改进路由层协议对能量效率的提 高是有限的，如果要大幅度地提高网络的吞吐量，增加网络的能量效率，在路由层采用 6 第一章绪论 能量度量的同时，链路层需要采用可以使得节点处于休眠状态的链路层协议以降低串音 的影响。 论文第五章总结了论文内容及作者贡献，并对可以进一步研究的问题进行了讨论。 7 第二章a dh o c 网络基本模型和概念 第二章a dh o c 网络基本模型和概念 a dh o c 网络节点间通信不是利用固定的网络结构，而是利用相邻的无线节点根据其路 由协议选择路径进行通信。由于这些节点位置可变、以及无线链路的不稳定性等，造威a d h o c 网络具有随机且容易发生改变的拓扑结构【3 5 3 8 ，使得原本就非常复杂的网络分析问 题变得更加复杂。本章给出了一个简单的a dh o c 网络模型，并对其进行了分析。 2 1 基本的随机图模型 a dh o c 网络没有固定的网络结构，其节点之间是否连通与收发信机的功率、节点问的 距离、当前信道的状态等都有关系，是一种不固定的连接，不能用连接固定的网络拓扑图 进行描述，需要用到随机拓扑图模型【3 9 】。 图的定义如下：图是指一个有序的三元组( ne ，妒) ，其中列 空称为顶点集，呻的 元素称为顶点，e 称为边集，e 中的元素称为边，9 是e 到绅元索有序对或无序对簇取厢q 函数，称为关联函数。一般可以将图简单表示为g = ( ne ) 。对于图g = ( 玎d ，顶点集 ( v 1 ，屹，v 丑) 中一共包含了月个顶点，每条边连在一对顶点之间 4 0 】。 文献【4 l 】中定义随机图是一组随机连接的点和边的集合。三种常用的随机图模型，分 别是固定边数模型，b e r n o u l l i 模型和动态模型，其中b e m o u l l l 模型在a dh o c 网络的分析 中应用较多。三种模型的定义如下： 1 固定边数模型：对于图g f g ( n , f ) ，设矿中顶点数为，e 中边数为e ，且为定值， 令= c ：，则0 se 茎n ，且顶点数为n ，边数为e 的图有c ：个。所得图为固定边数模型 随机图。 2 b e r n o u l l i 模型：对于图g f c - ( n , o ，给定顶点集玎图中其任意两个顶点问存在一条 边的概率悬，。随着连接概毫p 的增加，图的连通性也相应增加。! 妒= o 时，整个网络中没 有一条边，当p = 1 时，网络中任意两个节点间都有边相连，成为一个完全图。当0 啕v l 时， 在相同的p 值下可以得到多个不同的网络拓扑图。如图2 1 所示为一个节点数为1 5 的网络， 在不同连接概率下所得到的拓扑图： 8 第二章a dh o c 网络基本模型和概念 ( a ) p = o 时网络拓扑图 ( c ) p = l 时的网络拓扑图 图2 1 不同连接概率条件下网络拓扑示意图 9 第二章a dh o e 同络基本模型和概念 3 动态模型：对于m g = c - ( n , f ) ，给定顶点数 和一个正整数时间“从包含所有顶点但 边数为0 的图g ( 月，d ) 开始，每隔一个时间间隔从可能的边中随机地选择一条边加到图中，则 在第t 个时间间隔。图g 嘶r ) 中有绦边。 2 2a dh o e 网络模型 为了便于对a dh o e 网络进行分析，我们根据随机图论定义了其数学模型，在本论文随 后的章节中所指的a dh o e 网络也是指满足下面条件的a dh o e 网络。我们假设网络中共有个 随机分布的节点，每个节点的发射功率相同且接收机所需的接收功率也相同，相邻节点之 间为双向链路。并且节点的发射功率固定，其有效传播距离为r 。当两个节点间距离小于或 等于r 时，认为两点间的连接概率为1 ；当两个节点之间的距离大于r 时，认为接收节点不 能正确接收到发射节点的信号，发射节点的信号相对该节点而言为一干扰信号，此时两节 点间连接概率为0 。在这种情况下一个a dh o c 网络可以表示为一个有条件的b e r n o u l l i 随机图 模型g _ - - - ( n 点) 。e 中元素，写) 表示节点蜀与骂之间存在一条双向链路，其连接概率多可以 袭示为： p = $ 描o 0 慨 ， ”“ 式中凰为网络中通过同样信道同时发送数据的其它节点，为保护间隔系数，一般由物理 层协议规定，用于表明相邻节点使用相同信道传输数据时不互相干扰的保护间隔 4 2 1 。如 图2 3 所示： 第二章a dh c c 网络基本模型和概念 l 夏g , - 一i 专 雩乒露i j 畸一j 警。 图中为一个包含了h 个节点的a dh o c 网络，假设网络中每个节点的最大传输速率为 w b i t l sa 回络中节点砭正在向像节点= | 孑发送数据，此时，网络中还有其它节点在通信，设节 点甄正在和节点瓦通信。如果目的节点巧能正常的接收来自信源节点硎的数据，则应该满足 以下条件： 肛，一一i r 阪- x t l _ r ( 2 3 ) l x 。- x | ，l ( 1 + a ) r 根据三角不等式，考虑到节点可以在同一条直线上，因此可以得到： 陟一五j + 阪一五j 2 阢一五j 三学一五隹譬之f - 一五i ( 2 4 ) j 瞄i - x i l ( 1 + 江一r 、 j 眵，- x i | 丛 从上式可以得到，a dh o c 络中正在同时通信的信源节点问的间距应该大于或等于 a r ，因此对于每一个信源节点而言，在其以址沈为半径的圆内不应该存在其它的同时发送 数据包的节点。设网络中所有无线节点位于一个( 口6 ) l n 2 的矩形区域内，考虑到节点可能位 于矩形区域边缘的情况，在该情况下网络中可以容纳更多的节点。如图2 4 所示： 第二章a dh o e 网络基本模型和概念 墼 i 慧鋈釜：溅黛瑟搽遂慧惑慧黼蕊蕊 浏：i ! ：= ；- 母錾：；= ；! i ；= ；= = i = ! ：馨j ：囊鬈：! ；= ；! 簟：麓奠一。 缓i b 。 j ：j j i ，j j ：! ；：0 ： o ：产眨：鬈：乒曩j 靴：鼍：曩：! ： 薯誊誊材l 萎蓦差藏羲萋蓦黧笔謦蓦誊蓦善 ：- ：j i 二二j j ：t ：一：物r ，2 ：0 ：，：，：i i ! ：，：，： ：j ；j ：i ： ：，：q r 疆：- ：f c 7 - j o ：，：，：一： ：一：弘：。：z ：? 晔五： ：；! ；= ：舞；呀哮誓：；! j j 鬈一雾；j ；= ! ! 薯；j 叠：! = j 毫，? i ：? ：j 二 图2 4 面积为( a x b ) m 2 的a d h o c 网络模型 可得在该矩形区域内，a dh o c 暖 络同时允许的最大的连接对数m 为： m 坠笔；掣 ( 2 5 ) 2 足2 、7 设在某一时刻a db o c 网络的可能的最大通信容量为g 。，则： 。第紫肌脚 ：丝垒些垒2 r 由公式2 6 可以看出，c 。随着r 的减小而增大。但月过小时，网络就将失去连通性，应 该在保证网络连通性的前提下，尽量减小r 。因此，对于发射功率和接收功率相同的a dh o e 网络存在一个r 的折衷值，使得网络即保持一定的系统容量，也具有良好的连通性，同时也 避免了不必要的能量浪费。 2 4a dh o e 网络中重要节点对网络性能的影响 a dh o c 网络是一种没有固定结构的网络，上一节指出，其通信容量随节点传输距离减 少而增大，因此其传输距离不会为一个任意大的值，在移动节点同其发射范围以外的节点 通信需要通过其它节点转发。转发分组时，不论采用哪种路由协议，一般都采用最小跳数 作为路由的度量尺度。在这样的情况下网络中的某些节点可能成为熟点位置，如图2 5 ( a ) 中的节点3 、节点7 和节点8 。这些处于热点位置的节点由于转发数据的可能性大于其它节点， 因此其能量消耗一般比非热点位置的节点( 如处于边界的节点1 1 或者节点9 ) 能量消耗快， 第二章a dh o c 网络基本模型和概念 当网络中某个热点节点的能量耗尽时，可能会引起网络分成几部分，使网络拓扑图成为一 个非连通图【4 3 】，引起网络性能的快速下降。 6 6 、 - ， ( a ) 原始的网络拓扑图 2 3 ( b ) 节点3 和7 能量耗尽后的网络拓扑图 2 3 ( c ) 节点3 和8 能量耗尽后的网络拓扑 图2 5a dh o c 网络热点节点能量耗尽后网络拓扑改变示意图 从图中可以看出，顶点集r j l , 2 ，6 ，1 1 中的节点与顶点集i r 2 4 ，5 ，9 ，i o p p 的节点通信，都 会经过顶点集吩 3 ，7 ，8 l 中的一个或者两个节点。此外- 巧中的节点间通信时也可能将节点7 作为中间节点，而巧中的节点通信时也可能将节点3 和8 作为中间节点。以节点7 为例，假设 1 4 第二章a dh o c 网络基本模型和概念 节点2 正在向节点1 1 发送数据，采用最常用的最小跳数路由算法，所选择的路径为2 7 1 1 。 过一段时间后若节点6 欲向节点1 0 发送数据，按照最小跳数路由算法，其所选路径为 6 - - * 7 - * 8 - * 1 0 。由于两条路径均通过节点7 ，使得网络中所有数据都将通过节点7 ，因此可能 会出现下面两种不利情况： ( 1 ) 节点7 由于要转发网络中的所有数据，因此其能量消耗大于网络中其它节点。一旦 节点7 中的能量耗尽，则网络拓扑将发生改变，此时，节点7 与网络中其它节点的连接中断， 将不能再发送或接收任何数据，无论是对整个网络还是节点7 而言。显然都不希望产生这种 情况。 ( 2 ) 节点7 负荷较重，当源节点产生大量数据使得在节点7 数据到达的速率超过链路层处 理数据的速率时，数据将在链路层的缓冲队列中排队等待，随着缓冲队列中数据的增加， 分组延时也将增加。如果一直保持该状态，将使得链路层存储数据的缓存队列发生溢出， 造成分组丢失。而源节点在规定的时间内没有收到目的节点发回的确认信息，将继续保留 并重传该分组，从而进一步加剧了该路径上各节点的拥塞，最终造成链路中断。 上面的分析也适用于节点3 和节点8 。( 1 ) 中的情形将使得网络拓扑改变，网络性能大为 降低，( 2 ) 中的情形将带来网络的局部拥塞，同时造成不必要的能量损耗。 我们认为节点3 、节点7 以及节点8 处于热点位置，其网络负荷一般大于网络中其它节点， 因此其能量损耗也大于网络中其它节点。当节点集 3 ，7 或节点集 3 ，8 ) 能量耗尽时，该a d h o c 网络被分为两部分，如图2 5 中b 和c 所示。从图中可以看出顶点集 1 , 2 ，3 ，4 ，5 678 ，9 ，1 0 的 非空子集 3 ，7 ) 和 3 ，8 都是该a d h o e 网络拓扑图g 的一个2 顶点割集。所谓顶点割集是指对于 连通图g ，若n 是顶点集v 的非空真子集，岱确不连通，但对n 的任何真子集吩都有g 玛连 通，则称h 是g 中一个点割集。使得g 不连通或成为平凡图所必须删除的顶点的最小个数， 即最小项点割集中的顶点个数，称为该图的点连j 臣度。 图2 5 中的网络拓扑图是一个点连通度为2 的连通图，去掉包含两个顶点的非空子集 3 ，8 ) 或f 3 ，7 中的任何一个，该a d h o e 网络就将被分为不连通的两部分，并且影响的链路数较多。 同样，图中的顶点子集 5 ，8 、 5 ，1 0 以及 2 ，7 也是一个最小顶点割集，但是从图上可以看 到其中任何一个顶点集中的节点不工作，对网络的影响相对小一些。因此虽然同样是最小 顶点割集，但是对网络的影响却不一样。我们将对网络性能影响大的最小顶点割集中的节 点称为网络中的重要节点，这些节点的存在与否对整个网络的性能有着举足轻重的影响。 构造一个可靠的通信网络的时候，总是希望其连通度越大越好，在网络拓扑固定的情 况下，总是希望处于网络关键位置的顶点割中的节点越可靠越好。