高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

基于VIKOR和用户QoS优先级的云计算自适应算法

, 

上一篇

下一篇

程曦, 宋铁成. 基于VIKOR和用户QoS优先级的云计算自适应算法[J]. 西南师范大学学报(自然科学版), 2021, 46(7): 109-113. doi: 10.13718/j.cnki.xsxb.2021.07.015
引用本文: 程曦, 宋铁成. 基于VIKOR和用户QoS优先级的云计算自适应算法[J]. 西南师范大学学报(自然科学版), 2021, 46(7): 109-113. doi: 10.13718/j.cnki.xsxb.2021.07.015
shu
CHENG Xi, SONG Tie-cheng. Cloud Computing Adaptive Algorithm Based on VIKOR and User QoS Priority[J]. Journal of Southwest China Normal University(Natural Science Edition), 2021, 46(7): 109-113. doi: 10.13718/j.cnki.xsxb.2021.07.015
Citation: CHENG Xi, SONG Tie-cheng. Cloud Computing Adaptive Algorithm Based on VIKOR and User QoS Priority[J]. Journal of Southwest China Normal University(Natural Science Edition), 2021, 46(7): 109-113. doi: 10.13718/j.cnki.xsxb.2021.07.015
shu

基于VIKOR和用户QoS优先级的云计算自适应算法

  • 1.

    四川文理学院，康养产业学院，四川 达州 635000

  • 2.

    重庆邮电大学 通信与信息工程学院，重庆 400065

  • 基金项目: 国家自然科学基金项目(61702065)；四川省教育信息化应用与发展研究中心项目(JYXX18-030)
详细信息
    作者简介:

    程曦，硕士，讲师，主要从事计算机应用技术研究 .

  • 中图分类号: TP393

