基于量子粒子群優化算法的云計算負載均衡分析*

李祥琴， 羅傳軍， 楊 利

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

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

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

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

1 云計算系統負載均衡

1.1 云計算系統基本結構

云計算系統是一種為了解決海量任務的并行式處理系統，與單節點計算機系統相比，其工作模式具有比較明顯的差異，云計算將服務器、存儲設備、網絡、打印機等抽象成資源，任何用戶都可按自己的需求申請相應類型服務，能夠滿足不同用戶服務質量要求.云計算系統的基本結構如圖1所示.

圖1 云計算系統的基本結構Fig.1 Basic structure of cloud computing system

1.2 云計算系統負載均衡數學模型

設用戶任務集合為S={s1，s2，…，sm}，其中，si為第i個用戶的任務；云計算系統所有節點資源組成的集合為R={r1，r2，…，rl}，其中，rj為節點資源的虛擬設備，其與實際相關物理設備相對應；云計算中具體物理設備集合為D={d1，d2，…，dn}，dk為第k個物理設備.以上三個參數的相互關聯集合可表示為

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

(1)

式中：Mrd為云計算資源與物理設備之間的映射關系；Mtr為用戶任務與云計算系統資源之間的映射關系.

設第i個用戶的任務被分配到第j個資源上，云計算節點資源采用第k個物理設備處理該任務，任務在相應物理設備處理時間為E(si，Mtr，dk)，物理設備dk開始執行第i個用戶任務時間為ST(dk)，則第i個用戶的任務完成時間為

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

(2)

物理設備dk上任務完成時間之和為

(3)

式中，cik=1為si在dk上執行；否則cik=0.云計算負載均衡求解就是找到一個用戶任務完成時間最少的方案，即

(4)

2 負載均衡方法

2.1 標準粒子群優化算法

(5)

(6)

式中：w為權值；τ1、τ2為加速因子；β為搜索時間間隔.

2.2 量子粒子群優化算法

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

(7)

在量子力學中，粒子運動的動力學方程為

(8)

對量子粒子群優化算法的粒子收斂行為進行分析可知：算法中存在一個以點P為中心的某種形式的吸引勢，把點P稱為粒子的吸引子.通過在吸引子中建立一維勢阱，推導出粒子在勢阱中的定態薛定諤方程，解得粒子出現在相對吸引子位置Y的概率密度函數為

(9)

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

引入蒙特卡羅隨機模擬方法測量粒子的位置，粒子在以P點為中心的一維勢阱中運動，其位置可表示為

(10)

式中：u為一個隨機數；XP為當前P點位置.

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

(11)

為了測試量子粒子群優化算法(QPSO)的優越性，本文采用標準粒子群優化算法(PSO)進行了對比分析.選用的標準測試函數為Griewank和Rosenbrock，其定義分別為

(12)

(13)

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

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

2.3 云計算負載均衡方法

本文引入量子粒子群優化算法對云計算負載均衡問題的數學模型進行求解，具體步驟如下：

1) 建立云計算系統，確定各種云計算資源的數量、云計算任務數量以及各種云計算資源的處理能力；

2) 收集用戶任務，對云計算用戶調度任務進行分解，劃分為不同大小的云計算任務；

3) 根據云計算任務、云計算資源以及物理設備之間的對應關系，以用戶任務完成時間最短為目標函數，構建云計算負載均衡問題的數學模型；

4) 引入量子粒子群優化算法對云計算負載均衡的數學模型解進行搜索，找到最優的云計算負載均衡方案.

3 云計算負載均衡方法性能驗證

3.1 實驗參數設置

為了分析量子粒子群優化算法云計算負載均衡方法的性能，采用Matlab 2017工具箱編程云計算負載均衡程序，云計算系統中的節點資源類型為5類.量子粒子群優化算法的參數設置為：量子粒子數為20，搜索擴張系數為0.25，最大迭代次為300.

3.2 實驗結果與分析

3.2.1 任務完成時間對比

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

圖3 云計算負載均衡方法的負載完成時間Fig.3 Load completion time of load balancing methods for cloud computing

3.2.2 資源負載分配結果對比

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

3.2.3 最優方案迭代次數對比

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

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

表1 最優方案的迭代次數對比Tab.1 Comparison of iteration times for optimal solution

4 結 論

負載均衡是云計算系統中的一項關鍵技術，針對當前云計算負載均衡方法存在的不足，為了獲得更優的云計算負載均衡效果，本文設計了基于量子粒子群優化算法的云計算負載均衡方法.測試結果表明，量子粒子群優化算法可以獲得理想的云計算負載均衡方案，使云計算節點之間的負載更加均衡，加快了用戶任務完成速度，具有一定的推廣價值.