基于节点剩余能量的分时分簇LEACH改进算法*

吴标，余剑，易仁杰

（电子工程学院，合肥230037）

基于节点剩余能量的分时分簇LEACH改进算法*

吴标，余剑，易仁杰

（电子工程学院，合肥230037）

针对无线传感网络中高效路由协议的设计问题，基于传感器节点的剩余能量提出一种分时分簇的改进LEACH算法。算法通过分时分簇方式，有效克服了传统LEACH算法中簇首数目不稳定的缺陷，且不会额外增加网络的能耗，使得簇首在整个网络中的分布以及网络的能量消耗更加均衡，有效延长了传感器网络的正常工作时间。仿真实验验证了改进算法的有效性。

无线传感器网络，分时分簇，LEACH，网络正常工作时间

0　引言

无线传感器网络（Wireless Sensor NetWorks，WSN）［1］是由众多传感器节点组成并以自组织方式相互协同工作的分布式感知网络，传感器节点负责完成实时监测、感知和采集各种环境或监测对象的信息。每个传感器节点由电池供电，其运算、存储、通信能力有限，因此，如何高效使用能量来最大化网络生命周期，成为路由协议设计时首先考虑的问题［2-3］。

传感器网络的路由协议主要分为平面路由协议和分层路由协议，由于平面路由协议需要维护很大的路由表，需要较大的存储空间，网络的扩展性差，不适于在大规模的传感网络中应用。分层路由协议就是将网络划分为若干个簇，每个簇通过一定的算法选择一个簇首，其余为非簇首节点。非簇首节点负责收集其所感知的网络消息并传递给簇首，簇首收集处理本簇成员的消息后传递给汇聚节点，较非簇首节点能耗较大。LEACH（LowEnergy AdaptiveClusteringHierarchy）［4］作为WSN网络最先提出的高效能分簇路由协议，因其采用节点轮转担当簇首的方法使得整个网络能耗更加均衡，从而达到延长网络生命周期的目的。文献［5-7］改进簇首选举的策略，在选取簇首时将节点的能量、距离汇聚节点的距离等考虑进去，使簇首数目尽可能接近最佳比例。LEACH及其改进协议［5-8］较平面路由协议，网络能耗更低、生命周期更长，但产生簇首的数目波动性较大，每轮中能达到最佳簇首的比例很小［9］，文献［8］中虽然簇首比例更为接近最佳比例，却增加网络整体的能耗。另外，在很多对可靠性要求比较高的应用中要求网络的所有节点均存活才能正常工作［10］。因此，网络第一个节点死亡的时间是网络正常工作的时间，是衡量算法有效性的重要指标。如何改进LEACH算法簇首选举机制，稳定的簇首数目、均衡化簇首分布和网络负载成为延长网络正常工作时间的关键。

本文针对LEACH算法产生簇首数目不稳定的问题，提出一种基于节点剩余能量的分时分簇路由算法LEACH-RE（LEACH based on theResidual Energy），且在簇首选举策略中采用自适应方式均衡化簇首分布，均衡了网络的负载，延长了网络正常工作时间，仿真实验对结果进行了验证。

1　LEACH算法概述

LEACH算法定义了“轮”（Round）的概念，网络按“轮”运行，传感网络每个节点根据自身产生的随机数决定是否成为簇首，每轮的工作过程分成两个阶段：簇建立阶段和稳定阶段。

LEACH网络结构模型具有以下特点：①汇聚节点位于网络之外，处理能力和能量不受限制。②所有的传感器节点具有相同的有限初始化能量，且每个节点有唯一的ID号作为标识。③无线信道是对称的，即节点A向节点B发送信息的能耗跟节点B向节点A发送相同长度信息的能耗是相同的。④簇内和簇间均采用单跳通信。⑤节点担当发送者时，可根据接收信号强度估算相对距离自动调整发射的功率以节省能量［11］。

