一种LEACH协议的多级分簇改进算法

罗 冰，黄玉清

(西南科技大学信息学院，四川 绵阳 621010)

1 概述

无线传感器网络(Wireless Sensor Network,WSN)是集信息采集、信息传输、信息处理于一体的智能信息系统，它综合了传感器技术、嵌入式技术、现代网络及无线通信技术、分布式信息处理技术等，可用于环境检测、医疗护理、军事等众多领域。无线传感器网络节点具有体积小、能量有限且电池不宜更换等特点。因此，采用高效的功率控制策略，减少不必要的能量消耗，延长网络生存时间是无线传感器网络的一个重要研究课题[1]。

LEACH(Low Energy Adaptive Clustering Hierarchy)[2]协议是第一个提出数据聚合的层次路由协议，采用动态分簇，各个节点以循环的方式随机担任簇头，由簇头节点负责收集簇内其他节点的数据，进行数据融合，直接发送到sink节点，以此均衡节点的能量消耗。与之前的平面多跳路由协议以及静态分簇算法相比，LEACH 协议可以将网络生存寿命延长15%左右[2]。

本文提出一种LEACH 协议的多级分簇改进算法。采用多级聚簇的思想，并结合传感器网络的节能策略，对LEACH 协议进行改进。

2 LEACH 协议

LEACH 协议的核心思想是使用分布式算法，传感器节点通过自主聚簇，并在簇内通过随机选举产生簇头节点。簇头节点收集簇内其他传感器节点数据并进行数据融合，最终传送到sink 节点。

在LEACH 的运行过程中，通过“轮”的概念表示每个簇的循环重构。每轮分为2 个阶段：构建阶段和稳定阶段。(1)在构建阶段，随机选举簇头并进行聚簇。(2)在稳定阶段，簇内节点向簇头节点发送数据，簇头节点进行数据融合并向sink 节点传输。

2.1 构建阶段

各节点产生一个在[0,1]之间的随机数，如果该数小于T(n)，则该节点当选为簇头。T(n)的计算方法如下：

其中，n 为总节点数；p 为网络中簇头数与总节点数的百分比；r 为当前的选举轮数；G 为最近1/p 轮不是簇头的节点集合。当选为簇头的节点向网络广播消息时，在其他节点接收到广播消息后，依据广播消息的信号强度，确定要加入的簇，使用载波监听机制向各自的簇头节点发送通知。

2.2 稳定阶段

接收到通知消息的簇头节点，为其簇内的普通节点创建时分多址(Time Division Multiple Access,TDMA)时隙表。普通节点在其各自的时隙内，将采集的数据传输到簇头节点。在所有数据传输完毕后，簇头节点进行数据融合，并将其直接传输到sink 节点，结束本轮循环，准备开始下一轮选举。LEACH 是最简单的层次路由协议，每轮随机选取簇头节点，避免了簇头因能量消耗过多而死亡，可以有效降低无线传感器网络能量消耗，延长网络生存寿命。但是仍然存在一些缺点：选举产生的簇头节点是不均匀分布的，会导致一部分簇头节点集中分布在某一区域，而其他区域没有簇头节点[3]。

LEACH 协议要求任意2 个节点可以直接互相通信，要求节点具有较大功率通信能力、扩展性差，且簇头节点直接将数据传输到sink 节点，因此，不适用于sink 节点距离传感器区域较远的大规模网络。LEACH 协议假设簇头节点为簇内每个普通节点创建TDMA 时隙表，尽管有些节点可能没有数据需要传输，从而造成不必要的开销[4-5]。

3 LEACH 协议改进算法

针对LEACH 协议的不足，出现很多对其改进的算法，主要涉及T(n)的计算、簇头数的优化、簇内节点数的计算等[6-7]。本文在LEACH 协议的基础上，通过采用多级分簇[8]，减少与sink 节点直接通信的簇头节点数量，从而降低能量消耗、均衡节点能量、延长网络生存周期。

