云計算中基于cloudsim的蟻群調度算法研究

張翰林　謝曉燕

摘要：介紹了云計算仿真工具cloudsim，在描述其架構的基礎上，實現了cloudsim模擬云環境下調度策略的過程。引入蟻群算法，并基于蟻群算法實現了對cloudsim中調度策略的拓展，并與輪循、貪心等傳統代數算法進行對比分析測試。結果表明，蟻群算法在應對云計算中海量任務和數據處理時，由于傳統代數算法。

關鍵詞：云計算，cloudsim，蟻群算法

中圖分類號：TP393 文獻標識碼：A 文章編號：1009-3044（2016）03-0219-02

云計算按照服務類型，大致可以分為三類：將基礎設置作為服務Iaas、將平臺作為服務paas、將軟件作為服務saas。然而，不管何種類型的云計算服務，都有不同的、負責的組件，配置環境和部署條件的要求，因此，在異構真實的云環境下，對云端調度分配策略的優劣的評價，以及由調度策略所帶來的云端設備的復合、節能、系統規模性能進行量化、評價是非常不易的。所以，本文引入云計算仿真工具Cloudsim，構建一個云環境下的分布式系統模擬器來實現云計算試驗的模擬。

與此同時，目前廣泛應用于云計算的如先到先服務FCFS算法、Greedy貪心算法[2]等，由于算法本身的特點，均是傳統代數算法靜態建模完成的，并不能針對網絡中各種不確定變化做出對應的調整。而蟻群優化算法作為一種智能算法，在經過多次迭代后，任務必然能分配給一個合理的虛擬機。因此，本文在介紹Cloudsim架構、工作原理的同時，通過cloudsim搭建了一個云計算平臺，并在此平臺下，對FCFS算法、Greedy貪心算法以及蟻群優化算法進行的對比測試和分析。結果證明蟻群優化算法對于網絡中突發情況的應對是較優的。

1 cloudsim介紹

1.1 cloudsim體系結構

Cloudsim是澳大利亞墨爾本大學Rajkumar Buyya教授領導團隊開發的云計算仿真器，是一個通用的、可拓展的支持建模和模擬的仿真框架，并能進行云計算基礎設施和管理服務的實驗。其體系結構[1]如圖：

1.2 cloudsim技術實現

由上圖的體系結構圖可知，開發人員主要通過cloudsim的最高層用戶代碼層來實現仿真模擬。通過對該層提供的一些基本實體（如主機、虛擬機、應用、用戶數量、應用類型等）的拓展，從而達到（1）建立應用配置請求和任務負載分配請求（2）通過模擬出的云場景，測試自定義配置運行的魯棒性（3）基于云平臺擴展實現自定的調度策略。

Cloudsim是開源的，其用戶代碼層為開發人員提供了一系列可供拓展的實力和方法，通過拓展這些接口來實現用戶自己的調度或分配策略，進行相關科研測試。本文主要進行調度策略的研究，故需要對DatacenterBroker類進行拓展，實現自定義的調度策略，完成對算法的模擬并進行測試和試驗分析。

具體的仿真步驟如下：（1）初始化cloudsim包，主要是在其他實體創建前對cloudsim的參數包括日期、用戶數量、跟蹤日志等進行初始化。

（2）創建數據中心，是在虛擬機的生命周期內負責管理虛擬機的一組主機。通過調用API函數，完成創建數據中心的工作。

（3）創建數據中心代理，負責在云計算中，根據用戶的Qos要求以及現有云資源協調用戶和服務供應商并部署服務。

（4）創建虛擬機，并對虛擬機的參數進行設置，并提交給任務代理。

（5）創建云任務，生成指定參數的云任務。

（6）調用自定義的任務調度策略，將云任務分配到虛擬機

（7）啟動仿真，執行整個仿真流程。

（8）統計試驗結果。

2.1 蟻群算法的原理

覓食原則：每只螞蟻能夠在感知的環境里尋找食物，如果發現食物則直接向該方向前進；如果沒有，則檢查感知環境內的食物信息素，向著信息素濃度高的地方走去。同理，尋找蟻穴的方式是感知環境內的蟻穴信息素。

前進原則：每只螞蟻都會向著信息素濃度高的方向前進，如果在感知范圍內沒有相關的信息素提示，則會依照原來行進的方向繼續走下去。此外，螞蟻能夠識別剛剛走過的位置，防止螞蟻原地不動。

躲避障礙原則：螞蟻在覓食過程中，如果遇到障礙物，會隨機選擇一個方向繼續行進；當然，如果有信息素提示，會按照覓食原則前進。

