劉國志,代 飛+,莫 啟,許小龍,強振平,王雷光

(1.西南林業(yè)大學(xué) 大數(shù)據(jù)與智能工程學(xué)院,云南 昆明 650224;2.云南大學(xué) 軟件學(xué)院,云南 昆明 650091;3.南京信息工程大學(xué) 計算機與軟件學(xué)院,江蘇 南京 210044)

0 引言

車聯(lián)網(wǎng)是智能交通系統(tǒng)中的一個新興概念，旨在通過與物聯(lián)網(wǎng)(Internet of Things, IoT)集成來提高交通安全性和乘客舒適度，是物聯(lián)網(wǎng)的一個重要實施方式[1-2]?；谲囉脽o線通信技術(shù)——車輛到一切(Vehicle to Everything, V2X)，車聯(lián)網(wǎng)將車輛、路邊單元(Road-Side Unit, RSU)和服務(wù)提供商連接為一個有機的網(wǎng)絡(luò)整體，實現(xiàn)了它們之間的全方位通信[3]。在車聯(lián)網(wǎng)中，智能車輛可以通過V2X通信，具體而言，其可以通過車輛對車輛(Vehicle to Vehicle, V2V)通信與其他車輛共享信息[4]，從而通過周圍車輛共享的路況信息獲得更廣闊的視野，大大減少盲點帶來的交通事故[4]。同時，部署智能基礎(chǔ)設(shè)施(如RSU)，服務(wù)提供商能夠獲取用戶服務(wù)需求和道路環(huán)境信息，基于這些數(shù)據(jù)為車載用戶提供諸如自動駕駛、路徑規(guī)劃、碰撞預(yù)警、車載娛樂等多種服務(wù)，從而提高駕駛安全性和旅途舒適性[5-6]。同樣，車輛對行人(Vehicle to Pedestria, V2P)通信使車輛和行人能夠發(fā)出安全警告。有了車聯(lián)網(wǎng)中的V2X通信，智能車輛就有可能及時調(diào)整駕駛狀態(tài)，避免交通事故[7-8]。

一般地，車輛本地搭載的計算設(shè)備計算能力較弱，某些車輛甚至不會搭載計算設(shè)備[9]。因此，目前大部分車聯(lián)網(wǎng)用戶會將服務(wù)需求卸載到云端進(jìn)行處理[10]，云平臺可以提供大量的計算和緩存資源。然而，極大的傳輸成本和相對較長的延遲可能會降低用戶體驗，尤其是對延遲敏感的應(yīng)用。如果某些服務(wù)(如碰撞預(yù)警)的延遲超過一定限度，則會降低服務(wù)質(zhì)量，甚至發(fā)生交通事故[11]。

邊緣計算是解決該問題的有效方案之一，其通過在RSU部署邊緣服務(wù)器，將計算、帶寬、存儲等資源分布到靠近用戶的一側(cè)[12]，從而縮短車聯(lián)網(wǎng)用戶和計算資源的距離，降低服務(wù)時延[13]。然而，由于邊緣服務(wù)器所配備的計算、存儲、帶寬資源往往有限，如果將所有任務(wù)卸載到邊緣服務(wù)器，則容易導(dǎo)致邊緣服務(wù)器過載，邊緣服務(wù)器一旦過載，服務(wù)時延便會升高，服務(wù)質(zhì)量也會相應(yīng)降低[14]。因此，某些車聯(lián)網(wǎng)用戶的服務(wù)請求仍需卸載到云平臺或在本地執(zhí)行，以保證邊緣服務(wù)器的效率。如何在滿足邊緣服務(wù)器資源限制的約束下，對車聯(lián)網(wǎng)用戶服務(wù)的卸載目的地進(jìn)行決策，盡可能降低服務(wù)時延，是車聯(lián)網(wǎng)邊緣計算中的挑戰(zhàn)之一。

“端—邊—云”架構(gòu)下的任務(wù)卸載問題可以歸約為邊緣服務(wù)器計算資源和通信資源約束下獲得最小平均服務(wù)時延的聯(lián)合優(yōu)化問題，為此本文引入深度強化學(xué)習(xí)方法來解決優(yōu)化問題。本文的主要貢獻(xiàn)如下：

(1)提出一種“端—邊—云”協(xié)同的車聯(lián)網(wǎng)邊緣計算系統(tǒng)模型。該模型由一個中心云服務(wù)器、多輛車多個RSU組成，其中每個RSU配備一個邊緣服務(wù)器。

(2)提出一種基于深度Q網(wǎng)絡(luò)(Deep Q-Network, DQN)的車聯(lián)網(wǎng)服務(wù)卸載方法(Service Offloading method based on DQN, SODQN)，分別定義了DQN的4個要素，即環(huán)境、狀態(tài)、動作和獎勵。

(3)采用模擬數(shù)據(jù)進(jìn)行對比實驗，證明SODQN方法能夠有效降低車聯(lián)網(wǎng)用戶的平均服務(wù)時延。

1 相關(guān)工作

