低功耗自适应分群分层LEACH协议的研究

韩春霞，王琳杰

(1.铜仁学院数学与计算机科学系,554300；2.铜仁学院计算机应用技术研究所，贵州铜仁,554300)

目前，无线传感器网络的路由协议是国内研究的热点。一个路由协议往往对能量有效性、可扩展性、数据传输可靠性、实现复杂度、稳健性等很多因素进行综合考虑而折中得到的。根据节点在路由过程中是否有层次结构、作用是否有差异，可分为平面路由协议和层次路由协议。平面路由协议简单、健壮性好，但建立、维护路由的开销大，可以用于中小规模的网络；层次路由则能够提高协议的可扩展性，同时还能方便地支持数据聚合，适用于大规模网络，成为当前重点研究的路由技术。

无线传感器网络低能量自适应分群分层LEACH（Low Energy Adaptive Clustering Hierarchy）是一个协议体系，进行本地计算以减少发送数据量，采用本地控制进行网络配置和网络操作。LEACH将能量高效分群路由协议和MAC协议与应用特定数据累积综合在一起，共同达到良好的系统寿命、时延、应用感觉到的服务质量。LEACH是能够组织大量节点的分布式分群技术，实现均匀分布所有节点间能量的自适应算法和群首位置循环算法。

LEACH协议有更优于其他的路由协议的特性，但也存在着许多的不足之处有待研究改进，本文就LEACH协议的改进方案作为研究的主要目标。

1 LEACH协议概述

低功耗自适应分群算法(LEACH)并不是一个单纯的路由协议，它提供了一个包括分群、路由、MAC和物理层的完整的无线传感器网络的协议框架。LEACH把网络的工作过程分成轮，每一轮包括建立期和稳定期。在建立期执行分群协议，把网络分成若干个群；稳定期分成若干帧，在每一帧，成员节点向群首发送数据，群首合并后发送给远端的BS。

在LEACH协议中，群首是本地控制中心，协调其群内的数据传输。其中，主要是分群建立阶段、数据稳定传输阶段。在分群建立阶段，传感器节点随机生成一个0-1之间的随机数，如果选定的值小于某一域值T(n)，那么这个节点成为群首节点。在数据稳定传输阶段，传感器节点在自己的时隙中将采集的数据传送到群首节点，群首节点经过数据融合再将数据传送到BS基站。每个群采用不同的CDMA代码进行通信减少其他群内节点的干扰，详细的LEACH协议工作流程可参见文献资料。

2 LEACH的改进策略

2.1 LEACH协议的优缺点

相比于其他路由协议，虽然LEACH协议拥有许多优点。比如动态分配群首算法、分层簇型结构等。尽管如此，LEACH也存在着许多不足，在LEACH协议中，群首的选择由随机数产生，很少考虑当前节点剩余能量及当前节点与Sink节点的位置关系，导致WSN中节点间的能量不均衡及位置分布不均匀。在每次建立分群的过程中，每个非群首节点也要参与其中，这就增加了分群的复杂程度。在数据传输阶段，由于群首节点与Sink节点直接通信，导致远离Sink节点的群首消耗更多的能量，致使该节点迅速死亡，出现监控盲区。

2.2 LEACH的改进策略

LEACH算法的改进是多种多样的，近年来，国内外许多研究学者提出了很多改进算法。在LEACH协议改进中，很多人一直是把改进群首选择算法作为研究的重点，比如在早期的改进算法中有DCHS，它的改进是在选取群首概率公式中加入了能量比例因子，使剩余能量较高的节点有更多的机会当选为群道节点，但这并没有考虑这个节点是否曾当选过群首节点。

LEACH-C和LEACH-F采用的都是中心分群算法，它们在数据稳定传输阶段与LEACH协议相同。在分群建立阶段，是通过每个节点发送其当前位置信息和能量信息给BS进行信息交互，为此，BS根据所得的每个节点的信息，结合全局信息寻找最佳群首。但是这两种算法，每次通信每个节点都要与BS进行交互信息，增加了不少的能量消耗。

王万良等人提出了一种基于LEACH的改进算法，改进思想是在分群的建立阶段，所有候选节点必须是曾从未当选过群首的节点，并且该侯选节点的能量必须大于前r轮中群首节点的平均能量，防止个别节点快速死亡。该算法的缺点是每个参与竞争群首的节点必须知道前r轮群首节点的平均能量，需要多次与BS进行信息交互，增加了一定的能量消耗。

顾相平等人提出了LEACH-ED算法，该分群算法结合了剩余能量和群首间距离约束。在选择群首时，如果生成的随机数小于加入能量因素的阀值，就计算该节点与群首间的距离，当大于某一距离时，该节点才能成为群首。由于每次都需要计算竞选群首节点与现有群首节点间的距离，这不仅增加了算法的复杂度，还增加了节点的能量消耗。

