基于改進(jìn)布谷鳥搜索算法的云計(jì)算任務(wù)調(diào)度

劉竹松， 陳　潔， 田　龍

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

?

基于改進(jìn)布谷鳥搜索算法的云計(jì)算任務(wù)調(diào)度

劉竹松， 陳潔， 田龍

(廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006)

摘要:針對(duì)云計(jì)算系統(tǒng)中能否高效地調(diào)度子任務(wù)的問題，本文提出了一種基于改進(jìn)布谷鳥搜索算法的任務(wù)調(diào)度算法.利用柯西分布對(duì)陷入局部極值的鳥巢進(jìn)行擾動(dòng)，有利于提高布谷鳥搜索算法全局搜索的質(zhì)量.算法運(yùn)用整數(shù)編碼方式，利用改進(jìn)后的算法求得最優(yōu)解.使用云仿真平臺(tái)進(jìn)行驗(yàn)證，結(jié)果證實(shí)了所提出算法的有效性.

關(guān)鍵詞:云計(jì)算； 任務(wù)調(diào)度； 布谷鳥搜索算法； 柯西分布

隨著信息時(shí)代的快速發(fā)展，在分布式計(jì)算、并行計(jì)算和網(wǎng)格計(jì)算逐步發(fā)展成熟的基礎(chǔ)上，云計(jì)算應(yīng)運(yùn)而生.作為一種新興的商業(yè)計(jì)算模型，云計(jì)算(Cloud Computing)[1]已經(jīng)成為了工業(yè)界和學(xué)術(shù)界研究的熱點(diǎn).云計(jì)算是并行計(jì)算(Parallel Computing)[2]、網(wǎng)格計(jì)算(Grid Computing)和分布式計(jì)算(Distributed Computing)的發(fā)展，是虛擬化、效用計(jì)算、負(fù)載平衡等多種技術(shù)融合提升的結(jié)果.其核心思想是將大量計(jì)算資源、儲(chǔ)存資源和服務(wù)資源等通過網(wǎng)絡(luò)連接起來形成資源池，根據(jù)用戶的需求對(duì)資源進(jìn)行統(tǒng)一調(diào)度和管理.在云計(jì)算系統(tǒng)中，可按需進(jìn)行動(dòng)態(tài)地部署、配置、重新配置和取消服務(wù)[3].然而，由于不斷增長(zhǎng)的用戶量和云計(jì)算網(wǎng)絡(luò)中節(jié)點(diǎn)的異構(gòu)性和復(fù)雜性，如何及時(shí)、高效地進(jìn)行任務(wù)調(diào)度，合理地利用資源，提高資源利用率和任務(wù)執(zhí)行的效率，成為云計(jì)算研究的核心問題之一[4].因此在云計(jì)算領(lǐng)域中，任務(wù)調(diào)度問題屬于一個(gè)熱門的課題.

1云計(jì)算任務(wù)調(diào)度

在云計(jì)算系統(tǒng)中，任務(wù)調(diào)度的實(shí)質(zhì)是將n個(gè)相互獨(dú)立的任務(wù)合理分配到m個(gè)異構(gòu)的可用資源上，以達(dá)到任務(wù)調(diào)度目標(biāo)[5].

云計(jì)算中資源通過虛擬化的方式提供給用戶，通常云計(jì)算中任一資源VM可以被描述為

VM={vmid,mips,size,ram,bw,pesNumber}.

其中，vmid表示資源id號(hào)，mips表示CPU運(yùn)行指令數(shù)，size表示資源大小，ram表示內(nèi)存，bw表示帶寬，pesNumber代表?yè)碛械腃PU個(gè)數(shù).

用戶提交的任一任務(wù)Clet可以被描述為

Clet={id,length,fileSize,outputSize}.

其中，id表示任務(wù)id，length代表任務(wù)長(zhǎng)度，fileSize、outputSize分別代表任務(wù)Clet的輸入、輸出文件大小.