1.1网络能耗模型

图1　网络能量模型

网络能耗模型的结构如图1所示［12］，网络的能耗主要集中在信号发射、接收和路径损耗上。信号在路径中的衰减模型分为自由空间和多径传输两种，这里将在信道传播损耗折合到发送端信号放大电路里。这样发送端能耗主要由信号发射电路和信道折合放大电路组成。

发射端的能耗主要由信号发射电路和信道折合放大电路构成，发送k bits信号的能耗由式（1）获取：

其中，Eelec为节点电路损耗的能量，εfs为自由空间传输损耗，εmp为多径衰减传输损耗，d0为自由空间传输模式与多径衰减模式的切换阈值，可通过式（2）得到：

接收端接收k bits数据电路的能耗为：

1.2簇建立阶段

簇建立阶段主要完成簇首选举和成簇两个过程。簇首选举过程中节点采取随机轮转的方式担当簇首，将网络的整体能耗分摊到每个节点。选举过程中，根据式（4）每轮设定一个阈值T（n）。每个节点自主地产生一个［0，1］的随机数，若该随机数小于T（n），则此节点在本轮中担当簇首，同时将该消息以广播的形式告知到整个网络；否则，此节点为非簇首节点，等待接收其他簇首的消息。节点一旦担当簇首，在接下来的1/p-1轮中，不再担当簇首。式中，p为簇首的比例，通常取5%［4］，r表示网络当前运行的轮数，G表示在最后的1/p轮中还没有成为簇首节点的集合。在r=0时每个节点都以p的概率成为簇首，经过1/p-1轮之后阈值T值变为1。

簇首选举过程完成后，成为簇首的节点广播Be-Head消息到整个网络，该消息主要包括簇首的ID、位置等信息。非簇首节点保持侦听状态，收到所有簇首Be-Head消息以后，根据接收到消息的强弱选择强度最大的簇，并向对应的簇首返回Join-Msg消息，确保加入距自身最近簇首。该消息比较短小，一般包含节点ID和簇首节点的ID。簇首节点收集完本簇的Join-Msg消息以后，根据成员数目按照TDMA方式为本簇的成员分配时隙，建立时隙表。然后将时隙表作为Response-Msg应答消息广播给其成员，非簇首节点仅在其分配的时隙内与其对应簇首进行通信，完成网络的成簇过程。

1.3稳定阶段

网络成簇以后，进入了稳定的数据传输阶段，该阶段占每轮的大部分时间。簇内通信中，非簇首节点根据Response-Msg消息明确被分配的时隙，在被分配的时隙内将收集的数据发送到对应簇首，其他时隙内该节点处于休眠状态以节省能量，确保簇内数据传输不会发生冲突。在整个过程中簇首始终处于开启状态，以接收本簇成员的数据。将本簇成员数据和自身采集数据融合以后，簇首采用载波侦听同步CSMA的方式将融合后的数据发送到汇聚节点，避免了簇首同时向汇聚点发送数据时的阻塞现象。所有簇首完成数据传送之后，新的一轮开始，网络重新进入簇建立阶段。

2　LEACH-RE算法描述

LEACH算法动态随机选择每轮的簇首，使所有节点轮转担当簇首。该算法动态周期性地重组网络，很好地适应了网络变化的要求，具有路由管理简单、稳定性强、易于网络的拓展等优点，很大程度上均衡了能量在所有节点的消耗。但是簇首选举过于随机，导致簇首数目波动较大，选出簇首在网络中分布随机，均不利于延长网络的生命周期。

2.1网络结构模型

采用与LEACH算法相似的网络模型。N个传感器节点在网络内随机均匀分布，网络按“轮”周期性地运行。LEACH-RE网络模型除了具备LEACH网络5个特点以外，还要求各节点和汇聚节点之间时间是同步的。

