无人机自组网GPSR路由协议研究

祝 经，周新力，宋斌斌，王程民

(海军航空大学， 山东 烟台 264001)

1 引言

随着无人机集群组网应用的发展，无人机自组网协议受到广泛关注，在诸如MAC协议、路由协议、跨层协议、机会网络传输协议等方面均有大量研究[1-2]，其中路由协议是保障无人机自组织网络运行稳定性和节点间可靠通信的关键。根据是否需要地理位置信息辅助，无人机自组网路由协议可分为基于拓扑结构的路由协议和基于地理位置的路由协议两大类[3]。

参考现有文献可以看出，基于地理位置的路由协议在维护邻居列表时所需的开销远小于基于拓扑结构的路由协议在建立和维护路由表时所需的开销[4]。而且，基于地理位置的路由协议具有更强的扩展性且无需考虑网络收敛问题[5]。另外，中小型无人机大多都具有定位功能，对基于地理位置路由协议的运行也提供便利。因此，综合考虑以上特性，在高动态的无人机自组网中，基于地理位置的路由协议具有良好的应用前景。而GPSR协议作为一种典型的基于节点地理位置信息的路由协议，具有扩展性强、健壮性好和适应高动态拓扑等特点，从而已成为最适用于无人机自组网的路由协议之一。

为此，梳理GPSR协议相关研究现状，分析需要进一步优化和改进的研究发展方向，为基于地理位置信息辅助的路由协议更好地用于无人机网络提供进一步深入研究的思路，具有很强的现实意义。

2 GPSR协议概述

GPSR协议中，每个节点将位置、标识符等信息封装在数据包的包头中，并通过周期性相互交换控制消息的方式，获取邻居一跳节点的位置信息，建立邻居列表和节点之间的路由，从而实现对数据包的传输。GPSR协议有贪婪转发(greedy forwarding)和周边转发(perimeter forwarding)[6]2种数据包转发方式。

2.1 贪婪转发

贪婪转发是基于欧几里得距离的邻近度量，其通过选择到目的节点最近的邻居节点作为数据包转发的下一跳节点[7]。此外，贪婪转发通过交换信标消息来进行预先邻居节点发现，使得每个节点在一次交换中拥有其邻居节点的地理位置信息。如图1所示，数据包从源节点S传输至目的节点D。通过选择传输范围内距离目的地最近的节点作为下一跳，数据包被一跳一跳地转发。在目的地移动性非常高的情况下，这种路由模式提供了相当接近有线网络的成功率。但是，当发送节点在其通信范围内没有比本节点距离目的节点更近的节点时，就会出现路由空洞，即局部最小化现象。如图1所示，节点S在寻找到达节点D的路由时，发现单跳通信范围内不存在比S节点距离D节点更近的邻居节点。此时则认为贪婪转发失效，S节点称为局部最小化点。路由空洞就是所有相邻局部最小化点之间的连线所构成的多边形区域。

图1 贪婪转发过程示意图Fig.1 Greedy forwarding process

2.2 周边转发

当数据包传输过程中遇到路由空洞，即贪婪转发算法失败时，为了能将数据包绕过路由空洞继续向前转发，则需切换至周边转发。在周边转发模式中，首先基于平面化算法将网络平面化，然后空洞节点采用右手规则，在比自身距离目的节点远的邻居节点中作出选择，选出下一跳转发节点。如图2所示，节点S的传输范围内，所有其他节点与目的节点之间的距离都大于其自身。因此，节点S切换至周边转发模式，按照右手准则，顺时针遍历该多边形，形成路径:S-A-F，绕过路由空洞。当在节点F处再次符合贪婪转发条件时，则切换模式，形成路径F-D，节点将数据包转发至目的节点D。

图2 周边转发过程示意图Fig.2 Perimeter forwarding process

2.3 平面化算法

GPSR协议采用的平面化算法有：相关邻接图算法(relative neighbor graph，RNG)和加百利图算法(gabriel graph，GG)[7]。2种算法的原理图如图3所示。

RNG算法定义为：节点A，B之间的距离大于或等于任意节点X到2个节点的距离。其表达式为：

∀X≠A，B∶d(A，B)≤max[d(X，A)，d(X，B)]

(1)

GG算法定义为：在以节点A，B间距离为直径的圆内，若不存在任意节点X，则存在两节点A，B之间的边(A，B)。其表达式为：

∀X≠A，B∶d2(A，B)≤[d2(X，A)+d2(X，B)]

(2)

图3 RNG和GG平面化算法原理示意图Fig.3 RNG and GG planarization algorithm

3 GPSR协议研究现状

针对无人机自组织网络中由于节点部署稀疏、节点高速移动等特性可能带来的影响，学者们对GPSR协议展开了广泛的研究和改进，其中主要有如下几个方面。

