无人机自组网中改进型反应-贪婪-反应路由协议

梅家栋， 南建国

(空军工程大学航空工程学院， 西安， 710038)

随着电子技术、传感器技术和通信技术的发展，无人机是执行情报、监视和侦察任务的空中传感器平台，开始具备武器打击能力，在军事领域中发挥着更大的作用[1-3]。通过建立无人机集群，可实现大量单无人机系统无法高效完成的任务[4]。无人机集群高效运转的基础是建立稳定可靠的通信网络，保证无人机节点间的高效通信[5]。而移动自组织网络具有无中心、组网高度灵活、拓扑动态可变、抗毁性强等特点，可有效满足无人机集群组网通信的需求。无人机集群采用移动自组网的通信架构，形成了无人机自组网[6-7](flying Ad Hoc networks, FANETs)。由于无人机节点的高机动性，无人机自组网具有网络拓扑变化剧烈，链路断开频繁等特点[8-9]。因此，设计能够适应网络环境高度动态变化的路由协议是一项重要研究课题[10]。

基于拓扑和基于地理位置信息是两种重要的路由发现策略[11-12]，各有其优势和局限性。若能将两者有机结合，实现优势互补，可有效提高路由协议的性能。文献[13]提出了反应-贪婪-反应(reactive-greedy-reactive,RGR)路由协议，通过有效结合AODV和贪婪地理转发策略(greedy geographic forwarding,GGF)，RGR路由协议能在高动态环境下具有较好的网络性能。但RGR协议存在4个主要问题：①路由发现阶段沿用AODV路由协议盲目洪泛RREQ消息的方式，网络开销大；②以最小跳数标准选择路径，没有考虑节点的负载状况，容易造成网络中的“热点”问题，当业务量大时，会产生较大的排队时延，甚至出现缓存溢出丢弃数据分组的情况；③在切换到GGF模式进行数据传输时，将向前距离作为下一跳节点的选择依据，忽略了无人机节点的高动态性以及节点的负载状况；④节点的高机动性带来链路断开频繁的问题，使得提高GGF模式分组转发成功概率十分关键，RGR协议则未考虑这一问题。文献[14]为降低路由开销，提出了受限洪泛机制，同时为了提高对链路断开的快速反应能力，引入了移动预测机制，一定程度上提高了网络的性能。文献[15]针对GGF模式失败提出了3种解决方案，并未对提高GGF模式的成功转发概率提出有效措施。文献[16～17]提出了一种Improved-RGR路由协议及路径请求延迟机制，降低了网络的控制开销，但是未考虑网络中节点的负载均衡问题。GGF模式是本地修复的替换策略，文献[18]针对AODV协议的本地修复存在的延迟问题，提出了一种自适应修复算法，有效改善了AODV路由协议的性能。

基于国内外的研究现状及RGR协议存在的问题，本文提出了一种基于负载均衡和高GGF成功概率的改进RGR路由协议(load balancing and high GGF success probability-RGR,LBHGS-RGR)。

1 LBHGS-RGR路由协议

1.1 基于节点负载状态和地理位置信息辅助的受限洪泛机制

在无人机自组网中，无人机节点移出通信范围或发生拥塞都会导致链路发生中断[19-21]，严重影响网络性能。RGR协议在选择路径时，以最小跳数标准选择路径，没有考虑节点的负载状况，某些中间节点需要转发大量数据，容易造成网络中的“热点”问题。如图1所示，位于网络中心的节点4和节点7在多条路径中作为中间节点，承担更多的分组转发任务，负载较重。由于有限的链路带宽和数据处理能力的限制，这类节点更易发生节点的拥塞。此外，RGR协议在进行路由发现时，沿用AODV协议向全网进行盲目洪泛的策略，会带来大量的网络开销，导致节点缓存溢出和网络拥塞，严重影响网络的性能[22]。当网络中节点数增多时，带来的影响更加严重。

图1 节点拥塞示意图

1.1.1 节点负载状态划分

节点的负载通过MAC层队列中的数据长度来度量，并将节点的负载状态分为拥塞和正常[23]。通过计算缓存区的队列长度与最大队列长度的比值，确定负载状态函数Li(t)：

(1)

