基于蚁群算法的云任务调度研究

王云松，孙佳林，龚跃

（长春理工大学计算机科学与技术学院，长春 130022）

基于蚁群算法的云任务调度研究

王云松，孙佳林，龚跃

（长春理工大学计算机科学与技术学院，长春 130022）

针对云计算中任务分配算法效率不高的问题，提出了一种改进的蚁群算法来解决云计算中的任务分配问题。首先假定要分配的任务为蚂蚁的起点，执行任务的虚拟机为蚂蚁的终点，任务分配的过程就是蚂蚁从起点走到终点的过程。然后随机选择一个任务作为蚂蚁的起点，用改进的蚁群算法计算后把任务分配给相应的虚拟机，直到所有任务都分配完成。最后当所有蚂蚁都把任务分配完成后，选择代价最小的路径作为本次任务分配的方案。通过使用cloudsim仿真器进行仿真实验，证明了蚁群算法能够有效的解决云计算中任务分配的问题。

蚁群算法；云计算；任务分配；cloudsim

任务分配是云计算［1-2］中的关键问题，近些年来人们也提出了很多种任务分配的方法。这些任务调度方法大致分为两类：基于效率的调度算法和基于公平的调度算法。基于效率的调度算法有传统的轮询调度算法、启发式遗传算法［3］、蚁群算法［4-9］、混合启发式算法［10］和模拟退火算法［11］等。基于公平调度的算法有回溯算法调度和改进的遗传算法调度［12］等。科学家们通过研究蚂蚁寻路的过程发现蚂蚁经过的路径上会留下一些信息素，蚂蚁会优先选择信息素浓度高的路径行走，最终会形成一条从蚁穴到食物的最短路径。本文将启发式算法中的蚁群算法进行改进并应用于云计算的任务分配中。

1 蚁群任务分配算法设计

通过分析蚁群算法解决TSP问题的过程［13-14］，下面将蚁群算法应用于解决任务分配的问题上。随机生成p个蚂蚁，其中第k只蚂蚁随机选择任务i，并计算从任务i到每一个虚拟机的概率。第k只蚂蚁将任务i分配到虚拟机j上运行的概率计算公式如（1）式所示。由（1）式可以看出任务i在虚拟机j上运行的时间越短，其概率值Pij(k)就越大，这就意味着第k只蚂蚁选中这条路径的概率就越大。

其中，i∈［1，n］代表要分配的任务，j∈［1，m］代表处理任务的虚拟机，timeij表示任务i在虚拟机j上运行的时间，α是任务运行时间的权重因子，β是信息素矩阵的权重因子，ηij表示任务i到虚拟机j路径上的信息素矩阵，τij表示将任务i分配给虚拟机j运行的奖惩因子，τij的计算公式如（2）式所示。如果虚拟机j上没有任务执行，则τij=1不进行惩罚，否则根据虚拟机上任务运行时间的长短进行惩罚。

其中，timeij表示任务i分配给虚拟机j运行所要花费的时间，taski虚拟机j上已分配的任务i运行所需时间，runtimej表示虚拟机j上已经分配的t个任务所要运行的总时间。其中runtimej的计算公式如（3）式所示。当第k只蚂蚁分配好所有任务后，需要用（4）（5）（6）式更新信息素矩阵。

其中，Δηij是信息素的增量，totaltimek是第k只蚂蚁分配完所有任务后，最慢完成所分配任务的虚拟机的运行时间。用上面（4）式计算第k只蚂蚁分配完成所有任务后在其所经过路径上留下的信息素增量。用（5）式更新信息素矩阵后，用（6）式蒸发所有路径上信息素的浓度，以避免因某条路径上信息素浓度过高影响其它蚂蚁对解空间的探索，使得算法过早收敛。ρ是蒸发因子，其取值范围在［0～1］之间。

第k只蚂蚁周游一圈的流程图如图1所示。第k只蚂蚁从任务列表中随机选择一个任务i，令虚拟机j=1，判断j＜m（虚拟机的数量）是否成立，如果成立则根据公式（2）进行奖惩因子的计算，根据公式（1）计算把任务i分配给虚拟机j的概率，然后让j++，选择下一个虚拟机。同样计算奖惩因子和概率，直到计算完成任务i分配给所有虚拟机的概率Pij，用random（）函数生成1到100的随机整数，然后把任务i分配给使得Pij*random（）最大的虚拟机。如果任务没有分配完成则继续分配，否则根据任务分配情况，更新信息素矩阵并开始第k+1只蚂蚁的游历。

用蚁群算法求解任务分配的步骤是：

