車聯(lián)網(wǎng)中自適應(yīng)聯(lián)合計算卸載資源分配算法

林 峰，羅鋮文+，丁鵬舉，蔣建春

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 電子信息與網(wǎng)絡(luò)工程研究院，重慶 400065；3.重慶郵電大學(xué) 自動化學(xué)院，重慶 400065)

0 引 言

隨著C-V2X中各種計算密集型和對延遲敏感的應(yīng)用興起，給計算資源有限的車輛帶來了巨大挑戰(zhàn)[1]。移動云計算(MCC)資源豐富，但是距離車輛較遠，會產(chǎn)生巨大的傳輸時延和能耗[2]。將計算下沉到MEC服務(wù)器，使得時延和能耗更低[3]。文獻[4]提出一種云輔助的移動邊緣計算卸載策略，結(jié)合遺傳算法以時延和能耗最小化為優(yōu)化目標。文獻[5]使用強化學(xué)習(xí)，為降低計算時延，將任務(wù)卸載到本地、MEC、遠端云服務(wù)器。文獻[6]提出了一種聯(lián)合計算卸載策略，將計算任務(wù)分別在MEC、空閑車輛，和本地計算。文獻[7]提出一種節(jié)能的卸載策略，在遠端云協(xié)助下優(yōu)化MEC系統(tǒng)中的卸載選擇和資源分配來最大程度地降低成本。目前工作中，同時考慮時延和能耗的前提下對多輛車并發(fā)卸載進行研究的較少，以及計算平臺并未得到充分利用。在上述工作的基礎(chǔ)上，本文提出一種自適應(yīng)的聯(lián)合計算卸載資源分配算法，首先，該算法考慮多輛車并發(fā)卸載計算任務(wù)的場景，在滿足最大時延約束下，該算法能自適應(yīng)得到每輛車卸載到本地、遠端云服務(wù)器、MEC服務(wù)器、空閑車輛的最優(yōu)任務(wù)比例，同時對MEC的計算資源做最優(yōu)分配。通過實驗仿真與其它算法相比，驗證所提算法具有最小系統(tǒng)總成本。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

為了盡可能利用所有的計算資源來降低系統(tǒng)總成本，考慮了4種計算卸載方式。如圖1所示，卸載車輛的計算任務(wù)可以在本地計算，可以卸載到當前RSU下的空閑車輛Vidle計算，可以卸載到配備有MEC服務(wù)器的RSU上計算，也可以通過蜂窩網(wǎng)卸載到遠端云服務(wù)器計算。遠端云服務(wù)器的計算資源豐富，但是車輛卸載任務(wù)到遠端云服務(wù)器的通信時延，能耗會很高，RSU上配備的MEC服務(wù)器離車輛近，通信時延低，但是計算資源有限?？臻e車輛計算能力較弱，但是通信時延較低。

圖1 網(wǎng)絡(luò)模型

假定多輛車同時卸載任務(wù)，定義當前RSU覆蓋下有計算任務(wù)需要卸載的車輛集合為V={v1,v2,…,vn}， 每輛車都有一個計算任務(wù)需要卸載，對應(yīng)的任務(wù)集合為S={S1,S2,…,Sn}, 空閑車輛的集合為C={c1,c2,…,ck}。 假設(shè)車輛上傳鏈路的信道是瑞利信道模型[8]。

車輛vi與BS之間的上傳/下載的數(shù)據(jù)速率為

(1)

車輛vi與空閑車輛、MEC之間上傳/下載的數(shù)據(jù)速率為

(2)

1.2 任務(wù)模型

1.3 計算模型

1.3.1 本地計算模型

(3)

(4)

其中，Pi表示車輛vi的設(shè)備功率。

1.3.2 MEC計算模型

(5)

(6)

(7)

(8)

(9)

1.3.3 云計算模型

(10)

(11)

(12)

(13)

(14)

其中，Pcloud表示遠端云服務(wù)器的設(shè)備功率，PBS表示基站的發(fā)射功率。

1.3.4 空閑車輛計算模型

(15)

(16)

(17)

(18)

(19)

其中，Pidle表示空閑車輛的設(shè)備功率。

2 問題建模

在本節(jié)中，將多個車輛的任務(wù)卸載和MEC的計算資源分配建模為多約束優(yōu)化問題，在本研究中考慮的是多天線的卸載方式，故4個時延不是簡單的相加關(guān)系，而是取它們中最大的時延。所以由前一節(jié)可以得到聯(lián)合卸載的總時延T，總能耗E，定義聯(lián)合卸載系統(tǒng)的成本為H

(20)

(21)

H=γ·T+(1-γ)·E

(22)

