基于進(jìn)化博弈模型的多層次云應(yīng)用部署

王亞利 文欣秀

1(濟(jì)源職業(yè)技術(shù)學(xué)院成教中心 河南 濟(jì)源 459000) 2(華東理工大學(xué)信息科學(xué)與工程學(xué)院 上海 200237)

0 引 言

云計(jì)算環(huán)境中，云應(yīng)用部署不僅需要滿(mǎn)足物理服務(wù)器的資源利用率和功耗優(yōu)化等需求，同時(shí)還需要考慮用戶(hù)應(yīng)用在響應(yīng)時(shí)間上的性能考慮，這些綜合性的優(yōu)化因素是當(dāng)前云環(huán)境中應(yīng)用部署的關(guān)鍵問(wèn)題。為了確保以上的需求，需要從多方面考慮不同的條件，最為重點(diǎn)的是云環(huán)境中動(dòng)態(tài)變化的負(fù)載狀況和時(shí)間漸變的資源可用性等因素，以至于需要調(diào)整云應(yīng)用的部署目標(biāo)和資源分配方案，進(jìn)而動(dòng)態(tài)地對(duì)應(yīng)用進(jìn)行重部署[1]。

本文將重點(diǎn)考慮多層次云應(yīng)用部署中的兩個(gè)主要屬性：(1) 可適應(yīng)性。即需要根據(jù)云環(huán)境中的運(yùn)行條件調(diào)整云應(yīng)用的部署位置和相應(yīng)資源分配，以此維持應(yīng)用執(zhí)行在響應(yīng)時(shí)間上的期望性能等級(jí)，并維持其資源利用率(包括CPU利用率以及物理服務(wù)的功耗利用率)。(2) 可擴(kuò)展性。即需要在做出云應(yīng)用部署決策的同時(shí)，降低非決定性因素對(duì)于優(yōu)化目標(biāo)的影響，并維系相互沖突目標(biāo)間的影響最小化，保證更小的決策波動(dòng)。

為了實(shí)現(xiàn)多層次云應(yīng)用的自適應(yīng)和可擴(kuò)展性的部署，本文設(shè)計(jì)一種基于進(jìn)化博弈模型的多層次云應(yīng)用部署算法EGMAP。該算法中，每個(gè)云應(yīng)用均維持一個(gè)應(yīng)用部署策略集合，可視為一個(gè)進(jìn)化種群，集合中的每個(gè)策略用于表示應(yīng)用的部署位置和資源分配解。在理論分析的基礎(chǔ)上，算法確保通過(guò)部署策略間的一系列進(jìn)化博弈過(guò)程，種群狀態(tài)(策略分布)可以收斂至一種與初始狀態(tài)無(wú)關(guān)的進(jìn)化穩(wěn)定均衡策略上。進(jìn)化穩(wěn)定種群狀態(tài)中的支配策略稱(chēng)為進(jìn)化穩(wěn)定策略。在該狀態(tài)下，除了進(jìn)化穩(wěn)定策略之外，沒(méi)有任一其他策略可以支配整個(gè)種群。在給定該理論性質(zhì)前提下，算法可以以穩(wěn)定的方式利用進(jìn)化穩(wěn)定策略將云應(yīng)用部署策略運(yùn)行于穩(wěn)定狀態(tài)[2]。

仿真結(jié)果證明了相應(yīng)的理論分析和算法設(shè)計(jì)初衷，云應(yīng)用可以進(jìn)化到進(jìn)化穩(wěn)定部署策略上，并在給定的負(fù)載狀況和資源可用性條件下，得到相應(yīng)的應(yīng)用部署位置和資源分配解。與啟發(fā)式部署方法的比較結(jié)果顯示，應(yīng)用響應(yīng)時(shí)間性能、資源利用率和能量利用等性能指標(biāo)，本文算法得到了更好的均衡效果。

1 相關(guān)工作

