高校云數(shù)據(jù)中心基于蟻群算法的資源調(diào)度研究

戰(zhàn)非

（西安航空學(xué)院 計算機(jī)學(xué)院，陜西 西安　710077）

高校云數(shù)據(jù)中心基于蟻群算法的資源調(diào)度研究

戰(zhàn)非

（西安航空學(xué)院 計算機(jī)學(xué)院，陜西 西安710077）

針對構(gòu)建高校云計算數(shù)據(jù)中心的目的出發(fā)，對基于蟻群算法的云計算資源調(diào)度進(jìn)行研究。通過云仿真軟件CloudSim進(jìn)行仿真實驗，證明蟻群算法在多任務(wù)執(zhí)行時間及相對標(biāo)準(zhǔn)差方面優(yōu)于傳統(tǒng)資源調(diào)度算法。

云計算；數(shù)據(jù)中心；蟻群算法；CloudSim

數(shù)字化校園建設(shè)作為高校發(fā)展的重要環(huán)節(jié)，越來越受到廣泛的重視。但是隨著建設(shè)的深入，數(shù)據(jù)量和信息量都海量的增加，高校現(xiàn)有及新建各系統(tǒng)之間無法做到資源共享，硬件設(shè)備利用率不高等問題也顯現(xiàn)出來，于是高校數(shù)據(jù)中心應(yīng)運(yùn)而生，通過建立高校數(shù)據(jù)中心，可以實現(xiàn)教務(wù)、后勤、學(xué)生管理等各個職能部門數(shù)據(jù)的統(tǒng)一存儲、統(tǒng)一管理和資源共享，極大地提高使用效率。

云計算作為一種新興的計算模式，主要應(yīng)用于互聯(lián)網(wǎng)中，將基礎(chǔ)資源設(shè)施、應(yīng)用系統(tǒng)、軟件平臺等作為服務(wù)提供給用戶［1-2］。同時云計算也是一種基于虛擬化為基礎(chǔ)的架構(gòu)方式，能夠?qū)⒋罅抠Y源進(jìn)行虛擬化，構(gòu)建龐大的的資源池，對外以服務(wù)方式進(jìn)行管理。

如上所述，構(gòu)建基于云計算的高校數(shù)據(jù)中心便于解決傳統(tǒng)模式下數(shù)據(jù)中心的不足，可以實現(xiàn)對數(shù)據(jù)和資源更加統(tǒng)一的、高效的管理，為高校各部門之間的數(shù)據(jù)共享提供便利。云計算數(shù)據(jù)中心工作過程中，任務(wù)調(diào)度和資源分配是至關(guān)重要的環(huán)節(jié)，文中主要討論如何基于蟻群算法對云計算中資源進(jìn)行調(diào)度，進(jìn)行仿真實驗并分析結(jié)果。

1　構(gòu)建高校中基于云計算的數(shù)據(jù)中心

1.1云計算高校數(shù)據(jù)中心的建設(shè)目標(biāo)

基于云計算的高校數(shù)據(jù)中心，在保留傳統(tǒng)數(shù)據(jù)中心的特點之上，對數(shù)據(jù)的存儲和管理提出了更高的要求，建設(shè)云計算數(shù)據(jù)中心應(yīng)從以下幾個方面著手：

1）硬件方面，建立一定規(guī)模的機(jī)房，實現(xiàn)完備的硬件設(shè)施及充足的帶寬，以擴(kuò)展性強(qiáng)，能耗較低，安全可靠為基礎(chǔ)。能夠滿足學(xué)校中不同職能部門的服務(wù)要求。

2）數(shù)據(jù)存儲方面，建立集中管理、安全性強(qiáng)的統(tǒng)一數(shù)據(jù)存儲平臺，能夠保證數(shù)據(jù)更新的實時性，具有完整的重要數(shù)據(jù)的備份及容災(zāi)機(jī)制。

3）網(wǎng)絡(luò)服務(wù)方面，能夠為學(xué)校各項工作提供持續(xù)不間斷的網(wǎng)絡(luò)服務(wù)，具有良好的監(jiān)測機(jī)制和故障預(yù)防機(jī)制。

1.2云計算數(shù)據(jù)中心體系架構(gòu)

