鮮永菊，宋青蕓，郭陳榕，劉 闖

(重慶郵電大學 通信與信息工程學院，重慶 400065)

0 引 言

移動設備受限于小巧的體積，在計算能力與能耗方面有較大的局限。移動邊緣計算(Mobile Edge Computing,MEC)通過將云計算能力下沉至移動終端側(cè)，可以近距離為移動用戶提供計算服務，有助于用戶高效地執(zhí)行任務，減少能耗，提高執(zhí)行任務能力[1]。

盡管MEC具有許多優(yōu)勢，但MEC服務器自身有限的計算能力仍會帶來許多挑戰(zhàn)，主要體現(xiàn)在計算資源供需不平衡，特別是部署在熱點小區(qū)(商圈、密集住宅區(qū))中的MEC服務器，將面臨大量任務卸載請求，若無法及時處理眾多請求，會導致用戶體驗降低[2]。針對此類問題，文獻[3-6]通過拒絕、推遲或任務排隊的方式來緩解MEC服務器過多的工作量，雖然改善了資源有限的問題，但可利用的資源沒有得到擴展。因此，越來越多的學者將目光投向宏觀場景下的多MEC服務器協(xié)作。

協(xié)作通信被廣泛應用在移動通信網(wǎng)絡中。多MEC服務器協(xié)作需要對MEC服務器的實時信息進行控制，當前主流的方案主要是軟件定義網(wǎng)絡(Software Defined Network,SDN)集中控制與分布式控制[7-9]，現(xiàn)有的研究通常忽略兩種方案由于信息交互帶來的能耗與時延，而專注于制定卸載策略。

關(guān)于MEC服務器協(xié)作卸載的研究，文獻[10]針對協(xié)作小區(qū)之間的組合問題，提出了一種基于博弈論的任務分組方案，將多個熱點小區(qū)與非熱點小區(qū)生成多個協(xié)作集，但未具體研究協(xié)作集內(nèi)的卸載與資源分配；文獻[11]研究了兩個邊緣節(jié)點之間的協(xié)作，以最大化降低時延，該問題通過遺傳粒子群算法求解，但文獻中涉及到的MEC服務器數(shù)量較少，并且無法保證啟發(fā)式算法解的穩(wěn)定性；文獻[12]在能耗約束下提出了最小化時延的優(yōu)化問題，并設計算法將多個任務協(xié)作到多個MEC服務器組成的集群中，但未優(yōu)先將任務卸載至本小區(qū)的MEC服務器上，這可能會影響其他小區(qū)執(zhí)行自身的任務；文獻[13]通過一種迭代更新方法將主MEC服務器過量的任務卸載至其他MEC服務器，但未對計算資源進行分配；文獻[14]提出了一種MC-GBA算法，可以依據(jù)代價將主MEC服務器中過量的任務卸載至從MEC服務器，實現(xiàn)計算資源的擴充；文獻[15-17]通過遠端云中心與本地MEC實現(xiàn)多級卸載，并分別通過任務屬性、任務需求以及資源剩余劃分出不同的卸載用戶。

基于以上研究，本文采用主從MEC服務器協(xié)作卸載的方式，以改善熱點小區(qū)內(nèi)計算資源有限的問題。在主從MEC系統(tǒng)中，通過SDN的集中控制，主MEC服務器將自身無法完成的任務二次卸載至附近仍有可利用計算資源的從MEC服務器進行計算，實現(xiàn)了計算資源的拓展。為了最小化熱點小區(qū)內(nèi)請求用戶執(zhí)行任務的總代價，本文提出一種基于主從MEC系統(tǒng)的任務聯(lián)合卸載方案，依次分析了不同屬性任務以及從MEC服務器數(shù)量對方案的影響，并與其他卸載方案對比驗證了所提方案的有效性。

1 系統(tǒng)模型

1.1 網(wǎng)絡場景

在一個多小區(qū)計算場景，每個小區(qū)內(nèi)有一個MEC服務器部署在基站側(cè)，負責處理本小區(qū)內(nèi)產(chǎn)生的計算任務，多小區(qū)之間通過SDN控制器集中控制，結(jié)構(gòu)如圖1所示。MEC服務器和用戶均可通過基站與SDN控制器進行信令傳遞，SDN控制器收集各個服務器可提供的計算資源并對資源池進行更新，這樣，SDN可以集中控制多個小區(qū)內(nèi)的計算任務卸載以及資源分配。

圖1 基于SDN集中控制的主從MEC系統(tǒng)結(jié)構(gòu)

