基于最小完成時(shí)間的車載邊緣計(jì)算任務(wù)流卸載策略

李 波，晉士程，丁洪偉，武 浩

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

0 引 言

基于傳統(tǒng)云計(jì)算模式的車聯(lián)網(wǎng)(internet of vehicle，IoV)面對(duì)海量終端接入時(shí)會(huì)造成網(wǎng)絡(luò)擁塞，增加計(jì)算服務(wù)延遲[1]。而具備分布式、實(shí)時(shí)性和移動(dòng)性特點(diǎn)的移動(dòng)邊緣計(jì)算(mobile edge computing，MEC)[2,3]能夠就近為車輛提供所需計(jì)算服務(wù)，被認(rèn)為是一種有效降低車載任務(wù)時(shí)延的方案[4,5]。

在車載邊緣計(jì)算(vehicular edge computing，VEC)環(huán)境下，由于車輛的移動(dòng)性，車輛與周圍資源構(gòu)成的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)具有不穩(wěn)定性[6]。針對(duì)動(dòng)態(tài)變化的資源如何合理地進(jìn)行計(jì)算卸載是保證任務(wù)順利且高效執(zhí)行的關(guān)鍵。現(xiàn)有的研究通常利用車載自組織網(wǎng)將周邊車輛作為卸載資源，比如文獻(xiàn)[6-8]在VEC場(chǎng)景下，根據(jù)車輛的計(jì)算異質(zhì)性、機(jī)動(dòng)性，考慮車輛移動(dòng)性可能導(dǎo)致的服務(wù)中斷情況，為任務(wù)選擇合適的車輛節(jié)點(diǎn)進(jìn)行卸載。或是以路側(cè)單元(roadside unit，RSU)作為卸載資源，例如文獻(xiàn)[9-11]根據(jù)車輛移動(dòng)速度、RSU覆蓋范圍、計(jì)算和通信資源的變化等實(shí)際條件，為任務(wù)選擇最佳的RSU進(jìn)行卸載。盡管現(xiàn)有研究對(duì)于VEC環(huán)境下的卸載策略取得了一定進(jìn)展，但仍存在以下問題：①車輛應(yīng)用模型多為單任務(wù)、離散任務(wù)或串行任務(wù)模型，對(duì)于復(fù)雜任務(wù)流模型的研究較少。②多數(shù)研究對(duì)于資源的利用較為單一，僅以RSU或僅以車輛作為代理資源。因此，在動(dòng)態(tài)VEC環(huán)境下同時(shí)利用RSU和車輛作為代理資源，以最小完成時(shí)間為目標(biāo)實(shí)現(xiàn)復(fù)雜任務(wù)流的卸載，是本文研究的重點(diǎn)。對(duì)此，本文通過不同復(fù)雜度的任務(wù)流建模求解，以任務(wù)屬性和資源實(shí)時(shí)信息為依據(jù)對(duì)任務(wù)進(jìn)行合理的映射，使得最終卸載策略具有較廣泛的適用性。

1 系統(tǒng)模型

VEC體系主要由車輛攜帶的車載單元(on board unit，OBU)、RSU、邊緣服務(wù)器(edge server，ES)和蜂窩網(wǎng)的BS、WLAN接入點(diǎn)組成，形成可以實(shí)現(xiàn)車車互聯(lián)(vehicle to vehicle，V2V)、車路互聯(lián)(vehicle to roadside，V2R)的無線網(wǎng)絡(luò)系統(tǒng)[1]。其中，在V2R模式下，車輛可以通過無線網(wǎng)絡(luò)訪問部署在RSU上的ES[12]，獲取邊緣服務(wù)器的信息和計(jì)算資源。在V2V模式下，車輛之間組成車載自組織網(wǎng)實(shí)現(xiàn)車輛之間的信息共享。

假定所有車輛都在單行道路上以自身速度勻速前行，生成任務(wù)的車輛為源車輛，其余為協(xié)作車輛，沿車輛行駛方向有多個(gè)RSU。每個(gè)車輛可以通過GPS和自身傳感器與其它車輛和RSU進(jìn)行速度、位置、資源使用情況等狀態(tài)信息的實(shí)時(shí)共享，源車輛通過對(duì)這些狀態(tài)信息的分析來確定自身任務(wù)是否需要卸載、何時(shí)卸載以及卸載至何處。在進(jìn)行任務(wù)相關(guān)數(shù)據(jù)的傳輸時(shí)，車輛與RSU、RSU與RSU之間均通過移動(dòng)無線通信網(wǎng)絡(luò)進(jìn)行連接，車輛與車輛之間通過DSRC(dedicated short range communications)實(shí)現(xiàn)通信，系統(tǒng)架構(gòu)如圖1所示。

