一種基于多維聚類預處理的云計算任務調度算法

邵雯娟

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

1 研究背景

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

2 聚類分析法原理

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

3 算法描述

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

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

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

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

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

相關性系數定義為向量的單位化內積：

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

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

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

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

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

（7）對資源進行分類預處理后，在已有的分類類別中選擇性能最優的資源，最大限度地體現了任務調度的公平性。

4 算法性能分析

在任務調度系統中，用戶提交任務的最終完成時間取決于該任務集中所有任務的完成時間，也就是任務完成時時間最大的任務。

任務i預期完成時間L主要由隊列等候時間、處理和存儲時間、轉發延遲時間組成。

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

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

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

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

轉發延遲時間可由公式（3）計算得出：（3）

F（i，k）表示任務i使用K源后，轉發任務結果所需的傳輸時間，t_datai指任務輸出數據量，r_comk表示資源K的通信帶寬能力。

因此，任務預期完成時間可以表示為：

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

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

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

5 結語

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

該調度策略仍然存在很多可改進的地方：

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

（2）云環境下的資源節點具有動態變化性，需考慮基于隨機優化的動態資源分類。

（3）本文將資源劃分為計算型，轉發型以及存儲型3個維度，可結合實際用戶需求，提出多維Qos優化的云任務調度優化算法。