毛鶯池 郝帥 平萍 戚榮志

摘 要：針對(duì)跨數(shù)據(jù)中心的資源調(diào)度問(wèn)題，提出了一種基于組合雙向拍賣（PCDA）的資源調(diào)度方案。首先，將云資源拍賣分為三個(gè)部分：云用戶代理報(bào)價(jià)、云資源提供商要價(jià)、拍賣代理組織拍賣;其次，在定義用戶的優(yōu)先級(jí)及任務(wù)緊迫度的基礎(chǔ)上，在拍賣過(guò)程中估算每一個(gè)工作發(fā)生的服務(wù)等級(jí)協(xié)議（SLA）違規(guī)并以此計(jì)算云提供商的收益，同時(shí)每輪競(jìng)拍允許成交多項(xiàng)交易;最終達(dá)到根據(jù)用戶等級(jí)合理分配云資源調(diào)度的效果。仿真實(shí)驗(yàn)結(jié)果表明該算法保證了競(jìng)拍成功率，與傳統(tǒng)一次拍賣成交一項(xiàng)的組合雙向拍賣方案相比，PCDA在競(jìng)拍時(shí)間段產(chǎn)生的能耗降低了35.00%，拍賣云提供商的利潤(rùn)提高了約38.84%。

關(guān)鍵詞：能耗;容器即服務(wù);資源調(diào)度;穩(wěn)定匹配;組合雙向拍賣

中圖分類號(hào)： TP393.027? ? ? 文獻(xiàn)標(biāo)志碼：A

Abstract： Aiming at the resource scheduling problem across data centers， a Priority Combinatorial Double Auction （PCDA） resource scheduling scheme was proposed. Firstly， cloud resource auction was divided into three parts： cloud user agent bidding， cloud resource provider bid， auction agent organization auction. Secondly， on the basis of defining user priority and task urgency， the violation of Service Level Agreement （SLA） of each job during auction was estimated and the revenue of cloud provider was calculated. At the same time， a number of transactions were allowed in each round of bidders. Finally， reasonable allocation of cloud resource scheduling according to user level could be achieved. The simulation results show that the algorithm guarantees the success rate of auction. Compared with traditional auction， PCDA reduces energy consumption by 35.00% and the profit of auction cloud provider is about 38.84%.

Key words： energy consumption; Container as a Service （CaaS）; resource scheduling; stable matching; combinatorial double auction

0 引言

經(jīng)典云計(jì)算服務(wù)體系可以分為三層：基礎(chǔ)設(shè)施即服務(wù)（Infrastructure-as-a-Service， IaaS）、平臺(tái)即服務(wù)（Platform-as-a-Service， PaaS）和軟件即服務(wù)（Software-as-a-Service， SaaS）[1]。通過(guò)使用PaaS模型，客戶能夠?qū)Ｗ⒂诖a而不用考慮維護(hù)成本和操作系統(tǒng)等因素。盡管PaaS服務(wù)模型具有上述優(yōu)勢(shì)，但仍然存在一些缺點(diǎn)。例如，在PaaS環(huán)境中開(kāi)發(fā)的應(yīng)用程序受平臺(tái)規(guī)范的限制——為了能夠在Google App Engine （GAE）上運(yùn)行Java應(yīng)用程序，開(kāi)發(fā)人員必須首先確保他們使用的第三方庫(kù)與GAE兼容，這是因?yàn)镚AE不支持所有的Java運(yùn)行時(shí)環(huán)境。近年來(lái)Shepherd[2]提出了容器即服務(wù)（Container-as-a-Service， CaaS）模型以解決PaaS模型導(dǎo)致的以上問(wèn)題。容器作為CaaS模型的實(shí)現(xiàn)基礎(chǔ)，提供了一種隔離的虛擬環(huán)境而不需要中間監(jiān)控介質(zhì)（Hypervisor）[3]。

基于容器的云數(shù)據(jù)中心不斷擴(kuò)建，不得不面對(duì)跨數(shù)據(jù)中心資源調(diào)度的能耗問(wèn)題。針對(duì)跨數(shù)據(jù)中心的資源調(diào)度問(wèn)題，本文提出了一種基于組合雙向拍賣（Priority Combinatorial Double Auction， PCDA）的資源調(diào)度方案，主要包含三個(gè)算法：云用戶及其代理的報(bào)價(jià)算法、云提供商及其代理的要價(jià)算法、拍賣代理算法。在拍賣過(guò)程中估算每一個(gè)工作發(fā)生的服務(wù)等級(jí)協(xié)議（Service Level Agreement， SLA）違規(guī)并以此計(jì)算云提供商的收益，同時(shí)每輪競(jìng)拍允許成交多項(xiàng)交易。仿真實(shí)驗(yàn)結(jié)果表明該算法保證了競(jìng)拍成功率，云提供商的利潤(rùn)提高了約38.84%。另外，PCDA方案在競(jìng)拍時(shí)間段產(chǎn)生的能耗比傳統(tǒng)一次拍賣成交一項(xiàng)的組合雙向拍賣方案節(jié)約35.00%。

1 相關(guān)工作

