一种煤矿井下无线自组网灾后重构算法

胡青松， 王胜男

(1.中国矿业大学 地下空间智能控制教育部工程研究中心， 江苏 徐州 221116； 2.中国矿业大学 信息与控制工程学院， 江苏 徐州 221116； 3.中国矿业大学 徐州市智能安全与应急协同工程研究中心， 江苏 徐州 221116)

0 引言

煤矿巷道中部署有大量有线通信网络和无线通信节点，它们是地面与井下的信息传递桥梁，对于保障煤矿安全高效生产至关重要。在灾害情况下，这些通信设施常受到不同程度的破坏，导致原有网络拓扑损毁，无法快速准确感知、传输灾情信息，使得救援工作难以开展或效率不高[1]。但此时仍有许多残存节点可继续工作，若能利用残存节点和救援人员新布设的少量节点(简称新设节点)重构应急通信网络，不但能够感知灾害现场态势，而且可为确定受困人员位置提供条件[2]。其中，通过构造局部虚拟骨干网以辅助重构矿山救援网络(Coal Mine Rescue Network，CMRN)[3]能够显著降低网络能量开销，增强连通覆盖控制能力。

矿井通信系统通常包括1个骨干网、多个分支、若干专线。CMRN重构的目的是利用无线重构手段恢复网络连通。需要说明的是，本文中虚拟骨干网与矿井通信系统中的骨干网概念不同。它是一种基于支配集的重构方法，旨在建立一种分层的拓扑关系，负责全网的路由分发和管理，使一些原本由有线骨干网处理的网络功能转为由无线通信节点来维护，从而恢复该部分网络的连通性。虚拟骨干网的主要研究工具是图论中的连通支配集(Connected Dominating Set，CDS)[4]。顾剑峰等[5]提出了一种基于代数连通度的虚拟骨干网构造算法，其核心是维护虚拟骨干网的稳定性。阎新芳等[6]采用独立支配集为移动自组织网络(Mobile Ad-hoc Network，MANET)快速重构骨干网，重构网络具有自恢复能力，同时针对簇头间长距离传输导致能量消耗过大问题，进一步提出了一种基于多级簇树的虚拟骨干网构造算法。

在外部环境大幅改变(如发生事故)致使信道条件恶化情况下，如何维护网络有效性仍是一大挑战。当矿井发生事故后，煤矿巷道中的通信节点发生移位或失效，部分通信链路损坏，残存节点间平均通信距离增大、分布呈不均匀性，网络连通性急剧恶化。该情况下在部分区域仍有可能利用残存节点有效构造虚拟骨干网,以辅助恢复CMRN连通性。为此，本文提出一种基于多维度虚拟骨干网构造的煤矿井下无线自组网灾后重构算法，在部分网络设施损毁情况下，最大限度地恢复该部分网络的连通性，为灾后抢险救援提供通信保障。

1 问题模型

假设煤矿灾后局部受损区域为一个矩形空间。该区域内有1个目标节点和n个可用节点(包括残存节点与新设节点)，如图1所示。每个节点具有唯一的ID，目标节点ID为0，可用节点ID为i(i=1，2，…，n)。各节点初始能量不同且能量受限。假设可用节点具有相同的传输半径，各节点可根据接收信号强度指示(Received Signal Strength Indication，RSSI)计算节点间距离。

图1 煤矿灾后无线自组网Fig.1 Wireless ad hoc network after coal mine disaster

可用节点在网络重构过程中被分为感知节点、统治节点和中继节点3类。感知节点负责感知灾害区域态势信息。统治节点接收其通信范围内感知节点传递的信息，融合压缩后传输给下一跳中继节点，构成虚拟骨干网[7]。网络以周期性方式工作，完成虚拟骨干网构造、数据收集与转发工作。

CDS用简单无向图G=(V,F)表示，其中V为可用节点集合，F为节点之间的连通边集[8]。设D为G的一个非空子集，对于G中的任一顶点v，若满足v属于D或与D中的1个顶点相邻，则D称为G的支配集。如果由D导出的子图为连通图，则D称为连通支配集。D中的节点称为统治节点(支配节点)，不属于D的节点称为成员节点(被支配节点)。

2 虚拟骨干网构造指标

