基于短时轨迹交互的稀疏UANET贪婪路由协议*

陈秉试

（厦门海洋职业技术学院，福建 厦门 361012）

0 引 言

无人机自组网络（UAV Ad Hoc Network，UANET）在军民用方面都发挥着重要作用[1-2]。无人机自组网络以无人机作为基本节点，通常配备地面通信设备辅助通信或作为后台数据管控，不仅具有常规移动自组网络的一般特点，如移动性﹑自组织性﹑可扩展性以及多跳路由等，也具有自身的特点，如三维空间运动特性﹑节点密度稀疏性﹑能量有限性等。因此，在多跳数据传输时，应当结合UANET自身特点设计路由协议。

文献[3]以按需距离矢量路由协议AODV（Ad hoc On-demand Distance Vector Routing）路由为基础，加入阈值衡量无人机节点间的链路质量，提高了传输路径的选择可靠性。但是，AODV中路径探索和传输分离使得其难以适应高度动态的拓扑环境。表驱动式优化链路状态路由协议OLSR（Optimized Link State Routing）在无人机网络中得到广泛应用并进行了改良。文献[4]提出了P-OLSR路由协议，通过装载在无人机上的全球定位系统（Global Positioning System，GPS）获取节点位置，并通过节点运动轨迹预测选择中继节点，同时在Linux开发板中完成硬件实现。文献[5]在OLSR路由中加入节点速度和能量信息，并对节点的willingness进行分级，从而优化多点中继（Multi Point Relay，MPR）集合。文献[6]则在OLSR路由中考虑了节点连接时间﹑链路层拥塞度以及节点剩余能量，提出了MPEAOLSR路由协议，改善了数据传输性能。但是，基于OLSR及其改进的路由协议均需要不断维护并更新MPR集，网络开销较大。

贪婪周边无状态路由协议（Greedy Perimeter Stateless Routing，GPSR）以节点空间位置为依据，在无人机网络多跳数据传输中体现出了优异性能，特别是在节点密度较大的场景下[7-8]，且原理简单﹑网络开销较小。但是，该机制并不能完全适用于无人机自组网特点。文献[9]从无人机节点位置﹑速度和方向等角度考虑，综合筛选中继节点，具有开销小﹑可靠性高的优点。文献[10]提出基于移动预测和链路保持时间的路由协议MP-GPSR，缓解高度动态拓扑变化对链路链接情况的影响，并利用两跳节点信息提高右手准则在处理路由空洞时的效率。然而，目前应用在UANET的GPSR及其改进并未充分考虑三维空间关系，且对于节点移动性的预测都以当前瞬时运动状态为依据，预测准确度有待提高。本文将针对三维空间关系进行位置关系计算，节点还将根据自身运动轨迹完成短时轨迹的曲线拟合并交互拟合阶数和系数，通过少量的网络开销提高了移动预测准确度，从而提高数据包传输交付率。此外，针对稀疏环境下时常出现路由空洞导致右手准则难以发挥的问题，本文将采用携带转发的方法降低开销。

1 系统模型

设所研究的UANET中共包含N个节点，每个节点通信半径均为R。对于节点i(i=1,2,…,N)，其通信半径内的所有节点称为节点i的一跳邻居。节点i位置可以通过机载GPS获取，可用三维坐标(xi,yi,zi)表示，其中xi表示经度，yi表示维度，zi表示海拔高度。于是，它与节点j之间的距离可以表示为：

