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

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

1(東北大學(xué)信息科學(xué)與工程學(xué)院　沈陽　110819)2　　　(東北大學(xué)秦皇島分?！『颖鼻鼗蕧u　066004)(yuanying1121@gmail.com)

?

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

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

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

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

關(guān)鍵詞云計(jì)算；虛擬化；資源分配；非完全信息博弈；隱馬爾可夫預(yù)測(cè)

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

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

本文提出了1種基于非完全信息博弈的云資源分配模型.考慮到云市場(chǎng)多租賃環(huán)境下服務(wù)提供商之間存在競(jìng)爭(zhēng)關(guān)系，他們不可能公開自己的實(shí)際出價(jià)，因此利用隱Markov模型，根據(jù)服務(wù)提供商的歷史資源需求情況預(yù)測(cè)其當(dāng)前出價(jià).根據(jù)預(yù)測(cè)的出價(jià)構(gòu)建動(dòng)態(tài)博弈定價(jià)模型以激勵(lì)服務(wù)提供商選擇符合整體利益的最優(yōu)購(gòu)買出價(jià)策略，從而實(shí)現(xiàn)利益最大化.然后設(shè)計(jì)支持多服務(wù)提供商、多種資源同時(shí)分配的分配算法，根據(jù)不同種類資源分別出價(jià)進(jìn)行資源的分配以最大化基礎(chǔ)設(shè)施提供商的利益.

1相關(guān)工作

資源分配問題是當(dāng)前Internet面臨的重要挑戰(zhàn)，特別是在云計(jì)算這樣的大規(guī)模分布式環(huán)境下，資源的合理、高效分配問題在近2年成為研究者關(guān)注的重點(diǎn)問題[4].因此，當(dāng)前云資源特別是作為云基礎(chǔ)設(shè)施的數(shù)據(jù)中心資源的利用率低下問題，一直是研究界和業(yè)界致力于解決的重點(diǎn)問題.

云資源分配問題的研究可劃分為2個(gè)方向：1)以最大化資源利用率為目標(biāo)，根據(jù)用戶具體需求(每個(gè)虛擬網(wǎng)絡(luò)所需要的CPU、帶寬、存儲(chǔ)等資源)的描述，將基礎(chǔ)設(shè)施提供商的硬件資源盡可能多地分配以提高資源利用率[5-6]，這樣的解決方式是集中式的，需要完整全局信息才能實(shí)現(xiàn).2)以最大化收益為目標(biāo)，這部分的研究?jī)?nèi)容細(xì)分為最大化整體收益和最大化基礎(chǔ)設(shè)施提供商收益等不同目標(biāo).研究方法通常借鑒經(jīng)濟(jì)學(xué)領(lǐng)域的拍賣和博弈理論構(gòu)建模型.第1個(gè)方向?qū)儆谔摂M網(wǎng)絡(luò)映射問題，第2個(gè)方向是從宏觀角度考慮的資源分配問題.考慮到云市場(chǎng)的運(yùn)營(yíng)機(jī)制，在服務(wù)提供商和基礎(chǔ)設(shè)施提供商之間的分配應(yīng)更側(cè)重經(jīng)濟(jì)利益，而服務(wù)提供商及其用戶之間的分配應(yīng)更側(cè)重于效率.

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

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

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

2基于非完全信息博弈定價(jià)模型

2.1基于HMM的服務(wù)提供商單位資源出價(jià)預(yù)測(cè)

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

Fig. 2　Structure of HMM model.圖2　隱Markov模型結(jié)構(gòu)

SP根據(jù)觀測(cè)到其他競(jìng)爭(zhēng)者資源請(qǐng)求的記錄以及下一時(shí)刻的資源請(qǐng)求數(shù)量vt+1，預(yù)測(cè)出其最有可能的出價(jià),即首先計(jì)算條件概率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)

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

目前，尚未有研究將隱Markov模型應(yīng)用于云資源分配，而隱Markov模型在語音識(shí)別、基因關(guān)聯(lián)分析和基因識(shí)別、文字識(shí)別及股市預(yù)測(cè)等領(lǐng)域取得了重大成功.因此，本文將其應(yīng)用到對(duì)SP出價(jià)的預(yù)測(cè)上，進(jìn)而在預(yù)測(cè)價(jià)格的基礎(chǔ)上構(gòu)建非完全信息動(dòng)態(tài)博弈定價(jià)模型，根據(jù)當(dāng)前市場(chǎng)狀態(tài)迅速、靈活地確定價(jià)格使其達(dá)到利益的最優(yōu)化，獲得納什均衡解.

2.2服務(wù)提供商博弈定價(jià)模型

當(dāng)SP采用HMM獲得其他SP所請(qǐng)求的CPU、帶寬和存儲(chǔ)資源的預(yù)測(cè)價(jià)格后，本文采用動(dòng)態(tài)博弈定價(jià)的方法獲得其自身穩(wěn)定均衡的出價(jià).在動(dòng)態(tài)博弈定價(jià)中SP采用文獻(xiàn)[14]提出的方法確定投標(biāo)策略，即極大化Cobb-Douglas效用函數(shù)：

(5)

(6)

(7)

(8)

(9)

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

(10)

定理1. 當(dāng)

時(shí)，各服務(wù)提供商的期望收益在合理的策略集上可以達(dá)到最優(yōu)，系統(tǒng)存在納什均衡解.可進(jìn)一步放寬約束：如果SP對(duì)于商品出價(jià)的策略集合為大于1的有限正整數(shù)集合時(shí)，系統(tǒng)存在納什均衡解.

