基于馬爾科夫優化的移動邊緣計算車載網絡任務卸載

李沁穎，曹青松

(江西科技學院 a. 信息工程學院，b. 智能工程學院，江西南昌 330098)

車載網絡利用車輛與車輛(vehicle to vehicle，V2V)[1]、車輛與基礎設備(vehicle to infrastructure，V2I)[2]、車輛與互聯網(vehicle to network，V2N)[3]等方式進行無線通信，以保證車輛駕駛的安全性和提高交通通行的效率，實現路況預測和協同駕駛；但是集中式車載網絡受到通信距離的限制，不能高效地利用網絡資源，并且傳輸與計算也無法滿足移動設備用戶需求，因此移動邊緣計算(mobile edge computing，MEC)車載網絡引起廣泛關注。將MEC引入車載網絡，令車載數據下沉至網絡邊緣和本地設備[4-5]，協助車載系統迅速分析決策[6]，極大地節省了網絡資源的容量，同時也提高了車輛的服務質量(quality of service,QoS)。此外，考慮車輛用戶對實時通信的需求和車輛計算資源能力有限[7]，MEC車載網絡將分布密集的計算任務資源部分或全部分配至網絡邊緣進行計算卸載[8]，以降低計算成本，改善計算性能，緩解數據傳輸過程的丟包、延遲問題。Zhang等[9]考慮MEC車載網絡中車輛移動性，采用契約理論設計了最優計算卸載策略的資源分配方案，結果表明，MEC車載網絡能夠有效提高車輛任務的計算效率。為了提高任務計算結果的可靠性，Zhang等[10]利用MEC服務器接收車載節點任務信息，以預測車載節點可通信區域，從而提出目標服務器的計算卸載方案。Huang等[11]針對網絡頻繁切換帶來的負擔問題，將蜂窩網絡中的車輛通信業務卸載到車載網絡中的V2V通信路徑，為車輛數據傳輸提供了新方案。Chen等[12]研究多用戶無線卸載問題，利用分布式博弈理論，設計基于移動邊緣云計算的任務卸載方法，綜合考慮了多信道無線通信環境。Al-Shuwaili等[13]采用凸近似定理，提出將通信和計算資源分配至MEC服務器，以解決資源分配造成的能量消耗過大的問題。Zhang等[14]提出多弧度結合機制，利用該機制模型匹配MEC服務器和移動終端，使得計算任務能夠卸載至最優MEC服務器，降低了任務卸載過程中產生的開銷。

已有的基于MEC車載網絡資源分配和任務卸載的文獻大多考慮單一的智能網聯汽車，將車輛計算任務完全卸載至移動邊緣設備或本地車輛； 而在實際駕駛環境中，智能網聯汽車多以車隊的形式進行駕駛，目前鮮有對智能網聯式車隊選擇最優任務卸載方案的研究。本文中針對MEC車載網絡，建立移動車輛參考點群組移動模型，利用簇頭車輛節點預估群組其他車輛的移動速度和方向，構建任務卸載模型，將計算任務分別卸載至相鄰的車輛節點和MEC服務器，采用馬爾科夫優化過程，獲取車輛節點狀態，通過狀態轉移，選擇資源分配和任務卸載聯合優化方案，從而實現提高任務卸載效率的目標。

1 MEC車載網絡系統模型

根據任務需求將資源按不同比例分配至MEC服務器和相鄰車載網絡車輛，建立MEC車載網絡系統模型，進行任務卸載計算，其中系統模型主要包含車載網絡車輛移動模型和任務卸載模型。

1.1 車載網絡車輛移動模型

考慮模型中的車輛移動方向，采用參考點群組移動模型作為車輛移動模型，如圖1所示。

圖1 基于移動邊緣計算(MEC)的車載網絡場景

對于模型中的車輛移動方向，僅考慮5種移動情況，即正北N、正南S、正東E、正西W、靜止狀態F，記為a={N, S, E, W, F}。

EVGm=Ecen+random()Rsas，

(1)

DVGm=Dcen+random()Raaa，

(2)

式中： random()為取隨機量的函數；Rs、Ra分別為車輛速度偏移率、車輛角度偏移率；as、aa分別為車輛速度偏移量、車輛角度偏移量。

1.2 任務卸載模型

T—任務計算總過程； TMEC—移動邊緣計算(MEC)服務器任務計算總過程； Tv—車輛任務計算總過程； Tt—任務傳輸過程；任務傳輸至MEC的過程；任務傳輸至本地車輛的過程； Tw—任務在MEC服務器的等待過程；任務在MEC的執行過程；任務在本地車輛的執行過程。圖2 智能網聯車隊車輛任務計算過程

