賀智明　張揚(yáng)　高林

摘要：針對(duì)云計(jì)算環(huán)境下的資源調(diào)度優(yōu)化問題，提出了一種基于量子粒子群策略的混洗蛙跳改進(jìn)算法（簡(jiǎn)稱QPSFLA算法），旨在引入量子粒子群搜索策略防止傳統(tǒng)混洗蛙跳算法容易陷入局部最優(yōu)的問題。在CloudSim平臺(tái)上的模擬試驗(yàn)結(jié)果表明，QPSFLA算法能夠達(dá)到預(yù)期效果，而且比平臺(tái)自帶算法和傳統(tǒng)混洗蛙跳算法效率更高。

關(guān)鍵詞：云計(jì)算；量子粒子群；混洗蛙跳；資源調(diào)度

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）02-0311-04

云計(jì)算是在分布式計(jì)算（Distributed Computing）、并行計(jì)算（Parallel Computing）和網(wǎng)格計(jì)算（Grid Computing）的基礎(chǔ)之上，通過整合虛擬化和效用計(jì)算等理論后形成的一種新的計(jì)算模式[1]。通過網(wǎng)絡(luò)，云計(jì)算將復(fù)雜的大規(guī)模處理任務(wù)拆分為若干個(gè)小任務(wù)，然后分配給網(wǎng)絡(luò)中多個(gè)任務(wù)中心進(jìn)行處理，完成后再將各任務(wù)中心的處理結(jié)果反饋給用戶。提供這些服務(wù)的網(wǎng)絡(luò)和任務(wù)中心即是所謂的云。云計(jì)算提供了一種新的模式，這種模式把本地的服務(wù)轉(zhuǎn)移到網(wǎng)絡(luò)上以減少軟硬件的管理成本[2-3]。云計(jì)算資源調(diào)度通過一定的策略將用戶請(qǐng)求合理的分配到各個(gè)計(jì)算資源上，使用戶請(qǐng)求得到滿意的計(jì)算服務(wù)。

1 云計(jì)算資源調(diào)度及調(diào)度模型

云資源調(diào)度包括用戶請(qǐng)求、計(jì)算資源及分配策略幾個(gè)部分。假設(shè)任務(wù)數(shù)為M，資源數(shù)為N，用T表示用戶請(qǐng)求，T={T1 ，T2，…，Tm}，計(jì)算資源P={P1，P2，…，Pn}。云計(jì)算資源調(diào)度模型可描述為將M個(gè)用戶請(qǐng)求按照一定的策略調(diào)度分配給N個(gè)計(jì)算資源執(zhí)行，以獲取最優(yōu)的資源分配。如圖1所示。

由圖1可知，云資源調(diào)度包含兩層。第一層調(diào)度從用戶層到虛擬機(jī)層，第二層從虛擬機(jī)層到服務(wù)層。在這二次調(diào)度模型中，第一層創(chuàng)建一個(gè)虛擬機(jī)，其中包括計(jì)算資源、網(wǎng)絡(luò)資源和存儲(chǔ)資源，并且根據(jù)一定的規(guī)則描述虛擬機(jī)的每個(gè)任務(wù)。通過兩層結(jié)構(gòu)，任務(wù)可以獲取所需的資源，但高等級(jí)請(qǐng)求可能會(huì)占用服務(wù)器多余的資源，從而增加低等級(jí)任務(wù)的等待時(shí)間而造成資源浪費(fèi)。

2 QPSO算法

3 SFLA算法

混洗蛙跳算法是一種啟發(fā)式的群體進(jìn)化算法，該算法最先由Eusuff和Lansey于2003年提出。SFLA算法是一種新型的仿生物學(xué)智能優(yōu)化算法，SFLA 集成了模因演算法（MA，memeticalgorithm）和粒子群算法（PSO，particle swarm optimization）的優(yōu)點(diǎn)。SFLA算法概念簡(jiǎn)單、參數(shù)少、計(jì)算效率高，全局搜索能力強(qiáng)，易于實(shí)現(xiàn)?；旌贤芴惴ㄖ饕獞?yīng)用于解決多目標(biāo)優(yōu)化問題。

3.1 算法原理

混合蛙跳算法（Shuffled Frog Leaping Algorithm， SFLA）模擬了不同青蛙族群在尋找食物時(shí)進(jìn)行信息交流的過程[5]?；旌贤芴惴ㄏ葘⑶嗤軅€(gè)體按照一定的方法分成若干個(gè)子群，將全局搜索策略與局部搜索策略相結(jié)合，每只青蛙在子群中交換思想，而算法中的混合策略使各子群間的思想得到交換。其中，子群是由相同特征的青蛙組成，不同的子群是由具有不同的思想的青蛙組成。子群中青蛙按照一定的方法進(jìn)行局部尋優(yōu)。在局部尋優(yōu)達(dá)到給定條件后再執(zhí)行混合策略，直到達(dá)到最優(yōu)解。全局混合策略與局部尋優(yōu)策略可以使蛙跳算法跳出局部最優(yōu)解，這是混合跳算法的主要優(yōu)點(diǎn)。

