广西师范大学学报(自然科学版) ›› 2024, Vol. 42 ›› Issue (2): 94-104.doi: 10.16088/j.issn.1001-6600.2023041602

• • 上一篇    下一篇

云资源调度的回答集程序描述性求解

王卫舵1,2, 王以松1,2*, 杨磊1,2   

  1. 1.公共大数据国家重点实验室(贵州大学), 贵州 贵阳 550025;
    2.贵州大学 人工智能研究院, 贵州 贵阳 550025
  • 收稿日期:2023-04-16 修回日期:2023-09-17 发布日期:2024-04-22
  • 通讯作者: 王以松(1975—), 男(土家族), 贵州思南人, 贵州大学教授, 博士。 E-mail: yswang@gzu.edu.cn
  • 基金资助:
    国家自然科学基金(61976065)

Descriptive Solution of the Answer Set Programming for Cloud Resource Scheduling

WANG Weiduo1,2, WANG Yisong1,2*, YANG Lei1,2   

  1. 1. State Key Laboratory of Public Big Data (Guizhou University), Guiyang Guizhou 550025, China;
    2. Institute of Artificial Intelligence, Guizhou University, Guiyang Guizhou 550025, China
  • Received:2023-04-16 Revised:2023-09-17 Published:2024-04-22

摘要: 针对求解难度为NP完全的基础设施即服务(IaaS)模式云资源调度问题,本文提出一种基于回答集程序(ASP)的描述性优化求解方法,并对其正确性进行分析。首先,把满足虚拟机CPU使用的情况下关闭尽可能多的主机做为减少云平台能耗的方法,将云资源调度问题形式化表述;其次,结合形式化描述以及减少云平台能耗的策略,将云资源调度问题用ASP编码为描述性(优化)问题,并分析其正确性;最后,在公开的PlanetLab数据集上进行实验,结果显示,ASP方法可在保障服务质量的同时减少集群能耗,最高可节能13%以上。这表明ASP方法在云资源调度问题上是有效的,从而提供一种易理解、易修改并能充分利用ASP最新工具成果的有效云资源调度新方法。

关键词: 回答集程序, 云资源调度, 多目标优化, 约束满足问题, 能耗

Abstract: Aiming at solving the NP-complete IaaS model cloud resource scheduling problem, an optimal solution method based on answer set program is proposed, and its correctness is analyzed. First of all, it is determined that the way to reduce the energy consumption of the cloud platform is to shut down as many hosts as possible while satisfying the CPU usage of the virtual machine, and formulated the cloud resource scheduling problem. Secondly, combined with the formal description and the strategy of reducing the energy consumption of the cloud platform, the cloud resource scheduling problem is coded as a descriptive (optimization) problem with ASP, and its correctness is analyzed. Finally, the experiment is carried out on the public PlanetLab data set. The experimental results show that the ASP method can not only guarantee the quality of service but also reduce the energy consumption of the cluster, which can save more than 13% of the energy. This shows that ASP method is effective in cloud resource scheduling, and provides a new effective cloud resource scheduling method that is easy to understand, easy to modify and can make full use of the latest ASP tools.

Key words: answer set programming, cloud resource scheduling, multi-objective optimization, constraint satisfaction problem, energy consumption

中图分类号:  TP393.09

