移動邊緣計算中的資源分配與任務調度方法

李 津，章雨鵬，龐 玲，丁為然，孫 罡，虞紅芳

（1.信息系統安全技術重點實驗室，北京 100101；2.電子科技大學信息與通信工程學院，成都 611731）

移動邊緣計算（mobile edge computing，MEC）是一種新興的生態系統［1-2］，旨在融合電信和IT服務，在無線接入網的邊緣提供云計算平臺。MEC在邊緣提供存儲和計算資源，減少移動終端用戶的延遲，可更有效地利用移動網絡backhual和核心網絡。移動邊緣計算場景［3］如圖1所示。MEC在移動網絡的邊緣提供云計算和存儲資源，具有諸如超低延遲、密集計算能力以及減少網絡擁塞等顯著優勢，這對于諸如物聯網［4-5］、視頻流分析，增強現實和聯網汽車等新興應用是必需的。

隨著技術的發展，終端的應用越來越智能化、多樣化，例如人工智能、增強現實（augmented reality，AR）、虛擬現實（virtual reality，VR）、自動駕駛等應用逐漸成為現實。許多應用的實現需要較高的計算性能作為支撐，比如VR/AR、認知輔助等［6-7］。如果用戶設備不能提供足夠的計算能力（例如由于過時的處理器，有限容量的電池等），則應用程序無法運行。在便攜性方面，人們通常希望在可穿戴設備上實現這些應用，這意味著設備必須偏向小型化的方向發展。現階段看來，高性能與便攜性幾乎是矛盾的，因為更小的設備尺寸決定了設備只能配備更小的處理芯片、更小的電池。計算卸載［8］模式的出現就是為了解決這個矛盾。計算卸載是指資源受限的設備將資源密集型計算任務轉移到外部平臺。

對于邊緣網絡資源受限、彈性不足等問題，需要引入資源管理和任務調度機制來對邊緣網絡進行統籌管理。設計合理的資源分配和調度方案，充分利用邊緣資源降低用戶時延，提高用戶體驗。方案設計時需要考慮多方面因素，比如用戶量、計算資源的分布、計算資源的多少等，將邊緣的資源最大化利用。現有關于移動邊緣計算的相關工作中，相當大一部分集中在對計算卸載過程中的決策問題進行研究，包括計算卸載過程中的無線發射功率控制，設備、邊緣服務器、云端服務器之間計算任務分配比例決策，邊緣服務器以及設備上的計算資源分配問題等。

上述問題都不是單獨存在的，決策之間會相互影響，甚至不同優化目標之間是一對矛盾。通常，上述問題的決策結果之間存在關聯性，很多研究將決策問題進行聯合考慮，從整體角度出發進行優化。綜合相關文獻，并參考文獻［9］，本文將這類決策問題統稱為“聯合任務卸載和資源分配問題”。比如，文獻［10］中假設用戶端設備的芯片具有“動態電壓頻率調節”能力，通過動態調整電壓就可以調整用戶設備CPU頻率和耗電量，從而影響任務的執行速率，并對兩者關系進行建模，提出相應的算法來最小化能量消耗和應用程序執行的延遲。文獻［11-12］利用 CPU運行周期和CPU功耗之間的關系進行建模，以最小化能耗或時延為目標提出優化方案。也有研究為邊緣計算模式提出了框架和工作流程設想，但較少關注邊緣服務器合作對于邊緣網絡的重要性。

本研究具有以下特點：①關注邊緣服務器側的資源分配，未對客戶端的資源分配進行干預；②假設調度策略事先不知道用戶任務的全局信息，即任務何時到達、將會持續多久等；③強調通過任務調度的方式來加強邊緣服務器之間的合作，提高峰值抗壓能力；④認為服務存在最低資源限制，低于閾值時服務將無法運行，高于閾值時服務性能將隨著CPU時間的增加而線性增加。

1 模型構建

進行資源分配和任務調度問題的建模。用戶任務卸載的時延可以分成兩部分：通信時延和計算時延。場景為移動邊緣網絡下，無線傳輸時延不是本文關注的重點，可以將其看做一個相對固定的常數tw。當任務到達基站之后，如果直連的邊緣服務器有能力對任務進行處理，則沒有后續的傳輸時延；如果需要以此為中轉將任務發送到邊緣域的其他邊緣服務器進行處理，則需要增加backhual的傳輸時延。

