优化网络生命周期和最短化路径的WSN移动sink路径规划算法

莫文杰，郑 霖

(1.广西无线宽带通信与信号处理重点实验室(桂林电子科技大学)，广西 桂林 541004；2.桂林电子科技大学 信息与通信学院，广西 桂林 541004)

(*通信作者电子邮箱gwzheng@gmail.com)

优化网络生命周期和最短化路径的WSN移动sink路径规划算法

莫文杰1,2，郑 霖1,2*

(1.广西无线宽带通信与信号处理重点实验室(桂林电子科技大学)，广西 桂林 541004；2.桂林电子科技大学 信息与通信学院，广西 桂林 541004)

(*通信作者电子邮箱gwzheng@gmail.com)

为了缓解无线传感器网络(WSN)中传感器节点分布不均匀、传感器节点感知数据量不同而造成能耗不均衡、“热区”等问题，提出一种优化网络生命周期和最短化路径的WSN移动sink路径规划算法(MSPPA)。首先，通过监测区域网格化，在每个网格内分布若干个移动sink候选访问站点，sink在每个网格中选择一个站点停留收集网格中节点数据；然后，分析所有传感器节点的生命周期与sink站点选择的关系，建立权衡网络生命周期和sink移动路径的优化模型；最后，使用双链遗传算法规划移动sink遍历网格的顺序和选择每个网格中移动sink访问站点，得到移动sink节点遍历所有网格收集数据的路径。仿真结果显示，与已有的低功耗自适应分簇(LEACH)算法与基于移动sink节点与集合节点(RN)的优化LEACH分簇算法(MS-LEACH-RN)相比，MSPPA在网络生命周期方面提高了60%，且具有良好的能耗均衡性。实验结果表明，MSPPA能有效缓解能量不均衡、“热区”问题，延长网络生命周期。

无线传感器网络；移动sink；数据收集；双链遗传算法；路径规划；网络生命周期

0 引言

当前，基于移动sink节点的数据收集优化是无线传感器网络(Wireless Sensor Network, WSN)研究的关键问题之一[1]。WSN引入移动sink节点不仅可均衡节点流量负载，还可以平衡节点能量消耗，从而可以有效避免“热区”问题并延长网络的生存时间[2-3]。但是使用移动sink节点收集数据也带来了新的挑战：一是sink位置更新问题，频繁泛洪sink位置信息将过多消耗节点能量；二是由于sink移动，网络拓扑频繁改变，这会加剧网络拓扑构建的开销[4-5]。因此，优化基于移动sink节点的路由协议以及规划移动sink轨迹的算法受到学术和应用领域的广泛关注。根据sink移动模型，Gu等[6]将基于移动sink的路由协议分成四类：不可控移动模型、路径限制移动模型、站点限制移动模型和不限制移动模型。基于上述四种sink移动模型，下面分别介绍国内外研究者提出的有关基于移动sink的路由协议。

不可控移动模型是指sink节点安装在移动单元上(如动物)，故其位置、速度和轨迹都未知。基于此模型，Lin等[7]提出了基于分簇的分层数据传输(Hierarchical Cluster-based Data Dissemination, HCDD)协议，使用K-means算法将网络划分成簇，簇头处于较高层，负责收集簇内传感器节点数据和转发数据。当sink驻留在其中一个簇时，该簇的簇头通知其他簇头sink的位置，各个簇头以其他簇头为中继节点多跳将数据传输到sink节点。Hamida 等[8]提出了基于虚拟线的数据传输(Line-Based Data Dissemination, LBDD)协议，该协议在网络中央构建一条宽度为w的虚拟线(virtual line)，虚拟线内的传感器节点负责收集和缓存虚拟线外节点的数据，并将sink感兴趣的数据以多跳方式传输给随机游走的sink节点。文献[7-8]采用了sink节点不可控移动模型，能很好地解决随机移动sink位置更新问题，但是无论是HCDD协议的簇头，还是LBDD协议的虚拟线内节点，都存在较高的控制开销与路由开销，其缩短了网络生命周期。

