基于車輛成組的V2V協(xié)同計(jì)算卸載策略研究

0 引言

隨著無線通信技術(shù)和車載互聯(lián)網(wǎng)的爆炸性發(fā)展，越來越多的車輛配備了具有通信、存儲(chǔ)、計(jì)算和人機(jī)交互能力的車載單元［1］。許多智能交通應(yīng)用程序可以在車載單元上運(yùn)行，同時(shí)也有相當(dāng)比例的車載應(yīng)用對(duì)計(jì)算資源與能源需求極大，被稱為計(jì)算密集型應(yīng)用。面對(duì)這些應(yīng)用，單個(gè)車載單元的計(jì)算能力可能無法完全滿足要求。車聯(lián)網(wǎng)邊緣計(jì)算（VEC）的出現(xiàn)為解決這一問題提供了新的途徑［2］。VEC 與移動(dòng)邊緣計(jì)算（MEC）相比，其終端從個(gè)人移動(dòng)設(shè)備變?yōu)榱烁咚僖苿?dòng)的車輛。通過將核心網(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ò)場(chǎng)景中，車輛在計(jì)算卸載過程中高速移動(dòng)，使得V2I 卸載面臨許多問題，如車輛可能在計(jì)算結(jié)果返回之前離開RSU 覆蓋的小區(qū)，高速移動(dòng)會(huì)影響無線鏈路質(zhì)量。在熱點(diǎn)地區(qū)，由于交通擁擠和移動(dòng)終端數(shù)量過多，RSU 會(huì)承受很大的負(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ì)算時(shí)延。在文獻(xiàn)［9］中，計(jì)算任務(wù)被分成若干個(gè)無依賴關(guān)系的子任務(wù)，分別卸載到沿途經(jīng)過的各個(gè)RSU，通過車速、鏈路質(zhì)量、RSU 覆蓋半徑、子任務(wù)大小等因素預(yù)測(cè)經(jīng)過每個(gè)RSU 覆蓋小區(qū)的時(shí)間，以此來分配子任務(wù)數(shù)量，確保計(jì)算結(jié)果的返回。

對(duì)于車載網(wǎng)絡(luò)中的V2V 卸載，車輛通常成組來共享信息并互相幫助完成計(jì)算任務(wù)。文獻(xiàn)［10］提出了一種協(xié)同車輛邊緣計(jì)算網(wǎng)絡(luò)架構(gòu)，該網(wǎng)絡(luò)中的多個(gè)相鄰車輛組成一個(gè)組，組中的車輛可以通過無線鏈路相互通信和協(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ù)分配問題看作并行處理器的最小完成時(shí)間問題，提出了一種基于列表調(diào)度的任務(wù)分配算法，以最小化任務(wù)的總完成時(shí)延。

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

1 系統(tǒng)模型

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

本文研究單向直行道路上，車組在行駛過程中的計(jì)算卸載問題，場(chǎng)景如圖1所示。在該場(chǎng)景中，路側(cè)單元RSU 均勻分布在道路兩側(cè)，其覆蓋范圍互不重疊。這n個(gè)RSU 記作R={R1,R2...Ri...Rn}，其中Ri表示第i個(gè)RSU。每個(gè)RSU 的覆蓋半徑為r，相鄰RSU 之間由光纖連接。同車道內(nèi)前后M輛車組成一個(gè)車組。用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ù)劃分的大小單元。

整個(gè)車組以共同的速度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)定卸載的時(shí)間信息，用τ={τ1,τ2...τm-1}分別表示組內(nèi)車輛預(yù)計(jì)離開車組的時(shí)間節(jié)點(diǎn)。要盡量保證分配給車輛Ui的計(jì)算任務(wù)在τi時(shí)間內(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ù)傳輸時(shí)間如式（2）所示。

然后考慮計(jì)算結(jié)果的返回。由于返回的計(jì)算結(jié)果數(shù)據(jù)量通常很小，所以車組內(nèi)的計(jì)算結(jié)果返回時(shí)延可以忽略不計(jì)。相鄰RSU 之間的光纖帶寬為B，子任務(wù)返回結(jié)果的數(shù)據(jù)量為dbit。任務(wù)返回時(shí)由于返回?cái)?shù)據(jù)量很小，在RSU 之間的傳輸時(shí)間可以忽略不計(jì)，所以任務(wù)的返回時(shí)間主要由每次經(jīng)過RSU的等待時(shí)間tw決定。子任務(wù)結(jié)果在RSU 之間返回時(shí)每經(jīng)過一個(gè)RSU 都要有一個(gè)等待時(shí)延，經(jīng)過n個(gè)RSU 則返回時(shí)延為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í)行時(shí)的復(fù)雜度用執(zhí)行單位大小的任務(wù)需要耗費(fèi)的CPU圈數(shù)來表示。假設(shè)4種不同類型任務(wù)的計(jì)算復(fù)雜度不同，分別是αA,αB,αC,αD，單位為CPU 圈數(shù)/bit。

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

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

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

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

2.1 問題建立

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

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

式中：

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

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

車組中所有車輛離開車組的概率，用ε ={ε1,ε2,...,εm-1}表示。假設(shè)車輛在離開車組后保持原地等待，同時(shí)不停止任務(wù)的計(jì)算過程，同時(shí)車組繼續(xù)保持前進(jìn)。表示第i輛車離開車組的時(shí)刻。離開車組的車輛在完成計(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。返回時(shí)延是由式（8）定義。

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

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

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

限制條件如下：

a）ti<τi

b）pi=piA+piB+piC+piD

d）0≤pi≤N

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

在上述條件中，條件a）是對(duì)每輛車中計(jì)算任務(wù)時(shí)延的限制，即每個(gè)車輛的計(jì)算任務(wù)必須在該任務(wù)的限制時(shí)延內(nèi)完成。b）為子任務(wù)數(shù)量的約束條件，即分配給每個(gè)車輛的子任務(wù)數(shù)量等于4 種子任務(wù)數(shù)量的總和。c）以及d）是對(duì)每個(gè)車輛分配到子任務(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ī)模較小時(shí)可以通過暴力枚舉法在較短時(shí)間內(nèi)找到最優(yōu)解。然而當(dāng)問題規(guī)模擴(kuò)大后，暴力枚舉所需的時(shí)間則呈指數(shù)級(jí)增長(zhǎng)。具體來看，式（10）相當(dāng)于將N個(gè)任務(wù)放進(jìn)M個(gè)容器內(nèi)，一共有MN種可能性，時(shí)間復(fù)雜度為O(MN)，屬于NP-hard 問題。通過啟發(fā)式算法在較短的時(shí)間內(nèi)找出一個(gè)次優(yōu)解也是解決這類問題的一個(gè)途徑。本文使用模擬退火算法對(duì)該式進(jìn)行求解，以得到較低時(shí)間代價(jià)的次優(yōu)解。

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

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

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

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

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

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

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

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

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

3 仿真與分析

本章通過仿真來驗(yàn)證所提算法的性能。仿真場(chǎng)景如表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 所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

圖7 車組總時(shí)延隨車速的變化