目前，云應(yīng)用部署的相關(guān)工作中，多數(shù)部署方法均只考慮了單層次應(yīng)用的部署問(wèn)題，且一般以單目標(biāo)作為優(yōu)化目標(biāo)，如文獻(xiàn)[3-6]均只進(jìn)化了物理服務(wù)器的能量?jī)?yōu)化，忽略了應(yīng)用性能的滿(mǎn)足度。而本文算法考慮的是一種多層次云應(yīng)用體系，考慮的是多目標(biāo)的同步優(yōu)化，且可以通過(guò)進(jìn)化博弈模型在多個(gè)相互沖突的目標(biāo)間找到均衡。此外，博弈模型是云計(jì)算環(huán)境中常用的優(yōu)化機(jī)制，已經(jīng)應(yīng)用在應(yīng)用部署[7-9]、任務(wù)調(diào)度[10]、基于副本感知的調(diào)度問(wèn)題[11]中。文獻(xiàn)[7-9]以貪婪的思想尋找云應(yīng)用部署問(wèn)題的均衡解。然而，貪婪方法的穩(wěn)定性較差，即使可以得到部署均衡解，也無(wú)法保證用戶(hù)方一定穩(wěn)定在部署均衡解上。本文算法將通過(guò)進(jìn)化博弈中的復(fù)制動(dòng)態(tài)機(jī)制確保得到的均衡解是具有漸近穩(wěn)定性的，這可以保證多應(yīng)用執(zhí)行過(guò)程中部署策略不會(huì)出現(xiàn)過(guò)大波動(dòng)。遺傳算法[12-13]和其他隨機(jī)式優(yōu)化算法[14-15]也可用于求解云計(jì)算中的應(yīng)用部署問(wèn)題。這些算法雖然可以尋找最優(yōu)部署解，但是部署策略的穩(wěn)定性無(wú)法保證。相比而言，本文算法將尋找進(jìn)化穩(wěn)定解，并論證其解可以收斂在均衡解上。文獻(xiàn)[16]也做了云應(yīng)用部署的類(lèi)似研究，也考慮了響應(yīng)時(shí)間性能目標(biāo)，但本文在此基礎(chǔ)上另外加入了帶寬分配和功耗兩個(gè)目標(biāo)優(yōu)化，同時(shí)在每個(gè)部署策略中考慮了帶寬分配參數(shù)，這些與實(shí)際的云計(jì)算環(huán)境中需要考慮的問(wèn)題也更加貼近。同時(shí)，本文在仿真環(huán)境中進(jìn)行大量實(shí)際應(yīng)用負(fù)載的仿真實(shí)驗(yàn)，可以更加準(zhǔn)確地評(píng)估與測(cè)試算法的性能。

2 多層次云應(yīng)用部署模型

云計(jì)算環(huán)境中，應(yīng)用部署模型可作如下描述：假設(shè)數(shù)據(jù)中心有M臺(tái)物理主機(jī)，用于部署N個(gè)云應(yīng)用。每一個(gè)云應(yīng)用的執(zhí)行經(jīng)過(guò)三個(gè)服務(wù)器層次，如圖1所示。每臺(tái)服務(wù)器可運(yùn)行在一個(gè)虛擬機(jī)上，一臺(tái)物理主機(jī)可運(yùn)行多臺(tái)虛擬機(jī)，虛擬機(jī)可以共享本地主機(jī)的可用資源。具體地，云用戶(hù)提交應(yīng)用請(qǐng)求后，需要依次通過(guò)最外層的Web服務(wù)器、中間層的App應(yīng)用服務(wù)器、最底層的Database數(shù)據(jù)庫(kù)服務(wù)器才能完成，應(yīng)用通過(guò)虛擬機(jī)形式執(zhí)行后，通過(guò)后臺(tái)服務(wù)器返回至外層的Web前臺(tái)顯示應(yīng)用執(zhí)行結(jié)果。Web服務(wù)器接收應(yīng)用任務(wù)的HTTP消息，驗(yàn)證消息中的數(shù)據(jù)并向提交應(yīng)用的用戶(hù)提供Web用戶(hù)接口。App應(yīng)用服務(wù)器執(zhí)行相應(yīng)功能的應(yīng)用邏輯并處理用戶(hù)提交的數(shù)據(jù)。DB數(shù)據(jù)庫(kù)服務(wù)器則進(jìn)行數(shù)據(jù)訪問(wèn)與存儲(chǔ)。每條消息順序地從Web服務(wù)器通過(guò)應(yīng)用服務(wù)器到數(shù)據(jù)庫(kù)服務(wù)器進(jìn)行處理，響應(yīng)消息則反向從數(shù)據(jù)庫(kù)服務(wù)器返回。本文假設(shè)不同的云應(yīng)用利用不同的服務(wù)器集合，且服務(wù)器在不同應(yīng)用間不進(jìn)行共享。每臺(tái)服務(wù)器假設(shè)運(yùn)行于一臺(tái)主機(jī)的虛擬機(jī)上，且一臺(tái)主機(jī)可以運(yùn)行多臺(tái)虛擬機(jī)，它們可以共享本地主機(jī)上的可用資源。

圖1 應(yīng)用執(zhí)行的三層模型

多層次云應(yīng)用部署問(wèn)題的目標(biāo)是：尋找一種進(jìn)化穩(wěn)定策略，在該策略下，N個(gè)云應(yīng)用(以N×3臺(tái)虛擬機(jī)形式表示)部署在M臺(tái)物理主機(jī)上，使得對(duì)于給定的負(fù)載條件和可用資源狀況下，所有云應(yīng)用能夠適應(yīng)于其部署所在位置和相應(yīng)資源分配，并實(shí)現(xiàn)目標(biāo)函數(shù)的最小化。以下給出多層次云應(yīng)用部署的相關(guān)優(yōu)化目標(biāo)：

