高效的多无人直升机自组织网络路由算法研究

梁 涛,伍心皓

(1.海军装备部装备采购中心，北京 100071；2.中国直升机设计研究所，江西 景德镇 333001)

0 引言

随着电子技术、传感器技术和通信技术的不断发展，无人直升机系统的性能也取得了长足的进步，现代无人直升机可以进行自主飞行，也可以由工作人员进行远程操作控制。由于其功能较多、飞行动作灵活、安装容易和操作简单等优点，无人直升机逐渐应用于各种任务，例如搜索救援、边界监视、野火监视、风力估计、灾难监测、遥感和交通监控等任务。

由于无人直升机网络拓扑的频繁变化、无人直升机的快速移动和无线链路质量的不稳定，现有的移动自组织网络路由不适用于无人直升机网络。文献[1]在两个微型无人机和地面站的网络中评估OLSR协议，发现OLSR路由协议无法应对快速变化的拓扑结构。文献[2]提出基于BATMAN的路由，结果显示由于其收敛时间较长，拓扑结构的频繁变化会损害该算法的效率。相比传统的先应式路由和反应式路由，基于地理信息的路由无需路由表，也不需要反复查找最短路径，因此其耗费较低。对于地面车辆，DTNgeo[3]算法充分利用了导航信息和存储-携带-运输的技术，该方法通过引入摆渡无人机提高路由效率。 LAROD是一种基于位置的飞行器路由算法[4]，将地理信息路由与存储-携带-转发机制相结合，在较低的开销下确保了与Epedemic路由相当的分组投递率。在稀疏节点网络中基于地理信息路由转发的性能结果证实：单纯的基于地理信息的贪婪转发方案通常只适用于非关键应用[5]。因此，将基于地理信息转发与其他机制结合是更佳的途径。

文献[6]对无人机的移动轨迹进行预测，利用该信息进行数据保持或数据发送路由选择，相比AODV和LAR算法，提升了吞吐量。完整轨迹感知路由的主要优点是多跳路径的优化，其缺点在于在整个任务期间需要知道所有无人机的路径。

本文针对多无人直升机自组织网络的拓扑变化快，频繁中断连接的特点，结合DTN路由机制与基于地理信息的路由方法，提出了一种高效的多无人直升机自组织网络路由算法。仿真试验结果表明所提出的算法都能很好地适应多无人直升机自组织网络的间歇连接性特征，在投递率方面优于现有的算法。

1 网络路由算法

多无人直升机自组织网络与其他移动自组织网络不同的是，无人直升机节点是飞行的机器，而且它们的移动与动作具有高度的任务驱动性。而且，每个无人直升机的地理位置通常是已知的。本节首先给出多无人机直升机自组织网络模型，在该模型的基础上提出多无人直升机自组织网络路由算法。

1.1 网络模型

本文引入两种链路：“实链路(real links)”和“虚链路(virtual links)”，其中实链路代表普通传输数据的无线链路，虚链路则为一个假设存在的链路，代表在数据传输前需要被携带运输的链路。

1)实链路

当某两个节点ni和nj的地理距离为d，同时两个节点经由实链路连接，D为每个节点的通信传输距离，那么d≤D。在加权图G中，wij代表这条链路的边的权值，其实际意义为这条链路上的ni和nj之间的预期数据传输延迟：

(1)

式中：Mdata代表需要被传输的数据的大小，s(ni,nj)代表节点ni与nj之间的吞吐量。在连通的网络中进行路由转发时，加权图被用于计算消息传输的最短路径，该路径具有最小的传输延迟。

2)虚链路

(2)

(3)

1.2 DTNclose算法

为了解决现有算法存在的问题，本文提出基于位置预测的DTNclose算法。因为每个无人直升机当前的位置、方向和速度都是可用的，所以本文对无人直升机的运动进行预测，得到时间F后无人直升机的位置，根据该位置信息，选择新的下一跳节点，被选择的节点应当是未来离目标更近的无人直升机。由此，可以有效避免被选择的无人直升机在接收到数据后朝着远离目标的方向运动，从而增加网络传输的效率。

