丁 順，陳世平

?

云計算中基于包簇映射的多目標蟻群資源分配算法

丁 順１，陳世平２

（1. 上海理工大學光電信息與計算機工程學院，上海 200093；2. 上海理工大學信息化辦公室，上海 200093）

云計算環(huán)境中，虛擬機放置就是將虛擬機映射到物理機的過程，一個最優(yōu)的放置策略對于提高計算效率和資源利用率是非常重要的。本文中將云計算環(huán)境下虛擬機放置問題作為多目標組合優(yōu)化問題進行闡述，提出一種多目標蟻群優(yōu)化方法，同時優(yōu)化運營成本和資源浪費，并將其應用到包簇拓撲結構中，目標是有效地獲得一組非支配解，同時最大限度地減少總資源浪費和營運成本。實驗將該算法與現(xiàn)有的多目標遺傳算法（MGA）和三種單目標算法進行比較。結果表明，本文所提出的算法比其它算法可以達到更優(yōu)的效果，實現(xiàn)兩個目標的折衷。

云計算；多目標優(yōu)化；支配解；蟻群算法

0 引言

近年來，云計算逐漸成為一個流行的商業(yè)計算模型，它可以通過互聯(lián)網(wǎng)來托管和交付服務[1]。云計算主要有三種類型：基礎設施即服務（IaaS）、平臺即服務（PaaS）和軟件即服務（SaaS）。云計算平臺的使用和部署有許多優(yōu)點，例如可靠性、服務質量和健壯性[2]。對于消費者來說，云似乎是無限的，而且消費者可以購買到滿足他們需求的計算力并且響應時間快。從提供者的角度來看，關鍵問題是通過最小化運營成本來最大化利潤，在這個方面，云數(shù)據(jù)中心的電力管理就變得至關重要了，因為它影響了運營成本。此外，大規(guī)模計算機系統(tǒng)的能耗還引發(fā)了許多其它嚴峻的問題，包括二氧化碳和系統(tǒng)的可靠性。云計算的出現(xiàn)在過去的幾年里對信息技術行業(yè)產(chǎn)生了巨大的影響，像亞馬遜、谷歌、IBM、微軟以及Oracle等大公司已經(jīng)開始在世界各地建立新的托管云數(shù)據(jù)中心來提供冗余度以及確保在應用出錯的情況下的可靠性。

云計算中的資源分配就是虛擬機映射到物理機的過程，目前大多數(shù)關于虛擬機放置的研究都集中在一個標準上，然而許多現(xiàn)實問題需要考慮多個標準。基于這個原因，最近的研究傾向于關注多目標的情況。因此，在本文中將云計算環(huán)境下虛擬機放置問題作為多目標組合優(yōu)化問題進行闡述，提出一種多目標蟻群優(yōu)化方法，同時優(yōu)化運營成本和資源浪費，并將其應用到包簇拓撲結構中[3]，旨在為大規(guī)模數(shù)據(jù)中心處理提供一種有效的解決方案。通過實驗對該算法的性能與多目標遺傳算法（MGA）和三種單目標算法的性能進行了比較，結果表明該算法比其它算法有更好的效果。

1 研究基礎

目前關于云計算資源調度的研究主要有：以提高資源利用率為目標的資源分配策略、以降低數(shù)據(jù)中心能耗為目標的資源分配策略以及基于經(jīng)濟學模型的資源調度。文獻[4]通過監(jiān)控虛擬機的狀態(tài)，當虛擬機負載減少時降低處理器的速度來降低能耗。但提出的策略并沒有建立能耗減少和應用性能的關系，降低能耗后可能會對應用性能造成不良的影響。文獻[5]提出兩級調度器：元調度器和虛擬機調度器，通過擴展Cloudsim類庫實現(xiàn)啟發(fā)式調度算法來提高云計算系統(tǒng)的資源利用率。文獻[6]設計一個基于遺傳基因的價格調節(jié)算法來處理市場的供需平衡，但該方法目前只考慮CPU資源，而對內(nèi)存以及帶寬等資源并沒有涉及。文獻[7]提出了云計算中虛擬機放置的自適應管理框架，提出了帶應用服務級目標約束的虛擬機放置多目標優(yōu)化遺傳算法，用于制定框架中的虛擬機放置策略，但是沒有考慮能耗問題，沒有將資源控制和能耗控制結合起來。

