基于LEACH算法的簇首均衡算法

郑安达

摘要：针对LEACH算法中存在簇首密度分布不均衡的问题，该文提出了一种改进的LEACH算法。该文算法通过选举备用簇首的方式平衡簇首，首先根据簇首选举区域内的节点和簇首个数计算簇首密度以确定是否选举备用簇首，然后通过选举备用簇首作为下一轮簇首的方式减少网络选举簇首的轮数以及均衡网络簇首分布。仿真实验表明，该文算法与LEACH算法相比，在延长网络寿命和降低网络能量消耗方面有显著提升。

关键词：无线传感器网络；LEACH算法；备用簇首；簇首选举；网络寿命

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）04-0252-02

Cluster Head Equalization Algorithm Based on LEACH Algorithm

ZHENG An-da

（School of Information Engineering， Jiangxi University of Science and Technology， Ganzhou 341000，China）

Abstract：Aiming at the problem of the cluster head density is not balanced in LEACH algorithm，this paper proposes an improved LEACH algorithm.The algorithm first calculates the cluster head density according to the number of nodes and the number of cluster heads in the cluster head election area to determine whether to elect the standby cluster head，and reduces the number of cluster head election and the balanced network cluster head distribution by electing the standby cluster head as the next round cluster head.Simulation results show that the proposed algorithm improves the network lifetime and reduces the network energy consumption significantly compared with the LEACH algorithm.

Key words： wireless sensor networks；LEACH algorithm；spare cluster head；cluster head election；network lifetime

無线传感器网络（Wireless Sensor Network，WSN）是一种综合了传感器技术、无线通信技术、嵌入式、计算机技术等先进技术的网络结构[1]，通常用于环境监测、军事领域、医疗护理、航空航天等领域。由于无线传感器网络节点体积小，通常被部署于环境复杂的地点，不容易更换电池，因此如何降低网络的能量消耗成为国内外科研机构和学者研究的热点[2-3]。

设计高效的路由算法是降低网络能量消耗和延长网络寿命的有效方法。目前主流的无线传感器网络路由算法可分为两类，一类是分簇路由算法，另一类是平面路由算法[4]。由于平面路算法存在自组织工作复杂，无网络管理节点等缺点，逐渐被分簇路由算法取代。其中LEACH算法[5]是最早被提出来的一种分簇路由算法。LEACH算法引入了轮的概念，以循环方式随机选举簇首，尽可能的使每个节点都能均衡地被选为簇首。许多路由算法都是基于LEACH算法的改进，如LEACH-M算法[6]、Q-LEACH算法[7]、NPCHS-LEACH[8]算法等。

本文提出了一种改进的LEACH算法，本文算法通过引入簇首密度，选举备用簇首的方式以平衡簇首选举，达到均衡网络能量消耗和延长网络寿命的目的。

1 LEACH算法

LEACH算法核心思想是引入轮的概念，通过循环方式进行周期性选举簇首，选举分为两个过程，第一个过程为簇首的选举过程，第二个过程为数据传输过程，当这两个过程完成后作为一个周期的完成。一个周期完成后网络进入下一轮循环，网络通过这种周期循环来选举簇首，平衡网络的能量消耗。

在簇首选举过程，网络中的节点随机生成一个0到1的数，通过随机数与阈值比较来判断本轮是否成为簇首，如果该节点生成的随机数小于阈值，则该节点被选为簇首。阈值为：

（1）

式中为簇首百分比，为目前进行的轮数，为最后轮中没有被选为簇首的节点集合。没有被选中的的节点根据簇首的广播信号强度大小决定加入的簇，并发送入簇请求。簇首收到入簇请求后建立路由列表，并将路由列表发送给列表中的节点。

LEACH算法可以使网络中的节点尽可能平等地被选为簇首，平衡网络能量消耗，防止在选举中某些节点成为簇首的次数过多或者过少而影响网络的稳定性，但是该算法也存在一些不足。由于LEACH算法的簇首选举在生成0到1之间的数字时是随机的，会出现簇首密度过大的情况，簇头密度过大导致网络能量不必要的消耗，增加网络能量消耗，导致网络过快死亡。

2 LEACH算法的改进

本文针对LEACH算法中存在簇首密度不均衡的问题进行了改进，引入簇首密度因素，对簇首密度过大的区域采用选举备用簇首的策略，减少簇首选举的轮数和均衡簇首密度，从而降低网络能量的消耗。改进后的算法运行周期和LEACH算法一样，也分为两个过程，包括簇的选举过程和数据传输过程。

2.1 簇首选举

为保证网络簇首选举合理分配，在簇首选举过程中，网络中的节点首先根据式（1）选举簇首，节点通过随机产生0到1之间的数字与阈值比较，如果小于阈值，则被选为簇首。簇首选举完成后对自身转发范围内的簇首密度进行密度计算。计算式为：