圖1給出了云計算數(shù)據(jù)中心體系中分層管理中的4個核心要素。

圖1　云計算數(shù)據(jù)中心架構(gòu)圖

物理層，也稱為HaaS（Hardware as a Service，硬件設(shè)施即服務(wù)）［3］。作為云數(shù)據(jù)中心的底層，主要針對硬件設(shè)施，如具有設(shè)施齊備的一定規(guī)模的機(jī)房等；

虛擬層，該層也稱為IaaS（Infrastructure as a Service，基礎(chǔ)設(shè)施即服務(wù)），將物理層硬件（包括存儲設(shè)備、服務(wù)器和網(wǎng)絡(luò)設(shè)備等）進(jìn)行全面虛擬化，構(gòu)建可共享的按需分配的基礎(chǔ)資源設(shè)施；

管理層，該層是數(shù)據(jù)中心的決策層，可稱為PaaS（Platform as a Service，平臺及服務(wù)），它將計算平臺作為一項服務(wù)，以虛擬化為基礎(chǔ)，統(tǒng)一對用戶、安全、任務(wù)資源等進(jìn)行管理；

應(yīng)用層，可稱為SaaS（Software as a Service），本層是高校中直接面對用戶的接口層，應(yīng)該具有友好的便于操作的界面，為學(xué)校不同部門的需求提供按需獲取的云計算服務(wù)。

2　任務(wù)調(diào)度在云計算中的應(yīng)用

云計算的優(yōu)勢體現(xiàn)在更強(qiáng)的計算能力和更高的計算效率，可以為用戶提供更優(yōu)質(zhì)的服務(wù)，而云計算中資源分配策略和任務(wù)調(diào)度策略是實現(xiàn)這些優(yōu)勢的基礎(chǔ)。

2.1任務(wù)調(diào)度概念

調(diào)度問題指的是，在滿足一定的約束規(guī)則條件下，根據(jù)提前制定好的資源分配策略對單個或者多個并行的任務(wù)進(jìn)行分配，以最短處理時間和提高處理性能為目標(biāo)，分配給各個處理節(jié)點按一定的順序執(zhí)行任務(wù)。

調(diào)度系統(tǒng)的好壞基于兩個基本元素，分別是性能和效率。調(diào)度算法作為調(diào)度系統(tǒng)的基礎(chǔ)，算法本身的效率和調(diào)度質(zhì)量至關(guān)重要。針對云計算的特點，需要選擇更高效的算法來支持。

2.2任務(wù)調(diào)度策略分類和算法

任務(wù)調(diào)度以種類劃分，可以分為靜態(tài)調(diào)度和動態(tài)調(diào)度。靜態(tài)調(diào)度策略應(yīng)用較為簡單但效率往往比較低下；動態(tài)調(diào)度策在云計算中要充分考慮不同計算節(jié)點自身的處理能力，還要結(jié)合硬件條件、服務(wù)費(fèi)用等各個因素，最終尋找一個具有最優(yōu)組合的節(jié)點，然后將任務(wù)進(jìn)行分配。實際應(yīng)用中，我們也可以將動態(tài)和靜態(tài)兩種調(diào)度結(jié)合起來作為混合調(diào)度方式使用。

針對任務(wù)調(diào)度的經(jīng)典算法比較多，從系統(tǒng)角度出發(fā)希望每個進(jìn)程能較為公平的被執(zhí)行，具有較大的吞吐量。從用戶角度出發(fā)，希望響應(yīng)速度較快，執(zhí)行時間較短。常見的算法有FIFO算法，Dijkstra算法，Round Robin算法等。但是在云計算中有其自身的特點，需要對異構(gòu)基礎(chǔ)資源的支持，以分布式計算為基礎(chǔ)，所以我們也多以啟發(fā)式算法來進(jìn)行任務(wù)調(diào)度。所謂啟發(fā)式算法指：基于直觀或經(jīng)驗構(gòu)造的算法，在一定計算條件的約束下，給出待解決組合優(yōu)化問題每一個實例的一個可行解，該可行解與最優(yōu)解的偏離程度通常不可預(yù)計。較為常用的算法有模擬退火算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)遺傳算法、蟻群算法等。本文的重點就是討論蟻群算法的模型和在云計算中的應(yīng)用。

