Finding best and worst k-coverage paths in multihop wireless sensor networks

Coverage is a fundamental problem in wireless sensor networks (WSNs). From both economic and applicable concerns, designers always would like to provide guaranteed QoS of coverage of WSNs. In this paper, we address two path-coverage problems in WSNs, maximum k-support path coverage (a.k.a. best case coverage) and minimum k-breach path coverage (a.k.a. worst case coverage), in which every point on the desired resultant path is covered by at least k sensors simultaneously while optimizing certain objectives. We present two polynomial-time approaches to find optimal solutions for both maximum k-support coverage problem and minimum k-breach coverage problem. The time complexity of both algorithms are O(k²n log n), where n is the number of deployed sensor nodes and k is the coverage degree. In addition, a number of properties of kth-nearest point Voronoi diagram are presented, which is new to the literature.