C-V2X車聯(lián)網(wǎng)中基于模擬退火算法的任務(wù)卸載與資源分配

李智，薛建彬

（蘭州理工大學(xué) 計算機與通信學(xué)院，蘭州 730050）

0 引言

車聯(lián)網(wǎng)（Internet of Vehicles，IoV）［1-3］技術(shù)是智能交通系統(tǒng)發(fā)展的主要支撐技術(shù)。IoV 技術(shù)以網(wǎng)聯(lián)車輛為移動感知對象終端，在通信網(wǎng)絡(luò)中實現(xiàn)多系統(tǒng)間交互，感知道路交通實時狀況，使智能交通平臺對道路和車輛進行全程實時控制，從而提高交通效率和交通安全性。由于車聯(lián)網(wǎng)無線通信環(huán)境差且網(wǎng)聯(lián)車輛自身資源受限，所以在傳輸與處理網(wǎng)聯(lián)車輛產(chǎn)生具有可分時延敏感特點的大數(shù)據(jù)流量計算任務(wù)過程中，帶來了時延抖動、計算能耗與通信系統(tǒng)開銷大等問題，目前已被相關(guān)專業(yè)技術(shù)人員密切關(guān)注。

為解決上述問題，將具備移動邊緣計算（Mobile Edge Computing，MEC）［4-6］功能的邊緣MEC 服務(wù)器，以C-RAN［7］方式部署在基站附近，可在網(wǎng)絡(luò)邊緣對大數(shù)據(jù)流量計算任務(wù)進行快速卸載和計算，從而降低通信時延、計算能耗及系統(tǒng)開銷。目前，基于MEC 的任務(wù)卸載和資源分配問題，研究人員紛紛提出了不同觀點。劉繼軍等［8］提出了資源分配與基于博弈論的任務(wù)卸載決策聯(lián)合優(yōu)化策略，提高了系統(tǒng)總增益。以降低通信時延為目的，譚友鈺等［9-10］分別提出了多邊緣MEC 服務(wù)器協(xié)作資源分配方案，與基于MEC 高能效任務(wù)卸載決策。Tran等［11］提出了多MEC 服務(wù)器啟發(fā)式聯(lián)合任務(wù)卸載和資源分配策略，從而提高了系統(tǒng)效用。Nguyen等［12］建立了數(shù)據(jù)冗余模型，充分利用MEC 服務(wù)器上的空閑資源對任務(wù)進行計算和分配，從而減少了網(wǎng)絡(luò)帶寬消耗。余翔等［13］針對高速公路場景，提出了一種基于行車方向，以車輛為節(jié)點進行車輛與車輛、人、網(wǎng)絡(luò)等間進行通信的環(huán)境中，每個車輛根據(jù)信道感知結(jié)果獨立選擇傳輸資源，并保留所選資源供今后使用的算法，對網(wǎng)絡(luò)資源進行合理分配，提高了資源分組接收率。薛建彬等［14］通過分析任務(wù)卸載系統(tǒng)中能量收集狀態(tài)及用戶功率分配狀態(tài)，提出了一種基于能量收集的系統(tǒng)能效優(yōu)化方案，提升了系統(tǒng)中用戶的能量效率。吳振銓等［15］為解決任務(wù)調(diào)度問題，提出了一種啟發(fā)式算法，采用移動設(shè)備局部最優(yōu)卸載策略，降低任務(wù)執(zhí)行延遲。楊天等［16］考慮二進制任務(wù)卸載模型，通過聯(lián)合優(yōu)化任務(wù)執(zhí)行位置，對基于精英選擇策略的遺傳算法做出了部分改進，設(shè)計了聯(lián)合卸載決策與資源分配算法，降低了系統(tǒng)成本。Chen等［17］采用博弈論方法，提出了一種基于MEC 的多用戶任務(wù)計算卸載方案，降低了任務(wù)卸載時延。路亞［18］提出一種多移動邊緣計算服務(wù)器啟發(fā)式聯(lián)合任務(wù)卸載和資源分配策略，從而最大化系統(tǒng)效用。Hamzah等［19］提出了一種位置感知任務(wù)加載策略，減少了任務(wù)處理時間及網(wǎng)絡(luò)時延。以降低系統(tǒng)開銷為目的，張海波等［20］提出一種基于Q 學(xué)習(xí)算法的任務(wù)卸載策略；閆偉等［21］提出一種基于自適應(yīng)遺傳算法的任務(wù)卸載和資源分配方案。

