杜 楚 ，黃澤鋒，李小翠

(1.中國(guó)電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081；2.河北省智能化信息感知與處理重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050081；3.中國(guó)地質(zhì)大學(xué)(北京)信息工程學(xué)院,北京 100083)

0 引言

近年來(lái)，物聯(lián)網(wǎng)設(shè)備的普及催生了許多新興物聯(lián)網(wǎng)應(yīng)用，如智能家居、智慧城市、實(shí)時(shí)制造和患者監(jiān)測(cè)等。這些物聯(lián)網(wǎng)應(yīng)用通常表現(xiàn)出嚴(yán)格的服務(wù)質(zhì)量(QoS)要求，如低延遲和低能耗等，對(duì)物聯(lián)網(wǎng)設(shè)備有限的資源與計(jì)算能力帶來(lái)了重大挑戰(zhàn)[1-3]。邊緣計(jì)算成為緩解新興物聯(lián)網(wǎng)應(yīng)用低延遲要求和設(shè)備資源受限之間沖突的首選平臺(tái)[4-6]。邊緣計(jì)算支持在靠近終端用戶的邊緣服務(wù)器上配置服務(wù)，用戶可以將復(fù)雜的計(jì)算任務(wù)卸載到附近的邊緣服務(wù)器，實(shí)現(xiàn)快速響應(yīng)和實(shí)時(shí)計(jì)算任務(wù)處理[1]。因此，在邊緣計(jì)算下，服務(wù)實(shí)時(shí)配置到距離終端用戶最近的邊緣服務(wù)器上的同時(shí)，滿足用戶請(qǐng)求約束的QoS是一個(gè)關(guān)鍵挑戰(zhàn)。此外，當(dāng)終端用戶請(qǐng)求的服務(wù)未配置在請(qǐng)求的邊緣服務(wù)器上時(shí)，為保證QoS，考慮將用戶任務(wù)通過(guò)當(dāng)前請(qǐng)求的邊緣服務(wù)器遷移到臨近的邊緣服務(wù)器運(yùn)行，或?qū)⑴R近邊緣服務(wù)器上配置的服務(wù)動(dòng)態(tài)遷移到當(dāng)前邊緣服務(wù)器。因此，利用邊緣服務(wù)器之間協(xié)作，動(dòng)態(tài)服務(wù)配置與遷移機(jī)制研究對(duì)于邊緣計(jì)算下減少用戶請(qǐng)求服務(wù)訪問(wèn)延遲和降低設(shè)備能耗開銷至關(guān)重要。

邊緣計(jì)算下的任務(wù)動(dòng)態(tài)配置和遷移受到了廣泛關(guān)注。許多研究者致力于設(shè)計(jì)有效算法來(lái)提升QoS和降低成本。任務(wù)分配決策在服務(wù)配置中起著關(guān)鍵作用，Chen等[7]通過(guò)對(duì)各參數(shù)的聯(lián)合優(yōu)化，設(shè)計(jì)了一種能量最優(yōu)動(dòng)態(tài)計(jì)算卸載方案。文獻(xiàn)[8]為了最小化任務(wù)的卸載時(shí)間，設(shè)計(jì)了一種基于延遲依賴的優(yōu)先級(jí)感知任務(wù)卸載策略，根據(jù)任務(wù)的截止時(shí)間為每個(gè)任務(wù)分配優(yōu)先級(jí)。文獻(xiàn)[9-12]集中于部分卸載策略或協(xié)同優(yōu)化卸載決策和資源配置。大多數(shù)相關(guān)研究只關(guān)注任務(wù)卸載以解決延遲和能耗限制，而忽略了用戶的服務(wù)請(qǐng)求在實(shí)際情況下是高度動(dòng)態(tài)的。邊緣節(jié)點(diǎn)可能沒(méi)有配置任務(wù)所需的服務(wù)，這會(huì)限制任務(wù)卸載策略?？紤]服務(wù)請(qǐng)求的多樣性與邊緣節(jié)點(diǎn)有限的服務(wù)數(shù)量之間的沖突，文獻(xiàn)[13]提出將服務(wù)從云遷移到網(wǎng)絡(luò)邊緣。但是，云服務(wù)器和邊緣節(jié)點(diǎn)之間通信的時(shí)間和能源成本很高。因此，頻繁地從云到邊緣節(jié)點(diǎn)的服務(wù)遷移會(huì)導(dǎo)致延遲和能耗增加。文獻(xiàn)[14]提出在邊緣節(jié)點(diǎn)之間遷移服務(wù)，使可用服務(wù)更接近用戶設(shè)備，減少服務(wù)遷移的額外成本。文獻(xiàn)[15]解決了何時(shí)何地遷移服務(wù)以在QoS和遷移成本之間實(shí)現(xiàn)最佳權(quán)衡的挑戰(zhàn)。文獻(xiàn)[16-18]側(cè)重在動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境中實(shí)現(xiàn)低延遲服務(wù)遷移和無(wú)縫計(jì)算。任務(wù)卸載和服務(wù)遷移問(wèn)題可以建模為馬爾可夫決策過(guò)程(MDP)，利用強(qiáng)化學(xué)習(xí)算法獲得MDP的最優(yōu)策略。

