一種基于SDN 的多約束無人船網(wǎng)絡(luò)傳輸路由算法

陳立家，周為，許毅，魏天明，田延飛

1 武漢理工大學(xué) 航運(yùn)學(xué)院，湖北 武漢 430063

2 武漢理工大學(xué) 內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430063

3 武漢理工大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430063

4 浙江海洋大學(xué) 船舶與海運(yùn)學(xué)院，浙江 舟山 316022

0 引 言

隨著智能化技術(shù)的不斷發(fā)展，無人駕駛船舶的概念開始引起全球海事行業(yè)的高度關(guān)注。2016 年英國羅爾斯·羅伊斯公司（Rolls-Royce）與芬蘭阿爾托大學(xué)等單位合作啟動(dòng)了“高級自主海上應(yīng)用”項(xiàng)目，擬于2020 年前推出無人近海貨輪產(chǎn)品[1]。中國船級社于2019 年發(fā)布了《智能船舶規(guī)范（2020）》[2]，該規(guī)范介紹了國內(nèi)外智能船舶技術(shù)發(fā)展和應(yīng)用成果。由于無人船與岸基中心數(shù)據(jù)交互頻繁，并且受岸基中心的控制，因此需解決無人船通信網(wǎng)絡(luò)問題，以保證無人船與岸基中心之間通信網(wǎng)絡(luò)的穩(wěn)定性與可靠性。

學(xué)者們對無人船與岸基中心的通信問題進(jìn)行了大量研究。喬大雷等[3]采用窄帶物聯(lián)網(wǎng)（NB-IoT）技術(shù)和船舶自動(dòng)識(shí)別系統(tǒng)（AIS）構(gòu)建了無人船-岸通信鏈路來解決數(shù)據(jù)通信問題；張瑞杰等[4]研究了基于信道感知的無人船自組網(wǎng)隨機(jī)接入?yún)f(xié)議，可保證無人船組網(wǎng)觀測信息傳遞的可靠性和實(shí)時(shí)性；崔亞妮等[5]綜合網(wǎng)絡(luò)連通度、鏈路通信質(zhì)量、網(wǎng)絡(luò)連接收益和網(wǎng)絡(luò)連接成本構(gòu)建了多無人船網(wǎng)絡(luò)拓?fù)鋬?yōu)化模型；黃一等[6]針對無人船6 種數(shù)據(jù)類型的特點(diǎn)，構(gòu)建了基于時(shí)序數(shù)據(jù)庫的無人船信息管理系統(tǒng)拓?fù)浼皵?shù)據(jù)流動(dòng)模型，為長航時(shí)無人船信息存儲(chǔ)與通信傳輸難題提供了解決方法。

上述研究僅對無人船與岸基之間網(wǎng)絡(luò)的連通性進(jìn)行了分析，但無人船網(wǎng)絡(luò)傳輸過程中不僅需要搭建一個(gè)與岸基互通的網(wǎng)絡(luò)，還需要保證數(shù)據(jù)傳輸?shù)姆€(wěn)定性與可靠性。為了解決無人船網(wǎng)絡(luò)在數(shù)據(jù)傳輸時(shí)數(shù)據(jù)量大、時(shí)延高等問題，本文擬提出一種基于軟件定義網(wǎng)絡(luò)(software defined network，SDN)的多約束無人船網(wǎng)絡(luò)傳輸路由算法(unmanned surface vessel multiple constraint routing algorithm，USMCRA)，并通過仿真實(shí)驗(yàn)，驗(yàn)證其在提高網(wǎng)絡(luò)傳輸效率和穩(wěn)定性方面的效果。

1 無人船網(wǎng)絡(luò)設(shè)計(jì)

1.1 SDN 無人船架構(gòu)

