LEACH协议的改进与仿真分析*

汤 玉，汪学明

（贵州大学 计算机科学与信息学院，贵州 贵阳 550025）

0 引言

无线传感器网络（WSN)由随机布设在监测区域内大量廉价微型传感器节点组成，是一个多跳的自组织网络系统。与移动自组织网络(AdHoc)相比，WSN具有节点数量大、能量受限、以数据为中心、拓扑结构动态变化等特点，使得一些为传统固定网络和AdHoc网络设计的路由算法不适合无线传感器网络的特点和应用要求[1]。由于WSN节点采用微型电池供电，节点能量有限且能量不可补充，设计节能有效的路由机制能延长整个网络的生存周期，因此合理的路由协议是无线传感器网络研究的重点问题[2]。

当今的路由结构主要有平面式和分层式。分层路由在节点的组织管理和网络扩展性方面都比平面路由要好。层次路由协议中，无线传感器网络被划分成多个簇，每个簇由一个簇头节点及多个簇内成员节点构成，多个簇头形成高一级网络。在高一级网络中，又可以再分簇，再次形成更高一级网络，一直到最高级的汇聚节点为止[3]。簇的形成解决了平面路由的路由开销大、维护较大的路由表、占用较多的存储空间的缺点。LEACH协议是分层协议中最早提出也是最具有代表性的协议，采用自适应、随机分布、自组织的成簇方式，数据通信采用局部控制方法，采用低能耗MAC协议和信息压缩法、除冗余信息的处理技术实现节能的目的。

廖明华等提出一种改进的簇头选举算法LEACH-ECHC，当所有簇头的剩余能量最小值小于某个阈值时，进行全网选举，当簇头能量小于该簇剩余能量的平均值时，进行簇内选举，并对簇头产生的阈值进行优化[4]。张震等提出利用PEGASIS算法使簇头成链，并选择剩余能量最多的簇头传送信息给基站。在选择簇头时，考虑节点的剩余能量，给节点设置一个能量阈值，小于该值则不能当选为簇头，因此提高了网络的健壮性[5]。还有很多有关基于 LEACH协议的改进算法，很好地提高了网络某些方面的性能。

1 LEACH协议算法

LEACH协议采用分簇思想将网络中的节点分成很多簇，每个簇具有一个簇头，簇内的非簇头节点采集到数据后直接发送给该簇的簇头节点，簇头节点融合簇内成员发送来的数据后，将数据直接发送给基站。簇的形成是周期性的，称为轮。每轮循环都包括两个阶段，第一个阶段完成簇的组成，第二个阶段负责稳定的数据通信。一轮完了重复进入下一轮工作。

1.1 簇的组成

LEACH算法每轮开始时都要先确定簇头。给每个节点设定闽值T(n)，同时节点产生介于0，1之间的随机数，若产生的这个随机数小于闽值T(n)，则该节点当选为簇首[6]。阈值T(n)由式（1）给出。其中，P是簇头在所有节点中所占的百分比，r是选举轮数，r m od（1/ p ）代表这一轮循环中已经当过簇头的节点个数，G是这一轮选举中未当选簇头的节点集合。

簇头选举好，普通节点就开始选择加入哪个簇。簇头向其他节点发送广播消息，其他节点根据收到的消息信号强弱来决定加入哪个簇头，并向该簇头发送请求加入信息，正式成为其簇内成员。簇头对本簇内各成员分配相应的传输时隙形成传输列表（TDMA），然后将该 TDMA列表发给簇内成员。这样簇的建立就完成了。

1.2 稳定数据通信

簇建立好后，就可以进行数据通信了。簇内成员的发射器在自己的TDMA时间槽会自动打开并将采集到的数据发送给簇头节点，其他时隙处于睡眠状态。簇头节点一直处于活跃状态以接收簇内所有节点发送来的数据，簇头接收完数据后将收到的数据进行融合处理，去掉冗余信息后直接发送给 sink汇聚节点。这样通过簇头进行数据处理之后再发送给汇聚节点的通信方式有效地减少了发送能量的消耗。汇聚节点能量可以补充，对整个网络的寿命没有一点影响。当稳定数据通信持续一段时间后，网络重新开始组簇，进入新的一轮工作，如此循环进行，直到网络中的节点能量消耗到网络无法再进行为止。

2 LEACH协议的改进

由于 LEACH协议的簇头既要融合簇内节点发送来的数据又要将处理后的数据发送给基站，这两大任务消耗能量都是最严重的部分，所以簇头比普通节点消耗能量要大很多。针对上述缺点对LEACH进行改进，通过簇内节点成链，让簇内节点由单跳通信转变为簇内节点多跳的传输模式，让簇内节点融合数据后再由一个簇内节点将数据发送给簇头，这样簇头就减少了处理簇内节点数据的能耗，只负责将收集到的数据发送给基站即可。

2.1 簇的形成

簇头的产生和簇内节点的确定都采用 LEACH协议的产生方式，这里不在介绍，不过簇头不用对本簇内各成员分配相应的传输时隙。

2.2 簇内节点成链

簇形成后，簇内的成员节点按照贪婪算法形成一个小型的节点链。为了保证簇内每个节点都有自己的相邻节点，节点发送能量递减的测试信号，通过监测应答来确定离自己最近的邻居节点[7]。链的形成从簇内离簇头最远的节点开始构建，每个簇内节点都找到自己的相邻节点，通信中只有一个节点当选为领导节点与簇头通信[8]。已经成链的节点不能被再次访问，依此下去，簇内所有节点将形成一条链。如图1，每个节点只与它最近的邻居节点通信。

