一種基于深度強(qiáng)化學(xué)習(xí)的任務(wù)卸載方法*

高宇豆 ，黃祖源 ，王海燕 ，保 富 ，張 航 ，李 輝

(1.云南電網(wǎng)有限責(zé)任公司 信息中心，云南 昆明 650214；2.西南林業(yè)大學(xué) 大數(shù)據(jù)與智能工程學(xué)院，云南 昆明 650224)

0 引言

車聯(lián)網(wǎng)(Internet of Vehicle，IoV)是車載網(wǎng)(Vehicular Ad hoc Network，VANET)和物聯(lián)網(wǎng)(Internet of Things，IoT)的深度融合，旨在提高車輛網(wǎng)絡(luò)的性能，降低交通擁堵的風(fēng)險[1]。在車聯(lián)網(wǎng)中，許多車輛應(yīng)用不僅需要大量的計算資源，還對響應(yīng)時間有嚴(yán)格的要求[2]。但是，車輛是計算資源和通信能力有限的裝置。對于這些計算密集、延遲敏感的應(yīng)用，車輛無法提供足夠的計算和存儲資源[3]。

為應(yīng)對車載應(yīng)用所需的大量計算資源，云計算被視為一種可行的解決方案。在云計算環(huán)境下，車輛可以通過無線網(wǎng)絡(luò)將計算密集型應(yīng)用卸載到云上運(yùn)行。這種端-云協(xié)作的計算模式很好地擴(kuò)展了車輛的計算能力[4]。

然而，對于計算密集、延遲敏感的應(yīng)用，端-云協(xié)作的計算模式是不夠的。因為，遠(yuǎn)程任務(wù)卸載帶來的高傳輸延遲會降低用戶體驗[3]。為解決此問題，將車聯(lián)網(wǎng)和邊緣計算相結(jié)合的車輛邊緣計算，被認(rèn)為是滿足低延遲的更好解決方案[5]。

但是，由于邊緣服務(wù)器具有的計算資源和存儲資源是有限的，過多的卸載任務(wù)會導(dǎo)致邊緣服務(wù)器過載[6]。在邊緣服務(wù)器過載情況下，任務(wù)的等待時間會顯著延長，從而增加任務(wù)的完成時間。為此，本文提出了一種車聯(lián)網(wǎng)中基于深度強(qiáng)化學(xué)習(xí)的任務(wù)卸載方法，主要貢獻(xiàn)包括以下幾點：

(1)把以最小化任務(wù)完成時間為目標(biāo)的多任務(wù)卸載問題規(guī)約為優(yōu)化問題；

(2)提出了一種基于深度強(qiáng)化學(xué)習(xí)的任務(wù)卸載算法，使用深度強(qiáng)化學(xué)習(xí)來求解上述優(yōu)化問題；

(3)通過實驗，驗證了所提算法的有效性。

1 相關(guān)工作

相關(guān)學(xué)者使用動態(tài)規(guī)劃方法對任務(wù)卸載進(jìn)行了研究。文獻(xiàn)[7]使用二次約束二次規(guī)劃方法，提出了一種兩層計算卸載框架，用于將移動用戶和小基站的計算密集型任務(wù)分別卸載到移動邊緣服務(wù)器和宏基站；文獻(xiàn)[8]基于混合整數(shù)線性規(guī)劃方法，提出一種對邊緣云上的計算、緩存和通信進(jìn)行聯(lián)合優(yōu)化的方法；在此基礎(chǔ)上，文獻(xiàn)[9]提出了一種基于混合整數(shù)非線性規(guī)劃的任務(wù)卸載方法，實現(xiàn)了在節(jié)省用戶設(shè)備電池壽命的同時最大限度地減少延遲。這些工作主要將計算卸載問題規(guī)約為凸優(yōu)化問題，使用動態(tài)規(guī)劃方法對問題進(jìn)行求解。但是，車輛邊緣計算環(huán)境下的任務(wù)卸載未必總是凸優(yōu)化的。

相關(guān)學(xué)者使用博弈論對任務(wù)卸載進(jìn)行了研究。文獻(xiàn)[10]將移動設(shè)備用戶間的分布式計算卸載決策問題規(guī)約為一個多用戶計算卸載博弈，并設(shè)計了一個可以達(dá)到納什均衡的分布式計算卸載算法；文獻(xiàn)[11]使用博弈論，提出了一個移動感知的分層邊緣計算框架，實現(xiàn)同時降低智能設(shè)備的能源成本和任務(wù)執(zhí)行時間；文獻(xiàn)[12]研究了基于端-邊-云車聯(lián)網(wǎng)下的計算卸載機(jī)制，提出了各種基于博弈論的任務(wù)卸載優(yōu)化策略，可用于邊緣服務(wù)器的選擇和任務(wù)傳輸管理。這些工作僅考慮了卸載策略對系統(tǒng)一個快照的最優(yōu)方案或接近最優(yōu)方案，未考慮車輛邊緣計算環(huán)境下當(dāng)前策略對資源分配的長期影響。

