王亞利 文欣秀

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

(1)

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

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

(2)

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

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

frt=Tp+Tw+Tc

(3)

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

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

(4)

Tw計算方法如下：

(5)

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

(6)

Tc計算方法如下：

(7)

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

(8)

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

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

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

(9)

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

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

(10)

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

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

(11)

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

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

(12)

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

3 進化博弈模型

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

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

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

定義1如果對于任意策略l≠k，存在一個確定的x′∈(0,1)，使得對于所有的x∈(0,x′)，式(13)均是成立的，則稱策略k為進化穩(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，即可得到比其他策略更高的收益。因此，任意博弈者不會通過從策略k改變至其他策略上而獲得更高的收益，這表明進化穩(wěn)定策略是處于納什均衡的一個解。而進化穩(wěn)定策略也將是擁有更低種群份額的任意變異策略無法入侵的策略。

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

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

(16)

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

(17)

(18)

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

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

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

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

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

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

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

(19)

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

圖2所示為兩個應(yīng)用a1和a2的兩種示范博弈策略，此時，N=2，M=2。應(yīng)用a1的策略s(a1)將第一層虛擬機VM部署于主機1的內(nèi)核3，即h1,1=1，c1,1=3，對應(yīng)功耗為90 W，p1,1=90，并且虛擬機消耗30%的CPU份額和80 kbit/s網(wǎng)絡(luò)帶寬，即c1,1=30、b1,1=80。第二層虛擬機部署在主機1的內(nèi)核3上，即h1,2=1、c1,2=3，對應(yīng)功耗為100 W，即p1,2=100，并且消耗了30%的CPU份額和85 kbit/s網(wǎng)絡(luò)帶寬，即c1,2=30、b1,2=85。第三層虛擬機部署在主機2的內(nèi)核3上，即h1,3=2、c1,3=3，對應(yīng)功耗為83 W，即p1,2=83，虛擬機消耗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是本文算法通過進化博弈使每個應(yīng)用尋找進化穩(wěn)定策略的過程。在初始第0代種群時，針對N個應(yīng)用隨機方式生成N個種群，即N個策略，即步驟1-步驟2。在第g代種群中，每個種群實施系列博弈，即步驟4-步驟24。單次博弈隨機選擇策略對s1和s2，根據(jù)前文中描述的目標(biāo)函數(shù)，得到兩個策略間的勝者策略和敗者策略，即步驟7-步驟9。敗者策略從種群中移除，勝者策略被復(fù)制以增加其種群份額，并以概率Pm進行變異，即步驟10-步驟15。變異操作隨機從勝者種群中選擇三臺虛擬機中的一臺，并隨機變換其h值，即步驟12。

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

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

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

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

4.foreach populationPirandomly selected fromPdo

//初始化一個空種群集合

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

7.s1←randomlySelect(Pi)

//隨機種群個體

8.s2←randomlySelect(Pi)

//隨機種群個體

9. winner←performGame(s1,s2)

//兩部署策略間博弈

10. replica←replicate(winner)

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

11.ifrandom()≤Pmthen

//變異概率比較

12.replica←mutate(winner)

//對博弈勝者作變異操作

13.endif

14.Pi{s1,s2}

//從種群中剔除兩個個體

//將勝者填充至種群

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)用的虛擬機

24.endfor

25.g=g+1

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

26.endwhile

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

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

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

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

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

(20)

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

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

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

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

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

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

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

(21)

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

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

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

(22)

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

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

證明不同的策略擁有不同的適應(yīng)度值，換言之，所有策略中僅有一個策略擁有最高適應(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}處，差分等式集合可通過替換x1=1-x2-…-x|S*|進行縮?。?/p>

(23)

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

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

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

(24)

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

(25)

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

6 仿真實驗測評

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

表1 消息到達率和消耗處理時間

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

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

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

表3 仿真實驗參數(shù)配置

將本文設(shè)計的進化博弈的多層次云應(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)時間情況，統(tǒng)計了四個目標(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é)果，在種群進化下，EGMAP可以節(jié)省主機能耗，EGMAP-HV在種群世代末期的功耗平均穩(wěn)定在334 W，是所有算法中最優(yōu)的。從圖3(d)、圖4(d)和圖5(d)的結(jié)果可以看到，算法的響應(yīng)時間隨著種群世代進化呈現(xiàn)比較穩(wěn)定的狀態(tài)，這是因為響應(yīng)時間與其他目標(biāo)之間是沖突的，而EGMAP算法可以在所有目標(biāo)之間實現(xiàn)均衡優(yōu)化。EGMAP-HV在種群世代末期的平均響應(yīng)時間為26.12 ms，是算法中最優(yōu)的。

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

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

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

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

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

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

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

表4 性能對比

續(xù)表4

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

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

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

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

綜合實驗結(jié)果來看，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)過一重比較來決定最終的博弈勝者。Pareto支配要求嚴(yán)格的支配策略，一個策略只有在所有策略上均表現(xiàn)最優(yōu)才有可能在進化若干世代后變?yōu)橹洳呗?。然而，在多?shù)情況下，使用Pareto支配時策略之間會相互約束，因為這些優(yōu)化目標(biāo)之間相互沖突的關(guān)系。

7 結(jié) 語

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