賈淑霞，郝萬明,高梓涵，楊守義

(鄭州大學 信息工程學院，鄭州 450001)

0 引 言

隨著5G網(wǎng)絡(luò)的普及，計算密集型的移動應用將不斷增加，但移動設(shè)備可能不足以支撐這些應用的計算需求，移動云計算(Mobile Cloud Computing,MCC)應運而生。雖然MCC具有高存儲能力和強大計算能力等優(yōu)點，但是它增加了前向鏈路傳輸延時，對延時敏感應用(如人臉識別、自動駕駛交互式情景在線游戲等)并不適用。為降低傳輸延時，有學者提出移動邊緣計算(Mobile Edge Computing,MEC)[1-2]，將計算密集型任務卸載至距離終端較近的移動網(wǎng)絡(luò)邊緣進行處理，可同時滿足用戶快速交互響應和靈活計算服務的需求，緩解了核心網(wǎng)絡(luò)的壓力。

MEC系統(tǒng)主要涉及計算任務卸載策略的研究，其性能的好壞一般是以時延或能耗為衡量指標，目前卸載策略依照需求可分為最小化時延、最小化能耗以及均衡能耗和時延，但這些策略未考慮計算任務的執(zhí)行機制，將計算任務看作一個整體，即為粗粒度卸載。而在實際生活中，任務之間是存在依賴性的，例如通過智能手環(huán)分析人的睡眠狀態(tài)，首先傳感器根據(jù)手腕的動作幅度和頻率采集運動數(shù)據(jù)，然后系統(tǒng)根據(jù)傳感器反饋的數(shù)據(jù)進行計算來衡量睡眠的質(zhì)量，即任務間存在依賴關(guān)系，為細粒度卸載。此外，任務卸載并非靜態(tài)過程。文獻[3]中提出了一種新的移動感知編碼概率緩存方案使得吞吐量最大，文獻[4-5]只考慮了移動用戶的移動性，并未涉及用戶能耗與時延需求且未考慮任務之間的依賴性。

為了更好地符合實際通信場景，本文考慮了任務之間的依賴性，并針對在任務卸載時由于設(shè)備的移動而導致任務遷移這一問題建立了任務遷移模型，提出通過優(yōu)化資源分配和任務卸載策略來解決基于聯(lián)合時延和能耗的損耗函數(shù)最小的優(yōu)化問題。仿真結(jié)果表明本文提出的算法能夠以更小的損耗提升系統(tǒng)性能。

1 模型建立

1.1 系統(tǒng)模型

本文假設(shè)一個移動用戶可以被相鄰兩個邊緣云服務，且邊緣云之間通過宏基站(Macro Base Station,MBS)互聯(lián)，從而實現(xiàn)任務的相互遷移。遷移是指任務在未完成卸載時離開當前邊緣云而導致數(shù)據(jù)在邊緣云之間的遷移，即卸載至邊緣云1的任務在未完成計算之前，設(shè)備已移出邊緣云1的服務范圍內(nèi)轉(zhuǎn)而進入邊緣云2服務范圍，從而邊緣云1的任務計算結(jié)果會通過MBS遷移到邊緣云2，然后返回至終端。系統(tǒng)模型如圖1所示，由兩個邊緣云服務器和若干應用組成。假設(shè)移動應用包括一組子任務，每個子任務按順序依次進行，即下一個子任務需在上一個子任務完成后才能進行。在該系統(tǒng)中，每個應用被劃分成任務序列N，用集合N={1,2,3,…,N}表示。其中任務間的依賴性不可忽略，本文子任務的依賴模型為順序進行，因此采用有向無環(huán)圖進行描述，用G(N,E)表示。用E表示調(diào)用依賴關(guān)系，E={e|e=e(i,j),i,j∈N}，其中i∈N代表每個任務，e(i,j)表示任務的先后順序，即任務j要等到i完成后才能執(zhí)行。

圖1 基于遷移的系統(tǒng)模型

1.2 計算模型

(1)本地計算模型

假設(shè)移動設(shè)備的計算能力為Fl，則任務i在本地的計算時間可表示為

(1)

