MEC 中卸載決策與資源分配的深度強化學習方法

楊 天，楊 軍

（寧夏大學 信息工程學院，寧夏 銀川 750021）

0 概述

目前，智能化終端已經成為現代生活中不可缺少的一部分［1-2］，同時隨著5G 通信技術的發展，人們開始在智能終端設備上開展高清視頻直播、增強現實等新型業務。然而，由于受到計算能力和電池容量的限制，終端設備無法高效地滿足大量新型計算任務低時延、高計算的基本要求［3］，而若將計算密集型任務卸載至云端，則會增加傳輸的延遲和額外的網絡負載［4-5］。為此，人們提出移動邊緣計算（Mobile Edge Computing，MEC）［6-7］技術，將云端的計算與存儲能力遷移至網絡邊緣，通過邊緣進行任務計算，從而降低終端設備能耗與執行時延，提高服務質量［8］。

在MEC 環境中，以卸載決策和資源分配為主的計算卸載技術是學者們重點研究的對象［9］。目前相關研究主要針對多用戶單MEC 服務器場景，且多數沒有同時考慮計算資源約束與時延約束［10-17］，這將導致不能更準確地模擬真實的卸載情況，如在自動駕駛、緊急救援等場景下，需要在有限資源下完成時延敏感型任務的計算。本文將卸載場景轉變為多用戶多MEC 服務器場景，同時考慮計算資源有限與時延約束的情況，結合深度強化學習理論和一種新型目標函數，提出卸載決策與資源分配的聯合優化方法，從而在滿足時延約束的情況下縮短計算任務完成時間并降低終端能耗。

1 相關研究

近年來，國內外學者已對MEC 計算卸載技術進行了深入的研究。文獻［10］將可再生綠色能源引入到MEC系統中，將執行時延與卸載失敗率作為優化目標，基于Lyapunov 優化提出一種卸載決策與資源分配算法，但該系統僅適用于單用戶卸載情況。文獻［11］根據任務剩余完成時間進行邊緣服務器的計算切換來縮短任務完成時間，以提高任務的卸載效率。文獻［12］結合K近鄰（K Nearest Neighbor，KNN）算法與強化學習中的Q-learning 算法，提出一種多平臺卸載智能資源分配方法。該方法首先通過KNN 算法選擇卸載節點，然后通過Q-learning算法優化資源分配，以降低系統時延成本。文獻［11-12］雖然研究多用戶卸載問題，但更關注于時延的優化而忽略了設備能耗的優化。文獻［13］為了在計算依賴任務時控制超出時延約束的任務比例，提出一種最優資源管理策略以最小化移動設備能耗，但該模型沒有考慮邊緣設備的計算資源約束。文獻［14］在邊緣節點計算資源受限的情況下提出基于非合作博弈論的傳輸功率分配算法，獲得了較好的計算卸載性能。文獻［15］針對多用戶完全卸載決策提出一種基于博弈論的任務卸載算法。該算法將卸載博弈模型轉換為勢博弈模型，通過基于有限改進性質的分布式博弈方法尋找納什均衡解，以同時優化計算時延和設備能耗。文獻［16］提出一種基于深度神經網絡（Deep Neural Network，DNN）的優化算法。該算法首先利用序列二次規劃（Sequential Quadratic Programming，SQP）法得到優化結果，然后利用優化結果訓練DNN，不斷更新網絡權值，直到訓練完成。實驗結果表明，訓練完成的DNN可以很好地逼近SQP 的優化結果且精度很高，運行時間也大幅縮短。文獻［14-16］雖然考慮了計算資源約束，但提出的系統模型均建立在單個MEC 服務器上，沒有對多個MEC 服務器的計算資源受限問題進行研究。文獻［17］建立了一個同時考慮終端、邊緣節點和云計算節點的半馬爾科夫決策過程資源分配模型，并提出一種尋找最優資源分配方案的算法以降低能耗和時延，但該研究沒有考慮任務計算的時延約束。

