朱 偉，吳傳峰，夏 興

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

0 引言

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

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

本文面向水下無人平臺公共計(jì)算環(huán)境能耗問題,提出了一種能耗關(guān)鍵的VM部署模型,設(shè)計(jì)了基于改進(jìn)蟻群的VM部署算法來求解該模型,算法提出了負(fù)載感知概率選擇模型,改進(jìn)了蟻群的路徑選擇;提出了動態(tài)信息素模型,優(yōu)化了信息素更新規(guī)則,從而實(shí)現(xiàn)了對VM部署方式的優(yōu)化,并通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 問題建模

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

1.1 相關(guān)定義

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

定義1

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

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

(1)

式中:i為VM標(biāo)識號,VMCPU為CPU需求,VMMem為內(nèi)存需求,VMDisk為磁盤需求,VMBw為網(wǎng)絡(luò)需求。

定義2

公共計(jì)算環(huán)境中服務(wù)器節(jié)點(diǎn)集合為P={PM1,PM2,…,PMm},m為服務(wù)器節(jié)點(diǎn)數(shù)量。每個服務(wù)器節(jié)點(diǎn)表示為:

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

(2)

式中:j為服務(wù)器節(jié)點(diǎn)標(biāo)識號,PMCPU為CPU資源,PMMem為內(nèi)存資源,PMDisk為磁盤資源,PMBw為網(wǎng)絡(luò)資源。

定義3

VM與服務(wù)器之間的映射關(guān)系可用部署矩陣θ表示。將n個VM部署到m個服務(wù)器節(jié)點(diǎn)上,用矩陣的形式表示如下:

(3)

式中:θij為VM與服務(wù)器PM的對應(yīng)關(guān)系,若θij值為1,表示虛擬機(jī)i被部署到服務(wù)器j上;若θij值為0,則虛擬機(jī)i未被部署到服務(wù)器j上。

定義4

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

(4)

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

定義5

(5)

定義6

服務(wù)器j的綜合資源利用率Uj計(jì)算如下:

(6)

定義7

當(dāng)進(jìn)行VM部署時(shí),服務(wù)器當(dāng)前的CPU資源剩余可用量

(7)

定義8

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

(8)

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

1.2 能耗模型

服務(wù)器的電源能耗取決于CPU、內(nèi)存、磁盤和網(wǎng)絡(luò)設(shè)備的能耗,而其中CPU能耗占服務(wù)器能耗的比重最大。研究表明,服務(wù)器節(jié)點(diǎn)的CPU利用率與電源能耗呈線性關(guān)系[11]。

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

(9)

(10)

服務(wù)器集群的單位時(shí)間的總能耗Eall由所有服務(wù)器的能耗之和求得:

(11)

本文所研究的VM部署問題,目的是優(yōu)化服務(wù)器集群的能量消耗,因此目標(biāo)函數(shù)式為:

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

(12)

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

2 基于改進(jìn)蟻群的VM部署算法

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

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

2.1 帶有負(fù)載感知的概率選擇模型

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

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

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

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

(13)

路徑啟發(fā)因子ηij是決定狀態(tài)轉(zhuǎn)移函數(shù)的核心元素,路徑的本身屬性影響著螞蟻的路徑選擇方向,從這個角度出發(fā),對路徑啟發(fā)因子進(jìn)行優(yōu)化設(shè)計(jì),可以改進(jìn)蟻群算法的性能。

傳統(tǒng)啟發(fā)因子一般設(shè)計(jì)為VM功耗的倒數(shù),計(jì)算如下:

(14)

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

針對傳統(tǒng)啟發(fā)因子的設(shè)計(jì)問題,本文綜合考慮當(dāng)前待分配虛擬機(jī)i的資源需求與服務(wù)器剩余的可用資源量,計(jì)算服務(wù)器的資源滿足度,設(shè)計(jì)路徑啟發(fā)因子。

(15)

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

(16)

式中:AvgVPLEFTi表示虛擬機(jī)i部署時(shí),平均的服務(wù)器資源滿足度。

改進(jìn)的啟發(fā)因子設(shè)計(jì)如下:

(17)

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

傳統(tǒng)的啟發(fā)因子進(jìn)行VM部署時(shí)只考慮服務(wù)器功耗,會導(dǎo)致資源利用不均衡。改進(jìn)后的啟發(fā)因子會綜合考慮服務(wù)器的資源負(fù)載需求,使資源利用更均衡,提高資源的平均利用率,進(jìn)而降低服務(wù)器集群能耗,實(shí)現(xiàn)對VM更合理的部署。

2.2 動態(tài)信息素更新規(guī)則

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

基于這一問題,本文設(shè)計(jì)了動態(tài)信息素更新規(guī)則,信息素的更新隨算法階段動態(tài)變化,使其適應(yīng)算法不同階段的運(yùn)行方式,可以改進(jìn)蟻群算法求解的效率。傳統(tǒng)的螞蟻信息素的生成及更新規(guī)則如下。

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

(18)

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

(19)

傳統(tǒng)的信息素變化量模型:

(20)

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

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

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

(21)

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

圖2 信息素時(shí)變函數(shù)Fig.2 Pheromone time-varying function

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

(22)

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

2.3 算法描述

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

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

② 取一只螞蟻攜帶n個VM,置于初始出發(fā)點(diǎn);

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

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

⑤ 更新服務(wù)器剩余資源可用量;

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

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

⑧ 根據(jù)當(dāng)前迭代回合數(shù),通過式(22)計(jì)算當(dāng)前信息素強(qiáng)度;

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

⑩ 重復(fù)執(zhí)行②～⑧,直到所有螞蟻都已構(gòu)造路徑解;

3 仿真實(shí)驗(yàn)與分析

Cloudsim云計(jì)算仿真平臺是2009年由澳大利亞墨爾本大學(xué)Rajkumar Buyya教授提出的云計(jì)算系統(tǒng)仿真工具集,提供了云計(jì)算場景下多種虛擬資源分配和應(yīng)用調(diào)度接口[16]。通過該平臺,用戶不需要運(yùn)營維護(hù)龐大的云計(jì)算系統(tǒng)便可以模擬云計(jì)算中的各種資源,方便快捷地實(shí)現(xiàn)相關(guān)仿真實(shí)驗(yàn)[17]。

本文在Java環(huán)境的CloudSim仿真平臺上進(jìn)行仿真實(shí)驗(yàn)。為了模擬真實(shí)情況下的計(jì)算環(huán)境異構(gòu)問題,服務(wù)器類型配置、VM類型配置如表1和表2所示。

表1 服務(wù)器節(jié)點(diǎn)性能參數(shù)Tab.1 Server node performance parameters

表2 VM性能參數(shù)Tab.2 VM performance parameters

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

表3 算法參數(shù)Tab.3 Algorithm parameters

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

① 算法收斂性對比

在不同VM數(shù)量條件下,算法VMACO與ACOSA得到最優(yōu)解的平均迭代次數(shù)如表4所示。因?yàn)镽R算法屬于調(diào)度算法中的直接法,故不討論其收斂性。

表4 算法平均迭代次數(shù)Tab.4 Algorithm average iterations

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

② 資源利用率對比

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

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

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

③ 服務(wù)器啟動數(shù)量對比

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

圖4 服務(wù)器啟動數(shù)量對比Fig.4 Comparison of number of servers

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

④ 平臺能耗對比

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

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

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

4 結(jié)束語

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