摘  要： 針對云平臺的虛擬資源的負(fù)載均衡問題，為了實現(xiàn)虛擬資源的合理分配和保持用戶桌面的穩(wěn)定性，提出一種基于動態(tài)改變算法權(quán)值的自適應(yīng)粒子群算法，并利用Eucalyptus平臺進(jìn)行實驗。實驗證明，該方法比貪婪算法和基本粒子群算法具有更好的調(diào)節(jié)效果，能夠有效地控制負(fù)載均衡和保持系統(tǒng)的穩(wěn)定性。

　　關(guān)鍵詞： 虛擬桌面；負(fù)載均衡；服務(wù)器

0 引言

　　目前已有許多高校將云計算、虛擬化技術(shù)應(yīng)用到實驗實訓(xùn)中心的服務(wù)器管理和用戶桌面系統(tǒng)的部署控制，搭建各種內(nèi)部云計算平臺進(jìn)行資源管理和提供服務(wù)。通過一段時間的部署體驗發(fā)現(xiàn)，當(dāng)用戶的桌面需求快速增加時，服務(wù)器需要部署更多的虛擬機(jī)，負(fù)載壓力以幾何級陡增。服務(wù)器配置存在差異，服務(wù)器所承載的負(fù)載極限各不相同，如果不能對虛擬機(jī)進(jìn)行實時遷徙，就會出現(xiàn)部分服務(wù)器的負(fù)載過大，有些服務(wù)器的負(fù)載小，造成負(fù)載不平衡和影響平臺的穩(wěn)定性[1-2]。因此，怎樣對云服務(wù)器進(jìn)行負(fù)載調(diào)節(jié)管理，有效提高資源利用率是當(dāng)前云計算研究的一項熱點。通過對相關(guān)參考文獻(xiàn)的研究[3]，本文利用一種基于粒子群算法的動態(tài)改變權(quán)值的自適應(yīng)變異的方法對實驗云平臺的虛擬資源進(jìn)行負(fù)載均衡調(diào)節(jié)。

1 系統(tǒng)模型定義

　　將實驗中心的云服務(wù)器資源定義為的四元組，分別代表了服務(wù)器的處理器資源、內(nèi)存資源、網(wǎng)絡(luò)資源和磁盤存儲資源。采用同樣的方法將虛擬資源定義為的四元組。虛擬資源的負(fù)載均衡控制實際上就是將M個虛擬機(jī)分配到N臺服務(wù)器上的NP問題。每個虛擬桌面只能部署到一臺物理服務(wù)器上，每臺服務(wù)器上需要同時運行多個虛擬桌面，針對這種情況，利用一個矩陣來描述這種NM組合的部署情況：

　　SV=D11 D12 D13 … D1mD21 D22 D23 … D2mD31 D32 D33 … D3m…  …   …   …   …Dn1 Dn2 Dn3 … Dnm（1）

　　SV矩陣中每個Dnm元素的取值范圍為{0，1}。當(dāng)Dnm=1時，表示第M個虛擬桌面部署到第N臺服務(wù)器上；如果Dnm=0時，則表示該服務(wù)器上沒有部署虛擬桌面。

　　1.1 服務(wù)器負(fù)載能力

　　利用式（2）計算云中一臺服務(wù)器的負(fù)載能力C，并對整個實驗云的服務(wù)器負(fù)載能力求平均值Cavg，將Cavg作為每個節(jié)點的基本負(fù)載能力基礎(chǔ)。式（2）中，表示每個虛擬桌面需要的處理器資源數(shù)，表示所部署服務(wù)器所能提供的處理器資源總量，并且。

　　1.2 集群負(fù)載計算

　　觀察某個時間段的虛擬機(jī)用量，假設(shè)t時刻為實驗云的某個運行時間，利用參考文獻(xiàn)[4]提供的方法計算該時刻前的T時間內(nèi)的服務(wù)器負(fù)載情況。利用T時間作為實驗云的負(fù)載觀察區(qū)間，計算每個虛擬桌面的平均資源利用率作為第j臺虛擬機(jī)的負(fù)載，以此計算第k臺服務(wù)器t時間內(nèi)的負(fù)載情況。利用式（3）定義第k臺服務(wù)器的負(fù)載LkS。

