趙昱，惠曉濱，高楊軍，郭慶

（空軍工程大學(xué)裝備管理與安全工程學(xué)院，西安710051）

基于改進(jìn)QPSO算法的云計(jì)算資源調(diào)度策略研究

趙昱，惠曉濱，高楊軍，郭慶

（空軍工程大學(xué)裝備管理與安全工程學(xué)院，西安710051）

資源調(diào)度問(wèn)題是云計(jì)算研究的一個(gè)重要方向。針對(duì)傳統(tǒng)量子粒子群算法的不足，提出了一種改進(jìn)量子粒子算法，并將其應(yīng)用于云計(jì)算資源調(diào)度策略。首先，建立了云計(jì)算資源調(diào)度問(wèn)題的模型，并將資源調(diào)度任務(wù)完成的時(shí)間作為適應(yīng)度函數(shù)。隨后采用自適應(yīng)機(jī)制，通過(guò)改變粒子位置更新的慣性權(quán)值，提高了算法的全局搜索能力，加快了收斂速度。最后通過(guò)實(shí)驗(yàn)仿真對(duì)該算法進(jìn)行了測(cè)試。實(shí)驗(yàn)表明，該算法能更好更快地找到云計(jì)算資源調(diào)度方案，使資源分配更加合理高效。

云計(jì)算，資源調(diào)度，量子粒子群算法，慣性權(quán)值

0 引言

近年來(lái)，隨著互聯(lián)網(wǎng)網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，互聯(lián)網(wǎng)所需要處理的業(yè)務(wù)量也隨之快速增長(zhǎng)。人們對(duì)計(jì)算服務(wù)質(zhì)量要求越來(lái)越高，單一計(jì)算平臺(tái)難以滿足人們的要求，在此背景下云計(jì)算應(yīng)運(yùn)而生［1-2］。云計(jì)算集成了分布式計(jì)算和網(wǎng)格計(jì)算等多種技術(shù)，可以將分布于不同物理域的服務(wù)器通過(guò)邏輯維連接成一個(gè)巨大的資源池，通過(guò)虛擬技術(shù)等將實(shí)現(xiàn)用戶任務(wù)的快速完成。資源管理是云計(jì)算的核心技術(shù)，其效率的高低直接影響云計(jì)算服務(wù)質(zhì)量，因此，云計(jì)算資源調(diào)度一直是云計(jì)算研究領(lǐng)域中的重點(diǎn)和難點(diǎn)［3］。

針對(duì)云計(jì)算資源調(diào)度優(yōu)化問(wèn)題，國(guó)內(nèi)外學(xué)者進(jìn)行了大量深入的研究。云計(jì)算資源調(diào)度實(shí)際上是一種多約束、多目標(biāo)優(yōu)化問(wèn)題，是一類NP難題。為此，學(xué)者們提出了許多算法。如文獻(xiàn)［4］提出采用遺傳算法求解云計(jì)算資源調(diào)度問(wèn)題，相對(duì)于傳統(tǒng)調(diào)度算法，其獲得了較好的服務(wù)質(zhì)量；文獻(xiàn)［5］以任務(wù)完成時(shí)間、系統(tǒng)吞吐量作為目標(biāo)構(gòu)建云計(jì)算資源調(diào)度模型，然后采用蟻群算法進(jìn)行求解，取得了不錯(cuò)的調(diào)度效果。在這些算法中，粒子群算法具有參數(shù)設(shè)置少，全局搜索能力強(qiáng)等優(yōu)點(diǎn)，成為了云計(jì)算資源調(diào)度研究中的一個(gè)重要的方向，然而其易陷入局部最優(yōu)和出現(xiàn)“早熟”的現(xiàn)象是其在計(jì)算諸多優(yōu)化問(wèn)題中難以克服的缺點(diǎn)。量子粒子群算法是將量子力學(xué)概念與粒子群算法相結(jié)合，通過(guò)解薛定諤方程和蒙特卡羅估計(jì)等方法，以波函數(shù)的形式描述粒子在空間內(nèi)的運(yùn)動(dòng)狀態(tài)，通過(guò)波函數(shù)塌縮來(lái)確定粒子的位置。實(shí)驗(yàn)證明，量子粒子群算法相對(duì)于標(biāo)準(zhǔn)粒子群算法具有更好的計(jì)算性能，在尋找最優(yōu)解和避免陷入局部最優(yōu)等方面更加適合求解優(yōu)化問(wèn)題。

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

云計(jì)算系統(tǒng)在保證滿足用戶高質(zhì)量服務(wù)的同時(shí)，盡可能地減少服務(wù)時(shí)間，使用戶可以在較短的時(shí)間內(nèi)獲得計(jì)算結(jié)果或數(shù)據(jù)。從服務(wù)提供者角度來(lái)看，云計(jì)算的系統(tǒng)資源是有限的，資源競(jìng)爭(zhēng)是不可避免的，如何能夠減少資源競(jìng)爭(zhēng)，或者使各個(gè)計(jì)算節(jié)點(diǎn)達(dá)到負(fù)載均衡，是整個(gè)服務(wù)過(guò)程中需要考慮的問(wèn)題。因此，只有通過(guò)資源調(diào)度將用戶的需求任務(wù)分配到合適的計(jì)算資源上，才能滿足以上兩方面的要求。在資源調(diào)度的過(guò)程中，模型可由以下幾個(gè)要素組成:

（1）任務(wù)集合S={s1，s2，…，sn}，表示n個(gè)相互獨(dú)立且不可再分的任務(wù)組成的集合。

（2）虛擬資源集合V={v1，v2，…，vn}，表示云計(jì)算資源池中所包含的虛擬計(jì)算資源，其中每個(gè)計(jì)算資源vi采用如下形式描述:

式中，CPU表示內(nèi)核數(shù)，MEMORY表示內(nèi)存大小，DISK表示磁盤空間大小。

基于以上要素，計(jì)算資源調(diào)度的目標(biāo)是通過(guò)對(duì)任務(wù)集中的各個(gè)任務(wù)進(jìn)行合理的分配資源，并且對(duì)各個(gè)任務(wù)的執(zhí)行進(jìn)行排序，從而使得總?cè)蝿?wù)的執(zhí)行達(dá)到最優(yōu)。為簡(jiǎn)化模型，本文對(duì)模型進(jìn)行如下簡(jiǎn)化:

①虛擬機(jī)的性能滿足任一任務(wù)的要求；

②每個(gè)任務(wù)只能由一個(gè)虛擬計(jì)算資源執(zhí)行；

③不考慮任務(wù)傳輸時(shí)間對(duì)模型優(yōu)化的影響。

由于云計(jì)算系統(tǒng)的計(jì)算并行性，多個(gè)任務(wù)可以同時(shí)在數(shù)據(jù)中心的各個(gè)節(jié)點(diǎn)上執(zhí)行，對(duì)于一個(gè)調(diào)度方案D，完成n個(gè)任務(wù)的時(shí)間為執(zhí)行時(shí)間最長(zhǎng)的虛擬機(jī)，其數(shù)學(xué)表達(dá)式為:

其中，n為任務(wù)數(shù)量；m為云計(jì)算資源的數(shù)量。

2 量子粒子群算法（QPSO）

粒子群優(yōu)化算法具有簡(jiǎn)單易行、易于理解等優(yōu)點(diǎn)，從而受到了眾多學(xué)者的關(guān)注。但在實(shí)際應(yīng)用中也表現(xiàn)出了容易早熟、全局尋優(yōu)能力差等特點(diǎn)。2004年，Sun等從量子力學(xué)的角度出發(fā)，提出了一種新的粒子進(jìn)化模型，由于粒子是以概率波的形式出現(xiàn)在空間，使得算法可以在整個(gè)可行區(qū)域內(nèi)搜索最佳解，所以它的全局搜索能力遠(yuǎn)勝于標(biāo)準(zhǔn)粒子群算法。

首先假定系統(tǒng)是一個(gè)量子粒子系統(tǒng)，假設(shè)粒子的運(yùn)動(dòng)空間為N維，m為種群數(shù)量，t為迭代次數(shù)。在搜索空間中，第i個(gè)粒子的位置是xi=（xi1，xi1，…xiN），其中i=1，2…m。將xi代入目標(biāo)函數(shù)即可算出其適應(yīng)值。記第i個(gè)粒子在第t次迭代中搜索到的局部最優(yōu)位置為，整個(gè)粒子群搜索到的最優(yōu)位置為其中g(shù)代表處于全局最好位置粒子的下標(biāo)。

在量子空間中，利用波函數(shù)ψ（x，t）描述粒子的狀態(tài)，通過(guò)求解薛定諤方程得到粒子的概率密度函數(shù)和概率分布函數(shù)，而粒子在空間中的具體位置則由蒙特卡羅反變換得到，有

最后，得到量子粒子群算法的進(jìn)化方程為:

ξ為慣性權(quán)值，也是QPSO算法中唯一的一個(gè)收斂參數(shù)，其取值可以固定不變，也可引入自適應(yīng)機(jī)制動(dòng)態(tài)調(diào)節(jié)，一般按照下式取值:

式中，tmax為最大迭代次數(shù)，t表示當(dāng)前迭代次數(shù)。

因此，標(biāo)準(zhǔn)的量子粒子群算法流程如下:

步驟1:初始化群體規(guī)模、最大迭代次數(shù)、解空間維數(shù)以及粒子位置；

步驟2:分配初始化粒子局部最優(yōu)和全局最優(yōu)值；

步驟3:優(yōu)化過(guò)程，按照式（3）～式（5）更新QPSO算法中的所有粒子；

步驟4:計(jì)算群體當(dāng)前的全局最優(yōu)位置，即更新pi和pg；

步驟5:根據(jù)約束條件進(jìn)行判斷，當(dāng)前所求的解是否滿足，若滿足輸出最優(yōu)解，否則跳到步驟2繼續(xù)搜索直到滿足條件或達(dá)到最大迭代次數(shù)為止。

3 基于改進(jìn)QPSO算法的云計(jì)算資源調(diào)度策略

通過(guò)上節(jié)粒子更新計(jì)算公式可知，慣性權(quán)值ξ的選擇關(guān)系到整個(gè)算法的收斂性和搜索能力，因此，如何選擇ξ成為QPSO算法的關(guān)鍵。對(duì)于一個(gè)確定的粒子來(lái)說(shuō)，進(jìn)化速度的快慢，說(shuō)明粒子越靠近或越遠(yuǎn)離粒子群的當(dāng)前最佳位置，即粒子的搜索范圍也隨之縮小或增加了。所以為了提高算法性能，對(duì)于靠近粒子群當(dāng)前最佳位置的點(diǎn)，ξ應(yīng)該增大以使粒子盡量發(fā)散；對(duì)于遠(yuǎn)離當(dāng)前最佳位置的點(diǎn)，ξ應(yīng)該減小使粒子收斂。為此本文提出了一種自適應(yīng)機(jī)制的ξ選取方法，即:

f（t）由下式確定:

考慮云計(jì)算調(diào)度策略的任務(wù)完成時(shí)間，本文定義所有任務(wù)完成時(shí)間為適應(yīng)度函數(shù)，其數(shù)學(xué)表達(dá)式如下:

因此，基于改進(jìn)QPSO算法的云計(jì)算資源調(diào)度策略流程為:

步驟1:初始化群體規(guī)模、最大迭代次數(shù)、解空間維數(shù)以及粒子位置；

步驟2:計(jì)算各個(gè)粒子的適應(yīng)度函數(shù)值，并且確定初始位置各個(gè)粒子的局部最優(yōu)值和全局最優(yōu)值；

步驟3:優(yōu)化過(guò)程，按照式（6）確定迭代慣性權(quán)值的大小，并通過(guò)式（3）～式（5）更新QPSO算法中的所有粒子；

步驟4:計(jì)算群體當(dāng)前的全局最優(yōu)位置和各個(gè)粒子局部最優(yōu)位置的適應(yīng)度函數(shù)值，與前一次迭代的適應(yīng)度函數(shù)比較，根據(jù)比較結(jié)果更新pg和pi值；

步驟5:根據(jù)約束條件進(jìn)行判斷，當(dāng)前所求的解是否滿足，若滿足輸出最優(yōu)解，否則跳到步驟2，繼續(xù)搜索直到滿足條件或達(dá)到最大迭代次數(shù)為止。

綜上可知，改進(jìn)QPSO算法的云計(jì)算資源調(diào)度流程圖，如圖1所示。

圖1 本文算法的云計(jì)算資源調(diào)度模型求解流程

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

為了測(cè)試改進(jìn)后的QPSO算法在云計(jì)算資源調(diào)度中的應(yīng)用效果，本文采用Cloudsim作為實(shí)驗(yàn)?zāi)M平臺(tái)，在一臺(tái)處理器為Inter（R）Core（TM）i7-4710MQ，內(nèi)存為8 G，操作系統(tǒng)為Windows 8的計(jì)算機(jī)上進(jìn)行仿真實(shí)驗(yàn)。

實(shí)驗(yàn)中，選擇標(biāo)準(zhǔn)粒子群算法（PSO）、量子粒子群算法（QPSO）和本文算法進(jìn)行了對(duì)比。在相同實(shí)驗(yàn)條件下，3種算法的參數(shù)設(shè)置為:種群規(guī)模為10，PSO算法中c1和c2都為2，所有算法迭代次數(shù)為500次。

當(dāng)云計(jì)算資源數(shù)量為8個(gè)時(shí)，將10個(gè)～100個(gè)不同的任務(wù)分配到資源節(jié)點(diǎn)進(jìn)行計(jì)算，其中，虛擬機(jī)參數(shù)為:ram=512 MB；imagesSize=10 000 MB，不同虛擬機(jī)MIPS為250～2 000之間的隨機(jī)整數(shù)。任務(wù)通過(guò)不同大小的待處理數(shù)據(jù)來(lái)設(shè)定。采用PSO、QPSO和本文算法對(duì)資源調(diào)度方案進(jìn)行求解，各種方案的任務(wù)完成時(shí)間如圖2所示。

圖2 任務(wù)數(shù)量增加的任務(wù)完成時(shí)間

對(duì)圖2任務(wù)完成時(shí)間進(jìn)行分析，可以得到如下結(jié)論:當(dāng)任務(wù)數(shù)量較少時(shí)，3種算法完成任務(wù)的時(shí)間差距很??；隨著任務(wù)數(shù)量的增加，3種算法得到的最優(yōu)調(diào)度方案完成時(shí)間差距逐步增大。當(dāng)任務(wù)數(shù)量達(dá)到100時(shí)，QPSO算法與本文算法相差400 ms，而標(biāo)準(zhǔn)粒子群算法與本文相差700 ms。從以上趨勢(shì)分析，對(duì)于固定計(jì)算資源數(shù)量的數(shù)據(jù)中心，本文算法較傳統(tǒng)算法更具優(yōu)勢(shì)，同時(shí)任務(wù)數(shù)量越多，優(yōu)勢(shì)越明顯。

當(dāng)任務(wù)數(shù)量為100時(shí)，將這100個(gè)任務(wù)分配給10個(gè)～30個(gè)計(jì)算資源進(jìn)行計(jì)算，虛擬機(jī)參數(shù)、任務(wù)參數(shù)和算法參數(shù)同上，采用PSO、QPSO和本文算法對(duì)資源調(diào)度方案進(jìn)行求解，各種方案的任務(wù)完成時(shí)間如圖3所示。

圖3 資源數(shù)量增加的任務(wù)完成時(shí)間

從圖3可知，當(dāng)任務(wù)數(shù)量相同時(shí)，通過(guò)3種算法的資源調(diào)度來(lái)完成任務(wù)，隨著計(jì)算資源的增加，QPSO算法與本文算法明顯優(yōu)于標(biāo)準(zhǔn)粒子群算法，而本文算法略優(yōu)于QPSO，因此，本文算法更適合于云計(jì)算資源調(diào)度。

最后，統(tǒng)計(jì)了100個(gè)任務(wù)在分配給8個(gè)計(jì)算資源時(shí)的節(jié)點(diǎn)負(fù)載，3種算法分配任務(wù)的負(fù)載圖如圖4。圖4表明，PSO算法在進(jìn)行資源分配時(shí)節(jié)點(diǎn)負(fù)載最不均衡，其次是QPSO，本文算法相對(duì)與前兩種算法性能更優(yōu)；對(duì)比算法均不同程度地出現(xiàn)了處理能力強(qiáng)的資源分配到較少的任務(wù)，而處理能力弱的資源分配到了較多任務(wù)的現(xiàn)象。本文算法具有易于實(shí)現(xiàn)、不易陷入局部最優(yōu)的特點(diǎn)，因此，獲得了更為理想的調(diào)度方案。

圖4 計(jì)算資源負(fù)載情況