D=E=F=0.

根據(jù)文獻(xiàn)[15]關(guān)于3元函數(shù)極值的充分條件：當(dāng)

(11)

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

證畢.

定理2. 本文提出的基于預(yù)測(cè)定價(jià)的博弈系統(tǒng)是激勵(lì)相容且個(gè)人理性的.

證明.

1) 激勵(lì)相容性.在SP個(gè)人理性出價(jià)且其個(gè)人利益不受到損失的同時(shí)，使得其他SP的收益也有所增加，各SP出價(jià)能夠達(dá)到一種均衡出價(jià)狀態(tài)s*.

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

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

因?yàn)閷?duì)于交易價(jià)格來說，實(shí)際估值和預(yù)測(cè)價(jià)格不可能為負(fù)值，顯然有

證畢.

由上面的推導(dǎo)和證明可以看出使用HMM預(yù)測(cè)價(jià)格為最終的博弈提供了合理的理論依據(jù)；非完全信息博弈理論也使本模型可以形成穩(wěn)定的納什均衡解，且本文提出的基于預(yù)測(cè)定價(jià)的博弈系統(tǒng)是激勵(lì)相容且個(gè)人理性的最優(yōu)化系統(tǒng)收益.

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

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

3.1傳統(tǒng)云資源分配凈勝標(biāo)確定問題分析

以1個(gè)簡(jiǎn)單的例子來分析組合資源分配過程中以各類資源的平均價(jià)格作為SP排序依據(jù)進(jìn)行資源分配所產(chǎn)生的錯(cuò)誤激勵(lì)機(jī)制.設(shè)請(qǐng)求資源包括CPU、帶寬和存儲(chǔ)3類資源，2個(gè)SP申請(qǐng)資源分配的數(shù)據(jù)如下：

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

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

很明顯，SP1各類資源的單價(jià)都比SP2高，從經(jīng)濟(jì)學(xué)角度分析，SP1應(yīng)比SP2更具有競(jìng)爭(zhēng)力；但是由于SP1的平均價(jià)格要比SP2的平均價(jià)格低，這樣在傳統(tǒng)的組合資源分配中SP1就排在了SP2的后面.由此可見，傳統(tǒng)云資源分配模型中基于各類資源均價(jià)的凈勝標(biāo)確定手段缺乏公平性，將導(dǎo)致INP收益無法達(dá)到最優(yōu)，其激勵(lì)效果有可提高的空間.

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

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

(12)

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

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

考慮到上述2點(diǎn)，本文利用貪心算法對(duì)云資源分配模型進(jìn)行求解，設(shè)計(jì)了CVSA-UPV算法.該算法以分類單位資源價(jià)格向量的長(zhǎng)度作為貪心選擇標(biāo)準(zhǔn)，按分類單位資源價(jià)格向量的長(zhǎng)度對(duì)SP進(jìn)行排序，并采用貪心算法分配資源以達(dá)到最大化INP收益的目的.這樣有效地避免了傳統(tǒng)的組合資源分配過程中以各類資源的平均價(jià)格為SP進(jìn)行排序所產(chǎn)生的定價(jià)誤差和形成錯(cuò)誤的激勵(lì)機(jī)制且資源分配結(jié)束后系統(tǒng)收益最大.下面對(duì)CVSA-UPV算法進(jìn)行詳細(xì)介紹.

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

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

輸出：資源分配方案.

①S個(gè)SP將通過非合作動(dòng)態(tài)博弈定價(jià)策略獲得的自身對(duì)組合資源包中各類資源的競(jìng)拍出價(jià)xi=和自身的資源需求oi=提交給拍賣代理；

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

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

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

⑦ 當(dāng)出現(xiàn)1個(gè)組合包內(nèi)的3類資源需求不能同時(shí)被滿足時(shí)，從列表中選取下一個(gè)SP進(jìn)行分配，直到INP中的1類資源數(shù)為0或者SP列表被完全遍歷.

4性能分析與評(píng)估

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

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

(13)

(14)

(15)

Fig. 3　Comparison of actual price, auction price andpredicted price by HMM for CPU, bandwidth and storage.圖3　CPU、帶寬和存儲(chǔ)資源的實(shí)際估值、交易價(jià)格與預(yù)測(cè)價(jià)格的比較

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

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

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

Fig. 4　Profit of infrastructure provider.圖4　基礎(chǔ)設(shè)施提供商的收益

Fig. 5　Comparison of the unit price of different kinds ofresources.圖5　基礎(chǔ)設(shè)施提供商銷售各類資源單價(jià)的比較

5結(jié)束語

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

參考文獻(xiàn)

[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(張順利, 邱雪松, 陳東東, 等. 網(wǎng)絡(luò)虛擬化環(huán)境中虛擬網(wǎng)資源分配機(jī)制[J]. 北京郵電大學(xué)學(xué)報(bào), 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)(孟義平. 三元函數(shù)極值的一個(gè)充分條件[J]. 江蘇科技大學(xué)學(xué)報(bào): 自然科學(xué)版, 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)(李明楚, 許雷, 孫偉峰. 基于非完全信息博弈的網(wǎng)格資源分配模型[J]. 軟件學(xué)報(bào), 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

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

中圖法分類號(hào)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).