文章快速检索     高级检索
  浙江大学学报(工学版)  2017, Vol. 51 Issue (6): 1233-1241  DOI:10.3785/j.issn.1008-973X.2017.06.022
0

引用本文 [复制中英文]

李建丽, 丁丁, 李涛. 基于二次聚类的多目标混合云任务调度算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1233-1241.
dx.doi.org/10.3785/j.issn.1008-973X.2017.06.022
[复制中文]
LI Jian-li, DING Ding, LI Tao. Multi-objective hybrid cloud task scheduling using twice clustering[J]. Journal of Zhejiang University(Engineering Science), 2017, 51(6): 1233-1241.
dx.doi.org/10.3785/j.issn.1008-973X.2017.06.022
[复制英文]

基金项目

国家自然科学基金资助项目(61300176);中央高校基本科研基金资助项目(2016JBM019)

作者简介

李建丽(1990—),女,硕士生,从事云计算、计算机并行处理研究.
orcid.org/0000-0003-3760-7853 .
E-mail: 14120399@bjtu.edu.cn

通信联系人

丁丁,女,副教授.
orcid.org/0000-0002-4108-3418.
E-mail: dding@bjtu.edu.cn

文章历史

收稿日期:2016-11-30
基于二次聚类的多目标混合云任务调度算法
李建丽 , 丁丁 , 李涛     
北京交通大学 交通数据分析与挖掘北京市重点实验室, 北京 100044
摘要: 针对混合云环境包含大量异构云计算节点的情况, 提出二次聚类方法, 依据资源的综合特性, 将异构资源进行分簇, 将任务分发到合适的资源聚类, 缩小任务搜索空间.在此基础上, 结合私有云的安全可靠性、公有云的可扩展性以及用户需求的多样性, 提出混合云环境下多目标优化的任务调度算法.该算法首先在私有云优先调度截止时间短的任务, 对于每个聚类, 将任务分配给完成时间最接近于其结束时间的资源, 以完成更多的任务;将溢出的高负载任务转移到公有云聚类执行, 结合任务的计算成本、通信开销和截止时间的约束, 选择费用最低的资源.实验结果表明, 与传统无聚类的算法相比, 该算法降低了执行费用, 同时提高了资源利用率和用户满意度.
关键词: 混合云    二次聚类    任务调度    多目标优化    资源异构    
Multi-objective hybrid cloud task scheduling using twice clustering
LI Jian-li , DING Ding , LI Tao     
Beijing Key Lab of Traffic Data Analysis and Mining, Beijing Jiaotong University, Beijing 100044, China
Abstract: A twice clustering method was introduced aiming at the case that hybrid cloud environment contains a large number of heterogeneous computing nodes. This method reduced task search space through clustering the heterogeneous resources based on the synthetic characteristics of resources and splitting tasks to the appropriate cluster resources. On this basis, multi-objective task scheduling algorithm in hybrid cloud was proposed, combined with the security and reliability of the private cloud, the scalability of the public cloud and the diversity of user requirements. Firstly, the earliest deadline first algorithm was used in private cloud. To accomplish more tasks, the task was assigned to resource whose completing time was closest to the deadline for each cluster. Then, the public cloud handled the overloading tasks, which would choose the lowest-cost resource under the constraint of computing budget, communication cost and the deadline. Simulation results confirm that the proposed algorithm performs better in lower cost, better resource utilization and greater user satisfaction, compared to the traditional algorithm without clustering.
Key words: hybrid cloud    twice clustering    task scheduling    multi-objective optimization    resourceheterogeneity    

云计算将计算、存储、内容传输、网络和应用等从用户终端集中到“云端”, 形成了用户按需付费, 获取“云端”资源的一种新型服务模型[1-4].任务调度是云计算的基本研究问题之一.随着计算机的更新换代, 云计算环境包含大量的异构资源, 任务调度就是考虑异构资源的综合性能, 结合任务的各种需求, 以一种合理的方式把任务分配到不同的计算节点上, 实现资源与任务的有效匹配.云计算资源调度直接影响整个执行的性能、稳定性和可靠性, 因此, 资源的有效调度已经成为影响云计算能否成功的重要因素之一[5].

目前, 云计算模式大致分为3类:私有云、公有云和混合云.私有云是企业或组织内部提供的专有的云计算系统, 具有数据安全性好、服务质量高等特性;公有云是指以第三方提供的方式为用户提供服务的云计算平台, 具有资源规模大、按需付费的特点;混合云融合了私有云和公有云, 是近年来云计算的主要发展模式和方向[6-8].混合云架构, 不仅可以利用私有云的保密性来保证重要数据的安全, 同时也突破了私有云的硬件限制, 利用公有云的可扩展性, 更灵活更高效地完成突发峰值业务的调度.

在混合云平台中, 任务调度存在新的挑战[9-11].首先, 混合云存在大量的异构节点, 任务调度是一个复杂的大规模优化问题.其次, 混合云的用户数量级很大, 不同的用户需求各异, 用户提交的任务越来越多样化.最后, 在混合云环境下, 实现完成时间和整体耗费之间的平衡直接关系到整个系统的性能和用户的使用满意度.可见, 混合云平台的任务调度是一个复杂的大规模多目标优化问题.由此, 任务调度面临着三大问题:一是混合云环境资源节点增多, 计算复杂度不断增大;二是资源的异构性以及任务需求多样, 任务分配变得困难;三是平衡完成时间和整体耗费增加了调度难度.

