基于非完全信息博弈的云資源分配模型

苑　迎　王翠榮　王　聰　任婷婷　劉冰玉

1(東北大學信息科學與工程學院　沈陽　110819)2　　　(東北大學秦皇島分校　河北秦皇島　066004)(yuanying1121@gmail.com)

?

基于非完全信息博弈的云資源分配模型

苑迎1,2王翠榮2王聰2任婷婷2劉冰玉2

1(東北大學信息科學與工程學院沈陽110819)2(東北大學秦皇島分校河北秦皇島066004)(yuanying1121@gmail.com)

摘要針對云環境下相互競爭的多租賃市場運營模式，以提高資源供求雙方利益及資源能效為目標，提出了一種基于非完全信息博弈的云資源分配模型.首先利用隱Markov理論根據服務提供商(service provider, SP)的歷史資源需求情況預測其當前出價，以預測值為基礎構建動態博弈定價模型，激勵服務提供商選擇符合整體利益的最優購買出價策略，從而實現利益最大化；然后設計了支持多服務提供商、多種資源同時分配，以分類資源單位價格進行分配的資源分配模型，保證了基礎設施提供商(infrastructure provider, INP)的收益最優.仿真實驗表明：在博弈定價模型中，預測價格與實際交易價格相近且交易價格低于實際估值，能夠保障服務提供商的利益；基于不同種類資源單價的分配模型能夠增加基礎設施提供商的收益.

關鍵詞云計算；虛擬化；資源分配；非完全信息博弈；隱馬爾可夫預測

近年來，云計算技術的興起為整個IT行業帶來了劃時代意義的變革，使得人們可以直接通過網絡獲得服務和計算資源.云計算帶來的最大好處就是IT資源的按需分配，這將極大提高資源利用率并降低IT行業的運營成本.這樣靈活使用資源的前提就是虛擬化技術的應用，包括CPU、內存、存儲、網絡等一系列IT硬件資源的虛擬化[1].在網絡虛擬化環境下，傳統的互聯網服務提供商(Internet service provider, ISP)被劃分為基礎設施提供商(infrastructure provider, INP)和服務提供商(service provider, SP)[2].

因此，虛擬資源的高效、合理租賃問題是云計算研究的關鍵問題，在硬件虛擬化技術成熟后開始受到越來越多的關注.現有的虛擬資源管理研究內容主要集中在虛擬資源的部署和租賃交易方式2個方面.前者以硬件資源利用率為目標，研究如何在有限的硬件資源上盡可能滿足更多的用戶，為用戶直接進行資源分配并創建虛擬網絡，屬于虛擬網絡映射問題(virtual network embedding, VNE)[3]；后者更加宏觀研究云市場競爭的多租賃環境下INP和SP之間的供求關系，以最大化社會整體利益為目標，并保證公平、高效的競爭環境.目前已有的研究方法通常借鑒經濟學領域內的拍賣理論模擬云環境下的資源租賃市場，激勵參與者選擇合理的成交價格以獲得符合最優整體利益的均衡策略.但是云環境下的資源是多樣化的，包括處理器、存儲、帶寬等，這樣包含多維資源的拍賣特別是組合拍賣的凈勝標問題通常屬于NP-Hard問題.另外，拍賣中采用的統一資源定價方案簡單地將用戶出價除以全部資源需求量以獲得平均單位資源價格，這樣的機制在激勵效果和公平性上存在問題.

本文提出了1種基于非完全信息博弈的云資源分配模型.考慮到云市場多租賃環境下服務提供商之間存在競爭關系，他們不可能公開自己的實際出價，因此利用隱Markov模型，根據服務提供商的歷史資源需求情況預測其當前出價.根據預測的出價構建動態博弈定價模型以激勵服務提供商選擇符合整體利益的最優購買出價策略，從而實現利益最大化.然后設計支持多服務提供商、多種資源同時分配的分配算法，根據不同種類資源分別出價進行資源的分配以最大化基礎設施提供商的利益.

1相關工作

