有效降低无线网络节点能量的LEACH新算法

岑成龙，王 玫

(桂林电子科技大学通信研究所，广西桂林541004)

无线传感器网络(WSN)是由大量具有通信和计算能力的微小传感器节点，以无线的方式连接构成的自组测控网络。它综合了传感器技术、嵌入式计算技术、分布式信息处理技术等多个学科，是新兴的交叉研究领域。由于无线传感器网络具有自组性、可靠性、可扩展性和容错性等特点成为了目前国际科学研究的热点。传感器节点的能量非常有限，对于如何提高节点的能量效率是面临的主要挑战。

对于如何提高无线网络的能量效率，国内外的专家已进行了许多研究。文献［1-2］中介绍了一种自组、自适应按簇分层的LEACH算法，该算法的不足之处是在选举簇头时没有考虑节点的剩余能量。文献［3］通过最优化链路层编码和物理层调制来折中传输能量和电路能量，使网络的总能量消耗降低。在文献［4］中研究了单位成本条件下信道传输的最大比特数、比特传输能耗与传输数量及速率的关系。在文献［5］中，介绍了基于CDMA的无线传感器网络最小能量消耗的问题，其能量消耗模型包括传输消耗的能量和电路消耗的能量两方面，文中通过联合最优化网络中每个节点的传输能量和传输时间以使网络的能量消耗达到最小。文献［6］中，提出了一种将网络节点分成多层簇的分簇算法。文献［7］研究了无线传感器网络中进行中短距离信息传输时能量消耗对系统性能的影响。以上这些文献在研究如何使网络节点能量消耗达到最小时，都没有考虑到节点收集到的信息冗余量过多的情况，本文在LEACH协议的基础上，研究当节点收集到的冗余信息过多时，再进一步分簇，目的是将冗余信息剔除掉，从而降低节点的能量消耗。

1 LEACH协议

LEACH［1］(Low-Energy Adaptive Clustering Hierarchy)是MIT的Chandrakasan等人为无线传感网络设计的低功耗自适应分层路由算法。在LEACH算法中，将WSN中所有节点分成若干的簇，每个簇中选举一个节点作为簇头负责与基站通信。LEACH算法引入了“轮”的机制，每一轮分为簇形成阶段和簇稳定阶段。在簇形成阶段，WSN中以一个给定的概率随机地选举节点成为簇头，被选为簇头的节点在网络中就其身份进行广播，其他非簇头节点根据“就近原则”加入离它最近的簇中;分簇完成后，簇头节点为簇中每个节点制定一个时序表，此时簇的形成阶段结束。在簇稳定阶段，所有的非簇头节点根据簇头节点制定的时序表按顺序将自己收集到的数据发给所属簇的簇头节点，簇头节点将收集到的所有数据进行融合后，再把数据发送给远方的基站。由于簇头节点需要消耗大量的能量，因此，在LEACH算法中，为了避免簇头能量消耗过快，每个节点须轮流担任簇头。

2 新算法的描述

2.1 基于LEACH簇头选举阈值的改进

LEACH协议在选择簇头的时候没有考虑节点的剩余能量这一因素，而LEACH在选举簇头时都是随机的，这就有可能导致有的节点在剩余能量过少时被选作簇头。而由于簇头需要消耗大量的能量，从而加速了该节点的死亡。针对这一情况，在对LEACH协议在簇头选举时进行一些改进。在每一轮簇头的选举时，将节点的剩余能量这一因素考虑进来。LEACH算法在选择簇头时，每个节点首先随机分配一个随机数，只要这个随机数小于规定的阈值T(n)就成为簇头。这导致成为簇头的节点数大大超过最优簇头数kopt。簇头节点数太多就会导致在分簇时，网络节点消耗大量的能量进行分簇。为此，对LEACH算法规定的阈值T(n)做一些改进，使网络的簇头数降低从而节省因分簇而大量消耗的能量，并将节点的剩余能量考虑进来。文献［1］中T(n)定义为

重新定义T(n)，其公式为

式中:p是网络中簇头所占的比例，p=0.05;r为当前的轮数，G是在最后1/p轮中没有成为簇头的节点集合;Eave表示每一轮所有非死亡节点剩余能量的平均值。改进后的式(1)可以降低节点成为簇头的概率，从而节省分簇所要消耗的能量，达到延长网络生命周期的目的。

2.2 基于剩余能量的LEACH二层簇头的描述

为了使LEACH适合更大范围的传感器网络，在LEACH第一层簇头的基础之上再次对网络进行分簇。也就是在LEACH选出簇头时，把LEACH的第一层簇头再看作普通的节点，然后再对这些节点分簇并选出第二层的簇头。这样做的优点是:在大规模的网络中，由于节点分布的密度较高，许多节点收集到的信息可能是重叠的，这很容易导致信息冗余。而在第一层簇头的基础之上再进行分簇就可以进一步将信息进行压缩，这样可以减少传到基站的数据量，从而达到降低节点能量消耗的目的。

LEACH二层簇头算法的思路是:在网络节点中首先选举第一层簇头，这里选举的第一层簇头和LEACH算法选举簇头的思路一样;所不同的是，被选举为簇头的节点在进行广播时，将自己剩余能量的信息E(i)和坐标位置(xi，yi)一起进行广播。然后所有的簇头节点将自己的剩余能量E(i)和根据所收到信息中其他簇头节点的剩余能量E(i)进行比较，将剩余能量最大的节点作为第二层的簇头。

