基于休眠簇头的LEACH算法研究

兰 慎 ，彭 刚 ，李发飞

（1.桂林电子科技大学 计算机与控制学院，广西 桂林 541004；2.桂林空军学院 教育技术中心，广西 桂林 541003）

在无线传感器网络 WSN （Wireless Sensor Networks）[1]中，分簇算法是有效节约能量的一种手段，是目前研究的关键技术之一。参考文献[2]在簇头选举上加入了节点剩余能量指标，提出了每簇簇头独立轮换机制，参考文献[3]把四色算法引入到簇头的选举过程中，并且通过此算法优化了网络簇结构，参考文献[4]提出了将整个网络分为两级拓扑簇内和簇间，利用节能算法，在优化的拓扑结构中找到能耗最小路径转发数据，减少了存储和控制消息，参考文献[5]在LEACH算法的基础上提出了备用节点和负载平衡的思想。这些文献中提出的算法，都在一定程度上延长了网络生存期，但是都需要通过轮选举簇头、重新分簇过程，消耗额外能量较多。

因此，本文在对分簇算法LEACH[6]的详细研究分析的基础上，针对LEACH算法中簇头选择算法存在的一些不足，提出改进后的分簇算法S_LEACH。

1 LEACH算法的介绍与分析

LEACH算法的基本思想是将网络划分为若干个簇，再通过随机数值来选择簇头和轮换簇头，以达到能量消耗相对均衡。LEACH算法簇头选取公式 T（n）定义如下：

式中：p为簇头的百分比，r为当前轮数，rmod（1/p）为此轮以前已当选过簇头的节点个数，G为在此轮以前还未当选过簇头的节点集合。该算法分为两个阶段：簇建立阶段和稳定工作阶段。

簇建立阶段。在选举产生簇头后，所有当选的簇头都向网络中的所有节点广播这一消息，非簇头节点通过接收信号的强度，选择信号最强的簇加入并通知该簇头，收到通知的簇头就产生一个TDMA定时消息，并且连同将在本簇节点中通信时使用的CDMA编码一起发送给该簇中所有其他节点。

在稳定阶段，节点持续采集数据并在时隙到来时向簇头传输数据，簇头融合处理该簇节点传来的数据，之后发送到基站（BS）。网络中节点不断地进行轮循环工作。

LEACH算法的一些不足：

（1）整体网络能量利用率低，每轮都要重新选簇头，重新分簇[7]。这一过程会消耗大量的节点能量，整个网络的生存期也会随之缩短。

（2）能耗不均匀，LEACH算法中假定所有节点都可以直接与BS通信，造成LEACH算法无法更好应用于较大的WSN区域，特别对于簇头，由于其要处理的数据比较多，这会导致其较早的死亡。

（3）簇头选择不合理，所有节点当选簇头概率相同，没有考虑节点自身的限制条件如剩余能量[8]。

2 S_LEACH算法

针对上述问题，本文对簇头选择进行了改进，以提高网络总能量利用率、增强网络稳定性、延长网络生存期的设计目标，提出了S_LEACH算法。

2.1 S_LEACH设计思想

无线传感器网络在工作到一段时间后，会出现节点死亡，这样整个网络的工作节点总数就会减少，通过LEACH算法计算得到的簇头数量Popt值会变成不是最优的选择，导致簇头的选举过程变的不可信，进而造成整个网络的稳定性下降。

因此本文对LEACH算法做如下改进：

（1）用休眠簇头节点代替原算法中用轮换方法选择的簇头节点，避免了整体网络的能量利用率低的情况。改进后算法只需要一次并且是第一次分簇[9]，此过程仍采用LEACH算法。在第一次完成分簇与首批簇头的选定后，就进行休眠簇头的选择，之后便可以进入稳定工作阶段。在此阶段当某簇的簇头能量小于当前簇的平均能量时，可唤醒其中一个休眠的簇头接替当前簇头工作，避免了因频烦的簇头选举带来的能量损耗。通过这种方式也可以避免当网络中节点不断死亡时，使得计算所得的popt不可信，进而导致的网络不稳定。

