高级搜索

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

张骥先 谢宁 张学杰 李伟东

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

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

    作者简介: 张骥先: 男,1980年生,讲师,研究方向为分布式系统、云计算、移动计算;
    谢宁: 女,1991年生,硕士生,研究方向为云计算;
    张学杰: 男,1965年生,教授,博士生导师,研究方向为高性能计算、可重构计算;
    李伟东: 男,1981年生,副教授,研究方向为组合优化和算法博弈论
    通讯作者: 李伟东,weidong@ynu.edu.cn
  • 基金项目: 国家自然科学基金项目(61472345, 61762091, 11663007),云南省教育厅科学研究基金项目(2017ZZX228)

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

English

    1. [1]

      NISAN T, ROUGHGARDEN T, TARDOS E, et al. Algorithmic Game Theory[M]. Cambridge: Cambridge Univ. Press, 2007: 218–233.

    2. [2]

      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

    3. [3]

      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

    4. [4]

      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

    5. [5]

      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

    6. [6]

      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.

    7. [7]

      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.

    8. [8]

      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

    9. [9]

      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

    10. [10]

      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

    11. [11]

      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

    12. [12]

      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.

    13. [13]

      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

    14. [14]

      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

    15. [15]

      张骥先, 谢宁, 李伟东, 等. 一种支持云计算虚拟资源分配的可信多需求拍卖机制[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

    16. [16]

      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

    17. [17]

      Grid Workloads Archives[OL]. http://gwa.ewi.tudelft.nl,2018.2.

    1. [1]

      陈前斌, 管令进, 李子煜, 王兆堃, 杨恒, 唐伦. 基于深度强化学习的异构云无线接入网自适应无线资源分配算法. 电子与信息学报, 2020, 42(6): 1468-1477.

    2. [2]

      唐伦, 肖娇, 魏延南, 赵国繁, 陈前斌. 基于云雾混合计算的车联网联合资源分配算法. 电子与信息学报, 2020, 42(0): 1-8.

    3. [3]

      陈前斌, 谭颀, 魏延南, 贺兰钦, 唐伦. 异构云无线接入网架构下面向混合能源供应的动态资源分配及能源管理算法. 电子与信息学报, 2020, 42(6): 1428-1435.

    4. [4]

      唐伦, 魏延南, 谭颀, 唐睿, 陈前斌. H-CRAN网络下联合拥塞控制和资源分配的网络切片动态资源调度策略. 电子与信息学报, 2020, 42(5): 1244-1252.

    5. [5]

      邵鸿翔, 孙有铭, 蔡佶昊. 面向用户体验的多小区混合非正交多址接入网络资源分配方法. 电子与信息学报, 2020, 42(0): 1-8.

    6. [6]

      高东, 梁子林. 基于能量效率的双层非正交多址系统资源优化算法. 电子与信息学报, 2020, 42(5): 1237-1243.

    7. [7]

      彭海英, 王泽东, 吴大鹏. 带有卸载压缩激励的云增强FiWi网络节能机制. 电子与信息学报, 2020, 42(7): 1726-1733.

    8. [8]

      陈容, 陈岚, WAHLAArfan Haider. 基于公式递推法的可变计算位宽的循环冗余校验设计与实现. 电子与信息学报, 2020, 42(5): 1261-1267.

    9. [9]

      陈卓, 冯钢, 何颖, 周杨. 运营商网络中基于深度强化学习的服务功能链迁移机制. 电子与信息学报, 2020, 42(0): 1-7.

    10. [10]

      曾菊玲, 张春雷, 蒋砺思, 夏凌. 基于信道定价的无线虚拟网络资源分配策略:匹配/Stackelberg分层博弈. 电子与信息学报, 2020, 41(0): 0-7.

    11. [11]

      刘焕淋, 杜理想, 陈勇, 胡会霞. 串扰感知的空分弹性光网络频谱转换器稀疏配置和资源分配方法. 电子与信息学报, 2020, 42(7): 1718-1725.

    12. [12]

      刘通, 唐伦, 何小强, 陈前斌. 融合区块链与雾计算系统中基于网络时延和资源管理的优化任务卸载方案. 电子与信息学报, 2020, 42(0): 1-6.

    13. [13]

      王君珂, 印珏, 牛人杰, 任少康, 晁洁. DNA计算与DNA纳米技术. 电子与信息学报, 2020, 42(6): 1313-1325.

    14. [14]

      陈勇, 刘曦, 刘焕淋. 基于特征通道和空间联合注意机制的遮挡行人检测方法. 电子与信息学报, 2020, 42(6): 1486-1493.

    15. [15]

      殷志祥, 唐震, 张强, 崔建中, 杨静, 王日晟, 赵寿为, 张居丽. 基于DNA折纸基底的与非门计算模型. 电子与信息学报, 2020, 42(6): 1355-1364.

    16. [16]

      左志斌, 常朝稳, 祝现威. 一种基于数据平面可编程的软件定义网络报文转发验证机制. 电子与信息学报, 2020, 42(5): 1110-1117.

    17. [17]

      夏士超, 姚枝秀, 鲜永菊, 李云. 移动边缘计算中分布式异构任务卸载算法. 电子与信息学报, 2020, 41(0): 1-8.

    18. [18]

      张凯, 陈彬, 许志伟. 基于多目标进化策略算法的DNA核酸编码设计. 电子与信息学报, 2020, 42(6): 1365-1373.

    19. [19]

      柳娟, 谢文彬, 汪改英, 汤敏丽. 基于DNA和限制性核酸内切酶的基本逻辑门设计. 电子与信息学报, 2020, 42(6): 1332-1339.

    20. [20]

      刘汝卿, 蒋衍, 姜成昊, 李锋, 朱精果. 应用于激光雷达信号处理系统的放大电路接口设计. 电子与信息学报, 2020, 42(7): 1636-1642.

  • 图 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
  • 加载中
图(5)表(1)
计量
  • PDF下载量:  54
  • 文章访问数:  626
  • HTML全文浏览量:  261
文章相关
  • 通讯作者:  李伟东, weidong@ynu.edu.cn
  • 收稿日期:  2018-06-13
  • 录用日期:  2018-12-24
  • 网络出版日期:  2019-01-02
  • 刊出日期:  2019-05-01
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

/

返回文章