本文中主要針對視頻分析這一類流式業務場景。對于流式的任務來說，每個任務（一幀）的大小相對固定，所以可以用一個常數tlj來表示第j類服務在backhual中從邊緣服務器傳輸到控制器的時延。假設邊緣存在m種服務和n臺邊緣服務器，符號i∈m表示某種服務，j∈n表示某臺邊緣服務器。

1.1 邊緣緩存

首先考慮邊緣緩存［13］問題。本文中認為邊緣服務的成功運行需要資源超過某個閾值Thr，低于該閾值服務將無法運行。而邊緣的資源又是相對有限的。這里就存在一個決策問題，緩存哪些種類的服務來使得平均時延最低。引入決策變量xi，j來表示服務i是否運行在服務j上。本文中的模型符號說明見表1。

表1 模型符號說明

1.2 邊緣計算時延

計算時延是指任務在邊緣服務器中計算所需的時間。任務的計算時延同時受多個維度計算資源的影響，本文中只考慮CPU頻率對計算時延的影響。假設某個任務的執行時間服從參數為1/μ的負指數分布，μ為服務速率。假設當服務分配到的CPU頻率超過前述的資源閾值后，這個服務速率將隨CPU頻率的增加呈線性增長。例如，服務i的系數是ki，在邊緣服務器j上分配到的處理器頻率為 fi，j，則服務速率是 μi，j=ki×fi，j。可以用簡單的m/m/1排隊模型來建模任務的計算時延。

1.3 云計算時延

由于邊緣資源的限制以及突發流量的存在，邊緣無法及時處理用戶卸載的任務。在此情況下，任務有可能被發送到遠端的數據中心執行，本文將這個過程的時延稱為云計算時延。云計算時延經歷的通信時延遠大于邊緣網絡內部的通信時延tl。有一點值得注意，云計算時延會隨著時間改變，但在一個較短的時間內，可以假設邊緣到云數據中心的通信延遲是一個常數。因為云數據中心有近乎無限的計算資源，相比邊緣需要更少的計算時延，而且相對固定，因此總的來看，對于每種服務i，在一個周期內可以用一個常數來代表云計算時延，用符號Ti表示。

1.4 優化模型

分析3種時延之后，對計算卸載時延進行建模。目的是通過調整邊緣網絡的資源分配和任務調度來優化整個邊緣網絡的延遲性能。每種服務的每個用戶的時延都是一個隨機變量，可以對這些時延做一個加權平均（權重為θ）來表征整個邊緣的性能。

如圖2所示，當某個邊緣服務器的直連用戶較多地使用某種服務時，可以適當調高該種服務的資源數量，即提高fi，j。當邊緣服務器上多種服務的用戶請求都比較多時，就需要決定哪些服務、多少比例的請求將會被遷移，以及遷移的任務將會到達何處執行。到達率調整量di，j代表對邊緣服務器j上服務i的負載調整。當di，j是正數時，表示需要將一部分域內的其他基站同種服務的負載遷移到本服務器上；反之，表示需要將一定量的用戶請求轉移到其他節點進行計算，有可能是其他邊緣服務器，也有可能是云數據中心。當確定了 di，j之后，每個節點按照比例 ρi，j=di，j/λi，j將到達的用戶任務請求轉發給控制器，再由控制器決定轉發的目的節點。

根據排隊論中m/m/1模型，可以得到邊緣服務器j上服務i的計算時延為

即使是同種服務，每個邊緣服務器都有自己的排隊隊列，tc均不相同，需要根據其處理的用戶數來進行加權平均。每個邊緣服務器所占負載比重為：

則服務i在邊緣的平均計算時延為

除了在邊緣執行的任務，還有一部分任務被卸載到云端執行，在云端執行的任務比例由每個邊緣服務器到達率調整量di，j決定。在 backhual傳輸引入的時延計算也類似。故其傳輸比例可以分別表示為：

引入的平均時延分別表示為：

綜上所述，對某種服務i，其平均延遲可以表示成：

再利用服務的權重進行加權平均，就可以得到邊緣域平均時延的完整表達為：

決策存在一定的約束：

1）為了保證計算隊列收斂，服務速率要大于請求到達率，即

2）邊緣服務器至多將直連的任務都轉發出去，服務到達率經過調整不能小于0，即：

3）邊緣域內只處理內部產生的需求，剩余需求交由云端執行，故服務到達率調整求和應小于等于0，即

4）同一邊緣服務器上，分配給不同服務的資源總和不能超過資源限制，即