資源分配問題是當前Internet面臨的重要挑戰，特別是在云計算這樣的大規模分布式環境下，資源的合理、高效分配問題在近2年成為研究者關注的重點問題[4].因此，當前云資源特別是作為云基礎設施的數據中心資源的利用率低下問題，一直是研究界和業界致力于解決的重點問題.

云資源分配問題的研究可劃分為2個方向：1)以最大化資源利用率為目標，根據用戶具體需求(每個虛擬網絡所需要的CPU、帶寬、存儲等資源)的描述，將基礎設施提供商的硬件資源盡可能多地分配以提高資源利用率[5-6]，這樣的解決方式是集中式的，需要完整全局信息才能實現.2)以最大化收益為目標，這部分的研究內容細分為最大化整體收益和最大化基礎設施提供商收益等不同目標.研究方法通常借鑒經濟學領域的拍賣和博弈理論構建模型.第1個方向屬于虛擬網絡映射問題，第2個方向是從宏觀角度考慮的資源分配問題.考慮到云市場的運營機制，在服務提供商和基礎設施提供商之間的分配應更側重經濟利益，而服務提供商及其用戶之間的分配應更側重于效率.

Fig. 1　Structure of the cloud resources allocation model based on uncompleted information game.圖1　非完全信息博弈的云資源分配模型結構圖

文獻[7]提出了一種基于拍賣的公平資源分配框架，但是該框架是以單個服務提供商的最小花費為目標的，應用到多服務提供商競爭的環境下不能獲得全局最優的資源分配策略.文獻[8]引入博弈論解決網絡資源分配，該分配方案中未考慮基礎設施提供商提供資源的有限性問題且僅考慮了帶寬資源并未考慮計算資源的分配.文獻[9]基于隨機整數規劃設計了云資源優化分配模型，將整體分配問題拆分成可以并行解決的若干子問題以提高求解效率，模型考慮了價格不確定性問題，用樣本均值逼近方法進行解決，但由于采用集中式算法，該模型在用戶規模較大時效率不高.文獻[10]針對多基礎設施提供商和多服務提供商競爭環境中虛擬網絡資源分配的特點，從服務管理的角度基于組合雙向拍賣理論提出了多個基礎設施提供商和多服務提供商競爭的虛擬網資源分配模型，但是在傳統組合拍賣中，根據均價進行排序的方式在不同種資源價格差異較大時無法獲得最優方案.文獻[4]基于反向拍賣設計了3種云資源交易模型：C-DSIC，C-BIC和C-OPT.其中，C-DSIC也是基于Vickrey拍賣的，具有分配效率和個人理性，但不是預算平衡的；C-BIC不是個人理性的，但是具有分配效率和預算平衡且購買開銷也小于D-DSIC；C-OPT模型在凈勝標確定和支付規則上不同于前兩者，而是采用了虛擬動態定價機制，這點在云資源分配中非常重要，它使得C-OPT更適用于云資源分配時用戶需求分布不同的情況，更符合實際情況.在傳統資源分配方式中，由資源提供者定價的機制只關注資源提供者的利益，忽略了用戶的收益[11]，而動態定價可以提高用戶收益，加速資源提供者競爭的健康性并且可以提高云資源利用率[12]，因此在資源分配模型中加入動態定價機制是很有必要的.

上述研究存在4點不足： 1)部分研究僅解決單個服務提供商向基礎設施服務商申請資源時如何創建公平的交易環境并得到較高的經濟收益和效用，在用戶規模過大時每次僅與一個服務提供商的交易模式效率過低；2)部分算法只針對單種資源進行分配，云環境下的資源種類更加多樣化，并且服務提供商對于每種資源的估價、用量存在差異，能夠同時分配多種資源的算法才更符合實際需求；3)已有的能夠支持多服務提供商資源分配技術的研究大都基于組合拍賣，致力于提高市場競爭公平性和最大化收益等，但忽略了服務提供商自身客觀存在的非合作的行為，另外，組合拍賣中根據不同種資源均價排序分配的方式在價格差異較大時缺乏公平性；4)在資源分配中使用動態定價機制有助于構建更合理、高效的交易機制，但采用集中式的定價算法效率不高，需設計更加高效的定價機制.

