0 概述

无人机自组网(Unmanned Aerial Vehicle Ad Hoc Network, UANET)是将无人机作为网络节点, 各节点间相互转发控制指令、自身状态、数据报文等信息, 从而自动连接建立起一个完整的移动网络^[1]。同时, 其通信无需借助地面控制站或卫星等基础通信设施。由于中小型无人机的移动速度约8 m/s~120 m/s^[2], 因此高速率特性导致UANET拓扑变化过于频繁, 链路也变得极不稳定, 严重影响UANET性能^[3-5]。为建立更加可靠的通信网络, 研究UANET路由协议成为该领域的重要课题之一。由于无人机具有定位功能^[6], 因此基于地理位置的路由协议广泛应用于UANET中。

为使基于地理位置的贪婪周边无状态路由(Greedy Perimeter Stateless Routing, GPSR)协议^[7]适应高动态的UANET, 研究人员对GPSR协议做了大量改进。当节点运动速度过大时, GPSR协议维护的邻居列表难以准确反映邻节点的位置信息。自适应信标方案(ABPP)^[8]可以动态调整信标频率, 预测无人机的位置。GPSR-TA协议^[9]采用两跳自适应信标算法, 对通信范围边缘的邻节点移入与移出进行感知。GPSR-TAMP协议^[10]在GPSR-TA协议的基础上使用邻节点移动预测算法, 对邻节点位置进行实时更新。MP-GPSR协议^[11]预测邻节点位置的同时考虑链路生存时间, 以提高链路稳定性。但这些协议在遇到路由空洞时, 数据转发效率急剧下降。为此, EA-GPSR协议^[12]在选择下一跳节点时, 同时考虑节点位置、剩余能量和能量收集能力, 防止空洞继续变大。MPGR协议^[13]通过2跳周界转发, 降低路由空洞的影响。NEW-GPSR协议^[14]采用一种新的空洞处理算法, 将空洞节点作为树根, 对空洞树进行拆分, 有效降低空洞节点的通信量。但以上协议大多是在遇到路由空洞时做出改进, 或者是仅考虑了路由空洞而忽略了邻节点位置信息的精确度。

为提前避开路由空洞, 同时提高邻节点位置信息的精确度, 建立更加可靠的通信链路, 本文提出一种基于邻节点筛选的GPSR(GPSR Based on Neighbor Node Screening, GPSR-NS)协议。

1 GPSR协议

GPSR协议是一种应用在无线网络方面的路由协议^[7]。该协议通过其一跳邻节点的位置信息找出下一跳转发节点, 无需维护路由表, 是一种无状态的路由协议。GPSR协议通过周期性的HELLO机制使每个节点都维护一个邻居列表, 当节点要发送或转发数据分组时, 根据邻居列表选择下一跳节点。GPSR协议将贪婪转发和周边转发相结合。在通常情况下, GPSR协议采用贪婪转发模式进行数据转发, 下一跳节点是距离目的节点最近且比自身距离目的节点更近的节点。如果找不到合适的节点, 即出现路由空洞现象, 则贪婪转发失效, 此时, 切换到周边转发模式。该模式借助平面图和右手法则绕过空洞, 直至找到比空洞节点更接近目的节点的下一跳节点, 才会再次切换到贪婪转发模式。依此反复, 直到将数据分组传送到目的节点。

GPSR协议虽然简单、高效, 但仍存在以下问题:

1) 该协议在贪婪转发时, 没有考虑路由空洞问题, 仅在遇到路由空洞时采取措施, 路由效率低。

2) 周期性的HELLO机制使网络在高动态环境下维护的邻节点信息不够精确, 影响下一跳节点的选择。

3) 该协议在贪婪转发时仅将邻节点与目的节点的欧式距离作为判断依据, 考虑较单一, 导致链路断裂的风险高。

4) GPSR协议使用右手法则绕过空洞, 虽避免了协议的失效, 但该法则较随意且路由代价大, 所选路由非最优路由。

2 GPSR-NS协议

本文提出一种GPSR-NS协议。当节点发送或者转发数据时, 首先采用失效节点筛选机制, 剔除已失效的邻节点, 同时更新邻节点位置; 其次采用空洞节点筛选机制, 剔除下一跳可能成为空洞节点的邻节点; 最后使用原始贪婪转发模式对数据进行转发。当邻居列表为空或贪婪转发失败时, 转换到周边转发模式。

2.1 HELLO消息修改

