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

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

0 引 言

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

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

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

1 模型建立

1.1 系統(tǒng)模型

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

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

1.2 計算模型

(1)本地計算模型

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

(1)

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

任務(wù)i在本地的計算能耗可計算為

(2)

(2)傳輸計算模型

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

(3)

(4)

(5)

(3)邊緣云計算模型

(6)

(7)

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

1.3 遷移模型

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

(8)

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

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

2.1 卸載模型

本文將卸載過程建立為馬爾科夫決策過程(Markov Decision Process,MDP)。MDP是時序決策的標(biāo)準(zhǔn)方法，可以在計算資源充足的條件下給出最優(yōu)解。MDP考慮了動作及系統(tǒng)的下個狀態(tài)不僅和當(dāng)前的狀態(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ù)，即任務(wù)執(zhí)行完動作后會得到某個狀態(tài)下的獎勵，一般作為決策的依據(jù)。通?；貓蠛瘮?shù)和目標(biāo)函數(shù)相關(guān)。由于MDP追求最大化回報，本文的優(yōu)化目標(biāo)是最小化損耗函數(shù)之和，因此回報函數(shù)與之存在負(fù)相關(guān)關(guān)系。

2.2 優(yōu)化問題

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

(10)

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

(11)

(12)

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

(13)

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

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

(14)

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

(15)

(16)

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

(17)

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

(18)

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

(19)

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

(20)

時延為

(21)

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

(22)

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

(23)

(24)

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

(25)

即前一個任務(wù)和當(dāng)前任務(wù)均在邊緣云系統(tǒng)中執(zhí)行，但要考慮的是當(dāng)前任務(wù)是在邊緣云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)

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

(35a)

s.t.

(35b)

(35c)

(35d)

(35e)

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

3 問題求解

3.1 資源分配問題

(36a)

s.t.

(36b)

對公式進(jìn)行化簡，即

(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為一個訓(xùn)練周期，采用時序差分法更新Q值表，公式為

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

(40)

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

(41)

(42)

QLBA算法如下：

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

對于每一個episode：

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

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

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

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

(5)直到達(dá)到最終目標(biāo)狀態(tài)停止。

3.3 算法復(fù)雜度

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

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

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

表1 仿真參數(shù)

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

圖3 Q-learning學(xué)習(xí)收斂曲線

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

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

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

圖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í)行的任務(wù)來說，由于邊緣云計算資源有限，發(fā)生遷移的概率較大，導(dǎo)致能耗比其他方案高。

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

5 結(jié)束語

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