Cloud Computing Adaptive Algorithm Based on VIKOR and User QoS Priority

  • 1.

    College of Health Care Industry, Sichuan University of Arts and Science, Dazhou Sichuan 635000, China

  • 2.

    College of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, China

  • 摘要: 针对传统调度算法不能提供一种在考虑负载平衡的同时满足用户服务质量(Quality of Service，QoS)的自适应方法进行了研究，提出一种基于改进多准则妥协解排序法(VIKOR)和用户QoS优先级的云计算自适应调度算法. 该算法首先使用最优-最差多准则决策为每个评估标准或用户QoS优先级分配重要性权重，然后使用VIKOR评估和确定每个用户请求的等级并进行排序，最后自适应任务调度根据虚拟机的负载率来分配工作负载以保持动态负载平衡. 实验结果表明：本文方法在MaKespan、吐出量和虚拟机利用率性能方面均有明显改善.
    Abstract: Aiming at the fact that traditional scheduling algorithms cannot provide an adaptive method that satisfies user quality of service (QoS) while considering load balancing, an adaptive scheduling algorithm has been proposed in this paper for Cloud Computing Based on vlsekriterijumska optimizacijai kompromisno resenje (VIKOR) and user QoS priority. In the algorithm, the optimal worst multi criteria decision is first used to assign importance weight to each evaluation standard or user QoS priority, then VIKOR used to evaluate and determine the level of each user's request and sort it. Finally, adaptive task scheduling allocates workload according to the load rate of virtual machine to maintain dynamic load balance. The experimental results show that the performance of MaKespan, throughput and virtual machine utilization are significantly improved.
  • 加载中

  • 图 1  本文提出的算法流程图

    下载: 全尺寸图片 幻灯片

    表 1  输入任务数不同时各算法的MaKespan ms

    任务 200 300 400 500 600 700 800
    SSAL 179.1 218.4 268.8 308.1 319.1 352.7 379.2
    本文 148.2 201.5 232.3 263.1 275.5 281.1 304.8
    下载: 导出CSV

    表 2  输入任务数不同时各算法的吞吐量 请求·s-1

    任务 200 300 400 500 600 700 800
    SSAL 15.72 16.87 17.77 19.04 21.42 22.94 23.22
    本文 22.43 24.21 25.22 26.74 27.39 29.40 32.78
    下载: 导出CSV

    表 3  输入任务数不同时各算法的VM利用率

    任务 200 300 400 500 600 700 800
    SSAL 0.522 0.540 0.599 0.602 0.614 0.653 0.690
    本文 0.581 0.613 0.652 0.692 0.692 0.749 0.755
    下载: 导出CSV

    表 4  VM数量不同时各算法的MaKespan ms

    VM数量 20 40 80 120 160 200
    SSAL 264.6 232.6 215.9 170.4 126.7 110.9
    本文 345.7 332.2 273.3 213.5 189.2 169.9
    下载: 导出CSV
  • [1] ISMAYILOV G, TOPCUOGLU H R. Neural Network Based Multi-Objective Evolutionary Algorithm for Dynamic Workflow Scheduling in Cloud Computing[J]. Future Generation Computer Systems, 2020, 102: 307-322. doi: 10.1016/j.future.2019.08.012
    [2] 陶勇, 沈济南. 基于动态关键路径的云工作流调度算法[J]. 计算机应用研究, 2018, 35(5): 1500-1505. doi: 10.3969/j.issn.1001-3695.2018.05.048
    [3] KHORSAND R, GHOBAEI-ARANI M, RAMEZANPOUR M. A Self-Learning Fuzzy Approach for Proactive Resource Provisioning in Cloud Environment[J]. Software: Practice and Experience, 2019, 49(11): 1618-1642. doi: 10.1002/spe.2737
    [4] GHOBAEI-ARANI M, KHORSAND R, RAMEZANPOUR M. An Autonomous Resource Provisioning Framework for Massively Multiplayer Online Games in Cloud Environment[J]. Journal of Network and Computer Applications, 2019, 142: 76-97. doi: 10.1016/j.jnca.2019.06.002
    [5] MISHRA S K, SAHOO B, PARIDA P P. Load Balancing in Cloud Computing: a Big Picture[J]. Journal of King Saud University - Computer and Information Sciences, 2020, 32(2): 149-158. doi: 10.1016/j.jksuci.2018.01.003
    [6] KHORSAND R, GHOBAEI-ARANI M, RAMEZANPOUR M. FAHP Approach for Autonomic Resource Provisioning of Multitier Applications in Cloud Computing Environments[J]. Software: Practice and Experience, 2018, 48(12): 2147-2173. doi: 10.1002/spe.2627
    [7] XU X L, ZHANG X Y, KHAN M, et al. A Balanced Virtual Machine Scheduling Method for Energy-Performance Trade-Offs in Cyber-Physical Cloud Systems[J]. Future Generation Computer Systems, 2020, 105: 789-799. doi: 10.1016/j.future.2017.08.057
    [8] SAFARI M, KHORSAND R. Energy-Aware Scheduling Algorithm for Time-Constrained Workflow Tasks in DVFS-Enabled Cloud Environment[J]. Simulation Modelling Practice and Theory, 2018, 87: 311-326. doi: 10.1016/j.simpat.2018.07.006
    [9] NAYAK S C, TRIPATHY C. Deadline Based Task Scheduling Using Multi-Criteria Decision-Making in Cloud Environment[J]. Ain Shams Engineering Journal, 2018, 9(4): 3315-3324. doi: 10.1016/j.asej.2017.10.007
    [10] 陈暄, 王大伟, 王常亮, 等. 基于IFWA-ABC的云计算资源任务调度算法的研究[J]. 计算机应用研究, 2019, 36(10): 3022-3026. doi: https://www.cnki.com.cn/Article/CJFDTOTAL-JSYJ201910033.htm
    [11] SAFARI M, KHORSAND R. PL-DVFS: Combining Power-Aware List-Based Scheduling Algorithm with DVFS Technique for Real-Time Tasks in Cloud Computing[J]. The Journal of Supercomputing, 2018, 74(10): 5578-5600. doi: 10.1007/s11227-018-2498-z
    [12] doi: http://www.sciencedirect.com/science/article/pii/S1389128618313665 GOLCHI M M, SARAEIAN S, HEYDARI M. A Hybrid of Firefly and Improved Particle Swarm Optimization Algorithms for Load Balancing in Cloud Environments: Performance Evaluation[J]. Computer Networks, 2019, 162: 1-15.
    [13] RAGMANI A, ELOMRI A, ABGHOUR N, et al. An improved Hybrid Fuzzy-Ant Colony Algorithm Applied to Load Balancing in Cloud Computing Environment[J]. Procedia Computer Science, 2019, 151: 519-526. doi: 10.1016/j.procs.2019.04.070
    [14] KAUR A, KAUR B. Load Balancing Optimization Based on Hybrid Heuristic-Metaheuristic Techniques in Cloud Environment[J]. Journal of King Saud University-Computer and Information Sciences, 2019, 2(10): 1-12.
    [15] CHEN Xing, WANG Haijiang, MA Yun, et al. Self-Adaptive Resource Allocation for Cloud-Based Software Services Based on Iterative QoS Prediction Model[J]. Future Generation Computer Systems, 2020, 105: 287-296. doi: 10.1016/j.future.2019.12.005
  • 加载中
