无线传感器网络LEACH算法的改进

李 登，徐东明

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

0 引 言

无线传感器网络(wireless sensor networks，WSN)由小型传感器组成[1]。由于传感器内置电池不易更换的缺点，节点的能效对于WSN尤为重要。分簇算法常被用来优化WSN的网络能耗，聚类是分簇算法中常见的一种方法[2]，低功耗自适应集分簇算法(low energy adaptive clustering hierarchy，LEACH)[3]被认为是现有突出的分簇路由算法之一，但它随机分簇和簇头能耗不均匀的缺点，会使簇头节点能量耗尽的时间缩短而影响WSN的性能。文献[4]的改进算法加入距离因子，剩余能量因子来选择簇头节点；文献[5]提出基于集中节能距离(CEED)算法，在头节点选取时加入能量的考量，但是该算法降低了节点成为簇头的概率。文献[6]提出基于能量和密度的低功耗自适应集簇(LEACH-ED)分层协议，利用加权思想使节点产生了基于能量和密度的权值，但是该算法未考虑节点之间的距离及节点可重复利用的情况。

本文基于LEACH分簇算法，对文献[6]算法进行了改进。改进的算法除了考虑每轮运行中网络的平均能量，还加入节点到基站的距离、网络运行的有效轮次及每轮运行结束后节点的能量剩余等情况。此外每个分组中的节点数不能太多更不能太少，所以节点选择加入某个分簇时，还需计算头节点的半径范围。改进的方法充分考虑已当过簇头的节点可以重复被选为头节点的情况，最大化提高网络中节点的利用率。

1 无线传感器网络和能量模型

1.1 无线传感器网络模型

无线传感器网络的组成如图1所示。数据从节点发送到基站(base station，BS)可以是单跳或者多跳，节点多部署在偏远地区。由于传感器节点电池不易更换的特点导致它容易出现能量耗尽的问题。因此，如何尽可能使节点的能耗均匀化作为整个网络生存时间的有利条件。

WSN网络模型[7]假设如下：

(1)WSN由n个传感器节点和一个基站(BS)组成。节点均匀分布在区域A=M×M[m2] 空间上；

(2)每个节点的有效感知范围、存储的容量、通信的范围相同；

(3)基站位于传感区域外，具有无限的资源(即功率和存储容量)；

(4)每个节点始终都有要在其各自指定的时间内发送的信息；

(5)传感器节点和基站都是静止的；

(6)传感器节点配备GPS设备，因此可识别位置。

图1 无线传感器网络结构

1.2 无线传感器网络能量模型

采用文献[8]中使用的能量模型如图2所示。

图2 无线电能量模型

发送端发送Lbit数据的耗能如式(1)所示

(1)

节点接收Lbit消息的能耗如式(2)所示

Er=L*Eelec

(2)

分组中头节点处理成员节点数据消息的能量消耗如式(3)所示

Ea=L*Eda

(3)

式中：Eda为单位数据消息聚合的耗能大小。

2 LEACH算法的改进

2.1 LEACH算法

LEACH算法的具体操作过程是以“轮”的方式进行，每轮的运行由如下阶段组成：网络的初始化阶段和分簇内节点数据的稳定传输阶段。第一阶段通过让各个节点在 [0 1] 之间选择随机数来判断该节点能否成为该轮传输的簇头节点，如果该随机数与已经确定的T(n) 相比较小于该阈值，那么这个节点就可以被选取成为簇头节点，此时新的簇头节点就会广播给其它节点以告知其成为头节点，网络中其它节点会依据头节点传来的消息情况来决定要加入某个分簇中。一旦分簇完成，系统就会开始节点数据的传输阶段，在此阶段普通节点使用时分多址(time division multiple access，TDMA)协议进行数据的传输，簇头节点会把来自其它节点的消息进行处理后发送给BS。每一轮重复该过程。其中在簇头形成阶段，网络的阈值T(n)[9]的表达式如式(4)所示

(4)

式中：p为网络所需CH的比例大小，r为网络现阶运行的轮次。