為解決跨數(shù)據(jù)中心的資源調(diào)度問(wèn)題，一些現(xiàn)有方法通過(guò)雙向拍賣機(jī)制來(lái)進(jìn)行資源調(diào)度。在這方面，孫佳佳等[4]提出一種基于雙向拍賣的智能資源分配機(jī)制，引入威望衰減系數(shù)和用戶信譽(yù)度，并且將群搜索優(yōu)化算法引入到資源分配機(jī)制中。He等[5]將跨數(shù)據(jù)中心資源調(diào)度的最小能耗成本問(wèn)題轉(zhuǎn)換約束隨機(jī)優(yōu)化問(wèn)題，然后在雙向拍賣機(jī)制的基礎(chǔ)上，利用Lyapunov優(yōu)化技術(shù)設(shè)計(jì)了一種在線控制算法以降低數(shù)據(jù)中心的能耗?；陔p向拍賣的資源調(diào)度方案研究中，還有一種將資源進(jìn)行組合拍賣的機(jī)制。在這方面，Zhao等[6]提出了一種組合雙向拍賣機(jī)制，將不同類型的虛擬機(jī)捆綁在一起進(jìn)行競(jìng)拍，采用多輪競(jìng)拍交易的方式使得上一輪競(jìng)標(biāo)失敗的用戶和數(shù)據(jù)中心有機(jī)會(huì)調(diào)整報(bào)價(jià)并提高獲得下一輪競(jìng)標(biāo)成功的概率。Huu等[7]提出了一種新的資源調(diào)度模型，使用組合雙向拍賣機(jī)制并考慮了能耗參數(shù)。基于此模型，作者提出了三種用于贏家確定的算法，實(shí)驗(yàn)結(jié)果表明三種算法中的綠色貪婪算法可以顯著減少數(shù)據(jù)中心的能耗并且為云提供商產(chǎn)生更高的收益。本文在這些已有方法的基礎(chǔ)上，研究了跨數(shù)據(jù)中心的資源調(diào)度問(wèn)題，提出了一種基于組合雙向拍賣的資源調(diào)度方案PCDA，保證了競(jìng)拍成功率，提高了云提供商的利潤(rùn)，降低了競(jìng)拍時(shí)間段產(chǎn)生的能耗。

2 問(wèn)題陳述與系統(tǒng)模型

2.1 問(wèn)題提出

現(xiàn)有云服務(wù)市場(chǎng)主要存在兩種資源交易方式：一種是云提供商提供固定的資源組合出售給用戶，但用戶的需求是靈活多變的，這也違背了云計(jì)算按需獲取的理念;另一種基于組合雙向拍賣的資源交易方式可以讓參與交易的雙方將多種類型的商品按照組合進(jìn)行報(bào)價(jià)，滿足了用戶對(duì)所需資源多樣性的需求并實(shí)現(xiàn)了資源的按需分配。

在組合雙向拍賣機(jī)制中最關(guān)鍵的問(wèn)題是確定每輪拍賣的獲勝者。已有方法[8-11]主要采用近似算法、啟發(fā)式算法等方式尋求一種最優(yōu)化策略來(lái)求解該問(wèn)題，但這些方法在云計(jì)算環(huán)境的規(guī)模較大時(shí)競(jìng)拍效率不高。另一方面，這些方法在運(yùn)用組合雙向拍賣機(jī)制進(jìn)行云資源分配時(shí)只考慮交易帶來(lái)的收益而忽略了能耗問(wèn)題。

基于上述問(wèn)題，本文提出了一種基于組合雙向拍賣的資源調(diào)度方案，定義了用戶優(yōu)先級(jí)并在獲勝者確定問(wèn)題中考慮了SLA違規(guī)造成的懲罰金這個(gè)因素，同時(shí)每輪拍賣成交多項(xiàng)交易提高了拍賣的效率，通過(guò)減少服務(wù)器節(jié)點(diǎn)空閑狀態(tài)的時(shí)間從而降低了數(shù)據(jù)中心的能耗。

2.2 基于組合雙向拍賣的資源競(jìng)拍模型

如圖1所示，云資源市場(chǎng)框架主要由云用戶及其代理、云提供商及其代理以及云市場(chǎng)管理者組成[12]。云用戶代理（UserBroker）幫助用戶完成交易，同時(shí)，云提供商將資源信息通過(guò)云提供商代理（ProviderBroker）提交到云市場(chǎng)管理者。云市場(chǎng)管理者是基于組合雙向拍賣的資源調(diào)度中的關(guān)鍵角色，主要包括云信息服務(wù)模塊和拍賣代理（BidBroker）模塊。

圖2展示了基于雙向拍賣的資源競(jìng)拍模型。任務(wù)執(zhí)行完成后，用戶需要向云提供商支付服務(wù)費(fèi)用，如果有新的任務(wù)需求則用戶需要重新參與競(jìng)拍獲得新的資源。對(duì)于云提供商的收益，主要是從用戶獲得的費(fèi)用減去執(zhí)行完成用戶任務(wù)的所有成本。其中，所有成本包括參與競(jìng)拍的費(fèi)用、競(jìng)拍時(shí)間服務(wù)器節(jié)點(diǎn)空閑狀態(tài)的能耗成本、執(zhí)行任務(wù)時(shí)產(chǎn)生的成本等。

如圖3所示，展示了拍賣模型的案例，用戶可以對(duì)A和B兩種類型的資源通過(guò)用戶代理給出報(bào)價(jià)，云提供商代理從拍賣市場(chǎng)獲得用戶請(qǐng)求信息并針對(duì)A和B這兩種捆綁資源包進(jìn)行要價(jià)，雙方通過(guò)拍賣代理完成交易，但是若在截止期限結(jié)束時(shí)不考慮SLA違規(guī)則性能有限，文獻(xiàn)[13]中提出一種新的獲勝者確定算法，考慮任務(wù)的期限限制（即任務(wù)緊急程度），以減少SLA違規(guī)的懲罰成本并最大化提供者的利潤(rùn)。本文在文獻(xiàn)[13]基礎(chǔ)上，定義了用戶優(yōu)先級(jí)并同時(shí)考慮任務(wù)的緊急程度來(lái)計(jì)算云提供商的利潤(rùn)。

