基于蚁群算法的LEACH协议在WSN中的研究

郦元宏 王泽民

（瑞利科技有限公司 新能源事业部，杭州，310023）

基于蚁群算法的LEACH协议在WSN中的研究

郦元宏 王泽民

（瑞利科技有限公司 新能源事业部，杭州，310023）

针对WSN中LEACH协议的簇头选举过程未考虑节点剩余能量，以及簇头与Sink节点之间采用单跳通信造成某些节点因能量损耗过快从而造成网络分割的问题，提出一种基于蚁群算法的 LEACH协议。该协议通过引入节点剩余能量的方法，降低了低能量节点当选簇头的概率，并实现了能量均衡的多跳路由。仿真实验结果表明，与传统LEACH协议相比，新协议降低了能耗，延长了网络生命周期。

无线传感器网络；LEACH协议；蚁群算法

无线传感器网络（Wireless Sensor Network，WSN）是一种自组织测控网络系统，由大量随机分布的具有特定功能的传感器节点构成，具有数据采集、感知、控制等多种功能，可广泛用于军事、工业和农业等众多领域[1]。网络中的节点一般由电池提供能量，也可以由太阳能、风能等新能源提供。由于节点能量的有限性，降低节点的能量消耗，延长网络的生命周期，成为无线传感器网络研究中的一个热点[2]。

WSN中，LEACH（Low Energy Adaptive Clustering Hierarchy， LEACH）协议是一种典型的分层协议[3]，目前使用较为成熟广泛。该协议通过分簇把网络自组织起来。簇首负责把簇成员的信息收集起来，并将其发给Sink节点，这可以有效的减少簇成员的能量消耗。但是LEACH协议的多跳路由功能比较弱，在网络的规模比较大时，没有对多条路由进行合理的优化，在路由过程中造成了大量的能量浪费，进而缩短了网络的生命周期。

文献[4-6]对传统的LEACH进行了改进，其中文献[4]将 LEACH 协议和蚁群算法进行了简单的组合，簇头节点的选取规则未有更改，对簇头之间的路由计算也只是简单套用蚁群算法。文献[5]主要针对 LEACH 协议中簇头节点的选取规则进行重新设计，在簇结构形成阶段选取簇头时考虑各个传感器节点的剩余能量、但是未对簇头路由算法进行优化，导致路由过程整体能耗过高。文献[6]对簇头选取进行了比较合理的规划，充分考虑了节点剩余能力、平均能量等因素对簇头选择的影响，但是没有将能量因子融入到簇头路由选择中，导致某些关键路由节点的能量消耗过快。

本文提出了一种改进的LEACH协议，新协议在多跳路由选择上采用了改进的蚁群算法寻找最优解，同时在簇首选举中加入了节点剩余能量和局部网络平均能量的影响因子。

1 LEACH协议分析

LEACH是第一种应用于无线传感器网络的分层路由协议，很多后续的分层路由协议都是基于它改进而来。LEACH协议的执行过程是周期性的，每个周期成为一轮，每一轮分为两个阶段，分别为簇的建立和数据传输。

在簇的建立阶段，每个节点产生一个（0～1）之间的随机数，当这个随机数小于预先设定的阈值Ti时，该节点当选簇首。随后，当选为簇首的节点向四周广播其当选为簇首的消息，其它节点收到消息后，将根据一定的规则（比如根据无线电信号的强度），决定应当加入哪个簇，并回复消息以告知该簇首[7]。

阈值Ti定义如下：

式中，p为簇首节点数占节点总数的比例，r为当前进行的轮数，G为前rmod(1/p)轮中尚且没有当选簇首节点的集合。

在数据的传输阶段，簇内成员使用 TDMA（Time Division Multiple Access）机制，向簇首节点传输数据，簇首节点将收集到的各节点数据进行数据融合，最后发送给Sink节点。稳定传输一定流量的数据后，LEACH协议将重新进行簇首选举，开始下一个周期。

由于LEACH协议在簇首选举的过程中只是简单采用了随机的算法试图均衡整个网络的能量消耗，没有考虑节点的剩余能量的情况，易使某些关键节点过多的当选为簇首，并导致其能量耗尽而过早死亡。因此必须要引入一种充分考虑节点剩余能量的机制，避免能量低节点过多担任簇首。

2 蚁群算法

蚁群算法(Ant colony algorithm)是一种拥有广阔应用前景的仿生算法，具有良好的分布式计算机制和较强的鲁棒性，最初用来解决复杂的 TSP（Travelling Salesman Problem）最优路径问题[8-9]。蚁群算法的诞生，正是受自然界中蚁群的觅食行为的启发。蚁群在觅食的过程中，会在经过的路线上留下一些特殊的化学物质，我们称之为信息素(pheromone)。蚁群中的每个蚂蚁都能感知到自己所处位置附近信息素的存在的多寡，会倾向于往信息素浓度高的方向移动，并使该方向的信息素进一步加强，如此大量积累，便可以找到最优的路径。

在蚁群算法中，第k只蚂蚁，从i节点选择到j节点路径的概率为

第t轮结束，开始第t+1轮，其信息素更新

