李 波，牛 力，彭紫藝，黃 鑫，丁洪偉

(云南大學(xué)信息學(xué)院， 云南 昆明 650500)

1 引言

隨著5G通信技術(shù)的不斷發(fā)展，人們對(duì)及時(shí)性、低延遲性服務(wù)的需求日益增強(qiáng)，然而考慮到移動(dòng)終端自身體積受限、計(jì)算能力不足等因素，以及將海量計(jì)算任務(wù)卸載至云服務(wù)器必將導(dǎo)致其負(fù)荷過載和云服務(wù)器與用戶物理距離遠(yuǎn)而導(dǎo)致其網(wǎng)絡(luò)延遲過大等不利因素對(duì)計(jì)算卸載的影響[1]，2014年歐洲電信標(biāo)準(zhǔn)化協(xié)會(huì)ETSI(European Telecommunications Standards Institute)提出了移動(dòng)邊緣計(jì)算MEC(Mobile Edge Computing)[2]的概念，即將云服務(wù)器的計(jì)算服務(wù)從核心網(wǎng)絡(luò)下沉至用戶附近的網(wǎng)絡(luò)邊緣，以滿足用戶對(duì)低延遲的需求，優(yōu)化用戶的服務(wù)體驗(yàn)。汽車作為5G時(shí)代主要的移動(dòng)終端，將移動(dòng)邊緣計(jì)算技術(shù)與車聯(lián)網(wǎng)技術(shù)相融合，為車載用戶的實(shí)時(shí)性需求以及未來(lái)的無(wú)人駕駛提供了理論依據(jù)。在車載邊緣計(jì)算VEC(Vehicular Edge Computing)[3]環(huán)境中，車載用戶可以通過車載單元與部署在道路兩側(cè)的路側(cè)單元實(shí)現(xiàn)信息交互，將任務(wù)從車載本地遷移至代理資源，從而滿足用戶對(duì)計(jì)算服務(wù)的需求。但是，由于路側(cè)單元RSU(Rode Side Unit)的服務(wù)范圍較小，車輛的高速移動(dòng)性會(huì)導(dǎo)致車輛終端到代理資源之間的通信鏈路發(fā)生改變，同時(shí)考慮代理資源的可用計(jì)算能力的動(dòng)態(tài)變化[4]對(duì)計(jì)算卸載的影響，如何持續(xù)為移動(dòng)用戶提供有效的計(jì)算服務(wù)是目前車載邊緣計(jì)算環(huán)境中亟需解決的問題之一。

針對(duì)卸載場(chǎng)景動(dòng)態(tài)化對(duì)計(jì)算卸載的影響，近年來(lái)國(guó)內(nèi)外學(xué)者提出了不同的解決方案。文獻(xiàn)[5]提出了一種基于最小完成時(shí)間的計(jì)算切換策略，通過對(duì)比分析在邊緣層引入計(jì)算切換對(duì)計(jì)算卸載的影響，證明了計(jì)算切換策略的有效性，但該策略屬于求當(dāng)前時(shí)刻最優(yōu)解，并不適用于解決動(dòng)態(tài)環(huán)境中的計(jì)算卸載問題。文獻(xiàn)[6]闡述了一種路徑可預(yù)測(cè)的場(chǎng)景，通過預(yù)測(cè)得到汽車運(yùn)動(dòng)軌跡，對(duì)需要卸載的計(jì)算任務(wù)進(jìn)行預(yù)測(cè)性上傳和下載，以降低車輛移動(dòng)性對(duì)計(jì)算卸載的影響。但是，該算法只實(shí)現(xiàn)了對(duì)任務(wù)上傳和下載階段的卸載性能優(yōu)化，并未對(duì)計(jì)算執(zhí)行過程進(jìn)行深入探討，且不適用于動(dòng)態(tài)環(huán)境中的計(jì)算卸載問題。

