POSTER: Approximation Algorithm for Minimizing the Size of Coverage Hole in Wireless Sensor Networks

摘要

Covering a bounded region with minimum number of homogeneous sensor nodes is an NP-complete problem [1]. In this article we have introduced a variation of area coverage problem in which the boundary sensor nodes of a coverage hole are allowed to move towards the hole for minimizing the size of the hole. We have shown that this problem is NP-hard. A ρ??approximation algorithm is proposed to solve this problem, where 2?≤?ρ?≤?3 and O(ΔlogΔ?+?k~ 2) is the time complexity.