SDN 是由美國斯坦福大學(xué)提出的一種新型網(wǎng)絡(luò)架構(gòu)[7]，隨著SDN 網(wǎng)絡(luò)的不斷發(fā)展，該構(gòu)架可適用于多種網(wǎng)絡(luò)場景?；赟DN 的無人船網(wǎng)絡(luò)架構(gòu)主要由數(shù)據(jù)轉(zhuǎn)發(fā)層、SDN 控制層、SDN 應(yīng)用層組成[8]。其中數(shù)據(jù)轉(zhuǎn)發(fā)層主要負(fù)責(zé)無人船端的數(shù)據(jù)采集并將數(shù)據(jù)交由船載的SDN 交換機(jī)進(jìn)行傳輸。SDN 控制層是一組SDN 控制器，負(fù)責(zé)收集網(wǎng)絡(luò)的拓?fù)湫畔?，通過南向接口向SDN 交換機(jī)下發(fā)轉(zhuǎn)發(fā)策略[9]。岸基系統(tǒng)作為SDN 應(yīng)用層主要實(shí)現(xiàn)2 個(gè)功能：接收由數(shù)據(jù)轉(zhuǎn)發(fā)層發(fā)送的數(shù)據(jù)以及向無人船發(fā)送控制信息；通過北向接口開發(fā)SDN控制器的應(yīng)用。網(wǎng)絡(luò)結(jié)構(gòu)框圖如圖1 所示。

圖1 SDN 無人船網(wǎng)絡(luò)結(jié)構(gòu)框圖Fig. 1 System structure diagram of USV network based on SDN

1.2 網(wǎng)絡(luò)模型

根據(jù)無人船網(wǎng)絡(luò)結(jié)構(gòu)圖設(shè)計(jì)了網(wǎng)絡(luò)模型圖G(A，B，C，Si，Bi)，如圖2 所示，其中A為岸基端，B為無人船端，C為SDN 控制器，Si為近海端交換機(jī)節(jié)點(diǎn)，Bi為岸端SDN 交換機(jī)接入節(jié)點(diǎn)，bw1～bw10為帶寬，bwi1～bwi7為某條鏈路上的帶寬。網(wǎng)絡(luò)主要實(shí)現(xiàn)從無人船端B至岸基端A的數(shù)據(jù)傳輸。控制器C位于網(wǎng)絡(luò)中心位置，能夠收集網(wǎng)絡(luò)整體信息，負(fù)責(zé)統(tǒng)籌網(wǎng)絡(luò)資源和優(yōu)化流量的路由選擇。近海端交換機(jī)節(jié)點(diǎn)Si主要負(fù)責(zé)無人船端的數(shù)據(jù)傳輸，并根據(jù)控制器C下發(fā)的規(guī)則轉(zhuǎn)發(fā)流量數(shù)據(jù)包。岸基端交換機(jī)節(jié)點(diǎn)Bi作為一個(gè)接入節(jié)點(diǎn)主要負(fù)責(zé)整合Si發(fā)送的數(shù)據(jù)，并將整合數(shù)據(jù)發(fā)送至岸基端。 USMCRA 算法旨在研究Si與Bi之間的鏈路，確定鏈路中流量的信息以及路由路徑選擇。

圖2 無人船網(wǎng)絡(luò)模型圖Fig. 2 Network model diagram of USV

式中：ft為端口計(jì)數(shù)器的數(shù)值；α 為時(shí)間周期。根據(jù)式（1）得到的已用帶寬，計(jì)算鏈路中的帶寬利用率δ。

式中：ki（t）為t時(shí)刻在鏈路i上已用數(shù)據(jù)流帶寬的大??；mi為鏈路i中的實(shí)際帶寬。

通過網(wǎng)絡(luò)中某條鏈路的帶寬容量mi與控制器計(jì)算出的已用帶寬容量ki可以求出對應(yīng)鏈路中剩余帶寬的容量Ri。

2 多約束參數(shù)的設(shè)定

