云计算中基于模糊聚类的资源调度的应用研究

王小军，王　运，郝　喆

云计算中基于模糊聚类的资源调度的应用研究

王小军，王运，郝喆

目前大多数云计算数据中心在资源分配过程中没有充分考虑作业的性能代价问题，采用一种改进的云计算资源分配策略，建立并行任务性能代价模型，利用改进的模糊聚类算法(CBFCM Cost-Based Fuzzy Clustering Algorithm)对云计算资源集进行分组，根据用户服务等级USL进行调度，采用四种资源调度算法进行分析。实验结果表明，采用CBFCM算法对云计算资源进行分类后，AFCFS算法与其他算法相比，可以减少作业响应时间和作业等待时间。

云计算；并行任务；模糊聚类；性能代价

云计算是在网格计算、并行计算、虚拟化技术等技术的基础上发展成的一种可配置的资源共享池技术，具有按需服务、广泛的网络接入、资源共享、弹性计算、服务可度量的特征。[1]根据Berkeley对云计算模型的定义，可以分为IAAS、PAAS、SAAS三层结构。目前云计算中关注的热点主要包括提高资源利用率、节约能源、降低运行成本、云计算安全等。[2]

一、相关研究

云计算服务本质是并行任务处理，为了提供廉价优质的按需服务，高效的任务调度是关键，总体而言并行调度策略可以分为基于优先级的调度、基于分组的调度、基于复制的调度三种。[3]基于优先级的调度为任务分配一个优先级，根据优先级给任务分配资源，基于分组的调度尽可能将资源需求类似的任务分配到一个分组，以组为单位分配资源，减少处理器间通信消耗。基于复制的调度TDS[4]利用处理器的空闲时间复制前驱任务，避免某些前驱任务的通信数据传输，从而减少传输延迟。因此，云计算中任务调度的目的都是对任务相关资源的合理分配，降低集群系统能耗，提高系统资源的利用率。

传统的并行分布式系统调度模型基于优先级的任务调度方法有最大最小(Max-Min)算法、贪心(greedy)算法、遗传算法、蚁群算法等，上述方法以最小化作业完成时间为目标，但没有充分考虑服务提供商和用户的QOS(Quality Of Service)需求，如代价成本、资源利用率等因素，导致在资源按组分配中，资源的选择开销大、分配存在经验性。

文献5和6对集群资源关键属性进行聚类分析，通过任务节点的迁移，实现计算的负载均衡，但其没有考虑任务的代价和偏好。为了兼顾云计算中资源关键属性划分和任务的偏好，文献7和8基于两级调度模式的任务调度策略，采用模糊聚类的方法根据集群资源聚类结果和任务偏好，最大限度体现调度公平性，有助于减少问题的规模性，但其没有考虑任务的性能和代价模型，无法满足SLA(Service-Level Agreement)服务质量要求。

为了提高集群资源的利用率，满足SLA服务质量要求，建立并行任务代价模型，采用CBFCM(Cost-Based Fuzzy Clustering Algorithm)算法，根据集群资源的等级和任务的性能代价进行分类，满足用户QOS的前提下，提高资源的利用率。一方面描述了云计算中并行任务的代价模型和任务处理流程；另一方面利用改进的模糊聚类算法CBFCM对资源进行分组，根据任务代价参数，对任务进行调度，有利于满足服务双方的各自需求。

二、模型描述

1.用户模型

用户是根据服务等级租用云服务，提交任务的实体。用户集合可以表示为Users={U1,U2,…,Um}，其中Ui表示一个租用云服务的实体，可以表示如下的六元组：

Ui

Uid是云服务中对用户实体的唯一标记；

Uname是对用户实体的友好描述；

USL(User Service Level)表示用户的服务等级，SL(Service Level)标识提供给用户的资源类型，SL={Golden,Silver,Copper}，该参数与用户计费相关；

UJobs是用户提交作业的集合，作业集合表示为Jobs={job1,job2,…,jobj}；

Upos表示用户的地理位置；

Usec表示用户数据的安全等级需求。

2.任务模型

为了描述任务模型，做如下假定：云计算中的并行作业由多个不断互相通信的任务组成，每一个任务独占一个虚拟机VM资源，作业调度过程中尽可能保证所有任务并行执行，防止任务阻塞，最小化作业运行时间。

Ui提交的作业集合可以表示为Jobs={job1,job2,…,jobn}，其中作业jobj可以用六元组表示

Jid表示服务提供商分配给jobj的全局唯一标识；

Jtyps表示作业的类别，根据作业中任务集合的大小分为小作业small job和大作业large job，如下所示：

