The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region

Abstract EN

This paper considers the complexity of the Minimum Unit-Disk Cover (MUDC) problem.

This problem has applications in extending the sensor network lifetime by selecting minimum number of nodes to cover each location in a geometric connected region of interest and putting the remaining nodes in power saving mode.

MUDC is a restricted version of the well-studied Minimum Set Cover (MSC) problem where the sensing region of each node is a unit-disk and the monitored region is geometric connected, a well-adopted network model in many works of the literature.

We first present the formal proof of its NP-completeness.

Then we illustrate several related optimum problems under various coverage constraints and show their hardness results as a corollary.

Furthermore, we propose an efficient algorithm for reducing MUDC to MSC which has many well-known algorithms for approximated solutions.

Finally, we present a decentralized scalable algorithm with a guaranteed performance and a constant approximation factor algorithm if the maximum node density is fixed.