基于多维QoS约束遗传蚁群算法的云计算任务调度

魏志华，黄 青，况少平

(1.武汉理工大学 计算机科学与技术学院，湖北 武汉 430070；2.湖北交通职业技术学院 交通信息学院，湖北 武汉 430070)



基于多维QoS约束遗传蚁群算法的云计算任务调度

魏志华1，黄 青1，况少平2

(1.武汉理工大学 计算机科学与技术学院，湖北 武汉 430070；2.湖北交通职业技术学院 交通信息学院，湖北 武汉 430070)

利用蚁群算法解决云计算任务调度问题时，启发因子、信息素蒸发系数、期望启发因子等参数的设定往往采用经验选取的方式，而这些参数又与算法性能息息相关，提出一种遗传蚁群融合算法，对这些参数进行编码，在进化过程中找到最优组合，充分结合了蚁群算法的反馈机制、遗传算法的全局搜索能力和收敛速度较快的特点，同时根据不同用户的需求提出多维QoS的约束来进行信息素的局部更新和全局更新。改进的遗传蚁群算法(GAACO)在云仿真平台CloudSim上与模拟退火算法(SA)、基本蚁群算法(ACO)进行了对比仿真实验，结果表明，该算法提高了解的收敛速度和全局搜索能力，同时在任务调度时间、成本、服务质量及系统负载方面都有着更好的表现。

云计算；GAACO；自适应；多维约束；仿真

云计算作为一种新型的商业服务模式，一经提出便受到了工业界和学术界的广泛关注。随着云计算相关研究与应用的深入发展，云计算系统的规模越来越大，拓扑结构越来越复杂，再加上资源的异构性，使得如何有效地进行云计算任务调度成为了云计算领域一个相当重要的研究课题。

已有文献证明云计算任务调度属于一个NP完全问题[1-2]，可采用启发式算法如遗传算法[3-4]、蚁群算法[5]、模拟退火算法[6]、粒子群算法[7]等进行求解，众多学者对此表现出了极大的兴趣和关注，在商业领域各大公司也对此做了一定的研究，以Google的Hadoop[8]为例，总共有3种调度算法，包括先来先服务算法[9]、公平调度算法[10]和计算能力调度算法[11]。目前，关于云计算任务调度还未形成统一的规范，但是一个好的任务调度策略应该能够适应不同云计算环境，以及任务数量和性能等方面的差异，同时能够根据用户需求在成本、时间、可靠性及系统负载几方面达到均衡。蚁群算法能够较好地满足群体性的组合优化要求，但在选取启发因子、信息素挥发系数及期望启发因子时往往依靠经验，而这些参数又与算法性能息息相关[12]，同时存在收敛速度过慢、容易陷入局部最优解等问题。

针对以上不足，笔者提出了一种结合用户多维QoS(quality of service)约束的遗传蚁群算法，一方面将用户需求用数学的形式融入到算法当中，另一方面利用遗传算法对启发式因子、期望启发因子及信息素挥发系数进行编码，在进化的过程中找到最优组合，提高了蚁群算法的收敛速度和全局搜索的能力，使虚拟机资源负载和用户综合代价得到了优化。

1 云计算任务调度问题概述

云计算任务调度融合了用户需求与资源分配的问题，使得任务执行时间跨度短、资源负载率低，为了深入分析问题，建立如下云计算任务调度模型：将n个任务分配到m个资源上，用任务序列J={J1,J2,…,Ji}(i=1,2,…,n)代表n个任务，每个任务由任务长度length、输入数据文件inputfileSize、输出文件大小outputfileSize这3部分组成，用虚拟机资源序列m={Vm1,Vm2,…,Vmj}(j=1,2，…,m)代表m个资源，每个资源由每秒处理指令速度mips、存储大小storage、内存ram、带宽bw组成，则单个任务在每个虚拟机资源上的期望执行时间Dn×m可表示为：

(1)

2 遗传蚁群算法

2.1 遗传蚁群算法求解云计算任务调度

蚁群算法的基本模型是意大利学者DIRIGO受到了自然界中蚂蚁进行群体性寻食行为的启发而提出的，蚂蚁寻食具有一定的自组织性，本质上来讲是最短路径问题，因而可以用来求解TSP等经典的NP问题。遗传算法(genetic algorithm,GA)是模拟达尔文生物进化论的自然选择和遗传学机理生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。故可利用遗传算法来优化蚁群算法，以提高全局搜索能力和收敛速度。

(2)

蚂蚁运动时，为避免信息素积累过多，每完成一次调度，需要对信息素进行更新，可按如下规则进行更新：

(3)

Δτij(n)=Q/multiQoSp

(4)

式中：Q为信息素强度；multiQoSp为多维QoS约束。

结合云计算任务调度的特点，遗传蚁群算法对普通蚁群算法的改进主要体现在以下几个方面：①启发因子、期望启发因子及信息素挥发系数经过了遗传种群的交叉变异，增加了解的可能性，提高了全局搜索能力。②信息素更新方面，进行了全局和局部更新，同时又结合了云计算任务调度过程中对成本、时间、系统负载及服务质量的要求，提出了多维QoS约束。