盡管當(dāng)前針對(duì)終端移動(dòng)性對(duì)計(jì)算卸載的影響做出了大量的工作，但均未能解決如何在任務(wù)執(zhí)行過程中有效降低卸載場(chǎng)景動(dòng)態(tài)化對(duì)計(jì)算卸載的影響。本文提出了基于馬爾科夫決策過程[7]的計(jì)算切換策略。首先，針對(duì)代理資源的可用計(jì)算能力動(dòng)態(tài)變化建立車載邊緣計(jì)算環(huán)境中的計(jì)算卸載場(chǎng)景，并將代理資源計(jì)算能力以及卸載場(chǎng)景的通信鏈路的動(dòng)態(tài)變化時(shí)隙作為計(jì)算切換時(shí)隙依據(jù)；之后，將任務(wù)完成時(shí)間最小化作為本文的優(yōu)化目標(biāo)并建立相應(yīng)的回報(bào)函數(shù)模型；最后，基于貝爾曼方程以及策略迭代的方法求出最優(yōu)的計(jì)算切換策略。

2 系統(tǒng)模型

車載邊緣計(jì)算VEC卸載場(chǎng)景模型通常分為3層，即核心云層、邊緣計(jì)算層和汽車終端層[8]，如圖1所示。

Figure 1 Offloading scenario of vehicular edge computing 圖1 車載邊緣計(jì)算卸載場(chǎng)景

本文將VEC環(huán)境中的計(jì)算卸載系統(tǒng)模型分成任務(wù)模型、通信模型、計(jì)算模型和切換模型。

2.1 任務(wù)模型

本文將源節(jié)點(diǎn)產(chǎn)生的計(jì)算任務(wù)表示為：

Task={Din,C,Dout,Td}

(1)

其中，Din表示計(jì)算任務(wù)的上傳數(shù)據(jù)量，Dout表示計(jì)算任務(wù)的結(jié)果數(shù)據(jù)量，C表示計(jì)算任務(wù)的計(jì)算量，Td表示任務(wù)的截止完成時(shí)間。

本文將任務(wù)的上傳數(shù)據(jù)量與結(jié)果數(shù)據(jù)量的比值定義為“輸入輸出比”[9]：

(2)

2.2 通信模型

在VEC環(huán)境中的計(jì)算卸載過程中，根據(jù)節(jié)點(diǎn)類型不同，節(jié)點(diǎn)之間的通信方式不同。在該場(chǎng)景中，源節(jié)點(diǎn)可將任務(wù)通過無(wú)線通信的方式傳遞給RSU和基站BS，RSU與邊緣服務(wù)器ES(Edge Server)通過有線連接的方式進(jìn)行通信，ES之間也通過有線傳輸?shù)姆绞綄?shí)現(xiàn)互聯(lián)互通。故根據(jù)通信模式的不同，各節(jié)點(diǎn)間單跳基礎(chǔ)帶寬可表示為：

BW={V2V,V2R,V2B,R2E,E2E}

(3)

(4)

其中,n表示所選通信鏈路上的鏈路類型數(shù)。

2.3 計(jì)算模型

當(dāng)汽車源節(jié)點(diǎn)產(chǎn)生計(jì)算任務(wù)時(shí)，計(jì)算卸載決策模塊根據(jù)任務(wù)屬性、資源狀態(tài)和網(wǎng)絡(luò)環(huán)境等多個(gè)因素進(jìn)行計(jì)算卸載判決[10]。

當(dāng)任務(wù)在車輛本地進(jìn)行計(jì)算時(shí)，任務(wù)的完成時(shí)間TL表示為：

(5)

其中,FL表示車輛本地的計(jì)算能力。

當(dāng)任務(wù)執(zhí)行卸載時(shí)，任務(wù)在ES上的完成時(shí)間表示為：

(6)

2.4 切換模型

本文采用基于Docker的計(jì)算遷移技術(shù)，文獻(xiàn)[11]具體分析了計(jì)算切換的過程，指出由于計(jì)算切換而增加的切換開銷Thandoff，包括切換前剩余計(jì)算量的打包時(shí)間Tpackage、邊緣服務(wù)器Ea到Eb的切換時(shí)延Ta→b和數(shù)據(jù)包在邊緣服務(wù)器Eb上的重啟時(shí)間Treboot。切換開銷Thandoff可表示為：

Thandoff=Tpackage+Ta→b+Treboot

(7)

(8)

(9)

3 基于馬爾科夫決策過程的計(jì)算切換策略

