王小軍，王　運，郝　喆

云計算中基于模糊聚類的資源調度的應用研究

王小軍，王運，郝喆

目前大多數(shù)云計算數(shù)據(jù)中心在資源分配過程中沒有充分考慮作業(yè)的性能代價問題，采用一種改進的云計算資源分配策略，建立并行任務性能代價模型，利用改進的模糊聚類算法(CBFCM Cost-Based Fuzzy Clustering Algorithm)對云計算資源集進行分組，根據(jù)用戶服務等級USL進行調度，采用四種資源調度算法進行分析。實驗結果表明，采用CBFCM算法對云計算資源進行分類后，AFCFS算法與其他算法相比，可以減少作業(yè)響應時間和作業(yè)等待時間。

云計算；并行任務；模糊聚類；性能代價

云計算是在網(wǎng)格計算、并行計算、虛擬化技術等技術的基礎上發(fā)展成的一種可配置的資源共享池技術，具有按需服務、廣泛的網(wǎng)絡接入、資源共享、彈性計算、服務可度量的特征。[1]根據(jù)Berkeley對云計算模型的定義，可以分為IAAS、PAAS、SAAS三層結構。目前云計算中關注的熱點主要包括提高資源利用率、節(jié)約能源、降低運行成本、云計算安全等。[2]

一、相關研究

云計算服務本質是并行任務處理，為了提供廉價優(yōu)質的按需服務，高效的任務調度是關鍵，總體而言并行調度策略可以分為基于優(yōu)先級的調度、基于分組的調度、基于復制的調度三種。[3]基于優(yōu)先級的調度為任務分配一個優(yōu)先級，根據(jù)優(yōu)先級給任務分配資源，基于分組的調度盡可能將資源需求類似的任務分配到一個分組，以組為單位分配資源，減少處理器間通信消耗?；趶椭频恼{度TDS[4]利用處理器的空閑時間復制前驅任務，避免某些前驅任務的通信數(shù)據(jù)傳輸，從而減少傳輸延遲。因此，云計算中任務調度的目的都是對任務相關資源的合理分配，降低集群系統(tǒng)能耗，提高系統(tǒng)資源的利用率。

傳統(tǒng)的并行分布式系統(tǒng)調度模型基于優(yōu)先級的任務調度方法有最大最小(Max-Min)算法、貪心(greedy)算法、遺傳算法、蟻群算法等，上述方法以最小化作業(yè)完成時間為目標，但沒有充分考慮服務提供商和用戶的QOS(Quality Of Service)需求，如代價成本、資源利用率等因素，導致在資源按組分配中，資源的選擇開銷大、分配存在經(jīng)驗性。

文獻5和6對集群資源關鍵屬性進行聚類分析，通過任務節(jié)點的遷移，實現(xiàn)計算的負載均衡，但其沒有考慮任務的代價和偏好。為了兼顧云計算中資源關鍵屬性劃分和任務的偏好，文獻7和8基于兩級調度模式的任務調度策略，采用模糊聚類的方法根據(jù)集群資源聚類結果和任務偏好，最大限度體現(xiàn)調度公平性，有助于減少問題的規(guī)模性，但其沒有考慮任務的性能和代價模型，無法滿足SLA(Service-Level Agreement)服務質量要求。

為了提高集群資源的利用率，滿足SLA服務質量要求，建立并行任務代價模型，采用CBFCM(Cost-Based Fuzzy Clustering Algorithm)算法，根據(jù)集群資源的等級和任務的性能代價進行分類，滿足用戶QOS的前提下，提高資源的利用率。一方面描述了云計算中并行任務的代價模型和任務處理流程；另一方面利用改進的模糊聚類算法CBFCM對資源進行分組，根據(jù)任務代價參數(shù)，對任務進行調度，有利于滿足服務雙方的各自需求。

二、模型描述

1.用戶模型

用戶是根據(jù)服務等級租用云服務，提交任務的實體。用戶集合可以表示為Users={U1,U2,…,Um}，其中Ui表示一個租用云服務的實體，可以表示如下的六元組：

Ui

Uid是云服務中對用戶實體的唯一標記；

Uname是對用戶實體的友好描述；

USL(User Service Level)表示用戶的服務等級，SL(Service Level)標識提供給用戶的資源類型，SL={Golden,Silver,Copper}，該參數(shù)與用戶計費相關；

UJobs是用戶提交作業(yè)的集合，作業(yè)集合表示為Jobs={job1,job2,…,jobj}；

Upos表示用戶的地理位置；

Usec表示用戶數(shù)據(jù)的安全等級需求。

2.任務模型

為了描述任務模型，做如下假定：云計算中的并行作業(yè)由多個不斷互相通信的任務組成，每一個任務獨占一個虛擬機VM資源，作業(yè)調度過程中盡可能保證所有任務并行執(zhí)行，防止任務阻塞，最小化作業(yè)運行時間。

Ui提交的作業(yè)集合可以表示為Jobs={job1,job2,…,jobn}，其中作業(yè)jobj可以用六元組表示

Jid表示服務提供商分配給jobj的全局唯一標識；

Jtyps表示作業(yè)的類別，根據(jù)作業(yè)中任務集合的大小分為小作業(yè)small job和大作業(yè)large job，如下所示：

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

Jlen表示作業(yè)中任務集大小，Jlen=Jtasks;

Jtasks表示作業(yè)中的任務集合

Jtasks={Task1,Task2,…,Taskk}

Jres表示作業(yè)運行所需要的最小的資源集。

為了考慮作業(yè)的代價和性能，在六元組中引入Jart表示作業(yè)的平均響應時間(Average Response Time)(定義1)，表示作業(yè)進入調度隊列直到作業(yè)運行結束的時間。Jawt表示作業(yè)的平均等待時間(Average Wait Time)(定義2)，表示作業(yè)進入調度隊列到作業(yè)分配到資源開始運行的時間。

3.資源模型

云計算中的資源是服務商提供的共享可配置的計算資源(如網(wǎng)絡、服務器、存儲、應用和服務等)。資源模型表示為Resource={r1,r2,…,rp}，資源總數(shù)p=Resource，其中rk可以用八元組表示

rk=

Rid表示資源的唯一編號；

Rsupply表示資源的提供商；

Rtype表示資源類型，與USL滿足關系(USL∈Rtype)，根據(jù)用戶的服務等級，選擇與之對應的資源類型。

Rcomp表示資源的處理能力，采用MHz為計量單位；

Rmem表示資源可提供的內存，采用MB為計量單位；

Rstor表示資源的存儲能力，采用GB為計量單位；

Rio表示資源的交換能力，采用Gb為計量單位；

Rnet表示資源的網(wǎng)絡帶寬，采用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}表示為數(shù)據(jù)空間。[9-11]

FCM模糊聚類算法根據(jù)n個資源數(shù)據(jù)點xj對c個不同類中心ωi的隸屬度，對目標函數(shù)反復迭代獲得最優(yōu)劃分。

(1)

2.CBFCM模糊聚類算法

FCM算法中，資源數(shù)據(jù)點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)

新的目標函數(shù)如下：

(5)

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

(6)

隸屬度更新公式為：

(7)

3.CBFCM算法流程

假設資源集合Resources={R1,R2,…,Rk}，是云計算服務提供商提供的硬件資源，根據(jù)Rtype分為不同的資源池，對不同的資源池采用改進的CBFCM算法進行分類，其算法流程如下：

(1)設置初始化參數(shù)，給出初始聚類中心ω={ω1,ω2,…,ωc},迭代次數(shù)l=0，最大迭代數(shù)為T，閾值為ε，平滑指數(shù)m=2；

