基于能耗均衡的LEACH改进方法

张 帅 杨清海 冯友兵

1(西安电子科技大学通信工程学院综合业务网理论及关键技术国家重点实验室 陕西 西安 710071)2(江苏科技大学电子信息学院 江苏 镇江 212003)

0 引 言

无线传感器网络(WSN)作为一种新兴的信息采集技术，具有自组织、部署快捷、高容错性和强隐蔽性等技术优势， 目前已广泛应用于工农业、国家安全、城市监控、空间探索等许多重要的领域[1-4]。而其自组织性使得拓扑控制成为WSN生命期最大化的关键技术[5-7]。

LEACH[8]是最早提出的高效能分簇算法，其以簇为单元向基站传送数据，在执行过程中不断循环进行簇的重构过程，重构过程可以分两个阶段：簇的建立阶段和传输数据的稳定阶段。为节省算法开销，稳定传输阶段的持续时间要大于建立阶段的持续时间。簇的建立过程可详细分成4个阶段：簇头的选择、簇头的广播、簇头的建立和调度机制的生成；稳定传输阶段中，普通节点将采集的数据传送到簇头，簇头对簇中所有节点的数据进行信息融合后再传送给汇聚节点。LEACH很好地解决了传感器节点能耗过大的问题，有效降低了节点能耗。

但LEACH算法存在以下不足：在选择簇头时根据节点随机产生一个0～1之间的随机数选取簇头，而没有考虑节点当前的剩余能量，有可能将低能量节点误选为簇头而加快该节点死亡的速度；同时，簇的数量具有很大的随机性，而过多的簇也会减少分簇的带来的能耗有效性。因此，如何改进LEACH算法的簇头选择机制、优化簇头的数目成为延长网络正常生命周期的关键。

1 相关工作

针对传统LEACH算法在簇头选择机制和簇头数目随机等方面存在的问题，国内外学者作了很多提高其性能的改进。其中，文献[9]提出LEACH-C算法，节点在每一轮开始时先把位置和能量等状态信息发至基站，基站接收到节点状态信息后，先计算网络的能量均值，只有剩余能量大于该值的才可参与簇头的选择，然后基站利用模拟退火算法[10]进行统一分簇，并选出簇头，最后基站广播包含分簇及簇头的信息给各个节点完成入簇过程。该方法实际上是对LEACH算法中参加簇头选择的节点作了一些限制条件，但这种限制极其有限，特别是在节点的平均剩余能量较低时，即使满足LEACH-C算法的条件，也有较大可能出现簇头过早死亡的情况。文献[11]提出一种基于LEACH的簇头成链可靠拓扑控制算法，该算法规定簇头数目为5个，利用PEGASIS算法使簇头成链,并选择剩余能量最多的簇头传送信息给基站。选择簇头时考虑节点的剩余能量，给节点设置一个能量阈值，小于该值则不能当选为簇头。此方法虽提高了网络的健壮性，但却增加了延迟，网络总能量消耗过快。文献[12]提出基于节点剩余能量的分时分簇LEACH改进算法，其通过分时分簇方式，有效克服了传统LEACH算法中簇头数目不稳定的缺陷，且不会额外增加网络的能耗，使得簇头在整个网络中的分布以及网络的能量消耗较为均衡。文献[13]提出基于簇头间距均匀部署的LEACH改进算法，该算法在簇头选择过程中限定簇头间的最小距离，使得选出的簇规模近似均衡，以降低簇内通信能量消耗，为避免网络中各个节点的能量失衡，基于节点剩余能量设定新的簇头选择阈值改进算法，增加剩余能量高的节点成为簇头的概率。通过比较分析，本文算法在选取簇头时考虑节点剩余能量因素，同时采用均衡化的思想，包括与网络能耗相关的最优簇头数目和考虑节点剩余能量的簇头选择阈值，以降低网络节点整体能耗、延长网络生命周期。

2 网络部署

将N个WSN节点随机分布在M×M的监测区域内，构成WSN，其结构如图1所示。为便于分析，全文作如下假设：

(1) 假设监测区域无障碍物；

(2) 基站的能量充足，且固定位于区域中心位置；

(3) 节点保持静止且为同构节点且自身能量已知；

(4) 节点间采用单跳通信。

图1 无线传感器网络部署示意图

3 能耗均衡拓扑控制算法

3.1 通信能耗模型

本文算法无论是汇聚节点(基站)收集网络节点的剩余能量，还是汇聚节点与簇头节点、簇头节点与簇内成员节点之间的通信能耗均采用一阶无线电能耗模型。WSN中汇聚中心(基站)和簇头根据不同的情况使用多径衰减模型和自由空间模型计算发送端和接收端之间在交换信息时的能量消耗[14]。设发送和接收1比特数据的能耗为Eelec，d为发送节点和接收节点之间的距离，则发送l比特的数据包的能耗为:

ETx(l,d)=lEelec+lεfsd2d

(1)

ETx(l,d)=lEelec+lεampd4d≥d0

(2)

接收l比特的数据包的能耗为：

ERx(l)=lEelec

(3)

式中：l为传送数据的长度；d为发送节点和接收节点之间的距离；d0为自由空间模型和多径衰减模型转折的阈值，一般在80米左右;εfs为自由空间模型参数;εamp为多径衰落空间模型参数;Eelec为发送和接收单位比特数据的能耗。

3.2 最优簇头数目

令簇头的数量为k，利用能量消耗模型可以推出最优簇头数目Kopt。

(4)

式中：l为传送数据的长度，单位为bit;dtoBS为簇头和基站的距离，如图1所示。

