云計算環境下基于改進GSO的目標主機選擇算法

陳偉, 程家超, 張超

(宿州職業技術學院計算機系, 安徽宿州234101)

云計算環境下基于改進GSO的目標主機選擇算法

陳偉, 程家超, 張超

(宿州職業技術學院計算機系, 安徽宿州234101)

目標主機的選擇是虛擬機動態遷移過程中的重要階段，是實現負載均衡的關鍵。針對基本螢火蟲算法存在的精度不高、收斂較慢的問題，提出了一種改進的螢火蟲優化算法，用于解決虛擬機遷移時虛擬機和目標物理主機的映射問題，實現多目標最優求解。該算法通過引入步長調整因子，能夠動態調整移動步長，克服了步長過大或過小導致的精度不高、后期收斂較慢的缺點。全面考慮物理主機負載指標，建立負載均衡模型，將螢火蟲算法中個體與節點資源相對應，利用螢火蟲發光機制尋優求解，以實現目標主機的優化選擇。仿真實驗表明，該算法能夠快速完成目標主機的選擇，有效平衡系統資源，實現數據中心負載均衡。

云計算；螢火蟲群優化算法；動態步長；負載均衡；目標主機選擇；虛擬機

引言

云計算[1]是集分布式計算、虛擬化技術、網格計算和 Web 服務等技術發展起來的一種綜合技術[2]，它為用戶提供了基礎設施、平臺以及軟件的服務，并且通過互聯網將服務按需的提供給用戶[3]。虛擬化技術[4]是云計算中的關鍵技術，可以把硬件資源如服務器、網絡、內存及存儲等進行虛擬化，在物理機上批量創建虛擬機來擴展基礎設施層的云資源池，同時可以通過虛擬機的動態遷移技術來實現云數據中心的負載均衡。虛擬機的動態遷移，就是把虛擬機從高負載物理節點遷移至低負載物理節點，實現負載均衡，以提高資源利用率且節能降耗[5]。虛擬機遷移過程中，如何選擇目標主機來接收遷出的虛擬機是本文的研究所在。目標主機選擇是一個NP問題，目前大都采用一些啟發式的算法進行求解。文獻[6]中使用最佳適應算法通過向量比較方式尋找遷移后不會超出負載閾值上限的目標主機，實現虛擬機的調度；文獻[7]通過蟻群算法進行目標求解，資源利用率相對提高，但算法收斂速度過慢；文獻[8]采用遺傳算法進行虛擬機的放置，實現物理機負載均衡；文獻[9]引入粒子群優化算法并進行改進，將不滿足遷移的物理機加入到規避列表，以避免遷移后資源占用率過高；文獻[10]提出了一種多目標蟻群優化的虛擬機放置算法，主要考慮數據中心網絡流量的優化和物理機資源浪費；文獻[11]提出了數據中心負載不均衡度以及物理機與虛擬機之間不匹配度的概念，利用蟻群算法實現較低負載不均衡度；文獻[12]采用權值適應度粒子群優化(WFPSO)算法，能更好地降低應用的執行時間，但未考慮負載均衡的情況。

本文針對虛擬機遷移中目標主機選擇問題，引入人工螢火蟲群優化(Glowworm Swarm Optimization, GSO)算法，并進行改進，從負載均衡角度出發，對目標主機尋優問題進行求解，并通過實驗對該算法有效性進行驗證。

1 云計算負載均衡模型

云計算環境下，當某物理主機上負載過高時可以通過遷出虛擬機的方式減輕負載，本文的算法是讓遷出的虛擬機分配給負載值小的目標主機，避免加重高載主機的負擔，從而提高系統運行效率和資源利用率。

云計算中單個節點的負載指標[13]主要包括CPU利用率Ci、內存利用率Mi、磁盤利用率Di和帶寬利用率Bi。設Ci、Mi、Di、Bi的權重分別為α1、α2、α3、α4，則節點i的綜合負載為：

