基于LEACH的WSNs分簇优化策略

李亚男，徐夫田，陈金鑫(.山东师范大学信息科学与工程学院，济南25004;2.山东省地方税务局信息中心，济南25004)

基于LEACH的WSNs分簇优化策略

李亚男1，徐夫田2*，陈金鑫1
(1.山东师范大学信息科学与工程学院，济南250014;2.山东省地方税务局信息中心，济南250014)

针对LEACH算法中能量消耗不均匀的缺陷，本文提出了一种改进的路由协议来提高无线传感器网络的能量效率。在簇首选择阶段，引入节点剩余能量和初始能量来调节传感器节点随机数的大小;在成簇阶段，该算法将节点的剩余能量和距离汇聚节点的远近作为成簇的依据，使簇首的分布更加合理;在数据传输阶段，将节点与汇聚节点之间的距离及节点的剩余能量相结合，提出一种单跳与多跳相结合的传输方式，从而减少了能量消耗。仿真实验表明，改进后的算法能够更好的减少能耗，延长无线传感器网络的生命周期。

无线传感器网络;LEACH算法;随机数;剩余能量

无线传感器网络是由大量低成本、低能量的无线传感器节点组成的，它们被部署在指定的区域，动态的收集环境信息、相互协作，不断的将重要数据信息传到汇聚节点，达到无人值守、自动检测环境的目的［1-2］。作为一种新兴的信息获取方式和处理模式，WSNs在很多领域得到了广泛的应用。在军事方面的应用主要是实现对敌军兵力和装备的监控、对战场的实时监控、目标的定位、战场评估、化学攻击等，在环境科学中的应用是为野外随机性的研究数据获取提供方便［3］。由于无线传感器节点大多采用能量有限的电池供电，且节点数目多、分布广、所处环境复杂，很难对节点充电以及受成本和体积的限制，节能是WSN需要高度重视的问题［4-5］。因此设计无线传感器网络的首要目标就是尽可能的减少能量消耗，延长网络的生命周期。在WSNs体系中，路由协议是一个非常重要的研究领域，网络层路由技术的设计对WSNs中的能量效率有重要影响。因此设计优化网络的整体能耗效率、延长网络寿命的路由协议是无线传感器网络的一项重要研究内容［6］。

LEACH(Low-Energy Adaptive Clustering Hierar-chy)［7］协议是最早的WSNs分簇路由协议，但是没有考虑到节点的能量因素，从而造成某些节点过早死亡，整个网络能量消耗不均，缩短了网络的生命周期。目前对LEACH协议的改进主要是针对簇首的选择，成簇的过程及数据传输进行改进的，文献［8］的S-LEACH(Specifically-LEACH)中在成簇阶段采用分布式自协商和集中式相结合的算法以及设计了局部路由维护机制，此算法的优点是在能量耗尽导致的节点失效后，不会产生路由断点，缺点是集中式成簇开销较大，不利于网络的扩展。文献［9］在路由机制上采用单挑与多跳相结合的方式，采用MTE机制，优点是在簇首选择时考虑的节点的能量状态，缺点是在路由机制上只考虑的距离因素而未考虑节点的剩余能量因素。文献［10］的LEACH-PSOC算法利用粒子群算法的收敛性和全局优化能力将整个网络区域分割成多个字区域并考虑节点的剩余能量，此算法使簇头分布均匀，减少了能量消耗，但增加了网络延迟。文献［11］通过对网络中信息素浓度的建立和更新，达到降低簇头节点能量消耗过快的问题，此算法簇头分布均衡，优化了路由选择路径，但在数据传输阶段由于对网络进行搜索遍历，造成能量的消耗。

本文在借鉴上述改进算法的优点后提出一种新的改进算法，在簇首选择阶段，根据节点剩余能量和初始能量调节传感器节点生成随机数的大小，在成簇阶段，将节点的剩余能量和距离汇聚节点的远近作为成簇的依据;在数据传输阶段，根据节点与汇聚节点的距离及其剩余能量采用单跳与多跳相结合的方式传输，从而减少了能量消耗，优化了数据传输路径，延长网络的生存周期。

1 LEACH协议简介

LEACH协议的执行过程按轮周期性的运行，节点根据某个阈值等概率的成为簇首。LEACH协议使用的网络模型具有以下特点［12］:①所有的传感器网络节点都是同构的，初始能量相同，都使用全向天线;②传感器网络节点都是静止的，不具有移动性;③所有传感器节点都可以和汇聚节点直接通信;④信道采用对称信道。

