基于分区和能量距离因子的LEACH 改进协议

卞有为，张玲华

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

引 言

无线传感器网络（Wireless sensor network, WSN）是一种随机部署在某个地域范围内的自组织网络[1]。WSN 的目标是对部署区域内的目标对象的数据进行感知、采集和处理，将处理过的数据发送给基站（Base station, BS），BS 将数据呈现给监测者。WSN 具有低能耗、低价格、自组织且部署便捷的特点，在环境勘察、医疗救助和军事行动中有着广泛运用[2]。

WSN 一般部署在人员无法到达的特殊区域，例如战场、自然灾害发生时的受灾地区[3]。从部署阶段开始，传感器节点的能量补充就几乎是不可能的，这一直持续到传感器节点死亡。如何高效利用网络中的有限能量是WSN 的重要研究方向。在保持传感器节点能量不变的情况下，尽可能延长整个系统的寿命。

WSN 网络中一般有2 种节点：普通节点和Sink 节点[4]。Sink 节点一般只有1 个，它负责汇聚全网的信息，发送给监测者，一般有能量供给。除Sink 节点外为普通节点，这些传感器通过人力随机部署在需要监测的地区，位置固定，没有能量供给。

如果每一个节点都直接与Sink 节点通信，普通节点的能量会急剧衰耗，而且会发生严重的数据阻塞，降低网络的传输效率，延迟增大[5]。针对这些问题，许多学者提出了分簇的思想，节点被分成许多小集群。最初的分布式分簇算法，低功耗自适应集簇分层型协议（Low energy adaptive clustering hierarchy，LEACH），由麻省理工大学的Heinzelma 等提出，基本思想是WSN 分成若干簇子网，每簇子网中有一个簇头节点，簇头节点接收簇内节点发送来的的数据，融合后发给Sink 节点，他们定义了簇头选举阈值函数，协议采取轮流竞选簇头的方式，使网络的能量得到更好利用，网络的可工作时间得到了显著延长[6]。但是由于簇头选举的随机性，部署离Sink 节点过远的簇头容易提前耗尽能量，导致外围的节点死亡早，出现热区现象，不利于网络的生存。Younis 等[7]在LEACH 基础上提出了改进的混合节能分布式分簇协议（Hybrid energy-efficient distributed，HEED）协议，在簇头选择时考虑到节点的剩余能量，但是没有考虑到节点和Sink 的距离，簇头节点的分布不均。文献[8]中给出了LEACH-C 协议，BS 在后台决定哪些节点当选簇头，BS 了解节点的分布，优化了簇头分配，但节点和BS 频繁地交换位置和能量信息加速了网络能量消耗。文献[9]提出一种四分相低功耗自适应集簇分层型协议（Quadrature-LEACH，Q-LEACH）算法，将部署区域分区4 次，提高了网络的数据吞吐量延长网络寿命。文献[10]提出了节能低功耗自适应集簇分层型协议（Energy-efficient LEACH，EE-LEACH）算法，选择剩余能量最高的节点将数据转发给BS，有助于提供更好的数据包传递比率，减少能量的消耗。文献[11]的改进型低功耗自适应集簇分层型协议（LEACH-advance，LEACH-AD）算法，综合了节点密度和剩余能量，对簇头选举函数进行修正，但没有考虑节点的分布和距离因子，远距离的簇头耗能快。

针对以上问题，本文提出了一种基于分区和能量距离因子的LEACH 改进协议(LEACH energydistance-partition，LEACH-EDP)。在该算法中提出剩余能量因子和距离因子并计算，针对无线电衰耗模型对部署区域进行分区，采取不同的修正参数，最后对簇头选举阈值函数进行修正，有针对性地改变因子的权重，可以有效延长WSN 的生存时间。通过仿真和数据对比得出，LEACH-EDP 协议与传统LEACH 和LEACH-AD[11]相比，降低了能量消耗，延长了网络寿命，并延缓了第1 个死亡节点出现的时间。

1 系统模型

1.1 网络模型

本文对WSN 做如下的设定：

(1) 网络开始运行前，随机部署传感器节点，传感器节点无法移动，直到网络死亡。

