,, ,

(1.湖北大学 计算机与信息工程学院，武汉 430062； 2.北京理工大学 信息与电子学院，北京 100081)

0 引言

无线传感器网络[1]由大量随机部署在空间中的传感器节点组成，主要广泛的应用在工程领域[2]中，如：海洋环境探测、森林火灾监控、空气污染监控等。由于节点的能量和通信范围有限，所以引入移动Sink[3]对簇头数据进行收集[4]，减少簇内的通信成本，从而延长了无线传感器网络的使用生存周期[5]。LEACH[6]是流行的分层路由协议之一，该协议主要以形成集群和选择簇头来减少簇内节点的能量消耗。路由协议设计的宗旨是最大限度地降低能耗和延长使用寿命[7]。在实际设计中，传统LEACH协议是簇头收集的数据融合直接发送给基站，而修改后的LEACH协议是簇头将收集的数据发送给MS，MS运行一个周期将所有的数据发送给基站。

Mottaghi等[8]提出了基于sink节点与集合节点优化的LEACH算法，该算法建立一条宽为ω的虚拟路径，sink节点只能在此区域来回移动，然而只有部分簇头与sink通信的距离减少，并没有解决所有的簇头与sink的通信距离。林志贵等[9]在WSN中结合sink节点延长无线传感器网络的生命周期，提出了移动中继的WSN节能移动路由算法，可以避免因局部突发事件造成网络过早失效；该算法在网络运行中普通节点需要判断是否将数据直接传给sink还是发送给簇头，节点需要与簇头和sink多次通信，才能将数据传送出去。刘林锋等[11]在改进传统的LEACH协议算法中引入sink收集数据，采用蚁群算法搜寻移动sink的最优路径。但是蚁群算法在路径规划时容易陷入局部最优，导致路径规划并不是最优路径。卢先领[12]等提出了时延受限的移动sink数据收集算法，该算法通过时延限制了sink的移动速度和移动轨迹，该算法固定了MS的运动轨迹，但未固定簇头，当簇头被重新选取，MS收集数据的路径并不是最优。

上述文献都考虑了簇头将数据发送给MS，然而并没有真正解决簇头与MS通信成本达到最小，本文提出了基于LEACH算法引入MS收集簇的数据，并与蚁群遗传算法(ACGA)相结合获得MS移动最短路径并与簇头近距离通信，以解决簇头能量消耗过快、数据传输比率低、网络生命周期短的问题，通过实验数据分析WSNs能量利用率提高了50%、数据传输比率提高到24.5%、网络生命周期提高了60%。

1 无线传感器网络数据模型

1.1 LEACH算法分析

LEACH[6]算法以循环随机的方式选取簇头节点并采用单跳路由的方式通信，如果某个节点的随机数小于阈值,则该节点成为簇头。[6]的计算公式如下为：

(1)

p是网络中簇头所占的百分比，r为当所运行的选举轮数；G是最近1/p轮不是簇头的节点集。

节点的通信过程如图1所示。

图1 簇头与节点间的通信

节点收发送数据的能耗[11 ]模型如下：

ETX=mEelec+mεdχ

(2)

簇头接收簇内节点数据时能量消耗如下：

ERX=wmEelec

(3)

簇头一个周期内消耗的能耗为：

Qk(t)=wEDA(t)+wERX(t)

(4)

1.2 WSN中MS的访问路径规划模型

在呈现路径规划之前，我们应该考虑WSN模型；在一个恶劣的环境中随机部署N个初始能量为的节点，并且部署之后静止不动(MS不用考虑)。同时，MS通过广播告知每一个节点，通过每一个节点返回的消息，MS确定每一个簇头的位置并路径规划，可以确定最佳的移动路径。在此采集信息过程中，当存活节点的个数低于总数的15%，则宣布WSNs生命周期结束。

为了尽可能的使WSNs生命周期变长，MS的速度和路径对网络生命周期有很大的影响。当确定了最佳路径后，MS将以最佳的速度去接收每一个簇头的数据。假设在一片区域内随机部署了N=30个节点如图2所示，从形成簇的结构来看，可以将其分成为6个相等的区域，每一个单独区域就是一个簇，通过随机部署每一个簇的普通节点数都不一样，在此通过LEACH协议选取的簇头，簇头将传送自己的信息可以确定每一个簇头的位置，从而可以确定最佳的移动路径，达到最小的能量消耗。

图2 sink移动轨迹

在此场景中，将呈现出最佳的路径算法和花费最短的时间收集数据，引入最短时间周期进行如下证明：

(5)

为了有效的收集数据，当普通节点收集到的数据采用TDMA传送到簇头，为了防止簇头收集到的数据溢出而导致数据丢失，应及时将数据传送给MS，每一个周期ξ由每一个簇头传送数据的时间和移动sink移动σ决定的。则如下为：

