一种基于位置预测的无人机辅助海面自组网地理路由算法*

周天香，夏玮玮，燕锋

（东南大学移动通信国家重点实验室，江苏 南京 210096）

0 引言

随着海上活动的增加，海洋环境中的无线通信需求显著增加[1]。为了满足这一不断增长的需求，需要在海上建立有效的通信，传统的通信方式包括卫星通信和岸基通信[2]。然而，卫星通信的传输距离长，信号的时延大，且传输速率有限。至于岸基基站，虽然能提供较高的传输速率，但是基站的通信范围有限，难以覆盖到较远距离的船只[3]。

相比之下，无人机具有更高的灵活性和可移动性[4]。无人机部署在三维空间中，可以扩展视距传输范围。无人机可以充当空中中继，进一步扩大信号传输范围[5]。因此，无人机辅助海面通信具有很大潜力。为了给无人机辅助的海面通信网络提供可靠和高效的信息传输保障，需要设计一种路由算法，能够快速适应网络拓扑的变化，减少数据包的传输时延，提高数据包投递率。

近年来，针对海面自组网和FANETs（Flying Ad Hoc Networks，飞行自组网）的路由算法进行了许多研究。在海面自组网方面，大部分研究集中在验证现有经典路由算法的性能上。文献[6] 和[7] 中基于NS3 平台通过仿真验证了，在海面自组网中，相比于DSR（Dynamic Source Routing，动态源路由）、DSDV（Destination Sequence Distance Vector，目的序列距离向量）和OLSR（Optimized Link State Routing，优化链路状态路由）算法，AODV（Ad Hoc On Demand Distance Vector，自组网按需距离向量）算法具有最佳性能。除此之外，有大量研究致力于改进现有路由算法。文献[1] 提出了航道和机会路由图来模拟船只的相遇机会。然而，该算法需要完整的网络位置信息，且具有较高的时间复杂度，使其难以在海洋大区域内实现。

针对FANETs，GPSR（Greedy Perimeter Stateless Routing，贪心周边无状态路由）算法是最常用的[8]。改进GPSR 性能的主要研究集中在位置预测、路由决策和恢复策略方面。首先，为了减少无人机移动性的影响，在文献[9]和[10]中使用匀速直线运动模型描述无人机的移动。但在实际场景中，无人机不太可能直线移动。文献[11]和[12]使用高斯分布描述无人机移动概率密度函数，提供低误差和平滑的预测结果。在路由决策方面，做贪婪决策时应考虑各种因素。文献[13]和[14]考虑了距离、车辆方向、偏转角度、速度变化和邻居密度。此外，在恢复策略方面，文献[14]使用有限洪泛来跳出路由空洞，可能会导致不必要的带宽浪费。文献[15]提出了3种恢复策略，包括重试、转发到最远的邻居和最佳移动节点等方法。

然而，单纯的海面和无人机自组织网络的路由算法并不适用于异构的无人机辅助海上通信网络。无人机辅助的车联网是一种无人机作为中继辅助通信的异构网络，网络中同时考虑车辆和无人机两类节点。文献[16]、[17]和[18] 中都提出了一种基于十字路口结构的反应式路由算法来广播路线发现请求，目的地节点基于请求消息中封装的信息来计算路径得分，基于得分进行路径选择。文献[19] 中使用蚁群方法改进了反应路由算法。然而无人机辅助的车联网中的路由算法大多是针对特殊的交通场景进行设计的，算法依赖于十字路口的构造，并不适合节点可以任意移动的海面自组网。

针对无人机辅助的海面通信网络场景，本文提出了一种基于位置预测的地理位置路由（Location Prediction Based Routing，LPGR）算法。该算法将预测模型和多因素路由决策相结合。本文的主要研究思路如下：

首先，所提算法采用高斯马尔科夫预测模型来获得节点的准确位置。基于预测位置，转发节点进行多因素的路由决策。如果节点转发失败，则陷入路由空洞，失败节点将发起两跳转发过程来跳出路由空洞。

其次，所提算法在路由决策中考虑多个因素，包括距离、偏转角度、速度差、运动方向角、邻居数量和路径有效期。之后采用主成分分析法来得到各个因素的权重并做出精确的路由决策。

最后，本文搭建了一个基于OMNeT++平台的仿真环境，对比了AODV、GPSR 和LPGR 三种算法的性能，验证了所提算法在端到端时延和数据包投递率方面的良好性能。

1 系统模型