上述文獻關(guān)于任務(wù)卸載和資源分配問題，研究人員根據(jù)不同優(yōu)化目標，分別提出了不同解決方案，優(yōu)化了時延、能耗、帶寬等指標。但現(xiàn)有研究內(nèi)容均考慮二進制卸載模型，未考慮IoV 通信環(huán)境中實際情況，且任務(wù)卸載決策是個多目標優(yōu)化問題。目前針對任務(wù)卸載低時延、低計算能耗和最小化系統(tǒng)開銷等要求，現(xiàn)有方案優(yōu)化效果不佳，應(yīng)用上還需繼續(xù)優(yōu)化。本文設(shè)計以蜂窩通信（LTE-V-Cell）［22］為主的LTE-V2X［23-26］車聯(lián)網(wǎng)通信環(huán)境中任務(wù)按比例卸載的通信模型，利用模擬退火算法（Simulated Annealing Algorithm，SAA）確定最優(yōu)卸載比例因子。在上述過程中，將系統(tǒng)開銷最小化問題轉(zhuǎn)化為功率和計算資源分配凸優(yōu)化問題，并用拉格朗日乘子法獲取最優(yōu)解，進一步優(yōu)化網(wǎng)絡(luò)系統(tǒng)，從而降低任務(wù)傳輸時延、計算能耗及系統(tǒng)開銷，進而提高C-V2X（Cellular Vehicle to Everything）［27］車聯(lián)網(wǎng)中的通信效率。

1 系統(tǒng)模型

本文建立了LTE-V-Cell 通信模式的C-V2X 車聯(lián)網(wǎng)通信系統(tǒng)模型，如圖1 所示。模型中的設(shè)備包含：車輛、基站、路側(cè)單元（Road Side Unit，RSU）以及邊緣MEC 服務(wù)器。

首先，本文系統(tǒng)模型中各設(shè)備的作用介紹如下：

1）基站。基站具備無線接入控制功能，可對空中接口Uu 進行合理管理，同時可控制資源分配與調(diào)度。

2）邊緣MEC 服務(wù)器。邊緣MEC 服務(wù)器以C-RAN 方式部署在基站附近，將基帶資源、硬件協(xié)作化等進行集中化處理，實現(xiàn)協(xié)作式車輛與實時云計算結(jié)構(gòu)的網(wǎng)絡(luò)邊緣處理模式，降低網(wǎng)絡(luò)通信時延。

3）RSU 和車輛。RSU 處于基站和車輛之間，車輛可和RSU 進行通信。RSU 將任務(wù)傳輸?shù)竭吘塎EC 服務(wù)器上進行任務(wù)卸載和計算處理，即RSU 為車輛和邊緣MEC 服務(wù)器間數(shù)據(jù)通信提供全方位服務(wù)。

其次，將計算任務(wù)初步建模介紹如下：本文定義在道路上均勻部署了m個邊緣MEC 服務(wù)器和n個車輛，所有邊緣MEC 服務(wù)器部署集合可表示為M={Mm|m∈N+}，車輛節(jié)點部署集合可表示為N={Vn|n∈N+}。假設(shè)所有車輛均服從泊松分布，則網(wǎng)絡(luò)通信系統(tǒng)中第i個邊緣服務(wù)器下的第j個車輛，每次在某時刻可產(chǎn)生一個可分割待處理的密集型任務(wù)，將其表示為：其中，為車輛產(chǎn)生的任務(wù)數(shù)據(jù)量；為計算任務(wù)時CPU 周期數(shù)；為處理任務(wù)時可容忍的最大約束時延；為任務(wù)的價值量，任務(wù)的重要程度定義為值越大說明任務(wù)越重要。