2.2 改进的LEACH算法

针对LEACH算法、文献[6]中基于LEACH算法优化算法的不足，本文在LEACH算法的基础上，对文献[6]的算法进行了改进，改进后的算法同LEACH算法一样分为两个阶段。改进后算法的流程如图3所示。

图3 改进算法的流程

在簇的形成阶段，首先考虑到整个系统中节点的平均能量，平均能量[10]的计算公式如式(5)所示

(5)

式中：Eto表示的是网络总的能量。

在簇头节点的选择上，改进算法优化了簇头节点的选取方法，在簇头节点的选取函数中加入了每轮运行中各个节点的能量剩余情况，改进的公式如式(6)所示

(6)

式中：nalive是网络系统运行中节点的存活数量，Ere是网络运行中各个节点的能量剩余大小，Ebe是网络中各个节点最初的原始能量。

文献[6]中算法利用加权思想，使节点产生了基于节点能量和密度的权值来优化簇头节点的选取，权值公式如式(7)所示

(7)

式中：Eres是网络中节点的剩余能量大小，E0是节点的初始能量，nneb是节点的邻居节点数，Ncul是该簇头节点的簇内成员数量，γ1和γ2是权值影响因子。

根据上面的权值公式得到改进之后的阈值公式如式(8)所示

(8)

针对文献[6]中算法引入的加权值未考虑节点距离的情况进行优化。当一个节点被选取成为簇头节点之后，如果此时该簇头节点的能量剩余仍大于当前网络系统中的平均能量剩余值，那么该簇头节点可再一次被选择成为头节点。此时需要考虑到节点每轮运行结束后的能量剩余情况、网络运行轮次以及节点到基站的距离因素，得到改进之后的阈值公式如式(9)所示

(9)

式中：Er-re(i) 是每轮运行结束后总的剩余能量，rre为网络运行中剩余的轮数，其中rre=r-rnow，rnow是当前运行的轮次数，dmax、dmin、dto-BS分别为各个节点到汇聚节点的最大、最小距离值、当前轮中节点到汇聚节点的大小，可以看出剩余能量越多，到汇聚节点的距离越近，被选取成为簇头节点的可能性就越大。

簇头节点为集群中各个普通节点分配信息传输的 TDMA 时隙，这样就能确保各节点在进行数据传输时不会发生冲突，此外还允许每个非簇头节点在其TDMA时隙未到达期间保持休眠状态，不发送任何数据直至其TDMA时隙的到来，从而减少各个节点能量的消耗。此刻网络的分簇阶段完成并且开始进行数据传输阶段。

在传输数据阶段，簇头节点的能量损失主要有：接收其分组中各个成员节点数据消息的能耗、对各成员节点的数据消息及自身数据进行融合处理的能耗,以及向汇聚节点发送消息的能耗，具体如式(10)所示

(10)

各个簇中普通节点的能量损失如式(11)所示

(11)

则网络的总能耗情况如式(12)所示

(12)

(13)

当簇头节点选取完成后，其它成员节点与簇头节点进行数据传输需要在簇头节点的有效范围内，每个分簇所占面积如式(14)所示

(14)

普通节点在该区域内传输数据给簇头节点，不会产生簇中节点分布极度不均匀的情况，普通节点入簇的有效半径如式(15)所示

(15)

3 仿真结果分析

3.1 参数设置

为了评估优化后算法的优势，利用MATLAB平台检验其有效性。在实验环境中我们将100个节点随机分布在范围为(0，0)和(100,100)内，一个汇聚节点的分布位置为(xm,ym)=(50,50)。 我们将最佳簇头百分比定义为0.05 (p=0.05)， 具体的通信能量参数配置见表1。

表1 仿真参数设置

3.2 结果分析

本文主要考虑了各个分簇算法的网络生命持续时间、节点的数据传输情况、网络中节点的能量剩余情况几个方面，将改进的算法与LEACH算法、文献[6]的算法进行对比。3种算法节点死亡数量随轮次增加的变化情况见表2，算法的生命持续时间对比如图4所示。

