基于動態規劃的云計算虛擬機簇聚類方法

祝衍軍

(東莞職業技術學院計算機工程系，廣東 東莞 523808)

基于動態規劃的云計算虛擬機簇聚類方法

祝衍軍

(東莞職業技術學院計算機工程系，廣東 東莞 523808)

多虛擬機聚簇的快速高效實現，對于云數據處理能力的提升具有重要意義。基于虛擬機聚簇的一般原理，引入動態規劃全局優化策略，構建一種新的虛擬機聚簇方法。首先根據預設的虛擬機屬性判別函數，對虛擬機資源執行升序排列；進而選取升序集合中心位置的虛擬機作為聚簇起點，根據動態規劃策略從兩個方向開始進行聚簇；聚簇的原則本著全局聚簇最優的動態規劃準則。實驗結果表明，基于動態規劃的虛擬機聚簇方法，聚簇速度快，聚簇效果穩定。

虛擬機；聚簇；云計算；動態規劃

隨著信息技術和大數據處理技術的飛速發展，人們對于信息處理和數據處理的要求越來越高，這也直接導致了計算任務的復雜度和難度不斷攀升[1]。在這種情況下，個人終端的計算資源很難獨立解決計算任務，抑或需要花費更大的成本來完成計算任務。為了解決上述問題，科學家們提出了云計算模型和云服務技術。云計算模式，是在分布模式、并行模式、網格模式之后的又一種新型計算模式，其信息處理能力相比于以往獲得了空前提高。云端服務器不僅硬件配置好，軟件功能強大，而且整合了網絡間各種可以利用的計算資源，可以解決個人終端無法解決的復雜計算任務[2]。

為了提高云計算的效率和云服務的質量，研究者構建了虛擬化技術。通過虛擬化處理，一臺真實的服務器被動態分割成多個虛擬服務器[3]。虛擬機模式的構建，不僅大大降低了云端計算資源的管理難度，也大大提升了云端計算資源的利用效率，這對于快速高效地解決用戶的計算任務具有重要意義[4]。也正因為如此，云計算領域近年來出現了大量有關虛擬機部署的研究成果。李強等[5]指出，啟發式的搜索方法對于虛擬機部署是比較合適的，因為其有利于云端全局優化的實現。何東曉等[6]認為，虛擬機的調度應該綜合考慮多方面的原因，尤其是用戶的需求和云內計算資源的利用情況，并為此構建了一種基于多要素聚類的虛擬機調度方案。劉進軍和趙生慧[7]的研究結論顯示，物理服務器上的負載狀況對于虛擬機資源的分配有著重要影響，基于服務器負載去構建虛擬機調度策略才能真正提高云端的計算效率。王光波等[8]針對云計算中虛擬機部署問題，提出了一種基于架構負載感知的虛擬機聚簇部署算法。

大量的虛擬機調度和部署方面的研究成果，極大地推動了云計算技術走向成熟。當前，一個新的熱點研究就是從單個虛擬機資源的部署轉變到包含多個虛擬機資源的虛擬機簇的部署[9-10]。本文將在過程研究成果的基礎上，借助全局優化算法中的動態規劃方法，對虛擬機簇的部署問題展開研究。

1　虛擬機簇和云計算整體架構

為了便于明確本文研究在云計算領域中的位置，以及明確本文的核心研究內容，先對虛擬機簇的概念以及云計算任務配置的整體架構進行闡述[11-12]。

簇，本身就帶有集合的含義[13]。所以，虛擬機簇實際上就是多個虛擬機構成的集合。當然，能夠進入一個虛擬機簇的虛擬機，彼此之間應該有著某種聯系，或者同時符合了進入該虛擬機簇的條件。虛擬機簇的聚集和部署，必然要依賴構成云的硬件架構。在一個云端的數據處理過程中，參與進來的硬件資源包括：服務器主機、刀片中心、機架，數據中心等，這些硬件資源按照處理能力和在云端所處位置的差異，一般分屬于不同的層次，其結構如圖1所示。

圖1　云數據處理的硬件架構

