LEACH 算法应用于矿井无线通信的路由算法研究

2022-01-28王越群通信作者高小虎曹春梅

电子制作 2022年1期

王越群（通信作者），高小虎，曹春梅

（江苏商贸职业学院电子与信息学院，江苏南通，226000）

1 应用于矿井中的无线传感器网络分层路由算法

无线传感网[1]路由算法的主要作用是优化路径，探求初始结点和目标结点间的多跳优化路径并将数据沿优化路径正确传输[2]。其中，分层路由算法应用最为广泛，而LEACH 作为最基础的分层路由算法之一，也常被用来作为改进算法的基础算法。

针对长带状井道的环境结构，提出LEACH-mine 算法。在LEACH 算法的蔟首选择中，没有重视结点电量。LEACHmine 算法将结点剩余电量作为条件，以蔟内结点的均衡电量作为比较基准，选出电量高的结点成为蔟首。限制结点多次成为蔟首，均衡电量损耗。

(1)成蔟阶段，在狭长的巷道内，蔟首不必向所有区域内的普通结点发送消息，只需通知相邻结点，邀请入蔟。以距离蔟头的长度为基准，结点选择距离小的蔟，发出申请信息，这样减少蔟头电量损耗。

(2)信息传递。蔟间通讯采用多跳方式将消息传送至Sink结点。利用最小跳数路由算法，选择电量最多且相距最远的结点转发信息。

算法在相同电量的基础上，信息传输距离最远，优化电量利用效率，适合远距离传输的网络结构。而在文献[3]中，笔者提出线性拓扑和局部电量均衡的分层路由算法。蔟首选举的过程中，不仅考量结点当前电量，还引入相对位置均衡因子，使得位于区域中央且电量较高的结点更方便成为蔟首，有效解决了巷道边缘结点成为蔟首，却不利于转发消息的问题。

文献[4]中，为了解决带状巷道的能耗均衡问题，笔者提出LEBUC 算法。将结点电量、结点与Sink 结点的距离、结点分布密度作为控制条件，选出符合要求的蔟首，改善矿井WSN 路由电量空洞的情况。在分蔟前，由电量模型计算出能耗最小的条件下，最优的蔟首期望个数，而后通过调整阈值，使得候选蔟首的数量大于期望的最优个数，竞争失败的结点暂时“停工”，以减少能耗。长距离线性巷道中，靠近Sink 的结点由于大量转发监测信息，能耗快，生命期短，因此解决此电量“空洞”的有效办法是计算合理的蔟首竞选半径。作者改进了 EEUC 算法[5]只考虑候选蔟首与Sink 结点距离的情况，加入对结点剩余电量的考量。

2 LEACH 算法

LEACH 算法作为分蔟路由算法中最典型的算法，对WSN 路由算法的设计另辟新径，但是矿井巷道的网络拓扑不同于其他环境下的结构，LEACH 算法应用在矿井巷道狭窄绵长的环境中，仍存在很多的不足之处[6]。

WSN 的路由机制负责选择信息传递的路径，而传输的效率则决定了整个网络的使用周期，即传输速率越快，电量损耗越少，网络使用时间越长[7]。LEACH 的分蔟理论能够适应矿井长巷道的环境结构，使得蔟内结点能够将收集的信息统一由蔟首结点简单处理后压缩传送，节省时间和电量。蔟首结点承担预处理感知数据以及转发数据的功能，因此，如何优化蔟首结点选择机制显得至关重要。传统的LEACH分蔟算法在蔟首结点选择机制上，考虑因素单一，面对矿井复杂多变的应用环境，性能显得不够稳定。

LEACH 算法是一种低功耗自适应集蔟分层型算法，从上一节的讨论中，可以看出LEACH 算法作为经典分蔟机制，应用于矿井长巷道环境中，还是有很多缺陷，蔟首结点选择的策略上随机性太强，选择蔟首结点的约束条件太少，无法保证最终蔟首结点自身剩余电量多，位置优越，和其他结点通信便利的优势。位于巷道中心，剩余电量多且邻居结点数量多的结点成为蔟首结点更利于信息的转发和收集。

文献[8]在改进 LEACH 算法中，通过改变结点成为蔟首结点的概率的计算方式，对阈值T(n) 引入结点电量因子和相对位置因子，提高剩余电量高且距离区域中心的较近的结点成为蔟首结点的可能性。但是并没有考虑到蔟内结点与蔟首结点通信的情况，如果蔟首结点本身的邻居结点个数较多，也就是与蔟首结点直接通信的结点数量较多，可减少蔟内收集数据时多次转发而产生的电量损耗和时延。

本文主要考虑从三个方面优化蔟首结点选择机制，将结点剩余电量、邻居结点个数、结点距离局部区域中心的距离三个因素引入阈值和结点产生的随机值的计算中。

(1)将结点剩余电量作为结点产生0～1 随机值的条件因素，使得剩余电量高的结点产生的随机值越小；

(2)在初始阶段，统计邻居结点的个数，在计算阈值T(n) 时可加入考虑，降低邻居结点个数较少的结点成为蔟首结点的可能性；

(3)选择距离区域中心位置近的结点作为蔟首结点，可保证通信范围和通信质量。

3 基于LEACH 优化算法的矿井WSN 路由算法

■3.1 阈值的优化

针对矿井长直巷道结构，在矿井网络的每个区域内蔟首结点的选择过程中，对阈值进行优化，引入结点的相对位置因素和结点邻居结点个数，进而优化 LEACH 算法的蔟首结点选择机制。

■3.2 RPLA 算法描述

对WSN 模型的预设条件为以下几点：

(1)传感器电量有限，但类型相同。

(2)假设Sink 结点电量不受限，可以持续工作，且不能变换位置。