目前云計算中虛擬機放置研究工作雖然取得一定的效果，但是還是存在一些問題。第一，大多數(shù)關于虛擬機放置的研究都集中在一個標準上，這樣得到的最優(yōu)放置也只是某一定條件的最優(yōu)解，無法進行各準則下最優(yōu)放置的相互比較，然而由于云計算環(huán)境的復雜性，單從一個方面的改進并不能很好的滿足云資源調度的要求，許多現(xiàn)實問題需要考慮多個標準并進行權衡和折衷。第二，目前大多數(shù)調度算法的計算量很大并且缺少普遍性，從而造成用戶的等待時間太長，用戶滿意度低。本文通過對營運成本和資源浪費兩個目標的優(yōu)化，將提出的多目標蟻群算法應用到包簇的拓撲結構中并且取得很好的效果。

1.1 多目標進化算法

多目標進化算法（MOEAs）是一種隨機優(yōu)化方法，通常是使用基于群體的方法去找到Pareto最優(yōu)解[8]。大多數(shù)現(xiàn)有的MOEAs在選擇的時候使用的是支配的概念，因此，我們只關注基于支配的MOEAs這一類問題?！爸洹备拍畹亩x如下，在不失一般性的情況下，用m個決策變量參數(shù)和n個目標函數(shù)來描述多目標最小化問題。

所有沒被其它點支配的點都成為非支配點，通常情況下，在解空間中非支配點聚集在一起構成了一個面，并且它們經(jīng)常被認為是代表一個非支配面。根據(jù)定義，在目標空間中，非支配面上的點不會被其它點所代替。因此它們是Pareto最優(yōu)點（它們組成了Pareto最優(yōu)面），相應的變量向量被稱為Pareto最優(yōu)解。

上面的概念還可以通過擴展去找到一個非支配解集。讓我們假設一個解集中有N個解，每個解都有M個目標函數(shù)值，在我們接下來的工作中，使用以下步驟來找到非支配解集[11]。

1）初始化i=1

4）如果解集中的解遍歷完，進入到步驟5，否則i加1，進入步驟2

5）所有未標記為支配解的都是非支配解

1.2 包簇分配模型

云計算數(shù)據(jù)中心傳統(tǒng)資源管理方法以虛擬機為中心（VM-Centric）來設計資源分配模型，使用扁平、細顆粒度的資源分配方式。而這種細粒度的管理模型會導致所要解決的計算問題規(guī)模巨大，對虛擬機固定的資源分配也不利于資源共享。

為了突破這些限制，文獻[3]提出一種包簇資源分配框架，通過分層的抽象模型來降解問題的規(guī)模。其中“包”為虛擬機或其他包的集合。這是個遞歸定義，一個大包可以是許多小包的集合，而這些小包可能是虛擬機的集合，也可能是更小包的集合。一個資源共享的虛擬機組合被模塊化為需求包，而多個包又進一步被抽象稱一個更高級別的包，進而由虛擬機與包構成一個層次化組織構架。“簇”為數(shù)據(jù)中心拓撲中位置相近的服務器或更低級別的簇的集合,簇所擁有的資源是其組成部分的資源之和。用包和簇來將虛擬機-服務器映射問題轉換成一系列小得多的包-簇映射問題。

2 云計算資源的目標函數(shù)構建

2.1 營運成本

2.2 資源浪費

在云計算資源調度的過程中，與其它物理資源相比，主要的能源消耗是CPU和內(nèi)存，因此在本文中，在提出的包簇映射算法中我們只關注CPU和內(nèi)存這兩種資源，并且如果需要，該算法也可以通過擴展去支持其它資源優(yōu)化。由于每個簇（服務器）上的剩余資源可能會因為不同的包簇映射策略而不同。因此，為了充分利用多維資源，下面的公式用于計算調度過程中資源浪費的潛在成本。

其中約束如下：

3 多目標蟻群算法描述

蟻群優(yōu)化算法是一個用于解決組合優(yōu)化的分布式算法。該算法通過模擬螞蟻的覓食過程完成調度。首先，螞蟻隨機選擇一條路徑，當這個螞蟻達到預期目標時，它們計算這條路徑的適應度，螞蟻根據(jù)適應度在路徑上設置信息素。最后，為了將螞蟻集中到高適應度的路徑上，并盡可能快的找到最優(yōu)解，需要進行信息素更新和行為選擇。

3.1 信息素定義

3.2 行為選擇的轉移概率

3.3 適應度函數(shù)

當一個螞蟻經(jīng)過所有的簇后就形成了一條路徑，這條路徑就是問題的可行解。為了確保解的質量，避免陷入局部最優(yōu)狀態(tài)，而是盡可能保證或得到的解釋全局最優(yōu)解，因此使用一個適應度函數(shù)來評價解的優(yōu)劣性。在優(yōu)化模型問題的基礎上，需要對適應度函數(shù)進行定義。根據(jù)文中的調度優(yōu)化模型，其中給出了兩個調度目標并將成本最小化。因此公式8的適應度函數(shù)也就是評價函數(shù)。

