移動邊緣計算中計算卸載與資源分配的聯(lián)合優(yōu)化策略①

龍 隆 劉子辰 石晶林 周一青 邱大偉 徐順清

(*中國科學(xué)院計算技術(shù)研究所移動計算與新型終端北京市重點實驗室 北京 100090) (**中國科學(xué)院大學(xué) 北京 100049)

0 引 言

隨著移動通信的高速發(fā)展以及移動終端的快速普及，許多新型應(yīng)用隨之產(chǎn)生，如虛擬現(xiàn)實、增強現(xiàn)實以及自動駕駛等[1-5]。而這類需要具有低時延高可靠特點的應(yīng)用對移動終端的計算能力提出較高要求。由于計算能力有限的移動終端在處理這類應(yīng)用時將產(chǎn)生較高的時延進而影響終端用戶的服務(wù)體驗，因此如何降低應(yīng)用處理時延、提升終端用戶的服務(wù)體驗是目前亟需解決的關(guān)鍵問題之一[6]。針對以上問題，移動云計算(mobile cloud computing，MCC)技術(shù)被提出。MCC的目標是將云端豐富的計算資源擴展至資源受限的移動終端，從而增強移動終端潛在的計算能力[7-10]。為實現(xiàn)該目標，移動終端需要將計算密集的任務(wù)通過無線接入的方式遷移至云服務(wù)器。盡管這種方式可以降低移動終端的負載但也存在明顯的缺陷，即移動終端與云服務(wù)器較遠的距離以及大量的終端業(yè)務(wù)請求將導(dǎo)致網(wǎng)絡(luò)時延的增加，從而降低終端用戶服務(wù)體驗。

為了進一步降低網(wǎng)絡(luò)時延，移動邊緣計算(mobile edge computing，MEC)作為一種新的技術(shù)被提出。在MEC系統(tǒng)中，由基站與邊緣服務(wù)器組成的服務(wù)節(jié)點就近為移動終端提供計算、通信與存儲服務(wù)[11，12]。然而與云服務(wù)器相比，服務(wù)節(jié)點的計算資源有限，過多的計算任務(wù)將為服務(wù)節(jié)點帶來額外的負載從而影響網(wǎng)絡(luò)時延。因此為解決上述問題，需要設(shè)計一種新的MEC計算卸載與資源分配的聯(lián)合優(yōu)化策略。

目前，基于MEC的卸載策略與資源分配方面已有相關(guān)研究。文獻[13]以最小化移動終端的能耗與時延為目標，對移動終端的卸載策略、計算資源以及傳輸功率進行聯(lián)合優(yōu)化。該研究優(yōu)化了移動終端的計算能力、功耗以及卸載策略，但并未考慮云端計算資源的優(yōu)化。文獻[13]是在MCC應(yīng)用場景下對時延與能耗進行研究，然而在該場景下移動終端與MCC較遠的物理距離可能會導(dǎo)致額外的時延，進而影響用戶的服務(wù)體驗。文獻[14]則提出了在MEC網(wǎng)絡(luò)下一種基于排隊論的低復(fù)雜度算法，該算法通過優(yōu)化頻譜資源與邊緣服務(wù)器的計算資源以最小化移動終端的能耗與時延。文獻[15]則提出了一種上行鏈路等功率分配方案，基于該方案對設(shè)備能耗進行優(yōu)化。此外，由于博弈論是一種有效的分布式方法，因此廣泛應(yīng)用于解決MEC場景下的資源優(yōu)化分配問題[16-18]。文獻[19]則提出了基于博弈論的計算資源與頻譜資源聯(lián)合優(yōu)化算法，解決了多終端用戶的計算卸載與資源分配問題。盡管文獻[14]與文獻[19]采用不同的方法降低了終端的時延與能耗，但兩者都忽略了下行頻譜資源對終端時延的影響，而這在實際應(yīng)用場景中并不總是成立的。例如在增強現(xiàn)實游戲應(yīng)用場景中，移動用戶將實時發(fā)送視頻數(shù)據(jù)，而服務(wù)端將對收到的視頻數(shù)據(jù)進行識別并經(jīng)過渲染將視頻返回至用戶端。在此過程中，移動用戶的任務(wù)時延不但受到數(shù)據(jù)上傳、計算時延的影響，同樣受到下行數(shù)據(jù)傳輸時延的影響，因此對于這類應(yīng)用場景，下行鏈路資源的優(yōu)化顯得十分重要。

