于晶，魯凌云，李翔

（1.北京交通大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044；2.北京交通大學(xué) 軟件學(xué)院，北京 100044）

0 概述

隨著人工智能、5G 移動(dòng)通信和車(chē)聯(lián)網(wǎng)技術(shù)的發(fā)展，大量的智能車(chē)載應(yīng)用不斷被開(kāi)發(fā)，例如自動(dòng)駕駛、碰撞預(yù)警、虛擬現(xiàn)實(shí)等［1］。然而，計(jì)算密集型和時(shí)延敏感型的任務(wù)對(duì)于車(chē)載終端來(lái)說(shuō)無(wú)疑是一個(gè)巨大的挑戰(zhàn)。移動(dòng)云計(jì)算（Mobile Cloud Computing，MCC）能夠?qū)⑷蝿?wù)卸載到資源豐富的遠(yuǎn)程云服務(wù)器上，可以解決車(chē)輛計(jì)算能力不足的問(wèn)題［2］，因此成為解決上述矛盾的一個(gè)關(guān)鍵技術(shù)，但遠(yuǎn)距離任務(wù)傳輸帶來(lái)的時(shí)延無(wú)法滿足安全類(lèi)應(yīng)用對(duì)實(shí)時(shí)性的要求［3］。對(duì)此，移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）被引入到車(chē)聯(lián)網(wǎng)中，MEC 服務(wù)器被部署到道路兩側(cè)的路邊單元（Road Side Unit，RSU）中，為車(chē)輛提供近距離的任務(wù)卸載服務(wù)［4］。相比于云計(jì)算卸載，邊緣計(jì)算卸載不僅可以緩解車(chē)輛終端的資源不足，而且可以降低任務(wù)傳輸時(shí)延，緩解核心網(wǎng)絡(luò)的壓力。

目前，針對(duì)車(chē)聯(lián)網(wǎng)中的任務(wù)卸載問(wèn)題，國(guó)內(nèi)外學(xué)者展開(kāi)了大量研究，但大部分研究都是單獨(dú)針對(duì)云計(jì)算卸載或者邊緣計(jì)算卸載，很少有研究關(guān)注云計(jì)算和邊緣計(jì)算的協(xié)作。此外，文獻(xiàn)往往假設(shè)MEC 服務(wù)器具有足夠資源，能夠滿足所有任務(wù)的卸載請(qǐng)求，然而事實(shí)并非如此。受硬件和成本的制約，MEC 服務(wù)器可提供的資源也相對(duì)有限，尤其是在車(chē)輛密集的區(qū)域，僅依靠邊緣層可能無(wú)法滿足海量數(shù)據(jù)的計(jì)算和存儲(chǔ)［5］。由于云計(jì)算和邊緣計(jì)算都擁有各自的優(yōu)勢(shì)，云服務(wù)器適合處理計(jì)算密集但對(duì)實(shí)時(shí)性要求低的任務(wù)，而邊緣服務(wù)器更適合處理計(jì)算量小或者對(duì)時(shí)延敏感的任務(wù)，因此，讓兩者相互協(xié)作以實(shí)現(xiàn)優(yōu)勢(shì)互補(bǔ)逐漸吸引了大家的關(guān)注。在網(wǎng)絡(luò)架構(gòu)方面，軟件定義網(wǎng)絡(luò)（Software Defined Network，SDN）技術(shù)由于具備轉(zhuǎn)控分離、集中控制、開(kāi)放接口、可編程等特性，因此對(duì)于實(shí)現(xiàn)邊云異構(gòu)網(wǎng)絡(luò)的有效協(xié)作具有重要意義［6］。

在車(chē)聯(lián)網(wǎng)中，影響卸載決策的因素比如車(chē)輛位置、服務(wù)器資源、信道狀態(tài)等都具有時(shí)變性，如果使用傳統(tǒng)的最優(yōu)化算法或者啟發(fā)式算法來(lái)求解最優(yōu)決策，不僅要對(duì)環(huán)境做出很多靜態(tài)假設(shè)，而且每當(dāng)有新任務(wù)時(shí)，都需要重新經(jīng)歷一次復(fù)雜度超高的計(jì)算［7］，這對(duì)于那些對(duì)時(shí)延極其敏感的安全類(lèi)應(yīng)用來(lái)說(shuō)無(wú)疑是巨大的隱患。除此之外，現(xiàn)有的工作在制定任務(wù)卸載決策和資源分配方案時(shí)很少考慮車(chē)載應(yīng)用的緊急程度，所以任務(wù)卸載到每個(gè)服務(wù)器的可能性是相同的，而且卸載到同一個(gè)服務(wù)器的任務(wù)分配到的資源也是相同的，這也許會(huì)導(dǎo)致對(duì)時(shí)延敏感的任務(wù)無(wú)法在限制時(shí)間內(nèi)完成。為簡(jiǎn)化問(wèn)題，很多采取部分卸載方式的方案中也會(huì)忽略車(chē)輛在上傳任務(wù)過(guò)程中的移動(dòng)性，并假設(shè)任務(wù)可以在剩余通信時(shí)間內(nèi)上傳完成，但這在實(shí)際應(yīng)用中是不現(xiàn)實(shí)的。

