孫英華 ，吳哲輝 ，郭振波 ，顧衛(wèi)東

SUN Yinghua1，2,WU Zhehui2,GUO Zhenbo1,GU Weidong3

1.青島大學(xué) 信息工程學(xué)院，山東 青島 266071

2.山東科技大學(xué) 信息科學(xué)與工程學(xué)院，山東 青島 266510

3.山東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，濟(jì)南 250101

1.College of Information Engineering,Qingdao University,Qingdao,Shandong 266071,China

2.College of Information Science and Engineering,Shandong University of Science and Technology,Qingdao,Shandong 266510,China

3.Shandong Provincial Key Laboratory of Computer Network,Jinan 250101,China

1 研究概述

目前網(wǎng)絡(luò)上擁有超大量的各種各樣的計(jì)算資源，同時(shí)有數(shù)不清的各種潛在的計(jì)算需求。如何有效和高效地共享計(jì)算資源，一方面提高全球現(xiàn)有IT資源的利用率，另一方面為人們提供更方便更廉價(jià)的計(jì)算服務(wù)，是一個(gè)具有重大價(jià)值的研究課題。近年來(lái)，隨著網(wǎng)格、云等新型分布式平臺(tái)和SOA技術(shù)的發(fā)展，一些基于網(wǎng)格（Grid）、云（Cloud）和社會(huì)網(wǎng)絡(luò)（Social Network）的計(jì)算資源共享模型相繼被提出，其相應(yīng)的資源管理、調(diào)度和共享機(jī)制得到了持續(xù)的研究。

1.1 三種計(jì)算資源共享模型

本文根據(jù)共享特征和實(shí)現(xiàn)機(jī)制的不同將已有的資源共享模型分為三類：合作共享型、公用計(jì)算型和市場(chǎng)交易型。

合作共享模型（Corporation Sharing Model）通常構(gòu)建在網(wǎng)格或者社會(huì)網(wǎng)絡(luò)的平臺(tái)上，通過(guò)無(wú)縫地集成多個(gè)自愿加入的廣域資源合作解決問(wèn)題，實(shí)現(xiàn)網(wǎng)格內(nèi)或社會(huì)網(wǎng)絡(luò)內(nèi)計(jì)算資源、存儲(chǔ)資源、通信資源、信息資源的全面共享，如DEISA、DutchGrid、EGEE、Co-op[1]等。

公用計(jì)算模型（Utility Computing Model）構(gòu)建在云計(jì)算平臺(tái)，通過(guò)計(jì)算資源虛擬化技術(shù)和SOA技術(shù)，以IaaS（Infrastructure as a Service）、PaaS（Platform as a Service）、SaaS（Soft as a Service）甚至是 XaaS（Everything as a Service）的服務(wù)形式，在線提供包括硬件、軟件和基礎(chǔ)設(shè)施在內(nèi)的虛擬計(jì)算資源，按照使用時(shí)間或流量收費(fèi)，如 Amazon EC2、Rackspace、Tsunamic、FlexiScale等。

市場(chǎng)交易共享模型（Market Trading Model）將計(jì)算能力、存儲(chǔ)空間、數(shù)據(jù)資源、軟件服務(wù)等計(jì)算資源看成是商品，在網(wǎng)格、云甚至是云間構(gòu)建市場(chǎng)平臺(tái)，資源所有者和資源需求者直接或通過(guò)代理在市場(chǎng)中進(jìn)行交易，以市場(chǎng)經(jīng)濟(jì)規(guī)律調(diào)控供需和價(jià)格，如Nimrod-G、Tycoon、Popcorn、GridEcon等。

1.2 待解決的問(wèn)題和相關(guān)的研究

目前以Google Apps、Amazon Ec2、FlexiScale、Salesforces.com為代表的云服務(wù)尚存在一些明顯的問(wèn)題：（1）云服務(wù)商提供的資源和服務(wù)各成體系，云和云之間是孤立的，沒(méi)有共享渠道，且大多數(shù)云服務(wù)商采用“預(yù)付費(fèi)”的結(jié)算方式，從而導(dǎo)致“廠商鎖定問(wèn)題（Vendor Lock-in Problem）”[2]。（2）目前云市場(chǎng)有壟斷傾向，服務(wù)質(zhì)量和價(jià)格由云服務(wù)商單方?jīng)Q定，SLA（Service Level Agreement）內(nèi)容也是云服務(wù)商單方確定，主要用于告知服務(wù)方式和免責(zé)條款，用戶無(wú)法有效保障自身權(quán)益。（3）云間技術(shù)還不夠完善，中小企業(yè)的云資源和云服務(wù)尚需借助大企業(yè)的云平臺(tái)發(fā)布，限制了中小企業(yè)SMEs（Small and Medium Enterprises）的競(jìng)爭(zhēng)力，用戶很難得到優(yōu)質(zhì)、低價(jià)、個(gè)性化的服務(wù)。

