一种改进的无线传感器网络LEACH协议及仿真

王巧玲　曾春华

摘 要： 针对无线传感器网络经典LEACH协议中簇首数目选择及通信方面的不足，提出一种改进的M-LEACH算法，对如何动态确定最优簇数目进行了研究，分析了影响最优簇数目的因素，推导出了最优簇首比例公式，同时给出了一种能量均衡的无线传感器网络分簇路由算法。仿真实验结果表明，与经典LEACH协议相比，运行M-LEACH协议后能够减少网络能耗和均衡网络能耗，延长网络的生命周期。

关键词： 无线传感器网络；LEACH协议；簇首选取；网络生命周期

中图分类号：TP393。01 文献标识号：A 文章编号：2095-2163（2014）05-

A Modified LEACH Protocol and Simulation for Wireless Sensor Networks

WANG Qiaoling， ZENG Chunhua

（College of Science， Jiangxi Agricultural University， Nanchang 330045， China）

Abstract： Aiming at the efficiency of cluster head election and communications in the classical LEACH protocol for Wireless Sensor Networks （WSN）， an improved M-LEACH algorithm is proposed。 In this algorithm， the factors affecting the optimal number of clusters are analyzed， and also the optimal proportion of cluster head is deduced， further an energy balanced routing algorithm for WSN is proposed。 The simulation result shows that the improved M-LEACH algorithm can reduce and balance the network energy consumption effectively comparing with classical LEACH， therefore can prolong the lifetime of the network。

Keywords： Wireless Sensor Networks； LEACH Protocol； Cluster Head Election； Network Lifetime

0 引 言

无线传感器网络（Wireless Sensor Networks， WSN）是由大量具有通信与计算能力的微小传感器节点以大区域、高密度方式而布设在无人值守的监控区域所构成的能够根据环境自主完成指定任务的“智能”自治测控网络系统[1]。而且由于WSN能够联合协作地实时监测、感知并采集分布在区域内的监测对象的信息，再传输给需要信息的基础用户，已经广泛地应用于各大领域，诸如国防军事、国家安全、环境监测、医疗监护、空间探索、交通管理、森林火险监测、智能家居等多个方面[2]。但由于传感器节点在能量、存储、计算和通信能力上仍较为有限，且WSN还具有节点多、资源受限、多跳路由、动态变化等具体特点，若要实现能量高效的数据传输，以及同时提高网络的健壮性和扩展性，有效的针对方法之一就是将网络划分为簇，且通过簇首对数据的融合而减少传输的数据量，由此即可降低网络能量消耗、并节约带宽等有限资源[3]。接下来的分析还可知道，由于允许邻居节点在发送给基站前能够实现数据信息共享，且簇首节点也能够对簇成员节点的信息进行高效融合，这就使得基于簇的路由算法相对平面路由算法能节约能耗，进而更延长了网络的生命周期。此外，还因为分簇的拓扑结构可以容忍个别节点的失效，随之即使得网络具有了较好的适应性和稳定性，并且路由和控制开销也会较少，在移动管理和网络的局部同步的实现上也将相对容易一些。只是目前大多数层次路由算法仅仅根据节点当前的信息（如剩余能量）简单随机地选择簇首，却忽略了周围邻居节点的信息及网络剩余能量的均衡性，为此而导致某些簇头节点负载较重、进而成为瓶颈，具体后果即是严重降低了网络的生命周期。因此对WSN进行有效分簇已然成为当前的研究热点[4]。

综上所论可知，为了避免部分节点过早死亡而导致整个网络失效，簇首的负载要尽可能地均衡，同时簇数目的选取及簇首的分布也要合理。因此，研究过程就需要综合考虑各种因素以最佳确定簇首数目和簇首分布。不言而喻，这是研究开展的核心关键所在。

1 相关工作及问题描述

1.1 相关工作

分簇算法是WSN分簇路由协议设计中的关键技术，若将其依据不同基准，则有各种分类方式。具体来说，如果按照不同参数选择簇头可分为基于节点剩余能量、节点ID、最高连接数、节点位置、节点的权重等；如果另按算法的执行方式可分为集中式（在基站执行）和分布式，而分布式的分簇算法又可分为概率式（如LEACH）[5]和迭代式（如HEED）[6]两大类。其中，LEACH协议采用周期性随机选取簇首的机制，簇内成员节点在自己的TDMA时隙可将数据发送给簇首，其余时间则进入休眠状态，并且簇首对数据融合后将直接发送给基站。与平面路由和静态路由相比，该算法既节省了能耗，又延长了网络生存时间，但也存在相应不足[7]，对其分析论述如下：

