面向多目标优化的云计算调度研究综述*

郑 爽 吕遐东 陈 杰

（中国舰船研究设计中心 武汉 430000）

1 引言

云计算是并行计算和分布式计算技术等相结合的产物[1～2]。云计算利用互联网与虚拟机等技术使得云计算资源具有随时可用、按需服务等特性。云计算用户可以通过网络来远程调用数据中心中的虚拟机来运行应用程序或者存储数据。云计算使用按需付费的使用模式为用户提供高效可灵活调整的云计算资源，可以满足不同应用的各类需求，是目前一种普遍的计算方式。

云计算资源调度[3]是指根据云计算任务与云计算资源的实际情况将任务分配到资源执行且满足一定要求的一个过程，云环境下的资源调度是一个需要综合考虑各种情况的复杂性问题。对云服务供应商来说要有效的协调和分配资源，降低成本；对用户来说首先要满足服务的质量。云计算的计算资源共享池环境里有着大量资源节点，需要对资源进行合理分配与调度，才能实现海量数据的快速计算。

在优化设计中，要求多个目标达到最优的问题被称为多目标优化或者多约束问题[4]。多目标优化的云计算调度是在考虑多个调度指标的情况下将任务映射到合适的云计算的资源上的一个过程。

已存在一些相关的云计算调度相关综述研究文献，往往只着重于阐述云计算调度中启发式算法研究，对云计算调度中其他重要因素有所忽略。如：文献[5]看重不同云环境下云计算任务调度启发式算法研究与讨论。文献[6]针对云计算任务调度各类启发式算法优缺点进行了总结归纳。文献[7]以调度目的为侧重点总结归纳了四类调度的启发式算法策略。文献[8]也只以云计算任务调度启发式算法为出发点总结分析了各类方法的基本思想与优缺点。而本文针对云计算整个调度流程进行了梳理，并对常用的一些调度指标体系并进行系统性总结，在算法研究方面不仅总结了经典算法与启发式算法也阐述了基于强化学习、深度强化学习的新型调度研究，并都选取相关代表文献进行总结分析。最后，讨论面向多目标优化的云计算调度研究中存在的不足和未来研究趋势，为云计算调度的进一步研究提供参考。

2 体系架构

2.1 云计算基本概念

数据中心：云数据中心其中包括对服务器、存储、网络、应用等的虚拟化，使用户可以按需调用各种资源；其次还有对物理服务器、虚拟服务器以及相关业务的自动化流程管理。数据中心依据服务器性能等的不同分为单一数据中心、多同构数据中心、多异构数据中心。

服务器：服务器是通过虚拟化、集群技术等进行资源整合，通过云端控制平台按需生成相关主机资源。服务器也可称之为物理主机，可以自行分配与实行多种网络功能服务。服务器也可以分为同构与异构。

云计算任务（Task，t）：云计算任务就是云用户提交的需要用到云计算资源（服务器、网络设备、存储等）处理的任务，云计算任务根据任务的特点可以分为一般任务、计算型任务、存储型任务、内存型任务。

虚拟机（VM）：虚拟机是服务器通过虚拟化技术虚拟表示形式的应用、服务器、存储和网络的的一种服务模式，以虚拟机的形式为用户提供云服务可以减少IT开销，同时提高效率和敏捷性。虚拟机根据运行内存、CPU核心数、存储的不同也可以分为同构虚拟机与异构虚拟机，虚拟机对应任务类型也分为通用型、计算型、内存型和存储型等，这些虚拟机在CPU、内存、操作系统等软硬件设施上都有所不同。

云用户：通过云计算服务接口向云服务提供商请求云计算服务的大型企业、小型组织或个人。

云服务提供商：基于云平台、基础结构、应用程序、存储提供云服务服务的公司或者组织。

指标体系：对云计算调度的一种量化评价方案。可以根据调度指标的多少分为单一目标优化和多目标优化指标体系。云计算调度中的典型指标有任务执行时间、系统能耗、系统可用性、系统经济、负载均衡、资源利用率、安全性等。

指标权重：多目标优化的云计算调度中各各优化指标的的相对比重，权重不仅仅是某一指标所占的百分比，强调的是指标的相对重要程度，倾向于贡献度或重要性。

目标函数：是云计算调度系统的性能标准，云计算在调度中所追求的目标，通常，这些目标通过量化的指标与权重设置为数学函数的形式。

