林 峰,李 華,羅鋮文,朱智勤

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院,重慶 400065;2.重慶郵電大學(xué) 自動化學(xué)院,重慶 400065)

0 引 言

隨著車聯(lián)網(wǎng)的飛速發(fā)展,涌現(xiàn)了各種對延遲敏感的車載應(yīng)用,例如自動駕駛、自動導(dǎo)航、自然語言處理等應(yīng)用[1]。但是,現(xiàn)有計算資源和能耗受限的車輛無法充分滿足這些應(yīng)用對低延遲的要求。文獻(xiàn)[2]考慮了單移動邊緣計算(mobile edge computing,MEC)服務(wù)器多個用戶的情況,將任務(wù)卸載到MEC或者本地計算,以時延和能耗加權(quán)和最小化為目標(biāo),提出了一種二等分搜索方法來獲得最優(yōu)的卸載決策。文獻(xiàn)[3]提出了一種基于粒子群優(yōu)化算法(particle swarm optimization,PSO)的計算卸載策略,將計算任務(wù)卸載到本地和MEC進(jìn)行計算,平衡了時延與能耗,同時考慮了MEC服務(wù)器的負(fù)載均衡。文獻(xiàn)[4]使用MEC服務(wù)器+云端云服務(wù)器+本地的聯(lián)合卸載方式,提出了一種基于強(qiáng)化學(xué)習(xí)的無模型方法,考慮在能耗和任務(wù)的依賴關(guān)系約束下,最小化時延。文獻(xiàn)[5]考慮任務(wù)依賴的遷移方案,并使用基于改進(jìn)遺傳算法(genetic algorithm,GA)求解卸載決策,以最小化時延與能耗的加權(quán)和為目標(biāo),將計算任務(wù)卸載到本地、MEC服務(wù)器、遠(yuǎn)端云進(jìn)行計算。文獻(xiàn)[6]以優(yōu)化時延和能耗為目標(biāo),將多個用戶的計算任務(wù)卸載到多個MEC服務(wù)器,并且考慮計算任務(wù)之間依賴關(guān)系,基于改進(jìn)的遺傳算法提出了一種聯(lián)合卸載決策與任務(wù)調(diào)度算法。

現(xiàn)有研究較少關(guān)注依賴任務(wù)計算卸載與資源分配問題,且存在依賴任務(wù)模型覆蓋不全面、遠(yuǎn)端云服務(wù)器的計算卸載延遲大的限制;在考慮任務(wù)依賴關(guān)系時,大多考慮單個移動設(shè)備的依賴任務(wù),并沒有考慮多個車輛的依賴任務(wù)并發(fā)卸載,這與實際應(yīng)用具有很大的差別。少有研究將卸載決策、資源分配、MEC服務(wù)器的負(fù)載均綜合考慮,并且現(xiàn)有的計算資源也沒有得到充分的利用。因此,本文提出了面向依賴任務(wù)的聯(lián)合計算卸載及資源分配算法。首先,該算法考慮多個車輛的依賴任務(wù)同時卸載到多個計算平臺(車輛本地+MEC服務(wù)器+空閑協(xié)助車輛+遠(yuǎn)端云服務(wù)器),建立各個計算平臺的時延與能耗模型;其次,基于拍賣算法的競價思想,建立計算資源、通信資源的分配模型,根據(jù)負(fù)載狀態(tài),建立MEC服務(wù)器集群的負(fù)載均衡度模型;然后,構(gòu)造聯(lián)合優(yōu)化卸載決策、資源分配、負(fù)載均衡度的優(yōu)化問題;最后,結(jié)合粒子群算法收斂快與遺傳算法全局搜索強(qiáng)的特點,加入爬山搜索策略提高局部搜索能力,提出了自適應(yīng)粒子群遺傳混合算法對優(yōu)化問題求解。仿真結(jié)果表明,與其他算法對比,該算法具有良好的收斂性,能夠在滿足最大容忍時延的同時,降低系統(tǒng)總開銷,有效提升邊緣服務(wù)器集群的負(fù)載均衡度。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)拓?fù)淠Ｐ?/h3>

