基于改进LEACH的多簇头分簇路由算法

任克强，余建华，谢 斌

(江西理工大学 信息工程学院，江西 赣州 341000)

基于改进LEACH的多簇头分簇路由算法

任克强，余建华，谢 斌

(江西理工大学 信息工程学院，江西 赣州 341000)

为了降低无线传感器网络(WSN)的能耗，延长网络的生存周期，提出一种多簇头双工作模式的分簇路由算法。算法对低功耗自适应集簇分层(LEACH)协议作了以下改进：采用多簇头双工作模式来分担单簇头的负荷，以解决单簇头因能耗较大而过早消亡的问题；选举簇头时充分考虑节点位置和节点剩余能量，并应用粒子群优化(PSO)算法优化簇头的选举，以均衡网络内各节点的能耗；建立簇与簇之间的数据传输路由，以减少簇间通信的能耗。仿真结果表明，算法有效降低了网络的能耗，延长了网络的生存周期。

无线传感器网络；分簇路由算法；LEACH协议；粒子群优化

无线传感器网络(Wireless Sensor Network，WSN)是由部署在监测区域内的大量传感器节点构成的无线自组织网络，传感器节点将监测到的数据通过路由算法来实现数据分组的多跳传输。WSNs的生存周期往往取决于传感器节点的能量，而传感器节点所携带的能量有限，因此，研究和设计高效节能的路由算法一直是WSNs领域的研究热点[1]。

WSNs路由算法主要有平面路由算法和分簇路由算法，分簇路由算法在拓扑管理、能量效率以及数据融合等方面具有明显的优势[2]。低功耗自适应集簇分层(low energy adaptive clustering hierarchy，LEACH)协议[3]作为分簇路由协议的典型代表，采用动态分簇、随机选举簇头等方式来延长网络生存周期；但存在单跳、单簇头以及能耗较大等不足。文献[4]根据节点剩余能量以及备选簇头与邻居簇头的距离来优化簇头的选举。文献[5]根据节点剩余能量和节点密度进行分簇，以平衡簇内和簇间的通信能耗。文献[6]提出一种采用链式传输的分簇路由协议，以减少节点间的传输能耗。文献[7]应用粒子群优化(Particle Swarm Optimization，PSO)算法优化分簇过程，选择高能量的节点担任簇头以克服能量受限的问题。文献[8]利用PSO算法将网络分成多个子区域，通过考虑节点剩余能量选举簇头，但簇头的负荷较重。

针对上述问题，本文对LEACH协议进行改进，提出一种基于改进LEACH和PSO的多簇头分簇路由算法。算法采用多簇头、双工作模式以及PSO优化簇头选举等措施来降低网络能耗，以延长网络生存周期。

1 相关技术

1.1 LEACH协议

LEACH协议定义了“轮”的概念，将时间划分为若干轮，每轮由簇的建立和数据传输两个阶段组成。

在簇的建立阶段，各传感器节点生成0～1之间的随机数，如果某个节点选取的随机数小于所设定的阈值T(n)，那么该节点就当选为这一轮的簇头。T(n)的计算式为

(1)

式中：p为簇头占总节点数的百分数；r为当前的轮数；G为最近的1/p轮中未当选簇头节点的集合。被选为簇头的节点向网络广播当选簇头的信息，其他节点根据接收信号的强度选择加入哪个簇，并告知相应的簇头，完成分簇。

在数据传输阶段，簇内普通节点周期性地将采集数据发送给簇头节点，簇头节点将接收到的信息进行必要的处理后传送给基站。持续工作一段时间后，进行下一轮簇头选举和分簇。

1.2 粒子群优化算法

粒子群优化算法源于对鸟群捕食行为的研究，鸟群中的每只鸟被抽象成“粒子”，每个粒子的适应值取决于优化函数，而飞行的方向和位置则由速度v决定。对于初始的一群随机粒子，算法通过个体极值pbest和全局最优值gbest来更新个体，并进行迭代来寻求最优解。

vid(t+1)=wvid(t)+c1*rand1()*(pbest-xid(t))+

c2*rand2()*(gbest-xid(t))

(2)

xid(t+1)=xid(t)+vid(t+1)

(3)

式中：vid(t)为粒子当前的速度；w为惯性权重；xid(t)为当前粒子的位置；rand1()和rand2()为介于(0，1)之间的随机函数；c1和c2为学习因子；通常c1=c2=2。

