基于量子粒子群優(yōu)化算法的云計(jì)算負(fù)載均衡分析*

李祥琴， 羅傳軍， 楊 利

(1. 荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院， 湖北 荊門 448000； 2. 湖北省荊門市電子政務(wù)信息中心， 湖北 荊門 448000； 3. 池州學(xué)院 大數(shù)據(jù)與人工智能學(xué)院， 安徽 池州 247000)

隨著計(jì)算機(jī)應(yīng)用范圍的不斷拓寬，每天會(huì)涌入大量數(shù)據(jù)，單機(jī)運(yùn)行速度已經(jīng)達(dá)到了瓶頸，無法滿足海量數(shù)據(jù)處理的要求，在此背景下，云計(jì)算技術(shù)應(yīng)運(yùn)而生[1].云計(jì)算技術(shù)是多種技術(shù)的集成，主要包括：網(wǎng)格計(jì)算技術(shù)、分布式處理技術(shù)、并行計(jì)算及人工智能技術(shù)，其基于互聯(lián)網(wǎng)技術(shù)將各種不同的資源打包成服務(wù)，通過收費(fèi)方式提供給用戶[2-3].由于云計(jì)算節(jié)點(diǎn)資源數(shù)量有限，且比較昂貴，因此需盡量使云計(jì)算資源上負(fù)載保持一種動(dòng)態(tài)均衡，故云計(jì)算資源利用率達(dá)到最大化是云計(jì)算領(lǐng)域中的一個(gè)重要研究方向[4-5].

針對云計(jì)算負(fù)載均衡問題，出現(xiàn)了許多類型的云計(jì)算負(fù)載均衡方法[6].最初，人們采用窮舉式搜索算法對負(fù)載均衡問題進(jìn)行求解[7]，但當(dāng)云計(jì)算資源負(fù)載規(guī)模較大時(shí)，計(jì)算復(fù)雜度會(huì)呈指數(shù)形式增長，在短時(shí)間內(nèi)很難搜索最優(yōu)云計(jì)算負(fù)載均衡方案，不能滿足現(xiàn)代海量數(shù)據(jù)處理的要求.隨著群智能技術(shù)研究的不斷深入，出現(xiàn)了許多類型群智能優(yōu)化算法，它們模擬自然界生物的群體搜索特性對問題進(jìn)行求解，如基于禁忌搜索算法、基于蝙蝠算法、基于蟻群算法及基于貓群優(yōu)化算法的云計(jì)算負(fù)載均衡方法等[8-10].上述算法均需建立云計(jì)算負(fù)載均衡問題的相關(guān)數(shù)學(xué)模型，然后找到云計(jì)算資源負(fù)載最優(yōu)分配方案[11-12]，故在實(shí)際應(yīng)用中，這些群智能優(yōu)化算法存在搜索效率低、局部最優(yōu)解搜索停滯、求解精度低等問題[12].

針對當(dāng)前云計(jì)算負(fù)載均衡方法的節(jié)點(diǎn)出現(xiàn)過負(fù)載或者長期空閑的局限性，本文設(shè)計(jì)了基于量子粒子群優(yōu)化算法[13]的云計(jì)算負(fù)載均衡方法，并與其他群智能優(yōu)化算法進(jìn)行了仿真對比實(shí)驗(yàn)，證明了云計(jì)算負(fù)載均衡方法的可行性和優(yōu)越性.量子粒子群優(yōu)化算法能夠避免其他群智能優(yōu)化算法在求解過程中存在的缺陷，提高了云計(jì)算節(jié)點(diǎn)資源的利用率，使節(jié)點(diǎn)負(fù)載更加均衡，能夠獲得更為理想的云計(jì)算負(fù)載方案.

1 云計(jì)算系統(tǒng)負(fù)載均衡

1.1 云計(jì)算系統(tǒng)基本結(jié)構(gòu)

云計(jì)算系統(tǒng)是一種為了解決海量任務(wù)的并行式處理系統(tǒng)，與單節(jié)點(diǎn)計(jì)算機(jī)系統(tǒng)相比，其工作模式具有比較明顯的差異，云計(jì)算將服務(wù)器、存儲(chǔ)設(shè)備、網(wǎng)絡(luò)、打印機(jī)等抽象成資源，任何用戶都可按自己的需求申請相應(yīng)類型服務(wù)，能夠滿足不同用戶服務(wù)質(zhì)量要求.云計(jì)算系統(tǒng)的基本結(jié)構(gòu)如圖1所示.

圖1 云計(jì)算系統(tǒng)的基本結(jié)構(gòu)Fig.1 Basic structure of cloud computing system

1.2 云計(jì)算系統(tǒng)負(fù)載均衡數(shù)學(xué)模型