在圖 1中，云數據處理的硬件架構被分為 4個層次，每個層次中硬件設備的數量是不固定的。虛擬機的聚簇和部署要根據任務的實際需要，分別部署在服務器主機上、刀片中心上、機架上、及數據中心上，無論在哪個層次上部署，虛擬機必須達成和硬件資源的匹配。

2　基于動態規劃的虛擬機聚簇方法

實際上，為了提高云數據處理的效率和提高云端的服務質量，如何將性能近似的虛擬機資源聚集在一起并和硬件資源實現協調的配置是關鍵，這本身是一個云端計算資源的全局優化問題。為此，本文將一種全局優化理論應用于云端的虛擬機聚簇之中，提出了基于動態規劃的虛擬機聚簇方法。

2.1動態規劃理論

動態規劃全局優化理論，是典型的將復雜問題拆解并通過多個階段決策來實現的方法。對于拆解的各個階段，用變量k表示，對應于第k個階段的狀態可用變量 xk表示。每執行一個階段的優化，整個系統的狀態就會發生一次改變，決定系統狀態如何向下一階段改變的策略稱之為決策，用變量 uk表示。這樣，一個系統實現全局優化的問題就變成了一個系統全部階段狀態轉換的判斷準則設計問題，對應會形成一個全局優化函數，即：

其中，n代表系統執行全部過程可以拆分的階段總數； vj表示每一個階段的判斷準則函數；Vk,n表示全局判斷準則函數。

動態規劃全局優化理論，具有一個重要特點，就是根據全局優化策略判斷當前狀態的決策以后，后續狀態不再受當前狀態的影響，這也是動態規劃理論中典型的無后效性。動態規劃的準則函數具有可分性，即：

2.2虛擬機聚簇

要解決云數據處理中的虛擬機聚簇問題，就需要依托虛擬機的各種屬性和狀態，構建有針對性地動態規劃全局優化函數。因為聚簇問題，就是要尋找各方面屬性接近的虛擬機構成一個集合，以便為同類問題服務。所以，先對云處理系統中可用的虛擬機進行排序，其排序是根據各個虛擬機屬性差異最小的原則進行的。據此，為每個虛擬機構建一個如下的性能判斷函數，即：

其中，Num表示與此虛擬機通信的其他虛擬機數目；Bw表示此虛擬機需要的帶寬總量；Load表示此虛擬機已經承擔的負載情況；Hard表示此虛擬機和服務器主機等硬件設施進行匹配時所需的硬件資源；αi表示每一種子屬性在總屬性之中的權重。

Bw的計算為：

其中，bwi表示第i個和此虛擬機通信信道所需的帶寬；k表示與此虛擬機聯系的所有其他虛擬機的數目。

Hard的計算為：

其中，CPU表示此虛擬機需要硬件匹配的 CPU主頻高低；REM表示此虛擬機需要硬件匹配的內存大小；STO表示此虛擬機需要硬件匹配的硬盤大小。

根據式(3)所構建的排序判斷公式，云端所有可以利用的虛擬機資源就可以按照屬性差異的大小進行一個升序的排列，從而形成一個按順序排列的虛擬機屬性集合

依托動態優化全局優化策略實現虛擬機聚簇，其核心思路就是從中尋找處于中間位置的虛擬機，然后逐漸向兩端搜索與其各方面差異最小的虛擬機聚集成簇。這個決策函數為：

至此，構建出依托于動態規劃全局優化策略的虛擬機聚簇判斷準則函數，即：

其中，Xk和Uk的計算分別如式(3)和式(6)。

2.3虛擬機聚簇算法的流程

基于動態規劃全局優化的虛擬機聚簇算法的基本流程如圖2所示，具體步驟如下：

步驟 1. 設置虛擬機屬性判斷函數，如式(3)所示，計算云端可利用的每一個虛擬機屬性。

步驟2. 對云端所有可以利用的虛擬機，按照屬性高低進行升序排列。

步驟3. 構建用于聚簇判斷的動態規劃全局優化函數。

步驟4. 選擇升序集合中處于中間位置的虛擬機，作為聚簇的起始位置。

步驟5. 執行動態規劃優化的聚簇處理，從兩個方向判斷臨近虛擬機是否符合聚簇條件。滿足聚簇條件的，將臨近虛擬機設置為下一階段判斷的起始位置，繼續執行聚簇判斷。不滿足聚簇條件的，將臨近虛擬機納入候選虛擬機集合，繼續判斷下一個虛擬機是否滿足聚簇條件。

