停車輔助的車輛邊緣計算中的雙重任務卸載設計

孫麒惠，朱金奇，花季偉，王振川，鄭 敏，魏艷敏

(天津師范大學 計算機信息工程學院，天津 300387)

0 引 言

將移動邊緣計算(mobile edge computing，MEC)技術引入車聯網，利用邊緣服務器為車輛提供邊緣計算服務，稱為車輛邊緣計算(vehicular edge computing，VEC)[3]，但邊緣服務器的資源有限[4]，當大量車輛任務產生時，邊緣服務器無法為車輛提供足夠的計算資源，特別是在交通流量密度很高的情況下。

受城市中停放車輛高密集分布且具有大量閑置計算資源的啟發，我們提出讓停放車輛輔助邊緣服務器，執行移動車輛產生的計算任務。為此，首先把路邊停放車輛組織成停車簇，停車簇作為虛擬邊緣服務器參與任務的卸載執行，從而極大緩解邊緣服務器資源受限的問題。其次，提出自上而下的任務優化分配方案，把任務合理的分配到各停車簇和邊緣服務器，以最小化卸載任務總的完成時間。對于分配到各停車簇的任務，在考慮停放車輛的能耗、收益以及任務完成延遲的基礎上，我們進一步提出簇內任務分配算法，為各卸載任務選擇最佳的停放車輛。通過上述雙重任務分配策略，既保證了卸載任務的服務質量，又使停放車輛的收益最大化，同時降低停放車輛的能耗開銷。仿真實驗結果表明，與其它幾種分配策略相比，本文所提任務分配方法具有較高的性能。

1 相關工作

已有VEC任務卸載相關研究主要分成兩類，其中大部分是通過集中式方式實現任務的分配，即存在一個控制器(或服務器)用來做全局任務分配決策。例如文獻[5]提出了一種異構感知的任務分配方案，該方案可以將相互依賴的任務映射到具有異構硬件和運行環境的設備上，從而共同降低任務延遲和能耗。文獻[6]中，作者基于半馬爾可夫決策過程(SDMP)提出了車輛云中的集中式任務卸載和資源分配問題，目的是使車輛的總報酬最大化。文獻[7]中，作者提出一種新任務調度模型為每個請求的任務分配服務器，從而使總響應時間最小化。文獻[8]提出在軟件定義網絡中，設計性能增強型路由協議管理車輛網絡資源，控制器根據車輛的拓撲結構在基站間分配信息。文獻[9]分析了邊緣計算環境下的車輛通信模式選擇,作者根據K-means聚類算法和非支配排序遺傳算法得出最優任務卸載決策。文獻[10]中，道路上的所有停放車輛中選擇一個中心車輛執行的任務調度算法，為各個任務分配計算資源以便任務及時執行并保證車輛的使用率最大化。然而集中式方案通常沒有考慮各個邊緣設備在執行邊緣計算中各自利益的問題。

考慮到依賴于中央決策者進行任務分配方式的不足，部分研究采用分布式進行任務分配。比如文獻[11]中提出了一種知識驅動(KD)的服務卸載框架，作者著眼于邊緣節點類型，采用A3C算法在邊緣節點上訓練每種服務的卸載決策模型，然后將其分發給車輛。車輛在運行服務時，執行異步在線學習使時延最小。文獻[12]中車輛能夠在卸載計算任務時了解其相鄰車輛的卸載延遲性能，在此基礎上設計了一種自適應學習任務卸載算法，以最小化平均卸載延遲。文獻[13]中作者提出了一種利用先驗分布和統計信息引入貝葉斯推理的深度Q網絡算法，其中車輛動態選擇候選服務器來執行任務，最大程度地減少了延遲和能耗的總成本。文獻[14]提出了一個基于邊緣服務器和車載服務器合作工作的任務卸載策略，在安全切換交互協議的前提下使任務卸載算法降低能耗同時減少卸載時間。針對非車聯網的邊緣計算問題，文獻[15]中，作者將資源分配問題描述為雙重拍賣游戲，采用博弈方法進行建模獲得最優資源價格和設備資源需求。文獻[16]中作者開發了一種任務分配方案，允許非合作的邊緣設備使用動態激勵來挑選各個設備收益最大的任務,然而該方案沒有做出全局最優的任務調度。

