Efficient heuristic algorithm for the mobile sink routing problem - YUAN yuan1; PENG Yu-xing1; LI Shan-shan2; TANG Wen-sheng3 (Tongxin xuebao)
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.