基于改进差分进化算法的云端科学工作流调度自适应故障检测策略

原题目：An adaptive fault detector strategy for scientific workflow scheduling based on improved differential evolution algorithm in cloud

Abstract

讨论了在云计算环境中执行大规模科学工作流程的挑战，并提出了一种基于改进差分进化算法的自适应故障检测器策略，以最小化能源消耗、总成本和时间，并在调度科学工作流程时容忍故障。此外，该文章还介绍了一种自适应基于网络的模糊推理系统（ANFIS）预测模型，用于主动控制资源负载波动并提高故障预测准确性。

通过对文章的阅读了解容错到底是什么

Introduction

介绍了在大规模的云计算环境中，错误会导致用于计算的虚拟机不可用，因此，通过提出一个有效且高效的容错策略来对错误发生时的问题进行处理是很有必要的。

传统方法进行容错的实现是需要了解云计算结构以及大量的知识和经验的，在实施时代价昂贵，且在缺少建模的条件下无法准确地进行容错评估。

在很多现实世界的工作流调度中，多目标优化方法可以用于优化虚拟机的任务调度以满足用户需求。然而大多数的现有方法并未考虑到容错技术的使用。

Differential evolution算法很高效，但也有陷入局部最优以及收敛过慢的问题，因此本文通过优化F和CR参数来解决这些问题

总的来说，本文的贡献是提出了一种自适应故障容错工作流调度方法，该方法基于改进差分进化算法和多目标IDE算法，结合主动和反应技术。该方法通过应用自适应基于网络的模糊推理系统（ANFIS）预测模型来预测未来资源负载，从而主动控制资源负载波动并提高故障预测准确性。此外，在故障/失败发生后，该方法还通过反应性容错控制器来保证应用程序执行的可靠性。这种方法可以最小化能源消耗、总成本和时间，并在调度科学工作流程时容忍故障。

本文的相关工作主要讨论了故障检测和容错技术在云计算环境中的应用。文章指出，故障发生在系统中表明任务执行能力的无法实现，可能发生在网络的任何节点或任何过程中的不同组件中。相关工作还探讨了云计算环境下的工作流调度问题，并介绍了一些传统方法，如遗传算法、蚁群算法和粒子群优化算法等。此外，相关工作还介绍了一些基于云计算环境的故障检测和容错技术，如虚拟机迁移、备份和恢复等。

Workflow model

本文的工作流模型使用了直接无环图（DAG）来表示云计算环境中的工作流。该模型由一组任务和任务之间的依赖关系组成，其中每个任务都有一个权重，表示其参考值。具体地，该模型可以表示为： $W=(T,D)$ 其中，$T={T_0,T_1,…,T_n}$是一组任务，$D={(T_i,T_j)|T_i,T_j \in T}$是任务之间的依赖关系集合。每个任务都有一个权重$w_i$，表示其参考值。因此，我们可以将工作流模型表示为一个带权有向无环图（weighted directed acyclic graph），如下所示： $$G=(V,E)$$ 其中，$V={v_0,v_1,…,v_n}$是节点集合，对应于任务集合$T$；$E={(v_i,v_j)|w_{ij}\neq 0}$是边集合，对应于依赖关系集合$D$。

DAG是一种有向无环图，其中每个节点表示一个任务，每条边表示任务之间的依赖关系。在云计算环境中，DAG通常用于表示工作流模型，其中每个任务都有一个权重，表示其参考值。DAG可以帮助我们更好地理解和可视化工作流程，并且可以用于优化工作流程的调度和执行。在本文中，作者使用了一个样例DAG来说明其应用。

Proposed framework

本文的proposed framework主要提出了一种基于自适应故障容错技术的多目标工作流调度框架。该框架使用了主动和反应技术来控制资源负载波动，并通过反应性容错控制器来保证应用程序执行的可靠性。具体来说，该框架包括以下组件：