最后，定義任務(wù)卸載比例因子如下：考慮將任務(wù)部分卸載到本地、部分卸載到邊緣MEC 服務(wù)器上，形成任務(wù)本地和邊緣MEC 服務(wù)器協(xié)同卸載模型。定義任務(wù)卸載到邊緣MEC服務(wù)器上的比例因子為；任務(wù)卸載到本地的比例因子為1 -，且0 ≤≤1。

2 計算模型

本文將任務(wù)卸載方式分成兩個部分：其一，任務(wù)卸載到本地；其二，任務(wù)卸載到邊緣MEC 服務(wù)器上。

2.1 本地卸載時延與能耗計算模型

其中：k為能量常量因子，由車輛自身芯片結(jié)構(gòu)決定大小。

2.2 邊緣MEC服務(wù)器卸載時延與能耗計算模型

任務(wù)經(jīng)邊緣MEC 服務(wù)器卸載需經(jīng)過三個步驟：1）任務(wù)上傳至邊緣MEC 服務(wù)器；2）任務(wù)在邊緣MEC 服務(wù)器上執(zhí)行計算；3）邊緣MEC 服務(wù)器將任務(wù)計算結(jié)果回傳給車輛。在此過程中產(chǎn)生相應(yīng)的任務(wù)傳輸時延、任務(wù)執(zhí)行計算時延、任務(wù)回傳時延。但由于任務(wù)經(jīng)過邊緣MEC 服務(wù)器一系列卸載計算處理后，將當(dāng)時結(jié)果回傳給車輛的任務(wù)數(shù)據(jù)量將遠遠小于原始任務(wù)數(shù)據(jù)量，因此忽略下行鏈路任務(wù)的回傳時延。下面將對任務(wù)卸載到邊緣MEC 服務(wù)器卸載的時延與能耗計算模型進行詳細介紹。

基于時分多址接入（Time-Division Multiple Access，TDMA）或正交頻分多址接入（Orthogonal Frequency Division Multiple Access，OFDMA）的多用戶MEC 系統(tǒng)，設(shè)計控制卸載數(shù)據(jù)大小和時間或子信道分配的最佳策略，可最小化卸載時延與系統(tǒng)能耗［28-29］。當(dāng)車輛節(jié)點和RSU 進行通信時，本文采用OFDMA 的多用戶MEC 系統(tǒng)，即每個車輛節(jié)點可在通信系統(tǒng)中與RSU 通過獨立信道進行信息傳輸，則任務(wù)卸載在邊緣MEC 服務(wù)器上的傳輸速率rMi，Vj可根據(jù)香農(nóng)公式定義為：

其中：fMi，Vj為邊緣MEC 服務(wù)器分配給車輛的計算資源。

3 問題描述

通過上述分析，考慮到C-V2X 車聯(lián)網(wǎng)中諸多應(yīng)用對時延、計算能耗及系統(tǒng)開銷要求非常高，本文利用時延權(quán)衡因子ζ和能耗權(quán)衡因子1 -ζ形成系統(tǒng)開銷最小化目標，使車輛在最大網(wǎng)絡(luò)帶寬限度內(nèi)進行任務(wù)卸載和資源分配。將系統(tǒng)開銷f(C)定義為任務(wù)卸載到本地的開銷與任務(wù)卸載到邊緣MEC 服務(wù)器的開銷之和。

其中，任務(wù)卸載到本地的開銷和任務(wù)卸載到邊緣MEC服務(wù)器開銷分別表示為：

本文采用組合優(yōu)化技術(shù)優(yōu)化系統(tǒng)開銷最小化目標，則目標函數(shù)表示為：

式（10）表示給定任務(wù)卸載比例因子的取值范圍；式（11）表示車輛到邊緣MEC 服務(wù)器上的傳輸功率不能超過車輛最大傳輸功率；式（12）表示任務(wù)卸載到邊緣MEC 服務(wù)器上可分配資源為非負數(shù)；式（13）表示給任務(wù)卸載分配的可計算資源大小不能超過邊緣MEC 服務(wù)器自身資源；式（14）表示所有車輛通信帶寬之和不可超過網(wǎng)絡(luò)帶寬B。