　　其中，Ck表示第k臺服務(wù)器的負(fù)載能力，n表示在T時間區(qū)內(nèi)第k臺服務(wù)器上部署的所有的虛擬桌面數(shù)量，t表示第j臺虛擬桌面在T時間區(qū)內(nèi)總運行時間。部署虛擬桌面需要考慮服務(wù)器的負(fù)載均衡情況，利用式（3）預(yù)測計算每臺服務(wù)器上的虛擬桌面的負(fù)載量。通過方差公式（式（4））估算云服務(wù)器集群的負(fù)載能力，選擇負(fù)載能力較強的服務(wù)器作為部署需要的優(yōu)先考慮節(jié)點。

　　其中，N是實驗云的服務(wù)器節(jié)點數(shù)量，是實驗云中第j臺服務(wù)器的固有負(fù)載量，是實驗云中第j臺服務(wù)器在t時間預(yù)測計算的平均負(fù)載量。的值越大，表示服務(wù)器集群的負(fù)載能力越大，將其作為負(fù)載極限的判斷參考條件。

　　1.3 目標(biāo)函數(shù)

　　為實現(xiàn)本文提出的目標(biāo)，定義函數(shù)fmax（S，V）用于計算實驗云資源利用率最大化，函數(shù)fmin（m）用于計算虛擬機(jī)的遷徙次數(shù)。目標(biāo)函數(shù)為：

　　約束條件為：<ε，即通過式（4）計算得到負(fù)載方差必須小于服務(wù)器固有預(yù)定的閾值ε；<Cε，即通過負(fù)載均衡后云的負(fù)載總量必須小于固有的負(fù)載能力Cε。

2 負(fù)載均衡設(shè)計

　　2.1 動態(tài)自適應(yīng)算法

　　為了實現(xiàn)動態(tài)自適應(yīng)負(fù)載均衡目標(biāo)，在標(biāo)準(zhǔn)粒子群算法的基礎(chǔ)上進(jìn)行自適應(yīng)變異處理和動態(tài)改變權(quán)值，克服原有算法收斂過快的現(xiàn)象。具體算法使用的公式如下。

　　（1）算法的粒子速度和位置更新公式：

　　為了提高算法的全局搜索能力，使粒子能夠隨群體規(guī)模的大小而變化，根據(jù)參考文獻(xiàn)[5]對式（6）中w進(jìn)行動態(tài)設(shè)置[5]，具體公式如下：

　　w=wmin-hvwh+svws（8）

　　其中，wmin為w的初始值；hv為進(jìn)化速度因子，hv=，用當(dāng)前迭代f（Gn）與上一次迭代f（Gn-1）間的最小值和最大值計算進(jìn)化速度hv；sv為粒子聚集因子，。Ft為當(dāng)前迭代粒子適應(yīng)度值的平均值，，計算規(guī)模為N的粒子群迭代到第t次時的適應(yīng)度平均值。

　?。?）計算群體的自適應(yīng)公式：

　　其中，f（Gi）表示利用目標(biāo)函數(shù)計算第i群體的適應(yīng)度，  f（Gavg）表示N個群體的平均適應(yīng)度，f（G）表示從i到N不斷演變的群體適應(yīng)度值。f（G）的取值范圍是{1，fmax（f（Gi）-f（Gavg））}。根據(jù)參考文獻(xiàn)[4]的方法定義隨機(jī)因子Pm，Pm的取值范圍是{K，0}，同時滿足且f（P）<fd[4]。是預(yù)期的方差閾值，fd是預(yù)期的適應(yīng)度最優(yōu)值，K的取值范圍是{0.1，0.55}。利用式（10）對群體的N各粒子進(jìn)行自適應(yīng)變異，提高算法的全局求優(yōu)能力。

