改進模糊聚類的云任務(wù)調(diào)度算法

胡 蒙，苑迎春，王雪陽

（河北農(nóng)業(yè)大學 信息科學與技術(shù)學院，河北 保定071001）

0 引 言

目前，已有的云任務(wù)調(diào)度研究［1－8］主要針對云平臺中全體資源，當任務(wù)量大、資源數(shù)多時任務(wù)選擇資源的時間開銷很大，致使云平臺調(diào)度效率較低，因此找到恰當?shù)姆椒▽Y源進行合理劃分從而縮小資源選擇的范圍十分必要。聚類是一種有效的對目標進行分類的手段。關(guān)于資源聚類的研究集中于最近幾年，多是基于集群、網(wǎng)格環(huán)境下的［9－11］，研究云計算平臺下的還較少。郭等［12］提出了一種云計算環(huán)境下針對工作流任務(wù)的聚類調(diào)度算法，提高了工作流任務(wù)的調(diào)度性能，該算法將資源劃分到可選和備用兩個聚類中，在對任務(wù)隊列進行調(diào)度時，只是根據(jù)任務(wù)的最好最壞完成時間差，并沒有考慮任務(wù)本身的資源偏好；李等［13］基于資源公平分配原則提出了一種兩級調(diào)度算法，該算法在資源聚類基礎(chǔ)上引入任務(wù)資源偏好，將任務(wù)依次進行調(diào)度，保證了較高的用戶滿意度，但是由于兩個聚類之間資源差異較大，容易造成性能最好和最差的聚類間完成時間差較大，致使總的完成時間較長、資源利用率較低。

本文針對現(xiàn)有算法的不足之處，提出一種改進模糊聚類的云任務(wù)調(diào)度算法。該算法是在傳統(tǒng)的模糊聚類基礎(chǔ)上進行改進的任務(wù)調(diào)度算法，依據(jù)設(shè)定的閾值對任務(wù)分配實施調(diào)整，最大限度體現(xiàn)任務(wù)調(diào)度的公平性，有助于提高系統(tǒng)的資源利用率。

1 問題描述

云計算環(huán)境中有大量的計算型資源、帶寬型資源、存儲型資源等各類資源。不同任務(wù)對這些資源的偏好不同，有些計算型的任務(wù)希望獲得處理器性能較好的計算型資源，有些網(wǎng)絡(luò)交互型的任務(wù)對處理器性能要求不高，卻需要保證足夠的帶寬型資源。因此，本文要解決的問題就是針對云計算環(huán)境下的任務(wù)模型和資源模型，研究如何將一批任務(wù)合理地分配到一組資源上，既能使算法的執(zhí)行時間較短，又能保證這批任務(wù)總體完成時間最短且負載均衡。

1.1 任務(wù)模型

云計算環(huán)境下的任務(wù) （本文中簡稱為云任務(wù)）可以分為相互間獨立的元任務(wù)和相互間存在約束關(guān)系的依賴任務(wù)兩類。本文的研究對象只考慮元任務(wù)，為以后繼續(xù)研究依賴任務(wù)打下基礎(chǔ)。

假設(shè)用戶提交的任務(wù)集合中包含m 個云任務(wù)，這m 個任務(wù)相互獨立且大小不一。以Cloudlet表示第i個任務(wù)，它的特性可以用一維向量來描述Cloudlet＝ ｛cloudletid，cloudletuserid，cloudletlength，cloudletPEs，cloudletbw，cloudletstor，cloudletifile，cloudletofile｝。其中，參數(shù)cloudletid為任務(wù)編號，cloudletuserid為任務(wù)隸屬的用戶編號，cloudletlength為任務(wù)長度（單位：MI，百 萬 條 指 令 數(shù) 目），cloudletPEs、cloudletbw、cloudletstor為用戶所期望的PE數(shù)、帶寬大小（單位：MB／s）、存儲空間大小 （MB），cloudletifile、cloudletofile分別為輸入輸出文件大小。

