Optimal k-support coverage paths in wireless sensor networks

Coverage is a fundamental problem in wireless sensor networks since sensors may be spread in arbitrary manner. In this paper, we addressed the k-support coverage problem. Most of the existing works assume that the coverage degree is 1, i.e. every point in a certain path falls within the sensing range of at least one sensor node. In this work, we focus on the case when we require that every point on the path is covered by at least k sensors, while optimizing certain objectives. We give an optimal polynomial-time algorithm and prove that the time complexity of our algorithm is O(k²n²). To the best of our knowledge, this is the first polynomial time algorithm finding an optimum k-coverage path in sensor networks with general sensing radius and general k.