基于深度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—），男，安徽霍邱人，教授，博士，主要研究方向：时间序列分析、金融分析、计算智能。