作者：徐世武，王 平
引言
无线传感器网络是当前网络技术界备受关注的前沿热点研究领域，涉及多学科，高度交叉，知识高度集成。无线传感器网络集成了传感器技术、计算机技术和通信技术，在军事、环境、健康、家庭、商业等许多方面有着巨大的潜在应用前景。无线传感器网络由大量密集分布的传感器节点通过自组织的方式形成网络，节点通过网络协议快速形成自主构建、自主组织和自主管理的通信网络。这种通过数千个微小的节点之间互相通信，通过接力的方法实现大范围监控的模式极大地提高了工作效率。然而节点大都需要在无人看管、不更换电池或者不可能更换电池的条件下长时间地工作，因此高效、低功耗路由算法在无线传感器网络中就显得非常重要。
1 基于LEACH的经典分簇算法分析
1．1 LEACH路由算法分析
为了提高整个网络的的生存时间，将功耗均衡的分配到网络中的每个节点，麻省理工学院的Wendi Rabiner Heinzelman等人提出了一种低功耗的自适应路由协议——LEACH协议(Low-Energy Adaptive ClusteriingHierarchy)。在LEACH协议中，每个传感节点都有机会充当簇头节点，簇头节点的选择主要依据网络中所需要的簇头节点个数与到目前为止每个节点已经充当簇头节点的次数来判定的。网络中每个节点在0～1之间随机选择一个数，如果选择的数小于规定阀值T(n)，则该节点就充当簇首节点。T(n)的计算如下：
式(1)中，p表示在无线网络中簇头节点所占的百分比，r为当前循环次数，G是在前1／p轮中未充当过簇头节点的集合。LEACH算法通过设置T(n)值，以保证每个节点在1／p轮内都有机会充当一次簇头节点，从而平衡了节点的能量消耗。簇头节点确定之后，簇头节点通过广播告知整个网络自己已经成为簇头节点，簇头节点在广播过程中采用CSMA MAC协议来避免冲突。这时，网络中的非簇头节点可以根据接收到的信号强度来决定自己要从属于哪个簇，选择信号强度最强的源节点作为自己的簇头节点，并告知相关的簇头节点，自己则成为簇内组员。
LEACH分簇算法缺点：
①刚开始假设每个节点能量相同，在现实环境中很难做到。
②每个节点成为簇首节点的概率相同，这样可能导致一些高能量节点没机会成为簇首节点，而一些低能量节点成为簇首节点。一旦这些低能量节点成为簇首节点，将会很快耗尽其能量。
③LEACH协议不能保证簇头在每个区域都分布均匀，虽然统计上面是均匀的，但是由于簇头产生带有极大的随机性，有些区域可能簇头数会较多。
④簇首节点在通信过程中采用单跳与基站通信，这样就会导致较远的簇首节点能量消耗过大，而过早死亡，影响整个网络的性能。
⑤整个网络节点在两跳范围内，这样不符合大规模网络需求。
1．2 根据节点初始能量不同改进
根据整个网络中节点能量的初始不同，Georgios Smaragdakis等人提出了一种改进行分簇算法——SEP算法(a Stable Election Proto-col for clustered heterogeneous)，先把整个网络分成两类节点，能量较高的节点称为高能量节点，能量低的称为正常节点。高能量节点则根据式(2)进行选择成为簇首节点的概率，而正常节点则根据式(3)选择成为簇首节点的概率。可以看出，高能量节点成为簇首节点的机会大于低能量节点。相较于LEACH算法，充分利用了整个网络的功耗。
为整个网络簇首节点的概率，Pnrm为正常节点成为簇首节点的概率，Padv为高能量节点成为簇首节点的概率。r为当前循环次数，G1是在前1／p轮中正常节点未充当过簇头节点的集合。G2是在前1／p轮中高能量节点未充当过簇头节点的集合。m为网络中高能量节点的比例。a为高能量节点高于正常节点能量部分。
在参考文献中，作者对SEp算法进行再次改进，利用整个网络节点的平均能量与节点当前能量的比值来限制节点成为簇首节点的概率，两类节点成为簇首节点概率如式(4)所示。
根据式(4)，可以看出进一步限制的低能量节点成为簇首节点的概率。
1．3 根据节点剩余能量的不同而改进
M．J．Handy等人提出了DCHS(Deterministic Clus-ter-Head Selection)算法，根据LEACH算法中的T(n)计算不足之处，对其进行改进，如式(5)所示。式(5)中En_current表示节点当前的能量，En_max表示节点初始的能量。
由改进后的算法可以看出，当前节点能量比较高的节点成为簇首节点的概率变大，从而降低了低能量节点成为簇首节点的概率，提高了整个网络的性能。然而根据式(5)可以看出，当整个网络运行到一定的时间后，大部分节点的能量都将剩余不多，相应的T(n)就会变小，那么整个网络中节点成为簇首的概率变小，从而影响到整个网络的性能。M．J．Handy等人对式(5)进一步改进，得到式(6)，从而有效解决了式(5)的不足之处。在式(6)中rs表示节点连续未当选过簇头的轮次。一旦节点当选为簇首节点，则rs置零。
1．4 根据簇首节点随机分布不均而改进
LEACH-C算法是LEACH算法的集中式控制版本，采用模拟退火算法获得更优的簇头选举策略，克服了LEACH算法中每轮产生的簇头数与位置的随机性。
LEACH-C算法可以把每个节点的地理位置以及节点当前的能量报告给基站。基站把所有节点的能量取平均，当网络中某些节点的能量低于平均值时，将不能成为候选簇头节点，从而更加有效地解决了低能量节点成为簇头节点的概率。