基于模擬退火機制的車輛用戶移動邊緣計算任務卸載新方法

張德干 李 霞* 張 捷 張 婷 龔倡樂

①(天津理工大學天津市智能計算及軟件新技術重點實驗室 天津 300384)

②(天津體育學院體育經濟與管理學院 天津 301617)

③(北京交通大學電子信息工程學院 北京 100044)

1 引言

隨著物聯網的普及以及物聯網技術的不斷升級，智能交通的建設也被廣為關注，從而衍生出了以車輛自組織網絡(Vehicular Ad hoc NETworks,VANET)為代表的移動物聯網[1,2]。車聯網(Internet Of Vehicles,IOV)主要指的是車載設備通過無線通信的技術，對于所能獲得到的所有車輛動態信息進行有效利用，從而在車輛移動的過程中提供各種不同的服務[3]。車聯網的特征主要體現在了：能夠在車與車之間提供有效的距離保障，幫助用戶進行實時導航，通過與其他車輛的實時通信來提高交通運行的效率，以及降低車輛發生碰撞事故的概率[4-6]。

考慮到車聯網中對于信息處理的實時性的要求，如果將所有的信息處理都放在云平臺去執行，無法滿足低延遲以及高質量的服務要求[7-9]。移動邊緣計算(Mobile Edge Computing, MEC)技術的出現將云計算和服務擴展到了網絡邊緣，由于靠近設備本身，保證了信息處理的實時性，提高了數據傳輸的性能[10-13]。通過采用MEC技術，可以部署邊緣服務器等輕量級的基礎設施，將云平臺的計算任務放在邊緣服務器上執行，從而減輕云平臺的任務執行壓力，給用戶帶來更高質量的服務。但是如果所有用戶將其任務都進行卸載，也會給MEC服務器的計算能力帶來很大的壓力。任務卸載決策成為實現高效計算卸載關鍵性問題[14,15]。

在任務卸載策略中，時耗以及能耗是需要著重考慮的兩個方面。Oueis等人[16]提出了一種用于小型蜂窩云計算的負載分配方法，但是在多用戶場景下的時間消耗上未做過多考慮。通過綜合考慮資源的分配以及計算方式，Wei等人[17]提出了貪婪策略的任務卸載算法，但該算法在節約能量的同時容易導致服務器任務堆積而增大時耗。Tran等人[18]分析出任務卸載的目標問題是混合整數非線性規劃問題(Mixed Integer Nonlinear Layout Problems, MINLP)，將每個用戶的卸載方式從任務完成時間以及設備能耗兩方面進行考慮，但是并未與車聯網環境下的計算任務特殊性相結合。Kao等人[19]考慮到移動邊緣計算當中資源的有限性，結合在線學習的方法來減小任務時延方面的問題，但是在與移動邊緣計算技術相結合上需要更進一步對時耗和能耗進行平衡。

本文提出基于模擬退火機制的車輛用戶移動邊緣計算任務卸載新方法，主要工作如下：(1)通過定義用戶的任務計算卸載效用，綜合考慮時耗和能耗；(2)結合模擬退火機制，根據當前道路的密集程度對系統卸載效用進行優化，改變用戶的卸載決策，選擇在本地執行或者卸載到邊緣服務器上執行。仿真結果表明，本算法在給定的環境下使所有用戶都能得到滿足低時延高質量的服務。在減少用戶任務計算時間的同時降低了能量消耗。

2 基本原理

2.1 場景模型

如圖1所示，場景設置在車輛密集的十字路口，在十字路口有多個路邊設備(RoadSide Units, RSU)，并且都配置有MEC服務器，將其看作一個服務器群。周圍的車輛(Vehicle)就是移動的用戶，用戶可以與服務器群中的任意一個進行通信并將任務資源卸載到服務器上。因此，可以將用戶以及服務器群進行如下定義：V=(1,2,...,v)，M=(1,2,...,m)，由于將RSU與MEC進行了一一對應，所以均可以用m∈M進行代替。

