0 引言

隨著無線通信技術(shù)和車載互聯(lián)網(wǎng)的爆炸性發(fā)展，越來越多的車輛配備了具有通信、存儲、計算和人機交互能力的車載單元［1］。許多智能交通應(yīng)用程序可以在車載單元上運行，同時也有相當比例的車載應(yīng)用對計算資源與能源需求極大，被稱為計算密集型應(yīng)用。面對這些應(yīng)用，單個車載單元的計算能力可能無法完全滿足要求。車聯(lián)網(wǎng)邊緣計算（VEC）的出現(xiàn)為解決這一問題提供了新的途徑［2］。VEC 與移動邊緣計算（MEC）相比，其終端從個人移動設(shè)備變?yōu)榱烁咚僖苿拥能囕v。通過將核心網(wǎng)的計算資源部署到車輛網(wǎng)絡(luò)的邊緣，路側(cè)單元（RSU）覆蓋范圍內(nèi)的車輛可以將部分或全部任務(wù)卸載給部署在RSU 的MEC 服務(wù)器以獲得更好的計算服務(wù)，這種方式稱為車輛到基礎(chǔ)設(shè)施（V2I）卸載［3］。另一種方法是將任務(wù)卸載給其他有計算能力的車輛，稱為車輛到車輛（V2V）卸載［4］。與V2I卸載相比，V2V 卸載可以充分利用其他車輛的計算資源，緩解路邊MEC服務(wù)器的壓力。

通過V2I 卸載，車輛可以將計算任務(wù)卸載到部署在RSU的MEC服務(wù)器來完成計算。然而，在典型的車載網(wǎng)絡(luò)場景中，車輛在計算卸載過程中高速移動，使得V2I 卸載面臨許多問題，如車輛可能在計算結(jié)果返回之前離開RSU 覆蓋的小區(qū)，高速移動會影響無線鏈路質(zhì)量。在熱點地區(qū)，由于交通擁擠和移動終端數(shù)量過多，RSU 會承受很大的負載［5］。因此，如何充分利用閑置車輛的大量計算資源來降低RSU 的負載是計算卸載的關(guān)鍵問題之一［6］。文獻［7］考慮將卸載到負載過重RSU 的計算任務(wù)轉(zhuǎn)移到周圍負載較輕的RSU，并通過車輛將計算結(jié)果帶回輕負載RSU 的范圍內(nèi)。在文獻［8］中，V2I卸載問題被視為車輛與RSU 之間的匹配問題，通過求解任務(wù)車輛與RSU 之間的最優(yōu)匹配來最小化所有車輛的平均計算時延。在文獻［9］中，計算任務(wù)被分成若干個無依賴關(guān)系的子任務(wù)，分別卸載到沿途經(jīng)過的各個RSU，通過車速、鏈路質(zhì)量、RSU 覆蓋半徑、子任務(wù)大小等因素預(yù)測經(jīng)過每個RSU 覆蓋小區(qū)的時間，以此來分配子任務(wù)數(shù)量，確保計算結(jié)果的返回。

對于車載網(wǎng)絡(luò)中的V2V 卸載，車輛通常成組來共享信息并互相幫助完成計算任務(wù)。文獻［10］提出了一種協(xié)同車輛邊緣計算網(wǎng)絡(luò)架構(gòu)，該網(wǎng)絡(luò)中的多個相鄰車輛組成一個組，組中的車輛可以通過無線鏈路相互通信和協(xié)作完成計算任務(wù)。文獻［11］考慮了車組內(nèi)成員的協(xié)作以及計算任務(wù)的可分割性，其中組內(nèi)的不同車輛具有不同類型的計算任務(wù)。文獻［12］將計算任務(wù)分為順序子任務(wù)和依賴子任務(wù)，并提出了一種任務(wù)調(diào)度算法確定任務(wù)的最優(yōu)計算順序。在文獻［13］中，作者將計算任務(wù)劃分為若干有先后順序的子任務(wù)，并將任務(wù)分配問題看作并行處理器的最小完成時間問題，提出了一種基于列表調(diào)度的任務(wù)分配算法，以最小化任務(wù)的總完成時延。