目前云计算调度机制还未形成统一的标准与规范, 混合云环境下的调度算法不多.一些常见的启发式调度算法包括:Max-Min, Min-Min, Greedy算法等.上述算法的主要目标是缩短任务的执行时间, 无法反映用户真正的服务质量(quality of service, QoS)需求.综合考虑用户的多个需求对任务调度的影响, 已有一些方法, 如Van den Bossche等[12]提出的一种基于关键因素的二进制调度方法、Wang等[13]提出的满足用户QoS需求的自适应调度算法(adaptive scheduling algorithm, AsQ), 考虑的都是整体服务资源, 当任务量大、资源数多的时候, 选择资源的时间开销很大.结合资源异构特性, 将资源合理划分, 缩小任务的搜索空间, 则能够直接缩短任务匹配资源的时间, 有效降低任务调度开销.

聚类是实现资源分类预处理的一种有效方式, 聚类分析方法近年来被很多学者用于网格计算和云计算领域的资源划分和任务调度工作, 主要有划分方法、层次方法、基于密度的方法、基于网格的方法以及基于模型的方法.最常见的是基于划分的方法, 包括硬划分和软化分2种类型, 区别在于隶属度的不同.硬划分是基于目标函数将每个对象严格地划分到某个类中, 隶属度不是“0”就是“1”, 属于或者不属于某一类的划分非常严格.硬划分方法的典型代表如K-Means聚类方法[14]和C-均值聚类算法[15].然而现实中, 大多数个体对象并没有严格的属性, 软化分就是用模糊的方法处理聚类问题, 隶属度区间为[0, 1], 在一定程度上属于或者不属于某一类.模糊聚类分析方法是软化分的一种方法, 该方法建立了对对象类属的不确定性的描述.在混合云环境下, 存在大规模的不同级别的计算机集群, 资源异构性和模糊性非常明显, 不同资源之间的差异性通常没有严格的区分, 因此模糊聚类是一种比较合适的资源划分方法.

模糊聚类算法在云计算领域的资源划分和任务调度的研究有很多.杜晓丽等[16]针对DAG任务图提出了一种基于传递闭包法的模糊聚类调度算法.陈志刚等[17]提出了基于超图的多维性能聚类任务调度算法.李文娟等[18]提出了基于FCM聚类方法的任务调度算法.Li等[19]提出了基于信任驱动和QoS需求的工作流聚类分析调度方法.江务学等[20]提出了异构云环境下基于分簇的云资源感知任务调度方案.这些方法都为任务调度和云资源聚类提供了有价值的借鉴. K-Means、FCM以及文献[20]将资源默认分为3种资源簇这些方法不适合混合云的异构特点.当出现数量庞大的异构资源时, 杜晓丽等[16]提出的基于传递闭包的模糊聚类算法大量增加聚类个数, 直接导致了同类资源被划分到独立的资源簇中.在任务调度的过程中, 存在大量闲散未被利用的计算资源.

针对上述问题, 本文提出混合云环境下基于二次聚类的多目标任务调度算法(multi-QoS task scheduling based on twice clustering in hybrid cloud, MQTS-TC):通过二次聚类将异构资源按照其综合性能进行分簇, 解决混合云的资源异构问题;在此基础上, 选择满足任务需求并且最接近于任务截止时间的资源聚类, 更有效地完成任务对资源的选择.用户提交的任务首先在私有云上执行, 优先调度时间约束较紧的任务, 根据资源负载对任务分配实施调整, 保证私有云完成更多的任务, 溢出的高负载任务则调度到公有云上完成, 结合任务的计算成本、通信开销、截止时间和安全性约束, 选择费用最低的资源.

1 调度模型 1.1 任务模型

本文调度模式为批处理调度模式, 假设用户提交的每个任务都是云调度器进行任务和资源匹配的最小单位, 用户提交的任务集T={t0, t1, …, tn-1}由n个相互独立的元任务组成, 用户提交的基本单元ti(i∈[0, n-1])可以进一步表示为第i个任务:

$ {{t}_{i}}=\left\{ {{t}_{\text{ID}}}, {{t}_{\text{Len}}}, {{t}_{\text{File}}}, {{t}_{\text{Out}}}, {{t}_{\text{Se}}}, {{t}_{\text{DL}}}, {{t}_{\text{Cost}}} \right\}. $

式中:tID为任务的标号;tLen为任务计算量的大小, 用任务包含的指令数表示;tFile为处理任务需要的相关输入数据的大小;tOut为处理任务产生的相关输出数据的大小;tSe为任务对资源安全性的要求, 共分为5个等级{1, 2, 3, 4, 5}, 等级越高, 表示该任务对资源的安全性要求越高;tDL为任务的最晚完成时间, 作为调度策略能否成功的一个约束参数;tCost为任务在执行过程中需要的最高预算费用, 作为调度策略成本控制的一个约束参数.

