基于能量均衡高效的LEACH 改进算法*

谢 佳，张玲华

（南京邮电大学 通信与信息工程学院，江苏 南京 210023）

0 引言

无线传感器网络(Wireless Sensor Network,WSN)是一种随机部署在某个地域范围内的自组织网络[1]。WSN[2]能够监测、感知和收集区域内环境或被监控对象的信息，广泛应用于国防军事、工业过程控制、环境监测等领域[3]，其研究、开发和应用关系到国家安全、经济发展等许多重要方面[4]。

WSN 具有以数据为中心、资源受限、快速部署、网络拓扑频繁变化不易维护等特点[5]。其应用环境特殊，当节点能量耗尽将无法继续工作。因此,为了能够延长WSN 的生命周期，设计出简单有效的协议，是WSN 的一项关键技术。

LEACH(Low Energy Adaptive Clustering Hierarchy)[6]

是最早被提出来的自适应分簇路由协议，但在严重限能的WSN 中，对簇首的选择较为随机，且没有将节点密度、节点负荷和节点剩余能量考虑进簇首选举过程中，整个网络性能较低[7]，不利于WSN 的生存。

很多学者提出了改进的LEACH 协议。文献[8]中提出了LEACH-C 协议，通过获取节点的位置和剩余能量信息参与簇首选举，优化分簇，但频繁交换信息使得网络能耗加快；文献[9]通过建立规模不同的簇提出了EEUC 路由协议；文献[10]对EEUC 协议进行了改进，但是没有考虑到随着周期不同，各个因子对网络负载均衡的影响也不同；文献[11]的LEACH-Advanced 协议加入了剩余能量因子、距离因子，对LEACH 算法的阀值函数进行修正，但是没有考虑密度因子的影响。

针对以上问题，本文提出了一种基于能量均衡高效的LEACH 改进协议LEACH-X。通过仿真数据的结果得出，LEACH-X 协议与传统LEACH 和LEACHAdvanced 相比，降低了功耗，明显延缓了第一个死亡节点的出现，一定时间内存活节点增多，有效延长了网络寿命。

1 LEACH 协议概述

1.1 LEACH 协议简介

LEACH 工作周期在簇首选举阶段，节点生成一个随机值，该值与阈值T(n)比较，若小于阈值，则该节点就被选举为本轮的簇首。阈值T(n)公式[12]如下:

式中，P是网络中簇首节点所占比，r表示当前轮数，G是在运转(1/p)轮后未被选择为簇首节点的节点集。

1.2 网络模型

本文对WSN 作如下预置条件：

（1）传感器节点部署随机，部署之后不能再移动;

（2）传感器节点具有相等的初始能量，其计算、通信和融合数据的能力是相同的;

（3）传感器节点能量有限，普通节点无能量补充；

（4）传感器节点可以感知信号强度从而计算获得距离。

1.3 能耗模型

无线传感器网络中根据接收方和发送方之间的距离来决定采用哪种能量模型[13]进行能量计算:发送方所消耗的能量为：

接收方所消耗的能量为:

式中，Eelec为收发器或接收器电路所消耗的能量;k为传输的数据大小;d是发送和接收方间距离;εfs、εmp为自由空间和多径衰落的损耗系数;d0为距离阀值，定义为:

2 LEACH-X 协议

本文引入剩余能量因子、密度因子和距离因子，考虑最优簇首数目和本轮次中当选过簇首的次数，考虑普通节点是否需要入簇的必要性，再结合节点部署区域对阈值公式T(n)进行改进，并对候选簇首进行二次竞争选举，减小了条件不佳的节点当选簇首的概率，均衡整个网络的能量负载，延长网络寿命避免部分节点提前死亡而导致网络瘫痪。

2.1 剩余能量因子

节点的初始能量相同，随着运行周期的不断增加，所有节点的能量都减少，而当选过簇首的节点若被频繁选取将导致这些节点提前能量枯竭死亡。根据参考文献[14]引入剩余能量因子Esurplus(i)对阈值函数进行修正，定义为:

式中，Ecurrent(i)为节点i的当前剩余能量，Eaverage(r-1)是第r-1 轮节点的平均能量，E0是网络初始时的平均能量。该式表明，节点剩余能量越大，通过阈值函数当选簇首的概率就越大。剩余能量因子的引进充分考虑了节点的剩余能量，使簇首的选取更为合理，延长网络的工作时间。

2.2 密度因子

在实际应用中，大多数无线传感器网络节点都是随机部署的，若簇首节点附近的节点数量少，则会增加通信成本导致节点能量消耗较快。受文献[14]启发，引入归一化邻居节点密度因子(i)，其定义为:

σ(i)为邻居节点密度,其计算式为:

式中，Nneibor是在通信半径内的邻居节点数量，Nst为均匀分布簇中节点邻居节点数。邻居节点的集合为：

其中，d(i,j)为节点i、j之间的距离，R为通信半径。根据参考文献[15]得到:

其中，A为一个定值（分布的正方形区域边长）；N为监测范围内节点总数量；p(i)表示簇首的数量占所有节点数量的百分比，其计算式为：

式中，knum为网络中分簇的数量，Nalive为网络存活节点总数量。根据文献[16]，最优簇首数:

根据密度因子的定义，若节点密度过小，数据传输大部分采用多径衰落模式，数据传输成本很高，引入密度因子，通过阈值函数降低其成为簇首的概率，使网络能耗更均衡。

2.3 距离因子

由能耗模型可知，距离Sink 节点较远的节点消耗的能量比其他节点更多。无线传感器网络中，接收信号的强弱和信号的传输距离成反比，基于这个原理可以获得节点之间的距离。本文引入参考文献[15]中的距离因子d(i)，其定义如下:

式中，dmax和dmin代表网络中节点到Sink 节点距离的最大值和最小值，dtoSink为节点i与Sink 节点之间的距离。距离因子经过归一化，数值控制在0～1 之间，方便控制参数。距离Sink 节点越近，当选簇首的概率越大，使得簇首的选举更为合理。

2.4 阈值函数

参考文献[16]提出的一种分区方法，可以将部署区域划分，分别采取不同的能耗模型。改进的阈值函数为：

式中，(i)为密度因子，函数M(i)、F(i)的定义为：

其中，Ctimes为i节点当选过簇首的次数，w1和w2是增益参数。

新的阈值函数针对节点部署的不同区域采取不同的增益参数。离Sink 节点较近的区域，采用自由空间衰落能耗模型，此时节点能耗相比多径传输要少，修正时增大距离因子的权重;对于离Sink 节点较远区域的节点，采用多径衰落能耗模型，节点能耗更快更容易提前死亡，于是修正时减小距离因子的权重。

2.5 二次选举

参考文献[17]提出了候选簇首权值的定义，本文在此基础上进行改进，候选簇首的竞争权值为：

式中，λ1、λ2和λ3是和为1 的权值因子。根据参考文献[15]及多次实验验证，将密度因子的加权值λ2设成1/5仿真效果较好。对于剩余能量因子的加权值λ1，随着轮次的增加，剩余能量越来越少，为了均衡节点能量，需更加侧重考虑剩余能量因素。经多次验证，加权因子λ1取值3/5，间距因子的加权值λ3取值1/5 时得到的仿真结果较好。

根据式(16)可知，节点的剩余能量越大，它能承担的成员节点数就越多，就越适合成为簇首；同理，其所含邻居节点数越多，即相对密度越大，通信成本越低；候选簇首到Sink 节点的距离越近，其传输数据所需能量就越少，则更适合当选簇首。

2.6 LEACH-X 算法流程

LEACH-X 算法步骤如下：

（1）初始阶段，Sink 节点向全网广播信号，接收节点计算出与Sink 节点的距离，按照式(15)划分区域;

（2）普通节点向Sink 节点发送位置信息与能量信息;

（3）Sink 节点计算得出最大距离dmax和最小距离dmin，平均剩余能量并广播这些消息;

（4）簇建立阶段，节点接收首先比较当前能量与平均剩余能量的大小，再计算得到剩余能量因子Esurplus(i)、密度因子(i)、距离因子d(i)，记录此轮当选过簇首的次数Ctimes；

（5）节点生成随机数值rand，对照式(13)选取相应的阈值函数计算T(i)，小于阈值T(i)，当选为候选簇首;

（6）候选簇首根据式(16)计算竞争权值，并广播自己为簇首的消息，否则为普通节点;

（7）普通节点接收到簇首的消息，分别计算与簇首和基站的距离，若与基站的距离比任一簇首的距离近则不加入簇，否则选择最近的簇首加入簇;

（8）簇建立阶段完成，进入稳定传输阶段,普通节点将监测的信息发给簇首节点簇首压缩融合数据发往基站;

（9）一个周期完成，循环重复簇建立阶段和稳定传输阶段，直到网络中所有节点死亡。

LEACH-X 算法流程如图1 所示。

图1 算法流程图

3 实验仿真与结果分析

本文在MATLAB 平台上进行仿真实验，对算法LEACH、LEACH-Advanced[12]、LEACH-X 进行性能比较分析。具体参数设置见表1。

表1 网络参数设置