步驟6. 不斷更新虛擬機的狀態，重復步驟5，直到升序集合和候選集合中的所有虛擬機都執行了聚簇判斷。

步驟7. 將形成聚簇的虛擬機歸并為一個簇，用于后續和硬件資源的匹配。沒有納入此簇的其他虛擬機，可以重新執行一個新的聚簇處理，或留用待命。

圖2　虛擬機聚簇算法流程

3　實驗結果與分析

通過如下的實驗過程驗證本文提出的虛擬機聚簇方法的有效性。實驗仿真平臺選用云計算性能測試常用的軟件CloudSim。在CloudSim平臺下，云數據處理硬件結構的數據中心，主要依托于采取的機架數目。以一個機架配置 8個刀片中心、一個刀片中心配置16臺服務器主機的模式設置。一個數據中心下的服務器主機數量就是 128個，兩個數據中心下的服務器主機數量就是256個，3個數據中心下的服務器主機數量就是 512個，以此類推。在虛擬機的設置方面，設置10種類型的虛擬機，其CPU主頻、內存、硬盤等硬件的匹配需求，如表1所示。

表1　虛擬機的設置

虛擬機和其他虛擬機通信的帶寬需求以及虛擬機上的實際負載情況，是根據系統設置的隨機指令更替系統而隨機發生變化的，以模擬云端實際虛擬機的使用情況。這種隨機變化，也就為后續的動態規劃聚簇提供了可以判別的依據。對應于硬件資源，每一個數據中心配置500個虛擬機，500個虛擬機都按照表1的方式分為10類，每類50個虛擬機。

分別按照Greedy算法、啟發式算法、本文提出的動態規劃聚簇方法執行虛擬機的聚簇處理，考察這 3種方法形成聚簇效果的時間差異，結果如圖3所示。

圖3　三種方法的聚簇時間對比

從圖 3中可以看出，本文方法和啟發式方法的聚簇時間都是增加幅度由快變慢，且本文方法在聚簇的絕對時間上明顯偏低，實現2 000個虛擬機的聚簇，僅僅花費了3.2 s，而啟發式方法則花費了近10 s。Greedy聚簇算法雖然起初的聚簇時間較低，但之后增長趨勢越來越明顯，實現2 000個虛擬機的聚簇，時間消耗達到了11.3 s。可見，3種方法的聚簇時間對比，明顯證實了本文方法的聚簇速度更快。

聚簇對云數據處理效率的提升是否有益，一般通過跳數來進行衡量。如果聚簇合理，虛擬機之間的通信就會相對穩定，跳變發生的次數少，跳數也偏低，這有利于云數據高效處理。反之，跳數越高，聚簇越不穩定，云數據處理的效率也就會大大降低。3種方法聚簇后的跳數比對如圖4所示。

圖4　3種方法聚簇的跳數對比

從圖4中可以看出，3種方法形成的聚簇效果比對，本文的方法最為理想，其跳數隨著聚簇虛擬機數量的增加出現的數量最少，最有利于云數據處理過程穩定地實現。

4　結　論

隨著云計算的發展和逐步成熟，在云端實現大數據處理的計算任務越來越多。原本針對虛擬機部署的執行策略，已經逐步向多個虛擬機形成的虛擬機簇進行部署的執行策略轉變。本文針對虛擬機如何實現有效聚簇來展開研究, 依托虛擬機簇的構建原理和云數據處理的普適性硬件結構，引入一種動態規劃的全局優化策略，以實現虛擬機的聚簇處理。整個聚簇過程的實現，首先設置虛擬機的屬性判斷函數，進而執行升序排序處理，然后執行動態規劃全局優化判斷策略，從升序集合的中心位置開始向兩個方向進行聚簇。實驗結果表明，本文構建的基于動態規劃的聚簇方法，不僅實現了虛擬機資源的快速聚簇，而且聚簇的效果也比較合理，對于云數據處理過程穩定的實現是有益的。