云任務(wù)Cloudlet 的計算需求可由下式計算得到：cloudletcomp＝cloudletlength／cloudletPEs。

1.2 資源模型

云計算環(huán)境中的資源多是指通過虛擬化技術(shù)呈現(xiàn)給用戶的虛擬資源。假設(shè)一個資源集合中包含n 個虛擬機資源，這n個虛擬機資源性能不一。以Vm 表示第j 個資源，它的特 性 可 以 用 一 維 向 量 描 述Vm ＝ ｛Vmid，VmuserId，VmCPU，VmMIPS，Vmbw，Vmstor｝。其中，Vmid為資源編號，VmuserId為資源隸屬的云服務(wù)商編號，VmCPU為資源的CPU數(shù)目，VmMIPS表示每秒執(zhí)行的百萬條指令數(shù)目，Vmbw、Vmstor分別為資源的通信能力、存儲能力。

資源的計算能力表示為：Vmcomp＝Vmcpu×VmMIPS，值越大該資源計算性能越好。

資源j的綜合性能由式 （1）計算得出

其中，a、b、c分別表示資源的3項性能參數(shù)的經(jīng)驗系數(shù)。

聚類資源綜合性能crpj由某一類型聚類內(nèi)所有資源的綜合性能均值求得

2 基于模糊聚類和Min－Min的調(diào)度算法

本文考慮到任務(wù)選擇資源的盲目性對任務(wù)執(zhí)行情況有一定程度的影響，提出了基于資源模糊聚類的任務(wù)調(diào)度算法，在聚類內(nèi)使用Min－Min啟發(fā)式算法進行調(diào)度，并在此基礎(chǔ)之上進行了適當?shù)母倪M，以提高系統(tǒng)資源利用率，保證系統(tǒng)負載均衡性。算法主要分為模糊聚類、任務(wù)分配和算法改進3個過程。

2.1 資源聚類劃分過程

在云計算環(huán)境中，一方面，難以描述任務(wù)對資源的需求；另一方面，由于云計算環(huán)境的動態(tài)性，亦難以精確描述資源本身的屬性。因此，要恰如其分地進行任務(wù)與資源的匹配調(diào)度自然也具有模糊性。本文使用模糊C 均值聚類方法 （FCM）［14］，按照資源多維屬性特征進行模糊劃分，聚類的主要步驟如下：

步驟1 以n個資源的屬性值Vmcomp，Vmbw和Vmstor建立初始化樣本矩陣Rn×3，rij為矩陣中的一個元素，代表第i個資源的第j維性能。

步驟2 對步驟1中的矩陣Rn×3根據(jù)式 （3）進行標準化處理得到r′ij，再根據(jù)式 （4）將數(shù)據(jù)壓縮到 ［0，1］之間，得到r″ij

其中，r′jmin和r′jmax分別為r′1j，r′2j，...，r′nj中的最小值和最大值。

步驟3 將n個資源按照性能劃分為3個類別，即設(shè)定聚類中心數(shù)目為3個，初始化隸屬度矩陣U。

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

其中，uki表示數(shù)據(jù)i 對模糊組k 的隸屬度，i∈［0，1］；ck是模糊組k 的聚類中心；dki＝ck－xi是第i 個數(shù)據(jù)與第k個聚類中心與之間的歐氏距離；m ∈［1，∞）是一個加權(quán)指數(shù)，最佳取值范圍為 ［1.5，2.5］，一般取m＝2。

若J＜閾值ε，或達到迭代次數(shù)t，則聚類結(jié)束。否則，繼續(xù)步驟6。

步驟6 按照式 （6）重新計算隸屬度U，返回步驟4

經(jīng)過此模糊聚類算法運算，最終將云平臺中n 個資源劃分為3個聚類，分別為：計算型資源集 （CompCluster）、帶寬型資源集 （BwCluster）、存儲型資源集 （StorCluster）。

2.2 基于Min－Min的任務(wù)分配過程

根據(jù)任務(wù)偏好類型將任務(wù)分配到2.1節(jié)生成的3個聚類集資源上。具體算法步驟如下：

