基于蟻群算法的虛擬機雙目標優化部署方法

裴 多

(重慶市綜合經濟研究院 信息化研究中心，重慶 401147)

0 引 言

云計算的核心技術包括靈活接入的移動終端、硬件技術、海量存儲技術、虛擬化技術以及分布式并行計算。云平臺靈活高效地資源配置和管理得益于上述各種技術的成熟。其中，虛擬化技術實現對數據中心存在的零散資源進行有效整合，并對虛擬化后的抽象資源進行統一管理、配置和監控，一定程度上改善了云服務提供商資源利用率低和運營成本高的問題。然而，虛擬機的放置是一個從虛擬機到物理主機映射的過程，虛擬機的放置優化問題，是多個目標相互作用相互影響，復雜困難的組合優化問題，因此，解決多目標虛擬機部署策略是云數據中心提高資源利用率[1]和節省能耗[2]的關鍵。Liu等[3]提出了基于蟻群算法的虛擬機放置算法，該算法通過減少物理服務器的運行數量以及提高物理資源的利用率來降低系統的能耗問題。文獻[4]則采用生物物理學的優化方法來放置虛擬機，通過該方法減少資源的浪費以及能耗。文獻[5]提出了基于緩存競爭意識的虛擬機放置算法。

線性規劃方法是虛擬機放置的傳統分析方法。Chen等[6]采用整數線性規劃來對虛擬機的放置與遷移進行求解，用于解決云中虛擬機整合時帶來的緩存競爭問題。文獻[7]以提高鏈路利用率為目的，采用線性規劃來描述路線分配問題，并提出基于多項式時間的虛擬機放置的啟發式算法。此外，文獻[8]也采用整數線性規劃來描述了面向服務的虛擬機放置問題，并使用樹算法來得到虛擬機的放置方案，從而降低通信成本以及建設成本。

遺傳算法是另外一種虛擬機放置優化算法。Tang等[9]提出了基于遺傳算法的虛擬機放置算法，該算法綜合考慮了物理機器以及通信網絡帶來的能源消耗問題。同時，為提高遺傳算法的效率，提出了混合的遺傳算法。文獻[10]研究了動態環境下面向代理服務器的虛擬機放置問題，綜合考慮了變化的資源供應、提供商的定價以及租戶的動態需求三方面因素，使用遺傳算法得到高質量的可伸縮性強的放置方案。

約束規劃方法也被用于虛擬機放置。為提高數據的安全性，文獻[11]通過研究分析數據存在的安全隱患來構建信息泄露約束條件，在保證滿足該約束條件下進行虛擬機的放置。由于之前的虛擬機放置研究沒有考慮物理機器擁有多個處理器的情況，導致單個物理機器的調度變得更加復雜。因此，文獻[12]采用約束規劃來描述物理機器中多個處理機的調度問題，并使用改進后的約束規劃方法求解虛擬機的放置問題。

虛擬機部署策略經常被描述為向量裝箱問題的變體問題，這是一個NP-hard問題。為了解決這個問題，各種啟發式算法被提出。Li等[13]在虛擬機放置問題時，考慮了由網絡通信量以及物理機器的利用造成的開銷，采用基于二進制搜索算法來確定所需物理機器的個數以及放置問題。文獻[14]提出了基于信息改進的煙花算法(IEFWA)。作者以降低數據中心的能耗問題為目的，結合IEFWA算法與基于生物地理學的優化算法(BBO)來求解虛擬機的放置問題。

上述研究成果都把虛擬機部署策略用單一目標實現，然而在云數據中心，為了提高資源利用率和降低能耗，需要考慮多個優化目標。因此，本文提出了基于蟻群智能的虛擬機多目標優化部署策略，首先給出多目標優化問題的描述，然后建立優化目標函數，采用蟻群算法對雙目標函數求解，最后與降序首次適應算法進行實驗驗證。

1 蟻群算法

1.1 基本蟻群系統的機制原理

基本蟻群算法的優化機理包括兩個階段：適應階段和協作階段。首先是適應階段，每只螞蟻依據自己對信息的累積選擇和調整其認為最優的路徑，路徑上的信息量越大，說明選擇該路徑的螞蟻越多；在協作階段，螞蟻之間通過信息素共享信息，以便產生更能優化性能的解，與自動機的學習機理一致。

