传感器网络中基于Voronoi网格的快速覆盖判定算法

覆盖问题是传感器网络研究中的一个基础课题,判定感兴趣的区域是否被一组给定的传感器节点完全覆盖,在监控等传感器网络的许多应用领域中具有重要意义。提出了一种传感器网络中基于Voronoi网格的快速覆盖判定算法VT-RCDA(Voronoi Tessellation based Rapid Coverage Decision Algorithm)。算法首先将感兴趣的区域进行正方形网格剖分,然后采用Voronoi网格模型将复杂的区域覆盖问题转化为简单的顶点覆盖问题。理论分析与仿真实验表明,与已有算法相比,新算法具有较好的覆盖判定正确率,较低的计算复杂度,且针对具有n个节点的传感器网络,能在O(nlogn)的时间开销内快速判断出任意给定感兴趣区域能否被这n个传感器节点覆盖。

Voronoi Tessellation-based Rapid Coverage Decision Algorithm for Wireless Sensor Networks

Coverage problem is a fundamental issue in the researches of sensor networks. In lots of applications area of sensor networks such as monitoring, etc, it is of great importance to determine that whether the area of interest is completely covered by a given set of sensors. A novel Voronoi tessellation-based rapid coverage decision algorithm was proposed, in which the area of interest was partitioned into square grid firstly, and then the complex area coverage problem was transformed into simple vertexes coverage problem by using Voronoi Tessellation models. Theoretical analysis and simulation results show that, compared with existed algorithms, the new algorithm has good correctness rate of coverage decision, lower computation complexity, and for sensor networks with n different sensors, can determine that whether a randomly given area of interest is completely covered by the n different sensors with time cost of O (nlogn).