基于改進蟻群優(yōu)化算法的云計算資源調(diào)度

肖耀濤

(廣東郵電職業(yè)技術(shù)學(xué)院， 軟件學(xué)院， 廣東, 廣州 510630)

0 引言

隨著網(wǎng)絡(luò)技術(shù)的高速發(fā)展，云計算通過并行計算與分布式計算逐步發(fā)展而來[1]。傳統(tǒng)的服務(wù)模式因云計算的應(yīng)用發(fā)生變化。當前云計算主要是將數(shù)據(jù)中心的各種資源采用虛擬化技術(shù)形成虛擬資源池，并通過虛擬貨源池將資源提供給用戶[2]?，F(xiàn)階段云計算相關(guān)研究中，資源分配與任務(wù)調(diào)度十分熱門，因為相較于傳統(tǒng)并行計算及其他計算方法，云計算具有自治性以及動態(tài)性[3]。

為研究云計算資源調(diào)度問題，許多學(xué)者對此進行研究。如黃偉建等[4]研究了基于混沌貓群算法的云計算多目標任務(wù)調(diào)度，李衛(wèi)星[5]研究基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化,但當資源量增大時，依然存在難以調(diào)度等問題。

蟻群優(yōu)化算法來源于自然界螞蟻覓食時，找到食物源至蟻穴的最短路徑[6]。每只螞蟻在尋找食物時，為了防止迷路，在爬行過程中會將一種化學(xué)物質(zhì)信息素(Pheromone)釋放在路徑上[7]，使得其爬行范圍可以被其他螞蟻感知到。當同一路徑上走過的螞蟻逐漸增多，該路徑上的信息素濃度也逐漸提高，因此螞蟻選擇路徑覓食概率也隨之增加，導(dǎo)致此路徑信息素濃度持續(xù)加大。蟻群優(yōu)化算法的求解過程中，并不需要人工干預(yù)，并且求解結(jié)果不依靠初始路線規(guī)劃，同時此算法復(fù)雜度較低。但蟻群優(yōu)化算法的計算規(guī)模較小[8]，一旦應(yīng)用場景規(guī)模較大時，該算法穩(wěn)定性較低。因此，現(xiàn)有的蟻群優(yōu)化算法并不適合大規(guī)模的云計算資源環(huán)境[9]，由于其收斂性在資源數(shù)量增多時變得較差，極易陷入局部最優(yōu)解[10]。因此，本文研究基于改進蟻群優(yōu)化算法的云計算資源調(diào)度，設(shè)計云計算資源調(diào)度模型，應(yīng)用改進蟻群優(yōu)化算法實現(xiàn)云計算資源的最佳調(diào)度，便于資源規(guī)模達到用戶需求。

1 基于改進蟻群優(yōu)化算法的云計算資源調(diào)度研究

1.1 云計算資源調(diào)度模型

很多復(fù)雜的資源都存儲在云計算模塊內(nèi)，為快速完成并解決用戶資源調(diào)度問題，必須選擇最佳的資源調(diào)度方案。采用Map/Reduce思想的編程模型規(guī)劃云計算模型，設(shè)計資源調(diào)度模型如圖1所示，該模型采用改進蟻群優(yōu)化算法對大規(guī)模云計算資源數(shù)據(jù)集進行調(diào)度處理。對云計算資源進行調(diào)度，用戶提交數(shù)據(jù)集后，調(diào)度過程進行切分數(shù)據(jù)集，即進行數(shù)據(jù)集分布式化，將用戶提交的數(shù)據(jù)集切分為多個子數(shù)據(jù)集，并移交至調(diào)度中心，最終根據(jù)改進蟻群優(yōu)化算法，向虛擬資源節(jié)點調(diào)度每個子數(shù)據(jù)集。

圖1 資源調(diào)度模型

1.2 資源調(diào)度的相關(guān)定義

