网格任务调度优化模型和算法研究

论文摘要

随着科学技术的快速发展,大量科学计算和复杂应用的计算量越来越大。作为一种正在迅速发展的基础设施,网格能够共享大规模分布的计算资源、存储资源、数据资源、软件资源、设备资源等,突破现有的计算限制,实现大规模协同的科学计算及协同问题求解,从而为解决超大规模、超级复杂的计算密集或数据密集的问题提供一种新的计算模式。由于网格资源具有大规模分布性、类型异构多样性、动态变化性等特点,网格的研究具有极大的挑战性,在网格计算的研究中,任务调度的研究是一个热点。本文重点对网格计算过程中的任务调度和负载均衡进行了较深入地研究,并完成了以下工作:①对网格计算的研究背景和网格计算在美国、欧洲、日本及我国的研究情况进行了总结。②阐述了网格计算的定义,分析了网格计算的特点和应用,对网格计算研究进行了分类,研究了五层沙漏结构、开放网格服务体系结构和WEB服务资源框架等三种体系结构。③分析了网格计算中任务调度的基本特征、目标,并对任务调度进行了形式化定义,研究了网格计算中资源节点间实现任务均衡分配的负载均衡策略的三种情况。④研究了能有效实现任务调度和负载均衡的三种智能算法——遗传算法、免疫克隆算法和模拟退火算法,并对蚁群算法等其他影响网格计算的算法进行了简要的介绍。⑤提出了两种新的网格任务调度优化模型和算法:并行遗传免疫克隆算法(PGICA)和并行模拟退火克隆算法(PSACA)。PGICA算法充分考虑了遗传算法和免疫克隆算法的优点,将二者进行了有效整合,建立了算法模型,证明了算法的收敛性。PSACA算法结合了遗传算法、模拟退火算法和免疫克隆算法的优点,并在此基础上建立了算法优化模型,对算法过程进行了形式化描述,⑥通过仿真实验证明了PGICA算法和PSACA算法在实现任务调度和负载均衡上达到良好的效果。

论文目录

• 中文摘要
• 英文摘要
• 1 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 国外的研究现状
• 1.2.2 国内的研究现状
• 1.3 研究方法
• 1.4 论文的组织结构
• 1.5 本章小结
• 2 网格计算概述
• 2.1 网格的内涵
• 2.1.1 网格的定义
• 2.1.2 网格的特点
• 2.1.3 网格的应用
• 2.1.4 网格的研究分类
• 2.2 网格亟待解决的问题
• 2.3 网格计算体系结构
• 2.3.1 五层沙漏结构
• 2.3.2 开放网格服务体系结构（OGSA）
• 2.3.3 Web 服务资源框架（WSRF）
• 2.4 本章小结
• 3 网格计算的任务调度和负载均衡
• 3.1 网格计算中任务调度
• 3.1.1 资源管理和任务调度
• 3.1.2 任务调度的基本特征
• 3.1.3 任务调度问题的定义
• 3.1.4 Globus 网格资源管理分层模式
• 3.2 网格计算中的负载均衡
• 3.2.1 传输链路聚合
• 3.2.2 更高层交换
• 3.2.3 服务器群集解决方案
• 3.2.4 带均衡策略的服务器群集
• 3.3 几种常见的智能优化调度算法
• 3.3.1 遗传算法
• 3.3.2 模拟退火算法
• 3.3.3 免疫克隆算法
• 3.3.4 其他优化算法
• 3.4 本章小结
• 4 基于并行遗传免疫克隆算法的任务调度
• 4.1 问题的定义
• 4.2 PGICA 算法模型
• 4.3 PGICA 算法的收敛性分析
• 4.4 PGICA 算法的算法的结构
• 4.5 仿真实验及结果分析
• 4.6 本章小结
• 5 基于并行模拟退火克隆算法的任务调度
• 5.1 网格资源优化模型
• 5.2 PSACA 算法的结构与描述
• 5.2.1 PSACA 算法的思想
• 5.2.2 抗体编码及初始抗体群
• 5.2.3 亲和度
• 5.2.4 抗体克隆
• 5.2.5 克隆变异算子
• 5.2.6 克隆交叉算子
• 5.2.7 克隆选择算子
• 5.3 算法描述
• 5.4 仿真实验
• 5.4.1 实验环境及参数选取
• 5.4.2 实验结果
• 5.4.3 结果分析
• 5.5 PSACA 算法的主要源代码
• 5.6 本章小结
• 6 结论及展望
• 6.1 全文总结
• 6.2 研究工作展望
• 6.3 本章小结
• 致谢
• 参考文献
• 附录