式中：qi(t)为节点i在t时刻MAC层接口的队列长度；qi max表示为节点i最大MAC层接口最大队列长度。负载状态函数会随时间变化，可以通过采样获得观测值的时间序列Li(k)。

通过比较负载状态函数的数值与拥塞系数ρ大小，确定节点的负载状态Mi，将负载状态分为拥塞(congested)和正常(normal)：

(2)

Li为节点i的负载状态函数，拥塞系数的大小取值为网络的归一化吞吐量的最大值Smax，具体的推导以及证明过程，可见参考文献[23]。

1.1.2 受限洪泛具体实现过程

为了减少RREQ控制分组的数量，同时考虑节点的负载状况，本文提出基于节点负载状况和地理位置信息辅助的受限洪泛机制。在源节点发起路由请求时，处于拥塞状态的中间节点不参与路由的建立过程，在接收到RREQ分组后直接丢弃，不参与转发。而负载较轻的节点收到RREQ分组后，未处于拥塞状态的节点同时满足与目的节点之间的距离关系时，才能参与路由建立的洪泛过程。

在按需式路由完成初始化后，通过其建立过程，网络中的节点获得包括目的节点在内的路由建立相关节点的地理位置信息。同时，相邻节点间在进行路由维护时，通过在HELLO消息中携带的地理位置信息，周期性更新相邻节点的地理位置信息。在基于网络中的节点可获得目的节点的位置信息的前提下，源节点在进行路由发现时，在RREQ消息中添加距离目的节点的距离信息，并设置初始值为零。当源节点向邻节点广播RREQ分组后，中间节点接收RREQ分组处理流程图如图2所示。当网络中的节点均未获得目的节点的地理位置信息，则退化为盲目洪泛机制。

图2 中间节点接收RREQ分组处理流程图

1.2 GGF模式下高分组成功传输概率的路径选择策略

RGR路由协议沿用AODV协议路由建立时最小跳数的衡量标准，进行路径选取。跳数最小也代表节点之间链路的平均距离最大，下一跳节点可能位于通信的边界，会进一步增大了链路断开的可能性。而提高链路断开后的路由修复的成功概率，可以有效减少路由重启的频率，减小传输时延和网络控制开销，提高分组投递率。

RGR路由协议采用贪婪地理转发模式(GGF)，文献[24]已经验证过，在节点分布密集的条件下，采用GGF模式的成功概率很高。基于此，在进行按需式路由建立后的路径选择时，选择节点的平均邻居节点数最多的路径。在RREQ消息中，添加link_number字段，用以存储建立的路径上节点邻居数信息。当节点接收到RREQ消息后，通过查询自身的邻居节点列表，将邻节点个数加到link_number值中，更新后继续转发RREQ消息。同时考虑到路径中跳数会对传输时延的影响，采用路径的平均邻节点个数，作为路径选择的依据。目的节点在首次接收到RREQ消息后，对于后续规定时间内接收到的来自源节点的RREQ消息，并不是直接丢弃。在第一次接收到RREQ分组后，目的节点通过读取link_number字段数值Nl及hop_count字段数值Kl，通过式(3)来计算对应路径的平均邻居节点个数NAl，并将其进行缓存。在后续接收到的RREQ消息中选择具有最大的NAl的路径，作为用于传输数据分组的反应式路径：

(3)

1.3 基于节点负载预测和运动特征的分组转发策略

1.3.1 GGF模式下的负载预测机制

为了避免GGF模式选择的下一跳节点处于拥塞状态，导致转发失败的情况，因此引入了负载预测机制。每间隔一个HELLO消息周期，节点在MAC层接口对自身的负载状态进行采样，获得一组负载函数序列。利用采样序列预测下一个HELLO到来时刻节点的负载状况，并通过HELLO消息携带当前时刻的负载状态观测值和下一个周期的预测状态广播给其邻居节点。通过交互HELLO消息后，可以获得邻居节点的负载状态信息，并以此作为下一跳决策的依据，避免处于拥塞状态的节点参与转发。所以需要选择合适的预测模型，实时、准确判断节点是否处于拥塞状态[25]。