其中ρ表示信息素的挥发系数，取值区间为(0，1)，allowedk为蚂蚁k下一步可以选择的节点集合，表示节点i到节点j之间的信息素浓度，表示i到j的能见度，一般取i至j的距离的倒数，α为信息启发式因子，代表信息素的重要性，β为期望启发式因子，代表距离的重要性。

显然，蚁群算法对寻找最优路径（一般为最短路径）非常有效，如果将其应用到WSN中寻找最短路由也是很合适的。但该算法仅仅找到了最短的路由，没有考虑节点剩余能量的情况。

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

3.1 新协议的算法原理

基于以上对蚁群算法和LEACH协议在无线传感器网络应用中存在的问题，本文提出了一种新的协议，名为ANT-LEACH协议。新协议从以下两个方面对LEACH协议进行了改进。首先改进LEACH协议的簇首选举规则。修改阈值Ti的生成公式：

在簇首选举公式中，通过引入能量因子，可降低低能量节点当选簇首的概率，均衡整个网络的能量；其次，将蚁群算法中的能见度系数更改为由距离和节点剩余能量共同决定；加入系数 ，主要是由于无线电传输模型中信号的衰减反比于距离的三次方，这里系数可以在3～4间取值[10]。为矫正系数，表示无线电信号在信道中的传播质量，一般μ≤1。新的能见度系数

3.2 ANT-LEACH 协议实现

ANT-LEACH协议延续了传统LEACH协议的流程，但改进了簇首节点选举算法和路由算法，具体流程如图1所示。

图1 ANT-LEACH协议的流程图

4 仿真实验和结果分析

为了验证 ANT-LEACH协议的性能，使用OPNET网络仿真工具对新协议进行建模和仿真[11]。在200 m×200 m范围内，随机布置50个节点，每个节点的初始能量为0.5 J，控制包/广播包的长度为64 bit，数据包的长度为1024 bit，自由空间的信号放大器放大倍数En=1.0×10−11J/bit·m−2，多径衰减模型中放大器的放大倍数Ef=1.0×10−15J/bit·m−4，收发器耗能 6.0×10−8J/bit，基站坐标（48,180），α=1，β=1.8，γ=3，μ=0.9，ρ=0.2。设定仿真探头为：节点存活个数、存活节点的平均能量。仿真结果如图2和3所示。

图2 点存活个数和时间的关系

图3 存活节点的平均能量和时间的关系

从图2可以看出，ANT-LEACH协议出现第一个节点死亡的时间相比LEACH协议第一个节点死亡的时间推迟了至少10 min，即使用ANT-LEACH协议的网络的稳定期比LEACH协议提高35%左右。这主要是由于ANT-LEACH协议使得低能量节点当选簇首的概率大为降低，从而避免了其过早死亡。由于新协议在簇头和基站之间的数据通信采用了基于能量因子的改进的蚁群算法的进行多跳优化策略，从而在获得近似最短路由的前提下，避免了某些能量低节点过多地承担数据转发任务，从而进一步延长了整个网络的生存时间。从图3 可以看出，ANT-LEACH协议对降低网络平均能耗是有效的，相比LEACH协议，新协议的平均能耗曲线更为平滑，平均剩余能量提高明显。

5 结束语

本文将具有良好鲁棒性的蚁群算法应用于LEACH协议，并且对两种算法进了针对性的改进，最终使改进后的蚁群算法在兼顾能量均衡的前提下，获得近似最优解。工程实践也表明，该协议可以用于特别强调节能的传感器自组网，对延长网络寿命有重要意义。但目前该研究只针对小规模的无线网络，而且仿真中随机布置的 30个节点也是以基站为中心随机分布，因此下一步可以更大规模网络和非基站为中心网络进行研究，并定量分析该协议的性能。

[1]PRAVEENA A,DEVASENA S.Achieving energy efficient and secure communication in wireless sensor networks[J].IEEE,2006,11(5):341-356．

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

[3]沈波,张世永,钟亦平.无线传感器网络分簇路由协议[J].软件学报,2006,17(7):1587-1600.

[4]胡彧,王静. 基于蚁群算法的LEACH协议研究[J].传感技术学报,2011,26(6):851-856.

[5]李虎雄,张克旺.基于蚁群优化的无线传感器网络路由优化算法[J]. 西北工业大学学报,2012,19(1):34-36.

[6]王林,潘军.无线传感器网络中基于能量优化的路由协议ANT-LEACH[J].计算机应用, 2011,25(3):715-717

[7]HEINZELMAN W R,CHANDRAKASAN A,BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C].Proceedings of the 33rd HawaiiInternational Conference on System Sciences,2000.

[8]杨靖,林溢,熊伟丽,等.蚁群算法在无线传感器网络路由中的应用研究[J].计算机工程与应用,2008,44(22):13-15.

[9]王青正,闵林,郭拯危,等.基于蚁群优化的无线传感器网络能耗均衡路由算法[J].计算机应用研究,2009,26(12):4716-4718.

[10]张毅,梁艳春.蚁群算法中求解参数最优选择分析[J].计算机应用研究,2007,24(8):70-71．

[11]王磊,施荣华.无线传感器网络路由算法的仿真研究[J].计算机仿真,2010,28(3):170-174.