0 引言

云计算作为一种基于互联网的计算服务模式，受到了工业界、学术界的广泛关注。云计算有三大特征：资源池化、快速弹性、按需分配的自主服务。云计算通过资源虚拟化为用户提供了基础设施即服务(Infrastructure as a Service, IaaS)，平台即服务(Platform as a Service, PaaS)和软件即服务(Software as a Service, SaaS)。随着云计算技术的快速发展，其在能源、制造、金融、教育科研、电子政务、医药医疗、电信通信等主要领域都有很好的应用前景。由于云计算中用户群体规模很大，提交的任务数量很多，如何快速响应用户需求，高效地进行云计算任务调度成为云计算领域中重要的研究课题。

云计算任务调度属于NP完全问题^[1]，目前，云计算任务调度方法大都采用了静态资源调度算法。各大云计算公司如Google、IBM采用的调度算法和Hadoop一样，先来先服务(First Come First Serviced, FCFS)算法是Hadoop的默认调度算法，但是对于短作业可能存在等待时间过长的问题。雅虎和Facebook提出了计算能力调度和公平份额调度算法，但是这两种算法都不能根据集群中的节点生成较优的调度方案^[2-3]。智能优化算法如：模拟退火算法、粒子群优化(Particle Swarm Optimization, PSO)算法^[4]、蚁群算法^[5]、遗传算法^[6]等在求解NP类问题上非常适合，在云计算任务调度中，这类启发式算法相比传统的任务调度算法，能够显著降低总任务完成时间，但是存在参数设置不合适、调度目标单一、迭代时间过长等问题。

针对以上分析，本文首次提出一种基于多尺度量子谐振子算法(Multi-scale Quantum Harmonic Oscillator Algorithm, MQHOA)的云计算任务调度算法以克服上述算法存在的弊端，MQHOA是2009年提出的一种模仿量子谐振子波函数能级模型的优化算法^[7]。文献[8]给出了MQHOA的实现，该算法数学原理简单物理含义明确且无需任何先验知识。完备的解空间搜索能力和精确的聚焦能力使MQHOA能够较准确地在高维空间中实现对解的搜索定位。文献[9]给出了算法最新的改进模型，引入能级稳定过程，使MQHOA在高能级的亚稳态进行充分的搜索，从而避免过早地陷入到解空间中的某一区域，无法充分搜索整个解空间。文献[10]将模拟谐振子算法应用于多项目调度问题，验证了算法的有效性，表明了模拟谐振子算法的改进算法MQHOA应用在云计算任务调度的可行性。文献[11]分析了MQHOA在求解整数非线性规划问题上的性能，得到MQHOA在求解精度和收敛速度上均优于文中对比算法。云计算调度问题本身就是一个整数规划问题，这体现了MQHOA在解决这类问题的良好性能。MQHOA在解决云计算调度问题中，由于算法本身的特点，克服了粒子群算法局部搜索能力不足并且需要较多先验知识的缺点，面对多样化的任务调度需求，适应性更强。基于MQHOA的任务调度算法利用高斯采样的随机性处理云计算任务调度，解决传统调度算法存在的短作业等待时间过长问题，而且相比蚁群算法、粒子群算法、遗传算法，该算法也具有MQHOA收敛速度快、参数设置少、数学结构简单的优点，能够较好平衡局部搜索和全局搜索这两个过程。仿真实验结果表明，基于MQHOA的任务调度算法可以取得较优的任务调度方案和负载均衡。

1 云计算任务调度与MQHOA物理模型 1.1 云计算任务调度问题描述

云计算任务调度问题的实质是将用户提交的任务交给合适的资源上运行，通过对任务的合理分配，使总的任务完成时间达到最小。为了深入研究云计算调度问题，本文假设用户提交的任务之间相互独立，并且执行没有先后顺序；各个任务的计算成本和数据中心中资源的计算能力已知；分配之后任务将一直对应虚拟机上运行，不会中断。

用户提交的任务可以用T表示，则n个相互独立的任务可以集合T={T₁, T₂, …, T_n}表示，数据中心上虚拟机资源用VM表示，则m个虚拟机资源组成的集合表示为VM={VM₁, VM₂, …, VM_m}，将n个相互独立的任务分配到m个虚拟机资源上运行，这种分配关系可以用矩阵A的形式表示：

