基于簇头阈值优化的LEACH的分簇路由

刘 卫，李跃飞, 谢英辉

(1. 长沙民政职业技术学院，湖南 长沙 410004;2. 湖南信息学院，湖南 长沙 410104)

0 引 言

随着现代电子技术的发展，无线传感网络广泛应用于各类应用，如康复医疗、战场、野外环境监测等[1-3]。这些传感节点先感测环境数据，然后经处理后，再传输至基站。由于无线传感网络常部署于野外恶劣环境，更换节点电池是不现实的。因此，能量消耗成为无线传感网络的研究热点[4]。

为了节省传感节点能量，一般不允许传感节点与基站直接通信。因此，为了存储节点能量，将邻近节点或具有相同特性的节点汇聚成一个簇[5-6]。每个簇内选择一个节点作为簇头，并由簇头收集簇内节点的感测数据，经融合后，再传输至基站。通过簇结构，有利于降低能量消耗。

目前，研究人员提出不同的簇算法，如基于层次、基于区域以及基于节点度分簇算法，其中基于节点度分簇算法得到广泛关注，也是本文关注的焦点。基于节点度的分簇算法是利用节点度决策簇头。所谓节点度就是指节点的一跳邻居节点数。尽管节点度反映了节点密度信息，但是未能全面地反映邻居节点的分布情况。

为此，以低功耗自适应簇分层 (Low Energy Adaptive Clustering Hierarchy，LEACH)[7]协议为基础，提出基于节点分布密度的LEACH的修正协议，记为LEACH-C。LEACH-C协议充分考虑了节点分布密度。其原因在于：分布密度越高，意味着在一小面积区域内节点数越多，即邻居节点间相距更近。那么位于密集区域中心的节点就只需消耗较少的能量就连接到其他节点。因此，分布密度高的节点优先成为簇头。反之，分布密度越低，意味着在区域内其邻居节点数少，且分布广。这类节点需要消耗更的能量才能与邻居节点通信。

为了更好地描述节点分布密度，LEACH-C协议首先定义内部节点和边界节点，并通过内部节点数计算节点分布密度。然后，依据节点分布密度因子和剩余能量因子对LEACH协议中的阈值进行修正。同时，依据节点分布密度调整节点传输距离，进而降低节点能量消耗。最后，仿真实验数据表明，修正后的LEACH-C协议能够有效地保存能量，提高网络寿命。

1 LEACH概述及约束条件

1.1 LEACH协议及其不足

作为经典分簇算法，低功耗自适应分层LEACH协议受到广泛的关注。LEACH协议由初始阶段和稳定传输两个阶段组成。同时，LEACH协议将时间划分不同的轮。每一轮执行一次簇头选择算法。在每轮内，每个传感节点竞争成为簇头或加入邻近的簇。

在竞争簇头时，每个传感节点先产生一个随机数Nr，再与阈值Th进行比较。若小于阈值，就成为簇头。节点si的阈值定义如式(1)所示。

(1)

其中p表示网内簇头数的比例，即簇头数占总的节点数的百分比。而r表示当前轮数。G为节点集，由在r-1轮内未成为簇头的节点组成。

依式(1)可知，阈值随轮数r的增加而上升。换而言之，后期节点比前期节点成为簇头的概率要大。一旦成为簇头，节点就向邻居节点广播消息包，该消息包有两个目的：一是告知邻近节点，该节点已成为簇头；二是让非簇头节点接收该消息包，使得这些接收节点能够估算与该簇头的距离，进而决策是否加入该簇。

一旦形成簇后，簇头给簇成员节点分配时隙。簇成员节点在各自时隙内传输数据，而其他时隙保持睡眠状态，进而减少能量消耗。

尽管LEACH协议相比其他算法存在一定的优势，但是它仍存在一些不足。首先，LEACH协议在选择簇头是以单个节点的特性为依据，而并没有考虑到周围环境特性，如节点密度。其次，在选择簇头时，没有考虑到距离信息。离簇头或基站近的节点的能量消耗速度更快。因此，若不考虑到距离信息，容易导致覆盖空洞。

为此，本文以LEACH协议为基础，对其簇头选择策略进行改进，即对阈值进行修改，同时采用自适应调整传输距离策略。

1.2 约束条件

提出的LEACH-C协议基于以下约束条件:

(1)节点随机分布于网络；

(2)所有节点的初始能量相同，并且有限；

(3)网络属静态的。即节点一旦部署后，就不再移动；

(4)节点能够依据接收信号强度，估算自己的位置；

(5)节点能够估算自己的剩余能量。