HELLO消息在GPSR协议中用于获取邻节点位置信息。在GPSR协议中, 每隔HELLO消息周期时间, 节点会将自己的位置信息广播出去。而GPSR-NS协议所使用的邻居预测算法和空洞节点筛选机制需要获取邻节点速度、与x轴正方向的夹角及其一跳邻居列表。为此, 需对HELLO消息添加相应字段, 修改后的HELLO消息格式见表 1。

2.2 失效节点筛选机制

当节点运动速度增大时, 周期性的HELLO机制将导致邻列表中所维护的信息不能准确反映邻节点的位置, 甚至还维护已移出当前节点通信范围的邻节点。而原始贪婪转发所选的下一跳节点大多在通信边缘处, 其移出当前节点通信范围的可能性更大。若数据包发向已失效的邻节点处, 则其将丢失且需重传, 严重影响数据包发送成功率, 降低通信可靠性。同时, 非最优的邻节点会使路由跳数变大, 从而导致数据包传输时延和路由开销增大。

为避免这一现象, 提高邻节点的有效性, 引入邻节点预测算法, 预判邻节点当前时刻的位置。由于无人机在很短的一段时间内, 速度、运行方向可以看作固定不变^[15], 因此采用匀速直线运动的计算方式来预测节点位置。

若当前节点接收HELLO消息后, 记录t₀时刻邻节点的位置为(x_t0, y_t0), 速度为v, 运动方向与水平方向的夹角为θ, 则当前节点在t时刻可根据式(1)、式(2)预测该邻节点的当前位置。

$ {{x_t} = {x_{{t_0}}} + v\left( {t - {t_0}} \right)\cos \theta } $

(1)

$ {{y_t} = {y_{{t_0}}} + v\left( {t - {t_0}} \right)\sin \theta } $

(2)

通过预测判断该邻节点是否在当前节点的通信范围内, 若在, 则更新邻列表中该邻节点的位置信息为(x_t, y_t); 否则剔除该邻节点。

假设节点S为当前转发节点, 节点D为目的节点。图 1为t₀时刻节点S的邻节点分布情况。将节点S的所有一跳邻节点组成的集合记为X={A, B, C, E, F, G}。

图 2为节点S在t时刻预测的邻节点分布情况, 由此可知节点G已经移出节点S的通信范围, 即节点G对节点S来说已成为失效节点, 则剔除失效节点后的邻节点集合可记为X₁={A, B, C, E, F}。

2.3 空洞节点筛选机制

当原始协议遇到路由空洞时, 采用平面化算法与右手准则寻找下一跳节点。该策略没有提前感知空洞节点的出现, 且在处理空洞时算法复杂, 降低了数据转发效率。

为避免所选邻节点为空洞节点, 设计空洞节点筛选机制剔除下一跳可能成为空洞节点的邻节点。该机制提前感知空洞节点的出现, 以免将数据包发往错误的路径上, 提高数据包的转发效率。空洞节点筛选机制是通过检测邻节点的一跳邻节点中是否有比该邻节点到目的节点近的节点, 若有, 则该邻节点有效; 否则邻节点无效, 将被剔除。为此, 需要维护节点的两跳邻列表, 两跳邻列表的具体格式见表 2。

为降低开销, 该机制首先遍历所有一跳邻节点, 找出距离目的节点比自身近的节点, 将这些节点记为待定邻节点; 然后判断待定邻节点为有效邻节点还是无效邻节点; 最后将无效邻节点剔除。如图 3所示, 待定的邻节点集合为X₂={C, E, F}。

空洞节点分布情况如图 4所示, 其中穿过节点S、C、E、F的虚弧线分别表示以目的节点D为圆心, 以距离d_SD、d_CD、d_ED和d_FD为半径的圆弧。待定邻节点C的一跳邻居为E、F、S、H、I, 由于节点I到目的节点D的距离比自身C到目的节点D的距离近, 因此待定邻节点C为有效邻节点。待定邻节点E的一跳邻居为C、F、S, 没有任何一跳邻节点到目的节点D的距离比自身E到目的节点D的距离近, 因此待定邻节点E为无效邻节点。同理, 待定邻节点F为有效邻节点, 因此有效邻节点集合为X₂={C, F}。

3 仿真结果与分析 3.1 仿真环境

为验证GPSR-NS协议的性能, 利用网络仿真软件NS2.35在相同条件下对GPSR协议、MP-GPSR协议和GPSR-NS协议进行仿真分析。

由于多架无人机间的飞行高度相对水平, 因此仿真场景设置为平面图。同时, 为使仿真数据具有可靠性, 对同一速度范围下的50个场景进行性能分析, 取平均值作为最终结果, 其他参数设置见表 3。

