趙庶旭，元 琳，張占平

蘭州交通大學(xué) 電子與信息工程學(xué)院，蘭州 730070

隨著智能終端的飛速發(fā)展和逐漸普及，以及第五代移動(dòng)通信網(wǎng)絡(luò)（5G）的成功部署，網(wǎng)絡(luò)中的數(shù)據(jù)量正在成指數(shù)式增長[1-2]。網(wǎng)絡(luò)擁塞已成為無人駕駛、高清視頻直播、虛擬現(xiàn)實(shí)和增強(qiáng)現(xiàn)實(shí)等低能耗、低時(shí)延需求的任務(wù)所面臨的問題。而終端設(shè)備的計(jì)算能力有限，計(jì)算密集型任務(wù)會(huì)消耗大量能量，導(dǎo)致設(shè)備續(xù)航能力極速下降[3]。另一方面云計(jì)算平臺(tái)由于地理位置距終端設(shè)備存在一定距離，數(shù)據(jù)在物理鏈路上的傳輸時(shí)延較長，無法滿足低時(shí)延任務(wù)的實(shí)際要求[4]。因此，終端設(shè)備自身和云計(jì)算都無法高效地解決此類問題，移動(dòng)邊緣計(jì)算（mobile edge computing，MEC）應(yīng)運(yùn)而生[5-6]。MEC將計(jì)算資源和存儲(chǔ)資源部署在靠近終端設(shè)備或靠近數(shù)據(jù)源一側(cè)，來滿足任務(wù)在實(shí)時(shí)處理、數(shù)據(jù)安全和隱私保護(hù)方面的需求，極大地提高了用戶體驗(yàn)與服務(wù)質(zhì)量，同時(shí)緩解了網(wǎng)絡(luò)擁塞和帶寬壓力[7-8]。雖然MEC可以將計(jì)算卸載到邊緣端，但邊緣服務(wù)器在單位時(shí)間內(nèi)處理數(shù)據(jù)的能力是有限的。因此，需要設(shè)計(jì)一種高效的卸載方案，在統(tǒng)籌時(shí)延、能耗和成本的基礎(chǔ)上，決定任務(wù)是在本地執(zhí)行還是卸載到邊緣服務(wù)器上執(zhí)行，以及卸載到哪一臺(tái)邊緣服務(wù)器上，以提高整個(gè)MEC系統(tǒng)的資源利用率。

1 相關(guān)研究