4 優(yōu)化模型

本文目標函數(shù)優(yōu)化問題屬于卸載比例因子、傳輸功率、計算資源分配多個目標優(yōu)化的困難問題，求解難度非常大，因此將系統(tǒng)開銷最小化問題進行拆分并逐一求解。由于任務(wù)部分卸載和二進制卸載模型相比，前者需要考慮子任務(wù)先后處理的順序問題，所以任務(wù)部分卸載時需設(shè)置任務(wù)處理優(yōu)先程度，對于優(yōu)先程度較高的任務(wù)優(yōu)先處理，對于優(yōu)先程度較低或不重要的任務(wù)，可上傳至蜂窩網(wǎng)絡(luò)云平臺進行遠處理。

4.1 任務(wù)處理優(yōu)先程度

由于不同車輛用戶需求不同，從而產(chǎn)生的計算任務(wù)屬性也大不相同，且邊緣MEC 服務(wù)器自身資源受限。在同一時刻，某一邊緣MEC 服務(wù)器不能在該協(xié)同域內(nèi)，對所有車輛節(jié)點產(chǎn)生的可分時延敏感型任務(wù)同時進行卸載計算。

針對可分時延敏感型任務(wù)需求，本文用任務(wù)處理優(yōu)先程度來確定車輛節(jié)點產(chǎn)生的計算任務(wù)是否為可分時延敏感型計算任務(wù)。針對任務(wù)處理優(yōu)先程度，設(shè)置了任務(wù)處理優(yōu)先程度閾值，用來表示。其中，定義可分時延敏感型計算任務(wù)處理優(yōu)先程度大于等于該閾值，可進行本地和邊緣協(xié)同卸載計算；而小于該閾值的計算任務(wù)視為任務(wù)處理優(yōu)先程度低或不重要任務(wù)，可將其上傳至蜂窩網(wǎng)絡(luò)云服務(wù)器中進行處理，避免網(wǎng)絡(luò)通信擁堵。該過程將在SAA 偽代碼中體現(xiàn)。

上述任務(wù)優(yōu)先程度定義為在某時刻，受任務(wù)處理最大可容忍約束時延條件限制，任務(wù)優(yōu)先處理的程度。本文用任務(wù)重要程度和任務(wù)處理最大可容忍約束時延來定義任務(wù)處理優(yōu)先程度，則構(gòu)建任務(wù)處理優(yōu)先程度的數(shù)學(xué)模型為：

其中：?為任務(wù)重要程度的權(quán)衡因子；1 -?為最大約束時延的權(quán)衡因子，且?∈[0，1]，可通過熵值法求解。

4.2 基于模擬退火算法的任務(wù)卸載

根據(jù)任務(wù)處理優(yōu)先程度，將優(yōu)先卸載的任務(wù)，按照一定比例卸載至本地和邊緣MEC 服務(wù)器進行任務(wù)卸載處理；同時優(yōu)化卸載比例因子，使得任務(wù)按照最優(yōu)卸載比例因子卸載到本地和邊緣MEC 服務(wù)器。本文采用模擬退火算法優(yōu)化卸載比例因子。該算法的原理是模擬固體從加熱狀態(tài)到冷卻整個過程中狀態(tài)的變化情況，從而解決與固體物質(zhì)退火過程相似的一般組合優(yōu)化問題。隨著溫度不斷降低，結(jié)合車輛泊松分布的概率，在最優(yōu)卸載比例因子解空間中隨機搜索系統(tǒng)開銷最小化的全局卸載比例因子最優(yōu)解，從而解決本文方案中的困難問題。該算法只與初始最高溫度、最小溫度以及退火次數(shù)有關(guān)。

模擬退火算法實現(xiàn)步驟如下：