然而，上述研究并沒有充分考慮計算卸載過程中車組內(nèi)的車輛之間保持穩(wěn)定連接的時間以及車輛在計算過程中離開車組的情況。本文聯(lián)合考慮車組成員能保持穩(wěn)定連接的時間和車輛突發(fā)離組的情況，具體分析了車輛因故障離組和中途主動離組的2 種情形。對計算任務(wù)根據(jù)不同類型劃分子任務(wù)，設(shè)計了一個動態(tài)的組內(nèi)計算任務(wù)分配算法，其中計算任務(wù)卸載總時延包括任務(wù)上傳時延、任務(wù)計算時延和結(jié)果返回時延。為了使整個車組計算任務(wù)的總時延最小，提出了一種車組內(nèi)計算任務(wù)分配算法。該算法調(diào)整了子任務(wù)的分配方式，通過迭代實現(xiàn)總時延最小。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)拓撲

本文研究單向直行道路上，車組在行駛過程中的計算卸載問題，場景如圖1所示。在該場景中，路側(cè)單元RSU 均勻分布在道路兩側(cè)，其覆蓋范圍互不重疊。這n個RSU 記作R={R1,R2...Ri...Rn}，其中Ri表示第i個RSU。每個RSU 的覆蓋半徑為r，相鄰RSU 之間由光纖連接。同車道內(nèi)前后M輛車組成一個車組。用U=(U0,U1...Ui...UM-1)表示車組內(nèi)的車輛，其中U0的計算任務(wù)僅靠自己不能完成，稱為任務(wù)車；組內(nèi)其他車輛或多或少有可以提供給任務(wù)車的空閑計算資源，稱為服務(wù)車。本章中任務(wù)車U0的計算任務(wù)分為4 種類型，分別是圖像處理、視頻處理、交互式游戲、增強現(xiàn)實［14-16］，可以用L=(LA,LB,LC,LD)表示，每種類型的任務(wù)可以劃分成若干相等大小的不相關(guān)的子任務(wù)，以I作為子任務(wù)劃分的大小單元。

整個車組以共同的速度v向前行進，車組內(nèi)每一輛車的計算能力分別為f=(f0,f1,...,fm-1)，單位是CPU圈數(shù)/s，其中f0是本地計算的計算能力。

1.2 通信模型

在車輛形成車組后，由任務(wù)車U0作為車頭來協(xié)調(diào)組內(nèi)車輛和分配計算任務(wù)。組內(nèi)車輛分享行駛路線使得U0可以獲取組內(nèi)各車輛能與車組保持穩(wěn)定卸載的時間信息，用τ={τ1,τ2...τm-1}分別表示組內(nèi)車輛預(yù)計離開車組的時間節(jié)點。要盡量保證分配給車輛Ui的計算任務(wù)在τi時間內(nèi)完成并返回。組內(nèi)車輛通過LTE-V 方式進行通信，根據(jù)香農(nóng)公式可知任務(wù)上傳到組內(nèi)服務(wù)車的速率如式（1）所示。

式中：

B0——分配給任務(wù)車的信道帶寬

h——上行信道衰落系數(shù)

N0——高斯白噪聲功率

pi——卸載到第i輛車的子任務(wù)數(shù)量

圖1 基于車輛成組的V2V卸載

任務(wù)車將帶寬分成M-1 份向組內(nèi)每一輛服務(wù)車傳送分配的任務(wù)。卸載到第i輛車的任務(wù)傳輸時間如式（2）所示。

然后考慮計算結(jié)果的返回。由于返回的計算結(jié)果數(shù)據(jù)量通常很小，所以車組內(nèi)的計算結(jié)果返回時延可以忽略不計。相鄰RSU 之間的光纖帶寬為B，子任務(wù)返回結(jié)果的數(shù)據(jù)量為dbit。任務(wù)返回時由于返回數(shù)據(jù)量很小，在RSU 之間的傳輸時間可以忽略不計，所以任務(wù)的返回時間主要由每次經(jīng)過RSU的等待時間tw決定。子任務(wù)結(jié)果在RSU 之間返回時每經(jīng)過一個RSU 都要有一個等待時延，經(jīng)過n個RSU 則返回時延為ntw。

1.3 計算模型

