基于馬爾科夫決策過程的車載邊緣計算切換策略*

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

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

1 引言

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

針對卸載場景動態化對計算卸載的影響，近年來國內外學者提出了不同的解決方案。文獻[5]提出了一種基于最小完成時間的計算切換策略，通過對比分析在邊緣層引入計算切換對計算卸載的影響，證明了計算切換策略的有效性，但該策略屬于求當前時刻最優解，并不適用于解決動態環境中的計算卸載問題。文獻[6]闡述了一種路徑可預測的場景，通過預測得到汽車運動軌跡，對需要卸載的計算任務進行預測性上傳和下載，以降低車輛移動性對計算卸載的影響。但是，該算法只實現了對任務上傳和下載階段的卸載性能優化，并未對計算執行過程進行深入探討，且不適用于動態環境中的計算卸載問題。

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

2 系統模型

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

Figure 1 Offloading scenario of vehicular edge computing 圖1 車載邊緣計算卸載場景

本文將VEC環境中的計算卸載系統模型分成任務模型、通信模型、計算模型和切換模型。

2.1 任務模型

本文將源節點產生的計算任務表示為：

Task={Din,C,Dout,Td}

(1)

其中，Din表示計算任務的上傳數據量，Dout表示計算任務的結果數據量，C表示計算任務的計算量，Td表示任務的截止完成時間。

本文將任務的上傳數據量與結果數據量的比值定義為“輸入輸出比”[9]：

(2)

2.2 通信模型

在VEC環境中的計算卸載過程中，根據節點類型不同，節點之間的通信方式不同。在該場景中，源節點可將任務通過無線通信的方式傳遞給RSU和基站BS，RSU與邊緣服務器ES(Edge Server)通過有線連接的方式進行通信，ES之間也通過有線傳輸的方式實現互聯互通。故根據通信模式的不同，各節點間單跳基礎帶寬可表示為：

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

(3)

(4)

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

2.3 計算模型

當汽車源節點產生計算任務時，計算卸載決策模塊根據任務屬性、資源狀態和網絡環境等多個因素進行計算卸載判決[10]。

當任務在車輛本地進行計算時，任務的完成時間TL表示為：

(5)

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

當任務執行卸載時，任務在ES上的完成時間表示為：

(6)

2.4 切換模型

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

Thandoff=Tpackage+Ta→b+Treboot

(7)

(8)

(9)

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

本文將基于馬爾科夫決策過程的計算切換策略定義為一個離散時間無限的折扣馬爾科夫決策過程M={S,A,P,R,γ}，其中S表示根據該場景中各個ES的計算能力、決策時隙內的網絡帶寬和剩余計算量而建立的狀態空間模型，A為動作空間矩陣，P表示在決策時隙內的狀態轉移概率矩陣，R表示獎勵值，γ∈[0,1]為折扣因子。

3.1 計算切換決策時隙

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

3.2 狀態空間模型

在車載邊緣計算環境中，因不同的ES的硬件性能、負載情況和網絡鏈路狀態不同，導致計算任務在不同的ES上所獲取的任務完成時間不同，一般選擇當前決策時刻內完成時間最短的代理資源。計算任務在代理資源上的狀態可表示為：

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

(10)

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

基于上述分析和任務模型，本文將該場景中的3個ES在決策時隙內對應的計算過程視為離散狀態空間S。在計算執行過程中下一個時隙計算切換位置的選擇只與當前時隙任務剩余計算量、代理資源計算狀態、網絡鏈路狀態以及終端移動性對計算卸載的影響有關，因此計算切換過程滿足馬爾科夫性的要求。

基于馬爾科夫的計算切換的狀態空間表示為：

S={s1,s2,s3}

(11)

3.3 動作空間模型

動作空間模型指在切換決策時刻作為決策的輸入而具體執行的操作。本文將決策動作定義為在切換決策時刻根據當前時隙各代理資源的狀態所采取的切換決策行為。決策動作矩陣A可表示為：

(12)

其中，{a11,a22,a33}表示在決策時刻不執行切換，任務仍在當前代理資源上執行；{a12,a13}表示當前時隙內任務在ES1上執行到下一個時隙任務分別從ES1切換到ES2和ES3上時所采取的動作，{a21,a23}和{a31,a32}同理。

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

3.4 狀態轉移矩陣

根據馬爾科夫決策過程的定義，狀態轉移概率可表示為：

(13)

其中，St,St+1分別表示在t,t+1時刻的狀態空間，si表示在t時刻的狀態，sj表示在t+1時刻的狀態，at表示在t時刻的動作。

在車載邊緣計算環境中，本文將任務的完成時間作為優化目標，在決策時隙變化時根據任務的剩余計算量、代理資源的計算能力、網絡鏈路帶寬狀態以及用戶移動位置對任務完成時間的影響，構建狀態轉移概率矩陣P，其狀態轉移概率圖如圖2所示。

Figure 2 State transition probability圖2 狀態轉移概率

根據不同狀態下的轉移概率，可到的狀態轉移概率矩陣P為：

(14)

狀態轉移概率矩陣P中的轉移概率pij滿足：

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

