基于蚁群与退火混合优化算法的网格资源调度的研究

摘要

网格是构建在互联网上的一种前沿信息技术。它将地理上分布不同、软硬件异构的各种资源通过高速网络连接成为一个巨大的信息服务平台,实现了广域、动态变化的资源的全面共享。然而网格具有异构性、动态性、资源广泛分布与共享、自治性与多级管理等特点,传统的资源调度技术在网格环境中已经难以适用,因此研究适合网格环境的资源调度策略对网格技术的应用至关重要。
　　本文首先分析了蚁群算法(ACA)和模拟退火算法(SA)的原理。针对蚁群算法应用于资源调度的经济性和安全性不高以及模拟退火算法易遗失当前最优解等缺点,分别对蚁群算法和模拟退火算法进行了改进。改进后的蚁群算法通过局部和全局信息素更新规则,实现对资源信息素的实时调节,引入了价格激励机制,促使了资源拥有者提供的资源价格和用户的预算趋于合理化,并融合面向资源的可信机制,把资源节点的可信度作为系统性能和安全的评估标准,增强了系统的可靠性和有效性,同时设计重调度机制,实现了即使出现个别节点失效的情况也能顺利完成任务,提高了任务执行成功率和系统的容错性。改进后的模拟退火算法通过对状态产生函数、状态接受函数和控制参数更新函数的选取,最大限度地增加了算法解空间的多样性,添加了记忆表和双阈值等功能,保障了算法最后能够返回一个较好的近似最优解。
　　其次,针对网格资源调度系统的特点,提出了基于蚁群与退火混合优化算法(ACA-SA)的网格资源调度策略。该策略采用改进蚁群算法作为网格资源调度的基础性算法,并将改进模拟退火算法与之结合进行调度。它利用改进蚁群算法具有的正反馈性和并行搜索结构等特性进行快速收敛,克服了单一改进模拟退火算法调度时间长的不足,提高了调度的效率;利用改进模拟退火算法的概率突跳性,有效地避免了单一改进蚁群算法陷入局部极小并最终趋于全局最优,能够改善资源调度的最优解质量。
　　最后,利用GridSim仿真工具对本文提出的资源调度算法进行性能测试与验证。实验结果表明,基于蚁群与退火混合优化算法的资源调度策略具有可行性,能够缩短调度的完成时间,改善网格系统的整体性能。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

§1.1 研究的背景和意义

§1.2 国内外研究与发展现状

§1.3 论文的主要工作

§1.4 论文的组织结构

第二章 网格资源调度技术

§2.1 网格

§2.2 网格资源调度

§2.3 本章小结

第三章 蚁群算法和模拟退火算法

§3.1 组合优化问题和元启发式算法概述

§3.2 蚁群算法

§3.3 模拟退火算法

§3.4 本章小结

第四章 基于蚁群与退火混合优化算法的网格资源调度设计

§4.1 使用混合算法进行资源调度的可行性分析

§4.2 网格资源调度策略的总体设计

§4.3 蚁群算法的改进设计

§4.4 模拟退火算法的改进设计

§4.5 蚁群算法与模拟退火算法的衔接设计

§4.6 网格资源调度策略的总流程

§4.7 本章小结

第五章 仿真实验及算法性能分析

§5.1 网格仿真工具GridSim介绍

§5.2 仿真环境的搭建

§5.3 实验的设计与实现

§5.4 实验结果与分析

§5.5 本章小结

第六章 总结与展望

§6.1 工作总结

§6.2 研究展望

参考文献

致谢

作者在攻读硕士期间主要研究成果