NSGAⅡ多目标均值聚类的云计算虚拟资源调度研究*

石　慧　李俊杰　谢志明　陈　恩

(1.汕尾职业技术学院　汕尾　516600)(2.汕尾市创新工业设计研究院　汕尾　516600) (3.深圳华为技术有限公司　深圳　518129)



NSGAⅡ多目标均值聚类的云计算虚拟资源调度研究*

石慧1,2李俊杰1,2谢志明1,2陈恩3

(1.汕尾职业技术学院汕尾516600)(2.汕尾市创新工业设计研究院汕尾516600) (3.深圳华为技术有限公司深圳518129)

如何采取有效的方法在海量数据、分布性强并且是复杂变化的资源池中进行资源的有效组织、调度和管理是云计算的关键技术之一。常用的计算机虚拟资源调用方法,往往建模复杂,且数理方程描述困难,求解方法复杂。首先研究了云计算虚拟资源调度问题,构建了以云计算集群的负载均衡、任务平均完成时间和成本开销为评价指标的多目标调度模型,应用带精英策略的非支配集排序遗传算法(NSGAⅡ)进行求解。在该算法中引入K均值聚类(KMC)加快外部种群的聚类过程。实验结果证明了用多目标演化算法进行云计算虚拟资源调度的有效性和可行性。

云计算; 虚拟资源调度; 分布式; 多目标演化算法; 聚类

Class NumberTP393

1　引言

目前,云计算虚拟资源调度方法在动态分配数据中心的物理与虚拟资源方面面临许多挑战:用户需求的实时动态变化很难准确预测;物理与虚拟资源分布较广且分布种类复杂;需要综合考虑系统性能、成本、效益等因素。因此迫切需要高效的资源调度算法,以适应不断增长的业务需求,同时也要考虑虚拟机的动态分配和迁移过程中物理机综合性能评价因素,包括CPU、存储、网络等多方面因素,从而高效地为用户作业分配合适的计算资源。

虽然目前有各种各样的现有算法和方法来解决资源调度问题,但是各种调度算法依赖于任务调度的类型。Shivani等在一篇云计算资源调度的综述文章中提到云计算资源调度的常用启发式算法有:蚁群算法、蜂群算法、优先级算法、装箱算法等,并对这几种算法的总体流程进行了简单介绍[1]。GuiyiWei等提出一种基于博弈论的云资源调度方法,但是该方法对资源分配时的质量并未进行具体量化和计算[2]。Van den Bossche, R.等考虑到资源调度中涉及到的数据中心的利用率、计算成本和调度时间等关键因素的均衡,提出一个二元整数调度模型来进行建模,该方法对公有云的调度比较有效,但对混合云的调度却效率不高[3]。Nedeljko Vasic’等通过建立一个有效的资源评估框架和分类签名方法最大限度减少资源管理开销[4]。Abirami S.P.等提出一个线性规划策略通过衡量任务和资源来解决云计算资源调度问题,却没有深入考虑到其他影响资源调度的因素,诸如时间,资源损耗等,且该策略对资源的利用率还有待提高[5]。陶杰提出一个带赔偿机制的云计算服务拍卖方法来解决云计算资源分配问题,但没有对资源提供方与需求方进行很好的收益优化[6]。朱映映等提出一种动态任务调度算法处理海量数据任务调度问题,但没有进一步分析虚拟化资源调度与分配时间的收益问题[7]。吴恒等提出了一种收益敏感的虚拟资源按需调度方法,来解决虚拟机的资源重配操作耗时问题,但没有深入分析资源分配时的提供方和需求方之间的收益平衡问题[8]。Seematai S等用“偏执”的方法来动态解决云计算数据中心虚拟机分配问题,通过最小化“偏执”能较好地整合不同类型的工作集,并且能提高服务器的资源利用率,并利用启发式算法在提高资源利用率的同时有效地防止系统过载[9]。

本文首先对云计算虚拟资源调度进行分析和建模,设计出一种合理的云计算虚拟资源调度模型。然后在多目标演化算法研究的工作基础上,设计和实现了一种新的基于NSGA-Ⅱ的多目标均值聚类算法(K-NSGA-Ⅱ)对云计算虚拟资源调度过程进行优化。实验结果证明了用多目标演化算法进行云计算虚拟资源调度的有效性和可行性。