3　基于蟻群算法的資源調(diào)度分析

3.1蟻群算法基本原理

蟻群算法來源于自然界螞蟻種群覓食現(xiàn)象，蟻群在未知食物在什么地方的前提下開始尋找食物，當(dāng)個體螞蟻找到食物后，在其經(jīng)過的路徑上會釋放一種揮發(fā)性分泌物，我們稱之為信息素，信息素濃度的大小表征路徑的遠(yuǎn)近。其他螞蟻在尋找食物的過程中，在一定范圍內(nèi)感知信息素的強(qiáng)弱，永遠(yuǎn)朝著信息素濃度較多的方向移動，經(jīng)過一段時間運(yùn)行，可能會出現(xiàn)一條最短的路徑，大多數(shù)螞蟻依照此路徑運(yùn)動［4-5］。

蟻群算法本質(zhì)是一種隨機(jī)搜索算法，具有以下行為規(guī)律：

1）隨著時間的增長，每條路徑上的信息素濃度在不斷變化，某些路徑信息素不斷累積，某些路徑不斷揮發(fā)，螞蟻根據(jù)信息素濃度以一定的概率來選擇下一條路徑。

2）為規(guī)避螞蟻停滯不前在本地打轉(zhuǎn)，用一個禁忌表來記錄已經(jīng)走過的路徑，通過禁忌表剔除本次循環(huán)已經(jīng)走過的路徑。

3）當(dāng)單個螞蟻走完某條路徑后，都會以路徑長度為根據(jù)釋放相應(yīng)濃度的信息素，被走的多的路徑信息素濃度逐漸增大，走的少的信息素濃度不斷揮發(fā)，這將作為其他螞蟻選擇此條路徑的概率的依據(jù)。

3.2蟻群算法數(shù)學(xué)模型

設(shè)將M只螞蟻放入到N個隨機(jī)選擇的地點，螞蟻k（k= 1，2，…，m）行進(jìn)規(guī)律根據(jù)信息素濃度決定，總是向著濃度高的路徑運(yùn)動。

開始時期，螞蟻隨機(jī)選擇一條路徑，因為此時各條路徑上的信息素濃度基本相同，使用禁忌表tabuk（k=1，2，…，m）來記錄螞蟻k所走過的路徑，該表將根據(jù)螞蟻運(yùn)動的過程實時進(jìn)行調(diào)整，用（t）來表示在t時刻螞蟻k選擇地點j作為目標(biāo)的

狀態(tài)轉(zhuǎn)移概率：

其中：

allowedk表示螞蟻k下一步可以選擇的地點。

τij（t）表示地點i到地點j的路徑在t時刻的信息素量。

ηij（t）表示經(jīng)地點i行進(jìn)至地點j的初始信息，該信息由所求解問題得到。為地點i到地點j的先驗值，dij表示地點i和j之間的距離。

α代表信息啟發(fā)因子，其值越大代表當(dāng)前路徑越重要，螞蟻就更傾向去選擇該條路徑。這里我們設(shè)α=1。

β為期望啟發(fā)因子，代表螞蟻根據(jù)起發(fā)信息去選擇路徑過程中受影響的程度，表示計算能力預(yù)測值的相對權(quán)重。這里我們設(shè)β=5。

在實際計算過程中，需要對路徑上殘余信息量動態(tài)處理，因為隨著螞蟻搜索過程的進(jìn)行，路徑上聚集越來越多的信息素將會淹沒啟發(fā)信息。所以當(dāng)螞蟻k完成一條路徑或者走完多個地點后，需要更新信息素濃度，這里通過如下規(guī)則來調(diào)整路徑（i，j）在t+n時刻的信息量：

其中：

ρ表示信息素?fù)]發(fā)系數(shù)，則1-ρ表示信息素殘留因子，規(guī)定ρ的取值范圍為ρ?［0，1］，為防止信息素隨時間進(jìn)行無限聚集，這里取ρ=0.5。

Δτij（t）代表螞蟻從t時刻到t+n時刻，從地點i到地點j路徑上信息素的增量。初始時刻Δτij（0）=0。