假设某个无人直升机标记为n，那么在整个无人直升机网络中有部分节点与无人直升机n存在端到端链路，即这部分无人直升机可以通过中继节点和无人直升机n连通。将这部分无人直升机节点的集合标记为M，对于DTNclose算法而言，选出的下一跳节点m必须满足以下条件：

dm(S,t+F)

arg mindm(S,t+F),m∈M.

(4)

式中，t为当前时间，F为预测的时间间隔，dm(S,t+F)为时间t+F时节点m和目标S的距离，arg min保证选择的节点m为时间t+F时集合M中距离目标S最近的一个，同时，dm(S,t+F)

在完成预测之后，使用得到的位置信息计算t+F时刻集合M中各个节点以及当前节点n到目标节点的虚链路权值，找到其中权值最小的一个无人直升机节点。如果该节点为当前节点n，则不进行数据传输，无人直升机节点n将存储该数据并继续携带飞行；否则，当前节点n将开始向被选择的无人直升机节点传输数据，被选择的无人直升机节点即为下一跳。

1.3 基于DTNclose的改进算法DTNmul

DTNgeo与DTNclose都是单副本传输。每个消息网络中都只有一个副本，一旦数据包传输出错，或者某个消息副本传输的跳数过多且仍未到达目的地，都有可能导致该副本被丢弃，从而影响无人直升机数据传输的效果。

为了解决该问题，提出一种基于多消息拷贝的DTNmul算法。DTNmul算法在DTNclose算法基础上借鉴Epidemic算法的泛洪传播方式，其路由选择方式与DTNclose一致。区别在于DTNclose算法中每个无人直升机在发送完一个数据包后，不会继续保存这个数据包，而DTNmul对这一点进行优化，无人直升机可以继续保存已经发送的数据包。为了尽可能减少网络的负载，DTNmul算法会在某个消息到达消息的最终目的节点后，删除这个消息在整个网络中的副本，从此该消息只有在目标节点中才存在唯一的副本，因此可以大量减少网络的负载。

2 试验

本文在ONE仿真平台中实现DTNgeo、DTNclose和DTNmul三个算法，比较三个算法的运行结果。仿真试验的相关参数设置见表1。

表1 仿真试验相关参数

首先，设置DTNclose的预测时间F=4s，在ONE平台完成仿真试验后，可以生成一个报告文件MessageDeliveryReport.txt。该文件记录了从仿真开始到仿真结束的全网络数据交付比，因此可以得到折线图(如图1)，横坐标为仿真时间，纵坐标为该时间整个无人直升机网络数据包的交付比，即仿真时间内成功传输到目的节点的数据包的数量占这段时间全部创建数据包的比率。

图1 三种路由算法交付比

由图1可知，总体的交付比DTNclose>DTNmul>DTNgeo，三种算法在高峰期都拥有95%以上的交付比，可见折线起伏较大。这是由于数据包传输到地面站只能通过摆渡无人直升机，所以当摆渡无人直升机进入地面站的通信范围内，会有一大批数据包传输到目的地，交付比会大幅上升；反之，当没有摆渡无人直升机在地面站的通信范围内时，不会有数据包到达目的地，但是各个无人直升机还在产生数据包，因此交付比会持续下降，直到下一个摆渡无人直升机进入地面站的通信范围。

5 结论

为了设计实现适合多无人直升机自组织网络的路由算法，本文利用无人直升机的位置信息和移动信息，提出了一种高效的多无人直升机自组织网络路由算法。该算法结合了地理信息路由和延迟容忍网络路由，能同时处理存在端到端链路、链路连接中断这两种情况；利用无人直升机的位置信息和移动信息，对无人直升机未来的位置进行预测，以选择更优的路径进行消息发送；考虑到多无人直升机网络频繁中断的特点，提出了多副本消息传输的策略。仿真试验结果表明，两种路由算法都能很好地适应多无人直升机自组织网络的间歇连接性特征，同时，对该算法的两种改进能有效提升算法性能。