侯 歡 歡

(太原工業(yè)學(xué)院計(jì)算機(jī)工程系 山西 太原 030008)

0 引 言

云計(jì)算是一種新型的商業(yè)計(jì)算模式，它是并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算融合發(fā)展的結(jié)果。云計(jì)算的發(fā)展一直與大數(shù)據(jù)密切相關(guān)，正是依靠云計(jì)算技術(shù)才使龐大的數(shù)字資源得以高效的分析處理[1]。為提高數(shù)據(jù)處理的高效性，云計(jì)算將每個(gè)任務(wù)分成若干個(gè)相互獨(dú)立的任務(wù)，通過(guò)任務(wù)調(diào)度將任務(wù)分配給計(jì)算資源進(jìn)行處理。隨著用戶需求的日益提高，如何滿足用戶請(qǐng)求,提高云計(jì)算任務(wù)調(diào)度效率已經(jīng)成為云計(jì)算研究領(lǐng)域的關(guān)鍵問(wèn)題之一。傳統(tǒng)任務(wù)調(diào)度算法很難均衡云計(jì)算環(huán)境下的多維約束調(diào)度，粒子群優(yōu)化算法(Partical Swarm Optimization，PSO)是一種群體智能全局尋優(yōu)的算法[2]。該智能優(yōu)化算法在優(yōu)化組合、多目標(biāo)尋優(yōu)、聚類分析等領(lǐng)域應(yīng)用廣泛且效果突出[3-5],利用智能優(yōu)化算法在多維度多任務(wù)方面的尋優(yōu)優(yōu)勢(shì)引起了越來(lái)越多學(xué)者的研究與關(guān)注，已成為云計(jì)算任務(wù)調(diào)度的新工具。文獻(xiàn)[6]在分組遺傳算法的基礎(chǔ)上，提出了基于多維資源協(xié)同聚合的虛擬機(jī)調(diào)度策略，對(duì)均衡資源分配具有一定的優(yōu)勢(shì)；文獻(xiàn)[7]提出了基于改進(jìn)遺傳算法的云計(jì)算任務(wù)調(diào)度，通過(guò)兩個(gè)適應(yīng)度來(lái)選擇種群，縮短了總?cè)蝿?wù)和平均任務(wù)完成時(shí)間；文獻(xiàn)[8]綜合考慮遺傳算法和蟻群算法的優(yōu)勢(shì),提出一種遺傳-蟻群算法的云計(jì)算任務(wù)調(diào)度優(yōu)化算法,提高云計(jì)算任務(wù)求解效率；文獻(xiàn)[9]把改進(jìn)的蟻群算法應(yīng)用到云計(jì)算任務(wù)調(diào)度中，實(shí)現(xiàn)了虛擬機(jī)的負(fù)載均衡和調(diào)度時(shí)間的優(yōu)化；文獻(xiàn)[10]針對(duì)用戶滿意度和云提供商利益需求，提出一種融合粒子群和遺傳算法的PSOGA改進(jìn)算法;文獻(xiàn)[11]在遺傳算法基礎(chǔ)上,提出了一種考慮時(shí)間、成本、CPU、內(nèi)存和帶寬等多維約束的任務(wù)調(diào)度算法MCGA；文獻(xiàn)[12]針對(duì)標(biāo)準(zhǔn)量子粒子群優(yōu)化算法收斂速度慢、求解效率低的缺陷,提出一種基于改進(jìn)量子粒子群算法的云計(jì)算資源調(diào)度方法;文獻(xiàn)[13]提出了一種基于非占優(yōu)排序的混合多目標(biāo)粒子群優(yōu)化的工作流調(diào)度算法HPSO,使調(diào)度解的空間分布更加一致，云環(huán)境工作流調(diào)度更優(yōu)化；文獻(xiàn)[14]綜合考慮任務(wù)截止時(shí)間、調(diào)度預(yù)算和可靠性，提出一種多QOS約束離散粒子群優(yōu)化的任務(wù)調(diào)度算法,有效解決了多約束任務(wù)調(diào)度。本文融合改進(jìn)的分?jǐn)?shù)階達(dá)爾文粒子群算法和多目標(biāo)函數(shù)構(gòu)造，提出了一種新的云計(jì)算任務(wù)調(diào)度算法。

