云工作流系统中基于粒子群算法的任务调度优化研究

发布时间：2018-05-05 04:43

本文选题：云计算 + 工作流系统　；参考：《安徽大学》2017年硕士论文

【摘要】：云计算是一种大型计算资源共享模型。云计算平台在充分利用海量异构分布式资源的同时,可以向用户提供无处不在、方便、按需的网络计算资源服务。云计算的关键特征在于按需服务、超大规模、虚拟化、高可伸缩性和通用性。工作流是一种部分或完全由计算机自动执行的业务流程。工作流管理系统从用户处接收任务且根据用户的需求和任务限制条件为每个任务分配合适的资源。由于云计算的目标是为用户提供执行效率更好且成本更低的资源,并且随着在云环境中大规模电子商务以及科学计算等应用的不断发展,使得对云环境中任务自动分配和执行的QoS(QualityofService)目标的要求不断提升。因此,如何使得云环境中的任务调度和资源分配方案更加合理是一个重要的研究方向。云工作流系统是一种将云计算海量的资源配置与工作流的自主资源分配方法相结合的产物,云工作流管理系统根据工作流任务之间的依赖关系以及任务之间的优先级将云计算中的各种可用资源分配给相应的工作流任务。由于在云环境中资源的使用是有偿的,如果无法以一种合理的方式为这些任务分配合适的资源,那么将会增加云服务提供商的成本,同时也会使云环境中的各类资源无法得到充分利用。因此,如何通过云工作流系统为用户所提交的任务分配合适的资源是一项十分重要的问题。针对这一问题,可以在云工作流系统中通过任务调度算法为不同任务分配合适的资源,早期的云环境由于规模不大,云服务提供商所最为关注的是任务执行的费用问题,因此早期云环境中的任务调度算法优化目标为降低任务执行费用。随着云计算的不断发展,用户对任务执行完成时间的要求越来越高,云服务提供商也同时需要较高的资源利用率,此时调度算法的优化目标又转移至降低任务执行时间。近年来随着云计算领域针对QoS优化目标的研究不断兴起,使得云工作流任务调度算法需要同时针对任务执行的时间与费用目标进行优化。因此,如何将任务执行时间与费用两个目标有效的结合,进而形成合适的QoS优化目标又成为了当下研究的热点。但是随着近几年来云计算行业的蓬勃发展以及巨型云数据中心的不断出现,云服务所带来的巨额能耗成本在总运营成本中所占比重越来越大,如何优化与管理大型云数据中心的能源消耗是一个巨大的挑战,通过云工作流管理系统可以管理和优化云环境中的任务调度,降低服务器运行能耗。然而,现有的云工作流管理系统针对能耗目标优化的研究较少,导致任务调度算法无法充分提高服务器资源利用率,降低任务执行能耗。同时现有基于能耗的任务调度算法仅对任务执行时的QoS需求或能耗目标单独进行优化。导致调度策略在优化了服务器能耗的同时,降低了云工作流服务性能指标。这会造成云工作流无法满足用户在使用时的QoS需求。因此,如何在保证用户QoS需求的同时,尽可能降低任务执行能耗是一个急需解决的问题。目前云工作流系统常用的任务调度优化算法为粒子群算法,然而传统惯性权重的粒子群算法存在易陷入局部最优,迭代收敛速度缓慢的缺点。由此导致任务调度方案的费用与能耗较高。因此,本文首先改进了传统自适应惯性权重,新的自适应惯性权重通过更加精确的描述粒子位置状态以增强在算法迭代过程中对惯性权重的调整精度。接着提出了一种精细搜索的自适应惯性权重粒子群算法(Fine Adaptive Inertia Weight-based Particle Swarm Optimization,FAIWPSO),然后将该算法分别针对云工作流系统任务调度方案的执行费用与能耗两个目标分别进行优化。提出了两种任务调度算法:费用优化的粒子群任务调度算法与能耗感知的粒子群任务调度算法。本文的主要工作和创新点具体如下:1.针对传统自适应惯性权重的粒子群算法易陷入早熟与局部收敛的缺点,对传统自适应惯性权重的成功值计算方法进行改进,提出了一种精细搜索的自适应惯性权重策略的粒子群算法。之后使用该算法对于云工作流任务调度执行费用与能耗目标分别进行了优化研究。2.首先针对任务执行的费用目标进行研究。将精细搜索的自适应惯性权重粒子群算法与云工作流任务层调度的费用模型相结合提出了一种费用优化的自适应惯性权重粒子群任务调度算法,对云工作流任务执行费用进行优化。通过将费用优化的自适应惯性权重粒子群任务调度算法与其他五种不同惯性权重的粒子群算法实验对比,结果表明费用优化的自适应惯性权重粒子群任务调度算法在算法收敛性、适应度和任务执行费用三方面均优于其余算法。3.接着针对任务执行的能耗目标进行优化研究。根据任务执行能耗计算模型设计了适于评价任务调度方案执行能耗的适应度计算方法。之后结合精细搜索的自适应粒子群任务调度算法提出了针对任务执行能耗进行优化的能耗感知自适应粒子群任务调度算法。通过与其他几种惯性权重的粒子群算法进行实验对比。结果表明,能耗感知自适应粒子群任务调度算法不但收敛稳定而且调度方案的执行能耗最低。本文基于当前针对云工作流任务调度的费用与能耗问题进行了深入的研究。提出了一种精细搜索的自适应惯性权重粒子群算法,分别针对当前任务调度优化目标中两个较为重要的目标费用与能耗分别进行研究,提出了针对不同优化目标的两种粒子群任务调度算法。最终通过实验证明了两种算法不仅优化了云工作流环境中的任务执行费用与能耗,而且在算法收敛稳定性上均优于对比算法。在降低了云环境中任务执行的费用与能耗的同时,也利于我国的节能减排事业。因此本文在理论与实践两方面均具有重要意义。
[Abstract]:Cloud computing is a large computing resource sharing model. The cloud computing platform can provide users with ubiquitous, convenient and on-demand network computing resources while making full use of large and heterogeneous distributed resources. The key feature of cloud computing is that the key features of the cloud computing are on demand service, large scale, virtualization, high scalability and generality. A business process that is partially or completely automatically executed by a computer. A workflow management system receives tasks from the user and allocates appropriate resources for each task according to user needs and task constraints. Because the target of cloud computing is to provide users with better efficient and lower resources, and with the cloud environment. With the continuous development of large-scale e-commerce and scientific computing, the requirements of the QoS (QualityofService) target for task allocation and execution in the cloud environment are increasing. Therefore, how to make the task scheduling and resource allocation scheme more rational in the cloud environment is an important research direction. A product of combining a cloud computing resource configuration with an autonomous resource allocation method of workflow. The cloud workflow management system assigns all kinds of available resources in the cloud computing to the corresponding workflow tasks according to the dependencies between the tasks and the priority between tasks. It is paid, if it is not possible to allocate the appropriate resources for these tasks in a reasonable way, it will increase the cost of cloud service providers and also make the various resources in the cloud environment not fully utilized. Therefore, it is a very important way to allocate the appropriate resources for the tasks submitted by the user through the cloud workflow system. In order to solve this problem, the task scheduling algorithm can be used in the cloud workflow system to allocate the appropriate resources for different tasks. In the early cloud environment, because of the small size, the cloud service provider is most concerned about the cost of the task execution, so the task scheduling algorithm in the early cloud environment is optimized to reduce the task. With the continuous development of cloud computing, the demand for the completion time of task execution is getting higher and higher, and the cloud service provider also needs higher resource utilization. At this time, the optimization target of scheduling algorithm is transferred to the reduction of task execution time. In recent years, the research on the target of QoS optimization in the field of cloud computing is becoming more and more popular. It makes the cloud workflow task scheduling algorithm need to optimize the time and cost target of task execution. Therefore, how to combine the two goals of the task execution time and the cost effectively and then form the appropriate QoS optimization target has become the hot spot of the present research. However, with the vigorous development of the cloud computing industry in recent years. With the continuous appearance of the giant cloud data center, the huge energy cost of the cloud service is becoming more and more important in the total operating cost. How to optimize and manage the energy consumption of the large cloud data center is a huge challenge. Through the cloud workflow management system, it can manage and optimize the task scheduling in the cloud environment, and reduce the task scheduling in the cloud environment. However, the existing cloud workflow management system has less research on the optimization of energy consumption targets, which leads to the task scheduling algorithm can not fully improve the utilization of the server resources and reduce the task execution energy consumption. At the same time, the existing task scheduling algorithm based on energy consumption only carries out the QoS requirement or energy consumption target in the execution of the task alone. Optimization. It leads to the scheduling strategy to optimize the energy consumption of the server and reduce the performance indicators of the cloud workflow service. This will cause the cloud workflow not to meet the user's QoS requirements in use. Therefore, how to reduce the task execution energy consumption as much as possible while guaranteeing the user's QoS needs is an urgent problem. The common task scheduling optimization algorithm is particle swarm optimization (PSO), but the traditional particle swarm optimization (PSO) has the disadvantage of easy to fall into local optimal and slow convergence rate. Thus, the cost and energy consumption of the task scheduling scheme are higher. Therefore, this paper first improves the adaptive inertia weight and the new adaptive inertia weight. By describing the position state of the particle more accurately to enhance the precision of the adjustment of the inertia weight during the iterative process of the algorithm, a fine search adaptive inertia weight particle swarm optimization (Fine Adaptive Inertia Weight-based Particle Swarm Optimization, FAIWPSO) is then proposed, and the algorithm is then directed to the cloud workflow, respectively. The execution cost of the system task scheduling scheme and the two goals of energy consumption are optimized respectively. Two task scheduling algorithms are proposed: the particle swarm task scheduling algorithm and the energy aware particle swarm task scheduling algorithm for cost optimization. The main work and innovation points of this paper are as follows: 1. the particle swarm optimization for the traditional adaptive inertia weight is calculated. It is easy to fall into the shortcoming of precocious and local convergence, and improves the success value calculation method of the traditional adaptive inertia weight. A particle swarm optimization algorithm is proposed for the fine search adaptive inertia weight strategy. After that, the algorithm is used to optimize the.2. first for the execution cost and the energy consumption target of the cloud workflow task scheduling. Firstly, the cost target of task execution is studied. An adaptive inertia weight particle swarm optimization algorithm is proposed by combining the adaptive inertia weight particle swarm optimization algorithm with the cost model of cloud workflow task layer scheduling, which optimizes the execution cost of the cloud workflow task. The optimized adaptive inertia weight particle swarm task scheduling algorithm is compared with five other particle swarm optimization experiments with different inertia weights. The results show that the cost optimization of adaptive inertia weight particle swarm optimization algorithm is better than the other algorithm.3. in the algorithm convergence, the fitness and the task execution cost three. The energy consumption target of the line is optimized. According to the task execution energy calculation model, the fitness calculation method is designed to evaluate the energy consumption of the task scheduling scheme. Then the adaptive particle swarm optimization (PSO) task scheduling for the task execution energy consumption is proposed by combining the fine search adaptive particle swarm optimization task scheduling algorithm. The results show that the energy aware adaptive PSO task scheduling algorithm is not only convergent and stable, but also the energy consumption of the scheduling scheme is the lowest. This paper is based on the current research on the cost and energy consumption of cloud workflow task scheduling. A fine search adaptive inertia weight particle swarm optimization (PSO) is developed. According to the study of two important target costs and energy consumption respectively in the current task scheduling optimization target, two particle swarm task scheduling algorithms for different optimization targets are proposed. The final pass through experiment proves that the two algorithms not only optimize the cloud, but also optimize the cloud. The task execution cost and energy consumption in the workflow environment are better than the contrast algorithm in the convergence stability of the algorithm. It is also beneficial to the energy saving and emission reduction of our country while reducing the cost and energy consumption of the task execution in the cloud environment. Therefore, this paper is of great significance in two aspects of theory and practice.

【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.09;TP18

【共引文献】