車聯(lián)網(wǎng)場景下的移動邊緣計算卸載策略

余 翔,劉一勛,石雪琴,王 政

(重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065)

0 概述

作為移動邊緣計算(Mobile Edge Computing,MEC)的典型服務(wù)場景[1],車聯(lián)網(wǎng)(Internet of Vehicles,IoV)為智能交通系統(tǒng)中的車載終端、路側(cè)單元以及行人提供無線通信服務(wù),實現(xiàn)車對車(V2V)、車對基礎(chǔ)設(shè)施(V2I)、車對行人(V2P)以及車對網(wǎng)絡(luò)(V2N)的通信[2]。

與傳統(tǒng)移動通信中的計算任務(wù)不同,在車聯(lián)網(wǎng)場景中,車載終端會在短時間內(nèi)生成大量合作感知信息[3]與分布式環(huán)境通知消息[4]來合作完成保障道路安全與提高交通效率的車聯(lián)網(wǎng)安全型業(yè)務(wù)。由于車載終端的計算任務(wù)涉及人身安全,因此對時延有嚴(yán)格的要求,與傳統(tǒng)的通信業(yè)務(wù)相比,其計算任務(wù)數(shù)量激增且處理優(yōu)先級更高。

在傳統(tǒng)云車系統(tǒng)中,移動云計算雖然極大地提高了資源利用率和計算性能,但由于回程和骨干網(wǎng)絡(luò)上的傳輸容量限制以及延遲波動,遠(yuǎn)離移動車輛的云服務(wù)可能使卸載效率大幅降低。配置MEC服務(wù)器的車聯(lián)網(wǎng)架構(gòu)被認(rèn)為是一種有效縮短V2I、V2N應(yīng)用時延的方案[5-6]。此類方案將連接的汽車云擴(kuò)展到分散的移動基站環(huán)境中,使數(shù)據(jù)和應(yīng)用能夠靠近車輛,實現(xiàn)車載計算任務(wù)的實時化處理,減少業(yè)務(wù)的時延。

計算卸載作為MEC的關(guān)鍵技術(shù)之一[7],是MEC系統(tǒng)實現(xiàn)終端業(yè)務(wù)實時化處理的重要手段[8-9]。實驗證明,將任務(wù)卸載到MEC上,最多可減少88%的時延[10]。文獻(xiàn)[11]在MEC車聯(lián)網(wǎng)場景下考慮任務(wù)執(zhí)行時延、車輛移動時延以及數(shù)據(jù)傳輸時延,設(shè)計基于任務(wù)時延的效用函數(shù)來平衡負(fù)載和表現(xiàn)時延滿意度,進(jìn)而提出一種低復(fù)雜度的算法用于解決該整數(shù)非線性規(guī)劃問題。文獻(xiàn)[12]提出加入MEC服務(wù)器減少C-V2X中端到端信令時延的方法。文獻(xiàn)[13]設(shè)計基于MEC的卸載架構(gòu),考慮MEC服務(wù)器的資源限制和計算任務(wù)的時延容忍,通過引入契約理論設(shè)計有效的計算卸載策略,最大限度地提高了MEC服務(wù)提供商的利益,增強(qiáng)了車輛的效用。文獻(xiàn)[14]研究了車輛邊緣網(wǎng)絡(luò)中的多車輛計算卸載問題,提出一種基于博弈論的車載邊緣網(wǎng)絡(luò)離線算法,其考慮每輛車的卸載策略以求最小化系統(tǒng)總開銷。文獻(xiàn)[15]研究5G環(huán)境中車輛的計算任務(wù)卸載問題,從計算任務(wù)和通信兩個方面對5G網(wǎng)絡(luò)車輛計算卸載的能量消耗進(jìn)行建模,并利用人工魚群算法解決計算卸載能耗最小化問題,但其在邊緣車輛網(wǎng)絡(luò)的計算卸載過程中,未考慮車輛同時并發(fā)多個具有不同優(yōu)先級計算任務(wù)的情況。

本文針對MEC車聯(lián)網(wǎng)計算卸載系統(tǒng),在MEC服務(wù)器計算資源負(fù)載不均的限制條件下,提出基于遺傳算法的卸載策略。通過對計算任務(wù)進(jìn)行編碼,利用遺傳算法尋找最優(yōu)卸載策略,將計算任務(wù)卸載至合適的MEC服務(wù)器,在保障車載安全型業(yè)務(wù)優(yōu)先處理的同時,減小MEC服務(wù)器計算資源負(fù)載不均對任務(wù)完成率的影響。

1 系統(tǒng)模型

本文系統(tǒng)模型如圖1所示。假設(shè)J個配置MEC服務(wù)器的RSU在道路上均勻分布,將MEC服務(wù)器記為mecj,j∈{1,2,…,J},C臺隨機(jī)分布的車輛各自攜多個計算任務(wù),設(shè)共攜帶N個計算任務(wù),表示為Ltask={b,w,ω,tmax,RL},其中,b表示輸入數(shù)據(jù)的大小,w表示任務(wù)計算量,ω是一個可變的參數(shù),表示該計算任務(wù)的重要程度,以區(qū)分該任務(wù)為傳統(tǒng)計算任務(wù)或車載安全型計算任務(wù),tmax表示任務(wù)截止時限,任務(wù)處理時延超出時限則表示任務(wù)處理失敗,RL表示任務(wù)所屬車載終端所在的MEC服務(wù)小區(qū)。

圖1 MEC車聯(lián)網(wǎng)系統(tǒng)模型Fig.1 System model of MEC Internet of vehicles

用x表示車載終端將計算任務(wù)卸載至MEC服務(wù)器的編號,x={0,1,…,J},1～J表示卸載至MEC服務(wù)器的編號,x=0表示任務(wù)由車載終端處理完成。N個計算任務(wù)的卸載策略構(gòu)成卸載策略向量集X={x1,x2,…,xN}。

1.1 通信模型

車輛移動與通信模型可參考文獻(xiàn)[16],車輛與RSU之間的通信是通過LTE-V2I直連的無線鏈路進(jìn)行的[17],車輛到RSU的上傳鏈路設(shè)定為頻率平坦型快衰落的瑞利信道[18]。根據(jù)香農(nóng)公式可以計算出上傳鏈路的數(shù)據(jù)傳輸速率為:

(1)

場景中車輛以恒定單方向的速度行駛,車輛Ci的速度用vi表示,車輛的移動性使其與RSU覆蓋范圍中心之間的距離dl隨時間變化,變化規(guī)律可用下式表示:

(2)

其中,e表示車輛行駛水平線與RSU的距離,s表示RSU的覆蓋范圍。

(3)

1.2 計算模型

計算任務(wù)的處理分為數(shù)據(jù)傳輸和數(shù)據(jù)計算兩部分,若任務(wù)i進(jìn)行本地計算,則僅考慮其計算時延而不考慮傳輸時延。本地任務(wù)處理時延的計算公式為:

(4)

其中,eloc表示車載終端的計算能力。對于需要進(jìn)行卸載的任務(wù),有本地服務(wù)器卸載與其他服務(wù)器卸載2種情況。

1.2.1 本地服務(wù)器卸載

(5)

(6)

(7)

1.2.2 其他服務(wù)器卸載

由于當(dāng)前所在范圍MEC服務(wù)器的負(fù)載較重,車載終端決定將計算任務(wù)卸載至其他MEC服務(wù)器。MEC服務(wù)器之間往往通過光纖等有線鏈路進(jìn)行相連。假設(shè)在有線鏈路l上的計算任務(wù)平均傳輸?shù)却龝r延為tw,則此時任務(wù)處理時延的計算公式為:

(8)

其中,a表示計算任務(wù)卸載至其他范圍MEC服務(wù)器的有線鏈路跳數(shù)。