本文將多用戶單MEC 服務器卸載場景轉變為多用戶多MEC 服務器卸載場景，同時考慮服務器計算資源約束與任務時延約束，研究卸載決策與資源分配的聯合優化方法，以期使系統在滿足時延約束時縮短完成時間并降低終端能耗。針對研究問題設計一種新的目標函數并數學建模，利用結合深度學習感知能力與強化學習決策能力的深度強化學習方法，基于Nature Deep Q-learning（Nature DQN）算法并根據問題模型進行部分改進，提出Based DQN 算法，并將該算法與全部本地卸載算法ALO、隨機卸載與分配算法ROA、最小完成時間（Minimum Complete Time，MCT）算法［11］和多平臺卸載智能資源分配算法［12］進行實驗對比，同時對比不同目標函數下的優化結果。

2 系統模型

本文系統模型場景為多用戶多服務器應用場景，如圖1 所示，其中有N臺終端設備與M臺MEC 服務器，并通過無線通信鏈路連接MEC 服務器計算卸載終端設備的任務數據。本文假設每個終端設備都可以對自己的執行任務進行卸載計算或本地計算，卸載時任務只能卸載到一臺MEC 服務器上進行計算，并且每個終端設備處于無線連接的范圍之內。而每臺MEC 服務器的計算能力有限，不能同時接受每一個終端的卸載請求。終端設備的集合為U=｛1，2，…，i，…，N｝，MEC 服務器的集合為S=｛1，2，…，j，…，M｝，所有任務的集合為R。模型中每個終端設備i都有一個待處理的計算密集型任務Ri，具體包括計算任務Ri所需的數據Di（代碼和參數）、計算任務Ri所需的CPU 工作量Wi以及任務Ri的完成時延約束ηi，即Ri?(Di，Wi，ηi)。

圖1 系統模型場景Fig.1 Scene of system model

以向量X=[x1，x2，…，xi，…，xN]表示每個Ri的卸載決策。其中，xi∈{0，1，…，j，…，M}，x=0 表示當前為本地卸載，其余表示將Ri卸載至第j臺MEC 服務器。

2.1 計算模型

若Ri在本地處理，用TLi表示Ri本地執行的時間，具體定義如式（1）所示。

其中：工作量Wi具體為完成Ri所需的CPU 周期總數表示終端設備i本地的計算能力，即每秒所執行的CPU 周期數。

其中：Ji為終端設備i計算每單位CPU 周期的能耗，根據文獻［18］，

若Ri在邊緣處理，Ri邊緣執行下的時延與設備能耗應分別從數據上傳、數據處理和數據回傳3 個部分進行計算，具體如下：

1）終端設備i將Ri的數據通過無線信道上傳至相應的MEC 服務器。

其中：Di為Ri的數據大小；νK為系統模型中的數據上傳速率，即每秒上傳的數據量。則終端設備i上傳數據的能耗如式（4）所示。

其中：pK為終端設備i的上行傳輸功率。

2）MEC 在接收到處理數據后分配計算資源進行計算。

此時，終端設備i沒有計算任務而處于等待狀態并產生空閑能耗，設為終端設備i的空閑功率，則卸載計算下終端設備i的空閑能耗為：

3）MEC 服務器將計算結果返回給終端設備i。

根據文獻［19］可知，回傳時計算結果較小且下行速率較高。因此，本文忽略終端設備接收時的時延與能耗。則Ri邊緣執行下的時延為傳輸時延與MEC 服務器計算時延之和，即：

Ri邊緣執行下的設備能耗為設備i的上傳能耗與設備i等待Ri在MEC 服務器上計算完成的空閑能耗之和，即：

綜上所述，終端設備i中任務Ri整個計算過程的時延Ti和能耗Ei分別為：

需要注意的是，Ti與應滿足式（12）和式（13）所示的限制條件。

其中：Ri的時延約束ηi參照文獻［20］，為計算能力是1.4 GHz 并根據式（1）計算結果的2 倍；Fj為第j臺MEC服務器的整體計算資源，即每個卸載至第j臺MEC 服務器的Ri所分配的計算資源總和不應超過Fj。

2.2 問題模型

本文的研究目的是在多用戶多MEC 服務器場景下，考慮計算資源有限且計算任務具有時延約束的情況，設計聯合優化系統的卸載決策和資源分配方案，使得所有計算任務在滿足時延約束下縮短完成時間并最小化所有終端設備的能耗，同時延長終端設備的使用時間。因此，系統目標函數G定義如式（14）所示。