3.2 算法基本流程

1）初始化各參數(shù)，隨機(jī)產(chǎn)生青蛙種群粒子（即SFLA種群粒子）；

2）用適應(yīng)度函數(shù)對(duì)粒子個(gè)體進(jìn)行降序排列選擇；

3）將降序排列的粒子分配到每個(gè)族群中；

4）利用預(yù)設(shè)的迭代次數(shù)進(jìn)行局部尋優(yōu)；

5）將各青蛙族群進(jìn)行混洗。在每個(gè)族群都進(jìn)行過一輪進(jìn)化后，將各個(gè)族群中的蛙重新進(jìn)行排序和族群劃分并記錄全局最優(yōu)解；

6）判斷迭代是否結(jié)束，如果滿足收斂條件，算法迭代停止并且輸出粒子，否則轉(zhuǎn)到第二步繼續(xù)執(zhí)行。

4 改進(jìn)SFLA算法

本文提出改進(jìn)的SFLA算法在局部搜索時(shí)使用QPSO搜索策略的QPSO - SFLA算法（QPSFLA），算法局部搜索使用QPSO搜索策略，得到局部最優(yōu)解后使用SFLA算法可以得到精確結(jié)果。算法流程如下：

1） 參數(shù)：群體大小，群體大小，迭代的最大數(shù)量的局部搜索，迭代和等的整體數(shù)量。

2） 生成初始種群粒子。

3） 確定適應(yīng)度函數(shù)F（x）用來評(píng)估青蛙粒子的優(yōu)點(diǎn)。

4） 青蛙在按降序排列，并確定Qbest（全局最優(yōu)解） ，如果滿足收斂條件，則停止執(zhí)行；否則，下一個(gè)步驟。

5）青蛙種群劃分：將青蛙粒子分配到M個(gè)種群中，第一只進(jìn)入第一個(gè)種群，第二只進(jìn)入第二個(gè)種群，以此類推，第m個(gè)進(jìn)入第m種群，m+1進(jìn)入第一種群，m+2進(jìn)入第二個(gè)，直至所有的青蛙粒子劃分完畢。

5 仿真實(shí)驗(yàn)

本文使用澳大利亞墨爾本大學(xué)推出的cloudsim3.3平臺(tái)[6-7]進(jìn)行云計(jì)算資源調(diào)度仿真實(shí)驗(yàn)，通過擴(kuò)展DataCenterBroker類來模擬改進(jìn)的資源調(diào)度算法。

實(shí)驗(yàn)分別選擇CloudSim自帶的輪循算法、混洗蛙跳算法及量子粒子群混洗蛙跳算法模擬資源調(diào)度。實(shí)驗(yàn)所需的數(shù)據(jù)如表1所示。模擬的任務(wù)數(shù)量分別為5、60、140、290，任務(wù)長(zhǎng)度為10000至20000，仿真實(shí)驗(yàn)次數(shù)為300次，取平均值作為實(shí)驗(yàn)結(jié)果。

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

本文針對(duì)云計(jì)算資源調(diào)度的特點(diǎn)，分析了混洗蛙跳算法在云計(jì)算資源調(diào)度中應(yīng)用的不足，提出一種改進(jìn)的混洗蛙跳算法，對(duì)局部搜索進(jìn)行改進(jìn)。并將此算法應(yīng)用在資源調(diào)度策略上，實(shí)驗(yàn)證明該算法不但避免了原有算法易陷入局部最優(yōu)，而且提高了資源調(diào)度的整體性能。

參考文獻(xiàn)：

[1] AnIlbmst M，F(xiàn)ox A，Gmth R，et a1.A view of cloud computing[J].Communications of the ACM，2009，53（4）：50-58.

[2] Brian Hayes.Cloud computing[J].Communications of the ACM，2008（7）：9-11.

[3] 李建鋒，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，30（1）：184-186.

[4] 李愛國(guó).多粒子群協(xié)同優(yōu)化算法[J].復(fù)旦學(xué)報(bào)：自然科學(xué)版，2004，43（5）：923-925.

[5] Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Joumal of Water Sources Planning and Management，2003，129（3）：210-225.

[6] The Could Lab.Cloudsim[EB/OL].[2011-08-15].http：//www.cloudbus.org/cloudsim.

[7] Buyya R，Ranjan R，Calheiros R N.Modeling and simulation of scalable cloud computing environments and the CloudSim Toolkit：chanllenges and opportunities[C]//proceedings of the 7th High Performance Computing and Simulation Conference.New York，USA：IEEE Press，2009：21-24.