一种云中科学工作流下截止期限约束的费用优化调度方法

本发明属于云计算以及调度算法两大领域，尤其涉及一种云中科学工作流截止期限约束的费用优化调度方法。

科学工作流是处理特定顺序的任务集合，已成为规范化和结构化复杂科学过程的重要范式。随着科学计算系统的不断复杂化，其特征主要表现为数据密集型与计算密集型，需要更高性能的系统环境来执行大量的任务。云中科学工作流调度是根据一定的资源使用规则来分配与管理资源。它是一个N-P困难问题,也就是说没有确定的多项式来求最优解。对于工作流调度，在传统本地系统中得到了广泛的研究，如集、网络中；但在传统的本地系统中应用不仅非常昂贵，而且不方便扩展资源。而云计算作为一种将计算机基础设施和软件作为服务按需使用提供给用户的模式，适合用来执行科学工作流，可实现即付即用而且使用非常灵活。

云计算能为使用者提供其需要的计算能力，也就是可以租赁给用户无限的资源。值得注意的是，如今商业云计算服务供应商的收费模式一般为小时为最小计费单位(如Amazon EC2)，也就是说，无论我们租赁资源五十九分钟还是一秒钟，都均以一小时为单元进行租赁费用的收取。因此，如何在适当的时间(截止期限)内以较低的费用来执行任务成为了云中工作流的一个主要问题。对于云中科学工作流调度而言，好的调度方法或者策略，可以高效的完成任务-资源的映射以及有效的降低了租赁资源的费用。

本发明的目的在于：针对截止期限约束的云中科学工作流调度所租赁虚拟机所花费的费用问题，提出了一种云中科学工作流下截止期限约束的费用优化调度方法，旨在减少整个云中工作流任务租赁虚拟机的费用。

为了达到上述目的，本发明所采用的技术方案是：一种云中科学工作流下截止期限约束的费用优化调度方法，具体步骤如下：

步骤1：用户提交需求：用户提交工作流及相关的资源需求和整个工作流调度截止期限；

步骤2：对相关概念进行定义：包括对本文目标函数、约束条件、任务间的传输数据的通信开销、任务开始运行时间、结束运行时间等的定义；

步骤3：云中工作流任务排序：根据传统概率向上权值计算每个任务的权值并对任务降序排列得出任务序列SortedT；

步骤4：分配子截止期限：根据步骤3所得的任务概率向上权值为任务分配子截止期限；

步骤5：使用蚁算法进行任务调度：使用蚁算法对排好序的任务在满足子截止期限下使费用最小化调度至虚拟机，使得最终执行费用最低。

进一步地，本发明提出的云中科学工作流下截止期限约束的费用优化调度方法，所述的步骤1中用户所提交的工作流用有向无循环图G＝{T,E}来描述，图的节点T表示工作流中的任务集T＝{t1,t2,...,tn}共有n个任务，图的有向边E表示工作流中任务间的相互依赖关系集E＝{ei,j|ti∈T∩tj∈T}，其中ei,j表示任务ti为任务tj的前驱(也可以说任务tj为任务ti的后继)，即只有当任务ti执行结束后才能执行任务tj，而有向边上的权重表示任务间传递的数据集Data＝{datai,j|ti∈T∩tj∈T}，其中datai,j表示任务ti与任务tj之间传输的数据。

进一步地，本发明基于蚁算法的云中科学工作流费用优化调度方法，所述的步骤2中定义的目标函数为租赁所有虚拟机费用总和，约束条件为其完成时间需满足用户定义的截止期限。

s.t.WFE≤D (2)

其中LFl表示租赁虚拟机vml的结束时间，LSl表示租赁虚拟机vml的开始时间，Cl表示租赁虚拟机单位时间内所需费用，约束条件中，WFE表示整个工作流完成时间、D表示用户定义的截止期限。

进一步地，本发明基于蚁算法的云中科学工作流费用优化调度方法，所述的步骤5使用蚁算法对排好序的任务进行调度的过程是一个迭代的过程，具体迭代步骤如下：

步骤5.1：初始化蚁算法相关参数：相关参数包括初始蚁信息素τ0、启发函数矩阵ηn×m、信息素启发因子α、启发式因子β、迭代次数Itmax、蚁数量AntNmax等；