LEACH协议的执行过程分为2个阶段:成簇阶段和数据传输阶段。数据传输阶段的时间比成簇时间长。一个成簇阶段和一个数据传输阶段就构成了一轮。在成簇阶段，每个节点生成0～1之间的随机数，如果生成的随机数小于阈值T(n)，那么该节点被当选为簇头，并向周围节点广播其成为簇头的消息。阈值T(n)计算式(1)为:

其中:P是网络中簇头占所有节点比例，即节点当选簇头的概率;r是目前循环进行的回合数，G是在最后1/p轮中还未当选过簇头的节点集合。通过这个阈值当选为簇头的节点向外发送广播消息，周围节点根据接收到的信号强度决定要加入的簇并通知簇首要加入该簇。簇头收到加入请求后将节点加入自己的路由表并为每个节点设定一个TDMA时间表，再将该表发送给所有簇内节点。此后的簇稳定阶段，节点按照该表进行数据传输。每隔一定时间整个网络重新进入簇形成阶段开始新一轮的簇头选举过程［13-14］。

LEACH算法虽然是比较经典的分簇协议，但是该算法的簇首分布不合理，网络中的能量消耗不均匀，从而造成某些节点过早死亡，整个网络能量消耗不均，缩短了网络的生命周期。

2 基于LEACH协议的改进算法

2.1 改进后的系统模型

2.1.1 网络模型

①网络中的所有节点具有相同的初始能量，随机分布并且部署后不再移动;②汇聚节点位置固定，能量无限;③网络中所有节点的位置未知，无需定位系统或定位算法求解节点的位置;④所有网络节点的发射功率固定，每个节点可以通过接收到信息的信号强度(RSSI)判断自身距离发送者的近似距离;⑤网络中所有节点可以计算出自己当前的剩余能量。

2.1.2 能量模型

本算法的能量模型采用文献［15］，能耗的计算公式如下:

数据发送消耗的能量公式为(2):

数据接收消耗的能量公式为(3):

数据融合消耗的能量公式为(4):

其中ET(k，d)为发送数据消耗的能量，Eelec为发射电路消耗的能量，当d≤d0时，采用自由传输模型，消耗的能量为εfs，当d＞d0时采用多径衰减模型，消耗的能量为εmp，ER(k)为接收数据消耗的能量，Eg(k)为数据融合及融合后发送数据消耗的能量。

根据文献［16］，可以得出信号强度和接收节点距离发送节点的距离d的关系，式(5)如下:

其中:r是接收节点和发送节点之间的距离，PR是无线信号的接收功率，n是传播因子。

2.2 改进后的工作过程

本文在考虑了节点剩余能量和节点接收到信号的强弱程度选择加入簇的基础上，对LEACH协议进行了改进，和LEACH算法一样，改进算法依然分为轮，每一轮分为簇首的选择、簇的形成和数据传输3个阶段。

2.2.1 簇头选举阶段

在簇头选举阶段，通过对LEACH中每个节点产生的随机数进行改进，从而完成簇首的选择。阈值T (n)不变，比较节点产生的随机数与阈值T(n)的大小，若生成的随机数小于阈值T(n)，那么该节点被当选为簇头，并向周围节点广播其成为簇头的消息。改进后每个节点产生(0，1)之间的随机数为:

其中r(i)为节点i在(0，1)之间产生的随机数，Ei-residual为节点的剩余能量，Ei-init为网络中所有节点的初始能量，Ri为调整后的最终随机数。这样剩余能量大的节点产生的随机数越小，就越容易成为簇首。

此阶段，除了节点产生的随机数不同外，簇首选举过程与LEACH算法相同。

2.2.2 簇的建立阶段

①簇头选举完后，每个簇头节点向网络中的所有剩余节点广播自己成为簇首的消息，假设节点的传输范围为r=50 m，簇头则仅对传输范围内的节点发送广播信号，剩余节点根据接收到的信号强度来决定加入哪个簇。这是由于在无障碍物的情况下，节点接收到的信号强度越大，说明距离发送节点的距离越近，节点接收到簇头发送的信号强度用str(head)表示;②同时Sink节点向所有非簇头节点发送信号，信号强度用str(Sink)表示;③节点比较从Sink节点和从簇头节点接收的信号强度。若从Sink节点接收的信号强度较大，即str(head)＜str(Sink)，则此节点不加入任何簇，而是与Sink节点直接通信，将其收集的数据直接发送给Sink节点，这也降低了簇头节点的能量负载，使得簇头节点的能量消耗减少。若从簇首节点接收的信号强度较大，即str(head)＞str(Sink)，则该节点加入该簇头所在的簇。

