基于監(jiān)督學習的可信云計算資源拍賣機制研究
doi: 10.11999/JEIT180587
-
1.
云南大學信息學院 ??昆明 ??650500
-
2.
云南大學數(shù)學與統(tǒng)計學院 ??昆明 ??650500
基金項目: 國家自然科學基金(61472345, 61762091, 11663007)，云南省教育廳科學研究基金(2017ZZX228)
Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing
-
1.
School of Information Science and Engineering, Yunnan University, Kunming 650500, China
-
2.
School of Mathematics and Statistics, Yunnan University, Kunming 650500, China
Funds: The National Natural Science Foundation of China (61472345, 61762091, 11663007), The Scientific Research Foundation of Department of Education of Yunnan Province (2017ZZX228)
-
摘要: 使用拍賣方式來進行資源分配可以使得資源提供商獲得更大的收益，是云計算領(lǐng)域近年來研究的重點之一。但資源分配問題是NP難的，無法在多項式時間內(nèi)求解，現(xiàn)有研究主要通過近似算法或啟發(fā)式算法來實現(xiàn)資源分配，但存在算法耗時長，與最優(yōu)解相比準確度低的缺點。監(jiān)督學習中分類及回歸思想可對多維云資源分配問題進行建模和分析，針對不同問題規(guī)模，該文提出基于線性回歸、邏輯回歸、支持向量機的3種資源分配算法，并且基于臨界值理論設(shè)計了支付價格算法，從而確保拍賣機制的可信性。在社會福利、分配準確率、算法執(zhí)行時間、資源利用率等多個方面進行測試分析，取得了很好的效果。
-
關(guān)鍵詞:
- 云計算 /
- 資源分配 /
- 機制設(shè)計 /
- 監(jiān)督學習
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)}\} $ 監(jiān)督學習算法對資源分配的預(yù)測結(jié)果：
${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)
計量
- 文章訪問數(shù): 2373
- HTML全文瀏覽量: 787
- PDF下載量: 81
- 被引次數(shù): 0
下載:
