基于任務聚類的IABC云計算資源調度方法

鄭 洲，張曦煌，張 偉

(1.無錫工藝職業技術學院 信息中心，江蘇 無錫 214206；2.江南大學 物聯網學院，江蘇 無錫 214122)

0 引 言

云計算是全球信息通訊技術行業公認的發展核心，隨著技術的發展，云服務慢慢發展成為“自來水”式的服務，個人或企業無需關心計算存儲資源從何而來，只需按需付費，就可以獲得想要的數據存儲處理資源[1]。但是云資源的有限性和云計算需求的快速增長是當前云計算急需解決的問題，云資源不同的分配調度方法，使云服務的質量也大相徑庭，因此挖掘更優的云資源調度方法，對于提高云服務質量、提高用戶云服務體驗具有重要意義。

云計算資源調度是一個NP完全問題。Hadoop平臺的資源調度方法有先進先出調度方法、公平份額調度方法[2]、計算能力調度方法。傳統的調度方法有Min-Min算法、Max-Min算法、Sufferage算法、HEFT算法等。當前研究的熱點是基于群智能算法的調度方法，文獻[3]基于混沌擾亂策略提出了自適應蟻群算法，應用于云計算資源調度時收斂速度快、搜索能力強；文獻[4]融合了粒子群算法和蟻群算法用于云計算資源調度，使用粒子群算法的最優解用于初始化蟻群算法，克服了蟻群算法收斂速度慢的問題；文獻[5]提出了改進人工蜂群算法，成功避免了算法“早熟”問題，此方法可以縮短任務平均執行時間，但是當前對云計算資源調度的優化目標較單一，且對云計算資源調度的優化方法僅僅局限于對算法的優化。

本文從兩個方面改進了人工蜂群算法，一是改進了跟隨蜂蜜源選擇概率，二是改進了雇傭蜂蜜源搜索策略，此改進方法在偏好的優化目標上均具有最優表現；提出了任務聚類方法，將任務分為計算型、通信型、存儲型3類，從而有針對性地分配虛擬資源，此方法在任務完成時間和資源利用率上優勢明顯，且任務量越大優勢越明顯。

1 云計算資源調度問題建模

1.1 云計算任務模型

從實際情況來講，任務之間是具有時序關系的，某一任務執行完畢之后才能執行另一任務。為了直觀表達任務之間的時序約束關系，本文使用有向無循環圖(direct acyclic graph，DAG)建立任務模型，如圖1所示。

圖1 任務的DAG模型

圖1中任務t1為起始節點，任務t9為結束節點。對DAG模型定義兩個集合，分別為集合T和E，T為所有任務的集合，E為任務ti與tj之間邊eij的集合，eij表示任務ti與tj之間存在時序關系，任務ti執行完畢后才能執行任務tj。

1.2 云計算資源模型

1.3 云計算約束模型

本文考慮費用約束、完成時間約束、可靠性約束等3個方面的約束條件。

費用約束就是完成任務產生的費用不能高于用戶的費用要求。假設任務ti分配到了虛擬機資源vmki上，費用約束即為

(1)

式中：S.C為完成所有任務的費用，n為任務數量，U.C為用戶給出的費用上限。

完成時間約束就是所有任務最終的完成時間不能超過用戶給定的截止時間。即對?ti，有

(2)

式中：S.T為完成所有任務的時間，U.T為用戶給出的任務完成截止時間。

可靠性約束就是所有任務使用的虛擬機可靠性要大于等于用戶的可靠性要求，即

(3)

式中：S.R為所有虛擬機的可靠性最小值，U.R為用戶給出的可靠性值。

1.4 云計算服務質量模型

本文資源調度的優化目標包括費用、完成時間、可靠性等3個方面，因此服務質量模型需要分別建立費用、完成時間、可靠性的適應度函數。

(4)

(2)完成時間適應度函數的建立。將任務ti的最早開始時間記為EST(ti,vmj)，則EST(ti,vmj)

EST(ti,vmj)=maxavail(vmj),EFT(tk)+cki

(5)

(6)

(4)服務質量模型的建立。根據以上分析，使用傳統的加權方式將多個優化目標綜合為一個優化目標，即

(7)

式中：α、β、γ分別為權值系數，其值的大小反應優化目標的偏好，那么通過調整權值就可以改變優化中心。要求0≤α,β,γ≤1，且α+β+γ=1。

2 改進人工蜂群算法的任務調度

人工蜂群算法是模擬蜂群采蜜行為的群體智能算法，每個蜜源位置代表一個可行解，蜂群找到最優蜜源的速度代表算法的收斂速度，蜂群尋找最優蜜源的過程就是算法尋優的過程[6]。

