基于最优簇头数和三段路由的改进型LEACH算法

糜 昊

(山西师范大学 物理与信息工程学院，山西 临汾 041004)

0 引 言

许多廉价的微传感器节点被放置在指定的监控区域，通过无线通信以多跳的方式自发地形成无线传感器网络(WSN)[1]。作为一个新平台，WSN被广泛应用于数据传输、采集和处理[2]。能够实时监测和收集指定区域内被监测对象的各种数据信息，如温度、湿度、声音、压力、物体位置或化学浓度等，然后对收集的信息进行处理并传送至基站(BS)[3]。这可实现对传感器节点的实时检测、跟踪和遥控。由于硬件和物联网的发展[4]以及监测区域存在不确定性，WSN会应用于环境传感、军事监视、国土防御和其它特殊情况[5]。通常，由传感器节点配置的电池能量有限，不能充电或更换[6]，而能耗又决定了网络的寿命和价值。因此，在设计路由协议时，必须非常注意能耗问题。

LEACH(Low-Energy Adaptive Clustering Hierarchy)是一种流行的分簇路由协议，该协议周期性地执行集群的建立阶段和数据的传输阶段，并且一个循环可以用轮的概念来描述[7]。在集群的建立阶段，每个节点随机生成一个介于0～1之间的数字，如果生成的随机数小于阈值T(n)，其幸运地会成为簇头，并广播其为簇头的消息[8]。阈值T(n)定义，式(1)如下：

(1)

其中，p是成为簇头的预期概率；r是当前轮；r*mod(1/p)表示这轮中选为簇头的节点数；G是最近1/p轮中未选为簇头的节点集[9]。

在接收到消息后，其它节点选择加入离其最近的集群并成为集群内的成员。该协议随机选举簇头，并不断循环集群重建过程。同一轮中的传感器节点不允许重复被选举，并且所有节点成为簇头的可能性相同。在数据传输阶段，集群成员将收集到的数据传输到簇头，由其接收并融合数据，最后将其发送到基站[10]。LEACH协议的数据路由如图1所示。

图1 LEACH协议的数据路由

虽然LEACH协议非常流行并被广泛使用，但仍存在一些缺点：

(1)LEACH很难确定最优的p值[11]。当p太小时，传感器网络只能选举数目很少的簇头，增加了集群内的传输距离，从而增加集群内传输能耗；当p太大时，会产生多余的簇头，增加数据传输到基站的能耗。

(2)LEACH规定簇头以单跳模式与基站通信[12]。当传输距离超过一个阈值时，能量将由2次方衰减变为4次方衰减，能耗巨大，网络寿命急剧下降。

(3)LEACH忽略残余能量对簇头选举的影响，会出现残余能量低的节点选为簇头，不利于能量均衡消耗[12]。

本文主要针对以上3个缺陷对LEACH协议进行改进，提出基于最优簇头数和三段路由的改进型LEACH算法，将其命名为LEACH-N。该算法删除了LEACH协议中的p和簇头选举的阈值公式，避免了簇头的随机性。首先，依据网络区域的节点总数计算出理论上的最优簇头数，并按照残余能量由高到低进行选举，保证了每一轮的网络节点能耗的均衡性[13]，完全避免了残余能量低的节点被选举为簇头；其次，集群内传输后簇头残余能量最高的成为高层簇头，接收和融合其余普通簇头的数据包最后传至基站，形成节点—簇头—高层簇头—基站的三段数据路由，实现了用相对较低的能量传输整个网络的数据包。本算法应用在基站位于传感器区域中心或距离区域较近的网络时，可以最大限度的推迟首节点死亡时间，提高信息传输量；应用在基站距离传感器区域很远的网络时，可以大幅延长网络寿命、提高传输量。

下面这些词和固定短语的情况又有点儿不同,但也都属于借代造词。词本身都是借体,所包含的词义部分也都是被代替的本体。

1 LEACH-N算法

1.1 改进方案

首先，LEACH中簇头不仅接收和融合集群中所有节点传输的数据，还继续将数据包发送到远处的基站，因此比普通集群成员节点的能耗负担更大。此外，残余能量非常低的传感器节点也具有与其它节点相同的概率成为簇头，这可能直接加速其死亡。如果这种情况频繁发生，那么WSN中幸存的传感器节点的数量将会迅速减少，导致网络寿命缩短。同领域的其它学者也发现了这个问题并改进了阈值公式，例如Kim、Yong、Min等人在公式中引入节点的剩余能量来增加高能量节点选举的概率，但其不能完全避免残余能量低的节点成为簇头[12]。因此，LEACH-N首先取消了p值和阈值公式，依据网络区域中节点的数目计算出理论上最优的簇头数；在每一轮中，选择高残余能量的节点为簇头。网络区域中的簇头数量保持恒定，在一定程度上可以避免随机性造成的能量浪费。本算法中如果节点的残余能量相对较低，那么其必须作为集群的成员节点，所以其只需要消耗更低的能量完成集群内通信来确保其生存。这种基于最优簇头数的选举方式可以最大程度的均衡网络节点能耗，提高信息传输量。

其次，簇头传输数据包的能耗一定比接收和融合的能耗大。某些特殊情况下，基站与监测区域之间的距离远大于该区域的跨度，此时能量以4次方衰减。为了降低这部分的能耗，本文选举出高层簇头，形成节点—簇头—高层簇头—基站的三段数据路由，避免所有簇头和基站之间的直接通信，如图2所示。这种基于三段路由的传输可以适用于传感器网络距离节点区域遥远的情形，延长网络寿命。

图2 LEACH-N算法的数据路由