1 粒子群優(yōu)化算法及其衍化

1.1 粒子群算法

粒子群優(yōu)化算法與其他智能優(yōu)化算法一樣，易陷入局部最優(yōu)、搜索精度不高、后期收斂慢等問(wèn)題。針對(duì)這些問(wèn)題，國(guó)內(nèi)外學(xué)者提出了多種改進(jìn)算法。文獻(xiàn)[15]將達(dá)爾文進(jìn)化理論引入粒子群優(yōu)化算法中，提出了一種達(dá)爾文粒子群優(yōu)化算法(Darwinian Partical Swarm Optimization,DPSO)。文獻(xiàn)[16]將分?jǐn)?shù)階微分理論引入粒子群優(yōu)化算法中，提出了分?jǐn)?shù)階粒子優(yōu)化算法(Fractional Order Partical Swarm Optimization,FOPSO),通過(guò)重排原始速度來(lái)修正速度導(dǎo)數(shù)以便控制優(yōu)化算法的收斂速度，取得了不錯(cuò)的效果。受文獻(xiàn)[16]的啟發(fā)，學(xué)者M(jìn)icael將分?jǐn)?shù)階微分和達(dá)爾文進(jìn)化理論相結(jié)合，集中兩者的優(yōu)點(diǎn)應(yīng)用于粒子群優(yōu)化算法中，提出了分?jǐn)?shù)階達(dá)爾文粒子群算法(Fractional Order Darwinian Partical Swarm Optimization,FODPSO)。實(shí)驗(yàn)結(jié)果表明，與其他智能優(yōu)化算法相比，該算法通過(guò)分?jǐn)?shù)階次α來(lái)控制計(jì)算精度與收斂速度，由于過(guò)度依賴分?jǐn)?shù)階次α，容易造成局部最優(yōu)[17]。恰當(dāng)?shù)臋?quán)重系數(shù)ω不僅能提高尋優(yōu)能力還能加速收斂速度。但現(xiàn)實(shí)中對(duì)權(quán)重系數(shù)ω的設(shè)置往往是手動(dòng)設(shè)置固定值，這不利于粒子群對(duì)最優(yōu)解的搜索。

在一個(gè)M維目標(biāo)空間中，Nnum個(gè)粒子組成群落，每個(gè)粒子的速度和位置更新：

(1)

(2)

第i個(gè)粒子位置向量為Xi=(xi1,xi2,…,xiD)，速度向量為Vi=(vi1,vi2,…,viD)，第i個(gè)粒子經(jīng)歷過(guò)的位置中最優(yōu)位置Wi=(wi1,wi2,…,wiD)，整個(gè)粒子群最優(yōu)位置Wg=(wg1,wg2,…,wgD)。式(1)中：ω表示慣性系數(shù)；c1、c2表示加速系數(shù)；R1d、R2d為[0,1]間的隨機(jī)數(shù)；wid表示粒子個(gè)體最優(yōu)值；wgd表示粒子群整體最優(yōu)值。

1.2 粒子群算法的衍化

DPSO將自然選擇理論引入算法中，對(duì)粒子群的壽命進(jìn)行動(dòng)態(tài)縮減。設(shè)SC為粒子搜索計(jì)數(shù)器用以追蹤粒子群適應(yīng)值沒(méi)有改變次數(shù)。當(dāng)粒子群適應(yīng)度沒(méi)有提高時(shí)，其中的粒子被刪除后，該粒子群的搜索計(jì)數(shù)器不置為0，而以下式進(jìn)行設(shè)置：

(3)

式中：Nkill表示粒子群適應(yīng)值沒(méi)變化期間被刪除的粒子數(shù)；SCmax表示最大計(jì)數(shù)值。若粒子群中所有粒子被刪除，且當(dāng)前粒子群數(shù)沒(méi)有超過(guò)種群設(shè)置數(shù)，新建粒子群概率為：

p=r/Nnum

(4)

式中：r為[0,1]間隨機(jī)數(shù)；Nnum表示種群粒子數(shù)。文獻(xiàn)[17]給出了分?jǐn)?shù)階次α調(diào)整公式：

