无线传感器网络路由优化中的能量均衡LEACH改进算法

何书前 严晨 邓正杰 石春

摘  要： 详细分析了LEACH算法，并介绍了LEACH算法的优缺点。针对LEACH算法选择簇头没有考虑剩余能量，提出一种改进后的算法LEACH?N。主要节点利用剩余能量和特定范围内相邻节点数的不同，给予不同成为簇头的概率;同时，增加普通节点可以直接发送数据到汇聚节点（Sink），减少能量的消耗。仿真结果表明，与传统LEACH算法相比，LEACH?N算法能均衡节点能量消耗，延长网络的生命周期。

关键词： 改进的LEACH算法; 无线传感器网络; 路由协议; 算法分析; 能量均衡; 能耗减少

中图分类号： TN919?34                         文獻标识码： A                          文章编号： 1004?373X（2020）05?0006?04

Improved LEACH algorithm based on energy balance in route optimization

of wireless sensor networks

HE Shuqian， YAN Chen， DENG Zhengjie， SHI Chun

（School of Information Science and Technology， Hainan Normal University， Haikou 571158， China）

Abstract： The LEACH algorithm is analyzed in detail， including its advantages and disadvantages. As the LEACH algorithm fails to take into account the residual energy in the selection of cluster head， an improved algorithm LEACH?N is proposed. It can get the main nodes′ different probabilities in becoming cluster heads  according to the different remaining energy and the number of adjacent nodes in specific scope，. Meanwhile， common nodes are added， which can send data directly to the aggregation node （Sink） to reduce the energy consumption. The simulation results show that， in comparison with the traditional LEACH algorithm， the LEACH?N algorithm can balance the energy consumption of the nodes， and prolong the network life cycle.

Keywords： improved LEACH algorithm; WSN; routing protocol; algorithm analysis; energy balance; energy consumption reduction

0  引  言

如何在网络节点能量受限的条件下，通过网络协议有效保证整个网络的生命周期和传输数据量，一直是无线传感器网络（Wireless Sensor Networks，WSNs）研究的热点问题[1]。LEACH协议[2]作为WSNs能量有效分簇路由选择协议的代表，在分层次无线传感器路由协议应用中得到了很高的关注，并在其基础上发展了很多路由协议，如EEHC[3]，HEED[4]，DEEC[5]等。

与传统WSNs路由协议相比，LEACH协议节省了能量，延长了网络的生命周期，但也存在一定的缺陷。例如，在簇头选择时，只考虑节点成为簇头的概率，未考虑节点剩余能量、消耗能量和传输距离等重要影响因素，导致剩余能量较少的节选为簇头而造成缩短网络生命周期的问题。针对LEACH协议存在的问题，近年来，很多文献[5?10]提出了很多解决方案，文献[5]利用仿射传播聚类解决均衡分簇问题;文献[6?9]则引入相应的影响因素，改变分簇阈值，达到改善分簇质量的目的;文献[10?11]则将LEACH协议扩展至多跳环境，利用聚类的方法进行簇头节点选择，并结合最小传输能量（Minimum Transmission Energy，MTE）协议，大大延长了生命周期。针对该问题，本文引入簇内节点剩余能量消耗不均衡因素，如剩余能量、相邻节点数量和传输距离等因素，提出了一种改进的LEACH算法，因引入更加合理的剩余能量因素和节点数据传输机制，显著降低了簇头节点的能耗，有效延长了网络的生命周期和网络数据吞吐量。

1  LEACH算法概述

LEACH协议具有周期性运行过程，每轮周期由初始化和稳定两个阶段组成，每轮则分为簇建立和数据传输两个步骤。在簇建立阶段，相邻节点动态成簇，并以固定规则来选择簇头。成簇之后，簇内节点先将数据汇聚给簇头，由簇头将数据融合后转发给汇聚节点（Sink）;在数据传输中有调度机制，为节点分配时隙进行数据传输。为节约频繁的分簇造成的资源消耗，每轮的数据传输时间需大于簇建立的时间。具体算法流程如下：

1） 簇建立。每个节点随机生成一个0～1之间的随机数，若该节点在上一轮未选为簇头，且随机数小于设定的阈值[T（n）]，则该节点在此轮成为簇头。如果该节点在上一轮已经当选过簇头，则该节点不再当选为簇头。[T（n）]计算如式（1）所示：

[T（n）=p1-prmod（1p），     n∈G0，     其他] （1）

式中：[p]为簇头节点数目占总节点数的比例;[r]为当前轮数;[G]为在最近的[1p]轮中未当选簇头的节点集合。

所有簇头节点确定后，簇头节点向其他所有节点广播当前簇头的消息，其他节点根据接收信号的强弱，判定传输距离大小，以此选择加入哪个簇;节点发送加入簇请求成为簇成员，簇头根据成员节点的信息，控制協调簇的数据传输，形成TDMA时间表。