1.2 资源模型

虚拟化是云计算的关键技术之一, 可以将云环境当中的实体资源抽象成各种虚拟资源, 用户连接到网络可以获得更多类型的服务.R={r0, r1, …, rm-1}表示云环境的虚拟资源集合, 由m个资源组成, 其中, 第j个资源rj(j∈[0, m-1])可以进一步表示为

$ {{r}_{j}}=\left\{ {{r}_{\text{ID}}}, {{r}_{\text{Mips}}}, {{r}_{\text{Size}}}, {{r}_{\text{Bw}}}, {{r}_{\text{Pes}}}, {{r}_{\text{Se}}} \right\}. $

式中:rID为资源的标号;rMips为资源的计算能力;rSize为资源的存储能力;rBw为资源的网络传输能力;rPes为资源含有CPU的个数;rSe为资源的安全性的级别, 同样共有5个等级{1, 2, 3, 4, 5}, 等级越高, 表示该资源的安全性能越好.

在该模型当中, 每个资源都只有一个CPU, 每个资源在同一时刻只能运行一个任务, 不考虑加速比的概念.假定私有云是安全的, 安全性级别的设置主要是针对公有云的.私有云上的操作费用和维护费用都被忽略掉, 只有租用公有云时才会按需付费.

2 二次聚类

本文中的环境异构主要是指资源节点的处理能力、存储能力和不同节点之间的数据传输能力3个方面的差异.在异构环境下, 任务分配的资源不同, 其完成时间包括任务执行时间, 任务输入、输出时间定会受到影响, 进而影响整个应用程序的完成和用户的满意度.因此, 在进行资源选择的时候, 需要根据资源的综合能力对资源加以区分, 以实现资源和任务的合理匹配.模糊聚类便是一种比较合适的资源划分方法, 并且该方法更加适合混合云的异构特点.

模糊聚类算法可以解决一定的资源异构问题, 然而在实际的云计算环境当中, 由于资源的规模很大, 且种类差异性较大, 导致基于传递闭包法的模糊聚类算法的聚类随着资源规模的增大, 聚类类型个数急剧增大.因此, 本文提出一种二次聚类方法, 主要分为2个步骤:首先对数据的预处理, 将云资源的数据归一化, 消除量纲的影响, 建立资源的模糊相似矩阵和模糊等价矩阵, 获得初步的聚类结果;其次计算聚类资源的类间相似度, 进行二次聚类, 优化聚类结果.

2.1 问题定义

文中定义了3个资源特征来表示资源的整体性能, 则资源集合R={r0, r1, …, rm-1}中的每个资源rj(j∈[0, m-1])性能都可以由一个三维向量来表示, 即

$ {\mathit{\boldsymbol{r}}_j} = \{ {r_{j1}},{r_{j2}},{r_{j3}}\} ,j \in \left[ {{\rm{0}},m{\rm{ - 1}}} \right]. $

式中:rj1rj2rj3分别表示资源的计算能力rMips、存储能力rSize和网络传输能力rBw.

定义1  资源综合能力rGj可以根据资源的3个性能指标综合计算得出:

$ {r_{{\rm{G}}j}} = \sqrt {\frac{{ar_{j1}^2 + br_{j2}^2 + cr_{j3}^2}}{{a + b + c}}} . $ (1)

式中:abc分别表示用户对计算能力、存储能力和传输能力的偏好, 根据实际需求, 一般取大于0的实数.a/(a+b+c)、b/(a+b+c)、c/(a+b+c)分别表示计算能力、存储能力和传输能力所占的比重.为了简化计算, abc的取值分别为0.7、0.1和0.2, 在实际计算中, a+b+c的和不一定为1, 但是必须要保证计算能力、存储能力和传输能力所占比重的和为1.若用户对计算能力、存储能力、传输能力的要求不同, 可以对其所占比重进行调整, 相应地修改abc的取值.

定义2  聚类资源综合能力rCGk, 表示第k个聚类Cluster的综合能力, 为类内所有资源的综合能力的均值:

$ {{r}_{\text{CG}k}}=\frac{1}{x}\sum\limits_{j=0}^{x}{{{r}_{\text{G}j}}}\text{.} $ (2)

式中:x表示类内包含的资源数.

定义3  聚类资源相似度Dij, 表示第i个聚类资源rCGi和第j个聚类资源rCGj的相似度, 经过类间距的计算得出:

$ {{D}_{ij}}={{r}_{\text{CG}i}}-{{r}_{\text{CG}j}}. $ (3)
2.2 二次聚类的主要步骤 2.2.1 数据预处理

假设资源的各项性能指标原始数据如表 1所示.

表 1 云虚拟资源性能指标原始数据 Table 1 Original data of cloud virtual resources performance

首先利用资源各项性能指标的均值和标准差对原始数据进行标准化处理, 消除量纲的影响:

$ r{{\prime }_{jk}}=\frac{{{r}_{jk}}-{{{\bar{r}}}_{k}}}{{{S}_{k}}}. $ (4)

式中:${{\bar{r}}_{k}}$是资源在第k个性能指标上的所有原始数据的均值, Sk是资源在第k个性能指标上的原始数据标准差.