（1）定义信息素矩阵ηij用来存储蚂蚁k从任务i走到虚拟机j所经过路径上信息素的浓度，其中ηij∈［0，1）。

（2）定义timeij矩阵来存储任务i在虚拟机j上运行的时间，其中timeij=任务i中所有要执行指令的长度/虚拟机j每秒钟执行的指令数。

（3）定义最短完成时间minTime和任务的分配方式bestArrange，初始化minTime为整型的最大值。

图1 第k只蚂蚁的任务分配流程图

（4）初始化信息素矩阵的所有值为0.1，根据任务的长度和虚拟机每秒执行指令数初始化timeij矩阵。

（5）初始化蚂蚁的数量是虚拟机数量的10倍以上。

（6）让第k只蚂蚁开始探索解空间。

（7）第k只蚂蚁随机在任务列表中随机选择一个任务i进行任务分配。

（8）根据公式（2）计算出将任务i分配给每一个虚拟机的奖惩因子，已经分配任务的虚拟机runtime时间越长其惩罚越严重，当没有任务运行时runtime=0，τ的值为1，表示不进行惩罚。

（9）根据公式（1）计算出将任务i分配给每一个虚拟机的概率值，其中任务i在虚拟机j上运行时间越短，其概率值越高。由于引入奖惩因子，所有没有分配任务的虚拟机比已分配任务的虚拟机被选中的概率要高。

（10）随机生成0到100以内的整数q，定义浮点数temp，让temp=q*p［i］［j］（任务i分配给虚拟机j的概率），选择所有从任务i到虚拟机j的路径中temp值最大的虚拟机r，并将任务i分配给虚拟机r。标记任务i为已分配状态，更新虚拟机r的运行时间为runtimer=runtimer+time［i］［r］（将任务i分配给虚拟机r的运行时间），并记录任务i已分配给虚拟机r。

（11）跳到第（7）步，重新选择一个没有分配的任务i+1进行虚拟机的分配。

（12）当第k只蚂蚁分配完所有任务后，记录第k只蚂蚁在这种分配方式下的任务完成时间finish-Time（finishTime是所有虚拟机运行时间（runtime）的最大值），如果finishTime小于minTime则让minTime=finishTime，并且用bestArrange记录第k只蚂蚁的分配方式。

（13）根据公式（5）更新信息素矩阵。

（14）根据公式（6）对蚂蚁留下的信息素进行蒸发，避免算法过早收敛。ρ为蒸发系数。

（15）跳到第（6）步，让第k+1只蚂蚁开始探索解空间。

（16）当所有蚂蚁都走完后，bestArrange中记录的就是最佳的分配方案。

（17）调用cloudsim仿真器的任务分配函数，按照bestArrange中记录的方案进行任务分配。

2 仿真实验设计与结果分析

CloudSim［15-17］是一款很好的云计算仿真平台，它使用Java语言编写，可以很容易的实现数据中心、物理机、虚拟机和网络的创建。能够很方便的对物理机和虚拟机进行配置，如CPU的处理能力、内存的大小、硬盘的大小和带宽的大小进行配置。

图2 CloudSim仿真流程图

用CloudSim来进行仿真的流程如图2所示。初始化CloudSim包，利用CloudSim所提供的方法来创建数据中心，给创建好的数据中心分配虚拟机并设置虚拟机的参数，然后CloudSim会进行参数的校验，校验成功后启动仿真并输出结果。

用CloudSim来进行任务调度仿真的步骤如下：

（1）初始化CloudSim的包。

（2）创建数据中心。

（3）创建物理机，设置物理机参数（如CPU、内存、硬盘、网卡信息等）并分配网络带宽。

（4）创建虚拟机，设置虚拟机的参数（如CPU、内存、硬盘、网卡信息等）并分配网络带宽。

（5）创建一系列任务并按照特定的任务调度算法将任务分配给虚拟机。

（6）启动仿真并记录输出的结果。

（7）仿真结束。

表1 不同任务数量下两种调度策略的执行时间（ms）

创建50台虚拟机，设置每台虚拟机的计算能力参数mips（每秒钟执行百万条指令）是在10～100内随机生成的一个整数值，即mips∈［10，100］，这能体现出每台虚拟机的计算能力都是不同的。创建10个测试组，每个测试组包含100，200，300，……1000个任务，其中每个任务的长度是在10000～100000（该任务包含多少百万条指令）内随机生成的一个整数，表示每个任务的长度不同。其中蚁群任务调度算法的初始化参数为：α=1、β=1、ρ=0.5、AntNum= vmNum*10、AntGen（蚁群的代数）=2。

