基于煙花算法的云計(jì)算任務(wù)調(diào)度研究

孫鳳杰，王克儉*，何振學(xué)，高萬豪

(1. 河北農(nóng)業(yè)大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 保定 071001；2. 天津城建大學(xué)控制與機(jī)械工程學(xué)院，天津 300384)

1 引言

云計(jì)算是基于分布式計(jì)算、網(wǎng)格計(jì)算以及并行計(jì)算發(fā)展起來的新型計(jì)算模式，并且成為當(dāng)今社會(huì)的一個(gè)熱點(diǎn)研究方向。云計(jì)算中的任務(wù)調(diào)度算法會(huì)影響到云計(jì)算的效率。云計(jì)算環(huán)境下將任務(wù)動(dòng)態(tài)地調(diào)用給各個(gè)虛擬機(jī)并提供給用戶使用，怎樣合理地將任務(wù)分配給不同的虛擬資源，進(jìn)而使得整個(gè)系統(tǒng)的性能達(dá)到最優(yōu)效果，是云任務(wù)調(diào)度算法需要解決的關(guān)鍵性問題[1]。傳統(tǒng)的云任務(wù)調(diào)度算法有：貪心算法、輪詢調(diào)度算法等，對(duì)于少量任務(wù)來說，這些算法可以取得較好地效果，但是隨著任務(wù)數(shù)量的不斷增加，傳統(tǒng)算法存在著完成時(shí)間較長、負(fù)載不均衡以及資源利用率低等一系列缺點(diǎn)[2]。因此，為了解決傳統(tǒng)算法所帶來的缺點(diǎn)，一些群體智能算法不斷地被應(yīng)用于云任務(wù)調(diào)度中，并且成為目前研究的熱點(diǎn)，比如遺傳算法[3，4]、蟻群算法[5]、粒子群算法[6，7]、煙花算法[8]。

屈遲文等人[9]提出了一種基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法，該算法通過檢測個(gè)體相似度增加交叉操作的有效性對(duì)算法進(jìn)行改進(jìn)，但是沒有考慮任務(wù)的完成成本。劉峰等人[10]提出了一種基于時(shí)間和負(fù)載均衡的雙適應(yīng)度函數(shù)改進(jìn)的遺傳算法，但是缺乏對(duì)任務(wù)的完成成本的優(yōu)化。齊平等人[11]提出了一種將粒子群算法與資源可靠性評(píng)估模型相結(jié)合的調(diào)度算法，雖然解決了資源失效問題，但是沒有考慮任務(wù)的完成時(shí)間和成本。王欣欣等人[12]提出了一種基于任務(wù)完成時(shí)間和能量消耗的動(dòng)態(tài)遺傳算法的云計(jì)算資源調(diào)度，該算法降低了時(shí)間和能量，但是未考慮任務(wù)的成本。

譚營等人[12]首次嘗試將離散煙花算法用于求解旅行商問題，并且得到了不錯(cuò)的效果，除此之外，煙花算法還被應(yīng)用于0/1背包問題上[14]、方程組求解問題上[15]、施肥問題上[16]、圖像識(shí)別領(lǐng)域[16]。在云計(jì)算任務(wù)調(diào)度中，極少的涉及到煙花算法。因此，在云計(jì)算中，為了尋找最優(yōu)的云任務(wù)調(diào)度方案，使得任務(wù)完成時(shí)間短、成本低，本文提出了一種將煙花算法與云計(jì)算任務(wù)調(diào)度模型相結(jié)合的任務(wù)調(diào)度算法，并且通過CloudSim進(jìn)行實(shí)驗(yàn)，驗(yàn)證了本文算法的有效性。

2 云計(jì)算中任務(wù)調(diào)度模型

2.1 云任務(wù)調(diào)度的描述

云任務(wù)調(diào)度模[18]主要由以下部分構(gòu)成：任務(wù)、任務(wù)管理器、任務(wù)調(diào)度器和云環(huán)境，模型如圖1所示。在該模型中，云任務(wù)調(diào)度分為兩個(gè)級(jí)別，第一級(jí)別是任務(wù)到虛擬機(jī)的調(diào)度，主要是研究任務(wù)調(diào)度算法，即當(dāng)用戶提交任務(wù)到數(shù)據(jù)中心時(shí)，合理地將任務(wù)調(diào)度到虛擬機(jī)進(jìn)行執(zhí)行；第二級(jí)別是虛擬機(jī)到物理機(jī)的調(diào)度，即將虛擬機(jī)接收的任務(wù)調(diào)度到合適的主機(jī)并運(yùn)行的過程。本文研究的是第一級(jí)別的調(diào)度，即云任務(wù)調(diào)度。 在該任務(wù)調(diào)度過程中，采用任務(wù)調(diào)度策略將用戶所提交的n個(gè)任務(wù)合理地分配至m個(gè)空閑的虛擬資源上使用(n>m)，進(jìn)而達(dá)到時(shí)間短、成本低、負(fù)載均衡等目標(biāo)，其中任務(wù)調(diào)度策略就是用戶所使用的不同的調(diào)度算法。

