一种多目标约束条件的云计算资源调度算法*

张素芹,徐 飞

(1.西安工业大学 理学院,西安 710021；2.西安工业大学 计算机科学与工程学院,西安 710021)

云计算是近几年逐渐兴起的一种技术，各行业利用云计算的主要目的是资源共享和协同工作。然而面对云计算规模庞大服务器系统以及具有多样性和动态性的资源，用户群体本身各不相同，用户提出的对任务的目标约束条件各不相同，这些任务调度在基于云计算环境下的问题变得非常棘手。如何对云计算系统中资源有效调度，合理分配管理，使得海量的用户任务调度开支低，完成时间短，负载水平均衡，资源利用率高[1]，成为云计算领域中研究的热点和难点问题[2]。

目前大量专家学者和技术人员从事云计算任务调度研究问题，也提出了大量的独特见解。文献[3]提出了一种基于粒子群优化的算法，仅考虑了任务的截止时间和预算两个约束条件，该算法对云计算调度和资源分配有较好的通用性；文献[4]从服务商角色考虑，能最小化成本，但未考虑系统负载均衡，这样不仅浪费资源也影响其收益。文献[5]提出了基于服务质量等级划分新的调度模型；文献[6]提出一种算法是和贪心算法相结合，考虑用户的满意度的约束条件，但没有完全考虑供应商的成本；文献[7]从资源利用率和云服务收益成本角度出发，提出了一种新颖且实用的任务调度算法，该算法能很好的缩短任务完成时间，但未能综合考虑多质量等级划分目标约束条件。文献[8]提出的算法考虑了负载均衡，通过对服务器设置服务序列和负载均衡指数参数，利用服务器对任务进行连接数约束选择，使系统达到设定的负载均衡度，有效缩短完成时间，达到系统优化的目的，这种算法缺点是未考虑成本问题，使得执行时任务成本很高。文献[9]提出的任务调度算法基于并行遗传算法，该方法在某种程度上缩短了任务调度的总执行时间，但却会使算法陷入局部解，求解精度难以保证。文献[10]考虑了任务执行时间以及用户信任度等质量等级划分约束条件，该策略能够使系统负载保持均衡，缩短了任务的执行时间，但执行成本较高。

文中针对云计算环境下用户对资源调度提出的各不相同的多目标约束条件问题,提出一种基于多目标约束条件的云计算任务调度算法，此算法不仅能够有效降低任务调度时的截止时间底线违背率，还能节约平均执行成本和缩短平均任务执行时间。

1 多目标约束条件的任务调度算法

1.1 多目标调度模型构建

本文约定一些定义和假设。文中提出的多目标约束条件主要考虑截止时间底线(Deadline,DL)和调度预算(Budget,Bg)两种。 DL为用户提出任务调度申请至调度完全结束时，能够接受的最长时间；Bg为用户愿意为此次任务调度支出的费用。

任务调度问题描述：假设云计算系统中有m个计算节点,等待调度的任务有n个，用集合表示为P={P1,P2,P3,…,Pm},T={t1,t2,t3,…,tn}。S(Pm,Rk)为Pm节点能为Rk提供的计算能力。R(tn,Rk) 为任务tn被系统调度时，调度可用资源Rk所需要的计算能力。Bn为调度tn时的预算。C为m×n矩阵，表示为

(1)

元素cij为将任务ti分配到节点Pj上时，其是否进行调度，当cij=1,为正在调度，cij=0 为未调度。vij为比率，表示当ti执行时，其实际执行时间与调度其时花费的开支超过截止时间底线之比；Dij为调度ti时实际执行时间同约束目标条件的比率。Min(Odeadline)和Min(Obudget)为云计算环境下，系统完成调度时实现的最小调度目标。

从用户角度出发，其希望当所有任务调度完所需的时间按照其期望值执行，那么就需要最小化vij；同时，在计算能力方面还将考虑应用任务调度时消耗的计算能力要不大于系统总的计算能力。

因此截止时间底线的目标约束条件可用式(2)和式(3)分别表示

(2)

(3)

用户在取得执行时间上满意服务时，还希望付出的调度开支能最小化，那么系统就要将用户的所有任务调度时总的开支达到最小。另外，系统还要求某些任务调度时的开支必须小于系统的总的调度预算。

那么对于应用任务调度预算的目标约束条件可用式(4),(5)表示

(4)

(5)

1.2 多目标约束转化为单目标过程

(6)

用户在调度服务得到满意的情况下，其还希望调度花费能尽可能的少。实际调度中，因为调度任务所需要的费用是同用户的满意程度成正比关系，因此将调度的费用开支、调度目标和调度预算这三者之间的隶属关系用yijbudget这个函数表示，如下所示：

