一種能耗關鍵的公共計算環境虛擬機部署算法

朱 偉，吳傳峰，夏 興

(江蘇自動化研究所，江蘇 連云港 222061)

0 引言

水下無人平臺作為一種小型化作戰平臺,具備自主探測、定位和打擊目標的能力,這些能力的達成需一定規模的計算資源支持;另一方面,水下無人平臺受空間、能源配置限制,需統籌配置共用計算資源,并對資源的能耗提出了較高要求。公共計算環境通過提供公共的信息處理資源,具有資源共用、架構開放和健壯抗毀等顯著特點,可提升艦船裝備集成優化設計水平及信息實時處理、抗毀生存能力,提高系統開放性、裝備使用的靈活性,代表了未來艦艇電子裝備發展的方向[1]。公共計算環境可在滿足水下無人平臺信息處理對計算資源需求的同時,有效解決空間、能源受限問題。公共計算環境作為一種云環境,能耗大小與虛擬機(Virtual Machine,VM)數量、部署算法有直接的關系。

國內外眾多學者從不同角度開展了VM部署算法研究。文獻[2]為解決由非最佳VM放置導致的SLA違規問題,提出了一種基于多資源的VM放置方法,以提高CPU利用率和降低程序執行時間。文獻[3]針對CPU和內存的資源使用狀態提出了一種基于雙游標控制機制的VM部署選擇算法,在一定程度上實現了雙目標優化平衡。文獻[4]提出了一種多目標蟻群系統VM部署算法,目標是獲得Pareto最優解集,同時提高通信收入和降低服務器的功耗。文獻[5]針對數據中心能耗問題,提出了一種融合模擬退火算法的蟻群算法(ACOSA)。雖然目前的相關研究己經取得一些成果,但VM部署問題屬于NP問題,無法在多項式時間內找到最優解,VM部署方式仍有進一步優化的空間。

本文面向水下無人平臺公共計算環境能耗問題,提出了一種能耗關鍵的VM部署模型,設計了基于改進蟻群的VM部署算法來求解該模型,算法提出了負載感知概率選擇模型,改進了蟻群的路徑選擇;提出了動態信息素模型,優化了信息素更新規則,從而實現了對VM部署方式的優化,并通過仿真實驗驗證了算法的有效性。

1 問題建模

通過虛擬化技術,物理服務器可以同時運行多個VM,每個VM可以獨立運行應用程序或服務[6]。VM部署問題是在計算環境中將VM合理地分配到物理服務器上的過程[7]。VM部署的合理性可以直接影響計算資源的利用效率、性能和服務器集群能耗[8]。

1.1 相關定義

VM部署需要考慮多種因素,部署過程往往十分復雜,在研究過程中需要對其進行簡化建模處理[9]。相關定義如下[10]:

定義1

公共計算環境中所有VM的集合為V={VM1,VM2,…,VMn},n為VM數量。每臺VM表示為:

VMi=(VMCPUi,VMMemi,VMDiski,VMBwi),

(1)

式中:i為VM標識號,VMCPU為CPU需求,VMMem為內存需求,VMDisk為磁盤需求,VMBw為網絡需求。

定義2

公共計算環境中服務器節點集合為P={PM1,PM2,…,PMm},m為服務器節點數量。每個服務器節點表示為:

PMj={PMCPUj,PMMemj,PMDiskj,PMBwj},

(2)

式中:j為服務器節點標識號,PMCPU為CPU資源,PMMem為內存資源,PMDisk為磁盤資源,PMBw為網絡資源。

定義3

VM與服務器之間的映射關系可用部署矩陣θ表示。將n個VM部署到m個服務器節點上,用矩陣的形式表示如下:

(3)

式中:θij為VM與服務器PM的對應關系,若θij值為1,表示虛擬機i被部署到服務器j上;若θij值為0,則虛擬機i未被部署到服務器j上。

定義4

由部署矩陣θ得到VM與服務器之間的部署約束條件,表示如下:

(4)

前4個約束條件的物理意義為部署在服務器j上的所有VM需要的CPU資源、內存資源、磁盤資源與網絡資源總數不得超過服務器j所能提供的資源數。最后一個約束條件為部署矩陣每一行只能有一個θ為1,表示一個VM只能部署到唯一服務器上。

定義5

(5)

定義6

服務器j的綜合資源利用率Uj計算如下:

(6)

定義7

