基于果蝇优化算法的矿井WSN路由协议研究

王越群，汤丽娟

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

1 绪论

矿井工作环境在不断变化，地面和井下的良好沟通需要依赖持续稳定地从井下接收有效可靠的信息，如巷道中自然因素信息（煤尘、风速等）、矿工信息等数据，事故发生时，地面工作人员才能做出准确地判断和决定，确保矿工生命安全[1]。无线传感网便于扩展，十分符合矿井井下的工作环境，既能确保感测消息的及时传送，又便于网络布置[2]。因此，WSN也被更多地使用在矿井行业中。

WSN（Wireless Sensor Network）作为一种分布式自组织的实时性网络，在矿井行业中主要被应用于井下的人员定位，井下环境数据的采集以及安全监控[3]，这些应用都需要信息及时可靠地传输。针对国内矿井环境，为保证无线网络的可靠性，对设计井下无线网络的路由机制或相关改进机制却并不多。因此，设计一个高性能的WSN路由协议，对矿井作业十分重要[4]。

2 无线传感器网络路由协议

■2.1 矿井WSN路由协议分析

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

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

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

（2）数据传输。簇间通讯采用多跳方式将消息传送至Sink节点。利用最小跳数路由算法，选择能量最多且相距最远的节点转发信息。

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

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

煤矿巷道深长，网络设计有特殊性，且存在诸多问题，在矿井巷道环境下使用层次路由如LEACH算法的挑战和有待调整的地方有如下几点:

(1)协议没有将候选簇首的剩余能量作为条件因素之一。

(2)簇首的选举是随机产生的，由于人员的移动导致节点分布随机且不均匀，因此簇的范围大小也就不均匀，容易造成小范围内有多个簇，某些偏远位置只有一个大范围的簇存在，这样不利于数据的传输。

(3)在窄长巷道中，Sink周围的簇头传送自身的融合消息同时，也要负责转发其他簇头的消息，能耗负担过重，容易失效，出现路由“空洞”，改变网络结构，降低网络功效。

■2.2 基于能耗均衡的层次路由算法分析

最初的层次路由算法，以LEACH协议最为经典。LEACH算法的分簇机制中，以“轮”为时间单位，在每一轮中，选举出符合条件的簇首，从公式（1）中可以看出，能否成为簇首主要取决于网络中簇首数量的比例。

其中，P是簇头节点数占总节点数的比例；r是已经过的轮数；G是在前1/P轮中没有充当簇头节点的集合。

LEACH- mine算法在选举簇首时，加入了节点剩余能量这一条件，优化了LEACH算法随机选举簇首的问题。而线性拓扑和局部能量均衡的分簇路由协议（ LEACHTLLEB），簇首的条件还加入了节点位置信息，在巷道的狭长网络拓扑结构下，边缘节点避免成为簇首，有利于信息的转发。但以上两种优化算法都没有改善矿井无线网络中路由“空洞”问题。 PCEB-MS路由协议（DPCA算法）则通过控制节点功率调节成簇范围大小，解决路由空洞问题。SOCRP协议以簇首间“局部协商”策略，缓解了数据传输的“重叠”问题。

■2.3 矿井WSN路由协议存在的问题

WSN分布在矿井的狭长带状空间中，复杂的环境状况和具有特殊性的空间结构都让矿井 WSN路由协议的设计具有一些特殊性和挑战[9]：

（1）能耗不均

单跳通信的传输方式已经无法适应矿井巷道的结构特点，若按传统方式将 Sink节点安置在巷道通风口处，那远离巷道口的节点由于巷道几十米甚至数百米的传输距离，普通节点无法负荷超长距离的传输，所以节点必须通过中间节点转发数据才能将有效信息传回到Sink节点，距离Sink节点较近的节点由于多次充当“数据中继站”，能量负担远大于其他节点。因此，多跳方式也存在能量负载不均衡的问题。

（2）数据延迟

长距离的多跳传输，距离较远的节点传输数据经历的跳数越多，引发数据延迟问题。因此，多跳路由机制的关键问题是如何实现跳数与链路的能耗平衡。

（3）数据传输的可靠性和精度

矿井条件恶劣，无线电信号的传输会受到严重干扰，但是由于矿井对于地下的安全性要求较高，所以对感知数据的精确度也有较高的要求，矿井 WSN路由协议的有一大挑战就是确保恶劣条件下数据传输的可靠性和精度。

（4）可扩展性

随着节点的失效死亡以及工作面的掘进带来的新的节点的投入，网络路由机制的设计要有足够的可扩展性，网络的性能不能随着规模的增大而降低[10]。

■2.4 果蝇优化算法

