云计算环境下的启发式任务调度算法

摘要

由于云计算具有分布式计算存储、服务资源池化、高扩展性、高可用性、成本经济等新颖特点，云计算应用领域的不断扩大，涉及医疗、科研、网络安全、图形图像处理等多个领域。学者们对云计算领域中的技术进行深入研究，包括云数据存储、云数据管理、云计算任务调度、云计算编程模型、云计算安全等，其中任务调度是核心内容并且是研究热点之一。任务调度的研究主要集中在任务调度模型和任务调度算法两个方面。鉴于云计算任务量大、调度目标复杂等特点，国内外许多学者尝试结合启发式算法进行任务调度，并取得了一定效果。本文以云计算任务调度算法为目标，对云计算任务调度的关键问题进行了详细的分析，对基于改进的启发式算法的云计算任务调度进行了深入研究和探索。
　　本文首先介绍了云计算概念、云计算系统和服务、云计算的体系结构和云计算关键技术，再介绍云计算任务调度的概念、特点、目标，分析传统算法的优缺点。提出启发式算法解决该类问题存在的优势。在分析几种启发式算法的基础上，选取较为新颖的布谷鸟搜索算法和混合蛙跳算法进行重点研究。在分析两种算法背景、思想和流程的基础上，发现算法的优点和不足。针对布谷鸟搜索算法在进化后期容易造成早熟，易陷入局部最优解，无法搜索出全局最优解的缺点，提出一种改进的布谷鸟搜索算法，结合柯西变异算子较强的扰动能力改进其后期搜索的问题。在分析基本混合蛙跳算法局部搜索部分存在不足，提出一种改进的混合蛙跳算法，该方法引入双学习能力因子，使用新的局部搜索更新策略，改善了算法的寻优能力。然后基于两种改进的算法，即自适应柯西变异布谷鸟搜索算法和双学习能力混合蛙跳算法进行标准函数测试。最后，结合任务调度问题描述设计编码方式和适应度函数，并提出了自适应布谷鸟搜索算法的任务调度方案和双学习能力混合蛙跳算法的任务调度方案。
　　本文在CloudSim仿真平台上对提出的任务调度方案进行模拟，用于评估算法对云计算任务调度时的性能影响，为算法性能进行了较为客观科学的评估。对比实验结果，本文提出的自适应布谷鸟搜索算法的任务调度方案和双学习能力混合蛙跳算法的任务调度方案在时间跨度和负载均衡方面都能表现良好，满足设计要求。

目录

摘要

第一章 绪论

1．1 研究背景和意义

1．2 云计算任务调度研究现状

1．2．1 Google的MapReduce调度

1．2．2 Amazon的调度策略

1．2．3 IBM调度策略

1．2．4 Windows Azure调度策略

1．2．5 Apache Hadoop调度策略

1．2．6 现有的算法研究趋势

1．3 论文研究的主要内容和创新点

1．4 论文结构及内容安排

第二章 云计算任务调度基础研究

2．1 云计算概述

2．1．1 云计算概念和定义

2．1．2 云计算系统和服务

2．1．3 云计算体系结构

2．1．4 云计算关键技术

2．2 云计算任务调度概述

2．2．1 云计算任务调度概念

2．2．2 云计算任务调度特点

2．2．3 云计算任务调度目标

2．2．4 传统的任务调度算法

2．3 本章小结

第三章 启发式算法

3．1 遗传算法

3．2 粒子群算法

3．3 基本布谷鸟搜索算法

3．3．1 寄生育雏行为和莱维飞行

3．3．2 基本布谷鸟算法思想

3．3．3 基本布谷鸟搜索算法伪代码和流程图

3．3．4 算法的优缺点

3．4 改进的布谷鸟搜索算法

3．4．1 柯西分布和柯西变异算子

3．4．2 自适应柯西变异布谷鸟搜索算法

3．4．3 改进后的算法流程

3．5 基本混合蛙跳算法思想

3．5．1 模因算法和粒子群算法

3．5．2 基本混合蛙跳算法思想

3．5．3 基本混合蛙跳算法伪代码和流程图

3．5．4 算法的优缺点

3．6 改进的混合蛙跳算法思想

3．6．1 双学习能力因子

3．6．2 改进的局部搜索策略

3．6．3 改进后的算法流程

3．7 标准测试函数实验

3．7．1 实验参数设置

3．7．2 实验结果与分析

3．8 本章小结

第四章 云计算环境下的启发式任务调度算法

4．1 云计算任务调度问题描述

4．2 编码方式

4．3 适应度函数设计

4．4 基于ACCS的任务调度步骤

4．5 基于DLSFLA的任务调度步骤

4．6 本章小结

第五章 实验仿真

5．1 CloudSim相关简介

5．1．1 CloudSim的特点

5．1．2 CloudSim体系结构

5．2 仿真环境与实验参数设置

5．2．1 环境配置

5．2．2 仿真步骤

5．3 实验结果及分析

5．3．1 算法性能分析

5．3．2 任务调度结果分析

5．4 本章小结

总结与展望

参考文献

攻读学位期间发表的论文

声明

致谢