基于剩余能量的LEACH算法优化的研究

摘要：针对LEACH算法中存在的节点能耗分布不均衡问题，提出一种新的成簇路由方案。在参考 LEACH 路由算法的基础上，引入剩余能量，建立新的簇头选举机制。仿真试验结果表明，该算法在网络生存时间和负载均衡方面较已有算法有较大的提高。

关键词：无线传感器网络；剩余能量；负载均衡

中图分类号：TP311文献标识码：A文章编号：1009-3044(2011)26-6370-02

无线传感器网络是由部署在监测区域内能进行无线通讯交流的大量无线传感器节点组成的一个自组织网络。由于可自组织网路、环境适应能力强等特点无线传感器网络在军事、交通、矿业、农业领域具有广阔的应用前景。但构成无线传感器网络的传感器节点通常能量有限，因此为了最大限度地延长网络生存时间，设计一种能量有效的路由协议来适应无线传感器网络的特点，以降低节点能耗和提高网络生命期为目标的网络协议已经成为无线传感器网络研究的热点之一。

1 研究基础和相关工作

路由协议是无线传感器网络的重要技术之一，它的作用是将数据由源节点传送到目的节点，因此路由协议的性能和整个网络的性能密切相关。目前，路由协议可以分为平面路由协议和分层路由协议。

在平面路由协议中，节点间地位是平等，是通过局部操作和反馈信息来生成路由的。典型的平面路由协议有: SPIN[1]、Directed Diffusion、Rumor、SAR等。分层路由协议中通常将网路节点划分为若干簇，由簇头负责管理簇内节点。典型的分簇路由协议有: LEACH[2]、TEEN[3]、PEGASIS、CEFL、DAEA等。

1.1 LEACH算法简介

低功耗自适应分簇算法LEACH首次提出分簇的思想，也是分层路由协议中最重要和最具代表性的算法。在LEACH算法中，节点自组织成不同的簇，每个簇只有一个簇头。所有非簇头节点将自己的数据发给所属簇的簇头节点，簇头节点在数据融合后将数据发送给基站。其基本思想是在运行过程中不断的循环执行簇的重构过程，每个簇重构过程由“轮”的概念来描述，每一轮由两个阶段组成：簇的建立阶段和传输数据的稳定阶段。

在簇的建立阶段，每个传感器节点先生成0-1之间的随机数，如果生成的随机数小于阀值T(n)，那么这个节点就被选为簇头，阈值的大小由下式确定：

（1）

T(n) 表示为：式中，P 是簇头在所有节点中所占的百分比，r是选举轮数，G是这一轮循环中未当选簇头的节点集合 。

如果这个数小于簇头当选阈值 T(n)，那么则该节点就当选为本轮循环的簇头；反之则为簇内普通节点。节点当选为簇头以后，广播消息告知其他节点自己是新簇头；非簇头节点根据收到的广播消息的信号强弱决定要加入的簇，并向簇头发送加入簇的请求。簇的建立完成后，开始进入传输数据的稳定阶段。

1.2 LEACH算法分析

尽管LEACH能够提高网络的生存时间，但是协议所使用的假设条件仍存一些问题：

1）在LEACH算法中的假设条件是所有节点都可与汇聚节点sink直接通信，若节点与sink节点距离较远的情况下能量消耗增大，不适合在大规模的无线传感器网络中应用[4]。

2）簇头的形成是随机的，此时在节点之间传送数据时，可能加大能量的消耗[5]。

3）簇头选定之后，要向网络覆盖的所有区域发送广播信息，增加了节点间的通信量。这个过程要消耗相当多的能量。

4）每开始新的一轮工作，都要重新选举聚类首领,重新划分聚类。这一过程每个节点都要参与，需要消耗大量的能量。

2 基于LEACH算法的优化

本文针对一些问题，提出一种基于LEACH算法优化的方法。将能量因素纳入考虑，改进了其计算方法。

2.1 前提条件和算法

本文是基于LEACH的优化算法，实验环境是被监测区域已知且传感器节点均匀分布，sink节点固定的情况。具体条件如下：

1) 所有传感器节点是平等的，初始能量相同。

2) 传感器节点与sink节点的位置是固定不变的。

3) 传感器节点向任意方向发送数据的功率是相同的。

4) 本算法只考虑数据处理和数据传输的能量消耗。

本文所提出的算法与基于LEACH的固定聚类算法相似，在簇头选举机制中引入剩余能量。公式如下：

（2）

其中，Eelse表示节点剩余能量，E0表示节点初始能量，Nr表示节点的通讯范围内节点数，nr表示Nr内剩余能量大于簇内平均剩余能量的节点数。由于综合考虑了节点能量和阈值大小对簇头选取的影响，式(2)的改进有效地弥补了式(1)的缺陷。

2.2仿真实验

本文利用matlab作为分析工具，设计了以下场景：传感器节点总数为100，均匀分布在100×100的被测区域中，sink节点位于(50, 175)。所有节点初始能量相同，初始值为2 J，数据包长度为500 B，发送和接收数据的能量消耗为50 nJ/bit，放大电路功耗为100 pJ/(bit・m-2)。通过仿真实验对提出的算法进行分析，以评价该算法的性能。

图1是改进后算法和LEACH算法的仿真结果进行的比较。从图中可以观察到改进后的协议在不同的节点数目情况下都明显的延长了网络的生命周期；且网络越大，网络的生命周期延长得相对越多，在100个节点时网络的生命周期延长达到了 40%左右。

3 结束语

在LEACH协议的基础上提出了基于剩余能量的无线传感器网络节能的优化分簇算法。在簇首选择机制上，根据节点剩余能量和簇内平均剩余能量，让剩余能量大的节点尽可能优先担任簇首，减少了算法的复杂度，减少了簇内节点之间不必要的通信能耗，有利于节点能量的同步消耗，从而有效地延长了整个网络的生命期。模拟实验表明，优化后的簇首选择机制可以有效延长网络生存时间。

参考文献：

[1] Heinzelman Kulk J,Balak Rishnan H.Adaptive protocols for information dissemination for wireless sensor networks[C]//Proc of ACMConference on Mobile Computing and Networking,Washington,USA,1999:174-185.

[2] Heinzelman W,Chandrakasan A,Balakrishnan H.Energy -efficient communication protocol for wireless microsensor networks [C]//TheHawaii Int’l Conf System Sciences.Hawaii：IEEE Computer Society,2000.

[3] Wendi B Heinzelman,Anantha P Chandrakasan,Hari Balakrishnan.An applicantion-specific protocol architecture for wireless micro-sensor networks.

[4] Zhou Z,Zhou S,Cui S,et al. Energy-efficient cooperative communication in a clustered wireless sensor network [J].IEEE Transactions on Vehicular Technology, 2008,57(6):3618-3628.

[5] 乐世成,王培康.无线传感器网络中的节能路由算法[J].计算机工程,2008,34(7):113-117.