在分布式雾计算中，利用进化动作进行深度强化学习以实现动态工作流调度

《Neurocomputing》：Deep reinforcement learning with evolved actions for dynamic workflow scheduling in distributed fog computing

动态工作流调度在分布式雾计算中面临复杂环境与动态挑战，本文提出多智能体DRL框架，结合遗传编程自动生成调度规则并引入 niching 技术优化规则多样性，实验验证其优于传统方法及现有DRL/GP方案。

　　

何一凡|徐展|林健|李远庄|张世宇

浙江财经大学，杭州，中国

摘要

在分布式雾计算（DWSDFC）中，动态工作流调度是一个关键的优化问题，对满足现代应用的计算需求具有重要意义。DWSDFC的动态和分布式特性使其成为一个极具挑战性的任务，尤其是使用传统的调度方法难以解决。最近，深度强化学习（DRL）作为一种强大的解决方案出现，能够在不同的决策点选择合适的调度规则作为行动。DRL的有效性在很大程度上取决于这些调度规则。然而，这些调度规则通常是手动设计的，需要大量的领域专业知识。因此，本研究专注于自动化设计DRL行动，以提高其解决问题的能力。首先，将DWSDFC构建为一个去中心化的部分可观测马尔可夫决策过程。然后，提出了一个多智能体DRL框架，包括一个路由智能体和一个排序智能体来处理DWSDFC。具体来说，排序智能体中的行动是通过一种称为遗传编程（GP）的进化算法生成的。为了增强这种进化行动集的多样性，从而提高DRL的性能，将基于行动之间行为差异的生态位技术集成到GP中。在各种DWSDFC实例上的广泛实验结果表明，所提出的方法比常见的调度规则以及最先进的DRL和GP方法更有效。

引言

计算能力的重要性日益被认识到是推动技术进步和高效执行各种任务的关键因素。智能计算领域的最新进展证明了数据驱动学习框架在复杂现实世界系统中的有效性[1]，[2]。这一趋势在广泛的学习范式和问题设置中也得到了体现，突显了数据驱动方法的广泛应用[3]，[4]，[5]。这样的智能计算范式通常需要大量的、可扩展的计算能力，无论是用于训练还是部署。云计算（CC）[6]是一种广泛使用的并行处理模型，它可以根据需求向用户提供处理器、内存、磁盘和通信网络等强大资源，无论用户位于何处。因此，将复杂任务卸载到云节点上已成为设备性能不足的用户的一个可行解决方案。这些任务通常被组织成复杂的工作流[7]，即旨在简化流程并确保高效执行的任务序列。第五代（5G）移动网络的最新发展[8]以及物联网（IoT）[9]等新应用领域改变了网络资源的访问模式。为了最小化延迟并提高服务质量，资源正在被重新部署到更接近最终用户的地方。这种转变催生了边缘计算（EC）[10]的概念。EC在数据源附近进行数据处理和分析。由于边缘节点位于生成数据的设备更近的地方，它们可以比云节点更快地做出响应。EC中的任务通常是要求快速响应的相对简单的工作流。

然而，应用程序的复杂性和多样性日益增加，这凸显了需要一种更细致的方法来弥合EC和CC之间的差距，从而产生了雾计算（FC）[6]，[11]，[12]。通常，FC通过中间节点（如网关、路由器或专用雾服务器）进行操作，这些节点位于边缘设备和云数据中心之间。这些雾节点提供了更接近网络边缘的计算和存储能力，但资源比单个边缘设备更多。FC通过支持任务的层次化分布，实现了更可扩展和灵活的服务部署：一些在边缘处理，一些在雾节点处理，其余的在云中处理[6]。这种分层架构提高了系统的响应能力，减少了核心网络的拥塞，并支持需要实时和高吞吐量处理的应用程序，例如智慧城市[13]、自动驾驶汽车[14]和工业自动化[15]。

尽管应用范围广泛，但在FC环境中的工作流调度仍然是一项远非简单的任务。工作流通常包含具有严格优先级和资源限制的相互依赖的任务，必须将它们映射到最合适的节点上，以优化诸如完成时间、预算和服务质量等重要目标[16]。此外，雾节点在计算能力、能源容量和网络带宽方面的异构性给调度过程带来了相当大的复杂性[6]。与以集中控制和丰富资源为特征的常规云环境不同，FC环境需要能够适应环境部分观测结果以及工作流到达、资源可用性和用户移动性的动态变化的去中心化调度策略[17]。这些困难促使本研究提出了一种新的分布式雾计算（DWSDFC）动态工作流调度模型，该模型具有到达的工作流、有限的资源和部分观测结果。与许多工作流调度问题类似，DWSDFC可以分为两个子问题：（1）从等待池中选择任务的排序；（2）将任务分配给节点的路由。

已经提出了许多启发式方法[19]，[20]、元启发式方法[21]，[22]和机器学习方法[23]，[24]来解决类似环境中的工作流调度挑战，每种方法在可扩展性、执行时间和解决方案质量方面都有各自的权衡。启发式方法通常轻量且快速，适用于实时场景。然而，它们往往依赖于固定的调度规则，容易陷入局部最优解。相比之下，元启发式方法进行全局搜索，可能产生更好的解决方案，但计算密集度较高，不太适合高度动态或时间受限的环境。