2基于非完全信息博弈定價模型

2.1基于HMM的服務提供商單位資源出價預測

如圖2所示，隱Markov模型是在Markov的基礎上發展起來的，它的狀態不能直接觀察到，但能通過觀測向量序列觀察到，每個觀測向量都是通過某些概率密度分布表現為各種狀態，每一個觀測向量是由1個具有相應概率密度分布的狀態序列產生，因此隱Markov模型是1個雙重隨機過程：系統狀態變化的隨機過程和由狀態決定輸出的隨機過程.當系統中表層事件可能是由低層事件引發而產生時，隱Markov模型能夠有效地解決這類問題，因此本文將HMM理論應用到SP單位資源出價的預測上，利用已知的任意SP的歷史資源請求序列(觀測值)，預測下一輪分配中該SP對于單位資源的出價(隱含狀態).

Fig. 2　Structure of HMM model.圖2　隱Markov模型結構

SP根據觀測到其他競爭者資源請求的記錄以及下一時刻的資源請求數量vt+1，預測出其最有可能的出價,即首先計算條件概率p(Xt+1=qj|Ot+1=vt+1).

由貝葉斯公式可知：

p(Xt+1=qj|Ot+1=vt+1)=

(1)

(2)

令p{Xt+1=qj,Ot+1=vt+1}=αt+1(qj,vt+1)，則

(3)

由已知：

p(Xt+1=qj|Xt=qi)=aqiqj，

p(Ot+1=vt+1|Xt=qi)=bqivt+1，

代入式(3):

(4)

根據式(4)可以計算出αt+1(qj,vt+1)，將結果代入到式(1)可以得到SP所有可能的出價的概率，選取出概率最大的qj進行競價.

目前，尚未有研究將隱Markov模型應用于云資源分配，而隱Markov模型在語音識別、基因關聯分析和基因識別、文字識別及股市預測等領域取得了重大成功.因此，本文將其應用到對SP出價的預測上，進而在預測價格的基礎上構建非完全信息動態博弈定價模型，根據當前市場狀態迅速、靈活地確定價格使其達到利益的最優化，獲得納什均衡解.

2.2服務提供商博弈定價模型

當SP采用HMM獲得其他SP所請求的CPU、帶寬和存儲資源的預測價格后，本文采用動態博弈定價的方法獲得其自身穩定均衡的出價.在動態博弈定價中SP采用文獻[14]提出的方法確定投標策略，即極大化Cobb-Douglas效用函數：

(5)

(6)

(7)

(8)

(9)

將式(7)(8)(9)代入式(6)得任意SP的期望收益即效用函數,化簡得：

(10)

定理1. 當

時，各服務提供商的期望收益在合理的策略集上可以達到最優，系統存在納什均衡解.可進一步放寬約束：如果SP對于商品出價的策略集合為大于1的有限正整數集合時，系統存在納什均衡解.

D=E=F=0.

根據文獻[15]關于3元函數極值的充分條件：當

(11)

時，式(6)存在極大值.進一步放寬約束，令SP對于所請求資源出價的策略集合為大于1的有限正整數集合時，系統此時存在納什均衡且其均衡解落于給定的SP策略集合中，是合理可行的均衡策略，因此式(6)給出的SP之間的博弈存在納什均衡解.

證畢.

定理2. 本文提出的基于預測定價的博弈系統是激勵相容且個人理性的.

證明.

1) 激勵相容性.在SP個人理性出價且其個人利益不受到損失的同時，使得其他SP的收益也有所增加，各SP出價能夠達到一種均衡出價狀態s*.

2) 個人理性.每個SP的出價行為也要符合個人理性約束，即效用都為正.

對于獲得資源量為0的SP來說(在本文的分配算法中，資源緊張時有可能有些SP無法獲得資源)，其收益可看作是0.對于參與交易(即分得資源)的SP來說，討論式(6)的可能取值范圍，以CPU資源為例，其實際估值與交易價格之差為

因為對于交易價格來說，實際估值和預測價格不可能為負值，顯然有

證畢.