2 算法描述

LEACH协议中的簇头节点主要负责簇内数据的收集、融合和转发，其能耗比普通节点大很多。由于LEACH协议采用随机策略选举簇头，有可能导致能量低的节点当选簇头，另外，簇头节点直接与基站进行通信，也容易导致距基站较远的簇头节点因能耗较大而过早消亡。因此，本文对LEACH协议进行了改进，采用多簇头双工作模式来分担单簇头的负荷，以解决单簇头工作负荷过重而过早消亡的问题；设计节点的适应值函数时充分考虑节点的当前剩余能量和位置关系，并应用PSO算法优化簇头的选举，以均衡网络内各节点的能耗，延长网络的生存周期。

本文簇头分为主簇头(CHR)、转发簇头(CHT)以及备用簇头(CHP)，工作模式分为三簇头模式和双簇头模式。算法仍采用轮作为周期，相比于以往轮的定义，本文的轮由首轮分簇、簇头选举、簇内工作模式选择以及簇间数据传输4部分组成。

2.1 首轮分簇

首轮分簇阶段主要完成节点信息的收集、选举临时簇头并进行分簇。网络中的节点将各自的位置和能量信息发送给基站，基站将收集到的信息进行处理，并计算出当前网络能量的平均值。为了减小能量相对较小的节点在首轮分簇阶段担任临时簇头的概率，各节点将生成的随机数乘上一个以各自当前剩余能量与当前网络能量平均值的比值的负指数权衡因子作为新的随机数，当新的随机数小于阈值T(n)时，节点即可选为临时簇头，当选的临时簇头广播其当选消息，若在其广播范围之内存在其他临时簇头，则能量最大的临时簇头当选为最终的临时簇头，能量相对小的则变成普通节点，普通节点根据接收到的信息强弱加入相应的簇。由于节点的位置是固定的，所以在之后的运行周期只需要向基站发送能量信息。

2.2 簇头选举

LEACH协议选举簇头时未充分考虑节点的当前能量、簇头之间的距离以及簇头与普通节点之间的距离等因素，容易使能量低、位置偏的节点被选为簇头。为了避免这类情况的发生，本文在簇头选举的过程中引入了PSO算法，要利用PSO算法进行簇头选举优化，必须首先根据各个簇头在通信过程中担任的角色，设计相应的适应值函数，本文为PSO算法设计的适应值函数如表1所示。

表1 簇头选举的适应值函数

1)CHR的适应值函数：CHR负责收集簇内节点的信息并转发给CHP进行融合(三簇头模式)，或者将收集的信息融合后转发给CHT(双簇头模式)。因此，当选的CHR必须具备较高的能量、距簇内各普通节点的平均距离最小。其中，n为簇内节点的个数；f1为候选CHR能量评价因子，等于候选CHR的当前能量Ecurrent(k)除以所有节点当前能量之和，值越大，候选CHR的能量越高；f2为候选CHR到簇内剩余各个节点距离的评价因子，等于候选CHR到所有簇内节点之间的距离之和除以候选CHR到某一节点距离的最大值，值越接近(n-1)/2，表示距离簇内节点的平均距离越小；α1，α2为权重因子。

2)CHT的适应值函数：CHT负责在两种工作模式下分别接收CHR或者CHP转发过来的数据，并将数据转发给基站。CHT不仅要有较高的能量，而且距CHR以及基站的距离越小越好。其中，G1为候选CHT能量评价因子，等于候选CHT的能量与节点能量总和之比，比值越大表示当前候选CHT能量越高；G2为候选CHT到CHR的距离，等于候选CHT到CHR距离的最小值，值越小表示候选CHT越靠近CHR；G3为距基站的距离，等于候选CHT到基站距离的最小值，值越小表示距离基站越近，将数据转发给基站越省能量；β1，β2，β3为权重因子。

3)CHP的适应值函数：在三簇头模式下，CHP负责将CHR转发过来的数据进行融合并将融合后的数据转发给CHT；此外，当CHR意外死亡，CHP可以履行CHR的功能。所以CHP应具有较高的能量，并且距CHR和CHT越近越好。其中，M1为候选CHP能量占当前总能量的比值，比值越大说明其当前能量越高；M2为候选CHP分别到CHR和CHT的距离，等于候选CHP分别到CHR和CHT距离之和的最小值，值越小表示候选CHP越靠近CHR和CHT节点；λ1，λ2为权重因子。