圖1 場景模型

2.2 用戶計算任務

2.3 本地執行任務

定義1 本地任務執行時間。

每個計算任務既可以在本地(Local)執行，也可以卸載到邊緣服務器上，雖然將任務卸載到邊緣服務器會減輕本地計算的消耗，但是相應地，在上傳相應任務的時候，會增加耗時以及部分上傳的能量消耗。將所有車輛用戶的類型進行統一化，用戶在本地執行計算的能力是相同的，可以定義為lv[cycles/s]，結合每個任務所需要的計算資源，可以得到，用戶v如果在本地執行計算任務Tv，需要的時間如式(1)所示

2.4 任務卸載到邊緣服務器

如果將任務上傳到服務器，會增加任務時間消耗，主要可以將時間分作傳輸時間以及在服務器上執行的時間，同時計算任務的執行也會產生能量的消耗。

定義3 任務傳輸時間。

在車聯網中，主要采用了短程通信技術，提供車輛以及基礎設備之間的雙向短程通信[22]。在專用短程通信技術(Dedicated Short Range Communications, DSRC)體系結構中，每輛車上備有車載設備(On-Board Unit, OBU)，相當于移動終端設備，具有一定的數據處理能力，同時，在馬路上還部署了相應的路邊單元RSU，為車輛提供數據訪問服務[9,23]。

DSRC的底層技術主要是采用了正交頻分復用(Orthogonal Frequency Division Multiplexing,OFDM)的技術[24,25]。如果只使用1個信道來傳輸信號將造成資源浪費的情況，因此OFDM將信道劃分成了若干個正交的子信道用于傳輸。另外，正交頻分多址(Orthogonal Frequency Division Multiple Access, OFDMA)技術如圖2所示，作為OFDM的演進，利用OFDM對信道進行子載波化后，在部分子載波上加載傳輸數據，從而用戶可以選擇信道條件較好的子通道來進行數據傳輸，可以保證各個子載波都被對應信道較優的用戶使用，獲得了頻率上的分集增益。

圖2 OFDM與OFDMA工作模式對比

假設將帶寬B劃分成N個相同的子頻帶，則每個大小為，W=B/N(Hz)，在車聯網通信網絡的物理層中，結合OFDM技術，劃分出了7個10 MHz的子信道用于傳輸，因此可以看作每個服務器有7條子信道。

綜上所述，當用戶選擇將計算任務卸載到邊緣服務器執行時，將消耗的總時間為

3 用戶任務卸載效用

結合之前的規定，可以得到如下的約束：

(1)車輛用戶在任務執行方式的選擇上，可以考慮在本地執行或者是傳輸到邊緣服務器上；

(2)同一個邊緣服務器可以同時處理多個用戶的計算任務；

(3)在范圍內可以選擇某個邊緣服務器的任一子頻帶進行數據的傳輸；

(4)如果用戶選擇將計算任務卸載到某服務器，但是當前服務器因為負載過多導致用戶卸載效用過低時，則不執行任務卸載。

對式(13)進行擴展后，可以做出如式(14)的公式

4 算法描述

4.1 模擬退火機制的相關定義

模擬退火是一種啟發式的算法，同時也是一種貪心算法，不同的是，在搜索的過程中，由于引入了隨機因素，因此在迭代更新可行解時，會有一定的概率去接受一個比當前值要差的元素，因此模擬退火算法是可以跳出局部最優解，從而求得全局最優解[26]。在本文做出如下定義：

定義6 初始溫度T0，模擬退火算法開始的溫度，在本文將用戶車輛的數量看作初始溫度，即

T0=V。

定義7 降溫系數α，根據文獻，采用指數式的下降方式，因此有T(n+1)=αT(n) ，α為降溫系數，取值為0.8～0.99[27]。