圖1 系統(tǒng)架構(gòu)

建立車輛集合V={V0,V1,…,VX}， 其中V0代表源車輛。建立RSU集合R={R1,R2,…,RY}，RY代表第Y個(gè)RSU。對(duì)于可卸載任務(wù)，供其選擇的執(zhí)行位置有本地資源和代理資源(包括協(xié)作車輛和RSU)，建立所有資源集合p={p0,p1,p2,…,pM}， 其中p0為本地資源，p1～pM為代理資源。用ηim表示任務(wù)ni與資源pm的映射關(guān)系，當(dāng)ni在pm上執(zhí)行時(shí)ηim=1，否則ηim=0。

1.1 任務(wù)模型

圖2給出了一個(gè)具體的以DAG表示的任務(wù)流示例，其中任務(wù)1是任務(wù)2的前項(xiàng)任務(wù)，任務(wù)3是任務(wù)2的后項(xiàng)任務(wù)。任務(wù)1和任務(wù)10分別為入口任務(wù)和出口任務(wù)，因而不可卸載。任務(wù)9需要獲取任務(wù)3、任務(wù)6和任務(wù)8的輸出結(jié)果才可以執(zhí)行。

圖2 DAG

1.2 通信模型

在VEC環(huán)境下，包括V2R和V2V的通信模式。其中，V2R是車輛與RSU之間的通信，V2V是車輛與車輛之間的通信。兩種通信模式都會(huì)隨著車輛的移動(dòng)而發(fā)生通信鏈路的變化。

1.2.1 V2R通信模型

V2R通信模型參考文獻(xiàn)[14]。假設(shè)d為車輛與RSU覆蓋范圍中心之間的距離，BVR為車輛與RSU之間的基礎(chǔ)帶寬，δ為路徑損耗因子，ε為信道衰落因子，P0為車輛的傳輸功率，N0為噪聲功率，根據(jù)香農(nóng)公式可以得出V2R模式的傳輸速率為

(1)

由于車輛始終處于運(yùn)動(dòng)狀態(tài)，d值時(shí)刻在變化。對(duì)于一個(gè)車輛而言，假設(shè)其剛好進(jìn)入RSU覆蓋邊緣作為起始點(diǎn)，行駛速度為v，忽略道路寬度，則t時(shí)刻的d值為

(2)

其中，rR為RSU的覆蓋半徑，l為RSU覆蓋范圍中心到道路的垂直距離，如圖3所示。

圖3 V2R通信模型

車輛與RSU之間的傳輸速率是時(shí)刻變化的，將平均上傳速率作為實(shí)際傳輸速率，則車輛在當(dāng)前RSU覆蓋范圍內(nèi)的V2R傳輸速率表示為

(3)

若車輛當(dāng)前處于Rx的覆蓋范圍，需要與Ry(x≠y) 通信，因?yàn)楦鱾€(gè)RSU的位置是固定的，兩個(gè)相鄰RSU之間的傳輸速率sRR視為固定值。設(shè)兩個(gè)RSU中間跳數(shù)為H，則此時(shí)通信速率為

(4)

1.2.2 V2V通信模型

單輛車可通信范圍是以rV為半徑的圓形區(qū)域，則車輛之間最大可通信距離為2rV。當(dāng)車距在最大可通信距離內(nèi)時(shí)，車輛之間以單跳的方式通信，如圖4中的車輛A和車輛B。當(dāng)車距超過2rV時(shí)，車輛之間不能直接通信，需要將其它可通信車輛作為中繼點(diǎn)，以多跳的方式進(jìn)行通信，如圖4中車輛A和車輛C之間的跳數(shù)為2。

圖4 V2V通信模型

兩車之間通信速率表示如下

(5)

其中，BV2V是車載自組織網(wǎng)中的基礎(chǔ)帶寬，HM代表車輛之間通信的跳數(shù)。

1.3 運(yùn)動(dòng)模型

圖5 兩車初始位置通信狀態(tài)

對(duì)于圖5(a)所示情況：