(2) 所有节点的初始能量相同，拥有特有的身份标识（Identity document，ID）号，且拥有等效的计算、通信和融合数据的能力。

(3) Sink 节点拥有稳定的能量供应，数据处理能力不限，除外的普通节点无能量补充。

(4) 每个节点都有与Sink 节点通信的能力，可以通过感知信号的强度，计算出与发送者的距离。

1.2 能耗模型

WSN 采用一阶无线电模型的通信能耗模型如图1 所示，简单假设分为发送端和接收端，单位为J。发送节点对采集的数据进行放大和传输消耗能量，接收节点接收消耗能量。

由一阶无线电模型[8]可知，能量消耗公式如式(1),(2)所示。

发送端能耗为

图1 能耗模型Fig.1 Energy consumption model

接收端能耗为

式中，Eelec为发射电路的消耗能量，d为发送节点与接收节点之间的距离，k为数据包的大小，εmp为多径衰落损耗系数，εfs为自由空间损耗系数，d0为自由空间衰落和多径衰落的切换阈值，定义为

2 LEACH 协议

LEACH 算法是最早的分布式成簇算法，整个网络自组织成簇，每个簇只有一个簇头。LEACH 算法中为簇的选举定义了一个周期，每个节点根据阈值函数轮流竞争成为簇头，尽量避免一个节点连续当选簇头而导致能量消耗快，节点提前死亡。在一个个周期中，节点选举簇头成簇，普通节点甄选距离值最小的簇头加入簇头的小网络，将从环境中感知的信息发送给簇头，簇头融合数据再发送给BS，这样一个个周期重复下去，完成WSN 感知采集数据的任务。LEACH 算法的简要步骤如下：

(1) 每个周期开始，所有节点竞争选举簇头，每个节点随机生成一个大于0 小于1 的随机数，如果此值小于阈值函数T(n) 的值，则这个节点被选为簇头，阈值函数T(n) 定义为

式中，p为节点通过选举函数竞选成为簇头的概率，r为当前的周期数，n为节点总数，G为非簇头的节点集合。

(2) 选举上的簇头向网络广播自己的信息，普通节点选取离自己最近的簇头加入其簇网络。

(3) 建立时隙表，分配时隙，簇内节点采集处理数据后将数据发给簇头节点。

(4) 簇头接收成员发来的数据包，将融合后的数据包发给BS。

3 LEACH-EDP 协议

传统的LEACH 算法，簇头选举完全随机，对于部分距离BS 很远的簇头，这些节点可能提前耗尽能量，退出网络系统，不利于网络的整体生存。LEACH-AD[11]算法修正了簇头选举阈值函数，引入节点能量和密度因子，但是没有考虑到多径衰落的模型，远距离簇头能耗依旧很大。针对以上情况本文提出LEACH-EDP 算法。LEACH-EDP 对阈值函数依据能耗模型进行修正，提出新型剩余能量和距离因子，对部署区域进行分区，针对环境来权衡能量和距离因子的权重，在不同的区域采用不同的修正系数，能够达到延长网络寿命、降低能量损耗的目标。

3.1 能量因子

随着运行周期的不断增加，WSN 网络中所有节点拥有的能量会逐渐降低，但对于远离Sink 节点的节点，如果连续当选簇头，该节点的能量会快速下降，整个网络会出现“热区”现象，即围绕着BS 的区域中的簇头能量消耗少，远离BS 的区域中簇头能量消耗大，在外围的节点会提前死亡，外围的节点死亡过多，系统丧失对外围的数据监测，不利于网络的工作运行。针对这种情况，可以将节点的剩余能量因素引入到簇头的竞选过程中。文献[11]中LEACH-AD 协议引入了剩余能量因子，对簇头选举阈值函数(式（4）)进行修正，剩余能量因子定义为

式中，Ei为网络中第i 个节点的剩余能量，随着网络周期的不断增加，节点的能量在不断减少，可知Ei在不断减少，剩余因子Efactor在阈值函数中所占的权重会不断减少，在网络运行的后期Efactor会很小，从而失去均衡簇头的作用。为此本文提出改进的剩余能量因子Efactor，定义为