假定當前群組Gm車輛節點VGm發布計算任務VWGm=(λWVGm, (1-λ)WVGm)，其中λ為計算任務劃分至本地車輛的比例，λWVGm為傳輸至本地車輛節點的計算任務容量，(1-λ)WVGm為通過無線通信鏈路傳輸至MEC服務器的計算任務容量。執行結束后需將計算結果返還至車輛節點，如果在MEC服務器任務計算結果返還過程中，車輛節點計算任務還未結束，則需要等待執行。

為了更好地利用閑置網絡資源，達到最大任務時間最小化的目標，令執行時間等于任務傳輸時間，計算恰當的資源分配和任務卸載比例。任務資源分配為

(3)

(4)

其中資源分配和任務卸載比例為

(5)

式中：φ為計算任務的復雜度；β為任務傳輸完整度；Cv為車輛計算數據能力，即單位時間內車輛中央處理器(CPU)循環執行的周期數；Sv為車輛網絡通信傳輸速度。

當前車輛節點處于行駛狀態時，可將任務卸載至當前節點可用的通信范圍內具有相同行駛方向和相似行駛速度的相鄰車輛和MEC服務器；當前車輛節點處于靜止停泊狀態時，可將任務卸載至車輛節點可用通信范圍內的其他停泊鄰居車輛和MEC服務器，如圖3所示。

VGm={V1, V2, , Vb}—智能網聯式車隊車輛節點，m=1, 2,,x，x為群組個數，b為群組車輛節點個數； WVGm—車輛 節點的計算任務容量； λ—計算任務劃分至本地車輛的 比例； 1-λ—計算任務劃分至MEC服務器的比例。圖3 移動邊緣計算(MEC)車載網絡任務資源分配模型

1.3 任務卸載計算

當計算任務分配至本地相鄰車輛時，車輛節點計算任務執行時間為

(6)

車輛計算任務按需求比例分配至計算數據能力為CMEC、計算任務復雜度為φ的MEC服務器，則MEC服務器執行任務時間為

(7)

在計算過程前后，需要通過無線通信鏈路將任務傳輸至計算節點，則計算任務傳輸至MEC服務器和相鄰車輛的傳輸時間分別為

(8)

(9)

式中：SMEC為MEC服務器網絡通信傳輸速度。

由此，計算任務在MEC服務器、本地相鄰車輛的執行時間和傳輸時間分別為

(10)

(11)

(12)

T=max{TMEC,Tv,Tt}

。

(13)

根據式(13)獲得的計算任務執行總時長，對所有資源分配和任務卸載方案進行最優決策。

2 馬爾科夫優化過程

MEC車載網絡下資源分配和任務卸載的馬爾科夫優化過程表示為(A，S，P，R)，其中A為行為空間，S為系統狀態空間，P為狀態轉換概率，R為開銷收益。

2.1 行為空間

在時間段[1,k]可選擇的數據傳輸路徑為行為空間A={a1,a2, ,ak}，其中

(14)

式中γ為當前數據通過多種狀態的鄰居車輛節點傳輸。

2.2 狀態空間

(15)

2.3 狀態轉移

狀態轉移pz(i,j)為在時間段[k-1,k]，當前行為從當前選擇的路徑i轉移至路徑j的條件概率，即

(16)

其中

1.2.2 研究過程 征得源量表作者同意后對N-QOL量表進行漢化。首先由2名英語較好的研究生將量表翻譯成中文，其中1名托福考試成績優異；然后由研究者和以上2人共同對翻譯結果進行綜合整理，再請2名大學英語教師將量表回譯成英文，與源量表進行比較，最后經過4名翻譯人員及研究者的反復商討確定初步版本。將漢化后的量表提交給5名相關專家，采用4分法對量表內容效度進行評價，1=不相關，2=有點相關，3=相關，4=高度相關。根據專家意見對量表進行修改后進行預試驗，選取20例夜尿癥患者填寫量表，了解患者對各條目的反應，必要時進行文化調試。最后將量表應用于較大樣本的夜尿癥人群中，評價漢化后量表的性能。

(17)

選擇不同運動方向的pγ0,γ1(i,j)的計算過程如下。

1)當γ0≠F且γ1≠F時，

(18)

其中

(19)

式中：psuc為當前車輛節點傳輸數據至鄰居車輛節點的成功概率；H為傳輸路徑的傳輸容量。

2) 當γ0=F時，

(20)

1)當ak=0時，計算任務選擇在本地相鄰車輛中傳輸，則任務卸載至當前車輛節點或其他鄰居車輛節點，即

