基于改进蚁群算法的QoS 约束云任务调度

丁 智

(扬州职业大学，江苏 扬州 225009)

云环境下任务调度具有不同的目标需求［1］，大多数调度算法集中在工作流调度和独立任务调度，而以工作流任务和独立任务混合的形式提交任务，称之为部分相关任务。调度策略主要分为以性能、QoS 和效益为中心。云环境下任务调度是一大研究热点，有人提出一种概率相关的优先级算法，执行独立任务使用较少的计算资源［2］。也有人提出两种用于私有云的任务调度算法，实现较少的完成时间［3］。还有一些启发式算法也被用于基于QoS 的任务调度［4］。有文献提出一种云环境下多QoS 约束的服务工作流调度方法［5］。此外，还有人提出了基于负载均衡的蚁群优化算法用于云应用调度［6］。然而，大多数研究没有考虑QoS 约束的任务期限。为了有效地进行部分相关任务调度，本文提出了一种满足服务质量(QoS)约束的调度模型，并将改进的蚁群优化算法(ACO +)用于云环境下部分相关任务调度。

1 云任务调度模型

由于云任务调度研究主要集中在独立任务调度和工作流任务调度，缺乏对部分相关任务调度的研究。因此，在研究部分相关任务调度模型的基础上，提出满足QoS 约束的部分相关任务调度模型。部分相关任务模型通常被视为一个有向无环图(DAG)，其中V={T1，T2，…，Tn}代表任务集合，E 代表任务之间的依赖关系，即若＜Tj，Tk＞∈E(j，k=1，2，…，P)，则Tj→Tk，Tj是Tk的先驱节点。图1 是一个简单的工作流实例。

图1 工作流

部分相关任务在一组计算资源VM ={VM1，VM2，…，VMnv}上执行，ExeTimei为执行时间，Lengthi为任务i 的长度，Mipsj为虚拟机j 的单字长定点指令平均执行速度。TranTime 为通信时间，Comij为标志位，maxTransfRate 为最大传输速率，Oputj为输出信息量。

为了满足服务质量约束，FinishTimei需满足式(4)，FinishTimei为任务Ti的完成时间，混合任务集中的每个任务Ti都必须满足QoS 约束的截止时间，记为QoSi。

2 改进ACO 的任务调度算法

蚁群算法是受自然界真实蚁群的集体觅食行为启发用于解决各种组合优化问题的随机搜索方法。蚁群算法基于stigmergy 思想［7］，成员与群体之间通过环境的相互作用间接地沟通。

本文采用蚁群算法的思想将部分相关任务作为蚁群分配任务。为了得到更好的部分相关任务完成时间，把部分相关任务划分成多个子群。AveMips 是对所有虚拟机的MIPSS 取平均值［8］。minTime 是工作流任务根节点的最小执行时间，maxTime 是工作流任务输出节点的最大执行时间。

本文采用改进的蚁群算法解决云环境下的部分相关任务调度问题。算法中每只蚂蚁代表可分配的虚拟机。启发因子ηm，i，j表示任务Ti被分配给虚拟机VMj的期望程度，用式(7)表示，其中NV 代表虚拟机数量。Pm，i，j代表任务Ti被分配给虚拟机VMj处理的概率。

在不同的虚拟机分配策略下，任务Ti被分配给虚拟机VMj执行同样会增加该任务被分配给该虚拟机信息素，若仍然用τm，i，j来表示改进蚁群算法中的信息素，则信息素的更新策略为:(1)当子群中所有任务都在规定时间内完成，则信息素根据式(9)进行更新［9］;(2)当子群中的任务没有在规定时间内完成，则信息素根据式(10)进行更新;(3)当所有的任务都在规定时间内完成，信息素根据式(11)进行更新。其中ρ(0 ＜ρ ＜1)是信息素的衰变参数，Δτm，i，j是选择信息素的增量，见式(12)。

当子群中所有的任务都在规定时间内完成，则虚拟机处于空闲状态，此时需要增加信息素增量Δτm，i，j来吸引其他任务在该虚拟机上执行;而子群中的任务没有在规定时间完成，则虚拟机处于忙的状态，此时需要通过减少信息素来使其他任务选择其他虚拟机执行。

3 实验与分析

为了评估改进蚁群算法在云环境下任务调度的性能，借助云仿真器CloudSim［10］中已有的算法对满足QoS 约束的部分相关任务进行调度，并比较分析。已知云仿真器中已有的算法已经将任务流按特定顺序排序，并对分配到相同虚拟机上的任务优先执行QoS 约束较弱的任务。

3.1 CloudSim 仿真流程

图2 描述了CloudSim 的仿真流程，包括创建datacenter 资源，datacenter 向CIS 进行注册，当有请求时，CIS 根据请求从列表中选择合适的云服务提供商提返回用户，然后由DatacenterBroker 负责信息交互的过程。

图2 CloudSim 仿真流程

