改進模糊聚類的云任務調度算法

胡 蒙，苑迎春，王雪陽

（河北農業大學 信息科學與技術學院，河北 保定071001）

0 引 言

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

本文針對現有算法的不足之處，提出一種改進模糊聚類的云任務調度算法。該算法是在傳統的模糊聚類基礎上進行改進的任務調度算法，依據設定的閾值對任務分配實施調整，最大限度體現任務調度的公平性，有助于提高系統的資源利用率。

1 問題描述

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

1.1 任務模型

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

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

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

1.2 資源模型

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

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

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

其中，a、b、c分別表示資源的3項性能參數的經驗系數。

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

2 基于模糊聚類和Min－Min的調度算法

本文考慮到任務選擇資源的盲目性對任務執行情況有一定程度的影響，提出了基于資源模糊聚類的任務調度算法，在聚類內使用Min－Min啟發式算法進行調度，并在此基礎之上進行了適當的改進，以提高系統資源利用率，保證系統負載均衡性。算法主要分為模糊聚類、任務分配和算法改進3個過程。

2.1 資源聚類劃分過程

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

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

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

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

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

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

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

若J＜閾值ε，或達到迭代次數t，則聚類結束。否則，繼續步驟6。

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

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

2.2 基于Min－Min的任務分配過程

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

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

其中，α，β，γ∈ ［0，1］，分別是云任務對3 種資源需求的經驗系數。

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

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

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

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

步驟4 根據步驟3的結果，找出最早完成時間最小的任務ti和所對應的資源rj。

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

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

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

步驟8 結束。

2.3 算法性能的改進

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

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

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

步驟3 如果newMakespan＜makespan，則繼續步驟3，否則轉步驟4。

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

步驟4 調度算法結束，退出程序。

3 仿真實驗及結果分析

3.1 實驗環境

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

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

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

（2）任務參數設置：根據用戶請求創建云任務，任務長度分布在區間 ［500，4000］，期望帶寬大小范圍為［1000，4000］，期望存儲空間大小范圍為 ［500，3000］。

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

3.2 性能評價指標

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

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

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

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

3.3 實驗及結果分析

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

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

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

圖1 算法執行時間對比

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

3.3.2 實驗2：多次調度中，改進算法與傳統聚類算法的性能比較

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

圖2 Makespan對比

圖3 平均響應時間對比

圖4 系統資源利用率對比

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

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

4 結束語

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

在下一步研究中，將會考慮資源和任務的動態性等因素，對調度算法作進一步研究，以適應動態的云計算環境。

［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）. ［陳康，鄭緯民.云計算：系統 實 例 與 研 究 現 狀 ［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）.［陳全，鄧倩妮.云計算及其關鍵技術 ［J］.計算機應用，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）.［周發超，王志堅，葉楓.一種新型的云任務調度算法研究 ［J］.中國科學技術大學學報，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）.［黃俊，王慶鳳，劉志勤，等.基于資源狀態蟻群算法的云計算任務分配 ［J］.計算機工程與設計，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）.［英昌甜，于炯，楊興耀.云計算環境下能量感知的任務調度算法 ［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）.［施進發，焦合軍.面向多維度QoS的云資源在線調度優化研究 ［J］.計算機工程與設計，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）. ［郭東.基于應用偏好模糊聚類的網格資源選擇 ［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）.［陳志剛，楊博.網格服務資源多維性能聚類任務調度 ［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）. ［聶靖.網格資源模糊聚類研究 ［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）.［郭鳳羽，禹龍，田生偉，等，云計算環境下對資源聚類的工作流任務調度算法 ［J］.計算機應用，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）.［李文娟，張啟飛，平姈娣，等，基于模糊聚類的云任務調度算法 ［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）.［曲福恒，崔廣才，李巖芳，等.模糊聚類算法及應用 ［M］.北京：國防工業出版社，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.