定義8 終止溫度，如果在若干次迭代的情況下沒有可以更新的狀態，或者達到了設定的終止溫度，則認為退火完成。

定義9 降溫概率，假設當前狀態為f(n)，在下一時刻狀態變為f(n+1)， 則定義系統由f(n)變為f(n+1)的概率為

4.2 初始卸載策略

在滿足定義的卸載約束條件的情況下，根據式(12)選擇滿足自身卸載效用最大的方式執行任務，以此來得到初始卸載策略，即初始溫度。變量符號及含義見表1。初始卸載策略算法如表2所示。

表1 變量符號及含義

表2 生成初始溫度(算法1)

4.3 狀態轉換機制

狀態轉換就是在滿足設定的約束的條件下，用戶選擇計算任務執行方式的集合，通過隨機概率，改變用戶的計算任務執行方式，即是否執行卸載以及選擇卸載的子頻帶，來建立新的卸載策略。

4.4 基于模擬退火機制的邊緣計算任務卸載算法

綜上所述，本節所提基于模擬退火機制的邊緣計算任務卸載算法(Task Offloading algorithm with MEC based on Simulated Annealing,TOSA)的執行步驟如下：

(1)根據邊緣服務器的通信范圍，得到處于通信范圍內的車輛用戶數量，得到初始溫度；

(2)根據式(12)，結合定義的用戶卸載約束，通過算法1構建用戶卸載的初始策略，并根據式(15)計算出初始的系統卸載效用；

(3)若沒有達到設定的終止溫度，在規定的迭代次數范圍內，通過表3所示的算法2，獲得新的卸載策略，再根據式(15)計算出新的系統卸載效用；

表3 狀態轉換(算法2)

(4)通過對比本次及上次系統卸載效用的值，如果大于上次系統卸載效用，則接受此次卸載策略，并更新函數的當前解，否則根據式(16)得到降溫概率p，并產生一個均勻分布的隨機數，如果p大于隨機數，則接受卸載策略，否則放棄此次卸載策略；

(5)根據降溫系數，調整當前溫度，重復執行步驟(2)-步驟(4)；

(6)當達到終止溫度或者規定的迭代次數，終止退火，此時得到的用戶卸載效用即是函數的最優解。邊緣計算卸載算法如表4所示。

表4 基于模擬退火機制的邊緣計算任務卸載算法(算法3)

5 算法測試仿真與分析

5.1 測試仿真環境設置

本實驗使用了MATLAB平臺，對本文設置的算法TOSA進行測試。通過對比在不同時間段(即不同車流量環境)，不同數量的服務器以及不同大小的計算任務3個方面進行考慮，并與其他任務卸載方法進行對比，實驗證明，TOSA算法在時耗和能耗方面都有一定的提升。環境變量設置如表5所示。

表5 仿真參數

5.2 實驗結果與分析

圖3和圖4為在用戶對于時耗和能耗的選擇偏好不同情況下(即權重λ1,λ2的選擇)將計算任務卸載到MEC服務器上執行的情況。根據圖3可以得出，隨著用戶對于時耗偏好的增加，平均每個用戶在執行計算任務時所消耗的時間均有所下降，并且車流量越大，計算時間下降得越明顯。這是因為在低車流量的場景下，MEC服務器的工作負載并不大，因此用戶將計算任務卸載到MEC服務器上執行時不會產生過大的擁塞，因此每個用戶的任務計算執行時間改善并不明顯。但是隨著車流量的增大，如果所有用戶都將任務卸載到MEC服務器上去執行，同樣會給邊緣服務器帶來巨大的負載，而且會導致計算任務的阻塞，增加任務計算時間。在用戶執行計算任務時如果更加偏向于選擇更短的時耗的情況下，TOSA算法會調整用戶卸載效用的計算權值，改變部分用戶的卸載決策，因此優化了用戶的任務計算時間。從圖3可知，在高車流量場景下，當用戶對于時間的偏好到達最大值時，平均每個用戶的任務計算時間下降了72%。

