多智能體邊緣計算任務卸載

趙庶旭，元 琳，張占平

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

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

1 相關研究

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

2 系統建模

2.1 網絡建模

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

圖1 網絡模型圖Fig.1 Network model diagram

2.2 任務建模

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

其中，x∈{0,1,2,…,p,…,N}，當x=0時代表本地執行，當x=1時代表子任務將被卸載到序號為1的ES上執行。同理，當x=p時代表子任務將被卸載到序號為p的ES上執行。

2.3 時延模型

假設本地處理任務的時延有且只由CPU產生，定義為：

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

若Rij需卸載到ES上執行，則需要從發送時延、傳播時延和處理時延三方面對在ES上的時延進行分析，定義為：

綜上所述，當子任務之間存在依賴關系時，總時延為在本地執行的子任務時延之和加在邊緣服務器上執行的子任務時延之和：

當子任務之間相互獨立時，總時延為第i個智能體上所有子任務時延的最大值：

2.4 能耗模型

這里的能耗是指智能體端的能耗，假設在本地執行的任務所產生的能耗只與CPU有關，能耗模型定義如下：

2.5 費用模型

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

其中，uES表示邊緣服務器單位時間的價格，表示服務器p計算資源的使用率，表示服務器p計算資源的總量。

2.6 目標函數

多智能體邊緣計算任務卸載問題是一個最優化問題，本文的目標是在保障時延的前提下，最小化能耗和費用，在提升整個MEC系統的資源利用率的同時延長智能體的續航時間，目標函數定義如下：

其中，α和β分別是能耗和費用所占權重。

3 模型求解

為求解上述模型，本文提出一個部分可觀測的、多智能體完全合作的基于深度強化學習的邊緣計算任務卸載算法。在實際應用環境中，由于底層物理鏈路的不穩定性，邊緣服務器的狀態存在不能被完整觀測的可能性，稱其為“部分可觀測”。在多智能體強化學習中，每一個智能體都是自主、可交互的[19]，它們獨立地接收邊緣服務器的狀態信息，根據自身的策略函數決定當前采取的卸載方案。同時，智能體之間相互通信，共同優化目標值，整體的卸載效果通過一個綜合的標準來評判。

強化學習是一種具備自學習能力、能做出最優決策的算法[20]。它將問題抽象為智能體不斷在環境中試錯的過程，在每一個時間步長中，智能體都會收到環境的狀態信息，并根據狀態信息作出響應動作。在下一個時間步長中，會根據環境的反饋給該智能體一個相應的獎勵值。若是期望的結果，則給一個正獎勵，反之，則給一個負獎勵[21-22]。目標是最大化累積獎勵[23]。但強化學習局限于低維度問題，在大規模狀態、動作空間問題中，存在“維度災難”。因此，引入深度學習，將強化學習的決策能力與深度學習的感知能力相結合，依靠強大的深度神經網絡的表示學習來解決高維卸載問題。

圖2 模型結構圖Fig.2 Model structurediagram

3.1構建MDP

馬爾可夫決策過程（Markov decision process，MDP）一般包含狀態空間（state space，S）、動作空間（action space，A）和獎勵函數（reward function，R）。狀態空間S定義如公式（10）所示，包含資源剩余向量U，決策矩陣X，目標函數G。

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

動作空間A表示在每一個狀態下可以采取的所有動作，定義如下：

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

獎勵函數R表示智能體執行動作、狀態轉移后，根據環境反饋獲得的獎勵，定義如下：

其中，Gt為t時間段內的目標函數值，Gt+1為智能體在狀態St下作出響應動作At后t+1時間段內的目標函數值，GSD為任務在本地執行時的目標函數值。上述三個目標函數值均根據公式（9）計算。注意，在本地執行時，目標函數不存在費用部分（等于零），只有能耗部分和時延限制。當Gt+1＞Gt時，即執行動作At后，G變大，即能耗和花費增大，向不期望的方向發展，給予負獎勵。反之，給予正獎勵。

3.2 基于DRQN的任務卸載算法

深度遞歸Q網絡（DRQN）是對深度Q網絡（DQN）的一種改進，利用遞歸神經網絡（RNN）解決部分可觀測馬爾可夫決策過程（POMDP），提高DQN性能。在MEC應用場景中，由于底層物理鏈路的不穩定性和智能體感知的局限性，智能體很難接收到當前時間段內環境的精準狀態信息，導致了POMDP問題。DRQN保留先前狀態信息，補充當前狀態信息，解決缺失值問題。具體實現過程是用長短時記憶遞歸神經網絡（LSTM RNN）代替DQN中卷積層后第一個全連接層，DRQN架構如圖3所示。

圖3 DRQN架構圖Fig.3 DRQN architecture diagram

將邊緣服務器ES返回的狀態信息作為輸入，卷積層對狀態信息進行卷積運算，得到特征圖，傳遞給LSTM層，LSTM根據先前記憶補充狀態信息，并更新記憶，最后經過一個全連接層輸出Q值。其中，ht是上一時間步長網絡的返回值，即ht=LSTM(ht-1,at)，作為下一時間步長的輸入。

DRQN利用一個權重為θ的神經網絡來逼近Q函數，即Q(ht,at;θ)≈Q*(st,at)。損失函數為目標值與預測值的均方差，定義如下：

其中，r為獎勵，γ為折扣因數，位于0～1之間，決定了即時獎勵和未來獎勵的重要性，接近0意味著即時獎勵更重要，接近1意味著未來獎勵更重要。神經網絡通過梯度下降更新θ最小化損失。注意，目標Q的參數是θ′，和預測Q的參數θ不同。DRQN采用一種稱為目標網絡的獨立網絡來計算目標值，目標網絡與預測網絡結構一致，但滯后于預測網絡若干時間步長，從預測網絡中復制權重θ更新自己的權重θ′。因此，目標Q值與預測Q值具有一定的差異性，進而用來計算損失。

智能體從狀態s執行某一動作a轉移到狀態s′，獲得獎勵r,＜s,a,s′,r＞就是智能體的一條經驗，保存在經驗緩存中。DRQN從經驗緩存中隨機選擇一批訓練樣本，減少經驗之間的相關性，提高算法的泛化性。具體算法如下：

4 仿真實驗

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

圖4 不同折扣因數DRQN能耗、花費對比Fig.4 Comparison of energy consumption and cost ofDRQN with different discount factors

在滿足最大時延的前提下，本文將DRQN、DQN以及隨機卸載算法與本地執行的能耗和費用做差再除以本地執行的能耗和費用的比例（energy and cost reduction ratio，ECRR）作為算法的評價指標之一。如表1所示，DQN和DRQN能耗和花費縮減率都達到了50%以上，并且DRQN比DQN提高了近2個百分點。

表1 ECRR對比表Table 1 ECRR comparison table

不同任務數量下的各算法性能研究，任務數量取值范圍為[20，100]，以10為步長，畫出本地執行、隨機卸載算法、DQN以及DRQN在能耗、花費和時延上的對比圖。

由圖5可以看出，隨著任務數量的增加，各算法生成的卸載策略在能耗和花費方面大致呈現上升趨勢，DRQN較隨機卸載算法、DQN在能耗和花費上表現更佳。本地卸載所消耗的能量最多，這是由于智能體的計算能力遠遠小于邊緣服務器的計算能力造成的。另外，從圖5可以看出隨機卸載算法具有一定的波動，這是因為算法的隨機性造成的。

圖5 各算法仿真結果對比圖Fig.5 Comparison of simulation results of various algorithms

5 結束語

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