基于最小完成時間的車載邊緣計算任務流卸載策略

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

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

0 引 言

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

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

1 系統模型

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

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

圖1 系統架構

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

1.1 任務模型

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

圖2 DAG

1.2 通信模型

在VEC環境下，包括V2R和V2V的通信模式。其中，V2R是車輛與RSU之間的通信，V2V是車輛與車輛之間的通信。兩種通信模式都會隨著車輛的移動而發生通信鏈路的變化。

1.2.1 V2R通信模型

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

(1)

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

(2)

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

圖3 V2R通信模型

車輛與RSU之間的傳輸速率是時刻變化的，將平均上傳速率作為實際傳輸速率，則車輛在當前RSU覆蓋范圍內的V2R傳輸速率表示為

(3)

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

(4)

1.2.2 V2V通信模型

單輛車可通信范圍是以rV為半徑的圓形區域，則車輛之間最大可通信距離為2rV。當車距在最大可通信距離內時，車輛之間以單跳的方式通信，如圖4中的車輛A和車輛B。當車距超過2rV時，車輛之間不能直接通信，需要將其它可通信車輛作為中繼點，以多跳的方式進行通信，如圖4中車輛A和車輛C之間的跳數為2。

圖4 V2V通信模型

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

(5)

其中，BV2V是車載自組織網中的基礎帶寬，HM代表車輛之間通信的跳數。

1.3 運動模型

圖5 兩車初始位置通信狀態

對于圖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覆蓋范圍內與Ry的可通信總時長ΔtVxRy為：

若當前RSU是車輛初始連接的RSU，則

(16)

否則

(17)

(18)

1.4 時延模型

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

(19)

當資源pm的計算能力為fm時，執行計算所需時長為

(20)

待任務ni計算完成后將計算結果發送至nj所需傳輸時長為

(21)

若任務ni為入口任務，其開始執行的時刻STi和執行結束的時刻CTi分別為

STi=0

(22)

(23)

(24)

CTi=STi+Tcal

(25)

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

(26)

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

2 卸載調度策略

任務的卸載與調度屬于組合優化問題，而組合優化問題屬于NP完全問題。面對任務間的約束關系和動態變化的網絡拓撲結構，本文提出了一種基于動態優先級的最早完成時間的卸載策略ECTDP(earliest completion time based on dynamic priority)，該策略可分為兩個步驟：可用資源的選擇、任務-資源的映射，主要思路流程如圖6所示。

圖6 ECTDP策略流程

2.1 可用資源的選擇

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

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

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

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

綜上，當任務ni有多個前項任務時，每個前項任務基于上述3種情況進行可用卸載資源的選擇，所有前項任務所選資源交集即為任務ni的可用卸載資源池。若無交集，說明當所有前項任務完成時，至少兩個前項任務所選的RSU不同，此時僅以其中距離位置原點最遠的RSU作為可用卸載資源池。

2.2 任務-資源映射

當一個任務的所有前項任務全部執行完畢，則該任務就緒。對于復雜任務流，同一時間可能有多個任務就緒。面對就緒任務的不斷更新以及網絡拓撲的動態變化，為了使任務流順利執行且用時最短，合適的資源-任務映射關系尤為重要。僅將計算能力較強或通信速率快的資源作為任務的卸載目標較為片面，因為實際執行中各個資源的狀態不同。另外，當多個無依賴關系的任務就緒，在有限的資源下，任務的調度順序也是需要面臨的問題。對此本文以任務在資源中的實際執行情況為依據進行映射。

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

算法1：計算任務b-level值算法

(1)以任務流的逆向拓撲順序建立任務節點列表List， 設任務ni的b-level值為BL(ni)

(2)建立空集合B

(3)for每個任務ni∈Listdo

(4)ifni是出口任務then

(5)BL(ni)=ci

(6)else

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

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

(9)endfor

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

(11) 令B=?

(12)endif

(13)endfor

算法1中第(5)行代表出口任務的b-level值是其自身的節點權值。第(7)行至第(10)行表示一個任務的b-level值是該任務的節點權值、輸出邊權值與其后項任務中最大的b-level值三者之和。

對于每個就緒任務，在其自身的可用卸載資源池中，按照1.4節給出的時延模型計算在各個資源上的完成時間，并計算該任務的b-level與各完成時間的差值。該值體現任務自身屬性與資源實際執行情況的匹配程度，以此作為評價各個任務優先級的標準，可以起到綜合考慮且自適應動態變化的作用，具體算法如下：

算法2：ECTDP策略調度算法

(1)建立就緒任務集合RET、 可用資源池集合AP、 任務-資源映射集合TPM、 動態優先級值集合DP

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

(4)whileRET≠?do

(5)ifRET={nexit}then

(6) 將nexit放在本地執行

(7) 將nexit從RET中剔除

(8)else

(9)DP=?

(10)for每個任務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)值最大的任務-資源對， 將ni卸載至pm， 更新TPM

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

(19)endif

(20)endwhile

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

3 實驗仿真

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

3.1 參數設置