云計(jì)算的任務(wù)調(diào)度的目標(biāo)[6]是對(duì)用戶提交的任務(wù)實(shí)現(xiàn)最優(yōu)調(diào)度，具體包括實(shí)現(xiàn)最優(yōu)時(shí)間跨度 (Optimal Makespan)，保障服務(wù)質(zhì)量(Quality of Service，QoS)，保證負(fù)載均衡(Load Balancing)以及節(jié)省經(jīng)濟(jì)成本(Economic Principles).時(shí)間跨度是從云計(jì)算系統(tǒng)中第一個(gè)任務(wù)開始，直到最后一個(gè)任務(wù)執(zhí)行完成過程中所消耗的時(shí)間，時(shí)間跨度越短證明調(diào)度策略越好.跨度是調(diào)度中重要且常見的目標(biāo)，因此，實(shí)現(xiàn)最優(yōu)跨度是用戶和云計(jì)算提供商的共同目標(biāo).負(fù)載均衡是云計(jì)算系統(tǒng)中的資源分配負(fù)載平衡，達(dá)到最優(yōu)化資源使用、最大化吞吐量和最小化響應(yīng)時(shí)間，避免過載.

近年來，許多啟發(fā)式智能算法引起了眾多學(xué)者的關(guān)注和興趣，如蟻群算法、模擬退火算法、粒子群優(yōu)化算法、遺傳算法等.這些算法以各自的優(yōu)點(diǎn)對(duì)NP hard問題和組合優(yōu)化問題進(jìn)行求解.文獻(xiàn)[7]提出基于改進(jìn)蟻群算法的任務(wù)調(diào)度算法，有效縮短云計(jì)算環(huán)境下的任務(wù)平均運(yùn)行時(shí)間.文獻(xiàn)[8]提出基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法，調(diào)度總?cè)蝿?wù)完成時(shí)間和任務(wù)平均完成時(shí)間較短.文獻(xiàn)[9]提出基于混合蛙跳算法的調(diào)度算法，算法保證QoS的資源調(diào)度.文獻(xiàn)[10]提出一種融合蟻群算法和模擬退火算法的混合調(diào)度算法.該算法以最小化調(diào)度時(shí)間為目標(biāo).相對(duì)而言，布谷鳥搜索算法是一種比較新穎的群體智能啟發(fā)式優(yōu)化算法.國(guó)內(nèi)外一些學(xué)者在此方面做了一些研究，但鮮有將此算法應(yīng)用于求解云計(jì)算調(diào)度上.

本文提出了云計(jì)算系統(tǒng)中基于改進(jìn)的布谷鳥搜索算法的調(diào)度方案，并通過仿真實(shí)驗(yàn)，驗(yàn)證了云計(jì)算系統(tǒng)下該算法具有良好的任務(wù)調(diào)度性能.

本文重點(diǎn)關(guān)注以性能為中心的最優(yōu)跨度和負(fù)載均衡兩個(gè)目標(biāo)，并定義為

(1)

?Load(X)=λD(X)VM+(1-λ)D(X)Clet，

(2)

2基本布谷鳥算法思想

布谷鳥搜索(Cuckoo Search，簡(jiǎn)稱CS)算法是一種新興的仿生智能算法，由Xinshe Yang和S.Deb在2009年提出[11]，其思想源于對(duì)布谷鳥寄生育雛行為以及鳥類或果蠅Lévy flights行為的模擬.算法由兩個(gè)主要構(gòu)件：Lévy flights隨機(jī)游動(dòng)和偏好隨機(jī)游動(dòng)，共同構(gòu)成平衡算法的局部搜索和全局搜索的步驟.

布谷鳥搜索算法建立在3個(gè)理想條件上：

(1) 每只布谷鳥一次只產(chǎn)一個(gè)蛋，并且把蛋放在隨機(jī)選擇的鳥巢里；

(2) 孵化高質(zhì)量蛋的鳥巢將會(huì)傳給下一代；

(3) 可用的寄主的鳥巢數(shù)量是固定的，布谷鳥的蛋被寄主發(fā)現(xiàn)的概率是Pa∈[0,1].被發(fā)現(xiàn)后，寄主可以把蛋扔了或者遺棄原來的鳥巢并新建一個(gè).

在布谷鳥搜索算法中，基于萊維飛行，布谷鳥選擇寄主鳥巢的位置更新式為

(3)

算法的群體由k個(gè)隨機(jī)生成的布谷鳥巢組成，即群體：P={X1,X2,…Xk}；每個(gè)布谷鳥巢包含n個(gè)鳥蛋，一個(gè)鳥巢代表一個(gè)候選解X={x1,x1,…,xn}.

3基于ACCS算法的云計(jì)算任務(wù)調(diào)度

3.1改進(jìn)的布谷鳥搜索算法

