《Journal of Parallel and Distributed Computing》：Reload: Deep reinforcement learning-based workload distribution for collaborative edges
编辑推荐：
针对动态边缘环境中异构任务、网络和服务器带来的调度挑战，本文提出基于深度强化学习的智能调度器Reload，通过A2C算法优化任务分配策略，有效降低平均响应时间，并通过仿真验证其有效性。
梁宇|葛继东|吴杰|张胜|文世武|罗斌
中国南京师范大学计算机与电子信息学院/人工智能学院
摘要
边缘计算是一项有前景的技术，旨在实现网络边缘的及时计算。主要的服务提供商几年前开始部署地理分布式的边缘服务器。在地理分布式的边缘环境中，一个主要挑战是任务调度，即如何将移动用户提交的各种任务分配到分布式边缘，以优化某些指标。然而，在地理分布式的边缘环境中执行任务调度并不容易。我们观察到，在动态边缘环境中设计高效的任务调度解决方案存在三个主要挑战：异构任务、动态边缘网络和异构边缘服务器。在本文中，我们提出了一种黑盒解决方案，用于协作式边缘环境中的任务调度，而不依赖于详细的分析性能建模。我们提出了Reload，这是一个基于智能深度强化学习的任务调度器。Reload仅基于已知信息学习策略，而不需要预测未来。Reload将其策略表示为一个神经网络，该网络将“原始”观察结果映射到调度动作。在训练过程中，Reload从一无所知开始，通过强化学习逐渐学会做出更好的调度决策，这种强化学习以过去决策的奖励信号形式进行。Reload利用Advantage Actor Critic（A2C）来训练策略网络。我们通过广泛的模拟来评估Reload的性能。
引言
近年来，互联网边缘产生的数据量呈爆炸性增长。例如，一个高清的交通监控摄像头每天可以生成几TB的数据[1]。此外，越来越多的计算密集型应用，如交互式游戏、实时视频分析和虚拟或增强现实，在网络边缘变得越来越流行；更糟糕的是，这些应用通常要求低延迟。云计算似乎无法及时处理如此大量的数据，因为一方面，将如此大量的数据传输到集中式计算集群会产生不可忽视的延迟。另一方面，集中式计算集群的计算能力呈线性增长，无法与网络边缘产生的数据量呈指数级增长相匹配。
边缘计算是一项有前景的技术，旨在实现网络边缘的及时计算[2]。主要的服务提供商几年前开始部署地理分布式的边缘服务器。例如，谷歌部署了超过1400个边缘服务器[3]。通过这些地理分布式的边缘服务器，终端用户可以随时随地获得低延迟的边缘服务，这大大减轻了大量数据对骨干网络和集中式数据中心的影响。
任务调度是地理分布式边缘的关键，即如何将移动用户提交的各种任务分配到分布式边缘，以优化某些指标，例如平均任务响应时间、在截止日期前完成的任务数量。以往的工作在地理分布式边缘中执行任务调度方面存在不足。大多数研究[1]、[4]、[5]、[6]专注于将突发任务请求卸载到单个服务器或设备上。一些关于边缘协作的研究旨在强调其在设备对设备环境中的优势。例如，[7]中的工作提出了一种实现能效高的协作任务执行的方法。这些研究可能失败了，因为它们大多没有考虑边缘环境的动态性。
在地理分布式的边缘环境中执行任务调度并不容易。我们观察到，在动态边缘环境中设计高效的任务调度解决方案存在三个主要挑战。首先，用户任务在任务工作负载1、任务截止日期、任务输入大小等方面是异构和动态的。用户任务的异构性阻碍了一些高效算法的设计。其次，边缘网络在带宽方面通常是动态的，特别是从终端用户到边缘服务器（通常与蜂窝基站或接入点一起部署）的上传带宽。第三，不同服务器的工作负载可能差异显著，因为边缘服务器是地理分布的，这种地理差异使得不同的终端用户偏好不同的边缘服务器。
在本文中，我们考虑以下一般场景：在本地区域部署了多个异构边缘服务器。每个边缘服务器都与一个接入点（AP）相关联。AP可以是蜂窝基站、WiFi路由器或任何可以接收和发送消息的其他硬件。因此，这些边缘服务器通过无线方式连接。这些AP和边缘服务器形成了协作式边缘环境，因为它们通过执行从终端用户卸载的任务并将分析结果发送回终端用户来协作服务终端用户。在这种场景下，移动用户可以随时随地移动。每个用户都可以将其任务卸载到协作式边缘环境进行快速执行。通常，用户通过距离自己最近的AP提交任务。需要注意的是，正如我们之前提到的，用户与AP之间的带宽通常是随时间动态变化的。在本文中，我们的目标是最小化所有卸载到协作式边缘环境的任务的平均响应时间。任务的响应时间定义为任务提交到协作式边缘环境的时间与任务分析结果发送回用户的时间之间的差异。当用户将其任务提交到边缘环境时，边缘环境必须确定该任务应卸载到哪些边缘服务器以及卸载的比例，即该任务的多少工作负载应卸载到每个边缘服务器。为此，我们必须智能地执行任务调度。
然而，在协作式边缘环境中进行任务调度是困难的，原因如下。首先，由于任务的完成时间不仅取决于任务本身，还取决于每个服务器上待处理队列中的其他任务，因此需要未来任务的信息来解决当前的优化问题。其次，由于边缘服务器采用先来先服务（FCFS）策略来调度任务，当前的决策也会影响未来任务的完成时间。第三，任务的完成时间取决于待处理队列的工作负载，因此无法给出完成时间的封闭形式表达式。
因此，我们提出了一种黑盒解决方案，用于协作式边缘环境中的任务调度，而不依赖于详细的分析性能建模。我们选择深度强化学习（DRL）[10]、[11]，因为它在解决各种研究领域的许多难题方面显示出了优势。然而，由于调度预算有限和决策空间较大，将DRL集成到所提出的问题中具有挑战性。首先，对于调度问题，存在调度质量和调度开销之间的权衡。高质量的调度可以有效减少任务完成时间，但代价是消耗较长的调度时间。其次，在我们的问题中，我们不仅需要决定目标边缘服务器，还需要决定卸载的工作负载百分比，这导致了较大的决策空间。这两个内在相互关联的挑战共同使问题变得更加复杂。
我们提出了Reload，这是一个针对协作式边缘环境中的任务卸载而定制的智能深度强化学习任务调度器。Reload仅基于已知信息学习策略，而不需要预测未来。Reload将其策略表示为一个神经网络，该网络将“原始”观察结果映射到调度动作。神经网络以可扩展的方式将丰富的观察结果多样性纳入调度策略。在训练过程中，Reload从一无所知开始，通过强化学习逐渐学会做出更好的调度决策，这种强化学习以过去决策的奖励信号形式进行。Reload利用Advantage Actor Critic（A2C）[12]来训练策略网络，该网络以边缘网络状况、服务器统计信息和任务特征作为输入，并通过输出（例如，动作分布）选择最佳动作。我们通过广泛的模拟来评估Reload的性能。
主要贡献总结如下：
•我们考虑了一个场景，其中边缘服务器通过无线方式连接，并协作执行从各种终端用户卸载的任务。
•我们设计并实现了Reload。尽管任务、边缘网络和边缘服务器具有各自的异构性和动态性，但它们有隐藏的规律，如果我们能够学习这些规律，应该有助于我们进行调度。
•我们进行了广泛的模拟来评估Reload的性能。评估结果证实了Reload的有效性。
本文的其余部分组织如下。我们在第2节中阐述研究动机。第3节介绍任务调度问题。第4节介绍Reload。第5节进行评估。第6节回顾相关工作。第7节讨论局限性和未来工作。第8节总结本文。
部分摘录
动机
在本节中，我们从三个不同且可能正交的方面展示了边缘环境的动态性，即异构任务、动态边缘网络和异构边缘。
系统模型和问题表述
在本节中，我们阐述了协作式边缘环境中任务调度的问题，并提供了问题的正式数学表述。
我们将时间划分为离散的时间槽，每个时间槽的持续时间与可以生成任务调度决策的时间尺度相匹配。我们设想以下场景：在一个局域网中，总共有N个边缘服务器，分别为e1、e2、...和eN。这些边缘服务器通常是
基于深度强化学习的工作负载分配
在本节中，我们首先介绍了Reload中的基本学习机制。然后，我们展示了如何使用深度强化学习（DRL）来解决TSiCE问题，并介绍了状态空间、动作空间和奖励信号的详细信息。
性能评估
在本节中，我们通过广泛的模拟来评估Reload的性能。我们首先介绍评估设置。然后我们介绍几个最先进的基准进行比较。最后我们在多种设置中展示了比较结果。
相关工作
边缘计算中的一个主要研究领域是卸载，它可以被视为边缘计算范式的一个通用杀手应用。通过将计算密集型且可能耗能的任务卸载到附近的边缘服务器，移动设备可以加速任务并节省能源消耗。
已经提出了几项研究[27]、[28]、[29]，通过卸载任务的所有或部分工作负载来优化移动设备上的能源消耗。例如，Cuervo等人[30]
讨论
在本节中，我们讨论了Reload的几个局限性和可能的未来研究方向。
动态边缘服务器集。Reload解决了协作式边缘云环境中的在线任务调度问题。在其当前设计中，协作式边缘云中的边缘服务器集是固定的。实际上，我们可能允许边缘设备随时离开或加入协作式边缘云。例如，由于工作负载过重或温度过高，某个边缘服务器可能会崩溃，然后一些
结论
在本文中，我们考虑了协作式边缘云环境中的任务调度问题。我们观察到，在动态边缘环境中设计高效任务调度解决方案存在三个主要挑战：异构任务、动态边缘网络和异构边缘服务器。我们提出了一种黑盒解决方案Reload，用于协作式边缘环境中的任务调度，而不依赖于详细的分析性能建模。Reload仅基于已知信息学习策略
CRediT作者贡献声明
梁宇：撰写 – 审稿与编辑，撰写 – 原始草稿。
葛继东：监督。
吴杰：资源提供。
张胜：形式分析，概念化。
文世武：验证。
罗斌：项目管理。
利益冲突声明
代表所有作者，通讯作者声明，在我们提交给《并行与分布式计算杂志》的手稿“Reload: 基于深度强化学习的协作式边缘工作负载分配”中不存在利益冲突。
梁宇是南京师范大学的副教授。她分别于2011年和2021年在南京大学获得了硕士和博士学位。2011年至2017年期间，她是趋势微中国开发中心的高级软件工程师。她的研究兴趣包括云计算和边缘计算中的资源分配。她的出版物包括发表在TON、TMC、TPDS、TON、INFOCOM、MM、ICDCS和ICDE等期刊上的文章。