邊緣節(jié)點(diǎn)之間的協(xié)作(例如任務(wù)卸載和遷移)降低了設(shè)備的能源消耗，提高了QoS約束。以上研究大多數(shù)分別考慮這2種協(xié)作策略，并沒(méi)有將服務(wù)配置和遷移有效地結(jié)合起來(lái)。因此，本文提出了一種高效的計(jì)算任務(wù)卸載策略，將任務(wù)卸載與服務(wù)遷移策略動(dòng)態(tài)結(jié)合，以最小化任務(wù)處理成本。本文的主要貢獻(xiàn)包括以下3點(diǎn)：

① 基于現(xiàn)實(shí)的任務(wù)請(qǐng)求模式與任務(wù)協(xié)作處理方式，分析了若干種任務(wù)請(qǐng)求模式的特征，歸納出多種請(qǐng)求情況，并制定了相應(yīng)的遷移和卸載策略。

② 提出一種新的邊緣協(xié)作策略，在考慮傳統(tǒng)的縱向遷移和橫向卸載協(xié)同方式的同時(shí)引入服務(wù)橫向遷移的方式，并行執(zhí)行任務(wù)卸載和服務(wù)遷移過(guò)程，減小了數(shù)據(jù)傳輸延遲，達(dá)到網(wǎng)絡(luò)整體能量消耗及響應(yīng)延遲的最小化。

③ 通過(guò)對(duì)多種請(qǐng)求場(chǎng)景的分析，將選擇任務(wù)執(zhí)行地點(diǎn)問(wèn)題建模成多維馬爾可夫決策過(guò)程，利用深度強(qiáng)化學(xué)習(xí)算法并合理設(shè)置該算法的狀態(tài)空間、動(dòng)作空間和獎(jiǎng)懲函數(shù)等屬性，實(shí)現(xiàn)該問(wèn)題快速?zèng)Q策。

為了評(píng)估該策略的可行性及高效性，本文對(duì)所構(gòu)建的邊緣計(jì)算網(wǎng)絡(luò)下的任務(wù)協(xié)同處理問(wèn)題進(jìn)行了模擬仿真實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文提出的策略可以有效地降低網(wǎng)絡(luò)整體延遲以及能量損耗。

1 相關(guān)工作

1.1 邊緣計(jì)算下的任務(wù)卸載

任務(wù)服務(wù)配置決策在邊緣計(jì)算中起著關(guān)鍵作用。通過(guò)對(duì)各參數(shù)的聯(lián)合優(yōu)化，文獻(xiàn)[7]提出了一種能量最優(yōu)動(dòng)態(tài)計(jì)算卸載方案?？紤]各個(gè)邊緣節(jié)點(diǎn)的能量效率和優(yōu)先級(jí)，提出了公平任務(wù)卸載方案[9]。文獻(xiàn)[10]引入了一種新的動(dòng)態(tài)邊緣計(jì)算模型，并設(shè)計(jì)了一種在線原對(duì)偶算法來(lái)卸載到達(dá)的任務(wù)。為了提高卸載算法的泛化能力，文獻(xiàn)[11]提出了一種基于元強(qiáng)化學(xué)習(xí)的任務(wù)卸載方法?？紤]邊緣節(jié)點(diǎn)資源受限，文獻(xiàn)[12]提出了一種資源感知自適應(yīng)任務(wù)卸載框架，靈活選擇最優(yōu)卸載策略。

但是，這些算法沒(méi)有考慮到用戶請(qǐng)求的服務(wù)可能沒(méi)有在執(zhí)行節(jié)點(diǎn)上配置。這項(xiàng)工作引入了一種動(dòng)態(tài)計(jì)算卸載策略，將具有豐富計(jì)算資源的中間節(jié)點(diǎn)作為任務(wù)的執(zhí)行節(jié)點(diǎn)。如果執(zhí)行節(jié)點(diǎn)沒(méi)有配置相應(yīng)的服務(wù)，服務(wù)遷移過(guò)程并行進(jìn)行。本文采用深度強(qiáng)化學(xué)習(xí)算法快速?zèng)Q策最優(yōu)中間節(jié)點(diǎn)。

1.2 邊緣計(jì)算下服務(wù)遷移

邊緣節(jié)點(diǎn)有限的服務(wù)和用戶時(shí)延敏感約束給邊緣計(jì)算下開展服務(wù)配置與遷移帶來(lái)了更多的挑戰(zhàn)。為了實(shí)現(xiàn)低延遲和無(wú)縫計(jì)算，邊緣節(jié)點(diǎn)間的服務(wù)遷移備受關(guān)注。文獻(xiàn)[16]提出了一種基于用戶活動(dòng)熱點(diǎn)的服務(wù)遷移策略，根據(jù)用戶活動(dòng)熱點(diǎn)圖，提前在邊緣節(jié)點(diǎn)上部署服務(wù)。文獻(xiàn)[17]開發(fā)了一種基于松弛和舍入的最優(yōu)迭代求解方法來(lái)最小化遷移成本。文獻(xiàn)[14]將服務(wù)遷移問(wèn)題表述為非線性 0-1規(guī)劃問(wèn)題，并設(shè)計(jì)了基于粒子群的服務(wù)遷移方案。然而，由于傳統(tǒng)啟發(fā)式算法時(shí)間復(fù)雜度高，難以實(shí)現(xiàn)算法的快速收斂。強(qiáng)化學(xué)習(xí)正在成為優(yōu)化服務(wù)遷移策略的一種有前途的方法，文獻(xiàn)[18-20]提出了服務(wù)遷移的決策過(guò)程建模為一維馬爾可夫決策，以服務(wù)遷移延遲為目標(biāo)函數(shù)，提出利用強(qiáng)化學(xué)習(xí)優(yōu)化服務(wù)遷移決策，實(shí)現(xiàn)算法快速收斂，有效地減少遷移過(guò)程中的額外延遲和能量消耗。