在云任務(wù)調(diào)度過程中，最優(yōu)調(diào)度方案的求解過程是一個(gè)離散型組合優(yōu)化問題，基本布谷鳥算法在進(jìn)化后期容易造成早熟，易陷入局部最優(yōu)解，無法搜索出全局最優(yōu)解[12].由于基本布谷鳥的缺點(diǎn)以及云任務(wù)調(diào)度的特點(diǎn)，本文對(duì)基本布谷鳥算法進(jìn)行如下改進(jìn)，提出基于自適應(yīng)柯西變異的布谷鳥搜索算法(Adaptive Cauchy Cuckoo Search，簡(jiǎn)稱ACCS).

ACCS的基本思想是當(dāng)布谷鳥搜索的單個(gè)鳥巢陷入局部極值時(shí)，利用柯西分布的全局變異和離散分布特點(diǎn)[13]，對(duì)單個(gè)鳥巢進(jìn)行柯西變異以增加鳥巢的多樣性，有利于跳出局部極值進(jìn)行全局搜索，同時(shí)提高搜索速度和質(zhì)量.

當(dāng)同一鳥巢在連續(xù)n代中，鳥巢的適應(yīng)度平均差值仍然保持在變異范圍之內(nèi)，則說明此鳥巢已陷入局部最優(yōu)狀態(tài)，無法自主進(jìn)步，需要進(jìn)行外部干預(yù).由于柯西變異在全局搜索時(shí)有較優(yōu)的表現(xiàn)，因此本文引入柯西擾動(dòng)算子，對(duì)陷入局部最優(yōu)狀態(tài)的鳥巢進(jìn)行外部干預(yù)，進(jìn)行擾動(dòng)變異.

1) 柯西分布

柯西分布是一種常見的分布函數(shù)，一維柯西分布隨機(jī)變量C(0,σ)的密度函數(shù)定義為

(4)

其中σ為尺度參數(shù).當(dāng)σ=1時(shí)，稱為標(biāo)準(zhǔn)柯西分布.

圖1　高斯隨機(jī)數(shù)和柯西隨機(jī)數(shù)的分布密度

Fig.1Distribution density of GaussianN(0, 1) random numbers and CauchyC(0, 1) random numbers

由圖1可見，柯西分布在原點(diǎn)的峰值比高斯分布小，而兩端無限趨近于x軸的速度比高斯分布慢.說明柯西分布更易產(chǎn)生遠(yuǎn)離遠(yuǎn)點(diǎn)的隨機(jī)數(shù)，柯西變異的擾動(dòng)能力比高斯變異強(qiáng)，能有效防止算法陷入局部最優(yōu).

2) 擾動(dòng)時(shí)機(jī)

(5)

其中，Tpre表示向前比較的代數(shù)；Tcur表示當(dāng)前代數(shù)；Fi表示第i代當(dāng)前鳥巢的適應(yīng)度值；其中Tpre

3) 擾動(dòng)方法

(6)

改進(jìn)后的布谷鳥算法流程如圖2所示.

圖2　改進(jìn)后的布谷鳥搜索算法流程

算法流程如下：

(1) 初始化算法基本參數(shù)；

(2) 計(jì)算各鳥巢適應(yīng)度并進(jìn)行評(píng)估，更新最優(yōu)鳥巢記錄X*；

(3) 變異判斷：根據(jù)公式評(píng)估是否需進(jìn)行柯西變異,若需要，則根據(jù)式(5)～(6)進(jìn)行柯西變異，產(chǎn)生新的鳥巢，并評(píng)估鳥巢適應(yīng)度，更新最優(yōu)鳥巢記錄；

(4) 萊維飛行：根據(jù)式(3)更新鳥巢的位置，并評(píng)估新的鳥巢適應(yīng)度值，對(duì)比先前最優(yōu)后更新最優(yōu)鳥巢記錄；

(5) 產(chǎn)生隨機(jī)數(shù)R，若R>Pa，則隨機(jī)改變鳥巢位置，得到一組新的鳥巢位置；

(6) 檢驗(yàn)算法是否滿足停止條件，滿足則輸出最優(yōu)值和對(duì)應(yīng)的最優(yōu)解，否則轉(zhuǎn)(2)繼續(xù)下一代搜索.

3.2ACCS的云計(jì)算資源調(diào)度設(shè)計(jì)

3.2.1基于整數(shù)編碼的調(diào)度方案

