基于遗传算法的云计算调度系统研究文献综述
2020-05-01 08:49:24
自2006年8月9日，Google首席执行官埃里克施密特在搜索引擎大会首次提出“云计算”的概念至今已有十余年，经过十多年的发展，作为主要用于科学计算的网格计算的民用版，云计算的理论逐渐发展并实现了商业应用。相比于传统的计算方式，云计算的优势在于充分利用互联网的优势，摆脱了本地计算资源和地域的限制，使计算任务按照一定的规则分布在大量的分布式计算机上，利用大规模的算力进行并行计算，效率更高。而今互联网通信技术不断发展，带宽和传输速率越来越高，随之而来的是全球每时每刻产生和需要处理的越来越大的数据量，我们正慢慢进入大数据时代；于此同时，亦得益于带宽的不断增长和全球众多、分散于各地的物理计算资源或者大型的计算中心，通过网络访问非本地的计算服务（包括数据处理、存储和信息服务等）的条件越来越成熟，云计算整合各方，展现出了不可估量的应用潜力，尤其是最近几年，各方巨头都在以前所未有的速度和规模推动云计算技术和产品的普及，各个云计算平台如雨后春笋般出现。准确把握并发展这个具有革命性的技术热点是时代对我们的要求。
问题总是随着发展出现的。随着云计算的用户越来越多、需要处理的数据量越来越大、应用场景越来越复杂，需要解决或者完善的问题也逐步显现，亟待解决，而任务调度问题可以说是其中的重中之重了。合适的任务调度策略能够尽最大可能的配置各种资源，无论是物理计算资源还是计算需要的能源亦或者网络带宽资源，从而提高计算效率；也能提高用户的使用体验，有利于技术的推广和接受从而使技术真正做到普惠于民、推动发展。任务调度问题本质是资源的优化利用，即在一定的资源下实现更高的计算效率，使任务完成时间尽量短、减小网络阻塞并提高服务质量从而实现既定的优化目标。基本过程便是根据优化目标设计适当的调度算法，以系统当前的资源和任务状态为条件，将用户的任务分配到合适的虚拟机上运算。而对优化问题的处理最常用的便是遗传算法，该算法以生物遗传为启发，目标便是寻找全局最优解，鉴于原始遗传算法存在一定的缺陷因此要根据不同问题进行算法的改进。本文要探讨的问题便是在任务独立调度的情况下，利用改进遗传算法实现总任务完成时间最小化的目标。
相比于网格计算，云计算的环境比较复杂，体现在参与调度的计算机软硬件、网络连接、计算性能以及用户提交的任务性质往往存在差异，并且在云计算领域至今没有实现标准化，因此采用不同的调度策略可以实现不同的优化目标。目前主要的优化目标主要有任务总完成时间最少、各个计算节点负载均衡、服务提供商付出最少开销以及提高服务质量等方面，国内外已有大量学者和机构致力于实现不同的优化目标。目前来看，单说调度策略，国内外的技术己经十分成熟并广泛应用于商业了，如Google、VMware、 HP、 Amazon、IBM和Apache Hadoop公司都对云计算任务调度策略做了深入的研究并取得了傲人的成果。其中具有代表性的两个互联网巨头的策略——Google的MapReduce和Amazon调度方法得到的良好的反馈，此外当前绝大多数任务调度依然使用Hadoop架构中的算法，却未能达到云计算的要求。
从不同的优化目标来看，结合改进的遗传算法，国内外也取得了很大成果。Pandey等人提出了粒子群启发式优化算法来进行任务调度；考虑到服务成本，Liu K平衡了时间与费用，提出了CTC任务调度算法。张荣浩结合蚁群算法和模拟退火算法，引入资源与任务的匹配因子与负载均衡度提出ACOSA；李建锋等人对传统遗传算法进行了改进，针对任务的总完成时间和平均完成时间提出了基于改进GA的双适应度任务调度算法，进一步改善了任务调度的时间性能；Tingting Wang等人以任务完成时间和负载均衡为优化目标同样对传统遗传算法进行了改进，一定程度上改善了以往任务调度中时间性能和数据中心资源利用率顾此失彼、难以兼得的困境；与之类似，王波等人从用户满意度和云服务供应商的利益出发，将粒子群算法和遗传算法融合，提出了符合用户需求的PSOGA改进算法。目前来看，遗传算法应用于任务调度已经取得了丰厚的经验，同时仍有很大的探索空间。
2. 研究的基本内容与方案
{title}2.1主要研究内容：云计算具有一定的商业属性，故其设计调度策略的目的是不断提高使用者的使用体验。从这方面来说是以QoS为优化目标，而其中任务完成时间绝对是一个重要的指标，在任务量和资源一定的情况下，尽量减小任务完成总时间有利于提高使用体验。虽然目前云计算的任务形式是独立任务和关联任务并行但此处本文的研究场景是独立任务调度，即不对关联任务比如优先级等做考虑，相比之下其数学模型会更加简洁，专攻一点也有利于设计更好的策略进而实现总任务完成时间最少的遗传算法优化目标。
（1）对手中在独立任务调度情况下各优化遗传算法所实现的优化目标进行比对和归纳，研究其数学模型，从而找出最适合实现最小化总任务完成时间优化目标的算法改进方案，以此为依据设计自己的调度策略；
（2）考虑到网格计算中采用min-min或者max-min的经典调度算法实现最优的任务完成时间，故欲将次算法应用于独立任务调度下的改进遗传算法中，借此也能减小算法的复杂度；同时对子代的筛选和算子的设计进行必要的改进并设计适应度函数。由于MATLAB强大的绘图功能以及简洁的编程环境故选择MATLAB作为仿真工具，评估算法的性能。3. 参考文献
[1]刘琼昕，陈嘉玉，宋晔，苏思悦. 混合遗传算法在云计算任务调度中的应用中国高科技产业化研究会会议论文集，2017-10-26
[2] 刘宇光，崔倩，张淼.基于遗传算法的云计算任务调度策略.信息技术Information Technology，2017年08期
[3] 戴艳红.云计算中一种基于遗传算法与效益驱动的任务调度算法.内蒙古师范大学学报(自然科学汉文版)，Journal of Inner Mongolia Normal University(Natural Science Edition)，2017年02期
[4]Wen-Zhun HUANG，Xin-Xin XIE.A Novel Cloud Computing System Intrusion Detection Model Based on Modified Genetic Algorithm.DEStech Transactions on Environment，Energy and Earth Science.2016-06-15
[5]Jie Zhao.A Benefit-driven Task Scheduling Algorithm based on Genetic Algorithm in Cloud Computing.Computer Science and Electronic Technology International Society.2015-11-28
[6]刘鹏.云计算[M].北京：电子工业出版社，2010.3
[7]冯宪彬，丁蕊.改进型遗传算法及其应用[M].北京：冶金工业出版社，2016.8
[8]雷英杰，张善文等.MATLAB遗传算法工具箱及应用[M].西安,西安电子科技大学出版社，2005.4
[9]Wang T, Liu Z, Chen Y, et al. Load balancing task scheduling based on genetic algorithm in cloud computing[C]//Dependable, Autonomic and Secure Computing (DASC), 2014 IEEE 12th International Conference on. IEEE, 2014: 146-152.
[10]刘春燕，杨巍巍.云计算基于遗传粒子群算法的多目标任务调度[J].计算机技术与发展，2017.1
[11]Rodriguez M A, Buyya R. A taxonomy and survey on scheduling algorithms for scientific workflows in IaaS cloud computing environments[J]. Concurrency and Computation: Practice and Experience,2017, 29(8)
[12]曹阳，刘亚军，俞琰.基于遗传-蚁群算法的云计算任务调度优化[J].吉林大学学报（理学版），2016.09
[13]Kliazovich D, Pecero J E, Tchernykh A, et al. CA-DAG: Modeling communication-aware applications for scheduling in cloud computing[J]. Journal of Grid Computing, 2016, 14(1):23-39.
[14]胡艳华，唐新来.基于改进遗传算法的云计算任务调度算法[J].计算机技术与发展，2016.09
[15]李建锋，彭舰.云计算环境下基于改进遗传算法的任务调度算法[J].计算机应用，2011.01
[16]邓见光.云计算任务调度策略研究[D].华南理工大学，2014.04
[17]Prahhavathi P, Nithyanandan L.Network selection in wireless heterogeneous networks [C]
//Proceedings of 2013 international conference on communications and signal processing.
Melmarunathur:[s.n.]，2013:357一361.
[18]Lee Y C,Zomaya A Y.Energy efficient utilization of resources in cloud computing systems[J]. Journal of Supercomputing, 2012, 60 ( 2) : 268一280
[19]王贝.云计算环境下任务调度优化算法的研究[D].中国科学技术大学，2017.5
[20]Babu P D, Amudha T. A novel genetic algorithm for effective job scheduling in grid environment[M]//Computational Intelligence, Cyber Security and Computational Models.Springer India. 2014:385-393
[21]刘琼昕，陈嘉玉，宋晔，苏思悦.混合遗传算法在云计算任务调度中的应用[Z].第十一届全国信号和智能信息处理与应用学术会议专刊，2017.10
[22]Convolbo M W, Chou J. Cost-aware DAG scheduling algorithms for minimizing execution cost on cloud resources[J]. The Journal of Supercomputing, 2016. 72(3): 985一1012.
[23]刘宇光，崔倩，张淼.基于遗传算法的云计算任务调度策略[J].信息技术，2017.8