2　云计算虚拟资源调度建模

云计算虚拟资源调度过程是:首先用户终端向服务端提交作业任务,服务端在收到作业请求后对任务属性进行分析,并评估当前资源池中资源的综合性能指标,在云计算服务资源池中搜索能满足约束条件资源的节点,并选择最合适的资源节点来完成作业任务。本文的评价指标从云计算集群的负载均衡、任务的平均完成时间和成本开销三个方面进行分析研究,任务调度的主要目标是使这些任务的平均完成时间最短,用户所花费的成本最小,云计算平台的资源能被充分利用。

图1　虚拟资源调度的评价指标

2.1云计算集群的负载均衡

本文综合考虑CPU、内存和带宽这三种资源属性,提出一种负载均衡指标方法,通过计算资源节点的CPU处理能力、内存和网络带宽,对任务分配进行预测分析,并根据预测值对资源进行合理分配,从而有效防止资源失衡。

定义1虚拟资源:用具有一定资源特性的节点表示虚拟资源,第i个虚拟资源节点表示为

Vi=(Vci,Vmi,Vbi)

(1)

其中,参数Vci,Vmi,Vbi表示第i个虚拟机资源的CPU计算能力、内存大小,网络带宽。

定义2任务描述:每个子任务Taskj表示为

Tj=(Cj,Mj,Bi)

(2)

Cj、Mj、Bi分别表示完成任务期望的CPU数目、内存和网络带宽。任务的集合表示为T={T1,T2,T3,…,Tj,…,Tn}。虚拟机集群表示为V={V1,V2,V3,…,Vi,…,Vn}。

定义3任务资源分配矩阵:

(3)

如果将任务i分配到资源j上执行,alji=1,反之,alji=0。

定义4虚拟机资源节点利用率:考虑到的CPU数目、内存和网络带宽,得到虚拟机资源节点利用率如下

(4)

参数q1、q2、q3分别表示CPU数目、内存和网络带宽的权重系数,分别取值为0.7、0.2、0.1。

定义5虚拟机集群的平均资源占用率:

(5)

定义6虚拟机节点资源分配负载情况用虚拟机节点资源分配数标准差函数衡量如下

(6)

分析: 1) 当Vcmb>Vavg,σ(j)的值越大表明资源节点j的负载越重,此时不宜再分配任务给该资源节点,σ(j)的值越小,当前资源节点负载越接近均衡,暂不给该节点分配任务。 2) 当Vcmb

综合以上分析,把基于负载均衡的适应度函数定义为

f1=σ(j)

(7)

2.2任务的平均完成时间

定义7任务的平均完成时间:

云计算数据中心同时向多用户提供服务,本文把虚拟机调度的把平均完成时间作为云计算虚拟资源调度的一个重要因素。用户作业用Taski(i=1,2,…,n)来表示,T(Taski)为调度虚拟机资源执行任务Taski的完成时间。基于任务平均完成时间的适应度函数定义为

(8)

2.3成本开销

定义8成本开销:

云计算虚拟资源调度的成本受很多因素影响,本文主要考虑的因素包括虚拟机的功耗cost、虚拟机迁移消耗F(x)和每台物理机上的成本[10]。

cost=cost1×t

(9)

其中,cost1表示该用户作业选择的虚拟机单位时间价格,t表示该虚拟机工作的时间。

g(x)表示虚拟机迁移总次数,g(x)定义如下

(10)

其中xi∈{0,1},xi=1表示迁移了虚拟机i,xi=0表示没有迁移虚拟机i。

(11)

