金 瑾, 何 嘉

(成都信息工程學(xué)院計(jì)算機(jī)學(xué)院,四川成都610225)

0 引言

云計(jì)算是近年新興的一種網(wǎng)絡(luò)應(yīng)用模式。是集網(wǎng)格計(jì)算、分布式計(jì)算、并行計(jì)算、效用計(jì)算、網(wǎng)絡(luò)存儲(chǔ)、虛擬化、負(fù)載均衡等傳統(tǒng)計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)為一體,再互相融合的產(chǎn)物。云計(jì)算的核心思想:將大量用網(wǎng)絡(luò)連接的計(jì)算資源統(tǒng)一管理和調(diào)度,從而構(gòu)成一個(gè)計(jì)算資源池。像電力資源一樣,用戶只需提出所需,云計(jì)算就能夠向提供方便快捷的服務(wù)。因此如何快速合理地對(duì)網(wǎng)絡(luò)資源進(jìn)行調(diào)度是云計(jì)算需要解決的關(guān)鍵問題,它關(guān)系到云資源環(huán)境所能提供服務(wù)的好壞。

傳統(tǒng)的資源調(diào)度算法有輪詢算法(RR),基本ACO算法等,RR算法的原理是每一次把來自用戶的請(qǐng)求輪流分配給內(nèi)部中的服務(wù)器,從1開始,直到N(內(nèi)部服務(wù)器個(gè)數(shù)),然后重新開始循環(huán)。它不考慮服務(wù)器的狀態(tài)(即不關(guān)心當(dāng)前服務(wù)器的連接數(shù)和響應(yīng)速度),因此當(dāng)請(qǐng)求服務(wù)間隔時(shí)間變化比較大時(shí),輪詢調(diào)度算法容易導(dǎo)致調(diào)度不平衡。目前的資源調(diào)度策略大多數(shù)是通過虛擬機(jī)級(jí)別上的調(diào)度技術(shù)結(jié)合一定的調(diào)度策略為虛擬機(jī)內(nèi)部應(yīng)用做資源調(diào)度[1],例如文獻(xiàn)[2]針對(duì)計(jì)算集群中的虛擬機(jī)調(diào)度進(jìn)行建模,根據(jù)虛擬機(jī)的負(fù)載動(dòng)態(tài)調(diào)節(jié)處理器電壓,文獻(xiàn)[3-4]通過動(dòng)態(tài)分配云計(jì)算數(shù)據(jù)中心的虛擬機(jī),減少服務(wù)器的個(gè)數(shù),文獻(xiàn)[5]給出基于門限的云計(jì)算資源動(dòng)態(tài)調(diào)度方法,文獻(xiàn)[6]提出基于博弈論的云計(jì)算資源分配算法。這些資源調(diào)度方法雖在一定程度上提高了源調(diào)度的效率,然而面對(duì)數(shù)量龐大的資源時(shí)卻時(shí)常會(huì)遇到瓶頸,而智能算法的各方面優(yōu)點(diǎn)表明其對(duì)于像云資源調(diào)度類的調(diào)度問題顯示出一定的優(yōu)越性。

蟻群算法是20世紀(jì)90年代初意大利的M.Dorigo等學(xué)者提出的[7],與遺傳算法、粒子群算法等智能算法一樣,蟻群算法是模擬現(xiàn)實(shí)世界中真實(shí)螞蟻的覓食行為而形成的一種模擬進(jìn)化算法,這些學(xué)者們充分利用蟻群搜索食物的過程與旅行商問題之間的相似性,解決了TSP問題,取得了很好的結(jié)果。大量的實(shí)驗(yàn)結(jié)果還證明蟻群算法的有效性和在某些領(lǐng)域的優(yōu)勢(shì)[8-9]。同時(shí),蟻群算法也存在一定的缺陷,即搜索時(shí)間過長和容易陷入局部較優(yōu)解[10],蟻群算法在動(dòng)態(tài)環(huán)境下也表現(xiàn)出高度的靈活性和健壯性,成功解決了許多組合優(yōu)化問題。云計(jì)算中的任務(wù)調(diào)度問題,實(shí)質(zhì)上是一種尋找較優(yōu)解的問題,即,從資源分配給任務(wù)的多個(gè)解中選出較優(yōu)解的一種過程,從解決問題角度看,蟻群優(yōu)化算法非常適合解決云環(huán)境中的資源調(diào)度問題[11]。