本文將基于馬爾科夫決策過程的計(jì)算切換策略定義為一個(gè)離散時(shí)間無(wú)限的折扣馬爾科夫決策過程M={S,A,P,R,γ}，其中S表示根據(jù)該場(chǎng)景中各個(gè)ES的計(jì)算能力、決策時(shí)隙內(nèi)的網(wǎng)絡(luò)帶寬和剩余計(jì)算量而建立的狀態(tài)空間模型，A為動(dòng)作空間矩陣，P表示在決策時(shí)隙內(nèi)的狀態(tài)轉(zhuǎn)移概率矩陣，R表示獎(jiǎng)勵(lì)值，γ∈[0,1]為折扣因子。

3.1 計(jì)算切換決策時(shí)隙

在該計(jì)算卸載場(chǎng)景中，ES等間距部署在路旁，車輛運(yùn)動(dòng)遵循高速公路運(yùn)動(dòng)模型，做勻速運(yùn)動(dòng)。為使實(shí)驗(yàn)場(chǎng)景更切合真實(shí)環(huán)境，設(shè)定ES的計(jì)算負(fù)載能力和卸載場(chǎng)景的網(wǎng)絡(luò)帶寬服從時(shí)隙動(dòng)態(tài)變化，將卸載場(chǎng)景的動(dòng)態(tài)變化時(shí)隙設(shè)為基于MDP的計(jì)算切換決策時(shí)隙，綜合考慮計(jì)算和通信對(duì)任務(wù)完成時(shí)間的影響，以解決是否執(zhí)行切換以及切換到哪里等切換決策問題。本文將切換決策時(shí)刻的變化時(shí)隙定義為常數(shù)t，則基于馬爾科夫決策過程的計(jì)算切換決策時(shí)刻表示為T={0,t,2t,…}。

3.2 狀態(tài)空間模型

在車載邊緣計(jì)算環(huán)境中，因不同的ES的硬件性能、負(fù)載情況和網(wǎng)絡(luò)鏈路狀態(tài)不同，導(dǎo)致計(jì)算任務(wù)在不同的ES上所獲取的任務(wù)完成時(shí)間不同，一般選擇當(dāng)前決策時(shí)刻內(nèi)完成時(shí)間最短的代理資源。計(jì)算任務(wù)在代理資源上的狀態(tài)可表示為：

si={Ct,Dout,BWV2R,BWE2E,μV2R,μE2E},i=1,2,3

(10)

其中，Ct表示在決策時(shí)隙t內(nèi)的任務(wù)剩余計(jì)算量；Dout表示任務(wù)完成后的結(jié)果數(shù)據(jù)量，可根據(jù)輸入輸出比得到；BWV2R和BWE2E分別表示車輛終端與候選代理資源的數(shù)據(jù)傳輸速率和源代理資源切換到候選代理資源的數(shù)據(jù)傳輸速率；μV2R和μE2E分別表示車輛終端與候選代理資源的切換時(shí)延和源代理資源切換到候選代理資源的切換時(shí)延。

基于上述分析和任務(wù)模型，本文將該場(chǎng)景中的3個(gè)ES在決策時(shí)隙內(nèi)對(duì)應(yīng)的計(jì)算過程視為離散狀態(tài)空間S。在計(jì)算執(zhí)行過程中下一個(gè)時(shí)隙計(jì)算切換位置的選擇只與當(dāng)前時(shí)隙任務(wù)剩余計(jì)算量、代理資源計(jì)算狀態(tài)、網(wǎng)絡(luò)鏈路狀態(tài)以及終端移動(dòng)性對(duì)計(jì)算卸載的影響有關(guān)，因此計(jì)算切換過程滿足馬爾科夫性的要求。

基于馬爾科夫的計(jì)算切換的狀態(tài)空間表示為：

S={s1,s2,s3}

(11)

3.3 動(dòng)作空間模型

動(dòng)作空間模型指在切換決策時(shí)刻作為決策的輸入而具體執(zhí)行的操作。本文將決策動(dòng)作定義為在切換決策時(shí)刻根據(jù)當(dāng)前時(shí)隙各代理資源的狀態(tài)所采取的切換決策行為。決策動(dòng)作矩陣A可表示為：

(12)

其中，{a11,a22,a33}表示在決策時(shí)刻不執(zhí)行切換，任務(wù)仍在當(dāng)前代理資源上執(zhí)行；{a12,a13}表示當(dāng)前時(shí)隙內(nèi)任務(wù)在ES1上執(zhí)行到下一個(gè)時(shí)隙任務(wù)分別從ES1切換到ES2和ES3上時(shí)所采取的動(dòng)作，{a21,a23}和{a31,a32}同理。

