王昱，左利云

(1.广东石油化工学院 网络与教育信息技术中心，广东 茂名 525000；2.广东石油化工学院 计算机学院，广东 茂名 525000)

随着云计算的普及，云数据中心的规模和数量迅猛增长，调度问题成为云计算发展的关键，调度策略是云计算实现高效计算的重要因素。对此很多学者提出了一些解决方案，如对负载进行管理[1]、对应用数据进行划分优化[2]等，但无论是针对资源负载还是数据应用，都要面对如何尽可能满足用户多方面需求的情况下提高调度效率。而对于这种多目标优化问题的求解很多学者提出了采用一些智能仿生算法来实现[3，4]，如非支配排序算法(NSGA-II)[5]、Pareto支配进化算法(SPEA2)[6]、基于参考信息的进化算法(PAES)[7]等。文献[8]提出了一种偏好向量引导的高维目标协同进化算法。文献[9]提出了一种利润敏感的空间调度方法，其主要目标是服务商利润最大化，它采用基于遗传、模拟退火的粒子群优化算法实现。文献[10]针对IaaS的工作流调度问题，提出了一种进化算法来实现最大化完工时间和成本的优化。文献[11]针对云计算中任务的截止时间约束问题，提出一种基于二部图模型的调度算法。文献[12]针对端到端延迟约束问题提出一种启发式调度算法。文献[13]提出一种基于改进粒子群的优化算法。文献[14]为了降低任务执行成本提出一种改进遗传算法，它的主要目标在于降低工作流调度的成本。文献[15]提出了一种多目标调度方法，它的主要优化目标为整个系统的吞吐量。文献[16]提出了一种融合布谷鸟搜索算法与基于对立的学习算法结合的方法，以提高云计算中的性能并降低成本。这些研究多是从云计算提供方的角度出发，对云计算系统调度问题提出的调度方法，多目标优化也是针对云计算提供商的角度提出对性能和成本费用的优化。基于此，本文将从用户角度出发，针对用户对截止时间和费用的需求差异，研究云计算中的任务完成时间和费用的均衡调度问题，从而提高调度完成效率并减少用户的花费。本文提出了一种基于改进遗传算法的调度方法，同时考虑截止时间和费用预算两个约束条件下，尽可能实现时间和费用均衡最优化。

1 系统模型

用户提交任务至任务请求管理器，经过任务预处理至调度管理器，基于改进遗传算法的智能调度方法部署在调度管理器中，其系统结构见图1。图1中，用户通过用户接口提交任务请求至请求管理器，请求管理器将任务请求信息传输至调度管理器，包括任务大小、所需数据量、完成的截止时间及预算费用等。调度管理器中拥有可用云资源信息，如可用资源的计算、传输能力和计算、传输价格等。任务提交至调度管理器时，调度管理器根据任务参数约束，结合资源参数等信息，采用本文提出的多目标优化算法得到最合适的任务资源组合，将结果返回给用户。

图1 系统结构模型

1.1 资源描述

云计算中调度的资源，主要指虚拟机。模拟亚马逊云服务的模式，则资源Ru为

Ru=

(1)

式中：Cu为资源计算能力，影响任务计算时间；Lu为传输能力，影响任务的传输时间；Pu为计算价格；Su为存储价格；Qu为传输价格(主要指外部传输价格，因亚马逊云服务中内部传输不收费)。

1.2 任务描述

设任务Ti为任务请求的一个单位，每个资源一次处理一个任务。则任务Ti为

Ti=

(2)

式中：TDi为任务的截止时间；TCi为任务长度；TLi为任务计算所需信息量，直接影响任务的传输时间；TMi为任务的预算花费。

1.3 时间和费用模型

在任务调度时有两个约束，分别为截止时间和费用。要满足这两个约束条件必须要计算调度模型中任务的完成时间和花费。

任务完成时间由任务计算时间和传输时间两部分组成。此时，由式(1)、式(2)可计算任务Ti在云计算中的完成时间tiRu为

(3)

由式(3)可得，截止约束条件为tiRu≤TDi。

假设费用产生主要在云计算的租用上，其主要有计算费用、存储费用和传输费用三部分组成。任务Ti使用云计算的花费Fi为

Fi=TCi×Pu+TLi×Qu+TLi×Su

(4)

由式(4)可得，费用约束为Fi≤TMi。

1.4 多目标优化调度模型

该问题的多目标优化模型表示如下：

(5)

(6)

s.t.tiRu≤TDi，Fi≤TMi

(7)

式中：Ti为任务i，i=1,2,…,n;Rj为资源j，j=1,2,…,m;fij为满足费用函数f(x)的任务资源分配对；cij为满足时间函数c(x)的任务资源分配对。

1.5 约束处理—惩罚函数

由于约束参数与多个变量相关，为了根据约束条件更好地调整并确定相关变量，可采用柔性约束的处理方法，将惩罚项加入总的时间和费用函数中，可得到时间和费用的惩罚函数为