图( 1) 表( 4)
计量
  • 文章访问数:  599
  • HTML全文浏览数:  599
  • PDF下载数:  109
  • 施引文献:  0
出版历程
  • 收稿日期:  2020-07-01
  • 刊出日期:  2021-07-20

基于VIKOR和用户QoS优先级的云计算自适应算法

    作者简介: 程曦，硕士，讲师，主要从事计算机应用技术研究
  • 1. 四川文理学院，康养产业学院，四川 达州 635000
  • 2. 重庆邮电大学 通信与信息工程学院，重庆 400065
  • 收稿日期:  2020-07-01
基金项目:  国家自然科学基金项目(61702065)；四川省教育信息化应用与发展研究中心项目(JYXX18-030)

摘要: 针对传统调度算法不能提供一种在考虑负载平衡的同时满足用户服务质量(Quality of Service，QoS)的自适应方法进行了研究，提出一种基于改进多准则妥协解排序法(VIKOR)和用户QoS优先级的云计算自适应调度算法. 该算法首先使用最优-最差多准则决策为每个评估标准或用户QoS优先级分配重要性权重，然后使用VIKOR评估和确定每个用户请求的等级并进行排序，最后自适应任务调度根据虚拟机的负载率来分配工作负载以保持动态负载平衡. 实验结果表明：本文方法在MaKespan、吐出量和虚拟机利用率性能方面均有明显改善.

English Abstract

    全文HTML

  • 近年来，随着互联网的发展，云计算为用户服务增加了一种新的模式，允许用户随时随地以按次付费的方式访问信息技术服务[1-2]. 但云环境的特征不同于其他环境的特征，云计算的资源是异构的且分布在很大的区域，操作环境和这些资源使用的工具不同. 云中的资源通过动态通信层相互关联，并向用户提供多种服务和计费策略，云计算的其他特征包括按需自助服务、广域网接入、共享资源池和快速弹性[3-5]. 由于这些特性，满足云资源峰值需求的动态负载均衡成为现代高性能计算系统面临的挑战. 云计算中的负载平衡通过将多个客户端的请求提供给服务器组来减少此问题，从而最大程度地减少了客户端的等待时间[6].

    云计算负载平衡使数据中心可以避免虚拟机(Virtual Machine，VM)中的过载/欠载[7]，负载平衡算法需要具有以下特征：成本效益，即负载均衡算法以较低的成本提供更好的性能；可扩展性和灵活性，即负载平衡算法必须具有改变大小的能力，并且必须对分布式系统中的变化可行；优先级，即必须在执行负载平衡之前确定所有工作的优先级[8-9]. 负载平衡方法主要分为3类：静态负载平衡、动态负载平衡和混合负载平衡[10]. 静态负载平衡方法通过先到先得策略将任务分配给资源，此方法使用内存和处理器功能容量之类的信息. 动态负载平衡方法是利用当前系统的状态将任务分配给资源的遗传算法[11]. 混合负载平衡方法利用静态和动态负载平衡方法将任务分配给资源.

    文献[12]提出一种用于在云环境中实现负载均衡的萤火虫算法和改进粒子群优化算法的混合算法，分别用于制定、改进资源有效利用率和任务响应时间等重要指标，该算法在全局搜索性能和收敛速度上都有明显的提高. 文献[13]提出一种基于模糊逻辑和蚁群优化的混合算法来改善云计算负载均衡，该算法采用田口实验设计来确定蚁群优化参数的最佳值，并定义模糊模块来评估信息素值提高计算时间，该算法可以改善云计算架构中的负载平衡，减少相应的时间. 文献[14]提出一种云环境下基于混合启发式和元启发式技术的负载均衡优化算法，用于负载分布均匀的情况下优化虚拟机的利用率. 该算法基于启发式技术和元启发式算法的混合，实现其在制造时间和成本方面的最佳性能.

    在研究了现有云计算负载均衡的基础上，为了在考虑负载均衡的同时满足用户服务质量要求，本文提出一种基于改进多准则妥协解排序法(VIKOR)和用户服务质量(QoS)优先级的云计算自适应调度算法. 该算法使用最优-最差多准则决策从用户角度为每个评估标准或用户QoS优先级分配重要性权重，VIKOR通过最大化团体利益和最小化个人负面影响对用户要求进行排序. 根据虚拟机的速度和内存能力，设计自适应任务调度方法将用户请求从全局优先级队列分发到属于相应虚拟机的输出队列. 当服务器的容量发生超时变化时，该算法可以产生最优的吞吐量. 实验结果表明，本文算法能有效提高MaKespan、吐出量和虚拟机利用率等性能.