（2）在实际情况下，由于LEACH算法分簇不均衡，而且簇头节点到BS距离不等的因素，要计算得到优化的簇头数量。首先按照参考文献[6]中的假设计算特殊的情况，假设有N个节点均匀分布在一个A=M×M区域，且基站离监测节点都相对较远。在这种情况下存在两种能量衰退模型，一种是多路径衰退模型其衰退系数为 εmp，另一种是自由空间衰退模型其衰退系数为εfs。如果网络中存在k个簇，则每个簇平均有N/k个节点，由参考文献[6]中可得最优簇kopt值的计算公式：

通过实验得出，当 N=100，M=100 m，75 m

又根据参考文献[10]，在参考文献[6]相同的假设情况下，当基站位于监测节点网络的中心位置时，其给出了最优簇kopt的值计算公式：

因为在参考文献[10]同样环境下，参考文献[11]给出了簇头到基站的平均距离计算方法：

其中，x，y为节点的坐标，参考文献[10]中通过式（3）得到式（2），从式（2）可以看出，在参考文献[10-11]的假设情况下，网络簇数量或是簇头数量与节点到基站的距离无关，簇的数量只与网络的节点数量N有关。

本文在仿真过程中，取 N=100，kopt=5（即实验中 p=5%）。在第一次分完簇后，可以把每个簇看成原来WSN网络的子网络，并且假设它们是独立、均匀分布。此时簇头就相当于是基站，满足参考文献[10]中的假设，由式（2）可以计算出该簇（子网络）中所需要簇头的数量，这个数量即为休眠簇头的数量。因为这是在子网络中计算的簇头数量，而子网络本身就是一个簇，所以根据式（2）计算出的簇头数量即可为休眠簇头数量。

2.2 S_LEACH工作过程

S_LEACH算法工作也可以分为两个过程：准备阶段和工作阶段。准备阶段包括簇头的选择、分簇和休眠簇头的确定。休眠簇头的确定环节是确保新算法可以正确工作的重要环节，也是算法的改进点。

为了方便说明，用Ai0表示第 i簇的簇头；用Aij表示第i簇的标号为j的节点，其中 0

（1）准备阶段

簇的建立过程中主要是选第一批簇头和分簇，因为改进的算法S_LEACH是一次性确定所有簇头，并且只需要一次分簇，所以在簇的初始阶段仍采用LEACH算法进行确定第一批簇头和首次分簇。

基于 LEACH算法，在分簇的过程中，簇头 Ai0（i=0，1，2，3，4）会在全网范围内广播 ADV消息，非簇头节点根据收到的ADV能量大小，回复JoinREQ消息（含节点自身ID和簇头ID）选择加入哪个簇。簇头Ai0统计加入的节点数量，并由式（2）计算出本簇中休眠簇头的数量n=kopt。再在为簇内成员节点分配TDMA时隙表和CDMA编码时，把前n个回复确认的节点确定为休眠簇头节点，并作好标记存储在Ai0缓存中。完成后，Ai0再给标记的n个节点发送含有将来用于唤醒休眠簇头节点的特定的发射功率Wi的消息，这n个节点收到后记录Wi，之后马上进入休眠状态并设定定时器，定时苏醒后，等待一定时间再查看是否有唤醒消息，无则进入睡眠状态。

（2）工作阶段

在准备阶段的工作完成之后，WSN就进入工作阶段，在此阶段每个簇的Ai0每隔一定时间先查看自己的缓存中是否还有有标记了的Ais，有则计算当前簇的所有节点的平均剩余能量（Ei_ave）的大小并且和自己的剩余能量（Ei_res）比较。

如果Ei_res>Ei_ave，则 Ai0继续当选为簇头，如果 Ei_res

当Ais收到后对比自已 ID和Mwakeup中的 ID，如果相同则结束睡眠进入工作状态，如果不同则继续睡眠。对比结果相同的节点 A′is回复消息 Mback给 Ai0，说明自己已经做好准备当簇头了。

Ai0收到Mback后，再发送包含正处于休眠状态的簇头信息的消息给 A′is，A′is收到后记录并且回复确认。之后Ai0再发送消息（含有 A′is的ID）给基站说明本簇的簇头现在更改为A′is，基站在收到消息后回复同意消息给Ai0，并把自己记录的该簇的簇头信息更新为 A′is。Ai0同时在簇内广播簇头更改消息，簇内所有普通节点都更新自己的簇头信息。在广播消息发送完成并且Ai0收到BS回复的同意消息之后就降级为普通节点，并保存新簇头Ais的信息，之后进入稳定工作阶段。

