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

145引用格Vol.55,No.7COALENGINEERING第55卷第7 期程炭煤doi:10.11799/ce202307024基于消息效用的煤矿井下概率路由算法研究杨萍，李敬兆，张小波，吕乐3，唐俊1（1.安徽理工大学电气与信息工程学院，安徽淮南232001；2.中国科学技术大学，安徽合肥231600;3.陕西延长石油榆林煤化有限公司，陕西榆林719000)摘要：由于深部矿井地下空间环境复杂，通信传输过程中时常出现传输中断、传输延时高等情况。为解决该问题，需增加大量节点，使得通信传输成本增加。因此，在现有条件下，根据矿井人员的社会性提出一种基于消息效用的煤矿井下概率路由算法。首先，基于井下节点的移动特点定义移动轨迹相似度、节点相遇持续时间和节点相似度；其次，根据井下工作节点的社会性对其分类为不同社区，社区内外采用不同的消息转发策略，提高传输效率；最后，通过添加ACK删除机制限制网络允余副本，有效避免了网络拥塞。在One平台上的仿真结果表明，该算法在通信环境较差的矿井场景下可以在降低网络延时的前提下，提高消息投递成功率。关键词：机会网络；相遇概率；移动轨迹；路由算法中图分类号：TD67；T P393文献标识码：A文章编号：16 7 1-0 9 59(2 0 2 3)0 7-0 145-0 6Probabilistic routirgorithm in coal mine based on message utilityYANG Ping,LI Jingzhao,ZHANG Xiaobo,LYU Le,TANG Jun(1.School of Electrical and Information Engineering,Anhui University of Science and Technology,Huainan 232001,China;2.University of Science and Technology of China,Hefei 231600,China;3.Shaanxi Yanchang Petroleum Yulin Coal Chemical Co.,Ltd.,Yulin 719000,China)Abstract:Due to the complex underground space environment in deep mines,transmission interruption and high transmissiondelay often happen in the communication transmission.To solve it,a large number of nodes need to be added which increasesthe communication transmission cost.We proposed a probabilistic routing algorithm based on message utility in coal mine.Under the existing conditions,the sociality of people is used to assist in decision-making transmission strategies.Firstly,basedon the movement characteristics of underground nodes,the movement track similarity,node encounter duration and nodesimilarity are defined;secondly,the underground work nodes are classified into different communities according to theirsociality,and different message forwarding strategies are used inside and outside the communities to improve transmissionefficiency;Finally,by adding an ACK deletion mechanism to limit network redundant copies,network congestion is effectivelyavoided.The simulation results on the One platform show that the algorithm can improve the success rate of message deliveryand reducing the network delay in the mine scenario with poor communication environment.Keywords:opportunity network;encounter probability;mobile model;routing algorithm煤炭作为科技发展的重要工业能源，煤炭工业为我国经济发展提供了重要支持。然而，由于煤矿井下空间异构、环境恶劣，导致瓦斯事故、机电故障等时常发生。因此，需要对矿井进行全覆盖、不间断的安全监测。但是矿井有线通信部署困难，成本较高；无线信号衰减快，存在视野盲区。在这种情况下，机会网络被引入到矿井通信系统中。机会网络（OPportunisticNETwork）是一种不需要进行网络部署，对基础设备要求不高的移动自组织网络 2.3】，常应用在车载网络、灾难应急、野外数据收集等领域 4-6 。机会网络是通过移动节点间的相遇带来的通信机会进行数据的传输 7 ，所采用的路收稿日期：2 0 2 2-10-12基金项目：国家自然科学基金项目（518 7 40 10）；物联网关键技术研究创新团队（2 0 1950 ZX003）作者简介：杨萍（1999），女，安徽池州人，硕士，主要研究方向为物联网和网络通信，E-mail：2 8 2 36 52 98 6 q q.c o m。通讯作者：李敬兆（196 4），男，安徽准南人，博士，教授，主要研究方向为智能控制，E-mail：2 546 6 2 58 3 q q.c o m。式：杨萍，李敬兆，张小波，等基于消息效用的煤矿井下概率路由算法研究J煤炭工程，2 0 2 3，55（7）145-150.1462023年第7 期研究探讨程炭煤由机制是“存储一携带一转发”，在中继节点上缓存信息，遇到其他节点时进行信息转发，直到信息到达目的节点 8 。一般地，机会网络中的节点是由人携带的便携性通信终端构成 9，具有移动性强、网络连接间歇性 10 1和网络延时大的特点。因此，在矿井实际应用场景中，携带通信设备的矿工和车辆可视为移动节点，通过日常工作活动和交流，使得节点相遇，从而实现数据传输。因为人是具有社会性的，根据工作任务来进行活动，相应地，节点也具有一定的社会性，节点移动的随机性减小 。针对以上实际特点，本文提出一种基于消息效用的煤矿井下概率路由算法，根据节点的聚散程度划分为不同社区 12】，并依据社区内外节点的社会性，设计不同的路由机制，使得消息投递成功率提高、网络延时降低；并建立缓存管理机制，合理管控节点缓存空间 13，减少网络中的允余消息。1文献综述机会网络是依靠节点的移动传递消息，这便决定了网络延时较高、投递成功率低等特性，为解决这个问题，一般从缓存管理策略和路由策略两大方面解决机会网络消息传递过程出现的问题文献 14 针对矿井环境和矿工移动特点分区建立马尔可夫模型，通过综合开考虑计算出终端网络时延、与目的节点相遇概率和扩散范围，最后选择最合适消息转发策略，实现分组低延时转发。但是在终端活跃度差异不大，活动范围较大的情况下，不能良好地模拟出矿井的实际情况，并且没有考虑缓存空间和网络中的穴余副本，造成网络负担较大。文献 15 以消息传递概率作为消息转发依据，先后计算当前一跳和二跳节点的消息传输概率；将二跳节点的消息传输概率与一跳节点的消息传输概率比较，若一跳节点的消息传输概率大于二跳节点，优先选择一跳节点中消息传递概率大的节点传输消息；若都不是，则将消息存于缓存区。该算法减少了网络中的消息副本，并提高了消息投递成功率，但是算法复杂，使得网络延时增加。文献 16 提出了基于运动相似性的机会网络缓存管理策略，首先定义并计算节点的消息扩散程度和运动相似性，从而得出消息转发效用值和存储效用值；其次，依据消息转发效用值来选择合适的节点转发消息，当缓存空间溢出时，优先丢弃存储效用值较低的消息。该算法将节点运动相似性和缓存空间作为消息转发概率影响因素，有效减少节点的盲目携带，降低了网络负载，但是没有考虑节点相遇持续时间对节点消息转发的影响，该算法的消息投递成功率有待提高。文献 17 通过收集节点的历史接触信息，包括节点的相遇时间、相遇次数和节点关系稳定度，以此计算节点转发效用值；然后，在通信范围内选择消息转发效用值最大的节点转发消息；最后，根据余弦相似度选择下一节点转发消息。该算法使得转发节点最大程度均匀分布，但是容易导致消息重复扩散，并且对于活跃度大，消息转发概率高的节点利用率不高。本文根据井下移动节点移动规律和节点间的社会性，对节点移动范围进行分区，根据社区内外的节点移动属性选择不同的路由传输策略。通过加入节点的相遇持续时间、移动轨迹相似度等相关因素，形象模拟了井下节点的移动特征，有效地提高了消息投递成功率，并大幅度降低了消息延时和网络负载。2网络模型及定义2.1矿井机会网络模型煤矿井下通信信号差，巷道中节点间的通信链路间歇性连接甚至不连接，因此通过增加矿工和矿车携带的移动通信设备，从而增强井下的通信交流。矿工或矿车表示移动节点，因此节点间具有一定的社会关系，并保持相对稳定。节点间的密切程度与工作内容相关【18 ，因此煤矿井下的节点间可形成一种隐形的工作关系网络，这种关系网络表示了节点间因工作而产生的联系程度，定义网络的节点集合V=lui,U2，,n，节点之间的关系连接集合E(（,b）I,beV），那么可以得到加权无向图：G=(V,E,p)(1)式中，Pa.表示节点和节点b的关联性，数值越大，表示节点和节点b之间相遇频率越高、密切程度越高；若（a,b）E，那么pa,6=0，即节点和节点b之间无交集；Pa.60，1，根据工作安排调整参数。在社区内部，节点密度较高，联系频繁，而处于不同社区的节点联系的频率相对较低。因此，将网络按照节点密度划分为不同的社区。井下矿工和矿车的往往遵循相同的移动规律，他们会根据自已的工作任务在固定的巷道中移动，行驶相同的移动轨迹，因此本文选用基于地图的固定路线的MRM（M a p Ro u t e M o v e me n t）作为移动模1472023年第7 期程炭研究探讨煤型 19，用其来模拟矿车和矿工在井下工作的移动规律。矿井机会网络的应用场景如图1所示。矿区IP网络远程调度中心地面井下国工业以太网交换机无线接入点矿工分支巷矿车工作面口工作面日口待采区工作面日图1矿井机会网络应用场景2.2相关定义1）定义1：节点相遇持续时间。井下移动节点的工作活动往往表现出周期性的规律，并且，节点间的关系随着移动过程中与其他节点频繁建立连接而加强。节点在移动过程中可以和一个节点建立多次通信或者和多个节点建立通信，每次的通信时间都不相同，若节点间的通信次数越多，通信时间越长，表明节点间的关联性越强。那么用通信时长表示节点间的关系程度，设计在时间T内，节点和节点b间建立通信n次，通信时间集合为(t,t2，t，那么节点的相遇持续时间公式为：Pa.b=Tab/T=(ti+t2+.+tn)/T(2)式中，Ta。表示节点与节点b相遇持续时间总和。2）定义2：节点移动轨迹相似度。煤矿井下的矿工和矿车的每天工作几乎无异，因此它们的移动轨迹往往有着高度重合性，通过比较矿工当前的移动轨迹和历史移动轨迹，衡量该节点历史移动轨迹信息的可用性，以节点的移动轨迹去辅助预测节点的相遇概率，在时间T内，取个轨迹点。节点i的历史轨迹按照时间顺序由轨迹点组成，历史移动轨迹为IP1,P2，Pm，当前的移动轨迹为q1,92，9，则节点i移动轨迹相似度计算公式：1mMS(i)=match(pk,qk)(3）mK=1其中，匹配函数：(1Idl8match(Pk,qk)=(4)其他式中，d|为两轨迹点间的距离；为当前和历史节点移动轨迹点间的误差，可根据节点移动速度适当调整。当两轨迹点之间的距离少于等于时，match函数取值为1，表示节点历史移动轨迹与当前移动轨迹重合度较高，具有较高的可信度。否则match函数取值为0。3）定义3：节点相似度。节点和节点b的相似率是指节点与节点6 拥有的共同相遇节点个数与它们两个节点分别相遇的节点总数的比值。INnSim(a,b)=(5)N.UN.a式中，N。表示在时间T内节点所相遇的节点；N，表示在时间T内节点b所相遇的节点3基于消息效用的煤矿井下概率路由算法根据煤矿井下工作内容的不同将节点活动分为两类：工作活动限制在一个范围内，定义为社区内；在不同的工作区域活动，定义为社区间。3.1社区内消息效用值转发策略同一个区域内矿工的工作内容和范围相同，对于社区内的消息传递概率也大致相同，优先选择节点中缓存空间、活跃度高的节点，消息投递的成功率也更大。用消息转发效用值作为判断依据，节点选择消息转发效用值最大的进行数据的转发。TIN,BfreeP(6)uility(i）TNBtotal其中，T,为节点i在时间T内与其他节点相遇持续时间总和；N，为节点i在时间T内相遇节点个数，N表示总节点个数；Bre为节点剩余缓存空间；Brotal为节点总缓存空间。3.2社区间移动轨迹辅助决策消息转发策略节点的移动轨迹和历史移动轨迹重合度越高，则节点历史信息的可信度越高。利用节点移动轨迹相似度辅助相遇概率的预测，相遇概率的计算分为更新、衰退、和传递三个部分。1）更新。当社区间的两节点相遇时，用一下公式更新投递概率：P(a,b)=P(a,b)old+1-P(a,b)oldMS(a)（7)2）衰减。当两节点在一段时间内，相遇次数减少甚至无相遇，那么他们之间的相遇概率也会降低，由此得到衰减投递概率公式：P(a.b)=P(a,b)a-T.(8)1482023年第7 期研究探讨程炭煤3）传递。若节点、c 都能与目的节点b相遇，那节点便可通过中间节点c将消息传递给目的节点b。那么节点的传递性投递概率公式为：P(a,c)=P(a,c)old+1-P(a,c)laP(a,b)P(b,c)pa.c(9)3.3路由算法3.3.1消息转发流程路由算法的步骤及流程如图2 所示。开始节点相遇交换信息更新预测概率更新消息转发效用值结束相遇节点Y加入发送队列为目的节点NY节点是否属子YPutility,(b)Putliy(a）同一社区NNNYp(b)p(a)图2路由算法流程3.3.2ACK删除机制由于穴余的消息副本在网络长时间保留会占用节点宝贵的缓存空间，并影响新消息的转发和投递。然而矿井下的数据十分重要，过满的缓存空间会导致重要数据丢失，甚至关乎到工人的生命安全，因此设计一个合理的缓存管理十分重要。本文将添加ACK删除机制来删除余副本和已经成功传递的消息。每个节点都有自已的列表，当消息成功传输到目的节点时，该消息就被标上投递成功的标记，在与其他节点相遇交换信息列表时，可获取相关信息，从而删除缓存的已送达的副本3.3.3社区间消息转发示例节点A携带有消息M1、M 3、M 5、M 7，节点B携带有消息M2、M 3、M 4、M 6，每条消息都有各自的目标节点；其中节点A携带的消息M1的目标节点是节点B，节点B携带的消息M4目标节点是节点A。在相遇前节点A和节点B各自的消息列表如图3所示。节点A和B相遇后消息列表如图4所示，节点A将消息M1传递给节点B，节点A删除该条消息，节点B对M1标记，表示投递完成。同理，消息M4更新投递概率，判断是否还有消息需要转发。AB消息IDM1M3M5M7消息IDM2M3M4M6目标节点BEFC目标节点DEAC跳数0121跳数2115投递概率预测BC DEF投递概率预测AC DEFP(A.O)0.80.50.70.50.4P(B,O)0.90.50.80.70.8图3节点A和节点B相遇前AB1一消息IDM3M5M7M4消息DM2M3M1M5目标节点EFCV目标节点DEF跳数1 31跳数2 13投递概率预测BCDEF投递概率预测ACDEFP(A,O)0.80.50.70.50.4P(B,O)0.90.50.80.70.6图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 andWait算法和本文算法，从节点数量和节点缓存对投递成功率、平均传输延时、网络负载和平均剩余能量四个维度进行性能评估。实验的仿真参数见表1。表1仿真节点参数设置参数名取值仿真区域/m4500 x3400仿真时间/h12节点移速/(ms)0,0.51.5,45消息传输速率/kbps2001024消息大小/kB200,500消息产生间隔/s30消息生存周期/min200149灰2023年第7 期程研究探讨煤4.2不同节点缓存下的性能评估四种算法的性能评估分别如图5一图8 所示，从图中可以看出本文提出的算法在投递成功率、网络负载和平均跳数上表现均较为优异，从而表明本算法在井下机会网络中有一定的优势作用。从图5中可以看到在节点缓存不同时，本算法在投递成功率比Epidemic算法提高了2 6%，比Porphet算法提高了18%2 1%，比Sprad andWait算法提高了5%10%。当节点的缓存空间增大时，四种算法的投递成功率都随之增大，这是因为传送的消息不用因为缓存空间不足被删去或者选择其他的节点暂存，从而提高了投递成功率0.90.8%/率0.70.60.5-.-Epidmic0.4-Prophet0.3-Sprad and Wait一*-本算法0.2515.202530354045501010节点缓存空间/MB图5不同节点缓存下的投递成功率图6、图7 的仿真结果展示了在缓存空间增大的情况下，四种算法在平均传输延时和网络负载方面表现出相同的趋势，且本算法在两方面表现优良这是由于其他三种算法在传输过程中不断增加副本，而本文算法中引人了ACK删除机制，删除穴余副本，从而降低网络负载和平均传输延时。6000-o-Epidmic5500-v-Prophet上-SpradandWait5000一*-本算法450040003500300025005-0101520253035404550节点缓存空间/MB图6不同节点缓存下的平均传输延时图8 表明，本文算法在节点缓存空间不断增大时，平均跳数仍较为稳定，这是因为本文算法通过添加ACK删除机制删除网络中的消息副本，节点缓存空间的大小对平均跳数几乎没有影响4.3不同消息生存时间下的性能评估下面描述了四种算法在不消息生存周期不断增200-o-Epidmic175-*-Prophet-Sprad and Wait150一*-本算法125100755025-1051015202530355404550节点缓存空间/MB图7不同节点缓存下的网络负载6.0-.-Epidmic5.5-v-Prophet5.0-Sprad and Wait-*-本算法4.54.03.53.02.52.0105101520253035404550节点缓存空间/MB图8不同节点缓存下的平均跳数加的情况下的性能表现分别如图9一图12 所示，图9仿真结果表明，在消息生存周期增加的情况下，本算法的投递成功率保持良好，甚至有所提高。这是因为消息在网络中存活时间越长，相应地，能被投递到合适地目标节点的概率越大。0.90-.-Epidmic-Prophet0.85上-Sprad andWait0.80一*-本算法%率0.750.700.650.600.550.5050100150200250300消息生存周期/min图9不同消息生存周期下的投递成功率50004500S/轮400035003000-Epidmic2500-Prophet-SpradandWait2000本算法50100150200250 300消息生存周期/min图10不同消息生存周期下的平均传输时延从图10 的仿真结果可以看出，在消息生存周期150赵巧芝）责任编辑2023年第7 期研究探讨程炭煤增加时，平均延时大幅度增加，这是由于消息生存时间过长，一定程度上使得网络中存在的允余消息过多，增加了网络负载，使得网络处理消息的速度降低，从而平均传输时延增加。图11、图12 的仿真结果表明本算法在生存周期增加的条件下，在网络负载和平均跳数上仍表现不错。这是由于本算法结合了移动轨迹相似度和节点相遇持续时间，使得节点在移动过程中能够选择更合适的中继节点，并且增加的ACK删除机制，从而在消息生存时间不变的情况下，提高消息的投递成功率，降低网络负载和减少平均跳数。200180160140120-.-Epidmic100-Prophet80-Sprad andWait一*-本算法60402050100150200250300消息生存周期/min图11不同节消息生存周期下的网络负载6.0.-Epidmic5.5-v-Prophet-Sprad and Wait5.0-*-本算法4.54.03.53.02.550100150200250300消息生存周期/min图12不同消息生存周期下的平均跳数5结语根据矿井下机会网络通信中节点的移动规律性、节点之间的相关性，提出基于消息效用的煤矿井下概率路由算法，将节点活动范围分成不同社区，根据社区内和社区间节点的移动特点，选择不同的消息转发策略，减少消息在网络中的盲目传递，更快更准确地将消息传递给目的节点。针对消息在传递过程中不断增加副本问题，添加了ACK删除机制，有效减少了网络负载和允余消息。One平台仿真实验证明，本算法更具针对性，对于煤矿井下的场景更为适用，但仍存在不足，如网络延时上并没有得到较好的改善，仍有优化空间参考文献：1贾升煜。矿井机会网络路由算法与缓存管理策略研究【D.徐州：中国矿业大学，2 0 2 0.2刘慧，张振宇，杨文忠，等机会网络中基于陌生人的转发算法J计算机工程与设计，2 0 17，38（4）：36-43.3崔建群，吴淑庆，常亚楠，等机会网络中基于节点相似率的概率路由算法J小型微型计算机系统，2 0 2 1，42(3):609-614.4彭碧涛接触概率和数据分组新鲜度感知的机会网络路由算法J小型微型计算机系统，2 0 17，38（7)：1459-146 3.5刘名阳，陈志刚，吴嘉。机会网络中计算节点间数据分组余弦相似度的高效转发策略J小型微型计算机系统，2019,40(1):104-110.6余翔，刘志红，闫冰冰基于社交关系的移动机会网络路由算法简J计算机工程，2 0 17，43（12）：19-2 0.7张棋飞，桂超，宋莺，等基于节点运动的机会网络路由算法J软件学报，2 0 2 1，32（8）：2 597-2 6 12.8葛宇，梁静基于相遇概率时效性和重复扩散感知的机会网络消息转发算法J计算机应用，2 0 2 0，40（5）：1397-1402.9张峰机会网络中基于节点相遇间隔的缓存管理策略J计算机科学，2 0 19，46(5)：57-6 1.10周春月，庞迪基于节点属性和缓存管理的机会网络路由算法J北京交通大学学报，2 0 2 1，45(2)：7 1-7 9.11林玉成，陈志刚，吴嘉机会网络中计算节点间相似度的路由算法J小型微型计算机系统，2 0 18，39(8）：17 59-17 6 4.12刘慧，张振宇，杨文忠，等机会网络中基于节点社会属性的转发算法J计算机工程与应用，2 0 17，53（2 2）：92-96,115.13崔苑茹，李鹏，刘宏，等基于校园机会网络的协作小组缓存调度策略 J电子学报，2 0 2 1，49(12)：2 399-2 40 6.14邹艳芳，于宏毅，李青，等基于终端属性的矿下机会网络分组转发协议 J计算机应用研究，2 0 17，34(1)：51-56.15薄，乔林，王丹妮，等基于转发概率的时延容忍网络路由 J中国电子科学研究院学报，2 0 19，14（8)：7 8 1-785,797.16张力，陈滢生，王言通基于运动相似性的机会网络缓存管理策略J计算机工程与设计，2 0 18，39（8）：36-40.17朱坤，刘林峰，吴家皋。一种基于节点位置余弦相似度的机会网络转发算法J计算机科学，2 0 18，45（12）：6 1-65,85.18高媛，王淑敏，孙建飞基于用户兴趣相似性的节点移动模型J计算机应用，2 0 15，35（9）：2 457-2 46 0.19朱孝顺。面向矿井安全监测的机会网络路由算法研究【D徐州：中国矿业大学，2 0 2 1.