本文在MEC系統(tǒng)下，以最小化所有移動終端的任務(wù)時延為目標，提出一種基于博弈論的計算卸載與資源分配的聯(lián)合優(yōu)化算法(computation offloading and resource allocation game, CORAG)。該算法首先將所有移動終端的卸載決策與資源優(yōu)化問題通過博弈模型進行表示并引入勢博弈概念證明該模型具有納什均衡性。隨后在已知終端卸載決策的基礎(chǔ)上，對上、下行頻譜資源以及邊緣服務(wù)器的計算資源進行聯(lián)合優(yōu)化并利用拉格朗日乘子法獲取計算資源與頻譜資源的最優(yōu)解。最后，基于獲得的最優(yōu)解，利用迭代法得到所有移動終端的納什均衡解。仿真結(jié)果表明，本文所提出的基于博弈論的計算卸載與資源分配算法與現(xiàn)有算法相比可以獲取更低的時延，進而提升用戶服務(wù)體驗。

1 基于MEC的系統(tǒng)建模與問題描述

1.1 系統(tǒng)模型

MEC系統(tǒng)的網(wǎng)絡(luò)框架如圖1所示，該系統(tǒng)由1臺邊緣服務(wù)器與1個基站組成。

邊緣服務(wù)器與基站可以為其覆蓋范圍內(nèi)的N個移動終端提供計算與通信服務(wù)。其中多個移動終端的集合表示為L={i:i=1,2,…,N}，單個終端由i進行表示。為了防止終端間干擾，基站的頻譜資源通過正交的方式分配給每個終端且總頻譜帶寬為B。假設(shè)每個終端只執(zhí)行一個計算任務(wù)wi={si,mi,ci}，其中si表示輸入數(shù)據(jù)的大小，mi表示計算結(jié)果數(shù)據(jù)的大小，ci表示一個任務(wù)所需中央處理器(central processing unit, CPU)循環(huán)總量。由于計算任務(wù)既可以本地執(zhí)行也可以在邊緣服務(wù)器執(zhí)行，因此移動終端i的卸載決策由ai進行表示，其中Ai∈{0,1}且ai∈Ai。當(dāng)Ai=1時，表示終端i將會選擇將任務(wù)卸載至MEC服務(wù)器。Ai=0時，則表示任務(wù)在終端i執(zhí)行。因此所有終端的卸載策略表示為A={Ai|Ai∈{0,1},i∈L}。

圖1 MEC系統(tǒng)網(wǎng)絡(luò)架構(gòu)

1.2 通信模型

由于每個移動終端在執(zhí)行任務(wù)時將會占用上行與下行的頻譜資源，因此終端i的上行傳輸速率可以表示為

(1)

其中，ki為終端上傳數(shù)據(jù)所占上行帶寬百分比，Pi,B表示終端的發(fā)送功率，hi,B表示基站與終端間的信道衰落系數(shù)，d為終端與基站的距離，r為路徑損耗，σ2為信道的噪聲功率。同理下行傳輸速率表示為

(2)

其中，ξi為終端接收下行數(shù)據(jù)所占帶寬百分比，hB,i表示為基站與終端間的信道衰落系數(shù)，PB為基站的發(fā)射功率。

1.3 計算模型