2.1 人工蜂群算法原理

在人工蜂群算法中使用到的參數包括種群數量SN、算法最大迭代次數MaxCycle、蜜源停留最大次數Limit。

(1)初始化蜜源，隨機生成N個蜜源[7]，每個蜜源記為xi=(xi1,xi2,…,xid),d為任務的數量，xij表示第j個任務在虛擬機xij上執行。蜜源初始化為

xij=lbj+rand(0,1)(ubj-lbj)

(8)

式中：i=1,2,…,N,ubj、lbj分別為可行域維度j上的最大值和最小值，rand(0,1)為(0,1)間的隨機數。若xij為非整數，則通過取整轉化為整數。

(2)對蜜源收益度進行評價，評價函數為

(9)

式中：fi為優化問題的目標函數。

(3)雇傭蜂進行鄰域搜索。每只雇傭蜂在原蜜源附近搜索新蜜源，比較新蜜源和原蜜源的適應度值，保留適應度大的蜜源。蜜源搜索方式為

Vij=xij+rij(xij-xkj)

(10)

式中：Vij為雇傭蜂搜尋到的新食物源，xij為當前食物源，xkj為隨機選取的異于當前食物源的另一食物源，rij為[-1,1]的隨機數。

(4)跟隨蜂的蜜源選擇。雇傭蜂選擇蜜源后通過搖擺舞將信息傳遞給跟隨蜂，跟隨蜂依據各蜜源適應度值選擇蜜源，即

(11)

式中：pi為跟隨蜂選擇某一蜜源的概率。跟隨蜂進行蜜源選擇后變為雇傭蜂。

(5)偵查蜂搜索策略。若雇傭蜂在某蜜源鄰域搜索次數超過Limit次，則放棄此處，雇傭蜂轉換為偵查蜂，按照式(8)產生新蜜源彌補放棄的蜜源。這樣可以使人工蜂群算法跳出局部極值。

2.2 改進人工蜂群算法(IABC)

2.2.1 改進跟隨蜂蜜源選擇概率

在傳統的人工蜂群算法中，跟隨蜂的蜜源選擇依據輪盤賭方式進行，這種方式能夠引導跟隨蜂快速收斂于較優解，增加了在較優解附近的細致搜索，但是即使最差解也有被選擇的可能，這樣就造成了跟隨蜂資源的浪費，產生了一些極差解附近的無效搜索。為了解決這一問題，本文對跟隨蜂的蜜源選擇概率進行改進，即

(12)

式中：fitmin為所有蜜源適應度最小值。從上式可以看出，跟隨蜂的蜜源選擇概率引入了適應度最小值，選擇概率正比于適應度跨度，極大地減小了跟隨蜂選擇“劣質解”的概率，使更多的跟隨蜂能夠選擇較優解，產生有效搜索。

2.2.2 改進蜜源搜索策略

在傳統的人工蜂群算法中，雇傭蜂的蜜源搜索策略為式(10)，這種搜索策略具有很強的隨機性和盲目性。本文對雇傭蜂的搜索策略提出改進，前期使雇傭蜂具有很大的搜索范圍，后期使雇傭蜂快速收斂至最優解，提高收斂速度，即

(13)

其中

(14)

式中：Vij為雇傭蜂搜尋到的新食物源，xij為當前食物源，xkj為隨機選取的異于當前食物源的另一食物源，rij為[-1,1]的隨機數，c∈[cmin,cmax]為學習因子，xbest為當前最優食物源，fitbest為當前最優食物源適應度，fitgoal為目標適應度。上式表示，當最優適應度值為目標值的95%之前，使用隨機搜索方式，且學習因子較大，實現了算法的大范圍搜索，隨著迭代次數Cycle增大，學習因子逐漸減小，有利于較優解附近的細致搜索，當適應度值增加大95%目標值時，算法開始向全局最優解xbest靠近，增加收斂速度。

2.3 改進人工蜂群算法的任務調度

首先介紹任務初始化的方法，而后給出基于改進人工蜂群算法的任務調度步驟。

任務的初始化包括任務的分組和組內的優先級排序。任務的分組就是根據DAG圖，將沒有依賴關系的任務分為一組，便于任務的并行執行。如圖1所示將10個任務分為了5組。組內任務的優先級排序依據下式給出

(15)

式中：rank(ti)為任務ti的優先級，tj為ti的直接后繼節點，Succ(ti)為任務ti所有直接后繼節點的集合。分析式(15)可以看出，計算任務優先級從最后一個組開始，逐漸計算至第一組。

使用改進人工蜂群算法對計算資源進行調度的步驟為：

