路由算法LEACH的改进研究

应越

（杭州师范大学钱江学院，浙江 杭州 310012）

一.引言

LEACH（Low-Energy Adaptive Clustering Hierarchy）协议是第一个在无线传感网络中提出的分簇式路由协议，其后的大部分分簇式路由协议都是在它的基础上发展而来的。LEACH协议是MIT的Heinzelman等人为无线传感器网络设计的低功耗自适应分簇式路由算法。该算法的基本思想是先将传感节点恰当分簇（Clustering），然后为每个簇（Cluster）选取簇头，簇内非簇头节点直接与簇头通信，而簇头节点在接收到本簇之内所有节点的数据后进行数据融合，然后发给数据Sink。该算法通过随机选择每簇簇头，平均分担中继通信业务来实现负荷的均匀分担。LEACH协议定义了"轮"(round)的概念，每一轮随机选择簇头，动态分簇，由簇头承担中继通信业务。下一轮工作周期重新选择簇头并分簇。采用这种方法可以使因中继业务繁重而衰竭的节点呈均匀分布状态，LEACH可以延长网络的生命周期。但是LEACH假设所有的节点都能直接与每簇簇头和Sink通信，因每簇的大小受限，而且整个网络规模的扩张性也并不良好。而且动态分簇引起路由计算的时延和计算处理的能耗。当然，LEACH算法的主要缺陷为：非簇头节点均需直接和簇头节点通信，参与大距离通信的节点数目依然很多。

二.LEACH算法概述

1.算法环境

在开发协议的过程中，对传感器网络和网络模式做了如下假设：

假设所有节点都能够与汇聚点直接通信；节点可以使用电源控制来控制发送能量的不同；每个节点都具备支持不同MAC协议的计算能力；进行信号处理的能量是可以计算的。

无线传感器节点能量受限，在最初的簇首选择回合中，所有的节点都携带相同的能量，并且每个成为簇首的节点都消耗大致相同的能量。无线电信号传输在各个方向上能量消耗相同。节点可感知它的剩余能量，并能相应地改变它的发射功率。

2.算法描述

LEACH(Low-Energy Adaptive Clustering Hierarchy)协议是第一个在无线传感器网络中提出的层次式路由协议，其后的大部分层次式路由协议都是在它的基础上发展而来的。LEACH协议节约能量的主要原因是它运用了数据压缩技术和分层动态路由技术，通过本地的联合工作来提高网络的可扩展性和鲁棒性，通过数据融合来减少发送的数据量，通过把节点随机地设置成群头节点来达到网络内部负载均衡的目的，防止群头节点的过快死亡。LEACH协议分为两个阶段操作，即簇类建立阶段（set-upphase）和稳定工作阶段（steady-state phase）。簇类建立阶段和稳定工作阶段持续时间总和为一轮（round）。在簇类建立阶段，LEACH协议随机选择一个传感器节点作为簇头节点，随机性确保簇头与Sink之间数据传输的高能耗成本均匀的分摊到所有传感器节点。在簇头节点选定后，该节点对网络中所有节点进行广播，广播数据包含有该节点成为簇头节点的信息。一旦传感器节点收到广播数据包，根据接收到的各个簇头节点广播信号强度，该节点选择信号强度最大的簇头，加入该簇，发送成为其成员节点的数据包。分簇形成后，簇头采用TDMA策略分配信道使用权给成员节点。一旦处于稳定工作阶段，簇头节点开始接收该簇中每个节点采集的数据，然后采用数据融合和数据压缩等技术进行汇聚，将整合后的数据传输给Sink，在稳定阶段持续一段时间后，网络又进入另一次分簇建立阶段。

3.存在不足

从上一节的分析，我们知道LEACH协议的精华内容是分布式的成簇技术和自适应的成簇算法以及簇首位置的轮换算法。其中分布式的成簇技术保证了大数口的节点的自组织行为。自适应的成簇算法以及簇首位置的轮换算法保证所有节点公平地承担能量消耗的负担，最终可以延长整个系统的生存时间。主要的不足有些下几方面：