路径限制模型是指sink节点被安置在路径被约束的移动单元上(如公交车)。基于此模型，Mottaghi等[9]结合移动sink节点、低功耗自适应分簇(Low-Energy Adaptive Clustering Hierarchy, LEACH)算法[10]和集合节点(Rendezvous Node，RN)，提出一种基于移动sink节点与集合节点RN的优化LEACH分簇算法(optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes, MS-LEACH-RN)。该协议在网络中央构建一条宽度为w的虚拟线，移动sink在线内作往返直线移动，然后设置一个簇头到sink节点的距离阈值d0，当簇头到sink节点的距离小于d0时，虚拟线外以LEACH协议选取的簇头直接将簇内收集到的数据发送到sink节点，否则，将数据发送到最近的虚拟线内RN，最后RN将数据传输给靠近的移动sink节点。Bhatti等[11]提出一种基于虚拟网格与移动sink节点的动态路由调整方案，该方案将正方形监测区域划分成多个大小一致的网格，sink节点在正方形区域外移动，网格内选取头节点负责收集网格数据，并以其他头节点为中继多跳传输给移动sink节点。该方案以维护sink最新位置的次优路由来达到最小化路由重构开销的目的。梁青等[12]提出基于二分法与移动 sink 的无线传感器网络数据收集协议，该协议将网络分为面积相等的两个子域，子域交线为移动sink的轨迹，随节点死亡率的增加，对子域内部进行二分，确定并改变移动sink的轨迹。移动sink与固定 sink并存，簇头收集簇内兴趣事件并发送至距自己跳数最小的sink。文献[9，11-12]采用了移动sink路径限制模型，都存在关键性节点(如文献[8]的RN与簇头和文献[10]的网格头节点)能耗过大问题，导致其快速死亡。

站点限制移动模型是指移动sink节点只能停留在某些固定位置收集数据。基于此模型，Yun等[13]提出了一种延迟容忍最大化生命周期的单移动sink路由协议。该协议将网络区域分成多个子区域，在每个子区域布置一个固定的sink驻留站点，移动sink遍历所有站点收集数据；然后采用线性规划(Linear Programming, LP)优化移动sink每轮驻留在每个站点的时间，从而最大化网络生命周期。林德钰等[14]提出移动与静态sink相结合的节能策略，该策略使静态 sink节点位于检测区域的中心采用单跳传输方式收集区域中心处节点的数据，移动sink位于距离静态sink节点一定距离处作快速移动，到达固定站点后停留并采集区域外围节点数据。王章权等[15]提出一种移动无线传感网络的sink节点移动路径选择算法，在该算法中，sink节点采用分布式最短路径树算法收集传感节点的相关信息和感知数据，采用虚拟力理论计算所有虚拟力的合力， 根据停留次数、合力大小和方向等信息计算当前网格中心的停留时间和下一个停留网格中心。文献[13-15]采用站点限制移动模型，故其单跳通信传输方式使远离移动sink站点的传感器节点能耗较大，易出现“热区”现象。

不限制移动模型是在不限制sink移动路径与停留站点的情况下规划sink移动路径。基于此模型，Pavithra等[16]基于集合点(Rendezvous Point, RP)提出一种加权集合规划算法，该协议基于源节点到固定sink的数据转发路由，计算每个传感器节点的权重(其转发数据量与其到固定sink的跳数)动态选择节点作为集合点，sink遍历所有集合点收集数据。王薇等[17]提出了一种基于二次栅格划分的可变长编码单亲遗传算法的最佳路径构建方法。该算法首先在网络区域中使用粗粒度栅格进行划分，并利用可变长度编码的单亲遗传算法获得最佳途经栅格，从而构造出初始最佳路径；然后对于每一个途经栅格再次使用细粒度栅格进行划分以优化收集路径。于志博等[18]针对sink移动速度限制从而导致时延较大的问题，提出了时延约束下的移动 sink 路径优化策略，根据时延和网络能耗之间的关系设计了可调节的节点权重，通过模拟退火遗传算法得到最优节点权重，并依据此权重通过迭代得到汇聚节点和最佳移动路径。

