基于模糊聚類的云計(jì)算集群資源調(diào)度算法

周麗娟

山西財(cái)經(jīng)大學(xué)實(shí)驗(yàn)教學(xué)中心，山西 太原 030006

云計(jì)算（cloud computing）作為一種將計(jì)算資源作為服務(wù)并通過網(wǎng)絡(luò)并提供給用戶的計(jì)算模式，使得用戶可以通過按需使用計(jì)算資源，這些資源主要包括數(shù)據(jù)、軟件、硬件和帶寬。云計(jì)算通過提供軟件即服務(wù)、平臺(tái)即服務(wù)和基礎(chǔ)設(shè)施即服務(wù)這三類服務(wù)來為用戶作業(yè)提供解決方案。云計(jì)算中的資源具有地理分散、資源異構(gòu)和動(dòng)態(tài)變化等特征。

云計(jì)算是在網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展而來，其主要特征是通過引入虛擬化計(jì)算，使得云計(jì)算環(huán)境下的資源調(diào)度不同于網(wǎng)格計(jì)算，但其目標(biāo)往往是最小化最大完工時(shí)間，并通過啟發(fā)式算法來尋求實(shí)現(xiàn)資源最優(yōu)分配。

美國國家標(biāo)準(zhǔn)技術(shù)院將云計(jì)算定義為：云計(jì)算是一種通過網(wǎng)絡(luò)并使得用戶可以按需來共享的一個(gè)可配置的資源池，該資源池能在僅需較少管理開銷和交互的情況下，對(duì)資源進(jìn)行快速配置和釋放，云計(jì)算模式的5個(gè)基本特征為：按需自助服務(wù)、網(wǎng)絡(luò)的廣泛訪問和共享資源池以及快速的彈性能力。

資源調(diào)度是云計(jì)算的一個(gè)核心問題，直接關(guān)系到云計(jì)算服務(wù)的穩(wěn)定性、資源的使用效率和用戶滿意程度。云計(jì)算的資源調(diào)度問題的研究從理論技術(shù)本身上來說具有非常重要的意義［1-3］。

文獻(xiàn)［4］針對(duì)云計(jì)算領(lǐng)域的任務(wù)調(diào)度問題，提出了一種基于人工免疫的云計(jì)算平臺(tái)動(dòng)態(tài)任務(wù)調(diào)度算法，通過排隊(duì)論粗略確定保持云平臺(tái)穩(wěn)定的條件，為后面的計(jì)算提供基礎(chǔ)數(shù)據(jù)，然后利用免疫理論中的免疫克隆算法來為不同節(jié)點(diǎn)分配資源實(shí)現(xiàn)最優(yōu)配置，實(shí)現(xiàn)負(fù)載平衡處理。為了提高傳統(tǒng)資源調(diào)度算法的資源利用率，文獻(xiàn)［5］提出了一種云計(jì)算環(huán)境下的資源調(diào)度模型，該資源調(diào)度模型基于人工蜂群算法進(jìn)行調(diào)度方案優(yōu)化。文獻(xiàn)［6］分析討論了1組Directed acyclic graph（DAG）共享云計(jì)算資源調(diào)度［7-8］中的多DAG數(shù)量、屬性結(jié)構(gòu)分布特點(diǎn)和資源需求量關(guān)系，提出了一種基于資源需求強(qiáng)度預(yù)測(cè)變異方法的進(jìn)化算法（evolutional algorithm based on the forecasting of resource demand，EFRD）。文獻(xiàn)［9］研究了云端資源的管理和調(diào)度，從服務(wù)商需求角度出發(fā)來構(gòu)建云資源調(diào)度方法，能在不損害用戶和生產(chǎn)商利益的前提下實(shí)現(xiàn)收益平衡。

