张 然，覃少华

（广西师范大学 计算机科学与信息工程学院，广西 桂林541004）

0 引 言

低功耗自适应聚类路由协议 （low energy adaptive clustering hierarchy，LEACH）是无线传感器网络中一种经典的分层路由协议，其算法通过循环随机地选举簇首节点来提高网络的能量利用率和延长系统的生命周期。相对于一般的平面静态路由协议，LEACH可以将网络生存时间延长近15%。然而，LEACH协议在进行簇首选择时采用各节点等概率随机成为簇首的选取方式，没有考虑到节点的剩余能量等因素，可能导致所选的簇首不是最优，从而影响到整个无线传感器网络的存活时间。

针对LEACH协议在簇首选择策略上存在的不足，文献 ［1－3］中通过引入节点的能量因素，提高具有较多剩余能量的节点成为簇首的可能性对其进行优化，但尚未考虑到系统每轮的总能量和平均能量。由此，本文提出了一种簇首优化的改进算法——LEACH－TE。该算法在重新计算最优簇首数的基础上，结合节点的剩余能量、每轮网络的总能量和平均能量来优化簇首的选取。这些措施有效地提高了节点的能量利用率、均衡了网络的能耗负载和延长了系统的生命周期。

1 LEACH协议

LEACH协议的工作过程被划分为周期性的 “轮”，每轮包括成簇和数据传输两个阶段。在成簇阶段，节点间首先按照一定的策略进行簇首选举；待簇首节点确定后，将向全网广播自己本轮担任簇首的消息，其他节点根据接收到的广播信号的强度来决定本轮所要加入的簇，并发送加入请求消息给相应的簇首；最后，簇首节点接收加入请求消息并创建TDMA和CDMA编码机制。在数据传输阶段，簇首节点首先接收簇内成员节点采集的监测数据，然后对其和自身数据进行融合处理，最终将融合后的数据发送给基站。

簇首的选举是LEACH算法的核心组成部分，在整个LEACH协议中扮演着极为重要的角色，其具体的选择策略描述如下：在成簇阶段，各节点产生一个 ［0，1］之间的随机数，若该数小于某一个阈值T（n），则向全网通告自己本轮担任簇首的消息；若节点之前已经担任过簇首，则将阈值T（n）设置为0，表明本轮自己不再会担任簇首；反之，若节点之前未曾担任过簇首，则在本轮中以阈值T（n）为概率竞选簇首；当网络中只剩下一个节点未担任过簇首时，该节点将把阈值T（n）设置为1，表明自己本轮无条件地成为簇首。T（n）的计算公式如下

式中：P——簇首节点占所有节点百分比的期望值；r——当前轮数；G——最近的1／P轮中未担任过簇首节点的节点集。

根据LEACH协议使用的无线能量损耗模型，传感器节点在距离d上传输l比特数据，其发送和接收能耗分别为

式 中：Eelec——发送和接收电路的能量损耗；εfriss－amp、εtwo－ray－amp——自由空间模型和多路径衰减模型中的功率放大损耗；dcrossover——距离阈值，文中为87m。当传输距离小于距离阈值时采用自由空间模型计算能耗，反之则采用多路径衰减模型计算能耗。

2 LEACH－TE协议

2.1 LEACH协议簇首选择时存在的问题

LEACH协议每轮的簇首选择过程完全依赖于各节点产生的随机数，没有考虑节点的剩余能量。节点无论能量多少，担任簇首的概率都大致相同。这样可能导致剩余能量较低的节点仍被选为簇首，从而很快被耗尽失效。这不但不利于整个系统生存时间的延长，而且由于簇首节点的失效而导致整个聚类无法通信，也不利于网络的健壮性。

2.2 LEACH－TE协议

本文基于原有的LEACH协议提出一种改进协议——LEACH－TE。首先根据节点的剩余能量和网络的平均能量，筛选出剩余能量大于或等于网络平均能量的节点，再通过调整簇首阈值T（n）的计算公式，提高已筛选出的节点里面剩余能量较大者成为簇首的概率，从而更有效地均衡各节点的能耗负载，进一步延长系统的生命周期。

2.2.1 新的最优簇首数计算公式

LEACH协议中给出了最优簇首数的计算公式，并根据仿真实验推导出当最优簇首数Kopt＝5（即P＝5%）时，平均每轮的能耗最小。但在具体的应用中，最优簇首数应根据被监测区域的面积、传感器节点的数目及基站的位置等因素来确定。

设A是一个边长为M的正方形监测区域，N是A中规则分布的传感器节点数目。文献 ［4］中指出传感器节点与基站的距离期望为

这个距离期望主要取决于基站的位置坐标 （x＊，y＊）。

假设有K个簇，则平均每个簇中有N／K个传感器节点：一个簇首节点和 （N／K）－1个簇成员节点。簇首节点的能耗由3部分组成，分别为接收簇成员节点数据的能耗、融合处理的能耗以及将融合后的数据发送给基站的能耗。考虑到基站和簇首节点之间的距离通常较远 （大于距离阈值dcrossover），故采用多路径衰减模型来计算能量消耗。