與上述工作相比，本文工作的主要區(qū)別在于：使用深度強(qiáng)化學(xué)習(xí)方法來求解車輛邊緣計算環(huán)境下的任務(wù)卸載問題。由于深度學(xué)習(xí)方法能提高對車輛網(wǎng)絡(luò)的認(rèn)知能力，因此該方法能更好地學(xué)習(xí)到任務(wù)卸載的復(fù)雜特征。

2 本文方法

2.1 車輛網(wǎng)邊緣計算架構(gòu)

本文將考慮多任務(wù)的車輛網(wǎng)邊緣計算架構(gòu)。此架構(gòu)由1 個基站(Base Station，BS)、k 輛車、m 個路側(cè)單元(Road Side Unit，RSU)和m 個邊緣服務(wù)器組成，其中，車輛集表示為V={v1，v2，…，vK}，路側(cè)單元集表示為R={r1，r2，…，rM}，邊緣服務(wù)器集表示為S={s1，s2，…，sM}。在此架構(gòu)下，借鑒文獻(xiàn)中基站的思想[13]，本文將基站作為控制實體，用于獲取邊緣計算可用資源、信道可用資源、任務(wù)信息等；道路旁的每個路側(cè)單元配備了一個邊緣服務(wù)器；每個邊緣服務(wù)器可為其覆蓋范圍內(nèi)的車輛提供計算和存儲資源；車輛是任務(wù)的產(chǎn)生者，通過無線網(wǎng)絡(luò)與路側(cè)單元進(jìn)行通信。

在給定的時間間隔t，每輛車可以產(chǎn)生多個任務(wù)。每個任務(wù)表示為二元組Ti，j=＜di，j，ci，j＞，其中，di，j表示執(zhí)行第i 輛車產(chǎn)生的第j 個任務(wù)所需的數(shù)據(jù)量的大小，ci，j表示執(zhí)行第i 輛車產(chǎn)生的第j 個任務(wù)所需的計算量的大小，i∈[1，2，…，K]，j∈[1，2，…，J]。這些任務(wù)通路側(cè)單元可以被卸載到邊緣服務(wù)器上執(zhí)行。

2.2 本地計算模型

當(dāng)車輛vi產(chǎn)生的任務(wù)Ti，j在本地執(zhí)行時，則該任務(wù)的完成時間由兩部分組成：執(zhí)行時間和等待時間，定義如下：

2.3 卸載計算模型

當(dāng)車輛vi產(chǎn)生的任務(wù)Ti，j被卸載到邊緣服務(wù)器執(zhí)行時，則該任務(wù)的完成時間由四部分組成：任務(wù)所需數(shù)據(jù)的傳輸時間、任務(wù)在邊緣服務(wù)器的執(zhí)行時間、任務(wù)在邊緣服務(wù)器的等待時間和執(zhí)行結(jié)果返回時間，定義如下：

進(jìn)一步，本文考慮車輛與路側(cè)單元間的無線傳輸是基于正交頻分多址的，則數(shù)據(jù)傳輸率si，l又由分配給任務(wù)的上行線路的帶寬、車輛的傳輸功率ρi、車輛與路側(cè)單元間的信道增益決定λi，l。于是，數(shù)據(jù)傳輸率的定義如下：

其中，B 表示上線線路的帶寬，N 表示將帶寬分為N 份，σ 表示高斯噪聲。

其中，αe表示邊緣服務(wù)器每個計算單元的計算能力(單位為GHz)，βe表示邊緣服務(wù)器分配車輛給任務(wù)的單元數(shù)。

2.4 問題定義

在多任務(wù)的車輛邊緣計算架構(gòu)下，任務(wù)卸載的目標(biāo)是：通過優(yōu)化任務(wù)卸載決策，最小化任務(wù)的完成時間。

首先，需要定義任務(wù)卸載決策。由于每個任務(wù)要么在本地執(zhí)行，要么被卸載邊緣服務(wù)器執(zhí)行，故而，任務(wù)卸載決策可以定義為：

其中，αi，j為卸載決策變量，其定義如下：

其次，定義每個任務(wù)的完成時間。基于卸載決策變量，任務(wù)的完成時間定義如下：

最后，基于上述分析，以最小化任務(wù)完成時間為目標(biāo)的多任務(wù)卸載問題可以規(guī)約為一個如下所示的單目標(biāo)優(yōu)化問題：

