云環境下基于模糊聚類的任務調度算法

胡鵬

（南京郵電大學電子與光學工程學院微電子學院，江蘇 南京 210023）

云計算是通過互聯網提供的動態可擴展虛擬化資源，按需提供方便可用的網絡訪問[1]。由于云計算系統的動態性和多樣性，任務調度成為一個挑戰性的問題[2]。文獻[3]首先制定任務執行時間目標函數，然后引入改進粒子群優化算法來調度任務并增強負載均衡。文獻[4]通過基于混沌慣性權重的隨機選擇對群居蜘蛛群體進行智能建模，使得總體完工時間最小化。文獻[5]先構建云計算資源負載平衡優化的約束條件， 其次通過改進螢火蟲算法優化資源搜索路徑， 優化云服務器中虛擬機之間的任務負載平衡來縮短用戶任務完成總時間。文獻[6]以完成時間、成本以及最后期限違反率為目標函數， 將布谷鳥算法和粒子群優化組合來智能優化任務調度問題。文獻[7] 提出了一種引入min-min 和max-min 算法生成初始化種群，選擇任務完成時間和負載均衡作為雙重適應度函數，提高初始化種群質量、算法可搜索性和收斂速度的改進遺傳算法進行任務調度。文獻[8]在遺傳算法的變異操作中引入了一種改進的隨機因子和慣性權重的增強型粒子群優化算法，通過增強粒子群優化算法中的當前最優解和全局最優解重構變異算子，增強遺傳和粒子群優化算法具有更快的收斂速度而且不會陷入局部最優解。文獻[9]利用布谷鳥搜索和引力搜索算法的優點，根據不同的評價指標，提升了算法的性能。文獻[10]依據空間案投影分析計算了集群的負載均衡度，給出調度決策變量，依據任務的執行代價完成時限賦予任務不同優先級進行任務調度。

云任務調度下執行任務聚類有助于降低系統開銷[11]。現有調度大多是對云計算環境的資源和任務進行聚類[12-15]，再進行任務和資源的分配調度。本文提出了一種基于類簇匹配的策略，利用模糊聚類算法，通過對云任務進行分類，對云計算資源進行聚類分簇，將任務隊列與資源簇進行匹配，通過貪心策略將任務分配到對應的資源簇上進行調度。

1 相關工作

1.1 模糊聚類分析

聚類分析是把一個沒有類別標記的樣本按照某種準則劃分為若干子集，使相似的樣本盡可能歸于一類，把不相似的樣本劃分到不同的類中。傳統的硬聚類把每個待識別的對象嚴格的劃分某類中，具有非此即彼的性質，而模糊聚類建立了樣本對類別的不確定描述，更能客觀的反應客觀世界，從而成為聚類分析的主流。

模糊C 均值（Fuzzy C-means）算法簡稱FCM 算法，是一種基于目標函數的模糊聚類算法，主要是用于數據的聚類分析。相較于k-means 的硬聚類，模糊c 提供了更加靈活的聚類結果。大部分情況下，數據集中的對象不能劃分成為明顯分離的簇，指派一個對象到一個特定的簇有些生硬，也可能會出錯。因此對每個對象和每個簇賦予一個權值，指明對象屬于該簇的程度。雖然基于概率的方法也可以給出這樣的權值，但是有時候我們很難確定一個合適的統計模型，因此使用具有自然地、非概率特性的模糊c 均值就是一個比較好的選擇。

FCM算法流程圖如圖1 所示。

圖1 FCM 算法流程圖

因此，給定一個數據樣本集合為T={ T1，T2，T3，…Tn}，再通過FCM 聚類算法分析之后，得到了樣本類劃分為C={ C1，C2，C3，…Ck}，目標函數J 如式1 所示：

