基于螢火蟲群優化的虛擬機放置方法

徐勝超，熊茂華，周天綺

基于螢火蟲群優化的虛擬機放置方法

徐勝超1，熊茂華1，周天綺2

（1.廣州華商學院數據科學學院，廣東 廣州 511300；2.浙江藥科職業大學醫療器械學院，浙江 寧波 315100）

利用虛擬機放置策略對云數據中心的物理資源利用效率進行優化十分必要。提出了基于螢火蟲群優化的虛擬機放置（glowworm swarm optimization based VM placement，Gso-wmp）方法。GSO-VMP方法將物理主機的處理器使用效率表示為熒光素值，當一個虛擬機被放置到物理主機上時，該物理主機的熒光素值都要進行更新；能夠在局部徑向范圍內搜索到更多的可用物理主機，完成虛擬機放置，減少了虛擬機的遷移次數，從而間接地節省了物理主機的能量消耗。使用CloudSim作為GSO-VMP的仿真環境進行仿真，實驗結果表明，GSO-VMP方法使得云數據中心的能耗降低、多維物理資源利用率提高。

智能計算；螢火蟲群優化；虛擬機放置；云數據中心；低能量消耗

0 引言

低能量消耗與物理資源的充分利用是綠色云數據中心構造的兩個主要目標[1-2]。目前，國內外的研究主要采用虛擬機遷移技術來達到這兩個目標[3-5]。虛擬機放置及優化是虛擬機遷移中最重要的一個階段，屬于多目標優化問題或者裝箱問題[6]，它沒有最優解，只能在目標函數中得到一定程度的最優，目前針對虛擬機放置有很多智能優化算法，近年來的研究主要涉及兩個方面的研究進展：能量消耗模型的改進和智能算法的改進。

在能量消耗模型改進方面，早期的文獻在設計云數據中心物理主機的能量消耗模型時考慮的物理資源維度比較單一，例如單一物理資源[7]只考慮處理器利用率、處理器主頻大小、處理器溫度大小這一個維度[8]；后續考慮問題的維度擴展到了內存利用率、磁盤空間大小、I/O通信能力等；近3年，還考慮了更多的因素，如網絡帶寬因素、如網絡設備接口能量消耗等[9]。

在智能算法改進方面，近年來研究者提出了大量的新型智能算法進行虛擬機放置階段的優化，例如有基于遺傳算法[10]、貪心算法[11]、粒子群優化算法[12]、蟻群算法[13-14]、強化學習優化算法[15]、花授粉優化算法[16]、蛙跳算法[17]、穩定匹配[18]等的虛擬機放置策略。大部分優化策略的目的是在云數據中心的總體能量消耗、虛擬機遷移次數、SLA違規率、活動物理主機數量等目標指標上取平衡。

其中，貪心算法優化方面常見的有首次遞減適用算法[19]、最佳適用算法[20]、最佳遞減適用算法等，但是由于虛擬機放置是多目標優化問題，貪心算法也不可能得到最優解；在遺傳算法優化方面有常見的普通遺傳算法、家族遺傳算法[21]、混合遺傳算法[6]、改進的遺傳算法[22]等，但是由于它們采用約束編程的方式，限制了搜索空間。雖然，近年來蟻群算法優化的虛擬機放置在單維物理資源的高效利用方面取得了一定的成功，它們的實驗結果表明性能優于首次遞減適用的貪心算法，其不足是不能充分利用多個維度的物理資源。文獻[23]采用蟻群算法優化，從處理器和內存大小等多個維度的信息來考慮云數據中心的虛擬機遷移，結果表明它的性能優于遺傳算法。強化學習優化算法和花授粉優化算法是2019年被提出的虛擬機放置優化算法，在云數據中心的能耗與資源利用方面都性能良好，本文重點研究的也是虛擬機放置及優化策略。