本文的系統(tǒng)模型如圖1所示。本文考慮將MEC服務(wù)器部署在路側(cè)單元(road side unit,RSU)上,不失一般性,定義在基站(base station,BS)的覆蓋范圍內(nèi)提供計算卸載服務(wù)的MEC服務(wù)器集合為M={m1,m2,…,mn,…,mm},需要進(jìn)行計算任務(wù)卸載的車輛集合為V={v1,v2,…,vi,…,vk},并且每個車輛都有一個計算密集型任務(wù)Si需要卸載,計算密集型任務(wù)集合為S={s1,s2,…,si,…,sk}。其中si是可拆分型任務(wù),包含若干個具有時序和數(shù)據(jù)雙重依賴關(guān)系的子任務(wù)。假設(shè)每個卸載車輛所在MEC服務(wù)器下都有一些空閑協(xié)助車輛提供計算卸載[7],每個MEC服務(wù)器mn擁有獨立的計算資源Fn和存儲資源Wn。本文在BS處設(shè)立調(diào)度服務(wù)器(dispatch server, DS),其作用是對BS覆蓋下的所有卸載車輛做統(tǒng)一的卸載決策、管理、協(xié)調(diào)其范圍內(nèi)所有MEC服務(wù)器的資源分配,以及BS的帶寬資源分配。計算卸載決策過程視為半動態(tài)的,在一個調(diào)度周期Δt內(nèi)即幾百毫秒內(nèi),車輛集合V和計算密集型任務(wù)集合S保持不變,但是在不同的調(diào)度周期內(nèi)集合V,S可能變化[8]。為了減少協(xié)同處理時延,RSU與RSU、RSU與BS、BS與遠(yuǎn)端云服務(wù)器之間使用光纖鏈路連接。車輛與車輛、車輛與RSU之間使用PC5通信,車輛與BS之間使用蜂窩網(wǎng)通信。

圖1 系統(tǒng)模型Fig.1 System model

圖2 依賴任務(wù)模型Fig.2 Dependent task model

本文將卸載車輛vi的計算密集型任務(wù)Si的每個子任務(wù)建模為十元組S(i,j)={j,I(i,j),O(i,j),U(i,j),Z(i,j),L(i,j),Y(i,j),K(i,j),Q(i,j),E(i,j)}。其中,j表示子任務(wù)的編號;I(i,j)表示子任務(wù)S(i,j)的數(shù)據(jù)量;O(i,j)=α·I(i,j)為輸出結(jié)果數(shù)據(jù)量,δ為輸出數(shù)據(jù)量系數(shù),表示輸出數(shù)據(jù)量與輸入數(shù)據(jù)量之間的關(guān)系;U(i,j)∈{0,1,2,3}表示子任務(wù)S(i,j)將要卸載的位置,0表示本地、1表示MEC服務(wù)器、2表示空閑協(xié)助車輛、3表示遠(yuǎn)端云服務(wù)器;Z(i,j)表示當(dāng)U(i,j)=1時所對應(yīng)的MEC服務(wù)器的編號,其他情況Z(i,j)=0;L(i,j)表示子任務(wù)S(i,j)從卸載車輛vi到計算位置U(i,j)的傳輸時延;Y(i,j)表示子任務(wù)S(i,j)在計算位置U(i,j)的計算時延與計算結(jié)果O(i,j)傳到下一個計算位置集合K(i,j)的時延;K(i,j)表示S(i,j)后驅(qū)子任務(wù)的計算位置的集合。

1.2 數(shù)據(jù)傳輸模型

(1)

(2)

(3)

2 基于雙重依賴任務(wù)的計算模型

2.1 本地計算模型

子任務(wù)S(i,j)卸載至本地執(zhí)行傳輸時延為

L(i,j)=0

(4)

子任務(wù)S(i,j)卸載至本地的計算時延為

(5)

為了后續(xù)表達(dá)式簡潔,令

(6)

ξ(i,j,σ)=min(δ(k(i,j)-σ),1),σ=0,1,2,3;

(7)

(8)

(7)式中,δ(t)是沖激函數(shù)。