步驟1 初始化參數。給出虛擬機的運行價格、可靠性；人工蜂群算法最大迭代次數Maxcycle、蜂群規模SN，食物源最大停留次數Limit；

步驟2 初始化任務。就是將任務進行分組和優先級排序；

步驟3 初始化蜜源。根據式(8)對蜜源進行初始化；

步驟4 雇傭蜂的蜜源搜索。雇傭蜂使用改進的搜索方式，前期進行大范圍搜索，后期快速收斂至最優解；

步驟5 跟隨蜂的蜜源選擇。使用改進的選擇方法，增加跟隨蜂對優質解的選擇概率；

步驟6 偵查蜂搜索策略。在某一蜜源附近搜索次數超過Limit次而沒有更新時則放棄此蜜源，隨機生成一蜜源進行補充；

步驟7 達到搜索精度要求或者達到最大搜索次數時，算法結束，輸出最優解。

3 基于任務聚類的IABC調度方法

當前對云計算資源的調度策略研究主要集中在對調度算法的優化上，而對云任務缺少足夠的分析。本文使用模糊C均值聚類方法對任務進行預處理，對具有相似資源需求的任務進行聚類，從而有針對性地分配云資源。

3.1 任務聚類方法

本文將任務分為計算型、帶寬通信型、存儲型任務3類，因此選擇任務的計算量需求tcomp、任務期望帶寬tbw、任務期望存儲空間tstor作為任務的特征向量T=(tcomp,tbw,tstor)，其中計算量需求為tcimp=tlength/tPE,tlength為任務長度，tPE為任務期望的PE數量。

對任務的特征向量歸一化處理后，使用模糊C均值聚類方法[8,9]對任務進行分類，將任務分為計算型、帶寬通信型、存儲型任務3類，然后根據任務分類有針對性地進行資源調度，模糊C均值聚類原理簡單，這里不再贅述。

3.2 虛擬機評價方法

對任務聚類后，為了有針對性地分配虛擬資源，也需要給出虛擬資源的評價方法。與任務的分配類型相對應，需要對虛擬資源的計算能力、帶寬通信能力、存儲能力進行評價，即第j個虛擬資源的特征向量為vmj=(vmjcomp,vmjbw,vmjstor)，以計算能力為例給出評價公式，另外兩個屬性與計算能力的評價公式一致，即

(16)

3.3 基于任務聚類的IABC調度步驟

對任務進行分類、虛擬機資源進行評價后，使用改進人工蜂群算法進行針對性的資源分配，其步驟為：

步驟1 初始化參數。給出虛擬機的運行價格、可靠性；人工蜂群算法最大迭代次數Maxcycle、蜂群規模SN，食物源最大停留次數Limit;

步驟2 初始化任務。就是將任務進行分組、優先級排序、聚類，將任務分為計算性、通信型、存儲型3類;

步驟3 初始化蜜源。根據式(8)對蜜源進行初始化;

步驟4 雇傭蜂的蜜源搜索。雇傭蜂使用改進的搜索方式，前期進行大范圍搜索，后期快速收斂至最優解;

步驟5 跟隨蜂的蜜源選擇。使用改進的選擇方法，增加跟隨蜂對優質解的選擇概率;

步驟6 偵查蜂搜索策略。在某一蜜源附近搜索次數超過Limit次而沒有更新時則放棄此蜜源，隨機生成一蜜源進行補充;

步驟7 達到搜索精度要求或者達到最大搜索次數時，算法結束，輸出最優解，否則轉至步驟4。

4 仿真實驗驗證

4.1 實驗設計

使用CloudSim云計算平臺仿真模擬器作為實驗平臺，在jdk7.0和eclipse環境編程，增加了DAG生成模塊作為擴展。本文的創新點包括兩大方面，一是改進了人工蜂群算法，二是提出了基于任務聚類的調度方法，因此驗證實驗分為兩個實驗。

實驗二：驗證任務聚類在資源調度中的作用。任務參數設置為：任務長度在[500,4000]范文內取值，帶寬取值范圍為[1000,4000]，任務期望存儲空間取值范圍為[500,3000]，輸入輸出數據量范圍為[10000,50000]。虛擬資源參數設置為：虛擬機CPU數量在{1,2,3,4}中選取，處理速度范圍為[500,1000]，帶寬范圍為[500,3000]，存儲空間取值范圍為[512,2048]。實驗分兩組進行，一是任務量較少時，將聚類IABC調度結果與無聚類IABC算法、Min-Min算法、K-Min算法調度結果進行比較；二是任務量較多時，上述算法的調度結果對比。

4.2 實驗結果及分析

