第３２卷第１Ｏ期 ２０１１年１０月 通信学报
Ｊｏｕｍａｌ ｏｎ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｖｂｌ＿３２ Ｎｏ．１０
０ｃｔｏｂｅｒ ２０１Ｉ
高效的移动ｓｉｎｋ路由问题的启发式算法 袁远１彭宇行 ，李姗姗 ，唐丈胜。 （１．国防科学技术大学计算机学院并行与分布式处理国家重点实验室，湖南长沙４１００７３： ２．国防科学技术大学计算机学院软件所，湖南长沙４１００７３；３．湖南师范大学计算机教学部，湖南长沙４１００８１）
摘要：移动ｓｉｎｋ最短路由问题可以看作是带邻近区域的旅行商问题（ＴＳＰＮ）的一个特例，其邻近区域为随机部署 的传感器节点的无线通信范围，可建模成大小各异并且存在重叠的圆盘。由于目前还不存在多项式时间算法来解 决该种ＴＳＰＮ问题，提出了一种新颖的启发式算法。它利用ＴＳＰ路径为不自交环路的特性构造一条赛道，通过内 圈启发式、弯道启发式以及捷径搜索在Ｏ（ｎ ）时间复杂度内找出赛道内的近似最短路径。形式化证明和大规模模 拟实验都验证了该算法较同类算法能够更高效地找出较优的近似解。 关键词：传感器网络；移动ｓｉｎｋ路由：数据收集；ＴＳＰＮ 中图分类号：ＴＰ３９３ 文献标识码：Ｂ 文章编号：１０００．４３６Ｘ（２０１１）１０—０１０７—１１
Ｅｆｆｉｃｉｅｎｔ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｍｏｂｉｌｅ ｓｉｎｋ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ＹＵＡＮ ｙｕａｎ ，ＰＥＮＧ Ｙｕ—ｘｉｎｇ ，ＬＩ Ｓｈａｎ．ｓｈａｎ２，ＴＡＮＧ Ｗｅｎ．ｓｈｅｎｇ
（１．ＰＤＬ，ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ，ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ４１００７３，Ｃｈｉｎａ； ２．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｓｏｆｔｗａｒｅ，Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅ￣ｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ ４１００７３，Ｃｈｉｎａ； ３．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｔｅａｃｈｉｎｇ，Ｈｕｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ ４１００８１，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎ ｌａｒｇｅ—ｓｃａｌｅ ｍｏｎｉｔｏｎｎｇ ｒｅｇｉｏｎ，ｒａｎｄｏｍｌｙ ｄｅｐｌｏｙｅｄ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｍａｙ ｎｏｔ ｂｅ ｆｕｌｌｙ ｃｏｎｎｅｃｔｅｄ ｗｉｔｈ ｈｉｇｈ ｐｒｏｂａｂｉｌｉｔｙ．Ｕｓｉｎｇ ｍｏｂｉｌｅ ｓｉｎｋ ｆｏｒ ｄａｔａ ｃｏｌｌｅｃｔｉｏｎ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｆｅａｓｉｂｌｅ ｓｏｌｕｔｉｏｎｓ．Ｍｏｂｉｌｅ ｓｉｎｋ ｓｈｏｒｔｅｓｔ ｒｏｕｔｉｎｇ ｐｒｏｂ— ｌｅｍ Ｃａｎ ｂｅ ｒｅｇａｒｄｅｄ ａｓ ａ ｓｐｅｃｉａｌ ｃａｓｅ ｏｆ ＴＳＰ ｗｉｔｈ ｎｅｉｇｈｂｏｒｈｏｏｄｓ（ＴＳＰＮ）ｐｒｏｂｌｅｍ，ｓｉｎｃｅ ｔｈｅ ｎｅｉｇｈｂｏｒｈｏｏｄｓ ａｒｅ ｔｈｅ ｒａｄｉｏ ｒａｎｇｅｓ ｏｆ ｔｈｅ ｓｅｎｓｏｒ ｎｏｄｅｓ，ｗｈｉｃｈ Ｃａｎ ｂｅ ｍｏｄｅｌｅｄ ａｓ ｐｏｓｓｉｂｌｙ ｏｖｅｒｌａｐｐｅｄ ｄｉｓｋｓ ｗｉｔｈ ｄｉｖｅｒｓｅ ｓｉｚｅｓ．Ｔｈｉｓ ｋｉｎｄ ｏｆ ＴＳＰＮ ｐｒｏｂｌｅｍ ｈａｓ ｎｏ ｐｏｌｙｎｏｍｉａｌ ａｌｇｏｒｉｔｈｍｓ ｓｏ ｆａｒ．Ｔｏ ｈａｎｄｌｅ ｉｔ，ａ ｎｏｖｅｌ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｗａｓ ｐｒｏｐｏｓｅｄ，ｗｈｉｃｈ ｆｉｒｓｔ ｆｏｒｍｓ ａ“ｒａｃｅｔｒａｃｋ”ｂｙ ｕｔｉｌｉｚｉｎｇ ｔｈｅ ｎｏｎ－ｉｎｔｅｒｓｅｃｔｉｎｇ ｌｏｏｐ ｐｒｏｐｅｒｔｙ ｏｆ ＴＳＰ ｒｏｕｔｅｓ，ａｎｄ ｔｈｅｎ ｔｈｒｏｕｇｈ ｔｈｅ ｉｎｎｅｒ ｌａｎｅ ｈｅｕｒｉｓ— ｔｉｃ，ｍｅ ｂｅｎｄ］ｈｅｕｒｉｓｔｉｃ ａｎｄ ｔｈｅ ｓｈｏｒｔｃｕｔ ｓｅａｒｃｈｉｎｇ，ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｌｌ ｆｉｎｄ ａｎ ａｐｐｒｏｘｉｍａｔｉｏｎ ｓｏｌｕｔｉｏｎ ｗｉｔｈｉｎ Ｏ（ｎ ）ｃｏｍｐｕｔａ— ｔｉｏｎ ｔｉｍｅ．Ｔｈｅ ｆｏｒｍａｌ ｐｒｏｏｆｓ ａｎｄ ｔｈｅ ｌａｒｇｅ—ｓｃａｌｅ ｓｉｍｕｌａｔｉｏｎｓ ａｌｌ ｖｅｒｉｆｙ ｔｈａｔ ｏｕｒ ａｌｇｏｒｉｔｈｍ Ｃａｎ ａｃｈｉｅｖｅ ａ ｇｏｏｄ ａｐｐｒｏｘｉｍａ— ｔｉｏｎ ｒａｔｉｏａｎｄ ｃａｎｂｅｍｏｒｅ ｅｆｆｉｃｉｅｎｔｔｈａｎｔｈｅ ｒｅｌａｔｅｄ ａｌｇｏｒｉｔｈｍｓ． Ｋｅｙ ｗｏｒｄｓ：、￣ｖｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ；ｍｏｂｉｌｅ ｓｉｎｋ ｒｏｕｔｉｎｇ；ｄａｔａ ｃｏｌｌｅｃｔｉｏｎ；ＴＳＰＮ
言 霎薹 在大面积的Ｅｔ标监控区域内，随机部署的无线 是控制移动ｓｉｎｋ来访问每个无线传感器节点，收集 收稿日期：２０１０—１０ ０２；修回日期：２０１１．０４．１１ 基金项目：国家重点基础研究发展计划（“９７３”计划）基金资助项目（２０１１ＣＢ３０２６０１）；国家自然科学基金项目（６０９０３２２４， ６０９０３２２３）；国家自然科学基金项目（６０９０３２２３） Ｆｏｕｎｄａｔｉｏｎ Ｉｔｅｍｓ：Ｔｈｅ Ｎａｔｉｏｎａｌ Ｂａｓｉｃ Ｒｅｓｅａｒｃｈ Ｐｒｏｇｒａｍ ｏｆ Ｃｈｉｎａ（９７３ Ｐｒｏｇｒａｍ）（２Ｏｌ１ＣＢ３０２６０１）；Ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ（６０９０３２２４，６０９０３２２３） 通信学报 第３２卷 完数据后送回基站。这样不但能够省去传感器节点 多跳转发数据的通信能耗，同时移动ｓｉｎｋ可以靠近 部署的节点，保证了链路质量。然而移动ｓｉｎｋ也面 临节能问题，即需要考虑设计一条最短路径使移动 ｓｉｎｋ能够完成对所有的传感器节点间的数据收集， 这被称作“移动ｓｉｎｋ路由问题”。 如果不考虑无线通信范围，移动ｓｉｎｋ路由问题 能够简单地规约成一个旅行商问题（ＴＳＰ）。传感器网 络中许多关于移动性控制方面的研究也正是利用 了这种规约，例如ＲＤ．ＶＴ算法 与ＰＢＳ算法 Ｊ。 这些工作为了简化问题，忽略了无线通信范围，都 假设ｓｉｎｋ只有移动到传感器节点的位置上才有数据 的交互。事实上，如图１所示，利用无线通信范围， ｓｉｎｋ的路径长度可得到极大的缩短。 如果考虑无线通信范围，则移动ｓｉｎｋ路由问题 可以被看作是带邻近区域（ｎｅｉｇｈｂｏｒｈｏｏｄｓ）的ＴＳＰ问 题（ＴＳＰＮ）Ｉ￣－－种特殊情况【４】。在ＴＳＰＮ问题中，商 人不需要与顾客见面，只需将自己的商品送到顾客 的邻近区域则完成了交易；而在移动ｓｉｎｋ路由问题 中，移动ｓｉｎｋ只需要进入传感器节点的无线通信范 围就能够获取到数据，因此无线通信范围即是邻近来 建模 Ｊ。由于部署有先后或者规格不同等原因，传 感器节点的通信半径受电池剩余能量的影响也不 一样；同时由于随机部署，不同节点的通信范围存 在重叠的可能。因此移动ｓｉｎｋ路由问题可等价于一 个邻近区域是随机部署的大小各异并且存在重叠 的圆盘区域的ＴＳＰＮ问题。 ＴＳＰＮ问题最早于１９９４年由Ｅ．Ａｒｋｉｎ和Ｒ． Ｈａｓｓｉｎ开始研究ｌｂｊ。近年来，针对不同形状邻近区 域，如线段、凸多边形、圆盘等，以及针对不同位 置关系的邻近区域，即重叠、弱重叠或者不重叠， 国内外学者们提出了很多近似算法。其中针对圆盘 区域的算法主要讨论了不重叠但大小各异的圆盘 区域Ｉ６Ｊ或者重叠但等大小的圆盘区域［７１２种特殊情 况，而移动ｓｉｎｋ路由问题中的圆盘区域既大小各异 又存在重叠，这种情况是ＴＳＰＮ问题中的新难点， 目前还没有专门针对该难题的高效算法。由于重叠 邻近区域的ＴＳＰＮ问题已经被证明了是ＡＰＸ—Ｈａｒｄ 的【８Ｊ，并且在传感器网络应用中，部署的节点数目
一般几百甚至上千，时间复杂度过高的算法不受欢 迎，因此更需关注的是如何降低算法时间复杂度。 在这篇文章中，提出了一种新颖的启发式算法来解 决移动ｓｉｎｋ路由问题，取名为“ＲａｃｅＴｒａｃｋ”。该 算法特点在于先从传感器节点所在位置构造一条 ＴＳＰ路径，再利用ＴＳＰ路径为不白交环路的几何 特性构造一条ｓｉｎｋ可能经过的赛道（ｒａｃｅｔｒａｃｋ），然 后通过本文提出的内圈启发式、弯道启发式以及 捷径搜索逐步找到赛道中的近似解。本文的主要 贡献如下。 １）利用ＴＳＰ路径的几何特性，提出了一种新颖 的移动ｓｉｎｋ路由启发式算法：构造一条赛道，并根 据赛车原理求解。高效地解决了存在重叠且大小各 异的圆盘邻近区域的ＴＳＰＮ问题。 ２）该算法能够高效地在Ｏ（ｎ ）时间内为移动 ｓｉｎｋ设计出一条近似最短路径，较现有同类ＴＳＰＮ 算法更适合大规模的移动ｓｉｎｋ路由问题。 ３）理论上证明了算法近似比为Ｉ 。。ｌ＜（１＋ ）
（Ｉ ｌ＋２∑ Ｉ），并且大规模的模拟实验结果也验 证了该算法的有效性。
２相关工作 在ＴＳＰＮ问题中，若将每个邻近区域都看成 一个点，则ＴＳＰＮ问题可转化成ＴＳＰ问题。因此， ＴＳＰ算法可以作为ＴＳＰＮ近似算法中的一个基本 步骤来使用。根据ＴＳＰ算法使用的先后，ＴＳＰＮ 近似算法能够被分成２类：ＴＳＰ后置算法和ＴＳＰ 前置算法。 ＴＳＰ后置算法首先在每个邻近区域中选择合适 的顶点，然后对这些顶点利用已知的ＴＳＰ近似算法 构建最短路径。Ｄｕｍｉｔｒｅｓｃｕ和Ｍｉｔｃｈｅｌｌ［７１考虑了重 叠等大小圆盘区域的情况，提出了一种近似比不超 过ｌ１．５的算法。该算法首先找出所有圆盘区域的最 大独立集，再对该最大独立集中的圆心求ＴＳＰ路 第ｌＯ期 袁远等：高效的移动ｓｉｎｋ路由问题的启发式算法 径。最终路径由该ＴＳＰ路径加上独立集中的每个圆 盘区域边缘构成。他们在同一文章中还利用 ｍ．ｇｕｉｌｌｏｔｉｎｅ分割法，提出了一种解决不重叠且等大 小圆盘区域的算法，其近似比不超过３．５。 Ｅｌｂａｓｓｉｏｎｉ【９】等设计了一种算法来迭代地选择不重 叠的胖区域中的合适顶点，即每轮从邻近区域中找 出一个点，保证该点到前面各轮已选取的顶点距离 之和最小，该算法的近似比为９．１ａ＋ｌ（ａ是胖系数， 当邻近区域是圆盘时，有。ｃ＝４）。他们在文中还提 出了一种针对等大小重叠圆盘区域的常数近似比 算法，即先找出一个面积最小方框，并保证每个圆 盘区域中至少有一个点被该方框覆盖，然后再从方 框中找出最少数量的顶点，并构建ＴＳＰ路径。该算 法近似比为ａ 。目前，针对大小各异不重叠胖区域 的近似算法中，近似程度最好为Ｍｉｔｃｈｅｌｌ［ｍ］给出的 ＰＴＡＳ算法。Ｃｈａｎ和Ｅｌｂａｓｓｉｏｎｉ［ＨＩ则将该算法扩展 到了高维空间。最近，Ｍｉｔｃｈｅｌｌ［１２］又从瘦区域出发， 对于不重叠、大小各异、并且任意形状的邻近区域 给出了常数近似比算法。由于ＴＳＰ后置算法在选择 邻近区域合适：顷点时很难评价每次选择对最终路 径的贡献程度，因此近似比较好的算法多数集中在 区域不重叠的特殊情况；对于邻近区域可重叠的情 况，其效果一般不够理想。 ＴＳＰ前置算法与后置算法恰好相反，它先利用 邻近区域中的特殊点，如几何中心，构建一条ＴＳＰ 路径，再对该路径进行优化。Ｙｕａｎ［４］等研究了移动 ｓｉｎｋ路由问题中无线通信范围为大小各异但不重叠 的圆盘区域的情况。他们先以所有的圆心为顶点构 建一条ＴＳＰ路径，然后按照该路径中的顶点访问顺 序来搜索圆盘上的最优替代顶点。虽然该方法能取 得较好的效果，但是其搜索的时问复杂度太大。 Ｓｕｇｉｈａｒａ［１３］等的工作针对了移动ｓｉｎｋ的数据收集过 程中无线通信范围为等大小但重叠的圆盘区域的 情况，并将其转化成“标签覆盖”问题，同样利用 基于圆心构建出的ＴＳＰ路径的顶点访问顺序，采取 动态规划方法来找出圆心连线之间存在的捷径。虽 然时间复杂度为Ｏ（ｎ ），但是该算法考虑的是圆心 之间是否存在能够访问其他圆盘的捷径，因此解的 效果还有提升的空间。 本文设计的ＲａｃｅＴｒａｃｋ算法属于ＴＳＰ前置算法，它 利用ＴＳＰ路径本身的几何特性在Ｏ（ｎ２）时间复杂度下解 决了大小各异又可重叠的圆盘邻近区域的移动ｓｉｎｋ路 由问题，并且契殓结果说明效果要优于同类算法。 ３问题描述 设ｄｉｓｔ（ｐ，ｇ）表示点Ｐ到点留之间的距离；ｄｉｓｔ（ｐ， 表示点Ｐ到点集ｘ之间的距离，即有ｄｉｓｔ（ｐ， ＝ ｍｉｎ ｘ ｄｉｓｔ（ｐ，ｑ）；Ｔｖ标识一条路径，顶点顺序用有 序集合＜ｖｌ’ｖ２…．Ｖｎ＞表示；ＩＴｖＩ表示路径 的长度。 则移动ｓｉｎｋ路由问题可描述如下。 定义１移动ｓｉｎｋ路由问题。 已知：在一个面积为ＲｘＲ方形监控区域内，随 机部署有ｎ个传感器节点，传感器节点ｉ通信范围 用圆盘区域Ｄｉ（ ｆ，ｒ／）（１≤ｉ≤，ｚ）来标识，其中Ｕｆ表 示圆心，即节点所在位置； 表示圆盘半径，即节 点的无线通信半径。移动ｓｉｎｋ的起始位置固定在监 控区域内一点Ｓ。 目标：找出一条最短的路径瓦。 ，从起始点Ｓ 开始最终回到点Ｓ，并保证进入每个传感器的通信 范围至少一次，即对于任意ｉ（１≤ｉ≤，ｚ），有ｄｉｓｔ（ｕｆ， ）≤ｎ。