2.2.3 中继节点选举阶段

中继节点的选举以节点的剩余能量为依据，每个簇首节点以半径2r广播自身ID和剩余能量消息，以此更新其邻居表。然后将邻居表中的各簇首节点的剩余能量进行比较，选取值最大的作为其中继节点。

2.2.4 多跳路由策略

在该阶段，Sink节点再次向各簇头节点发送信号，各簇头节点根据接收到的信号强度和自身的剩余能量选择单跳路由或者多跳路由。首先，若簇头节点接收到的信号强度大，说明此簇头节点距离Sink节点较近;其次，各簇头节点将自身的剩余能量与网络中所有节点的平均能量进行比较，若Ei-residual≥Eaverage，则此簇头节点与Sink节点直接通信;若Ei-residual＜Eaverage，则此簇头节点与Sink节点以多跳方式通信，多跳方式通信的中继节点选择距离此簇头节点最近且能量较大的簇头节点。若簇头节点接收到的信号强度小，则都以多跳方式与Sink节点通信。

2.2.5 数据传输阶段

该阶段主要分为3个阶段:①对于直接与Sink节点通信的节点将收集的数据传送给Sink节点;②簇内成员节点到簇首节点。根据簇首为各成员节点分配的TDMA时隙表，簇内成员节点将收集到的数据在自己的时隙内发给簇首，非时隙时间休眠以节省能量;③簇首节点到中继节点。各成员节点将数据发送给簇首后，簇首进行数据融合后将数据发给中继节点;④中继节点到Sink节点。中继节点将数据进行数据融合后将数据发给Sink节点。

2.3 改进后的网络拓扑结构

改进后的拓扑结构如图1所示。距离Sink节点近的节点直接将数据传给基站，距离基站较远且能量不足的节点先将数据融合后传给中继节点，中继节点再将数据传给基站，其他剩余能量大的簇头则直接将数据传给基站。

图1 拓扑结构

3 仿真及结果分析

本文使用MATLAB仿真LEACH算法和改进后的算法，主要参数的设置参考文献［17］，如表1所示。分别从网络生存时间、节点数与能量消耗关系、网络吞吐量三方面进行仿真比较。

表1 仿真参数

3.1 网络生存时间比较分析

分别在大小为100 m×200 m和300 m×400 m的区域内，比较两者节点的存活数量随时间变化的情况，如图2所示。

图2 生存时间曲线

从图2可得出:改进后的算法比LEACH算法性能高。在300 m×400 m区域里，第1个节点死亡时，改进后的算法比LEACH算法性能提高了300%。因为考虑了节点的剩余能量因素，所以均衡了网络的能量消耗，减少了第1个节点的死亡时间，延长了网络的生存时间，提高了网络的寿命。

3.2 节点数与能耗关系的比较分析

图3是节点数目与平均能量消耗之间的关系仿真结果。从图3可以看出，在节点数目小于175时，两者都是随着节点数目的增加而增加，节点数目超过175后，LEACH算法的平均能量消耗成上升趋势，而改进后的算法平均能耗成下降趋势。因此，在节点数目超过175后，改进后的算法能量消耗少，从而延长网络的生命周期。

图3 节点数与平均能耗曲线

3.3 网络吞吐量比较分析

如图4所示，随着网络运行时间的增加，Sink节点接收到的数据总量的变化情况。随着网络运行时间的延长，改进后算法Sink节点接收到的数据总量在一个生命周期内比LEACH算法多近1.3倍。因此改进后的算法在网络吞吐量性能上要优于LEACH算法。

图4 网络吞吐量曲线

4 结束语

本文针对LEACH协议的不足，对其进行了改进。主要在簇首选择阶段，将节点的剩余能量和初始能量考虑进来作为随机数的调整因素，其次在成簇的过程中，将节点的剩余能量和距离汇聚节点的距离考虑进来，优化了整个网络的成簇结构，减少了能量消耗，最后在数据传输阶段，采用单跳与多跳相结合的方式进行数据传输，优化了数据传输路径，使簇首负载均衡，延长了整个无线传感器网络的生命周期。