簇内成员节点的主要任务是将采集感知的信息传送到对应的簇头，本文设置成员节点距离簇头比较近即簇内传输距离较小，故在簇内采用自由空间能耗模型。因此，成员节点的能量消耗为：

(5)

式中：dtoCH为普通节点与簇头之间的距离，如图1所示。

∬r2ρ(r,θ)drdθ

(6)

(7)

(8)

每个簇的能量消耗为:

(9)

故能量总消耗为:

Etotal=kEcluster=

(10)

最后，对Etotal求导k，从而计算出WSN最优簇头数目为：

(11)

式中：N为总节点数；εamp为多径衰落模型系数;εfs为自由空间模型系数;M为布置区域边长;dtoBS是簇头与基站之间的距离。

3.3 基于能量的簇头选择阈值

由于簇的规模和簇头选择对WSN总能耗影响较大：一方面，当簇的规模较小时，易导致WSN能量消耗不合理；另一方面，当簇的规模较大时，簇头转发数据量太大、负担较重，易造成能耗增大，使普通成员节点在单位之间可发送的数据量急速降低。故本文提出的簇头选择机制的改进方法为：

(12)

3.4 算法描述

基于能耗均衡的LEACH改进算法在执行时循环进行簇的重构，仍然和传统LEACH一样按轮(round)进行，每轮依然分成簇的建立阶段和传输数据的稳定阶段。该算法的目标是在每一轮中产生可以实现整个WSN更低能耗的最优数目的簇头，同时，在簇头的选举时充分考虑节点的剩余能量引入簇头选择新阈值，从而使能量消耗更加均衡。

簇的建立可详细分成4个阶段：选择簇头、簇头广播信息、普通节点入簇和生成调度机制。首先，为了使得WSN能耗更加均衡，本文改进算法中由汇聚中心或者基站集中调度产生最优簇头数目Kopt。然后在已经确定最优数目簇头的基础上，通过一种分布式的方法来形成簇，其间节点不受任何中心节点调控而自主决定是否成为簇头。进行选举簇头的过程中，每个节点都要产生一个基于自身剩余能量的簇头选择新阈值T′(n)以及一个0～1之间的随机数，当随机数小于T′(n)，并且考虑该节点在最近的1/P轮中未当选为簇头，则当选为簇头，并发布自己是簇头的公告消息，这样做的目的是具有多能量的节点比能量少的节点更加容易被选举为簇头。簇头被选举之后利用非持续性CSMA MAC协议广播簇头消息(ADV)，其余节点根据自己所收到的广播信号的强弱来判断其归属于哪个簇，然后簇头建立一个TDMA调度为成员节点分配交换的时隙，从而保证数据消息之间没有冲突，并且使非簇头节点的无线电模块在非传输时间内关闭，节省了能量。在稳定传输数据的阶段，WSN普通节点将采集的数据信息发给簇头，簇头进行数据信息融合后发给汇聚节点。具体步骤：

(1) 在M×M监测区域中随机部署N个传感器节点，并在监测区域中心部署汇聚节点或者基站，其结构示意图如图1所示。

(2) 无线传感器节点向整个网络广播自身信息。

(3) 根据式(11)确定最优簇头数目。

(4) 根据最优簇头数目Kopt和WSN中已经成为簇头的次数来确定簇头。具体的选择方法是：每个WSN节点产生一个0～1之间的随机数，与将随机数与式(12)所示的阈值进行比较，若小于阈值，则当选为簇头。

(5) 簇头确定之后向全网广播簇头消息，其余节点接收消息，并向距离最近的簇头发送加入消息，完成簇的建立。

(6) 簇头采用TDMA为成员分配交换数据的时隙。

(7) 数据稳定传输阶段，成员节点将采集信息发给簇头，簇头将信息融合后再发给基站。

(8) 进入下一轮，重复步骤(3)-步聚(7)。

4 仿真与结果分析

4.1 仿真参数

设在100 m×100 m的区域中随机部署N个传感器节点，其中汇聚节点/基站位于区域中心(50，50)。其他仿真参数的设置参考文献[14]。

表1 仿真参数

4.2 仿真结果分析

为分析节点消耗的能量是否均衡，对网络已出现节点死亡后的各轮次死亡节点数量进行对比分析。仿真发现两种算法在100轮时均已经出现了死亡节点，图2给出了本文改进算法和传统LEACH算法在第100轮时，死亡节点和工作节点的分布情况，很显然本文改进算法死亡节点数量远远少于传统LEACH算法。

(a) 传统LEACH算法

(b) 本文算法图2 第100轮时死亡节点分布情况

图3为100个节点在同一随机分布下，使用本文算法和传统算法的死亡节点数量的变化趋势，可以看出，传统LEACH算法大概在65轮左右出现第一个死亡节点，随后死亡节点的数量急剧上升，且节点大面积死亡。而本文改进算法第一个死亡节点出现在约70轮，且随着工作轮数的增加，死亡节点的数量呈平缓上升趋势，说明使用本文改进算法延迟了第一个节点时间，且节点能耗更加均衡。

图3 死亡节点数量变化趋势

为了避免单次仿真的偶然性，图4给出两种算法在多次仿真以及同一随机分布情况下第一个节点死亡的轮数，可以看出，本文改进算法第一个节点死亡时间始终晚于传统算法，说明整个网络的能耗更加均衡，有效延长了网络的生命周期。

图4 N=100，第一个节点死亡的轮数(first_dead)

5 结 语

本文在选取簇头时考虑节点剩余能量因素，同时采用均衡化的思想来选取簇头，即从最优簇头数目和基于能量的簇头选择阈值两个方面入手，对LEACH算法进行了改进。仿真实验结果表明，本文算法与传统LEACH算法相比，降低了WSN节点的整体能耗，延长了网络使用寿命。