邊緣計算中的服務(wù)卸載一般按照決策者的數(shù)量和決策范圍不同分為集中式的任務(wù)卸載和分布式的任務(wù)卸載兩類，本文研究基于集中式的任務(wù)卸載問題。HE等[15]同時考慮延遲敏感應(yīng)用和計算密集型應(yīng)用，提出一種計算卸載算法，在計算截止日期的約束下使完成的任務(wù)數(shù)量最大化;LI等[16]考慮服務(wù)延時約束下的任務(wù)卸載問題，提出一種基于凸優(yōu)化理論和吉布斯抽樣的具有統(tǒng)計服務(wù)質(zhì)量(Quality of Service, QoS)保證的任務(wù)卸載算法；GUO等[17]將卸載問題表述為混合整數(shù)非線性規(guī)劃問題，并設(shè)計了基于遺傳算法和粒子群優(yōu)化的解決方案，然而進(jìn)化算法通常是一種通過不斷更新當(dāng)前解來尋找全局最優(yōu)解的迭代算法，對全局信息的依賴和迭代期間的時間復(fù)雜性為該算法顯著的缺點；LIU等[18]考慮執(zhí)行順序下的任務(wù)卸載問題，在計算延遲的約束下采用有向無環(huán)圖(Directed Acyclic Graph, DAG)找出最優(yōu)卸載策略來最小化平均服務(wù)時延。這些研究僅考慮了車輛和邊緣服務(wù)器的資源，沒有充分利用云服務(wù)器豐富的資源，相比之下，本文充分利用了“端—邊—云”的計算資源。

近年來，將深度學(xué)習(xí)(Deep Learning, DL)技術(shù)應(yīng)用于強化學(xué)習(xí)(Reinforcement Learning, RL)而形成的深度強化學(xué)習(xí)(Deep Reinforcement Learning, DRL)方法，相比于傳統(tǒng)的強化學(xué)習(xí)方法具有更強的環(huán)境感知能力，在諸如電子游戲、參數(shù)優(yōu)化、機器人控制等多個領(lǐng)域得到了廣泛研究并取得令人振奮的成果，如何將強化學(xué)習(xí)應(yīng)用于車聯(lián)網(wǎng)環(huán)境，提高車聯(lián)網(wǎng)用戶的服務(wù)體驗，也是當(dāng)今車聯(lián)網(wǎng)領(lǐng)域的一大研究方向。一些工作研究了基于強化學(xué)習(xí)的任務(wù)卸載工作。XU等[19]將車聯(lián)網(wǎng)與數(shù)字孿生結(jié)合，考慮QoS約束下的服務(wù)卸載問題，提出一種基于DRL的服務(wù)卸載算法；WANG等[20]提出一種基于強化學(xué)習(xí)的移動邊緣計算中的聯(lián)合任務(wù)卸載和遷移算法，使移動邊緣設(shè)備收益最大化；ALAM等[21]在移動霧計算環(huán)境下提供無縫和可感知延遲的移動服務(wù)，并提出基于強化學(xué)習(xí)的任務(wù)卸載機制；XU等[22]提出一種基于強化學(xué)習(xí)的聯(lián)合方法，對智能城市的通信和計算資源進(jìn)行優(yōu)化配置，然而當(dāng)優(yōu)化問題的狀態(tài)空間和動作空間變成高維時，存儲Q值所需的內(nèi)存空間呈指數(shù)型增長，同時更新和搜索最佳卸載決策會產(chǎn)生大量存儲和時間開銷，基于強化學(xué)習(xí)求解該問題將變得非常困難。一些其他的研究使用了DRL的任務(wù)卸載方法。DAI等[2]提出一種基于深度確定性策略梯度(Deep Deterministic Policy Gradient, DDPG)的聯(lián)合邊緣計算和緩存方案，可以動態(tài)地協(xié)調(diào)邊緣服務(wù)器的計算資源和緩存資源，最大化系統(tǒng)效用；HU[23]提出一種具有多時間尺度、基于DQN的服務(wù)卸載方法，降低了由大行動空間帶來的復(fù)雜性。這些研究在將邊緣計算應(yīng)用到車聯(lián)網(wǎng)的過程中，雖然使用了DRL，但僅考慮移動端架構(gòu)中的任務(wù)卸載問題，相比之下，本文考慮了“端—邊—云”協(xié)同架構(gòu)中的任務(wù)卸載和資源分配問題。

本文從平均服務(wù)延遲、“端—邊—云”協(xié)同、動態(tài)環(huán)境下的邊緣資源分配3個方面研究了虛擬環(huán)境下的任務(wù)卸載問題。本文工作與上述工作有以下兩個不同之處:

(1)本文提出一種“端—邊—云”協(xié)同的車聯(lián)網(wǎng)邊緣計算系統(tǒng)模型，為動態(tài)環(huán)境中的任務(wù)考慮最合適的邊緣云機會。

(2)本文考慮了邊緣服務(wù)器和云服務(wù)器的協(xié)同資源分配。

2 系統(tǒng)建模和問題定義

2.1 “端—邊—云”協(xié)同的車聯(lián)網(wǎng)邊緣計算模型

車聯(lián)網(wǎng)環(huán)境中的“端—邊—云”協(xié)同邊緣計算系統(tǒng)模型如圖1所示，該系統(tǒng)分為車聯(lián)網(wǎng)用戶層、邊緣層和云服務(wù)層3層。

(1)車聯(lián)網(wǎng)用戶層 包括在道路上行駛的所有用戶車輛，且每一用戶車輛均配備有限的計算資源。用戶的服務(wù)需求可以運用本地的計算資源，在安裝于本地的車載應(yīng)用內(nèi)滿足。

(2)邊緣層 包括分散在道路旁邊的邊緣計算節(jié)點，每個邊緣計算節(jié)點包括RSU，以及配備在該RSU上的邊緣服務(wù)器兩部分。RSU用于收集用戶流量、網(wǎng)絡(luò)狀況等信息，有一定的覆蓋范圍，該范圍將道路分為一個個不重合的道路段，車聯(lián)網(wǎng)用戶層中的用戶也因此被分在唯一的道路段中。每一道路段中的用戶可以通過無線信道連接到相應(yīng)的邊緣計算節(jié)點上。本文假設(shè)每個RSU均會配備一個邊緣服務(wù)器，并在服務(wù)器中已經(jīng)預(yù)先安裝好了服務(wù)提供商提供的各類車載應(yīng)用，可以滿足用戶卸載到邊緣服務(wù)器上的服務(wù)需求。同時，用戶的服務(wù)需求還可卸載到中心云執(zhí)行，邊緣計算節(jié)點會將服務(wù)需求通過有線信道轉(zhuǎn)發(fā)到中心云進(jìn)行計算。

