劉霜

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

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

2.1.1 初始化信息素

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

2.1.2 路徑選擇

在各個節(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ā)信息的相對重要性。tabk（k=1，2，L，m）代表第k只螞蟻行走的禁忌表，即不會選擇的路徑，如果t時(shí)刻，第k只螞蟻選擇節(jié)點(diǎn)Xij，則就會被加入到禁忌表中。

2.1.3 信息素更新

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

（3）

（4）

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

2.2 算法流程

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

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

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

Step3：設(shè)定完成之后初始化算法的信息素，并將螞蟻在各個節(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 仿真分析

為了對算法的可行性和有效性進(jìn)行驗(yàn)證，選擇CloudSim平臺對算法進(jìn)行仿真分析。在實(shí)際仿真過程中，將初始條件c，d設(shè)置為0.5，其余參數(shù)的值設(shè)置為1，在仿真中采用50個虛擬機(jī)節(jié)點(diǎn)，50個任務(wù)，每個任務(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)行對比。

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

4 結(jié)語

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

參考文獻(xiàn)

[1]王芳，李美安，段衛(wèi)軍.基于動態(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