綜上所述，這些方法在特定的場(chǎng)景下節(jié)能效果十分顯著，但是并不適用于本文的場(chǎng)景。因此，本文提出了一種高效的計(jì)算任務(wù)卸載策略，采用深度強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)快速?zèng)Q策，并將服務(wù)遷移與任務(wù)動(dòng)態(tài)卸載相結(jié)合。

2 網(wǎng)絡(luò)和性能模型

本節(jié)介紹了系統(tǒng)模型，包括網(wǎng)絡(luò)模型、能耗模型和時(shí)延模型3個(gè)部分。

2.1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)基本要素主要包括邊緣節(jié)點(diǎn)的描述、服務(wù)和任務(wù)描述以及時(shí)間片的劃分，具體的定義如下：

① 該研究場(chǎng)景中，網(wǎng)絡(luò)包括N個(gè)邊緣節(jié)點(diǎn)，將這些邊緣節(jié)點(diǎn)表示為集合F={F1，F(xiàn)2，…，F(xiàn)i，…，F(xiàn)N}。對(duì)于這些邊緣節(jié)點(diǎn)，通過(guò)以下幾個(gè)屬性來(lái)描述：邊緣節(jié)點(diǎn)的唯一標(biāo)識(shí)Fi.id、邊緣節(jié)點(diǎn)的地理位置Fi.Loc=(Lx,Ly)、邊緣節(jié)點(diǎn)當(dāng)前托管的服務(wù)列表Fi.HostLst、邊緣節(jié)點(diǎn)當(dāng)前正在處理的任務(wù)列表Fi.PT以及處理器頻率Fi.Fre。其中，i∈[1,N],Lx為邊緣節(jié)點(diǎn)地理位置的經(jīng)度，Ly為邊緣節(jié)點(diǎn)地理位置的緯度。不失一般性的前提下，本文考慮所有邊緣節(jié)點(diǎn)的資源相同，資源包括CPU處理能力、帶寬、內(nèi)存和存儲(chǔ)。

② 本文網(wǎng)絡(luò)中包括了M種類型的服務(wù)，將這些服務(wù)類型標(biāo)記為集合S={S1，S2，…，Si，…，SM}，并通過(guò)以下幾個(gè)屬性來(lái)描述：服務(wù)的唯一標(biāo)識(shí)Si.id，服務(wù)的大小Si.Bytes和服務(wù)重配置所需的時(shí)間Si.RCT，其中，i∈[1,N]。服務(wù)重配置所需的時(shí)間與服務(wù)本身所占用的大小無(wú)直接關(guān)系。

③ 將時(shí)間段T均勻地劃分為相等的時(shí)間片，將其標(biāo)記為T={T1，T2，…，Ti，…，Tt}。

④ 每個(gè)時(shí)間片下，假定用戶會(huì)發(fā)出K個(gè)任務(wù)請(qǐng)求，將其標(biāo)記為C={C1，C2，…，Ci，…，CK}。對(duì)于這些任務(wù)請(qǐng)求，通過(guò)以下幾個(gè)屬性來(lái)描述：任務(wù)請(qǐng)求的地理位置Ci.Loc=(Lx,Ly)，任務(wù)請(qǐng)求的類型Ci.Sj，任務(wù)請(qǐng)求的數(shù)據(jù)量大小Ci.Bytes以及任務(wù)處理所需的CPU時(shí)鐘周期Ci.Cir。其中，i∈[1,N]，j∈[1,M]，Lx為發(fā)出請(qǐng)求的用戶的經(jīng)度，Ly為發(fā)出請(qǐng)求的用戶的緯度。

2.2 能量模型

對(duì)于每個(gè)任務(wù)請(qǐng)求，其所需的總能耗為：

Etotal=Ecomp+Etti+Eftji，

(1)

式中，Ecomp為該任務(wù)的計(jì)算處理能耗；Etti為任務(wù)卸載到邊緣節(jié)點(diǎn)Fi的能耗；Eftji為服務(wù)從邊緣節(jié)點(diǎn)Fj遷移到邊緣節(jié)點(diǎn)Fi的能耗,i∈[1,N]，j∈[1,M]。

通信能耗模型的參數(shù)及其相關(guān)參數(shù)如表1所示。Etti和Eftji都是通信時(shí)將數(shù)據(jù)包從i點(diǎn)發(fā)送到j(luò)點(diǎn)產(chǎn)生的能耗，根據(jù)FORM模型，對(duì)于kbyte從節(jié)點(diǎn)發(fā)送到距離為d的節(jié)點(diǎn)的過(guò)程,，可以表示為：

