LEACH分簇层次路由算法的研究与改进

王 创

(安徽理工大学 电气与信息工程学院，安徽 淮南 232000)

传感器节点是物联网的感知层面，节点一般采用电池进行供电，节点的使用时长直接关乎着网络的生命周期[1]。网络路由算法可以分为平面路由算法和分簇层次路由算法，LEACH(Low Energy Adaptive Clustering Hierachy)算法[2]是分簇层次路由算法的典型代表，进行数据通信时首先通过簇内节点搜集信息来发送给簇头，簇头同时承担着数据融合和信息传输的任务，能量消耗巨大[3]。目前，国内许多学者对LEACH算法进行了改进。刘洲洲等[4]在传统LEACH算法的基础之上引入粒子群算法，对惯性权重因数进行优化，使簇内分布更加合理。陈立万等[5]通过改进经典遗传算法引进轮盘赌思想和LEACH算法进行融合，从而使算法不易陷入局部最优。王旭等[6]对LEACH算法的阈值函数进行修正，并且通过布谷鸟搜索算法引入距离因子、密度因子和距离因子，采用多跳方式和sink节点进行通信。

1 相关理论概述

1.1 WSN路由算法

路由算法是整个无线传感器网络技术的核心和基础，通过不同指令将终端节点采集到的数据传递到基站。因此，如何节省数据传输时消耗的能量，延长网络的生命周期成为了重要问题之一。在无线传感器网络当中，用于延长网络生命周期的路由协议主要包括LEACH、DEEC、TEEN、PEGASIS等。LEACH算法是一种WSN低功耗自适应聚类路由通信方法，是最早出现的WSN分簇层次路由协议。进行数据通信时首先通过簇内节点搜集信息来发送给簇头，簇头同时承担着数据融合和信息传输的任务。但节点根据生成随机数字与阈值进行判断是否当选簇头，所以无法保证簇头的分布以及选择的合理性。PEGASIS算法每轮只有一个簇头和基站进行通信，TEEN算法提出的是双门限值来降低数据传输量，两种算法都不太实用。

1.2 网络模型

网络模型是由N个随机分布的传感器节点所构成的网络，应用场景往往是周期性的数据收集。假设有N个传感器节点随机分布在边长为M的正方形区域内，并且具有以下几点性质：① 传感器网络当中的节点部署后就不能随意移动，因为整个网络是静态网络模型；② 基站处于正方形区域当中一个固定位置，并且基站仅有一个；③ 在这个区域当中所有节点地位平等，拥有相同的初始能量、通信能力以及数据处理能力，被选中簇头节点和普通节点的几率是一样的；④ 节点无法获得位置信息，节点要想获取位置必须和GPS、定位算法或者有向天线等设备，这样做必然会大幅度增加成本和能耗；⑤ 无线发射功率可以根据距离远近进行相应的调整。

1.3 能耗模型

本文采用的无线传输节点模型如图1所示。本模型主要将节点能耗分为3个部分：发送数据能耗、接收数据能耗和数据融合能耗。发送端和接收端的距离d决定了无线信号的能量衰减。由节点发送比特的能量发送到距离为d的区域上，消耗能量由发射电路损耗以及功率放大损耗两部分构成，各个节点之间发送消息以及接收消息的能耗

(1)

式中：Eelec表示发射电路消耗的能量，也就是传输1比特信息电路所消耗的能量。总消耗的能量取决于传输距离和阈值之间的关系，传输距离小于阈值d0时，使用自由空间模型(Friss)；当传输距离大于阈值d0时，使用多径衰减模型。其中εfx、εmp分别是自由空间模型以及多径衰减模型功率放大所消耗的能量。

图1 无线能耗模型

2 LEACH算法的研究

2.1 LEACH算法运作过程

LEACH算法首先提出了“轮”的概念，每个节点根据网络簇头的百分比和节点已经成为簇头的次数来确定是否当选为簇头。其中每个节点随机产生从0到1的随机数字，并根据阈值公式来判断是否当选为簇头(如小于阈值，则当选为簇头)，成簇方式为簇头选择最近的簇头加入。阈值公式为