(5)

通過(guò)大量實(shí)驗(yàn)可知分?jǐn)?shù)階次α在[0.5,0.8]之間時(shí)，F(xiàn)ODPSO算法可取得較快的收斂速度。但是通過(guò)式(5)可以看出：隨著迭代次數(shù)的加大，分?jǐn)?shù)階次α?xí)€性減小，這勢(shì)必會(huì)使粒子群陷入局部最優(yōu)和低速收斂。同時(shí)根據(jù)式(1)可以看出：權(quán)重系數(shù)ω越大，速度v就大，這有利于擴(kuò)大最優(yōu)解的搜索空間；當(dāng)權(quán)重系數(shù)ω越小，速度v就小，這會(huì)在當(dāng)前解空間中挖掘更好解，因此權(quán)重系數(shù)ω的設(shè)置不能拘泥于定值。對(duì)此，本文通過(guò)改變分?jǐn)?shù)階次α和慣性權(quán)重系數(shù)ω的調(diào)整方式和陷入局部最優(yōu)的跳出方式，對(duì)分?jǐn)?shù)階達(dá)爾文粒子群算法進(jìn)行改進(jìn)。

2 改進(jìn)分?jǐn)?shù)階達(dá)爾文粒子群算法

2.1 基于自適應(yīng)動(dòng)態(tài)調(diào)整權(quán)重系數(shù)

研究學(xué)者統(tǒng)計(jì)實(shí)驗(yàn)發(fā)現(xiàn)，動(dòng)態(tài)的權(quán)重系數(shù)要比固定設(shè)置的能獲得更好的尋優(yōu)結(jié)果[18]。借鑒前人研究，將粒子的適應(yīng)度值引入慣性權(quán)重系數(shù)ω的調(diào)整中，提出了一種基于自適應(yīng)度動(dòng)態(tài)調(diào)整權(quán)重系數(shù)的方法。設(shè)favg為粒子群平均適應(yīng)度，fbest為粒子群最佳適應(yīng)度，第i個(gè)粒子的適應(yīng)度為fi，慣性權(quán)重系數(shù)ω的調(diào)整如下：

(6)

式中：ωmin、ωmax表示慣性權(quán)重系數(shù)ω的最小、最大值。通過(guò)式(6)我們可以看出當(dāng)前粒子適應(yīng)度與平均適應(yīng)度差值越大，慣性權(quán)重系數(shù)ω越小，這有利于局部搜索；反之，當(dāng)前粒子適應(yīng)度與平均適應(yīng)度差值越小，慣性權(quán)重系數(shù)ω越大，有利于粒子跳出局部進(jìn)行范圍更廣的搜索最優(yōu)解。

2.2 基于進(jìn)化信息調(diào)整分?jǐn)?shù)階次α

(7)

(8)

(9)

(10)

(11)

基于粒子進(jìn)化因子fev∈[0,1]，利用高斯圖函數(shù)得出分?jǐn)?shù)階次α的調(diào)整公式：

(12)

通過(guò)式(12)可知，分?jǐn)?shù)階次α的調(diào)整不再依賴迭代次數(shù)，而是依據(jù)粒子自身的進(jìn)化信息，這可避免算法因分?jǐn)?shù)階次α線性減小而引起的局部最優(yōu)和收斂緩慢。

根據(jù)分?jǐn)?shù)階微分方程的格林瓦德-列特尼科夫(G-L)定義，粒子速度更新策略變?yōu)椋?/p>

(13)

粒子的位置更新依據(jù)式(2)進(jìn)行，其中加速系數(shù)滿足3≤c1+c2≤4。

2.3 基于Levy飛行特征的局部最優(yōu)

本文將Levy飛行特性引入改進(jìn)的分?jǐn)?shù)階達(dá)爾文粒子群算法中，利用Levy飛行特性擴(kuò)展搜索空間，根據(jù)局部最優(yōu)概率因子popt對(duì)算法取得局部最優(yōu)wg進(jìn)行位置擾動(dòng)。

定義局部最優(yōu)概率因子popt：

(14)

