基于蚁群算法和DAG工作流的云计算任务调度研究

发布时间：2018-07-29 21:03

【摘要】：云计算作为一种新型商业模式，推动了工业生产等各方面的发展。云计算以一种透明的方式给用户提供各种服务，用户不需要了解云计算平台的技术实现便可以根据自己的需求获取多元化的服务。如何将云计算中的虚拟资源有效的分配给各类用户是一个关键技术问题，一个好的资源分配策略可以在满足用户需求的同时，提高系统的运行效率，因此，研究云计算环境下的任务调度策略具有重要的现实理论意义。本文深入的剖析了云计算的关键技术，，重点的研究了云计算中的任务匹配算法，针对现有调度算法中存在的一些缺陷，本文提出了一种优化的蚁群模型来解决不同任务模型的调度问题。本文首先用蚁群算法来解决独立任务系统的调度问题，然后用蚁群搜寻DAG（有向无环图）任务调度问题的优化解。以下是本文的主要工作：（1）在独立任务调度系统中，任务之间彼此无关联，将任务分配给虚拟机的过程可以看作一个多目标优化问题，蚁群能够基于一种正反馈的机制不断迭代来全局搜索问题的优化解。针对蚁群的这些特性本文提出了一种用于解决任务分配的蚁群模型，通过构建智能的“人工蚁群”，使得蚁群能够快速的收敛，将任务分配到合理的虚拟机。本文在一个高性能的云计算仿真平台CloudSim上进行相关实验，对其中的云计算任务调度模块进行了扩展，并将蚁群算法与FCFS（先来先服务）和贪心调度策略进行比较。（2）在实际的情况下，任务之间会存在一些关联，本文用DAG工作流的模型来描述这个复杂的任务调度系统，并对现有的一些DAG调度算法进行了研究。为了解决此类任务的调度问题，本文先提出了一种基于优先级调度算法，通过对任务赋予优先级的方式来动态分配虚拟机；之后，本文在此算法的基础上提出了一种融合蚁群和优先级调度的综合性算法，该算法结合了蚁群和优先级调度算法的优势，能够在有限时间内搜寻问题的优化解。最后，在CloudSim平台通过仿真实验对本文提出的蚁群算法的有效性进行了分析。
[Abstract]:Cloud computing as a new business model has promoted the development of industrial production and other aspects. Cloud computing provides users with a variety of services in a transparent manner. Users do not need to know the technological implementation of cloud computing platform to obtain a variety of services according to their own needs. How to allocate virtual resources effectively to all kinds of users in cloud computing is a key technical problem. A good resource allocation strategy can improve the efficiency of the system while meeting the needs of users. It is of great theoretical significance to study the task scheduling strategy in cloud computing environment. In this paper, the key technologies of cloud computing are deeply analyzed, and the task matching algorithm in cloud computing is studied, aiming at some defects in the existing scheduling algorithms. In this paper, an optimized ant colony model is proposed to solve the scheduling problem of different task models. In this paper, ant colony algorithm is first used to solve the scheduling problem of independent task system, and then ant colony is used to search the optimal solution of DAG (directed acyclic graph) task scheduling problem. The following is the main work of this paper: (1) in the independent task scheduling system, the tasks are not related to each other, the process of assigning tasks to the virtual machine can be regarded as a multi-objective optimization problem. Ant colonies can iterate through a positive feedback mechanism to optimize the global search problem. According to these characteristics of ant colony, this paper proposes an ant colony model to solve the problem of task allocation. By constructing an intelligent "artificial ant colony", the ant colony can converge quickly and assign tasks to a reasonable virtual machine. In this paper, we do some experiments on a high-performance cloud computing simulation platform CloudSim, and extend the task scheduling module of cloud computing. The ant colony algorithm is compared with FCFS (first come, first served) and greedy scheduling strategy. (2) in the actual situation, there are some relationships between tasks. This paper describes the complex task scheduling system with the model of DAG workflow. Some existing DAG scheduling algorithms are studied. In order to solve the scheduling problem of this kind of tasks, a priority-based scheduling algorithm is proposed in this paper, which allocates the virtual machine dynamically by assigning priority to the task. Based on this algorithm, a comprehensive algorithm combining ant colony and priority scheduling is proposed in this paper. This algorithm combines the advantages of ant colony and priority scheduling algorithm, and can search the optimal solution of the problem in limited time. Finally, the effectiveness of the proposed ant colony algorithm is analyzed by simulation experiments on CloudSim platform.
【学位授予单位】：湖北工业大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.01

【参考文献】