基于蟻群算法的云計(jì)算資源調(diào)度分析

劉霜

摘 要當(dāng)前，云計(jì)算資源調(diào)度中常用的算法包括遺傳算法、蟻群算法、粒子群算法以及綜合優(yōu)化算法等。不同算法所關(guān)注的角度存在一定的差異，遺傳算法和粒子群算法主要從資源調(diào)度的效率方面進(jìn)行優(yōu)化，而蟻群算法則是從云計(jì)算資源調(diào)度的計(jì)算成本方面進(jìn)行考慮。論文討論了基于優(yōu)化蟻群算法的云計(jì)算資源調(diào)度，在兼顧任務(wù)效率的基礎(chǔ)上，能夠進(jìn)一步降低計(jì)算成本。

【關(guān)鍵詞】云計(jì)算 資源調(diào)度 蟻群算法

1 云計(jì)算資源調(diào)度

云計(jì)算資源調(diào)度主要是對(duì)某個(gè)時(shí)間點(diǎn)或者時(shí)間段內(nèi)如何向用戶進(jìn)行資源分配的決策過(guò)程。資源是根據(jù)單個(gè)或者多個(gè)優(yōu)化目標(biāo)進(jìn)行分配的，其中，目標(biāo)包括了任務(wù)的效率、成本等方面的問(wèn)題。云計(jì)算中的不同應(yīng)用程序所需要的資源不同，加上云計(jì)算本身的異構(gòu)性以及動(dòng)態(tài)性的特點(diǎn)，導(dǎo)致云計(jì)算資源調(diào)度問(wèn)題成為了一個(gè)非常復(fù)雜的多目標(biāo)優(yōu)化問(wèn)題。而作為良好的資源調(diào)度策略，不僅需要進(jìn)一步提高計(jì)算的效率，同時(shí)還應(yīng)該控制調(diào)度成本，實(shí)現(xiàn)對(duì)資源的最大化利用。另外，云計(jì)算資源管理還需要利用有限的物理資源，為更多的用戶提供多樣化的服務(wù)，同時(shí)滿足不同類型用戶在計(jì)算效率、成本等服務(wù)質(zhì)量方面的差異化要求。2基于蟻群算法的云計(jì)算資源調(diào)度

蟻群算法是以中用于尋求最優(yōu)解決方案的機(jī)率型技術(shù)，其最早是由Marco Dorigo于1992年在其博士論文中引入，主要借鑒了螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。螞蟻在路徑上前進(jìn)時(shí)能夠根據(jù)前面螞蟻所留下的分泌物選擇路徑，其選擇一條路徑的概率與該路徑上分泌物的強(qiáng)度成正比。因此，大量螞蟻構(gòu)成的群體行為實(shí)際上構(gòu)成了一種學(xué)習(xí)信息的反饋現(xiàn)象，即選擇某一條路徑的螞蟻越多，后面的螞蟻則繼續(xù)選擇該路徑的可能性更大。螞蟻個(gè)體之間通過(guò)這種信息尋求最短的目標(biāo)路徑。在云計(jì)算環(huán)境下，可以將資源調(diào)度問(wèn)題看作一個(gè)多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題。從解決這類問(wèn)題的角度來(lái)看，蟻群優(yōu)化算法很適合解決資源調(diào)度的問(wèn)題，傳統(tǒng)的蟻群算法通常只能在效率和成本兼顧一面，對(duì)此本文提出了一種新的優(yōu)化蟻群算法。

2.1 算法設(shè)計(jì)

建立子任務(wù)與虛擬節(jié)點(diǎn)分配矩陣X，定義節(jié)點(diǎn)Xij，其中i（1，2，…，n），j（1，2，…，m）為節(jié)點(diǎn)集合，構(gòu)成了一個(gè)沒有方向的完全圖G（V，E）。通過(guò)優(yōu)化蟻群算法能夠獲取一個(gè)適用于資源調(diào)度方案使F得值達(dá)到最小。

2.1.1 初始化信息素

在初始化算法的階段，為了確保螞蟻能夠很好地進(jìn)行路徑尋優(yōu)，需要將所有路徑的信息素的初始值設(shè)置為最大，完成信息素的初始化。

2.1.2 路徑選擇

在各個(gè)節(jié)點(diǎn)上都分布著若干只螞蟻進(jìn)行最優(yōu)解的搜索，則第k只螞蟻在t時(shí)刻選擇節(jié)點(diǎn)Xij的概率為：

（1）

（2）

τij（t）代表了t時(shí)刻，螞蟻在Xij節(jié)點(diǎn)位置所殘留的信息素；φij（t）代表了螞蟻的啟發(fā)信息。α和β非別表示殘留信息素和啟發(fā)信息的相對(duì)重要性。tabk（k=1，2，L，m）代表第k只螞蟻行走的禁忌表，即不會(huì)選擇的路徑，如果t時(shí)刻，第k只螞蟻選擇節(jié)點(diǎn)Xij，則就會(huì)被加入到禁忌表中。

