基于萤火虫的优化遗传算法的云计算资源调度策略研究毕业论文

 2020-04-04 10:04

摘 要

云计算是传统计算机技术与网络技术相结合的产物,如分布式计算、网格计算和并行计算等,是一种基于互联网计算服务的使用和交付新模式。基于虚拟机化、海量数据管理等关键性技术,用户只需通过网络接口动态申请获取计算资源。随着用户需求多样化、动态化、高效化和云数据中心规模的不断扩大化、分布式服务器计算处理能力差异化,分布式资源调度问题和资源利用率问题变成了主要的优化目标,为此本文建立基于萤火虫-遗传算法的云计算资源调度模型。

  1. 在云计算系统环境下,结合计算任务-虚拟机资源节点的一级调度模型,对个体编码、适应度函数、选择复制和交叉变异过程进行重新设计,建立基于遗传算法的云计算资源调度模型。
  2. 将萤火虫与计算资源相对应,重新设定萤火虫决策域更新方式、选择吸引概率公式和位置移动策略,建立基于萤火虫算法的云计算资源调度模型。为了解决遗传算法的早熟问题,使调度方案全局最优,综合考虑两种算法优缺点,将两种资源调度模型整合成建立基于萤火虫-遗传算法的资源调度模型。
  3. 利用CloudSim云计算仿真平台进行实验,并分析结果。结果表明本文建立的资源调度模型的任务完成时间小于采用单一遗传算法的资源调度模型,虚拟机负载也更均衡,同时也比其他优化的遗传算法任务完成时间短,资源调度方案的整体优化效果明显。

关键词:云计算;资源调度;负载均衡;遗传算法;萤火虫算法

Abstract

Cloud computing is a combination of traditional computer technologies and network technologies, such as distributed computing, grid computing, and parallel computing. It is a new model for the use and delivery of Internet-based computing services. Based on key technologies such as virtualized machines and massive data management, users only need to dynamically obtain computing resources through network interfaces. With the diversification, dynamism, and efficiency of user requirements, the continuous expansion of the scale of cloud data centers, and the differentiation of distributed server computing and processing capabilities, the issue of distributed resource scheduling and resource utilization becomes a major optimization goal. This paper establishes a cloud computing resource scheduling model based on firefly-genetic algorithm.

  1. Under the cloud computing system environment, combined with the first-level scheduling model of computing task-virtual machine resource node, the individual coding, fitness function, selective replication and crossover mutation process are redesigned, and a cloud computing resource scheduling model based on genetic algorithm is established.
  2. Corresponding to the fireflies and computing resources, the fireflies decision-making domain update method, the selection probability formula and the location movement strategy are reset, and a cloud computing resource scheduling model based on the firefly algorithm is established. In order to solve the premature problem of genetic algorithm and make the scheduling scheme globally optimal, considering the advantages and disadvantages of the two algorithms, the two resource scheduling models are integrated into a resource scheduling model based on firefly-genetic algorithm.
  3. Use the CloudSim cloud computing simulation platform to conduct experiments and analyze the results. The results show that the task completion time of the resource scheduling model established in this paper is less than the resource scheduling model using a single genetic algorithm. The virtual machine load is also more balanced. At the same time, the task completion time is shorter than other optimized genetic algorithms, and the overall optimization effect of the resource scheduling program is obvious.

Key Words: Cloud Computing;Resource Scheduling;Load Balancing;Genetic Algorithm;Glowworm Swarm Optimization

摘 要 I

Abstract II

第1章 绪论 1

1.1 研究背景及意义 1

1.2 研究现状 2

1.3 本文研究内容 4

1.4 本文组织结构 4

1.5 本章小结 5

第2章 云计算及资源调度 6

2.1 云计算体系结构 6

2.2 云计算关键技术 7

2.3 资源调度描述 8

2.3.1 资源调度架构 8

2.3.2 资源调度模型 8

2.4 负载均衡概述 10

2.5 本章小结 10

第3章 基于遗传算法的云计算资源调度策略研究 11

3.1 遗传算法原理 11