（1）若云任務(wù)列表CloudletList非空，根據(jù)式 （7）計算任務(wù)偏好類型，將任務(wù)添加到相應(yīng)的計算型任務(wù)隊列CompCloudletList、帶寬型任務(wù)隊列BwCloudletList、存儲型任務(wù)隊列StorCloudletList

其中，α，β，γ∈ ［0，1］，分別是云任務(wù)對3 種資源需求的經(jīng)驗系數(shù)。

（2）根據(jù)Min－Min算法分別將CompCloudletList分配到CompCluster聚類中、將BwCloudletList分配到BwCluster、將StorCloudletList分配到StorCluster中，具體算法步驟如下：

步驟1 判斷任務(wù)集合是否為空，不為空，則執(zhí)行步驟2；否則跳到步驟8。

步驟2 對于所有任務(wù)，分別計算其映射到資源集合上的預計完成時間ETCij。

步驟3 對于所有任務(wù)，求出它們映射到所有可用資源上的最早完成時間ECTij＝ETCij＋rtj，rtj表示機器j 的就緒時間。

步驟4 根據(jù)步驟3的結(jié)果，找出最早完成時間最小的任務(wù)ti和所對應(yīng)的資源rj。

步驟5 將任務(wù)ti映射到資源rj上；并將該任務(wù)從任務(wù)集合中刪除。

步驟6 更新資源rj的期望就緒時間rtj。

步驟7 更新其它任務(wù)在資源rj上的最早完成時間；回到步驟1。

步驟8 結(jié)束。

2.3 算法性能的改進

運用Min－Min算法進行調(diào)度時，總是選擇預計完成時間最小的任務(wù)執(zhí)行，導致性能差的資源利用率較低，導致負載不均衡。為了克服這個缺點，提出一種改進策略。旨在使完成時間最小的聚類集的資源不再處在空閑狀態(tài)，使完成時間最大的聚類集的資源從繁忙的調(diào)度中解放出來，從而提高資源利用率，保證負載均衡性。具體步驟如下：

步驟1 分別計算每個聚類的完成時間makespan，并兩兩計算聚類間的完成時間差D，分別記錄最大值Dmax、最小值Dmin，以及其所對應(yīng)的聚類集編號ii、jj。

步驟2 若Dmax＜閾值θ，則步驟4，否則執(zhí)行步驟3。

步驟3 如果newMakespan＜makespan，則繼續(xù)步驟3，否則轉(zhuǎn)步驟4。

在聚類ii中找到完成時間最小的任務(wù)Cloudleti以及它對應(yīng)的資源Vmj；在聚類jj中找到使Cloudleti完成時間最小的資源Vmk。將Cloudleti重新分配到Vmk上，并更新Vmj和Vmk的就緒時間。

步驟4 調(diào)度算法結(jié)束，退出程序。

3 仿真實驗及結(jié)果分析

3.1 實驗環(huán)境

本文算法在云計算仿真平臺CloudSim［15］下進行實驗驗證。仿真實驗是在模糊聚類基礎(chǔ)之上分別實現(xiàn)了Round Robin、Min－Min和改進算法，并針對時間跨度、平均響應(yīng)時間、平均資源利用率3個指標對算法進行了評價。

在仿真實驗中，任務(wù)和虛擬機資源分別是由任務(wù)發(fā)生器CloudletGenerator和資源發(fā)生器VmGenerator隨機生成的，每次實驗時，可以指定任務(wù)個數(shù)和每個任務(wù)屬性值的范圍，以及資源個數(shù)和每個資源性能的取值范圍。其具體實驗環(huán)境設(shè)置如下：

（1）云平臺參數(shù)設(shè)置：云平臺設(shè)有10個數(shù)據(jù)中心，每個數(shù)據(jù)中心4 臺主機，每臺主機配置如下：PE 個數(shù)為1，2，4個隨機生成、處理器速度為2000 MIPS、內(nèi)存4GB、磁盤1 TB、帶寬10 GB／s，數(shù)據(jù)中心特征：系統(tǒng)架構(gòu)為x86，操作系統(tǒng)為Linux，虛擬機為Xen。