Ecmm,ij(k,d)=ETx(k,d)+ERx(k)，

(2)

ETx(k,d)=Eelec×k+εamp×k×dn，

(3)

ERx(k)=Eelec×k，

(4)

式中，ETx(k,d)為將數(shù)據(jù)大小為k的數(shù)據(jù)轉(zhuǎn)發(fā)到距離為d的節(jié)點(diǎn)所消耗的能量；ERx(k)為接收kbyte數(shù)據(jù)所消耗的能量。傳播衰減指數(shù)n的值受環(huán)境影響較大。若設(shè)備之間傳輸數(shù)據(jù)時(shí)沒(méi)有建筑物遮擋，可將n的值設(shè)置為2，否則根據(jù)具體的環(huán)境可設(shè)置為3，4或5。Eelec和εamp分別表示單位能耗常數(shù)和發(fā)射放大器單位能耗常數(shù)。

表1 一階無(wú)線電模型參數(shù)

2.3 時(shí)延模型

對(duì)于每個(gè)任務(wù)請(qǐng)求，其所需的總延遲為：

Dtotal=Dcomp+max(Dtti,ArgMin{Dfttji}+Dr)+Dw,

(5)

式中，Dcomp為該任務(wù)的計(jì)算處理時(shí)間；Dtti為任務(wù)轉(zhuǎn)發(fā)卸載到邊緣節(jié)點(diǎn)Fi的時(shí)間；Dftji為服務(wù)從邊緣結(jié)點(diǎn)Fj遷移到邊緣節(jié)點(diǎn)Fi的時(shí)間；Dr為服務(wù)的重配置時(shí)間；Dw為任務(wù)請(qǐng)求處理的等待時(shí)間，i∈[1,N]，j∈[1,M]。Dttti和Dfttji都是通信時(shí)將數(shù)據(jù)包從i點(diǎn)發(fā)送到j(luò)點(diǎn)產(chǎn)生的時(shí)延，本文將無(wú)線傳輸時(shí)的延遲定義為：

delay=knetlgdij+bnet,

(6)

式中，dij為i點(diǎn)與j點(diǎn)的距離；knet和bnet定義如下：

knet=44.9-6.55lg(hb)，

(7)

bnet=46.3+33.9lg(f)-13.82lg(hb)-ahm+cm，

(8)

式中，f為信號(hào)頻率，單位MHz；hb為節(jié)點(diǎn)的天線高度；cm在一般情況下設(shè)置為3 dB;ahm定義如下：

ahm=3.20(lg(11.75hr))2-4.97，

(9)

式中，hr為用戶設(shè)備的高度。單個(gè)任務(wù)的計(jì)算時(shí)延Dcomp定義如下：

(10)

式中，C.Cir為任務(wù)處理所需的CPU時(shí)鐘周期；F.Fre為邊緣節(jié)點(diǎn)的處理器頻率。

2.4 目標(biāo)函數(shù)定義

整個(gè)網(wǎng)絡(luò)的能耗和延遲成本定義為所有任務(wù)的能量消耗之和以及所有任務(wù)的時(shí)延之和的加權(quán)和，目標(biāo)函數(shù)定義如下：

(11)

式中，Ditotal為所有任務(wù)請(qǐng)求完成所需的時(shí)延總和；Eitotal為所有任務(wù)請(qǐng)求完成所需的能量總和；ω1和ω2分別是控制權(quán)重的參數(shù)。

3 基于DQN服務(wù)配置與遷移

在強(qiáng)化學(xué)習(xí)算法中，對(duì)于每個(gè)時(shí)間片Tτ，產(chǎn)生系統(tǒng)狀態(tài)Sτ，并計(jì)算上一時(shí)刻的獎(jiǎng)勵(lì)Rτ-1。根據(jù)預(yù)先定義的策略選擇動(dòng)作Aτ。執(zhí)行該操作后，系統(tǒng)將在下一個(gè)時(shí)間片中轉(zhuǎn)換到新狀態(tài)Sτ+1。同樣，再次計(jì)算獎(jiǎng)勵(lì)Rτ并根據(jù)狀態(tài)Sτ+1選擇新動(dòng)作Aτ+1。

3.1 服務(wù)配置狀態(tài)空間

系統(tǒng)狀態(tài)基于延遲、能耗、邊緣節(jié)點(diǎn)托管的服務(wù)類型、邊緣節(jié)點(diǎn)的運(yùn)行狀態(tài)以及當(dāng)前時(shí)間片的所有請(qǐng)求信息。系統(tǒng)總延遲和總能耗如下：

(12)

即，Xi,j(t)為t時(shí)刻，請(qǐng)求i在邊緣節(jié)點(diǎn)Fj上執(zhí)行的總延遲Dtotal。

(13)

即，Yi,j(t)為t時(shí)刻，請(qǐng)求i在邊緣節(jié)點(diǎn)Fj上執(zhí)行的總能耗Etotal。

綜上所述，系統(tǒng)在t時(shí)刻的狀態(tài)可以表示為：

