通用的多元抵制假名的云計算拍賣機制

游坤，王欽輝，李鑫

通用的多元抵制假名的云計算拍賣機制

游坤1，王欽輝2*，李鑫3

（1.金陵科技學院 軟件工程學院，南京 211169； 2.陸軍指揮學院 訓練管理系，南京 210045； 3.南京航空航天大學 計算機科學與技術(shù)學院，南京 211106）（ ? 通信作者電子郵箱qinhuiwang@aliyun.com）

針對云環(huán)境下資源拍賣機制設(shè)計問題，研究設(shè)計了一種更通用的多元抵制假名拍賣機制（GFAITH）。首先形式化定義了系統(tǒng)模型，其次圍繞誠信和抵制假名的設(shè)計目標，證明了當考慮用戶需求多樣性時，會出現(xiàn)新的作弊形式——需求減少作弊，它將破壞誠信屬性和抵制假名屬性，且實驗結(jié)果表明它將嚴重影響系統(tǒng)性能。據(jù)此，提出了GFAITH機制，從用戶預處理、預分配與定價、抵制需求減少作弊三個階段實現(xiàn)設(shè)計目標，并驗證了GFAITH的資源分配是可行的，而且能夠抵制假名。實驗結(jié)果表明，GFAITH能從利潤和社會財富等指標上有效保證系統(tǒng)的性能，驗證了該機制的有效性和效率。

云計算；機制設(shè)計；誠信；抵制假名；拍賣

0 引言

云計算是一種能夠提供按需訪問共享資源池的模型，這些資源包括CPU、存儲、內(nèi)存等，且通常被劃分為不同類型的虛擬機（Virtual Machines， VM），用戶按需訪問，并支付相應(yīng)的費用［1］。云計算的靈活性和高可靠性帶來了巨大的經(jīng)濟效益，但一個重要挑戰(zhàn)是需要共同解決資源管理與定價問題，以提高系統(tǒng)效率并激勵用戶和提供商參與［1］。

拍賣被廣泛應(yīng)用于銷售珍貴的商品，這引發(fā)了一波研究設(shè)計云資源拍賣機制的浪潮［2-3］。然而參與拍賣的投標人多是自私的，他們總是試圖通過操縱標價來獲利。因此，為充分利用云資源，拍賣機制必須阻止投標人作弊，而且鼓勵他們向拍賣人透露他們對競拍資源的真實估值。為解決這一問題，通常設(shè)計誠信（truthful）拍賣機制來阻止這種單純的投標作弊，如文獻［4-6］。然而，當可能出現(xiàn)假名投標時（即投標人以多個假名進行投標），誠信拍賣機制會失效。通過這種方式，不誠實的投標人能夠通過虛假名稱來投標，實現(xiàn)操縱拍賣結(jié)果的目標，這將導致機制不公平和效率損失。事實上，假名投標在互聯(lián)網(wǎng)上運行的各類拍賣中極易出現(xiàn)［7-8］，因為此情況下投標人可以很容易地生成多個假名，且不易被發(fā)現(xiàn)。由于云拍賣機制總是在互聯(lián)網(wǎng)上運行，導致容易出現(xiàn)同樣的作弊行為，比如通過多個郵件注冊不同的賬號來實現(xiàn)假名投標。然而現(xiàn)有的誠信拍賣機制并不能應(yīng)對這類新型作弊方式。因此，設(shè)計拍賣機制時既要保證誠信，還需要保護拍賣免受假名作弊，即需要確保機制是抵制假名（false-name-proof）的。

一方面，已有許多用于云資源分配的誠信拍賣機制，但它們不是抵制假名的；另一方面，已有的抵制假名拍賣機制并不能直接應(yīng)用于云拍賣，這是因為云拍賣的特殊性，即需要處理VM的異構(gòu)性（有多種類型的VM實例、每種類型都有多個單元）和用戶的多樣性（用戶對資源的需求偏好不同）?，F(xiàn)有抵制假名拍賣機制通常假設(shè)用戶是專一（single-minded）的，即用戶所請求資源要么被全部滿足，要么什么也沒有。一旦考慮用戶需求的多樣性，將出現(xiàn)一種新的作弊方式——需求減少（Demand-Reduction， DR）作弊。該作弊方式將破壞機制的抵制假名屬性，并嚴重影響拍賣系統(tǒng)性能。

