基于深度Q網絡的多目標任務卸載算法

鄧世權，葉緒國

基于深度Q網絡的多目標任務卸載算法

鄧世權1，葉緒國2*

（1.凱里學院 大數據工程學院，貴州 凱里 556011； 2.凱里學院 理學院，貴州 凱里 556011）（*通信作者電子郵箱yexuguo2008@126.com）

在移動邊緣計算（MEC）中，計算資源和電池容量有限的移動設備（MD）可卸載自身計算密集型應用到邊緣服務器上執行，這樣不僅可以提高MD計算能力，也能降低能耗。然而，不合理的任務卸載決策不但會延長應用完成時間，而且會大量增加能耗，進而降低用戶體驗。鑒于此，首先分析MD的移動性和任務間的順序依賴關系，建立動態MEC網絡下的以應用完成時間和能源消耗最小為優化目標的多目標任務卸載問題模型；然后，設計求解該問題的馬爾可夫決策過程（MDP）模型，包括狀態空間、動作空間和獎勵函數，并提出基于深度Q網絡（DQN）的多目標任務卸載算法（MTOA-DQN），該算法采用一條軌跡作為經驗池的最小單元來改進原始的DQN算法。在多種測試場景下，MTOA-DQN的性能在累積獎勵和Cost方面均優于三種對比算法（基于分解的多目標進化算法（MOEA/D）、自適應的DAG任務調度算法（ADTS）和原始的DQN算法），驗證了該算法的有效性和可靠性。

移動邊緣計算；任務卸載；完成時間；能源消耗；強化學習

0 引言

隨著5G、物聯網等技術的不斷演進，移動設備（Mobile Device， MD）正迅速成為世界上規模最大的人工智能平臺，人們已進入了一個由汽車、高清攝像頭、可穿戴設備、智能手機等物聯網設備組成的物物相聯的時代［1-2］。種類繁多的新型應用也層出不窮，如人臉識別、云游戲、虛擬現實（Virtual Reality， VR）/增強現實（Augmented Reality， AR）等，此類應用在占用大量計算和存儲資源的同時，也對時效性提出了更高需求。然而，MD的兩個關鍵技術問題嚴重制約了移動互聯網的發展：一是為了MD的便攜性，在設計時需考慮其尺寸、重量和散熱等問題，導致MD計算能力無法與同等價位的臺式設備相提并論，在應對VR/AR等時延敏感型應用時顯得力不從心，延長了應用的響應時間，降低用戶體驗質量（Quality of Experience， QoE）；二是長久以來難以突破的電池技術也限制了QoE，特別是在運行云游戲、視頻直播等應用時，大量消耗續航能力有限的MD電池能量［3-4］，降低了該類應用在MD上部署的可能性。

為了解決上述問題，移動邊緣計算（Mobile Edge Computing， MEC）［5-6］應運而生，它將IT服務環境和云計算技術在網絡邊緣相結合，提高邊緣網絡的計算能力和存儲能力，這不僅減少了網絡操作，還降低了服務時延，為用戶提供了超低時延和高帶寬的網絡服務解決方案，保障了用戶的QoE。因此，MD利用MEC技術可卸載其計算任務到邊緣服務器上執行，在提高MD計算能力的同時，也降低了能源消耗，該過程稱為計算卸載［7］。

當前，隨著代碼分解和并行計算的蓬勃發展，MD待處理的應用可被建模成一個有向無環圖（Directed Acyclic Graph， DAG），即應用被分解成多個任務，且任務間存在順序依賴關系。這樣的分解方式可實現細粒度的任務卸載，使任務在本地和邊緣服務器上并行處理成為可能。然而，不合理的卸載決策不僅延長應用完成時間，也大量消耗MD電池能量。另外，任務間的順序依賴關系對最優卸載方案的求解也帶來了巨大挑戰。

深度強化學習（Deep Reinforcement Learning， DRL）將強化學習（Reinforcement Learning， RL）的高決策能力和深度神經網絡（Deep Neural Network， DNN）的強表示能力有機結合［8-9］。承載了DRL算法的智能體不斷與環境交互，可主動學習在不同環境狀態下采取的最佳動作（即策略），從而最大化長期累積獎勵。借助DNN超凡的表示能力，可有效應對復雜、動態的網絡環境，因此能夠擬合最優策略（卸載決策）。DRL被廣泛應用于復雜的工程優化和機器人控制問題中，并已在面向DAG的任務卸載問題中嶄露頭角［10-12］。鑒于此，本文提出基于深度Q網絡（Deep Q-Network， DQN）的多目標任務卸載算法（Multi-objective Task Offloading Algorithm based on DQN， MTOA-DQN）來最小化應用完成時間和MD電池能源消耗。本文的主要工作包括以下三個方面：