SDN 交換機(jī)負(fù)責(zé)無人船與岸基系統(tǒng)之間的數(shù)據(jù)傳輸，SDN 控制器通過獲取網(wǎng)絡(luò)拓?fù)鋱D來控制全局網(wǎng)絡(luò)的鏈路，控制器與交換機(jī)之間通過OpenFlow 協(xié)議進(jìn)行信息交換[10]。交換機(jī)通過PACKET_IN 消息傳遞數(shù)據(jù)分組到控制器，一般情況下發(fā)送的消息屬于控制平面的流量?？刂破魇褂肞ACKET_OUT 消息把數(shù)據(jù)分組發(fā)送給交換機(jī)，便于將數(shù)據(jù)分組通過數(shù)據(jù)平面轉(zhuǎn)發(fā)出去[11]。交換機(jī)端口計(jì)數(shù)器負(fù)責(zé)統(tǒng)計(jì)端口收發(fā)的數(shù)據(jù)包個(gè)數(shù)和字節(jié)數(shù)，控制器通過OpenFlow 協(xié)議中的狀態(tài)（STATS）消息周期性地獲取交換機(jī)統(tǒng)計(jì)信息。根據(jù)控制器收發(fā)統(tǒng)計(jì)數(shù)據(jù)，計(jì)算網(wǎng)絡(luò)傳輸?shù)穆酚陕窂?。以下對多約束網(wǎng)絡(luò)傳輸路由算法的約束條件進(jìn)行定義。

2.1 帶寬約束

無人船數(shù)據(jù)通過SDN 網(wǎng)絡(luò)進(jìn)行傳輸時(shí)，控制器以時(shí)間周期α 詢問交換機(jī)端口計(jì)數(shù)器中t時(shí)刻的數(shù)據(jù)字節(jié)數(shù)統(tǒng)計(jì)信息，然后控制器根據(jù)一個(gè)周期內(nèi)端口計(jì)數(shù)器字節(jié)數(shù)的變化情況，計(jì)算出某一時(shí)刻某條鏈路的已用帶寬O。

2.2 時(shí)延約束

基于SDN 的網(wǎng)絡(luò)時(shí)延計(jì)算包含兩部分，數(shù)據(jù)鏈路層中數(shù)據(jù)包從一個(gè)SDN 交換機(jī)到另一SDN交換機(jī)的時(shí)延，以及SDN 交換機(jī)到SDN 控制器的時(shí)延[12]。通過SDN 控制器可獲取數(shù)據(jù)收發(fā)時(shí)間戳的差值，即：轉(zhuǎn)發(fā)策略經(jīng)由交換機(jī)S1，交換機(jī)S2回到SDN 控制器的時(shí)延T1，時(shí)延計(jì)算原理圖如圖3 所示。從交換機(jī)B到交換機(jī)A的原理同上，記此時(shí)延為T2。控制器給交換機(jī)發(fā)送攜帶有時(shí)間戳的命令（request）報(bào)文，然后解析交換機(jī)返回的回復(fù)（reply）報(bào)文，獲得的往返時(shí)間差即為計(jì)算交換機(jī)到控制器的時(shí)延。記控制器到交換機(jī)的往返時(shí)延分別為Ta，Tb。鏈路前向和后向的平均時(shí)延T為

圖3 網(wǎng)絡(luò)時(shí)延原理圖Fig. 3 Schematic diagram of network delay

2.3 大小數(shù)據(jù)流約束

當(dāng)無人船產(chǎn)生的大量數(shù)據(jù)在SDN 網(wǎng)絡(luò)中傳輸時(shí)，需重新選擇數(shù)據(jù)流路徑。為了提高網(wǎng)絡(luò)資源的利用率，應(yīng)區(qū)分?jǐn)?shù)據(jù)流的大小，并為大數(shù)據(jù)流分配路由路徑[13]。數(shù)據(jù)流大小的區(qū)分是通過比較計(jì)數(shù)器中字節(jié)數(shù)的變化與數(shù)據(jù)在計(jì)數(shù)器內(nèi)持續(xù)的時(shí)間實(shí)現(xiàn)的，數(shù)據(jù)流的大小分類可通過式（5）來進(jìn)行判斷。

式中：vi(t1)和vi(t0)分別為在第i條鏈路t1時(shí)刻和t0時(shí)刻計(jì)數(shù)器統(tǒng)計(jì)端口的字節(jié)數(shù)；β 為數(shù)據(jù)流的速率占帶寬的比例。通過對β 進(jìn)行界定即可區(qū)分網(wǎng)絡(luò)中的大小數(shù)據(jù)流。為適應(yīng)無人船中不同網(wǎng)絡(luò)鏈路帶寬，當(dāng)β＞10%時(shí)判定為大數(shù)據(jù)流[14]。將數(shù)據(jù)流大小作為USMCRA 算法約束條件之一，可為大流量數(shù)據(jù)提供高效的路由路徑。