本文假設(shè)車組內(nèi)任務(wù)車輛的計算負載較重，且計算任務(wù)可以分割為若干相等大小的無依賴關(guān)系的子任務(wù)。執(zhí)行計算任務(wù)需要耗費車輛的計算資源，通常使用執(zhí)行該計算任務(wù)所要耗費的CPU 圈數(shù)來表示。任務(wù)執(zhí)行時的復(fù)雜度用執(zhí)行單位大小的任務(wù)需要耗費的CPU圈數(shù)來表示。假設(shè)4種不同類型任務(wù)的計算復(fù)雜度不同，分別是αA,αB,αC,αD，單位為CPU 圈數(shù)/bit。

考慮到任務(wù)分割，這4 類任務(wù)劃分為若干個子任務(wù)。4 種任務(wù)的每個子任務(wù)數(shù)量表示為NA,NB,NC,ND，子任務(wù)總數(shù)為N。

假設(shè)每個子任務(wù)的大小為Ibit。車組中的每輛車都由任務(wù)車輛分配了一定數(shù)量的子任務(wù)，分配給第i輛車的4 種任務(wù)的子任務(wù)數(shù)分別為pi={piA,piB,piC,piD}，則第i輛車的計算時延包括了4 種任務(wù)的計算時延，可通過式（3）計算。

如上所述，組內(nèi)的每輛車都被分配了這4 類任務(wù)中若干數(shù)量的子任務(wù)。本文通過調(diào)整每輛車被分配的子任務(wù)數(shù)量以降低總?cè)蝿?wù)時延。

2 算法設(shè)計與實現(xiàn)

2.1 問題建立

對于組內(nèi)被分配了計算任務(wù)的服務(wù)車輛，在任務(wù)計算完成后將計算結(jié)果直接返回給任務(wù)車輛。對于中途離開的服務(wù)車輛，考慮該車輛在離開車組后繼續(xù)進行計算工作，在計算完成后借助RSU 將計算任務(wù)返回給原車組中的任務(wù)車輛。

車輛離開車組的原因包括客觀因素與主觀因素。例如車輛在行駛過程中突發(fā)故障就屬于客觀因素。對于這種情況，可以根據(jù)已行駛時間估計車輛在未來一段時間內(nèi)出故障的概率。對于第i輛車在任務(wù)過程中發(fā)生故障的概率可以用式（4）表示。

式中：

車輛也可能因駕駛者的主觀意愿臨時變更行駛方向或是需要在原地停留一段時間。對于這種情況，可以根據(jù)車輛歷史參與計算任務(wù)卸載的情況來推測本次任務(wù)過程中會發(fā)生主觀離組的可能性。假設(shè)車輛i歷史參與任務(wù)卸載的次數(shù)為yi，在任務(wù)過程中主動離開的次數(shù)為xi，通過車輛歷史參與任務(wù)卸載次數(shù)和中途離開的次數(shù)的比值可以推測其本次任務(wù)過程中離組的概率，具體如式（5）所示。

根據(jù)上面的2個因素，如果有一個因素發(fā)生，車輛就會離開車組。因此，第i輛車在任務(wù)過程中離開車組的概率可以用式（6）算出。

車組中所有車輛離開車組的概率，用ε ={ε1,ε2,...,εm-1}表示。假設(shè)車輛在離開車組后保持原地等待，同時不停止任務(wù)的計算過程，同時車組繼續(xù)保持前進。表示第i輛車離開車組的時刻。離開車組的車輛在完成計算任務(wù)后將計算結(jié)果返回給當前所在的RSU。車組在車輛i離開車組后經(jīng)過的RSU 數(shù)量由式（7）給出。

離開車組的服務(wù)車輛可以通過式（7）獲得車組當前所在的位置，并將結(jié)果返回到其范圍內(nèi)的RSU。接下來，結(jié)果將在相鄰的RSU 之間傳輸，并最終到達車組當前所在的RSU。返回時延是由式（8）定義。

車組中每個車輛的總?cè)蝿?wù)時延如式（9）所示，是任務(wù)上傳時延、任務(wù)計算時延和任務(wù)返回時延之和。

整個車組的總?cè)蝿?wù)時延定義為車組中所有任務(wù)完成的時間，也就是組內(nèi)最后一個車輛完成任務(wù)的時間。本文目標是通過優(yōu)化組內(nèi)車輛子任務(wù)的分配，以最小化任務(wù)完成的總時延。

