Determining Sensor Locations in Wireless Sensor Networks
Network lifetime plays an important role in the design of wireless sensor networks. This paper studies the problem of prolonging the wireless sensor network's lifetime, through introducing additional sensors at proper locations to achieve the goal of minimizing the length of the longest edge in...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2015-08-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2015/914625 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547232856932352 |
|---|---|
| author | Zimao Li Wenying Xiao |
| author_facet | Zimao Li Wenying Xiao |
| author_sort | Zimao Li |
| collection | DOAJ |
| description | Network lifetime plays an important role in the design of wireless sensor networks. This paper studies the problem of prolonging the wireless sensor network's lifetime, through introducing additional sensors at proper locations to achieve the goal of minimizing the length of the longest edge in the network. The problem is in fact the bottleneck Steiner tree problem, trying to find a Steiner tree minimizing the length of the longest edges for the given n terminals in the Euclidean plane by introducing at most k Steiner points. A restricted bottleneck Steiner tree problem is studied in this paper, which requires that only degree ≥3 Steiner points are not allowed to be adjacent in the optimal solution. We show that the restricted problem is MAX-SNP hard and cannot be approximated within performance ratio 2 in polynomial time unless P = NP; we first propose a polynomial time 3 -approximation algorithm and then improve the ratio to 2 + ε for any given ε > 0 , by presenting a polynomial time randomized approximation algorithm, which is almost optimal to the restricted problem. |
| format | Article |
| id | doaj-art-7ab3467b2f7e436eb284ae263714cd2e |
| institution | Kabale University |
| issn | 1550-1477 |
| language | English |
| publishDate | 2015-08-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-7ab3467b2f7e436eb284ae263714cd2e2025-02-03T06:45:31ZengWileyInternational Journal of Distributed Sensor Networks1550-14772015-08-011110.1155/2015/914625914625Determining Sensor Locations in Wireless Sensor NetworksZimao LiWenying XiaoNetwork lifetime plays an important role in the design of wireless sensor networks. This paper studies the problem of prolonging the wireless sensor network's lifetime, through introducing additional sensors at proper locations to achieve the goal of minimizing the length of the longest edge in the network. The problem is in fact the bottleneck Steiner tree problem, trying to find a Steiner tree minimizing the length of the longest edges for the given n terminals in the Euclidean plane by introducing at most k Steiner points. A restricted bottleneck Steiner tree problem is studied in this paper, which requires that only degree ≥3 Steiner points are not allowed to be adjacent in the optimal solution. We show that the restricted problem is MAX-SNP hard and cannot be approximated within performance ratio 2 in polynomial time unless P = NP; we first propose a polynomial time 3 -approximation algorithm and then improve the ratio to 2 + ε for any given ε > 0 , by presenting a polynomial time randomized approximation algorithm, which is almost optimal to the restricted problem.https://doi.org/10.1155/2015/914625 |
| spellingShingle | Zimao Li Wenying Xiao Determining Sensor Locations in Wireless Sensor Networks International Journal of Distributed Sensor Networks |
| title | Determining Sensor Locations in Wireless Sensor Networks |
| title_full | Determining Sensor Locations in Wireless Sensor Networks |
| title_fullStr | Determining Sensor Locations in Wireless Sensor Networks |
| title_full_unstemmed | Determining Sensor Locations in Wireless Sensor Networks |
| title_short | Determining Sensor Locations in Wireless Sensor Networks |
| title_sort | determining sensor locations in wireless sensor networks |
| url | https://doi.org/10.1155/2015/914625 |
| work_keys_str_mv | AT zimaoli determiningsensorlocationsinwirelesssensornetworks AT wenyingxiao determiningsensorlocationsinwirelesssensornetworks |