（2）任務(wù)參數(shù)設(shè)置：根據(jù)用戶請求創(chuàng)建云任務(wù)，任務(wù)長度分布在區(qū)間 ［500，4000］，期望帶寬大小范圍為［1000，4000］，期望存儲空間大小范圍為 ［500，3000］。

（3）虛擬機資源參數(shù)設(shè)置：虛擬機CPU 個數(shù)取值為｛1，2，4｝，處理器速度范圍為 ［500，1000］，帶寬大小范圍為 ［500，3000］，存儲空間大小范圍為 ［512，2048］。

3.2 性能評價指標

Makespan表示任務(wù)總體完成時間，是指從第一個任務(wù)進入云平臺到最后一個任務(wù)完成的這段時間，即所有任務(wù)總體完成時間，如式 （8）所示

其中，rtj是資源j 的就緒時間。

任務(wù)響應(yīng)時間 （response time，RT）是指一個任務(wù)從進入云平臺開始到這個任務(wù)完成的這段時間，即任務(wù)的等待時間加上執(zhí)行時間。m 個任務(wù)的平均任務(wù)響應(yīng)時間（average response time，ART）計算公式如下

平均資源利用率 （average resource utilization ratio）通過以下公式計算得到

3.3 實驗及結(jié)果分析

仿真實驗的目的共有兩個：①將無聚類Min－Min和聚類后Min－Min算法進行比較，驗證聚類算法的優(yōu)越性；②研究在聚類基礎(chǔ)之上如何將任務(wù)進行調(diào)度使得算法性能更優(yōu)。為此，設(shè)置了下面兩組實驗。

3.3.1 實驗1：無聚類Min－Min和聚類后Min－Min算法執(zhí)行時間比較

在本次實驗中，設(shè)置云任務(wù)集中任務(wù)個數(shù)m＝ ｛100，200，300，400，500，600，800，1000｝，資源集中資源個數(shù)n＝ ｛10，20，30，40，50，60，80，100｝，由設(shè)計的隨機任務(wù)發(fā)生器和隨機資源發(fā)生器生成任務(wù)列表和資源列表，比較無聚類Min－Min和聚類后Min－Min的算法執(zhí)行時間，比較結(jié)果如圖1所示，其中橫軸表示每次調(diào)度中云任務(wù)個數(shù) （單位：個），縱軸表示算法的執(zhí)行時間 （單位：ms）。

圖1 算法執(zhí)行時間對比

由圖1可以看出，本次實驗中，聚類后的Min－Min算法執(zhí)行時間明顯小于無聚類的Min－Min算法，而且隨著任務(wù)數(shù)量的增加，聚類后算法效率提高的越多。當任務(wù)個數(shù)較多時，如m＝1000時，聚類后比無聚類的Min－Min算法在執(zhí)行時間上提高了207.38%。在任務(wù)個數(shù)較少時，如m＝100時，由于圖上縱軸間隔大，不能很明顯的顯示出兩個算法的好壞，而從實驗數(shù)據(jù)上來看，聚類后比無聚類的Min－Min算法在執(zhí)行時間上提高了18.18%。

3.3.2 實驗2：多次調(diào)度中，改進算法與傳統(tǒng)聚類算法的性能比較

在本次實驗中，設(shè)置云任務(wù)集合中任務(wù)個數(shù)m ＝｛100，110，120，130，140，150｝，資源集合中資源個數(shù)n的取值范圍為 ［15，25］，由設(shè)計的隨機發(fā)生器Cloudlet－Generator和VmGenerator生成任務(wù)列表和資源列表，分別比較 聚 類 后 的Round Robin （FCMRR 算 法）、Min－Min（FCMMM 算法）和本文算法3種算法的Makespan、平均響應(yīng)時間和平均資源利用率3項性能指標，比較結(jié)果如圖2、圖3、圖4 所示，其中橫軸均表示云任務(wù)個數(shù) （單位：個），縱軸依次表示Makespan （單位：s）、平均響應(yīng)時間（單位：s）、平均資源利用率。

