QoS优化的网格工作流调度算法研究

摘要

网格工作流是将工作流管理和网格计算相融合，为下一代分布式协作的工作流系统设计提供了一种非常有前景的解决方案，它可以方便地构建、执行调度、管理和监控网格应用，使得网格应用能够自动实施并且效率较高。网格工作流调度是网格工作流管理中的一个关键问题，适当的调度对系统的性能可产生重要的影响，它直接影响网格工作流的执行成功与否和效率的高低。通常，网格工作流调度是一个NP完全问题。因此，研究开发性能优良的网格工作流调度算法有重要的理论价值。
　　 本文分析和讨论了一些典型网格工作流调度算法、网格工作流管理系统中的调度问题，阐述了网格工作流调度问题中涉及的关键技术，指出了现有算法中存在的一些不足，并展望了该领域的进一步研究方向；给出了一种可扩展的网格服务QoS参数构造模型，定义了网格服务多维QoS参数的效用更新函数，提出了一种网格工作流QoS的估算算法。
　　 针对现有的网格工作流调度算法存在一个或多个以下缺陷：大多只考虑DAG结构的网格工作流、涉及QoS参数较少、将多维QoS参数聚合成一个单目标函数进行优化调度的现状，应用NSGA-Ⅱ和MOPSO_CD算法，本文设计了两种QoS约束的多目标优化的网格工作流调度算法GWNSGA2和GWMOPSO。这两种调度算法基于表达结构丰富的AGWL网格工作流模型，能表达更复杂的网格工作流应用，考虑了响应时间、服务费用、可靠性、可利用性、声誉5维QoS参数，将这5维QoS参数分别设置为5个目标函数，同时也设置5个约束条件进行多目标优化。通过一个典型网格工作流实例进行实验比对，实验结果和理论分析均表明了两算法的可行性和有效性。

目录

文摘

英文文摘

声明

第一章绪论

1.1研究背景

1.2网格工作流调度算法研究现状

1.2.1典型网格工作流调度算法及分析

1.2.2典型网格工作流管理系统调度介绍

1.3存在的问题

1.4研究意义和内容

1.4.1研究意义

1.4.2研究内容

1.5组织结构

第二章网格工作流调度关键技术

2.1网格工作流设计

2.1.1工作流结构

2.1.2工作流规范/模型

2.1.3工作流构建系统

2.2调度策略

2.3性能评估

2.4本章小结

第三章基于AGWL网格工作流模型的多维QOS估算

3.1引言

3.2网格服务QoS

3.2.1网格服务QoS参数构造模型

3.2.2网格服务QoS参数效用更新函数

3.3基于AGWL网格工作流QoS的估算

3.3.1网格工作流中活动的QoS计算方法

3.3.2网格工作流各维QoS参数的综合估算算法

3.4本章小结

第四章QoS约束的多目标优化的网格工作流调度

4.1引言

4.2网格工作流调度模型和思想

4.3基于NGA-II的网格工作流调度算法GWNSGA2

4.3.1快速非支配排序

4.3.2拥挤距离计算

4.3.3约束处理机制

4.3.4 GWNSGA2调度算法描述

4.3.5 GWNSGA2调度算法时问复杂性分析

4.4基于MOPSO_CDP的网格工作流调度算法GWMOPSO

4.4.1编码策略

4.4.2粒子状态更新机制

4.4.3变异操作

4.4.4 GWMOPSO调度算法描述

4.4.5 GWMOPSO算法时间复杂性分析

4.5实验设计

4.5.1实验环境与实例设置

4.5.2算法参数的设置

4.5.3目标函数及约束函数的确定

4.6实验结果及分析

4.6.1可行性实验

4.6.2有效性实验

4.6本章小结

第五章总结与展望

5.1总结

5.2展望

参考文献

致谢

攻读硕士学位期间发表的学术论文目录、参加的科研项目