高效的移动sink路由问题的启发式算法  

Efficient heuristic algorithm for the mobile sink routing problem

作　　者：袁远[1] 彭宇行[1] 李姗姗[2] 唐文胜[3] 

机构地区：[1]国防科学技术大学计算机学院并行与分布式处理国家重点实验室,湖南长沙410073 [2]国防科学技术大学计算机学院软件所,湖南长沙410073 [3]湖南师范大学计算机教学部,湖南长沙410081

出　　处：《通信学报》2011年第10期107-117,共11页Journal on Communications

基　　金：国家重点基础研究发展计划("973"计划)基金资助项目(2011CB302601);国家自然科学基金项目(60903224;60903223);国家自然科学基金项目(60903223)~~

摘　　要：移动sink最短路由问题可以看作是带邻近区域的旅行商问题(TSPN)的一个特例,其邻近区域为随机部署的传感器节点的无线通信范围,可建模成大小各异并且存在重叠的圆盘。由于目前还不存在多项式时间算法来解决该种TSPN问题,提出了一种新颖的启发式算法。它利用TSP路径为不自交环路的特性构造一条赛道,通过内圈启发式、弯道启发式以及捷径搜索在O(n2)时间复杂度内找出赛道内的近似最短路径。形式化证明和大规模模拟实验都验证了该算法较同类算法能够更高效地找出较优的近似解。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.

关 键 词：传感器网络 移动sink路由 数据收集 TSPN 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]