网格计算中资源调度算法及其模拟技术研究

摘要

网格是构建在互联网之上的一组新兴技术，它的出现掀起了继传统互联网、万维网(WEB)之后的第三次技术浪潮。网格是一个集成的计算与资源环境，可以充分吸纳分布在不同地理位置上的各种资源，并对它们实现全面的资源共享。网格资源调度是网格研究的重要内容之一，它的目标是对用户提交的任务实现最优调度，并设法提高网格系统的总体吞吐量。由于网格系统中资源的异构性、动态性和自治性等特性，使得网格资源调度变得极其复杂。网格资源调度问题被证明是一个 NP完全问题，而遗传算法是解决 NP完全问题的锐利工具。因此，本文对网格计算的相关理论进行了深入的研究学习，对现有网格资源调度算法的基本思想、优缺点进行了充分的分析比较，在这个基础上，选择遗传算法作为改进的基础，提出了基于QoS Guided GA的网格资源调度算法。
　　本文作了大量的理论研究工作，为下一步工作的展开奠定了良好的理论基础。本文全面概述了网格计算的基本概念、特征以及体系结构；详细介绍了网格资源调度的特点、过程、组织模式、调度的执行流程、评价标准以及几种常见的网格资源调度算法；对遗传算法的产生和发展、基本原理、实现过程进行了详细的阐述；最后全面分析比较了当前几种流行的网格模拟技术它们的技术特征、优势和不足以及它们的局限和发展趋势。
　　本文针对简单遗传算法(SGA)在网格调度中的存在的一些不足，并借鉴经济模型中的QoS服务质量机制，提出了一系列的改进措施，所做的工作主要包括以下五个方面:
　　(1)传统的SGA网格调度算法，单纯以提高网格系统的整体吞吐量为调度目标，忽略了网格服务质量的因素，无法保证用户对网格服务质量的要求。本文以同时保证系统调度的吞吐量和网格服务质量为目标，把经济模型中的截止时间(Deadline)和预算(Budget)两个QoS指标引入到遗传算法中，提出了一种基于QoS Guided GA的网格资源调度算法。
　　(2)在以往的网格调度算法研究中，大多假设子任务之间是相互独立的，没有相互依赖关系，以简化研究，没有考虑子任务之间的优先级问题，本文综合考虑任务对资源的要求和用户对任务的时间、代价约束三方面的要求，给出了任务的QoS优先级的计算公式，以此确定不同子任务之间的优先级别即执行次序。
　　(3)对原来的适应度函数进行改进，以此来挑选时间跨度小且QoS服务质量高的个体，改善了原来单一的以最小时间跨度为目标的搜索方式，大大提高了用户对服务质量的满意程度。
　　(4)对SGA中的过于简单的遗传操作进行了改进:选择操作采取“轮盘赌”与最优个体保存策略相结合的方式；交叉操作中通过计算两个体的海明距离来判断是否执行交叉操作；变异操作中引入变异前、后个体的生存竞争机制。通过这些改进措施，能够较好的解决SGA的“早熟”收敛和“欺骗”问题。
　　(5)本文详细设计了基于QoS Guided GA的网格资源调度算法的各个组成部分，选择功能全面应用广泛的GridSim网格模拟器进行模拟实验，通过多次实验与传统SGA网格调度算法以及Min-Min算法进行对比，验证了改进后算法性能的优越性。

目录

封面

声明

目录

中文摘要

英文摘要

第一章 绪论

1.1 课题背景及研究意义

1.2 研究现状

1.3 本文所作的工作及创新点

1.4 论文组织结构

第二章 网格资源调度概述

2.1 网格计算

2.2 网格资源调度概述

第三章 遗传算法简介

3.1 遗传算法的产生和发展

3.2 遗传算法的基本理论

3.3 遗传算法的实现过程

第四章 基于 QoS Guided GA 的网格资源调度算法

4.1 网格 QoS 概述

4.2 问题描述及定义

4.3 基于 QoS Guided GA 的网格资源调度算法的具体实现

第五章 网格模拟技术研究

5.1 网格模拟技术介绍5.1.1 MicroGrid

5.2 网格模拟技术的比较分析

5.3 网格模拟技术的局限性及发展趋势

第六章 基于 GridSim 的仿真实验

6.1 网格仿真模拟器 GridSim

6.2 基于 Qos Guided GA 的网格资源调度算法的设计与实现

6.3 实验内容及结果分析

第七章 总结与展望

参考文献

攻读硕士学位期间发表的学术论文

致谢