因此，本文所討論的時延最小化問題可以表述為式（10）。

限制條件如下：

a）ti<τi

b）pi=piA+piB+piC+piD

d）0≤pi≤N

e）piA≤NA,piB≤NB,piC≤NC,piD≤ND

在上述條件中，條件a）是對每輛車中計算任務(wù)時延的限制，即每個車輛的計算任務(wù)必須在該任務(wù)的限制時延內(nèi)完成。b）為子任務(wù)數(shù)量的約束條件，即分配給每個車輛的子任務(wù)數(shù)量等于4 種子任務(wù)數(shù)量的總和。c）以及d）是對每個車輛分配到子任務(wù)數(shù)量的限制，表明每輛車被分配到的每種類型的子任務(wù)數(shù)不超過車組內(nèi)該種類子任務(wù)的總數(shù)。e）給出了車組內(nèi)每種類型子任務(wù)數(shù)量上限的約束。

2.2 所提算法

通過分析發(fā)現(xiàn)，目標函數(shù)屬于混合整數(shù)規(guī)劃問題，存在最優(yōu)解。這類問題在問題規(guī)模較小時可以通過暴力枚舉法在較短時間內(nèi)找到最優(yōu)解。然而當問題規(guī)模擴大后，暴力枚舉所需的時間則呈指數(shù)級增長。具體來看，式（10）相當于將N個任務(wù)放進M個容器內(nèi)，一共有MN種可能性，時間復(fù)雜度為O(MN)，屬于NP-hard 問題。通過啟發(fā)式算法在較短的時間內(nèi)找出一個次優(yōu)解也是解決這類問題的一個途徑。本文使用模擬退火算法對該式進行求解，以得到較低時間代價的次優(yōu)解。

在車組形成后，組內(nèi)的服務(wù)車輛將路由、計算資源、歷史完成情況、故障概率等信息發(fā)送給任務(wù)車輛。任務(wù)車輛然后根據(jù)式（6）預(yù)測在計算任務(wù)過程中各個服務(wù)車輛的離開概率。首先任務(wù)車輛在分配每一個子任務(wù)前，通過式（2）、式（6）、式（8）、式（10）分別計算將此子任務(wù)卸載到每一個服務(wù)車輛的卸載時延，然后根據(jù)貪心算法依次將4種類型任務(wù)的子任務(wù)分給組內(nèi)的服務(wù)車輛。貪心算法的策略是每個服務(wù)車輛被分配任務(wù)后累積自己的總?cè)蝿?wù)時延，任務(wù)車輛將下一個子任務(wù)分配給當前總?cè)蝿?wù)時延最小的服務(wù)車輛。在所有子任務(wù)分配完畢后，使用模擬退火算法優(yōu)化子任務(wù)的分配方式，在所限定迭代次數(shù)內(nèi)找出次優(yōu)解。詳細算法步驟如圖2所示。

模擬退火算法的步驟包括以下幾步。

a）隨機在以下2個操作中二選一執(zhí)行。

（a）隨機選擇車組內(nèi)2輛車，交換其中一個不同類型的子任務(wù)。

（b）將車組內(nèi)一輛車的一個子任務(wù)隨機分配給另一輛車。

b）計算新的總時延與之前總時延的差值。

c）如果差值為負，即通過任務(wù)交換或任務(wù)分配得到的時延比之前低，則接受此操作。否則則按一定概率接受此次操作，接受概率與當前溫度有關(guān)。

圖2 車組內(nèi)協(xié)同計算任務(wù)分配算法

d）將當前溫度乘以冷卻系數(shù)得到新的溫度。

3 仿真與分析

本章通過仿真來驗證所提算法的性能。仿真場景如表1所示。車組內(nèi)車輛的計算能力為f={3×107，5×107，2×107，3×107，3×107}圈/s，4種計算任務(wù)的計算復(fù)雜程度分別是30、15、40、20［17］。具體參數(shù)設(shè)置如表1 所示。

所選取的對比算法分別是隨機卸載算法以及貪婪卸載算法［18］。

a）隨機卸載算法：4 種計算任務(wù)將隨機數(shù)量的子任務(wù)分配給組內(nèi)車輛。

b）貪婪卸載算法：貪婪分配算法在每次分配任務(wù)時都選擇能使當前總計算時延最小的車輛進行分配。

