云平台下任务调度的克隆选择范文

《计算机应用研究杂志》2015年第五期

1问题建模和相关定义

1.1工作流任务模型工作流任务由存在相互依赖关系的子任务构成，这些子任务构成有向无环图(DirectedAcyclicGraph，DAG)，用二元组表示为G=(N,E)，其中N代表一组节点，E代表连接节点的边，边上的数字代表边的权重。典型的DAG工作流任务模型如图1所示。

1.2相关定义用T表示DAG中的节点集合，用来描述任务集T={t1,t2,…,tn}，n表示任务总数。用E表示有向边的集合，用来描述任务之间的依赖关系，E={eij|eij=(ti,tj),eij∈T×T}，任务tj必须在其前驱任务执行完成后才能开始处理。任务的完成时间、执行费用定义和计算方法如下，其中相关符号说明如表1所示。假定任务ti分配在资源Rk上执行，tr(Rk)表示资源Rk的通信能力，data(ti,tj)表示任务ti和tj之间数据传输的通信量，本文采用式1来计算任务ti到tj数据传输的通信时间。cp(Rk)表示资源Rk的计算性能，load(ti)表示任务ti的计算量，本文采用式2来计算任务ti在资源Rk上的执行时间.

2TCCS任务调度算法

受生物克隆选择机理的启发，DeCastro[12]等人提出克隆选择算法，其本质是一种高效、并行的全局搜索方法。本文基于CSA思想，提出一种TCCS改进算法。

2.1染色体编码本文采用字符编码方式，将任务占用的资源序列编码为染色体。假定工作流任务包含10个任务，云平台提供5个可用资源，则染色体长度为10，每个基因取值为1~5之间的随机数。染色体的编码如图2所示，任务1资源1上面执行，任务2在资源3上面执行，以此类推。

2.2种群初始化在GSA中，初始化种群对算法性能有重要的影响。随机种群可能导致算法收敛过慢，或者最终结果不够理想。本文认为DAG中任务所处层级越高，则任务优先级越高，如图1中任务t1级别高于任务t4。本文采用前驱任务优先调度策略快速生成可用初始种群.

2.3亲和度函数亲和度函数的选取至关重要，直接影响到算法的收敛速度和最优解的查找。本文将工作流任务完成所需要的时间和经济成本的加权值作为亲和度函数，因此需要对这两种属性的数据进行无量纲化处理。对于每一批进化的种群，用minFinish表示该批种群中任务完成时间最小值，maxFinish表示任务完成时间最大值，用minCost表示该批种群中经济成本最小值，maxCost表示经济成本最大值。则亲和度函数可表示为公式10，其中ω1和ω2为任务完成时间和经济成本的加权因子，且ω1+ω2=1.

2.4免疫基因操作本文采取交叉变异和基因变异两步对抗体进行免疫基因操作，以增加抗体种群的多样性，避免种群过早收敛。交叉变异将两个抗体交换基因片段，形成两个新的个体。它可以促进不同抗体之间的基因交流，有利于丰富种群的多样性。交叉变异可以表示为公式11，每次随机选取抗体中相同位置的连续两位基因片段进行交换，其中n表示工作流任务的个数。基因变异将是在基因编码的层面对抗体进行变异。本文选取交换突变的方式进行基因变异。在抗体基因编码中，随机选择两个位置，并交换其取值。例如抗体基因编码为：1423542351，随机选取第3位与第9位基因编码进行交换突变，则突变的结果为1453542321。

2.5克隆选择算法步骤n表示任务总数，m表示资源节点数，N表示迭代代数最大值。步骤一：抗体初始化。本文根据4.2介绍的初始种群生成方式生成一组可行的调度方案，采用实数编码方式对任务所分配的资源序号进行编码。步骤二：亲和度计算。按照公式8计算抗体亲和度f(ti)，本文选取ω1=ω2=0.5，表示任务完成时间和任务执行成本权重相同。f(ti)的值越小，表示解越优，若f(ti)达到理想值f*，或迭代次数达到最大值N，则停止计算，否则继续。步骤三：抗体选择。按一定的概率ρr选择亲和度高的抗体形成一个临时抗体群tmp{r}。步骤四：抗体克隆。tmp{r}中的抗体独立进行克隆，亲和度越高的抗体，抗体克隆的数量越多，抗体t的克隆数目Ci如式12所示，其中α为克隆调节系数，fmax为当前抗体中的最大亲和度，M为群体规模。

