基于馬爾科夫博弈的云代理與微云收益優(yōu)化

張鋒輝，符茂勝，何富貴

(皖西學(xué)院 電子與信息工程學(xué)院，安徽 六安 237012)

0 引 言

由于移動(dòng)設(shè)備的計(jì)算資源和電池容量極為有限，使得計(jì)算密集型應(yīng)用在移動(dòng)端的實(shí)施面臨挑戰(zhàn)，解決這一挑戰(zhàn)有效方法是將計(jì)算密集型任務(wù)卸載到云上執(zhí)行，這種方法稱(chēng)為移動(dòng)云計(jì)算[1]。由于微云相比遠(yuǎn)程云計(jì)算中心距離移動(dòng)設(shè)備更近，可以大幅度減少傳輸延遲，因此使用微云進(jìn)行計(jì)算卸載是移動(dòng)云計(jì)算的發(fā)展趨勢(shì)[2]。

卸載任務(wù)到微云具有提高云計(jì)算效率、縮短任務(wù)傳輸時(shí)間等優(yōu)點(diǎn)，但該方式也存在一些挑戰(zhàn)：①移動(dòng)設(shè)備通常無(wú)法確定那些是距離最近的微云，造成通信距離延長(zhǎng)；②由于設(shè)備的移動(dòng)性會(huì)導(dǎo)致它和微云之間的無(wú)線連接不穩(wěn)定，造成通信中斷；③部分微云會(huì)拒絕一些移動(dòng)設(shè)備接入，造成任務(wù)無(wú)法卸載[3]。為解決微云存在的這些問(wèn)題，一種新形式是云代理將該地區(qū)的微云進(jìn)行聯(lián)合為附近的移動(dòng)用戶(hù)提供云計(jì)算服務(wù)。云代理將任務(wù)送入距離最近的微云，當(dāng)移動(dòng)設(shè)備越出網(wǎng)絡(luò)覆蓋范圍時(shí)，云代理能保證將結(jié)果送回。該系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 系統(tǒng)架構(gòu)

近期移動(dòng)云計(jì)算中一個(gè)重要的研究方向是云代理和微云的虛擬機(jī)租用關(guān)系，其中Xie等使用雙向博弈方法采用分布式多維價(jià)格機(jī)制提高微云中虛擬機(jī)利用率，從而提高云代理和微云的收益[4]。Qiu等采用斯坦伯格博弈的方法激勵(lì)微云提供虛擬機(jī)資源給云代理使用[5]。Jin等提出了競(jìng)價(jià)機(jī)制提高微云資源利用效率，并保證競(jìng)價(jià)過(guò)程的不可欺詐性[6]。Liu等將微云的資源分配過(guò)程建模為半馬爾科夫過(guò)程，并使用自適應(yīng)多維價(jià)格方法提高微云的資源利用率[7]。另外一些研究采用博弈的方法或隨機(jī)控制的方法提高雙方收益[8-10]，但這些研究主要考慮在單個(gè)時(shí)間片內(nèi)虛擬機(jī)的租用問(wèn)題，沒(méi)有考慮長(zhǎng)期內(nèi)用戶(hù)任務(wù)提交的隨機(jī)性。

本文將云代理和微云的服務(wù)過(guò)程建模為排隊(duì)過(guò)程，以云代理和微云實(shí)際利潤(rùn)為收益，把微云租賃虛擬機(jī)給云代理的過(guò)程轉(zhuǎn)化為兩者將任務(wù)送入虛擬機(jī)資源池而提高收益的過(guò)程，從隨機(jī)性角度將這一過(guò)程建模為馬爾科夫博弈，提出反向迭代算法實(shí)現(xiàn)博弈的納什均衡。將該方法和云代理租用固定虛擬機(jī)方法進(jìn)行對(duì)比，仿真結(jié)果表明采用馬爾科夫博弈能明顯提高收益。

1 云代理與微云關(guān)系模型

1.1 系統(tǒng)描述