ARIMA模型实现简单、运算速度快、短期预测精度较高、时效性强，具有强线性预测的特点，但无法准确预测负载时间序列的非线性关系。小波神经网络(wavelet neural network，WNN)有效结合了小波分析和神经网络，对复杂非线性不确定系统具备较好的预测效果。因此，文中采用基于ARIMA-WNN组合预测模型，实现对节点负载状态信息的预测。通过将负载状态函数看作由线性部分和非线性部分组成，组合预测的步骤如下：

步骤1得到负载函数采样序列后，通过差分法将非平稳的负载时间序列进行平稳化处理，通过建立ARIMA模型后，得到线性部分的预测值。负载时间序列的非线性特征通过将预测结果与原序列的残差得到。ARIMA模型数学表达如式(4)所示：

(4)

步骤2将步骤1获得的残差值代入到WNN模型中，通过不断修正神经元之间的连接权值和阈值，通过预测得到残差的修正值，即为负载时间序列的非线性特征预测值。WNN模型描述如下：

图3 WNN模型结构图

图3中隐含层节点的输出为：

j=k,k+1,…,k-1+m

(5)

式中：fj(x)为小波基函数；aj、bj分别小波基函数的伸缩参数和平移参数；f(j)为第j个节点的输出值。

隐含层选取Morlet函数作为激励函数，其数学表达式为：

(6)

模型的输出结果为：

(7)

步骤3通过将步骤1得到的线性部分的预测值和步骤2得到的非线性部分的预测值相加，得到下一时刻负载的预测值。

1.3.2 基于运动特征的分组转发策略

当链路断开时，RGR路由协议切换到贪婪地理向前转发模式进行数据传递，通过选择距离目的节点最近的邻节点作为下一跳节点，以保证数据分组具有最大的向前距离。这种仅考虑节点间的距离关系的转发策略适合于节点运动能力弱或基本静止的网络。对于无人机自组网，网络中的节点具有高动态性，所以在进行转发决策时，不仅要考虑到节点间的位置关系，还要考虑节点的运动特征。

如图4所示，在直角坐标系中，节点j的坐标(xj,yj)，目的节点d的坐标为(xd,yd)，节点j是i的下一跳。节点j的运动速度为νj=vjcosθji+vjsinθjj，目的节点的运动速度为vd=vdcosθdi+vdsinθdj，式中vj和vd是节点j和的d的运动速率，θj和θd为节点j和节点d运动速度与x轴正向的夹角。

图4 节点相对运动关系示意图

可计算出节点j和节点d的相对运动速度为：

νjd=vj-νd

(8)

相对运动速率为

Δv=|vjd|=

(9)

节点j和d间的相对距离矢量为：

ljd=(xj-xd)i+(yj-yd)j

(10)

则相对距离为：

(11)

节点j和d的相对距离矢量与相对运动速度之间的夹角可表示为：

(12)

如图4所示，节点d的通信半径为R，则满足节点j进入d通信范围内，相对距离矢量与运动速度的最大夹角为：

(13)

定义进入目的节点通信范围时间：

(14)

在选择下一跳节点时，首先选取Te<0的节点，此时说明该节点已经处于目的节点的通信范围内，对于Te>0的候选节点，选择Te最小的节点，对于Te=0的节点则不做考虑，因为该节点背离目的节点运动。

当节点通过GGF模式找不到下一跳节点时，启用SCF的路由机制，等待下一个HELLO周期再进行判断。当处于低负载状态的节点进入其通信范围内或拥塞节点重新恢复为正常状态时，转发数据包。

2 实验结果及分析

2.1 仿真环境设置

本文通过OPNET14.5网络仿真软件对LBHGS-RGR路由协议的性能，进行仿真验证。比较对象选取AODV协议、文献[13]中的RGR协议和文献[17]中的Improved-RGR协议、文献[18]中的AR-AODV协议。仿真区域大小设置为100 km×100 km×20 km，100个节点在区域内随机分布，各个节点参数设置相同，节点的通信半径为20 km。节点运动模型为RWP模型[26](暂停时间为0)，通信模型采用CBR数据源，数据包大小为512 B,MAC协议采用IEEE802.11，信道传输速率为2 Mbit/s，信号传播损失模型为Friis模型，MAC层队列缓存区最大长度为50，仿真运行时间为20 min。通过改变网络中的节点发包速率以及节点的运动速度，设置不同的仿真场景，通过分组投递率、平均端到端时延和路由开销3项性能指标的对比分析，实验结果取10次实验的平均值。

