基于IPSO_CS的云資源調(diào)度算法仿真研究

李新飛, 謝曉蘭,b

(桂林理工大學(xué) a.信息科學(xué)與工程學(xué)院; b.廣西嵌入式技術(shù)與智能系統(tǒng)重點(diǎn)實(shí)驗(yàn)室， 廣西 桂林 541006)

0 引 言

云計(jì)算是大規(guī)模分布式計(jì)算和并行處理的一個(gè)新的視角，它以按使用付費(fèi)的方式提供服務(wù)[1]，是一種從任務(wù)集中的云計(jì)算模式[2]發(fā)展，可以提供大規(guī)模分布式資源并進(jìn)行協(xié)同計(jì)算的超級(jí)計(jì)算服務(wù)。網(wǎng)絡(luò)“云”將分解后的小塊計(jì)算機(jī)程序數(shù)據(jù)使用在多部服務(wù)器組上，在處理和分析后服務(wù)于用戶(hù)，而任務(wù)調(diào)度的效率成了云計(jì)算中最迫切需要解決的問(wèn)題。

隨著應(yīng)用程序計(jì)算需求以及用戶(hù)需求的快速增長(zhǎng)，計(jì)算資源不斷增多，任務(wù)調(diào)度作為組合優(yōu)化問(wèn)題在考慮如何及時(shí)、高效地進(jìn)行任務(wù)分配以及合理利用資源、提高資源利用率方面起著十分關(guān)鍵的作用。任務(wù)調(diào)度就是綜合考慮任務(wù)完成時(shí)間、負(fù)載均衡和服務(wù)質(zhì)量等因素，將用戶(hù)任務(wù)匹配給合適的虛擬計(jì)算資源，所選用的任務(wù)調(diào)度優(yōu)化算法直接影響著任務(wù)分配的效率，算法的優(yōu)劣程度影響著減少總?cè)蝿?wù)執(zhí)行時(shí)間。智能優(yōu)化算法在解決任務(wù)調(diào)度問(wèn)題方面非常有效，可以顯著降低搜索復(fù)雜度，增大搜索空間，在模擬自然過(guò)程中解決全局最優(yōu)解問(wèn)題。粒子群算法以及其各種優(yōu)化算法作為智能優(yōu)化算法的典型，雖然應(yīng)用領(lǐng)域紛雜、起源很久但由于其簡(jiǎn)單容易實(shí)現(xiàn)且沒(méi)有許多參數(shù)而被廣泛使用。

在考慮到粒子群及其優(yōu)化算法的優(yōu)勢(shì)和云計(jì)算環(huán)境下巨大的資源數(shù)量，以及種群初始化和萊維飛行搜索的隨機(jī)性造成不穩(wěn)定性而產(chǎn)生的結(jié)果隨機(jī)性，對(duì)任務(wù)的執(zhí)行時(shí)間進(jìn)行算法穩(wěn)定性分析判斷，從執(zhí)行時(shí)間和成本出發(fā)提出了一種改進(jìn)的粒子群布谷鳥(niǎo)算法(Improved particle swarm cuckoo algorithm，IPSO_CS)，采用非線性自適應(yīng)慣性權(quán)重代替提高種群多樣性；引入布谷鳥(niǎo)搜索(cuckoo search)中模擬捕食者狩獵的萊維飛行機(jī)制增加粒子位置變化的活力，調(diào)整搜索范圍的步長(zhǎng)因子，增大靠近精英解的概率，以及tent混沌擾動(dòng)打破局部最優(yōu)的狀態(tài)。仿真結(jié)果表明，其可以很好的解決算法的早熟收斂、搜索效率低、結(jié)果隨機(jī)等問(wèn)題，相較與其他 PSO 具有更優(yōu)的性能。

1 研究背景