CBFCM算法對不同Rtype資源進行聚類分析時候，提取rk的6個關鍵屬性，考慮了同一個類中心ωi與各資源點Xj之間的距離遠近程度，引入加權因子Mij，對資源之間的歐幾里得距離進行放大，在加速聚類的同時，也節(jié)省了服務器提供商的運行成本，提高資源分配目的性和利用率。

4.CBFCM聚類有效性分析

依據(jù)模糊集理論中可能性分布概念，為了分析模糊聚類的有效性，可以采用基于可能性分布的聚類有效性函數(shù)的方法，對于給定的聚類中心數(shù)c和隸屬度U，劃分系數(shù)定義為：

(8)

可能性劃分系數(shù)定義為：

(9)

聚類有效性函數(shù)定義為：

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

(10)

若存在(U*;c*)滿足FP(U*;c*)=minc{minΩcFP(U;c)}，則以(U*;c*)為最優(yōu)的有效性聚類。

根據(jù)上述聚類有效性函數(shù)定義，通過對指數(shù)m不同取值的情況下，CBFCM和FCM算法的有效性函數(shù)進行分析，可以得出最優(yōu)的資源分類數(shù)。

四、作業(yè)調度

1.調度流程

云計算服務使用過程中，用戶向云服務提供商提交并行作業(yè)集，在云端其資源聚類和作業(yè)調度流程如圖1所示。

云計算服務模型中，資源是以虛擬機VM的形式提供終端用戶的并行作業(yè)使用，資源聚類過程是依據(jù)用戶服務級別USL，定義資源的類型為金、銀、銅、普通四個級別，根據(jù)資源rk的6個關鍵屬性Rcomp、Rmem、Rstor、Rio、Rnst、Rpos，采用CBFCM算法，對資源進行分類，并將分類結果標記到Rtyps中，同時將資源分別放入不同級別的資源集中，提供給資源調度進程DR(Dispatching Resource)調度并行作業(yè)使用，作業(yè)中的每一個任務獨占一個資源(VM)。

圖1　云計算資源聚類和作業(yè)調度流程

圖1中作業(yè)調度流程如下，云計算用戶將并行作業(yè)Jobs提交給服務提供商SP，服務提供商根據(jù)用戶的服務級別USL，將Jobs添加到與USL對應的作業(yè)隊列Job Queue。資源調度進程DR，選用不同的調度算法，將Job Queue中的作業(yè)調度到由VM組成的資源集中進行運行，如果資源集中空閑VM的數(shù)量大于當前作業(yè)中任務數(shù)Jlen，則當前作業(yè)可立即執(zhí)行，否則該作業(yè)進入等待狀態(tài)，直到其他作業(yè)完成，提供足夠多的空閑VM資源時，當前任務才能調度進入執(zhí)行狀態(tài)。當?shù)却隣顟B(tài)的隊列長度大于上限閾值時，SP可以租用更多的資源VM投入到資源集中，保障用戶的服務等級。

2.調度算法

資源調度進程DR，采用的調度算法包括先來先服務FCFS(First Come First Served)、小作業(yè)優(yōu)先SJFS(Small Job First Served)、大作業(yè)優(yōu)先LJFS(Large Job First Served)、自適應先來先服務AFCFS(Adaptive First Come First Served)四種資源調度算法，其資源調度算法描述如下所示。

算法1先來先服務調度算法FCFS

輸入：當前調度的作業(yè)隊列job queue

輸出：當前隊列中首個順序可執(zhí)行作業(yè)

Begin

∥對job queue按照作業(yè)進入隊列先后排序

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小作業(yè)優(yōu)先算法SJFS

輸入：當前調度的作業(yè)隊列job queue

輸出：當前隊列中最小的可執(zhí)行作業(yè)

Begin

∥對job queue按照作業(yè)由小到大排序

jobsList = getJobsListBySizeIncremental(job queue)

∥判斷空閑資源VM時候滿足當前job的需求

bool check = checkifJobCanBeExecuted(job)

if check then return job