本文研究熱點小區(qū)(主小區(qū))內(nèi)的高負載任務卸載優(yōu)化，將熱點小區(qū)MEC服務器無法完成的計算任務二次卸載到周圍尚有計算資源的小區(qū)(從小區(qū))進行計算。這個過程中，暫不考慮從小區(qū)內(nèi)的任務，只讓從小區(qū)充當輔助計算節(jié)點，同時忽略集中控制信令傳遞所需的時延與能耗。此外，主小區(qū)內(nèi)任務不可拆分，即任務執(zhí)行只有本地執(zhí)行、主MEC服務器執(zhí)行以及從MEC服務器執(zhí)行三種狀態(tài)，同時假設每個用戶攜帶一個計算任務。

1.2 通信模型

用戶通過無線網(wǎng)絡與MEC服務器進行交互。為了簡化問題，假設在同一小區(qū)內(nèi)多用戶占用相等且不相交頻譜資源，并且不考慮小區(qū)內(nèi)部通信干擾。任務上行速率為

(1)

式中：Ptra,i表示用戶i的發(fā)送功率，gi表示用戶i與MEC服務器之間的信道增益，N0表示信道單位噪聲與干擾的功率譜密度。用戶通過無線信道上傳任務花費時延與能耗分別為

(2)

(3)

由于MEC服務器返回任務結(jié)果數(shù)據(jù)量很小，任務結(jié)果傳回用戶的時延將忽略。

考慮MEC服務器間通信，主MEC服務器與從MEC服務器通過有線鏈路相連，主MEC服務器到從MEC服務器方向的傳輸速率為rM，此部分不涉及到用戶能耗代價，MEC服務器之間任務傳輸?shù)臅r延為

(4)

1.3 計算模型

1.3.1 本地計算

設用戶終端的計算能力為floc,i，任務在終端本地執(zhí)行的時延與能耗分別為

(5)

Ei,0=κibidi(floc,i)2。

(6)

式中：κi是與硬件架構(gòu)相關(guān)的常數(shù)。記αi和βi為用戶對于時延與能耗的權(quán)重系數(shù)，用戶本地執(zhí)行總代價為

Ui,0=αiTi,0+βiEi,0。

(7)

1.3.2 MEC服務器計算

任務如果卸載到MEC服務器執(zhí)行，需要占用MEC服務器的計算資源。記Fj表示第j個MEC服務器可提供的總計算資源，F(xiàn)i,j表示MEC服務器j為用戶i分配的計算資源。

當任務在主MEC服務器執(zhí)行，此時j=1，任務計算的時延與能耗可以分別表示為

(8)

(9)

這里用戶產(chǎn)生的能耗為用戶上傳任務產(chǎn)生的能耗。那么，用戶的總計算代價可表示為

Ui,1=αiTi,1+βiEi,1。

(10)

若任務在從MEC服務器執(zhí)行，那么此時1

(11)

這里任務執(zhí)行產(chǎn)生的能耗同樣為用戶卸載任務產(chǎn)生的能耗，表示為

(12)

用戶的總計算代價為

Ui,j=αiTi,j+βiEi,j，1

(13)

綜合考慮任務在MEC服務器端執(zhí)行，可以將任務執(zhí)行代價函數(shù)寫為

(14)

1.4 卸載模型與資源分配模型

記本地執(zhí)行任務的決策向量集(卸載集)為A={a1,a2,…,an}，其中ai∈{0,1}，并且

(15)

卸載集A記錄了每個任務是否卸載執(zhí)行，其中卸載執(zhí)行的任務還需選擇目標MEC服務器。任務的多MEC服務器選擇矩陣表示為

(16)

式中：bi,j∈{0,1}，取值表示含義為

(17)

A、B兩個決策變量可以表示多任務卸載決策。對于計算資源分配，本文引入計算資源分配矩陣F，表示為

(18)

1.5 最小化代價優(yōu)化問題

任務執(zhí)行過程中，時延與能耗是用戶感知明顯的，也是任務在MEC服務器計算相對于本地計算最具有優(yōu)勢的性能指標。本文的優(yōu)化目標是在主MEC服務器計算資源有限的情況下，最小化主小區(qū)內(nèi)所有任務的執(zhí)行代價之和?；谥皩ο到y(tǒng)模型的分析，優(yōu)化問題P1可表示為

(19a)

s.t.C1:ai∈{0,1}

(19b)

C2:bi,j∈{0,1}

(19c)

(19d)

(19e)