1）考慮MD的移動性和任務間的順序依賴關系，建立動態MEC網絡下的多目標任務卸載問題模型，以最小化應用完成時間和MD電池能源消耗為優化目標。該模型首次在具有多邊緣服務器的MEC系統中研究了依賴性任務的卸載問題。

2）針對以上建模問題，設計了相應的馬爾可夫決策過程（Markov Decision Process， MDP），包括狀態空間、動作空間和獎勵函數。提出基于DQN的多目標任務卸載算法MTOA-DQN，該算法將一條軌跡作為經驗池的最小單元，保證了抽樣數據的完整性，進而提高算法收斂性能。

3）對于新建模的任務卸載問題，不存在基準測試集，因此隨機生成多種測試場景對本文算法進行性能評估。在累積獎勵和Cost方面，本文算法均優于基于分解的多目標進化算法（MultiObjective Evolutionary Algorithm based on Decomposition， MOEA/D）、自適應的DAG任務調度（Adaptive DAG Tasks Scheduling， ADTS）算法和原始DQN算法。

1 相關工作

MD采用MEC下的計算卸載技術可將其計算密集型或時延敏感型應用卸載到邊緣服務器上執行，用于輔助計算和續航能力有限的MD，以支撐該類應用在MD上的部署。因此，國內外學者針對怎樣在MD和邊緣服務器之間卸載任務，以及在減少應用完成時間的同時盡可能降低MD能耗等問題進行了一系列研究。

Lin等［13］研究了移動云計算（Mobile Cloud Computing，MCC）網絡中的任務調度問題，提出基于動態電壓頻率調節（Dynamic Voltage and Frequency Scaling， DVFS）技術的任務調度算法來最小化應用完成時間和MD能源消耗。Mahmoodi等［14］介紹了無線感知的聯合任務調度和計算卸載算法，可確定應用中每個任務的執行位置和調度順序，通過MD和云端的并行計算來縮短應用完成時間。周業茂等［15］提出了移動云計算下基于延時傳輸的多目標工作流調度算法，該算法基于非支配排序遺傳算法（Nondominated Sort Genetic Algorithm， NSGA-Ⅱ）設計了工作流的執行位置和執行順序的編碼策略。Song等［16］研究了應用完成時間和MD能源消耗之間的權衡，并建模為多目標計算卸載問題，提出了一種基于分解的多目標進化算法MOEA/D；但他們所考慮的MEC環境是靜態的，并未考慮MD的移動性。楊天等［17］提出一種面向多用戶的任務卸載與資源分配算法，以MEC系統的總成本最小為優化目標，但未考慮任務間的順序依賴關系。Yang等［18］提出了一種綜合框架，允許MD卸載任務到云端或邊緣服務上執行，將該卸載問題建模為能源開銷最小化問題，并提出了一種輕量級線性規劃算法。Wu等［19］針對DAG調度問題，設計了相應的MDP模型，并提出了基于策略梯度DRL的自適應的DAG任務調度（ADTS）算法來最小化應用完成時間。詹文翰等［20］提出了基于近端策略優化（Proximal Policy Optimization）的計算卸載調度方法來最小化應用完成時間。Yan等［21］研究了MEC系統下的應用任務卸載，提出了基于Actor-Critic架構的DRL來確定每個任務執行位置和分配MD計算功率，從而減少應用完成時間。

上述研究工作中，大多數考慮的MEC網絡環境是靜態的，例如，在MD執行應用過程中，其地理位置保持不變。然而，在真實網絡環境中，動態性和不確定性是MEC網絡的關鍵特征，如MD的移動性和無線信道的變化性。此外，已有研究工作要么最小化應用時間，要么最小化MD能源消耗，鮮有兼顧兩者。基于以上分析，本文研究動態MEC網絡環境下的多目標任務卸載問題，并滿足任務間的順序依賴關系，同時最小化應用完成時間和MD能源消耗。

2 系統模型

圖1 MEC系統示意圖

圖2 一個應用的DAG

表1 主要符號匯總

MD在執行應用階段，迅速移動導致其地理位置發生變化，我們假定卸載不同任務時MD可動態移動，但卸載任務過程中MD地理位置保持不變。下面介紹本地計算、邊緣計算和問題描述。