如图1所示，为了简化分析，假设无人机在三维空间中移动，船舶在二维海面上移动，节点的移动模型采用随机路点模型，其中所有无人机和船舶都在网络层运行LPGR协议。每个节点都配备有全球定位系统（Global Position System,GPS）模块，并周期性地向邻居广播信标，每个信标包括了邻居的一些运动信息。在接收到来自邻居的信标后，本节点将邻居的信息保存到其本地邻居表中。其中，在多因素路由决策中，不仅需要位置信息，还需要速度和邻居数量信息。因此，信标字段包括当前位置、速度和邻居数量信息。

图1 系统模型示意图

2 基于位置预测的地理位置路由算法

本文提出了一种基于位置预测的地理位置路由算法，所提算法的完整流程如图2所示。

图2 基于位置预测的地理位置路由算法（LPGR）的流程图

步骤1：当一个节点接收到一个数据包时，它会检查目的节点是否为其本身。如果是，则本次数据传输完成。如果不是，则转到步骤2。

步骤2：节点检查目的节点是否在自身通信范围内。如果是，则将数据包直接发送给目的节点。如果不是，则转到步骤3。

步骤3：节点按照LPGR算法的规则计算下一跳节点。

步骤3.1：节点先进行多因素贪婪转发。基于预测的位置信息，节点在其邻居范围内计算每个邻居的路由决策值，如果存在比自身决策值更低的邻居，则将决策值最低的邻居作为下一跳进行数据包传输。如果不存在，则转到步骤3.2。

步骤3.2：节点陷入路由空洞，发起两跳转发过程，在两跳邻居范围内寻找路由决策值低于自身的节点作为下一跳。如果不存在合适的两跳邻居，则传输失败。

2.1 位置预测模型

在多因素贪婪转发过程中，当前节点根据其本地表中最新更新的邻居位置信息，进行路由决策。由于节点的移动性，在当前时刻邻居的实际位置与本地表中记录的位置不同，可能导致链路断开。如图3所示，在t0时刻，节点B广播信标给节点S，节点S将节点B的位置信息保存到本地邻居表。经过t1-t0时间后，在t1时刻，节点B移动到了B′位置，超出了节点S的通信范围。如果节点S在t1时刻选择数据包转发给节点B，则会导致链路中断，数据丢失。

图3 节点移动性造成的链路中断问题

为了减轻移动性对节点通信性能的影响，有必要预测节点的移动性，在路由决策中使用预测位置进行计算，从而提高网络的连接性能和路由寿命。所提出的算法使用高斯分布来描述无人机移动概率密度函数，进而得到节点的预测位置[12]。移动性预测的目标是基于tn-1时刻的过去位置和移动性特征，获得tn时刻节点的预测位置分布。

本文假设Δt是tn-1和tn之间的单位步长时间，ΔT=tn-tn-1=mΔt，m表示单位时间的数量。节点的速度在时刻tn是随机的。因此速度可以被视为匀速运动，加速度是一系列在Δt期间具有恒定方差ε的高斯白噪声。

对于tn-1和tn之间的第k个单位步长的节点i，x轴上的速度分量用表示，位置分量用x(k)表示，其表达式如下：

根据tn-1时刻的位置，tn时刻x轴的高斯分布的变量可以表示为：

y轴和z轴的变量表达式与x轴类似。

用(xn-1,yn-1,zn-1)表示tn-1时刻的位置，因此在ΔT=tn-tn-1=mΔt之后，到达位置(xn,yn,zn)的概率密度函数可以表示为：

2.2 多因素贪婪转发策略

此外，距离可能不是唯一影响路由决策的因素。如图4所示，当前转发节点S的通信范围内存在2个邻居节点A和B，节点A距离目的节点D的距离最近，但其运动方向与节点D相反。如果根据传统贪婪转发考虑的因素，节点S选择节点A作为下一跳，则数据包可能需要经过更多跳或更大时延才能到达目的节点。

图4 距离和速度因素对路由决策的影响

为避免做出次优选择，在决策中有必要考虑多种影响因素，包括距离、偏转角、速度差、运动方向角、邻居数量和路径有效期。对不同因素值进行线性加权求和得到路由决策值，以改进原有贪婪转发策略。

所考虑的第一个因素是距离，指的是当前节点选择距离目的节点更近的邻居节点。当前节点用Nc表示，则Nc的邻居Ni和目的节点Nd之间的距离f1可以表示为：

所考虑的第二个因素是偏转角。为了减少路由跳数，数据包应该尽量沿着直线方向传输到目的节点，即如图5所示，偏转角希望尽可能小。偏转角f2可以表示为：

图5 路由决策中的多因素因子示意图