其中，γ為時延權(quán)重系數(shù)，(1-γ)為能耗權(quán)重系數(shù)?？筛鶕?jù)移動服務(wù)的需求及移動設(shè)備的狀態(tài)來設(shè)置。例如，當運行時延敏感型移動服務(wù)時，可以適當增加γ的值。

(23)

C1表示車輛vi確定把任務(wù)Si要卸載到本地，MEC服務(wù)器，遠端云服務(wù)器，空閑車輛的任務(wù)比例相加為整個任務(wù)；C2表示完成每輛車的任務(wù)的時間不應(yīng)超過最大容忍時延；C3表示能卸載到空閑車輛的最大數(shù)目；C4表示為每個車輛分配的計算資源不能超過MEC服務(wù)器的總資源；C5表示為車輛任務(wù)分配的計算資源總和不能超過MEC服務(wù)器的總資源。

3 算法設(shè)計

目前，許多研究采用智能算法解決優(yōu)化問題。本文選擇改進的粒子群算法，即帶壓縮因子的粒子群算法(PSO-X)[10]。由于本文的目標函數(shù)有等式和不等式約束，所以在PSO-X基礎(chǔ)上，提出矩陣編碼方式，和粒子修正算法，并在目標函數(shù)基礎(chǔ)上加上罰函數(shù)進行約束條件的處理。本文改進的粒子群算法流程如圖2所示。

圖2 改進粒子群算法流程

3.1 粒子編碼

圖3 粒子編碼矩陣

3.2 粒子修正算法

從圖3可以看到，初始化的粒子編碼矩陣每一行的前4列相加不為1，不滿足約束C1。粒子編碼矩陣的第5列相加不為1，不滿足式約束C5。粒子編碼矩陣的第4列大于0的個數(shù)超過了當前空閑車輛數(shù)，不滿足約束C3。所以在本小節(jié)給出一種粒子修正算法來使得粒子滿足式(23)的C1，C3，C5約束條件。C4約束在初始化和邊界處理之后，一定會滿足，C2用罰函數(shù)法進行處理。

假設(shè)當前RSU下有car輛車需要任務(wù)卸載，idlecar輛空閑車輛。粒子修正算法描述見表1。

表1 粒子修正算法

通過粒子修正算法后，粒子的編碼矩陣如圖4所示?？梢钥吹搅Ｗ泳幋a矩陣每一行的前4列相加為1，也就是每個車輛卸載到各個計算點的任務(wù)相加為整個計算任務(wù)。矩陣的第5列相加為1，表示當前RSU下為每個車輛分配的MEC計算資源之和等于MEC服務(wù)器的總資源，矩陣第4列大于0的個數(shù)等于2，表明當前只能為兩輛車提供計算任務(wù)。

圖4 粒子編碼矩陣修正后

3.3 罰函數(shù)法構(gòu)造適應(yīng)度函數(shù)

罰函數(shù)法可以將約束優(yōu)化問題轉(zhuǎn)換為非約束優(yōu)化問題。該方法通過創(chuàng)建兩個約束函數(shù)，加入懲罰因子，然后將它們添加到約束優(yōu)化問題的目標函數(shù)中創(chuàng)建懲罰函數(shù)[11,12]。

將式(23)中的C2改寫為

(24)

當x≤0，是不進行懲罰的，只有當x>0時，才進行懲罰，所以懲罰函數(shù)為

(25)

其中，q是相對約束懲罰函數(shù)，θ(q) 是分段賦值函數(shù)，γ(q)是懲罰指數(shù)。

適應(yīng)度函數(shù)為目標函數(shù)加上懲罰函數(shù)

(26)

3.4 粒子速度與位置更新

在粒子群算法中使用約束因子去控制粒子行為以達到最終收斂[13]，不僅可以有效搜索不同的區(qū)域，而且能得到高質(zhì)量的解。壓縮因子法的速度更新公式為[14]

(27)

4 仿真結(jié)果與分析

在本節(jié)中分別對本文算法、All-Local算法、All-Mec算法、Random算法以及文獻[6]算法進行仿真和對比。

All-Local算法：將任務(wù)全部留在本地進行計算。

All-Mec算法：將任務(wù)全部卸載到當前RSU配備的MEC服務(wù)器上進行計算。

Random算法：將任務(wù)隨機的全部卸載到本地，MEC，遠端云服務(wù)器，空閑車輛進行計算。

文獻[6]算法：將整個計算任務(wù)分成3部分，分別在空閑車輛，MEC和本地計算。

改進的PSO-X算法的參數(shù)設(shè)置見表2，所提算法的相關(guān)仿真參數(shù)見表3。