2.1 本地計算

相應地，本地執行消耗的電池能量為：

其中是依賴于芯片結構的有效電容系數。

2.2 邊緣計算

邊緣計算模型是基于文獻［13］中的云計算模型，但存在兩點不同之處：首先本文模型考慮了多個邊緣服務器共存的密集型網絡場景；其次本文模型邊緣服務器的計算能力隨時間動態變化。

進一步可得MD發送任務v的輸入數據所消耗的電池能量為：

綜上所述，MD卸載任務v到邊緣服務器上執行的總時延通過式（12）計算得到，而對應的總能耗通過式（13）計算。

2.3 問題描述

基于本地和邊緣計算，并通過式（14）計算出應用的完成時間：

MD執行應用的總能耗為執行所有任務產生的能耗和，即：

3 算法設計

通過式（17）和（18）可遞歸地計算出應用中每個任務的優先級，然后對每個任務的優先級進行降序排序，得到所有任務的執行順序，表示為：

3.1 MDP模型

1）狀態空間：

2）動作空間：

3.2 基于DQN的多目標任務卸載算法

基于3.1節構建的MDP模型，構建基于DQN的多目標任務卸載算法（MTOA-DQN），如算法1所示。

算法1 MTOA-DQN。

輸入 MD的應用；

12） End For

21） End For

23） End For

4 實驗與結果分析

4.1 算法收斂性

4.2 完整性能比較

為驗證MTOA-DQN對原始DQN改進的有效性，首先與DQN進行性能比較，圖4展示了DQN和MTOA-DQN的累積獎勵曲線。顯然，在三個測試場景下，本文MTOA-DQN的性能要優于原始的DQN，驗證了MTOA-DQN的有效性。在DQN中，經驗池中的數據以一個時間步的轉移樣本作為最小單元，而本文的多目標任務卸載問題在一個回合結束之后才能將應用中的所有任務調度完成，因此這樣的存儲方式不再適用本文問題。為了解決該問題，MTOA-DQN將一個回合之后產生的軌跡作為經驗池中的最小單元，注意一條軌跡代表對多目標任務卸載問題的一次求解，體現了數據的完整性，有助于網絡的訓練，因此本文的MTOA-DQN比原始DQN更適應網絡的動態變化。

對于應用的總開銷（即優化目標（）），比較了以下四種算法：

1）基于分解的多目標進化算法（MOEA/D）［16］：該算法同時優化任務平均處理時延和設備平均能耗，獲得多組Pareto支配解。

2）自適應的DAG任務調度（ADTS）算法［19］：該算法是基于REINFORCE的強化學習方法，旨在最小化應用完成時間。

3）原始的DQN算法［9］：采用神經網絡來逼近Q值，經驗池中元素以一個時間步產生的數據作為最小單元。

4）MTOA-DQN：本文改進的DQN，經驗池中元素以一個回合產生的數據作為最小單元。

為了比較的公平性，MOEA/D的參數設置遵循原文獻［16］的設置方法，即種群規模和最大迭代次數分別為100和100，鄰居個數為10，變異概率為0.01。在所有實驗中，每種算法獨立運行20次，統計算法每次獲得的最優Cost值，因此每種算法存在20個最優值，最后計算這20個值的平均值。

圖5為四種算法運行20次獲得的最優Cost值的箱線圖，圖中縱坐標為算法獲得的最優Cost值。從圖中可看出，MOTA-DQN在三個測試場景下的“箱子”均處于圖的最下側，表明該算法獲得了最小的Cost值，能同時最小化應用完成時間和MD能耗。三種基于RL的方法均優于MOEA/D，這是因為MOEA/D只能解決靜態MEC網絡下的多目標任務卸載問題，并不能適應MD的移動性，這驗證了RL可較好地處理動態MEC網絡環境下的問題。在RL算法中，DQN是基于值函數的方法，ADTS是基于策略的方法，根據實驗可知，DQN優于ADTS，這反映了基于值函數的方法能更好地處理本文的問題，這就是為什么本文改進DQN算法來處理多目標任務卸載問題。另一方面，ADTS僅優化了應用完成時間，并未考慮MD能耗指標，從而導致較高的Cost值。

圖3 不同參數下的累積獎勵

圖4 不同任務規模N下兩種DQN的累積獎勵

圖5 不同任務規模N下四種算法的箱線圖