3.2 基于遗传算法的云资源调度方法 11

3.2.1 个体编码和种群初始化 11

3.2.2 适应度函数设计 12

3.2.3 遗传算子设计 14

3.3 云计算环境下基于遗传算法的云资源调度算法设计 16

3.4 本章小结 17

第4章 基于萤火虫-遗传算法的云计算资源调度策略研究 18

4.1 基于萤火虫算法的云计算资源调度策略研究 18

4.1.1 萤火虫算法原理 18

4.1.2 基于萤火虫算法的云资源调度方法 18

4.2 基于萤火虫-遗传算法的云计算资源调度算法设计 21

4.2.1 算法思想 21

4.2.2 算法设计 21

4.2.3 算法时间复杂度 23

4.3 本章小结 23

第5章 仿真实验及结果分析 24

5.1 CloudSim概述 24

5.2 实验结果及分析 25

5.3 本章小结 30

第6章 总结与展望 31

参考文献 32

致 谢 33

绪论

1.1 研究背景及意义

随着海量数据的不断产生,单片计算机的计算能力较低,无法按时、高效完成用户提交的计算任务,由此研发了分布式计算系统[6]。分布式计算研究的是将庞大的计算任务拆分成多个便于传输和高效计算的任务块,并依据一定的分配策略将之分配给多个计算机处理,同理最后也要依据一定策略将多个计算结果综合整理得到与未拆分计算相同的最终计算结果,从而提高数据处理能力和服务质量。它具有灵活的体系结构、可靠可用性均较好。随着数据级别从GB、TB、PB、EB的逐渐增大,一种以分布式计算、网格计算、并行计算为基础的商业化计算概念诞生,即云计算。它为计算机或其他设备提供共享处理资源和数据、是一种按需访问的可配置的计算资源、是一种数据密集型的超级计算方式和服务模式,实现了无处不在的、方便的、按需的网络访问、共享可配置的计算资源池(如网络、服务器、存储、应用和服务),可快速配置和发布,以最少的管理工作获得与服务供应商的互动[3],研发并运用了多种新型计算机技术,其中虚拟化、海量数据分布式存储、海量数据管理和负载均衡资源管理等技术最为关键。

虚拟机技术在云计算系统的大量使用使网络的扩展性大大增强,从而根据用户的动态需求随时随地访问云计算资源,提升了云计算服务商的服务质量、服务能力和服务效率,鉴于它的低成本、虚拟化技术支持、多样化服务等优势,已经得到大规模的飞速发展并被广泛地应用[2]

计算数据中心的计算机集群存储着云计算的软硬件资源,并具有完善的应用服务及专业化的管理[2]。同时在云计算系统中,云虚拟机处理性能存在有较大差异,因此执行任务的规模和性质也存在很大差异 。计算资源的限制,云计算任务的数量和要求急剧增加,再加上没有合理的调度策略,使一些云服务器上负载的任务过多,而导致任务无法在用户规定时间内完成,随着恶性循环而产生负载不均衡。面对数据中心不断增大的规模和动态变化的需求,如何对其中的虚拟资源进行动态的管理并及时有效地分配给需要的用户是一个必须解决的问题。

资源调度是一个目标组合规划问题,不合理的资源调度制约着云计算的发展。由于资源调度问题而引起的: 1) 并发任务较多时,由于资源之间的竞争而引起的提交的任务不能及时完成,等待时间长,用户体验差;2) 数据中心大量的资源浪费引发数据中心能耗大大增加,不节能环保;3) 创造的经济收益由于系统的性能下降而减少[3]。目前主要从负载均衡角度通过对启发式算法进行改进,得到满足要求的资源调度方案。

作为云计算技术中的重要问题,资源调度是在整个云计算系统中所有节点间分配任务负载的一种策略机制,避免了某些节点过负载或又亏负载,某些节点完全闲置或处于资源利用率不高的情况,有助于实现高的用户满意度,提高云计算系统的整体性能和资源利用率,同时确保每个计算资源能被有效公平的分配。

1.2 研究现状

