【TSC 2023】基于遗传编程的Fog Computing动态调度策略

发布网友 发布时间：2024-10-24 05:31

我来回答

共1个回答

热心网友 时间：2024-11-01 03:43

《Genetic Programming for Dynamic Workflow Scheduling in Fog Computing》论文深入探讨了动态工作流调度策略在Fog Computing环境中的应用。随着移动设备和智能机器人的广泛应用，用户请求和数据量激增，Fog Computing技术成为解决延迟问题的有效途径。它通过将计算资源部署在边缘设备与云端之间，以缩短数据处理时间。然而，如何高效地将任务分配到边缘或云服务器，成为了一项具有挑战性的任务流调度问题。传统的调度启发式方法适用于解决静态工作流调度问题，但面对动态、不可预测的真实环境时，需要一种新的调度策略，以综合考虑移动设备、边缘设备与云端。

为应对这一挑战，《Genetic Programming for Dynamic Workflow Scheduling in Fog Computing》提出了基于遗传编程超启发式算法（GPHH）的动态工作流调度（DWSFC）算法。该算法能够基于实时信息进行动态响应，有效实现工作流的高效调度。GPHH算法利用遗传编程生成调度规则，采用事件驱动的模拟系统，通过实时调整路由规则（Routing Rule）和序列规则（Sequencing Rule），优化任务在边缘设备和云端的分配与执行。优化目标是使得整个工作流程的完成时间最短，即最小化最晚完成任务的时间（Makespan）。

算法设计中，首先利用Routing Rule判断任务是否上传至云端或本地执行，然后根据Sequencing Rule对任务队列进行排序，决定执行顺序。整个流程由事件驱动，按照任务到达、处理、执行直至结束的顺序循环执行，直至所有工作流完成。此过程涉及四个核心事件，即任务到达、任务处理、任务执行和任务结束。同时，算法利用适应度评估、Elitism选择、父代选择和子代繁殖等遗传算法的基本操作，通过交叉变异算子进行GP个体的进化，以寻找最优的路由和序列规则。

实验部分展示了不同工作流和设备数量下的调度场景，以及在五种不同类型工作流执行流程的实例。实验环境包括不同处理速率和带宽的Fog Server、Cloud Server和移动设备，通过构造九种调度场景，对比人工规则与GPHH算法的性能。参数设置遵循现有文献的常规设定。实验结果表明，GPHH算法在处理不同设备数量和工作流种类时，展现出显著优势，能够实现更短的完成时间（Makespan）。

通过分析不同场景下Routing Rule和Sequencing Rule的大小、终端变量的使用情况以及可视化结果，可以进一步理解GPHH算法在优化动态工作流调度中的作用。这些分析揭示了算法如何在复杂环境中实现高效调度，以及路由规则和序列规则对完成时间的影响。实验结果和分析共同证明了GPHH算法在动态工作流调度问题上的有效性和实用性，为Fog Computing环境下的工作流管理提供了新的解决方案。