1) CPU資源分配：表示主機(jī)分配給每臺(tái)虛擬機(jī)的CPU處理內(nèi)核時(shí)間的份額，以百分比形式表示。若分配份額為100%，則表明一個(gè)CPU的處理能力完全分配至一臺(tái)虛擬機(jī)VM，該值表示虛擬機(jī)CPU利用率的上限。由于云應(yīng)用部署的三層結(jié)構(gòu)，可將該目標(biāo)表示為：

(1)

式中：ct表示分配至第t層服務(wù)器上的CPU時(shí)間比例。

2) 網(wǎng)絡(luò)帶寬資源分配：表示主機(jī)分配給每臺(tái)虛擬機(jī)的網(wǎng)絡(luò)帶寬量，單位為bits/s。該值為虛擬機(jī)帶寬消耗的上限。由于云應(yīng)用部署的三層結(jié)構(gòu)，可將該目標(biāo)表示為：

(2)

式中：bt表示分配至第t層服務(wù)器的網(wǎng)絡(luò)帶寬資源。

3) 應(yīng)用的響應(yīng)時(shí)間：表示一個(gè)消息從Web服務(wù)器傳輸至數(shù)據(jù)庫(kù)服務(wù)器間所需要的時(shí)間，可表示為：

frt=Tp+Tw+Tc

(3)

式中：Tp表示應(yīng)用在三臺(tái)服務(wù)器上處理用戶(hù)發(fā)出消息的總時(shí)間；Tw表示消息在服務(wù)器上等待處理的時(shí)間；Tc表示消息在服務(wù)器之間傳輸?shù)目倳r(shí)間。Tp、Tw和Tc三個(gè)值通過(guò)M/M/1隊(duì)列模型估算，應(yīng)用的消息到達(dá)服從泊松分布，服務(wù)器的消息處理時(shí)間按指數(shù)分布。

Tp計(jì)算方法如下：令Tp,t表示第t層服務(wù)器處理消息需要的時(shí)間，表示為：

(4)

Tw計(jì)算方法如下：

(5)

式中：O表示主機(jī)上用于分配應(yīng)用的處理內(nèi)核數(shù)量；λ表示應(yīng)用的消息到達(dá)率，即在單位時(shí)間內(nèi)應(yīng)用接收來(lái)自于用戶(hù)的消息數(shù)量；ρt表示第t層服務(wù)器的CPU利用率；fmax表示主機(jī)的最大CPU頻率；ft表示第t層服務(wù)器寄宿的主機(jī)的CPU頻率。同時(shí)：

(6)

Tc計(jì)算方法如下：

(7)

4) 主機(jī)功耗：表示應(yīng)用執(zhí)行過(guò)程中主機(jī)消耗的平均功耗，單位為W，計(jì)算為：

(8)

式中：H表示數(shù)據(jù)中心內(nèi)的主機(jī)總量；Pfho,idle和Pfho,max分別表示當(dāng)頻率為fho時(shí)，主機(jī)h的CPU處理內(nèi)核o利用率分別為0%和100%時(shí)的功耗。

多層次云應(yīng)用部署過(guò)程中，需要滿(mǎn)足以下四種約束：

1) CPU內(nèi)核能力約束：對(duì)于所有M臺(tái)物理主機(jī)，滿(mǎn)足oi≤LU，其中：LU表示一臺(tái)主機(jī)的最大內(nèi)核處理能力；oi表示分配給第i臺(tái)主機(jī)的處理內(nèi)核份額。該約束的違例條件可計(jì)算為：

(9)

若oi>LU，則Ii=1；否則，Ii=0。

2) 網(wǎng)絡(luò)帶寬能力約束：對(duì)于所有的M臺(tái)主機(jī)，滿(mǎn)足bi≤LB，其中：bi表示分配給第i臺(tái)主機(jī)的總帶寬量(百分比形式表示)；LB表示一臺(tái)主機(jī)的最大帶寬能力。該約束的違例條件可計(jì)算為：

(10)

若bi>LB，則Ii=1；否則，Ii=0。

3) 響應(yīng)時(shí)間約束：對(duì)于所有M個(gè)云應(yīng)用，滿(mǎn)足ri≤LR，其中：LR表示應(yīng)用的響應(yīng)時(shí)間上限值；ri表示應(yīng)用i的響應(yīng)時(shí)間。響應(yīng)時(shí)間的上限約束的違例條件可計(jì)算為：

(11)

若ri>LR，則Ii=1；否則，Ii=0。

4) 能耗約束：對(duì)于所有M個(gè)云應(yīng)用，滿(mǎn)足ei≤LE，其中：LE表示主機(jī)能耗的上限值；ei表示主機(jī)i的能耗。能耗上限約束的違例條件可計(jì)算為：

(12)

若ei>LE，則Ii=1；否則，Ii=0。

3 進(jìn)化博弈模型

傳統(tǒng)的博弈模型中，一個(gè)博弈參與者的目標(biāo)是選擇一個(gè)使其收益最大化的策略。進(jìn)化博弈不同，它是一個(gè)種群內(nèi)的所有博弈參與者間需要進(jìn)行隨機(jī)式重復(fù)的博弈。