(3)云服務(wù)層 即中心云所在的層，該層包括高性能的計算資源，并同服務(wù)提供商直接相連，能夠高效、快速地滿足用戶的服務(wù)需求。

將決策模型配置到一臺僅用于決策的邊緣服務(wù)器(稱為決策者)ES上，決策者知曉每臺邊緣服務(wù)器的資源使用情況。在該系統(tǒng)中，時間被離散化為不同的時間段，在每個時間段開始時，RSU會收集所屬道路段的環(huán)境信息(如用戶流量、網(wǎng)絡(luò)狀況等)發(fā)送給決策者。當(dāng)決策者做出卸載決策后，用戶需求根據(jù)決策結(jié)果卸載到指定設(shè)備，同時決策者會將服務(wù)卸載結(jié)果發(fā)送給中心云，進(jìn)行匯總和卸載參數(shù)優(yōu)化，中心云再將優(yōu)化過的參數(shù)回傳給決策者，從而不斷調(diào)優(yōu)服務(wù)卸載決策。

2.2 網(wǎng)絡(luò)通信模型

為了更準(zhǔn)確地對車聯(lián)網(wǎng)邊緣計算服務(wù)卸載系統(tǒng)中的網(wǎng)絡(luò)通信建立計算模型，首先定義車聯(lián)網(wǎng)用戶。

定義1車聯(lián)網(wǎng)用戶。車聯(lián)網(wǎng)用戶是一個三元組μi=λi,ρi,δi，其中：i為車聯(lián)網(wǎng)用戶的編號；λi為該車聯(lián)網(wǎng)用戶和對應(yīng)邊緣計算節(jié)點之間的最大數(shù)據(jù)傳輸速率；ρi為該用戶的信號發(fā)射功率；δi為該用戶和邊緣計算節(jié)點之間的信道增益。相應(yīng)地，用U(τ)={μ1,μ2,…,μM(τ)}表示用戶集，即車聯(lián)網(wǎng)邊緣計算環(huán)境中τ時間段內(nèi)所有用戶的集合。

(1)λi如2.1節(jié)所述，本系統(tǒng)中用戶和邊緣計算節(jié)點以無線方式連接。假設(shè)用戶采用頻分復(fù)用正交多址接入技術(shù)與邊緣計算節(jié)點相連，進(jìn)行數(shù)據(jù)的雙向傳輸，其中每個子信道的帶寬為w，且在某一道路段內(nèi)，各用戶與邊緣計算節(jié)點之間的通信干擾可以忽略不計，則用戶μi和對應(yīng)邊緣計算節(jié)點之間的最大數(shù)據(jù)傳輸速率

(1)

(2)邊緣計算節(jié)點和云服務(wù)器之間傳輸數(shù)據(jù)所產(chǎn)生的往返時延 根據(jù)圖1，本系統(tǒng)中用戶和邊緣計算節(jié)點間采用無線方式連接，邊緣服務(wù)器和云服務(wù)器之間采用有線方式連接。由于云服務(wù)器距離邊緣計算節(jié)點的地理距離較遠(yuǎn)，邊緣計算節(jié)點將用戶數(shù)據(jù)轉(zhuǎn)發(fā)給云端所產(chǎn)生的時延與云端將服務(wù)處理結(jié)果返回所產(chǎn)生的時延相近，且該時延與輸入數(shù)據(jù)的數(shù)據(jù)量無關(guān)。因此，邊緣計算節(jié)點和云服務(wù)器之間傳輸數(shù)據(jù)所產(chǎn)生的往返時延

(2)

2.3 服務(wù)時延計算模型

本系統(tǒng)中，因為用戶的服務(wù)需求可以在本地執(zhí)行，可以卸載到邊緣服務(wù)器執(zhí)行，亦可卸載到中心云上執(zhí)行，所以需要考慮3種不同情況下的服務(wù)時延。首先定義系統(tǒng)中的服務(wù)需求。

定義2服務(wù)需求。車聯(lián)網(wǎng)環(huán)境中的服務(wù)需求是一個三元組si=di,ri,μi，其中：di為該服務(wù)需求所需輸入?yún)?shù)的數(shù)據(jù)量；ri為完成該服務(wù)需求所需的計算量；μi為產(chǎn)生該服務(wù)需求的用戶。相應(yīng)地，用S(τ)={s1,s2,…,sM(τ)}表示車聯(lián)網(wǎng)邊緣計算環(huán)境中τ時間段內(nèi)所有用戶服務(wù)需求的集合。

在定義2基礎(chǔ)上，詳細(xì)定義不同情況下滿足用戶服務(wù)需求所需的服務(wù)時延，并給出系統(tǒng)平均服務(wù)時延的計算公式。

2.3.1 本地執(zhí)行時用戶的服務(wù)時延

當(dāng)用戶的服務(wù)需求在本地執(zhí)行時，用戶無需將該服務(wù)的輸入?yún)?shù)通過無線信道上傳到邊緣服務(wù)器，只需通過位于本地的車載應(yīng)用，利用本地計算資源進(jìn)行處理即可。此時需要考慮等待本地計算資源空閑時所產(chǎn)生的等待時延和本地車載應(yīng)用處理服務(wù)需求的執(zhí)行時延。因此，對于用戶μi和其產(chǎn)生的服務(wù)需求si={di,ri,μi}，可以得到該用戶在本地使用車載應(yīng)用處理服務(wù)si的執(zhí)行時延

(3)

式中fi為用戶μi所配備的本地計算資源的計算速率。