當(dāng)移動終端將任務(wù)卸載至邊緣服務(wù)器后，此時的任務(wù)時延主要由上行傳輸時延ti,u、下行傳輸時延ti,d、服務(wù)器計算時延ti,m以及回程鏈路時延ti,b4部分組成。由于基站與服務(wù)器之間是通過有線的方式進行連接，因此回程鏈路時延忽略不計。此外當(dāng)移動終端選擇在邊緣服務(wù)器執(zhí)行任務(wù)時，分配給移動終端的計算資源不能高于邊緣服務(wù)器最大計算能力，其中邊緣服務(wù)器的最大計算能力用fm表示。

(1)本地執(zhí)行任務(wù)。當(dāng)任務(wù)wi在本地執(zhí)行時，計算時延表示為

(3)

其中，fi,l為移動終端的計算能力。因此終端i在本地執(zhí)行任務(wù)的總時延表示為

Ui,l=ti,l

(4)

Ui,m=ti,u+ti,d+ti,m

(5)

1.4 問題形式化描述

由于不同任務(wù)所需的資源不同，為了滿足所有移動終端的任務(wù)時延要求，在計算與通信資源約束條件下對終端的計算卸載決策A，上行頻譜資源K，下行頻譜資源P以及服務(wù)器計算資源F4個方面聯(lián)合優(yōu)化，其中優(yōu)化目標可以表示為

(6)

C4:fi,l≥0 ?i∈L

C5:ai∈{0,1} ?i∈L

其中F={fi,m:∑ifi,m≤fm,?i∈L}，a=(a1,a2,…,an)，K={ki:∑iki≤1,?i∈L}，P={ξi:∑iξi≤1,?i∈L}。其中限制條件C1表示分配給所有移動終端計算資源總和小于等于服務(wù)器的計算能力，限制條件C2、C3表示分配給所有移動終端的上行與下行頻譜資源的百分比，限制條件C4則表示終端的本地計算資源是非負的，C5表示為移動終端的卸載決策。此外由式(6)可以看出，由于ai為整型變量，因此問題式(6)為混合整型線性規(guī)劃問題且為非凸的，因此很難得到直解。為了解決以上問題，本文提出了一種基于博弈論的計算卸載與資源分配算法。

2 基于博弈論的計算卸載與資源分配算法

博弈論是指博弈或者對弈過程中，通過考慮或預(yù)測參與人的實際行為從而優(yōu)化參與者的決策。為了獲取最優(yōu)卸載策略，接下來將把上述問題建模為博弈模型。

2.1 博弈形式化表述

首先將問題式(6)通過博弈模型G={L,(Ai)i∈L,Wi}來表示，其中L為終端個數(shù)，Ai為終端的卸載策略，wi為終端i的時延效用函數(shù)。a-i=(a1,a2,…,ai-1,ai+1,…,aN)表示除了終端i以外其他終端的卸載決策。由于每個移動終端用戶具有自私性，因此為了最小化所有終端的任務(wù)時延，所有參與者會對有限的計算資源、頻譜資源進行競爭。因此在競爭條件下，每個移動終端的時延表示為

(7)

由于該模型具有納什均衡的特性，即存在最優(yōu)的卸載策略使得每個終端時延最低。因此在所有移動終端完成決策后，需要對卸載至服務(wù)器的移動設(shè)備進行通信與計算資源優(yōu)化，而資源的優(yōu)化目標可以表示為

(8)

根據(jù)海塞矩陣很容易證明函數(shù)W(k,ξ,f)為凸函數(shù)，此外由于限制條件C1～C3是線性的，因此問題式(8)變?yōu)橥箖?yōu)化問題[20]。為了解決該問題，采用對偶的方法，相應(yīng)的對偶函數(shù)表示為

(9)

可以看出式(9)分為2個部分。第1部分為內(nèi)層函數(shù)，主要由變量k、f、ξ組成。第2部分為外層函數(shù)，其中變量μ、λ、θ為拉格朗日乘子且為非負值。由于內(nèi)層函數(shù)是凸的，因此將通過卡羅需-庫恩-塔克(Karush-Kuhn-Tucker，KKT)條件獲取最優(yōu)解。為了表示更加直觀，將上、下行傳輸速率表示為