L(i)=α1Ci+α2Mi+α3Di+α4Bi

(1)

其中：α1+α2+α3+α4=1，Ci、Mi、Di、Bi的值分別為：

(2)

(3)

(4)

(5)

其中：j表示物理節點i上第j個虛擬機；

分別表示物理節點i上虛擬機使用的CPU、內存、磁盤、帶寬之和；

分別表示節點i上CPU、內存、磁盤、帶寬總量。

云數據中心中物理機集群的平均負載為各物理主機負載的平均值，表示為：

(6)

由此可以計算出物理機負載信息值的標準差，衡量整個云數據中心的總體負載均衡情況，并將此標準差作為適應度函數。

(7)

由S的表達式可以看出，標準差越小表明數據中心中各個物理機負載差異較小，整個云計算環境負載效果較好[14]，反之，則越差。虛擬機遷移中目標主機的選擇就是保證遷入后能讓整體負載達到最優，S的值達到最小。

2 GSO算法

GSO算法是印度學者K.N.Krishnanand和D.Ghose于2005年提出的一種新型群智能優化算法[15]。算法的思想源于模擬螢火蟲在晚上群聚活動的自然現象而提出的，螢火蟲通過散發熒光素與同伴進行信息傳遞告知食物源，熒光素越高越亮的螢火蟲其對同伴的吸引力和號召力就越強，最終大量的螢火蟲聚集在較亮的螢火蟲周圍，也即是食物豐富的地方。

在GSO算法中，每只螢火蟲都被看作是解空間的一個解，每個螢火蟲都被隨機分布在目標函數的定義空間中，螢火蟲各自擁有自己的熒光素和視線范圍。每個螢火蟲熒光素的亮度和自己所在位置對應的目標函數的適應度值有關。熒光素越亮的螢火蟲所在位置視為越好，對應的目標函數值越優。GSO算法中螢火蟲尋優的移動方式：螢火蟲在自己的視野范圍內尋找鄰域內熒光較亮的螢火蟲并向其移動靠攏，螢火蟲的視野即決策域半徑會隨鄰域中螢火蟲密度發生變化，當密度較小時會加大決策半徑以便可以找到更多的螢火蟲，反之會減小決策半徑。最終，通過不斷地位置更新，使大部分螢火蟲聚集在較優的位置從而實現目標的優化。

2.1熒光素更新

每只螢火蟲都有自己的熒光素，通過熒光素的亮光來吸引同伴，熒光素的更新公式為：

li(t+1)=(1-ρ)li(t)+γJ(xi(t+1))

(8)

其中：li(t)為第t代第i只螢火蟲的熒光素值；xi(t+1)表示第t+1代螢火蟲的位置；J(xi(t+1))表示螢火蟲所在位置對應的目標函數的適應度值；ρ和γ分別表示螢火蟲的消失速率和更新速率。

2.2決策域半徑更新

決策域半徑表示螢火蟲的視野范圍，表示算法的搜索空間，在視野范圍內搜索其他螢火蟲。決策域半徑是動態變化的，會隨著搜索空間內螢火蟲的數目多少而加大或減小，以確保視野范圍內的螢火蟲數量，決策域半徑得更新公式為：

β(nt-|Ni(t)|)}}

(9)

(10)

2.3確定螢火蟲移動方向

螢火蟲i的移動方向受鄰域內熒光素值大的螢火蟲影響，熒光素值越大吸引力就越大，相應地，螢火蟲選擇向其移動的概率就越大。假設螢火蟲向概率最大的螢火蟲j移動，則有：

j=max(pi)

(11)

其中：pi=(pi1,pi2,...,piNi(t))；螢火蟲i向j移動的選擇概率為：

(12)

2.4螢火蟲位置更新

螢火蟲向選擇概率大的螢火蟲移動后，新的位置表示為：

(13)

3 改進GSO算法在目標主機選擇中應用

3.1算法應用分析