因此，用戶μi的服務(wù)需求在本地執(zhí)行，所產(chǎn)生的服務(wù)時延

(4)

2.3.2 卸載到邊緣服務(wù)器執(zhí)行時用戶的服務(wù)時延

當(dāng)用戶的服務(wù)需求被卸載到邊緣服務(wù)器上處理時，需要考慮等待無線信道空閑所產(chǎn)生的等待時延、將服務(wù)需求輸入?yún)?shù)從用戶本地上傳至邊緣服務(wù)器的傳輸時延、等待邊緣服務(wù)器剩余計算資源滿足算法分配的計算資源時所產(chǎn)生的等待時延、在邊緣服務(wù)器上處理服務(wù)需求的執(zhí)行時延，以及將處理完成的服務(wù)結(jié)果返回給用戶的回程時延4部分。由于相比輸入?yún)?shù)，服務(wù)結(jié)果的數(shù)據(jù)量一般較小，回程時延一般忽略不計，本系統(tǒng)也忽略回程時延，則用戶μi將服務(wù)需求si的輸入?yún)?shù)上傳至邊緣服務(wù)器所需的時間

(5)

在邊緣服務(wù)器上處理服務(wù)si的執(zhí)行時延

(6)

因此，如果用戶μi的服務(wù)需求被卸載到邊緣服務(wù)器執(zhí)行，則產(chǎn)生的服務(wù)時延

(7)

2.3.3 卸載到云服務(wù)器時用戶的服務(wù)時延

如圖1所示，如果用戶的服務(wù)需求需要被卸載到云端執(zhí)行，則該服務(wù)的輸入?yún)?shù)首先要通過無線信道由用戶車輛上傳到邊緣層，再由相應(yīng)的邊緣計算節(jié)點通過有線信道轉(zhuǎn)發(fā)給云端進(jìn)行處理。因為云端配備的云服務(wù)器具有較強的計算能力，處理時延相比傳輸時延可以忽略不計，所以當(dāng)用戶μi將服務(wù)si卸載到云端執(zhí)行時產(chǎn)生的服務(wù)時延主要包括等待無線信道空閑的等待時延、將輸入?yún)?shù)上傳到邊緣計算節(jié)點的傳輸時延，以及邊緣計算節(jié)點和云服務(wù)器之間傳輸數(shù)據(jù)所產(chǎn)生的往返時延RTT3部分，其中，用戶μi將服務(wù)需求si的輸入?yún)?shù)上傳至邊緣服務(wù)器所需的時間如式(5)所示。

因此，如果用戶μi的服務(wù)需求被卸載到云服務(wù)器執(zhí)行，則所產(chǎn)生的服務(wù)時延

(8)

2.3.4 系統(tǒng)總服務(wù)時延

在本系統(tǒng)中，每一個用戶的服務(wù)需求可被且僅可被卸載到本地、邊緣服務(wù)器和云端三地中的其中一處執(zhí)行．使用0-1變量αi和βi表示某個服務(wù)si的卸載情況：

(9)

(10)

因此，任意服務(wù)si的服務(wù)時延

(11)

對于τ時間段內(nèi)的所有用戶，系統(tǒng)總服務(wù)時延

(12)

2.4 問題建模

在本系統(tǒng)中，本文將車輛網(wǎng)的服務(wù)卸載問題歸約為一個優(yōu)化問題，以在邊緣服務(wù)器計算和通信資源約束條件下獲得最小的平均服務(wù)時延，因此對該問題進(jìn)行如下建模：

(13)

s.t.

(14)

(15)

(16)

?i≤M(τ),?τ；

(17)

αi,βi∈{0,1},?i≤M(τ),?τ。

(18)

3 基于DQN的車聯(lián)網(wǎng)服務(wù)卸載方法

本文結(jié)合DRL算法設(shè)計了一種SODQN方法來解決車聯(lián)網(wǎng)邊緣計算環(huán)境中的服務(wù)卸載問題，SODQN框架如圖2所示。

3.1 DQN的4個關(guān)鍵元素

作為人工智能領(lǐng)域的一部分，強化學(xué)習(xí)通過在智能體和環(huán)境交互過程中不斷試錯和學(xué)習(xí)得到最大收益的策略。近年來深度學(xué)習(xí)快速發(fā)展，使得計算機學(xué)習(xí)數(shù)據(jù)的高維抽象特征表示成為可能[24]。DRL將深度學(xué)習(xí)和強化學(xué)習(xí)結(jié)合，較好地解決了傳統(tǒng)強化學(xué)習(xí)無法應(yīng)用于高維度狀態(tài)空間和動作空間的問題，進(jìn)一步提高了強化學(xué)習(xí)求解問題的能力[25-26]。本文結(jié)合DQN算法設(shè)計了一種SODQN方法，其中DQN的智能體即為決策者ES，DQN有4個關(guān)鍵要素，分別為環(huán)境、狀態(tài)、動作和獎勵。

(1)環(huán)境

利用DQN算法卸載車聯(lián)網(wǎng)邊緣計算服務(wù)時，智能體通過狀態(tài)、動作、獎勵和環(huán)境進(jìn)行交互來學(xué)習(xí)，其中環(huán)境由車輛信息、任務(wù)數(shù)量、邊緣服務(wù)器的計算資源和通信資源組成。因此，定義環(huán)境

(19)

(2)狀態(tài)

利用DQN算法卸載車聯(lián)網(wǎng)邊緣計算服務(wù)時，狀態(tài)用于反映車輛環(huán)境的狀況[2]。以環(huán)境中某一時間段內(nèi)所有車聯(lián)網(wǎng)用戶的服務(wù)需求、網(wǎng)絡(luò)狀況，以及邊緣服務(wù)器的資源情況為系統(tǒng)狀態(tài)，表示為st(dt,ct,pt,δt)，其中：dt為待卸載服務(wù)輸入的數(shù)據(jù)量；ct為執(zhí)行該服務(wù)所需的計算量；pt為該用戶的信號發(fā)射功率；δt為該用戶和邊緣計算節(jié)點之間的信道增益。

