基于位置信息的船舶编队自组网路由协议设计∗

（武汉第二船舶设计研究所 武汉 430205）

1 引言

随着科技的不断发展，海上船舶装备越来越多，船舶编队协同越来越多。当前的船舶网络并没有构成一个大型的自组网，船舶之间的信息交互和共享能力有待提升［1］，面对海上的突发情况，无法保障船舶编队的通信质量。而Ad-Hoc网络具有无中心，独立组网，自适应更新路由的特点，可以提高船舶之间通信的可靠性［2］。不仅如此，在编队执行任务的过程中会发生不同队形的切换，各节点之间的距离发生变化，通信链路可能会发生断裂，保障编队通信网络的稳定是至关重要的［3］。

目前的Ad-Hoc网络采取的路由策略主要有两种:反应式和先应式，反应式是指当源节点要向目的节点发送报文时，源节点在网络中发起路由查找过程，找到相应的路由后，才开始发送报文，代表协议有AODV［4］。该类协议通过发送时刻感知拓扑进行转发，不需要维持路由，但是寻找路由需要一定的时间，增加了报文传输时延。先应式主要以OLSR［5］、DSDV［6］为主，网络中的每个节点周期性地通过拓扑感知，维持并更新路由表。通过文献［7］中的实验分析可以看出，反应式路由协议分组投递率较为高，但是因为转发之前需要计算路由表，因此时延较高，而先应式路由协议因为每个节点都维持着路由表，因此传输时延较低，但是路由表存在滞后性，链路可能断裂。为了控制报文的丢包率，目前有很多算法结合先应式算法与网络的特点设计链路状态评估方式。比如，在文献［8～9］中通过对节点剩余能量的评估，优先选取剩余能量更高的节点进行转发，保障网络的能量均衡，从而减少了链路断开。

除了上述两种类型的协议，目前有人提出了基于强化学习的 Q-Routing［10～11］，这类协议与先应式和反应式的都不同，其路由表是逐渐收敛形成。该类算法通过定义节点之间转发的反馈策略，不断学习收敛路由表，通过强化学习使节点在动态变化的拓扑结构下自适应切换路由。但是对于不断变化编队网络而言，该算法需要不断学习，路由形成所需收敛时间过多，而在收敛期间，网络的通信性能较差。

根据上述分析，为了保障编队的实时通信，需要采取先应式的路由策略，同时为了减少链路的断开，需要根据编队的网络特点，量化链路状态，并且在此基础上建立最优链路状态拓扑感知模型。因此本文提出了一种基于位置信息的船舶编队自组网路由协议（Location-based Routing for Ship Formation，LRSF）。首先节点之间交互位置信息，通过位置信息的变化预测链路状态，定义链路质量，并在此基础上建立最优链路拓扑感知模型，保障节点感知全网拓扑变化，最后进行路由计算，及时地切换路由，减少链路断开的次数，保障编队通信质量。

2 船舶编队自组网概述

当前海上船舶设备数量和种类越来越多，海上任务主要是以船舶编队的方式执行，船舶编队频繁地变化，难以保障船舶之间通信的可靠性。为了提升船舶编队的通信性能，可以将编队构建成一个移动自组网。当前的船舶编队协同面临一个显著的问题——如何降低队形变换的过程中报文的丢失率，如图1所示。

以图1所示的场景举例，编队从人字形切换到一字形编队，初始时，B与D之间可以直接一跳传输进行通信，随着编队的变换，B与D同时绕着C进行转动，直至呈现一字形，在此过程中，B与D的距离不断地增大直至无法一跳直接通信，需要由C进行转发进行转发。然而当前存在的移动自组网协议，并不能很好地感知节点之间的距离变化，不能及时地进行路由切换，导致B与D之间的通信报文发生丢失。

图1 人字形编队切换至一字形编队

为了解决上述问题，节点需要感知到节点之间相对位置信息的变化并及时切换路由。因此本文考虑通过节点之间的相对移动评估链路质量，使节点感知周围邻居的变化趋势，同时结合节点之间的运动趋势建立拓扑感知模型，保障节点感知全网的变化趋势，最后结合全局拓扑进行路由计算。

