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/thesisDetails?columnId=74419880&Fpath=home&index=0 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850213132721455104 |
|---|---|
| author | YUAN yuan1 PENG Yu-xing1 LI Shan-shan2 TANG Wen-sheng3 |
| author_facet | YUAN yuan1 PENG Yu-xing1 LI Shan-shan2 TANG Wen-sheng3 |
| author_sort | YUAN yuan1 |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-9d549fff8b2c42d1bbe321dd0a1b85ec |
| institution | OA Journals |
| issn | 1000-436X |
| language | zho |
| publishDate | 2011-01-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-9d549fff8b2c42d1bbe321dd0a1b85ec2025-08-20T02:09:11ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2011-01-013210711774419880Efficient heuristic algorithm for the mobile sink routing problemYUAN yuan1PENG Yu-xing1LI Shan-shan2TANG Wen-sheng3In 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.http://www.joconline.com.cn/thesisDetails?columnId=74419880&Fpath=home&index=0wireless sensor networks;mobile sink routing;data collection;TSPN |
| spellingShingle | YUAN yuan1 PENG Yu-xing1 LI Shan-shan2 TANG Wen-sheng3 Efficient heuristic algorithm for the mobile sink routing problem Tongxin xuebao wireless sensor networks;mobile sink routing;data collection;TSPN |
| title | Efficient heuristic algorithm for the mobile sink routing problem |
| title_full | Efficient heuristic algorithm for the mobile sink routing problem |
| title_fullStr | Efficient heuristic algorithm for the mobile sink routing problem |
| title_full_unstemmed | Efficient heuristic algorithm for the mobile sink routing problem |
| title_short | Efficient heuristic algorithm for the mobile sink routing problem |
| title_sort | efficient heuristic algorithm for the mobile sink routing problem |
| topic | wireless sensor networks;mobile sink routing;data collection;TSPN |
| url | http://www.joconline.com.cn/thesisDetails?columnId=74419880&Fpath=home&index=0 |
| work_keys_str_mv | AT yuanyuan1 efficientheuristicalgorithmforthemobilesinkroutingproblem AT pengyuxing1 efficientheuristicalgorithmforthemobilesinkroutingproblem AT lishanshan2 efficientheuristicalgorithmforthemobilesinkroutingproblem AT tangwensheng3 efficientheuristicalgorithmforthemobilesinkroutingproblem |