因事故而损坏的通信节点或链路，其位置具有随机性[9]，可用节点在进行网络连通性恢复时重要程度存在差异，需要对可用节点的重要性进行评估。本文提出以无线传感器网络(Wireless Sensor Network，WSN)介数中心度[10]、节点紧密度[9]为基础，辅以节点剩余能量筛选机制的多维度综合评价指标。构造虚拟骨干网时，顺序选取综合评价指标大的节点作为统治节点，以增强局部重构网络的鲁棒性，延长网络寿命。

2.1 WSN介数中心度

如果某个节点被较多的最短路径经过，那么该节点在数据传输中的作用较重要。采用WSN介数中心度来描述这一特性。节点i的WSN介数中心度为

(1)

式中：nk(i)为任意可用节点k(k=1，2，…，n，k≠i)到目标节点最短路径中经过节点i的条数；nk为节点k到目标节点最短路径的条数。

2.2 节点紧密度

不同于寻常的WSN节点分布，局部灾后可用节点分布通常呈现聚集性或稀疏性，节点紧密度反映了这一特性。节点紧密度用于表征某节点通过网络到达其他节点的难易程度，以此衡量节点的重要性，定义为该节点到达所有其他节点的距离之和的倒数。节点i的紧密度为

(2)

式中dij为节点i，j之间的距离。

2.3 多维度综合评价指标

WSN介数中心度和节点紧密度只考虑了节点某方面的重要性，本文将这2种指标与节点剩余能量筛选机制结合，得到多维度综合评价指标，步骤如下。

(1) 构建指标矩阵：

(3)

式中xir为节点i的第r项指标，r=1,2,…,h,h为评价指标数，本文中h=3,r=1表示WSN介数中心度，r=2表示节点紧密度，r=3表示节点剩余能量。

(2) 归一化处理。虚拟骨干网评价指标越大，越有益于重构网络的健壮性，因此对指标矩阵中的元素进行正向归一化处理。

(4)

(3) 指标变异性处理。以标准差体现指标的变异性，标准差越大则指标差异越大，反映出的信息越多，该指标本身的评价强度越大，应该给该指标分配更大的权重。第r项指标的标准差为

(5)

(4) 构建多维度综合评价指标。设Rmr为第m，r项指标之间的相关系数，m=1,2,…,h，则第r项指标用于指标冲突性分析的相关系数为

(6)

指标相关系数越大，则该指标与其他指标的相关性越强、冲突性越小，反映出的相同信息越多，所评价内容越有重复之处，应在一定程度上削弱该指标的评价强度，减小该指标分配的权重。

综合指标的标准差和相关系数，构建第r项指标的信息量：

(7)

cr越大，则第r项指标在整个评价指标体系中的作用越大，应给其分配更大的权重。

第r项指标的客观权重为

(8)

矿井灾后节点i的多维度综合评价指标为

Hi=W1Mi+W2Ci+W3Ei

(9)

式中Ei为节点剩余能量。

经过处理后的指标权重Wr为正向指标，即Hi越大，节点i当选为统治节点的优先级越高。

3 虚拟骨干网构造过程

3.1 初始阶段

初始阶段矿井局部区域所有可用节点都为普通节点(感知节点)。设置20个可用节点随机分布于巷道中，如图2所示。虚拟骨干网构造过程将经历若干轮统治节点选举，每一轮根据多维度综合评价指标选举出合适的统治节点并更新支配集，直至网络呈现收敛状态[11]。

图2 虚拟骨干网构造初始状态Fig.2 The initial state of virtual backbone network construction

统治节点选举步骤如下。

(1) 各节点与1跳内邻居节点交互ID和综合评价指标，生成1跳邻居列表Neighbour_hop1。Neighbour_hop1内各节点再与其1跳内邻居节点交互信息，生成2跳邻居列表Neighbour_hop2。

(2) 在第1次统治节点选举过程中，综合评价指标最大的节点传输半径内ID最小的节点被选举为初始统治节点，其广播自身成为统治节点的信息。

(3) 收到该信息的感知节点将自身设置为被支配节点，并广播自身成为被支配节点的信息，不参与下一次统治节点的选举。

(4) 其余节点重复上述步骤，直至各节点通信范围内不存在孤立的感知节点。

