（电工理论与新技术专业论文）无线传感器网络拓扑控制的研究.pdf

a b s t r a c t s e n s o rn e t w o r ki sr e g a r d e da so n eo ft h ef o u rn e wt e c h n o l o g i e si nt h e2 或c e n t u r y , w h i c hw i l lm a k eg r e a ts e n s et op e o p l e sl i v e s i nw i r e l e s ss e n s o rn e t w o r k s ，t h es e n s o r n o d e s ，w h o s ep o w e ri ss u p p l i e db yb a t t e r i e s ，a r es m a l le m b e d d e ds y s t e m s e v e r yn o d e h a sl i m i t e dp o w e rt oc o m p u t ea n dc o m m u n i c a t e t h a t sw h y o p t i m i z e dt o p o l o g y c o n t r o la l g o r i t h mi sn e e d e d ，b e s i d e sf o re n e r g y - e fi c i e n tp r o t o c o l sf o rm a c ，r o u t i n g a n da p p l i c a t i o n t o p o l o g yc o n t r o lh a sv i t a li n f l u e n c eo nt h ep e r f o r m a n c eo ft h e n e t w o r k ag o o dt o p o l o g yi saf i r mf o u n d a t i o no ftm es y n c h r o n i z a t i o n ，l o c a t i o na n d s oo n ，w h i c hr e s u l t si nal o n g e rl i f e t i m e t o p o l o g yc o n t r o la l g o r i t h m sa r ei n v e s t i g a t e dh e r e m a i nr e s e a r c hd i r e c t i o n sa r e d i s c u s s e da n da n a l y z e dh e r e a sf o rc l u s t e r i n g ，r er e s e n t a t i v ea l g o r i t h m sa r e s u m m a r i z e di nt h i sp a p e r c o m p a r i s o ni sm a d eb e t w enc l u s t e r i n ga n d p l a n a r t o p o l o g yc o n t r o la l g o r i t h m p o w e rc o n t r o li sa ni m p o r t a n td i r e c t i o no f t o p o l o g yc o n t r o li nw i r e l e s ss e n s o r n e t w o r k s b e s i d e sf o rr e p r e s e n t a t i v ep o w e rc o n t r o la l g o r i t h m s ，a ne n e r g ym o d e la n d t h er a t i oo ft r a n s m i s s i o nr a n g ea n de n e r g yi sa l s oa n a l y z e di nt h i sp a p e r w ec o m eu p w i t ht h ee x i s t e n c eo fa no p t i m i z e dt r a n s m i s s i o nr a n g e ，w h i c hi st h e np r o v e db yt h e r e s u l t so ft h ee m u l a t i o n t w om e a n so f t o p o l o g yc o n t r o la r ec o m b i n e dt oc r e a t ea ne n e r g y - a w a r eh y b r i d t o p o l o g yc o n t r o la l g o r i t h m - - e a h t c f i r s t ，c l u s t e r i n gi sc a r r i e dt h r o u g h ，w h i c h r e s u l t si ni sa st h ec l u s t e rh e a d s t h e ne a c hn o d ea d j u s ti t st r a n s m i s s i o nr a n g e ，w h i c h l e a d st oab e t t e rt o p o l o g y t h er e s u l t so fe m u l a t i o np r o v et h a tt h en o d es e to ft h e c l u s t e rh e a d sa r es y m m e t r i c a la n do v e r l a y st h ew h o l en e t w h a t sm o r e ，t h et o p o l o g y i so p t i m i z e d ，w h i c hi sas u b n e to ft h eo r i g i n a lg rp h i c s t h i sp a p e ra l s ot a k e si n t o c o n s i d e r a t i o nt h ea s y m m e t r yb e t w e e nt h ei n s i d ea n do u t s i d e t h ea l g o r i t h mi sc a r r i e d o np e r i o d i c a l l y , w h i c hp r o l o n g st h el i f e t i m eo ft hn e t w o r ke f f e c t i v e l y k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ，t o p o l o g yc o n t r o l ，h y b r i d ，e n e r g y a w a r e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨盗盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：田 签字日期：功司年弓月f l a 学位论文版权使用授权书 本学位论文作者完全了解苤盗盘茎有关保留、使用学位论文的规定。 特授权墨盗盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：同飞 签字日期：b 司年月1 日 导师签名：以雨纠 签字日期：加司年弓月曰 第一章绪论 引言 第一章绪论弟一早珀下匕 微电子机械技术( m e m s ) 、计算技术和无线通信等技术的进步，推动了低功耗 多功能传感器的快速发展，使其在微小体积内能够集成信息采集、数据处理和无 线通信等多种功能。无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ，w s n ) 就是由部 署在监测区域内大量微型传感器节点组成，通过a dh o c 的方式形成的一个自组 织的网络系统。传感器节点可以提供光照、温度、湿度等多种测量数据，最终通 过多跳的方式传递给观察者f l 2 1 。无线传感器网络采用新的技术和新的标准，包 括小型化设计、高能量密度储能设备、软件硬件的协作设计以及网络的支持等。 它不仅应用于军事和工业领域，而且还会成为人们日常生活的一部分，这是一个 随着新技术的出现而飞速发展的领域。 1 无线传感器网络的特点 无线传感器网络是一种特殊的无线移动网络，与无线的a dh o c 网络相似， 都属于无固定基础机构型的网络，但是两者之间仍然存在很大区别。与传统网络 相比，无线传感器网络主要具有以下特点【1 】1 2 1 【3 】【4 】： ( 1 ) 节点资源有限 传感器网络中对节点的定位是廉价的结构简单的小型设备，由于受价格、体 积和功耗的限制，其计算能力、存储能力和通信能力都十分有限。此外，传感器 节点通常都是采用电争有限的电池供电，一般在使用过程中很难充电或更换，一 旦电池能量耗尽，也就意味着该节点也就失去了作用( 死产) 。因此在无线传感器 网络设计过程中，任何层面的协议都要以最小化网络能耗、最大化网络寿命为目 标。 第一章绪论 ( 2 ) 节点数量众多、分布密集、无中心 为了对一个区域执行监测任务，往往向该区域投放成千上万传感器节点。传 感器节点分布非常密集，节点之间通信的连接度高，采集到的数据冗余大，使系 统有较强的容错性和抗毁性。无线传感器网络中所有节点具有相同的硬件结构， 具有独立的采集信息和路由功能，节点可以随时加入或离开网络，少数节点的故 障不会影响整个网络的正常工作。 ( 3 ) 拓扑动态性强 无线传感器网络是一个动态的网络，节点采用电池供电，可能会因为电池能 量耗尽而退出网络；传感器节点通常抛洒在战场、森林或其他环境恶劣的区域， 因此随时有可能损坏，而退出网络运行。另外，新的传感器节点也可能由于工作 的需要而被添加到网络中。这些都会使网络的拓扑结构随时发生变化，因此网络 应该具有动态拓扑组织功能。网络的运行无需依赖于任何预设的设施或任何人为 的因素，节点通过分层协议和分布式算法协调各自的行为，节点开机后就可以快 速、自动地组成个独立的网络，并且在运行过程中对网络拓扑的改变作出相应 的反应，以保证网络的正常运行。 ( 4 ) 多跳路由 网络中节点通信距离有限，一般在几十到几百米范围内，节点只能与它通信 半径覆盖范围内的节点直接通信。如果希望与较远距离之外的节点进行通信，则 需要通过其他节点进行转发。无线传感器网络中的多跳路由是由普通网络节点完 成的，所有节点结构相同，没有专门的路由设备。这样每个节点既是传感器节点， 义是路由节点。 ( 5 ) 以数据为中心 对于观察者来说，最关心的就是传感器节点所感知的数据。比如在智能家属 应用中，人们可能希望知道“现在客厅的温度足多少”，在森林火灾监测系统中， 人们希望知道“是否发生了火灾”，而传统网络传送的数据是和节点的物理地址 联系起来的。以数据为中心的特点要求传感器网络的设计必须以数据管理和处理 为中心，把数据库技术和网络技术紧密结合，从逻辑概念和软、硬件技术两个方 面实现一个高性能的以数据为中心的网络系统，使用户如同使用通常的数据库管 2 镕一t 镕 理系统乖i 数据处理系统一样自如地在传感器嘲络上进行感知数据的管理 i 与传统a d i i o 网络的区别 在早期的研究中，人们认为对a dh o c 网络协议稍加修改甚至无需修改就可 以直接府片 于无线传感器网络中。但是随着研究的不断深入，人们逐渐发现了无 线传感器嘲络与其他网络如移动通信网、a dh o c 网络、因特网等网络相比的一 些区j j i ： ( i ) 无线传感器网络中的竹点数目更为巨大( 上千甚至l 万) ，分布更为密集， 且节点不定具有全球唯一的地址标识。 ( 2 ) 无线传感器网络中的节点一般不进行快速移动，但由于环境影响或者能 量耗尽等因素，节点有可能会随时加入或离开，因而嘲络的拓扑结构动态性很强。 ( 3 ) 传感器节点主要是咀数据为中心进行路由并采用广播方式通信，而a d h o c 网络大都采用点对点方式通信。 ( 4 ) 无线传感器网络中节点的电池能量、计算能力和存储能力都十分有限。 因此在无线传感器网络中其首要设计目标是能源的高效使用，这也是传感器网 络和传统网络最重要的区别之一。 1 无线传感器网络的体系结构 i41 无线传感器网络的节点硬件结构 b 婚 图l l 传感器网络具有很强的应用相关性在不同的应用要求下来_ i 不同的软件系 统和硬件，f 台。图卜i 所示为儿种典型的传感器宵点模型。一般而言，七线传感 第一章绪论 器节点主要由传感器模块、处理器模块、无线收发模块和能量供应模块等部分组 成。作为一个完整的小型嵌入式设备，要求其各模块协调高效工作，下面分别介 绍各模块【1 】： ( 1 ) 传感器模块 传感器在现实中的应用十分广泛，渗透在工业、医疗、军事和航天等各个领 域，而网络化的传感器系统相对于传统的传感器应用又增加了许多优点。 传感器一般包括传感器探头和变送系统两部分，首先，测到的物理量的变化 通过各种机制转化成电阻、电容或者电感变化。然后，这些电子特性变化通过转 换电路转化为电信号，经处理后，最终转换成数字信号。因此，传感器模块的主 要作用就是采集用户所需的现场数据。 ( 2 ) 处理器模块 处理器模块是无线传感器节点的计算核心，所有的设备控制、任务调度、能 量计算、功能协调、通信协议、数据整合及数据转发存储等任务都是在这个模块 的支持下完成的，因此处理器模块的设计在传感器节点的设计中是至关重要的， 用户应综合考虑运行速度、集成度、功耗、外围接口以及成本等各方面因素来选 择适合自己应用的处理器。 ( 3 ) 无线通信模块 节点之间的相互通信是靠节点的无线通信模块完成的。通信模块消耗的能量 在传感器节点中占主要部分，所以考虑通信模块的工作模式和收发能耗很关键。 传感器节点的通信模块必须是能量可控的，并且收发数据的功耗要非常低，对于 支持低功耗待机监听模式的技术要优先考虑。 ( 4 ) 能量供应模块 传感器网络一般都是布置在人烟稀少或危险的区域，所以其能源不可能来自 于现在普遍使用的工业电能，而只能依赖于自身的存储和自然界的给予。一般来 说，目前使用的大部分都是自身存储一定能量的化学电池。 4 第一章绪论 1 4 无线传感器网络的通信协议体系结构 一圆圆圈圈 一 二二蔓匠二 网络层 堕! 数繁路匝四匝因匿 肱ii】 一匿因匿 图一通信协议体系结构 通信协议体系结构是网络通信协议的集合，是对网络及其部件所应完成功能 的定义和描述。对无线传感器网络来说，其网络通信协议结构类似于t c p i p 协 议体系结构，但又不同于传统的计算机网络和通信网络。如图1 - - 2 所示，将通 信协议体系结构分为物理层、数据链路层、网络层、传输层、应用层。以下分别 叙述各组成部分的功能以及相关研究的最新进展。 1 物理层1 5 j 无线电传输是目前w s n 采用的主流传输方式，需要解决的问题有：频段选择、 节能的编码方式、调制算法设计等。在频段选择方面，i s m 频段由于具有无需注 册、具有大范围的可选频段、没有特定的标准、可以灵活使用的优点，被人们普 遍采用。与无线电传输相比，红外线、光波传输具有不需要复杂的调制、解调机 制，接收器电路简单，单位数据传输功耗小等优点。但由于不能穿透非透明物体， 只能在一些特殊的w s n 系统中使用。另外，光束通信容易受周围环境中的光线及 阳光干扰，但它比无线电通信更加高效，s m a r t d u s t 中就采用光束为通信介质。 声波和超声波通信主要应用在水下等特殊环境下。根据网络应用环境的不同，传 感器网络可能同时采用几种方式作为通信手段。目前，对w s n 物理层的研究迫切 需要解决的问题有：在降低硬件成本方面需要研究集成化、全数字化、通用化的 电路设计方法：在节能方面需要设计具有高数据率、低符号率的编码、调制算法。 5 第一章绪论 2 数据链路层 数据链路层用于建立可靠的点到点、点到多点的通信链路，主要涉及媒介访 问控制( m a c ) 协议【1 3 】 1 9 1 【2 0 1 。现有的蜂窝电话网络、a dh o c 网络中的m a c 协议主 要关心如何满足用户的q o s 要求、节省带宽资源以及如何在节点高速移动的环境 中建立彼此间的连接，功耗是第二位的，这些协议并不适合w s n 。c s m a 是典型的 随机竞争类m a c 协议，虽然具有分布式、易扩展的优点，但冲突会导致能量浪费 和时延的不确定性。目前，w s n 的数据链路层还存在以下一些问题需要深入的探 讨：网络的动态性对信道分配策略的影响；在节能的基础上，如何提高带宽的利 用率和信道访问的公平性、降低通信延迟等。 3 网络层【6 】 网络层包括拓扑控制( 组网) 和路由两个部分。本文将在后续章节详细介绍 拓扑控制相关内容。传感器网络中路由算法主要分为平面路由协议和层次路由协 议，每个传感器节点所带的电量有限，然而通讯、计算、传感等环节都要消耗能 量，其中通讯是消耗能量的最主要环节，需要通过适当的路由算法，减少网络中 的计算量和通讯量，有效延长网络的寿命。 4 传输层8 】【9 】 现阶段对传输控制的研究主要集中于错误恢复机制。参考文献 7 分析了端 到端错误恢复机制在无线多跳网络中的性能。仿真表明，随着无线信道质量的下 降( 信道错误率从1 上升到5 0 ) ，端到端错误恢复机制的性能下降很快( 发送 成功率从9 0o 6 0 下降到接近0 ) 。 8 0 设计了一种快取慢存的数据流控制机制。通 过在数据通路中的每个中间节点中都保持正确的数据包转发次序，来减少错序报 文的盲目转发。该方法可以有效地平衡中间节点的报文缓存数量，为w s n 提供低 开销的错误恢复服务。目前对w s n 传输控制的研究还很少。如何在拓扑结构、信 道质量动态变化的条件下，为上层应用提供节能、可靠、实时性高的数据传输服 务是今后研究的重点。 5 应用层f l o 】【1 l 】【1 2 】【1 3 】 应用层与具体的应用场合和环境密切有关，因此其设计不可能是通用的，必 须针对具体应用的需求进行设计。尽管如此，应用层的主要任务是获取数据并进 6 第一章绪论 行初步处理，这一点是共同的。以数据为中心和面向特定应用的特点要求w s n 能 够脱离传统网络的寻址过程，快速有效地组织起各个节点的信息并融合提取出有 用信息直接传送给用户。同时，为了适应不同网络的需求，还要考虑加入时钟同 步1 0 l 1 、定位技术【1 2 】等功能。 i 传感器节点的限制 传感器节点在实现各种网络协议和应用系统时，存在以下一些现实约束。 ( 1 ) 电源能量有限 传感器节点体积微小，通常用电量有限的电池供电。传感器节点消耗能量的 模块包括传感器模块、处理器模块和无线通信模块。随着集成电路工艺的进步， 处理器和传感器模块的功耗变得很低，绝大部分能量消耗在无线通信模块上。 无线通信模块存在发送、接收、空闲和睡眠四种状态。无线通信模块在发送 状态时能量消耗最大，在空闲状态和接收状态的能量消耗接近，略少于发送状态 的能量消耗，在睡眠状态的能量消耗最少。如何让网络通信更有效率，减少不必 要的转发和接收，不需要通信时尽快进入睡眠状态，是传感器网络协议设计需要 重点考虑的问题。 ( 2 ) 通信能力有限 无线通信的能量消耗e 与通信距离d 的关系是： e = k d ” 其中，参数n 满足：2 i 是与信号传播无关的系统损耗因子。 当发送者与接受者之间的距离大于交越距离d 。时，使用下面的t w o - r a y g r o u n dp r o p a g a t i o n 模型( 信号能量的衰减与距离的四次方成正比) 确定信号的 传输衰减。 w = 竽 ( 3 - 3 ) 其中：h ，、h 。意义同公式( 3 1 ) ，其余同公式( 3 2 ) 。 在这种情况下，由于发送者和接受者之间距离较远，接收信号来自直线和地 面反射等多条路径，多条路径下的相消干涉导致信号能量的衰减与传输距离的四 次方成正比。 典型的网络层功率控制算法 本文的功率控制将主要研究网络层的功率控制，即如何通过改变节点的发射 距离来动态调整网络的拓扑结构，优化网络拓扑。下面介绍几种典型的网络层功 率控制算法。 3 4 基于节点度的算法 一个节点的度数是指所有距离该节点一跳的邻居节点的数目。基于节点度算 法的核心思想是：给定节点度数的上限和下限需求，动态调整节点的发射功率， 使得节点的度数能够落在上限和下限之间。基于节点度的算法利用局部信息来调 整相邻节点间的连通性，从而保证整个网络的连通性，同时保证节点问的链路具 第三章基于功率控制的拓扑控制 有一定的冗余性和可扩展性。 此类算法对传感器节点的要求不高，不需要严格的时钟同步。通过计算机仿 真可以确定，此类算法的收敛性和网络的连通性是可以保证的，它们通过少量的 局部信息达到了一定程度的优化效果。但是此类算法还存在一些明显不完善的地 方，例如需要进一步研究合理的邻居节点判断条件，对于节点度的上限和下限数 值都缺少严格的理论推导等。 3 4 基于邻近图的算法 无线传感器网络拓扑信息用图g e 表示，其中y 是传感器节点集合，f 是一组边集合，每条边p = ( 口，访e ( 其中，v e1 , 3 表示节点与节点y 都在 彼此的无线通信范围内。 图g e 的邻近图g e 是指：对于任意一个节点v e 以给定其邻居的 判别条件q ，e 中满足q 的边( ，访属于e 。基于邻近图的功率可知算法是指： 所有节点都使用最大功率发射时形成的拓扑图为图g ，按照一定的规则q 求出该 图的邻近图g ，最后g ，中每个节点以自己所邻接的最远通信节点来确定发射功 率。这是一种解决功率分配问题的近似解法。考虑到传感器网络中两个节点形成 的边是有向的，为了避免形成单向边，一般在运用基于邻近图的算法形成网络拓 扑以后，还需要对现有网络中的边进行删减或者增加新边，以使得最后得到的网 络拓扑是双向连通的。 目前基于邻近图的算法主要有d r n g 和d l s s 算法，它们以原始网络拓扑 双向连通为前提，保证优化后的拓扑也是双向连通的。 3 4 3c o m p o w 算法 c o m p o w ( c o m m o np o w e rp r o t o c o l 【3 4 j 协议设计的最主要目的是提高网络容量， 并且同时兼顾网络的能量有效性。其设计依据是其对网络容量和能量消耗特性的 理论分析。c o m p o w 的优化目标是：在保证嘲络连通性的前提下，将全嘲的公共 功率值调整到一个最低的水平，以最大限度地提高网络容量。c o m p o w 协议要求 全网所有节点采用相同发射功率值( 公共功率) ，以保证链路的双向连通性，这一 点对于a dh o c 网络中的许多通信协议如m a c 协议、链路控制层协议、路由协议 非常必要。c o m p o w 协议的核心问题是如何设定全网的最佳公共发射功率。其做 第三章基于功率控制的拓扑控制 法是在每个节点的用户空间都维护多个路由表，每个路由表对应了一个全网的公 共功率量级，即：全网所有节点都以该量级的功率发射，形成了一个该功率量级 下的网络拓扑，在该网络拓扑上通过运行d s d v 协议，每个节点生成该功率量级 下的路由表。其中，路由表的表项数目反映了该功率量级下该节点与网络中所有 其他节点的连通程度。全网最佳公共发射功率的选择原则为：每个节点都选择保 持与采用最大功率发送时路由表的条目数完全相同的最小功率量级，根据链路的 双向性特性可以证明，能够相互连通的节点所选的最小功率量级必定是完全相同 的。选定该最小功率量级后，每个节点都将该功率量级下生成的路由表( 包括所 有表项) 调入内核空间以用于数据转发，同时每个节点的发射功率将被调整到该 功率水平。 3 4 4c l u s t e r p o w 算法 前面介绍的c o m p o w 协议适合于网络节点分布比较均匀的情况，然而，当网 络中的节点分布不均匀时，一个位置比较偏远的节点将会使全网的发射功率提升 到一个非常高的水平。因此，根据每个节点的实际情况采用不同的发射功率量 级，对于非均匀分布的网络来说是非常必要的。c l u s t e r p o w 协议就是在该类情 况下对c o m p o w 协议的一种改进，其作法是每个节点根据自己与目的节点的连通 性而并不是与网络中所有其他节点的连通性来选择自己的最小发射功率量级。当 然，c l u s t e r p o w 协议最主要的设计目的也是提高网络容量。在c l u s t e r p o w 协议 下，每个节点在用户空间也维护多个路由表，每个路由表对应一个功率量级。每 个功率量级下路由表的生成过程与c o m p o w 协议完全相同。c l u s t e r p o w 与c o m p o w 最主要的区别体现在核心路由表的产生和节点最优发射功率的确定上。在c o m p o w 协议中，核心路由表的每个表项是共同产生的，每个节点将某一功率量级下生成 的所有表项全部调入内核空间以用于数据转发，而且无论数据分组的目的节点是 谁，该节点都会以该功率量级发送；而在c l u s t e r p o w 协议中，核心路由表的每 个表项是单独产生的，针对每个目的节点，发送节点选择能够与该目的节点保持 连通的最小发射功率量级，同时将用户空间中在该功率鼍级下生成的到达该目的 节点的路由表项调入内核空间，并且当有到达该目的节点的数据分组时，采用该 功率量级进行发射。 2 7 第三章基于功率控制的拓扑控制 3 4 5c b t c 算法 c b t c ( c o n e b a s e dd i s t r i b u t e dt o p o l o g yc o n t r o l 是一种分布式的拓扑控制算 法，该算法把节点的传播区域划分为若干个不重叠的扇面，其中每个扇面覆盖一 定大小角度的区域，节点向周围区域中的节点逐渐增大发射信号来寻找其相邻节 点，直到该节点能在每一个扇面内都至少能找到一个相邻节点或节点的功率达到 它的最大发射功率为止。c b t c 算法生成的网络拓扑具有对称性和节点度数有界 性的特点，且能够更好地保证网络的连通性。当然c b t c 算法也有需要进一步解 决的问题：比如功率应怎样逐渐增大；由于各节点能量消耗的差异，应怎样保护 低能量节点等。 发射距离分析与优化 3 5 节点间距分析 假设节点被随机抛洒在一个2 r 2 r 的区域内( 如图3 4 ) ，下面我们计算源 节点到目的节点的平均距离，即任意两个节点的平均距离。 jl 月 ， 月晨 ， 。 月 图3 - 4 节点随机抛洒 若z 为源节点到目的节点距离的随机变量，则显然，其x 坐标和y 坐标的取 值相互独立且有可能取到( 一r ，+ r ) 问的任何值。于是得到其分布函数为： 嘶= 毋s ：秽 伊4 ， 其分布密度函数为： 第三章基于功率控制的拓扑控制 于z l 、z j 景，o 立积 一l 景一竽胚z _ 5 于是得到源节点和目的节点之间的平均距离为： 一z = 广玩( z ) d z = 墨( 压+ l n ( 1 + 压) ( 3 _ 6 ) 但是上式具有局限性，它仅适用于节点直线传输且任何两点都能够连接的情 况，对于大规模的传感器网络来说，节点间的通信有时是经过其它节点转发的， 只是按照直线距离计算是不切实际的。 下面介绍文献 3 8 的计算方法： 设源节点和目的节点的距离为v ，则存在两种情况： 当v r 时，源节点必须通过路由节点的转接才能 到达目的节点 3 7 3 8 。 图3 4 节点闯通信距离模型 如图3 4 所示，s 表示源节点，d 表示目的节点，r 为路由节点，v 表示s 和 d 的距离，z 表示d 和r 的距离，x 为源节点到达目的节点的最大发射距离。p 是 与发射距离相关的随即变量，kz 分别是与v 、z 相关的随机变量。当矿 r 时， 只有在能够找到一个r 能够担当两者中继节点时，节点才进行数据发送。 尸= 孑冀v r ) n ( ，尺 7 ) 计算p 的数学期望： e pi ( 矿r ) u ( ( 矿 r ) n ( ) 尺) 】= 3 x 2 一r 3 rf v e 卅d v d p 3 ( x 2 2 r 比叩d v ( 3 - 8 ) 第三章基于功率控制的拓扑控制 其中，a s d 是以s 为圆心以r 为半径的圆与以d 为圆心以v 为半径的圆的重 叠部分面积；a 是以s 为圆心以r 为半径的圆与以d 为圆心以z 为半径的圆的 重叠部分面积。两者均可通过几何知识求得其数值。 3 5 距离与能量的比值 从前面的分析可知，当两个节点不在彼此的通信范围内时，数据包的转发和 路由就成为必须，即进行多跳通信。无线发射范围相当程度上影响了网络拓扑和 能量消耗。较大的发射距离要付出较多的能量消耗代价，而较小的发射距离会使 用大量的转发和路由。因此，优化节点的发射功率对延长网络生存期具有十分重 要的作用。 我们参考文献 3 9 中的收发器能量模型，即若将一个长度为k - b i t 的分组 ( p a c k e t ) 消息传送距离，米，则收发器为了发送这个消息需耗能： 瓦( | | ，r ) = 丘一m ( 1 ) + 艮唧( i ，) = 女( ，l + ， ( 3 9 ) 若每次发送的数据包大小固定，即k 为常数，则上式可简化为： 玩p = 墨，”+ 如 ( 3 1 0 ) 其中，毛= 、砭= k t , 均为常数，。与发射机和信道有关；：是发射接收 机的能量消耗，且与r 无关：n 是路径损失因子，根据传播距离常取值2 6 。 假设节点接收同样大小数据包的能量消耗为e ，则进行一次发射的总能耗 为： 反( r + e = 墨，”+ 包+ e ( 3 一1 1 ) 第三章基于功率控制的拓扑控制 图3 - 5 发射距离与距离能量效率 由前面对于节点距离的计算可以得到距离与能量的比值为： “r ：墨 竺! ! 兰三1 2 型g 兰三尘! ! ( 墨! 塑 、 e 。u + e r ：兰! ! 竺 3 。1 2 3 ( x 2 - - 2 r w p 如咖) ( 3 墨厂”+ 红+ e 其中，如一c 。s - l ( 去) + v 2c o s - i ( 1 一专) 一，瓜而z vz v 一 ： z 2c o s - l ( 掣) - 4 - r 2c o s - 1 ( 掣) 一了厅而而再而石琢鬲i z v zz v ，z 若取路径损失因子r = 2 ，k l = 6 6 3 1 9 1 0 一，k ：+ e ，= 1 4 7 6 1 0 ，图3 4 是用 m a t i a b 对发射距离与距离能量效率比值的仿真结果，从上到下依次为密度为 0 0 8 ，0 0 4 ，0 0 0 5 时距离能量效率与通信半径的变化曲线。从图中结果可以看 出，r 值较小时，随着r 值的增加，距离能量效率增加，但当r 超过一定值后， 距离能量效率开始下降，即发射功率存在一个最优值。另外从图中还可以看出， 节点密度不同时，最优发射功率也不同，密度越大，最优发射功率越小，这与实 际情况相符合。 3 本章小节 功率控制是无线传感器网络拓扑控制中一个重要的研究方向，无线发射范围 3 l 第三章基于功率控制的拓扑控制 相当程度上影响了网络拓扑和能量消耗，如果发射半径增加，通信中的平均跳数 会减少，使信道的空间复用度减小，同时也会使节点发射时的功耗增加；如果发 射半径减小，可使发送时的功耗减小，也能提高信道的空间复用度，但收发节点 间报文的平均转发次数可能会增多，且节点之间不能形成有效链路，网络中将会 出现孤岛现象，导致整个网络的连通性很难保证。本章分析了功率控制的意义， 给出信号传递时的能耗模型，并从距离与能耗比值的角度得到了最优的发射半 径，并对其进行了仿真。 第四章混合式拓扑控制算法 4 引言 第四章混合式拓扑控制算法 在第二章中我们已经提到，层次型拓扑控制算法将节点分为簇头和簇成员， 在保证了覆盖范围内的节点通信的前提下，通过关闭非骨干网节点的通信模块， 来延长网络生存期；第三章中，我们又进一步分析了基于功率控制的拓扑控制的 原理以及优化参数，并介绍了几种典型的算法。由前面的介绍可知，拓扑控制在 无线传感器网路中具有举足轻重的作用，拓扑控制算法的性能将直接决定了路由 算法的实现，并且在很大程度上影响了网络寿命。针对节点能量有限的特点，本 章将层次型拓扑控制和功率控制两种方式进行有效结合，提出一种能量有效的混 合式拓扑控制算法一e a h t c 算法。该算法优先选择剩余能量高的节点担任簇头 节点，而且算法采用局部信息，动态调节节点通信范围，改变一跳可达邻居数量， 从而减轻m a 层负担达到节能的目的。同时在网络运行过程中，算法通过周期 性重新选举簇头，减小并均衡网络中节点的能耗，从而进一步延长了网络的生存 期。 4 网络模型 用连通无向图口，矽来表示无线传感器网络，其中：y 是传感器节点集合， 是一组边集合，每条边e = ( u ，v ) e ( 其中u ，v v ) 表示节点u 与节点v 都 在彼此的无线通信范围内，即为邻居节点或称这两个节点相距一跳。一个节点的 跳邻居节点的数目称为该节点的度数。如果图g 的任何两个顶点u 和v 之间 都至少存在一条( u - - v 路，则称g 是连通的。对于给定的无向图g ( v ，e ) ，若 找到v 的一个子集i c _ v ，v v m ，v n i ，在图g 中没有边直接相连，则i 称为图g 的独立集。 第四章混合式拓扑控制算法 4 。相关知识 4 3 能量有效性 在无线传感器网络层次型拓扑控制算法中，节点被划分为簇头节点和簇成员 节点。虽然不同的分簇算法具有不同的目标，有的侧重于图的形状，有的侧重于 网络的稳定性，但是在层次型拓扑控制算法中簇头担当着举足轻重作用，要负责 簇内所有成员的管理、数据处理、数据转发等任务，因而其能量消耗远远大于簇 成员的能量消耗。因此，在设计层次型拓扑控制算法时，簇头的选择至关重要， 且应该将其能量有效性放在首位，同时应分布均匀，能够覆盖全网，并兼顾簇的 规模及资源的合理利用等方面。 4 3 环带模型 传感器网络多采用多跳中继通信，沿途的节点不仅要发送自己感测的数据， 还要转发其他节点的数据，多个测量点的数据以这种方式发送到槽节点s i n 。由 于传感器网络的多跳通信和多对一的数据传递特征，使得整个网络的能耗严重不 均衡。可用如图4 一所示的环带模型标识。 佬 弋 弋 瓷 犍岁 图4 - 1 能量不均衡环带模型 假定s i n 节点位于待测域的中心位置，节点分布均匀且采用相同的通信 半径。则我们可以将整个区域分为若干环带，如图4 一所示，第十环上节点的 数据首先发给第环上的节点，然后第环上的节点再将其转发给第一环上的 节点，以此类推，直至数据到达s i n 节点。 第四章混合式拓扑控制算法 距离s i n 节点越近，节点代为转发的数据越多，因而能量消耗越大。最终 网络的寿命是由s i n 节点周围的节点决定的。 4 4e a h t c ( e n e r g ya w a r eh y b r i dt o p o l o g yc o n t r o l 算法 4 4 算法假设 ( 1 ) 网络为静态网络，每个节点具有相同的硬件结构和信息处理能力，网 络中的节点已知自己的地理位置，且具有唯一的i d 。 ( 2 ) 不考虑由于竞争信道引起的延时或错误，即物理上相邻的节点能够正 确接收信息。 ( 3 ) 每个节点都带有功率可调的全向天线。 4 4 节点权值确定 算法需要节点生成一个权值来指示该节点适合充当簇头的程度，为了使簇头 的选择足够优化，节点的权值应综合考虑多方面的因素。首先，由于传感器节点 是能量有限的，簇头的选择应优先考虑节点的剩余能量，节点剩余能量越多，它 就越可能成为簇头节点。其次，簇头所管理的成员节点数量应该限制在合理的范 围内，一方面，管理的节点过多虽然可以提高系统的吞吐量，但是计算和维护开 销较大，且容易造成簇内多个节点发送的数据产生碰撞；另一方面，簇头管理节 点过少使得网络中簇头数增多，增大了网络的能量消耗。文献 4 0 通过对研究随 机图的边数和节点数之间的关系发现当网络的度数为时基本上能够保证网 络的连通度，且此时的网络拓扑具有较好的吞吐量和可靠性；第三，理想情况下， 传感器节点的发射功率是相同的，可是在现实环境中，各节点因为不同的天线性 能、不同的电池能量，而导致不同的发射功率。选取功率大的节点做簇头，辐射 的范围大，包含的节点多，可以减少簇头的总个数，提高了整个网络的吞吐率； 最后，在权值中反映节点i d ，使得各节点权值具有唯一性。综合考虑以上参数， e a h t c 借助a d h o 网络中的a o w 白适应按需加权算法的思想。利用式( 一l 计算节点v 的权值为： 3 5 第四章混合式拓扑控制算法 v = l e r + 2 丽+ 3 p + 一； ( 一1 ) 其中，e 表示节点剩余能量，d v 表示节点的度数，万表示节点的理想度数， 当或= 万时，令l i 以一o l = 。 为节点的最大发射功率，i d 为节点的唯一标识， - 、2 、，、 。为权重系数，代表了各种参数的重要程度，权重因子越大代表 该参数越重要，且满足l + 2 + 3 + 42 。 因为算法中权值越大的节点越有可能成为簇头节点，其计算方法实现了这种 要求。如果节点剩余能量越大，节点的连接度数越接近于理想度数，节点到邻居 节点距离平方的平均值越小，权值越大，节点也越有可能成为簇头节点。由于传 感器节点的能源约束是设计网络协议的主要考虑因素，e a h t c 设定c 的取值一 般要远远大于c 2 ，c ，即簇头的选择主要决定于能量，只有在剩余能量差别不大 时，节点的连接度数和发送功率才体现作用。而节点d 是在前三者生成权值相 同时才起作用，因此c 的取值非常小。 4 4 邻居探测 s i n k 节点发起邻居探测，所有节点以相同的最大通信半径发送h e l l o 消息， 消息中包括自己的i d 、权值、位置等信息。接收到h e l l o 消息，则将其信息存 入邻居表中。由于节点通信半径完全相同，节点间不可能存在单向链路，因此可 将整个网络用连通无向图口，矽表示。 4 4 分簇 节点处于以下三种状态中的一种： 1 ) 空白状态；2 ) 簇头状态；3 ) 簇成员状态； 节点发出以下两种消息： ( 1 ) l e a d e r ( i d ，w ) ：宣布自己为簇头的消息，i d 为自己的标识符，w 为自己的 权值； ( 2 ) m e m b e r ( i d c i d ) ：宣布自己为簇成员的消息，i d 同上，c i d 为要加入的 簇的簇头jd 。 邻居探测完成后，若节点发现自己比所有邻居权值都大，则以最大通信半径 3 6 第四章混合式拓扑控制算法 广播l e a d e r 消息，宣布自己为簇头。这样就选出了部分在邻居中权值最大的节 点作为簇头。其余节点状态按以下规则进行： 规则( a ) ：收到l e a d e r 消息 若为空白状态，则广播m e m b e r 消息，宣布自己加入该簇；若已为成员状态， 则进行计算，如果原簇头距离s i n k 节点更近，则宣布加入新簇，否则不变。 规则( b ) ：收到m e m b e r 消息 1 ) 若为簇头节点收到针对自己的簇成员广播，则将其加入成员信息表中， 如果针对其他节点的簇成员广播，则查看该成员是否是自己的成员，如果是，则 将其删除； 2 ) 若为空白节点收到该消息，则更新邻居表中该邻居的信息，并查看是否 所有权值大于自己的邻居都发出了m e m b e r 消息，如果是，则自己发出l e a d e r 消 息，宣布称为簇头： 3 ) 若为成员节点收到该消息，则不做任何处理。 现证明在给定的连通无向图口，矽，由上述算法得到的簇头节点集构成 了一个独立集。 证明：由算法描述可知，若节点v 宣布为簇头，则它周围所有相邻的节点皆 为簇成员状态，所以任何两个簇头节点都不可能是相邻的。因此由独立集的定义 可知，该算法得到的簇头节点集构成了一个独立集。 图例： 图4 _ 2 原始拓扑 假设网络拓扑如图4 所示，节点旁边的数字代表节点的能量值。该阶段过 程如下： s i n k 节点发起邻居探测后，图中1 1 个节点均得到了自己的邻居信息表。其 3 7 第四章混合式拓扑控制算法 中，节点5 、6 、1 0 节点由于比自己所有邻居的能量都大，宣布成为簇头。节点5 成为簇头以后，1 、2 、9 号节点会宣布成为5 的成员；节点6 成为簇头以后，7 、 8 号节点宣布成为6 的成员，9 号节点经过判断簇头6 到s i n k 节点的距离更远， 于是退出刚才加