3.1 协议控制开销优化

基于拓扑结构的路由协议需要知道全局节点的拓扑信息，并建立和维护路由表，而传统的GPSR协议作为典型基于地理位置的路由协议，仅需知道所有一跳邻居节点当前时刻的位置信息，再根据这些位置信息即可完成数据的转发，不需要建立和维护路由表[8]。因此相比基于拓扑结构的路由协议，GPSR协议具有更少的控制开销，传输效率更高，更适用于拓扑结构变化频繁的无人机网络。然而GPSR协议仍可能面临着开销过大的问题[9]，如周边转发模式下的冗余现象，见图4所示。

图4 周边转发冗余现象示意图Fig.4 Perimeter forwarding redundancy

由图4(a)可知，数据包在转发过程中遇到了路由空洞，在网络平面化之后，根据右手规则选择下一跳节点，形成了S-A-B-C-E-F-D的传输路径。而从图4(b)可以发现，如果节点S在遇到路由空洞之后直接将E作为下一跳节点，形成S-E-F-D，将比原来的方式具有更短的路径，即传统的周边转发模式可能会出现绕路的现象。

为了降低车载自组网(vehicular ad hoc network，VANET)中遇到局部最优的可能性，文献[10]设计了一种改进的基于流量密度分层的GPSR协议。在稀疏区域，每个节点维护一个记录其多跳邻居节点的列表，而在稠密区域，每个节点只维护其单跳邻居节点。每个节点会根据外围流量密度的变化而改变策略。仿真结果表明，相比传统GPSR协议，改进后的GPSR协议具有更高的传输速率和更小的控制开销。

文献[11]提出了一种改进版的E-GPSR协议，采用了一种新的机制来代替传统的周边转发模式进行下一跳节点的选择。新的选择机制基于源节点(或中继节点)到目的地的距离加上源节点(或中继节点)到下一跳的距离，从而使得下一跳为总距离最小的邻居。改进的E-GPSR协议经过验证，可以有效地减少传输延迟和控制开销。

文献[12]基于虚拟坐标映射提出了一种有效的空洞绕过路由协议(EVRP)。EVRP通过映射边缘节点在虚拟圆上的坐标，将空白边缘的随机结构转化为规则结构。经过聚类和冗余调度后，每个节点都有一个能量阈值。如果节点的能量低于阈值，则向集群头发送故障消息，集群头利用与故障节点的交角，将其所有邻居视为预备边界节点，同时判断每个预备边界节点。这样就构造了一个虚拟矩形，覆盖产生动态中间目的节点的路由空洞，提高了数据包传输过程中绕过路由空洞的效率和成功率。仿真和分析结果表明，EVRP在寻找最短路由路径方面具有更高的传输率、更小的控制开销和能量消耗。

3.2 路由空洞处理算法优化

由于无人机网络具有稀疏性，节点密度较为稀疏，且当路径上出现阻挡或是通信链路不稳定导致的节点断开，都不可避免地会出现路由空洞现象[13-15]。该空洞既可以是物理上网络无法覆盖的内部区域，也可以是应用程序定义的无法进行数据包路由的交通阻塞区域。

当传统GPSR协议在贪婪转发过程中出现路由空洞现象时，节点根据目标节点和一跳邻居节点的位置信息构造平面图，再使用周边转发的方式，绕开路由空洞，直至满足条件回到贪婪转发状态。在网络节点密度足够密集的条件下，贪婪转发一定可以找到一条最优路径[16]。但是当出现空洞之后，周边转发算法在选择节点时具有一定的随意性，只能保证能够找到一条到达目的节点的路径，但不一定是最优路径，即贪婪转发方法将终止在局部最优，而不是全局最优。并且传统的周边转发方式不仅需要进行多次的转发才能回到贪婪转发状态，在过程中也极容易出现绕路的现象，增加不必要的多跳节点和端到端延时。如果无人机网络部署在不理想的环境中，则将频繁地遇到空洞，从而频繁地切换数据包转发方式，以致可能会带来更多不必要的跳数。同时数据包转发方式的频繁切换，将使数据包的生存周期降低，从而导致数据包丢失的概率增加。因此，传统路由空洞处理算法在应用时仍存在一定的问题，如何优化路由空洞处理算法以提升协议的传输效率，已成为GPSR协议研究的热点。

文献[17]提出了一种新的空洞处理算法，其首先检测出空洞的边界，然后选取边界凸包中的一个节点作为中继节点，最后利用中继节点的信息，将数据包绕空洞转发，从而构造出跳数较少的路径。新提出算法能够较好地处理路由空洞，提高数据包投递率，但由于其较高的算法复杂度，仍面临着端到端延时和控制开销较高的问题。