显然，若dij＜R，则节点i与节点j互为一跳邻居节点，即相互成为潜在的中继节点。节点将周期发送信标，包含节点ID﹑空间坐标﹑速度等，发送周期设定为ΔtB。一跳邻居节点之间可通过周期信标感知相互位置，并根据运动惯性利用曲线拟合完成移动性预测。由于节点运动状态通常连续变化，且在一段短时范围内将按规划轨迹和运动状态飞行，设节点i从当前时刻在未来时间间隔Δt内在其轨迹liΔt上将以viΔt做匀速曲线运动，则节点将Δt﹑liΔt﹑viΔt等短时轨迹运动信息以及时间戳﹑节点ID﹑坐标信息加载在数据包字段中发送给其他节点，以实现更精确的拓扑变化感知。然而，若所有节点都将此信息加载在周期信标中必然将大大增大网络负载，因此短时轨迹运动信息将由发出数据请求的节点加载在请求包中扩散，以寻找数据源。若有节点含有该请求包对应的数据，则成为源节点，而发出请求的节点成为目的节点，且响应包从源节点发出，利用路由协议传输至目的节点。这样从目的节点发出请求包到源节点准备发出响应包，通常需要比信标周期长得多的时间间隔。源节点仅根据目的节点发送请求包时的位置﹑速度﹑角度等信息预测将导致较大偏差，特别是在节点运动速度较大的无人机网络环境中。因此，目的节点通过发送短时轨迹运动信息可显著提高移动预测准确率。

2 GR-TTI路由协议

2.1 总体流程

发起数据请求的节点i拟合liΔt，并将拟合参数与其他标记自身状态和数据请求信息加入请求包piΔt发出。发出请求的节点若在发出请求包后等待Δt仍未收到响应包，则重新发送请求。重复发送nr次请求若未收到响应包，则放弃请求。相应的流程图如图1所示。

图1 节点请求流程

在稀疏节点密度环境下，请求包将以泛洪方式扩散。其他节点在接收到请求包piΔt后，先检测当前时刻与请求包内时间戳的差值是否超过时间间隔Δt/2。若超过，则说明当响应包传回时目的节点已飞出可预测轨迹，因此丢弃请求包；若未超过，则检测本地是否有对应的响应包。若有，则采用贪婪转发或携带转发传给目的节点；否则，泛洪请求。

为减少网络中相同请求包的冗余，中继节点在转发请求包后若收到其他节点转发来的相同请求包则丢弃。类似地，为减少网络中相同响应包转发冗余，中继节点在转发响应包后若收到其他节点转发相同的响应包，则丢弃。节点针对请求包的处理流程如图2所示。

图2 请求包接收后处理流程

2.2 贪婪转发

请求节点即为目的节点，发送响应包的节点即可视为源节点。当源节点或中继节点按照图2进入贪婪转发时，根据请求包或者上一跳节点告知的请求时间戳﹑Δt以及目的节点轨迹信息计算当前时刻目的节点位置，并根据邻居信标信息评估下一跳距离目的节点最近的节点并转发响应包，同时告知其目的节点运动和轨迹信息。在稀疏场景下可能出现路由空洞，即暂无下一跳节点或者不存在比自己距离目的节点更近的邻居节点，则采用携带转发。

2.3 短时轨迹交互

无人机节点的轨迹可事先根据任务采用传统经典算法或现代智能算法规划完成，其中传统经典算法包括数学归纳法﹑动态归纳法﹑最优控制法以及导数相关法等。现代智能算法包括遗传算法﹑人工神经网络算法和蚁群算法等[11]。但是，UANET中节点常由于突发情况临时修改轨迹，如某些节点电量不足返程充电﹑某些节点由于故障返程维修或者某些节点之间临时需要相互支援等。因此，节点之间交互短时轨迹信息即可。一方面提高预测精确度，另一方面增大拓扑变化灵活度。

设节点A在t0时刻发送请求包，则其将[t0,t0+Δt]时间段内轨迹进行w阶多项式拟合，表示为：

其中，t∈[t0,t0+Δt]，且{αr,…,α0}﹑{βr,…,β0}﹑{γr,…,γ0}分别是经纬度和海拔位置坐标和时间的拟合多项式系数。通过发布时间戳﹑时间间隔和三组多项式系数，即可使得源节点与中继节点快速预测目的节点位置。

2.4 携带转发

稀疏场景下，当某个中继节点的邻居节点中已无距离目的节点更近的下一跳节点时，则形成路由空洞。若采用传统GPSR右手准则转发，可能下一跳节点仍然无法摆脱路由空洞，甚至由于局部节点密度过低形成临时的孤立节点。因此，在本文提出的协议中，节点将采用携带转发[12]策略缓解响应包转发途中出现的路由空洞问题，即节点遇到路由空洞时将待转发的数据存储于本地缓存中，通过对邻居节点运动轨迹预测发现存在距离目的节点更近的下一跳节点，完成响应包转发。若缓存时间超过一定时间无法找到目的节点或者更优中继节点，则丢弃数据包。

