王翠娥,顧永跟,吳小紅,陶 杰

(1.杭州電子科技大學(xué)計(jì)算機(jī)應(yīng)用研究所 杭州 310018；2.湖州師范學(xué)院信息與工程學(xué)院 湖州 313000）

1 引言

云計(jì)算SLA是云服務(wù)質(zhì)量的重要保證[1]。針對(duì)云計(jì)算SLA中的響應(yīng)時(shí)間，將在充分保障QoS[2]的前提下，最小化用戶(hù)任務(wù)的完成時(shí)間定義為響應(yīng)時(shí)間。云計(jì)算雙市場(chǎng)模型中將云資源提供商和云服務(wù)提供商[3]分別作為資源代理和用戶(hù)代理，在雙市場(chǎng)中對(duì)資源需求和服務(wù)需求進(jìn)行協(xié)商和匹配。在用戶(hù)某項(xiàng)工作的預(yù)算確定以及違例賠償明確的情況下，云服務(wù)提供商會(huì)考慮如何優(yōu)化服務(wù)的響應(yīng)時(shí)間，尋求一組能在最短時(shí)間內(nèi)完成任務(wù)的資源組合。

機(jī)制設(shè)計(jì)是博弈規(guī)則設(shè)計(jì)的主要方法，即使博弈中的代理都是自利的，也可以通過(guò)機(jī)制設(shè)計(jì)獲得一個(gè)最佳結(jié)果[4,5]。本文假設(shè)云資源提供商是自治﹑理性﹑智能的，設(shè)計(jì)的機(jī)制中，不論其他資源提供商的報(bào)價(jià)如何，真實(shí)報(bào)價(jià)是其占優(yōu)策略。對(duì)于一個(gè)機(jī)制設(shè)計(jì)問(wèn)題，需要考慮兩個(gè)方面：一個(gè)是機(jī)制中每個(gè)代理人的目標(biāo)，另一個(gè)是機(jī)制的目標(biāo)[6]。在本文所設(shè)計(jì)的機(jī)制中，云服務(wù)提供商在SLA條款中預(yù)算值和違例賠償值一定的情形下，尋求一種用戶(hù)完成工作時(shí)間最短的方法。在各云資源提供商都追逐最大效用的情況下，該機(jī)制為云服務(wù)提供商尋求用戶(hù)工作的最短響應(yīng)時(shí)間創(chuàng)建了一個(gè)真實(shí)的資源成本顯示環(huán)境。那么如何在理性﹑智能﹑自治的云資源提供商之間制定一種交互的協(xié)議，以促成各云資源提供商顯示資源的真實(shí)成本，正是本文設(shè)計(jì)的機(jī)制要解決的問(wèn)題。

2 機(jī)制設(shè)計(jì)相關(guān)概念

為了后文敘述方便，將機(jī)制設(shè)計(jì)理論中相關(guān)符號(hào)和幾個(gè)重要概念列舉如下。

θ：參與用戶(hù)任務(wù)競(jìng)爭(zhēng)的云資源提供商的一種類(lèi)型組合，θ=θ1×…×θn。

θ-i：云資源提供商i除外的其他參與用戶(hù)任務(wù)競(jìng)爭(zhēng)的資源提供商的一種類(lèi)型組合，θ-i=θ1×…×θi-1×θi+1×…×θn。

Θ：參與用戶(hù)任務(wù)競(jìng)爭(zhēng)的云資源提供商的所有類(lèi)型組合，Θ=Θ1×…×Θn。

Θ-i：云資源提供商除外的其他參與用戶(hù)任務(wù)競(jìng)爭(zhēng)的資源提供商的所有類(lèi)型組合，Θ-i=Θ1×…×Θi-1×Θi+1×…×Θn。

定義1 （社會(huì)選擇函數(shù)在占優(yōu)策略上的實(shí)現(xiàn)）如果一個(gè)機(jī)制M=((Si)i∈N,g(·))所導(dǎo)出的貝葉斯博弈 Γb有一個(gè)弱占優(yōu)策略均衡，且使得那么稱(chēng)該機(jī)制在占優(yōu)策略均衡上滿(mǎn)足社會(huì)選擇函數(shù)f(·)。

定義2 （占優(yōu)策略激勵(lì)兼容）如果一個(gè)直接顯示機(jī)制D=((Θi)i∈N,f(·))所導(dǎo)出的貝葉斯博弈有一個(gè)弱占優(yōu)策略均衡，其中N，那么社會(huì)選擇函數(shù)f:Θ1×…×Θn→X是占優(yōu)策略激勵(lì)兼容的。社會(huì)選擇函數(shù)激勵(lì)兼容的充分必要條件為ui(f(θi,θ-i),，坌i∈N，坌θi∈Θi，坌θ-i∈Θ-i即無(wú)論其他代理人報(bào)價(jià)如何，代理人i報(bào)的真實(shí)類(lèi)型θi總是其最優(yōu)反應(yīng)。

3 不完全信息資源成本報(bào)價(jià)模型

對(duì)于云計(jì)算任務(wù)分配，本文構(gòu)建了一個(gè)不完全信息的非合作博弈模型。以博弈論的觀點(diǎn)，假設(shè)云資源提供商是自治﹑理性﹑智能的。云資源提供商的自治性是指其策略不受云用戶(hù)和其他資源提供商的影響和控制；理性是指其所選的策略是為追求自己的效用最大化；智能性是指云資源提供商知道博弈規(guī)則，并且會(huì)在選擇策略時(shí)充分考慮其他資源提供商的可能行為。

在云計(jì)算中，一個(gè)用戶(hù)提交的工作可以被分為多個(gè)任務(wù)，這些任務(wù)可以在云數(shù)據(jù)中心獨(dú)立并行地執(zhí)行。假設(shè)用戶(hù)的某一項(xiàng)工作被劃分成m個(gè)相同的任務(wù)，數(shù)據(jù)中心現(xiàn)有Y個(gè)云資源提供商，n為參與用戶(hù)任務(wù)競(jìng)爭(zhēng)的云資源提供商。云資源提供商i有一個(gè)任務(wù)處理速率μi，μi由資源提供商代理的服務(wù)器處理速率決定，可以視為常數(shù)，ti=1/μi表示單個(gè)任務(wù)的處理時(shí)間。此外，每個(gè)云資源提供商有一個(gè)可接受的任務(wù)數(shù)qi及處理單個(gè)任務(wù)的資源成本ci，ci為資源提供商i的私有信息，θi(ci,qi)為云資源提供商的真實(shí)類(lèi)型，θ^i(c^i,qi)為云資源提供商i所報(bào)的類(lèi)型。每個(gè)理性的云資源提供商都追逐各自效用的最大值，其效用記為ui(k(·)，p1(·),…,pn(·),θi)，價(jià)值函數(shù)vi(k(·),θi)=-ki(θ)×ci，則：

其中，k(·)和pi(θ)是機(jī)制設(shè)計(jì)的分配函數(shù)和支付函數(shù)。云服務(wù)提供商的目標(biāo)是在預(yù)算值和違例賠償值一定的情形下，為用戶(hù)在SLA條款中尋找min(maxti)。

4 一種優(yōu)化響應(yīng)時(shí)間的機(jī)制設(shè)計(jì)

在理性參與人的假設(shè)下，Neumann和Morgenstern提出并證明了期望效用最大化理論[7]。理性的資源提供商都追求效用最大化，因此對(duì)于響應(yīng)時(shí)間的優(yōu)化問(wèn)題，云服務(wù)提供商必須考慮各資源提供商對(duì)所提供資源報(bào)價(jià)的真實(shí)性，即希望在所有資源提供商提供真實(shí)資源成本的前提下，尋找任務(wù)響應(yīng)時(shí)間最短的云資源提供商。本著這一目標(biāo)，作為機(jī)制設(shè)計(jì)者的云服務(wù)提供商必須設(shè)計(jì)該機(jī)制下的支付函數(shù)和分配函數(shù)，使得參與該機(jī)制的資源提供商都愿意報(bào)出真實(shí)的資源成本。

為了更準(zhǔn)確地分析機(jī)制設(shè)計(jì)問(wèn)題，需要定義一個(gè)機(jī)制設(shè)計(jì)環(huán)境，下面介紹本文機(jī)制設(shè)計(jì)的準(zhǔn)線性環(huán)境[8]，在準(zhǔn)線性環(huán)境下，可以找到一個(gè)激勵(lì)兼容但非獨(dú)裁的社會(huì)選擇函數(shù)f(·)。

定義3 (機(jī)制設(shè)計(jì)的準(zhǔn)線性環(huán)境)代理集N={1,2,…,n}；可選結(jié)果集0}；代理i具有類(lèi)型 θi∈Θi，Θi定義為參與用戶(hù)任務(wù)競(jìng)爭(zhēng)的云資源提供商i的類(lèi)型空間，類(lèi)型是與決策制定有關(guān)的所有私有信息；社會(huì)選擇函數(shù)f(θ)=(k(θ),p1(θ),…,pn(θ))；效用函數(shù)ui(x,θ)=ui((k(·),p1(·),…,pn(·))，θi）=vi(k,θi)+pi。

其中，分配向量k(θ)=(k1(θ),k2(θ),…,kn(θ))，ki(θ)定義為云服務(wù)提供商對(duì)云資源提供商i(i=1,2,…,n)的分配函數(shù)；支付向量p(θ)=((p1(θ),p2(θ),…,pn(θ)),pi(θ)定義為云服務(wù)提供商對(duì)云資源提供商i的支付函數(shù)。

4.1 用戶(hù)任務(wù)分配機(jī)制設(shè)計(jì)

4.1.1 分配函數(shù)的設(shè)計(jì)

一個(gè)有效的用戶(hù)任務(wù)分配方案k(θ)=(k1(θ),k2(θ),…,kn(θ))必須滿(mǎn)足以下條件。

·非負(fù)性：ki(·)≥0,i=1,2,…,n；

·ki(·)≤qi,i=1,2,…,n。

因此本文機(jī)制的分配函數(shù)設(shè)計(jì)如下：

其中，[i]表示所報(bào)的處理任務(wù)相關(guān)資源成本升序排列處于第i位的云資源提供商，]被定義為具有下列特點(diǎn)的云資源提供商：

4.1.2 支付函數(shù)的設(shè)計(jì)

4.2 機(jī)制的性能分析

命題1 該機(jī)制滿(mǎn)足分配有效性。

證明 首先驗(yàn)證該機(jī)制驅(qū)使下的云資源提供商i的占優(yōu)策略（報(bào)告其真實(shí)資源成本ci），分以下兩種情形。

綜合上述兩種情形，可知云資源提供商i在效用驅(qū)使下，令其報(bào)價(jià)i等于真實(shí)資源成本ci是其占優(yōu)策略。

有了上述結(jié)論，就很容易驗(yàn)證本文設(shè)計(jì)的分配規(guī)則滿(mǎn)足代理（云資源提供商）效用函數(shù)最大化，即對(duì)于被分配任務(wù)的云資源提供商，其整體資源成本是最小的。

已知價(jià)值函數(shù)vi(k(·),θi)=-ki(θ)×ci，在上述分析的基礎(chǔ)上可將其記為vi(k(·),θi)=ki(θ)×i，將其代入k*(θ)證畢。

命題2 該機(jī)制滿(mǎn)足弱預(yù)算均衡性。

命題3 該機(jī)制滿(mǎn)足個(gè)體理性。

個(gè)體理性也被稱(chēng)作自愿參與性，社會(huì)選擇函數(shù)的個(gè)體理性暗含如果一個(gè)機(jī)制實(shí)現(xiàn)了該社會(huì)選擇函數(shù)，則參與該機(jī)制的每個(gè)代理都將有非負(fù)的效用，一般假設(shè)不參與機(jī)制時(shí)的效用i(θi)=0，即 ui(f(θi,θ-i),θi)≥i(θi),?(θi,θ-i)∈Θ。

如果云資源提供商i在該機(jī)制下競(jìng)標(biāo)到了任務(wù)，則完成用戶(hù)任務(wù)的總成本降低，因此在i參與的情況下它的效用ui(f(θ),θi)>0；如果云資源提供商 i沒(méi)有競(jìng)標(biāo)到任務(wù)或者自動(dòng)退出該機(jī)制，那么

由以上分析可知，云資源提供商參與該機(jī)制的效用總是不小于退出該機(jī)制的效用，具備自愿參與該機(jī)制的意向，于是該機(jī)制的個(gè)體理性得證。

命題4 該機(jī)制是占優(yōu)策略激勵(lì)兼容的。

下面采用反證法加強(qiáng)驗(yàn)證結(jié)論的正確性。如果一個(gè)機(jī)制是占優(yōu)策略激勵(lì)兼容的，那么定有下式成立：

如果本文設(shè)計(jì)的機(jī)制不是占優(yōu)策略激勵(lì)兼容的，那么至少存在一個(gè)代理i使得式（5）不成立，即對(duì)于代理i,云資源提供商效用函數(shù)該機(jī)制的支付函數(shù)與 θi無(wú)關(guān)，于是可以得到下式：

5 預(yù)算約束下響應(yīng)時(shí)間最短的資源提供商最優(yōu)組合算法

在各資源提供商真實(shí)顯示資源成本的前提下，本節(jié)提出了一種預(yù)算約束下響應(yīng)時(shí)間最短的資源提供商最優(yōu)組合算法，描述如下：

·各云資源提供商對(duì)用戶(hù)提交的工作標(biāo)示出任務(wù)的處理時(shí)間和可處理的任務(wù)數(shù)，記為（ti,qi）；

·云服務(wù)提供商接收云資源提供商所報(bào)的信息（ti,qi）；

·云服務(wù)提供商對(duì)云資源提供商所報(bào)信息的任務(wù)處理時(shí)間ti進(jìn)行升序排列；

·按任務(wù)處理時(shí)間ti的升序，從第[1]個(gè)云資源提供商到第]個(gè)云資源提供商依次選出m個(gè)任務(wù)數(shù)，滿(mǎn)足并把相應(yīng)的資源提供商添加進(jìn)列表L，同時(shí)令

·e>E時(shí)，從列表中移除最大 （或剩余信息中最大）ti的相關(guān)信息；繼續(xù)尋找第個(gè)云資源提供商，并添加進(jìn)列表L，最后選出列表中的資源提供商。這組云資源提供商正是滿(mǎn)足預(yù)算約束下任務(wù)響應(yīng)時(shí)間最短的最優(yōu)組合。

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

本文提出了一種基于機(jī)制設(shè)計(jì)理論的云計(jì)算SLA響應(yīng)時(shí)間優(yōu)化方案，設(shè)計(jì)了一種DSIC機(jī)制。假設(shè)云資源提供商是自治﹑理性﹑智能的，那么在這個(gè)機(jī)制中不論其他資源提供商的報(bào)價(jià)如何，真實(shí)報(bào)價(jià)是其占優(yōu)策略。該機(jī)制能夠保證各云資源提供商顯示真實(shí)的資源成本，因此為云用戶(hù)尋找到一組滿(mǎn)足用戶(hù)預(yù)算約束下響應(yīng)時(shí)間最短的資源提供商是可能的，這也是本文機(jī)制設(shè)計(jì)的目標(biāo)。本文的云資源報(bào)價(jià)機(jī)制為云計(jì)算SLA的設(shè)計(jì)提供了一個(gè)有利環(huán)境，在資源成本真實(shí)顯示的環(huán)境下云服務(wù)提供商能優(yōu)化用戶(hù)服務(wù)需求的響應(yīng)時(shí)間，同時(shí)在一定程度上提升了用戶(hù)對(duì)云資源提供商的信任度。后續(xù)筆者將在雙市場(chǎng)云模型中對(duì)云計(jì)算SLA中的其他參數(shù)的優(yōu)化（如服務(wù)花費(fèi)、違例賠償?shù)葯C(jī)制）設(shè)計(jì)問(wèn)題作進(jìn)一步探討。此外，對(duì)于參與人多維私有類(lèi)型信息的情況，如何設(shè)計(jì)既有較低計(jì)算復(fù)雜性又有激勵(lì)兼容性的機(jī)制也有待進(jìn)一步研究。