為解決上述問(wèn)題，本文綜合考慮環(huán)境動(dòng)態(tài)性以及任務(wù)優(yōu)先級(jí)，提出基于雙深度Q 網(wǎng)絡(luò)（Double Deep Q Network，DDQN）算法的邊云協(xié)作任務(wù)卸載機(jī)制，DDQN 算法在與環(huán)境交互過(guò)程中可以對(duì)未來(lái)的環(huán)境變化進(jìn)行一定程度的估計(jì)，通過(guò)不斷學(xué)習(xí)并調(diào)整策略實(shí)現(xiàn)長(zhǎng)期效用最大化。同時(shí)，提出基于任務(wù)優(yōu)先級(jí)的資源分配方案，使優(yōu)先級(jí)越高的任務(wù)能分配到的資源越多。此外，給出一種基于確定卸載決策和資源分配方案的的卸載比例計(jì)算方法，在任務(wù)能夠完成上傳的前提下，最小化任務(wù)處理時(shí)間。

1 相關(guān)研究

針對(duì)車(chē)輛邊緣計(jì)算環(huán)境中的任務(wù)卸載決策問(wèn)題，目前已經(jīng)有大量的研究工作。文獻(xiàn)［8］提出一種基于遺傳算法和啟發(fā)式規(guī)則的混合智能優(yōu)化算法，制定的卸載決策可以最小化時(shí)延和資源消耗。文獻(xiàn)［9］對(duì)多用戶多MEC 服務(wù)器場(chǎng)景中的負(fù)載均衡和任務(wù)卸載問(wèn)題進(jìn)行了聯(lián)合優(yōu)化。文獻(xiàn)［10-12］也基于各種數(shù)值優(yōu)化理論提出相應(yīng)的任務(wù)卸載和資源分配方案。強(qiáng)化學(xué)習(xí)作為解決復(fù)雜環(huán)境下序列決策問(wèn)題的強(qiáng)大武器，被學(xué)者們用來(lái)解決任務(wù)卸載問(wèn)題。文獻(xiàn)［13］將計(jì)算卸載調(diào)度問(wèn)題形式化為優(yōu)化時(shí)延和能耗組成的長(zhǎng)期成本問(wèn)題，并將其建模為一個(gè)等價(jià)的馬爾可夫決策過(guò)程（Markov Decison Process，MDP），設(shè)計(jì)的基于深度強(qiáng)化學(xué)習(xí)（Deep Reinforcement Learning，DRL）的算法可以得到問(wèn)題的最優(yōu)解。然而，上述工作均假設(shè)MEC 服務(wù)器擁有足夠多的計(jì)算和存儲(chǔ)資源，但是在實(shí)際場(chǎng)景中，MEC 的資源受限于硬件和成本，在車(chē)輛密集的區(qū)域可能無(wú)法保證服務(wù)質(zhì)量。

邊緣計(jì)算與云計(jì)算的融合可以構(gòu)建出更加高效可靠的邊云協(xié)作任務(wù)卸載環(huán)境。文獻(xiàn)［14］為充分利用云服務(wù)器和邊緣服務(wù)器的資源，提出約束隨機(jī)化卸載和約束啟發(fā)式貪心卸載兩種方案解決協(xié)同任務(wù)卸載問(wèn)題。文獻(xiàn)［15］通過(guò)構(gòu)建一個(gè)云端-邊緣-車(chē)輛三層協(xié)同的網(wǎng)絡(luò)，將任務(wù)卸載決策問(wèn)題形式化為收益和服務(wù)質(zhì)量最大化問(wèn)題，并提出由Kuhn-Munkres 算法、遺傳算法、內(nèi)點(diǎn)法和KKT 條件組成的算法求解上述非確定性多項(xiàng)式（Nondeterministic Polynomially，NP）問(wèn)題。包括上述文獻(xiàn)在內(nèi)的很多工作都假設(shè)動(dòng)態(tài)的車(chē)聯(lián)網(wǎng)環(huán)境可以被準(zhǔn)確地建模，然而，這在實(shí)際情況下很難做到。因此，能夠擺脫模型限制的DRL 算法特別適合用來(lái)解決復(fù)雜動(dòng)態(tài)車(chē)聯(lián)網(wǎng)環(huán)境中的任務(wù)卸載問(wèn)題。

文獻(xiàn)［16］研究了邊云協(xié)作環(huán)境中的非獨(dú)立任務(wù)卸載問(wèn)題，并且提出一個(gè)基于強(qiáng)化學(xué)習(xí)和序列二次規(guī)劃的兩級(jí)交替方法框架。文獻(xiàn)［17-19］利用DRL算法解決了車(chē)聯(lián)網(wǎng)中的任務(wù)卸載問(wèn)題。近年來(lái)，利用SDN 協(xié)助車(chē)聯(lián)網(wǎng)計(jì)算卸載的研究有一定的成果［20-22］，例如，文獻(xiàn)［21］通過(guò)設(shè)計(jì)一種集成SDN 和MEC 的車(chē)聯(lián)網(wǎng)框架，實(shí)現(xiàn)網(wǎng)絡(luò)、緩存和計(jì)算的動(dòng)態(tài)編排。文獻(xiàn)［22］構(gòu)建一種MEC 輔助的軟件定義車(chē)聯(lián)網(wǎng)架構(gòu)，并提出一種帶重處理機(jī)制的任務(wù)卸載方案，能夠在滿足時(shí)延約束的前提下最大化可靠性。