2.2 多维QoS约束函数的建立

普通蚁群算法在求解问题时并未进行多维QoS的约束，而在实际的云计算调度过程中，却又有相应的要求，因此，笔者增加了成本、时间、可靠性3个方面的多维QoS约束，建立了相应的约束函数。

设Kbest为将当前待分配的任务全部分配给性能最好虚拟机的任务集合，Kworst为将当前待分配的任务全部分配给性能最差的虚拟机的任务集合，p为当前蚂蚁的编号，K为编号为p的蚂蚁任务分配方案，Kj为第Kj个任务所分配的资源序号，k为当前待分配任务个数。基于此，提出了如下假设。

假设1 用Tmin表示将当前待分配任务全部分配到性能最好的资源时的时间代价，Tmax表示将当前待分配任务全部分配到性能最差资源时的时间代价，Tc表示采用遗传蚁群算法进行任务调度时的时间代价，Tres表示时间约束，其数学定义分别为：

假设2 用Cmin表示将当前待分配任务全部分配到性能最好资源时的成本代价，Cmax表示将当前待分配任务全部分配到性能最差资源时的成本代价，Cc表示采用遗传蚁群算法进行任务调度时的成本代价，Cres表示成本约束，其数学定义分别为：

式中：perofmips为单位时间执行指令的成本代价；perofbw为单位时间带宽的成本代价。

假设3Res为采用遗传蚁群算法进行任务调度时的可靠性量化值；resRes为可靠性约束，其数学定义式分别为：

resResKj=Resp/antSize

其中，antSize为蚂蚁种群的大小。

假设4λ1，λ2，λ3分别为成本、时间、可靠性的权重系数(λ1+λ2+λ3=1)，可根据用户要求进行调整，笔者选取3个系数分别为0.3,0.4,0.4，最终多维QoS约束函数定义为：

multiQoSp=λ1·Tresp+λ2·Cresp+λ3·resResp

(5)

2.3 算法流程描述

开始；

初始化遗传算法变异概率Pm、交叉概率Pc、种群规模大小、进化代数等参数；

初始化蚁群算法种群蚂蚁数量m、虚拟机资源集合J、信息素强度Q，以及启发因子α、期望启发因子β及信息素挥发系数γ的最大值；

While(nc<进化代数){

分别对α,β,γ进行二进制编码；

选择个体进行交叉；

分别α,β,γ进行多点变异；

对α,β,γ进行解码；

While(所有蚂蚁是否已完成任务分配){

将m只蚂蚁随机分配到虚拟机序J上；

初始化每只蚂蚁的禁忌表及每只蚂蚁可能路径上的信息素；

While(所有任务是否已分配完){

For 每只蚂蚁do

记录已分配虚拟机；

利用式(2)和已解码α,β,γ的初步生成待分配虚拟机概率；

用轮盘赌的方式选择任务执行的虚拟机；

计算每个蚂蚁的多维约束函数值multi-QoSp；

利用式(5)进行局部更新；

存储当前蚂蚁任务调度方案；

记录当前最好的解及α,β,γ的值；}

计算每只蚂蚁约束函数值；

记录当前最佳调度方案；

记录当前最好的解及α,β,γ的值；

全局更新；

禁忌表清零；

nc++；}}

结束；

3 仿真实验

3.1 实验环境

为了测试笔者算法的性能，实验采用墨尔本大学网格实验室的CloudSim3.0.2云仿真平台，同时与基本蚁群算法(ACO)[13]、模拟退火算法(SA)[14]进行了仿真对比和结果分析。在云仿真平台中首先新建MyAll-ocationTest类进行云环境的初始配置，包括数据中心的创建、云计算任务的规模参数初始化、任务大小与输入输出数据文件大小、虚拟机资源的创建，每个虚拟机资源包括cpu个数、内存大小、带宽以及指令处理速度等指标，创建cloudsim对象添加云计算任务，同时在DatacenterBroker类中新建GAACO、ACO与SA共3种算法。遗传蚁群算法相关参数如表1所示。

表1 遗传蚁群算法参数表

3.2 实验设计与结果分析

笔者从4个方面来比较遗传蚁群算法的性能，即平均时间花费、平均成本、算法服务质量、系统资源负载率。初始时，任务规模为10个，云计算资源为10个，虚拟机存储大小为10 GB，内存大小为256 MB，cpu个数为1，带宽为1 000 MB，单位时间带宽花费为0.01元/s，单位时间指令花费为0.01元/s。任务大小按10个递增进行实验。算法服务质量是通过multiQoS体现的。定义资源负载率为：

(6)

式中：usei为第i台资源的负载；useAvg为系统平均负载；n为资源个数。

任务数量按10个递增时，计算各算法平均时间代价，结果如图1所示。可以看到GAACO的时间代价要优于ACO，但时间花费比SA长，并且随着任务数量的增加，时间上的差距越来越大，与ACO相比时间减少了50.9%，与SA相比相差3%，故从时间代价来说笔者算法优于ACO，但与SA相差不大。

图1 各算法平均时间代价

各算法在不同任务数量条件下的成本代价如图2所示，任务数量以10的倍数增加，可以看到各算法的差异并不大，平均成本代价仅相差1%左右。