3.1 進(jìn)化穩(wěn)定策略ESS

假設(shè)初始種群中所有博弈者的博弈策略為k，種群中占比x(x∈(0,1))的博弈者發(fā)生策略變異，該部分博弈者的策略變?yōu)閘。當(dāng)一個(gè)博弈者參與到博弈過(guò)程中時(shí)，其對(duì)手執(zhí)行策略k和l的比例分別為1-x和x。因此，執(zhí)行策略k和l的博弈者的期望收益分別為U(k,xl+(1-x)k)和U(l,xl+(1-x)k)。

定義1如果對(duì)于任意策略l≠k，存在一個(gè)確定的x′∈(0,1)，使得對(duì)于所有的x∈(0,x′)，式(13)均是成立的，則稱(chēng)策略k為進(jìn)化穩(wěn)定策略。

U(k,xl+(1-x)k)>U(l,xl+(1-x)k)

(13)

如果支付函數(shù)為線性形式，則由式(13)可知：

(1-x)U(k,k)+xU(k,l)>(1-x)U(l,k)+xU(l,l)

(14)

如果x接近于0，則式(14)可推導(dǎo)出：

U(k,k)>U(k,l)或U(k,k)=U(l,k)和U(k,l)>U(l,l)

(15)

式(15)表明：若博弈者采用策略k，即可得到比其他策略更高的收益。因此，任意博弈者不會(huì)通過(guò)從策略k改變至其他策略上而獲得更高的收益，這表明進(jìn)化穩(wěn)定策略是處于納什均衡的一個(gè)解。而進(jìn)化穩(wěn)定策略也將是擁有更低種群份額的任意變異策略無(wú)法入侵的策略。

3.2 復(fù)制動(dòng)態(tài)

復(fù)制動(dòng)態(tài)用于描述不同策略的種群隨時(shí)間推進(jìn)策略發(fā)生的變化。令λk(t)≥0代表采用策略k∈K的博弈者數(shù)量，K表示可行策略集合。博弈者的總種群數(shù)量可表示為：

(16)

令xk(t)=λk(t)/λ(t)表示在時(shí)間t時(shí)采用策略k的博弈者的種群份額。種群狀態(tài)定義為：X(t)=[x1(t),x2(t),…,xk(t),…,xK(t)]。給定X，采用策略k的期望收益定義為U(k,X)。種群的平均收益表示為：

(17)

(18)

式(18)表明當(dāng)博弈者的收益比種群平均收益更高(或更低)時(shí)博弈者將增加(或減少)其種群份額。

定理1若策略k為嚴(yán)格占優(yōu)策略，則xk(t)t→∞→ 0。

若策略得到的收益嚴(yán)格高于任意博弈對(duì)手的收益，則認(rèn)為該策略是嚴(yán)格支配策略。隨著支配策略的種群份額的增加，最后將占優(yōu)整個(gè)種群。相反，若策略收益嚴(yán)格低于采用嚴(yán)格支配策略的博弈者，則該策略被稱(chēng)為嚴(yán)格被支配策略。因此，嚴(yán)格被支配策略在種群中會(huì)隨著時(shí)間逐漸消失。

納什均衡與復(fù)制動(dòng)態(tài)的穩(wěn)定狀態(tài)間具有密切聯(lián)系，其穩(wěn)定狀態(tài)下的種群份額將不會(huì)隨著時(shí)間而發(fā)生改變。由于處于納什均衡時(shí)沒(méi)有博弈者會(huì)改變其策略，復(fù)制動(dòng)態(tài)中的每一個(gè)納什均衡都將是一種穩(wěn)定狀態(tài)。如前所述，一個(gè)進(jìn)化穩(wěn)定策略是一個(gè)納什均衡處的一個(gè)解。因此，進(jìn)化穩(wěn)定策略即為復(fù)制動(dòng)態(tài)中處于穩(wěn)定狀態(tài)的一個(gè)解。換言之，進(jìn)化穩(wěn)定策略是種群中處于穩(wěn)定狀態(tài)的嚴(yán)格占優(yōu)策略。

本文的目標(biāo)就是對(duì)每個(gè)應(yīng)用維持一個(gè)部署策略的種群，每個(gè)種群中，策略被隨機(jī)選取，博弈者間進(jìn)行重復(fù)博弈直到種群狀態(tài)達(dá)到一種穩(wěn)定狀態(tài)。即：部署算法可以找到種群的嚴(yán)格占優(yōu)策略，并根據(jù)該策略(進(jìn)化穩(wěn)定策略ESS)完成虛擬機(jī)部署。

4 基于進(jìn)化博弈的多層次云應(yīng)用部署算法

將N個(gè)云應(yīng)用定義為N個(gè)種群，表示為{P1,P2,…,PN}，每個(gè)種群在策略間進(jìn)行博弈。將策略s定義為應(yīng)用中三臺(tái)虛擬機(jī)的部署位置和資源分配解，表示為：

