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

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

0 引 言

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

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

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

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

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

1.1 系統(tǒng)模型

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

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

圖1 MEC系統(tǒng)網絡架構

1.2 通信模型

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

(1)

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

(2)

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

1.3 計算模型

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

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

(3)

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

Ui,l=ti,l

(4)

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

(5)

1.4 問題形式化描述

由于不同任務所需的資源不同，為了滿足所有移動終端的任務時延要求，在計算與通信資源約束條件下對終端的計算卸載決策A，上行頻譜資源K，下行頻譜資源P以及服務器計算資源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表示分配給所有移動終端計算資源總和小于等于服務器的計算能力，限制條件C2、C3表示分配給所有移動終端的上行與下行頻譜資源的百分比，限制條件C4則表示終端的本地計算資源是非負的，C5表示為移動終端的卸載決策。此外由式(6)可以看出，由于ai為整型變量，因此問題式(6)為混合整型線性規(guī)劃問題且為非凸的，因此很難得到直解。為了解決以上問題，本文提出了一種基于博弈論的計算卸載與資源分配算法。

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

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

2.1 博弈形式化表述

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

(7)

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

(8)

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

(9)

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

(10)

(11)

(12)

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

(13)

(14)

(15)

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

2.2 納什均衡的存在性

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

(16)

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

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

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

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

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

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

證明首先設置勢函數為

(18)

隨后設置2個不同策略a=(ai,a-i)，a′=(ai′,a-i)并將2個不同的策略帶入函數φ(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 算法描述

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

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

3 仿真結果與分析

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

3.1 參數設置

表1 仿真參數設置

3.2 仿真分析

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

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

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

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

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

圖4 不同算法在不同計算結果數據大小下的總時延比較

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

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

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

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

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

4 結 論

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