（计算机应用技术专业论文）无线网络中能量高效的拓扑控制算法研究.pdf

曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ”) 本人郑重声明：此处所提交的博士口硕士留论文无线网络中能量高 效的拓扑控制算法研究，是本人在导师指导下，在曲阜师范大学攻读博士 口 硕士囱学位期间独立进行研究工作所取得的成果。论文中除注明部分外 不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡献的 个人和集体，均已在文中已明确的方式注明。本声明的法律结果将完全由本 人承担。 作者签名：锌海羊 日期：2 。肋c z 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“ ) 无线网络中能量高效的拓扑控制算法研究系本人在曲阜师范大学攻读博 士口硕士囱学位期间，在导师指导下完成的博士口硕士囱学位论文。本 论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的 名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同 意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和 借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可 以公开发表论文的全部或部分内容。 作者签名：钟涛。平 日期：2 - o 0 f2 i 导师签名溻印涪 日期：。占多 无线网络中能量高效的拓扑控制算法研究 摘要 一个无线传感器网络是由部署在一个地理区域的传感器节点组成的，用来监视物理现 象如温度、湿度、地震现象等等。典型的，一个传感器设备由三个基本部分组成：在周围 环境获得数据的传感系统；本地数据处理和存储的处理系统；数据传输的无线通信系统。 除此之外，还要有一个能源设备来提供系统完成任务所需要的能量。这个能源设备往往是 能量有限的电池。再者，给电池充电是不方便的也是不可能的，因为节点有可能是布控在 恶劣的环境中。另一方面，传感器系统用该有足够长的生命周期来满足应用的需要，在很 多情况下要求生命周期是几个月甚至是几年，因此，关键的问题就是怎样将生命周期延长 到这样长的时间。 传感器节点的移动性十分的灵活，它可以通过不同的方式实现，例如节点装备移动设 备改变位置，移动设别在能量消耗的观点来看是十分昂贵的，使节点的移动性不是很方便， 实际上由于移动性导致能量的消耗比能量的获得要大，因此，让特殊的节点移动而不是让 每个节点移动可以减少能量的消耗。在这种情况下，移动性和节点的异构性紧密相关。 综上所述，如何高效的使用能量成为无线网络拓扑控制研究中一个至关重要的问题。 本文主要研究了无线网络中的能量高效的拓扑控制机制，并得到了一些有价值的结 论。第一章介绍了研究的背景，问题的提出以及相关的工作，接着给出了文章的基本框架 结构。第二章给出了一个移动无线传感器网络中能量有效的拓扑控制算法。第三章介绍了 移动无线传感器网络中基于概率的最大权控制集的构造方法，最后对全文进行了总结，并 提出迸一步的研究方案。 关键词：无线网络；移动无线传感器网络；能量有效；拓扑控制；控制集 一一一 无线网络中能量高效的拓扑控制算法研究 a b s t r a c t aw i r e l e s ss e n s o rn e t w o r kc o n s i s t so fs e n s o rn o d e sd e p l o y e do v e rag e o g r a p h i c a la r e af o r m o n i t o r i n gp h y s i c a lp h e n o m e n al i k et e m p e r a t u r e ，h u m i d i t y ，v i b r a t i o n s ，s e i s m i ce v e n t s ，a n ds oo n t y p i c a l l y ，as e n s o rn o d ei s at i n yd e v i c et h a ti n c l u d e st h r e eb a s i cc o m p o n e n t s ：as e n s i n g s u b s y s t e mf o rd a t aa c q u i s i t i o nf r o mt h ep h y s i c a ls u r r o u n d i n ge n v i r o n m e n t ，ap r o c e s s i n g s u b s y s t e mf o rl o c a ld a t ap r o c e s s i n ga n ds t o r a g e ，a n daw i r e l e s sc o m m u n i c a t i o ns u b s y s t e mf o r d a t at r a n s m i s s i o n i na d d i t i o n ，ap o w e rs o u r c es u p p l i e st h ee n e r g yn e e d e db yt h ed e v i c et o p e r f o r mt h ep r o g r a m m e dt a s k t h i sp o w e rs o u r c eo f t e nc o n s i s t so fab a a e r yw i t hal i m i t e d e n e r g yb u d g e t i na d d i t i o n ，i tc o u l db ei m p o s s i b l eo ri n c o n v e n i e n tt or e c h a r g et h eb a r e r y ， b e c a u s en o d e sm a yb ed e p l o y e di nah o s t i l eo ru n p r a c t i c a le n v i r o n m e n t o nt h eo t h e rh a n d ，t h e s e n s o rn e t w o r ks h o u l dh a v eal i f e t i m el o n ge n o u g ht of u l f i l lt h e a p p l i c a t i o nr e q u i r e m e n t s i n m a n yc a s e sa l i f e t i m ei nt h eo r d e ro fs e v e r a lm o n t h s ，o re v e ny e a r s ，m a yb er e q u i r e d m o b i l i t yo fs e n s o rn o d e si sa c t u a l l yf e a s i b l e ，a n di tc a nb ea c c o m p l i s h e di nd i f f e r e n tw a y s f o re x a m p l e ，s e n s o r sc a nb ee q u i p p e dw i t hm o b i l i z e r sf o rc h a n g i n gt h e i rl o c a t i o n a sm o b i l i z e r s a r eg e n e r a l l yq u i t ee x p e n s i v ef r o mt h ee n e r g yc o n s u m p t i o ns t a n d p o i n t ，a d d i n gm o b i l i t yt os e n s o r n o d e sm a yb en o tc o n v e n i e n t i nf a c t ，t h er e s u l t i n ge n e r g yc o n s u m p t i o nm a yb eg r e a t e rt h a nt h e e n e r g yg a i nd u et om o b i l i t yi t s e l f s o ，i n s t e a do fm a k i n ge a c hs e n s o rn o d em o b i l e ，m o b i l i t yc a n b el i m i t e dt os p e c i a ln o d e sw h i c ha r el e s se n e r g yc o n s t r 萄n e dt h a nt h eo r d i n a r yo n e s i nt h i sc a s e ， m o b i l i t yi ss t r i c t l yt i e dt ot h eh e t e r o g e n e i t yo fs e n s o rn o d e s t h e r e f o r e ，t h ec r u c i a lq u e s t i o ni s ： h o wt op r o l o n gt h en e t w o r kl i f e t i m et os u c ha l o n gt i m e a sar e s u l t ，h o wt ou s et h ee n e r g ye f f i c i e n t l ym a k e st h et o p o l o g yc o n t r o la nk e yp r o b l e mi n w i r e l e s ss e n s o rn e t w o r k i nt h i st h e s i sw em a i n l yd i s c u s s e dt h e e n e r g ye f f i c i e n tt o p o l o g yc o n t r o lm e c h a n i s mi n m o b i l ew i r e l e s ss e n s o rn e t w o r k sa n dg o ts o m ec o n c l u s i o n s i nt h ef i r s tc h a p t e rw ei n t r o d u c e dt h e b a c k - g r o u n do fo u rs t u d y ，t h er e l a t e dw o r ka n dt h es t r u c t u r eo fo u rt h e s i s i nt h es e c o n dc h a p t e r w ei l l u m i n a t e da ne n e r g ye f f i c i e n tt o p o l o g yc o n t r o la l g o r i t h mi nm o b i l ew i r e l e s sn e t w o r k i nt h e t h i r dc h a p t e rw eg a v eam e t h o dt oc o n s t r u c tt h em a x i m u m - w e i g h t e dd o m i n a t i n gs e tb a s e d p r o b a b i l i t yi nm o b i l ew i r e l e s ss e n s o rn e t w o r k ，a tl a s tw ec o n c l u d e dt h ew h o l et h e s i sa n d p r e s e n t e dt h ef u t u r ew o r k k e y w o r d s ：w i r e l e s sn e t w o r k ；m o b i l ew i r e l e s ss e n s o rn e t w o r k ；e n e r g ye f f i c i e n t ； t o p o l o g yc o n t r o l ；d o m i n a t i n gs e t h 无线网络中能量高效的拓扑控制算法研究 目录 第一章前言1 1 1 研究背景和研究现状1 1 1 1 研究背景2 1 1 2 研究现状4 1 2 论文结构和内容6 第二章移动无线传感器网络中能量有效拓扑控制算法7 2 1 准备工作7 2 2 算法设计7 2 2 1 计算一跳邻居表7 2 2 2 一跳邻居列表的消减8 2 3 算法的细节描述9 2 4 算法的有效性分析1 0 2 5 仿真工具介绍1 1 2 5 1n s 2 简介1 1 2 5 2 使用n s 2 进行网络仿真的方法和一般过程11 2 5 3n s 2 的功能模块1 2 2 5 4n s 2 的软件构成1 2 2 5 5n s 2 现有的仿真元素l3 2 6 仿真结果13 第三章移动无线传感器网络中基于概率的最大权控制集l6 3 1 准备工作1 6 3 2 算法设计18 3 3 算法分析。18 3 4 仿真结果2 0 第四章总结和展望21 参考文献2 2 在校期间发表的学术论文2 5 致谢2 6 i l l 无线网络中能量高效的拓扑控制算法研究 第一章前言 1 1 研究背景和研究现状 在最近几年，无线传感器网络无论是在研究还是在应用领域都引起了很多的关注。传 感器节点最为一个电池设备，要面对的最重要的一个方面就是怎样减少能量消耗，只有这 样无线传感器网络的生命周期才能延长到合理的时间，无线传感器网络应用前景十分广阔 i ij ，它在环境监测、国家安全、空间探索、交通管理等领域具有非常巨大的应用价值，从 而引起了工业界、军界和学术界的高度关注。2 0 0 3 年，在美国的技术评论中，无线传 感器网络成为十大新兴技术之首i 卫。2 0 0 5 年，在德国柏林召开了欧洲第1 届专业传感器网络 会议。同年，a c m 增设传感器网络研究专刊t o s n ( t r a n s a c t i o n so n s e n s o rn e t w o r k s ) 。科技工 作者提出了大量无线传感器网络的研究课题，拓扑控制是其中的一个基本问题，拓扑控制 就是要形成一个优化的网络拓扑结构，它是传感器网络中许多其他研究课题的基础p j 。 一个无线传感器网络是由部署在一个地理区域的传感器节点组成的，用来监视物理现 象如温度，适度，地震现象等等。典型的，一个传感器设备由三个基本部分组成：在周围 环境获得数据的传感系统；本地数据处理和存储的处理系统；数据传输的无线通信系统1 4 i 。 除此之外，还要有一个能源设备来提供系统完成任务所需要的能量。这个能源设备往往是 能量有限的电池。再者，给电池充电是不方便的也是不可能的，因为节点有可能是布控在 恶劣的环境中i 蜘。另一方面，传感器系统用该有足够长的生命周期来满足应用的需要，在 很多情况下要求生命周期是几个月甚至是几年，因此，关键的问题就是怎样将生命周期延 长到这样长的时间巾i 。 在一些情况下可以在外部环境中提取能量1 7 l ( 比如用太阳能纽扣电池作为能源) ，然而， 外部能源供给设备经常表现出不连续的特点，这样就需要一个能量缓冲设备。在一些情况 下能量是非常宝贵的资源，要非常节俭的使用。因此能量保持是一个设计无限传感器网络 的要考虑的十分重要的问题。 实验表明数据传输在能量消耗中是十分昂贵的降i ，而数据处理耗能则相对少一些，传 输一位信息的能耗近似于一千个操作消耗的能量。传感系统的能量消耗主要取决于不同的 传感类型，有些情况中尤其是通信系统中处理消耗的能量是可以忽略不计的，而在有些情 况下传感数据消耗的能量可能比数据传输的能量还要大，总体而言，节能技术主要关注两 个子系统1 9 l ：网络子系统( 如在协议的设计中要考虑单节点操作的能量管理) 和传感子系 统( 如减少大量的或者频繁的高能耗事件的技术) 。 通过引进不同的应用技术可以延长网络的生命周期i l 们，例如，能量有效的协议目的在 于最小化网络在活跃期的能量消耗，然而大部分的能量消耗来自于节点的元件( 如c p u ， 天线等等) ，即使他们闲置的时候也是这样。能量管理方案就是在节点临时不用的情况下 关闭这些元件。 无线网络中能量高效的拓扑控制算法研究 传感器节点的移动性十分的灵活，它可以通过不同的方式实现，例如节点装备移动设 备改变位置，移动设别在能量消耗的观点来看是十分昂贵的，使节点的移动性不是很方便， 实际上由于移动性导致能量的消耗比能量的获得要大，因此，让特殊的节点移动而不是让 每个节点移动可以减少能量的消耗i l 。在这种情况下，移动性和节点的异构性紧密相关。 另一方面，与其提供移动设备，不如让节点分布在自己可以移动的实体上( 如动物、汽车 等等) 。在这种情况下有两个不同的选择，首先所有的节点分布在活动实体上使得所有的 节点都是移动的1 1 2 l 。另一种方法只有一部分特殊的节点是移动的，其它节点是静止的。无 论如何两种方法都没有移动性产生的能量消耗，但是移动元素在设计网络是要考虑到。 移动性也可以减少能量的消耗i l 引，来传感器的包通过多跳的路径在网络中传向基节 点，当基节点是静态的时候，一些路径的负载要比其他路径重，这取决与网络的拓扑和源 节点包的产生。靠近基节点的节点转发很多的包，所以过早的经受能量枯竭问题，即使是 使用了能量保持技术。另一方面，如果一个移动设备负责数据的收集( 移动数据收集者) 就会改变信息流量，普通节点等待移动设备的信息和向他的路由消息，所以与移动收集者 的通信是近距离发生的( 直接或者有限的多跳) ，结果普通的节点节省了能量，另外移动 设备为了分散数据通信产生的能量消耗而访问网络。 无线传感器网络一般具有这样的网络特性：自组织、随机部署、大规模、传感器节点 资源有限、环境复杂、网络拓扑经常发生变化i l 引。由于这些特性的存在，使拓扑控制成为 具有挑战性的研究课题。与此同时，这些特性也使得拓扑控在无线传感器网络研究中变得 十分重要：首先，拓扑控制是一种重要的节能技术；其次，拓扑控制保证覆盖质量和连通 质量1 1 5 i ；再次，拓扑控制能够提高m a c ( m e d i aa c c e s sc o n t r 0 1 ) 协议和路由协议的效率、降 低通信干扰，为数据融合提供拓扑基础；此外，拓扑控制能够提高网络的可扩展性、可靠 性等其他性能。总之，拓扑控制对网络性能具有重大的影响，因而对它的研究具有十分重 要的意义1 1 6 l 。 1 1 1 研究背景 目前，拓扑控制研究已经形成功率控制和睡眠调度两个主流研究方向1 1 7 l 功率控制，就 是为传感器节点选择合适的发射功率；睡眠调度，就是控制传感器节点在睡眠状态和工作 状态之间的转换。 拓扑控制研究的问题是：在保证一定的网络连通质量和覆盖质量的前提下，一般以延 长网络的生命期为主要目标，兼顾通信干扰、负载均衡、网络延迟、可靠性、简单性、可 扩展性等其他性能，形成一个优化的网络拓扑结构。无线传感器网络是与应用相关的，不 同的应用对底层网络的拓扑控制设计目标的要求也不尽相同。下面介绍拓扑控制中一般要 考虑的设计目标和相关的概念、结论。 ( 1 ) 覆盖：覆盖可以看成是对传感器网络服务质量的度量。在覆盖问题中，最重要的 因素是网络对物理世界的感知能力f l 引。覆盖问题可以分为区域覆盖、点覆盖和栅栏覆盖 2 无线网络中能耸高效的拓扑控制算法研究 ( b a r rie rc o v e r a g e ) 0 9 1 。 ( 2 ) 网络生命周期：网络生命期有多种定义。一般将网络生命周期定义为直到死亡节点 的百分比低于某个阈值时的持续时间1 2 叭。也可以通过对网络的服务质量的度量来定义网络 的生命1 2 l i 。 ( 3 ) 干扰和竞争：减小通信干扰、减少m a c 层的竞争和延长网络的生命期基本上是一 致的1 2 2 l 。网络无线信道竞争区域的大小与节点的发射半径r 成正比嘲，所以减小r 就可以 减少竞争。睡眠调度显然也可以通过使尽可能多的节点睡眠来减小干扰和减少竞争。 ( 4 ) 网络延迟：当网络负载较高时，低发射功率会带来较小的端到端延迟；而在低负 载情况下，低发射功率会带来较大的端到端延迟1 2 4 。 ( 5 ) 拓扑性质：事实上，对于网络拓扑的优劣，很难直接根据拓扑控制的终极目标给 出定量的度量。因此，在设计拓扑控制( 特别是功率控制) 方案时，往往退而追求良好的拓 扑性质。除了连通性之外，对称性、平面性、稀疏性、节点度的有界性、有限伸展性等， 都是希望具有的性质i z 引。 此外，拓扑控制还要考虑诸如简单性、负载均衡、可靠性、可扩展性等其他方面。拓 扑控制的各种设计目标之间有着错综复杂的关系。对这些关系的研究也是拓扑控制研究的 重要内容。 对动态无线传感器网络，由于节点移动的特性使得网络拓扑不断的变化，因而使得网 络中存在着很多不确定因素，比如一个节点的邻居节点不是一定的；网络的连通性也是时 刻变化的。在拓扑变化以后要求节点做出相应的重配置使其适应变化后的网络，然而如果 拓扑变化的很快，重配置就会经常发生，从而消耗很多的能量，这就要求能量和通信质量 之间均衡。总之，连通性、通信负载和能量有效性之间的均衡问题是移动传感器网络中具 有挑战性的问题i 拍j 。 在移动无线传感器网络中，大多数路由协议牵扯到泛洪，这经常会导致广播风暴1 2 7 1 。 由控制集所组成的虚拟骨干网来避免广播风暴是一种行之有效的方法。在控制集的帮助 下，网络中的平均信息负担减少了，这样就使得路由协议变得更加简单，并且能更快的使 用网络拓扑的变化1 2 引。再者，在移动传感器网络中，由于种种条件的限制，传感器一旦布 控以后就很难对其进行更换电池或者对电池充电，这就使得在能量来自电池的传感器网络 中有效的使用能量成为设计网络时必须要考虑的重要问题，由控制集中的节点担任传输节 点可以有效的减少网络中的能量消耗。由此看来在移动无线传感器网络中构建控制集是十 分必要的。 控制集( d s ) 问题是指给出一个图g _ ( ve ) ，找出一个子集d v 使得对任意的节 点1 ，v ，要么，d ，要么 ，有一个邻居在d 中。如果这个子集d 是连通的，那么这个子 集d 就叫做连通控制集( c d s ) 。这些问题众所周知是n p 完全问题1 2 引。最大权控制集 ( m w d s ) i h 题是由控制集问题引申出来的，它是找出带权图g 中的一个控制集使得总的权 值和最大。如今有很多关于静态网络中构造各种性质的控制集的近似算法，然而在动态网 无线网络中能量高效的拓扑控制算法研究 络中构造控制集的近似算法却很少。 1 1 2 研究现状 拓扑控制的概念是与网络冗余紧密联系的，密集的网络有典型的度冗余，在很多情况 下，网络的布控是随机的，例如通过飞机播撒传感器节点，因此比起在节点出现故障时或 者以后就处理，这种布控大规模节点的方法还是很方便的。在很多情况下开始布控许多节 点比起需要时重新布控额外的节点要容易的多，也由于相同的原因，冗余布控比起手工的 布控要容易的多。拓扑控制的目标在于动态的，自适应的网络拓扑，基于网络的应用，使 得最小化活跃节点的数目来延长网络的生命周期。 在静态传感器网络中已经有很多关于能量有效的拓扑控制的研究，比如l e a c h ( l o w e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) 1 3 0 l 算法是一种自适应的分簇拓扑算法，有的学者针对 l e a c h 算法节点规模小，簇头选举没有考虑节点的地理位置等不完善的地方，提出了改 进算法h e e d ( h y b r i de n e r g ye f f i c i e n td i s t r i b u t e dc l u s t e r i n g ) i , t l l os t e m ( s p a r s et o p o l o g y a n de n e r g ym a n a g e m e n t ) 1 3 2 l 算法是一种低占空比的唤醒机制。文献 3 3 】的作者设计了一种 e e c c p 算法，由于他考虑了边界效应的影响和设计的最短路由路径，所以这个算法的仿真 结果也很好。 g a f ( g e o g r a p h i c a la d a p t i v ef i d e l i t y ) 是一个保持恒定路由精度来减少能量消耗的位置 驱动的协议，节点分布的传感区域被分成小的网格，每个网格是这样定义的：对于相邻的 网格a 和b ，所有a 中的节点可以与b 中的节点通信，反之亦然。在同一个网格中的所 有节点在路由上是相等的，只有一个节点是活跃的。因此节点可以和其他节点合作决定那 个节点应该睡眠，睡眠多长时间。 起初节点是一个发现状态，这个状态中节点与其他节点交换发现信息。广播信息以后， 节点进入活跃状态，当在活跃状态是，节点周期的广播发现信息，一个节点当发现另一个 节点要占用路由时，它可以从发现状态或者活跃状态进入睡眠状态，节点经过一段时间的 睡眠状态唤醒后进入发现状态，g a f 中的负载均衡是通过周期的重新选举节点来实现的， 例如节点为了管理路由始终保持活跃状态。头结点的选择是通过考虑剩余能量的基于级别 的算法，因此在适当的节点比例下延长的了网络的生命周期，g a f 是一个独立的路由协议 以至于他看可以应用于任何解决这一问题的方法。除此之外，g a f 在包丢失和信息的延迟 方面没有影响到路由的性能，然而网络的结构导致了低的覆盖范围利用率，实际上，网格 内的所有节点必须能和相邻网格的节点通信，实际上节点应该能够覆盖广播半径的不到一 半的距离。 作为地理位置的路由协议，g e r a f ( g e o g r a p h i cr a n d o mf o r w a r d i n g ) 提出了一个基于 位置驱动和占空比的操作，这利用了节点的位置和冗余性。节点根据给定的占空比进入活 跃和睡眠状态，节点周期的进入活跃状态，从个监听时间开始以至于他可以根据需要随 时加入路由。当有包需要发送的时候数据传输丌始，在这种情况下，节点进入活跃状态并 4 无线网络中能量高效的拓扑控制算法研究 且广播自己的位置信息和目的节点的位置信息，接着接受者的接受阶段开始了。除了优先 权以为，一个分布随机的方案用来减少相邻的节点同时进入睡眠的概率。特别的，接近目 标节点的发送节点覆盖范围的一部分被分成许多的区域，每个区域有自己的优先级，这样 比起优先级别低的节点，优先级高的节点就会被选择。 在广播以后，优先级高的节点用来传输数据。如果只能一个节点占用信道，就只能简 单的把包向前传到处理终端。否则，许多节点可以同时发送数据，从而导致碰撞，一个技 术( 回退) 用来选择单个传输者。也可能有这样的情况，所有的节点都不是传输者，因为 他们都在睡眠区域，在这种情况下，在下个传输任务之f ； ，将选择第二高的优先级的节点 作为传输者。中继选择阶段一直重复以达到最大数目的节点。最后，通过一跳一跳的传输 包被传送到目的节点。注意到，中继的选择在时间上是较晚的，所以g e r a f 几乎不需要地 理位置信息，它也不需要拓扑的信息和路由表。 s p a n 是一个在网络中所有节点中选择合作者的连通性驱动的协议，协作者一直保持活 跃状态执行多跳路由，其他的节点进入睡眠状态并且周期的检查是否需要唤醒变成协作 者。为了保证足够数目的协作者s p a n 采用了合格协作者规则：如果两个相邻的非协作者 节点不能够直接互相通信，或者通过一个或多个协作者节点，那么节点互为协作者。然而， 几个节点同时发现缺少协作者也是可能发生的，他们将同时决定变成协作者，为了避免这 种情况，节点通过一个随机的回退延迟来决定成为协作者，每个节点利用一个函数产生随 机的时间，这个函数同时考虑邻居节点中潜在的协作者数目和剩余能量。基本的原则是： ( i ) 有更多剩余能量的节点应该最大可能的自愿成为协作者。( i i ) 协作者的选择方式应 该尽量的减少他们的数量。每个协作者周期的检查它是否应该退出协作者。更具体的说， 一个节点应该退出协作者当他的每一对节点都可以直接通信或者通过其他的协作者。为了 避免失去连通性，旧的协作者在新的协作者可用之前将继续工作，s p a n 选择算法需要知道 邻居节点的信息和连通性的信息来决定一个节点时候成为协作者。这些信息由路由协议提 供。 a s c e n t ( a d a p t i v es e l f - c o n f i g u r i n gs e n s o rn e t w o r k st o p o l o g i e s ) 是连通性驱动的协 议，与s p a n 不同，它不依靠路由协议。在a s c e n t 中一个节点通过连通性和节点自己衡 量的包丢失信息决定是否加入网络或则继续睡眠。a s c e n t 最基本的思想是起初只有几个 节点是积极的，其他的节点是消极的。例如：它们监听包，但不转发，如果活跃节点的数 目不是足够的，基节点将遭受很高的消息丢失，基节点将发送求助信息给他的邻居节点， 请他们加入网络从消极状态转入积极状态，消极节点保持无线设备开启并监听所有的传向 积极邻居的包，然而它不传送数据包或者交换路由信息，他们只在不打扰其他节点的情况 下收集网络结构的信息，相反，积极节点传送数据包和路由信息知道他们能量用完。积极 节点在发现严重的数据丢失的时候也可以发送求助信息。只要加入网络，节点就开始监听 网络状念，并且通过邻居宣告信息宣布自己是积极节点，这个过程一直继续直到丢包率达 到预先给定的阈值，当网络状态改变( 节点失效) 或者环境的变化导致丢包率上升，这个 无线网络中能量高效的拓扑控制算法研究 过程将重新开始。像前边提到的一样，a s c e n t 是路由协议独立的。除此之外，由于把节 点的密度所谓考虑的参数，它限制了碰撞导致的信息丢失，最后，这个协议有很好的性能。 另外，能量的节省没有成比例的增加，因为它取决与消极睡眠周期而不是活跃节点的数目。 l i a n gz h a o 等人彤i 提出了一种算法来解决匀速移动传感器网络中的拓扑控制问题，他 们假设节点在自己的运动轨迹上匀速运动，然而这个模型有以下的缺点：( 1 ) 整个算法 是集中式算法，缺少实际应用性。( 2 ) 匀速运动模型过于理想化，不实际，现实中的节 点很少是一直在做匀速运动的，这就大大限制了它的应用。j i a n b ol i 等人提出了一种变速移 动传感器网络的拓扑控制算法( v r m n ) l a s j ，它对匀速移动网络模型进行了改进，考虑的节 点的变速移动，假设节点在一条由起始位置和终止位置确定的线段上移动，通过计算节点 之间的最大距离先找出节点的一跳邻居，然受通过一个类x t c 过程删除一跳邻居表中一些 节点，使得更加的能量有效。然而这个模型也存在着一些问题：( 1 ) 节点的移动模型还 是有很大的局限性，实际的节点不会只在一条线段上做运动。( 2 ) 一跳邻居的计算方法 存在问题，由于节点移动性的原因，在发送半径以外的节点不一定就不能通信，等它移动 到发送半径范围内就可以成为一跳邻居。( 3 ) 类x t c 过程中可能删掉不应该删除的一跳 邻居。 1 2 论文结构和内容 论文的第一章介绍了研究现状和研究背景，给出了本文做的主要研究工作和文章的框 架结构。 第二章给出了一个移动无线传感器网络中能量有效的拓扑控制算法，采用一个新的运 动模型，借助中继区和类g e r a f 方法给出了一个能量有效的拓扑控制算法。理论分析与仿 真结果表明，该算法可以节省更多的能量，是一个能量有效的拓扑控制算法。 第三章给出了移动无线传感器网络中基于概率的最大权控制集的构造方法，并证明了 当网络中的最小权顶点覆盖与最大权控制集的权值之比s 很小的时候，我们算法的近似因 子是十分接近l 的。 最后对全文进行总结，并提出进一步的研究目标。 6 无线网络中能量高效的拓扑控制算法研究 第二章移动无线传感器网络中能量有效拓扑控制算法 由于在移动无线传感器网络中很难对电池进行充电或者更换电池，所以节省能量消耗 成为无线传感器网络中的一个重要问题。本文采用一个新的运动模型，借助中继区和类 g e r a 方法给出了一个能量有效的拓扑控制算法。理论分析与仿真结果表明，该算法可以节 省更多的能量，是一个能量有效的拓扑控制算法。 2 1 准备工作 无线传感器网络通常被模拟成图g = ( v ，e ) ，其中v 节点集代表着网络中的所有传感器 节点，e 边集中的边代表传感器节点之间的链路。为了方便讨论，我们假设所有传感器节 点有相同的发射半径r ，节点v 的一跳邻居列表定义为( f ) ，节点v 在一个以o i 为圆心，：为 半径的圆形区域内自由移动。节点v 的功率定义为致，我们采用采用一个广泛应用的模型： 髟= q a ( 1 ) 这里c 是一个常数，口是能力衰减指数，r 是发射节点与接收节点之间的距离。 下面我们给出中继区的概念1 3 6 l ：已知节点f 和，对于任意的节点x ，如果有 b 。 只。+ p ，+ ，那么x 所在的区域就定义为节点f 关于，的中继区，记为b 。这里见嘶 表示从口到b 直接通信的最小功率。中继区的边界渐近的逼近与节点f 和，的垂线。图2 - 1 是一个中继区的例子。 图2 - 1 中继区 2 2 算法设计 我们把移动传感器网络的生命周期分成单位时问段，我们只要保证在每个时间段内 m w s n 的连通性和能量有效性就可以了。 2 2 1 计算一跳邻居表 根据我们前边的假设，节点v f 在一个以d f 为圆心，为半径的圆形区域内自由移动， 这是我们提前知道的。那么任意两个节点( v ，v ，) 之问的最大距离就可以容易的计算出来： d i s t ( e ，) = jd f e l + + o ( 2 ) 7 无线网络中能量高效的拓扑控制算法研究 这里h d f | 表示两个圆心之问的距离。有了上述的定义，那么与v ，的最大距离d i s t ( v , ，1 ，) 小 于最大发射半径r 的节点 ，显然会成为节点e 的一跳邻居。基于这个理论，在算法的这一 步，我们让节点k 以最大发射半径r 发射一个信息，收到消息的节点向节点l 反馈他们移 动区域的圆心位置和半径信息。节点v 收到反馈以后，计算与他们的最大距离，离它最大 距离小于r 的节点放入它的一跳邻居列表中。这里需要注意的是，与v ，的最大距离大于r 的 节点也可能成为它的一跳邻居，因为q 确实接到了它的反馈，只是它有时会移动到v 无法 通信的范围。我们把这样的节点也放入v 的一跳邻居节点列表中。这样在v 的一跳邻居列 表中我们再加一个属性，把d i s t ( v ，v j ) 小于r 的邻居赋值为l ，把d i s t ( v , ，1 ，) 大于r 的邻居赋 值为o 。 2 2 2 一跳邻居列表的消减 对于列表中属性是1 的节点，根据中继区的概念，在v 的一跳邻居列表中，如果存在这 样的两个邻居1 ，和使得只i 只，+ p 。t ，j g a , g 然k 在v f 关于v ，的中继区内，这样直 接由v ，向u 发送消息所消耗的能量是比经过中继节点，转发消耗的能量多，这样我们就把 咋在m 的l ( i ) q u 删除。这里会出现这样的一种情况：假设节点e 和邻居x ，y ，z ，节点y 在如， 节点z 在灭。，显然这里我们应该把y 和z 在v 的一跳邻居列表中删除，但是如果我们先删 除了节点y ，那么z 就会保留下来。如图2 2 所示。为了防止这种情况的发生，我们把一跳 邻居列表中的节点按距离降序排列，从距离最远的节点开始删除，这样就不会出现上述的 情况了。 z 图2 - 2 中继区中的特殊情况 列表中属性是0 的节点，由于它有时会和v 失去通信，所以寻找他们的中继节点是不现 实的。我们对他们发送消息采取类 n g e r a f l 3 7 1 的方法。既然节点能接受到他们的反馈信息， 说明他们会出现在v 。的发射半径以内，我们让v f 首先向a i 区域内发送消息，由a i 区域内的 节点负责转发，如果4 内没有节点可以负责转发，那么在4 区域内寻找转发节点，依次类 推。4 的内半径是r 2 + r ( i 一1 ) 2 n ，( f = l ，n ) ，宽度是r 2 n 。图2 3 个一个n 等于4 的例 子。 8 2 3 ( 2 ) 把三( f ) 中的一跳邻居按照距离如f ( h ，屹) 降序排列成( v l ，v ：，v , m ) ( 3 ) 将三( d 广播给( f ) 中的每个节点 ( 4 ) 对于e l ( i ) p 以升序的顺序执行以下步骤 ( a ) 如果节点，。的属性是0 g e r a f ( ) ( b ) 如果节点，的属性是1 i f ( 3 k ，& l ( k ) & d i s t ( v f ，) 口+ d i s t ( v 睹，) 4 w ( s ) ，与最大权 值相矛盾。所以最大权值独立集是一个极大独立集。 定理3 ：极大独立集是一个控制集1 3 9 j 。 由上面得定理1 3 可以得出，我们的算法确实返回了一个权值最大的控制集。 定理4 ：最大权控制集问题是n p 完全的。 证明：最大权控制集的补集就是最小权顶点覆盖，我们很容易的可以把最大权控制集 问题规约到最小权顶点覆盖问题，由于最小权顶点覆盖问题是n p 完全的，所以最大权控 制集问题也是n p 完全的。 由于最大权控制集问题是n p 完全的，所以我们的算法也就是个近似算法，下面我们 来看一下算法的近似因子。 定理5 ：假设最小权顶点覆盖与最大权控制集的权值之比不超过s ，我们的算法的近 似因子为1 一占。 证明：算法的i j 一部分是构造最小权值顶点覆盖的算法，它的近似因子2 ，现在我们 假设算法返回最大权值控制集为s ，最优值为s ，那么v - s 就是最小权值顶点覆盖算法返 回的顶点覆盖，v - s 掌就是最小权值顶点覆盖的最优值。因为最小权值顶点覆盖近似算法的 近似因子是2 ，所以w ( y s ) 2 w ( v s 木) ，由于整个图的权值总和是一个定值，我们用w 来表示，则