1）輸入初始化參數(shù)。參數(shù)包括計算迭代次數(shù)、初始最高溫度以及終止溫度等。將初始溫度T=T0設(shè)置為一個較高的值，一般情況設(shè)置為1 000，且呈衰減狀態(tài)。內(nèi)循環(huán)迭代次數(shù)最大一般設(shè)置為50。隨機給定一個初始解，同時也是算法迭代的起點，最終計算目標函數(shù)值

2）內(nèi)部循環(huán)迭代次數(shù)依次遞增，如Lk=1，2，…，50，重復(fù)第3）步到第5）步。

其中，第5）步中的終止條件一般情況下會定義為：當(dāng)連續(xù)若干個新解都沒有被接受時，則算法終止。通過以上算法步驟可以看出，此過程是基于Metropolis 準則在某個最佳溫度下搜索最優(yōu)解，從理論上看，要經(jīng)過無數(shù)次迭代才搜索出最優(yōu)解，但實際上定義一個最大可迭代次數(shù)即可搜索出最優(yōu)解。

4.3 資源分配

為了保證任務(wù)經(jīng)過邊緣MEC 服務(wù)器成功卸載計算，且在通信過程中不會發(fā)生信息中斷現(xiàn)象，車輛任務(wù)卸載時延需小于或等于網(wǎng)聯(lián)車輛節(jié)點在當(dāng)前所屬協(xié)同域內(nèi)的停留時間。其中，網(wǎng)聯(lián)車輛節(jié)點在當(dāng)前所屬協(xié)同域內(nèi)的停留時間由車輛移動速度來決定。在這樣的條件限制下，可獲得最佳功率和計算資源。

在資源分配問題中，由于車輛傳輸功率和計算資源之間不存在相互約束因子，因而不能進行聯(lián)合優(yōu)化，因此可將資源分配問題拆分成最優(yōu)任務(wù)卸載比例因子下對傳輸功率和計算資源各自優(yōu)化的兩個問題。

4.3.1 功率優(yōu)化

通過對資源分配問題進行分解，可將式（17）中功率優(yōu)化問題表示為：

通過對傳輸功率最小化函數(shù)凸優(yōu)化分析，可將傳輸功率優(yōu)化目標函數(shù)重新改寫：

此時新優(yōu)化目標函數(shù)式（20）為凸優(yōu)化問題，用拉格朗日乘子法進行求解。拉格朗日乘子法可將難解的NP-hard 問題中相關(guān)約束條件吸收到目標函數(shù)中去，使得目標函數(shù)保持線性關(guān)系并求最優(yōu)解。

根據(jù)式（20）凸優(yōu)化問題構(gòu)建拉格朗日函數(shù)為：

其中：β為目標函數(shù)約束條件式（11）中相對應(yīng)的拉格朗日乘子，且β≥0。

利用KKT（Karush-Kuhn-Tucker）條件求解式（21）在處取極值時的充分必要條件，可得：

根據(jù)KKT 條件可得最優(yōu)解為：

4.3.2 計算資源優(yōu)化

通過對資源分配問題進行分解，將式（17）中計算資源優(yōu)化問題表示為：

根據(jù)式（25）凸優(yōu)化問題構(gòu)建該優(yōu)化函數(shù)的拉格朗日函數(shù)為：

其中：λ為目標函數(shù)約束條件式（12）中相對應(yīng)的拉格朗日乘子；而μ是目標函數(shù)約束條件式（13）中相對應(yīng)的拉格朗日乘子，且λ≥0，μ≥0。

利用KKT 條件求解式（25）在處取極值時的充分必要條件，求得最優(yōu)解，Vj為：

4.4 SAA偽代碼

5 仿真實驗與結(jié)果分析