1.3 能量模型

无线电能量消耗主要有两部分组成：运行电子元器件、功率放大器所消耗的能量和接收器所消耗的能量[8]。如图1所示，在相距为d的两节点间传输q比特的数据信息，消耗的能量：

(2)

其中，Eelec运行发射器或接收器固定的能量消耗，Efrris、Etworay分别表示发射器在自空间、双径传播模型(two ray ground model)的单位功率放大器的能量消耗[9]。而dco的定义如式(3)所示：

(3)

其中，λ为波长、l为系统损耗。ht、hr分别表示发射天线和接收天线的增益系数。相应地，对于接收q比特的数据包所消耗的能量：

ERX(q)=q*Eelec

(4)

图1 无线电能量消耗模型

2 LEACH-C协议

与LEACH协议不同，LEACH-C协议在选择簇头充分考虑了能量、距离以及节点分布密度。同时，依据节点分布密度自适应调整传输距离。

2.1 内部节点和边界节点

首先定义两类节点：内部节点和边界节点。假定网络节点集为S,其内有N个传感节点，即si∈S,且i=1,2,…,N。节点si的一跳邻居节点集表示为Nei。

内部节点：如果节点sk∈S被邻居节点包围，则节点sk称为内部节点。具体而言，如果在节点sk一跳邻居集Nek内有三个节点，并且这三个节点分别与节点sk所形成的三个夹角之和等于360°，则该节点称为内部节点。

图2 内部节点和边界节点的定义示意图

如图2(a)所示，节点sk的一跳邻居集内有三个节点sa、sb和sc。它们分别与sk连线所形成的三个角度之和等于360°，如式(5)所示，则节点sk称为内部节点。

∠α+∠β+∠λ=360°

(5)

利用三角函数知识，并结合各连线的长度，可计算式(5)：

(6)

其中x、y、z、a、b和c分别表示各连线的长度。

边界节点：如果节点sj∈S不是内部节点，则该节点就称为边界节点。

如图2(b)所示，节点sj不满足内部节点的定义。在其一跳邻居节点内，不存在三个节点与它形成的三个夹角之和等于360°。

2.2 节点分布密度

每个节点判断自己是否为内部节点或边界节点。引入变量flag，若是内部节点，则flag=1，否则为0。然后节点将自己的flag值将载入HELLO消息包，并向邻居节点传输。

邻居节点通过交互HELLO消息包，便可估算一跳邻居节点中有多少节点是内部节点。节点si的一跳邻居节点集为Nei，集内节点数为|Nei|。若Nei内有Mi个内部节点，则节点si的分布密度ρi：

(7)

从式(7)可知，ρi值越大，表明节点分布越密集，反之，节点分布越稀疏。

2.3 自适应传输距离策略

传统的LEACH协议采用固定传输距离，不论节点周期环境是密集或稀疏[10]，这不但浪费了节点能量，也可能形成了不必要的干扰。为此，LEACH-C协议自适应调整传输距离。依据节点分布密度情况，提升或缩短传输距离。

从式(7)可知，节点的分布密度反映了邻居节点类型，即是内部节点多还是边界节点多。这也体现了邻居节点的分布情况，是分布紧密还是松散的。节点的分布密度越高，意味着节点所处的区域越密集。反之，节点所处的区域越稀疏。

如图3所示，三角形状的点表示边界节点，而圆节点表示内部节点。区域1的边界节点形成了一个覆盖空洞，而区域2的内部节点表征了一个密集区 域。而区域3表征了一个低密度区域，其周围有多个边界节点。

图3 内部节点或边界节点对区域覆盖的影响

由图3可知，分布密度越大，节点聚集越多，可缩短传输距离，反之，可提升传输距离。因此，将节点分布密度ρi分为三类。假定R是节点最大的传输距离。如果ρi∈(0.85,1]，节点的传输距离为R/4；若ρi∈(0.5,0.85]，节点的传输距离为R/2；若ρi∈(0,0.5]，节点的传输距离为R。传输距离调整策略的伪代码如图4所示。

图4 传输距离调整过程伪代码

2.4 阈值修改

LEACH协议的阈值设置并没有顾及到节点密度以及节点能量信息。为此，LEACH-C协议对此阈值修改。将节点的分布密度和剩余能量信息融入阈值，其中节点si的剩余能量百分比Ei:

(8)

其中Eint、Ecur分别表示节点si的初始能量、当前剩余能量。

考虑到节点分布密度和剩余能量百分比对阈值影响的不同，给这两个因子设置不同的比重。将这两因子融合成一个变量ψi：