(3)传感器结点随机部署在监测区域后，位置不能变换。

(4)每个传感器结点都可以对数据进行融合。

(5)传感器结点可以自动调节发射功率。

(6)Sink 结点收集数据后定时向基站发送。

上述条件中假设Sink 结点是电量不受限制的传感器结点，采用集中式控制策略执行机制[9]。机制的执行过程具有周期性，每轮执行过程包括两个阶段：成蔟阶段和稳定信息传递阶段。其中成蔟阶段包括蔟首结点选择阶段、蔟首结点收集蔟内成员结点信息阶段、最终蔟的形成阶段；而稳定信息传递阶段包括蔟内传输、蔟间传输。本章主要研讨蔟的形成阶段：

(1)初始化蔟首选举阶段

算法规定一个0-1 之间的阈值T(n)，并通过公式（1）得出结点产生的随机值µ：

式中，Eire为结点剩余电量，E0为结点初始电量。若µ

(2)普通结点要求入蔟

蔟首结点产生后，向附近结点广播竞选成功的消息，消息中包含蔟首结点的位置和剩余电量情况，其他普通结点通过比较与本区域蔟首结点和左右相邻两个区域蔟首结点之间的距离，来选择距离最近的蔟首结点，发送要求入蔟的消息，同时将自己的位置信息、剩余电量信息、ID 号以及结点的邻居结点数量信息，压缩发给要要求入蔟的蔟首结点。

(3)蔟首结点收集信息

蔟首结点收集蔟内成员的位置信息、剩余电量信息、结点ID 以及结点的邻居结点数量（结点度数）信息等，将成员结点信息存储表中。

(4)完成阶段

蔟首结点设置TDMA 时隙表调度蔟内结点避免发生冲突。蔟首结点将TDMA 时隙表发送给蔟内成员，成员结点根据收到的时隙表，按照确定时隙向蔟首结点发送感知信息。

稳定传输阶段，蔟内结点与蔟首结点采用单跳通信，在规定时间内直接将采集的数据发送给蔟首结点，在非传输时间内，关闭无线电设备保存电量。一段时间后，下一轮蔟首结点竞选开始。蔟间通信则采用单跳直接通信方式，数据经过蔟首结点简单的处理融合后，发送给相邻Sink 结点。

RPLA 算法的核心代码如图1 所示。

图1 RPLA 算法核心代码

4 仿真与分析

■4.1 仿真环境

表1 仿真参数表

本次仿真实验监测的区域范围是200m×10m 的矩形区域，模拟矿井长直隧道形状，监测区域长度长于宽度，其中随机部署100 个结点，并将Sink 结点坐标设置为区域边界靠近中轴线，坐标为（200，25），这样可使结点密度适中，便于观察结点位置和分蔟效果。结点初始电量、数据包大小和报头大小等无线电量模型相关参数的取值与文献[9]相同。

■4.2 仿真结果与分析

(1)基站接收数据包数量比较

图2 给出三种算法中基站接收的数据包的数量，接收数量差异较大，很明显改进后的RPLA 路由算法中基站接收的数据包数量远远超过 LEACH 算法，略优于 LEACH_ C 算法，从图2 中可以看出，RPLA 机制接收的数据包数量高于LEACH 算法且是LEACH 算法接收数据包数量的约两倍左右，LEACH 算法在第600 轮时不再接收数据，而LEACH_C 算法从第600 轮开始接收的数据包数量也在减少，但改进的RPLA 路由算法从开始时，接收的数据包数量就远大于LEACH 算法，LEACH_ C 算法虽然接收数据包的数量多于LEACH 算法，但在第700 轮开始接收数据包的速度缓慢，最后结点全部失效，不再接收数据包。

图2 基站接收数据包数量比较

RPLA 路由算法在蔟首结点选举上考虑结点的剩余电量情况，利用单个结点剩余电量与全部结点总电量的比值作为产生的随机数，同时重新构建阈值中结点成为蔟首结点概率的计算模型，根据实际工程背景，加入了结点相对位置和结点邻居结点个数两个因子，因此选举出的蔟首结点电量相对较高且位置便于信息传递。

(2)存活结点个数比较

图3 中给出了LEACH、LEACH_ C 以及 RPLA 三种算法的存活结点个数的比较，在200 轮的实验时间之前，三种算法存活结点个数相差不大，但在实验中后期，随着实验时间的增长，三种算法的能耗逐渐增多，RPLA 机制的优势明显，相较于其他两种机制，RPLA 机制能耗较少，存活结点数量较多。在实验进行到第700 轮时，改进机制的存活结点数约是LEACH_ C 机制的4.5 倍，而LEACH 算法此时的存活结点数已经为0，网络生命周期早已经结束。

图3 存活结点个数比较

LEACH 算法随机选举蔟首结点，信息传递能力不强，反而导致能耗更多，RPLA 机制针对LEACH 算法的不足，做出改进，蔟首结点的位置位于区域中心，可以缩短蔟内结点的信息传递距离，降低能耗，从而延长井下网络使用时间。

(3)结点平均剩余电量比较

正如图4 所示，对三种算法的实验结果进行对比分析，在井下网络工作的时间里，传感器平均剩余电量的情况，实际上，反映出结点的平均能耗情况。可以看出LEACH算法中结点的平均剩余电量在第700 轮时为0，而此时LEACH-C 算法和RPLA 算法的结点平均剩余电量仍有很多，由于RPLA 算法在蔟首结点选择时考虑到结点的相对位置和邻居结点个数，当候选蔟首结点位于区域中心附近且邻居结点个数较多时，蔟首结点的邻居结点可以直接将感知数据发送给蔟首结点，缩短蔟首结点与结点之间的距离，减少能耗。