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

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

0 引 言

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

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

假定所有車輛都在單行道路上以自身速度勻速前行，生成任務(wù)的車輛為源車輛，其余為協(xié)作車輛，沿車輛行駛方向有多個RSU。每個車輛可以通過GPS和自身傳感器與其它車輛和RSU進(jìn)行速度、位置、資源使用情況等狀態(tài)信息的實(shí)時共享，源車輛通過對這些狀態(tài)信息的分析來確定自身任務(wù)是否需要卸載、何時卸載以及卸載至何處。在進(jìn)行任務(wù)相關(guān)數(shù)據(jù)的傳輸時，車輛與RSU、RSU與RSU之間均通過移動無線通信網(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個RSU。對于可卸載任務(wù)，供其選擇的執(zhí)行位置有本地資源和代理資源(包括協(xié)作車輛和RSU)，建立所有資源集合p={p0,p1,p2,…,pM}， 其中p0為本地資源，p1～pM為代理資源。用ηim表示任務(wù)ni與資源pm的映射關(guān)系，當(dāng)ni在pm上執(zhí)行時ηim=1，否則ηim=0。

1.1 任務(wù)模型

圖2給出了一個具體的以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是車輛與車輛之間的通信。兩種通信模式都會隨著車輛的移動而發(fā)生通信鏈路的變化。

1.2.1 V2R通信模型

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

(1)

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

(2)

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

圖3 V2R通信模型

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

(3)

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

(4)

1.2.2 V2V通信模型

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

圖4 V2V通信模型

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

(5)

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

1.3 運(yùn)動模型

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

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

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

若vx

t1=0

(6)

(7)

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

(8)

若vx>vy， 則

t1=0

(9)

(10)

(11)

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

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

若vx>vy， 則

(12)

(13)

(14)

(15)

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

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

(16)

否則

(17)

(18)

1.4 時延模型

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

(19)

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

(20)

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

(21)

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

STi=0

(22)

(23)

(24)

CTi=STi+Tcal

(25)

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

(26)

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

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

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

圖6 ECTDP策略流程

2.1 可用資源的選擇

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

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

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

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

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

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

(2)建立空集合B

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

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

(5)BL(ni)=ci

(6)else

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

(8) 計算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)行表示一個任務(wù)的b-level值是該任務(wù)的節(jié)點(diǎn)權(quán)值、輸出邊權(quán)值與其后項(xiàng)任務(wù)中最大的b-level值三者之和。

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

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

(1)建立就緒任務(wù)集合RET、 可用資源池集合AP、 任務(wù)-資源映射集合TPM、 動態(tài)優(yōu)先級值集合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每個任務(wù)ni∈RETdo

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

(12)for每個資源pm∈APido

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

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

(15)endfor

(16)endfor

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

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

(19)endif

(20)endwhile

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

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

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

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

本文以單行道作為仿真場景，有一個源車輛，其生成一個任務(wù)流，沿車輛行駛方向有若干個RSU，滿足任務(wù)流的整個執(zhí)行過程可用。所有車輛初始位置都在第一個RSU覆蓋范圍內(nèi)，初始位置和車速在各自區(qū)間內(nèi)隨機(jī)產(chǎn)生，服從均勻分布。單個任務(wù)的計算量、數(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è)計與結(jié)果分析

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

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

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

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

(4)各個車輛按照運(yùn)動模型運(yùn)動；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2.4 單個任務(wù)計算量對任務(wù)流完成時間的影響

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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