上述工作研究了云計(jì)算任務(wù)調(diào)度，具有重要的意義，本文提出了一種基于模糊聚類的云資源調(diào)度方法，在對(duì)云計(jì)算異構(gòu)資源進(jìn)行模糊聚類的基礎(chǔ)上，實(shí)現(xiàn)資源的動(dòng)態(tài)調(diào)度，并通過實(shí)驗(yàn)證明了文中方法的有效性。

1 資源調(diào)度目標(biāo)函數(shù)

本文的云計(jì)算資源調(diào)度模型采用Map-Reduce編程/資源調(diào)度模型［10-14］，如圖1所示。

從圖1可以看出，云計(jì)算每個(gè)單元包含2個(gè)節(jié)點(diǎn)：主控節(jié)點(diǎn)Jobtracker和從節(jié)點(diǎn)Task Tracker，主控節(jié)點(diǎn)負(fù)責(zé)任務(wù)的資源分配、調(diào)度以及失敗任務(wù)的跟蹤，從節(jié)點(diǎn)主要負(fù)責(zé)任務(wù)的執(zhí)行。

TaskTracker從節(jié)點(diǎn)可以形式化的表示為G(V，E)，其中V表示其所屬主控節(jié)點(diǎn)所能管理的所有節(jié)點(diǎn)構(gòu)成的集合，而E是對(duì)應(yīng)的邊集。因此，這些節(jié)點(diǎn)可以執(zhí)行一系列任務(wù)。

圖1 Map-Reduce編程/任務(wù)調(diào)度模型Fig.1 Program/task scheduling model of map-reduce

本文的主要工作就是采用模糊聚類算法選擇最合適分配給節(jié)點(diǎn)的資源進(jìn)行分配。

資源分配過程中考慮的性能指標(biāo)主要包括：預(yù)計(jì)執(zhí)行時(shí)間T(r)、網(wǎng)絡(luò)帶寬B(r)和網(wǎng)絡(luò)延遲D(r)。

1）T(r)：任務(wù)ti在處理節(jié)點(diǎn)tnj執(zhí)行的最早完成時(shí)間，可以表示為：

式（1）中，S(nj)為某任務(wù)在節(jié)點(diǎn)nj上可以執(zhí)行的最早時(shí)間，Eij為在節(jié)點(diǎn)nj上執(zhí)行某任務(wù)ti所需的執(zhí)行時(shí)間。

2）B(r)：表示路徑r對(duì)應(yīng)的網(wǎng)絡(luò)帶寬最大值。

3）D(r)：路徑r對(duì)應(yīng)的網(wǎng)絡(luò)延遲最大值。

因此，資源調(diào)度的目標(biāo)函數(shù)為：

滿足：

其中，a、b和c分別為預(yù)計(jì)執(zhí)行時(shí)間T(r)、網(wǎng)絡(luò)帶寬B(r)和網(wǎng)絡(luò)延遲D(r)的各自權(quán)重，TLT、ELT和DLT為對(duì)應(yīng)的界限。

2 基于模糊聚類的資源調(diào)度算法

2.1 模糊聚類

模糊K-MEANS算法具有計(jì)算簡單和聚類速度快的特點(diǎn)，是一種動(dòng)態(tài)聚類算法，能通過不斷最小化誤差平方和來求取聚類，并求出每個(gè)數(shù)據(jù)樣本點(diǎn)到聚類中心的隸屬度，隸屬度最高的聚類被定位樣本點(diǎn)所屬的分類，模糊K-MEANS算法需要確定最優(yōu)聚類個(gè)數(shù)和初始聚類中心：聚類個(gè)數(shù)對(duì)于聚類精度具有較大的影響，由于初始階段無法準(zhǔn)確確定聚類個(gè)數(shù)，因此，通過隨機(jī)確定聚類個(gè)數(shù)。

不同的初始聚類中心對(duì)聚類結(jié)果影響巨大，傳統(tǒng)的K均值算法隨機(jī)選取K個(gè)點(diǎn)作為初始聚類種子，并不斷通過迭代直到聚類中心確定和算法收斂。