(21)

2)當ak=1時，計算任務選擇在無線通信中傳輸，則任務卸載至MEC服務器節點，則

(22)

3)當ak=γ時，計算任務選擇在車輛行駛方向傳輸，則任務分別卸載至相鄰車輛節點和MEC服務器節點，即

(23)

2.4 系統最優決策

在基于MEC車載網絡的系統模型中，車輛可利用馬爾科夫優化過程選擇最優決策方案，并將任務卸載至本地相鄰車輛和MEC服務器節點，從而獲得任務最短執行時間，因此系統在整個任務執行周期的期望執行時間ttot為

(24)

式中：arg min{·}為取任務執行時間最小值函數；η為折扣因子，0≤η≤1；t為時間周期；TGm為車輛群組任務執行最短時間。

通過式(24)可獲得最短執行時間，從而選擇資源分配和任務卸載的聯合優化方案。

3 基于馬爾科夫優化的任務卸載流程

3.1 系統初始化

在車輛行駛區域中，將所有車輛節點、RSU設備節點、MEC服務器節點進行自定義組織，構建MEC車載網絡。由于系統網絡結構是相對穩定的，并且每個系統節點均有對應的計算能力、傳輸速度、當前狀態等參數信息，因此當網絡結構中節點狀態發生變化時，系統網絡結構也會進行重新構造，每個節點參數信息隨之更新。

3.2 任務卸載流程

假設發布計算任務的車輛節點為初始節點，并考慮當前車輛節點可通信范圍內的所有相鄰車輛節點和MEC服務器節點的參數信息，形成計算任務的所有資源分配和卸載方案。同時，根據任務復雜度、完整度及任務量，計算車輛任務分配至本地車輛節點和MEC服務器的比例。

將可通信范圍內的所有車輛節點設為備選節點，根據車輛狀態信息計算出每個備選節點的任務傳輸成功率，即為預選節點跳轉成功率，從而組成狀態轉移矩陣。

通過狀態轉移矩陣可以采集到計算任務的所有預選傳輸路徑，計算每個傳輸路徑中任務卸載的總時長，從而確定任務卸載最優方案，即任務卸載時長最短的傳輸路徑。

4 仿真實驗

4.1 仿真實驗參數

設計相應的仿真實驗，并通過MATLAB軟件實現，具體仿真實驗參數如表1、2所示。

表1 智能網聯式車隊車輛仿真環境參數

表2 移動邊緣計算(MEC)車載網絡任務卸載仿真實驗參數

4.2 仿真結果分析

從不同任務量、時間段2個方面進行考慮，分別比較車輛計算任務全部卸載至車輛節點、MEC服務器及分別卸載至車輛節點、MEC服務器的總時長，結果如圖4所示。

(a)不同任務量

(b)不同時間段 MEC—移動邊緣計算。圖4 不同任務量、時間段時資源分配和任務卸載的總時長

從圖4(a)中可以看出，不同任務量時，任務卸載至車輛節點用的時長明顯長于其他2種任務卸載方法所用時長，并且本文中采用的馬爾科夫優化方法所耗費的總時長最短。在資源分配和任務卸載過程中，3種方法的總時長均隨著任務資源容量的增加而緩慢增加。此外，當車輛處于靜止狀態時，任務分別卸載至本地相鄰車輛節點和MEC服務器的總時長短于車輛處于行駛狀態時的總時長，原因是車輛處于行駛狀態受到地理環境、行駛速度等多方面的影響，造成傳輸速度和通信的不穩定。

從圖4(b)中可以看出，車輛高速移動性使得任務僅卸載至車輛節點所耗費的總時長隨MEC服務器傳輸速度增大而浮動，不能很好地反映網絡傳輸速度和任務卸載之間的關系；隨著MEC服務器傳輸任務速度的增大，任務傳輸時間逐漸減少，任務僅卸載至MEC服務器和分別卸載至MEC服務器、車輛節點所用的總時長也呈遞減趨勢，并且本文中采用的方法任務執行總時長最短。

5 總結

本文中研究了MEC環境中車載網絡任務資源分配和卸載問題，構建了描述資源分配和任務卸載路徑方案的MEC車載網絡系統模型，考慮不同任務的計算需求，將任務資源按不同比例分配至車輛節點和MEC服務器，通過馬爾科夫優化過程選擇資源分配和任務卸載聯合最優方案。仿真實驗表明，本文中采用的資源分配和任務卸載馬爾科夫優化方法節省了任務執行總時長，能夠合理利用網絡資源，提高效率。