St={X(t),Y(t),F.HostLst,F.rt,C.Loc,Ci.S}∈S，

式中，S為系統(tǒng)的狀態(tài)空間。

3.2 服務(wù)遷移動(dòng)作空間

動(dòng)作空間被定義為等待處理的任務(wù)請(qǐng)求的候選執(zhí)行地點(diǎn)集，即所有的邊緣節(jié)點(diǎn)集合以及云節(jié)點(diǎn)，系統(tǒng)Tτ時(shí)刻的動(dòng)作可以表示為一維向量：

At= {aF1,aF2,…,aFN,ac}∈A，

式中，A為所有可執(zhí)行的動(dòng)作，每一個(gè)元素值代表了該請(qǐng)求是否在此處執(zhí)行，其值為1時(shí)代表在此處執(zhí)行，其值為0時(shí)代表不在此處執(zhí)行；Fi為邊緣節(jié)點(diǎn)；c為云節(jié)點(diǎn)。

3.3 服務(wù)配置與遷移獎(jiǎng)懲函數(shù)

本文的目標(biāo)是最小化延遲和能耗，因此，系統(tǒng)Tτ時(shí)刻的獎(jiǎng)勵(lì)定義為：

Rt=M1-(Dtotal(t)+Etotal(t))，

(14)

式中，M1為常數(shù)值；Dtotal(t)，Etotal(t)分別表示時(shí)刻t產(chǎn)生的任務(wù)請(qǐng)求的處理延遲以及能量損耗。

3.4 服務(wù)配置與遷移算法設(shè)計(jì)

本文采用了DNN和 Q-Learning相結(jié)合的深度Q-Learning算法。在深度Q-Learning算法中，使用Q-Network存儲(chǔ)Q矩陣，該網(wǎng)絡(luò)由權(quán)重為θ的DNN組成，可以有效存儲(chǔ)Q值信息。算法1描述了深度Q-Learning算法。對(duì)于每次迭代，首先獲取初始狀態(tài)S0，對(duì)每個(gè)時(shí)間片τ，根據(jù)預(yù)先定義的策略選擇動(dòng)作Aτ，并獲取下一個(gè)狀態(tài)Sτ+1。通過(guò)式(14)計(jì)算獎(jiǎng)勵(lì)，更新Q-Network并最終輸出動(dòng)作Aτ。

算法 1:基于服務(wù)遷移和邊緣協(xié)作的DQN算法輸入:θ:Q-Network的權(quán)重D:經(jīng)驗(yàn)重放池輸出:Aτ:動(dòng)作算法流程:1:for episode = 1,M do2: 獲取初始狀態(tài)S03: 初始化D3: for τ= 1,k do4: 調(diào)用算法2選擇動(dòng)作Aτ 5: 獲取狀態(tài)Sτ+16: 通過(guò)式(14)計(jì)算Rτ7: 調(diào)用算法3,根據(jù)Sτ,Sτ+1,Aτ,Rτ,D更新Q-Network8: 輸出動(dòng)作Aτ9: end for10:end for

3.4.1 動(dòng)作選擇

動(dòng)作選擇基于epsilon-greedy策略，該算法主要包括2個(gè)部分：探索者及開發(fā)者。預(yù)設(shè)一個(gè)ε閾值，每次選擇時(shí)產(chǎn)生一個(gè)隨機(jī)值Φ，當(dāng)Φ大于ε，則由開發(fā)者進(jìn)行動(dòng)作選擇；否則通過(guò)探索者進(jìn)行動(dòng)作選擇。具體動(dòng)作選擇過(guò)程如算法2所示。

算法 2:動(dòng)作選擇輸入: Sτ:當(dāng)前狀態(tài) BD:最佳動(dòng)作表輸出: Aτ:動(dòng)作算法流程: 1:產(chǎn)生隨機(jī)值Φ 2:ifΦ>εthen 3: 通過(guò)開發(fā)查找最佳動(dòng)作表BD,得到Aτ 4:else 5: 獲取可用計(jì)算資源列表L 6: 從資源列表中隨機(jī)選取邊緣節(jié)點(diǎn)Fi,得到對(duì)應(yīng)的Aτ 7:end if

3.4.2 Q-Network更新

在Q-Learning算法中，每個(gè)Q(Sτ-1，Aτ-1)都可以用如下規(guī)則更新：

Q(Sτ-1,Aτ-1)←(1-α)Q(Sτ-1,Aτ-1)+

