基于多QoS约束的网格计算任务调度算法研究

论文摘要

网格计算是高性能计算的一种方式,是近年来兴起的热门信息技术之一,它结合了传统的分布式计算,高性能计算等多种计算方式于一体。网格计算将网络上空余的多台计算机转化为自己的工作站,并克服了异构环境下协调管理难以实现的问题,能有效地协同多个QoS约束指标,并将计算任务分散到各个工作站并发执行完成计算任务。网格计算有效地解决了在较短时间内计算运算量庞大的计算任务,如天气预报、地震预测、导弹运行轨迹、卫星发射等大规模计算任务。在网格计算的众多研究热点中,任务调度算法显得格外的重要。网格计算环境从本质上讲是构建在多个工作站上的虚拟计算网络,不同的工作站具备自己各方面的特性,如不同的操作系统,不同的运算处理能力,不同的网络环境等。在这样的异构环境中设计出一套适合的任务调度算法不是一件容易的事情,因此良好的任务调度算法设计将在很大程度上决定了网格计算任务的优良表现。研究表明网格计算任务调度算法属于NP-Hard问题,针对此类问题难以得到最优解,甚至根本就不存在最优解的特点。本文研究了在网格计算任务调度中如何寻找任务调度的满意解。本文综述了网格计算任务调度算法和满意优化的发展现状,深入地研究了多QoS约束满意优化问题,提出一种针对网格计算任务调度算法的多QoS约束满意优化模型。将该模型作为优化方案的评价体系,分别采用Min-Min算法,Max-Min算法和遗传算法作为寻优方法来找寻潜在的优化方案,将这二者统一在一起形成了完整的多QoS约束满意优化求解模型。并将此模型成功运用在多QoS指标约束下的网格计算任务调度算法中。通过仿真实验分析了带多QoS约束的启发式任务调度算法和不带多QoS约束的启发式任务调度算法,同时也针对不同初始化种群的遗传算法作出分析。在众多QoS约束指标中,本文选取了运行时问、优先级、信任度作为主要约束指标进行网格计算任务调度算法的多QoS约束满意优化。对每一维的QoS约束指标通过研究给出满意度函数,并最终将各满意度函数相结合得到网格计算任务调度算法模型,通过该模型得到任务的总体满意度。结合任务发起者预先指定的满意度要求,确定网格计算任务的调度方案。仿真结果表明,本文提出的网格计算任务调度算法在满足用户对满意度的需求的情况下,较好地协同了各个QoS约束指标,充分发挥了遗传算法在解决多目标组合优化算法的优越性,取得了较为理想的效果。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.1.1 网格计算
• 1.1.2 网格计算中的任务调度算法
• 1.2 国内外研究现状
• 1.2.1 网格计算任务调度算法研究现状
• 1.2.2 满意优化理论研究现状
• 1.2.3 现有研究工作存在的问题
• 1.3 本文主要研究内容
• 第2章 问题定义与满意优化方法
• 2.1 问题的定义
• 2.2 QoS约束指标
• 2.2.1 运行时间
• 2.2.2 任务优先级
• 2.2.3 任务对资源的信任度
• 2.3 满意优化方法
• 2.3.1 满意优化的基本概念
• 2.3.2 满意度的定义
• 2.3.3 满意度函数
• 2.4 多目标优化问题
• 2.5 综合满意度函数的定义
• 2.6 本章小结
• 第3章 多QoS约束满意优化模型的建立
• 3.1 引入满意优化的必要性
• 3.2 多QoS约束满意优化模型
• 3.3 多QoS约束满意度函数定义
• 3.3.1 运行时间满意度函数定义
• 3.3.2 优先级满意度函数定义
• 3.3.3 信任度满意度函数定义
• 3.4 综合满意度函数的建立
• 3.5 本章小结
• 第4章 多QoS约束启发式任务调度算法
• 4.1 算法概述
• 4.2 MQoS-Min-Min算法
• 4.3 MQoS-Max-Min算法
• 4.4 算法仿真及仿真结果分析
• 4.4.1 仿真环境
• 4.4.2 Simgrid简介
• 4.4.3 仿真结果
• 4.5 本章小结
• 第5章 多QoS约束满意优化任务调度算法
• 5.1 遗传算法介绍
• 5.1.1 遗传算法的特点
• 5.1.2 遗传算法与传统方法比较
• 5.2 多目标组合优化算法
• 5.2.1 多目标优化中的遗传算法
• 5.2.2 NSGA-Ⅱ算法
• 5.3 MQoS-GA算法
• 5.3.1 MQoS-GA算法简介
• 5.3.2 染色体编码
• 5.3.3 初始化种群
• 5.3.4 选择算子
• 5.3.5 交叉算子
• 5.3.6 变异算子
• 5.3.7 MQoS-GA算法总体流程
• 5.4 算法仿真及仿真结果分析
• 5.4.1 仿真环境
• 5.4.2 仿真结果
• 5.5 本章小结
• 结论和展望
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文