图2中的各节点与其通信范围内的邻居节点交互自身ID和综合评价指标，经过多次选举后，节点3，5，8，9，14，18当选为统治节点，处于其通信范围内的其他节点为感知节点，如图3所示。初始阶段结束后通过该选举方式产生的统治节点可覆盖全部可用节点。

3.2 支配集连接阶段

在支配集连接阶段，虚拟骨干网筛选支配节点并为各支配节点建立连接，形成连通支配集。具体步骤如下。

图3 统治节点选举Fig.3 Election of dominant nodes

(1) 各感知节点监测Neighbour_hop1内的初始统治节点数量，如大于1，即该节点位于2个或2个以上统治节点覆盖范围的交集内，则该节点被选为候选中继节点，否则距离2个不相交统治节点最近的感知节点被选为候选中继节点。

(2) 经步骤(1)筛选出的候选中继节点可能有多个，将处于交集内的候选中继节点根据综合评价指标排序，指标最大的节点被选为中继节点，其他候选中继节点退化为感知节点。

(3) 其余感知节点选择距离自身最近的统治节点加入其统治集合，向其发送数据。

(4) 各统治节点与其通信范围内的统治节点或中继节点建立虚拟骨干网链路，将采集数据以多跳形式传输至目标节点。

(5) 考虑到生成的虚拟骨干网可能存在闭合回路，引入Dijkstra算法[12]在网络中生成较优的树形多跳网络结构。

考虑统治节点长期处于工作状态，能耗较大，而被统治节点具有间歇性休眠模式，且只需与所属的统治节点通信，能耗较小，因此设置1个能量阈值，当统治节点能量低于阈值时触发重新选举过程，选举出的新统治节点接替自身后主动退出连通支配集，避免因能量耗尽死亡而造成更大的网络空洞。

中继节点选举如图4所示。节点6处于统治节点9，14的支配范围内，且该范围只有其1个节点可承担中继节点角色，因此当选为中继节点。而统治节点8，14支配范围内的节点2，7，13，17，20均可作为候选中继节点，因此选取综合评价指标最大的节点20作为中继节点，其他节点退化为感知节点。

选举出中继节点后，退化为感知节点的节点2，7加入距离自身较近的统治节点14，成为其成员节点，节点13，17成为统治节点8的成员节点，如图5所示。类似地，节点4成为统治节点3的成员节点，节点1成为统治节点5的成员节点。各统治节点、中继节点之间建立连接，将收集的灾情数据传输至目标节点。

图4 中继节点选举Fig.4 Election of relay nodes

图5 虚拟骨干网构造完成Fig.5 Finished virtual backbone network construction

4 虚拟骨干网能耗分析

4.1 节点能耗模型

采用文献[13]中的一阶无线电能耗模型分析虚拟骨干网能耗。节点能耗由发射电路损耗和功率放大损耗组成。设置距离阈值d0，当节点通信距离小于d0时采用自由空间模型，否则使用多径衰落模型。

(10)

式中εfs，εamp分别为自由空间模型和多径衰落模型的功率放大损耗。

节点发送能耗为

(11)

式中：s为数据长度；Eelec为节点收发单位比特数据的电路能耗；d为通信距离。

节点接收能耗为

Esm=sEelec

(12)

4.2 数据融合与转发能耗

统治节点可接收并转发前一跳节点传来的数据。统治节点转发能耗为

Etrans=Erm+Esm=

(13)

式中dtrans为统治节点间距离。

假设某区域内共有w个节点，其中1个为统治节点，其余w-1个为成员节点。若每个数据包大小均为s，在1个收发周期内统治节点接收w-1次数据，融合w-1次数据，则其能耗为

Etrans_cs=(w-1)sEda+(w-1)sEelec

(14)

式中Eda为统治节点融合单位比特数据的能耗。

4.3 虚拟骨干网能耗

在每个收发周期内，虚拟骨干网中节点能耗分为以下3种情况：

(1) 若节点为统治节点且承担中继功能，则节点能耗包括融合数据能耗、发送融合数据能耗、转发数据能耗。

(2) 若节点为统治节点但不参与中继过程，则节点能耗包括融合数据能耗和发送融合数据能耗。

(3) 中继节点能耗包括发送自身数据能耗和转发其他节点数据能耗。