α[Rτ-1+γ×maxAτQ(Sτ,Aτ)，

(15)

式中，α為學(xué)習(xí)率；γ為折扣率。在深度Q-Learning算法中，Q值信息一般都被抽象存儲(chǔ)在DNN中，由于系統(tǒng)狀態(tài)會(huì)在每個(gè)時(shí)刻Tτ不斷變化，因此DNN需要自適應(yīng)地進(jìn)行更新。目標(biāo)網(wǎng)絡(luò)提供穩(wěn)定的Q(Sτ，Aτ;θ’)，其y(τ)定義如下：

yτ=E{(1-α)Q(Sτ-1,Aτ-1;θ′)+

α(Rτ-1+γmaxQ(Sτ,Aτ;θ′))}，

(16)

式中，θ′為目標(biāo)網(wǎng)絡(luò)的權(quán)重，會(huì)間歇地重置回θ。

算法3描述了Q-Network更新過(guò)程。在該算法中，對(duì)于每個(gè)時(shí)刻，都將經(jīng)驗(yàn)四元組(Sτ，Aτ，Rτ，Sτ+1)存儲(chǔ)在經(jīng)驗(yàn)重放池D中，然后在D中抽取一組四元組用于更新網(wǎng)絡(luò)。對(duì)于每個(gè)四元組(Sτ-1(j)，Aτ-1(j)，Rτ-1(j)，Sτ(j))，計(jì)算Q(Sτ(j)，Aτ(j);θ’) 和y(τ)。

3.5 服務(wù)配置與遷移算法復(fù)雜度分析

在算法1中，算法時(shí)間復(fù)雜度主要包括動(dòng)作選擇算法和Q-Network更新算法。其中，對(duì)于行2及行5的狀態(tài)觀察和收集，其時(shí)間復(fù)雜度與需要收集的狀態(tài)的個(gè)數(shù)有關(guān)，即邊緣節(jié)點(diǎn)的個(gè)數(shù)N，對(duì)于K個(gè)任務(wù)請(qǐng)求，需要預(yù)計(jì)每個(gè)任務(wù)請(qǐng)求在各個(gè)邊緣節(jié)點(diǎn)上運(yùn)行的延遲和能耗，因此該步驟的時(shí)間復(fù)雜度為O(K×N)。對(duì)于行4，其時(shí)間復(fù)雜度取決于動(dòng)作選擇算法，開發(fā)過(guò)程只需要查找最佳動(dòng)作表，因此時(shí)間復(fù)雜度為O(1)，探索過(guò)程需要在可用資源列表中隨機(jī)選擇動(dòng)作，在3.3節(jié)已經(jīng)分析過(guò)該步驟的時(shí)間復(fù)雜度為O(N)。對(duì)于行6，其時(shí)間復(fù)雜度取決于獎(jiǎng)勵(lì)函數(shù)的計(jì)算，具體為O(N+M+K)。對(duì)于行7，其時(shí)間復(fù)雜度取決于Q-Network的更新，其時(shí)間復(fù)雜度取決于經(jīng)驗(yàn)重放池D的大小，大小取決于狀態(tài)空間S的大小和動(dòng)作空間的大小A，狀態(tài)空間大小為邊緣節(jié)點(diǎn)和云節(jié)點(diǎn)的個(gè)數(shù)之和N+1，動(dòng)作空間大小一般情況下為邊緣節(jié)點(diǎn)的個(gè)數(shù)N，故可得該算法時(shí)間復(fù)雜度為O(N2)。

4 結(jié)果評(píng)估

實(shí)驗(yàn)程序的運(yùn)行環(huán)境為：64位Windows10操作系統(tǒng)、16 GB內(nèi)存、處理器為Intel(R) Core(TM) i7-3770 CPU @ 3.40 GHz以及顯卡NVIDIA GeForce GTX 1070 Ti，通過(guò)Python程序?qū)崿F(xiàn)。為保證實(shí)驗(yàn)的科學(xué)性，所有實(shí)驗(yàn)均在同一環(huán)境下進(jìn)行。

4.1 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)中的參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

網(wǎng)絡(luò)區(qū)域?yàn)?00 m×500 m，該區(qū)域中均勻分布了50個(gè)邊緣節(jié)點(diǎn)。由于邊緣節(jié)點(diǎn)的資源限制，每個(gè)邊緣節(jié)點(diǎn)上最多可配置H=2種服務(wù)。通常一個(gè)物聯(lián)網(wǎng)部署之后，會(huì)根據(jù)節(jié)點(diǎn)的部署情況，選擇一個(gè)合適的通信范圍，為了保障該網(wǎng)絡(luò)的連通性，本文將邊緣節(jié)點(diǎn)的通信半徑設(shè)為150 m。邊緣節(jié)點(diǎn)的CPU頻率F.Fre=2 GHz。任務(wù)處理所需的CPU時(shí)鐘周期C.Cir∈[50,200]單位時(shí)間。信號(hào)頻率f=2.5 MHz，天線高度hb=35 m，用戶設(shè)備高度hr=1 m。無(wú)線信號(hào)傳輸?shù)膸抴i=500 MHz，無(wú)線傳輸?shù)哪芰肯某?shù)Eelec=50 nJ/bit，傳輸放大器的能耗常數(shù)εamp=0.1 nJ/(bit·m2)。CPU單循環(huán)的計(jì)算能耗為6×10-9Wh。成本函數(shù)的時(shí)延權(quán)重ω1=0.8，能耗權(quán)重ω2=0.2。