(7)

通过分析上述两种情况下的约束条件可以得出，若实现最小化的调度预算和截止时间，同时还能完成所有应用任务的调度请求，仅需要最小化截止时间的隶属度函数值和调度预算开支的隶属度函数值。这就是将多目标转化成单目标问题加以解决的方法，具体转化过程表示为

Min(O)=ω1MinOdeadline+ω2MinObudget

(8)

1.3 单目标求解

1.3.1 设计进化算子

文中在进化论知识研究的基础上，重新设计了经过取模后的算子，得到新的交叉算子，再经过变异、选择操作，利用新的交叉算子对遗传算法进行重新构造，从而对多目标转化单目标后的问题进行求解。

重新构造的交叉算子算法描述如下：

输入参数：c1[n],c2[n];

输出流程：child_c[n];

{for(i=1;i<=n;i++)

Child_c[i]=(c1[i]+c2[i])%m;

Return child_c[n];}

遗传算法中的变异算子是一种辅助性的操作算子,参与变异的父代染色体个体用数组c[n]表示，变异算子的算法如下：

输入参数：c[n];

输出流程：child_m[n];

{ 任意从区间[1,m]选取一个整数，记作x;

任意从区间[1,n]中选取一个整数，记作i;

for (k=1;k<=n;k++)

if (k=i)

child_m[k]=x;

else child_m[k]=c[k];

return child_m[n];}

1.3.2 求解最优解

通过对以上目标求解过程分析得出，实际调度过程中将多目标的问题可以转换成单目标约束的优化问题来解决。步骤如下：

1) 交叉和变异的初始概率值分别设定为Pc，Pm，种群的规模值设定为R，用P(0)表示初始种群，从区间[1,m]中选择任意的一个整数作为染色体基因数。g表示种群代数，最初的种群代数设置为0。

2) 任意选择两个染色体个体(Pi,Pj)， 然后利用交叉概率Pc，进行取模运算，最后再进行交叉操作，将最后生成的新染色体集合记作Oc。

3) 利用变异概率Pm，对新生成的染色体集合进行变异操作。将这一操作生成的新染色体集合记作Om。

4) 第g代种群记为P(g),通过对目前的种群和经过一系列操作后生成的种群集合进行合并，得到P(g)∪Om∪Oc，再从该集合中选择R个需要保留下来的最优秀的染色体个体，记作P(g+1)。

5) 如果这时遗传算法能够满足算法的迭代终止条件，达到设定的最大值，则终止；否则跳转到第二步继续执行。

2 仿真及分析

采用CloudSim 平台来模拟云环境， 对此调度算法进行模拟仿真。并将实验结果与常被用来作为评价调度策略性能优劣基准的Min-Min 算法和以服务质量为导向的改进的Min-Min 算法进行对比。

在CloudSim环境中建立 10 个共享时间点。对目标进行求解时，设定种群规模数R为 100，Pc为0.90，Pm为 0.10，迭代最大次数设置为400。用户提出的调度任务数值相同，设定任务数依次为 10,20,…,100，应用任务设定的约束条件仅为调度预算和截止时间底线，分别对三种算法进行仿真实验。算法的可信性标准为算法的平均任务完成时间、任务截止时间底线违背率和平均调度开销。

图1为三种算法在平均任务完成时间上的对比，从图1可以看出，在提交任务比较少时，执行的时间差异性不大，随着调度任务数量的增大，文中提出的算法在执行时间上明显优于另外的两种算法。

图2为应用任务截止时间底线违背率的对比，随着调度任务书数量的增大，传统的Min-Min算法违背率相对较高，而文中提出的算法增加的幅度较小，优于Min-Min算法以及改进的Min-Min算法。

图3为调度成本的对比，传统的Min-Min算法不管在任务少或不断增加的情况下，调度成本一直明显高于其他两种算法，文中提出的算法与改进的Min-Min算法相对成本都较低。

图1 平均任务完成时间对比

图2 应用任务截止时间底线违背率

图3 三种算法的平均调度开销

3 结 论

文中提出了一种基于多目标约束的云计算任务调度算法，通过对调度预算及截止时间违背率约束条件的设定，利用隶属度函数将复杂的多目标问题转换为单目标问题解决，利用进化算子对遗传算法进行构建，从而得到单目标问题的最优解。进行仿真实验，实验结果表明，在仿真环境相同的情况下，本文提出的策略平均调度完成时间短，执行费用和截止时间底线违背率都相对较低而且能使系统负载相对均衡，资源利用率高。