图3 两种调度算法任务完成时间

分别使用轮询调度算法（RR）和蚁群任务调度算法（ACO）进行仿真实验，仿真结果如表1所示。

通过表1的仿真数据，轮转调度算法和蚁群调度算法分别在分配了100到1000个任务后，通过CloudSim仿真平台进行相应的任务调度，按照每批任务完成所用时间做折线图。结果如图3所示。

可以得出如下结论：改进的蚁群算法整体要好于轮询调度算法，随着任务数的增加，蚁群算法处理用时大大优于轮询调度算法。

3 结论

通过将蚁群算法从TSP问题移植到云计算任务分配中来并进行相应的改进后，发现蚁群算法能够较好的解决任务分配问题，使得任务的完成时间比传统的轮询调度算法完成时间短。蚁群算法是模拟自然界中蚂蚁寻路的仿生学算法，在利用正反馈方式求解任务分配的过程中，得到了较为理想的仿真结果。

［1］王于丁，杨家海，徐聪，等.云计算访问控制技术研究综述［J］.软件学报，2015，26（5）：1129-1150.

［2］王继，程志华，彭林，等.云计算综述及电力应用展望［J］.中国电力，2014，47（7）：108-112+127.

［3］张雨，李芳，周涛.云计算环境下基于遗传蚁群算法的任务调度研究［J］.计算机工程与应用，2014，50（6）：51-55.

［4］GanRongwei，GuoQingshun，ChangHuiyou，Yi Yang.Improvedantcolonyoptimizationalgorithm for the traveling salesman problems［J］.Journal of Systems Engineering and Electronics，2010，21（2）：329-333.

［5］MaurizioMarchese.Anantcolonyoptimization method for generalized TSP problem［J］.Progress in Natural Science，2008，18（2008）：1417-1422.

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

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

［8］黄俊，王庆凤，刘志勤，等.基于资源状态蚁群算法的云计算任务分配［J］.计算机工程与设计，2014，35（9）：3305-3309.

［9］赵飞，吴航，龚跃.蚁群算法解决网格环境下任务调度问题的研究［J］.长春理工大学学报：自然科学版，2013，36（Z1）：97-100.

［10］孔令夷.面向有约束TSP的一种混合启发式算法［J］.西安邮电大学学报，2013，18（1）：86-89.

［11］罗晨，李渊，刘勇，等.基于模拟退火遗传算法的多agent系统任务分配［J］.计算机应用研究，2012，29（6）：2114-2116.

［12］于莹莹，陈燕，李桃迎.改进的遗传算法求解旅行商问题［J］.控制与决策，2014，29（8）：1483-1488.

［13］刘少伟，王洁.一种改进的蚁群算法在TSP问题中的应用研究［J］.计算机仿真，2007，24（9）：155-157+ 186.

［14］韩成，赵斌，白宝兴，等.基于集群的蚁群算法在TSP中的应用研究［J］.长春理工大学学报：自然科学版，2008，31（4）：109-112..

［15］王霞俊.CloudSim云计算仿真工具研究及应用［J］.微型电脑应用，2013，29（8）：59-61.

［16］查英华，杨静丽.云计算仿真平台CloudSim在资源分配研究中的应用［J］.软件导刊，2012，11（11）：57-59.

［17］王燕妮，吴文辉.Cloudsim3.0仿真流程分析［J］.软件，2014，35（4）：63-64.

Research of Cloud Task Scheduling Based on Ant Colony Algorithm

WANG Yunsong，SUN Jialin，GONG Yue

（School of Computer Science and Technology，Changchun University Of Science and Technology，Changchun 130022）

In order to solve the problem of low efficiency of task allocation，an improved ant colony algorithm was proposed to solve the problem of task allocation in cloud computing.Firstly，It was assumed that the task was the starting point of the ants，the virtual machine to perform the task was the end of the ants，the process of task allocation was the process of ants from the beginning to the end.Secondly，one task was selected as the starting point of the ants randomly.The improved ant colony algorithm was used to assign the task to the corresponding virtual machine.Until the end of the task assignment was completed.Finally，the path of the minimum cost was chosen as the solution of this task when all the ants were assigned to the tasks.By using the cloudsim simulator，it is proved that ant colony algorithm can effectively solve the problem of task allocation in cloud computing.

Ant Colony Optimization，cloud computing，task allocation，cloudsim

TP399

A

1672-9870（2017）01-0133-04

2016-09-05

王云松（1987-），男，硕士研究生，E-mail：wang_yun_song@163.com

龚跃（1960-），男，教授，博士生导师，E-mail：gongyue888878@sina.com