(6)

如果簇内有w个普通节点，每一个普通节点传输m bit消息。传输的信息的速率为R，则移动sink收集簇头内的信息所需要的时间如下为：

(7)

当确定最佳路径之后，MS以为最佳路径运行，此时，MS的速度为v，则移动的时间如下为：

(8)

每一次收集数据的一个周期为是由MS移动的路径和采集簇头数据的时间决定。

2 基于蚁群遗传算法的路径规划

2.1 蚁群算法的改进

蚁群算法[12]与其他优化算法都有自己的局限性，容易陷入到局部的最优解，通过引入遗传算法[13]的选择、变异和交叉算子，改变蚁群算法易陷入局部解后不再更新路径，并增加了算法的多样性，避免了算法过早结束而未达到最优解。所谓的交叉算子是根据生物学中的两个父代个体的部分染色体交叉互换产生新的染色体传递给下一代，并通过交叉分析产生新的有益基因。

蚁群算法中的每一只蚂蚁个体都具有良好的粒子性，将其转化为粒子群算法的思维：所有的粒子都由一个优化的函数来决定适应函数值。而每一个粒子的速度可以改变粒子的方向和决定他们行驶的距离，此时粒子将会在空间内搜寻最优解，通过每一次的迭代，粒子通过跟踪两个极值用来更新自己的位置，两个极值分别是个体极值pbest,另外一个是整个种群的最优极值gbest。按照遗传算法的交叉变异操作如下：

vk+1=c0vk+c1r1(pbestk-xk)+

c2r2(gbestk-xk)

(9)

式中，c0vk项可以作为遗传算法的变异操作，c1r1(pbestk-xk)项转化为遗传的交叉操作，c2r2(gbestk-xk)项转化为遗传的选择操作；每一次的都可以让蚂蚁的当前解与个体最优解和全局最优解进行交叉运算，同时解出新的最优解，最后通过新的最优解计算出最短距离。

2.2 蚁群遗传算法实现

当簇头选取之后，确定簇头的位置，并寻找最佳路径收集数据，假设MS是一只蚂蚁，从而选取一个簇头的位置进行开始，通过蚁群算法的“随机比例规则”选择下一个簇头。则MS转移概率Pij(t)为：

(10)

通过MS在每一条路径上留下的信息素浓度，由信息素浓度的强度选择下一个簇头，此时可以在求解最短路径时产生m个初始解。设其中经过的路径(i,j)的初始解有s个，每一个路径长度为L1,L2,...LK然而路径上的初始信息量如下为：

(11)

当每一个MS走完一步或者完成一次循环，要对残留的信息进行更新处理，每次迭代完成后，各路径上的信息素都需要更新，其公式如下:

(12)

m只蚂蚁获得的所有路径中当前路径的长度已经小于上一次迭代路径长度的最短距离时，则终止本次寻找最短路径，此时所获得的路径为最短路径。

3 仿真实验分析

通过Matlab对LEACH协议中加入MS，与原有的LEACH协议对比能量消耗、数据传输和网络寿命等；改变原有固定不变的基站，从而使用MS收集数据传给基站和采用的ACGA算法对MS的路径进行规划。簇头的能量消耗减少以至于增加WSNs网络生命周期。将300个节点随机部署在400 m*400 m的正方形内，BS的坐标为(0,0)。主要分析WSNs能量消耗、网络寿命和数据传输。WSNs主要参数如表1所示：

表1 网络仿真参数

通过实验对比分析，与没有MS进行转接数据相比，提高了无线传感器的数据传输，并增加了簇头的选取。从而增加的WSNs生命周期和能量利用率。图3展现了使用MS加大了数据的传输量，当传输率增加时，节点传输完数据后提前进入休眠状态并减小能量的损耗；图4对比原有的LEACH协议生命周期，LEACH协议80%的节点死亡接近1 500轮，而本文采用的算法80%的节点死亡接近3 700轮，通过实验对比，整个网络周期平均提高了60%。图5显示了加入MS之后提升了数据传输率的同时网络能量消耗减小，最终能量利用率也提高；从图6看出LEACH算法工作轮数在1 600所有的节点死亡，加入MS之后工作轮数在3 800所有的节点死亡。总体来看根据引入MS提高了节点能量的利用率和延长的网络生命周期。

图3 数据传输对比 图4 死亡节点数对比

图5 网络能量消耗对比 图6 剩余能量对比

