一种基于SDN 的多约束无人船网络传输路由算法

陈立家，周为，许毅，魏天明，田延飞

1 武汉理工大学 航运学院，湖北 武汉 430063

2 武汉理工大学 内河航运技术湖北省重点实验室，湖北 武汉 430063

3 武汉理工大学 计算机学院，湖北 武汉 430063

4 浙江海洋大学 船舶与海运学院，浙江 舟山 316022

0 引 言

随着智能化技术的不断发展，无人驾驶船舶的概念开始引起全球海事行业的高度关注。2016 年英国罗尔斯·罗伊斯公司（Rolls-Royce）与芬兰阿尔托大学等单位合作启动了“高级自主海上应用”项目，拟于2020 年前推出无人近海货轮产品[1]。中国船级社于2019 年发布了《智能船舶规范（2020）》[2]，该规范介绍了国内外智能船舶技术发展和应用成果。由于无人船与岸基中心数据交互频繁，并且受岸基中心的控制，因此需解决无人船通信网络问题，以保证无人船与岸基中心之间通信网络的稳定性与可靠性。

学者们对无人船与岸基中心的通信问题进行了大量研究。乔大雷等[3]采用窄带物联网（NB-IoT）技术和船舶自动识别系统（AIS）构建了无人船-岸通信链路来解决数据通信问题；张瑞杰等[4]研究了基于信道感知的无人船自组网随机接入协议，可保证无人船组网观测信息传递的可靠性和实时性；崔亚妮等[5]综合网络连通度、链路通信质量、网络连接收益和网络连接成本构建了多无人船网络拓扑优化模型；黄一等[6]针对无人船6 种数据类型的特点，构建了基于时序数据库的无人船信息管理系统拓扑及数据流动模型，为长航时无人船信息存储与通信传输难题提供了解决方法。

上述研究仅对无人船与岸基之间网络的连通性进行了分析，但无人船网络传输过程中不仅需要搭建一个与岸基互通的网络，还需要保证数据传输的稳定性与可靠性。为了解决无人船网络在数据传输时数据量大、时延高等问题，本文拟提出一种基于软件定义网络(software defined network，SDN)的多约束无人船网络传输路由算法(unmanned surface vessel multiple constraint routing algorithm，USMCRA)，并通过仿真实验，验证其在提高网络传输效率和稳定性方面的效果。

1 无人船网络设计

1.1 SDN 无人船架构

SDN 是由美国斯坦福大学提出的一种新型网络架构[7]，随着SDN 网络的不断发展，该构架可适用于多种网络场景。基于SDN 的无人船网络架构主要由数据转发层、SDN 控制层、SDN 应用层组成[8]。其中数据转发层主要负责无人船端的数据采集并将数据交由船载的SDN 交换机进行传输。SDN 控制层是一组SDN 控制器，负责收集网络的拓扑信息，通过南向接口向SDN 交换机下发转发策略[9]。岸基系统作为SDN 应用层主要实现2 个功能：接收由数据转发层发送的数据以及向无人船发送控制信息；通过北向接口开发SDN控制器的应用。网络结构框图如图1 所示。

图1 SDN 无人船网络结构框图Fig. 1 System structure diagram of USV network based on SDN

1.2 网络模型

根据无人船网络结构图设计了网络模型图G(A，B，C，Si，Bi)，如图2 所示，其中A为岸基端，B为无人船端，C为SDN 控制器，Si为近海端交换机节点，Bi为岸端SDN 交换机接入节点，bw1～bw10为带宽，bwi1～bwi7为某条链路上的带宽。网络主要实现从无人船端B至岸基端A的数据传输。控制器C位于网络中心位置，能够收集网络整体信息，负责统筹网络资源和优化流量的路由选择。近海端交换机节点Si主要负责无人船端的数据传输，并根据控制器C下发的规则转发流量数据包。岸基端交换机节点Bi作为一个接入节点主要负责整合Si发送的数据，并将整合数据发送至岸基端。 USMCRA 算法旨在研究Si与Bi之间的链路，确定链路中流量的信息以及路由路径选择。

图2 无人船网络模型图Fig. 2 Network model diagram of USV

式中：ft为端口计数器的数值；α 为时间周期。根据式（1）得到的已用带宽，计算链路中的带宽利用率δ。

式中：ki（t）为t时刻在链路i上已用数据流带宽的大小；mi为链路i中的实际带宽。

通过网络中某条链路的带宽容量mi与控制器计算出的已用带宽容量ki可以求出对应链路中剩余带宽的容量Ri。

2 多约束参数的设定