为了方便研讨最短路径问题，矿井网络路由可以用带权值的图来表示，可以表示为G(N,B)，N表示矿井网络中的节点数量，B表示通信节点间的通路，Cij表示通路(i,j)的权值,C=C[ij]表示权值矩阵，S,D分别表示源节点和目标节点，Iij表示每个通路的链接，定义如下:

如果Iij=1，Ijk=1，则Iik=1，网络中求最短路径的问题可以转化为求目标函数最小值的优化问题，目标函数可表示如下：

■2.5 适应度函数

在路由网络中，因为会用到邻居节点来转发数据，因此邻居节点的剩余能量因素也要作为优化需要考虑的条件之一。Er、Erb、Erave分别代表节点的剩余能量、邻居节点的平均剩余能量和节点的平均剩余能量。这样，单个节点的能量便可由公式（4）表示[11]:能量可分别由：

其中，α，β表示平衡因子，令0＜β＜α，表示更注重节点的剩余能量情况。

公式（5）中，fn(i= 1,2,3,...,n)分别对应路径中第i个节点的能量平衡值，节点的能量平衡比如公式（6）所示：

节点能量安全平衡比Vsafe=ε，0<ε<0.3。Vsafe是节点能量相较于全网能量比值的安全值，假若节点的能量过低即V＜Vsafe，那么该节点进入保护状态，不再采集数据和转发数据。若ε取的值较小时，网络的初始能量与能耗成反比；反之，取大值。

已知Numnb（i=1,...,n）表示第i个节点的邻居节点个数，簇内路由选择考虑节点邻居节点个数多的节点，在其中优先选择能量代价较小的节点且邻居节点数较多的节点作为下一跳转发节点，保证整体选择最优路径，因此用单个节点的邻居节点数倒数来表征。

在保证节点数量最少的条件下，优化的最短路径应满足公式（8）[12]：

利用邻居节点个数和节点剩余能量代价构造适应度函数，如公式（9）所示：

在开始时刻产生一定数量的果蝇个体，计算每个个体的fitness，比较出最小值，迭代更新果蝇集体的位置和方向，fitness最小值对应的节点，就是对应最佳路径上的节点。

图1

■2.6 MRP-FOA算法思想

MRP-FOA算法的设计思路是：簇首节点选举过程以节点剩余能量和全网能量的比值产生节点随机数，与阈值比较，平衡全网节点的剩余能量；由于簇间通信邻居节点承担转发的功能，将节点的邻居节点个数引入作为“度数”平衡因子，利用节点邻居节点个数确定出最终簇首节点；簇首节点位置应尽量满足距离区域中心距离最近的要求，由此将节点与区域中心的距离作为相对位置衡量因子引入阈值计算中；稳定传输数据时，簇内节点与簇首节点通信，采用多跳与单跳结合的方式，如果簇首节点与节点距离很近，属于邻居节点，那么节点直接将数据发送给簇首节点，若相距较远，则根据FOA_C算法找到的最优路径依靠其他节点的多跳转发，将数据发送出去。

3 仿真与分析

仿真参数如表1所示。基于果蝇优化算法的分簇路由协议仿真结果分析如下：

表1 仿真参数表

（1）可靠性比较

图2中可以看出MRP-FOA协议中基站接收数据包最稳定且数量最多，这是因为本文在设计网络模型时考虑到矿井巷道监测的独特性，因此采用等分区间设置多个Sink节点，缩短簇首节点与Sink节点间的距离。

图2 数据包接收率

(2)死亡节点数量比较

图3中可以明显看出失效节点数量随时间的变化趋势，MRP-FOA协议死亡节点数量最少，网络生命周期持续最长（实验设定90%节点死亡时间为网络生命周期）。

图3 死亡节点数量

4 结论

本文优化了簇间通信机制，在簇内普通节点到簇首的路径选择上，通过改变步长优化果蝇算法的收敛速度，同时结合簇内节点到簇首欧式距离以及节点能量创造适应度函数，利用改进的果蝇优化算法FOA_C得到簇内节点到簇首的最短路径，使得稳定传输阶段，簇内数据信息收集时，节点能耗降低，进而达到整体网络能耗降低的效果。

无线传感网在矿井方面的使用已经引起广泛地关注和讨论，本文大量调研了关于矿井无线传感网层次路由算法的相关研究，针对煤矿井下网络的特殊结构和层次路由协议的不同应用，进行深入分析和对比各算法的优势和不足之处，层次路由算法将散落在窄长巷道的传感器节点分簇，便于这种特殊拓扑结构的网络构造，针对不同的问题，如能耗、时延等各协议给出了相应的改进策略，但大多是以高能耗为代价，减少时延和保障通信质量，或是为降低时延而增加网络带宽的开销。