表2展示了四種算法在三個測試場景上運行20次后獲得的平均Cost值。顯然，MOTA-DQN獲得了最小的Cost值，也表明本文算法的性能最佳。

表2 不同任務規模N的Cost平均值比較

綜上所述，在處理動態MEC網絡下的多目標任務卸載問題上，與MOEA/D、ADTS和DQN相比，本文的MTOA-DQN表現更優，能同時最小化應用完成時間和MD電池能源消耗。

5 結語

任務卸載問題是MEC網絡中的重要研究內容，做卸載決策時的一個關鍵問題是怎樣同時最小化MD的應用完成時間和電池能源消耗。鑒于此，本文建立了基于MEC網絡的多目標任務卸載問題，考慮了MD的移動性和任務間的順序依賴關系；然后，分析應用和MD相關信息，設計MDP模型，并提出了基于DQN的多目標任務卸載算法MTOA-DQN來同時優化所關注的兩個目標。MTOA-DQN算法將一個回合產生的軌跡作為其經驗池中數據的最小單元，該方法能保證數據集的完整性。實驗結果表明，在三種不同任務數規模應用場景下，與MOEA/D、ADTS和原始的DQN相比，MTOA-DQN能獲得最小Cost值，從而能最小化MD的應用完成時間和電池能源消耗，提升用戶體驗質量。

[1] LI L L， LIU Z F， TSENG M L， et al. Enhancing the Lithium-ion battery life predictability using a hybrid method［J］. Applied Soft Computing， 2019， 74： 110-121.

[2] ATAT R， LIU L J， CHEN H， et al. Enabling cyber-physical communication in 5G cellular networks： challenges， spatial spectrum sensing， and cyber-security［J］. IET Cyber-Physical Systems： Theory and Applications， 2017， 2（1）： 49-54.

[3] LI C L， ZHU L Y， TANG H L， et al. Mobile user behavior based topology formation and optimization in ad hoc mobile cloud［J］. Journal of Systems and Software， 2019， 148： 132-147.

[4] NOVAK E， TANG Z F， LI Q. Ultrasound proximity networking on smart mobile devices for IoT applications［J］. IEEE Internet of Things Journal， 2019， 6（1）： 399-409.

[5] MAO Y Y， YOU C S， ZHANG J， et al. A survey on mobile edge computing： the communication perspective［J］. IEEE Communications Surveys and Tutorials， 2017， 19（4）： 2322-2358.

[6] WANG S， ZHANG X， ZHANG Y， et al. A survey on mobile edge networks： convergence of computing， caching and communications［J］. IEEE Access， 2017， 5： 6757-6779.

[7] ABBAS N， ZHANG Y， TAHERKORDI A， et al. Mobile edge computing： a survey［J］. IEEE Internet of Things Journal， 2018， 5（1）： 450-465.

[8] KENESHLOO Y， SHI T， RAMAKRISHNAN N， et al. Deep reinforcement learning for sequence-to-sequence models［J］. IEEE Transactions on Neural Networks and Learning Systems， 2020， 31（7）： 2469-2489.

[9] MNIH V， KAVUKCUOGLU K， SILVER D， et al. Human-level control through deep reinforcement learning［J］. Nature， 2015， 518（7540）： 529-533.

[10] LUONG N C， HOANG D T， GONG S M， et al. Applications of deep reinforcement learning in communications and networking： a survey［J］. IEEE Communications Surveys and Tutorials，2019， 21（4）： 3133-3174.

[11] KIRAN B R， SOBH I， TALPAERT V， et al. Deep reinforcement learning for autonomous driving： a survey［J/OL］. IEEE Transactions on Intelligent Transportation Systems. （2021-01-23）［2022-06-20］. https：//arxiv.org/pdf/2002.00444v2.pdf.

[12] WAN Z Q， JIANG C， FAHAD M， et al. Robot-assisted pedestrian regulation based on deep reinforcement learning［J］. IEEE Transactions on Cybernetics， 2020， 50（4）： 1669-1682.

[13] LIN X， WANG Y Z， XIE Q， et al. Task scheduling with dynamic voltage and frequency scaling for energy minimization in the mobile cloud computing environment［J］. IEEE Transactions on Services Computing， 2015， 8（2）： 175-186.

[14] MAHMOODI S E， UMA R N， SUBBALAKSHMI K P. Optimal joint scheduling and cloud offloading for mobile applications［J］. IEEE Transactions on Cloud Computing， 2019， 7（2）： 301-313.

