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

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

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

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

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

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

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

1 模型構建

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

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

1.1 邊緣緩存

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

表1 模型符號說明

1.2 邊緣計算時延

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

1.3 云計算時延

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

1.4 優(yōu)化模型

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

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

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

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

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

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

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

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

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

決策存在一定的約束：

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

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

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

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

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

綜上所述，完整的優(yōu)化模型為：

2 聯(lián)合決策算法

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

2.1 服務緩存子問題

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

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

2.2 資源任務聯(lián)合調度

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

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

2.3 優(yōu)化目標松弛

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

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

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

2.4 偽代碼

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

算法：JRATS

輸入：迭代輪數(shù)IterNum

輸入：精度調整輪數(shù)R

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

1：初始化：對數(shù)障礙參數(shù)r=0.01

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

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

4：for服務 i∈M do

5：計算服務緩存優(yōu)先指標 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：根據(jù)式（19）、（20）和障礙函數(shù)參數(shù) r，計算梯度

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

23：end for

24：提高障礙函數(shù)精度r=r×0.1

25：end for

3 實驗仿真與結果分析

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

3.1 性能指標

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

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

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

3.2 結果分析

圖3所示為邊緣域內是否進行邊緣合作的效果對比。與JRATS算法對比的是沒有邊緣合作的方案。圖中數(shù)據(jù)為m=10，n=20時所測得的數(shù)據(jù)。每臺邊緣服務器單獨進行服務緩存和調度決策?！吧舷蕖闭劬€反映的是將所有任務傳輸?shù)皆贫藞?zhí)行所需要的平均時延，即沒有任何調度和本地執(zhí)行，該值可作為性能優(yōu)化的下限。

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

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

圖4所示為計算得到的任務被傳輸?shù)皆贫藞?zhí)行的比例，稱為云端卸載比例?？梢钥闯觯琂RATS在低級和中級壓力情況下能夠顯著地降低云端卸載比例，從而獲得更低的平均時延。在大負載下，邊緣合作也無法繼續(xù)降低時延，退化成未合作的模式。

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

圖6 所示為采用不同調度算法時對用戶QoS滿足率的統(tǒng)計（時延限定為0.5 s）?？梢钥闯觯琂RATS能在低壓力下保證較好的QoS滿足率。隨著邊緣負載壓力的增大，不論是哪種調度算法，用戶的QoS滿足率都呈下降趨勢。但是不論在哪個負載區(qū)間，JRATS都能取得更好的表現(xiàn)，這也驗證了JRATS算法滿足了提高邊緣峰值抗壓能力的設計目標。

4 結論

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