基于最低能耗的改进LEACH分簇算法

孙文胜+朱为佳+苗红亮

摘要：针对LEACH（Low Energy Adaptive Clustering Hierarchy）算法中的随机分簇和簇头能耗不均问题，提出一种基于最低能耗的改进LEACH分簇算法MEC-LEACH（Minimum Energy Consumption based LEACH）。MEC-LEACH分簇算法通过最小化网络能耗得出最优簇头数，同时引入簇头的剩余能量和簇头距离sink节点的远近等因素综合选举簇头节点，使得剩余能量较大且距离sink较近的节点优先成为簇头节点，进而均衡簇头节点和网络总的能耗。仿真实验表明，MEC-LEACH算法相比其它改進算法可以有效降低网络能耗，延长网络生存时间。

关键词：LEACH协议；随机分簇；最低能耗；剩余能量；网络生存时间DOI：10.11907/rjdk.162713中图分类号：TP312文献标识码：A

文章编号：16727800（2017）004004405

0引言 无线传感器网络（Wireless Sensor Networks，WSN）[1]是由大量微型传感器节点自组织和自适应形成的通信网络，网络内的传感器节点自身具有感知、存储和处理数据的能力，可以将感知数据通过无线方式发送给用户。近年来，随着微机电系统、片上系统、无线通信和低功耗嵌入式技术的飞速发展，WSN受到越来越多的关注，其在军事国防、智能家居、环境监测以及医疗等领域广泛应用。但是无线传感器网络的节点能量有限且不易进行实时更换，这使得如何更高效地利用有限的节点能量延长网络寿命，成为WSN中非常重要的设计目标。 分簇的网络结构可以方便地进行节点管理、资源分配以及负载均衡，所以分簇算法往往被用来进行优化无线传感器网络的能量消耗。其中最经典的分簇算法是Heinzelman等[2]提出的LEACH算法，相比于没有分簇的网络，LEACH算法可以延长网络寿命15%左右。但是，由于LEACH算法采用随机选择簇头机制，容易出现簇头节点过早死亡，从而导致网络能量消耗不均，降低了网络性能。 针对LEACH算法的不足，很多学者提出了新的算法以改进和提高LEACH算法的性能。文献[3]提出的LEACH-C算法采用sink节点统一管理网络节点和分簇的策略，并且根据节点剩余能量进行簇头选择，有效均衡了网络能耗，但是簇头选择机制只单纯考虑了节点的剩余能量会导致距离sink较远的节点成为簇头，加重了簇头的能耗。文献[4]研究了LEACH-C算法，提出改进后的pLEACH算法，pLEACH采用最优簇头思想等分圆形网络区域，每个区域内再进行簇头选举，下一轮选举簇头时，网络旋转一定角度形成新的分簇区域，有效避免了簇头节点集中在某一处的问题，但是依然存在簇头距离sink较远的问题。文献[5]中的EH-LEACH算法同样采用了最优簇头的思想，将网络划分为一个个网格，每个网格为一个簇，并且选择簇头时考虑了节点的剩余能量，有效均衡了网络能耗，但是该算法中最优簇头的划分没有考虑网络实时变化的因素，随着网络运行，最初的最优状态可能并非最优。文献[6]、[7]针对LEACH算法均是改进其选举簇头时的阈值，考虑了节点的剩余能量，而并没有考虑最优簇头以及簇头距离sink的距离。文献[8]提出的改进LEACH算法虽然选择簇头时考虑了节点的剩余能量以及节点位置信息，但没有考虑网络能耗决定的最优簇头的影响，一定程度上增加了网络能耗。文献[9]提出的M-LEACH算法根据网络能耗确定最优簇头，选择簇头时基于节点的剩余能量和上一轮节点消耗的能量来进行选举，该算法在一定程度上均衡了网络能耗，但是确定最优簇头时只考虑了簇头稳定传输阶段的能耗，并没有考虑簇头形成阶段的能耗，以及簇头距离sink的距离等因素，网络能耗还可以进一步降低。 本文在以上研究的基础上，针对LEACH算法的随机分簇和网络能耗不均问题提出基于最低能耗的改进LEACH分簇算法MEC-LEACH（Minimum Energy Consumption based LEACH）算法，利用最小化网络能耗决定网络分簇数，进而根据最优簇头概率以及簇头的剩余能量和簇头距离sink的远近来选择簇头节点，使得簇头能耗更加均衡，从而降低整个网络的能耗，延长网络寿命。