由于螢火蟲群優化算法在解決經典裝箱問題上有很好的優勢[24]，本文提出了基于螢火蟲群優化的虛擬機放置（glowworm swarm optimization based VM placement，GSO-VMP）方法，通過這種智能優化算法，大量的虛擬機在云數據中心的物理主機上遷移、優化放置、負載均衡，以提高物理資源的使用效率。最后與近幾年的常見虛擬機放置優化策略進行比較，在各個性能指標方面完成了GSO-VMP的測試與性能分析，得到了理想的實驗結果。

1 螢火蟲群優化算法

由于螢火蟲群算法的控制中心不在一個單獨的點上，所以該算法具有很好的擴展性。它模擬了螢火蟲的行為，一個會產生更亮的光（高熒光素）的螢火蟲意味著它更接近一個實際的位置，具有更加接近目標函數的值，在GSO-VMP中指的是云數據中心的總體能量消耗（目標函數）最低。

根據一定的概率機制，每個螢火蟲都會選擇一個比自己具有更高螢光素的鄰居，并且向它移動，該移動過程是基于局部徑向范圍的。螢火蟲群算法中，在開始的時候螢火蟲在一個隨機的位置，所有的螢火蟲都包括一個相同的熒光素。本文將螢火蟲群算法應用到虛擬機放置這個過程中，使虛擬機選擇和部署在不同的物理主機，最終目的是降低云數據中心的能量消耗和減少SLA（service level agreement）違規比率。SLA違規比率可以通過式（1）計算。

其中，SLATAH是SLA違規的在線時間PDM是虛擬機遷移后的性能降低，這些在虛擬機放置的經典文獻都有介紹[25]。

2 GSO-VMP工作環境與相關術語

2.1 GSO-VMP的工作環境

云計算環境下分配可用的資源給云客戶端具有各種不同的模式，這些模式都可以被認為是針對云數據中心資源池的一種基于服務的訪問，虛擬機技術通過將云客戶端的請求封裝成虛擬機的形式來分配與訪問。圖1是GSO-VMP虛擬機放置策略的資源分配模型，它由3個主要步驟組成。

步驟1 云客戶端提交請求。

步驟2 服務提供者處理請求。

步驟3 云數據中心資源分配與管理。

首先，云客戶端提交請求到云服務提供者，代理將返回該結果到右邊的云數據中心資源管理模塊。云資源管理將查詢該請求，與可用資源池的資源進行比較，并做出決策。云資源管理對云客戶端請求的接受都基于平臺的資源可用性，如果超過了資源的可用能力，云資源管理將會把該請求傳遞到資源分配模式，尋找全局可用資源，該資源分配方法被傳遞到資源管理模塊，里面包含了GSO-VMP等虛擬機分配與優化的相關的操作。

圖1 GSO-VMP虛擬機放置策略的資源分配模型

2.2 GSO-VMP的相關術語

2.2.1 云客戶端請求模型

所以，當云客戶端只發送一個請求到一個資源上時，可以按照式（2）和式（3）來表達。

另外，如果客戶端的請求數超過一個的時候，可以按照式（3）和式（4）來表達。

2.2.2 云數據中心能量消耗模型

（1）有資源必須有能力提供給云客戶端的請求；

（2）所有虛擬機的資源請求必須小于或等于整個物理主機的資源提供能力；

則整個云數據中心的物理主機的資源利用效率如式（8）所示：

3 GSO-VMP虛擬機放置策略

3.1 GSO-VMP總體描述

下面分別具體描述GSO-VMP的4個階段。

（1）螢火蟲初始化階段

初始種群由大量的螢火蟲組成，這些被認為是虛擬機放置階段的候選解決方法。一個螢火蟲可以認為是一個元素向量，每個元素都表示一個虛擬機。元素的值采用被分配了虛擬機后物理主機的ID來表示。

初始種群的產生基于最小負載的物理主機，從物理主機狀態檢測階段產生的候選遷移物理主機列表HostsToMigrateList中獲取。