图2 各算法成本代价

各算法服务质量实验结果如图3所示，可以看出笔者算法与SA的服务质量随着任务数量的增长在缓慢上升，而ACO却呈现直线急剧上升的趋势，服务质量是成本、时间、可靠性的一个综合指标，可以看到GAACO的综合表现要优于ACO和SA ，分别降低了14.4%和76.8%。

图3 各算法服务质量

图4 各算法系统负载

各算法系统负载实验结果如图4所示，可以看出ACO的系统负载一直维持在一个较高的水平，而GAACO的系统负载高于SA却明显优于ACO，平均系统负载GAACO比ACO减少了50.2%。同时结合图1～图3可知，SA更偏向的是一种平均调度，即分配到每个虚拟机上的任务个数都基本一样，所以利用式(6)得出的负载为0，但云计算任务调度往往要求成本、时间、可靠性在用户需求的基础上达到均衡，这体现在QoS上。综上所述，笔者所提出的算法在实际调度过程中更能满足客户的需求。

4 结论

在对云计算任务调度进行了深入的研究之后，笔者提出的算法从4个方面与基本蚁群算法、模拟退火算法进行了比较，结果表明笔者算法的综合性能要优于其他两个算法，能够较好地均衡时间代价、成本代价、可靠性和系统负载，能较好地满足用户多维QoS的要求。

[1] 李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011，31(1):184-186.

[2] BAYATI M，PRABHAKAR B，SHAH D，et al. Iterative scheduling algorithms[C]∥Infocom IEEE International Conference on Computer Communications. [S.l.]:[s.n.],2007:445-453.

[3] 熊聪聪，冯龙，陈丽仙，等.云计算中基于遗传算法的任务调度算法研究[J].华中科技大学学报(自然科学版)，2012(S1):1-4.

[4] WEI Y , TIAN L. Research on cloud design resources scheduling based on genetic algorithm[C]∥International Conference on Systems and Informatic.[S.l.]:[s.n.],2012:2651-2656.

[5] 王芳，李美安，段卫军.基于动态自适应蚁群算法的云计算任务调度[J].计算机应用，2013，33(11):3160-3162.

[6] 袁晓林，施化吉.基于模拟退火算法的云计算资源调度模型[J].软件导刊，2015(2):68-70.

[7] 张陶，于炯，杨兴耀,等.基于改进粒子群算法的云计算任务调度算法[J].计算机工程与应用，2013,49(19):68-72.

[8] WHITE T. Hadoop: the definitive guide[M].[S.l.]:O’reilly Media Inc, 2010：215-220.

[9] KULKARNI A P, KHANDEWAL M. Survey on hadoop and introduction to YARN[J]. International Journal of Emerging Technology and Advanced Engineering, 2014,4(5):82-87.

[10] WANG J, YAO Y, MAO Y, et al. FRESH: fair and efficient slot configuration and scheduling for hadoop clusters[C]∥IEEE International Conference on Cloud Computing.[S.l.]:[s.n.], 2014:761-768.

[11] ELKHOLY A M, SALLAM E A H. Self-adaptive hadoop scheduler for heterogeneous resources[C]∥International Conference on Computer Engineering and Systems.[S.l.]:[s.n.], 2014:427-432.

[12] 杜衡吉，李勇.蚁群算法中参数设置对其性能影响的研究[J].现代计算机(专业版)，2012(9):3-7.

[13] 段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005:36-37.

[14] 张浩荣，陈平华，熊建斌.基于蚁群模拟退火算法的云环境任务调度[J].广东工业大学学报，2014(3):77-82.Cloud Computing Task Scheduling Based on Adaptive and QoS Constraint Genetic Ant Colony Algorithm

WEI Zhihua:Prof.; School of Computer Science and Technology, WUT, Wuhan 430070, China.

WEIZhihua,HUANGQing,KUANGShaoping

When using ant colony algorithm to solve the task scheduling problem in cloud computing, the set of heuristic factor, information element evaporation coefficient, expectations inspired factor tend to use experience to select the way, but these parameters is closely related to the performance of the algorithm,a kind of genetic ant colony mixed algorithm was proposed. The parameters are coded, and the optimal combination is found in the process of evolution. The feedback mechanism of ant colony algorithm and the global searching ability of genetic algorithm and the fast convergence rate are fully integrated. At the same time, according to the needs of different users, the paper puts forward the constraint of multi-dimensional QoS to carry on the local update and global update of the pheromone. A constructive simulation experiments was done in the cloud simulation platform CloudSim between the genetic ant colony algorithm(GAACO), simulated annealing algorithm(SA) and basic ant colony algorithm(ACO). The results showed that the algorithm not only can improve the convergence speed and global search ability, but also has better performance in job scheduling time, cost, and quality of service and system load.

cloud computing; GAACO; Qos; simulation

2095-3852(2016)05-0631-05

A

2016-05-17.

魏志华(1964-)，男，湖北武汉人，武汉理工大学计算机科学与技术学院教授.

TP338;TP316.4 DOI：10.3963/j.issn.2095-3852.2016.05.024