近年來，國內(nèi)外各大互聯(lián)網(wǎng)、通信公司和眾多學(xué)者對(duì)MEC任務(wù)卸載開展了大量的研究工作[9-11]。文獻(xiàn)[12]利用馬爾可夫決策過程，提出了一種一維搜索算法求解功率受限的延遲最小化問題，是一種最優(yōu)搜索算法。但該方法需要預(yù)先獲得集群的信道質(zhì)量以及任務(wù)到達(dá)率等精確信息，在實(shí)際應(yīng)用中存在一定的局限性。文獻(xiàn)[13]提出了一種基于博弈論的卸載算法，將卸載博弈轉(zhuǎn)換為勢博弈，通過分布式博弈尋找納什平衡解。但該方法是建立在單邊緣服務(wù)器場景下的，沒有考慮實(shí)際應(yīng)用中多服務(wù)器計(jì)算資源受限情況。文獻(xiàn)[14]利用序列二次規(guī)劃法優(yōu)化后的結(jié)果訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)，以減少時(shí)延和能耗，但該方法也受限于單邊緣服務(wù)器場景下。文獻(xiàn)[15]提出了一種多平臺(tái)卸載資算法，利用K鄰近算法選擇云計(jì)算、邊緣計(jì)算或是本地計(jì)算，之后通過強(qiáng)化學(xué)習(xí)優(yōu)化資源分配，但其更側(cè)重于時(shí)延的優(yōu)化，忽略了設(shè)備能耗。另外，許多文獻(xiàn)利用啟發(fā)式算法解決邊緣計(jì)算卸載問題。文獻(xiàn)[16]提出了一種新型網(wǎng)絡(luò)設(shè)計(jì)方案，并使用Lyapunov隨機(jī)優(yōu)化工具解決了受延遲和可靠性約束的計(jì)算和發(fā)射功率最小化問題。文獻(xiàn)[17]使用首次適應(yīng)、在線優(yōu)先以及線性規(guī)劃等啟發(fā)式算法來優(yōu)化能耗和時(shí)延問題。利用啟發(fā)式算法解決大規(guī)模任務(wù)卸載問題時(shí)，由于問題維度過高，導(dǎo)致生成卸載決策的時(shí)間過長，因此無法滿足任務(wù)實(shí)時(shí)處理的需求。目前大多數(shù)邊緣計(jì)算卸載策略都是基于先驗(yàn)分布或歷史數(shù)據(jù)的，由于MEC中任務(wù)卸載通過無線傳輸，可用資源都是隨著信道質(zhì)量、任務(wù)到達(dá)率以及能量等因素動(dòng)態(tài)變化的，因此先驗(yàn)分布或歷史數(shù)據(jù)預(yù)測算法很難應(yīng)用于真實(shí)場景中?；谏鲜鲅芯康牟蛔?，定義卸載場景為多智能體多邊緣服務(wù)器場景。并同時(shí)考慮時(shí)延、能耗以及花費(fèi)因素，提出多智能體完全合作關(guān)系，在保證最大時(shí)延的前提下，降低能耗和花費(fèi)，提高邊緣服務(wù)器集群的資源利用率。引入深度強(qiáng)化學(xué)習(xí)，將強(qiáng)化學(xué)習(xí)的決策能力與深度學(xué)習(xí)的感知能力相結(jié)合，依靠強(qiáng)大的深度神經(jīng)網(wǎng)絡(luò)的表示學(xué)習(xí)來解決高緯度動(dòng)態(tài)任務(wù)卸載問題。首先，根據(jù)問題提出目標(biāo)函數(shù)，建立數(shù)學(xué)模型，包括任務(wù)建模、時(shí)延模型、能耗模型以及花費(fèi)模型。隨后，構(gòu)建馬爾可夫決策模型，利用DRQN對(duì)模型進(jìn)行求解。最后，進(jìn)行上述算法與本地執(zhí)行、隨機(jī)卸載、DQN等算法在時(shí)延、能耗、花費(fèi)方面的對(duì)比實(shí)驗(yàn)，仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了多智能體環(huán)境下基于DRQN卸載策略的有效性和可靠性。

2 系統(tǒng)建模

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

本文所建模型為多智能體多邊緣服務(wù)器模型，為邊緣計(jì)算任務(wù)卸載場景。如圖1所示，模型中包括N個(gè)邊緣服務(wù)器（edge server，ES）和M個(gè)智能體（smart device，SD），其中ES部署在基站上，SD通過無線鏈路傳輸數(shù)據(jù)。SD上的任務(wù)根據(jù)時(shí)延和能耗需求可以選擇在本地執(zhí)行，也可以選擇在ES上執(zhí)行；在ES計(jì)算資源允許的情況下可以選擇在一臺(tái)ES上執(zhí)行，也可以選擇在多臺(tái)ES上執(zhí)行，ES和SD是一種多對(duì)的關(guān)系。

圖1 網(wǎng)絡(luò)模型圖Fig.1 Network model diagram

2.2 任務(wù)建模

針對(duì)任務(wù)粒度[18]大小，從資源利用率和計(jì)算復(fù)雜度考慮，本文采用細(xì)粒度劃分任務(wù)。即智能體上的每個(gè)任務(wù)都可以被劃分為k個(gè)子任務(wù)，不同的子任務(wù)可以在不同的ES上執(zhí)行，也可以在本地執(zhí)行，從而縮減計(jì)算時(shí)延。任務(wù)集合定義為其中，表示第i個(gè)智能體上第j個(gè)子任務(wù)輸入的數(shù)據(jù)量，包括代碼和輸入?yún)?shù)；Cij表示執(zhí)行第ij個(gè)子任務(wù)所需的計(jì)算資源。這里的計(jì)算資源是指CPU，假設(shè)任務(wù)在本地智能體CPU上執(zhí)行和卸載到ES的CPU上執(zhí)行所需的計(jì)算資源是相同的；表示第ij個(gè)子任務(wù)計(jì)算完成后所得的結(jié)果數(shù)據(jù)；表示執(zhí)行第ij個(gè)子任務(wù)的最大時(shí)延約束。本文的卸載目標(biāo)是在滿足最大時(shí)延約束的條件下，盡可能地降低能耗和縮減費(fèi)用，并得到如下決策矩陣：