（2）熒光素值更新階段

因此，物理主機的熒光素值是根據目標函數值的變化而改變。無論什么時候當一個虛擬機被放置到物理主機上時，該物理主機的熒光素值都要進行更新。如果熒光素值比較高，意味著它可以更好地降低物理主機的能量消耗，熒光素值也隨著時間的變化而衰減。

（3）螢火蟲移動階段

1）發現鄰居區域

2）計算概率

3）螢火蟲移動

在移動階段的最后，根據它所選擇的物理主機，虛擬機的資源使用效率也發生了變化，虛擬機的狀態通過式（17）進行計算。

（4）局部徑向范圍更新階段

3.2 GSO-VMP放置策略的實現

GSO-VMP螢火蟲群虛擬機放置優化整個過程的偽代碼如下。

算法1

輸入 物理主機列表PhList,虛擬機選擇階段產生的侯選虛擬機列表VMsToMigrateList，初始參數

輸出 已經完成好的虛擬機放置列表Placement of VMs

4 GSO-VMP仿真實驗與性能分析

4.1 實驗環境

本文參考了Cloudsim4.0工具包，同時依據圖1中的功能模塊，實現了基于Java語言的云資源管理方法，根據算法1在該模塊中實現了螢火蟲群算法的優化代碼。表1顯示了云數據中心的物理主機和虛擬機的參數配置情況，為了使描述簡單，這些物理主機都是相同的配置，表2顯示了GSO-VMP算法與其他常見的Benchmark智能算法的參數設置，這些參數設置是虛擬機放置優化算法的常見經驗設置，用來比較不同的虛擬機放置算法的性能優劣[4]。

表1 云數據中心的物理主機的參數設置

表2 不同優化策略性能分析相關的參數設置

4.2 客戶端虛擬機類型設置

實驗中與虛擬機相關的參數都來自最常見的CoMon項目，它是由PlanetLab開發的一個項目[30]。虛擬機遷移周期設置為10 min一次，一共運行24 h，每次統計一天內的能量消耗，在一周內重復運行5次取平均值，一周內每天虛擬機請求的個數見表3，不同的虛擬機粒度見表4。

表3 周一到周五PlanetLab項目的設置

表4 CoMon項目不同虛擬機粒度的參數設置

4.3 仿真結果與性能分析

4.3.1 物理資源的利用效率

GSO-VMP多維物理資源利用效率分析如圖3所示，顯示了各個智能算法優化針對云數據中心的所有物理主機的處理器資源、內存資源和存儲資源的平均利用效率情況，也對包括云數據中心在內的所有活躍物理主機情況進行了分析。CPU利用效率隨虛擬機個數的變化如圖4所示，顯示了隨著虛擬機請求個數的增加，物理資源利用效率的變化情況。這些實驗結果表明，GSO-VMP策略可以使得云數據中心的物理主機資源利用率平均達到91%以上，而且處理器的利用效率最高。

在相同的軟硬配置和虛擬機請求的條件下，花授粉優化算法（flower pollination algorithm，FPA）、遺傳算法（genenic algorithm，GA）以及蟻群優化（ant colony optimization，ACO）算法等虛擬機放置優化策略只能使得云數據中心的物理資源達到72%的利用效率，GSO-VMP策略能夠高效地利用物理資源。分析原因是GSO-VMP能夠在局部徑向范圍內搜索到更多的可用物理主機，完成虛擬機放置，通過定義最佳鄰居數量，經過螢火蟲群優化后，各個物理主機的處理器的利用效率提高，從而間接地節省了物理主機的能量消耗。

圖3 GSO-VMP多維物理資源利用效率分析

圖4 CPU利用效率隨虛擬機個數的變化

另外一個原因是GSO-VMP中虛擬機遷移都是基于虛擬機對處理器利用效率需求情況。GSO-VMP可以很好地分配虛擬機到目標物理主機，整體來講，所有上面的實驗結果都證明GSO-VMP是一個可操作的，成功的和高效的大規模云資源分配和優化策略。