1 基本蟻群優(yōu)化算法的原理

以MMAS應(yīng)用于TSP問題的求解為例闡述基本蟻群優(yōu)化算法的原理[12-15]。

為了便于描述問題,首先引入以下符號(hào):m:螞蟻數(shù)量,dij(i,j=1,2,…,n):城市之間的距離;τij(t):t時(shí)刻在城市i,j連線的殘留信息量,一般取τij(0)=C(C常數(shù));ηij:t時(shí)刻螞蟻由城市i轉(zhuǎn)移到城市j的啟發(fā)信息,一般取;即信息素的大小為兩城市距離的倒數(shù)。

pij(t):t時(shí)刻螞蟻由城市i轉(zhuǎn)移到城市j的概率,計(jì)算公式為:

其中reallowedk表示螞蟻k下可走的城市集,它是動(dòng)態(tài)變化的,因螞蟻k的進(jìn)程而改變;信息量 τij(t)會(huì)逐漸衰弱,1-p:衰減程度;α:螞蟻所積累的信息量(在運(yùn)動(dòng)過程中),β:啟發(fā)式因子所起的不同作用(在螞蟻選路的過程中);

蟻群算法的步驟:

(2)螞蟻根據(jù)公式(1)選擇所要走的下一個(gè)城市,并修改 tabuk;

(3)每只螞蟻?zhàn)咄暌粭l邊后,按式 τij(t+1)=(1-ρ).τij(t)+ρ Δτkij更新該邊的信息素,其中 Δτkij=Q/lp,其中l(wèi)p是螞蟻從初始位置到當(dāng)前城市走過的路徑長度。ρ表示信息的持久性。對(duì)于所有邊(i,j)限制 τij(t)∈[τmin(t),τmax(t)];超出這個(gè)范圍的值被強(qiáng)制設(shè)為 τmax或者是 τmin。這樣做可以使信息素較為平均,防止信息素大小兩極分化,從而使算法更好地尋優(yōu);

(4)計(jì)算最佳路徑。當(dāng)全部螞蟻?zhàn)咄晁谐鞘泻?按下面式計(jì)算最優(yōu)路徑的長度并且保留,

lmin=minlk,k=(1,2,…,m),其中 lk:第k只螞蟻所走路徑長度;

(5)經(jīng)過n個(gè)時(shí)刻。螞蟻k一次循環(huán)結(jié)束,即所有的城市都走完一遍。此時(shí),要根據(jù)下式對(duì)這一輪遍歷的全局最優(yōu)路徑上的信息量作一些更新::全局信息素?fù)]發(fā)系數(shù),lk:最優(yōu)路徑長度;

(6)如果設(shè)置的迭代次數(shù)未完,則清空禁忌表,重復(fù)上述過程。

2 GA-ACO與云計(jì)算資源調(diào)度

2.1 問題描述

采用所提出的GA-ACO算法尋找當(dāng)前策略中的最優(yōu)或較優(yōu)的策略。由于云計(jì)算環(huán)境的特殊性和復(fù)雜性,需先對(duì)云資源調(diào)度問題與傳統(tǒng)的應(yīng)用蟻群算法的TSP問題進(jìn)行關(guān)聯(lián),以供改進(jìn)蟻群算法來適合云資源調(diào)度問題的使用[16],云資源調(diào)度問題與傳統(tǒng)的TSP問題的差異主要體現(xiàn)在以下3個(gè)方面:

(1)在TSP問題中,城市之間會(huì)有固定的拓?fù)浣Y(jié)構(gòu)。而云環(huán)境中的資源并不是固定不變的,所以也不存在固定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。