wgd=wgd(1+levy(ξ)tanh(fev))

(15)

式中:Levy(ξ)是隨機(jī)搜索路徑，步長(zhǎng)的大小通過(guò)levy分布隨機(jī)數(shù)產(chǎn)生且1≤ξ≤3，0≤fev≤1，0≤tanh(·)≤1。

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

云計(jì)算是利用并行計(jì)算來(lái)處理大數(shù)據(jù)，是按需服務(wù)的模式，資源調(diào)度與網(wǎng)格計(jì)算的任務(wù)調(diào)度相差無(wú)幾，但云計(jì)算以資源虛擬化為前提，通常采用Map/Reduce分布處理技術(shù)[19]。云計(jì)算任務(wù)調(diào)度數(shù)學(xué)模型可表示為：

Model={T,VM,F,A}

(16)

式中：任務(wù)集合T={T1,T2,…，Tn}；n表示任務(wù)的個(gè)數(shù)；每個(gè)任務(wù)都有屬性TAi=,sTi、eTi、dTi,TLi分別表示任務(wù)的大小、最早開(kāi)始時(shí)間、最遲完成時(shí)間和任務(wù)執(zhí)行總時(shí)間。虛擬機(jī)集合VM={VM1,VM2,…，VMm}，其中m表示虛擬機(jī)個(gè)數(shù)。每個(gè)虛擬機(jī)都有屬性：VAj=,Vcompj、Vcpuj、Vramj、Vbwj分別表示虛擬機(jī)j的處理能力、CPU、內(nèi)存、帶寬。

3.1 任務(wù)調(diào)度的多目標(biāo)

綜合評(píng)價(jià)云計(jì)算任務(wù)調(diào)度的優(yōu)良需要從客戶最短等待時(shí)間、虛擬機(jī)資源負(fù)載均衡程度及任務(wù)完成所耗費(fèi)用等不同角度進(jìn)行。

(1) 客戶最短等待時(shí)間WFi:

(17)

式中：timeij表示任務(wù)Ti在所分配的虛擬機(jī)VMj上執(zhí)行所需時(shí)間；sum(VMj)表示分配到虛擬機(jī)VMj上的任務(wù)總數(shù)。綜上可知客戶最短等待時(shí)間WFi表示各個(gè)虛擬機(jī)處理完成分配到的任務(wù)Ti的最遲完成時(shí)間的最大值。這里需要特別說(shuō)明，任務(wù)的處理時(shí)間等于任務(wù)指令長(zhǎng)度除以運(yùn)行該任務(wù)虛擬機(jī)的執(zhí)行速度：

timeij=TAi/VAj

(18)

(2) 虛擬機(jī)資源負(fù)載均衡程度?:

(19)

(3) 任務(wù)完成所耗費(fèi)用Cost:

(20)

式(20)體現(xiàn)了虛擬機(jī)VMj上處理任務(wù)的費(fèi)用所耗，所用費(fèi)用與虛擬機(jī)的CPU、內(nèi)存、帶寬性能有關(guān)。

本文從客戶最短等待時(shí)間、虛擬機(jī)資源負(fù)載均衡程度及任務(wù)完成所耗費(fèi)用等三個(gè)目標(biāo)出發(fā)綜合衡量云計(jì)算任務(wù)調(diào)度的優(yōu)良，數(shù)學(xué)模型如下：

minWF,min?,minCost

(21)

式中: 目標(biāo)函數(shù)minWF、min?、minCost表示客戶最短等待時(shí)間、虛擬機(jī)資源負(fù)載均衡程度及任務(wù)完成所耗費(fèi)用等三個(gè)目標(biāo)要同時(shí)取得最小值，并且約束條件是任務(wù)只能被一個(gè)虛擬機(jī)執(zhí)行。

3.2 任務(wù)調(diào)度多目標(biāo)函數(shù)構(gòu)造

