（应用数学专业论文）无线传感器网络自适应拓扑控制研究.pdf

河南大学研究生硕士学位论文第l 页 摘要 拓扑控制是无线传感器网络研究的核心问题之一。以高密度部署的无线传感 器网络通过基于覆盖控制的节点调度、功率控制等手段，在不影响网络覆盖性、 连通性的前提下，减少网络中活跃节点的数量，减小节点发射功率，减少信道冲 突，降低了节点的能耗，从而达到延长网络生存时间的目的。 本文为解决网络能耗瓶颈问题进而延长网络生存时间，分别从覆盖控制、功 率控制和与其他层协议相结合三个方面进行研究，提出了自适应节点调度算法、 非均匀功率控制算法和与路由相结合的拓扑控制机制。 一、节点自适应覆盖调度算法，节点通过对最远盲区顶点的覆盖方法降低网 络的覆盖冗余，在仅根据邻居信息和保证网络覆盖要求的前提下，逐层扩散调度 命令，尽可能使更多的节点休眠。在预定的网络模型下，算法执行后极大的降低 了网络的覆盖冗余，减轻了由于冗余数据造成的网络负担。 二、非均匀功率控制算法，为解决由于功率控制而加剧的“热区问题”，算法 通过s i n k 节点逐层向外建立梯度用于控制功率控制协议中的邻居密度控制因子， 在降低网络发射功耗和保持网络连通度中寻找折衷方案。仿真证明方案使得网络 的负载均衡性得到了很大的提高，为路由协议和m a c 协议提供了基础，有效的缓 解了“热区问题”。 三、与路由协议相结合的拓扑控制机制，由于网络拓扑结构的改变将影响到路 由路径长度以及节点间的连通性，所以路由协议与拓扑控制协议有密切的关系， 算法通过设计的权重函数和节点类别转换机制使得数据在路由的过程中充分考虑 节点休眠状态、路由历史、当前能量等相关信息并在路由的过程中进行功率的适 应性调整，充分利用拓扑控制信息提高网络数据通信的负载均衡性，延长网络生 存时间，仿真实验证明拓扑控制与路由协议的结合能大大延长网络的生存时间。 关键词：无线传感器网络；覆盖控制；功率控制；自适应 第l i 页河南大学研究生硕士学位论文 a b s t r a c t t o p o l o g yc o n t r o lo fw i r e l e s ss e n s o rn e t w o r k si st h ec o r ei s s u eo fw i r e l e s ss e n s o r n e t w o r k i nw i r e l e s ss e n s o rn e t w o r ko fh ig h d e n s i t yd e p l o y m e n t ，n e t w o r kt o p o l o g y c o n t r o lt e c h n o l o g yt h r o u g hc o n t r o l b a s e dc o v e r a g eo ft h en o d es c h e d u l i n g ，p o w e r c o n t r o la n do t h e rm e a n st or e d u c et h en u m b e ro fa c t i v en o d e sa n dr e d u c i n gt h en o d e t r a n s m i s s i o np o w e ra n dr e d u c ec h a n n e lc o n f l l e ta n dr e d u c et h en o d e se n e r g y c o n s u m p t i o nw i t h o u ta f f e c t i n gt h ep e r f o r m a n c eo fn e t w o r kc o v e r a g ea n dc o n n e c t i v e s o a st oe x t e n dt h en e t w o r kl i f et i m e i nt h i sp a r p e r ，t os o l v ee n e r g yb o t t l e n e c kp r o b l e m si nt h en e t w o r ka n dt h u se x t e n d t h es u r v i v a lt i m e o ft l l en e t w o r k , s t u d yf r o mc o v e r i n gc o n t r o l l i n g t h r e er e s p e c t st h a t p o w e rc o n t r o l sa n dc o m b i n e sw i t ha n do t h e rl a y e r so fa g r e e m e n t ss e p a r a t e l y p a p e rp u t s f o r w a r dan e ws c h e d u l i n ga l g o r i t h mb a s e do nn o d ea d a p t i v ec o v e r a g e n o n u n i f o r i l l p o w e rc o n t r o l 鲥g o f i t h ma n dw i t ht h er o u t i n gb yac o m b i n a t i o no ft o p o l o g yc o n t r o l m e c h a n i s m s f i r s t ，t h en o d ec o v e r a g ea d a p t i v es c h e d u l i n ga l g o r i t h m ，t h en o d et h r o u g ht h eb l i n d s p o ta sf a ra sc o v e r a g eo fw a y st or e d u c ep e a kn e t w o r kr e d u n d a n c y , a c c o r d i n gt ol o c a l i r f f o r m a t i o na n de n s u r en e t w o r k c o v e r a g er e q u i r e du n d e rt h ep r e m i s eo ft h e p r o l i f e r a t i o no fl a y e r - b y - l a y e rs c h e d u l i n go r d e r , a sf a ra sp o s s i b l e ，s ot h a tm o r e n u m b e r o fd o r m a n tn o d e s i nt h ea s s u m p t i o nn e t w o r km o d e lc o n d i t i o n s t h ea l g o r i t h mg r e a t l y r e d u c e da f t e rt h ei m p l e m e n t a t i o no ft h en e t w o r kr e d u n d a n c yc o v e r a g e ，t h e r e b yr e d u c i n g r e d u n d a n td a t ad u et ot h eb u r d e nc a u s e db yt h en e t w o r k s e c o n d n o n - u n i f 0 1 t np o w e rc o n t r o la l g o r i t h m t oe n h a n c et h ep r o b l e mo ft h e e x a c e r b a t i n g ”h o tz o n e ”b e c a u s eo ft h ep o w e rc o n t r 0 1 s i n kn o d es t e pb ys t e pt h r o u g h t h ee s t a b l i s h m e n to ft h eg r a d i e n ti su s e dt ob eac o n t r o lf a c t o ro fp o w e rc o n t r 0 1 i nt h e r e d u c t i o no fe n e r g yc o n s u m p t i o na n dm a i n t a i nc o n n e c t i v i t yt of i n dac o m p r o m i s e t h e s i m u l a t i o np r o v e dt h a tt h el o a db a l a n t eh a v eb e e np r o m o t e dg r e a t l y m r d ，t h ec o m b i n a t i o no fr o u t i n gp r o t o c o l sa n dt o p o l o g yc o n t r o lm e c h a n i s m s d u e t oc h a n g e si nn e t w o r kt o p o l o g yw i l la f f e c t t h er o u t i n gp a t hl e n g t ha n dc o n n e c t i v i t y b e t w e e nn o d e s ，s ot h er o u t i n gp r o t o c o l sa n dt o p o l o g yc o n t r o lp r o t o c o li sc l o s e l yr e l a t e d t h r o u g ht h ew e i g h tf u n c t i o na n dt h en o d et y p eo fc o n v e r s i o nm e c h a n i s mi nt h ep r o c e s s o fr o u t i n gn o d eh i b e r n a t i o nf u l l yt a k e ni n t oa c c o u n t ，r o u t i n gh i s t o r y , t h ec u r r e n te n e r g y a n do t h e rr e l a t e di n f o r m a t i o n , a n da d j u s tp o w e rw i t l lr o u t i n ga d a p t i v e l y t h eu s i n go f t o p o l o g yi n _ f o r m a t i o ni m p r o v e st h el o a db a l a n c i n go fn e t w o r kc o m m u n i c a t i o n ，a n d e x t e n d st h es u r v i v a lt i m eo fn e t w o r k t h es i m u l a t i o nr e s u l t ss h o wt o p o l o g yc o n t r o la n d r o u t i n gp r o t o c o l sc o m b i n e d 晰t 1 1t h en e t w o r kc a ng r e a t l ye x t e n dt h es u r v i v a lt i m e ，w i t h e x c e l l e n tp e r f o r m a n c e k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k s ；c o v e r a g ec o n t r o l ；p o w e rc o n t r o l ；a d a p t i v e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的对所研究酌课题有新百勺见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文牛不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做酌任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位申请人( 学位论文作者) 签名： 2 0d7 r 牟月 日 关于学位论文著作权使用授权书 本人经河南大学审核批准授予硕士学位。作为学位论文的作者。本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 甄质文 本和电子文本) 以供公众检索、奎阅。本人授权河南大学出于宣扬、辰览学校 学术发展和进行学术交流等目的。可以采取影即、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名： 2 0o 学位论文指导教师釜名： 2 0 河南大学研究生硕士学位论文第1 页 第1 章绪论 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k ) 是由大量低成本且具有传感、数 据处理和无线通信能力的传感器节点通过自组织方式形成的网络。它独立于基站 或移动路由器等基础通信设施，通过分布式协议自组成网络。 1 1 无线传感器网络概述 目前传感器网络技术已被列为对人类未来生活产生深远影响的十大新兴技术 之首，随着微机电技术、低功耗无线电通信技术、嵌入式计算技术、微型传感器 技术及集成电路技术的发展和相互融合，使得使用大量低成本的微型传感器以自 组织方式构造出无线传感器网络成为现实。它具有网络规模大、成本低、节点硬 件简单、功耗低、自组织等特点，被广泛应用于环境军事侦察、医疗健康、空间 探索、交通管理、农业等领域。 1 1 1 概念和特点 无线传感器网络通常运行在人无法接近的恶劣甚至危险的远程环境中，能源 无法更换，通过有效设计来延长网络的生命周期成为国内外研究的关键技术之一， 另一方面，由于传统网络与无线传感器网络有着明显不同，前者以传输数据为目 的，后者则以数据为中心，所以在网络协议和算法的设计上也有很大的不同，这 也是当前无线传感器网络研究的另一关键技术，无线传感器网络具有以下特点： 1 资源高度受限，由于传感器节点受体积、功耗和价格的限制，其计算能力、 存诸能力通信能力都很有限。传感器节点由于大都分布在无人看守或危险的环境 中，所以一般采用电池供电，电池的容量一般不是很大，在使用过程中，不能给 电池充电或更换电池，一旦电池能量用完，这个节点也就失去了作用( 死亡) ，这 些特点决定无线传感器网络所使用的协议应简单、有效和节能。 2 大规模，高密度分布，为了完成对区域的监测任务，获取更加详细和精确 信息，往往在目标区域内随机布署成千上万的传感器节点。传感器节点分布非常 密集，通过分析多个传感器传回的采集信息可以提高采集数据的精度。节点的大 量冗余也增强了网络的容错能力，但大量的节点冗余也带来了不必要的能量消耗。 3 自组织，网络的部署和拓扑结构的形成无需依赖于任何外界干预，节点通 第2 页河南大学研究生硕士学位论文 过拓扑控制算法和网络协议协调各自的行为，节点被布署到目标区域后便自动地 组成一个独立的监测网络。 4 动态拓扑，无线传感器网络也是一个动态的网络，由于节点资源的受限， 节点可能会因为电池能量耗尽或其他故障，突然退出网络，也可能由于应用需要 而向网络中添加新的传感器节点。这些会使网络的拓扑结构发生变化，因此无线 传感器网络还应具有动态拓扑结构的管理功能，即当节点加入和退出时能动态改 变网络的拓扑结构以适应变化。 5 与应用高度相关，传感器网络是用来感知客观物理世界，获取物理世界的 信息量的一种无线网络。客观世界的物理量多种多样，不可穷尽。不同类型的传 感器节点关心不同的物理量，因此对传感器网络的应用需求也各不相同。而不同 的应用需求对传感器网络的要求也不同，其软硬件系统和各层网络协议都会有极 大的差别。所以对于不同的应用背景，设计不同的传感器节点软硬件和各层网络 协议是无线传感器网络不同于其他网络的显著特点。 1 1 2 体系结构 无线传感器网络中的传感器节点主要有两类：普通传感器节点( s e n s o r ) 和汇 聚节点( 测。无线传感器网络典型的体系结构阳3 如图卜1 所示。汇聚节点为一个 特殊节点，它是中心处理节点。该节点可向区域内的普通传感器节点发送数据采 集命令，或者接收由传感器节点采集来的感知信息，通过如i n t e r n e t 、卫星或移 动通信网络等方式向基站转发信息，普通传感器节点具有感知、数据处理和无线 通信功能，它们承担着信息的感知、采集和转发任务，转发数据时通过网络自组 织和多跳路由，将数据向汇聚节点发送。最后，数据信息传送到基站报告给用户。 节点由于资源受限，通信距离较短，只能与邻居交换数据，与s i n k 节点的通信必 须使用多跳路由。所以为了保证网络内大多数传感器节点可以与“m 节点通信， 节点往往高密度布署。 河南大学研究生硕士学位论文第3 页 图1 - 1 无线传感器网络体系结构 由于与应用高度相关，针对不同的应用需求，传感器节点设计也不尽相同， 但其典型的基本硬件结构如图l 一2 所示，主要包括能量供应模块、传感器模块、 处理器模块和无线收发模块，能量供应模块由电池及电源管理电路等组成负责传 感器节点能量的供应和管理，无线收发模块主要由信号调理电路和射频模块组成， 处理模块主要包括微处理器和a d 转换器件，传感器模块主要由各种物理参数传感 无件及相关电路。处于节约能量的目的，硬件在设计上要尽量采用低功耗器件， 软件在设计上要以节能为中心，为换取更长的生存时间更高的能量利用率，可以 牺牲一些其他的性能指标。 1 1 3 关键技术 图1 - 2 传感器节点硬件体系结构 无线传感器网络的研究内容很多，目前研究内容主要包括： 1 硬件方面： ( 1 ) 电源技术：由于能量资源是限制无线传感器网络生命期的重要因素，所 以研究体积更小、容量更大的高性能电源是研究的重要方面； 第4 页河南大学研究生硕士学位论文 ( 2 ) 传感器技术：研究各种用途的传感器件、 性、传感器的微型化和便携化等都是研究的重点； ( 3 ) 无线通信技术：由于采用无线通信方式， 无线传感器网络的编码、多址访问等技术； 增强传感器对恶劣环境的适应 如何规避信道干扰，研究适合 ( 4 ) 低功耗芯片技术：研究体积小、功耗低、功能强的c p u 、无线通信芯片等； ( 5 ) 嵌入式操作系统：研究实时性强、配置灵活、代码量少、支持密集并发 操作的嵌入式操作系统，以及相关的应用开发支撑环境。 2 软件方面： ( 1 ) 低能耗介质访问控制( m a c ) 协议 m a c 协议用来控制底层基础结构，控制传感器节点的工作模式和通信过程。由 于传感器节点有能量高度受限、规模大的特点，m a c 层协议必须首先考虑节能问题， 其次才是考虑利用率、实时性和公平性等。m a c 层协议要支持节点的休眠操作，使 得节点在必要时可以关闭某些模块，如传感模块、数据发送模块、数据接收模块 使之进入低功耗的休眠状态，以实现节能的目的。 ( 2 ) 拓扑控制技术 拓扑控制技术是传感器网络的重要支撑技术，在大规模、高密度部署的无线 传感器网络中存在大量的冗余节点，拓扑控制通过节点调度、功率控制等手段利 用节点冗余特性提高能量利用效率，延长网络生存时间。在不影响网络覆盖性能 的前提条件下，通过减少网络中活跃节点数量，并使用冗余节点实现节点交替工 作，对节点的工作功率策略性的调整，以达到延长网络生存时间的目的。 ( 3 ) 网络安全技术 无线传感器网络除要承担数据采集、数据传输外还要进行数据的融合、任务 协同控制等。无线传感器网络安全问题主要考虑传感器网络任务执行的机密性、 数据产生的可靠性以及数据传输的机密性。无线传感器网络的安全机制，如机密 性、消息认证、消息完整性鉴别、认证广播和安全管理等也是研究的重要方向。 无线传感器网络自身的特点决定了它的安全薄弱性，也决定了其研究方法要与传 统网络安全有很大的区别。 ( 4 ) 定位技术 由于无线传感器网络的自身特点，没有位置信息的数据是没有意义的，确定 事件发生的位置或采集数据的节点位置是无线传感器网络基本功能之一。为了提 供有效的位置信息，传感器节点必须能够获得自身位置信息。由于节点存在资源 河南大学研究生硕士学位论文第5 页 受限、随机部署等特点，定位机制必须拥有能量高效性、鲁棒性、自组织性和分 布式计算等特点。 ( 5 ) 能量高效路由协议 路由协议负责路由生成和选择，是传感器节点自组成网的核心。无线传感器 网络的特点和高度受限的节点资源要求必须以一种分布式、局部化的方式实现计 算简单、存储代价低的路由协议。节能是无线传感器网络路由协议设计追求的一 个重要目标。无线传感器网络路由协议不仅要考虑单个传感器节点的能耗，更要 综合考虑全网的能量消耗，努力实现全网能耗的负载均衡，因此能量高效路由协 议是无线传感器网络设计的重要研究方向。 ( 6 ) 数据融合技术 由于无线传感器网络节点的密集布署，网络中节点大量冗余，由节点冗余所 带来数据冗余会加重网络传输负载，为减少网络中传输的冗余数据以实现节约能 量的目的，传感器节点在收集数据和转发数据的过程中，要进行数据融合，去除 冗余信息。但数据融合技术是以增加传输延迟以及降低鲁棒性为代价的，具体应 用时要根据应用的需求而定，研究数据的缓存和融合策略特殊环境下的数据融合 方法是无线传感器网络研究的一个重要内容。 ( 7 ) 应用层技术 无线传感器网络的应用层研究主要是研究各种应用系统的开发和多任务之间 的协调以及传感器网络程序设计语言、程序设计方法、软件测试工具、软件开发 环境和工具、面向应用的系统服务以及网络测试和配置管理工具等。 1 2 研究背景和研究意义 无线传感器网络因其巨大的应用价值，已经引起了世界许多国家军事部门、 商业界和学术界的极大关注。美国自然科学基金委员会在2 0 0 3 年制定了无线传感 器网络研究计划，投资3 千4 0 0 万美元，支持相关基础理论和项目的研究；美国 国防部和各军事部门都对无线传感器网络给予了高度重视，把无线传感器网络作 为一个重要研究领域。英特尔、微软等信息工业界巨头也开始了无线传感器网络 方面的研究，纷纷设立了相应的研究计划和项目。日本、英国、意大利、巴西等 国家也对无线传感器网络表现出了极大的兴趣，纷纷展开了对该领域的研究工作。 虽然，国外从2 0 0 0 年以前就开始对无线传感器网络展开研究，但这些研究还与实 第6 页河南大学研究生硕士学位论文 际应用相差甚远。国内近几年才出现一些相关报道。总体而言，我国在无线传感 器网络方面的研究工作还很少，但国内与国际水平的差距并不大，及时开展这项 对人类未来生活影响深远的前沿技术的研究，对整个国家的政治、经济和国防战 略将有重大的意义。 无线传感器网络涉及的技术较多，需要研究的问题也很多，能量消耗问题便 是其中主要的问题之一。由于在无线传感器网络中，通常要求网络的生存时间长 达数月甚至数年，而传感器节点通常采用微型电池供电，电池提供的能量十分有 限，加之，传感器节点通常被部署在无人值守的环境口1 下而不能持续充电，且对于 拥有成千上万的这种传感器节点h 3 的无线传感器网络来说，对电池的替换更是任务 艰巨甚至是不可能；另外，电池技术在近些年来也没有大的突破陆1 。因此，为了延 长无线传感器网络的生存时间，研究开发降低传感器节点的能量消耗的技术是无 线传感器网络中的核心问题1 ，也是当前国内外研究机构关注的焦点。 1 3 研究内容 网络拓扑控制是无线传感器网络中节约能耗的主要手段之一。理想的拓扑结 构不仅能够提高路由协议和m a c 协议的效率，为数据融和、时间同步和目标定位 等很多方面提供良好的基础，而且有利于延长网络生存时间。网络拓扑控制所面 临的一个首要问题是覆盖控制，本课题研究的主要内容是：首先，根据无线传感器 网络自身能量有限的特点，结合己有的节能策略，设计适用于无线传感器网络的、 开销比较低的覆盖控制机制。其次，由于传感器节点通信模块在节点耗能中占的 比重最大，所以研究在保证信道连通的条件下策略性地降低发射功率的富余量， 从而减少发射端节点的能量消耗随着发送端节点发射功率的降低，其所能影响 到的邻居节点数量也随之减少，节省了网络中与此次通信不相关节点的接收能量 消耗，达到了减少网络整体能量消耗的目的研究内容主要包括以下两个方面： 1 覆盖控制问题 每个传感器节点存在一定的传感范围，当大量的传感器节点随机部署在网络 的感知区域时，这些传感器节点的传感范围可能存在交叠( o v e r l a p ) ，从而导致覆 盖冗余传感器节点的出现，如何寻找这些覆盖冗余传感器节点并控制它们定期进 入休眠状态是覆盖控制需要解决的问题。因为进入休眠状态的传感器节点基本上 不消耗能量，所以可以大大降低整个传感器网络的能量消耗。为此，本文提出了 一种基于盲区覆盖的冗余传感器节点查找算法，该算法不仅能快速准确地找出网 河南大学研究生硕士学位论文第7 页 络中的覆盖冗余传感器节点，而且还能判断网络是否被传感器节点完全覆盖，时 间复杂度小，执行效率高。 2 功率控制问题 功率控制指节点在无线通信过程中选择最恰当的功率发送分组，以此达到优 化网络应用相关性能的目的。由于节点发射功率的选择对网络多方面的性能均会 产生影响，因此，网络中的节点采用多大的功率级发送分组是一个非常复杂并具 有挑战性的课题。目前常见的功率控制算法如d i 触n g 口1 、d l s s 等在功率控制中没有 考虑到“热区”问题哺3 ，从而大大限制了上层路由算法的有效性，反而由于“热区 效应”导致网络过早死亡，本文提出了一个非均匀功率控制算法，在实现对节能 功率控制的前提下，充分考虑汇聚节点周围的能量均衡性，为上层路由提供了有 效支持，从而延长了网络生存时间。 1 4 论文组织结构 全文共分为五章，安排如下： 第一章介绍了本课题的背景，阐述了本课题的研究目的以及意义，最后介绍 了本文各章节的组织结构。 第二章介绍了无线传感器网络无线传感器网络的拓扑控制，然后着重从基于 覆盖控制的节点调度和功率控制两个方面分析了现有的典型算法，最后介绍了网 络系统能量消耗的主要来源，以及可采取的节能策略。 第三章提出了一种覆盖控制算法及节点调度算法，然后针对其进行了仿真分 析。 第四章首先描述了无线传感器网络中的功率控制算法和极具代表性的基于邻 近图的功率控制算法d r n g ，然后针对“热区 问题分析了其缺点，最后详细讲解 了本文提出的非均匀动态功率控制算法并对其进行了仿真与分析。最后分析了功 率控制技术对上层路由的影响和设计与路由相结合的拓扑控制技术的必要性。 第五章结合前两章的拓扑控制算法提出了和路由相结合的拓扑控制机制，使 之能够适应负载均衡的要求。 最后是对本文中所做的工作进行一个全面的总结，并指明了下一步需要进行 的工作。 第8 页河南大学研究生硕士学位论文 第2 章无线传感器网络的拓扑控制 在无线传感器网络的规划和设计中，减少节点的能量消耗、延长其工作时间 并最大化网络的生命周期是首先要解决的重要问题。除了设计能量高效的m a c 协 议、路由协议以及应用层协议之外，拓扑控制也是解决该问题的有效措施之一。 拓扑控制是指在满足网络覆盖度和连通度的前提下，通过调整传感器覆盖能 力和功率控制，以减少冗余数据产生、剔除节点间不必要的通信链路，形成一个 数据转发的优化网络结构隋1 ，一般以延长网络生存周期为主要目标，兼顾通信干扰、 网络延迟、负载均衡、可靠性、可扩展性等其他性能。但是在一般的拓扑控制中 还存在节点能量消耗不均衡的问题，它严重影响着网络的整体寿命，所以在设计 拓扑控制策略时必须考虑网络中所有节点的能量均衡消耗问题，使节点的能耗相 对平均，避免由于某些能耗较大的节点失效而导致整个网络瘫痪。 2 1 自适应拓扑控制的研究现状 拓扑控制研究已经形成睡眠调度和功率控制两个主流研究方向n 引所谓睡眠 调度，就是控制传感器节点在工作状态和睡眠状态之间的转换；所谓功率控制， 就是为传感器节点选择合适的发射功率。 2 1 1 覆盖控制 覆盖控制是传感器网络拓扑控制中的一个重要问题，体现了无线传感器网络 所能提供的“感知 服务质量。优化传感器网络覆盖对于合理分配网络的空间资 源，更好地完成环境感知、信息获取任务以及提高网络生存能力都具有重要的意 义。 一、网络覆盖问题分类 根据覆盖对象的不同，无线传感器网络的覆盖问题可以分为3 类：区域覆盖 ( a r e ac o v e r a g e ) ，点覆盖( p o i n tc o v e r a g e ) 和栅栏覆盖( b a r r i e rc o v e r a g e ) r l , j 。 区域覆盖是被研究的最多的覆盖问题，它要求目标区域中的每一点至少被一个节 点覆盖，同时保证网络内各节点间的通信连通性，并在满足覆盖和连通要求的前 提下，尽可能减少所需节点数，使网络成本最小。如在战场实时监控应用中，就 河南大学研究生硕士学位论文第9 页 需要对目标区域内的每一个点进行监测。图2 - 1 显示出网络对给定的正方形目标 区域进行区域覆盖的例子。 图2 - 1 区域覆盖图2 - 2 点覆盖图图2 - 3 栅栏覆盖 在点覆盖问题中，覆盖要求覆盖到目标区域中的一组点，它只需对目标区域 内的有限的离散点进行监测，并确定覆盖这些点所需的最少节点数。图2 2 显示 了一组随机分布的传感器覆盖一组点的例子。 栅栏覆盖是考虑某个移动目标沿任意轨迹穿越传感器的部署区域时被检测到 的概率。图2 - 3 显示了一个常见的栅栏覆盖问题，路径的起点和终点是从区域的 底部和顶部的边界线上选择。 二、现有典型覆盖算法分类分析 网络覆盖是无线传感器网络中的一个关键技术。目前，针对不同的应用，研 究人员提出了各种不同的覆盖控制算法。以下根据覆盖分类，分别介绍和分析了 区域覆盖、点覆盖和栅栏覆盖问题中的几种典型覆盖算法。其中以区域覆盖为主。 1 区域覆盖 区域覆盖是覆盖问题中被研究的最多的问题之一。区域覆盖要求对传感器网 络目标区域中的每一点都至少覆盖一次。以下主要讨论现有的区域覆盖控制算法。 ( 1 ) 能量高效覆盖控制 s l i j e p c e v i cn 2 1 提出的基本思想是将网络中所有传感器节点划分为很多不相 交的节点集，并且在任意时刻有且只有一个节点集合处于活跃工作状态，其它节 点集处于休眠状态。通过调度节点集之间的工作与休眠，可以有效地延长网络生 存时间。s l i j e p c e v i c 设计了一种集中启发式算法，并将寻找最大数量的无交节点 集问题归结为n p 完全问题。该算法首先将网络覆盖区域划分为若干个域，其中每 个域内的点被相同的节点覆盖。拥有最少覆盖节点数的域称为临界域。临界域的 覆盖节点数构成无交节点集个数的上限。该算法的基本思想是尽量避免将覆盖临 第10 页河南大学研究生硕士学位论文 界域的节点划分到同一个节点集合中。 y en 羽提出了一种基于探测的分布式节点密度控制算法p e a s 。在p e a s 中，节 点随机休眠一段时间，当醒来时广播一个通信半径为c 的探针( p r o b e ) 报文，在该 半径内的活动节点接收到该通告消息后会发送一个回复消息。节点若接收到回复 消息，即可继续休眠，否则节点将判断自己是附近唯一的工作节点，需要中断休 眠，保持工作状态。通过调整探测范围和唤醒间隔，可以实现不同的网络覆盖质 量。p e a s 算法不依赖节点的精确位置信息，计算开销小，但不能保证网络的覆盖 质量。 t i a nn 4 1 基于计算几何，提出了s p o n s o rs e c t o r 算法。在该算法模型中，节 点的传感区域是一个二维空间中，以节点为中心的碟形，当某节点的传感区域被 它的邻居完全覆盖时，该节点是一个冗余节点，可以进入休眠状态。s p o n s o rs e c t o r 的每一轮开始时节点收集自己邻居的信息，当发现自己的邻居已经完全覆盖自己 的传感区域后，则进入准备休眠状态。s p o n s o rs e c t o r 算法中仅考虑了自己被邻 居完全覆盖时的休眠，在一定程度上减少了覆盖冗余程度，但对于不能相互覆盖 却产生覆盖交叠区域的覆盖冗余性没有相应的减少。 y a n n 6 3 提出了一种可以为目标区域不同点提供不同覆盖质量的节点调度算法。 网络生存时间被划分为若干等长的时段。在每个时段初期，节点首先随机产生一 个位于该时段内的参考时间点。此外，该算法使用离散网格点作为网络覆盖区域 的近似，并使用网格点来判断目标区域是否被充分覆盖。对于落在其覆盖范围内 的每个网格点，节点根据自身的参考时间点以及该点被邻居节点覆盖的情况决定 相对于该网格点的工作周期。节点在每个时段内的工作周期为针对其覆盖范围内 全部网格点的工作周期的并集。 c h e n 口7 1 设计了一种基于网格划分的活跃工作节点选择算法。该算法用网格点 作为网络覆盖区域的近似，并试图选择尽可能少的活跃节点来覆盖全部网格点。 c h e n 分别使用了集合覆盖问题和线性规划问题对该问题进行了抽象。仿真实验表 明，尽管线性规划方法能计算出更小的覆盖集，但是其收敛速度慢，计算时间长， 因而，不适合大规模无线传感器网络。 h u a n g n 鲫针对二维目标区域是否被无线传感器网络覆盖的决策问题，首次提 出了基于边界覆盖的集中式、多项式时间判别算法。进一步，h u a n g 训提出了判断 三维空间是否被覆盖的多项式时间算法。h u a n g 啪3 提出了一种能够保持网络原始覆 盖质量的分布式节点调度算法。该算法采用与文献 1 6 类似的方法。所不同的是， 河南大学研究生硕士学位论文第11 页 该算法不是根据网格点来确定节点的工作周期，而是根据位于节点覆盖范围内其 它邻居节点覆盖边界之间的交点的覆盖状况来确定节点的工作周期。 g a o 心订在文献 1 4 的基础上，指出已知节点精确位置信息时节点的覆盖区域被 其邻居节点完全覆盖至少需要3 个节点，最多只需要5 个邻居节点。考虑到在没 有精确的节点位置信息时很难实现节点的完全覆盖冗余，文献 2 1 分析了在节点 位置信息未知时节点成为完全覆盖冗余节点的概率，以及节点部分冗余与其邻居 节点个数间的关系。在此基础上，w u 口乙设计了一种不依赖节点位置信息、但只能 保证概率覆盖的节点调度算法l d a s 。 与文献 1 6 中的工作类似，文献 2 3 中也提出了一种能够为不同区域提供不 同覆盖质量的节点调度协议。但是该协议不是根据网格点的覆盖度，而是根据邻 居之间的相对位置关系来判断目标区域的覆盖度。 ( 2 ) 能量高效连通覆盖 z h a n g 口4 。证明了若节点的通信范围r c 至少两倍于节点感知范围r s ( r c 2 r s ) 时， 如果活动节点能够覆盖整个监测区域，则该节点集合也是连通的。根据这个结论， z h a n g 提出了一个分布式的节点密度控制算法o g d c 。算法以轮次循环运行，每轮开 始时，随机选择开始节点并广播消息。当节点接收到广播消息后，根据其邻居信 息、自己的位置信息，计算是否被邻居节点所覆盖。对于r c o 时满足 刀刀2 i n n + ( 2 k 一1 ) i n i n n 一2 1 n k + 2 a 且n 足够大时，节点数为r l 的网络( k + 1 ) 连通 的概率至少是e 。一。 如果网络中的节点并不是均匀分布的，尤其是稀疏网络，那么几何随机图理 论就无法应用，但是研究人员对此也做了一些工作。s a n t i h 钔等人假设n 个节点( 节 点数固定，也可能变化) 在d 维部署区域r = 0 ，f 内随机均匀部署，对于节点密 度没有限制，他们的目标是使所有节点都具有最小半径发射半径r ，使得到的图是 连通的。 k u b i s c h h 7 3 等人描述了两种将邻节点数控制在一定数量内的分布式算法，并通 过仿真实验评价了它们的性能。l i u _ 8 3 等人研究了关于节点有不同最大发射范围的 问题，得到了非连接的信息，采用了一个分布式拓扑结构控制算法来最小化最大 功率，保持了每个节点的可达性。c r u z h 引等人研究了跨层问题，提出了一个结合 连接调度表和功率控制的算法。 2 计算几何方法 如果能够获得节点之间的距离或它们的相对位置的信息，那么可以有效地实 现将网络拓扑变得稀疏。利用计算几何方法构建邻近图的方法能够实现拓扑控制。 经常使用的几何结构有以下几种： ( 1 ) 最小生成树( m s t ) 。文献 5 0 提出了一种基于本地信息的最小生成树的构 造法，其思想是每个节点会收集它的邻节点，然后构造( 如使用p r i m 算法) 这些节 点的最小生成树，将能量代价作为连接权重( 代价相同的连接由加入的节点表示符 作为间断符来区分) 。下一步的关键就是在化简后的拓扑中保留这些对应于最小生 河南大学研究生硕士学位论文第15 页 成树中直接邻节点的边。这种构造法保持了原图的连通性，而且每个节点的最大 度数是6 。它能限制双向连接，也比较容易加人功率控制。而且，平均节点度数比 较小，接近理论界限。 ( 2 ) g a b r i e l 图( g a b r i e lg r a p h ，g g ) 。在传输功率正比传输距离的平方时， g g 是最节能的拓扑。m s t 是g g 的子图，g g 也满足连通性。在文献 5 1 中介绍了 g g 的分布式构造法。一个节点必须要对于它的所有邻节点测试边的圈定义是否还 成立，如果所有的节点都与它们的邻节点的位置相交换，那么这是很容易做到的。 ( 3 ) 相关邻近图( r e l a t i v en e i g h b o rg r a p h ，r n g ) ，很容易用本地算法实现。 如果原始图g 是连通的，那么它也是连通的。其稀疏程度在m s t 和g g 之间，连通 性也在m s t 和g g 之间，优于m s t ，冲突干扰优于g g ，是两者的折中。r n g 易于用 分布式算法构造。l j 畸2 1 等人提出的d r n g 和d l m s t 是两个具有代表性的基于邻近图 理论的算法。基于邻近图的功率控制算法的基本思想是：设所有节点都是用最大 发射功率发射时形成的拓扑图g ，按照一定的邻居判别条件求出该图的邻近图g ， 每个节点以自己所邻近的最远节点来确定发射功率。d r n g 是基于有向r n g 的，d l m s t 是基于有向局部m s t 的。d r n g 和d l m s t 能够保证网络的连通性，在平均功率和节 点度等方面具有良好的性能。 另外，r o d o p l u 等提出了一种基于e n c l o s u r e 图的功率分配算法r & m 璐驯，该算 法中每个节点在周围确定一个称作e n c l o s u r e 的区域，在e n c l o s u r e 区域中的节 点称为节点的真正邻居。l i u 等基于y g 提出了c b t c 瞄4 3 算法，每个节点独立调节发 射功率，以保证在每a 角度内有一个邻居节点。 2 2 拓扑控制的节能策略 传感器节点主要有四部分组成：计算模块、通信模块、传感模块以及能量供应 模块。从传感器的构成分析传感器网络的能耗，分为三个方面： 1 传感能耗：传感器网络中的传感器信号采集时所消耗的能量。 2 计算能耗：传感器进行简单的本地信号处理，以及多传感器间进行协同信 号处理时微处理器所消耗的能量。 3 通信能耗：用户在网络中发布命令以及每个传感器节点向基站发回报告时 的无线电通信所消耗的能量。 在上述的系统能耗中，由于传感器网络自身的特点而引起的能量浪费主要体 第16 页河南大学研究生硕士学位论文 现在通信方面，包括： 第一、相邻传感器节点采集的信号相关性很强，信息存在大量的冗余。在网 络中传输冗余信息会导致能量浪费。 第二、相邻传感器节点在通信时节点的发射功率存在有很大的富余量，从而 造成能量浪费。 第三、在数据传输过程中，为了保证通信的正确性，需要额外的控制信息的 通信开销 而在传感能耗、计算能耗、通信能耗中通信能耗所占的比重最大，计算能耗 所占的比重最小，所以设计出合理的拓扑控制协议将重点放在传感能耗和通信能 耗的节省上。 河南大学研究生硕士学位论文第17 页 第3 章自适应覆盖控制与节点调度算法设计 由于无线传感器网络的自身特点，通常无线传感器网络的节点在目标区域的 部署有大规模、高密度的特点，这就导致网络中大量节点的覆盖区域相互交叠。 这种覆盖冗余性会导致采集、传输数据的冗余以及信道的干扰，浪费了有限的能 量资源。使用合适的覆盖控制算法和节点调度算法在保证一定覆盖性的前提下使 一些节点的传感模块策略性的休眠，对延长网络生存时间有重要意义。 3 1 自适应覆盖调整算法 目前，传感器网络的初始部署有两种策略：一种是大规模的随机部署；另一 种是针对特定的用途进行计划部署。由于传感器网络通常大规模高密度部署，因 此大都采用随机部署方式。但是这种大规模随机投放方式很难一次性地将大量的 传感器节点放置在适合的位置，极易造成传感器网络节点分布的过密或过疏，从 而形成覆盖重叠区和覆盖盲区。因此，在传感器网络初始部署后，我们需要采用 覆盖控制策略以获得理想的网络覆盖性能。为了有效的进行节点的覆盖控制我们 首先设计了节点自适应传感半径调整算法a a s r ( a d a p t i v ea d j u s t m e n to fs e n s i n g r a d i u s ) ，使节点为自己选择合适的覆盖范围。 3 1 1 网络模型假设 由于无线传感器网络的应用高度相关性，任何覆盖控制算法都应针对确定的 应用需求，所以在对本文提出的无线传感器网络覆盖控制算法讨论之前有必要对 研究对象的网络模