混合云（Hybrid Cloud）[3]的概念是2011年提出的，最近兩年以FP7-ICT為代表的一些項(xiàng)目正在研究異構(gòu)云接口技術(shù)，如Morfeo 4CaaSt[4]旨在開(kāi)發(fā)PaaS的云服務(wù)和應(yīng)用程序框架，支持Internet規(guī)模多層應(yīng)用的優(yōu)化和彈性托管；mOSAIC[2]的目的是建立一個(gè)開(kāi)源的云應(yīng)用程序編程接口（API）和一個(gè)面向SMEs的應(yīng)用開(kāi)發(fā)平臺(tái)。VMware公司的 Cloud Foundry[5]、RedHat的 Openshift[6]提供開(kāi)源的PaaS函數(shù)，為不同架構(gòu)的私有云或公共云提供彈性開(kāi)發(fā)環(huán)境。Andreas Menychtas[7]提出了一種新的云市場(chǎng)，一方面提供一個(gè)集成的開(kāi)發(fā)和銷售XaaS產(chǎn)品的平臺(tái)，另一方面為客戶提供一個(gè)一站式購(gòu)買(mǎi)計(jì)算服務(wù)的解決方案。以上研究將為混合云平臺(tái)的搭建提供技術(shù)支持，建立容納不同云提供商的統(tǒng)一的云計(jì)算編程接口和面向多種云的應(yīng)用開(kāi)發(fā)平臺(tái)，解決異構(gòu)云之間的互操作、應(yīng)用的可移植以及自治服務(wù)的自動(dòng)發(fā)現(xiàn)、部署等問(wèn)題。

在解決了資源層、應(yīng)用層技術(shù)支持且市場(chǎng)平臺(tái)建立起來(lái)之后，如何幫助用戶以滿意的價(jià)格獲得滿意的資源或服務(wù)，是要解決的問(wèn)題之一。一種做法是研究選擇策略[8]，在已有的商品中為用戶擇優(yōu)選擇，但這種方法仍然只適用于商品市場(chǎng)（定價(jià)市場(chǎng)），用戶不能參與價(jià)格制定。另一種做法是將供需組織到一起進(jìn)行雙向拍賣，市場(chǎng)轉(zhuǎn)化成一個(gè)買(mǎi)賣雙方平等、定價(jià)由買(mǎi)賣方共同決定的雙向市場(chǎng)。

文獻(xiàn)[9]介紹Tycoon市場(chǎng)按照出價(jià)情況對(duì)資源按比例分配的拍賣機(jī)制；Spawn[10]采用單向Viekery拍賣模型管理異構(gòu)工作站網(wǎng)絡(luò)的資源；Popcorn[11]基于Web采用單向和雙向拍賣模型實(shí)現(xiàn)Internet上的資源在線分配。JaWS[12]基于雙向拍賣模型，買(mǎi)方與賣方提交定單到匹配器，定單可以隨時(shí)更新，匹配器一旦匹配到買(mǎi)方與賣方定單，交易即可完成。文獻(xiàn)[13]提出了一種連續(xù)的雙向拍賣定價(jià)機(jī)制CDA，對(duì)CPU資源采用統(tǒng)一拍賣。文獻(xiàn)[14]提出了一種基于雙向拍賣的適應(yīng)性云計(jì)算資源分配機(jī)制。文獻(xiàn)[15]提出了一種基于多單元連續(xù)雙向拍賣機(jī)制MDA（Multi-unit Double Auction）和相應(yīng)的定價(jià)策略及資源分配方法。文獻(xiàn)[16]基于CDA提出更新的UCDA，允許供應(yīng)商根據(jù)資源負(fù)載自行定價(jià)，而用戶根據(jù)作業(yè)時(shí)限自行確定投標(biāo)價(jià)格。

以上提及的方法，文獻(xiàn)[9-13]適用網(wǎng)格市場(chǎng)CPU計(jì)算周期的拍賣，文獻(xiàn)[14-16]適用云資源拍賣。以上文獻(xiàn)的共同特點(diǎn)是將拍賣的資源默認(rèn)為同一質(zhì)量，拍賣順序由雙方報(bào)價(jià)決定。然而，未來(lái)的混合云市場(chǎng)中計(jì)算資源來(lái)自不同的服務(wù)商，因地域、成本、服務(wù)質(zhì)量等因素的差異，其價(jià)格必然不同，研究非同質(zhì)云資源的交易機(jī)制很有實(shí)用價(jià)值和應(yīng)用前景。

1.3 本文研究重點(diǎn)

