近年来，云计算^[1-2]成为了工业界和学术界研究热点.云计算是并行计算、网格计算^[3]的发展，属于分布式计算的一种技术，核心思想是将大量用网络连接起来的计算资源进行统一管理和调度，形成一个计算资源池向用户提供服务.提供这种资源的网络被称为“云”.云计算的任务调度问题属于一个新兴课题，现有的一些理论还不够完善，缺乏一个系统的方法.近年兴起的启发式智能化方法引起了众多学者的关注和兴趣，诸如模拟退火、神经网络、遗传算法、微粒群算法、蚁群算法，以及它们之间的混合算法^[4-7]，这些算法成为解决NP类以及组合爆炸问题的有力工具.文献[8]提出了一种具有双适应度的遗传算法(DFGA)，在保证任务的总完成时间最小的情况下，也考虑到任务的平均完成时间，然而该类算法对系统中的反馈信息利用不够充分，求解效率低；文献[9]提出一种基于蚁群优化的计算资源分配算法，根据云环境的特点，分析了诸如线路质量、带宽占用和响应时间等因素对调度的影响；文献[10]提出了一种改进的蚁群算法，算法在达到整体网络负载均衡的同时，还延长网络寿命并获得利润.由于蚁群算法初始阶段缺乏信息素，存在搜索时间过长、易于停滞的缺点，因此在搜索效率上不高.文献[11]提出了基于信任驱动的资源负载均衡调度算法.该算法不仅考虑了用户任务的信任需求，目标是使资源达到负载平衡，而且兼顾任务执行时间跨度等因素.本文在充分利用“云”资源前提下，对云计算中任务的高效合理调度和资源的负载均衡机制进行了研究，提出了一种基于蚁群模拟退火算法(ACOSA)的任务调度算法，并通过仿真实验，验证了云环境下该算法具有良好的任务调度性能.

1 问题描述 1.1 云计算中的编程模型

目前的云环境中使用的计算模式^[12]很多都是采用谷歌公司提出的MapReduce，该模型将每个任务分成若干个子任务，然后把子任务调度到大规模的虚拟机计算节点中进行处理.MapReduce非常适合对大规模数据集的处理.其执行过程如图 1所示.

从图 1可看出，MapReduce有6个步骤，经分析可分成两个主要的过程：(1) Map过程：把每个任务由程序里MapReduce库分割成M个片，每个片大小从16到64MB不等；进而分配给多个worker并行执行，输出经过处理后得出的中间结果；(2) Reduce过程：把Map过程得出的结果进行分析汇总，输出R个输出文件作为最后结果.因此，在MapReduce编程模型下，对大规模的子任务进行调度是一个非常复杂的问题.由于每个任务都要分成Map过程中的M片，Reduce过程中的R片，而M与R要比worker的数量大很多，因此每个worker都要执行非常多的工作^[13].

衡量调度任务策略优劣的目标主要有：服务质量QoS(Quality of Service)、最优跨度(Optimal Makespan)、负载均衡(Load Balancing)、经济原则(Economic Principle)等.其中，调度的跨度是最重要的指标，指云环境下从第一个任务开始算起，直到最后一个任务执行完毕所消耗的时间，跨度越短证明调度策略越好.考虑到云环境中每个虚拟机计算节点的计算能力不尽相同，以及每个任务对资源各项指数偏好也有差异，任务到虚拟机资源节点上的均衡分配以及服务质量也是衡量调度策略的重要因素，因此应将时间跨度和负载均衡结合作为评估目标的同时，充分考虑策略的服务质量，也就是任务与资源的匹配度.

本文依据云环境下模型的特点，提出一种适用于大规模并行处理系统的新的调度算法，即蚁群模拟退火算法，该算法充分利用蚁群算法解决大规模组合优化问题的并行性、正反馈性和鲁棒性的优势，并为避免蚁群算法易陷入局部最优解、收敛速度慢的缺点，利用模拟退火算法灵活、运行效率高和较少受到初始条件约束等优点，建立一个较优的分配调度策略. 并通过仿真实验可知，蚁群模拟退火算法进行任务调度可以在减少任务总完成时间的同时, 均衡系统负载，提高服务质量.