參考文獻[6]，計算消耗是計算能力的超線性函數(shù)，表示為：pl=κl(Fl)γ，其中γ=2，κl表示CPU的有效電容系數(shù)[6]，設(shè)置為10-15。

任務i在本地的計算能耗可計算為

(2)

(2)傳輸計算模型

移動設(shè)備通過無線信道將計算任務卸載到邊緣節(jié)點，總消耗時間包括傳輸時間以及云上執(zhí)行時間兩部分[6]，其傳輸速率可表示為

(3)

(4)

(5)

(3)邊緣云計算模型

(6)

(7)

式中：κe表示CPU的有效電容系數(shù),設(shè)置為10-16來滿足邊緣云計算的能耗需求。

1.3 遷移模型

由于移動設(shè)備不是靜止不動的，本文定義任務停留時間t為任務在邊緣云服務范圍內(nèi)所待時間，若任務在邊緣云上執(zhí)行時間大于任務停留時間，則任務需要在兩個邊緣云內(nèi)進行遷移，否則無需遷移。采用停留時間的概率密度函數(shù)來體現(xiàn)移動設(shè)備的移動性[3-5]，表示為

(8)

式中：wi表示任務i的平均停留時間[3]。

2 卸載模型以及優(yōu)化問題

2.1 卸載模型

本文將卸載過程建立為馬爾科夫決策過程(Markov Decision Process,MDP)。MDP是時序決策的標準方法，可以在計算資源充足的條件下給出最優(yōu)解。MDP考慮了動作及系統(tǒng)的下個狀態(tài)不僅和當前的狀態(tài)有關(guān)還和采取的動作有關(guān)，其中比較重要的三個元素為狀態(tài)S、動作A以及回報R。

(1)狀態(tài)S

S={S0,S1,S2,…,SN-1,ST} 。

(9)

(2)動作A

圖2 狀態(tài)轉(zhuǎn)變圖

(3)回報R

回報也被稱為獎勵函數(shù)，即任務執(zhí)行完動作后會得到某個狀態(tài)下的獎勵，一般作為決策的依據(jù)。通?；貓蠛瘮?shù)和目標函數(shù)相關(guān)。由于MDP追求最大化回報，本文的優(yōu)化目標是最小化損耗函數(shù)之和，因此回報函數(shù)與之存在負相關(guān)關(guān)系。

2.2 優(yōu)化問題

本文定義損耗函數(shù)(Loss Function,LF)來衡量服務用戶質(zhì)量，將卸載問題轉(zhuǎn)化為在一定約束條件下?lián)p耗函數(shù)之和最小化的問題。其中損耗函數(shù)定義為特定狀態(tài)下時間和能耗與全部在本地執(zhí)行比值的加權(quán)和。損耗函數(shù)表示為

(10)

即前一個任務和當前任務均在本地執(zhí)行，僅需考慮任務i在本地執(zhí)行的能耗以及時延，表示為

(11)

(12)

因此該狀態(tài)下?lián)p耗函數(shù)表示為

(13)

即前一個任務在本地執(zhí)行，當前任務在邊緣云執(zhí)行，需要考慮傳輸數(shù)據(jù)以及移動設(shè)備的移動性。根據(jù)任務停留時間t和該狀態(tài)下任務在邊緣云系統(tǒng)中完成計算的時間T1的長度關(guān)系分情況討論：

①t>T1，即任務可以順利地在邊緣云1上完成卸載不會發(fā)生遷移，這種情況的概率記為Pwi(t>T1)。

(14)

用FTi-1表示前一個任務的完成時間，根據(jù)圖2可以看出完成時間依賴于狀態(tài)00或者10，引入p00、p10來表示來自這兩狀態(tài)的概率。即

(15)

(16)

②t≤T1，即任務不能順利在邊緣云1完成，需要遷移至邊緣云2完成，這種情況的概率記為Pwi(t≤T1)。由于發(fā)生遷移額外產(chǎn)生了遷移成本，用Em=ηHi表示，其中η表示單位遷移價格，此時能耗為

(17)

根據(jù)移動模型(8)，可以計算得到相應的概率為

(18)

P2=Pwi(t>T1)=1-Pwi(t≤T1)。

