云環(huán)境下基于模糊聚類的任務(wù)調(diào)度算法

胡鵬

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

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

云任務(wù)調(diào)度下執(zhí)行任務(wù)聚類有助于降低系統(tǒng)開銷[11]?，F(xiàn)有調(diào)度大多是對云計算環(huán)境的資源和任務(wù)進行聚類[12-15]，再進行任務(wù)和資源的分配調(diào)度。本文提出了一種基于類簇匹配的策略，利用模糊聚類算法，通過對云任務(wù)進行分類，對云計算資源進行聚類分簇，將任務(wù)隊列與資源簇進行匹配，通過貪心策略將任務(wù)分配到對應(yīng)的資源簇上進行調(diào)度。

1 相關(guān)工作

1.1 模糊聚類分析

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

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

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

圖1 FCM 算法流程圖

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

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

1.2 貪心策略

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

2 基于模糊聚類的任務(wù)調(diào)度

2.1 問題建模

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

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

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

2.2 聚類分析

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

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

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

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

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

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

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

步驟6 根據(jù)式（6）重新計算隸屬度U，再返回到步驟4 重復(fù)執(zhí)行。

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

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

2.3 貪心調(diào)度分配

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

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

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

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

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

步驟5 調(diào)度分配結(jié)束。

按照以上步驟，對內(nèi)存需求型任務(wù)和帶寬需求型任務(wù)也采用同樣的貪心策略進行任務(wù)調(diào)度分配，直到所有的任務(wù)均執(zhí)行結(jié)束，將結(jié)果反饋給用戶。

3 實驗仿真與分析

3.1 實驗環(huán)境

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

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

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

3.2 評價指標

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

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

3.3 仿真結(jié)果分析

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

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

圖2 任務(wù)Makespan 比較結(jié)果

圖3 算法AU 比較結(jié)果

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

4 結(jié)論

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