切換策略可用于引導(dǎo)行為，在整個(gè)計(jì)算卸載過中所采取的所有動(dòng)作共同組成策略π=(ρ0,ρ1,…,ρN)，定義為一個(gè)連續(xù)切換決策序列。切換決策序列表示每個(gè)決策時(shí)隙所采取的行為，其中ρt:S→A。

3.4 狀態(tài)轉(zhuǎn)移矩陣

根據(jù)馬爾科夫決策過程的定義，狀態(tài)轉(zhuǎn)移概率可表示為：

(13)

其中，St,St+1分別表示在t,t+1時(shí)刻的狀態(tài)空間，si表示在t時(shí)刻的狀態(tài)，sj表示在t+1時(shí)刻的狀態(tài)，at表示在t時(shí)刻的動(dòng)作。

在車載邊緣計(jì)算環(huán)境中，本文將任務(wù)的完成時(shí)間作為優(yōu)化目標(biāo)，在決策時(shí)隙變化時(shí)根據(jù)任務(wù)的剩余計(jì)算量、代理資源的計(jì)算能力、網(wǎng)絡(luò)鏈路帶寬狀態(tài)以及用戶移動(dòng)位置對(duì)任務(wù)完成時(shí)間的影響，構(gòu)建狀態(tài)轉(zhuǎn)移概率矩陣P，其狀態(tài)轉(zhuǎn)移概率圖如圖2所示。

Figure 2 State transition probability圖2 狀態(tài)轉(zhuǎn)移概率

根據(jù)不同狀態(tài)下的轉(zhuǎn)移概率，可到的狀態(tài)轉(zhuǎn)移概率矩陣P為：

(14)

狀態(tài)轉(zhuǎn)移概率矩陣P中的轉(zhuǎn)移概率pij滿足：

0≤pij<1,i,j=1,2,3

(15)

3.5 優(yōu)化方程和策略迭代算法

在基于馬爾科夫決策過程的計(jì)算切換決策過程中，本文將從狀態(tài)si切換到狀態(tài)sj所獲得的報(bào)酬定義為Rij，是一個(gè)隨機(jī)變量。

本文采用無(wú)限馬爾科夫決策過程模型，定義vi(n)為系統(tǒng)現(xiàn)在狀態(tài)si經(jīng)過n次轉(zhuǎn)移后的總期望獲得，即其遞推關(guān)系可表示為：

i=1,2,3;N=3;n=1,2,3,…

(16)

每轉(zhuǎn)移一次到達(dá)sj的報(bào)酬，必須乘上相應(yīng)的轉(zhuǎn)移概率pij以得到總的期望獲得，故式(16)可寫成下列形式：

i=1,2,3;N=3;n=1,2,3,…

(17)

將qi作為由狀態(tài)si作出一次轉(zhuǎn)移的期望獎(jiǎng)勵(lì)，定義為狀態(tài)si的即時(shí)期望獎(jiǎng)勵(lì)，具體表示為：

(18)

則式(17)可表示為：

i=1,2,3;N=3;n=1,2,3,…

(19)

在基于馬爾科夫決策過程的計(jì)算切換過程中，根據(jù)動(dòng)作空間矩陣的描述，當(dāng)終端采用策略序列π時(shí)，累積獎(jiǎng)勵(lì)服從一個(gè)分布，累積獎(jiǎng)勵(lì)在狀態(tài)si時(shí)采取的一系列動(dòng)作的總體期望值定義為狀態(tài)-動(dòng)作值函數(shù)：

(20)

其中，γ為折扣因子，用于計(jì)算累積獎(jiǎng)勵(lì)。

根據(jù)馬爾科夫決策過程的定義，計(jì)算狀態(tài)值函數(shù)的目的是為了從數(shù)據(jù)中得到最優(yōu)策略。每個(gè)策略序列對(duì)應(yīng)著一個(gè)狀態(tài)-動(dòng)作值函數(shù)，即總期望獎(jiǎng)勵(lì)，最優(yōu)策略對(duì)應(yīng)的是最優(yōu)狀態(tài)值函數(shù)。為此，基于馬爾科夫決策過程的計(jì)算切換策略就是為了使vπ(s,a)最大化：