(2)在TSP問題中,城市之間的信息素用城市之間的距離的倒數(shù)表示。而在云計(jì)算環(huán)境中則需要用資源的通信能力和計(jì)算能力等相關(guān)系數(shù)表示信息素。

(3)啟發(fā)信息也起著非常重要的作用,在云環(huán)境中,需要以資源固有屬性(如計(jì)算和通信能力)表示在蟻群算法中的啟發(fā)信息。

把云計(jì)算資源調(diào)度的問題描述如下:設(shè)有 T個(gè)需要執(zhí)行的任務(wù),P個(gè)可用的資源。用集合表示為:任務(wù)集合T={T1,T2,…,Tn};資源集合 P={P1,P2,…,Pm};用 Ti表示第i個(gè)子任務(wù),Pj表示第j個(gè)處理機(jī)資源。資源調(diào)度就是將n個(gè)子任務(wù)分配給m個(gè)處理機(jī)資源,從而使所有任務(wù)的完成時(shí)間最短,資源的利用率最高。

云資源調(diào)度的目標(biāo)即是求(2)式的最小值[17]:

(2)式中,∑imi=M,M是給定時(shí)間內(nèi)交給云計(jì)算環(huán)境的總?cè)蝿?wù)量,mi表示資源i上分配mi個(gè)任務(wù),0≤表示資源i上反能執(zhí)行的最大任務(wù)并行數(shù)。

2.2 GA-ACO算法及在云資源調(diào)度中的應(yīng)用

設(shè)第i個(gè)資源的處理能力為Pi,資源負(fù)載平衡能力為Li,任務(wù)節(jié)點(diǎn)與調(diào)度節(jié)點(diǎn)的通信能力為Ci,則每個(gè)資源的初始信息素表示為:τi(0)=α Pi+βCi+θ Li,其中 α,β,θ表示資源的處理能力初始化因子、資源節(jié)點(diǎn)間通信能力初始化因子和負(fù)載平衡能力初始化因子。

t時(shí)刻,第i個(gè)螞蟻選擇資源j的概率由下面的公式確定:

基中參數(shù)α 1代表信息素的重要程度,β1代表資源屬性的重要程度,τj(t)表t時(shí)刻資源j的信息素濃度,ωu表示能見度因素。

遺傳算法的全局搜索能力很強(qiáng),但是局部搜索能力較弱[18],此算法運(yùn)算簡單,收斂速度快,但是求解到一定程度時(shí)往往出現(xiàn)收斂停滯現(xiàn)象。而蟻群算法采用正反饋原理[19],加快了進(jìn)化速度,但是其全局搜索能力較差,容易限入局部解。兩個(gè)算法優(yōu)缺點(diǎn)具有互補(bǔ)的特性。文中所提出的GA-ACO算法即是將遺傳算法和蟻群算法進(jìn)行交叉融合,從而克服各自的缺點(diǎn),達(dá)到較好的優(yōu)化性能。GA-ACO算法對(duì)于蟻群算法的每個(gè)解,用局部搜索算法來精煉,并更新每個(gè)資源的信息素。然后,用GA算法的進(jìn)化算子進(jìn)化出新的解,再利用MMAS的轉(zhuǎn)移概率建立GA算法的交叉算子。

GA-ACO算法步驟如下:

(1)初始化 nk個(gè)解;

(2)對(duì)每個(gè)個(gè)體的解 xk(k=1,2,…,nk)執(zhí)行局部搜索;根據(jù)(1)式對(duì)更新信息素;

(3)對(duì)于 k=1,2,…,nk/2,隨機(jī)選擇兩個(gè)父代 xa和xb,對(duì) xa和xb進(jìn)行交叉操作得到x′,如果 U(0,1)≤pm,則對(duì) x′進(jìn)行變異;

(4)用子代代替群體中較差的那一半;再根據(jù)(1)式更新信息素。