SDN 交换机负责无人船与岸基系统之间的数据传输，SDN 控制器通过获取网络拓扑图来控制全局网络的链路，控制器与交换机之间通过OpenFlow 协议进行信息交换[10]。交换机通过PACKET_IN 消息传递数据分组到控制器，一般情况下发送的消息属于控制平面的流量。控制器使用PACKET_OUT 消息把数据分组发送给交换机，便于将数据分组通过数据平面转发出去[11]。交换机端口计数器负责统计端口收发的数据包个数和字节数，控制器通过OpenFlow 协议中的状态（STATS）消息周期性地获取交换机统计信息。根据控制器收发统计数据，计算网络传输的路由路径。以下对多约束网络传输路由算法的约束条件进行定义。

2.1 带宽约束

无人船数据通过SDN 网络进行传输时，控制器以时间周期α 询问交换机端口计数器中t时刻的数据字节数统计信息，然后控制器根据一个周期内端口计数器字节数的变化情况，计算出某一时刻某条链路的已用带宽O。

2.2 时延约束

基于SDN 的网络时延计算包含两部分，数据链路层中数据包从一个SDN 交换机到另一SDN交换机的时延，以及SDN 交换机到SDN 控制器的时延[12]。通过SDN 控制器可获取数据收发时间戳的差值，即：转发策略经由交换机S1，交换机S2回到SDN 控制器的时延T1，时延计算原理图如图3 所示。从交换机B到交换机A的原理同上，记此时延为T2。控制器给交换机发送携带有时间戳的命令（request）报文，然后解析交换机返回的回复（reply）报文，获得的往返时间差即为计算交换机到控制器的时延。记控制器到交换机的往返时延分别为Ta，Tb。链路前向和后向的平均时延T为

图3 网络时延原理图Fig. 3 Schematic diagram of network delay

2.3 大小数据流约束

当无人船产生的大量数据在SDN 网络中传输时，需重新选择数据流路径。为了提高网络资源的利用率，应区分数据流的大小，并为大数据流分配路由路径[13]。数据流大小的区分是通过比较计数器中字节数的变化与数据在计数器内持续的时间实现的，数据流的大小分类可通过式（5）来进行判断。

式中：vi(t1)和vi(t0)分别为在第i条链路t1时刻和t0时刻计数器统计端口的字节数；β 为数据流的速率占带宽的比例。通过对β 进行界定即可区分网络中的大小数据流。为适应无人船中不同网络链路带宽，当β＞10%时判定为大数据流[14]。将数据流大小作为USMCRA 算法约束条件之一，可为大流量数据提供高效的路由路径。

3 USMCRA 算法的实现

3.1 基本思想

USMCRA 算法以带宽、时延、数据流大小为约束条件，通过控制器获取网络全局的拓扑结构，设计路由转发策略从而实现网络的优化。

根据图2 的无人船网络模型，无人船端主机为host1，岸基端的监控主机为host2，两主机之间路由路径由近海端路由节点与岸端路由节点组成，主机之间的某条路由路径为pi={l1,l2,···,li,···,ln}， 实 际 带 宽 为b={b1,b2,···,bi,···,bn}。在 选取数据传输的路由路径时，首先根据式（5）确定网络中的大小数据流，然后统计当前链路剩余可用带宽x和链路时延t，由此决定某一链路的路由选择条件即为li= (x,t)。链路当前可用带宽x由当前链路中最小带宽决定，链路时延t由链路总时延决定，因此选取某条链路中的当前可用带宽和时延有：

从式（6）可以看出，数据传输所需要的最小带宽min{x}要小于当前链路中的最小带宽pix，因此选择数据传输的路径需要条件限制，此时受限路由路径集合py为

在总路径p与受限路由路径py之间选取候选路径pz，候选路径中的最大当前可用带宽max{xi}与数据传输的最小延迟min{ti}，结合每条链路上为带宽和时延分配的权重，即可确定无人船网络传输的路由最佳路径[15]，分配权重W的计算公式为

式中：a,b为权重因子。为使得权重W∈(0，1)，规定a+b=1，0＜a＜1，0＜b＜1。

3.2 算法步骤及流程

基于以上链路带宽、时延以及数据流大小的约束条件，以Dijkstra 算法为基础，提出了USMCRA算法。

步骤1） 将各约束参数初始化；数据流大小约束参数β=10%，每条链路的信息为(xi，ti)，循环次数N=0，选取的路由路径为pi。

步骤2） 采用SDN 控制器收集网络视图，获取网络状态信息。根据数据流大小约束条件判断网络中的数据流量，建立网络链路集合。

步骤3） 在网络链路集中通过Dijkstra 算法收集每个节点中的状态信息，并访问节点直到遍历所有节点。

步骤4） 判断所访问的节点构成的路由路径是否满足带宽和时延约束条件，满足条件则进入下一步，不满足条件则返回步骤3）。

步骤5） 通过式（6）和式（7）分别计算路径带宽和时延，对统计的链路状态信息进行排序，建立候选路径表。

