基于改進(jìn)粒子群算法的云計(jì)算資源調(diào)度模型的研究

趙 宏 偉

(沈陽大學(xué) 信息工程學(xué)院, 遼寧 沈陽　110044)

基于改進(jìn)粒子群算法的云計(jì)算資源調(diào)度模型的研究

趙 宏 偉

(沈陽大學(xué) 信息工程學(xué)院, 遼寧 沈陽110044)

摘要:為實(shí)現(xiàn)云計(jì)算資源的合理運(yùn)用和負(fù)載均衡,提出了云計(jì)算資源的動態(tài)調(diào)度管理框架,設(shè)計(jì)了一種考慮各虛擬機(jī)資源數(shù)、各虛擬機(jī)性能,以及當(dāng)前的負(fù)載情況的資源分配算法,實(shí)現(xiàn)了一種改進(jìn)的粒子群算法的云計(jì)算資源動態(tài)調(diào)度模型.實(shí)驗(yàn)結(jié)果表明,此調(diào)度模型能有效改善動態(tài)資源的分配,提高云計(jì)算系統(tǒng)中資源的利用率.

關(guān)鍵詞:分布式; 云計(jì)算; 粒子群; 負(fù)載平衡

云計(jì)算[1]是一種計(jì)算方式,通過互聯(lián)網(wǎng),以資源的形式提供給用戶.目前,在云計(jì)算的各個(gè)方面都有了大量的研究,比較著名的系統(tǒng)如Google公司推出的Hadoop的體系結(jié)構(gòu)和Amazon的彈性計(jì)算云系統(tǒng)(elasticcomputecloud,簡稱EC2)等[2].在云計(jì)算系統(tǒng)中,由于云計(jì)算的復(fù)雜性和不確定性,云資源呈現(xiàn)動態(tài)變化的特點(diǎn),為了提高資源利用率和系統(tǒng)的吞吐率,如何進(jìn)行資源的調(diào)度成為了云計(jì)算系統(tǒng)中的核心.

目前,學(xué)術(shù)界在云計(jì)算環(huán)境下的資源調(diào)度方面已經(jīng)進(jìn)行了大量研究工作,2009年,NimBus等提出了基于貪婪算法的云計(jì)算資源調(diào)度模型,該云計(jì)算模型簡單,并沒有考慮載負(fù)載平衡;文獻(xiàn)[3]提出了一種云資源調(diào)度模型----云效用最大化模型,與傳統(tǒng)調(diào)度模型相比,目標(biāo)函數(shù)不再是最小化最大完工時(shí)間,而是以達(dá)到效用最大為調(diào)度目標(biāo),但難以滿足日益增長的云計(jì)算規(guī)模;文獻(xiàn)[4]根據(jù)云計(jì)算的彈性化和虛擬化等新特性,提出了云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理模型和虛擬機(jī)放置多目標(biāo)優(yōu)化遺傳算法,但云計(jì)算系統(tǒng)模型考慮不完美,并且最優(yōu)化達(dá)不到期望的效果.隨著仿生智能算法的發(fā)展,不少學(xué)者提出了基于蟻群算法、粒子群算法、遺傳算法等的云計(jì)算資源調(diào)度模型,這些仿生智能算法具有搜索能力強(qiáng)、并行性好等特點(diǎn),可以快速找到云計(jì)算資源最優(yōu)調(diào)度方案,有效提高云計(jì)算資源的利用效率[5].然而,仿生智能算法在實(shí)際應(yīng)用中,它們均存在易陷入局部最優(yōu)解,收斂速度慢等缺陷,有時(shí)不能獲得最優(yōu)資源調(diào)度方案,這就需要對仿生智能算法進(jìn)行改進(jìn)和完善[6].

從以上分析可知,云計(jì)算系統(tǒng)中的資源請求時(shí),根據(jù)資源調(diào)度動態(tài)變化的特點(diǎn),需要考慮各個(gè)方面的因素,因此,本文設(shè)計(jì)的調(diào)度框架,綜合考慮了SLA、應(yīng)用性能、負(fù)載平衡、結(jié)點(diǎn)性能、虛擬機(jī)性能等多個(gè)因素,設(shè)計(jì)了云計(jì)算資源的動態(tài)調(diào)度管理框架,并設(shè)計(jì)了一種高效率的改進(jìn)的PSO算法.

1云計(jì)算環(huán)境下的動態(tài)資源調(diào)度框架