Jtype={smallJlen∈[1,12],Jtype={largeJlen∈[13,24]}

Jlen表示作业中任务集大小，Jlen=Jtasks;

Jtasks表示作业中的任务集合

Jtasks={Task1,Task2,…,Taskk}

Jres表示作业运行所需要的最小的资源集。

为了考虑作业的代价和性能，在六元组中引入Jart表示作业的平均响应时间(Average Response Time)(定义1)，表示作业进入调度队列直到作业运行结束的时间。Jawt表示作业的平均等待时间(Average Wait Time)(定义2)，表示作业进入调度队列到作业分配到资源开始运行的时间。

3.资源模型

云计算中的资源是服务商提供的共享可配置的计算资源(如网络、服务器、存储、应用和服务等)。资源模型表示为Resource={r1,r2,…,rp}，资源总数p=Resource，其中rk可以用八元组表示

rk=

Rid表示资源的唯一编号；

Rsupply表示资源的提供商；

Rtype表示资源类型，与USL满足关系(USL∈Rtype)，根据用户的服务等级，选择与之对应的资源类型。

Rcomp表示资源的处理能力，采用MHz为计量单位；

Rmem表示资源可提供的内存，采用MB为计量单位；

Rstor表示资源的存储能力，采用GB为计量单位；

Rio表示资源的交换能力，采用Gb为计量单位；

Rnet表示资源的网络带宽，采用MB为计量单位；

Rpos表示资源的地理位置信息。

三、CBFCM算法(Cost-Based Fuzzy Clustering Algorithm)

1.FCM(Fuzzy Clustering Algorithm)模糊聚类算法

设X={x1,x2,…,xn}是n个需要聚类的资源，其中每个资源Xi有m个属性,用向量Xj={xj1,xj2,…,xjm}表示，则X={xj|xj=(xj1,xj2,…,xjm),1≤j≤n}表示为数据空间。[9-11]

FCM模糊聚类算法根据n个资源数据点xj对c个不同类中心ωi的隶属度，对目标函数反复迭代获得最优划分。

(1)

2.CBFCM模糊聚类算法

FCM算法中，资源数据点Xj与类中心ωi的隶属度满足如下关系：

∑ci=1uij=1,uij∈(0,1)

(2)

但是类中心ωi与各资源点xj之间的距离关系无法描述，为此引入了加权因子Mij表示相对于同一个类中心ωi与各资源点Xj之间的距离远近程度。

对于同一个类中心ωi，Mi满足如下关系：

Mi=∑nj=1uij(Mi>0)

(3)

加权因子Mij,表示如下：

引入加权因子Mij的欧几里得距离公式如下：

(4)

新的目标函数如下：

(5)

聚类中心vi的更新公式由于加权因子Mij相互抵消，与FCM一致：

(6)

隶属度更新公式为：

(7)

3.CBFCM算法流程

假设资源集合Resources={R1,R2,…,Rk}，是云计算服务提供商提供的硬件资源，根据Rtype分为不同的资源池，对不同的资源池采用改进的CBFCM算法进行分类，其算法流程如下：

(1)设置初始化参数，给出初始聚类中心ω={ω1,ω2,…,ωc},迭代次数l=0，最大迭代数为T，阈值为ε，平滑指数m=2；

CBFCM算法对不同Rtype资源进行聚类分析时候，提取rk的6个关键属性，考虑了同一个类中心ωi与各资源点Xj之间的距离远近程度，引入加权因子Mij，对资源之间的欧几里得距离进行放大，在加速聚类的同时，也节省了服务器提供商的运行成本，提高资源分配目的性和利用率。

4.CBFCM聚类有效性分析

依据模糊集理论中可能性分布概念，为了分析模糊聚类的有效性，可以采用基于可能性分布的聚类有效性函数的方法，对于给定的聚类中心数c和隶属度U，划分系数定义为：

(8)

可能性划分系数定义为：

(9)

聚类有效性函数定义为：

FP(U;c)=F(U;c)-P(U;c)

(10)

若存在(U*;c*)满足FP(U*;c*)=minc{minΩcFP(U;c)}，则以(U*;c*)为最优的有效性聚类。

根据上述聚类有效性函数定义，通过对指数m不同取值的情况下，CBFCM和FCM算法的有效性函数进行分析，可以得出最优的资源分类数。

四、作业调度

1.调度流程

云计算服务使用过程中，用户向云服务提供商提交并行作业集，在云端其资源聚类和作业调度流程如图1所示。

云计算服务模型中，资源是以虚拟机VM的形式提供终端用户的并行作业使用，资源聚类过程是依据用户服务级别USL，定义资源的类型为金、银、铜、普通四个级别，根据资源rk的6个关键属性Rcomp、Rmem、Rstor、Rio、Rnst、Rpos，采用CBFCM算法，对资源进行分类，并将分类结果标记到Rtyps中，同时将资源分别放入不同级别的资源集中，提供给资源调度进程DR(Dispatching Resource)调度并行作业使用，作业中的每一个任务独占一个资源(VM)。

图1　云计算资源聚类和作业调度流程

图1中作业调度流程如下，云计算用户将并行作业Jobs提交给服务提供商SP，服务提供商根据用户的服务级别USL，将Jobs添加到与USL对应的作业队列Job Queue。资源调度进程DR，选用不同的调度算法，将Job Queue中的作业调度到由VM组成的资源集中进行运行，如果资源集中空闲VM的数量大于当前作业中任务数Jlen，则当前作业可立即执行，否则该作业进入等待状态，直到其他作业完成，提供足够多的空闲VM资源时，当前任务才能调度进入执行状态。当等待状态的队列长度大于上限阈值时，SP可以租用更多的资源VM投入到资源集中，保障用户的服务等级。

2.调度算法

资源调度进程DR，采用的调度算法包括先来先服务FCFS(First Come First Served)、小作业优先SJFS(Small Job First Served)、大作业优先LJFS(Large Job First Served)、自适应先来先服务AFCFS(Adaptive First Come First Served)四种资源调度算法，其资源调度算法描述如下所示。

算法1先来先服务调度算法FCFS

输入：当前调度的作业队列job queue

输出：当前队列中首个顺序可执行作业

Begin

∥对job queue按照作业进入队列先后排序

jobsList = getJobsList(job queue)

for each job in jobsList

∥判断空闲资源VM时候满足当前job的需求

bool check = checkifJobCanBeExecuted(job)

if check then return job

else continue；

end if

end for

End

算法2小作业优先算法SJFS

输入：当前调度的作业队列job queue

输出：当前队列中最小的可执行作业

Begin

∥对job queue按照作业由小到大排序

jobsList = getJobsListBySizeIncremental(job queue)

∥判断空闲资源VM时候满足当前job的需求

bool check = checkifJobCanBeExecuted(job)

if check then return job

else return null;∥当前队列没有可执行的作业

end if

End

算法3大作业优先调度算法LJFS

输入：当前调度的作业队列job queue

输出：当前队列中最大的可执行作业

Begin

∥对job queue按照作业由大到小排序

jobsList=getJobsListBySizeDecremental(job queue)

for each job in jobsList do

∥判断空闲资源VM时候满足当前job的需求

bool check = checkifJobCanBeExecuted(job)

if check then return job

else continue;

end if

end for

End

在上述三种调度算法中，FCFS考虑了作业的顺序与调度的关系，SJFS、LJFS考虑了作业的大小与调度的关系，对于空闲资源VM的数量与作业调度的关系没有关注，AFCFS算法考虑了空闲资源VM的数量与当前调度作业任务集关系，在空闲资源VM有限的情况下，优先考虑空闲资源数量与作业任务集相当的作业进行调度，进一步提高空闲碎片资源的利用率。

算法4自适应先来先服务算法AFCFS

输入：当前调度的作业队列job queue

输出：当前队列中自适应空闲资源的可执行作业

Begin

jobsList = getJobsList(job queue)

freeVMsListSize = getFreeVmsListSize()

for each job in jobList

if(freeVmsListSize-job.len)∈[0,β]&&

checkifJobCanBeExecuted(job)then

∥如果作业长度与空闲资源小于阈值β，则该资源为自适应候选资源

return job

else continue;

end if

end for

End

3.性能分析

为了对云计算中资源调度算法进行分析，定义参数p表示作业Jtype=small所占的比例，作业平均负载JAL(Jobs Average Load)表示为JAL=p(1+12)/2+(1-p)(13+24)/2。

参数q表示可以同时调度进入资源集的作业的数量，由于作业中每个并行任务独占一个资源VM，因此参数满足下列条件q≤Resourcemax/JAL，假设资源集的大小为60VM，参数p=0.5，最多同时调度进入资源池的作业为q=4.8，表示最多同时调度作业的数量不能超过4.8。

其他作业调度性能相关定义如下。

定义1：作业平均响应时间ART(Average Response Time)

ART=∑nj=1rjN

定义2：作业平均等待时间

AWT=∑nj=1wjN

定义3：虚拟服务器租用时间LT(Lease Time)

LT=∑qi=1Tlease(i)

其中，LT表示租用虚拟机的总时间，假设累计租用q台虚拟机，Tlease(i)为VMi的租用时间。

定义4：作业运行代价(Job Cost Price)

Cost=∑qi=1Tlease(i)×pricei

pricei=(αusl+βpos)×pricebase

作业的运行代价由使用资源时间和资源VM的单价决定，资源VM单价由参数资源的地理位置βpos、资源的用户级别αusl，以及资源的基础定价决定。

五、实验仿真

实验仿真中硬件环境采用虚拟化平台提供并行作业运行所需要的虚拟机资源，虚拟化平台采用VMware Vsphere 5.1虚拟化软件、VMware Vcloud Automation Center 6.0云计算管理软件，6台服务器刀片，提供计算资源VM60个，资源根据6个关键属性，对资源集采用CBFCM算法和标准FCM算法进行分类处理，并标记为分类的资源类型，通过聚类有效性函数(公式10)，可以得出当分类数为3时，函数值取值最小，分类数为3是最优的划分数。同时FCM和CBFCM算法的迭代次数和分类正确性进行统计，如表1所示。

表1　FCM和CBFCM算法性能分析

通过表1不难发现，CBFCM算法与FCM算法在资源的分类中的性能对比，CBFCM具有较大的优势，同时也为云计算服务模型中用户服务等级的划分，提供较好的划分依据。

对作业调度算法的性能分析，定义参数p=0.5，也就是调度中大小作业的比例均等，在四种调度算法中，选取代表性的三类算法FCFS、LJFS、SFCFS，对作业平均响应时间ART、平均等待时间AWT和作业平均运行代价ACP三个性能指标进行试验分析，分析结果如图2-4所示。

图2　算法平均响应时间对比

图3　算法平均等待时间对比

图4　作业平均运行代价对比

通过图2、图3的分析可以发现，AFCFS在作业调度的ART和AWT性能上，都占有较大的优势，其中算法LJFS和AFCFS性能相差不大，FCFS在作业调度上性能较差，不推荐使用。图4中作业运行代价中，AFCFS算法在参数q取值3.5时，取得最优值，表明随着同时进入资源集作业数量的增加，平均运行代价ACP会先降低再升高，ACP最优取值与参数p和资源集的大小相关。

六、总　结

笔者围绕云计算数据中心资源分配过程中作业的性能代价问题，提出了一种新的云计算资源分配策略，在建立并行任务性能代价模型的基础上，利用改进的模糊聚类算法(CBFCM Cost-Based Fuzzy Clustering Algorithm)对云计算资源集依据用户服务等级USL进行分组，并对作业采用四种不同的调度算法FCFS、SJFS、LJFS、AFCFS进行分析。通过实验表明，在云计算资源分类的应用中，CBFCM算法在迭代次数和分类正确性方面有较大的优势，AFCFS作业调度算法在平均响应时间ART、平均等待时间AWT、平均运行代价ACP性能指标中，较其他三个算法有较大的优势。通过实验可以发现，基于CBFCM资源分类和作业调度的策略在云计算服务中有一定的优势。

[1]林伟伟，齐德昱.云计算资源调度研究综述[J].计算机科学，2012(10):1-6.

[2]许力,曾智斌,姚川.云计算环境中虚拟资源分配优化策略研究[J].通信学报,2012(Z1):9-16.

[3]李新，贾智平，鞠雷.一种面向同构集群系统的并行任务节能调度优化方法[J].计算机学报，2012(3):591-602.

[4]薛景文,田玉玲.基于改进克隆选择算法的云计算任务调度算法[J].计算机应用与软件,2013(5):167-170.

[5]姚婧，何聚厚.基于模糊聚类分析的云计算负载均衡策略[J].计算机应用.2012(1):213-217.

[6]李文娟，张启飞，平玲娣.基于模糊聚类的云任务调度算法[J].通信学报，2012(3):146-154.

[7]戴炳荣,宋俊典,钱俊玲.云计算环境下海量分布式数据处理协同机制的研究[J].计算机应用与软件,2013(1):107-110.

[8]王登科,李忠.基于粒子群优化与蚁群优化的云计算任务调度算法[J].计算机应用与软件,2013(1):290-293.

责任编辑张军涛

On the Application of Resource Scheduling Based on Fuzzy Clustering in Cloud Computing

WANGXiao-jun,WANGYun,HAOZhe/JiangsuOpenUniversity

At present, most cloud computing data centers have not taken into full account the performance costs of assignment in the process of the resource allocation. This paper took a modified resource allocation strategy of cloud computing, set up a performance cost model of parallel task, grouped the resource set of cloud computing by using the improved Fuzzy Clustering Algorithm (CBFCM Cost—based Fuzzy Clustering Algorithm) , scheduled according to the users service level, and analyzed by means of four different scheduling algorithms. The result shows that compared with the other algorithms, AFCFS can shorten the response time and the waiting time of assignment, once CBFCM is used in the resource grouping of cloud computing.

cloud computing；parallel task；fuzzy clustering；performance cost

G434 ∶TP301.6

A

2095-6576(2015)03-0026-06

2015-04-21

王小军，江苏开放大学信息化建设处高级工程师，理学硕士,主要从事计算机应用、网络学习研究。(wangxj@jsou.cn)

江苏开放大学“十二五”规划2013年度课题“个性化推荐系统在网络教学中的应用研究”(13SEW-Q-052)；国家开放大学2014-2015年度青年课题“个性化推荐系统在移动学习中的应用研究”(G14A1401Q)