如圖2所示，本文僅考慮云代理租用一個(gè)企業(yè)微云資源情景，微云的資源劃分為類(lèi)型相同的虛擬機(jī)，它們構(gòu)成虛擬機(jī)資源池，云代理和微云中均有一隊(duì)列用于存儲(chǔ)移動(dòng)用戶(hù)和企業(yè)內(nèi)部用戶(hù)提交的任務(wù)。將兩者服務(wù)的過(guò)程劃分為不同的時(shí)間片，單個(gè)時(shí)間片定義為微云完成所有任務(wù)需要的時(shí)間，每個(gè)時(shí)間片內(nèi)兩者將任務(wù)送入虛擬機(jī)資源池執(zhí)行。為保證任務(wù)能夠被快速處理，當(dāng)微云資源池中虛擬機(jī)數(shù)量不能滿(mǎn)足提交的任務(wù)量時(shí)，多余的任務(wù)將被送入其它微云進(jìn)行計(jì)算，并支付相應(yīng)費(fèi)用[11]。

圖2 任務(wù)執(zhí)行過(guò)程

微云中虛擬機(jī)資源池被分為V個(gè)虛擬機(jī)，云代理中任務(wù)隊(duì)列容量為F1，微云隊(duì)列容量為F2。在時(shí)間片t內(nèi)，云代理將b個(gè)任務(wù)放入虛擬機(jī)資源池運(yùn)行，同時(shí)有c1個(gè)任務(wù)進(jìn)入云代理的隊(duì)列。在同一個(gè)時(shí)間片內(nèi)，微云送d個(gè)任務(wù)進(jìn)入虛擬機(jī)資源池，同時(shí)有c2個(gè)任務(wù)到達(dá)微云。因此在時(shí)間片t中，云代理隊(duì)列長(zhǎng)度s1小于隊(duì)列容量，0≤s1≤F1。微云中隊(duì)列長(zhǎng)度s2小于隊(duì)列容量，0≤s2≤F2。

1.2 系統(tǒng)狀態(tài)和動(dòng)作

(1)

(2)

系統(tǒng)以時(shí)間片形式運(yùn)行，云代理和微云每個(gè)時(shí)間片分別送b和d個(gè)任務(wù)進(jìn)入微云虛擬機(jī)資源池執(zhí)行。但送入任務(wù)數(shù)不能高于隊(duì)列中任務(wù)的個(gè)數(shù)，因此：0≤b≤s1, 0≤d≤s2。

將每個(gè)時(shí)間片中用戶(hù)提交給云代理的最大任務(wù)量用c1max表示。內(nèi)部用戶(hù)提交至微云任務(wù)數(shù)的最大值用c2max表示，因此：0≤c1≤c1max, 0≤c2≤c2max。

1.3 系統(tǒng)轉(zhuǎn)移函數(shù)

在不同時(shí)間片內(nèi)，任務(wù)進(jìn)入云代理和微云的數(shù)量會(huì)有一定隨機(jī)性，把該系統(tǒng)任務(wù)到達(dá)的過(guò)程描述為泊松過(guò)程[12-14]，任務(wù)的平均到達(dá)率為λ。因此云代理在狀態(tài)為s的條件下將b個(gè)任務(wù)送入到虛擬機(jī)資源池后隊(duì)列中的數(shù)量的概率為p(c1)，當(dāng)進(jìn)入隊(duì)列的數(shù)量多于隊(duì)列剩余的空間時(shí)，多余的任務(wù)將被丟棄，在此情況下云代理隊(duì)列中任務(wù)數(shù)量的轉(zhuǎn)移函數(shù)為

(3)

在時(shí)間片t中，微云將d個(gè)任務(wù)送入虛擬機(jī)資源池運(yùn)行。同時(shí)內(nèi)部用戶(hù)提交的任務(wù)進(jìn)入隊(duì)列，當(dāng)隊(duì)列滿(mǎn)時(shí)微云將任務(wù)送入其它云中運(yùn)行并支付費(fèi)用，因此微云狀態(tài)變量s2在微云動(dòng)作d下的轉(zhuǎn)移概率為

(4)

在系統(tǒng)中狀態(tài)變量s1和s2相互獨(dú)立，S′表示下一個(gè)時(shí)間片系統(tǒng)的狀態(tài)，因此我們可以得到在云代理動(dòng)作b和微云動(dòng)作d下系統(tǒng)的轉(zhuǎn)移概率

(5)

1.4 云代理和微云的即時(shí)收益函數(shù)