2.2 云计算调度架构

云计算调度架构如图1所示，在云计算调度架构中，云用户直接面对的是虚拟机，而虚拟机必须部署到服务器上才有能力来处理云任务，真正解决问题的还是实际的物理资源，所以云计算调度是一个二级的调度，即在满足一定调度指标的前提下，根据调度策略将任务分配到虚拟机上执行的任务调度[9]和将虚拟机部署到物理位置相同或分隔、资源同构或异构的服务器上的资源调度[10]两个调度过程。

图1 多目标优化的云计算调度架构

2.3 多目标优化的资源调度运行过程

云环境下的多目标优化调度需要从实际需求出发选择恰当的调度指标，调度指标可以选择一个或者多个，然后为每个指标定权重来构成调度的目标函数。通过这样的方式将多目标求解问题转换为单一目标函数最优化问题。然后调度策略生成器获取任务管理器与虚拟资源管理器中的信息结合云计算调度的指标评价体系通过调度算法来生成一个符合需求的调度策略或者说调度的方案。再按照生成的方案将云用户的任务提交到资源上运行，运行完成后将结果返回给云用户。

3 主要研究方面

3.1 云计算调度优化指标体系

在多目标优化的云计算调度问题上需要面对的指标是有很多的，为了得到用户和云服务提供商满意的调度结果，就需要从众多的调度指标中挑选出一定量的能充分代表需求的指标来构造一个指标体系。例如基于利益相关视角的多维QoS云资源调度方法[11]以云任务执行时间、云任务最终完成时间、云系统能耗、云系统可用性、云系统经济五个调度指标构成了一个基于利益相关的指标体系。面向服务可靠性的云资源调度方法[12]以服务器负载均衡作为调度指标体系设置了一个面向服务可靠性的指标体系。云环境下绿色任务调度策略[13]以系统性能作为指标体系设置了一个面向绿色云计算的调度体系。

云环境下的调度是要考虑单一或者多个指标最优化的复杂问题，需要从实际需求出发选择恰当的调度指标来构成一个多目标优化指标体系。根据实际需求出发，云计算相关调度指标体系可以分为面向性能的指标体系、面向经济的指标体系与面向绿色节能的指标体系。

目前尚无专门论文来面向多目标优化的云计算指标体系进行研究，本文根据不同论文的优化侧重点不同将相同类型优化体系进行了一定汇总。现阶段多目标优化的云计算调度指标体系研究成果较少，评价指标的设置没有一个科学的方法进行对比分析，需要进一步进行评价指标在数学方面的研究。

3.2 云计算调度优化指标权重确定方法

设置云计算调度指标体系之后，就需要依据各指标权重与云计算调度指标体系来确定调度的目标函数。在多目标优化的云计算调度中，各指标的相对重要性（权重）的确定是一个关键。其特点就在于指标与指标间的矛盾性，而解决矛盾性的就是依靠合理的给各指标设置权重来解决。对各指标的赋权的合理与否，直接确定到分析结论的可靠性，目前多目标优化的权重确定方法主要有主观定权法、专家评价法、层次分析法、熵权法、相关系数法等。但目前多目标优化的云计算调度中相关文献中定权重主要还为主观设置各指标权重。例如，文献[20]给时间、安全、费用、可靠性指标应用主观定权重（0.4，0.2，0.2，0.2）。文献[21]给执行时间、负载应用主观定权重为（1，1）。仅有极个别利用层次分析法来为各指标设置权重。例如，文献[22]应用层次分析法给执行时间、服务延迟成本、成本、运行能耗定权重为（0.39，0.07，0.375，0.165）。

表2 典型定权方法

目前在多目标优化的云计算调度研究中设置多目标权重的方法都非常原始，且绝大多数只看重在固定权重方式下调度结果的优劣，没有考虑到权重赋值的合理与否也与调度的结果好坏有着直接的影响，未来的多目标优化的云计算调度权重设置中应该对权重的具体值设置进行多次实验验证，找到一个最优的权重赋值方案。

3.3 云计算传统资源调度方法

在对云计算调度问题解决方法发探索中，人们首先想到的是针对一个目标然后不惜一切代价将该目标优化到极限，例如。在云计算任务调度方面的研究首先出现了一些简单但是很经典的调度策略。MCT（最小完成时间）[23]、先来先服务、Round Robin 调度[24]、贪婪策略调度[25]、Min-Min调度[26]和Max-Min调度[27]等。