設(shè)用戶任務(wù)集合為S={s1，s2，…，sm}，其中，si為第i個(gè)用戶的任務(wù)；云計(jì)算系統(tǒng)所有節(jié)點(diǎn)資源組成的集合為R={r1，r2，…，rl}，其中，rj為節(jié)點(diǎn)資源的虛擬設(shè)備，其與實(shí)際相關(guān)物理設(shè)備相對應(yīng)；云計(jì)算中具體物理設(shè)備集合為D={d1，d2，…，dn}，dk為第k個(gè)物理設(shè)備.以上三個(gè)參數(shù)的相互關(guān)聯(lián)集合可表示為

C={S，R，D，Mtr，Mrd}

(1)

式中：Mrd為云計(jì)算資源與物理設(shè)備之間的映射關(guān)系；Mtr為用戶任務(wù)與云計(jì)算系統(tǒng)資源之間的映射關(guān)系.

設(shè)第i個(gè)用戶的任務(wù)被分配到第j個(gè)資源上，云計(jì)算節(jié)點(diǎn)資源采用第k個(gè)物理設(shè)備處理該任務(wù)，任務(wù)在相應(yīng)物理設(shè)備處理時(shí)間為E(si，Mtr，dk)，物理設(shè)備dk開始執(zhí)行第i個(gè)用戶任務(wù)時(shí)間為ST(dk)，則第i個(gè)用戶的任務(wù)完成時(shí)間為

F(si，Mtr，dk)=ST(dk)+E(si，Mtr，dk)

(2)

物理設(shè)備dk上任務(wù)完成時(shí)間之和為

(3)

式中，cik=1為si在dk上執(zhí)行；否則cik=0.云計(jì)算負(fù)載均衡求解就是找到一個(gè)用戶任務(wù)完成時(shí)間最少的方案，即

(4)

2 負(fù)載均衡方法

2.1 標(biāo)準(zhǔn)粒子群優(yōu)化算法

(5)

(6)

式中：w為權(quán)值；τ1、τ2為加速因子；β為搜索時(shí)間間隔.

2.2 量子粒子群優(yōu)化算法

標(biāo)準(zhǔn)粒子群優(yōu)化算法與其他智能優(yōu)化算法一樣，存在不同程度的局限性，如存在搜索后期效率低、找最優(yōu)解的概率低等問題.為了克服標(biāo)準(zhǔn)粒子群優(yōu)化算法的缺陷，提出了量子粒子群優(yōu)化算法.

(7)

在量子力學(xué)中，粒子運(yùn)動(dòng)的動(dòng)力學(xué)方程為

(8)

對量子粒子群優(yōu)化算法的粒子收斂行為進(jìn)行分析可知：算法中存在一個(gè)以點(diǎn)P為中心的某種形式的吸引勢，把點(diǎn)P稱為粒子的吸引子.通過在吸引子中建立一維勢阱，推導(dǎo)出粒子在勢阱中的定態(tài)薛定諤方程，解得粒子出現(xiàn)在相對吸引子位置Y的概率密度函數(shù)為

(9)

式中，L為粒子與種群平均最優(yōu)解間的距離.

引入蒙特卡羅隨機(jī)模擬方法測量粒子的位置，粒子在以P點(diǎn)為中心的一維勢阱中運(yùn)動(dòng)，其位置可表示為

(10)

式中：u為一個(gè)隨機(jī)數(shù)；XP為當(dāng)前P點(diǎn)位置.

根據(jù)式(5)、(6)和(10)可以得到具有量子行為的粒子進(jìn)化方程，即

(11)

為了測試量子粒子群優(yōu)化算法(QPSO)的優(yōu)越性，本文采用標(biāo)準(zhǔn)粒子群優(yōu)化算法(PSO)進(jìn)行了對比分析.選用的標(biāo)準(zhǔn)測試函數(shù)為Griewank和Rosenbrock，其定義分別為

(12)

(13)

圖2為兩種算法在不同測試函數(shù)下的對比分析結(jié)果.由圖2可知，相對于粒子群優(yōu)化算法，量子粒子群優(yōu)化算法能夠找到更優(yōu)的解.

圖2 量子粒子群算法和粒子群算法的性能對比Fig.2 Performance comparison between QPSO algorithm and PSO algorithm

2.3 云計(jì)算負(fù)載均衡方法

本文引入量子粒子群優(yōu)化算法對云計(jì)算負(fù)載均衡問題的數(shù)學(xué)模型進(jìn)行求解，具體步驟如下：

1) 建立云計(jì)算系統(tǒng)，確定各種云計(jì)算資源的數(shù)量、云計(jì)算任務(wù)數(shù)量以及各種云計(jì)算資源的處理能力；

2) 收集用戶任務(wù)，對云計(jì)算用戶調(diào)度任務(wù)進(jìn)行分解，劃分為不同大小的云計(jì)算任務(wù)；