3 總體思路

基于組合雙向拍賣的資源調(diào)度方案主要分為三個(gè)部分：

1）云用戶及其代理報(bào)價(jià)——云用戶代理根據(jù)用戶執(zhí)行任務(wù)所需的資源屬性（CPU核數(shù)、內(nèi)存大小和帶寬等）對(duì)執(zhí)行任務(wù)所對(duì)應(yīng)的捆綁云資源進(jìn)行報(bào)價(jià)，其中還要將時(shí)間因素考慮到出價(jià)的影響因素里，對(duì)于任務(wù)最后截止時(shí)間即將到來(lái)的時(shí)候，用戶會(huì)提高報(bào)價(jià)使競(jìng)拍成功。將時(shí)間作為報(bào)價(jià)的一個(gè)影響因素，那么如果用戶在競(jìng)拍中獲勝則云提供商必須保證將分配給該用戶所要求的整個(gè)期間的資源。用戶租用云資源時(shí)，因?yàn)槿蝿?wù)的時(shí)間期限，對(duì)于資源的需求緊迫程度是變化的。

2）云提供商及其代理要價(jià)——云提供商代理對(duì)于用戶所需資源捆綁包的要價(jià)主要從CPU、內(nèi)存和帶寬等的價(jià)格指標(biāo)衡量，對(duì)于在用戶完成任務(wù)的截止時(shí)間內(nèi)沒(méi)有執(zhí)行完任務(wù)的情況，云提供商需要交付SLA違約的懲罰金，SLA違規(guī)的懲罰金與超時(shí)時(shí)間成正比。懲罰金還與用戶等級(jí)有關(guān)，用戶等級(jí)越高，云資源提供商的SLA違規(guī)的懲罰金越多。

3）拍賣代理——針對(duì)每一類資源捆綁包，拍賣代理將用戶代理提交的報(bào)價(jià)和云資源提供商代理提交的要價(jià)進(jìn)行排序，對(duì)于滿足用戶報(bào)價(jià)高于云資源要價(jià)的情況按照用戶最高報(bào)價(jià)與云資源提供商最低要價(jià)進(jìn)行匹配，依次繼續(xù)，直到不滿足上述條件。拍賣代理還要考慮到不同等級(jí)的用戶享有資源的優(yōu)先級(jí)不同，保證不同等級(jí)的用戶利益和云提供商的利益。在一次拍賣成交多項(xiàng)的同時(shí)考慮用戶等級(jí)，更加契合了企業(yè)界中資源調(diào)度場(chǎng)景。

圖4展示了拍賣分階段流程。在拍賣代理算法執(zhí)行結(jié)束后，競(jìng)標(biāo)成功某捆綁資源的用戶提交任務(wù)到競(jìng)拍成功該捆綁資源的云提供商，云提供商從數(shù)據(jù)中心劃分出滿足該用戶需求的資源。

通過(guò)上述步驟后，云提供商需要分配資源給用戶以執(zhí)行完成任務(wù)。首先，用戶代理根據(jù)競(jìng)拍結(jié)果返回方案給用戶，用戶提交任務(wù)到競(jìng)拍結(jié)果映射的云提供商服務(wù)器節(jié)點(diǎn)上執(zhí)行;然后，任務(wù)執(zhí)行完成后，云提供商代理根據(jù)執(zhí)行結(jié)果和買方需要支付的費(fèi)用返回給用戶代理;最后，對(duì)于云提供商，如果發(fā)生了超過(guò)任務(wù)最后截止時(shí)間發(fā)生了SLA違規(guī)此句不通順，則需要支付相應(yīng)的懲罰金，對(duì)于用戶，則需要向云提供商支付服務(wù)費(fèi)用。

4 基于組合雙向拍賣的云資源調(diào)度方案

4.1 云用戶及代理報(bào)價(jià)

組合雙向拍賣方案中用戶的報(bào)價(jià)算法及參與競(jìng)標(biāo)需要滿足以下限制條件和函數(shù)。

1）對(duì)于第i個(gè)用戶的第k個(gè)任務(wù)taskki競(jìng)標(biāo)時(shí)用戶期望可以滿足的條件是在任務(wù)截止時(shí)間內(nèi)可以完成任務(wù)，即為：

其中：dki表示完成任務(wù)的截止時(shí)間，timebid是競(jìng)標(biāo)時(shí)間，timeexecute是指任務(wù)taskki的執(zhí)行時(shí)間，timeexecute的值等于任務(wù)長(zhǎng)度lengthki（單位是MI（Million of Instructions））與數(shù)據(jù)中心服務(wù)器節(jié)點(diǎn)的每秒百萬(wàn)條指令volj（MIPS，即Million Instructions Per Second）的比值。

2）假定第i個(gè)用戶的第k個(gè)任務(wù)，代理的估價(jià)vki與時(shí)間緊迫度成線性關(guān)系[11]，則：

其中， fv（t）與時(shí)間緊迫度成線性關(guān)系，其取值在（0，1）區(qū)間：

其中：kv是個(gè)結(jié)合緊迫程度來(lái)取值的常量設(shè)置為0.5，rmin表示估價(jià)預(yù)期最低值，rmax表示估價(jià)預(yù)期最高值。

3）云資源市場(chǎng)中，報(bào)價(jià)存在以下關(guān)系：

其中：bki表示第i個(gè)用戶的第k個(gè)任務(wù)對(duì)某捆綁云資源的報(bào)價(jià)，Prmin則為云市場(chǎng)允許的最低價(jià)，Prmax為云市場(chǎng)允許的最高價(jià)，則報(bào)價(jià)的解可表示成[11]：