目標函數是由樣本的隸屬度uij與該樣本到各個類中心的歐氏距離組成，m 是一個隸屬度因子，實質是一個刻畫模糊化程度的參數，最佳取值范圍在[1.5，2.5]，大部分情況下取2。式（2）為約束條件，表示一個樣本屬于所有類的隸屬度和要為1。因此本質上就是要求得最小的目標函數值，目標函數值越小，表示簇內相似度越高，因此FCM就是不斷迭代求最優J 的過程。

1.2 貪心策略

貪心算法（又稱貪婪算法）是在對問題求解時，總是做出在當前看來最好的選擇。也就是說，不從整體的最優解上加以考慮，它所做出的是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關。

2 基于模糊聚類的任務調度

2.1 問題建模

假定用戶所提交的任務集T 中包含有n 個任務，這n 個任務相互獨立大小不同，即T = {T1，T2，T3，…，Tn}，第j 個任務又可以詳細描述為Tj= {tid，tlen，tPe，tcomp，tmem，tbw}，其中，tid是任務所屬的編號，tlen是任務的長度，tPe是任務運行所需要的內核數，tcomp是任務執行時需要的計算能力，tmem是任務執行時所需要的內存量，tbw是任務運行時所需要的帶寬，其中tcomp也可以根據以下公式計算得到：tcomp= tlen/ tPe。

云環境下的資源為虛擬機資源。因此假定一個資源集合中有m 個虛擬機資源，即VM = {VM1，VM2，VM3，…VMm}，且這些資源性能不同，而第i 個資源又可以詳細描述為VMi= {Vmid，Vmcpu，Vmmips，Vmcomp，Vmmem，Vmbw}，這里的Vmid指的是虛擬機所屬的編號，Vmcpu是該資源的CPU 數目，Vmmips是該虛擬機資源每秒的指令執行能力，Vmcomp是該資源的計算能力，Vmmem是該資源的存儲能力，Vmbw是該資源的帶寬能力。虛擬機資源的計算能力可由下式得到：Vmcomp=VmcpuVmmips。

ETC（i，j）矩陣所代表的是各個任務分別在各個虛擬機上的完成時間，ETCij指的是任務i 在虛擬機j 上執行需要的完成時間，它由任務的執行時間ECTij加上任務的等待時間wij得到：ETCij=ECTij+wij，最后用來計算任務執行總時間。

2.2 聚類分析

本文采用模糊FCM 聚類算法對任務集和資源集進行聚類劃分，根據公式（1）目標函數可以簡單按照如下步驟進行劃分：

步驟1 對于n 個任務，以它們的需求屬性tcomp，tmem，tbw建立一個初始的樣本矩陣Tn×3，tij為矩陣中的一個元素，代表任務i的第j 維需求。

步驟2 對步驟1 中的矩陣Tn×3根據式（3）進行標準化，再利用式（4）壓縮數據到[0，1]之間。

tj代表的是任務在第j 維需求的均值，Sj代表的是各任務在第j 維需求的標準差，t′jmin和t′jmax分別是t′1j，t′2j， …t′nj中的最小值和最大值。

步驟3 設定參數包括類別為3 類、迭代最大次數、目標函數閾值以及隸屬度因子m=2，初始化隸屬度矩陣U。

步驟4 根據式（5）分別計算3 個聚類中心ci。

步驟5 根據式（1）計算類內各節點與聚類中心的目標函數值，若小于所給閾值或者相較于上次的目標函數值的變化量小于所給閾值，或者達到迭代次數，則算法停止，否則繼續執行下一步。

步驟6 根據式（6）重新計算隸屬度U，再返回到步驟4 重復執行。

經過此類模糊聚類分析，可將所提交任務集劃分為三個任務類，分別為計算需求型（CompClass）、內存需求型（MemClass）以及帶寬需求型（BwClass）。

對主機資源集群來說，也采用聚類分析的方法來對虛擬機資源進行分類，在步驟1 中，以m 個資源的屬性值Vmcomp，Vmmem以及Vmbw來建立初始樣本矩陣Rm×3，rij代表了第i 個資源的第j 維屬性性能，其他的步驟原理同對任務聚類分析一樣，最終得到了三個資源簇分別為計算型資源簇（CompCluster）、內存型資源簇（MemCluster）以及帶寬型資源簇（BwCluster）。

