相关专题：
摘 要：分层路由算法是延长无线传感器网络寿命的一个重要方法。然而现有的分簇算法大都存在着负载能量不均衡的问题。本文主要针对经典分簇算*EACH，对其基本思想、分簇机制和簇的通信方式等作了分析，同时对其负载能量不均衡的问题作出改进，并用MATLAB进行仿真分析。仿真后的结果表明，改进后的算法能够均衡节点的能耗，使分簇更加合理，有效延长了网络的生命周期。
0 引言
无线传感器网络是近年来信息技术领域的一个研究热点，它融合了传感器、计算机科学、信号与信息处理、通信等多个领域的技术。作为一个新兴的、正在发展的技术领域，业界对其研究正在不断深入。无线传感器网络为人类与客观物理世界的交互提供了一种新的有效手段，它的诸多特点使其应用范围涉及军事应用、工业监视与控制、医疗监护、智能家居、物流管理、消费电子等诸多领域，具有广阔的市场及产业前景。2003 年8 月，美国《商业周刊》的技术*论将无线传感网络定位成21 世纪高技术领域的四大支柱型产业之一。
在无线传感器网络中，能量有效性是网络性能的一个重要指标。它对能源消耗有着很严格的限制，应尽可能少地消耗能量以达到延长网络生命周期的目的。因此，设计一种良好的路由协议，减少不必要的能源消耗是非常必要的。本文主要探讨了低能量自适应聚类协议（LEACH），指出了LEACH 协议存在的缺陷，并给出相应的解决方案加以优化。
1 经典LEACH 协议分析
1.1 算法描述
LEAC(Low-Energy Adaptive CluSTering Hierarchy）协议是针对无线传感网络设计的一种低功耗自适应分层路由算法，是最早提出的分簇路由协议。它的基本思想是以循环的方式随机选择簇头节点，其他各节点根据接收到的来自簇头的信号强度进行集群分组，使得整个网络的能量负载平均分配到每个传感器节点中，从而降低网络能源消耗，提高网络整体生存时间。
LEACH 协议定义了“轮”的概念，每一轮由簇的建立和稳定状态阶段组成。在簇的建立阶段，首批簇头的选取是随机的。对于一个节点n 而言，为其随机选取一个在0 到1 之间的随机数，若这个数字小于一个门限值T(n)，则节点n 就成为本轮的簇头节点。门限T(n)定义如下：
其中，P 是网络中簇头节点占总节点数目的百分比；r 是当前的轮数；G 是在前1/P 轮中没有担当过簇头节点的节点集合；符号mod 是求模运算符号。
簇头节点选定后，向周围广播自己成为簇头的信息（ADV），非簇头节点根据接收到的信号强度来决定从属的簇类。当簇头收到反馈消息后，便为簇内节点分配时隙（基于TDMA 方式）。在稳定阶段，簇内节点在自己时隙到来时刻向簇头发送检测数据，簇头节点则将接收到的数据后进行必要的融合后传送到基站或汇聚节点。经过一段时间的数据传送后，网络重新进行簇的建立阶段，进行下一轮的簇重建，如此循环。
1.2 LEACH 算法的局限性
LEACH 算法将负载均匀地分布在整个网络上，大大节约了通信过程中的能量损耗。簇头位置的轮换算法把远距离通信的负载轮流分配给网络节点，可以延长整个系统的生存时间。另外，簇头节点在处理数据时用到了数据融合和数据压缩技术，使得传输的数据量大大减小。但LEACH 算法同时也存在着许多不足之处：
(1)簇头选择问题 。LEACH 协议的簇头是随机产生的，选择机制中没有考虑节点的剩余能量和节点已经做过簇头的次数。一旦所剩能量较少的节点成为簇头，将会很快耗尽其能量，过早死亡。其簇内成员也将因收不到已死簇头发出的信息而不断地发送请求信号，耗费大量的能量而导致加速死亡，降低了整个网络的生存时间。
(2)簇头数量问题。在 LEACH 协议随机选择簇头的机制中，并没有控制簇头的数量。所以很有可能在某一轮中出现只产生一两个簇头，或产生很多簇头的情况。若簇头过少，则成员节点要经过很长的路径与簇头进行通信，簇头也将接收大量节点的信息并向基站进行转发。因此对每一个节点来说都负担过重；而若产生过多簇头，则会有过多的节点与基站通信，降低了网络能量的利用率。
(3)簇头分布问题。 LEACH 协议中，虽然在统计上簇头是均匀分布的，但是由于簇头产生的随机性，可能会出现部分区域簇头密度大，部分区域簇头稀少的现象。
2 LEACH 算法的优化
上述LEACH 算法中的不足，导致了无线传感器网络负载能量不均衡。本文主要通过改进簇头节点选举算法来对LEACH 协议进行优化。主要目标是避免能量低的节点成为簇头，控制簇头数量达到最优，减少簇头在每轮中分布不均的现象。从而达到降低系统能量消耗，延长网络生命周期的最终目的。
2.1 簇头选举机制的算法改进
对于簇头选举的改进协议，在文献[6]中将其阈值作了改进：
2.2 改进算法的具体实现
算法进行优化后详细描述如下。
1)在簇的建立阶段，簇头由所有节点自主决定，在每一轮中自行生成k 个簇。k 的值由（4）式决定。
2)将每个节点的剩余能量与上一轮中预计的当前网络平均能量进行比较，若剩余能量大于网络的当前平均能量，则有资格成为簇头候选节点；否则只能等待簇头广播簇类信息。
3）能量大于当前网络平均能量的节点，判断自己生成的随机数是否小于门限值T(n)（即上文中已作改进的（3）式），若小于则成为簇头节点；若大于门限值则为成员节点，等待簇头发送告知信息 。至此，簇头的选举阶段完成。
4)成为簇头的节点，要以一定的功率发送簇头告知信息，但不是全网广播。该消息只包括簇头节点的ID 和消息标识符。在此之后簇头将等待簇成员的加入信息。
5)成员节点根据接收到的ADV 消息的信号强弱来选择一个信号强的簇头节点，并向其发送一个请求加入的消息，该消息只包括节点的ID 和簇头节点的ID。