综合上述两点，本文提出基于最优簇头数和三段路由的改进型LEACH算法(LEACH-N)，在算法开始时，根据设定的参数值进行初始化。该算法预先计算理论上最优的簇头数量，然后是选举过程。幸存的节点根据从最高到最低的残余能量排序，序列号小于或等于理论上最优数目的节点将成为簇头。在其它节点加入集群后，根据分配的时间隙发送数据包，由簇头接收、融合，将剩余能量最高的选为高层簇头，完成到基站的数据传输。LEACH-N算法的程序流程图如图3所示。

图3 LEACH-N算法程序流程图

1.2 能耗模型

该算法采用了与LEACH协议相同的能耗模型，以更清晰地验证其性能。发射机发送l位数据所消耗的能量为式(2)：

(2)

接收机需要消耗能量来接收l位数据，能量计算为式(3)：

ERx=l×Eelec

(3)

表1 模拟参数

1.3 最优簇头数计算

LEACH-N中的簇头数是一个常量，但精确计算最优数并不容易，因为实际上传感器节点是被随机放置在监测区域内的。为了便于计算，希望节点在该区域内尽可能均匀地分布。使用N表示传感器节点的数量；C表示簇头的数量；S表示监测区域的面积。集群之间的距离小于d0，将自由空间模型用于集群内信息传输。

节点到簇头的传输过程的能耗分析：S/C是每个集群的平均面积，让S/C=πd12，其中d1是成员节点和簇头之间的平均距离。在此过程中，发送数据的平均能耗为式(4)：

Es=(N-C)×l×Eelec+(N-C)×l×εfs×d12

(4)

接收和融合数据的平均能耗为式(5)：

Er=(N-C)×l×(Eelec+EDA)

(5)

所以此过程的平均能耗为式(6)：

E1=(N-C)×l×(2Eelec+EDA)+(N-C)×

l×εfs×d12

(6)

E2=(C-1)×l×(2Eelec+EDA)+(C-1)×

l×εfs×d22

(7)

将以上两个过程的能耗相加得到一轮的总平均能耗为式(8)：

Etotal=(N-1)×l×(2Eelec+EDA)-l×εfs×

(8)

只有当N/C+C/1为最小值时，能量才可以最有效的被利用。根据二元基本不等式，当N/C=C/1时，达到最小值。最后计算得最优簇头数为式(9)：

(9)

这在理论上是一个最优值，而且WSN的状态越接近理想，其就越接近真实的最优值。此外，需要指出的是，该数学建模并没有考虑到高层簇头向基站发送信息的能耗，因为无论监测区域中的哪个节点成为高层簇头，与节点到基站之间的距离相比，节点之间的距离忽略不计以简便计算。

2 实验结果与分析

2.1 仿真环境

本文使用LEACH算法作为LEACH-N算法的比较，仿真工具为MATLAB。模拟系统的主要参数设置见表1。其他参数设置如下：传感器节点总数为100，分布在100×100 m的区域中，区域4个顶点坐标分别为(0,0)、(0,100)、(100,0)和(100,100)，阈值距离d0=87.7 m，LEACH算法中使用的p值为0.05。经计算该传感器网络区域的最优簇头数为10。

2.2 不同传输距离时的结果分析

2.2.1 传输距离d

传输距离为60 m时，两种算法存活节点数和数据包传输量随时间的变化如图4所示。可看出虽然此时LEACH-N算法在网络寿命方面不如LEACH，但是其使得首节点死亡时间落后于LEACH，提高了信息传输量。首节点死亡时间与所有节点残余能量有关，故随机选取了网络中的10个节点，将其在1 000轮时的残余能量记录在了表2中。从10组结果中可看出使用LEACH的传感器网络中节点之间残余能量相差较大，如4号和9号之间相差值达到了0.109 4 J，能量利用很不均衡。而使用LEACH-N算法的传感器网络中节点残余能量全部为0.274J左右，相差最大值仅仅为0.001 1 J，均衡性明显提高，所有节点几乎是同时死亡，这保证了网络在存活期间始终以恒定的信息传输速率工作，故信息传输量可达最大。

图4 距离60 m时网络寿命和数据包传输量的对比

表2 1 000轮时节点残余能量

2.2.2 传输距离d>d0

能耗随着距离增加呈4次方衰减，实验分别测试了当距离为100，150，200，250和300 m时的网络寿命和信息传输量，结果见表3、表4。可以看出，随着距离逐渐增加，LEACH-N的提高率越来越大。相比LEACH协议，当基站距离最近的传感器节点300 m时，网络寿命延长了285.1%，信息传输量提高了336.5%，优势明显。距离300 m时两种算法存活节点数和数据包传输量随时间的变化如图5所示。

表3 不同传输距离时的网络寿命提高率

表4 不同传输距离时的数据包传输量提高率

图5 距离300 m时网络寿命和数据包传输量的对比

3 结束语

本文提出了一种基于最优簇头数和三段路由的改进型LEACH算法。当传输距离小于阈值时，虽然使用LEACH-N算法的网络寿命延长效果不如LEACH协议，但是选举最优数目的簇头可以使网络节点消耗能量的均衡性最强，推迟首节点死亡时间，信息传输量得到提高。当传输距离大于阈值时，高层簇头形成的三段路由的作用开始体现，LEACH-N算法的提高效果会随着传输距离的增加而愈来愈好，传感器网络寿命明显被延长，信息传输量也被最大化。本算法对于不同的传输距离均有其优势，可应用于基站处于不同位置时的WSN。但是三段路由会增加网络的通信延迟，故论文的未来工作将集中于寻找网络寿命和通信延迟之间的平衡点，提升WSN的综合性能。