資源調(diào)度方案屬于組合優(yōu)化問題，應(yīng)用布谷鳥算法求解調(diào)度問題首先需要構(gòu)造合理的編碼方式來表示調(diào)度問題的解.在云任務(wù)調(diào)度中，設(shè)有n個(gè)任務(wù)需要在有m個(gè)虛擬機(jī)上執(zhí)行，則代表解為n維的一元數(shù)組，每個(gè)任務(wù)對(duì)應(yīng)的虛擬機(jī)號(hào)即為當(dāng)前維的值.在對(duì)虛擬機(jī)號(hào)進(jìn)行編碼時(shí)，采用從1至m遞增的整數(shù)編碼.由于CS與ACCS算法迭代過程中使用的為實(shí)數(shù)編碼方式，所以本文采用編碼時(shí)使用式(7)，解碼時(shí)使用式(8)的編解碼算法調(diào)度：

X=[x1,x2,…,xn]，

xi∈[1,m+1)，且xi為實(shí)數(shù)，

(7)

X′=[|x1|,|x2|,…,|xm|].

(8)

xi為實(shí)數(shù)，且xi∈[1,m+1)，|xi|表示對(duì)xi向下取整，解碼后每一維上的數(shù)值代表對(duì)應(yīng)任務(wù)所分配的執(zhí)行資源序列號(hào)即虛擬機(jī)編號(hào).

3.2.2適應(yīng)度函數(shù)設(shè)計(jì)

為實(shí)現(xiàn)調(diào)度方案具有最優(yōu)跨度和較優(yōu)的負(fù)載均衡.在本文中，綜合考慮調(diào)度方案的最優(yōu)時(shí)間跨度時(shí)間和負(fù)載均衡，由式(1)和(2)可得出用來進(jìn)行任務(wù)調(diào)度方案評(píng)價(jià)的目標(biāo)函數(shù)式(9).其中ω∈(0,1]為權(quán)值因子；F(X)越小，調(diào)度方案X越優(yōu)：

F(X)=ω×Time(X)+(1-ω)×Load(X).

(9)

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

為驗(yàn)證算法的有效性，本文采用了CloudSim云計(jì)算仿真器[14-15]，它可對(duì)云系統(tǒng)上的不同調(diào)度和分配策略性能進(jìn)行量化比較.為對(duì)比改進(jìn)的ACCS算法與CS算法、經(jīng)典遺傳算法(GA)[16]和經(jīng)典粒子群算法(PSO)[17-18]，本文同時(shí)在CloudSim上仿真模擬了GA和PSO的任務(wù)調(diào)度情況.

4.1仿真環(huán)境與實(shí)驗(yàn)參數(shù)設(shè)置

本文擴(kuò)展了云計(jì)算仿真平臺(tái)CloudSim 2.1，重寫了DataCenterBroker、Cloudlet等類，對(duì)算法進(jìn)行了模擬仿真.在相同的初始條件下，對(duì)基于GA算法、PSO算法、CS算法和改進(jìn)的ACCS調(diào)度算法進(jìn)行了基于CloudSim 2.1平臺(tái)的資源調(diào)度的實(shí)驗(yàn)仿真.

為保持公平性，各算法基本參數(shù)均使用默認(rèn)值.相關(guān)參數(shù)設(shè)置如表1、表2.

表1　各算法的基本參數(shù)

表2CloudSim虛擬機(jī)(VM)配置及其他運(yùn)行參數(shù)

Tab.2CloudSim virtual machine (VM) configuration and other operating parameters

VM參數(shù)值其他參數(shù)值總數(shù)50算法的總運(yùn)行次數(shù)(S)10MIPS500～2000算法的總迭代次數(shù)(MaxIter)500內(nèi)存256～2048比例因子:λ0.5帶寬500～1000比例因子:ω0.75

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

為表現(xiàn)算法的優(yōu)越性，本文分別進(jìn)行了多種任務(wù)、資源模式下的算法尋優(yōu)，同時(shí)從迭代次數(shù)和尋優(yōu)時(shí)間兩個(gè)方面進(jìn)行模擬實(shí)驗(yàn).

表3中體現(xiàn)了任務(wù)量逐漸增大過程中4種算法的運(yùn)行情況.可以明顯地看出，在經(jīng)過10次500代運(yùn)行過程中，4種算法在求解出的平均最優(yōu)適應(yīng)度值上相差不大，但ACCS算法明顯優(yōu)于其他3種算法.

