基于节点相对速度的“周界转发”策略改进

杨振伟，许诺

（四川大学电子信息学院，成都610065）

0 引言

在过去的十几年中，人们对使用无人机进行各种应用和服务的兴趣越来越大。无人机（Unmanned Aerial Vehicles，UAVs），已经被证明可以有效地完成更多比较复杂的任务，当它们被部署在同一个系统中时，就形成了一种特殊的飞行自组织网络（Flying Ad-hoc Networks，FANETs）[1]。FANETs 的部署通常是基于任务目的的，其移动模型[2]由所完成任务的需求和性质决定。相比于移动自组网（Mobile Ad-hoc Networks，MANETs）和车载自组网（Vehicle Ad-hoc Networks，VANETs），FANETs 具有特殊的网络拓扑结构，其路由协议需要适应FANETs 的高度动态拓扑结构以及所受的飞行约束条件。因此，用于FANETs 的路由协议应充分考虑到多无人机网络部署的任务需求，网络拓扑结构和仿真移动模型的特点。

在FANETs 网络系统中，无法预先部署可以进行数据收发的通信基站节点，每个节点既是发送数据的通信终端，又是转发数据的路由节点，是一种典型的多跳路由模式。FANETs 网络的独特特性引发了传统网络中不存在的路由问题，需要新的路由算法组织网络通信[3]。随着定位技术的发展和全球定位系统的广泛应用，地理路由协议为物联网、无线传感器网络和无线网状网络等下一代无线网络[4]的发展提供了较为可靠的路由协议。

FANETs 中UAV 节点的快速移动和网络拓扑的频繁更新，导致节点之间的通信链路经常发生中断。路由查询恢复时，路由开销会增加数倍。为了解决路由查询导致路由开销突然增加的问题，学者们提出了各种新的基于地理位置的预测路由协议[2]。本文基于贪婪周界无状态路由（Greedy Perimeter Stateless Routing，GPSR）协议[5]对FANETs 中的路由协议性能开展研究，并对GPSR 协议的“周界转发”策略进行优化。

1 贪婪周界无状态路由协议

GPSR 协议[5]是一种基于地理位置响应迅速且高效的路由协议，已被设计并应用于车载自组织网络和传感器网络，在无人机网络中也有较多应用。GPSR 协议使用节点的地理位置信息来计算路由表进行路由查询，转发数据和控制消息，并且假设所有节点都在拓扑范围内的同一高度。

在GPSR 协议中，节点将它们的位置信息封装在通信数据包的报头中，每个节点发送包含其位置和标识符的信标消息，以便其他节点可以知道其位置和方向，控制分组消息的定期交换使得节点可以建立网络内节点位置表。GPSR 协议的优点之一就是每个节点只需要保存其相邻节点的位置和其他相关信息，减少了节点内存资源的占用。根据不同的网络密度分布，GPSR 协议通过两种模式完成数据的通信传输：贪婪转发和周界转发。

1.1 贪婪转发模式

贪婪转发[6]是基于节点间距离的邻居节点位置计算方法，贪婪转发模式是在源节点的邻居节点集中选择到目的地距离最近的邻居节点作为通信传输的下一跳中继节点。通过信标消息的定期洪泛，每个节点都保存了其邻居节点的位置信息，在下一跳选择中按照贪婪算法选择中继节点，如此不断转发直至到达目的节点。

如图1 所示，从源节点25 向目标节点19 发送消息，依次经过节点28、节点10、节点26、节点29，在每一跳中选择距离目的节点最近的邻居节点，将数据包逐跳转发到目的节点。

在目的节点移动性比较低的情况下，贪婪转发模式提供了相当于有线网络的数据交付成功率。当数据包到达不能执行贪婪转发模式的拓扑区域时，则使用周界转发模式。

图1 贪婪转发模式

1.2 周界转发模式

当贪婪转发策略失败时，将使用周界转发模式。如图2 所示，在源节点S 的可传输范围之内，除了源节点S 本身以外，不存在其他距离目的节点更近的邻居节点，这种情况称之为路由空洞。

如图2 所示，源节点S 和目的节点D 的覆盖范围的重合区域，该区域不包含相邻节点。在这种情况下，协议使用右手定则发送接收到的数据包，传输路径为SABDECS，这种转发模式我们称为周界转发。

图2 周界转发-右手定则

1.3 平面图

周界转发模式可以采用右手定则绕过路由空洞，但是，在某些情况下，周界转发模式可能会进入路由死循环，无法转发至目标节点。

如图3 所示，节点1 和节点25 均为彼此邻居节点集中距离目标节点12 的最近邻节点，数据包在节点1和节点25 之间无限循环转发，会增大网络开销和通信延迟，造成通信链路拥塞。