云計(jì)算環(huán)境下的任務(wù)調(diào)度作為數(shù)學(xué)七大難題之一的NP完全問(wèn)題[3]，最優(yōu)解的獲取適合如灰狼算法、粒子群算法、禁忌搜索[4]、煙花算法等相關(guān)智能改進(jìn)算法來(lái)逼近最優(yōu)解。文獻(xiàn)[5]中在編碼方式采用間接編碼進(jìn)行改進(jìn)，優(yōu)化相關(guān)參數(shù)設(shè)置且在任務(wù)調(diào)度的效率方面有所進(jìn)步。文獻(xiàn)[6]中為加快搜索速度以及減少云計(jì)算任務(wù)執(zhí)行時(shí)間引入局部及全局信息深度更新的方法來(lái)改進(jìn)蟻群算法。文獻(xiàn)[7]中的雙適應(yīng)度遺傳算法 (Double fitness genetic algorithm，DFGA) 考慮任務(wù)完成時(shí)間和任務(wù)平均完成時(shí)間雙適應(yīng)度。文獻(xiàn)[8]中提出一種優(yōu)化的多目標(biāo)粒子群算法(Optimize multi-objective task scheduling particle swarm algorithm，MOTS-PSO) ，分別給予任務(wù)總執(zhí)行時(shí)間、總傳輸時(shí)間和單節(jié)點(diǎn)執(zhí)行代價(jià)不同的權(quán)重建立多目標(biāo)優(yōu)化模型，解決傳統(tǒng)粒子群算法收斂速度慢和精度低等問(wèn)題，實(shí)驗(yàn)證明算法效果更優(yōu)。文獻(xiàn)[9]中在多目標(biāo)方面提出一種遺傳與粒子群算法融合多目標(biāo)任務(wù)調(diào)度算法，將粒子群和遺傳算法的優(yōu)勢(shì)結(jié)合起來(lái)，針對(duì)調(diào)度策略不能滿(mǎn)足用戶(hù)需求的問(wèn)題進(jìn)行多目標(biāo)優(yōu)化。文獻(xiàn)[10]中在tent映射的自適應(yīng)混沌粒子群的任務(wù)調(diào)度問(wèn)題研究中引入混沌優(yōu)化策略，以其混沌運(yùn)動(dòng)的隨機(jī)遍歷優(yōu)勢(shì)解決粒子群(PSO)算法迭代后期易陷入局部最優(yōu)的缺陷。文獻(xiàn)[11]中將蟻群算法優(yōu)勢(shì)、多維服務(wù)質(zhì)量約束、遺傳算法優(yōu)勢(shì)相結(jié)合提出了一種云計(jì)算多QoS約束云計(jì)算任務(wù)調(diào)度算法(Multi-QoS with genetic and ant colony optimization algorithm，MQoS-GAAC)，將用戶(hù)的服務(wù)質(zhì)量作為適應(yīng)度函數(shù)，采用動(dòng)態(tài)融合策略確定蟻群算法和遺傳算法的最佳融合時(shí)間，不僅提高了用戶(hù)服務(wù)質(zhì)量，而且保持了資源負(fù)載均衡。文獻(xiàn)[12]中研究證明粒子群算法與遺傳算法相比在云計(jì)算環(huán)境中調(diào)度效果更好。以上工作考慮到的目標(biāo)單一、早熟收斂或多目標(biāo)優(yōu)化等問(wèn)題，可以看出PSO 更適合云計(jì)算中的資源調(diào)度。本文在考慮到以上工作各方的優(yōu)勢(shì)后提出一種結(jié)合粒子群算法和布谷鳥(niǎo)搜索的(IPSO_CS)改進(jìn)粒子群算法進(jìn)行任務(wù)調(diào)度，經(jīng)仿真結(jié)果證明比其他PSO算法調(diào)度效果更優(yōu)。

2 云資源調(diào)度問(wèn)題

云任務(wù)調(diào)度采用映射/規(guī)約模式將任務(wù)分配到資源節(jié)點(diǎn)上，達(dá)到任務(wù)完成總時(shí)間短、服務(wù)質(zhì)量好等需求。云任務(wù)被分解為若干個(gè)相互獨(dú)立的子任務(wù)[13]后，各子任務(wù)隨機(jī)分配給并行的資源計(jì)算節(jié)點(diǎn)上執(zhí)行、整合、輸出，適合于大規(guī)模數(shù)據(jù)的處理，工作效率高。

調(diào)度模型及適應(yīng)度函數(shù)

作為云計(jì)算環(huán)境下的任務(wù)集合T={t1，t2，…，tm}，表示在當(dāng)前時(shí)刻共有m個(gè)執(zhí)行過(guò)程中不可阻斷的相互獨(dú)立任務(wù)。VM虛擬機(jī)資源集合VM={vmm1，vmm2，…，vmmn} ，n為虛擬機(jī)資源數(shù)量。在資源節(jié)點(diǎn)上預(yù)期完成時(shí)間的完成情況：