李天池提出了LEACH-IMP算法，该算法主要针对群首选择提出的改进策略。LEACH-IMP将LEACH群首选择分为了全网群首选择，半网群首选择，群内群首选择。在改进算法中，先设置了一个能量阀值，每个分群周期开始时，计算平均群能量和群内平均能量，判断现有群中的平均群能量是否小于能量阀值，如果是，启动半网群首选择号召，这时其他的群根据自己群的情况决定是否要响应半网群首选择号召，所有响应半网群首选择号召的群将在下一轮中按照全网选择规则进行重选。否则，每个群首再判断自己的剩余能量是否小于群内平均能量，如果比群内平均能量小，则在本群内响应群首选择，否则，不进行任何群首选择。此算法的改进，可以避免每轮群首选择时，都要进行全网群首选择。设置每隔一定轮数后，强制进行全网选择，可以平衡半网选择导致的能量不均衡。在全网选择机制和半网选择机制中，改进算法均考虑了能量因子和距离因子，使距离近的节点能更大的机会当选为群首，以更好地均衡能量消耗。但在半网选择中，每一轮，都要计算群内平均能量，一定程度上，又增加了能量消耗，从改进算法的流程看，又增加算法的复杂度。

柳丽娜提出的LEACH-L算法针对LEACH算法中群首选择的不均以及能耗较大等问题进行改进。在群首选举阶段，改进主要通过引入时间延迟Twait ，使剩余能量越大的节点以更大的可能性成为群首，这就使整个网络系统的能耗更为均衡，同时从覆盖面积的角度进行考量，使群首的分布更加均匀。在数据传输阶段，LEACH-L采用的是单跳和多跳相结合的方式。最开始选取群首的时候所有节点都向基站发送了信息，基站对每个群首的地理位置和剩余能量等信息都了如指掌，并且因为基站的位置是固定不变的，所以每个群首到基站的距离都是可以知道的，于是把群首剩余能量和他们与基站的距离作为判断的标准来确定是选择单跳还是多跳的方式进行数据通信。

刘长江提出了一种加权的最优阀值路由算法LEACH-M，LEACH-M算法在群首选择时，改进重点是提出新的节点阀值计算公式T（n），该公式考虑了能量和节点未当选群首的的轮数。在群的建立时，LEACH-M引入权重因子F，该公式综合考虑了节点与群首、群首与BS间距离、群首剩余能量等因素。这样引入F，在群的建立阶段，尽可能使群首分布均匀，而且减少网络中能量的消耗，达到节能。

李成岳等人提出的LEACH-T算法的改进主要针对群首的选择过程。在群首选择时，引入一个随机时间间隔，为每个节点设置一个计时器T，T的计算综合考虑节点的剩余能量、节点距离BS的位置、节点曾经当选群首的次数，当到达计时时间后，具有最短时间间隔的节点有更大机会成为群首节点。与原有的LEACH算法相比，LEACH-T具有更好的性能，它不仅保留了分布式群首产生的优点，还避免了每轮产生群首个数的不确定性，更能均匀分布群首节点，使群首节点的选择趋于合理，从而达到网络能耗均衡，节省能量，最大化生命周期的目的。

3 总结

LEACH算法的改进是多种多样的，在上述的改进方案中，有的提出了一套完整的从群首选择到数据传输的新的算法，而有的改进算法只是针对其中一个阶段提出了新的想法。以上关于LEACH协议算法的改进仍然保留着原有的LEACH协议算法思想，都是以如何节省能量和延长网络生命周期作为改进考虑的核心问题。对以上算法的改进，仿真实验表明，相比于传统的LEACH在延长网络生存时间、节省能量和平衡节点能量消耗等方面有更优的性能。

[1]陈林星编著.无线传感器网络技术与应用[M].电子工业出版社.2009.3:151-156

[2]Handy M J,Haase M,Timmermann D.Low Energy Adaptive Clustering Hierarchy W it h Deter ministic C luster-head Selection[C]//Proceedings of the 4th I EEE Conference on Mobile and Wireless Communications Networks.I EEE Communications Society,2002:368-372.

[3]Heinzelman W B.Application-Specific Prot ocol Architect u res for Wireless Network s[D].Ph.D Dissertation.Boston:Massachusetts Institute of Technology,2000.

[4]王万良,陈陪俊,郑建炜.一种基于 LEACH的无线传感器路由算法及其仿真[J].系统仿真技术,2008,4(2):75-79

[5]顾相平,孙彦景,钱建生.一种改进的无线传感器网络 LEACH-ED 算法[J].传感技术学报,2008,21(10):1770-1774

[6]李天池.无线传感器网络LEACH协议的算法改进[D],山东大学.2012.3

[7]柳丽娜.无线传感器网络中LEACH算法的研究和改进[D],吉林大学.2012.5

[8]刘长江.基于能耗优化的无线传感器网络LEACH协议研究与改进[D].广西大学.2012.6

[9]李成岳,申铉京,陈海鹏,孙恩岩.无线传感器网络中LEACH路由算法的研究与改进[J].传感技术学报.2010年8月第23卷第8期:1163-1167