基于图匹配理论的云任务与云资源满意“婚配”方法

doi:10.3969/j.issn.0372-2112.2014.08.019

电子学报 ›› 2014, Vol. 42 ›› Issue (8): 1582-1586.DOI: 10.3969/j.issn.0372-2112.2014.08.019

基于图匹配理论的云任务与云资源满意“婚配”方法

匡桂娟^1,2,3, 曾国荪^1,3, 曹洁^1,3, 熊焕亮^1,3,4

1. 同济大学计算机科学与技术系, 上海 201804;
2. 青岛农业大学理学与信息学院, 山东青岛 266109;
3. 国家高性能计算机工程技术中心同济分中心, 上海 201804;
4. 江西农业大学软件学院, 江西南昌 330045

收稿日期:2013-11-26 修回日期:2014-03-20 出版日期:2014-08-25
- 作者简介:
- 匡桂娟女，1972年生于山东青岛.同济大学电子与信息学院博士.研究方向为分布式计算、云计算.E-mail：1gjkuang@tongji.edu.cn；曾国荪男，1964年生于江西，博士，教授，博导，研究方向为异构计算、并行计算、信息安全.E-mail：gszeng@tongji.edu.cn
- 基金资助:
- 国家863高技术研究发展计划 (No.2009AA012201）; 国家自然基金 (No.61272107，No.61202173，No.61103068）; 上海市优秀学科带头人计划 (No.10XD1404400）; 教育部网络时代的科技论文共享专项研究课题 (No.20110740001）; 华为创新计划研究项目 (No.IRP-2013-12-03）

Satisfactory Marriage Method Between Cloud Tasks and Resources Based on Graph Theory

KUANG Gui-juan^1,2,3, ZENG Guo-sun^1,3, CAO Jie^1,3, XIONG Huan-liang^1,3,4

1. Department of Computer Science and Technology, Tongji University, Shanghai 201804, China;
2. School of Science and Information Science, Qingdao Agricultural University, Qingdao, Shandong 266109, China;
3. Tongji Branch, National Engineering & Technology Center of High Performance Computer, Shanghai 201804, China;
4. Software College, Jiangxi Agricultural University, Nanchang, Jiangxi 330045, China

Received:2013-11-26 Revised:2014-03-20 Online:2014-08-25 Published:2014-08-25
- Supported by:
- National High-tech R&D Program of China (863 Program) (No.2009AA012201); National Natural Science Foundation of China (No.61272107, No.61202173, No.61103068); Excellent Academic Leade Program of Shanghai Municipal (No.10XD1404400); Research Project of Science and Technology Paper Sharing in the Network Age of Ministry of Education (No.20110740001); Huawei Innovation Research Project (No.IRP-2013-12-03)

摘要/Abstract

摘要：

目前的云资源管理策略多从云资源提供商的角度出发，而资源使用方的资源偏好考虑很少.本文开展满足云任务与云资源双方偏好的满意婚配资源管理方法研究.根据用户任务的资源请求，以及资源提供商的资源管理策略，关注一方对另一方的偏好程度，依据偏好计算双方对资源配置的双方综合满意度，建立资源满意婚配图模型，运用图匹配理论证明了资源满意婚配的存在性，并给出最大满意度资源分配方案.最后通过实验测试所提出方法的有效性.

关键词: 云计算, 资源管理, 双方偏好, 综合满意度, 满意婚配模型

Abstract:

In cloud computing system,most of the existing cloud resource management methods are developed for the resource providers,while few for the users.This paper proposed a satisfactory marriage method between the cloud tasks and resources to meet the preferences of the resource user as well as the provider fairly.The user's requirement of cloud resources and the cloud provider's resource management strategies are extracted as their preferences to the other side.Then,the both-side satisfactions of a resource allocation are calculated.The cloud system resource management system is modeled as a weighted bipartite graph.The existence of the satisfactory marriage scheme is proved and an algorithm is developed based on graph theory to get it.The experiment results demonstrate that our method is valid.

Key words: cloud computing, resource management, two-sides preference, comprehensive satisfaction degree, satisfactory marriage model

中图分类号:

TP338

匡桂娟, 曾国荪, 曹洁, 等. 基于图匹配理论的云任务与云资源满意“婚配”方法[J]. 电子学报, 2014, 42(8): 1582-1586.

KUANG Gui-juan, ZENG Guo-sun, CAO Jie, et al. Satisfactory Marriage Method Between Cloud Tasks and Resources Based on Graph Theory[J]. Acta Electronica Sinica, 2014, 42(8): 1582-1586.

参考文献

[1] M Armbrust,A Fox,R Griffith,et al.Above the clouds:A Berkeley view of cloud computing[R].Dept Electrical Eng and Comput Sciences,University of California,Berkeley,Rep UCB/EECS-2009-28,2009.
[2] 师雪霖,徐恪.云虚拟机资源分配的效用最大化模型[J].计算机学报,2013,36(2):252-261. Shi Xuelin,Xu Ke.Utility maximization model of virtual machine scheduling in cloud environment[J].Chinese Journal of Computer,2013,36(2):252-261.(in Chinese)
[3] X Meng,C Isci,J Kephart,et al.Efficient resource provisioning in compute clouds via vm multiplexing[A].Proceedings of the 7th International Conference on Autonomoc Computing[C].New York:ACM,2010.11-20.
[4] 谭一鸣,曾国荪,王伟.随机任务在云计算平台中能耗的优化管理方法[J].软件学报,2012,23(2):266-278. Tan Yiming,Zeng Guosun,Wang Wei.Policy of energy optimal management for cloud computing platform with stochastic tasks[J].Chinese Journal of Software,2012,23(2):266-278.(in Chinese)
[5] [JP3]李强,郝沁汾,肖利民,等.云计算中虚拟机放置的自适应管理与多目标优化[J].计算机学报,2011,34(12):2253-2264. Li Qiang,Hao Qinfen,Xiao Limin,et al.Adaptive management and multi-objective optimization for virtual machine placement in cloud computing[J].Chinese Journal of Computers,2011,34(12):2253-2264.(in Chinese)
[6] 徐猛,崔立真,李庆忠.基于扩展图规划的Top-K服务组合方法研究[J].电子学报,2012,40(7):1404-1409. Xu Meng,Cui lizhen,Li Qingzhong.An extended graph-planning based top-K service composition method[J].Acta Electronica Sinica,2012,40(7):1404-1409.(in Chinese)
[7] 孙大为,常桂然,李凤云,等.一种基于免疫克隆的偏好多维QoS云资源调度优化算法[J].电子学报,2011,39(8):1824-1831. Sun Dawei,Chang Guiran,Li Fengyun,et al.Optimizing multi-dimensionalQoS cloud resource scheduling by immune clonal with preference[J].Acta Electronica Sinica,2011,39(8):1824-1831.(in Chinese)
[8] H Xu,BC Li.Anchor:A Versatile and efficient framework for resource management in the cloud[J].IEEE Transtractions on Parallel and Distributed Systems,2013,24(6):1066-1076.
[9] D Gale,LS Shapley.College admissions and the stability of marriage[J].Am Math,1962,69(1):9-15.
[10] 李铭洋,樊治平,刘洋.一种基于偏好序信息的双边匹配方法[J].运筹与管理,2012,21(4):113-119. Li Mingyang,Fan Zhiping,Liu Yang.A method for two-sided matching based on preference ordinal information[J].Operations Research and Management Science,2012,21(4):113-119.(in CHinese)
[11] 王树禾.图论[M].北京:科学出版社,2009.67-82. Wang Shuhe.Graph Theory[M].Beijing:Science Press,2009.67-82.(in Chinese)
[12] R N Calheiros,R Ranjan,CAF D Rose,et al.CloudSim:A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[J].Software:Practice and Experience,2011,41(1):23-50.

[1]	赵开强, 康萍, 刘彬, 郭真, 冯朝胜, 卿昱. 支持云代理重加密的CP-ABE方案[J]. 电子学报, 2023, 51(3): 728-735.
[2]	郑涛, 蒙祖尧, 张宏科. 基于多信道绑定的应急终端协同方法[J]. 电子学报, 2022, 50(11): 2645-2652.
[3]	刘雷, 陈晨, 冯杰, 肖婷婷, 裴庆祺. 车载边缘计算卸载技术研究综述[J]. 电子学报, 2021, 49(5): 861-871.
[4]	陈亮, 李峰, 任保全, 杨建喜. 软件定义物联网研究综述[J]. 电子学报, 2021, 49(5): 1019-1032.
[5]	罗智勇, 朱梓豪, 谢志强, 孙广路. 面向云计算的花朵差分授粉工作流多目标优化算法研究[J]. 电子学报, 2021, 49(3): 470-476.
[6]	李航, 冯朝胜, 刘帅南, 刘彬, 赵开强. 支持离线/在线加密及可验证外包解密的CP-WABE方案[J]. 电子学报, 2020, 48(11): 2146-2153.
[7]	罗睿辞, 叶蔚, 刘学洋, 孙基男, 张世琨. 基于拥塞博弈的微服务运行时资源管理方法[J]. 电子学报, 2019, 47(7): 1497-1505.
[8]	卢晶, 段勇, 刘海波. 基于z值的分布式密度峰值聚类算法[J]. 电子学报, 2018, 46(3): 730-738.
[9]	王于丁, 杨家海. DACPCC:一种包含访问权限的云计算数据访问控制方案[J]. 电子学报, 2018, 46(1): 236-244.
[10]	丁嘉宁, 张鹏, 杨嵘, 刘俊朋, 刘庆云, 熊刚. 支持多租户的网络测试床模拟流量标记和溯源模型[J]. 电子学报, 2017, 45(8): 1947-1956.
[11]	杜思军, 徐尚书, 刘俊南, 张俊伟, 马建峰. 云计算中抗共谋攻击的数据位置验证协议[J]. 电子学报, 2017, 45(6): 1321-1326.
[12]	陈振华, 李顺东, 王道顺, 黄琼, 张卫国. 集合成员关系的安全多方计算及其应用[J]. 电子学报, 2017, 45(5): 1109-1116.
[13]	李焱, 郑亚松, 李婧, 朱春鸽, 刘欣然. 云环境下面向跨域作业的调度方法[J]. 电子学报, 2017, 45(10): 2416-2424.
[14]	陶晓玲, 韦毅, 王勇. 一种基于分层多代理的云计算负载均衡方法[J]. 电子学报, 2016, 44(9): 2106-2113.
[15]	陈凯, 许海铭, 徐震, 林东岱, 刘勇. 适用于移动云计算的抗中间人攻击的SSP方案[J]. 电子学报, 2016, 44(8): 1806-1813.

基于图匹配理论的云任务与云资源满意“婚配”方法

Satisfactory Marriage Method Between Cloud Tasks and Resources Based on Graph Theory

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics