k coverage algorithm in wireless sensor network based on voronoi diagram

《k coverage algorithm in wireless sensor network based on voronoi diagram》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第38卷第4期计算机工程2012年2月Vol.38No.4ComputerEngineeringFebruary2012···网络与通信·网络与通信···文章编号：：：1000———3428(2012)04———0084———04文献标识码：：：A中图分类号：：：TP393基于Voronoi图的无线传感器网络K覆盖算法王王王成成成，成，，，樊建席樊建席，，，王仁喜，王仁喜，，，李，李李李硕硕硕(苏州大学计算机科学与技术学院，江苏苏州215006)摘摘摘要要要：要：：：针对无线传感器网络(WSN)在随机高密度部署节点情况下的多重覆盖问题，提出一个基于Voronoi图的K覆盖算法。该算法利用邻

2、居节点信息计算Voronoi覆盖邻居节点集，构建有向Voronoi覆盖关系图，通过调整关系图中的节点状态实现K覆盖。仿真结果表明，该算法能正确判断网络覆盖率，连通K覆盖的近似最小活动节点集数目少于CCP算法。关键词：：：无线传感器网络：；Voronoi图；最小覆盖集；多重覆盖；Voronoi覆盖邻居节点KCoverageAlgorithminWirelessSensorNetworkBasedonVoronoiDiagramWANGCheng,FANJian-xi,WANGRen-xi,LIShuo(SchoolofComputerScienceandTechnology,SoochowU

3、niversity,Suzhou215006,China)【【【Abstract】】】Fortheproblemofmulti-coverageunderthecasethatthesensornodesarehigh-densitydeployedinWirelessSensorNetwork(WSN),thispaperproposesak-coveringalgorithmbasedonVoronoidiagram.ThisalgorithmusestheinformationofneighborsnodestoestablishthesetcalledVoronoiCoverage

4、Neighbor(VCN)nodeset,thenbuildsadirectedgraphreflectingtherelationshipofthecoverage.Accordingtotherequirementcoverageofnetwork,adjuststhestateofnodestoachieveKcoverage.Simulationresultsshowthatthealgorithmcancorrectlydeterminethenetworkcoverage,andthenumberofapproximateminimumactivenodesissuperior

5、toCoverageConfigurationProtocol(CCP)algorithm.【【【Keywords】】】WirelessSensorNetwork(WSN);Voronoidiagram;minimumcoverageset;multi-coverage;VoronoiCoverageNeighbor(VCN)nodeDOI:10.3969/j.issn.1000-3428.2012.04.0281概述考虑1覆盖，对于目标区域的多重覆盖判断，文献[3,6]分别无线传感器网络是由大量微型传感器节点组成的，采用提出传感器节点的感知圆相交点K覆盖和相交圆周线的K覆自组织、多跳、无

6、线通信方式的大规模高密度网络系统，它盖检测方法，这2种方法都能有效保证K覆盖，但计算复杂广泛应用于军事、环境监测与预报系统、医疗卫生等领域。度偏高。文献[7]利用计算几何理论的K阶最近邻点Voronoi拓扑控制是无线传感器网络中的重要基础问题，它是在图检查网络多重覆盖度。但是相对普通Voronoi图，K阶最满足网络要求的覆盖度和连通度的前提下，通过睡眠调度、近邻点Voronoi图的构造方法是一个集中式算法，比较复杂。功率控制和邻居节点选择等方法，形成一个优化的网络结构，另外，文献[7]没有考虑冗余节点休眠问题。基于以上分析，[1]为其他功能模块提供基础。无线传感器网络节点一般采用本文在文献

7、[5]的基础上，提出一一一个基于普通Voronoi图的多随机高密度部署，大量的冗余节点会增加感知数据的冗余性重覆盖判别方法和连通K覆盖集构造算法。和发生无线通信冲突与干扰的可能性。睡眠调度是解决上述2网络模型与相关定义问题的有效手段，它通过某种规则方法，选择尽可能少的节2.1基本假设点作为活跃工作节点(最小连通覆盖集)提供可靠服务，其余本文工作基于如下基本模型假设：的节点则转入低功耗的睡眠状态，降低网络的能量消耗，延(1