當進行VM部署時,服務器當前的CPU資源剩余可用量

(7)

定義8

服務器集群的綜合資源平均利用率(AVG)的計算如下:

(8)

式(8)表示所有服務器綜合資源利用率的平均值,值越大表示VM部署越合理。

1.2 能耗模型

服務器的電源能耗取決于CPU、內存、磁盤和網絡設備的能耗,而其中CPU能耗占服務器能耗的比重最大。研究表明,服務器節點的CPU利用率與電源能耗呈線性關系[11]。

文獻[12]研究表明,服務器空閑時的電源能耗約占滿負載能耗的70%,關閉空閑的服務器可以減少能耗。如服務器的滿負載功率可知,空閑功率未知,服務器的能耗功率可以定義為基于CPU利用率與最大能耗功率的線性函數:

(9)

(10)

服務器集群的單位時間的總能耗Eall由所有服務器的能耗之和求得:

(11)

本文所研究的VM部署問題,目的是優化服務器集群的能量消耗,因此目標函數式為:

min(Eall(s)),s∈S,

(12)

式中:s為滿足約束條件式(4)的部署方案,S為所有部署方案s組成的方案域。

2 基于改進蟻群的VM部署算法

蟻群優化 (Ant Colony Optimization,ACO) 算法是由意大利學者Marco Dorigo于1992年提出的一種基于自然界螞蟻群體智能行為的啟發式算法[13],其模擬了螞蟻在尋找食物過程中放置信息素的行為,并通過這種信息素來控制螞蟻的搜索方向,從而找到最優路徑[14]。蟻群算法廣泛應用于解決各種優化問題,能夠有效地處理大規模和復雜問題,并在全局搜索空間中找到較優解。

在蟻群算法中,螞蟻是算法的基本單元,它們通過在路徑上釋放化學物質——信息素,來引導其他螞蟻前往食物的位置。蟻群算法的關鍵步驟包括螞蟻的移動和信息素更新[15]。螞蟻在移動過程中根據當前位置的啟發式規則和信息素濃度,計算下一步移動的概率。當螞蟻選擇一條路徑并到達目標后,會在路徑上留下信息素,其他螞蟻在搜索過程中通過感知信息素的濃度,更傾向于選擇信息素濃度較高的路徑。這種正反饋機制使得信息素濃度逐漸增強,最終導致螞蟻集中在最短路徑或最優解附近。

2.1 帶有負載感知的概率選擇模型

在云計算服務中,用戶申請的服務不同,所需求的資源也不同,進而導致了用戶需求的VM類型多種多樣。根據VM需求的資源類別,可以將VM分為CPU需求型、儲存需求型、內存需求型、網絡需求型與混合需求型。進行VM部署時,如果將同種類型的VM部署在同一個服務器上,會導致同類需求VM之間的資源競爭,降低服務器工作效率。另一方面,也會使某一類型資源過載,而其他資源未被合理利用,降低資源利用率,導致服務器集群可放置的VM數減少,總功耗增加。如圖1所示,一個服務器上放置多個內存需求型VM,會導致內存資源短缺,而CPU資源剩余,資源利用率低。

圖1 VM部署簡圖Fig.1 VM deployment diagram

基于這一問題,設計了基于負載感知的概率選擇模型,在進行VM部署時,盡量在服務器上部署不同資源需求的VM,避免部署過多類型相同的VM,進而提升資源利用率,降低服務器集群能耗。

蟻群算法中,概率選擇式(13)是算法的核心,螞蟻在路徑選擇上依據概率公式計算每條路徑的選擇概率,通過輪盤賭的方式,最終選擇一條道路。概率選擇式影響螞蟻在節點的方向選擇,從而決定最終的路徑解。

(13)

路徑啟發因子ηij是決定狀態轉移函數的核心元素,路徑的本身屬性影響著螞蟻的路徑選擇方向,從這個角度出發,對路徑啟發因子進行優化設計,可以改進蟻群算法的性能。

傳統啟發因子一般設計為VM功耗的倒數,計算如下:

(14)

式中:Ej為服務器j當前時刻單位時間功耗,計算見式(10)。該啟發因子單純地依賴服務器的功耗進行VM部署,未考慮資源的合理利用,會導致一些資源未被完全利用,而另一些資源負載嚴重,使得服務器的資源利用不均衡,平均資源利用率低。

