基于監(jiān)督學(xué)習(xí)的可信云計(jì)算資源拍賣機(jī)制研究
doi: 10.11999/JEIT180587 cstr: 32379.14.JEIT180587
-
1.
云南大學(xué)信息學(xué)院 ??昆明 ??650500
-
2.
云南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院 ??昆明 ??650500
基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61472345, 61762091, 11663007)，云南省教育廳科學(xué)研究基金(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ái)進(jìn)行資源分配可以使得資源提供商獲得更大的收益，是云計(jì)算領(lǐng)域近年來(lái)研究的重點(diǎn)之一。但資源分配問題是NP難的，無(wú)法在多項(xiàng)式時(shí)間內(nèi)求解，現(xiàn)有研究主要通過近似算法或啟發(fā)式算法來(lái)實(shí)現(xiàn)資源分配，但存在算法耗時(shí)長(zhǎng)，與最優(yōu)解相比準(zhǔn)確度低的缺點(diǎn)。監(jiān)督學(xué)習(xí)中分類及回歸思想可對(duì)多維云資源分配問題進(jìn)行建模和分析，針對(duì)不同問題規(guī)模，該文提出基于線性回歸、邏輯回歸、支持向量機(jī)的3種資源分配算法，并且基于臨界值理論設(shè)計(jì)了支付價(jià)格算法，從而確保拍賣機(jī)制的可信性。在社會(huì)福利、分配準(zhǔn)確率、算法執(zhí)行時(shí)間、資源利用率等多個(gè)方面進(jìn)行測(cè)試分析，取得了很好的效果。
-
關(guān)鍵詞:
- 云計(jì)算 /
- 資源分配 /
- 機(jī)制設(shè)計(jì) /
- 監(jiān)督學(xué)習(xí)
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 基于臨界值的價(jià)格計(jì)算算法(CV-PAY)
輸入 所有用戶的需求信息集：${R} = \{ R_{}^{(1)}\,R_{}^{(2)}\, ·\!·\!· \,R_{}^{(m)}\} $ 監(jiān)督學(xué)習(xí)算法對(duì)資源分配的預(yù)測(cè)結(jié)果：
${PD} = ({\rm{pd}}_{}^{(1)}\,{\rm{pd}}_{}^{(2)}\, ·\!·\!· \,{\rm{pd}}_{}^{(m)})$每類虛擬資源的容量：${C} = ({c_1}\;\;\;{c_2}\;\;\; ·\!·\!· \;\;\;{c_n})$ 輸出 被選中的用戶需要支付的價(jià)格，
${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) 運(yùn)行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}$ 
下載: 導(dǎo)出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 張?bào)K先, 謝寧, 李偉東, 等. 一種支持云計(jì)算虛擬資源分配的可信多需求拍賣機(jī)制[J]. 電子與信息學(xué)報(bào), 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)
計(jì)量
- 文章訪問數(shù): 2428
- HTML全文瀏覽量: 805
- PDF下載量: 83
- 被引次數(shù): 0
下載:
