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

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

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

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

2 量子粒子群算法（QPSO）

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

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

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

最后，得到量子粒子群算法的進化方程為:

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

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

因此，標準的量子粒子群算法流程如下:

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

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

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

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

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

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

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

f（t）由下式確定:

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

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

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

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

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

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

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

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

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

4 實驗與仿真

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

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

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

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

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

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

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

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

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

圖4 計算資源負載情況

5 結(jié)論

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

［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］袁浩，李昌兵.基于社會力群智能優(yōu)化算法的云計算資源調(diào)度［J］.計算機科學，2015，42（4）:206-208，243.

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

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

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

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

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

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

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

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

［12］黃宇，韓璞，劉長良，等.改進量子粒子群算法及其在系統(tǒng)辨識中的應(yīng)用［J］.中國電機工程學報，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

國家自然科學青年基金資助（71501184）

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