WSN中LEACH协议的改进与研究*

张 浩，赵建平

0 引 言

随着传感器技术、嵌入式计算技术、微电子技术和无线通信技术的日趋成熟，无线传感器网络（Wireless Sensor Networks，WSN）[1]应 运 而 生，并广泛应用于军事、环境参数监测与采集、智能家居、温室大棚等领域[2]。无线传感器网络是由数量众多、体积微小、仅电池供电的传感器节点组成，并以自组织方式互相协同工作的分布式感知网络。由于传感器节点能量有限且大多部署在电池不易更换的环境中，因此如何均衡网络能耗、最大程度延长网络生命周期成为首要问题[3]。路由协议作为延长网络生命最有效的方式之一[4]，受到国内外研究人员的广泛关注。研究表明，层次型路由协议相比较于平面路由，解决了其建立、维护路由开销大、信息冗余大、数据传输跳数多、网络规模小的问题。而LEACH[5]协议是层次型路由协议最具代表性的。所以，后续的一系列协议都是对LEACH协议某种程度的改进[6]。

相较于一般的平面多跳路由协议和静态分层算法，LEACH协议可以将网络周期延长15%[7]，但尚存在不足，主要体现在：

①LEACH协议假定所有的节点都可以与汇聚节点直接通信，因此该协议无法在大规模WSN中应用[8]；

②在簇头的竞选阶段没有考虑当选为簇头的节点可能剩余的能量较低，大大缩短了网络的生命周期[9]；

③没有考虑簇头的位置，选出的簇头可能集中在某一个区域，导致一些普通节点周围没有任何簇头节点。

本文针对无线传感器网络LEACH（Low Energy Adaptive Clustering Hierarchy）算法中簇头随机选取造成网络能耗过快、网络生命周期变短的问题，提出一种基于节点剩余能量和距离基站距离[10]的簇头选取算法（LEACH-ED）。实验验证结果表明，综合考虑节点剩余能量和到基站距离的LEACH-ED算法，相比较于基本的LEACH算法，系统的整体耗能减小，网络生命周期延长60%，且网络的扩展性能更好。

1 LEACH协议概述

LEACH是最早提出的分簇路由协议，奠定了分簇路由协议的基本思想。在运行过程中，它不断执行簇的重构过程。重构过程以“轮”为单位[11]，分为两个阶段：簇的建立阶段和数据传输的稳定阶段。为了节省网络开销，稳定阶段的持续时间要大于建立阶段持续的时间。簇的建立阶段主要包括簇头节点的选择、簇头节点的广播、簇头节点的建立和调度机制的生成；数据传输稳定阶段主要负责数据的融合和传输。在所有数据传输完成后，新的一轮开始，网络需要重新选择簇头。

1.1 簇形成过程

1.1.1 簇头的选择

每一个传感器节点产生一个（0，1）之间的随机数，然后与式（1）生成的阈值T(n)进行比较。如果节点产生的随机数小于T(n)，则此节点可能当选为簇头。如果最终当选簇头，则将当选为簇头的消息广播告知网络其他节点。

式中，p为簇首的比例，r表示网络当前运行的轮数，G表示在最后的1/p轮中还没有成为簇首节点的集合。在r=0时，每个节点都以p的概率成为簇头，经过1/p-1轮后阈值变为1。

1.1.2 簇的建立

簇头选举过程完成后，成为簇头的节点广播自己成为簇头的消息到整个网络。该消息主要包括簇头的ID、位置等。普通节点根据接收到消息的强弱选择强度最大的簇，并向对应的簇头返回消息，确保加入距离自身最近的簇头。簇头根据簇内包括的节点个数，采用TDMA方式为簇中每个节点分配向其传输数据的时间点。

在数据传输稳定阶段，簇内节点根据簇头分配的数据传输时间点，定时唤醒。此时，向簇头传输数据，其余时间处于休眠状态，以便降低耗能。整个过程中，簇头始终处于开启状态，以接收本簇成员的数据。将本簇成员数据和自身采集的数据融合后，簇头采用载波侦听同步CSMA的方式，将融合后的数据发送到汇聚节点，避免了簇头同时向汇聚节点发送数据时的阻塞现象。所有簇首完成数据传送后，新的一轮开始，网络重新进入簇建立阶段。

