随着近几年各类智能设备的快速发展和广泛普及，传统以云数据中心为核心的运行模式在单位时间内需要承载的数据量越来越大，其造成的数据阻塞和网络延迟极大影响了用户服务质量.一方面是由于所用的业务数据交互都需要通过核心网进行传输，因此在网络高峰期会对核心网产生很大负载压力；另一方面是根据智能设备与云数据中心两者之间的相对距离产生较大网络延迟，这严重影响了延迟敏感性应用的服务体验[1].针对以上云计算服务模式产生的问题，移动边缘计算(mobile edge computing, MEC)通过在靠近物理实体或数据源头的一侧采用网络、计算、存储和应用核心能力为一体的开放平台就近提供服务，使其应用程序在边缘侧执行，产生更快的网络服务响应，满足行业在实时处理、智能应用、安全和隐私保护等方面的基本需求[2].换言之，MEC的核心思想是将计算资源和缓存资源边缘化和本地化，从而降低网络延迟和缓解带宽压力，这样既满足了智能设备扩展计算能力的需求，同时也弥补了云计算平台传输时延较长的缺点[3].
虽然MEC增强了智能设备的计算能力并且缓解了核心网的网络压力，但是其边缘服务器在单位时间内能够处理的数据是有限的，因此需要设计一种卸载方案决定移动任务是在本地智能设备上执行，还是卸载到远程服务器上执行.目前常见的任务卸载方式主要包括2种：粗粒度任务卸载和细粒度任务卸载.粗粒度任务卸载是指将整个移动终端应用作为卸载对象，并未根据功能再将其划分为多个子任务，这种卸载方法往往未充分考虑MEC边缘服务器的低时延和性能相对有限的特性，同时对MEC边缘服务器的资源利用率较低；细粒度任务卸载是指先将一个移动应用划分为多个具有数据依赖关系的子任务，因为划分后的子任务所需的计算复杂度和数据传输量更少，因此可以将部分或者所有任务卸载到多个远程服务器上进行处理，以此节省计算时间和传输时间，并且对边缘服务器集群的资源利用率更高[4].因此本文将设计一种基于细粒度任务卸载的算法策略，结合深度强化学习构建Markov决策过程(Markov decision processes, MDP)模型，以此解决卸载什么、卸载多少以及卸载到哪里的问题，最终有效减少智能设备和各服务节点的能耗、时延和网络使用量，提高整个MEC平台的资源利用率.
本文通过改进深度强化学习算法来解决MEC中具有大规模服务节点的任务卸载问题，其主要贡献包含3个方面：
1) 构建了大规模异构MEC中具有多服务节点和移动任务内部具有多依赖关系的卸载模型.
2) 结合MEC实际应用场景，利用长短期记忆(long short-term memory, LSTM)和事后经验回放(hindsight experience replay, HER)改进深度强化学习算法，以此优化任务卸载策略.
3) 综合比较任务卸载策略的能耗、费用、负载均衡、延迟、网络使用量和平均执行时间等指标，以此分析各卸载策略的优缺点.
1 相关工作
随着5G技术的日益成熟，MEC的任务卸载问题在近几年得到了广泛关注和研究.其中，文献[5]研究了基于任务卸载决策和通信资源分配的联合优化方案，用于最大程度上降低能耗、通信成本和延迟；文献[6]研究了一种针对计算资源和无线网络资源的多目标卸载决策，以便满足延迟敏感性应用的网络需求，同时在此基础上降低能耗；文献[7]研究了基于计算资源和网络资源的联合优化策略，通过部分计算卸载解决MEC中多用户的延迟最小化问题；文献[8]提出了基于时分多址和正交频分多址的资源调度策略，解决了以最小化能耗为目标的部分计算卸载问题；文献[9]提出移动任务可以根据需求选择MEC中的多个基站进行计算卸载，并在此基础上研究了基于深度强化学习算法的任务卸载策略以最大程度优化长期性能.文献[10]对MEC架构进行了数学建模，通过在网络边缘测量用户设备与MEC服务器的数据包往返时间，对MEC的计算卸载策略进行了优化，决定了何时将用户的计算任务卸载至MEC服务器上进行处理，并通过人脸识别应用验证了该策略的有效性，与移动设备的本地执行相比大幅降低了服务时延、节省了设备的能源消耗.文献[11]研究了MEC卸载场景下的多用户业务时延问题，提出了一种新型的部分计算卸载模型，通过最优数据分割等策略对通信及计算资源的分配进行了优化，并在通信资源远大于计算资源的特定场景下进行了实验验证，与设备的本地执行及边缘云执行相比，所提出的部分卸载策略可以使所有用户设备的加权时延最小，从而提高用户的服务体验质量.目前大多数MEC卸载策略算法研究主要是假设资源需求的先验分布或者基于历史数据来预测资源需求;由于MEC的可用资源都是随着信道质量、任务到达率和能源状态而动态变化的，因此先验概率很难在实际环境中做出准确假设[12];文献[13]在MDP框架中构建了用于降低延迟的任务卸载模型，并提出了一种一维搜索算法来寻找最优解，但该方法的前提是需要预先获得集群环境中信道质量变化以及任务到达的准确统计信息，所以该方法在真实场景中很难具有应用价值；另外目前文献提出利用启发式算法来解决基于历史数据的资源需求问题，文献[14]利用Lyapunov优化方法解决了具有无线能源传输功能的移动设备在动态任务卸载策略方面的研究；文献[15-16]也同样利用了Lyapunov方法对任务卸载的能耗和延迟进行了研究；文献[17]使用线性整数规划以及首次适应和在线优先等启发式算法来优化任务卸载中的延迟和能耗问题.以上研究在利用启发式算法处理大规模任务卸载问题时都会由于问题维度过高导致算法生成决策的时间很长，同时该类算法也只能求出近似最优解，因此其在实际使用中并不能符合预期要求.
基于上述研究，相比于假设先验分布或者启发式算法，深度强化学习通过结合深度学习和强化学习的优势，具有自学习和自适应等特征，需要提供的参数较少，有较好的全局搜索能力，能够解决较复杂、高维度且更加接近实际情况的任务场景.另外为保证算法策略在MEC的任务卸载问题中能够具有更好的泛化性能及更快的收敛速度，本文利用LSTM和HER对深度强化学习算法DQN进行改进：
1) 在MEC真实环境中由于问题复杂性和感知局限性容易导致环境信息产生误差及缺失，造成算法生成的策略缺乏有效性和稳定性，因此结合LSTM是为了解决依赖于时序的任务卸载问题，利用部分观测Markov过程(partially observed Markov decision processes, POMDP)对只有不完全状态信息的系统建模,依据当前的缺失信息做出决策，提高算法的泛化性能；
2) 深度强化学习算法在解决MEC实际问题时由于大部分情况下无法得到有效反馈，其模型很难学习到可用策略，造成求解复杂问题的决策无法收敛，因此结合HER是为了解决因为稀疏奖励导致的收敛速度变慢问题.
相比于传统深度强化学习算法，基于LSTM和HER改进的深度强化学习算法在实用性和收敛性上都有了很大提高，对解决MEC中任务卸载问题提供了更高效鲁棒的算法策略.结合以上分析，本文重点研究了大规模异构MEC中具有多服务节点和移动终端任务内部具有多依赖关系的卸载问题，通过比较能耗、费用、负载、延迟、网络使用量以及平均执行时间等多方面因素来验证基于深度强化学习算法策略的优劣.
2 问题建模
2.1 任务依赖模型
MEC的组成结构通常包含云数据中心层、边缘服务器层以及用户设备层3部分.如图1所示，终端设备层包含各类传感器、电脑和手机等具有一定处理性能的设备；边缘服务器层是按照相对距离对所有边缘服务器进行区域划分，每个区域包含性能适中且异构的边缘服务器；云数据中心层包含大量性能优异的物理服务器，这些服务器组成集群为用户提供服务.当来自移动终端的任务需要卸载时，首先会通过某种切分算法将一个整体的移动应用划分为多个子任务，这些子任务有的是必须在本地执行，比如用户交互任务、设备I
O任务和外围设备接口任务等，还有一些是可在本地执行，也可进行卸载的任务，它们通常都是数据处理型任务，计算量较大.划分后的子任务彼此之间有数据交互，但是又能够独立执行，这是进行细粒度卸载决策的前提条件[18].
Fig. 1 Composition structure diagram of MEC
图1 MEC组成结构图
假如移动应用拆分后的子任务之间具有依赖关系，该关系可以用一个有向图 Loop=(V,E)表示，其中图的每个节点vi∈V表示拆分后的子任务，图的每条边表示任务间的数据依赖，例如eij∈E表示任务vi执行完成后会将数据传输给vj，而vj必须接收该数据后才能继续往后执行[14].如图2所示，一个移动应用拆分后的子任务集合为V={v1,v2,v3,v4,v5}，其中v1和v5必须在本地设备执行，其余子任务可以根据需要进行卸载.同时各子任务之间用有向线条表示其数据依赖，例如v5必须在接受到v2和v4的处理结果后才能继续执行.
Fig. 2 Multi-tasking data dependency diagram
图2 多任务数据依赖图
2.2 问题建模
本文将整个MEC中的所有计算设备用(DC,ES,MP)表示，其中DC(data center)表示具有海量计算资源的云数据中心，其主要由一个物理机集群组成；ES(edge server)表示具有m个边缘服务器的集合{es1,es2,…,esm}；MP(mobile phone)表示具有n个移动终端设备的集合{mp1,mp2,…,mpn}，同时设定每个终端设备在同一时间只能有一个应用发出请求.将每个移动应用拆分后的子任务用一个五元组
描述，其中
表示在第i个移动设备中第j个子任务的输入数据量，如程序代码或者输入参数；
表示同一子任务用于接收数据所能使用的上传带宽；Mij表示该子任务部署所需的计算资源，因为本文的优化目标之一是任务分配后处理产生的总能耗，同时有研究表明主机的功耗与其CPU利用率的相关系数高达0.990 667，因此本文将该值定义为任务部署需要消耗的CPU性能；
表示在第i个移动终端设备中第j个子任务计算产生的数据量；
表示同一子任务用于提供结果下载所能使用的下行带宽.根据以上任务模型产生的卸载决策，本文设计了6种模型来多方面评估其有效性[19]：
1) 能耗模型
针对包含智能手机和远程服务器等所有计算设备在一定时间内产生的总能耗，本文首先定义第i台计算设备的功率模型为
(1)
其中,K表示计算设备在空闲状态所消耗能耗的百分比，
表示第i台计算设备在满负载时所消耗的能耗，u为CPU利用率[20].另外计算设备负载是随时间而不断变化的，现假设u(t)为单位时间内计算设备CPU利用率的变化函数，则从时刻t0开始，一个计算设备在单位时间t内的能耗为
(2)
总数量为1+m+n的所有计算设备在单位时间t内产生的总能耗为
(3)
2) 费用模型
用户获取远程服务器提供的计算资源需要支付相应的费用，本文使用基于资源剩余量的动态价格模型，当资源剩余量越少时资源价格越高，此时用户较倾向于选取单价较低的服务节点作为卸载目标，从而在降低用户花销的同时提高资源利用率.基于计算资源剩余量的动态价格模型：
Cost=Costexist+Timeunit×Priceunit×
Ratioused×Rtotal,
(4)
其中,Costexist表示当前设备已经产生的费用，Timeunit表示费用计算的单位间隔时间，Priceunit表示单位计算资源所设定的价格，Ratioused表示当前设备使用的计算资源比率，Rtotal表示当前设备的总计算资源.同时由于本地设备的计算资源属于用户个人所有，不需要作为运营商提供的服务进行费用计算，因此所有收费设备(数量为1+m)的总开销:
(5)
3) 负载均衡
负载均衡是实现集群中各类资源有效利用和共享的一个重要手段，其主要是为了实现最佳化资源使用、最大化吞吐率、最小化响应时间以及避免过载的目的.集群中所有设备的负载均衡：
(6)
其中,Loadi表示第i个计算设备所有资源的综合负载；index表示用于计算负载均衡的指标数量，如CPU、内存和硬盘等，本文主要考虑计算设备的CPU利用率；λk是各项资源的权重，其满足条件
表示各资源的使用率；Avg为所有计算设备的综合负载均值；LB表示各个计算设备的综合负载均衡值.
4) 服务时延
根据子任务之间的依赖关系，一个移动应用的服务时延是指第1个子任务接收用户请求的时间Timefirst到最后1个子任务获取结果并执行相应操作的时间Timeend之间的差值，其服务时延:
SL=Timeend-Timefirst.
(7)
5) 平均执行时间
执行时间是指一个子任务进行数据处理所需要花费的时间，当子任务卸载的计算设备性能越好，则其处理时间越短，在规定时间内能处理的请求就越多.因此卸载决策需要尽可能降低移动应用的平均执行时间，其中平均执行时间:
(8)
其中,subnum表示一个移动应用拆分后的子任务数量，FTTaski表示第i个子任务结束处理的时间，STTaski表示第i个子任务开始处理的时间，Loop(Taskfirst,Taskend)表示子任务集合形成的有向图.
6) 网络使用量
网络使用量是指所有移动应用在规定时间内产生的数据传输量，该值过高可能导致整个网络产生拥塞，进一步降低应用程序的处理性能.网络使用量：
(9)
其中,appnum表示单位时间内所有请求的移动应用数量，TLi表示第i个移动应用处理请求所产生的延迟，TSi表示第i个移动应用处理请求所产生的总数据传输量，Timeunit表示设定的单位时间.
3 深度强化学习算法设计
强化学习是一种能在特定场景下通过自学做出最优决策的算法模型，其通过把所有现实问题都抽象为智能体与环境的互动过程来进行建模.在互动过程中的每个时间步，智能体都收到环境的状态并选择相应的响应动作，然后在下一个时间步，智能体根据环境的反馈获得一个奖励值和新的状态.强化学习根据获得的奖励不断学习知识以适应环境，其所有智能体的目标都是最大化预期累积奖励或在所有时间步获得的预期奖励之和.虽然强化学习具有很多优势，但同时该方法缺乏可扩展性，并且本质上局限于相当低维的问题.这些限制的存在是因为强化学习算法与其他算法具有相同的内存复杂度、计算复杂度以及机器学习算法中的样本复杂度.
为解决强化学习难以处理的决策问题，深度强化学习将深度学习的感知能力和强化学习的决策能力相结合，依靠强大的函数逼近和深度神经网络的表示学习性质来解决具有高维度状态空间和动作空间的环境问题[21].下面通过结合实际移动计算环境构建MDP模型，并针对深度Q学习网络(deep Q-Learing network, DQN)算法进行改进，以此解决MEC中的任务卸载问题.
3.1 MDP模型
1) 状态空间
为了综合考虑MEC中子任务与服务器资源之间的特性，本文定义在时间步t的状态空间为St=(Cin,Nup,M,Cout,Ndo,U1,U2,…,U2+m).其中，Cin表示当前子任务所需的输入数据量；Nup表示该子任务用于接收数据所能使用的上传带宽；M表示该子任务部署所需的CPU资源；Cout表示当前子任务计算产生的结果数据量；Ndo表示同一子任务用于提供结果下载所能使用的下行带宽；Ui表示在时间步t第i个计算设备的CPU利用率,同时为了保证子任务只能选择在本地移动终端设备或者远程服务器上执行，因此对于该子任务只需考虑2+m个计算设备，其中包含1个云数据中心、1个本地设备和m个边缘服务器.
2) 动作空间
为了将子任务卸载到合适的计算设备上，在深度强化学习中规定动作空间与可用计算设备集合呈对应关系，用
表示第i个子任务是否卸载到第j个计算设备上，例如动作空间Ai=(0,0,1,…,0)说明第i个子任务根据策略被卸载在第3个计算设备上.所以对于包含2+m个计算设备的集群，其动作空间为A=(a1,a2,…,a2+m).
3) 奖励函数
本文将综合考虑MEC中所有设备的能耗、费用以及负载均衡3方面因素来评估卸载决策的优劣，同时为了解决异构计算设备因性能差异在每一个时间步所造成的奖励值偏差，本文利用z-score标准化方法分别对能耗、费用以及负载均衡进行正规化，当数据序列为{x1,x2,…,xnum}时，其计算为
(10)
分别将式(2)(4)(6)与式(10)进行结合可以求出各个计算设备的能耗、费用以及负载均衡正规化值，则奖励函数为
(11)
其中,
分别表示第i个设备的能耗、费用以及负载均衡正规化值；σ,ξ,φ表示3个因素所占的权重，同时σ+ξ+φ=1.另外由于移动终端设备属于用户私有，所以部署在本地设备上的模块不计算费用，因此
表示只计算云数据中心和边缘服务器提供远程服务的总费用.
根据以上构建的MDP模型，结合深度强化学习的MEC任务卸载策略的伪代码如算法1所示：
算法1. 结合深度强化学习的任务卸载算法.
输入：包含一个移动设备、多个边缘服务器和一个云数据中心的集合hostList、所有需要卸载的任务集合taskList;
输出：对任务集合taskList的卸载决策.
① 基于taskList初始化卸载集合offloadList;
② 基于hostList初始化动作空间A;
③ For任务T∈taskList
④ 获取任务T的输入数据量Cin、上传带宽Nup、所需CPU资源M、输出数据量Cout、下行带宽Ndo;
⑤ 获取hostList在时间步t的CPU利用率集合CPUList;
⑥ 构建时间步t的状态空间St;
⑦ 根据状态St选择动作at∈A，其中at表示选择设备h∈hostList;
⑧ If任务T能够放置在设备h上
⑨ 创建键值对
T,h
并将任务T从集合taskList中移除;
⑩ 在offloadList中添加键值对T,h;
Else
在设备h所在的上层网络集群中随机选择设备h′∈hostList;
创建键值对T,h′并将任务T从集合taskList中移除;
在offloadList中添加键值对T,h′;
End If
End For
Return offloadList.
3.2 算法优化
1) LSTM网络
DQN是一种基于值迭代的深度强化学习算法，其目标是估计最优策略的Q值，该算法利用深度神经网络计算近似值函数，把Q-Table的更新问题变成一个函数拟合问题，使其根据相近的状态得到相近的输出动作，以此解决传统Q-Learning算法在高维且连续问题方面的不足.通过更新参数θ使
函数的计算结果逼近Q值：
(12)
其中,st+1表示状态st在时间步t采取动作at后的下一状态，rt+1是采取动作at后的即时奖励，而a′为状态st+1能够采取的所有动作；γ为价值累积过程中的折扣系数，决定了未来回报相对于当前回报的重要程度；α为学习速率，该值越大，则保留之前训练的效果就越少.
DQN不仅利用函数拟合改进了Q-Learning算法的搜索速度，同时还通过增加经验池和目标网络提升了其多样性和稳定性.其中经验池是将每个时间步智能体与环境交互得到的转移样本(st,at,rt,st+1)储存到回放记忆单元，当进行训练时随机抽取一定数量的样本来解决数据之间的相关性及非静态分布问题；目标网络是指使用另一个网络TargetNet生成训练过程的目标Q值，该网络的结构与DQN的神经网络MainNet保持一致，每经过C轮迭代，将MainNet的参数复制给TargetNet.因此通过在一段时间内保持2个网络参数的差异性，以此利用当前Q值和目标Q值的差值来计算损失函数，随后使用随机梯度下降等方法反向更新MainNet网络的参数.DQN算法的损失函数计算为
(13)
其中,
表示当前网络MainNet的输出，用来计算当前状态动作对的Q值；
表示目标网络TargetNet的输出，用来计算采取所有可能动作后的目标Q值.
在MEC的真实环境中，由于问题的复杂性和感知的局限性,系统很难直接获取到当前时间步所处的精确状态.假设系统的状态信息不能直接观测得到,是部分可知的，因而通常需要使用POMDP对只有不完全状态信息的系统建模,依据当前的不完全状态信息做出决策[22].POMDP可以用一个六元组(S,A,T,R,Z,O)描述.其中，S表示系统所处环境的状态集合，其都是部分可观测的；A表示动作的有限集合；Z表示观测值的有限集合；T:S×A→π(S)是状态转移函数；R:S×A→R是奖励函数；O:S×A→π(Z)是状态和系统所做动作给出的观测函数.通常情况下，DQN只能在观测值z∈Z能够很好地反映真实环境状态s∈S的情况下才能取得较好结果，因此其很难直接用于解决实际的MEC问题.
鉴于MEC中资源随时间逐步进行变化，以及LSTM网络对于长时间状态的记忆能力，本文提出将LSTM与DQN相结合用来处理依赖于时序的实际MEC问题.通过将DQN网络的1个全连接层替换为LSTM层，利用循环结构使其能够整合长时间的历史数据，以更好地估计当前状态.如图3所示，改进后的DRQN算法获取当前时间步的观察状态zt以及动作at组成状态动作对，将其与LSTM中的输出值进行整合可以推导出真实环境状态st，随后导入深度神经网络进行训练.因此相比较于DQN算法使用的
更倾向于使用
来进行函数拟合，其中ht表示LSTM层在当前时间步的输出值，其迭代为
ht+1=LSTM(ht,zt,at).
(14)
Fig. 3 DRQN algorithm training flow chart of MainNet
图3 DRQN算法MainNet训练流程图
2) 事后经验回放
为提高深度强化学习算法的泛化性能，DQN算法通过经验回放对样本数据进行存储，随后利用随机采样更新深度神经网络参数，以此实现数据之间的独立同分布以及降低其关联性，解决了经验数据的相关性和非平稳分布问题，提高了数据利用率并且降低了更新网络参数产生的方差.深度强化学习在解决实际问题时由于大部分情况下无法得到有效反馈，其模型很难学习到可用策略，造成求解复杂问题的决策无法收敛.因此本文希望在经验回放的基础上结合后见之明的思想，提出利用事后经验回放解决MEC中无法获取有效反馈的问题.
HER是用来解决反馈奖励稀疏的一种样本数据存储结构，其通过渐进式学习方法调整任务目标以此提高模型的策略探索能力[23].现假设智能体将经历从初始状态s0到达目标状态g的学习过程，但最终在学习结束时其终止状态为g′，则生成的真实学习轨迹可以表示为
{(s0,g,a0,r0,s1),(s1,g,a1,r1,s2),…,
(sn,g,an,rn,g′)},
其中,an表示智能体在时间步n时采取的动作，rn表示智能体在时间步n时获取的奖励.基于以上假设，HER将目标状态g替换成终止状态g′，以此表示智能体在该学习过程中达成目标并获取到有效反馈，其生成的想象学习轨迹可以表示为
{(s0,g′,a0,r0,s1),(s1,g′,a1,r1,s2),…,
(sn,g′,an,rn,g′)}.
因为每次迭代过程中模型的学习目标都是不同的，因此所选取的动作也将发生变化，则在时间步t时根据当前状态st和目标状态g得到的动作计算为
at=π(st,g).
(15)
相应的即时奖励计算为
rt=Reward(st,at,g).
(16)
最后将根据目标状态g计算得到的经验存入经验池中，其中基于HER的每一条经验将由5部分元素组成：当前状态s、动作a、及时奖励r、下一状态s′、当前目标g.同时在训练过程中，基于HER的经验回放可以通过目标采样策略生成想象目标g′，并结合状态st和动作at来计算新的奖励并将其存入到经验池中，以此生成一些额外的训练经验，其计算为
r′=Reward(st,at,g′),
(17)
其中本文采用的目标采样策略为future，即对时间步t以后的状态进行随机采样，选取k个状态作为新的想象目标集合.HER充分利用了人类从失败经历中获取有用经验的思想，通过想象轨迹在学习过程中达成想象目标而获取有效奖励，以此保证生成的任何策略都能利用反馈奖励进行学习.其中智能体首先在靠近初始状态的较小区域到达想象目标状态，随后逐渐向周围区域进行探索，利用渐进式学习满足难度逐渐增加的任务目标，最终使模型学习到实际目标状态.基于HER的训练过程代码如算法2所示：
算法2. 基于HER的深度强化学习.
输入：用于目标重采样的策略RSample、奖励函数Reward().
① 初始化回放空间D;
② For迭代次数episode=1,2,…,M
③ 对目标g和初始状态s0进行抽样;
④ For迭代次数t=0,1,…,T-1
⑤ 利用式(15)选择动作at；
⑥ 执行动作at然后获得新状态st+1；
⑦ End For
⑧ For迭代次数t=0,1,…,T-1
⑨ 利用式(16)计算即时奖励rt;
⑩ 将转移样本(st,at,rt,st+1,g)存入D;
利用策略RSample抽样一组额外目标G;
For g′∈G
利用式(17)和目标g′计算奖励r′;
将转移样本(st,at,r′,st+1,g′)存入D;
End For
End For
从回放空间D中对转移样本进行采样;
计算损失函数并更新网络参数;
End For
3.3 算法流程
Fig. 4 HERDRQN algorithm flow chart
图4 HERDRQN算法流程图
图4是基于LSTM和HER改进的深度强化学习算法HERDRQN流程图.该算法首先将每个时间步智能体与环境交互得到的转移样本(zt,at,rt,zt+1)储存到HER记忆单元，随后在训练过程中利用future策略对样本进行随机采样，将其进行拆分后分别用于训练当前值网络和目标值网络的权重，其中这2个网络的结构一致，都是由一个单隐层的LSTM网络和2个全连接层组成，其中最后一个全连接层的节点数为动作空间大小.为保证在MEC真实环境中获取到更精确的状态，当前值网络和目标值网络通过LSTM网络的长时间序列观测值对当前时间步的状态st和下一时间步的状态st+1进行推导，然后利用全连接层分别求出2个网络对应状态的Q值，根据式(13)求出误差并计算梯度反向更新当前值网络的权重.另外基于LSTM改进的DRQN算法流程与HERDRQN算法流程在网络结构上是一致的，区别在于两者采用的记忆单元方法存在不同，其中DRQN算法使用的是回放记忆单元，而HERDRQN算法使用的是事后经验回放单元.
图5是基于HER改进的深度强化学习算法HERDQN流程图.与HERDRQN算法的流程相比，HERDQN算法的差异在于当前值网络和目标值网络使用的是3个全连接层，其将LSTM层替换为一个具有256个节点的全连接层，同时当前环境的观测值被直接作为状态进行训练，因此该算法在状态信息只能部分可知的情况下表现相对较差.另外与DRQN算法和HERDRQN算法的差异类似，DQN算法与HERDQN算法的网络结构都是3个全连接层，但DQN算法使用的是回放记忆单元，HERDQN算法使用的是事后经验回放单元.
Fig. 5 HERDQN algorithm flow chart
图5 HERDQN算法流程图
4 MEC任务卸载仿真实验
4.1 仿真环境
本文采用iFogSim对基于MEC的任务卸载问题进行仿真实验[24]，通过比较各算法在大规模异构集群中的能耗、费用、负载均衡、服务时延、平均执行时间以及网络使用量等来反映卸载决策的优劣，其中实现的算法包括基于本地设备优先放置的策略Mobile、基于边缘服务器优先放置的策略Edge、基于深度强化学习的策略DQN、基于LSTM改进的深度强化学习策略DRQN、基于HER改进的深度强化学习策略HERDQN以及基于LSTM和HER改进的深度强化学习策略HERDRQN.仿真实验模拟的设备集群主要包含1个云数据中心、60个边缘服务器和数量不等的移动终端设备，其中所有边缘服务器将平均划分到10个不同的区域，并且每个移动终端设备在同一时间内只能发送一个应用卸载请求.本文参考SPEC(standard performance evaluation corporation)设置了相应的仿真设备配置及平均性能功耗比，该值越大表明设备在相同性能下能耗越少，其详细信息如表1所示.
为了模拟移动应用拆分成不同子任务后的卸载流程，本文根据参考文献[25]构建了一个网络购物的子任务依赖关系，如图6所示，该应用主要是由edge,front end,login,accounts,orders,shipping,catalogue,cart和payment等子任务组成，其中edge必须在移动设备上执行，而其余子任务则可以根据决策选择是否卸载.网络购物应用通常对卸载决策的要求非常高，其一方面需要将高计算量的数据处理模块卸载到远程服务器上执行，尽可能降低移动设备能耗；另一方面计算模块需要尽可能靠近数据源，以此降低模块之间数据传输所造成的延迟.如表2所示，本文通过CPU Length和NW Length这2个变量来表示任务依赖对计算复杂度和数据传输量的要求，当CPU Length越大并且NW Length越小时，则表示该任务更偏向于高计算量需求，反之则偏向于数据传输需求.同时本文对于所有深度强化学习算法模型的参数进行统一设置以确保训练结果的公平性，其中定义深度强化学习的记忆空间大小M=100 000，优化算法SGD的学习速率α=0.005，批学习大小BatchSize=32，目标网络参数的更新周期C=50，折扣系数γ=0.9；对于基于LSTM改进的深度强化学习算法，设置其LSTM网络层的时间窗口为10；对于基于HER改进的深度强化学习算法，其将型号为DL360 Gen10的边缘服务器目标利用率设置为100%，因为该设备在所有边缘服务器中的平均性能功耗比最大，而其余设备的目标利用率设置为0%，以此组成的所有设备利用率数组作为初始状态.
Table 1 Detailed Configuration Table of Computing Devices
表1 计算设备详细配置表
ModelDeviceTypeCPUFrequency∕MHzCoresMemorySize∕GBAverage Performance to PowerRatio∕Performance per PowerUnit Price∕CNY per MinuteRX4770 M4Cloud Datacenter2100112192128280.05RX350 S7Edge Server2200162450350.01DL325 Gen10Edge Server20003212880830.01DL360 Gen10Edge Server25002848115500.01TX120Local Device2666244540TX150 S5Local Device2666243560TX150 S6Local Device2400486670
Fig. 6 Subtask dependence graph for online shopping
图6 网络购物子任务依赖图
Table 2 Characteristic Table of Subtasks
表2 子任务特征表
Tuple TypeCPU LengthN∕W LengthREQUEST30001000BROWSE10001000LOG_B300100IDENTIFY500500LOG_U300100SELECT1000500BUY50001000SEE500500ADD500200PAY500500SEND5001000LOG_O300100
4.2 实验结果分析
为了反映移动应用在不同时间段的资源利用率变化情况，本文使用Google Cluster Trace数据集来模拟各模块利用率随时间所发生的变化[26].另外为了保证各深度强化学习算法生成的策略高效可用，本文首先从Google数据集中选择1 000个应用来对各神经网络进行训练，随后选取其他数据对训练后的网络模型进行检验，以此比较各策略的泛用性和高效性.
Fig. 7 Resource loss graph generated by each algorithm in task offloading
图7 各算法在任务卸载中所产生的资源损耗图
图7是各算法在任务卸载中所产生的资源损耗图.由图可知随着应用数量的增长，各算法所生成的卸载策略在能耗、费用、负载均衡、延迟、网络使用量以及执行时间等方面大致呈递增关系，其中基于Mobile算法的卸载策略在费用和延迟上都能取得很好的效果，而在其余方面则表现较差，这主要是因为Mobile算法是将子任务优先卸载到本地设备上执行，当资源不足后再逐步向上层设备卸载，因此该算法在网络层面具有更低的延迟；另外由于本地设备属于用户个人所有，处理任务时不需要支付相应的计算费用，因此该算法产生的费用很低.同时根据表1中的数据可知移动设备的处理能力和平均性能功耗都要远小于远程服务器，所以移动设备处理子任务会产生更高的执行时间和能耗；另外基于Edge算法的卸载策略在负载均衡方面表现较好，在其余方面则表现一般，主要原因是Edge算法将子任务优先卸载到边缘服务器集群中，这造成所有边缘服务器的资源利用率都能维持在一个很高的水平，使其负载均衡的计算结果最低.
DQN算法、DRQN算法、HERDQN算法和HERDRQN算法都是利用深度强化学习自动从数据中生成相应的卸载策略，由图7中的结果可知随着应用数量的增长，DQN算法和DRQN算法生成的卸载策略在网络使用量方面表现较优，在其余方面则表现一般，但是DRQN算法在综合性能上要优于DQN算法.当应用数量较多时，HERDQN算法和HERDRQN算法生成的策略在能耗、费用、负载和延迟上都要优于DQN算法和DRQN算法，其中HERDRQN算法的结果是所有深度强化学习算法中表现最好的.
为验证异构设备中CPU利用率与不同资源损耗之间的关系，本文利用各算法生成的决策对120个应用进行卸载处理，根据表1中各设备类型的平均性能功耗比分析异构设备在不同CPU利用率下的数量分布对资源损耗的影响.表3是各算法根据CPU利用率对异构设备进行分类的详细数据，由表3可知当CPU利用率在[80%,100%]的范围时，HERDRQN算法所生成的策略倾向于将子任务卸载到型号为DL360 Gen10的边缘服务器设备，同时对于型号为RX350 S7和DL325 Gen10的边缘服务器设备则是所有深度强化学习算法中使用最少的.
Table 3 Number Distribution Table of Heterogeneous Devices with Different CPU Utilization Rates
表3 各算法在不同CPU利用率下的异构设备数量分布表
ModelCPU Utilization∕%MobileEdgeDQNDRQNHERDQNHERDRQNRX4770 M4 [80,100]000000RX350 S7 [80,100]065331DL325 Gen10 [80,100]617784DL360 Gen10[80,100]7077710TX120[80,100]2400000TX150 S5[80,100]2400000TX150 S6[80,100]2400003RX4770 M4(20,80)000000RX350 S7(20,80)16100000DL325 Gen10(20,80)091105DL360 Gen10(20,80)0100114TX120(20,80)000100TX150 S5(20,80)200108TX150 S6(20,80)300107RX4770 M4[0,20]111111RX350 S7[0,20]4415171719DL325 Gen10[0,20]141012121211DL360 Gen10[0,20]13101312126TX120[0,20]164040394040TX150 S5[0,20]144040394032TX150 S6[0,20]134040394030
由表1可知在相同功耗下，DL360 Gen10和RX350 S7分别是性能最好和最差的边缘服务器型号，同时该算法也将部分子任务卸载到平均性能功耗比很低但资费为0的本地设备，因此HERDRQN算法在能耗、费用、负载和延迟等方面都具有很好的性能.除此之外，结合表3和表4可知：由于Mobile算法对移动设备的CPU利用率很高，因此其卸载决策产生的费用最低但能耗最高；Edge算法将所有子任务均匀卸载到所有边缘服务器上，因此其卸载决策对边缘服务器的CPU利用率都保持在20%～80%之间，保证了负载均衡的性能；相比于DQN算法，DRQN算法和HERDQN算法在CPU利用率为[80%,100%]时对平均性能功耗比最低的边缘服务器使用较少，因此这2种算法在能耗方面都要优于DQN算法.
Table 4 Total Number Table of Heterogeneous Devices
with Different CPU Utilization Rates
表4 各算法在不同CPU利用率下的异构设备总数量表
AlgorithmCPU Utilization∕%[80,100](20,80)[0,20]Total Numberof DevicesMobile852175181Edge729145181DQN191161181DRQN175159181HERDQN181162181HERDRQN1824139181
4.3 实机验证实验
该部分实验主要用于验证各算法在实际MEC卸载任务中的性能表现.整个测试平台共使用3台服务器和2台笔记本电脑用于实验模拟，其中2台服务器用于模拟不同地理位置的边缘服务节点，1台服务器用于模拟云数据中心，而2台笔记本电脑则用于模拟用户的移动设备.所有服务器均采用Ubuntu 16.04.6 LTS操作系统、型号为Intel Xeon E5-2660的16核处理器、2张千兆网卡和32 GB内存、并且都安装了Docker 18.09.2，CRIU(CheckpointRestore In Userspace) 3.10，sysstat 12.1.1.
Fig. 8 Energy consumption comparison chart of each algorithm in test environment
图8 各算法在测试环境中的能耗比较图
CRIU是用于实现checkpointrestore功能的工具软件，它通过冻结运行的应用程序并将其执行状态以快照的形式保存到磁盘上，因此借助该软件可以实现应用程序的卸载；sysstat提供了Linux系统的性能监控功能，它可以用于统计CPU的资源利用率，以此计算服务器设备的能耗和费用等信息，其中各类型设备的单价与表1保持一致.同时为了模拟不同用户应用的动态资源变化，本实验使用容器技术构建了一定数量的多种Web应用：使用静态页面的网站、使用SQLite3数据库的动态网站和使用MySQL数据库的动态网站，并且利用webbench网站压力测试工具模拟用户对网站的连续请求操作.除此之外，为了测试用户地理位置对任务卸载策略的影响，本实验使用EUA数据集来模拟用户的位置变化，利用Linux traffic control工具模拟因相对距离导致的传输延迟[27].图8～10是各算法在该测试环境下能耗、费用和延迟等指标的性能表现.由图可知，各算法的实机实验结果与模拟实验结果基本一样，最终HERDRQN算法在能耗方面表现最佳，在费用和延迟方面也超过了大部分算法，因此其综合性能是所有算法中最好的.
Fig. 9 Cost comparison chart of each algorithm in test environment
图9 各算法在测试环境中的费用比较图
Fig. 10 Delay comparison chart of each algorithm in test environment
图10 各算法在测试环境中的延迟比较图
5 结 论
本文首先提出利用深度强化学习解决大规模异构MEC中具有多服务节点和移动终端任务内部具有多依赖关系的卸载问题，然后将各算法生成的卸载策略在边缘计算仿真平台iFogSim上进行实验，最后通过比较能耗、费用、负载、延迟、网络使用量以及平均执行时间等多方面因素来验证各算法策略的优劣.根据比较各算法的多方面结果可知，基于LSTM网络和HER改进的HERDRQN算法在能耗、费用、负载均衡和延迟等方面都具有很好的结果.另外本文利用各算法策略对一定数量的应用进行卸载，通过比较不同CPU利用率下的异构设备数量分布来验证其与各资源损耗之间的关系，以此证明HERDRQN算法生成的策略在解决MEC任务卸载问题中的科学性和有效性.
[1]Zhao Ziming, Liu Fang, Cai Zhiping, et al. Edge Computing: Platforms, Applications and Callenges[J]. Journal of Computer Research and Development, 2018, 55(2): 327-337 (in Chinese)(赵梓铭, 刘芳, 蔡志平, 等. 边缘计算: 平台、应用与挑战[J]. 计算机研究与发展, 2018, 55(2): 327-337)
[2]Skarlat O, Nardelli M, Schulte S, et al. Optimized IoT service placement in the fog[J]. Service Oriented Computing and Applications, 2017, 11(4): 427-443
[3]Zi Zishu, Xie Renchao, Sun Li, et al. A survey of mobile edge computing[J]. Telecommunication Science, 2018, 34(1): 87-101 (in Chinese)(李子姝, 谢人超, 孙礼, 等. 移动边缘计算综述[J]. 电信科学, 2018, 34(1): 87-101)
[4]Liu Liqing, Chang Zheng, Guo Xijuan, et al. Multiobjective optimization for computation offloading in fog computing[J]. IEEE Internet of Things Journal, 2017, 5(1): 283-294
[5]Chen M, Liang Ben, Dong Min. Joint offloading decision and resource allocation for multi-user multi-task mobile cloud[C] 
Proc of 2016 IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2016
[6]Munoz O, Pascual-Iserte A, Vidal J. Optimization of radio and computational resources for energy efficiency in latency-constrained application offloading[J]. IEEE Transactions on Vehicular Technology, 2014, 64(10): 4738-4755
[7]Ren Jinke, Yu Guanding, Cai Yunlong, et al. Latency optimization for resource allocation in mobile-edge computation offloading[J]. IEEE Transactions on Wireless Communications, 2018, 17(8): 5506-5519
[8]You Changsheng, Huang Kaibin, Chae H, et al. Energy-efficient resource allocation for mobile-edge computation offloading[J]. IEEE Transactions on Wireless Communications, 2016, 16(3): 1397-1411
[9]He Yin, Zhang Zheng, Yu F R, et al. Deep reinforcement learning-based optimization for cache-enabled opportunistic interference alignment wireless networks[J]. IEEE Transactions on Vehicular Technology, 2017, 66(11): 10433-10445
[10]Messaoudi F, Ksentini A, Bertin P. On using edge computing for computation offloading in mobile network[C] Proc of 2017 IEEE Global Communications Conf. Piscataway, NJ: IEEE, 2017
[11]Ren Jinke, Yu Guanding, Cai Yunlong, et al. Partial offloading for latency minimization in mobile-edge computing[C] Proc of 2017 IEEE Global Communications Conf. Piscataway, NJ: IEEE, 2017
[12]Han Zhenhua, Tan Haisheng, Chen Guigai, et al. Dynamic virtual machine management via approximate Markov decision process[C] Proc of the 35th Annual IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2016
[13]Liu Juan, Mao Yuyi, Zhang Jun, et al. Delay-optimal computation task scheduling for mobile-edge computing systems[C] Proc of 2016 IEEE Int Symp on Information Theory. New York: IEEE, 2016: 1451-1455
[14]Mao Yuyi, Zhang Jun, Letaief K B. Dynamic computation offloading for mobile-edge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(12): 3590-3605
[15]Liu Chenfeng, Bennis M, Poor H V. Latency and reliability-aware task offloading and resource allocation for mobile edge computing[C] Proc of 2017 IEEE Globecom Workshops. New York: IEEE, 2017
[16]Jiang Zhefeng, Mao Shiwen. Energy delay tradeoff in cloud offloading for multi-core mobile devices[J]. IEEE Access, 2015, 3: 2306-2316
[17]Chen Weiwei, Wang Dong, Li Keqin. Multi-user multi-task computation offloading in green mobile edge cloud computing[J]. IEEE Transactions on Services Computing, 2019, 12(5): 726-738
[18]Huang C, Chiang M S, Dao D T, et al. V2V data offloading for cellular network based on the software defined network (SDN) inside mobile edge computing (MEC) architecture[J]. IEEE Access, 2018, 6(99): 17741-17755
[19]Lu Haifeng, Gu Chunhua, Luo Fei, et al. Optimization of lightweight task offloading strategy for mobile edge computing based on deep reinforcement learning[J]. Future Generation Computer Systems, 2020, 102: 847-861
[20]Wang Feng, Xu Jie, Wang Xin, et al. Joint offloading and computing optimization in wireless powered mobile-edge computing systems[J]. IEEE Transactions on Wireless Communications, 2018, 17(3): 1784-1797
[21]Wang Chenmeng, Liang Chengchao, Yu F R, et al. Computation offloading and resource allocation in wireless cellular networks with mobile edge computing[J]. IEEE Transactions on Wireless Communications, 2017, 16(8): 4924-4938
[22]Zhao Tiancheng, Eskenazi M. Towards end-to-end learning for dialog state tracking and management using deep reinforcement learning[J]. arXiv preprint, arXiv:1606.02560, 2016
[23]Andrychowicz M, Wolski F, Ray A, et al. Hindsight experience replay[C] Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2017: 5048-5058
[24]Gupta H, Dastjerdi V A, Ghosh S, et al. iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of things, edge and fog computing environments[J]. Software: Practice and Experience, 2017, 47(9): 1275-1296
[25]Guerrero C, Lera I, Juiz C. A lightweight decentralized service placement policy for performance optimization in fog computing[J]. Journal of Ambient Intelligence and Humanized Computing, 2019,10(6): 2435-2452
[26]Xu Jie, Chen Lixing, Ren Shaolei. Online learning for offloading and autoscaling in energy harvesting mobile edge computing[J]. IEEE Transactions on Cognitive Communications and Networking, 2017, 3(3): 361-373
[27]Lai P, He Qiang, Abdelrazek M, et al. Optimal edge user allocation in edge computing with variable sized vector bin packing[C] Proc of the 16th Int Conf on Service-Oriented Computing. Berlin: Springer, 2018: 230-245
