基于消息效用的煤矿井下概率路由算法研究

杨 萍，李敬兆，张小波，吕 乐，唐 俊

(1.安徽理工大学 电气与信息工程学院，安徽 淮南 232001；2.中国科学技术大学，安徽 合肥 231600；3.陕西延长石油榆林煤化有限公司，陕西 榆林 719000)

煤炭作为科技发展的重要工业能源[1]，煤炭工业为我国经济发展提供了重要支持。然而，由于煤矿井下空间异构、环境恶劣，导致瓦斯事故、机电故障等时常发生。因此，需要对矿井进行全覆盖、不间断的安全监测。但是矿井有线通信部署困难，成本较高；无线信号衰减快，存在视野盲区。在这种情况下，机会网络被引入到矿井通信系统中。

机会网络(OPportunistic NETwork)是一种不需要进行网络部署，对基础设备要求不高的移动自组织网络[2，3]，常应用在车载网络、灾难应急、野外数据收集等领域[4-6]。机会网络是通过移动节点间的相遇带来的通信机会进行数据的传输[7]，所采用的路由机制是“存储—携带—转发”，在中继节点上缓存信息，遇到其他节点时进行信息转发，直到信息到达目的节点[8]。一般地，机会网络中的节点是由人携带的便携性通信终端构成[9]，具有移动性强、网络连接间歇性[10]和网络延时大的特点。

因此，在矿井实际应用场景中，携带通信设备的矿工和车辆可视为移动节点，通过日常工作活动和交流，使得节点相遇，从而实现数据传输。因为人是具有社会性的，根据工作任务来进行活动，相应地，节点也具有一定的社会性，节点移动的随机性减小[11]。针对以上实际特点，本文提出一种基于消息效用的煤矿井下概率路由算法，根据节点的聚散程度划分为不同社区[12]，并依据社区内外节点的社会性，设计不同的路由机制，使得消息投递成功率提高、网络延时降低；并建立缓存管理机制，合理管控节点缓存空间[13]，减少网络中的冗余消息。

1 文献综述

机会网络是依靠节点的移动传递消息，这便决定了网络延时较高、投递成功率低等特性，为解决这个问题，一般从缓存管理策略和路由策略两大方面解决机会网络消息传递过程出现的问题。

文献[14]针对矿井环境和矿工移动特点分区建立马尔可夫模型，通过综合开考虑计算出终端网络时延、 与目的节点相遇概率和扩散范围，最后选择最合适消息转发策略，实现分组低延时转发。但是在终端活跃度差异不大，活动范围较大的情况下，不能良好地模拟出矿井的实际情况，并且没有考虑缓存空间和网络中的冗余副本，造成网络负担较大。

文献[15]以消息传递概率作为消息转发依据，先后计算当前一跳和二跳节点的消息传输概率；将二跳节点的消息传输概率与一跳节点的消息传输概率比较，若一跳节点的消息传输概率大于二跳节点，优先选择一跳节点中消息传递概率大的节点传输消息；若都不是，则将消息存于缓存区。该算法减少了网络中的消息副本，并提高了消息投递成功率，但是算法复杂，使得网络延时增加。

文献[16]提出了基于运动相似性的机会网络缓存管理策略，首先定义并计算节点的消息扩散程度和运动相似性，从而得出消息转发效用值和存储效用值；其次，依据消息转发效用值来选择合适的节点转发消息，当缓存空间溢出时，优先丢弃存储效用值较低的消息。该算法将节点运动相似性和缓存空间作为消息转发概率影响因素，有效减少节点的盲目携带，降低了网络负载，但是没有考虑节点相遇持续时间对节点消息转发的影响，该算法的消息投递成功率有待提高。

文献[17]通过收集节点的历史接触信息，包括节点的相遇时间、相遇次数和节点关系稳定度，以此计算节点转发效用值；然后，在通信范围内选择消息转发效用值最大的节点转发消息；最后，根据余弦相似度选择下一节点转发消息。该算法使得转发节点最大程度均匀分布，但是容易导致消息重复扩散，并且对于活跃度大，消息转发概率高的节点利用率不高。

本文根据井下移动节点移动规律和节点间的社会性，对节点移动范围进行分区，根据社区内外的节点移动属性选择不同的路由传输策略。通过加入节点的相遇持续时间、移动轨迹相似度等相关因素，形象模拟了井下节点的移动特征，有效地提高了消息投递成功率，并大幅度降低了消息延时和网络负载。

2 网络模型及定义

2.1 矿井机会网络模型

煤矿井下通信信号差，巷道中节点间的通信链路间歇性连接甚至不连接，因此通过增加矿工和矿车携带的移动通信设备，从而增强井下的通信交流。矿工或矿车表示移动节点，因此节点间具有一定的社会关系，并保持相对稳定。节点间的密切程度与工作内容相关[18]，因此煤矿井下的节点间可形成一种隐形的工作关系网络，这种关系网络表示了节点间因工作而产生的联系程度，定义网络的节点集合V={v1，v2，…，vn}，节点之间的关系连接集合E⊆{(a，b)|a，b∈V}，那么可以得到加权无向图：

