基于二次栅格划分的移动sink最小路径构建算法
A Routing Planning Algorithm base on Twice Grid Division for Mobile Sink

在无线传感器网络中引入移动sink能够有效解决能量空洞问题，从而提高无线传感器网络的生存时间。但是移动sink的移动速度限制通常会影响数据收集的时延特性，文章的研究重点即如何为移动sink构建最佳巡航路径，从而减小信息收集时延。充分利用传感器节点的通信范围，将构建最佳路径问题转化为求解带邻域的旅行商问题TSPN（traveling salesman problem with neighborhoods），并提出了一种基于二次栅格划分的可变长编码单亲遗传算法的最佳路径构建方法。该算法首先在网络区域中使用粗粒度栅格进行划分，并利用可变长度编码的单亲遗传算法获得最佳途经栅格，从而构造出初始最佳路径。然后对于每一个途经栅格再次使用细粒度栅格进行划分以优化收集路径。仿真结果表明，新算法能够获得更短的数据收集路径，大幅度减低了网络信息收集时延，有效地拓展了网络的生存时间。
Introduce mobile sinks into wireless sensor networks can balance the energy level of the sensor nodes, resolve the hotspot problem and prolong the lifetime of the whole network. However, the mobility of the sink may also introduce additional delays. Therefore, it is important to design an efficient routing protocol for the mobile sink. In this paper, we deduce this routing planning problem into a Traveling Salesman Problem with Neighborhoods (TSPN). In addition, we propose a routing design algorithm base on twice grid division and variable-length Partheno-genetic Algorithm. In this algorithm, we divide the network area with the grids coarse-grained, and obtain the grids on the best path with variable-length Partheno-genetic Algorithm. We then divide every grid on the path with the grids fine-grained in order to optimize the path. Finally, we implement this algorithm in Matlab and the simulation results show that the proposed algorithm can significantly improves the efficiency and effectiveness of the routing planning for the mobile sink