$\mathit{\boldsymbol{A = }}\left[ {\begin{array}{*{20}{c}} {{a_{11}}}&{{a_{12}}}& \cdots &{{a_{1n}}}\\ {{a_{21}}}&{{a_{22}}}& \cdots &{{a_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{a_{m1}}}&{{a_{m2}}}& \cdots &{{a_{mn}}} \end{array}} \right]$

(1)

在矩阵A中，a_ij代表第j个任务是否分配到第i个虚拟机上运行，其中a_ij∈{1, 0}，i∈{1, 2, …, m}，j∈{1, 2, …, n}，任何一个任务只能分配到一个虚拟机上，故有$\sum\limits_{i = 1}^m {{\alpha _{ij}} = 1} $。任务T_i的长度用Length_i表示，虚拟机VM_j的性能用MIPS_j表示，则任务T_i在虚拟机VM_j上的执行时间可以用e_ij表示：

${e_{ij}} = Lengt{h_i}/MIP{S_j}$

(2)

分配矩阵A对应的运行时间矩阵可以用E表示：

$\mathit{\boldsymbol{E}} = \left[ {\begin{array}{*{20}{c}} {{e_{11}}}&{{e_{12}}}& \cdots &{{e_{1n}}}\\ {{e_{21}}}&{{e_{22}}}& \cdots &{{e_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{e_{m1}}}&{{e_{m2}}}& \cdots &{{e_{mn}}} \end{array}} \right]$

(3)

对于分配矩阵对应的所有任务运行时间用C表示：

$C = \mathop {{\rm{arg}}\;{\rm{max}}}\limits_i \sum\limits_{j = 1}^n {{a_{ij}}{e_{ij}}} \,;i \in \left\{ {1,2, \cdots m} \right\}$

(4)

云计算任务调度的优化目标是使C最小，一个好的分配方案应该是平衡各个虚拟机上面的任务，在多个虚拟机中，找到运行任务时间最长的虚拟机，优化这个虚拟机上的任务负载。

1.2 MQHOA物理模型描述

量子力学中的定态薛定谔方程描述了在势阱V(x)约束下粒子的概率分布情况，MQHOA引入定态薛定谔方程，将优化问题中的目标函数的f(x)作为定态薛定谔方程中的势阱V(x)=f(x)，在这一对应条件下，函数优化问题就转化为求粒子在势阱V(x)=f(x)约束条件下的基态波函数ψ₀(x)问题^[12]。在量子系统中，粒子处于基态时将在势阱最低点附近以最大的概率出现，目标函数的概率分布与基态波函数的概率分布一样。薛定谔方程无法求出复杂势阱的波函数，而函数在最优解附近的寻优过程类似于物理中谐振子势在平衡位置的简谐振动，所以复杂的目标函数f(x)可以在最优解位置用泰勒展开式展开:

$f\left( x \right) = f\left( {{x_0}} \right) + f'\left( {{x_0}} \right)\left( {x - {x_0}} \right) + \frac{1}{2}f''\left( {{x_0}} \right){\left( {x - {x_0}} \right)^2} + \cdots $

(5)

其中：f(x₀)为常数，在最优解附近f ′(x₀)等于0，去除高次项之后只剩下二次项$\frac{1}{2}f''\left( {{x_0}} \right){\left( {x - {x_0}} \right)^2}$。用谐振子势阱近似表示目标函数f(x)并代入定态薛定谔方程得到：

$\left( { - \frac{\hbar }{{2m}}\frac{{{\partial ^2}}}{{\partial {x^2}}} + \frac{1}{2}k{x^2}} \right)\psi \left( x \right) = \mathit{\boldsymbol{E}}\psi \left( x \right)$

(6)

根据量子理论，在势阱V(x)=f(x)约束条件下可以准确获得波函数，不同能级的波函数如图 1所示。

波函数从高能态到基态的变化过程是一个逐渐收敛到稳定状态的过程。从图 1中可以看出，高能态对应多个高斯分布的叠加的不稳定状态，基态对应单一高斯分布的稳定状态${\psi _0}\left( x \right) = \frac{{\sqrt a }}{{{{\rm{ \mathsf{ π} }}^{1/4}}}}{{\rm{e}}^{ - a2x2/2}}$。波函数的变化过程反映了在同一尺度下MQHOA多个高斯采样区域不断聚焦到一个高斯分布的过程，在MQHOA中引入多尺度因素，使MQHOA在保证不遗漏采样的情况下能对不同尺度的优化函数进行采样。量子理论解释了MQHOA收敛到全局最优解的过程，反映了算法具有较好的全局搜索和局部搜索能力。

2 云计算任务调度设计 2.1 MQHOA的3个迭代过程

对于一个定义域为[min, max]的目标函数可以初始化尺度为σ_s=max-min，算法唯一需要确定的采样区域个数k，MQHOA初始化时在目标函数的定义域内分别随机生成k个采样位置x_i，计算k个采样位置x_i的标准差σ′_k，下面说明MQHOA的3个迭代过程。

1) 能级稳定过程。

在算法初始化时生成了k个采样位置，对于每个采样位置x_i都按照高斯分布N(x_i, σ_s²)采样生成一个新的采样位置x′_i，比较生成的新的采样位置与当前采样位置的目标函数值，如果f(x′_i)＜f(x_i)，则将当前采样位置替换成新的采样位置x_i=x′_i，否则不进行任何操作。当k个高斯采样结束之后，计算当前的k个采样位置的标准差σ_k，得到迭代前后标准差变化的绝对值为Δσ_k=|σ_k-σ′_k|，替换σ′_k为σ_k，当Δσ_k>σ_s时，迭代重复进行，直到Δσ_k≤σ_s跳出循环。

2) 能级降低过程。