［1］邓亚平，邓利军.无线传感器网络的能量有效加权分簇算法［J］.计算机工程与设计，2011(4):1216-1219.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Micro Sensor Networks［C］//Proceedings of the Hawaii Conference on System Sciences，2000.

［3］刘东江，贾卓生.基于分簇的无线传感器网络路由协议的研究［J］.计算机科学，2012，39(10):23-25.

［4］王海涛.无线传感网络中的分簇协议综述［J］.传感器世界，2011(4):6-10.

［5］刘群，白全炜，曾宪华，等.能量感知的WSN节点分类控制路由算法［J］.传感技术学报，2011，24(7):1053-1059.

［6］李建奇，曹斌芳，王摇立，等.一种结合LEACH和PAGASIS协议的WSN的路由协议研究［J］.传感技术学报，2012，25(2): 263-267.

［7］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocolfor Wireless Microsensor Networks［C］//Proc of the 33rd An-Nual Hawaii Int’l Conf.on System Sciences.Maui: IEEE Computer Society，2000:3005-3014.

［8］李芳芳，王靖.一种基于LEACH协议的无线传感器网络路由算法［J］.传感技术学报，2012，25(10):1445-1451.

［9］胡钢，谢冬梅，吴元忠.无线传感器网络路由协议LEACH的研究与改进［J］.传感技术学报，2007，20(6):1391-1396.

［10］陈晓娟，王卓，吴洁.一种基于LEACH的改进WSN路由算法［J］.传感技术学报，2013，26(1):116-121.

［11］胡彧，王静.基于蚁群算法的LEACH协议研究［J］.传感技术学报，2011，24(5):747-751.

［12］张怡，李云，刘占军，等.无线传感器网络中基于能量的簇首选择改进算法［J］.重庆邮电大学学报(自然科学版)，2007，19 (5):613-616.

［13］杨冕，秦前清.基于无线传感器网络的路由协议［J］.计算机工程与应用，2004，32:130-131.

［14］黄少昱，曹阳，王悦伟.无线传感器网络中的路由技术［J］.计算机工程与应用，2004，19:123-126.

［15］Heinzelman W R.An Application Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans on Wireless Communications，2002，1(4):660-670.

［16］方震，赵湛，郭鹏，等.基于RSSI测距分析［J］.传感技术学报，2007，20(11):2526-2530.

［17］Huang Wenwen，Peng Yali，Wen Jian，et al An Energy-Efficientmultihop Hierarch Routing Protocol for Wireless Sensor Networks［C］//Proceeding of the 2009 Intermational Conference on Networks Security，Wireless Communications and Trusted Computing Washington DC，USA，2009:469-472.

李亚男(1988-)，女，硕士研究生，主要研究方向为无线传感器网络，lynwu. di@163.com;

徐夫田(1965-)，男，博士，山东省地方税务局信息中心主任，主要研究方向为电子政务、数据库，670793991@qq.com;

陈金鑫(1988-)，男，硕士研究生，主要研究方向为无线传感器网络，728839869 @qq.com。

Clustering Optimization Strategy for WSNs Based on LEACH

LI Yanan1，XU Futian2*，CHEN Jinxin1

(1.Department of Information Science and Engineering，Shandong Normal University，Jinan 250014，China; 2.Information Center，Local Tax Bureau of Shandong Province，Jinan 250014，China)

To solve the unevenness of energy consumption in LEACH，We propose an improved routing protocol to improve the energy efficiency of the wireless sensor networks.In the cluster heads selection stage，this paper introduces residual energy and initial energy of the sensor nodes as two important components to adjusts the values of random numbers.In clustering stage，the algorithm uses the residual energy and the distance between sensor nodes and the Sink node as the basis for clustering to make the distribution of the cluster heads more reasonable.In the stage of data transmission，a route method，which combines single hop route with multi-hop route according to the distance between sensor nodes and the Sink node and the residual energy，is proposed to reduce energy consumption.Simulation results demonstrate that the improved algorithm is more efficient in reducing energy consumption and prolonging the life cycle of wireless sensor networks.

wireless sensor networks;LEACH algorithm;random numbers;residual energy

TP393

A

1004－1699(2014)05－0670－05

10.3969/j.issn.1004－1699.2014.05.019

2014-01-16

2014-04-09