[1] Jayasinghe D, Pu C, Eilam T, et al. Improving performance and availability of services hosted on IaaS clouds with structural constraint-aware virtual machine placement [C]//2011 IEEE International Conference on Services Computing. Piscataway: United States, 2011: 72-79.

[2] 楊博, 劉大有, Liu J M, 等. 復雜網絡聚類方法[J].軟件學報, 2009, 20(1): 54-56.

[3] Gupta R, Bose S K, Sundarrajan S, et al. A two stage heuristic algorithm for solving the server consolidation problem with item-item and bin-item incompatibility constraints [C]//SCC 08: Proceedings of the 2008 IEEE International Conference on Services Computing. Piscataway: United States, 2008: 39-46.

[4] Calheiros R N, Ranjan R, De Rose C A F, et al. CloudSim: a novel framework for modeling and simulation of cloud computing infrastructures and services, Grids-Tr-2009-1 [R]. Melbourne Australia: the University of Melbourne, Grid Computing and Distributed Systems Laboratory, 2009.

[5] 李強, 郝沁汾, 肖利民, 等. 云計算中虛擬機放置的自適應管理與多目標優化[J]. 計算機學報, 2011, 34(12): 2253-2264.

[6] 何東曉, 周栩, 王佐, 等. 復雜網絡社區挖掘——基于聚類融合的遺傳算法[J]. 自動化學報, 2010, 36(8): 1160-1170.

[7] 劉進軍, 趙生慧. 面向云計算的多虛擬機管理模型的設計[J]. 計算機應用, 2011, 31(5): 1417-1422.

[8] 王光波, 馬自堂, 孫磊, 等. 基于架構負載感知的虛擬機聚簇部署算法[J]. 計算機應用, 2013, 33(5): 1271-1275.

[9] Rana S, Jasola S, Kumar R. A hybrid sequential approach for data clustering using K-means and particle swarm optimization algorithm [J]. International Journal of Engineering, Science and Technology, 2010, 2(6): 167-176.

[10] Zhou W Y, Yang S B, Fang J, et al. Vmctune: a load balancing scheme for virtual machine cluster using dynamic resource allocation [C]//Grid and Cooperative Computing (GCC), 2010 9th International Conference on. IEEE, 2010: 81-86.

[11] Cui L, Li B, Zhang Y Y, et al. Hotsnap: a hot distributed snapshot system for virtual machine cluster [C]// Proceedings of the 27th International Conference on Large Installation System Administration, 2013: 59-74.

[12] 趙銀亮, 朱常鵬, 韓博, 等. 以虛擬機為核心實現動態行為調整的方法[J]. 西安交通大學學報, 2013, 47(6): 6-11.

[13] 孫鵬劼, 翟奮樓, 劉東旭, 等. 基于Web的拉絲模仿真系統開發與研究[J]. 圖學學報, 2013, 6(6): 106-109.

Clustering Method of Virtual Machine in Cloud Computing Based on Dynamic Programming

Zhu Yanjun
(Department of Computer Engineering, Dongguan Polytechnic, Dongguan Guangdong 523808, China)

Fast and efficient implementation of multiple virtual machine cluster is greatly significant to enhance processing ability of cloud computing. In this paper, a new clustering method is proposed for virtual machine with general principle of virtual machine cluster and dynamic programming strategy. First, all virtual machine resources are performing in ascending order according to default discriminant function. Second, virtual machine at center position of ascending set is selected as starting point of clustering, and dynamic programming strategy begins from two directions. Clustering principles are based on dynamic programming criterion. Experimental results show that cluster method based on dynamic programming has a fast speed and a stable effect.

virtual machine; clustering; cloud computing; dynamic programming

TP 393

A

2095-302X(2015)06-0955-05

2015-06-25；定稿日期：2015-07-21

2014年度東莞職業技術學院院級科研基金資助項目(2014b05)；東莞市高等院校、科研機構科技計劃一般項目(2014106101037，2014106101033)；東莞職業技術學院政校行企合作開展科研與服務資助項目(ZXHQ2014d010)；廣東省省級科技計劃項目(2014A010103002)

祝衍軍(1982–)，男，湖南邵陽人，工程師，碩士。主要研究方向為云計算、商業智能。E-mail：zhuyanjunhn@126.com