任務(wù)調(diào)度的好壞不僅僅由一個(gè)目標(biāo)函數(shù)決定，本文將最短等待時(shí)間、虛擬機(jī)資源負(fù)載均衡程度及任務(wù)完成所耗費(fèi)用等三個(gè)目標(biāo)以基于先驗(yàn)偏好[20]構(gòu)造任務(wù)調(diào)度滿意度函數(shù)，再將任務(wù)調(diào)度的多目標(biāo)問(wèn)題轉(zhuǎn)化成單目標(biāo)問(wèn)題。設(shè)客戶最短等待時(shí)間的區(qū)間為[WFmin,WFmax]，虛擬機(jī)資源負(fù)載均衡程度滿意區(qū)間[?min,?max]，任務(wù)完成所耗費(fèi)用區(qū)間[Costmin,Costmax]，引入極小值ε，三個(gè)目標(biāo)的計(jì)算如下：

(22)

(23)

(24)

利用幾何平均法將以上三個(gè)目標(biāo)進(jìn)行融合，任務(wù)調(diào)度綜合滿意度評(píng)價(jià)為：

(25)

通過(guò)式(25)可知，利用幾何平均法將三個(gè)評(píng)價(jià)目標(biāo)轉(zhuǎn)換為綜合滿意度CS，并且只有當(dāng)且僅當(dāng)三個(gè)評(píng)價(jià)目標(biāo)同時(shí)滿意度為1時(shí)，綜合滿意度CS才為1。

3.3 粒子編碼規(guī)則

粒子編碼有兩種，一是直接編碼，另一種是間接編碼。本文采用間接編碼方式即對(duì)每個(gè)子任務(wù)所對(duì)應(yīng)的虛擬機(jī)進(jìn)行編碼，也就是說(shuō)一個(gè)粒子對(duì)應(yīng)著一個(gè)任務(wù)的分配策略。比如任務(wù)數(shù)n=3，虛擬機(jī)數(shù)m=3,任務(wù)分解后的子任務(wù)數(shù)mall=10，粒子編碼(2,3,1,2,3,3,2,1,2,1)即為一種可行的任務(wù)調(diào)度方案。粒子編碼如表1所示。

表1 粒子編碼

續(xù)表1

表1中，任務(wù)序號(hào)、子任務(wù)序號(hào)對(duì)(3,9)表示第3個(gè)任務(wù)中的第4個(gè)子任務(wù)序號(hào)為9；子任務(wù)序號(hào)、虛擬機(jī)序號(hào)對(duì)(2,3)表示把子任務(wù)2分配到虛擬機(jī)3上去執(zhí)行。

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

為了驗(yàn)證本文改進(jìn)算法的優(yōu)越性，從兩個(gè)方面進(jìn)行對(duì)比分析：一是利用四種測(cè)試函數(shù)對(duì)比尋優(yōu)效果；二是通過(guò)任務(wù)調(diào)度對(duì)比分析算法的調(diào)度性能。采用Cloudsim 3.0云平臺(tái)軟件對(duì)算法的實(shí)際調(diào)度性能進(jìn)行仿真對(duì)比，仿真是在Windows 7系統(tǒng)下，CPU：i5-4460T@2.7 GHz, RAM:4 GB。

4.1 尋優(yōu)效果對(duì)比分析

將本文算法、FOPSO和FODPSO在表2所示的四個(gè)標(biāo)準(zhǔn)函數(shù)上[17]對(duì)比尋優(yōu)效果。三種粒子群優(yōu)化算法的參數(shù)設(shè)置如表3所示。種群規(guī)模設(shè)為50，最大迭代次數(shù)為1 000次。三種粒子群優(yōu)化算法運(yùn)行100次取平均。

表2 四個(gè)標(biāo)準(zhǔn)函數(shù)

表3 參數(shù)設(shè)置

圖1為三種智能優(yōu)化算法對(duì)表2四個(gè)標(biāo)準(zhǔn)函數(shù)的尋優(yōu)收斂曲線。

圖1 三種粒子群優(yōu)化算法尋優(yōu)收斂曲線