其中：X為任務卸載決策向量；Y為計算資源分配向量；限制條件C1～C3 表示每個任務Ri只能卸載到本地或其中一臺MEC 服務器上進行計算；C4 表示任務完成時延的約束；C5 表示分配的計算資源應滿足的限制約束。

3 卸載決策與資源分配的聯合優化方法

在上文建立的問題模型下，考慮采用結合強化學習與深度學習的深度強化學習方法進行問題求解，一方面是因為深度強化學習中的強化學習理論以“試錯”的方式讓智能體在與環境交互的過程中通過獲得獎勵來指導行為以改善決策，這適用于本文模型中任務卸載決策與計算資源分配的聯合優化，另一方面是因為引入深度學習的深度強化學習方法可避免狀態空間、動作空間過大而帶來的存儲困難問題。因此，下文將結合系統模型，首先設計系統狀態（State）、系統動作（Action）、獎勵函數（Reward）3 個要素，然后對深度強化學習算法中的Nature DQN 算法進行部分改進，提出一種基于深度強化學習的卸載決策與資源分配聯合優化方法Based DQN，使得目標函數值G最小。

3.1 系統狀態、動作與獎勵函數設計

為聯合優化卸載決策與資源分配方案以最小化目標函數值，令系統狀態s包括卸載決策向量X、計算資源分配向量Y、剩余計算資源向量Z與G，如式（19）所示。

其中，Z=[z1，z2，…，zj，…，zM]，zj表示為第j臺MEC 服務器所剩的計算資源：

初始化時，系統狀態為本地卸載狀態，即X為零向量，Y中每個任務所分配的計算資源為fLi，G為全部本地卸載下的計算值，Z中每個zj=Fj。

系統動作a應確定對哪一項任務進行怎樣的卸載決策與計算資源分配，即對終端設備i下的任務Ri選擇卸載與資源分配方案，調整系統狀態，如式（21）所示。

其中：λ為Ri的卸載方案，λ∈｛0，1，…，j，…，M｝；ψ為Ri的計算資源分配方案。需要注意的是，當λ=0 時，

獎勵函數r應關聯目標函數，具體定義如式（22）所示。

其中：G為當前t時刻狀態st下的目標函數值；G′為st采取動作at到下一狀態st+1下的目標函數值，兩者分別通過各自狀態中的卸載決策向量與資源分配向量計算出相應的時延與能耗后，再按照式（14）進行計算；GL為全部本地卸載下的計算值，當G′結果更優時（G＞G′）獲得正獎勵，即在狀態st下采取動作at能夠獲得更優的目標函數值，反之獎勵為非正值。

3.2 基于Nature DQN 算法的聯合優化

Nature DQN 是在Q-Learning 算法的基礎上演變而來的。在Q-learning 算法中，智能體在t時刻下觀察環境中的狀態st，根據概率以隨機或者Q表的方式選擇動作at執行，改變到狀態st+1并獲得獎勵rt，通過式（23）更新Q表與當前狀態，并循環此學習過程，收斂于最大的Q函數Q*，得到最優策略。

其中：δ是學習率；γ是折扣系數。

相較于Q-learning 算法，Nature DQN 算法不同點在于其Q值不是直接通過系統狀態和系統動作計算，而是通過Q網絡（神經網絡）進行計算，即期望神經網絡擬合Q表，如式（24）如示。以神經網絡進行擬合，可以應對隨著狀態、動作維數的增大而帶來的Q表存儲困難問題，如在本文所提的狀態與動作中，隨著N與M的增加，自身的組合數量龐大，Q表將難以進行對應Q值的存儲。

其中：θ為神經網絡的參數。Nature DQN 算法中使用了2 個結構相同但θ不同的Q網絡（當前網絡Q與目標網絡Q′），當前網絡Q進行動作選擇并更新θ，目標網絡Q′計算目標Q 值。目標網絡Q′中的參數θ′不需要迭代更新，而是每隔一段時間復制θ進行延遲更新，以減少目標Q值和當前Q值相關性，使算法更好地收斂。

此外，Nature DQN 采用經驗回放訓練強化學習的學習過程，即將st、at、rt、st+1、done（判斷學習是否結束的布爾值）五元組存儲到一個經驗池中，通過隨機抽樣進行學習，減少樣本之間的相關性，更好地訓練神經網絡。