步骤5.2：迭代开始：判断是否已达到最大迭代次数Itmax，若没有达到，则执行步骤5.3，否则迭代结束，转到步骤5.9；

步骤5.3：计算转移概率：蚂蚁antk从任务序列SortedT中依次取任务并计算任务ti分配至虚拟机vml的概率；

步骤5.4：选择虚拟机：为任务根据概率选择公式以及满足子截止期限调度虚拟机。

步骤5.5：判断蚂蚁antk是否完成搜索，若已完成搜索则转到步骤5.7，否则转到步骤5.3。

步骤5.6：局部更新信息素

步骤5.7：判断是否所有蚂蚁都已完成搜索，若已全部完成搜索则转到步骤5.9，否则转到步骤5.3。

步骤5.8：全局更新信息素并记录局部最优调度方案

步骤5.9：输出全局最优调度方案。

进一步地，本发明基于蚁算法的云中科学工作流费用优化调度方法，所述的步骤5.3中，定义启发函数矩阵ηn×m，矩阵的每一行代表一个任务，每一列代表一个虚拟机，其中的ηi,l值代表任务ti分配至虚拟机vml的启发函数值。

我们定义执行费用的倒数作为启发项，也就是任务ti在虚拟机vml上执行所消耗的费用，定义公式如公式4所示，定义ECi,l为任务ti在虚拟机vml上的执行费用，定义公式如式5所示。

转移概率公式为：

其中，τi,l表示路径(i,l)上的信息素浓度；α为信息素启发因子，表示蚂蚁在路径上留下的信息素的重要性，越大说明信息素对后面其他蚂蚁选择路径的影响越大；β为期望启发因子，反映了启发函数的重要性，β越大说明蚂蚁在移动过程中启发信息受重视程度越高。

本发明提供的优化调度方法具有如下优点和有益效果：本发明考虑到科学工作流中任务间相互约束的特性，利用传统概率向上权值对任务的执行顺序进行排序，然后使用蚁算法进行截止期限约束下以优化租赁费用为目标的任务-资源间的调度，此方法可有效降低任务租赁虚拟机的费用。

图1为云工作流调度系统模型图

图2为本发明提供的云中科学工作流下截止期限约束的费用优化调度方法流程图；

图3为云工作流实例结构图；

为了使本领域技术人员更好地理解本申请中的技术问题、技术方案和技术效果，下面结合附图和具体实施方式对本发明一种云中科学工作流下截止期限约束的费用优化调度方法作进一步详细说明。

本发明提出的优化调度系统模型的具体流程如图1所示：用户提交工作流及相关的资源需求和截止期限；工作流管理系统(WMS)接收到用户的需求后，自动执行资源获取、任务调度和工作流执行。更详细地说，资源容量估计分析工作流结构以确定所需的计算资源量，资源获取模块与外部资源配置系统进行协商，获取满足所需求的确定资源数量，一旦分配了适当的资源，执行管理器将与工作流调度模块协调，完成工作流任务与资源之间的映射，并引导在执行管理器上运行任务。

如图2为本发明的方法具体实施步骤：

步骤1：用户提交工作流G＝{T,E}及整个工作流调度截止期限D；具体实例如图3所示，实例中每个顶点表示一个任务，此实例中共有13个任务；有向线段代表了任务间相互约束的关系，如从任务t2指向任务t8的有向线段表示任务t2为任务t8的前驱；有图中有向边上的数字表示任务间传输的数据，如从任务t2到任务8的有向边上的数字3代表从任务t2传输到任务8的数据量为单位3。

步骤2：本发明假设共有m种虚拟机VMs＝{vm1,vm2,...,vmm}且都处于同一数据中心下，那么所有虚拟机带宽(也就是bw)相同。对于任务ti与任务tj之间传输数据的通信开销，定义公式如下。

因工作流中任务间存在相互约束的特性，对于任务ti而言，只有当所有前驱任务均已结束执行且将传输数据传输到本身后，方可开始执行，任务ti的开始执行时间定义如公式8，其中由于t1无前驱，则开始执行时间为0。