2.1.3 信息素更新

在每次循環(huán)之后都需要對(duì)該次循環(huán)中的最優(yōu)解或者局部最優(yōu)解的信息素進(jìn)行更新，從而確保找到全局最優(yōu)解能夠有更高的效率，按照下面的公式對(duì)信息素進(jìn)行更新：

（3）

（4）

其中，F(xiàn)best就表示了全局最優(yōu)解的值，通過(guò)對(duì)信息素的更新，能夠進(jìn)一步提高算法的效率，縮短計(jì)算所需要的時(shí)間。

2.2 算法流程

根據(jù)上面的分析，確定了基于蟻群算法的云計(jì)算資源調(diào)度的具體流程：

Step1：確定算法的適應(yīng)度函數(shù)；

Step2：設(shè)置算法的各類指標(biāo)參數(shù)和算法結(jié)束條件，參數(shù)需要確保合理性，以保證算法效率；

Step3：設(shè)定完成之后初始化算法的信息素，并將螞蟻在各個(gè)節(jié)點(diǎn)進(jìn)行隨機(jī)分布，進(jìn)行路徑搜索；

Step4：每次完成一輪搜索之后，從其中選擇當(dāng)前的最優(yōu)解，然后更新信息素；

Step5：繼續(xù)進(jìn)行搜索，如果滿足之前設(shè)置的結(jié)束條件，則確定當(dāng)前獲取的最優(yōu)解為算法的全局最優(yōu)解，如果不滿足算法結(jié)束條件，則跳轉(zhuǎn)到Step4。

3 仿真分析

為了對(duì)算法的可行性和有效性進(jìn)行驗(yàn)證，選擇CloudSim平臺(tái)對(duì)算法進(jìn)行仿真分析。在實(shí)際仿真過(guò)程中，將初始條件c，d設(shè)置為0.5，其余參數(shù)的值設(shè)置為1，在仿真中采用50個(gè)虛擬機(jī)節(jié)點(diǎn)，50個(gè)任務(wù)，每個(gè)任務(wù)被分割為范圍為[10，60]的子任務(wù)，螞蟻群的規(guī)模設(shè)置為50，實(shí)驗(yàn)循環(huán)次數(shù)為30次，實(shí)驗(yàn)終止的條件為達(dá)到最大迭代次數(shù)。在完全相同的實(shí)驗(yàn)條件下，采用本文所設(shè)計(jì)蟻群優(yōu)化算法和標(biāo)準(zhǔn)蟻群算法進(jìn)行對(duì)比。

通過(guò)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析發(fā)現(xiàn)，本文所設(shè)計(jì)的蟻群優(yōu)化算法能夠在總體完成時(shí)間較少的基礎(chǔ)上減低計(jì)算成本，而不是以犧牲計(jì)算成本來(lái)提高計(jì)算效率，或則以犧牲計(jì)算效率來(lái)降低計(jì)算成本。因此，本文所設(shè)計(jì)的蟻群優(yōu)化算法在云計(jì)算資源調(diào)度中能夠同時(shí)兼顧計(jì)算效率和計(jì)算成本，實(shí)現(xiàn)較好的資源調(diào)度效果。

4 結(jié)語(yǔ)

由于云計(jì)算環(huán)境本身的特性，其資源調(diào)度面臨大量的計(jì)算，如何進(jìn)行合理的資源調(diào)度，提高資源調(diào)度的效率，并控制資源調(diào)度成本，成為當(dāng)前云計(jì)算資源調(diào)度研究的重要內(nèi)容。就目前來(lái)看，云計(jì)算資源調(diào)度的算法較多，但是各類算法考慮的方向不同，如何同時(shí)兼顧計(jì)算效率和計(jì)算成本，實(shí)現(xiàn)雙方的協(xié)調(diào)，而不是以犧牲效率或者犧牲成本來(lái)提升效率或者控制成本，對(duì)云計(jì)算資源調(diào)度提出了挑戰(zhàn)。對(duì)此，論文提出了一種基于蟻群算法的優(yōu)化資源調(diào)度算法，通過(guò)在CloudSim平臺(tái)對(duì)論文所設(shè)計(jì)的算法進(jìn)行仿真分析，驗(yàn)證了該算法能夠在有效降低成本的基礎(chǔ)上確保云計(jì)算資源調(diào)度的效率，并且算法具有可行性和有效性。

參考文獻(xiàn)

[1]王芳，李美安，段衛(wèi)軍.基于動(dòng)態(tài)自適應(yīng)蟻群算法的云計(jì)算任務(wù)調(diào)度[J].計(jì)算機(jī)應(yīng)用，2013（11）：3160-3162+3196.

[2]張雨，李芳，周濤.云計(jì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究[J].計(jì)算機(jī)工程與應(yīng)用，2014（06）：51-55.

作者單位

山東理工大學(xué) 山東省淄博市 255000