云用戶代理給出報(bào)價(jià)主要是根據(jù)對(duì)捆綁資源的估價(jià)以及市場(chǎng)允許最高、最低價(jià)來(lái)確定的，并提交到拍賣代理參與競(jìng)標(biāo)。具體步驟如下：

1）用戶提交服務(wù)請(qǐng)求到用戶代理，由云用戶代理幫助其完成交易;

2）云用戶代理根據(jù)用戶任務(wù)的所需資源信息及任務(wù)的時(shí)間緊迫度給出報(bào)價(jià);

3）用戶代理將用戶所需資源請(qǐng)求以及價(jià)格信息提交到拍賣代理;

4）用戶代理等待拍賣代理返回結(jié)果，如果競(jìng)拍成功進(jìn)入步驟5），競(jìng)拍失敗則進(jìn)入步驟6）;

5）用戶代理競(jìng)拍成功，則返回競(jìng)拍結(jié)果給用戶，用戶獲得資源提供方的報(bào)價(jià)以及所需資源;

6）若用戶競(jìng)標(biāo)失敗，則返回到步驟1），等待下一輪的報(bào)價(jià)。

云用戶及其代理的報(bào)價(jià)算法偽代碼如下。

4.2 云提供商及其代理要價(jià)

用戶提交資源請(qǐng)求到云市場(chǎng)，云提供商從云市場(chǎng)獲得用戶所需資源捆綁包信息，提供商參加云市場(chǎng)的拍賣并為用戶分配容器實(shí)例。提供商的收益計(jì)算的相關(guān)函數(shù)以及要價(jià)函數(shù)如下所示。

云提供商代理對(duì)用戶所需資源的估價(jià)：

其中，percpu、permem、persto和perbw分別表示單位時(shí)間的CPU價(jià)格、內(nèi)存價(jià)格、存儲(chǔ)價(jià)格和帶寬價(jià)格，本文考慮這些單位時(shí)間資源類型的價(jià)格是隨著服務(wù)器節(jié)點(diǎn)資源利用情況動(dòng)態(tài)變化的?？紤]某種資源分配后數(shù)據(jù)中心剩余某種資源的單位價(jià)格與資源利用情況相關(guān)，下一次競(jìng)標(biāo)的要價(jià)如式（12）所示。CPUj、MEMj、STOj和BWj分別表示第j個(gè)資源提供商其數(shù)據(jù)中心服務(wù)器節(jié)點(diǎn)的當(dāng)前CPU處理能力、內(nèi)存大小、磁盤容量和網(wǎng)絡(luò)帶寬。usedCPU和totalCPU分別表示節(jié)點(diǎn)已經(jīng)使用的CPU資源量和該節(jié)點(diǎn)總的CPU資源量，usedMEM和totalMEM分別表示節(jié)點(diǎn)已經(jīng)使用的內(nèi)存資源量和該節(jié)點(diǎn)總的內(nèi)存資源量，usedSTO和totalSTO分別表示節(jié)點(diǎn)已經(jīng)使用的磁盤存儲(chǔ)資源和該節(jié)點(diǎn)總的磁盤存儲(chǔ)資源量，usedBW和totalBW分別表示節(jié)點(diǎn)已經(jīng)使用的帶寬資源和該節(jié)點(diǎn)總的帶寬資源。

云提供商將自身數(shù)據(jù)中心的資源情況信息提交到云提供商代理，代理根據(jù)其所提交的信息和從云市場(chǎng)管理獲得的用戶所需資源信息給出資源的要價(jià)。與大多數(shù)已有方法[14-16]不同，本文中云提供商的要價(jià)與當(dāng)前數(shù)據(jù)中心的資源利用情況關(guān)聯(lián)起來(lái)，實(shí)現(xiàn)了價(jià)格的動(dòng)態(tài)調(diào)整，這可以提高數(shù)據(jù)中心的資源利用效率并盡可能地避免了過(guò)載現(xiàn)象，從而保證了服務(wù)質(zhì)量（Quality of Service，QoS）。

云提供商代理的要價(jià)算法描述如下：

1）云提供商代理從云市場(chǎng)拍賣代理獲得用戶及所需資源信息。

2）云提供商代理根據(jù)用戶所需捆綁資源以及云提供商數(shù)據(jù)中心的資源利用情況給出要價(jià)。

3）云提供商代理將要價(jià)提交到拍賣代理。

4）等待競(jìng)拍結(jié)果，如果競(jìng)拍成功，則進(jìn)入步驟5）;競(jìng)拍失敗，進(jìn)入步驟6）。

5）從拍賣代理返回的結(jié)果是競(jìng)標(biāo)成功，分配資源給該用戶，進(jìn)入步驟7）。

6）從拍賣代理返回的結(jié)果是競(jìng)標(biāo)失敗，等待進(jìn)入下一輪競(jìng)拍，進(jìn)入步驟7）。

7）繼續(xù)當(dāng)前算法，直到所有競(jìng)拍任務(wù)完成。

云提供商及其代理的要價(jià)算法偽代碼如下。

云提供商通過(guò)云代理幫助其完成交易，也僅僅通過(guò)云代理獲得競(jìng)標(biāo)的結(jié)果和用戶任務(wù)的所需資源信息等，因此避免了云市場(chǎng)的惡意競(jìng)爭(zhēng)現(xiàn)象。

4.3 拍賣代理

