基于最短路径的无人机自组网改进路由算法

王朝炜，常新时，马腾森，庞明亮，王卫东

(北京邮电大学 电子工程学院，北京 100876)

0 引言

无人机自组织网络(UAV Ad Hoc Network,UANET)是移动自组织网络(Mobile Ad Hoc Network,MANET)在无人机场景内的一种典型应用。除了具有MANET自组织的特点，还有独特的移动性、时延性和拓扑动态性等特点，在各领域UANET都具有广泛的应用，如森林火灾监测、搜索和救援行动[1-3]、侦察行动、运输[4]等。

在无人机通信网络中，节点通过无线方式相互通信，无人机通信网络节点可以在不依赖基础设施的情况下完成与网络中其他节点的通信，未直接相连的节点可以通过中继节点进行多跳通信。相较于传统的无线网络来说，UANET的移动性更高，这使得无人机的网络拓扑更加复杂且变化更加频繁。此外，无人机在高速飞行时需要保持必要的安全距离来避免碰撞，这也给UANET组网和维护带来挑战[5]。无线通信网络的一个很重要研究方向是路由协议的设计；因此，如何有效地选择适合数据传输的链路，是衡量一个路由协议是否优秀的标准。基于以上特性，传统的Ad Hoc网络路由协议无法直接在UANET中使用。因此，设计一种能够降低丢包率、减少故障情况恢复时间、提高系统稳定性等指标的路由协议是当前UANET的研究热点。

在性能提升方面：Sarao等人[6]通过考虑几个性能指标来分析Ad Hoc网络的路由协议，如吞吐量、端到端延迟、标准化路由负载，以各种速度和暂停时间接收的数据包，这为路由协议的评估方法提供了思路。Jiang和Han[7]专注于为无人机设计的路线，并旨在对路由协议进行一些完整的调查。此外，还详细比较了现有路由协议的性能。

在路由协议对比方面：Abbasi和Khan[8]提供了基于仿真的现有动态结点选择路由协议和静态结点选择路由协议的研究，给出了这一领域关于路由技术的深刻见解。Nayyar[9]分析测试UANET中AODV、DSDV、DSR等常见路由协议，以及各路由协议在分组投递率、端到端时延进而吞吐量的性能指标，验证最优路由。

在多路径路由研究方面：针对UANET节点能量有限、移动快、数据多,造成网络QoS下降的问题，逯建琦[10]提出将改进的萤火虫算法融入到多径路由中形成萤火虫多径路由算法(AOMDV-FMRA)。首先为减小速度对路径稳定度的影响，在路由发现过程中引入边界评价因子以适应拓扑变化，再根据路径上节点的负载信息，对反向路由进行选择；最后将能量评价参数映射到萤火虫算法中对收集到的路径能量信息进行处理，作为流量分配的依据，提高算法性能。

本文根据UANET的结构特点，以最短路径路由算法为基础，提出一种基于最短路径的改进UANET路由算法，通过对比AODV(Ad Hoc On-demand Distance Vector Routing)和最短路径算法，以丢包率、平均端到端时延、平均抖动等指标来验证所提算法的性能。仿真结果表明，所提出算法在无人机节点随机移动场景中，整体性能有显著提升。

1 UANET中的路由协议

在UANET中，无人机作为网络节点组成了多跳自组织网络。其中，路由协议被定义是通过中间节点查找从源节点到目的节点有效路径的过程。由于无人机节点的移动性，网络频谱随时发生改变，网络连接也会因此处于非稳定状态，造成链路间隙性终端。节点移动性、间断性链路、有限的网络资源，使得无人机中的路由协议成为一项具有挑战性的研究工作。常见UANET中的路由协议分为主动路由协议和反应式路由协议，其中，反应式路由又分为混合路由协议、基于地理位置的路由协议和受自然启发的路由协议。UANET示意如图1所示。

图1 UANET示意图Fig.1 Schematic diagram of UANET

1.1 主动路由协议

主动路由协议[11]又称为表驱动路由协议。在这种路由类型中，为了存储网络内部相邻节点的状态，每个参与路由的无人机节点需要维护一个或多个路由信息表。当无人机节点移动或者状态变化时，路由表的信息就会发生变化，此时每个节点都需要更新自己存储的数据表结构信息[12]。而无论此时是否需要传输数据，每个节点都要和网络中的其他节点交换最新的路由信息。

