（计算机应用技术专业论文）无线传感器网络覆盖控制算法研究.pdf

l r c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fd e n g r e s e a r c ho nc o v e r a g ec o n t r o la l g o r i t h m s i nw i r e l e s ss e n s o rn e t w o r k c a n d i d a t e ：z h a n gj i n s u p e r v is o r ：p r o f l i ud a x i n a c a d e m i cd e g r e ea p p li e df o r ：d o c t o ro fe n g i n e e r i n g s p e c i a l t y ：c o m p u t e ra p p li c a t i o nt e c h n o l o g y d a t e o fs u b m i s s i o n ：o c t o b e r2 0 0 9 d a t eo fo r a le x a m i n a t i o n ：j a n u a r y2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 巳， 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：魂器 日期： 2 , 0 1 0 年；月z 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。，涉密学位论文待解密后适用本声明。 本论文( 豳在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：魂潘 导师( 签字) ：训求论一 。 v 。 日期：2 0 i o 年弓月2 ，日 幼f 汐年己月乙日 t i 无线传感器网络覆，斋控制算法研究 摘要 无线传感器网络技术作为多学科交叉的新型技术，由于其广阔的应用前 景，得到了广泛的关注。要实现对分布区域内的各种环境或对象的感知与监 测，首要的问题就是必须对监控区域进行有效的覆盖控制。国内外研究人员 从覆盖能力、网络连通性、能量有效性与算法精确性等方面对无线传感器网 络覆盖控制问题进行了研究，并取得了一些成果。但由于无线传感器网络本 身的特殊性，再加上被监测环境的变化复杂，导致目前的覆盖算法在实际应 用中具有很大的局限性。本文重点研究具有较大实用性的覆盖控制算法，解 决能量受限、通信能力有限及复杂环境条件下的监控区域有效覆盖问题。 在对现有节能覆盖方式分析的基础上，将多因素优化节能与多重覆盖节 能方式相结合，提出了一种能量有效的多重物理覆盖算法，在保障覆盖与连 通性的前提下，以能量、覆盖度为衡量指标，采用调度机制实现节点轮换活 跃与休眠，有效地提高网络生存时间。仿真实验结果表明，与目f j i 典型算法 相比，提出的算法在网络生存时间、能量消耗与消亡节点数上具有显著的优 势。 分析了不规则区域物理覆盖的连通性问题，对关键区域覆盖控制进行了 数学描述，提出了关键区域覆盖启发式优化算法。通过分配不同的权值创建 感知区域图和终端集合，创建加权节点s t e i n e r 树，形成最少数量格点集并 构建覆盖关键区域的传感器放置方法。理论分析证明提出的算法能以优化的 传感器节点数量，实现关键区域完全覆盖功能。通过不同场景下、不同参数 仿真结果表明，与现有的算法相比，在关键区域格点数、感知范围、发送范 围和关键区域格点选择分布概率变化时，提出的算法具有更少的传感器布置 数量。 针对具有不同传输半径的不规则w s n 的物理覆盖与广播数据信息转 发，提出了最小单位圆集信息覆盖算法。该算法以覆盖范围的轮廓集为出发 点，以时间复杂度o ( n l o g n ) 有效的计算出覆盖范围的轮廓集，并以节点最 少数量的邻居节点子集实现所有邻居节点的覆盖。通过理论分析证明该算法 找到的最小单位圆覆盖集与其轮廓集是相等的。大量的仿真实验及与现有的 覆盖算法的对比，表明了提出的算法在保证物理覆盖的同时，以最少数量的 哈尔滨。i ：程人学博+ 学位论文 节点实现了全局信息覆盖。 最后，给出了信息覆盖的数学描述，并从理论上证明覆盖敏感的信息覆 盖问题为n p 完全问题。针对该问题，提出了覆盖敏感的分布式信息覆盖算 法。该算法在每个节点中运行，节点将通过本地选择最少数量的节点实现信 息覆盖，该算法同时具有节能的特点。通过与现有的数据查询处理算法的对 比，实验结果表明了提出的算法在充分考虑物理覆盖连通性前提下，不仅实 现了信息覆盖，而且明显地降低了节点的能耗与数据查询能耗、提高了网络 的生存时间。 关键词：w s n ；覆盖控制；连通性；物理覆盖；信息覆盖 - a b s t r a c t a san e wm u l t i k n o w l e d g et e c h n o l o g y , w i r e l e s ss e n s o rn e t w o r kh a sg a i n e d c o m p r e h e n s i v ea t t e n t i o nf o ri t se x t e n s i v ea p p l i c a t i o np r o s p e c t i no r d e rt om o n i t o r a n ds e n s et h ee n v i r o n m e n ta n do b j e c t se f f i c i e n t l y , c o v e r i n gt h em o n i t o r i n ga n d s e n s i n ga r e af u l l yi st h ef i r s ti m p o r t a n tp r o b l e m m a n yr e s e a r c h e r sh a v ee x p l o r e d t h ec o v e r a g ec a p a c i t y , c o n n e c t i v i t y , p o w e re f f i c i e n c y , a c c u r a c yo fc o v e r a g e p r o b l e m so fw s n h o w e v e r , t h ee f f e c t i v e n e s so f t h ee x i s t i n gs c h e m e sd e g r a d e s g r e a t l yi na c t u a le n v i r o n m e n t f o rt h ec h a r a c t e r so fw s na n dt h ec h a n g e f u l e n v i r o n m e n t 、斫t ht h ec o n s i d e r a t i o no fr e q u i r e m e n t so fa c t u a le n v i r o n m e n t ，t h i s d i s s e r t a t i o nf o c u s e so nt h ec o v e r a g ec o n t r o lp r o b l e mi nw s n ，a n dd e s i g n sm o r e e f f i c i e n tc o v e r a g ec o n t r o la l g o r i t h m sf r o mp h y s i c a lc o v e r a g ea n di n f o r m a t i o n c o v e r a g ea s p e c t s b a s e do na n a l y z i n gc u r r e n tp o w e r - s a v i n gc o v e r a g es c h e m e ，a n dc o m b i n i n g t h em u l t i f a c t o ro p t i m i z e dp o w e rs a v i n gs c h e m ea n dm u l t i l e v e lc o v e r a g ep o w e r s a v i n gs c h e m e ，a ne f f i c i e n tp o w e rm u l t i l e v e lc o v e r a g ea l g o r i t h m i sp r e s e n t e d b y m e a s u r i n ge n e r g ya n dc o v e r a g ed e g r e e ，i tp u t sr e d u n d a n ts e n s o rn o d e st os l e e p m o d et os a v ee n e r g yw h i l em a i n t a i nt h es e n s i n gf i e l ds u 伍c i e n tc o v e r a g ed e g r e e w i t hp r e c o n d i t i o no f c o v e r a g ea n dc o n n e c t i v eo fw s n d e t a i l e d s i m u l a t i o nr e s u l t s a n dc o m p a r e dt oe x i s t i n gs c h e m e si n d i c a t et h a tt h ep r o p o s e de p c aa l g o r i t h mn o t o n l yg u a r a n t e e st h en e t w o r kc o v e r a g ed e g r e e ，b u ta l s op r o l o n g s t h en e t w o r k l i f e t i m e t h e nt h ec o n n e c t i v i t yp r o b l e mo fp h y s i c a li r r e g u l a ra r e ac o v e r a g e i s a n a l y z e d i tg i v e st h em a t h e m a t i c a ld e s c r i p t i o no fc r i t i c a l a r e ac o v e r a g ea n d p r o p o s e st h ec r i t i c a la r e ac o v e r a g eh e u r i s t i co p t i m i z a t i o na l g o r i t h m b ya s s i g n i n g d i f f e r e n tw e i g h tf o rc r i t i c a lg r i dp o i n t sa n dc o m m o ng r i dp o i n t st oc r e a t et h eg r a p h o fs e n s i n gf i l e da n dt e r m i n a ls e t ，i te s t a b l i s h e sn o d e w e i g h t e ds t e i n e rt r e et of o 衄 c r i t i c a la r e a sc o v e r a g e 酊d ss e tw i t hm i n i m a ln u m b e r t h e o r e t i ca n a l y s i sp r o v e s t h a tt h ep r o p o s e da l g o r i t h m sc a r lf u l l yc o v e ra l lc r i t i c a lg r i d sa n df o r maw s n d e t a i l e ds i m u l a t i o nr e s u l t sa n dc o m p a r i s o nw i t ha ne x i s t i n ga l g o r i t h mi n d i c a t e 哈尔滨t 稃人7 ：博十7 ：何论文 t h a tt h ep r o p o s e da l g o r i t h m so b v i o u s l yd e p l o yf e w e rs e n s o r sw i t hv a r y i n gt h e n u m b e ro fc r i t i c a lg r i dp o i n t s ，s e n s i n gr a n g e ，t r a n s m i s s i o nr a n g ea n dt h es e l e c t i o n d i s t r i b u t i o np r o b a b i l i t yo fc r i t i c a lg r i dp o i n t s i no r d e rt od e a lw i t hp h y s i c a lc o v e r a g ea n db r o a d c a s t i n gd a t ai n f o r m a t i o n f o r w a r d i n gp r o b l e mi nw s n w i t hd i f f e r e n tt r a n s m i s s i o nr a d i u s ，am i n i m u mu n i t d i s k ss e ti n f o r m a t i o nc o v e r a g ea l g o r i t h mi sp r o p o s e d ，w h i c hc a nc a l c u l a t es k y l i n e s e te f f i c i e n t l yw i t ht h et i m ec o m p l e x i t yo ( nl o gn ) t h ep r o p o s e da l g o r i t h mc o v e r s 、 e a c hn o d ew i t hm i n i m u mu n i td i s kc o v e rs e t ，a n dt h em i n i m u mu n i td i s kc o v e rs e t o fan o d ei s e q u i v a l e n t t oi t ss k y l i n es e t d e t a i l e ds i m u l a t i o nr e s u l t sa n d c o m p a r i s o n sw i t he x i s t i n ga l g o r i t h m si n d i c a t et h a tt h ep r o p o s e da l g o r i t h m n o t o n l yc o v e r sa l ln o d e sw i t hm i n i m u m n o d e s ，b u ta l s op r o l o n g st h en e t w o r kl i f e t i m e f i n a l l y , t h ed e s c r i p t i o no fi n f o r m a t i o nc o v e r a g ei sp r e s e n t e d ，a n dw ep r o v e t h a tt h ei n f o r m a t i o nc o v e r i n gp r o b l e mi san p - c o m p l e t ep r o b l e m t h i sp a p e r p r o p o s e sac o v e r a g e - a w a r ed a t aq u e r ya l g o r i t h m ，w h i c hm a i n t a i n sn o to n l yt h e p h y s i c a lc o v e r a g eo fw s n ，b u ta l s ol o g i c a l d a t ai n f o r m a t i o nc o v e r a g e i ti s e x e c u t e db ye a c hs e n s o rn o d et ol o c a l l ys e l e c tt h em i n i m u mn u m b e ro fk - n e i g h b o r i n g n o d e si no r d e rt oa c h i e v ei n f o r m a t i o nc o v e r a g e d e t a i l e d e x p e r i m e n t a ls t u d ya n dc o m p a r i s o n sw i t he x i s t i n ga l g o r i t h m si n d i c a t et h a tt h e e n e r g yc o n s u m p t i o no fe h d qi sl e s s ，a n dt h ep e r f o r m a n c eo fe h d q i sm u c h b e t t e ri nt e r m so fq u e r yc o s ta n dn e t w o r k1 i f e t i m e k e y w o r d s ：w s n ；c o v e r a g ec o n t r o l ；c o n n e c t i v i t y ；p h y s i c a lc o v e r a g e ；i n f o r m a t i o n 无线传感器网络覆盖控制算法研究 目录 第1 章绪论1 1 1 本文课题研究的背景与意义1 1 2 国内外研究现状3 1 - 2 1 连通性覆盖4 1 - 2 2 节能覆盖8 1 2 3 动态覆盖12 1 2 4 不规则覆盖1 5 1 - 2 5 其他覆盖18 1 - 2 - 6 存在的问题与研究趋势。1 9 1 3 本文主要研究内容2 0 1 4 本文的结构安排2 l 第2 章能量有效的多重物理覆盖算法2 4 2 1 引言2 4 2 2 相关定义2 5 2 3 算法描述2 7 2 3 1 节点合法性检测算法2 7 2 3 2 盲点消除算法2 9 2 3 3 休眠节点激活算法3l 2 4 仿真结果与分析3 3 2 4 1 活跃节点数量3 4 2 4 2 覆盖度性能3 6 2 4 3 生存时间3 7 2 5 本章小结3 8 第3 章关键区域覆盖优化算法3 9 3 1 引言3 9 3 2 问题描述4 1 3 3 关键区域覆盖启发式优化算法4 2 3 3 1 算法描述4 2 哈尔滨f ：程人学博十学位论文 3 3 2 算法时i 剐复杂性4 6 3 3 3 仿真结果与分析4 6 3 4 关键区域覆盖优化算法5 l 3 4 1 算法描述5 l 3 4 2 算法时间复杂性5 4 3 4 3 仿真结果与分析5 4 3 5 本章小结5 8 第4 章最小单位圆集信息覆盖算法6 0 4 1 引言6 0 4 2 问题描述6 1 4 3 算法描述6 3 4 4 算法性能分析6 6 4 5 算法仿真与分析6 9 4 5 1 同构网络7 0 4 5 2 异构网络7 2 4 6 本章小结7 5 第5 章覆盖敏感的分布式信息覆盖算法7 6 5 1 引言一7 6 5 2 问题描述7 7 5 3 算法描述8 0 5 4 算法性能分析8 2 5 5 仿真结果8 5 5 5 1 能量有效性8 5 5 5 2 参数对系统性能的影响8 8 5 5 3 数据处理性能9 0 5 6 本章小结9 2 结论9 3 参考文献9 6 攻读博士学位期间发表的论文和取得的科研成果1 0 7 致谢1 0 8 第1 章绪论 第1 章绪论 随着无线通信、嵌入式计算技术、传感器技术、微电子技术的发展，无 线传感器网络技术应运而生。覆盖控制问题是无线传感器网络的基础问题， 针对无线传感器网络特点的覆盖研究是网络应用迫切需要解决的问题。本章 首先介绍了课题研究的背景与意义，归纳了该领域国内外的研究现状，综述 了现有的研究成果及存在的问题，最后阐述了本文所作的主要研究工作。 1 1 本文课题研究的背景与意义 近年来，随着微机电系统( m i c r o e l e c t r o m e c h a n i s ms y s t e m ，m e m s ) 、 无线通信、信息网络与集成电路等技术的迅速发展，新兴的无线传感器网络 ( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 应运而生1 1 - 2 1 。无线传感器网络综合了传感 器技术、嵌入式计算技术、分布式信息处理技术和通信技术，能够协作地实 时监测、感知、采集网络分布区域内的各种环境或监测对象的信息，并对这 些信息进行处理，获得详尽而准确的信息，传送到需要这些信息的用户。借 助于节点内置的形式多样的传感器测量所在周边环境中的热、红外、声纳、 雷达和地震波信号，从而探测包括温度、湿度、噪声、光强度、压力、土壤 成分、移动物体的大小、速度和方向等众多人们感兴趣的物质现象1 3 - 4 | 。 w s n 可以使人们在任何时间、地点和任何环境条件下获取大量详实可靠的 物理世界的信息1 5 - 6 | 。 由于具有体积小、价格低廉以及彼此之间可以在近距离内进行无线通信 等良好特性，w s n 在国防军事、反恐抗灾、智能家居、环境监测、地震与 气候预测、交通管理、医疗卫生、制造业等许多方面都具有广泛应用前景， 是国内外的热点研究领域川。美国商业周刊认为，w s n 是全球未来四大 高技术产业之一，是2 1 世纪世界最具有影响力的2 1 项技术之一。麻省理工 学院的新技术评论认为w s n 是改变世界的十大新技术之一1 8 】。美国 s t a n f o r d 、u cb e r k e l e y 、u c l a 、m i t 等大学及i n t e l 公司对w s n 的研究处 于世界领先的位置。 哈尔滨【：稃人学博f ：学位论文 我国最近几年也开始重视w s n 的研究。国家自然科学基金从2 0 0 4 年 开始，逐年加强了对w s n 领域研究的资助。在“中国未来2 0 年技术预见 研究”报告中，有7 项技术课题直接论述了传感网络。2 0 0 6 年初发布的 国家中长期科学与技术发展规划纲要为信息技术确定了3 个前沿方向， 其中有两个与w s n 研究直接相关。 w s n 具有电源能量有限、通信能力有限、节点计算能力有限、传感器 节点数量大且分布范围广、网络动态性强、感知数据流巨大、以数据为中心 等特点，与传统的a dh o c 网络和i n t c r n e t 网络有很大不同【，】。w s n 作为一 种新的计算模式j 下在推动科技发展和社会进步，关系到国家经济和社会安 全，已成为国际竞争的制高点，引起了世界各国军事部门、工业界和学术界 的极大关注。但是，w s n 在向实用化发展的过程中还有很多问题需要解 决，在各个层面以及跨层设计上都有很大的研究和发展空间 t 0 - 1 1 。 要实现对分布区域内的各种环境或对象进行感知与监测，首要的问题就 是必须对监控区域进行有效的覆盖控制】。覆盖问题是任何类型的无线传 感器网络中的基本问题。覆盖可以定义为对于监控区域内的任何一点，都满 足至少在一个传感器节点的感知范围之内，则称该区域被覆盖。w s n 的覆 盖控制问题，可以看作是在传感器网络节点能量、无线网络通信带宽、网络 计算处理能力等资源普遍受限情况下，通过网络传感器节点放置以及路由选 择等手段，最终使w s n 的各种资源得到优化分配，进而使感知、监视、传 感、通信等各种服务质量得到改掣坫- - 6 】。由于受到w s n 网络的连通性、能 量有效性、算法复杂性、网络动态性与可扩展性等条件的约束，通过一定的 方法开展w s n 覆盖控制算法研究，实现w s n 的感知与监测功能，具有十 分重要的理论意义【 - 。1 。可以预见，w s n 必将广泛应用于各个领域，而提供 对良好的覆盖控制技术是w s n 迅速普及与实用化的关键，具有十分重要的 经济价值和社会意义。 本文着眼于w s n 中的覆盖控制问题，在充分考虑实际场景对覆盖控制 的要求的前提下，放宽约束条件，研究更加接近实际的覆盖控制算法。从 w s n 的物理覆盖与逻辑信息覆盖进行系统深入的研究：在满足w s n 物理 覆盖的前提下，提出逻辑覆盖的新概念，即不仅解决w s n 中感知区域覆盖 与连通性的基本物理覆盖问题，同时在此基础上，以w s n 的核心功能 感知数据的处理为中心，实现w s n 逻辑功能上的覆盖，即信息覆盖。因此 第1 章绪论 本课题不仅具有非常重要的理论意义，而且具有十分重要的经济价值和社会 意义。 1 2 国内外研究现状 到目前为止，在世界范围内，无线传感器网络技术还基本处于基础理论 研究和初步应用阶段1 2 0 - 2 1 。 欧美等国非常重视w s n 技术在未来通信网络中的地位与作用，已经进 行了大量的理论分析与研究，同时也建立了一些实验平台 2 2 - 2 4 1 。美国 s t a n f o r d 、u cb e r k e l e y 、u c l a 、m i t 等大学的研究小组在积极深入的开展 技术研究的同时已经建立了相应的实验平台；英国、意大利、希腊等国家也 对相关技术进行了深入的研究；美国的i b m 公司、m i c r o s o f t 公司、b e l l 实 验室、德国p h i l i p s 公司已经加紧研究新的技术和投入开发支持w s n 覆盖功 能的专业芯片，并将新技术应用到产品当中。 韩国、新加坡、我国台湾、香港科技大学、香港城市大学、清华大学、 上海交通大学、西安电子科大、北京邮电大学等高校等及中科院上海微系统 研究所、沈阳自动化所、软件研究所、计算所、电子所、自动化所等科研机 构也展开了w s n 覆盖控制技术的研究。 由于无线传感器网络本身的特性，覆盖控制问题不可能只考虑覆盖这一 个因素【2 5 - 2 7 1 。而且大多数情况下，覆盖问题与连通性、节能、生命周期、路 由、调度等诸多因素都密切相关，甚至是紧耦合，采用某种单一的方法并不 能实现w s n 性能的最优化 2 8 - 3 0 1 。而混合机制就是在考虑多因素的前提下， 通过多种机制联合优化方式达到优化网络性能的目的【3 l 书1 。 随着w s n 领域的研究不断深入，对于w s n 覆盖控制算法的研究已不 仅仅包括单纯的覆盖含义，更与具体应用紧密相连。从无线传感器网络相关 应用视角将覆盖控制问题可以划分为连通性覆盖、节能覆盖、动念覆盖、与 不规则覆盖等方面，如图1 1 所示。下面分别介绍各类覆盖问题国内外研究 现状。 n 合尔滨r 程大学博十学何论文 图1 1 覆盖控制算法分类 f i g1 1c l a s s i f i c a t i o no fc o v e r a g ec o n t r o la l g o r i t h m s 1 2 1 连通性覆盖 连通性覆盖问题是w s n 覆盖控制中的一个重要组成部分，它同时考虑 了w s n 的覆盖能力和网络连通性这两个相互联系的属性。连通覆盖问题所 要解决的是如何同时满足网络一定的传感覆盖和通信连通性需求，这对于一 些要求可靠通信的应用至关重要【搏蚓。根据具体的连通性要求，连通性覆盖 又可具体分为两类：一般情况覆盖和最差最佳情况覆盖( w o r s t b e s t c a s e c o v e r a g e ) 。 1 2 1 1 一般情况覆盖 在许多实际自然环境中，由于网络情况不能预先确定且多数确定性覆盖 模型会给网络带来对称性与周期性特征，从而掩盖了某些网络拓扑的实际特 性。因此，需要对节点随机分布在传感区域而预先没有得到自身位置的情况 进行讨论，这正是无线传感器网络一般情况覆盖( 也称随机覆盖) 所要解决 的问题 3 7 - 3 s 1 。目前，w s n 的随机覆盖已成为w s n 覆盖控制的一个热点问 题。随机节点覆盖考虑在w s n 中传感器节点随机分布且预先不知道节点位 4 第1 章绪论 i | 1 置的条件f ，网络完成对监测区域的覆盖任务，学者关于此类问题的研究内 容较多，主要包括文献 3 9 4 5 文献 3 9 1 6 pg u p t a 等设计的算法通过选择连通的传感器节点路径来得到 最大化的网络覆盖效果。当指令中心向w s n 发送一个感应区域查询消息 时，连通传感器覆盖的目标是选择最小的连通传感器节点集合并充分覆盖 w s n 区域。文献 3 9 】分别设计了集中与分布式两种贪婪算法。假设已选择 的传感器节点集为m ，剩余与m 有相交传感区域的传感器节点称为候选节 点。集中式算法初始节点随机选择构成m 之后，在所有从初始节点集合出 发到候选节点的路径中选择一条可以覆盖更多未覆盖子区域的路径。将该路 径经过的节点加入m ，算法继续执行直到网络查询区域可以完全被更新后 的m 所覆盖。 文献 4 0 从理论角度出发，假设在给定监控区域内，传感器的到达服从 泊松分布或统一分饰的前提下，当感知范围或传感器节点数量的变化时对 w s n 的覆盖度的概率进行了理论分析，并给出了理论分析结果。文献 4 l 】 则采用定向传感器实现随机布置的传感器网络的覆盖，由于定向传感器可以 有效地避免感知范围其他节点的干扰，可以提高覆盖的效率，减少布置的节 点的数量。文献 4 2 】中t s a i 等从更加实际的应用场景出发，对有遮挡环境下 的分布式w s n 中的覆盖问题进行了研究，对遮挡所造成的感知覆盖范围的 性能进行了分析。由于遮挡物的存在，感知范围将变得不规则，接收信号强 度等发生改变，这使得覆盖控制更复杂。t s a i 的研究表明遮挡物的标准偏差 增加2 d b ，感知覆盖范围将降低1 0 。文献【4 3 】对位置信息未知情况下，如 何对传感器节点进行有效的调度以同时满足感知覆盖范围与网络连通性的要 求。为了实现上述要求，该文提出了一种联合覆盖与连通性的网络模型，以 分布式随机调度的方式动态地调整节点的感知覆盖范围，并建立了节点密 度、调度参数、覆盖质量、检测概率与检测延迟等因素之间的关系。 文献 4 4 】对节点位置无关、或节点与其邻居节点相对方向无关情况下的 覆盖问题进行了研究，在上述前提下，提出了几个理论上可证明的启发式算 法，这些算法通过与该节点两跳内的邻居节点进行信息交互，以确定节点的 冗余度。这些算法的特点是在没有精确的位置信息的前提下，具有较低的额 外开销和强壮性。并提出了两个分布式的低复杂度的协议，在不降低覆盖性 能的前提下，以切换的方式周期性地选择合适的活跃节点覆盖控制区域，以 哈尔滨i ：科人学博一卜学位论文 实现能量节省，延长网络生命周期。 文献 4 5 1 基于无线网络中提出的构建连通支配集( c o n n e c t e dd o m i n a t i n g s e t ，c d s ) 算法，用于选择骨干节点进行数据通信。当节点感知范围等于通 信范围时，c d s 中的节点可以覆盖网络中所有节点，即节点覆盖。同时也 保证网络的连通性。虽然现有的研究认为在节点部署密度很大时，通过构建 c d s 得到的节点覆盖可以近似于区域覆盖，但是节点覆盖并不等于区域覆 盖。该文分析了两者之间的关系，给出节点覆盖等于区域覆盖的充分必要条 件。根据分析结果，基于已有的构建c d s 算法，提出了一种与节点位置无 关网络连通性覆盖协议( l o c a t i o n i n d e p e n d e n tc o n n e c t e dc o v e r a g ep r o t o c o l ， l i c c p ) 。在l i c c p 协议中，每个节点无须知道自己的物理位置，根据本地 节点密度选择合适的通信范围，利用c d s 算法选出的工作节点可以提供高 质量的网络连通性覆盖、并在节能的同时有效地延长网络寿命。 这类算法的优点在于，节点传感区域模型可以是任意凸形区域，更加符 合实际环境；可以灵活地选择使用集中式或分布式方式实现；在保证网络覆 盖任务的同时，考虑了网络的连通性，算法周期执行降低了网络通信代价， 并可以延长网络的生存时间。这类算法的缺点是虽然同时考虑了连通性与网 络的覆盖性，但是由于覆盖问题的一般性，大多基于某些假设或特定的模 型，因此不能保证实用性；并没有考虑实际无线信道中出现的通信干扰等因 素。 1 2 1 2 最差最佳情况覆盖 最差情况覆盖是指在感知区域内寻找一条路径，当目标沿该路径穿越该 区域时被检测到的概率最小。因此，如果能找到该路径，并沿着该路径布置 节点以最大程度地提高w s n 覆盖性能与可监测性。而最佳情况覆盖的目标 正好相反，是在感知区域内寻找一条路径，当目标沿该路径穿越该区域时被 检测到的概率最大。找到最佳情况覆盖路径可以提高监控区域的安全性，同 时为高质量服务业务提供有效的途径。 最差情况覆盖典型的代表是“最小暴露路径( m i n i m a le x p o s u r e p a t h ) ，f 删与“最大突破路径( m a x i m a lb r e a c hp a t h ) ” 4 7 1 问题。最佳情况覆 盖典型的代表是“最大暴露路径( m a x i m a le x p o s u r ep a t h ) 4 8 1 与“最大支撑 路径( m a x i m a ls u p p o r tp a t h ) 1 4 7 1 问题。 6 笫1 章绪论 最差最佳情况覆盖分别采用计算几何中的v o r o n o i 图与d e l a u n a y 三角 形来完成最大突破路径和最大支撑路径的构造和查找。其中，v o r o n o i 图是 由所有d e l a u n a y 三角形边上的垂直平分线形成，而d e l a u n a y 三角形的各顶 点为网络的传感器节点，并满足子三角形外接圆中不含其他节点。由于 v o r o n o i 图中的线段具有到最近的传感器节点距离最大的性质，因此最大突 破路径一定是由v o r o n o i 图中的线段组成。最大突破路径查找过程如下： ( 1 ) 基于各节点的位置产生网络v o r o n o i 图； ( 2 ) 给每一条边赋予一个权重来代表到最近传感器节点的距离； ( 3 ) 在最小和最大的权重之| 、日j 执行二进制查找算法：每一步操作之前 给出一个参考权重标准，然后进行宽度优先查找( b r e a d t hf i r s ts e a r c h ) ，检查 是否存在一条从s 到d 的路径，满足路径上线段的权重都比参考权重标准 要大。如果路径存在，则增加参考权重标准来缩小路径可选择的线段数目， 否则就降低参考权重标准； ， ( 4 ) 最后得到一条从s 到d 的路径，也就是最大突破路径。 类似地，由于d e l a u n a y 三角形是由所有到最近传感器节点距离最短的 线段组成，因此最大支撑路径必然由d e l a u n a y 三角形的线段构成。给每一 条边赋予一个权重来代表路径上所有到周围最近传感器节点的最大距离，查 找算法同上。最差最佳覆盖算法的归纳如表1 1 中所示。 表1 1 最差最佳覆盖算法归纳 t a b l e1 1c o n c l u s i o no f b e s t w o r s t - c a s ec o v e r a g ea l g o r i t h m s 文献基本思想特点 优点：可指导网络节点的 分别采用计算几何中的v o r o n o i 图与 配置来改进整体网络的覆 d e l a u n a y 三角形来完成最犬突破路径和 盖：适用于1 ) 。9 络路径规 最大支撑路径的构造和查找。其中， 划、目标观测等许多戍用 【4 6 _ 4 8 v o r o n o i 图是由所有d e l a u n a y 三角彤边 场所。 ：的垂直平分线形成：而d e l a u n a y 三 缺点：前提较多，很多情 角形的各顶点为网络的传感器节点，并 况未考虑，不适用于网络 满足了：三角形外接圆中小含其他节点。 中存在节点覆盖能力有差 异时算法的执行情况。 这类算法的优点在于，在最佳与最差两种度量条件下，分别得到了临 哈尔滨。1 ：祥人学博十学何论文 界的网络路径规划结果，可以指导网络节点的酉己置来改进整体网络的覆盖； 作为一种特殊的w s n 覆盖控制算法，适用于网络路径规划、目标观测等许 多应用场所。缺点是，这些算法的前提是所有节点都是全局连通的，当一个 传感器检测到目标时，所有其他节点都能检测到该事件。而节点之间的通信 开销、延迟等并没有考虑；算法是集中式的计算方式，需要预先知道各节点 的位置信息；算法没有考虑实际中障碍、环境和噪声等可能造成的影响：网 络中均为同质节点，不适用于网络中存在节点覆盖能力有差异时算法的执行 情况。 1 2 2 节能覆盖 传感器节点采用电池供电，能量非常有限。如何提高节点的能量效 率，从而延长整个w s n 寿命就成为需要关注的一项重要研究内容【4 9 】。节能 覆盖可以分为两类：一是联合路由、生命周期最大化等因素的优化节能方 法；二是以多重覆盖方式，采用轮换“活跃”和“休眠节点的节能覆盖方 案，以有效地提高网络生存时间。 1 2 2 1 联合优化节能覆盖 联合优化节能覆盖是将其他属性如能耗、路由、网络生命周期等因素 与覆盖问题相结合，在保障覆盖能力的前提下，通过适当的方式实现节能。 文献 5 0 针对移动节点位置优化问题，提出了无线传感网络通