云計算環境下，在確保云數據中心負載均衡前提下，選擇目標主機進行虛擬機遷移，解決虛擬機和物理機的映射問題，把虛擬機分配到對應的物理主機上，此選擇過程即是尋優的過程，可以借鑒GSO算法解空間尋優方式求尋找最適合的目標主機，即求算法的最優解。把虛擬機與螢火蟲個體進行對應，把虛擬機遷移過程中需要遷移的虛擬機看作是新加入覓食的螢火蟲，把物理機集群看作是螢火蟲的聚集群，新加入的螢火蟲可以不斷地移動變化位置，直至尋找到最優位置。尋優過程需滿足云數據中心負載標準差越小，J(xi(t+1))的值越大，由此得出，螢火蟲熒光素越亮，位置越好，負載標準差也越小，螢火蟲的位置即為需要選擇的目標主機。

3.2改進GSO算法

3.2.1 GSO算法存在問題

GSO算法具有較強的搜索能力，操作方便，實現起來比較簡單，但是后期收斂速度慢和求解精度不高等缺陷依然存在。GSO算法采用固定移動步長，搜索初期，如果步長較小，則易陷入局部極值，降低收斂速度；搜索后期，螢火蟲個體和峰值的距離也越來越近，此時如果步長較大，超過這個距離則會跳過全局最優解，造成峰值附近的震蕩，導致精度降低。由此可見，在GSO算法采用固定步長對算法的精度和收斂速度都會有一定的影響，不適合實際需求，因此，要把算法進行改進，使得算法在不同的搜索時期，能夠自動調整步長的大小，以滿足求解的需要。

3.2.2 步長動態調整的GSO算法

針對GSO算法在收斂速度和求解精度上存在的問題，對GSO算法進行了改進，使其步長能夠隨著迭代次數進行動態調整。迭代初期，個體與最優解距離較遠，設置較大的步長值，有利于全局搜索且易跳出局部極值，提高收斂速度；迭代后期，個體與最優解越來越靠近，逐步減少步長值對局部搜索有利，防止跳過最優解，提高算法精度[16]。為此，引入式(14)和(15)對步長進行動態調整。

s(t)=c×s0

(14)

(15)

其中：s0為步長初始值；c為步長調整因子，其值隨著迭代次數的增加而適當減小，隨著實際位置的變化進行動態調整，初始階段個體移動尋優時離高亮度螢火蟲實際距離越大，則步長越大；tmax為最大迭代次數；smax和smin分別表示移動步長的最大值和最小值。由式(13)～式(15)可得出改進后的螢火蟲位置更新公式：

(16)

改進后的算法步長會隨著迭代次數和實際位置的變化而自適應調整，不會因為步長太大導致跳過最優解，也不會因為尋優初期階段步長太小而影響收斂速度，因此，改進后算法在搜索精度和收斂速度能夠得到一定的改善。

3.3目標主機選擇算法實現流程

算法實現步驟描述如下：

(1) 初始化。初始化參數n，ρ，γ，β，nt，s0，rs，l0，smax，smin，tmax，并隨機產生n只螢火蟲，定義其初始位置。

(2) 計算熒光素。根據式(8)更新各螢火蟲的熒光素值，將其作為目標函數，并需滿足云數據中心負載標準差即式(7)的值越小，J(xi(t+1))的值越大。

(3) 尋找鄰域Ni(t)。在決策域內尋找熒光值高于自己的個體構成鄰域Ni(t)。

(4) 確定移動方向。按照式(12)計算選擇概率，確定螢火蟲移動方向。

(5) 更新螢火蟲位置。根據式(14)和(15)對移動步長進行調整，然后根據式(16)進行螢火蟲位置的更新。

(6) 更新決策域。根據式(9)更新決策域半徑。

(7) 判斷迭代次數是否超過最大值，未達到則轉至步驟(2)，否則轉步驟(8)。

(8) 輸出最優解。