(21)

基于貝爾曼方程并運(yùn)用迭代循環(huán)算法求出最佳切換策略，具體過程如下所述：

(1)初始化實(shí)驗(yàn)環(huán)境，根據(jù)任務(wù)完成時(shí)間求出當(dāng)前時(shí)隙的狀態(tài)轉(zhuǎn)移概率矩陣P和獎(jiǎng)勵(lì)值R。

家在五樓，沒有燈火，想必父親已經(jīng)睡了。蔣海峰爬上樓，掏出鑰匙開門，聽見屋里發(fā)出令人恐怖的喊聲：“哪個(gè)？”

4 實(shí)驗(yàn)仿真與結(jié)果分析

本文針對(duì)車載邊緣計(jì)算環(huán)境中的計(jì)算卸載問題進(jìn)行仿真實(shí)驗(yàn)和結(jié)果分析，對(duì)比分析最小完成時(shí)間算法MCT(Minimum Complete Time)、基于最小執(zhí)行時(shí)間的計(jì)算切換算法METH(Handoff based on MET)、基于最小完成時(shí)間的計(jì)算切換算法MCTH(Handoff based on MCT)和基于馬爾科夫決策過程的計(jì)算切換算法MDP(handoff based on Markov Decision Process)，說明MDP算法的有效性。

實(shí)驗(yàn)仿真過程為：(1)卸載環(huán)境生成；(2)源節(jié)點(diǎn)產(chǎn)生卸載任務(wù)；(3)確定卸載算法；(4)計(jì)算卸載執(zhí)行；(5)計(jì)算切換執(zhí)行；(6)結(jié)果統(tǒng)計(jì)收集分析。

4.1 性能參數(shù)

本文針對(duì)車載邊緣計(jì)算環(huán)境中的計(jì)算卸載問題，提出以下3種性能參數(shù)以評(píng)價(jià)所提算法的有效性：

(1)任務(wù)平均完成時(shí)間：源節(jié)點(diǎn)所產(chǎn)生的計(jì)算密集型卸載任務(wù)執(zhí)行卸載過程所需要的總體完成時(shí)間，其中包括任務(wù)上傳時(shí)間、任務(wù)在代理資源上的執(zhí)行時(shí)間和任務(wù)完成后其結(jié)果量的下載時(shí)間。

(3)任務(wù)平均切換開銷：在計(jì)算執(zhí)行過程中，每次執(zhí)行計(jì)算切換所需的總時(shí)間開銷。

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

實(shí)驗(yàn)根據(jù)Geek2MIPS準(zhǔn)則[12]，設(shè)定邊緣層代理資源節(jié)點(diǎn)的計(jì)算能力為82335×[3,4,5,6,7]，汽車節(jié)點(diǎn)在運(yùn)動(dòng)過程中可通過V2R的方式與RSU上的代理資源進(jìn)行信息交互，且RSU的服務(wù)半徑為100 m～150 m均勻分布，具體參數(shù)設(shè)置如表1所示。

4.3 結(jié)果分析

本文實(shí)驗(yàn)基于1 000次仿真實(shí)驗(yàn)中各性能參數(shù)的平均值作為算法性能的度量標(biāo)準(zhǔn)，對(duì)比分析引入計(jì)算切換策略對(duì)計(jì)算卸載性能的提升，以及提出的基于MDP的計(jì)算切換策略可以進(jìn)一步降低計(jì)算切換所帶來(lái)的額外開銷，從而進(jìn)一步降低車輛移動(dòng)性對(duì)計(jì)算卸載的影響。

在卸載場(chǎng)景動(dòng)態(tài)變化的車載邊緣計(jì)算環(huán)境中，充分考慮代理資源的可用計(jì)算能力、通信環(huán)境的帶寬變化和車輛的移動(dòng)性對(duì)計(jì)算卸載的影響，對(duì)比分析4種算法的任務(wù)平均完成時(shí)間，實(shí)驗(yàn)結(jié)果如圖3所示。

Table 1 Parameter setting

Figure 3 Impact of dynamic scenarios on computational offloading圖3 動(dòng)態(tài)卸載場(chǎng)景對(duì)計(jì)算卸載的影響