2.2 基于模糊K-MEANS資源分配算法

采用模糊聚類算法來對(duì)節(jié)點(diǎn)資源進(jìn)行分配的原理可以表示為：

首先設(shè)定一個(gè)初始的聚類數(shù)K，最大聚類數(shù)Kmax，距離閥值為θd，當(dāng)新節(jié)點(diǎn)被釋放時(shí)，需對(duì)所有資源進(jìn)行重新聚類，而當(dāng)新任務(wù)到來時(shí)，首先需計(jì)算與其具有最小距離的聚類，將最小聚類對(duì)應(yīng)的中心作為資源分配的節(jié)點(diǎn)。

選擇具有最小距離的聚類中心作為任務(wù)被分配的資源節(jié)點(diǎn)。

當(dāng)新節(jié)點(diǎn)被釋放時(shí)，需要計(jì)算其與所有聚類中心的距離，如果其與所有聚類中心的距離均大于閥值θd，且聚類中心的數(shù)量尚未超過允許的最大數(shù)量時(shí)K≤Kmax時(shí)，增加一個(gè)新的聚類SK+1，并計(jì)算新的聚類中心。

當(dāng)新任務(wù)到來時(shí)，則計(jì)算其與所有聚類中心的距離，選擇具有最小距離的聚類作為其所屬的聚類。

算法1基于改進(jìn)模糊K-MEANS算法的資源分配算法可以描述為：

輸入：所有節(jié)點(diǎn)集合和任務(wù)集合；

初始化：距離閥值為θd、聚類數(shù)K，聚類最大數(shù)量Kmax，初始化聚類集合S1，S2，...SK空集，初始化數(shù)據(jù)中心c1，c2，...，cK，當(dāng)前迭代次數(shù)t=1。

步驟1：對(duì)聚類于新來的任務(wù)xi，計(jì)算其到每個(gè)節(jié)點(diǎn)聚類Sj的隸屬度wij：

其中，||xik-cjk||表示節(jié)點(diǎn)資源xi到數(shù)據(jù)中心cj之間的歐幾里得距離，當(dāng)中心點(diǎn)的坐標(biāo)與節(jié)點(diǎn)資源xi相同時(shí)，即 ||xi-cq||?=0?，wij==1，否則wij0，且wij滿足

步驟2：對(duì)各個(gè)節(jié)點(diǎn)資源聚類Sj的中心c1，c2，...，cK進(jìn)行更新：

步驟3：計(jì)算各資源節(jié)點(diǎn)xi到所有聚類中心的距離的最小值J(W，C)：

步驟4：對(duì)距離最小值J(W，C)進(jìn)行判斷。

如果其大于距離閥值θd，判斷K≤Kmax是否成立：如果成立，則轉(zhuǎn)入步驟5；否則，轉(zhuǎn)入步驟6；

步驟5：將節(jié)點(diǎn)xi作為聚類中心，并重建新聚類，cK+1=xi，聚類SK={xi}，并將聚類數(shù)K=K+1。

步驟6：查找任務(wù)應(yīng)分配的節(jié)點(diǎn)，即計(jì)算J(W，C)對(duì)應(yīng)的聚類，其使：

步驟7：對(duì)于具有最小J(W，C)的聚類Sj，對(duì)其聚類中心cj進(jìn)行調(diào)整，得到新的聚類中心為：

其中，η為學(xué)習(xí)率。

步驟8：判斷算法已達(dá)到最大迭代次數(shù)。

如果達(dá)到，則算法結(jié)束；否則，判斷任務(wù)與所有節(jié)點(diǎn)聚類中心的距離是否小于距離閾值：

其中，n為樣本總數(shù)。

當(dāng)大于距離閾值時(shí)，需對(duì)節(jié)點(diǎn)進(jìn)行重新聚類，增加聚類總數(shù)。

3 結(jié)果分析