與現(xiàn)有工作相比，本文考慮了車(chē)聯(lián)網(wǎng)的時(shí)變性、任務(wù)的優(yōu)先級(jí)、通信鏈路的持續(xù)時(shí)間以及計(jì)算資源成本對(duì)任務(wù)卸載決策制定的綜合影響。還提出一種基于DDQN 的算法來(lái)學(xué)習(xí)任務(wù)卸載決策，該算法可以最大化由時(shí)延和成本構(gòu)成的長(zhǎng)期效用。

2 系統(tǒng)模型

2.1 系統(tǒng)架構(gòu)分析

如圖1 所示，本文構(gòu)建的基于SDN 的邊云協(xié)作車(chē)聯(lián)網(wǎng)架構(gòu)在邏輯上由用戶層、數(shù)據(jù)層和控制層組成。

圖1 基于SDN 的邊云協(xié)作車(chē)聯(lián)網(wǎng)架構(gòu)Fig.1 Architecture of edge-cloud collaborative vehicular network based on SDN

用戶層由行駛在一段單向雙車(chē)道公路上的車(chē)輛用戶構(gòu)成。本文假設(shè)每個(gè)時(shí)隙最多有n個(gè)車(chē)輛，車(chē)輛集合記為N={1，2，…，n}。每個(gè)車(chē)輛在同一時(shí)隙最多可以擁有一個(gè)待處理的任務(wù)，車(chē)輛i的任務(wù)描述為T(mén)i={di，ci，，θi}，其中：di是任務(wù)的總數(shù)據(jù)量，單位為比特（bit）；ci是完成任務(wù)Ti所需要的CPU 周期數(shù)；是任務(wù)可以容忍的時(shí)延上限；θi(0 ≤θi≤1)是任務(wù)的卸載比例，為充分利用車(chē)輛本地的計(jì)算資源并進(jìn)一步降低任務(wù)處理時(shí)延，本文采取部分卸載方式，將(1-θi)比例的任務(wù)留在本地處理，將車(chē)輛可用計(jì)算資源記為Flocal=

數(shù)據(jù)層由邊緣卸載計(jì)算層和云卸載計(jì)算層構(gòu)成，負(fù)責(zé)執(zhí)行用戶層車(chē)輛卸載的計(jì)算任務(wù)。其中，邊緣計(jì)算層是由m個(gè)依次部署在RSU 中的邊緣服務(wù)器構(gòu)成，邊緣服務(wù)器資源相對(duì)比較少，主要負(fù)責(zé)執(zhí)行對(duì)時(shí)延要求高或者對(duì)計(jì)算資源要求少的任務(wù)。車(chē)輛會(huì)通過(guò)無(wú)線車(chē)輛到基礎(chǔ)設(shè)施（Vehicle-to-Infrastructure，V2I）鏈路將任務(wù)上傳到其通信范圍內(nèi)的中繼RSU中，然后中繼RSU 通過(guò)有線基礎(chǔ)設(shè)施到基礎(chǔ)設(shè)施（Infrastructure-to-Infrastructure，I2I）鏈路將任務(wù)轉(zhuǎn)發(fā)給目標(biāo)MEC 服務(wù)器執(zhí)行。m個(gè)邊緣服務(wù)器當(dāng)前可用的資源可以表示為Fmec=云計(jì)算層由1 個(gè)部署在基站（Base Station，BS）中的云服務(wù)器構(gòu)成，云服務(wù)器具有充足的資源，用表示。但是遠(yuǎn)距離的任務(wù)傳輸會(huì)產(chǎn)生不可預(yù)測(cè)的時(shí)延，安全和隱私也得不到保障，所以云服務(wù)器的主要作用是彌補(bǔ)邊緣計(jì)算層資源的不足。一些計(jì)算量大且對(duì)時(shí)延要求較低的任務(wù)會(huì)被卸載到云服務(wù)器執(zhí)行，中繼RSU 通過(guò)有線光纖鏈路將任務(wù)轉(zhuǎn)發(fā)到云服務(wù)器中。本文構(gòu)建的邊云協(xié)作計(jì)算卸載環(huán)境可以通過(guò)優(yōu)勢(shì)互補(bǔ)的方式克服云計(jì)算和邊緣計(jì)算各自的缺點(diǎn)，充分發(fā)揮各自的長(zhǎng)處。

控制層主要是指部署在基站中的SDN 控制器。邏輯上集中的SDN 控制層具有瞬時(shí)獲取全局網(wǎng)絡(luò)狀態(tài)的能力，可配置、可編程、對(duì)第三方開(kāi)放的網(wǎng)絡(luò)基礎(chǔ)能力等一系列突破對(duì)于實(shí)現(xiàn)邊緣計(jì)算和云計(jì)算的有效協(xié)作具有重要意義，能夠幫助實(shí)現(xiàn)兩者的優(yōu)勢(shì)互補(bǔ)，滿足邊云協(xié)作計(jì)算網(wǎng)絡(luò)對(duì)于統(tǒng)一控制、任務(wù)合理卸載和資源有效分配的需求。

在本文構(gòu)建的基于SDN 的邊云協(xié)作計(jì)算環(huán)境中，車(chē)輛的計(jì)算任務(wù)會(huì)被部分卸載到云服務(wù)器或邊緣服務(wù)器中執(zhí)行，所有車(chē)輛在某個(gè)時(shí)隙的卸載決策集合可以表示為X={α1，α2，…，αi，…，αn}，其中，αi∈{0，1，2，…，m}，當(dāng)αi=0 時(shí)，表示車(chē)輛i的任務(wù)將被卸載到云服務(wù)器執(zhí)行；當(dāng)αi=j，j∈{1，2，…，m}時(shí)，表示車(chē)輛i的任務(wù)將被卸載到編號(hào)為j的邊緣服務(wù)器上執(zhí)行。