由圖1可以看出：FOPSO和FODPSO對(duì)Rastrigin標(biāo)準(zhǔn)函數(shù)的尋優(yōu)效果一般，過(guò)早陷入了局部最優(yōu)；隨著迭代次數(shù)的增加，F(xiàn)OPSO和FODPSO在多峰Ackley函數(shù)、單峰Sphere、Rosenbrock函數(shù)上，收斂速度緩慢，尋優(yōu)精度不精。而本文改進(jìn)算法無(wú)論是對(duì)Sphere、Rosenbrock兩種單峰函數(shù)還是對(duì)Rastrigin、Ackley多峰函數(shù)都能在若干次迭代后迅速?gòu)木植孔顑?yōu)中跳出，并快速搜尋到最優(yōu)值，擴(kuò)大了對(duì)最優(yōu)值的全局搜索能力。

4.2 任務(wù)調(diào)度對(duì)比分析

在Cloudsim 3.0平臺(tái)中將云計(jì)算任務(wù)調(diào)度算法添加到DatacenterBroker類中；通過(guò)重置Cloudlet類和VM類進(jìn)行虛擬機(jī)和任務(wù)的參數(shù)設(shè)置。將本文改進(jìn)算法與文獻(xiàn)[10，13，21]進(jìn)行云計(jì)算任務(wù)調(diào)度，使用最大完成時(shí)間、截止時(shí)間違背率和虛擬機(jī)資源利用率三個(gè)云計(jì)算任務(wù)調(diào)度評(píng)價(jià)指標(biāo)定量分析調(diào)度結(jié)果。本文粒子群參數(shù)設(shè)置詳見(jiàn)表3，任務(wù)數(shù)n=200，資源數(shù)m=50，其他算法的參數(shù)設(shè)置參照對(duì)應(yīng)參考文獻(xiàn)。

(1) 最大完成時(shí)間。最大完成時(shí)間是評(píng)價(jià)任務(wù)調(diào)度的重要指標(biāo)，最大完成時(shí)間越小表示任務(wù)完成的速度越快，算法的調(diào)度性能越好。通過(guò)設(shè)置不同的任務(wù)量，對(duì)比各算法的最大完成時(shí)間，結(jié)果如圖2所示。

圖2 四種任務(wù)調(diào)度算法最大完成時(shí)間

圖2顯示了在不同任務(wù)總數(shù)參與調(diào)度的情況下，各調(diào)度算法最大完成時(shí)間的趨勢(shì)。隨著任務(wù)數(shù)的增多，各算法完成任務(wù)調(diào)度的最大完成時(shí)間隨之增大。文獻(xiàn)[13]不僅改進(jìn)了粒子算法固有的尋優(yōu)劣勢(shì)，還綜合了任務(wù)調(diào)度的多目標(biāo)，將最晚完成時(shí)間作為任務(wù)調(diào)度的考核目標(biāo)之一，任務(wù)完成的最大時(shí)間與其他兩種算法相比較小。文獻(xiàn)[10，21]對(duì)粒子群算法的改進(jìn)并不徹底，粒子群算法任然存在陷入局部最優(yōu)和收斂過(guò)慢的毛病，并且調(diào)度考核的目標(biāo)單一，任務(wù)完成最大時(shí)間隨著任務(wù)數(shù)的增大而不斷增大。本文算法通過(guò)調(diào)整分?jǐn)?shù)階次α系數(shù)以加速收斂，利用Levy飛行隨機(jī)擾動(dòng)以擺脫局部最優(yōu)，自適應(yīng)動(dòng)態(tài)調(diào)整權(quán)重系數(shù)來(lái)收縮自如地尋找最優(yōu)值，較為全面地改進(jìn)分?jǐn)?shù)階達(dá)爾文粒子群算法，并將最短等待時(shí)間、資源負(fù)載均衡程度及任務(wù)完成所耗費(fèi)用等三個(gè)目標(biāo)規(guī)劃為單一目標(biāo)評(píng)價(jià)函數(shù)，以作為任務(wù)調(diào)度的評(píng)價(jià)目標(biāo)，取得了較好的調(diào)度效果。

(2) 截止時(shí)間未完成率。截止時(shí)間是任務(wù)調(diào)度最根本的要求，也是考量任務(wù)調(diào)度的基本指標(biāo)。調(diào)度算法對(duì)大量任務(wù)進(jìn)行調(diào)度時(shí)，很難萬(wàn)無(wú)一失地在截止時(shí)間前完成所有數(shù)據(jù)處理。截止時(shí)間未完成率就是在截止時(shí)間未完成的任務(wù)數(shù)與總?cè)蝿?wù)數(shù)的間比值。通過(guò)設(shè)置不同的任務(wù)量，對(duì)比各算法的截止時(shí)間未完成率，結(jié)果如圖3所示。

