一種基于多維聚類預(yù)處理的云計算任務(wù)調(diào)度算法

邵雯娟

摘要：文章主要介紹了一種基于多維聚類預(yù)處理的云計算任務(wù)調(diào)度算法，根據(jù)預(yù)先分類好的資源特征向量進行分類依據(jù)，將云計算資源與特征向量間的相似度距離作為測度函數(shù)，將資源劃分到預(yù)先定義好的類別中。本調(diào)度算法對資源進行分類預(yù)處理，能有效縮小任務(wù)對于資源搜索的范圍，從而提高任務(wù)調(diào)度的速度。關(guān)鍵詞：特征向量；相似度測度；任務(wù)調(diào)度

1 研究背景

云計算主要采用虛擬化技術(shù)將數(shù)據(jù)中心的物理資源虛擬化為資源節(jié)點后，進行統(tǒng)一管理和對外服務(wù)。用戶享受的服務(wù)質(zhì)量水平將會和所需支付的費用成正比。正是由于用戶的不同需求，云任務(wù)調(diào)度器需要為用戶任務(wù)選擇合適的資源，最大限度地滿足用戶對于服務(wù)質(zhì)量的需求，提高資源利用率，維持資源負載均衡。因此，研究云環(huán)境下的任務(wù)調(diào)度算法意義重大。

2 聚類分析法原理

聚類分析是根據(jù)樣本自身的屬性，用數(shù)學(xué)方法按照某種相似性或差異性指標，定量地確定樣本之間的親疏關(guān)系，并按這種親疏關(guān)系程度對樣本進行聚類。通常是用樣本間的相似系數(shù)來描述其親疏程度。有了相似系數(shù)就可定量地對樣本進行分組，根據(jù)分類函數(shù)將差異最小的歸為一組，組與組之間再按分類函數(shù)進一步歸類，直到所有樣本歸為一類為止。

3 算法描述

本算法的目標是找到對資源集的一個劃分，使資源性能相近或相似的節(jié)點聚在一起共同構(gòu)成一個分類類別。算法的主要思想是：

（1）對訓(xùn)練集中的云系統(tǒng)資源向量事先進行手工粗分類，分為：計算型，轉(zhuǎn)發(fā)型，存儲型，計算出每一類的特征向量F（x_i）={x₁，x₂，x₃，…，x_n）。

（2）對測試集中的云系統(tǒng)資源向量建立初始樣本矩陣：S（y_t）=（y₁，y₂，y₃，…，y_n）。

（3）用類間的相似系數(shù)來描述其親疏程度，計算每個資源向量與各個大類的特征向量間的相似性測度函數(shù)。

M_j=（F（x₁），S（y_j））=（m₁，m₂，m₃）

相關(guān)性系數(shù)定義為向量的單位化內(nèi)積：

根據(jù)相似性測度函數(shù)M_j=（F（x₁），S（y_j））的值，根據(jù)模式分類的原則：

C（z）=ArgM_iaxM_j（F（x₁），S（y_j））

（4）比較和S_i最相似的類，從而確定該資源向量的分類，將該資源和大類歸并為一個類別。

（5）重復(fù)執(zhí)行上述操作，直到資源池中所有資源向量都只屬于同一個分類類別為止，即所有資源節(jié)點都有明確的分類類別。

（6）在每個大類中，將資源按照綜合性能進行降序排序，性能較好的資源將優(yōu)先被調(diào)度。

（7）對資源進行分類預(yù)處理后，在已有的分類類別中選擇性能最優(yōu)的資源，最大限度地體現(xiàn)了任務(wù)調(diào)度的公平性。

4 算法性能分析

在任務(wù)調(diào)度系統(tǒng)中，用戶提交任務(wù)的最終完成時間取決于該任務(wù)集中所有任務(wù)的完成時間，也就是任務(wù)完成時時間最大的任務(wù)。

任務(wù)i預(yù)期完成時間L主要由隊列等候時間、處理和存儲時間、轉(zhuǎn)發(fā)延遲時間組成。

隊列等候時間可用公式（1）計算得出：（1）

Q（i）表示任務(wù)T_i在分類類別中在任務(wù)隊列中等待調(diào)度的時間，n表示任務(wù)i前面的任務(wù)數(shù)，T_j表示第j個任務(wù)的預(yù)期完成時間。

處理和存儲時間可用公式（2）計算得出：（2）

S（i，k）表示任務(wù)T_i使用資源k時，所需的計算執(zhí)行時間，t_ci表示任務(wù)計算量，r_calk表示資源K的計算能力，t_si表示所需存儲的任務(wù)量，r_stork表示資源K的存儲能力。

轉(zhuǎn)發(fā)延遲時間可由公式（3）計算得出：（3）

F（i，k）表示任務(wù)i使用K源后，轉(zhuǎn)發(fā)任務(wù)結(jié)果所需的傳輸時間，t_datai指任務(wù)輸出數(shù)據(jù)量，r_comk表示資源K的通信帶寬能力。

因此，任務(wù)預(yù)期完成時間可以表示為：

T_i=Q（i，k）+S（i，k）+F（i，k） （4）

使用CloudSim仿真平臺，將本調(diào)度算法（以下簡稱GCCTS）與Min-Min和Max-Min算法進行模擬實驗調(diào)度，數(shù)據(jù)取自模擬20次取得的平均值。從調(diào)度策略的平均完成時間對3種算法進行性能比較。圖1所示為資源數(shù)為20時，3種算法任務(wù)平均完成時間的比較圖。圖2所示為資源數(shù)為50時，3種算法任務(wù)平均完成時的比較圖。

由以上分析可以看出，Min-Min算法由于每次優(yōu)先選擇任務(wù)完成時間最小的任務(wù)執(zhí)行，因而任務(wù)最終完成時間小于Max-Min算法，但次于GCCTS算法。

5 結(jié)語

文章主要介紹一種基于多維聚類預(yù)處理的云計算任務(wù)調(diào)度算法。首先介紹了聚類分析方法，論述分類方法的具體實現(xiàn)步驟，利用該方法將資源劃分到預(yù)先定義好的分類類別中。然后詳細介紹算法的主要思想、偽代碼實現(xiàn)，并經(jīng)過對模擬環(huán)境下的實驗數(shù)據(jù)分析，本調(diào)度算法對資源進行分類預(yù)處理，能有效縮小任務(wù)對于資源搜索的范圍，從而提高任務(wù)調(diào)度的速度。

該調(diào)度策略仍然存在很多可改進的地方：

（1）在聚類分割時，可進一步考慮總體的資源統(tǒng)計特性，考慮采用馬哈拉諾比距離，代替相似度度量值。

（2）云環(huán)境下的資源節(jié)點具有動態(tài)變化性，需考慮基于隨機優(yōu)化的動態(tài)資源分類。

（3）本文將資源劃分為計算型，轉(zhuǎn)發(fā)型以及存儲型3個維度，可結(jié)合實際用戶需求，提出多維Qos優(yōu)化的云任務(wù)調(diào)度優(yōu)化算法。