Workflow task queue：将用户提交的工作流程按照一定规则排列在队列中，等待分配到云数据中心的虚拟机上执行。
MAPE-k control loop：该控制循环由四个组件组成，包括monitor、analyzer、planner和executer。这些组件共享一个知识库，用于监测、分析、计划和执行工作流程。
ANFIS prediction model：该模型是一种自适应基于网络的模糊推理系统，用于预测未来资源负载，并通过主动控制资源负载波动来提高故障预测准确性。
Reactive fault-tolerant controller：该控制器是一种反应性容错技术，用于在故障/失败发生后保证应用程序执行的可靠性。

本文提出的框架可以最小化能源消耗、总成本和时间，并在调度科学工作流程时容忍故障。

Monitor component

Monitor component被描述为一个组件，其主要职责是收集云数据中心中的工作流任务信息和资源负载率。具体来说，用户传感器和资源传感器会在预定的时间间隔内从应用程序和云环境中收集足够的数据，并将其提供给Monitor component。其中，用户传感器的职责是收集用户工作流任务的信息（如请求速率、类型、大小等），而资源传感器的职责是收集资源负载率的信息（如CPU负载、应用内存和网络流量）。Monitor component会将监测到的数据进行整合，并存储在知识库中以供分析组件使用。

Analyzer component

在本文中，Analyzer component被描述为一个组件，其主要职责是分析Monitor component收集到的负载信息，并预测未来的资源负载。具体来说，Analyzer component使用ANFIS神经网络模型来预测未来的资源负载，并根据Monitor component的反馈进行调整。预测值会被传输到Planner component中，以便根据系统条件自适应地选择工作流调度算法。通过分析和预测资源负载，Analyzer component可以帮助实现负载均衡和最佳性能。

当Analyzer component接收到Monitor component传递的数据后，它会使用ANFIS神经网络模型来预测未来的资源负载。ANFIS模型是一种自适应基于网络的模糊推理系统，可以处理非线性和动态系统，并具有良好的泛化能力。在本文中，ANFIS模型被用于预测未来的资源负载，并根据Monitor component的反馈进行调整。具体来说，当预测值与实际值不匹配时，Analyzer component会根据误差信号对ANFIS模型进行调整，以提高预测准确性。除了资源负载预测外，Analyzer component还可以执行其他分析任务，例如检查工作流任务之间的依赖关系、计算任务权重和优先级等。通过这些分析任务，Analyzer component可以帮助实现更好的工作流调度和执行效果。

Fuzzy Planner component

在本文中，Fuzzy Planner component被描述为一个组件，其主要职责是根据Analyzer component预测的资源负载来分配工作流任务到高效的云资源上。具体来说，Fuzzy Planner component使用三个模糊if-then规则来进行工作流任务分配：

如果资源负载被预测为正常，则执行“无变化”命令，并调用IDE调度算法。
如果资源负载被预测为高，则执行“未来可能发生错误”的命令，并调用主动容错控制器以减少负载。
如果资源负载被预测为非常高，则执行“故障发生”的命令。

这些规则是基于模糊逻辑和经验知识设计的，并可以根据实际情况进行修改和优化。通过使用Fuzzy Planner component，可以实现更好的工作流任务分配和资源利用率。

IDE算法

在本文中，IDE算法的具体设计内容如下：

初始化种群：首先，随机生成一组初始解作为种群，并计算每个解的适应度值。
变异操作：对于每个个体，随机选择另外两个不同的个体，并计算它们之间的差异向量。然后，将差异向量与当前个体进行加权和操作，得到一个新的变异向量。
交叉操作：将变异向量与当前个体进行交叉操作，得到一个新的解。
选择操作：根据适应度函数选择最优解，并将其作为下一代种群中的父代。
自适应参数设置：通过自适应参数设置技术来调整IDE算法中的参数。

具体来说，通过监测种群中最优解和平均适应度值之间的差异来调整缩放因子和交叉概率等参数。通过以上步骤，IDE算法可以在连续空间中寻找最优解，并且具有较好的收敛速度和搜索能力。

在本文中，IDE算法优化的目标是最小化工作流任务的makespan、总成本和能源消耗。具体来说，IDE算法的目标函数可以表示为：

$ f(x) = w_1 \times makespan(x) + w_2 \times cost(x) + w_3 \times energy(x) $