本文采用PSO选取簇头的步骤如下：

步骤1，初始化粒子种群，即随机初始化粒子的位置xid和速度vid，对于平面网络而言，xid和vid在x，y两个方向上有分量。

步骤2，计算每个粒子的适应值F1，并令粒子的个体极值pbest等于粒子的当前位置，全局极值gbest等于当前粒子中适应值最大的粒子所对应的位置。

步骤3，通过式(2)、式(3)更新粒子的xid和vid，对于更新后的xid，vid，相应地更新粒子的适应值F1。

步骤4，更新个体极值pbest以及全局极值gbest。

步骤5，重复执行步骤2～步骤4，直至达到预定迭代次数。

步骤6，当达到最大迭代次数时，选择全局极值gbest，作为CHR的位置。

步骤7，根据CHP的适应值函数和CHT的适应值函数，重复执行步骤2～步骤6，选择全局最优解作为CHP和CHT。

2.3 簇内工作模式选择

设CHR和CHP之间的距离为d1，CHP和CHT之间的距离为d2，CHT和CHR之间的距离为d3，且d1，d2和d3的值均小于阈值d0。则根据自由空间能量模型[9]，簇头a转发1bit数据到距离为d的簇头b的能耗为Es(l,d)=lEelec+lεfsd2，其中εfs为功率放大能耗因子，Eelec为发射电路的能耗。

节点接收1bit数据的能耗为Ec=lEelec，将1bit数据进行融合的能耗为Ed=lEDF(EDF为融合单位比特数据所需的能量)。

如果采用三簇头工作模式，CHR负责收集簇内节点信息并转发给CHP的能耗为E1，CHP将接收到的信息进行融合处理后转发给CHT的耗能为E2，CHT将接收到的信息转发给临近簇的CHT的耗能为Et，那么在三簇头模式下将1bit数据转发至簇外簇头的总能耗为

(4)

如果采用双簇头模式工作，CHR收集、融合簇内信息并将融合后的数据转发给CHT的耗能为E4；CHT将接收到的信息转发给临近簇的CHT的能耗为Et；则在双簇头模式下将1bit数据转发至簇外簇头的总能耗为

(5)

由于Eelec，Ec和εfs均为常数，令Etotal2=Etotal3，可以得到

(6)

2.4 簇间数据传输

簇生成之后，需要将簇内收集的数据转发至基站。每个CHT根据与临近簇的CHT的距离，选择距离较近的临近簇CHT为其数据转发的中转簇头，从而在簇与簇之间建立一条以CHT为链的数据传输路由，这样可以减少数据传输过程的能耗。

3 实验仿真及分析

为了验证本文算法的性能，将本文算法分别与LEACH、文献[7]以及文献[8]进行比较实验。实验平台：Windows 7 专业版+MATLAB 2009a。实验场景：200个节点随机分布在200 m×200 m的区域内，基站的坐标位于(100，150)。实验参数：网络仿真周期为1 500轮，节点的初始能量为0.5 J，Eelec=50 nJ/bit，εfs=10 (pJ·bit-1·m-2)，d0=87 m，α1=0.5，α2=0.5，β1=0.5，β2=0.25，β3=0.25，λ1=0.3，λ2=0.7。

3.1 网络存活节点

随着网络的运行，有些节点会因能量耗尽而死亡，同一时间内网络存活节点数量越多，则网络节点的能量使用越均衡。图1为4种算法随网络运行时间变化的网络存活节点。

图1 网络存活节点

从图1可以看出，本文算法的存活节点数多于其他3种算法。这是因为本文算法采用多簇头混合工作模式，优化选出的各簇头能量高且各司其职，有效减轻了簇间信息的转发负荷，均衡了簇内节点的能量消耗，从而有效地延长了节点的存活时间。而其他3种算法分别在簇头选举、簇头分布、信息传输以及能耗均衡上不同程度地存在缺陷，导致节点的存活时间得不到有效的延长。

3.2 网络总能耗

图2所示为4种算法的网络总能耗。从图2可以看出，本文算法的网络总能耗曲线斜率最小，其次是文献[8]、文献[7]，最大的是LEACH，说明本文算法在网络运行每轮的网络总能耗都比LEACH、文献[7]及文献[8]要少，这是因为本文算法能够使簇内节点和簇头之间的能耗更加均衡，从而达到降低网络总能耗及延长网络生存周期的目的。

图2 网络总能耗

