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

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

0 引 言

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

1 系統(tǒng)模型

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

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

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

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

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

(1)

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

(2)

1.2 任務(wù)模型

1.3 計(jì)算模型

1.3.1 本地計(jì)算模型

(3)

(4)

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

1.3.2 MEC計(jì)算模型

(5)

(6)

(7)

(8)

(9)

1.3.3 云計(jì)算模型

(10)

(11)

(12)

(13)

(14)

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

1.3.4 空閑車(chē)輛計(jì)算模型

(15)

(16)

(17)

(18)

(19)

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

2 問(wèn)題建模

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

(20)

(21)

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

(22)

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

(23)

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

3 算法設(shè)計(jì)

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

圖2 改進(jìn)粒子群算法流程

3.1 粒子編碼

圖3 粒子編碼矩陣

3.2 粒子修正算法

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

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

表1 粒子修正算法

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

圖4 粒子編碼矩陣修正后

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

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

將式(23)中的C2改寫(xiě)為

(24)

當(dāng)x≤0，是不進(jìn)行懲罰的，只有當(dāng)x>0時(shí)，才進(jìn)行懲罰，所以懲罰函數(shù)為

(25)

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

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

(26)

3.4 粒子速度與位置更新

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

(27)

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

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

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

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

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

文獻(xiàn)[6]算法：將整個(gè)計(jì)算任務(wù)分成3部分，分別在空閑車(chē)輛，MEC和本地計(jì)算。

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

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

表3 仿真參數(shù)

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

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

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

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

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

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

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

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

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

如圖9所示，隨著輸出數(shù)據(jù)量的增加，除了All-Local外所有算法的系統(tǒng)總成本都增加。因?yàn)楸镜赜?jì)算不存在計(jì)算結(jié)果的返回時(shí)延，所以All-Local算法的系統(tǒng)總成本保持不變，而其它算法的影響也較小，是因?yàn)橹挥行遁d到MEC，遠(yuǎn)端云，空閑車(chē)輛才有結(jié)果返回時(shí)延，而計(jì)算結(jié)果的返回量相對(duì)較小，所以對(duì)系統(tǒng)成本影響不大。因此，在許多的論文中都是忽略不計(jì)的[15]。

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

5 結(jié)束語(yǔ)

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