①簇首的产生具有极大的随机性，可能会出现部分簇首相距sink节点太远或部分簇内成员离簇首太远的情况，大大增加了节点的传输能耗，故不能有效地延长网络生存时间。

②LEACH算法随机选择簇首并没有考虑到节点的能量状态，不能有效提高网络的生存时间。能量消耗均衡机制要求所有节点的初始能量相同，但这在实际的应用中保证此初始条件比较困难。

③由于每轮固定簇头之后再建立簇类，所以簇头开销较大，并且离散式区域算法虽然对于节点位置等要求不高，但无法做到最优。

④由于LEACH要求节点之间以及节点与基站之间均可以自接通信，所以网络的扩展性不强，并且不适用于大型网络。

⑤LEACH的传输距离较远，并且数据融合相对较少，这就要求传输更多的数据到更远的距离，从而加大了能量消耗。

三.LEACH算法改进

为了避免低能量级与位置不佳的节点被选为簇首，进一步均衡整个网络的能量负载分布，提出一种新型的簇首选择机制。LEACH提出簇头位置随机轮换算法来避免太快地消耗完某个充当簇头节点的能量，就是让簇类中的每个节点轮流成为簇头，这样就能避免由于一个节点的失效而引起的网络瘫痪，起到延长整个网络生命周期的作用。但是LEACH协议的簇头位置轮换算法是山每个簇头产生一个随机数并与系统给定的门限值比较，即簇头是每轮随机产生的，故有可能存在某一节点的剩余能量己经很小但仍被选为簇头节点的情况。这样这个节点的能量就可能很快耗尽。

该算法在LEACH的基础上，利用加权思想使节点产生一个改进的权值概率，通过与随机产生的概率阈值相比来选择簇首，进而生成整个簇，改进的权值概率要综合考虑节点所处的网络环境和本身状态。基于网络能耗最小的考虑，通过数学推导和仿真实验，一般选取簇首比例为5%，为了使得权值概率能维持5%的平均值，权值因子可以起到调节作用，以确保最优簇首个数的选取。

权值因子在成簇概率中调节着距离因素和剩余能量因素之间的权衡关系，权值因子值的确定自接影响着成簇概率的大小，决定了协议优化的效果。看出，随着权值因子的增大，第一个节点死亡的时间也随之减小，这是因为随着权值因子的增大，距离函数开始占据主要作用，导致网络中处于理想位置的节点更容易成为簇首，增加了这部分节点的能量消耗，从而使得这些节点过早的死亡。反之，权值因子减小的时候，簇首主要是根据网络中的节点的剩余能量来选择，所以更进一步的考虑了网络的能量消耗平衡，使得网络中第一个节点死亡的时间往后推迟。随着权值因子增大时，处于理想位置的节点总是优先被选为簇首，所以减小了网络的总能量消耗，进而使得网络中最后一个节点死亡的时间得到延迟。

结束语

本文在LEACH协议的基础上使用新型的簇首选择机制来扩大了LEACH协议的应用范围，算法利用加权思想综合考虑节点的剩余能量、地理位置等参数来优化簇首的选择，从而有效地避免了低能量与位置不佳的节点被选为簇首的可能性，进一步保证网络内节点能量负载的均衡性。结果表明，与LEACH协议相比，新型的簇首选择机制算法明显延长了网络的生存寿命。

[1]孙利民，李建中，陈渝，朱红松著.无线传感器网络[M].北京：清华大学出版社，2006.

[2]周东清，葛午未，朱娜.基于QoS的无线传感器网络路由 [J].计算机工程与应用.2007，43（23）：157-160.

[3]宋文，王兵，周应宾等著.无线传感器网络技术与应用[M].北京：电子工业出版社，2007.