一種工業(yè)互聯(lián)網(wǎng)平臺(tái)下的路由策略設(shè)計(jì)

武帆， 王聰慧

(陜西工業(yè)職業(yè)技術(shù)學(xué)院 電氣工程學(xué)院，陜西 咸陽(yáng) 712000)

0 引言

傳統(tǒng)的工業(yè)企業(yè)中，工業(yè)網(wǎng)絡(luò)組網(wǎng)、信息化建設(shè)存在很多問(wèn)題，由于各個(gè)設(shè)備的協(xié)議標(biāo)準(zhǔn)并不統(tǒng)一，導(dǎo)致工業(yè)應(yīng)用之間無(wú)法互相通信，網(wǎng)絡(luò)信息流受限[1]。隨著5G技術(shù)在我國(guó)的商業(yè)化，使得將互聯(lián)網(wǎng)引入工業(yè)網(wǎng)絡(luò)中成為現(xiàn)實(shí)。5G通信的高帶寬、低時(shí)延、高可靠和廣連接特性也為工業(yè)互聯(lián)網(wǎng)[2]的無(wú)線傳輸和應(yīng)用提供了可能。然而，傳統(tǒng)互聯(lián)網(wǎng)中的路由策略基本為盡力而為的策略，不可避免的出現(xiàn)了如丟包、傳輸時(shí)延增大等問(wèn)題[3]，這在工業(yè)網(wǎng)絡(luò)中是不能被接受的，工業(yè)互聯(lián)網(wǎng)要求網(wǎng)絡(luò)傳輸應(yīng)具有可靠性、實(shí)時(shí)性和優(yōu)先性[4]，例如需要對(duì)生產(chǎn)現(xiàn)場(chǎng)某設(shè)備發(fā)送一個(gè)控制指令信息，如果延時(shí)很長(zhǎng)，則會(huì)對(duì)工業(yè)生產(chǎn)造成不可預(yù)測(cè)的后果。因此我們需要對(duì)工業(yè)互聯(lián)網(wǎng)下的路由策略進(jìn)行設(shè)計(jì)改進(jìn)，降低時(shí)延，保證優(yōu)先性[5]。

背壓算法[6]是一種分布式自適應(yīng)的路由調(diào)度算法，能較好地控制網(wǎng)絡(luò)擁塞，提高網(wǎng)絡(luò)吞吐量，在網(wǎng)絡(luò)高負(fù)載情況下表現(xiàn)良好。但背壓算法在低負(fù)載情況下時(shí)延較大[7]，且無(wú)法滿足工業(yè)互聯(lián)網(wǎng)中數(shù)據(jù)包分優(yōu)先等級(jí)傳輸?shù)囊?。為此，本文提出了一種改進(jìn)的背壓算法，優(yōu)化算法中的積壓差計(jì)算方式，在鏈路權(quán)值中加入優(yōu)先級(jí)函數(shù)，使得數(shù)據(jù)傳輸時(shí)延有效降低，高優(yōu)先級(jí)數(shù)據(jù)更快到達(dá)目的節(jié)點(diǎn)。最后進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果表明本算法能夠改善低負(fù)荷情況下的時(shí)延較大的問(wèn)題，同時(shí)使數(shù)據(jù)傳輸具有優(yōu)先性，滿足實(shí)際工業(yè)互聯(lián)網(wǎng)的路由轉(zhuǎn)發(fā)需求。

1 背壓算法分析

1.1 背壓算法描述

背壓策略是由文獻(xiàn)[8]提出，用于路由路徑選擇的算法，該算法用背壓值來(lái)決定數(shù)據(jù)分發(fā)的路徑。背壓值越大，說(shuō)明結(jié)點(diǎn)積壓的數(shù)據(jù)包越多，故給與其更大的轉(zhuǎn)發(fā)機(jī)會(huì)。