其中，x∈{0,1,2,…,p,…,N}，當(dāng)x=0時(shí)代表本地執(zhí)行，當(dāng)x=1時(shí)代表子任務(wù)將被卸載到序號(hào)為1的ES上執(zhí)行。同理，當(dāng)x=p時(shí)代表子任務(wù)將被卸載到序號(hào)為p的ES上執(zhí)行。

2.3 時(shí)延模型

假設(shè)本地處理任務(wù)的時(shí)延有且只由CPU產(chǎn)生，定義為：

其中，Cij為上文中提到的Rij所需的計(jì)算資源，這里具體為執(zhí)行Rij所需的CPU時(shí)鐘周期數(shù)，fSDi表示智能體i的CPU主頻。

若Rij需卸載到ES上執(zhí)行，則需要從發(fā)送時(shí)延、傳播時(shí)延和處理時(shí)延三方面對(duì)在ES上的時(shí)延進(jìn)行分析，定義為：

綜上所述，當(dāng)子任務(wù)之間存在依賴關(guān)系時(shí)，總時(shí)延為在本地執(zhí)行的子任務(wù)時(shí)延之和加在邊緣服務(wù)器上執(zhí)行的子任務(wù)時(shí)延之和：

當(dāng)子任務(wù)之間相互獨(dú)立時(shí)，總時(shí)延為第i個(gè)智能體上所有子任務(wù)時(shí)延的最大值：

2.4 能耗模型

這里的能耗是指智能體端的能耗，假設(shè)在本地執(zhí)行的任務(wù)所產(chǎn)生的能耗只與CPU有關(guān)，能耗模型定義如下：

2.5 費(fèi)用模型

費(fèi)用是指用戶使用運(yùn)營商提供的計(jì)算資源所支付給運(yùn)營商的費(fèi)用，所以費(fèi)用只在卸載后產(chǎn)生，不涉及本地執(zhí)行部分。本文使用基于計(jì)算資源剩余量的費(fèi)用模型，即計(jì)算資源剩余越多用戶支付的費(fèi)用越低，定義如下：

其中，uES表示邊緣服務(wù)器單位時(shí)間的價(jià)格，表示服務(wù)器p計(jì)算資源的使用率，表示服務(wù)器p計(jì)算資源的總量。

2.6 目標(biāo)函數(shù)

多智能體邊緣計(jì)算任務(wù)卸載問題是一個(gè)最優(yōu)化問題，本文的目標(biāo)是在保障時(shí)延的前提下，最小化能耗和費(fèi)用，在提升整個(gè)MEC系統(tǒng)的資源利用率的同時(shí)延長智能體的續(xù)航時(shí)間，目標(biāo)函數(shù)定義如下：

其中，α和β分別是能耗和費(fèi)用所占權(quán)重。

3 模型求解

為求解上述模型，本文提出一個(gè)部分可觀測的、多智能體完全合作的基于深度強(qiáng)化學(xué)習(xí)的邊緣計(jì)算任務(wù)卸載算法。在實(shí)際應(yīng)用環(huán)境中，由于底層物理鏈路的不穩(wěn)定性，邊緣服務(wù)器的狀態(tài)存在不能被完整觀測的可能性，稱其為“部分可觀測”。在多智能體強(qiáng)化學(xué)習(xí)中，每一個(gè)智能體都是自主、可交互的[19]，它們獨(dú)立地接收邊緣服務(wù)器的狀態(tài)信息，根據(jù)自身的策略函數(shù)決定當(dāng)前采取的卸載方案。同時(shí)，智能體之間相互通信，共同優(yōu)化目標(biāo)值，整體的卸載效果通過一個(gè)綜合的標(biāo)準(zhǔn)來評(píng)判。

