鄭 洲，張曦煌，張 偉

(1.無錫工藝職業(yè)技術學院 信息中心，江蘇 無錫 214206；2.江南大學 物聯(lián)網(wǎng)學院，江蘇 無錫 214122)

0 引 言

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

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

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

1 云計算資源調(diào)度問題建模

1.1 云計算任務模型

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

圖1 任務的DAG模型

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

1.2 云計算資源模型

1.3 云計算約束模型

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

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

(1)

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

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

(2)

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

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

(3)

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

1.4 云計算服務質(zhì)量模型

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

(4)

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

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

(5)

(6)

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

(7)

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

2 改進人工蜂群算法的任務調(diào)度

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

2.1 人工蜂群算法原理

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

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

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

(8)

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

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

(9)

式中：fi為優(yōu)化問題的目標函數(shù)。

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

Vij=xij+rij(xij-xkj)

(10)

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

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

(11)

式中：pi為跟隨蜂選擇某一蜜源的概率。跟隨蜂進行蜜源選擇后變?yōu)楣蛡蚍洹?/p>

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

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

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

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

(12)

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

2.2.2 改進蜜源搜索策略

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

(13)

其中

(14)

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

2.3 改進人工蜂群算法的任務調(diào)度

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

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

(15)

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

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

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

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

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

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

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

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

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

3 基于任務聚類的IABC調(diào)度方法

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

3.1 任務聚類方法

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

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

3.2 虛擬機評價方法

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

(16)

3.3 基于任務聚類的IABC調(diào)度步驟

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

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

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

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

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

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

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

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

4 仿真實驗驗證

4.1 實驗設計

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

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

4.2 實驗結果及分析

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

圖2 偏好執(zhí)行費用時各算法調(diào)度結果

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

偏好于完成時間的調(diào)度結果如圖3所示。

圖3 偏好完成時間時各算法調(diào)度結果

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

偏好于可靠性的調(diào)度結果如圖4所示。

圖4 偏好可靠性時各算法調(diào)度結果

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

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

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

圖5 任務較少時的調(diào)度結果

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

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

圖6 任務多時的調(diào)度結果

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

5 結束語

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

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

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

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

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

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