依據(jù)算法向m個虛擬機節(jié)點上(m

(1)n個待執(zhí)行獨立資源的集合用T={T1,T2,…,Tj,…,Tn}描述；

(2)m個虛擬機處理資源的節(jié)點用V={V1,V2,…,Vi,…,Vm}描述；

(3) 虛擬機節(jié)點Vi單位時間內(nèi)處理的指令數(shù)用MIPSi描述，以每秒百萬計，m個虛擬機的計算能力用MIPS={MIPS1,MIPS2,…,MIPSm}描述，即計算速度；

(4) 用矩陣M描述資源與虛擬機節(jié)點之間的映射關(guān)系，若資源Tj被分配至虛擬機節(jié)點Vi上進行調(diào)度，則Mij=1，否則Mij=0，其中Mij為矩陣中的元素，M的形式如式(1)，

(1)

(5) 第i個虛擬機內(nèi)第j個子數(shù)據(jù)集的執(zhí)行時間，即資源的期望執(zhí)行時間的表達式如式(2)：

(2)

可由上述矩陣計算，每個虛擬機Vi執(zhí)行子數(shù)據(jù)集的時間，如式(3)，

(3)

式中，n表示虛擬機Vi執(zhí)行的子數(shù)據(jù)集數(shù)量，Time(i,h)表示虛擬機Vi執(zhí)行第j個子數(shù)據(jù)集的時間。

1.3 基于改進蟻群算法的優(yōu)化調(diào)度

1.3.1 蟻群優(yōu)化算法

若云計算環(huán)境內(nèi)，有待處理資源n個，等待執(zhí)行任務(wù)虛擬機m個，螞蟻x只，當螞蟻尋找食物時，信息素會殘留在路徑上，依據(jù)信息素濃度，下一只螞蟻選擇覓食路徑，用式(4)表示路徑選擇的概率：

(4)

隨著螞蟻最佳路徑選擇時，信息素濃度產(chǎn)生變化，用式(5)表示:

(5)

1.3.2 蟻群算法的改進

(1) 改進選擇下一節(jié)點概率計算公式

螞蟻從當前節(jié)點i選擇節(jié)點j，在改進算法中，用式(6)表示：

(6)

式中，q為隨機數(shù)。

當qq0，當前節(jié)點i到j(luò)的距離反比函數(shù)由上述啟發(fā)信息函數(shù)ηij采用，利用ηjT作為改進算法的啟發(fā)函數(shù)。設(shè)定期望值，通過節(jié)點j到目標節(jié)點的距離，目標點距離最近節(jié)點期望值最大，表示距離目標更近的節(jié)點更會被螞蟻選擇。

(2) 改進啟發(fā)因子β

在標準蟻群算法初始階段中，信息素值是固定的，β值是固定的，由式(6)可知，解的搜索并未由此時的信息素指導(dǎo)，信息素值會隨著算法運行，而依據(jù)不同路徑持續(xù)更新，使全局最優(yōu)解信息體現(xiàn)出來，提升了此時信息素的作用，所以將啟發(fā)因子β設(shè)計為一個減函數(shù)，用式(7)表示，其具有迭代次數(shù)。

β(i)=b1/i

(7)

式中，i表示當前迭代次數(shù)，b是常數(shù)。隨著增加循環(huán)次數(shù)，β值逐漸變小。β值在初始階段較大，是因為探索路徑依賴于啟發(fā)信息，使算法的收斂速度提升。后期搜索路徑利用信息素和啟發(fā)值，使信息素的指導(dǎo)作用充分發(fā)揮，在選擇路徑時依賴信息素強度。

(3) 改進信息素的更新

當螞蟻選中邊(i,j)時，更新邊(i,j)上的信息素，利用式(8)進行：

τij=(1-ρ)τij+ρΔτij

Δτij=Q/lk

(8)

式中，本次迭代時，lk表示第k只螞蟻已走過路徑的長度。

為提升螞蟻選擇其他邊的概率，要在螞蟻選擇一條邊時，適量減少此邊的信息素，全部螞蟻走過一次循環(huán)后，為使搜索最佳路徑的概率逐漸加大，需進行信息素的全局更新，通過式(9)執(zhí)行，

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(9)

式中，Lgbest表示現(xiàn)階段獲得的最優(yōu)路徑長度。

1.3.3 改進蟻群算法的云計算資源調(diào)度步驟

(1) 對云計算虛擬機資源數(shù)、節(jié)點數(shù)、迭代次數(shù)以及信息素進行初始化，即初始化算法參數(shù)。

(2) 在虛擬機節(jié)點上，隨機放置X只螞蟻。

(3) 對螞蟻個體移動至下一虛擬機節(jié)點的概率進行計算，然后將螞蟻依照計算結(jié)果移動。

(4) 對螞蟻走過路徑的信息素進行局部更新，然后將對應(yīng)的禁忌表進行修改。

(5) 對步驟(2)—(4)進行重復(fù)，直至某一條可行的路徑被蟻群中的每個螞蟻個體找到。

(6) 對所有路徑的信息素進行全局更新。

(7) 將迭代次數(shù)增加，獲取調(diào)度過程的最優(yōu)解是指，其值已達到預(yù)設(shè)的最大迭代次數(shù)，最終停止搜索。

2 實驗結(jié)果與分析

采用CloudSim仿真平臺進行實驗，其支持云計算的基礎(chǔ)設(shè)施建設(shè)，利用datacenterbroker實現(xiàn)云任務(wù)到虛擬機的匹配。模擬采用500個虛擬計算資源進行調(diào)度，并選取文獻[4]基于混沌貓群算法的云計算多目標任務(wù)調(diào)度算法、文獻[5]基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化算法與本文算法進行對比，分析不同算法下的負載均衡度，結(jié)果如圖2所示。由圖2可知，隨著資源個數(shù)的增加，不同算法的負載均衡度也隨之增加，基于混沌貓群算法的云計算多目標任務(wù)調(diào)度算法在資源個數(shù)為200、400、500時，負載均衡度要高于基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化算法與本文算法，基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化算法在資源個數(shù)為100、300時，負載均衡度高于基于混沌貓群算法的云計算多目標任務(wù)調(diào)度算法與本文算法，但本文算法的負載均衡度始終最低，因此本文算法在實現(xiàn)負載均衡方面具有較好效果。

圖2 不同算法負載均衡度比較

3種算法在虛擬機上的負載均衡相對標準差統(tǒng)計結(jié)果如圖3所示。由圖3可知，基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化算法的相對標準差較大，始終大于本文算法與基于混沌貓群算法的云計算多目標任務(wù)調(diào)度算法，說明資源分配并不均勻，而本文算法的相對標準差始終最低。這是由于本文方法利用蟻群算法的信息素的擴散和更新的特性，將云計算資源調(diào)度進行了全局搜索，使資源進行較為均勻的分配。

圖3 資源分配相對標準差

對比不同算法的總效用值，分析結(jié)果如圖4所示。

由圖4可知，隨著資源個數(shù)的增加，不同算法的調(diào)度總效用值也隨之提升，但基于混沌貓群算法的云計算多目標任務(wù)調(diào)度算法與基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化算法的調(diào)度總效用值始終低于本文算法，本文算法調(diào)度總效用始終都是最大的。這是由于本文算法利用蟻群優(yōu)化算法將選擇節(jié)點的范圍擴大，避免陷入局部最優(yōu)解，進而可最大程度滿足用戶資源調(diào)度需求。

圖4 不同算法的總效用值對比

對不同資源個數(shù)下3種算法調(diào)度所需的迭代次數(shù)進行計算，分析不同算法的收斂特性，分析結(jié)果如圖5所示。由圖5可知，3種算法隨著資源個數(shù)的增加產(chǎn)生迭代，但基于混沌貓群算法的云計算多目標任務(wù)調(diào)度算法與基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化算法的迭代次數(shù)始終大于本文算法，且隨著資源個數(shù)增加，迭代次數(shù)變化波動較大，說明本文算法有較好的收斂特性，僅需較少的迭代次數(shù)便可達到較好的資源調(diào)度效果。

圖5 不同算法收斂特性對比

在不同資源個數(shù)下，對不同算法調(diào)度后的資源利用率進行比較，分析資源庫應(yīng)用不同算法的資源調(diào)度情況，分析結(jié)果如圖6所示。

圖6 不同算法資源利用率對比

對圖6進行分析，隨著資源個數(shù)的上升，不同算法調(diào)度后的資源利用率也逐漸下降，基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化算法應(yīng)用后的資源利用率始終高于基于混沌貓群算法的云計算多目標任務(wù)調(diào)度算法，但本文算法應(yīng)用后的資源利用率同時高于2種用來比較的算法。表明本文算法應(yīng)用后可提升資源庫中資源利用率，優(yōu)勢顯著。這是由于本文算法應(yīng)用信息素及時更新資源調(diào)度節(jié)點，避免了計算的冗余，使資源調(diào)度的計算量減少，且單位時間內(nèi)能夠處理更多的資源量。

3 總結(jié)

本文研究基于改進蟻群優(yōu)化算法的云計算資源調(diào)度，對云計算資源調(diào)度問題進行深入分析。采用云計算模型并通過對蟻群優(yōu)化算法進行改進，以達到最佳的云計算資源調(diào)度。在未來階段，可在此基礎(chǔ)上進行加深研究，提升算法的運行時間，使用戶可以更高效地進行資源調(diào)度。