基于改进蚁群算法的LEACH协议研究

严斌亨，刘 军，刘广斌，何杨炯

(武警工程大学 信息工程系，西安 710086)

基于改进蚁群算法的LEACH协议研究

严斌亨，刘 军，刘广斌，何杨炯

(武警工程大学 信息工程系，西安 710086)

针对LEACH协议在数据传输阶段，簇首与汇聚节点之间采用单跳模式传输数据使得能量消耗快并且不均衡的问题，提出一种基于改进蚁群算法的新型路由协议；该协议利用了能耗因子对蚁群转移概率以及信息素更新进行改进，充分考虑了节点的剩余能量和节点间距离，通过信息素的建立和更新，寻找簇首节点和基站之间的最优传输路径，进行多跳传输模式，从而均衡簇首节点能量消耗；仿真实验结果表明，改进后的ACO-BEC协议较之于LEACH协议，能够有效降低了整个网络能量消耗，延长了网络寿命。

无线传感器网络；LEACH协议；蚁群算法；信息素；能量均衡

0 引言

20世纪五六十年代以来，随着计算机网络技术、无线通信技术、传感器技术和分布式处理技术等高新技术的成熟发展，无线传感器网络[1](WSNs，Wireless Sensor Networks)逐步形成。WSNs是由大量体积小、成本低、电池供电的传感器节点密集分布在一定范围内的自适应系统[2]，这些传感器节点在部署范围内协同进行数据的采集、存储、处理和传输，完成对整个区域的监控。目前广泛应用于军事、工业、农业、医学和抢险救灾等领域[3-4]。

LEACH[5-10]是最早被提出来的经典分簇路由协议，该协议通过随机等概率的方式选举簇首，以此达到均衡网络能量，提高网络寿命的目的，但LEACH协议随机簇首选举方式以及数据的单跳传输模式，使得能量消耗不均，加速个别节点死亡，影响整体网络寿命[6]。因此，针对LEACH协议的缺陷，越来越多的改进协议被提出来，文献[7]考虑节点剩余能量、节点稀疏程度等因素来保证最优簇头，同时将优化过的蚁群算法用于选择最优能量路径完成簇头间信息传输；文献[8]提出的DSCT算法在以改进的LEACH协议对WSN进行分簇的基础上，利用蚁群算法寻找出连接所有簇首的最优路径，使移动sink沿着此路径移动并进行数据收集；文献[9]提出的基于最小生成树的非均匀算法UCRAMST算法利用节点的剩余能量选举簇首，通过建立最优传输路径减少能量消耗。但是以上一些改进方法或在计算转移概率以及更新信息素只考虑能量并未考虑节点及链路的其它状况，或是过于复杂，这将不利于网络节点能量的均衡和节省。因此，本文在LEACH协议的基础上，提出一种基于蚁群算法的改进协议ACO-BEC (balanced energy consumption based on ACO for LEACH)，该协议在数据传输时利用优化后的蚁群算法寻找最优路径，采用多跳模式，在搜寻下一跳时考虑节点的剩余能量，避免节点过早死亡，从而延长网络寿命。

1 LEACH协议分析

经典LEACH协议采用分簇拓扑控制的管理机制，一组节点形成一个簇，簇成员与簇首通信，簇首汇聚并融合采集的数据并转发至汇聚节点，协议引入了‘轮’的概念，每一轮包括两个阶段：簇的建立阶段及数据稳定传输阶段[10]。

簇的建立阶段可细分为两步：第一步是各节点随机等概率竞选簇首；第二步是簇首节点广播消息，非簇首节点选择加入相应的簇。在簇首选举时，各个节点产生一个介于0到1间的随机数，并与确定的阈值T(n)相比较，判定是否担任簇首。阈值T(n)计算公式见式(1)：

(1)

式中,p是节点中簇首的百分数，r是当前选举的轮数，G是之前轮中未当选过簇首的节点集合，rmod(1/p)是该轮循环中已当选过簇头的节点数量。

选举完成后，簇首节点主动广播身份消息，非簇节点根据接收到的广播信号的强度来选择要加入的簇，并向簇首反馈加入信息，各簇内节点采用TDMA方式与簇首通信；簇建立完成后，各成员节点若有数据要发送，就利用各自分配的时间片将数据发送到簇首，当簇首节点接收到所有的数据后，对数据进行融合处理，将有用的数据发送到汇聚节点；持续一段时间之后，整个网络进入下一轮重新进行簇首选举[11]。

研究表明，LEACH协议有效延长了网络的整体寿命，较之前的平面多跳路由协议和静态分簇协议可以将网络的生存周期延长15%左右[5]。然而LEACH协议在数据传输阶段中，簇首节点把收集到的数据传输至汇聚节点时，采用的是单跳通信，而由能耗模型可知，当传输距离过大时，能耗量与距离的四次方成正比，将使节点的能量消耗过大，加速死亡。

2 基于改进蚁群算法的ACO-BEC协议

