（计算机应用技术专业论文）无线传感器网络基于覆盖问题的部署模型研究.pdf

大连理丁大学硕士学位论文 摘要 在无线传感器网络的部署中，节点间的检测区域会出现交叠，导致在某些区域存在 大量的冗余节点，既浪费节点的有限能量，又占用了网络信道：另一方面在其它部分区 域会出现盲点，使该区域不能被节点检测到，使网络的可信度和可靠性降低。无线传感 器网络不仅需要考虑覆盖问题，还必须保证节点间的连通性。由于节点部署后可能面临 不可预料的失效，仅仅保证1 连通不能有效地解决这个问题。 针对上述问题，本文对覆盖部署模型和拓扑控制方法进行了深入研究，具体工作体 现在以下几个方面： ( 1 ) 对覆盖控制算法问题进行了研究，重点分析了区域覆盖和栅栏覆盖两类问题， 为后续的网络拓扑结构优化设计提供了依据。 ( 2 ) 考虑了无线传感器网络的覆盖控制优化、感知模型的影响、约束条件以及节点 利用率等方面因素，提出了一种基于v o r o n o i 图的优化解决方案，实现全覆盖和至少2 连通性。感知范围可以用数学思想抽象为包含每个节点的v o r o n o i 多边形集合，节点与 v o r o n o i 剖分存在1 对1 的映射关系，求相应v o r o n o i 图面积的最大值，可以估算网络 中所用节点的最小值，从而减少网络的开销。 ( 3 ) 针对监测区域中的边界节点感知冗余问题，提出了基于边界拓扑控制的优化部 署策略。在维持网络拓扑全局性质的前提下，将覆盖部署划分为水平和垂直两类，根据 几何拓扑学的知识，有效地结合了网络连通度和连接角的内在关系，量化并优化三种基 本模型的部署，证明了模型的可靠性和各种部署最优方案之间的差异性。 ( 4 ) 对本文中所提方案均进行了模拟验证，在不同的部署模型下，衡量网络连通性、 节点定位及节点利用率等性能指标，并分析各方案的性能表现。 仿真表明，本文提出的基于v o r o n o i 图的优化解决方案在相同条件下优于相应文献 中的部署方案，使用更少的节点个数达到更好的覆盖效果。对提出的基于边界拓扑的优 化部署策略绘制了详细的节点部署网络拓扑图。模拟显示，每种部署模型在特定条件下 都有自身明显的优越性。但是当通信半径与感知半径的比值在【1 7 3 ，2 ) 时，6 连通情况下 的三角形部署模型的特点表现地更加明显，它比4 连通和3 连通部署的平均节点数分别 减少了2 3 9 和5 0 0 ，节点利用率最高可达8 2 7 。 关键词：无线传感器网络；连通；覆盖优化；v o r o n o i 图；拓扑控制 大连理工大学硕士学位论文 r e s e a r c ho nd e p l o y m e n tm o d e lb a s e do nc o v e r a g ei nw s n s a b s t r a c t i nt h ed e p l o y m e n to fw i r e l e s ss e n s o rn e t w o r k s ( w s n s ) ，t h e r em a yb eo v e r l a p p i n go f s e n s i n ga r e a so fn o d e so ral a r g eq u a n t i t yo fr e d u n d a n tn o d e si ns o m ea r e ao ft h en e t w o r k i n o n eh a n d ，s u c hp r o b l e m sl e a dt o w a s t i n go fe n e r g yo fn o d e sa n dm a k ec o m m u n i c a t i o n c h a n n e l sb u s y o nt h eo t h e rh a n d ，t h e r em a y a p p e a rb l i n da r e a sw h i c hc o u l dn o tb es e n s e db y t h es e n s o rn o d e s ，r e s u l t i n gi nt h ed e c r e a s i n go fr e l i a b i l i t ya n dc r e d i b i l i t yo ft h en e t w o r k a t t h es a m et i m e ，n o to n l ys h o u l dt h ec o v e r a g ep r o b l e mb ec o n s i d e r e d ，b u ta l s ot h ec o n n e c t i v i t y b e t w e e nn o d e s a st h e r em i g h tb eu n a n t i c i p a t e dl o s sa f t e rd e p l o y m e n t ，t h ep r o b l e mw i l ln o t b es o l v e dw i t ho n l y1 - c o n n e c t i v i t y t h ed e p l o y m e n tm o d e l sa n dt o p o l o g yc o n t r o lm e t h o d so fw 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 ep r o b l e mw e r er e s e a r c h e di nd e p t hi nt h i sp a p e r i tm a i n l ye m b o d i e di nf o l l o w i n g f o u ra s p e c t s ： ( 1 ) p a y i n gag r e a te f f o r to nt h ea l g o r i t h m so fc o v e r a g ec o n t r o l l i n gs t r a t e g y ，a n dm a i n l y f o c u s i n go nt h ea n a l y s i so f t h er e g i o nc o v e r a g ea n db a r r i e rc o v e r a g ew h i c h p a v e dt h ew a y f o r t h ef o l l o w i n go p t i m i z i n gd e s i g n i n go f t o p o l o g yo ft h en e t w o r k ( 2 ) a no p t i m i z e ds o l u t i o nw a sp r o p o s e db a s e do nv o r o n o ip o l y g o n sa f t e rw eh a v e a n a l y z e da tl e a s t2 - c o n n e c t i v i t ya n dc o n s i d e r e df a c t o r so fo p t i m i z a t i o no fw s n s c o v e r a g e c o n t r o l ，e f f e c t so f s e n s o rm o d e l s ，r e s t r i c t i o n sa n dn o d e se f f i c i e n c y t h u s 。t h ef u l lc o v e r a g e a n d2 - c o n n e c t i v ya r ei m p l e m e n t e d t h es e n s i n gr a n g ec a nb ed e s c r i b e da sas e to fv o r o n o i p o l y g o n sw h i c hi n c l u d e se v e r yn o d ew i t h1 一t o 一1m a p p i n g sb e t w e e nv o r o n o ip o l y g o n sa n d s e n s o rn o d e s s ot h em i n i m u mn u m b e r so fn o d e su s e di nt h en e t w o r kc a nb ee v a l u a t e d t h r o u g hm a x i m u mv a l u eo fc o r r e s p o n d i n gv o r o n o ip o l y g o n s ，t h e nt h ec o s to fn e t w o r ki s g r e a t l yr e d u c e d ( 3 ) f o rt h er e d u n d a n tp r o b l e mo fn o d e si ns e n s i n gb o u n d a r yo fs e n s i n gr e g i o n ，a n o p t i m i z a t i o nd e p l o y m e n ts t r a t e g yw a sp r o p o s e db a s e do nt h et o p o l o g i c a lc o n t r o l l i n go f b o u n d a r i e s c o v e r a g ed e p l o y m e n tw a sd i v i d e di n t o v e r t i c a ld e p l o y m e n ta n dh o r i z o n t a l d e p l o y m e n to nt h ep r e m i s eo fm a i n t a i n i n gg l o b a lp r o p e r t yo fn e t w o r kt o p o l o g y t h ep a p e r c o m b i n e dw i t hi n t e r n a lr e l a t i o n sb e t w e e nn e t w o r kc o n n e c t i v i t ya n dc o n n e c t i o n a n g l e s a c c o r d i n gt ot h e o r i e so fg e o m e t r i c a lt o p o l o g ye f f i c i e n t l y d e p l o y m e n to ft h e3k i n d so fb a s i s p a t t e r n sw a so p t i m i z e da n dt h ed i f f e r e n t i ao fo p t i m a ls o l u t i o n sa n dr e l i a b i l i t yo fm o d e l sw e r e p r o v e d 一i i i 无线传感器网络基于覆盖问题的部署模型研究 ( 4 ) t h ep a p e rv e r i f i e dt h ep e r f o r m a n c eo fa l lt h es o l u t i o n sp r o p o s e di nt h i sp a p e rb y s i m u l a t i o nc o n s i d e r i n gt h ef a c t o r so fd i f f e r e n td e p l o y m e n t s ，c o n n e c t i v i t yo fn e t w o r k ， p o s i t i o n so fn o d e sa n dt h eu t i l i z a t i o n sr a t eo fn o d e s t h es i m u l a t i o n ss h o wt h a t ，t h eo p t i m i z m i o np a t t e r nb a s e do nv o r o n o ip o l y g o no ft h i s p a p e ri s b e t t e rt h a nd e p l o y m e n tp a t t e r ni nc o r r e s p o n d i n gw o r k s ，w h i c ha c h i e v e db e t t e r c o v e r a g er e s u l t sw i t hf e w e rn o d e s a l s o ，t o p o l o g i c a lg r a p ho fn o d e sd e p l o y m e n tn e t w o r ki s p l o t t e df o ro p t i m i z a t i o nd e p l o y m e n tm o d e l sb a s e do nb o u n d a r yt o p o l o g y t h ee x p e r i m e n t i l l u s t r a t e st h a te v e r yd e p l o y m e n tm o d e lh a sap r e d o m i n a n ta d v a n t a g ei nac e r t a i ns i t u a t i o n h o w e v e r ，w h e nt h er a t i oo fc o m m u n i c a t i o nr a d i u sa n ds e n s o rr a d i u si sb e t w e e n 1 7 3 ，2 ) ，t h e t r i a n g l ep a t t e r nb a s e do n6 - c o n n e c t i v i t ys h o w sg r e a ts u p e r i o r i t y ，a n dc o m p a r e dt ot h em o d e l s b a s e do n4 - c o n n e c t i v i t ya n d3 - c o n n e c t i v i t y ，t h ea v e r a g en u m b e ro fn o d e su s e dr e d u c e db y 2 3 9 a n d5 0 o s e p a r a t e l y ，w h i l et h ee f f i c i e n c yo fn o d e sr e a c h e sa sh i g ha s8 2 7 k e yw o r d s ：w i r e t e s ss e n s o rn e t w o r k s ；c o n n e c t i v i t y ；c o v e r a g eo p t i m i z a t i o n ； v o r o n o ip o t y g o n ；t o p o l o g yc o n t r o l i v 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 垂线焦整基圃终耋量壁垒因丝坠登薹趔堑堑 作者签名：邀血日期： 型2 年l 月二卫日 大连理工大学硕十学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：丞缝焦整篷图缝叁匙羔f 要题垒翌羞蕉堡堑堑 作者签名：墨坠 ，垫日期：且年l 月二望日 导师签名：匿l 生主蓊一日期：军年l 月j 日 大连理t 大学硕士学位论文 1 绪论 1 1 研究背景及意义 在当今信息技术飞速发展的时代，以i n t e m e t 为代表的信息网络给人们的生活带来 了巨大的变化。微电子技术、计算技术和无线通信等技术的进步，推动了低功耗多功能 传感器的快速发展，使其在微小体积内能够集成信息采集、数据处理和无线通信等多种 功能。无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 就是由部署在监测区域内大量 的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳的自组织的网络系统， 其目的是协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。 传感器、感知对象和观察者构成了传感器网络的三个要素。如果说i n t e r n e t 构成了逻辑 上的信息世界，改变了人与人之间的沟通方式，那么，无线传感器网络就是将逻辑上的 信息世界与客观上的物理世界融合在一起，改变人类与自然界的交互方试。人们可以通 过传感器网络直接感知客观世界，从而极大地扩展了现有网络的功能和人类认识世界的 能力。 无线传感器网络打破了传统的点对点数据信息交互方式，提出了一种崭新的分散信 息交换模式，实现了物理世界、计算世界以及人类社会三元世界的连通。无线传感器网 络在环境恶劣、无人职守、资源受限的环境中显示了很大的应用价值，能够客观有效的 获取物理信息，具有十分广阔的应用前景，推动了低功耗多功能传感器的快速发展，使 其在微小体积内部能够集成信息采集、数据处理和无线通信等多种功能。无线传感器网 络是当前国际上备受关注的、由多学科高度交叉的前沿研究热点领域之一。美国商业周 刊和m r r 技术评论在预测未来技术发展的报告中，分别将无线传感器网络列为2 1 世纪 最有影响的2 1 项技术和改变世界的1 0 大技术之一1 1 j 。传感器网络、塑料电子学和仿生 人体器官又被称为全球未来的三大高科技产业i 引。 1 2 国内外的研究现状 最早的传感器网络出现在上个世纪七十年代，将传统的传感器采用点对点传输连接 传感控制而构成传感器网络，称之为第一代传感器网络。随着传感器技术以及计算机技 术的发展，传感器网络同时还具有了获取多种信息信号的综合处理能力，并通过与传感 控制器的相连，组成了有信息综合和处理能力的传感器网络，这是第二代传感器网络。 从上世纪末开始，现场总线技术开始应用于传感器网络，人们用其组建智能化传感器网 络，大量多功能传感器被运用，并使用无线技术连接，无线传感器网络逐渐形成。它在 无线传感器网络基于覆盖问题的部署模型研究 数据采集、传输、融合分析于一体，是信息技术的一个新领域，在环境监测、医疗监护、 交通管理、军事侦察等领域具有广阔的应用前景p j 。 从2 0 0 0 年起，国际上开始出现一些有关传感器网络研究结果的报道，引起了世界 各国军事部门、工业界和学术界的极大关注。美国军方有包括c 4 k i s r 计划、s m a r ts e n s o r w e b 、灵巧传感器网络通信、无人值守地面传感器群、传感器组网系统、网状传感器系 统c e c 等研究。最近几年来，传感器技术和通信技术的迅速发展使得传感和通信的结 合成为最新兴的技术；功能越来越强的计算机以及网络的普遍化发展使得网络计算能力 大大加强；m e m s ( 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 ) 的迅速发展为设计和实现 s o c ( s y s t e mo nc h i p ) 提供了基础；更小、更廉价的低功耗计算设备代表的“后p c 时代 冲破了传统台式计算机和高性能服务器的设计模式。所有这些技术上的进步使得新的信 息获取和处理模式有了很大的改变，无线传感器网络就是在这种大环境下逐步发展的。 1 3 本文的研究问题及分析 1 3 1 覆盖控制与冗余问题 研究覆盖控制和冗余问题是传感器网络中的重要支撑技术之一，对网络覆盖的测量 能够使我们了解是否存在监测和通信盲区，了解被监测区域的无线传感器网络的覆盖情 况，从而重新调整传感器节点分布或者在将来添加传感器节点时可采取相应的改进措 施。以通过调整网络覆盖的密度，对被监测区域中重要区域设置特质节点，部署更多的 传感器节点，保证测量数据的可靠性。因此，网络覆盖有着很重要的意义，对网络性能 有着直接的影响。 无线传感器网络首先要实现监测区域或目标对象信息的有效的感知覆盖和通信覆 盖。包括以下内容：监控对象的所有目标都必须满足覆盖需求，根据监测需求的不同， 重要的区域可能要多重覆盖来到达感知精度的要求。在满足信息感知要求的同时，还要 能把采集的信息传输给用户，满足通信的连通覆盖要求。为了节省能量来延长网络生存 时间，以及减少节点之间的干扰，在满足感知覆盖和通信覆盖的前提下，通过节点调度 机制让尽可能多的节点进入睡眠状态。 无线传感器网络的覆盖控制关注的是传感器节点对监测区域的情况分析，确定节点 如何部署、工作节点如何进行选择，实现对监测区域或目标对象物理信息的精确感知与 信息传递，以满足网络的监控需求，同时提高w s n s 的相关性能，如延长网络工作寿命、 保证网络连通性等。覆盖控制问题对网络的监控服务质量具有重要的支持作用，覆盖问 题可以看作是传感器网络服务质量的一种度量。覆盖控制的手段多种多样，在一些环境 优化、人为可达、网络规模较小的应用中，可以通过节点合理部署实现对监控对象的完 大连理t 大学硕士学位论文 全覆盖。而在环境恶劣、节点数量大、传感器随机分布的应用场合，需通过工作节点的 调度实现网络监控区域的完全感知。 考虑到小体积、低成本的传感器节点往往采用电池来提供能量，网络传输中的冗余 数据将会极大地耗尽电池能量，进而缩短整个网络的生存时间。为了尽可能地减少冗余 数据导致的额外能量消耗，延长网络生存时间，需要对随机部署的网络的拓扑进行优化 控制，在保持覆盖性能的前提下，减少工作节点数1 4 j 。 一种解决办法是将高密度部署的节点划分成若干互不相交的节点集合，每个节点集 合都能维持目标区域或目标点的原始覆盖质量，通过轮换每个集合的工作时间，在任意 时刻只有一个节点集合处于工作状态，从而延长整个网络的生存时间。显然，网络的生 存时间与这样的节点集合数成正比。 消除或者减少节点的覆盖冗余是减少系统能耗，延长生存时间的有效方式。如果一 个节点的感知区域完全被邻居节点的覆盖区域包含，那么关闭该节点不会导致网络覆盖 性能下降。问题的关键是节点如何仅仅依赖局部邻居节点的信息，自主判断是否属于覆 盖冗余。为此，需要设计分布式、局部化的冗余覆盖检测算法重新部署网络中的节点结 构。 1 3 2 覆盖连通问题的研究进展及算法分析 覆盖是提供监测和目标跟踪服务质量的一种度量。随着无线传感器网络应用的普 及，更多的研究工作深入到其网络配置的基本理论方面，仅仅研究覆盖问题是远远不够 的，连通性也需要研究。覆盖网络可以允许一定的容错性和盲点存在，但是一旦失去了 连通性，整个网络只能被迫瘫痪。此外，传感器在部署之后，可能遭受不可遇料的攻击 和失效，因此仅仅研究1 连通问题是不够的，同时也为研究k 连通问题( 后 1 ) 提出了 新的挑战。本文的研究重点主要在于部署前和部署阶段的网络的覆盖问题和连通问题， 与此相关的研究工作大概有以下方面： 无线传感器网络覆盖的研究最初是从计算几何发展起来的。因为传感器节点具有造 价高并且携带能量少的特点，所以如何选用最少的节点实现覆盖是前期大量研究工作的 目标。早在1 9 3 9 年的文献【5 1 中严格证明了点在圆面上的全覆盖问题，随后又在很多领 域被重新证实，这也为近几年来无线传感器覆盖问题奠定了坚实的理论基础1 6 j 。 在对覆盖问题算法的研究中，有很多是基于全局信息寻找次优结果的算法，这种算 法一般用于网络部署或者重部署。文献f 7 1 使用线性规划技术选取最小活动节点集合来保 证覆盖性。在该研究中，作者使用的模型是二维和三维的点阵网格，并分析了目标定位 的问题，作者假设每个传感器节点的感应距离都足够与数据汇集点通信，因而省略了对 无线传感器网络基于覆盖问题的部署模型研究 连通性的考虑。除了提出使用整数线性规划解决来保证全局覆盖情况下最小化传感器造 价的问题外，作者对节点数的边界进行了分析，并给出设置适当节点位置的方法。 文献【8 1 在发起区域概念的基础上提出了基于局部信息计算来控制节点是否工作并 保持完全覆盖的算法。发起区域指一个邻居覆盖的最大区域。当一个节点接收到邻居发 送的数据包时，就计算该邻居的发起区域，如果其邻居的发起区域总和包含了该节点所 覆盖的区域，就关闭。文献【8 1 研究的是在节点部署后阶段如何调度节点的工作以延长网 络生存时间，该研究没有考虑连通问题。 文献 9 q u 定义了一个判断性的覆盖问题，目标是判断网络中的每一个点是否都在k 个传感器的覆盖之下( k 是预先指定的值) ，每个节点的覆盖区域可以是任意大小。该工 作提出了一个多项式时间的算法，该算法可以转换为分布式算法。 连通覆盖与通信半径和感知半径之间有着内在的关系。最早讨论这个问题的是文献 f 1 0 1 ，文中证明了如果通信半径大于或等于感知半径的两倍，那么传感器网络覆盖则保 证网络的连通性。如果通信半径设置的太大，无线通信会产生相互干扰，这样会大大降 低网络的运行效率和生存时间。所以，为了保证网络的连通性，通信半径设置成感知半 径的两倍是一个好的选择。文献【1 1 】则进一步指出，当通信半径大于或等于两倍感知半 径时，k 覆盖保证k 连通。其中k 覆盖是指目标区域中的每一点都在至少k 个传感器节 点的感知范围之内，而k 连通是指，网络中任何k 1 个节点失效，网络都能保证连通。 文献1 1 2 1 在文献 1 0 ，1 1 的基础上进一步对如下命题做出了严格证明：在初始部署的网络 是k 连通的条件下，“通信半径至少是感知半径的两倍”是k 覆盖保证k 连通的充分必 要条件。 1 3 3 本文研究内容 在众多节点部署覆盖方案中，本文选取均匀部署作为研究的出发点。它的节点布阵 相对容易，网络中节点能量消耗相对集中，为监测和勘探提供了强大的理论基础。在综 合了以上小节文献的思想及文献 1 2 1 知，当= r c 时，线性方案的部署可以达到近似最优 解，从文献【1 3 】得知，n r c r , 2 1 t e i ，才能完成网络的覆盖与连通，而文献 1 4 ，1 5 i k n 示我们，当1 r , rs时，为网络的二连通提供可行性的保障。本文分别分析节点覆盖,2 与连通的关系，最终找出在不同部署条件下的最优解。 本文的主要贡献在以下几个方面： ( 1 ) 分析节点全覆盖与2 连通的关系，并找出在不同部署条件下的最优解。考虑优 化时要在传感器节点数相对少，同时要求1 覆盖的面积尽可能达到最大，从而达到对节 点的利用率最高。 大连理工大学硕十学位论文 ( 2 ) 网络布局状况，受r c 肛和边界因素的影响，利用逼近的方法，求出传感器理想 数量的逼近值。由于1 覆盖的面积越大，则要求围成每个节点的v o r o n o i 多边形面积最 大，它面积的大小受仉影响，从而影响网络布局状况，这种状况也正体现了它与传感 器节点个数的关系。 ( 3 ) 综合网络覆盖性能的各项指标，对基于常规的三角形、四边形及六边形的规则 部署作比较，验证最优解传感器节点数量的最小值，并通过实验证实各自的适用范围。 1 3 4 本论文的组织结构 本论文分为六章，其中 第一章：叙述了无线传感器网络研究背景及意义，同时阐述了国内外在本课题应用 领域的发展现状及研究进展，并对本论文的主要研究工作和论文组织结构进行了说明。 第二章：介绍了无线传感器网络的基本概念、网络体系结构、应用到覆盖领域的基 本模型及特点，同时对几种常见的感知模型进行了相关的分析。 第三章：分析了无线传感器网络覆盖的相关技术并对现有的无线传感器网络覆盖控 制算法进行分类介绍和比较。 第四章：在网络的连通性、定位、边界覆盖等问题上对已有的部署方案进行了分析， 给出了基于v o r o n o i 的覆盖优化方案，减少了节点数目和网络的开销并由实验模拟证实。 第五章：对网络拓扑结构进一步改进，提出了基于网络拓扑的优化部署模型，从覆 盖优化算法的性能指标出发，并通过仿真证明此方案的可行性和有效性。 最后结论部分对论文作了总结，提出了今后研究的方向。 无线传感器网络基丁覆盖问题的部署模犁研究 2 覆盖相关理论及模型 2 1无线传感器网络结构 2 1 1 传感器节点结构 传感器节点及网络的研究项目提出的传感器节点实物模型中，传感器的体系结构如 图2 1 所示。结构由四个主要模块组成：处理器模块、传感器模块、无线通信模块和能 量模块。其中，处理器模块是控制中心，控制整个传感器节点的操作，存储、处理自身 感应和其他节点传送的数据；传感器模块在监测区域内采集信息并进行数据转换；无线 通信模块负责与其他的传感器节点进行通信，交换控制信息和收发采集数据；能量供应 模块通常采用微型电池【1 6 j 为传感器节点运行提供能量。 图2 1 传感器节点的体系结构 f i g 2 1 a r c h i t e c t u r eo fs e n s o rn o d e 2 1 2 传感器网络的体系结构 按照w s n s 的应用类型，无线传感器网络可分为两种结构：同构型和异构型。同构 型w s n s 是所有的传感器节点具有相同的硬件配置和性能，有的节点具有采集功能，有 的节点具有数据传输与处理功能，有的节点同时具有这两种功能，节点间协同工作完成 工作任务；异构型w s n s 多采用分簇的网络结构，网络分成一个个簇，簇由特质节点( s i n k n o d e ) 和簇内节点组成，特质节点相对于普通节点具有更多的能量，更大的传输半径， 更强的通信、计算能力。一般由簇内节点感应信息，然后传递给特质节点进行信息的融 合和中转。特质节点可对附近的普通节点进行分工管理，如图2 2 所示。传感器节点一 一6 一 大连理工大学硕十学位论文 般有同时兼具信息的采集、发送和路由的功能，传感器节点将感应的数据通过多跳传递 给特质节点，特质节点再将信息传递给下一站的特质节点，最终将消息传送给接收基站。 萏 特质节点 。 普通节点特质节点管理区 + 一一一一 特质节点通信层 图2 2 无线传感器网络异构型体系结构图 f i g 2 2h e t e r o g e n e o u sa r c h i t e c t u r eo fw i r e l e s ss e n s o rn e t w o r k s 从网络功能上看，每个传感器节点兼顾传统网络节点的终端和路由器双重功能，除 了进行本地信息收集和数据处理外，还要对其他节点转发来的数据进行存储、管理和融 合等处理，同时与其他节点协作完成一些特定任务。 2 2 覆盖控制的基本模型 覆盖控制是无线传感器网络应用的一个基本问题，即在保证一定的服务质量( q o s ) 条件下，如何达到网络覆盖范围最大化，提供可靠的监测和目标跟踪服务。对网络覆盖 的测量能够使我们了解是否存在监测和通信盲区，了解被监测区域的无线传感器网络的 覆盖情况，从而重新调整传感器节点分布或者在将来添加传感器节点时可采取相应的改 进措施。以通过调整网络覆盖的密度，对被监测区域中重要区域设置特质节点，部署更 多的传感器节点，保证测量数据的可靠性。因此，网络覆盖有着很重要的意义，对网络 性能有着直接的影响。 无线传感器网络基丁覆盖问题的部署模犁研究 文献【1 7 】给出了一个无线传感器网络的简单覆盖模型，这是覆盖问题最基本的情况。 设有一个面积为s 的监控区域，每个传感器节点可以检测的范围是一个圆，圆的半径r 即为探测距离，所有的传感器节点都独立地进行工作。如图2 3 所示。 f i g 2 3 s i m p l ec o v e r a g em o d e l 首先，不考虑节点可能落入边界区域造成覆盖面积的减小，每个传感器节点所监控 的区域为：r r 2 ，则每个传感器能监控整个区域的概率p 。斌2 s ，令一个节点覆盖区域 的概率为： p 口) = p ( 2 1 ) 假设传感器节点的布置是相互独立的事件，则两个传感器节点覆盖区域的概率为： p 似+ 么) = p ( 彳) + 尸( 么) 一p ( 彳) p ( 彳) = 1 一( 1 一p ) 2 ( 2 2 ) 同理3 个节点所能检测的覆盖概率为： p ( 彳+ 彳+ 彳) ；p ( 彳+ 彳) + p ( 彳) - p + 彳) p 口) = 1 一( 1 - p ) 3 ( 2 3 ) 因此根据数学归纳法可以得知，1 1 个节点的覆盖概率是： p ( 4 + 么+ + 彳) = 1 - ( 1 - p f ( 2 4 ) 所以，要以概率p 来监测面积为s 的目标区域，传感器半径为尺，则所要的随机布 置的传感器节点数目为： 川吨。秽刊2 面l g ( 1 - 甭p ) ( 2 5 ) 当某些节点抛洒在区域边界的时候( 图2 4 所示) ，其覆盖率小于p 。 大连理丁大学硕士学位论文 图2 4 节点抛洒在边界的覆盖情况 f i g 2 4 t h en o d e so nt h ee d g eo ft h ea r e a 假设节点在区域外的覆盖面积为s ，则节点数n 满足： 鲤婆 一堡( ! 二旦! ( 2 6 ) 1 9 ( 1 一等)l g ( 1 - 篓) 文献【1 7 】给出了理想情况下，覆盖一个面积为以。的区域，所需要的传感器节点的 最小数目为： n a t 2i | a 撇= h | 厨 q 作者在文献【1 8 】中通过引入正六边形的结构，通过几何运算得出了这个关系式。 2 3 感知模型 2 3 1 感知原型 w s n s 的工作环境对节点的传感、通信都有不可忽视的影响，尤其是w s n s 多应用 于恶劣环境，节点的传感及通信范围难以保证为某一固定半径的圆，传感与通信具有方 向性，且随着距离的增大，监控准确度和概率都相应减小，如图2 5 ( a ) 所示，称为“感 知原型。感知原型没有统一的数学表述形式，在覆盖控制研究中采用较少。 一9 一 无线传感器网络基于覆盖问题的部署模焉4 研究 蕊、”一i ：0 0 、欢斟)：魁) 姒，) 2 3 2 二元感知模型 在二维平面上，传感器节点的覆盖范围是一个以节点为圆心，以，为半径的圆形区 域。该圆形区域称为传感器节点的“感知圆盘”。，f 称为传感器节点的感知半径，由节 点感知单元的物理特性决定。假设节点的坐标为s 以，y ，) ，在二元感知模型中，对于平 面上任意一点p ( x p ，y ，) ，节点s 检测到点p 处发生的事件的概率为 鹏p ) = 忙 孑 ( 2 8 ) 其中，d ( s ，p ) = 瓴一x p ) 2 + ( y ，一y p ) 2 为点p 和节点s 之间的欧几里德( e u c l i d ) 距离。 类似地，在二元感知模型中节点在三维空间中的感知范围是一个以节点为中心，为半 径的球形区域。 2 3 3 概率感知模型 传感器的感知模型对分析覆盖问题至关重要。二元感知模型假定传感器节点对事件 的检测是确定的。在实际应用环境中，由于环境噪声干扰以及信号强度随传输距离衰减， 传感器节点的监测能力表现出一定的不确定性，概率感知模型反映了这种不确定性。在 文献【1 9 】中所采用的感知模型在去除方向性的同时，保留了距离对感知精度的影响，随 着传感器与监控目标距离的增大，传感器对目标的感知概率也逐渐减小直至无法感知， 如图2 5 ( c ) 所示，称为“概率感知模型”，概率感知模型是一种连续模型，当单个传感 器无法满足监控的概率需求时，可以通过多节点监控信息的融合进行协同感知，从而能 够提取出单个传感器无法监控到的目标信息，最大程度还原现实网络环境中的物理信息 大连理t 大学硕士学位论文 感知状态，更加符合网络感知的较高要求。在概率感知模型中， 点处发生的事件的概率为 p ，( s ，p ) = e 一碰卯 传感器节点检测到任意 其中，a ( s ，p ) 为节点s 与事件发生点p 之间的欧几里德距离( e u c l i d ) ， 节点的感知能力以及信号随距离的衰减程度。显然，只有当d g ，p ) = 0 时， p ，g ，p ) ；1 。 文献【2 0 】对概率检测模型进行了修正： ( 2 9 ) 参数口表示 检测概率 f o 厂+ 妄a ( s ，p ) p r g ，p ) = t e - x a p ，一 矗 ，p ) ，因此就相应的增加了计算的复杂性。 人连理工大学硕十学位论文 ( 砂 ， 、 。i ， ( 、 f n i ) ! 乡 、 d卜 刁 ， 八刑 (5c渺 d卜 ( a ) 粒度较大的网格尺寸( b ) 粒度较小的网格尺寸 图3 5 在不同网格尺寸下的采样点分布 f i g 3 5 d i s t r i b u t i o no ft h es a m p l e si nv a r i o u ss i z e so fg r i d s 上述算法需要一个中心节点( c e n t r a ln o d e ) 来执行，就会潜在地导致该节点的计算负 担和网络瓶颈问题的出现。为此，算法结合了m a x m i nd c l u s t e r 分簇协议【3 5 1 ，分担中 心节点的计算量，平均节点的能耗，延长网络生存时间。但算法中精度与算法运行时间 是一对矛盾量，需要平衡考虑。 3 1 2 点覆盖 点覆盖指的是离散的点目标在任意时刻至少被一个传感器覆盖。它关心的是覆盖目 标区域中的一组点，它只需对目标区域内的有限个离散点进行监测，并确定覆盖这些点 的节点位置和所需的最少节点数。图3 6 显示了一组随机分布的传感器覆盖一组观测点 的例子。 图3 6 点覆盖 f i g 3 6 p o i n tc o v e r a g e 无线传感器网络基丁覆盖问题的部署模犁研究 在每个时间间隔内，只有一个传感器节点集合处于工作状态，其他集合将依次被唤 醒。由此可见，点覆盖的优化就是确定不相交集合的最大数，就相应的延长了每个传感 器两次激活的时间间隔，整个网络寿命也得到了延长。 点覆盖与区域覆盖对网络信息的要求不同，实现点覆盖只需邻居集合的信息，区域 覆盖则还需要几何、方向等方面的数据。 3 1 3 栅栏覆盖 在特定环境下( 如战场) ，人们关心目标以任意路径穿越传感器节点部署的区域被感 应到的概率。栅栏覆盖考虑的正是这样一类的问题，以找到起始位置和终止位置的一条 或者多跳路径。如图3 7 所示。 f i g 3 7 b a r r i e rc o v e r a g e ( 1 ) 覆盖最差和最好情形的控制算法 文献 3 6 ，3 7 】中指出，如果某条路径上的每个点与最近节点的距离最大，则该路径称 为“最大突破路径( m a x i m a lb r e a c hp a t h ) ”，如图3 8 所示。显然，当目标沿着这样的路 径穿越网络时，不被检测到的概率最大。相对于检测方而言，这样的路径是“最坏情形 路径”。与之对应的是，如果路径上的每个点与最近节点的距离最小，则称该路径为“最 大支撑路径( m a x i m a ls u p p o r tp a t h ) 。当目标沿着这样的路径穿越网络时，被检测到的 概率最大，因此这样的路径是“最好情形路径 。 大连理工大学硕士学位论文 图3 8 最大突破路径与最大支撑路径 f i g 3 8 m a x i m a lb r e a c hp a t ha n dm a x i m a ls u p p o r tp a t h m e g u e r d i c h i a n 提出了解决“最坏 和“最好 问题的两种算法，为放置额外的传感 器来改善覆盖提供了依据。算法以计算几何中的v o r o n o i 图( 第四章将详细介绍) 与 d e l a u n a y 三角形为理论基础。由于v o r o n o i 图是区域中的点到最近的传感器节点距离最 大的点的集合，因此“最大突破路径 一定是由v o r o n o i 图中的线段组成；相反d e l a u n a y 三角划分后的线段到最近传感器节点距离最短，因此“最大支撑路径”由d e l a u n a y 三 角形的线段构成。然后给每一条边赋予一个权重来代表到最近传感器节点的距离，利用 查找算法寻找出“最好”和“最坏 情形的路径。 “最坏”和“最好”两种情况下，分别得到了临界的网络路径规划结果，可以指导 网络节点的配置来改进整体网络的覆盖。 ( 2 ) 覆盖暴露模型的控制算法 以上的控制算法都是假定传感器节点的模型为二元感知模型。而在“目标暴露( t a r g e t e x p o s u r e ) ”覆盖模型控制算法中，节点的感知能力随着距离的增加成指数衰减，被称为 指数感知模型。 文献 3 8 】把随机部署的传感器节点的感知模型定义为义岛力2 南。一个运动 目标沿着路径p 在时间间隔为i t ，t ，l 内经过w s n s 监视区域的暴露路径定义为 b ；