1.2 基本蟻群系統的數據模型

螞蟻在探索路徑的過程中，依據各條路徑上信息量的多少決定其跳轉的方向。禁忌表tabk用于標記第k只螞蟻已經走過的元素，隨著螞蟻對路徑的不斷探索，禁忌表tabk進行動態調整。在向最優路徑進化的過程中，螞蟻依據各條路徑上積累的信息量和路徑的自身的啟發信息來權衡當前路徑是最優路徑的概率。

1.3 改進的蟻群算法

蟻群系統具有方便和其它算法相結合，較強的魯棒性等優點，但是算法探索時間長、容易收斂于局部最優解是尤為明顯的缺點。

精英策略的螞蟻系統[15](elitist ant system，EAS)，基于排列的螞蟻系統[16](rank-based AS，ASrank)，最大最小螞蟻系統[17](MAX-MIN ant system，MMAS)都對AS進行了少量的修改而獲得了更好的性能。1997年，螞蟻算法的創始人M.Dorigo又提出了一種具有全新機制的蟻群算法[18](ant colony system，ACS)，這是蟻群算法發展史上的又一新突破。

ACS和AS之間存在以下3方面的不同：

(1)采用一種偽隨機比例規則確定下一個要選擇的元素，在開發當前路徑與探索新路徑之間權衡。

(2)信息素全局更新規則只在當前探索的最優路徑上消耗與釋放信息素。

(3)螞蟻每次跳轉到一個元素后，按照信息素局部更新規則，都會揮發該邊上一定量的信息素，以此來增大其它螞蟻探索剩余路徑的概率。

與AS相比，蟻群系統ACS重新定義了狀態轉移規則，信息素全局更新規則以及信息素局部更新規則。

(1)狀態轉移規則

一只位于元素i的螞蟻要確定下一個移動到的元素，應用式(1)和式(2)給出的規則，即偽隨機比例規則

(1)

其中

(2)

式中：η(i,j)為啟發函數，代表螞蟻從元素i跳轉到元素j的期望程度值。β為期望啟發式因子，用于調整啟發信息在路徑選擇時的重要性，反映出螞蟻在探索路徑的過程中啟發信息在螞蟻選擇路徑中的受重視程度，β值越大，表示螞蟻偏向于貪心規則選擇路徑的可能性越大。集合(C-tabk)是第k只螞蟻下一步可以選擇的元素集合。q為在[0,1]區間均勻分布的隨機數，q0是決定了利用先驗知識與探索新路徑之間的相對重要性。

(2)信息素全局更新規則

ACS運用了更加大膽的規則確定路徑上的信息，即只增大全局最優路徑上的信息素

τij(t)=(1-ρ)×τij+ρ×Δτb(i,j)

(3)

其中

(4)

式中：ρ是信息素揮發參數，取值范圍為：0<ρ<1，Cb為從尋路開始到當前為止全局最優的路徑長度。

(3)信息素局部更新規則

ACS引入了負反饋機制，每當一只螞蟻由一個元素跳轉到另一個元素時，該路徑上的信息素將依據式(5)揮發掉一部分，實現信息素的局部更新，以此降低已經走過的路徑再次被選定的幾率

τij=(1-ξ)×τij+ξ×τ0,0<ξ<1

(5)

ACS算法[18]在搜索時間長、易陷于局部最優解兩個方面都有明顯改善。

2 雙目標優化模型的建立

虛擬機放置優化問題是一個多目標優化問題。根據前面對多目標問題描述，我們首先給出兩個優化目標：資源模型和能耗模型。

資源模型主要考慮兩種資源CPU和內存。物理主機資源利用率和虛擬機放置有很大關系，為了實現多維資源綜合利用[19]，下面給出計算資源未利用模型

(6)

式中：wj為第j臺物理主機的資源浪費率，P表示CPU資源，M表示內存資源，l是未利用資源比例，T是主機最高資源利用率。

目前研究表明能耗和CPU利用率是線性關系[20]，為了節省能耗，物理主機的能耗忽略不計。第j臺物理主機的能耗可以表示為