(9)

最后，对LEACH协议的阈值(式(1))进行修改，如式(10)所示：

(10)

3 性能仿真

3.1 仿真参数及性能指标

本节评估LEACH-C协议的性能，利用MATLAB建立仿真平台，并与LEACH、DT-LEACH[11]和DEGRA[12]进行比较。选择这三个协议作为参考原因在于：LEACH是经典的簇协议，并且本文所提出的协议是基于LEACH的改进协议。

而DT-LEACH和DEGRA协议均是基于节点密度集协议，与LEACH-C协议具有可比性。DT-LEACH协议与LEACH协议簇头选择策略相同，不同之处在于：DT-LEACH协议依据节点密度决策节点是否有资格加入簇。若节点密度小于预定的节点密度值D，就可以入该簇，否则不能加入。而DEGRA协议引用了博弈理论，利用博弈理论解决簇头选择问题。

100个节点随机分布于200 m×200 m监测区域内。基站位于监测区域中心。节点的初始能量为1 J，节点传输距离最R=40 m，其他仿真参数如表1所示(注：“*”表示相乘)。

表1 仿真参数

3.2 数值分析

从每轮的能量消耗、传输的消息数和网络寿命三方面分析LEACH-C协议，其中，传输的消息数表示在网络内有一半节点失效 (Half Node Die, HND)时，基站所接收到消息数。而网络寿命表示从两个方面进行分析：在第一个节点失效 (First Node Die, FND)前，所执行的轮数，以及一半节点失效HND前，所执行的轮数。每次实验独立重要10次，并记录10次的实验数据。

(1)每轮的能量消耗

平均每轮所消耗的能量数据如表2所示。从表2可知，LEACH协议所消耗的能量最多，而LEACH-C协议所消耗的能量最少。LEACH-C协议比LEACH的能量消耗降低50.7%。这主要因为：LEACH协议仅采用简单的阈值决策簇头，具有随机性，没有考虑到簇头节点本身的特性，如剩余能量，这使得簇头容易因能量耗尽而失效。一旦簇头失效，会导致数据传输中断，加大了能量消耗。

表2 平均每轮所消耗的能量

而LEACH-C协议在选择簇头，充分考虑了节点能量信息，以及节点分布密度，并自适应调整传输距离，这些策略均有利于存储节点能量。此外，DT-LEACH协议和DEGRA协议的能量消耗低于LEACH协议。原因在于：DT-LEACH和DEGRA协议与LEACH协议相比，它们在选择簇头时融合了更多节点信息，使得簇结构更为稳定。因此，DT-LEACH和DEGRA协议的能耗低于LEACH协议。

(2)传输的消息数

本次实验分析LEACH-C协议的在HND前，基站所接收的消息数，这个指标反映了协议的数据传输性能。数据如表3所示。

表3 基站在HND前所接收的消息数

从表3可知，提出的LEACH-C协议所接收的消息数最多，比传统的LEACH协议提高了约42.4%。而DT-LEACH和DEGRA协议中基站所接收的消息数也优于LEACH协议。传统的LEACH协议并没有优化簇头选择过程，只是简单地利用预设的阈值定义节点成为簇头的概率，没有考虑到节点的个体特性。而尽管DT-LEACH协议的簇头选择策略与LEACH协议相同，但是它优化簇形成过程，非簇头节点加入簇，并不是像LEACH协议那样采取简单的就近原则，而是依据节点密度进行决策。所以，其性能优于LEACH协议。

(3) 网络寿命

最后，分析了各协议的网络寿命，并分别利用在FND和HND时所执行的轮数表征，数据结果如表4所示。

从表4可知，在提出的LEACH-C协议能够有效地提高网络寿命。在FND时，LEACH-C协议比LEACH、DT-LEACH和DEGRA协议的网络寿命分别提高了71.87%、31.91%、16.07%。类似在，在HND时，LEACH-C协议比LEACH、DT-LEACH和DEGRA协议分别提高了14.30%、31.78%、16.74%。这些数据表明改进后LEACH-C协议能够保存节点能量，进而扩延网络寿命。

表4 网络寿命

4 总 结

针对无线传感网络的簇算法，首先分析了经典的LEACH协议的不足，然后提出LEACH的修正协议。依据节点分布密度和剩余能量对阈值进行修正，提高了簇头性能，缓解了簇头能耗速度。同时，对节点的传输距离进行自适应地调整。在稀疏区域，提高传输距离，而在密集区域，降低传输距离。仿真结果表明，修正后的LEACH-C协议有效地保存了节点能量，提升了网络寿命。