綜上所述，集中式方式主要以滿足卸載任務的需求為目標求解最優解，而分布式方式則是以滿足終端設備的需求如收益等為設計目標。目前來看，綜合考慮卸載任務和移動終端設備需求的研究很少，為此，我們從同時協調上述兩個優化目標出發，尋求滿足條件的最優解。

2 系統架構

2.1 系統框架

本工作中任務卸載的基本架構如圖1所示，主要包括一個基站、邊緣服務器、基站范圍內的停車簇以及移動車輛4部分。

圖1 系統架構

(1)移動車輛(mobile vehicle)：是道路上行駛的智能車輛，這些車輛產生各種應用服務，如網絡游戲、智能駕駛應用、增強現實等。

(2)基站(base station)：移動車輛產生的任務卸載請求均需要發送給基站，基站為所有卸載任務分配具體執行任務的邊緣服務器、停車簇和計算資源。

(3)邊緣服務器(edge server)：邊緣服務器位于基站附近，通過有線網絡可以直接快速的與基站進行數據交換。

(4)停車簇(parking cluster)：一個基站通信范圍內有多輛停放車輛，位于同一條街道上的停放車輛被組織成停車簇。停車簇充當虛擬邊緣服務器，輔助邊緣服務器，為移動車輛提供任務計算和數據存儲服務。

2.2 任務模型

2.3 停車簇的構建

典型的停車簇如圖2所示，構建過程描述如下：首先，各道路上的車輛確定各自的地理位置，然后根據各自的地理位置確定其在停車簇中的角色。令道路中間的停放車輛作為簇頭，如圖中的H，道路上的其它停放車輛(M1～M11)充當簇成員。

圖2 停車簇

簇頭管理維護整個停車簇，包括簇內資源的管理，為具體的任務卸載分配車輛成員，以及處理車輛離開和加入簇的事件等。簇內車輛成員周期性向簇頭發送信息，包括其ID號、位置以及剩余電量、剩余資源等。考慮到簇頭車輛在車主的控制下隨時可能離開，我們將距離簇頭最近的停放車輛作為備用簇頭，如圖中的SH，當簇頭離開，需要簇頭將信息傳輸到備用簇頭并令新的簇頭重新管理停車簇。

2.4 停車簇調查

我們提出的策略基于路邊停放車輛狀況，因此路邊停放車輛的分布以及穩定性是本策略實現的關鍵，本小節通過調研分析車輛的停放狀況。文獻[17]對美國普吉特海灣地區現有的停車位使用情況進行調查發現，車位具有長時間連續占用的特點，地面停車場的平均利用率約占78%，其中一半以上的停車場占用率接近100%。文獻[18]對加拿大蒙特利爾市5500平方公里的停放車輛狀況進行統計分析，每天停放車輛的數量約為3萬，平均停車事件6.1萬次起，平均停車時間將近6.95 h。報告文獻[19]中對深圳道路的狀況進行調查顯示，全市停車泊位密度為0.21萬個/平方公里。文獻[20]中調查了哈爾濱市商圈停車場現狀，發現白天停車位利用率維持在80%以上且相對穩定。盡管上述提供的停車報告僅針對幾個城市或區域，但大范圍停車、長時間停車、高密度路邊停車在每個城市都很常見，由此我們得出停車簇的結構具有一定的穩定性。現有的城市交通車輛變化很大，街道上的車輛甚至每秒鐘都會快速變換位置，尤其在交通高峰期。但停放車輛會靜止數小時，且每輛車的靜止時間遠長于行駛時間。基于上述特征我們得出：與移動車輛相比，城市中停放車輛輔助任務卸載，具有很強的實用性。

2.5 基本思想

對于道路上移動車輛生成的任務，可以通過本地或服務器兩種方式執行。服務器分為兩種類型：基站旁的邊緣服務器和由停車簇構成的虛擬邊緣服務器。如果任務的本地完成時間小于其最大容忍響應時間，則將在本地執行，否則應將任務卸載到服務器。在卸載時，首先，生成任務的車輛向基站發送請求消息，請求消息包含其ID和具體任務信息。基于收集到的任務信息，根據下面提出的自上而下任務調度算法為所有請求的任務分配服務器和計算資源，之后基站將資源分配要求發送給服務器節點。對于分配給停車簇的任務，簇頭根據簇內任務分配算法確定執行子任務的具體停放車輛，同時將結果告知基站。基站再將具體卸載任務的最終結果通知給產生任務的移動車輛，最后實現并行計算。

3 策略實現

3.1 任務卸載分析

當任務Ti需要被卸載到服務器j(j∈L) 上時，完成時間分為兩部分：產生任務Ti的移動車輛到服務器j的傳輸數據時間和執行任務所花費的時間，由于任務輸出結果的傳輸時間很小所以這里忽略不記。任務Ti的完成時間表示為

(1)

其中，ti,j是完成時間，ttran,ij是任務數據傳輸時間，ri,j是服務器j分配給任務Ti的資源量。對于傳輸時間ttran,ij， 若任務Ti被卸載到基站附近的邊緣服務器，其值為

(2)

其中，c(Vi,S)表示從移動車輛到該基站的吞吐量，根據香農定理，其值為

(3)

其中，B代表信道帶寬，Pv是車輛傳輸功率，g0為路徑損耗常數，ξ(Vi,S)和d分別是產生任務的車輛到邊緣服務器的信道功率增益和距離，β表示路徑損耗指數，I是干擾的最大接收功率，σ2是高斯噪聲。

若j為停車簇，任務將被分割成多個子任務，由若干停放車輛成員并行執行。此時為了計算ttran,ij， 我們首先檢查產生任務Ti的車輛是否可以直接與停車簇j通信。如果可以

(4)

其中，cvel是車對車通信的吞吐量，Lcj是停車簇j的長度，R是車輛的通信范圍，si/2cvel表示由一跳數據傳輸引起的平均任務傳輸延遲，Lcj/2R表示向具體停放車輛傳輸數據的平均通信跳數。

否則任務數據必須在基站的幫助下傳輸到停車簇j，此時ttran,ij為

(5)

(6)

其中，PB是基站傳輸功率，ξ(S,Vp)和d′分別是基站到停放車輛p的信道功率增益和距離。

3.2 自上而下的任務調度分析

道路上行駛的智能車輛可能會同時生成任務，產生計算資源的競爭，為此需要合理分配計算節點和資源。任務的分配由基站執行，此外，基站還同時負責維護深度學習模型的參數等。

本文將移動車輛產生的任務調度問題描述為一個優化問題，優化的目的是最小化任務總的完成時間，該優化問題表示為

(7)

s.t.

zi,j∈{0,1}, ?i∈T,j∈L

(8)

(9)

(10)

(11)

ri,j≤rmax, ?i∈T,j∈L

(12)

約束式(8)中，當任務Ti被分派給服務器j時，zi,j的值為1，否則為0。約束(9)確保每個任務只能卸載到一個服務器上執行。約束(10)保證每個任務都在最大容忍響應時間內完成。ri,j是服務器j分配給任務Ti的資源量，最大資源量約束為rmax。式(11)保證服務器分配給任務的計算資源總量不超過其擁有的資源Rj。條件(12)是對每個任務計算資源量的約束。

該問題涉及兩個問題：資源分配和執行任務具體位置的選擇。分配給每個任務的計算資源是不高于rmax的任何值，此外和基站直接連接的邊緣服務器以及周圍的停車簇均能執行卸載任務，該調度問題是NP難問題[21]。為了解決該優化問題，我們把此問題轉化為兩個子問題，通過分別解決兩個子問題解決問題P。首先假設執行任務的服務器已經確定，此時P轉化為

(13)

s.t.

(14)

(15)

(16)

在確定資源分配后，下一步需要選擇任務卸載的最佳服務器節點。此時根據式(1)可得ti,j， 問題P簡化為子問題P2，只需求解zi,j。 該子問題P2是0-1整數規劃問題，我們采用分支定界算法[23]解決。

通過求解資源分配和服務器節點選擇兩個子問題，最終解決了自上而下任務調度的優化問題。

3.3 簇內任務分配分析

根據前一節優化得到的占用資源大小，將分配給停車簇的任務分為不同的子任務，由多個停放車輛并行執行，以加快任務的執行速度。我們令簇頭負責為子任務分派具體的停放車輛，從而盡可能滿足停放車輛的能耗和收益需求。以停車簇j為例，由于上一小節已經為卸載到j上的每個任務確定了最佳資源，因此執行任務Ti的停放車輛數量為

(17)

為了簇頭合理的分配子任務，定義Ti的每個子任務卸載到停放車輛p的懲罰函數為

(18)

(19)

其中，ttran,i′p是停放車輛p接收子任務數據花費的時間，根據式(4)或式(5)獲得，ci/nilv是執行子任務的時間。

在具體分配停放車輛時，要考慮車輛的電池能量狀態，盡量降低停放車輛的能量消耗。停放車輛p執行子任務消耗的能量表示為

