无线传感器网络中的LEACH算法分析与设计

摘要：在分析了经典的LEACH分簇路由算法，以及基于LEACH算法基础上的几种经典的改进算法后，针对小规模无线测距网络的特点，在传输数据量较少、簇首节点无需进行大量数据融合的情况下，对LEACH算法进行改进，增加了节点与基站直接通信的个数，减少了多跳累加误差对测距的影响。使用MATLAB软件进行仿真，理论与实验仿真表明，本文提出的改进算法能够延长整个网络的生存时间，减少了一些不必要的能量浪费。
关键词：无线传感器网络；分簇路由算法；LEACH；性能分析

引言
    无线传感器网络是当前网络技术界备受关注的前沿热点研究领域，涉及多学科，高度交叉，知识高度集成。无线传感器网络集成了传感器技术、计算机技术和通信技术，在军事、环境、健康、家庭、商业等许多方面有着巨大的潜在应用前景。无线传感器网络由大量密集分布的传感器节点通过自组织的方式形成网络，节点通过网络协议快速形成自主构建、自主组织和自主管理的通信网络。这种通过数千个微小的节点之间互相通信，通过接力的方法实现大范围监控的模式极大地提高了工作效率。然而节点大都需要在无人看管、不更换电池或者不可能更换电池的条件下长时间地工作，因此高效、低功耗路由算法在无线传感器网络中就显得非常重要。

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算法可以把每个节点的地理位置以及节点当前的能量报告给基站。基站把所有节点的能量取平均，当网络中某些节点的能量低于平均值时，将不能成为候选簇头节点，从而更加有效地解决了低能量节点成为簇头节点的概率。

1．5 根据LEACH实时性不强而改进
    根据LEACH算法实时性不强的问题，Manjeshwar A等人提出了TEEN算法，TEEN算法与LEACH算法较大的不同点是，在簇首节点的选举过程中，协议设置了两个阈值，分别为硬阈值、软阈值两个参数。硬阈值是被检测数据不能超过的数值，而且软阈值决定了被测数据的波动范围。只有当被监测数据超过硬阈值且被监测数据的变化幅度大于软阈值时，节点才会传送最新的监测数据，并设置为新的硬阈值。相对于LEACH算法，TEEN算法能够较大地减少节点之间数据传送的次数，从而有效减少了整个网络的功耗，延长了整个网络的寿命。APTEEN算法则结合了LEACH与TEEN两种算法，是一种主动型与响应型混合的数据传输模式。但网络中有突发事件时，数据传输模式将会采用与TEEN相同的模式(响应型模式)，只不过AFTEEN算法多了一个计数器，节点每传送一次数据，对应的计数器将清零。当计数器的时间到达的时候，将采取主动发送这个数据，不再判断软、硬门限值。
1．6 根据网络节点分布密度不均而改进
    在LEACH算法中并未考虑节点分布密度对网络的影响，在分布密度大的区域，相对簇首节点的负担也较重，能量也容易耗尽，因此应该增加该区域簇首节点的个数。参考文献中根据无线网络中周围节点存活个数不同，来改变该区域内节点成为簇首节点的概率。为了在节点密集区域增加簇头的个数，只需要增大对应节点成为簇头的概率，对于节点稀疏区域则降低其中节点成为簇头的概率即可。因此将簇头选举的阈值修改为：
   
    式(7)中Neighbor(n)_alive与Network_alive分别表示表示节点n邻居集中以及整个网络中存活节点的数目，1／p表示平均每簇中节点的个数，从式(7)可以看出当节点周围存活个数大于平均值时，该区域节点成为簇首节点的概率将增大，反之则降低。
1．7 根据大规模多跳网络而改进
    根据LEACH算法跳距的局限性，在LEACH算法中，整个网络最大跳距为两跳，这样就会导致远离基站的簇首节点，能量消耗太大而过早死亡，影响到整个网络的性能，Siva D．Muruganathan等人提出了BCDCP多跳分簇算法，簇首节点的选择由基站来控制，基站首先将每个节点的当前能量取平均，只有大于平均值的节点才有机会成为簇首节点，这样就避开了低能量节点成为簇首节点的可能。当簇首节点与基站的距离超过一定时，不直接与基站通信，而是借助其他簇首节点转发到基站，选择其他簇首节点是采用的是最小生成树算法，这样就减轻了远离基站簇首节点的负担，也扩展了整个网络的规模。
1．8 节点能量传输模型与最优簇首节点概率
    大部分作者都把节点传输模型采用公式(8)与(9)，式中k为传输信息的比特数，d为节点之间距离。εfs为自由空间传送方式下的功率放大参数。式(8)为节点接收数据所消耗的能量，式(9)是发送数据所消耗的能量，因本文针对的是小规模无线传感器网络，所以采用的是自由空间模型。
   
    因为不同规模的网络，节点密度的不同，最优簇首个数也不相同，采用参考文献提出的最优簇首个数公式(10)，采用的是自由空间模型。
   

2 分簇路由算法设计
2．1 算法设计
    本文主要针对一些特定的环境下，对经典的LEACH算法进行改进。目前关于无线传感器网络测距技术，普遍采用信号强度与信号差往返时间来测距两种方法。前者在理论上较难实现，一般很难在现实中使用。而后者理论简单，但由于硬件成本的限制，只能采用一般的时钟晶振，这时就对节点之间的时间同步提出了较高的要求。而目前传统的时间同步算法都会随着跳数的增加，误差越变越大，而在小规模测距定位系统中，节点之间无需传输大量的数据，因此簇首节点无需进行大量的数据融合，因此本文设计的初衷是减少传输跳数、延长整个网络生存时间。因此对传统的LEACH算法作以下改进。能量传输模型采用式(8)与式(9)，网络中最优簇首个数比例采用式(10)，规定阈值T(n)采用式(6)。

    条件1：如图1所示，当dBD>dAD或dAB>dAD，直接让簇内节点D把数据传输给基站，与簇内节点D先把数据传给簇首B，在转发给基站A的能量要少。

  
    显然可以看出当dBD>dAD时，ETxDB>ETxDA，接收能量是相同的。这样就很容易得到当dBD>dAD时，直接让簇内节点把数据传输给基站，与簇内节点先把数据传给簇首，在转发给基站的能量要少是成立的。同理当dAB>dAD时也是成立的。
    条件2：如图1所示，当时，则直接让簇内节点D把数据传输给基站，与簇内节点D先把数据传给簇首B，在转发给基站A的能量要少。

2．2 算法性能分析
    根据2．1小节所讨论的条件下对LEACH算法进行改进，在其他参数都相同的条件下，改进前与改进后死亡节点个数随选举轮数增加而变化情况如图2所示。从图2中可以看出，改进后的算法节点生存时间优于改进前的算法，尤其随着选举轮数增加，优势越来越明显。改进前第一个节点的死亡时间为1051轮，改进后第一个节点死亡时间为1062轮，改进前一半节点死亡时间为1273轮，改进后为1301轮。从2．1小节也可以知道，部分簇内节点可以直接与基站通信，从而减少了部分节点的传输跳数。