基于QoS云计算任务调度优化

聂清彬，陈飞旭，秦美峰，曹耀钦

(1.西南交通大学希望学院,成都 610400;2.成都文理学院,成都 610400;3重庆工程学院,重庆 400065)

近年来,云计算凭借其低成本、配置灵活和资源利用效率高的优势,正在以极快的速度兴起。在云计算[1-2]中,其资源的分配一直是研究的重点,云计算的用户可以根据自己的需求来付费和购买适合的资源，从而最大程度节省了成本，给用户带来了更好体验。因此，就如何规划、利用庞大的云计算资源问题,国内外学者从自己的研究中提出了相应的观点。方秋义等[3]采用一种满足一定条件下的低成本和低负载的资源分配策略，以此实现系统的负载均衡；李志敏等[4]通过在云计算资源算法中引入人工蜂群算法，算法收敛精度提高，使云计算资源分配的效率提升；魏杰等[5]将针对数据密集型应用的虚拟资源分配,提出云环境下时延敏感的虚拟机放置方法,该方法可以有效地降低总数据传输时延和最大数据传输时延，获得较优的云计算资源，从而节省运营成本；蔡晓丽等[6]设计了一种改进的粒子群算法，通过改进粒子迭代过程中社会项系数和认知项系数的权重变化,使算法更符合最优解的求解规律,避免陷入局部最优解，以此提高资源分配的准确性；王英等[7]提出了一种基于生产函数的云服务提供商收益最大化同时兼顾用户满意度的资源调度算法，合理规划云服务器所有资源,最大程度优化配置资源;然后结合用户请求，解决了云数据中心资源利用率低、云服务提供商收益低的问题。

这些算法虽然能够成功地完成云计算的资源分配,但由于云计算技术的飞速发展，用户对其使用的需求日益提高，用户在关注任务是否能完成的同时，更加注重于完成调度的成本和时间等。在现有研究基础之上，将传统蚁群算法进行改良得到改进的蚁群优化算法(improved ant colony optimization algorithm),使算法的效率明显提高。在处理云计算资源分配方面的问题时有了明显的提升，在减少成本的同时节省了任务所需要的时间，仿真模拟实验说明算法在处理云计算资源分配方面问题时拥有较好的优越度[8]。

1 调度算法描述

调度算法是云计算资源调度的核心技术，优秀的调度算法可以保证云计算资源调度的高效性和合理性，因此引入传统的蚁群算法，并对其进行优化和改进，实现高效资源调度[9-13]。

蚁群算法(AG)[14-20]是一种模拟蚂蚁觅食行为的模拟优化算法，它是由意大利学者Dorigo M等于1991年首先提出，并首先使用在解决TSP(旅行商问题)上。自然界中的蚂蚁从巢穴出发觅食，通常会在通过的路径上留下大量的信息素来引导后面的蚂蚁，路径上信息素积累的越多，其使之后的蚂蚁选择该路径的概率也就越大，传统的蚁群算法到最后往往会出现几条路径的信息素高于其他路径的情况，如果每只蚂蚁都将任务分配给信息素浓度最高的节点处理，那么就会出现搜索停滞现象。也就是算法收敛速度过快导致的局部最优解，从而无法得到全局最优解。因此需要对传统的蚁群算法进行改进和优化，以发现全局最优解。在传统的蚁群算法运算的前期阶段中各路径的信息素含量差距不明显，则蚂蚁就更倾向于选择路程较短的路径，这就让距离较短的路径更容易被后来的蚂蚁选择,导致盲目而局部的搜索，因此为了避免这种情况的出现，为此，在传统的蚁群算法基础之上加入随机选择机制,扩大全局寻优能力，增加解的多样性,设置由参数q0控制伪随机比率，表示如下

(1)

(2)

(3)

2 云计算任务分配问题

云计算任务分配问题是将n个任务通过采用的调度算法合理地分配到m个可利用的虚拟节点资源上，并使得任务执行时间最短，所消耗成本最低，同时满足用户Qos需求的过程[21-25]。

2.1 云计算任务模型

常见的云计算任务调度算法是将一个任务划分成几个相对独立的子任务，再将每个子任务分配到相应的虚拟资源同时进行计算，最后再将每个计算的结果进行汇总处理，得到最终结果，研究只对上述情况中相对独立的子任务并行计算的情况做出分析,任务T是包含n个元素的任务集，表示为：T={Task1,Task2…Taski},Taski代表用户需要处理的任务。

2.2 云计算资源模型

2.3 Qos模型

在文献[11]中提到，云计算的服务质量(Qos)是衡量用户对云计算满意程度的一种标准。研究将用户的开销需求、任务完成时间需求和任务结果是否有效可用这3个方面的Qos需求纳入考虑范围内，分别建立开支需求适应度因子(payment)、任务完成时间适应度因子(time)和任务结果有效可用性适应度因子(usable)。

2.3.1 用户开支需求适应度因子

在分配云计算资源时，假设调度任务到被分配的虚拟节点上，则虚拟节点集合vm={vm1,vm2…,vmj}，其中任务Taski对应vmj，且调度任务所需要的费用不得超过用户规定的开支，故资源的分配需要满足以下约束条件

(4)

式中：GP表示执行任务所需的费用，LP表示用户设置的开支约束,vmij·p表示任务Taski在被分配的虚拟节点上vmj的执行费用。

(5)

2.3.2 任务完成时间需求适应度因子

在分配云计算资源时，假设调度任务到被分配的虚拟节点上，则虚拟节点集合vm={vm1,vm2，…,vmj}，其中任务Taski对应vmj，且调度任务完成时间不得超过用户设置的完成时间需求，故资源的分配需要满足以下约束条件