若vx=vy， 則兩車始終可以通信；

若vx

t1=0

(6)

(7)

車輛Vx和Vy的可用通信總時(shí)長ΔtVxVy為

(8)

若vx>vy， 則

t1=0

(9)

(10)

(11)

對(duì)于圖5(b)所示情況：

若vx≤vy， 則兩車始終不可通信；

若vx>vy， 則

(12)

(13)

(14)

(15)

而對(duì)于V2R的通信，車輛Vx在第y個(gè)RSU覆蓋范圍內(nèi)與Ry的可通信總時(shí)長ΔtVxRy為：

若當(dāng)前RSU是車輛初始連接的RSU，則

(16)

否則

(17)

(18)

1.4 時(shí)延模型

將資源pm和pn之間的通信速率表示為rmn，對(duì)于同一資源，其內(nèi)部傳輸速率設(shè)為無窮大，即相同資源上傳輸數(shù)據(jù)所需時(shí)長為0。則將一個(gè)任務(wù)ni卸載所需時(shí)長為

(19)

當(dāng)資源pm的計(jì)算能力為fm時(shí)，執(zhí)行計(jì)算所需時(shí)長為

(20)

待任務(wù)ni計(jì)算完成后將計(jì)算結(jié)果發(fā)送至nj所需傳輸時(shí)長為

(21)

若任務(wù)ni為入口任務(wù)，其開始執(zhí)行的時(shí)刻STi和執(zhí)行結(jié)束的時(shí)刻CTi分別為

STi=0

(22)

(23)

(24)

CTi=STi+Tcal

(25)

為任務(wù)流中的每個(gè)任務(wù)尋找最優(yōu)卸載決策，其中包括是否卸載、何時(shí)卸載以及映射資源，目的是使得整個(gè)任務(wù)流的完成時(shí)間，即出口任務(wù)的結(jié)束時(shí)間最小，本文優(yōu)化目標(biāo)和約束條件表達(dá)如下

(26)

其中，約束條件C1表示一個(gè)任務(wù)只能在一個(gè)資源上執(zhí)行，C2表示一個(gè)資源不能同時(shí)執(zhí)行多個(gè)任務(wù)，C3表示任意兩個(gè)連通的任務(wù)之間的依賴關(guān)系呈因果性。

2 卸載調(diào)度策略

任務(wù)的卸載與調(diào)度屬于組合優(yōu)化問題，而組合優(yōu)化問題屬于NP完全問題。面對(duì)任務(wù)間的約束關(guān)系和動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，本文提出了一種基于動(dòng)態(tài)優(yōu)先級(jí)的最早完成時(shí)間的卸載策略ECTDP(earliest completion time based on dynamic priority)，該策略可分為兩個(gè)步驟：可用資源的選擇、任務(wù)-資源的映射，主要思路流程如圖6所示。

圖6 ECTDP策略流程

2.1 可用資源的選擇

由于車輛移動(dòng)性會(huì)導(dǎo)致資源之間的通信鏈路發(fā)生變化，為了保證前項(xiàng)任務(wù)與后項(xiàng)任務(wù)之間的順利傳輸以及源車輛將任務(wù)完整地卸載至目標(biāo)資源，可靠的通信鏈路至關(guān)重要。此外，當(dāng)一個(gè)任務(wù)有多個(gè)前項(xiàng)任務(wù)，資源的異構(gòu)性和移動(dòng)性必然導(dǎo)致這些前項(xiàng)任務(wù)在全部完成時(shí)，互相存在時(shí)間和空間上的跨度，而這種時(shí)空上的差異是影響后項(xiàng)任務(wù)執(zhí)行狀況的又一重要因素。因此，需要對(duì)一個(gè)任務(wù)的可用卸載資源進(jìn)行篩選。所有車輛在單行道中勻速前行，因而每個(gè)車輛在每個(gè)時(shí)刻的位置都可以預(yù)測(cè)得知，以此作為解決問題的依據(jù)。在通信上，選擇在傳輸期間通信鏈路穩(wěn)定無變化的資源；在時(shí)間上，采用即執(zhí)行完即傳輸?shù)姆绞?，?shí)現(xiàn)時(shí)間的不間斷利用和重疊利用；在空間上，為避免空間跨度過大，以源車輛的位置為準(zhǔn)對(duì)周邊資源進(jìn)行選擇，形成一個(gè)隨源車輛移動(dòng)且覆蓋范圍動(dòng)態(tài)變化的可選區(qū)域。當(dāng)一個(gè)任務(wù)nj已執(zhí)行完畢，對(duì)其后項(xiàng)任務(wù)ni卸載資源的選擇有以下3類：