3 USMCRA 算法的實(shí)現(xiàn)

3.1 基本思想

USMCRA 算法以帶寬、時(shí)延、數(shù)據(jù)流大小為約束條件，通過控制器獲取網(wǎng)絡(luò)全局的拓?fù)浣Y(jié)構(gòu)，設(shè)計(jì)路由轉(zhuǎn)發(fā)策略從而實(shí)現(xiàn)網(wǎng)絡(luò)的優(yōu)化。

根據(jù)圖2 的無人船網(wǎng)絡(luò)模型，無人船端主機(jī)為host1，岸基端的監(jiān)控主機(jī)為host2，兩主機(jī)之間路由路徑由近海端路由節(jié)點(diǎn)與岸端路由節(jié)點(diǎn)組成，主機(jī)之間的某條路由路徑為pi={l1,l2,···,li,···,ln}， 實(shí) 際 帶 寬 為b={b1,b2,···,bi,···,bn}。在 選取數(shù)據(jù)傳輸?shù)穆酚陕窂綍r(shí)，首先根據(jù)式（5）確定網(wǎng)絡(luò)中的大小數(shù)據(jù)流，然后統(tǒng)計(jì)當(dāng)前鏈路剩余可用帶寬x和鏈路時(shí)延t，由此決定某一鏈路的路由選擇條件即為li= (x,t)。鏈路當(dāng)前可用帶寬x由當(dāng)前鏈路中最小帶寬決定，鏈路時(shí)延t由鏈路總時(shí)延決定，因此選取某條鏈路中的當(dāng)前可用帶寬和時(shí)延有：

從式（6）可以看出，數(shù)據(jù)傳輸所需要的最小帶寬min{x}要小于當(dāng)前鏈路中的最小帶寬pix，因此選擇數(shù)據(jù)傳輸?shù)穆窂叫枰獥l件限制，此時(shí)受限路由路徑集合py為

在總路徑p與受限路由路徑py之間選取候選路徑pz，候選路徑中的最大當(dāng)前可用帶寬max{xi}與數(shù)據(jù)傳輸?shù)淖钚⊙舆tmin{ti}，結(jié)合每條鏈路上為帶寬和時(shí)延分配的權(quán)重，即可確定無人船網(wǎng)絡(luò)傳輸?shù)穆酚勺罴崖窂絒15]，分配權(quán)重W的計(jì)算公式為

式中：a,b為權(quán)重因子。為使得權(quán)重W∈(0，1)，規(guī)定a+b=1，0＜a＜1，0＜b＜1。

3.2 算法步驟及流程

基于以上鏈路帶寬、時(shí)延以及數(shù)據(jù)流大小的約束條件，以Dijkstra 算法為基礎(chǔ)，提出了USMCRA算法。

步驟1） 將各約束參數(shù)初始化；數(shù)據(jù)流大小約束參數(shù)β=10%，每條鏈路的信息為(xi，ti)，循環(huán)次數(shù)N=0，選取的路由路徑為pi。

步驟2） 采用SDN 控制器收集網(wǎng)絡(luò)視圖，獲取網(wǎng)絡(luò)狀態(tài)信息。根據(jù)數(shù)據(jù)流大小約束條件判斷網(wǎng)絡(luò)中的數(shù)據(jù)流量，建立網(wǎng)絡(luò)鏈路集合。

步驟3） 在網(wǎng)絡(luò)鏈路集中通過Dijkstra 算法收集每個(gè)節(jié)點(diǎn)中的狀態(tài)信息，并訪問節(jié)點(diǎn)直到遍歷所有節(jié)點(diǎn)。

步驟4） 判斷所訪問的節(jié)點(diǎn)構(gòu)成的路由路徑是否滿足帶寬和時(shí)延約束條件，滿足條件則進(jìn)入下一步，不滿足條件則返回步驟3）。