主动路由协议在维护全局路由表时，时延性能占优，保障了数据包的正确转发，适用于对时延较敏感的持续性业务；但路由建立和维护的过程会占用部分网络资源，增加网络控制开销，此时该路由协议对于频繁变化的拓扑结构抵抗性较弱，不适合应用于UANET中。主动路由协议可以分为目的序列距离矢量路由[13](Destination Sequenced Distance Vector，DSDV)和优化链路状态路由协议[14](Optimized Link State Routing，OLSR)。

1.2 反应式路由协议

反应式路由协议，也称为按需路由协议[15]。在这种路由类型中，当无人机节点发送其数据分组时，且需要确保其自身路由表中不存在到达目的节点的路由，无人机节点才会启动路由发现过程，该路由表中只存储活动路由的信息。此时启动的路由维护机制用于维护有效路由和删除无效路由[16]，当网络拓扑发生变化时，失败的路由将被删除，路由发现过程将重新开始。此外，路由表会定期更新。因此，与主动路由协议相比，反应式路由协议的效率更高[17]。常见按需式路由协议主要包括按需距离矢量路由(AODV)、Ad Hoc按需多路径距离矢量路由(AOMDV)和动态源路由(Dynamic Source Routing，DSR)。

1.2.1 混合路由协议

混合式路由协议，结合了先应式和反应式路由协议的特点。在区域内，节点采用先应式路由协议，目的是维护到区域内部其他节点的路由信息，降低区域内节点的通信延迟；在区域外，节点采用反应式路由协议，只有节点发起通信请求时且不存在到目的节点有效路径时才建立通信路径，避免了维护到区域外其他无用节点所需的大量网络开销。混合路由协议适用于节点数量较大规模的网络，常见的混合路由协议包括区域路由协议[18]、时序路由协议(TORA)和聚集路由协议(GRP)。

1.2.2 基于地理位置的路由协议

基于地理位置的路由是利用网络中无人机节点的地理位置信息来辅助路由的选择[19]，此类协议要求网络中的每个无人机节点都带有可以提供自身地理位置信息的硬件设备。首先，通过地理位置信息装置或者坐标预测技术来估算目的节点的位置；然后，根据得出的位置信息来做出路由决策并完成数据包的转发。常见的基于地理位置的路由协议是[20]GPSR(Greedy Perimeter Stateless Routing)。

1.2.3 受自然启发的路由协议

受自然启发的路由协议源于蚁群、蜂群、鸟群等自然现象。在实际应用中存在一定的缺点，例如会增加通信延迟、通信开销和能量的消耗[11]。事实上，自然启发的路由方案是基于拓扑的路由方法的子集，是一种反应式路由[21]。

2 最短路径算法及改进算法

2.1 最短路径算法

最短路径算法是求解单源最短路径问题的一种算法[22]。给定一个有向图V=(K,E)，其中K为节点的集合，E为边的集合，最终以求解得到k.d与k.n为目的，其中k.d为节点k到源节点的最短距离，k.n表示节点k到源节点的下一跃点。最短路径算法通过迭代操作，对所有的边进行松弛操作从而更新节点到源节点的最短距离，最终得到所有可能的最短路径。其伪代码如算法1所示。

算法1 最短路径算法(V)伪代码输入:V(K,E)输出:k.d,k.n1:初始化操作2:fori=1to|K|-1do3:foreachedgeE(u,k)∈E4: ifk.d>u.d+w(u,k)5: k.d=u.d+w(u,k)6: k.n=u

算法的步骤流程如下：首先，第1行对所有节点的d值和n值进行初始化，源节点的d值为0，其他节点的d值为无穷大；其次，算法进行了|K|-1次处理，每次处理对应2～6行的一次for循环，每次循环内部都对所有的边E(u,k) 进行松弛操作；4～6行表示对边E(u,k) 进行松弛操作，其中w(u,k) 表示边E(u,k)的权值。图2为最短路径算法的执行示例。其中，图2(a)为算法的输入拓扑图，S为源节点；图2(b)是初始化的结果；图2(c)～(f)是每次循环迭代操作之后的节点状态。

最短路径作为一种主动式路由协议，适用于网络规模较小、拓扑变化较稳定的网络环境。当路径中的节点发生损坏，使得算法失效，导致路径中断无法正常传输，从而节点再次进行路由发现。这会增加通信网络的延迟和开销，还可能会导致网络堵塞。因此，最短路径算法不适合拓扑结构迅速变化的UANET。

图2 最短路径算法执行示例Fig.2 Example of shortest path algorithm execution

2.2 基于最短路径的改进路由算法

