樂 藝

(南京城市職業(yè)學(xué)院 江蘇 南京 210002)

0 引 言

對于云供應(yīng)商而言，部署應(yīng)用使其維持相應(yīng)的資源利用率(CPU資源和帶寬資源)和功耗的同時，滿足期望的性能等級(響應(yīng)時間)是當前在云端部署應(yīng)用任務(wù)必須解決的問題[1]。為了確保上述需求，需要通過考慮多個不同的條件，如負載和資源可用性等，調(diào)整應(yīng)用的部署目標和資源分配方案，進而動態(tài)地對應(yīng)用進行重部署。本文將重點關(guān)注云端應(yīng)用部署的適應(yīng)性和穩(wěn)定性。適應(yīng)性即根據(jù)給定目標的上下文環(huán)境，調(diào)整應(yīng)用的部署位置和資源分配；穩(wěn)定性指對于應(yīng)用的部署方案和資源分配方案，應(yīng)盡量最小化方案決策的波動。

為了實現(xiàn)云端應(yīng)用的自適應(yīng)和穩(wěn)定性的部署策略，本文提出一種基于進化博弈理論的云應(yīng)用部署算法。本文算法的每個應(yīng)用維持一個應(yīng)用部署策略集合(即一個種群)，其中每個策略表示應(yīng)用的部署位置和資源分配?？梢源_保通過部署策略間的一系列進化博弈過程[2]，種群狀態(tài)(策略分布)可以收斂至一種與初始狀態(tài)無關(guān)的進化穩(wěn)定均衡上。進化穩(wěn)定種群狀態(tài)中的占優(yōu)策略稱為進化穩(wěn)定策略。在該狀態(tài)下，除了進化穩(wěn)定策略之外，沒有任一其他策略可以占優(yōu)整個種群。在給定該理論性質(zhì)前提下，算法可以以穩(wěn)定的方式利用進化穩(wěn)定策略將云應(yīng)用部署策略運行于穩(wěn)定狀態(tài)。

1 相關(guān)工作

許多研究工作已經(jīng)在云計算應(yīng)用部署方面展開，其多數(shù)工作所考慮的應(yīng)用為單層次的應(yīng)用體系結(jié)構(gòu)，大多考慮單目標優(yōu)化，例如文獻[3-6]均只考慮了能耗節(jié)省一個目標。相比而言，本文算法考慮的是一種多層次的應(yīng)用體系，考慮了多目標的同步優(yōu)化，且可以在多個沖突目標間尋找平衡。

目前，博弈論方法已經(jīng)被用于云計算的諸多方面，如應(yīng)用部署[7-9]、任務(wù)分配[10]及數(shù)據(jù)副本調(diào)度[11]等。文獻[7-9]將基于貪婪思想的算法用于尋找應(yīng)用部署問題的均衡解，但貪婪思想并不能確保所達到的部署均衡解具有好的穩(wěn)定性。而本文算法將通過進化博弈中的復(fù)制動態(tài)機制確保得到的均衡解是具有漸近穩(wěn)定性的。

遺傳算法[12-13]和其他隨機式優(yōu)化算法[14-15]也可用于求解云計算中的應(yīng)用部署問題。這些算法雖然可以尋找最優(yōu)部署解，但也無法保證其穩(wěn)定性。相比而言，本文算法將尋找進化穩(wěn)定解，并驗證其解可以收斂在均衡解上。

文獻[16]的工作與本文有些類似，但本文在問題形式化上對其進行了擴充。本文在其基礎(chǔ)上另外加入了帶寬分配和功耗兩個目標優(yōu)化，同時在每個部署策略中考慮了帶寬分配參數(shù)，這與實際的云計算環(huán)境中需要考慮的問題也更加貼近。同時，本文在仿真環(huán)境中進行大量實際應(yīng)用負載的仿真實驗，可以更加準確地評估與測試算法的性能。

2 問題描述