針對傳統啟發因子的設計問題,本文綜合考慮當前待分配虛擬機i的資源需求與服務器剩余的可用資源量,計算服務器的資源滿足度,設計路徑啟發因子。

(15)

式中:leftj為服務器j中資源剩余可用量,計算方法見式(7);虛擬機i的資源需求與服務器j剩余資源可用量的比值VPLEFTi,j表示服務器資源的滿足度,VPLEFTi,j越大,表示該服務器的滿足度越高。

(16)

式中:AvgVPLEFTi表示虛擬機i部署時,平均的服務器資源滿足度。

改進的啟發因子設計如下:

(17)

虛擬機i的資源需求與服務器j之間的資源滿足度VPLEFTi,j越大于平均資源滿足度AvgVPLEFTi,路徑啟發因子ηij越大,表示服務器j可以更好地滿足虛擬機i的資源需求,虛擬機i部署在服務器j的概率越高。

傳統的啟發因子進行VM部署時只考慮服務器功耗,會導致資源利用不均衡。改進后的啟發因子會綜合考慮服務器的資源負載需求,使資源利用更均衡,提高資源的平均利用率,進而降低服務器集群能耗,實現對VM更合理的部署。

2.2 動態信息素更新規則

ACO算法存在收斂性問題,算法迭代過程中無法收斂到正確的結果或者收斂時間較長。螞蟻之間信息交互及通信通過信息素來完成,優化信息素更新方式可以優化蟻群算法的求解性能。

基于這一問題,本文設計了動態信息素更新規則,信息素的更新隨算法階段動態變化,使其適應算法不同階段的運行方式,可以改進蟻群算法求解的效率。傳統的螞蟻信息素的生成及更新規則如下。

在每只螞蟻進行巡邏,構建好路徑解之后,螞 蟻k在經過的路徑上留下信息素,則路徑(i,j)上的局部信息素τij更新規則如下:

(18)

完成一次算法迭代,要對全局信息素進行更新,供算法下次迭代使用。全局信息素更新規則如下:

(19)

傳統的信息素變化量模型:

(20)

在傳統的信息素變化量模型中,信息素強度是一個定值,算法執行不同階段的信息素強度相同。信息素對后續螞蟻的指引作用減弱,解不容易收斂。

通過對蟻群算法路徑搜索過程進行研究,可以將蟻群尋優過程分為2個階段:算法前期為螞蟻探索階段,初期每條路徑上信息素濃度為預設初值,各個路徑上信息素濃度差別不大,螞蟻相當于更依賴路徑信息的短路徑貪心搜索;算法后期為信息素利用階段,此時螞蟻在經過的路徑上釋放了相應的信息素,路徑信息素又反過來影響螞蟻的路徑選擇。減少前期信息素留存,可以擴大螞蟻的搜索范圍。增大后期信息素留存,可以加快解的收斂速度。

對此,本文提出時變信息素策略,設計時間變化函數f(t)來優化信息素Q釋放規則,使信息素跟隨算法執行時間動態變化。前期時變函數f(t)取值較小,可以減少螞蟻釋放信息素,擴大解的搜索空間。后期時變函數f(t)取值較大,可以增加螞蟻釋放信息素,進而加快解路徑的收斂速度。時變函數設計如下:

(21)

式中:K為算法初始設置的最大迭代次數,t為螞蟻巡邏時間,即算法當前迭代回合。K=20時的函數圖像如圖2所示。

圖2 信息素時變函數Fig.2 Pheromone time-varying function

Q(t)=f(t)×Q,

(22)

式中:Q為信息素強度,Q(t)為引入時變策略的動態信息素。信息素強度跟隨算法迭代時間動態變化。

2.3 算法描述

本文面向VM部署中的能耗問題,對蟻群算法進行改進,提出基于負載感知的概率選擇模型與動態信息素更新規則的VM部署算法(VMACO),算法具體步驟如下:

① 初始化算法各參數,包括VM參數、服務器參數、螞蟻數量、最大迭代次數和信息素強度等;

② 取一只螞蟻攜帶n個VM,置于初始出發點;

③ 根據當前VM資源需求與服務器剩余資源量可用量,通過式(17)計算負載感知路徑啟發因子;

④ 根據概率選擇式(13)計算螞蟻下一步的運動方向,通過輪盤賭的方式,將VM部署在服務器上;

⑤ 更新服務器剩余資源可用量;

⑥ 重復③～⑤,直到完成所有VM的部署;