3.2 结果分析

本文主要通过平均端到端时延、丢包率、路由开销、网络吞吐量等4个评价参数来验证GPSR、MP-GPSR和GPSR-NS协议的性能。其中, 平均端到端时延是指所有分组从源节点发送到目的节点接收的时间差的均值, 丢包率是指仿真期间丢失数据分组数量与发送数据分组数量的比值, 路由开销是指路由消息总数据量与接收分组总数据量的比值, 网络吞吐量是指单位时间内网络节点平均收到的数据包数量。

图 5为GPSR、MP-GPSR和GPSR-NS协议的平均端到端时延。当节点最大速度为100 m/s时, GPSR协议的平均端到端时延为1.93 s, MP-GPSR协议的平均端到端时延为1.07 s, GPSR-NS协议的平均端到端时延为0.83 s。经比较, GPSR-NS协议的平均端到端时延相比GPSR协议降低了56.79%, 相比MP-GPSR协议降低了21.94%。GPSR-NS协议中结合邻预测算法, 避免数据转发到失效邻节点或非最优邻节点处, 降低数据包重传的可能性, 同时提前对空洞节点做出预判, 降低数据包遇到路由空洞的概率, 有效减少路由跳数及传输时延, 从而提高数据包转发效率。

图 6为GPSR、MP-GPSR和GPSR-NS这3种协议的丢包率。当节点最大速度为100 m/s时, GPSR协议的丢包率为82.98%, MP-GPSR协议的丢包率为78.68%, GPSR-NS协议的丢包率为55.99%。经比较, GPSR-NS协议的丢包率相比GPSR协议降低了32.53%, 相比MP-GPSR协议降低了28.84%。GPSR-NS协议对邻节点进行位置预测时, 剔除已失效的邻节点, 避免数据包传输到失效节点处导致数据包丢失。因此, GPSR-NS协议可有效提高数据转发的成功率, 进而增强网络传输可靠性。

图 7为GPSR、MP-GPSR和GPSR-NS这3种协议的路由开销。当节点最大速度为100 m/s时, GPSR协议的路由开销为5.66, MP-GPSR协议的路由开销为4.57, GPSR-NS协议的路由开销为2.79。经比较, GPSR-NS协议的路由开销相比GPSR协议降低了50.67%, 相比MP-GPSR协议降低了38.81%。GPSR-NS协议精准的邻节点位置可有效减少路由跳数, 同时结合空洞节点筛选机制, 提前避开空洞节点, 防止数据转发到空洞节点处而采用平面图结合右手准则的方式绕行空洞带来的额外开销。因此, GPSR-NS协议可有效降低路由开销。

图 8为GPSR、MP-GPSR和GPSR-NS这3种协议的网络吞吐量。当节点最大速度为100 m/s时, GPSR协议的网络吞吐量为1.61 kb/s, MP-GPSR协议的网络吞吐量为1.97 kb/s, GPSR-NS协议的网络吞吐量为3.99 kb/s。经比较, GPSR-NS协议的网络吞吐量相比GPSR协议提高了147.86%, 相比MP-GPSR协议提高了102.12%。当节点高速运动时, 网络拓扑结构变化剧烈, 链路频繁断裂, 数据包不能稳定传输。但GPSR-NS协议避开失效的邻节点与可能成为空洞的邻节点, 可以建立更加稳定且可靠的通信, 有效提高网络吞吐量。

4 结束语

针对动态UANET链路不稳定和通信不可靠的问题, 通过在GPSR协议中提高邻节点位置的精确度和数据转发效率, 提出一种GPSR-NS协议。该协议采用失效节点筛选机制, 使数据能够更精确地进行传输, 避免将数据传输到失效的邻节点处, 有效提高了链路可靠性。结合空洞节点筛选机制, 对所有下一跳邻节点是否会成为空洞节点做出预判, 提前避开可能成为空洞的节点, 有效提高数据的转发效率。仿真结果表明, 与GPSR、MP-GPSR协议相比, GPSR-NS协议平均端到端时延分别降低56.79%、21.94%, 丢包率分别降低32.53%、28.84%, 路由开销分别降低50.67%、38.81%, 网络吞吐量分别提高147.86%、102.12%。但该算法在选择下一跳邻节点时未考虑节点的负载量, 当网络传输的数据量较大时, 容易造成网络拥塞现象, 因此, 实现网络负载均衡及降低算法复杂度将是下一步的研究重点。