圖2 Makespan對比

圖3 平均響應(yīng)時間對比

圖4 系統(tǒng)資源利用率對比

由圖2可見，改進算法在完成時間上，明顯低于FCMRR 算法和FCMMM 算法，這是因為改進算法在任務(wù)調(diào)度時采用的Min－Min算法，而Min－Min的調(diào)度目標就是基于最早完成時間的任務(wù)優(yōu)先調(diào)度，所以任務(wù)集合整體完成時間要比FCMRR 算法小，而改進算法又針對聚類間完成時間差異大于閾值θ 時進行了改進，使得完成時間比FCMMM 算法進一步縮短。從圖3 可以看出，改進算法使得任務(wù)的平均響應(yīng)時間顯著縮短。如，當任務(wù)數(shù)m＝由110變?yōu)?20 時，改進算法的平均響應(yīng)時間增加了3.17%，F(xiàn)CMRR、FCMMM 分別增加了6.48%、7.37%。由此可以看出，改進算法平均響應(yīng)時間增幅不大，比較穩(wěn)定。由圖4可以看出，F(xiàn)CMMM 算法平均資源利用率均在40%以下，因為采用傳統(tǒng)Min－Min算法，而Min－Min的缺點就是負載不均衡。改進算法針對聚類間完成時間差異大于閾值θ時進行了改進，系統(tǒng)資源利用率均在40%以上，略高于FCMRR 算法，明顯高于FCMMM 算法。

綜合以上分析可知，在云計算環(huán)境中，改進算法不僅執(zhí)行效率顯著提高，而且又能在一定程度上縮短任務(wù)集合的Makespan和任務(wù)的平均響應(yīng)時間，且能提高系統(tǒng)的資源利用率保持系統(tǒng)負載均衡性。

4 結(jié)束語

本文針對云計算環(huán)境下的獨立任務(wù)調(diào)度問題進行研究，總結(jié)了傳統(tǒng)調(diào)度算法的特點。通過深入分析云平臺中資源的特性，提出了一種改進模糊聚類云任務(wù)算法。該算法首先將資源特征矢量化，并基于這些特征進行模糊聚類，明顯縮小了任務(wù)選擇資源的范圍，從而有效降低了算法的執(zhí)行時間。最后，通過實驗分析可知，與傳統(tǒng)聚類算法相比，該算法一方面有效的縮短了云任務(wù)集合的完成時間和平均響應(yīng)時間，另一方面，從系統(tǒng)角度來看，顯著提高了系統(tǒng)的資源利用率，并保持了負載均衡性。

在下一步研究中，將會考慮資源和任務(wù)的動態(tài)性等因素，對調(diào)度算法作進一步研究，以適應(yīng)動態(tài)的云計算環(huán)境。

［1］Wang LZ，Ranjan R，Chen JJ，et al.Cloud computing：Methodology，systems and applications ［M］.Boca Raton：CRC Press，2012：20－25.

［2］Daniel Nurmi，Rich Wolski，Chris Grzegorczyk.The eucalyptus open source cloud computing system ［C］／／Proceeding of the Cluster Computing and the Grid.California：University of California，2009.

［3］CHEN Kang，ZHENG Weimin.Cloud computing：System instances and current research ［J］.Journal of Software，2009，20 （5）：1339－1347 （in Chinese）. ［陳康，鄭緯民.云計算：系統(tǒng) 實 例 與 研 究 現(xiàn) 狀 ［J］.軟 件 學 報，2009，20 （5）：1339－1347.］

［4］CHEN Quan，DENG Qianni.Cloud computing and its key techniques［J］.Journal of Computer Applications，2009，29（9）：2562－2567 （in Chinese）.［陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù) ［J］.計算機應(yīng)用，2009，29 （9）：2562－2567.］

