肖耀濤

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

0 引言

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

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

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

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

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

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

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

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

依據(jù)算法向m個(gè)虛擬機(jī)節(jié)點(diǎn)上(m

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

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

(4)

隨著螞蟻?zhàn)罴崖窂竭x擇時(shí)，信息素濃度產(chǎn)生變化，用式(5)表示:

(5)

1.3.2 蟻群算法的改進(jìn)

(1) 改進(jìn)選擇下一節(jié)點(diǎn)概率計(jì)算公式

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

(6)

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

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

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

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

β(i)=b1/i

(7)

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

(3) 改進(jìn)信息素的更新

當(dāng)螞蟻選中邊(i,j)時(shí)，更新邊(i,j)上的信息素，利用式(8)進(jìn)行：

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

Δτij=Q/lk

(8)

式中，本次迭代時(shí)，lk表示第k只螞蟻已走過(guò)路徑的長(zhǎng)度。

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

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

(9)

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

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

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

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

(3) 對(duì)螞蟻個(gè)體移動(dòng)至下一虛擬機(jī)節(jié)點(diǎn)的概率進(jìn)行計(jì)算，然后將螞蟻依照計(jì)算結(jié)果移動(dòng)。

(4) 對(duì)螞蟻?zhàn)哌^(guò)路徑的信息素進(jìn)行局部更新，然后將對(duì)應(yīng)的禁忌表進(jìn)行修改。

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

圖2 不同算法負(fù)載均衡度比較

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

圖3 資源分配相對(duì)標(biāo)準(zhǔn)差

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

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

圖4 不同算法的總效用值對(duì)比

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

圖5 不同算法收斂特性對(duì)比

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

圖6 不同算法資源利用率對(duì)比

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

3 總結(jié)

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