圖1云計(jì)算資源的動態(tài)調(diào)度管理框架

Fig.1Dynamicschedulingmanagementframeworkofcloudcomputingresources

針對傳統(tǒng)云計(jì)算系統(tǒng)中調(diào)度系統(tǒng)結(jié)構(gòu)的優(yōu)缺點(diǎn),提出了一種綜合考慮SLA、應(yīng)用性能、負(fù)載平衡、結(jié)點(diǎn)性能、虛擬機(jī)性能等多個(gè)因素的云計(jì)算調(diào)度系統(tǒng)框架,調(diào)度系統(tǒng)的結(jié)構(gòu)如圖1所示.在云計(jì)算系統(tǒng)中調(diào)度分為兩級調(diào)度:一級調(diào)度為任務(wù)級調(diào)度,主要作用是為用戶提交的任務(wù)提供相應(yīng)的虛擬機(jī)資源,達(dá)到虛擬機(jī)資源的有效使用;二級調(diào)度為虛擬機(jī)布置調(diào)度,主要功能是把虛擬資源合理布置到物理機(jī)資源上,以達(dá)到物理機(jī)資源的最優(yōu)配置.

整個(gè)調(diào)度系統(tǒng)框架主要由以下部分組成:

(1) 云計(jì)算平臺門戶.主要通過WEB方式,負(fù)責(zé)接收用戶提交的各類任務(wù),平臺門戶中包括SAAS、PAAS、IAAS等各類應(yīng)用服務(wù).

(2) 資源描述模塊.資源描述模塊接收到任務(wù)后,首先判斷任務(wù)所調(diào)度應(yīng)用的類型,從而獲取應(yīng)用性能(應(yīng)用所需資源情況);其次,根據(jù)用戶的服務(wù)質(zhì)量(SLA),得到用戶所能接受的任務(wù)處理結(jié)果,例如最小完成時(shí)間或最低費(fèi)用等,并把分析結(jié)果發(fā)布給資源預(yù)測模塊.

(3) 資源預(yù)測模塊.該模塊主要根據(jù)資源描述模塊提供SLA和應(yīng)用性能的信息,對用戶提交的任務(wù)進(jìn)行資源需求預(yù)測.

(4) 虛擬資源調(diào)度模塊.該模塊主要根據(jù)資源預(yù)測模塊預(yù)測的結(jié)果和VM資源的使用情況,包括VM的CPU利用率、內(nèi)存使用情況和I/O使用情況等信息,采用基于粒子群的多目標(biāo)優(yōu)化方法,得到相應(yīng)資源池,在相應(yīng)的資源池中,獲取云環(huán)境中最優(yōu)的虛擬資源,進(jìn)行資源配置,布置任務(wù).

(5) 資源池(POOL)模塊.調(diào)度系統(tǒng)設(shè)計(jì)了不同應(yīng)用類型的資源池,包括計(jì)算密集型、存儲密集型和應(yīng)用密集型等各類的資源池.調(diào)度系統(tǒng)根據(jù)用戶提交任務(wù)的情況,進(jìn)行不同資源池的調(diào)度,這時(shí),資源池也將把本資源池的情況,發(fā)布給VMMomiter模塊.

(6)VMMomiter模塊.主要功能包括:①VMMomiter監(jiān)視虛擬資源(VM)和物理資源結(jié)點(diǎn)(PM)的使用情況,提供所監(jiān)視的信息,并確定什么時(shí)候進(jìn)行全局的VM布置;②監(jiān)視虛擬資源(VM)的過載或低載,確定什么時(shí)候進(jìn)行VM遷移;③基于虛擬機(jī)規(guī)則器產(chǎn)生的布置策略,進(jìn)行全局虛擬機(jī)放置;④基于虛擬機(jī)規(guī)則器產(chǎn)生的遷移策略,進(jìn)行虛擬機(jī)遷移,及將這些虛擬機(jī)遷移到哪個(gè)結(jié)點(diǎn).

(7) 物理資源調(diào)度模塊.物理資源調(diào)度模塊實(shí)質(zhì)上是VM放置模塊,主要是將VM映射到PM,物理資源調(diào)度模塊的任務(wù)是通過改變VM的布局和配置來滿足不同POOL和不同應(yīng)用性能的目標(biāo).