(7)

式中：u為資源利用率。

上面給出了資源模型和能耗模型，為了提高資源未使用利用率和降低能耗，我們建立如下目標優化函數。r表示請求資源，v表示第v臺虛擬機，S表示放置在第j臺主機上的虛擬機的集合

(8)

(9)

約束條件：①每臺虛擬機只可以放置在一臺物理主機上；②各個虛擬機請求資源的總和不可以超過最高資源利用率；③每個虛擬機的資源請求不會超過最高資源利用率。

3 雙目標優化模型求解算法描述

該小節尋找提高資源利用率和節省能耗的虛擬機放置方案，提出基于ACS雙目標虛擬機放置(bi-objective VM placement ACS，bi-OVMPACS)算法。

3.1 信息素和啟發信息定義

設有m臺虛擬機放置到n臺物理主機，為了記錄虛擬機分配到物理主機的信息素定義一個m行n列的矩陣τm×n,τij表示虛擬機i放置到主機j的信息素。在初始化階段，τm×n的值為

(10)

其中

(11)

定義矩陣ηm×n記錄虛擬機放置到主機的啟發信息，ηij表示虛擬機i放置到主機j的啟發信息。虛擬機放置到主機要同時考慮資源利用率和能耗兩個優化目標，因此

(12)

(13)

(14)

3.2 虛擬機選擇規則

根據ACS的偽隨機比例狀態轉移規則，定義虛擬機選擇規則

(15)

其中

(16)

式中：q為[0,1]之間的隨機數，q0是[0,1]之間的一個常數，α為信息素和啟發信息的相對重要程度，ppej是選擇某個虛擬機的概率，Ωj則是待放置虛擬機可以放置到主機j的集合。

3.3 信息素更新規則

信息素更新規則是影響虛擬機放置的重要部分，螞蟻經過的路徑信息素增加，同時信息素隨時間揮發，因此信息素可能增加可能減少。信息素的揮發有利于避免算法快速收斂于局部最優，同時擴大搜索空間。該算法信息素更新包括兩部分：信息素局部和信息素全局更新。

式(17)表示虛擬機i放置到主機j后信息素局部信息素更新規則，β表示局部信息素揮發參數

τij(t)=(1-β)×τij(t-1)+β×τ0

(17)

當所有的螞蟻都找到了一條路徑之后，按照上文介紹的比較規則，選擇最優路徑H進行信息素全局更新，更新規則如下

(18)

4 實驗結果與分析

4.1 蟻群行為和參數對算法性能影響的分析

在蟻群算法中，參數是影響算法求解性能和效率的關鍵因素之一。目前，蟻群算法中的參數設置暫且沒有系統的理論依據和通用的操作方法，一般情況下依據經驗和大量實驗數據確定參數值。下面就bi-OVMPACS算法中的參數α，β，γ，antNum對性能的影響進行簡要分析。

(1)參數α。信息素是表示先驗信息的載體，而啟發信息是表示未來信息的載體[21,22]。參數α并不用來影響信息素和啟發信息，而是用以控制二者之間的相互作用。根據式(15)、式(16)可知，當α=0時，演變為無信息素影響的bi-OVMPACS算法；當α=1時，演變為無啟發信息影響的bi-OVMPACS算法。

(2)參數β，γ。在蟻群算法中，各只螞蟻之間通過信息素進行合作，以增大迅速發現最優解的概率。在bi-OVMPACS算法中，參數β和參數γ都與信息素更新密切相關。信息素局部更新規則運用負反饋機理，以信息素局部更新因子β，局部調整信息素，減小再選擇已經走過路徑的概率，增大對新路徑探索的概率。信息素全局更新規則運用“精英策略”，只對當前狀況下最優路徑上的信息素進行調整，而其它路徑上的信息素不變。如果信息素全局更新因子γ過大，會造成算法的隨機性和全局搜索能力，而且已探索過的路徑再次被選定的幾率太大；如果γ太小，雖然算法的隨機性和全局探索能力有所增強，但是探索到最優路徑的時間消耗太多。