(2)

式中：p为预期的簇头百分比；r为当前轮数；G为最近1/p轮内没有当选簇头节点的集合[7]。

通过选出簇头节点来进行数据融合可以有效降低网络冗余、延长网络周期。LEACH算法开创了分簇层次路由算法的先河。但是，LEACH算法选择簇头的方式是随机的，能量较低的节点也有几率当选簇头，一旦簇头过早死亡，将会缩短网络的生命周期。成簇方式考虑片面，没有顾忌全局。

2.2 LEACH算法的优缺点分析

在LEACH算法当中，为了将簇头和普通节点之间加以区分，进一步组建高级网络，簇内成员之间仅仅依靠数据采集就可以实现短距离的数据传输，可以有效节省维护路由信息的数量。正是由于对簇头的选取机制发生转变，导致各个节点担任簇头的几率大致相同，因此在进行任务平均分配的前提之下有效均衡了节点损耗，各个节点之间的剩余能量差异很小，从而有效规避了节点过早死亡的问题。同时簇头还对接收到的信息进行数据融合，从而进一步减少节点能耗，大大增强了节点能量的利用程度，有效避免通信路径的通信堵塞。此外LEACH算法本身具备更好的拓展性，即使算法本身在进行节点均衡、延长节点使用时间、提升能源利用效率上进行了完善，但是本身依然存在很大程度的不足。

首先就是在节点进行初始化的过程，在进行簇头选择时要考虑到节点是否担任过簇头，因为没有关注到那些工作节点的剩余能量，这样能量较低的节点很大程度上就会当选簇头，从而进一步降低了节点能量的使用效率。随着节点不断死亡，簇头数每轮出现一定的偏差，大大增大了现有的簇头工作效率，导致一部分簇头提早死亡。同时分布式无法保证节点均匀分布在网络的各个区域，这就极大可能导致簇头没有进行集中分布，导致各个簇头之间的检测区域不一致，从而导致部分节点能量过早耗尽死亡。分簇能耗对于整个网络来说将是一个完整的开销，因此会导致网络节点的使用效率降低。同时由于簇内成员和汇聚节点之间采用单跳通信方式，因此距离必须远远小于通信半径，这就导致算法无法大规模应用于无线传感器网络当中。同时在稳定传输节点，单跳通信无法消耗大量能量，簇头容易过早死亡。

3 改进算法概述

3.1 能量消耗

节点能耗主要来自无线通信模块收发数据和空闲监听时产生的能耗。节点发送数据的能耗PS(k)表示为

PS(k)=Eeleck+Eampdγk

(3)

节点接收数据产生的能耗PR(k)为

PR(k)=Eeleck

(4)

节点分析和处理数据产生的能耗Pepu(k)为

Pepu(k)=Eepuk

(5)

其中：k为数据包的大小；Eelec为射频电路的能耗系数；Eamp为电路放大器能耗系数；d为发送距离；γ为信号衰减指数，取值一般为2或4[8-9]。

3.2 二次竞争法选举簇头

首轮竞争中，普通节点产生零到一的随机数a，与阈值进行比较，选出候选簇头节点。第二轮竞争中候选簇头节点建立自己的邻居簇头节点集合Ich，通过权值Wi集合内的其余候选簇头进行再次竞争得到最优簇头节点。

针对LEACH算法的簇头选举方式的不合理，通过综合考量节点和基站之间的距离与节点自身能量，引入距离因子和能量因子的概念。通信距离会对无限传感通信产生的能耗造成巨大影响，根据数据传输和数据接收之间的关系，可以得到

Pr=(Pt/r)n

(6)

其中：r节点间的距离;n是传播因子;Pr是接收功率;Pt是发送功率。进行簇头选举前，由基站发送广播，计算节点i自身与基站之间的距离dBi，同时将自身的能量信息反馈给基站，因此可以得到在节点i竞选簇头的距离因子

Di=(dBi-dm)/(dm-dn)

(7)

其中:Di是距离因子；dBi是节点i和基站的距离；dm是节点与基站之间的最远距离；dn是节点基站之间的最近距离。

传统的LEACH协议在选举簇头的过程中对节点能量考虑不合理，使得能量较低的节点也有几率当选为簇头，这将会对网络的生命周期造成影响，因此引入能量因子的概念

(8)

其中：Ere为节点的剩余能量因子；Ec为当前节点能量；Et为节点的初始能量。

改进后的阈值公式为

(9)

这里的λ1和λ2均为常数，并且相加为1，在进行第一轮竞争时，节点选取一个零到一的随机数a，只有小于A(n)时才可以当选簇头，否则进入休眠一直到竞争结束。公式限制了成为簇头的条件，只有那些没有当选过簇头的、能量消耗低的、距离基站距离短的才有可能当选为本轮的候选簇头节点。

第一次竞争选择出候选簇头之后，建立每个候选簇头节点的邻居簇头集合，再依照相对能量和节点密度来对簇头竞争的权值进行确定，进而经二次竞争之后最终对簇头节点进行确定，确定了每个候选簇头节点的邻簇头节点集合。Ich={Ii/Ij是候选簇头且d(Ii,Ij)

(10)

这里的ρ为密度因子，ich为候选簇头的邻居节点数，ist完全按照均匀散布的簇中节点的邻居节点数目，因此候选簇头的竞争权值为

wi=αEre+βp

(11)

其中：α、β为权值因子，并且之和为1，由此可以根据公式来对每个簇头的竞争权值进行计算。

在进行候选簇头的二次竞争中，每个候选簇头都根据消息来搭建相邻簇头集合Ich，并且根据权值的大小来选举最终的簇头节点，并且如果簇头权值相等的话，则选择id小的当选簇头。在确定了簇头之后，周围普通节点选择距离自己最近的簇头加入，紧接着对簇内的通信进行优化：设C为簇头节点，A为普通节点，当节点C与节点A之间的距离小于节点A到sink节点之间的距离时，那么节点A采集数据后先经过节点C，先发送到节点C进行数据融合后再发送到sink节点。当节点C到节点A的距离大于节点A到sink节点之间的距离时，无需进行数据融合，节点A采集的数据直接发送到sink节点。

4 仿真分析

4.1 主要参数

采用MATLAB2012b对传统LEACH算法和改进算法进行对比仿真。无线传感器网络设定为圆形区域，圆的半径为100 m。同时，在圆的内部随机生成100个节点，这些节点在区域当中均匀分布，汇聚节点位于圆心。具体参数如表1所示。

表1 参数设置

4.2 仿真结果

仿真结果如图2-图4所示。由图2可以看出，传统算法和改进算法的第一个死亡节点大概都出现在第100周期，但是传统算法在第400周期节点就全部死亡，而改进算法可以将节点生命周期延长到第800周期。实验证明改进算法明显延长了节点的生命周期，使得改进后的算法延长了整个网络的生命周期。由图3可以看出，两种算法消耗的整体能量大致相等。但是随着时间的推移，两种算法的总能量消耗都在极具增长，但是改进后的算法增长速度较慢，随着轮数的不断增加，改进算法的优势将会更加的突出。由图4可以看出，在相同的轮数情况下，改进算法的数据吞吐量将会大大的高于传统算法。因此可知改进算法的数据传输能力将会远高于传统算法。

图2 两种算法节点存活时间对比

图3 两种算法网络能量消耗对比

图4 两种算法数据传输对比

5 结 论

针对无线传感器的能量高度受限问题，同时对传统LEACH算法簇头选举方式进行了改进和优化。以此提出了基于二次竞争竞选簇头的方法，紧接着对簇内通信方式进行了优化得到了改进LEACH算法，使用该通信方法可以大幅度降低网络能量损耗，延长网络的生命周期。