(8) 虛擬機(jī)規(guī)則器模塊.虛擬機(jī)規(guī)則器,根據(jù)物理資源調(diào)度模塊提供的多目標(biāo)優(yōu)化產(chǎn)生的策略,通知VMMomiter進(jìn)行資源的布置或遷移.策略主要刻畫了應(yīng)用性能與所需資源關(guān)系模型,實(shí)現(xiàn)了在虛擬機(jī)資源配置中滿足一定性能的條件上,提高資源的使用效率.

(9) 物理資源模塊(PM).物理資源模塊主要包括一些服務(wù)器、存儲空間等硬件設(shè)備,這些設(shè)備分布在各個(gè)結(jié)點(diǎn),統(tǒng)一作為云計(jì)算中心的基礎(chǔ)設(shè)施,供虛擬資源使用.

2基于改進(jìn)粒子群算法FPSO的多目標(biāo)優(yōu)化

由于在云計(jì)算環(huán)境中,資源調(diào)度分為兩級調(diào)度:一級的虛擬資源調(diào)度,主要是為用戶任務(wù)分配可用的虛擬資源,另一級是物理資源調(diào)度,主要是虛擬機(jī)布置到適合的物理機(jī)資源的調(diào)度.物理資源調(diào)度可以通過Kvm、Vmvare等中間件的虛擬機(jī)模板,完成虛擬機(jī)到物理資源的映射.因此,本文主要針對虛擬資源調(diào)度模型進(jìn)行研究.

2.1基本粒子群算法

基本的PSO算法利用式(1)和式(2)來計(jì)算在D維空間中的優(yōu)化問題,第t代的第d維(d=1,2,3,…,D)的速度和位置可以表示如下:

2.2改進(jìn)粒子群算法FPSO

改進(jìn)粒子群算法主要是把負(fù)載的指標(biāo)和服務(wù)質(zhì)量指標(biāo)引入到基本PSO算法中, 本文對于PSO的改進(jìn)主要體現(xiàn)在粒子群的初始化和適應(yīng)度函數(shù)(Fitness)設(shè)計(jì)方案上, 對于一個(gè)粒子的適應(yīng)度計(jì)算, 通過式(3)即可. 式(3)用來優(yōu)化服務(wù)質(zhì)量和應(yīng)用負(fù)載兩個(gè)目標(biāo), 一旦發(fā)現(xiàn)有直接影響云計(jì)算系統(tǒng)性能的延遲, 就觸發(fā)第二級調(diào)度調(diào)度程序, 進(jìn)行虛擬機(jī)遷移或重新布置虛擬機(jī). 式(3)列出了云資源調(diào)度系統(tǒng)的虛擬機(jī)調(diào)度的模型.

(1) 負(fù)載的指標(biāo).主要考慮CPU利用率、CPU就緒隊(duì)列長度、內(nèi)存使用情況和磁盤訪問頻度,以及I/O速度等.

(2) 服務(wù)質(zhì)量的指標(biāo).云計(jì)算系統(tǒng)中,每隔一個(gè)固定的小時(shí)間段,虛擬機(jī)向VMMoniter提供虛擬機(jī)負(fù)載信息,VMMoniter根據(jù)匯報(bào)信息進(jìn)行更新.資源是動態(tài)產(chǎn)生的,在本模型中考慮的負(fù)載指標(biāo)主要包括各虛擬機(jī)當(dāng)前負(fù)載、性能、任務(wù)數(shù)等.我們可以靜態(tài)或動態(tài)地確定負(fù)載指標(biāo)的權(quán)重.

通過計(jì)算公式(3),函數(shù)Prank(Si)給出對應(yīng)于虛擬機(jī)Si的服務(wù)質(zhì)量,得到虛擬資源的質(zhì)量指標(biāo).

Prank(Si)=min(E(Si),LifeTime(Si))+

式中,E(Si)是虛擬機(jī)的平均執(zhí)行的時(shí)間,LifeTime(Si)是為Si的生存周期, 其中l(wèi)ic是Si和VMMoniter(c)之間需要傳輸?shù)臄?shù)據(jù)量,bic是Si和VMMoniter(c)之間傳輸?shù)木W(wǎng)絡(luò)帶寬,a1,a2,…,an是選定的負(fù)載指標(biāo);k1,k2,…,kn是權(quán)重.如果有資源請求到達(dá),對每個(gè)虛擬機(jī)采用式(3)的方法計(jì)算得到初始化的粒子群,其中每個(gè)粒子是一個(gè)調(diào)度方案,最后基于式(1)、式(2)求出最優(yōu)解,基于粒子群算法優(yōu)化調(diào)度算法,流程如圖2所示.

