无线传感器网络分布式概率覆盖保持协议.doc

第1期田莹等：无线传感器网络分布式概率覆盖保持协议75无线传感器网络分布式概率覆盖保持协议田莹，张淑芳，王莹（大连海事大学 信息科学技术学院，辽宁 大连 116026）摘 要：覆盖配置能有效缓解无线传感器网络中节点能量受限的问题，但现有的研究多是基于物理覆盖，这与实际的信号传播特点不符。针对这一问题，提出了分布式传感器网络概率覆盖保持协议（DPCCP），该协议基于概率探测模型，利用Voronoi划分在节点本地执行概率覆盖判断算法。仿真实验中，将DPCCP嵌入LEACH路由协议，形成LEACHE协议，验证算法效率。仿真结果表明，DPCCP在保持网络覆盖度的同时，可关闭大量冗余节点，有效地延长了网络寿命。关键词：无线传感器网络；协议；分布式；概率覆盖中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2009)01-0070-06Distributed probabilistic coverage-preserving configuration protocol for wireless sensor network TIAN Ying, ZHANG Shu-fang, WANG Ying(College of Information Science and Technology, Dalian Maritime University, Dalian 116026, China)Abstract: Coverage configuration is an effective method to alleviate the energy-limitation problem of sensor nodes in wireless sensor networks. Most of current researches were based on physical coverage model which is inconsistent with the realistic characteristic of signal propagation. Therefore, a distributed probabilistic coverage-preserving configuration protocol (DPCCP) was proposed. This protocol is based on probabilistic detection model and used Voronoi diagram to judge the probabilistic coverage degree on sensor nodes. In the simulation, LEACHE was presented by embedding DPCCP into LEACH seamlessly without any modification of the original workflow to validate the efficiency of the algorithem. Simulation results show that DPCCP can effectively reduce the number of active sensor nodes and prolong the network lifetime on the condition of coverage-preserving.Key words: wireless sensor network; protocol; distributed; probabilistic coverage1 引言收稿日期：2007-10-18；修回日期：2008-12-05随着微机电系统、传感器技术、通信技术的发展，无线传感器网络技术已经广泛应用于军事、环境、家庭和商业等用途，如目标跟踪、环境观测、地震监测、智能家居和建筑物状态监控等应用1。但由于传感器网络节点的能量受限，如何在保证网络覆盖质量的前提下，延长网络使用寿命，已经成为无线传感器网络应用研究的重要方面2。在研究无线传感器网络覆盖问题的文献中，大部分采用确定性传感器探测模型，即传感器具有确定的探测精度和探测半径，目标区域内的一点如果处于某个传感器的探测半径之内，则认为该点是被覆盖的，文献3称这种覆盖为物理覆盖（physical coverage）。在物理覆盖的概念下，只有当目标区域内的任意一点都处于至少一个传感器节点的探测半径之内时，该被监测区域才处于完全覆盖状态。文献46研究了完全覆盖问题，给出了相应的完全覆盖算法。但是，完全覆盖在实际的无线传感器网络应用中有时是不可实现或者不必要的。例如，对于随机布置的无线传感器节点就不能确保目标区域内的任意一点都处于节点的监测范围之内，而且随着网络运行时间的增加，网络中可能会出现故障节点，这会进一步增加完全物理覆盖的难度；而对于天气预报方面的应用，传感器节点的覆盖面积达到目标区域面积的90%就可以获得令人满意的预测结果7。因此，提出了部分覆盖7（partial coverage）和百分比覆盖8（percentage coverage）的概念，放弃了对目标区域的完全覆盖，允许目标区域根据协议设定的覆盖度要求或覆盖百分比存在未被覆盖的区域，其目的是在满足应用对监测精度要求的情况下，使更多的节点进入休眠状态，保存能量。仿真结果表明这两种覆盖技术可以显著延长网络寿命。然而，在物理覆盖模型下，传感器节点独立地完成各自的探测任务，不考虑利用相邻传感器节点的测量结果进行数据融合，这与无线传感器网络的实际应用情况是不符的。在实际中，传感器节点间往往会进行数据融合，从而使监测性能得到提高9。概率覆盖算法采用了非确定性传感器探测模型，即传感器的探测精度随着感应信号衰减的规律而变化，根据目标到传感器距离的变化和环境因素的影响，通过多个传感器的协同工作，以一定的检测概率发现目标。目前，很多文献采用了这种概率探测模型讨论无线传感器网络覆盖问题，如文献912。文献10提出基于概率覆盖模型的概率覆盖算法（PCA），但只是用于评价随机布置的传感器网络检测概率的置信度。Co-Grid覆盖算法9将目标区域分成边界重叠的单元，采用基于概率的分布式探测模型，依据设定的虚报警率（或成功探测率），在各单元内选择数目最小的工作节点，达到节能的目的。Co-Grid算法虽然提出了网络配置方法，但算法要求的时间复杂度较高(O(2n)，对无线传感器网络的动态特性适应能力较差。文献11提出了一种基于概率探测模型的覆盖配置算法（CCAP），但只适用于评价点目标的覆盖概率。文献12提出了基于概率探测模型的覆盖保持协议（CPP），在保持网络覆盖前提下，使传感器网络中的工作节点数目尽可能小。但该协议采用中心控制算法配置网络，限制了网络的规模。并且，上述文献都没有将覆盖配置算法与具体的路由协议相结合，讨论节能效果。针对这些问题，本文提出了一种分布式的基于概率探测模型的覆盖保持配置协议(DPCCP，distributed probabilistic coverage-preserving configuration protocol)，本协议采用Neyman-Peason概率探测模型。DPCCP不同于其他概率覆盖保持算法在于：1）在保持网络覆盖程度的前提下，DPCCP采用分布式算法，使节点自调度自身的工作状态；2）基于Voronoi划分网络进行覆盖配置，并利用Voronoi图的性质简化配置算法；3）将DPCCP与LEACH协议13相结合，形成LEACHE (LEACH- extension) 协议，并与LEACH协议进行仿真比较，评价DPCCP协议的节能效果。2 算法模型的建立2.1 概率探测模型假设N个传感器节点随机分布在监测区域中，节点的位置为(xi , yi)，i=1,2,N，则第i个节点可以观测到目标的测量值可表示为3 (1)其中，是观测目标发射的信号强度；a是信号衰减指数，a0；di是位于(xt , yt)的目标到传感器节点Ni的距离，满足；ni为节点Ni的观测噪声。假设ni服从零均值的高斯分布，即，则节点Ni的二进制假设检验为(2)假设所有节点采用相同的检测门限t进行判决，则根据Neyman-Peason准则得到判决门限和虚警概率的关系为(3)(4)其中。位于(xt , yt)的观测目标被节点Ni观测到的检测概率为(5)其中。在无线传感器网络中，节点密度通常较高，因此，在监测区域发生的事件会被多个传感器节点同时检测到，此时系统对位于(xt , yt)的观测目标的检测概率可表示为10 (6)根据式（6），当多个传感器节点同时检测同一事件的发生时，系统检测概率PD将高于任何单个节点的检测概率PDi。2.2 参数定义定义1 （-概率覆盖）如果存在一个工作节点集合，位置为(xi , yi)，i=1,2,N，使目标点(xt , yt)处的系统检测概率PDg，则称点(xt , yt)满足-概率覆盖。如果一个区域中的所有点都满足-概率覆盖，则称这个区域为完全-概率覆盖。定义2 （K-传感器概率覆盖距离）K -传感器概率覆盖距离被定义为为了研究方便，假设di=rk，对任意i=1,2,K，此时，g为系统在目标点处的检测概率门限。当K=1时，传感器概率覆盖距离为r1，这说明单个传感器Ni独立工作时，无论其他节点是否工作，以Ni为圆心，r1为半径的圆盘区域必然满足完全g-概率覆盖。定义3 （最大感知距离Rs）最大感知距离被定义为。当节点Ni独立工作时，如果diRs，则节点Ni的检测概率为，此时节点Ni对目标点的系统检测概率的影响可忽略，其中l为影响系统检测概率的最小节点检测概率。本文假设网络中的每个传感器节点都可以获得自己在网络中所处的位置，与文献5,912中的假设相同，假设节点间的通信距离不小于最大感知距离，即RcRs，以保证网络配置时的连通性。3 分布式概率覆盖保持协议DPCCP适用于高密度、大规模、随机分布的传感器网络。本协议基于Neyman-Peason概率探测模型，在保持覆盖性能的前提下，通过传感器节点间的协同工作减少每个感知周期内工作节点个数，其中的概率覆盖判断算法，采用Voronoi划分网络，并利用Voronoi图的性质简化节点配置过程。3.1 Voronoi划分Voronoi图是计算几何中最基本的几何结构之一，广泛应用于地理学、生态学和物理学等多个领域15。Voronoi表示了空间点集之间的邻近关系，如图1为Voronoi划分的含有8个点的平面。假设N个传感器随机分布在观测区域中，则根据Voronoi平面划分的定义15，可以把无线传感器网络观测区域划分为N个接界的凸多边形。每个凸多边形分别含有一个传感器节点，含有节点Ni的凸多边形标为V(Ni)，并且V(Ni)内的任意一点P到节点Ni的距离必小于点P到其他传感器节点的距离。图1 Voronoi图划分的平面设节点Ni的坐标(xi , yi)，i=1,2,N，P点坐标(x , y)，其他节点坐标(xk , yk)，则其关系满足不等式(7)3.2 节点自调度策略在DPCCP中，节点以一定周期轮换工作状态，在每个工作周期的开始阶段，首先，传感器节点要初始化状态信息，包括关闭节点感知模块，更新节点自身和其邻节点的位置信息，并根据Voronoi划分方法，计算节点所在凸多边形的顶点位置；然后，节点执行覆盖配置算法，以判断在这个工作周期中是否可以进入休眠状态。如图2 所示，节点的判断过程可分为5个状态: 判断（checking），竞争（competition），启动（on-duty），等待（waiting），休眠（off-duty）。在这5个状态的转换过程中，节点要执行相应的判断。1) 判断状态：传感器节点利用本文提出的概率覆盖判断算法判断自己是否满足休眠的条件，如果符合条件（Eligibility）进入休眠状态；否则（Ineligibility）节点设置随机延迟时间，启动定时器，准备进入竞争状态。2) 竞争状态：如果定时器超时，则节点竞争成功（Win），进入启动状态；否则（Lose），进入等待状态。3) 等待状态：竞争失败的节点在等待状态中，接收竞争成功节点的广播消息On-duty Message，更新其他节点在本地保存的状态信息，然后进入判断状态，以便继续在判断状态中执行覆盖判断算法。4) 启动状态：竞争成功的点进入启动状态，首先，要向其他节点广播On-duty Message，其中包含该节点的惟一标识号ID和位置信息，同时开始执行感知工作。启动状态结束后，即一个工作周期结束，节点初始化状态信息，并准备开始下一周期的判断过程（Next period）。5) 休眠状态：传感器节点关闭不必要的装置，节省能量。休眠状态结束后，节点初始化状态信息，准备开始下一周期的判断过程。每个节点都要根据其他节点的状态执行自调度过程，直到确定自身为启用状态或休眠状态。图2 节点自调度状态转移3.3 概率覆盖判断算法假设传感器节点Ni存在若干个启动状态邻节点，如果节点Ni关闭时，V(Ni)满足完全-概率覆盖，则节点Ni可进入休眠状态，相反，如果此时V(Ni)不满足完全-概率覆盖，则节点Ni需要进入启动状态，以保证关闭网络中的部分节点后，网络的覆盖度不会减小。本文首次采用一种确定性的方法，在V(Ni)中找到概率覆盖最薄弱的一点P，只要该点处的系统检测概率达到-概率覆盖，则V(Ni)满足完全-概率覆盖。定理1 假设存在K个处于启动状态的传感器节点Ni，i=1,2,K，和一个目标点P，并且节点Ni到点P的欧式距离是di。如果，则点P必满足-概率覆盖。证明 设系统检在目标点处测概率门限为，则由定义2可知；令，则F(di)为关于di的单调递增函数，由平均值定理，当且仅当, 时“=”成立又因为F(di)为关于di的单调递增函数，当且仅当di=r，时,中的“=”成立又因为，当di=rk，时PD=。推论1 假设传感器节点Ni周围存在K个处于启动状态的节点Nk，k=1,2,K。如果V(Ni)中存在一点M，满足 且点M满足距离关系，则V(Ni)必满足完全-概率覆盖。文献14中定理2已经证明，V(Ni)中满足的点必然是V(Ni)的一个顶点。根据上述讨论，节点Ni在本地执行的概率覆盖判断算法为：找到V(Ni)中一个的顶点，使其符合在所有顶点中最大的要求，并判断这个顶点是否满足距离关系。如果满足距离关系，则V(Ni)必满足完全-概率覆盖；否则V(Ni)可能不满足完全-概率覆盖，为保持网络覆盖度，节点Ni需要进入启动状态。4 实验与仿真分析为了测试本文提出的概率覆盖算法性能，在面积(120120)m2区域内分别随机布置300、500、800、1 000个传感器，信号衰减指数a分别取1、1.25和1.5，g取0.90，Pfi取0.05，l取0.06，q取15，s取1。如图3所示，感应节点数目受信号衰减指数的影响变化很大，随着a值的增加，信号衰减严重，则保持覆盖度需要的感应节点数目大量增加。当布置的传感器节点密度达到一定值时，即使增加传感器节点数目，网络中只需要恒定数目的节点进行感知工作，就能够保持覆盖度。例如，当a取1时，无论布置的节点数目为300、500、800，甚至更多，网络中只需32个节点工作，就可以保持覆盖度。图3 概率覆盖算法性能DPCCP具有很强的实用性，能够直接嵌入现有的路由协议，无需改变原路由协议的工作过程。为了进一步验证DPCCP的节能效果，本文将DPCCP嵌入LEACH 13协议，形成LEACHE协议。LEACH协议是最早提出的一种分布式分簇路由协议，通过采用分簇式路由和TDMA通信机制，实现网络的节能。LEACH协议的执行过程被划分为多个周期，称为轮。每一轮又被划分为两个阶段：簇形成阶段和稳态通信阶段。在簇形成阶段，传感器节点采用分布式算法形成多个簇，每个簇含有惟一的簇头；在稳态通信阶段，簇内使用TDMA的通信方式，簇成员节点在自己占有的时隙与本簇头通信，而簇间的通信由簇头完成。LEACHE协议是在LEACH协议每轮的簇形成阶段之前，插入DPCCP算法，在保持网络覆盖度的前提下，先关闭冗余节点，再执行LEACH协议。图4 网络节点寿命图5 节点归一化平均剩余能量本文仿真中采用了LEACH协议的节点能量消耗模型13，将LEACHE与LEACH的节能效果进行比较，仿真参数中a取1，随机布置300个节点，其他参数与图3的仿真参数相同，每个节点的初始能量为E0=0.25J，基站的位置为(xb,yb)=(60m,150m)。图4仿真了网络节点寿命，LEACHE第一个节点失效的时间接近LEACH的2倍，而最后一个节点失效的时间LEACHE长达LEACH的5倍。因此，DPCPP的应用可以显著延长无线传感器网络寿命，并且保证网络监控质量。图5仿真了节点的归一化平均剩余能量曲线，仿真结果表明LEACHE能量消耗曲线比LEACH平稳，当LEACH的节点能量耗尽时，LEACHE才平均消耗了75的节点能量。因此，LEACHE的节能效果要远好于LEACH。5 结束语本文针对于大规模随机分布的无线传感器网络的覆盖问题进行了讨论。在概率探测模型的基础上，提出了DPCCP协议，该协议采用分布式算法，保持网络概率覆盖度的前提下，能使网络中大量冗余节点进入休眠状态。DPCCP协议采用基于Voronoi划分的概率覆盖判断算法，该算法利用Voronoi图的性质，将概率计算简化为距离计算，减小了节点执行算法的计算量，增强了算法的可实现性。仿真结果表明，DPCCP协议能够科学有效地关闭网络中的冗余节点，延长网络寿命。参考文献：1AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y. Wireless sensor networks: a surveyJ. IEEE Computer Networks, 2003,38: 393-422. 2CARDEI M, WU J. Energy-efficient coverage problems in wireless adhoc sensor networksJ. Journal of Computer Communications on Sensor Networks, 2005, 29(4): 413-420.3WANG B, WANG W, SRINIVASAN V. Information coverage for wireless sensor networksJ. IEEE Communications Letters, 2005, 9(11): 967-969.4TIAN D, GEORGANAS N D. Connectivity maintenance and coverage preservation in wireless sensor networksJ. Ad Hoc Networks, 2005, 3(6):744-761.5蒋杰,方力,张鹤颖,窦文. 无线传感器网络最小连通覆盖集问题求解算法J. 软件学报,2006,17(2):175-184.JIANG J, FANG L, ZHANG H Y, DOU W. An algorithm for minimal connected cover set problem in wireless sensor networksJ. Journal of Software, 2006,17(2):175-184.6屈玉贵,蔺智挺,赵保华. 无线传感器网络的WPCS覆盖策略J. 电子与信息学报，2007,29(4): 767-770.QU Y G, LING Z T, ZHAO B H. WPCS coverage strategy for wireless sensor networkJ. Journal of Electronics & Information Technology, 2007,29(4):767-770.7LIU Y Z, LIANG W F. Approximate coverage in wireless sensor networksA. Proceedings of the IEEE Conference on Local Computer Networks 30th Anniversary (LCN05)C. 2005. 1-8.8BAI H, CHEN X, HO Y C. Percentage coverage configuration in wireless sensor networksA. Lecture Notes in Computer Science3758C. 2005. 780-791.9XING G L, LU C Y, PLESS R. Co-grid: an efficient coverage maintenance protocol for distributed sensor networksA. IPSN04C. Berkeley, California, USA, 2004. 414-423.10AHMED N, KANHERE S, JHA S. Probabilistic coverage in wireless sensor networksA. Proceedings of the 30th Conference on Local Computer NetworksC. IEEE, USA, 2005. 672-679.11ZHANG D X, XU M, CHEN Y W. Probabilistic coverage configuration for wireless sensor networksA. Wireless Comm