圖1 任務(wù)調(diào)度模型

2.2 云任務(wù)調(diào)度中的相關(guān)定義

本文中用n來表示云任務(wù)的數(shù)量，m來表示虛擬機(jī)的數(shù)量，etcij表示第j個(gè)任務(wù)在第i個(gè)虛擬資源上的執(zhí)行時(shí)間，i∈[1，m]，j∈[1，n]，用來計(jì)算各個(gè)虛擬資源上任務(wù)運(yùn)行完成所需的時(shí)間，rcui表示第i個(gè)虛擬機(jī)的單位成本。本文將任務(wù)的完成時(shí)間和成本作為云計(jì)算中任務(wù)調(diào)度效果的評(píng)價(jià)指標(biāo)。

1)任務(wù)完成時(shí)間

云計(jì)算中任務(wù)完成時(shí)間是衡量任務(wù)調(diào)度效果的重要因素之一，任務(wù)完成時(shí)間如式(1)所示

(1)

(2)

式中，task＿length(j)為第j個(gè)任務(wù)的長度，mipsi為第i個(gè)虛擬機(jī)的處理速度。

2)任務(wù)的完成成本

除了完成時(shí)間外，另一個(gè)重要的衡量因素是任務(wù)完成成本，任務(wù)的完成成本如式(3)所示

(3)

(4)

式中，vm＿cost(i)為第i個(gè)虛擬機(jī)的花費(fèi)。

3 基于煙花算法的云任務(wù)調(diào)度算法

2010年譚營教授和其團(tuán)隊(duì)提出了煙花算法[13]，它是通過模擬自然界中煙花爆炸過程所形成的群體智能優(yōu)化算法，并且具有局部性、隨機(jī)性以及多樣性的特點(diǎn)，主要用于復(fù)雜問題的優(yōu)化。煙花算法把每一煙花作為問題的一個(gè)可行解，根據(jù)適應(yīng)度函數(shù)來計(jì)算每一煙花所產(chǎn)生火花數(shù)，適應(yīng)度值越大的煙花產(chǎn)生的火花數(shù)目越多，反之越少，其中煙花爆炸所產(chǎn)生一定數(shù)量火花的過程就是搜索鄰域的過程。煙花算法主要由爆炸算子、變異算子以及選擇策略三部分組成。

3.1 算法的編碼

本文采用了資源-任務(wù)的編碼方式，這種編碼方式通俗易懂，操作簡單，不易出錯(cuò)。比如煙花為{2，3，4，1，2，3，4，1，2，3}，10個(gè)任務(wù)分配給4個(gè)虛擬資源，編號(hào)1、2、3和4的虛擬資源上所對(duì)應(yīng)的任務(wù)數(shù)為2、3、3和2，即：{{1，2}，{2，3}，{3，4}，{4，1}，{5，2}，{6，3}，{7，4}，{8，1}，{9，2}，{10，3}}，表示1號(hào)任務(wù)分配給2號(hào)虛擬資源，2號(hào)任務(wù)分配給3號(hào)虛擬資源，以此類推，10號(hào)任務(wù)分配給3號(hào)虛擬資源，編碼方式如圖2所示，Vi為任務(wù)Ti執(zhí)行時(shí)所對(duì)應(yīng)的虛擬資源編號(hào)，Ti為任務(wù)編號(hào)。

圖2 編碼方式

假設(shè)有n個(gè)任務(wù)，m個(gè)虛擬資源，一個(gè)煙花為{3，2，1，4，3，2，…，m，m-1}，表示第1個(gè)任務(wù)分配到第3個(gè)虛擬資源上，第2個(gè)任務(wù)分配到第2個(gè)虛擬資源上，第3個(gè)任務(wù)分配到第1個(gè)虛擬資源上，第4個(gè)任務(wù)分配到第4個(gè)虛擬資源上，以此類推，任務(wù)和虛擬資源所對(duì)應(yīng)的關(guān)系如表1所示。

表1 任務(wù)與虛擬資源所對(duì)應(yīng)的關(guān)系

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