(1)nj在源車輛V0上執(zhí)行，ni的可用資源有：

(2)nj在協(xié)作車輛Vx(x≠0) 上執(zhí)行，ni的可用資源有：

(3)nj在Rx上執(zhí)行，ni的可用資源有：

綜上，當(dāng)任務(wù)ni有多個(gè)前項(xiàng)任務(wù)時(shí)，每個(gè)前項(xiàng)任務(wù)基于上述3種情況進(jìn)行可用卸載資源的選擇，所有前項(xiàng)任務(wù)所選資源交集即為任務(wù)ni的可用卸載資源池。若無交集，說明當(dāng)所有前項(xiàng)任務(wù)完成時(shí)，至少兩個(gè)前項(xiàng)任務(wù)所選的RSU不同，此時(shí)僅以其中距離位置原點(diǎn)最遠(yuǎn)的RSU作為可用卸載資源池。

2.2 任務(wù)-資源映射

當(dāng)一個(gè)任務(wù)的所有前項(xiàng)任務(wù)全部執(zhí)行完畢，則該任務(wù)就緒。對(duì)于復(fù)雜任務(wù)流，同一時(shí)間可能有多個(gè)任務(wù)就緒。面對(duì)就緒任務(wù)的不斷更新以及網(wǎng)絡(luò)拓?fù)涞膭?dòng)態(tài)變化，為了使任務(wù)流順利執(zhí)行且用時(shí)最短，合適的資源-任務(wù)映射關(guān)系尤為重要。僅將計(jì)算能力較強(qiáng)或通信速率快的資源作為任務(wù)的卸載目標(biāo)較為片面，因?yàn)閷?shí)際執(zhí)行中各個(gè)資源的狀態(tài)不同。另外，當(dāng)多個(gè)無依賴關(guān)系的任務(wù)就緒，在有限的資源下，任務(wù)的調(diào)度順序也是需要面臨的問題。對(duì)此本文以任務(wù)在資源中的實(shí)際執(zhí)行情況為依據(jù)進(jìn)行映射。

在進(jìn)行任務(wù)-資源的映射之前，首先根據(jù)任務(wù)之間的依賴關(guān)系，計(jì)算每個(gè)任務(wù)的b-level(bottom level)，即任務(wù)到出口任務(wù)的最長路徑長度，該值能夠體現(xiàn)單個(gè)任務(wù)對(duì)整個(gè)任務(wù)流影響的重要程度，具體算法如下：

算法1：計(jì)算任務(wù)b-level值算法

(1)以任務(wù)流的逆向拓?fù)漤樞蚪⑷蝿?wù)節(jié)點(diǎn)列表List， 設(shè)任務(wù)ni的b-level值為BL(ni)

(2)建立空集合B

(3)for每個(gè)任務(wù)ni∈Listdo

(4)ifni是出口任務(wù)then

(5)BL(ni)=ci

(6)else

(7)for每個(gè)任務(wù)nj∈sub(ni)do

(8) 計(jì)算BL(nj)+ci+mi的值， 并將該值放置集合B

(9)endfor

(10)BL(ni)為集合B的最大值

(11) 令B=?

(12)endif

(13)endfor

算法1中第(5)行代表出口任務(wù)的b-level值是其自身的節(jié)點(diǎn)權(quán)值。第(7)行至第(10)行表示一個(gè)任務(wù)的b-level值是該任務(wù)的節(jié)點(diǎn)權(quán)值、輸出邊權(quán)值與其后項(xiàng)任務(wù)中最大的b-level值三者之和。

對(duì)于每個(gè)就緒任務(wù)，在其自身的可用卸載資源池中，按照1.4節(jié)給出的時(shí)延模型計(jì)算在各個(gè)資源上的完成時(shí)間，并計(jì)算該任務(wù)的b-level與各完成時(shí)間的差值。該值體現(xiàn)任務(wù)自身屬性與資源實(shí)際執(zhí)行情況的匹配程度，以此作為評(píng)價(jià)各個(gè)任務(wù)優(yōu)先級(jí)的標(biāo)準(zhǔn)，可以起到綜合考慮且自適應(yīng)動(dòng)態(tài)變化的作用，具體算法如下：