在一个数据帧的传送过程中，簇首节点消耗的能量为

式中：l——每个数据消息的比特数，EDA——进行数据融合处理所消耗的能量，dtoBS——簇首节点到基站的距离。

设RCH为每个簇所占的面积，由上述可知其值约等于M2／K。设ρ（x，y）是每个簇中传感器节点的分布密度，其值为K／M2。E［dtoCH］是簇成员节点到簇首节点的距离期望，由文献 ［4］可得

这里假设RCH是一个圆形区域，由上述可知其半径R＝令x＝rcosθ，y＝rsinθ，代入式 （6），得到簇成员节点到簇首节点的距离期望为

在传送每一帧数据时，簇成员节点只需将自己的监测数据发送给簇首节点。考虑到簇成员节点和簇首节点之间的距离通常较近 （小于距离阈值dcrossover），故采用自由空间模型来计算能量消耗。因此，簇成员节点发送l比特数据到簇首节点所消耗的能量为

由上述可知，在每一帧数据的传送过程中，单个簇内消耗的能量Ecluster由簇首节点的能耗ECH和簇成员节点的能耗Enon－CH两部分组成，即

因此，每一轮循环中整个网络所消耗的总能量Etotal为

将Etotal对K求一阶导数，并令其等于零，得到新的最优簇首数Kopt的计算公式

2.2.2 LEACH－TE簇首选择策略的改进

步骤1 在进行簇首选择前，每个节点的剩余能量记为Eres。Etotal是网络中节点ID从0到N－1的节点的剩余能量之和 （N为网络中存活节点数目）。在每一轮的初始阶段，基站计算全网的平均能量，得到Eavg＝Etotal／N（当网络中有节点死亡时，为其近似值）。只有剩余能量大于或等于平均能量的节点才有资格成为簇首，即

步骤2 在步骤1的基础上，为在剩余能量大于或等于平均能量的节点中选择剩余能量较大的节点成为簇首，将节点的剩余能量和网络的总能量等因素考虑进来，调整了簇首阈值T（n）的计算公式

式中：Eres——节点的剩余能量，Etotal——网络的总能量（当网络中有节点死亡时，为其近似值），Kopt——最优簇首数。当Etotal＞0时，各节点采用式 （15）中的簇首阈值计算公式；当Etotal＝0时，各节点采用式 （1）中的簇首阈值计算公式。式 （15）可使剩余能量较大的节点具有更高的簇首阈值，从而提高其成为簇首的概率，能有效地改善网络的健壮性，使得簇首的选择更为合理。

3 仿真实验

3.1 仿真场景及参数

本文基于NS2平台对LEACH和LEACH－TE协议进行仿真实验。考察100个节点随机分布在100m×100m区域中的传感器网络。基站位于 （50，140），由式 （4）可得E［dtoBS］＝94.86m。当N＝100时，根据式 （13）得到最优簇首数Kopt＝6。所有节点具有相同的初始能量2J。发送和接收电路能耗Eelec＝50nJ／bit，εfriss－amp和εtwo－ray－amp分 别 为10pJ／bit／m2、0.0013pJ／bit／m4。其他参数与文献 ［5］相同。

3.2 仿真结果及分析

本文网络仿真性能评价指标包括网络生存时间、能量消耗和基站接收的数据量3个方面。其中，在网络生存时间的评价标准中，引入文献 ［1］中的3种评价方法：First Node Dies（FND），即第一个节点死亡；Half of the Nodes Alive（HNA），即一半节点存活；Last Node Dies（LND），即最后一个节点死亡。

图1显示的是原有的LEACH协议和改进后的LEACH－TE协议网络中存活节点数随运行时间变化的曲线。LEACH协议第一个节点死亡的时间为410轮，而LEACH－TE协议第一个节点死亡的时间为510轮，比LEACH协议提高了约25%；LEACH－TE协议一半节点死亡的时间比LEACH协议提高了约45%，最后一个节点死亡的时间比LEACH协议也提高了约45%，见表1的统计数据。这表明LEACH－TE协议能更有效地均衡网络的能耗负载，进一步延长系统的生命周期。

图1 网络存活节点数随运行时间变化关系

表1 两种协议的存活节点数统计

图2显示的是原有的LEACH协议和改进后的LEACH－TE协议网络能耗随运行时间变化的曲线。LEACH协议在第200轮前消耗的能量为85.98J，而LEACH－TE协议此时的能耗仅为58.81J，在这一阶段相对LEACH协议能耗降低了约46.20%。在第300轮，400轮前LEACH－TE的能耗也比LEACH分别降低了约25.83%，21.09%，见表2的统计数据。由此可见，在相同的时间里，LEACH－TE协议的能耗比LEACH协议要低，具有更高的能量利用率。

图3显示的是原有的LEACH协议和改进后的LEACH－TE协议基站接收的数据量随运行时间变化的曲线。LEACH协议在第一个节点死亡时基站接收的数据量为0.891002×106bit，而LEACH－TE协议此时基站接收的数据量为1.28864×106bit，在这一阶段相对LEACH协议基站接收的数据量增加了约44.63%。在一半节点死亡和全部节点死亡时LEACH－TE协议基站接收的数据量也比LEACH协议分别增加了约83.11%和79.01%，见表3的统计数据。由此可见，LEACH－TE协议在相应的时间段内要比LEACH协议转发到基站的数据量大。