表示当前节点Nc的位置坐标，[·]表示矢量的点乘运算。

所考虑的第三个和第四个因素分别是速率差和运动方向角，指的是当前节点会选择在速率和移动方向上更接近目的节点的邻居。邻居Ni和目的节点Nd之间的速率差f3可以表示为：

所考虑的第五个因素是邻居数量。具有更多邻居的邻居节点更有可能找到合适的下一跳。用di表示邻居数量，则有f5=1/di。

所考虑的第六个因素是路径有效期，有效期表示两个节点保持连接的剩余时间[17]。对于路径有效期，可分为两种不同场景讨论：（i）两个节点分布在二维平面中，例如两艘船只；（ii）两个节点分布在三维空间中，例如两架无人机。

场景（i）如图6所示，在二维海平面中，考虑两个速度非零的船只节点Nc和Ni，速率分别为vc和vi，视距通信范围为R，(xc,yc)和(xi,yi)为对应位置坐标，θc和θi为对应速度方位角。则路径有效期可表示为：

其中

场景（ii）如图7所示，在三维空间中，考虑两个速度非零的节点Nc和Ni，速率分别为vc和vi，视距通信范围为R，(xc,yc,zc)和(xi,yi,zi)为对应位置坐标，θc和θi为对应速度方位角，φc和φi为对应速度俯仰角。则路径有效期可表示为：

图7 三维空间的路径有效期示意图

其中

总的路由决策函数可以由上述因素线性加权计算得到

其中ωi(i=1,2,3,4,5,6)表示各个因素对应的权重，满足0 ≤ωi≤ 1，且ω1+ω2+ω3+ω4+ω5+ω6=1。路由决策值越小，该邻居作为下一跳节点转发的质量越高。

2.3 主成分分析法计算因素权重

路由决策中每个因素对于路由决策的贡献可能不同，反映在对应的权重。所提算法采用主成分分析方法来确定权重。主成分分析方法基于各个因素的方差来计算权重，方差大的因素波动越剧烈，可以提供越多的信息量，并对路由决策产生更显著的影响。相反，方差小的因素波动较小，对于路由决策影响更弱。基于主成分分析法来得到各个因素的精确权重，当前转发节点可以做出更精确的路由决策。主成分分析法计算权重的过程如下：

（1）去中心化。求出每个因素的平均值，所有样本减去每个因素的平均值。

（2）计算协方差矩阵C。协方差矩阵可以表示为

其中，cov[·]表示协方差运算。对角线上是各个因素的方差，非对角线上是协方差值。cov(f1,f2) ＞ 0表示如果f1和f2中的一个增加，另一个也会增加。cov(f1,f2) ＜ 0表示如果f1和f2中的一个增加，另一个减小。cov(f1,f2)=0表示这两个因素相互独立。

（3）计算特征值λ和对应的特征向量，其可以表示为：

其中，每个因素的贡献可以通过降序排列的特征值得到。

（4）计算权重。每个因素的权重可以根据相应的特征值，按照下列表达式计算得到：

2.4 两跳转发恢复策略

如果贪婪转发失败，即当前转发节点的邻居决策值中没有比自身更小的，则会陷入路由空洞。在二维平面中，使用构造平面图的方法来从路由空洞中恢复，但利用右手定则的方法不再适用于三维空间。因此所提算法采用两跳转发作为恢复策略。如果陷入路由空洞，贪婪失败节点会在其两跳邻居范围内寻找合适的节点。两跳转发的具体步骤如下：

步骤1：如果贪婪转发失败，失败节点会向其邻居广播两跳请求。两跳请求消息包含的字段如表1所示。

表1 两跳请求的字段

步骤2：每个邻居节点在收到两跳请求后，会根据以下规则选择合适的两跳邻居节点。

步骤2.1：基于GPS模块获得最新时刻的位置和速度，每个邻居计算自身的路由决策值。如果该决策值小于贪婪失败节点的决策值，则邻居节点将返回自身作为下一跳节点。如果不是，则转到步骤2.2。

步骤2.2：每个邻居依次计算其两跳邻居的路由决策值。如果存在两跳邻居的路由决策值小于贪婪失败节点的决策值，则选择其中具有最小决策值的两跳邻居作为两跳节点。如果不存在，则当前邻居不能提供合适的两跳邻居，将返回贪婪失败节点本身。

步骤3：每个邻居节点将计算得到的下一跳节点信息放进两跳响应的字段中，将其发回给贪婪失败节点。两跳响应消息的字段如表2所示。

表2 两跳响应的字段