表350個(gè)虛擬機(jī)時(shí)各任務(wù)量(個(gè))下各算法獨(dú)立運(yùn)行10次后的平均最優(yōu)適應(yīng)度值(F)和算法尋優(yōu)平均運(yùn)行時(shí)間(T)數(shù)據(jù)

Tab.350 virtual machine quotas for the data of： the average optimal fitness after 10 times of independent operation of algorithms (F) and the average running time algorithm for optimization (T)

任務(wù)量評(píng)價(jià)算法GAPSOCSACCS100F45.781948.849144.079943.0578T61.779714.01095.586319.34238200F80.103679.807277.857976.9321T122.30623.44837.0962111.8429300F116.338124.956116.473114.281T182.67132.61748.7115514.4412400F158.525169.639159.068154.538T240.84142.676410.157616.7352500F219.634227.444205.148204.872T304.53852.962411.854319.3373600F259.565234.448259.242256.349T366.34760.854413.494121.7931700F328.747322.772310.469309.132T430.82970.352214.898124.0812800F386.646402.795384.384379.116T497.97880.545116.576926.7378900F485.871469.542462.518448.563T567.92490.500129.490218.37661000F533.627562.591546.407530.597T633.95899.330119.914931.9478

在運(yùn)行時(shí)間上，GA算法由于其復(fù)雜的操作，運(yùn)行時(shí)間最長(zhǎng)，是CS運(yùn)行時(shí)間的近20倍，ACCS的近14倍，而且隨任務(wù)量的增長(zhǎng)，倍數(shù)呈增長(zhǎng)趨勢(shì).同時(shí)，PSO的運(yùn)行時(shí)間是CS的4～5倍，是ACCS的3～4倍.CS 算法不論是在運(yùn)行時(shí)間上還是尋優(yōu)結(jié)果上都明顯優(yōu)于GA和PSO算法.而改進(jìn)后的ACCS算法由于加入了擾動(dòng)因子的緣故，算法的運(yùn)行時(shí)間相比CS稍有增多，但尋優(yōu)結(jié)果更優(yōu).即ACCS能夠在相對(duì)GA和PSO更短的時(shí)間內(nèi)獲取到比包括CS在內(nèi)的更優(yōu)的解.

5結(jié)論

本文提出基于全局搜索柯西變異的布谷鳥搜索算法ACCS，并將其運(yùn)用于云計(jì)算任務(wù)調(diào)度.基于最優(yōu)時(shí)間跨度和負(fù)載均衡兩個(gè)目標(biāo)，采用整數(shù)編碼方式應(yīng)用ACCS算法進(jìn)行求解.在CloudSim云計(jì)算仿真平臺(tái)對(duì)所提算法進(jìn)行仿真，同時(shí)模擬了GA、PSO算法的云計(jì)算任務(wù)調(diào)度，實(shí)驗(yàn)結(jié)果表明該算法能夠在更短的時(shí)間內(nèi)尋取到更優(yōu)的調(diào)度方案，調(diào)度方案的最優(yōu)時(shí)間跨度和負(fù)載均衡方面均表現(xiàn)良好.

參考文獻(xiàn)：

[1] JADEJA Y，MODI K.Cloud computing-concepts，architecture and challenges[C]∥IEEE.Computing，Electronics and Electrical Technologies(ICCEET).[S.l.：s.n.]，2012：877-880.

[2] 劉東，常靜，魏文紅.基于MPI的并行蟻群算法的研究與實(shí)現(xiàn)[J].廣東工業(yè)大學(xué)學(xué)報(bào)，2008，1(25)：38-42.

LIU D，CHANG J，WEI W H.MPI-based parallel Ant Colony algorithm and its implementation[J].Journal of Guangdong University of Technology，2008，1(25)：38-42.

[3] 陳康，鄭緯民.云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J].軟件學(xué)報(bào)，2009，1(20)：1337-1348.

CHEN K，ZHENG W M.Cloud computing：system instances and current research[J].Journal of Software，2009，1(20)：1337-1348.

[4] 張建勛，古志民，鄭超.云計(jì)算研究進(jìn)展綜述[J].計(jì)算機(jī)應(yīng)用研究，2010，2(27)：429-433.

ZHANG J X，GU Z M，ZHENG C.Survey of research progress on cloud computing[J].Application Research of Computers，2010，2(27)：429-433.

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

LIN W W，QI D Y.Survey of resource scheduling in cloud computing[J].Computer Science，2012，10(39)：1-6.