由上面的推導和證明可以看出使用HMM預測價格為最終的博弈提供了合理的理論依據；非完全信息博弈理論也使本模型可以形成穩定的納什均衡解，且本文提出的基于預測定價的博弈系統是激勵相容且個人理性的最優化系統收益.

3基于各類資源分別定價的云資源分配模型

本節主要介紹圖1下半部分的云資源分配模型，首先舉例說明傳統云資源分配模型中，基于各類資源均價的凈勝標確定手段[10]缺乏公平性，然后對資源分配問題進行建模，進而給出基于貪心算法的資源分配算法.

3.1傳統云資源分配凈勝標確定問題分析

以1個簡單的例子來分析組合資源分配過程中以各類資源的平均價格作為SP排序依據進行資源分配所產生的錯誤激勵機制.設請求資源包括CPU、帶寬和存儲3類資源，2個SP申請資源分配的數據如下：

SP1所請求的組合資源包為o1=1,2,4，組合資源包的單價為x1=15,3,5，由o1和x1得到組合資源包的平均價格為

SP2所請求的組合資源包為o2=2,1,4，組合資源包的單價為x2=12,2,4，由o2和x2得到組合資源包的平均價格為

很明顯，SP1各類資源的單價都比SP2高，從經濟學角度分析，SP1應比SP2更具有競爭力；但是由于SP1的平均價格要比SP2的平均價格低，這樣在傳統的組合資源分配中SP1就排在了SP2的后面.由此可見，傳統云資源分配模型中基于各類資源均價的凈勝標確定手段缺乏公平性，將導致INP收益無法達到最優，其激勵效果有可提高的空間.

3.2云資源分配模型及求解算法

本文考慮的資源分配環境是1個INP可以同時滿足多個SP需求的情況，SP為1組資源的組合與INP進行交易.將云資源分配模型形式化為1個四元組A=K,X,O,C，其中K為S個SP的集合，K={k1,k2,…,kS}；X={x1,x2,…,xS}為SP所提交的價格集合，?xi，xi=表示服務提供商SPi對CPU、帶寬和存儲資源的出價；O={o1,o2,…,oS}為SP所請求的各類資源的組合需求，?oi,oi=表示服務提供商SPi對各類資源的需求量；C=cCPU,cBW,cStorage為INP所擁有的CPU、帶寬和存儲的資源.以最大化INP收益為目標，資源分配模型可以表示為

(12)

其中，δi∈{0，1}.

尤其需要注意的是：為了保證更好的公平性，應當在資源分配的過程中采用各類資源分別定價、統一判斷凈勝標的機制，以提高激勵效果；另外，在動態定價之后的資源分配步驟中也需要著重考慮效率問題，因此INP應一次性將可分配的資源分配給獲勝的若干SP，而不是為單獨的資源進行多次分配.

考慮到上述2點，本文利用貪心算法對云資源分配模型進行求解，設計了CVSA-UPV算法.該算法以分類單位資源價格向量的長度作為貪心選擇標準，按分類單位資源價格向量的長度對SP進行排序，并采用貪心算法分配資源以達到最大化INP收益的目的.這樣有效地避免了傳統的組合資源分配過程中以各類資源的平均價格為SP進行排序所產生的定價誤差和形成錯誤的激勵機制且資源分配結束后系統收益最大.下面對CVSA-UPV算法進行詳細介紹.

算法1. CVSA-UPV資源分配算法.

輸入：SP定價策略及資源需求、INP最低價格；

輸出：資源分配方案.

①S個SP將通過非合作動態博弈定價策略獲得的自身對組合資源包中各類資源的競拍出價xi=和自身的資源需求oi=提交給拍賣代理；

② INP將各類資源交易的最低價格提交給拍賣代理；

③ 拍賣代理根據INP提交的最低價格確定參與資源分配的SP；

⑥ 從排列好的SP列表中第1個SP開始，計算其各類資源需求量，如果均滿足則分配資源；

⑦ 當出現1個組合包內的3類資源需求不能同時被滿足時，從列表中選取下一個SP進行分配，直到INP中的1類資源數為0或者SP列表被完全遍歷.

