I_MOAFT：一种智能的多层框架，用于雾计算-云计算环境中实现能效高效且低延迟的任务调度

时间：2026年2月24日

来源：Sustainable Computing: Informatics and Systems

编辑推荐：

多目标任务调度在雾-云环境中面临资源异构和低延迟需求挑战，本文提出融合DBSCAN聚类与改进的I_MOAFT元启发式算法的多层框架，通过动态聚类减少计算复杂度，创新性整合非支配排序、自适应精英保留机制和动态探索范围调整策略，实验表明可使makespan减少55.8%，能耗降低43.2%

Leila Aminoroaya|Reihaneh Khorsand|Mahdi Mosleh

伊朗伊斯法罕伊斯兰自由大学计算机工程系

摘要

在雾计算-云计算环境中，有效的任务调度是一个关键挑战，因为物联网（IoT）应用对低延迟有严格要求，同时雾计算资源的异构性也很高。现有方法常常存在过早收敛、解决方案多样性不足以及适应资源异构性能力差等问题。为了解决这些限制，本文提出了一种多层次框架，该框架将机器学习与改进的元启发式优化策略相结合。在该框架的雾计算层中，引入了一种两阶段调度机制：首先，使用基于密度的空间聚类算法（DBSCAN）根据任务的资源需求对任务进行聚类，以减少异构性和通信开销；其次，每个聚类由改进的多目标Ali Baba和Forty Thieves（I_MOAFT）算法进行调度。I_MOAFT引入了四个关键创新：（1）智能集成DBSCAN引导的聚类，用于结构化种群初始化和增强探索；（2）将AFT算法扩展到多目标框架中，通过非支配排序和动态拥挤距离实现稳健的帕累托最优解；（3）一种新颖的选择性精英主义与动态消除（SEDE）机制，结合基于密度的档案剪枝和高斯引导的扰动，以平衡收敛性和多样性；（4）一种改进的自适应跟踪机制，借鉴了SAFT算法，每个搜索代理根据性能反馈动态调整其探索范围。使用真实世界科学工作流程进行的广泛模拟表明，所提出的框架在完成任务时间（makespan）上比现有算法提高了55.8%，能源消耗降低了43.2%。

引言

物联网应用的快速增长——如智能医疗、工业自动化和智能交通——对低延迟、节能和可靠的计算产生了强烈需求[1]。鉴于数据中心和边缘基础设施的环境和运营成本，能源意识调度是分布式系统中可持续计算的关键支柱。雾计算-云计算通过将云资源扩展到更接近数据源的雾计算节点，显著降低了时间敏感型IoT任务的延迟和带宽使用[2]。然而，由于资源异构性、动态工作负载以及需要同时优化相互冲突的目标（如完成任务时间、能源和成本），在这样的环境中进行任务调度仍然具有挑战性，使其成为一个复杂的多目标优化问题[4]。

尽管进行了大量的研究工作，但现有的任务调度解决方案仍存在一些根本性限制，这些限制阻碍了它们在现实世界场景中的性能。一个常见的问题是将任务视为同质集合，忽略了它们不同的计算特性、通信模式和时间约束[5]。这导致搜索空间探索效率低下和节点间通信开销过高，尤其是在大规模、异构的环境中[6]。缺乏在优化前对相似任务进行分组的前处理机制，加剧了这一问题，导致冗余计算和资源利用不足[7]。聚类技术已被证明可以提高复杂环境中的搜索效率，但它们在雾计算-云计算调度器中的集成仍然有限[8]。 Ali Baba和Forty Thieves（AFT）算法是一种受人类行为启发的元启发式算法，为解决这些挑战提供了有力的基础。该算法通过其独特的代理交互机制（包括小偷的协调搜索和女仆的防御策略），展示了探索与利用之间的强大内在平衡[9]。其简单的结构、少量的控制参数以及在各种工程设计问题中的有效性证明了它作为复杂现实世界应用核心优化器的潜力[9]。然而，原始的AFT是为单目标、连续数值优化设计的，缺乏处理具有资源限制的离散多目标问题所需的机制，这对雾计算-云计算任务调度来说是一个重大限制[10]。此外，虽然AFT显示出有希望的收敛行为，但其基本框架没有包含非支配排序或任何正式的档案管理系统来保留多样化的解决方案。当应用于多目标问题时，这种缺失可能导致帕累托前沿向狭窄区域收敛，从而导致解决方案多样性差和系统操作者的决策灵活性受限。缺乏识别和维持分布良好的非支配解决方案的结构化机制（如动态拥挤距离），使得算法在复杂的多模态搜索环境中容易过早收敛[11]。在需要同时平衡多个服务质量（QoS）指标的雾计算-云计算环境中，这一缺陷尤为重要[12]。此外，原始的AFT依赖于固定的代理移动和探索范围更新规则。这种静态配置虽然在早期探索阶段有效，但无法适应搜索过程的进展。随着种群的收敛，固定的步长可能导致在局部最优解附近停滞或过度扰动，从而破坏算法在后期实现高精度收敛的能力[13]。自适应策略已在其他元启发式算法中成功应用，以保持探索与利用之间的稳健平衡[14]，但它们在AFT框架中的应用尚未得到充分探索。

