任務(wù)遷移的移動(dòng)邊緣計(jì)算系統(tǒng)中資源分配和任務(wù)卸載策略*

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

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

0 引 言

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

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

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

1 模型建立

1.1 系統(tǒng)模型

本文假設(shè)一個(gè)移動(dòng)用戶可以被相鄰兩個(gè)邊緣云服務(wù)，且邊緣云之間通過宏基站(Macro Base Station,MBS)互聯(lián)，從而實(shí)現(xiàn)任務(wù)的相互遷移。遷移是指任務(wù)在未完成卸載時(shí)離開當(dāng)前邊緣云而導(dǎo)致數(shù)據(jù)在邊緣云之間的遷移，即卸載至邊緣云1的任務(wù)在未完成計(jì)算之前，設(shè)備已移出邊緣云1的服務(wù)范圍內(nèi)轉(zhuǎn)而進(jìn)入邊緣云2服務(wù)范圍，從而邊緣云1的任務(wù)計(jì)算結(jié)果會(huì)通過MBS遷移到邊緣云2，然后返回至終端。系統(tǒng)模型如圖1所示，由兩個(gè)邊緣云服務(wù)器和若干應(yīng)用組成。假設(shè)移動(dòng)應(yīng)用包括一組子任務(wù)，每個(gè)子任務(wù)按順序依次進(jìn)行，即下一個(gè)子任務(wù)需在上一個(gè)子任務(wù)完成后才能進(jìn)行。在該系統(tǒng)中，每個(gè)應(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代表每個(gè)任務(wù)，e(i,j)表示任務(wù)的先后順序，即任務(wù)j要等到i完成后才能執(zhí)行。

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

1.2 計(jì)算模型

(1)本地計(jì)算模型

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

(1)

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

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

(2)

(2)傳輸計(jì)算模型

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

(3)

(4)

(5)

(3)邊緣云計(jì)算模型

(6)

(7)

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

1.3 遷移模型

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

(8)

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

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

2.1 卸載模型

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

(1)狀態(tài)S

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

(9)

(2)動(dòng)作A

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

(3)回報(bào)R

回報(bào)也被稱為獎(jiǎng)勵(lì)函數(shù)，即任務(wù)執(zhí)行完動(dòng)作后會(huì)得到某個(gè)狀態(tài)下的獎(jiǎng)勵(lì)，一般作為決策的依據(jù)。通?；貓?bào)函數(shù)和目標(biāo)函數(shù)相關(guān)。由于MDP追求最大化回報(bào)，本文的優(yōu)化目標(biāo)是最小化損耗函數(shù)之和，因此回報(bào)函數(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)下時(shí)間和能耗與全部在本地執(zhí)行比值的加權(quán)和。損耗函數(shù)表示為

(10)

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

(11)

(12)

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

(13)

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

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

(14)

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

(15)

(16)

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

(17)

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

(18)

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

(19)

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

(20)

時(shí)延為

(21)

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

(22)

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

(23)

(24)

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

(25)

即前一個(gè)任務(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，此時(shí)能耗為

(29)

(30)

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

(31)

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

(32)

(33)

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

(34)

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

(35a)

s.t.

(35b)

(35c)

(35d)

(35e)

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

3 問題求解

3.1 資源分配問題

(36a)

s.t.

(36b)

對(duì)公式進(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)來實(shí)現(xiàn)卸載決策。Q-learning算法思想：通過狀態(tài)和動(dòng)作構(gòu)建一個(gè)Q值表，根據(jù)Q值來選取獲得最大回報(bào)的動(dòng)作[7-8]。該算法核心是以一個(gè)episode為一個(gè)訓(xùn)練周期，采用時(shí)序差分法更新Q值表，公式為

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

(40)

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

(41)

(42)

QLBA算法如下：

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

對(duì)于每一個(gè)episode：

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

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

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

(4)根據(jù)式(40)計(jì)算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ù)分析

此部分對(duì)所提算法進(jìn)行評(píng)價(jià)，采用Matlab進(jìn)行仿真，與其他三種不同的方案進(jìn)行比較，即完全卸載方案(All-edge scheme)、本地計(jì)算方案(All-local scheme)和文獻(xiàn)[9]中隨機(jī)卸載方案(Random scheme)。本文假設(shè)邊緣云的覆蓋半徑為500 m，移動(dòng)設(shè)備和邊緣云之間的無線信道增益遵從瑞利隨機(jī)衰落。其他仿真參數(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ù)趨于一個(gè)穩(wěn)定的值，證明了本文提出的QLBA算法是收斂的。

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

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

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

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

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

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

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

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

從圖6可看出All-local scheme的能耗最小，All-edge scheme的能耗最大。原因有以下幾點(diǎn)：一是All-local scheme相對(duì)于其他三種方案節(jié)省了傳輸能耗；二是本地的計(jì)算能力相對(duì)于在邊緣云的計(jì)算能力要小；三是對(duì)于全部在邊緣云上執(zhí)行的任務(wù)來說，由于邊緣云計(jì)算資源有限，發(fā)生遷移的概率較大，導(dǎo)致能耗比其他方案高。

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

5 結(jié)束語

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