5）為某種服務分配的CPU頻率應當大于等于最小門限，即

綜上所述，完整的優化模型為：

2 聯合決策算法

該優化問題為混合整數非線性規劃，此類問題在多項式時間內無法找到全局最優解［14-15］。本文中提出一種JRATS（joint resource allocation&task scheduling）算法，將問題拆分成兩個相對容易求解的子問題，即服務緩存和資源任務聯合調度。服務緩存子問題是對決策變量xi，j進行決策，在該部分提出一種貪心策略，為每個邊緣服務器確定應緩存的服務。資源任務聯合調度則是在已確定服務緩存的基礎上，對資源配置和任務調度進一步優化，采用的方法是類似內點法（interior-point method）的梯度下降方法。

2.1 服務緩存子問題

服務緩存子問題是一個01規劃的問題，與后續子問題緊密耦合。當控制器控制的邊緣服務器數量較多時，常規解法耗時會迅速增加，求解比較困難。因此本文給出一種貪心策略，用于決定邊緣服務器上的服務緩存，可大大降低求解時間，同時避免過多的性能損耗。

在邊緣選定服務進行緩存，本質上是為了讓更多用戶卸載的任務在邊緣得到執行，而無需卸載到云端。因此某種服務的任務到達率是重要的參考指標。另外，不同任務對延遲的容忍程度不同，對延遲容忍度較低、權重較高的任務應該優先得到滿足。對上述兩點進行權衡，引入“緩存優先指標”，見式（15）所示。每臺邊緣服務器根據優先指標來排序，依次按最低運行要求分配計算資源，直到服務器資源耗盡。對于被分配計算資源的服務，將服務緩存決策變量 xi，j置1。

2.2 資源任務聯合調度

確定邊緣服務器緩存的服務種類之后，有可能還有資源盈余，剩余資源需要在這些確定緩存的服務之間進行分配。而分配計算資源的方案會影響服務隊列的等待時間。要最優化時延，還需要確定計算任務在邊緣和云端的比例。因此還有兩個決策需要決定：①每種服務需要分配的計算資源，該決策由fi，j確定；② 需要作出調整的任務比例，該決策由 di，j確定。

兩個決策問題無法分開決策，需要在一個優化過程中得出結果。在確定服務緩存決策變量xi，j后，原目標函數從原本的混合整數非線性規劃（MINLP）轉化成一般的帶約束非線性規劃（NLP）問題。

2.3 優化目標松弛

采用“對數障礙”的方法［16］，經過松弛，原目標可以轉化為：

然后通過最速下降法進行求解。下面分別對兩類變量求取梯度的閉式：

確定下降方向（負梯度）后，還需確定步長，本文中選用簡單的黃金分割法進行一維搜索。而計算資源fi，j可以初始化為該種服務的最低資源要求；任務調整量di，j可以初始化為將所有任務都轉發出去，即-λi，j，這樣的時延一定是最大的，因為沒有任務在本地執行。

2.4 偽代碼

通過前文的推導，將原來的混合整數非線性規劃問題轉化為相對容易求解的服務緩存和資源任務聯合調度2個子問題，兩個子問題的優化過程就是JRATS算法的步驟。將上述求解過程合并，得到完整問題的求解方案。偽代碼展示的是決策算法，用于決策服務緩存、服務器內資源分配、節點間任務調度等問題。

算法：JRATS

輸入：迭代輪數IterNum

輸入：精度調整輪數R

輸出：xi，j，fi，j，di，j

1：初始化：對數障礙參數r=0.01

2：初始化：xi，j=0，?i∈M，?j∈N

3：for邊緣服務器 j∈N do

4：for服務 i∈M do

5：計算服務緩存優先指標 ranki，j=θi×λi，j

6：end for

7：服務緩存順序orderj對rankj進行逆序排序

8：資源余量rest=C

9：for服務 i∈orderjdo

10：if資源余量rest≥門限Thrithen

11：xi，j=1

12：rest=rest-Thri

13：end if

14：end for

15：end for

17：for round=1→R do

18：for iter=1→Iter Num do

19：根據式（19）、（20）和障礙函數參數 r，計算梯度

20：通過一維搜索確定下降步長α，β

23：end for

24：提高障礙函數精度r=r×0.1

25：end for

3 實驗仿真與結果分析