圖3 四種任務(wù)調(diào)度算法截止時(shí)間未完成率

圖3顯示了不同任務(wù)總數(shù)與截止時(shí)間未完成率的關(guān)系。隨著任務(wù)數(shù)的增多，本文任務(wù)調(diào)度算法與文獻(xiàn)[13]都維持在較低的截止時(shí)間未完成率，兩者相比較而言，本文調(diào)度算法的未完成率較低，一直保持在5%以下，這是由于本文的目標(biāo)函數(shù)中有客戶最短等待時(shí)間這一評(píng)價(jià)約束目標(biāo)。文獻(xiàn)[21]單以截止時(shí)間為約束，粒子群優(yōu)化算法改進(jìn)不到位，制約了最終的調(diào)度結(jié)果。文獻(xiàn)[10]主要考慮任務(wù)與資源的負(fù)載率，并沒(méi)有將任務(wù)完成截止時(shí)間作為任務(wù)調(diào)度的約束條件，致使任務(wù)截止時(shí)間未完成率較高。

(3) 虛擬機(jī)資源利用率。虛擬機(jī)資源利用率表示虛擬機(jī)資源的整體利用程度[22]。公式為:

(26)

式中：tj.stime表示任務(wù)j的開(kāi)始時(shí)間；tj.etime表示任務(wù)j的結(jié)束時(shí)間；Δij為布爾變量，若Δij=1表示任務(wù)j被分配到虛擬機(jī)i上執(zhí)行，反之亦然；Tetime表示所有任務(wù)完成總時(shí)間。在任務(wù)數(shù)n=100的情況下，隨機(jī)選取10個(gè)虛擬機(jī)(5,10,18,27,39,46,55,63,72,80)，對(duì)比分析各算法在虛擬機(jī)上的資源利用率，結(jié)果如圖4所示。

圖4 各算法虛擬機(jī)資源利用率對(duì)比

圖4顯示了各算法在不同虛擬機(jī)上的資源利用率，在任務(wù)數(shù)一定的情況下，本文算法的任務(wù)調(diào)度較為均衡，虛擬機(jī)資源利用較為充分，資源利用率始終保持在95%以上。文獻(xiàn)[13]綜合任務(wù)執(zhí)行代價(jià)和執(zhí)行能耗，以此均衡各虛擬機(jī)間的負(fù)載，也獲得了不錯(cuò)的效果，資源利用率始終保持在90%以上。文獻(xiàn)[10]和文獻(xiàn)[21]以截止時(shí)間或執(zhí)行綜合能耗為評(píng)價(jià)目標(biāo)，虛擬機(jī)均衡無(wú)法圓滿地兼顧，資源利用率波動(dòng)較大，各虛擬機(jī)間的負(fù)載不夠均衡。

5 結(jié) 語(yǔ)

本文提出了一種基于分?jǐn)?shù)階達(dá)爾文粒子群的多目標(biāo)云計(jì)算任務(wù)調(diào)度算法。通過(guò)改變分?jǐn)?shù)階次α和慣性

權(quán)重系數(shù)ω的調(diào)整方式和陷入局部最優(yōu)的跳出方式，對(duì)分?jǐn)?shù)階達(dá)爾文粒子群算法進(jìn)行改進(jìn)，融合最短等待時(shí)間、資源負(fù)載均衡及任務(wù)完成所耗費(fèi)用等三個(gè)目標(biāo)構(gòu)造任務(wù)調(diào)度滿意度函數(shù)，以此搜索任務(wù)調(diào)度最優(yōu)解。仿真實(shí)驗(yàn)表明，本文改進(jìn)的調(diào)度算法與其他三種調(diào)度算法相比，本文調(diào)度算法不僅有最低的任務(wù)最大完成時(shí)間和截止時(shí)間未完成率，還較好地完成了虛擬資源的均衡負(fù)載。