(3)動作

動作空間定義為分配給用戶的子信道個數(shù)和計算資源數(shù)，分別用獨熱(One-Hot)向量(0/1)c和(0/1)b表示。例如，假設(shè)最大子信道數(shù)和最大計算資源數(shù)分別為3和4，(0/1)c(1)=(0,1,0,0)，(0/1)b(2)=(0,0,1,0,0)分別表示將1個子信道和2個計算資源分配給當(dāng)前時間步?jīng)Q策的用戶服務(wù)需求。因此，動作空間即為兩者的笛卡爾積，即

A=(0/1)c×(0/1)b。

(20)

式中×表示笛卡爾積。本文用α(χ)∈A表示動作空間在時間步χ執(zhí)行的一個動作。

(4)獎勵

服務(wù)卸載的目的是使所有用戶長期的平均服務(wù)時延之和最小。本文定義在系統(tǒng)狀態(tài)st(χ)時執(zhí)行動作α(χ)所獲得的即時獎勵r(χ)為：假設(shè)st(χ)決定的是用戶μi的服務(wù)需求卸載，則μi產(chǎn)生的服務(wù)需求si將根據(jù)動作α(χ)執(zhí)行的服務(wù)卸載，比將si卸載到用戶本地執(zhí)行時能夠節(jié)約的時間，即

(21)

因為最大化相比于本地執(zhí)行的節(jié)約時間和最小化長期用戶平均服務(wù)時間在本質(zhì)上相同，所以用式(21)作為獎勵函數(shù)。

在本文的系統(tǒng)模型中，假設(shè)決策者ES為DQN算法的智能體，智能體通過狀態(tài)、動作、獎勵和環(huán)境進(jìn)行交互。針對DQN的4個關(guān)鍵要素，基于DQN車聯(lián)網(wǎng)環(huán)境下的任務(wù)卸載過程如下：當(dāng)決策者收到車輛的任務(wù)請求時，首先基于當(dāng)前環(huán)境狀態(tài)尋找最優(yōu)行動，然后將動作返回給車輛，該動作表示該任務(wù)是在車輛、邊緣服務(wù)器或云服務(wù)器上執(zhí)行；行動執(zhí)行后，決策者將收到該動作得到的獎勵；最后，環(huán)境進(jìn)入下一個狀態(tài)。

3.2 基于DQN的服務(wù)卸載方法SODQN

傳統(tǒng)的Q學(xué)習(xí)算法用Q表存儲t時刻的狀態(tài)、動作下獲得的Q值Q(st,at)，決策者通過遍歷Q表，尋找狀態(tài)St下獲得最大獎勵的動作。然而，隨著狀態(tài)空間和動作空間的增加，存儲Q值所需的內(nèi)存空間呈指數(shù)型增長，同時更新和搜索最佳卸載決策會產(chǎn)生大量的存儲和時間開銷。為了緩解這一問題，DQN采用神經(jīng)網(wǎng)絡(luò)近似估計不同狀態(tài)動作組合下的Q值，將Q表的更新問題變成一個函數(shù)擬合問題。因此，本文設(shè)計了一種基于DQN的任務(wù)卸載算法，如算法1所示。邊緣服務(wù)器將道路段中用戶的服務(wù)需求、網(wǎng)絡(luò)發(fā)射功率、無線信道增益，以及剩余子信道和計算資源等組合為系統(tǒng)狀態(tài)st輸入DQN網(wǎng)絡(luò)，計算出狀態(tài)st下所有動作的近似Q值(第6行)，并將該狀態(tài)下的所有Q值和狀態(tài)st輸入算法2(ActionSelection)決策出最優(yōu)動作at(第7行)，根據(jù)該動作進(jìn)行服務(wù)卸載(第8行)；服務(wù)卸載完成后，智能體觀測到環(huán)境的下一個狀態(tài)和該動作的獎勵rt(第9行)，并將經(jīng)驗et=(st,at,rt,st+1)存儲到經(jīng)驗池D(第10行)；將網(wǎng)絡(luò)參數(shù)θpre和θtar、經(jīng)驗池D，以及當(dāng)前的狀態(tài)st輸入算法3(DQNNetworkUpdate)更新DQN網(wǎng)絡(luò)(第11行)。

算法1SODQN算法。

輸入:預(yù)測網(wǎng)絡(luò)Qpre、參數(shù)θpre、目標(biāo)網(wǎng)絡(luò)Qtar、參數(shù)θtar、經(jīng)驗池D、當(dāng)前狀態(tài)st。

輸出:一個動作at。

1: 初始化經(jīng)驗池D的大小為N

2: 使用隨機權(quán)重初始化Qpre的參數(shù)θpre

3: 使用隨機權(quán)重初始化Qtar的參數(shù)θtar,θtar=θpre

4: for episode=1 to M do

5: for t=1 to T do

6: 狀態(tài)st下所有動作的近似Q值

7: at= ActionSelection(st,Q值)

8: 根據(jù)at判斷服務(wù)為本地執(zhí)行，或者卸載到邊緣服務(wù)器，或者卸載到云端

9: 計算獎勵rt并觀察下一個狀態(tài)st+1

10: 將經(jīng)驗et=(st,at,rt,st+1)存儲到經(jīng)驗池D中

11: θpre,θtar=DQNNetworkUpdate(θpre，θtar，D，st)

12: end for

13:end for

14:output at

下面分別提出SODQN算法中的兩個關(guān)鍵步驟——動作選擇和DQN網(wǎng)絡(luò)更新，并給出相應(yīng)的算法。

