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

Ren-Song Ko

International Journal of Distributed Sensor Networks, 2011, vol. 8, issue 1, 918252

Abstract: 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.

Date: 2011
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.sagepub.com/doi/10.1155/2012/918252 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:sae:intdis:v:8:y:2011:i:1:p:918252

DOI: 10.1155/2012/918252

Access Statistics for this article

More articles in International Journal of Distributed Sensor Networks
Bibliographic data for series maintained by SAGE Publications ().