云計算基于隨機進化博弈動態的資源優化配置

尹 成 國

(海南熱帶海洋學院計算機科學與技術學院 海南 三亞 572022)

0 引 言

云計算通過其數據中心可以按需提供計算、存儲、通信等資源服務于大規模分布環境[1]。云環境中的資源分配機制要求向云用戶提供資源用于處理作業和存儲數據，常用的資源提供手段包括按需提供和預留式提供[2]。按需提供時的定價是以即付即用為基礎的，按需資源提供可以適應于具有波動和不可預測的資源需求狀況。而預留式提供則可能有效利用空閑資源，且其價格低于按需提供。

由于云環境中參與實體的異構性和動態特性，資源的分配與管理是異常復雜的。很多研究利用經濟學的思想完成資源分配優化問題，即博弈論的思想，這源于云環境中的資源管理與社會經濟學活動擁有極大的相似性[3]。博弈理論可以通過搜索均衡解，利用迭代的方法將云資源分配形式化為效用優化問題。當前的相關研究主要包括三種類型的經濟學博弈模型：(1) 基于合作式博弈的資源分配方法，通過將多個云用戶組成為聯盟的形式進行資源分配，以增加實體效用[4-5]。(2) 基于非合作式博弈的資源分配方法，利用云實體間的相互影響，采用對實體的基礎的理性假設，讓博弈者得到最大化的收益，并對行為策略擁有很好的判斷和預測[6-7]。(3) 基于進化式博弈的資源分配方法，擁有有限理性的云實體間的博弈求解問題[8-9]。然而，通常情況下，現實環境中的云用戶對于資源使用的行為難免會發生錯誤，這表明用戶的策略均衡不是僅能通過一次性的動態調整得到的[10]。同時，以上研究均是在無限制的云種群環境中進行的，這也與實際情況不符。本文將利用隨機動態機制研究有限云種群中的資源分配進化博弈問題，并通過用戶策略的固定指數與入侵指數，求解不同種群大小中策略的進化方向。

1 資源分配模型

假設云計算系統擁有N個用戶競爭資源，資源通過市場機制分配和提供，即通過資源價格的波動反映資源供求關系的變化。換言之，此時的資源分配取決于所有云用戶對資源的出價策略。

定義1假設每個用戶向資源方提交的一個競價si，那么，s={s1,s2,…,sN}表示所有競爭用戶的競價集。如果si∈R，s為N個元素的向量。如果si為多維數值，則s為M×N矩陣，M為向量si的維度。

本文將維度限定為一維空間，那么，資源分享σi∈[0,1]即代表第i個競價用戶所分配的資源份額，且定義為：

(1)

假設每個用戶對于獲得的資源份額σi擁有一個評估函數vi(σi)，該評估可視為給定資源份額下對于性能的價值評估，如在計算市場中處理作業的完成時間或給定帶寬份額下數據的傳輸時間。每個性能度量可轉換成一個可與競價相比較的等價值。如果用戶的評估是連續可微分的，則本文的博弈算法中用戶的效用函數可定義為評估與其競價的差值，即：

Ui=vi(σi)-si

(2)

2 進化博弈的效用矩陣

為了簡化分析，本文的博弈模型中云用戶被抽象為兩種具有有限理性的用戶種群。換言之，博弈即是研究具有兩種策略x和y的進化動態過程，這表明每個用戶在競價博弈過程中將面臨兩種競價策略博弈的進化動態過程。博弈框架的效用矩陣可表達為對稱2×2矩陣，如表1所示。

表1 兩種策略下的博弈效用矩陣

效用矩陣的含義可理解為：當面對另一采用策略x的用戶時，用戶采用策略x的效用為a，而面對另一采用策略y的用戶時，用戶采用策略x的效用為c，其他依此類推。兩種用戶策略x和y定義為競價ky和競價y，y為用戶預算，k為常數，0

(3)

(4)

(5)

(6)

令px和py分別表示采用策略x和策略y的用戶比例，則：

px+py=1

(7)

采用x和y的用戶效用為：

