車聯網中自適應聯合計算卸載資源分配算法

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

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

0 引 言

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

1 系統模型

1.1 網絡模型

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

圖1 網絡模型

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

車輛vi與BS之間的上傳/下載的數據速率為

(1)

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

(2)

1.2 任務模型

1.3 計算模型

1.3.1 本地計算模型

(3)

(4)

其中，Pi表示車輛vi的設備功率。

1.3.2 MEC計算模型

(5)

(6)

(7)

(8)

(9)

1.3.3 云計算模型

(10)

(11)

(12)

(13)

(14)

其中，Pcloud表示遠端云服務器的設備功率，PBS表示基站的發射功率。

1.3.4 空閑車輛計算模型

(15)

(16)

(17)

(18)

(19)

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

2 問題建模

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

(20)

(21)

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

(22)

其中，γ為時延權重系數，(1-γ)為能耗權重系數。可根據移動服務的需求及移動設備的狀態來設置。例如，當運行時延敏感型移動服務時，可以適當增加γ的值。

(23)

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

3 算法設計

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

圖2 改進粒子群算法流程

3.1 粒子編碼

圖3 粒子編碼矩陣

3.2 粒子修正算法

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

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

表1 粒子修正算法

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

圖4 粒子編碼矩陣修正后

3.3 罰函數法構造適應度函數

罰函數法可以將約束優化問題轉換為非約束優化問題。該方法通過創建兩個約束函數，加入懲罰因子，然后將它們添加到約束優化問題的目標函數中創建懲罰函數[11,12]。

將式(23)中的C2改寫為

(24)

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

(25)

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

適應度函數為目標函數加上懲罰函數

(26)

3.4 粒子速度與位置更新

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

(27)

4 仿真結果與分析

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

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

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

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

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

改進的PSO-X算法的參數設置見表2，所提算法的相關仿真參數見表3。

表2 PSO-X算法相關參數

表3 仿真參數

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

圖5 空閑車輛數對平均每輛車系統成本的影響

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

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

圖6 計算任務量對系統總成本的影響

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

圖7 車輛數對系統總成本的影響

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

圖8 帶寬對系統總成本的影響

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

圖9 輸出數據量系數對系統總成本的影響

5 結束語

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