算法2：ECTDP策略調(diào)度算法

(1)建立就緒任務(wù)集合RET、 可用資源池集合AP、 任務(wù)-資源映射集合TPM、 動(dòng)態(tài)優(yōu)先級(jí)值集合DP

(2)初始化RET={nentry}，AP=?，TPM=?，DP=?

(4)whileRET≠?do

(5)ifRET={nexit}then

(6) 將nexit放在本地執(zhí)行

(7) 將nexit從RET中剔除

(8)else

(9)DP=?

(10)for每個(gè)任務(wù)ni∈RETdo

(11) 尋找ni自身可用資源池APi

(12)for每個(gè)資源pm∈APido

(13) 計(jì)算ni在資源pm上的完成時(shí)間CTi,m

(14) 計(jì)算DP(ni，pm)=BL(ni)-CTi,m

(15)endfor

(16)endfor

(17) 取DP(ni，pm)值最大的任務(wù)-資源對(duì)， 將ni卸載至pm， 更新TPM

(18) 將ni從RET中剔除， 更新Tmprepare和RET

(19)endif

(20)endwhile

算法2中第(14)行所得動(dòng)態(tài)優(yōu)先級(jí)值可能為正數(shù)、負(fù)數(shù)或0，但始終選擇值最大的作為優(yōu)先映射。當(dāng)ni執(zhí)行完畢，其后項(xiàng)任務(wù)中可能部分已就緒，此時(shí)第(18)行更新RET的操作包括加入新的就緒任務(wù)，將與舊的就緒任務(wù)同時(shí)參與下一輪迭代的對(duì)比。

3 實(shí)驗(yàn)仿真

本文以整個(gè)任務(wù)流的完成時(shí)間作為性能指標(biāo)(式(26))，分別以任務(wù)數(shù)、任務(wù)流最大出度、單個(gè)任務(wù)計(jì)算量、單個(gè)任務(wù)數(shù)據(jù)量、協(xié)作車輛數(shù)量作為實(shí)驗(yàn)變量，在不同環(huán)境下與3種基準(zhǔn)卸載策略進(jìn)行對(duì)比，包括不卸載(local computing，LC)，全部卸載至RSU(full offloading to RSU，F(xiàn)OR)，以距離源車輛最近且能通信的單個(gè)車輛作為卸載資源進(jìn)行部分卸載(some part offloading，SPO)[15]。

3.1 參數(shù)設(shè)置

本文以單行道作為仿真場(chǎng)景，有一個(gè)源車輛，其生成一個(gè)任務(wù)流，沿車輛行駛方向有若干個(gè)RSU，滿足任務(wù)流的整個(gè)執(zhí)行過程可用。所有車輛初始位置都在第一個(gè)RSU覆蓋范圍內(nèi)，初始位置和車速在各自區(qū)間內(nèi)隨機(jī)產(chǎn)生，服從均勻分布。單個(gè)任務(wù)的計(jì)算量、數(shù)據(jù)量和輸出結(jié)果的數(shù)據(jù)量也在各自取值范圍內(nèi)隨機(jī)產(chǎn)生，服從均勻分布?；A(chǔ)參數(shù)設(shè)置見表1[14]。

表1 參數(shù)設(shè)置

3.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

首先以上述參數(shù)進(jìn)行基準(zhǔn)實(shí)驗(yàn)，然后僅改變?nèi)蝿?wù)數(shù)、任務(wù)流最大出度、單個(gè)任務(wù)計(jì)算量、單個(gè)任務(wù)數(shù)據(jù)量、協(xié)作車輛數(shù)量這些因素中的其中一個(gè)，保持其余不變，利用控制變量法進(jìn)行多組對(duì)比實(shí)驗(yàn)。對(duì)于每組參數(shù)的實(shí)驗(yàn)過程如下：

(1)初始化車輛數(shù)量、速度和位置，設(shè)定環(huán)境參數(shù)，生成仿真環(huán)境；

(2)根據(jù)任務(wù)數(shù)、最大出度、計(jì)算量和數(shù)據(jù)量隨機(jī)生成一個(gè)任務(wù)流；

(3)設(shè)置資源屬性參數(shù)，生成資源模型；

(4)各個(gè)車輛按照運(yùn)動(dòng)模型運(yùn)動(dòng)；