本文認(rèn)為，當(dāng)前計(jì)算資源共享模型的發(fā)展趨勢(shì)是：（1）底層架構(gòu)將突破一個(gè)計(jì)算網(wǎng)格或者一家公司提供的資源云和服務(wù)云，建立在混合云環(huán)境之上。（2）自由交易的市場(chǎng)模式將會(huì)代替網(wǎng)格中的統(tǒng)一調(diào)度模式和云中的商品市場(chǎng)模式，計(jì)算資源的價(jià)格將由市場(chǎng)經(jīng)濟(jì)規(guī)則和供需平衡決定。（3）在混合云平臺(tái)上，SMEs將獲得更多機(jī)會(huì)，與大型IT供應(yīng)商競(jìng)爭(zhēng)，為用戶提供更多的個(gè)性化的服務(wù)。（4）供應(yīng)和需求之間的匹配過(guò)程，將會(huì)受到除價(jià)格之外的多種因素的影響，包括供給/需求的數(shù)量、資源的質(zhì)量等級(jí)、賣方的個(gè)性化需求、用戶的信用反饋等。

鑒于此，提出一種基于混合云環(huán)境的計(jì)算資源市場(chǎng)模型 HCRM（Hybrid Cloud Resource Market），重點(diǎn)研究其交易管理機(jī)制，本文主要研究：（1）HCRM的功能架構(gòu)和參與角色；（2）HCRM的交易管理模式；（3）HCRM的供需質(zhì)量模型；（4）質(zhì)量感知的雙向拍賣匹配算法。

圖1 HCRM的分層結(jié)構(gòu)

2 混合云資源市場(chǎng)的交易管理機(jī)制

混合云資源市場(chǎng)HCRM是運(yùn)行在異構(gòu)的混合云環(huán)境、以服務(wù)方式為用戶提供計(jì)算資源交易的虛擬市場(chǎng)。HCRM的參與者分為買(mǎi)方、賣方、市場(chǎng)管理者和交易代理者。買(mǎi)方是資源請(qǐng)求者，包括個(gè)人用戶、SMEs，自行或者通過(guò)買(mǎi)方代理提出購(gòu)買(mǎi)需求；賣方是資源擁有者，包括個(gè)人用戶、SMEs和大型云服務(wù)提供商，自行或者通過(guò)賣方代理提交資源供應(yīng)。市場(chǎng)管理者為用戶提供市場(chǎng)平臺(tái)、用戶管理、交易管理、報(bào)價(jià)基準(zhǔn)參考、交易賬戶管理和轉(zhuǎn)帳服務(wù)，并負(fù)責(zé)監(jiān)管市場(chǎng)運(yùn)營(yíng)秩序，接受用戶反饋。

2.1 HCRM的功能架構(gòu)

HCRM的組成有四層：物理資源層，資源管理層，市場(chǎng)管理層和用戶接口層，如圖1所示。

（1）物理資源層是底層的各種網(wǎng)絡(luò)資源，包括計(jì)算資源、存儲(chǔ)資源、數(shù)據(jù)資源、網(wǎng)絡(luò)應(yīng)用、遠(yuǎn)程設(shè)備、網(wǎng)絡(luò)互連設(shè)備、云和云間服務(wù)設(shè)施等。

（2）資源管理層是支持網(wǎng)格和云結(jié)構(gòu)的中間件層，主要負(fù)責(zé)資源描述、資源組織、資源查找、資源預(yù)留、資源部署和資源監(jiān)控等工作。

（3）市場(chǎng)管理層提供用戶管理、交易管理、交易支持服務(wù)和安全管理，主要負(fù)責(zé)管理控制市場(chǎng)活動(dòng)，約束市場(chǎng)交易行為。

用戶管理負(fù)責(zé)用戶身份的管理認(rèn)證、用戶賬戶信息和信用信息的許可認(rèn)證，負(fù)責(zé)對(duì)買(mǎi)賣方進(jìn)行身份登記、用戶等級(jí)權(quán)限檢查和對(duì)用戶請(qǐng)求的管理。

交易管理負(fù)責(zé)供應(yīng)管理、需求管理、供給和需求匹配，并為用戶提供定價(jià)參考，負(fù)責(zé)提供多種交易模型以供用戶選擇；根據(jù)市場(chǎng)供需變化對(duì)商品價(jià)格進(jìn)行調(diào)整，提供市場(chǎng)指導(dǎo)價(jià)；記錄歷史交易信息，并用SLA條款約束交易行為。

交易支持服務(wù)通常提供工作流管理、信用管理、網(wǎng)上轉(zhuǎn)賬和風(fēng)險(xiǎn)代理服務(wù)，負(fù)責(zé)用戶信譽(yù)更新、管理用戶資金賬戶、計(jì)費(fèi)管理并監(jiān)管買(mǎi)賣雙方資金流向，輔助約束交易行為。

安全管理是通過(guò)監(jiān)測(cè)市場(chǎng)交易活動(dòng)的商品和用戶的安全服務(wù)負(fù)責(zé)，負(fù)責(zé)保障計(jì)算資源市場(chǎng)的整體安全，包括身份認(rèn)證、訪問(wèn)授權(quán)和安全審計(jì)等。