将改进的蚁群算法和改进的粒子群算法在CloudSim 仿真器上进行试验，并应用于求解PDTs任务调度模型。本实验采用计算机操作系统为Windows 7、CPU 2.66GHz、内存2G，硬盘250GB。虚拟机所需设置的参数包括虚拟机ID、MIPS、存储空间、带宽、开销等，微软Windows Azure 平台提供了5 种规格的虚拟机，选取前3 种，见表1。

表1 虚拟机参数表

3.2 实验数据

在云仿真器中，改进的蚁群算法通过修改Datacenter Broker 类、Cloudlet 类以及Datacenter类来实现，表2 描述了PDTs 任务的参数设置。

表2 中Cloudlet0 -Cloudlet14 分别对应任务T1到T15，并给出了满足QoS 限制的独立任务的截止时间和工作流任务集合的截止时间，则所有任务的截止时间集合Set1 ={510，78，420，1250，1250，1250，1250，1250，1250，1250，1250，1350，190，1350，1350}为QoS1。并对改进的蚁群算法的相关参数设置如下:α=0.6，β=0.6，ρ=0.7。

表2 PDTs 任务参数表

3.3 实验结果分析

统计不同方法任务分配到虚拟机上执行的完成时间，并对云仿真器中已有的分配算法和蚁群算法、满足QoS 约束的任务相比较，任务完成时间见图3。

图3 各算法的任务完成时间

从图3 中可以看出，蚁群算法大部分任务都无法满足QoS 约束;仿真器中已有的算法对任务进行调度时，任务号1 和任务号12 也不能很好地满足QoS 约束。

而采用改进的蚁群算法对部分相关任务调度模型进行调度时，将得到的完成时间与QoS 约束相比较，混合任务流中的所有任务都能满足QoS约束，见图4。从图3 和图4 可知，本文提出的改进蚁群算法与仿真器中已有的算法以及原有的蚁群算法相比能有效地满足QoS 约束。

图4 ACO+算法任务完成时间

为了测试数据的有效性，本文在QoS 约束集Set1 的基础上，进行另一组QoS 约束实验，QoS 约束条件的截止时间集Set2 = {1350，1350，68，1250，1250，1250，1250，1250，1250，1250，1250，1350，320，650，850}，即QoS2，完成时间见图5。

图5 ACO+算法任务完成时间

从图4 和图5 可以看出改进的蚁群算法能够很好地解决云环境下混合任务模型部分相关任务的调度问题，并保证任务的QoS 约束。

4 结论

根据改进的蚁群算法将部分相关任务分配给虚拟机，并根据不同的参数测试改进蚁群算法性能。实验结果表明改进的蚁群算法具有较高的收敛性和寻优能力，适用于云环境下任务调度。本文对混合任务模型分析时只设置了一个输入和一个输出，任务调度的输入输出过程相对简单，在处理独立任务和工作流任务的过程中，考虑了每个独立任务的截止时间，没考虑整个工作流中间过程的截止时间。

［1］ ZHANG Z，ZHANG X. A load balancing mechanism based on ant colony and complex network theory in open cloud computing federation［C］//Proceedings of the 2nd International Conference on Industrial Mechatronics and Automation. Piscataway:IEEE，2010.

［2］ ZHU L，LI Q，HE L. Study on cloud computing resource scheduling strategy based on the ant colony optimization algorithm［J］. IJCSI International Journal of Computer Science Issues，2012，9(5):54 -58.

［3］ NISHANT K，SHARMA P，KRISHNA V，et al. Load balancing of nodes in cloud using ant colony optimization［C］//Computer Modelling and Simulation，2012 UKSim 14th International Conference on. IEEE，2012.

［4］ YAN HUA Z，LEI F，ZHI Y. Optimization of cloud database route scheduling based on combination of genetic algorithm and ant colony algorithm［J］. Procedia Engineering，2011(15):3341 -3345.

［5］ MISHRA R，JAISWAL A. Ant colony optimization:A solution of load balancing in cloud［J］. International Journal of Web ＆ Semantic Technology，2012，3(2):33 -50.

［6］ LIU X，CHEN J，WU Z，et al. Handling recoverable temporal violations in scientific workflow systems:a workflow rescheduling based strategy［C］//Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster，Cloud and Grid Computing. IEEE Computer Society，2010.

［7］ LIU H，XU D，Miao H K. Ant colony optimization based service flow scheduling with various QoS requirements in cloud computing［C］//Software and Network Engineering，2011 First ACIS International Symposium on. IEEE，2011.

［8］ CHIMAKURTHI L. Power efficient resource allocation for clouds using ant colony framework［J/OL］. arXiv preprint arXiv:1102.2608，2011.

［9］ ENDO P T，DE ALMEIDA PALHARES A V，PEREIRA N N，et al. Resource allocation for distributed cloud:concepts and research challenges［J］. IEEE，2011，25(4):42 -46.

［10］CALHEIROS R N，RANJAN R，BELOGLAZOV A，et al. CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］. Software:Practice and Experience，2011，41(1):23 -50.