统治节点采用多跳形式将融合数据通过虚拟骨干网传输至目标节点，其能耗与数据传输跳数有关[14-15]。虚拟骨干网多跳传输链路如图6所示，统治节点A的融合数据经T跳到达目标节点。

图6 虚拟骨干网多跳传输链路Fig.6 Multi-hop transmission link of virtual backbone network

执行第T跳转发任务的节点能耗为

ET=Enet(T,T)+(T-1)Enet(T,T-1)

(15)

式中：Enet(T,T)为节点发送自身数据的能耗；Enet(T,T-1)为节点转发第T-1跳数据的能耗。

除目标节点外，虚拟骨干网在1个传输周期内的能耗为

Enet=Enet(T,T)+Enet(T-1,T-1)+…+Enet(1,1)+(T-1)×Enet(T,T-1)+(T-2)Enet(T-1,T-2)+…+Enet(2,1)

(16)

5 仿真实验

采用Matlab R2017A平台对基于本文算法重构的网络能耗、规模、节点覆盖率等指标进行验证，并与考虑邻居节点数的基于休眠机制和能量均衡的连通支配集(Sleep and Energy Balance-based Connected Dominating Set，SEBCDS)算法[16]和能量均衡的最小连通支配集(Energy Balance Minimum Connected Dominating Set，EBMCDS)算法[17]进行比较。3种算法采用相同的初始残存局部网络节点模型，参数见表1。为排除随机因素影响，每种算法均重复300次实验，取平均值作为实验结果。

表1 实验参数Table 1 Experimental parameters

设Eelec=5 nJ/bit，εfs=50 pJ/(bit·m2)，εamp=1.3 nJ/(bit·m2)，Eda=5 nJ/bit，各节点1轮传输数据大小为200 bit。网络剩余能量如图7所示。可看出网络运行300轮时，基于SEBCDS算法构建的网络剩余能量趋近于0，而基于EBMCDS算法和本文算法构建的网络仍有少量剩余能量，网络生命周期较长。另外，基于本文算法构建的网络能耗速率小于其他2种算法，原因是本文算法不仅引入节点剩余能量筛选机制，且考虑了对能耗影响较大的WSN介数中心度和节点紧密度因素。

图7 网络剩余能量Fig.7 Network residual energy

为了排除随机性影响，研究了可用节点总数为20时的统治节点变化情况，如图8所示。由于采用平均值，所以部分结果为小数。在相同的节点分布下，网络收敛时虚拟骨干网规模越小，则网络开销越小，性能越优。从图8可看出，SEBCDS算法因仅考虑网络规模，选出的统治节点较少；EBMCDS算法只将节点能量作为选取条件，易选出较多的冗余统治节点，生成的虚拟骨干网规模较大，造成能量浪费；本文算法综合考虑网络的拓扑性度量和能量因素，不求取局部最优，因此在统治节点数未达到饱和时网络规模介于其他2种算法之间；当节点通信半径大于55 m时，各算法选出的统治节点数均趋于饱和，此时本文算法选出的统治节点数略少于SEBCDS算法，从而生成规模较小且性能较优的虚拟骨干网。

图8 统治节点数Fig.8 Number of dominant nodes

可用节点总数为50时网络覆盖率如图9所示。可看出网络覆盖率随节点通信半径增大而增大；EBMCDS算法因只考虑节点剩余能量而忽视了网络拓扑因素对虚拟骨干网的影响，得到的网络覆盖率较低；节点通信半径大于27 m时，由于本文算法均衡了能量、WSN中心介数与节点紧密度3个维度，所以生成的网络获得了较优的簇树从属关系，节点覆盖率优于其他2种算法。

图9 节点覆盖率Fig.9 Node coverage

6 结语

针对恢复煤矿灾后CMRN连通性难题，提出了一种基于多维度虚拟骨干网构造的煤矿井下无线自组网灾后重构算法，引入WSN介数中心度、节点紧密度及节点剩余能量筛选机制3个维度构建虚拟骨干网节点综合评价指标。实验结果表明，基于该算法重构的网络在剩余能量、统治节点数、网络覆盖率等方面表现出较优性能。在后续研究中，拟将该算法与矿井灾后态势感知与数据传输方法结合，实现灾后数据高效感知与稳定传输。