矿山环境下基于Ad Hoc网络的多路径QoS路由算法

闫帅领， 张蕾

(衡水学院 数学与计算机学院， 河北 衡水 053000)

0 引言

在复杂的矿山环境中数据安全、可靠传输困难。目前，针对数据传输已开展很多研究。文献[1]将数据先传递到数据中心，再通过数据中心分发。文献[2]以C/S(Client-Server，服务器-客户机)工作模式搭建数据传输架构，利用专用线路传输图像数据。文献[3-5]引入云计算以遏制无线数据传输对环境的依赖，确保数据传输的可靠性。文献[6]借鉴AODV(Ad Hoc On-Demand Distance Vector Routing，无线自组网按需平面距离向量路由)协议的思想，通过无线传感器网络转发实现数据传输。文献[7]通过分组头压缩的改进型DSR(Dynamic Source Routing，动态源路由)算法优化无线网移动通信数据传输性能。然而，文献[1-2]为有线数据传输，在矿山特殊环境下不易铺设线路且施工费用高，另外受天气影响线路容易产生破坏，导致数据传输失败。文献[3-5]通过云计算势必会增加数据处理时间，影响数据传输的实时性。文献[6-7]基于简单协议生成的路由算法更适用于矿山环境，但文献[6]未考虑数据传输过程中中间节点破坏的情况，文献[7]以最短路径作为路由选择标准，均未解决数据传输的准确性问题。因此，本文提出了一种矿山环境下基于Ad Hoc网络的多路径QoS路由算法(Multipath QoS Routing Algorithm，MQRA)。该算法在路由建立过程中引入区块链，可防止数据被篡改；通过QoS约束得到多条可用路径，再根据不同级别标准寻找数据传输主路径和备选路径，可避免数据丢失。

1 算法原理

1.1 QoS相关参数定义

(1) 路由路径带宽。路由路径带宽是指整个路由路径中所有相邻节点的最小带宽。

B=min{Bij}

(1)

式中：B为路由路径带宽；Bij为路由中相邻节点i，j(i，j=1，2，…，n，n为网络中节点数，i≠j)之间的通信链路带宽。

(2) 路径时间延迟。数据包从源节点到达目的节点所需时间为路径时间延迟。令网络中所有节点具有相同的处理能力和信道带宽，且所用的无线信道是对称的，路由请求探测包、目的节点的响应包及数据包的大小相等，则路径时间延迟为

T=Tpro+Ttra

(2)

Tpro=Tw+Te

(3)

式中：Tpro为节点转发数据包的时间；Ttra为节点之间传输数据包所用时间；Tw为数据包在队列中的等待处理时间；Te为数据包的实际处理时间。

由于数据包在队列中的等待处理时间很短，可忽略不计,所以根据式(2)和式(3)可得

T=Te+Ttra

(4)

(3) 路径生存活力。路径生存活力是指路径中节点最小存活时间。

E=min{Ei}

(5)

(6)

式中：E为路径生存活力；Ei为路径中节点i存活时间；θ为节点能源；ω为节点连通度；α为节点存活的平衡因子。

(4)路径生存能力。路径生存能力反映了路径的可用性，主要由路由路径带宽、路径时间延迟和路径生存活力决定。

(7)

1.2 路由建立

矿山环境下的路由建立是一种由源节点发起的通过中间转发设备到达目的节点的过程。首先将源节点、中间节点及目的节点封装为独立的区块，然后利用请求/应答方式将各个区块进行有效连接，最后形成1条由源节点到目的节点的区块链。路由建立具体步骤如下。

(1) 节点通过周期性地向邻居节点广播探测包EERQ而逐渐形成稳定的区块，如图1所示。Pre-point为上一节点地址，由于源节点为创世节点而不存在上一节点，所以源节点的Pre-point设置为null；Merkle tree保存源节点的邻居节点；ID为本节点地址。

图1 区块创建Fig.1 Block creation