圖3 不同時耗偏好下任務計算時間

圖4是時耗偏好值不同情況下用戶能效消耗示意圖，可以看出隨著用戶對于時間偏好的增加，用戶的任務執行能耗均增加了，在車流量較大的環境下，用戶能量消耗增大得越明顯。這是因為在低車流量的場景下，大部分用戶都選擇將計算任務卸載到MEC服務器上去執行，并不會產生較大的任務執行能耗，而只有傳輸的能耗。另外，當用戶的時耗偏好值加大，TOSA會更加關注任務計算的時間，即減小能耗的權值，因此在任務卸載的決策上會選擇時耗更小的方案，如將任務放在本地執行，導致任務執行的能耗會加大。在車流量較大的情況下，MEC服務器有較大的負載，所以為了降低時耗，將有更多任務在本地執行，因此能量消耗增加更明顯。

圖4 不同時耗偏好下任務能量消耗

圖5、圖6以及圖7是在不用數量的MEC服務器情況下，用戶通過TOSA、貪婪算法任務卸載(Select Maximum Saved Energy First, SMSEF)以及使用局部搜索算法優化任務卸載(Local Search Optimization algorithm, LSO)將計算任務進行卸載的時耗、能耗以及用戶卸載效用的對比圖。

圖5是在兩種車流量環境下，不同MEC服務器數量的用戶執行計算任務的能耗示意圖，由圖可知，因為SMSEF主要從用戶的計算任務能量消耗上進行了優化，會盡可能地選擇將任務卸載到MEC服務器上，因此用戶自身的能量消耗并不大。但是本文所提出的TOSA算法以及LSO算法綜合考慮了計算任務執行的時耗以及能耗兩個方面，因此能量消耗相對較高，在車流量較大的環境下，TOSA,LSO以及SMSEF算法的用戶能量消耗均有明顯增大。另外，隨著MEC服務器數量的增加，3種算法在能量消耗上都有所降低。在MEC服務器數量達到最大值時，TOSA算法相比于LSO算法能耗降低了45%。

圖5 不同MEC服務器數量下能耗對比圖

圖6是在兩種車流量環境下任務計算時間對比圖，從中可以看出，隨著MEC服務器數量的增加，有更多的計算任務可以卸載到MEC服務器上執行，因此時耗均有所降低。其中SMSEF算法從用戶能耗方面考慮會盡可能將任務卸載到MEC服務器上執行，因此當服務器數量不多的時候會帶來任務阻塞，導致任務計算時間加長，其中在車流量較大的環境下表現更為明顯，本文提出的TOSA算法隨著MEC服務器數量的增加，任務計算時間總體下降24%，比SMSEF算法低約55%，比LSO算法低約33%。

圖6 不同MEC服務器數量下時耗對比圖

結合時耗和能耗兩方面，圖7展示了3種算法的計算任務卸載效用。由圖可以看出，當MEC數量較少時，低車流量環境下SMSEF算法由于只考慮了能量的消耗，所以任務卸載效用遠低于TOSA算法和LSO算法，高車流量環境下，SMSEF算法因為只考慮了能量消耗而忽略的時間消耗，根據式(12)-式(15)可以得到在這種情況下任務卸載效用小于0，即并不適合進行任務卸載。隨著MEC服務器數量的增加，3種算法的任務卸載效用均有所提高，其中本文所提出的TOSA算法綜合考慮了時耗和能耗兩方面，因此在任務卸載效用上表現優于其他兩種算法，在車流量較大的環境下表現更加明顯。在服務器數量達到最大時，任務卸載效用比LSO算法高40%，比SMSEF算法高29%。

圖7 不同MEC服務器數量下用戶任務卸載效用對比圖

