C-V2X車聯網中基于模擬退火算法的任務卸載與資源分配

李智，薛建彬

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

0 引言

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

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

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

1 系統模型

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

首先，本文系統模型中各設備的作用介紹如下：

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

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

3）RSU 和車輛。RSU 處于基站和車輛之間，車輛可和RSU 進行通信。RSU 將任務傳輸到邊緣MEC 服務器上進行任務卸載和計算處理，即RSU 為車輛和邊緣MEC 服務器間數據通信提供全方位服務。

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

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

2 計算模型

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

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

其中：k為能量常量因子，由車輛自身芯片結構決定大小。

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

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

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

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

3 問題描述

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

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

本文采用組合優化技術優化系統開銷最小化目標，則目標函數表示為：

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

4 優化模型

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

4.1 任務處理優先程度

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

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

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

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

4.2 基于模擬退火算法的任務卸載

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

模擬退火算法實現步驟如下：

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

2）內部循環迭代次數依次遞增，如Lk=1，2，…，50，重復第3）步到第5）步。

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

4.3 資源分配

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

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

4.3.1 功率優化

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

通過對傳輸功率最小化函數凸優化分析，可將傳輸功率優化目標函數重新改寫：

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

根據式（20）凸優化問題構建拉格朗日函數為：

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

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

根據KKT 條件可得最優解為：

4.3.2 計算資源優化

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

根據式（25）凸優化問題構建該優化函數的拉格朗日函數為：

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

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

4.4 SAA偽代碼

5 仿真實驗與結果分析

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

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

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

6 結語

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