2） 数据传输。簇内所有节点将采集的数据传输给簇头节点，簇头保持在线状态，接收完所有其他节点数据后，进行数据融合减少数据冗余，再把整个簇的数据发送到Sink节点。数据传输过程是以帧的方式实现，每帧分配相应的时隙给簇内的节点[2]。

2  改进的LEACH算法

针对LEACH算法的不足，本文对LEACH算法的簇头选择和数据传输进行了改进。改进的LEACH算法采用了与LEACH算法相同的网络模型，针对LEACH算法没有考虑节点剩余能量和位置的不足，改进了LEACH算法簇头选择方法（简称为LEACH?N），主要依据各节点特定范围内的节点数和节点的剩余能量，得到节点成为簇头的概率。与WSNs的实际情况相符，提高簇的生成质量，从而减少WSNs的能耗，以延长WSNs的生命周期。

LEACH?N算法的基本思想是：根据当前节点特定范围内的节点数、剩余能量和汇聚发送能量消耗为主要因素选取簇头;再引入节点与簇头之间的距离进行分簇，成簇后进行数据传输时，考虑普通节点到Sink节点之间的距离，在限定的短距离范围内，制定节点直接传输数据至汇聚节点，进一步节省能量消耗，提高数据传输效率。

LEACH?N算法流程如图1所示，具体步骤如下：

1） 每一个节点计算与其他节点距离小于[d0]的节点数[a]，[d0]的计算公式如下：

[d0=EfsEmp]  （2）

式中：[Efs]表示自由空间信道模型信号放大器功耗;[Emp]表示多路径衰减信道模型信号放大器功耗。

2） 计算节点剩余能量[El]。

3） 节点根据剩余能量和特定范围内的节点数计算出各个节点可成为新的簇头节点的阈值，阈值计算公式为：

[T（n）=pi1-pirmod（1pi）?ElE0，n∈G0，      其他] （3）

式中：[pi=p?an]，[p]为整个网络中簇头节点占总节点数[n]的比例;[E0]为节点的初始能量;[G]代表在上一轮[r-1]中未当选簇头的节点集合，[r]是WSNs进行的轮数;[rmod（1pi）]为一轮循环中当选过簇头的传感器节点个数。

4） 节点会产生一个[0，1]的随机数。如果随机数小于这个阈值[T（n）]，则该节点成为簇头。

5） 所有簇头选择完成之后，广播所有簇头节点位置信息，剩余的普通节点选择距离最近的簇头入簇，并将自己的标识记为该簇头的标识号。

6） 所有节点入簇完成，转为数据传输阶段，簇内的普通节点比较到簇头和Sink节点的距离，若到Sink节点的距离更小，则直接传输数据到Sink节点，减少能量的消耗。

7） 簇头节点接收簇内非簇头节点的数据，通过计算、融合后将数据发送给Sink节点。该阶段运行一轮后，进入下一轮，转至步骤2），计算剩余能量[El]。

3  仿真实验与分析

3.1  LEACH?N算法仿真实验环境设置

仿真实验采用Matlab作为实验平台，对经典的LEACH算法、LEACH?N算法和Combine LEACH & MTE算法[10]进行仿真实验比较。仿真的能量模型采用Heinzelman等人提出的无线通信模型[11]，节点的模型使用一阶无线通信模型（First Order Radio Model，FORM）。在该模型中，节点在距离[d]上传输[k] bit时，若传输距离小于等于[d0]，采用自由空间模型;当传输距离大于[d0]时，采用多路径衰减模型。

节点发送[k] bit数据到Sink节点的能耗计算公式如下：

[ETx to BS（k，d）=（ETx+EDA）?k+Emp?k?d4，d>d0（ETx+EDA）?k+Efs?k?d2，d≤d0] （4）

节点发送[k] bit数据到簇头的能耗计算公式如下：

[ETx to CS（k，d）=ETx?k+Emp?k?d4，d>d0ETx?k+Efs?k?d2，d≤d0] （5）

簇头接收和融合[k] bit数据的能耗计算公式如下：

[ERx（k，d）=（ETx+EDA）?k] （6）

式中：[ETx]为发射1 bit数据损耗的能量;[ERx]为接收融合1 bit数据损耗的能量;[EDA]为数据聚焦单位数据的能量;[d]为数据传输的距离。

仿真网络中有100个节点且随机地分布在100 m×100 m范围内，Sink节点的位置固定，每个节点的初始能量为0.5 J，仿真参数如表1所示。

