高级搜索

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

张骥先 谢宁 张学杰 李伟东

引用本文: 张骥先, 谢宁, 张学杰, 李伟东. 基于监督学习的可信云计算资源拍卖机制研究[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]

      王汝言, 徐宁宁, 吴大鹏. 能耗和时延感知的虚拟化云无线接入网络资源分配机制. 电子与信息学报, 2019, 41(1): 83-90.

    2. [2]

      代美玲, 刘周斌, 郭少勇, 邵苏杰, 邱雪松. 基于终端能耗和系统时延最小化的边缘计算卸载及资源分配机制. 电子与信息学报, 2019, 41(11): 2684-2690.

    3. [3]

      唐伦, 魏延南, 马润琳, 贺小雨, 陈前斌. 虚拟化云无线接入网络下基于在线学习的网络切片虚拟资源分配算法. 电子与信息学报, 2019, 41(7): 1533-1539.

    4. [4]

      张达敏, 张绘娟, 闫威, 陈忠云, 辛梓芸. 异构网络中基于能效优化的D2D资源分配机制. 电子与信息学报, 2019, 41(0): 1-9.

    5. [5]

      张海波, 李虎, 陈善学, 贺晓帆. 超密集网络中基于移动边缘计算的任务卸载和资源优化. 电子与信息学报, 2019, 41(5): 1194-1201.

    6. [6]

      王汝言, 梁颖杰, 崔亚平. 车辆网络多平台卸载智能资源分配算法. 电子与信息学报, 2019, 41(0): 1-8.

    7. [7]

      王汝言, 李宏娟, 吴大鹏. 基于Stackelberg博弈的虚拟化无线传感网络资源分配策略. 电子与信息学报, 2019, 41(2): 377-384.

    8. [8]

      梁靓, 武彦飞, 冯钢. 基于在线拍卖的网络切片资源分配算法. 电子与信息学报, 2019, 41(5): 1187-1193.

    9. [9]

      熊余, 杨娅娅, 张振振, 蒋婧. 软件定义时分波分复用无源光网络中基于带宽预测的资源分配策略. 电子与信息学报, 2019, 41(8): 1885-1892.

    10. [10]

      唐伦, 杨希希, 施颖洁, 陈前斌. 无线虚拟网络中基于自回归滑动平均预测的在线自适应虚拟资源分配算法. 电子与信息学报, 2019, 41(1): 16-23.

    11. [11]

      崔苗, 喻鑫, 李学易, 张广驰, 刘怡俊. 多用户多载波无线携能通信系统的上下行联合资源分配. 电子与信息学报, 2019, 41(6): 1359-1364.

    12. [12]

      唐伦, 周钰, 谭颀, 魏延南, 陈前斌. 基于强化学习的5G网络切片虚拟网络功能迁移算法. 电子与信息学报, 2019, 41(0): 1-9.

    13. [13]

      王汝言, 李宏娟, 吴大鹏, 李红霞. 基于半马尔科夫决策过程的虚拟传感网络资源分配策略. 电子与信息学报, 2019, 41(0): 1-8.

    14. [14]

      唐伦, 马润琳, 杨恒, 陈前斌. 基于非正交多址接入的网络切片联合用户关联和功率分配算法. 电子与信息学报, 2019, 41(9): 2039-2046.

    15. [15]

      唐伦, 周钰, 杨友超, 赵国繁, 陈前斌. 5G网络切片场景中基于预测的虚拟网络功能动态部署算法. 电子与信息学报, 2019, 41(9): 2071-2078.

    16. [16]

      李世宝, 王升志, 刘建航, 黄庭培, 张鑫. 基于接收信号强度非齐性分布特征的半监督学习室内定位指纹库构建. 电子与信息学报, 2019, 41(10): 2302-2309.

    17. [17]

      邹虹, 高毅爽, 闫俊杰. 带有卸载时延感知的边缘云增强FiWi网络节能机制. 电子与信息学报, 2019, 41(2): 394-401.

    18. [18]

      孙远, 李春国, 黄永明, 杨绿溪. 基于带缓存的云接入网络最优能效设计. 电子与信息学报, 2019, 41(7): 1525-1532.

    19. [19]

      胡宇翔, 李子勇, 胡宗魁, 胡涛. 基于流量工程的软件定义网络控制资源优化机制. 电子与信息学报, 2019, 41(0): 1-8.

    20. [20]

      陈容, 陈岚, WAHLAArfan Haider. 基于公式递推法的可变计算位宽的CRC设计与实现. 电子与信息学报, 2019, 41(0): 1-7.

  • 图 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下载量:  41
  • 文章访问数:  365
  • HTML全文浏览量:  168
文章相关
  • 通讯作者:  李伟东, 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搜索

/

返回文章