(6)

式中：GT表示任务实际完成时间；LT表示用户设置的时间长度约束；vmij·t表示任务Taski在被分配的虚拟节点上vmj的完成时间。

(7)

2.3.3 任务结果有效可用性适应度因子

在分配云计算资源时，假设调度任务到被分配的虚拟节点上，则虚拟节点集合vm={vm1,vm2…,vmj}，其中任务Taski对应虚拟机vmj，且最终虚拟节点得出的任务结果的有效性和可用程度不得低于用户提出的有效可用性需求，故任务集所用的虚拟节点资源的执行任务的有效可用性必须满足

(8)

其中：GU表示任务集所选的虚拟节点资源运算结果的有效可用性；LU表示用户提出的有效可用性约束；vmij·u表示任务Taski被分配的虚拟节点上vmj计算得到结果的有效可用性。在资源分配过程中，用户会优先选择任务结果有效可用性高的虚拟节点进行资源调度，故任务Taski在经虚拟节点资源vmj运行得出结果的有效可用性适应度因子为

(9)

(10)

(11)

2.4 云计算资源调度的综合适应度函数模型

综上对用户的QoS需求的分析，根据所得的用户开支需求适应度因子、任务完成时间需求适应度因子和任务结果有效可用性适应度因子，可以得到执行任务、分配虚拟节点资源的综合适应度函数模型如下

(12)

至此，以资源调度的适应度因子作为引导因子来改进传统的蚁群算法，得到改进的蚁群算法公式如下

(13)

式中：tabuk表示已经通过的路径。

3 算法流程

1)初始化：根据虚拟节点的计算能力、带宽、内存等基础参数对蚁群优化算法的各项参数进行初始化，其中包括信息素的初始化、虚拟节点初始价格的初始化、迭代次数的初始化、信息素浓度的初始化和任务执行时间的初始化。创建禁忌列表tabuk用于记录蚂蚁已经走过的路径。

3)根据改进公式(13)计算每一只蚂蚁选择下一个相邻节点的转移概率，根据计算结果将任务分配到相应的虚拟资源节点上。

4)当任务被分配到虚拟资源节点上以后，更新在本次迭代过程中蚂蚁通过路径上的信息素，并将已通过的路径添加进禁忌表tabuk中。

5)重复执行步骤2)～4)，使整个蚁群任务集都找到最优的路径为止。

7)对所有路径上的信息素进行全局更新。

8)迭代次数累加，判断是否达到最大迭代次数，若未达到，则继续执行步骤2),若已达到最大迭代次数，则停止搜索，得到的结果即是云计算资源分配的最优解。

4 实验测试与结果分析

CloudSim 3.0是墨尔本大学的网络实验室和Gridbus项目推出云计算仿真软件。为了验证本文设计的改进蚁群优化算法在处理云计算资源调度问题时的有效性和可行性，使用CloudSim 3.0平台，在相同的条件和环境下进行实验，并与传统的蚁群算法以及CloudSim 3.0自带的Min-Min调度算法的任务分配结果进行对比。

实验中，对CloudSim 3.0 模拟器进行参数设置，设置20个任务中心，每个任务中心部署10个虚拟节点资源，随机设置虚拟节点的性能，设置虚拟节点能力为[1000,2000]MIP,内存为[512,2048]MB,带宽为[5000,10000]b/s,用户任务数量为200～1000个，在[500,3800]间随机设置任务长度，最大迭代次数为60次。

图1 算法运行的成本比较

从图1中可以看出当任务数量较少时，传统的蚁群算法、Min-Min调度算法和改进的蚁群优化算法在完成云计算资源调度方面所消耗的成本大致差别不大，但随着任务数量的增多，传统的蚁群算法在云计算资源调度方面所消耗的成本快速上升，而改进的蚁群算法在此方面仍维持较低的成本支出且始终低于Min-Min算法的消耗，这说明提出的改进蚁群优化算法有效地降低了成本消耗。

从图2中可以看出，虽然Min-Min调度算法在任务和改进的蚁群优化算法在任务数量较少时完成调度的时间相差不大，且都低于传统的蚁群算法所需要的时间，但在任务数量增加后，改进的蚁群优化算法在消耗时间方面的涨幅相对更小，上升曲线也更平稳，故说明提出的改进蚁群优化算法在任务完成时间方面有较好优势。

图2 算法运行时间的比较

图3 算法得出结果的有效可靠性比较

从图3中可以看出，在任务数量较少时提出的蚁群优化算法得出结果的有效性低于传统的蚁群算法和Min-Min调度算法得出结果的有效性，但随着任务数量的增加，改进的蚁群优化算法得出结果的有效性成正比例上升，并且高于其余2个算法得出结果的有效性，而其他2个算法虽然在任务数量较低时有更高的任务结果有效性，但增长曲线更波折、不稳定，故说明提出的改进的蚁群优化算法在得出的任务结果的有效性方面也具有明显优势。

5 结 语

针对一般云计算资源调度问题没有全面的考虑用户QoS需求的情况，引入引导因子对传统的蚁群算法进行优化和改良，得到一种改进的蚁群优化算法，该算法充分的考虑了任务完成时间、任务所需成本和任务结果的有效性，以此来综合得出用户对服务的满意程度。并对改进算法进行模拟仿真实验，实验表明，该算法在任务完成时间、任务所需成本和任务结果的有效可用性3个方面均具有明显的优势，但在满足基于用户QoS需求这3个方面的同时，要求能高效地进行任务调度方面还略有不足，应该考虑负载均衡的问题。