2.2 仿真结果分析

图5～7为节点在发包速率为20 packets/s保持不变的条件下，不同的节点最大运动速度对不同路由协议的网络性能的影响。其中，图5显示了不同路由协议下，无人机节点最大移动速度与分组投递率之间的关系曲线。从图中可得，随着运动速度的增大，5种不同的路由协议的数据分组投递率都会不同程度的下降。这是因为运动速度的增大会使得节点间的链路更加不稳定，链路断开的可能性增大，路由失败机率增加。由于LBHGS-RGR路由协议在数据传输过程中，出现链路断开的情况后，则切换至GGF模式，同时提高了GGF模式下的分组成功转发概率，能很好应对网络拓扑的剧烈变化。因此，相较于其他4种路由协议具有更高的分组投递率。

图5 节点最大移动速度与分组投递率关系图

从图6可以看出随着节点速度增大，5种路由协议的平均端到端时延都在增大。相较于AODV和AR-AODV协议，在节点移动速度较大时，RGR协议及其改进型因为不需要进行本地路由修复，时延相对较低，同时LBHGS-RGR协议考虑了节点的负载，减小了数据传输过程中的排队时延，进一步降低了平均端到端时延。

图6 节点最大移动速度与平均端到端时延关系图

由图7可知，当网络中节点的运动速度较小时，5种路由协议的路由开销较为接近。随着节点运动速度的增大，由于链路断开频繁，路由开销都在增大，LBHGS-RGR协议采用受限的洪泛机制，减少了路由开销，但是相较于Improved-RGR在路由开销方面提升不大。

图7 节点最大移动速度与路由开销关系图

图8～10显示了网络节点在最大运动速度保持在50 m/s不变的条件下，数据包产生速率对不同种类路由协议性能的影响。

图8 数据包产生速率与分组投递率关系图

由图8可知，随着数据包产生速率的增加，网络出现拥塞的概率增大，部分节点由于缓存溢出开始丢弃数据分组，5种路由协议的分组投递率都在下降，其中AODV协议下降最快，并随着负载增大，下降趋势更加明显，AR-AODV和Improved-RGR性能相近，LBHGS-RGR协议下降趋势则最缓。这是由于LBHGS-RGR协议均衡了网络负载，有效避免了拥塞节点的发生，减少了丢包。

图9为数据包产生速率对网络的平均端到端时延的影响，相比于其他4种路由协议，LBHGS-RGR协议能有效减少平均端到端时延，这主要得益于LBHGS-RGR协议减少了网络拥塞发生的概率，有效降低了数据传输过程中的排队时延。

图9 数据包产生速率与平均端到端时延关系图

由图10可知，当数据包产生速率较小时，网络中的节点负载较轻，5种路由协议的开销相近，随着数据包产生速率的增大，路由协议的开销都在增大。其中，AODV协议和RGR协议的网络开销增加较剧烈，两者的性能相近。AR-AODV和Improved-RGR都未进行负载的均衡，随着数据包产生速率的增加，路由开销相较于LBHGS-RGR协议也较大。而LBHGS-RGR协议通过受限洪泛机制减少了路由请求分组的数量，同时采用负载均衡机制，减少节点拥塞的发生，提高了链路的稳定性，降低了网络的控制开销。

图10 数据包产生速率与路由开销关系图

3 结语

本文针对无人机自组网提出了LBHGS-RGR路由协议，对协议的基于节点负载状态和地理位置信息辅助的受限洪泛机制、GGF模式下高分组成功传输概率的路径选择策略和基于节点负载预测和运动特征的分组转发策略3项关键措施进行了阐述。在分别改变节点最大运动速度和数据包产生速率条件下，通过将LBHGS-RGR路由协议与AODV和RGR协议及其改进型下进行了对比分析。仿真结果表明，LBHGS-RGR路由协议有效改善了网络性能，提高了应对高动态网络环境的能力，能更好地适应无人机自组网。