步骤4：贪婪失败节点在收到两跳响应后，会检查所有响应中的下一跳字段，选择其中决策值最小的节点来完成数据包转发。

3 仿真结果

在本节中，基于OMNeT++模拟器，实现LPGR算法，并将所提算法与AODV算法和GPSR算法进行性能验证，性能指标包括端到端时延与数据包投递率。

3.1 仿真参数设置

本仿真考虑数量级为几十到上百个节点的异构自组网场景，根据被广泛引用的文献[21]中的参数设置，本仿真的关键参数如表3所示。无人机和船只的移动模型为随机路点移动模型，无人机和船只的位置和速度在给定范围内随机生成，每架无人机的高度在50 m到100 m范围内随机生成。采用随机模型可以表示节点移动的平均特征，可以反映出节点的平均移动特征，得到的性能指标也能代表路由算法的平均性能。为研究海面自组网路由算法的性能，仅考虑船只有收发数据包业务，在船只中随机指定源和目的节点发送UDP数据报文，船只既可以作为收发节点，也可以作为中继节点，无人机仅作为中继节点进行数据包转发。

表3 关键参数设置

3.2 对端到端时延的仿真结果

图8表示不同无人机数量下平均端到端时延的变化趋势。如图8中所示，端到端时延随着无人机数量的增加而波动。可以看出，与AODV和GPSR算法相比，所提的LPGR算法具有更低的端到端时延，这可能是由于所提算法使用了预测模型得到了准确的邻居位置，并基于主成分分析法计算的精确权重进行路由决策，更有可能选择高质量的下一跳节点，从而减少了传输跳数和时延。

图8 不同无人机数量下端到端时延示意图（船只数量为40）

图9描述了不同船只数量下的平均端到端时延。从图9可以看出，由于采用了预测位置、多因素路由决策和合适的因素权重，所提出的LPGR算法比其他算法具有更低的时延。此外，从图9可以观察到，所有端到端时延都随着船只数量的增加而上升。产生这种趋势的原因可能是，随着收发节点数量的增加，中继节点的负载更大，需要更多时间来处理数据包并做出路由决策。

图9 不同船只数量下端到端时延示意图（无人机数量为50）

3.3 对数据包投递率的仿真结果

图10显示了在不同无人机数量下三种路由算法的数据包投递率对比情况。如图10所示，相比AODV和GPSR算法，由于所提算法利用预测模型的精确位置信息，并且通过基于优化权重的多因素路由决策中选择下一跳节点，LPGR算法可以提供更高的数据包投递率。基于预测位置做决策，可以减少链路中断的可能性。此外，转发节点以精确的权重做多因素路由决策，更有可能选择合适的下一跳。此外，贪婪失败节点在陷入路由空洞后会发起两跳转发流程，显著提高了数据包的传递率。

图10 不同无人机数量下数据包投递率示意图（船只数量为40）

图11描述了不同船只数量下的数据包投递率变化趋势。从图11可以看出，由于预测位置和精确的路由决策，相比于AODV和GPSR算法，所提出的LPGR算法获得了最高数据包投递率。此外，收发节点数量越多，网络负载越大，拥塞越严重，因此数据包投递率随着船只数量的增加而降低。同时，随着发射节点数量的增加，中继节点必须处理更多的数据包，如果中继节点的处理能力不能满足要求，则可能发生丢包。

图11 不同船只数量下数据包投递率示意图（无人机数量为50）

4 结束语

本文提出了一种基于位置预测的无人机辅助海上自组织网络地理路由算法。为了减少节点移动性的影响，该算法使用高斯马尔科夫预测模型来获得准确的定位。转发节点根据预测的位置进行多因素路由决策。当陷入路由空洞时，转发节点将发起两跳转发流程以从空洞中恢复。该算法采用多因素贪婪转发策略，包括距离、偏转角、速度、移动方向、邻居数量和路径有效期。此外，通过主成分分析法计算出各个因素的权重用于做出精确的路由决策。所提算法应用在数量级为几十到上百个节点的无人机辅助海面自组网场景，仿真结果表明，与AODV 和GPSR 算法相比，所提算法可以显著降低端到端时延，提高数据包投递率，为数据传输提供可靠高效的转发机制。但是所提算法假设每个节点周期性的广播信标，对于移动性强的节点而言，如果周期偏长，可能会导致其邻居中存储的节点位置与实际位置存在较大误差，而周期偏短，会导致网络控制开销过大，影响网络性能。在未来研究中，节点可以根据预测位置和实际位置之间的误差，自适应地发送信标，在降低网络开销的同时保证位置的精确性。