(5)根據(jù)每個(gè)任務(wù)完成時(shí)刻，實(shí)時(shí)更新各個(gè)車輛的位置以及所有資源的使用情況；

(6)依照不同策略進(jìn)行卸載；

(7)待該任務(wù)流執(zhí)行完成，記錄當(dāng)前參數(shù)下各策略的任務(wù)流完成時(shí)間;

(8)重復(fù)(1)到(7)過程，進(jìn)行1000次仿真，求出各個(gè)策略完成時(shí)間的平均值作為該組實(shí)驗(yàn)結(jié)果。

3.2.1 基準(zhǔn)實(shí)驗(yàn)

為了綜合評(píng)價(jià)各卸載策略的優(yōu)劣性，以基礎(chǔ)參數(shù)作為經(jīng)典仿真場(chǎng)景進(jìn)行基準(zhǔn)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖7所示。

圖7 基準(zhǔn)實(shí)驗(yàn)結(jié)果對(duì)比

由圖7可知，SPO策略比LC策略更優(yōu)，因?yàn)镾PO可以利用周邊單個(gè)協(xié)作車輛進(jìn)行分布式計(jì)算，相比完全在本地串行執(zhí)行更節(jié)省時(shí)間。FOR策略比SPO策略更優(yōu)，是因?yàn)镕OR可以充分利用邊緣端較強(qiáng)的計(jì)算能力，縮短了每個(gè)任務(wù)的計(jì)算時(shí)間。而ECTDP策略最優(yōu)，是因?yàn)樵摬呗詫SU和協(xié)作車輛作為選擇目標(biāo)，計(jì)算資源的形式不再單一，充分利用邊緣端強(qiáng)大的計(jì)算能力和車載自組織網(wǎng)的分布式計(jì)算，實(shí)現(xiàn)V2V和V2R兩種通信模式的優(yōu)勢(shì)互補(bǔ)、相互延伸。此外，在進(jìn)行資源選擇時(shí)以通信鏈路的穩(wěn)定和減小時(shí)空跨度為核心思想，避免了通信鏈路的變化造成的計(jì)算切換和等待，增大了時(shí)間的利用率，降低任務(wù)間的傳輸時(shí)間。

具體而言，在ECTDP策略進(jìn)行任務(wù)-資源映射時(shí)，單個(gè)任務(wù)的b-level值體現(xiàn)該任務(wù)對(duì)整個(gè)任務(wù)流的影響程度，是任務(wù)自身屬性的呈現(xiàn)。任務(wù)在各資源上的完成時(shí)間體現(xiàn)了在各種因素影響下的任務(wù)實(shí)際執(zhí)行情況，是資源實(shí)際狀態(tài)的呈現(xiàn)。將兩者的差值作為調(diào)度任務(wù)的標(biāo)準(zhǔn)，是考慮了任務(wù)和資源的各方面因素后的綜合評(píng)價(jià)，體現(xiàn)了任務(wù)與資源的實(shí)際匹配程度。優(yōu)先選擇差值最大的任務(wù)-資源對(duì)，能夠最大程度縮短單個(gè)任務(wù)的完成時(shí)間并且對(duì)任務(wù)流整體造成的影響最大。因此，ECTDP策略可以大大降低任務(wù)流的完成時(shí)間，相比LC、SPO和FOR策略分別縮短了60.24%、41.75%和34.14%。

3.2.2 任務(wù)數(shù)對(duì)任務(wù)流完成時(shí)間的影響

將任務(wù)數(shù)分別設(shè)為10、30、40和50進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖8所示。

圖8 不同任務(wù)數(shù)的任務(wù)流完成時(shí)間

由圖8可以看出，任務(wù)數(shù)越多，執(zhí)行任務(wù)流越耗時(shí)。這是因?yàn)槿蝿?wù)流的規(guī)模越大，整個(gè)任務(wù)流中需要計(jì)算和傳輸?shù)臄?shù)據(jù)也隨之增加，為方便描述，將任務(wù)流中總的計(jì)算量和數(shù)據(jù)量統(tǒng)稱為總工作量。由于總工作量是由多個(gè)子任務(wù)的相關(guān)量線性疊加而得，因此總工作量與總?cè)蝿?wù)數(shù)近似呈線性正相關(guān)。而在有限的資源下，執(zhí)行任務(wù)流所需時(shí)長也與總工作量近似呈線性正相關(guān)。故而隨著任務(wù)數(shù)的增多，任務(wù)流的完成時(shí)間呈近似線性上升。此時(shí)FOR策略雖優(yōu)于SPO策略，然兩者差距始終較小。這是因?yàn)镕OR利用邊緣端的較強(qiáng)計(jì)算能力，相對(duì)于SPO能夠節(jié)省任務(wù)的計(jì)算時(shí)間，但FOR的全部卸載又導(dǎo)致過多的通信開銷。

