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

于淑香，周洪斌

（沙洲职业工学院 电子信息工程系，江苏 张家港 215600）

引言

云计算是网格计算、并行计算和分布式计算等多种技术的融合[1]，其本质是把各地的计算机资源及相关的终端设备等组织在网络“云”中，为广大用户提供软件、存储、计算和大数据的访问使用等服务。云计算系统是采用多种技术把“云”中各种资源进行重组形成一个巨大的资源库，方便随用随取，解决了当前大数据时代，激增的数据量和计算机有限的硬件水平及处理能力的矛盾。云计算的使用类似居民用水电一样“按需使用，按量付费”，具有较高灵活性和可靠性。高效的任务调度和合理资源分配是提高云计算系统性能的重点和难点，这些技术的提高能使云计算系统更好地满足客户需求，降低能源消耗，提高企业效益。

资源调度模型的发展过程分为两个阶段，启发式算法和传统的资源调度算法。启发式算法主要根据非线性理论和人工智能理论，模拟生物的自然行为寻找一些资源调度问题的最优解[2]。而传统的资源调度算法有先来先服务，贪心法、轮转调度，最大最小等算法。很多专家和学者研究实验表明，在云计算任务调度中，使用启发式算法明显优于传统的资源调度算法，具有不可比拟的优越性。

1 云计算任务调度模型

1.1 云计算的编程模型

云计算系统包含很多复杂和结构迥异的资源，最优的任务调度方案能保证快速完成用户任务并且提高系统的效率和利用率。当前的云计算系统大部分选用Map/Reduce思想的编程模型[3]，该模型特别适合应用于云计算系统中大规模数据集的产生和处理。任务调度模型如图1所示。

图1任务调度模型

云计算系统中有巨大的用户量和任务量，在用户提交任务后，任务调度系统首先要进行任务分布式化，即切分任务，把用户提交的任务集切分成多个子任务；子任务提交给调度中心后，根据映射法则的算法，把每个子任务调度分配给虚拟资源节点。

1.2 任务调度的相关定义

按照相关的算法将N个用户任务分配到M个虚拟资源节点上（M＜N），云计算环境下任务的数学模型表示如下：

⑴T={T1，T2，……Tn}表示N个待执行独立任务的集合。

⑵V={V1，V2，……Vm}表示M个虚拟机资源节点。

⑶MIPS={MIPSl，MIPS2，……，MIPSm}表示M个虚拟机的计算能力，即计算速度，MIPSi表示虚拟机Vi单位时间内处理的指令数，以百万/秒计。

⑷任务和虚拟机节点之间的映射关系如矩阵M表示，若任务Ti被分配到虚拟机Vj上执行调度，则矩阵中的元素Mij=1，否则Mij=0。

⑸任务的期望执行时间，即第j个子任务在第i个虚拟机上执行时间。

由上述矩阵，可以计算出每个虚拟机Vi执行子任务的时间，如公式（1）所示。

公式中n表示虚拟机Vi执行的子任务数量，Time(i,j)表示虚拟机Vi上的第j个子任务执行时间。

2 改进蚁群优化算法

蚁群算法是学者Mr.Dorigo等提出的，该算法受自然界中蚂蚁的觅食行为过程启发而提出。该算法具有启发式、正反馈和分布式的搜索特点，在许多NP类问题的优化求解过程中被普遍应用，如模式识别、旅行商问题、车辆调度、多重背包等。随着算法应用演变发展，出现了更接近现实的模拟蚂蚁觅食过程的算法，即蚁群优化算法。

2.1 蚁群优化算法原理

设蚂蚁数量是n，在寻找食物经过的路径上，蚂蚁会留下信息素，而后来的蚂蚁会依据在此路径上走过的蚂蚁留下信息素浓度去选择合适的路径，即每只蚂蚁会根据一定的概率转移到下一个虚拟机资源节点，在t时刻，第k只蚂蚁从虚拟机Vi访问虚拟机Vj的概率计算如公式（2）所示。

其中:τij表示路径(i,j)上的信息素浓度，α表示蚂蚁对信息素的敏感度；β表示蚁群对信息素的敏感度，ηij表示节点j对节点i上蚂蚁的吸引水平，即启发因子，allowedk表示还没有访问的节点。

在不断寻找食物的过程中,蚂蚁在路径上留下的初始信息素会陆续散发掉,同时又会在路径上继续释放出新的信息素，所以为了有利于发现最优的解，在蚁群优化算法中，要更新路径上的信息素，全局和局部的信息素更新如公式（3）所示。

其中:ρ ∈(0,1]表示信息素挥发系数，Δτij(t)表示所有m只蚂蚁释放在路径上的信息素总量(t)表示在路径(i,j)上第k只蚂蚁释放信息素的增量，计算信息素增量如公式（4）所示。

其中，Q表示一次搜索结束后路径上存留信息素的总量；Lk表示蚂蚁k走过路径总长度。

2.2 蚁群优化算法的改进

2.2.1 信息素初始化

