面向資源均勻使用需求的工業(yè)5G實時調(diào)度方法

田 宇,陳文謠,關(guān)鎖玲,許 馳,夏長清,金 曦

1(中國科學院 網(wǎng)絡化控制系統(tǒng)重點實驗室,沈陽 110016)2(中國科學院 沈陽自動化研究所,沈陽 110016)3(中國科學院 機器人與智能制造創(chuàng)新研究院,沈陽 110169)4(中國科學院大學,北京 100049)5(沈陽工業(yè)大學,沈陽 110870)

1 引 言

隨著無線技術(shù)應用的日益普及,在一些特定工業(yè)場景中無線通訊技術(shù)正逐漸取代有線通訊技術(shù)[1-3].目前,在諸多的無線網(wǎng)絡中,最接近工業(yè)運動控制系統(tǒng)需求的是5G無線傳輸技術(shù),5G所支持的高可靠性超低時延在一定程度上滿足了運動控制系統(tǒng)以及工業(yè)實時系統(tǒng)對無線網(wǎng)絡的基本需求.本文關(guān)注非授權(quán)頻段的私有5G技術(shù),該技術(shù)無需運營商支持,具有靈活性高、可控性高、隱私安全保障性強等特點.但由于非授權(quán)5G使用帶寬有限的ISM(Industrial,Scientific,Medical)頻段,在這種情況下,數(shù)據(jù)傳輸所用資源的分配會對關(guān)鍵數(shù)據(jù)傳輸?shù)膶崟r性造成較大影響,而關(guān)鍵數(shù)據(jù)的實時到達對保證工業(yè)實時控制系統(tǒng)的穩(wěn)定運行具有重要意義.如果數(shù)據(jù)延遲到達,不僅影響實時控制系統(tǒng)的穩(wěn)定運行,還可能導致控制系統(tǒng)的癱瘓,甚至嚴重危害人員生命安全.因此為確保關(guān)鍵數(shù)據(jù)傳輸?shù)膶崟r性,需在低時延5G無線傳輸技術(shù)的基礎(chǔ)上為其分配確定性的傳輸資源.

比如在實時控制的移動機器人系統(tǒng)中,如圖1所示.控制器通過與5G基站相連下發(fā)控制命令,攜帶移動終端的機器人通過5G移動終端接收控制命令并執(zhí)行,進而產(chǎn)生反饋信號通過同一無線鏈路返回到控制器.

在這樣的一個面向運動需求的實時控制系統(tǒng)中,既存在固定周期的周期性數(shù)據(jù),也存在特定事件觸發(fā)的突發(fā)數(shù)據(jù).對于固定周期的時間觸發(fā)數(shù)據(jù),可以進行預先的資源分配,平衡各控制回路之間的資源占用,同時保證各控制回路之間資源占用不沖突,并滿足其截止時間限制.而對于事件觸發(fā)的環(huán)境,動作是按需執(zhí)行的,即由某個事件觸發(fā).事件發(fā)生的時刻無法預知,因此無法預先為其分配資源.現(xiàn)有工業(yè)無線網(wǎng)絡的實時調(diào)度研究中,大部分只關(guān)注時間觸發(fā)數(shù)據(jù)的實時調(diào)度,僅有少量研究考慮了事件觸發(fā)數(shù)據(jù)的傳輸需求,但都為事件觸發(fā)數(shù)據(jù)添加了行為限制條件,例如限制了最短的事件觸發(fā)數(shù)據(jù)生成間隔,限制了事件觸發(fā)數(shù)據(jù)的并發(fā)性等.這些限制使理論模型不同于真實系統(tǒng),相關(guān)研究也無法實際應用.事件觸發(fā)數(shù)據(jù)的生成時間完全隨機,為使任意時刻生成的事件觸發(fā)數(shù)據(jù)都能夠得到所需的傳輸資源,分配給時間觸發(fā)數(shù)據(jù)資源后,剩余的空閑資源應均勻分布在時間維度上.因此本文提出一種時間觸發(fā)數(shù)據(jù)的調(diào)度算法,該算法不僅能確保時間觸發(fā)數(shù)據(jù)的實時性和可靠性,還能夠為事件觸發(fā)數(shù)據(jù)均勻的預留空閑資源.從而為不可預知的事件觸發(fā)數(shù)據(jù)的資源分配做出最快速的響應.

