余建迪，朱 翔，陈培基，徐超超，唐震洲

（温州大学 物理与电子信息工程学院，浙江 温州 325035）

一种能耗平衡和密度感知的无线传感器网络分簇算法

余建迪，朱 翔，陈培基，徐超超，唐震洲

（温州大学 物理与电子信息工程学院，浙江 温州 325035）

WSN在实际应用中其能量是有限的，因其所处环境等，后期对能源的补充不易。为了延长其生命周期，此对LEACH算法进行了一些改进，根据节点自身能量情况以及节点密度情况来改进对簇头的选取方式，并提出了一种EDS-LEACH算法。通过用MATLAB对LEACH算法，EDS-LEACH算法以及2种其他文献的分簇算法进行仿真比较，验证了EDS-LEACH算法在网络的存活时间上较之LEACH算法以及另外两种分簇算法有显著提高。

WSN；EDS-LEACHL；能量；簇头；算法

无线传感器网络（WSN：Wireless Sensor Networks）近年来迅速发展，因其个体小巧、价格低廉、部署方便且拥有强大的监测、感知功能，能将采集到的数据准确传输给用户进行分析，被广泛应用于国防、工业、农业、商业等[1]。但无线传感器网络的每个传感器节点的电池容量有限，网络中的传感器个数多且分布不均，节点所处环境不定，对于给传感器充电或者更换电池来说可能更不易。这就导致了当网络中大部分节点耗尽能量，整个网络就将濒临瘫痪。因此，如何延长无线传感器网络的平均寿命成为了研究无线传感器网络的重点问题之一。

考虑到各节点能量不平衡，无线传感器网络通常采用分簇的方式，通过选择簇头来转发信息给基站的方式，延长网络平均寿命。LEACH算法就是一种基于多簇结构的自适应聚类路由协议[2]。其通过簇头节点转发数据给基站，减少了每个节点向基站发送数据的次数以及所产生的信号冲突问题，提高数据发送的效率，并且实现了网络能量负载均衡。然而，LEACH算法也有其自身的不足之处：1）其簇头选择未对节点剩余能量进行判断。2）其簇头选择并没有考虑到待选择的节点的周围节点密度。3）其数据传输仅采用单跳，不利于簇头节点降低能耗。

围绕如何选择簇头，如何形成簇群，如何传输数据，有许多文献在LEACH的基础上进行优化研究，提出了很多优秀的算法和协议。文献[3]考虑到节点初始能量以及节点密度对阈值算法进行了改进。文献[4]考虑节点初始能量和节点平均能量，提出了LEACH-EA、LEACH-EI两种新的算法用于不同规模的无线传感器网络。文献[5]采用中继节点承担数据转发，提出了EB-LEACH分簇多跳路由协议。文献[6]结合贪婪算法选择中继节点，提出了一种基于时间的簇头竞争算法。文献[7]采用粒子群算法和蚁群算法提出了多跳算法。

文中以无线传感器网络的簇头选择方式作为切入点，针对上述不足点1与不足点2，提出EDS-LEACH算法，并与文献[3]文献[4]所涉及的部分算法以及LEACH算法一同用MATLAB仿真，比较各算法对WSN网络生命周期的延长情况。

1　LEACH算法介绍

1.1LEACH算法概述

LEACH[2]（Low Energy Adaptive Clustering Hierarchy）是Heinzelman等提出的一种经典的自适应型的集群算法。该算法提出了“轮”的概念，每一轮由两个阶段构成：一为初始分簇[8-9]，二为稳定状态。

1.2初始分簇阶段

在LEACH算法的分簇阶段，随机选择网络中的节点作为簇头节点，负责接收簇群范围内的节点发送的信息，统一转发给基站节点，从而使整个网络的能量负载能够均衡分配在各个节点上，延长了首个死亡节点的生存时间以及总网络的寿命[10]。

簇头选择方式为：网络中的节点产生0～1之间的随机数，如果这个数小于阈值T（n）[11]，则该节点当选簇头，T（n）的计算方法如图（1）所示：

其中，p为期望簇头在节点总数的百分比，r为当前轮数，G为在过去轮中为当选簇头的节点集合。由上式可知，当r=0时，T=p，即在初始阶段每个节点都以p的概率成为簇头。若在此过程中某一节点成为了簇头，则其在接下来的轮中都不能再成为簇头，而若在此过程中每一节点没有成为簇头，则其下一轮中成为簇头的概率为，比前一轮的概率增加了，因而其成为簇头的概率得到提升。轮数r增加，概率T也随之增加，到时，T=1。所以该网络中所有的节点都会在轮中仅成为一次簇头。

2　LEACH算法改进

LEACH算法通过产生一个阈值，让节点自主选择是否当选簇头。文中考虑了节点剩余能量大小以及其覆盖范围内存活的节点总数，但仍保留LEACH算法的基本“轮”机制，在其阈值公式上进行了改进，提出了EDS-LEACH算法。

2.1改进公式

其中，Ecurrent为节点当前剩余能量，Emax为当前所有节点里最大的剩余能量，m为节点监听范围内的节点数，M为当前各节点监听范围内的节点数中的最大值。

2.2改进分析

2.2.1节点能量分析

在原LEACH算法中，任何一个节点均有机会成为簇头，然而该算法却没有考虑到节点自身剩余能量情况，当节点自身剩余能量较少时，若继续成为簇头节点，该节点将会加速死亡，从而影响到整个网络的生命周期。我们可以采取降低其阈值的方案，从而降低该节点当选为簇头的概率。