(10)

(11)

(12)

為了優(yōu)化外層函數(shù)，在已知內(nèi)層函數(shù)最優(yōu)解的基礎(chǔ)上通過梯度法對拉格朗日乘子進行優(yōu)化，其中拉格朗日乘子表示如下：

(13)

(14)

(15)

其中，?1、 ?2、 ?3為迭代步長，t為迭代次數(shù)且t≥0。

2.2 納什均衡的存在性

為了證明博弈模型G存在一個純策略納什均衡，本文引入勢博弈的概念。

(16)

定義2如果存在一個勢函數(shù)φ(a)對于任何一個終端設(shè)備i在i∈Lai,ai′∈Ai條件下使得下式成立：

Wi(ai,a-i)-Wi(ai′,a-i)

=φ(ai,a-i)-φ(ai′,a-i) (17)

則該博弈為完全勢博弈。由于普通勢博弈包含完全勢博弈，因此完全勢博弈具有普通勢博弈的所有屬性。

定理1如果一個普通勢博弈具有有限的策略集合，那么它存在一個純策略的納什均衡。

定理2如果一個博弈模型是完全勢博弈且存在勢函數(shù)，那么存在一個純策略的納什均衡且具有有限遞增屬性。

證明首先設(shè)置勢函數(shù)為

(18)

隨后設(shè)置2個不同策略a=(ai,a-i)，a′=(ai′,a-i)并將2個不同的策略帶入函數(shù)φ(a)與wi(ai,a-i)中得到：

+(1-aj)Uj,l

(19)

+(1-aj)Uj,l

(20)

Wi(a)=aiUi,m+(1-ai)Ui,l

(21)

(22)

基于式(19)～(22)可以得到：

φ(a)-φ(a′)=Wi(a)-Wi(a′)

(23)

因此上述博弈模型為完全勢博弈且存在純策略納什均衡。

2.3 算法描述

由于邊緣服務(wù)器擁有所有接入終端的完整信息，因此服務(wù)器可以根據(jù)接入信息獲取優(yōu)化后的卸載策略并將該策略發(fā)送至移動終端。根據(jù)納什均衡性，所有移動終端將會服從該卸載決策。詳細的算法描述如算法1所示。

算法1 基于博弈論的計算卸載與資源分配算法步驟 1 初始化:對終端卸載策略a,終端發(fā)射功率pi,B, pB,任務(wù)的輸入數(shù)據(jù)大小si、輸出數(shù)據(jù)大小mi以及任務(wù)所需的計算資源ci進行初始化;步驟2 在已知卸載策略基礎(chǔ)上,獲取任務(wù)卸載至本地終端時所需的執(zhí)行時延Ui,l;步驟3 對于卸載至云端的任務(wù)通過式(10)～(12)獲取上、下行資源以及計算資源的最優(yōu)解k?i、ξ?i、 f?i;步驟4 在步驟3的最優(yōu)解基礎(chǔ)上,通過式(13)～(15)對拉格朗日乘子進行更新;步驟5 基于步驟3和4,將卸載至服務(wù)端的任務(wù)時延Ui,m并與卸載至本地的任務(wù)時延Ui,l進行比較。如果Ui,m>Ui,l,則終端卸載至本地即ai=0否則ai=1。通過循環(huán)獲取新的計算卸載策略a;步驟6 在已知策略a的基礎(chǔ)上,設(shè)定其他終端卸載策略不變,單一改變終端i的卸載策略即ai=1,然后通過步驟3、4獲取終端的任務(wù)時延。此時,如果Ui,l>Ui,m,ai=1同時對策略a進行更新。然后i+1且ai=1,重復(fù)步驟6直到終端i等于N時循環(huán)結(jié)束。此時得到最優(yōu)的卸載策略a以及資源分配k?i、 ξ?i、 f?i。

3 仿真結(jié)果與分析

