停車輔助的車輛邊緣計(jì)算中的雙重任務(wù)卸載設(shè)計(jì)

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

(天津師范大學(xué) 計(jì)算機(jī)信息工程學(xué)院，天津 300387)

0 引 言

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

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

1 相關(guān)工作

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

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

綜上所述，集中式方式主要以滿足卸載任務(wù)的需求為目標(biāo)求解最優(yōu)解，而分布式方式則是以滿足終端設(shè)備的需求如收益等為設(shè)計(jì)目標(biāo)。目前來看，綜合考慮卸載任務(wù)和移動(dòng)終端設(shè)備需求的研究很少，為此，我們從同時(shí)協(xié)調(diào)上述兩個(gè)優(yōu)化目標(biāo)出發(fā)，尋求滿足條件的最優(yōu)解。

2 系統(tǒng)架構(gòu)

2.1 系統(tǒng)框架

本工作中任務(wù)卸載的基本架構(gòu)如圖1所示，主要包括一個(gè)基站、邊緣服務(wù)器、基站范圍內(nèi)的停車簇以及移動(dòng)車輛4部分。

圖1 系統(tǒng)架構(gòu)

(1)移動(dòng)車輛(mobile vehicle)：是道路上行駛的智能車輛，這些車輛產(chǎn)生各種應(yīng)用服務(wù)，如網(wǎng)絡(luò)游戲、智能駕駛應(yīng)用、增強(qiáng)現(xiàn)實(shí)等。

(2)基站(base station)：移動(dòng)車輛產(chǎn)生的任務(wù)卸載請(qǐng)求均需要發(fā)送給基站，基站為所有卸載任務(wù)分配具體執(zhí)行任務(wù)的邊緣服務(wù)器、停車簇和計(jì)算資源。

(3)邊緣服務(wù)器(edge server)：邊緣服務(wù)器位于基站附近，通過有線網(wǎng)絡(luò)可以直接快速的與基站進(jìn)行數(shù)據(jù)交換。

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

2.2 任務(wù)模型

2.3 停車簇的構(gòu)建

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

圖2 停車簇

簇頭管理維護(hù)整個(gè)停車簇，包括簇內(nèi)資源的管理，為具體的任務(wù)卸載分配車輛成員，以及處理車輛離開和加入簇的事件等。簇內(nèi)車輛成員周期性向簇頭發(fā)送信息，包括其ID號(hào)、位置以及剩余電量、剩余資源等?？紤]到簇頭車輛在車主的控制下隨時(shí)可能離開，我們將距離簇頭最近的停放車輛作為備用簇頭，如圖中的SH，當(dāng)簇頭離開，需要簇頭將信息傳輸?shù)絺溆么仡^并令新的簇頭重新管理停車簇。

2.4 停車簇調(diào)查

我們提出的策略基于路邊停放車輛狀況，因此路邊停放車輛的分布以及穩(wěn)定性是本策略實(shí)現(xiàn)的關(guān)鍵，本小節(jié)通過調(diào)研分析車輛的停放狀況。文獻(xiàn)[17]對(duì)美國普吉特海灣地區(qū)現(xiàn)有的停車位使用情況進(jìn)行調(diào)查發(fā)現(xiàn)，車位具有長時(shí)間連續(xù)占用的特點(diǎn)，地面停車場的平均利用率約占78%，其中一半以上的停車場占用率接近100%。文獻(xiàn)[18]對(duì)加拿大蒙特利爾市5500平方公里的停放車輛狀況進(jìn)行統(tǒng)計(jì)分析，每天停放車輛的數(shù)量約為3萬，平均停車事件6.1萬次起，平均停車時(shí)間將近6.95 h。報(bào)告文獻(xiàn)[19]中對(duì)深圳道路的狀況進(jìn)行調(diào)查顯示，全市停車泊位密度為0.21萬個(gè)/平方公里。文獻(xiàn)[20]中調(diào)查了哈爾濱市商圈停車場現(xiàn)狀，發(fā)現(xiàn)白天停車位利用率維持在80%以上且相對(duì)穩(wěn)定。盡管上述提供的停車報(bào)告僅針對(duì)幾個(gè)城市或區(qū)域，但大范圍停車、長時(shí)間停車、高密度路邊停車在每個(gè)城市都很常見，由此我們得出停車簇的結(jié)構(gòu)具有一定的穩(wěn)定性?，F(xiàn)有的城市交通車輛變化很大，街道上的車輛甚至每秒鐘都會(huì)快速變換位置，尤其在交通高峰期。但停放車輛會(huì)靜止數(shù)小時(shí)，且每輛車的靜止時(shí)間遠(yuǎn)長于行駛時(shí)間?；谏鲜鎏卣魑覀兊贸觯号c移動(dòng)車輛相比，城市中停放車輛輔助任務(wù)卸載，具有很強(qiáng)的實(shí)用性。

2.5 基本思想