但是在将单一目标最优化过程中可能会在其他因素上付出比较大的代价。随着科学的进步，此类问题求解方法的增加，人们开始考虑解决多目标同时得到优化的问题。

随着可以实现多目标优化的启发式算法的不断成熟，越来越多的研究人员把将基于生物启发的遗传算法、狮子算法、帝国竞争算法等和基于群体智能的蚁群算法、粒子群算法、猫群算法、鱼群算法等引入到云计算调度中，这类算法的思想[8]在于：解决多目标优化问题时，给出一个在满足约束条件的情况下，基于多目标优化的一个优解。可能这个解有时不是这个解空间中的最优解，但是是尽量满足调度指标的极优解。

表3 经典调度策略

表4 经典启发式算法

图2 启发式算法一般流程

各个启发式方法都有其优缺点，单独用来做云计算调度的算法都有其缺陷，有些研究人员就针对某一算法的缺项进行专门优化，设计了一系列改进型的启发式算法。例如，改进差分进化算法、改进遗传算法、改进粒子群、改进蚁群等。也有研究人员就将其中算法进行两两组合，利用算法之间优势互补来设计新的组合算法，例如利用遗传算法（GA）在迭代前期寻优速度快，蚁群算法（ACO）进化后期搜索速度快，求解效率高的的特点设计的GA-ACO优化算法。还有基于布谷鸟搜索（CS）和粒子群优化（PSO）两种算法相结合提出的多目标布谷鸟粒子群优化算法（MO-CPSO）等。

3.4 云计算新型资源调度方法

传统算法策略的最优解在特定的条件下才能获得，面对越来越复杂的云计算环境，其通用性不强，并且容易在多目标求解的过程中陷入局部最优解，从而无法得到全局最优解。针对这些问题就有研究人员将强化学习[36]、深度强化学习[37]等新兴技术应用到云计算调度中来探索最优的调度策略。

这类新型的云计算资源调度方法在机制上与传统启发式算法有很大的不同，例如强化学习（Reinforcement Learning，RL）作为一种无模型的学习方法，其是通过不断试错机制来探索解决问题的最优解。在多目标优化的云计算资源调度问题上可以通过不断试错的机制来得到多目标优化的云计算资源调度问题的最优解。深度学习具有很强大的特征提取的能力，在多目标优化的云计算资源调度问题上可以通过学习到的特征来进行优化调度。所以在云调度求解上二者也有着很好的性能表现，其次也可以将二者结合起来构成深度强化学习算法来充分利用二者的优势。

表5 改进启发式算法

表6 新型资源调度方法

4 结语

云计算通过虚拟化技术将各种资源整合起来形成资源池，并将大量云用户提交的任务分配到资源节点上运行，使各个用户都能按需获取计算资源、存储资源和各种软件服务。目前，多目标优化的云计算调度主要研究方向集中在调度算法上，多目标优化的云计算调度算法主要为启发式算法、改进的启发式算法。很少有将强化学习、深度学习等新型方法应用到多目标优化的云计算调度中来。其次，目前关于多目标的云计算调度的调度指标权重设置也处于一个很原始的状态，现有关于多目标的云计算调度研究的权重设置方式多为主观设置权重，仅有极个别利用层次分析法设置指标权重，但具体情况下权重如何设置，设置之后效果有何变化，也无研究人员专门研究此内容。

随着云计算平台的资源异构化、作业的多样化、服务质量的严格化，云服务提供商现在多倾向于使用大规模数据中心下的多用户多队列多虚拟机集群的服务模式。面对复杂多变的云环境，传统启发式算法其通用性不强的缺点渐渐显露了出来，未来云调度算法的研究应该从改进启发式算法转移到将强化学习、深度学习这类通用性更强的方法改进应用到多目标优化的云计算调度上来。调度指标的权重设计也应该尝试采用更多的数学分析的方法，例如模糊法、模糊层次分析法等。也可以尝试在调度过程中设计权重自适应调整的机制。

总之，一个优秀的多目标优化的云计算调度需要根据任务与资源的不确定性来灵活的采取调度策略，在尽可能综合考虑更多的调度指标下，提高云计算服务质量。