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

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

0 概述

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

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

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

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

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

1 系統(tǒng)模型

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

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

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

1.1 通信模型

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

(1)

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

(2)

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

(3)

1.2 計(jì)算模型

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

(4)

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

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

(5)

(6)

(7)

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

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

(8)

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

1.2.3 計(jì)算資源分配

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

(9)

(10)

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

(11)

(12)

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

(13)

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

(14)

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

最終計(jì)算模型建模為:

max(P)

s.t.

C3:ej

(15)

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

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

2.1 問(wèn)題描述

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

2.2 編碼

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

M≥lbJ

(16)

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

(17)

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

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

2.3 初始化

初始化遺傳算法的相關(guān)參數(shù),包括最大的迭代次數(shù)I、染色體長(zhǎng)度N×M、變異概率pm、交叉概率pc、種群大小ps以及預(yù)留種群r。多數(shù)遺傳算法是隨機(jī)選擇初始種群,GAOS策略則結(jié)合了預(yù)定義染色體和隨機(jī)染色體算法進(jìn)行種群初始化。在預(yù)定義染色體過(guò)程中,將染色體中權(quán)重最高類(lèi),即車(chē)載安全類(lèi)的計(jì)算任務(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個(gè)計(jì)算任務(wù)被預(yù)定義,則剩余(N-Nc)個(gè)計(jì)算任務(wù)的編碼隨機(jī)生成,剩余(r-ps)個(gè)種群的染色體編碼隨機(jī)生成,維持種群的隨機(jī)性。

2.4 解集修復(fù)

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

(19)

(20)

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

(21)

以Nj表示卸載到服務(wù)器j的任務(wù)編號(hào),找到最小價(jià)值密度的計(jì)算任務(wù)并將其從MEC服務(wù)器隊(duì)列移除,再重新計(jì)算消耗的計(jì)算資源,重復(fù)該步驟,直至所有計(jì)算任務(wù)消耗的計(jì)算資源不超過(guò)MEC服務(wù)器總的計(jì)算資源。解集修復(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)化問(wèn)題的關(guān)鍵,其目標(biāo)函數(shù)如式(15)所示。因此,給出適應(yīng)度函數(shù)的計(jì)算公式為:

(22)

2.6 選擇操作

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

(23)

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

2.7 交叉操作

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

2.8 變異操作

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

3 仿真結(jié)果分析

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

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

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

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

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

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

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

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

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

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

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

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

(24)

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

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

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

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

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