由式(4) 得到的结果不一定在[0, 1], 因此, 再次使用极值标准化方法, 将资源归一化到[0, 1]:

$ r{{\prime\prime }_{jk}}=\frac{r{{\prime }_{jk}}-r{{\prime }_{k\text{min}}}}{r{{\prime }_{k}}_{\text{max}}-r{{\prime }_{k}}_{\text{min}}}. $ (5)

式中:rkminr0k, …, rm-1k的最小值, rkmaxr0k, …, rm-1k的最大值, m为资源的个数.处理后的资源性能指标数据如图 1所示.

图 1 资源原始数据预处理结果 Fig. 1 Pre-processing results of resource original data
2.2.2 一次聚类

(1) 建立模糊相似矩阵.

建立模糊相似矩阵, 计算方法有很多种[21], 如余弦法、相关系数法、最小算术平均法、欧式距离法、汉明距离法等.本文利用最大最小法得到资源性能指标数据的模糊相似关系${{{\tilde{R}}}_{s}}, {{{\tilde{R}}}_{s, jk}}$表示rjrk的相似度:

$ {{{\tilde{R}}}_{s}}_{\ jk}=\frac{\sum\limits_{t=1}^{d}{\text{min}~\left( r{{\prime\prime }_{jt}}, r{{\prime\prime }_{kt}} \right)}}{\sum\limits_{t=1}^{d}{\text{max}}\left( r{{\prime\prime }_{jt}}, r{{\prime\prime }_{kt}} \right)}. $ (6)

式中:d为资源性能指标个数, rjtrj资源的第t维性能指标, rkrk资源的第t维性能指标.

$ {{\tilde{R}}_{s}}\approx \left[\begin{matrix} 1.00&0.31&0.13&0.10&0.13&0.44&0.46&0.08&0.\ 35&0.41&0.12&0.14 \\ 0.31&1.00&0.62&0.64&0.10&0.64&0.30&0.51&0.71&0.74&0.56&0.11 \\ 0.13&0.62&1.00&0.81&0.36&0.40&0.37&0.83&0.44&0.64&0.88&0.40 \\ 0.10&0.64&0.81&1.00&0.25&0.40&0.22&0.75&0.44&0.66&0.71&0.29 \\ 0.13&0.10&0.36&0.25&1.00&0&0.48&0.50&0&0.18&0.47&0.75 \\ 0.44&0.64&0.40&0.40&0&1.00&0.20&0.33&0.89&0.71&0.37&0 \\ 0.46&0.30&0.37&0.22&0.48&0.20&1.00&0.29&0.22&0.42&0.34&0.57 \\ 0.08&0.51&0.83&0.75&0.50&0.33&0.29&1.00&0.36&0.54&0.95&0.38 \\ 0.35&0.71&0.44&0.44&0&0.89&0.22&0.36&1.00&0.78&0.40&0 \\ 0.41&0.74&0.64&0.66&0.18&0.71&0.42&0.54&0.78&1.0&0.58&0.20 \\ 0.12&0.56&0.88&0.71&0.47&0.37&0.34&0.95&0.40&0.58&1.00&0.36 \\ 0.14&0.11&0.40&0.29&0.75&0&0.57&0.38&0&0.20&0.36&1.00 \\ \end{matrix} \right] $

(2) 建立模糊等价矩阵.

对模糊相似矩阵通过求传递闭包建立模糊等价矩阵 Rs*, 然后通过设定不同的阈值α∈[0, 1]来划分, 可以得到不同的聚类结果.α值越接近于0, 说明类内的资源相似度越小; 反之, 则说明相似度很高.

$ R_{s}^{*}\approx \left[\begin{matrix} 1.00&0.46&0.46&0.46&0.46&0.46&0.46&0.46&0.\ 46&0.46&0.46&0.46 \\ 0.46&1.00&0.66&0.66&0.50&0.74&0.50&0.66&0.74&0.74&0.66&0.50 \\ 0.46&0.66&1.00&0.81&0.50&0.66&0.50&0.88&0.66&0.66&0.88&0.50 \\ 0.46&0.66&0.81&1.00&0.50&0.66&0.50&0.81&0.66&0.66&0.81&0.50 \\ 0.46&0.50&0.50&0.50&1.00&0.50&0.57&0.50&0.50&0.50&0.50&0.75 \\ 0.46&0.74&0.66&0.66&0.50&1.00&0.50&0.66&0.89&0.78&0.66&0.50 \\ 0.46&0.50&0.50&0.50&0.57&0.50&1.00&0.50&0.50&0.50&0.50&0.57 \\ 0.46&0.66&0.88&0.81&0.50&0.66&0.50&1.00&0.66&0.66&0.95&0.50 \\ 0.46&0.74&0.66&0.66&0.50&0.89&0.50&0.66&1.00&0.78&0.66&0.50 \\ 0.46&0.74&0.66&0.66&0.50&0.78&0.50&0.66&0.78&1.00&0.66&0.50 \\ 0.46&0.66&0.88&0.81&0.50&0.66&0.50&0.95&0.66&0.66&1.00&0.50 \\ 0.46&0.50&0.50&0.50&0.75&0.50&0.57&0.50&0.50&0.50&0.50&1.00 \\ \end{matrix} \right] $