對(duì)于道路上移動(dòng)車輛生成的任務(wù)，可以通過本地或服務(wù)器兩種方式執(zhí)行。服務(wù)器分為兩種類型：基站旁的邊緣服務(wù)器和由停車簇構(gòu)成的虛擬邊緣服務(wù)器。如果任務(wù)的本地完成時(shí)間小于其最大容忍響應(yīng)時(shí)間，則將在本地執(zhí)行，否則應(yīng)將任務(wù)卸載到服務(wù)器。在卸載時(shí)，首先，生成任務(wù)的車輛向基站發(fā)送請(qǐng)求消息，請(qǐng)求消息包含其ID和具體任務(wù)信息?；谑占降娜蝿?wù)信息，根據(jù)下面提出的自上而下任務(wù)調(diào)度算法為所有請(qǐng)求的任務(wù)分配服務(wù)器和計(jì)算資源，之后基站將資源分配要求發(fā)送給服務(wù)器節(jié)點(diǎn)。對(duì)于分配給停車簇的任務(wù)，簇頭根據(jù)簇內(nèi)任務(wù)分配算法確定執(zhí)行子任務(wù)的具體停放車輛，同時(shí)將結(jié)果告知基站。基站再將具體卸載任務(wù)的最終結(jié)果通知給產(chǎn)生任務(wù)的移動(dòng)車輛，最后實(shí)現(xiàn)并行計(jì)算。

3 策略實(shí)現(xiàn)

3.1 任務(wù)卸載分析

當(dāng)任務(wù)Ti需要被卸載到服務(wù)器j(j∈L) 上時(shí)，完成時(shí)間分為兩部分：產(chǎn)生任務(wù)Ti的移動(dòng)車輛到服務(wù)器j的傳輸數(shù)據(jù)時(shí)間和執(zhí)行任務(wù)所花費(fèi)的時(shí)間，由于任務(wù)輸出結(jié)果的傳輸時(shí)間很小所以這里忽略不記。任務(wù)Ti的完成時(shí)間表示為

(1)

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

(2)

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

(3)

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

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

(4)

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

否則任務(wù)數(shù)據(jù)必須在基站的幫助下傳輸?shù)酵＼嚧豭，此時(shí)ttran,ij為

(5)

(6)

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

3.2 自上而下的任務(wù)調(diào)度分析

道路上行駛的智能車輛可能會(huì)同時(shí)生成任務(wù)，產(chǎn)生計(jì)算資源的競爭，為此需要合理分配計(jì)算節(jié)點(diǎn)和資源。任務(wù)的分配由基站執(zhí)行，此外，基站還同時(shí)負(fù)責(zé)維護(hù)深度學(xué)習(xí)模型的參數(shù)等。

本文將移動(dòng)車輛產(chǎn)生的任務(wù)調(diào)度問題描述為一個(gè)優(yōu)化問題，優(yōu)化的目的是最小化任務(wù)總的完成時(shí)間，該優(yōu)化問題表示為

(7)

s.t.

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

(8)

(9)

(10)

(11)

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

(12)

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

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

(13)

s.t.

(14)

(15)

(16)

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

通過求解資源分配和服務(wù)器節(jié)點(diǎn)選擇兩個(gè)子問題，最終解決了自上而下任務(wù)調(diào)度的優(yōu)化問題。

3.3 簇內(nèi)任務(wù)分配分析

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

(17)

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

(18)

(19)

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

在具體分配停放車輛時(shí)，要考慮車輛的電池能量狀態(tài)，盡量降低停放車輛的能量消耗。停放車輛p執(zhí)行子任務(wù)消耗的能量表示為

(20)

其中，Pv是車輛傳輸功率，ttran,i′p是傳輸時(shí)間，ei′,p是在停放車輛p上運(yùn)行子任務(wù)Ti′所消耗的能量，γ是文獻(xiàn)[24]中與任務(wù)執(zhí)行能量消耗相關(guān)的系數(shù)。

基于執(zhí)行子任務(wù)固有獎(jiǎng)勵(lì)，時(shí)間懲罰函數(shù)以及車輛能量消耗，定義停放車輛p執(zhí)行子任務(wù)的效用函數(shù)為

(21)

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

Ep,remain=Ep-Ei′,p

(22)

其中，Ep是停放車輛p的當(dāng)前能量值。

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

算法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 實(shí)驗(yàn)設(shè)置

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

表1 默認(rèn)參數(shù)

我們將本文所提策略與以下3種策略進(jìn)行比較：

(1)本地執(zhí)行(local computing，LC)：移動(dòng)車輛產(chǎn)生的計(jì)算任務(wù)總是全部由產(chǎn)生任務(wù)的車輛本地執(zhí)行。

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

(3)停車簇內(nèi)任務(wù)分配(parking cluster task allocation，PCTA)：車輛產(chǎn)生的所有任務(wù)隨機(jī)分配資源及服務(wù)器節(jié)點(diǎn)，對(duì)于分配到停車簇的任務(wù)，使用本文提出的簇內(nèi)子任務(wù)分配算法進(jìn)行分配。