傳統(tǒng)的雙向拍賣一次拍賣成交一項(xiàng)交易，并且大多數(shù)研究在獲勝者確定算法中沒(méi)有考慮時(shí)間緊迫度，基本上考慮的是最大化云提供商的收益而忽略了用戶收益。在云計(jì)算服務(wù)市場(chǎng)，用戶的等級(jí)不同，其享有的資源優(yōu)先級(jí)也不同，同時(shí)高用戶優(yōu)先級(jí)在資源調(diào)度過(guò)程中因?yàn)镾LA違規(guī)造成的懲罰金額也會(huì)更高，因此，為了保證不同等級(jí)的用戶利益和云提供商的利益，每個(gè)用戶有不同的優(yōu)先級(jí)，即超級(jí)VIP是3，VIP是2，普通用戶是1。在一次拍賣成交多項(xiàng)的同時(shí)考慮用戶等級(jí)，更加契合了企業(yè)界中資源調(diào)度場(chǎng)景。這里需要用到的條件及函數(shù)如下。

拍賣代理達(dá)成交易需滿足以下限制條件：

競(jìng)拍過(guò)程中用戶i的第k個(gè)任務(wù)與云提供商j如果競(jìng)拍匹配，云提供商j的預(yù)估利潤(rùn)profit為：

其中：l為一個(gè)常量設(shè)置為1，timebidnow表示當(dāng)前競(jìng)標(biāo)花費(fèi)的時(shí)間，lengthki表示第i個(gè)用戶的第k個(gè)任務(wù)的任務(wù)長(zhǎng)度，volj表示云提供商數(shù)據(jù)中心服務(wù)器節(jié)點(diǎn)的單位時(shí)間處理能力，lengthki與volj的商等于該任務(wù)假設(shè)在當(dāng)前云提供商服務(wù)器節(jié)點(diǎn)上時(shí)的執(zhí)行時(shí)間，Pricet表示單位時(shí)間的違約價(jià)格。

競(jìng)拍結(jié)束后，最終資源提供者的利潤(rùn)Eprofitj表示為：

拍賣代理負(fù)責(zé)從云用戶代理和云提供商代理獲取資源的報(bào)價(jià)和要價(jià)信息，并對(duì)所有報(bào)價(jià)和要價(jià)進(jìn)行一個(gè)排序后，為每種捆綁資源生成一個(gè)報(bào)價(jià)列表和一個(gè)要價(jià)列表。傳統(tǒng)雙向拍賣每次由用戶出價(jià)最高者與提供商要價(jià)最低者進(jìn)行交易，雖然這樣保證每次交易雙方都有收益，但每輪拍賣只能成交一項(xiàng)交易，其他用戶必須等到下一輪拍賣。本文拍賣代理算法中多個(gè)用戶和多個(gè)云提供商針對(duì)多種資源或資源組合遞交各自的價(jià)格，允許一次拍賣成交多項(xiàng)交易。拍賣代理從用戶所報(bào)最高價(jià)開(kāi)始在滿足式（13）和（14）的情況下尋找要價(jià)。

拍賣代理算法具體步驟如下：

1）用戶代理提交用戶所需資源信息和報(bào)價(jià)到拍賣代理，云提供商代理提交數(shù)據(jù)中心相關(guān)信息和要價(jià)到拍賣代理;

2）拍賣代理對(duì)各種捆綁資源分別生成所有用戶代理的報(bào)價(jià)列表以及對(duì)各種捆綁資源分別生成所有云提供商代理的要價(jià)列表;

3）拍賣代理根據(jù)用戶代理的報(bào)價(jià)和云提供商的要價(jià)，并依據(jù)當(dāng)前輪次的時(shí)間估算發(fā)生SLA違規(guī)的懲罰金，得到云提供商的預(yù)期利潤(rùn)profit;

4）對(duì)于某類捆綁資源，對(duì)所有用戶的報(bào)價(jià)以及所有云提供商的要價(jià)進(jìn)行排序;

5）對(duì)于某類捆綁資源，拍賣代理從用戶代理所報(bào)最高價(jià)開(kāi)始在滿足式（13）和（14）限制條件的情況下，尋找云提供商代理中要價(jià)最低的促成交易，再?gòu)挠脩魣?bào)價(jià)次高者繼續(xù)尋找此時(shí)剩余云提供商代理要價(jià)最低者促成交易，直至估算的profit≤0時(shí)結(jié)束這類資源的交易;

6）重復(fù)上述步驟4）和5），直至所有類型的捆綁資源都完成了交易，結(jié)束本輪拍賣;

7）一輪交易完成后，云用戶的任務(wù)情況和云提供商的資源情況都發(fā)生了變化，需要重新報(bào)價(jià)和要價(jià)，返回到步驟1）;

8）循環(huán)該策略，直至完成所有的任務(wù)。

拍賣代理算法偽代碼如下。

4.4 云資源調(diào)度方法能耗分析

在當(dāng)今全球能源緊缺的情況下，研究云市場(chǎng)中的資源調(diào)度時(shí)，應(yīng)當(dāng)將能耗作為資源調(diào)度的一個(gè)重要因素。從IaaS角度來(lái)說(shuō)，云計(jì)算數(shù)據(jù)中心一般由計(jì)算和存儲(chǔ)服務(wù)器、網(wǎng)絡(luò)設(shè)備、冷卻系統(tǒng)等組成，云資源集中存儲(chǔ)在數(shù)據(jù)中心再依據(jù)用戶需求分配調(diào)度這些云資源。當(dāng)云提供商參與競(jìng)拍的時(shí)候，數(shù)據(jù)中心處于開(kāi)啟狀態(tài)的服務(wù)器節(jié)點(diǎn)雖然并沒(méi)有執(zhí)行任務(wù)，但這些空閑的服務(wù)器節(jié)點(diǎn)也會(huì)產(chǎn)生電能的消耗。