Ux=apx+bpy=apx+b(1-px)

(8)

Uy=cpx+dpy=cpx+d(1-px)

(9)

云用戶種群的平均效用為：

(10)

效用作為云用戶反映其目標和偏好的質量指標，在重復博弈過程中，較優的策略將為用戶帶來更高的效用，并感染云種群采用較差的策略。

復制方程集合描述了決策選擇過程，每種策略的平均增長率為其適應度與整個種群的平均適應度之差得到。

由于px+py=1，可知:

(11)

且:

Ux-Uy=(a-c)px+(b-d)(1-px)

(12)

如圖1所示，均衡點或者在邊界或者在內部，有以下五種常見情況：

1) 當a>c且b>d時，種群進化最終將由利用策略x的用戶組成。唯一穩定均衡點為px=1。策略x為嚴格Nash均衡，即為進化穩定策略ESS，策略y不是。形態表示為x←y。

2) 當a

5) 當a=c且b=d時，整個種群維持當前狀態，策略x和y具有同等偏好。代與代之間的進化不作改變。形態表示為x--y。

圖1 不同穩定點的圖示

3 基于Moran過程的選擇動態

對于有限云種群中的進化博弈，N個個體的策略的選擇動態可形式化為帶來頻率依賴適應度的Moran過程[11]。假設云種群由N個云用戶組成，采用策略x的用戶數量為i，則采用策略x的用戶比例為(N-i)/N，每個采用策略x的用戶需與其他們用戶博弈。根據式(8)，采用策略x的用戶效用可定義為：

(13)

采用策略y的用戶數量為N-i，則根據式(9)，該類用戶效用為：

(14)

令Ti,i+1表示用戶數增加一個的概率，Ti,i-1表示用戶減少一個的概率，Ti,i表示用戶保持不變的概率，則：

(15)

(16)

Ti,i=1-Ti,i+1-Ti,i-1

(17)

轉移矩陣為：

(18)

式(18)表示云種群的狀態變化轉移矩陣僅在三條對角線上可以進行轉換，其他概率均為0，這是由于相同類型的用戶不會增加或減少多于兩個。

進化博弈擁有兩個吸收態，即i=0和i=N。i=0表示所有云用戶采用策略x，i=N表示所有云用戶采用策略y。當云種群到達兩個狀態之一時，這種狀態將保持穩定。否則，擁有更高效用的策略將入侵擁有低效用的策略。以下將計算兩個狀態間的吸收概率。

令ri表示采用策略x的用戶數量從i改變為N的概率，即從狀態變為狀態i=N的概率。ri可表示為遞歸關系式：

ri=Ti,i+1ri+1+Ti,iri+Ti,i-1ri-1

(19)

明顯地，ri擁有兩個吸收點r0=0和rN=1，其中，r0=0表示當沒有用戶采用策略x時用戶數量從N變為0的概率，rN=1表示當所有用戶采用策略x時云種群狀態保持穩定的概率。換言之，采用策略y的概率為0。

將式(15)-式(17)代入式(19)，則：

ri=Ti,i+1ri+1+(1-Ti,i+1-Ti,i-1)ri+Ti,i-1ri-1=

Ti,i+1(ri+1-ri)-Ti,i-1(ri-ri-1)+ri?

Ti,i+1(ri+1-ri)-Ti,i-1(ri-ri-1)=0

(20)

令wi=ri-ri-1，根據式(13)、式(14)和式(20)，則：

(21)

將r0=0代入式(21)，則：

(22)

將rN=1代入式(22)，則：

(23)

聯合式(22)和式(23)，有：

(24)

根據式(24)，定義兩種概率θx→y=r1和θy→x=1-rN-1。前者表示種群中一個x用戶變化為y用戶且固定的概率，后者則反之。定義θx→y和θy→x為兩固定指數，當θx→y變大時，選擇策略x的用戶將逐步入侵整個種群，當θy→x增加時，選擇策略x的用戶將被其他策略代替，則：

(25)