图 1 簇内链式结构

2.3 簇内数据传输

数据的传输是由簇内离簇头最近的那个节点将数据传输给簇头的。首先由簇头在本簇内决定离自己最近的那个节点作为链的领导节点，然后领导节点通过Token控制数据从两个链尾开始传输，分别经过各自的邻居节点将数据融合处理和数据转发，一步一步传到离簇头最近的那个节点，由该节点融合它两边邻居节点发送来的数据和自身采集到的数据后发送给簇头，簇头再将接收到的数据和自身采集到的数据融合后发送给基站。这样一次簇内数据的采集和发送就完成了。如图 2，选择距离簇头最近节点B为领导节点，传输数据时节点B产生Token控制信号，将Token沿着链传给节点D，节点D将自己采集到的数据传给节点C，节点C将D的数据和自己采集到的数据进行融合后发送给节点 B，然后B将Token传给节点F，F和E的数据传输与C和D的数据传输方式一样，最后B将C和E还有自己采集的数据进行融合后发送给簇头，簇头将收到的数据和自己采集的数据处理后发送给基站。这样一轮数据的传输就完成了。当簇头节点能量耗尽时，系统重新启动，进入下一轮簇的选举。

图2 一个簇的数据传输

改进后的算法簇内节点之间采用最近距离的多跳方式发送数据，大大节约了簇内节点单跳发送数据给簇头消耗的能量。其次一个簇内的节点不会过多，这样形成短链，对数据的传输时延不会产生太大的影响，对于无线传感器网络来说是可以的。再次簇内节点将采集的数据进行融合处理才发给簇头，很大程度上节约了簇头融合数据消耗的能量，增加了稳定数据通信阶段的时间，大大地延长了网络寿命。该算法与LEACH协议相比节能效果较好。

在改进的算法中，之所以通过簇内离簇头最近的节点与簇头进行数据通信，是考虑到最短路径的因素。因为一般簇头四周都会有簇内节点，如果形成的链收集到的数据直接由链首传输给簇头的话，路径可能达不到最优，从而对于整个簇来说消耗的总能量会加大。如图 3，簇一就是采用由链首将信息融合后发送给簇头。簇二是采用由离簇头最近的节点融合数据后发送给簇头。相比之下簇二路径更短，所以整个簇消耗的能量也最低。

3 仿真分析

协议的改进主要是为均衡网络节点能耗和提高网络寿命为目的。通过NS2工具对LEACH协议和改进后的协议进行仿真，分析比较协议的网络寿命和存活节点的数目。网络寿命规定为网络中节点开始部署到网络中 80%节点死亡的时间，存活节点的数目规定为不同时刻存活节点的个数。通过这两个性能指标可以反映出网络整体能量的消耗水平。

仿真模型采用100个节点随机分布在50m×50m范围内，基站位置为（25 m，25 m），簇头节点概率为0.05，每个节点的初始能量为2J，且不能移动，信息长度为500 Byte。

图4为LEACH协议和改进后的协议在整个网络各时刻中节点存活数量变化图。由图4可知，改进后的协议寿命比 LEACH协议长，且曲线的坡度明显没有 LEACH那么陡，这是因为簇内节点链式连接后，无论是簇头还是簇内节点的能量消耗都有所减少，所以每轮的数据稳定通信时间也就相对变长了，进而提高了路由协议的使用时间。改进后的协议虽然在性能方面比改进前有明显的提高，但由于该算法比较复杂，不太适合大规模的WSN网络。

图 3 两种成链结构的比较

图4 存活节点数目

4 结语

考虑到簇头即要融合簇内数据又要转发数据消耗过多能量以及簇内节点单跳发送数据消耗多余能量的缺点，利用簇内节点成链，通过簇内节点融合簇内采集到的数据为簇头节点分担任务，节约簇头节点能量消耗，使网络中的节点能耗均衡，以此达到提高每轮簇稳定数据通信时间，进而提高网络寿命。使用NS2对改进后的LEACH协议进行仿真，分析结果表明网络寿命比LEACH协议延长。

[1] 马祖长,孙怡宁,梅涛.无线传感器网络综述[J].通信学报,2004,25(04):114-127.

[2] 胡钢,朱佳奇,陈世志.无线传感器网络簇间节能路由算法[J].通信技术,2009,42(11):135-137.

[3] 王殊，阎毓杰，胡富平,等.无线传感器网络的理论及应用[M].北京:北京航空航天大学出版社,2007:1-78.

[4] 廖明华,张华,王东.基于 LEACH协议的簇头选举改进算法[J].计算机工程,2011,37(07):112-114.

[5] 张震,闫连山,潘炜,等.基于LEACH和PEGASIS的簇头成链可靠路由协议研究[J].传感技术学报,2010, 23(08):1173-1178.

[6] 张瑞华,张红.无线传感器网络分簇算法分析与性能比较[J].通信技术,2010,43(01):156-161.

[7] 王薇.无线传感器网络低功耗分级路由协议研究[D].浙江:浙江大学,2006.

[8] 孙献璞,张艳玲,张建东.无线动态令牌协议及性能分析[J].电子学报，2009,36(10):2039-2043.

[9] 李林,穆灵. 基于组合公钥的 WSN认证协议的设计及分析[J].信息安全与通信保密,2009(07):93-95.

[10] 林先超,杨寿保,单来祥,等.一种传感器网络分布式认证方案[J].信息安全与通信保密,2006(07):114-116.