式中，Ei为第i 个节点的当前能量，Eavg为网络的节点平均能量。根据式（6）中计算得到的剩余能量因子，相比原来的因子，不会随着系统能量的减少而降低权重，且当节点i 的能量小于节点平均能量时，Efactor为负数，此节点通过阈值函数当选簇头的概率下降，使整个网络的簇头分布更加合理，延长网络的工作时间。

3.2 距离因子

文献[11]中的LEACH-AD 算法，引入了密度因子来修正簇头的竞选阈值函数，定义为

式中，R0为通信半径，kn为节点i 通信半径内的节点个数，Rj为通信半径内的节点到节点i 的距离。

由于节点随机分布在部署区域内，当某个节点周围密度过小时，Rj会很小，导致Di过大，趋于无穷值，不利于簇头选举概率的调整。随着网络运行，网络中部分节点会陆陆续续死亡，退出系统，节点密度会不断降低，Di的权重会不断减少，直到失去均衡作用。

本文LEACH-EDP 算法引入距离因子来均衡簇头的能量消耗。远离Sink 的节点消耗的能量一般大于其他节点，引入距离因子来均衡簇头选举概率。

文献[12]中提出距离因子 φ = d0di，其中d0同式（3）中的定义，di为节点到Sink 节点的距离。d0为定值，此距离因子只由di决定，当di很大或很小时，距离因子相差很大，不利于调整参数的范围，为此本文采取归一化的方法，对di进行归一化处理[13-14]，重新定义距离因子Dfactor为

式中，Dmax为全网节点和Sink 节点距离的最大值，Dmin全网节点和Sink 节点距离的最小值，Di为节点i和Sink 节点之间的距离。

如式（8）所示，距离因子经过归一化，数值被控制在0 到1 之间，当节点i 离Sink 最远时，距离因子为0，当节点i 离Sink 最近时，距离因子为1，有利于控制参数。

图2 区域分区Fig.2 Region partition

经过这样的设计，在能量因素相同的条件下，距离Sink 节点越近，有更大几率当选簇头，离Sink 节点远的节点当选的几率降低。

3.3 区域划分

由一阶无线电模型可知，节点能耗与距离d的n次方呈线性关系，尤其当发送端和接收端的距离大于d0时，节点能量的消耗量将从d的平方变成d的四次方，节点能耗极大增加，所以，针对距离大于d0的节点，按照d0为半径，Sink 为中心，将部署区域分为2 个部分，文献[15]中提出了一种分区方法，如图2 所示。

以d0为半径将部署区域分为2 部分，小于d0的区域记为Area1，大于等于d0的区域记为Area2。

根据无线电一阶模型，2 区域内簇头节点采取不同的能耗公式，所以通过分区来对2 个区域的簇头选举阈值函数进行有针对性的修正。

LEACH-AD 协议[11]采用的簇头选举阈值函数为

式中，Ei为能量因子(剩余能量)，D'为节点密度因子，α和β均为增益参数。由于LEACH-AD 没有进行分区处理，对远近簇头的优化采取同样的策略，不利于网络能量的均衡。 为解决这一问题，本文LEACH-EDP 算法采取新的簇头选举阈值函数，且针对不同区域采取不同的优化参数去修正函数，如式（10），（11）所示。

式中，T(n) 为LEACH 簇选举阈值函数；Efactor为能量因子；Dfactor为距离因子；w1，w2，w3，w4为增益参数，Area1，Area2分别为位于区域1、2 的节点集合。

新的修正函数针对不同的区域采用不同的增益参数。对于区域1 中的节点，这些节点离Sink 近，采用的是自由空间衰落能耗模型，节点能量的消耗相对多径传输较少，区域周围节点的能量相差不大，希望在修正时增大距离因子的权重，减少能量因子的权重。对于区域2 中的节点，这些节点位于部署区域的外围，采用的是多径衰落能耗模型，能耗较大，节点易提前死亡，希望在修正时增大能量因子的权重，适量减少距离因子的权重。