4.3.2 云數據中心的總體能量消耗

圖5和圖6顯示了GSO-VMP、GA、ACO、FPA等虛擬機放置策略在不同的虛擬機請求下的云數據中心的能量消耗情況。總體來說，隨著云客戶端的虛擬機個數的增加，能量消耗都在增長。與GA、ACO和FPA策略比較起來，GSO-VMP策略的能量消耗最小。

圖5 GSO-VMP隨虛擬機個數的能量消耗情況

圖6 GSO-VMP隨主機個數的能量消耗情況

因為客戶端的虛擬機請求個數的增加，越來越多的物理主機將被分配虛擬機，當活動主機數目不夠的時候，云數據中心還會啟動處于睡眠狀態的物理主機。GSO-VMP能夠獲得這樣的良好性能也是因為螢火蟲群算法的虛擬機放置優化策略以及該策略在對云數據中心總體能量消耗的目標函數設計之上。

表5顯示了隨著物理主機數量的變化，整個云數據中心不同算法的總體能量消耗與資源利用情況。從表5可以看出，在相同的虛擬機請求個數條件下，GSO-VMP策略的最大能量消耗只有100.3 kW·h，GA策略是125 kW·h。ACO策略是 129 kW·h，FPA策略是 111 kW·h，因此GSO-VMP虛擬機放置策略比常見的優化策略可以節省20%的能量消耗，間接降低了企業成本。

表5 不同算法的總體能量消耗與資源利用情況

5 結束語

本文提出了云數據中心基于螢火蟲群優化的虛擬機放置策略——GSO-VMP。GSO-VMP通過定義云數據中心總體能量消耗的目標函數，將物理主機處理器的使用效率作為螢火蟲群的熒光素亮度值的函數參數，將螢火蟲群優化算法的4個階段運用到虛擬機的放置過程中，最終將大量的候選遷移虛擬機重新高效地放置到最合適的物理主機之上。實驗結果表明，GSO-VMP在能量消耗與資源利用方面有更加優秀的性能。下一步工作是將GSO-VMP放置策略運用到容器云資源分配之中。

[1] 陳雙喜, 趙若琰, 劉會, 等. 基于KVM的虛擬機Post-Copy動態遷移算法穩定性優化[J]. 電信科學, 2021, 37(7):57-66.

CHEN S X, ZHAO R Y, LIU H, et al. Stability optimization of dynamic migration algorithm for Post-Copy of virtual machine based on KVM[J]. Telecommunications Science, 2021, 37(7):57-66.

[2] 黃丹池, 何震葦, 嚴麗云, 等. Kubernetes容器云平臺多租戶方案研究與設計[J]. 電信科學, 2020, 36(9): 102-111.

HUANG D C, HE Z W, YAN L Y, et al. Research and design of multi-tenant scheme for Kubernetes container cloud platform[J]. Telecommunications Science, 2020, 36(9): 102-111.

[3] SHI T, MA H, CHEN G. Energy-aware container consolidation based on PSO in cloud data centers[C]//Proceedings of 2018 IEEE Congress on Evolutionary Computation. Piscataway: IEEE Press, 2018: 1-8.

[4] USMAN M J, ISMAIL A S, CHIZARI H, et al. Energy-efficient virtual machine allocation technique using flower pollination algorithm in cloud datacenter: a panacea to green computing[J]. Journal of Bionic Engineering, 2019, 16(2): 354-366.

[5] ARIANYAN E, TAHERI H, KHOSHDEL V. Novel fuzzy multi objective DVFS-aware consolidation heuristics for energy and SLA efficient resource management in cloud data centers[J]. Journal of Network and Computer Applications, 2017(78): 43-61.

[6] KAAOUACHE M A, BOUAMAMA S. Solving Bin packing problem with a hybrid genetic algorithm for VM placement in cloud[J]. Procedia Computer Science, 2015, 60(1): 1061-1069.