结合以上所述问题，本文提出了一种适用于无人机网络的基于最短路径的改进算法。改进流程如下：首先，最短路径算法属于集中式思想，而UANET网络是一个分布式的系统，最短路径算法无法直接运用。改进的方式为相邻节点之间的路由信息先通过交换，再进行最短路径中的松弛操作，进而触发链式更新操作，就可以实现将最短路径算法分布化，使其能运行在无人机网络中；其次，调整了路由表的结构。在原始路由表中增添了记录下一跳节点的列表，列表信息包括三部分，分别是待选下一跳的IP地址集合、其他下一跳的接口集合和待选下一跳对应到达目的节点的跳数集合。这样路由信息表更新时不仅更新下一跳的信息，还会同时更新备选下一跳集合，使得每个节点均有多个下一跳可供选择，与此同时要保证待选集合更新时，所有的备选下一跳均不同，这样才能确保在路径切换时无人机节点均跳跃到不同的下一跳上。通过以上改进操作，实现在最短路径算法的基础上进行多路径传输的思想。

2.2.1 路由发现过程

改进路由算法的路由发现过程，通过路由信息广播，无人机节点间进行信息交换可以发现多个下一跳节点并保存至下一跳集合；通过松弛操作，发现N条最短路径，并保存其中前两条路径。选择先被发现的路径作为传输主路径，另外一条作为备选路径；若最短路径只有一条，那么次短路径有若干条，则选取最短路径作为传输主路径，次短路径作为备选路径。路由发现过程如图3所示。

图3 路由发现流程Fig.3 Route discovery flowchart

2.2.2 路由维护过程

无人机节点移动时，会导致路由网络拓扑结构发生改变，节点A的邻居节点也会随之改变。当节点A发生故障情况时，传输路径断开，降低了通信网络的稳定性。此时，路由维护对于增强网络结构的可靠性十分重要。路由维护的原理是通过检测本地路由表中的路由是否超过所设时限，如果有路由在一定的时间范围内没有进行更新操作，则认为该路由失效，就将该路由从路由表中删除；然后对外进行广播；如果在传输过程中路径发生断裂，则会再次进行路由发现。

在改进路由算法中，网络中的节点每隔固定时间就会主动广播并更新路由信息，若发现的新路径比现有路径长，则保持使用现有路径，并更新备选路径，这样可以减小路由开销；如果新的路径比现有路径更短，则切换到新路径，并更新备选路径，这在一定程度上增加了网络的稳定性。当网络运行时，若传输路径上的节点A发生故障或丢包次数达到所设阈值，便会触发路径切换机制，将传输路径切换至备选路径；与此同时节点A的上一跳便会向邻居节点广播节点A故障的消息。邻居节点收到消息，对比自身路由信息，若它的下一跳集合中有节点A，那么它将会更新自身路由信息并广播；若没有，则不会广播。如果备选路径也断开传输，则无人机节点会重新发起路由发现操作。

当路径失效且路由表更新后，无人机节点会将更新后的信息广播给邻居节点，但向外广播只会使得其他节点的路由状态更准确，并没有对自身节点失效的路由信息做出补偿。改进算法在此方面做出了一定的优化，具体方法是：在链路失效后节点会广播更改后的路由信息，在此路由信息广播包中加入一个标志位，当邻居节点收到此广播信息后会反馈相关的路由信息，用于对失效的路由进行补偿。

3 改进路由算法的仿真实现

3.1 仿真参数设置

本文采用EXata作为仿真验证平台，EXata 是用来研究、开发、测试、评估的工具包，它表现、互动和行为的精确程度同真实网络相似[23]，用户能够根据网络模拟器对网络模型的拟合来计算网络的基础行为和评估网络能达到的综合性能。EXata 创建了一个数字网络副本，该副本使用真实的应用程序与现实网络实时连接。

本文的仿真场景中，在有32个随机分布的无人机的UANET网络上进行模拟仿真。无人机节点分布在3 000 m×3 000 m的地域范围内，模拟运行120 s。在网络中建立一对一通信链接，32个无人机随机移动，设置不同的运动速度(分别为1～2 m/s、4～5 m/s、8～10 m/s、12～13 m/s)，网络拓扑实时发生变化，链路状态也随之发生变化。详细的仿真参数如表1所示。

表1 仿真参数设置Tab.1 Simulation parameter settings

在EXata系统中，固定比特率传输(Constant Bit Rate,CBR)采用的是尽力而为的发送策略，也就是说CBR没有如TCP传输协议一样对数据包的到达率做出保证，因此采用CBR数据传输能在仿真中更好地反映出路由协议的真实性能，无人机节点仿真示意如图4所示。

