MHeedra：在异构多用户边缘-云平台上实现支持复制的任务调度

《Future Generation Computer Systems》：MHeedra: Putting Duplication-Enabled Task Scheduling Within Heterogeneous Multi-User Edge-Cloud Platforms to Work

任务调度在边缘云平台中面临异构资源、通信延迟和多用户场景的复杂挑战，本文提出MHeedra框架，结合MILP模型与ACO元启发式算法，支持任务复制和动态调度以优化QoS。实验表明MHeedra-ACO达到63.33%的CPLEX最优解，任务复制使延迟提升1.45倍。

　　在当前快速发展的数字技术环境中，边缘计算与云计算的结合成为解决高性能计算需求的重要手段。边缘计算平台通过将计算资源部署在网络的边缘，即靠近数据源的位置，能够有效缓解数据本地性带来的性能问题。同时，云计算通过其强大的计算能力和广泛覆盖的网络连接，提供了更远距离的计算支持。然而，由于边缘计算和云计算之间存在资源异构性、传输能力差异以及多层级架构的复杂性，如何高效地在这些平台之间调度任务成为一大挑战。

本研究提出了一种名为MHeedra的任务调度框架，旨在解决边缘-云混合计算环境中的任务放置问题。MHeedra基于混合整数线性规划（MILP）模型设计，进一步演化为一种蚁群优化（ACO）元启发式算法，从而能够在大规模实际场景中进行高效调度。这一框架的核心目标是优化任务的分配方式，使得计算任务能够被合理地分配到不同层级的计算资源，同时兼顾任务复制带来的优势，以减少数据传输的延迟，提高响应效率。

在边缘-云混合计算环境中，任务的执行往往受到多种因素的影响。首先，计算资源的异构性意味着不同的计算节点具有不同的处理能力和存储容量。其次，数据传输的延迟和带宽限制对整体性能有显著影响。此外，多用户共享同一计算资源池，使得任务调度不仅要考虑单个任务的执行时间，还要考虑多个用户的请求优先级和资源占用情况。因此，设计一种能够同时满足这些需求的任务调度策略显得尤为重要。

MHeedra-MILP模型通过引入多个决策变量，如任务是否被分配到特定资源、任务之间的执行顺序以及任务复制的可行性，来优化任务放置方案。这些决策变量能够帮助模型在满足硬性约束的同时，尽量减少软性约束的违反。硬性约束包括任务必须按顺序执行、不允许任务抢占以及所有任务必须被分配到合适的资源。软性约束则涉及任务的执行时间、数据传输延迟以及资源利用率等因素。

为了验证MHeedra-MILP模型的有效性，我们设计了一种基于参数化的实例生成器，用于模拟实际的边缘-云平台和工作负载。该实例生成器能够生成不同规模和复杂度的任务调度问题，从而为模型的评估提供丰富的数据支持。通过将MHeedra-MILP模型与CPLEX的最优解进行对比，我们的实验结果显示，MHeedra-ACO在所有实例和所有运行中能够匹配63.33%的最优解。这一结果表明，MHeedra-ACO在大规模任务调度问题中具有较高的求解精度和效率。

在实际应用中，任务复制是一种有效的优化手段。通过将任务复制到多个计算节点，可以减少任务之间的数据传输延迟，提高整体的响应速度。然而，任务复制也会带来额外的计算开销，因此需要在任务复制和计算效率之间找到平衡。我们的实验表明，在传输受限的工作负载中，任务复制可以带来高达1.45倍的延迟改善，但同时也需要合理控制资源占用，以避免对其他任务的执行造成影响。

此外，为了应对多用户和多层级平台的复杂性，MHeedra框架引入了任务捆绑的概念。任务捆绑将多个任务组合成一个用户请求，从而能够在保持任务细粒度调度的同时，提高资源利用率和调度效率。这种设计使得调度器能够更好地处理来自不同用户的请求，同时确保任务的执行顺序和资源分配符合实际需求。

在任务调度过程中，如何平衡任务复制与计算资源的使用是一个关键问题。我们的实验表明，MHeedra-ACO算法在处理任务复制时，能够有效地减少网络通信开销，同时保持较高的计算效率。通过引入一种基于ε-贪婪策略的蚁群优化算法，MHeedra-ACO能够在大规模任务调度问题中找到接近最优的解决方案。这一算法的设计不仅考虑了任务的执行顺序和资源分配，还结合了任务复制的可行性，从而在实际应用中提供了更高的灵活性和适应性。

为了进一步验证MHeedra框架的性能，我们设计了多个实验场景，涵盖了不同规模和复杂度的任务调度问题。这些场景模拟了实际的边缘-云平台和工作负载，包括任务的释放时间分布、任务的执行时间以及生成的数据量等因素。通过这些实验，我们能够全面评估MHeedra-MILP和MHeedra-ACO算法在不同情况下的表现，从而为实际应用提供可靠的理论支持。

在实验结果中，我们发现MHeedra-ACO在处理任务复制时，能够显著减少网络通信延迟，同时保持较高的任务完成率。这表明，MHeedra-ACO在实际应用中具有较高的实用性。此外，通过对比不同算法在相同任务调度问题中的表现，我们能够进一步验证MHeedra框架的优越性。实验结果显示，MHeedra-ACO在大多数情况下能够提供接近最优的解决方案，同时保持较高的计算效率和资源利用率。

综上所述，MHeedra框架通过结合混合整数线性规划模型和蚁群优化算法，为边缘-云混合计算环境中的任务调度问题提供了一种高效的解决方案。该框架不仅能够优化任务的分配方式，还能够有效减少网络通信延迟，提高响应速度。通过设计合理的任务复制策略和任务捆绑方法，MHeedra框架能够在多用户和多层级平台中实现更高的调度效率和资源利用率。这些研究成果为未来的边缘-云计算研究提供了重要的理论支持和实践指导。