图2中的Combine LEACH & MTE仿真图形是Mounir Arioua等人[11]提出的一种结合LEACH和MTE协议的算法，从图2中可以看出，LEACH?N算法比Combine LEACH & MTE生命周期长，因为LEACH?N算法考虑了节点剩余能量，而Combine LEACH & MTE没有考虑剩余能量。但是LEACH?N算法的不足是适用于规模小的网络，但是Combine LEACH & MTE可以采用不同类型的WSNs。

从图2中可以得到LEACH算法和LEACH?N算法生命周期的比较，如表2所示。从表2中可以看出，随着网络的运行，改进算法的效率不断提高。因为随着节点的不断死亡，网络区域中簇头覆盖范围要更大，原始的LEACH算法选择簇头在节点稀疏的概率越大，而LEACH?N算法中簇头的选择考虑特定范围内相邻节点数，从而在节点更密集的区域选择簇头，也说明 LEACH?N算法在长时间的网络运行能耗的节省更加明显。

3.2.2  Sink节点接收数据量

两种算法Sink点接收数据的关系多少比较如图3所示。图3中两条曲线，LEACH算法在不到1 500多轮时数据量已经不再变化，而LEACH?N算法则到了2 000多轮，而且LEACH?N的数据量是LEACH算法20多倍，得到这个结果一方面因为网络生命周期的延长，从而网络整体发送数据更多了;另一方面是在数据传输阶段增加了簇内普通节点，距离Sink点更近，将数据直接传输给Sink节点。所以LEACH?N算法在整体上比LEACH算法更加优化。

3.2.3  网络剩余能量

两种算法网络剩余能量与时间关系如图4所示。从图4中可以得到，在轮数相同的情况下，LEACH?N算法中的网络剩余能量比LEACH算法网络剩余能量多，说明LEACH?N算法可以更好地平衡网络中节点的能耗，节省网络能量，延长网络的生命周期。

4  结  语

本文针对LEACH算法的不足，提出了LEACH?N算法，进行了相应的仿真实验比较，实验结果表明，改进后的算法延长了WSNs的生命周期。本文提出的LEACH?N算法在簇头选举和数据传输方式上进行改进。选择簇头时，考虑节点能量状况和特定范围内相邻的节点数;传输数据中，簇内普通节点距离Sink节点更近时，直接与Sink节点通信。仿真实验结果显示，LEACH?N算法使节点的能量消耗更加平衡。LEACH?N算法也有如下不足之处：簇头的选择没有充分考虑是否会在边缘区域，会造成簇头与Sink点长距离的通信;LEACH?N算法中的簇头节点与Sink点采用单跳通信，所以适用于小规模网络，如果网络监测区域大，会使簇头节点能量消耗较快。

参考文献

[1] LIU Xuxun. A survey on clustering routing protocols in wireless sensor networks [J]. Sensors， 2012， 12（8）： 11113?11153.

[2] SINGH A P， SHARMA N， ROY N R， et al. Residual energy and distance based energy?efficient communication protocol for wireless sensor network [J]. International journal of computer applications， 2013， 74（12）： 11?16.

[3] GUAN Xin， WU Huayang， BI Degang. EEHCA： An energy?efficient hierarchical clustering algorithm for wireless sensor networks [J]. Information technology journal， 2008， 7（2）： 245?252.

[4] CHAN T J， CHEN C M， HUANG Y F， et al. Optimal cluster number selection in ad?hoc wireless sensor networks [J]. WSEAS transactions on communications， 2008， 7（8）： 837?846.

[5] SOHN I， LEE J H， LEE S H. Low?energy adaptive clustering hierarchy using affinity propagation for wireless sensor networks [J]. IEEE communications letters， 2016， 20（3）： 558?561.

[6] MITTAL N， SINGH U， SOHI B S. A stable energy efficient clustering protocol for wireless sensor networks [J]. Wireless networks， 2017， 23（6）： 1809?1821.

[7] 徐佳，冯鑫，杨富贵，等.最大化最小能耗概率的移动Sink无线传感器网络数据收集方法[J].电子学报，2015，43（12）：2470?2475.

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

[8] 刘云翔，张伟.矿井无线通信网络中LEACH协议的改进[J].现代电子技术，2017，40（9）：66?69.

[9] LINDSEY S， RAGHAVENDRA C S. PEGASIS： Power?efficient gathering in sensor information systems [C]// Proceedings of the IEEE Aerospace Conference. Big Sky， Montana： IEEE， 2002： 3， 1125?1130.

[10] 孔国利，苏玉.基于扇形分簇的无线传感器网络路由算法[J].现代电子技术，2017，40（5）：22?26.

[11] ARIOUA M， ASSARI Y E， EZZAZI I， et al. Multi?hop cluster based routing approach for wireless sensor networks [C]// The 6th International Conference on Sustainable Energy Information Technology. Madrid， Spain： Elsevier， 2016： 584?591.