基于IM-ACO算法的网格任务调度算法研究与实验

摘要

网格计算是分布式计算的一种，是解决科学计算、工程计算和商业计算等大规模计算的下一代极具潜力的计算平台。网格将在地理位置上分布的异构的各种高性能计算资源整合起来，将高速互联网、计算机、大型数据库、传感器、远程设备等融为一体，为人们提供更多的资源、功能和服务。由于网格所具有的广域性、动态性、异构性的特点，使得如何对任务进行调度以满足用户的需求成为一个极具挑战性的问题。 任务调度技术是网格核心服务之一，它根据任务提交的信息采用适当的策略将不同的任务分配到合适的资源节点上去运行。可将其描述为将m个相互独立的任务分配到n个异构的可用资源上以获取最小的完成时间和最大资源利用率的问题。这是一个NP完全问题。 目前存在的网格任务调度策略，如遗传算法、蚁群算法、模拟退火算法、禁忌算法等，皆优缺点分明，都不能够单独实现对网格任务的最优调度，而且没有将免疫算法和蚁群算法结合在一起来解决网格任务调度问题的策略。 本文通过分析蚁群优化算法和其他一些优化算法的优缺点，应用算法混合的一般原则，深入了解待优化问题本身的特性，提出了结合免疫机制的蚁群优化算法，用于解决网格任务最优调度问题。 具体工作如下： 1)解析网格计算环境，阐述网格定义、特征及体系结构。 2)提出了结合免疫机制的蚁群优化算法。蚁群算法的收敛速度快，但容易陷入局部最优解，并且解构造的计算复杂度大；而免疫算法的操作算子简单，并能有效的维持种群多样性，防止种群退化。本文结合实际需求和优化问题的特性，提出了结合免疫机制的蚁群优化算法，获得了较强的全局和局部寻优能力。 3)在研究了仿真软件Simgrid之后设计了模拟程序对算法进行了性能评估和验证。通过与基于遗传算法的任务调度算法比较分析，验证了本文算法的正确性。

目录

文摘

英文文摘

声明

第1章绪 论

1.1选题背景

1.2国内外发展现状

1.3课题研究目的、意义

1.4课题研究内容及论文组织结构

第2章 网格计算

2.1网格的基本概念

2.1.1网格的目的

2.1.2网格的意义

2.1.3网格计算的特点

2.2网格体系结构

2.2.1体系结构的概念

2.2.2五层沙漏结构

2.2.3开放网格服务体系结构OGSA

2.2.4 Web服务资源框架WSRF

2.3 Globus项目介绍

2.3.1 Globus的起源和发展

2.3.2 Globus体系结构

2.4网格任务调度

2.4.1网格任务调度的模型

2.4.2网格任务调度组织模式

2.4.3网格任务的调度过程

2.4.4网格任务调度面临的问题

第3章 蚁群算法和免疫算法

3.1蚁群算法及其现有改进工作

3.1.1 AS算法描述

3.1.2算法特点

3.2蚁群改进算法及策略分析

3.2.1典型改进算法

3.2.2改进策略分析

3.2.3现有算法存在的问题

3.3免疫算法

3.3.1生物免疫系统概述

3.3.2人工免疫系统

3.3.3免疫与蚁群算法结合的优势

第4章 免疫-蚂蚁算法的网格任务调度

4.1网格任务调度的影响因素

4.1.1任务间约束DAG图

4.1.2任务时间属性

4.1.3数据传输延迟

4.1.4数据分配

4.1.5问题描述

4.2免疫-蚁群算法

4.2.1抗体间差异度量

4.2.2疫苗的提取

4.2.3交叉与变异

4.2.4对疫苗进行接种

4.2.5免疫选择

4.2.6蚁群融入抗体群

4.3网格任务调度算法过程

第5章 基于Simgid和TSP的仿真试验

5.1 SimGrid仿真工具包

5.2实验仿真结果及其评价

5.2.1仿真环境

5.2.2具体的仿真方法

5.3仿真结果及其评价

第6章 总结与展望

参考文献

致 谢

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