高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于监督学习的可信云计算资源拍卖机制研究

张骥先 谢宁 张学杰 李伟东

张骥先, 谢宁, 张学杰, 李伟东. 基于监督学习的可信云计算资源拍卖机制研究[J]. 电子与信息学报, 2019, 41(5): 1243-1250. doi: 10.11999/JEIT180587
引用本文: 张骥先, 谢宁, 张学杰, 李伟东. 基于监督学习的可信云计算资源拍卖机制研究[J]. 电子与信息学报, 2019, 41(5): 1243-1250. doi: 10.11999/JEIT180587
Jixian ZHANG, Ning XIE, Xuejie ZHANG, Weidong LI. Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1243-1250. doi: 10.11999/JEIT180587
Citation: Jixian ZHANG, Ning XIE, Xuejie ZHANG, Weidong LI. Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1243-1250. doi: 10.11999/JEIT180587

基于监督学习的可信云计算资源拍卖机制研究

doi: 10.11999/JEIT180587
基金项目: 国家自然科学基金(61472345, 61762091, 11663007),云南省教育厅科学研究基金(2017ZZX228)
详细信息
    作者简介:

    张骥先:男,1980年生,讲师,研究方向为分布式系统、云计算、移动计算

    谢宁:女,1991年生,硕士生,研究方向为云计算

    张学杰:男,1965 年生,教授,博士生导师,研究方向为高性能计算、可重构计算

    李伟东:男,1981年生,副教授,研究方向为组合优化和算法博弈论

    通讯作者:

    李伟东 weidong@ynu.edu.cn

  • 中图分类号: TP302

Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing

Funds: The National Natural Science Foundation of China (61472345, 61762091, 11663007), The Scientific Research Foundation of Department of Education of Yunnan Province (2017ZZX228)
  • 摘要: 使用拍卖方式来进行资源分配可以使得资源提供商获得更大的收益,是云计算领域近年来研究的重点之一。但资源分配问题是NP难的,无法在多项式时间内求解,现有研究主要通过近似算法或启发式算法来实现资源分配,但存在算法耗时长,与最优解相比准确度低的缺点。监督学习中分类及回归思想可对多维云资源分配问题进行建模和分析,针对不同问题规模,该文提出基于线性回归、逻辑回归、支持向量机的3种资源分配算法,并且基于临界值理论设计了支付价格算法,从而确保拍卖机制的可信性。在社会福利、分配准确率、算法执行时间、资源利用率等多个方面进行测试分析,取得了很好的效果。
  • 图  1  两种算法预测错误率与参数$\lambda $变化关系

    图  2  SVM-ALLOC预测错误率与参数C及$\sigma $变化关系

    图  3  3种监督学习算法的训练时间

    图  4  不同分配算法求解社会福利与预测准确率对比

    图  5  不同分配算法资源利用率对比

    表  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/JEIT170353

    ZHANG 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)
计量
  • 文章访问数:  2315
  • HTML全文浏览量:  766
  • PDF下载量:  81
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-06-13
  • 修回日期:  2018-12-24
  • 网络出版日期:  2019-01-02
  • 刊出日期:  2019-05-01

目录

    /

    返回文章
    返回