本節(jié)對云應(yīng)用部署問題做形式化描述。假設(shè)現(xiàn)有M臺主機用于部署N個云應(yīng)用，每個應(yīng)用設(shè)計為三層服務(wù)器模型，即每個應(yīng)用的執(zhí)行需要按序通過外層的Web服務(wù)器、中間的應(yīng)用服務(wù)器及后臺的數(shù)據(jù)庫服務(wù)器，然后通過后臺服務(wù)器返回至外層的Web前臺顯示應(yīng)用執(zhí)行結(jié)果，該模型如圖1所示。其中：Web服務(wù)器接收應(yīng)用任務(wù)的HTTP消息，驗證消息中的數(shù)據(jù)并向提交應(yīng)用的用戶提供Web用戶接口；APP應(yīng)用服務(wù)器執(zhí)行相應(yīng)功能的應(yīng)用邏輯并處理用戶提交的數(shù)據(jù)；Database數(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)用部署問題的目標是尋找一種進化穩(wěn)定策略，該策略將N個應(yīng)用(即N×3臺虛擬機)部署于M臺主機上，使得對于給定的負載條件和可用資源下，應(yīng)用能夠適應(yīng)其部署位置和資源分配，并實現(xiàn)以下相關(guān)目標的最小化。

3) 響應(yīng)時間表示消息從Web服務(wù)器傳輸至數(shù)據(jù)庫服務(wù)器間所需要的時間，表示為Tp+Tw+Tc，其中：Tp表示應(yīng)用在三臺服務(wù)器上處理用戶發(fā)出消息的總時間，Tw表示消息在服務(wù)器上等待處理的時間，Tc表示消息在服務(wù)器傳輸?shù)目傃訒r。Tp、Tw和Tc三者通過M/M/1隊列模型估算，應(yīng)用的消息到達服從泊松分布，服務(wù)器的消息處理時間按指數(shù)分布。

(1)

Tw計算方法如下：

(2)

(3)

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

Tc計算方法如下：

(4)

t′=t+1

4) 功耗表示應(yīng)用執(zhí)行過程中主機運行三臺虛擬機時的總體功耗，單位為W，定義為：

(5)

將CPU能力約束考慮為：對于所有M臺主機，wi≤1，wi表示分配給第i臺主機的總CPU時間份額。該約束的違例條件可計算為：

(6)

若wi>1，則Ii=1；否則，Ii=0。

考慮的帶寬能力約束為：對于所有的M臺主機，yi≤1，yi表示分配給第i臺主機的總帶寬量(百分比形式表示)。該約束的違例條件可計算為：

(7)

若yi>1，則Ii=1；否則，Ii=0。

3 進化博弈理論

對于傳統(tǒng)的博弈論而言，博弈者的目標是選擇一個使其收益最大化的策略。相比而言，進化博弈是種群中博弈者隨機式重復(fù)的博弈過程。本節(jié)介紹進化博弈的兩個關(guān)鍵要素：進化穩(wěn)定策略ESS和復(fù)制動態(tài)。

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

假設(shè)初始種群中所有博弈者的博弈策略為k，有一小部分種群的博弈者比例為x，x∈(0,1)，其出現(xiàn)策略變異，執(zhí)行不同的變異策略l。當一個博弈者參與到博弈過程中時，其對手執(zhí)行策略k和l的比例分別為1-x和x。因此，執(zhí)行策略k和l的博弈者的期望收益分別為U(k,xl+(1-x)k)和U(l,xl+(1-x)k)。

定義1一個策略k為進化穩(wěn)定策略，若對于每個策略l≠k，存在一個確定的x′∈(0,1)，使得對于所有的x∈(0,x′)，如式(8)所示的不等式恒成立。

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

(8)

如果支付函數(shù)為線性，則由式(8)可推出：

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

(9)

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

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

(10)

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

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

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

(11)

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

(12)

在復(fù)制動態(tài)中，種群份額xk的動態(tài)可作如下描述：

(13)

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

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

納什均衡與復(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ōu)策略。

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

4 算法設(shè)計

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

(14)