（4）用戶接口層是SOA建構(gòu)層，為用戶提供服務(wù)的注冊(cè)、登錄、身份驗(yàn)證和各種應(yīng)用模塊的服務(wù)入口。通過(guò)門(mén)戶網(wǎng)站，用戶可以無(wú)縫地使用符合權(quán)限的服務(wù)，服務(wù)提供者可以發(fā)布新的服務(wù)。

本文主要研究市場(chǎng)管理層的交易管理機(jī)制。

2.2 HCRM的交易模型

一個(gè)市場(chǎng)要正常運(yùn)行，必須要有一套規(guī)范的交易機(jī)制，如何定價(jià)、如何進(jìn)行供需分配是市場(chǎng)機(jī)制必須解答的，有效的交易機(jī)制能夠鼓勵(lì)更多的用戶參與計(jì)算資源交易并直接影響到整個(gè)市場(chǎng)的效率。計(jì)算資源市場(chǎng)可采用的交易模型大致有三種：（1）商品市場(chǎng)。由云供應(yīng)商單方規(guī)定并公布資源規(guī)格和價(jià)格，用戶從中選擇購(gòu)買(mǎi)。（2）談判市場(chǎng)。買(mǎi)家和賣家或其代理機(jī)構(gòu)面對(duì)面進(jìn)行價(jià)格談判，雙方共同決定成交價(jià)格。（3）拍賣市場(chǎng)。買(mǎi)方和賣方各自報(bào)價(jià)，由拍賣機(jī)制決定供需匹配結(jié)果和成交價(jià)格。

三者各自的局限性是：商品市場(chǎng)由賣方單方面決定價(jià)格；談判市場(chǎng)時(shí)間上開(kāi)銷較大；拍賣市場(chǎng)需有大量的供應(yīng)和需求保證足夠的市場(chǎng)流動(dòng)性。

圖2 市場(chǎng)管理層的交易管理模型

HCRM包括大量的供應(yīng)和需求，供應(yīng)和需求的添加、刪除是動(dòng)態(tài)的且非常頻繁，每個(gè)買(mǎi)方或賣方根據(jù)自己的預(yù)算價(jià)格或成本價(jià)格獨(dú)立報(bào)價(jià)，買(mǎi)賣方都想盡可能提高自己的經(jīng)濟(jì)效益，且作為商品的計(jì)算資源時(shí)效性顯著，因此HCRM適合采用雙向拍賣的交易模式。

圖2描述了HCRM市場(chǎng)管理層的交易管理組件，由價(jià)格管理器、交易管理器、交易監(jiān)管器、支付管理器、反饋管理器和數(shù)據(jù)庫(kù)組成，各個(gè)組件之間的信息流如圖2所示。

考慮到HCRM中的資源來(lái)自不同賣方，質(zhì)量差別較大，用戶對(duì)資源質(zhì)量的需求也不同，并且買(mǎi)賣雙方都接受不同質(zhì)量不同定價(jià)，本文以資源類型篩選為前提，以質(zhì)量約束的報(bào)價(jià)策略為支持，將質(zhì)量感知的雙向拍賣機(jī)制作為HCRM交易模型的核心，建立了質(zhì)量感知的供需匹配模型，如圖2陰影部分所示。

交易管理的流程如下：（1）買(mǎi)家和賣家分別向市場(chǎng)提交自己的供給和需求，根據(jù)價(jià)格管理器提供的參考價(jià)格，自行或由代理提出報(bào)價(jià)。（2）交易管理器核查供應(yīng)質(zhì)量、需求參數(shù)以及買(mǎi)賣雙方給出的出價(jià)和要價(jià)是否合理。（3）類型篩選器按供需類型篩選出類型一致的供應(yīng)和需求。（4）拍賣器進(jìn)行質(zhì)量感知的雙向拍賣，拍賣中成功匹配的供應(yīng)和需求建立交易合約。（5）交易監(jiān)控器監(jiān)控交易合約的執(zhí)行情況。（6）成功執(zhí)行時(shí)由支付管理器負(fù)責(zé)買(mǎi)賣雙方的轉(zhuǎn)賬，當(dāng)有人違反合約時(shí)負(fù)責(zé)扣除違約方的罰款。（7）反饋管理器將收到的交易信息保存歸檔，并更新相關(guān)的數(shù)據(jù)庫(kù)。

2.3 HCRM的供需質(zhì)量模型

賣方提供的供應(yīng)集合 Supplies={Sp1，Sp2，…，Spi，…}，其中供應(yīng) Spi=(Resource_Typei，Seller_IDi，Supply_Numi，Resource_Qualityi，Lowest_Pricei，Valid_Timei) ，這 里Resource_Typei是賣方提供資源的種類；Seller_IDi賣方在市場(chǎng)注冊(cè)時(shí)獲得的ID；Supply_Numi是賣方所提供的資源數(shù)量；Lowest_Pricei（簡(jiǎn)記為L(zhǎng)pi）是賣方所報(bào)的最低售價(jià)，實(shí)際成交價(jià)格不能低于該值；Valid_Timei是指該資源的有效使用時(shí)段，去除該資源已分配和預(yù)留給其他買(mǎi)方的時(shí)間段。