(15)

3.5 優化方程和策略迭代算法

在基于馬爾科夫決策過程的計算切換決策過程中，本文將從狀態si切換到狀態sj所獲得的報酬定義為Rij，是一個隨機變量。

本文采用無限馬爾科夫決策過程模型，定義vi(n)為系統現在狀態si經過n次轉移后的總期望獲得，即其遞推關系可表示為：

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

(16)

每轉移一次到達sj的報酬，必須乘上相應的轉移概率pij以得到總的期望獲得，故式(16)可寫成下列形式：

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

(17)

將qi作為由狀態si作出一次轉移的期望獎勵，定義為狀態si的即時期望獎勵，具體表示為：

(18)

則式(17)可表示為：

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

(19)

在基于馬爾科夫決策過程的計算切換過程中，根據動作空間矩陣的描述，當終端采用策略序列π時，累積獎勵服從一個分布，累積獎勵在狀態si時采取的一系列動作的總體期望值定義為狀態-動作值函數：

(20)

其中，γ為折扣因子，用于計算累積獎勵。

根據馬爾科夫決策過程的定義，計算狀態值函數的目的是為了從數據中得到最優策略。每個策略序列對應著一個狀態-動作值函數，即總期望獎勵，最優策略對應的是最優狀態值函數。為此，基于馬爾科夫決策過程的計算切換策略就是為了使vπ(s,a)最大化：

(21)

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

(1)初始化實驗環境，根據任務完成時間求出當前時隙的狀態轉移概率矩陣P和獎勵值R。

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

4 實驗仿真與結果分析

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

實驗仿真過程為：(1)卸載環境生成；(2)源節點產生卸載任務；(3)確定卸載算法；(4)計算卸載執行；(5)計算切換執行；(6)結果統計收集分析。

4.1 性能參數

本文針對車載邊緣計算環境中的計算卸載問題，提出以下3種性能參數以評價所提算法的有效性：

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

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

4.2 參數設置

實驗根據Geek2MIPS準則[12]，設定邊緣層代理資源節點的計算能力為82335×[3,4,5,6,7]，汽車節點在運動過程中可通過V2R的方式與RSU上的代理資源進行信息交互，且RSU的服務半徑為100 m～150 m均勻分布，具體參數設置如表1所示。

4.3 結果分析

本文實驗基于1 000次仿真實驗中各性能參數的平均值作為算法性能的度量標準，對比分析引入計算切換策略對計算卸載性能的提升，以及提出的基于MDP的計算切換策略可以進一步降低計算切換所帶來的額外開銷，從而進一步降低車輛移動性對計算卸載的影響。

在卸載場景動態變化的車載邊緣計算環境中，充分考慮代理資源的可用計算能力、通信環境的帶寬變化和車輛的移動性對計算卸載的影響，對比分析4種算法的任務平均完成時間，實驗結果如圖3所示。

Table 1 Parameter setting

Figure 3 Impact of dynamic scenarios on computational offloading圖3 動態卸載場景對計算卸載的影響

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

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

針對引入計算切換對計算卸載性能的影響，就任務平均切換次數和任務平均切換開銷等性能指標，對比分析3種算法的性能效果，實驗結果如圖4和圖5所示。

Figure 4 Handoff times圖4 切換次數

由圖4可知，在切換次數方面，MDP算法的總體切換次數最小，為2.03次。對比METH算法和MCTH算法的切換次數分別縮小了7.3%和14.7%。這是因為在計算卸載執行過程中，隨著卸載場景的動態變化，METH算法的計算切換策略受代理資源計算能力變化時隙決定，即代理資源的計算能力發生變化會觸發一次計算切換策略；而MCTH算法的計算切換策略同時受到代理資源的計算能力和網絡通信鏈路變化的共同影響。所以，MCTH算法的計算切換策略所觸發的計算切換次數相較于METH算法的較高，而MDP算法的計算切換策略考慮整個計算執行過程，通過迭代的方式尋得近似最優策略，故其切換次數最少。

Figure 5 Handoff cost圖5 切換開銷

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

結合圖4中的計算切換次數，MCTH算法的計算切換策略綜合考慮了當前決策時刻的計算開銷和通信開銷，在犧牲切換次數的前提下，降低了計算切換開銷；同理，MDP算法的計算切換策略從整體執行過程考慮，進一步降低了計算切換開銷，保證了用戶的服務體驗。

5 結束語

本文針對計算卸載場景動態變化的車載邊緣計算環境中的計算卸載問題進行了探討和分析，就任務平均完成時間、任務平均切換次數和任務平均切換開銷等性能參數，對比分析了MCT、METH、MCTH和MDP算法的計算卸載性能。充分考慮代理資源的計算能力動態變化以及車輛移動性對計算卸載性能的影響，本文提出MDP算法的計算切換策略，實驗結果表明了算法的有效性。

基于現有的研究，本文將任務完成時間作為主要優化目標，在未來的研究中，應更多地考慮基于多種性能屬性下多個用戶產生多個任務由多個代理資源共同服務的復雜情況，使得實驗場景更加切合實際。