[15] 周業茂，李忠金，葛季棟，等. 移動云計算中基于延時傳輸的多目標工作流調度［J］. 軟件學報， 2018， 29（11）： 3306-3325.（ZHOU Y M， LI Z J， GE J D， et al. Multi-objective workflow scheduling based on delay transmission in mobile cloud computing［J］. Journal of Software， 2018， 29（11）： 3306-3325.）

[16] SONG F H， XING H L， LUO S X， et al. A multiobjective computation offloading algorithm for mobile-edge computing［J］. IEEE Internet of Things Journal， 2020， 7（9）： 8780-8799.

[17] 楊天，楊軍. 移動邊緣計算中的卸載決策與資源分配策略［J］. 計算機工程， 2021， 47（2）： 19-25.（YANG T， YANG J. Offloading decision and resource allocation strategy in mobile edge computing［J］. Computer Engineering， 2021， 47（2）： 19-25.）

[18] YANG L， ZHONG C Y， YANG Q H， et al. Task offloading for directed acyclic graph applications based on edge computing in Industrial Internet［J］. Information Sciences， 2020， 540： 51-68.

[19] WU Q， WU Z W， ZHUANG Y H， et al. Adaptive DAG tasks scheduling with deep reinforcement learning［C］// Proceedings of the 2018 International Conference on Algorithms and Architectures for Parallel Processing， LNTCS 11335. Cham： Springer， 2018： 477-490.

[20] 詹文翰，王瑾，朱清新，等. 移動邊緣計算中基于深度強化學習的計算卸載調度方法［J］. 計算機應用研究， 2021， 38（1）： 241-245， 263.（ZHAN W H， WANG J， ZHU Q X， et al. Deep reinforcement learning based offloading scheduling in mobile edge computing［J］. Application Research of Computers， 2021， 38（1）： 241-245， 263.）

[21] YAN J， BI S Z， ZHANG Y J A. Offloading and resource allocation with general task graph in mobile edge computing： a deep reinforcement learning approach［J］. IEEE Transactions on Wireless Communications， 2020， 19（8）： 5404-5419.

Multi-objective task offloading algorithm based on deep Q-network

DENG Shiquan1， YE Xuguo2*

（1，，556011，；2，，556011，）

For the Mobile Device （MD） with limited computing resources and battery capacity in Mobile Edge Computing （MEC）， its computing capacity can be enhanced and its energy consumption can be reduced through offloading its own computing-intensive applications to the edge server. However， unreasonable task offloading strategy will bring a bad experience for users since it will increase the application completion time and energy consumption. To overcome above challenge， firstly， a multi-objective task offloading problem model with minimizing the application completion time and energy consumption as optimization targets was built in the dynamic MEC network via analyzing the mobility of the mobile device and the sequential dependencies between tasks. Then， a Markov Decision Process （MDP） model， including state space， action space， and reward function， was designed to solve this problem， and a Multi-Objective Task Offloading Algorithm based on Deep Q-Network （MTOA-DQN） was proposed， which uses a trajectory as the smallest unit of the experience buffer to improve the original DQN. The proposed MTOA-DQN outperforms three comparison algorithms including MultiObjective Evolutionary Algorithm based on Decomposition （MOEA/D）， Adaptive DAG （Directed Acyclic Graph） Tasks Scheduling （ADTS） and original DQN in terms of cumulative reward and cost in a number of test scenarios， verifying the effectiveness and reliability of the algorithm.

Mobile Edge Computing (MEC); task offloading; completion time; energy consumption; Reinforcement Learning (RL)

This work is partially supported by National Natural Science Foundation of China （11961038）， Science and Technology Project of Education Department of Guizhou Province （［2017］333）.

DENG Shiquan， born in 1981， M. S.， associate professor. His research interests include intelligent information processing， edge computing， computational intelligence.

YE Xuguo， born in 1982， Ph. D.， professor. His research interests include time series analysis， financial analysis， computational intelligence.

TP391.9

A

1001-9081（2022）06-1668-07

10.11772/j.issn.1001-9081.2021061367

2021?08?02；

2021?08?15；

2021?09?28。

國家自然科學基金資助項目（11961038）；貴州省教育廳科技項目（［2017］333）。

鄧世權（1981—），男，貴州江口人，副教授，碩士，CCF會員，主要研究方向：智能信息處理、邊緣計算、計算智能；葉緒國（1982—），男，安徽霍邱人，教授，博士，主要研究方向：時間序列分析、金融分析、計算智能。