1.   基于VIKOR和用户QoS优先级的云计算自适应调度

  • 本文提出的协议首先将用户所有请求放入一个输入队列，然后根据用户需求，采用最优-最差和VIKOR混合方法估计用户请求的相对重要性/权重并进行排序，根据VM的速度和内存容量来分配工作负载，当服务器的容量发生超时变化时，该算法可以产生最优的吞吐量. 具体流程图如图 1所示.

    • 1.1.   从用户角度评估标准权重

  • 由于在决策过程中不同的最终用户具有不同的准则，因此本文使用最优-最差多准则决策为每个评估标准分配重要性权重. 该方法考虑两个成对比较向量，并允许评估每个准则相对于输入队列中用户请求的权重.

    最优-最差多准则决策的步骤如下：最终用户依赖专家组的判断，并针对其请求的QoS参数初始化一组首选标准[c1，c2，…，cn]，然后从用户角度分析和确定最优(最理想/最重要)和最差(最不理想/最不重要)标准.

    相对于其他准则，确定最佳准则的优先级. 这是根据从1到9的标准进行的. aBi值表示最佳准则B相对于准则i的优先级. 然后根据最差准则确定准则的优先级，也是根据从1到9的标准进行的. aiW值表示标准i相对于最差标准W的优先级. 最后计算准则权重(W1，…，Wn)，其中所有i的最大绝对差$ \left| {\frac{{{W_B}}}{{{W_i}}} - {a_{Bi}}} \right| $和$ \left| {\frac{{{W_i}}}{{{W_W}}} - {a_{iW}}} \right| $最小化. 计算准则权重的最小-最大模型表示为

    式(1)中$ \sum\nolimits_i {{W_i} = 1, {W_i} \ge 0} $. WB表示最佳准则B的权重，Wi表示准则i的权重，WW表示最差标准W的权重. 通过求解上述问题，得到优选准则的最优权重.

    • 1.2.   评估和确定每个用户请求的等级

  • VIKOR方法是一种良好的多属性决策方法，它通过最大化群体利益和最小化负面影响，使用折衷解决方案得到决策者接受. 折衷排序根据折衷编程方法中用作聚合函数Lpi的排序来计算. 假设有m个备选方案，表示为A1，A2，…，Am，Ai的第j方面的排名由fij表示，该fij指定备选方案Ai的第j标准函数的值. 如果考虑k个准则，

    其中，1≤p≤∞；i=1，2，…，m为全局准则的指数，fj*为正最优解，fj-为负最优解.

    VIKOR方法评估有两个规则：多数规则和反对规则.

    • 1.3.   自适应调度将请求分发到属于相应VM的输出队列

  • 为了实现云计算环境的动态自适应，满足不同任务的QoS要求，本文提出一种基于阈值动态负载均衡算法的自适应scheduler，将请求分发到属于相应VM的输出队列. 如果自适应scheduler应用预先定义的时间间隔并以任何间隔将请求分发到相应的VM输出队列，那么确定最佳间隔大小将变得困难. 对于较短的预定义时间间隔，自适应scheduler组件和自适应dispatchers之间信息交换可能比长的预定义时间间隔提供更多的网络开销. 此外，当预定时间间隔太长时，自适应dispatchers对VM获取信息提供的精度较低，从而导致负载不平衡问题. 为了克服这些缺点，确定一个阈值来与自适应调度器VM负载进行比较. 如果VM的负载大于阈值，则自适应dispatcher将负载信息发送给自适应scheduler.