考慮1 個RSU 和1 個邊緣MEC 服務(wù)器可形成1 個協(xié)同域，則多個RSU、邊緣MEC 服務(wù)器與多個車輛節(jié)點可構(gòu)成多個協(xié)同域覆蓋道路通信場景。在該場景中某時刻下，一個車輛節(jié)點可產(chǎn)生一個計算任務(wù)，因此任務(wù)數(shù)和車輛節(jié)點數(shù)目相同。為了簡化仿真，將車輛節(jié)點數(shù)目設(shè)定為40，而將邊緣MEC 服務(wù)器和RSU 各設(shè)定為5個，從而搭建MEC 仿真場景。任務(wù)數(shù)據(jù)量為（400～1 200）KB；任務(wù)計算CPU 周期數(shù)為（0.2～1.0）GHz；車輛本地卸載計算能力為1 GHz；能量系數(shù)k=1 × 10-26；網(wǎng)絡(luò)帶寬B為20 MHz；鏈路增益由路徑損耗生成，如下所示：

其中：噪聲功率σ2為-100 dBm；邊緣MEC 服務(wù)器自身資源fMEC為20 GHz；時延因子ζ為0.2；初始溫度T0為1 000°，溫度衰減系數(shù)α為0.95，衰減系數(shù)值越大降溫越慢，導(dǎo)致迭代次數(shù)增加但會找到全局最優(yōu)解。

圖8 為迭代次數(shù)與系統(tǒng)開銷之間的關(guān)系圖。由圖8 可知，本文所提模擬退火算法和基于Q-學(xué)習(xí)卸載策略均可經(jīng)過多次迭代，達到系統(tǒng)開銷最小化目標。其中，基于Q-學(xué)習(xí)卸載策略在迭代過程中存在局部最優(yōu)解，使系統(tǒng)開銷收斂速度較慢，且最終優(yōu)化目標效果不佳。本文算法經(jīng)過多次迭代可迅速達到系統(tǒng)開銷最小化目標，且收斂速度快。由圖8 可得基于Q-學(xué)習(xí)卸載策略和本文算法的平均系統(tǒng)開銷分別為：196.567 0、76.741 6。綜上所述可得：1）本文算法比基于Q-學(xué)習(xí)卸載策略的系統(tǒng)開銷降低了60.96%；2）相較于基于Q-學(xué)習(xí)卸載策略，本文算法可更快實現(xiàn)LTE-V-Cell 車聯(lián)網(wǎng)通信系統(tǒng)中系統(tǒng)開銷最小化目標，本文算法可加速收斂且優(yōu)化效果最佳。

6 結(jié)語

智能交通成為當(dāng)今智慧城市交通發(fā)展的關(guān)鍵技術(shù)，未來汽車工業(yè)在智慧城市的推動發(fā)展中，對網(wǎng)聯(lián)車輛通信方面高帶寬、低時延、高可靠等要求會越來越高，這些要求是目前MEC 技術(shù)與車聯(lián)網(wǎng)技術(shù)融合發(fā)展的關(guān)鍵研究目標。由于本文方案考慮到車聯(lián)網(wǎng)中實際情況，采用任務(wù)比例卸載計算模型，利用搜索全局最優(yōu)解的模擬退火算法，將任務(wù)按照最佳比例協(xié)同卸載在本地和邊緣MEC 服務(wù)器，同時實現(xiàn)在LTE-V-Cell 車聯(lián)網(wǎng)通信系統(tǒng)中，對資源統(tǒng)一調(diào)度與分配，最小化時延、計算能耗及系統(tǒng)開銷，進而實現(xiàn)時延敏感型大數(shù)據(jù)流量的快速處理、共享和交互，給車輛用戶提供最佳的服務(wù)體驗，可有效降低事故發(fā)生，提高交通效率，確保本文研究與現(xiàn)實車聯(lián)網(wǎng)環(huán)境中的運行情況更加貼切，從而達到更高的資源利用，綜上所述本文方案最佳、最有效。下一步將考慮現(xiàn)實環(huán)境中，若在RSU 覆蓋范圍之外存在計算能力更強的車輛節(jié)點時，大數(shù)據(jù)流量任務(wù)還會進行細分，則車輛節(jié)點間可進行協(xié)同通信；同時也將考慮在任務(wù)卸載過程中，會存在多協(xié)同域間通信覆蓋或遷移現(xiàn)象，在下一步的研究中將引入網(wǎng)絡(luò)切換技術(shù)，實現(xiàn)更高的技術(shù)實用性。