賣方的Resource_Qualityi是由市場(chǎng)管理者根據(jù)資源可信性、賣家信譽(yù)、網(wǎng)絡(luò)安全性和用戶的偏好確定的，取值從1到5，用以指定同類型資源的不同質(zhì)量（5表示最高質(zhì)量）。

定義1（供應(yīng)Spi的資源質(zhì)量）

其中α1+α2+α3=1，具體取值根據(jù)用戶偏好確定，這里假定 α1=α2=α3=1/3。

（1）Reliabilityi表示資源可信度，由資源進(jìn)入市場(chǎng)的時(shí)間和資源服務(wù)成功率決定。Resource_Lifei是Spi進(jìn)入市場(chǎng)的時(shí)間，Market_life是整個(gè)市場(chǎng)的生存時(shí)間，Successi是Spi成功提供服務(wù)的次數(shù)，F(xiàn)aili是Spi曾經(jīng)服務(wù)失敗的次數(shù)。rank()是一個(gè)轉(zhuǎn)換函數(shù)，將一個(gè)百分?jǐn)?shù)轉(zhuǎn)換成1～5之間的數(shù)據(jù)。

這里β1+β2=1，具體取值根據(jù)用戶偏好確定，本文假定β1=0.4，β2=0.6。

（2）Reputationi代表賣方信譽(yù)度，完全由買(mǎi)方平均信譽(yù)反饋值決定。每一個(gè)與Spi交易的買(mǎi)家反饋一個(gè)1～5之間的數(shù)值Feedbackk評(píng)價(jià)賣家信譽(yù)情況，5為最高信譽(yù)。m是與Spi交易過(guò)的買(mǎi)家數(shù)量。

（3）Securityi表示該資源的網(wǎng)絡(luò)安全度，由市場(chǎng)管理者根據(jù)權(quán)威機(jī)構(gòu)的評(píng)估數(shù)據(jù)以及歷史信息給出，取值在1～5之間，5為最高安全等級(jí)。SecuValuei是權(quán)威認(rèn)證機(jī)構(gòu)對(duì)資源Spi所在網(wǎng)絡(luò)的安全性做出的認(rèn)證值，Normali為Spi所在網(wǎng)絡(luò)提供安全服務(wù)的次數(shù)，Unnormali是該資源曾經(jīng)出現(xiàn)網(wǎng)絡(luò)非安全服務(wù)的次數(shù)。rank()函數(shù)定義同上。

這里γ1+γ2=1，具體取值根據(jù)用戶偏好確定，本文假定γ1=0.5，γ2=0.5。

買(mǎi)方提交的需求集合Demand={Dm1，Dm2，…，Dmj，…} ，其中需求Dmj=(Resource_Typej，Buyer_IDj，Demand_Numj，Demand_Qualityj，Highest_Pricej，Demand_Timej)，這里 Resource_Typej是買(mǎi)方需求的資源種類；Buyer_IDj買(mǎi)方在市場(chǎng)注冊(cè)時(shí)獲得的ID；Demand_Numj是買(mǎi)方所需求的資源量；Highest_Pricej（簡(jiǎn)記為Hpj）是指買(mǎi)方可以接受的最高出價(jià)，實(shí)際交易價(jià)格不能高于該值；Demand_Timej指需求的有效時(shí)間，超出時(shí)效系統(tǒng)不再為該需求進(jìn)行匹配。

買(mǎi)方的Demand_Qualityj代表買(mǎi)方對(duì)資源的質(zhì)量需求。市場(chǎng)為用戶提供與質(zhì)量等級(jí)相應(yīng)的合理報(bào)價(jià)參考，以及已成交的歷史信息數(shù)據(jù)，買(mǎi)方根據(jù)自己的預(yù)算和市場(chǎng)信息提出報(bào)價(jià)。

2.4 質(zhì)量感知的雙向拍賣算法QaDA

經(jīng)典的連續(xù)雙向拍賣CDA（Continuous Double Auction）適用于同質(zhì)物品拍賣，HCRM中的資源來(lái)自不同賣方，質(zhì)量差別大，用戶就不同質(zhì)量資源差別定價(jià)已達(dá)成共識(shí)，因此設(shè)計(jì)了一種質(zhì)量感知的雙向拍賣算法QaDA（Quality-aware Double Auction）。

QaDA的交易過(guò)程描述如下：

（1）買(mǎi)賣雙方提交各自的報(bào)價(jià)和參加交易的供需數(shù)量信息。

（2）市場(chǎng)根據(jù)賣方供應(yīng)的質(zhì)量判斷交易者的報(bào)價(jià)是否合理，若合理則被市場(chǎng)接受，不合理則通知他們重新報(bào)價(jià)。

