基于馬爾科夫博弈的云代理與微云收益優化

張鋒輝，符茂勝，何富貴

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

0 引 言

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

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

圖1 系統架構

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

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

1 云代理與微云關系模型

1.1 系統描述

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

圖2 任務執行過程

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

1.2 系統狀態和動作

(1)

(2)

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

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

1.3 系統轉移函數

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

(3)

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

(4)

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

(5)

1.4 云代理和微云的即時收益函數

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

(6)

(7)

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

(8)

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

(9)

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

(10)

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

2 馬爾科夫博弈

云代理和微云分別將任務送至虛擬機資源池，由于任務到達的隨機性，各自隊列中任務數量呈現馬爾科夫轉移特性，因此可采用馬爾科夫博弈的方法對兩者關系進行建模。使用W1表示云代理的長期收益，W2表示微云的長期收益，β表示博弈的折扣系數。π(S,b)表示時間片t內系統狀態為S下云代理采用動作b的概率。π(S,d)表示時間片t內系統狀態為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 系統分析和算法設計

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

反向迭代算法:

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

輸出：云代理和微云在每一個狀態的最優策略

Repeat：

(1)在每個系統狀態和最優動作d*下計算云代理的最優動作，使用下式

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

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

(3)根據云代理的最優動作b*在狀態S下計算微云的最優的動作d*，使用如下公式

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

(4)根據微云最優的動作計算最優收益

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

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

returnb*,d*

end repart

else

k=k+1

goto 1

end if

4 實驗仿真

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

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

由圖3可看出當采用反向迭代算法時，當迭代到59次時兩者的收益收斂于ε納什均衡。在經過20次迭代后兩者收益均值趨于穩定，結果表明該采用反向迭代算法能很好達到博弈的均衡點。

圖3 均值的收斂性

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

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

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

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

5 結束語

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