Ftime′(x)=F(x)+α|tiRu-TDi|，Fcost′(x)=F(x)+β|Fi-TMi|

(8)

式中：α和β分别为时间和费用的惩罚因子。

2 基于改进遗传算法的多目标优化调度方法

本优化问题包括了费用和时间最小两个优化目标,同时还有截止时间、成本预算等约束条件,对于这类组合优化问题的求解尤其是最优解有一定难度。而改进的遗传算法NSGA-II在解决该类优化问题时有一定优势,它降低了非劣排序遗传算法的复杂性,具有运行速度快、解集收敛性好等优点。它在初始化阶段利用初始值进行引导,即通过单目标遗传算法获取NSGA-II初始种群的部分个体,以提高算法的收敛性能。该算法的实现过程简单描述如伪代码所示。其中Xij为任务Ti在时间j时的调度变量，N为任务总数，H为时间总数。

3 实验验证

3.1 实验环境及参数设置

为了验证所提调度方法性能，在云仿真软件Cloudsim3.0上进行仿真实验。创建了两个数据中心A和B，两个数据中心中虚拟机数目分别为20和200，A中虚拟机的配置参数为：1个CPU，CPU计算能力为200 MIPs，内存1 G，硬盘空间2 G，带宽2 M/s；B中虚拟机的配置参数均为A中虚拟机配置参数的2倍。创建了100 ～600个随机云任务，其任务长度为400～1000 MIPs，文件大小为200～400 MB，输出大小为20～40 MB。

3.2 调度方法性能的评价指标

实验采用了三个评估指标来评估所提调度方法的性能：任务完成时间、使用云计算的费用和截止时间超出率。将Min-Min算法[17]、基准调度方法(FCFS)[18]和基于蚁群算法的多目标调度方法MOACO，与本评价指标中截止时间超出率用于评估超出任务截止时间的情况，其表示为

表1 两个数据中心收费标准参数AB计算价格/(＄/h)0.0850.120存储价格/(＄/GB)0.060.10传输价格/(＄/GB)0.050.10

文所提调度方法进行对比。实验中的费用参考亚马逊云服务的价格(见表1),计算能力等参数不同,数据中心的费用也不同。云计算的费用是根据任务计算时间折合计算量,存储和传输费用则根据任务本身存储和传输大小统计。

(9)

式中：nv为超出截止时间的任务数；n为总任务数。

3.3 各种方法的调度完成时间

本实验中完成时间是在不超过任务截止时间情况下执行任务花费的时间，通过20次实验取平均值得到4种方法(MONSGA、MOACO、Min-Min和FCFS)在任务数为100～600范围内的完成时间，见图2。并通过任务的完成时间来评估4种方法的调度效果。

图2 完成时间

由图2可知，MONSGA表现最好，MOACO次之，尤其是随着任务的增多，这两种方法的优势越明显。而这4种算法中，FCFS的效果最差。Min-Min算法虽然在完成时间方面较有优势，但随着任务的增多其表现不如多目标优化的仿生算法MONSGA和MOACO，这是由于MONSGA和MOACO算法能随着代数增加智能调整逼近最优解，实现多目标间的均衡优化。而由于MONSGA惩罚因子的增加，并对初始值进行了引导，使得其效果更优于MOACO。

3.4 各种方法的费用

为了评估4种方法使用云计算的费用情况，实验分两种情况，即在任务数分别为200和500时根据任务的不同截止时间约束，评估其费用情况，实验结果见图3和图4。

图3 200个任务时的费用 图4 500个任务时的费用

由图3、图4可知，这4种方法中MONSGA的费用最小，MOACO次之，Min-Min费用最高，这是由于Min-Min算法的目标是完成时间最优，它总优先调度优势资源，导致费用最高。而MONSGA和MOACO追求多目标优化，从而实现费用与时间的均衡，其费用相对较少，二者相比，由于MONSGA对初始值进行了引导，其效果比MOACO更好。

3.5 截止时间违反率

设置任务为500，截止时间为100～3000 s。通过实验验证截止时间超出率这一指标，其结果见图5。

由图5可知，截止时间违反率也是MONSGA和MOACO表现最好，由于这两个多目标优化算法都考虑了截止时间约束问题。且二者中，MONSGA表现最好，MOACO次之。而Min-Min算法由于追求完成时间最优，导致一些大任务违反截止时间。

图5 截止时间违反率

4 结语

为实现云计算中调度完成时间与费用的均衡优化问题，本文提出了一种基于改进遗传算法的调度优化方法——MONSGA，以任务的完成时间和费用为目标，考虑截止时间和费用预算约束，并将其与MOACO算法、FCFS算法、Min-Min算法进行对比。结果显示，提出的调度方法MONSGA在完成时间、费用、截止时间违反率三个评估方面均表现最好，且这种优势随着任务数的增加而更明显。