（3）市場(chǎng)中負(fù)責(zé)資源查找的模塊找到資源類型匹配的且都在有效期的供應(yīng)和需求加入到一個(gè)拍賣組，假設(shè)有m個(gè)供應(yīng)、n個(gè)需求。買(mǎi)方需求按報(bào)價(jià)從高到低排成一個(gè)隊(duì)列Qd，賣方供應(yīng)先按質(zhì)量從高到低、質(zhì)量相同的再按要價(jià)從低到高排成一個(gè)隊(duì)列Qs。供需依次交替進(jìn)行連續(xù)的匹配，直到全部供需都被處理完為止。

匹配過(guò)程如下：

注 ：（1）matched(Spi，Dmk)的條件是：(Resource_Typei與Resource_Typek一致或兼容)&&(Supply_Numi不少于Demand_Numk)&&(Valid_Timei滿足Demand_Timek)&&(Lpi不高于Hpk)。

（2）在一輪拍賣中成交的一對(duì)供需(Spi，Dmj)，其成交價(jià)格 Trade_Price 記為 Tpi，j，則

QaDA算法的調(diào)度時(shí)機(jī)有兩種：（1）異步調(diào)度，即每當(dāng)一個(gè)新的供應(yīng)Sp或者一個(gè)新的需求Dm到達(dá)時(shí)，供需匹配模塊就被調(diào)度執(zhí)行一次。這種方式調(diào)度頻率比較高。（2）時(shí)間段調(diào)度，即每到下一個(gè)時(shí)間段Time_Slot開(kāi)始，匹配模塊被調(diào)度一次。與異步調(diào)度相比，這種方式調(diào)度頻率降低，但是匹配算法處理的數(shù)據(jù)量增大。

2.5 匹配成功率和成交總量

為了保證買(mǎi)方的應(yīng)用不會(huì)因其在不同資源間切換而超時(shí)，這里規(guī)定：假定(Spi1，Dmj1)、(Spi2，Dmj2)是一輪拍賣中成交的兩對(duì)供需，則必有i1≠i2，而 j1=j2或者j1≠j2均有可能。

定義2將一個(gè)在一輪拍賣中匹配成功的賣方供應(yīng) Spi的資源集合定義為 R_Spi=R_Spi1∪R_Spi2∪…∪R_Spik∪…∪R_Spit∪R_Spia，t是正整數(shù)且t≥1，其中：

（1）t=1時(shí)，Spi中的資源只與一個(gè)買(mǎi)方需求成交。

（2）t＞1時(shí)，i1≠i2≠…≠ik≠…≠it，在本輪拍賣中成交的供需對(duì)中必有(Spi1，Dmj1)，(Spi2，Dmj2)，…，(Spik，Dmjk)，…，(Spit，Dmjt)并且 j1≠j2≠…≠jk≠…≠jt。

（3）R_Spia為Spi中在一輪拍賣結(jié)束后剩余的資源子集，R_Spia=?時(shí)Spi中全部資源都成交，R_Spia≠?時(shí)Spi中仍有剩余資源。

定義3一輪拍賣后，匹配成功率記為P：

一輪拍賣后，需求 Dmj的成交額記為 Amj，（1）如果 Dmj沒(méi)有匹配成功，則 Amj=0；（2）如果 Dmj與供應(yīng)Spi匹配成功，且匹配成功的資源量是Dj，成交價(jià)格是Tpi，j，則

一輪拍賣后，供應(yīng)Spi的成交額記為 Asi，（1）如果Spi沒(méi)有匹配成功，則 Asi=0；（2）若果 Spi被匹配給 t(t≥1)個(gè)買(mǎi)方，根據(jù)定義2將成交的匹配對(duì)記為(Spi1，Dmj1)，(Spi2，Dmj2)，…，(Spik，Dmjk)，…，(Spit，Dmjt)，且成交價(jià)格分別為 Tpi1，j1，Tpi2，j2，…，Tpik，jk，…，Tpit，jt，則

定義4一輪拍賣中m個(gè)賣方與n個(gè)買(mǎi)方的成交總量為：

下一章中將用匹配成功率P和拍賣成交總量A來(lái)比較不同拍賣算法的效率。

3 仿真結(jié)果與分析

為了進(jìn)行仿真驗(yàn)證，自行設(shè)計(jì)和開(kāi)發(fā)了一個(gè)小型的計(jì)算資源交易模擬系統(tǒng)，用Java語(yǔ)言編寫(xiě)，主要實(shí)現(xiàn)用戶注冊(cè)、供應(yīng)和需求提交、供需報(bào)價(jià)參考和報(bào)價(jià)代理、供需數(shù)據(jù)隨機(jī)生成、供需拍賣匹配、匹配結(jié)果圖表輸出等功能。數(shù)據(jù)庫(kù)采用MySQL，有用戶表、供應(yīng)表、需求表、歷史成交表、市場(chǎng)信息表等組成。本章實(shí)驗(yàn)中使用均勻分布的隨機(jī)數(shù)據(jù)，模擬運(yùn)行CDA算法[13]和QaDA算法，從賣家要價(jià)、買(mǎi)家出價(jià)、匹配成功率和成交總量方面進(jìn)行了比較分析。

