Ad hoc 网络中基于区块链技术的多路径路由算法研究

闫帅领，程凤林，周林锦，陈晓军，彭玲玲

（衡水学院数学与计算机学院 河北 衡水 053000）

0 引言

传统的Ad hoc 网络是一种动态拓扑网络，网络内的节点即数据的发送者，同时充当着路由器和接受者的角色。 为了在Ad hoc 网络内建立稳定高质量的路由，很多学者进行了一系列的研究，其中楼巧巧和赵知劲等［1］提出的多跳广播算法，综合评价节点信息进而保证了路由综合性能的优越性；李红卫和陈业程［2］考虑远海无人船的环境设计了以最短路径为最优选择的组播路由算法进而保证了数据传输的时效性。 Xin 等［3］提出了一种针对飞行Ad Hoc 网络的多策略路由算法，该算法具有路由毁坏后快速重建的特点。 以上算法在一方面体现了较好的优势，但是都存在一个显著的缺陷。 比如楼巧巧等提出的算法过于追求综合性能而无法保证特定条件下路由的高稳定性和高质量性；李红卫和陈业程［2］提出的算法虽然考虑了环境却忽略了节点的高速移动性，容易造成频繁地更换路由和路由毁坏不可修复的情况；Xin 等［3］提出的算法有较好的稳定性和高质量，但是其对环境针对性太强而无法适合其他场景的推广。 为此，本文提出的基于区块链技术的多路径QoS 路由算法一方面保证了路由的稳定性和高质量，同时也考虑了路由毁坏的修复和重建。

1 Ad hoc 网络区域P2P 模型的建立

Ad hoc 网络区域是指在网络内能够两两相互通信的节点所组成的一个区域，而且Ad hoc 网络中所有节点必须属于一个区域且只能属于一个区域，区域内的所有节点地位平等，即均可与相邻区域内的节点进行通信［4-5］。 初始化Ad hoc 网络，网络内未进入区域的节点间隔（T1）不定时间发起区域请求。 区域的形成有以下几步：

（1）Ad hoc 网络内节点生成随机生成大数据编号，向其邻居节点发出随机生成大数据编号的探测包，并等待邻居节点返回的响应包。

（2）节点收到邻居节点的探测包后，首先检查自己的区域标记，如果已经标记，则忽略该探测包。 否则，返回其响应包并同时标记本节点的区域标记为该大数据编号。

（3）过一个固定周期T2（T2＞T1），节点收到邻居节点返回的响应包，则做标记确认，否则，撤销区域标记。

图1 为区域化的Ad hoc 网络示意图。 在图1 中整个Ad hoc 网络被划分成了4 个区域，分别为区域1、区域2、区域3、区域4，在每一个区域内节点与节点之间均可直接进行通信，且相邻区域内的节点可相互通信。

图1 区域化的Ad hoc 网络

2 基于区块链技术的多路径路由算法

2.1 路径生存活力

节点生存活力是该节点正常情况下的持续工作的时间，该值主要由节点的移动性、连通性和通信距离三个主要因素决定。 用Eid表示，它是通过该节点具有最小的连通度β 和电池消耗剩余α 的计算获得，可以表示为式（1）所示：

式（1）中μ为一个平衡因子，根据节点的移动速度决定，移动速度越快该值就越小，反之越大。 在分母加1 是为了防止节点的β为0 所导致的公式无效情况。β的值为该节点能量覆盖下的节点数量，如图2 所示，A 与B 两个节点在节点C 的能量覆盖下，而节点D、E、F 由于距离原因无法与节点C 进行通信，所以节点C 的连通度β为2。α为节点的原始满能量，随着时间的推移其能量值不断减少，所覆盖的通信半径也在缩小，那么覆盖的节点数随之减少，故变化不大。 所以此值能从一定程度上反映节点的可持续工作时间，进而可以推理出整个路径的生存活力。

图2 节点的连通度例图

路径的生存活力是本路径所能存在的最长时间的参考值E。 E 为路径中节点生存活力最小值，则如式（2）所示：

2.2 QoS 参数计算

路径的生存能力反映了路径的可用性能，生存能力较大的路径更具有优越可用性。 它主要可由时间延时，可用带宽和路径生存活力来决定。 令路径的生存能力为M，则M 可以表示为式（3）所示：

式（3）中γ、ξ、δ为调和系数，τ为路由生存能力的平衡因子，根据路径中数据包的探测情况而自行设定。Bandwidth、T、E分别代表路径的带宽，时间延时和路径生存活力，而Bandwidth_B、T_B、E_B分别表示路径的带宽，时间延时和路径生存活力的估计标准值，该值可根据实际情况进行估计。

2.3 路由的建立