2.3 貪心調度分配

根據貪心策略將三個任務類分別分配到對應的資源簇上執行，以計算需求型任務匹配計算型資源簇為例，具體的執行步驟如下：

步驟1 判斷任務集合是否為空，是則跳至步驟5，否則進行步驟2。

步驟2 按照式（7）和式（8）對任務隊列的計算需求度以及簇內資源的綜合能力進行排序。

步驟3 將需求最大的任務分配到綜合能力最好的虛擬機資源上運行。

步驟4 返回至步驟2，更新虛擬機資源的綜合性能排序隊列，并且不斷更新任務和虛擬機之間的映射關系。

步驟5 調度分配結束。

按照以上步驟，對內存需求型任務和帶寬需求型任務也采用同樣的貪心策略進行任務調度分配，直到所有的任務均執行結束，將結果反饋給用戶。

3 實驗仿真與分析

3.1 實驗環境

本文的實驗環境采用win10 操作系統，開發工具為IDEA，利用云仿真平臺CloudSim[16]進行驗證仿真，與Min-min 和Max-min 算法的執行結果從任務的總體完成時間、平均資源利用率進行了對比。具體環境如下：

任務參數配置：任務長度設置為[500，3000]，任務內存需求范圍[512，2048]，任務帶寬需求范圍[1000，3000]，任務計算能力需求范圍[500，3000]。

虛擬機資源參數配置：CPU 的個數取值{1，2，4}，虛擬機的處理速度[500，1000]，內存范圍[512，2048]，帶寬范圍[500，3000]。

3.2 評價指標

任務完成總時間Makespan 是從第一個任務開始執行到最后一個任務執行結束所需要的時間，可以通過公式（9）虛擬機資源的工作時間來得到：

上述式中，l 為虛擬機j 上所分配的任務總數，m 為虛擬機資源總數，主要的評價指標由這兩個組成。

3.3 仿真結果分析

在云平臺上，隨機生成了50，100，200，500，1000，2000 個任務，分別將本文的算法與Min-min 算法和Max-min 算法對比，比較三種算法情況下的任務總完成時間以及虛擬機資源的平均利用率。

從圖2 和圖3 的結果來看，本文算法相較Min-min 和Max-min 兩種算法有著較快的任務執行速度，這是因為Min-min 和Max-min 算法都是基于任務最早的完成時間的大小來進行分配的，沒有考慮到虛擬機的資源情況和負載均衡能力，而本文算法針對虛擬機的資源綜合能力進行貪心策略的分配，可以讓每個任務都能得到最合適的資源去運行，因此在執行速度上有著很大程度的提高。其次當任務量較多時，本文算法資源利用率一直在50%的水平以上，最高達到了70%，而Min-min 算法和Max-min 算法的資源利用率相比于本文算法一直處于較低水平。

圖2 任務Makespan 比較結果

圖3 算法AU 比較結果

綜上分析可知本文算法在云計算環境下，不僅可以提高任務的完成效率，還可以在一定程度上提高云計算的資源利用率，提高云計算系統的整體性能。

4 結論

本文針對云計算環境下的任務調度問題進行分析，提出了一種基于模糊聚類和貪心策略分配的任務調度算法，通過對任務集和虛擬機資源進行聚類分析和類簇匹配，縮小了任務選擇運行資源的范圍，提高算法運行效率，再通過貪心策略調度機制，將任務具體分配到虛擬機資源上進行調度執行。最后通過CloudSim 平臺仿真結果可知，一方面可以大大的提高云環境下任務的執行效率，縮短執行時間，另一方面也提高了虛擬機資源的利用率，下一步將對虛擬機集群的負載均衡度作進一步優化的研究，以適應高速發展的云計算體系。