為了驗證本文所提基于博弈論的計算卸載與資源分配算法(CORAG)性能，在信道條件不變的基礎(chǔ)上，分別與文獻[21]所提的本地卸載算法(LOC)、隨機卸載算法(random offloading completely, ROC)以及文獻[19]提出的計算卸載與上行頻譜資源分配(computation offloading and uplink resource game，COURG)進行比較分析。

3.1 參數(shù)設(shè)置

表1 仿真參數(shù)設(shè)置

3.2 仿真分析

首先考慮移動終端個數(shù)變化對系統(tǒng)總時延的影響。當(dāng)終端的發(fā)射功率為23 dBm，邊緣服務(wù)器的計算能力為30 000 Megacycles/s，上下行鏈路帶寬相同且為20 MHz時，仿真結(jié)果如圖2所示。圖2表明，本文提出的CORAG算法的性能優(yōu)于LOC、ROC以及COURG算法，隨著移動終端數(shù)量增加CORAG算法優(yōu)勢更加明顯。這是因為在計算與通信資源有限的條件下，CORAG算法可以更好地為不同的移動終端分配最優(yōu)的計算與通信資源，因此所有移動終端的總時延最低。另外從圖2可以看出，當(dāng)所有移動設(shè)備的計算任務(wù)在本地執(zhí)行時，由于計算任務(wù)時延的大小只與自身計算能力有關(guān)，因此隨著終端數(shù)的增加，LOC算法的總時延是線性遞增的；當(dāng)采用隨機卸載策略時，由于一部分移動終端會將任務(wù)卸載至邊緣服務(wù)器而另一部分移動終端在本地執(zhí)行計算任務(wù)，因此所有移動終端總時延低于LOC算法且呈波動變化。此外，由于COURG算法忽略了下行資源的優(yōu)化，因此其總時延略高于CORAG算法。

圖2 不同算法在不同移動終端數(shù)量下的總時延比較

當(dāng)移動終端數(shù)量為10、邊緣服務(wù)器計算能力為30 000 Megacycles/s且上、下行帶寬為20 MHz時，比較在不同輸入數(shù)據(jù)大小下不同算法的性能，仿真結(jié)果如圖3所示。由圖3可以看出，隨著上行輸入數(shù)據(jù)的增大，CORAG算法總時延低于LOC、ROC以及COURG算法。這是因為CORAG算法可以根據(jù)獲得輸入數(shù)據(jù)的大小分配最優(yōu)的上、下行帶寬資源以及計算資源，進而使得所有終端設(shè)備的總時延最低。另外從圖3明顯看出，當(dāng)計算任務(wù)在本地執(zhí)行時，總時延僅與任務(wù)所需計算資源有關(guān)，因此LOC算法沒有明顯變化。

圖3 不同算法在不同輸入數(shù)據(jù)大小下的總時延比較

圖4表示不同算法在不同計算結(jié)果數(shù)據(jù)大小下的性能仿真分析。仿真結(jié)果表明，隨著計算結(jié)果數(shù)據(jù)的增大，CORAG算法的總時延低于LOC、ROC以及COURG算法。由圖4可以看出，當(dāng)計算結(jié)果大小不變時，所提算法性能明顯優(yōu)于其他3種算法且隨著計算結(jié)果數(shù)據(jù)的逐漸增大，CORAG算法性能優(yōu)勢明顯。此外，由于COURG算法忽略了下行帶寬的優(yōu)化，因此隨著計算結(jié)果數(shù)據(jù)的增大，所有移動終端的總時延波動較大。而LOC算法的計算任務(wù)時延與計算結(jié)果大小無關(guān)，因此所有設(shè)備的總時延基本不變。最后，由于ROC算法中任務(wù)總是隨機進行卸載，因此曲線是波動變化的。

圖4 不同算法在不同計算結(jié)果數(shù)據(jù)大小下的總時延比較