式中：ai表示第i個應(yīng)用；hi,t表示執(zhí)行應(yīng)用ai的第t層虛擬機的主機ID；ci,t表示應(yīng)用ai的第t層虛擬機的CPU份額分配；bi,t表示應(yīng)用ai的第t層虛擬機的帶寬分配；fi,t表示主機hi,t的CPU頻率。圖2所示為兩個應(yīng)用a1和a2的兩種示例策略，N=2，M=3，圖中：應(yīng)用a1的策略s(a1)將第一層虛擬機VM部署于主機1上，即h1,1=1，其運行于1 GHz的CPU頻率，虛擬機消耗30%的CPU份額和80 Kbit/s帶寬，即c1,1=30，b1,1=80；第二層虛擬機部署于主機1，即h1,2=1，其消耗了30%的CPU份額和85 Kbit/s帶寬，即c1,2=30，b1,2=85；第三層虛擬機部署于主機2，即h1,3=2，其運行于2 GHz的CPU頻率，虛擬機消耗45%的CPU份額和120 Kbit/s帶寬，即c1,3=45，b1,3=120。給定s(a1)，應(yīng)用a1在CPU分配和帶寬分配上的目標值為105%和285 Kbit/s。

圖2 部署策略示例

算法1所示為本文算法通過進化博弈使每個應(yīng)用尋找進化穩(wěn)定策略的過程。

算法1基于進化博弈的虛擬機部署算法

1.g=0

2. randomly generate the initialNpopulations forNapplications:P={P1,P2,…,PN}

3.whileg

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)

11.ifrandom()≤Pmthen

12.replica←mutate(winner)

13.endif

14.Pi{s1,s2}

16.endfor

19.whilediis infeasibledo

20.Pi{di}

22.endwhile

23.deploy VMs for the current application based ondi

24.endfor

25.g=g+1

26.endwhile

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

一旦種群中的所有策略參與博弈，算法即識別可行策略，其種群份額xs為最高，并將其作為一個占優(yōu)策略di，即步驟18-步驟22。若策略從不違背CPU和帶寬能力的約束，則可認為該策略為可行策略。算法根據(jù)占優(yōu)策略部署應(yīng)用的三臺虛擬機。

算法1步驟9的performGame()中，博弈勝者的選擇取決于給定的兩個策略的占優(yōu)關(guān)系及其可行性。定義一個策略s1占優(yōu)另一個策略s2，表示為s1>s2，當且僅當:(1)s1的目標值優(yōu)于或等于s2的所有目標值；(2)s1的目標值優(yōu)于s2的至少一個目標值。

5 穩(wěn)定性分析

