基于LEACH的无线传感器网络路由协议改进算法*

翁锦深，秦华标，张宗国

（华南理工大学电子与信息学院 广州510640）

1 引言

无线传感器网络由许多具有低功率无线收发装置的传感器节点组成，能够有效地在不同环境中监测收集周边环境信息，并传送到远处的基站进行处理。无线传感器网络可以被广泛地应用于军事、商业、医疗救护和环境监测等多方面。由于传感器节点的电池能量有限，因此节点的通信应该有效地利用能量，以延长网络的生命周期[1]。LEACH协议是一种典型的、可以有效延长网络生命周期的节能路由协议，然而其存在很多不完善的地方，主要体现在3方面：一是簇头的产生具有极大的随机性，可能会出现部分簇头相距过近或部分区域的节点离簇头太远的情况，大大增加了节点的传输能耗；二是每个簇中节点数目分布不均匀，网络拓扑结构分布不均匀使节点能耗不一，大大减少了网络生存时间；三是LEACH协议采用单跳的形式，所有节点都可以与汇聚节点直接通信，距离汇聚节点远的簇头能量消耗巨大，并且也不适合在规模较大的无线传感器网络中应用。针对LEACH协议的缺点，很多参考文献提出了相应的改进算法。参考文献[2]通过建立多层次的聚类方法减少节点之间的通信距离，从而降低系统的能耗。参考文献[3]提出了一种基于分簇的自适应混合型路由控制算法，该算法针对大规模时间驱动型网络场景应用，采用网内节点启发机制，解决了LEACH算法面对大规模网络缺乏自适应性、通信效率难以得到保障等问题。参考文献[4]引入簇成员数门限和合并极小簇的方法，避免极大簇和极小簇同时存在的问题。参考文献[5]在簇头数据传输方面将网络中均匀分布的簇头构造成一棵路由树，通过多跳传输的方式，减少直接与基站通信的簇头节点数量。参考文献[6]主要针对无线传感器网络面临的众多安全问题，从组合公钥和节点能量入手，对LEACH协议进行了改进。

综上所述，对LEACH协议的改进可以归结为对簇头选择算法的改进、簇形成阶段算法的改进、多跳路由方法的实现、数据融合算法[7]的改进等。而众多参考文献也主要针对LEACH协议缺点的一两点进行相应改进，本文综合考虑了LEACH协议的几大缺点，从簇头选举算法、簇形成阶段、多跳路由的实现等方面入手，提出了改进协议算法LEACH-Ⅱ协议。

2 LEACH-Ⅱ协议

2.1 LEACH-Ⅱ协议的簇头选举算法

LEACH簇头的选举过程[8]是：节点从0～1中随机选择一个值，若当前轮中这个值小于设定的阈值Ti（n），则该节点成为簇头，阈值Ti（n）按式（1）计算：

其中，p为期望的簇头节点在所有传感器节点中的百分比，r是当前的轮数。LEACH簇头选择算法虽然实现了簇头随机产生，各节点当簇头的机会相对均等，但是实际上随机产生簇头很容易导致多轮运行后各节点剩余能量相差较大而使大部分节点死亡。所以，LEACH-Ⅱ协议在选择簇头时，不仅考虑了各节点成为簇头的概率，还综合考虑了节点剩余能量、平均能量和最大能量的大小，保证簇头尽量在能量高的节点中产生，避免能量低的节点成为簇头。

LEACH-Ⅱ协议的簇头选举算法中，阈值Ti(n)的定义为：

其中，Ecurrent为节点当前的能量，Emax为当前各节点中剩余能量的最大值，Eaverage为当前各节点能量的平均值。LEACH-Ⅱ协议的簇头选举策略同LEACH协议相比，发生了很大的变化：节点能否成为簇头，不仅与随机概率有关，还与节点本身能量、平均节点能量有关。如果一个节点能量较小，小于各节点的平均能量，它成为簇头的几率就会大大减少；反之，如果一个节点的能量较大，远远大于各节点平均能量，它成为节点的几率就比能量低于平均能量的节点大得多。更重要的是，它也保留了LEACH协议随机产生簇头的机制。LEACH-Ⅱ协议的簇头选举策略大大改善了LEACH协议中因距离不等而导致大批节点不均匀死亡的问题。其流程如图1所示。

2.2 LEACH-Ⅱ协议的簇形成阶段算法