(19)

式中：ai表示第i個(gè)應(yīng)用；hi,t表示執(zhí)行應(yīng)用ai的第t層虛擬機(jī)的主機(jī)ID；ci,t表示主機(jī)hi,t內(nèi)的內(nèi)核ID；ui,t表示對(duì)于執(zhí)行應(yīng)用ai的第t層虛擬機(jī)的CPU分配；bi,t表示對(duì)于執(zhí)行應(yīng)用ai的第t層虛擬機(jī)的帶寬分配；pi,t表示分配至第t層虛擬機(jī)的主機(jī)hi,t的內(nèi)核ci,t的功耗閾值，該閾值轉(zhuǎn)換為CPU的p狀態(tài)，每個(gè)內(nèi)核需要運(yùn)行在其虛擬機(jī)請(qǐng)求的最高p狀態(tài)。

圖2所示為兩個(gè)應(yīng)用a1和a2的兩種示范博弈策略，此時(shí)，N=2，M=2。應(yīng)用a1的策略s(a1)將第一層虛擬機(jī)VM部署于主機(jī)1的內(nèi)核3，即h1,1=1，c1,1=3，對(duì)應(yīng)功耗為90 W，p1,1=90，并且虛擬機(jī)消耗30%的CPU份額和80 kbit/s網(wǎng)絡(luò)帶寬，即c1,1=30、b1,1=80。第二層虛擬機(jī)部署在主機(jī)1的內(nèi)核3上，即h1,2=1、c1,2=3，對(duì)應(yīng)功耗為100 W，即p1,2=100，并且消耗了30%的CPU份額和85 kbit/s網(wǎng)絡(luò)帶寬，即c1,2=30、b1,2=85。第三層虛擬機(jī)部署在主機(jī)2的內(nèi)核3上，即h1,3=2、c1,3=3，對(duì)應(yīng)功耗為83 W，即p1,2=83，虛擬機(jī)消耗45%的CPU份額和120 kbit/s帶寬，即c1,3=45、b1,3=120。給定策略s(a1)，應(yīng)用a1在CPU分配和帶寬分配上的目標(biāo)值為105%和285 kbit/s。

圖2 部署策略示例

算法1是本文算法通過(guò)進(jìn)化博弈使每個(gè)應(yīng)用尋找進(jìn)化穩(wěn)定策略的過(guò)程。在初始第0代種群時(shí)，針對(duì)N個(gè)應(yīng)用隨機(jī)方式生成N個(gè)種群，即N個(gè)策略，即步驟1-步驟2。在第g代種群中，每個(gè)種群實(shí)施系列博弈，即步驟4-步驟24。單次博弈隨機(jī)選擇策略對(duì)s1和s2，根據(jù)前文中描述的目標(biāo)函數(shù)，得到兩個(gè)策略間的勝者策略和敗者策略，即步驟7-步驟9。敗者策略從種群中移除，勝者策略被復(fù)制以增加其種群份額，并以概率Pm進(jìn)行變異，即步驟10-步驟15。變異操作隨機(jī)從勝者種群中選擇三臺(tái)虛擬機(jī)中的一臺(tái)，并隨機(jī)變換其h值，即步驟12。

算法1基于進(jìn)化博弈模型的多層次云應(yīng)用部署過(guò)程

1.初始化種群世代數(shù)g=0

2.隨機(jī)生成對(duì)應(yīng)N個(gè)云應(yīng)用的N個(gè)進(jìn)化種群，并將其表示為集合P={P1,P2,…,PN}

3.若當(dāng)前世代數(shù)g小于最大世代數(shù)Gmax

4.foreach populationPirandomly selected fromPdo

//初始化一個(gè)空種群集合

6.forj=1 to |Pi|/2do

7.s1←randomlySelect(Pi)

//隨機(jī)種群個(gè)體

8.s2←randomlySelect(Pi)

//隨機(jī)種群個(gè)體

9. winner←performGame(s1,s2)

//兩部署策略間博弈

10. replica←replicate(winner)

//復(fù)制博弈勝者策略

11.ifrandom()≤Pmthen

//變異概率比較

12.replica←mutate(winner)

//對(duì)博弈勝者作變異操作

13.endif

14.Pi{s1,s2}

//從種群中剔除兩個(gè)個(gè)體

//將勝者填充至種群

16.endfor

18.di←argmaxs∈Pixs

19.whilediis infeasibledo

20.Pi{di}

21.di←argmaxs∈Pixs

22.endwhile

23.根據(jù)di部署相應(yīng)應(yīng)用的虛擬機(jī)

24.endfor

25.g=g+1

//種群世代數(shù)增加1

26.endwhile

一旦種群中的所有策略參與博弈，算法即識(shí)別可行策略，其種群份額xs為最高，并將其作為一個(gè)占優(yōu)策略di，即步驟18-步驟22。若策略不違背CPU內(nèi)核和網(wǎng)絡(luò)帶寬資源能力的約束，即式(9)中CU=0和式(10)中CB=0，則該策略視為一個(gè)可行策略。算法根據(jù)占優(yōu)策略部署云應(yīng)用的三臺(tái)虛擬機(jī)。