1.2.3 計算資源分配

為保證任務(wù)在規(guī)定時限內(nèi)完成且任務(wù)不中斷,要求計算任務(wù)在車輛離開所屬MEC小區(qū)前完成任務(wù)。因此,本地服務(wù)器卸載的情況應(yīng)滿足式(9),其他服務(wù)器卸載的情況應(yīng)滿足式(10):

(9)

(10)

由此可推導(dǎo)出2種情況下完成計算任務(wù)所需計算資源分別為:

(11)

(12)

對所有卸載至mecj服務(wù)器的計算任務(wù),申請的總計算資源為:

(13)

本文研究目的是對優(yōu)先級較高的計算任務(wù)優(yōu)先處理,同時提升全計算任務(wù)的完成數(shù)量。因此,定義系統(tǒng)效用函數(shù)如下:

(14)

其中,α表示計算任務(wù)總權(quán)重值。

最終計算模型建模為:

max(P)

s.t.

C3:ej

(15)

在式(15)中:約束條件C1表示一個計算任務(wù)只能卸載至某一個MEC服務(wù)器,不能同時卸載至兩個服務(wù)器;C2表示計算任務(wù)采取二元卸載,只能將整個計算任務(wù)卸載至MEC服務(wù)器,或者不進(jìn)行卸載;約束條件C3表示卸載至MEC服務(wù)器的計算任務(wù)所消耗的計算資源不能超過MEC總的計算資源。

2 基于遺傳算法的任務(wù)卸載策略

2.1 問題描述

本文將優(yōu)化問題轉(zhuǎn)化為背包問題,并采用遺傳算法[19]來進(jìn)行求解以滿足計算卸載需求。不同的MEC服務(wù)器具有不同的計算能力,當(dāng)計算資源不夠的MEC服務(wù)器承接大量的計算任務(wù)時,不僅無法保障計算任務(wù)的完成,而且會導(dǎo)致MEC服務(wù)器負(fù)載過重影響其他業(yè)務(wù)的處理。同時隨機(jī)地對計算任務(wù)進(jìn)行卸載,又會導(dǎo)致在尋找最優(yōu)計算卸載策略時迭代次數(shù)冗長。因此,本文采用基于遺傳算法的任務(wù)卸載策略(Genetic Algorithm-based Offloading Strategy,GAOS)預(yù)留合適的初始染色體,結(jié)合貪婪算法尋找每個MEC服務(wù)器的最優(yōu)卸載策略,加速迭代過程。

2.2 編碼

本文采用二進(jìn)制編碼,每條染色體的編碼為一種卸載策略X,用X(m)表示策略X中m位的取值,X(m)取0或1。為了表示所有計算任務(wù)能卸載至所有服務(wù)器,編碼位數(shù)M應(yīng)滿足以下條件:

M≥lbJ

(16)

以[XiMXiM+1XiM+2…X(i+1)M]表示計算任務(wù)i的卸載結(jié)果,其卸載的MEC服務(wù)器編號xi為:

(17)

不超出8個MEC服務(wù)器的計算任務(wù)策略編碼過程如圖2所示。

圖2 策略編碼與MEC服務(wù)器的映射Fig.2 Mapping of policy coding to MEC servers

2.3 初始化

初始化遺傳算法的相關(guān)參數(shù),包括最大的迭代次數(shù)I、染色體長度N×M、變異概率pm、交叉概率pc、種群大小ps以及預(yù)留種群r。多數(shù)遺傳算法是隨機(jī)選擇初始種群,GAOS策略則結(jié)合了預(yù)定義染色體和隨機(jī)染色體算法進(jìn)行種群初始化。在預(yù)定義染色體過程中,將染色體中權(quán)重最高類,即車載安全類的計算任務(wù)(ω=ω1)編碼設(shè)置如下:

(18)

預(yù)定義染色體編碼算法描述如下:

輸入N,ps,Ri,ω1

