一種工業互聯網平臺下的路由策略設計

武帆， 王聰慧

(陜西工業職業技術學院 電氣工程學院，陜西 咸陽 712000)

0 引言

傳統的工業企業中，工業網絡組網、信息化建設存在很多問題，由于各個設備的協議標準并不統一，導致工業應用之間無法互相通信，網絡信息流受限[1]。隨著5G技術在我國的商業化，使得將互聯網引入工業網絡中成為現實。5G通信的高帶寬、低時延、高可靠和廣連接特性也為工業互聯網[2]的無線傳輸和應用提供了可能。然而，傳統互聯網中的路由策略基本為盡力而為的策略，不可避免的出現了如丟包、傳輸時延增大等問題[3]，這在工業網絡中是不能被接受的，工業互聯網要求網絡傳輸應具有可靠性、實時性和優先性[4]，例如需要對生產現場某設備發送一個控制指令信息，如果延時很長，則會對工業生產造成不可預測的后果。因此我們需要對工業互聯網下的路由策略進行設計改進，降低時延，保證優先性[5]。

背壓算法[6]是一種分布式自適應的路由調度算法，能較好地控制網絡擁塞，提高網絡吞吐量，在網絡高負載情況下表現良好。但背壓算法在低負載情況下時延較大[7]，且無法滿足工業互聯網中數據包分優先等級傳輸的要求。為此，本文提出了一種改進的背壓算法，優化算法中的積壓差計算方式，在鏈路權值中加入優先級函數，使得數據傳輸時延有效降低，高優先級數據更快到達目的節點。最后進行仿真實驗，仿真結果表明本算法能夠改善低負荷情況下的時延較大的問題，同時使數據傳輸具有優先性，滿足實際工業互聯網的路由轉發需求。

1 背壓算法分析

1.1 背壓算法描述

背壓策略是由文獻[8]提出，用于路由路徑選擇的算法，該算法用背壓值來決定數據分發的路徑。背壓值越大，說明結點積壓的數據包越多，故給與其更大的轉發機會。

設在一個多跳網絡中，有V個結點，L條鏈路，鏈路都為雙向通信，用無向圖G=(V,L)來表示。網絡中有J個源節點和目標節點不盡相同的單播信息流數據，在工業互聯網中通常為指令數據，由各個工業單元發出，定義為Data={d1,d2,…dj}。時間被分割為多個時隙，在任意時隙上我們可知網絡中每個節點的各個數據包的積壓情況。

首先計算積壓差。(Vp,Vq)∈L為一條路徑，指結點Vq為結點Vp的相鄰結點，Vf為網絡某信息流df的終點結點，計算結點Vp和結點Vq之間的信息流數據包的隊列的積壓差，且規定積壓差的值為非負數，如式(1)。

(1)

然后計算路徑權重。路徑(Vp,Vq)上可能有多個數據流需要傳輸，計算出每個數據流在該路徑上的積壓差，然后取其中的最大值為路徑(Vp,Vq)上的權重值，計算方法如式(2)。

(2)

最后進行調度策略的選擇。計算出各條路徑的背壓差，再結合每條路徑的傳輸速率λVp,Vq，完成最優調度策略優化，最優傳輸路徑集合σ(t)如式(3)。

(3)

其中，Π表示可用來調度且互不干擾的路經集合；σ表示路徑調度集合。在該時隙，路徑(Vp,Vq)在路由調度策略下將最優種類的數據包dpq(t)從結點Vp傳輸到結點Vq。

1.2 算法分析

背壓算法在多個傳輸信息需要通過信道時，優先讓等待時間差較大的數據包傳輸。計算的積壓差越大，數據應優先發送，從而實現傳輸效率的最優化。然而當網絡剛開始傳輸數據時，整個網絡中的負載都比較小，計算出的積壓差很小，導致調度策略不容易選擇下一轉發結點，有可能出現積壓差相等無法選擇路徑只能隨機發送的情況[9]。這時調度策略的時延會大大增加。如圖1所示。

圖1 網絡輕負荷狀態下結點積壓差

以圖1中網絡狀態為例，網絡中傳輸一種dk數據流，各個節點在圖中用圓來表示結點，圓外的數字表示該數據流在本結點所對應的隊列長度，各條鏈路上的傳輸速率相同。以a結點傳輸數據包為例，e結點為數據流目的節點，可以看到，a結點與相鄰任意節點的積壓差都為0，背壓策略無法提供合適的方案，數據包只能隨機選擇結點進行發送。因此，當網絡規模較大且負載較小時，背壓算法的效果較差，網絡性能下降，出現較大傳輸轉發時延，有待優化。

在工業互聯網平臺下，數據的重要性并不一樣。例如，一條指令數據操作一個機械臂抓取貨物，與一條報表數據上傳給上位數據中心，這兩條數據流在轉發時，如果指令數據發生比較大的時延，可能會對工業生產帶來較大的損失和安全問題；相反，類似上述的報表數據這種不是特別重要的信息數據流發生一定的滯后和延遲，則不會特別影響整體的工業研發與生產。因此，對于工業互聯網路由的數據轉發和性能優化，設計數據優先級是有必要的。

2 路由方案設計

2.1 設計思路

背壓算法是基于兩個相鄰結點的積壓差來進行調度，只考慮了一跳內。圖1中a結點向e結點發送數據，可以考慮加入一跳之外的一些信息來修正積壓差，使得數據能夠更加傾向于向目的結點進行轉發，從而改善積壓差較小時算法時延較大的問題。