1 Armbrust M,Fox A,Grith R,et al.Above the Clouds:Aberkeley View of Cloud Computing.Technical Report UCB/EECS-2009-28,EECS Department,University of California,Berkeley,2009

2 Buyya R,Yeo C S,Venugopal S,et al.Cloud computing and emerging IT platforms:vision,hype,and reality for delivering computing asthe 5th utility.Future Generation Computer Systems,Elsevier Science,2009,25(6):599～616

3 Yonggen Gu,XiaohongWu,Jie Tao.Building an open cloud dual-market for cloud computing service.Proceedings of the 2nd International Symposium on ComputerNetwork and Multimedia Technology (CNMT’10),IEEE,2010:691～694

4 Nisan N,Ronen A.Algorithmic mechanism design.Games and Economic Behavior,2001,35(1):166～196

5 Nisan N,Roughgarden T,Tardos E,et al.Algorithmic Game Theory.Cambridge University Press,New York,2007

6 Garg D,Narahari Y,Gujar S.Foundations of mechanism design:a tutorial-part 1:key concepts and classical results.Sadhana—Indian Academy Proceedings in Engineering Sciences,2008,33(2):83～130

7 Neumann J V,Morgenstern O.Theory of Games and Economic Behavior.Princeton University Press,1944

8 Narahari Y,Garg D,Narayanam R,et al.Game Theoretic Problems in NetworkEconomicsandMechanismDesignSolutions.Springer,2009