周麗娟

山西財經(jīng)大學(xué)實驗教學(xué)中心，山西 太原 030006

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

滿足：

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

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

2.1 模糊聚類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)果分析

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

3.1 負(fù)載均衡程度

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

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

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

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

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

3.2 負(fù)載均衡效率

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

其中，ηload_0表示聚類中心的負(fù)載均衡值，從公式（11）可以看出，當(dāng)ET_k的值越小時，對應(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é) 語

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