（1）节点以相同的概率选择充当簇首，因此剩余能量小的节点负载过重，可能过早死亡，如此将影响网络的寿命和健壮性；

（2）所有节点采取单跳方式发送数据，使得某些距基站较远的节点能量开销较大，即将导致网络能量分布不均衡。

而HEED成簇路由通过采用混合簇头选举机制，同时考虑了节点的剩余能量和邻节点的度，尤其做到了平衡能量消耗和簇首节点的均匀分布而延长了网络的寿命，但却未曾考虑到最优簇数目的问题。

分簇算法中最优簇数目的确定将直接影响着网络的寿命，然而现有的大多数成簇算法对于最优簇数目没有施与充分的考虑。研究表明[8]，簇数目的最优值kopt是存在的。一方面，若分成簇的数目小于kopt，则簇内成员节点将会由于距簇头太远而在数据传输过程中使能量耗尽，或在还未接受到足够数量的节点反馈信息时簇首就开始为其他节点分配TDMA时隙，而将形成冗余通信而造成能量的浪费；另一方面，若簇数目大于kopt，则将无法达到WSN分层结构减少数据传输量的设计效果[9]。实际上，在经典LEACH协议中，簇数目只是固定的比例，而没有考虑节点剩余能量及邻居节点的状态。但已有文献[10]从平衡网络负载均衡程度对的角度来优化簇数目，也就是通过设置定时器将节点的剩余能量和簇头比例联系起来，使剩余能量大的节点成为簇头的概率也相应增大，且仿真实验表明随着簇头比例的增大，负载均衡程度也已出现大幅增加。另有文献[11]利用概率知识推导了最优簇数目，并指出若未按最优方式分簇，即会导致网络消耗的能量呈指数增长。虽然如此，但上述算法却都依然我能获得网络能耗良好均衡的实现。有鉴于此，本文将重点给出有针对性的完整研究称，而且经过仿真测试，得到了理想的实验结果，

1.2 问题描述

（1） 系统模型

为了简化问题模型，本文对要研究的无线传感器网络作以下假设：

①所有节点随机部署在监测区域，部署后节点和基站是静止的；

②除Sink节点外，每个节点的能量有限、初始能量相同、地位平等；

③每个节点均有唯一的标识ID，且剩余能量和位置可以感知；

④除基站外所有节点的有效通信范围相同，节点间的通信链路是双向的。

将无线传感器网络抽象为一个无向加权图G=（V，E），其中V为传感器节点的集合，V={vi|i=1，2…N}，且N为传感器节点的个数；E则是边的集合，E={（vi，vj）|（vi，vj）VV，ij}。

（2） 能量模型

本文采用文献[11]中的节点工作能耗模型来计算网络的能量消耗。每发送l bit的信息到距离为d的节点所消耗的能量为：

ET（l， d）=ET-elec（l）+ET-amp（l， d）= （1）

在式（1）中，Eelec表示发射装置和接收电路每发送或接收单位bit的能量消耗；fs和mp表示发射放大器将每bit数据传送单位平方米所耗的能量；d0是传输距离的门限值，并且 。若传输距离小于阈值d0时，功率放大损耗采用自由空间模型；而当传输距离大于等于阈值d0时，即采用多路径衰减模型。

传感器节点每接收l bit信息所消耗的能量可计算为：

ER（l）=ER-elec（l）=Eelecl （2）

因此，将l bit的数据从节点ni传输到nj消耗的能量可表示为：

Ei， j（l）=ER（l）+ET（l， d） （3）

（3） 问题描述

定义1 节点vi与vj之间的距离dij可用公式（4）进行计算，其中（xi， yi）和（xj， yj）分别表示节点vi、vj的坐标。

（4）

定义2 设传感器节点的通信半径为R，节点i、j间的距离为d（j， i），若d（j， i）R则称节点i、j互为邻居节点，记节点i的邻居节点集合为N（i），即N（i）={jd（j， i）R}。

