邊緣計算系統(tǒng)中延時敏感型任務(wù)調(diào)度策略

王 星，于 炯，杜旭升，張姍姍，楊少智

(新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046)

0 引 言

隨著物聯(lián)網(wǎng)技術(shù)的發(fā)展，延時敏感型應(yīng)用(如健康監(jiān)測、增強現(xiàn)實游戲等)量日益增長[1]。由于IoT設(shè)備資源有限，可以將運算量較大且復(fù)雜的任務(wù)卸載至遠程服務(wù)器執(zhí)行。云計算是處理卸載任務(wù)的潛在方式。然而，由于距離云端較遠，IoT設(shè)備發(fā)送大量任務(wù)至遠程云端會導(dǎo)致較長響應(yīng)時間和嚴重的網(wǎng)絡(luò)擁塞。為此，邊緣計算作為新計算模式應(yīng)運而生[2,3]。邊緣計算在計算基礎(chǔ)設(shè)施上提供了一個附加層，由網(wǎng)絡(luò)邊緣的若干服務(wù)器構(gòu)成。對于來自IoT設(shè)備的卸載任務(wù)，邊緣計算可提供計算服務(wù)并返回結(jié)果。利用這種方式，卸載任務(wù)的傳輸延時和核心網(wǎng)絡(luò)上的負載可以得到有效降低，使得邊緣計算成為應(yīng)用的熱點。

邊緣計算中，任務(wù)調(diào)度是核心問題[4]。為了降低任務(wù)計算能耗，IoT設(shè)備可卸載任務(wù)至邊緣服務(wù)器。然而，任務(wù)卸載會導(dǎo)致額外的傳輸能耗，并延長卸載任務(wù)的完成時間。此時，必須研究IoT設(shè)備如何做出卸載決策。此外，當計算任務(wù)調(diào)度至不同邊緣服務(wù)器時，傳輸和計算代價均有所不同。因此，如何設(shè)計有效的調(diào)度策略降低任務(wù)傳輸和計算所導(dǎo)致的系統(tǒng)代價也是調(diào)度問題必須解決的難題。然而，有關(guān)邊緣服務(wù)器調(diào)度策略的相關(guān)研究中，考慮服務(wù)器代價優(yōu)化的策略目前相對較少，尤其是在非高峰時期的邊緣服務(wù)器代價優(yōu)化問題少有研究。

本文將研究邊緣計算環(huán)境下任務(wù)調(diào)度的代價優(yōu)化問題，目標是最小化邊緣計算系統(tǒng)代價，并滿足任務(wù)QoS需求。提出一種針對延時敏感任務(wù)的調(diào)度模型，設(shè)計兩階段任務(wù)調(diào)度代價優(yōu)化算法TTSCO，并通過仿真實驗驗證了算法的效率。

1 相關(guān)研究

邊緣計算環(huán)境中任務(wù)調(diào)度問題已有一些研究成果。文獻[5]研究了移動計算系統(tǒng)中雙國代價/延時均衡的任務(wù)調(diào)度問題，所設(shè)計的調(diào)度算法可以最小化競爭與協(xié)作場景下的系統(tǒng)代價。文獻[6]在移動邊緣計算MEC系統(tǒng)中提出了一種動態(tài)計算卸載策略以最小化執(zhí)行代價。文獻[7]提出了一種漸近式最優(yōu)卸載方法以最大化網(wǎng)絡(luò)利用率，并確保無線應(yīng)用的服務(wù)質(zhì)量。文獻[8]針對多用戶的MEC系統(tǒng)提出了一種在線聯(lián)合計算資源管理算法，可以有效降低任務(wù)調(diào)度中的長期能量消耗。以上工作僅考慮的是用戶與邊緣云間的負載分布，而邊緣云中的任務(wù)調(diào)度問題并沒有有效解決。