1.2 相关定义

定义1  云环境下待执行的n个任务表示为T={T₁, T₂, ……T_n}，m个虚拟机资源表示为集合V={V₁, V₂, ……V_m}，用一个n×m的矩阵S表示任务在虚拟机资源上的执行时间矩阵，S ={S_ij|S_ij表示T_i在V_j上的执行时间，1 < i < n, 1 < j < m}. E是一个n×m的资源分配矩阵，E ={E_ij|E_ij表示T_i是否分配到V_j上执行，分配执行则E_ij=1, 否则E_ij=0，1 < i < n, 1 < j < m}.每个任务用六元组来表示，即

$ {T_i} = \left\langle {{\rm{TI}}{{\rm{D}}_i},{\rm{T}}{{\rm{C}}_i},{\rm{T}}{{\rm{B}}_i},{\rm{T}}{{\rm{R}}_i},{\rm{T}}{{\rm{F}}_i},{\rm{T}}{{\rm{P}}_i}} \right\rangle , $

(1)

其中，TID_i表示任务编号，TC_i表示任务期待资源cpu处理能力，TB_i表示任务期待带宽，TR_i表示任务期待内存，TF_i表示任务期待资源故障率，TP_i表示是任务期待资源费用.同样的，每个节点用六元组表示如下：

$ {V_i} = \left\langle {{\rm{VI}}{{\rm{D}}_i},{\rm{V}}{{\rm{C}}_i},{\rm{V}}{{\rm{B}}_i},{\rm{V}}{{\rm{R}}_i},{\rm{V}}{{\rm{F}}_i},{\rm{V}}{{\rm{P}}_i}} \right\rangle , $

(2)

VID_i表示节点编号，VC_i表示节点cpu处理能力，VB_i表示节点带宽，VR_i表示节点内存大小，VF_i表示节点故障率，VP_i表示节点使用价格.

定义2  根据用户不同需求来计算各个任务到每个资源节点的匹配程度，引入匹配因子，用户任务i与第j个资源节点匹配因子表示如下.

$ {\rm{Matc}}{{\rm{h}}_{ij}} = 1/\sqrt {\sum\limits_{i = 1}^5 {{{\left( {{\rm{T}}{{\rm{m}}_i} - {\rm{V}}{{\rm{m}}_j}} \right)}^2}} } , $

(3)

其中，Tm_i表示任务i对资源的期望值(由式(1)可得)，Vm_j表示第j个资源节点的参数权值(由式(2)可得).匹配因子越大，表明任务选择该资源节点能获得较好的资源服务质量.

定义3  设X是一个任务与资源的映射序列，则负载均衡度定义为

$ {\rm{Load}}\left( X \right) = \sqrt {\sum\limits_{i = 1}^n {{{\left( {1 - {C_1}\frac{{{Y_i}}}{{{\rm{L}}{{\rm{v}}_i}}}} \right)}^2}} } , $

(4)

其中，Y_i表示资源节点i上的任务量，Lv_i表示资源节点的计算能力，C₁为归一化参数，使得$ 0 < {C_1}\frac{{{Y_i}}}{{{\rm{L}}{{\rm{v}}_i}}} \le 1 $.云环境中资源节点的计算能力可由节点静态信息算出，其中包括节点中每个cpu的处理能力p、cpu的个数n、内存大小r、网络带宽b，为每项参数设置不同的权值系数W_i，作用是表示每个参数的影响度，通过加权运算，云计算资源节点的计算能力表示为

$ \begin{array}{l} {\rm{L}}{{\rm{v}}_i} = {W_1} \times n\left( {{V_i}} \right) + {W_2} \times p\left( {{V_i}} \right) + {W_3} \times b\left( {{V_i}} \right) + \\ {W_4} \times r\left( {{V_i}} \right). \end{array} $

(5)

定义4  云环境下任务调度的目标是对用户提交的任务实现最优调度，同时增强资源的负载均衡度.将时间跨度和负载均衡度综合作为衡量指标，则目标函数定义为

