The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region
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 s...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2011-11-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2012/918252 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547199926403072 |
|---|---|
| author | Ren-Song Ko |
| author_facet | Ren-Song Ko |
| author_sort | Ren-Song Ko |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-164dc96e12e144d0807f49925f7fa33c |
| institution | Kabale University |
| issn | 1550-1477 |
| language | English |
| publishDate | 2011-11-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-164dc96e12e144d0807f49925f7fa33c2025-02-03T06:45:33ZengWileyInternational Journal of Distributed Sensor Networks1550-14772011-11-01810.1155/2012/918252918252The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored RegionRen-Song KoThis 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.https://doi.org/10.1155/2012/918252 |
| spellingShingle | Ren-Song Ko The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region International Journal of Distributed Sensor Networks |
| title | The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region |
| title_full | The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region |
| title_fullStr | The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region |
| title_full_unstemmed | The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region |
| title_short | The Complexity of the Minimum Sensor Cover Problem with Unit-Disk Sensing Regions over a Connected Monitored Region |
| title_sort | complexity of the minimum sensor cover problem with unit disk sensing regions over a connected monitored region |
| url | https://doi.org/10.1155/2012/918252 |
| work_keys_str_mv | AT rensongko thecomplexityoftheminimumsensorcoverproblemwithunitdisksensingregionsoveraconnectedmonitoredregion AT rensongko complexityoftheminimumsensorcoverproblemwithunitdisksensingregionsoveraconnectedmonitoredregion |