一種基于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 算法可在一定程度上優化無人船網絡通信。