1.2 网络能耗模型

LEACH算法的能耗模型定义为：

ETx是发送k比特数据、传输距离d的能耗，ERx则是接收k比特数据的能耗，Eelec是收发1 bit数据电路消耗的能量，εfs表示自由空间放大器传播损耗，εmp表示多径衰减放大器传输损耗，d0为常数且

2 LEACH协议改进算法

2.1 改进算法网络模型

改进后的算法采用的无线通信模型与LEACH协议一致，传感器节点随机分布在已知区域内，普通传感节点能够感知、采集数据并发送给簇头节点，簇头节点融合、整理后发送给汇聚节点。在设计算法时，同时做以下假设：

①传感器节点初始能量相同且有限；

②传感器节点和汇聚节点位置确定后，在剩余网络周期内不再移动；

③节点在发送能量时，能够自动调整发射功率以节省能量；

④汇聚节点位于已知区域外。

2.2 改进算法描述

LEACH-ED基于LEACH协议，考虑加入剩余能量和到汇聚节点的距离因素后提出的新算法，其中新算法在簇的建立、稳定数据传输阶段与最基本的LEACH算法相同，最主要的区别体现在簇头选择和更新过程。思想如下：首先计算基于存活节点数的最佳簇头个数，假设在当前网络中有Nr个节点存活且随机分布在M×M的区域内，这块区域被平分为K个簇，此时每个簇中含有的节点个数为Nr/K（包含一个簇头节点和Nr/K-1个普通节点），则最佳簇头的个数就等于所分成的簇数。根据节点的能耗模型，簇头传输l bit的数据所消耗的能量为：

每一个簇成员节点消耗的能量为：

则每一个簇收发l bit的数据时所消耗的最大能耗是：

一帧中，所有的Nr个节点消耗的总能量为：

设sink节点的坐标为(x0, y0)，当前节点的坐标为(xi, yi)，则当前节点到sink节点的距离为：

每个簇所占据的面积约为M2/K，假设是一个簇头节点位于簇的中间且密度为ρ(x, y)的任意形状的区域。根据节点的通信半径r= M /ð，则普通节点到簇头节点的距离为：

对式（9）进行极坐标变换。令x=rsinθ、y=rcosθ，其中，代入得：

将式（8）、式（10）代入式（6），然后再代入式（7），可得整个网络的总能耗为：

要使整个网络的能耗最低，将Etotal对K求导并让其等于零，可得到理想的簇头数：

改进后的算法将某一节点的剩余能量与网络平均能量的比值作为考虑因素，使剩余能量最大的节点能够优先竞选选为簇头。选用当前节点到sink节点距离与所有活着的节点到sink节点较近的节点优先被选举为簇头。改进后的T(n)为：

其中 α, β∈(0,1)且 α+β=1，同时有：

通过综合考虑节点的剩余能量与网络的平均能量的比值、到节点到汇聚节点的距离与节点的汇聚节点的距离的比值，可以使剩余能量大、距离汇聚节点近的节点优先竞选成为簇头，从而使网络的能耗更加均衡，延长网络的生命周期。

3 仿真分析

为了验证LEACH-ED算法性能是否高于LEACH算法，选择MATLAB平台，在100 m×100 m的网络区域内随机分布100个节点进行仿真。分别从网络节点存活数、死亡数、数据包接收数等方面，对改进后的算法性能进行评价，参数设置见表1。

表1 仿真参数

在一定的环境下，LEACH-ED算法随着运行轮数的增加，网络中死亡节点数目与存活节点数目的变化人别如图1、图2所示。其中，LEACH算法在2 000轮时出现了大面积死亡，而LEACH-ED算法大面积死亡的时间是3 200轮；在网络生命周期上，LEACH-ED算法比LEACH延长了60%。LEACH存活的数目在2 100轮全部死亡，而LEACH-ED存活的时间达到了4 100轮。所以，改进算法提高了节点的存活率，延长了网络寿命。

图1 节点死亡数-工作轮数

图2 节点存活数-工作轮数

图3 为基站收到的数据包数与工作轮数的关系变化曲线。可以看出，相比LEACH算法，改进后的LEACH—ED算法在相同的轮数下接收的数据包数大大提升，提高了网络的工作效率。