else return null;∥當前隊列沒有可執(zhí)行的作業(yè)

end if

End

算法3大作業(yè)優(yōu)先調度算法LJFS

輸入：當前調度的作業(yè)隊列job queue

輸出：當前隊列中最大的可執(zhí)行作業(yè)

Begin

∥對job queue按照作業(yè)由大到小排序

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

在上述三種調度算法中，F(xiàn)CFS考慮了作業(yè)的順序與調度的關系，SJFS、LJFS考慮了作業(yè)的大小與調度的關系，對于空閑資源VM的數(shù)量與作業(yè)調度的關系沒有關注，AFCFS算法考慮了空閑資源VM的數(shù)量與當前調度作業(yè)任務集關系，在空閑資源VM有限的情況下，優(yōu)先考慮空閑資源數(shù)量與作業(yè)任務集相當?shù)淖鳂I(yè)進行調度，進一步提高空閑碎片資源的利用率。

算法4自適應先來先服務算法AFCFS

輸入：當前調度的作業(yè)隊列job queue

輸出：當前隊列中自適應空閑資源的可執(zhí)行作業(yè)

Begin

jobsList = getJobsList(job queue)

freeVMsListSize = getFreeVmsListSize()

for each job in jobList

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

checkifJobCanBeExecuted(job)then

∥如果作業(yè)長度與空閑資源小于閾值β，則該資源為自適應候選資源

return job

else continue;

end if

end for

End

3.性能分析

為了對云計算中資源調度算法進行分析，定義參數(shù)p表示作業(yè)Jtype=small所占的比例，作業(yè)平均負載JAL(Jobs Average Load)表示為JAL=p(1+12)/2+(1-p)(13+24)/2。

參數(shù)q表示可以同時調度進入資源集的作業(yè)的數(shù)量，由于作業(yè)中每個并行任務獨占一個資源VM，因此參數(shù)滿足下列條件q≤Resourcemax/JAL，假設資源集的大小為60VM，參數(shù)p=0.5，最多同時調度進入資源池的作業(yè)為q=4.8，表示最多同時調度作業(yè)的數(shù)量不能超過4.8。

其他作業(yè)調度性能相關定義如下。

定義1：作業(yè)平均響應時間ART(Average Response Time)

ART=∑nj=1rjN

定義2：作業(yè)平均等待時間

AWT=∑nj=1wjN

定義3：虛擬服務器租用時間LT(Lease Time)

LT=∑qi=1Tlease(i)

其中，LT表示租用虛擬機的總時間，假設累計租用q臺虛擬機，Tlease(i)為VMi的租用時間。

定義4：作業(yè)運行代價(Job Cost Price)

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

pricei=(αusl+βpos)×pricebase

作業(yè)的運行代價由使用資源時間和資源VM的單價決定，資源VM單價由參數(shù)資源的地理位置βpos、資源的用戶級別αusl，以及資源的基礎定價決定。

五、實驗仿真

實驗仿真中硬件環(huán)境采用虛擬化平臺提供并行作業(yè)運行所需要的虛擬機資源，虛擬化平臺采用VMware Vsphere 5.1虛擬化軟件、VMware Vcloud Automation Center 6.0云計算管理軟件，6臺服務器刀片，提供計算資源VM60個，資源根據(jù)6個關鍵屬性，對資源集采用CBFCM算法和標準FCM算法進行分類處理，并標記為分類的資源類型，通過聚類有效性函數(shù)(公式10)，可以得出當分類數(shù)為3時，函數(shù)值取值最小，分類數(shù)為3是最優(yōu)的劃分數(shù)。同時FCM和CBFCM算法的迭代次數(shù)和分類正確性進行統(tǒng)計，如表1所示。

表1　FCM和CBFCM算法性能分析

通過表1不難發(fā)現(xiàn)，CBFCM算法與FCM算法在資源的分類中的性能對比，CBFCM具有較大的優(yōu)勢，同時也為云計算服務模型中用戶服務等級的劃分，提供較好的劃分依據(jù)。