路由建立的过程是一种由源节点发起的通过请求／应答的方式［6］。 首先将网络区域化，区域中的节点周期性地根据其QoS 约束竞争主节点和副节点；然后将网络中区域中的主副节点以区块的形式不断上链以形成并行区块链。该过程的最终目的是寻找两条以目的节点为终点的稳定且高质量的路由。 当源节点需要向目的节点发送数据且源节点又无到目的节点的路由时，源节点便创建创世区块。 如下图3 所示。 以寻找到达目的节点的链表。 接着源节点按照其默克尔树（Merkle tree）向其临界点发送探测包EERQ，从而开启了目的节点寻找的过程。

源节点收到邻居节点的正常确认包后，检查其时间延迟是否在合理的时间之内以及该节点的最大输出带宽是否在合适的区间，在相邻本区域内寻找主节点和备选节点，区域内的其他节点作为主副节点的备用节点，且周期性地根据QoS 约束条件竞争替换主副节点。 一个区域视为一个区块，区块内的节点通过竞争主节点获得该区块的优先上链权。 而区域内主节点的性能指标为该区块与其他区块竞争上琏的依据。 路径形成的过程为区块链形成的过程，一旦该区块上链即为该区域的主节点被选为通信路径中的一个节点，而该节点在通信的过程中会由于其主节点地位的丧失而由本区域内的其他节点进行替代，进而保证了该数据通信线路的稳定性。 以图2 中节点1 与节点10 进行通信，则路由区块链形成过程如下：

①区域1 内节点1 作为源节点，由源节点创建原始区块。

②由区域1 的邻居区域2 内节点区块竞争第一次上链，由式（3）计算节点的QoS 约束值，然后按照其结果值按照降序进行排序，具有更大QoS 约束值的节点担任本区域的主节点，次小值为副节点，其他节点均为备选节点。主节点获得优先上链区块。

③按照②所示过程完成其他区域内节点区块的上链。整个路由区块链形成结果如图4 所示。

图4 路由区块链

如图5 所示，节点1 与节点10 之间形成的路径依次为：

图5 数据投包率随速度变化情况

第一条路径：节点1→节点3→节点4→节点10

第二条路径：节点1→节点3→节点8→节点10

第三条路径：节点1→节点6→节点4→节点10

第四条路径：节点1→节点6→节点8→节点10

第五条路径：节点1→节点5→节点4→节点10

第六条路径：节点1→节点5→节点8→节点10

考虑到QoS 约束问题，路由最大可能地由主副节点所构成，备选节点可在周期内竞争成为主副节点以保证主副节点的性能优越性。 在图4 中，节点3 为区域2 的主节点，节点4 为区域3 的主节点。 节点1 与节点10 的数据传输需要经过节点3 和节点4 的数据转发方可完成，所以上述第一条路径为最优路径。 但是当节点3 或者节点4由于移动或者能源耗尽等原因失去数据转发能力时，其对应的副节点便代替其主节点的功能，所以上述第二、三、四条路径为最优路径的备选路径。 故实际采用的路径是前四条路径。

3 仿真实验

本次仿真采用NS-3 网络仿真环境，部署在虚拟机上。 并采用多次实验最后采用排除极值并对正常结果值平均的办法进行。

网络拓扑结构是一个节点随机分布在1 000 m×1 000 m 的平面矩形区域的网络模型，移动节点速度为50 m／s 到100 m／s。 MAC 层采用IEEE 802.11，采用恒定比特率（constant bit rate，CBR）数据流，仿真时间为900 s，其中节点最大停留时间变化范围是0 s、40 s、80 s、120 s、160 s。 节点数在对BMQR 和AODV 协议进行模拟性能评估时，主要考虑移动节点的数据报文投递率PDF（Packet delivery fraction）的性能参数。

图5 为网络中所有节点均为正常节点的情况下，数据包投包率延时随速度变化情况。 由图可知，本文所提出的算法在节点移动速度较AODV 算法表现更优，主要原因在于由于EMQR 算法在数据的传输过程中确保多条路径工作，具有更加稳定的路由。 而AODV 协议由于不断重新进行路由的建立，无法确保数据包的正确投递。

4 结语

本文提出的多路径QoS 路由算法将区块链技术与Ad hoc 网络很好地进行了融合，通过区域内节点间的竞争机制自动确定路由节点的选择，很大程度上保证了路由中节点的稳定性。 仿真实验中通过与AODV 协议的对比，可发现本文提出的算法在节点移动的环境中，展示出了巨大的优势。 但是由于区块链技术的融入，需要进行不断的QoS约束值的计算，故本算法存在控制开销较大的问题，以后针对该问题将继续展开研究。