(19)

因此該狀態(tài)下能耗公式可整合為

(20)

時延為

(21)

此狀態(tài)下?lián)p耗函數(shù)表示為

(22)

即前一個任務在邊緣云系統(tǒng)中執(zhí)行，當前任務在本地執(zhí)行，則此狀態(tài)的能耗和時延表達式為

(23)

(24)

因此該狀態(tài)下的損耗函數(shù)為

(25)

即前一個任務和當前任務均在邊緣云系統(tǒng)中執(zhí)行，但要考慮的是當前任務是在邊緣云1還是邊緣云2執(zhí)行，因此仍要分情況考慮：

(26)

引入p01、p11來表示來自這兩狀態(tài)的概率：

(27)

(28)

②t≤T2，該情況的概率記為Pwi(t≤T2)，類比于狀態(tài)01，此時能耗為

(29)

(30)

P4=Pwi(t>T2)=1-Pwi(t≤T2)。

(31)

該狀態(tài)下的能耗和時延表示為

(32)

(33)

因此該狀態(tài)下的損耗函數(shù)表示為

(34)

本文需要按順序依次對所有任務進行狀態(tài)決策，目標是通過優(yōu)化傳輸功率以及進行卸載決策使得損耗函數(shù)之和最小，將優(yōu)化問題可描述為

(35a)

s.t.

(35b)

(35c)

(35d)

(35e)

式中：C1約束是對傳輸功率的限制；C2約束是保證邊緣云的頻率不超過服務器的最大頻率；C3約束表示的是每一狀態(tài)的計算時間要小于任務完成的最大時延；C4約束表示的是每個任務選擇的子狀態(tài)空間的任何狀態(tài)要在整個系統(tǒng)狀態(tài)范圍內(nèi)，即任務可選擇在本地執(zhí)行或者在邊緣云系統(tǒng)中執(zhí)行。

3 問題求解

3.1 資源分配問題

(36a)

s.t.

(36b)

對公式進行化簡，即

(37)

ifz(pmax)≤0 then

else

repeat

else

end if

end if

(38)

(39)

3.2 基于Q-learning的卸載算法

本文提出QLBA(Q-learning Based Algorithm)來實現(xiàn)卸載決策。Q-learning算法思想：通過狀態(tài)和動作構(gòu)建一個Q值表，根據(jù)Q值來選取獲得最大回報的動作[7-8]。該算法核心是以一個episode為一個訓練周期，采用時序差分法更新Q值表，公式為

Q(s,a)=(1-α)Q(s,a)+α[R+γmaxQ(s′,a′)]。

(40)

式中：γ越趨近于0表示更注重眼前的獎勵；γ越趨近于1表示更注重未來的獎勵；α表示學習率為Q值和當前Q值的比率，若α越趨近于1表示保留之前的值越少。Q-learning的優(yōu)勢就是融合了蒙特卡洛以及動態(tài)規(guī)劃進行離線學習，通過求解貝爾曼方程得出最優(yōu)路徑。本文的優(yōu)化目標是最小化損耗函數(shù)之和，因此回報函數(shù)與之存在負相關(guān)關(guān)系，即問題(35)轉(zhuǎn)換為

(41)

(42)

QLBA算法如下：

設(shè)置初值以及矩陣R，初始化矩陣Q全為0。

對于每一個episode：

(1)隨機選擇一個初始狀態(tài)；

(2)在當前狀態(tài)的所有可能行為中選取一個動作；

(3)利用選定的動作a得到下一個狀態(tài)；

(4)根據(jù)式(40)計算Q值；

(5)直到達到最終目標狀態(tài)停止。

3.3 算法復雜度

由文獻[6]可知，資源分配階段采用的二分法的復雜度為O(lb(p/ε))，卸載決策階段采用的Q-learning算法的復雜度為O(N2)，因此算法總體復雜度為O(lb(p/ε))+O(N2)。

4 仿真結(jié)果及數(shù)據(jù)分析