本文以單行道作為仿真場景，有一個源車輛，其生成一個任務流，沿車輛行駛方向有若干個RSU，滿足任務流的整個執行過程可用。所有車輛初始位置都在第一個RSU覆蓋范圍內，初始位置和車速在各自區間內隨機產生，服從均勻分布。單個任務的計算量、數據量和輸出結果的數據量也在各自取值范圍內隨機產生，服從均勻分布。基礎參數設置見表1[14]。

表1 參數設置

3.2 實驗設計與結果分析

首先以上述參數進行基準實驗，然后僅改變任務數、任務流最大出度、單個任務計算量、單個任務數據量、協作車輛數量這些因素中的其中一個，保持其余不變，利用控制變量法進行多組對比實驗。對于每組參數的實驗過程如下：

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

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

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

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

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

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

(7)待該任務流執行完成，記錄當前參數下各策略的任務流完成時間;

(8)重復(1)到(7)過程，進行1000次仿真，求出各個策略完成時間的平均值作為該組實驗結果。

3.2.1 基準實驗

為了綜合評價各卸載策略的優劣性，以基礎參數作為經典仿真場景進行基準實驗，實驗結果如圖7所示。

圖7 基準實驗結果對比

由圖7可知，SPO策略比LC策略更優，因為SPO可以利用周邊單個協作車輛進行分布式計算，相比完全在本地串行執行更節省時間。FOR策略比SPO策略更優，是因為FOR可以充分利用邊緣端較強的計算能力，縮短了每個任務的計算時間。而ECTDP策略最優，是因為該策略將RSU和協作車輛作為選擇目標，計算資源的形式不再單一，充分利用邊緣端強大的計算能力和車載自組織網的分布式計算，實現V2V和V2R兩種通信模式的優勢互補、相互延伸。此外，在進行資源選擇時以通信鏈路的穩定和減小時空跨度為核心思想，避免了通信鏈路的變化造成的計算切換和等待，增大了時間的利用率，降低任務間的傳輸時間。

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

3.2.2 任務數對任務流完成時間的影響

將任務數分別設為10、30、40和50進行對比實驗，實驗結果如圖8所示。

圖8 不同任務數的任務流完成時間

由圖8可以看出，任務數越多，執行任務流越耗時。這是因為任務流的規模越大，整個任務流中需要計算和傳輸的數據也隨之增加，為方便描述，將任務流中總的計算量和數據量統稱為總工作量。由于總工作量是由多個子任務的相關量線性疊加而得，因此總工作量與總任務數近似呈線性正相關。而在有限的資源下，執行任務流所需時長也與總工作量近似呈線性正相關。故而隨著任務數的增多，任務流的完成時間呈近似線性上升。此時FOR策略雖優于SPO策略，然兩者差距始終較小。這是因為FOR利用邊緣端的較強計算能力，相對于SPO能夠節省任務的計算時間，但FOR的全部卸載又導致過多的通信開銷。

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

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

將任務流的最大出度分別設為總任務數的20%、40%、60%和80%進行對比實驗，實驗結果如圖9所示。

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

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

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

將單個任務的計算量分別設定為(0,2]、(4,6]、(6,8]和(8,10](×108cycle)進行對比實驗，實驗結果如圖10所示。

圖10 不同計算量的任務流完成時間

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

3.2.5 單個任務數據量對任務流完成時間的影響

將單個任務的數據量分別設定為(10,20]、(20,30]、(30,40]、(40,50](MB)進行對比實驗，實驗結果如圖11所示。

圖11 不同數據量的任務流完成時間

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

3.2.6 協作車輛數量對任務流完成時間的影響

將協作車輛的數量從1增加至10進行對比實驗，實驗結果如圖12所示。

圖12 不同協作車輛數量的任務流完成時間

由圖12可以看出，協作車輛數量的變化對LC和FOR策略無影響，因為這兩個策略的執行與協作車輛無關。FOR和ECTDP策略會隨著協作車輛的增多先減少執行時間，再趨于平穩。這是因為協作車輛的增加使道路內交通密度變大，源車輛能夠連接到其它車輛的可能性變大，即增大了并行計算的可能性，從而縮短完成時間。然而此時任務流的最大出度為6，即同時就緒的可并行計算的任務最多為6個。因此隨著協作車輛的繼續增多，可用資源對于任務是一種供大于求的過飽和狀態，使得任務流的完成時間不再有明顯變化，從而趨于平穩。ECTDP策略受協作車輛影響的波動比SPO策略小，這是因為前者除了協作車輛還可以將RSU作為卸載資源，充分利用邊緣端的強大計算資源。ECTDP相比LC、SPO和FOR策略平均縮短了60.03%，42.65%和34.47%。

4 結束語

本文針對車載邊緣計算環境中的復雜任務流卸載進行了研究，考慮了任務依賴關系、車輛的移動性、資源的異構性、資源的使用狀況以及通信網絡拓撲結構的變化等因素，提出了一種基于動態優先級的卸載策略，充分的實驗表明，本文提出的策略相較于其它策略性能始終最優。在未來的研究中，將重點研究車載邊緣環境中在滿足任務流完成時間最小的同時降低源車輛的能耗開銷，實現卸載策略的多目標優化。