3.1 存活节点

本实验假设网络检测区域为100×100 m2的方形区域，节点数量为100 个，Sink 坐标为(180,225)，节点随机均匀分布。选取2 个时间点轮数r=1 200 和r=1 400 对3种算法当前存活节点的分布进行比较，且3 种算法的初始分布相同，如图2 所示，其中横坐标与纵坐标表示网络检测区域的范围，单位为m。

图2 节点分布图

图3 和图4 呈现了随周期数变化的网络存活节点数。

图3 第1 个、第10 个和所有节点死亡周期

图4 存活节点数

LEACH 算法的第一个死亡节点出现在周期856，LEACH-Advanced 与LEACH-X 算法第一个死亡节点出现在周期1 311 和1 529，相较LEACH 算法延迟了53%和78%。

所有节点死亡则判定网络死亡。LEACH 算法的网络死亡时间在周期1 369，LEACH-Advanced 算法的网络死亡时间在周期1 598，相较LEACH 延迟了16.7%，LEACH-X 算法的网络死亡时间为周期2 412，相较LEACH 延迟了76.1%

从以上分析可以得出，LEACH-X 算法在延长网络寿命上优于LEACH 和LEACH-Advanced 算法，因为LEACH-X 对簇首的选举条件多加限制，且考虑了普通节点加入簇的必要性，对不同的区域节点采取不同的优化参数，二次竞争考虑了剩余能量、节点密度和距离，延缓了节点死亡。

3.2 剩余能量和发送的数据包

网络中设置节点的初始能量为0.5 J，Sink 节点能量无限制。随周期变化的网络剩余能量如图5 所示。

图5 网络剩余能量

相较前两种算法，LEACH-X 在网络能量损耗50%时延迟了大约55.2%和31.5%；网络能量损耗90%时，相较前两种算法，LEACH-X 延迟了大约68.8%和38.6%。

网络中普通节点将处理后的数据发送给簇首节点或者直接发送到Sink 节点，数据经过簇首节点的压缩融合后再发往Sink，随周期变化发送到Sink 节点的数据包数如图6 所示。可以看到相较于另外两种协议，LEACH-X 发送到Sink 节点的数据包数量明显增多。

图6 发送到Sink 节点的数据包数

3.3 结果分析

根据以上的实验结果，可以证明LEACH-X 协议在网络生存时间、能量消耗、数据发送上都要优于LEACH和LEACH-Advanced。从簇首成簇的原理上分析，LEACH 簇首的选举完全随机，容易使得节点的负载不均衡，选取剩余能量较低，距离Sink 节点不合理的节点成为簇首，这会导致网络能耗较快，节点的死亡提前，网络生存时间大大减短。LEACH-Advanced 利用每个节点发送位置信息和剩余能量生成能耗更低、性能更低的簇，但没有考虑最优簇首数目、节点当选过簇首的次数和不同区域的划分。

LEACH-X 优化了网络性能：(1)簇首选择充分考虑了节点负荷，结合最优簇首数目提出密度因子，合理增大了附近节点密度大的候选节点当选的概率，有效均衡了网络负载；(2)考虑节点的剩余能量，增加剩余能量多，减少多次当选过簇首节点被选举为簇首的概率；(3)充分考虑节点的地理位置，对节点的部署区域进行分区处理，提出距离因子并针对不同的区域采用不同的加权参数；(4)二次竞争选举中合理考虑了剩余能量因子、密度因子、距离因子的影响。因此，改进的LEACH-X 协议优化了传统簇首选举函数的不合理性，增大有足够能量且位置、密度更合理的节点当选的概率。相较其他2 种协议，LEACH-X 协议减少了某些簇首节点能耗过大而加快死亡的情况出现，网络能耗更低性能更优，寿命得到了更好的延长。

LEACH-X 对于阈值函数的修正会导致相比LEACH增加了多次判断与计算的过程，这可能会增加节点间通信的次数，从而使网络的总延迟增加。因此，该算法更适用于对时延要求不高的网络，限制了该算法的使用范围。

4 结论

本文基于LEACH 协议，提出了改进的LEACH-X 协议。对簇首选举阶段时的阈值函数进行改进，改进后的阈值综合考虑了最优簇首数目、邻居节点密度、剩余能量、当选过簇首的次数和到Sink 的距离，并对不同部署区域采用不同的优化参数，进行二次竞争选举，修改各因子的权重。同时，对LEACH、LEACH-Advanced、LEACH-X 进行仿真实验，结果表明LEACH-X 使簇首选举更合理，均衡了簇间能量负载，减少了网络能量消耗，有效延长了网络生命周期。