3.3 生存周期

生存周期可以通过第1个节点死亡(FND)、半数节点死亡(HND)及最后一个节点死亡轮数(LND)3个指标来衡量。表2所示为4种算法的FND、HND和LND。

表2 4种算法的生存周期比较

从表2可知，LEACH、文献[7]、文献[8]和本文算法的FND出现轮数分别为293，423，667和813，HND出现的轮数分别为415，645，796和917，LND出现的轮数分别为695，783，832和1 026，本文算法有效延长了网络的生存周期。此外，从仿真开始到出现FND的时间段称为网络稳定期，稳定期是衡量网络稳定系数的重要指标，FND出现的时间越晚，网络的稳定性越好。LEACH、文献[7]、文献[8]和本文算法的稳定期分别为293轮、423轮、667轮和813轮，本文算法的稳定期是LEACH的2.77倍，文献[7]的1.92倍，文献[8]的1.21倍，本文算法有效均衡了各个节点能耗，推迟了FND出现的时间，使得网络具有更好的稳定性和可靠性。

4 小结

针对LEACH协议存在的不足，提出一种基于改进LEACH和PSO的多簇头双工作模式分簇路由算法。该算法主要从簇头负荷、工作模式和簇头选举3个方面对LEACH协议进行了改进和优化，并在相同环境下与LEACH协议和相关文献进行比较实验。实验结果表明，该算法的性能(存活节点、生存周期以及总能耗)优于LEACH协议和相关文献，可以有效均衡网络能耗，延长网络生存周期。

[1] 赵阿群，刘昌阳.一种基于收集树协议的工业无线传感器网络动态路由机制[J].电子与信息学报，2012，34(9)：2194-2199.

[2] 邹虹，彭国龙.一种基于LEACH改进的均匀分簇路由算法[J]. 电视技术，2013，37(3)：133-136.

[3] HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proc. Hawaii International Conference on System Sciences. Hawaii：IEEE Computer Society，2000：3005-3014.

[4] 黄加异，程良伦.一种聚类区域自适应调整的WSN能耗均衡分簇算法[J].计算机应用研究，2012，29(11)：4276-4279.

[5] 卢先领，王莹莹，王洪斌，等.无线传感器网络能量均衡的非均匀分簇算法[J].计算机科学，2013，40(5)：78-81.

[6] 赵菊敏，张子辰，李灯熬.一种无线传感器网络链式传输分簇路由协议[J].传感器与微系统，2014，33(3)：135-138.

[7] 梁英，于海斌，曾鹏.应用PSO优化基于分簇的无线传感器网络路由协议[J].控制与决策，2006，21(4)：453-461.

[8] 陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法[J].传感技术学报，2013，26(1)：116-121.

[9] 杨永健，贾冰，王杰.无线传感器网络中LEACH协议的改进[J].北京邮电大学学报，2013，36(1)：105-109.

任克强(1959— )，教授，硕士生导师，主要研究方向为信息隐藏、无线传感器网络等；

余建华(1987— )，硕士研究生，主研无线传感器网络；

谢 斌(1977— )，副教授，硕士生导师，主要研究方向为视频信号处理、通信技术。

责任编辑：许 盈

Multi-cluster-heads Clustering Routing Algorithm Based on Improved LEACH

REN Keqiang，YU Jianhua，XIE Bin

(SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,JiangxiGanzhou341000,China)

In order to reduce the energy consumption of WSN and prolong the network lifetime, a clustering routing algorithm with multi-cluster-heads and double working modes is proposed. The algorithm makes following improvement on LEACH protocol: to solve the problem of single cluster head premature demise due to larger energy consumption, multi-cluster-heads and double working modes are used to share the load of single cluster head; to balance energy consumption of network nodes, PSO algorithm is used to optimize cluster head election, and head election considers location and residual energy of nodes fully; data transmission routing among clusters is established to reduce energy consumption of inter cluster communication. The simulation results show that the algorithm can efficiently reduce the network energy consumption, and prolong the network lifetime.

WSN; clustering routing algorithm; LEACH protocol; particle swarm optimization

【本文献信息】任克强，余建华，谢斌.基于改进LEACH的多簇头分簇路由算法[J].电视技术,2015，39(13).

江西省教育厅青年科学基金项目(GJJ11132)；江西省研究生创新基金项目(YC2013-S199)

TP393

A

10.16280/j.videoe.2015.13.015

2014-12-06