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

doi:10.11772/j.issn.1001-9081.2022111705

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (11): 3351-3357.DOI: 10.11772/j.issn.1001-9081.2022111705

• National Open Distributed and Parallel Computing Conference 2022 (DPCS 2022） • Previous Articles Next Articles

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

Kun YOU¹, Qinhui WANG²(), Xin LI³

^1.School of Software Engineering，Jinling Institute of Technology，Nanjing Jiangsu 211169，China
^2.Department of Training Management，Army Command College，Nanjing Jiangsu 210045，China
^3.College of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing Jiangsu 211106，China

Received:2022-11-04 Revised:2023-01-04 Accepted:2023-01-16 Online:2023-02-28 Published:2023-11-10
Contact: Qinhui WANG
About author: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.
Supported by:
National Natural Science Foundation of China(61802182)

通用的多元抵制假名的云计算拍卖机制

游坤¹, 王钦辉²(), 李鑫³

^1.金陵科技学院软件工程学院, 南京 211169
^2.陆军指挥学院训练管理系, 南京 210045
^3.南京航空航天大学计算机科学与技术学院, 南京 211106

通讯作者: 王钦辉
作者简介:游坤（1982—），女，山西沁源人，高级工程师，博士，CCF会员，主要研究方向：云计算、服务计算
王钦辉（1985—），男，江西丰城人，副教授，博士，主要研究方向：云计算、无线网络 qinhuiwang@aliyun.com
李鑫（1987—），男，江西南昌人，副教授，博士，主要研究方向：云计算、边缘计算。
基金资助:
国家自然科学基金资助项目(61802182)

Abstract

Abstract:

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.

Key words: cloud computing, mechanism design, truthfulness, false-name-proof, auction

摘要：

针对云环境下资源拍卖机制设计问题，研究设计了一种更通用的多元抵制假名拍卖机制（GFAITH）。首先形式化定义了系统模型，其次围绕诚信和抵制假名的设计目标，证明了当考虑用户需求多样性时，会出现新的作弊形式——需求减少作弊，它将破坏诚信属性和抵制假名属性，且实验结果表明它将严重影响系统性能。据此，提出了GFAITH机制，从用户预处理、预分配与定价、抵制需求减少作弊三个阶段实现设计目标，并验证了GFAITH的资源分配是可行的，而且能够抵制假名。实验结果表明，GFAITH能从利润和社会财富等指标上有效保证系统的性能，验证了该机制的有效性和效率。

关键词: 云计算, 机制设计, 诚信, 抵制假名, 拍卖

CLC Number:

TP393

Kun YOU, Qinhui WANG, Xin LI. General multi-unit false-name-proof auction mechanism for cloud computing[J]. Journal of Computer Applications, 2023, 43(11): 3351-3357.

游坤, 王钦辉, 李鑫. 通用的多元抵制假名的云计算拍卖机制[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3351-3357.

Figures/Tables 6

Fig. 1 Users effectively improving utility by DR cheating in FAITH

Fig. 2 DR cheating impact on revenue and social welfare of auctioneer

Fig. 3 Valuation function of Type Ⅱ

Fig. 4 Social wealth of GFAITH varying with number of VM instances

Fig. 5 Revenue of GFAITH varying with number of VM instances

Fig. 6 Running time of GFAITH

References 21

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. 10.1016/j.is.2014.07.006
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. 10.1016/j.jss.2015.06.025
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. 10.1016/j.jss.2016.12.009
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. 10.1016/j.jss.2018.03.003
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. 10.1109/tcc.2019.2901785
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. 10.1109/tsc.2019.2924002
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. 10.1109/icdcs.2015.24
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.1109/access.2021.3110914
10	SAMIMI P， TEIMOURI Y， MUKHTAR M. A combinatorial double auction resource allocation model in cloud computing［J］. Information Sciences， 2016， 357： 201-216. 10.1016/j.ins.2014.02.008
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. 10.1109/tmc.2019.2901474
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. 10.1007/s10586-020-03225-9
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. 10.1109/tmc.2022.3189050
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. 10.1109/tcc.2022.3155495
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. 10.1016/s0899-8256(03)00045-9
16	Microsoft. Azure［EB/OL］. ［2022-07-30］..
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. 10.1145/585265.585266
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. 10.1145/860575.860630
20	MAS-COLELL A， WHINSTON M D， GREEN J R. Microeconomic Theory［M］. Oxford ： Oxford University Press， 1995： 493-502. 10.52292/j.estudecon.1996.463
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. 10.1016/s0004-3702(01)00077-7

[1]	Chaoying YAN, Ziyi ZHANG, Yingnan QU, Qiuyu LI, Dixiang ZHENG, Lijun SUN. Double auction carbon trading based on consortium blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3240-3245.
[2]	Peiyao ZHANG, Xiaodong FU. Incentive mechanism of crowdsourcing multi-task assignment against malicious bidding [J]. Journal of Computer Applications, 2024, 44(1): 261-268.
[3]	Jingyi WANG, Chao LI, Heng SONG, Di LI, Junwu ZHU. Spectrum combinatorial auction mechanism based on random walk algorithm [J]. Journal of Computer Applications, 2023, 43(8): 2352-2357.
[4]	Jiaxing LU, Hua DAI, Yuanlong LIU, Qian ZHOU, Geng YANG. Dictionary partition vector space model for ciphertext ranked search in cloud environment [J]. Journal of Computer Applications, 2023, 43(7): 1994-2000.
[5]	Yanan PAN, Qingxian PAN, Zhaoyi YU, Jiajing CHU, Song YU. Online incentive mechanism based on quality perception in spatio-temporal crowdsourcing [J]. Journal of Computer Applications, 2023, 43(7): 2091-2099.
[6]	Jingyu SUN, Jiayu ZHU, Ziqiang TIAN, Guozhen SHI, Chuanjiang GUAN. Attribute based encryption scheme based on elliptic curve cryptography and supporting revocation [J]. Journal of Computer Applications, 2022, 42(7): 2094-2103.
[7]	Jinquan ZHANG, Shouwei XU, Xincheng LI, Chongyang WANG, Jingzhi XU. Cloud computing task scheduling based on orthogonal adaptive whale optimization [J]. Journal of Computer Applications, 2022, 42(5): 1516-1523.
[8]	CHEN Jiahao, YIN Xinchun. Traceable and revocable ciphertext-policy attribute-based encryption scheme based on cloud-fog computing [J]. Journal of Computer Applications, 2021, 41(6): 1611-1620.
[9]	GE Lina, HU Yugu, ZHANG Guifen, CHEN Yuanyuan. Reverse hybrid access control scheme based on object attribute matching in cloud computing environment [J]. Journal of Computer Applications, 2021, 41(6): 1604-1610.
[10]	LI Bei, ZHANG Wenyin, WANG Jiuru, ZHAO Wei, WANG Haifeng. Sealed-bid auction scheme based on blockchain [J]. Journal of Computer Applications, 2021, 41(4): 999-1004.
[11]	YANG Ling, JIANG Chunmao. Strategy of energy-aware virtual machine migration based on three-way decision [J]. Journal of Computer Applications, 2021, 41(4): 990-998.
[12]	ZHU Yongjin, YIN Fei, DOU Longlong, WU Kun, ZHANG Zhiwei, QIAN Zhuzhong. Adaptive network transmission mechanism based on forward error correction [J]. Journal of Computer Applications, 2021, 41(3): 825-832.
[13]	Xiaoling SUN, Guang YANG, Yanping SHEN, Qiuge YANG, Tao CHEN. Searchable encryption scheme based on splittable inverted index [J]. Journal of Computer Applications, 2021, 41(11): 3288-3294.
[14]	LYU Jiayu, ZHU Zhirong, YAO Zhiqiang. Two-channel dynamic data encryption strategy in cloud computing environment [J]. Journal of Computer Applications, 2020, 40(8): 2268-2273.
[15]	GUO Shujie, LI Zhihua, LIN Kaiqing. Fuzzy membership degree based virtual machine placement algorithmin cloud environment [J]. Journal of Computer Applications, 2020, 40(5): 1374-1381.

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

通用的多元抵制假名的云计算拍卖机制

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 21

Related Articles 15

Recommended Articles

Metrics