每台物理机上的成本=启动成本(每次新开一台服务器的成本m0+资源单位时间的成本(cost2)×时间×资源大小M。综合上述三个主要因素,整个成本开销定义为

cost1×t+F(x)+m0+cost2×M×t

(12)

基于成本开销的适应度函数定义为

f3=cost1×t+F(x)+m0+cost2×M×t

(13)

目标函数:通过上述分析,本文的云计算虚拟资源调度优化目标为:负载越均衡越好,任务平均完成时间越少越好,成本开销越少越好。

Fitness={minf1,minf2,minf3}

(14)

3　基于NSGA-Ⅱ多目标均值聚类算法

3.1非支配集排序遗传算法(NSGAⅡ)算法

2000年Deb提出带精英策略的非支配集排序遗传算法(NSGA-Ⅱ)[11]用来求解多目标优化问题,该算法提出了非支配集排序方法,采用拥挤度距离,代替了需要指定共享半径的适应度共享策略,并在快速排序后的同级比较中作为胜出标准,使Pareto域中的个体能扩展到整个Pareto域,并均匀分布,在包含父种群和子种群的交配池中,依照适应度和分布度选择最好的N(种群大小)个体,从而使解有较好的收敛性。

算法1NSGA-Ⅱ算法

REPEATE

随机初始化开始种群p(0),并对p(0)进行非支配排序,初始化每个个体的rank值。

通过二进制锦标赛法从p(t)选择个体,并进行交叉和变异操作,产生新一代种群Q(t)。

计算新种群的目标值。

通过合并P(t)和Q(t)产生出组合种群R(t)。对R(t)进行非支配排序,并通过排挤和精英保留策略选出N个个体,组成新一代种群P(t+1)。

UNTIL直到满足结束条件。

3.2K均值聚类NSGA-Ⅱ算法

聚类是一种重要的数据分析技术,是把群体中的个体集合划分为由类似的个体组成的多个类的过程,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。K-means[12]算法是典型的基于原型的目标函数聚类方法的代表,把数据点到原型的某种距离作为优化的目标函数,利用函数求极值的方法得到迭代运算的调整规则。K-means算法的核心思想是把n个待操作对象划分为k个聚类,使任意的聚类中的元素到其各自聚类的中心平方和最小。由于K-Means算法需要用初始随机种子,不同的随机种子点会有得到完全不同的结果。为了解决这个问题,本文采用K-Mean++算法。

算法2K-means++算法

//选取K个种子点

REPEATE

随机挑个随机点当“种子点”。

对于每个点,计算其和最近的一个“种子点”的距离D(x),并保存在数组中,然后把这些距离加起来得到Sum(D(x))。

再取一个随机值,用权重的方式来取计算下一个“种子点”。

UNTIL直到所有的K个种子点都被选出来。

// K-Means算法

REPEATE

对目标中的所有点求到这K个种子点的距离。假如点Pi离种子点Si最近,那么Pi属于Si点群。

移动种子点到属于它的“点群”的中心。

所有种子点分配完成后,重新计算K个聚类的中心。

与前面计算得到的k个聚类中心比较,检查聚类中心是否发生变化。

UNTIL种子点无法再移动。

输出聚类结果。

3.3基于NSGA-Ⅱ多目标均值聚类算法

考虑到NSGA-Ⅱ算法采用精英策略,可能会导致种群收敛分布不均,降低算法的全局搜索能力。本文在现有的NSGA-Ⅱ算法中引入K-means++聚类技术,新生代子种群进行分类,并根据结果值的优劣分成若干簇。在每一个聚类中随机选择个体进行局部提高,并评估适应度,若新个体的评估值比父个体更优,选择评估值较优的个体替换父个体,并把优秀个体加入当前种群。

算法3K-NSGA-Ⅱ算法

初始化种群

WHILE(终止标准没有达到)DO

执行NSGA-Ⅱ遗传策略(算法1)

执行聚类、个体局部学习提高操作(算法2)

ENDWHILE

4　云计算虚拟资源调度算法设计

算法执行前,先检查资源节点的性能参数是否符合应用需求,把能够与应用需求性能符合的节点组成初始种群,然后设计出符合条件的适应度函数,综合考虑到资源调度效率、系统负载、任务执行时间、成本等因素,本文使用负载函数、任务的平均完成时间和成本开销构成适应度函数。优化策略采用基于NSGA-Ⅱ多目标均值聚类算法(K-NSGA-Ⅱ),该算法主要分为NSGA-Ⅱ遗传操作和聚类、个体局部学习提高操作两个阶段,其随机性保持了个体多样性、也避免搜索陷入局部最优。

4.1云环境下的遗传算法的设计

算法4云环境下的遗传算法的设计

// 初始化

一定范围内随机生成资源节点和任务

IF节点满足任务的最低要求

选择作为初始种群

ENDIF// 开始评

REPEAT

计算适应度函数值

调用K-NSGA-Ⅱ算法获取到任务的最优调度策略(算法3)

UNTIL 终止条件满足

将运行结果返回给用户

4.2编码方案

虚拟资源的调度是求解虚拟机资源映射到用户作业上的可行方案的过程。假设用户作业数N=5,资源池可用的虚拟机数M=8,表1是将用户作业分配到相应的虚拟资源节点的一个方案。解向量(5,7,4,7,4)表示一个作业调度方案,解码得到5号虚拟机分配作业1,7号虚拟机分配作业(2,4),4号虚拟机分配作业(3,5),算法搜索过程中的每个解向量都表示一个潜在的虚拟机分配方案。

表1　用户作业虚拟机节点分配表

5　参数设置与实验分析

本文采用云计算仿真软件CloudSim和编程工具Myeclipse,实验围绕任务的平均完成时间、以资源节点各属性的利用率为构成因素的负载均衡和成本开销等方面分别设定不同的实验条件,将传统优先匹配启发式算法PMH、以任务完成时间为目标的单目标简单遗传算法CGA和本文提出K-NSGA-Ⅱ算法进行对比。

5.1参数设置

实验模拟5个配置相同的数据中心,物理服务器为5台,共部署5～50台虚拟机,模拟多用户提交多任务的资源调度。

1) 数据中心特征参数设置

