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

• 作者: 唐文胜 彭宇行 李姗姗 袁远
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: 传感器网络 移动sink路由 数据收集 TSPN
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 技术报告
• 页码范围: 107-117
• 分类号: TP393
• 字数: 8305字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-436X.2011.10.014

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	唐文胜	湖南师范大学计算机教学部	47	282	9.0	15.0
2	彭宇行	国防科学技术大学计算机学院并行与分布式处理国家重点实验室	43	448	13.0	19.0
3	李姗姗	国防科学技术大学计算机学院软件所	14	293	8.0	14.0
4	袁远	国防科学技术大学计算机学院并行与分布式处理国家重点实验室	4	24	2.0	4.0