對(duì)于DQN中的網(wǎng)絡(luò)參數(shù)設(shè)置，學(xué)習(xí)率α=0.1，折扣率γ=0.9。對(duì)于DNN的結(jié)構(gòu)，本文使用4層全連接層的神經(jīng)網(wǎng)絡(luò)，該網(wǎng)絡(luò)的設(shè)置基于實(shí)驗(yàn)結(jié)果。本文對(duì)網(wǎng)絡(luò)的深度設(shè)置開展了大量實(shí)驗(yàn)，結(jié)果表明，4層的網(wǎng)絡(luò)在本文的問(wèn)題場(chǎng)景以及數(shù)據(jù)下有較好的表現(xiàn)。本文將狀態(tài)St和動(dòng)作At對(duì)表示為元組，并轉(zhuǎn)換成12 127×1的向量，將其作為DNN的輸入。在DNN的第1層和第2層之間添加了線性整流激活函數(shù)。DNN的輸出則是St和At元組的Q值對(duì)。需要注意的是，在該網(wǎng)絡(luò)中，所有的邊緣節(jié)點(diǎn)有著相同的DNN結(jié)構(gòu)和權(quán)重。

4.2 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)通過(guò)觀察系統(tǒng)長(zhǎng)期的平均延遲以及能耗來(lái)探索不同的系統(tǒng)參數(shù)設(shè)置對(duì)該策略的影響，這些系統(tǒng)參數(shù)包括任務(wù)請(qǐng)求的稀疏度以及服務(wù)類型的個(gè)數(shù)。

4.2.1 任務(wù)請(qǐng)求稀疏度

當(dāng)任務(wù)請(qǐng)求的稀疏度越高，平均每個(gè)時(shí)刻產(chǎn)生的任務(wù)請(qǐng)求會(huì)越多，則系統(tǒng)的平均響應(yīng)延遲以及能耗會(huì)越高。為了研究任務(wù)請(qǐng)求的稀疏度對(duì)平均延遲和能耗的影響，本文實(shí)驗(yàn)將任務(wù)請(qǐng)求的稀疏度prob設(shè)置為0.2，0.4,0.8。不同任務(wù)請(qǐng)求稀疏度設(shè)置下系統(tǒng)平均延遲如圖1所示。

圖1 不同任務(wù)請(qǐng)求稀疏度設(shè)置下系統(tǒng)平均延遲Fig.1 Average system delay under different task request sparsity settings

系統(tǒng)的平均響應(yīng)延遲與每個(gè)時(shí)刻的任務(wù)請(qǐng)求數(shù)量成正比，即與任務(wù)請(qǐng)求的稀疏度成正比，但從圖中可以觀察發(fā)現(xiàn)，稀疏度prob=0.4時(shí)，相比于稀疏度prob=0.2時(shí)的系統(tǒng)平均延遲沒(méi)有增加至一倍，其原因是prob=0.2時(shí)，在密集部署邊緣節(jié)點(diǎn)的網(wǎng)絡(luò)中，該網(wǎng)絡(luò)的計(jì)算負(fù)載是不飽和的，因此接收到任務(wù)請(qǐng)求時(shí)，邊緣節(jié)點(diǎn)往往可以立即處理該任務(wù)請(qǐng)求。而稀疏度prob=0.4時(shí)，該網(wǎng)絡(luò)的計(jì)算負(fù)載接近飽和，此時(shí)任務(wù)請(qǐng)求開始出現(xiàn)不能在最合適的邊緣節(jié)點(diǎn)上立即處理的情況，邊緣間協(xié)同處理情況開始變得頻繁。prob=0.8時(shí)，該網(wǎng)絡(luò)的計(jì)算負(fù)載過(guò)飽和，因此平均延遲相比于稀疏度prob=0.4時(shí)翻倍。

不同任務(wù)請(qǐng)求稀疏度設(shè)置下系統(tǒng)平均能耗如圖2所示。直覺(jué)上，系統(tǒng)的平均能耗與每個(gè)時(shí)刻的任務(wù)請(qǐng)求數(shù)量成正比，即與任務(wù)請(qǐng)求的稀疏度成正比，因?yàn)闊o(wú)論系統(tǒng)是否處于飽和的狀態(tài)，任務(wù)請(qǐng)求是否由于計(jì)算資源不足導(dǎo)致延遲增加都與能量損耗沒(méi)有直接關(guān)系。由圖2可以看出，當(dāng)系統(tǒng)計(jì)算負(fù)載接近飽和時(shí)，開始出現(xiàn)較頻繁的服務(wù)遷移和任務(wù)卸載，這些任務(wù)協(xié)同處理方式必然會(huì)導(dǎo)致傳輸能耗增加，因此，系統(tǒng)的平均能耗與任務(wù)請(qǐng)求的稀疏度成線性增加的關(guān)系。

圖2 不同任務(wù)請(qǐng)求稀疏度設(shè)置下系統(tǒng)平均能耗Fig.2 Average system energy consumption under different task request sparsity settings

4.2.2 服務(wù)類型的個(gè)數(shù)

不同服務(wù)類型數(shù)量設(shè)置下系統(tǒng)平均延遲如圖3所示。

圖3 不同服務(wù)類型數(shù)量設(shè)置下系統(tǒng)平均延遲Fig.3 Average system delay under different service types and quantity settings