(1)

式中,etcij為相應(yīng)虛擬機(jī)處理速度下任務(wù)長(zhǎng)度的完成時(shí)間。本文云計(jì)算任務(wù)調(diào)度目標(biāo)旨在盡可能使任務(wù)完成時(shí)間time最短，任務(wù)分配到虛擬機(jī)上的總完成時(shí)間模型

(2)

任務(wù)在虛擬機(jī)上占用各種資源的執(zhí)行成本模型如下：

(3)

式中：Time(i,j)為虛擬機(jī)i上任務(wù)j的執(zhí)行時(shí)間;k為任務(wù)個(gè)數(shù);Ci為單位時(shí)間虛擬資源的費(fèi)用。這里的費(fèi)用包括3個(gè)方面：帶寬、內(nèi)存、CPU，單位為MB。

本模型為使任務(wù)完成時(shí)間Time和執(zhí)行成本C最小，采用線性加權(quán)計(jì)算的適應(yīng)度函數(shù)，分配不同指標(biāo)不同權(quán)重：

Fitness=f1Time+f2C,f1+f2=1

(4)

Fitness作為本文優(yōu)化目標(biāo)也作為適應(yīng)度函數(shù)，其值越小，算法性能越好，在實(shí)際應(yīng)用中，任務(wù)調(diào)度作為實(shí)際問(wèn)題，還需要考慮負(fù)載均衡、能耗等因素。

由于種群初始化和萊維飛行搜索的隨機(jī)性會(huì)造成結(jié)果的不穩(wěn)定性，對(duì)任務(wù)的執(zhí)行時(shí)間進(jìn)行算法穩(wěn)定性的分析判斷。方差D(n)作為樣本偏離程度即數(shù)據(jù)波動(dòng)程度可以判斷結(jié)果的穩(wěn)定性：

(5)

從執(zhí)行時(shí)間、執(zhí)行成本、穩(wěn)定性進(jìn)行多方面分析作為本文任務(wù)調(diào)度模型的判別標(biāo)準(zhǔn)。

3 IPSO_CS算法

3.1 基本粒子群算法

標(biāo)準(zhǔn)粒子群算法[14]是在動(dòng)物集群活動(dòng)行為的基礎(chǔ)上，通過(guò)最佳個(gè)體體驗(yàn)(pbest)和群體中最佳群體體驗(yàn)(gbest)在問(wèn)題求解空間中進(jìn)行演化，使得種群逐步趨于最優(yōu)?；玖Ｗ尤核惴ㄓ捎谄浜?jiǎn)單，易實(shí)現(xiàn)等優(yōu)點(diǎn)被廣泛應(yīng)用。在n維搜索空間算法模仿m個(gè)粒子的群體以基于自己和其他粒子最優(yōu)位置的基礎(chǔ)上進(jìn)行搜索飛行和位置更新，Xi=(xi1，xi2，…，xin)為第i個(gè)粒子的位置，速度Vi=(vi1，vi2，…，vin)。制定相應(yīng)適應(yīng)度函數(shù)后計(jì)算群體內(nèi)各粒子的適應(yīng)度值，以最佳個(gè)體體驗(yàn)(pbest)和群體中最佳群體體驗(yàn)(gbest)對(duì)群體內(nèi)每顆粒子的速度和位置進(jìn)行更新:

vi,j(t+1)=Wvi,j(t)+c1rand1[pi,j(t)-xi,j(t)]+

c2rand2[pg,j(t)-xi,j(t)]

(6)

xi,j(t+1)=xi,j(t)+vi,j(t+1),

(7)

j=1,2,…,n

式中：W為慣性權(quán)重，用于提高算法的收斂性;c1、c2為加速度常數(shù)控制個(gè)體和全局最佳粒子效果的特定參數(shù)；rand1、rand2為隨機(jī)數(shù)函數(shù)，用于在粒子運(yùn)動(dòng)時(shí)提供在[0，1]范圍內(nèi)的隨機(jī)量[15]，以控制粒子在搜索空間中的運(yùn)動(dòng)。