博弈過(guò)程根據(jù)兩個(gè)策略的優(yōu)劣關(guān)系及其可行性得以延續(xù)，即算法1中的函數(shù)performGame()。如果一個(gè)可行策略和一個(gè)不可行策略參與在博弈過(guò)程中，則可行策略肯定贏得博弈過(guò)程。如果兩個(gè)策略均是可行策略，則需要根據(jù)以下三種策略選擇最終的博弈獲勝者。

1) Pareto支配PD。該策略根據(jù)支配關(guān)系定義。一個(gè)策略s1占優(yōu)另一策略s2，表示為s1﹥s2，當(dāng)且僅當(dāng)以下兩個(gè)條件滿(mǎn)足：s1的目標(biāo)值優(yōu)于或等于s2的所有目標(biāo)值；s1的目標(biāo)值優(yōu)于s2的至少一個(gè)目標(biāo)值。支配策略將贏得博弈過(guò)程。如果兩個(gè)策略間相互不存在支配關(guān)系，則隨機(jī)選擇一個(gè)策略為博弈勝者。

2) 超體積HV(Hypervolume)。該策略根據(jù)超體積指標(biāo)定義，它度量給定策略s在目標(biāo)空間中支配的體積，定義為：

HV(s)=Λ(∪{x′|s>x′>xr})

(20)

式中：Λ表示勒貝格測(cè)度；xr表示目標(biāo)空間中的參考點(diǎn)。越大的超體積表明策略越優(yōu)。給定兩個(gè)策略，擁有更高超體積的策略將是博弈最終的獲勝方。如果兩個(gè)策略擁有相同的超體積，則隨機(jī)選擇一個(gè)策略作為博弈最終的獲勝方。

3) Pareto支配與超體積混合策略PD-HV。該策略是以上兩種策略的混合形式。首先，對(duì)于兩個(gè)給定的策略執(zhí)行Pareto支配比較，若兩個(gè)策略不存在任意支配關(guān)系，則利用超體積HV選擇最終的博弈勝者。如果此時(shí)兩個(gè)策略仍然具有相同的超體積HV，則隨機(jī)選擇最終的博弈獲勝方。

如果博弈中的兩個(gè)策略均為不可行策略，則依據(jù)前文定義的約束違例進(jìn)行比較。如果以下條件滿(mǎn)足，策略s1與策略s2博弈過(guò)程中將視為博弈獲勝者：策略s1的約束違例低于或等于策略s2的所有約束違例；策略s1的約束違例低于策略s2的至少一個(gè)約束違例。

5 策略穩(wěn)定性分析

進(jìn)化博弈過(guò)程中博弈者策略的穩(wěn)定性至關(guān)重要，即需要通過(guò)證明每個(gè)種群的狀態(tài)是否收斂至一個(gè)進(jìn)化穩(wěn)定均衡上分析算法是否能夠達(dá)到至少一個(gè)納什均衡。穩(wěn)定性分析包括三個(gè)步驟：1) 設(shè)計(jì)描述種群狀態(tài)動(dòng)態(tài)的差分等式；2) 證明策略選擇過(guò)程存在均衡；3) 證明均衡是漸近穩(wěn)定或進(jìn)化穩(wěn)定的。先對(duì)穩(wěn)定性分析中使用的符號(hào)含義作出如下說(shuō)明。

S代表可行策略集合，S*代表種群中出現(xiàn)的一個(gè)策略集合。

X(t)={x1(t),x2(t),…,x|S*|(t)}代表時(shí)間t時(shí)的種群狀態(tài)，其中，xs(t)表示采用策略s∈S的種群份額，且：

(21)

Fs代表策略s的適應(yīng)度值，該值是根據(jù)不同博弈者之間的占優(yōu)關(guān)系決定的相對(duì)值，博弈勝者比敗者擁有更高的適應(yīng)度值。

pk,s=xk×Φ(Fs-Fk)代表當(dāng)策略s與策略k博弈獲勝時(shí)被復(fù)制的概率，Φ(Fs-Fk)代表策略s的適應(yīng)度高于策略k的適應(yīng)度的概率。

則策略s的種群份額的動(dòng)態(tài)過(guò)程可描述為：

(22)

注意：若策略s為嚴(yán)格占優(yōu)策略，則xs(t)t→∞→ 0。

定理2種群狀態(tài)收斂于均衡上。

證明不同的策略擁有不同的適應(yīng)度值，換言之，所有策略中僅有一個(gè)策略擁有最高適應(yīng)度值。給定定理1，假設(shè)F1>F2>…>F|S*|，則種群狀態(tài)將收斂于均衡，即：X(t)t→∞={x1(t),x2(t),…,x|S*|(t)}t→∞={1,0,…,0}。證畢。