文獻[9]研究了大規(guī)模無線城域網(wǎng)絡(luò)WMAN中的多重朵云部署問題，可以有效降低移動端與朵云間的平均訪問延時。文獻[10]在霧計算系統(tǒng)中設(shè)計了一種以最小化任務(wù)完成時間為目標的任務(wù)調(diào)度與資源管理策略。文獻[11]提出了一種兩階段線性規(guī)劃算法處理霧計算中的代價優(yōu)化問題。為了處理移動用戶的峰值負載和云端資源的高效利用問題，文獻[12]在邊緣云中提出了一種樹型結(jié)構(gòu)分布的服務(wù)器模型，并通過一種啟發(fā)式算法對任務(wù)負載進行了有效調(diào)度。文獻[13]將代價優(yōu)化問題形式化為馬爾可夫決策問題MDP，并設(shè)計了一種最小化運行代價的方法。為了滿足任務(wù)的服務(wù)質(zhì)量需求，文獻[14]在邊緣云中提出了一種周期性任務(wù)調(diào)度方法，可以使在邊緣云中的處理的任務(wù)量達到最大。以上工作中，雖然對邊緣云中的任務(wù)調(diào)度與資源管理問題有所研究，但并沒有以降低邊緣服務(wù)器的利用代價為目標考慮任務(wù)調(diào)度。

2 系統(tǒng)模型

2.1 邊緣計算體系

邊緣計算系統(tǒng)由一個邊緣計算代理ECA和若干異構(gòu)邊緣服務(wù)器構(gòu)成，如圖1所示。ECA擁有全部可用資源信息，并實現(xiàn)與每個部署服務(wù)器的通訊。每臺服務(wù)器可運行若干虛擬機，可負責用戶卸載任務(wù)的執(zhí)行。通過將計算任務(wù)卸載至邊緣計算系統(tǒng)，可以使用戶獲得更好的體檢質(zhì)量(低延時、強大計算能力)。

圖1 邊緣計算模型

對于來自用戶的卸載計算任務(wù)，ECA將根據(jù)資源需求選擇合適的服務(wù)器進行處理，即：ECA將周期性地執(zhí)行任務(wù)調(diào)度策略。令I(lǐng)為兩個連續(xù)任務(wù)調(diào)度過程的間隔時間，由于每組任務(wù)的完成時間不同，因此需要動態(tài)的調(diào)整I的取值，將其定義為

I=tmd

(1)

其中，tmd為所有任務(wù)的期望完成時間的最大值。

2.2 問題描述

(1)任務(wù)模型和服務(wù)器模型

令T={t1,t2,…,tn} 為邊緣計算系統(tǒng)中一組延時敏感型任務(wù)，n為任務(wù)數(shù)。將ti∈T定義為ti={di,wi,δi,si}，di為任務(wù)ti的數(shù)據(jù)傳輸量，wi為ti的任務(wù)執(zhí)行負載，δi為完成任務(wù)ti的截止時間，si為任務(wù)ti對系統(tǒng)的存儲需求。

令集合E={e1,e2,…,em} 為構(gòu)成邊緣計算系統(tǒng)的m臺異構(gòu)邊緣服務(wù)器。每臺服務(wù)器ej∈E定義為ej={Bj,Vj,Rj,Sj}， 其中，Bj為服務(wù)器ej與ECA間的通信帶寬，邊緣服務(wù)器的作用在于可以部署若干臺虛擬機VM，每臺虛擬機VM可用于執(zhí)行單一的計算任務(wù)。令Vj為部署在ej上的虛擬機數(shù)量，Sj為ej上的可用存儲資源量。ej上每臺虛擬機的計算速率是相同的，表示為Rj。當發(fā)生任務(wù)調(diào)度時，每臺虛擬機占據(jù)的帶寬可以動態(tài)調(diào)整。令bi,j為ti調(diào)度至ej上執(zhí)行時的帶寬需求，Cj為ej的接通代價。

以變量xij表示ti是否調(diào)度至ej上執(zhí)行，并以二進制形式定義為

同時，約定一個服務(wù)器僅能處理一個任務(wù)，即

(2)

邊緣服務(wù)器的資源受限，必須滿足以下任務(wù)調(diào)度約束條件，即服務(wù)器必須具有足夠的存儲空間，否則會產(chǎn)生數(shù)據(jù)流失。因此，調(diào)度任務(wù)的總體存儲需求不能超過ej的存儲資源，即

(3)

此外，由于每臺服務(wù)器上部署的虛擬機數(shù)量有限，調(diào)度任務(wù)的總數(shù)也不能超過ej的虛擬機總數(shù)，即

(4)

(2)性能