(5)若迭代未完成,則一直重復(fù)上述步驟,直到迭代完成。

其中交叉算法如下:

輸入:xa和xb

令 x′=xa;

For所有的(i,j)∈x′and(i,j)?xb

do從 x′中刪除(i,j);

End

基于公式(3)連接各個(gè)部分。

3 仿真實(shí)驗(yàn)結(jié)果與討論

所做的算法應(yīng)用于云計(jì)算資源調(diào)度中,因此分別用MATLAB軟件和云計(jì)算仿真軟件(cloudsim)進(jìn)行仿真。MATLAB軟件是常用的仿真軟件,具有用法靈活、程式結(jié)構(gòu)性強(qiáng)、延展性好等優(yōu)點(diǎn),自帶了很多智能計(jì)算的工具箱,方便進(jìn)行計(jì)算機(jī)仿真。而CloudSim是一個(gè)新的、通用的和可擴(kuò)展的仿真框架,用于新的云計(jì)算基礎(chǔ)設(shè)施和應(yīng)用服務(wù)的無縫建模、仿真和試驗(yàn)。

為驗(yàn)證GA-ACO算法的收斂性,用ACO算法與GA-ACO算法在MATLAB仿真平臺(tái)下的收斂性進(jìn)行對(duì)比,結(jié)果如圖1和圖2所示。GA-ACO算法當(dāng)?shù)螖?shù)為100次時(shí),其精度為10-5,而基本的ACO算法迭代資數(shù)為3000次時(shí)精度不足10-2。實(shí)驗(yàn)結(jié)果表明,改進(jìn)后的GA-ACO算法收斂度和精度相較于ACO算法都有所提高。

圖1 ACO算法的性能

圖2 GA-ACO算法的性能

另外,采用CloudSim仿真平臺(tái)驗(yàn)證改進(jìn)算法相較于其它調(diào)度算法的優(yōu)越性,用云資源調(diào)度算法中傳統(tǒng)算法輪詢調(diào)度算法(RR)、ACO算法及GA-ACO算法分別進(jìn)行調(diào)度。實(shí)驗(yàn)主要參數(shù)取值為:時(shí)間長度 T為24小時(shí),利用率閾值為80%,預(yù)測時(shí)間間隔為200s,改進(jìn)蟻群算法中 α為1,β為4,ρ為0.5,螞蟻數(shù)量為80,最大迭代次數(shù)為120。假定數(shù)據(jù)中心有50臺(tái)宿主機(jī),CPU數(shù)在[1,5]內(nèi)隨機(jī)產(chǎn)生,MIPS為800,虛擬機(jī)所需CPU數(shù)為1,MIPS在[100,900]內(nèi)隨機(jī)產(chǎn)生,實(shí)驗(yàn)的任務(wù)數(shù)量分別是[50,100,150,200,250,300,350,400]。實(shí)驗(yàn)結(jié)果如圖3所示,當(dāng)任務(wù)數(shù)量250時(shí),GA-ACO算法相的平均時(shí)間比ACO和RR算法分別少50和100s,而且隨著任務(wù)數(shù)量越來越多,改進(jìn)的GA-ACO算法后期隨著信息素的增加,正反饋性增強(qiáng),時(shí)間增加的幅度要遠(yuǎn)小于RR和ACO算法。因此所提出的GA-ACO算法在任務(wù)數(shù)量較多的時(shí)候執(zhí)行效率要高,而執(zhí)行時(shí)間要短。

圖3 任務(wù)執(zhí)行的平均時(shí)間對(duì)比

4 結(jié)束語

利用遺傳算法對(duì)蟻群算法進(jìn)行改進(jìn),并且引入最大最小蟻群算法對(duì)基于蟻群算法進(jìn)行優(yōu)化,從而使兩種算法融合,改善原來算法的缺陷。形成新的GA-ACO算法,用實(shí)驗(yàn)討論了新算法的精度和收斂度,相較于基于的ACO算法,新算法的精度和收斂度都有顯著的提高,結(jié)合云計(jì)算資源調(diào)度的一些特點(diǎn),將新算法應(yīng)用于云資源調(diào)度中,與傳統(tǒng)算法相比,新算法大大縮短了任務(wù)的平均運(yùn)行時(shí)間,提高了資源的利用效率。

