Efficient heuristic algorithm for the mobile sink routing problem
In large-scale monitoring region,randomly deployed wireless sensor networks may not be fully connected with high probability.Using mobile sink for data collection is one of the feasible solutions.Mobile sink shortest routing prob-lem can be regarded as a special case of TSP with neighborhoods（TSPN）...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2011-01-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/74419880/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In large-scale monitoring region,randomly deployed wireless sensor networks may not be fully connected with high probability.Using mobile sink for data collection is one of the feasible solutions.Mobile sink shortest routing prob-lem can be regarded as a special case of TSP with neighborhoods（TSPN） problem,since the neighborhoods are the radio ranges of the sensor nodes,which can be modeled as possibly overlapped disks with diverse sizes.This kind of TSPN problem has no polynomial algorithms so far.To handle it,a novel approximation algorithm was proposed,which first forms a "racetrack" by utilizing the non-intersecting loop property of TSP routes,and then through the inner lane heuris-tic,the bend heuristic and the shortcut searching,the algorithm can find an approximation solution within O（n2） computa-tion time.The formal proofs and the large-scale simulations all verify that our algorithm can achieve a good approxima-tion ratio and can be more efficient than the related algorithms. |
|---|---|
| ISSN: | 1000-436X |