由于螢火蟲熒光素越高吸引力越大，使得螢火蟲在移動過程中趨向于熒光素亮的螢火蟲，因此，把負載較小的物理主機看作是熒光素值較高的螢火蟲，從而吸引其他螢火蟲向其移動，實現虛擬機往低負載目標主機遷移。另外把式(7)作為適應度函數，保證了虛擬機在遷移到目標主機后云數據中心整體的負載標準差較小，實現集群負載均衡。

4 仿真實驗

本文采用仿真實驗工具CloudSim[17]模擬云計算環境，采用Java語言編程實現本文算法進行仿真實驗，觀察虛擬機遷移后云中心負載均衡及資源使用率情況。

4.1負載均衡測試

在云數據中心模擬60臺物理主機，每臺物理機上隨機部署虛擬機，并通過隨機方式改變虛擬機的資源使用量，以此模擬負載的變化。

圖1展示了利用本文算法前后云數據中心物理機資源使用率對比情況。h1～h60表示物理機節點，未調整之前CPU、內存、帶寬使用率差異較大，數據中心負載嚴重失衡，存在很多高負載狀態的物理機。利用本文算法調整之后，物理機的CPU、內存、帶寬使用率都趨于正常，維持在60%～70%左右，物理機負載比較均衡。

圖1 使用本文算法調整前后資源使用率對

采用式(7)物理主機負載標準差作為負載均衡度來衡量數據中心的負載均衡情況。負載標準差越小，整體負載均衡效果越好。圖2展示了幾種基于虛擬機遷移算法的負載均衡情況對比。最優負載調度策略(Optimality Based Schedule, OBS)基于最優負載，負載較輕的目標主機會瞬間急劇升高，導致產生群聚效應，負載均衡度效果不佳。文獻[5]的算法采用負載預測進行遷移觸發，使用加權概率進行目標主機選擇，對負載均衡有一定的改善。本文在文獻[5]的基礎上，對目標節點選擇采用改進GSO算法進行解決，使個體在移動時保持負載標準值最小，從而有效避免了群聚效應，負載均衡度維持較低值，負載均衡表現非常出色。

圖2 負載均衡對比

4.2目標主機選擇

選取不同時刻對云數據中心發出虛擬機遷移請求，對本文改進的GSO算法和基本GSO算法進行性能比較。不同時刻提交的虛擬機遷移請求個數見表1。

表1 不同時刻遷移數

不同時刻兩種算法在發出遷移請求到選擇目標主機的運行時間如圖3所示。可見，在處理相同虛擬機遷移請求個數時，對目標主機的尋優過程中，本文改進的GSO算法所用時間明顯低于基本的GSO算法，能夠快速地定位目標主機，使整體負載值標準差最小，數據中心負載均衡情況良好。

圖3 不同時刻遷移時間對比

5 結束語

負載均衡問題是云計算中的關鍵問題。通過虛擬機遷移方式解決云數據中心負載均衡問題是本文的研究基礎。本文針對虛擬機遷移過程中目標主機選擇問題，引入了螢火蟲優化算法，并對其進行改進，通過動態調整步長方式，完善和克服了精度低、收斂速度慢等問題，有效實現了目標主機的最優求解。仿真實驗表明，本文算法能夠快速選擇目標主機，平衡各物理機負載差異，實現云計算環境下負載均衡。

[1] VAQUERO L M,RODERO-MERINO L,CACERES J,et al.A break in the clouds:towards a cloud definition[J].Acm Sigcomm Computer Communication Review,2008,39(1):50-55.

[2] 李喬,鄭嘯.云計算研究現狀綜述[J].計算機科學,2011,38(4):32-37.

[3] 韓德志,李楠楠,畢坤.云環境下的虛擬化技術探析[J].華中科技大學學報:自然科學版,2012,40(S1):262-265.

[4] 董運萌.一種云計算環境下負載均衡敏感的聚類部署方法研究[D].長春:吉林大學,2015.

[5] 陳偉,張超.基于負載趨勢預測的虛擬機動態遷移策略研究[J].綏化學院學報,2016,36(12):145-149.

