高校云數據中心基于蟻群算法的資源調度研究

戰非

（西安航空學院 計算機學院，陜西 西安　710077）

高校云數據中心基于蟻群算法的資源調度研究

戰非

（西安航空學院 計算機學院，陜西 西安710077）

針對構建高校云計算數據中心的目的出發，對基于蟻群算法的云計算資源調度進行研究。通過云仿真軟件CloudSim進行仿真實驗，證明蟻群算法在多任務執行時間及相對標準差方面優于傳統資源調度算法。

云計算；數據中心；蟻群算法；CloudSim

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

云計算作為一種新興的計算模式，主要應用于互聯網中，將基礎資源設施、應用系統、軟件平臺等作為服務提供給用戶［1-2］。同時云計算也是一種基于虛擬化為基礎的架構方式，能夠將大量資源進行虛擬化，構建龐大的的資源池，對外以服務方式進行管理。

如上所述，構建基于云計算的高校數據中心便于解決傳統模式下數據中心的不足，可以實現對數據和資源更加統一的、高效的管理，為高校各部門之間的數據共享提供便利。云計算數據中心工作過程中，任務調度和資源分配是至關重要的環節，文中主要討論如何基于蟻群算法對云計算中資源進行調度，進行仿真實驗并分析結果。

1　構建高校中基于云計算的數據中心

1.1云計算高校數據中心的建設目標

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

1）硬件方面，建立一定規模的機房，實現完備的硬件設施及充足的帶寬，以擴展性強，能耗較低，安全可靠為基礎。能夠滿足學校中不同職能部門的服務要求。

2）數據存儲方面，建立集中管理、安全性強的統一數據存儲平臺，能夠保證數據更新的實時性，具有完整的重要數據的備份及容災機制。

3）網絡服務方面，能夠為學校各項工作提供持續不間斷的網絡服務，具有良好的監測機制和故障預防機制。

1.2云計算數據中心體系架構

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

圖1　云計算數據中心架構圖

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

虛擬層，該層也稱為IaaS（Infrastructure as a Service，基礎設施即服務），將物理層硬件（包括存儲設備、服務器和網絡設備等）進行全面虛擬化，構建可共享的按需分配的基礎資源設施；

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

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

2　任務調度在云計算中的應用

云計算的優勢體現在更強的計算能力和更高的計算效率，可以為用戶提供更優質的服務，而云計算中資源分配策略和任務調度策略是實現這些優勢的基礎。

2.1任務調度概念

調度問題指的是，在滿足一定的約束規則條件下，根據提前制定好的資源分配策略對單個或者多個并行的任務進行分配，以最短處理時間和提高處理性能為目標，分配給各個處理節點按一定的順序執行任務。

調度系統的好壞基于兩個基本元素，分別是性能和效率。調度算法作為調度系統的基礎，算法本身的效率和調度質量至關重要。針對云計算的特點，需要選擇更高效的算法來支持。

2.2任務調度策略分類和算法

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

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

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

3.1蟻群算法基本原理

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

蟻群算法本質是一種隨機搜索算法，具有以下行為規律：

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

2）為規避螞蟻停滯不前在本地打轉，用一個禁忌表來記錄已經走過的路徑，通過禁忌表剔除本次循環已經走過的路徑。

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

3.2蟻群算法數學模型

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

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

狀態轉移概率：

其中：

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

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

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

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

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

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

其中：

ρ表示信息素揮發系數，則1-ρ表示信息素殘留因子，規定ρ的取值范圍為ρ?［0，1］，為防止信息素隨時間進行無限聚集，這里取ρ=0.5。

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

其中：Q表示信息素強度；Lk表示螞蟻k在當前循環中走過的路徑總長度。

4　CloudSim仿真及結果分析

4.1蟻群算法調度流程

用蟻群算法進行調度，首先對并行的所有用戶任務分類，并且給出優先級順序，因為這樣才能體現出不同任務對應不同服務質量的要求。然后依據算法進行資源分配與調度，當算法找到符合服務要求的最優路徑，提供資源并進行綁定，開始執行。流程圖如圖2所示。

圖2　蟻群算法資源調度流程圖

4.2仿真測試過程

CloudSim仿真經過的步驟包括：首先新建數據中心，然后確定模擬資源參數，通過DatacenterBroker類的對象建立代理，由此代理負責信息的交互，然后創建虛擬機開始執行云任務，最終獲取結果。

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

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

/**新建虛擬機列表，根據要仿真的虛擬機規格參數（id、PE數量、MIPS速率、內存、帶寬等等）創建虛擬機vm，并提交代理*/

/**建立云任務列表，根據仿真參數（ID、PE數量、文件大小等）新建一個云任務并添加進列表，列表的創建及添加代碼省略*/

4.3實驗結果及分析

通過在CloudSim中進行實驗，設定執行的任務數為20～100，計算節點數為10個。為了說明蟻群算法在云計算中應用的效果，選取了FIFO算法和Dijkstra算法這兩種傳統算法作為對比。執行10次取平均值，執行任務所需時間如圖3所示。

通過該圖我們分析出，當任務量較少時3種算法完成任務時間基本相同，但是隨著任務量的增加，實驗表明過蟻群算法完成所有任務時間要優于另外兩種算法。為了更進一步的展示幾種算法的區別，對任務分配的結果的相對標準差值進行計算，如圖4所示。

通過該圖顯示，當任務數增加，蟻群算法的偏差值越來越小，且趨于線性漸進，明顯優于其他兩種算法。

通過以上分析，云計算的特點就是并行處理大量任務，通過蟻群算法進行資源調度可以適應常規云計算的要求。

5　結束語

云計算作為一種蓬勃發展商業計算模式，建立在將大量資源虛擬化的基礎上，可以統一對高校的數據進行管理，根據用戶對作業量的需求提供服務。文中給出高校中云計算數據中心的構建體系模型，重點討論應用蟻群算法在云計算中進行作業調度和資源分配的問題，通過CloudSim仿真實驗，從結果上對比了兩種傳統調度算法。最終證明該算法符合一般云計算任務調度和資源分配的要求。

圖3　任務執行時間結果圖

圖4　相對標準差結果圖

［1］陳全，鄧倩妮.云計算及其關鍵技術［J］.計算機應用，2009 （9）：2563-2564.

［2］劉正偉，文中領，張海濤.云計算和云數據管理技術［J］.計算機研究與發展，2012，49（z1）：56-27.

［3］孟湘來.基于云計算的數據中心構建探析［J］.中國企業教育，2012（22）：240-241.

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

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

［6］宋雪梅，李兵.蟻群算法及其應用［J］.河北理工學院學報，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

國家自然科學基金項目（71373203）

戰非（1981—），男，陜西西安人，碩士，講師。研究方向：軟件工程、軟件開發、移動互聯網應用。