一種基于進化博弈理論的虛擬機部署算法

樂 藝

(南京城市職業學院 江蘇 南京 210002)

0 引 言

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

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

1 相關工作

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

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

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

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

2 問題描述

本節對云應用部署問題做形式化描述。假設現有M臺主機用于部署N個云應用，每個應用設計為三層服務器模型，即每個應用的執行需要按序通過外層的Web服務器、中間的應用服務器及后臺的數據庫服務器，然后通過后臺服務器返回至外層的Web前臺顯示應用執行結果，該模型如圖1所示。其中：Web服務器接收應用任務的HTTP消息，驗證消息中的數據并向提交應用的用戶提供Web用戶接口；APP應用服務器執行相應功能的應用邏輯并處理用戶提交的數據；Database數據庫服務器則進行數據訪問與存儲。每條消息順序地從Web服務器通過應用服務器到數據庫服務器進行處理，響應消息則反向從數據庫服務器返回。本文假設不同的云應用利用不同的服務器集合，且服務器在不同應用間不進行共享。每臺服務器假設運行于一臺主機的虛擬機上，且一臺主機可以運行多臺虛擬機，它們可以共享本地主機上的可用資源。

圖1 應用執行的三層模型

云應用部署問題的目標是尋找一種進化穩定策略，該策略將N個應用(即N×3臺虛擬機)部署于M臺主機上，使得對于給定的負載條件和可用資源下，應用能夠適應其部署位置和資源分配，并實現以下相關目標的最小化。

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

(1)

Tw計算方法如下：

(2)

(3)

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

Tc計算方法如下：

(4)

t′=t+1

4) 功耗表示應用執行過程中主機運行三臺虛擬機時的總體功耗，單位為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 進化博弈理論

對于傳統的博弈論而言，博弈者的目標是選擇一個使其收益最大化的策略。相比而言，進化博弈是種群中博弈者隨機式重復的博弈過程。本節介紹進化博弈的兩個關鍵要素：進化穩定策略ESS和復制動態。

3.1 進化穩定策略ESS

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

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

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

(8)

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

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

(9)

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

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

(10)

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

3.2 復制動態

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

(11)

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

(12)

在復制動態中，種群份額xk的動態可作如下描述：

(13)

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

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

納什均衡與復制動態的穩定狀態間聯系密切，其穩定狀態下的種群份額將不會隨著時間而發生改變。由于處于納什均衡時沒有博弈者會改變其策略，復制動態中的每一個納什均衡都將是一種穩定狀態。如前文所述，一個進化穩定策略是一個納什均衡處的一個解，因此，進化穩定策略即為復制動態中處于穩定狀態的一個解。換言之，進化穩定策略是種群中處于穩定狀態的嚴格占優策略。

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

4 算法設計

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

(14)

式中：ai表示第i個應用；hi,t表示執行應用ai的第t層虛擬機的主機ID；ci,t表示應用ai的第t層虛擬機的CPU份額分配；bi,t表示應用ai的第t層虛擬機的帶寬分配；fi,t表示主機hi,t的CPU頻率。圖2所示為兩個應用a1和a2的兩種示例策略，N=2，M=3，圖中：應用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)，應用a1在CPU分配和帶寬分配上的目標值為105%和285 Kbit/s。

圖2 部署策略示例

算法1所示為本文算法通過進化博弈使每個應用尋找進化穩定策略的過程。

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

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

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

5 穩定性分析

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

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

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

(15)

Fs代表策略s的適應度值，該值是根據不同博弈者之間的占優關系決定的相對值，博弈勝者比敗者擁有更高的適應度值。

(16)

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

定理2種群狀態收斂于均衡上。

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

定理3定理2中得到的均衡是漸近穩定的。

證明：在均衡X={1,0,…,0}處，差分等式集合可通過替換x1=1-x2-…-x|S*|進行縮小：

(17)

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

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

(18)

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

(19)

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

6 仿真實驗

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

表1 應用類型及其屬性

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

表2 CPU可運行的頻率狀態及功耗

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

圖3所示為四個優化目標同步考慮時得到的目標值的性能表現情況，圖中統計了單個目標值的最大值、最小值和平均值隨著種群代數增加的變化情況。可見，本文算法較好地均衡了不同目標值，使得算法在CPU的分配、響應時間、帶寬分配及功耗方面取得了較好的性能均衡。

(a) CPU分配

(b) 響應時間

(c) 帶寬分配

(d) 功耗

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

表3 性能比較

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

表4 兩種算法在目標值上的穩定性

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

圖4 計算代價比較

7 結 語

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