2.2 任務(wù)優(yōu)先級(jí)設(shè)定

考慮到車(chē)載應(yīng)用的多樣性，比如碰撞預(yù)警這類(lèi)對(duì)時(shí)延要求極高的安全類(lèi)應(yīng)用、語(yǔ)音識(shí)別這類(lèi)對(duì)時(shí)延不敏感的娛樂(lè)性應(yīng)用等，本文將抽象出一個(gè)任務(wù)優(yōu)先級(jí)的評(píng)定標(biāo)準(zhǔn)，用于指導(dǎo)計(jì)算資源的分配以及卸載策略的制定。除了任務(wù)的緊急程度，任務(wù)所需的計(jì)算量也是任務(wù)卸載和資源分配時(shí)必須參考的指標(biāo)，任務(wù)的優(yōu)先級(jí)可以定義為式（1）所示：

其中：psf是縮放系數(shù)，用來(lái)調(diào)整任務(wù)計(jì)算量或者時(shí)延對(duì)優(yōu)先級(jí)的影響程度。式（1）表明，任務(wù)所需計(jì)算量越大，或者任務(wù)所能容忍的最大時(shí)延越小，任務(wù)的優(yōu)先級(jí)越高。

2.3 通信模型

行駛在道路上的車(chē)輛需要將任務(wù)通過(guò)無(wú)線V2I鏈路傳給中繼RSU，鏈路的傳輸速率直接影響任務(wù)的上傳時(shí)間。根據(jù)香農(nóng)公式，車(chē)輛i與編號(hào)為k的中繼RSU 之間的無(wú)線數(shù)據(jù)傳輸速率Ri，k可以利用式（2）計(jì)算得到：

其中：Bi，k是信道帶寬；Pi，k是車(chē)輛i的發(fā)射功率；σ2是噪聲功率；信道增益Gi，k與車(chē)輛和RSU 之間的距離di，k密切相關(guān)，具體關(guān)系可以表示為Gi，k=-30-35lg(di，k)［23］。此 外，本文還假設(shè)車(chē)輛 和RSU 之間的無(wú)線通信采用了正交頻分多址技術(shù)，所以忽略了信道之間的干擾。

2.4 計(jì)算模型

本文除了將任務(wù)處理時(shí)延作為評(píng)價(jià)指標(biāo)，為了避免計(jì)算資源的浪費(fèi)，還引入成本這一因素來(lái)指導(dǎo)決策的制定。本文采取部分卸載方式，將任務(wù)在本地和服務(wù)器中按比例并行處理。任務(wù)Ti在本地處理部分所需時(shí)間的計(jì)算式如式（3）所示：

任務(wù)在本地處理時(shí)不消耗服務(wù)器的資源，所以沒(méi)有成本。卸載處理的那部分任務(wù)有邊緣服務(wù)器和云服務(wù)器兩類(lèi)選擇。

2.4.1 邊緣卸載

當(dāng)αi=j，j∈{1，2，…，m}時(shí)，車(chē)輛i的任務(wù)將被卸載到編號(hào)為j的MEC 服務(wù)器中執(zhí)行。任務(wù)的上傳時(shí)間計(jì)算式如式（4）所示：

其中：δi用來(lái)調(diào)整時(shí)延和成本所占的權(quán)重；Ce是MEC服務(wù)器的單位計(jì)算資源成本；Gsf是縮放因子，用來(lái)將成本值調(diào)整到合適的取值范圍內(nèi)。

2.4.2 云卸載

當(dāng)αi=0 時(shí)，車(chē)輛i的任務(wù)將被卸載到云服務(wù)器中執(zhí)行。任務(wù)的傳輸時(shí)間計(jì)算式如式（9）所示：

其中：υfiber=1 μs/bit，是RSU 到云服務(wù)器的單位數(shù)據(jù)傳輸時(shí)延是返回的執(zhí)行結(jié)果數(shù)據(jù)量，一般遠(yuǎn)小于輸入的數(shù)據(jù)量，所以往往忽略其占用的傳輸時(shí)間。

任務(wù)的執(zhí)行時(shí)間計(jì)算式如式（10）所示：

其中：Cc是MCC 服務(wù)器的單位計(jì)算資源成本。

2.5 效用函數(shù)

基于以上定義，可以得到一個(gè)用于衡量卸載決策和資源分配方案優(yōu)劣的效用函數(shù)：

式（14）表示所有任務(wù)的平均效用，并且將任務(wù)的優(yōu)先級(jí)作為系數(shù)進(jìn)一步加強(qiáng)任務(wù)優(yōu)先級(jí)的重要性。其 中，X是問(wèn)題的解，當(dāng)αi∈{1，2，…，m}時(shí)，ui=，當(dāng)αi=0 時(shí)，ui=。因此，在求解卸載策略和資源分配方案時(shí)，優(yōu)化目標(biāo)就是最大化上述由時(shí)延和成本構(gòu)成的效用函數(shù)。

3 邊云協(xié)作任務(wù)卸載機(jī)制