[1] Ge R,Feng X,Cameron K.Performance-constrained distributed dvs scheduling for scientific applications on power-aware clusters[A].Proceedings of the 2005 ACM/IEEE conference on Supercomputing[C].IEEE Computer Society,Washington DC,USA,2005:34-35.

[2] Von L G,Wang L,Younge A J,et al.Power-Avare Scheduling of Virtual Machines in DVFS-enabled Clusters[A].Proc.Of IEEE International Conference on Cluster Computing 2009[C].New Orleans,LA,USA,2009:1-10.

[3] Beloglazov A,Abawajy J,Buyya R.Energy-Aware Resource Allocation Heuristics for Efficient Management of Data Centers for Cloud computing[J].Future Generation Computer Systems,2012,28(5):755-768.

[4] Buyya R,Beloglazov A,Abawajy J.Energy-Efficient Management of Data Center Resources for Cloud Com-puting:A Vision,Architectural Elements,and Open Challenges[C].Proceedings of the 2010 International Conference on Parallel and Distributed Processing Techniques and Applications(PDPTA2010),Las Vegas,USA,July 2010:215-224.

[5] Lin Wei-Wei,Wang J Z,Liang Chen.et al.A Threshold-based Dynamic Resource Allocation Scheme for Cloud Computing[J].Procedings Engineering,2011,23(8):695-703.

[6] Wei Gui-yi,Visilakos A,Zheng Yao,et al.A gametheoretic method of fair resource allocation for cloud computing services[J].The Jounal of Supercomputing,2010,54(2):252-269.

[7] Dorigo M,Maniezzo V.Colorni A.Ant system:optimization by a colony of cooperating aigents[J].IEEE Transactions on SMC,1996,26(1):29-41.

[8] Dorigo M,Gambardella L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutional Comutation,1997,1(1):53-66.

[9] Dorigo M,Gambardella L M.A study of some properties of ant-Q[A].Voigt H-M,Ebeling W,Rechenberg I,etal.Proceedings of the PPSN 44th International Conference on Parallel Problem Solving from Nature[C].Berlin:Springer-Verlag,1996:656-665.

[10] Dorigo M,Maniezzo V,Colorni A.Ant system:an autocatalytic optimizing process[J].Tech Rep,1991:91-106.

[11] 王天擎,謝軍,曾洲.基于蟻群算法的網(wǎng)格資源調(diào)度策略研究[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(15):3611-3613.

[12] 段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社,2005:385-390.

[13] 譚營.計(jì)算群體智能基礎(chǔ)[M].北京:清華大學(xué)出版社,2009:263-265.

[14] 王永貴,韓瑞蓮.基于改進(jìn)蟻群算法的云環(huán)境任務(wù)調(diào)度研究[J].計(jì)算機(jī)測量與控制,2011,19(5):1203-1211.

[15] 曹文梁,康嵐蘭.基于遺傳算法的混合蟻群算法及其在TSP中的應(yīng)用研究[J].2011,33(1):91-93.

[16] McKerrow P.Modelling the dragan-f lyer Four-Rotor Helicopter[A].Proceedings of IEEE International Conference on Robotics Automation[C].2004:3596-3601.

[17] 李士勇.蟻群算法及其應(yīng)用[M].哈爾濱:哈爾濱工業(yè)大學(xué)出版社,2004:101-108.

[18] RowlinsG,ed.Foundations of Genetic Algorithm[J].Los Altos Morgan Kan fmann,1991:767-777.

[19] C M White,G G Yen.A Hybrid Evolutionary Algorithm for TSP[J].In Proceedings of the IEEE Congress on Evolutionary Computation.2004,12(2):1473-1478.