李建坡 姜 雪 朱绪宁

(东北电力大学信息工程学院，吉林 吉林 132012)

0 引言

无线传感器网络(wireless sensor networks，WSN)最关心的问题之一是在能量有限的情况下尽可能地延长网络生命周期［1］。WSN路由协议分为平面路由协议和分簇路由协议。平面路由协议算法简单，易于实现，但一般需要牺牲存储空间维持大量的路由表，这增加了通信负担，造成信息冗余及拥塞，使能量损耗增大、延迟加长［2］。分簇路由通过簇头对簇内节点间的信息融合及转发机制来减少数据的传输量和距离，进而降低通信能量，达到节能的目的。低能量自适应分簇路由协议(low energy adaptive clustering hierarchy，LEACH)是比较成熟常用的分簇路由算法。该算法簇头可随机选择并定期更换，这在一定程度上实现了节点的负载平衡，延长了网络的生命周期，可以更好地进行资源分配，是一种优化能量使用效率的算法。

1 LEACH路由算法

LEACH算法是针对无线传感器网络设计的一种低功耗自适应的分簇路由算法，它是第一个在无线传感器网络中提出的层次式路由协议。由于短距离通信比较节约能量，因此在LEACH算法中，更多的通信都是局限在簇的内部，只有少数簇头节点才和远处的基站进行远距离通信［3］。同时，LEACH算法采用分簇的自适应技术和簇头节点的轮换技术，使得网络的载荷分布相对比较均衡，能够延长网络的生命周期。另外，LEACH算法在每个簇内部可以进行本地计算和处理，去除数据中的冗余成分，减轻簇头节点的通信负担，所需能耗要远远小于通信能耗。

当研究低功耗的无线通信时，不同的通信特征和假设模型会很大程度地影响算法性能。在LEACH算法的仿真过程中，使用的硬件能耗模型如图1所示［4－5］。

图1 LEACH通信功耗模型Fig.1 Communication energy consumption model of LEACH

收发电路处理1 bit数据所消耗的能量为:

发射放大电路向单位面积发送1 bit数据所消耗的能量为:

在d距离内处理k比特的信号，发送消耗的总能量为:

接收时消耗的总能量为:

由以上公式可以看出，接收一个分组的能耗与数据量及通信距离有很大的关系。因此，在算法设计中不仅要尽量减少通信距离，而且要尽量减少所要传输的数据量。

2 改进的LEACH路由算法

LEACH算法是一个用来优化能量使用效率的协议体系，它具有许多优点。但LEACH算法也有它的不足之处，主要体现在以下几个方面。

①每轮都要先确定簇头节点，然后建立簇，期间用于建立簇的通信开销较大。由于LEACH算法的簇头选举机制没有考虑到具体地理位置，这使得簇头节点不能均匀地分布在整个网络中，无法做到最优。

②簇头的选举是等概率产生的，没有考虑到不同节点之间能量的差异。如果能量低的节点被选作簇头，很容易导致能量耗尽而死亡，那么在这一轮中，整个簇无法通信，既不利于整个网络的健壮性，也不利于网络整体生命的延长。

③LEACH的传输距离较远，并且数据融合相对较少，这就要求传输更多的数据到更远的距离，从而加大了能量消耗。某些离基站很远的簇头节点能量消耗更快，这将影响网络的覆盖范围和生存时间［6－8］。

针对LEACH算法的不足，本文主要从以下两个方面对LEACH算法进行改进。

①选择设置网络内的最优簇头个数。在LEACH算法中，簇头节点担当着至关重要的角色，簇头节点个数的选择直接影响LEACH算法性能的优劣。若簇头数目过少，那么节点到簇头节点的距离就会较远，传输数据的能量损耗会增加;若簇头数目过多，会使得数据融合的效率较低，且簇头节点消耗能量较多，从而使得整个网络在每轮中的总耗能增大。

②簇头节点选举算法。LEACH算法的簇头轮换时随机产生一个数，由于簇头是随机产生的，所以可能存在某些节点的剩余能量不多但仍被选为簇头节点的情况，这样这个节点可能因为能量不足而无法完成簇头节点的功能或因能量迅速耗尽而死去。所以，簇头的选取依据必须要考虑到这方面的因素。

2.1 簇头节点数目的选取