(20)

其中，Pv是車輛傳輸功率，ttran,i′p是傳輸時間，ei′,p是在停放車輛p上運行子任務Ti′所消耗的能量，γ是文獻[24]中與任務執行能量消耗相關的系數。

基于執行子任務固有獎勵，時間懲罰函數以及車輛能量消耗，定義停放車輛p執行子任務的效用函數為

(21)

其中，ri是完成任務Ti所獲得獎勵，則停放車輛完成子任務獲得的獎勵為ri/ni，Emin是保證車輛能夠正常駕駛的最小能量值。停放車輛p執行完Ti′子任務后剩余能量值Ep,remain為

Ep,remain=Ep-Ei′,p

(22)

其中，Ep是停放車輛p的當前能量值。

簇頭分配任務時，需要盡可能地使停放車輛的效用最大化，算法1顯示了停車簇中具體分配子任務的偽代碼：

算法1：Allocation of parked vehicles

(1)arrange all subtasks in queueZ；

(2)record all parking vehicles asP;

(3)for each subtaskTi′inZ

(5) for each idle vehiclepinPdo

(6) calculateui′,pusing Equation(21);

(7) ifumax

(8)umax=ui′,p;

(9) record vehiclepask；

(10) else

(11) continue;

(12) end if

(13) end for

(14) assign subtaskTi′to parking vehiclekfor execution;

(15) remove elementkfrom setP;

(16)end for

4 性能模擬

4.1 實驗設置

我們利用c++進行實驗模擬，假設一個基站覆蓋區域內有5條縱橫交錯的街道，平均每條街道長900 m，該區域有100～500輛車隨機移動。車輛傳輸半徑R為250 m，車輛的總能量為3 W，Emin設置為車輛總能量的30%。對于停放車輛的當前能量值在總能量值的60%～100%之間隨機選擇。每輛車擁有的資源設置為0.4 GHz，基站擁有的資源設置為8 GHz。此外，設置無干擾情況[25]，同一條街道上的停放車輛被組織成一個停車簇，根據文獻[11]中城市道路停車調查，默認設置停車簇中的停車分布符合文獻所述中等密度分布。令移動車輛以60%的概率產生任務，任務參數設置如下：計算資源量ci為1000 cycles/bit，數據大小si為 [2,4] Mb， 任務的最大容忍響應時間為[4,8] s。 其它默認參數見表1。

表1 默認參數

我們將本文所提策略與以下3種策略進行比較：

(1)本地執行(local computing，LC)：移動車輛產生的計算任務總是全部由產生任務的車輛本地執行。

(2)自上而下任務分配(top-down task assignment，TDTA)：根據3.2節所提出的自上而下的任務調度，把任務分配到各停車簇和邊緣服務器，對于在停車簇執行計算的任務，停車簇根據任務分配到的計算資源隨機給各任務分配停放車輛。

(3)停車簇內任務分配(parking cluster task allocation，PCTA)：車輛產生的所有任務隨機分配資源及服務器節點，對于分配到停車簇的任務，使用本文提出的簇內子任務分配算法進行分配。

性能評估指標為任務完成率、任務完成時間和停放車輛效用，任務完成率即成功完成任務的數量與產生的總任務數量之比，任務完成時間指的是平均完成一個任務所花費的時間，其中執行失敗的任務完成時間統一記為9 s；停放車輛效用是從車輛執行任務所獲利出發的一個關于時間、能耗和固有獎勵的函數值，其中獎勵和任務數據大小成正比。

4.2 實驗分析

4.2.1 任務數量的影響

為了分析任務數量對各種策略性能的影響，假設基站覆蓋區域內有4個停車簇，我們設置不同的移動車輛數量，即將任務數量從100逐漸增加到350個，此時各調度策略的性能變化如圖3、圖4和圖5所示。

圖3 完成率隨任務數量的變化

圖4 任務完成時間隨任務數量的變化

圖5 車輛效用值隨任務數量的變化

