基于成本的云计算任务调度策略

摘 要：云计算服务的商用对用户来说最关键的是成本问题。文章提出了基于粒子群算法的云计算任务调度策略。采用了间接编码的方式，设置参数，考虑经济成本和时间成本因素，选取了适应度函数，实验结果表明，文章算法具有较强的寻优能力，可以解决云计算任务调度问题。

关键词：云计算；任务调度；成本粒子群算法

引言

在这大数据的时代，云计算已是学术界、商界的新贵。虽然云计算技术在商业中应用的比较广泛，但是就云计算技术，还有许多需要完善和改进的。云计算是一种商业计算模型，它将计算任务分布在大量计算机构成的资源池上，是各种应用系统能够根据需要获取计算力、存储空间和信息服务。

1 任务调度问题描述

在云计算环境下，一个大规模的任务计算必须在逻辑上划分成许多个子任务进行，然后通过处理子任务来完成主任务。任务调度是将云计算中用户提交的任务请求分配到多个资源的过程。在云计算的应用中，大多数是商业的应用，因此在云计算的任务调度更多的考虑成本指标，同时满足用户的需求。成本由时间成本和经济成本等组成。

2 基于本文算法的云计算任务调度

粒 子 群 优 化 算 法（Particle Swarm Optimization，简称PSO）是由美国的J.Kennedy 博士和 R.C.Eberhart受鸟群觅食行为的启发提出的一種基于群体智能的优化算法。因算法程序结构简单、需要调节的参数较少、高效等特点，被广泛应于到科学研究。

2.1 粒子编码方式

本文采用间接编码方式，采用离散数值编码，编码长度等于子任务数量。设有M个任务，N个资源，每个任务又划分为多个子任务。

子任务的总数量：

其中，TNum（t）为第 t 个任务划分子任务的个数。

对每个子任务的编码方式为：

采用自然数编码，即按任务自然数顺序进行编码。第i个任务中的第 j 个子任务的序号是 R[i，j]。

文中使用ETC 矩阵[1]表示任务的运行时间，ETC（i，j）表示子任务i在第j个资源上执行的时间。其中，ETC（i，j）表示子任务i在云资源j上执行的时间，ETC（i，j）=0表示子任务i不在资源j上执行。用RUC数组表示计算资源单位时间内任务执行的成本[3]，根据粒子解码结果和ETC矩阵[2]，可看出资源j运行完被分配到本资源的全部子任务的时间Time（j）：

所有资源上的子任务全部执行完后，表示全部任务运行完毕，则任务的总完成时间FTime：

第r个资源运行本资源上的全部子任务所花费的总时间为：

完成全部任务的总花费成本为：

2.2 粒子速度和位置的更新

标准粒子群算法的速度和位置更新公式为：

其中[2]，ω代表惯性权重，v表示第i个粒子在第k+1次迭代时在j维的速度，c1、c2表示粒子个体的学习因子和粒子群体的学习因子，r1，r2为0到1之间均匀分布的随机数，x表示第i个粒子在第k+1次迭代时在j维的位置，pbest表示第i个粒子在第k次迭代时个体历史最优位置，gbest表示第k次迭代时的全局最优位置。其次为了防止粒子飞出最大解空间，通常限制vij∈（-vmax，vmax）。

为了增加搜索过程中的种群的多样性，优化最优解的搜索能力，本文提出自适应的惯性权重，如下的更新公式

其中rand为0，1之间的随机数

3 实验仿真与结果

本文实验使用Matlab生成ETC矩阵和RCU数组。运用CloudSim-3.0对传统粒子群算法和本文算法进行云环境下的仿真实验，实验在任务数相同、任务大小相同、计算资源的计算能力相同的情况下进行。实验测试执行200次，采用200次实验的实验结果的平均值作为作图的数据。实验参数设置：种群规模P为50个，计算资源数N为10个，任务数M为20个，惯性权重ωstart、ωend为0.95、0.4，学习因子c1、c2为2、2，最大迭代次数为1000次。

实验结果如下图：

由以上实验结果可以看出，与传统的PSO算法相比，本文算法寻优能力更强，收敛速度较快。

4 结束语

本文研究了云计算任务调度模型，改进了粒子群算法，并应用到云计算任务调度上，主要考虑了时间成本和经济成本。仿真结果显示本文算法具有较强的寻优能力。

参考文献

[1]封良良，张陶，贾振红，等.云计算环境下基于改进粒子群的任务调度算法[J].计算机工程，2013，39（5）：183-186.

[2]娄建峰，高岳林，李飞，等.基于改进粒子群算法的云计算任务调度算法[J].微电子学与计算机，2016，33（8）：112-116.

[3]封良良，夏晓燕，贾振红，等.实验基于资源预先分类的云计算任务调度算法[J].计算机仿真，2013，30（10）：363-367.

作者简介：常贺（1993-），男，硕士研究生，研究方向：计算机网络与控制工程。