為解決這一問題，本文考慮一個典型的VM實例拍賣場景，并設(shè)計一個既誠信又抵制假名投標的通用多元拍賣機制（General multi-unit FAlse-name-proof auction mechanism for vIrTual macHine allocation， GFAITH）。該系統(tǒng)中，投標人將他們的標價密封提交給拍賣師，以請求具有多個單元的不同類型的VM實例。GFAITH包括三個階段算法：第一階段對用戶進行預處理；第二階段對處理后的用戶進行預分配和預定價；第三階段基于預分配的結(jié)果阻止DR作弊操作。

本文的主要工作如下：

1）云拍賣場景下，考慮用戶的多樣性將出現(xiàn)新的作弊方式——DR作弊，證明了該作弊方式將破壞現(xiàn)有機制的抵制假名屬性，并將嚴重影響系統(tǒng)性能。

2）設(shè)計一種更通用的多元云拍賣機制GFAITH，并從理論上證明它既能保證誠信，又是抵制假名的。

3）通過實驗驗證GFAITH能有效保證系統(tǒng)的性能。

1 相關(guān)工作

為更高效管理云資源，如何設(shè)計高效的拍賣機制問題吸引了廣泛的研究興趣［9］。Wang等［6］建議將信任的第三方作為拍賣人進行利潤最大化的多輪拍賣；Samimi等［10］則提出了一個組合雙向拍賣機制；Hosseinalipour等［5］利用拍賣機制研究了云提供商和云管理者之間的交互問題。然而，這些工作主要聚焦于分配的公平與效率，并未考慮用戶的策略行為性。

Zhang等［11］針對ad-hoc Cloudlet場景，調(diào)度員和移動設(shè)備（Mobile Devices， MD）分別扮演拍賣師和投標人的角色，并提出了一種基于Lyapunov優(yōu)化和VCG（Vickrey-Clarke-Groves）的在線拍賣機制。Patel等［12］提出在線雙重拍賣，以實現(xiàn)基礎(chǔ)設(shè)施即服務(wù)（Infrastructure as a Service， IaaS）云中能源、收入和性能之間的多目標權(quán)衡。他們采用基于加權(quán)二分匹配的算法來確定獲勝者，并采用VCG驅(qū)動算法來確定支付方式。文獻［5］中研究客戶和云管理者之間的交互，并設(shè)計了基于期權(quán)的順序拍賣。近年來，一些研究工作設(shè)計了較多的雙向拍賣機制，如文獻［2-4］；同時一些已經(jīng)向移動邊緣計算拓展，如文獻［13-14］中設(shè)計了誠信拍賣機制。

然而，這些研究僅考慮了誠信屬性，并不能應(yīng)對假名投標的作弊。文獻［15］中研究了經(jīng)濟學組合拍賣中的假名投標，分析了假名投標獲利的形式和流行性，并在后續(xù)相關(guān)研究中提出了一些抵制假名的拍賣機制。但目前仍少有研究工作對云拍賣中的假名投標進行研究。文獻［8］中首次提出了云計算中運行靈活高效的抵制假名拍賣機制——虛擬機分配的抵制假名拍賣機制（False-name-proof Auction for vIrTual macHine allocation， FAITH），但它僅適用用戶是“專一”的情況，并未考慮用戶需求的多樣性。

不同于以往研究工作，本文考慮更通用的情況：即考慮了云資源的異構(gòu)性（多種類型與多種數(shù)量）與用戶的需求的多樣性，用戶參與拍賣需求不再是“專一”的，即可以被部分滿足。在這種情況下，證明將出現(xiàn)一種新的作弊方式——DR作弊，并通過實驗證明這一作弊形式將嚴重影響系統(tǒng)性能。據(jù)此，本文研究設(shè)計了更通用的拍賣機制GFAITH。

