基于改进蚁群算法的云计算任务调度研究*

魏 勇，赵开新，张松青，王东署

（1.河南工学院，河南 新乡 453003；2.郑州大学电气工程学院，郑州 450001）

基于改进蚁群算法的云计算任务调度研究*

魏 勇1，赵开新1，张松青1，王东署2

（1.河南工学院，河南 新乡 453003；2.郑州大学电气工程学院，郑州 450001）

把改进的蚁群算法应用到云计算任务调度中，通过将任务在虚拟机上的一次分配作为蚂蚁的一次成功搜索，实现了虚拟机的负载均衡和调度时间的优化，提高云计算资源分配的效率。通过在CloudSim平台下进行仿真测试，结果显示，改进蚁群算法在负载均衡性能和总的任务调度时间方面均优于基本的蚁群算法。

基本蚁群算法，改进蚁群算法，云计算，任务调度

0 引言

云计算是一种新兴的计算模式，它是并行计算、分布式计算和网格计算的发展，它真正体现了按需服务的理念，它对存在于云计算环境中的海量数据、软硬件资源进行统一管理，并将这些资源进行虚拟化，形成一个巨大的资源池，当用户需要这些资源时，就通过某种调度方式，从资源池中动态获取资源［1-2］。因此，如何对资源池中的资源进行管理和分配，如何对任务进行高效地调度成为云计算中所要解决的重要问题。

蚁群算法是一种智能算法，被应用到云计算中，能缩短任务执行时间，提高负载平衡度，较好地解决云计算中资源的管理和调度，以及虚拟机的负载均衡。但存在搜索最优路径所需迭代次数多、效率低以及容易陷入局部最优路径等缺陷［3-5］。本文通过对基本蚁群算法进行改进，提出了一种云环境下基于改进蚁群算法的任务调度方案。

1 云计算任务调度

1.1 云计算体系结构

在云计算中，通常将系统划分为如下页图1所示的三层结构，分别为应用层、虚拟层和基础设施层。云计算的分层模型很多，但所有分层模型都是基于这三层为基础的，并且调度模型也是建立在这三层结构之上。应用层是云计算向用户展示服务以及用户向云计算申请服务的接口，主要负责向虚拟层提交任务、向用户收集申请。虚拟层则是应用层用户能够看到的自己获得的全部资源，负责给用户的具体申请来分配虚拟机资源，将满足运行条件的任务交给基础设施层执行。基础设施层则是实际的服务器集群［6-8］。

图1 云计算体系结构

1.2 问题的描述

用户任务集合为：R={task1，task2，task3，…，taskn}，taski（i∈［1，n］）表示编号为i的任务，Q={taskit，taskic}，表示完成任务i所需的时间和对CPU的硬件需求。虚拟机的集合表示为V={v1，v2，v3，…，vm}，vi（i∈［1，n］）表示编号为i的虚拟机。预期完成时间（ETC，excepted time to completion）表示任务taski独立在虚拟机vmj上的执行时间为ETCij，所有ETCij元素组成ETC矩阵，式（1）是n个任务在m个虚拟机对应的ETC矩阵。

本文针对资源调度模型作出如下假设：

假设1：各任务之间没有依赖关系，虚拟机的性能能够满足任一任务的要求；

假设2：所有的任务可以被完全分配；

假设3：资源是被独占的，非共享的，一个任务只能分配给一个虚拟机。

任务调度的目标是建立任务与资源之间的映射，即R→V的映射。本文将改进蚁群算法应用到云计算的任务调度中，为任务寻找最优的映射，使任务完成时间缩短，减少资源消耗，提高云计算的效率和性能。

1.3 云计算中蚁群算法的调度过程

算法的调度过程如图2，当有任务申请、结点失效和结点过载时会触发蚁群算法调度。其中任务申请是有新任务时正常的任务提交，结点过载是当有结点负载超过92%时发出的均衡负载申请，结点失效是当正在执行任务的结点Down机时发出的负载转移申请。正常的任务申请是由虚拟机触发的，而结点失效和结点过载也会触发任务的申请。蚂蚁寻找信息素值大的结点。每一次蚂蚁遍历的都是负载较低的结点，该结点会因获得新的任务而负载上升，信息素值下降。而高负载结点由于获得任务多，随着先前任务的结束而负载下降，信息素值上升。这样多次调度后，低负载结点负载会升高，而高负载结点负载会降低，真正实现负载均衡。

图2 蚁群算法调度结构图

2 蚁群算法的改进

在蚁群算法中信息素挥发系数ρ的取值对算法的性能影响很大，为了提高算法的自适应性，本文对基本蚁群算法信息素挥发系数动态进行调整：

式中，ρmin和ρmax为挥发系数的最大和最小值，min和max为防止信息素最低或者最高的极限值。（t）为时变函数，值域介于ρmin和ρmax之间，其值变化趋势如图3。

图3 （t）曲线变化图

由于云计算任务的调度比较复杂，为了建立任务和资源的映射，改进的蚁群算法信息素函数将对求解到的全局最优路径给予奖励，即对其所包含的路径上的信息素浓度进行加强，同时对求解到的局部迭代最差路径给予惩罚，即对其所包含的路径上的信息素浓度进行减弱，这样，最优路径和最差路径信息浓度的差异会进一步扩大，从而达到使蚁群尽可能地在最优路径附近搜索的目的。

改进后的蚁群算法的全局信息素浓度更新方式为：

式中，Lbest是全局最优路径，Lworst为迭代最差路径，σ为算法中引入的一个参数。

每只蚂蚁完成对路径的搜索后都要对其所走过的路径进行一次局部更新，该局部更新方法参照基本蚁群算法模型。局部更新的公式为：