3) 根據(jù)云計(jì)算任務(wù)、云計(jì)算資源以及物理設(shè)備之間的對應(yīng)關(guān)系，以用戶任務(wù)完成時(shí)間最短為目標(biāo)函數(shù)，構(gòu)建云計(jì)算負(fù)載均衡問題的數(shù)學(xué)模型；

4) 引入量子粒子群優(yōu)化算法對云計(jì)算負(fù)載均衡的數(shù)學(xué)模型解進(jìn)行搜索，找到最優(yōu)的云計(jì)算負(fù)載均衡方案.

3 云計(jì)算負(fù)載均衡方法性能驗(yàn)證

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

為了分析量子粒子群優(yōu)化算法云計(jì)算負(fù)載均衡方法的性能，采用Matlab 2017工具箱編程云計(jì)算負(fù)載均衡程序，云計(jì)算系統(tǒng)中的節(jié)點(diǎn)資源類型為5類.量子粒子群優(yōu)化算法的參數(shù)設(shè)置為：量子粒子數(shù)為20，搜索擴(kuò)張系數(shù)為0.25，最大迭代次為300.

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

3.2.1 任務(wù)完成時(shí)間對比

選擇文獻(xiàn)[14]和文獻(xiàn)[15]的云計(jì)算負(fù)載均衡方法進(jìn)行對比實(shí)驗(yàn).每一種云計(jì)算負(fù)載均衡方法均進(jìn)行5次仿真實(shí)驗(yàn)，以增加實(shí)驗(yàn)結(jié)果的可靠性，3種云計(jì)算負(fù)載均衡方法的任務(wù)完成時(shí)間對比結(jié)果如圖3所示.由圖3可知，基于量子粒子群優(yōu)化算法的云計(jì)算負(fù)載均衡方法的任務(wù)完成時(shí)間最短，而文獻(xiàn)[14]和文獻(xiàn)[15]的云計(jì)算負(fù)載均衡方法的任務(wù)完成時(shí)間均有一定的延長，量子粒子群優(yōu)化算法提升了任務(wù)完成的速度.

圖3 云計(jì)算負(fù)載均衡方法的負(fù)載完成時(shí)間Fig.3 Load completion time of load balancing methods for cloud computing

3.2.2 資源負(fù)載分配結(jié)果對比

3種云計(jì)算負(fù)載均衡方法的資源負(fù)載分布結(jié)果對比如圖4所示.根據(jù)圖4結(jié)果可知，量子粒子群優(yōu)化算法的云計(jì)算資源負(fù)載十分均衡，出現(xiàn)少量的“過負(fù)載”或者“空負(fù)載”現(xiàn)象；而文獻(xiàn)[14]和文獻(xiàn)[15]的云計(jì)算負(fù)載均衡方法均出現(xiàn)了大量“過負(fù)載”或者“空負(fù)載”現(xiàn)象，這表明量子粒子群優(yōu)化算法可以保證云計(jì)算負(fù)載均衡，提高了云計(jì)算資源利用率.

3.2.3 最優(yōu)方案迭代次數(shù)對比

量子粒子群優(yōu)化算法與文獻(xiàn)[14]和文獻(xiàn)[15]的云計(jì)算負(fù)載均衡方法找到最優(yōu)方案的迭代次數(shù)對比如表1所示.由表1可知，量子粒子群優(yōu)化算法找到最優(yōu)方案的迭代次數(shù)均值明顯少于文獻(xiàn)[14]和文獻(xiàn)[15]的云計(jì)算負(fù)載均衡方法，量子粒子群優(yōu)化算法加快了云計(jì)算負(fù)載均衡問題的求解速度，可以滿足大規(guī)模云計(jì)算負(fù)載均衡應(yīng)用要求.

圖4 云計(jì)算負(fù)載均衡方法的負(fù)載分布對比Fig.4 Comparison of load distribution among load balancing methods for cloud computing

表1 最優(yōu)方案的迭代次數(shù)對比Tab.1 Comparison of iteration times for optimal solution

4 結(jié) 論

負(fù)載均衡是云計(jì)算系統(tǒng)中的一項(xiàng)關(guān)鍵技術(shù)，針對當(dāng)前云計(jì)算負(fù)載均衡方法存在的不足，為了獲得更優(yōu)的云計(jì)算負(fù)載均衡效果，本文設(shè)計(jì)了基于量子粒子群優(yōu)化算法的云計(jì)算負(fù)載均衡方法.測試結(jié)果表明，量子粒子群優(yōu)化算法可以獲得理想的云計(jì)算負(fù)載均衡方案，使云計(jì)算節(jié)點(diǎn)之間的負(fù)載更加均衡，加快了用戶任務(wù)完成速度，具有一定的推廣價(jià)值.