2 預備知識

2.1　系統(tǒng)模型

然而“專一性”假設(shè)與用戶的多樣性相悖：有些用戶僅需要部分資源就能滿足需求，如文本處理［18］。對此，本文考慮更一般的情況，即用戶需求類型存在多種可能，并分別討論所對應(yīng)的估值函數(shù)。根據(jù)文獻［18］的研究，通常將應(yīng)用類型劃分為三類：資源敏感型應(yīng)用、資源不敏感型應(yīng)用和介于兩者之間的類型，分別對應(yīng)以下估值類型：超加性（super-additive）、次加性（sub-additive）和一般性。

超加性意味著當投標人的要求不能完全滿足時，他們的效用會降低。這是有道理的，因為當投標人需要資源應(yīng)用于一些棘手的應(yīng)用場景時（如實時視頻流應(yīng)用），他們希望所請求的資源全部滿足，否則將影響服務(wù)質(zhì)量。值得注意的是，用戶是專一的情況可視為該類型的特殊情況。

次加性意味著當投標人的請求得到部分滿足時，分配更多的資源并不會顯著增加效用。這種類型與投標人對一些簡單的應(yīng)用程序（例如文件/文本傳輸應(yīng)用程序）需要較低資源的情況相吻合。

類型Ⅲ：一般情況。此時估值函數(shù)既不是遞增型也不是遞減型。幸運的是，根據(jù)文獻［19］的研究，一般情況下的估值函數(shù)可以表示為次加性的情況，但唯一的限制條件是估值函數(shù)是非遞減的，且在自由處置的普遍假設(shè)下可以自動滿足。

2.2　設(shè)計目標

首先給出拍賣設(shè)計的兩個關(guān)鍵屬性的定義：誠信和抵制假名，這是本文拍賣機制的主要設(shè)計目標。

3 挑戰(zhàn)

本文首先會證明：當考慮用戶的多樣性時，即用戶的需求可被部分滿足時，將出現(xiàn)新的作弊形式，這種新作弊形式將使現(xiàn)有的抵制假名拍賣機制失效；其次，通過仿真實驗證明這種新的作弊方式將大幅影響拍賣系統(tǒng)的性能。

3.1　研究方法

選擇FAITH［8］作為典型的云拍賣機制進行研究。主要基于以下考慮：一是FAITH是典型的抵制假名拍賣機制；二是FAITH同樣考慮了云拍賣的特殊屬性（資源的異構(gòu)性）。

首先簡要地介紹FAITH機制的工作原理，包括定價算法和分配算法兩部分，注意兩個算法運行之前，需要按單位權(quán)重標價從高到低對所有用戶進行排序。

3.2　新作弊方式

當用戶不再是專一的，而可以接受需求被部分滿足時，一種新的作弊方式出現(xiàn)了，稱為DR作弊。換句話說，當用戶的請求可以部分滿足時，它可以選擇需求欺騙以求獲利。

3.3　新作弊方式對系統(tǒng)的影響

運行實驗100次，并對結(jié)果求平均，圖1繪制了DR作弊方式使投標人的效用增加，其中縱軸表示累積分布函數(shù)（Cumulative Distribution Function， CDF）。從圖1中可觀察到近20%的作弊用戶可以通過DR作弊獲利。進一步，圖2通過顯示拍賣系統(tǒng)性能損失率（包括利潤損失和社會財富損失）與DR作弊用戶數(shù)量的關(guān)系，表明了DR作弊影響FAITH的利潤和社會財富。從圖2可以看出，DR作弊不僅會激勵投標人選擇作弊，而且還會損害系統(tǒng)性能。這也促使我們設(shè)計新機制來應(yīng)對DR作弊。

圖1　用戶通過DR作弊在FAITH里提升效用

