基于多因子与双簇头的LEACH优化算法

胡 栗

（昆明理工大学信息工程与自动化学院 云南省人工智能重点实验室 云南省计算机技术应用重点实验室）

无线传感器网络 （Wireless Sensor Network，WSN）是由多个传感器节点无规律散落在某个空间内，实现信息交互功能的网络体系。 节点之间在一定的条件下实现数据转发，最终将数据传送到基站，完成整个网络的通信工作。 在各个传感器节点通信［1］过程中，节点能耗问题必须关注，节点电池能量是有限的，而且往往被安放在一些复杂空间中，导致电池不易更换［2］，一旦电池能量耗尽，就不能继续执行传递数据信息的任务，相当于该节点“死亡”，若多个节点“死亡”，网络不再连通，最终致使整个无线传感器网络“瘫痪”。 因此，节点的能耗问题是无线传感器网络生命周期的关键限制条件， 在保证网络连通的前提下，减少节点能耗、延长整个网络的生命周期成为无线传感器网络研究的热点。

节点之间采用分簇路由的方式优化节点能耗是目前最有效的途径之一。 经典分簇算法低能耗自适应聚类层次协议 （Low Energy Adaptive Clustering Hierarchy，LEACH）虽然能起到一定的效果，但也存在不足：每个节点都有某种可能成为或者不成为簇头，但每轮重复选举的过程会导致能量浪费；簇头节点到基站的距离不同，距离较远的簇头节点由于经过的路径相对较长，因此会过多使用能量而导致自身“死亡”，致使整个网络处于分区不连通状态； 在选举簇头节点过程中，约束条件少之又少，因此很难选出符合条件的簇头节点完成网络间的信息交互过程。

针对上述问题， 胡源等提出非均匀分簇算法，把整个空间划分成不同区域，在簇头节点的选择上提出采用与距离相关的通信代价评估函数选择最优簇头［3］；刘卫等提出LEACH-C算法，该算法修正了LEACH原先的阈值计算方法，使用两种控制因子作为簇头选择约束条件，同时节点间的距离可以随情况改变［4］；戴剑勇等提出基于改进萤火虫优化神经网络的WSNs分簇路由协议，使用萤火虫智能优化算法和权重因子平衡簇内、簇间的通信距离，采用BP神经网络优化簇头选举和数据传输路径［5］；甄岩等提出分布式能量均衡的WSN动态数据转发策略， 根据节点自身的能量、位置和相关因素构建层次结构，并根据节点的通信开销等选择中继节点进行数据转发［6］。

针对以上提出的分簇路由算法、簇头节点选举与数据传输阶段，考虑因素都不够全面、不能很好地优化节点能耗的问题，笔者提出基于多因子与双簇头的LEACH优化算法，完成网络节点间的通信。

1 网络和能耗模型

1.1 WSN数学网络模型

WSN数学网络模型类似于图论中图的数据结构，无线传感器网络是多个传感器节点随机散落在监控区域，节点与节点之间构成相互连通的链路，因此可以用无向赋权图Gw表示：

1.2 WSN节点能耗模型

WSN节点间数据处理与传输过程的能耗远多于其他应用能耗，因此笔者根据文献［6］中的一阶无线电能耗模型进行说明，分为发送数据和接收数据两个阶段。

发送节点能耗ETX（k，d）的计算式为：

为了简化问题，只考虑同一簇群内的数据融合问题，其中节点数据融合的能耗Ec的计算式为：

其中，ni是簇群内所有节点的数量；EDA是每比特数据融合的能耗。

由式（1）～（3）可以看出，在数据长度相同的情况下，传感器节点的能耗主要是由节点间的传输距离、邻居节点的数量等因素决定的。

2 基于多因子与双簇头的LEACH优化算法

上述提出的各种分簇算法都没有较好地优化节点能耗，单个簇头节点承担数据转发的压力过大， 数据传输过程中缺乏良好的数据转发路径， 不能很好地解决节点能量消耗问题。 而且LEACH算法仅有较少的约束条件，在延长网络生命周期的过程中存在一定缺陷。

为此， 笔者提出基于多因子与双簇头的LEACH优化算法，其基本原理是：首先提出一种新的簇头评估阈值函数，通过加入距离控制因子和轮次能耗因子判断节点能否成为簇头节点；其次设置成簇评估函数判断簇头所在簇群能否成簇，同时设置副簇头节点均衡簇头节点数据转发的能耗压力，降低簇头节点能耗；最后在数据传输过程中通过加入权重因子综合选择中继节点，采用多跳方式转发数据到基站。

2.1 簇头选举

经典LEACH算法中，任一节点都有相同的可能性成为簇头节点， 节点会产生一个0～1范围内的随机值，若该值小于阈值函数T，就采用洪泛方式使其余节点都知道“我”已经是簇头，该轮应该放弃当选。 每次都以同样的方式选举簇头，使得能量消耗的代价随之增加，又因为约束条件少之又少， 导致很难选出符合条件的簇头， 因此LEACH算法存在一定的缺陷。