步驟5） 通過式（6）和式（7）分別計(jì)算路徑帶寬和時(shí)延，對統(tǒng)計(jì)的鏈路狀態(tài)信息進(jìn)行排序，建立候選路徑表。

步驟6） 候選路徑表采用式（8）進(jìn)行判斷，帶寬與時(shí)延最小的一條鏈路即為無人船網(wǎng)絡(luò)路由路徑。

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

3.3 復(fù)雜度分析

若網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)，m條邊，平均每個(gè)點(diǎn)的鏈路數(shù)為m/n，USMCRA 算法需先找出備選路徑，此步驟要執(zhí)行n-1 次，然后根據(jù)約束條件遍歷網(wǎng)絡(luò)路徑集合N，從中選出與備選路徑集u最接近的點(diǎn)。算法時(shí)間復(fù)雜度計(jì)算公式如式（10）所示。

該算法的時(shí)間復(fù)雜度為O(n2)，通過不同權(quán)重的設(shè)定選取不同的路徑，實(shí)現(xiàn)USMCRA 算法[16]。

4 仿真實(shí)驗(yàn)

4.1 仿真環(huán)境

實(shí)驗(yàn)采用mininet 仿真平臺(tái)。mininet 平臺(tái)可快速創(chuàng)建支持SDN 的網(wǎng)絡(luò)，模擬真實(shí)環(huán)境下的網(wǎng)絡(luò)工作。通過mininet 實(shí)驗(yàn)平臺(tái)可靈活地為網(wǎng)絡(luò)添加新功能并進(jìn)行相關(guān)測試，然后部署到真實(shí)的硬件環(huán)境中[17]。根據(jù)無人船網(wǎng)絡(luò)模型在mininet平臺(tái)中搭建相似拓?fù)鋱D，如圖5 所示（因圖示原因部分節(jié)點(diǎn)已省略），采用的控制器為RYU 控制器。

圖5 無人船網(wǎng)絡(luò)拓?fù)鋱DFig. 5 Network topology diagram of USV

4.2 USMCRA 算法仿真結(jié)果

mininet 平臺(tái)搭建完成后，采用Python 語言在RYU 控制器中實(shí)現(xiàn)USMCRA 算法。在RYU 控制器APP 文件夾中添加如下.py 文件：setting.py，shortest_forwarding.py， network_awareness.py， network_monitor.py，network_delay_detector.py 等。其中network_awareness.py 是用于收集網(wǎng)絡(luò)信息的模塊；network_monitor.py 是用于收集網(wǎng)絡(luò)流量信息的模塊；network_delay_detector.py 是用于收集鏈路延遲信息的模塊；setting.py 是通用設(shè)置模塊；shortest_forwarding.py 是一個(gè)簡單的應(yīng)用程序。在RYU 控制器中執(zhí)行此文件可運(yùn)行USMCRA算法。文件結(jié)構(gòu)圖如圖6 所示。

圖6 文件結(jié)構(gòu)圖Fig. 6 File structure diagram

首先實(shí)現(xiàn)RYU 控制器中的數(shù)據(jù)采集模塊，通過確定β 來區(qū)分?jǐn)?shù)據(jù)流大小，采用sflow 將交換機(jī)端口的數(shù)據(jù)結(jié)果以數(shù)據(jù)圖的形式展現(xiàn)，仿真結(jié)果如圖7 所示。

圖7 S1 端口流量統(tǒng)計(jì)圖Fig. 7 S1 port flow statistics result

根據(jù)代碼選取的路由路徑如表1 所示，其中Si為網(wǎng)絡(luò)中交換機(jī)的位置；ethi為端口位置。

表1 路由算法路徑選擇Table 1 Optimal path selection

基于選擇的路徑，通過iperf 流量工具測試數(shù)據(jù)的傳輸速率，并與未添加USMCRA 算法的網(wǎng)絡(luò)傳輸速率進(jìn)行比對，結(jié)果如圖8 所示。由圖可知，由于RYU 控制器收集網(wǎng)絡(luò)拓?fù)湫畔?，路由算法還沒有為數(shù)據(jù)流量規(guī)劃路徑，兩者在前10 s 內(nèi)的傳輸速率較為接近；在10 s 之后RYU 控制器通過算法下發(fā)路由轉(zhuǎn)發(fā)策略，網(wǎng)絡(luò)傳輸速率有較大提高，USMCRA 算法傳輸速率較正常傳輸速率提高了16%左右。