結合問題模型，本文根據約束條件C5，在原始Nature DQN 算法的動作選擇上增加了at中ψ是否滿足計算資源約束的判斷，篩選有效的執行動作，以提高學習效率。具體算法如下：

將動作篩選算法（AS）加入到Nature DQN 算法中，若at滿足計算資源約束則執行該動作，否則重新根據ε貪婪策略選取動作。具體算法如下：

4 實驗與結果分析

利用Python 語言在Visual Studio Code 平臺上對本文算法與全部本地卸載算法（ALO）、隨機卸載與分配算法（ROA）、最小完成時間算法（Minimum Complete Time，MCT）［11］、多平臺卸載智能資源分配算法［12］進行實驗對比，以驗證本文算法的有效性，同時在不同目標函數下對比Based DQN 算法的優化效果，以驗證新提目標函數的有效性。具體仿真參數如下：

假設每一臺設備i的計算能力為1 GHz，上行傳輸功率為700 mW，空閑功率為100 mW，上傳速率為2 Mb/s，M=2，且每臺MEC 服務器的整體計算能力分別為5 GHz 與4 GHz，ψ∈｛fLi，1.2，1.4，1.6｝GHz。任務Ri中的數據Di服從（500，1 000）的均勻分布，單位為Kb。工作量Wi服從（1 000，1 500）的均勻分布，單位為Megacycles。

對于深度強化學習的參數，設ε 為0.9，學習率δ為0.001，折扣系數γ為0.9，經驗回放集合Φ大小為2 000，隨機采樣樣本數b為32，更新頻率h為50，學習間隔步長σ為5（學習步數需大于200）。

4.1 算法收斂情況

假設有7 臺終端設備，即所需執行的任務數量為7，執行回合數（episode）為150，比較目標函數值G的變化，如圖2 所示。可以看出：ROA 算法在整個迭代過程震蕩，無法收斂；ALO 算法始終保持收斂，但由于全部任務卸載到本地，造成較大的時延與能耗，目標函數值較高；其余3 種算法隨著episode 的增加逐步收斂，MCT 算法在第96 回合達到收斂；多平臺卸載智能資源分配算法在第127 回合后逐步收斂，且收斂目標函數值比MCT 算法的計算結果降低3.12%；Based DQN 算法自100 回合后逐步收斂，其結果較于多平臺卸載智能資源分配算法降低1.53%，在5 種算法中結果最優。MCT 算法與多平臺卸載智能資源分配算法結果較差于Based DQN 算法，這是因為兩者對任務完成時延關注更多。此外，多平臺卸載智能資源分配算法中使用Q-learning 算法進行訓練學習，由于本文中狀態、動作維數較大，Q表存儲問題導致探索不全面，使得多平臺卸載智能資源分配算法不能得到最優結果。

圖2 5 種算法的目標函數值變化Fig.2 Change of objective function values of five algorithms

將ROA 算法、MCT 算法、多平臺卸載智能資源分配算法和Based DQN 算法的能耗分別與ALO 算法的能耗總和做差，再分別除以ALO 算法的能耗總和作為降低能耗比例（Energy Reduced Scale，ERS），并聯合對比在滿足時延約束下的縮短完成時間的比例（Time Reduced Scale，TRS），如表1 所示。可以看出：MCT 算法、多平臺卸載智能資源分配算法與Based DQN 算法可在縮短完成時間的同時降低終端能耗50%以上，且Based DQN 算法中時延與能耗減少的比例更大。

表1 4 種算法的TRS 和ERSTable 1 TRS and ERS of four algorithms %

4.2 不同學習率下的算法收斂情況

分別在0.01、0.001、0.0001 這3 種不同學習率δ下對比Based DQN 算法的收斂情況，如圖3 所示。可以看出：當δ為0.01時，算法收斂速度較快，但較大的學習率導致收斂于局部最優解；當δ較小為0.000 1 時，算法收斂速度較慢，較長的收斂時間影響了算法的優化效率。

圖3 不同學習率下Based DQN 算法的收斂情況Fig.3 Convergence of Based DQN algorithm under different learning rates