本文考慮車輛是并行的,可以同時與空閑車輛、MEC服務(wù)器和BS通信,MEC服務(wù)器以及BS也可以并行通信。因此子任務(wù)S(i,j)的計算結(jié)果O(i,j)從本地車輛傳輸?shù)胶篁?qū)子任務(wù)計算位置集合K(i,j)的時延應(yīng)該取最大時延,即為

(9)

(10)

(11)

子任務(wù)S(i,j)在本地計算的計算時延與計算結(jié)果O(i,j)傳到后驅(qū)子任務(wù)計算位置集合K(i,j)的時延為

(12)

子任務(wù)S(i,j)卸載至本地計算的總能耗計算式為

(13)

(14)

2.2 MEC服務(wù)器計算模型

子任務(wù)S(i.j)從卸載車輛vi到mn服務(wù)器的傳輸通信時延計算式為

(15)

子任務(wù)S(i,j)在mn服務(wù)器的計算時延為

(16)

(16)式中,F(n,i)表示mn服務(wù)器分配給車輛vi的計算資源,單位為cycles/s。

子任務(wù)S(i,j)的計算結(jié)果O(i,j)從mn服務(wù)器傳輸?shù)胶篁?qū)子任務(wù)計算位置集合K(i,j)的時延為

(17)

(18)

子任務(wù)S(i,j)在mn服務(wù)器的計算時延與計算結(jié)果O(i,j)傳到后驅(qū)子任務(wù)計算位置集合K(i,j)的時延為

(19)

子任務(wù)S(i,j)卸載至mn服務(wù)器的總能耗計算式為

min(|δ(k(i,j)-1)·(q(i,j)-Z(i,j))|,1)·

(20)

(21)

2.3 空閑協(xié)助車輛計算模型

子任務(wù)S(i,j)從卸載車輛vi到空閑協(xié)助車輛的傳輸通信時延為

(22)

子任務(wù)S(i,j)在空閑協(xié)助車輛的計算時延為

(23)

子任務(wù)S(i,j)的計算結(jié)果O(i,j)從空閑協(xié)助車輛傳輸?shù)胶篁?qū)子任務(wù)計算位置集合K(i,j)的時延為

(24)

子任務(wù)S(i,j)在空閑協(xié)助車輛的計算時延與計算結(jié)果O(i,j)傳回到后驅(qū)子任務(wù)計算位置集合K(i,j)的時延為

(25)

子任務(wù)S(i,j)卸載至空閑協(xié)助車輛的總能耗計算式為

(26)

(27)

2.4 遠(yuǎn)端云服務(wù)器計算模型

子任務(wù)S(i,j)從卸載車輛vi到遠(yuǎn)端云服務(wù)器的傳輸通信時延為

(28)

子任務(wù)S(i,j)在遠(yuǎn)端云服務(wù)器的計算時延為

(29)

子任務(wù)S(i,j)的計算結(jié)果O(i,j)從遠(yuǎn)端云服務(wù)器傳輸?shù)胶篁?qū)任務(wù)計算位置集合K(i,j)的時延為

(30)

子任務(wù)S(i,j)在遠(yuǎn)端云服務(wù)器的計算時延與計算結(jié)果O(i,j)傳回到后驅(qū)任務(wù)計算位置集合K(i,j)的時延為

(31)

(32)

(33)

3 系統(tǒng)總開銷模型

本文是分布式的聯(lián)合計算任務(wù)卸載,并且子任務(wù)之間具有時序與數(shù)據(jù)的雙重依賴。在本研究中假設(shè)車輛是并發(fā)的卸載方式,總的時延不是簡單的各個子任務(wù)時延相加。因此,在考慮任務(wù)Si的總時延時,本文采用了關(guān)鍵路徑法(critical path method,CPM)[12],在本文中關(guān)鍵路徑就是時延最長的路徑,所有的路徑通過DAG圖的廣度優(yōu)先遍歷算法獲得。

假設(shè)車輛vi的任務(wù)Si的路徑集合為Pi={P(i,1),P(i,2),P(i,3),…,P(i,ρ)},總共有ρ個路徑。車輛vi的任務(wù)Si路徑P(i,ρ)的總時延為

(34)

