基于蚁群优化算法的云任务分配策略研究

姜力争 裴云曼 赵建涛

(华北电力大学控制与计算机工程学院 北京 102206)

0 引 言

云计算[1-2]是一种新型的计算模型，它通过虚拟化技术，将分布于不同网络节点的资源联系起来形成资源池，为用户所需资源进行统一管理和统一分配。而云计算中的任务分配算法的优劣对用户的满意程度与平台的质量效率产生了直接的影响，因此任务分配算法一直是云计算领域的重点研究方向。近年来，许多专家学者对云计算中的任务分配问题进行了深入研究。任务分配算法大致可以分为三类[3]。第一类为基于经典策略的任务分配算法，如轮询算法、Min-Min算法和Max-Min算法等。第二类为基于单一群智能优化算法的任务分配算法，如蚁群算法、遗传算法、蛙跳算法等。第三类为基于混合群智能优化算法的任务分配算法，如遗传-蚁群算法[4]、蛙跳-蚁群算法[5]等。

蚁群算法[6](Ant colony optimization,ACO)是一种仿生优化算法，其灵感是Marco Dorigo发现蚂蚁在觅食过程中群体所表现出来的超高的团队合作能力，能够很好地应用于任务-资源分配的N-P问题。文献[6]提出劣化因子蚁群算法，劣化因子的合理选择不仅可以平衡负载还能提高资源的利用率。文献[7]提出的改进信息素挥发程度的蚁群优化算法，提高局部和全局的搜索性能。文献[2]提出的基于资源状态的蚁群算法，在资源消耗和任务等待时间上有较大优势。上述研究从不同角度上都改进了云计算任务分配问题。但是云计算的任务分配问题是一个需要以多指标最优为最终目标，既要考虑云服务的稳定性和用户的满意程度，又要考虑资源的使用效率和运营成本。现有的研究多以单一指标为最终的研究目标，缺乏对任务分配问题的全面考虑。

针对上述的问题，本文通过对任务分配模型的分析，提出服务稳定性好、资源利用率高、任务完成时间短的任务分配模型。基于该模型，改变资源执行任务的可见度，自适应方式调节信息量，根据虚拟机状态更新信息素的蚁群优化算法。与轮询算法、Min-Min算法、标准蚁群算法以及文献[11]提出的优化蚁群算法(OACO)进行仿真实验，实验结果表明该蚁群优化算法在任务完成时间、资源利用率以及服务稳定性上具有显著优势。

1 任务分配模型分析

云环境下的任务分配模型[1]可以分为三层：应用层、调度层和物理层。在云环境中，应用层存在多个用户，每个用户都可以发送请求来运行多个应用，每个应用又对应着多个任务。调度层会根据不同的任务分配不同的虚拟机。任务分配的过程实质上是将任务按照某一分配原则分配到虚拟机节点上执行的过程。任务分配过程，如图1所示。

图1 任务分配过程

由此，可将任务在虚拟机上的执行时间定义为Max(costi)，总资源消耗定义为∑exeij。

2 基本蚁群算法

蚁群算法具有并行、自组织、鲁棒性强、正反馈的特点[8]。其智能性主要体现在以下三个方面：

(1) 蚂蚁之间可以利用信息素进行“交流”。

(2) 蚂蚁在搜索路径的过程中，已经被蚂蚁搜索过的路径将不会再被选择。

(3) 蚂蚁之间有很强的团队合作能力，单凭一只蚂蚁，很难找到食物。

2.1 定义变量

为了方便描述，定义以下变量：

antNum为蚂蚁数量；

taskNum为任务数量；

vmNum为虚拟机数量；

iterationTimes为迭代次数；

optimalPath为最优路径；

pheromone[taskNum][vmNum]为信息素矩阵；

α为信息素因子；

β为可见度因子；

ρ为信息素挥发因子。

2.2 算法步骤描述

Step1初始化信息素矩阵、最佳长度以及antNum只蚂蚁。

pheromone[i][j]=0.1f,ifi

optimalPath=MAX_VALUE

Ants[i].init(exe,α,β), ifi

Step2如果循环次数小于迭代次数iterationTimes，则执行第三步到第五步，否则输出结果，算法结束。

(1)

Step4更新禁忌表和可搜索列表。

Step5更新信息素浓度。

(2)

(3)

基本蚁群算法的任务分配流程如图2所示。

图2 基本蚁群算法的任务分配流程

3 蚁群优化算法

基本蚁群算法[8]在处理较小规模的任务分配问题时能够快速找到最优解，但随着大数据时代的带来，数据呈现出井喷式爆发增长的趋势，数据的高性能计算是云计算任务分配的核心问题。基本蚁群算法随着数据规模的扩大计算性能严重下降，为此，本文针对基本蚁群算法的缺点进行了优化改进。