車(chē)輛移動(dòng)性、計(jì)算資源、信道狀態(tài)的時(shí)變性等因素導(dǎo)致車(chē)聯(lián)網(wǎng)環(huán)境的高度不確定，此時(shí)將任務(wù)卸載決策問(wèn)題建模為MDP 過(guò)程，這是一種高效的解決方案。盡管在理論上可以采用動(dòng)態(tài)規(guī)劃或者啟發(fā)式算法求解MDP，但其超高的計(jì)算復(fù)雜度無(wú)法滿足車(chē)載應(yīng)用對(duì)實(shí)時(shí)性的要求。此外，MDP 的狀態(tài)轉(zhuǎn)移概率矩陣也很難獲取，在這種情況下，不基于模型的強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）算法可以用來(lái)獲取最優(yōu)策略。RL 算法不需要任何先驗(yàn)知識(shí)，通過(guò)不斷與環(huán)境交互學(xué)習(xí)，最終獲得的決策模型可以實(shí)現(xiàn)長(zhǎng)期效用最大化。近年來(lái)，深度強(qiáng)化學(xué)習(xí)算法又利用神經(jīng)網(wǎng)絡(luò)強(qiáng)大的近似能力解決了RL 算法狀態(tài)空間有限的問(wèn)題。

因此，本節(jié)首先將效用優(yōu)化問(wèn)題轉(zhuǎn)化為馬爾可夫決策過(guò)程，并采用深度強(qiáng)化學(xué)習(xí)方法求解最優(yōu)策略。然后，闡述在任務(wù)卸載策略已知情況下的基于優(yōu)先級(jí)的資源分配方案。最后，在卸載策略和資源分配方案已知的情況下，以最小化任務(wù)處理時(shí)間和保證傳輸可靠性為目標(biāo)，給出任務(wù)最佳卸載比例的計(jì)算方法。

3.1 基于DDQN 的任務(wù)卸載決策機(jī)制

DDQN［24］是一種基于價(jià)值的深度強(qiáng)化學(xué)習(xí)算法，適用于車(chē)輛任務(wù)卸載這種具有大規(guī)模離散動(dòng)作空間的場(chǎng)景。DDQN 的核心思想是使用深度神經(jīng)網(wǎng)絡(luò)近似代替動(dòng)作價(jià)值（以下簡(jiǎn)稱(chēng)“Q值”）函數(shù)，將環(huán)境狀態(tài)作為輸入，輸出是每個(gè)動(dòng)作對(duì)應(yīng)的Q值，其中最大Q值對(duì)應(yīng)的動(dòng)作將成為當(dāng)前最優(yōu)策略，環(huán)境也會(huì)反饋一個(gè)獎(jiǎng)勵(lì)值來(lái)評(píng)價(jià)動(dòng)作的好壞，同時(shí)也用來(lái)優(yōu)化神經(jīng)網(wǎng)絡(luò)的參數(shù)，然后環(huán)境將進(jìn)入下一個(gè)狀態(tài)，不斷循環(huán)上述過(guò)程直到收斂。

本節(jié)首先闡述MDP 的3 大要素，即狀態(tài)空間、動(dòng)作空間和獎(jiǎng)勵(lì)函數(shù)，然后介紹動(dòng)作價(jià)值函數(shù)以及最優(yōu)策略的定義，最后給出動(dòng)作價(jià)值網(wǎng)絡(luò)的更新過(guò)程。

3.1.1 狀態(tài)空間

具有全局信息瞬時(shí)收集能力的SDN 控制器恰好可以承擔(dān)DRL 中智能體這一角色，在每個(gè)時(shí)隙中，SDN 控制器監(jiān)控其通信范圍內(nèi)的車(chē)聯(lián)網(wǎng)環(huán)境，并且收集狀態(tài)信息，包括車(chē)輛位置、車(chē)輛任務(wù)、以及邊緣服務(wù)器和云服務(wù)器的資源可用信息。定義狀態(tài)空間為S，t時(shí)隙的狀態(tài)s(t)如下：

3.1.2 動(dòng)作空間

根據(jù)t時(shí)隙觀察到的狀態(tài)s(t)，智能體會(huì)輸出一個(gè)動(dòng)作作為當(dāng)前時(shí)隙采取的卸載策略。定義動(dòng)作空間為A，t時(shí)隙的動(dòng)作a(t)如式（16）所示：

其中：αi(t)，i∈{0，1，…，n}是車(chē)輛i在t時(shí)隙的卸載目標(biāo)服務(wù)器，其他兩類(lèi)動(dòng)作，即?j(t)，j∈{1，2，…，m}和?0(t)分別是邊緣服務(wù)器和云服務(wù)器在當(dāng)前時(shí)隙提供的資源比例，用來(lái)降低資源成本，盡量用更少的資源完成更多的任務(wù)。

3.1.3 獎(jiǎng)勵(lì)函數(shù)

在t時(shí)隙，智能體根據(jù)狀態(tài)s(t)給出動(dòng)作a(t)之后，環(huán)境立刻反饋一個(gè)獎(jiǎng)勵(lì)Rt，如式（17）所示。該獎(jiǎng)勵(lì)值可以用來(lái)評(píng)價(jià)動(dòng)作a(t)的好壞，并指導(dǎo)價(jià)值網(wǎng)絡(luò)參數(shù)的更新。

3.1.4 動(dòng)作價(jià)值函數(shù)