有關(guān)的實(shí)驗(yàn)參數(shù)配置如下：資源類型分為A、B、C和D四種類型。參加匹配的供應(yīng)數(shù)m、參加匹配的需求數(shù)n；所有供應(yīng)的最低要價(jià)服從均勻分布 fL，所有需求的最高出價(jià)服從均勻分布 fH；所有供應(yīng)的數(shù)量服從均勻分布 fP，所有需求的數(shù)量服從均勻分布 fD；所有供應(yīng)的可用時(shí)間段服從均勻分布 fA，所有需求的求購(gòu)時(shí)間段服從均勻分布 fR；資源質(zhì)量等級(jí)服從均勻分布 fQ。

首先，考察匹配成功率與參與拍賣的供需數(shù)量的關(guān)系。這里認(rèn)為所有交易方均能理性報(bào)價(jià)，且對(duì)市場(chǎng)效益率有個(gè)基本認(rèn)同。取 fL=U(100，200)，fH=U(120，240)，單位是元/h；取 fP==U(1，20)，fD=U(1，20)，單位是VM；取 fA=fR=U(1，24)，單位是h。取 fQ=U(0，5)。

先設(shè)置 m=n，分別取值50、150、250、350、450、550、650、750、850、950，每種情況運(yùn)行500次，取其實(shí)驗(yàn)平均值，實(shí)驗(yàn)結(jié)果如圖3所示。再設(shè)先設(shè)置m=n，分別取值500、1 500、2 500、3 500、4 500、5 500、6 500、7 500、8 500、9 500，每種情況運(yùn)行500次，取其實(shí)驗(yàn)值的平均值，實(shí)驗(yàn)結(jié)果如圖4所示。

圖3 用戶數(shù)量較少時(shí)兩算法的匹配成功率

圖4 用戶數(shù)量較多時(shí)兩算法的匹配成功率

由實(shí)驗(yàn)數(shù)據(jù)可以看出：（1）隨著參與拍賣的供需數(shù)量的增加，兩種算法的匹配成功率均會(huì)增高。（2）相同條件下，QaDA比CDA的匹配成功率要高一些。不難分析CDA中出價(jià)高的需求先和報(bào)價(jià)最低的供應(yīng)匹配，使出價(jià)低的買(mǎi)方和出價(jià)高的賣方減少了匹配機(jī)會(huì)，影響到匹配成功率。QaDA中買(mǎi)/賣方交替與所有剩余賣/買(mǎi)方試探匹配的策略也提高了其匹配成功率。（3）相比之下，CDA對(duì)用戶數(shù)量的增長(zhǎng)敏感度較低，隨著供需數(shù)量的增加QaDA的匹配成功增長(zhǎng)率更明顯一些。QaDA更適用于拍賣參與者較多的情況。

上述實(shí)驗(yàn)的同時(shí)，記錄每次實(shí)驗(yàn)的成交金額，圖5由所有實(shí)驗(yàn)累計(jì)而得，實(shí)驗(yàn)數(shù)據(jù)表明，與CDA比較，QaDA獲得更大的成交總額。

圖5 兩種算法成交總量的比較