采用Matlab作為仿真工具，對JRATS算法性能進行仿真驗證。對比邊緣合作和無合作的效果，同時對比不同的貪心策略，只按照權重貪心或只按照到達率進行貪心。而對于沒有邊緣合作，單機進行決策的算法，文獻［14-15］中的方案均為在縱向方向進行均衡，可作為JRATS算法的對比。

3.1 性能指標

算法目的是降低請求所需時延，提高用戶體驗，本文中設置以下性能指標：①系統中用戶的平均時延，這也是算法直接優化的目標；② 滿足QoS的用戶比例，雖然該指標不是算法的直接優化目標，但QoS的滿足率可以反映將平均時延作為優化目標是否合理。同時，運營商十分看重該指標，該指標具有重要意義。

QoS滿足率的計算。在每個邊緣決策樣本中會設置一個QoS時延限制，當用戶的時延小于該QoS時延限制時，可認為滿足QoS要求。通過排隊模型可以得到每個隊列的平均時延，所以本文直接將平均時延是否小于QoS時延限制作為這批用戶是否滿足QoS的標準。

邊緣負載程度描述。邊緣負載是指單位時間內邊緣域中用戶產生的計算卸載請求，即請求的到達率。本文中為負載大小設計了一個標桿值benchmark，反映邊緣負載相對于邊緣承受能力的大小，從而擺脫服務種類m和邊緣服務器數量n變動的影響。假設每臺邊緣服務器的計算資源為C（比如CPU的主頻）。對于n臺邊緣服務器，式（19）展示了標桿值的計算方法。當然，計算資源還需要乘以服務率系數k才能反映處理用戶的能力。標桿值本質上是整個邊緣域所有的計算資源。

3.2 結果分析

圖3所示為邊緣域內是否進行邊緣合作的效果對比。與JRATS算法對比的是沒有邊緣合作的方案。圖中數據為m=10，n=20時所測得的數據。每臺邊緣服務器單獨進行服務緩存和調度決策。“上限”折線反映的是將所有任務傳輸到云端執行所需要的平均時延，即沒有任何調度和本地執行，該值可作為性能優化的下限。

圖3分別為根據本文中提出的JRATS算法和文獻［14］中提出的wall算法，以及基于文獻［15］思想的算法plain計算得到的結果。

可以看出：在較低負載等級情況下，具有邊緣合作思想的JRATS算法可以達到更低的平均系統時延。這是因為利用邊緣閑置的服務器來為鄰居節點提供一定的計算服務可以提升系統整體的性能。隨著邊緣負載的增加，3種算法的平均時延都逐漸增加，這說明邊緣的資源在處理邊緣負載時已力不從心，需要將更多任務傳遞到云端執行，而邊緣合作能夠提高邊緣系統的抗壓能力。通過對結果的分析發現：利用邊緣合作的JRATS算法相比未利用邊緣合作的算法平均降低了70%的時延。

圖4所示為計算得到的任務被傳輸到云端執行的比例，稱為云端卸載比例。可以看出，JRATS在低級和中級壓力情況下能夠顯著地降低云端卸載比例，從而獲得更低的平均時延。在大負載下，邊緣合作也無法繼續降低時延，退化成未合作的模式。

圖5 所示為計算得到的上述過程中任務經過傳輸而不在本地執行的比例，更多的網絡傳輸可能引入更多的傳輸開銷，但也更利于資源的集中。可以看出，JRATS算法采用將更多任務進行二次轉移的辦法來減少本地任務執行的壓力。

圖6 所示為采用不同調度算法時對用戶QoS滿足率的統計（時延限定為0.5 s）。可以看出，JRATS能在低壓力下保證較好的QoS滿足率。隨著邊緣負載壓力的增大，不論是哪種調度算法，用戶的QoS滿足率都呈下降趨勢。但是不論在哪個負載區間，JRATS都能取得更好的表現，這也驗證了JRATS算法滿足了提高邊緣峰值抗壓能力的設計目標。

4 結論

提出了邊緣聯合分配與任務調度算法。分析了邊緣資源分配和任務調度的特點，根據服務緩存需要分配最低資源的要求，將邊緣網絡的決策問題建模成聯合資源分配和任務調度模型，在一個優化過程中得出資源分配和任務調度方案JRATS。并將原NP-hard問題通過拆分成服務緩存和聯合調度兩個子問題進行求解。最后利用仿真對方案的效果進行評估，證明JRATS能有效地整合利用邊緣資源，提高邊緣承載峰值負載的能力，減少用戶時延。