強(qiáng)化學(xué)習(xí)算法關(guān)注的是系統(tǒng)長(zhǎng)期效用最大化，即從當(dāng)前時(shí)隙到結(jié)束時(shí)隙的累計(jì)效用最大。t時(shí)隙的長(zhǎng)期累積折扣效用可以表示為Ut=Rt+γRt+1+γ2Rt+2+…+γ3Rt+n，其中，γ是折扣因子，未來(lái)時(shí)隙的獎(jiǎng)勵(lì)對(duì)當(dāng)前時(shí)隙的影響要打一個(gè)折扣。由于狀態(tài)轉(zhuǎn)移和動(dòng)作選擇的不確定性，在當(dāng)前時(shí)隙，很難得到準(zhǔn)確的Ut。在上述情況下，通過(guò)馬爾可夫性假設(shè)和求期望的方式可以消除隨機(jī)性，得到只與當(dāng)前時(shí)隙的狀態(tài)st和動(dòng)作at有關(guān)的動(dòng)作價(jià)值函數(shù)Qπ(st，at)，其計(jì)算式如式（18）所示：

3.1.5 最優(yōu)策略的定義

解決強(qiáng)化學(xué)習(xí)問(wèn)題意味著要尋找一個(gè)最優(yōu)策略π*，該策略使個(gè)體在與環(huán)境交互過(guò)程中獲得的效用始終大于其他策略。一般來(lái)說(shuō)，很難直接找到這個(gè)最優(yōu)策略，只能通過(guò)比較若干不同策略的優(yōu)劣來(lái)找到一個(gè)相對(duì)比較好的策略，也就是局部最優(yōu)解。比較策略的優(yōu)劣可以通過(guò)比較策略產(chǎn)生的動(dòng)作價(jià)值實(shí)現(xiàn)，最優(yōu)策略對(duì)應(yīng)的動(dòng)作價(jià)值優(yōu)于其他策略的動(dòng)作價(jià)值。所以，基于最優(yōu)動(dòng)作價(jià)值，可以給出最優(yōu)策略的定義如式（19）所示：

從式（19）可以看出，在當(dāng)前狀態(tài)下，最大Q值對(duì)應(yīng)的動(dòng)作就是最優(yōu)動(dòng)作。因此，可以通過(guò)比較當(dāng)前狀態(tài)下所有動(dòng)作的Q值來(lái)找到最優(yōu)動(dòng)作。

3.1.6 動(dòng)作價(jià)值網(wǎng)絡(luò)的更新

根據(jù)貝爾曼方程，可以得到t時(shí)隙的動(dòng)作價(jià)值和t+1 時(shí)隙的動(dòng)作價(jià)值的遞推關(guān)系，如式（20）所示，利用該公式，在理論上可以求出所有情況的Q值。

然而，對(duì)于狀態(tài)空間很大的復(fù)雜場(chǎng)景，使用動(dòng)態(tài)規(guī)劃或者Q-learning 這種傳統(tǒng)的方式計(jì)算Q值將產(chǎn)生巨大的時(shí)間和內(nèi)存成本，這明顯不適用于本文場(chǎng)景。深度強(qiáng)化學(xué)習(xí)解決上述問(wèn)題的方式是利用神經(jīng)網(wǎng)絡(luò)近似計(jì)算Q值，參數(shù)為ω的動(dòng)作價(jià)值網(wǎng)絡(luò)將狀態(tài)作為輸入，輸出不同動(dòng)作的Q值，神經(jīng)網(wǎng)絡(luò)的正向傳播所需計(jì)算量極小。所以，解決深度強(qiáng)化學(xué)習(xí)問(wèn)題的核心變成了動(dòng)作價(jià)值網(wǎng)絡(luò)參數(shù)的訓(xùn)練，不斷優(yōu)化網(wǎng)絡(luò)參數(shù)，使計(jì)算出的Q值盡可能接近真實(shí)值。

在深度強(qiáng)化學(xué)習(xí)算法中，同樣使用梯度下降法更新神經(jīng)網(wǎng)絡(luò)的參數(shù)，此時(shí)需要一個(gè)真實(shí)值與神經(jīng)網(wǎng)絡(luò)的估計(jì)值進(jìn)行比較，但真實(shí)值卻無(wú)法獲得。根據(jù)式（20）可以得到式（21）：

使用γQπ(st+1，at+1)近似代替γE[Qπ(st+1，at+1)]后，式（21）的等號(hào)左邊變成Qπ(st，at)-γQπ(st+1，at+1)，Qπ(st，at)和Qπ(st+1，at+1)都可以通過(guò)神經(jīng)網(wǎng)絡(luò)計(jì)算，而等號(hào)右邊是t時(shí)隙獲得的真實(shí)獎(jiǎng)勵(lì)，使Qπ(st，at)和Qπ(st+1，at+1)的差值盡量接近Rt是神經(jīng)網(wǎng)絡(luò)的優(yōu)化目標(biāo)。根據(jù)貪心策略，下一個(gè)狀態(tài)st+1是在狀態(tài)st下執(zhí)行最優(yōu)動(dòng)作at得到的，然后將st+1作為輸入，計(jì)算得到的Q值中，選取最大Q值用于參數(shù)更新。此時(shí)，可以得到均方差損失函數(shù)，如式（22）所示：