3.3 動作選擇

在決策過程中，強化學(xué)習(xí)算法如果在狀態(tài)st下每次都選擇Q值最大的動作，則易導(dǎo)致卸載策略終止于局部最優(yōu)。因此，在SODQN算法中采用貪婪算法(ε-greedy)進(jìn)行一定比例的隨機探索。具體而言，貪婪算法在每次動作時以概率ε隨機選擇一個動作，從而避免了每次都選擇Q值最大的動作。SODQN算法中的動作選擇定義為

(22)

動作選擇偽代碼如算法2所示，當(dāng)輸入的概率小于ε時，at為在動作空間中隨機選擇動作(第2～3行)，否則選擇Q值最大的動作(第4～5行)。

算法2動作選擇(ActionSelection)。

輸入：當(dāng)前狀態(tài)st,Q值。

輸出：一個動作at。

1: s=st

2: if概率<ε then

3: at為在動作空間中隨機選擇動作

4:else

5: at=argmaxatQ(st,at)(選擇Q值最大的動作)

6: outputat

3.4 網(wǎng)絡(luò)更新

為了保證打破數(shù)據(jù)的相關(guān)性和訓(xùn)練的穩(wěn)定性，DQN引入經(jīng)驗回放機制和雙網(wǎng)絡(luò)機制兩種重要的技術(shù)。

(1)經(jīng)驗回放機制 為了進(jìn)行經(jīng)驗回放，DQN將智能體和環(huán)境進(jìn)行交互的經(jīng)驗數(shù)據(jù)et=(st,at,rt,st+1)存儲到經(jīng)驗池D={e1,…,et,…,eN}，并在訓(xùn)練時對經(jīng)驗池D中的經(jīng)驗數(shù)據(jù)進(jìn)行隨機小批量采樣，從而解決了數(shù)據(jù)的相關(guān)性及非靜態(tài)分布問題。

(2)雙網(wǎng)絡(luò)機制 為了保證訓(xùn)練的穩(wěn)定性并避免Q值估計過高，在訓(xùn)練時引入預(yù)測網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)雙網(wǎng)絡(luò)。其中預(yù)測網(wǎng)絡(luò)Qpre用于估計每個動作的Q值，目標(biāo)網(wǎng)絡(luò)Qtar用于評估動作選擇的貪婪策略。目標(biāo)網(wǎng)絡(luò)與預(yù)測網(wǎng)絡(luò)結(jié)構(gòu)相同，每經(jīng)過C輪迭代，即將預(yù)測網(wǎng)絡(luò)的參數(shù)θpre復(fù)制給目標(biāo)網(wǎng)絡(luò)的參數(shù)θtar。預(yù)測網(wǎng)絡(luò)參數(shù)θpre用于估計策略并選擇動作，目標(biāo)網(wǎng)絡(luò)參數(shù)θtar用于估計Q值以衡量動作價值，最終兩種網(wǎng)絡(luò)之間通過交替更新參數(shù)實現(xiàn)解耦。因此兩個網(wǎng)絡(luò)參數(shù)在一段時間內(nèi)保持差異性，從而利用當(dāng)前Q值和目標(biāo)Q值計算損失，然后用小批量隨機梯度下降(Mini-batch Stochastic Gradient Descent, MSGD)反向更新預(yù)測網(wǎng)絡(luò)的參數(shù)θpre。DQN的損失函數(shù)

Li(θi)=[(yi-Qpre(st,ai;θpre))2]。

(23)

式中yi為由目標(biāo)網(wǎng)絡(luò)生成的目標(biāo)Q值，

(24)

在損失函數(shù)的基礎(chǔ)上，采用算法3概括DQN網(wǎng)絡(luò)的更新過程。

算法3中，首先從經(jīng)驗池D中隨機小批量抽取minbatch組經(jīng)驗數(shù)據(jù)組成Dτ(步驟1)，然后通過訓(xùn)練Dτ數(shù)據(jù)更新網(wǎng)絡(luò)參數(shù)，具體步驟如下：

步驟1計算經(jīng)驗數(shù)據(jù)et=(st,at,rt,st+1)對應(yīng)的目標(biāo)Q值(第3行)。

步驟2通過目標(biāo)Q值和損失函數(shù)Li(θi)計算預(yù)測網(wǎng)絡(luò)Qpre的損失值(第4行)。

步驟3采用MSGD最小化預(yù)測網(wǎng)絡(luò)Qpre的損失值，同時反向更新Qpre的參數(shù)θpre(第5行)。

步驟4重復(fù)上述操作C輪后，復(fù)制參數(shù)θpre來更新目標(biāo)網(wǎng)絡(luò)參數(shù)θtar(第6行)。

算法3網(wǎng)絡(luò)更新(DQNNetworkUpdate)。

輸入：預(yù)測網(wǎng)絡(luò)Qpre、參數(shù)θpre、目標(biāo)網(wǎng)絡(luò)Qtar、參數(shù)θtar、經(jīng)驗池D，當(dāng)前狀態(tài)st。

輸出：θpre，θtar。

1: 從經(jīng)驗池D中隨機抽取B條經(jīng)驗數(shù)據(jù)et=(st,at,rt,st+1),構(gòu)成小批量訓(xùn)練集為Dτ

2: for et=(st,at,rt,st+1) in Dτdo

3: 計算目標(biāo)Q值yi

4: 計算損失函數(shù)Li(θi)

5: 通過最小化Li(θi)更新預(yù)測網(wǎng)絡(luò)的參數(shù)θpre

6: C輪迭代后復(fù)制參數(shù)θpre來更新目標(biāo)網(wǎng)絡(luò)參數(shù)θtar

7:end for

8:output θpre, θtar

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

4.1 實驗平臺與實驗數(shù)據(jù)集