⑦ 計算當前螞蟻的路徑長度,即根據式(11)計算服務器集群能耗;

⑧ 根據當前迭代回合數,通過式(22)計算當前信息素強度;

⑨ 通過局部信息素更新式(18),更新路徑的信息素值,作為之后螞蟻的指引;

⑩ 重復執行②～⑧,直到所有螞蟻都已構造路徑解;

3 仿真實驗與分析

Cloudsim云計算仿真平臺是2009年由澳大利亞墨爾本大學Rajkumar Buyya教授提出的云計算系統仿真工具集,提供了云計算場景下多種虛擬資源分配和應用調度接口[16]。通過該平臺,用戶不需要運營維護龐大的云計算系統便可以模擬云計算中的各種資源,方便快捷地實現相關仿真實驗[17]。

本文在Java環境的CloudSim仿真平臺上進行仿真實驗。為了模擬真實情況下的計算環境異構問題,服務器類型配置、VM類型配置如表1和表2所示。

表1 服務器節點性能參數Tab.1 Server node performance parameters

表2 VM性能參數Tab.2 VM performance parameters

算法的性能會受到參數影響,為確定參數的取值,本文參考文獻[18]進行設置相關缺省值,再采取控制變量法,控制其他系數不變,僅改變待研究的系數,研究該系數對算法性能的影響,確定各個參數的最優取值,當VM數量在100～1 000時,參數綜合最優設置如表3所示。其中α為啟發因子系數,β為信息素強度系數,ρ為局部蒸發率,Q為信息素強度,Imax為最大迭代次數,Ants為螞蟻數。

表3 算法參數Tab.3 Algorithm parameters

為驗證本文提出的調度算法的性能,在相同環境和條件下將本文提出的調度算法與文獻[5]提出的融合蟻群算法、輪詢 (Round Robin,RR)算法進行比較。實驗中,服務器節點由表1的5種類型組成,每種類型數量為40。每次申請的VM由表2的10種類型組成,每種類型數量相等,VM申請數量由100遞增到600,步長為100。為減少實驗偶然性的影響,實驗都在相同環境下運行10次,并取平均值作為最終結果。

① 算法收斂性對比

在不同VM數量條件下,算法VMACO與ACOSA得到最優解的平均迭代次數如表4所示。因為RR算法屬于調度算法中的直接法,故不討論其收斂性。

表4 算法平均迭代次數Tab.4 Algorithm average iterations

本文提出的VM部署算法VMACO相比ACOSA平均迭代次數減少19.7%,收斂速度更快。

② 資源利用率對比

在不同VM數量條件下,3種算法進行VM初始部署時的服務器平均資源利用率如圖3所示,計算方式見式(8)。

圖3 平均資源利用率對比Fig.3 Comparison of average resource utilization

由圖3可以看出, VMACO平均資源利用率最高。VMACO在VM部署時考慮服務器上各個資源的負載水平,盡量在同一臺服務器上安置資源需求不同的VM,使得整個服務器集群平均資源利用率更高。

③ 服務器啟動數量對比

在不同VM數量條件下,3種算法進行VM初始部署時所需要啟動的最少服務器數量如圖4所示。

圖4 服務器啟動數量對比Fig.4 Comparison of number of servers

由圖4可以看出, VMACO服務器啟動數量最少, RR最多。VMACO對資源的利用率更高,所啟動服務器數更少。

④ 平臺能耗對比

在不同VM數量條件下,3種算法進行VM部署時的服務器平臺的單位時間能耗如圖5所示,計算方式見式(11)。

由圖5可以看出,VMACO能耗最低。盡量在服務器上部署資源需求不同的VM,使得資源利用率更高,從而減少所需服務器數,降低服務器集群能耗。

圖5 平臺總能耗對比Fig.5 Comparison of total platform energy consumption

4 結束語

為降低水下無人平臺公共計算環境能耗,本文以最小能耗為目標,建立了一種能耗關鍵的VM部署模型,設計了基于改進蟻群的VM部署算法來求解該模型,提出了負載感知概率選擇模型,改進了蟻群的路徑選擇;提出了動態信息素模型,優化了信息素更新規則。通過算法對比實驗,驗證了提出的VM部署算法能夠提升平均資源利用率,顯著降低公共計算環境的能耗。本文僅考慮VM部署中的靜態部署問題,現實情況中VM會根據需要動態銷毀與創建,進一步的工作應考慮VM的動態部署問題。