文献[18]为最大限度地提高分组转发效率，在贪婪转发模式下采用了一种新的路由算法IAPS(interference aware progress speed)，该算法可以估计下一跳节点的转发距离、链路质量和信道访问难度。当数据包转发达到局部最小值时，算法IAPS采用一种基于竞争优势的机会转发方法来绕过空洞区域，从而可以有效地提高网络资源利用率和平均吞吐量，降低无线多跳网络的拥塞损失率。

3.3 链路建立稳定性优化

GPSR协议在工作时，源节点掌握自身位置信息、一跳范围内邻居节点以及目的节点的地理位置信息，并在使用贪婪算法时，根据欧几里得距离来选择下一跳节点[19-20]。下一跳节点通常是邻居节点列表中与目的节点欧几里得距离最小的节点，因此，这样选择的下一跳节点通常处于节点通信范围的边缘。而无人机自组网中通常以无人机作为通信节点，其具有的高速移动特性可能会使所选择的下一跳节点在数据包到达之前就已移出通信范围。如图5所示，源节点S向目的节点D传输数据包。在数据包传输之前，根据贪婪转发的原则，节点S将选择距离目的节点D最近的B作为下一跳节点。当数据包传输的过程中，节点发生移动，S移动到了S′，B移动到了B′，然而B′已经不在S′的通信范围之内，即B′不在S′的邻居节点列表中。这样就会造成数据包无法从S′传输到B′，导致传输链路出现断裂，数据包将出现回传或丢失现象，降低网络的整体性能。

除此之外，由于无人机自组织网络部署环境的复杂性、资源有限性等特点，建立的链路容易由于节点间的通讯干扰、节点休眠、电力耗尽以及数据拥塞等因素而失效[21]，由此就会造成链路稳定性下降，增加丢包率和端到端延时，影响数据包的传输。因此，面对无人机节点高速移动等特性，传统的GPSR协议仍存在一定的局限性，不能够保证节点选择和链路建立的准确性和可靠性，还需进行相关优化来更好地解决问题。

图5 节点移出通信范围现象示意图Fig.5 Node moving out of communication range

文献[22]在原有GPSR路由协议基础上进行了改进，通过选取邻居节点移动方向、链路风险、邻居节点密度和邻近度等4个指标来评估链路质量，可有效地提升包投递率，增加链路的稳定性。

文献[23]提出一种基于预测地理位置的路由协议PGRP，以减少数据包的丢失，提升网络的性能。在PGRP中，每个节点将根据节点的移动方向和角度给相邻节点一个权重，并根据节点移动的加速度预测每个节点在发送hello数据包时的位置。相比传统GPSR协议，PGRP在数据包投递率、平均跳数等方面均有所提升，能够有效地提高链路的稳定性。

文献[24]结合移动预测，提出了一种高效可行的更新算法DBUM。DBUM由主动更新和强制更新2种模式构成，其能够在较少信标流量情况下提高节点位置信息的准确性。评估结果表明：采用DBUM算法的GPSR协议，在提高了地理位置信息准确性的同时，减少了控制开销和端到端延时，较好地克服了节点高移动性对网络整体性能的影响。

3.4 节点能量均衡优化

在无人机自组网中，无人机作为其中的移动节点，能量因素将对其载荷能力产生较大的影响[25]。而GPSR路由协议的贪婪转发机制通常基于欧氏距离来选择下一跳节点进行数据的转发，虽然比较容易实现，但也易造成网络中节点能量分布不均衡，影响网络的整体性能，主要原因如下：

在数据转发过程中，路径上的节点既是主机又是路由器，将承担数据处理和数据转发双重任务，能量消耗较快，容易导致网络中节点的能量不均衡[26]。

贪婪算法在选择下一条节点时，通常只考虑了距离因素，没有考虑节点能量消耗的差异，如图6所示。源节点S在向目的节点D转发数据包时，在N1，N2，N3，N4中往往选取距离目的节点更近的N2作为下一跳节点。当出现热点路由问题时，即如果目的节点D为热点数据源，数据包频繁地传至D，则S-N2-D将成为一条热点路由。热点路由频繁地承担数据转发的任务，例如N2这样热点路由上的节点就可能会出现过早的能量耗尽，从而缩短网络的生存时间。

因此，如何均衡网络中节点的能量，延长网络的生存周期，从而提高协议工作效率成为了GPSR路由协议研究的热点问题[27-28]。

图6 热点路由现象示意图Fig.6 Hotspot routing

文献[29]提出了一种基于地理路由协议的能量均衡贪婪转发路由(EBGR)协议，以实现路由路径的均衡能耗，同时保持分层网络的良好效率和可扩展性。该方法使用剩余跳数代替传统贪婪转发机制中的欧氏距离，结合节点的剩余能级，建立起源节点与汇聚节点之间的路径。