本文提出了一种针对雾计算-云计算环境的多目标任务调度框架，该框架将机器学习与元启发式优化相结合，以提高收敛速度和解决方案多样性。本文的主要贡献总结如下：

•
将基于DBSCAN的智能任务聚类机制集成到调度流程中，根据任务的资源需求对任务进行预处理，从而减少雾计算环境中的搜索空间异构性和通信开销。
•
通过非支配排序和动态拥挤距离，将改进的多目标Ali Baba和Forty Thieves（I_MOAFT）算法扩展为多目标优化引擎，能够生成一个分布良好的帕累托前沿，以实现完成任务时间和能源之间的复杂权衡。
•
引入了一种新颖的选择性精英主义与动态消除（SEDE）机制，通过结合基于密度的档案剪枝和高斯引导的扰动来主动管理外部档案，从而促进持续探索并防止过早收敛。
•
借鉴SAFT算法，将一种改进的自适应跟踪策略纳入I_MOAFT中，使每个搜索代理能够根据性能反馈动态调整其探索范围，从而在整个优化过程中保持全局搜索和局部细化的稳健平衡。
•
建立了一个全面的两阶段评估框架：（i）在标准基准函数上测试I_MOAFT算法以评估收敛性和多样性；（ii）在雾计算-云计算环境中使用真实世界科学工作流程评估整个调度框架，确保理论上的合理性和实际的可重复性。

本文的其余部分组织如下。第2节介绍了雾计算-云计算环境中的多目标任务调度问题表述。第3节回顾了相关工作及其局限性。第4节介绍了所提出的多层次框架。第5节详细介绍了I_MOAFT算法，包括非支配排序和新型SEDE机制。第6节在标准基准函数上评估了I_MOAFT。第7节使用基于Python的定制模拟平台进行了实际评估。最后，第8节总结了本文。

部分摘录

问题表述

本文解决了云雾计算框架中的多目标任务调度问题。工作负载由一个或多个科学工作流程组成，每个工作流程表示为一个有向无环图（DAG）。DAG正式定义为G = (V, E)，其中

T_{1}

T_{2}

T_{n}

是

T_{i}

T_{j}

个计算任务的集合，E表示表示它们之间优先级和数据依赖性的有向边

e_{i}

T_{j}

表示任务

T_{j}

在

T

开始执行之前必须等待

T

提出的框架

所提出的框架由三个相互连接的层组成——物联网（IoT）、雾计算和云计算，如图1所示。IoT层包括生成数据密集型任务的分布式设备，这些任务具有不同的服务质量（QoS）要求。这些任务根据它们的延迟敏感性和计算需求通过准入控制模块路由到雾计算层或云计算层。

提出的I_MOAFT任务调度算法

改进的多目标Ali Baba和Forty Thieves（I_MOAFT）算法是对原始AFT元启发式算法的全面扩展，重新设计用于解决雾计算-云计算环境中的复杂多目标任务调度问题。虽然原始AFT通过其基于故事的机制展示了探索与利用之间的良好平衡——其中小偷代表搜索代理，“Ali Baba的家”象征全局最优解——但它存在一些关键问题

定量和统计性能分析

为了严格评估所提出的改进多目标Ali Baba和Forty Thieves（I_MOAFT）算法的性能，使用具有不同帕累托前沿几何形状的多目标基准函数进行了一系列实验，包括凹形、凸形、不连续和欺骗性结构。选定的测试套件包括MMF5、MMF10、MMF12、MMF14及其变体（例如MMF10_l、MMF14_a、MMF15_l）——这些函数旨在挑战欺骗性

实验环境、工作流程模型和仿真设置

所提出的I_MOAFT任务调度框架通过Python进行了全面仿真评估。所有实验都在配备了Intel® Core™ i7-11800H处理器（2.30 GHz）、16 GB RAM和64位Windows 11 Pro操作系统的系统上完成。算法在MATLAB R2023b中实现，以确保一致性和可重复性。为了保证统计可靠性，每个实验独立执行了30次，结果取所有试验的平均值。

结论

本文提出了一种针对雾计算-云计算环境的多层任务调度框架，该框架结合了基于DBSCAN的聚类和改进的元启发式算法I_MOAFT。该框架首先根据任务的计算特性（CPU、内存、存储）对任务进行分组，以减少异构性和通信开销；然后使用I_MOAFT对每个聚类进行调度，通过非支配排序、动态拥挤距离和自适应机制改进了原始AFT算法