4性能分析與評估

模擬實驗首先對資源分配算法中隱Markov預測的可行性以及適用性進行了分析,然后分別對本文提出的CVSA-UPV算法和傳統的各類資源不分別定價的分配算法進行比較.實驗在Matlab仿真環境下實現，思路是通過編寫仿真程序模擬拍賣過程，通過拍賣樣本數據對HMM模型進行訓練從而獲得收斂的模型；然后在后續模擬拍賣過程中測試本文提出的算法在資源估價準確度、基礎設施提供商收益及資源單價定價方案等方面的性能.

實驗 1. 首先對SP的實際估值、交易價格與預測價格進行比較.本文假設SP請求的組合資源包括CPU、帶寬和存儲3類資源，價格的單位采用vrc(virtual resource currency)表示，CPU的單位資源價格在2～20 vrc之間，帶寬的單位資源價格在8～40 vrc之間，存儲的單位資源價格在1～10 vrc之間.本文使用式(13)～(15)來描述SP對基礎設施供應商資源的實際估值[16]：

(13)

(14)

(15)

Fig. 3　Comparison of actual price, auction price andpredicted price by HMM for CPU, bandwidth and storage.圖3　CPU、帶寬和存儲資源的實際估值、交易價格與預測價格的比較

從圖3可以看出，在本文提出的非合作博弈定價模型中，SP的交易價格與其實際估值趨勢相同，在實際估值的下方波動且波動幅度較小.根據收益計算公式，顯然每個SP的收益非負，因此該博弈模型是符合個人理性的并能反映市場實際情況.另外，通過隱Markov模型獲得的預測價格圍繞著交易價格波動且幅度較小，充分說明隱Markov預測模型的有效性且具有較好的適應性.

實驗2. CPU、帶寬和存儲的各個參數設置與實驗1相同，實驗中INP擁有各類資源數量分別設定為10，20，30，40，50，60，70，80，90，100，SP的個數S=15，30，50.比較了本文提出的CVSA-UPV算法與傳統組合拍賣中根據均值進行分配2種方式的收益情況，結果如圖4所示.從圖4可以看到當SP個數相同時，基于CVSA-UPV算法比傳統組合拍賣中根據均值進行分配的算法CVSA-MV的收益要高；隨著SP數量的增多，2種分配算法的收益都逐步增加，說明算法符合實際市場規律；隨著INP所擁有的資源數的增加，基于CVSA-UPV算法比傳統組合拍賣中根據均值進行分配的算法的收益增加得明顯，這說明本文的算法有較好的激勵機制，使得INP的單位資源效用增大.

實驗3. CPU、帶寬和存儲的各個參數除單位資源價格外設置與實驗1相同，實驗中共有30個SP，進行20次實驗.圖5中的實驗結果為所有SP各類單位資源價格方差的均值取0，0.66，43.8，91.02，203.58時，本文提出的CVSA-UPV算法與傳統組合拍賣中根據均值分配的算法CVSA-MV對INP單位資源的效用進行比較.實驗中假定CPU和存儲的價格保持在6～10之間，逐步提高帶寬的價格.當各類資源的單價均相同分別取8，9，10時，分配資源的單價的平均值為第1簇柱狀圖.從圖5可以清楚地看出采用2種算法得到的各類資源單價是相同的.當各類資源的單價相差很小且均勻分布在8～10時，分配各類資源的單價的平均值為第2簇柱狀圖.2種算法得到的各類資源單價的差值較小.隨著各類單位資源價格方差的增大，采用CVSA-UPV算法獲得的帶寬的單價明顯高于采用傳統組合拍賣中根據均值進行分配的算法，且2種算法獲得單價的差值逐步增大.從實驗數據可以看出，當INP的資源有限且各類資源單價相差很大時，采用CVSA-UPV能有效提高INP單位資源的價格，使其獲得較高的收益，能夠使出價高的SP更具有競爭力，因此更符合市場的競爭規律.

Fig. 4　Profit of infrastructure provider.圖4　基礎設施提供商的收益