某轮簇头选举出来后，就到了簇的形成阶段，即节点选择簇头并成为该簇的簇成员。在LEACH-Ⅱ协议的簇形成阶段中，簇头会利用CSMA(carrier sense multiple access，载波侦听多路访问)的MAC机制广播一个通告消息ADV，并定义一个系统参数NM，初始化为0。ADV本身是一个很小的消息，仅包含了节点ID和表明信息类型的头部。非簇头节点接收到通告消息后，首先判断各簇头消息信号的强弱，然后选择发送通告信号最强的那个簇头，并加入该簇成为其簇成员。该节点同时会给簇头发送一个请求消息joint-REQ，这个消息和通告消息ADV类似，也仅由节点ID和簇头ID构成。簇头每接到一个joint-REQ消息，NM就自动加1。当NM增加到为当前存活节点数，k为簇数）时，簇头将禁止别的节点再加入本簇。如果此时簇头还有别的节点发来的joint-REQ消息，簇头将给该节点发送一个拒绝消息。这个信息类似于ADV消息，所不同的是，原来表示信息类型的部分被填充了表示拒绝的内容。收到拒绝消息的节点将检查所收到的所有通告消息ADV，根据信号强弱，挑选发出第二强信号的簇头作为自己将要加入的簇，然后再重复之前的过程，给该簇头发送一个请求消息joint-REQ。一个簇建立起来后，簇头根据簇内节点情况建立一个TDMA(time division multiple access,时分多址)调度，并把这个调度通知给簇内各节点。为了减少能量消耗，簇内非簇头节点将一直关闭无线电模块，直到处于各自的传输阶段才重新开启。TDMA调度保证了各非簇头节点传输数据不会发生冲突。

LEACH-Ⅱ协议的簇形成阶段还对形成的时间做了规定，具体操作时在簇头函数里添加了一个时间定时器。一旦超过了这个时间，簇头将不再接受节点入簇的申请。簇形成阶段中簇头和非簇头对应的工作流程分别如图2和图3所示。

2.3 LEACH-Ⅱ协议的多跳路由实现

LEACH-Ⅱ协议的多跳路由具体实现为：节点成为簇头后，会向周围节点广播通告消息，当汇聚节点获取到各个簇头的广播消息后，便根据这些簇头通告消息的强弱，把信号最强的那个簇头定义为第一簇头(the first cluster)。其他簇头将不再向汇聚节点传递数据，而是先把数据传递给第一簇头，由第一簇头对其他簇头传递过来的数据做进一步的融合处理之后，再传递给汇聚节点，从而实现簇头与汇聚节点之间的多跳路由，LEACH-Ⅱ协议的多跳路由示意如图4所示。

LEACH-Ⅱ协议多跳路由第一簇头选举流程如图5所示，定义第一簇头的多跳路由的优点是距离汇聚节点较远的簇头先把数据传递给第一簇头，大大减少了能量的消耗。虽然这会大大增加第一簇头的负担，但从总体上看，它依旧有利于节省网络的总能量。

当网络处于多跳路由的工作方式时，一般簇头不直接向汇聚节点发送数据，而是先发向第一簇头，这里会出现一个问题：在某一轮中，某个普通簇头与第一簇头之间的距离要大于该普通簇头与汇聚节点的距离，也就是说，会出现个别普通簇头因为多跳路由，能耗不但没有减小反而增大的现象。这个现象在某一轮的执行过程中可能出现，但这是小概率的事件。而在实际情况中，多跳路由考虑的是网络的总体消耗能量的减小和均衡，从整个网络长远的运作上看，大多数普通簇头节省的能量要大于个别簇头多消耗的能量。

3 仿真结果和分析

为了检验LEACH-Ⅱ协议的性能，首先在NS2平台上对LEACH和LEACH-Ⅱ协议进行仿真。仿真分为两部分：一是基于不同初始能量0.5 J、1 J的仿真；二是基于不同汇聚节点位置((50,-50)、(50,-100)、(50,-150))的仿真。接着针对本文改进协议LEACH-Ⅱ和已有的LEACH改进协议LEACH-C进行对比仿真。

3.1 基于不同初始能量的仿真

在初始能量分别为0.5 J和1 J的情况下，两种协议的网络生存周期如图6和图7所示。

其中横坐标代表轮数，纵坐标代表存活节点的数目。如图6所示，不管节点初始能量为多大，LEACH-Ⅱ协议运行的轮数均要大于LEACH协议。也就是说，LEACH-Ⅱ协议延长了网络的生命周期。初始能量为0.5 J时，LEACH-Ⅱ协议的网络周期由LEAC协议H的不足800轮延长到了近900轮，网络寿命延长了12.5%。从图7可以看出，初始能量为1 J时，LEACH协议运行了1 378轮，而LEACH-Ⅱ协议整整多出了200轮，网络寿命延长了14.5%。事实上，初始能量越高，LEACH-Ⅱ协议网络寿命延长的效果就越明显。这说明，LEACH-Ⅱ协议的各簇内成员经过数量均衡和簇头选举优化后，节点在传输数据时消耗的能量变得均衡了，网络寿命得到延长。

在初始能量分别为0.5 J和1 J的情况下，两种协议的网络总能量消耗如图8和图9所示。

初始能量为0.5 J时，LEACH-Ⅱ协议中节点总能量消耗的速度明显比LEACH协议慢。在前500轮中，由于节点数量多，传输数据任务重，总能量急剧减小，但是LEACH-Ⅱ协议减小的速度始终比LEACH协议慢。初始能量为1 J时和0.5 J时的趋势一致，即LEACH-Ⅱ协议的能量消耗速度要小于LEACH协议。LEACH-Ⅱ协议能量消耗得慢，从而延长了网络的生存周期，可见总能量消耗图同节点生成图互相对应。

