基于改進蟻群優化算法的云計算資源調度

肖耀濤

(廣東郵電職業技術學院， 軟件學院， 廣東, 廣州 510630)

0 引言

隨著網絡技術的高速發展，云計算通過并行計算與分布式計算逐步發展而來[1]。傳統的服務模式因云計算的應用發生變化。當前云計算主要是將數據中心的各種資源采用虛擬化技術形成虛擬資源池，并通過虛擬貨源池將資源提供給用戶[2]。現階段云計算相關研究中，資源分配與任務調度十分熱門，因為相較于傳統并行計算及其他計算方法，云計算具有自治性以及動態性[3]。

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

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

1 基于改進蟻群優化算法的云計算資源調度研究

1.1 云計算資源調度模型

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

圖1 資源調度模型

1.2 資源調度的相關定義

依據算法向m個虛擬機節點上(m

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

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

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

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

(1)

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

(2)

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

(3)

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

1.3 基于改進蟻群算法的優化調度

1.3.1 蟻群優化算法

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

(4)

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

(5)

1.3.2 蟻群算法的改進

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

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

(6)

式中，q為隨機數。

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

(2) 改進啟發因子β

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

β(i)=b1/i

(7)

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

(3) 改進信息素的更新

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

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

Δτij=Q/lk

(8)

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

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

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

(9)

式中，Lgbest表示現階段獲得的最優路徑長度。

1.3.3 改進蟻群算法的云計算資源調度步驟

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

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

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

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

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

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

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

2 實驗結果與分析

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

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

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

圖3 資源分配相對標準差

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

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

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

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

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

在不同資源個數下，對不同算法調度后的資源利用率進行比較，分析資源庫應用不同算法的資源調度情況，分析結果如圖6所示。

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

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

3 總結

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