蚁群算法[12](Ant Colony Optimization，ACO)是意大利学者Dorigo M受到蚂蚁觅食这一生理习性的启发所提出的算法。一方面，每个蚂蚁可以探测到其它蚂蚁留下的信息素，从而引导移动方向规划到达目的节点的路径；另一方面，由于信息素具有挥发性，其浓度的大小也间接反映了该条路径的长短及经过的蚂蚁数量，这在蚁蚂蚁中构成了一种信息素的正向反馈机制，因此，这个正反馈过程促使了在越短的路径上残留的信息素浓度越大。由于蚁群算法具有较强自适应性、鲁棒性、分布式等特点，具有十分广阔的应用前景。

2.1 协议网络模型

所有传感器节点被随机布置在正方形区域，对该网络做如下假设：

1)传感器节点随机部署后便不再移动，且节点能量有限，能获知坐标信息和自身剩余能量；

2)所有节点具有相同的处理能力、通信能力、存储能力，都能担任活跃节点、簇头或者普通节点；

3)基站位置固定，且能量不受限；

4)节点发射功率可控，且可通过信号的强度计算出节点之间的距离。

2.2 ACO-BEC协议簇首选举

基于蚁群算法的ACO-BEC协议也采用LEACH的‘轮’的概念，每一轮包括两个阶段：簇的建立和稳定数据传输。

在簇的建立阶段，ACO-BEC协议同样采用LEACH的选举簇首方式，但对LEACH协议选举时不考虑节点能量这一缺陷加以改进，由此设定新的阈值T′(n)，具体定义为：

(2)

式中，Ei_current为节点i当前的剩余能量，Einitial表示节点的初始能量。由式(2)可知，剩余能量越大的节点较之剩余能量少的节点，当选为簇头的概率更高。

2.3 稳定数据传输

ACO-BEC协议的数据传输阶段，不再是簇首与汇聚节点之间的直接单跳通信，而是利用蚁群算法自适应启发寻找一条在各簇首之间的最优多跳路径，进而将数据传输至汇聚节点。

2.3.1 蚁群算法的改进

无线传感器网络节点的拓扑结构可以看作一个连通的无向加权图G(N,V)，N为网络的节点集合，V为节点间的链路。初始时，各链路上赋予相同的初始信息素浓度τij(0)，第k只蚂蚁在行进过程中，根据各链路的信息素浓度决定转移方向，则从节点i出发选择节点j作为下一跳的转移概率为：

(3)

由式(3)可知，节点的下一跳转移概率主要受节点间的距离影响，而无线传感器网络的主要性能指标是网络的生存寿命，这就必须要求节点能耗均衡，故应使剩余能量多的节点作为下一跳的转移概率大，故将节点剩余能量融入启发函数中，改进后的转移概率为：

(4)

φij表示能耗因子，定义式如下：

(5)

式中，Ej为节点j的剩余能量，Eij-cost为节点i发送数据到下一跳节点j所需消耗的能量，dj-BS为节点j到基站的距离。由式(4)、(5)可看出，改进后的蚁群算法模型应用在无线传感器网络中，在簇首节点选择下一跳时，转移概率会依据节点间距离及下一跳节点的能量和距基站的距离关系共同选取：节点间距离越短，下一跳距离汇聚节点越近，且能量越大的节点的成为下一跳的转移概率越大。

2.3.2 信息素更新

基本的蚁群算法从更新信息素方法入手，提出了Ant-Cycle模型、Ant-Quantity模型和Ant-Density模型[12]。Ant-Cycle模型采用全局信息素更新策略，而后两种模型则采用了局部信息素更新策略，即蚂蚁走过相邻路径后更新路径信息素。本文为便于其他蚂蚁根据信息素的浓度来判断路径，采用了局部信息素更新策略Ant-Quantity模型，及时对该路径上的信息素进行更新。

当有蚂蚁从节点i到节点j的链路经过，信息素做如下的更新：

(6)

(7)

式中，Q为体现信息素大小的一个常数，Ej代表了节点当前的剩余能量，Hij代表该路径的跳数，据此蚂蚁就会倾向于选择节点剩余能量较大、跳数较小的路径。

3 仿真实验及性能分析

为了验证ACO-BEC协议的性能，本文采用MATLAB工具进行仿真实验。在仿真过程中，数据的发送和接收模型仍采用LEACH协议的简单能耗模型。初始时，将能量为 2J 的 100 个节点随机分布于 100 m×100 m 的覆盖区域，汇聚节点位置为(0,0)，信道的带宽是 2 Mb/s ，每个数据包长度为4 000 bit，控制消息长度为200 bit 。实验仿真的其它参数见表1。

表1 仿真参数

为了验证理论结果，通过仿真实验，分析了网络生存周期、节点能耗情况在ACO-BEC协议和LEACH原协议以及文献[8]改进的DCST算法的对比关系。仿真分析如下：