微云對(duì)虛擬機(jī)資源池的管理需有一定成本，本文將其描述成學(xué)習(xí)曲線模型，當(dāng)運(yùn)行的虛擬機(jī)數(shù)量增加時(shí)，管理單位虛擬機(jī)的邊際成本會(huì)以固定因子下降[11]。使用Uo表示管理運(yùn)行的虛擬機(jī)所需成本，管理首個(gè)運(yùn)行的虛擬機(jī)所需成本為co,φ表示微云的學(xué)習(xí)因子。因此管理運(yùn)行虛擬機(jī)所需的總成本是

(6)

(7)

云代理以單個(gè)虛擬機(jī)價(jià)格為p收取用戶(hù)費(fèi)用，且以每個(gè)虛擬機(jī)價(jià)格為q支付給微云。微云內(nèi)部用戶(hù)可免費(fèi)使用虛擬機(jī)資源。每個(gè)時(shí)間片t，云代理送b個(gè)任務(wù)到虛擬機(jī)資源池執(zhí)行，同時(shí)微云也將d個(gè)任務(wù)送入執(zhí)行，當(dāng)d+b>V時(shí)，多余的任務(wù)將別送入其它云執(zhí)行，并需支付相應(yīng)的費(fèi)用，其它云虛擬機(jī)單價(jià)使用r表示。多余的任務(wù)數(shù)量為V-b-d，使用γ1表示云代理送入任務(wù)過(guò)多時(shí)的懲罰因子，γ2表示微云送入任務(wù)過(guò)多時(shí)的懲罰因子，并將它們表示如下

(8)

R1代表在時(shí)間片t內(nèi)云代理的即時(shí)收益，可用如下公式表示

(9)

根據(jù)微云送入任務(wù)的多少和虛擬機(jī)資源池的使用情況，將其收益分為4種類(lèi)型表示

(10)

式(9)、式(10)描述了在每個(gè)時(shí)間片內(nèi)云代理和微云的收益。由于用戶(hù)提交任務(wù)具有隨機(jī)性，在單位時(shí)間內(nèi)的收益不能表示兩者的長(zhǎng)期收益，因此需對(duì)兩者的長(zhǎng)期收益進(jìn)行優(yōu)化。

2 馬爾科夫博弈

云代理和微云分別將任務(wù)送至虛擬機(jī)資源池，由于任務(wù)到達(dá)的隨機(jī)性，各自隊(duì)列中任務(wù)數(shù)量呈現(xiàn)馬爾科夫轉(zhuǎn)移特性，因此可采用馬爾科夫博弈的方法對(duì)兩者關(guān)系進(jìn)行建模。使用W1表示云代理的長(zhǎng)期收益，W2表示微云的長(zhǎng)期收益，β表示博弈的折扣系數(shù)。π(S,b)表示時(shí)間片t內(nèi)系統(tǒng)狀態(tài)為S下云代理采用動(dòng)作b的概率。π(S,d)表示時(shí)間片t內(nèi)系統(tǒng)狀態(tài)為S下微云選擇策略d的概率。因此我們得到長(zhǎng)期的折扣收益為