在初始时刻，利用蚁群优化算法原理将蚂蚁（任务）随机的放到云计算系统中的任意一个虚拟机上。此虚拟机处理器的数量为v_num。各处理器的处理能力v_pc，通信带宽能力v_bw等参数。利用这些参数指标，云计算系统可以初始化每个虚拟机的信息素值，计算如公式(5)所示。

其中虚拟机i的指标如下：τi()0是信息素初始值，v_numi是处理器的数量，v_pci是处理器的处理能力（即MIPS），v_bwi是通信带宽[4]。

2.2.2 选择虚拟机概率

在改进算法中，蚂蚁（任务）从虚拟机Vi访问虚拟机Vj的概率计算如公式（6）所示。

式中，q0∈(0，1)是给定的参数，q为(0，1)范围内的随机数。当 q＜q0时，j取 MAX{allowedk}中的k，能够得到使边(i,k)距离i最短、信息素最高的节点作为下一节点[5]。

当q＞q0时，启发信息函数ηij表示任务i选择虚拟机j的期望值。在此取ηij=propertyj*LLj,其中propertyj是固定值等于τi()0的值,其计算如公式（5）所示，LLj是虚拟机负载能力的衡量值，其值高低代表虚拟机当前状态下处理能力的高低，当该值比较高时，被选择的概率就更大。LLj的计算如公式（7）所示。

其中AVTime表示截止到前一次迭代结束时，在最优路径中的每个虚拟机Vi的平均执行时间。

2.2.3 信息素更新

在蚂蚁选中路径(i,j)后，立即按公式（8）局部更新路径(i,j)上的信息素。

式中，ρ是信息素的挥发因子，且ρ∈(0，1]，信息素的残留浓度用1-ρ表示，ρ值越大，散发越快，则残余浓度越低，所以曾探寻过的路径对选择当前路径的影响相对较小。信息素的增量用Δτij()t表示，第k只蚂蚁在本次迭代中经过路径的长度用Lk表示[6]。

在蚂蚁确定选择某一路径后应减少该条路径上的信息素，同时增加其余路径边被选择的概率，当所有蚂蚁都走完一次循环之后，根据式（9）全局更新信息素，进而使最佳路径的搜索概率更大[5]。

公式中，Lgbest是此刻得到的最优路径。

2.3 算法描述

⑴算法参数初始化，包括云计算虚拟机节点数，任务数，信息素和迭代次数等各参数。

⑵将X只蚂蚁随机放置在虚拟机节点上。

⑶计算出蚂蚁个体转移到下一虚拟机节点的概率，并根据计算结果进行移动。

⑷局部更新蚂蚁走过路径上的信息素值，并修改相应的禁忌表。

⑸重复步骤2)～4)，直到蚁群中的每个蚂蚁个体找到一条可行的路径截止。

⑹全局更新所有路径的信息素。

⑺增加迭代次数，如其值已达预设的最大迭代次数，则停止搜索，获得云计算任务调度的最优解。

3 仿真实验及结果分析

3.1 实验环境

为了验证改进蚁群算法在云计算系统中任务调度分配优化效果，本文选用澳大利亚墨尔本大学和Gridbus项目共同提出的云仿真软件CloudSim平台进行测试实验[7]，实验的硬件环境为2.66GHz的CPU，8G的内存，500G硬盘作为硬件环境，Windows10操作系统和JDK8.0的基础环境及Antl.9.7的编译工具。在CloudSim平台中对比测试本文改进蚁群优化任务调度算法、标准蚁群算法和MAX-MIN算法在任务调度分配执行方面的效率。通过初始化CloudSim，创建数据中心及DataCenterBroker,创建虚拟机、云任务集等一系列的操作后开始仿真实验。

3.2 结果分析

仿真实验主要测试在任务数量增加的情况下，本文算法的任务平均完成时间，并与其他比较算法进行对比，公平起见所有测试的算法都进行10次实验，统计平均，横坐标为申请任务数量，纵坐标为各算法分别完成任务处理所需时间。在实验软硬件环境相同，资源节点相同的情况下，几种算法的任务完成时间对比如图2所示。

图2各算法任务执行时间对比

在文件任务量不大情况下，各算法完成任务分配执行所用时间差别不大，但从整体上来看，任务量相同时本文改进蚁群优化算法执行任务用时比较短。而随着任务数量的增加，本文算法完成任务时间增幅度不大，相反另外两种比较算法的执行时间增加幅度非常大。同时在实验中发现本文算法的迭代次数少于其他比较算法，这是因为本文算法成功地避免了传统蚁群优化算法容易陷入局部最优解的缺点，这样可以使用户提交的任务在相应的资源节点最快分配执行完成，提高云计算系统的工作效率，取得了比较理想的资源任务调度效果。

4 结语

本文提出了基于改进蚁群优化算法的云计算任务调度算法。首先介绍了云计算系统的编程模型和任务调度相关定义，然后针对传统蚁群优化算法进行改进，并在CloudSim平台测试该算法在云计算系统任务调度中的性能。仿真实验结果表明，该算法在云计算系统任务调度方面有较好的性能，提高了资源的利用率。