步骤6） 候选路径表采用式（8）进行判断，带宽与时延最小的一条链路即为无人船网络路由路径。

USMCRA 算法流程图如图4 所示。

3.3 复杂度分析

若网络中有n个节点，m条边，平均每个点的链路数为m/n，USMCRA 算法需先找出备选路径，此步骤要执行n-1 次，然后根据约束条件遍历网络路径集合N，从中选出与备选路径集u最接近的点。算法时间复杂度计算公式如式（10）所示。

该算法的时间复杂度为O(n2)，通过不同权重的设定选取不同的路径，实现USMCRA 算法[16]。

4 仿真实验

4.1 仿真环境

实验采用mininet 仿真平台。mininet 平台可快速创建支持SDN 的网络，模拟真实环境下的网络工作。通过mininet 实验平台可灵活地为网络添加新功能并进行相关测试，然后部署到真实的硬件环境中[17]。根据无人船网络模型在mininet平台中搭建相似拓扑图，如图5 所示（因图示原因部分节点已省略），采用的控制器为RYU 控制器。

图5 无人船网络拓扑图Fig. 5 Network topology diagram of USV

4.2 USMCRA 算法仿真结果

mininet 平台搭建完成后，采用Python 语言在RYU 控制器中实现USMCRA 算法。在RYU 控制器APP 文件夹中添加如下.py 文件：setting.py，shortest_forwarding.py， network_awareness.py， network_monitor.py，network_delay_detector.py 等。其中network_awareness.py 是用于收集网络信息的模块；network_monitor.py 是用于收集网络流量信息的模块；network_delay_detector.py 是用于收集链路延迟信息的模块；setting.py 是通用设置模块；shortest_forwarding.py 是一个简单的应用程序。在RYU 控制器中执行此文件可运行USMCRA算法。文件结构图如图6 所示。

图6 文件结构图Fig. 6 File structure diagram

首先实现RYU 控制器中的数据采集模块，通过确定β 来区分数据流大小，采用sflow 将交换机端口的数据结果以数据图的形式展现，仿真结果如图7 所示。

图7 S1 端口流量统计图Fig. 7 S1 port flow statistics result

根据代码选取的路由路径如表1 所示，其中Si为网络中交换机的位置；ethi为端口位置。

表1 路由算法路径选择Table 1 Optimal path selection

基于选择的路径，通过iperf 流量工具测试数据的传输速率，并与未添加USMCRA 算法的网络传输速率进行比对，结果如图8 所示。由图可知，由于RYU 控制器收集网络拓扑信息，路由算法还没有为数据流量规划路径，两者在前10 s 内的传输速率较为接近；在10 s 之后RYU 控制器通过算法下发路由转发策略，网络传输速率有较大提高，USMCRA 算法传输速率较正常传输速率提高了16%左右。

图8 数据传输速率Fig. 8 Data transmission rate

衡量网络性能的一个重要指标就是网络传输中的抖动，其代表着网络的稳定性[18]。由图9 可知，USMCRA 算法的网络抖动在0.002 ms 左右，其峰值在0.2 ms，网络的波动较小。对于未添加算法的网络，网络起伏较大，峰值达到了0.9 ms。算法的实现提高了网络的稳定性，减少了网络的波动。

图9 数据传输抖动Fig. 9 Data transmission jitter

通过iperf 测试工具模拟无人船端向岸基端发送10，100，1 000 和10 000 Mbit 不同负载用户数据报协议（UDP）流量包的情况，统计传输不同流量包所需时间，结果如图10 所示。由图可知：基于SDN 的USMCRA 算法优化后的网络在负载较小时传输时间与正常网络传输的时间相差不大；随着网络负载的增大，优化后的网络完成传输的时间缩短，在负载达到104Mbit 时，路由算法优化后的网络较正常网络传输的时间减少了30%。由此可见，USMCRA 算法提高了网络的数据传输能力和对于大数据流量的处理能力，减少了传输时间。

图10 传输不同负载所需时长Fig. 10 Time for different load transmission

由仿真实验结果可知，USMCRA 算法可显著提高无人船网络传输的效率以及传输的稳定性。

5 结 语

针对无人船与岸基中心频繁的数据交互，需确保双方通信过程中网络的稳定性和实时性，本文提出了一种适用于无人船的SDN 架构下多约束无人船网络传输路由算法— USMCRA 算法。该算法采用基于SDN 的无人船网络模型，以网络带宽、时延和数据流大小为约束条件，计算适用于无人船网络的路由路径。

通过mininet 平台进行仿真实验，搭建无人船网络模型，采用USMCRA 算法进行网络优化。仿真实验表明，在高负载情况下，USMCRA 算法使得网络传输时长减少了30%，网络的稳定性也得到了提高。证明本文提出的USMCRA 算法可在一定程度上优化无人船网络通信。