對于優(yōu)化問題P1，目標函數(shù)W中第一項表示本地執(zhí)行的總代價，第二項表示所有卸載到MEC服務器中任務執(zhí)行的總代價。約束條件C1、C2表示卸載決策變量ai與bi,j為0～1整數(shù)變量，約束條件C3保證任務只能在本地計算或在某一個MEC服務器上進行計算，約束條件C4保證在每個MEC服務器上計算資源在有限的范圍內(nèi)進行分配。

1.6 優(yōu)化問題分析與方案制定

為最小化代價，需要得到優(yōu)化變量A、B、F的最優(yōu)解。但由于問題P1是一個混合整數(shù)非線性規(guī)劃問題，并且優(yōu)化函數(shù)中存在二元變量，導致該優(yōu)化問題非凸，不能通過常規(guī)凸優(yōu)化解法求解。

為求解優(yōu)化問題，首先考慮原問題的三個優(yōu)化變量。若已知需要卸載執(zhí)行的任務(卸載集A的解)，便可以通過一種方法得到MEC服務器選擇矩陣B與計算資源分配矩陣F的解；同時，卸載集A的求解又受到矩陣B與矩陣F值的影響。綜合以上分析，求解方案可設定初始卸載集A0，接著求得原問題松弛后的MEC服務器選擇矩陣B與資源分配矩陣F，最后再對卸載集A進行優(yōu)化。這樣，可將原問題分解為部分任務卸載、多MEC服務器選擇和計算資源分配三步求解。綜上，基于主從MEC系統(tǒng)的聯(lián)合卸載方案實現(xiàn)流程如圖2所示。

圖2 聯(lián)合卸載方案流程圖

2 聯(lián)合卸載方案

2.1 計算資源分配

當卸載集A與MEC選擇向量集B確定之后，記本地執(zhí)行的任務集合為N0，選擇卸載到MEC服務器j執(zhí)行的任務集合為Nj。此時，原問題P1可轉(zhuǎn)化為

(20a)

(20b)

由于不同MEC服務器的計算資源分配是相互獨立的，所以不同MEC服務器的計算資源分配不相互干擾。為了使該問題更加清晰，進行未知變量替換。令ωi,1=1/Fi,1，ωi,j=1/Fi,j其中Fi,1≠0，F(xiàn)i,j≠0，問題P2變?yōu)?/p>

(21a)

(21b)

容易看出，優(yōu)化問題P2′的優(yōu)化目標函數(shù)以及約束條件均為凸函數(shù)，同時，ωi,j的可行域是連續(xù)的凸集，因此P2′是一個凸優(yōu)化問題。通過構(gòu)造拉格朗日函數(shù)并結(jié)合KKT(Karush-Kuhn-Tucker)條件，可得到優(yōu)化問題P2′的最優(yōu)解為

(22)

2.2 多MEC服務器選擇

在主從MEC系統(tǒng)中，從MEC服務器負責執(zhí)行主MEC服務器上過量的任務，因此，為了求解多MEC服務器選擇，首先需確定可以在主MEC服務器上完成的任務集合N1，再將過量的任務分配給從MEC服務器。

規(guī)定所有可在主MEC服務器執(zhí)行的任務需滿足式(23)約束：

Ui,1≤Ui,0,?Ti∈N1，

(23)

即對于集合N1中的所有任務，執(zhí)行代價應小于本地執(zhí)行代價。

為了在完成多MEC服務器選擇的同時最小化任務執(zhí)行代價，本文提出一種基于貪婪的多MEC選擇算法(Greedy Based Multi-MEC Selection Algorithm，GBMS)。GBMS算法通過貪婪思想分階段進行求解，對于多MEC服務器選擇問題，該算法將較為容易地得到一個次最優(yōu)解。

輸入：多任務信息，主、從MEC服務器信息、集合Na。

for

l=l+1;

N1,l=N1,l-1∪{Tl};

else

Nc,l=Nc,l-1∪{Tl};

N1,l=N1,l-1;

end if

end if

if(l==L)

break;

end if

end for

根據(jù)集合N1,l與集合Nc,l生成多MEC服務器選擇矩陣B。

輸出：最終代價U(N1,L)+U(Nc,L)，多MEC服務器選擇矩陣B。

算法保證了二次卸載的任務是主MEC服務器過量的任務。在算法中，主MEC服務器上任務代價U(N1,l)容易求解，但從MEC服務器上任務執(zhí)行代價U(Nc,l)需要將過量任務匹配到M-1個從MEC服務器上后才可求解。

為了更清晰地表述集合Nc中最小化任務代價的問題，假設此時集合Nc中共有N′個任務。另外，在這個問題中只需要考慮M-1個從MEC服務器。因此，本文引入任務分配矩陣Z=(zi,j)N′×M-1,zi,j∈{0,1}表示要求解的矩陣。此時，最小化集合Nc中任務代價的問題為