5 結(jié)論

針對(duì)云計(jì)算環(huán)境下資源調(diào)度的NP難題，提出了一種改進(jìn)的量子粒子群算法，通過(guò)在迭代中更新唯一的參數(shù)慣性權(quán)值，加強(qiáng)了QPSO算法的全局搜索能力。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的QPSO在性能上優(yōu)于粒子群算法和標(biāo)準(zhǔn)量子粒子群算法，可以快速找到云計(jì)算資源調(diào)度方案，提高了資源利用率，為云計(jì)算資源調(diào)度策略提供了一個(gè)新的方法。

［1］RAJKUMAR B，CHEE S Y，SRIKUMAR V，et al.Cloud computing and emerging IT platforms:vision，hype，and reality for delivering computing as the 5th utility［J］.Future Generations Computer Systems，2009，25（6）:599-616.

［2］MICHAEL A，ARMANDO F，REAN G.Above the clouds:a berkeley view of cloud computing［R］.EECS，2009.

［3］袁浩，李昌兵.基于社會(huì)力群智能優(yōu)化算法的云計(jì)算資源調(diào)度［J］.計(jì)算機(jī)科學(xué)，2015，42（4）:206-208，243.

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

［5］肖明清，楊召，薛輝輝，等.云計(jì)算及其在測(cè)試領(lǐng)域的應(yīng)用探索［J］.空軍工程大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，16（1）:50-55.

［6］劉靜，須文波，孫俊，等.基于量子粒子群算法求解整數(shù)規(guī)劃［J］.計(jì)算機(jī)應(yīng)用研究，2007，24（3）:79-81，105.

［7］苑帥，沈西挺，邵娜娜，等.引入人工蜂群搜索算子的QPSO算法的改進(jìn)實(shí)現(xiàn)［J］.計(jì)算機(jī)工程與應(yīng)用，2016，52（15）:29-33.

［8］徐文忠，彭志平，左敬龍，等.基于遺傳算法的云計(jì)算資源調(diào)度策略研究［J］.計(jì)算機(jī)測(cè)量與控制，2015，23（5）:1653-1656.

［9］周文俊，曹健.基于預(yù)測(cè)及蟻群算法的云計(jì)算資源調(diào)度策略［J］.計(jì)算機(jī)仿真，2012，29（9）:239-242，246.

［10］劉衛(wèi)寧，靳洪兵，劉波，等.基于改進(jìn)量子遺傳算法的云計(jì)算資源調(diào)度［J］.計(jì)算機(jī)應(yīng)用，2013，33（8）:2151-2153.

［11］楊單，李超鋒，楊健，等.基于改進(jìn)混沌螢火蟲算法的云計(jì)算資源調(diào)度［J］.計(jì)算機(jī)工程，2015，41（2）:17-20.

［12］黃宇，韓璞，劉長(zhǎng)良，等.改進(jìn)量子粒子群算法及其在系統(tǒng)辨識(shí)中的應(yīng)用［J］.中國(guó)電機(jī)工程學(xué)報(bào)，2011，31（20）:114-120.

Research on Cloud Computing Resource Scheduling Strategy Based on Improved QPSO Algorithm

ZHAO Yu，HUI Xiao-bin，GAO Yang-jun，GUO Qing
（Material Management and Safety Engineering College，Air Force Engineering University，Xi’an 710051，China）

Resource scheduling problem is an important direction of cloud computing research. Aiming at the shortcomings of the traditional quantum particle swarm optimization algorithm，this paper proposes a quantum particle swarm algorithm based on improved.Cloud computing resource scheduling model is established firstly，and then the fitness function of the model is defined.Soon afterwards，by using the adaptive mechanism，the inertia of particle position update weights to improve the global search ability of the algorithm is changed，and the convergence speed is accelerated.Finally the simulation of the algorithm is tested by experiments.And the experimental results show that this method can better and faster to find cloud computing resource scheduling scheme，make resource allocation more reasonable and efficient.

cloud computing，resource scheduling，quantum particle swarm optimization，inertia weight

TP393

A

1002-0640（2017）04-0014-04

2016-02-05

2016-03-28

國(guó)家自然科學(xué)青年基金資助（71501184）

趙昱（1993-），男，山西運(yùn)城人，碩士研究生。研究方向：信息系統(tǒng)工程與智能決策。