[6] 左利云，曹志波. 云計(jì)算中調(diào)度問題研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2012，29(11)：4023-4027.

ZUO L Y，CAO Z B.Review of scheduling research in cloud computing[J].Application Research of Computers，2012，29(11)：4023-4027.

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

WANG Y G，HAN R L.Study on cloud computing task schedule strategy based on maco algorithm[J].Computer Measurement & Control， 2011，19(5)：1203-1204.

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

LI J F，PENG J.Task scheduling algorithm based on improved genetic algorithm in cloud computing environment[J].Journal of Computer Applications，2011，31(01)：184-186.

[9] 駱劍平，李霞，陳泯融.云計(jì)算環(huán)境中基于混合蛙跳算法的資源調(diào)度[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(29)：67-72.

LUO J P， LI X， CHEN M R.Guaranteed QoS resource scheduling scheme based on improved shuffled frog leaping algorithm in cloud environment[J].Computer Engineering and Applications， 2012， 48 (29)：67-72.

[10] 張浩榮，陳平華，熊建斌.基于蟻群模擬退火算法的云環(huán)境任務(wù)調(diào)度[J].廣東工業(yè)大學(xué)學(xué)報(bào)，2014，31(3)：77-82.

ZHANG H R，CHEN P H，XIONG J B.Task scheduling algorithm based on simulated annealing ant colony algorithm in cloud computing environment[J].Journal of Guangdong University of Technology，2014，31(3)：77-82.

[11] YANG X S，DEB S.Cuckoo search via Lévy flights[C].USA：IEEE Publications,2009：210-214.

[12] 王李進(jìn)，尹義龍，鐘一文.逐維改進(jìn)的布谷鳥搜索算法[J].軟件學(xué)報(bào)，2013，24(11)：2687-2698.

WANG L J，YIN Y L，ZHONG Y W.Cuckoo search algorithm with dimension by dimension improvement[J].Journal of Software，2013，24(11)：2687-2698.

[13] 文詩(shī)華，鄭金華，李密青.多目標(biāo)進(jìn)化算法中變異算子的比較與研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(2)：74-78.

WEN S H，ZHENG J H，LI M Q.Comparison and research of mutation operators in multi-objective evolutionary algorithms[J].Computer Engineering and Applications，2009，45(2)：74-78.

[14] 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[J].Software Practice & Experience, 2011, 41(1)：23-50.

[15] CALHEIROS R N， RANJAN R， BELOGLAZOV A， et al. CloudSim： a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software：Practice and Experience，2011，41(1)：23-50.

[16] TANG K S,MAN K F,KWONG S,et al.Genetic algorithms and their applications[J].IEEE Signal Processing Magazine,1996,13(6)：22-37.

[17] EBERHART R，KENNEDY J.A new optimizer using particle swarm theory[C].[S.l.]：Proceedings of the Sixth International Symposium on IEEE，1995：39-43.

[18] KENNEDY J，EBERHART R.Particle swarm optimization[C].[S.l.]：IEEE Int Conf Neural Networks， 1995：1942-1948.

Task Scheduling Algorithm Based on Improved Cuckoo Search Algorithm in Cloud Computing Environment

Liu Zhu-song, Chen Jie, Tian Long

(School of Computers, Guangdong University of Technology, Guangzhou 510006, China)

Abstract:In the view of efficient task scheduling, the researchers propose an improved cuckoo search based on the introduction of the variability of Cauchy operator, which is helpful in improving the global search and speeding up the convergence of algorithm, for addressing the problem of task scheduling and improving the global searching quality of the cuckoo search algorithm. The study uses an improved algorithm of integer encoding structure to get optimal solutions. The experimental results based on CloudSim platform show that the algorithm can significantly improve the effectiveness and efficiency.

Key words:cloud computing； task scheduling； cuckoo search algorithm； Cauchy distribution

收稿日期:2016- 01- 15

基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(61572144)；廣東省現(xiàn)代信息服務(wù)業(yè)發(fā)展專項(xiàng)資金資助項(xiàng)目(GDEID2011IS022)

作者簡(jiǎn)介:劉竹松(1979-)，男，副教授，主要研究方向?yàn)樵朴?jì)算、大數(shù)據(jù)，E-mail：liuzs@gdut.edu.cn

doi:10.3969/j.issn.1007- 7162.2016.03.006

中圖分類號(hào):TP393

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

文章編號(hào):1007-7162(2016)03- 0032- 05