此外，在當(dāng)前的參數(shù)環(huán)境下，全部卸載使得節(jié)省的計(jì)算時(shí)間微大于額外的通信開銷，兩者綜合作用下導(dǎo)致FOR相對(duì)于SPO的優(yōu)勢(shì)不明顯。對(duì)于不同的任務(wù)數(shù)，ECTDP都可以在計(jì)算開銷與通信開銷之間以及任務(wù)與資源的供求關(guān)系上做出均衡，因而面對(duì)不同規(guī)模的任務(wù)流，其完成時(shí)間始終最短，相比LC、SPO和FOR策略平均縮短了63.12%，45.82%和39.14%。

3.2.3 任務(wù)流最大出度對(duì)任務(wù)流完成時(shí)間的影響

將任務(wù)流的最大出度分別設(shè)為總?cè)蝿?wù)數(shù)的20%、40%、60%和80%進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖9所示。

圖9 不同最大出度的任務(wù)流完成時(shí)間

由圖9可知，隨著任務(wù)流最大出度的增大，LC和FOR策略不受影響，而SPO和ECTDP會(huì)有輕微的上升變化。因?yàn)槿蝿?wù)流的最大出度決定了一個(gè)任務(wù)所能連接的最多后項(xiàng)任務(wù)的數(shù)量，當(dāng)最大出度值增大時(shí)，任務(wù)流的復(fù)雜度增大。此時(shí)任務(wù)流內(nèi)部的傳輸增多，單個(gè)任務(wù)會(huì)有更多前項(xiàng)任務(wù)，其開始執(zhí)行時(shí)間受影響因素較多，推遲執(zhí)行的可能性增大。LC和FOR策略將任務(wù)集中在單個(gè)資源上執(zhí)行，資源內(nèi)部傳輸時(shí)長為0，因而不受影響。但SPO和ECTDP策略需要在不同資源上執(zhí)行，資源之間有一定的傳輸時(shí)長。然而任務(wù)流中單個(gè)任務(wù)的輸出結(jié)果量往往比較小，而且傳輸結(jié)果數(shù)據(jù)采用并行傳輸，不考慮通信競(jìng)爭(zhēng)，因此最大出度的變化對(duì)整個(gè)任務(wù)流的完成時(shí)間影響較小。但在不同出度的影響下，ECTDP策略始終是完成時(shí)間最短的，相比LC、SPO和FOR策略平均縮短了57.66%，40.70%和30.32%。

3.2.4 單個(gè)任務(wù)計(jì)算量對(duì)任務(wù)流完成時(shí)間的影響

將單個(gè)任務(wù)的計(jì)算量分別設(shè)定為(0,2]、(4,6]、(6,8]和(8,10](×108cycle)進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖10所示。

圖10 不同計(jì)算量的任務(wù)流完成時(shí)間

由圖10可得，隨著單個(gè)任務(wù)計(jì)算量的增加，整個(gè)任務(wù)流所需計(jì)算的數(shù)據(jù)增多，因此完成任務(wù)流所需時(shí)長會(huì)隨之上升。相比實(shí)驗(yàn)3.2.2，可以看出當(dāng)前實(shí)驗(yàn)參數(shù)下的FOR策略與SPO策略之間的差距逐漸增大。這是因?yàn)镕OR策略的優(yōu)勢(shì)在于所選資源的計(jì)算能力較強(qiáng)，當(dāng)只增加計(jì)算量不改變數(shù)據(jù)量時(shí)，節(jié)省的計(jì)算時(shí)間與額外通信開銷的比值增大，F(xiàn)OR策略的優(yōu)勢(shì)也逐漸明顯。而ECTDP策略在面對(duì)較大計(jì)算量的任務(wù)時(shí)，會(huì)通過分布式計(jì)算和卸載至計(jì)算能力較強(qiáng)的資源這兩種方式對(duì)計(jì)算時(shí)間進(jìn)行節(jié)省，使得任務(wù)流總完成時(shí)間最小，相比LC、SPO和FOR策略平均縮短了59.74%,43.18%和34.06%。