卸載任務(wù)的完成時間由3個部分組成：任務(wù)的計算時間lij,com、 從ECA至ej的ti輸入數(shù)據(jù)的傳輸時間lij,in以及服務(wù)器至ECA的輸出數(shù)據(jù)傳輸時間lij,out， 因此約束為

xij(lij,com+lij,in+lij,out)≤δi

(5)

對于調(diào)度至服務(wù)器ej上的任務(wù)ti，以上的3個時間分別計算為

lij,com=wi/Rj

(6)

lij,in=di,in/bij,down

(7)

lij,out=di,out/bij,up

(8)

其中，di,in為ti的輸入數(shù)據(jù)量，di,out為ti的輸出數(shù)據(jù)量，bij,up和bij,down分別為ECA與邊緣服務(wù)器間的上行和下行帶寬。假設(shè)上行帶寬與下行帶寬相等，即

bij,*=bij,up=bij,down

(9)

因此，式(5)可變?yōu)?/p>

(10)

其中

di=di,in+di,out

若ti調(diào)度至ej，通過解式(10)可得到需求帶寬。帶寬需求不等式如下

(11)

在所有任務(wù)可在各自截止時間δi內(nèi)完成的前提條件下，需要盡可能降低邊緣計算系統(tǒng)代價。那么，ECA與ej間ti的需求帶寬可表示為

(12)

對于每臺服務(wù)器ej，調(diào)度至ej上任務(wù)的需求帶寬之和不能超過ej的總帶寬，即

(13)

(3)代價

邊緣計算系統(tǒng)中，由于ECA負責與每臺邊緣服務(wù)器通信，并管理服務(wù)器，每臺服務(wù)器通過ECA可以轉(zhuǎn)換為在線ON和離線OFF狀態(tài)。若服務(wù)器為ON狀態(tài)，維持服務(wù)器運行則會生成相應(yīng)代價，如運行服務(wù)器的能量消耗。令服務(wù)器ej在ON狀態(tài)時的系統(tǒng)代價為Cj，則總體代價為所有處理ON狀態(tài)的服務(wù)器代價之和。

令yj為標識服務(wù)器ej狀態(tài)的二進制變量，表示為

(4)最優(yōu)化問題

邊緣計算系統(tǒng)中，邊緣計算代理的目標是將卸載任務(wù)調(diào)度至邊緣服務(wù)器上執(zhí)行。若服務(wù)器已有分派任務(wù)，定義狀態(tài)為ON；若沒有分派任務(wù)，定義狀態(tài)為OFF。調(diào)度算法的目標是使系統(tǒng)代價達到最小，形式化模型為

(14)

約束條件為

(15)

(16)

(17)

(18)

以下驗證以上的代價優(yōu)化問題為NP難問題。

定理邊緣計算系統(tǒng)的代價優(yōu)化問題為NP難問題。

證明：將邊緣服務(wù)器ej上的資源表示為pej=(Sj,Vj,Bj)。 當ti在服務(wù)器ej上執(zhí)行時，ti的資源需求可表示為ptij=(si,I,bij)。 考慮一種特殊情形，即所有服務(wù)器為同質(zhì)的。則ti的資源需求可重寫為pti=(si,I,bi)， 而服務(wù)器ej的資源可重寫為pe=(S,V,B)。 代價優(yōu)化問題的目標是最小化邊緣計算系統(tǒng)代價并確保所有任務(wù)的QoS需求。將每個任務(wù)視為一個物品，而每臺服務(wù)器為一個箱子。那么，目標即為利用最小數(shù)量的箱子裝入所有物品。顯然，該問題等同于三維矢量的裝箱問題，為NP難問題。證畢。

3 TTSCO算法設(shè)計

3.1 階段一

TTSCO算法首先選擇擁有最小單位代價uj的服務(wù)器執(zhí)行卸載任務(wù)，單位代價表示為式(19)。不失一般性，不同邊緣服務(wù)器的單位代價不同

uj=Cj/zj

(19)

其中，zj為服務(wù)器ej的大小，且

(20)

定義qej為任務(wù)調(diào)度至服務(wù)器后ej的剩余可用資源。根據(jù)裝箱問題中的最佳適應(yīng)算法BF，對于在服務(wù)器ej上處理的卸載任務(wù)，ECA將選擇該服務(wù)器上的最大largest任務(wù)進行處理。在TTSCO算法中，定義largest任務(wù)為具有最大標量積hi的任務(wù)，而標量積hi定義為