本文實驗的硬件環(huán)境使用英特爾(Intel)十代G6400奔騰2核4線程CPU，所有實驗環(huán)境均使用Python 3.6和Tensorflow 1.2.0實現(xiàn)。本文采用模擬數(shù)據(jù)作為實驗數(shù)據(jù)集，通過搭建模擬車聯(lián)網(wǎng)平臺實時生成車載用戶數(shù)據(jù)集，數(shù)據(jù)集包括超過1億條的模擬車載用戶信息。

4.2 實驗參數(shù)設(shè)置

由于CPU為2核四線程，每個邊緣服務(wù)器可以并行執(zhí)行4個任務(wù)。每個用戶開始時會從5種類型服務(wù)中隨機產(chǎn)生多種類型服務(wù)的服務(wù)需求，根據(jù)文獻(xiàn)[2]，設(shè)置5種類型服務(wù)所需的輸入數(shù)據(jù)為[25,30,40,45,60](單位：MB)，服務(wù)所需的計算量為[0.5,0.6,0.7,0.8,1.2](單位：Gigacycles)，產(chǎn)生各個服務(wù)需求的概率分別為[0.2,0.3,0.15,0.15,0.2]。為了評估SODQN方法在不同環(huán)境中的性能表現(xiàn)，根據(jù)文獻(xiàn)[2，29]，設(shè)置不同車聯(lián)網(wǎng)環(huán)境下每個道路段中網(wǎng)絡(luò)的總帶寬為20，30，40(單位：MHz)，而固定每一個子信道所占用的帶寬為1 MHz；邊緣服務(wù)器的計算能力為2.5，5，7.5(單位：Gigacycle/s)，而固定每份計算資源的計算能力為0.5 Gigacycle/s。因此，在不同環(huán)境中，子信道數(shù)可能為20，30，40，計算資源數(shù)可能為5，10，15。實驗中其余參數(shù)的設(shè)置如表1所示。

表1 CK度量元

4.3 實驗結(jié)果

本文選擇3種車聯(lián)網(wǎng)邊緣計算環(huán)境下的服務(wù)卸載方法與SODQN方法進(jìn)行對比：

(1)全本地卸載(Locally Offloading, LO) 將邊緣車聯(lián)網(wǎng)用戶產(chǎn)生的服務(wù)需求全部通過配置在本地的車載應(yīng)用執(zhí)行。

(2)全云端卸載(Cloud Offloading, CO) 當(dāng)車載用戶產(chǎn)生服務(wù)請求時，邊緣服務(wù)器全部上傳到云端進(jìn)行相應(yīng)的服務(wù)卸載操作。

(3)隨機卸載(Random Offloading, RO) 邊緣服務(wù)器隨機給用戶分配子信道和計算資源進(jìn)行相應(yīng)的服務(wù)卸載操作。

模擬環(huán)境為3個邊緣服務(wù)器、7個用戶，每個用戶開始時會從5種類型服務(wù)中隨機產(chǎn)生多種類型服務(wù)的服務(wù)需求，共生成20個任務(wù)，計算執(zhí)行所有用戶的服務(wù)需求產(chǎn)生的平均用戶服務(wù)延遲。實驗方案如下：

(1)通過改變系統(tǒng)中子信道和計算資源的個數(shù)，比較SOD和對比方法在不同車聯(lián)網(wǎng)邊緣計算環(huán)境中的表現(xiàn)。

(2)實驗中原始數(shù)據(jù)的平均大小在30 MB～70 MB之間，邊緣服務(wù)器的計算能力為2.5 Gigacycle/s，子信道數(shù)為20，比較SODQN和對比方法在不同車聯(lián)網(wǎng)邊緣計算環(huán)境中的表現(xiàn)。其中，使用學(xué)習(xí)率為0.01的DQN網(wǎng)絡(luò)進(jìn)行用戶服務(wù)卸載決策。

當(dāng)邊緣服務(wù)器的計算能力較弱(可分配的計算資源數(shù)為5)時，不同服務(wù)卸載方法在不同網(wǎng)絡(luò)環(huán)境下的表現(xiàn)如圖3所示。實驗結(jié)果表明，SODQN方法在各種網(wǎng)絡(luò)環(huán)境下的服務(wù)卸載表現(xiàn)均優(yōu)于其他方法。因為邊緣服務(wù)器CPU為2核四線程，以RO方法和SODQN方法可并行執(zhí)行4個線程，比LO方法(串行執(zhí)行)的用戶平均服務(wù)時延大幅降低。當(dāng)系統(tǒng)中的子信道數(shù)分別為20，30，40時，SODQN的用戶平均服務(wù)時延分別為1.073，1.015,0.955(單位：s)，相比表現(xiàn)最差的LO和CO方法，SODQN方法的性能提升了52.1%～76.3%。而和表現(xiàn)最好的RO方法比較，SODQN的用戶平均服務(wù)時延也降低了11.6%～14.1%。該實驗證明，SODQN方法在邊緣服務(wù)器計算能力較弱時，具備為用戶提供低時延服務(wù)的能力。

當(dāng)系統(tǒng)中所配備的邊緣服務(wù)器計算資源數(shù)為10時，實驗結(jié)果如圖4所示。可見，當(dāng)子信道個數(shù)為20，30，40時，相比其他4種方法，SODQN方法均較大幅度地減小了用戶的平均服務(wù)時延。例如，當(dāng)子信道個數(shù)為40時，用LO，CO，RO作為服務(wù)卸載方法所產(chǎn)生的用戶平均服務(wù)時延分別為4.023，2.132，0.954(單位：s)，而用SODQN方法時用戶的平均服務(wù)時延僅為0.863 s，其性能提升了9.5%～78.5%。當(dāng)系統(tǒng)中能夠分配的子信道個數(shù)為30時，相比LO和CO方法，SODQN方法較大幅度地降低了用戶平均服務(wù)時延，然而相比RO方法，SODQN方法產(chǎn)生的用戶平均服務(wù)時延下降不多，約為0.095 s，但是仍降低了9.7%左右。