圖3顯示，TDTA和所提任務分配策略在任務數量為100時能夠全部完成，這是因為基站附近服務器的可用資源充足，且在任務數量較少時停車簇具有的資源足夠卸載任務使用，為此每個卸載的任務可以分配到足夠的計算資源來執行任務。隨著任務數的增加，除LC外，其它3種分配策略的完成率均呈下降趨勢，這是因為任務總數增加，而邊緣服務器和停車簇擁有的計算資源卻保持不變，因此每個任務所分配的資源量降低造成任務完成率下降。其中，本文提出的策略總是具有最大的完成率。這是因為我們不但為每個任務選擇合理的停車簇，且為每個卸載到停車簇的任務選擇最佳的執行車輛，保證了任務的服務質量。圖4表明，隨著任務數量的增加，TDTA、PCTA和本文所提策略的任務平均完成時間都在增加，但均低于LC策略。本文所提策略性能最好，其次是TDTA，說明自上而下的任務調度可以最大限度地減少任務的總完成時間，同時盡可能地完成每個任務的計算請求。圖5顯示，隨著任務數量的增加，TDTA、PCTA和本文所提策略的停放車輛效用值均減小，而本文所提策略的車輛效用值始終保持最大。由于LC中的任務只能在本地執行，本地資源非常有限，一些復雜任務無法處理，因此LC的完成率最低、任務的平均完成時間最高。綜上所述，隨著任務數量增加，本文所提策略不僅性能最高，且能保證停放車輛的效用值最大化。

4.2.2 計算資源需求的影響

本組實驗研究在任務數量為200、停車簇數量為4的情況下，計算資源需求變化對策略性能的影響。將計算資源從600 cycles/bit變化到1600 cycles/bit，各種策略的性能變化如圖6、圖7、圖8所示。

圖6 完成率隨計算資源需求的變化

圖7 任務完成時間隨計算資源需求的變化

圖8 車輛效用值隨計算資源需求的變化

如圖6和圖7所示，隨著計算資源需求越來越大，4種分配策略的完成率呈下降趨勢，完成時間呈上升趨勢。計算資源需求的增加導致完成任務所需資源極大增加，而移動車輛的計算資源非常有限，因此LC完成率的下降趨勢以及任務平均完成時間的上升趨勢尤為明顯。對于另外3種策略，可以將任務卸載到邊緣服務器上，減少了任務的完成時間，提高了完成率，而由圖可看出我們所提的策略具有最大完成率以及最小任務完成時間。如圖8所示，本文所提策略、TDTA和PCTA的車輛效用值隨著計算資源需求的增加而降低。原因是執行任務所需的計算資源增加，導致時間和能耗都增加。當任務所需計算資源繼續增加時，任務執行時間和能量消耗不斷增大，導致任務無法卸載到停放車輛完成。本文所提策略保證了停放車輛執行卸載任務的完成時間和能量消耗最小，以及停放車輛收益最大，從而擁有停放車輛的最大效用值。

4.2.3 停車簇數量的影響

本組實驗主要研究停車簇數量對4種任務分配方案完成率以及車輛效用值的影響，實驗中默認任務數量仍保持200不變。

當只有一個停車簇時，圖9中的完成率較低，這是由于停放車輛較少，不足以支撐足夠多的任務卸載，但此時本文所提策略、TDTA和PCTA幾種卸載性能仍舊比LC的完成率要高。如圖9和圖10所示，隨著停車簇數量的逐漸增多，路邊停放車輛的可利用資源量增加，除LC外的其它幾種策略完成率和車輛效用值均呈上升趨勢，充分驗證了利用路邊停放車輛協助完成任務卸載可提高任務分配性能。LC本地執行策略和停放車輛的數量無關，因此不隨停車簇數量變化而變化。通過對比4種方案性能隨停車簇數量的變化，可見本文所提卸載策略的完成率和車輛效用值始終保持最大。

圖9 完成率隨停車簇數量的變化

圖10 車輛效用值隨停車簇數量的變化

本文所提分配策略始終保持性能最優，這是因為所提策略不僅利用具有豐富資源的停放車輛執行卸載任務。在任務分配方面，首先對資源和服務器節點的選擇進行了合理調度，又從停放車輛自私性的角度保證了停放車輛的效用值最大化。

5 結束語

本文把路邊停放車輛組織成停車簇，擁有充分且未被充分利用資源的停車簇可以協助基站附近的服務器，參與任務的卸載執行，從而極大緩解邊緣服務器的資源限制。在此基礎上，提出了自上而下的任務調度和停車簇內部分配策略來解決車輛邊緣計算中任務低完成延遲以及停放車輛低能耗且高收益的任務分配需求。仿真實驗結果表明了本文所提策略的有效性。下一步工作將考慮引入深度學習的方法對調度性能進行優化，并考慮車輛移動速度等其它因素對車聯網環境的影響。