1LEACH算法 1.1算法流程简述 LEACH算法采用了“轮”的方式进行簇头的重新选择。每一“轮”运行过程主要分为两个阶段完成，分别为簇的形成阶段和稳定传输阶段[10]。在簇的形成阶段，每个传感器节点产生一个[0～1]之间的随机数，如果产生的随机数小于给定的阈值T（n），该传感器节点则广播成为簇头节点的消息，其它节点根据接收到成为簇头节点消息的强弱判断自己加入哪一个簇，并发送加入簇的请求消息至簇头，簇头接收普通节点的加入请求后，按照时分复用为每一个簇内的节点划分特定的时隙，再将时隙表广播至簇内的成员节点。簇内成员接收时隙表消息，在指定的时隙内发送数据给簇头节点。至此，簇的形成阶段完成。其中选择簇头时给定的阈值T（n）表达式如下：其中，p为簇头占节点总数的比例，n为节点个数，r为当前网络运行的轮数，G为最近轮内没有当过簇头的传感器节点集合。LEACH算法中，所有簇形成后，网络开始进入稳定传输阶段。簇内成员节点根据簇头分配的TDMA时隙，完成数据采集以及将数据发送给簇头节点。如果当前节点的时隙尚未到来，节点可以暂时关闭发送数据模块，进入睡眠状态，需要发送数据时再打开。簇头节点则在一轮运行时间结束前，一直处于接收数据状态。为了防止簇间干扰，每个簇内使用唯一的CDMA扩展编码进行通信。当簇头完成簇内成员数据的采集后将其与自身的数据融合并统一发送给sink节点，sink节点接收所有簇头节点的数据后再发送至用户，接着运行下一轮的过程[11]。

1.2算法能耗模型LEACH算法能耗主要来自两个部分，分别为节点接收数据的能耗和发送数据的能耗。其中传感器节点发送Lbit数据的能耗如下式所示[12]：式中，Eelec为无线电收发单位比特数据能耗系数；参数εfs和εmp分别表示自由空间能耗和多径衰落能耗中的功率放大系数；d为源节点与目的节点间的距离，d0决定了传输模型，如果节点传输距离超过d0，则传输能耗采用多径衰落，能耗与距离的四次方成正比，反之则采用自由空间模型，能耗与距离的平方成正比。d0可由如下公式得到：

1.3算法不足LEACH算法采用“轮”的思想，并且产生随机数的方式，使得所有传感器节点成为簇头的概率相同，可以有效均衡能量消耗。但是LEACH算法仍然存在以下不足：（1）随机产生的簇头节点可能出现节点剩余能量较低，由于簇头本身需要完成更多较普通节点的任务，所以较低的能量会导致该簇头过早死亡，同时如果距离sink节点较远的节点成为簇头时，远距离的数据传输同样加重了簇头的能耗，加速了节点死亡，从而降低了网络生存时间。（2）不同的网络规模下，分簇的数量应根据网络规模进行自适应调整。如果分簇过少，则会出现每个簇过大，簇内成员过多，簇头节点无法完成过多的数据处理，造成信息传输效率降低。分簇过多时，簇头节点过多，则出现网络大部分数据传输都是单跳的，这样失去传感器网络多跳的优势，不能达到延长网络寿命的目的。〖BT1〗〖STHZ〗〖WTHZ〗2MEC-LEACH算法针对以上不足，本文提出基于最低能耗改进LEACH的MEC-LEACH算法，利用最小化网络能耗得出最优簇头数量，然后均衡最优簇头概率、节点剩余能量以及节点距离sink的距离来选择簇头节点。MEC-LEACH同样分为簇的形成阶段和稳定传输阶段。