初始能量不同时，通过对LEACH-Ⅱ协议和LEACH协议的仿真结果分析比较可知，LEACH-Ⅱ协议无论是在网络生存周期还是在能量消耗方面都有了较大的改善。

3.2 基于不同汇聚节点位置的仿真

上面通过不同初始能量的仿真得出了LEACH-Ⅱ协议优于LEACH协议的结论。接下来是对汇聚节点分别位于(50,-50)、(50,-100)和(50,-150)这3种情况下的网络生存周期进行仿真。为了方便分析，本次仿真只关注节点死亡10%、25%、50%、75%和100%这5个点。3种情况下的节点存活仿真结果分别如图10～图12所示。

其中，横坐标代表能量耗尽的节点数量，纵坐标代表轮数。如图10、图11和图12所示，即使汇聚节点在不同位置，LEACH-Ⅱ协议的生命周期也均大于LEACH协议的生命周期。汇聚节点在(50,-50)时，LEACH-Ⅱ协议中10%、25%、50%、75%和100%死亡节点的运行轮数均大于LEACH协议。汇聚节点在(50,-100)和(50,-150)时，死亡相同节点LEACH-Ⅱ协议运行的轮数均比LEACH协议多；且可以看出汇聚节点离普通节点越远，LEACH-Ⅱ协议的优越性越明显。

3.3 LEACH-Ⅱ协议与其他改进算法的比较

在LEACH协议的各种改进算法协议中，LEACH-C协议[9]是目前为数不多的公开源代码的LEACH改进协议。LEACH-C协议以循环的方式选择簇头，将整个网络的能量负载和通信业务平均分配到每个节点，改善了LEACH随机选择簇头导致的簇头分布不均和没有考虑节点能量的缺点，从而可以更好地降低传感器的能量消耗。

本文主要从生存周期和总能量消耗两方面对LEACH-Ⅱ协议和LEACH-C协议进行仿真对比。其中初始能量设为1 J，汇聚节点坐标(50,-150)，仿真结果如图13和图14所示。

如图13所示，50%节点死亡，LEACH-Ⅱ协议在第1 163轮出现该情况，LEACH-C协议在第1 098轮出现，LEACH-Ⅱ协议比LEACH-C协议提高5.91%。LEACH-Ⅱ协议在经过1 534轮后节点全部死亡，LEACH-C协议最后节点死亡则出现在第1 501轮，LEACH-Ⅱ协议比LEACH-C协议提高2.19%。从图14也可以看出，在能量消耗方面，LEACH-Ⅱ协议比LEACH-C协议略占优势。

因此，无论在网络存活周期方面还是网络耗能方面，LEACH-Ⅱ协议都要优于LEACH-C协议，虽然优势并不是十分明显。但从理论上讲，LEACH-C协议采用退火算法使簇头总能从能量大的节点中产生，虽然消除了簇头选举的随机性并考虑了节点的能量，但在簇形成过程中极大极小簇问题以及单跳方式使得距离汇聚节点远的簇头能量消耗巨大的现象依旧存在，而LEACH-Ⅱ协议综合考虑了这些问题，它的优势在于簇头选举阶段不受汇聚节点的控制，簇内节点数量均衡和简单多跳，因此在总能量消耗和生存周期方面都比LEACH-C协议都有所改善。

4 结束语

本文主要针对LEACH的不足，提出了一种高效聚类路由算法，该算法从簇头选举策略、簇形成阶段和多跳路由的实现3个方面对LEACH协议进行了改进，仿真结果表明该算法降低了总能量消耗，延长了网络的生存周期，同时算法简单、实现容易。

1 Nikolidakis S,Vergados D.Energy-efficient routing protocols in wireless sensor networks:a survey.IEEE Communications Survey& Tutorials,2012(3)

2 Meenakshi S,Kalpana S.An energy efficient extended LEACH.International Conference on Communication Systems and Network Technologies,Rajkot,India,2012

3 张小波,程良伦.SAHRC:一种基于分簇的无线传感器网络路由控制算法.电子与信息学报,2011,33(8)

4 吕涛,朱清新,张路桥.一种基于LEACH协议的改进算法.电子学报,2011,39(6)

5 尚凤军,任东海.无线传感器网络中分布式多跳路由协议算法研究.传感器技术学报,2012,25(4)

6 蔡志伟,江汀,李银勇等.基于CPK和能量的安全路由算法.电信科学,2011(10)

7 Wang J,Yu H,Shang Z.Research on reliable link layer communication in wireless sensor networks.Proceedings of the International Conference on Communication,Circuits and Systems,HongKong,2005

8 Yektaparast A,Nabavi F H,Sarmast A.An improvement on LEACH protocol(Cell-LEACH).International Conference on 14th Advance Communication Technology,PyeongChang,Korea,2012

9 HeinzelmanW,ChandrakasanA,BalakrishnanH.Anapplication-specific protocol architecture for wireless microsensor networks.IEEE Transactions on Wireless Communication,2002,1(4):60～70

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