云計(jì)算環(huán)境下虛擬資源調(diào)度的FPSO的步驟:

步驟1首先根據(jù)式(3)云計(jì)算系統(tǒng)資源初始化虛擬資源池的粒子數(shù),將資源池分為n個(gè)粒子.

圖2　基于FPSO粒子群算法優(yōu)化調(diào)度算法流程

步驟2針對初始粒子群,設(shè)置初始位置和初始速度.

步驟3根據(jù)式(3)計(jì)算每個(gè)粒子的適應(yīng)度值,并從中選擇最優(yōu)粒子作為個(gè)體最優(yōu)解.

步驟4根據(jù)式(1),式(2)更新粒子群的速度和位置,并與個(gè)體最優(yōu)解和群體最優(yōu)解進(jìn)行比較,根據(jù)結(jié)果更新個(gè)體最優(yōu)解.

步驟5對終止條件進(jìn)行判斷,若滿足則對群體最優(yōu)粒子位置進(jìn)行解碼,得到云計(jì)算資源的最優(yōu)調(diào)度方案,否則,返回步驟3繼續(xù)進(jìn)行迭代.

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

實(shí)驗(yàn)算法部分,選擇Sphere、Rosenbrock、Griewank[7]標(biāo)準(zhǔn)測試函數(shù)用于測試提出的FPSO算法的性能,并與PSO算法進(jìn)行了性能比較.3個(gè)函數(shù)中前兩個(gè)是單峰函數(shù),后一個(gè)是多峰函數(shù).實(shí)驗(yàn)工具采用MATLAB7,種群的初始設(shè)置如表1所示.

表1　測試函數(shù)參數(shù)設(shè)置

實(shí)驗(yàn)結(jié)果如表2所示.從表中可以看出,在3種測試函數(shù)中,FPSO算法獲得的平均適應(yīng)度值幾乎都要好于PSO算法,在Sphere、Rosenbrock 2個(gè)函數(shù)中的表現(xiàn)尤為明顯.FPSO算法獲得的標(biāo)準(zhǔn)方差也要小于PSO算法,并且FPSO算法能夠避免收斂較快而陷入局部最優(yōu).因此,FPSO比PSO算法更穩(wěn)定,具有較強(qiáng)的魯棒性.

表2　FPSO與PSO結(jié)果比較

本文對Cloudsim云計(jì)算的模擬平臺進(jìn)行了擴(kuò)展,重寫一系列的類,模擬了云計(jì)算的計(jì)算和網(wǎng)絡(luò)資源,結(jié)果見圖3～圖6.

在模擬實(shí)驗(yàn)中,進(jìn)行100次迭代,基于PSO資源分配算法和本文提出的FPSO云計(jì)算的資源分配算法的收斂效果比較,從圖3可以看出考慮負(fù)載指示FPSO收斂更快.在設(shè)置用戶提交200個(gè)任務(wù),分別進(jìn)行任務(wù)完成時(shí)間、負(fù)載平衡和服務(wù)質(zhì)量的情況進(jìn)行實(shí)驗(yàn)比較,圖4、圖5可以看出,在保證負(fù)載平衡的情況下,FPSO隨著任務(wù)的增加,完成時(shí)間要少于基于PSO的資源調(diào)度算法,圖6顯示出FPSO的服務(wù)質(zhì)量要優(yōu)于PSO.

總體實(shí)驗(yàn)表明,采用PSO資源分配算法比較簡單,并不考慮虛擬機(jī)的實(shí)際負(fù)載情況,資源處理的響應(yīng)時(shí)間較長,而采用本文提出的基于改進(jìn)的粒子群FPSO資源分配算法,資源是動態(tài)分配的,可以使各個(gè)虛擬機(jī)的負(fù)載得到均衡,加快了資源調(diào)度的速度,有效縮短任務(wù)的完成時(shí)間.從圖4結(jié)果來看,本算法在迭代次數(shù)較多、節(jié)點(diǎn)較多,有效資源較少的情況下工作效率明顯比PSO資源分配算法高,而這種情況正是云環(huán)境所具有的特點(diǎn).所以本算法在云計(jì)算環(huán)境中更有優(yōu)勢,提高了整個(gè)云計(jì)算系統(tǒng)的并行運(yùn)行的效率.