其中：Q表示信息素強(qiáng)度；Lk表示螞蟻k在當(dāng)前循環(huán)中走過的路徑總長度。

4　CloudSim仿真及結(jié)果分析

4.1蟻群算法調(diào)度流程

用蟻群算法進(jìn)行調(diào)度，首先對并行的所有用戶任務(wù)分類，并且給出優(yōu)先級順序，因為這樣才能體現(xiàn)出不同任務(wù)對應(yīng)不同服務(wù)質(zhì)量的要求。然后依據(jù)算法進(jìn)行資源分配與調(diào)度，當(dāng)算法找到符合服務(wù)要求的最優(yōu)路徑，提供資源并進(jìn)行綁定，開始執(zhí)行。流程圖如圖2所示。

圖2　蟻群算法資源調(diào)度流程圖

4.2仿真測試過程

CloudSim仿真經(jīng)過的步驟包括：首先新建數(shù)據(jù)中心，然后確定模擬資源參數(shù)，通過DatacenterBroker類的對象建立代理，由此代理負(fù)責(zé)信息的交互，然后創(chuàng)建虛擬機(jī)開始執(zhí)行云任務(wù)，最終獲取結(jié)果。

以下代碼為仿真過程中的核心類中截取的主要流程代碼，代碼注釋體現(xiàn)了整個仿真過程的具體步驟，調(diào)用方法中的一些仿真參數(shù)如帶寬（bw），內(nèi)存（ram），PE數(shù)（pesNumber）等等的定義語句，由于篇幅限制這里省略不寫，這些參數(shù)的取值根據(jù)常規(guī)虛擬機(jī)硬件水平設(shè)置［7-8，11］。

/**初始化CloudSim，新建數(shù)據(jù)中心dt1及數(shù)據(jù)中心代理，獲得ID*/

/**新建虛擬機(jī)列表，根據(jù)要仿真的虛擬機(jī)規(guī)格參數(shù)（id、PE數(shù)量、MIPS速率、內(nèi)存、帶寬等等）創(chuàng)建虛擬機(jī)vm，并提交代理*/

/**建立云任務(wù)列表，根據(jù)仿真參數(shù)（ID、PE數(shù)量、文件大小等）新建一個云任務(wù)并添加進(jìn)列表，列表的創(chuàng)建及添加代碼省略*/

4.3實驗結(jié)果及分析

通過在CloudSim中進(jìn)行實驗，設(shè)定執(zhí)行的任務(wù)數(shù)為20～100，計算節(jié)點數(shù)為10個。為了說明蟻群算法在云計算中應(yīng)用的效果，選取了FIFO算法和Dijkstra算法這兩種傳統(tǒng)算法作為對比。執(zhí)行10次取平均值，執(zhí)行任務(wù)所需時間如圖3所示。

通過該圖我們分析出，當(dāng)任務(wù)量較少時3種算法完成任務(wù)時間基本相同，但是隨著任務(wù)量的增加，實驗表明過蟻群算法完成所有任務(wù)時間要優(yōu)于另外兩種算法。為了更進(jìn)一步的展示幾種算法的區(qū)別，對任務(wù)分配的結(jié)果的相對標(biāo)準(zhǔn)差值進(jìn)行計算，如圖4所示。

通過該圖顯示，當(dāng)任務(wù)數(shù)增加，蟻群算法的偏差值越來越小，且趨于線性漸進(jìn)，明顯優(yōu)于其他兩種算法。

通過以上分析，云計算的特點就是并行處理大量任務(wù)，通過蟻群算法進(jìn)行資源調(diào)度可以適應(yīng)常規(guī)云計算的要求。

5　結(jié)束語

云計算作為一種蓬勃發(fā)展商業(yè)計算模式，建立在將大量資源虛擬化的基礎(chǔ)上，可以統(tǒng)一對高校的數(shù)據(jù)進(jìn)行管理，根據(jù)用戶對作業(yè)量的需求提供服務(wù)。文中給出高校中云計算數(shù)據(jù)中心的構(gòu)建體系模型，重點討論應(yīng)用蟻群算法在云計算中進(jìn)行作業(yè)調(diào)度和資源分配的問題，通過CloudSim仿真實驗，從結(jié)果上對比了兩種傳統(tǒng)調(diào)度算法。最終證明該算法符合一般云計算任務(wù)調(diào)度和資源分配的要求。