许多研究者都考虑到了节点不均匀分布与 “多对一”路由负载不均衡带来的“热区”问题，但大多数移动sink路由协议都没有考虑节点数据分布不均匀问题(节点数据产生速率非恒定)。在WSN现实情况中，节点数据产生速率非恒定也是“热区”问题产生的原因之一。而上述文献中都存在“热区”问题，缩短了网络生命周期。本文根据WSN节点不均匀分布、节点数据分布不均匀以及移动sink收集数据路径长短不同等因素，提出了优化网络生命周期与最短化路径的WSN移动sink路径规划算法MSPPA(Path Planning Algorithm of Mobile Sink)。将网络分成多个网格，在每个网格中分布多个候选站点，根据上述造成“热区”问题的因素，建立权衡网络生命周期和sink移动路径的优化模型。使用双链遗传算法对该优化模型进行求解，得到移动sink节点遍历所有网格收集数据最优路径。该算法均衡了全网数据收集的能耗开销，显著缓解了网络“热区”问题，延长了网络生命周期。

1 系统模型

1.1 优化目标与模型假设

针对sink节点移动轨迹可控的无线传感器网络，本文提出的MSPPA综合考虑了网络生命周期和sink节点移动路径长短两项指标。算法具体包含以下两个优化目标：1)最大化网络的生命周期；2)在目标1)的基础上，使sink移动距离最短化。

在MSPPA中，假设：1)所有传感器节点随机分布在二维的监测区域中，传感器节点位置固定不变，但是sink节点可在监测区域中移动并且停留收集数据；2)所有传感器节点具有相同的性能(如通信半径、初始能量、能耗模型等)，但节点的数据产生速率非恒定，即节点感知数据不均匀；3)所有节点可安装全球定位系统(Global Positioning System, GPS)模块或采用其他定位方法获知自身的位置坐标；4)sink节点能量不受限制，但是每个传感器节点的能量有限且不能补充。

1.2 优化模型