3 基于位置信息的船舶编队自组网路由协议设计

3.1 基于位置信息的链路状态量化

船舶编队在队形变换时，节点之间的相对运动趋势不一样，相应的通信链路状态也不一样，为了能够感知链路状态的变化，需要结合节点之间的位置信息变化对链路状态进行评估。在OLSR中并没有考虑链路质量差异，该算法默认每一跳链路具有相同的链路质量，并不符合船舶编队自组网的特点。在文献［12］中提出了基于期望传输次数的链路质量指标，如式（1）所示。

其中R表示两点之间的通信链路，LQ(R)表示R的链路质量，η表示R中的某一跳链路，ETX代表报文从源节点成功发送到目的节点的期望传输次数，φ(η)代表报文经过η的接收成功率，ρ(η)代表反向接收成功率，也即是相应的ACK报文的接收成功率。ETX越小，则链路传输效率越高。对于拓扑变化频率低的移动自组网而言，ETX可以较好地反映链路状态。但是船舶编队中，节点之间的拓扑变化较为频繁，节点之间会因为相对移动而导致链路突然断开，仅仅靠ETX无法真实地反映相对移动节点之间的链路状态。

为了解决这个问题，需要分析节点之间的相对位置变化和链路状态的联系。船舶编队队形变化导致了链路状态发生变化，而节点之间的相对加速度是队形开始变化的一个重要指标，感知节点之间的相对加速度可以预测链路状态。因此本文结合节点之间的相对加速度建立链路质量预测链路状态，链路质量如式（2）所示。

其中LQ(η)表示η的链路质量，节点i与j为一跳链路η的相邻节点，ai,j是节点i，j之间的相对加速度，μ是非负经验参数。在链路拥有相同的ETX情况下，节点之间的相对加速度越大，拓扑变化越剧烈，链路η更容易断开，因此在路由计算中，源节点与目的节点之间选择LQ(R)最小的链路作为通信链路。

相对加速度ai,j如式（3）所示:

其中vi,j(t2)为节点i和j在t2时刻的相对速度，vi,j(t1)为节点i和j在t1时刻的相对速度。vi,j(t2)和vi,j(t1)分别如式（4）、式（5）所示。

其中(xi(t),yi(t),zi(t))代表t时刻i节点的位置坐标，(xj(t),yj(t),zj(t))代表t时刻j节点的位置坐标。

3.2 最优链路状态拓扑感知模型

当前的船舶编队可以利用GPS或者北斗卫星获取实时位置信息，采取上述链路质量评估方式，节点只需知晓邻居节点之间的相对位置信息的变化，便可以预测链路状态变化。但是对于船舶编队移动自组网而言，节点本身的通信范围有限，并不能感知全网的所有链路变化，需要结合拓扑感知模型进行全网拓扑感知，才可以选择最小链路质量的链路进行路由。

目前OLSR采用最少中继节点拓扑感知模型，节点在邻居集合中选取最少的能够覆盖两跳邻居的节点作为中继节点，构成中继节点集合，一跳以外的节点可以通过中继节点与该节点进行通信，为了减少控制开销，只将节点与中继节点集合的链路加入拓扑结构。因为OLSR无法感知相对移动节点之间的链路状态的差异，选取的中继节点的不一定最优，形成的拓扑结构并非最优，以图2所示菱形拓扑场景为例，其中A节点两端来回匀速移动，S、B、D静止，S为源节点，D为目的节点，在OLSR算法下，D一旦选择A加入中继集合，将拓扑A->D发送到网络中洪泛，S只能感知到A->D，无法感知B->D拓扑，只能生成S->A->D的路由。

图2 菱形拓扑场景