研究目的旨在建立一个能量均衡的WSN簇拓扑结构，从而实现整个网络中节点剩余能量的均衡，并延长网络的生命周期，因此在分簇过程中应加入对最优簇数目的考虑。问题就是如何在能量约束的前提下确定最优簇数目及通过优化得到最优簇首，而且在均衡整个网络能量的同时使得网络消耗的能量最小。本文主要讨论均匀分布下最优簇数目的确定及影响最优簇数目的主要因素，同时还通过仿真实验对改进最优簇数目后的算法与经典LEACH相比而对网络性能的影响展开分析，并给出结论。

2 改进簇首选择后的分簇算法

2.1 最优簇数目的确定

设有n个节点均匀分布在面积为A=2a2a的正方形监测区域中，并假定：

（1）数据包长度相同，且不考虑重发和碰撞所消耗的能量；

（2）基站处于区域的中心，并且成员节点到CH的距离和CH到Sink节点的距离d都满足dd0。

各轮循环传输l bit数据时，每个簇头节点消耗的能量ECH主要包括：接收簇内节点信息所消耗的能量、进行数据融合所消耗的能量和将融合后的数据发送到基站消耗的能量。在此，设簇的数目为k，则平均每个簇中的成员节点为N1=n/k1，每轮中每个CH节点消耗的能量将为ECH=（nk1） Eelecl+nkEDAl+Eelecl +lfsdBS2，而单轮中每个非簇首节点消耗的能量即为Enon-CH=lEelec+lfsdCH2。其中，dBS是簇首节点到基站的平均距离，dCH则是成员节点到CH节点的平均距离。现对 dBS和dCH的运算过程可做如下呈现：

dBS= = =0。765a

dCH2= （5）

其中，（x，y）是节点的分布密度函数，每轮循环节点传输l bit数据时每个簇消耗的能量ECluster= ，因此网络消耗的总能量为：

Etotal=kECluster= （6）

求Etotal对k的一阶导数，并令其等于零，得

=0

由其可得到最优簇数目，具体公式为：

（7）

进一步地，最优簇的比例则表示为：

（8）

2.2 M-LEACH路由算法

分簇路由包括簇的生成（Cluster formation）和数据传输（Data transmission）两个过程。其中，簇的生成又可分为初始化簇首、初始簇首收集簇成员信息、最优簇形成、及稳定运行等四个技术阶段；而数据传输则可分为簇内传输和簇间路由两个阶段。

（1） 初始化簇首阶段

首先选择候选簇首节点构成初始簇首集合，只有候选簇首才有可能成为本轮的簇首。设Scandidate表示候选簇首的集合，定义：

Scandidate={ni|Ei>E} （9）

其中：

E= （10）

式中，N为网络中节点的数目；Ei表示节点i的当前剩余能量，也就是只有大于当前平均剩余能量的节点才有机会成为候选簇首。

（2） 收集簇成员信息阶段

成员节点将自身的剩余能量、位置及ID号等信息通过候选簇首发送至基站，于是每个候选簇首节点即已获得邻居节点的ID、位置和剩余能量等必要信息。

（3）簇的形成阶段

采用2.1中优化后的簇首数目选择簇首，基站会将最优簇首集合和簇的结构广播出去，每个非簇首节点则根据收到信号的强弱选择加入哪个簇，同时再将自己的位置和剩余能量等信息发送给簇首节点，即会等待CH节点分配TDMA时隙，以避免数据信息的冲突。簇成员节点在相应的时隙内就会将数据包发送给CH节点，而在发送时间外则将关闭收发设备，进入休眠状态，以减少消量消耗。

（4） 稳定运行阶段

当最优簇首集形成后，就进入稳定运行阶段。而在CH节点接收到了所有成员节点的数据后，即将数据融合后再通过簇间传输发送至基站。形成的簇经过一段时间运行后则很难保证所有簇成员节点能量消耗的平衡，此时若出现簇首节点的当前剩余能量低于门限值时，将重新选举簇首。

由于M-LEACH算法在优化簇首选择阶段充分考虑了节点本身及邻居节点的位置和剩余能量等信息，因此就能够平衡簇成员节点间的能量消耗，进而有效避免盲节点的产生，并在一定程度上可防范网络空洞的出现。

3 M-LEACH算法的仿真分析

通常，分簇算法的性能评估主要参照如下指标：网络的生存周期、每轮存活的节点数目、吞吐量、可靠性，等。基于此，本文即在探讨与分析参数对最优簇数目的影响及改进最优簇数目后的路由协议对网络能耗和生命周期影响的基础上，又对仿真结果进行了比较和分析。

