一种面向小型无人机自组网的路由判据*

张 倩，胡曦月，刘 颖

(武警工程大学 信息工程学院，西安 710086)

0 引 言

无人机自组网是小型无人机集群应用的基础，其性能决定了无人机集群任务完成效果。无人机自组网(Unmanned Aeronautical Ad Hoc Network，UAANET)作为移动自组网(Mobile Ad Hoc Network，MANET)的一个特例，与传统MANET相比，具有节点移动性强、拓扑变化速度快、能量受限、三维空间移动等特点[1-3]。其中，无人机自组网中的路由协议是网络的重要组成要素，而路由判据是衡量路由协议性能指标的重要依据，在相当程度上影响着无人机自组网数据传输的性能，也是集群中各成员之间协调完成各项任务的基础[4-5]。

当前，绝大多数网络路由算法是针对MANET设计的，这些协议都属于主动式路由协议，即已经提前根据判据计算出了路由表。但这种方式无法适应无人机自组网的快速拓扑变化、能量受限等特点，因此，必须设计能够适应UAANET网络拓扑快速变化的路由协议。随着定位技术的飞速发展以及终端设备的普及，基于地理位置信息的路由协议因简单高效，在无人机自组网中拥有广阔的应用前景[6]。以经典的航空路由协议(The Aeronautical Routing Protocol，AeroRP)为例，它是一种专为高度动态机载网络设计的、适用于特定领域的路由协议[7]。AeroRP最早在文献[8]中提出，后来在ns-3网络模拟器中进行了建模和分析，结果表明其在吞吐量和分组交付率方面优于传统的MANET路由协议[9-11]。但是AeroRP路由协议针对的是大型动态机载网络，没有考虑小型无人机节点飞行时间较短、节点数量过多时所带来的问题。

为此，本文针对小型无人机自组网节点数量多、位置变化快和续航时间短等特点，对AeroRP协议中的判距进行改进，设计了一种基于节点生存时间的路由判据(Routing Metric Based on Node Survival-time，RMBNS)，综合考虑了网络内各无人机的剩余飞行时间、移动速度矢量、与源节点之间距离以及源节点的最大传输距离等参数，将生存时间内到达源节点先后顺序作为度量尺度，实现了最优下一跳节点的选择，克服了传统判距可能选择无效节点导致数据传输中断的问题。

1 AeroRP协议

AeroRP是为高度动态的机载网络设计的路由协议，与其他端到端的MANET路由协议不同，它只进行逐跳路由决策，这种方式可以避免机载网络中因节点高速移动而导致在确定端到端路径后链路中断的问题[6-7]。

AeroRP的运行主要分为邻居发现和数据转发两个阶段。

(1)邻居发现阶段

在邻居发现阶段，机载节点TA通过以下三种机制尽可能多地收集有关网络拓扑的信息。

主动侦听：在主动侦听机制中，节点侦听正在其他节点之间交换的数据包，从中提取位置信息，并建立或更新其邻居表。为此，必须启用节点网络接口上的主动探测。这样收集的位置信息仅在“邻居保持时间”(neighborHoldTime)指定的时间间隔内有效。在此时间间隔内，如果未收到新的位置更新，将清除节点存储的位置信息。这有助于在高度动态的环境中跟踪所有活跃的邻居。

Hello信标：当节点不传输任何数据时，Hello信标由节点传输。这确保了其邻接节点知道它的存在。这些消息通常通过“Hello更新间隔”(helloUpdatelnterval)所规定的时间间隔定期广播。

地面站更新：地面站更新机制用于在执行某些任务中增强或替代主动侦听，这些任务具有预先确定的飞行计划。这些更新定期广播，并在网络中的所有节点之间交换。

(2)数据转发阶段

在此阶段，发送方节点通过使用邻居发现阶段中构建的拓扑表来确定转发分组的下一跳。截获时间(Time-to-Intercept，TTI)路由判据用于确定下一跳邻居[9-10,12]。对于拓扑表中的每个节点，TTI计算如公式(1)所示：

(1)

式中：Δd是节点邻居表中邻节点的当前位置和目的地位置之间的欧氏距离，R是所有节点的通用传输范围，Sd是记录的速度分量。选择具有最低TTI值的邻节点作为下一跳节点，并将数据包转发给该节点。