相较于基本蚁群算法，优化算法主要体现在以下几个方面。

(1) 根据虚拟机状态对任务ti选择虚拟机rj执行的启发式因子ηij(t)进行优化。将虚拟机的消耗考虑其中，减少任务的等待时间。

(4)

式中：costj(t)表示t时刻虚拟机vmj的状态情况。

(2) 在任务选择虚拟机vj执行后，更新虚拟机的消耗状态costj。

costj=costj+exeij

(5)

(3) 更新信息素浓度时，采用自适应信息量的更新策略改变τij(new)的值，动态调整信息量强度，提高全局的搜索能力，避免陷入局部最优解。

(6)

(7)

式中：Q为常量，代表每只蚂蚁释放信息素的强弱程度。

4 实验设计与分析

本实验采用CloudSim-3.0.3作为实验环境，步骤主要包括：产生实验数据，为保证实验的准确性，每种条件的数据为10组，取平均值作为最终结果。将不同条件的数据由不同的算法执行求取最优解，使用CloudSim进行仿真实验，得出的实验结果做可视化图形处理。

由文献[9]可知，任务执行时间可以认为只与任务的指令长度(MI)和虚拟机的执行速度(MIPS)有关，一个任务所需的执行时间等于任务指令长度除以运行该任务的虚拟机的执行速度。创建指定任务数量以及任务长度等信息的云任务，提交给任务代理。创建指定CPU数量以及执行速度等信息的虚拟机提交给任务代理。任务代理根据QoS要求提供任务与资源的分配策略。模拟为虚拟机分配处理核所用的策略为空间共享。

以随机数的方式设置任务的MI范围为500 000到3 000 000。以随机数的方式设置虚拟机的MIPS范围为500到2 000。设置任务数分别为20、40、60、80、100。设置虚拟机数为5。设置蚂蚁数为100，迭代次数为50。

根据文献[10]研究，将蚁群算法的参数设置为α=1.0，β=5.0，ρ=0.5，Q=5.0。

综上所述，云计算任务分配仿真实验参数设置表见表1。

表1 云计算任务分配仿真实验参数设置表

如图3所示，所提出的基于资源状态的自适应蚁群优化算法(MACO)调度任务完成时间最短，相比于轮询算法(RR)与基本蚁群算法(BACO)具有显著优势，并且随着任务数量的增加，优势会愈加明显。Min-Min算法是将最小的任务映射到执行最快的虚拟机上，结果显示Min-Min算法的效果较好，仅稍次于MACO算法。本文提出的MACO算法相比于RR算法提高了35.55%±8.13%，相比于BACO算法提高了20.5%±7.13%，相比于Min-Min算法提高了8.21%±5.07%。

图3 任务完成时间对比图

文献[11]提出的优化蚁群算法(OACO)，其实验参数与实验结果与本文较为相似，因此采用文献[11]中的实验结果数据进行对比实验。为与文献[11]中的数据保持一致性，另外生成一组任务数为25、50、75、100的实验数据。为排除因实验数据不同而造成的差异，均以相对RR算法的比值进行比较。如图4所示，OACO算法相对RR算法的时间比例随任务数的变化起伏较大，算法的稳定性比本文提出MACO差。在任务数为25时，OACO算法的完成时间优于本文的MACO算法，但随着任务数的增加，本文提出的算法MACO提高比例逐渐降低并显著优于OACO算法。无疑在大数据的时代，本文提出的MACO算法稳定性更高。OACO算法相比于RR算法提高了43.88%±6.85%，而本文提出的MACO算法相比于RR算法提高了44.29%±3.62%，以标准差来衡量算法的稳定性，则本文算法的算法稳定性是OACO算法的1.89倍。

图4 相对RR算法完成时间对比图

平台的占用时间，是一批任务全部完成时占用虚拟机的全部时间和，可以反映任务对资源的消耗情况。如图5所示，完成同一批任务，本文提出的MACO算法占用平台时间最少，平台资源的利用率最高。本文提出的MACO算法相比于RR算法提高了9.11%±2.78%，相比于Min-Min算法提高了1.81%±1.59%。

图5 平台占用时间对比图

5 结 语

本文提出了一种基于资源状态的自适应蚁群优化算法，该算法利用虚拟机的状态来修正启发式因子和释放信息素浓度，并以自适应的方式进行信息量的更新，避免早熟和局部收敛，提高全局搜索能力。实验结果表明，该算法在任务完成时间、资源利用率和服务稳定性方面均有良好表现。