基于改进差分进化的云计算任务调度算法

摘要

近年来，云计算因其计算能力强大、资源管理灵活、价格低廉、部署快捷等优点，在学术界与产业界受到极大推崇。任务调度是云计算的基本研究问题之一，它根据任务的各种需求，通过采用适当策略把不同的任务分配到云中合适的资源节点上执行。在云计算系统中，结合考虑每个计算处理节点的能力，以最合理的方式把用户提交的所有任务分配到数据集群中的计算节点上，这已经被证明是一个非确定多项式(non-deterministic polynomial，NP)问题。现有大部分对于云计算中的任务调度及资源分配调度算法将缩短任务的完成时间作为研究重点，然而它们没有很好的兼顾调度执行时间最小与成本最小，任务完成所需的成本也是个不可忽略的因素。云计算平台中不同的计算资源的使用成本不同，处理能力强的计算资源的使用成本要较高，而处理能力差一些的计算资源的使用成本则较低，云用户在选择云服务时应根据自己的经济预算以及所能等待的时间综合考虑。针对这种现象，本文开展了以下两个方面的工作：
　　（1）针对现有的差分进化算法（DE，Differential Evolution）后期收敛速度慢、参数设置困难、容易限于局部最优等不足，提出了一种改进的差分进化算法(IDE, Improving Differential Evolution)。算法从两个方面进行了改进：观察到差分进化算法中的基本交叉算子是能够生成两个子代个体的，考虑将其丢弃的子个体也加入到产生新个体的锦标赛选择中，用最少的仿真次数保留最多的有效遗传信息；同时，由于评估一次调度方案的时间非常长，要依靠大量的实验来得到控制参数的值非常困难，对算法的缩放因子F，交叉概率CR进行改进，使控制参数可以随着算法的进化自动调整。
　　（2）从云计算用户和云数据中心的角度出发，选取用户提交云任务的运行时间和运行费用为目标，提出了一个基于多目标优化的云计算任务调度模型。由于差分进化算法在调度中是没有约束条件的，而云任务调度受到了cpu，内存，容忍时间等约束。本文在IDE基础上，采取了基于规则的处理机制对约束条件进行了处理，提出了ICDE算法，最后研究开源云计算仿真器CloudSim，将ICDE算法，IDE算法，标准的差分进化算法DE，多目标调度模拟退火算法(Simulated Annealing，SA)，应用到基于多目标优化的云计算任务调度模型中，并使用CloudSim云平台模拟实现。通过对实验结果的对比分析说明，ICDE算法在任务完成时间和任务完成成本上都要优于其它几种算法。

目录

声明

第1章 绪 论

1.1 研究背景及意义

1.2 国内外研究现状及发展趋势

1.3 本文研究内容

1.4 本文组织结构

第2章 相关研究综述

2.1 云计算相关介绍

2.2 云计算的关键技术

2.3 云计算的应用场景

2.4 云计算任务调度

2.5 进化算法相关介绍

2.6 本章小结

第3章 改进的差分进化算法

3.1 标准差分进化算法

3.2 改进的差分进化算法

3.3 仿真实验

3.4本章小结

第4章 基于改进差分进化算法的云任务调度策略

4.1 多目标云任务调度的问题描述及定义

4.2 云任务调度系统模型

4.3经典调度算法

4.4 基于ICDE的任务调度策略

4.5本章小结

第5章 算法实验和结果分析

5.1 云计算仿真器CloudSim简介

5.2 CloudSim的仿真流程

5.3实验环境和仿真数据

5.4 实验结果与分析

5.5 本章小结

结论

参考文献

致谢

附录A 攻读学位期间所发表的学术论文

附录B 攻读学位期间参加的科研项目