所有传感器节点随机分布在指定区域并作如下假设：所有节点拥有相同的初始能量；任意2 个节点可以直接相互通信[9]；在节点部署之后，不会随时间移动，一直保持静止；sink 节点位于离传感器节点区域较远的位置。

3.1 多级分簇结构

依据簇头数与总节点数的百分比p，确定将网络划分为小单元的个数。在指定的场景中，按照所确定的单元个数，将网络进行均匀划分从而确定不同单元的范围，各个节点通过判断其坐标确定其所属单元。

在每个划分好的小单元中，分布若干传感器节点，每个单元通过选举产生一个二级簇头节点，单元内其他节点将数据传输到二级簇头节点进行数据融合。通过二次选举，在二级簇头中产生若干一级簇头节点，二级簇头节点将数据传输到最近的一级簇头节点进行数据融合，最终由一级簇头节点将数据直接传输到sink 节点。网络聚簇情况示意图如图1 所示。

图1 网络聚簇情况示意图

通过划分网络单元，保证簇头节点的均匀分布；通过采用多级分簇[10-11]，减少与sink 节点直接通信的节点数量，从而均衡网络能量消耗，延长网络生存周期。

3.2 簇头选举机制

在网络建立后，进行簇头选取。在第一轮的选举中，采用与LEACH 协议相同的方法，在划分的每个单元中，每个节点随机产生一个[0,1]之间的随机数，并按式(1)计算T(n)[12]。若该随机数小于T(n)，则该节点当选为二级簇头。同理，在二级簇头节点中随机产生[0,1]之间的随机数并与T(n)比较，若小于T(n)，则当选为一级簇头。

在之后的选举中，以节点剩余能量为标准；在每个单元中，各个节点将其剩余能量情况发送到二级簇头，由二级簇头动态选择具有最多剩余能量的节点为新的二级簇头。同理，二级簇头将其剩余能量情况发送到一级簇头并由一级簇头选取剩余能量最多的节点为新的簇头。在数据传输阶段，各级簇头节点采用与LEACH 协议同样的方法为其簇内各个节点创建TDMA 时隙表，各个节点在指定的时隙内，进行数据传输。簇头节点收到数据后进行数据融合，并向上一级节点传输，最终由一级簇头传输到sink 节点。

簇头选举算法如下：

定义 Ui表示普通节点；CH(Ui)表示二级簇头节点；MCH(Ui)表示一级簇头节点；A(Ui)表示普通节点产生的随机数；A(CHi)表示二级簇头节点产生的随机数；E(Ui)表示节点剩余能量。

算法描述如下：

通过上述方法，对LEACH 协议进行改进，采用多级分簇减少与sink 直接通信的节点数目，通过引入剩余能量进行簇头节点选取，均衡节点能量消耗。

4 仿真分析

4.1 仿真场景与参数

在100 m×100 m 区域内，随机分布100 个传感器节点，所有节点同构，拥有同样的初始能量且节点静止不动，sink节点固定在(40,200)。取p 为0.15，即将网络划分为15 个小单元，并通过计算坐标，确定不同单元的范围。各个节点通过其坐标确定其所属单元。节点初始能量为0.5 J，传输能耗和接收能耗为50 nJ/bit，数据融合能耗为5 nJ/bit，数据包大小为4000 bit。仿真采用Matlab R2007a 进行，将改进后的协议与LEACH 协议进行对比，验证其性能。

LEACH 协议聚簇分布如图2 所示。

图2 LEACH 协议聚簇分布

利用本文算法改进LEACH 协议，得到的聚簇分布如图3 所示。LEACH 协议由簇头节点直接将数据传输到sink节点，改进后的协议经过2 次选举，减少了与sink 节点直接通信的节点数目。

图3 改进协议的聚簇分布

4.2 节点存活数比较