hi=qejptij=siS′j+V′j+bijB′j

(21)

其中

qej=(S′j,V′j,B′j)=pej-∑pe*j

(22)

其中，ptij為調(diào)度至服務(wù)器ej上任務(wù)的資源需求。

3.2 階段二

階段一之后，可以得到初步的任務(wù)調(diào)度策略。但在部分情形下，初步的調(diào)度策略得到的邊緣計算系統(tǒng)代價還可以進一步降低。例如：現(xiàn)有兩個用戶任務(wù)，表示為A1、A2，兩臺邊緣服務(wù)器，表示為B1、B2。A1的資源需求為(10,10,10)，A2的資源需求為(20,20,20)。B1和B2的可用資源矢量分別為(15,15,15)和(50,50,50)。根據(jù)第一階段的調(diào)度策略，任務(wù)A1將被調(diào)度至B1，而A2被調(diào)度至B2。此時，總體代價為兩臺服務(wù)器的代價之和。然而，如果所有任務(wù)均調(diào)度至B2處理，總代價僅為服務(wù)器B2的代價。通過該策略，總代價可以進一步降低。

根據(jù)以上案例，對于最終選擇的服務(wù)器，僅擁有較少資源量的服務(wù)器被利用。因此，第一階段調(diào)度后，需要進一步優(yōu)化調(diào)度策略而降低不必要的代價。一般情形下，最后選擇的服務(wù)器擁有更多的可用資源量。在TTSCO算法中，將設(shè)計一種在最后選擇的服務(wù)器上最大化資源利用率的優(yōu)化策略，目標是重新將最小代價服務(wù)器上的任務(wù)調(diào)度至第一階段中最后選擇的服務(wù)器上執(zhí)行。通過這種方式，TTSCO算法能夠以最大的代價提高服務(wù)器資源利用率，并以更小的代價降低服務(wù)器上的非必要代價。

綜合以上，TTSCO算法的執(zhí)行過程如算法1所示。算法輸入為待調(diào)度至邊緣服務(wù)器上的任務(wù)集合以及可用邊緣服務(wù)器集合。步驟(1)對二進制決策變量xij和yj進行初始化操作。

接下來，在第一階段中，需要以單位代價uj的非遞減方式對邊緣服務(wù)器進行排列。若單位代價相同，則以Cj的非遞減方式進行排列，即式(19)和式(20)。步驟(5)～步驟(15)的主要目標是算法將根據(jù)任務(wù)對資源的需求以及當前服務(wù)器的可用資源情況選擇相應(yīng)可執(zhí)行待調(diào)度任務(wù)的資源提供方。步驟(6)從集合E中選擇單位使用代價最小的服務(wù)器ej。步驟(7)～步驟(14)的目標是先判斷是否所選服務(wù)器資源可以滿足集合T中的任務(wù)資源需求，若滿足，則選擇計算量最大的任務(wù)提交至服務(wù)器ej執(zhí)行；否則，將ej從服務(wù)器集合E中移除，即步驟(15)。步驟(8)中根據(jù)式(21)和式(22)獲得最大任務(wù)。然后，任務(wù)ti從待調(diào)度任務(wù)集合T中移除，并將tij和yj設(shè)置為1，即步驟(10)～步驟(12)。步驟(13)則將ej添加至已利用服務(wù)器集合U中。

第二階段中，首先獲取最后所選服務(wù)器eg1和集合U中擁有最小代價的服務(wù)器eg2。在步驟(19)～步驟(27)中，若eg1的可用資源可滿足eg2上任務(wù)ti的資源需求，則將ti重新調(diào)度至eg1，再更新決策變量。當eg2上的任務(wù)均被移除時，可從U中移除服務(wù)器eg2，再更新eg2的狀態(tài)。然后，即可從U中得到代價最小的新服務(wù)器，即步驟(22)～步驟(25)所示。

算法1： TTSCO算法

Input: set of tasks to be scheduledT, set of available edge serversE

Output: task scheduling variable {xij}, the state of severs {yj}

(1)initialize all variablexijto be 0,setyj=0 for all servers

(2)stage1:

(3)obtain the vector pej and compute the unit costujof each serverej∈E

(4)set of severs that are usedU={}

(5)whileT≠NULLdo

(6) choose the serverejwith the smallest value of unit costujinE

(7)whilethere are tasks can be assigned into serverejdo

(8) compute the dot producthof all tasks can be assigned int serverej

(9) accommodate thattiwith the biggest value of dot product into serverej

(10)T←T(〗ti}

(11) setxij=1

(12) setyj=1

(13)U=U∪{ej}

(14)endwhile

(15)E←E(〗ej}

(16)endwhile

(17)stage2:

(18)obtain the last selected servereg1and servereg2with smallest cost inU

(19)whiletasktiineg2can be put into the servereg1do

(20) put tasktiinto servereg2

(21) setxig1=1

(22)ifthere is no task ineg2then

(23)U←U(〗eg2}

(24) setyg2=0

(25) obtain the new servereg2with smallest cost inU

(26)endif

(27)endwhile

TTSCO時間復(fù)雜度分析。TTSCO算法劃分為兩個階段：先對邊緣服務(wù)器進行排列，然后將任務(wù)調(diào)度至邊緣服務(wù)器。首階段對服務(wù)器按服務(wù)性能進行排列的時間復(fù)雜度為O(mlogm)。 次階段中，需要調(diào)度的任務(wù)數(shù)為n個，在最差的情況下，所選服務(wù)器可以滿足所有未調(diào)度任務(wù)的資源需求，則算法將進行n次的標量積計算，并選擇最大largest的任務(wù)。那么，該階段的時間代價至少為O(n2)。綜上，最差情況下TTSCO算法的時間復(fù)雜度為O(mlogm+n2)。

4 實驗分析

本節(jié)在Matlab中構(gòu)建仿真實驗驗證TTSCO算法的性能。構(gòu)建兩種類型服務(wù)器組成的邊緣計算系統(tǒng)，并假設(shè)該系統(tǒng)擁有足夠的服務(wù)資源處理所有的任務(wù)需求。對于每個任務(wù)請求，其延時需求為di/α，α為[9,11]間的隨機分布量。為了實驗結(jié)果的有效性，將不同的服務(wù)器配置不同的能力，包括：服務(wù)器配置虛擬機數(shù)、服務(wù)器的存儲能力和計算效率、虛擬機間的通信帶寬等。每臺服務(wù)器的利用代價與其服務(wù)能力成正比。對比算法選擇隨機調(diào)度策略RANDOM進行對比。

4.1 對比研究

如圖2是TTSCO算法與LINGO軟件生成的理論最優(yōu)解的代價分布情況，可以看到，TTSCO生成的解與最優(yōu)解較為接近。

圖2 TTSCO算法與理論最優(yōu)解的分布

進一步，若定義c1為TTSCO算法獲得的解，c2為LINGO軟件得到的理論最優(yōu)解。令近似比c1/c2表示一種性能度量因子，如圖3是近似比的累積分布函數(shù)CDF?？梢钥吹剑票然咎幱?～1.3之間，且95%的近似比取值小于1.2，驗證TTSCO算法的求解準確率還是較高的。同時，隨著輸入任務(wù)的增加，LINGO軟件將花費更多時間(接近于一小時)求解理論最優(yōu)解。而TTSCO算法在Matlab上運行時間僅多花費幾秒即可得到近似最優(yōu)解。此外，由于本文討論的邊緣計算系統(tǒng)代價的最優(yōu)化問題是NP難問題，即在多項式時間內(nèi)無法獲得最優(yōu)解，但TTSCO算法在多項式時間內(nèi)獲得的近似最優(yōu)解依然是有效準確的。

圖3 近似率的CDF

4.2 參數(shù)影響分析

本節(jié)將分析相關(guān)參數(shù)配置對于TTSCO算法的影響，包括輸入任務(wù)數(shù)量、傳輸數(shù)據(jù)量以及任務(wù)的延時需求。

(1)任務(wù)量的影響