(24a)

s.t.C1:zi,j∈{0,1},

(24b)

問題P3中目標函數(shù)W′是原問題P1目標函數(shù)W去除已確定在主MEC服務器與本地執(zhí)行的任務后的目標函數(shù)，約束條件保證每個任務都只能在一個從MEC服務器上執(zhí)行。對于該問題，將會有2N′+1種選擇，是NP-hard問題。

為有效解決這個問題，本文通過一種連續(xù)變量替換結(jié)合迭代近似的方法進行求解[18]。首先對原優(yōu)化問題進行變量近似替換，引入連續(xù)變量vi,j。vi,j有以下性質(zhì)：

(25)

另外設定線性函數(shù)V(vi,j)，其表達式為

(26)

式中：ε是一個小值，t是迭代次數(shù)。接著，用vi,k替換P3約束條件中的zi,j，用V(vi,j)替換P3表達式中的zi,j，替換變量后的問題是凸優(yōu)化問題[18]，容易求解。

(27)

輸入：從MEC服務器執(zhí)行任務集合Nc，從MEC服務器信息。

初始化：t=0;

對集合Nc中的計算任務:

for

t=t+1;

將式(22)代入問題P3，并替換變量;

break;

end if

end for

輸出：任務分配矩陣Z、二次卸載任務代價U(Nc)。

2.3 卸載集更新

完成多MEC服務器選擇以及計算資源分配之后，通過卸載集更新策略對上一次卸載集A進行更新。為減少不必要的卸載，制定卸載更新策略為

(28)

當本地執(zhí)行代價不大于卸載執(zhí)行代價時，用戶不進行任務卸載，這樣確保單個用戶執(zhí)行代價不會過大，同時也不占用MEC服務器的計算資源。另外，結(jié)合圖2所示流程圖與卸載更新策略，當聯(lián)合方案沒有產(chǎn)生最終決策時，將嘗試卸載本地執(zhí)行且執(zhí)行代價最大的任務。這是由于該任務最可能通過卸載減少代價，若該任務卸載無法帶來代價的減少，則可認為方案已經(jīng)得到最優(yōu)解。

2.4 聯(lián)合卸載方案時間復雜度

假設聯(lián)合卸載方案一共進行S次迭代，每次迭代中需要執(zhí)行GBMS算法、計算資源分配以及卸載集更新。其中，計算資源分配只需相應的值計算；GBMS算法通過一輪迭代遍歷Na中所有用戶，迭代次數(shù)為L，在每次迭代中，U(N1)的求解可直接計算得到，U(Nc)的求解需要通過二次卸載算法求得，二次卸載算法也是一輪迭代，迭代次數(shù)為T，故GBMS算法的時間復雜度為O(LT)；卸載集更新中尋找到本地執(zhí)行且代價最大的用戶的時間復雜度為常數(shù)復雜度O(N)。因此，本文聯(lián)合卸載方案的時間復雜度為O(NS+LTS)。

3 仿真與分析

3.1 仿真參數(shù)設置

本文仿真基于Matlab平臺，仿真參數(shù)設置為[3,13]：網(wǎng)絡總帶寬B為5 MHz，信道噪聲與干擾的功率譜密度為-174 dBm/Hz,信道增益在[-50,-30]內(nèi)呈均勻分布，用戶i本地的CPU頻率floc,i在[0.5,1]GHz中隨機分布，并且其任務的數(shù)據(jù)大小bi在[600,1 000]kB中隨機分布，單位任務計算量di在[200,600]cycle/b中隨機取值，用戶i的發(fā)射功率P=0.1 W，系數(shù)κ=10-27，默認狀態(tài)下有40個用戶請求卸載。主MEC服務器提供的CPU頻率F1=20 GHz，從MEC服務器提供的CPU頻率在[2,8]GHz內(nèi)隨機分布，MEC服務器之間有線鏈路傳輸速率為20 MB/s，默認狀態(tài)下有5個從MEC服務器參與輔助計算。

3.2 仿真結(jié)果分析

在任務總計算量不變的情況下，本文方案中任務數(shù)據(jù)量與代價的關(guān)系仿真結(jié)果如圖3所示?？梢钥吹?，總代價隨數(shù)據(jù)量增加而增加。當數(shù)據(jù)量較小時，由于傳輸帶來的卸載代價較少，方案將大量任務卸載，因此本地代價較低。隨著任務數(shù)據(jù)量的增加，傳輸帶來的卸載代價增多，方案決策任務在本地執(zhí)行，因此本地代價增加。