表2　数据中心参数设置

2) 虚拟机参数设置

表3　虚拟机参数设置

3) 用户任务参数设置

表4　用户任务参数设置

4) 遗传算法的种群规模设为30,演化代数设为500,交叉率、变异率分别设为0.6和0.02。

5.2实验结果与分析

1) 实验一:设定数据中心虚拟资源节点总数为50 ,改变用户提交的任务数(任务数在1000～5000之间),各个算法任务的平均完成时间如图2所示。

图2　改变用户任务数时任务的平均完成时间

2) 实验二:设定用户提交的任务数均为3000,改变数据中心虚拟机资源总数(虚拟机资源总数在5～50之间),各个算法任务的平均完成时间如图3所示。

3) 实验三:设定数据中心虚拟资源节点总数为50 ,任务数为3000,实验中随机选取5个资源节点进行数据采样,分析当前节点的任务分布情况,计算各资源节点的CPU、内存和带宽利用率,得到各资源节点利用率及负载均衡情况如图4～图7所示。

图3　改变数据中心虚拟机资源总数时任务的平均完成时间

图4　CPU利用率

图5　内存利用率

图6　带宽利用率

图7　负载均衡情况

4) 实验四:设定数据中心虚拟资源节点总数为50 ,改变用户提交的任务数(任务数在1000～5000之间),各个算法成本开销情况如图8所示。

图8　成本开销情况

实验一、实验二、实验四对比可以看出,K-NSGA-Ⅱ算法给出的解的平均完成时间和成本开销均显著低于PMH和CGA算法,实验三对比可以看出K-NSGA-Ⅱ算法中各资源节点的CPU、内存和带宽的利用率的波动最小,负载也较为均衡。实验证明K-NSGA-Ⅱ算法是一种有效的云计算虚拟资源调度算法,该算法可以有效地对各资源节点的使用情况进行调节,从而提高数据中心服务器资源的利用率和服务质量。这是因为本文设计的模型把虚拟机资源调度和任务分配合并为一个过程,降低了任务的复杂性,同时考虑到任务调度时的负载均衡情况,提高了数据中心资源利用的效率。

6　结语

云计算虚拟资源调度方法在分配数据中心的物理与虚拟资源上面临许多挑战,本文构建了以云计算集群的平均完成时间、负载均衡和成本开销为评价指标的云计算虚拟资源调度多目标综合评估模型,应用带精英策略的非支配集排序遗传算法(NSGAⅡ)进行求解。在该算法中引入K均值聚类(KMC)加快外部种群的聚类过程。实现结果证明了用多目标演化算法进行云计算虚拟资源调度的有效性和可行性。下一步将继续研究多目标演化算法在动态环境下虚拟资源调度的可行性。

[1] Shivani Sharma, Dhanshri Parihar. A Review on Resource Allocation in Cloud Computing. Sharma et al., International Journal of Advance research[J]. Ideas and Innovations in Technology,2014,1(3):337-341.

[2] WEI Guiyi, ATHANASIOS V, ZHENG Yao, et al. A game- theoretic method of fair resource allocation for cloud computing services[J]. Journal of Supercomputing,2010,54(2):252-269.