为了保证节点尽可能按照最优链路进行转发，本文建立最优链路状态拓扑感知模型。在该模型中，节点优先链路质量最小的邻居节点加入中继节点集合，直至通过该集合可以覆盖所有的两跳邻居节点。在图2所示的场景下，D优先选择B加入中继节点集合，S感知到B->D的拓扑，生成S->B->D的路由。与OLSR的拓扑感知模型相比，最优链路拓扑感知模型可以保证最优的中继节点的链路参与全网的路由计算，提升网络通信的稳定性。

4 仿真实验及结果分析

为了评估LRSF算法的性能，在QualNet上模拟船舶编队变换的场景，比较LRSF和OLSR的网络性能指标。实验场景如图3所示，开始在QualNet上布置了8个节点组成人字形编队，随后经过时间t1切换成一字形，经过时间t2切换成菱形，为了研究算法在不同的拓扑变化快慢场景下的性能，设定多组t1和t2进行多次实验（因为船舶编队从一个队形切换到另一个队形，拓扑的初始状态和结束状态一致，变化的时间越短，拓扑变化越快），本次实验做了五组不同变换时间的对比实验，船舶编队切换时间参数配置如表1所示。

表1 船舶编队切换时间（s）配置

为了评估网络的性能，本文选取如下的网络性能指标。

1）平均端到端时延，如式（7）所示，指的是数据包从源节点发送到目的节点接收所需的时间，反映了路由协议的有效性。

其中表示平均端到端时延，Tr代表接收到数据包的时间，Ts代表发送数据包的时间，N表示发送数据包的个数。

图3 船舶编队切换场景

2）分组投递率，如式（8）所示，定义为到达目的节点的数据包的个数与源节点发送的数据包的个数的比值。投递率反映路由的可靠性，投递率越大，丢失分数据包越少，通信越可靠。

其中Pd指分组投递率，Pr表示目的节点接收数据包的个数，Ps表示源节点发送的数据包的个数。

为了保证实验结果的可靠性，随机选取源节点-目的节点并且设置CBR数据流，进行多次实验，取多次实验的平均结果作为网络性能指标的评估值。

本次实验中，随着编队切换的时间增加，两种算法的分组投递率如图4所示。随着编队变换所用时间的减少，网络拓扑结构剧烈程度增加，OLSR和LRSF的分组投递率都有一定程度的减少，但是LRSF的分组投递率明显高于OLSR，而且在80s以上的编队变化时间范围内，LRSF的分组投递率都在90%左右，而OLSR只有大约70%，LRSF此时的分组投递率远高于OLSR。

图4 分组投递率比较

随着编队切换的时间增加，两种算法的平均端到端时延如图5所示。在编队切换时间60s以上的范围内，OLSR的平均端到端时延一直都是高于LRSF，但是随着编队切换时间的减少，OLSR的时延开始快速下降，而LRSF可以保持平缓，主要是LRSF能够保持一个良好的分组投递率，而OLSR在此期间分组投递率下降较多，导致参与时延统计的报文数量减少，从而统计的平均端到端时延减少。在编队切换时间60s以内的范围，OLSR的平均端到端时延下降至LRSF以下，而LRSF此时的平均端到端时延也存在一定程度的下降，主要原因是此时的编队拓扑结构变化较快，LRSF的分组投递率也存在一定程度的降低。

图5 平均端到端时延比较

综上，在船舶编队进行简单的队形变化时，本文设计的LRSF算法能够保持一个较高的分组投递率，并且端到端时延有所下降，相较于OLSR具有一定的优越性。

5 结语

本文针对海上船舶编队提出了LRSF路由算法，通过实验结果可以看出在面向动态拓扑变化的场景下，LRSF比OLSR具有更高的报文投递率，网络通信更为可靠，尽管牺牲了些许时延，但是并未影响到网络通信的及时性，相较于传统的移动自组网协议具有一定的优越性。尽管如此，本文研究的是简单场景下船舶编队变换，拓扑变化较为单一，一旦发生网络拓扑剧烈或是不规则的变化，LRSF算法也不能保持良好的分组投递率，丢包较多，无法保持良好的通信性能，因此如何应用拓扑控制减少拓扑变化，并与路由算法相结合需要后续进行深入的研究。