$ F\left( X \right) = {\rm{Load}}\left( X \right) \times {\rm{Makespan}}\left( X \right), $

(6)

$ {\rm{Makespan}}\left( X \right) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {{S_{ij}}} } \times {E_{ij}}, $

(7)

其中，Makespan(X)表示任务时间跨度.

2 蚁群模拟退火算法

蚁群模拟退火算法的基本思想是把模拟退火算法融入蚁群算法的路径优化和信息素更新中，从而使求解效率和服务质量更加理想.算法流程如图 2所示.

(1) 信息素初始化.考虑到资源的可用性，若资源可用，则可设flag_j=1；若资源退出或失效，则设flag_j=0.文献[14]用节点的硬件资源来初始化一个节点的信息素.主要用cpu个数m，处理能力p，内存容量h，带宽b，故障率f来初始化信息素.并按式(8)为各参数设置阈值，若超过该阈值，则统一以阈值计算.

$ {m_{\max }} = {m_0},{p_{\max }} = {p_0},{r_{\max }} = {r_0},{b_{\max }} = {b_0},{f_{\max }} = {f_0}. $

(8)

cpu的初始信息素为

$ {\tau _{ip}}\left( 0 \right) = \frac{{m \times p}}{{{m_0}{p_0}}} \times 100\% . $

(9)

内存的初始信息素为

$ {\tau _{ir}}\left( 0 \right) = \frac{r}{{{r_0}}} \times 100\% . $

(10)

带宽的初始信息素为

$ {\tau _{ib}}\left( 0 \right) = \frac{b}{{{b_0}}} \times 100\% . $

(11)

故障率的初始信息素为

$ {\tau _{if}}\left( 0 \right) = \frac{f}{{{f_0}}} \times 100\% . $

(12)

所有flag_j=1的资源j的初始信息素^[15-16] τ(t₀)为

$ \tau \left( {{t_0}} \right) = a{\tau _{ip}}\left( 0 \right) + b{\tau _{ir}}\left( 0 \right) + c{\tau _{ib}}\left( 0 \right) + d{\tau _{if}}\left( 0 \right), $

(13)

其中a+b+c+d=1.

(2) 根据式(6)得定义目标函数，初始化参数.

(3) 蚂蚁开始循环，将n个任务置于m个资源上.

(4) 计算任务到资源匹配因子Match_ij作为启发信息，按式(14)计算转移概率，决定选择节点

$ p = \frac{{{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\rm{Matc}}{{\rm{h}}_{ij}}\left( t \right)} \right]}^\beta }}}{{\sum\limits_{k \in valid} {{{\left[ {{\tau _{ij}}\left( t \right)} \right]}^\alpha }{{\left[ {{\rm{Matc}}{{\rm{h}}_{ij}}\left( t \right)} \right]}^\beta }} }}, $

(14)

其中，τ_ij(t)表示t时刻资源j上的信息素浓度，Match_ij(t)表示t时刻任务i与资源j的匹配因子，α和β分别表示信息素浓度和匹配因子的重要程度.

(5) 计算负载均衡度和目标函数值，记录下蚁群此代最优解X.

(6) 运用模拟退火算法优化路径与更新信息素.

传统的蚁群算法(ACO)算法对每代蚂蚁遍历的序列不进行任何的处理，一直循环到最终收敛或者达到最大蚂蚁代数，退出循环并返回算法结果，降低了搜索性能.在这里引入了Boltzmann机制优化路径和更新信息素，具体算法如下：

Step1  对蚁群算法第i次迭代生成的最优解X随机交换两资源节点的任务形成新解X'.