当算法处于能级稳定状态后，找到当前k个采样位置中的最差解的位置x^worst，并以k个采样位置的平均值替换最差解的位置x^worst=x^mean，重新计算这个采样位置的标准差σ′_k，能级下降过程将一直重复执行直到σ′_k≤σ_s，这时k个采样位置x_i已经收缩到高斯分布N(x^mean, σ_s²)区域内。

3) 尺度降低过程。

单一尺度是无法对目标函数的最小值点进行逼近的，MQHOA中存在尺度降低过程，当2) 中能级降低过程达到能量基态时，尺度减半σ_s=σ_s/2，直到σ_s小于等于设定的最小搜索尺度σ_min跳出，最终算法停止得到最优解。

2.2 MQHOA求解云计算任务调度问题

云计算任务调度是一个离散优化问题，在云计算任务调度问题中，基于MQHOA的任务调度算法将每一个调度方案看成一个采样位置，目标函数是总任务调度时间。将每一个任务看成一个维度，每个任务有n个虚拟机可以选择，其范围为{0, 1, …, n-1}，则可得σ_s=n-1，对每一维度进行高斯采样都需要取整，在尺度降低过程中，尺度每次迭代降低至原来的1/λ，即σ_s=σ_s/λ，而且算法在尺度降低到σ_min=1时停止。在能级降低的过程中，通常将函数优化中的最坏值点替换成平均值在离散优化中没有意义，这里直接替换成最优值点。

MQHOA求解云计算任务调度问题的伪代码为：

BEGIN

 Initialization k、λ、σ_s=n-1

 随机生成k个调度方案x_i(i=1, 2, …, k)

 计算k个调度方案的标准差σ′_k

 DO

  DO

   DO

    对于每一个调度方案都按照高斯采样N(x_i, σ_s²)生成一个新的调度方案，如果总任务调度时间f(x′_i)＜f(x_i)则替换x_i=x′_i，计算新的标准差σ_k，得到Δσ_k=|σ_k-σ′_k|，替换标准差σ′_k=σ_k

   WHILE(Δσ_k>σ_s)

    更新最坏解值x^worst=x^best

  WHILE(σ_k>σ_s)

   尺度降低σ_s=σ_s/λ

 WHILE(σ_s>1)

  输出k个调度方案中的最优调度方案x^best。

为了方便理解，假设有3个虚拟机、5个任务，则生成的调度方案的分配矩阵可能是：

${\mathit{\boldsymbol{x}}_i} = \left( {\begin{array}{*{20}{c}} 0&1&0&0&1\\ 1&0&0&1&0\\ 0&0&1&0&0 \end{array}} \right)$

(7)

在调度方案形成的分配矩阵中，列代表每一个维度，第一个任务选择了第二个虚拟机，则分配矩阵中第二行第一列为1，同一列其他行为0，对于这一维度的初始高斯采样按照N(1, 2²)进行，生成的新的值然后取整，各个维度高斯采样完成之后就生成了新的调度方案。

3 实验结果及分析

CloudSim^[13]是澳大利亚墨尔本大学Rajkumar Buyya博士领导团队开发的云计算仿真平台，主要用于模拟云环境，对不同的应用和服务模型的调度策略进行性能测试。在CloudSim中，DatacenterBroker类模拟了一个代理，负责根据服务质量需求在线协商服务与资源的分配策略。对于一个新的任务调度算法，用户可以通过在DatacenterBroker中加入新的方法实现任务调度策略，从而完成该算法的模拟，本文中的算法都是通过修改DatacenterBroker类实现。

在基于MQHOA的任务调度算法的尺度降低过程中，尺度每次迭代降低至原来的1/λ。λ可以看作一个可调节收敛速度的参数，这并不是函数优化中每次迭代后尺度减半，这是因为尺度减半在处理类似云计算调度的离散优化问题过程中，每次搜索后收敛的速度过快，在还没有找到一个相对最优解的情况下，采样点的活动区域大大减小，这对于依赖于随机搜索的算法来说，很难跳出局部最优，寻找最优解的概率变得很低。文献[14]中用MQHOA求解旅行商问题时，设定λ值为1.1，旅行商问题与云计算调度问题类似，在本文实验中，设定基于MQHOA的任务调度算法的λ值为1.1，使收敛的速度变缓，迭代次数相对增加，寻优能力更强。