为解决路由出现死循环的问题，需要删除通信网络拓扑图中功能重合的链路，使之成为平面图。常用的两种处理方法是RNG 平面图和GG 平面图，平面化处理后的网络拓扑图可以有效减少以上路由转发困境，不可达即丢包，减少网络负载。

图3 平面图

2 贪婪周界无状态路由协议的优化

本节在GPSR 协议的基础上引入速度矢量，基于速度矢量对通信网络中的路由中继节点选择方法进行优化[7-9]，在路由计算中引入优化函数E，优先选取与目的节点做靠近运动的节点作为中继节点，对“周界转发”策略进行改进和优化，提高数据交付和网络路由开销。

中继节点R 与目标节点D 之间的运动状态可以概括为三种运动形式：相向运动，相对距离不断缩小；同向运动，相对距离几乎不变；反向运动，相对距离不断扩大。

速度矢量包括节点的瞬时移动方向和速度大小，优化函数E 的值

其中θ为目标节点D 与中继节点R 的速度矢量夹角，v_d 为目标节点D 的速度大小，v_r 为中继节点R的速度大小。e 越大，中继节点R 和目标节点D 之间的相对距离缩小的速度越快，节点链路越稳定。

改进的GPSR（Enhance Greedy Perimeter Stateless Routing，E-GPSR）协议在节点的位置信息和洪泛的信标信息中加入速度矢量，定时进行信息洪泛更新节点位置坐标和节点速度信息。网络中的其他节点接收信标信息，然后在路由表中更新其他节点的位置信息和速度矢量信息。

当源节点需要向目标节点发送信息时，在贪婪算法失效的情况下，分别计算各邻居节点与目标节点的优化函数值e，并结合GPSR 的周界转发策略选取中继节点。

图4 周界转发-E-GPSR

在图4 所示的拓扑网络中，GPSR 协议采用原始的周界转发模式，会造成较大的网络拥塞和数据丢包率，并且数据包无法送到目的节点。为解决数据传输中可能出现的数据包不可达的问题，本节对GPSR 协议的周界转发策略进行优化。节点20 与目标节点D 无法建立可靠连接，右手定则失效，采取回馈机制，在节点1和节点25 中选取合适的中继节点按反方向继续转发数据包。GPSR 协议的周界转发改进策略如下：

GPSR 改进算法

步骤1：洪泛信标消息，更新节点位置信息；

步骤2：源节点S 获取目标节点D 的编号，从路由表中查询D 的位置信息；

步骤3：

（1）若源节点S 的邻居节点中存在距离目的节点D 更近的节点，则采用贪婪转发策略选择此节点作为下一跳中继节点；

（2）若不存在，则采用周界转发策略的右手定则选择中继节点进行转发；

步骤4：若接收到数据不可达信息，则采用“周界转发”优化策略；

步骤5：结束。

3 NS2仿真实验与数据分析

3.1 NS2仿真平台

NS2 仿真平台作为国内外学者研究网络通信的重要模拟平台之一，底层协议采用C++语言编写，可以高效地进行数据运算和具体协议的实现；上层使用OTcl语言，方便用户进行网络组件和环境参数的设置[10]。仿真实验主要参数设置如表1 所示。

表1 仿真参数

本节主要通过标准路由开销和数据包交付率两个指标对GPSR 协议和E-GPSR 协议的路由性能进行对比分析。按照表1 所列参数，在随机生成的场景中重复实验10 次，对实验结果取平均值。

3.2 实验对比分析

（1）标准路由开销（Normalized Routing Overhead）

标准路由开销为仿真过程中由无人机节点发送的数据包总数与传输的所有消息和数据包之和的比值。路由开销的值可以使用以下公式求得：

图5 标准路由开销对比分析

E-GPSR 协议的平均路由开销比GPSR 协议提高了7.6%。当节点个数增加时，网络拓扑节点密度增加，可用路由增多，数据包在网络通信传输中所占比例增加，标准路由开销增加；当节点数目较多时，E-GPSR协议与GPSR 协议性能渐趋一致。

（2）数据包分组到达率（PDR，Packet Delivery Ratio）

数据包分组到达率为网络中目标节点接收到的数据包数量与源节点发送的数据包数量之比。PDR 的值可由下式求得：

在数据包分组到达率方面，E-GPSR 协议均好于GPSR 协议，平均分组到达率提高了5.8%。E-GPSR 协议在数据转发过程中对周界转发模式进行了改进，增加了路由查询路径，提高了数据包的分组到达率。

图6 数据包分组到达率对比分析

4 结语

本文在GPSR 协议周界转发策略的基础上，增加了右手定则路由查询恢复的补充策略。仿真实验表明，E-GPSR 协议稳定性增加，数据包的分组到达率有了一定的提高，在标准路由开销方面也增加了通信数据包的占比；另外，在通信时延方面相较于GPSR 协议有了一定的增加，但是对于网络性能的整体效果影响不大。E-GPSR 协议更加适合低速巡航自组网系统通信。