Step2  以模拟退火的原则保留X还是X'，计算目标函数大小F(X)和F(X')，若ΔF=F(X')-F(X) < 0, 则，用X'替代X；否则若exp(-ΔF/T) > rand(0, 1)，则也用X'代替X，否则，就保留X抛弃X'.退火温度按照T(t+1)= λT(t)进行迭代.其中T为退火温度，初始化温度为T₀, 终止温度为T_end, λ为退火系数.

Step3  若T < T_end模拟退火继续迭代，否则结束.

Step4  对模拟退火算法得出的最优解进行信息素的更新，释放信息素公式为

$ \Delta \tau _{ij}^k\left( {t + 1} \right) = \left( {1 - \rho } \right)\tau _{ij}^k\left( t \right) + \sum\limits_{k = 1}^m {\Delta \tau _{ij}^k} , $

(15)

其中，ρ为信息素挥发系数，Δτ_ij^k为每次迭代结束后最优解在路径(i, j)上释放的信息素.

(7) 循环执行达到最大蚂蚁迭代次数，退出循环并返回算法结果，否则执行(3).

3 算法分析和仿真实验

为验证新算法，采用扩展Cloudsim云计算仿真平台^[17]做模拟.并将本文提出的任务调度策略与基于基本蚁群系统ACO的任务调度策略在调度时间方面进行比较.

3.1 试验参数设置

算法中的a，b，c，d分别表示资源节点的cpu计算能力，内存，带宽，故障率的重要性，由于任务的执行受处理器处理能力的影响较大，因此把a，b，c，d的值分别设为0.4，0.2，0.2，0.2.由于信息素挥发系数过大易使解陷入局部最优解，过小会导致算法收敛速度过慢，于是本文综合考虑算法全局搜索能力和收敛速度两项指标，选择信息素挥发系数为0.5.α，β，分别表示信息素，匹配因子的重要性，y表示产生多少蚂蚁效果更好，退火系数λ决定退火的快慢.通过实验来获得α，β，y，λ的最优组合.虚拟机节点设为200个，Master的定时器设为5 s.任务大小为200 M，虚拟机处理能力为100~400 MIPS，内存容量为512 M~2 G，带宽为1~4 M/s，故障率为10%~30%.T₀设为10⁵，T_end设为10⁴.

3.2 实验结果及分析

首先提交一个任务大小为2 000 M的作业，该作业重复提交12次，最后得出有6次当α=1，β=2，y=4，λ=0.95时，为作业任务调度有效节点的时间最少.然后用不同作业大小的作业重复上述过程，最后得出50%的作业当α=1，β=2，y=4，λ=0.95为最优组合.表 1给出了作业大小为2000 M，α，β，y，λ取不同值时，任务调度的时间变化.因此取α=1，β=2，y=4，λ=0.95.

图 3为基于模拟退火蚁群算法(ACOSA)任务调度和基于基本蚁群算法(ACO)任务调度时间图.两种算法均调度350个任务，每增加50个任务进行一次数据采样.

从图 3可以看出，当任务量较少时，ACOSA和ACO的区别不大，ACO略占优势；但当任务量逐渐增大时，ACO花费的时间呈剧增状态，而ACOSA只是平缓增大.

图 4为两个算法的系统均衡度对比图.由图 4可看出虽然ACOSA算法在任务量较少时负载均衡性能比ACO算法优势不大，但随着任务量的增加，ACOSA算法的负载均衡性能要明显优于ACO算法.

因此在云环境下采用ACOSA算法进行任务调度更符合云计算的大规模运算的需求.这主要是因为相比ACO，ACOSA算法蚂蚁走下一步时使用匹配因子使得在任务选择资源节点时可以选择处理能力较强的资源，在任务跨度计算式加入负载均衡因子使得资源整体负载趋于均衡，这都能使得当处理海量任务时调度时间有效减小.为了使蚁群算法得出的最优解是全局最优解，在蚁群算法后期引入退火算法，有效增强了算法的全局搜索能力，避免了蚁群算法的缺陷.

4 结束语

为了克服蚁群算法在大规模的云环境下任务的调度出现速度慢、易陷入局部最优解的缺点，提出基于蚁群模拟退火算法(ACOSA)的任务调度策略，该算法从调度完成时间、负载均衡、任务与节点的匹配度，以及优化全局最优解来进行调度的优化，使用户任务更迅速找到合适的虚拟机资源并分配任务.实验证明改进的算法比基于基本蚁群算法(ACO)的任务调度在调度时间和负载均衡方面有更好的表现.云计算环境下的任务调度目标还涉及其他方面，如经济原则，这将是今后的研究方向.