本節(jié)分析算法的穩(wě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的種群份額，且：

(15)

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

(16)

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

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

證明：不同的策略擁有不同的適應(yīng)度值，換言之，所有策略中僅有一個策略擁有最高適應(yīng)度值。根據(jù)定理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>

(17)

式中：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的元素為：

(18)

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

(19)

對于所有s，cs1=-Φ(F1-Fs)，Zeq={0,0,…,0}是漸近穩(wěn)定的。證畢。

6 仿真實驗

本節(jié)通過仿真實驗驗證算法的適應(yīng)性和穩(wěn)定性。利用CLOUDSIM構(gòu)建云計算環(huán)境，建立的云數(shù)據(jù)中心仿真環(huán)境由100臺主機組成，即M=100，主機分布于10×10的網(wǎng)格拓撲結(jié)構(gòu)中。假設(shè)執(zhí)行5種類型的云應(yīng)用，表1給出了5種應(yīng)用的消息到達率(即每秒到達的消息數(shù))和消息在不同服務(wù)器上的處理時間(單位為秒)。仿真實驗中針對每種應(yīng)用類型執(zhí)行40個實用實例，即一共執(zhí)行200個應(yīng)用實例，N=200。

表1 應(yīng)用類型及其屬性

假設(shè)每臺主機配置AMD皓龍2218型CPU，該CPU擁有6種運行頻率/電壓組合，表2給出了在CPU利用率為0%和100%時每種頻率/電壓組合下的功耗，該參數(shù)配置可用于計算功耗目標值。

表2 CPU可運行的頻率狀態(tài)及功耗

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

圖3所示為四個優(yōu)化目標同步考慮時得到的目標值的性能表現(xiàn)情況，圖中統(tǒng)計了單個目標值的最大值、最小值和平均值隨著種群代數(shù)增加的變化情況?？梢?，本文算法較好地均衡了不同目標值，使得算法在CPU的分配、響應(yīng)時間、帶寬分配及功耗方面取得了較好的性能均衡。

(a) CPU分配

(b) 響應(yīng)時間

(c) 帶寬分配

(d) 功耗

表3所示為本文算法與經(jīng)典進化多目標遺傳算法NSGA-II、首次適應(yīng)算法FFA、最佳適應(yīng)算法BFA的比較結(jié)果。表3給出了最后一個種群代數(shù)中優(yōu)化目標值的最小值、平均值和最大值。在所有的目標中，本文算法均優(yōu)于NSGA-II算法，性能的最大差異出現(xiàn)在CPU未使用DVFS時的最小帶寬分配結(jié)果上，性能差異約為40%，而性能的最小差異則出現(xiàn)在CPU使用DVFS時的最大響應(yīng)時間上，性能差異約為16.6%。平均來說，本文算法的性能優(yōu)于NSGA-II算法為24.19%。若CPU不使用DVFS技術(shù)，F(xiàn)FA算法擁有最低的功耗，由于該算法的設(shè)計宗旨是以最小化利用主機數(shù)量部署虛擬機為目標的，因此在其他目標上表現(xiàn)不佳。BFA算法在CPU分配方面是最優(yōu)的，但在功耗方面表現(xiàn)最差，原因在于該算法在主機上部署虛擬機是尋找最適宜的主機，使得剩余資源具有更高的可用性。本文算法兼顧考慮了四個目標值，獲得了處于FFA和BFA之間更為均衡的目標值，并在響應(yīng)時間和帶寬分配上獲得了最優(yōu)的性能表現(xiàn)。

表3 性能比較

表4所示為20次不同的仿真實驗中在最后一代種群中本文算法和NSGA-II算法在目標值上的方差，越低的方差表明在目標值上更好的穩(wěn)定性(即不同仿真實驗下目標值上更小的波動)。顯然，本文算法比NSGA-II算法維持了更連續(xù)和更高的穩(wěn)定性，其平均穩(wěn)定性為29.32%，高于NSGA-II算法。該結(jié)果表明，本文算法相較NSGA-II算法具有穩(wěn)定屬性，因為本文算法可以找到部署方案的進化穩(wěn)定策略ESS。

表4 兩種算法在目標值上的穩(wěn)定性

圖4是本文算法與NSGA-II算法在不同種群代數(shù)下算法執(zhí)行時間的性能表現(xiàn)。可以看到，本文算法的執(zhí)行比NSGA-II算法快約74.1%，可見本文的進化博弈方法不僅可以在目標值的同步優(yōu)化取得較好的效果，而且算法的執(zhí)行效率也較高。

圖4 計算代價比較

7 結(jié) 語

為了實現(xiàn)云環(huán)境中自適應(yīng)性和穩(wěn)定性的應(yīng)用執(zhí)行與部署，本文提出了一種基于進化博弈理論的多目標虛擬機部署算法。該算法可以確保每個云應(yīng)用找到一種進化穩(wěn)定部署策略，在該策略下，對于給定的系統(tǒng)負載和資源可用性，應(yīng)用可確定其部署位置和相應(yīng)資源分配，證明了種群狀態(tài)可收斂于部署策略的進化穩(wěn)定策略ESS上，且得到的均衡解是漸近穩(wěn)定的。結(jié)果表明，在響應(yīng)時間、資源利用率、功耗等指標上，該算法均表現(xiàn)出較好的性能。