當采用策略x和y的用戶擁有相同效用時，稱為中立變種，其固定指數為1/N。本文利用1/N作為有限云種群中搜索策略選擇動態的基準。顯然，如果θx→y>1/N，則策略選擇將偏好策略x代替策略y；如果θx→y<1/N，策略選擇將反對策略x代替策略y。

4 有限云種群中的選擇動態

定義另一種度量指數，稱為入侵指數，表示為：

(26)

通過式(26)，可以比較每個i下的Uxi和Uyi，評估在位置i上該選擇是否增加或減少了策略x的用戶數量。聯合式(13)和式(14)可知，入侵動態可以φ1和φN-1的形式表示。入侵指數φ1和φN-1可以評估是否采用策略x或y的單個用戶擁有比整個種群更大的效用。如果φ1>1，則策略選擇偏好策略x入侵策略y；如果φN-1<1，策略選擇偏策略y入侵策略x。

從式(24)、式(26)、式(13)和式(14)可以發現，固定指數和入侵指數在其表達上擁有不同的復雜性。入侵指數表達更加簡單，為用戶效用矩陣和種群N的函數，函數φ1和φN-1用于評估當采用策略x的用戶數量為i時是否其用戶數量在下一步將增加或減少。然而，固定指數的表達更加復雜，無法明確通過N顯示。函數θx→y和θy→x用于度量進化博弈中用戶策略保持穩定的概率。

由于固定指數和入侵指數均取決于N，即種群大小對于用戶策略的選擇動態具有重要影響。實驗中將研究固定效用矩陣中N值的改變對選擇動態的影響。

5 數值分析

本節利用數值實驗觀察在具體的效用矩陣中不同種群大小N下用戶策略的進化方向變化。定義兩種評估函數分別為v1i(σi)=4/σi(實驗1)和v2i(σi)=4ln(1+σi)(實驗2)，σi為分配給i的資源分配比例。令k=1/2和y=2，則云用戶的競價策略包括競價為1和競價為2。

表2 具有兩種策略的博弈效用矩陣

給出效用矩陣后，固定指數和入侵指數僅為種群大小N的函數。圖2-圖5為MATLAB下的數值分析結果，表示在有限云種群中入侵指數和固定指數的變化情況。圖2顯示當種群大小增加時，用戶效用增加較少，甚至保持不變。圖3顯示當種群大小很小時，固定指數發生了顯著變化。隨著種群增加，固定指數趨于平衡。在不同種群規模下量化的數值如圖4和圖5，具體地：

(1) 對于N≤5,φ1,φN-1>1且θx→y<1/N<θy→x，策略選擇偏好策略x，且該策略將逐步占據整個種群。

(2) 對于51/N，策略選擇偏好發生變化，這取決于用戶的策略選擇。

(3) 對于81/N，策略選擇維持不變狀態。

圖2 效用變化

圖3 固定指數

圖4 表2效用矩陣得到的入侵指數

圖5 表2效用矩陣得到的固定指數

表3 兩種策略的效用矩陣

對于無限的種群大小，策略x的適應度大于策略y。因此，可以說策略x占優y，這表明策略x為嚴格Nash均衡或進化穩定策略ESS，而y不是。對于有限的種群大小，可以看出根據N有五種情況。隨著N的增加，策略x逐步獲得對于y的占優。同時，注意到a+d>b+c，策略選擇對于任意N均不會偏好作出改變。而a+b>c+d，對于較大的種群大小，策略選擇不會偏好y。如圖6和圖7所示，有：

圖6 表3效用矩陣得到的固定指數

圖7 表3效用矩陣得到的入侵指數

6 結 語

本文提出一種隨機動態模型，研究了有限云種群環境中的資源分配的進化博弈問題。通過對稱的用戶2×2效用矩陣，將用戶對資源的競價形式形式化為進化博弈，利用Moran過程尋找重復博弈過程中用戶的策略選擇在固定指數和入侵指數上的進化動態，求解了用戶種群在策略選擇上的演化方向。通過兩個具體的效用矩陣的數值分析，證明了該博弈算法下用戶為了最大化自身效用，其策略選擇對于不同的種群大小進化方向是不同的。