网络的能耗主要集中在数据传输中，本算法采用文献［12］的网络能量模型。LEACH-RE算法主要考虑节点发送数据、接收数据和簇首融合数据的能耗，网络初始化、睡眠模式等耗能均较小，可忽略。

2.2LEACH-RE的工作过程

与LEACH算法类似，LEACH-RE算法将工作过程也分成2个阶段：簇建立阶段和稳定阶段。网络布置完毕之后，汇聚节点以较大功率向整个网络发射网络消息，包含汇聚节点的位置信息、网络簇首的比例、成簇半径等信息。节点从该消息中获悉自身与汇聚节点的距离，担当簇首时根据这个距离选择合适的功率档与汇聚节点进行数据通信。成簇半径由汇聚节点在网络运行之前广播告知，簇的平均半径可由式（5）确定。簇首间距一定不小于2r，为保证簇首分布不过于密集，成簇半径设定为2r。

簇建立阶段主要完成簇首的选举和网络的组建。首轮中节点的初始能量是相同的，网络采用LEACH的方法完成簇建立阶段，2.2节已详细叙述。非首轮采用LEACH-RE算法完成簇建立阶段，具体过程见图2虚线框的内容。非首轮簇首选举采用“能者多劳”的原则，即剩余能量越多担当簇首次数越多，摒弃了LEACH簇首轮转导致个别节点早衰的劣势。每轮中剩余能量越多的节点延时越小，确保在簇首选举过程中剩余能量较大的节点担当簇首。节点根据自身剩余能量的情况由式（6）获取本轮应当延迟的时间，剩余能量越多的节点时延越小，率先达到时延的节点成为簇首并在其成簇半径2r内广播Be-Head消息；反之，时延越大。

其中，Tm表示网络的最大时延，EnRe（i）表示节点当前剩余能量，EnIni（i）表示节点的初始化能量。

到达指定时延的节点向外发射Be-Head消息，该消息比较短小，包括：簇首ID和簇首标示（表明该消息为Be-Head消息）。簇首根据成簇半径选择合适的发射功率档发射Be-Head消息，保证簇首不会过于密集分布在网络的某个区域，等待其他节点的加入消息。簇首成簇半径内的其他尚未达到时延的节点收到该消息后自动放弃本轮成为簇首的竞争，同时打开接收器，等待接收其他簇首的Be-Head消息。

图2　LEACH-RE工作过程

放弃竞争的节点在本轮中成为非簇首节点，在接收多个Be-Head消息后，根据接收信号的强弱决定加入到哪个簇，确保加入到距自身最近的簇首。在每个节点都确定加入到簇之后，所有节点均采用CSMA MAC协议发送Join-Msg消息，防止多个节点同时向簇首发送Join-Msg消息时发生消息阻塞。Join-Msg消息比较短小，一般包含节点ID和簇首节点的ID。簇首收集完本簇成员的所有Join-Msg消息后，基于簇内成员的数目，采用TDMA的方式为每个节点分配数据传输的时隙。时隙表构建完成后，簇首将时隙表作为Response-Msg消息以广播的方式告知本簇内的所有成员，同意加入本簇的请求。簇内成员节点仅在自身分配的时隙内处于工作状态，而在其他节点传输数据的时隙内始终处于休眠状态以节省能量。图2是LECH-RE一轮的工作过程，每轮结束后按该流程循环往复。该算法在非首轮中将簇建立阶段的簇首选择与成簇过程合二为一，以“能者多劳”为原则，确保能量较高节点成为簇首，并利用簇首Be-Head消息均衡化成簇的大小，使整个网络的能耗更为均匀。与LEACH相比，该算法实现了簇首数目的稳定和簇大小的均匀化，且未增加网络的能耗。

稳定传输阶段主要是完成本轮数据传输，采用与LEACH相同的工作方式，见1.3节。

3　仿真与结果分析

