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

毛鶯池 郝帥 平萍 戚榮志

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

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

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

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

1 相關工作

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

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

2.1 問題提出

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

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

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

2.2 基于組合雙向拍賣的資源競拍模型

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

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

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

3 總體思路

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

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

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

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

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

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

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

4.1 云用戶及代理報價

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

1）對于第i個用戶的第k個任務taskki競標時用戶期望可以滿足的條件是在任務截止時間內(nèi)可以完成任務，即為：

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

2）假定第i個用戶的第k個任務，代理的估價vki與時間緊迫度成線性關系[11]，則：

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

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

3）云資源市場中，報價存在以下關系：

其中：bki表示第i個用戶的第k個任務對某捆綁云資源的報價，Prmin則為云市場允許的最低價，Prmax為云市場允許的最高價，則報價的解可表示成[11]：

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

1）用戶提交服務請求到用戶代理，由云用戶代理幫助其完成交易;

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

3）用戶代理將用戶所需資源請求以及價格信息提交到拍賣代理;

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

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

6）若用戶競標失敗，則返回到步驟1），等待下一輪的報價。

云用戶及其代理的報價算法偽代碼如下。

4.2 云提供商及其代理要價

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

云提供商代理對用戶所需資源的估價：

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

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

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

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

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

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

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

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

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

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

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

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

4.3 拍賣代理

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

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

競拍過程中用戶i的第k個任務與云提供商j如果競拍匹配，云提供商j的預估利潤profit為：

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

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

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

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

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

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

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

4）對于某類捆綁資源，對所有用戶的報價以及所有云提供商的要價進行排序;

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

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

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

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

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

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

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

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

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

5 實驗驗證

5.1 實驗環(huán)境

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

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

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

服務器空閑節(jié)點的單位時間能耗設置為1.2kWh，滿負載狀態(tài)的單位時間能耗設置為2.0kWh。

三個云提供商設定服務器節(jié)點的每秒百萬條指令volj分別設置為1MIPS、1MIPS、0.5MIPS;

三個云提供商因為SLA違規(guī)導致的單位時間的違約價格分別設置為1元、1元、0.5元。

5.2 實驗結(jié)果

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

將本文方案（PCDA）與傳統(tǒng)的一次拍賣成交一項的組合雙向拍賣（Combinatorial Double Auction， CDA）方案[8]作比較。利潤建模為：用戶的報價減去云提供商的要價后，再減去云提供商因為SLA違規(guī)導致的懲罰金。如圖76所示，本文的PCDA方案比一次成交一項組合雙向拍賣的總體利潤高38.84%。這是因為本文云提供商為了獲得最大化的收益需要盡可能地減少SLA違規(guī)，本文方案提高了競拍效率（減少了timebid）導致云提供商SLA違規(guī)減少，相應的懲罰金也減少了，最終，整個云市場所有參與競拍的云提供商的整體利潤就會提升。

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

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

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

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

6 結(jié)語

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

參考文獻 （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)絡和群搜索優(yōu)化的資源分配機制[J].軟件學報，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)境下基于組合雙向拍賣的動態(tài)資源定價[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] 馬同偉，解瑞云，廖曉飛.云計算環(huán)境下兼顧買賣雙方利益的雙向拍賣資源分配算法[J].計算機應用研究，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.