3 基于深度強(qiáng)化學(xué)習(xí)的任務(wù)卸載

本節(jié)將提出一種基于深度強(qiáng)化學(xué)習(xí)的任務(wù)卸載算法，使用DQN 來求解優(yōu)化問題。該算法主要包括四部分內(nèi)容：(1)設(shè)置DQN 的配置；(2)基于DQN 的任務(wù)卸載算法；(3)基于ε-貪婪策略的動作選擇；(4)使用經(jīng)驗回放來更新DQN。

3.1 DQN 的配置

DQN 是一種基于值的深度強(qiáng)化學(xué)習(xí)方法，將強(qiáng)化學(xué)習(xí)和深度學(xué)習(xí)進(jìn)行了很好的結(jié)合。其核心是：使用神經(jīng)網(wǎng)絡(luò)來近似傳統(tǒng)Q-Learning 算法中的Q 函數(shù)[14]。本文選擇DQN 的原因是：在面對高維空間的復(fù)雜問題時，DQN能夠很好地學(xué)習(xí)到優(yōu)化策略。

在多任務(wù)的車輛邊緣計算架構(gòu)下，為了利用DQN，需要設(shè)置DQN 的配置，包括agent、環(huán)境、狀態(tài)和獎勵。

首先，在基站上部署agent。agent 通過一系列的觀察、動作和獎勵對環(huán)境做出反應(yīng)。具體地，當(dāng)收到來自車輛的任務(wù)請求時，agent 根據(jù)當(dāng)前觀察(狀態(tài))選擇動作，并確定卸載決策變量。然后，agent 將卸載決策變量回傳給車輛，以指示車輛是否卸載該任務(wù)。任務(wù)執(zhí)行結(jié)束后，再將任務(wù)的本地完成時間與邊緣服務(wù)器上完成時間的差值作為獎勵反饋給agent。

其次，環(huán)境由車輛網(wǎng)絡(luò)組成，主要包括邊緣服務(wù)器的計算資源、路側(cè)單元的帶寬資源和任務(wù)信息。其定義如下：

然后，在時間步τ，觀察（狀態(tài)）由邊緣服務(wù)器的可用計算資源和路側(cè)單元的可用帶寬資源組成。其定義如下：

最后，在時間步τ，對于任務(wù)Ti，j，動作a 的獎勵由任務(wù)的本地完成時間與邊緣服務(wù)器上完成時間的差值組成。其定義如下：

3.2 卸載算法框架

當(dāng)動作和狀態(tài)對空間變得高維連續(xù)時，傳統(tǒng)的QLearning 算法遍歷高維Q-table 是非常耗時的。為了解決這一問題，DQN 使用深度神經(jīng)網(wǎng)絡(luò)來近似Q(s，a)?；舅枷胧牵菏紫?，agent 根據(jù)對當(dāng)前環(huán)境觀察得到狀態(tài)s；其次，將狀態(tài)s 作為深度神經(jīng)網(wǎng)絡(luò)的輸入，得到神經(jīng)網(wǎng)絡(luò)輸出的多個Q(s，a)；然后，使用ε-貪婪策略從這多個Q(s，a)中選擇一個動作a，與此同時，環(huán)境將響應(yīng)選定的動作，給出獎勵r，并演化到新狀態(tài)s'；最后，將(s，a，r，s')存入經(jīng)驗池D，并使用D 更新DQN。

基于上述分析，算法1 給出了基于DQN 的任務(wù)卸載算法框架，記為DQN。

算法1 基于DQN 的任務(wù)卸載(DQN)：

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

輸出：預(yù)測網(wǎng)絡(luò)和目標(biāo)網(wǎng)絡(luò)。

在動作選擇上，DQN 引入了ε-貪婪策略。具體地，agent 采用1-ε 概率來選擇最大Q 值的動作，采用概率ε來隨機(jī)選擇動作。因此，基于ε-貪婪策略的動作選擇可定義為：

3.3 DQN 網(wǎng)絡(luò)更新

為了進(jìn)一步打破數(shù)據(jù)間的關(guān)聯(lián)性、防止過擬合，在訓(xùn)練過程中，DQN 使用了預(yù)測網(wǎng)絡(luò)Qpre和目標(biāo)網(wǎng)絡(luò)θtar。具體地，針對當(dāng)前的動作對(s，a)，預(yù)測網(wǎng)絡(luò)Qpre使用最新參數(shù)θpre預(yù)測當(dāng)前Q 值，而目標(biāo)網(wǎng)絡(luò)使用很久前的參數(shù)θtar得到目標(biāo)Q 值。與預(yù)測網(wǎng)絡(luò)相比，目標(biāo)網(wǎng)絡(luò)的結(jié)構(gòu)完全相同，但參數(shù)不同。