圖8、圖9、圖10是在不同車流量的情況下，3種算法對兩個大小的計算任務的卸載決策比較，且認為用戶在時耗與能耗的偏好值是相同的，即λ1=λ2=1/2。從圖8可以看出，在MEC服務器數量固定的情況下，隨著車流量和計算任務大小的增大，3種算法在任務計算時間上均增大，當計算任務大小增加時，SMSEF算法的任務計算時間明顯加劇。這是因為SMSEF將大量任務卸載到MEC服務器上執行，造成了計算任務的時耗加大。在達到最大車流量時，TOSA算法的時耗比LSO算法低7.8%，比SMSEF算法低60%。

圖8 不同車流量下時耗對比圖

圖9展示了車流量對于用戶能量消耗的影響。用戶的能量消耗隨著車流量的增加而增加，在均勻考慮時耗和能耗偏好值的情況下，TOSA算法會將用戶的計算任務選擇在本地執行，因此加大了用戶的能量消耗。但是在最大車流量時，TOSA算法的能量消耗比LSO算法低21%。

圖9 不同車流量下能耗對比圖

綜合任務計算時間以及用戶能量消耗，圖10展示了車流量對于用戶卸載效用的影響。在仿真實驗中，3種算法的用戶卸載效用隨著車流量環境的改變均有所增大，但是面對較大計算任務時用戶卸載效用略微低于小型計算任務，這也說明了MEC服務器主要適用于處理計算量不大的任務。當使用SMSEF算法處理較大計算量任務時，根據圖8所示任務計算時間過大，因此綜合對比下任務卸載效用小于0不適合進行任務卸載，相比之下，其中TOSA算法的卸載效用表現最佳。當處于中等車流量的環境時，LSO算法的卸載效用相比于TOSA算法和SMSEF算法表現欠佳，但是當車流量繼續增加時，SMSEF算法的用戶卸載效用明顯下降約68%，LSO算法的用戶卸載效用下降約22%，TOSA算法的用戶卸載效用相對穩定。圖11描述了1 d時間長度內車流量統計圖。

圖10 不同車流量下用戶卸載效用對比圖

圖11 1 d時間長度內車流量統計圖

圖12和圖13是根據1 d時間長度內車流量統計圖，結合對車輛用戶的時耗和能耗偏好值，選取λ1=0.3 ，λ2=0.7 (更偏向于能耗)和λ1=0.7 ，λ2=0.3(更偏向于時耗)進行對比得到的3種算法1 d內任務計算時間及任務能量消耗對比圖。

圖12是在1 d時間長度內3種算法在不同偏好值情況下任務計算時間示意圖。由此可知，隨著1 d內車流量的變化，任務計算時間處于先升后降的趨勢，其中SMSEF算法沒有考慮時間消耗的問題，所以總體高于其他兩種算法，且不穩定變化較大。另外，本文提出的TOSA算法在1 d時間內的任務計算時間均優于LSO算法，在卸載決策偏向于時耗的情況下(λ1=0.7)，TOSA算法的平均任務計算時間比LSO算法低約12%。

圖12 1 d時間長度內任務計算時間對比圖

圖13是在不同偏好值情況下，1 d時間長度內3種算法的用戶能量消耗示意圖。可以看出TOSA以及LSO算法在高車流量的時間段能量消耗更高，這是因為車流量較大時，部分計算任務會直接在本地執行，因此增加了能量的消耗，當決策偏向于能耗時(λ1=0.3)能量消耗有所下降，TOSA算法的平均用戶能量消耗比LSO算法低約42%。

6 結束語

本文提出一種基于模擬退火機制的車輛用戶移動邊緣計算任務卸載新方法，在車流量密集的十字路口環境下，通過定義用戶卸載效用，綜合考慮用戶在執行計算任務時的能耗以及時耗兩個方面，并利用模擬退火算法對用戶卸載效用進行優化，得到不同時間段，即不同車流量環境且符合用戶偏好的任務卸載決策。實驗證明TOSA算法可以有效的優化用戶的任務卸載決策，改善任務的能量消耗以及計算時間。