LEACH-EDP 算法采取分区处理，引入能量和距离因子，合理调整增益参数，有针对性地修正簇头选举阈值函数，均衡了网络能耗，有助于延长网络的寿命，延缓第一个死亡节点的出现。

3.4 LEACH-EDP 算法流程

LEACH-EDP 算法步骤如下：

(1) Sink 节点向全网广播消息，接收节点根据信号的强度计算出自己与Sink 节点之间的距离，按照式（3）划分自己所在的区域。

(2) 区域划分完成后，节点向Sink 节点汇报区域划分已完成，并交换距离和能量控制信息。Sink 节点接收汇报的控制信息，根据式（6）计算出最大最小距离、当前周期系统平均剩余能量，广播消息给其他节点。

图3 算法流程图Fig.3 Algorithm flow chart

(3) 进入簇头竞选阶段。所有普通节点收到Sink 的信息，根据式（6），（8），计算当前节点的能量因子Efactor和距离因子Dfactor。

(4) 节点生成一个大于0 小于1 的随机数rand，根据自己所在的区域，对照式（10）选取相应的阈值公式计算T ( n )，若rand 小于T ( n ) 则本周期当选簇头，广播自己是簇头的消息，否则为普通节点。

(5) 普通节点收到周围簇头的广播消息，按照信号的强弱，选取最近的簇头加入。

(6) 簇头的建立完成，进入数据传输阶段。普通节点感知环境对象的信息，处理好后发给子网里的簇头节点，簇头融合子网的数据发送给BS。

(7) 一个周期完成，重复簇头的选举，直到网络

中所有节点死亡。

算法流程图如图3 所示。

算法伪代码如下所示：

init( ); %初始化并定义各种常数参数

for i=1 to n %按照均匀分布随机部署节点S 集合

S(i)·xd=rand(1,1)*xm; % xm为 区 域x 轴 最大值

S(i)·yd=rand(1,1)*ym; %ym为区域y 轴最大值

S(i)·E=E0;%设置初始能量为E0

S(i)·type='N';%节点初始化类型为普通

end

for i=1 to n

Calculate_Dmax&Dmin&Partition( ); %计算Dmax，Dmin，每个节点的分区所属

end

for r=1 to rmax%周期总循环

for i =1 to n %簇头选举循环

Calculate_Dfactor&Efactor( ); %计算距离因子和能量因子

if (位于区域1?)

采取策略1;

elseif (位于区域2?)

采取策略2;

end

if (rand ＜Tn)

该节点标记为簇头;

else

该节点标记为普通节点;

end

end

for i =1 to n %计算普通节点能耗

if (普通节点?)

找出最近的簇头节点，加入，计算距离，按照能耗公式，计算能量消耗( )；

end

end

for i =1 to n %计算簇头节点能耗

if (簇头节点?)

计算融合数据耗能( )；

计算传输sink 的能耗( )；

end

end

Calculate_Energy&Energy_avg&Dead( ); %计算网络剩余能量，平均能量，节点死亡数

end

4 实验仿真与结果分析

本文在Matlab 2016 b 上进行仿真实验，对算法LEACH、LEACH-AD、LEACH-EDP 进行性能比较和分析。选取网络几个时间点的节点分布、网络节点剩余能量、网络节点死亡量作为性能指标进行比较。网络参数设置见表1。

表1 网络参数设置Table 1 Network parameter setting

4.1 节点分布图

本实验假设部署区域为100×100 的方形区域，节点数量为100 个，Sink 坐标为(0,0)，按照均匀分布部署在区域中，初始分布图如图4 所示。

本实验选取2 次相同时间点对3 种算法的节点活动状态进行比较，如图5 所示。3 种算法使用相同的初始节点分布，通过比较在相同时间点的分布图，可以直观判断出算法的性能。

由图5 中的节点分布可知，在周期600 时，LEACH 算法中区域外围的节点几乎已经死亡，LEACH-AD 中外围节点仍有部分节点还在活动，LEACH-EDP 算法中外围有大量节点存活；随着网络运行，在周期900 时，LEACH 中的外围节点完全死亡，LEACH-AD 中只有数个节点存活，LEACHEDP 中还有不少节点存活。这主要是因为，LEACH-EDP 算法考虑到了分区因素，在外围通过能量和距离因子来减少低能量节点成为簇头的概率，使得外围的节点存活时间延长，有利于网络的运行。