Fig. 5　Comparison of the unit price of different kinds ofresources.圖5　基礎設施提供商銷售各類資源單價的比較

5結束語

本文針對云環境下相互競爭的多租賃市場運營模式，提出了1種基于非完全信息博弈的云資源分配模型.考慮到云市場多租賃環境下SP之間存在競爭關系，他們不可能完全信息共享，因此將隱Markov模型應用到對SP出價的預測上，根據SP的歷史資源需求情況預測其當前出價.在預測價格的基礎上構建非完全信息動態博弈定價模型，根據當前市場狀態迅速、靈活地確定價格使其達到利益的最優化，獲得納什均衡解，從而實現利益最大化.設計了支持多SP、多種資源同時分配，以分類單位資源價格進行分配的資源分配模型，保證了INP的收益最優.仿真實驗表明：在博弈定價模型中，預測價格與實際交易價格相近且交易價格低于實際估值，能夠保障SP的利益；基于各類資源分別定價的分配模型能夠增加INP的收益.

參考文獻

[1]Zhang Sheng, Qian Zhuzhong, Wu Jie, et al. Virtual network embedding with opportunistic resource sharing[J]. Parallel and Distributed Systems, 2014, 25(3): 816-827

[2]Rahman M R, Aib I, Boutaba R. Survivable virtual network embedding[G] //LNCS 6091: Proc of the 9th Int Networking Conf on IFIP TC 6. Berlin: Springer, 2010: 40-52

[3]Yu Minlan, Yi Yung, Rexford J, et al. Rethinking virtual network embedding: Substrate support for path splitting and migration[J]. ACM SIGCOMM Computer Communication Review, 2008, 38(2): 17-29

[4]Prasad A S, Rao S. A mechanism design approach to resource procurement in cloud computing[J]. IEEE Trans on Computers, 2014, 63(1): 17-30

[5]Ghazar T, Samaan N. Pricing utility-based virtual networks[J]. IEEE Trans on Network and Service Management, 2013, 10(2): 119-132

[6]Rahman M R, Boutaba R. SVNE: Survivable virtual network embedding algorithms for network virtualization[J]. IEEE Trans on Network and Service Management, 2013, 10(2): 105-118

[7]Zaheer F E, Jin Xiao, Boutaba R. Multi-provider service negotiation and contracting in network virtualization[C] //Proc of Network Operations and Management Symp (NOMS). Piscataway, NJ: IEEE, 2011: 471-478

[8]Trinh T, Esaki H, Aswakul C. Quality of service using careful overbooking for optimal virtual network resource allocation[C] //Proc of the 8th IEEE Int Conf on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON). Piscataway, NJ: IEEE, 2011: 296-299

[9]Chaisiri S, Lee B S, Niyato D. Optimization of resource provisioning cost in cloud computing[J]. IEEE Trans on Services Computing, 2012, 5(2): 164-177

[10]Zhang Shunli, Qiu Xuesong, Cheng Dongdong, et al. A virtual network resource allocation mechanism for network virtualization[J]. Journal of Beijing University of Posts and Telecommunications, 2011, 34(6): 24-27(張順利, 邱雪松, 陳東東, 等. 網絡虛擬化環境中虛擬網資源分配機制[J]. 北京郵電大學學報, 2011, 34(6):24-27)

[11]Ridder F, Bona A. Four risky issues when contracting for cloud services, 1543314[R/OL]. 2011[2015-01-12]. http://www. gartner. com/id

[12]Mihailescu M, Teo Y M. Dynamic resource pricing on federated clouds[C] //Proc of the 10th IEEE/ACM Int Conf on Cluster, Cloud and Grid Computing (CCGrid). Piscataway, NJ: IEEE, 2010: 513-517

[13]Rabiner L. A tutorial on hidden Markov models and selected applications in speech recognition[J]. Proceedings of the IEEE, 1989, 77(2): 257-286

[14]Liu Shulin, Wang Mingxi. Sealed-bid auctions based on Cobb-Douglas utility function[J]. Economics Letters, 2010, 107(1): 1-3