由于εamp＜＜Eelec，比较式(3)和式(4)可以得出，能量主要消耗在远距离的传输中。在选取最优簇头数目时，我们希望达到两方面的效果:一是每轮数据通信所耗费的总能量最小;二是所耗费的能量能够比较均匀地分布在整个网络上。为此，我们假设在一个不太大的M×M区域内较均匀地分布有N个节点，并且这N个节点将被分为n个簇，那么每个簇都将有一个簇头节点和N/n－1个成员节点［7］。一个簇头节点在每帧消耗的能量为:

式中:k为每次数据传输包含的比特数;EDA为进行数据融合及数据压缩所需要的能量;dtosink为簇头节点到基站的距离。

每个成员节点只需要在各自的时隙内传送数据到相应的簇头节点，一个成员节点在每帧内消耗的能量为:

式中:dtoCH为从成员节点到簇头节点的距离。

基于我们的假设前提，每个簇的面积为M2/n，假定节点在这个区域的分布密度为ρ=n/M2，那么dtoCH的数学期望为:

如果假定每个簇所覆盖的区域是一个圆形区域，那么，这个圆的半径为，则式(7)可变为:

将式(9)代入式(6)可知，每个成员节点每帧的能量消耗为:

那么，所有节点的能量消耗为:

对Etotal求关于n的导数，解得:

求得的最优簇头数目考虑到了更全面的能量消耗因素，因而与原有的最优簇头数目相比，其更能够降低整体网络的能耗。

2.2 簇头节点的选取

在LEACH的簇头选取算法中，节点能否当选为簇头节点主要取决于节点在过去的r轮中是否担当过簇头节点，以及产生的(0，1)之间的随机数是否小于阈值T(i)。假设节点i(从时刻t开始)在第(R+1)轮开始被选定为簇头节点的概率为Pi(t)，通过Pi(t)的设定来保证本轮产生的簇头节点数为k，如果网络中有N个节点，那么产生簇头节点数的期望值为:

式中:G为在过去Rmod(N/k)轮中没有担任过簇头节点的节点集合。

由LEACH算法可知，只有在过去R轮中没有担任过簇头节点的节点，才有可能在第(R+1)轮中当选为簇头节点，且当选的概率为:

前R轮中，没有成为簇头节点的个数应该为N(1－kr/N)，如果经过N/k轮之后，所有的节点都担任过一次簇头节点，那么在以后的轮中，它们又可以重新担任簇头节点。因此，在第(R+1)轮中，有资格担任簇头节点的节点集合G的期望值为:

这种机制保证了每轮产生的簇头节点数为k，且在N/k轮之内，每个节点都有且仅有一次担任簇头节点。在一定程度上，我们认为这种机制能够保证网络能量消耗的均衡分布。

考虑到LEACH算法的簇头选择方法并不能够使得能量消耗均匀地分布在整个网络中，所以，我们有必要对LEACH的簇头选择方式进行相应的修改。具体修改方案为:第一，将节点的剩余能量因素加入到簇头选取的标准中，目的就是为了避免选择那些剩余能量较低的节点成为簇头，本算法采用的是节点剩余能量与整个网络平均剩余能量的比值;第二，将节点的能量消耗速度加入到簇头选取的标准中，簇头节点本身要消耗远高于成员节点的能量，如果一个能量消耗速度快的节点被选为簇头节点，那么也会加速它的死亡。最终方案可表示为:

式中:Eremain为节点第(R+1)轮选择开始前剩余的能量;Eave为在第(R+1)轮选举开始前整个网络的平均剩余能量;Ecorsume为在第 R轮中节点能量的消耗;Eave_cors为网络在第R轮中平均消耗的能量。

从改进后的最终方案来看，引入了节点剩余能量、网络平均剩余能量、上一轮能量消耗和上一轮网络平均能量消耗四个因素。

在这个方案中，节点能否成为簇头与其当前剩余能量成正比，与其上一轮中消耗能量数成反比。那么，如果一个节点的剩余能量比网络的平均能量级别要低，它当选为簇头的概率也将大大降低。同时，如果一个节点在一轮消耗的能量比网络平均消耗的能量要多，那么也会相应地降低它被选为簇头的概率。

3 LEACH算法的仿真与分析

为了验证改进算法的可行性，本文用Matlab仿真平台，将改进的LEACH算法和LEACH算法做比较。