性能評(píng)估指標(biāo)為任務(wù)完成率、任務(wù)完成時(shí)間和停放車輛效用，任務(wù)完成率即成功完成任務(wù)的數(shù)量與產(chǎn)生的總?cè)蝿?wù)數(shù)量之比，任務(wù)完成時(shí)間指的是平均完成一個(gè)任務(wù)所花費(fèi)的時(shí)間，其中執(zhí)行失敗的任務(wù)完成時(shí)間統(tǒng)一記為9 s；停放車輛效用是從車輛執(zhí)行任務(wù)所獲利出發(fā)的一個(gè)關(guān)于時(shí)間、能耗和固有獎(jiǎng)勵(lì)的函數(shù)值，其中獎(jiǎng)勵(lì)和任務(wù)數(shù)據(jù)大小成正比。

4.2 實(shí)驗(yàn)分析

4.2.1 任務(wù)數(shù)量的影響

為了分析任務(wù)數(shù)量對(duì)各種策略性能的影響，假設(shè)基站覆蓋區(qū)域內(nèi)有4個(gè)停車簇，我們?cè)O(shè)置不同的移動(dòng)車輛數(shù)量，即將任務(wù)數(shù)量從100逐漸增加到350個(gè)，此時(shí)各調(diào)度策略的性能變化如圖3、圖4和圖5所示。

圖3 完成率隨任務(wù)數(shù)量的變化

圖4 任務(wù)完成時(shí)間隨任務(wù)數(shù)量的變化

圖5 車輛效用值隨任務(wù)數(shù)量的變化

圖3顯示，TDTA和所提任務(wù)分配策略在任務(wù)數(shù)量為100時(shí)能夠全部完成，這是因?yàn)榛靖浇?wù)器的可用資源充足，且在任務(wù)數(shù)量較少時(shí)停車簇具有的資源足夠卸載任務(wù)使用，為此每個(gè)卸載的任務(wù)可以分配到足夠的計(jì)算資源來執(zhí)行任務(wù)。隨著任務(wù)數(shù)的增加，除LC外，其它3種分配策略的完成率均呈下降趨勢，這是因?yàn)槿蝿?wù)總數(shù)增加，而邊緣服務(wù)器和停車簇?fù)碛械挠?jì)算資源卻保持不變，因此每個(gè)任務(wù)所分配的資源量降低造成任務(wù)完成率下降。其中，本文提出的策略總是具有最大的完成率。這是因?yàn)槲覀儾坏珵槊總€(gè)任務(wù)選擇合理的停車簇，且為每個(gè)卸載到停車簇的任務(wù)選擇最佳的執(zhí)行車輛，保證了任務(wù)的服務(wù)質(zhì)量。圖4表明，隨著任務(wù)數(shù)量的增加，TDTA、PCTA和本文所提策略的任務(wù)平均完成時(shí)間都在增加，但均低于LC策略。本文所提策略性能最好，其次是TDTA，說明自上而下的任務(wù)調(diào)度可以最大限度地減少任務(wù)的總完成時(shí)間，同時(shí)盡可能地完成每個(gè)任務(wù)的計(jì)算請(qǐng)求。圖5顯示，隨著任務(wù)數(shù)量的增加，TDTA、PCTA和本文所提策略的停放車輛效用值均減小，而本文所提策略的車輛效用值始終保持最大。由于LC中的任務(wù)只能在本地執(zhí)行，本地資源非常有限，一些復(fù)雜任務(wù)無法處理，因此LC的完成率最低、任務(wù)的平均完成時(shí)間最高。綜上所述，隨著任務(wù)數(shù)量增加，本文所提策略不僅性能最高，且能保證停放車輛的效用值最大化。

4.2.2 計(jì)算資源需求的影響

本組實(shí)驗(yàn)研究在任務(wù)數(shù)量為200、停車簇?cái)?shù)量為4的情況下，計(jì)算資源需求變化對(duì)策略性能的影響。將計(jì)算資源從600 cycles/bit變化到1600 cycles/bit，各種策略的性能變化如圖6、圖7、圖8所示。

圖6 完成率隨計(jì)算資源需求的變化

圖7 任務(wù)完成時(shí)間隨計(jì)算資源需求的變化

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

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

4.2.3 停車簇?cái)?shù)量的影響

本組實(shí)驗(yàn)主要研究停車簇?cái)?shù)量對(duì)4種任務(wù)分配方案完成率以及車輛效用值的影響，實(shí)驗(yàn)中默認(rèn)任務(wù)數(shù)量仍保持200不變。

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

圖9 完成率隨停車簇?cái)?shù)量的變化

圖10 車輛效用值隨停車簇?cái)?shù)量的變化

本文所提分配策略始終保持性能最優(yōu)，這是因?yàn)樗岵呗圆粌H利用具有豐富資源的停放車輛執(zhí)行卸載任務(wù)。在任務(wù)分配方面，首先對(duì)資源和服務(wù)器節(jié)點(diǎn)的選擇進(jìn)行了合理調(diào)度，又從停放車輛自私性的角度保證了停放車輛的效用值最大化。

5 結(jié)束語

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