在一定程度上適應(yīng)度值決定著種群個(gè)體的生存能力，煙花算法中是通過計(jì)算每個(gè)煙花的適應(yīng)度值來確定每個(gè)煙花所產(chǎn)生的火花數(shù)量，適應(yīng)度值越大的煙花產(chǎn)生更多的火花，反之，產(chǎn)生更少的火花。本文采用時(shí)間適應(yīng)度函數(shù)、成本適應(yīng)度函數(shù)，對(duì)于煙花wi的適應(yīng)度函數(shù)如下。

時(shí)間適應(yīng)度函數(shù)的定義如式(5)所示

(5)

(6)

式中，u為虛擬資源的利用率情況，該值越大，虛擬資源的利用率越高。

成本適應(yīng)度函數(shù)的定義如式(7)所示

(7)

因此，本文所設(shè)計(jì)的基于任務(wù)完成時(shí)間和成本的適應(yīng)度函數(shù)如式(8)

fit(wi)=α×fit1(wi)+β×fit2(wi)

(8)

式中，α∈[0，1]，任務(wù)完成時(shí)間的權(quán)重，β∈[0，1]，任務(wù)完成成本的權(quán)重。根據(jù)自己的偏好決定權(quán)重的取值，并且滿足α+β=1。

3.3 爆炸算子

算法初始化時(shí)，適應(yīng)度越好的煙花可以產(chǎn)生更多的火花，具有較強(qiáng)的局部搜索能力，適應(yīng)度越差的煙花可以產(chǎn)生越少的火花。煙花wi所產(chǎn)生的爆炸半徑Ri和爆炸火花的數(shù)量Si分別如式(9)和(10)所示。

(9)

(10)

式中，fitmin和fitmax分別表示當(dāng)前煙花種群中適應(yīng)度最小值和適應(yīng)度值最大值，fit(wi)為個(gè)體wi的適應(yīng)度值。γ為基本的爆炸幅度，用來調(diào)整爆炸半徑的大小，ρ為基本的爆炸火花數(shù)目，用來控制產(chǎn)生火花數(shù)目的大小，δ為極小常數(shù)，主要防止分母為0。

為了確保所產(chǎn)生的火花總數(shù)比較穩(wěn)定，避免出現(xiàn)好的煙花數(shù)目較多、差的煙花數(shù)目較少的狀況，需要限制火花個(gè)數(shù)，如式(11)所示。

(11)

式中，a和b為常數(shù)。

3.4 變異算子

為了保證煙花種群的多樣性，避免算法出現(xiàn)局部峰值的現(xiàn)象，引入變異算子來產(chǎn)生變異火花，本文采用了高斯變異：先在煙花種群中隨機(jī)選擇一個(gè)煙花wi，然后隨機(jī)選擇維度k進(jìn)行高斯變異操作，如式(12)所示

(12)

在產(chǎn)生爆炸火花和高斯變異火花的過程中，所產(chǎn)生的火花可能會(huì)超出邊界范圍，因此對(duì)超出邊界的個(gè)體采用映射規(guī)則，如式(13)所示。

(13)

3.5 選擇策略

為了保證煙花種群中優(yōu)秀的個(gè)體傳遞到下一代中，在產(chǎn)生爆炸火花和高斯變異火花后，種群中包括煙花、爆炸火花以及高斯變異火花，適應(yīng)度值最大的個(gè)體直接被保留至下一代，其余N-1個(gè)個(gè)體本文采用輪盤賭的方式進(jìn)行選擇，選擇概率如式(14)所示。

(14)

(15)

式中，sum(wi)為個(gè)體wi與其它個(gè)體的歐氏距離，K表示煙花和所產(chǎn)生的火花構(gòu)成的種群集合。

3.6 算法描述

煙花算法的整體流程如下：

Step1：隨機(jī)初始化煙花種群，產(chǎn)生N個(gè)煙花wi(i=1，2，3，…，N)，最大迭代次數(shù)gMax。

Step2：根據(jù)式(8)計(jì)算適應(yīng)度值。

Step3：根據(jù)式(9)、(10)和(11)計(jì)算每個(gè)煙花wi的爆炸半徑以及所產(chǎn)生的爆炸火花數(shù)，產(chǎn)生爆炸火花。

Step4：根據(jù)式(12)產(chǎn)生高斯變異火花，若有火花越界，則根據(jù)式(13)將超出邊界的火花映回到可行域。

Step5：將適應(yīng)度值最好的煙花或者火花保留到下一代，從煙花種群中根據(jù)式(14)和(15)選擇N-1個(gè)煙花。