2 相關(guān)研究

工業(yè)無線網(wǎng)絡的實時調(diào)度已被廣泛研究,在文獻[4,5]中該問題是NP難問題的推論被首次證明,同時該研究給出了網(wǎng)絡可調(diào)度的必要條件.此后,為了提高工業(yè)無線網(wǎng)絡的實時性能,研究人員提出了許多針對周期性時間觸發(fā)數(shù)據(jù)的實時調(diào)度算法,例如5G中可變參數(shù)集與資源位置的協(xié)同優(yōu)化[6,7],根據(jù)節(jié)點數(shù)據(jù)流進行分段時隙的分配[8],通過算法分離對工業(yè)無線網(wǎng)絡的實時性和可靠性進行優(yōu)化[9],以及資源空間復用[10]等.這些方法在考慮將時隙資源分配給時間觸發(fā)數(shù)據(jù)的同時,追求的是工業(yè)無線網(wǎng)絡在可靠性和實時性方面的提升.如果考慮事件觸發(fā)的數(shù)據(jù)包的加入,則會對時間觸發(fā)的數(shù)據(jù)包的時隙資源分配結(jié)果產(chǎn)生影響,從而導致資源利用率降低.甚至對系統(tǒng)可靠性產(chǎn)生影響.

為了處理事件觸發(fā)的數(shù)據(jù)包,一些方法允許事件觸發(fā)數(shù)據(jù)包占用時間觸發(fā)數(shù)據(jù)包的資源[11],或者分配兩種數(shù)據(jù)包可共享的時隙資源[12],并在事件觸發(fā)的數(shù)據(jù)包到來的時候,暫停時間觸發(fā)的數(shù)據(jù)包的傳輸[13].但是在這些方法中,事件觸發(fā)的數(shù)據(jù)包的引入可能會引起時間觸發(fā)數(shù)據(jù)包的延遲到達甚至丟失.另外,在文獻[14,15]中的工作通過搶占式方法對事件觸發(fā)數(shù)據(jù)包進行調(diào)度,但該方法同樣可能會影響時間觸發(fā)數(shù)據(jù)包的分配方案,甚至通過搶占造成數(shù)據(jù)包的丟失.本文提出一種為時間觸發(fā)數(shù)據(jù)包均勻分配資源的方法,在不允許事件觸發(fā)的數(shù)據(jù)包搶占時間觸發(fā)的數(shù)據(jù)包的前提下,以及在不暫停時間觸發(fā)的數(shù)據(jù)包傳輸?shù)耐瑫r,在最短時間內(nèi)保證對事件觸發(fā)數(shù)據(jù)包的資源響應.

3 系統(tǒng)模型及問題描述

本文針對時隙分配進行理論及算法上的研究,解決盡可能將時間觸發(fā)數(shù)據(jù)占用資源在時間維度均勻分布的問題.

如圖1所示,在大多數(shù)面向運動控制需求的實時控制系統(tǒng)中[16],均可以有如下控制過程描述,其中,Ci(i∈[1,n],n∈Z+)代表控制器節(jié)點,多個控制器與5G基站相連.Oi(i∈[1,n],n∈Z+)代表被控對象節(jié)點,與5G終端相連.此類系統(tǒng)中,控制拓撲如圖2所示,控制器Ci發(fā)送控制命令ci,依次經(jīng)由5G基站和終端達到執(zhí)行器,此過程稱為下行傳輸.被控過程包括執(zhí)行器、設備以及傳感器[17],Oi執(zhí)行控制命令后,傳感器產(chǎn)生反饋信號fi,經(jīng)由5G終端和基站返回控制器Ci,此過程稱為上行傳輸.其中{fi,ci|i∈[1,n],n∈Z+}的傳輸和被控過程構(gòu)成一條閉環(huán)反饋控制回路,各控制回路在控制層面相互獨立.