設(shè)在一個(gè)多跳網(wǎng)絡(luò)中，有V個(gè)結(jié)點(diǎn)，L條鏈路，鏈路都為雙向通信，用無(wú)向圖G=(V,L)來(lái)表示。網(wǎng)絡(luò)中有J個(gè)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)不盡相同的單播信息流數(shù)據(jù)，在工業(yè)互聯(lián)網(wǎng)中通常為指令數(shù)據(jù)，由各個(gè)工業(yè)單元發(fā)出，定義為Data={d1,d2,…dj}。時(shí)間被分割為多個(gè)時(shí)隙，在任意時(shí)隙上我們可知網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的各個(gè)數(shù)據(jù)包的積壓情況。

首先計(jì)算積壓差。(Vp,Vq)∈L為一條路徑，指結(jié)點(diǎn)Vq為結(jié)點(diǎn)Vp的相鄰結(jié)點(diǎn)，Vf為網(wǎng)絡(luò)某信息流df的終點(diǎn)結(jié)點(diǎn)，計(jì)算結(jié)點(diǎn)Vp和結(jié)點(diǎn)Vq之間的信息流數(shù)據(jù)包的隊(duì)列的積壓差，且規(guī)定積壓差的值為非負(fù)數(shù)，如式(1)。

(1)

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

(2)

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

(3)

其中，Π表示可用來(lái)調(diào)度且互不干擾的路經(jīng)集合；σ表示路徑調(diào)度集合。在該時(shí)隙，路徑(Vp,Vq)在路由調(diào)度策略下將最優(yōu)種類的數(shù)據(jù)包dpq(t)從結(jié)點(diǎn)Vp傳輸?shù)浇Y(jié)點(diǎn)Vq。

1.2 算法分析

背壓算法在多個(gè)傳輸信息需要通過(guò)信道時(shí)，優(yōu)先讓等待時(shí)間差較大的數(shù)據(jù)包傳輸。計(jì)算的積壓差越大，數(shù)據(jù)應(yīng)優(yōu)先發(fā)送，從而實(shí)現(xiàn)傳輸效率的最優(yōu)化。然而當(dāng)網(wǎng)絡(luò)剛開(kāi)始傳輸數(shù)據(jù)時(shí)，整個(gè)網(wǎng)絡(luò)中的負(fù)載都比較小，計(jì)算出的積壓差很小，導(dǎo)致調(diào)度策略不容易選擇下一轉(zhuǎn)發(fā)結(jié)點(diǎn)，有可能出現(xiàn)積壓差相等無(wú)法選擇路徑只能隨機(jī)發(fā)送的情況[9]。這時(shí)調(diào)度策略的時(shí)延會(huì)大大增加。如圖1所示。

圖1 網(wǎng)絡(luò)輕負(fù)荷狀態(tài)下結(jié)點(diǎn)積壓差

以圖1中網(wǎng)絡(luò)狀態(tài)為例，網(wǎng)絡(luò)中傳輸一種dk數(shù)據(jù)流，各個(gè)節(jié)點(diǎn)在圖中用圓來(lái)表示結(jié)點(diǎn)，圓外的數(shù)字表示該數(shù)據(jù)流在本結(jié)點(diǎn)所對(duì)應(yīng)的隊(duì)列長(zhǎng)度，各條鏈路上的傳輸速率相同。以a結(jié)點(diǎn)傳輸數(shù)據(jù)包為例，e結(jié)點(diǎn)為數(shù)據(jù)流目的節(jié)點(diǎn)，可以看到，a結(jié)點(diǎn)與相鄰任意節(jié)點(diǎn)的積壓差都為0，背壓策略無(wú)法提供合適的方案，數(shù)據(jù)包只能隨機(jī)選擇結(jié)點(diǎn)進(jìn)行發(fā)送。因此，當(dāng)網(wǎng)絡(luò)規(guī)模較大且負(fù)載較小時(shí)，背壓算法的效果較差，網(wǎng)絡(luò)性能下降，出現(xiàn)較大傳輸轉(zhuǎn)發(fā)時(shí)延，有待優(yōu)化。

