论文摘要
网格作为典型的分布式应用系统,由大量分布共享的异构资源组成,这些资源协同提供了巨大的计算能力。由于网格计算中资源具有在广域上分布、自主管理、本质上异构、负载动态变化等特性,使得网格环境下的任务调度所面临的问题比传统分布式环境要复杂得多,是一个NP完全问题(除极少数特殊情况外)。调度技术一直为计算机学者们研究的焦点,是网格的核心技术,它可以描述为合理解决计算任务在地理分布的各种资源之间的动态调度。总的来说,一个好的任务调度算法其关键的技术参数是在最短的时间内实现最优分配策略,从而提高系统资源的利用率以及保持系统较好的系统负载均衡。本文通过对智能算法——蚁群与遗传算法的深入研究,将它们引入到网格任务调度中,提出了基于改进型蚁群算法的网格任务调度技术与基于蚁群与遗传混合算法的网格任务调度技术。基于改进型蚁群算法的网格任务调度技术,主要针对现有网格任务调度算法负载均衡、资源利用率、跨度等方面的不足而提出。该算法的关键问题就是如何确定负载,使各个结点的负载基本趋于均衡,以达到网格系统任务调度要求总的执行时间最小以及系统的利用率最高。蚁群算法的正反馈特性容易导致搜索结果过早的陷入局部最优,改进型蚁群算法针对这一现象做出一系列改进:增加信息素权值、增加挥发平衡因子、引入前辈们提出的转移概率准则以及对信息素总量进行限制。蚁群算法基于随机搜索的特性,在算法的初期按启发信息进行求解,收敛速度缓慢。通过对遗传算法的研究,本文针对具有快速响应要求的网格任务调度提出了以仿真时间为优先目标的蚁群与遗传混合算法,该调度算法将蚁群与遗传算法混合应用于网格任务调度中,取两种算法之所长,去其所短,优势互补,从而在时间效率上优于蚁群算法。新算法在满足调度的限定条件之前采用遗传算法,充分利用遗传算法的群体性、快速搜索等优势生成初始解(即产生有关问题的初始信息素分布),随后采用本文提出的基于奖励因子的蚁群算法,在有一定初始信息素分布的情况下,最大限度地利用蚁群算法的正反馈性来快速求解任务的最优解。通过使用基于SimJava的网格资源调度模拟工具包GridSim仿真验证了如上算法,取得了令人满意的效果。