采用MATLAB R2013b作为实验仿真平台，对传统LEACH分簇路由算法、LEACH-ED算法［5］以及本文提出的LEACH-RE算法的能量均衡性进行仿真和性能对比分析。为减小单次实验的偶然性，进行100次蒙特卡罗实验，实验结果进行统计求平均。

本文的仿真环境设置如表1所示。对无线传感器网络的性能参数的分析有很多［13］，本文以轮为单位，针对网络每轮生成簇首数目的分布情况、网络能量的消耗情况和网络存活节点数随轮的变化情况对新算法的性能进行对比分析，这是网络正常工作时间即第一个节点死亡时间作为衡量网络节点存活状况的重要指标。

表1　仿真参数设置

3.1簇首分布情况在传感器网络运行的过程中随机选取100轮对LEACH算法、LEACH-ED［5］以及本文提出的LEACH-RE算法的簇首数目进行统计，网络中簇首的比例为5%。3种算法在相同的仿真环境下进行，参数设置见表1。统计的结果如图3～图5所示，横轴表示簇首的数目，纵轴表示轮数的统计。LEACH算法中节点是采用随机数决定成为簇首与否，导致网络产生的簇首数目具有很大的不确定性。从图3可以看出，采用LEACH产生簇首的数目波动性很大，分布在1到10之间；LEACH-ED在簇首选举中将能量考虑进去，使簇首过多或过少的情况明显减少，见图4；由图5可知，LEACH-RE算法产生簇首的数目更为稳定，较LEACH算法、LEACH-ED算法波动性明显小，更有利于网络总体能耗的减少。

图3　LEACH簇首分布统计图

图4LEACH-ED簇首分布统计图

3.2网络能耗情况

图6　每轮能量消耗

图7　每轮能耗的方差

选取网络运行的前100轮研究每轮网络的能耗情况，图6和图7分别是每轮所有节点能耗和能耗方差随轮数的变化情况，横轴表示网络运行的轮数，纵轴表示网络每轮的能耗或者能耗的方差。本文的LEACH-RE算法实现了簇首在网络中均匀分布，从图6可知较LEACH算法、LEACH-ED算法LEACH-RE算法每轮的能耗更为均衡，波动性较小；图7比较了3种算法在网络运行中耗能方差的情况，更明显地说明了LEACH-RE在每一轮的能耗更为均衡、稳定，更有利于均衡化网络的能耗，延长网络的正常工作时间。

图8　网络节点存活数目随轮数的变化

3.3网络运行情况

相同的网络仿真环境下，LEACH算法、LEACH-ED算法、LEACH-RE算法节点的存活数目随仿真轮数的变化情况如图8所示，横轴表示仿真进行的轮数，纵轴表示网络节点存活的数目。在对可靠性要求比较高的应用场景中要求所有节点均存活时传感器网络才能正常工作，一旦有节点死亡，网络的工作就不再具有意义。因此，这里将第一个节点死亡时网络进行到的轮数作为考量算法效能的重要指标。从图中可看出LEACH算法第一个节点死亡的轮数为776，LEACH-ED算法第一个节点死亡的轮数为835，LEACH-RE算法第一节点死亡轮数为900。可知，LEACH-RE算法较LEACH算法和LEACH-ED算法网络的正常工作时间分别延长了15.9%和7.8%。主要是改进了簇首的选举策略，保证了高能节点被选为簇首且均衡化了簇首在网络中的分布，放弃了簇首轮转机制而采用“能者多劳”机制，从而达到均衡化网络节点的能耗，延长网络正常工作的时间。

LEACH-RE算法簇内成员与簇首之间、簇首与汇聚节点之间均采用单跳的方式进行数据传输，由3.2节可获取3种算法一轮能耗的平均值。网络的总能量为50J，从而得到3种算法的理论最长轮数和实际达到轮数占理论最长轮数的百分比，具体数据如表2所示。由表2可知LEACH算法网络正常工作的时间可达到理论最大值的79.2%，LEACH-ED算法网络正常工作的时间可达到理论最大值的86.9%，而改进LEACH-RE算法的正常工作时间可达到理论最大值的91.0%，验证了LEACH-RE算法对于提高网络正常工作时间的有效性。