隔一定时间再次计算当前簇的所有节点的平均剩余能量（Ei_ave）的大小并且和当前簇头的剩余能量（Ei_res）比较大小，然后再按上述过程唤醒休眠簇头。

3 仿真及其结果分析

本文以Matlab作为实验仿真平台，在区域为100 m×100 m的范围内随机部署100个节点，基站位置为（50，175），节点初始能量为 0.5 J，

εmp=0.001 3 pJ/bit/m4，εfs=10 pJ/bit/m2。

图1比较了两种算法下在不同时段网络剩余总能量的值，可以看出LEACH算法在250 s时能量剩余总量为0 J；而S_LEACH算法在336 s时能量剩余总量才为0 J，新算法延长了大约34%的网络生命周期。这是因为原算法需要频繁地进行簇头选举和重分簇区，而且这些过程都需要和基站进行直接通信，能量消耗大。新算法只需要在本簇内唤醒休眠簇头节点即可保证网络继续工作，新算法除了在数据融合之后需要向基站发送信息外，只有在更换簇头时，通信一次即可，节约了大量的能量。

图1 两种算法的生存期

图2比较了两种算法在不同时段网络中节点死亡的数量，从图中可以看出，LEACH算法和S_LEACH算法第一次出现死亡节点的时间分别为149 s和251 s，这表明新算法很大程度上延长了网络的稳定性，因为在没有出现第一个死亡节点之前网络的整体拓扑结构是没有变化的，算法通过计算节点数计算的最优簇数量（kopt）也不会受影响，当有死亡节点出现的时候，其就会计算不准确，从而影响簇的形成与工作过程。而且S_LEACH的曲线图很接近直线，说明新算法中的死亡节点是稳定增加的，网络不会因为死亡节点的突然增加，而使得其他节点工作受重大影响，避免了监测数据不准确或是丢失严重。这些都可以说明新算法能量利用比较均匀并且其稳定性较好。

图2 两种算法死亡节点的比较

本文详述了LEACH算法的基本原理，针对该算法的不足，提出了一种休眠簇头的算法。与LEACH算法相比，改进后的算法减少了簇头选举的能耗并且避免了重新分簇带来的能量损耗，可使网络中的能量利用最大化。仿真实验表明，新算法的稳定性较好，并且能够有效地利用网络中有限能量，实现了延长网络生存周期的目标。

[1]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2006.

[2]张强，卢潇，崔晓臣.基于能量高效的无线传感器网络LEACH 算法改进[J].计算机工 程与设计，2010，32（2）：427-433.

[3]刘波，柴乔林，刘玲.基于分簇的无线传感器网络节能算法[J].计算机工程与设计，2008，29（4）：846-848.

[4]王春雷，柴乔林，王华，等.基于分簇的无线传感器网络节能算法[J].计算机应用，2007，27（2）：342-345.

[5]邢云冰，史浩山，赵洪钢.基于备用节点的无线传感器网络 LEACH算法的改进 [J].传感技术学报，2007，20（7）：1592-1596.

[6]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHMAN H.An application-specific protocol architecture for wireless micro-sensor networks [J].Wireless Communications，2002（1）： 660-670.

[7]张瑞华，高蕊.无线传感器网络 LEACH算法分析[J].网络技术，2010（4）：56-59.

[8]杨伟伟.基于 LEACH的WSN分簇算法研究[D].郑州：郑州大学信息工程学院，2010.

[9]陈楠.无线传感器网络LEACH算法的研究与改进[D].北京：北京邮电大学，2008.

[10]BANDYOPADHYAYS，COYLEEJ.Minimizingcommunication costsin hierarchically-clustered net-worksofwireless sensors[J].Computer Networks， 2004， 1（44）： 1-16.

[11]SMARAGDAKIS G， MATTA I， BESTAVROS A.SEP：A Stable election protocol for clustered heterogeneous wireless sensornetworks[C].Proc.ofthe Int′lWorkshop on SANPA， 2004， 251-261.