表2 死亡节点个数及对应的轮次

图4 3种算法的生命周期情况

图4显示了节点剩余数量随时间增大的变化状态。结合表2可以看出，改进后的算法的生命周期较LEACH算法提高了36.4%，较文献[6]的算法提高了15.8%。LEACH算法的网络生存时间较短是因为簇头随机选择的原因，LEACH算法判定节点在下一轮中是否能选取成为簇头节点仅仅依据该节点在前面轮次中是否已经当选过簇头节点，若当选过，则下一轮中不会再成为簇头节点。文献[6]算法虽然引入了能量密度加权因子，但是没有考虑到节点距离基站的远近、网络运行的轮次及节点可重复当选为簇头节点的情况。而改进后的算法不仅考虑到节点的剩余能量，还加入节点到基站距离的考量，以及节点传输数据的有效范围等因素，有效改善了节点分布不合理的问题。经过对比，改进后的算法优化了簇头节点的选取，增加了网络生存时间长度。

3种算法节点数据消息发送到汇聚节点的情况如图5所示。

图5 3种算法的传输数据情况

图5是3种算法随着时间的增长，网络中汇聚节点接收数据消息的情况。可以看出，改进后的算法节点向汇聚节点传输的数据包大小约为66 559数据包，文献[6]算法节点向汇聚节点传输的数据包大小约为35 893，LEACH算法节点向汇聚节点传输的数据包大小约为7560。文献[6]算法汇聚节点接收数据包大小是LEACH算法的4.7倍，改进后算法汇聚节点接收数据包大小是文献[6]算法的1.8倍。LEACH算法、文献[6]算法向汇聚节点传输的数据包数量较少，是因为未考虑网络中节点距离汇聚节点的远近，导致分簇中节点入簇可能不在有效范围内的情况，从而影响了汇聚节点接收数据消息的大小。改进的算法优化了簇头节点的选取，不仅加入了各个节点到汇聚节点的距离大小考量，还考虑到节点当选过簇头节点后，可再一次被选为簇头的情况，继而最大化的提高节点的利用率，提高了汇聚节点接收数据包的大小。

3种算法节点剩余能量情况如图6所示。

图6 3种算法节点剩余能量情况

图6是网络中节点的剩余能量随着时间增长的对比情况，与图4中存活节点数量直接相关。改进后算法节点能量在第1570轮耗尽，文献[6]算法在1355轮耗尽，LEACH算法在1151轮耗尽。LEACH算法耗能大是因为簇头节点选取随机、节点分布不合理、没有考虑节点到汇聚节点距离，节点剩余能量的原因等。节点的不合理分布容易造成网络中出现极大簇、极小簇的情况，从而导致网络中节点能耗不均匀的问题。文献[6]算法没有考虑各个节点到汇聚节点的距离大小，如果选取的簇头节点距离汇聚节点较远，会加剧网络中总能耗的增加。改进的算法增加了节点的剩余能量，节点距离汇聚节点远近的考量来优化簇头节点的选取，不会产生能量剩余少的节点被选为簇头节点的情况，此外还考虑到簇头节点接收普通节点数据消息的有效范围，避免距离簇头节点远的节点向该簇头节点传输数据时能耗快速耗尽的问题。可以看出进行改进后算法节点总的能量剩余趋势优于文献[6]，体现出改进算法有效均衡了网络能耗。

4 结束语

针对文献[6]中LEACH优化算法的不足，本文在LEACH分簇算法初始化阶段，簇头节点选择随机、成员节点入簇不合理的基础上，提出了一种改进的LEACH算法。改进算法先优化了簇头节点的选择概率，加入了节点在每轮运行结束后网络的平均剩余能量、簇头节点接收普通节点消息的有效范围、网络运行的轮次以及节点到汇聚节点的距离因素；此外还考虑到簇头节点是否可以重复当选为头节点的情况来提高网络中节点的利用率。实验结果表明，改进后的算法有明显的性能优势。