笔者提出的簇头评估阈值函数T的表达式为：

其中，p是节点成为簇头的概率；r为选举次数；QSCH（i）为簇头评估函数，该函数与节点间的距离、节点运行多轮之后使用的能量情况以及通信半径范围内节点的个数有关。 将节点此刻的值与阈值T进行比较，若大于阈值T，即为簇头。

由于簇头节点要转发大量数据，节点自身能量使用程度要大于普通成员节点，节点的剩余能量固然重要，但是究其根源，节点运行多轮后消耗的能量也是不容忽视的直接因素，通常选举簇头都会考虑节点的剩余能量，但是之前消耗的能量不只是数据传输的能量，还包括每轮节点向邻居节点广播自身信息所消耗的能量，以及换簇过程中控制信息消耗的能量等。 因此，笔者提出轮次能耗因子， 用以衡量节点运行多轮消耗的能量， 同时考虑到节点在与邻居节点通信过程中，节点间的距离也会影响节点能量的消耗量，因此提出将距离控制因子作为评估函数的一部分，由于簇头是针对整个网络的，考虑到全局性，簇头的评估标准还依赖网络中未失效的节点个数。

综上，簇头评估函数QSCH（i）的表达式如下：

2.2 成簇及副簇头选举

在簇头节点选举完成之后，各簇头节点周围的节点根据自己与簇头节点的距离进入相应的簇群内。 因为簇头的选举是针对整个网络而言的，考虑到全局性，根据节点自身的剩余能量和节点与基站的距离， 构造的成簇评估函数QSBC如下：

将簇头节点的剩余能量与整个网络中节点间的距离的比值作为评估值， 选择QSBC值较大的簇头节点成簇。

由于簇头节点既要接收簇内普通节点成员发来的数据， 又要进行簇间数据传输与基站通信，因此在数据接收与转发的过程中，能量消耗显著增加。 针对这个问题，提出用副簇头节点均衡簇头节点的能耗， 当簇群中选出副簇头后，由于默认副簇头与基站的距离比簇头节点近，因此簇头节点先将数据传递给副簇头节点，再一步步传递给基站，进而降低传输能耗。 副簇头节点只针对单个簇群而言，仅考虑节点的局部性，依赖于节点的邻居节点的能量和节点间的距离。 设α与β都是属于［0，1］的均衡调节因子，则构造的副簇头评估函数Pach如下：

在簇头选举与成簇的过程中，综合考虑节点与其通信半径内所有节点的平均距离和最大距离，同时考虑节点的轮次消耗能量和节点的剩余能量，既考虑节点的局部性又考虑整个簇群。 针对簇头存在过大数据转发压力的情况，设置副簇头节点来均衡簇头的能耗，达到了有效优化网络节点能耗的目的。

2.3 数据传输

数据传输分为簇内传输和簇间传输。 簇内传输是指单个簇群内，普通节点成员与簇头节点之间的信息交互。 簇间传输是指在簇头节点完成簇内传输后，通过多跳将数据传递给基站。 但是由于网络节点的分布是随机的，所以簇头与基站的距离不一，距离基站的远近程度可以衡量数据转发路径的长短，若到基站距离较短则选择一跳传递数据，反之则选择过渡点作为数据的承上启下节点（即中继节点），使得路径满足多跳的条件，将数据传递给基站。

要构建最优传输路径，中继节点的选择受多种条件的约束，同时考虑到簇群规模越小，簇内数据传递越少，簇头在数据处理过程中消耗的能量就越小。 笔者考虑多种限制条件：簇头节点与基站间的距离、簇群规模和簇头节点自身剩余能量，进而构造路径权重因子，作为判断中继节点构造最优传输路径的标准。 路径权重因子ω的表达式如下：

ω越小，表示簇头节点间的距离越小，簇群规模较小，且簇头节点剩余能量越高，更适合作为中继节点转发数据。

3 算法步骤

基于多因子与双簇头的LEACH优化算法的步骤如下：

a. 计算节点的轮次能耗因子、集中度和距离控制因子，构造新的簇头评估阈值函数；

b. 根据新的簇头评估阈值函数判断是否可以成为簇头；

c. 选举簇头完成后， 构造成簇评估函数，普通节点自行进入到某个簇中， 成为簇内成员节点；

d. 在簇群内设置副簇头节点均衡簇头的数据转发能耗；

e. 在数据转发阶段根据多种因子综合选择中继节点，形成最优传输路径，将数据传递给基站。

4 仿真模拟