表2 PSO-X算法相關(guān)參數(shù)

表3 仿真參數(shù)

圖5展示了空閑車輛數(shù)對平均每輛車系統(tǒng)成本的影響，也就是對系統(tǒng)總成本的影響，從圖中可以看到，隨著空閑車輛數(shù)的增加，平均每輛車的系統(tǒng)成本呈下降趨勢。其中，車輛數(shù)為16的下降趨勢最大，車輛數(shù)為10的下降趨勢最小。這是因為在RSU下車輛數(shù)較少時，每個車輛都能獲得較多的MEC計算資源，空閑車輛的計算資源對降低系統(tǒng)成本的趨勢較小。當車輛數(shù)增加時，所能獲得的MEC計算資源減少，此時增加空閑車輛數(shù),能較大的降低系統(tǒng)成本。

圖5 空閑車輛數(shù)對平均每輛車系統(tǒng)成本的影響

從中可以看到平均每輛車的系統(tǒng)成本低于400，說明本算法能夠在滿足最大容忍時延的同時，最小化系統(tǒng)總成本。

圖6展示了計算任務(wù)量對系統(tǒng)總成本的影響，并與其它4種算法進行了對比?？梢钥吹?，隨著計算任務(wù)量的增加，5種算法的系統(tǒng)總成本也隨著增加，本文所提算法的增加的幅度最小，并且系統(tǒng)總成本明顯低于其它4種算法，約是All-Local算法的22.09%，All-Mec算法的38.66%，Random算法的27.8%，文獻[6]算法的68.80%。

圖6 計算任務(wù)量對系統(tǒng)總成本的影響

圖7展示的是車輛數(shù)對系統(tǒng)總成本的影響，隨著車輛數(shù)的增加，5種算法的系統(tǒng)總成本都呈現(xiàn)上升趨勢。All-Mec算法在車輛數(shù)為20時出現(xiàn)突增，是因為當車輛數(shù)超過一定值時，導(dǎo)致MEC分配給每輛車的計算資源還沒有本地高，所以會出現(xiàn)比本地計算的系統(tǒng)總成本還高。本文算法相比其它算法，具有最小的系統(tǒng)總成本。

圖7 車輛數(shù)對系統(tǒng)總成本的影響

圖8展示了帶寬分配因子λ，ω，也就是帶寬對系統(tǒng)總成本的影響，隨著λ，ω的增加系統(tǒng)的總成本降低。因為當帶寬增加時，傳輸時延降低，能耗降低。而且可以看到當ω一定時，隨著λ的增加系統(tǒng)總成本的下降速度快。當λ一定時，隨著ω的增加系統(tǒng)總成本的下降速度相比于前者較慢。是因為ω增加，也就是與BS之間的帶寬增加，那么卸載到遠端云的傳輸時延就會降低，卸載到遠端云的任務(wù)量會自適應(yīng)增加，而遠端云的計算能力比MEC服務(wù)器強，所以比增加λ時的系統(tǒng)的總成本下降較快。

圖8 帶寬對系統(tǒng)總成本的影響

如圖9所示，隨著輸出數(shù)據(jù)量的增加，除了All-Local外所有算法的系統(tǒng)總成本都增加。因為本地計算不存在計算結(jié)果的返回時延，所以All-Local算法的系統(tǒng)總成本保持不變，而其它算法的影響也較小，是因為只有卸載到MEC，遠端云，空閑車輛才有結(jié)果返回時延，而計算結(jié)果的返回量相對較小，所以對系統(tǒng)成本影響不大。因此，在許多的論文中都是忽略不計的[15]。

圖9 輸出數(shù)據(jù)量系數(shù)對系統(tǒng)總成本的影響

5 結(jié)束語

本文為了降低C-V2X中計算任務(wù)的時延與能耗，提出一種自適應(yīng)的聯(lián)合計算卸載資源分配算法。所提算法相比之前的研究，綜合考慮了每個車輛任務(wù)的大小、最大容忍時延、當前路邊單元小區(qū)計算資源，網(wǎng)絡(luò)帶寬。并且能夠根據(jù)當前RSU的任務(wù)數(shù)自動調(diào)整卸載平臺和最優(yōu)卸載比例，在獲得卸載比例的同時對MEC的計算資源進行了分配。使用粒子群算法為基礎(chǔ)算法，改進了粒子編碼方式，加入了懲罰函數(shù)，和提出粒子修正算法對約束條件進行處理。通過實驗仿真，與其它算法相對比，本文所提算法能有效降低系統(tǒng)總成本。同時需要指出的是，本文只考慮了一個RSU下卸載的情況，下一步工作，將考慮多個RSU的協(xié)同卸載問題。