基于上述分析，本文不再限制用戶需求的類型，而是考慮用戶需求的多樣性，并引入虛擬用戶的概念，完成用戶的預處理，再通過控制DR作弊設(shè)計抵制假名拍賣機制。

圖2　DR作弊影響FAITH的利潤和社會財富

4 機制設(shè)計

4.1　用戶類型分析

首先分析不同類型的用戶，分別對應(yīng)三種估值函數(shù)：

1）類型Ⅰ的用戶。直觀地說，對于類型Ⅰ的投標人，他們沒有動機使用多個虛假名稱單獨請求VM實例，因為較低的請求總是會產(chǎn)生較低的投標估值。因此，只需要在這種情況下阻止DR作弊。

綜上，以下分析只需要涵蓋類型Ⅰ和類型Ⅱ的投標人即可。

圖3　類型Ⅱ的估值函數(shù)

4.2　主要算法

算法1 GFAITH。

//階段1：用戶預處理

//階段2：預分配

//階段3：阻止DR作弊

階段1：用戶預處理。

階段2：預分配與定價。

階段3：抵制DR作弊。

4.3　性質(zhì)證明

首先證明GFAITH的資源分配是可行的。

定理1GFAITH滿足分配的可行性。

證明GFAITH分配是基于第二階段預分配的結(jié)果進行的，而第二階段的分配與定價算法與FAITH算法一致，因此GFAITH并不違背預分配的可行性。 證畢。

為證明GFAITH滿足抵制假名投標屬性，首先證明以下引理。

證明 類似地，根據(jù)文獻［8］中引理1，易得以下兩式：

分別考慮兩類用戶：

用戶選擇DR作弊的情況是類似的，此處證明過程省略。 證畢。

如果用戶不選擇DR作弊，分別考慮以下情況：

情況Ⅰ：降低報價獲得更少的資源。由于最終要支付的價格計算與自身的報價無關(guān)。因此，這種情況下，因為獲得分配的資源減少，效用將下降。

情況Ⅱ：降低報價獲得更多的資源。這種情況不存在，因為虛擬用戶中單位權(quán)重標價高的首先獲得分配，而GFAITH從不釋放資源再分配。

情況Ⅲ：提高報價獲得更少的資源。由于待支付的定價計算與自身的報價高低無關(guān)，它的效用在獲得更少的資源情況下也將下降。

綜合上述所有情況，在沒有DR作弊時，引理成立。

考慮DR作弊的情況，證明過程類似上述推導，故此處省略。 證畢。

定理2 GFAITH是抵制假名的。

證明 根據(jù)引理3和引理4，得證。

5 性能評估

5.1　實驗方法

5.2　實驗結(jié)果

為更好測試GFAITH性能，將GFAITH與經(jīng)典方法FAITH比較。使用利潤和社會財富作為性能評價指標：利潤是所有贏家定價之和，社會財富是所有贏家的出價之和。

實驗結(jié)果如圖4、5所示。從圖中可以看出，GFAITH比FAITH性能稍差，但差距控制在8%以內(nèi)。這是因為DR作弊會減少分配的資源，從而減少所產(chǎn)生的社會福利和收入，這是控制DR作弊、減少其影響系統(tǒng)性能所做出的犧牲。相對于20%的性能損害，這是值得的。值得注意的是，當沒有DR作弊時，GFAITH表現(xiàn)更好。

更進一步，通過計算機制的運行時間來評估評估機制的計算開銷。在帶有Intel Core i5-2520 CPU 2.5 GHz的Windows 7中，使用Matlab 2005b實現(xiàn)了這些機制，圖6是實驗結(jié)果，結(jié)果表明FAITH和Modified-IR具有相似的成本，因為它們具有相同規(guī)模的計算復雜度。Modified-IR是基于文獻［21］提出的一種名為迭代縮減（Iterative Reducing， IR）的單項目多單元抵制假名機制［8］，它的性能嚴重依賴于保留價格（reservation price）。然而如果保留價格不能精細確定，拍賣機制的性能可能會非常差。