G=(V，E，ρ)(1)

式中，ρa，b表示节点a和节点b的关联性，数值越大，表示节点a和节点b之间相遇频率越高、密切程度越高；若(a，b)∉E，那么ρa，b=0，即节点a和节点b之间无交集；ρa，b∈[0，1]，根据工作安排调整参数。在社区内部，节点密度较高，联系频繁，而处于不同社区的节点联系的频率相对较低。因此，将网络按照节点密度划分为不同的社区。

井下矿工和矿车的往往遵循相同的移动规律，他们会根据自己的工作任务在固定的巷道中移动，行驶相同的移动轨迹，因此本文选用基于地图的固定路线的MRM(Map Route Movement)作为移动模型[19]，用其来模拟矿车和矿工在井下工作的移动规律。矿井机会网络的应用场景如图1所示。

图1 矿井机会网络应用场景

2.2 相关定义

1)定义1 ：节点相遇持续时间。井下移动节点的工作活动往往表现出周期性的规律，并且，节点间的关系随着移动过程中与其他节点频繁建立连接而加强。节点在移动过程中可以和一个节点建立多次通信或者和多个节点建立通信，每次的通信时间都不相同，若节点间的通信次数越多，通信时间越长，表明节点间的关联性越强。那么用通信时长表示节点间的关系程度，设计在时间T内，节点a和节点b间建立通信n次，通信时间集合为{t1，t2，…，tn}，那么节点的相遇持续时间公式为：

ρa，b=Ta，b/T=(t1+t2+…+tn)/T(2)

式中，Ta，b表示节点a与节点b相遇持续时间总和。

2)定义2：节点移动轨迹相似度。煤矿井下的矿工和矿车的每天工作几乎无异，因此它们的移动轨迹往往有着高度重合性，通过比较矿工当前的移动轨迹和历史移动轨迹，衡量该节点历史移动轨迹信息的可用性，以节点的移动轨迹去辅助预测节点的相遇概率，在时间T内，取m个轨迹点。节点i的历史轨迹按照时间顺序由轨迹点组成，历史移动轨迹为{p1，p2，…，pm}，当前的移动轨迹为{q1，q2，…，qm}，则节点i移动轨迹相似度计算公式：

其中，匹配函数：

式中，|d|为两轨迹点间的距离；ε为当前和历史节点移动轨迹点间的误差，可根据节点移动速度适当调整。当两轨迹点之间的距离少于等于ε时，match函数取值为1，表示节点历史移动轨迹与当前移动轨迹重合度较高，具有较高的可信度。否则match函数取值为0。

3)定义3：节点相似度。节点a和节点b的相似率是指节点a与节点b拥有的共同相遇节点个数与它们两个节点分别相遇的节点总数的比值。

式中，Na表示在时间T内节点a所相遇的节点；Nb表示在时间T内节点b所相遇的节点。

3 基于消息效用的煤矿井下概率路由算法

根据煤矿井下工作内容的不同将节点活动分为两类：①工作活动限制在一个范围内，定义为社区内；②在不同的工作区域活动，定义为社区间。

3.1 社区内消息效用值转发策略

同一个区域内矿工的工作内容和范围相同，对于社区内的消息传递概率也大致相同，优先选择节点中缓存空间、活跃度高的节点，消息投递的成功率也更大。用消息转发效用值作为判断依据，节点选择消息转发效用值最大的进行数据的转发。

其中，Ti为节点i在时间T内与其他节点相遇持续时间总和；Ni为节点i在时间T内相遇节点个数，N表示总节点个数；Bfree为节点剩余缓存空间；Btotal为节点总缓存空间。

3.2 社区间移动轨迹辅助决策消息转发策略

节点的移动轨迹和历史移动轨迹重合度越高，则节点历史信息的可信度越高。利用节点移动轨迹相似度辅助相遇概率的预测，相遇概率的计算分为更新、衰退、和传递三个部分。

1)更新。当社区间的两节点相遇时，用一下公式更新投递概率：

P(a，b)=P(a，b)old+[1-P(a，b)old]MS(a)(7)

2)衰减。当两节点在一段时间内，相遇次数减少甚至无相遇，那么他们之间的相遇概率也会降低，由此得到衰减投递概率公式：

3)传递。若节点a、c都能与目的节点b相遇，那节点a便可通过中间节点c将消息传递给目的节点b。那么节点的传递性投递概率公式为：

P(a，c)=P(a，c)old+[1-P(a，c)old]

P(a，b)P(b，c)ρa，c(9)

3.3 路由算法

3.3.1 消息转发流程

路由算法的步骤及流程如图2所示。

图2 路由算法流程

3.3.2 ACK删除机制

由于冗余的消息副本在网络长时间保留会占用节点宝贵的缓存空间，并影响新消息的转发和投递。然而矿井下的数据十分重要，过满的缓存空间会导致重要数据丢失，甚至关乎到工人的生命安全，因此设计一个合理的缓存管理十分重要。本文将添加 ACK 删除机制来删除冗余副本和已经成功传递的消息。每个节点都有自己的列表，当消息成功传输到目的节点时，该消息就被标上投递成功的标记，在与其他节点相遇交换信息列表时，可获取相关信息，从而删除缓存的已送达的副本。