因為所有不在本地計算的任務(wù)都需要卸載出去,所以這部分時延應(yīng)取傳輸?shù)組EC、空閑協(xié)助車輛、以及遠(yuǎn)端云服務(wù)器中最大的一個時延。而且任務(wù)之間具有依賴性,必須等前驅(qū)子任務(wù)執(zhí)行完并且把計算結(jié)果,傳到下一個子任務(wù)時才能開始執(zhí)行,所以在路徑p(i,ρ)上計算時延以及回傳時延應(yīng)該是相加。

車輛vi的任務(wù)Si的卸載總時延為Ti,總能耗為Ei,計算式為

Ti=max(T(i,1),T(i,2),T(i,3),…,T(i,ρ))

(35)

(36)

車輛集合V的所有計算密集型任務(wù)集合S的時延和,即系統(tǒng)總時延為T,總能耗為E,計算式為

(37)

(38)

系統(tǒng)總開銷為

H=βT+(1-β)E

(39)

(39)式中,β∈(0,1),為時延權(quán)重系數(shù);(1-β)為能耗權(quán)重系數(shù)?？筛鶕?jù)計算密集型任務(wù)的需求及車輛車載設(shè)備的狀態(tài)來設(shè)置β。例如,當(dāng)運行時延敏感型的計算服務(wù)時,可以適當(dāng)增加β的值。本文取β=0.8。

4 服務(wù)器資源分配與負(fù)載均衡模型

4.1 MEC服務(wù)器資源分配模型

調(diào)度服務(wù)器根據(jù)每個車輛卸載到各個MEC服務(wù)器的計算任務(wù)量,以及遠(yuǎn)端云服務(wù)器卸載量的情況,借鑒拍賣算法的競價思想,將計算資源、BS的帶寬資源分配給各個卸載車輛[13]。

車輛vi的任務(wù)Si對于mn服務(wù)器的計算資源競價為F(bn,i),mn服務(wù)器分配給車輛vi的計算資源為

(40)

(40)式中,a1表示計算資源請求量權(quán)值,a1=0.75;a2表示車輛的優(yōu)先級權(quán)值,a2=0.25。當(dāng)車輛vi處于mn服務(wù)器時,其優(yōu)先級會更高,這樣可以減少計算結(jié)果的回傳時延。

卸載到遠(yuǎn)端云服務(wù)器子任務(wù)越多的車輛應(yīng)該分到更多的帶寬資源,這樣可以減小傳輸通信時延,以及結(jié)果回傳時延。

車輛vi的任務(wù)Si對于mn服務(wù)器的存儲資源分配為

(41)

任務(wù)Si所有卸載到mn服務(wù)器的子任務(wù)必須先存儲,并且子任務(wù)的計算結(jié)果也需要存儲才能傳給后驅(qū)子任務(wù)。

4.2 MEC服務(wù)器負(fù)載均衡模型

在車聯(lián)網(wǎng)環(huán)境中,車輛的移動性造成MEC服務(wù)器下卸載車輛分布不均、MEC服務(wù)器的負(fù)載不均衡,不僅使得資源得不到充分的利用,也導(dǎo)致較差的QoE。所以在進(jìn)行卸載決策和資源分配時,考慮MEC服務(wù)器的負(fù)載均衡非常必要。

(42)

因此,mn服務(wù)器的負(fù)載為

(43)

(43)式中,α1+α2=1;α1表示對計算資源使用情況的重視程度;α2表示對內(nèi)存資源使用情況的重視程度。本研究對于計算資源與存儲資源的重視程度一樣,故α1=α2=0.5。

調(diào)度服務(wù)器下,MEC服務(wù)器集合為M={m1,m2,…,mn,…,mm},那么MEC服務(wù)器集群的負(fù)載集合為GM={G1,G2,…,Gn,…,Gm}。

MEC服務(wù)器集群的平均負(fù)載為

(44)

本文使用MEC服務(wù)器集群負(fù)載的標(biāo)準(zhǔn)差ω來表示集群的負(fù)載均衡度,表示為

(45)

ω越小,說明MEC服務(wù)器集群的負(fù)載均衡度越高;ω越大,說明MEC服務(wù)器集群的負(fù)載均衡度越低。

