李天朝，李蜀瑜

（陜西師范大學(xué) 計算機科學(xué)學(xué)院，陜西 西安 710062）

基于改進的蝙蝠算法在云計算資源調(diào)度中的研究

李天朝，李蜀瑜

（陜西師范大學(xué) 計算機科學(xué)學(xué)院，陜西 西安 710062）

本文對云計算中資源調(diào)度進行了深入的研究，針對云計算的資源調(diào)度模型，提出一種基于和聲算法和蝙蝠算法調(diào)度算法。在該求解方法中，通過改進蝙蝠的位置的平均響度，來減小的迭代次數(shù)。這一改進能夠提供易于調(diào)節(jié)的蝙蝠算法離散優(yōu)化問題，提高算法的收斂速度，縮短算法的運行時間。實現(xiàn)了蝙蝠算法對優(yōu)化問題的處理結(jié)果。通過仿真實驗表明，該算法是一種云計算環(huán)境下有效的任務(wù)調(diào)度算法。

元計算；蝙蝠算法；和聲算法；資源調(diào)度

云計算是一種商業(yè)模式和服務(wù)模式，是分布式計算、并行處理和網(wǎng)格計算等多種技術(shù)的拓展和延伸[1]。資源調(diào)度是云計算的核心問題，其效率直接影響整個云計算環(huán)境的工作性能，在云計算環(huán)境下，怎樣找到一個完善、高效的計算資源調(diào)度模型是至關(guān)重要的，它決定了云計算的性能，已經(jīng)成為當(dāng)前一個重要研究方向之一[2]。

文獻[3]中對云計算下的資源池模型做了介紹，分析了云計算調(diào)度資源流程和云計算環(huán)境下實體之間的關(guān)系。建立了一種云計算環(huán)境中資源調(diào)度算法，綜合考慮了云計算資源池中各種資源的綜合負(fù)載情況，采用人工加自動的虛擬機遷移技術(shù)實現(xiàn)云計算中物理服務(wù)器的負(fù)載均衡。文獻[4]使用了馬爾可夫鏈模型并提出一種控制算法，在特定的QoS約束條件下最大化每兩次虛擬機遷移的時間，從而決定哪些服務(wù)器是資源過載的。文獻[5]提出了一種基于克隆選擇算法的云集群資源調(diào)度方法。首先，定義了云環(huán)境下以最小化執(zhí)行時間跨度和負(fù)載均衡因子的集群資源調(diào)度模型，然后設(shè)計了抗體的編碼方式，抗體與抗原之間的親和度函數(shù)、抗體之間的親和度函數(shù)、克隆算子、退火交叉算子和高斯變異算子，并定義了基于克隆選擇算法的云計算集群資源調(diào)度方法。文獻[6]提出了CL-PSO算法，是以綜合置信度最優(yōu)解為目標(biāo)函數(shù)，文化粒子群算法 （CulturalParticleSwarm Optimization，CPSO）是文化算法（CA）和PSO算法相結(jié)合的組合算法，較好地克服了標(biāo)準(zhǔn)PSO算法存在的缺陷，為云計算資源調(diào)度提供了一種新的研究方法。文獻[7]針對現(xiàn)行資源調(diào)度算法存在算法效率低等弊端，提出一種新的云計算資源調(diào)度模型（IABC），基于利用改進人工蜂群算法的云計算資源調(diào)度模型，改進了傳統(tǒng)資源調(diào)度算法的缺陷，大幅度消減了任務(wù)的完成的時間，并且提高了云計算資源利用率。文獻[8]使用一種更先進、更精確的方法來預(yù)測虛擬機的CPU使用情況。建立了每個虛擬機的數(shù)據(jù)模型，利用了一種分布式?jīng)Q策支持系統(tǒng)（rDSS）作為云計算應(yīng)用來預(yù)測虛擬機的CPU使用率。

文中提出了一種改進的蝙蝠算法，通過改進蝙蝠的位置的平均響度，來減小的迭代次數(shù)。這一改進能夠提供易于調(diào)節(jié)的蝙蝠算法離散優(yōu)化問題，提高算法的收斂速度，減少了算法的執(zhí)行時間，實現(xiàn)了蝙蝠算法對優(yōu)化問題的處理結(jié)果。

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