3.4 信息素更新

如果路徑的適應性很高，那么此路徑的信息素就應該加強，從而讓更多的螞蟻找到這條路徑。因此，有必要更新路徑上每個點的信息素，更新規(guī)則如公式：

其中Q是一個常數(shù)，它的值被取為100。F(x)和B(x)的值越小，信息素的增量就越大。好的解會被信息素的更新而，同時差的解也會被信息素的更新而減弱。經(jīng)過幾次迭代后，越來越多的螞蟻將趨向于最佳路徑。信息素蒸發(fā)因子是用來防止獲得到解只能達到局部最優(yōu)。

3.5 算法流程

1）初始化包簇信息素、迭代系數(shù)、確定各個子目標函數(shù)權重。

2）螞蟻開始循環(huán)，k++

3）隨機散布若干只螞蟻并建立搜索空間

4）計算每只螞蟻移動到下一個節(jié)點的概率，螞蟻根據(jù)計算結果移動到相應的節(jié)點上

5）當螞蟻移動到新節(jié)點后，更新其經(jīng)過路徑的信息素，并對禁忌表進行相應的修改

6）重復執(zhí)行3）~5），直到整個蟻群中的每個個體均找到一個可行路徑為止

7）根據(jù)云計算資源調度問題的目標函數(shù)對所有可行路徑進行評價，并選擇當前最優(yōu)路徑

8）對所有路徑上的信息素進行全局更新操作

9）迭代次數(shù)增加，如果迭代次數(shù)達到最大迭代次數(shù)，則停止搜索，得到云計算資源調度問題的最優(yōu)解

3.6 實驗結果與分析

為了驗證本文所設計的蟻群優(yōu)化算法的可行和有效性，本文采用 Cloudsim[12]平臺來進行仿真，我們模擬了一個數(shù)據(jù)中心，它里面具有不同數(shù)量的異構服務器，每個服務器的處理器：1000、2000、3000 MIPS，內(nèi)存：1T，RAM：8 GB。每個虛擬機對資源的要求為內(nèi)存：1 GB，RAM:128 GB，CPU：250、500、750或1000 MIPS。在基于包簇的框架下，我們先對虛擬機逐層劃分包結構，直到底層的虛擬機；同樣的，也對服務器劃分簇機構。我們用不同的參數(shù)對相同的輸入進行多次測試，從而找到問題的最優(yōu)參數(shù)。我們將α，β，ρ，迭代次數(shù)，螞蟻個數(shù)分別設置為1，2，0.5，10，5。遺傳算法的迭代次數(shù)也設置為10，種群的規(guī)模為200，Pareto分數(shù)為0.7，遷移時間間隔為20，遷移率為0.2。

我們使用降序首次適應算法（FFD）、動態(tài)電壓調整（DVFS）、邏輯回歸（LR）、蟻群算法（ACO）和遺傳算法（GA）這五種算法分別測量了包簇映射的營運成本和資源浪費量。FFD算法是一種單目標算法，在該算法中，虛擬機根據(jù)請求的利用率進行排序，并將其放入到第一個具有足夠資源的物理機中。DVFS是一種電功率管理技術，它通過切割設備的頻率來最小化設備的能耗。從而使設備的性能保持穩(wěn)定。在Cloudsim中，DVFS被用在一個功率感知數(shù)據(jù)中心，其中虛擬機被分配給第一個具有足夠資源的服務器。LR方法通過對數(shù)據(jù)子集進行回歸擬合來建立一個評估原始數(shù)據(jù)的曲線。為了通過另一種方法來評估我們的ACO多目標方法，我們在具有相同目標函數(shù)的Matlab Optimization工具箱中使用了GA。模擬結果的數(shù)值如表2所示，在這個表中，我們使用了不同數(shù)量的簇，多個包以及不同數(shù)量的任務。在運營成本、資源浪費率等方面，使用不同的虛擬機放置算法進行比較。

表1 基于包簇映射結果的比較

Tab.1 Comparison of results based on package cluster mapping

圖1表示的是不同的算法在運營成本上的比較。由結果可知，F(xiàn)FD算法產(chǎn)生的成本最大，原因是虛擬機映射到第一個可用的服務器的排序機制沒有考慮到其它服務器中可用的資源。圖2中表示的是不同的算法在資源浪費上的比較。MACO算法嘗試使用所有可用的簇來映射所有的包。結果表明，在所有的目標中MACO可以找到比MGA更好的解決方案。在30個簇、40個包、50個任務中，我們可得到FFD、DVFS、LR、MACO和MGA這四個算法的資源浪費率分別為40%、1.67%、3.33%、0%、21.66% 。在使用FFD的25個簇中，有40%的資源沒有被利用，而對于使用MACO的12個簇中，所有的可用資源完全被利用。