5 問題建模

在滿足每個車輛的計算密集型任務(wù)Si的依賴關(guān)系以及最大容忍時延和資源限制前提下,以最小化聯(lián)合卸載系統(tǒng)的總開銷和負(fù)載均衡度為目標(biāo),將系統(tǒng)的任務(wù)卸載和資源分配建模為

?i∈[1,k],?n∈[1,m]

?i∈[1,k]

O(i,j))]≤Wn,?n∈[1,m]

C6:U(i,j)∈{0,1,2,3},

Z(i,j),Q(i,j)∈{1,2,…,m},

K(i,j)∈{0,1,2,3},?i∈[1,k],

?j∈[1,xi]

(46)

(46)式中,μ表示系統(tǒng)的總開銷在目標(biāo)函數(shù)的權(quán)重,(1-μ)表示負(fù)載均衡度在目標(biāo)函數(shù)中的權(quán)重,如果系統(tǒng)傾向于系統(tǒng)開銷,可以增大μ值,相反,如果更看重MEC服務(wù)器集群的負(fù)載均衡度,可以減小μ值;K=[K1,K2,…,Ki,…,Kk]T為所有車輛的依賴任務(wù)的拓?fù)渑判蚓仃?K中的第i行對應(yīng)車輛vi的計算任務(wù)Si的拓?fù)渑判蛳蛄縆i。

6 算法設(shè)計

6.1 粒子和遺傳種群初始化

由目標(biāo)函數(shù)可知需要求解K、U、Z、F、W、B等6個矩陣。本文改進(jìn)PSO算法和GA算法的編碼方式,采用多矩陣編碼方式,編碼示意圖如圖3所示。粒子種群、遺傳種群分別由矩陣運算K·Z、U·Z、Z·Z、F·Z、W·Z、B·Z形成6個大的矩陣構(gòu)成。以N為種群大小,k為車輛數(shù)目,那么要獲得第i個粒子/染色體的編碼,只需要取出各個矩陣的對應(yīng)的(i-1)·k+1到i·k行,相關(guān)的操作也只需要操作對應(yīng)的行即可。

拓?fù)渑判蚓仃嘖·Z初始化是從車輛任務(wù)的所有拓?fù)渑判蛑须S機(jī)選擇一種,計算卸載決策矩陣U和MEC編號矩陣Z初始化取(0,1]的隨機(jī)數(shù),再映射為整數(shù),當(dāng)MEC服務(wù)器的數(shù)量n=3時的映射關(guān)系為

(47)

整個進(jìn)化過程主要針對計算卸載決策矩陣U和MEC編號矩陣Z,因為在確定了卸載決策之后,才能根據(jù)卸載結(jié)果優(yōu)化卸載的MEC服務(wù)器,進(jìn)行資源分配,使得MEC服務(wù)器負(fù)載均衡。

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

上述優(yōu)化模型是帶約束的最小化系統(tǒng)開銷和負(fù)載均衡度的模型,當(dāng)采用粒子群遺傳混合算法對其進(jìn)行優(yōu)化時,需要將約束問題轉(zhuǎn)化為非約束問題。因此,本文采用自適應(yīng)懲罰函數(shù)對目標(biāo)函數(shù)進(jìn)行約束處理。在進(jìn)行約束處理時,目標(biāo)函數(shù)中C1、C6約束在編碼時處理,C3、C4、C5在采用競價分配資源方式時必然滿足,所以只需要針對C2約束進(jìn)行懲罰,故適應(yīng)度函數(shù)為

(48)

(48)式中,Γ取值為1 000,因為負(fù)載均衡度很小,所以需要提高它在適應(yīng)度函數(shù)中的占比;c(ρ)為懲罰系數(shù),ρ為可行解的比例;fok為可行解;fsum表示解的總數(shù)。ρ與c(ρ)成反比關(guān)系,當(dāng)ρ越大時代表可行解增加,c(ρ)應(yīng)該減小。c(ρ)=0,表示為沒有當(dāng)前種群可行解;c(ρ)=1時,表示當(dāng)前種群全為可行解。在剛開始的迭代中,種群中可行解數(shù)量較少,此時懲罰系數(shù)應(yīng)較高,以引導(dǎo)搜索進(jìn)入可行域。隨著種群的進(jìn)化,種群中的可行解增多,懲罰系數(shù)則應(yīng)減小[14]。