若当前节点自身具有最佳TTI，但其仍不在与目的节点数据传输的范围内，针对这种情况，AeroRP有三种处理模式：一是摆渡模式，即将数据包无限期地存储在自身缓存队列中，直到找到具有较低TTI的节点后进行转发；二是缓存模式，即排队时间有一定限制，超时后仍未找到具有更低TTI的节点，则丢弃；三是丢包模式，即直接将数据包丢弃。考虑到小型无人机的机载数据处理存储能力有限、续航时间短的特点，并且为了保证网络中数据的可靠传输，本文选择缓冲模式进行数据转发。

2 路由判据改进算法

2.1 路由判据步骤

如前文所示，经典的AeroRP协议中的TTI路由判据只考虑了相关节点的运动速度和距离信息，对于续航时间有限的小型无人机自组织网络不适合。为了避免因选择能量即将耗完或者所剩能量不足以维持数据转发的“潜在无效”节点作为下一跳节点的问题，这里提出基于生存时间的路由判据。判据为一种启发式度量，记为RMBNS，其物理含义是在网内所有节点中，某一节点在其生存时间内出现在源节点的通信传输范围内的先后顺序。具体步骤如下：

Step1 给定一个邻居节点Ni，已知节点的地理坐标为(xi，yi),速度为(vxi，vyi)，Ni的速度向量vi计算如公式(2)所示：

(2)

Step2 计算节点Ni正x轴与Ni速度矢量之间的夹角α：

(3)

Step3 给定目的地D的地理坐标为(xd，yd)。Ni的正x轴与Ni和D连接的直线之间的角度α′为

(4)

Step4 计算v：

v=vicos(α-α′)。

(5)

源节点和目的地之间基于速度分量v是RMBNS计算的一个重要部分，数值为正表示该邻节点正在靠近目的地移动，数值为负则表示邻节点正在向目的地相反的方向移动，绝对值越大表明节点的运动速度越大。

Step5 在三维空间中，对于给定的源节点地理坐标(xi，yi，zi)和目的地的地理坐标(xd，yd，zd),计算源节点与目的地之间的欧氏距离Δd：

(6)

Step6 获取节点Ni邻居表中邻居节点的剩余飞行时间ΔT：

ΔT=E/P-T。

(7)

式中：E是单个无人机的总能量，P是无人机的功率，T是无人机已飞行的时间。

Step7 根据公式(5)～(7)计算RMBNS，如公式(8)所示：

(8)

式中：R是指节点的数据传输范围。

Step8 选取具有最大RMBNS的邻节点作为下一跳节点。RMBNS=0是一种特殊情况，表示永远不要选择这个邻居节点作为下一跳，因为算法不会选择远离目的地、不在传输范围内，且生存时间低于门限值的邻居节点。

2.2 改进判据在AeroRP协议中的实现

AeroRP协议是在没有完整源节点到目的节点的端到端路由信息，即没有掌握网络全局路由信息的情况下进行路由决策的，因此这种路由决策是按跳进行。在实现路由判据时，每个节点都维护一张邻居表，用于存储当前在其通信范围内的节点信息。初始化时，N代表邻居表中邻节点数量，令N为零。节点收到任意数据包时，它会对其邻居表进行更新。如果收到的数据包是来自于节点Ni的主动侦听数据包或者是“Hello”通告数据包，那么当前节点会认为节点Ni在其通信范围内，并将节点Ni加入到它的邻居表中，使得N=N∪{Ni}，节点列表同时获取节点Ni的位置、轨迹等信息，并以数组的形式存于邻居表中。当前节点转发数据包时，它会遍历其邻居表，并计算每个邻节点包括其自己的RMBNS值，如果某一邻节点具有最大的RMBNS值，当前节点会将数据包转发给该节点。算法伪代码如下：

输入Input：location(my_x,my_y,my_z,my_vx,my_vy,my_T,dx,dy,dz)

输出Output：NextHop

初始化Inital：

RMBNS_neighbor *temp =head_//从邻居表的头部开始遍历

RMBNS =getRMBNS(location)//初始化RMBNS

nsaddr_t NextHop =-1//没有下一跳的传输

程序 Procedure RMBNS：，

Repeat

tempRMBNS =getRMBNS(temp->x_,temp->y_,temp->z_,temp->T,temp->v dx,dy,dz)

if(tempRMBNS >RMBNS)

RMBNS =tempRMBNS

ReturnNextHop//遍历邻居表，如果找到最大的RMBNS，则返回对应的下一跳地址

3 仿真实验与性能分析