在工業(yè)互聯(lián)網(wǎng)平臺(tái)下，數(shù)據(jù)的重要性并不一樣。例如，一條指令數(shù)據(jù)操作一個(gè)機(jī)械臂抓取貨物，與一條報(bào)表數(shù)據(jù)上傳給上位數(shù)據(jù)中心，這兩條數(shù)據(jù)流在轉(zhuǎn)發(fā)時(shí)，如果指令數(shù)據(jù)發(fā)生比較大的時(shí)延，可能會(huì)對(duì)工業(yè)生產(chǎn)帶來(lái)較大的損失和安全問(wèn)題；相反，類似上述的報(bào)表數(shù)據(jù)這種不是特別重要的信息數(shù)據(jù)流發(fā)生一定的滯后和延遲，則不會(huì)特別影響整體的工業(yè)研發(fā)與生產(chǎn)。因此，對(duì)于工業(yè)互聯(lián)網(wǎng)路由的數(shù)據(jù)轉(zhuǎn)發(fā)和性能優(yōu)化，設(shè)計(jì)數(shù)據(jù)優(yōu)先級(jí)是有必要的。

2 路由方案設(shè)計(jì)

2.1 設(shè)計(jì)思路

背壓算法是基于兩個(gè)相鄰結(jié)點(diǎn)的積壓差來(lái)進(jìn)行調(diào)度，只考慮了一跳內(nèi)。圖1中a結(jié)點(diǎn)向e結(jié)點(diǎn)發(fā)送數(shù)據(jù)，可以考慮加入一跳之外的一些信息來(lái)修正積壓差，使得數(shù)據(jù)能夠更加傾向于向目的結(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，從而改善積壓差較小時(shí)算法時(shí)延較大的問(wèn)題。

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

(4)

(5)

(6)

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

(7)

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

(8)

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

(9)

因此b、c、d點(diǎn)的積壓差最大，數(shù)據(jù)流向這3個(gè)結(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。

然而當(dāng)幾個(gè)相鄰結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)的跳數(shù)也相同時(shí)，這樣的優(yōu)化又失去了作用，如上述分析中的b、c、d點(diǎn)的修正積壓差相同，路由只能在這3個(gè)結(jié)點(diǎn)中隨機(jī)選擇一個(gè)進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)。考慮加入各個(gè)轉(zhuǎn)發(fā)結(jié)點(diǎn)的其他所有信息流的數(shù)據(jù)轉(zhuǎn)發(fā)隊(duì)列長(zhǎng)的均值，因?yàn)檫@個(gè)均值可以反映該結(jié)點(diǎn)上待轉(zhuǎn)發(fā)數(shù)據(jù)的多少，如果該值較大，說(shuō)明此結(jié)點(diǎn)上擁塞的數(shù)據(jù)包較多，最好不選擇該結(jié)點(diǎn)轉(zhuǎn)發(fā)。故我們可將各個(gè)結(jié)點(diǎn)所能容納的最大隊(duì)列MaxLength與各個(gè)信息流數(shù)據(jù)的隊(duì)列均值求差，即式(10)。

(10)

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

對(duì)積壓差進(jìn)行修正后，計(jì)算路徑的權(quán)值。在計(jì)算權(quán)值時(shí)，考慮為其乘以優(yōu)先級(jí)函數(shù)，如果數(shù)據(jù)優(yōu)先級(jí)較高，則其乘積越大，計(jì)算出的背壓越大，優(yōu)先轉(zhuǎn)發(fā)的幾率越高。

2.2 目標(biāo)修正函數(shù)與優(yōu)先函數(shù)

