基于改进深度强化学习的边缘计算服务卸载算法_曹腾飞.pdf

2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1543-1550ISSN 1001-9081CODEN JYIIDUhttp：/基于改进深度强化学习的边缘计算服务卸载算法曹腾飞*，刘延亮，王晓英（青海大学 计算机技术与应用系，西宁 810016）（通信作者电子邮箱）摘要：在边缘计算（EC）网络中，针对边缘节点计算资源和存储空间有限的问题，提出一种基于改进深度强化学习（DRL）的边缘计算服务卸载（ECSO）算法，以降低节点处理时延和提高服务性能。具体来说，将边缘节点服务卸载问题转化为资源受限的马尔可夫决策过程（MDP），利用DRL算法解决边缘节点的请求状态转移概率难以精确预测的问题；考虑到边缘节点执行缓存服务的状态动作空间过大，定义新的动作行为替代原有动作，并依据提出的动作筛选算法得到最优动作集合，以改进计算动作行为奖励值的过程，进而大幅度降低动作空间大小，提高算法训练的效率以及收益。仿真实验结果表明，对比原深度Q网络（DQN）算法、邻近策略优化（PPO）算法以及传统的最流行（MP）算法，ECSO 算法的总奖励值分别提升了 7.0%、12.7%和 65.6%，边缘节点服务卸载时延分别降低了 13.0%、18.8%和66.4%，验证了算法的有效性，说明ECSO能有效提升边缘计算服务的卸载性能。关键词：边缘计算；缓存服务；服务卸载；深度强化学习；动作行为奖励中图分类号：TP393；TP183 文献标志码：AEdge computing and service offloading algorithm based on improved deep reinforcement learningCAO Tengfei*，LIU Yanliang，WANG Xiaoying（Department of Computer Technology and Applications，Qinghai University，Xining Qinghai 810016，China）Abstract:To solve the problem of limited computing resources and storage space of edge nodes in the Edge Computing（EC）network，an Edge Computing and Service Offloading（ECSO）algorithm based on improved Deep Reinforcement Learning（DRL）was proposed to reduce node processing latency and improve service performance.Specifically，the problem of edge node service offloading was formulated as a resource-constrained Markov Decision Process（MDP）.Due to the difficulty of predicting the request state transfer probability of the edge node accurately，DRL algorithm was used to solve the problem.Considering that the state action space of edge node for caching services is too large，by defining new action behaviors to replace the original actions，the optimal action set was obtained according to the proposed action selection algorithm，so that the process of calculating the action behavior reward was improved，thereby reducing the size of the action space greatly，and improving the training efficiency and reward of the algorithm.Simulation results show that compared with the original Deep Q-Network（DQN）algorithm，Proximal Policy Optimization（PPO）algorithm and traditional Most Popular（MP）algorithm，the total reward value of the proposed ECSO algorithm is increased by 7.0%，12.7%and 65.6%，respectively，and the latency of edge node service offloading is reduced by 13.0%，18.8%and 66.4%，respectively，which verifies the effectiveness of the proposed ECSO algorithm and shows that the ECSO can effectively improve the offloading performance of edge computing services.Key words:Edge Computing(EC);caching service;service offloading;Deep Reinforcement Learning(DRL);action behavior reward0 引言 随着互联网与无线通信技术的发展，现代信息社会逐渐迈入了万物互联的物联网时代1。以超高清视频、虚拟现实（Virtual Reality，VR）、自动驾驶等为代表的各类新兴移动互联网业务大量涌现。根据中国互联网信息中心（China Internet Network Information Center，CNNIC）发布的 第 48 次中国互联网发展状况统计报告，截至2021年6月，我国网民规模达 10.11 亿，较 2020 年 12 月增长 2 175 万，互联网普及率达71.6%，较2020年12月提升1.2个百分点2。随着用户数大幅增长，人们对于网络多媒体资源的需求也迅速增长：我国网络视频用户规模达9.44亿，较2020年12月增长1 707万。这些数字表明人们对于计算型多媒体资源的需求增多，由于云端服务器通常远离用户侧，用户从中获取计算后的数文章编号：1001-9081（2023）05-1543-08DOI：10.11772/j.issn.1001-9081.2022050724收稿日期：2022-05-19；修回日期：2022-06-25；录用日期：2022-06-27。基金项目：国家自然科学基金资助项目（62101299，62162053）；青海省自然科学基金资助项目（2020-ZJ-943Q）。作者简介：曹腾飞（1987），男，湖北钟祥人，副教授，博士，CCF高级会员，主要研究方向：B5G网络中的边缘计算；刘延亮（2002），男，湖南衡阳人，硕士研究生，湖南衡阳人，主要研究方向：边缘计算、强化学习；王晓英（1982），女，吉林大安人，教授，博士生导师，博士，主要研究方向：计算机网络体系结构、移动计算。第 43 卷计算机应用据往往会导致较高的时延，仅依靠云服务的计算方式无法有效响应如此庞大的资源需求。因此，也诞生了一种新的计算模型边缘计算（Edge Computing，EC）3。通过将服务资源从云端迁移到边缘节点上，EC 可以有效降低时延，这使EC 成为提升计算型服务质量（Quality of Service，QoS）的一种重要方法。然而，由于当前边缘节点资源有限，通常不能在同一时隙内向区域内的所有用户提供服务，进而不能同时满足用户对于低时延的要求。因此，将云与边缘节点结合进行计算成了当前主要的研究方向。然而，由于边缘节点的资源有限，位于云端的计算型服务不能全部转移到边缘节点上，边缘节点需要自行决定应该从云端卸载哪些服务，而如何提高卸载服务效率来满足低时延的要求成了当前面临的问题。相关研究者针对此类问题进行了分析4-9，但这些工作只考虑了边缘节点有限的计算资源，却未考虑到边缘节点中存储容量有限的问题，因为资源和服务需要占据实际空间，许多计算型服务需要缓存所需服务资源至边缘节点以满足用户的需求。例如，自适应视频流（Dynamic Adaptive Streaming over HTTP，DASH）10中，视频文件以多个视频块的形式存储在云端或边缘节点中，每个块以不同的码率编码，DASH 作为计算型多媒体服务，需要设计算法提升用户的体验质量（Quality of Experience，QoE）。在 DASH 中使用由客户端实现的码率自适应技术（Adaptive Bitrate Streaming，ABR）算法11，将网络吞吐量等信息作为输入，输出下一视频块码率级别，视频服务应根据用户所处的网络环境从边缘节点缓存中获取合适码率的视频块提供给用户。另外，由于边缘节点存储资源有限，当大量用户从边缘节点请求流媒体服务时，将导致边缘节点的计算与存储资源负载过大等问题，因此需要同时考虑以上两者的约束条件，提升EC的服务卸载效率。近几年，深度强化学习（Deep Reinforcement Learning，DRL）12算法被广泛使用。DRL算法具有诸多优势，它能从训练的经验中学习并预测最佳行为，而且能适应不同的网络环境。最具代表性的深度强化学习算法为深度 Q 学习13。尽管已经有将深度 Q 学习应用到 EC 的相关工作14-15，但仍无法解决因动作空间过大以及存在非法动作导致的模型总体收益降低等问题。本文将计算型服务卸载问题建模为马尔可夫决策过程（Markov Decision Process，MDP），在实现深度Q网络（Deep Q-Network，DQN）16算法的基础上降低算法的动作空间大小，并提出了基于改进深度强化学习的边缘计算服务卸载（Edge Computing and Service Offloading，ECSO）算法。本文主要工作如下：1）将边缘计算服务卸载问题建模为存储空间以及计算资源限制的 MDP，同时将算法在边缘计算服务卸载中节省的时间消耗视为奖励。但由于本问题中的概率转移矩阵在实际情况下难以实现，需要进一步在 MDP 基础上实现深度强化学习算法。2）提出了基于改进深度强化学习的 ECSO 算法。相较于原DQN算法，本文提出了一种新的动作行为，规避了非法动作，优化了动作空间的大小，进而提升了算法的训练效率；同时，本文运用动态规划的思想提出了动作筛选算法，针对单一服务的动作进行筛选与组合，以便得到理论收益最大的最优动作集；并通过本文提出的动作筛选算法得到最优动作集，进而通过比例的方式梯度下降更新网络参数，优化算法决策。3）将 ECSO 算法分别与 DQN、邻近策略优化（Proximal Policy Optimization，PPO）17以 及 最 流 行（Most Popular，MP）18算法进行仿真实验对比。结果表明本文ECSO算法能显著降低边缘计算处理时延，相较于 DQN、PPO 以及 MP 算法，ECSO的算法奖励值分别提升了7.0%、12.7%和65.6%，边缘计算传输时延分别降低了13.0%、18.8%和66.4%。1 相关工作 边缘计算服务卸载作为边缘计算的一个重要领域，近年来被人们广泛关注。部分研究者将这类问题视为 MDP，利用最优化方法进行求解。文献 4 中提出了一个由用户和网络 运 营 商 联 合 通 信 计 算（Joint Communication Computing，JCC）资源分配机制组成的综合框架，在提供优质通信的同时最小化资源占用；文献 5 中提出了一种用于分配资源的框架，该框架结合了通信以及计算要素来解决移动边缘云计算服务的按需供应问题；文献 6 中提出了一种基于强化学习 的 状 态/动 作/奖 励/状 态/动 作（State-Action-Reward-State-Action，SARSA）算法，以解决边缘服务器中的资源管理问题，降低系统成本，并作出最佳的卸载决策；文献 7 中探究了 DQN 及 PPO 算法在基于多输入多输出（Multiple-Input Multiple-Output，MIMO）的 移 动 边 缘 计 算（Mobile Edge Computing，MEC）系统中的计算型服务卸载问题，目标是在随机系统环境下最大限度地降低移动设备的功耗及卸载延迟；文献 8 中提出了一种深度强化学习方法将任务分配到不同的边缘服务器进行处理，以便将包括计算服务延迟和服务故障损失在内的服务成本降至最低；文献 9 中针对车联网中车对外界的信息交换（Vehicle to Everything，V2X）网络的资源分配问题进行研究，并使用 Double DQN 来解决资源分配问题。然而，这些工作都基于一个未定的假设边缘节点能卸载并执行所有类型的计算型任务。事实上，边缘节点的存储空间通常有限，并且各服务缓存策略并不一致，因而在实际中很难有效地应用。而对于这类服务卸载问题来说，云服务器与边缘节点任务的分配效率以及多媒体的QoS是需要考虑的，例如，文献19 中提出了一种名为 BitLat的 ABR 算法以提高用户在线视频的 QoS。而基于资源受限的 MDP建模的服务卸载问题在很多情况下属于NP-hard问题20，常规的搜索方法已经不适用于解决此类问题，因而近年来不断有学者针对边缘节点的服务卸载问题提出优化理论，并取得了不错的效果。文献21 针对移动边缘计算上的在线计算与服务卸载问题，使用适应性遗传算法（Adaptive Genetic Algorithm，AGA）优化深度强化学习的探索过程，相较于对比算法，它所提出的DRGO 算法能更快地收敛并得到更好的卸载策略。文献22 针对5G边缘网络中的计算服务卸载问题，提出了一种高效可靠的多媒体服务优化机制，并利用博弈理论对问题进行求解，有效提升了网络传输性能。文献 23 中通过扩宽服务缓存的作用，实现了一种基于缓存服务和计算卸载的联合优化算法；但该算法假定计算型服务是可分割的，而本文假定每个计算型服务为最小单元，并通过增加服务数量来表示它是可分割的，改进文献 23 的算法以解决本文的问题。因此，不同于以上工作，本文提出了一种基于改进深度强化学习的DRL算法ECSO算法。通过对边缘节点可用存储资源及计算资源加以限制，并基于 MDP 模型实现 DRL算法，以解决状态概率转移难以预测的问题；同时，基于本文给出的动作筛选算法得到最优动作集，降低算法动作空间的大小，进一步优化算法决策过程，进而满足边缘计算服务卸1544第 5 期曹腾飞等：基于改进深度强化学习的边缘计算服务卸载算法载过程中对低时延的要求。2 服务卸载模型 本章将分别介绍系统模型、MDP以及边缘服务卸载的定义和描述。2.1系统模型在本文的模型中，边缘节点有着计算资源F以及存储空间C，计算资源F用于服务计算，存储空间C用于缓存服务数据。本文定义计算型服务集合为=1，2，K，时隙集合为=1，2，T。每个服务都有两个属性(ck，fk)，分别表示此服务所需空间以及此服务所需计算资源，假定每个单独的服务都是不可分割的。本文设定单一k服务带来的下载时延为tdownk，边缘节点使单一k服务减少的传输时延为tdtransk；用户发送请求到边缘节点的传输时延定义为tuplinkk，由于边缘节点算力有限，因而会带来额外的执行时延texeck。设定t时隙服务k的请求数量为dtk，dtk为用户对单一服务k的请求提供数量，表明当边缘节点提供单一服务k时，多个用户请求服务k这一类服务。本文定义的环境存在实际应用，例如，当社会热点新闻出现时，会引发大量用户关注，此时多个用户将请求相同的数据内容，当边缘节点缓存这类数据内容时，就可以直接向这些用户提供服务18。边缘节点不会缓存不在本地提供的服务，每一时隙边缘节点采取不同的策略来进行服务卸载，且单一时隙内总能完成回传数据的任务。系统模型如图1所示，本文的目标是解决单个边缘节点的边缘计算服务卸载问题。在该模型中，边缘节点拥有相应的计算资源以及存储资源，并且边缘节点可以记录所有服务。系统模型中存在两类过程：服务卸载过程以及边缘计算过程。在服务卸载过程中，当边缘节点未缓存k服务时，从云端下载相关数据需要的下载时延为tdownk；若边缘节点满足服务k的需求且可以提供服务时，用户无须再上传数据至云端计算，而只需向靠近用户侧的边缘节点发送指定服务的卸载请求数据，这个过程的时延为tuplinkk，整个过程消耗存储空间ck，完成服务卸载过程。而在边缘计算过程中，当边缘节点向用户提供已完成卸载的服务时，消耗计算资源fk，并消耗执行时延texeck完成计算。由于边缘节点靠近用户侧，当边缘节点卸载计算型服务时，边缘节点可降低的传输时延为tdtransk，完成边缘计算过程。此时如果针对单一服务k有多个服务请求时，则需要分别向多个用户提供计算型服务k，因此资源消耗也会增加，同时累计降低的传输时延也会增加。2.2马尔可夫决策过程在此系统模型中，本文将边缘计算服务卸载问题建模为MDP，下面将分别介绍状态空间、动作空间以及奖励方法。2.2.1状态空间状态是对当前系统环境的描述，而状态空间是所有可能状态的集合。在本文定义的问题中，状态是时隙开始时的系统状态，系统状态由缓存状态和请求状态组成。设定边缘节点t时隙下的服务缓存状态为矩阵Mt，如果边缘节点在时隙t内缓存提供服务k，其缓存状态Mtk=1，否则Mtk=0。同 样 的，边 缘 节 点 的 请 求 状 态 矩 阵 设 为Dt=dtk，其中dtk代表用户对于服务k在t时隙内的请求数量。边缘节点需要缓存数据和服务计算，但存储空间及计算资源有限。因此，存储空间和计算资源需要分别满足式（1）和式（2）：k ckdtkMtk C（1）k fkdtkMtk F（2）本文考虑到用户的请求可能针对同一个服务的不同类型，当边缘节点对服务k进行服务卸载时，不同类型的服务请求需要缓存并计算多份数据，因而存储以及计算资源约束需要考虑请求数量矩阵Dt，具体到每一服务即为dtk。由于缓存状态在t时隙开始时仍为t-1时的状态，因此t时隙的状态空间为St=(Mt-1，Dt)。2.2.2动作空间动作空间就是一系列边缘节点可能采取的动作的集合。本文定义动作矩阵At=Atk，其中Atk-1，0，1。对于每个边缘节点，Atk=1表示边缘节点在时隙t-1不提供服务k，而在时隙t内提供服务k。在这一动作中，用户会向边缘节点发送服务k的卸载请求，这个过程耗时tuplinkk，边缘服务器将会从云端下载服务所需服务数据，经过下载所需时延tdownk之后提供服务k；Atk=-1表示边缘节点在时隙t-1时在本地提供服务k，而在时隙t内不在本地提供服务k。在这一动作中，由于边缘节点只需删除相关服务数据，因此不会产生额外的时延；而Atk=0表示边缘节点不采取任何改变状态的行为，在时隙t的服务提供状态与在时隙t-1相同。设|为总服务数量，由于动作空间为一系列边缘节点可能采取的动作的集合，因此动作空间的总大小为3|，然而动作空间中也有许多无意义的动作，例如当Mt-1k=0且Atk=-1时，表明边缘节点并未缓存提供服务k所需的数据，但边缘节点仍要删除这些数据。这些动作即“非法动作”。设为满足存储空间及计算资源限制的所有策略的集合，那么这些动作可以表示为|AtkMt-1k+Atk。状态转移概率是策略制定后当前状态转移到新状态的概率。对于(Mt-1，At)来说，转移概率是确定的；但由于状态空间还包括请求状态Dt，它会随着时间的推移而随机变化，状态转移概率难以精确估测。这是边缘计算服务卸载问题不能直接用MDP来解决的根本原因。2.2.3奖励方法奖励方法R(s，a)就是边缘节点从状态s执行动作a之后得到的激励值，正向激励有利于提高边缘节点在此状态下执行动作a的概率；负向激励则降低边缘节点在此状态下执行动作a的概率。本文根据不同的状态和动作行为定义奖励方法：如果动作非法，则只需要施加负奖励以规避非法的动作；反之，如果图1边缘计算服务卸载模型Fig.1Edge computing service offloading model1545第 43 卷计算机应用动作带来正收益，则需要予以正奖励。以合法操作为例，当Atk=1时，表明边缘节点提供服务，这表示用户需要发送服务卸载请求，之后边缘节点从云端获取所需服务数据再提供服务k，因此降低的传输时延为tdtransk-tdownk-tuplinkk；当Atk=-1时，表明边缘节点删除相关服务数据并不再提供服务k，此时降低的传输时延为 0；若Atk=0，则表明维持时隙t-1内的服务缓存状态Mt-1k。若Mt-1k=0，表明时隙t-1内边缘节点不提供服务k，即t时隙内降低的传输时延为 0；若Mt-1k=-1，表明t-1时隙内边缘节点仍由边缘节点本地提供服务k，但由于服务数据已经缓存到边缘节点上，不需要从云端再获取服务数据，即t时隙内降低的总传输时延为tdtransk。由于执行计算型任务也会消耗一定的时间，提供服务时需要额外减去执行时延texeck，因而降低的边缘计算处理时延为降低的传输时延与执行时延的差值。考虑到单一服务数据缓存至边缘节点后，直到此服务数据被删除之前，向用户提供服务时不再需要从云端服务器下载此类数据，该时隙内提供服务不会带来额外的下载与上传时延tdownk+tuplinkk，奖励由式（3）给出，负奖励给予它较大惩罚，视为-，表述如下：Rtk=|dtk(tdtransk-texeck)-tdownk-tuplinkk，Atk合法且Atk=10，Atk合法且Atk=-1dtkMt-1k(tdtransk-texeck)，Atk合法且Atk=0-，Atk非法（3）2.3问题定义由2.2节的奖励方法可知，奖励代表着边缘节点在系统模型中总共降低的边缘计算处理时延。总处理时延越低，意味着边缘节点越能满足用户对于低时延的要求，因此目标是最大化边缘节点所获取的长期奖励，由式（4）给出：max limT 1Tt tRt（4）s.t.式（1），（2）其中：t是衰减因子，随着时间的变化不断减小；Rt=k Rtk表示t时隙内所有服务的奖励之和。3 ECSO算法 本章将介绍ECSO算法的具体实现以及优化过程。传统DRL（如 DQN）可以作为此类问题的解决方法，但相较于DQN，ECSO算法能更有效地降低边缘计算处理时延，因而更适合解决此类问题。3.1基于MDP的DRL实现上述MDP不能直接应用的原因是状态转移概率难以预测，且传统 MDP 的建模方案在一定程度上受到状态空间和动作空间大小的限制。而DRL算法可以很有效地解决这类问题，因为DRL算法可以不用预先输入任何数据，主要依靠不断的环境探索和经验回放来得到对应环境下执行动作的奖励，并依据这些奖励优化模型参数。本文以 DQN 为例实现DRL算法。DQN的目标就是得到执行动作后的预计奖励，即Q值。DQN将边缘节点的状态作为其深度神经网络的输入进行训练，得到所有动作的Q值，以此改进依赖于表格的传统强化学习算法。由此，它省略了以表格记录Q值的过程，直接通过深度神经网络生成Q值，解决了无限状态空间的问题。它的探索策略E为贪心策略，设定随机概率为p，如式（5）所示：E=rand(a)，p 0，)argmaxQ(s，a)，p ，1（5）使用贪心策略进行探索可以避免算法陷入局部最优状态。本文算法采用递减贪心策略，它的参数会随着训练迭代数的增加而递减，这种策略在训练前期能够探索更多的动作可能性，而后期也可以使算法减少采取随机动作的可能性，这有助于算法的稳定。DQN使用两个神经网络进行训练：一个是需要训练的主网络，一个是用于生成Q值的目标网络。DQN通过损失函数来训练模型参数。损失函数为目标网络的估计值Qr(s，a)和主网络的输出Q(s，a)的平方差，如式（6）所示：Loss=(Qr(s，a)-Q(s，a)2（6）其中：Qr(s，a)=reward+Q(s，argmaxaQ(s，a)（7）是应用于下一步奖励的衰减系数；Q(s，a)是目标网络中对 状 态s执 行 动 作a所 得 到 的 单 步 奖 励 估 计 值，而argmaxaQ(s，a)则是下一步状态s中拥有最高 Q 值估计的动作a。3.2动作筛选目前未经修改过的动作空间大小为3|，这个数值会随着总服务数量的增大而呈指数型增长，当服务数量过多时，模型训练将会非常困难。其次，定义的动作空间仍包括非法动作，非法动作的Q值无意义，算法执行和学习无意义的非法动作反而会影响它的稳定性，因此需要采取措施优化动作空间，以提高训练效率。在动作空间中，Atk-1，0，1，它执行动作的奖励值如式（3）所示。如果能拥有所有可计算部分的奖励，那么通过不同部分的组合就能得到预期的奖励，因此，无须计算整体At的奖励，而是根据用户所请求的服务来计算对应Atk的奖励，从而将动作空间的大小从3|降低到3|。但是，动作空间仍存在部分非法动作，例如，当Mt-1k=0且Atk=-1时，很明显动作非法。由此，本文定义新的动作行为xk，从式（3）中可以得知奖励只与边缘节点的三种动作状态有关，例如，在Mt-1k=1的缓存状态下，Atk=0时降低的边缘计算处理时延为dtktdtransk，带来的奖励视为等同于xk的奖励；Atk=-1时，边缘节点不会提供服务k，其降低的边缘计算处理时延为0，此时xk的奖励为0；而Atk=1是非法动作，奖励定为-。这样，仅需计算对于每个服务k的动作xk的奖励，动作空间大小也就降低至|，并且能够避免非法动作。而计算预期奖励时只需组合各动作对应的奖励，筛选得到最高值的动作行为集即可。具体动作筛选如算法1所示。算法1 动作筛选算法。输入 边缘节点存储空间C和计算资源F，所有服务的属性(ck，fk)，每个动作xk执行的预期奖励rk；输出 符合策略的动作集合Xt。1）初始化Rmax 02）FOR k 1 to K：3）FOR i 1 to C：4）FOR j 1 to F：5）if ck i and fk=0：6）令Rmax+=rk，如果Xt不包含xk，则将xk加入Xt中7）else：8）如果xk位于动作集合Xt中，则从Xt中去除xk，并令Rmax-=rk；否则，Rmax保持不变1546第 5 期曹腾飞等：基于改进深度强化学习的边缘计算服务卸载算法9）END FOR10）END FOR11）END FOR对于算法1，i与j从1开始逐渐迭代到最大值，这是为了寻找并优先组合能够带来收益、且所要求的资源最小的动作，并在后续迭代中从动作集中去除对于资源要求较大的动作。如果ck大于边缘节点所剩余的空间i，或是fk大于边缘节点剩余的计算资源j，那么服务k就不能在边缘节点本地提供，因而筛选后的动作集保持不变。当边缘节点剩余的存储空间和可用的计算资源满足服务k的需求时，边缘节点可以作出两种选择：提供服务k，并令Rmax+=rk；或者不提供服务k，令Rmax保持不变。算法 1的目标是尽可能在提供更多服务的情况下最大化各服务动作带来的奖励，而算法1本质上可视为动态规划问题进行求解，求解后得到的动作集合即为能带来最大奖励值的动作集合。3.3更新方法得到最优动作集后，由于主网络和目标网络输出的是单一动作xk的Q值，而不是整体Xt的Q值，因此不能使用整个Xt的Q值代替xk更新。由于Xt由筛选后的xk组成，因此，针对每个动作行为xk更新损失值的损失函数也需作出改变。对于t时刻候选动作列表Xt，根据式（6）所示的形式，定义式（8）：L(Xt)=(Qr-Q(St，Xt)2（8）其中：Qr=R+Q(St+1，argmaxXtQ(St+1，Xt)（9）对于Q(St，Xt)，分别计算其中每个xk动作产生的 Q 值，Q(St，Xt)为其中所有动作行为Q值之和，如式（10）所示：Q(St，Xt)=x XtQ(St，x)（10）为了得到动作列表Xt中每个xk的损失值，本文使用占比的方式计算每个xk的损失值，如式（11）所示：L(xk)=Q(St，xk)Q(St，Xt)L(Xt)（11）本质上，边缘节点执行的是各服务k的动作xk。依据算法1，每一次筛选得到的最优动作集取决于各动作xk预期的奖励，对应的是主网络预测的Q值。这一时隙得到的最优动作集与上一时隙中得到的最优动作集会因为主网络参数的更新而发生更改，各xk之间也相互独立，因而无须考虑各服务动作xk的组合情况，也不会导致算法性能下降。按照以上方法求解每个xk的损失值，就可以在更改动作空间之后使用动作行为的损失值梯度下降更新主网络。3.4算法流程及实现ECSO 算法流程如图 2 所示，主网络与目标网络有着相同的网络结构，由于定义了新的动作行为xk，主网络与目标网络的输出值均为xk的 Q 值而不是原有动作空间的 Q 值。首先，算法会根据探索策略随机选择执行动作或是Q值最高的行为执行动作，根据算法1筛选动作行为xk放入动作列表Xt中，并将元组(St，Xt，Rt，St+1)作为经验存入回放经验池中。之后算法随机取出一批经验来训练主网络。目标网络则输出动作列表的 Q值Q(St+1，X)。接着算法根据主网络输出的每个Q(St，xk)以及目标网络输出的Q(St+1，X)依次计算每个xk的损失值。并依次梯度下更新损失值，以此训练主网络，且每隔一定频率更新目标网络的网络参数。算法2给出了ECSO算法实现的伪代码。算法2 ECSO算法。输入 循环次数U和时隙数T，网络更新频率L，衰减因子；输出 Q网络参数。1）初始化主网络参数，令目标网络参数=，并使Q(St，at)=Q(St，at)2）FOR i 1 to U：3）初始化第一状态S14）FOR t 1 to T：5）输入St并通过如式（5）所示的策略贪心选择动作xk6）分别执行动作xk，得到新的状态St+1，并将xk放入候选动作集合Xt7）将元组(St，Xt，Rt，St+1)存入经验池中8）从回放经验池中随机取出一批回放样例(S j，Xj，R j，S j+1)9）根据算法1将Xj筛选得到最优动作集X10）通过式（10）在目标网络上计算Q值Q(S j+1，X)11）根据得到的Q(S j+1，X)，重新计算目标值：Qr=R j，终止R j+Q(S j+1，X)，其他12）通过式（11）得到X中每个xk的损失值，使用每个得到的损失值梯度下降更新网络参数13）每过L步将主网络的参数赋值给目标网络，即令=14）END FOR15）END FOR依据本文提出的 ECSO 算法，通过定期更新网络参数，优化目标网络对于边缘节点服务采取的动作集合Xt，从而达到优化边缘节点服务卸载决策的目的。4 仿真实验与结果分析 本章将介绍ECSO算法的实验环境以及参数设定，然后与其他 DRL 算法以及传统算法进行对比，根据结果验证本文 ECSO 算法更适合解决边缘计算服务卸载的问题。值得说明的是，本文在实验中对所有算法均设置了存储和计算资源的条件限制。4.1实验参数设置本实验使用 TensorFlow24运行算法。本次实验模拟考虑50个服务，计算所需资源fk在0.5，2.5 GHz内随机取值，储存所需资源ck在0.2，2 GB内随机取值，边缘节点减少的传输时延tdtransk在2，5 s内随机取值，假定服务所需的计算资源充足且充分利用，则它的执行时延texeck=ck fk。用户发送请求到边缘节点的传输时延tuplinkk取值取决于请求数量的多少。下载时延即为下载该服务数据需花费的时间，而带宽决定了下载速率的理论上限，考虑到单位的换算，服务对应的下载时延tdownk=8ck/Bandwidth，取带宽为 8 Gb/s。本文假设服务的请求频率遵循齐夫分布25，则平均请求数量如式（12）所示：图2ECSO算法流程Fig.2Flow of ECSO algorithm1547第 43 卷计算机应用D(k)=Vr(k)N（12）其中：r(k)是服务k的请求频率的排名；N是用户数量，在实验中取值为 150；在齐夫分布中通常取V=0.1；为数据分布的指数特征，在实验中取=1；设定边缘节点总计算资源为10 GHz，边缘节点总存储资源为10 GB。4.2性能分析4.2.1云端计算与边缘计算性能对比为了验证实验环境下边缘计算与直接由云端响应的服务性能差异，本文将两者进行了对比分析。ECSO-EC（ECSO-Edge Computing）：依照本文提出的算法以及模型进行运算，缓存的服务由边缘节点提供给用户，其他服务由云端进行响应。ECSO-CC（ECSO-Cloud Computing）：训练过程不变，只是边缘节点不再向用户提供缓存服务，转而由云端直接进行响应和运算，因而不考虑缓存服务带来的下载时延以及计算时延，因此不会降低传输时延。从图 3可以看出，在训练的开始阶段，由云端直接响应的性能优于由边缘节点缓存并提供服务的性能，这是由于边缘节点的决策还尚未被完全优化，边缘节点提供的服务并不能降低更多的时延。随着训练回合的增加，算法能够更好地决策，边缘节点也能优先向用户提供占用资源少、请求数量多的服务，因而 ECSO-EC 算法能够积累到较多正向的奖励值。ECSO-CC算法积累的奖励值代表边缘节点提供计算型服务时带来的额外时延，同样随着回合数的增加而趋于较低的值。此时由边缘节点提供计算型服务相比直接由云端响应所降低的总处理时延更高。这也表明了由边缘节点缓存并提供服务所带来的性能提升。4.2.2边缘计算中不同算法之间性能对比本节将对比不同回合中算法的奖励值以及单一回合中不同时隙下降低的传输时延。本文的ECSO、DQN和PPO这三种DRL算法以及传统MP算法介绍如下：ECSO：算法每时隙输出自身对各个动作的预测价值，并将它们作为动作筛选算法的输入，从而得到最优动作集。边缘节点每时隙按照最优动作集提供或卸载服务。DQN16：算法根据式（5）的 贪心算法探索得到动作并更新网络参数。边缘节点依据神经网络预测值提供以及卸载服务。PPO17：算法在开始阶段探索并积累动作轨迹，并且每一时隙更新动作轨迹的优势以及回报，一旦积累一定数量时，开始更新网络策略。边缘节点根据其中执行者网络的预测值提供或卸载服务。MP18：边缘节点根据用户每个时隙中服务请求数量的积累计算每个服务的流行度，每一时隙中提供流行度最高的服务。由于MP算法不具备学习能力，进行多个回合的实验不会对MP算法的表现带来提升。因而对于传统算法，本文只对比单个回合内 200次时隙所能降低的传输时延。最终用于对比的奖励值定义为算法最终降低的传输时延与缓存计算服务带来的各类时延之差。本文的目标为最大化迭代后的奖励值。图4为三种DRL算法在 100次迭代中的奖励值对比，奖励值定义如式（3）所示，是验证算法性能的重要指标之一。从图4中可以看出，本文实现的算法最终稳定的奖励值整体要高于 DQN 算法，而PPO算法前期由于需要积累动作轨迹以便积累完成后学习，因此在前30次迭代中探索得到的奖励很低；ECSO算法相较于DQN算法收敛更快，这是因为ECSO算法会预先筛选动作，排除非法的动作并执行最优动作。PPO算法探索环境得到的奖励并不稳定，这是因为在它积累完动作轨迹之后需要从回放经验池中随机取出一批样本进行学习，由于存在针对非法动作的奖励惩罚，这就使PPO难以短时间平稳所获得的奖励。而DQN以及ECSO算法因为使用贪心策略进行探索，它们探索得到的奖励能较为平缓地增长。由于优化了算法的动作空间，一定程度上规避了非法动作带来的负奖励