張鋒輝，符茂勝，何富貴

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

0 引 言

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

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

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

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

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

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

1.1 系統(tǒng)描述

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

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

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

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

(1)

(2)

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

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

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

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

(3)

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

(4)

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

(5)

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

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

(6)

(7)

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

(8)

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

(9)

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

(10)

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

2 馬爾科夫博弈

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

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è)計

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

反向迭代算法:

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

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

Repeat：

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

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

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

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

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

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

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

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

returnb*,d*

end repart

else

k=k+1

goto 1

end if

4 實驗仿真

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

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

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

圖3 均值的收斂性

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

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

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

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

5 結(jié)束語

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