如图1所示，将监测区域分成G个大小一致的网格，网格边长为L(L

图1 网络模型Fig. 1 Network model

本文采用的无线通信能量消耗模型与文献[20-21]相似，由于只考虑传感器节点发送数据到sink节点的单跳路由，故节点i单位时间内发送1 bit数据到sink节点的能耗如下：

(1)

定义节点生命周期Tnet为其能量耗尽所经过的时间，故节点i的生存时间[22-23]为：

(2)

根据上述分析，本文方法的目的是既要最大化网络生命周期，又要最小化sink移动路径长度[24]，故本文提出的优化模型可公式化为：

(3)

(4)

(5)

Ti>0,di→ms≥0;i=1,2,…,n

(6)

2 模型求解

本文问题模型中包含移动sink站点选址问题与移动sink遍历网格问题(即旅行商问题)，但是无论选址问题，还是TSP，都是NP-hard问题，求解存在困难，故采用双链遗传算法对本文模型进行求解。

2.1 染色体编码和解码

移动sink节点在每个网格中选取一个站点停留收集该网格中的传感器节点数据，并以此遍历所有网格，采用双链遗传算法对此问题进行编码。在此双链染色体编码中，一条基因链包含sink遍历所有网格的顺序，如{3,1,6,4,5,2}，另一条是使用0-1编码方式标记sink节点在网格中选取的站点，如{010,100,010,001,001,100}，则染色体和子链之间的关系[25]如图2所示。这两条子链组合成染色体，染色体的每一个基因由一个网格和其内站点组合而成，代表移动sink节点从网格中选取其中一个站点停留收集数据。子链一可得到移动sink节点遍历所有网格的顺序，子链二可得到子链一对应网格中sink选取的停留站点，这样，通过对每个基因进行相应的解码，就可以得到移动sink节点遍历网格收集数据的最优路径。

图2 子链、染色体关系Fig. 2 Relationship between sub-chain and chromosome

2.2 双链遗传算法求解过程

如图3所示，双链遗传算法求解优化模型(3)～(6)，迭代执行染色体评估、选择、交叉、变异等步骤[24]，最终获得优化网络生命周期的sink移动路径选择方案。

图3 MSPPA流程Fig. 3 Flow chart of MAPPA

令C表示染色体数量，c表示染色体操作数，α1表示交叉概率，α2表示变异概率，g表示迭代次数。根据优化模型，双链遗传算法的适应度函数为：

(7)

根据适应度函数，采用以下步骤求解优化模型。

步骤1 初始化。初始化C个双链染色体，迭代次数g=0，染色体操作数c=0，算法中α1、α2等参数。

步骤2 染色体评估。计算所有染色体的适应度，直接选择适应度最大的染色体继承到下一代种群中。

步骤3 选择。根据轮盘赌策略选择需要交叉的2个染色体。

步骤4 交叉。产生一个0～1的随机数，如果其大于α1，对已选择的2个染色体进行交叉操作。交叉操作采用部分匹配交叉法，先随机产生两个交叉点，定义这两点的区域为匹配区域，并交换两个父代的匹配区域，如图4所示。

对TEMP A、TEMP B中匹配区域以外出现的数码重复，要依据匹配区域内的位置逐一进行替代，匹配关系为{6↔1, 4↔5}，产生子代A、子代B，如图5所示。

步骤5 变异。产生一个0～1的随机数，如果其大于α2，对已交叉的2个染色体进行变异操作。随机产生两个变异位，交换染色体两个变异位的基因，再对子链二(sink站点链)的变异位相应的值进行位变异，如图6所示。

图4 父代匹配区域交换Fig. 4 Exchange of parental matching regions

图5 匹配关系替代图Fig. 5 Substitution map of matching relationship

图6 变异操作Fig. 6 Mutation operation

步骤6 返回或结束。c=c+1，如果c

3 仿真实现和分析

3.1 仿真参数设置

为了方便比较算法性能，网络生命周期与LEACH协议[10]相似，使用移动sink数据采集轮数计量。如表1所示，选择表中参数，在Matlab软件上编程实现MSPPA、 MS-LEACH-RN和LEACH算法。LEACH算法是典型的分簇数据收集协议，而MS-LEACH-RN[9]是基于移动sink节点与集合节点RN的优化LEACH分簇算法。将100个传感器节点随机分布在120 m×160 m的监测区域，通信半径60 m，节点感知数据量变化范围为0～8 000 bit，节点的初始能量为0.2 J。最后将监测区域划分成12个均等的网格，每个网格中以网格中心点、网格中节点分布密度重心和网格中数据分布质心为sink站点，仿真分析MSPPA的收敛性，并比较MSPPA、MS-LEACH-RN和LEACH算法。

表1 仿真参数Tab. 1 Simulation parameters

3.2 MSPPA收敛性仿真分析

为了验证MSPPA的收敛性，对MSPPA的最大适应度值和平均适应度值进行仿真计算，其收敛速度、寻优结果如图7所示。从图中最优解和平均解的对比，可知MSPPA具有较好的收敛性。

图7 MSPPA收敛性Fig. 7 Convergence of MSPPA

3.3 算法仿真结果分析

3.3.1 网络生命周期性能分析

为了比较MSPPA和MS-LEACH-RN、LEACH算法的网络生命周期性能，在仿真区域内随机分布50、100、150、200、250、300个传感器节点，并假设网络生命周期为网络中第一个节点死亡对应的轮数。如图8所示，MSPPA的网络生命周期是MS-LEACH-RN的1～2倍，是LEACH算法的8倍，可见MSPPA能延长网络生存时间。

3.3.2 存活节点数量性能分析

图9对比了上述三种算法的网络中存活节点数量随着仿真轮数的变化情况。LEACH协议中sink节点固定，簇头的负载过大，故在400轮时节点全部死亡；MS-LEACH-RN协议中sink移动轨迹固定在网络额度中线，在sink移动轨迹附近存在集合节点(RN)，RN虽然减小了一部分簇头节点能耗，但是远离sink移动轨迹的簇头能耗没有降低多少，故此类簇头节点过早死亡，网络寿命较短；MSPPA在800～950轮死亡的传感器节点骤然增加，可见其网络能量较为均衡，所以MSPPA在延长网络生命周期方面优于其他两个算法。

图8 网络生命周期Fig. 8 Network lifetime

图9 节点存活数量Fig. 9 Number of surviving nodes

3.3.3 节点剩余能量标准差分析

无线传感器网络中，全网所有节点所有能量的标准差是评价能量均衡路由协议的一个非常明了的指标。标准差反映了各节点剩余能量的分布状况，如果网内所有节点的能量水平相当，即它们之间的能量差异很小，则节点剩余能量的标准差较小；若标准差的值较大，则表示网络内各节点的能量情况差异较大，有些节点有充足的能量，而有些节点则因为能耗过快而过早死亡，缩短了网络寿命。因此，节点剩余能量的标准差(Standard Deviation)越小，网络中能量的分布越均匀，说明能量均衡路由协议的性能也越好。节点剩余能量的标准差σE的计算公式[26]如下：

(8)

如图10所示，在仿真150轮时，LEACH、MS-LEACH-RN和MSPPA传感器节点剩余能量标准差的斜率分别约为0.08/150，0.35/150和0.01/150，故MSPPA节点剩余能量标准差的斜率要远小于LEACH与MS-LEACH-RN，所以MSPPA在能量均衡方面优于其他两个算法。

3.3.4 “热区”情况分析

图11为MSPPA与LEACH和MS-LEACH-RN在仿真300轮时的节点能量消耗图，该图描绘了网络中所有传感器节点的能耗分布。尽管LEACH算法采用自适应簇头选取机制(选择剩余能量大的节点充当簇头)，稍微均衡了网络能耗，但是由于其簇内采用“多对一”通信，簇内所有数据都通过簇头传输到sink节点，导致簇头负载较大，如图11(a)所示，许多节点已耗尽0.2 J能量，“热区”效应严重。MS-LEACH-RN集合了移动sink节点、LEACH分簇算法、集合节点的优点，大大缩短了簇头节点到sink节点的通信距离，降低了簇头的能耗，但是网络边界的簇头由于距离移动sink轨迹较远，故其传输数据能耗较大，所以网络边界易出现“热区”，如图11(b)所示，网络边界节点能耗已达到0.1～0.14 J，出现“热区”效应。而MSPPA根据网络寿命动态选取每个网络中移动sink停留站点，故传感器节点与sink节点的通信距离不固定，能更好地均衡网络能耗，缓解“热区”效应，如图11(c)所示，网络还没出现“热区”现象，故可得出MSPPA在缓解“热区”问题上优于另外两个算法。

图10 节点剩余能量标准差Fig. 10 Residual energy standard deviation of nodes

图11 “热区”情况对比Fig. 11 Hotspot situation comparison

4 结语

本文针对节点分布不均匀、节点感知数据非均匀而造成能耗不均衡、“热区”能量空洞问题，设计了面向延长网络寿命和最短路径的WSN移动sink路径规划算法(MSPPA)。该算法将WSN监测区域划分成网格，根据网络实际情况，在每个网格中定义若干个sink候选站点(如网格中心点、网格中节点分布密度重心、网格中数据分布质心等)，使用双链遗传算法规划移动sink遍历网格的顺序和选择每个网格中移动sink访问站点，得到移动sink节点遍历所有网格收集数据的移动路径。该算法在能耗均衡性与缓解“热区”效应等方面，均表现良好，其网络生命周期优于LEACH和MS-LEACH-RN。

References)

