Equilateral Triangle Partition-based Coverage Decision Algorithm for Sensor Networks

Coverage problem is a fundamental issue in the researches of sensor networks. It is important to determine whether a region of interest is sufficiently covered by a given set of sensors in lots of monitoring applications of sensor networks. An Equilateral Triangle Partition based Rapid k-Coverage Decision Algorithm and a solution algorithm of maximum k-Coverage problem were proposed, in which the region of interest is partitioned into equilateral triangles firstly, and then the complex area coverage problem is transformed into simple equilateral triangle coverage problem. Theoretical analysis and simulation results show that, for sensor networks with n different sensors, the new algorithm can solve the k-coverage problem correctly for any given region of interest with computation time cost of O(n) only, which is far below the computation time cost O(nlogn) of previously well-known algorithms.