為了實現上述功能，我們嘗試使用當前結點到目的結點的最小跳數作為修正量對積壓差進行修正，使得數據流偏向于目的結點進行轉發。在圖1中，a結點與c、d、b、f、g、x、y、z結點的積壓差都為0，加入距離目的結點的最小跳數之后的修正量值為式(4)—式(6)。

(4)

(5)

(6)

積壓差修正，a點與b-d的積壓差相同，如式(7)。

(7)

a點與f、g的積壓差相同為式(8)。

(8)

a點與x、y、z的積壓差相同為式(9)。

(9)

因此b、c、d點的積壓差最大，數據流向這3個結點進行轉發。

然而當幾個相鄰結點到達目的結點的跳數也相同時，這樣的優化又失去了作用，如上述分析中的b、c、d點的修正積壓差相同，路由只能在這3個結點中隨機選擇一個進行數據包轉發。考慮加入各個轉發結點的其他所有信息流的數據轉發隊列長的均值，因為這個均值可以反映該結點上待轉發數據的多少，如果該值較大，說明此結點上擁塞的數據包較多，最好不選擇該結點轉發。故我們可將各個結點所能容納的最大隊列MaxLength與各個信息流數據的隊列均值求差，即式(10)。

(10)

將此值加入到積壓差中，再次修正積壓差。

對積壓差進行修正后，計算路徑的權值。在計算權值時，考慮為其乘以優先級函數，如果數據優先級較高，則其乘積越大，計算出的背壓越大，優先轉發的幾率越高。

2.2 目標修正函數與優先函數

根據上小節分析，我們引入了目標修正(Target Refinement, TR)函數，其作用是調整各個結點間計算出的背壓算法的積壓差值，使得信息數據包向著目的結點轉發，且選擇轉發傳輸壓力較小的結點進行跳轉。

(11)

TR函數的表達式為式(12)。

(12)

對積壓差修正完成后，開始計算鏈路的背壓。在式(2)中加入重要數據包優先(Important Packet First, IPF)函數，用來加大優先級較高的數據流的背壓，加快其轉發的速率，降低其時延。加入IPF函數后，路徑背壓算式變為式(13)。

(13)

IPF函數的形式為式(14)。

IPFdf(t)=ηdf(t)·e-ρdf(t)

(14)

式中，ρdf(t)為數據流df的優先級，數值越小優先級越高，從數據報文中解析得到該值；ηdf(t)為優先系數，根據網絡的不同而定，以確保高優先級數據的背壓足夠大。

2.3 轉發策略的工作流程

在每個時隙的開始，我們就可以計算出每個結點上的各個數據流隊列長度的均值，由于上個時隙只轉發了一個數據包，因此只需對上個時隙計算出的值進行修正，然后計算原始隊列差值，再根據上文式(11)和式(12)計算TR函數修正過的積壓差值，再從數據流中取出數據包的優先等級，計算IPF函數，得到路徑背壓差。根據各條路徑上的速率，找到權值最大的路徑進行數據包傳輸，如圖2所示。

圖2 提出路由策略的工作流程圖

在計算TR函數時，到目的結點的跳數可以在網絡拓撲組建完成之時就計算出來，算法中需要用到某個結點到另一結點的跳數時直接使用即可。因此，無論TR函數還是IPF函數，其計算的時間復雜度都是在常數復雜度O(1)上，因此并不增加原始背壓算法的時間復雜度。

3 仿真測試分析

為比較原背壓策略與提出的工業互聯網平臺的路由優化策略的性能，我們進行了實驗仿真。仿真平臺使用MATLAB 2017b。

實驗采用了GEANT網絡拓撲結構，如圖3所示。設置網絡結點20個，待傳輸數據150種，不同結點之間的跳數在組網時已預先計算完成。各個結點在每個時隙根據請求速率進行數據包轉發。考慮做兩組對比實驗：原始背壓算法和改進后的算法在數據流優先級相同時的性能對比，以及原始算法同一數據在不同優先級情況下的性能對比。其網絡參數全部保持一致，如表1所示。

圖3 仿真網絡拓撲圖

表1 仿真參數

我們采用數據轉發的時延大小作為算法性能比較的量化指標。首先定義時延和總時延的概念。時延指某個數據從發送結點到接收結點所需要花費的時長，總時延指各種數據從其發送結點到接收結點的時長總和。

設置仿真時間為200個時隙，調整請求速率，在第一組對比試驗中記錄總時延作為比較指標，進行5次實驗取平均值；在第二組實驗中固定請求速率，調整4個數據內容的優先級，對比這4組數據的發送時延與原始算法時延的關系。

仿真結果如圖4和圖5所示。在仿真測試中可以看到，當所有數據流優先級相同時，改進的路由策略在總時延上比原方案降低了21%，最大降低了39.5%，優化效果比較明顯。在給4組數據分別給與從高到低的四個優先級后，發現最低優先級數據比原算法轉發時延大了36%，而最高優先級的數據轉發時延比原始算法中時延減少了54%，轉發時延大大減小。

圖4 優化效果對比

圖5 不同優先級優先級數據轉發時延對比

實驗結果可以看出，設計的路由策略是有效的，引入TR函數和IPF函數后可以達到降低網絡時延和快速發送優先數據包的效果。

4 總結

針對工業互聯網平臺下對路由策略的低時延、優先性的要求進行了分析，提出了一種改進的背壓路由轉發算法，引入TR函數修正積壓差使在網絡低負荷狀態下時延較大的問題得到了一定改善，并設計IPF函數調整背壓使高優先級數據快速通過鏈路。仿真實驗對改進前后的路由策略進行了對比，結果顯示優化后的路由策略在時延上和轉發優先性上有一定的優勢。