3.2 粒子編碼

在云環(huán)境中應(yīng)用粒子群算法時(shí)，待分配子任務(wù)作為離散值需要對(duì)粒子進(jìn)行編碼，通過(guò)編碼結(jié)合任務(wù)調(diào)度與粒子位置和速度，對(duì)粒子個(gè)體采用自然數(shù)編碼。設(shè)有m個(gè)任務(wù)，分配給n臺(tái)虛擬機(jī)，粒子種群規(guī)模為NP，每個(gè)粒子的位置由向量Z表示，則第i個(gè)粒子可編碼為m維向量Zi=[zi1，zi2，…，zim]，zij的取值在0～n+1之間的隨機(jī)整數(shù)，每一維分量表示分配給此任務(wù)的虛擬機(jī)，比如最優(yōu)解若為(2,5,3,…)，則表示虛擬機(jī)2接受任務(wù)1，虛擬機(jī)5接受任務(wù)2，虛擬機(jī)3接受任務(wù)3等。粒子速度則由向量v表示，第i個(gè)粒子的速度表示為vi=[vi1，vi2，…，vim]，vij為-n到n之間的隨機(jī)數(shù)。

3.3 算法改進(jìn)策略

(1) 非線性自適應(yīng)慣性權(quán)重。粒子群算法的慣性權(quán)重W作為重要的進(jìn)化參數(shù)是由Shi等提出，也叫慣性因子，決定了先前狀態(tài)粒子對(duì)當(dāng)前狀態(tài)的影響。通常采用的典型線性遞減[16]策略。在迭代前期由于需要較大的全局搜索能力，需要賦予較大的慣性因子，用以豐富種群多樣性和搜索的隨機(jī)性，而后期需要較小的慣性因子聚焦局部搜索能力。在平衡優(yōu)化粒子搜索能力時(shí)，本文采用隨迭代次數(shù)自適應(yīng)的非線性慣性權(quán)重策略，對(duì)比實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的自適應(yīng)非線性慣性權(quán)重效果更好，且隨著算法不斷迭代，慣性權(quán)重值動(dòng)態(tài)改變：

(8)

式中：W為慣性因子,其最大最小值分別為0.9、0.4；d作為迭代次數(shù)，最大值為dmax。改進(jìn)后的自適應(yīng)慣性權(quán)重從最大的慣性因子隨迭代次數(shù)自適應(yīng)降到最小慣性因子，不僅解決了后期收斂速度慢的問(wèn)題，前期更是擴(kuò)大了搜索的隨機(jī)性。

(2) 布谷鳥(niǎo)搜索。Yang等提出的布谷鳥(niǎo)搜索算法是一種受布谷鳥(niǎo)繁殖行為和levy飛行策略啟發(fā)的元啟發(fā)式全局優(yōu)化方法，是一種模擬自然界布谷鳥(niǎo)提高生存機(jī)率的繁育行為和萊維飛行特性形成的有效搜索策略。萊維飛行機(jī)制是通過(guò)隨機(jī)游動(dòng)和偏好隨機(jī)游動(dòng)的短步長(zhǎng)與長(zhǎng)步長(zhǎng)相間行走用以達(dá)到平衡整體和局部尋優(yōu)有效性的方式，在平衡尋優(yōu)方面，Long等在萊維飛行中加入了動(dòng)態(tài)自適應(yīng)步長(zhǎng)因子[17]。改進(jìn)后算法全局搜索位置和路徑的更新

(9)

式中：Xt，Xt+1為t時(shí)刻和下一時(shí)刻粒子i位置；“⊕”為點(diǎn)對(duì)點(diǎn)乘法；ɑ為改進(jìn)步長(zhǎng)因子。改進(jìn)的隨粒子變化自適應(yīng)調(diào)整搜索范圍的步長(zhǎng)因子，引導(dǎo)粒子靠近種群最優(yōu)解即精英解：

(10)

服從λ的萊維分布的隨機(jī)搜索路徑：

Levy～u=t-λ

(11)

Mantegna算法模擬隨機(jī)步長(zhǎng)十分復(fù)雜且難實(shí)現(xiàn)的萊維飛行，其數(shù)學(xué)表達(dá)如下：

(12)

式中：s為步長(zhǎng);u、v為服從正態(tài)分布的兩個(gè)隨機(jī)數(shù);β通常取1.5。