Step6 如果迭代次數(shù)達(dá)到最大值，則輸出最終結(jié)果，否則，轉(zhuǎn)至Step2。

算法流程圖如圖3所示。

圖3 算法流程圖

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

4.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證本文算法的有效性，本文采用墨爾本大學(xué)Buyya教授帶領(lǐng)開發(fā)的CloudSim平臺(tái)[19]來模擬云計(jì)算環(huán)境，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。實(shí)驗(yàn)環(huán)境：eclipse2018、Intel(R)Core(TM) i5-4210U CPU 1.70GHz 2.40GHz的處理器，4.00GB的內(nèi)存。算法中主要參數(shù)的取值：基本爆炸火花數(shù)ρ=40，基本爆炸幅度γ=50，高斯火花個(gè)數(shù)M=5，參數(shù)a=0.8，參數(shù)b=0.04，α=0.2，β=0.8。

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

實(shí)驗(yàn)中云任務(wù)長度在500-20000之間，虛擬資源的運(yùn)算能力在1000-5000MIPS之間，最大迭代次數(shù)gMax為100，煙花種群大小N為30，將本文算法與GA、PSO和文獻(xiàn)[19]TCGA算法進(jìn)行對(duì)比，分析比較任務(wù)數(shù)的變化對(duì)任務(wù)的總完成時(shí)間和任務(wù)的總完成成本的影響。

1)當(dāng)資源數(shù)目為10個(gè)時(shí)，改變?nèi)蝿?wù)的數(shù)量從10個(gè)到220個(gè)，任務(wù)數(shù)分別是：10、40、70、100、130、160、190、220，然后記錄任務(wù)總完成時(shí)間的變化，如圖4所示。

圖4 不同任務(wù)數(shù)下的任務(wù)總完成時(shí)間結(jié)果對(duì)比圖

從圖4中可以得出，當(dāng)資源數(shù)不變時(shí)，任務(wù)數(shù)逐漸增加，本文算法的任務(wù)總完成時(shí)間要比GA、PSO和TCGA算法少。當(dāng)任務(wù)數(shù)比較少時(shí)，算法的效果不是特別明顯，主要是因?yàn)橘Y源數(shù)和任務(wù)數(shù)的差別不是特別大，資源節(jié)點(diǎn)有能力去處理這些任務(wù)，但是當(dāng)任務(wù)數(shù)多于100時(shí)，本文算法下的任務(wù)總完成時(shí)間明顯比其它三種算法好，并且本文算法的任務(wù)完成時(shí)間比GA降低了20%左右，比PSO降低了18%左右，比TCGA算法降低了15%左右。

2)當(dāng)資源數(shù)目為10個(gè)時(shí)，改變?nèi)蝿?wù)的數(shù)量從10個(gè)到220個(gè)，任務(wù)數(shù)分別是：10、40、70、100、130、160、190、220，然后記錄任務(wù)總完成成本的變化，如圖5所示。

圖5 不同任務(wù)數(shù)下的任務(wù)總完成成本結(jié)果對(duì)比圖

從圖5可以得出，本文算法的效果優(yōu)于其它三種算法，并且隨之任務(wù)數(shù)的不斷增加，本文算法的效果更明顯，并且本文算法的任務(wù)總完成成本比GA降低了14%左右，比PSO降低了13%左右，比TCGA算法降低了9%左右。

從以上結(jié)果可以看出，本文所提出的基于煙花算法的任務(wù)調(diào)度算法的效果更好，不僅有效的縮短了任務(wù)完成時(shí)間，而且降低了任務(wù)完成成本。

5 總結(jié)

為了降低云計(jì)算中任務(wù)調(diào)度完成時(shí)間和成本，并且為了保證種群多樣性，避免早熟收斂等問題，本文將煙花算法用于任務(wù)調(diào)度中。本文算法將任務(wù)完成時(shí)間和成本同時(shí)作為優(yōu)化目標(biāo)對(duì)云計(jì)算中任務(wù)進(jìn)行調(diào)度，仿真結(jié)果表明，本文算法可以在云計(jì)算中實(shí)現(xiàn)比較合理地任務(wù)調(diào)度，縮短了任務(wù)的執(zhí)行時(shí)間，并且降低了任務(wù)完成成本。

未來的工作中可以考慮其它因素對(duì)云計(jì)算中任務(wù)調(diào)度結(jié)果的影響，比如網(wǎng)絡(luò)服務(wù)質(zhì)量，并且為了提高煙花算法的效率，可以在集群環(huán)境中研究任務(wù)調(diào)度問題。