[7] BELOGLAZOV A, BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computation: Practice and Experience, 2012, 24(13): 1397-1420.

[8] WANG J V, CHENG C T, TSE C K. A power and thermal-aware virtual machine allocation mechanism for cloud data centers[C]//Proceedings of 2015 IEEE International Conference on Communication Workshop. Piscataway: IEEE Press, 2015: 2850-2855.

[9] 劉開南. 云數據中心基于遺傳算法的虛擬機遷移模型[J]. 計算機應用研究, 2020, 37(4): 1115-1118.

LIU K N. Virtual machine migration model in cloud data centers based on genetic algorithm[J]. Application Research of Computers, 2020, 37(4): 1115-1118.

[10] 徐勝超. 利用遺傳算法完成虛擬機放置策略的優化[J]. 計算機與現代化, 2020(12): 25-31, 42.

XU S C. Using genetic algorithm for virtual machine placement optimization[J]. Computer and Modernization, 2020(12): 25-31, 42.

[11] 徐勝超. 貪心算法優化云數據中心的虛擬機分配策略[J]. 計算機系統應用, 2021, 30(3): 134-141.

XU S C. Greedy algorithms optimized virtual machine allocation for cloud data centers[J]. Computer Systems & Applications, 2021, 30(3): 134-141.

[12] XIONG A P, XU C X. Energy efficient multiresource allocation of virtual machine based on PSO in cloud data center[J]. Mathematical Problems in Engineering, 2014: 816518.

[13] 徐勝超. 一種新的蟻群算法優化的虛擬機放置策略[J]. 計算機測量與控制, 2021, 29(5): 235-240.

XU S C. A new ant colony algorithm optimized virtual machine placement strategy[J]. Computer Measurement & Control, 2021, 29(5): 235-240.

[14] 陳艷, 周天綺, 徐勝超. 利用蟻群算法完成虛擬機放置的優化[J]. 計算機工程與設計, 2021, 42(5): 1229-1234.

CHEN Y, ZHOU T Q, XU S C. ACO-VMP: using ant colony optimization algorithm for virtual machine placement[J]. Computer Engineering and Design, 2021, 42(5): 1229-1234.

[15] DUGGAN M, FLESK K, DUGGAN J, et al. A reinforcement learning approach for dynamic selection of virtual machines in cloud data centres[C]//Proceedings of 2016 Sixth International Conference on Innovative Computing Technology (INTECH). Piscataway: IEEE Press, 2016: 92-97.

[16] 戴嬌, 張明新, 孫昊, 等. 花朵授粉算法的優化[J]. 計算機工程與設計, 2017, 38(6): 1503-1509.

DAI J, ZHANG M X, SUN H, et al. Optimization of flower pollination algorithm[J]. Computer Engineering and Design, 2017, 38(6): 1503-1509.

[17] LUO J P, LI X, CHEN M R. Hybrid shuffled frog leaping algorithm for energy-efficient dynamic consolidation of virtual machines in cloud data centers[J]. Expert Systems With Applications, 2014, 41(13): 5804-5816.

[18] WANG J V, FOK K Y, CHENG C T, et al. A stable matching-based virtual machine allocation mechanism for cloud data centers[C]//Proceedings of 2016 IEEE World Congress on Services. Piscataway: IEEE Press, 2016: 103-106.

[19] WOOD T, SHENOY P, VENKATARAMANI A, et al. Sandpiper: black-box and gray-box resource management for virtual machines[J]. Computer Networks, 2009, 53(17): 2923-2938.

[20] MISHRA M, SAHOO A. On theory of VM placement: anomalies in existing methodologies and their mitigation using a novel vector based approach[C]//Proceedings of 2011 IEEE 4th International Conference on Cloud Computing. Piscataway: IEEE Press, 2011: 275-282.