文献[30]引入兴趣梯度和能量梯度的概念来对GPSR协议进行改进。首先，当查询路径建立后，进行数据传输时，根据汇聚节点与事件区域节点发生数据内容的匹配程度确定兴趣阈值，并根据路径能量损耗数据包和传感器节点剩余能量，得到一个固定值作为能量阈值；然后，当节点接近阈值时，网络及时地根据递归贪婪算法和右手规则提前找出一条新的路径到目标区域，从而使节点负载相对均衡。通过这种改进方案，优化后的GPSR协议可以有效地减少网络能耗，并均衡节点能量，达到了延长网络生存周期的目的。

4 GPSR协议研究发展方向

近几年，随着对GPSR协议研究的深入，为更好地适应无人机自组网的工作特点，对一些新颖算法进行优化和改进，逐渐成为专家学者们新的研究发展方向。

4.1 三维优化算法

传统的GPSR路由协议在贪婪转发模式转变至周边转发模式之前，通常需要先采用GG和RNG等2种方式来构建一个二维的平面，再从中根据右手规则进行对下一跳节点的选择[31]。通过这2种平面化算法，可以较好地选择出下一跳节点，保证数据包存在一个路径传至目的节点。但是对于无人机自组网来说，无人机节点通常工作在三维空间中，在二维平面图上的节点选择通常会存在一些偏差，使节点无法找到正确的中间节点，从而可能导致数据包的传输错误，影响数据包传输的效率以及正确性[32]。

文献[33]提出一种改进的GPSR-3D路由协议，其采用表面转发模式来代替周边转发模式。表面转发模式首先基于一种新的三维几何结构将整个网络空间划分为一组子空间，然后根据一种并行多面体遍历算法来恢复局部极小值。仿真结果表明，GPSR-3D具有较高的可靠性、节能性和存储效率，但其控制开销较大且更多地适用于静止的网络中，难以满足无人机自组网中节点高速移动等特性。由此，设计出一种贴合无人机自组网三维工作环境特点的节点选择算法，成为未来的研究热点。

4.2 粒子群优化算法

GPSR协议根据地理位置信息来建立无人机自组网路由，在其贪婪转发选择下一跳节点时，当前节点通常只考虑在其一跳范围内距离目的节点最近的邻居节点，而忽略了丢包严重、节点能量消耗和边界节点易受干扰等问题，网络传输效率和质量实际上并不高[34]。因此，如何更全面地考虑多因素对节点选择的影响已成为协议优化重点关注的问题。

粒子群优化算法是一种较为成熟的群智能优化技术[35]，其可以在每次迭代过程中通过当前所找的个体极值和全局极值来不断更新自己的位置和速度，从而不断向目标位置靠近，最终找到最优解[36]。因此，为尽可能考虑到节点下一跳选择时的多方面因素，实现对无人机自组网中GPSR协议的进一步优化，利用粒子群算法来进行均衡处理可成为下一步研究的方向。

4.3 多径路由算法

传统的GPSR协议采用单路径、多跳的方式来实现数据包的转发。协议中数据包通过多个中间无线节点在单条路径上进行协作转发，每个中间节点将数据包从上一跳转发到下一跳节点。此种传输方式在拓扑变化较小且负载较低的网络中具有控制复杂度低、路径质量高等优点[21]。然而由于无人机自组网节点的高速移动性、部署环境的复杂性以及资源有限性等特点，单条路径容易发生断裂，如何提高链路传输的稳定性已成为一个不可避免的问题。

为解决GPSR协议中单路径传输所面临的问题，多径路由算法能够同时构造和维护多条自源节点到目的节点的路径，并根据网络要求将任务流量分配到一条或多条路径上。与单径路由相比，多径路由算法除了可靠性更高以外，还具有资源利用高效、QoS保证等优点。目前大部分多径路由算法，多以AODV和DSR为代表的基于拓扑结构的路由协议来进行设计，结合基于地理位置的路由协议的研究较少。如何设计出适合GPSR等基于地理位置的路由协议的多径路由算法，还需要研究者们展开更深入的研究工作。

5 结论

近年来，无人机自组网在现代化无人机作战形式中得到越来越多的重视和应用，而无人机自组网路由协议作为无人机自组网通信技术的重要组成部分，更是需要进行大量的研究来满足实际作战的需求。GPSR协议作为一种典型的基于地理位置的无人机自组网路由协议，被实验证明在无人机自组网中具有良好的性能，但仍存在一些问题，影响其更好地应用。本文在阐述了GPSR协议基本概念的同时，对其在无人机自组网中的研究现状和发展方向等方面进行了梳理和讨论，可为无人机自组网GPSR协议的研究提供重要参考。