表2　算法比较

4　结论

本文主要针对可靠性要求比较高的应用场景，改进LEACH算法产生簇首不稳定和成簇不均匀的问题，采用分时分簇方式使簇首在网络中的均匀分布，且不额外增加网络的能耗，均衡化网络的负载。仿真表明LEACH-RE算法较LEACH算法在延长网络正常工作时间和均衡网络能量消耗有了很大的改进，验证了其延长网络正常工作时间的有效性。

［1］赵丽霞，纪松波.无线传感器网络在智能交通中的应用［J］.物联网技术，2012，2（6）：25-27.

［2］李建洲，王海涛，陶安.一种能耗均衡的WSN分簇路由协议［J］.传感技术学报，2013，26（3）：396-401.

［3］AKHTAR A M，NAKHAI M R.Power aware cooperative routing in wireless mesh networks［J］.Communications Letters，IEEE，2012，16（5）：670-673.

［4］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks［C］//Systemsciences，2000. Proceedings of the 33rd annual Hawaii international conferenceon.IEEE，2000，2:10.

［5］顾相平，孙彦景，钱建生.一种改进的无线传感器网络LEACH-ED算法［J］.传感技术学报，2008，21（10）：1770-1774.

［6］刘玉华，赵永锋，许凯华，等.无线传感器网络LEACH协议的改进［J］.计算机工程与应用，2010，46（17）：117-120.

［7］唐甲东，蔡明.基于LEACH协议的能耗均衡路由算法［J］.计算机工程，2013，39（7）：134-136.

［8］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNANH.Anapplication-specific protocol architecturefor wirelessmicrosensornetworks［J］.WirelessCommunications，IEEE Transactionson，2002，1（4）：660-670.

［9］陈树，徐圆.基于分簇和覆盖优化的改进LEACH协议［J］.计算机工程，2014，40（11）：97-100.

［10］DIAMOND S M，CERUTI M G.Application of wireless sensor network to military information integration［C］//Industrial Informatics，2007 5th IEEE International Conferenceon.IEEE，2007，1：317-322.

［11］CHEN G，LI C F，YE M，et al.An unequal cluster-based routing strategy in wireless sensor networks［J］.Wireless Networks（JS），2009，15（2）：193?207.

［12］吴小兵，陈贵海.无线传感器网络中节点非均匀分布的能量空洞问题［J］.计算机学报，2008，31（2）：253-261.

［13］万青苗，张浩平，王强，等.无线传感器网络LEACH协议的改进研究［J］.电脑知识与技术，2012，32（8）：7679-7701.

Atime-division and Clusteringalgorithm of LEACH Based on Residual Energyof Sensor Nodes

WU Biao，YU Jian，YI Ren-jie
（401 Laboratory，Electronic Engineering Institute，HeFei 230037，China）

For the problemof effective routing protocol in wireless sensor network，this paper puts forwardan time-division and clusteringalgorithm of LEACH based on the Residual Energy（LEACHRE）of sensor nodes.By time-cluster and clustering method，LEACH-RE solves the problem of unstable cluster-head number that exists in LEACH algorithm without increasing the energy consumption of the network.In addition，the distribution of clusters and energy consumption in the network are well balanced.The normal lifetime of the sensor network is effectively extended.Simulations improve the effectiveness of the algorithm.

wirelesssensornetworks，time-divisionandclustering，LEACH，network normal lifetime

E917

A

1002-0640（2016）10-0084-05

2015-08-13

2015-09-16

电子工程学院院控基金资助项目（KY13A206）

吴标（1991-），男，安徽亳州人，硕士研究生。研究方向：无线传感器网络节能路由协议。