由圖3可知，MDP算法、METH算法和MCTH算法的任務(wù)完成時(shí)間分別為74.78 s,89.52 s和86.47 s，相較于MCT算法，分別提升了29.37%，15.45%和18.33%。

由上述分析可知，在計(jì)算卸載執(zhí)行過程中引入計(jì)算切換策略，可以有效地提升計(jì)算卸載的性能，說明了計(jì)算切換策略的有效性。與此同時(shí)，由圖3可知，MDP算法相較于METH算法和MCTH算法,平均完成時(shí)間分別提升了16.46%和13.52%。這是因?yàn)镸DP算法的計(jì)算切換策略通過策略迭代的方法尋找出近似最優(yōu)的切換策略，而另外2種算法計(jì)算切換策略基于局部貪心的思想，只考慮當(dāng)前最優(yōu)解，因此MDP算法的計(jì)算切換策略可以提供更佳的用戶服務(wù)體驗(yàn)。

針對(duì)引入計(jì)算切換對(duì)計(jì)算卸載性能的影響，就任務(wù)平均切換次數(shù)和任務(wù)平均切換開銷等性能指標(biāo)，對(duì)比分析3種算法的性能效果，實(shí)驗(yàn)結(jié)果如圖4和圖5所示。

Figure 4 Handoff times圖4 切換次數(shù)

由圖4可知，在切換次數(shù)方面，MDP算法的總體切換次數(shù)最小，為2.03次。對(duì)比METH算法和MCTH算法的切換次數(shù)分別縮小了7.3%和14.7%。這是因?yàn)樵谟?jì)算卸載執(zhí)行過程中，隨著卸載場(chǎng)景的動(dòng)態(tài)變化，METH算法的計(jì)算切換策略受代理資源計(jì)算能力變化時(shí)隙決定，即代理資源的計(jì)算能力發(fā)生變化會(huì)觸發(fā)一次計(jì)算切換策略；而MCTH算法的計(jì)算切換策略同時(shí)受到代理資源的計(jì)算能力和網(wǎng)絡(luò)通信鏈路變化的共同影響。所以，MCTH算法的計(jì)算切換策略所觸發(fā)的計(jì)算切換次數(shù)相較于METH算法的較高，而MDP算法的計(jì)算切換策略考慮整個(gè)計(jì)算執(zhí)行過程，通過迭代的方式尋得近似最優(yōu)策略，故其切換次數(shù)最少。

Figure 5 Handoff cost圖5 切換開銷

由圖5可知，在切換開銷方面，MDP算法的切換開銷最低，為0.85 s。相較于另外2種算法分別縮短了30.32%和18.27%。

結(jié)合圖4中的計(jì)算切換次數(shù)，MCTH算法的計(jì)算切換策略綜合考慮了當(dāng)前決策時(shí)刻的計(jì)算開銷和通信開銷，在犧牲切換次數(shù)的前提下，降低了計(jì)算切換開銷；同理，MDP算法的計(jì)算切換策略從整體執(zhí)行過程考慮，進(jìn)一步降低了計(jì)算切換開銷，保證了用戶的服務(wù)體驗(yàn)。

5 結(jié)束語(yǔ)

本文針對(duì)計(jì)算卸載場(chǎng)景動(dòng)態(tài)變化的車載邊緣計(jì)算環(huán)境中的計(jì)算卸載問題進(jìn)行了探討和分析，就任務(wù)平均完成時(shí)間、任務(wù)平均切換次數(shù)和任務(wù)平均切換開銷等性能參數(shù)，對(duì)比分析了MCT、METH、MCTH和MDP算法的計(jì)算卸載性能。充分考慮代理資源的計(jì)算能力動(dòng)態(tài)變化以及車輛移動(dòng)性對(duì)計(jì)算卸載性能的影響，本文提出MDP算法的計(jì)算切換策略，實(shí)驗(yàn)結(jié)果表明了算法的有效性。

基于現(xiàn)有的研究，本文將任務(wù)完成時(shí)間作為主要優(yōu)化目標(biāo)，在未來(lái)的研究中，應(yīng)更多地考慮基于多種性能屬性下多個(gè)用戶產(chǎn)生多個(gè)任務(wù)由多個(gè)代理資源共同服務(wù)的復(fù)雜情況，使得實(shí)驗(yàn)場(chǎng)景更加切合實(shí)際。