Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing
-
摘要: 使用拍卖方式来进行资源分配可以使得资源提供商获得更大的收益，是云计算领域近年来研究的重点之一。但资源分配问题是NP难的，无法在多项式时间内求解，现有研究主要通过近似算法或启发式算法来实现资源分配，但存在算法耗时长，与最优解相比准确度低的缺点。监督学习中分类及回归思想可对多维云资源分配问题进行建模和分析，针对不同问题规模，该文提出基于线性回归、逻辑回归、支持向量机的3种资源分配算法，并且基于临界值理论设计了支付价格算法，从而确保拍卖机制的可信性。在社会福利、分配准确率、算法执行时间、资源利用率等多个方面进行测试分析，取得了很好的效果。Abstract: Auction based resource allocation can make resource provider get more profit, which is a major challenging problem for cloud computing. However, the resource allocation problem is NP-hard and can not be solved in polynomial time. Existing studies mainly use approximate algorithms or heuristic algorithms to implement resource allocation in auction, but these algorithms have the disadvantages of low computational efficiency or low allocate accuracy. In this paper, the classification and regression of supervised learning is used to model and analyze multi-dimensional cloud resource allocation, for the different scale of problem, three resource allocation predict algorithms based on linear regression, logistic regression and Support Vector Machine (SVM) are proposed. Through the learning of the small-scale training set, the predict model can guarantee that the social welfare, allocation accuracy, and resource utilization in the feasible solution are very close to the optimal allocation solution. The payment price algorithm based on the critical value theory is proposed which ensure the truthful property of the auction mechanism design. Final experimental results show that the proposed scheme has good effect for resource allocation in cloud computing.
-
Key words:
- Cloud computing /
- Resource allocation /
- Mechanism design /
- Supervised learning
-
表 1 基于临界值的价格计算算法(CV-PAY)
输入 所有用户的需求信息集：${R} = \{ R_{}^{(1)}\,R_{}^{(2)}\, ·\!·\!· \,R_{}^{(m)}\} $ 监督学习算法对资源分配的预测结果：
${PD} = ({\rm{pd}}_{}^{(1)}\,{\rm{pd}}_{}^{(2)}\, ·\!·\!· \,{\rm{pd}}_{}^{(m)})$每类虚拟资源的容量：${C} = ({c_1}\;\;\;{c_2}\;\;\; ·\!·\!· \;\;\;{c_n})$ 输出 被选中的用户需要支付的价格，
${Pay} = ({\rm pay}_{}^{(1)}\,{\rm{pay}}_{}^{(2)}\, ·\!·\!· \,{\rm{pay}}_{}^{(m)})$(1) ${{PD}^{\rm{*}}} \leftarrow 0$ (2) $\delta \leftarrow {10^{{\rm{ - }}6}}$ (3) for each $i \leftarrow \{ i|{\rm{pd}}_{}^{(i)} \in {PD}, {\rm{pd}}_{}^{(i)}{\rm{ = 1}}\} $ do (4) ${\rm{pay}}_{}^{(i)} \leftarrow b_{}^{(i)};{\rm{pay}}_{}^{(i)'} \leftarrow 0\;\;\;\;;\;\;\;b_{}^{(i)} \leftarrow ({\rm{pay}}_{}^{(i)} + {\rm{pay}}_{}^{(i)'})/2$ (5) while (${\rm{|pay}}_{}^{(i)}{\rm{ - pay}}_{}^{(i)'}{\rm{| > }}\delta $) do (6) 运行LN-ALLOC, LG-ALLOC或SVM-ALLOC求解
出新的资源分配解${P}{{D}^{\rm{*}}}$(7) if ${\rm{pd}}_{}^{(i)}{\rm{ = }}1\;\;\;,{\rm{pd}}_{}^{(i)} \in {P}{{D}^{\rm{*}}}$ (8) ${\rm{pay}}_{}^{(i)} \leftarrow b_{}^{(i)};b_{}^{(i)} \leftarrow ({\rm{pay}}_{}^{(i)} + {\rm{pay}}_{}^{(i)'})/2$ (9) else (10) ${\rm{pay}}_{}^{(i)'} \leftarrow b_{}^{(i)};b_{}^{(i)} \leftarrow ({\rm{pay}}_{}^{(i)} + {\rm{pay}}_{}^{(i)'})/2$ (11) end if (12) end while (13) ${Pay} \leftarrow {Pay} \cup {\rm{pay}}_{}^{(i)}$ (14) end for (15) return ${Pay}$ 
下载: 导出CSV
-
NISAN T, ROUGHGARDEN T, TARDOS E, et al. Algorithmic Game Theory[M]. Cambridge: Cambridge Univ. Press, 2007: 218–233. LEHMANN D, O’CALLAGHAN L, and SHOHAM Y. Truth revelation in approximately efficient combinatorial auctions[J]. Journal of the ACM, 2002, 49(5): 577–602. doi: 10.1145/585265.585266 NEJAD M M, MASHAYEKHY L, and GROSU D. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(2): 594–603. doi: 10.1109/TPDS.2014.2308224 MASHAYEKHY L, FISHER N, and GROSU D. Truthful mechanisms for competitive reward-based scheduling[J]. IEEE Transactions on Computers, 2016, 65(7): 2299–2312. doi: 10.1109/TC.2015.2479598 WU Qinghua and HAO Jinkao. A clique-based exact method for optimal winner determination in combinatorial auctions[J]. Information Sciences, 2016, 334(c): 103–121. doi: 10.1016/j.ins.2015.11.029 LAI J and PARKES D. Monotone branch-and-bound search for restricted combinatorial auctions[C]. Proceedings of the 13th ACM Conference on Electronic Commerce, Valencia, Spain, 2012: 705–722. BANSAL N, FRIGGSTAD Z, KHANDEKAR R, et al. A logarithmic approximation for unsplittable flow on line graphs[C]. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, USA, 2009: 702–709. CHAKRABARTI A, CHEKURI C, GUPTA A, et al. Approximation algorithms for the unsplittable flow problem[J]. Algorithmica, 2007, 47(1): 53–78. doi: 10.1007/s00453-006-1210-5 MASHAYEKHY L, NEJAD M M, and GROSU D. A PTAS mechanism for provisioning and allocation of heterogeneous cloud resources[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(9): 2386–2399. doi: 10.1109/TPDS.2014.2355228 SHI Weijie, ZHANG Linquan, WU Chuan, et al. An online auction framework for dynamic resource provisioning in cloud computing[J]. IEEE/ACM Transactions on Networking, 2016, 24(4): 2060–2073. doi: 10.1109/TNET.2015.2444657 LIU Xi, LI Weidong, and ZHANG Xuejie. Strategy-proof mechanism for provisioning and allocation virtual machines in heterogeneous clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(7): 1650–1663. doi: 10.1109/TPDS.2017.2785815 ZAMAN S and GROSU D. Combinatorial auction-based dynamic VM provisioning and allocation in clouds[C]. Proceedings of the 2011 IEEE Third International Conference on Cloud Computing Technology and Science (CloudCom), Athens, Greece, 2011: 107–114. ZAMAN S and GROSU D. Combinatorial auction-based allocation of virtual machine instances in clouds[J]. Journal of Parallel and Distributed Computing, 2013, 73(4): 495–508. doi: 10.1109/CloudCom.2010.28 ZHANG Jixian, XIE Ning, ZHANG Xuejie, et al. An online auction mechanism for cloud computing resource allocation and pricing based on user evaluation and cost[J]. Future Generation Computer Systems, 2018, 89: 286–299. doi: 10.1016/j.future.2018.06.034 张骥先, 谢宁, 李伟东, 等. 一种支持云计算虚拟资源分配的可信多需求拍卖机制[J]. 电子与信息学报, 2018, 40(1): 25–34. doi: 10.11999/JEIT170353ZHANG Jixian, XIE Ning, LI Weidong, et al. Truthful multi requirements auction mechanism for virtual resource allocation of cloud computing[J]. Journal of Electronics &Information Technology, 2018, 40(1): 25–34. doi: 10.11999/JEIT170353 ZHANG Jixian, XIE Ning, ZHANG Xuejie, et al. Machine learning based resource allocation of cloud computing in auction[J]. Computers Materials & Continua, 2018, 56(1): 123–135. doi: 10.3970/cmc.2018.03728 Grid Workloads Archives[OL]. http://gwa.ewi.tudelft.nl,2018.2. -
下载:
图(5) / 表(1)
计量
- 文章访问数: 2232
- HTML全文浏览量: 741
- PDF下载量: 81
- 被引次数: 0