假設(shè)用戶參與競(jìng)拍的時(shí)候，某云提供商的服務(wù)器節(jié)點(diǎn)處于空閑狀態(tài)，競(jìng)拍成功后，任務(wù)被分配到某云提供商的服務(wù)器節(jié)點(diǎn)上執(zhí)行時(shí)是處于滿負(fù)荷狀態(tài)。用Pidle表示空閑狀態(tài)發(fā)服務(wù)器節(jié)點(diǎn)的單位時(shí)間能耗，Pmax表示滿負(fù)載狀態(tài)下的服務(wù)器節(jié)點(diǎn)單位時(shí)間能耗，timebid表示參與競(jìng)拍的時(shí)間，timeexecute表示任務(wù)的執(zhí)行時(shí)間，則從競(jìng)拍開(kāi)始到用戶任務(wù)執(zhí)行結(jié)束，總的能耗為：

功耗模型中，忽略了在任務(wù)傳輸時(shí)間內(nèi)產(chǎn)生的能耗。另外，因?yàn)椴豢紤]云提供商如何具體劃分資源并分配給用戶的問(wèn)題，因此僅從時(shí)間角度建模能耗。一般情況下，數(shù)據(jù)中心各個(gè)服務(wù)器節(jié)點(diǎn)的CPU等資源即使在執(zhí)行任務(wù)時(shí)也并不是一直處于滿負(fù)荷狀態(tài)，而是隨著時(shí)間變化而變化的，但為方便建模計(jì)算，將服務(wù)器節(jié)點(diǎn)執(zhí)行任務(wù)時(shí)的狀態(tài)都看成是處于滿負(fù)荷狀態(tài)。

5 實(shí)驗(yàn)驗(yàn)證

5.1 實(shí)驗(yàn)環(huán)境

為了評(píng)估基于組合雙向拍賣的資源調(diào)度方案的性能，利用Eclipse編輯器采用Java語(yǔ)言編寫了仿真程序。

仿真程序編寫環(huán)境具體如下：實(shí)驗(yàn)計(jì)算機(jī)CPU為Intel Core i7-5500u，內(nèi)存為8GB，操作系統(tǒng)為Windows 10專業(yè)版，JDK版本為1.8。

實(shí)驗(yàn)參數(shù)設(shè)置：為了驗(yàn)證方案的性能，需要度量用戶競(jìng)標(biāo)成功率和能耗等指標(biāo)，因此設(shè)置了3個(gè)云提供商：云提供商1的資源有320個(gè)CPU核、640GB內(nèi)存、1000GB磁盤以及1000Mb/s帶寬帶寬的單位，是否應(yīng)該寫為“b/s”，即bps的規(guī)范表達(dá)，請(qǐng)明確。;云提供商2資源有240個(gè)CPU核、480GB內(nèi)存、1000GB磁盤以及1000Mb/s帶寬;云提供商3的資源有160個(gè)CPU核、320GB內(nèi)存、500GB磁盤以及500Mb/s帶寬。分別設(shè)置了5個(gè)用戶和20個(gè)用戶參與競(jìng)拍的場(chǎng)景，用戶任務(wù)的最后截止時(shí)間從5s到20s不等，用戶優(yōu)先級(jí)設(shè)置為三種，數(shù)值分別標(biāo)記為1、2、3。

服務(wù)器空閑節(jié)點(diǎn)的單位時(shí)間能耗設(shè)置為1.2kWh，滿負(fù)載狀態(tài)的單位時(shí)間能耗設(shè)置為2.0kWh。

三個(gè)云提供商設(shè)定服務(wù)器節(jié)點(diǎn)的每秒百萬(wàn)條指令volj分別設(shè)置為1MIPS、1MIPS、0.5MIPS;

三個(gè)云提供商因?yàn)镾LA違規(guī)導(dǎo)致的單位時(shí)間的違約價(jià)格分別設(shè)置為1元、1元、0.5元。

5.2 實(shí)驗(yàn)結(jié)果

競(jìng)標(biāo)成功率意味著用戶的請(qǐng)求能得到及時(shí)響應(yīng)的概率競(jìng)標(biāo)成功率意味著用戶的請(qǐng)求能否得到及時(shí)響應(yīng)此句“競(jìng)標(biāo)成功率意味著用戶的請(qǐng)求能否得到及時(shí)響應(yīng)”不通順，改為現(xiàn)在這樣，符合表達(dá)嗎？，因此在實(shí)驗(yàn)中首先對(duì)方案能否滿足用戶請(qǐng)求進(jìn)行仿真驗(yàn)證。如圖5（a）所示，當(dāng)設(shè)置參與競(jìng)拍的用戶數(shù)為5時(shí)，第一輪用戶競(jìng)標(biāo)成功率為40%，第二輪又競(jìng)標(biāo)成功了一個(gè)用戶任務(wù)，則第二輪時(shí)總的競(jìng)標(biāo)成功率為60%（第一輪的40%的競(jìng)標(biāo)成功率加上這一輪用戶競(jìng)標(biāo)成功率20%得到），以此類推?？梢?jiàn)，本方案在競(jìng)標(biāo)第四輪時(shí)，全部競(jìng)拍任務(wù)已經(jīng)完成，即競(jìng)標(biāo)成功率100%。如圖65（b），當(dāng)用戶數(shù)設(shè)置為20時(shí)，競(jìng)標(biāo)成功率在第6輪之后開(kāi)始快速上升，最終在第13輪達(dá)到100%。這是因?yàn)楸痉桨敢淮纬山欢囗?xiàng)提高了拍賣效率，因此能相對(duì)較快地完成競(jìng)拍并在競(jìng)標(biāo)成功率方面能保證用戶需求。