DQN 的代價函數(shù)可以定義如下：

其中，ri是當(dāng)前獲得的獎勵，γ 是折現(xiàn)系數(shù)。

基于損失函數(shù)，算法2 描述了DQN 的更新過程。

算法2 DQN 網(wǎng)絡(luò)的更新：

輸入：預(yù)測網(wǎng)絡(luò)Qpre，預(yù)測網(wǎng)絡(luò)的參數(shù)θpre，目標(biāo)網(wǎng)絡(luò)Qtar，目標(biāo)網(wǎng)絡(luò)的參數(shù)θtar；

輸出：θpre，θtar。

(1)從經(jīng)驗池中隨機(jī)采樣得到Dτ；

(2)使用式(18)計算目標(biāo)Q 值yi；

(3)使用式(17)計算代價函數(shù)Li(θi)；

(4)對Li(θi)使用梯度下降，以更新預(yù)測網(wǎng)絡(luò)Qpre中的參 數(shù)θpre；

(5)每C 步后，使用參數(shù)θpre更新目標(biāo)網(wǎng)絡(luò)Qtar中的參 數(shù)θtar；

(6)輸 出θpre和θtar。

4 實驗

4.1 實驗設(shè)置

實驗考慮包含10 個RSU、10 輛車、30 個任務(wù)的場景。進(jìn)一步，實驗?zāi)M環(huán)境所需的參數(shù)設(shè)置如表1 所示。

表1 參數(shù)設(shè)置

實驗中，本文選擇下述3 個基準(zhǔn)算法，與本文所提DQN 方法進(jìn)行對比。

(1)本地任務(wù)卸載(LTO)。車輛產(chǎn)生的所有任務(wù)全部在本地執(zhí)行。

(2)隨機(jī)任務(wù)卸載(RTO)。車輛產(chǎn)生的任務(wù)隨機(jī)卸載到邊緣服務(wù)器執(zhí)行。

(3)邊緣任務(wù)卸載(ETO)。車輛產(chǎn)生的所有任務(wù)全部卸載到邊緣服務(wù)器執(zhí)行。

4.2 平均完成時間的比較

圖1 直觀顯示了30 個任務(wù)平均完成時間的對比。從圖1 可以看出：本文所提方法DQN 的性能優(yōu)于其他3種基準(zhǔn)算法。相比于表現(xiàn)最差的LTO 算法，DQN 算法的性能提升了15.5%；相比于表現(xiàn)較好的ETO 算法，TODQN算法的性能提升了4.1%。這是因為DQN 算法同時充分考慮了車輛邊緣計算環(huán)境下的計算資源和帶寬資源，而基準(zhǔn)算法沒有考慮這些資源對任務(wù)完成時間的影響。

圖1 平均完成時間的對比

4.3 參數(shù)對算法性能的影響

本實驗研究了各種參數(shù)對算法性能的影響，例如任務(wù)的數(shù)量、任務(wù)所需的數(shù)據(jù)量。

(1)任務(wù)的數(shù)量：本實驗中，其他參數(shù)保持不變，任務(wù)數(shù)量從30 增加到70。從圖2 可以看出，隨著任務(wù)數(shù)量的增多，任務(wù)總完成時間開始增加。相比于其他3 種基準(zhǔn)算法，DQN 算法的增加幅度最小。這是因為DQN 可以合理地利用車輛的計算資源和邊緣服務(wù)器的計算資源。

圖2 任務(wù)數(shù)量變化對總完成時間的影響

(2)任務(wù)計算量：本實驗中，其他參數(shù)保持不變，任務(wù)所需的計算量從0.5 Gigacycle 增加到1.3 Gigacycle。從圖3可以看出，隨著任務(wù)計算量的增加，所有算法的總完成時間都在增加，尤其是ETO 算法的性能逐漸低于RTO算法。這是因為邊緣服務(wù)器過載造成的。與ETO 和RTO相比，DQN 能很好地解決邊緣服務(wù)器過載的問題。

圖3 任務(wù)計算量變化對總完成時間的影響

5 結(jié)論

本文提出了一種車輛邊緣計算環(huán)境下基于深度強(qiáng)化學(xué)習(xí)的任務(wù)卸載方法。該方法使用DQN 對任務(wù)卸載問題進(jìn)行求解，可以得到具有最小完成時間的優(yōu)化卸載策略。通過實驗結(jié)果表明，該方法具有良好的性能。在下一步的研究工作中，將同時考慮任務(wù)完成時間和緩沖內(nèi)容的任務(wù)卸載。