基于Voronoi图的无线传感器网络覆盖空洞检测算法  

Coverage hole detection agorithm based on Voronoi diagram in wireless sensor network

作　　者：戴国勇[1,2] 陈麓屹[1] 周斌彬[1] 徐萍[1] 

机构地区：[1]浙江树人大学信息科技学院,杭州310014 [2]浙江工业大学计算机科学与技术学院,杭州310023

出　　处：《计算机应用》2015年第3期620-623,共4页journal of Computer Applications

基　　金：浙江省教育厅科研项目(Y201432448);国家自然科学基金面上项目(61379023)

摘　　要：针对无线传感器网络(WSN)中节点随机部署或部分节点能量耗尽带来的覆盖空洞(CH)问题,提出了一种基于Voronoi图的覆盖空洞检测算法。该算法利用节点的位置信息在覆盖区域范围内构建Voronoi图,通过计算每个Voronoi区域内的节点到该区域的顶点和边的距离来判断是否存在覆盖空洞,标识覆盖空洞的边界节点。仿真实验评估了不同节点分布密度、不同感知半径对空洞平均检测时间、平均能耗的影响,并与路径密度(PD)算法进行比较。实验结果表明所提算法在空洞平均检测时间和节点平均能耗两个方面均有10%左右的提升,对进一步延长网络生存期具有重要价值。To address the Coverage Hole （CH） problem in Wireless Sensor Network （WSN） caused by nodes＇ random deployment or running out of energy, a novel coverage hole detecting algorithm was proposed for wireless sensor networks in this paper. The location information of sensor nodes was used to build the Voronoi diagram for the monitored area. Then the distances between a sensor node and the vertex or edges of the corresponding Voronoi cell were calculated to decide the existence of coverage holes and identify the border nodes. Simulations were conducted to evaluate the performance of the proposed algorithm within different sensing ranges and nodes density. The performance comparison with the Path Density （PD） algorithm shows that the proposed algorithm has about 10% promotion both in average detection time and average energy consumption, which is important for prolonging the network lifetime.

关 键 词：无线传感器网络 覆盖空洞 VORONOI图 能耗 半分布式算法 

分 类 号：TP393.03[自动化与计算机技术—计算机应用技术]