為了進一步比較本文所提CORAG算法與LOC、ROC以及COURG 3種算法的性能，當(dāng)移動終端數(shù)量為10、移動終端的計算能力為1 000 Megacycles/s且邊緣服務(wù)器計算能力為35 000 Megacycles/s時，對不同算法在任務(wù)所需的CPU循環(huán)變化下進行仿真分析，仿真結(jié)果如圖5所示。仿真結(jié)果表明，隨著任務(wù)所需CPU循環(huán)的增加，消耗的資源逐漸遞增。因此在資源有限條件下，4種算法的總時延逐漸上升。此外，由于CORAG與COURG算法對計算與通信資源進行了優(yōu)化，因此算法性能優(yōu)于LOC與ROC且上升趨勢較為緩慢。另外從圖5可以看出，隨著任務(wù)所需CPU循環(huán)逐步增加，COURG算法曲線略微波動且在性能上與CORAG算法相近。這是因為隨著任務(wù)所需CPU循環(huán)數(shù)的增加COURG算法總能為移動終端分配最優(yōu)的計算資源，但由于該算法忽略了下行頻譜資源的優(yōu)化，因此COURG曲線會略微波動。

圖5 不同算法在不同任務(wù)所需的CPU循環(huán)變化下總時延比較

最后，在不同邊緣服務(wù)器的計算能力條件下對CORAG算法進行仿真，其仿真結(jié)果如圖6所示。仿真結(jié)果表明，當(dāng)移動終端數(shù)低于4時，邊緣服務(wù)器計算能力大小對所有移動終端的總時延影響較?。划?dāng)移動終端數(shù)從6逐步遞增至20時，邊緣服務(wù)器計算能力大小對所有移動終端的總時延影響較大。另外，通過對比計算能力為30 000 Megacycles/s與50 000 Megacycles/s曲線可知，當(dāng)移動終端個數(shù)由14增長至20時，2條曲線總時延的差值也在逐步增大。

圖6 隨著移動終端數(shù)個數(shù)增加，不同邊緣服務(wù)器計算能力條件下的CORAG算法性能比較

因此從以上結(jié)果可以得出，邊緣服務(wù)器的計算能力越高，移動終端的時延越低。這是因為當(dāng)終端個數(shù)較少時，現(xiàn)有的計算資源可以滿足終端用戶的需求；然而隨著終端數(shù)量的增加其需要的計算資源將越來越多，此時服務(wù)器的計算資源越豐富，移動終端的總時延越低，算法的性能越優(yōu)越。

4 結(jié) 論

本文針對計算能力不足的移動終端處理低時延、高可靠應(yīng)用而產(chǎn)生高時延的問題，提出了一種基于博弈論的計算卸載與資源分配聯(lián)合優(yōu)化算法。該算法在設(shè)計過程中首先將計算卸載與資源分配問題表示為非合作博弈模型并通過引入勢博弈概念證明該博弈模型存在納什均衡狀態(tài)；其次在已知移動終端卸載的決策條件下，利用拉格朗日乘子法獲取計算資源以及上下行頻譜資源的最優(yōu)解；最后在最優(yōu)解的基礎(chǔ)上，采用迭代法獲得移動終端的納什均衡解。仿真結(jié)果表明，與LOC算法、ROC算法以及COURG算法相比，本文提出的CORAG算法可以降低所有移動終端的任務(wù)時延，提升終端用戶的服務(wù)體驗。本文主要研究是在單基站覆蓋下多個移動終端在非合作場景中的時延優(yōu)化問題。然而在實際應(yīng)用場景中，移動終端是頻繁移動的，而這將增加不同終端間的連接幾率并使移動終端間的資源復(fù)用成為可能；此外由于網(wǎng)絡(luò)具有不同的負載特性，如何根據(jù)不同網(wǎng)絡(luò)特點進行有效的資源分配也是未來研究方向[22，23]。因此在終端頻繁移動的條件下根據(jù)不同的網(wǎng)絡(luò)特點，提出有效的資源分配算法降低終端任務(wù)時延是下一步的研究重點。