3实验结果与分析

3.1实验目的为验证TCCS算法的正确性和有效性，本文设计了云平台工作流任务调度的仿真实验，并在相同实验条件下与遗传算法进行对比。实验主要在算法收敛时间、任务完成时间—经济成本加权值两个方面进行比较。

3.2实验环境实验采用开源云仿真平台CloudSim[13]，它是澳大利亚墨尔本大学网格实验室和Gridbus项目组推出的云计算仿真软件。在该试验平台上分别测试了上述两种算法的调度时间、任务完成时间和经济成本。对图1所示的工作流任务，实验的相关参数取值如下：1)任务：每个任务的计算量随机产生，取值范围为[100,500]，本次实验中任务的计算量取值如下，单位是MI:Load={120,472,255,398,161,340,263,117,382,453}。前驱任务与后继任务之间的数据传输量如图1所示。2)虚拟机：计算资源中虚拟机的个数为5，计算能力取值为cp={2,4,6,8,10}，单位是MIPS。虚拟机之间的通信能力矩阵如下Tr所示，单位是ms(millisecond).3)参考SinaAppEnginge[14]的服务价格，设置资源任务计算的服务单价为0.03，通信带宽的服务单价为0.2。4)加权因子：设置任务完成时间和经济成本的加权因子ω1=0.5，ω2=0.5。

3.3实验结果分析本文选择遗传算法GA与TCCS算法进行对比试验。TCCS算法的相关参数设置为：种群规模为20，交叉变异与突变概率均为0.5，抗体记忆的比例为0.05。GA的相关参数为：种群规模为20，交叉变异与突变概率均为0.5。两个算法终止条件均为迭代500次后终止。实验中，两个算法的种群规模均为20，则算法的收敛速度取决于种群对问题空间的搜索能力。图3、图4为两种算法分别重复运行10次的实验结果。实验1：算法收敛时间对比测试算法收敛时间是指算法从执行开始到算法收敛的时间，值越小，算法的执行时间越短，可以更快的得到任务调度的结果。两种算法的收敛时间测试结果如图3所示。从图3中可以看出，TCCS算法收敛时间在4S以下的实验占60%，10次实验的平均收敛时间为4.21S，GA收敛时间在4S以下的实验占仅为10%，10次实验的平均收敛时间为5.64S。可见TCCS算法收敛速度相对GA较快，这是因为TCCS算法在种群初始阶段，采用简单策略生成一批可用的初始种群，避免了随机种群引起算法收敛速度慢的问题。实验2：任务完成时间与经济成本加权值对比测试任务完成时间与经济成本加权值通过公式10进行计算，该值越小，表明算法探索任务完成时间与经济成本多目标优化问题最优解的性能越好。两种算法的工作流任务调度测试结果如图4所示。从图4中可以看出，TCCS算法10次实验的任务完成时间与经济成本平均加权值为0.51，最小值为0.29，加权值在0.6以下的实验占70%，GA10次实验的任务完成时间与经济成本平均值为0.63，加权值在0.6以下的仅为40%。可见TCCS算法探索任务完成时间与经济成本最优解方面性能更优，这是因为TCCS算法在传统克隆选择算法的基础上增加了交叉变异算子，在抗体种群多样性方面进行了优化。

4结束语

本文结合云计算的特点，提出了一种对任务完成时间，经济成本多目标优化的克隆选择改进算法。在CloudSim仿真平台下，把TCCS算法与解决任务调度问题常用的GA进行了对比实验。实验表明，TCCS算法是有效的。需要注意的是，本文只考虑了任务完成时间和任务执行的经济成本的多目标优化，没有考虑云平台下资源的负载均衡问题，这也是本文下一步的研究重点。

作者：徐立 梁意文 单位：武汉大学 计算机学院