依據以上蟻群算法的原則，螞蟻的個體之間雖然沒有直接關聯，但螞蟻同螞蟻之間通過信息素進行信息的交互傳遞。在覓食過程中，會依據之前經過的螞蟻所留下的信息素來選擇它們要走的路徑。所以，大量螞蟻組成的群體行為實質上形成了一種學習信息的反饋現象，這也就是蟻群算法的一大特點----正反饋機制。根據這一特點，通過模仿螞蟻群體的行為，實現最優。整個過程如圖2所示：

2.2 算法流程

步驟1：任務開始；

步驟2：任務T1、T2、…、Tn參數，并進行任務分類；

步驟3：利用蟻群算法進行資源分配；

步驟4：所有任務是否執行成功？若為否，返回步驟3，若為是，執行步驟5；

步驟5：釋放占用資源

步驟6：任務結束

3仿真及結果分析

本文使用Cloudsim3.0進行仿真實驗，通過重寫DataCenterBroker類、Cloudlet類對cloudsim進行拓展，分別編寫了Greedy貪心算法和ACO蟻群算法，并將這兩種算法和Cloudsim自帶的RR輪循算法進行對比。

仿真說明：

一、對于虛擬機的運算速度和云任務的長度，取值大量的過高或過低都不符合實際情況，所以為了實驗的有效性，依照高斯分布在設定的長度區間內隨機產生虛擬機的運算速度和云任務長度。

二、虛擬機粒度最小化，設定單個虛擬機同一時間段內只具有處理單個任務的能力，對于那些性能較好具有并發計算能力的虛擬機，根據它的運算能力將其劃分為多個虛擬機。

三、對于等量的云任務，調度策略完成任務時間越短則認為該策略執行效率越高，由于云計算中的各個虛擬機計算資源間是并發處理子任務序列的，所以完成所有子任務所需的執行時間是各虛擬機完成子任務時間集合中的最大值，故采用MCT作為算法的評價標準。

實驗結果如圖3所示。

由圖3可以看出：Cloudsim自帶的RR算法的MCT是最大的，這主要是因為該算法采用的是簡單的輪循，雖然算法簡單，但卻并未進行任何優化，自然它耗費的時間就比較多。圖中數據還可以看出，當任務數在小于50的范圍內，ACO蟻群算法并不如Greedy貪心算法用時少，主要原因是蟻群算法的性質適合在訓練集龐大，訓練時間較長的情況下進行，由于具有迭代學習的過程，其時間復雜度相對Greedy算法較高。但也正是由于該原因，當任務數大于100后，由于ACO迭代學習的次數增加，所以能針對網絡環境中突發的各種情況進行應對，因此得到的結果也更準確，這一點是Greedy算法所不具備的。

在云計算環境中的任務分配問題中，除了要考慮直接影響用戶滿意度的任務完成時間之外還應充分考慮系統的負載平衡性，圖4表示了當任務數為200的時候，各虛擬機的負載對比：

從圖中可以看出，由于RR算法是按照順序分配的原則進行資源調度的，所以虛擬機的負載最不平衡；Greedy在設計時由于并未考慮的網絡中突發的各種情況，所以會當任務數較多時，會出現大量的調度失敗以及重調度，所以雖然負載均衡程度由于RR算法，但是也存在不均衡的缺點；而蟻群算法通過利用自身不斷迭代學習的特性，實現了虛擬機的負載相對均衡。

4總結

由于云計算環境的復雜性、異構性和不確定性，對資源分配的調度分配策略和負載均衡的要求也不斷提高。本文通過對蟻群算法特性的研究，利用Cloudsim云仿真工具實現了蟻群算法在云環境中資源分配調度策略的實現。

實驗結果表明，ACO蟻群算法在應對海量任務和數據處理的時候，無論是MCT任務最大完成時間還是負載均衡性能都由于傳統RR倫循算法和Greedy貪心算法。后續將繼續考察諸如云平臺中數據遷移的開銷、引入安全性約束條件、服務間資源資源共享等問題，這些都需要將現有的ACO蟻群算法進一步改進與完善。

參考文獻：

[1] 劉鵬.云計算[M].2版.北京： 電子工業出版社，2011.

[2] 田文洪，趙勇.云計算資源調度管理[M].國防工業出版社，2011.

[3] 王永貴，韓瑞蓮.基于改進蟻群算法的云環境任務調度研究[J].計算機測量與控制，2011，19（5）：1203-1204.

[4] 倪慶劍，邢漢承，張志政，等.蟻群算法及其應用研究進展[J].計算機應用與軟件，2008（8）：12-16.