實驗一：分別使用異構最早完成時間算法(HEFT)、傳統人工蜂群算法(ABC)、優秀種群引導的人工蜂群算法(GABC)、NIABC算法[10]及本文的改進算法進行資源調度，比較資源調度性能。偏好于花費的調度結果如圖2所示。

圖2 偏好執行費用時各算法調度結果

從圖2中可以看出，本文提出的改進人工蜂群算法在平均完成時間和平均執行費用上均少于其它算法，這是因為改進了跟隨蜂蜜源選擇策略，增加了優質解被選擇概率，改進了雇傭蜂蜜源搜索策略，兼顧了算法前期的大范圍搜索和后期向最優解收斂，這樣極大地節約了任務完成時間。另外由于在參數設置時偏好于執行費用，所以資源調度時選擇費用較低的虛擬機，但是費用低的虛擬機一般可靠性較差，所以改進人工蜂群算法在平均可靠性上沒有優勢。

偏好于完成時間的調度結果如圖3所示。

圖3 偏好完成時間時各算法調度結果

從圖3中可以看出，本文提出的改進人工蜂群算法相比于其它算法在平均完成時間和平均執行費用上具有優勢。因為偏好于任務完成時間，所以會挑選執行速度快的虛擬機，但是處理能力強的虛擬機未必可靠性就高，其隨機性較大，因此改進人工蜂群算法在平均可靠性上沒有優勢。

偏好于可靠性的調度結果如圖4所示。

圖4 偏好可靠性時各算法調度結果

從圖3中可以看出本文提出的改進人工蜂群算法具有最高的平均可靠性，但是由于偏好于可靠性，使得任務等待可靠性高的虛擬機執行，使任務完成時間增加，所以本文改進算法在完成時間上不再具有優勢；而且虛擬資源可靠性和價格成正相關關系，所以高可靠性導致了高花費，所以改進算法的花費也最高。

分析以上3個實驗，可以看出本文提出的改進算法在偏好方面均能取得最優解，且優勢明顯，所以根據任務實際調整優化參數，就可以調整優化中心，實現不同目標優化問題。

實驗二：任務量較少時，任務量取為10-150遞增，相應地虛擬機數量由3-20遞增，使用聚類IABC算法、無聚類IABC算法、Min-Min算法、K-Min算法進行多次資源調度，統計運行結果的平均值，結果如圖5所示。

圖5 任務較少時的調度結果

從圖5(a)中可以看出，本文的聚類IABC算法相比于其它算法在完成時間上具有優勢，但是這種優勢非常不明顯，這是由于任務量過少，改進人工蜂群算法的快速搜索能力未能完全表現，而且任務聚類也會消耗一些時間，使優勢更加不明顯。從圖5(b)中可以看出，聚類IABC算法的資源利用率最高，且非常穩定，相比于其它算法優勢明顯。

任務量較多時，任務量由100-1000遞增，相應地虛擬機數量由8-50遞增，使用聚類IABC算法、無聚類IABC算法、Min-Min算法、K-Min算法進行多次資源調度，統計運行結果的平均值，結果如圖6所示。

圖6 任務多時的調度結果

從圖6(a)中可以看出，本文的聚類IABC算法相比于其它調度方法在完成時間上優勢明顯，而且隨著任務量的增加這種優勢愈加明顯，這是因為任務聚類和虛擬資源評價，使虛擬資源相對于任務分配時更具有針對性，使計算型、通信型、存儲型資源能夠相應分配到計算型、通信型、存儲型任務上；從圖6(b)可以看出，本文的聚類IABC算法調度的資源利用率最高，充分使用了虛擬資源，能夠減少虛擬資源的占有。

5 結束語

本文在提出改進人工蜂群算法的基礎上，提出了基于任務聚類的改進人工蜂群資源調度方法，具體地講，本文完成了以下工作：

(1)改進了跟隨蜂蜜源選擇概率，增大了優質解被選擇的概率，從而增加了在優質解附近的“有效搜索”概率；

(2)改進了雇傭蜂的蜜源選擇策略，使算法前期大范圍搜索，達到一定精度后快速收斂至最優解附近，兼顧了搜索范圍和收斂速度；

(3)經仿真實驗驗證，改進人工蜂群算法在所“偏好”方面均取得最優解，所有只需要調整優化重心，就可以使用本文的改進方法進行不同方面的優化；

(4)在改進人工蜂群算法基礎上增加了任務聚類算法，通過對任務進行聚類，將任務分為不同類型，使得在資源分配時具有很強的針對性；

(5)經仿真驗證，在任務量較大和較少時，聚類IABC算法在完成時間和資源利用率上均具有優勢，但是任務量較少時優勢不明顯，而任務量較大時優勢明顯，且任務量越大優勢越明顯。