(3)參數antNum。螞蟻數antNum值大，能夠增加算法的全局探索能力和穩定性，然而antNum值太大，造成大量的曾經被確定的路徑上的信息量趨于均值，算法收斂速度減慢。反之，antNum太小，造成未來被探索的路徑上的信息量接近于0，減小了全局探索的隨機性，雖然收斂速度快，但算法的穩定性較差。

4.2 實驗參數

bi-OVMPACS算法實驗參數取值見表1。

表1 bi-OVMPACS算法實驗參數值

設置虛擬機選擇規則中的參數α=0.5，使先驗信息素和后驗信息素同等重要；信息素更新規則中的參數β=γ=0.4；根據Dorigo M等[18]的研究設置螞蟻數antNum與虛擬機數之比為2∶3；迭代次數itNum=20。

4.3 實驗結果對比及分析

為了驗證bi-OVMPACS算法對虛擬機放置目標函數的優化效果和當云數據中心有大規模虛擬機請求時的可擴展性，本文共設計了兩組實驗方案，分別為虛擬機放置優化目標對比實驗和虛擬機放置可擴展性實驗。虛擬機放置優化目標對比實驗在請求的虛擬機和負載主機情況一致的情況下，與降序首次適應算法比較兩個優化目標：能耗和資源利用率。bi-OVMPACS算法的可擴展性實驗分別在兩種不同類型虛擬機不同請求數量的情況下，對比螞蟻搜索到一條可行路徑的時間。

虛擬機放置優化目標實驗，與降序首次適應算法進行實驗對比。降序首次適應算法放置虛擬機的主要思想是，先將虛擬機從大到小排序，然后按照排列順序將虛擬機映射到主機。按主機啟用順序，如果能找到放置當前虛擬機而且是最早啟動的主機，則將當前虛擬機放置到該主機；否則，啟動另一臺主機放置當前虛擬機。FFD算法的主要的運算時間是用來對虛擬機進行排序，故其時間復雜度是O(nlogn)。

虛擬機請求實例采用3.2小節介紹的偽隨機方式產生，總共產生200個虛擬機請求。在參數P，stdCPU，stdMem一定的條件下，FFD算法與bi-OVMPACS算法虛擬機放置優化目標對比實驗，見表2。

表2 FFD算法與bi-OVMPACS算法優化目標對比實驗

上述實驗結果表明：在同等條件下，與FFD放置算法相比，bi-OVMPACS算法對虛擬機放置目標有明顯改善。當虛擬機請求的CPU和內存平均值一定時，目標函數值隨CPU和內存的相關數增大而減小，反映出不同虛擬機類型對目標函數的影響；當虛擬機請求的CPU和內存平均值不同時，目標函數隨虛擬機請求值的增大而增大。因此，bi-OVMPACS算法能夠在一定程度上實現云數據中心能耗和資源利用率同時優化的虛擬機放置問題。

bi-OVMPACS算法的可擴展性實驗，分別對比了虛擬機請求類型為25%和45%，數目從200增加到2000，參數stdP值為0.5的情況下，螞蟻探索到一條可行路徑的時間，實驗結果如圖1所示。

圖1 bi-OVMPACS算法的可擴展性實驗

上述實驗結果表明：虛擬機請求平均值為25%的探索時間少于平均值為45%，因為承載平均值為45%的虛擬機需要啟動更多的主機。隨著虛擬機請求數量的增加，螞蟻探索到一條路徑的時間可以在1 min內完成，在人們可以接受的范圍內。因此，bi-OVMPACS算法適合大規模數據中心的虛擬機放置。

5 結束語

本文首先對多目標優化問題進行了詳細描述，并且介紹了現有的幾種虛擬機放置算法，分析了它們在虛擬機放置中存在的問題，并在此基礎上綜合考慮需要優化的CPU和內存兩種資源，提出了基于蟻群智能的優化能耗和資源利用率的雙目標虛擬機放置模型。然后簡要介紹了基礎蟻群系統和改進的蟻群系統，詳細闡述了該算法的實現過程。最后，通過對比實驗，驗證了本文提出的算法在對虛擬機放置優化目標的有效性和該算法的可擴展性上具有一定的優越性。