邊緣計算系統中延時敏感型任務調度策略

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

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

0 引 言

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

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

本文將研究邊緣計算環境下任務調度的代價優化問題，目標是最小化邊緣計算系統代價，并滿足任務QoS需求。提出一種針對延時敏感任務的調度模型，設計兩階段任務調度代價優化算法TTSCO，并通過仿真實驗驗證了算法的效率。

1 相關研究

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

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

2 系統模型

2.1 邊緣計算體系

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

圖1 邊緣計算模型

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

I=tmd

(1)

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

2.2 問題描述

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

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

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

以變量xij表示ti是否調度至ej上執行，并以二進制形式定義為

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

(2)

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

(3)

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

(4)

(2)性能

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

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

(5)

對于調度至服務器ej上的任務ti，以上的3個時間分別計算為

lij,com=wi/Rj

(6)

lij,in=di,in/bij,down

(7)

lij,out=di,out/bij,up

(8)

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

bij,*=bij,up=bij,down

(9)

因此，式(5)可變為

(10)

其中

di=di,in+di,out

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

(11)

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

(12)

對于每臺服務器ej，調度至ej上任務的需求帶寬之和不能超過ej的總帶寬，即

(13)

(3)代價

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

令yj為標識服務器ej狀態的二進制變量，表示為

(4)最優化問題

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

(14)

約束條件為

(15)

(16)

(17)

(18)

以下驗證以上的代價優化問題為NP難問題。

定理邊緣計算系統的代價優化問題為NP難問題。

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

3 TTSCO算法設計

3.1 階段一

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

uj=Cj/zj

(19)

其中，zj為服務器ej的大小，且

(20)

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

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

(21)

其中

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

(22)

其中，ptij為調度至服務器ej上任務的資源需求。

3.2 階段二

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

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

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

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

第二階段中，首先獲取最后所選服務器eg1和集合U中擁有最小代價的服務器eg2。在步驟(19)～步驟(27)中，若eg1的可用資源可滿足eg2上任務ti的資源需求，則將ti重新調度至eg1，再更新決策變量。當eg2上的任務均被移除時，可從U中移除服務器eg2，再更新eg2的狀態。然后，即可從U中得到代價最小的新服務器，即步驟(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時間復雜度分析。TTSCO算法劃分為兩個階段：先對邊緣服務器進行排列，然后將任務調度至邊緣服務器。首階段對服務器按服務性能進行排列的時間復雜度為O(mlogm)。 次階段中，需要調度的任務數為n個，在最差的情況下，所選服務器可以滿足所有未調度任務的資源需求，則算法將進行n次的標量積計算，并選擇最大largest的任務。那么，該階段的時間代價至少為O(n2)。綜上，最差情況下TTSCO算法的時間復雜度為O(mlogm+n2)。

4 實驗分析

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

4.1 對比研究

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

圖2 TTSCO算法與理論最優解的分布

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

圖3 近似率的CDF

4.2 參數影響分析

本節將分析相關參數配置對于TTSCO算法的影響，包括輸入任務數量、傳輸數據量以及任務的延時需求。

(1)任務量的影響

本部分評估不同輸入數據量對TTSCO算法的影響，輸入任務的傳輸數據量設置為50 MB，輸入任務量從30增加到150，步長為30。結果如圖4所示。可以看到，若輸入任務量在增加，會導致系統代價增加，這是因為需要開啟更多的服務器執行卸載任務，進而導致更大的代價。而TTSCO算法相比RANDOM算法平均可以降低約50%的代價，這是由于TTSCO算法可以大幅提升每臺邊緣服務器的資源利用率，即處于ON狀態的服務器數量會大幅減少。

圖4 輸入任務量的影響

(2)傳輸數據量的影響

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

圖5 任務傳輸數據量的影響

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

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

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

圖6 任務延時需求的影響

5 結束語

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