6.3 粒子群算法和遺傳算法相關(guān)操作

6.3.1 粒子速度與位置更新

慣性權(quán)重較大使得粒子有較好的全局搜索能力,較小則有利于局部搜索。固定的慣性權(quán)重會陷入局部尋優(yōu),自適應(yīng)的慣性權(quán)重可以使粒子向最優(yōu)位置移動[15],自適應(yīng)慣性權(quán)重為

(49)

粒子的速度和位置更新公式為

vi(t)=wt·vi(t)+c1·rand[pi(t)-xi(t)]+

c2·rand[pg(t)-xi(t)]

xi(t+1)=xi(t)+vi(t)

(50)

(50)式中,c1、c2為學(xué)習(xí)因子;pi(t)、pg(t)分別為個體歷史最優(yōu)位置和種群全局最優(yōu)位置。

6.3.2 選擇交叉與變異操作

在GA算法中,交叉概率過小,在迭代過程中會影響種群的豐富度,導(dǎo)致收斂緩慢;過大則會影響優(yōu)良個體的遺傳。變異概率過小不容易產(chǎn)生新個體,影響種群多樣性;過大則會陷入局部最優(yōu)[17]。因此,本文采用自適應(yīng)的交叉概率和變異概率。種群的適應(yīng)度值較分散,說明種群比較豐富,交叉概率和變異概率應(yīng)該減小;反之,種群的適應(yīng)度值較集中,說明種群的豐富度不夠,交叉概率和變異概率應(yīng)該增大[18]。

自適應(yīng)交叉概率表示為

(51)

自適應(yīng)變異概率表示為

(52)

(51)—(52)式中,favg為當(dāng)前種群平均適應(yīng)度;fmax為當(dāng)前種群的最大適應(yīng)度;k1、k2為(0,1]的常數(shù)。

選擇和交叉操作采用單點部分映射交叉(partial-mapped crossover,PMX)與君主方案相結(jié)合的方式[19]。首先,對種群根據(jù)適應(yīng)度值進(jìn)行升序排列,用最優(yōu)的個體與所有偶數(shù)位置個體進(jìn)行交叉,每次交叉之后產(chǎn)生兩個新的個體;其次,對交叉后新產(chǎn)生的個體進(jìn)行變異操作產(chǎn)生子群體;然后,計算其適應(yīng)度值;最后,和父群體合并,并且根據(jù)適應(yīng)度值進(jìn)行升序排列,取前N個體為新的群體,進(jìn)行下一步的操作。

7 仿真實驗與結(jié)果分析

7.1 仿真參數(shù)設(shè)置

為了驗證本文算法的有效性,通過實驗與其他算法進(jìn)行對比,實驗仿真參數(shù)如表1[20]和表2所示

表1 PSO與GA算法相關(guān)參數(shù)Tab.1 PSO and GA algorithm related parameters

表2 仿真參數(shù)Tab.2 Simulation parameters

7.2 仿真結(jié)果分析

在本節(jié)中分別對Random算法、PSAO算法[3]、JODTS算法[6]、本文算法進(jìn)行仿真和對比。Random算法將依賴任務(wù)隨機(jī)卸載到本地、MEC服務(wù)器、空閑車輛、遠(yuǎn)端云服務(wù)器進(jìn)行計算。PSAO算法基于改進(jìn)的粒子群算法的卸載策略,將計算任務(wù)卸載到本地、MEC服務(wù)器進(jìn)行計算。JODTS算法基于改進(jìn)遺傳算法的卸載策略,將計算任務(wù)卸載到本地、MEC服務(wù)器進(jìn)行計算。