將本文方案（PCDA）與傳統(tǒng)的一次拍賣成交一項(xiàng)的組合雙向拍賣（Combinatorial Double Auction， CDA）方案[8]作比較。利潤(rùn)建模為：用戶的報(bào)價(jià)減去云提供商的要價(jià)后，再減去云提供商因?yàn)镾LA違規(guī)導(dǎo)致的懲罰金。如圖76所示，本文的PCDA方案比一次成交一項(xiàng)組合雙向拍賣的總體利潤(rùn)高38.84%。這是因?yàn)楸疚脑铺峁┥虨榱双@得最大化的收益需要盡可能地減少SLA違規(guī)，本文方案提高了競(jìng)拍效率（減少了timebid）導(dǎo)致云提供商SLA違規(guī)減少，相應(yīng)的懲罰金也減少了，最終，整個(gè)云市場(chǎng)所有參與競(jìng)拍的云提供商的整體利潤(rùn)就會(huì)提升。

競(jìng)拍的過(guò)程中，假定每個(gè)數(shù)據(jù)中心節(jié)點(diǎn)的單位時(shí)間能耗是額定的。依據(jù)文獻(xiàn)[16]中服務(wù)器在空閑狀態(tài)時(shí)的能耗能達(dá)到滿載時(shí)能耗的60%以上這一結(jié)論，在本實(shí)驗(yàn)中設(shè)置空閑狀態(tài)的服務(wù)器節(jié)點(diǎn)單位時(shí)間的能耗為1.2kWh，滿負(fù)載狀態(tài)的服務(wù)器節(jié)點(diǎn)單位時(shí)間能耗為2.0kWh。數(shù)據(jù)中心產(chǎn)生能耗的時(shí)間主要包括競(jìng)拍時(shí)間（服務(wù)器節(jié)點(diǎn)時(shí)空閑狀態(tài)）和任務(wù)執(zhí)行時(shí)間（服務(wù)器節(jié)點(diǎn)是滿負(fù)載狀態(tài)），忽略任務(wù)提交等傳輸時(shí)間因素。如圖7所示，本文提出的PCDA方案比傳統(tǒng)的組合雙向拍賣方案造成了更多的能耗，高出的能耗達(dá)34.40%。在設(shè)置拍賣時(shí)間時(shí)是每一輪拍賣時(shí)間為1s，因此當(dāng)任務(wù)長(zhǎng)度比較長(zhǎng)時(shí)，任務(wù)執(zhí)行時(shí)間就會(huì)較長(zhǎng)，此時(shí)從整體上任務(wù)的執(zhí)行時(shí)間長(zhǎng)短決定了能耗大小。任務(wù)的執(zhí)行時(shí)間是通過(guò)任務(wù)長(zhǎng)度除以數(shù)據(jù)中心的指令處理速度得到的，即lengthki/volj。本文設(shè)置實(shí)驗(yàn)中的3個(gè)數(shù)據(jù)中心的指令處理速度分別為1MIPS、1MIPS和0.5MIPS，而用戶的任務(wù)長(zhǎng)度是從6到120之間，大多數(shù)任務(wù)長(zhǎng)度設(shè)置為50以上，所以競(jìng)標(biāo)時(shí)間與任務(wù)執(zhí)行時(shí)間并不在一個(gè)數(shù)量級(jí)上，為此，對(duì)每一次任務(wù)單獨(dú)分析發(fā)現(xiàn)用戶提交的如果是短任務(wù)，PCDA算法能耗是低于傳統(tǒng)組合雙向拍賣方案的，佐證了本文的分析結(jié)果。

因?yàn)槠邢?，這里選取部分?jǐn)?shù)據(jù)如表1所示。序號(hào)1、4、5和6中任務(wù)長(zhǎng)度較短，即任務(wù)的執(zhí)行時(shí)間和競(jìng)拍時(shí)間在一個(gè)數(shù)量級(jí)時(shí)，可以看出因?yàn)镻CDA提高了拍賣效率減少了競(jìng)拍時(shí)間，實(shí)施PCDA方案進(jìn)行資源交易時(shí)的能耗小于實(shí)施CDA時(shí)的能耗，所以PCDA方案對(duì)于短任務(wù)比傳統(tǒng)一次交易成交一項(xiàng)的組合雙向拍賣更加節(jié)能。

更進(jìn)一步，為了去除任務(wù)時(shí)間對(duì)算法能耗的影響，本文僅僅對(duì)競(jìng)拍時(shí)間產(chǎn)生的能耗進(jìn)行了實(shí)驗(yàn)，如式（18）：

如圖98所示，當(dāng)對(duì)競(jìng)拍時(shí)間整個(gè)云市場(chǎng)參與競(jìng)拍的云提供商其服務(wù)器節(jié)點(diǎn)在競(jìng)拍時(shí)間段等待狀態(tài)時(shí)產(chǎn)生的能耗進(jìn)行統(tǒng)計(jì)，也就是忽略了每個(gè)數(shù)據(jù)中心的單位時(shí)間處理能力和任務(wù)長(zhǎng)度等影響因素，可以發(fā)現(xiàn)對(duì)于競(jìng)拍時(shí)間段產(chǎn)生的能耗，本文的PCDA比CDA算法平均節(jié)能約35.00%。

6 結(jié)語(yǔ)