本文取α=0.8, 得到的聚类结果为{r0}, {r1}, {r2, r3, r7, r10}, {r4}, {r5, r8}, {r6}, {r9}, {r11}.可以看到, 私有资源被分成了8类, 每一个类称为一个Cluster.实验表明, 随着资源数量的增多, 聚类的类型也逐步增多, 云环境中资源的异构性致使该方法聚类效果下降.

2.2.3 二次聚类

以上聚类结果按照聚类综合能力rCG升序排序, 排序结果如下:{r0}, {r5, r8}, {r11}, {r6}, {r1}, {r9}, {r4}, {r2, r3, r7, r10}.综合考虑资源聚类的差异性, 即聚类资源的相似度Dij, 当最近邻距离在一定范围之内, 即Dij < β, 将这2类归为同一类.经过计算聚类的类间距离, 归并距离相近的类, 得到好的聚类结果.假设β=0.06, 二次聚类的聚类结果如下:{r0, r5, r8}, {r1}, {r6, r9, r11}, {r4}, {r2, r3, r7, r10}, 重新分成5类, 可以通过调节β的值, 来达到比较合理的聚类结果.聚类结果的好坏, 通过一个F统计量来衡量:

$ F = \frac{{\sum\limits_{i = 1}^C {\sum\limits_{k = 1}^{{C_i}} {\sqrt {\frac{{\parallel {r_{{\rm{G}}k}} - {r_{{\rm{CG}}i}}{\parallel ^2}}}{{{C_i}C}}} } } }}{{\sum\limits_{i,j = 1}^C {\sqrt {\frac{{\parallel {r_{{\rm{CG}}i}} - {r_{{\rm{CG}}j}}{\parallel ^2}}}{C}} } }}. $ (7)

式中:Ci为每一个聚类内的资源数量, C为聚类个数, 分子表示类内每个资源与该类聚类中心的平均距离, 即类内元素的距离, 其值越小, 聚类结果越优;分母表示不同类中心与类中心的距离, 即类间距, 其值越大, 聚类结果越优.由此可知, F值越小, 聚类效果越好.

3 多目标任务调度算法 3.1 问题描述

在任务调度的过程当中, 考虑了任务的数据传输时间和CPU计算时间以及租用公有云消耗的数据传输费用、数存储费用和计算费用, 目标就是在任务截止时间约束和消耗代价约束条件下, 尽量地降低时间消耗和费用消耗.

定义4  数据传输时间TD.假设所有任务数据都在私有云上, 当任务需要转移到公有云执行时, 数据必须通过网络传输到公有云, 且传输时间取决于网络带宽, 第i个任务ti传输到第j个资源rj的数据传输时间如下式:

$ {{T}_{\text{D}i}}_{, j}=\frac{{{t}_{\text{File}i}}+{{t}_{\text{Out}i}}}{{{r}_{\text{Bw}j}}}. $ (8)

定义5  CPU计算时间TC, 取决于分配资源的计算能力:

$ {{C}_{i, j}}=\frac{{{t}_{\text{Len}i}}}{{{r}_{\text{Mips}j}}}. $ (9)

表示分配到第j个资源上的第i个任务的CPU计算时间.

定义6  预计开始执行时间TS, 表示从任务分配给资源起到任务得到执行的预估时间, 也称任务等待时间.

定义7  费用Ei, j, 租用公有云的消耗代价, 如下式:

$ {{E}_{i, j}}={{D}_{i}}\times {{u}_{j}}+{{D}_{i}}\times {{v}_{j}}+{{C}_{i, j}}\times {{w}_{j}}. $ (10)

式中:Di=tFilei+tOuti, ujvjwj分别表示第j个资源rj的单位传输价钱、单位存储价钱和单位计算价钱.Ei, j表示第i个任务在第j个资源上的执行费用, 为数据传输费用、存储费用和计算费用的和.

定义8  多目标多重约束问题.

$ \begin{align} &\text{Minimize} \\ &\sum\limits_{k=0}^{c}{\sum\limits_{j=0}^{m-1}{\sum\limits_{i=0}^{n-1}{{{E}_{i, j}}\times {{\theta }_{i, j, k}}}}}. \\ &\sum\limits_{k=0}^{c}{\sum\limits_{j=0}^{m-1}{\sum\limits_{i=0}^{n-1}{\left( D{{T}_{i, j}}+{{C}_{i, j}}+E{{S}_{j, k}} \right)}}}\times {{\theta }_{i, j, k}}. \\ &\text{Subject to} \\ &{{E}_{i, j}}\le {{t}_{\text{Cost}i}}. \\ &D{{T}_{i, j}}+{{C}_{i, j}}+E{{S}_{j}}\le {{t}_{\text{DL}i}}. \\ &{{t}_{\text{Se}i}}\le {{r}_{\text{Se}j}}. \\ \end{align} $