需要注意的是:因为第一层簇头节点通过剩余能量E(i)的比较就可以知道第二层簇头的身份和位置。因此，在选择第二层簇头时就不需要像第一层簇头那样进行身份广播了。第一层簇头根据E(i)的标记按顺序将信息传给第二层簇头，而不是基站。

进行二层簇头的改进是基于节点收集到的信息有较多重叠，也就是信息冗余。假设第一层簇头收到的信息冗余量为x，当第一层簇头将自己的全部信息传给第二层簇头时，第二层簇头就会将这些冗余信息剔除掉，而将剩下的信息传给基站。那么，LEACH二层簇头算法每轮所消耗的能量为

式中:ECH1表示第一层簇头的能量;ECH2表示第二层簇头的能量;Enon-CH表示非簇头节点的能量;k1表示第一层簇头数;k2表示第二层簇头数;Etot表示每轮节点消耗的总能量;M为区域边长;N为节点数。

3 仿真实验

实验参数为:区域边长M=100 m的正方形中，节点数n=200，基站的位置为(50，350)，数据长度l=4 000，控制包长度为100，发射电路和接收电路能量参数为ETx=ERx=Eele=50 nJ/bit，初始能量Eo=0.5 J，发射机放大器的参数为efs=10 pJ和emp=0.001 3 pJ，压缩数据消耗的能量为EDA=5 nJ·bit-1·signal-1。图1所示为LEACH与改进阈值后的LEACH存活节点数与时间关系的比较图。在图1中，改进后的LEACH算法出现第一个节点死亡是在r=108轮，最后一个节点死亡是在r=1 989轮;而LEACH算法出现第一个节点死亡是在r=101轮，最后一个节点死亡是在r=360轮。经过多次实验发现:改进后的LEACH算法簇头数目大约降低了40%，改进后的LEACH算法出现第一个节点死亡与原LEACH算法差不多，而改进后LEACH算法的生命周期比原LEACH算法生命周期提高了5倍。

图1 LEACH与改进阈值后的LEACH存活节点数与时间关系的比较图

如图2所示为二层簇头的LEACH、LEACH算法的生命周期与冗余度x的关系图。从图中可以看出当x≈0.8时，二层簇头的LEACH与LEACH算法的生命周期相等。当x＜0.8时，LEACH算法的生命周期比二层簇头的LEACH算法的生命周期长;当x＞0.8后，二层簇头的LEACH算法的生命周期比LEACH算法的生命周期长，而且随着x的增大，它们的生命周期差值越来越大。

图2 LEACH、二层簇头的LEACH生命周期与冗余度x的关系图

如图3、图4所示为二层簇头的LEACH与LEACH的对比图。在图3中，x=0.8，二层簇头的LEACH出现第一个节点死亡的时间是在r=139轮，最后一个节点死亡的时间是在r=377轮，而LEACH出现第一个节点死亡时间是在r=101轮，最后一个节点死亡的时间是在r=360轮;当第一层簇头节点数据冗余量为80%时，通过对比首轮节点的死亡轮数，可知采取二层簇头的LEACH算法首轮节点死亡延迟了约38%。而且从图中的曲线可以看出二层簇头的LEACH算法使节点消耗的能量更加均衡。

在图4中，假设x=1情况，也就是其他节点传给第二层簇头的信息都是冗余的情况。二层簇头的LEACH出现第一个节点死亡的时间是在r=151轮，LEACH出现第一个节点死亡时间是在r=106轮，二层簇头的LEACH出现首个节点死亡的时间比LEACH算法推迟了近50%;二层簇头的LEACH最后一个节点死亡是在r=419轮，而LEACH最后一个节点死亡是在r=377轮，二层簇头的LEACH的生命周期比LEACH算法的生命周期延长了11%。不仅如此，从图4中可以看出:二层簇头的LEACH算法的节点消耗的能量比LEACH算法节点消耗的能量更加均衡，这样可以避免有的区域节点过早地死亡，而导致信息收集盲点区域。

4 结论

本文提出了基于LEACH的二层簇头算法，继承了LEACH按轮选举簇头的特点，在第一层簇头的基础之上再次分层选举簇头，使得网络节点的能量消耗更加地均衡，弥补了LEACH算法个别节点消耗能量过快的不足，并且二层簇头LEACH算法能进一步地剔除节点中的冗余信息，使需要传输到基站的数据量减少，从而节省了节点的能量，延长网络生命周期。

［1］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol for wireless microsensor networks［C］//Proc.33rd HICSS.Hawaii:IEEE Computer Society，2000:3005-3014.

［2］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Trans.Wireless Communications，2002，1(4):660-670.

［3］CUI S，GOLDSMITH A J，BAHAI A.Energy-constrained modulation optimization［J］.IEEE Trans.Wireless Commun，2005，4(5):2349-2360.

［4］VERDU S.On channel capacity per unit cost［J］.IEEE Trans.Inf.Theory，1990，36(5):1019-1030.

［5］SHU T，KRUNZ M，VRUDHULA S.Joint optimization of transmit power-time and bit energy efficiency in CDMA wireless sensor networks［J］.IEEE Trans.Wireless Communications，2006，5(11):3109-3118.

［6］BANDYOPADHYAY S，COYLE E J.An energy efficient hierarchical clustering algorithm for wireless sensor networks［C］//Proc.IEEE INFOCOM.San Francisco:IEEE Press，2003:1713-1723.

［7］CUI S，MADAN R，GOLDSMITH A J，et al.Cross-layer energy and delay optimization in small-scale sensor networks［J］.IEEE Trans.Wireless Commun，2007，6(10):3688-3699.