(13)

Г(x)定義如下：

(14)

服從萊維飛行的粒子運(yùn)動(dòng)軌跡模仿動(dòng)物的捕獵行為，這種行為為其隨機(jī)廣泛的搜索能力奠定了基礎(chǔ)。

(3) tent混沌改進(jìn)。為避免早熟收斂且高效優(yōu)化此改進(jìn)算法，引入tent混沌擾動(dòng)，這種自然界看似很普遍的非線性混沌現(xiàn)象，以其隨機(jī)性特點(diǎn)不重復(fù)遍歷所有狀態(tài)達(dá)到解決收斂速度慢、尋優(yōu)精度差等問(wèn)題，在保證多樣的種群的條件下，增強(qiáng)了其跳出局部最優(yōu)的情況，平衡了全局和局部的搜索能力。單梁等[18]研究表明，Tent 映射的遍歷均勻性和收斂速度均優(yōu)于 Logistic 映射，引入tent混沌擾動(dòng)粒子，當(dāng)粒子全局最優(yōu)收斂到某個(gè)值持續(xù)不變超過(guò)設(shè)置的監(jiān)測(cè)值limit時(shí)，對(duì)粒子的速度進(jìn)行擾動(dòng)，改變其搜索方向和距離，引入混沌跳出局部最優(yōu)解[19]，避免陷入早熟的僵局。本文采用以下tent混沌公式：

(15)

將產(chǎn)生的混沌擾動(dòng)量載入到粒子速度的更新中。

(16)

式中：Vi+1為擾動(dòng)后的新的個(gè)體速度;rand為服從正態(tài)分布的隨機(jī)數(shù)；Si+1為產(chǎn)生的混沌擾動(dòng)量；S為隨機(jī)產(chǎn)生的(0,1)內(nèi)的初值。設(shè)定粒子最大飛行速度Vmax代替超出上限的速度值。利用混沌函數(shù)將產(chǎn)生的新的擾動(dòng)變量附加到迭代到監(jiān)測(cè)值limit時(shí)的粒子速度上，改變粒子的運(yùn)動(dòng)方向，得到新的擾動(dòng)后的粒子狀態(tài)。

(4) IPSO_CS算法描述。IPSO_CS算法步驟如下

步驟1初始化種群大小及各項(xiàng)參數(shù)等。

步驟2依據(jù)改進(jìn)式(8)改進(jìn)迭代的自適應(yīng)權(quán)重參數(shù)w。

步驟3計(jì)算可行粒子執(zhí)行時(shí)間適應(yīng)度值，確定最佳個(gè)體體驗(yàn)pbest和群體最佳群體體驗(yàn)gbest。

步驟4將當(dāng)前適應(yīng)度值進(jìn)行比較更新pbest、gbest。

步驟5粒子迭代過(guò)程開(kāi)始，依據(jù)式(7)、(9)進(jìn)化粒子群位置。

步驟6全局最優(yōu)收斂值迭代次數(shù)超過(guò)監(jiān)測(cè)值limit，依據(jù)式(16)改進(jìn)粒子速度。

步驟7判斷是否滿(mǎn)足終止條件，否則轉(zhuǎn)步驟3。

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

4.1 仿真實(shí)驗(yàn)過(guò)程

本文采用云仿真軟件cloudsim工具包對(duì)該調(diào)度策略進(jìn)行仿真，任務(wù)數(shù)設(shè)置為[50，100，200]，迭代次數(shù)[200，500]，將改進(jìn)后的(IPSO_CS)算法與(PSO)算法、(SAPSO)算法仿真比較。表1、2分別為本文硬件實(shí)驗(yàn)環(huán)境配置參數(shù)和調(diào)度算法參數(shù)配置。

表1 硬件實(shí)驗(yàn)環(huán)境配置

表2 調(diào)度算法參數(shù)配置

4.2 仿真結(jié)果及分析

將3個(gè)算法從任務(wù)調(diào)度策略和最終結(jié)果進(jìn)行仿真對(duì)比分析。

(1) 任務(wù)調(diào)度策略分析。為確保數(shù)據(jù)的可靠性，對(duì)每組任務(wù)進(jìn)行仿真后取平均值得到最終的結(jié)果。不同任務(wù)數(shù)下任務(wù)完成時(shí)間隨迭代次數(shù)的變化如圖1(a)～(c)所示。

