0 引言

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

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

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

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

1 系統(tǒng)模型

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

本文研究單向直行道路上，車組在行駛過程中的計(jì)算卸載問題，場景如圖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的計(jì)算任務(wù)僅靠自己不能完成，稱為任務(wù)車；組內(nèi)其他車輛或多或少有可以提供給任務(wù)車的空閑計(jì)算資源，稱為服務(wù)車。本章中任務(wù)車U0的計(jì)算任務(wù)分為4 種類型，分別是圖像處理、視頻處理、交互式游戲、增強(qiáng)現(xiàn)實(shí)［14-16］，可以用L=(LA,LB,LC,LD)表示，每種類型的任務(wù)可以劃分成若干相等大小的不相關(guān)的子任務(wù)，以I作為子任務(wù)劃分的大小單元。

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

1.2 通信模型

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

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

1.3 計(jì)算模型

本文假設(shè)車組內(nèi)任務(wù)車輛的計(jì)算負(fù)載較重，且計(jì)算任務(wù)可以分割為若干相等大小的無依賴關(guān)系的子任務(wù)。執(zhí)行計(jì)算任務(wù)需要耗費(fèi)車輛的計(jì)算資源，通常使用執(zhí)行該計(jì)算任務(wù)所要耗費(fèi)的CPU 圈數(shù)來表示。任務(wù)執(zhí)行時的復(fù)雜度用執(zhí)行單位大小的任務(wù)需要耗費(fèi)的CPU圈數(shù)來表示。假設(shè)4種不同類型任務(wù)的計(jì)算復(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輛車的計(jì)算時延包括了4 種任務(wù)的計(jì)算時延，可通過式（3）計(jì)算。

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

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

2.1 問題建立

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

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

式中：

車輛也可能因駕駛者的主觀意愿臨時變更行駛方向或是需要在原地停留一段時間。對于這種情況，可以根據(jù)車輛歷史參與計(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ù)的計(jì)算過程，同時車組繼續(xù)保持前進(jìn)。表示第i輛車離開車組的時刻。離開車組的車輛在完成計(jì)算任務(wù)后將計(jì)算結(jié)果返回給當(dāng)前所在的RSU。車組在車輛i離開車組后經(jīng)過的RSU 數(shù)量由式（7）給出。

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

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

整個車組的總?cè)蝿?wù)時延定義為車組中所有任務(wù)完成的時間，也就是組內(nèi)最后一個車輛完成任務(wù)的時間。本文目標(biāo)是通過優(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）是對每輛車中計(jì)算任務(wù)時延的限制，即每個車輛的計(jì)算任務(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)，目標(biāo)函數(shù)屬于混合整數(shù)規(guī)劃問題，存在最優(yōu)解。這類問題在問題規(guī)模較小時可以通過暴力枚舉法在較短時間內(nèi)找到最優(yōu)解。然而當(dāng)問題規(guī)模擴(kuò)大后，暴力枚舉所需的時間則呈指數(shù)級增長。具體來看，式（10）相當(dāng)于將N個任務(wù)放進(jìn)M個容器內(nèi)，一共有MN種可能性，時間復(fù)雜度為O(MN)，屬于NP-hard 問題。通過啟發(fā)式算法在較短的時間內(nèi)找出一個次優(yōu)解也是解決這類問題的一個途徑。本文使用模擬退火算法對該式進(jìn)行求解，以得到較低時間代價的次優(yōu)解。

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

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

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

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

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

b）計(jì)算新的總時延與之前總時延的差值。

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

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

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

3 仿真與分析

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

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

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

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

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

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

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

圖4 展示的是當(dāng)組內(nèi)子任務(wù)數(shù)增加到135 時，通過3種算法分配任務(wù)的車組最小時延與迭代次數(shù)的關(guān)系，其中車速仍固定在18 m/s。隨著任務(wù)數(shù)量的增加，可以看出，貪婪算法依舊可以較快地找到極小值，在約200次迭代后陷入局部極小值，由仿真結(jié)果來看，本文所提算法在約1 400 次迭代后找到了全局最小值17.64 s。隨機(jī)任務(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以后，貪婪算法的增長速率要明顯高于本文所提算法，這是因?yàn)樽尤蝿?wù)數(shù)量越多，貪婪算法越容易陷入局部最小，從而導(dǎo)致車組總?cè)蝿?wù)時延較大。

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

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

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

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

4 結(jié)束語

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

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