2.   实验结果与分析

  • 在本文中，所有实验均是在一台配置为Intel Core i7、3.4 GHz CPU和4 GB内存的Microsoft Windows 10平台上进行，使用云计算仿真平台CloudSim 3.0.3对本文提出的自适应任务调度算法进行评估. CloudSim是基于离散事件模型，用Java语言开发的仿真应用系统，具有跨平台部署等特点.

    为了评价本文自适应任务调度算法的性能，采用吞吐量、MaKespan和VM利用率等指标进行评估. 吞吐量是指虚拟机以最大速率每单位时间执行的用户任务数；MaKespan是指处理一组提交给系统的任务的完成时间；VM利用率是指CPU使用率的百分比，其值介于0到1之间. 将本文提出的算法与基于滑动窗口的自学习自适应负载均衡器(SSAL)算法进行分析比对. SSAL是一种将时间逻辑划分为固定大小的间隔，并将任务请求分配给在每个间隔具有最高性能的VM的负载均衡算法.

    表 1给出了在VM固定为100的情况下，本文算法和SSAL在输入任务量不同时的平均MaKespan[15]. 由表 1可以看出，MaKespan随着输入任务量的增加而增加，本文方法的MaKespan性能比SSAL好3.7%. 这是因为本文方法自适应scheduler根据性能负载比对所有VM进行排序，并选择相应的输出队列给相应的VM，因此它可以满足要求.

    表 2给出了在虚拟机(VM)固定为100的情况下，本文算法和SSAL在输入任务量不同时的吞吐量. 由表 2可以看出，吞吐量随着输入任务量的增加而增加，本文算法的吞吐量高于SSAL. 这是因为本文方法在自适应dispatcher的VM负载上设置阈值，将VM的负载率发送给自适应scheduler，而不是周期性地更新负载信息，然后将用户的任务请求分配给低负载、高性能的VM，从而产生最佳吞吐量.

    表 3给出了在虚拟机(VM)固定为100的情况下，本文算法和SSAL在输入任务量不同时的VM利用率. 由表 3可以看出，与SSAL相比本文方法提高了VM的利用率，这是因为本文提出的方法基于VM当前负载和性能来分配请求，从而使VM有较高的利用率.

    表 4给出了在任务数量固定为500的情况下，本文算法和SSAL算法在VM数量不同时的MaKespan. 由表 4可以看出，本文算法具有更高的效率，这是因为本文算法在全局优先级队列中将请求分配给适当的VM，基于VM最近的评估能力，它使每个任务都具有时间效率.

3.   结语

  • 针对云计算中的多准则决策问题，本文提出一种基于VIKOR和用户QoS优先级的云计算自适应调度算法，该算法执行自适应负载均衡和排序，并选择合适的任务分配操作来保证服务质量，使用最优-最差多准则决策从用户角度为每个评估标准或用户QoS优先级分配重要性权重，VIKOR通过最大化团体利益和最小化个人负面影响对用户请求进行排序，自适应任务调度器根据每个VM的负载率将VM分配给请求，并试图强制所有VM几乎同时实现任务请求. 当服务器的容量发生超时变化时，该算法可以产生最优的吞吐量. 实验结果表明，本文算法在MaKespan、吞吐量、虚拟机利用率方面均有明显的提高. 未来的工作是进一步完善算法模型，使其更加切合实际应用场景，并针对特定的使用场景，对算法进行针对性的优化.

参考文献 (15)

目录

版权所有：西南师范大学学报(自然科学版)

地址：重庆市北碚区西南大学 电话：023-68252540，68254576，68254478 电子邮箱：xbbjb@swu.edu.cn

本系统由北京仁和汇智信息技术有限公司开发

/

返回文章
返回