服務(wù)類型數(shù)量snum=50時(shí)，系統(tǒng)的平均延遲與圖3中prob=0.4的系統(tǒng)平均延遲基本一致。當(dāng)snum=20時(shí)，所有服務(wù)類型都可以在邊緣網(wǎng)絡(luò)中找到多個(gè)配置了該服務(wù)類型的邊緣節(jié)點(diǎn)，因此服務(wù)遷移和任務(wù)卸載的地點(diǎn)有了更多候選，也更容易找到與數(shù)據(jù)產(chǎn)生地點(diǎn)鄰近的任務(wù)處理地點(diǎn)。因此，在邊緣網(wǎng)絡(luò)的計(jì)算負(fù)載還沒(méi)有完全飽和時(shí)，隨著服務(wù)類型snum值減小，系統(tǒng)的平均響應(yīng)延遲也越小。值得一提的是，當(dāng)snum=100時(shí)，系統(tǒng)平均延遲的波動(dòng)率顯著增加，分析這一現(xiàn)象可能的原因是邊緣層配置的服務(wù)出現(xiàn)了“脫靶”的情況，即任務(wù)請(qǐng)求的類型可能在邊緣層級(jí)上沒(méi)有找到配置了相應(yīng)服務(wù)的邊緣節(jié)點(diǎn)，配置了相應(yīng)服務(wù)的邊緣節(jié)點(diǎn)計(jì)算資源不足或者其物理距離不夠鄰近也可能造成該問(wèn)題。在這種情況下，邊緣節(jié)點(diǎn)為保障任務(wù)能有效處理，必須將任務(wù)卸載至云端或者將云端中的服務(wù)類型遷移至邊緣層，這種遠(yuǎn)距離的遷移或者卸載都會(huì)導(dǎo)致任務(wù)的響應(yīng)急劇增加，從而出現(xiàn)了圖中系統(tǒng)平均延遲波動(dòng)率增加的情況。因此，當(dāng)服務(wù)類型數(shù)量遠(yuǎn)多于邊緣層所能配置的服務(wù)數(shù)量時(shí)，為盡量減少脫靶的情況，如何對(duì)邊緣層的服務(wù)進(jìn)行合理的預(yù)配置，以及在遷移時(shí)如何保證邊緣層服務(wù)的豐富度是亟需研究的問(wèn)題。

不同服務(wù)類型數(shù)量設(shè)置下系統(tǒng)平均能耗如圖4所示。

圖4 不同服務(wù)類型數(shù)量設(shè)置下系統(tǒng)平均能耗Fig.4 Average system energy consumption under different service types and quantity settings

由圖4可以看出，相比于系統(tǒng)平均延遲，服務(wù)類型數(shù)量snum=100時(shí)，邊緣網(wǎng)絡(luò)的系統(tǒng)平均能耗波動(dòng)率更大。如圖4所示，波動(dòng)率增大的原因是發(fā)生了脫靶情況，這種情況導(dǎo)致邊緣節(jié)點(diǎn)不得不進(jìn)行遠(yuǎn)距離的遷移和卸載，但受益于第3節(jié)提出的圍繞計(jì)算資源的策略，邊緣節(jié)點(diǎn)在任務(wù)處理時(shí)是將可用的計(jì)算資源作為遷移和卸載的中繼點(diǎn)，并通過(guò)服務(wù)遷移和任務(wù)卸載使其存在時(shí)間、空間上重疊，因此該策略在發(fā)生遠(yuǎn)距離邊緣間協(xié)作時(shí)，可以有效降低任務(wù)處理的延遲，但是邊緣節(jié)點(diǎn)的數(shù)據(jù)量傳輸?shù)木嚯x沒(méi)有太多變化，因此相比于系統(tǒng)平均延遲，系統(tǒng)的平均能耗在脫靶時(shí)代價(jià)更大。

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

針對(duì)服務(wù)請(qǐng)求高度多樣且動(dòng)態(tài)變化的情況，如何對(duì)計(jì)算、存儲(chǔ)和帶寬等資源限制的邊緣節(jié)點(diǎn)實(shí)時(shí)服務(wù)配置與遷移，使網(wǎng)絡(luò)的總體能耗以及請(qǐng)求延遲盡量最小化，本文提出了一種基于服務(wù)遷移和邊緣協(xié)作的服務(wù)動(dòng)態(tài)重配置策略，降低任務(wù)請(qǐng)求處理過(guò)程中的時(shí)延以及能耗。根據(jù)所提策略設(shè)置深度強(qiáng)化學(xué)習(xí)算法的狀態(tài)空間、動(dòng)作空間和獎(jiǎng)勵(lì)函數(shù)，并利用深度強(qiáng)化學(xué)習(xí)進(jìn)行任務(wù)處理地點(diǎn)的決策，解決傳統(tǒng)啟發(fā)式算法由于復(fù)雜度過(guò)高無(wú)法在時(shí)延敏感的場(chǎng)景中使用的問(wèn)題。為了驗(yàn)證本文提出策略的可行性和高效性，探索了2種不同的網(wǎng)絡(luò)參數(shù)因子對(duì)該策略的影響，并且對(duì)比了2種傳統(tǒng)的任務(wù)協(xié)作處理方式，實(shí)驗(yàn)結(jié)果表明，本文所提策略可有效降低系統(tǒng)任務(wù)處理延遲，并且一定程度上可以減小系統(tǒng)能耗。