云計(jì)算基于隨機(jī)進(jìn)化博弈動(dòng)態(tài)的資源優(yōu)化配置

尹 成 國(guó)

(海南熱帶海洋學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 海南 三亞 572022)

0 引 言

云計(jì)算通過(guò)其數(shù)據(jù)中心可以按需提供計(jì)算、存儲(chǔ)、通信等資源服務(wù)于大規(guī)模分布環(huán)境[1]。云環(huán)境中的資源分配機(jī)制要求向云用戶(hù)提供資源用于處理作業(yè)和存儲(chǔ)數(shù)據(jù)，常用的資源提供手段包括按需提供和預(yù)留式提供[2]。按需提供時(shí)的定價(jià)是以即付即用為基礎(chǔ)的，按需資源提供可以適應(yīng)于具有波動(dòng)和不可預(yù)測(cè)的資源需求狀況。而預(yù)留式提供則可能有效利用空閑資源，且其價(jià)格低于按需提供。

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

1 資源分配模型

假設(shè)云計(jì)算系統(tǒng)擁有N個(gè)用戶(hù)競(jìng)爭(zhēng)資源，資源通過(guò)市場(chǎng)機(jī)制分配和提供，即通過(guò)資源價(jià)格的波動(dòng)反映資源供求關(guān)系的變化。換言之，此時(shí)的資源分配取決于所有云用戶(hù)對(duì)資源的出價(jià)策略。

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

本文將維度限定為一維空間，那么，資源分享σi∈[0,1]即代表第i個(gè)競(jìng)價(jià)用戶(hù)所分配的資源份額，且定義為：

(1)

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

Ui=vi(σi)-si

(2)

2 進(jìn)化博弈的效用矩陣

為了簡(jiǎn)化分析，本文的博弈模型中云用戶(hù)被抽象為兩種具有有限理性的用戶(hù)種群。換言之，博弈即是研究具有兩種策略x和y的進(jìn)化動(dòng)態(tài)過(guò)程，這表明每個(gè)用戶(hù)在競(jìng)價(jià)博弈過(guò)程中將面臨兩種競(jìng)價(jià)策略博弈的進(jìn)化動(dòng)態(tài)過(guò)程。博弈框架的效用矩陣可表達(dá)為對(duì)稱(chēng)2×2矩陣，如表1所示。

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

效用矩陣的含義可理解為：當(dāng)面對(duì)另一采用策略x的用戶(hù)時(shí)，用戶(hù)采用策略x的效用為a，而面對(duì)另一采用策略y的用戶(hù)時(shí)，用戶(hù)采用策略x的效用為c，其他依此類(lèi)推。兩種用戶(hù)策略x和y定義為競(jìng)價(jià)ky和競(jìng)價(jià)y，y為用戶(hù)預(yù)算，k為常數(shù)，0

(3)

(4)

(5)

(6)

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

px+py=1

(7)

采用x和y的用戶(hù)效用為：

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

(8)

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

(9)

云用戶(hù)種群的平均效用為：

(10)

效用作為云用戶(hù)反映其目標(biāo)和偏好的質(zhì)量指標(biāo)，在重復(fù)博弈過(guò)程中，較優(yōu)的策略將為用戶(hù)帶來(lái)更高的效用，并感染云種群采用較差的策略。

復(fù)制方程集合描述了決策選擇過(guò)程，每種策略的平均增長(zhǎng)率為其適應(yīng)度與整個(gè)種群的平均適應(yīng)度之差得到。

由于px+py=1，可知:

(11)

且:

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

(12)

如圖1所示，均衡點(diǎn)或者在邊界或者在內(nèi)部，有以下五種常見(jiàn)情況：

1) 當(dāng)a>c且b>d時(shí)，種群進(jìn)化最終將由利用策略x的用戶(hù)組成。唯一穩(wěn)定均衡點(diǎn)為px=1。策略x為嚴(yán)格Nash均衡，即為進(jìn)化穩(wěn)定策略ESS，策略y不是。形態(tài)表示為x←y。

2) 當(dāng)a

5) 當(dāng)a=c且b=d時(shí)，整個(gè)種群維持當(dāng)前狀態(tài)，策略x和y具有同等偏好。代與代之間的進(jìn)化不作改變。形態(tài)表示為x--y。

圖1 不同穩(wěn)定點(diǎn)的圖示