圖3　兩種資源分配算法迭代收斂比較

圖4　兩種資源分配算法完成時(shí)間比較

圖5　兩種資源分配算法負(fù)載平衡比較

圖6　兩種資源分配算法服務(wù)質(zhì)量比較

4結(jié)論

本文提出了一種改進(jìn)的粒子群的云計(jì)算系統(tǒng)的動態(tài)調(diào)度系統(tǒng),并分析了云計(jì)算系統(tǒng)調(diào)度所涉及到的具體的模式和技術(shù),提出了云計(jì)算資源的動態(tài)調(diào)度管理框架,給出了框架系統(tǒng)結(jié)構(gòu)形式,然后設(shè)計(jì)并實(shí)現(xiàn)了一種綜合考慮各虛擬機(jī)任務(wù)數(shù)和各個(gè)虛擬機(jī)性能以及當(dāng)前的負(fù)載情況的改進(jìn)的粒子群資源分配算法FPSO.對于二級調(diào)度系統(tǒng)采用原始的虛擬機(jī)模板方式,通過VMMoniter對虛擬機(jī)進(jìn)行監(jiān)測,用來解決云計(jì)算系統(tǒng)調(diào)度中存在的延遲等問題,最后通過實(shí)例驗(yàn)證本文提出的方法相對于其他方法的優(yōu)越性.

參考文獻(xiàn):

[1] ARMBRUST M, FOX A, GRIFFITH R. A view ofcloud computing[J]. Communications of the ACM, 2010,53(4):50-58.

[2] COELLO C, CARLOS A, LECHUGA M S. MOPSO: a proposal for multiple objective particle swarm optimization[C]∥Proceedings of IEEE Congress on Evolutionary Computation, USA, Honolulu: IEEE, 2002:1051-1056.

[3] GOIRI I, GUITART J, TORRES J. Characterizing cloud federation for enhancing providers profit[C]∥3rd International Conference on Cloud Computing (CLOUD 2010), 2010:123-130.

[4] 師雪霖,徐恪. 云虛擬機(jī)資源分配的效用最大化模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2013,36(2):252-262.

(SHI X L, XU G. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013,36(2):252-262.)

[5] 李強(qiáng),郝沁汾,肖利民,等. 云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化[J]. 計(jì)算機(jī)學(xué)報(bào), 2011,34(12):2256-2257.

(LI Q, HAO X F, XIAO L M. Adaptive management and multi-objective optimization for virtual machine placement in cloud computing[J]. Chinese Journal of Computers, 2011,34(12):2256-2257.)

[6] 田冠華,孟丹,詹劍鋒. 云計(jì)算環(huán)境下基于失效規(guī)則的資源動態(tài)提供策略[J]. 計(jì)算機(jī)學(xué)報(bào), 2010,33(10):1859-1872.

(TIAN G H, MENT D, ZHAN J F. Reliable resource provision policy for cloud computing[J]. Chinese Journal of Computers, 2010,33(10):1859-1872.)

[7] 雷德明,嚴(yán)新平. 多目標(biāo)智能優(yōu)化算法及其應(yīng)用[M]. 北京:科學(xué)出版社, 2009:19-59.

【責(zé)任編輯: 肖景魁】

(LEI D M, YAN X P. Intelligent multi-objective optimization algorithm and application[M]. Beijing: Science Press, 2009:19-59.)

Resource Schedule Model Base on Improved PSO in Cloud Computing

ZhaoHongwei

(School of Information Engineering, Shenyang University, Shenyang 110044, China)

Abstract:A dynamic dispatching management framework is proposed to implement the rational use and load balancing of the resource of cloud computing. A resource allocation algorithm is designed, which comprehensively applies PSO and considers the resource numbers and performance of each virtual machine and current loading conditions. An improved cloud computing resources dynamic scheduling model based on PSO is realized. The result of the experiment indicates that the scheduling system can improve the efficiency of dispatching service and the utilization ratio in the cloud computing system.

Key words:distributed; cloud computing; particle swarm; load balance

中圖分類號:TP312

文獻(xiàn)標(biāo)志碼:A

文章編號:2095-5456(2015)06-0507-05

作者簡介:趙宏偉(1976-),男,遼寧沈陽人,沈陽大學(xué)副教授.

基金項(xiàng)目:遼寧省自然科學(xué)基金資助項(xiàng)目(2013020011).

收稿日期:2015-03-27