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

doi:10.11772/j.issn.1001-9081.2022111705

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (11): 3351-3357.DOI: 10.11772/j.issn.1001-9081.2022111705

• 2022年全国开放式分布与并行计算学术年会(DPCS 2022) • 上一篇

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

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

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

收稿日期:2022-11-04 修回日期:2023-01-04 接受日期:2023-01-16 发布日期:2023-02-28 出版日期:2023-11-10
通讯作者: 王钦辉
作者简介:游坤（1982—），女，山西沁源人，高级工程师，博士，CCF会员，主要研究方向：云计算、服务计算
王钦辉（1985—），男，江西丰城人，副教授，博士，主要研究方向：云计算、无线网络 qinhuiwang@aliyun.com
李鑫（1987—），男，江西南昌人，副教授，博士，主要研究方向：云计算、边缘计算。
基金资助:
国家自然科学基金资助项目(61802182)

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP393

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

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.

图/表 6

图1 用户通过DR作弊在FAITH里提升效用

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

图2 DR作弊影响FAITH的利润和社会财富

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

图3 类型Ⅱ的估值函数

Fig. 3 Valuation function of Type Ⅱ

图4 GFAITH的社会财富随VM实例数量的变化趋势

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

图5 GFAITH的利润随VM实例数量的变化趋势

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

图6 GFAITH的时间开销

Fig. 6 Running time of GFAITH

参考文献 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]	王菁怡, 李超, 宋衡, 李迪, 朱俊武. 基于随机游走算法的频谱组合拍卖机制[J]. 《计算机应用》唯一官方网站, 2023, 43(8): 2352-2357.
[2]	陆佳行, 戴华, 刘源龙, 周倩, 杨庚. 面向云环境密文排序检索的字典划分向量空间模型[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 1994-2000.
[3]	潘亚楠, 潘庆先, 于兆一, 褚佳静, 于嵩. 时空众包中基于质量感知的在线激励机制[J]. 《计算机应用》唯一官方网站, 2023, 43(7): 2091-2099.
[4]	孙京宇, 朱家玉, 田自强, 史国振, 关川江. 基于椭圆曲线加密且支持撤销的属性基加密方案[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2094-2103.
[5]	张金泉, 徐寿伟, 李信诚, 王重洋, 徐景芝. 基于正交自适应鲸鱼优化的云计算任务调度[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1516-1523.
[6]	陈家豪, 殷新春. 基于云雾计算的可追踪可撤销密文策略属性基加密方案[J]. 计算机应用, 2021, 41(6): 1611-1620.
[7]	葛丽娜, 胡雨谷, 张桂芬, 陈园园. 云计算环境基于客体属性匹配的逆向混合访问控制方案[J]. 计算机应用, 2021, 41(6): 1604-1610.
[8]	杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998.
[9]	李蓓, 张问银, 王九如, 赵伟, 王海峰. 基于区块链的密封式投标拍卖方案[J]. 计算机应用, 2021, 41(4): 999-1004.
[10]	祝永晋, 尹飞, 豆龙龙, 吴昆, 张志伟, 钱柱中. 基于前向纠错的自适应网络传输机制[J]. 计算机应用, 2021, 41(3): 825-832.
[11]	孙晓玲, 杨光, 沈焱萍, 杨秋格, 陈涛. 基于可拆分倒排索引的可搜索加密方案[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3288-3294.
[12]	吕佳玉, 竺智荣, 姚志强. 云计算环境下的双通道数据动态加密策略[J]. 计算机应用, 2020, 40(8): 2268-2273.
[13]	郭曙杰, 李志华, 蔺凯青. 云环境下基于模糊隶属度的虚拟机放置算法[J]. 计算机应用, 2020, 40(5): 1374-1381.
[14]	陈程军, 毛莺池, 王绎超. 基于激活-熵的分层迭代剪枝策略的CNN模型压缩[J]. 计算机应用, 2020, 40(5): 1260-1265.
[15]	许英鑫, 孙磊, 赵建成, 郭松辉. 基于蚁群优化算法的虚拟现场可编程门阵列部署策略[J]. 计算机应用, 2020, 40(3): 747-752.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 21

相关文章 15

编辑推荐

Metrics