图2 网络能耗随运行时间变化关系

表2 两种协议的网络能耗统计

图3 基站接收的数据量随运行时间变化关系

表3 两种协议基站接收的数据量统计

4 结束语

本文针对LEACH协议簇首选择策略的不足，提出了一种改进协议LEACH－TE。该协议在重新计算最优簇首数的基础上，通过综合考虑节点的剩余能量和网络的平均能量等因素来优化簇首的选择。仿真结果表明，改进后的协议在网络生存时间、能量利用率和基站接收的数据量3个方面相对于LEACH协议都有较大的提高。在今后的工作中，可以考虑从簇首节点到基站的距离以及簇成员节点到簇首的距离方面对算法进行改进，使得簇首的选择更为合理；也可以考虑对整个传感器网络进行区域划分，在每个区域内部进行簇首的选择和数据的传输，以保证每轮形成的簇的数目和簇内节点数都大致相同，进一步延长系统的生命周期。

［1］Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster－head selection［C］.Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks. Stockholm，Sweden：IEEE Communications Society，2002：368－372.

［2］YUE Shicheng，WANG Peikang.Energy efficient routing algorithm for wireless sensor networks ［J］.Computer Engineering，2008，34 （7）：113－117 （in Chinese）. ［乐世成，王培康.无线传感器网络中的节能路由算法 ［J］.计算机工程，2008，34（7）：113－117.］

［3］CHEN Xuejiao，LI Xiangyang.Research and improvement of LEACH protocol in wireless sensor networks［J］.Journal of Computer Applications，2009，29 （12）：3241－3243 （in Chinese）.［陈雪娇，李向阳.WSN中LEACH协议的研究及改进 ［J］.计算机应用，2009，29 （12）：3241－3243.］

［4］Edward J.An energy efficient hierarchical clustering algorithm for wireless sensor networks ［C］.Proceedings of the IEEE Wireless Communications and Networking Conference.New Orleans，LA，USA：IEEE，2003：1713－1723.

［5］Heinzelman W B，Chandrakasan A P，Balakrishnan H.Application－specific protocol architectures for wireless networks ［J］.IEEE Transactions on Wireless Communication，2002，1 （4）：660－670.

［6］LI Zhenke，CHEN Guoding，WANG Shuhua.Improved routing algorithm based on LEACH ［J］.Journal of Computer Applications，2009，29 （z2）：63－65 （in Chinese）.［李振科，陈国定，王淑华.基于LEACH协议的改进路由算法 ［J］.计算机应用，2009，29 （z2）：63－65.］

［7］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks：Communication clustering and aggregation ［J］.Ad Hoc Networks，2007，2 （1）：45－63.

［8］FAN Xiangning，SONG Yulin.Improvement on LEACH protocol of wireless sensor network ［C］.International Conference on Sensor Technologies and Applications.Washington，DC，USA：IEEE Computer Society，2007：260－264.

［9］SUN Limin，LI Jianzhong，CHEN Yu，et al.Wireless sensor network［M］.Beijing：Tsinghua University Press，2005 （in Chinese）. ［孙利民，李建中，陈渝，等.无线传感器网络［M］.北京：清华大学出版社，2005.］

［10］WANG Shu，YAN Yujie，HU Fuping，et al.The theory and applications of wireless sensor network ［M］.Beijing：Beihang University Press，2007 （in Chinese）.［王殊，阎毓杰，胡富平，等.无线传感器网络的理论及应用 ［M］.北京：北京航空航天大学出版社，2007.］

［11］SONG Wen，WANG Bing，ZHOU Yingbin，et al.The technology and applications of wireless sensor network ［M］.Beijing：Publishing House of Electronics Industry，2007 （in Chinese）.［宋文，王兵，周应宾，等.无线传感器网络技术与应用 ［M］.北京：电子工业出版社，2007.］

［12］YE M，LI C F，CHEN G H，et al.An energy efficient clustering scheme in wireless sensor networks ［J］.International Journal of Ad Hoc ＆ Sensor Wireless Networks，2007，3（2）：99－119.

［13］WANG Shengrong.The research and improvement of leach routing protocol in wireless sensor networks ［D］.Jinan：Shandong University Master’s Thesis，2008 （in Chinese）.［王声荣.无线传感器网络LEACH协议的研究与改进 ［D］.济南：山东大学硕士学位论文，2008.］

［14］LATIFF NMA，TSIMENIDIS C C，SHARIF B S.Energyaware clustering for wireless sensor networks using particle swarm optimization［C］.IEEE 18th International Symposium，2007：1－5.

［15］CHANG Ruayshiung，KUO Chiajou.An energy efficient routing mechanism for wireless sensor networks［C］.Proceedings of the 20th International Conference on Advanced Information Networking and Applications.Hualien，Taiwan：IEEE Computer Society，2006.