2.1簇的形成阶段 2.1.1最优簇头数量本文根据最小化网络能耗来计算最优簇头数，其中网络能耗由簇的形成阶段能耗与稳定传输阶段能耗组成。假设在M×M的网络区域内均匀分布n个传感器节点，网络分成k个簇，每个簇由一个簇头节点和SX（nkSX）-1个普通节点组成。网络传输能耗模型与LEACH算法相同，设传输数据为Lbit。在簇的形成阶段，网络的主要能耗来自3个部分，分别为：节点宣告成为簇头消息的能耗、普通节点加入簇内以及簇头分配TDMA时隙的能耗。其中簇头节点的主要能耗包含：开始广播簇头消息的能耗、接收簇内节点加入簇的能耗和广播TDMA时隙的能耗。根据公式（2）可以得出该阶段簇头的总能耗为：式中，d为簇头广播的距离，因为全网广播，所以采用多径衰落传输模型。dtoCH为簇内节点到簇头的距离。在该阶段簇内普通节点的能耗主要包含：接收簇头广播消息的能耗、发送加入簇的消息能耗和接收TDMA时隙的能耗。所以得到的能耗如下：稳定传输阶段，主要能耗来源于簇头数据收集和普通节点数据采集，以及簇头数据融合和发送数据给sink节点。其中簇头节点在稳定传输的每一帧能耗为：接收感知数据的能耗、融合数据的能耗以及发送数据至sink节点的能耗。所以可以得到总能耗为如下公式所示：其中，EDA为簇头融合单位比特数据的能耗，dtoBS为簇头到sink的距离，本文假设sink距离较远，采用多径传输。簇内普通节点在稳定传输阶段每一帧能耗主要来自发送数据给簇头节点，可以得出所有普通节点在稳定传输阶段的能耗如下：

2.2稳定传输阶段在稳定传输阶段，簇内成员节点根据自身的TDMA时隙，在指定时间内发送自身感知数据以及自身ID和当前剩余能量给簇头节点，簇头收集完簇内成员的剩余能量以及成员的數据信息后，再将融合后的数据进一步发送至sink节点，sink节点根据最新的全网剩余能量可以计算出当前的最佳分簇和最优簇头概率，选择新一轮簇头时，再将该信息广播至全网。其它节点再根据自身能量选举簇头，以进入新的一轮网络循环运行。综上，MEC-LEACH算法的流程如图1所示。

3仿真结果与分析

3.1仿真环境与参数设定为了验证MEC-LEACH算法的有效性，本文采用Matlab仿真平台对本文算法与文献[5]EH-LEACH算法以及文献[9]中的改进LEACH算法进行了仿真和对比。分别从网络生存时间、网络总能耗以及sink接收数据量等方面进行分析和比较。实验网络环境假设为：在100m100m的正方形区域内均匀分布100个传感器节点，节点均为同构的且具有GPS定位装置。Sink节点位于网络外固定位置。表1为实验参数设定。3.2实验结果分析

3.2.1权重因子λ取值〖JP2〗MEC-LEACH算法簇头节点选择时需要考虑节点的剩余能量以及簇头距离sink的远近占簇头选举的比重，所以实验中分别对权重因子取不同值分析其对网络寿命以及网络能耗的影响，从而确定一个最优值。由式（16）中λ取值范围，分别对权重因子取值：0、0.1、0.2、0.3、0.4、0.5、0.6、0.7、0.8、0.9、1.0。实验结果如图2、图3所示。

可以看出，随着权重因子λ的增加，网络的存活时间逐渐延长，网络能耗逐渐降低，当λ=0.6时，网络总能耗最低并且网络存活时间最长。此后λ逐渐增大，网络存活时间下降而网络能耗也随之增加，可见权重因子取值0.6时，即选择簇头时节点的剩余能量占比60%，簇头与sink的距离占比40%时，网络性能相对最佳，寿命更长。下面分别对当λ取值0.6时，本文MEC-LEACH算法与其它的改进LEACH算法进行算法性能比较。3.2.2网络生存时间网络生存时间直接关系到网络性能好坏，本文借助统计网络内每隔一段时间存活的节点数目来衡量网络生存时间长短。3种算法的网络生存时间如图4所示。