由上式可知,有2个优化目标:最小化任务调度的费用和最小化任务的总完成时间.其中, θi, j, k∈{0, 1}表示第i个任务在第j个资源上运行, 若该资源属于第k个Cluster, 则取值为1, 否则, 取值为0.有3个约束条件, 每个任务执行的费用要在预算范围之内;执行时间须在完成时间约束条件之内;本文中私有云不予考虑安全问题, 同时, 认为当任务在公有云上执行时, 公有资源的安全性等级必须在任务安全性等级之上, 否则, 任务转移不成功.

3.2 调度模型

本文的调度模型视图如图 2所示.

图 2 混合云资源调度模型 Fig. 2 Scheduling model in hybrid cloud

MQTS-TC算法首先采用二次聚类的方法对资源进行预处理, 得到不同的聚类;其次将任务按照其Deadline排序, 优先调度时间约束较紧的任务, 这样可以完成更多的任务;最后采用MQTS-TC算法分发任务.该算法优先在私有云上处理用户提交的任务, 若私有资源满足用户的需求, 则在私有云上处理任务, 若私有资源不满足约束条件, 则无法完成的任务需要转移到公有云上执行.

3.3 算法描述

具体的算法流程如下所示, 首先是私有云上的调度算法伪代码.

输入:T=t1, t2, …, tn, R={r1, r2, …, rm}

输出:〈ti, rj, Cprik〉//tirj上执行, rj属于第k个私有资源聚类Cluster, 即rjCprik

1. FuzzyClustering (Rpri)//Rpri$\subset $R

2. FuzzyClustering (Rpub)//Rpub$\subset $R, 通过二次聚类的方法分别对私有资源和公有资源聚类

3. Sort(Cluster)//将私有资源聚类和公有资源聚类按照其综合性能排序

4. SortEarlyDeadlineFirst (T)

5. FOR each tiT

6.    FOR each Cluster Cprik$\subset $Rpri

7.    $\text{time}=\frac{{{t}_{\text{Len}i}}}{{{C}_{\text{priCenterMips}k}}}$ //计算任务在每一个私有聚类的执行时间

8.    END FOR

9.   Cprik←GetClusterType(time)//找到其执行时间最接近于任务Deadline的私有资源聚类

10. END FOR

11. IFCprikexits, THEN

12.    FOR each tiT

13.      FOR each rjCprik

14.IF Ci, j+ESj < =tDLi

15.         assign ti to rj with min task load

16.       ELSE //不能满足任务的Deadline

17.          find a bit better cluster than Cprik and back

      to step 12

18.        END IF

19.      END FOR

20.     END FOR

21.     IF private clusters can not satisfied task ti

22.     schedule it on public clusters

23.    END IF

24. ELSE //私有资源不满足用户约束条件

25.     schedule it on public clusters

26. END IF

其中, 算法第1~3步通过二次聚类方法对资源进行预处理操作, 将聚类资源的综合能力降序排序.第4~10步把任务按照Deadline排序, 首先处理截止时间较短的任务, 将任务匹配到合适的资源聚类类型.第11~26步为每一个任务映射到执行时间最接近该任务截止时间、并且任务负载最少的资源上, 若不满足时间约束条件, 则转移到公有云上调度.

公有云上的调度算法伪代码如下所示:

输入:Tpub$\subset $T, Rpub={Cpub1, Cpub2, …, Cpub c}//Tpub为调度在公有资源上的任务

输出:〈ti, rj, Cpubk〉//tirj上执行, rj属于第k个公有资源聚类Cluster, 即rjCpubk

1. FOR each Cluster ti$\subset $Tpub

2.    FOR each Cluster Cpubk$\subset $Rpub

3.        $\text{time}=\frac{{{t}_{\text{Len}i}}}{{{C}_{\text{priCenter}\ \text{Mips}k}}}+\frac{{{t}_{\text{File}i}}+{{t}_{\text{Out}i}}}{{{C}_{\text{pubCenterBw}}}_{k}}$

4.      END FOR

5.    Cpubk←GetClusterType(time)//找到其执行时间最接近于任务deadline的公有资源聚类

6. END FOR

7. IF Cpubk exists, THEN

8.     FOR each tiTpub

9.      FOR each rjCpubk

10.          IF DTi, j+Ci, j+ESj < =tDLi & &

11.            Costi, j < =tCosti & & tSei < =rSej

12.                    find the resource rj that has the lowest cost

13.           END FOR

14.           assign ti to rj

15.       END FOR

16. ELSE//公有资源无法完成任务调度

17.        refuse to perform the task

18. END IF

其中, 算法1~6步将转移到公有云的任务根据预估传输时间和计算时间匹配到合适的资源聚类类型;第7~18步为任务映射花费最小的资源, 若公有云匹配不到资源, 则该任务完成失败.

4 算法性能评价 4.1 实验环境设置

采用仿真工具CloudSim3.0.3模拟混合云环境, 实验硬件配置为HP Elitedesk800, CPU: i7-4 790, 内存4 GB, 主频为3.6 GHz的计算机, 实验模拟了2个数据中心:私有数据中心和公有数据中心, 分别为30个虚拟节点和200个虚拟节点.虚拟机的各个属性取值范围如表 2所示, 性能不同的虚拟机定价也不同, 如表 3所示, 定价和资源性能好坏成正比.本文将MQTS-TC算法和Greedy算法、AsQ算法[13]相比较, 以获得相对客观的评价.考察不同算法对200到2 000个任务的调度情况, 将3种算法各自独立运行10次, 统计评价标准的平均值.