[15]Meng Yiping. Sufficient condition for extreme value of three variables function[J]. Jounal of Jiangsu of Science and Technologe: Natural Science Edition, 2010, 24(5): 511-513 (in Chinese)(孟義平. 三元函數極值的一個充分條件[J]. 江蘇科技大學學報: 自然科學版, 2010, 24(5): 511-513)

[16]Li Mingchu, Xu Lei, Sun Weifeng. Grid resource allocation model based on incomplete information game[J]. Journal of Software, 2012, 23(2): 428-438 (in Chinese)(李明楚, 許雷, 孫偉峰. 基于非完全信息博弈的網格資源分配模型[J]. 軟件學報, 2012, 23(2): 428-438)

Yuan Ying, born in 1981. PhD, lecturer in the School of Computer Center, Northeastern University at Qinhuangdao. Member of China Computer Federation. Her main research interests include virtual network embedding, virtual resource allocation in cloud computing.

Wang Cuirong, born in 1963. PhD, professor in the School of Computer and Communication Engineering, Northeastern University at Qinhuangdao. Member of China Computer Federation. Her main research interests include routing protocol, network security and sensor networks (wcr@mail.neuq.edu.cn).

Wang Cong, born in 1981. PhD. Lecturer in the School of Computer and Communication Engineering, Northeastern University at Qinhuangdao. Member of China Computer Federation. His main research interests include virtual network embedding, resource allocation in data center (congw1981@163.com).

Ren Tingting, born in 1984. PhD candidate. Lecturer in the School of Computer and Communication Engineering, Northeastern University at Qinhuangdao. Her main research interests include investment efficiency of cultural industry and the governance effect of non-efficiency investment (358568169@163.com).

Liu Bingyu, born in 1978. PhD candidate. Lecturer in the School of Economies and Business, Northeastern University at Qinhuangdao. Member of China Computer Federation. Her main research interests include data mining and community discovery (liuby78@163.com).

An Uncompleted Information Game Based Resources Allocation Model for Cloud Computing

Yuan Ying1,2, Wang Cuirong2, Wang Cong2, Ren Tingting2, and Liu Bingyu2

1(CollegeofInformationScience&Engineering,NortheasternUniversity,Shenyang110819)2(NortheasternUniversityatQinhuangdao,Qinhuangdao,Hebei066004)

AbstractConsidering the competing characteristics under multi-tenant environment in cloud computing and aiming to improve the profit of both the resource supply and demand sides, an uncompleted information game based cloud resource allocation model is proposed. Firstly, a hidden Markov model (HMM) is introduced to predict the current bid of service providers based on the historical resource demand. Then a game model for dynamical pricing is established base on the predicted bid value. It can motivate service providers to choose the optimal bidding strategy in accordance with overall interests and so as to achieve maximum benefits. Finally, a resource allocation model on the basis of unit prices of different types of resources is put forward to guarantee optimal gains for infrastructure provider (INP). The allocation model can support synchronous allocation for both multi service providers and various resources. Simulation results show that, in the pricing game model, the predicted price is close to the actual transaction price which is lower than the actual valuation, so it can guarantee the profit of service providers; the resource allocation model can simultaneously increase infrastructure provider’s revenue.

Key wordscloud computing; virtualization; resource allocation; uncompleted information game; hidden Markov prediction

收稿日期：2015-01-22；修回日期：2015-05-21

基金項目：國家自然科學基金項目(61300195,61402094)；河北省自然科學基金項目(F2014501078, F2016501079)；遼寧省教育廳科學研究一般項目(L2013099);河北省科技計劃項目(15210146)；秦皇島市科技計劃項目(201401A028)；東北大學秦皇島分校校內基金項目(XNB201607)

中圖法分類號TP393.02

This work was supported by the National Natural Science Foundation of China (61300195,61402094), the Natural Science Foundation of Heibei Province of China (F2014501078,F2016501079), the General Project of Liaoning Province Department of Education Science Research (L2013099), the Technology Planning Project of Hebei Province (15210146), the Science and Technology Research Project of Qinhuangdao (201401A0289), and the School Foundation of Northeastern University at Qinhuangdao (XNB201607).