【作者】 刘飞；

【导师】 薛胜军；

【作者基本信息】 南京信息工程大学 ， 计算机应用技术， 2014， 硕士

【摘要】 作为当前研究应用最广泛的商业化分布式计算技术,云计算得到各大IT厂商的推广,它通过虚拟化技术将数据中心的物理资源整合成资源池并以服务的方式提供给用户计费使用。随着云计算的不断发展,传统的单目标优化下的任务调度已经不能满足云计算所面对的多样化需求,因此,基于多目标优化的云计算任务调度研究有着重要的意义。本文通过分析云计算任务的特点提出混合云任务模型,并选取多个优化目标对其调度过程进行优化,建立了基于多目标优化的云计算任务调度模型,主要工作如下：(1)通过分析云计算的基本概念、体系结构和技术特点提出了兼有独立任务和工作流任务的混合云任务模型,并针对云计算需求多样化的特点引入了多目标优化的概念。(2)同时选取云计算用户关注的处理任务所需的运行时间和运行费用以及云服务提供商关注的数据中心虚拟机集群上云任务的负载均衡为优化目标,建立基于多目标优化的云任务调度模型来处理混合云任务,在此过程中建立了优化目标函数并设计了描述云任务和虚拟机的映射关系的编码方式。(3)在研究NSGA-Ⅱ (Non-dominated Sorting Genetic Algorithm-II,非支配排序遗传算法-Ⅱ)的基础上,针对云计算任务调度的特点对NSGA-Ⅱ算法采用STOX (Similar Task Order Crossover.相似任务序列交叉)操作来加快其在求解Pareto最优前沿时的收敛速度,采用LBSM (Load Balancing Shift Mutation,负载均衡位移变异)操作来避免算法收敛于局部最优并优化了负载均衡子目标,采用拥挤距离自适应参数使Pareto最优前沿中的个体分布更均匀。(4)在研究NPGA (Niched Pareto Genetic Algorithm,小生境Pareto遗传算法)的基础上,针对云计算任务调度的特点对NPGA算法采用STOX和LBSM操作进行改进,目标效果与(3)中相同。另外通过自适应选取比较集合规模和小生境半径分别提高了算法的收敛速度和Pareto最优前沿中个体分布的均匀性。(5)对开源云计算仿真器CloudSim进行研究,并分别对改进前后的NSGA-Ⅱ和NPGA在基于多目标优化的云计算任务调度问题中的应用进行仿真。仿真结果表明改进后的算法在求解得到的Pareto最优前沿中非重复最优解的个数和Pareto最优前沿中解分布的均匀性上的表现都优于对应的改进前的算法。另外,相比于改进前算法,选用改进后算法的Pareto最优前沿中解个体对应的调度方案时,云任务调度在各个优化子目标上的表现也更优。更多还原

【Abstract】 As the most widely used commercial distributed computing technology nowadays, cloud computing has been supported by many IT companies. The physical resources in the cloud data center are integrated into a resource pool by using virtualization technology and users can pay for the cloud computing service. However, the traditional task scheduling under single-objective optimization can’t meet the diverse needs faced by cloud computing with its continuous development, therefore, the study of cloud computing task scheduling based on multi-objective optimization has the vital significance.In this paper, a hybrid cloud computing task model is proposed by analyzing its feature, and multiple optimization objectives are selected to optimize its scheduling process. By doing these, a cloud computing task scheduling model based on multi-objective optimization is established. The main works in this paper are as follows.(1) The basic concepts, architecture and technical features of cloud computing are introduced, and a hybrid cloud computing task model containing independent tasks and workflow tasks is proposed. Also, some basic concepts of multi-objective optimization are introduced.(2) Three optimization objectives are selected. The time consumption and the financial cost of processing the tasks submitted by cloud computing users are two of them, and the third objective is the load balancing of the cloud computing tasks on the virtual machines in the cloud data center. A cloud computing task scheduling model based on multi-objective optimization is established with the hybrid cloud computing task model and the three optimization objectives. In this process, the objective function is established, and the encoding describing the mapping relationships between cloud tasks and virtual machines is designed.(3) An improved NSGA-Ⅱ (Non-dominated Sorting Genetic Algorithm-Ⅱ) is applied to the cloud computing task scheduling model based on multi-objective optimization. In this process, the STOX (Similar Task Order Crossover) operator is applied to make the evolution more efficient while the LBSM (Load Balancing Shift Mutation) operator is applied to avoid the premature convergence and optimize the objective of load balancing at the same time. In addition, the self-adapting crowding distance operator is presented to improve the diversity of individuals in the Pareto-optimal front.(4) An improved NPGA (Niched Pareto Genetic Algorithm) is applied to the cloud computing task scheduling model based on multi-objective optimization. In this process, the STOX operator and the LBSM operator are also used to improve the algorithm. In addition, the self-adapting size of comparison set operator and the self-adapting niche radius operator make the evolution more efficient and improve the diversity of individuals in the Pareto-optimal front respectively.(5) Study the open source cloud computing simulation tool CloudSim and simulate the improved NSGA-Ⅱ with NSGA-Ⅱ and improved NPGA with NPGA respectively when they are applied to the cloud computing task scheduling model based on multi-objective optimization. The simulation results show that the improved algorithms perform better in the aspects of maintaining the diversity and the distribution of the Pareto-optimal individuals. In addition, the cloud computing task scheduling can get better solution corresponding to the individual in the Pareto-optimal front of the improved algorithms.更多还原