強(qiáng)化學(xué)習(xí)是一種具備自學(xué)習(xí)能力、能做出最優(yōu)決策的算法[20]。它將問題抽象為智能體不斷在環(huán)境中試錯(cuò)的過程，在每一個(gè)時(shí)間步長中，智能體都會(huì)收到環(huán)境的狀態(tài)信息，并根據(jù)狀態(tài)信息作出響應(yīng)動(dòng)作。在下一個(gè)時(shí)間步長中，會(huì)根據(jù)環(huán)境的反饋給該智能體一個(gè)相應(yīng)的獎(jiǎng)勵(lì)值。若是期望的結(jié)果，則給一個(gè)正獎(jiǎng)勵(lì)，反之，則給一個(gè)負(fù)獎(jiǎng)勵(lì)[21-22]。目標(biāo)是最大化累積獎(jiǎng)勵(lì)[23]。但強(qiáng)化學(xué)習(xí)局限于低維度問題，在大規(guī)模狀態(tài)、動(dòng)作空間問題中，存在“維度災(zāi)難”。因此，引入深度學(xué)習(xí)，將強(qiáng)化學(xué)習(xí)的決策能力與深度學(xué)習(xí)的感知能力相結(jié)合，依靠強(qiáng)大的深度神經(jīng)網(wǎng)絡(luò)的表示學(xué)習(xí)來解決高維卸載問題。

圖2 模型結(jié)構(gòu)圖Fig.2 Model structurediagram

3.1構(gòu)建MDP

馬爾可夫決策過程（Markov decision process，MDP）一般包含狀態(tài)空間（state space，S）、動(dòng)作空間（action space，A）和獎(jiǎng)勵(lì)函數(shù)（reward function，R）。狀態(tài)空間S定義如公式（10）所示，包含資源剩余向量U，決策矩陣X，目標(biāo)函數(shù)G。

其中，U=[ ]u1,u2,…,up,…,uN，up表示序號(hào)為p的ES可使用的計(jì)算資源。

動(dòng)作空間A表示在每一個(gè)狀態(tài)下可以采取的所有動(dòng)作，定義如下：

其中，γ為第i個(gè)智能體上第j個(gè)子任務(wù)的卸載方案，γ∈{0,1,2,…,p,…,N}。

獎(jiǎng)勵(lì)函數(shù)R表示智能體執(zhí)行動(dòng)作、狀態(tài)轉(zhuǎn)移后，根據(jù)環(huán)境反饋獲得的獎(jiǎng)勵(lì)，定義如下：

其中，Gt為t時(shí)間段內(nèi)的目標(biāo)函數(shù)值，Gt+1為智能體在狀態(tài)St下作出響應(yīng)動(dòng)作At后t+1時(shí)間段內(nèi)的目標(biāo)函數(shù)值，GSD為任務(wù)在本地執(zhí)行時(shí)的目標(biāo)函數(shù)值。上述三個(gè)目標(biāo)函數(shù)值均根據(jù)公式（9）計(jì)算。注意，在本地執(zhí)行時(shí)，目標(biāo)函數(shù)不存在費(fèi)用部分（等于零），只有能耗部分和時(shí)延限制。當(dāng)Gt+1＞Gt時(shí)，即執(zhí)行動(dòng)作At后，G變大，即能耗和花費(fèi)增大，向不期望的方向發(fā)展，給予負(fù)獎(jiǎng)勵(lì)。反之，給予正獎(jiǎng)勵(lì)。

3.2 基于DRQN的任務(wù)卸載算法

深度遞歸Q網(wǎng)絡(luò)（DRQN）是對(duì)深度Q網(wǎng)絡(luò)（DQN）的一種改進(jìn)，利用遞歸神經(jīng)網(wǎng)絡(luò)（RNN）解決部分可觀測馬爾可夫決策過程（POMDP），提高DQN性能。在MEC應(yīng)用場景中，由于底層物理鏈路的不穩(wěn)定性和智能體感知的局限性，智能體很難接收到當(dāng)前時(shí)間段內(nèi)環(huán)境的精準(zhǔn)狀態(tài)信息，導(dǎo)致了POMDP問題。DRQN保留先前狀態(tài)信息，補(bǔ)充當(dāng)前狀態(tài)信息，解決缺失值問題。具體實(shí)現(xiàn)過程是用長短時(shí)記憶遞歸神經(jīng)網(wǎng)絡(luò)（LSTM RNN）代替DQN中卷積層后第一個(gè)全連接層，DRQN架構(gòu)如圖3所示。