下面考察報(bào)價(jià)對(duì)匹配成功率的影響。先考慮賣方的要價(jià)，將賣方要價(jià)分為五個(gè)區(qū)間：[100，120）、[120，140）、[140，160）、[160，180）、[180，200]，分別統(tǒng)計(jì)不同賣價(jià)區(qū)間上賣方的匹配成功率，如圖6所示。很顯然：（1）CDA算法中賣方要價(jià)直接影響到匹配能否成功，要價(jià)在均衡價(jià)格以下的有機(jī)會(huì)成交，而要價(jià)高于均衡價(jià)格的則交易機(jī)會(huì)減為0。（2）QaDA算法中，各要價(jià)區(qū)間上的賣方匹配成功率沒(méi)有特別大的波動(dòng)，要價(jià)高的成交率稍微低一點(diǎn)但仍有很大的成交機(jī)會(huì)。

圖6 賣方報(bào)價(jià)范圍對(duì)匹配成功率的影響

再考慮買(mǎi)方的出價(jià)，將買(mǎi)方出價(jià)分為五個(gè)區(qū)間：[120，144）、[144，168）、[168，192）、[192，216）、[216，240]，分別統(tǒng)計(jì)不同出價(jià)區(qū)間上買(mǎi)方的匹配成功率，如圖7所示。實(shí)驗(yàn)結(jié)果顯示：（1）CDA算法中買(mǎi)方出價(jià)直接影響到匹配能否成功，出價(jià)在均衡價(jià)格以上的有機(jī)會(huì)成交，而出價(jià)低于均衡價(jià)格的則交易機(jī)會(huì)減為0。（2）QaDA算法中，各出價(jià)區(qū)間上的買(mǎi)方匹配成功率隨著出價(jià)降低慢速下降，出價(jià)低的需求成交率低一些，但是仍有成交機(jī)會(huì)。

圖7 買(mǎi)方出價(jià)范圍對(duì)匹配成功率的影響

圖6和圖7的實(shí)驗(yàn)結(jié)果表明CDA不支持差別定價(jià)，QaDA支持按資源質(zhì)量合理報(bào)價(jià)。

從拍賣機(jī)制本身容易分析得知，由于CDA讓出價(jià)高的需求先和報(bào)價(jià)最低的供應(yīng)匹配，造成種種不合理現(xiàn)象，如質(zhì)量差的資源優(yōu)先成交、質(zhì)量高（報(bào)價(jià)高）的資源賣不出去、出價(jià)最高的買(mǎi)方卻買(mǎi)到質(zhì)量最低的資源，等等。QaDA保證出價(jià)高的買(mǎi)方和質(zhì)量最高的資源先匹配，出價(jià)低的買(mǎi)方有機(jī)會(huì)買(mǎi)到要價(jià)低、質(zhì)量也低一些的資源。因此，CDA適用于同質(zhì)物品拍賣，QaDA更適用于不同質(zhì)量差別定價(jià)的混合云環(huán)境。

4 總結(jié)和展望

本文綜述了目前計(jì)算資源共享模型的發(fā)展，提出了基于混合云環(huán)境的計(jì)算資源市場(chǎng)HCRM，討論了HCRM的功能架構(gòu)、參與角色和交易管理機(jī)制。本文主要貢獻(xiàn)是建立了供應(yīng)和需求的質(zhì)量模型，設(shè)計(jì)并仿真運(yùn)行了一種質(zhì)量感知的雙向拍賣算法QaDA。實(shí)驗(yàn)結(jié)果表明，與普通的連續(xù)雙向拍賣算法CDA相比，QaDA不僅可以引導(dǎo)用戶合理定價(jià)，還能獲得較高的匹配成功率和較高的成交總量。

進(jìn)一步的工作有：（1）研究質(zhì)量模型相關(guān)參數(shù)取值的確定方法；（2）設(shè)計(jì)質(zhì)量評(píng)價(jià)驅(qū)動(dòng)的報(bào)價(jià)模型；（3）從理論上對(duì)QaDA進(jìn)行效用分析。

[1]Haas C，Caton S，Chard K，et al.Co-operative infrastructures：an economic model for providing infrastructures for social cloud computing[C]//46th Hawaii International Conference on System Sciences（HICSS），2013：729-738.

[2]Teodor-Florin F，Munteanu V I，Negru V.Towards a service friendly cloud ecosystem[C]//11th International Symposium on Parallel and Distributed Computing，2012：121-130.

[3]Subramanian K.Analyst&researcher krishworld.com，hybrid clouds[R].2011.

[4]García-Gómez S，Escriche-Vicente M，Arozarena-Llopis P.4CaaSt：comprehensive management of cloud services through a PaaS[C]//10th IEEE International Symposium on Parallel and Distributed Processing with Applications，2012：53-64.

[5]The cloudfoundry project[EB/OL].[2013-10-15].http：//www.Cloudfoundry.com/.

[6]The open shift project[EB/OL].[2013-10-15].https：//www.openshift.com/.

[7]The Andreas project[EB/OL].[2013-10-15].http：//www.informatik.uni-trier.de/～ley/pers/hd/m/Menychtas：Andreas.

[8]Nizamani S A.A quality-aware cloud selection service for computational modellers[D].2013.

[9]Lai K，Rasmusson L，Adar E，et al.Tycoon：an implementation of a distributed market-based resource allocation system[J].Multiagent Grid Systems，2005，1（3）：169-182.

[10]Waldspurger C A，Hogg T，Huberman B A，et al.Spawn：a distributed computational economy[J].IEEE Trans on Soft Engineering，1992，18（2）：103-117.

[11]Regev O，Nisan N.The POPCORN market.Online markets for computational resources[J].Decision Support Systems，2000，28：177-189.

[12]Lalis S，Karipidis A.JaWA：an open market-based framework for distributed computing over the Internet[J].Grid，2000，3：36-46.

[13]翁楚良，陸鑫達(dá).一種基于雙向拍賣機(jī)制的計(jì)算網(wǎng)格資源分配方法[J].計(jì)算機(jī)學(xué)報(bào)，2006，29（6）：1004-1009.

[14]丁丁，羅四維，艾麗華.基于雙向拍賣的適應(yīng)性云計(jì)算資源分配機(jī)制[J].通信學(xué)報(bào)，2012，33（Z1）：132-140.

[15]Lan Youwen，Tong Weiqin，Liu Zongheng，et al.Multiunit continuous double auction based resource allocation method[C]//2012 Third International Conference on Intelligent Control and Information Processing，2012.

[16]Teymouri S，Rahmani A M.A continues double auction method for resource allocation in economic grids[J].International Journal of Computer Applications，2012，43（17）：332-340.