　　其中，Zk是表示粒子Z的第k維數(shù)值，是呈正態(tài)分布的隨機(jī)變量。對群體N個粒子進(jìn)行升序操作，利用式（10）將升序后的前一半數(shù)量的粒子與全局最優(yōu)的粒子進(jìn)行變異計算。將變異前后的粒子適應(yīng)度值進(jìn)行比較，選取最大值作為新的全局最優(yōu)，值小的作為新的局部最優(yōu)。

　　2.2 粒子編碼設(shè)計

　　由于服務(wù)器負(fù)載均衡涉及多種資源的控制分配，因此算法需要的粒子編碼采用多維向量的方式來處理，每一維代表一種資源情況。為了使算法更易于實現(xiàn)，將粒子編碼統(tǒng)一轉(zhuǎn)為整數(shù)編碼。假設(shè)第Zi粒子的編碼形式為{2，1，2，3，5，3，4，8，1}，在矩陣SV中對應(yīng)的值是D21=D12=D23=D34=D55=D36=D47=D88=D19=1，表示第1和第3虛擬桌面部署在2號服務(wù)器上，第4和第6虛擬桌面部署在3號服務(wù)器上，其他的虛擬桌面與服務(wù)器的映射部署以此類推。在算法的實現(xiàn)過程中，由于對于粒子的位置和速度進(jìn)行計算會出現(xiàn)粒子編碼為非整數(shù)情況，在這種情況下，采用四舍五入的規(guī)則對粒子編碼進(jìn)行轉(zhuǎn)換操作。

　　2.3 算法步驟設(shè)計

　　將目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，設(shè)置預(yù)期的閾值ε，約束條件作為判斷條件，具體實現(xiàn)步驟如下：

　　（1）根據(jù)用戶需求創(chuàng)建虛擬桌面集合，利用式（4）計算云負(fù)載能力，將虛擬桌面分配到合適的服務(wù)器。

　?。?）利用式（5）的目標(biāo)函數(shù)作為算法的適應(yīng)度函數(shù)，初始化算法中粒子的位置和速度，設(shè)置粒子當(dāng)前的局部最優(yōu)P和群體中的全局最優(yōu)G的位置。

　?。?）迭代進(jìn)行計算，判斷當(dāng)前的實驗云負(fù)載極限是否達(dá)到約束條件的ε（預(yù)定閾值），如果達(dá)到跳到步驟（11），否則繼續(xù)執(zhí)行步驟（4）。

　?。?）利用式（6）和（7）計算更新后的粒子的位置和速度，并且利用式（9）計算群體更新后的負(fù)載情況。

　?。?）根據(jù)式（8）計算調(diào)節(jié)算法的權(quán)值w，動態(tài)更新w，保持權(quán)值的動態(tài)更新。

　?。?）判斷更新后的群體變化是否達(dá)到約束條件，如果是執(zhí)行步驟（8），否則執(zhí)行步驟（7）。

　?。?）保留上次計算的局部最優(yōu)P值，迭代更新并重新初始化，繼續(xù)循環(huán)計算，直至達(dá)到約束條件，停止迭代。

　?。?）計算更新后的適應(yīng)度，如果更新后的適應(yīng)度優(yōu)于上一次的P的適應(yīng)度，則更新當(dāng)前的P值；假如更新后的群體適應(yīng)度優(yōu)于上一次的G的適應(yīng)度，則更新當(dāng)前的G值。

　?。?）根據(jù)式（9）計算當(dāng)前的粒子群體的適應(yīng)度的自適應(yīng)情況，并計算自動變異因子Pm。

　　（10）判斷式（6）中的隨機(jī)數(shù)是否小于Pm，如果小于Pm，利用式（10）進(jìn)行自適應(yīng)變異操作，并且更新當(dāng)前的P值和G值；否則跳轉(zhuǎn)到步驟（3）。

　?。?1）迭代計算結(jié)束，輸出負(fù)載均衡的組合結(jié)果。

3 實驗分析

