楊 天，楊 軍

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

0 概述

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

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

1 相關研究

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

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

2 系統(tǒng)模型

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

圖1 系統(tǒng)模型場景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本地執(zhí)行的時間，具體定義如式（1）所示。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 問題模型

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

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

3 卸載決策與資源分配的聯(lián)合優(yōu)化方法

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

3.1 系統(tǒng)狀態(tài)、動作與獎勵函數(shù)設計

為聯(lián)合優(yōu)化卸載決策與資源分配方案以最小化目標函數(shù)值，令系統(tǒng)狀態(tài)s包括卸載決策向量X、計算資源分配向量Y、剩余計算資源向量Z與G，如式（19）所示。

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

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

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

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

獎勵函數(shù)r應關聯(lián)目標函數(shù)，具體定義如式（22）所示。

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

3.2 基于Nature DQN 算法的聯(lián)合優(yōu)化

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

其中：δ是學習率；γ是折扣系數(shù)。

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

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

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

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

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

4 實驗與結果分析

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

假設每一臺設備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中的數(shù)據(jù)Di服從（500，1 000）的均勻分布，單位為Kb。工作量Wi服從（1 000，1 500）的均勻分布，單位為Megacycles。

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

4.1 算法收斂情況

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

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

將ROA 算法、MCT 算法、多平臺卸載智能資源分配算法和Based DQN 算法的能耗分別與ALO 算法的能耗總和做差，再分別除以ALO 算法的能耗總和作為降低能耗比例（Energy Reduced Scale，ERS），并聯(lián)合對比在滿足時延約束下的縮短完成時間的比例（Time Reduced Scale，TRS），如表1 所示?？梢钥闯觯篗CT 算法、多平臺卸載智能資源分配算法與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 所示?？梢钥闯觯寒敠臑?.01時，算法收斂速度較快，但較大的學習率導致收斂于局部最優(yōu)解；當δ較小為0.000 1 時，算法收斂速度較慢，較長的收斂時間影響了算法的優(yōu)化效率。

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

為進一步比較Based DQN 算法在不同學習率δ下對時延與能耗的優(yōu)化效果，分別對比不同學習率δ下的Based DQN 算法在收斂過程中TRS 與ERS 的變化情況，如圖4、圖5 所示?？梢钥闯觯寒敠臑?.01時，TRS 與ERS 收斂于局部最優(yōu)解；當δ為0.000 1時，TRS 與ERS 收斂過慢；當δ為0.001 時，Based DQN算法收斂后對時延與能耗的優(yōu)化效果最佳。因此，本文算法采用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 不同累計任務數(shù)量下的算法目標函數(shù)值對比

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

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

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

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

4.4 不同目標函數(shù)下的優(yōu)化情況

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

在式（25）所示的目標函數(shù)中：τ為執(zhí)行時延的權重系數(shù)；1-τ為執(zhí)行能耗的權重系數(shù)?？紤]到本文是在滿足時延約束下縮短時延、降低能耗，將τ分別取值為0.7、0.6、0.5 與式（14）在Based DQN 算法下進行TRS、ERS 聯(lián)合實驗對比，如表3 所示?？梢钥闯觯寒敠?0.7 和τ=0.6 時，算法更多關注時延的優(yōu)化；當τ=0.5 時，優(yōu)化結果較為均衡，而在新目標函數(shù)下的Based DQN 算法優(yōu)化效果最好，能夠在滿足時延約束下最大程度地縮短時延并降低能耗。

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

為進一步比較不同目標函數(shù)對時延與能耗的優(yōu)化程度，在累計任務為100 時，對比4 種目標函數(shù)下Based DQN 算法相較于MCT 算法時延與能耗分別降低的比例，如表4 所示?？梢钥闯觯築ased DQN 算法在新目標函數(shù)下時延與能耗的優(yōu)化效果更好，驗證了本文所設計目標函數(shù)的有效性。

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

5 結束語

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