在仿真环境中，无线传感器网络［9－13］包括1个基站和100个节点，节点随机分布在(100×100)m2的范围内，基站坐标(50，50)。具有5个簇头节点的网络分布情况如图2所示。图2中，“°”表示普通节点，“+”表示簇头节点，“×”表示基站。

图2 网络分布情况示意图Fig.2 Network distribution

3.1 试验参数设定

仿真网络中的主要参数值如表1所示。

表1 网络主要参数Tab.1 Major network parameters

3.2 仿真结果分析

图3 P取不同值时网络生命周期示意图Fig.3 The network life cycle under different P

当P=0.05和P=0.2时，网络生命周期示意图如图3所示。从图3可以看出，当P=0.05时，网络大概在工作600轮时开始出现死亡节点;当工作1200轮时，所有节点死亡，网络瘫痪。当 P=0.2时，网络在工作100轮时开始出现死亡节点;当工作800轮时，网络瘫痪。所以，P取不同的值时，网络在统一模型下的性能并不相同，簇头节点数目占网络中节点数目的百分比对网络的影响很大，本仿真模型中P取0.05。

两种算法网络生命周期的仿真结果如图4所示。

图4 网络生命周期比较曲线Fig.4 Comparison of the network lifecycle

相关仿真表明，采用LEACH算法时，在第520轮开始出现节点死亡，在1204轮节点全部死亡;采用改进后的LEACH算法时，在610轮出现节点死亡，在1400轮节点全部死亡。改进后的LEACH算法由于考虑了分群数量均衡和簇头节点位置信息，从而使整个网络分簇更加合理，节省了能量，有效地延长了整个网络的生命周期。

LEACH和ILEACH的网络能耗的仿真比较结果如图5所示。

图5 网络能耗比较曲线Fig.5 Comparison of the network energy consumption

从图5可以看出，ILEACH比LEACH能量消耗小，因此网络寿命会更长。具体来说，对于100个节点随机分布的场景，节点的总能量为25 J，采用LEACH算法在第610轮开始出现节点死亡，消耗的能量为19.7 J;而对应的ILEACH算法，此时的能耗只有16.8 J，在这一阶段能耗降低了14.7%。可见，ILEACH算法在能量节省方面显示出极大的优越性。

4 结束语

针对LEACH算法存在的不足，分析了簇头个数对系统性能的影响，并提出了改进的簇头选取算法。该算法全面考虑了簇内节点的各主要能量消耗，引入了节点剩余能量、节点消耗能量速度、网络平均剩余能量和网络平均消耗能量速度四个参数，能够更真实地反映网络最优簇头节点数目的选取。该算法继承了LEACH算法随机选取簇头节点的优点，防止有限轮次内同一节点被多次选为簇头节点，使簇头节点的选取更合理，能在一定程度上减少网络能量损耗，延长网络生存时间。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005.

［2］Akyildizetal I.Wireless sensor networks:a survey［J］.Computer Networks，2002，38(3):392 －422.

［3］胡刚，谢冬梅，吴元忠.无线传感器网络路由协议LEACH的研究与改进［J］.传感技术学报，2007，20(6):1391 －1396.

［4］Li J P，Zhu X N，Tang N，et al.Study on ZigBee network architecture and routing algorithm［C］∥2010 the 2nd International Conference on Signal Processing Systems，2010:389 －393.

［5］武春涛，胡艳军.无线传感器网络LEACH算法的改进［J］.计算机技术与发展，2009，19(3):80 －83.

［6］陈林星.无线传感器网络技术与应用［M］.北京:电子工业出版社，2009.

［7］李善仓，张克旺.无线传感器网络原理与应用［M］.北京:机械工业出版社，2008.

［8］李建坡，朱绪宁，唐宁.基于DSP的无线指纹考勤系统［J］.自动化仪表，2012，33(9):28 －31.

［9］张学.无线传感器网络的拓扑控制［J］.软件学报，2007，18(4):945.

［10］李建中，高宏.无线传感器网络的研究进展［J］.计算机研究与发展，2008，45(1):5.

［11］任丰原，黄海宁，林闯.无线传感器网络［J］.软件学报，2004，14(7):1283.

［12］孙利民.无线传感器网络［M］，北京:清华大学出版社，2005:156.

［13］缪强，郑扣根.无线传感器网络的路由协议设计研究［J］.计算机应用研究，2004(3):35.