云计算的应用范围广阔、应用技术比较前沿,也就意味着云计算关键技术的突破如:虚拟机技术、海量数据分布存储与分布处理技术、分布式服务器资源调度技术,都直接制约着云计算的发展速度。动态资源调配包括异构集群资源统一化管理模块与调配和资源合理调度策略,当某一个虚拟机资源的内存溢出、带宽受限制或网络资源无法满足要求时,资源调度模块能依据合理高效的调度策略临时借用同节点或其他节点下的虚拟机计算资源。目前学术领域以降低数据中心能耗为目标、以提高云计算系统虚拟机计算的高效性和降低虚拟机资源节点的浪费的资源调度策略颇多。

云计算环境下实际应用的是常见负载调度算法有轮询算法、随机方式、哈希方式、最快响应和最小连接方式。这些算法相对比较简单、资源调度优化的方向也比较单一,各自利弊点比较明显,导致虚拟机的负载均衡效果达不到、资源调度策略不完善。除此之外还有一些研究性的负载均衡算法,如下:

文献[1]以低能耗为目标,强化该调度过程中的各个功能,在原始功能模块上进行改进得来的能耗测量监控平台、虚拟机管理器、能耗调度器等。研究对能耗测量监控平台中的测量方式以及能耗的计算模型,并再分别对它们的实际功能进行解释,从而研究出了基于简单化与精确化准则的测量方式与计算模型;对于闲置的物理机、虚拟机,管理器研究关闭开启节能技术来关闭暂时闲置的物理机、虚拟机,以降低云计算数据中心的能耗。也即提出了一种基于对超时时间计算方式优化了的满足低能耗要求的关闭时间判断方法。能量调度器、测量监控平台和虚拟机管理器实时通信,其主要基于本文所研究的遗传算法所获得的最佳资源调度方案。

文献[2]提出了一种主要从低能耗和高资源利用率两个目标进行改进的算法。首先,对个体采用树型编码方式,并在种群初始化中设定负载阈值及相关参数初始化,采用本文所研究的遗传算法进行资源调度与分配,以提高资源的利用率; 此外本文还依据虚拟机负载均衡思路重新设计了适应度函数,采用了全新的衡量标准并建立出与之相对应的衡量公式;为了保证整体算法的稳定性和执行高效性,对每个遗传算子进行针对性优化,达到遗传终止条件后产生能耗最低的资源调度方案。

文献[4]提出了一种基于模拟退火思想的改进遗传算法。在迭代进化过程中,改进后的算法依据基于任务平均完成时间和负载均衡的双适应度函数来判断淘汰适应度低的和保留优秀的个体。当基因组发生突变时,也对自适应交叉变异概率函数进行了重新设计。同时由于遗传算法早熟的特性又设计了概率接受函数,从而在退火过程中接受劣质解。依据虚拟机上分配计算任务数量标准差来实现多节点的负载均衡。多重函数的重新设计目的是提高个体的多样性,扩大搜索种群范围,尽最大可能跳出局部最优而达到全局最优。

文献[6]提出了一种用于虚拟资源调度的智能优化策略。结合虚拟机资源特性,优化种群内染色体复制选择和交叉变异方式,设计虚拟机负载函数和云任务最优跨度函数作为双适应度函数,实现负载指标如CPU、虚拟机网络带宽及内存利用率和最有跨度指标如计算任务等待、传输通信及完成执行时间总和的多目标优化,整体提高资源调度效率。

文献[7]在考虑传统遗传算法存在收敛、易早熟等缺点,充分考虑了计算机群的动态异构性和海量数据处理特质,提出了一种基于染色体编码方式和适应度函数的改进遗传算法(IGA),并在云仿真器CloudSim 上对所研究算法仿真实验。结果表明该算法在性能和服务质量QoS方面都优于传统遗传算法,能更好地适用于大规模任务下的云计算环境资源调度。