定理3定理2中得到的均衡是漸近穩(wěn)定的。

證明在均衡X={1,0,…,0}處，差分等式集合可通過(guò)替換x1=1-x2-…-x|S*|進(jìn)行縮?。?/p>

(23)

式中：csk≡Φ(Fs-Fk)-Φ(Fk-Fs)，且Z(t)={z2(t),z3(t),…,z|S*|(t))，表示縮小后的對(duì)應(yīng)種群狀態(tài)。根據(jù)定理1，在(|S*|-1)維度下，Zt→∞(t)=Zeq={0,0,…,0}。

如果所有Z(t)的雅可比矩陣的特征值擁有負(fù)的實(shí)數(shù)值部分，則Zeq是漸近穩(wěn)定的。雅可比矩陣J的元素為：

s,k=2,3,…,|S*|

(24)

因此，J可以作如下定義：

(25)

式中：c21,c31,…,c|S*|1表示J的特征值。對(duì)于所有s，cs1=-Φ(F1-Fs)，因此，Zeq={0,0,…,0}是漸近穩(wěn)定的。證畢。

6 仿真實(shí)驗(yàn)測(cè)評(píng)

通過(guò)仿真實(shí)驗(yàn)難證算法性能。利用CloudSim平臺(tái)構(gòu)建云環(huán)境，建立的云數(shù)據(jù)中心仿真環(huán)境由M=100臺(tái)物理主機(jī)構(gòu)成，主機(jī)分布于10×10的網(wǎng)格拓?fù)浣Y(jié)構(gòu)中。實(shí)驗(yàn)中引入五種云應(yīng)用類(lèi)型進(jìn)行測(cè)試，表1給出了五種云應(yīng)用類(lèi)型的消息到達(dá)率(即每秒到達(dá)的消息數(shù))和消息在不同服務(wù)器上的處理時(shí)間，參數(shù)配置遵循齊普夫定律。仿真實(shí)驗(yàn)中針對(duì)每種應(yīng)用類(lèi)型執(zhí)行40個(gè)應(yīng)用實(shí)例，即一共執(zhí)行200個(gè)應(yīng)用實(shí)例，N=200。

表1 消息到達(dá)率和消耗處理時(shí)間

假設(shè)每臺(tái)主機(jī)配置Intel Core2 Quad Q6700型CPU，該CPU擁有五種運(yùn)行頻率/電壓組合(p狀態(tài))。表2給出了CPU率在0%和100%時(shí)每個(gè)p狀態(tài)下的主機(jī)功耗，該參數(shù)配置可用于計(jì)算功耗目標(biāo)值。

表2 主機(jī)的p狀態(tài)

設(shè)置每個(gè)種群中的策略數(shù)為100，算法1中的變異概率Pm設(shè)置為0.01，算法的最大種群代數(shù)Gmax設(shè)置為500，每個(gè)仿真結(jié)果選取獨(dú)立的20次仿真結(jié)果的平均值。表3給出仿真詳細(xì)參數(shù)配置。

表3 仿真實(shí)驗(yàn)參數(shù)配置

將本文設(shè)計(jì)的進(jìn)化博弈的多層次云應(yīng)用部署算法命名為EGMAP算法，在三種不同博弈勝者選擇策略下，可得到以下算法：EGMAP-PD、EGMAP-HV和EGMAP-PD-HV。

圖3、圖4和圖5分別給出了EGMAP-PD算法、EGMAP-HV算法和EGMAP-PD-HV算法得到的CPU資源分配、網(wǎng)絡(luò)帶寬資源分配、能耗和響應(yīng)時(shí)間情況，統(tǒng)計(jì)了四個(gè)目標(biāo)值的最大值、最小值和平均值隨著種群代數(shù)增加的變化情況。比較圖3(a)、圖4(a)和圖5(a)的結(jié)果，EGMAP-HV在種群世代末期的CPU資源分配平均穩(wěn)定在8.05%左右，是所有算法中最優(yōu)的。比較圖3(b)、圖4(b)和圖5(b)的結(jié)果，EGMAP-HV在種群世代末期的網(wǎng)絡(luò)帶寬資源分配平均穩(wěn)定在200.9 bit/s，是所有算法中最優(yōu)的。比較圖3(c)、圖4(c)和圖5(c)的結(jié)果，在種群進(jìn)化下，EGMAP可以節(jié)省主機(jī)能耗，EGMAP-HV在種群世代末期的功耗平均穩(wěn)定在334 W，是所有算法中最優(yōu)的。從圖3(d)、圖4(d)和圖5(d)的結(jié)果可以看到，算法的響應(yīng)時(shí)間隨著種群世代進(jìn)化呈現(xiàn)比較穩(wěn)定的狀態(tài)，這是因?yàn)轫憫?yīng)時(shí)間與其他目標(biāo)之間是沖突的，而EGMAP算法可以在所有目標(biāo)之間實(shí)現(xiàn)均衡優(yōu)化。EGMAP-HV在種群世代末期的平均響應(yīng)時(shí)間為26.12 ms，是算法中最優(yōu)的。