存活节点数比较如图4 所示，LEACH 协议在第170 轮附近的时候，出现第一个死亡节点，本文算法第一个死亡节点出现在第330 轮附近。LEACH 协议在第950 轮左右，节点全部死亡，而更改后的协议，在第1000 轮运行完毕之后，还有若干个存活节点。由此说明，本文算法可以有效避免节点过早死亡，达到延长网络生存周期的目的。

图4 存活节点数比较

4.3 能量消耗情况比较

网络剩余能量比较如图5 所示。

图5 网络剩余能量比较

从图5 可以看出，本文算法可以降低网络能量消耗，延长网络生存周期，这是因为采用多级聚簇，减少了与sink节点直接通信的节点数目，同时，在选举簇头节点时，考虑了节点剩余能量，选取具有最多剩余能量的节点为簇头，所以相较于LEACH 协议，更有利于网络能量均衡。

4.4 网络规模情况比较

当传感器节点数目增加到200 个时，图6 为存活节点数比较。从图6 可以看出，当网络规模增加到200 节点时，LEACH 协议在第230 轮左右，出现第一个死亡节点，而本文算法在第420 轮左右才出现第一个死亡节点。由此说明，当网络规模增大时，本文算法仍然可以有效地减少能量消耗，延长网络生存周期。

图6 存活节点数比较(200 节点)

5 结束语

本文提出一种LEACH 协议的多级分簇改进算法。采用划分网络的方法，保证簇头在整个网络内均匀分布，通过二次聚簇，减少与sink 节点直接通信的簇头节点数，并在簇头选举过程中引入节点剩余能量，从而更有效地保证了网络的能耗均衡。仿真结果表明，该算法均衡了节点能耗，避免了节点过早死亡，有效改善了网络性能。但目前研究都是基于理想环境，下一步将考虑环境干扰因素进行深入研究。

[1]Akyildiz I F,Sankarasubramaniam Y,Su W,et al. Wireless Sensor Networks: A Survey[J]. Computer Networks,2002,38(4): 393-422.

[2]Heinzelman W R,Chandrakasan A,Balakrishnan H. Energy Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. [S. l.]: IEEE Computer Society,2000.

[3]Kumar N,Kaur J. Improved LEACH Protocol for Wireless Sensor Networks[C]//Proceedings of the 33rd Hawaii International Conference on System. Washington D. C.,USA:IEEE Computer Society,2000.

[4]Yektaparast A,Nabavi F H,Sarmast A. An Improvement on LEACH Protocol[C]//Proceedings of International Conference on Advanced Communication Technology. Gujarat,India:[s. n.],2012.

[5]Sharma M,Sharma K. An Energy Efficient Extended LEACH[C]//Proceedings of International Conference on Communication Systems and Network Technologies. Jammu,India:[s. n.],2012.

[6]张 昱. 无线传感器网络的簇头间距自适应HAD-LEACH算法[J]. 计算机工程与应用,2007,43(30): 124-127.

[7]王 法. 无线传感器网络分簇协议LEACH 协议中的簇头选择的改进研究[D]. 成都: 电子科技大学,2008.

[8]Wairagn G R. Extending LEACH Routing Algorithm for Wireless Sensor Network[D]. Kampala,Uganda: Makerere University,2009.

[9]黄加异,程良伟. 一种聚类区域自适应调整的WSN 能耗均衡分簇算法[J]. 计算机应用研究,2012,42(11): 76-79.

[10] 李成岳,申铉京. 无线传感器网络中LEACH 路由算法的研究与改进[J]. 传感技术学报,2010,23(8): 63-67.

[11] 胡星华,骆 坚. 固定簇的LEACH 半径自适应簇头改进算法[J]. 传感技术学报,2011,24(1): 79-82.

[12] 吕 涛,朱清新,张路桥. 一种基于LEACH 协议的改进算法[J]. 电子学报,2011,39(6): 5-9.