［5］ZHOU Fachao，WANG Zhijian，YE Feng.Research of a novel cloud task scheduling algorithm ［J］.Journal of University of Science and Technology of China，2014，44 （7）：590－591（in Chinese）.［周發(fā)超，王志堅，葉楓.一種新型的云任務(wù)調(diào)度算法研究 ［J］.中國科學技術(shù)大學學報，2014，44 （7）：590－591.］

［6］HUANG Jun，WANG Qingfeng，LIU Zhiqin，et al.Cloud task scheduling based on resource state colony optimization ［J］.Computer Engineering and Design，2014，35 （9）：3305－3307（in Chinese）.［黃俊，王慶鳳，劉志勤，等.基于資源狀態(tài)蟻群算法的云計算任務(wù)分配 ［J］.計算機工程與設(shè)計，2014，35（9）：3305－3307.］

［7］YING Changtian，YU Jiong，YANG Xingyao.Energy－aware task scheduling algorithms in cloud computing ［J］.Microelectronics ＆ Computer，2012，29 （5）：189－191 （in Chinese）.［英昌甜，于炯，楊興耀.云計算環(huán)境下能量感知的任務(wù)調(diào)度算法 ［J］.微電子學與計算機，2012，29 （5）：189－191.］

［8］SHI Jinfa，JIAO Hejun.Optimization of cloud resource online scheduling on multidimensional QoS ［J］.Computer Engineering and Design，2013，34 （12）：4300－4302 （in Chinese）.［施進發(fā)，焦合軍.面向多維度QoS的云資源在線調(diào)度優(yōu)化研究 ［J］.計算機工程與設(shè)計，2013，34 （12）：4300－4302.］

［9］GUO Dong.Grid resources’selection based on applicationpreference based fuzzy clustering ［D］.Changchun：Jilin University，2009：15－20 （in Chinese）. ［郭東.基于應(yīng)用偏好模糊聚類的網(wǎng)格資源選擇 ［D］.長春：吉林大學，2009：15－20.］

［10］CHEN Zhigang，YANG Bo.Task scheduling based on multidimensional performance clustering of grid service resources［J］.Journal of Software，2009，20 （10）：2766－2774 （in Chinese）.［陳志剛，楊博.網(wǎng)格服務(wù)資源多維性能聚類任務(wù)調(diào)度 ［J］.軟件學報，2009，20 （10）：2766－2774.］

［11］NIE Jing.Research on grid resource based on fuzzy clustering［D］.Nanjing：Nanjing University of Information Science ＆Technology，2011：19－21 （in Chinese）. ［聶靖.網(wǎng)格資源模糊聚類研究 ［D］.南京：南京信息工程大學，2011：19－21.］

［12］GUO Fengyu，YU Long，TIAN Shengwei，et al.Workflow task scheduling algorithm based on resource clustering in cloud computing environment ［J］.Journal of Computer Applications，2013，33 （8）：2154－2157 （in Chinese）.［郭鳳羽，禹龍，田生偉，等，云計算環(huán)境下對資源聚類的工作流任務(wù)調(diào)度算法 ［J］.計算機應(yīng)用，2013，33 （8）：2154－2157.］

［13］LI Wenjuan，ZHANG Qifei，PING Lingdi，et al.Cloud scheduling algorithm based on fuzzy clustering ［J］.Journal on Communications，2012，33 （3）：146－154 （in Chinese）.［李文娟，張啟飛，平姈娣，等，基于模糊聚類的云任務(wù)調(diào)度算法 ［J］.通信學報，2012，33 （3）：146－154.］

［14］QU Fuheng，CUI Guangcai，LI Yanfang，et al.Fuzzy clustering algorithm and its application ［M］.Beijing：Defense Industry Press，2011：50－58 （in Chinese）.［曲福恒，崔廣才，李巖芳，等.模糊聚類算法及應(yīng)用 ［M］.北京：國防工業(yè)出版社，2011：50－58.］

［15］Buyya R，Ranjan R，Calheiros RN.Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit：challenges and opportunities ［C］／／Proceedings of the 7th High Performance Computing and Simulation Conference.New York，USA：IEEE Press，2009：21－24.