其中，$x$表示工作流任务的调度方案，$makespan(x)$表示完成所有任务所需的时间，$cost(x)$表示执行任务所需的总成本，$energy(x)$表示执行任务所需的总能源消耗。$w_1, w_2, w_3$是权重系数，用于平衡不同目标之间的重要性。通过优化上述目标函数，IDE算法可以得到一个最优的工作流调度方案，以实现更好的性能和效率。

Proactive fault-tolerance controller

在本文中，Proactive fault-tolerance controller被描述为一种主动容错控制器，其主要目的是防止进入故障区域并将新负载分配给异常的虚拟机。具体来说，当Analyzer component检测到资源负载过高时，Fuzzy Planner component会调用Proactive fault-tolerance controller来减少负载并防止系统进入故障状态。

Proactive fault-tolerance controller的实现方式是通过监测虚拟机的资源利用率和性能指标来判断是否存在异常情况。如果发现某个虚拟机出现了异常情况，则Proactive fault-tolerance controller会立即将其从负载均衡中移除，并将其上的任务重新分配给其他正常的虚拟机。这样可以避免故障扩散和系统崩溃。

总之，Proactive fault-tolerance controller是一种有效的容错控制器，可以帮助云环境实现更好的容错性能和可靠性。

Reactive fault-tolerance controller

在本文中，Reactive fault-tolerance controller被描述为一种响应式容错控制器，其主要目的是在故障发生后减少故障的影响。具体来说，当Analyzer component检测到某个虚拟机出现故障时，Fuzzy Planner component会调用Reactive fault-tolerance controller来处理故障并恢复系统正常运行。

Reactive fault-tolerance controller的实现方式是通过使用复制技术来提供容错能力。具体来说，当某个虚拟机出现故障时，Reactive fault-tolerance controller会将该虚拟机上的任务复制到其他正常的虚拟机上，并重新分配这些任务以保证系统正常运行。这样可以避免任务丢失和系统崩溃。

需要注意的是，Reactive fault-tolerance controller的主要缺点是成本较高。因为它需要额外的资源和计算能力来处理故障和执行复制操作。因此，在实际应用中需要权衡成本和性能之间的关系，并选择合适的容错策略。

总之，Reactive fault-tolerance controller是一种有效的容错控制器，在云环境中可以帮助提高系统可靠性和容错性能。

Executer component for the workflow tasks allocation

执行组件负责根据调度阶段执行的算法将用户发送的所有请求分配给现有的虚拟机。该组件负责实际执行规划组件决定的操作。

Performance evaluation

实验部分不作具体分析

在本文中，“Performance evaluation”部分描述了作者如何评估所提出的工作流调度算法的性能。具体来说，作者使用了WorkflowSim-1.0工具包和CloudSim模拟器来模拟云环境中的工作流，并评估所提出的算法在不同负载下的性能表现。

在实验中，作者使用了一组实验设置，包括虚拟机数量、任务数量、任务大小等参数。通过对这些参数进行不同组合和调整，作者可以模拟不同负载下的云环境，并评估所提出算法的性能表现。

最终，作者通过比较所提出算法和其他常用算法（如HEFT、Min-Min等）在不同负载下的性能指标（如makespan、总成本等）来评估其性能。实验结果表明，所提出算法可以显著提高系统性能和效率，并且在各项指标上均优于其他常用算法。

总之，“Performance evaluation”部分描述了作者如何评估所提出算法的性能，并给出了实验结果和结论。这些结果可以帮助读者更好地理解该算法的优点和局限性，并为进一步研究和应用提供参考。

Conclusion and future work

“Conclusion and future work”部分是本文的结论和未来工作方向。具体来说，该部分总结了本文的主要贡献和发现，并提出了一些未来研究的方向。

在结论部分，作者指出所提出的工作流调度算法可以显著提高云环境中的性能和效率，并且在各项指标上均优于其他常用算法。作者还强调了该算法的可扩展性和适应性，并指出它可以应用于不同类型的云环境和工作流场景。

在未来工作方向中，作者提出了一些有待进一步研究的问题，如如何进一步优化算法性能、如何处理更复杂的工作流场景、如何实现更高效的容错机制等。这些问题都是当前云计算领域面临的挑战，也是未来研究需要解决的重要问题。