輸出X

for k=1 to ps

for i=1 to N

if xi=Riand ωi=ω1then

else

end for

若共Nc個計算任務(wù)被預(yù)定義,則剩余(N-Nc)個計算任務(wù)的編碼隨機(jī)生成,剩余(r-ps)個種群的染色體編碼隨機(jī)生成,維持種群的隨機(jī)性。

2.4 解集修復(fù)

由式(9)～式(12)可知,當(dāng)分配給計算任務(wù)的計算資源恰好滿足時限,則2種情況下消耗的計算資源最小,分別為:

(19)

(20)

本文通過貪婪算法修復(fù)解集,對超出服務(wù)器j計算資源中的計算任務(wù)計算其價值密度dij,如式(21)所示:

(21)

以Nj表示卸載到服務(wù)器j的任務(wù)編號,找到最小價值密度的計算任務(wù)并將其從MEC服務(wù)器隊列移除,再重新計算消耗的計算資源,重復(fù)該步驟,直至所有計算任務(wù)消耗的計算資源不超過MEC服務(wù)器總的計算資源。解集修復(fù)算法描述如下:

輸入ps,J,ej,Ej,Nj,dij

輸出X

for k=1 to ps

for j=1 to J

if ej>Ejthen

for i=1 to Nj

if dij=min(dij) then

ej=ej-emin(dij)

until ej≤Ej

end for

end if

end for

2.5 適應(yīng)度函數(shù)構(gòu)造

適應(yīng)度函數(shù)的構(gòu)造是解決本文優(yōu)化問題的關(guān)鍵,其目標(biāo)函數(shù)如式(15)所示。因此,給出適應(yīng)度函數(shù)的計算公式為:

(22)

2.6 選擇操作

根據(jù)選擇概率選擇染色體,將上述個體作為第一代,采用正比于適應(yīng)度的輪盤賭隨機(jī)選擇方式,設(shè)個體的適應(yīng)度為fi,則i被選中的概率為:

(23)

對于初始化后的種群,計算每條染色體的適應(yīng)度值及其被選擇的概率進(jìn)行比較,剔除概率最低的染色體,選擇概率最大的染色體進(jìn)行復(fù)制,代替被剔除掉的染色體。

2.7 交叉操作

本文采用一點交叉方式,交叉概率為Pc,具體操作是在個體串中隨機(jī)設(shè)定一個交叉點,實行交叉時,該點前或后兩個個體的部分結(jié)構(gòu)進(jìn)行互換,并生成兩個新個體。

2.8 變異操作

對于本文優(yōu)化問題,變異操作就是將染色體的變異位1變?yōu)?,0變?yōu)?,其他位都保持不變,變異概率為Pc。因此,選擇一個變異位進(jìn)行變異,再計算其適應(yīng)度是否大于或等于其原來的適應(yīng)度,若不是則重新選擇變異位進(jìn)行變異。

3 仿真結(jié)果分析

本節(jié)通過仿真結(jié)果來驗證GAOS策略的性能。模擬一個擁有3個MEC服務(wù)器的車聯(lián)網(wǎng)計算卸載系統(tǒng),采用與文獻(xiàn)[20]相同的比較方式,將GAOS與以下卸載方案進(jìn)行比較:

1)ALL-Local策略:所有計算任務(wù)放在本地執(zhí)行。

2)Random策略:所有計算任務(wù)隨機(jī)卸載至MEC服務(wù)器,根據(jù)卸載車載終端數(shù)平均分配計算資源。

3)ALL-MEC策略:所有車載終端進(jìn)行任務(wù)卸載,MEC服務(wù)器根據(jù)剩余計算資源對計算任務(wù)平均分配計算資源。

仿真參數(shù)如表1所示,車載安全型計算任務(wù)參數(shù)如表2所示。

表1 仿真參數(shù)Table 1 Simulation parameters

表2 車載安全型計算任務(wù)參數(shù)Table 2 Parameters of safety on-board computing task