此部分對所提算法進行評價，采用Matlab進行仿真，與其他三種不同的方案進行比較，即完全卸載方案(All-edge scheme)、本地計算方案(All-local scheme)和文獻[9]中隨機卸載方案(Random scheme)。本文假設(shè)邊緣云的覆蓋半徑為500 m，移動設(shè)備和邊緣云之間的無線信道增益遵從瑞利隨機衰落。其他仿真參數(shù)參考文獻[6]和[10]設(shè)置，如表1所示。

表1 仿真參數(shù)

首先將任務數(shù)設(shè)置為25，βE、βT分別設(shè)置為0.6、0.4。圖3給出了Q-learning的學習收斂曲線，可以看出經(jīng)過1 000次迭代，損耗函數(shù)趨于一個穩(wěn)定的值，證明了本文提出的QLBA算法是收斂的。

圖3 Q-learning學習收斂曲線

不同任務數(shù)下(任務數(shù)25～55)四種方案的損耗函數(shù)對比如圖4所示。假設(shè)每個任務的數(shù)據(jù)量和計算能力不同，仿真時在給定范圍隨機取值，服從均勻分布；βE、βT分別設(shè)置為0.6、0.4。本文以All-local scheme作為對比基準，該方案始終為1，其他三種方案由于受無線信道狀態(tài)以及計算資源的限制都有所波動，可看出在不同任務數(shù)下本文所提出的QLBA優(yōu)于其他三種方案，可以從總體上最小化損耗函數(shù)。

圖4 不同應用的任務數(shù)的損耗函數(shù)

然后討論權(quán)重βE、βT對損耗函數(shù)的影響。本文方案與其他三種方案的βE與損耗函數(shù)的關(guān)系如圖5所示，此時任務數(shù)設(shè)置為25，仍以All-local scheme作為基準?？煽闯霎敠翬小于0.48時，全部在邊緣云系統(tǒng)執(zhí)行和所提方案幾乎無差別，但都優(yōu)于文獻[9]中的隨機方案；當βE大于0.48后，任務全部卸載方案的損耗函數(shù)增加得較快，可見完全卸載比較適用于對延遲比較敏感的應用。而本文提出的方案增長比較平穩(wěn)，在這幾種方案中最優(yōu)，證明了QLBA的優(yōu)越性。隨著βE的增加，可看出QLBA逼近全本地方案，可得出對延遲不敏感的應用更傾向在本地執(zhí)行任務。

圖5 βE與損耗函數(shù)的關(guān)系

圖6和圖7分別給出了隨著βE的增加四個方案的能耗以及時延的變化趨勢。

圖6 βE與能耗關(guān)系圖

圖7 βE與時延關(guān)系圖

從圖6可看出All-local scheme的能耗最小，All-edge scheme的能耗最大。原因有以下幾點：一是All-local scheme相對于其他三種方案節(jié)省了傳輸能耗；二是本地的計算能力相對于在邊緣云的計算能力要?。蝗菍τ谌吭谶吘壴粕蠄?zhí)行的任務來說，由于邊緣云計算資源有限，發(fā)生遷移的概率較大，導致能耗比其他方案高。

從圖7可看出任務全部在本地執(zhí)行的時延最高，全部卸載方案的時延最低。隨著βE的增加，QLBA的時延逐漸增加，逐漸和All-local scheme逼近。由此可得出結(jié)論：對時延比較敏感的應用分配較小的βE，對能耗比較敏感的應用分配較大的βE。綜上可得出，本文所提出的方案可以從總體上使系統(tǒng)損耗最小。

5 結(jié)束語

由于數(shù)據(jù)傳輸過程中的任務遷移導致額外的遷移成本，為降低遷移概率以及最小化損耗函數(shù)之和，本文提出了基于遷移的移動邊緣云系統(tǒng)的資源分配以及任務卸載。首先將應用卸載過程建模為MDP，考慮時延和能耗對決策的影響，定義損耗函數(shù)來衡量用戶質(zhì)量，將問題轉(zhuǎn)化為最小化損耗函數(shù)之和。先采用二分法在任務卸載前對每個任務的傳輸功率進行優(yōu)化，再采用QLBA對任務進行決策。仿真結(jié)果表明本文提出的方案優(yōu)于其他三種方案。未來工作中將進一步考慮多用戶的數(shù)據(jù)遷移問題。