3.1 仿真环境及参数设置

采用的仿真工具是Matlab 7。0，仿真环境为：n个传感器节点随机均匀分布在二维平面2a2a（单位：m2）的正方形监测区域中，假定基站的能量足够大，通信半径可以覆盖整个网络，普通传感器节点的能耗模型则采用1.2中的能量模型，并按公式（1）计算能耗，模型中各个参数的取值即如表1所示。

表1 能量模型参数设置表

Tab.1 Value of parameters in energy model

参数 Eelec EDA fs mp E0

取值 50nJ/bit 5nJ/bit 100pJ/bit/m2 0。0013pJ/bit/m4 0。5J

3.2 最优簇数目对网络生命周期的影响

设100个节点随机分布在100m100m的监测区域中，基站位于区域的中心（50，50）处。每轮发送数据包的长度l=1 000bit，仿真经过一定轮数后计算网络中存活节点的个数。此时再改变网络运行的最大轮数，每个实验重复10次，取平均存活的节点个数，由此而得到了采用改进最优簇数目后的LEACH与经典LEACH协议网络生命周期的对比曲线则如图1所示。

图1 M-LEACH算法与LEACH协议网络的生命周期对比

Fig. 1 Network lifetime comparison of M-LEACH and LEACH

图1表明，从网络开始运行即知，M-LEACH与经典LEACH相比，网络中第一个节点死亡经过的轮数出现了增加，因此网络的生命周期就得到了延长。另外，运行经过相同的轮数时，网络中存活的节点数将比LEACH增长大约20%，这是由于在优化簇数目时已经初步考虑了网络总的能量消耗。

4结束语

本文主要讨论了影响最优簇数目的因素以及均匀分布下最优簇数目的确定，在动态优化簇首选择的过程中，不仅考虑了候选节点的剩余能量，而且将其余节点到候选簇首的距离及其余节点剩余等因素考虑在内，更好地保证网络负载均衡，因而在一定程度上避免网络空洞的出现。仿真结果表明，最优簇数目与监测区域的面积、网络中的节点数等因素直接有关；而且通过与经典LEACH协议仿真对比可知，经过相同轮数后，改进最优簇数目的LEACH后网络运行的生命周期得到延长。但由于频繁构造簇又形成了一定的能量消耗，未来研究时则需提升对该问题的关注和研究力度。

参考文献

[1] 于海斌，曾鹏，等.智能无线传感器网络系统[M].北京：科学出版社，2006：5-6.

[2] JENNIFER Y， BISWANATH M， DIPAK G. Wireless sensor network survey [J]. Computer Networks， 2008（52）： 2292–2330.

[3] MATROUK K， LANDFELDT B. RETT-gen： a globally efficient routing protocol for Wireless Sensor Networks by equalising sensor energy and avoiding energy holes [J]. Ad Hoc Networks，2009， 7： 514-536.

[4] AKKAYA K， YOUNIS M. A survey of routing protocols in Wireless Sensor Networks [J]. Ad Hoc Networks， 2005， 3（3）：325-349.

[5] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H. Energy efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual International Conference on System Sciences， 2000（2）： 1-10.

[6] YOUNIS O， FAHMY S. HEED： a hybrid energy-efficient， distributed clustering approach for ad hoc sensor networks [J]. IEEE Transactions on Mobile Computing， 2004，3（4）： 366—379.

[7] LINDSEY S， RAGHAVENDRA C， SIVALINGAM K M0 Data gathering algorithms in sensor networks using energy metrics [J].IEEE Transactions on Parallel and Distributed Systems，2002， 13 （9）： 924- 935.

[8] 郝晓辰，房 艳，刘浩然，等.一种无线传感器网络的簇数目优化方法[J].传感技术学报，2008，21（8）：1432-1436.

[9] 吴臻， 金心宇.无线传感器网络LEACH算法的改进[J].传感技术学报，2006， 19（1）： 34-36.

[10] KUMAR D， ASERI T C， PATEL R B. EEHC： Energy efficient heterogeneous clustered scheme for wireless sensor networks [J]. Computer Comunications， 2009，32（4）：662-667.

[11] HEINZELMAN W B， CHANDRAKASAN A P， BALAKRISHNAN H. An application specific protocol architecture for wireless microsensor networks [J].IEEE Transactions on Wireless Communications， 2002， 1（4）：660-670.