[21] JOSEPH C T, CHANDRASEKARAN K, CYRIAC R. A novel family genetic approach for virtual machine allocation[J]. Procedia Computer Science, 2015(46): 558-565.

[22] VASUDEVAN M, TIAN Y C, TANG M L, et al. Energy-efficient application assignment in profile-based data center management through a repairing genetic algorithm[J]. Applied Soft Computing, 2018(67): 399-408.

[23] LIU X F, ZHAN Z H, DENG J D, et al. An energy efficient ant colony system for virtual machine placement in cloud computing[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 113-128.

[24] ALBOANEEN D A, TIANFIELD H, ZHANG Y. Glowworm swarm optimisation algorithm for virtual machine placement in cloud computing[C]//Proceedings of 2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress. Piscataway: IEEE Press, 2016: 808-814.

[25] ZHOU Z, HU Z G, LI K Q. Virtual machine placement algorithm for both energy-awareness and SLA violation reduction in cloud data centers[J]. Scientific Programming, 2016: 5612039.

[26] JAMIL M, YANG X S. A literature survey of benchmark functions for global optimisation problems[J]. International Journal of Mathematical Modelling and Numerical Optimisation, 2013, 4(2): 150.

[27] WANG R, ZHOU Y Q. Flower pollination algorithm with dimension by dimension improvement[J]. Mathematical Problems in Engineering, 2014: 481791.

[28] LIN W W, XU S Y, HE L G, et al. Multi-resource scheduling and power simulation for cloud computing[J]. Information Sciences, 2017, 397/398: 168-186.

[29] FARAHNAKIAN F, ASHRAF A, PAHIKKALA T, et al. Using ant colony system to consolidate VMs for green cloud computing[J]. IEEE Transactions on Services Computing, 2015, 8(2): 187-198.

[30] SPEC. Benchmarks, standard performance evaluation corporation[S]. 2021.

Approach of glowworm swarm optimization based virtual machine placement

XU Shengchao1, XIONG Maohua1, ZHOU Tianqi2

1. School of Date Science, Guangzhou Huashang College, Guangzhou 511300, China 2. School of medical instruments, Zhejiang Pharmaceutical Vocational University, Ningbo 315100, China

In a cloud data center, one of the most important problems is using novel virtual machine placement strategy to promote the physical resource utilization. An approach of glowworm swarm optimization based virtual machine placement for cloud data centers called GSO-VMP was proposed. In the virtual placement, GSO algorithm was used to find a near-optimal solution.Each physical host had a luciferin value which represented the available CPU utilization.Whenever a VM was placed to a physical host, luciferin value of this physical host was updated. GSO-VMP algorithm could search the more available physical host within localrange and thus the virtual migration numbers had been decreased and low energy consumption had been obtained. GSO-VMP had been evaluated using CloudSim with real-world workload data. The experimental results show that GSO-VMP has good performance in resource wastage and energy consumption.

intelligent computing, glowworm swarm optimization, virtual machine placement, cloud data center, low energy consumption

TP393

A

10.11959/j.issn.1000?0801.2022060

2021?08?25；

2022?01?24

周天綺，zhoutianqi_2018@126.com

廣東省高等學校科學研究特色創新項目（No.2021KTSCX167）；廣州華商學院校內導師制科研項目（No.2021HSDS15）

s: Characteristic Innovation Project of Scientific Research in Colleges and Universities of Guangdong Province (No.2021KTSCX167), Science and Research Project in Supervisor of Guangzhou Huashang College (No.2021HSDS15)

徐勝超（1980? ），男，廣州華商學院數據科學學院講師，主要研究方向為并行分布式處理軟件。

熊茂華（1958? ），男，廣州華商學院數據科學學院教授、碩士生導師，主要研究方向為嵌入式與物聯網、智能控制、人工智能技術。

周天綺（1976? ），男，浙江藥科職業大學醫療器械學院副教授，主要研究方向為圖像處理、醫療大數據和云計算。