本部分評估不同輸入數(shù)據(jù)量對TTSCO算法的影響，輸入任務(wù)的傳輸數(shù)據(jù)量設(shè)置為50 MB，輸入任務(wù)量從30增加到150，步長為30。結(jié)果如圖4所示?？梢钥吹剑糨斎肴蝿?wù)量在增加，會導(dǎo)致系統(tǒng)代價增加，這是因為需要開啟更多的服務(wù)器執(zhí)行卸載任務(wù)，進而導(dǎo)致更大的代價。而TTSCO算法相比RANDOM算法平均可以降低約50%的代價，這是由于TTSCO算法可以大幅提升每臺邊緣服務(wù)器的資源利用率，即處于ON狀態(tài)的服務(wù)器數(shù)量會大幅減少。

圖4 輸入任務(wù)量的影響

(2)傳輸數(shù)據(jù)量的影響

設(shè)置任務(wù)量為150，輸入任務(wù)的數(shù)據(jù)傳輸量從25 MB增加至50 MB，步長為5 MB。結(jié)果如圖5所示?？傮w來看，TTSCO算法得到的系統(tǒng)代價會隨著傳輸數(shù)據(jù)量的增加而增加。然而，當傳輸數(shù)據(jù)量較小時(低于30 MB)，代價并不會隨著傳輸數(shù)據(jù)量的增加而增加，趨勢較為平緩，這是由于任務(wù)調(diào)度會受到虛擬機利用數(shù)量的限制，而服務(wù)器的帶寬和存儲資源利用也相對較低。當增加任務(wù)傳輸數(shù)據(jù)量時，資源利用率雖有所增加，但總體代價并未變化，所以表現(xiàn)出在前期25 MB～35 MB的任務(wù)數(shù)據(jù)傳輸量時算法曲線基本是平緩直線形式。但進一步增加數(shù)據(jù)傳輸量后，當前服務(wù)器已無法滿足更大量的任務(wù)處理需求，更多的服務(wù)器將被開啟使用。此時，系統(tǒng)代價也將隨著傳輸數(shù)據(jù)量的增加而增加。

圖5 任務(wù)傳輸數(shù)據(jù)量的影響

同時，根據(jù)圖5，RANDOM算法得到的代價曲線比較平滑，說明代價值基本不隨輸入任務(wù)的數(shù)據(jù)傳輸量發(fā)生變化，這是由于RANDOM算法是以隨機方式選擇服務(wù)器執(zhí)行任務(wù)的，這樣會開啟過多處于運行狀態(tài)的服務(wù)器從而導(dǎo)致服務(wù)資源利用率較低。增加任務(wù)的傳輸數(shù)據(jù)量，資源利用率雖然會有所增加，但總代價不會出現(xiàn)大幅波動。圖5的結(jié)果也表明TTSCO算法比較RANDOM算法可以平均降低約50%的代價。

(3)任務(wù)延時需求的影響

本部分定義任務(wù)集包括7個任務(wù)，任務(wù)的數(shù)據(jù)傳輸量以5 MB步長從20 MB增加至50 MB，輸入任務(wù)量為15個任務(wù)集。每個任務(wù)的延時需求設(shè)置為δ/ρ，其中，δ為初始延時，ρ為下降率。以步長0.2從1至2改變ρ。圖6是實驗結(jié)果?？梢钥吹剑S著下降率ρ的增加，TTSCO算法的代價也將增加，而RANDOM算法的代價并沒有發(fā)生多大變化。這是由于較小的延時會要求更大的傳輸帶寬，在這種情況下需要開啟更多的邊緣服務(wù)器來滿足任務(wù)處理的需求。而本文的TTSCO算法平均比RANDOM算法可以降低約45%的代價。

圖6 任務(wù)延時需求的影響

5 結(jié)束語

研究了邊緣計算環(huán)境中任務(wù)調(diào)度的代價優(yōu)化問題，提出了一種兩階段調(diào)度算法。算法可以在滿足所有輸入任務(wù)的QoS需求的同時，使邊緣計算系統(tǒng)的任務(wù)調(diào)度代價達到最小。將算法的調(diào)度結(jié)果與LINGO軟件下得到的理論最優(yōu)解結(jié)果進行了比較，驗證算法可以以多項式時間得到較為接近于最優(yōu)解的調(diào)度方案，而相比對比算法可以有效降低邊緣計算系統(tǒng)的代價。進一步的研究方向可以考慮研究在多重邊緣服務(wù)器環(huán)境下的動態(tài)資源管理和任務(wù)調(diào)度決策問題。