圖8 數(shù)據(jù)傳輸速率Fig. 8 Data transmission rate

衡量網(wǎng)絡(luò)性能的一個(gè)重要指標(biāo)就是網(wǎng)絡(luò)傳輸中的抖動(dòng)，其代表著網(wǎng)絡(luò)的穩(wěn)定性[18]。由圖9 可知，USMCRA 算法的網(wǎng)絡(luò)抖動(dòng)在0.002 ms 左右，其峰值在0.2 ms，網(wǎng)絡(luò)的波動(dòng)較小。對于未添加算法的網(wǎng)絡(luò)，網(wǎng)絡(luò)起伏較大，峰值達(dá)到了0.9 ms。算法的實(shí)現(xiàn)提高了網(wǎng)絡(luò)的穩(wěn)定性，減少了網(wǎng)絡(luò)的波動(dòng)。

圖9 數(shù)據(jù)傳輸抖動(dòng)Fig. 9 Data transmission jitter

通過iperf 測試工具模擬無人船端向岸基端發(fā)送10，100，1 000 和10 000 Mbit 不同負(fù)載用戶數(shù)據(jù)報(bào)協(xié)議（UDP）流量包的情況，統(tǒng)計(jì)傳輸不同流量包所需時(shí)間，結(jié)果如圖10 所示。由圖可知：基于SDN 的USMCRA 算法優(yōu)化后的網(wǎng)絡(luò)在負(fù)載較小時(shí)傳輸時(shí)間與正常網(wǎng)絡(luò)傳輸?shù)臅r(shí)間相差不大；隨著網(wǎng)絡(luò)負(fù)載的增大，優(yōu)化后的網(wǎng)絡(luò)完成傳輸?shù)臅r(shí)間縮短，在負(fù)載達(dá)到104Mbit 時(shí)，路由算法優(yōu)化后的網(wǎng)絡(luò)較正常網(wǎng)絡(luò)傳輸?shù)臅r(shí)間減少了30%。由此可見，USMCRA 算法提高了網(wǎng)絡(luò)的數(shù)據(jù)傳輸能力和對于大數(shù)據(jù)流量的處理能力，減少了傳輸時(shí)間。

圖10 傳輸不同負(fù)載所需時(shí)長Fig. 10 Time for different load transmission

由仿真實(shí)驗(yàn)結(jié)果可知，USMCRA 算法可顯著提高無人船網(wǎng)絡(luò)傳輸?shù)男室约皞鬏數(shù)姆€(wěn)定性。

5 結(jié) 語

針對無人船與岸基中心頻繁的數(shù)據(jù)交互，需確保雙方通信過程中網(wǎng)絡(luò)的穩(wěn)定性和實(shí)時(shí)性，本文提出了一種適用于無人船的SDN 架構(gòu)下多約束無人船網(wǎng)絡(luò)傳輸路由算法— USMCRA 算法。該算法采用基于SDN 的無人船網(wǎng)絡(luò)模型，以網(wǎng)絡(luò)帶寬、時(shí)延和數(shù)據(jù)流大小為約束條件，計(jì)算適用于無人船網(wǎng)絡(luò)的路由路徑。

通過mininet 平臺(tái)進(jìn)行仿真實(shí)驗(yàn)，搭建無人船網(wǎng)絡(luò)模型，采用USMCRA 算法進(jìn)行網(wǎng)絡(luò)優(yōu)化。仿真實(shí)驗(yàn)表明，在高負(fù)載情況下，USMCRA 算法使得網(wǎng)絡(luò)傳輸時(shí)長減少了30%，網(wǎng)絡(luò)的穩(wěn)定性也得到了提高。證明本文提出的USMCRA 算法可在一定程度上優(yōu)化無人船網(wǎng)絡(luò)通信。