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

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

0 引言

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

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

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

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

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

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

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

　　1.2 集群負(fù)載計(jì)算

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

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

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

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

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

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

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

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

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

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

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

　　w=wmin-hvwh+svws（8）

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

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

　　其中，f（Gi）表示利用目標(biāo)函數(shù)計(jì)算第i群體的適應(yīng)度，  f（Gavg）表示N個(gè)群體的平均適應(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}，同時(shí)滿足且f（P）<fd[4]。是預(yù)期的方差閾值，fd是預(yù)期的適應(yīng)度最優(yōu)值，K的取值范圍是{0.1，0.55}。利用式（10）對(duì)群體的N各粒子進(jìn)行自適應(yīng)變異，提高算法的全局求優(yōu)能力。

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

　　2.2 粒子編碼設(shè)計(jì)

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

　　2.3 算法步驟設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)分析

　　3.1 實(shí)驗(yàn)環(huán)境搭建

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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