深度强化学习（DRL）[25]，[26]最近作为一种有前途的替代方案出现，因为它能够通过与环境的交互学习动态调度策略。多项研究探索了DRL在解决动态工作流调度问题中的应用，包括单智能体[27]，[28]，[29]和多智能体[30]，[31]设置。通常，DRL假设一个固定且有限的行动空间。然而，在FC的工作流调度背景下，这一常见假设并不总是适用。例如，任务排序决定了从候选池中执行的任务，其中每个行动都是选择一个单独的候选者。然而，这个候选池包含不同数量的候选任务。为了解决这个问题，一些研究[32]，[33]将调度规则作为行动使用。在这种设置下，DRL智能体能够选择其中一个规则，并识别出优先级最高的任务，而不管候选任务的数量如何变化。

显然，作为行动的可用调度规则集在DRL的性能中起着至关重要的作用。正是出于这个原因，本研究专注于为DRL自动设计基于调度规则的行动。为此，应用了遗传编程（GP）[34]，这是一种搜索满足给定规范的计算机程序的进化算法。这些计算机程序通常被编码为表达式树，并通过遗传操作符（例如子树交叉和子树变异）进行进化。GP在自动编程[35]、符号回归[36]和作业车间调度[37]等多个领域取得了成功应用。

为了增强进化规则的多样性和DRL的性能，我们引入了一种基于规则之间行为差异的生态位技术[38]。之后，使用了一个多智能体DRL框架，其中每个智能体对应一个子问题，并使用双重决斗深度Q网络（D3QN）[39]，[40]，[41]进行训练，以选择进化的行动。在本文的其余部分，我们将所提出的方法称为带有进化行动的DRL（DRL-EA）。这种混合设计比单独使用任一方法都有明显的优势。与产生单一固定规则的纯GP不同，DRL-EA使用学习到的策略根据当前系统状态选择不同的规则，从而更好地适应动态条件。与从手动设计的规则中选择的标准DRL不同，DRL-EA操作于由GP自动生成的更丰富的规则集。由于生态位机制，这些规则既高性能又多样化，为有效的策略学习提供了坚实的基础。在实验中，DRL-EA在大量的DWSDFC实例上进行了测试，与常见的调度规则以及基线DRL和GP方法进行了比较。实验结果突显了DRL-EA在解决DWSDFC方面的显著优势。这进一步证明了我们自动化设计DRL中行动的想法的有效性。本研究的主要贡献如下。

(1)

介绍了一种名为DWSDFC的新工作流调度模型，该模型具有到达的工作流、有限的资源和部分观测结果，以捕捉FC中遇到的困难。

(2)

采用基于D3QN的多智能体DRL框架来解决DWSDFC。这两个智能体分别对应于DWSDFC的排序子问题和路由子问题。

(3)

首次在FC的工作流调度中提出了DRL行动的自动设计思想。为了实现这一思想，应用GP来搜索有前途的调度规则作为行动。

(4)

将生态位技术集成到GP算法中，以增强生成的基于规则的行动的行为多样性，从而提高DRL的性能。

(5)

通过在大量实例上的全面比较实验验证了所提出方法DRL-EA的有效性，这些实例涵盖了多种比较方法。

本文的其余部分组织如下。第2节提供了本研究的充分背景知识。第3节详细介绍了DWSDFC的数学建模。第4节介绍了所提出的方法DRL-EA，并在第5节进行了测试。最后，第6节总结了研究并指出了几个未来的研究方向。

章节摘录

雾计算中的动态工作流调度

工作流调度是分布式计算环境（如CC、EC和FC）中任务管理中的一个关键问题。工作流通常表示一组具有依赖性的计算任务，通常被组织为有向无环图（DAG），其中节点代表任务，边表示数据或控制依赖性。工作流调度是指在满足任务依赖性的同时，将工作流任务映射和排序到计算资源的过程

问题定义

本节概述了四个关键模型，这些模型有助于形式化本文分析的雾计算场景，即工作流模型、设备模型、传输模型和任务处理模型。这些模型构成了定义DWSDFC问题的基础。本文中使用的重要符号列表可以在表1中找到。

提出的方法

为了解决DWSDFC问题，提出了一种名为DRL-EA的动态工作流调度框架，它结合了多智能体DRL和NichGP的优势。本节介绍了DRL-EA的设计和训练细节。

数值实验

本节检验了所提出方法在各种场景下的有效性和泛化能力。源代码可在在线仓库获取。

结论

本研究提出了深度强化学习与进化行动（DRL-EA），这是一种新颖的混合框架，它将DRL与遗传编程（GP）结合在一起，用于解决分布式雾计算（DWSDFC）中的动态工作流调度问题。为了应对雾环境的分散和部分可观测特性，问题被构建为一个Dec-POMDP，并使用多智能体DRL框架来解决。路由智能体（RA）和排序智能体（SA）分别接受训练以进行路由

CRediT作者贡献声明

何一凡：写作 – 审稿与编辑，撰写原始草稿，监督，方法论，概念化。徐展：撰写原始草稿，软件，方法论，数据管理。林健：监督，项目管理，资金获取。李远庄：可视化，验证。张世宇：可视化，验证。

利益冲突声明

作者声明他们没有已知的财务利益或个人关系可能会影响本文报告的工作。

致谢

本项工作得到了中国国家自然科学基金（项目编号61973267）和浙江省自然科学基金（项目编号LY24F030008和LQN26F030004）的支持。

何一凡于2023年在日本筑波大学获得计算机科学博士学位。他目前是中国浙江财经大学信息技术与人工智能学院的讲师。他的研究兴趣包括强化学习及其在组合优化（如工作流调度）等领域的应用。