max(Rj+β∑T(S′|S,b,d)∑π(S′,b′)

subjectto(1)(2)

0≤s1≤F1

0≤s2≤F2

0≤b≤s1

0≤d≤s2

0≤c1≤c1max

0≤c2≤c2max

(11)

3 系統(tǒng)分析和算法設(shè)計(jì)

在系統(tǒng)運(yùn)行的每個(gè)時(shí)間片內(nèi)，云代理和微云根據(jù)隊(duì)列中任務(wù)的個(gè)數(shù)選擇相應(yīng)任務(wù)量送入虛擬機(jī)資源池，因此在每個(gè)時(shí)間片內(nèi)博弈雙方獲得的收益不同，所以在每個(gè)時(shí)間片中系統(tǒng)的收益不同，因此該博弈是變和馬爾科夫博弈。此種類(lèi)型的馬爾科夫博弈具有納什均衡策略[15]。本文根據(jù)此類(lèi)博弈的特性設(shè)計(jì)了反向迭代算法使其達(dá)到ε納什均衡。

反向迭代算法:

輸入：p,q,r,G,F2,F1

輸出：云代理和微云在每一個(gè)狀態(tài)的最優(yōu)策略

Repeat：

(1)在每個(gè)系統(tǒng)狀態(tài)和最優(yōu)動(dòng)作d*下計(jì)算云代理的最優(yōu)動(dòng)作，使用下式

b*(S)= argmax∑T(S′|S,b,d*)

(2)計(jì)算在最優(yōu)動(dòng)作b*下云代理的最優(yōu)的收益

(3)根據(jù)云代理的最優(yōu)動(dòng)作b*在狀態(tài)S下計(jì)算微云的最優(yōu)的動(dòng)作d*，使用如下公式

d*(S)= argmax∑T(S′|S,b*,d)

(4)根據(jù)微云最優(yōu)的動(dòng)作計(jì)算最優(yōu)收益

(5)計(jì)算云代理和微云本次迭代和上次迭代所有狀態(tài)的均值

(7) if ΔV1≤ε,ΔV2≤ε

returnb*,d*

end repart

else

k=k+1

goto 1

end if

4 實(shí)驗(yàn)仿真

首先仿真估計(jì)該反向迭代算法的收斂性，而后比較該方法性能。

在仿真過(guò)程中，設(shè)置折扣因β=0.85，算法的終止條件為ε=1e-4，云代理中任務(wù)的平均到達(dá)率為λ1=12，微云中企業(yè)內(nèi)部用戶(hù)任務(wù)的到達(dá)率為λ2=8，系統(tǒng)中虛擬機(jī)個(gè)數(shù)為20。云代理以單位虛擬機(jī)價(jià)格為0.4 ＄收取移動(dòng)用戶(hù)費(fèi)用，以每個(gè)虛擬機(jī)價(jià)格0.32 ＄租用微云虛擬機(jī)資源池，當(dāng)任務(wù)量溢出時(shí)兩者將多余任務(wù)送入其它云進(jìn)行運(yùn)算并以單價(jià)為0.48 ＄支付給其它微云，首個(gè)運(yùn)行的虛擬機(jī)所需的管理成本為0.06 ＄，首個(gè)空閑虛擬機(jī)所需管理成本為0.03 ＄[12]。

由圖3可看出當(dāng)采用反向迭代算法時(shí)，當(dāng)?shù)?9次時(shí)兩者的收益收斂于ε納什均衡。在經(jīng)過(guò)20次迭代后兩者收益均值趨于穩(wěn)定，結(jié)果表明該采用反向迭代算法能很好達(dá)到博弈的均衡點(diǎn)。

圖3 均值的收斂性

為了和馬爾科夫博弈的方法進(jìn)行對(duì)比，設(shè)計(jì)了云代理租用固定虛擬機(jī)數(shù)量的方法，租用量為微云虛擬機(jī)數(shù)量的40%。圖4為兩種方法的比較。從圖4中可以看出相比租用固定虛擬機(jī)的方法使用馬爾科夫博弈能夠明顯提高云代理和微云的收益，并且系統(tǒng)收益明顯提高。

圖4 馬爾科夫博弈和租用40%虛擬機(jī)數(shù)量的收益比較

將馬爾科夫博弈的方法和微云租用其虛擬機(jī)60%的方法進(jìn)行對(duì)比，結(jié)果如圖5所示。圖中的收益是收斂時(shí)博弈雙方及系統(tǒng)的折扣收益。從中可以明顯看出采用馬爾科夫博弈方法使博弈雙方提高收益的同時(shí)也提高了系統(tǒng)收益。

圖5 馬爾科夫博弈和租用60%虛擬機(jī)數(shù)量的收益比較

5 結(jié)束語(yǔ)

本文根據(jù)在移動(dòng)云計(jì)算中任務(wù)提交的隨機(jī)性，將云代理租用微云虛擬機(jī)的收益獲得問(wèn)題轉(zhuǎn)化為兩者為使各自收益最大化而送任務(wù)到虛擬機(jī)資源池執(zhí)行的過(guò)程，并提出了反向迭代算法達(dá)到了該博弈的納什均衡點(diǎn)，最后仿真結(jié)果表明采用馬爾科夫博弈的方法能明顯提高云代理和微云收益，具有一定使用價(jià)值。但是該研究?jī)H針對(duì)同一類(lèi)微云，對(duì)于不同性質(zhì)的微云和處于不同地區(qū)的微云如何提高其收益是下一步的研究方向。