[3] Van den Bossche, R., Vanmechelen, K., Broeckhove, J. Cost-Optimal Scheduling in Hybrid IaaS Clouds for Deadline Constrained Workloads. Cloud Computing (CLOUD)[C]//2010 IEEE 3rd International Conference on. 5-10 July 2010:228-235.

[4] 陶杰,顾永跟,吴小红,等.带赔偿的云计算服务拍卖机制研究[J].数学的实践与认识,2013,43(4):117-123

TAO Jie, GU Yonggen, WU Xiaohong, et al. Compensation for Cloud Computing Practice and knowledge service auction mechanism of[J]. Mathematics,2013,43(4):117-123.

[5] 朱映映,陈阳,明仲.云系统中面向海量多媒体数据的动态任务调度算法[J].小型微型计算机系统,2013,34(4):783-788.

ZHU Yingying, CHEN Yang, MING Zhong. Based on massive multimedia data dynamic task scheduling algorithm for[J]. Micro Computer System, Cloud System in,2013,34(4):783-788.

[6] 吴恒,张文博,张建华,等.一种收益敏感的虚拟资源按需提供方[J].软件学报,2013,24(8):1963-1980.

WU Heng, ZHANG Wenbo, ZHANG Jianhua, et al. A virtual resource income sensitive according to the provided Journal of supplier[J]. Software,2013,24(8):1963-1980.

[7] Seematai S. Patil, Koganti Bhavani. Dynamic Resource Allocation using Virtual Machines for Cloud Computing Environment[J]. International Journal of Engineering and Advanced Technology,2014,24(6):1107-1117.

[8] 许波,赵超,等.云计算中虚拟机资源调度多目标优化[J].系统仿真学报,2014,3:592-595.

XU Bo, ZHAO Chao, et al. The multi-objective optimization[J]. Journal of System Simulation of Cloud Computing Resource Scheduling of virtual Machine,2014,3:592-595.

[9] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transaction on Evolutionary Computation,2002,6(2):182-197.

[10] 许波,赵超,等.云计算中虚拟机资源调度多目标优化[J].系统仿真学报,2014,3:592-595.

XU Bo, ZHAO Chao, et al. The multi-objective optimization[J]. Journal of System Simulation of Cloud Computing Resource Scheduling of Virtual Machine,2014,3:592-595.

[11] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transaction on Evolutionary Computation,2002,6(2):182-197.

[12] MacQueen, JB. Some Methods for Classification and Analysis of Multivariate Observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, USA: University of California Press,1967.

Cloud Computing Virtual Resource Scheduling Based on NSGA-Ⅱ Multi Object Clustering

SHI Hui1,2LI Junjie1,2XIE Zhiming1,2CHEN En3

(1. Shanwei Vocational Technical College, Shanwei516600)(2. Shanwei Innovation Industrial Design &Research Institute, Shanwei516600)(3. HUAWEI Technology Co., Ltd., Shenzhen518129)

How to take effective algorithms in the massive data, distributed and complex changes in the resource pool to organize, dispatch and manage resource effectively is one of the key technologies of cloud computing. Commonly used computer virtual resource calling algorithms often have complex modeling, and mathematical equations describing is difficult, solution method is complex. In this paper, the problem of virtual resource scheduling in cloud computing is studied, and a multi objective scheduling model is constructed based on the load balancing, task completion time and cost. NSGAⅡ is applied to solution in this algorithm, K means clustering (KMC) is introduced to speed up the clustering process of the external population. The results prove the effectiveness and feasibility of the virtual resource scheduling in cloud computing based on multi-objective evolutionary algorithm.

cloud computing, virtual resource scheduling, distributed, multi objective evolutionary algorithm, clustering

2016年3月10日,

2016年4月20日

2014年度广东省高职高专云计算与大数据专业委员会项目(编号:GDYJSKT14-02;GDYJSKT14-09);2015年度广东省信息技术教指委教改项目(编号:XXJZW2015002)资助。

石慧,女,硕士,讲师,研究方向:云计算与大数据。李俊杰,男,硕士,讲师,研究方向:云计算与大数据。谢志明,男,硕士,讲师,研究方向:云计算与大数据。陈恩,男,高级工程师,研究方向:云计算与大数据。

TP393DOI:10.3969/j.issn.1672-9722.2016.09.012