A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor Networks
Navigation with wireless sensor networks (WSNs) is the key to provide an effective path for the mobile node. Without any location information, the path planning algorithm generates a big challenge. Many algorithms provided efficient paths based on tracking sensor nodes which forms a competitive meth...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2012-11-01
|
| Series: | International Journal of Distributed Sensor Networks |
| Online Access: | https://doi.org/10.1155/2012/715261 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832553243371110400 |
|---|---|
| author | Yuanchao Liu Shukui Zhang Jianxi Fan Juncheng Jia |
| author_facet | Yuanchao Liu Shukui Zhang Jianxi Fan Juncheng Jia |
| author_sort | Yuanchao Liu |
| collection | DOAJ |
| description | Navigation with wireless sensor networks (WSNs) is the key to provide an effective path for the mobile node. Without any location information, the path planning algorithm generates a big challenge. Many algorithms provided efficient paths based on tracking sensor nodes which forms a competitive method. However, most previous works have overlooked the distance cost of the path. In this paper, the problem is how to obtain a path with minimum distance cost and effectively organize the network to ensure the availability of this path. We first present a distributed algorithm to construct a path planning infrastructure by uniting the neighbors’ information of each sensor node into an improved connected dominating set. Then, a path planning algorithm is proposed which could produce a path with its length at most c times the shortest Euclidean length from initial position to destination. We prove that the distributed algorithm has low time and message complexity and c is no more than a constant. Under different deployed environments, extensive simulations evaluate the effectiveness of our work. The results show that factor c is within the upper bound proved in this paper and our distributed algorithm achieves a smaller infrastructure size. |
| format | Article |
| id | doaj-art-1d81f360066f43df87d65ff9a0a52852 |
| institution | Kabale University |
| issn | 1550-1477 |
| language | English |
| publishDate | 2012-11-01 |
| publisher | Wiley |
| record_format | Article |
| series | International Journal of Distributed Sensor Networks |
| spelling | doaj-art-1d81f360066f43df87d65ff9a0a528522025-02-03T05:54:32ZengWileyInternational Journal of Distributed Sensor Networks1550-14772012-11-01810.1155/2012/715261A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor NetworksYuanchao Liu0Shukui Zhang1Jianxi Fan2Juncheng Jia3 Institute of Computer Science and Technology, Soochow University, Suzhou 215006, China State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210093, China Institute of Computer Science and Technology, Soochow University, Suzhou 215006, China Institute of Computer Science and Technology, Soochow University, Suzhou 215006, ChinaNavigation with wireless sensor networks (WSNs) is the key to provide an effective path for the mobile node. Without any location information, the path planning algorithm generates a big challenge. Many algorithms provided efficient paths based on tracking sensor nodes which forms a competitive method. However, most previous works have overlooked the distance cost of the path. In this paper, the problem is how to obtain a path with minimum distance cost and effectively organize the network to ensure the availability of this path. We first present a distributed algorithm to construct a path planning infrastructure by uniting the neighbors’ information of each sensor node into an improved connected dominating set. Then, a path planning algorithm is proposed which could produce a path with its length at most c times the shortest Euclidean length from initial position to destination. We prove that the distributed algorithm has low time and message complexity and c is no more than a constant. Under different deployed environments, extensive simulations evaluate the effectiveness of our work. The results show that factor c is within the upper bound proved in this paper and our distributed algorithm achieves a smaller infrastructure size.https://doi.org/10.1155/2012/715261 |
| spellingShingle | Yuanchao Liu Shukui Zhang Jianxi Fan Juncheng Jia A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor Networks International Journal of Distributed Sensor Networks |
| title | A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor Networks |
| title_full | A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor Networks |
| title_fullStr | A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor Networks |
| title_full_unstemmed | A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor Networks |
| title_short | A Path Planning Algorithm with a Guaranteed Distance Cost in Wireless Sensor Networks |
| title_sort | path planning algorithm with a guaranteed distance cost in wireless sensor networks |
| url | https://doi.org/10.1155/2012/715261 |
| work_keys_str_mv | AT yuanchaoliu apathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks AT shukuizhang apathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks AT jianxifan apathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks AT junchengjia apathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks AT yuanchaoliu pathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks AT shukuizhang pathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks AT jianxifan pathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks AT junchengjia pathplanningalgorithmwithaguaranteeddistancecostinwirelesssensornetworks |