文献[11]认为负载均衡是云计算的主要挑战之一,它将动态工作负载分布到多个节点上,以确保没有单个资源被淹没或未被充分利用,优化一个好的负载均衡器应该根据不断变化的环境和任务类型来调整策略。同时提出了一种基于遗传算法(GA)的新型负载均衡策略。该算法能够平衡云基础架构的负载,同时尽量减少给定任务集的构建范围。建议的负载平衡策略已使用CloudAnalyst模拟器进行了仿真。典型应用示例的仿真结果表明,该算法优于现有的先到先服务(FCFS),Round Robing(RR)和局部搜索算法Stochastic Hill Climbing(SHC)等现有方法。

文献[15]提出了模拟退火多种群遗传算法(SAMPGA),用于云计算任务调度,即模拟退火算法(SA)和多种群遗传算法(MPGA)的组合。在群体初始化中此算法采用最大最小算法来提高搜索效率。为了避免局部最优,提高全局最优性能。同时提出了一种基于自适应机制的多种群遗传进化的策略,以寻求更好的解决方案,提高了收敛速度。最后进行实验来评估所提出的方法在MATLAB中的效率。与模拟退火算法和模拟退火遗传算法相比,仿真结果表明改进后的算法在完成时间、完成成本、收敛速度和负载平衡度方面具有更优异的性能。

1.3 本文研究内容

在云计算中,虚拟机计算能力和计算任务的规模及类型均存在差异[6],由此一套完善的调度解决方案不仅能保证用户的服务质量,还能提高云资源计算处理效率,保证分布式服务器的资源浪费和负载均衡。针对云数据中心资源调度策略的不足,建立起云计算环境下的计算任务-虚拟机资源节点的一级资源调度模型,结合两种智能启发式算法:遗传算法和萤火虫算法。

遗传算法通过自适应的调整以及概率化的搜索方式得到最优解,具有良好的全局搜索能力。本文在云计算系统环境下,结合计算任务-虚拟机资源节点的一级调度模型,对个体编码、适应度函数、选择复制和交叉变异过程进行重新设计,建立基于遗传算法资源调度模型。但遗传算法不足之处在于没有能够及时利用网络的反馈信息,在参数随时间剧烈变化的网格环境下,遗传算法易趋向于早熟、收敛速度较慢,易陷于局部最优而导致资源调度方案不合理。萤火虫优化算法作为一种新型的种群智能启发式算法,模拟自然界中萤火虫发光特性。同样结合云计算资源调度模型,将萤火虫与计算资源相对应,重新设定决策域更新方式、选择吸引概率公式和位置移动策略,建立起基于萤火虫算法的资源调度模型。比遗传算法,该算法参数较少、操作相对简单、可靠性较好。综合分析两种算法,将两种重新设计的资源调度模型结合,相互补充,提出了基于萤火虫-遗传算法的资源调度模型。最后通过CLoudSim云计算仿真实验平台从完成时间和资源负载角度对上述模型进行实验,并结合其他优化算法比较分析其结果。

1.4 本文组织结构

第一章,介绍了云计算及资源调度的研究背景及意义及现状,阅读和分析参考文献等所提出的资源调度算法的优缺点,并提出了本文所研究的云计算资源调度课题,对本文的研究工作做具体的阐述。

第二章,描述了云计算体系架构,并简要介绍了海量数据管理等关键性技术和负载均衡相关理论,建立并分析云计算任务-虚拟机资源节点的资源调度模型。

第三章,描述了遗传算法原理。结合云计算任务和虚拟机资源节点,在个体编码、适应度函数设计、遗传算子设计等部分完成对算法模型的建立和资源调度过程的描述。

第四章,描述了萤火虫算法原理。在云计算环境下,结合云计算任务和虚拟机资源节点,在种群初始化、动态决策域更新、选择移动和位置更新等部分建立模型。并分析遗传算法和萤火虫算法的优缺点,将遗传算法与萤火虫算法相结合,建立萤火虫-遗传算法资源调度的总设计方案。

以上是毕业论文大纲或资料介绍,该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取,微信号:bysjorg。

相关图片展示:

您需要先支付 49元 才能查看全部内容!立即支付

该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找,微信号:bysjorg 、QQ号:3236353895;