圖3　任務(wù)執(zhí)行時間結(jié)果圖

圖4　相對標(biāo)準(zhǔn)差結(jié)果圖

［1］陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)［J］.計算機(jī)應(yīng)用，2009 （9）：2563-2564.

［2］劉正偉，文中領(lǐng)，張海濤.云計算和云數(shù)據(jù)管理技術(shù)［J］.計算機(jī)研究與發(fā)展，2012，49（z1）：56-27.

［3］孟湘來.基于云計算的數(shù)據(jù)中心構(gòu)建探析［J］.中國企業(yè)教育，2012（22）：240-241.

［4］劉鵬.云計算［M］.北京：電子工業(yè)出版社，2010.

［5］吳斌，史忠植.一種基于蟻群算法的TSP問題分段求解算法［J］.計算機(jī)學(xué)報，2001，24（12）：1329-1330.

［6］宋雪梅，李兵.蟻群算法及其應(yīng)用［J］.河北理工學(xué)院學(xué)報，2006，28（1）：42-43.

［7］Ran S A.A model for web service discovery with QoS［J］. ACMSIGCOM Exchanges.2003，4（1）:1-10.

［8］Buyya R，Murshed M，GridSim:A Toolkit for the Modeling and Simulation of Distributed Resource Management and Scheduling for Grid Computing［J］.The Journal of Concurrency and Computation:Practice and Experience（CCPE），2002（14）:13-15.

［9］Buyya R，Yeo CS，Venugopal S.Cloud Computing and E-merging IT Platforms:Vision，Hype and Reality for Delivering Computing as the 5th Utility［J］.Future Generation Computer Systems，2009（25）：599-616.

［10］Buyya R，Murshed M.GridSim:a toolkit for the modeling and simulation of distributed resource management and scheduling for Grid computing［J］.Concurrency and Computation: Practice and Experience，2002（14）：1175-1220.

［11］Buyya R，Ranjan R，Calheiros RN.Modeling and Simulation of Scalable CloudComputingEnvironmentsandthe CloudSim Toolkit:Challenges and Opportunities［J］.Proc. of the 7th High Performance Computing and Simulation Conference（HPCS 09），IEEE Computer Society，2009.

［12］Gustedt J，Jeannot E，Quinson M.Experimental methodologies for large-scale systems:a survey［J］.Parallel Processing Letters，Sep.2009（19）:399-418.

［13］TANG Wen，CHEN Zhong.Research of Subjective Trust Management Model Based on the Fuzzy Set Theory［J］. Journal of Software，2003，14（8）:1401-1408.

［14］LIU Shi-Kao，LIU Xing-Tang.A New Method of Elevation of Confidence Level ofLarge-ScalePerplexingSimulation System［J］.Journal of System Sim4ulation，2001，13（5）:666-669.

［15］Fay Chang，Jeffrey Dean，Sanjay Ghemawat et al.BigTable: a distributed storagesystemforstructureddata［J］. Operating Systems Design and Implementation，2000.

A research on resource scheduling based on ant-colony algorithm in cloud-based data center of colleges and universities

ZHAN Fei
（School of Computer Science，Xi'an Aeronautical Universities，Xi'an 710077，China）

For the purpose of constructing the cloud computing data center of colleges and universities，this article mainly focuses on cloud computing resource scheduling based on ant-colony algorithm.The proposed resource scheduling has been verified by CloudSim simulations.The simulation results reveal that both the multitask execution time and the relative standard deviation of our proposed resource scheduling based on ant-colony algorithm are to the traditional resource schedulings.

cloud computing；data center；ant-colony algorithm；cloudSim

TN91

A

1674－6236（2016）16-0018-04

2016-01-13稿件編號：201601092

國家自然科學(xué)基金項目（71373203）

戰(zhàn)非（1981—），男，陜西西安人，碩士，講師。研究方向：軟件工程、軟件開發(fā)、移動互聯(lián)網(wǎng)應(yīng)用。