在5个虚拟计算资源、200个任务和5个虚拟计算资源、500个任务两种调度规模下，通过算法迭代次数与总任务完成时间之间的关系对MQHOA与粒子群优化算法进行比较。实验中虚拟计算资源的处理能力分别是[1 700, 2 800, 3 600, 500, 1 200] MIPS(Million Instructions Per Second)，任务的长度在范围[1 000, 4 000] MI(Million Instructions)中均匀分布。所比较的粒子群算法参数设置为群体规模size为10，局部权重c₁与全局权重c₂都为2，惯性权重w根据经验值设为0.728，最大迭代次数设置为300，实验结果如图 2所示。

从图 2可以看出，MQHOA与PSO算法在前期10次迭代之内都有很快的收敛速度，PSO算法的下降速度明显小于MQHOA的下降速度，在50次迭代之后，PSO算法有一段时间趋于平衡，这是因为PSO算法前期收敛速度快，后期局部搜索能力不足，但是MQHOA直到满足条件退出迭代之前都有很强的局部搜索能力，所以在MQHOA的执行期间内，总任务完成时间都有下降。

MQHOA的迭代次数一般在100以内，PSO算法在迭代次数大于150后，总任务完成时间还有下降，设定最大的迭代次数为250，分别利用前面的条件随机生成{100, 200, 300, 400, 500}个任务，得到FCFS算法、PSO算法和MQHOA在各个虚拟计算资源上的运行时间(保留两位小数)如表 1所示。

分析表 1得到，基于MQHOA的任务调度算法在不同的任务集上总任务完成时间与3号虚拟计算资源的执行时间一致，这是因为3号虚拟计算资源的计算能力最差，而MQHOA是利用高斯采样随机寻解的智能算法，无法避免地将一定规模的任务分配给3号虚拟计算资源。在不同规模的任务集中，可以看出MQHOA总任务完成时间最短，分别为{40.35, 89.74, 147.23, 185.12, 268.07}，相比FCFS算法，能够减少50%~60%，相比PSO算法，能够减少10%~20%。

定义任务负载不均值(Degree of Imbalance，DI)为：

$DI = \left( {{C_{{\rm{max}}}} - {C_{{\rm{min}}}}} \right)/{C_{{\rm{avg}}}}$

(8)

其中：C_max为虚拟计算资源执行任务时间最长的时间，也就是总任务完成时间；C_min是虚拟计算资源执行任务时间最短的时间；C_avg是所有虚拟计算资源执行任务时间的平均时间，通过对任务负载不均值的计算，可以对完成任务调度后的虚拟机负载情况进行测量，对比三种算法在不同任务集上的负载情况，可以得到图 3。由图 3可以看出，FCFS算法的DI在不同的任务集上都维持一个相对稳定的状态，但是PSO算法和MQHOA在任务数量增多的情况下DI的趋势是上升，MQHOA上升的幅度比较缓慢，在任务数量达到一定量后，总体上趋于平衡，这表明MQHOA在适用于不同任务集上稳定性强于PSO算法。在不同的实验任务集上，MQHOA的DI保持在0.3~1.1的范围，比FCFS算法降低了1~1.5，比PSO算法降低了0.4~0.8。在云计算任务调度中，基于MQHOA的任务调度算法在总任务运行时间最短的情况下，也能有效地实现负载均衡，相比其他算法的优势明显。

4 结语

本文首次提出一种基于多尺度量子谐振子算法的云计算任务调度算法，该算法将任务分配到虚拟机的调度方案看成一个采样位置，利用高斯采样产生新的相对最优解，利用尺度下降来精确聚焦最优解的位置。基于MQHOA的任务调度算法具有数学结构简单、参数控制少的特点，在多样化的任务调度需求中适应能力更强。通过CloudSim模拟实验，得到MQHOA相比PSO算法和FCFS算法能够快速收敛，显著降低任务执行时间。在要求快速响应和负载均衡的云计算环境中，MQHOA性能明显优于FCFS算法和PSO算法。

在下一步的工作中，有两点还需进一步研究：第一，本文中基于MQHOA的任务调度算法在能级降低过程中，替换成最优点的操作会丢失解空间信息，可能导致陷入局部最优，可改进算法以增强全局搜索能力。第二，本文中只考虑了任务调度的时间因素和负载均衡，后续还将考虑任务之间的通信、任务优先级、计算成本、能耗，综合各种因素，使云计算任务调度在综合性能上达到最优。