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

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

1 引 言

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

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

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

2 相關(guān)研究

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

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

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

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

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

圖2 控制系統(tǒng)拓?fù)鋱D

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

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

圖3 處理時(shí)間在周期中的位置

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

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

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

4 調(diào)度方法

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

設(shè)xi,j表示任務(wù)流i是否占用時(shí)隙j,xi,j∈{0,1}.

·xi,j=1 表示任務(wù)流i占用時(shí)隙j;

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

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

(1)

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

(2)

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

1)唯一性約束.多個(gè)任務(wù)流不可占用同一時(shí)隙j,因此:

(3)

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

(4)

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

(5)

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

5 改進(jìn)問(wèn)題模型

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

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

(6)

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

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

輸入:S,set_t,s_add=1

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

2.whileS

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

4. 記錄時(shí)間;

5.if!solvethen//無(wú)解

6.S←S+s_add;

7.else

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

9.endwhile

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

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

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

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

規(guī)則1.

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

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

規(guī)則2.

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

規(guī)則3.

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

規(guī)則4.

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

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

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

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

1. 隨機(jī)生成n個(gè)任務(wù)流數(shù)組T

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

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

4.Xi={0}

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

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

7 實(shí) 驗(yàn)

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

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

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

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

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

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

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

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

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

8 結(jié) 論

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