(a) CPU資源分配 (b) 帶寬資源分配

(c) 能耗 (d) 應(yīng)用的響應(yīng)時(shí)間圖3 EGMAP-PD算法的性能表現(xiàn)

(a) CPU資源分配 (b) 帶寬資源分配

(c) 能耗 (d) 應(yīng)用的響應(yīng)時(shí)間圖4 EGMAP-HV算法的性能表現(xiàn)

(a) CPU資源分配(b) 帶寬資源分配

(c) 能耗 (d) 應(yīng)用的響應(yīng)時(shí)間圖5 EGMAP-PD-HV算法的性能表現(xiàn)

引入首次適應(yīng)算法FFA和最佳適應(yīng)算法BFA進(jìn)行對(duì)比實(shí)驗(yàn)，兩種算法是應(yīng)用于云應(yīng)用部署的經(jīng)典方法。表4給出了最后一個(gè)種群代數(shù)中優(yōu)化目標(biāo)值的最小值、平均值和最大值?？梢钥吹?，在所有優(yōu)化目標(biāo)值上，EGMAP-HV算法結(jié)果優(yōu)于EGMAP-PD和EGMAP-PD-HV。FFA算法得到了最小能耗，由于該算法可以將虛擬機(jī)部署到最小數(shù)量的物理主機(jī)上，充分利用主機(jī)資源，節(jié)省了能耗，但是該算法犧牲了其他目標(biāo)的優(yōu)化。BFA算法在CPU資源分配上表現(xiàn)最好，原因在于該算法將虛擬機(jī)部署到主機(jī)時(shí)維持了更好的資源可用性，部署時(shí)選擇了最為合適的物理主機(jī)。EGMAP-HV算法可以找到支配策略，該策略在主機(jī)間分布CPU資源時(shí)要優(yōu)于BFA?？偟膩?lái)看，EGMAP比FFA和BFA得到了更為均衡的結(jié)果，并且在應(yīng)用的響應(yīng)時(shí)間、CPU資源分配、網(wǎng)絡(luò)帶寬資源分配上均得到了最好的結(jié)果。

表4 性能對(duì)比

續(xù)表4

表5給出了三種EGMAP算法執(zhí)行給定進(jìn)化世代數(shù)時(shí)需要的時(shí)間。仿真時(shí)的系統(tǒng)環(huán)境是3.6 GHz AMD A6-5400K APU和6 GB內(nèi)存，操作系統(tǒng)為Windows 10。運(yùn)行世代數(shù)為500，EGMAP-HV約運(yùn)行6 min 15 s，是所有三種算法中最快的。

表5 算法執(zhí)行時(shí)間

圖6顯示了三種算法在不同世代數(shù)下超體積指標(biāo)的變化情況，該值是每個(gè)世代中每個(gè)應(yīng)用的支配策略下得到的均值超體積值。結(jié)果顯示EGMAP-HV是三種算法中超體積性能表現(xiàn)最好的。

圖6 超體積指標(biāo)變化

綜合實(shí)驗(yàn)結(jié)果來(lái)看，EGMAP-HV算法在所有目標(biāo)值表現(xiàn)和執(zhí)行效率上均是表現(xiàn)最優(yōu)的。EGMAP-PD和EGMAP-PD-HV均使用了Pareto支配的概念，這要求在所有優(yōu)化目標(biāo)上作出多重比較。而EGMAP-HV僅經(jīng)過(guò)一重比較來(lái)決定最終的博弈勝者。Pareto支配要求嚴(yán)格的支配策略，一個(gè)策略只有在所有策略上均表現(xiàn)最優(yōu)才有可能在進(jìn)化若干世代后變?yōu)橹洳呗?。然而，在多?shù)情況下，使用Pareto支配時(shí)策略之間會(huì)相互約束，因?yàn)檫@些優(yōu)化目標(biāo)之間相互沖突的關(guān)系。

7 結(jié) 語(yǔ)

提出了一種基于進(jìn)化博弈模型的多層次云應(yīng)用部署算法。算法可以確保每個(gè)云應(yīng)用種群找到一種進(jìn)化穩(wěn)定部署策略。通過(guò)該博弈策略，在給定的系統(tǒng)負(fù)載和云資源可用性條件下，云應(yīng)用可確定其最優(yōu)的部署位置和相應(yīng)資源分配。對(duì)算法穩(wěn)定性進(jìn)行了理論分析，證明應(yīng)用種群狀態(tài)可以收斂在部署策略的進(jìn)化穩(wěn)定策略點(diǎn)上，并證明了均衡解具有漸近穩(wěn)定性。仿真實(shí)驗(yàn)結(jié)果表明，與基準(zhǔn)算法相比，新算法在應(yīng)用的響應(yīng)時(shí)間、資源利用率以及能耗指標(biāo)上均表現(xiàn)出更好的性能。