一种基于图模型的可信云资源调度算法

doi:10.6040/j.issn.1671-9352.2.2017.247

山东大学学报（理学版） ›› 2018, Vol. 53 ›› Issue (1): 63-74.doi: 10.6040/j.issn.1671-9352.2.2017.247

一种基于图模型的可信云资源调度算法

齐平^1,2, 王福成², 王必晴^1,2

1. 合肥工业大学管理学院, 安徽合肥 230039;2. 铜陵学院数学与计算机科学系, 安徽铜陵 244000

收稿日期:2017-07-04 出版日期:2018-01-20 发布日期:2018-01-19
作者简介:齐平(1981— ),男,博士,副教授,研究方向为可信计算、粒计算. E-mail: qiping929@gmail.com
基金资助:
国家自然科学基金重点资助项目(71331002);安徽省高校优秀青年骨干人才国内外访学研修项目(gxfx2017113);铜陵学院人才科研启动基金资助项目(2015tlxyrc08)

Graph model based trustworthy resource scheduling algorithm in cloud environment

1. School of Management, Hefei University of Technology, Hefei 230039, Anhui, China;
2. Department of Mathematics and Computer Science, Tongling University, Tongling 244000, Anhui, China

Received:2017-07-04 Online:2018-01-20 Published:2018-01-19

摘要/Abstract

摘要： 根据并行任务及胖树形云系统的结构特点,综合考虑了云计算环境下资源节点与通信链路的可靠性问题,构建了基于任务执行行为的云系统可靠性度量模型。提出了一种基于图的可信云资源调度模型,将云任务可信资源需求与云资源动态供给的最优匹配问题转换成最小费用最大流图的构造和求解问题。针对图的求解计算复杂度较高的问题,结合商空间理论将初始网络转化为规模较小的商网络进行求解。仿真实验结果表明,该算法能够有效提高云任务执行的成功率,降低基于图模型的资源调度算法延迟。

关键词: 最小费用最大流, 云资源调度, 图模型, 商网络

Abstract: The characteristics of the graph structure of parallel task and fat tree cloud system are analyzed. Then, by combining cloud tasks trust requirement for resource nodes together with the trust requirement for communication links, an execution-behavior based reliability measurement model is established. Then, we present a graph based trustworthy cloud resource scheduling model. It is easy to express taskstrust scheduling requirement and resource supply on a unified way, which can be transformed to a minimum cost maximum flow network construction and solution problem. Finally, in consideration of reducing computational complexity, algorithms are applied on the quotient network to approximately obtain the minimum cost flow of original network. The simulation experimental results show that the proposed algorithms can effectively improve the success rate of cloud tasks execution and significantly reduce runtime of flow network.

Key words: cloud resource scheduling, quotient network, graph based model, minimum cost maximum flow

中图分类号:

TP301.6

齐平, 王福成, 王必晴. 一种基于图模型的可信云资源调度算法[J]. 山东大学学报（理学版）, 2018, 53(1): 63-74.

参考文献