根據(jù)上小節(jié)分析，我們引入了目標(biāo)修正(Target Refinement, TR)函數(shù)，其作用是調(diào)整各個(gè)結(jié)點(diǎn)間計(jì)算出的背壓算法的積壓差值，使得信息數(shù)據(jù)包向著目的結(jié)點(diǎn)轉(zhuǎn)發(fā)，且選擇轉(zhuǎn)發(fā)傳輸壓力較小的結(jié)點(diǎn)進(jìn)行跳轉(zhuǎn)。

(11)

TR函數(shù)的表達(dá)式為式(12)。

(12)

對(duì)積壓差修正完成后，開(kāi)始計(jì)算鏈路的背壓。在式(2)中加入重要數(shù)據(jù)包優(yōu)先(Important Packet First, IPF)函數(shù)，用來(lái)加大優(yōu)先級(jí)較高的數(shù)據(jù)流的背壓，加快其轉(zhuǎn)發(fā)的速率，降低其時(shí)延。加入IPF函數(shù)后，路徑背壓算式變?yōu)槭?13)。

(13)

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

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

(14)

式中，ρdf(t)為數(shù)據(jù)流df的優(yōu)先級(jí)，數(shù)值越小優(yōu)先級(jí)越高，從數(shù)據(jù)報(bào)文中解析得到該值；ηdf(t)為優(yōu)先系數(shù)，根據(jù)網(wǎng)絡(luò)的不同而定，以確保高優(yōu)先級(jí)數(shù)據(jù)的背壓足夠大。

2.3 轉(zhuǎn)發(fā)策略的工作流程

在每個(gè)時(shí)隙的開(kāi)始，我們就可以計(jì)算出每個(gè)結(jié)點(diǎn)上的各個(gè)數(shù)據(jù)流隊(duì)列長(zhǎng)度的均值，由于上個(gè)時(shí)隙只轉(zhuǎn)發(fā)了一個(gè)數(shù)據(jù)包，因此只需對(duì)上個(gè)時(shí)隙計(jì)算出的值進(jìn)行修正，然后計(jì)算原始隊(duì)列差值，再根據(jù)上文式(11)和式(12)計(jì)算TR函數(shù)修正過(guò)的積壓差值，再?gòu)臄?shù)據(jù)流中取出數(shù)據(jù)包的優(yōu)先等級(jí)，計(jì)算IPF函數(shù)，得到路徑背壓差。根據(jù)各條路徑上的速率，找到權(quán)值最大的路徑進(jìn)行數(shù)據(jù)包傳輸，如圖2所示。

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

在計(jì)算TR函數(shù)時(shí)，到目的結(jié)點(diǎn)的跳數(shù)可以在網(wǎng)絡(luò)拓?fù)浣M建完成之時(shí)就計(jì)算出來(lái)，算法中需要用到某個(gè)結(jié)點(diǎn)到另一結(jié)點(diǎn)的跳數(shù)時(shí)直接使用即可。因此，無(wú)論TR函數(shù)還是IPF函數(shù)，其計(jì)算的時(shí)間復(fù)雜度都是在常數(shù)復(fù)雜度O(1)上，因此并不增加原始背壓算法的時(shí)間復(fù)雜度。

3 仿真測(cè)試分析

為比較原背壓策略與提出的工業(yè)互聯(lián)網(wǎng)平臺(tái)的路由優(yōu)化策略的性能，我們進(jìn)行了實(shí)驗(yàn)仿真。仿真平臺(tái)使用MATLAB 2017b。

實(shí)驗(yàn)采用了GEANT網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，如圖3所示。設(shè)置網(wǎng)絡(luò)結(jié)點(diǎn)20個(gè)，待傳輸數(shù)據(jù)150種，不同結(jié)點(diǎn)之間的跳數(shù)在組網(wǎng)時(shí)已預(yù)先計(jì)算完成。各個(gè)結(jié)點(diǎn)在每個(gè)時(shí)隙根據(jù)請(qǐng)求速率進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)?？紤]做兩組對(duì)比實(shí)驗(yàn)：原始背壓算法和改進(jìn)后的算法在數(shù)據(jù)流優(yōu)先級(jí)相同時(shí)的性能對(duì)比，以及原始算法同一數(shù)據(jù)在不同優(yōu)先級(jí)情況下的性能對(duì)比。其網(wǎng)絡(luò)參數(shù)全部保持一致，如表1所示。