[6] 周文煜,陳華平,楊壽保,等.基于虛擬機遷移的虛擬機集群資源調度[J].華中科技大學學報:自然科學版,2011,39(S1):130-133.

[7] GAO Y,GUAN H,QI Z,et al.A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[J].Journal of Computer & System Sciences,2013,79(8):1230-1242.

[8] HU J,GU J,SUN G,et al.A scheduling strategy on load balancing of virtual machine resources in cloud computing environment[C]//Proceedings of the 3rd International Symposium on Parallel Architectures,Algorithms and Programming,Dalian,China,December 18-20,2010:89-96.

[9] 武興宇,孫磊,胡翠云,等.基于改進粒子群優化算法的虛擬機遷移選擇策略研究[J].計算機科學,2015,42(S1):20-23.

[10] 趙君,馬中,劉馳,等.一種多目標蟻群優化的虛擬機放置算法[J].西安電子科技大學學報:自然科學版,2015,42(3):173-178+185.

[11] 孟凡超,張海洲,初佃輝.基于蟻群優化算法的云計算資源負載均衡研究[J].華中科技大學學報:自然科學版,2013,41(S2):57-62.

[12] 何利文,袁野,王延松,等.基于WFPSO算法的云虛擬機放置策略[J].計算機應用研究,2017,34(2):591-594.

[13] 顧桓瑜,石磊,郭俊廷.基于改進螢火蟲算法的云計算負載均衡研究[J]. 大連交通大學學報,2015,36(6):107-110.

[14] 寧彬,谷瓊,吳釗,等.云計算環境下的混沌螢火蟲的資源負載均衡算法[J].計算機應用研究,2014,31(11):3397-3400.

[15] 趙光偉.人工螢火蟲群優化算法改進與應用研究[D].南寧:廣西民族大學,2012.

[16] 顧忠偉,徐福緣.一種新穎的螢火蟲算法求解PID控制器參數自整定問題[J].系統管理學報,2017,26(1):101-106.

[17] CALHEIROS R N,RANJAN R,BELOGLAZOV A,et al.CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software Practice & Experience,2011,41(1):23-50.

ASelectionAlgorithmofDestinationHostBasedonImprovedGlowwormSwarmOptimizationAlgorithminCloudComputingEnvironment

CHENWei,CHENGJiachao,ZHANGChao

(Department of Computer Information, Suzhou Vocational and Technical College, Suzhou 234101, China)

The selection of destination host is an important stage in the dynamic migration of virtual machines, and is the key to realize load balancing. In order to overcome the shortcomings of basic glowworm swarm optimization algorithm including low accuracy and slow convergence speed, an improved glowworm swarm optimization algorithm is proposed to solve the mapping problem between the virtual machine and the target physical host when the virtual machine is migrated, and the multi-objective optimal solution is realized. By introducing the step adjustment factor, the algorithm can dynamically adjust the moving step and overcome the shortcomings of low accuracy and slow convergence speed caused by too large step or too small step. Considering the physical load index, the load balancing model is established, and the individual and node resources in the improved glowworm swarm optimization algorithm are matched with each other, and the optimal selection of the destination host is realized by using the luminous mechanism of fireflies. The simulation experiment shows that the improved algorithm can select the destination host quickly，balance the system resource effectively and realize the load balancing of data center.

cloud computing; glowworm swarm optimization algorithm; dynamic step; load balancing; destination host selection; virtual machine

TP301.6

A

2017-08-04

安徽省高校自然科學研究重點項目(KJ2016A778;KJ2016A781);安徽省高校優秀青年人才支持計劃重點項目(gxyqZD2016586);安徽省質量工程項目(2016jyxm1039)

陳 偉(1982-),男,安徽阜陽人,講師,碩士,主要從事計算機網絡方面的研究,(E-mail)chenwei9737@163.com

1673-1549(2017)05-0051-06

10.11863/j.suse.2017.05.09