(2) 源节点向邻居节点发送EERQ(含无限大初始路径生存活力)，并设置有效时间域τ。当传输过程中EERQ的时间延迟Tζ大于τ，则EERQ将由于寻找路径的时间延迟过长而失效。

(3) 邻居节点收到EERQ后，开启处理数据包定时器并检查是否为初次收到该包，若是则回复正常确认包CEERP(主要包含EERQ的时间延迟Tζ和路由路径带宽B)并提出节点上链要求，否则转步骤(5)。

(4) 节点收到邻居节点的正常确认包CEERP后，检查Tζ是否大于τ，若是则丢弃CEERP，否则判断邻居节点的路由路径带宽B是否在常规区间，若是则同意邻居节点上链，否则拒绝邻居节点上链,并对邻居节点的可疑性进行定时检测。

(5) 邻居节点根据自身记忆路由表中的存储容量标志Isfull决定是否转发EERQ，当Isfull为0时丢弃EERQ，路由查找失败，否则转步骤(6)。

(6) 邻居节点根据式(6)计算自身的存活时间Ei，并将计算结果同探测包EERQ中的路径生存活力E进行比较，如果Ei

W=ω-ωHd+1,Hd

(8) 判断邻居节点是否为目的节点，若是转步骤(9)，否则向邻居节点转发EERQ，并转步骤(3)。

(9) 目的节点按照区块链路径向源节点传输公钥信息，源节点通过目的节点的公钥对所需传输信息进行加密。

路由查找成功后，源节点区块内保存了所有源节点到目的节点的节点检索过程。假设源节点为S，目的节点为D，节点2和节点6为恶意节点，节点4和节点8为不满足QoS约束条件节点，源节点区块如图2所示。

图2 源节点区块Fig.2 Block of source node

由图2可知，在恶意节点和不满足QoS约束条件节点处将不再进行路径探测，即节点2、节点4、节点6和节点8均失去了区块链的连接。最终得到3条可用路径，分别为R1：S—1—7—11—D，R2：S—1—7—12—13—D和R3：S—3—9—14—D。将这3条路径以到达的先后次序记录在源节点的记忆路由表中，计算中间节点的相关性数值，见表1。

表1 多路径中间节点的相关性数值Table 1 Correlation value of intermediate nodes in multipath

以中间节点的相关性数值之和作为第一路径选择标准，相关性数值之和越小，表明路径相关性越小。以路径长度作为第二路径选择标准，路径越短，链路越稳定，网络的控制开销越小。以路径形成先后顺序为第三路径选择标准，越早形成的路径对应的时间延迟越小。R1路径最先形成且需要经过3个中间节点；R2路径在R1路径之后形成，R2路径中存在4个中间节点且前2个与R1重复(重复则相关性数值加1)；最后形成的R3路径与R1，R2路径的中间节点均不相同。因此选择路径相关性小、链路稳定、时间延迟小的R1，R3作为路由路径，其中R1为数据传输主路径，R3为数据传输备选路径。

1.3 路由维护

在矿山环境下使用Ad Hoc网络对信息传输尽管有多条QoS路径保证[8-10]，但仍可能由于中间节点移动、带宽不足、传输超时等原因使链路连接失败[11-14]。因此，本文主要从3个方面对路由进行维护：① 由于在初次路由查找过程中采用了区块链思想，所以每个中间节点均保留其邻居节点的信息，可通过查询路径出现断裂处的上一个节点的路由表，使用相邻节点替代，进而恢复路由。② 备选路径并不是在主路径失效后启用，而是在主路径的可靠性评估下降到一定程度后即可启用。③ 在源节点处重新发起路由查找。

2 算法仿真

2.1 仿真参数设置

采用NS-3网络模拟矿山环境，从误码率和路径生存能力2个方面对MQRA与经典的AODV算法和DSR算法进行对比。设置节点数为10～100个，随机分布在1 000 m×1 000 m范围内，节点通信范围为50 m，节点移动速度为0～16 m/s，数据包发送速率为0～35个/s，仿真时间为900 s。模拟矿山网络中存在至少1个女巫攻击节点，当节点数达30个后加入1个能源受限节点、达40个后加入1个黑洞节点、达50个后加入1个DoS攻击节点。