圖3 仿真網(wǎng)絡(luò)拓?fù)鋱D

表1 仿真參數(shù)

我們采用數(shù)據(jù)轉(zhuǎn)發(fā)的時(shí)延大小作為算法性能比較的量化指標(biāo)。首先定義時(shí)延和總時(shí)延的概念。時(shí)延指某個(gè)數(shù)據(jù)從發(fā)送結(jié)點(diǎn)到接收結(jié)點(diǎn)所需要花費(fèi)的時(shí)長(zhǎng)，總時(shí)延指各種數(shù)據(jù)從其發(fā)送結(jié)點(diǎn)到接收結(jié)點(diǎn)的時(shí)長(zhǎng)總和。

設(shè)置仿真時(shí)間為200個(gè)時(shí)隙，調(diào)整請(qǐng)求速率，在第一組對(duì)比試驗(yàn)中記錄總時(shí)延作為比較指標(biāo)，進(jìn)行5次實(shí)驗(yàn)取平均值；在第二組實(shí)驗(yàn)中固定請(qǐng)求速率，調(diào)整4個(gè)數(shù)據(jù)內(nèi)容的優(yōu)先級(jí)，對(duì)比這4組數(shù)據(jù)的發(fā)送時(shí)延與原始算法時(shí)延的關(guān)系。

仿真結(jié)果如圖4和圖5所示。在仿真測(cè)試中可以看到，當(dāng)所有數(shù)據(jù)流優(yōu)先級(jí)相同時(shí)，改進(jìn)的路由策略在總時(shí)延上比原方案降低了21%，最大降低了39.5%，優(yōu)化效果比較明顯。在給4組數(shù)據(jù)分別給與從高到低的四個(gè)優(yōu)先級(jí)后，發(fā)現(xiàn)最低優(yōu)先級(jí)數(shù)據(jù)比原算法轉(zhuǎn)發(fā)時(shí)延大了36%，而最高優(yōu)先級(jí)的數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)延比原始算法中時(shí)延減少了54%，轉(zhuǎn)發(fā)時(shí)延大大減小。

圖4 優(yōu)化效果對(duì)比

圖5 不同優(yōu)先級(jí)優(yōu)先級(jí)數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)延對(duì)比

實(shí)驗(yàn)結(jié)果可以看出，設(shè)計(jì)的路由策略是有效的，引入TR函數(shù)和IPF函數(shù)后可以達(dá)到降低網(wǎng)絡(luò)時(shí)延和快速發(fā)送優(yōu)先數(shù)據(jù)包的效果。

4 總結(jié)

針對(duì)工業(yè)互聯(lián)網(wǎng)平臺(tái)下對(duì)路由策略的低時(shí)延、優(yōu)先性的要求進(jìn)行了分析，提出了一種改進(jìn)的背壓路由轉(zhuǎn)發(fā)算法，引入TR函數(shù)修正積壓差使在網(wǎng)絡(luò)低負(fù)荷狀態(tài)下時(shí)延較大的問(wèn)題得到了一定改善，并設(shè)計(jì)IPF函數(shù)調(diào)整背壓使高優(yōu)先級(jí)數(shù)據(jù)快速通過(guò)鏈路。仿真實(shí)驗(yàn)對(duì)改進(jìn)前后的路由策略進(jìn)行了對(duì)比，結(jié)果顯示優(yōu)化后的路由策略在時(shí)延上和轉(zhuǎn)發(fā)優(yōu)先性上有一定的優(yōu)勢(shì)。