圖3 顯示當車組內(nèi)子任務(wù)總數(shù)為80 時，通過3 種算法分配任務(wù)的車組最小時延與迭代次數(shù)的關(guān)系。車組速度設(shè)定為18 m/s。結(jié)果表明3 種算法都能在一定次數(shù)的迭代內(nèi)達到收斂。其中貪婪分配算法能較快獲取極小值，在大約400 次迭代后將總時延降低到11.84 s。本文所提算法在約1 400 次迭代后收斂到最小值11.84 s?？梢钥闯觯斪尤蝿?wù)總數(shù)量比較少時，這2種算法都能找到最小值。而隨機分配算法時延大于其他2種算法，性能較差。

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

圖3 N=80時車組總時延隨迭代次數(shù)增加的變化

圖4 展示的是當組內(nèi)子任務(wù)數(shù)增加到135 時，通過3種算法分配任務(wù)的車組最小時延與迭代次數(shù)的關(guān)系，其中車速仍固定在18 m/s。隨著任務(wù)數(shù)量的增加，可以看出，貪婪算法依舊可以較快地找到極小值，在約200次迭代后陷入局部極小值，由仿真結(jié)果來看，本文所提算法在約1 400 次迭代后找到了全局最小值17.64 s。隨機任務(wù)分配算法性能較差。

圖4 N=135時車組總時延隨迭代次數(shù)增加的變化

圖5表示車組的總?cè)蝿?wù)時延隨車組內(nèi)子任務(wù)數(shù)量增加而變化的情況。固定車組行駛速度18 m/s，可以看出，3 種任務(wù)分配算法得到的車組總時延均會隨車組內(nèi)子任務(wù)數(shù)量的增長而增長。隨著子任務(wù)數(shù)量增加，在子任務(wù)數(shù)量超過100以后，貪婪算法的增長速率要明顯高于本文所提算法，這是因為子任務(wù)數(shù)量越多，貪婪算法越容易陷入局部最小，從而導(dǎo)致車組總?cè)蝿?wù)時延較大。

圖6顯示了計算資源的利用率與組內(nèi)車輛數(shù)量的關(guān)系。將計算資源的利用率定義為參與計算的車輛的平均計算時延與任務(wù)總完成時延之比［19］。計算資源利用率越高也即意味著每一個參與計算的車輛節(jié)點的計算時間越接近。從圖6 可以看出，當車組中車輛數(shù)增加時，車組的計算資源利用率隨之增加，這是因為，當參與任務(wù)的車輛越多，任務(wù)就可以在更短的時間內(nèi)完成，所以離開車組的車輛返回結(jié)果所需的時間就越短，對整個車組的影響就更小。從圖6 的結(jié)果可以看出本文所提算法與其他2種算法相比能更合理地分配任務(wù)，提高計算資源的利用率。

圖7表示車組總?cè)蝿?wù)完成時延隨車速增加而變化的情況。從圖7可以看出車組的總?cè)蝿?wù)完成時延隨著車組速度的增加而增加。因為車組行駛速度越快，車組在任務(wù)進行過程中通過的RSU 單元越多，離開車輛組的車輛返回的任務(wù)結(jié)果所經(jīng)過的RSU 就越多，任務(wù)結(jié)果返回到車輛組的時間也就越長。

圖5 車組平均任務(wù)時延隨子任務(wù)數(shù)量的變化

圖6 車組平均計算資源利用率隨車輛數(shù)增加的變化

4 結(jié)束語

本文對基于車輛成組的組內(nèi)V2V 計算任務(wù)卸載問題進行了研究，提出了一種考慮車輛在計算卸載過程中離開車組的任務(wù)分配算法。首先介紹了研究背景與網(wǎng)絡(luò)模型。然后聯(lián)合考慮車組成員能保持穩(wěn)定連接的時間和車輛因故障突發(fā)離組的情況，具體分析了車輛離組的2種情形并建模。將計算任務(wù)劃分成不同類型的子任務(wù)，并設(shè)計了一個動態(tài)的組內(nèi)計算任務(wù)分配算法。該算法調(diào)整了子任務(wù)的分配方式，通過迭代實現(xiàn)總時延最小。最后，通過仿真對所提算法的有效性進行了驗證。

圖7 車組總時延隨車速的變化