戰(zhàn)非

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

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

戰(zhàn)非

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1蟻群算法基本原理

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

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

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

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

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

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

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

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

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

其中：

allowedk表示螞蟻k下一步可以選擇的地點(diǎn)。

τij（t）表示地點(diǎn)i到地點(diǎn)j的路徑在t時(shí)刻的信息素量。

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

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

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

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

其中：

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

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

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

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

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

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

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

4.2仿真測(cè)試過(guò)程

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

以下代碼為仿真過(guò)程中的核心類中截取的主要流程代碼，代碼注釋體現(xiàn)了整個(gè)仿真過(guò)程的具體步驟，調(diào)用方法中的一些仿真參數(shù)如帶寬（bw），內(nèi)存（ram），PE數(shù)（pesNumber）等等的定義語(yǔ)句，由于篇幅限制這里省略不寫，這些參數(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ù)量、文件大小等）新建一個(gè)云任務(wù)并添加進(jìn)列表，列表的創(chuàng)建及添加代碼省略*/

4.3實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

5　結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

［6］宋雪梅，李兵.蟻群算法及其應(yīng)用［J］.河北理工學(xué)院學(xué)報(bào)，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稿件編號(hào)：201601092

國(guó)家自然科學(xué)基金項(xiàng)目（71373203）

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