圖3 數(shù)據(jù)量與代價關(guān)系圖

圖4是當任務數(shù)據(jù)量不變時，任務執(zhí)行代價隨單位計算量增加的變化情況。可以看到，隨單位計算量增加，總的代價也隨之增加，本地代價先增加后減少，先增加是因為計算量增加導致的代價增加；當本地代價超過卸載執(zhí)行代價時，本文方案會將任務卸載執(zhí)行，因此在圖中本地代價曲線下降，并可預期本地代價將逐步減少為零。

圖4 單位計算量與代價關(guān)系圖

圖5為本文方案中從MEC服務器數(shù)量與用戶卸載數(shù)量的關(guān)系，可以看到，隨著從MEC服務器數(shù)量的增加，卸載到主MEC服務器用戶的數(shù)量大體相同，這是因為本文方案將任務優(yōu)先卸載到主MEC服務器執(zhí)行。在這個過程中，觀察到從MEC服務器執(zhí)行的任務數(shù)量并不是以線性增長的。這是因為當大量用戶卸載時，卸載代價也隨之增加，受卸載更新策略的影響，方案會使一些任務在本地執(zhí)行。

圖5 從MEC服務器數(shù)量與用戶卸載數(shù)量關(guān)系

從圖6中可以看出本文方案隨著從MEC服務器數(shù)量增加，系統(tǒng)總代價將減少。并且，觀察到當從MEC服務器足夠多時，卸載代價與本地代價將趨于穩(wěn)定。這是因為當從MEC服務器數(shù)量增多，可以使更多任務卸載執(zhí)行，但這也增加了任務傳輸?shù)拇鷥r。因此，卸載代價與本地代價將逐漸趨于穩(wěn)定。

圖6 從MEC服務器數(shù)量與代價關(guān)系

從圖7中可以看出隨著請求卸載任務數(shù)量的增加，本文方案優(yōu)先將任務卸載到主MEC服務器執(zhí)行。當主MEC服務器執(zhí)行的任務增多時，由于受到式(23)的限制，部分任務被卸載到從MEC服務器執(zhí)行。最終當主MEC服務器與從MEC服務器無法再降低任務執(zhí)行代價時，過量的任務將在本地執(zhí)行。

圖7 請求任務個數(shù)與實際卸載任務關(guān)系

圖8為用戶數(shù)量與任務執(zhí)行總代價的關(guān)系，可以看到當用戶數(shù)量較少時隨機方案的代價最少。這是因為隨機方案將任務隨機分配給不同的MEC服務器，可利用的資源更多，而本文方案與MC-GBA方案將任務優(yōu)先卸載至主MEC服務器，并沒有利用從MEC服務器的資源。隨著用戶數(shù)量增加，本文方案可以獲得最少的代價，這是因為本文方案不斷地將最有可能減少代價的任務卸載，直到?jīng)]有代價的更新，因此代價低于其他方案。

圖8 用戶數(shù)量與總代價關(guān)系對比

圖9為從MEC服務器數(shù)量對系統(tǒng)總代價的影響。如圖所示，在沒有從MEC服務器時，本文方案的代價大于統(tǒng)一方案的代價。這是由于本文方案基于貪婪策略為主MEC服務器分配任務，得到的不是全局最優(yōu)解，但貪婪思想可以減少計算復雜度。隨著從MEC服務器數(shù)量增多，除統(tǒng)一方案與本地執(zhí)行方案，其他方案可利用的資源增加，代價進一步降低。本文方案相比于MC-GBA方案對多MEC服務器中的任務分配更加合理，同時每次更新盡可能減少代價，因此，本文方案有最低的總代價。

圖9 從MEC服務器數(shù)量與總代價關(guān)系對比

4 結(jié)束語

本文研究了主從MEC服務器的協(xié)作卸載問題，提出了一種聯(lián)合卸載方案。方案每次迭代，首先根據(jù)設計的GBMS算法完成多MEC服務器選擇，接著求解凸優(yōu)化問題得到計算資源分配，最后更新卸載集，嘗試卸載本地執(zhí)行且代價最大的任務。仿真結(jié)果表明，所提方案能夠緩解熱點小區(qū)MEC服務器計算資源有限的問題，并有效降低請求卸載用戶的總代價。

未來的研究目標是整合熱區(qū)分集技術(shù)與任務卸載技術(shù)，設計有效的任務卸載方案，在更廣泛的實際場景中提高MEC服務的可靠性與有效性。