基于区域分割和Voronoi图的区域覆盖算法

针对无线传感器网络区域已知的区域覆盖问题，提出了一种基于区域分割和Voronoi图的覆盖算法（RSV）。算法首先分析已知区域的地理信息和兴趣点，根据传感器感知能力，构造合适大小的网格将已知区域细化分割。然后基于分割后的各个区域，根据兴趣点的数量划分其为不同权重部分，并初步设计传感器位置。根据初步部署位置和权重，对不同权重位置构造Voronoi图填补覆盖空洞，直至所有空洞被填补完毕，并为了延长运行寿命设计了合适的节点休眠策略。仿真实验显示，基于区域分割和加权Voronoi图的目标区域覆盖算法相较于现有算法，在节点数量增加较少的情况下，延长了网络的运行寿命，同时使节点能量消耗更加平均，在节点数量受限情况下，算法对有效区域的覆盖效果也更佳。

Area coverage algorithm based on region segmentation and Voronoi diagram

This paper proposed a novel algorithm based on region segmentation and Voronoi diagram(RSV) for area coverage problem with certain area in WSN. The algorithm analyzed points of interest(POI) and geographic information in certain area and designed the grid to divide the area. With the number of POI in divided area, the algorithm designed the initial deployment. According to the initial deployment location and weight, the algorithm constructed Voronoi diagram to fill the coverage holes for different weight positions until all the holes were filled and designed a suitable node dormancy strategy to prolong WSN lifetime. The results of simulation experiment show that the RSV algorithm prolongs WSN lifetime and balances the energy consumption among all sensors with less increased number of sensors. The RSV algorithm also has better coverage of the effective area with limited number of sensors.