由图1可知，ACO-BEC协议的第一个节点死亡时间为150 s，在370 s左右节点基本死亡； LEACH协议在120 s左右就出现死亡，210 s左右节点全部死亡；而已改进的DCST算法第一个死亡节点时间为140 s，在305 s左右节点基本死亡。这是由于ACO-BEC协议优化路径过程，并在网络运行时，考虑了节点的剩余能量及节点间的距离，使得其较LEACH协议以及DCST算法出现第一个死亡节点的时间分别延长了约25%、7%，网络生命周期延长分别达到76%、23%。因此，ACO-BEC协议均衡了簇首的能量消耗，延长了网络的生存时间。

图1 网络中剩余存活节点数目比较

图2是网络中节点的总能耗随网络的运行周期的变化情况，可看出在网络运行的整个周期里，改进协议ACO-BEC的总能耗一直低于LEACH协议及文献[8]的DCST算法，这是由于在无线传感器网络中能量的消耗主要是由于数据的传输，原协议采用单跳通信传输数据，当簇首节点与汇聚节点距离过大时，所需能耗更为明显；改进协议利用蚁群算法寻找一条最优的多跳路径，有效均衡了各节点的能耗，提高网络寿命。

图2 网络节点总能耗比较

4 结论

路由协议是WSNs的核心关键技术，其性能的优劣对网络整体性能有着直接的影响。本文从提高网络寿命和节省能耗两个方面对LEACH 协议进行了改进，提出一种基于改进蚁群算法的新型路由协议。该协议利用了蚁群算法的自适应性，在选择下一跳时考虑了节点的剩余能量和路径距离对于转移概率以及遗留信息素大小的影响，均衡了簇首节点的能耗。仿真实验结果表明，该协议能有效均衡网络能量消耗，延长了网络寿命。下一步研究的主要工作是：在确保网络寿命的同时，对网络服务质量(QoS)以及协议的安全性加以研究考虑。

[1] Yick J, Mukherjee B, Ghosal D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12): 2292-2330.

[2] 任丰原,黄海宁,林 闯.无线传感器网络[J].软件学报, 2003, 14(7): 1282-1291.

[3] 崔逊学,左从菊.无线传感器网络简明教程[M].北京:清华大学出版社,2009.

[4] 张晓玲,梁 炜,于海斌,等.无线传感器网络传输调度方法综述[J].通信学报,2012,33(5): 143-157.

[5] Heinzelman W R, Handrakasan A, Alakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[A]. HICSS 2000: Proceedings of the 33rd Annual Hawaii International Conference on System Sciences[C]. Maui: IEEE Computer Society, 2000: 3005-3014.

[6] 赵菊敏,张子辰,李灯熬,等.基于LEACH路由协议的多跳节能路由算法[J].计算机测量与控制, 2014, 22(5):1506-1509.

[7] 董国勇,彭 力,吴 凡,等. 一种采用蚁群优化的WSN能量均衡非均匀分簇路由算法[J].小型微型计算机系统,2015,36(7):1565-1568.

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

[9] 张明才,薛安荣,王 伟.基于最小生成树的非均匀分簇路由算法[J].计算机应用,2012,32(3):787-790.

[10] 孙利民,李建中,陈 渝,等.无线传感器网络[M].北京:清华大学出版社,2005.

[11] 陈炳才,么华卓,杨明川,等.一种基于LEACH协议改进的簇间多跳路由协议[J].传感技术学报, 2014,27(3):373-377.

[12] Dorigo M, Blumb C. Ant colony optimization theory: A survey[J]. Theoretical Computer Science, 2005,344(2/3) :243-278．

Research on LEACH Protocol Based on Improved Ant Colony Algorithm

Yan Binheng, Liu Jun, Liu Guangbin, He Yangjiong

(Department of Information Engineering, Engineering College of PAP, Xi′an 710086,China)

In order to solve the problem of excessive energy consumption for transmitting to sink node directly from cluster heads in LEACH routing protocol, a routing protocol based on improved ant colony algorithm was proposed. This protocol introduced lead the energy consumption factor to improve the ant transition probability and the pheromone updating rule. And It would take full account of the residual energy of nodes and the distance between the nodes, through the establishment and update of pheromone, make sure to find the optimal path between cluster heads and base station, and use multi-hop transmission to balance the energy consumption of cluster nodes. Simulation results show that this improved routing protocol better than LEACH protocol on the cluster-head nodes selection, and it can extend the survival time of the network, and makes the energy consumption more balanced.

wireless sensor networks; LEACH protocol; ant colony algorithm; pheromone; energy balance

2016-06-20；

2016-07-17。

严斌亨(1993-)，男，福建仙游人，硕士研究生，主要从事无线传感器网络路由协议方向的研究。

刘 军(1963-)，男，北京人，教授，硕士研究生导师，主要从事物联网、无线传感器网络、无线通信方向的研究。

1671-4598(2016)12-0136-03

10.16526/j.cnki.11-4762/tp.2016.12.039

TP393

A