基于蟻群算法的云計算資源調度分析

劉霜

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

【關鍵詞】云計算 資源調度 蟻群算法

1 云計算資源調度

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

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

2.1 算法設計

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

2.1.1 初始化信息素

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

2.1.2 路徑選擇

在各個節點上都分布著若干只螞蟻進行最優解的搜索，則第k只螞蟻在t時刻選擇節點Xij的概率為：

（1）

（2）

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

2.1.3 信息素更新

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

（3）

（4）

其中，Fbest就表示了全局最優解的值，通過對信息素的更新，能夠進一步提高算法的效率，縮短計算所需要的時間。

2.2 算法流程

根據上面的分析，確定了基于蟻群算法的云計算資源調度的具體流程：

Step1：確定算法的適應度函數；

Step2：設置算法的各類指標參數和算法結束條件，參數需要確保合理性，以保證算法效率；

Step3：設定完成之后初始化算法的信息素，并將螞蟻在各個節點進行隨機分布，進行路徑搜索；

Step4：每次完成一輪搜索之后，從其中選擇當前的最優解，然后更新信息素；

Step5：繼續進行搜索，如果滿足之前設置的結束條件，則確定當前獲取的最優解為算法的全局最優解，如果不滿足算法結束條件，則跳轉到Step4。

3 仿真分析

為了對算法的可行性和有效性進行驗證，選擇CloudSim平臺對算法進行仿真分析。在實際仿真過程中，將初始條件c，d設置為0.5，其余參數的值設置為1，在仿真中采用50個虛擬機節點，50個任務，每個任務被分割為范圍為[10，60]的子任務，螞蟻群的規模設置為50，實驗循環次數為30次，實驗終止的條件為達到最大迭代次數。在完全相同的實驗條件下，采用本文所設計蟻群優化算法和標準蟻群算法進行對比。

通過對實驗結果進行分析發現，本文所設計的蟻群優化算法能夠在總體完成時間較少的基礎上減低計算成本，而不是以犧牲計算成本來提高計算效率，或則以犧牲計算效率來降低計算成本。因此，本文所設計的蟻群優化算法在云計算資源調度中能夠同時兼顧計算效率和計算成本，實現較好的資源調度效果。

4 結語

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

參考文獻

[1]王芳，李美安，段衛軍.基于動態自適應蟻群算法的云計算任務調度[J].計算機應用，2013（11）：3160-3162+3196.

[2]張雨，李芳，周濤.云計算環境下基于遺傳蟻群算法的任務調度研究[J].計算機工程與應用，2014（06）：51-55.

作者單位

山東理工大學 山東省淄博市 255000