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

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

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

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

1 引言

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

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

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

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

2 基本原理

2.1 場景模型

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

圖1 場景模型

2.2 用戶計算任務(wù)

2.3 本地執(zhí)行任務(wù)

定義1 本地任務(wù)執(zhí)行時間。

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

2.4 任務(wù)卸載到邊緣服務(wù)器

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

定義3 任務(wù)傳輸時間。

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

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

圖2 OFDM與OFDMA工作模式對比

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

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

3 用戶任務(wù)卸載效用

結(jié)合之前的規(guī)定，可以得到如下的約束：

(1)車輛用戶在任務(wù)執(zhí)行方式的選擇上，可以考慮在本地執(zhí)行或者是傳輸?shù)竭吘壏?wù)器上；

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

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

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

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

4 算法描述

4.1 模擬退火機制的相關(guān)定義

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

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

T0=V。

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

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

定義9 降溫概率，假設(shè)當前狀態(tài)為f(n)，在下一時刻狀態(tài)變?yōu)閒(n+1)， 則定義系統(tǒng)由f(n)變?yōu)閒(n+1)的概率為

4.2 初始卸載策略

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

表1 變量符號及含義

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

4.3 狀態(tài)轉(zhuǎn)換機制

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

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

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

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

(2)根據(jù)式(12)，結(jié)合定義的用戶卸載約束，通過算法1構(gòu)建用戶卸載的初始策略，并根據(jù)式(15)計算出初始的系統(tǒng)卸載效用；

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

表3 狀態(tài)轉(zhuǎn)換(算法2)

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

(5)根據(jù)降溫系數(shù)，調(diào)整當前溫度，重復執(zhí)行步驟(2)-步驟(4)；

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

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

5 算法測試仿真與分析

5.1 測試仿真環(huán)境設(shè)置

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

表5 仿真參數(shù)

5.2 實驗結(jié)果與分析

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

圖3 不同時耗偏好下任務(wù)計算時間

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

圖4 不同時耗偏好下任務(wù)能量消耗

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

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

圖5 不同MEC服務(wù)器數(shù)量下能耗對比圖

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

圖6 不同MEC服務(wù)器數(shù)量下時耗對比圖

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

圖7 不同MEC服務(wù)器數(shù)量下用戶任務(wù)卸載效用對比圖

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

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

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

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

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

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

圖11 1 d時間長度內(nèi)車流量統(tǒng)計圖

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

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

圖12 1 d時間長度內(nèi)任務(wù)計算時間對比圖

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

6 結(jié)束語

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