3.2.5 單個(gè)任務(wù)數(shù)據(jù)量對(duì)任務(wù)流完成時(shí)間的影響

將單個(gè)任務(wù)的數(shù)據(jù)量分別設(shè)定為(10,20]、(20,30]、(30,40]、(40,50](MB)進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖11所示。

圖11 不同數(shù)據(jù)量的任務(wù)流完成時(shí)間

由圖11可知，單個(gè)任務(wù)數(shù)據(jù)量的增加對(duì)LC策略無影響，而對(duì)于涉及到卸載的其余3種策略有影響，會(huì)增加它們的通信時(shí)長從而使得完成時(shí)間有所增長。其中FOR策略隨著數(shù)據(jù)量的增加，逐漸成為性能最差的策略。因?yàn)楫?dāng)只增大數(shù)據(jù)量不改變計(jì)算量時(shí)，節(jié)省的計(jì)算時(shí)間與額外通信開銷的比值減小，此時(shí)FOR的劣勢(shì)會(huì)被放大。而部分卸載的SPO和ECTDP，會(huì)根據(jù)卸載量的大小進(jìn)行判斷，可以將卸載量大的任務(wù)留在本地執(zhí)行，減少通信開銷。其中ECTDP面對(duì)多個(gè)可卸載資源時(shí)能夠動(dòng)態(tài)地調(diào)節(jié)任務(wù)的調(diào)度順序，在最大程度利用并行計(jì)算和減少通信開銷之間進(jìn)行權(quán)衡，以實(shí)現(xiàn)最佳的綜合效果，相比LC、SPO和FOR策略平均縮短了50.56%，33.57%和44.16%。

3.2.6 協(xié)作車輛數(shù)量對(duì)任務(wù)流完成時(shí)間的影響

將協(xié)作車輛的數(shù)量從1增加至10進(jìn)行對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖12所示。

圖12 不同協(xié)作車輛數(shù)量的任務(wù)流完成時(shí)間

由圖12可以看出，協(xié)作車輛數(shù)量的變化對(duì)LC和FOR策略無影響，因?yàn)檫@兩個(gè)策略的執(zhí)行與協(xié)作車輛無關(guān)。FOR和ECTDP策略會(huì)隨著協(xié)作車輛的增多先減少執(zhí)行時(shí)間，再趨于平穩(wěn)。這是因?yàn)閰f(xié)作車輛的增加使道路內(nèi)交通密度變大，源車輛能夠連接到其它車輛的可能性變大，即增大了并行計(jì)算的可能性，從而縮短完成時(shí)間。然而此時(shí)任務(wù)流的最大出度為6，即同時(shí)就緒的可并行計(jì)算的任務(wù)最多為6個(gè)。因此隨著協(xié)作車輛的繼續(xù)增多，可用資源對(duì)于任務(wù)是一種供大于求的過飽和狀態(tài)，使得任務(wù)流的完成時(shí)間不再有明顯變化，從而趨于平穩(wěn)。ECTDP策略受協(xié)作車輛影響的波動(dòng)比SPO策略小，這是因?yàn)榍罢叱藚f(xié)作車輛還可以將RSU作為卸載資源，充分利用邊緣端的強(qiáng)大計(jì)算資源。ECTDP相比LC、SPO和FOR策略平均縮短了60.03%，42.65%和34.47%。

4 結(jié)束語

本文針對(duì)車載邊緣計(jì)算環(huán)境中的復(fù)雜任務(wù)流卸載進(jìn)行了研究，考慮了任務(wù)依賴關(guān)系、車輛的移動(dòng)性、資源的異構(gòu)性、資源的使用狀況以及通信網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化等因素，提出了一種基于動(dòng)態(tài)優(yōu)先級(jí)的卸載策略，充分的實(shí)驗(yàn)表明，本文提出的策略相較于其它策略性能始終最優(yōu)。在未來的研究中，將重點(diǎn)研究車載邊緣環(huán)境中在滿足任務(wù)流完成時(shí)間最小的同時(shí)降低源車輛的能耗開銷，實(shí)現(xiàn)卸載策略的多目標(biāo)優(yōu)化。