圖3 DRQN架構(gòu)圖Fig.3 DRQN architecture diagram

將邊緣服務(wù)器ES返回的狀態(tài)信息作為輸入，卷積層對(duì)狀態(tài)信息進(jìn)行卷積運(yùn)算，得到特征圖，傳遞給LSTM層，LSTM根據(jù)先前記憶補(bǔ)充狀態(tài)信息，并更新記憶，最后經(jīng)過一個(gè)全連接層輸出Q值。其中，ht是上一時(shí)間步長網(wǎng)絡(luò)的返回值，即ht=LSTM(ht-1,at)，作為下一時(shí)間步長的輸入。

DRQN利用一個(gè)權(quán)重為θ的神經(jīng)網(wǎng)絡(luò)來逼近Q函數(shù)，即Q(ht,at;θ)≈Q*(st,at)。損失函數(shù)為目標(biāo)值與預(yù)測值的均方差，定義如下：

其中，r為獎(jiǎng)勵(lì)，γ為折扣因數(shù)，位于0～1之間，決定了即時(shí)獎(jiǎng)勵(lì)和未來獎(jiǎng)勵(lì)的重要性，接近0意味著即時(shí)獎(jiǎng)勵(lì)更重要，接近1意味著未來獎(jiǎng)勵(lì)更重要。神經(jīng)網(wǎng)絡(luò)通過梯度下降更新θ最小化損失。注意，目標(biāo)Q的參數(shù)是θ′，和預(yù)測Q的參數(shù)θ不同。DRQN采用一種稱為目標(biāo)網(wǎng)絡(luò)的獨(dú)立網(wǎng)絡(luò)來計(jì)算目標(biāo)值，目標(biāo)網(wǎng)絡(luò)與預(yù)測網(wǎng)絡(luò)結(jié)構(gòu)一致，但滯后于預(yù)測網(wǎng)絡(luò)若干時(shí)間步長，從預(yù)測網(wǎng)絡(luò)中復(fù)制權(quán)重θ更新自己的權(quán)重θ′。因此，目標(biāo)Q值與預(yù)測Q值具有一定的差異性，進(jìn)而用來計(jì)算損失。

智能體從狀態(tài)s執(zhí)行某一動(dòng)作a轉(zhuǎn)移到狀態(tài)s′，獲得獎(jiǎng)勵(lì)r,＜s,a,s′,r＞就是智能體的一條經(jīng)驗(yàn)，保存在經(jīng)驗(yàn)緩存中。DRQN從經(jīng)驗(yàn)緩存中隨機(jī)選擇一批訓(xùn)練樣本，減少經(jīng)驗(yàn)之間的相關(guān)性，提高算法的泛化性。具體算法如下：

4 仿真實(shí)驗(yàn)