由仿真結(jié)果可見(jiàn)，IPSO_CS在3種不同的任務(wù)數(shù)量下收斂能力和調(diào)度尋優(yōu)能力都比PSO和SAPSO更好。SAPSO算法完成任務(wù)總時(shí)間比IPSO_CS和PSO相差較多，圖1(a)所示在任務(wù)數(shù)量較少迭代次數(shù)200內(nèi)，SAPSO沒(méi)有趨于穩(wěn)定，算法收斂和尋優(yōu)效果差，PSO和IPSO_CS總體的任務(wù)完成時(shí)間非常貼近，迭代初期100次左右IPSO_CS趨于平緩，PSO在迭代140時(shí)趨于平緩。在結(jié)合了CS搜索后粒子位置活力更活躍，加快了尋優(yōu)的能力。圖1(b)為改進(jìn)算法在后期較好的尋優(yōu)能力，在迭代次數(shù)250之前與PSO算法接近，但SAPSO算法效果整體較差。圖1(c)展示了在較大規(guī)模下，3種算法的收斂和尋優(yōu)能力，在迭代300次左右，3種算法都趨于平穩(wěn)，在粒子搜索增加CS的動(dòng)物捕獵行為的模仿后IPSO_CS除了在較早的迭代初期調(diào)度效果不佳之外，總體優(yōu)勢(shì)在迭代50次后體現(xiàn)出來(lái)。

(a) 任務(wù)數(shù)50完成時(shí)間

不同任務(wù)數(shù)量下任務(wù)完成成本對(duì)比如圖2所示。

執(zhí)行成本的相差不是太大，尤其是IPSO_CS與PSO，但是IPSO_CS在總的費(fèi)用上要優(yōu)于PSO和SAPSO，也就可以看出其分配方案更合理，效果更好。

(2)仿真結(jié)果穩(wěn)定性分析。除任務(wù)完成時(shí)間和費(fèi)用對(duì)比，對(duì)50個(gè)任務(wù)和200個(gè)任務(wù)的完成時(shí)間選取8組值繪出圖3、4所示的穩(wěn)定性對(duì)比[20]，觀察得出IPSO_CS曲線波動(dòng)較小且總體值小于PSO和SAPSO，說(shuō)明種群初始化和萊維飛行搜索的隨機(jī)性對(duì)IPSO_CS的影響較小，本文方案在執(zhí)行時(shí)間上相對(duì)穩(wěn)定。

圖3 任務(wù)數(shù)50執(zhí)行時(shí)間穩(wěn)定性對(duì)比

圖4 任務(wù)數(shù)200執(zhí)行時(shí)間穩(wěn)定性對(duì)比

綜上，通過(guò)不同規(guī)模條件下的仿真，本文的優(yōu)化IPSO_CS調(diào)度算法相比于PSO和SAPSO縮短了系統(tǒng)任務(wù)調(diào)度完成總時(shí)間和費(fèi)用，在算法收斂、搜索能力、穩(wěn)定性、調(diào)度效果方面都取得了較好效果，總體上保證了樣本多樣性，在資源調(diào)度方面尋優(yōu)更好。

5 結(jié) 語(yǔ)

傳統(tǒng)PSO在進(jìn)行云資源調(diào)度時(shí)容易出現(xiàn)早熟收斂、搜索效率低、結(jié)果隨機(jī)等問(wèn)題。本文提出的一種基于標(biāo)準(zhǔn)粒子群算法改進(jìn)的資源調(diào)度算法(IPSO_CS)，在增加粒子位置變化活力搜索精英解以及打破局部最優(yōu)的狀態(tài)，縮短任務(wù)執(zhí)行時(shí)間和成本上，比標(biāo)準(zhǔn) PSO 算法和SAPSO算法更好，調(diào)度策略上更優(yōu)。仿真結(jié)果表明，其可以很好地解決算法的早熟收斂、搜索效率低、結(jié)果隨機(jī)等問(wèn)題，相較與其他 PSO 具有更優(yōu)的性能。本文所提出的調(diào)度策略能夠較好的解決云計(jì)算中資源調(diào)度分配問(wèn)題。