圖4展示了不同算法的收斂性能。圖4中k=8,n=3,計算任務(wù)量為4 Mbit。從圖4可以看到,本文算法收斂速度最快,大概迭代120次時收斂。PSAO的收斂度居中,大概迭代140多次時收斂。收斂最慢的是JODTS算法,大概迭代210多次時收斂;在全局尋優(yōu)上本文算法最好,其次是JODTS算法,最差的是PSAO算法。因為粒子群算法單向傳遞信息,而遺傳算法是雙向的,所以粒子群算法收斂比遺傳算法快,但是它容易陷入局部最優(yōu),因此其尋優(yōu)能力沒有遺傳算法強(qiáng)。本文算法結(jié)合兩個算法的優(yōu)點,并加入爬山搜索策略進(jìn)行局部二次搜索,使得全局尋優(yōu)能力、收斂性能都有所提高。

圖4 算法收斂性分析Fig.4 Convergence analysis of the algorithm

圖5展示了當(dāng)DS下車輛數(shù)和MEC服務(wù)器數(shù)量一定時,計算任務(wù)量對系統(tǒng)總開銷的影響。圖5中,k=8,n=3。從圖5可以看出,隨著計算任務(wù)量的增加,4種算法的系統(tǒng)總開銷也隨著增加;本文所提算法的系統(tǒng)總開銷最低,約是Random算法的49.15%、PSAO算法的68.10%、JODTS算法的87.62%。當(dāng)計算任務(wù)量超過12時,系統(tǒng)總開銷增幅明顯增大,這是因為計算任務(wù)量過大造成數(shù)據(jù)傳輸和回傳開銷,MEC的計算開銷也明顯加大。從圖5中還可以看到,采用本文算法時,平均每輛車的時延小于計算任務(wù)的最大時延,這說明本文算法能夠在滿足最大容忍時延的同時,最小化系統(tǒng)總開銷。

圖5 計算任務(wù)量對系統(tǒng)總開銷的影響Fig.5 Calculate the impact of task volume on total system overhead

圖6展示了在MEC服務(wù)器數(shù)量、計算任務(wù)量和在子任務(wù)個數(shù)一定的情況下,車輛數(shù)對負(fù)載均衡度的影響。圖6中,n=3,車輛計算任務(wù)量為6 Mbit,子任務(wù)數(shù)為10。從圖6可以看出,本文所提算法相比其他3種算法具有最小的負(fù)載均衡度,并且負(fù)載均衡度增幅是最小的,能有效均衡DS下MEC服務(wù)器的負(fù)載。

圖6 車輛數(shù)對MEC服務(wù)器負(fù)載均衡度的影響Fig.6 Impact of the number of vehicles on MEC server load balancing

圖7展示了車輛數(shù)對MEC服務(wù)器負(fù)載均衡度的影響。圖7中,k=8,n=3,車輛計算任務(wù)量為6 Mbit。從圖7可見,車輛個數(shù)、MEC服務(wù)器數(shù)和計算任務(wù)量一定時,系統(tǒng)總開銷隨著輸出數(shù)據(jù)量系數(shù)δ的增加而增加;對比其他3種算法,本文算法具有最小的系統(tǒng)總開銷且輸出數(shù)據(jù)量對系統(tǒng)總開銷的影響較小,這是因為輸出數(shù)據(jù)量比較小,而且本文中在MEC服務(wù)器之間、MEC與BS之間、BS與遠(yuǎn)端云服務(wù)器之間使用的是光纖,帶寬很大。

圖7 輸出數(shù)據(jù)量對系統(tǒng)總開銷的影響Fig.7 Impact of output data volume on total system overhead

8 結(jié)束語

為了解決子任務(wù)之間的時序和數(shù)據(jù)雙重依賴關(guān)系導(dǎo)致的依賴時延問題、車輛的移動性分布不均造成MEC服務(wù)器的負(fù)載不均衡問題,以及降低時延與能耗,本文提出了一種基于雙重依賴任務(wù)的聯(lián)合計算卸載及資源分配算法。本文考慮了多個車輛的依賴任務(wù)同時卸載到多個計算平臺的情況,提出了自適應(yīng)粒子群遺傳混合算法聯(lián)合優(yōu)化卸載決策、資源分配、負(fù)載均衡度。仿真實驗表明,本文算法能夠在滿足最大時延的同時,降低系統(tǒng)總開銷,提升邊緣服務(wù)器集群的負(fù)載均衡度。