（2）

式中为转发范围内节点的总数，为簇首转发范围内簇首总数，当簇首密度且时，本文算法认为簇首密度过大，对簇首进行均衡，从多余簇首中选举备用簇首。

在选举备用簇首时，源簇首首先向转发范围内的邻居簇首发送请求，邻居簇首收到请求反馈本簇首的剩余能量信息，源簇首在收到剩余能量后對能量大小进行对比，并将能量较大的簇首选为备用簇首，将备用簇首的信息发送给路由列表内的所有节点和簇首。当本周期结束后，该区域不再进行簇首选举，此时备用簇首开始工作并作为下一周期簇首。

2.2 数据传输

网络数据传输过程与LEACH算法数据传输过程类似，簇内节点通过TDMA时间列表向簇首发送数据。簇首在向基站发送数据之前先侦听信道，当信道空闲时，该簇首开始发送数据，否则该簇首等待并继续侦听，直到侦听到信道空闲，如此重复该过程。数据传输阶段完成数据的采集和传送，簇头完成对节点数据的接收、数据的融合并通过簇首之间的数据传送转发给基站。

2.3 能量模型

传感器节点主要由收发器、处理器、传感单元、供电单元等四个部分组成，传感器节点的能量消耗主要集中在该四个组成部分。收发器用来进行节点之间或者节点与基站之间的通信，是数据传输的主要部分，处理器用于节点的管理、数据的融合和处理等功能，传感单元用于获取周围环境信息。供电单元主要为该节点提供能量，并对电源进行管理。节点消耗的总能量为

（3）

式中为收发单元消耗的能量，为处理器消耗的能量，为传感单元消耗的能量，为供电单元消耗的能量。

3 仿真实验与分析

本文使用MATLAB对LEACH算法和本分算法分别进行仿真。在无线传感器网络中随机分布100个传感器节点，分布在大小在100m×100m的区域内，如图1所示，基站设置在坐标为（50，50）位置。实验中以横轴轮数表示时间，纵轴作为参考指标，实验时间为1800轮。

图2比较了LEACH算法和本文算法的节点生命周期，从图中可以看出LEACH算法第1个死亡时间和最后一个节点死亡的时间分别在1000轮和1500轮，本文算法第一个节点和最后一个节点死亡的时间分别为1025轮和1780轮之后。通过数据可以看出，本文算法在延长网络节点生命周期方面有一定提升。

图3比较了两种算法在能量均衡方面的的性能，网络能量随着仿真时间的增加，能量消耗的差距逐渐增大。当仿真时间达到1500轮时，LEACH算法中的网络能量基本耗尽，而本文算法的能量耗尽时间为1780轮，从图3中可以看出，本文算法在节省网络能量消耗方面有一定的提升，同时也证明了该算法在延长网络方面的可行性。

4 结束语

本文针对无线传感器网络路由算法LEACH算法存在簇首

密度不均衡的问题，提出了一种改进的备选簇首的算法。该算法在密度较大的区域选举出剩余能量较多的节点作为备用簇首，当该区域簇首完成一个周期后不再进行下一轮的选举，而是使用备用簇首作为下一轮的簇首，从而减少节点选举轮数，均衡网络能量消耗。仿真结果表明，与LEACH算法相比，该算法在延长网络寿命，节省网络能量方面有一定的提升。

参考文献：

[1] 李建中，高宏.无线传感器网络的研究进展[J].计算机研究与发展，2008，45（1）：1-15.

[2] 向凤红，孔庆平， 毛剑琳，等.基于ZigBee的低功耗无线传感器网络改进协议[J].传感器与微系统，2017，36（3）：33-35.

[3] ZHANG Jing，LIU Yanheng，ZHANG Jindong，等.无线传感器网络簇半径自适应调整策略[J].吉林大学学报：工学版，2016，46（3）：876-883.

[4] 沈波，张世永，钟亦平.无线传感器网络分簇路由协议[J].软件学报，2006，17（7）：1588-1600.

[5] Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Hawaii International Conference on System Sciences.IEEE Computer Society，2000：8020.

[6] 胡艳华，张建军.LEACH协议的簇头多跳（LEACH-M）改进算法[J].计算机工程与应用， 2009，45（34）：107-109.

[7] 王东东，崔宝同.基于非均匀分簇多跳通信的改进Q—Leach研究[J].计算机技术与发展，2015（2）：212-215.

[8] 王灵矫，彭志强，李哲涛，等.基于权重的NPCHS-Leach协议簇头选取策略优化研究[J].传感技术学报，2015（12）：1846-1852.