4.2 死亡节点个数

网路初始化设置节点个数为100 个。BS 位置设计位于部署区域的边缘，可以更好的测试算法在极端环境下的性能。图6 呈现了随周期数变化的网络死亡节点数。

LEACH 算法的第一个死亡节点出现在周期348；LEACH-AD 算法第一个死亡节点出现在周期377，相较LEACH延迟了8.3%；LEACH-EDP 算法第一个死亡节点出现在周期625，相较LEACH和LEACH-AD 算法分别延迟了79.5%、65.7%。

所有节点死亡则判定网络死亡。LEACH 算法的网络死亡时间在周期1 191；LEACH-AD 算法的网络死亡时间在周期1 433，相较LEACH 延迟了20.3%；LEACH-EDP 算法的网络死亡时间在1 875，相较LEACH 和LEACH-AD算法分别延迟了57.4%、30.8%。

以上分析可以得出LEACH-EDP 算法在延长网络寿命上优于LEACH 和LEACH-AD 算法，主要是因为LEACHEDP 考虑了节点能量和节点距离，针对不同的区域节点采取不同的优化参数，改变相应的因子权重来均衡网络能量，让有能量位置适合的节点作为簇头来融合数据，延缓节点死亡。

图4 初始节点分布图Fig.4 Initial node distribution map

图5 节点分布图Fig.5 Node distribution map

图6 死亡节点个数Fig.6 Number of death nodes

4.3 网络剩余能量

网络初始化设置所有普通节点能量为0.5 J，100 个普通节点，Sink 节点能量无限制，网络初始总能量为50 J。随周期变化的网络剩余能量如图7 所示。

网 络 能 量 损 耗50% 时 ，LEACH 和LEACH-AD 算 法的周期大约在300，LEACH-EDP 的周期大约为360，相较前两种算法延迟了大约20%；网络能量损耗90% 时，LEACH 算法周期为603，LEACH-AD 算法周期为631，LEACH-EDP 算法周期为758，相较前两种算法分别延迟25.7%、20.1%。

以上分析可以得出，LEACH-EDP 在均衡网络能量上要优于LEACH 和LEACH - AD 算法，主要是由于LEACH-EDP 更加合理的簇头选举，使能量没有被过度浪费，分区的作用使外围节点尽量减少使用多径衰落的能耗模型，减少外围节点的能耗，均衡整个网络的能耗。

4.4 结果分析

根据以上的实验结果，可以证明LEACH-EDP 协议在网络生存时间、能量消耗上要优于LEACH 和LEACHAD 协议。

从簇头成簇的机理上分析，LEACH 没有对能量和距离加以考虑，簇头的选举完全随机，在区域边缘的节点能量消耗本就较大，相比中心地域的节点能量提前耗尽，节点死亡，网络探测失去作用。LEACH-AD 考虑了能量和密度但是效果并不明显。LEACH-EDP 通过能量和距离因子优化了传统簇头选举函数的不合理性，使有能量且位置合理的节点更可能当选，减少了某些簇头节点能耗过大情况的出现，分区策略调整了不同因子的权重，减少能量热区的出现。

但考虑到LEACH-EDP 对于簇头选举函数的修正可能导致相比LEACH 增加了平均簇头个数，在一般相同周期中，对于外围的节点仍有存活，一般节点会继续寻找簇头并成簇，这可能增加了节点间通信的次数，使网络的总延迟增加。

图7 网络剩余能量Fig.7 Network residual energy

5 结束语

本文针对LEACH 协议和LEACH-AD 提出改进的LEACH-EDP 协议。LEACH-EDP 协议采取了分区策略，对不同部署区域采取不同的优化方式来均衡权重因子，对于簇头选举阈值函数使用能量和距离因子来修正。同时对LEACH、LEACH-AD、LEACH-EDP 进行仿真对比，实验结果表明LEACHEDP 延长了网络的工作时间，延缓了第一个死亡节点的出现时间、更高效地利用了网络能量。