原始DQN 算法使用同一個(gè)神經(jīng)網(wǎng)絡(luò)計(jì)算Qπ(st，at)和Qπ(st+1，at+1)，導(dǎo)致相關(guān)性太強(qiáng)，不利于收斂。對(duì)此，Natural DQN 算法使用兩個(gè)結(jié)構(gòu)相同的網(wǎng)絡(luò)來(lái)分別計(jì)算Qπ(st，at)和Qπ(st+1，at+1)，并將計(jì)算當(dāng)前時(shí)隙Qπ(st，at)的網(wǎng)絡(luò)稱(chēng)作當(dāng)前Q網(wǎng)絡(luò)，將計(jì)算Qπ(st+1，at+1)的網(wǎng)絡(luò)成為目標(biāo)Q網(wǎng)絡(luò)，目標(biāo)Q網(wǎng)絡(luò)無(wú)需訓(xùn)練，只是定期從當(dāng)前Q網(wǎng)絡(luò)復(fù)制參數(shù)過(guò)來(lái)，以減少目標(biāo)Q值計(jì)算和神經(jīng)網(wǎng)絡(luò)參數(shù)更新的依賴(lài)關(guān)系。然而，使用貪心策略選擇最大的Qπ(st+1，at+1)這種方式會(huì)導(dǎo)致過(guò)度估計(jì)的問(wèn)題，使訓(xùn)練得到的模型有很大的偏差。對(duì)此，在Natural DQN 的基礎(chǔ)上，DDQN算法解耦了目標(biāo)Q值動(dòng)作的選擇和目標(biāo)Q值的計(jì)算，先利用當(dāng)前Q網(wǎng)絡(luò)選出下一個(gè)狀態(tài)下Q值最大的動(dòng)作a′=(st+1，at+1，ω)，然后從目標(biāo)Q網(wǎng)絡(luò)獲得動(dòng)作a′對(duì)應(yīng)的Q值，即(st+1，a′，ω′)，值得注意的是，此時(shí)的目標(biāo)Q值未必是最大值。以上是對(duì)算法思想的介紹，基于DDQN 的任務(wù)卸載決策算法具體描述見(jiàn)算法1。

算法1基于DDQN 的任務(wù)卸載決策算法

3.2 基于優(yōu)先級(jí)的資源分配方案

本文提出一個(gè)基于優(yōu)先級(jí)的資源分配方案，優(yōu)先級(jí)越高的任務(wù)可以分配到越多的計(jì)算資源，相比于平均分配的方式，可以提高高優(yōu)先級(jí)任務(wù)的完成率。通過(guò)上一節(jié)的策略模型可以得到當(dāng)前時(shí)隙的卸載策略，在此基礎(chǔ)上，本節(jié)首先根據(jù)優(yōu)先級(jí)計(jì)算任務(wù)的資源分配系數(shù)，然后為其分配相應(yīng)比例的計(jì)算資源。

3.2.1 邊緣服務(wù)器的資源分配

如果車(chē)輛i的卸載目標(biāo)服務(wù)器的編號(hào)為j，那么任務(wù)Ti的資源分配系數(shù)λi如式（23）所示：

其中：mecj代表卸載目標(biāo)為編號(hào)j的MEC 服務(wù)器的車(chē)輛集合。

任務(wù)Ti分配到的資源如式（24）所示：

3.2.2 云服務(wù)器的資源分配

如果車(chē)輛i的卸載目標(biāo)服務(wù)器為云服務(wù)器，那么任務(wù)Ti的資源分配系數(shù)λi如式（25）所示：

其中：mcc0代表卸載目標(biāo)云服務(wù)器的車(chē)輛集合。任務(wù)Ti分配到的資源如式（26）所示：

3.3 卸載比例計(jì)算

4 實(shí)驗(yàn)結(jié)果與分析

本文通過(guò)python 語(yǔ)言對(duì)本文算法進(jìn)行仿真并分析其性能。仿真場(chǎng)景是由1 個(gè)云服務(wù)器、3 個(gè)邊緣服務(wù)器和若干車(chē)輛用戶組成的云-邊-車(chē)輛3 層結(jié)構(gòu)。環(huán)境參數(shù)和神經(jīng)網(wǎng)絡(luò)的參數(shù)設(shè)置如表1 所示。

表1 參數(shù)設(shè)置Table 1 Simulation parameters

為驗(yàn)證本文算法的性能，選擇以下5 種算法進(jìn)行比較。

1）Natural DQN 算法。該算法是一種深度強(qiáng)化學(xué)習(xí)算法，在仿真實(shí)驗(yàn)中，除了目標(biāo)Q值的計(jì)算不同，其他均與本文算法保持一致。

2）模擬退火算法。與本文算法的區(qū)別是，該算法在每次迭代中會(huì)隨機(jī)選擇任務(wù)的卸載目標(biāo)服務(wù)器，并以所有任務(wù)的平均效用作為優(yōu)化目標(biāo)，所以只要迭代的次數(shù)足夠多，在理論上可以找到使平均效用最大的策略。

3）平均分配資源算法，在資源分配時(shí)，不考慮任務(wù)的優(yōu)先級(jí)。

4）全部卸載處理算法，任務(wù)全部卸載處理。

5）全部本地處理算法，任務(wù)全部留在本地處理。

圖2 是本文算法和Natural DQN 算法的收斂過(guò)程，為更清晰地展示2 個(gè)算法的差別，圖2（b）進(jìn)一步放大了前2 000 步的迭代過(guò)程?？梢钥闯鲈诘?00步以后，Natural DQN 算法的波動(dòng)更明顯，而且均方誤差大于本文算法，這恰好驗(yàn)證了Natural DQN 算法對(duì)于目標(biāo)動(dòng)作價(jià)值的過(guò)渡估計(jì)。此外，本文算法在迭代2 000 步左右就已經(jīng)完全收斂，而Natural DQN的曲線在迭代8 000 步左右才趨于一條穩(wěn)定的直線算法。