当把任务ti分配至虚拟机vml进行执行时，其执行时间由虚拟机的处理能力以及任务i的大小决定，可由公式9计算可得。其中ETi,l表示任务ti被分配至虚拟机vml的执行时间，size(ti)表示任务ti的数据量大小，p(vml)表示虚拟机vml的处理能力。

当任务ti分配给虚拟机vml执行结束的时刻也就是任务ti的结束执行时间，其由执行开始时间与在虚拟机上执行所需时间共同决定，定义公式如公式10所示。特别地，工作流中的最后一个任务tend执行结束时便代表整个工作流执行结束，也就是工作流的完成时间为任务tend的结束执行时间，定义公式如公式11所示。

EFTi＝ESTi+ETi,l (10)

WFE＝ExFTend (11)

步骤3：本发明根据HEFT中将任务i的概率向上权值Ri定义为从本身至tend的关键路径长度,定义公式如公式12所示，其中TTi,j由公式1计算可得，表示任务ti的平均执行时间，定义公式如公式13所示。根据概率向上权值Ri的大小对工作流中所有任务进行优先级大小排列，得任务排序队列SortedT。

步骤4：工作流的起始任务为t1，由公式10可知工作流的关键路径为任务t1的概率向上权值R1，SubDi表示任务ti的子截止期限，当任务分配至虚拟机进行运行其结束执行时间需满足对应的子截止期限，定义公式如公式14所示。其中，D为给出的总的截止期限。

步骤5.1：初始化蚁算法相关参数：相关参数包括初始蚁信息素τ0、启发函数矩阵ηn×m、信息素启发因子α、启发式因子β、迭代次数Itmax、蚁数量AntNmax等；

步骤5.2：迭代开始：判断是否已达到最大迭代次数Itmax，若没有达到，则执行步骤5.3，否则迭代结束，转到步骤5.10；

步骤5.3：计算转移概率：蚂蚁antk从任务序列SortedT中依次取任务并计算任务ti分配至虚拟机vml的概率；

转移概率公式为：

其中，τi,l表示路径(i,l)上的信息素浓度；α为信息素启发因子，表示蚂蚁在路径上留下的信息素的重要性，越大说明信息素对后面其他蚂蚁选择路径的影响越大；β为期望启发因子，反映了启发函数的重要性，β越大说明蚂蚁在移动过程中启发信息受重视程度越高。

定义启发函数矩阵ηn×m，矩阵的每一行代表一个任务，每一列代表一个虚拟机，其中的ηi,l值代表任务ti分配至虚拟机vml的启发函数值。

我们定义执行费用的倒数作为启发项，也就是任务ti在虚拟机vml上执行所消耗的费用，定义公式如公式17所示，定义ECi,l为任务ti在虚拟机vml上的执行费用，定义公式如式18所示。

步骤5.4：选择虚拟机：为任务根据概率选择公式以及满足子截止期限调度虚拟机。

步骤5.5：判断蚂蚁antk是否完成搜索，若已完成搜索则转到步骤5.7，否则转到步骤5.3。

步骤5.6：局部更新信息素：若一只蚂蚁完成对任务的调度，则进行局部更新信息素，转到步骤5.3，否则转到步骤5.4。局部信息素更新公式为：

其中Δτki,l为路径(i,l)上第k只蚂蚁遗留的信息素增量矩阵之和，Q表示信息素强度常量，TLCk为第k只蚂蚁使用虚拟机的所有费用。

步骤5.7：判断是否所有蚂蚁都已完成搜索，若已全部完成搜索则转到步骤5.9，否则转到步骤5.3。

步骤5.8：全局更新信息素并记录局部最优调度方案；

全部信息素更新公式为：

τi,l(t+1)＝(1-ρ)τi,l(t)+Δτi,l (20)

其中ρ表示信息素挥发系数；(1-ρ)表示信息素的残留因子，为了防止信息素无限积累，取值范围限定在0～1之间；Δτi,l表示路径(i,l)上所有蚂蚁遗留的信息素增量矩阵之和，由公式21计算可得。

步骤5.9：输出全局最优调度方案。

以上实例仅用以说明本发明而非限本发明所描述的技术方案，对于本领域技术人员应该理解，对上述发明所公开的云中科学工作流下截止期限约束的费用优化调度方法，在不脱离大名远离的前提下，还可以在此基础上做出改进，这些改进也视为本发明的保护范围。