[1] XING G, WANG T, XIE Z, et al. Rendezvous planning in wireless sensor networks with mobile elements [J]. IEEE Transactions on Mobile Computing, 2008, 7(12): 1430-1443.

[2] CHATZIGIANNAKIS I, KINALIS A, NIKOLETSEAS S. Efficient data propagation strategies in wireless sensor networks using a single mobile sink [J]. Computer Communications, 2008, 31(5): 896-914.

[3] KHAN A W, ABDULLAH A H, ANISI M H, et al. A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks [J]. Sensors, 2014, 14(2): 2510-2548.

[4] SUN W, YANG Z, ZHANG X, et al. Energy-efficient neighbor discovery in mobile Ad Hoc and wireless sensor networks: a survey [J]. IEEE Communications Surveys & Tutorials, 2014, 16(3): 1448-1459.

[5] 张惠麒,林志贵,李敏,等.基于移动sink节点的路由协议的比较与分析[J].计算机科学,2014,41(S1):276-280. (ZHANG H Q, LIN Z G, LI M, et al. Comparison and analysis of routing protocol based on mobile sink [J]. Computer Science, 2014, 41(S1): 276-280.)

[6] GU Y, REN F, JI Y, et al. The evolution of sink mobility management in wireless sensor networks: a survey [J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 507-524.

[7] LIN C-J, CHOU P-L, CHOU C-F. HCDD: hierarchical cluster-based data dissemination in wireless sensor networks with mobile sink [C]// IWCMC ’06: Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing. New York: ACM, 2006: 1189-1194.

[8] HAMIDA E B, CHELIUS G. A line-based data dissemination protocol for wireless sensor networks with mobile sink [C]// ICC ’08: Proceedings of the 2008 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2008: 2201-2205.

[9] MOTTAGHI S, ZAHABI M R. Optimizing LEACH clustering algorithm with mobile sink and rendezvous nodes [J]. AEU — International Journal of Electronics and Communications, 2015, 69(2): 507-514.

[10] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocols for wireless microsensor networks [C]// HICSS ’00: Proceedings of the 33rd Hawaii International Conference on Systems Sciences. Washington, DC: IEEE Computer Society, 2000, 8: 8020.

[11] BHATTI R, KAUR G. Virtual grid based energy efficient mobile sink routing algorithm for WSN [C]// Proceedings of the 11th International Conference on Intelligent Systems and Control. Piscataway, NJ: IEEE, 2017:30-33.

[12] 梁青,焦峰.WSN中基于二分法与移动Sink的数据收集协议[J].计算机工程,2016,42(12):39-43. (LIANG Q, JIAO F. Data collection protocol for WSN based on dichotomy and mobile sink [J]. Computer Engineering, 2016, 42(12): 39-43.)

[13] YUN Y, XIA Y. Maximizing the lifetime of wireless sensor networks with mobile sink in delay-tolerant applications [J]. IEEE Transactions on Mobile Computing, 2010, 9(9): 1308-1318.

[14] 林德钰,王泉,刘伎昭.无线传感网的移动与静态sink相结合的节能策略[J].哈尔滨工业大学学报,2016,48(11):162-168. (LIN D Y, WANG Q, LIU J Z. Energy-saving strategy by combining mobile and static sink schemes for wireless sensor networks [J]. Journal of Harbin Institute of Technology, 2016, 48(11): 162-168.)

[15] 王章权,陈友荣,任条娟,等.数据传输时延和跳数受限的Sink节点移动路径选择算法[J]. 传感技术学报,2016,29(4):583-592. (WANG Z Q, CHEN Y R, REN T J, et al. Sink node moving path selection algorithm limited by data transmission delay and hops [J]. Chinese Journal of Sensor and Actuators, 2016, 29(4): 583-592.)

[16] PAVITHRA H, SHIVASHANKAR, POORNIMA G R. An efficient mobile sink path selection approach for WSN’s [C]// Proceedings of the 2016 IEEE International Conference on Recent Trends in Electronics Information Communication Technology. Piscataway, NJ: IEEE, 2016: 151-155.

[17] 王薇,史浩山,黄鹏宇,等.基于二次栅格划分的移动sink最小路径构建算法[J].西北工业大学学报,2016,34(6):1016-1021. (WANG W, SHI H S, HUANG P Y, et al. A constructing mobile path minimal path algorithm based on quadratic grid [J]. Journal of Northwestern Polytechnical University, 2016, 34(6): 1016-1021.)

[18] 于志博,孔祥雪,裴金金.移动Sink的传感器网络路径优化策略[J].传感器与微系统,2016,35(11):44-46. (YU Z B, KONG X X, PEI J J. Mobile sink-based path optimization strategy in wireless sensor networks [J]. Transducer and Microsystem Technologies, 2016, 35(11): 44-46.)

[19] 陶志勇,蒋守凤.基于簇首移动的无线传感器网络路由算法[J].计算机工程与应用,2016,52(5):75-78. (TAO Z Y, JIANG S F. Clustering algorithm for wireless sensor networks with mobile cluster heads [J]. Computer Engineering and Applications, 2016, 52(5): 75-78.)

[20] SHI Y, HOU Y T. Theoretical results on base station movement problem for sensor network [C]// INFOCOM 2008: Proceedings of the 27th Conference on Computer Communications. Piscataway, NJ: IEEE, 2008:1-5.

[21] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks [J]. IEEE Transactions on Wireless Communications, 2000, 1(4): 660-670.

[22] TASHTARIAN F, MOGHADDAM M H Y, SOHRABY K, et al. ODT: optimal deadline-based trajectory for mobile sinks in WSN: a decision tree and dynamic programming approach [J]. Computer Networks, 2015, 77: 128-143.

[23] TASHTARIAN F, HOSSEIN Y M M, SOHRABY K, et al. On maximizing the lifetime of wireless sensor networks in event-driven applications with mobile sinks [J]. IEEE Transactions on Vehicular Technology, 2015, 64(7): 3177-3189.

[24] 王章权,陈友荣,尉理哲,等.优化网络生存时间的Sink节点移动路径选择算法[J]. 传感技术学报,2014,27(3):409-415. (WANG Z Q, CHEN Y R, YU L Z, et al. Mobile path selection algorithm of sink node for optimizing network lifetime [J]. Chinese Journal of Sensor and Actuators, 2014, 27(3): 409-415.)

[25] 曾又姣,金烨.基于遗传算法的贴片机贴装顺序优化[J].计算机集成制造系统,2004,10(2):205-208. (ZENG Y J, JIN Y. Optimization of placement order of placement machine based on genetic algorithm [J]. Computer Integrated Manufacturing Systems, 2004, 10(2):205-208.)

[26] ZENG K, REN K, LOU W, et al. Energy aware efficient geographic routing in lossy wireless sensor networks with environmental energy supply [J]. Wireless Networks, 2009, 15(1): 39-51.

This work is partially supported by the National Natural Science Foundation of China (61371107), the Foundation of Guangxi Key Laboratory of Wireless Wideband Communication and Signal Processing (GXKL061501).

MOWenjie, born in 1990, M. S. candidate. His research interests include wireless sensor network, routing protocol.

ZHENGLin, born in 1973, Ph. D., professor. His research interests include wireless UWB communication, wireless sensor network, mobile communication, adaptive signal processing, spread spectrum communication, packet wireless network.

Pathplanningalgorithmformobilesinkwithoptimizednetworklifetimeandshortestpathinwirelesssensornetwork

MO Wenjie1,2, ZHENG Lin1,2*

(1.GuangxiKeyLaboratoryofWirelessWidebandCommunicationandSignalProcessing(GuilinUniversityofElectronicTechnology),
GuilinGuangxi541004,China；2.SchoolofInformationandCommunication,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)

In order to alleviate the problem of the imbalance energy consumption and hotspot due to the uneven distribution of nodes and the different amount of perception data in the Wireless Sensor Network (WSN), a Path Planning Algorithm of Mobile Sink named MSPPA was proposed to optimize network lifetime and shortest path in WSN. Firstly, by defining the grids in the network area, several candidate sites of mobile sink were distributed in each grid, and then sink node selected a site for sojourning and collecting data of nodes in each grid. Secondly, based on the relationship between network lifetime and the selection of sink sites, an optimization model was established to weigh network lifetime and mobile journey of sink. Finally, the double-stranded genetic algorithm was proposed to plan the order of mobile sink traversing grids and selecting site of the mobile sink in each grid, then the optimal path of mobile sink was obtained. The simulation results show that, compared with Low-Energy Adaptive Clustering Hierarchy (LEACH) algorithm and optimizing LEACH clustering algorithm with Mobile Sink and Rendezvous Nodes (MS-LEACH-RN), the network lifetime of MSPPA was increased by 60%. The proposed MSPPA has a good balance of energy consumption as well. The experimental results indicate that the proposed MSPPA can effectively alleviate the imbalance of energy consumption and the hotspot problems, prolonging the network lifetime.

Wireless Sensor Network (WSN); mobile sink; data collection; double-stranded genetic algorithm; path planning; network lifetime

TN926

A

2017- 02- 08;

2017- 02- 26。

国家自然科学基金资助项目(61371107)；广西无线宽带通信与信号处理重点实验室基金资助项目(GXKL061501)。

莫文杰(1990—)，男，广西柳州人，硕士研究生，主要研究方向：无线传感器网络、路由协议； 郑霖(1973—)，男，广西桂林人，教授，博士，主要研究方向：无线超宽带通信、无线传感器网络、移动通信、自适应信号处理、扩频通信、分组无线网络。

1001- 9081(2017)08- 2150- 07

10.11772/j.issn.1001- 9081.2017.08.2150