式中ρ为信息挥发系数。

式中Lk表示第k只蚂蚁求得的路径距离，Q为算法中引入的一个参数。

3 改进的蚁群算法在云计算中的调度方案

把改进的蚁群算法应用在云计算中，设计出组合优化的模型，求得一个解s={X1，X2，…，Xm}的过程就是对其中每个决策变量Xi的求值过程，其中n是任务数，X的值域是元素（T，Vm）的集合，即n个任务{task1，task2，task3，…，taskn}、m个虚拟化资源{v1，v2，v3，…，vm}的迪卡尔积。元组（T，Vm）任务到资源的一个分配，是将任务T分配到资源Vm上，可以用一只蚂蚁在一张图G上的爬行过程来模拟，图上的每个顶点是一个分配，当任务分配完后，蚂蚁爬行结束，每个任务只能被分配一次，得到的解S的预期执行时间是个合理的目标函数，每个可能的决策（T，Vm）都有一个信息素P相对应，在算法开始执行时初始化信息素，并且信息素的值随着算法的运行而被更新。具体的调度过程如图4。

图4 改进蚁群算法的云计算调度流程图

4 实验与分析

本文采用CloudSim作为实验模拟平台来验证改进蚁群算法在云计算中应用的可行性和有效性，通过CloudSim中的DataCenter、VM等模拟计算机网络的资源、任务以及虚拟机，构建出云计算的仿真环境，在实验中设定任务数从20到100个，计算节点数为6个，虚拟机个数为10，蚂蚁数为10到100，迭代次数为600。信息启发算子α和期望启发算子β分别为1、5，信息素残留算子ρ=0.65。基本蚁群算法和改进后的蚁群算法完成任务所需的时间如图5，其中ACO表示基本蚁群算法，IACO表示改进蚁群算法。

图5 两种算法执行完任务所需时间

从图5可以看到，当任务量比较小时改进的蚁群算法和基本蚁群算法执行时间差别不大，但随着任务量的增加，改进后的蚁群算法明显比基本蚁群算法执行的时间减少，当任务达到100时，两种算法执行时间相差将近2 s，由此可以看出，在一定范围内，随着任务数的增加，这两种算法分配资源并执行的时间开销相差越来越大，因此，改进的蚁群算法在云计算中任务调度效率较高。

下页表1显示了基本的蚁群算法和改进的蚁群算法，每个节点上所分配的任务数，其中ACO表示基本蚁群算法，IACO表示改进蚁群算法，从表中可以看出采用改进蚁群算法执行任务时节点的负载均衡度较高。为了更直观地显示两种算法的差别，求解出两种算法任务分配结构的相对标准偏差，如图6所示。

表1 各节点上任务分配结果

图6 任务分配结果相对偏差

5 结论

在云计算环境中，资源的合理分配与管理、任务的调度是保证云计算服务质量的关键，为了在云计算环境中进行合理的任务调度，缩短完成总任务的时间，各节点尽可能达到负载均衡，把改进的蚁群算法应用到云计算任务调度中，通过仿真测试表明，随着任务量的增加，和基本蚁群算法相比，任务执行的时间明显减少，节点的负载均衡度有了明显提高。

［1］刘漳辉，王晓莉.云计算虚拟机群中带遗传算法的负载均衡算法［J］.福州大学学报，2012，40（4）：453-458.

［2］杨庆芳，梅朵，韩振波，等.基于云计算的蚁群算法求解城市路网最短路径［J］.吉林大学学报，2013，43（5）：1210-1214.

［3］査英华，杨静丽.改进蚁群算法在云计算任务调度中的应用［J］.计算机工程与设计，2013，33（5）：1716-1719.

［4］张陶.基于改进粒子群算法的云计算任务调度算法［J］.计算机工程与应用，2013，49（19）：68-72.

［5］刘卫宁.基于改进量子遗传算法的云计算资源调度［J］.计算机应用，2013，33（8）：2151-2153.

［6］YAGMAHAN B，YENISEY M M，A multi-objective ant colony system algorithm for flow shop scheduling problem［J］. Expert Systems with Applications，2010，37（2）：1361-1368.

［7］张春艳.基于蚁群优化算法的云计算任务分配［J］.计算机应用，2012，32（5）：1418-1420.

［8］刘新华，张旭堂，刘文剑.基于改进最大-最小蚂蚁系统的多工艺线路决策方法［J］.计算机集成制造系统，2008，14（12）：2414-2420.

Cloud Computing Task Scheduling Based on Improved Ant Colony Algorithm

WEI Yong1，ZHAO Kai-xin1，ZHANG Song-qing1，WANG Dong-shu2
（1.Henan Institute of Technology，Xinxiang 453003，China；2.Electrical Engineering School of Zhengzhou University，Zhengzhou 450001，China）

The improved ant colony algorithm is applied to the cloud computing task scheduling，realize load balancing and scheduling time optimization of virtual machine，improve the efficiency of resource allocation in cloud computing is improved.Through task in a virtual machine a distribution as ants to a successful search，the simulation test under the CloudSim platform，the results show that the improved ant colony algorithm is better than the basic ant colony algorithm in the load balancing performance and the total task scheduling time.

ant colony algorithm，improved ant colony algorithm，cloud computing，task scheduling

TP309.2

A

1002-0640（2017）05-0130-04

2016-03-18

2016-05-17

国家自然科学基金（61174085）；河南省高等学校重点科研基金（16A520084）；河南省高等学校教学工程基金（豫教高2012［1099］号）；河南省高等学校教学工程基金资助项目（豫教高2012［1185］号）

魏 勇（1982- ），男，河南卫辉人，硕士，讲师。研究方向：云计算、计算机网络。