針對(duì)跨數(shù)據(jù)中心的資源調(diào)度問(wèn)題，本文提出了一種基于組合雙向拍賣的資源調(diào)度方案——PCDA方案。PCDA中云用戶代理根據(jù)用戶資源需求進(jìn)行報(bào)價(jià)，云提供商根據(jù)云資源的價(jià)值對(duì)用戶進(jìn)行要價(jià)，拍賣代理根據(jù)用戶報(bào)價(jià)與云提供商的要價(jià)進(jìn)行綜合判斷以達(dá)到將云資源分配到用戶的最優(yōu)化。PCDA方案在雙向拍賣中確定獲勝者時(shí)定義了三種用戶優(yōu)先級(jí)，高優(yōu)先級(jí)用戶的任務(wù)如果沒(méi)有得到及時(shí)響應(yīng)處理，云提供商因?yàn)镾LA違規(guī)的懲罰金也就越高，在拍賣過(guò)程中計(jì)算每一個(gè)工作發(fā)生的SLA違規(guī)并以此計(jì)算云提供商的收益。每輪競(jìng)拍允許成交多項(xiàng)交易，提高了拍賣的效率。仿真實(shí)驗(yàn)結(jié)果表明，本文PCDA方案的云提供商利潤(rùn)比傳統(tǒng)組合雙向拍賣方案CDA的云提供商利潤(rùn)提高了38.84%。在競(jìng)拍時(shí)間段，PCDA方案中物理服務(wù)器產(chǎn)生的能耗比CDA方案減小了35.00%。

參考文獻(xiàn) （References）

[1] DOELITZSCHER F， SULISTIO A， REICH C， et al. Private cloud for collaboration and e-learning services： from IaaS to SaaS [J]. Computing， 2011， 91（1）： 23-42.

[2] SHEPHERD D. Containers as a Service （CaaS） is the cloud operating system-I build the cloud [EB/OL]. [2018-02-25]. http：//www.ibuildthecloud.com/blog/2014/08/19/containers-as-a-service-caas-is-the-cloud-operating-system/.

[3] PAHL C. Containerization and the PaaS cloud [J]. IEEE Cloud Computing， 2015， 2（3）： 24-31.

[4] 孫佳佳，王興偉，高程希，等.云環(huán)境下基于神經(jīng)網(wǎng)絡(luò)和群搜索優(yōu)化的資源分配機(jī)制[J].軟件學(xué)報(bào)，2014，25（8）：1858-1873.（SUN J J， WANG X W， GAO C X， et al. Resource allocation mechanism based on neural network and group search optimization in cloud environment [J]. Journal of Software， 2014， 25（8）： 1858-1873.）

[5] HE H， SHEN H. Green-aware online resource allocation for GEO-distributed cloud data centers on multi-source energy [C]// Proceedings of the 2017 International Conference on Parallel and Distributed Computing， Applications and Technologies. Piscataway， NJ： IEEE， 2017： 113-118.

[6] ZHAO Y， HUANG Z， LIU W， et al. A combinatorial double auction based resource allocation mechanism with multiple rounds for geo-distributed data centers [C]// Proceedings of the 2016 IEEE International Conference on Communications. Piscataway， NJ： IEEE， 2016： 1-6.

[7] HUU T T， THAM C K. An auction-based resource allocation model for green cloud computing [C]// Proceedings of the 2013 IEEE International Conference on Cloud Engineering. Piscataway， NJ： IEEE， 2013： 269-278.

[8] PRASAD G V， PRASAD A S， RAO S A. Combinatorial auction mechanism for multiple resource procurement in cloud computing [C]// Proceedings of the 2013 International Conference on Intelligent Systems Design and Applications. Piscataway， NJ： IEEE， 2013： 337-344.

[9] SHIRLEY S R， KARTHIKEYAN P. A survey on auction-based resource allocation in cloud environment [J]. International Journal of Research in Computer Applications and Robotics， 2013， 1（9）： 96-102.

[10] ALROKAYAN M， VDASTJERDI A， BUYYA R. SLA-aware provisioning and scheduling of cloud resources for big data analytics [C]// Proceedings of the 2014/3rd IEEE International Conference on Cloud Computing for Emerging Markets， Piscataway， NJ： IEEE， 2014： 1-8.

[11] 胡志剛，劉艷.云環(huán)境下基于組合雙向拍賣的動(dòng)態(tài)資源定價(jià)[J].計(jì)算機(jī)工程，2012，38（8）：19-21.（HU Z G， LIU Y. Dynamic resource pricing based on combinatorial double auction under cloud environment [J]. Computer Engineering， 2012， 38（8）： 19-21.）

[12] 馬同偉，解瑞云，廖曉飛.云計(jì)算環(huán)境下兼顧買賣雙方利益的雙向拍賣資源分配算法[J].計(jì)算機(jī)應(yīng)用研究，2016，33（3）：734-740.（MA T W， XIE R Y， LIAO X F. Two-way auction resource allocation algorithm for both buyers and sellers under the cloud computing environment [J]. Application Research of Computers， 2016， 33（3）： 734-740.）

[13] CHOI Y， LIM Y. Optimization approach for resource allocation on cloud computing for IoT [J]. International Journal of Distributed Sensor Networks， 2016， 12（3）： 1-6.

[14] ZAMAN S， GROSU D. A combinatorial auction-based mechanism for dynamic VM provisioning and allocation in clouds [J]. IEEE Transactions on Cloud Computing， 2013， 1（2）： 129-141.

[15] ZHAO Y， HUANG Z， LIU W， et al. A combinatorial double auction based resource allocation mechanism with multiple rounds for geo-distributed data centers [C]// Proceedings of the 2016 IEEE International Conference on Communications. Piscataway， NJ： IEEE， 2016： 1-6.

[16] WANG X， CHEN M， LEFURGY C， et al. SHIP： scalable hierarchical power control for large-scale data centers [C]// Proceedings of the 2009 International Conference on Parallel Architectures and Compilation Techniques. Piscataway， NJ： IEEE， 2009： 91-100.