3 仿真及分析

3.1 仿真条件

在MATLAB仿真平台上搭建UANET模型，设定仿真物理空间为经纬方向各3 km，海拔高度100～500 m。无人机通信半径为500 m，飞行时间300 s，飞行半径1 km，节点个数3～15，每个节点均匀速曲线运动，但速度取值为[5，30] m/s中的均匀随机值。不失一般性，各节点在海拔高度上随机分布于100～500 m。为保证无人机之间不相撞，各节点飞行高度不同，且各自保持设定高度飞行。飞行轨迹简化为圆周运动，圆周半径1 km。为增大拓扑动态，节点在圆周轨迹上将随机选择顺时针飞行或者逆时针飞行。选定某个飞行方向后，将保持10～20 s再重新随机选择飞行方向，该保持时间即为各节点请求包中的Δt。设定处于携带转发状态的节点缓存数据包时间为30 s。节点信标发送周期为1 s，最大请求次数为3次。仿真将评估GRTTI与传统GPSR路由协议在不同节点个数下的数据包到达率和请求-响应延迟方面的性能。为了抵消运动和通信过程的随机性，将重复100次后取平均值。

3.2 数据包到达率

数据包到达率定义为平均每个请求节点获得的响应包和发出的请求包的比值。该指标可验证路由协议的有效性。图3为节点个数从3增加到15时GR-TTI和GPSR数据包到达率性能曲线。

图3 数据包到达率

从图3可以看出，在节点密度总体稀疏的环境下，随着节点个数增加，两个路由协议数据包到达率均增加。这是由于更多的节点可使网络中具有更多潜在中继可提供转发，而节点过于稀疏时常导致断链或者孤立节点。同时可以看到，所提的GRTTI协议的数据包到达率性能在不同节点数下均优于GPSR。因为当出现孤立节点或者断链时，GPSR并无缓存措施只能丢弃数据包，而GR-TTI可通过携带转发模式等待目的节点或者中继节点出现，延长了响应包的生命周期，使得越稀疏的情况下GRTTI的数据包到达率性能优势越明显。且GR-TTI具有更准确的移动预测，从而更合理选择下一跳中继节点，实现更高的数据包到达率。

3.3 平均请求-响应延迟

当目的节点发出一次或多次请求后收到响应包，应统计其平均请求-响应延迟。该指标定义为对于有响应的请求，从第一次发出请求包时间到对应响应包到达目的节点的平均时间间隔。需要说明的是，发出请求而无法获得响应的情况已体现在数据包到达率上，平均请求-响应延迟则表征成功获得所需数据包的平均等待时长。图4为节点从3增加到15时GR-TTI和GPSR平均请求-响应延迟性能曲线。

图4 平均请求-响应延迟

从图4可以看出，在节点密度稀疏的场景下，随着节点数增大，两个协议的平均请求-响应延迟均呈下降趋势。因为节点数增多，源节点更容易寻找到合适的下一跳节点将数据传给目的节点。同时也可以看到，GR-TTI的平均请求-响应延迟低于GPSR，因为GR-TTI能更准确预测目的节点位置，从而使得响应包更快抵达目的节点。

4 结 语

节点密度稀疏的无人机自组网络容易造成链路不稳定和路由空洞，为了提高数据传输效率，提出了基于短时轨迹交互的贪婪路由协议。目的节点通过对自身短时轨迹的多项式曲线拟合，完成短时轨迹描述，并通过发布轨迹和运动信息的方式，使得源节点和中继节点能更准确判断其位置，从而增加数据包到达率。同时，修正传统的贪婪转发和携带转发机制，以适应节点密度稀疏环境下拓扑高度动态变化﹑链路生存期短和路由空洞的问题。