仿真模拟在Matlab 2019a平台进行， 本试验模拟100个传感器节点安置于200 m×200 m的区域中，基站默认在空间最右边。 通过加入多种控制因子， 优化簇头选举成簇和数据传输， 对节点的剩余能量以及运行的轮数通过多种算法进行仿真。 该试验将LEACH 算法、LEACH-C算法和笔者算法在节点存活数和剩余能量比值两个方面进行分析对比， 以证明笔者算法的优越性。

WSN参数设置如下：

节点分布区域 200 m×200 m

数据融合能耗Ec50 nJ/bit

节点初始能量Emax1 J

节点的通信半径R 30 m

WSN中节点的簇内传输是指单个簇群内，普通节点成员与簇头节点间的信息交互。 簇间传输是指簇头节点完成簇内传输后，通过多跳最后将数据传递给基站。 由于与基站的距离不同，导致能耗不同，因此为了分担簇头进行数据转发的能耗压力，设置副簇头节点，默认副簇头节点的位置更靠近基站， 距离相对较近。 通过在200 m×200 m的空间内随机布设100个传感器节点，节点仿真分簇，每个簇群的簇头节点和副簇头节点分布情况如图1所示。

图1 簇头成簇示意图

在无线传感器网络中，节点能耗均衡度是判断该网络保持网络数据通信时长的一个重要标准，通常情况下，运行一定轮数后，节点的剩余能量和网络中存活的节点数可以作为网络连通持久的参考依据。 现通过比较LEACH算法、LEACHC算法和笔者算法在轮数一定的情况下， 节点的最小剩余能量和平均剩余能量的比值以及存活节点数进行分析。

3种算法节点最小剩余能量和平均剩余能量的比值趋势如图2所示， 当节点运行600轮时，LEACH算法节点剩余能量比值为0.75，LEACH-C算法为0.83，笔者算法为0.86；当节点运行1 100轮时，LEACH算法节点剩余能量比值为0.0，LEACHC算法为0.5，笔者算法为0.7；当节点运行1 400轮时，LEACH算法和LEACH-C算法节点剩余能量比值均为0.00，而笔者算法为0.55。 由此可以看出，当LEACH 算法失效时， 节点能量耗尽，而LEACH-C算法和笔者算法的节点最小剩余能量和平均剩余能量比值较大， 能耗相对更为均衡；当LEACH-C算法失效时，节点能量耗尽，而笔者算法节点的最小剩余能量和平均剩余能量比值较大， 能耗相对更为均衡。 仿真试验结果表明， 当运行轮数一定时， 节点的剩余能量比值可以有效地衡量网络能耗情况， 随着轮数的增加， 节点最小剩余能量和平均剩余能量的比值在减小， 从各个算法比值的坡度趋势来看，在相同轮数情况下， 该比值越大， 各节点能量差距越小，能耗越均衡。 因此，从3种算法的节点剩余能量比值差距程度来看， 笔者算法在加入双簇头和多重控制因子后， 有效地均衡了节点能耗， 延续了节点运行的轮数， 延长了网络节点的生命周期。

图2 3种算法节点最小剩余能量和平均剩余能量比值趋势

3种算法存活节点个数的趋势如图3所示，节点运行到1 100轮时，LEACH算法存活节点的个数开始减少；当节点运行到1 400轮时，LEACH-C算法存活节点的个数开始减少，而笔者算法存活节点的个数还未减少，说明笔者算法能够有效延长网络生命周期； 当节点运行到2 500 轮时，LEACH算法存活节点的个数为0个，LEACH-C算法的也为0个， 而笔者算法存活节点的个数虽然减少，但仍然有大量存活节点，说明笔者算法相对而言能够运行更多轮数；当节点运行到3 100轮时，3种算法存活节点的个数均为0。 试验表明，在轮数一定的情况下，存活节点的个数越多，即表明网络中剩余可用节点的数量越多，可以继续进行网络信息交互，在能量有限的情况下节点能运行更多轮数。 随着运行轮数的不断增加，节点能量随之减少， 监测区中的节点剩余数会随之减少。 当运行轮数一定时，网络中节点的存活个数作为决定该网络是否可以继续使用的条件，即判断网络生命周期的另一个重要标准。 说明笔者算法相比于LEACH算法和LEACH-C算法，对网络生命周期的延长效果有明显提升。

图3 3种算法存活节点个数趋势

5 结束语

在无线传感器网络节点通信时，均衡节点能耗和延长网络生命周期是当前研究领域的重点。笔者提出的基于多因子与双簇头的LEACH优化算法， 通过设置双簇头节点均衡簇头节点的能耗， 在考虑剩余能量的同时考虑轮次消耗能量，设置距离控制因子和轮次能耗因子，数据传输过程加入路径权重因子选择中继节点构造最优传输路径。 仿真试验证明了笔者方法的优越性。 但是在轮次能耗因子的计算上增加了复杂度，而且在网络分簇过程中会存在某些节点不属于任意簇的情况，造成了节点资源的浪费，优化解决这些问题是下一步的研究方向。