3.3.3 社区间消息转发示例

节点A携带有消息M1、M3、M5、M7，节点B携带有消息M2、M3、M4、M6，每条消息都有各自的目标节点；其中节点A携带的消息M1的目标节点是节点B，节点B携带的消息M4目标节点是节点A。在相遇前节点A和节点B各自的消息列表如图3所示。

图3 节点A和节点B相遇前

节点A和B相遇后消息列表如图4所示，节点A将消息M1传递给节点B，节点A删除该条消息，节点B对M1标记，表示投递完成。同理，消息M4更新投递概率，判断是否还有消息需要转发。

图4 节点A和节点B相遇后

其中，节点A携带消息M5的目的节点是节点F，节点A和节点B相遇，节点B并非消息M5的目的节点，但是节点B对节点F的预测投递概率大于节点A对节点F的预测投递概率，所以节点A将消息转发给节点B。由于节点B的缓存空间已满，所以删除节点B消息列表里跳数最大的消息M6，空出缓存空间，从而节点A携带的消息M5成功被转发到节点B，并且节点A和节点B对消息M5的跳数增加。

4 仿真实验及结果分析

4.1 仿真环境

本算法在One平台模拟矿井机会路由仿真，采用MRM移动模型，仿真节点模拟煤矿井下主要移动节点：矿工、矿车和无线基站固定，选取经典算法Epidemic算法、Porphet算法、Sprad and Wait算法和本文算法，从节点数量和节点缓存对投递成功率、平均传输延时、网络负载和平均剩余能量四个维度进行性能评估。实验的仿真参数见表1。

表1 仿真节点参数设置

4.2 不同节点缓存下的性能评估

四种算法的性能评估分别如图5—图8所示，从图中可以看出本文提出的算法在投递成功率、网络负载和平均跳数上表现均较为优异，从而表明本算法在井下机会网络中有一定的优势作用。

图5 不同节点缓存下的投递成功率

从图5中可以看到在节点缓存不同时，本算法在投递成功率比Epidemic算法提高了26%，比Porphet算法提高了18%～21%，比Sprad and Wait算法提高了5%～10%。当节点的缓存空间增大时，四种算法的投递成功率都随之增大，这是因为传送的消息不用因为缓存空间不足被删去或者选择其他的节点暂存，从而提高了投递成功率。

图6、图7的仿真结果展示了在缓存空间增大的情况下，四种算法在平均传输延时和网络负载方面表现出相同的趋势，且本算法在两方面表现优良。这是由于其他三种算法在传输过程中不断增加副本，而本文算法中引入了ACK删除机制，删除冗余副本，从而降低网络负载和平均传输延时。

图6 不同节点缓存下的平均传输延时

图7 不同节点缓存下的网络负载

图8表明，本文算法在节点缓存空间不断增大时，平均跳数仍较为稳定，这是因为本文算法通过添加ACK删除机制删除网络中的消息副本，节点缓存空间的大小对平均跳数几乎没有影响。

图8 不同节点缓存下的平均跳数

4.3 不同消息生存时间下的性能评估

下面描述了四种算法在不消息生存周期不断增加的情况下的性能表现分别如图9—图12所示。

图9 不同消息生存周期下的投递成功率

图9仿真结果表明，在消息生存周期增加的情况下，本算法的投递成功率保持良好，甚至有所提高。这是因为消息在网络中存活时间越长，相应地，能被投递到合适地目标节点的概率越大。

从图10的仿真结果可以看出，在消息生存周期增加时，平均延时大幅度增加，这是由于消息生存时间过长，一定程度上使得网络中存在的冗余消息过多，增加了网络负载，使得网络处理消息的速度降低，从而平均传输时延增加。

图10 不同消息生存周期下的平均传输时延

图11、图12的仿真结果表明本算法在生存周期增加的条件下，在网络负载和平均跳数上仍表现不错。这是由于本算法结合了移动轨迹相似度和节点相遇持续时间，使得节点在移动过程中能够选择更合适的中继节点，并且增加的ACK删除机制，从而在消息生存时间不变的情况下，提高消息的投递成功率，降低网络负载和减少平均跳数。

图11 不同节消息生存周期下的网络负载

图12 不同消息生存周期下的平均跳数

5 结 语

根据矿井下机会网络通信中节点的移动规律性、节点之间的相关性，提出基于消息效用的煤矿井下概率路由算法，将节点活动范围分成不同社区，根据社区内和社区间节点的移动特点，选择不同的消息转发策略，减少消息在网络中的盲目传递，更快更准确地将消息传递给目的节点。针对消息在传递过程中不断增加副本问题，添加了ACK删除机制，有效减少了网络负载和冗余消息。One平台仿真实验证明，本算法更具针对性，对于煤矿井下的场景更为适用，但仍存在不足，如网络延时上并没有得到较好的改善，仍有优化空间。