云計算資源調(diào)度是云計算技術(shù)的一個重要組成基礎(chǔ)，它的目標(biāo)是研究用戶提交的任務(wù)分配計算節(jié)點、計算節(jié)點間進行動態(tài)擴展及在滿足用戶服務(wù)質(zhì)量要求并且執(zhí)行時間最短的前提下，虛擬機利用率最高，它的效能直接影響所有云計算環(huán)境的工作能效。在云計算資源調(diào)度中，就是盡可能的在短時間內(nèi)完成任務(wù)最多，目標(biāo)值調(diào)度時間最小，系統(tǒng)利用率最高。云計算資源調(diào)度模型如下：■

其中，xij表示任務(wù)i占用虛擬節(jié)點 j，1表示占用，0則表示未占用；tij表示任務(wù)i在虛擬節(jié)點j上使用的時間，cij表示任務(wù)i占用虛擬節(jié)點j上的費用，sij表示任務(wù)i占用虛擬節(jié)點j上的資源利用率，kij表示任務(wù)i占用虛擬節(jié)點j上的調(diào)度開銷。i表示虛擬節(jié)點的個數(shù)，j表示虛擬節(jié)點，T表示資源調(diào)度的目標(biāo)函數(shù)值，要求達(dá)到min S。

2 蝙蝠算法

蝙蝠算法 （Bat Algorithm，BA）[9-11]是劍橋大學(xué)Xin-She Yang教授在2010年提出的一種啟發(fā)式群智能優(yōu)化算法，它是利用蝙蝠回聲定位搜索捕食獵物模擬出的算法。蝙蝠算法是通過自然界中蝙蝠找尋食物的活動，通過使用回聲中的聲波定位去搜索它們的獵物，回聲中的聲波是由指定的脈沖速率和頻率獲得，通過迭代搜索得到最優(yōu)解，并且在生成的最優(yōu)解周圍進行局部搜索，直至找到最優(yōu)解。蝙蝠算法作為一種新穎的群智優(yōu)化算法，收斂速度快，參數(shù)少，模型簡單等優(yōu)點，已經(jīng)成功運用于多種問題中[12]。

起初必須確定N維的搜索空間，蝙蝠的響度是A，頻率范圍為[fmin，fmax]，脈沖頻率為r，對應(yīng)波長的范圍是[λmin，λmax]，指定第i只蝙蝠在t時刻的速度vti和位置lti的更新公式如下：

其中，fi表示蝙蝠頻率，β∈[0，1]它代表的隨機變量，服從均勻分布。x*表示通過每一次迭代得到的最佳位置。針對λf是一個增量，在本文中固定波長λ，而針對f進行調(diào)整，在進行部分搜索的期間，從現(xiàn)在的局部搜索中生成一個最優(yōu)解，每只蝙蝠將隨機生成一個新的位置。

在以上公式中，假設(shè)α和κ取值在[0，1]。隨著蝙蝠的速度和響度的不斷更新，象征著蝙蝠可以繼續(xù)飛向最優(yōu)解。

3 基于和聲搜索算法的蝙蝠算法的改進

對于基本蝙蝠算法種群中的每只蝙蝠在一個小范圍內(nèi)搜索能力比較強，但是整個群體缺乏有效的變異機制因為該算法采用種群向當(dāng)前最優(yōu)個體學(xué)習(xí)的機制，一旦被某個局部極值吸引，由于沒有有效的變異機制，使得整個種群都可能陷入局部最優(yōu)解。此外，蝙蝠算法也存在一些問題，例如后期收斂速度慢、難以擺脫局部最優(yōu)，種群迅速聚集到超個體，全局搜索能力較差等。

3.1 和聲搜索算法

和聲搜索（Harmony Search，HS）算法[13]是 2001年韓國學(xué)者Z.W.Geem等人提出的一種新的智能優(yōu)化算法，算法模擬了樂師們在音樂作曲中憑借自己的記憶，通過重復(fù)調(diào)整樂隊中各樂器的音調(diào)，最終能獲得一個優(yōu)美的和聲狀態(tài)的過程。HS算法將樂器聲調(diào)的和聲類比于優(yōu)化問題的解向量，評價即是各對應(yīng)的目標(biāo)函數(shù)值。算法引入兩個主要參數(shù)，即微調(diào)概率 （Pitch Adjusting Rate，PAR）和記憶庫取值概率（Harmony Memory Considering Rate，HMCR）[14]。

3.2 對蝙蝠算法的改進