對作業(yè)調度算法的性能分析，定義參數(shù)p=0.5，也就是調度中大小作業(yè)的比例均等，在四種調度算法中，選取代表性的三類算法FCFS、LJFS、SFCFS，對作業(yè)平均響應時間ART、平均等待時間AWT和作業(yè)平均運行代價ACP三個性能指標進行試驗分析，分析結果如圖2-4所示。

圖2　算法平均響應時間對比

圖3　算法平均等待時間對比

圖4　作業(yè)平均運行代價對比

通過圖2、圖3的分析可以發(fā)現(xiàn)，AFCFS在作業(yè)調度的ART和AWT性能上，都占有較大的優(yōu)勢，其中算法LJFS和AFCFS性能相差不大，F(xiàn)CFS在作業(yè)調度上性能較差，不推薦使用。圖4中作業(yè)運行代價中，AFCFS算法在參數(shù)q取值3.5時，取得最優(yōu)值，表明隨著同時進入資源集作業(yè)數(shù)量的增加，平均運行代價ACP會先降低再升高，ACP最優(yōu)取值與參數(shù)p和資源集的大小相關。

六、總　結

筆者圍繞云計算數(shù)據(jù)中心資源分配過程中作業(yè)的性能代價問題，提出了一種新的云計算資源分配策略，在建立并行任務性能代價模型的基礎上，利用改進的模糊聚類算法(CBFCM Cost-Based Fuzzy Clustering Algorithm)對云計算資源集依據(jù)用戶服務等級USL進行分組，并對作業(yè)采用四種不同的調度算法FCFS、SJFS、LJFS、AFCFS進行分析。通過實驗表明，在云計算資源分類的應用中，CBFCM算法在迭代次數(shù)和分類正確性方面有較大的優(yōu)勢，AFCFS作業(yè)調度算法在平均響應時間ART、平均等待時間AWT、平均運行代價ACP性能指標中，較其他三個算法有較大的優(yōu)勢。通過實驗可以發(fā)現(xiàn)，基于CBFCM資源分類和作業(yè)調度的策略在云計算服務中有一定的優(yōu)勢。

[1]林偉偉，齊德昱.云計算資源調度研究綜述[J].計算機科學，2012(10):1-6.

[2]許力,曾智斌,姚川.云計算環(huán)境中虛擬資源分配優(yōu)化策略研究[J].通信學報,2012(Z1):9-16.

[3]李新，賈智平，鞠雷.一種面向同構集群系統(tǒng)的并行任務節(jié)能調度優(yōu)化方法[J].計算機學報，2012(3):591-602.

[4]薛景文,田玉玲.基于改進克隆選擇算法的云計算任務調度算法[J].計算機應用與軟件,2013(5):167-170.

[5]姚婧，何聚厚.基于模糊聚類分析的云計算負載均衡策略[J].計算機應用.2012(1):213-217.

[6]李文娟，張啟飛，平玲娣.基于模糊聚類的云任務調度算法[J].通信學報，2012(3):146-154.

[7]戴炳榮,宋俊典,錢俊玲.云計算環(huán)境下海量分布式數(shù)據(jù)處理協(xié)同機制的研究[J].計算機應用與軟件,2013(1):107-110.

[8]王登科,李忠.基于粒子群優(yōu)化與蟻群優(yōu)化的云計算任務調度算法[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

王小軍，江蘇開放大學信息化建設處高級工程師，理學碩士,主要從事計算機應用、網(wǎng)絡學習研究。(wangxj@jsou.cn)

江蘇開放大學“十二五”規(guī)劃2013年度課題“個性化推薦系統(tǒng)在網(wǎng)絡教學中的應用研究”(13SEW-Q-052)；國家開放大學2014-2015年度青年課題“個性化推薦系統(tǒng)在移動學習中的應用研究”(G14A1401Q)