云計算中基于cloudsim的蟻群調(diào)度算法研究

張翰林　謝曉燕

摘要：介紹了云計算仿真工具cloudsim，在描述其架構(gòu)的基礎(chǔ)上，實現(xiàn)了cloudsim模擬云環(huán)境下調(diào)度策略的過程。引入蟻群算法，并基于蟻群算法實現(xiàn)了對cloudsim中調(diào)度策略的拓展，并與輪循、貪心等傳統(tǒng)代數(shù)算法進行對比分析測試。結(jié)果表明，蟻群算法在應(yīng)對云計算中海量任務(wù)和數(shù)據(jù)處理時，由于傳統(tǒng)代數(shù)算法。

關(guān)鍵詞：云計算，cloudsim，蟻群算法

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）03-0219-02

云計算按照服務(wù)類型，大致可以分為三類：將基礎(chǔ)設(shè)置作為服務(wù)Iaas、將平臺作為服務(wù)paas、將軟件作為服務(wù)saas。然而，不管何種類型的云計算服務(wù)，都有不同的、負(fù)責(zé)的組件，配置環(huán)境和部署條件的要求，因此，在異構(gòu)真實的云環(huán)境下，對云端調(diào)度分配策略的優(yōu)劣的評價，以及由調(diào)度策略所帶來的云端設(shè)備的復(fù)合、節(jié)能、系統(tǒng)規(guī)模性能進行量化、評價是非常不易的。所以，本文引入云計算仿真工具Cloudsim，構(gòu)建一個云環(huán)境下的分布式系統(tǒng)模擬器來實現(xiàn)云計算試驗的模擬。

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

1 cloudsim介紹

1.1 cloudsim體系結(jié)構(gòu)

Cloudsim是澳大利亞墨爾本大學(xué)Rajkumar Buyya教授領(lǐng)導(dǎo)團隊開發(fā)的云計算仿真器，是一個通用的、可拓展的支持建模和模擬的仿真框架，并能進行云計算基礎(chǔ)設(shè)施和管理服務(wù)的實驗。其體系結(jié)構(gòu)[1]如圖：

1.2 cloudsim技術(shù)實現(xiàn)

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

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

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

（2）創(chuàng)建數(shù)據(jù)中心，是在虛擬機的生命周期內(nèi)負(fù)責(zé)管理虛擬機的一組主機。通過調(diào)用API函數(shù)，完成創(chuàng)建數(shù)據(jù)中心的工作。

（3）創(chuàng)建數(shù)據(jù)中心代理，負(fù)責(zé)在云計算中，根據(jù)用戶的Qos要求以及現(xiàn)有云資源協(xié)調(diào)用戶和服務(wù)供應(yīng)商并部署服務(wù)。

（4）創(chuàng)建虛擬機，并對虛擬機的參數(shù)進行設(shè)置，并提交給任務(wù)代理。

（5）創(chuàng)建云任務(wù)，生成指定參數(shù)的云任務(wù)。

（6）調(diào)用自定義的任務(wù)調(diào)度策略，將云任務(wù)分配到虛擬機

（7）啟動仿真，執(zhí)行整個仿真流程。

（8）統(tǒng)計試驗結(jié)果。

2.1 蟻群算法的原理

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

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

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

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

2.2 算法流程

步驟1：任務(wù)開始；

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

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

步驟4：所有任務(wù)是否執(zhí)行成功？若為否，返回步驟3，若為是，執(zhí)行步驟5；

步驟5：釋放占用資源

步驟6：任務(wù)結(jié)束

3仿真及結(jié)果分析

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

仿真說明：

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

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

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

實驗結(jié)果如圖3所示。

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

在云計算環(huán)境中的任務(wù)分配問題中，除了要考慮直接影響用戶滿意度的任務(wù)完成時間之外還應(yīng)充分考慮系統(tǒng)的負(fù)載平衡性，圖4表示了當(dāng)任務(wù)數(shù)為200的時候，各虛擬機的負(fù)載對比：

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

4總結(jié)

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

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

參考文獻(xiàn)：

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

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

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

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