2.2.2节点密度分析

在公式（2）中，节点剩余能量率和节点密度都通过乘法因子的方式引入，其目的是为了让综合节点剩余能量以及节点密度后的阈值能够保证其取值范围不变。若采用将节点剩余能量率和节点密度相加后引入，将可能出现簇头选举失误的情况例如，某一节点，其ρ接近1，而EP接近0时，其总和接近1，相应的T值较大，则该节点当选簇头节点的概率大，一旦该节点当选簇头，将很快就死亡，影响整个网络的生命周期。

3　仿真参数及结果

文中在Windows平台下利用MATLAB进行仿真。假设在一个长100 m，宽100 m的区域内随机分配100个无线传感器节点，每个节点的能量随机分配，取值范围是0.3 J到0.5 J之间，基站位于坐标（50 m，50 m），具体参数[12-14]如表1所示。

网络存活节点百分比与工作时长变化关系通过100次的仿真求平均后得出结果如图1所示，图中可看出原来的LEACH算法在 550轮时出现了首个死亡节点，而 EDSLEACH算法在740轮才出现首个死亡节点，两者相差200轮。假定当系统内的节点存活数低于20%后，便认为该系统已瘫痪。由图知，当改变了阀值的系数后，网络生命周期比原来的LEANCH算法要更长，整个网络的能量利用率得到提高。

表1　仿真参数

仿真结果运行以1 500轮后节点存活数目作为算法节能的评价指标同时EDS-LEACH算法还与其他文献所提出的算法进行比较，从图中看出EDS-LEACH算法优于文献[3]的算法，其曲线与文献[4]的算法曲线走势类似，但依旧优于文献[4]所提出的算法。

图1　剩余节点曲线

4　结束语

文中针对LEACH算法加以改进，结合节点自身当前剩余能量以及节点密度，对LEACH算法的簇头选举公式进行修改，提出EDS-LEACH算法，提升了WSN网络的负载均衡能力，增加了WSN网络的生命周期。但本文并未考虑到节点通信方式的改进，如何让节点采用复合式单跳多跳[15]结合方式发送数据，我们将进一步深入研究。

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

[2]LI Hui-yun.An optimized LEATH algorithm in wireless sensor network[C].ISDEA，2014，Fifth International Conference on.IEEE，2014，191-194.

[3]秦相林，王玮琦.基于延长WSN生命周期的LEACH算法的改进[J]．黑龙江科技信息，2015，15（1）:111-112.

[4]白凤娥，王莉莉，马艳艳，等.无线传感器网络路由协议LEACH的算法分析[J].太原理工大学学报，2009，40（4）: 347-351.

[5]周方，李腊元，戴佳佳，等.多跳路由协议EB-LEACH[J].中北大学学报：自然科学版，2013，34（4）:413-418.

[6]蒋昌江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议[J].软件学报，2012，23（5）:1222-1232.

[7]郑波.基于改进粒子群算法的无线传感器能量优化[D].无锡：江南大学，2014.

[8]孙利民，叶驰，廖勇.传感器网络的路由机制[J].计算机科学，2004，31（1）:54-57.

[9]LIU Re，WANG Xiu-ping.An improvement to LEACH-based routing algorithm[C].ICIME，2011，133-136.

[10]任丰原，黄海宁，林闯.无线传感器网络[J].软件学报，2003，14（7）:1282-1291.

[11]XU Long-long，ZHANG Jian-jun.Improved LEACH cluster head multi-hops algorithm in wireless sensor networks[C]. DCABES，2010，263-267.

[12]Ameer A A，Younis M.A survey on clustering algorithm for wireless sensor networks[J].Computer Communication，2008，30:2826-2841.

[13]李岩，张曦煌，李彦中.基于LEACH协议的簇头多跳（LEACHM）算法[J].计算机工程与设计，2007，28（17）:4158-4160.

[14]刘铁流，巫咏群.基于能量优化的无线传感器网络分簇路由算法研究[J].传感技术学报，2011，24（5）:764-770.

[15]王国芳，李腊元，李春林，等.无线传感器网络中基于能量约束的簇首多跳算法[J].传感器技术学报，2009，22（7）: 997-1001.

An energy consumption balanced and density aware clustering algorithm for wireless sensor networks

YU Jian-di，ZHU Xiang，CHEN Pei-ji，XU Chao-chao，TANG Zhen-zhou
（Whenzhou University，Physics and Electronic Information Engineering College，Wenzhou 325035，China）

The energy of a wireless sensor network is limited.In order to prolong its life cycle，an energy consumption balanced and density aware clustering algorithm based on LEACH protocol is proposed for wireless sensor networks，which is called EDS-LEACH.EDS-LEACH takes full consideration on the residual energy of each node and the density of the network during the process of cluster header selecting.The performance of EDS-LEACH is compared with original LEACH and two other clustering algorithms.The results show that the survival time of the EDS-LEACH algorithm in network is distinctly much longer than the LEACH algorithm and two other clustering algorithms.

WSN；EDS-LEACHL；energy；cluster heads；protocol

TN929.5

A

1674－6236（2016）21-0115-03

2015-11-11稿件编号：201511114

国家自然科学基金资助项目(6130320)；浙江省新苗计划项目(2013R424016)

余建迪（1995—），男，浙江宁波人。研究方向：无线传感器网络及其应用。