[1] CANIOU Y, CARON E, CHANG A K W,et al. Budget-aware scheduling algorithms for scientific workflows with stochastic task weights on infrastructure as a service cloud platforms[J]. Concurrency and Computation: Practice and Experience, 2021, 33(17): 1-21. DOI: 10.1002/cpe.6065.
[2] VELPULA P, PAMULA R. CEECP: CT-based enhanced e-clinical pathways in terms of processing time to enable big data analytics in healthcare along with cloud computing[J]. Computers & Industrial Engineering, 2022, 168: 108037. DOI: 10.1016/j.cie.2022.108037.
[3] 师亮, 温亮明, 雷声, 等. 基于决策树和由均匀分布改进Q学习的虚拟机整合算法[J]. 计算机科学, 2023, 50(6): 36-44. DOI: 10.11896/jsjkx.220300192.
[4] BELOGLAZOV A, BUYYA R. Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers[J]. Concurrency and Computation: Practice and Experience, 2012, 24(13): 1397-1420. DOI: 10.1002/cpe.1867.
[5] 刘开南. 云数据中心基于贪心算法的虚拟机迁移策略[J]. 计算机应用, 2019, 39(11): 3333-3338. DOI: 10.11772/j.issn.1001-9081.2019040598.
[6] CHENG S, CAO C, YU P, et al. SLA-Aware andgreen resource management of IaaS clouds[C]// HPCC-SmartCity-DSS 2016. Los Alamitos, CA: IEEE Computer Society, 2016: 457-464. DOI: 10.1109/HPCC- SmartCity-DSS.2016.0072.
[7] 李双刚, 张爽, 王兴伟. 基于自适应虚拟机迁移的云资源调度机制[J]. 计算机科学, 2020, 47(9): 238-245. DOI: 10.11896/jsjkx.190900189.
[8] 杨翎, 姜春茂. 基于三支决策的虚拟机节能迁移策略[J]. 计算机应用, 2021, 41(4): 990-998. DOI: 10.11772/j.issn.1001-9081.2020081294.
[9] RANA N, LATIFF M S A, ABDULHAMID S M, et al. A hybrid whale optimization algorithm with differential evolution optimization for multi-objective virtual machine scheduling in cloud computing[J]. Engineering Optimization, 2022, 54(12): 1999-2016. DOI: 10.1080/0305215X.2021.1969560.
[10] KHELIFA A, HAMROUNI T, MOKADEM R,et al. Combining task scheduling and data replication for SLA compliance and enhancement of provider profit in clouds[J]. Applied Intelligence, 2022, 51(10): 7494-7516. DOI: 10.1007/s10489-021-02267-9.
[11] 徐珩僭, 王以松, 冯仁艳. 一种用于Slater与Kemeny选举求解的ASP方法[J]. 计算机工程, 2019, 45(9): 198-203. DOI: 10.19678/j.issn.1000-3428.0052139.
[12] 杨东, 王以松. 析取回答集程序设计结构化测试方法[J]. 计算机应用, 2023, 43(1): 215-220. DOI: 10.11772/j.issn.1001-9081.2021111891.
[13] MOCHI M. Planning and scheduling in digital health with answer set programming[J]. Electronic Proceedings in Theoretical Computer Science, 2022, 364: 228-235. DOI: 10.4204/EPTCS.364.38.
[14] DODARO C, GALATÀ G, KHAN M K,et al. Operating room (re)scheduling with bed management via ASP[J]. Theory and Practice of Logic Programming, 2022, 22(2): 229-253. DOI: 10.1017/S1471068421000090.
[15] ABELS D, JORDI J, OSTROWSKI M, et al. Train scheduling with hybrid answer set programming[J]. Theory and Practice of Logic Programming, 2021, 21(3): 317-347. DOI: 10.1017/S1471068420000046.
[16] ALI R, EL-KHOLANY M M S, GEBSER M. Flexible job-shop scheduling for semiconductor manufacturing with hybrid answer set programming[C]// Practical Aspects of Declarative Languages: LNCS Volume 13880. Cham: Springer Nature Switzerland AG, 2023: 85-95. DOI: 10.1007/978-3-031-24841-2_6.
[17] BELADY C L. In the data center, power and cooling costs more than the IT equipment it supports[J]. Electronics cooling, 2007, 13(1): 24.
[18] BUYYA R, BELOGLAZOV A, ABAWAJY J H. Energy-efficient management of data center resources for cloud computing: a vision, architectural elements, and open challenges[EB/OL].(2010-06-02)[2023-04-16]. https://arxiv.org/abs/1006.0308. DOI: 10.48550/arXiv.1006.0308.
[19] 朱喆. 回答集编程在RoboCup中型组的应用[J]. 信息通信, 2014(10): 104-105. DOI: 10.3969/j.issn.1673-1131.2014.10.062.
[20] GELFOND M, LIFSCHITZ V. The stable model semantics for logic programming[C]// Proceedings of International Logic Programming Conference and Symposium. Cambridge, MA: MIT Press, 1988: 1070-1080.
[21] 王淑庆. 基于ASP逻辑的偏好多语境系统[J]. 湖北大学学报(哲学社会科学版), 2014, 41(5): 44-49. DOI: 10.13793/j.cnki.42-1020/c.2014.05.010.
[22] HAVUR G, CABANILLAS C, POLLERES A. Benchmarking answer set programming systems for resource allocation in business processes[J]. Expert Systems with Applications, 2022, 205: 117599. DOI: 10.1016/j.eswa.2022.117599.
[23] 谢小天, 赵岭忠. 基于逻辑程序的调机路径规划研究[J]. 计算机工程, 2018, 44(1): 98-103. DOI: 10.3969/j.issn. 1000-3428.2018.01.016.
[24] GUPTA A, NAMASUDRA S. A novel technique for accelerating live migration in cloud computing[J]. Automated Software Engineering, 2022, 29(1): 34. DOI: 10.1007/s10515-022-00332-2.
[25] HABAEBI M H, MERRAD Y, ISLAM M R, et al. Extending CloudSim to simulate sensor networks[J]. Simulation, 2023, 99(1): 3-22. DOI: 10.1177/00375497221105530.
[26] 宋建松, 连玮, 陕粉丽, 等. IaaS云融合Q学习的自适应虚拟机部署[J]. 计算机工程与设计, 2021, 42(7): 1851-1858. DOI: 10.16208/j.issn1000-7024.2021.07.008.
[27] 许鹏飞. 基于SLO的服务质量监控系统的设计与实现[D]. 武汉: 华中科技大学, 2022. DOI: 10.27157/d.cnki.ghzku.2022.000154.
[28] 刘帅帅, 姜春茂. 能耗感知下云资源三支粒度调度策略研究[J]. 计算机应用研究, 2023, 40(3): 810-815. DOI: 10.19734/j.issn.1001-3695.2022.07.0365.
[1] 郑力宁, 金雪松, 云利军. 基于粒子群优化算法的云数据均衡放置策略[J]. 广西师范大学学报(自然科学版), 2022, 40(3): 202-209.
[2] 黄恒杰. 传感器中基于连通支配集的区域覆盖控制算法[J]. 广西师范大学学报(自然科学版), 2016, 34(4): 19-25.
[3] 岳才杰, 陈元琰, 朱新华. 一种有效的传感器网络区域查询算法[J]. 广西师范大学学报(自然科学版), 2015, 33(1): 52-58.
[4] 吴礻韦娴, 苏诚, 陈明, 冯国富, 池涛. 基于Agent的温室无线传感网络分簇管理模型[J]. 广西师范大学学报(自然科学版), 2011, 29(2): 210-214.
[5] 陈冬连, 罗晓曙, 陈宏滨, 廖志贤, 王文延. 一种多媒体传感器网络的分布式压缩传输算法[J]. 广西师范大学学报(自然科学版), 2010, 28(4): 25-29.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 袁静静, 郑宇钊, 徐晨枫, 殷婷婕. 非内吞依赖型生物大分子药物胞质递送策略研究进展[J]. 广西师范大学学报(自然科学版), 2024, 42(1): 1 -8 .
[2] 涂广升, 孔咏骏, 宋哲超, 叶康. 密文域可逆信息隐藏研究进展及技术难点分析[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 1 -15 .
[3] 杨杨阳, 朱震霆, 杨翠萍, 李世豪, 张舒, 范秀磊, 万蕾. 基于文献计量学分析的剩余污泥厌氧消化预处理研究进展[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 16 -29 .
[4] 许伦辉, 李金龙, 李若南, 陈俊宇. 基于动态生成对抗网络的路网缺失交通数据修复[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 30 -40 .
[5] 杨海, 谢亚琴. 基于Floyd算法的5G基站区域储能分配策略[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 41 -54 .
[6] 闫文文, 文中, 王爽, 李国祥, 王博宇, 吴艺. 基于AA-CAES电站和综合需求响应的供暖期弃风消纳策略[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 55 -68 .
[7] 甘友春, 王灿, 贺旭辉, 张羽, 张雪菲, 王帆, 喻亚洲. 考虑光热电站和柔性负荷的电氢热综合能源系统联合优化运行[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 69 -83 .
[8] 王旭阳, 王常瑞, 张金峰, 邢梦怡. 基于跨模态交叉注意力网络的多模态情感分析方法[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 84 -93 .
[9] 余谦, 陈庆锋, 何乃旭, 韩宗钊, 卢家辉. 基于矩阵运算加速的改进社区发现遗传算法[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 105 -119 .
[10] 龙芳, 蔡静, 朱艳. 逐步Ⅱ型混合截尾下Lomax分布多部件应力强度模型的可靠性分析[J]. 广西师范大学学报(自然科学版), 2024, 42(2): 120 -130 .
版权所有 © 广西师范大学学报(自然科学版)编辑部
地址:广西桂林市三里店育才路15号 邮编:541004
电话:0773-5857325 E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发