表 2 混合云资源属性 Table 2 Hybrid cloud resources parameters
表 3 混合云资源定价 Table 3 Hybrid cloud resources prices
4.2 实验结果与分析

合理匹配资源和任务, 减少用户花费, 缩短任务完成时间, 提高系统的工作效率, 同时提高用户满意度是调度的主要目标, 另一方面提高私有资源的利用率也是评价算法性能的一个标准.因此, 主要设置4个评价指标:首先是整体代价, “性价比”一直是用户评价服务的一个强有力的标准;其次是用户的满意度, 主要评价调度算法的有效性及合理性;第三是任务的延迟率, 包括任务的执行时间和完成时间, 用来评价调度算法的工作效率;最后是私有资源的利用率, 转移到公有云的数据量可以间接反映这一指标的变化.实验结果如下所示.

1) 花费.

图 3所示, 随着任务量的增加, 3种算法整体消耗的代价不断增大, MQTS-TC调度算法的费用最低, 原因是该方法在二次聚类基础上, 实现了任务与资源的有效匹配.相比AsQ和Greedy算法, 私有云完成的任务量最多, 减少了公有云执行的任务量, 因此租用公有云的费用就会降低.

图 3 不同算法的执行费用的比较 Fig. 3 Comparison of execution expenses of differentalgorithms

2) 用户的满意度

用户的满意度由完成任务数量占总任务数量的百分比来表示, 记为Ptask.设定任务的截止时间, 整体来看, MQTS-TC调度算法完成的任务数量最多, 如图 4所示.当用户提交2 000个任务时, MQTS-TC算法完成任务约占总任务的96%, 比AsQ算法高7%, 高出Greedy算法5%.图 5(a)图 5(b)的数据分别展示了500个任务和1 200个任务, 任务截止时间由小变大对用户满意度的影响;截止时间越长, 完成的任务越多, MQTS-TC调度算法将最接近任务截止时间的资源聚类与任务进行匹配, 更好地体现了按需分配的原则, 整体的用户满意度最高.

图 4 不同任务量在同一截止时间下的用户满意度 Fig. 4 User satisfaction with different tasks under same deadline
图 5 不同截止时间下的用户满意度 Fig. 5 Users' satisfaction under different deadlines

3) 延迟率.

实验发现, 随着任务数量越来越多, 图 6(a)中3种调度算法的执行时间都呈下降的趋势, 这是因为当数据规模变大时, 公有云的处理能力缩短了整体的任务执行时间Ttask.贪心算法的主要思想就是不断寻找当前完成时间最短的资源, 因而执行速度较快, 但是无法保证整体任务完成时间最短, 如下图 6(b)所示, 贪心算法的任务等待时间是最大的.AsQ算法利用RDI策略更好地实现了负载均衡, 有效减少了任务队列的等待时间;MQTS-TC策略充分利用私有资源来完成任务, 但任务执行时间比较长, 同时私有资源的任务队列长, 任务等待时间比较久;并且在任务与资源匹配时, 总是需要对资源进行预处理, 因此耗时比较长, 但是, 现实中资源预处理工作只需要做一次, 可以大大降低任务的等待时间.总体来看, 随着任务规模的增大, 3种算法的执行时间和等待时间差越来越小, 趋于一致.

图 6 不同任务量的执行时间和等待时间的比较 Fig. 6 Comparison of execution time and waiting time for different tasks

4) 私有资源的利用率.

图 7所示, 数据规模越大, 转移到公有云的任务量Pur就会越大;但在同等条件下, MQTS-TC算法转移到公有云的任务量相对较少, 其私有云完成的任务量超过AsQ算法大约10%, 超过Greedy算法30%左右, 说明MQTS-TC算法的私有云资源利用率最高.

图 7 转移到公有云的任务量 Fig. 7 Amount of task transferred to public cloud
5 结语

理论分析和实验结果表明, 本文提出的算法确保了任务的有效完成时间, 降低了整体的执行耗费, 提高了用户满意度, 同时保证了较高的私有云利用率.本文提出的MQTS-TC算法, 在采用二次聚类方法进行资源预处理的基础上, 首先选择私有资源来执行任务, 只有高负载任务才会被转移到公有资源完成调度.这样就保证了大部分任务在合理匹配的前提下, 能够在私有资源上完成调度, 降低了租用公有云的费用, 同时大大提高了私有资源的利用率.结合多目标需求优先执行截止时间较紧的任务, 保证系统能够在有效时间内完成大量的任务, 提高任务完成的百分比,进一步提高了用户的满意度.本文旨在为混合云环境下资源调度提供一种可行的解决方案, 下一步工作的重点就是提出更有效的调度策略, 缩短任务完成时间, 进一步完善混合云模型, 包括考虑私有云的操作费用、能量消耗等, 更好地提高任务调度的性能.