在Cloudsim云計(jì)算仿真環(huán)境［15-17］下對(duì)文中所提的資源調(diào)度算法進(jìn)行仿真和實(shí)驗(yàn)，并與文獻(xiàn)［5］方法和文獻(xiàn)［6］方法進(jìn)行比較，文中方法的參數(shù)設(shè)置為：物理節(jié)點(diǎn)數(shù)量為100，CPU計(jì)算能力2000（MI·s-1），內(nèi)存為8 GB，網(wǎng)絡(luò)帶寬為 150（MI·s-1），任務(wù)總數(shù)為1000個(gè)，任務(wù)個(gè)數(shù)與任務(wù)分配均為隨機(jī)的。

3.1 負(fù)載均衡程度

采用負(fù)載均衡因子來作為性能比較指標(biāo)，負(fù)載均衡因子可以定義為：

式（10）中，m為實(shí)驗(yàn)總次數(shù)，L為虛擬機(jī)r在某時(shí)

jj刻k的負(fù)載均衡值，為云計(jì)算數(shù)據(jù)中心在某時(shí)刻k的平均負(fù)載。

當(dāng)實(shí)驗(yàn)次數(shù)為50時(shí)，運(yùn)行文中方法與文獻(xiàn)［5］和文獻(xiàn)［6］方法進(jìn)行比較，3種方法得到的負(fù)載均衡因子的比較如圖2所示，在圖2中可以發(fā)現(xiàn)，文中方法的負(fù)載均衡能力最強(qiáng)，文獻(xiàn)［6］方法次之，而文獻(xiàn)［5］方法的負(fù)載均衡能力較差，因?yàn)槠湄?fù)載均衡因子遠(yuǎn)遠(yuǎn)大于另外兩種方法，且在仿真時(shí)間為400 s時(shí)，即仿真結(jié)束時(shí)仍沒有收斂的趨勢(shì)。而文中方法通過模糊聚類對(duì)所有節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)重分配，并將任務(wù)分配給需求最匹配的節(jié)點(diǎn)，因此具有最好的負(fù)載均衡能力。

圖2 負(fù)載均衡效果比較Fig.2 Comparisons of load balance effect

3.2 負(fù)載均衡效率

為了進(jìn)一步對(duì)3種算法的負(fù)載均衡效率進(jìn)行比較，在計(jì)算出所有的負(fù)載均衡因子后，可以計(jì)算得到負(fù)載均衡效率：

其中，ηload_0表示聚類中心的負(fù)載均衡值，從公式（11）可以看出，當(dāng)ET_k的值越小時(shí)，對(duì)應(yīng)算法的負(fù)載均衡效率越高。

3種算法的負(fù)載均衡效率的比較如圖3所示。從圖3可以看出，文中方法的負(fù)載均衡效率較高，文中方法得到的負(fù)載均衡效率的平均值分別為 0.0127，而文獻(xiàn)［5］和文獻(xiàn)［6］方法的值則分別為0.0416和0.0275，文中方法的負(fù)載均衡效率最高。

圖3 負(fù)載均衡效率Fig.3 Comparisons of load balance effect

4 結(jié) 語

為了實(shí)現(xiàn)云環(huán)境下資源的高效調(diào)度，設(shè)計(jì)了一種基于模糊聚類的云計(jì)算集群資源調(diào)度方法。通過模糊聚類方法對(duì)所有資源節(jié)點(diǎn)進(jìn)行聚類，當(dāng)新任務(wù)到來時(shí)，自動(dòng)計(jì)算其到各個(gè)聚類中心的距離，將具有最小聚類距離的聚類中心分配給該任務(wù)。在Cloudsim仿真工具下進(jìn)行實(shí)驗(yàn)，結(jié)果表明了文中方法能有效實(shí)現(xiàn)節(jié)點(diǎn)負(fù)載均衡，與其他方法相比，具有較好的負(fù)載均衡程度和負(fù)載均衡效率，具有較強(qiáng)的應(yīng)用前景。