　　3.1 實驗環(huán)境搭建

　　為了驗證本文提出算法的有效性和可行性，利用Eucalyptus系統(tǒng)作為實驗測試環(huán)境。根據(jù)參考文獻(xiàn)提供的方法，基于Eucalyptus平臺并結(jié)合KVM與QEMU的虛擬架構(gòu)搭建算法實驗需要的運行平臺[6-7]。

　　3.2 實驗結(jié)果分析

　　分別利用Eucalyptus自帶的貪婪算法、基本粒子群算法與本文設(shè)計的算法進(jìn)行實驗。根據(jù)實驗需要，設(shè)置了所需虛擬機(jī)桌面的數(shù)量規(guī)模分別為50、100、150、200、250和300等數(shù)量級。根據(jù)云控制器顯示的服務(wù)器與虛擬機(jī)的運行分析視圖，分別記錄了各個算法對服務(wù)器虛擬資源利用率的情況，結(jié)果如圖1和圖2所示，并對結(jié)果進(jìn)行分析。

　　如圖1所示，三種算法在不同規(guī)模用戶壓力下的服務(wù)器資源利用率的執(zhí)行結(jié)果各不相同，很明顯動態(tài)自適應(yīng)粒子群算法比其他兩種能更好地進(jìn)行資源的負(fù)載均衡調(diào)節(jié)，提高服務(wù)器的資源利用率。隨著虛擬桌面數(shù)量的不斷增加，為了保持服務(wù)器間資源利用率的平衡，利用三種算法進(jìn)行虛擬資源負(fù)載調(diào)節(jié)。如圖2所示，動態(tài)自適應(yīng)粒子群算法的遷徙數(shù)明顯少于基本粒子群算法和貪婪算法作用下的遷徙數(shù)，在穩(wěn)定性方面具有較好的表現(xiàn)。

4 結(jié)論

　　本文研究了實驗云虛擬資源的負(fù)載均衡問題，利用基于動態(tài)改變權(quán)值的自適應(yīng)變異的粒子群算法對服務(wù)器上的虛擬機(jī)進(jìn)行負(fù)載均衡調(diào)節(jié)。以Eucalyptus作為實驗平臺進(jìn)行測試，實驗結(jié)果驗證了本文提出負(fù)載均衡算法具有更好的優(yōu)越性。但本文的方法還處于實驗測試，沒有應(yīng)用到實際的用戶桌面負(fù)載調(diào)節(jié)中，這將是以后研究的重點。

參考文獻(xiàn)

　　[1] 陳小嬌，陳世平，方芳.云計算中虛擬機(jī)資源分配算法[J].計算機(jī)應(yīng)用研究，2014，31（9）：2584-2587.

　　[2] 常德成，徐高潮.虛擬機(jī)動態(tài)遷移方法[J].計算機(jī)應(yīng)用研究，2013，30（4）：971-976.

　　[3] 何丹丹.云環(huán)境下基于節(jié)能和負(fù)載均衡的混沌粒子群資源優(yōu)化調(diào)[J].計算機(jī)控制與測量，2014，22（5）：1626-1628.

　　[4] 劉衛(wèi)寧，高龍.異構(gòu)云中面向集群負(fù)載均衡的任務(wù)調(diào)度策略[J].計算機(jī)應(yīng)用，2013，33（8）：2140-2142.

　　[5] 張選平.一種動態(tài)改變慣性權(quán)的自適應(yīng)粒子群算法[J].西安交通大學(xué)學(xué)報，2005，39（10）：1039-1042.

　　[6] 楊子夜，周逸勛，陳海波，等.利用虛擬機(jī)動態(tài)遷移技術(shù)整合虛擬和模擬環(huán)境[J].小型微型計算機(jī)系統(tǒng)，2010，31（3）：423-429.

　　[7] 洪文圳，陳玉琴，黃曉峰.基于Eucalyptus的實驗云平臺搭建[J].微型機(jī)與應(yīng)用，2014，33（17）：59-61.