2.2 仿真结果分析

在固定节点移动速度(10 m/s)的条件下，数据传输误码率随网络中节点数变化情况如图3所示。可看出MQRA下误码率随着节点数增多先增大后平缓减小。这主要是由于随着节点数增多，网络中恶意节点增加，而区块链在构建时会出现控制包受到攻击而失效的情况，所以误码率偏大；一旦区块链网络形成，数据传输进入稳定时期，数据将会得到较好的保护，出现的误码主要来源于对最初探测包的攻击，因此误码率持续减小。AODV，DSR算法由于未对传输的数据包进行保护，所以整体上随着恶意节点增多，会引起较多的数据包丢失，造成误码率增大。

图3 误码率随节点数变化情况Fig.3 Bit error rate variation with the number of nodes

网络中存在50个常规节点和4个恶意节点的条件下，误码率随数据包发送速率变化情况如图4所示。可看出MQRA下误码率随着数据包发送速率提高呈逐渐减小趋势。主要原因为在最初的路由建立过程中，数据进行了区块封装操作，而在该过程中当数据包发送速率较慢则会出现较多的控制包被攻击而丢失的情况；随着数据包发送速率提高，区块链的校验功能变得完备，对数据包的保护能力提高，误码率不断减小。AODV，DSR算法下误码率最初由于数据包发送速率较慢出现了短暂减小，主要是由于恶意节点此时并未开始对数据包进行碰撞攻击，但当数据包发送速率较高时，传输的数据包必然会遭遇恶意节点攻击，且没有数据防护措施，造成误码率增大。

误码率随节点移动速度变化情况如图5所示。可看出MQRA下误码率随着节点移动速度增大先增大再减小，主要原因在于节点移动速度较小时出现了2条路径同时断裂的情况，造成较多数据包丢失，而之后随着节点移动速度增大，可快速恢复2条到达目的节点的路径。AODV，DSR算法下误码率明显偏大，主要因为数据包在传输过程中受路径断裂及恶意节点攻击影响而大量丢失，并且随着节点移动速度越大，数据包丢失越严重。

图4 误码率随数据包发送速率变化情况Fig.4 Bit error rate variation with packet transmission rate

图5 误码率随节点移动速度变化情况Fig.5 Bit error rate variation with node movement speed

路径生存能力随节点数变化情况如图6所示。可看出MQRA下路径生存能力随着节点数增多呈上升趋势，表明节点数越多，矿山数据传输越可靠，主要是由于节点数增多更利于形成区块链且不易断裂。AODV，DSR算法下路径生存能力随着节点数增多呈下降趋势，主要是由于较为密集的节点数会使主路径不断更新，进而影响数据传输的可靠性。

图6 路径生存能力随节点数变化情况Fig.6 Path viability variation with the number of nodes

路径生存能力随数据包发送速率变化情况如图7所示。可看出3种算法下路径生存能力随着数据包发送速率增加均有所下降，这是由于较快的数据包发送速率导致数据包传输不及时。但MQRA下路径生存能力与AODV，DSR算法下相比下降较为缓慢，主要原因在于区块链的使用确保了路径的可持续性，在路径建立初期便排除了可能出问题的节点。

图7 路径生存能力随数据包发送速率变化情况Fig.7 Path viability variation with packet transmission rate

3 结语

MQRA引入了区块链思想:首先对节点进行区块化封装，使各节点利用Merkle tree维护其邻居节点；然后根据邻居节点的时间延迟和存活时间更新路径生存活力并进行区块连接；最后依次以中间节点相关性数值之和、路径长度、路径形成先后顺序作为路径选择标准，筛选数据传输主路径和备选路径。仿真结果表明，在不同的节点数、数据包发送速率、节点移动速度情况下，该算法相比AODV，DSR算法具有较低的误码率和较好的路径生存能力，可有效保证数据传输的完整性和准确性。