图4 无人机随机运动场景图Fig.4 Node random motion scenario graph

3.2 仿真结果与分析

本节分析了UANET中不同路由算法的性能，将改进路由算法、AODV算法和最短路径算法进行对比，在无人机随机分布随机运动条件下，AODV路由协议链路切换不及时，而改进路由算法的链路是周期切换的，可以将链路及时快速地切换到更短更新的链路，在一定程度上降低时延，提高传输效率。通过实验对丢包率、平均端到端时延、平均抖动等参数进行评估，验证了改进路由算法的有效性。

各算法的丢包率如图5所示，当无人机移动速度较低，为1～2 m/s时，由于无人机移动缓慢，网络拓扑结构变化不大，最短路径算法优势明显，丢包率为16.4%，改进路由算法和AODV表现相差不大，前者略好；随着无人机移动速度的提高，改进路由算法和AODV丢包率均有下降，最短路径算法表现较差，丢包率上升，很不稳定。在无人机速度为4～5 m/s时，改进路由算法比最短路径算法和AODV分别低15.04%和8.94%；当速度上升到8～10 m/s时，改进路由算法比最短路径算法和AODV分别低16.21%和10.24%；当移动速度继续上升至12～13 m/s时，改进路由算法比最短路径算法和AODV分别低22.37%和4.75%。通过对比分析，发现随着无人机移动速度的提高，改进路由算法丢包率下降最大，因为由于无人机移动造成拓扑结构发生变化时，它能更快地切换到更短路径，从而实现更小的丢包率。总体看来，改进路由算法在无人机移动的情况下有更低的丢包率，优于其他两种算法。

图5 无人机随机运动场景各算法的丢包率Fig.5 Packet loss rate of each algorithm in the node random motion scenario

各算法的平均端到端时延如图6所示，同样，在当无人机移动速度为1～2 m/s的条件下，最短路径算法和AODV时延均超过1 s，只有改进路由算法时延在1 s内；随着无人机运动速度提高至4～5 m/s，3种算法的端到端时延均有所下降，改进路由算法的时延比最短路径算法和AODV分别低44.9%和74.0%，AODV延迟仍旧较高，因为AODV在拓扑发生变化时需要重新寻路，导致延迟增加；速度为8～10 m/s时，改进路由算法的时延比最短路径算法和AODV分别低37.5%和83.6%；在无人机移动速度为12～13 m/s时，改进路由算法的时延比最短路径算法和AODV分别低12.7%和60.5%。在此场景下，AODV端到端时延表现最差，最短路径算法表现次之，改进路由算法表现最好。因为当无人机移动造成拓扑结构发生快速变化时，所提出的算法可以更快地发现并切换到更短的传输路径，而更短的传输路径意味着更短的时延。

图6 无人机随机运动场景各算法的平均端到端时延Fig.6 Average end-to-end latency of each algorithm in a node stochastic motion scenario

图7为无人机在不同运动速度下,不同算法的平均抖动。

图7 无人机随机运动场景各算法的平均抖动Fig.7 Average jitter of each algorithm in the random motion scenario of the drone

无人机速度为1～2 m/s时，改进路由算法的平均抖动稍高于最短路径算法和AODV；无人机速度为4～5 m/s时，改进路由算法的抖动比最短路径算法高0.38 ms，比AODV低0.92 ms；无人机速度上升到8～10 m/s时，改进路由算法的抖动比最短路径算法高0.22 ms，比AODV低1.24 ms。无人机速度达到12～13 m/s时，改进路由算法仍处于次位。从图7整体来看，随着无人机运动速度的提高，各算法抖动程度均有不同程度的降低，最短路径算法抖动表现更优，改进路由算法次之，AODV表现较差。

从图5～图7总体分析，改进路由算法在无人机移动速度为1～2 m/s时丢包率稍差，平均抖动比最短路径算法稍高；在其他无人机速度运动的状态下，丢包率低，同时平均端到端时延和平均抖动均较低，整体性能最优。

4 结论

本文针对UANET中的网络可靠性问题，提出了基于最短路径的改进路由算法。介绍了UANET中的路由协议和最短路径算法的原理，详细阐述了改进算法的设计和路由策略。实验根据丢包率、平均端到端时延、平均抖动参数指标来评估改进路由算法的性能，将改进路由算法和AODV与最短路径算法对比仿真并分析结果，可以发现，在无人机随机分布且随机运动的高流量场景下，改进路由算法在整体性能上有一定的优势，均衡了网络负载，提高了网络的可靠性和稳定性，进而证明了改进路由算法的有效性。