[1] ROCHWERGER B, BREITGAND D, LEVY E, et al. The reservoir model and architecture for open federated cloud computing[J]. IBM Journal of Research & Development, 2009, 53(4):535-545.
[2] BUYYA R, YEO C S, VENUGOPAL S, et al. Cloud computing and emerging IT platforms: Vision, hype and reality for delivering computing as the 5th utility[J]. Future Generation Computer Systems, 2009, 25(6):599-616.
[3] 张建华, 张文博, 徐继伟, 等. 一种基于隐马尔可夫模型的虚拟机失效恢复方法[J]. 软件学报, 2014(11):2702-2714. ZHANG Jianhua, ZHANG Wenbo, XU Jiwei, et al. Approach of virtual machine failure recovery based on hidden Markov model[J].Journal of Software, 2014(11):2702-2714.
[4] 曹洁, 曾国荪, 匡桂娟, 等.支持随机服务请求的云虚拟机按需物理资源分配方法[J].软件学报, 2017, 28(2):457-472. CAO Jie, ZENG Guosun, KUANG Guijuan, et al. An on- demand physical resource allocation method for cloud virtual machine to support random service requests[J]. Journal of Software, 2017, 28(2):457-472.
[5] DARBHA S, AGRAWAL D P, Optimal scheduling algorithm for distributed memory machines[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 9(1):87-95.
[6] ZHU D, MOSSE D, MELHEM R. Power-aware scheduling for and/or graphs in real-time systems [J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 15(9):849-864.
[7] 李青, 李勇, 涂碧波, 等. QoS保证的数据中心动态资源供应方法[J].计算机学报, 2014, 37(12):2395-2406. LI Qing, LI Yong, TU Bibo, et al. QoS-guaranteed dynamic resource provision in internet data centers[J].Chinese Journal of Computers, 2014, 37(12):2395-2406.
[8] 师雪霖, 徐恪.云虚拟机资源分配的效用最大化模型[J].计算机学报, 2013, 36(2):252-262. SHI Xuelin, XU Ke. Utility maximization model of virtual machine scheduling in cloud environment[J]. Chinese Journal of Computers, 2013, 36(2):252-262.
[9] TOPCUOGLU H, HARIRI S, WU M Y. Performance-effective and low complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 13(3):260-274.
[10] MEZMAZ M, MELAB N, KESSACI Y, et al. A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems[J]. Journal of Parallel and Distributed Computing, 2011, 71(10):1497-1508.
[11] 丁滟, 王怀民, 史佩昌, 等.可信云服务[J].计算机学报,2015,38(1):133-149. DING Yan, WANG Haiming, SHI Peichang, et al. Trusted cloud service[J]. Chinese Journal of Computers, 2015, 38(1): 133-149.
[12] WANG W, ZENG Guosun, TANG Daizhong, et al. Cloud-DLS: dynamic trusted scheduling for cloud computing[J]. Expert Systems with Applications, 2012, 39(2012): 2321-2329.
[13] 曹洁, 曾国荪, 姜火文, 等. 云环境下服务信任感知的可信动态级调度算法[J]. 通信学报, 2014,35(11):39-49. CAO Jie, ZENG Guosun, JIANG Huowen, et al. Trust-aware dynamic level scheduling algorithm in cloud environment[J].Journal on Communications, 2014, 35(11): 39-49.
[14] 曹洁,曾国荪,钮俊,等.云环境下可用性感知的并行任务调度算法[J]. 计算机研究与发展,2013, 50(7):1563-1572. CAO Jie, ZENG Guosun, NIU Jun, et al. Availability- aware scheduling method for parallel task in cloud environment[J].Journal of Computer Research and Development, 2013, 50(7):1563-1572.
[15] 王守信, 张莉, 李鹤松. 一种基于云模型的主观信任评价方法[J]. 软件学报,2010,21(6):1341-1352. WANG Shouxin, ZHANG Li, LI Hesong. Evaluation approach of subjective trust based on cloud model[J]. Journal of Software, 2010, 21(6):1341-1352.
[16] 唐文,陈钟.基于模糊集合理论的主观信任管理模型研究[J]. 软件学报,2003,14(8):1401-1408. TANG Wen, CHEN Zhong. Research of subjective trust management model based on the fuzzy set theory[J]. Journal of Software, 2003, 14(8):1401-1408.
[17] 罗俊海,范明钰.基于置信度的MANETs主观信任管理模型[J]. 计算机研究与发展,2013,47(3):516-523. LUO Junhai, FAN Mingyu. A subjective trust management model based on certainty-factor for MANETs[J]. Journal of Computer Research and Development, 2013, 47(3):516-523.
[18] 邓晓衡,卢锡成,王怀民.iVCE中基于可信评价的资源调度研究[J]. 计算机学报, 2017,30(10):1750-1762. DENG Xiaoheng, LU Xicheng, WANG Haimin. Study on trust evaluation based resource scheduling in iVCE[J]. Chinese Journal of Computers, 2017,30(10):1750-1762.
[19] ABAWAJY J. Determining service trustworthiness in intercloud computing environments[C] //Proceedings of 2009 10th International Symposium on Pervasive Systems, Algorithms and Networks. New York: IEEE, 2009:784-788.
[20] RAGHEBI Z, HASHEMI M R. A new trust evaluation method based on reliability of customer feedback for cloud computing[C] // International ISC Conference on Information Security and Cryptology. New York: IEEE, 2013:1-6.
[21] LI X, DU J. Adaptive and attribute-based trust model for service-level agreement guarantee in cloud computing[J].IET Information Security, 2013, 7(1): 39-50.
[22] FAN W, YANG S, PEI J. A novel two-stage model for cloud service trustworthiness evaluation[J]. Expert Systems, 2014, 31(2): 136-153.
[23] 田冠华,孟丹,詹剑锋.云计算环境下基于失效规则的资源动态提供策略[J]. 计算机学报,2010,33(10):1859-1872. TIAN Guanhua, MENG Dan, ZHAN Jianfeng. Reliable resource provision policy for cloud computing[J]. Chinese Journal of Computers, 2010, 33(10):1859-1872.
[24] ISARD M, PRABHAKARAN V, CURRY J, et al. Quincy: fair scheduling for distributed computing clusters[C] //ACM Sigops, Symposium on Operating Systems Principles. New York: ACM, 2009: 261-276.
[25] 匡桂娟,曾国荪,曹洁,等.基于图匹配理论的云任务与云资源满意“婚配”方法[J]. 电子学报,2014,42(8):1582-1886. KUANG Guijuan, ZENG Guosun, CAO Jie. Satisfactory marriage method between cloud tasks and resources based on graph theory[J]. Acta Electronica Sinica, 2014, 42(8): 1582-1886.
[26] YAGER R. On the entropy of fuzzy measures[J]. IEEE Transactions on Fuzzy Systems,2000,8(4):453-461.
[27] 陈晓旭,吴恒,吴悦文等.基于最小费用最大流的大规模资源调度方法[J]. 软件学报,2017,28(3):598-610. CHEN Xiaoxu, WU Heng, WU Yuewen, et al. Sirius: large-scale resource scheduling based on minimum cost maximum flow[J].Journal of Software, 2017, 28(3):598-610.
[28] RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E Statistical Nonlinear &Soft Matter Physics, 2007, 76(3): 36-106.
[29] CALHEIROS R N, RANJAN R, ROSE C A F, et al. Cloudsim:a novel framework for modeling and simulation of cloud computing infrastructures and services[J/OL]. Computer Science, 2009. http://www.doc88.com/p-514938859172.html
[30] TOPCUOUGLU H, HARIRI S, Wu M Y. Performance-effective and low complexity task scheduling for heterogeneous computing[J]. IEEE Transaction on Parallel Distribution System, 2002, 13(3):260-274.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

一种基于图模型的可信云资源调度算法

Graph model based trustworthy resource scheduling algorithm in cloud environment

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

多维度评价

本文评价

推荐阅读 0