圖2 控制系統(tǒng)拓撲圖

每個控制回路中的數(shù)據(jù)傳輸可視為一個任務流.一個任務流每隔一個周期時間發(fā)起一個控制命令數(shù)據(jù)包,該數(shù)據(jù)包必須在該周期內(nèi)完成回路內(nèi)的上下行傳輸,即該回路視為任務流的路徑,周期視為傳輸?shù)南鄬刂蛊?

本文采用N={n1,n2,…}表示任務流集合.任務流ni對應一個二元組屬性.Ti表示任務流的時間觸發(fā)周期,也是每次回路控制的相對截止期,ti表示一個周期內(nèi)被控對象節(jié)點Oi的處理時間.如圖3所示,處理時間即為ti.

圖3 處理時間在周期中的位置

本文中周期采用調(diào)和周期(harmonic period),可以表示為每個周期性任務流的周期Ti=s′×2n,n為非負整數(shù),s′為單位周期中時隙的數(shù)目.由于調(diào)和周期可以通過改變n的數(shù)值刻畫差異性較大的多種周期,因此在工業(yè)網(wǎng)絡中被廣泛使用.由于本文對周期性時間觸發(fā)數(shù)據(jù)進行實時調(diào)度,故將不同任務流周期的最小公倍周期定義為超周期(既最大調(diào)和周期),并針對一個超周期內(nèi)的時隙資源進行調(diào)度.由于每個超周期內(nèi)調(diào)度需求與調(diào)度結(jié)果完全相同.因此本問題只關(guān)注一個超周期內(nèi)被占用資源的分布情況.

在網(wǎng)絡層面,任務流數(shù)據(jù)之間的資源占用沖突,任務流本身的命令先后順序依賴.基于該問題,本文針對單一信道進行時隙資源調(diào)度,即對于單一任務流而言,由于實時控制系統(tǒng)傳輸?shù)目刂泼畲蠖酁椴怀^20字節(jié)的短包,故可認為一個時隙資源就可以滿足一個控制命令所需資源,對于反饋信號也基于此設定.如圖3所示,控制信號ci占用一個時隙資源,反饋信號fi占用一個時隙資源,兩個信號之間要滿足處理時間不小于ti限制.并且假設在時隙0時,所有時間觸發(fā)的數(shù)據(jù)流釋放第一個數(shù)據(jù)包.

當將本文的問題模型考慮為一個可滿足性問題時,并將該問題的ti變?yōu)?,則該問題規(guī)約成與文獻[5]中的問題相同,文獻[5]中的問題是NP-hard問題,因此本文僅約束部分就NP-hard問題,加上該模型的目標后,本文的問題至少是NP-hard問題.

4 調(diào)度方法

各任務流之間存在復雜的依賴和沖突關(guān)系,數(shù)據(jù)包由控制器節(jié)點C{C1,C2…Cn}經(jīng)過5G無線鏈路到達被控對象節(jié)點O{O1,O2…On},在單一信道中,由于存在調(diào)度沖突,使得傳輸無法并行,基于這些限制,本文進行了如下規(guī)劃.

設xi,j表示任務流i是否占用時隙j,xi,j∈{0,1}.

·xi,j=1 表示任務流i占用時隙j;

·xi,j=0 表示不占用.

其中i表示任務流的序號,j是超周期中數(shù)據(jù)時隙的編號,設路徑上的任務流個數(shù)為n,超周期中時隙總數(shù)為m,則有1≤i≤n,1≤j≤m.此時最小任務流周期占用時隙的最大值可以表示為:

(1)

其中p表示任務流周期集合Ti中的最小周期,即p=minTi,Smax表示時隙占用數(shù)目最多的最小周期p內(nèi)所占用的時隙數(shù)目.本文時隙分配的目標就是均衡每個最小周期內(nèi)的資源占用,因此目標為最小化Smax的值,即:

(2)

問題規(guī)劃滿足以下約束:

1)唯一性約束.多個任務流不可占用同一時隙j,因此:

(3)

2)實時性約束.每次回路控制從控制命令生成到收到反饋必須在一個周期內(nèi)完成,即任務流i在每個Ti內(nèi)需占用2個時隙,因此:

(4)

3)處理時間約束.任務流i在該任務流周期Ti內(nèi)所傳輸?shù)膬蓚€數(shù)據(jù)包在時間上滿足時間差不小于處理時間ti,因此:

(5)

根據(jù)公式(1)-公式(5),本文使用ILOG CPLEX對該規(guī)劃進行求解,ILOG CPLEX是IBM推出的一款優(yōu)化模型工具箱,并提供特定的編程語言.對于0-1整數(shù)規(guī)劃問題,在存儲空間和時間允許的情況下,ILOG CPLEX一定能找到最優(yōu)解.對于本文的問題,公式(1)-公式(5)可以表示為0-1整數(shù)規(guī)劃問題,其中xi,j為變量,通過ILOG CPLEX自身語言將公式(1)作為CPLEX的目標函數(shù),公式(2)-公式(5)作為規(guī)劃的約束條件,再利用CPLEX調(diào)用自身優(yōu)化算法進行最優(yōu)解的求取.

5 改進問題模型

對于本文中的問題模型,在時間和存儲允許的情況下,規(guī)劃求解器可以求得該問題的最優(yōu)解,但隨著問題規(guī)模的增大,求解時間也隨之急劇增加,因此本文進一步提出了改進算法,以縮短求解器求解時間.

由于本文中問題目標是使占用的時隙資源盡量均勻的分配在時間維度上.具體來說是使每個最小任務流周期p內(nèi)占用時隙數(shù)目最多的周期占用時隙數(shù)目最少.基于這樣的一個目標,從最優(yōu)解的方向考慮,本文進一步提出了最小任務流周期p內(nèi)占用時隙總數(shù)的限制S.即:

(6)

在式(6)的限制條件下,解空間大小受S約束,通過由小至大調(diào)整S的取值,可指導求解器的尋優(yōu)過程,改進算法如算法1所示.

算法1.相對最優(yōu)限制算法

輸入:S,set_t,s_add=1

輸出:調(diào)度結(jié)果,求解時間

2.whileS

3.Solver(S,set_t)//定義求解函數(shù)Solver()

4. 記錄時間;

5.if!solvethen//無解

6.S←S+s_add;

7.else

8.returnSolver調(diào)度結(jié)果和求解時間;

9.endwhile

10.return調(diào)度失敗;

本文提出的相對最優(yōu)限制算法(算法1)是通過公式(6)對第4節(jié)模型進行簡化,在公式(6)極大縮短求解時間的前提下,能夠快速找到可行解.

6 啟發(fā)式調(diào)度

雖然用CPLEX求解器可求得該問題的最優(yōu)解,但隨著問題規(guī)模的增大,求解時間隨之增大,即使在改進問題模型下,求解時間依然急劇增加.因此本文又提出啟發(fā)式算法用以提高問題規(guī)模的可擴展性.

規(guī)則1.