3 基于Moran過(guò)程的選擇動(dòng)態(tài)

對(duì)于有限云種群中的進(jìn)化博弈，N個(gè)個(gè)體的策略的選擇動(dòng)態(tài)可形式化為帶來(lái)頻率依賴(lài)適應(yīng)度的Moran過(guò)程[11]。假設(shè)云種群由N個(gè)云用戶(hù)組成，采用策略x的用戶(hù)數(shù)量為i，則采用策略x的用戶(hù)比例為(N-i)/N，每個(gè)采用策略x的用戶(hù)需與其他們用戶(hù)博弈。根據(jù)式(8)，采用策略x的用戶(hù)效用可定義為：

(13)

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

(14)

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

(15)

(16)

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

(17)

轉(zhuǎn)移矩陣為：

(18)

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

進(jìn)化博弈擁有兩個(gè)吸收態(tài)，即i=0和i=N。i=0表示所有云用戶(hù)采用策略x，i=N表示所有云用戶(hù)采用策略y。當(dāng)云種群到達(dá)兩個(gè)狀態(tài)之一時(shí)，這種狀態(tài)將保持穩(wěn)定。否則，擁有更高效用的策略將入侵擁有低效用的策略。以下將計(jì)算兩個(gè)狀態(tài)間的吸收概率。

令ri表示采用策略x的用戶(hù)數(shù)量從i改變?yōu)镹的概率，即從狀態(tài)變?yōu)闋顟B(tài)i=N的概率。ri可表示為遞歸關(guān)系式：

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

(19)

明顯地，ri擁有兩個(gè)吸收點(diǎn)r0=0和rN=1，其中，r0=0表示當(dāng)沒(méi)有用戶(hù)采用策略x時(shí)用戶(hù)數(shù)量從N變?yōu)?的概率，rN=1表示當(dāng)所有用戶(hù)采用策略x時(shí)云種群狀態(tài)保持穩(wěn)定的概率。換言之，采用策略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，根據(jù)式(13)、式(14)和式(20)，則：

(21)

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

(22)

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

(23)

聯(lián)合式(22)和式(23)，有：

(24)

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

(25)

當(dāng)采用策略x和y的用戶(hù)擁有相同效用時(shí)，稱(chēng)為中立變種，其固定指數(shù)為1/N。本文利用1/N作為有限云種群中搜索策略選擇動(dòng)態(tài)的基準(zhǔn)。顯然，如果θx→y>1/N，則策略選擇將偏好策略x代替策略y；如果θx→y<1/N，策略選擇將反對(duì)策略x代替策略y。

4 有限云種群中的選擇動(dòng)態(tài)

定義另一種度量指數(shù)，稱(chēng)為入侵指數(shù)，表示為：

(26)

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

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

由于固定指數(shù)和入侵指數(shù)均取決于N，即種群大小對(duì)于用戶(hù)策略的選擇動(dòng)態(tài)具有重要影響。實(shí)驗(yàn)中將研究固定效用矩陣中N值的改變對(duì)選擇動(dòng)態(tài)的影響。

5 數(shù)值分析

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

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

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

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

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

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

圖2 效用變化

圖3 固定指數(shù)

圖4 表2效用矩陣得到的入侵指數(shù)

圖5 表2效用矩陣得到的固定指數(shù)

表3 兩種策略的效用矩陣

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

圖6 表3效用矩陣得到的固定指數(shù)

圖7 表3效用矩陣得到的入侵指數(shù)

6 結(jié) 語(yǔ)

本文提出一種隨機(jī)動(dòng)態(tài)模型，研究了有限云種群環(huán)境中的資源分配的進(jìn)化博弈問(wèn)題。通過(guò)對(duì)稱(chēng)的用戶(hù)2×2效用矩陣，將用戶(hù)對(duì)資源的競(jìng)價(jià)形式形式化為進(jìn)化博弈，利用Moran過(guò)程尋找重復(fù)博弈過(guò)程中用戶(hù)的策略選擇在固定指數(shù)和入侵指數(shù)上的進(jìn)化動(dòng)態(tài)，求解了用戶(hù)種群在策略選擇上的演化方向。通過(guò)兩個(gè)具體的效用矩陣的數(shù)值分析，證明了該博弈算法下用戶(hù)為了最大化自身效用，其策略選擇對(duì)于不同的種群大小進(jìn)化方向是不同的。