相比之下，為了支持更通用的范圍請求投標，GFAITH消耗更多計算開銷來防止DR作弊，但這種增加的開銷仍然是線性的。

圖4　GFAITH的社會財富隨VM實例數(shù)量的變化趨勢

圖5　GFAITH的利潤隨VM實例數(shù)量的變化趨勢

圖6　GFAITH的時間開銷

6 結(jié)語

本文研究了云計算環(huán)境下抵制假名拍賣機制設(shè)計問題。現(xiàn)有機制僅支持單一請求格式，當考慮用戶需求多樣性時，證明了新的作弊形式——DR作弊將破壞抵制假名屬性和嚴重影響系統(tǒng)性能?；诖耍芯吭O(shè)計了一種更通用的多元拍賣機制GFAITH，支持多種類型用戶參與投標，并從理論上證明了GFAITH既滿足誠信屬性又能抵制假名，能在防DR作弊的情況下有效保證系統(tǒng)的性能。下一步工作，可研究允許投標人同時謊報總需求和估值函數(shù)的問題，或者擴展至雙向拍賣機制。

[1] HASHEM I A T， YAQOOB I， ANUAR N B， et al. The rise of “big data” on cloud computing： review and open research issues［J］. Information Systems， 2015， 47： 98-115.

[2] BARANWAL G， VIDYARTHI D P. A fair multi-attribute combinatorial double auction model for resource allocation in cloud computing［J］. Journal of Systems and Software， 2015， 108： 60-75.

[3] KUMAR D， BARANWAL G， RAZA Z， et al. A systematic study of double auction mechanisms in cloud computing［J］. Journal of Systems and Software， 2017， 125： 234-255.

[4] KUMAR D， BARANWAL G， RAZA Z， et al. A truthful combinatorial double auction-based marketplace mechanism for cloud computing［J］. Journal of Systems and Software， 2018， 140： 91-108.

[5] HOSSEINALIPOUR S， DAI H. A two-stage auction mechanism for cloud resource allocation［J］. IEEE Transactions on Cloud Computing， 2021， 9（3）： 881-895.

[6] WANG Q， GUO S， LIU J， et al. Profit maximization incentive mechanism for resource providers in mobile edge computing［J］. IEEE Transactions on Services Computing， 2022， 15（1）： 138-149.

[7] YOKOO M， SAKURAI Y， MATSUBARA S. The effect of false-name declarations in mechanism design： towards collective decision making on the internet［C］// Proceedings of the 20th IEEE International Conference on Distributed Computing Systems. Piscataway： IEEE， 2000： 146-153.

[8] WANG Q， YE B， TANG B， et al. eBay in the clouds： false-name-proof auctions for cloud resource allocation［C］// Proceedings of the IEEE 35th International Conference on Distributed Computing Systems. Piscataway： IEEE， 2015： 153-162.

[9] SHARGHIVAND N， DERAKHSHAN F， SIASI N. A comprehensive survey on auction mechanism design for cloud/edge resource management and pricing［J］. IEEE Access， 2021， 9： 126502-126529.

[10] SAMIMI P， TEIMOURI Y， MUKHTAR M. A combinatorial double auction resource allocation model in cloud computing［J］. Information Sciences， 2016， 357： 201-216.

[11] ZHANG D， TAN L， REN J， et al. Near-optimal and truthful online auction for computation offloading in green edge-computing systems［J］. IEEE Transactions on Mobile Computing， 2020， 19（4）： 880-893.

[12] PATEL Y S， MALWI Z， NIGHOJKAR A， et al. Truthful online double auction based dynamic resource provisioning for multi-objective trade-offs in IaaS clouds［J］. Cluster Computing， 2021， 24（3）： 1855-1879.

[13] ZHOU H， WU T， CHEN X， et al. Reverse auction-based computation offloading and resource allocation in mobile cloud- edge computing［J］. IEEE Transactions on Cloud Computing， 2022（Early Access）： 1-15.