蝙蝠算法有一個很好的搜索能力。但是，它需要通過大量的迭代才能產(chǎn)生產(chǎn)生這種令人滿意的結(jié)果。在這里，我們定義動態(tài)比例系數(shù)參數(shù)θ，它是限制步長的隨機漫步的本地搜索的一個因素，改進提出了這個算法。適當(dāng)?shù)恼{(diào)整，從計算時間來看該參數(shù)減小了的迭代次數(shù)。此外，這一改進能夠提供易于調(diào)節(jié)的蝙蝠算法離散優(yōu)化問題。動態(tài)比例因子θ參數(shù)可以定義為：

這個公式定義了和聲搜索算法中寬帶參數(shù)之間的關(guān)系。取代了用公式（4），進一步演化的公式可以表述如下：

在上述的公式中，iter指代當(dāng)前迭代過程。為了解決收斂實例，上述這種增強版的方程式還是會用上的。在連續(xù)優(yōu)化問題中，θmax和θmin應(yīng)該可以分別被取作1和0.001。同時在離散優(yōu)化問題中，θmax和θmin可以分別被取作10和0.01。但是，這些數(shù)值通常在優(yōu)化問題中的參數(shù)整定時才會被推薦使用；同時，在遇到一些參數(shù)和問題高度緊密聯(lián)系，但是這些問題又需要得到較好調(diào)整的情況下，這些數(shù)值也會被推薦使用。

3.3 蝙蝠個體的編碼方式

云計算資源調(diào)度即是對所有可能的調(diào)度序列進行搜索，最后找到一個最好調(diào)度的方案。在處理云計算資源調(diào)度運用蝙蝠算法算法時，需要對資源進行劃分和蝙蝠個體進行編碼。為了便于計算，提高蝙蝠算法的搜索效果，文中采用二進制方式編碼作為蝙蝠個體的蝙蝠方式，即蝙蝠個體對應(yīng)每個任務(wù)的資源，每一個編碼后的蝙蝠個體實際上都與每一個資源相對應(yīng)。

改進的蝙蝠算法在云計算資源調(diào)度的優(yōu)化步驟：

1）初始化蝙蝠種群的位置x（i），速度v（i），脈沖發(fā)射速率r（i），脈沖響度A（i）和脈沖頻率f（i）；

2）初始化當(dāng)前區(qū)域中的蝙蝠數(shù)量xi（i∈{1…n}）。

3）根據(jù)個體不同的適應(yīng)值采用不同的頻率生成策略；

4）利用公式（2）~（4）計算蝙蝠飛行速度和空位方位；

5）評估新解，若滿足條件則更新位置和速度，同時利用公式（9）、公式（6）更新脈沖響度A（i）和發(fā)射速率r（i）；

6）判斷算法終止條件，若滿足搜素精度w或者達(dá)到搜素次數(shù)，則退出，并輸出最終結(jié)果，否則返回2）。

7）輸出最優(yōu)極值和個體。

4 算法仿真

文中將云計算中的任務(wù)調(diào)度的個數(shù)模擬為蝙蝠的個數(shù)，將資源優(yōu)化調(diào)度看成是蝙蝠個體搜索的過程，將滿足資源調(diào)度公式（1）模擬為蝙蝠所處的位置的優(yōu)劣。文中算法采用CloudSim[15]平臺測試，CloudSim是由澳大利亞墨爾本大學(xué)和Gridbus共同推出的云計算仿真軟件平臺，實驗環(huán)境為Windows 7操作系統(tǒng)，硬件主要包括i7CPU和8G DRR3，設(shè)定參數(shù)虛擬任務(wù)為500個，虛擬節(jié)點為8個，設(shè)置迭代次數(shù)為500，并將本文算法與PSO、GA在云計算模型中進行對比。

圖1 3種資源負(fù)載算法任務(wù)完成時間比較

圖2 3種資源負(fù)載算法能量消耗時間比較

從圖1~3中可以看出，該算法在本文中的任務(wù)完成時間一開始差別不太明顯。然而，隨伴著任務(wù)數(shù)量的增加，所花費的時間比其他算法，在能量消耗方面明顯減少，伴隨著任務(wù)數(shù)量的不斷增多，差異明顯。在3種算法的資源開銷方面，文中算法的時間開銷優(yōu)于其他的兩種算法，并在一定程度上節(jié)省了資源分配的時間。

圖3 3種資源負(fù)載算法開銷時間比較

5 結(jié)束語

云計算環(huán)境資源分配是云計算效率的關(guān)鍵，文中是基于云計算環(huán)境下的資源分配研究，針對當(dāng)前云計算資源調(diào)度算法存在收斂速度慢，資源利用率不足等缺陷，利用蝙蝠算法控制參數(shù)少、易于實現(xiàn)、計算簡單等優(yōu)點，提出了一種基于和聲搜素算法的蝙蝠算法的云計算資源調(diào)度模型．仿真結(jié)果表明，相對于遺傳算法和粒子群算法，文中算法不僅找到了理想的云計算資調(diào)度方案，任務(wù)完成時間急劇減少，而且克服了當(dāng)前云計算資源調(diào)度算法存在的不足，提高了云計算資源利用率，在現(xiàn)代大規(guī)模云計算中有著廣泛的應(yīng)用前景。

[1]林偉偉，齊德昱.云計算資源調(diào)度研究綜述[J].計算機科學(xué)，2012（10）:1-6.

[2]薛玉.云計算環(huán)境下的資源調(diào)度優(yōu)化模型研究[J].計算機仿真，2013（5）:362-365.

[3]劉賽，李緒蓉，萬麟瑞，等.云環(huán)境下資源調(diào)度模型研究[J].計算機工程與科學(xué)，2013（3）:48-51.

[4]Beloglazov A，Buyya R.Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers underquality ofservice constraints[J].IEEE Transactions on Parallel& Distributed Systems，2013，24（7）:1366-1379.

[5]朱利華，李春華，吳寬仁.基于改進克隆選擇算法的云計算集群資源調(diào)度[J].科學(xué)技術(shù)與工程，2013（13）:3642-3646.

[6]羅丹.云計算資源調(diào)度算法仿真[J].計算機仿真，2013（7）:280-283.

[7]孟令璽，李洪亮.基于CA-PSO算法的云計算資源調(diào)度策略[J].計算機仿真，2013（10）:406-410.

[8]Li-Hua G，Liying S，Sotaro C.Provisioning of requests for virtual machine sets with placement constraints in IaaS clouds[C].Integrated Network Management（IM 2013），2013 IFIP/IEEE International Symposium on.IEEE，2013:499-505.

[9]Yang X S.A new metaheuristic bat-Inspired algorithm[J].Science，2010（284）:65-74.

[10]Mirjalili S，Mirjalili S M，Yang X S.Binary bat algorithm[J].Neural Computing&Applications，2014，25（3-4）:663-681.

[11]Gandomi A H，Yang X S，Alavi A H，et al.Bat algorithm for constrained optimization tasks[J]. Neural Computing&Applications，2013，22（6）: 1239-1255.

[12]屈遲文，傅彥銘，侯勇順.融合入侵雜草算子的蝙蝠算法[J].計算機應(yīng)用與軟件，2015（4）:243-246.

[13]Zong W G，Kim J H，Loganathan G V.A new heuristic optimization algorithm:harmony search. [J].Simulation Transactions of the Society for Modeling&Simulation International，2001，76（2）:60-68.

[14]雍龍泉.一種全局和聲搜索算法求解絕對值方程[J].計算機應(yīng)用研究，2013，30（11）:3276-3279.

[15]Calheiros R N，Ranjan R，De Rose C A F，et al. Cloudsim:A novel framework for modeling and simulation of cloud computing infrastructures and services[R].Technical report，Grids-TR-2009-1，Grid computing and distributed system laboratory，The University of Melbourne，Australia，2009.

Resource scheduling in cloud computing based on improved bat algorithm

LI Tian-chao，LI Shu-yu
（College of Computer Science，Shaanxi Normal University，Xi’an 710062，China）

In this paper，after in-depth research cloud computing task scheduling strategy in cloud computing environments，for cloud computing resource scheduling model，we propose a scheduling algorithm harmony algorithms and bat algorithm.In the solving process，by improving the average loudness bat position，to reduce the number of iterations.This improvement can be easily adjusted to provide discrete optimization problems bat algorithm to improve the convergence speed，shorten the running time of the algorithm.Realized bat algorithm optimization problem processing results.Simulation results show that the algorithm is effective scheduling algorithm in a cloud computing environment.

cloud computing；resource scheduling；bat algorithm；harmony algorithms

TN99

：A

：1674－6236（2017）01-0043-04

2016-01-14稿件編號：201601097

李天朝（1982—），男，陜西大荔人，碩士研究生。研究方向：云計算。