可以看出，3种算法中，本文分簇算法最迟出现死亡节点并且网络生存时间最长，大约为1600s，相比EH-LEACH算法1200s和文献[9]的算法1350s，分别提升了约33%和19%。这主要因为，EH-LEACH算法和文献[9]的算法均没有考虑网络实时变化导致最优簇头的变化，导致网络分簇不均，簇头节点能耗不均衡。文献[9]虽然相比EH-LEACH算法在选择簇头时考虑了簇头上一轮消耗的能量，但没有考虑最优分簇以及簇头距离sink的远近，所以其相比EH-LEACH算法，网络生存时间提升并不明显，仍然没有本文的分簇算法生存时间长。3.2.3网络能耗网络系统总的能量消耗，可以衡量系统性能好坏以及网络能量消耗均衡性。3种算法对应的网络总能耗如图5所示。从图5可以看出，3种算法中，本文分簇算法网络总能耗最少，其次是文献[9]算法，EH-LEACH算法能耗最多。EH-LEACH算法中网络簇头个数始终不变，这样导致网络运行后期，有的簇内可能剩下的都是剩余能量较低的节点，加剧了节点死亡，增加了网络能耗。文献[9]同样没有考虑网络运行过程中簇头数变化的影响，同时簇头选择时没有考虑簇头距离sink的远近，距离sink较远的簇头能耗增加，导致其网络总能耗的增加。本文分簇算法由最小化网络能耗得到最优簇头，以及选择簇头时综合考虑节点剩余能量和簇头距离sink的远近，可以有效降低和均衡网络能耗。

3.2.4sink接收数据量通过对sink接收数据量分析，可以直观显示出网络的传输效率，进而衡量网络性能的好坏。3种算法的sink接收数据量如图6所示。

从图6可以看出，由于其它两种算法选择簇头节点时均没有考虑簇头距离sink 的远近因素，可能会出现距离sink较远的节点成为簇头节点，这样增加了簇头发送数据的能耗，以及发送数据的时间。所以相同时间内，EH-LEACH算法和文献[9]算法sink接收数据量均没有本文分簇算法多。此外，由于能耗不均，导致网络生存时间降低，相同时间内，本文分簇算法存活节点更多，发送数据越多，sink节点接收的数据也越多。网络运行至1600s左右时，本文分簇算法中sink共接收约203 000数据包，相比EH-LEACH算法（约137 000）和文献[9]的算法（约CM152 000），分别提升了48%和34%。

4结语 本文在分析LEACH算法的基础上，针对其随机分簇和簇头能耗不均的问题，通过最小化网络能耗来得到最优的分簇个数。在簇头节点选择上，考虑了最优簇头概率、簇头节点的剩余能量以及簇头与sink节点间的距离，使得剩余能量较高、距离sink较近的节点更容易成为簇头节点。仿真实验表明，相比其它的改进LEACH算法，本文提出的MEC-LEACH算法可以有效延长网络生存时间，降低和均衡网络能耗，提高网络sink节点接收数据量，进而提升网络性能。

参考文献：[1]李晓维.无线传感器网络技术[M].北京：北京理工大学出版社，2007.

[2]HEINZELMAN，RABINER W，CHANDRAKASAN，et al.Energyefficient communication protocol for wireless microsensor networks[J].Adhoc & Sensor Wireless Networks，2000（18）：1520.

[3]HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An applicationspecific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660670.

[4]GOU H，YOO Y.An energy balancing LEACH algorithm for wireless sensor networks[C].International Conference on Information Technology：New Generations，Itng 2010，Las Vegas，Nevada，Usa，2010：822827.

[5]PITHVA B，PATTANI K，CHRISTIAN A.Optimization of leach protocol in wireless sensor network[J].International Journal of Computer Applications，2014，93（12）：9758887.[6]王臻躍.基于LEACH的改进路由协议[J].软件导刊，2015（3）：114116.

[7]吴标，余剑，易仁杰.基于节点剩余能量的分时分簇LEACH改进算法[J].火力与指挥控制，2016，41（10）.

[8]余成波，邓顺华，方军，等.基于节点位置与剩余能量的LEACH协议优化[J].传感器与微系统，2016，35（5）：139141.

[9]谭军.簇首选择改进的 LEACH 无线传感器路由协议[J].计算机应用与软件，2015（6）：171173.

[10]〖ZK（#〗郑增威，吴朝晖.若干无线传感器网络路由协议比较研究[J].计算机工程与设计，2003，24（9）：2831.

[11]GIRGIRI A，AMINUBABA M，ALI L G，et al.Minimising energy consumption in wireless sensor network by enhancement of LEACH protocol[J].International Journal of Computer Science & Management Studies，2015.

[12]刘明，龚海刚，毛莺池，等.高效节能的传感器网络数据收集和聚合协议[J].软件学报，2005，16（12）：21062116.

（责任编辑：陈福时）