當(dāng)邊緣服務(wù)器中的計算資源比較充足(計算資源數(shù)為15)時，車載用戶能夠?qū)⒏嗟姆?wù)需求卸載到邊緣服務(wù)器上，因此相比全本地卸載能夠獲得更低的用戶服務(wù)時延，實驗結(jié)果也支持該結(jié)論。如圖5所示，無論子信道數(shù)有多少，當(dāng)計算資源數(shù)為15時，SODQN方法的表現(xiàn)或優(yōu)于或相近于其他4個方法。例如，當(dāng)子信道數(shù)為20時，SODQN方法相比LO，CO，RO方法，用戶平均服務(wù)時延降低78.0%，60.3%，8.8%；當(dāng)子信道數(shù)為30和40時，采用SODQN方法能降低7.3%～79.1%和7.8%～79.8%的用戶平均服務(wù)時延。需要注意的的是，與子信道數(shù)為30相比，子信道數(shù)為40時采用SODQN方法產(chǎn)生的用戶平均服務(wù)延遲降低了0.03 s，當(dāng)任務(wù)數(shù)為20時，增加子信道數(shù)對降低用戶平均服務(wù)延遲的效果已經(jīng)不明顯，子信道數(shù)為30～40可以滿足用戶服務(wù)需求。

實驗中設(shè)置邊緣服務(wù)器的計算能力為10 Gigacycle/s，子信道數(shù)為20，原始數(shù)據(jù)量平均為30 MB～70 MB，其他參數(shù)保持不變。如圖6所示，LO，RO，CO，SODQN 4種方法的用戶平均服務(wù)時延均隨原始數(shù)據(jù)量的增加而增加，這是因為車載設(shè)備的計算能力通常不足，難以滿足計算密集型服務(wù)的低延遲需求。需要注意的是，當(dāng)原始數(shù)據(jù)量大于等于70 MB時，RO方法產(chǎn)生的用戶平均服務(wù)時延將高于CO方法，同時SODQN卸載方法降低的用戶平均服務(wù)時延并不顯著，原因是隨著原始數(shù)據(jù)量的增加，將產(chǎn)生大量傳輸時延。未來有望通過5G通信減少數(shù)據(jù)傳輸時間，并通過SODQN進(jìn)一步降低用戶平均服務(wù)時延，來提高服務(wù)卸載的服務(wù)質(zhì)量水平。

綜上所述，本文SODQN方法在各種車聯(lián)網(wǎng)邊緣計算環(huán)境中均能顯著降低用戶的平均服務(wù)時延，相比其他4種對比方法，性能有2.8%～73.3%不等的提升。CO方法將所有用戶服務(wù)需求卸載到云端執(zhí)行，雖然云端計算資源豐富無需考慮任務(wù)的執(zhí)行時延，但是遠(yuǎn)距離傳輸將產(chǎn)生巨大的傳輸時延，因此表現(xiàn)較差；LO將所有用戶的服務(wù)需求卸載到本地執(zhí)行，雖然節(jié)省了服務(wù)需求執(zhí)行時的傳輸時延和等待時延，但是因為車輛一般不會配備豐富的計算資源，所以會增大服務(wù)時延；針對RO方法，即使邊緣服務(wù)器可同時并發(fā)執(zhí)行4個任務(wù)，由于其隨機分配資源導(dǎo)致方法無法制定最優(yōu)卸載策略，表現(xiàn)也較差。綜合來看，在4種對比方法中，RO使用邊緣服務(wù)器同時執(zhí)行4個任務(wù)，相比LO和CO方法雖然可以大幅降低用戶的服務(wù)平均時延，但是其隨機分配資源導(dǎo)致無法制定最優(yōu)卸載策略，因此產(chǎn)生的用戶等待時延和執(zhí)行時延較大。而SODQN方法在網(wǎng)絡(luò)訓(xùn)練完成之后，只需一次前向傳播操作即可制定最優(yōu)卸載策略，在降低方法復(fù)雜度的同時能夠精確分配資源，其綜合表現(xiàn)優(yōu)于RO方法。由此可以證明，SODQN方法能夠在各種網(wǎng)絡(luò)和邊緣環(huán)境下降低用戶服務(wù)時延，提高車聯(lián)網(wǎng)用戶的服務(wù)體驗。

6 結(jié)束語

為了滿足車聯(lián)網(wǎng)用戶對低時延服務(wù)的需求，本文提出基于DQN的車聯(lián)網(wǎng)邊緣計算服務(wù)卸載方法SODQN，來降低車聯(lián)網(wǎng)用戶長期的平均服務(wù)時延，為車聯(lián)網(wǎng)用戶提供高質(zhì)量的服務(wù)體驗。特別地，本研究提出一種“端—邊—云”協(xié)同的服務(wù)卸載架構(gòu)，將車輛邊緣環(huán)境下的服務(wù)卸載問題歸約為邊緣服務(wù)器計算和通信資源約束下獲得最小平均服務(wù)時延的優(yōu)化問題。其次，引入DQN解決優(yōu)化問題。最后，與其他3種方法進(jìn)行對比實驗，表明SODQN方法能夠有效降低用戶平均服務(wù)時延，驗證了本文方法的有效性。下一步將在考慮用戶服務(wù)時延需求的同時，研究如何進(jìn)一步降低用戶服務(wù)的能耗，以及將集中式的服務(wù)卸載架構(gòu)結(jié)合聯(lián)邦學(xué)習(xí)搭建為分布式服務(wù)卸載架構(gòu)。