在仿真中，采用路径规划分析MS移动的是否路径最短。通过实验比较三种算法进行最佳的移动轨迹；为了证明MS轨迹，将采用了100/150/200/250/300个节点部署进行分析，根据协议选取簇头确定路径，并采用蚁群算法、遗传算法、蚁群遗传算法进行分析，由于簇头选取占节点的10%，选取α=1，β=5，信息素增加强度系数Q=100，信息挥发系数ρ=0.95，蚂蚁个数为50，最大运行次数为1 000，并在同一台机器上、各参数设置同等的情况下进行计算比较。图7显示了3个算法进行路径规划时最短距离的比较，从图中可以看出节点数相对较少时路径规划没有明显的优势，当达到较多的节点部署时，则路径规划明显显现出来，并带入公式(8)可以证明MS移动使用的时间最短，然而每一个簇头传送数据采用的TDMA的时间间隔相同,LEACH-sink总收集数据的时间低于原有的算法，则公式(7)被证明，最终可以证明公式(5)在此应用中成立。图8为LEACH协议与引入MS之后同一节点数进行对比，网络寿命比原有的LEACH算法的网络生命增大了很多，可以看出MS在此过程减小了WSNs能量消耗。通过实验对路径综合进行比较，产生最短距离的算法为ACGA算法，可见在蚁群算法中融入遗传算法可以更好的选择路径。同时收集数据时可以减少簇头等待sink时间过长.达到时间最小化。

图7 最短路径对比 图8 网络生命对比

为了证明系统具有良好的稳健性，需要讨论所有节点的覆盖均匀程度，然而簇中的节点数不同会导致不同簇之间数据的容量不同和簇的生存周期，因此簇的负载平衡程度也是衡量整个系统的重要标准之一，负载平衡因子的计算如下：

(13)

由负载平衡因子公式比较改进后的算法负载均衡度明显比原有的好，而且基本处于稳定如图9。再次对系统多次进行实验并分析稳健性，随机提取10次WSN生命周期进行分析如图10，可以看出此数据的平均值为3 355、极差为47、标准方差为14.57，最大的生命周期与最小的生命周期没超过5%，可以推论系统具有良好的稳定性。

图9 负载均衡度 图10 系统的稳健性

4 结论

本文主要针对无线传感器网络延长生命周期进行研究，采

用LEACH分层协议引入MS收集簇头的数据减少簇头通信距离。在MS运动轨迹中提出了ACGA算法，加快了数据的收集和提高了能量利用率。同时本文优化了蚁群算法并结合了蚁群粒子化经过遗传算法产生新的算法，提高了蚁群算法的全局搜索能力，弥补了蚁群算法陷入局部最优化。减少了簇内成员的通信开销，提升了网络的生命周期。本文的不足没考虑MS移动的动态速度。后期将对无线传感器MS移动速度结合数据压缩解决能耗问题，并减少数据传输和提高网络生命周期。

[1] Jennifer Y, Biswanath M, Dipak G.Wirelesssensor network survey[J].Computer Networks,2008,2292-2330.

[2] KuAakowskihg P, Calle E, &Marzo J L. Performance study of wireless sensor and actuatornetworks in forest fire scenarios[J]. International Journal of Communication Systems, 2013,26(4), 515-529.

[3] Hoc Thai Nguyen, Linh Van Nguyen, and HaiXuan Le. Efficient Approach for Maximi-zing Lifespan in Wireless Sensor Networks by Using Mobile Sinks[J]. ETRI Journal,2017.

[4] Ilkyu Ha 1,MamurjonDjuraev, ByoungchulAhn. An Optimal Data Gathering Method for Mobile Sinks in WSNs[J].Wireless PersCommun (2017) 97:1401-1417.

[5] Bhattacharya I,Ghosh S ,Kundu S. Maximizing lifetime of Wireless Sensor Network through extended LEACH Algorithm[M].Advances in Computer Science and Information Technology. Computer Science and Information Technology. 2012：377-386.

[6] 王振兴，熊伟丽，徐保国.基于LEACH的簇树网络路由算法研究[J].计算机测量与控制，2008,16(11)：1735-1737.

[7] Soua R, Minet P. A survey on energy efficient techniques in wireless sensor networks[A]. In:IEEE Conference on Wireless and Mobile Networking[C]. 2011,12:1-9.

[8] 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.

[9] 林志贵，张 炜，孙有为，等．带移动中继的WSN移动路由算法[J] ．西北大学学报(自然科学版)，2015,45(5)：727-732.

[10] 刘林锋,郭 平,赵 娟,等.无线传感器网络中一种基于改进的LEACH协议的数据收集方案[J].计算机科学，2015,42(6A)299-302.

[11] 卢先领，王莹莹．时延受限的移动sink数据收集算法[J]．通信学报,2014，35(10)： 107-116．

[12] TarunpreetBhatia,SimmiKansal, ShivaniGoel , A.K. Verma . A genetic algorithm based distance-aware routing protocol for wireless sensor networks[J]. ComputersandElectricalEngineering,2016:441-445.

[13] Liu J H, Yang J G, Liu H P, et al. improved ant colony algorithm for robot path planning[J].MethodologiesandApplication,2017,21(19):5829-5839.