使用ns-3平台对改进判据的性能进行仿真验证，比较其与TTI判据的性能差别，同时对比两种判据下的AeroRP协议与经典主动路由协议OLSR的性能。仿真所模拟的应用场景为一个典型的多机单站小型无人机集群，网络由10～100个位置随机分布的节点组成，其中地面控制站作为固定的汇聚节点位于区域的中心位置，网络数据链路层协议选择IEEE802.11b。如前所述，实验使用AeroRP协议的缓冲模式，根据网络传输数据包大小设置缓冲区为200，最大缓冲时间设置为5 s。缓冲时间到期后，数据包将被清除。实验适用随机运动模型，传输层协议为UDP，其他相关参数设置如表1所示。

表2 实验参数

在实验中，分别从以下三个方面对判据进行测试：一是吞吐量，即单位时间内成功地传送数据包的数量；二是准确度，即目的节点成功接收的数据包数除以发送端MAC层发送的数据包数，该指标是根据分组选择的路由是否在目的地成功接收来进行测量；三是延迟，即数据包从源节点在MAC层传输数据包与目的地MAC层接收数据包之间的时间差。同一节点数量均进行30次仿真实验，结果取平均值。

图1给出了节点数量与网络平均吞吐量的关系，可以看出网络的节点密度对三种路由判据都有一定影响。当网络节点数量较少时，由于OLSR根据已经建立好的完整的端到端路由项进行快速数据转发，因此吞吐量比其他两者要高。但是，随着节点的增多，网络规模变大，OLSR事先建立的路由表中，一些节点由于随机运动超出了传输范围，或者生存时间不足以支持转发数据包，造成链路中断，最终导致吞吐量性能开始下降。相比之下，AeroRP TTI在少于70个节点的时候吞吐量比RMBNS的性能更优，吞吐量随着节点数的增加而增加，但当节点数接近70或更高时RMBNS判据的吞吐量比 AeroRP增长更快。这说明由于AeroRP的TTI判据选择下一跳时，只根据速度矢量和距离进行判断，随着节点的增加，所选的下一跳是一个生存时间即将耗尽的无人机节点的概率增大，这样会导致数据无法传递，使得吞吐量增长减慢；而RMBNS选择下一跳将无人机生存时间也考虑在内，所以在节点数量较大的场合下可以提高网络中数据传输的稳定性，吞吐量稳定增长，这非常适用于未来无人机的“蜂群”应用场景。

图1 节点密度对吞吐量的影响

不同节点数量下三种路由判据对路由准确度的影响如图2所示。仿真结果表明，无论节点数量如何，AeroRP的TTI、RMBNS和OLSR的准确率均超过了70%。随着节点数的增加，由于OLSR路由表中存在失效的节点，所以准确度不再提高。而AeroRP随着节点数量的增加，对数据包的转发和准确度接近100%，这说明了AeroRP能够准确地传递数据包；而RMBNS在准确度上也一直优于AeroRP的TTI判据。这在很大程度上说明RMBNS判据更适合在节点快速移动、飞行时间、能量受限的环境下准确传输数据。

图2 节点密度对准确度的影响

节点密度对数据包传输延迟的影响情况如图3所示。由于OLSR路由已根据判据计算出了路由表，因此在节点较少的情况下延迟比其他两者要低，但是OLSR随着节点的增加延迟一直在增大，说明这种主动式路由不适合动态的无人机网络环境；而随着节点密度的增加，AeroRP中的TTI判据的延迟在逐渐减小，当节点接近75甚至更多时，延迟进一步降低。RMBNS判据在延迟上一直比AeroRP的TTI较高，这是由判据设计的复杂度决定的。尽管RMBNS的延迟随着节点的增加也呈下降趋势，但是在提高准确度和吞吐量的前提下，牺牲一点延迟对于对实时性要求不高的应用是可以容忍的。

图3 节点密度对延迟的影响

4 结 论

小型无人机自组网有着广泛的应用前景，因其具有拓扑动态变化、能耗要求高等特点，在设计网络路由协议和判据时也存在着一定的挑战。在网络层利用地理信息进行路由，可以提高路由协议的性能。本文所提出的面向小型无人机的路由判据RMBNS是基于网络层共享物理层的地理位置信息和生存时间等信息，从而实现小型无人机网络路由的稳定性和健壮性。通过仿真发现，基于RMBNS的AeroRP协议性能明显优于经典的OLSR，并且与经典AeroRP协议中的TTI相比，RMBNS判据在路由吞吐量和准确度上都有所提升，更加适合小型无人机自组织网络路由的选择。