图3 基站收到的数据包数-工作轮数

图4 为簇头数与工作轮数的关系变化曲线。从图4可以看出，在相同的轮数下，改进的算法簇头数更多，簇头分布更加均匀，均衡了网络能耗。

图4 每一轮的簇头数-工作轮数

图5 为不同LEACH协议的网络能耗测试结果。

图5 能量消耗-工作轮数

从图5可知，随着轮数不断增加，两种LEACH协议的网络总能耗逐渐增加；但对于LEACH协议，LEACH-ED协议的能耗增加更为缓慢，节能效果明显。

4 结 语

本文对无线传感器分簇路由算法LEACH进行改进，提出了改进后的路由协议——LEACH-ED。在簇头竞争阶段，LEACH-ED对影响簇头选举的阈值进行改进，改进后的阈值综合考虑了节点的剩余能量、到基站的距离，使改进后的簇头选举更加合理，簇头分布更加均匀，有效减少了簇头选举能耗。仿真结果表明，相比较于LEACH协议，LEACHED有效均衡了网络的能量负载，使节点的存活率更高，延长了网络的生命周期。

[1] 赵丽霞,纪松波.无线传感器网络在智能交通中的应用[J].物联网技术,2012,2(06):25-27.ZHAO Li-xia,JI Song-bo.The Application of Wireless Sensor Network in Intelligent Transportation[J].Internet of Things Technology,2012,2(06):25-27.

[2] 孙利民,李建中,陈渝等.无线传感器网络[M].北京:清华出版社,2005:1-25.SU Li-min,LI Jian-zhong,CHEN Yu,et al.Wireless Sensor Network[M].Beijing:Tsinghua Press,2005:1-25.

[3] KATIYAR V,CHAND N,GAUTAM,et al.Improvement in LEACH Protocol for Large-scale Wireless Sensor Networks[C].Proceeding of the 2011 Emerging Trends in Electrical and Computer Technology Piscataway,2011:1070-1075.

[4] 石为人,柏荡,高鹏等.无线传感器网络簇头半径自适应调节路由算法[J].仪器仪表报,2012(02):1779-1785.SHI Wei-ren,BAI Dang,GAO Peng,et al.Wireless Sensor Network Cluster Head Radius Adaptive Routing Algorithm[J].Chinese Journal of Scientific Instrument,2012(02):1779-1785.

[5] 王臻跃.基于LEACH的改进路由算法[J].软件导刊,2015(03):114-116.WANG Zhen-yue.Improved Routing Algorithm based on LEACH[J].Software Guide,2015(03):114-116.

[6] 吴标,余剑.基于节点剩余能量的分时分簇LEACH改进算法[J].火力与指挥控制,2016(10):84-88,93.WU Biao,YU Jian.The Algorithm of LEACH Improvement based on the Residual Energy of Nodes is Proposed[J].Fire and Command Control, 2016(10):84-88,93.

[7] Nayebi A,Sarbazi-Azad H.Performance Modeling of the LEACH Protocol for Mobile Wireless Sensor Networks[J].J. Parallel Distrib. Comput.,2011(02):4.

[8] Heinzelman W R.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].Proceedings of the 33rd Ha-waii International Conference On System Sciences,IEEE Computer Society,2000.

[9] 潘霞,于宏毅,张霞.一种基于LEACH的能耗均衡分簇算法[J].电路与系统学报,2012,17(01):75-80.PAN Xia,YU Hong-yi,ZHANG Xia.A Balanced Clustering Algorithm based on LEACH[J].Journal of Circuits and Systems,2012,17(01):75-80.

[10] 李建坡,钟鑫鑫,徐纯.无线传感器网络动态节点定位算法综述[J].东北电力大学学报,2015(35):52-58.LI Jian-po,ZHONG Xin-xin,XU Chun.Wireless Sensor Network Dynamic Node Location Algorithm Overview[J].Journal of Northeast Dianli University,2015(35):52-58.

[11] 过文亮,施惠昌.一种新型的自适应最佳簇首分簇算法[J].微计算机信息,2009,25(02):183-184.GUO Wen-liang,SHI Hui-chang.A Novel Adaptive Optimal Cluster First Clustering Algorithm[J].Microcomputer Information,2009,25(02):183-184.