對最小周期任務流即周期為T0的任務流進行調(diào)度,為使占用資源盡量平均(設該任務流開始周期為第0個周期),當i為偶數(shù)時,將第i個周期內(nèi)的后一個數(shù)據(jù)包放到第i個周期末尾處,即X(i+1)T0-1=1,在該周期內(nèi)時隙間隔為T0/2處(通過改變時隙間隔來確定ti),放置第2個數(shù)據(jù)包,即X(i+1)T0-1-T0/2=1.當i為奇數(shù)時,將第i周期內(nèi)的第1個數(shù)據(jù)包放到第i個周期開始處,在該周期內(nèi)時隙間隔為T0/2處,放置第2個數(shù)據(jù)包.如果最小周期的任務流不唯一,則在偶數(shù)周期內(nèi)按該方式向前移動一個時隙,在奇數(shù)周期內(nèi)向后移動一個時隙,依此規(guī)則,放置周期均為最小周期的任務流.如果時隙占用沖突,則無解.

對于非最小周期任務流中最小周期的任務流,分為以下兩種規(guī)則.

規(guī)則2.

如果該任務流周期為T0的2倍,則將該周期內(nèi)的兩個數(shù)據(jù)包分別放在周期首尾處.若有相同周期的任務流,則分別從首尾處向前移動一個時隙,放置數(shù)據(jù)包,如果占用沖突,則無解.根據(jù)規(guī)則1的推導,該任務流一個周期內(nèi)的兩個數(shù)據(jù)包之間的距離滿足ti限制.

規(guī)則3.

若周期不是T0的2倍,則從前到后查找該任務流每個周期內(nèi)的第1/4周期和第3/4周期中的空時隙,若有空時隙,則在第0-1/4周期的第1個空時隙放置第1個數(shù)據(jù)包,在第2/4-3/4周期的第1個空時隙放置第2個數(shù)據(jù)包.若其中一個1/4周期內(nèi)無可占用時隙,則無解.對于擁有同樣周期的任務流,則在1/4-2/4周期內(nèi)和3/4-1周期內(nèi)分別放置一個數(shù)據(jù)包,而后據(jù)此規(guī)則循環(huán),若其中一個1/4周期內(nèi)無可占用時隙,則無解.

規(guī)則4.

對于剩余任務流,執(zhí)行規(guī)則3.

算法2.啟發(fā)式算法

輸入:時隙總數(shù)m,任務流總數(shù)n

輸出:調(diào)度序列X

1. 隨機生成n個任務流數(shù)組T

2.T←sort(T)//定義排序函數(shù)sort()

3. 計算相同周期的個數(shù),并存入數(shù)組K

4.Xi={0}

5. 數(shù)組arrd記錄空時隙位置

6.fork∈[0,K0)do

7.fori∈[0,m/T0)do

8. 執(zhí)行規(guī)則1

9. 更新X,addr

10.endfor

11.endfor

12.if(K1==0)return求解結(jié)果

13.endif

14.elseif(K1!=0&&TK0==2*T0)then

15.fork∈[0,K1),i∈[0,m/TK0)do

16. 執(zhí)行規(guī)則2

17. 更新X,addr

18.endfor

19.endelseif

20.else

21.fori∈[1,n)do

22. 執(zhí)行規(guī)則3,4

23. 更新X,addr

24.endfor

25.endelse

26.return求解結(jié)果

算法2在初始化隨機任務流數(shù)組T后,對T進行排序(第2行),并計算相同周期的個數(shù),存入K(第3行),同時初始化調(diào)度序列X={0}(第4行),記錄空時隙位置(第5行),然后根據(jù)規(guī)則1對最小周期任務流進行分配(第6-13行),根據(jù)規(guī)則2對非最小周期進行分配(第14-18行),最后根據(jù)規(guī)則3、規(guī)則4對剩余任務流進行分配(第19-25行).

7 實 驗

本實驗通過對比CPLEX方法(公式(1)-公式(5))、改進模型算法(算法1)、均分算法和啟發(fā)式算法(算法2)的執(zhí)行效果與執(zhí)行時間,說明各算法特性.其中均分算法是指上行資源與下行資源只允許分別使用整個任務周期的一半.該方法通過一種直觀的方式限制了變量的取值范圍,達到了縮短求解器求解時間的目的.