参考文献
[1] BUYYA R, YEO C S, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: vision, hype, and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems, 2009, 25(6): 599–616. DOI:10.1016/j.future.2008.12.001
[2] ARMBRUST M, FOX A, GRIFFITH R, et al. A view of cloud computing[J]. Communications of the ACM, 2010, 53(4): 50–58. DOI:10.1145/1721654
[3] 刘鹏. 云计算:第3版[M]. 北京: 电子工业出版社, 2015: 1-8.
[4] DILLON T, WU C, CHANG E. Cloud computing: issues and challenges[C]// IEEE International Conference on Advanced Information Networking and Applications. Perth: IEEE, 2010: 27-33.
[5] SINGH S, CHANA I. A survey on resource scheduling in cloud computing: issues and challenges[J]. Journal of Grid Computing, 2016, 14(2): 217–264. DOI:10.1007/s10723-015-9359-2
[6] BITTENCOURT L F, MADEIRA E R M, DA FONSECA N L S. Scheduling in hybrid clouds[J]. IEEE Communications Magazine, 2012, 50(9): 42–47. DOI:10.1109/MCOM.2012.6295710
[7] CHOPRA N, SINGH S. Deadline and cost based workflow scheduling in hybrid cloud[C] // 2013 International Conference on Advances in Computing, Communications and Informatics (ICACCI). Mysore: IEEE, 2013: 840-846.
[8] 云计算趋势: DevOps、Docker、混合云将有大的进步. (2016-04-13)[2016-04-13]. http://www.chinacloud.cn/show.aspxid=23234&cid=14.
[9] VASILE M A, POP F, TUTUEANU R I, et al. Resource-aware hybrid scheduling algorithm in heterogeneous distributed computing[J]. Future Generation Computer Systems, 2015, 51(C): 61–71.
[10] JENNINGS B, STADLER R. Resource management in clouds: survey and research challenges[J]. Journal of Network and Systems Management, 2015, 23(3): 567–619. DOI:10.1007/s10922-014-9307-7
[11] SHIFRIN M, ATAR R, CIDON I. Optimal scheduling in the hybrid-cloud[C] // IFIP/IEEE International Symposium on Integrated Network Management. Ghent: IEEE, 2013: 51-59.
[12] VAN DEN BOSSCHE R, VANMECHELEN K, BROECKHOVE J. Cost-optimal scheduling in hybrid iaas clouds for deadline constrained workloads[C] // 2010 IEEE 3rd International Conference on Cloud Computing (CLOUD). Miami: IEEE, 2010: 228-235.
[13] WANG W J, CHANG Y S, LO W T, et al. Adaptive scheduling for parallel tasks with QoS satisfaction for hybrid cloud environments[J]. The Journal of Supercomputing, 2013, 66(2): 783–811. DOI:10.1007/s11227-013-0890-2
[14] SINGH S, CHANA I. QRSF: QoS-aware resource scheduling framework in cloud computing[J]. The Journal of Supercomputing, 2015, 71(1): 241–292. DOI:10.1007/s11227-014-1295-6
[15] 张敏, 于剑. 基于划分的模糊聚类算法[J]. 软件学报, 2004, 15(6): 858–868.
ZHANG Min, YU Jian. Fuzzy partitional clustering algorithms[J]. Journal of Software, 2004, 15(6): 858–868.
[16] 杜晓丽, 蒋昌俊, 徐国荣, 等. 一种基于模糊聚类的网格DAG任务图调度算法[J]. 软件学报, 2006, 17(11): 2277–2288.
DU Xiao-li, JIANG Chang-jian, XU Guo-rong, et al. A Grid DAG scheduling algorithm based on fuzzy clustering[J]. Journal of Software, 2006, 17(11): 2277–2288.
[17] 陈志刚, 杨博. 网格服务资源多维性能聚类任务调度[J]. 软件学报, 2009, 20(10): 2766–2775.
CHEN Zhi-Gang, YANG Bo. Task scheduling based on multidimensional performance clustering of grid service resources[J]. Journal of Software, 2009, 20(10): 2766–2775.
[18] 李文娟, 张启飞, 平玲娣, 等. 基于模糊聚类的云任务调度算法[J]. 通信学报, 2012, 33(3): 146–154.
LI Wen-juan, ZHANG Qi-fei, PING Ling-di, et al. Cloud scheduling algorithm based on fuzzy clustering[J]. Journal of China Institute of Communications, 2012, 33(3): 146–154.
[19] LI W J, WU J Y, ZHANG Q F, et al. Trust-driven and QoS demand clustering analysis based cloud workflow scheduling strategies[J]. Cluster computing, 2014, 17(3): 1013–1030. DOI:10.1007/s10586-013-0340-1
[20] 江务学, 魏文国, 丁度坤, 等. 异构云环境下基于分簇的云资源感知任务调度方案[J]. 计算机应用研究, 2016, 33(11): 3422–3425.
JIANG Wu-xue, WEI Wen-guo, DING Du-kun, et al. Task scheduling scheme based on clustering in heterogeneous cloud computing platform[J]. Application Research of Computers, 2016, 33(11): 3422–3425.
[21] LIU Z, QU W, LIU W, et al. Resource preprocessing and optimal task scheduling in cloud computing environments[J]. Concurrency and Computation: Practice and Experience, 2015, 27(13): 3461–3482. DOI:10.1002/cpe.v27.13