The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region
Author
Source
International Journal of Distributed Sensor Networks
Issue
Vol. 2012, Issue 2012 (31 Dec. 2012), pp.1-25, 25 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2011-11-22
Country of Publication
Egypt
No. of Pages
25
Main Subjects
Telecommunications Engineering
Information Technology and Computer Science
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.
American Psychological Association (APA)
Ko, Ren-Song. 2011. The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region. International Journal of Distributed Sensor Networks،Vol. 2012, no. 2012, pp.1-25.
https://search.emarefa.net/detail/BIM-508043
Modern Language Association (MLA)
Ko, Ren-Song. The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region. International Journal of Distributed Sensor Networks No. 2012 (2012), pp.1-25.
https://search.emarefa.net/detail/BIM-508043
American Medical Association (AMA)
Ko, Ren-Song. The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region. International Journal of Distributed Sensor Networks. 2011. Vol. 2012, no. 2012, pp.1-25.
https://search.emarefa.net/detail/BIM-508043
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-508043