[1] 卓琨,张衡阳,郑博等.无人机自组网研究进展综述[J].电信科学,2015,31 (04):128-138.

ZHUO Kun,ZHANG Heng-yang,ZHENG Bo,et al.Progress of UAV Ad Hoc Network:A Survey[J].Telecommunications Science,2015,31(04):128-138.

[2] 谢相博,徐光辉,范凯鑫等.基于4G的无人机远程巡逻系统[J].通信技术,2015,48(11):1305-1309.

XIE Xiang-bo,XU Guang-hui,FAN Kai-xin,et al.UAV Remote Patrol System based on 4G[J].Communications Technology,2015,48(11):1305-1309.

[3] 王顶,赵颐轩,马娟.无人机网络环境下AODV协议的优化[J].计算机测量与控制,2013,21(06):1580-1583.

WANG Ding,ZHAO Yi-xuan,MA Juan.Optimization of AODV Routing Protocol for UAV Network[J].Computer Measurement & Control,2013,21(06):1580-1583.

[4] ROSATI S,KRUŻELECKI K,HEITZ G,et al.Dynamic Routing for Flying Ad Hoc Networks[J].IEEE Transactions on Vehicular Technology,2014,65(03):1690-1700.

[5] 刘济铭,孟凡计,王玉文.一种具有速度与能量意识的路由协议[J].通信技术,2013,46(01):63-66.

LIU Ji-ming,MENG Fan-ji,WANG Yu-wen.Routing Protocol with Speed and Energy Awareness[J].Communications Technology,2013,46(01):63-66.

[6] 董思妤,张洪,王路.无人机自组网OLSR路由协议的优化[J].军械工程学院学报,2017,29(02):67-70.

DONG Si-yu,ZHANG Hong,WANG Lu.Optimization of OLSR Routing Protocol in UAV Ad Hoc Network[J].Journal of Ordnance Engineering College,2017,29(02):67-70.

[7] HYLAND M T,MULLINS B E,BALDWIN R O,et al.Simulation-Based Performance Evaluation of Mobile Ad Hoc Routing Protocols in a Swarm of Unmanned Aerial Vehicles[C].International Conference on Advanced Information NETWORKING and Applications Workshops IEEE,2007:249-256.

[8] SHIRANI R,ST-HILAIRE M,KUNZ T,et al.The Performance of Greedy Geographic Forwarding in Unmanned Aeronautical Ad-Hoc Networks[C].Ninth Communication Networks and Services Research Conference,IEEE Computer Society,2011:161-166.

[9] 石祥滨,王锋.无人机自组网络多媒体数据传输路由算法研究[J].沈阳航空航天大学学报,2012,29(02):33-36.

SHI Xiang-Bin,WANG Feng.A Routing Algorithm for UAV Ad Hoc Networks Multimedia Data Transmission[J].Journal of Shenyang Institute of Aeronautical Engineering,2012,29(02):33-36.

[10] 李玉龙,黄国策,张衡阳等.移动预测的无人机自组网路由协议[J].空军工程大学学报:自然科学版,2015,16(03):61-65.

LI Yu-long,HUANG Guo-ce,ZHANG Heng-yang,et al.A Routing Protocol Based on Mobility Prediction in UAV Ad Hoc Networks[J].Journal of Air Force Engineering University(Natural Science Edition),2015,16(03):61-65.

[11] 王俊,周树道,朱国涛等.无人机航迹规划常用算法[J].火力与指挥控制,2012,37(08):5-8.

WANG Jun,ZHOU Shu-dao,ZHU Guo-tao,et al.Research of Common Route Planning Algorithms for Unmanned Air Vehicle[J].Fire Control & Command Control,2012,37(08):5-8.

[12] 安莹,王建新,刘耀等.延迟容忍网络中一种基于概率接纳和丢弃的拥塞控制算法[J].系统工程与电子技术,2014,36(03):553-563.

AN Ying,WANG Jian-xin,LIU Yao,et al.A Congestion Control Algorithm Based on Probabilistic Acceptance and Drop in Delay Tolerant Network[J].Systems Engineering and Electronics,2014,36(03):553-563.