圖1 營運成本比較

圖2 資源浪費比較

4 結語

針對云計算環(huán)境的復雜性，特別是云資源動態(tài)變化的不確定性，本文提出一種多目標集成的蟻群算法，算法從營運成本和資源浪費兩個目標進行優(yōu)化。通過與單目標和多目標算法進行比較，實驗結果表明，該算法能夠在使營運成本低、資源浪費少的情況下有效地進行資源調度，是一種可行的、有效的資源調度算法。下一步的工作是結合機器學習算法進一步優(yōu)化。

[1] Randles M, Lamb D, Odat E, et al. Distributed redundancy and robustness in complex systems[J]. Journal of Computer & System Sciences, 2011, 77(2): 293-304.

[2] 盧浩洋, 陳世平. 基于包簇映射的云計算資源分配框架[J]. 計算機應用, 2016, 36(10): 2704-2709.

[3] Laszewski G V, Wang L, Younge A J, et al. Power-aware scheduling of virtual machines in DVFS-enabled clusters[C]// IEEE International Conference on CLUSTER Computing and Workshops. IEEE, 2009: 1-10.

[4] Jeyarani R, Ram R V, Nagaveni N. Design and Implementation of an Efficient Two-Level Scheduler for Cloud Computing Environment[C]// Ieee/acm International Conference on Cluster, Cloud and Grid Computing. IEEE, 2010:585-586.

[5] You X, Xu X, Wan J, et al. RAS-M: Resource Allocation Strategy Based on Market Mechanism in Cloud Computing[M]. IEEE Computer Society, 2009.

[6] Buyya R, Beloglazov A, Abawajy J. Energy-Efficient Management of Data Center Resources for Cloud Computing: A Vision, Architectural Elements, and Open Challenges[J]. Eprint Arxiv, 2010, 12(4): 6-17.

[7] Ikeda M, Barolli L, Koyama A, et al. Performance evaluation of an intelligent CAC and routing framework for multimedia applications in broadband networks[J]. Journal of Computer & System Sciences, 2006, 72(7): 1183-1200.

[8] Deb K, Miettinen K. Multiobjective Optimization: Interactive and Evolutionary Approaches[M]. Springer-Verlag, 2008.

[9] K. Deb, Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, 2001.

[10] Deb K.Multi-objective genetic algorithms: problem difficultiesand construction of test problems.[J]. Evolutionary Computation, 2014, 7(3): 205-230.

[11] 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[J]. Computer Science, 2009.

[12] 師雪霖, 徐恪. 云虛擬機資源分配的效用最大化模[J]. 計算機學報, 2013, 36(2): 252-262.

[13] 錢瓊芬, 李春林, 張小慶, 等. 云數(shù)據(jù)中心虛擬資源管理研究綜述[J]. 計算機應用研究, 2012, 29(7): 2411-2415.

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

Multi-object ant Colony Resource Allocation Algorithm Based on Package Cluster Mapping in Coud Computing

DING Shun1, CHEN Shi-ping2

(1. School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China; 2. Network and Information Center Office, University of Shanghai for Science and Technology, Shanghai 200093, China)

In the cloud computing environment, virtual machine placement is the process of mapping a virtual machine to a physical machine. An optimal placement strategy is very important for improving computational efficiency and resource utilization. In this paper, the problem of virtual machine placement in cloud computing environment is described as a multi-objective combinatorial optimization problem. A multi-objective ant colony optimization method is proposed, which optimizes the operation cost and resource waste at the same time and applies it to the cluster topology. Effectively get a set of non-dominated solutions while minimizing the total waste of resources and operating costs. The experiment compares the algorithm with the existing multi-objective genetic algorithm (MGA) and three single-objective algorithms. The results show that the proposed algorithm can achieve better results than other algorithms and achieve the compromise between the two objectives.

Cloud computing; Multi-objective optimization; Non-dominated solutions; Ant colony algorithm

本研究獲得國家自然科學基金項目(61472256、61170277); 上海市一流學科建設項目( S1201YLXK);上海理工大學科技發(fā)展基金(16KJFZ035、2017KJFZ033); 滬江基金(A14006)等資助。

丁順，碩士，主要研究領域：計算機網(wǎng)絡、云計算；陳世平，教授，主要研究領域：計算機網(wǎng)絡、分布式計算、云計算。

TP3

A

10.3969/j.issn.1003-6970.2018.11.001

丁順，陳世平. 云計算中基于包簇映射的多目標蟻群資源分配算法[J]. 軟件，2018，39（11）：01-06