[14] SU Y， FAN W， LIU Y， et al. A truthful combinatorial auction mechanism towards mobile edge computing in Industrial Internet of Things［J］. IEEE Transactions on Cloud Computing， 2023， 11（2）： 1678-1691.

[15] YOKOO M， SAKURAI Y， MATSUBARA S. The effect of false-name bids in combinatorial auctions： new fraud in internet auctions［J］. Games and Economic Behavior， 2004， 46（1）：174-188.

[16] Microsoft. Azure［EB/OL］. ［2022-07-30］.https：//azure.microsoft.com/zh-cn/.

[17] LEHMANN D， O’CALLAGHAN L I， SHOHAM Y. Truth revelation in approximately efficient combinatorial auctions［J］. Journal of the ACM， 2002， 49（5）： 577-602.

[18] WANG Q， YE B， LU S， et al. A truthful QoS-aware spectrum auction with spatial reuse for large-scale networks［J］. IEEE Transactions on Parallel and Distributed Systems， 2014， 46（1）： 2499-2508.

[19] TERADA K， YOKOO M. False-name-proof multi-unit auction protocol utilizing greedy allocation based on approximate evaluation values［C］// Proceedings of the 2nd International Conference on Autonomous Agents and Multiagent Systems. Richland， SC： International Foundation for Autonomous Agents and Multiagent Systems， 2003： 337-344.

[20] MAS-COLELL A， WHINSTON M D， GREEN J R. Microeconomic Theory［M］. Oxford ： Oxford University Press， 1995： 493-502.

[21] YOKOO M， SAKURAI Y， MATSUBARA S. Robust multi-unit auction protocol against false-name bids［C］// Proceedings of the 17th International Joint Conference on Artificial Intelligence - Volume 2. San Francisco： Morgan Kaufmann Publishers Inc.， 2001： 1089-1094.

General multi-unit false-name-proof auction mechanism for cloud computing

YOU Kun1， WANG Qinhui2*， LI Xin3

（1，，211169，；2，，210045，；3，，211106，）

Aiming at the problem of resource auction mechanism in cloud environment， a more General multi-unit FAlse-name-proof auction mechanism for vIrTual macHine allocation （GFAITH） was studied and designed. First， the system model was formally defined. Then， around the design goals of being truthfulness and false-name-proof， it was proved that when considering the diversity of user demands， a new form of cheating， Demand-Reduction （DR） cheating， would emerge， which could destroy the truthful and false-name-proof properties， and the experimental results show that it would seriously affect the system performance. Based on the above， the GFAITH was proposed to achieve the design goals in three stages： user pre-processing， pre-allocation and pricing， and resisting demand reduction cheating. It is theoretical proved that the resource allocation of GFAITH is feasible and able to resist false-name-proof. Experimental results show that GFAITH can effectively guarantee the performance of the system from indicators such as revenue and social wealth， verifying the effectiveness and efficiency of the proposed mechanism.

cloud computing; mechanism design; truthfulness; false-name-proof; auction

1001-9081（2023）11-3351-07

10.11772/j.issn.1001-9081.2022111705

2022?11?04；

2023?01?04；

國家自然科學基金資助項目（61802182）。

游坤（1982—），女，山西沁源人，高級工程師，博士，CCF會員，主要研究方向：云計算、服務(wù)計算； 王欽輝（1985—），男，江西豐城人，副教授，博士，主要研究方向：云計算、無線網(wǎng)絡(luò)； 李鑫（1987—），男，江西南昌人，副教授，博士，主要研究方向：云計算、邊緣計算。

TP393

A

2023?01?16。

This work is partially supported by National Natural Science Foundation of China （61802182）.

YOU Kun， born in 1982， Ph. D.， senior engineer. Her research interests include cloud computing， service computing.

WANG Qinhui， born in 1985， Ph. D.， associate professor. His research interests include cloud computing， wireless networks.

LI Xin， born in 1987， Ph. D.， associate professor. His research interests include cloud computing， edge computing.