本文使用Python語言在Anaconda平臺(tái)上通過比較DRQN與RQN、隨機(jī)卸載算法在大規(guī)模異構(gòu)集群中能耗、費(fèi)用以及時(shí)延等因素來評(píng)價(jià)DRQN算法在多智能體任務(wù)卸載應(yīng)用中的優(yōu)劣。仿真實(shí)驗(yàn)?zāi)M的集群包括50個(gè)邊緣服務(wù)器、數(shù)量不等的智能體，其中，邊緣服務(wù)器均勻分布在9個(gè)面積相同的區(qū)域中，智能體隨機(jī)分布在距基站150 m范圍內(nèi)。假設(shè)帶寬20 MHz，智能體的上傳速度為5.3 Mb/s，上傳功率為1 500 mW，空閑時(shí)的放電功率為200 mW，極限CPU主頻為2 GHz/s，邊緣服務(wù)器的極限CPU主頻為50 GHz/s。并且R的數(shù)據(jù)量（單位，Kbit）服從（200，2 000）的均勻分布，所需計(jì)算資源服從（1 200，3 000）的均勻分布。設(shè)深度強(qiáng)化學(xué)習(xí)參數(shù)，學(xué)習(xí)率α為0.001，經(jīng)驗(yàn)緩存大小為6 000，批學(xué)習(xí)大小BatchSize為32。γ分別取0.7、0.9，對(duì)比其在不同任務(wù)數(shù)量下能耗、花費(fèi)情況，如圖4所示，γ=0.9時(shí)在能耗和花費(fèi)上的表現(xiàn)均優(yōu)于γ=0.7時(shí)，意味著在邊緣計(jì)算場景中，未來獎(jiǎng)勵(lì)發(fā)揮著重要作用，故本文實(shí)驗(yàn)γ取0.9。

圖4 不同折扣因數(shù)DRQN能耗、花費(fèi)對(duì)比Fig.4 Comparison of energy consumption and cost ofDRQN with different discount factors

在滿足最大時(shí)延的前提下，本文將DRQN、DQN以及隨機(jī)卸載算法與本地執(zhí)行的能耗和費(fèi)用做差再除以本地執(zhí)行的能耗和費(fèi)用的比例（energy and cost reduction ratio，ECRR）作為算法的評(píng)價(jià)指標(biāo)之一。如表1所示，DQN和DRQN能耗和花費(fèi)縮減率都達(dá)到了50%以上，并且DRQN比DQN提高了近2個(gè)百分點(diǎn)。

表1 ECRR對(duì)比表Table 1 ECRR comparison table

不同任務(wù)數(shù)量下的各算法性能研究，任務(wù)數(shù)量取值范圍為[20，100]，以10為步長，畫出本地執(zhí)行、隨機(jī)卸載算法、DQN以及DRQN在能耗、花費(fèi)和時(shí)延上的對(duì)比圖。

由圖5可以看出，隨著任務(wù)數(shù)量的增加，各算法生成的卸載策略在能耗和花費(fèi)方面大致呈現(xiàn)上升趨勢，DRQN較隨機(jī)卸載算法、DQN在能耗和花費(fèi)上表現(xiàn)更佳。本地卸載所消耗的能量最多，這是由于智能體的計(jì)算能力遠(yuǎn)遠(yuǎn)小于邊緣服務(wù)器的計(jì)算能力造成的。另外，從圖5可以看出隨機(jī)卸載算法具有一定的波動(dòng)，這是因?yàn)樗惴ǖ碾S機(jī)性造成的。

圖5 各算法仿真結(jié)果對(duì)比圖Fig.5 Comparison of simulation results of various algorithms

5 結(jié)束語

本文提出了一種利用DRQN記憶先前環(huán)境狀態(tài)信息解決部分可觀測多智能體任務(wù)卸載問題。通過仿真實(shí)驗(yàn)表明DRQN相比其他算法在能耗和花費(fèi)上具有一定的優(yōu)勢。在本文的基礎(chǔ)上還可以進(jìn)一步研究雙向DQN、優(yōu)先經(jīng)驗(yàn)回放以及對(duì)抗網(wǎng)絡(luò)等在邊緣計(jì)算實(shí)際應(yīng)用中的作用。隨著許多AI新技術(shù)的不斷涌現(xiàn)，決策算法經(jīng)歷了從規(guī)則到淺層監(jiān)督學(xué)習(xí)，到深度學(xué)習(xí)，再到深度強(qiáng)化學(xué)習(xí)的轉(zhuǎn)變；從單場景優(yōu)化到卸載決策與資源分配聯(lián)合優(yōu)化。但現(xiàn)有的方法還存在著許多的缺點(diǎn)和不足，更復(fù)雜的問題有待解決。相信在未來，多智能體之間的合作與協(xié)同將成為發(fā)展的主流趨勢，互搏與內(nèi)耗將不斷減少，聯(lián)合優(yōu)化將會(huì)創(chuàng)造更高的價(jià)值。