圖2 不同算法的損失值變化Fig.2 Loss value change of different algorithms

圖3 是不同算法產(chǎn)生的平均任務(wù)處理效用。將MEC 和MCC 服務(wù)器的數(shù)量分別固定為3 和1，針對(duì)10 種不同的車(chē)輛數(shù)進(jìn)行對(duì)比實(shí)驗(yàn)。由圖3 可知，隨著任務(wù)數(shù)量的增多，除了全部本地執(zhí)行算法以外的所有算法產(chǎn)生的平均效用都呈現(xiàn)下降的趨勢(shì)，這是因?yàn)榉峙浣o每個(gè)任務(wù)的計(jì)算資源逐漸減少，導(dǎo)致完成任務(wù)所需的時(shí)間增多。全部本地執(zhí)行算法的性能最差，而模擬退火算法獲得了效用最大的卸載決策，但是付出了很高的時(shí)間成本，相反，本文算法和Natural DQN 算法卻可以在極短的時(shí)間內(nèi)獲得近似最優(yōu)解。此外，相比于平均分配資源這種方式，本文算法在效用方面獲得了3 倍以上的提升，這說(shuō)明本文基于優(yōu)先級(jí)的資源分配方式讓資源得到了更好的利用。最后，相比于全部卸載執(zhí)行算法，本文算法采取部分卸載的方式顯然更加合理，效用至少提高了2 倍。

圖3 不同算法的平均任務(wù)處理效用Fig.3 Average task processing utility of different algorithms

圖4 是不同算法產(chǎn)生的平均任務(wù)處理時(shí)延?？梢钥闯?，除了全部本地執(zhí)行算法，隨著任務(wù)數(shù)增多，其他算法的平均時(shí)延都逐漸增多，這是因?yàn)槿蝿?wù)分配到的資源變少，而全部本地執(zhí)行算法主要與本地資源量有關(guān)，不受任務(wù)數(shù)量影響，所以變化較小。除了模擬退火算法，本文算法在時(shí)延性能方面要優(yōu)于其他算法，其中，全部卸載算法卸載的任務(wù)量最大，所以產(chǎn)生的時(shí)延大幅增長(zhǎng)。仔細(xì)觀察還可以發(fā)現(xiàn)，時(shí)延與效用的關(guān)系并不絕對(duì)，因?yàn)樗兴惴ǖ膬?yōu)化指標(biāo)都是效用，而效用由時(shí)延和成本兩部分構(gòu)成，所以效用大不代表時(shí)延小。

圖4 不同算法的平均任務(wù)處理時(shí)延Fig.4 Average tasks processing delay of different algorithms

圖5 和圖6 分別是任務(wù)和高優(yōu)先級(jí)任務(wù)的完成比例。首先，在資源總量不變的情況下，當(dāng)任務(wù)數(shù)量增加到一定程度時(shí)，任務(wù)的完成率將不可避免地下降，其中，全部卸載算法由于卸載的任務(wù)量大及浪費(fèi)了本地資源，所以任務(wù)完成率很低。而對(duì)于全部本地執(zhí)行算法，利用有限的本地資源，幾乎很難在規(guī)定時(shí)間內(nèi)完成任務(wù)，任務(wù)量大且時(shí)延敏感的高優(yōu)先級(jí)任務(wù)完成比例甚至均為0。其次，本文算法的任務(wù)和高優(yōu)先級(jí)任務(wù)完成比例都最接近模擬退火算法，在任務(wù)數(shù)適中的情況下，任務(wù)完成比例可以穩(wěn)定維持在100%。由于在卸載決策制定和資源分配時(shí)都將優(yōu)先級(jí)作為參考標(biāo)準(zhǔn)，因此相對(duì)于平均分配資源算法，本文算法能大幅提升高優(yōu)先級(jí)任務(wù)的完成比例。

圖5 不同算法的任務(wù)完成比例Fig.5 Success rate of tasks processing of different algorithms

圖6 不同算法的高優(yōu)先級(jí)任務(wù)完成比例Fig.6 Success rate of higher priority tasks processing of different algorithms

5 結(jié)束語(yǔ)

為緩解車(chē)載應(yīng)用日益豐富與車(chē)輛資源有限之間的矛盾，本文構(gòu)建一種基于SDN 的邊云協(xié)作車(chē)聯(lián)網(wǎng)計(jì)算卸載架構(gòu)，并將任務(wù)卸載問(wèn)題建模為馬爾可夫決策過(guò)程，把時(shí)延和計(jì)算資源成本構(gòu)成的效用作為優(yōu)化目標(biāo)，提出基于DDQN 的任務(wù)卸載機(jī)制和基于任務(wù)優(yōu)先級(jí)的資源分配方案。通過(guò)在卸載決策制定和資源分配過(guò)程中考慮任務(wù)優(yōu)先級(jí)因素，提高系統(tǒng)平均效用及降低任務(wù)處理時(shí)延。實(shí)驗(yàn)結(jié)果表明，本文提出的卸載比例計(jì)算方法在一定程度上提高了任務(wù)傳輸?shù)目煽啃?，?shí)現(xiàn)當(dāng)前策略的時(shí)延最小化。下一步將引入無(wú)線電干擾等復(fù)雜因素，構(gòu)建更加符合實(shí)際場(chǎng)景的通信模型。