首先驗證GAOS策略的迭代次數(shù)對任務(wù)完成率的影響,任務(wù)完成率表示為成功計算的計算任務(wù)占總計算任務(wù)的比例。本文通過多次重復(fù)實驗,研究不同車載終端數(shù)C下迭代次數(shù)對任務(wù)完成率的影響。由圖3可以看出,GAOS策略均可在有效次迭代后達(dá)到平穩(wěn)。

圖3 迭代次數(shù)對任務(wù)完成率的影響Fig.3 Influence of iterations number on task completion rate

本文通過重復(fù)實驗,研究用戶在不同卸載方案下車載安全型計算任務(wù)(ω=ω1)的成功處理比例。由圖4可以看出,為取得最大系統(tǒng)效用函數(shù)值,GAOS策略在卸載過程中,將更多優(yōu)先級高的任務(wù)卸載至MEC服務(wù)器。與未對優(yōu)先級任務(wù)做處理的Random策略以及ALL-MEC策略相比,分別提高了約30%和50%的車載安全型計算任務(wù)成功處理數(shù)量。

圖4 不同卸載方案下車載安全型計算任務(wù)完成數(shù)量Fig.4 Number of completed safety on-board computing tasks of different offloading schemes

定義參數(shù)v為MEC服務(wù)器負(fù)載不均程度因子:

(24)

在固定車載終端數(shù)為50的情況下,研究MEC服務(wù)器的負(fù)載不均程度對任務(wù)完成率的影響。由圖5可以看出,ALL-MEC策略以及Random策略會因MEC服務(wù)器負(fù)載不均而無法保證計算任務(wù)完成率。GAOS策略在對決策方案進(jìn)行迭代時,對負(fù)載嚴(yán)重的MEC服務(wù)器減少了計算任務(wù)的卸載,對負(fù)載較輕的MEC服務(wù)器增加了計算任務(wù)的卸載,以達(dá)到負(fù)載均衡的效果,相較于其他策略,其受MEC服務(wù)器負(fù)載不均的情況影響較小。

圖5 負(fù)載不均程度對任務(wù)完成率的影響Fig.5 Influence of load unevenness degree on task completion rate

可以看出,GAOS策略能夠在有限次的迭代后收斂,得到較優(yōu)的卸載策略。通過與傳統(tǒng)計算卸載策略的實驗對比可知,GAOS策略在具有各種多優(yōu)先級計算任務(wù)的車聯(lián)網(wǎng)場景下,與可以卸載更多數(shù)量的車載安全型計算任務(wù)至邊緣服務(wù)器,符合實際車聯(lián)網(wǎng)場景下車載安全性業(yè)務(wù)的處理要求。同時其在迭代的過程中將更多的計算任務(wù)卸載至具有更多計算資源的邊緣服務(wù)器,而對計算資源較少的邊緣服務(wù)器減少計算任務(wù)的卸載,實現(xiàn)了邊緣服務(wù)器負(fù)載均衡。

4 結(jié)束語

本文提出基于遺傳算法的任務(wù)卸載策略GAOS,用于在負(fù)載不均的多MEC服務(wù)器車聯(lián)網(wǎng)中尋找最優(yōu)卸載策略,其能夠在有限次迭代后收斂,滿足實際車聯(lián)網(wǎng)場景下車載安全性業(yè)務(wù)的處理要求。仿真結(jié)果表明,在車聯(lián)網(wǎng)環(huán)境車載計算任務(wù)不斷增加的情況下,GAOS可實現(xiàn)邊緣服務(wù)器負(fù)載均衡,任務(wù)成功處理數(shù)量較Random和ALL-MEC策略分別增加了約30%和50%。下一步將設(shè)計部分卸載策略,將車載計算任務(wù)合理拆分一部分至MEC服務(wù)器,一部分則留在本地,從而在結(jié)合MEC服務(wù)的同時充分利用本地的計算資源。