為進一步比較Based DQN 算法在不同學習率δ下對時延與能耗的優化效果，分別對比不同學習率δ下的Based DQN 算法在收斂過程中TRS 與ERS 的變化情況，如圖4、圖5 所示。可以看出：當δ為0.01時，TRS 與ERS 收斂于局部最優解；當δ為0.000 1時，TRS 與ERS 收斂過慢；當δ為0.001 時，Based DQN算法收斂后對時延與能耗的優化效果最佳。因此，本文算法采用0.001 的學習率。

圖4 不同學習率下Based DQN 算法的TRSFig.4 TRS of Based DQN algorithm under different learning rates

圖5 不同學習率下Based DQN 算法的ERSFig.5 ERS of Based DQN algorithm under different learning rates

4.3 不同累計任務數量下的算法目標函數值對比

分別模擬［20，100］的累計任務數量，對比5 種算法的目標函數值，如圖6 所示。可以看出：隨著累計任務數量的增加，5 種算法的G值逐漸增大，而在不同累計任務數量下ALO 算法、ROA 算法的G值較大，這主要是由于兩種算法沒有對任務卸載方案與計算資源分配方案進行合理優化，導致任務執行時，時延與能耗較高。3 種優化算法相比前述兩種算法在不同累計任務數量下能夠有效降低目標函數值。當累計任務數量為20 時，3 種算法差別較小，但隨著累計任務數量的增加，Based DQN 算法的優化效果得以體現。以累計任務數量等于100 時為例，多平臺卸載智能資源分配算法、Based DQN 算法相較于MCT 算法G值分別降低3.62%、5.89%。

圖6 不同累計任務數量下5 種算法的目標函數值Fig.6 Objective function values of five algorithm under different numbers of cumulative tasks

此外，本文將多平臺卸載智能資源分配算法與Based DQN 算法相較于MCT 算法的時延與能耗分別降低的比例進行對比，如表2 所示。可以看出：在大量累計任務數量下，Based DQN 算法優化效果更佳。

表2 2 種算法對MCT 算法的優化效果Table 2 Optimization effects of two algorithms for MCT algorithm %

4.4 不同目標函數下的優化情況

對于降低時延與能耗的多目標優化問題，通常以任務執行時延與終端執行能耗的加權和作為目標函數進行問題求解。將每一個任務執行時延與能耗加權和的平均值作為另一種目標函數（見式（25）），與本文所提目標函數（見式（14））進行時延與能耗的優化對比，終端設備數為7。

在式（25）所示的目標函數中：τ為執行時延的權重系數；1-τ為執行能耗的權重系數。考慮到本文是在滿足時延約束下縮短時延、降低能耗，將τ分別取值為0.7、0.6、0.5 與式（14）在Based DQN 算法下進行TRS、ERS 聯合實驗對比，如表3 所示。可以看出：當τ=0.7 和τ=0.6 時，算法更多關注時延的優化；當τ=0.5 時，優化結果較為均衡，而在新目標函數下的Based DQN 算法優化效果最好，能夠在滿足時延約束下最大程度地縮短時延并降低能耗。

表3 不同目標函數下Based DQN 算法的TRS 和ERSTable 3 TRS and ERS of Based DQN algorithm under different objective functions %

為進一步比較不同目標函數對時延與能耗的優化程度，在累計任務為100 時，對比4 種目標函數下Based DQN 算法相較于MCT 算法時延與能耗分別降低的比例，如表4 所示。可以看出：Based DQN 算法在新目標函數下時延與能耗的優化效果更好，驗證了本文所設計目標函數的有效性。

表4 不同目標函數下Based DQN 算法對MCT 算法的優化效果Table 4 Optimization effect of Based DQN algorithm for MCT algorithm under different objective functions %

5 結束語

本文在MEC 服務器計算資源有限的情況下考慮時延約束，設計一種新的目標函數并構建數學模型，對深度強化學習中的Nature DQN 算法進行改進，提出卸載決策與資源分配的聯合優化算法：Based DQN，以縮短計算任務完成時間，降低終端能耗。實驗結果表明，該算法的優化效果均優于ALO 算法、ROA 算法、MCT算法和多平臺卸載智能資源分配算法，且其在本文設計的目標函數下結果更優。下一步將研究任務具有優先級與執行順序以及無線干擾環境下的卸載決策和資源分配方案。