圖4描述了CPLEX方法,改進模型算法,均分方法對2000個任務流調(diào)度執(zhí)行時間的分布.該組對比中a=0.2,n=4,在這種情況下,極少數(shù)任務流的求解時間大于10秒,說明在10秒的時間范圍內(nèi),得到了絕大多數(shù)的最優(yōu)解.同時,在執(zhí)行時間長短分布狀態(tài)上,均分方法優(yōu)于改進模型算法,改進模型算法優(yōu)于CPLEX方法.

圖4 不同方法執(zhí)行時間分布

圖5(a)表示不同方法執(zhí)行時間的對比.在任務流數(shù)目為4-7的情況下,改進模型算法的執(zhí)行時間逐漸接近CPLEX求解器的執(zhí)行時間,說明隨著任務流數(shù)目的增多,改進模型算法的在執(zhí)行時間上的優(yōu)勢逐漸減小.而均分方法在執(zhí)行時間上優(yōu)勢明顯,原因是限制變量的取值范圍來換取執(zhí)行時間的減少.隨著節(jié)點數(shù)目的增加,在n=8時,CPLEX方法與改進模型算法在不限制執(zhí)行時間的情況下,兩小時未得到最優(yōu)解.

圖5(b)對比了改進模型算法,均分方法和啟發(fā)式方法的調(diào)度成功率,在n=12時,啟發(fā)式算法的調(diào)度成功率開始下降,隨著n的增大,3種方法的調(diào)度成功率均有所下降,原因是調(diào)度復雜度增加,時隙占用沖突增加.而在調(diào)度成功率方面,改進模型算法由于限制較少,可調(diào)度行更加靈活,成功率更高.啟發(fā)式算法相比于均分方法,靈活性較低,調(diào)度成功率相對較低.

圖5 執(zhí)行時間與調(diào)度成功率對比

圖6對比了改進模型算法(算法1),均分方法和啟發(fā)式算法所調(diào)度結(jié)果的優(yōu)劣程度,在不同任務流數(shù)目的情況下,改進問題模型算法和均分方法所調(diào)度的結(jié)果的方差波動范圍小,說明這兩種方法的調(diào)度結(jié)果接近理論值.原因是這兩種方法均能在時間和存儲空間允許的范圍內(nèi)找到非劣解.但相比來說,改進模型算法優(yōu)于均分方法,原因是改進模型算法對變量的限制條件相對少,可求解范圍大,非劣解可選擇數(shù)目多.

圖6 結(jié)果方差對比

啟發(fā)式算法在n=4時,調(diào)度結(jié)果較好,但隨著n的增加,啟發(fā)式算法的調(diào)度結(jié)果與理論值之間的方差增大,原因是啟發(fā)式算法在均勻分配調(diào)度空間的時候,并未考慮時隙占用數(shù)目最少的周期p這一因素.但該方差反映在時隙數(shù)目和理論值的差距上時,結(jié)果可以接受.

8 結(jié) 論

為使事件觸發(fā)數(shù)據(jù)能夠盡快得到5G網(wǎng)絡的響應,本文將時間觸發(fā)數(shù)據(jù)占用的資源均勻的分布在時間維度上,提出了時隙資源均勻占用的調(diào)度模型,并將該模型描述為求解器可解的0-1整數(shù)線性規(guī)劃問題.之后,為縮短求解器的執(zhí)行時間,對該模型進行改進,通過變量控制解空間大小,實現(xiàn)了在較小解空間內(nèi)的快速求解.但隨著問題規(guī)模的增大,本文又提出一種啟發(fā)式算法來增加問題可擴展性.最后通過實驗可以得出,改進模型算法,均分方法,啟發(fā)式算法各有優(yōu)劣,可根據(jù)不同需求選擇相應的調(diào)度方法.