Message Board

Dear readers, authors and reviewers,you can add a message on this page. We will reply to you as soon as possible!

2021 Volume 46 Issue 7
Article Contents

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

Cloud Computing Adaptive Algorithm Based on VIKOR and User QoS Priority

More Information
  • Received Date: 01/07/2020
    Available Online: 20/07/2021
  • MSC: TP393

  • 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] 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

    CrossRef Google Scholar

    [2] 陶勇, 沈济南. 基于动态关键路径的云工作流调度算法[J]. 计算机应用研究, 2018, 35(5): 1500-1505. doi: 10.3969/j.issn.1001-3695.2018.05.048

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [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

    CrossRef Google Scholar

    [10] 陈暄, 王大伟, 王常亮, 等. 基于IFWA-ABC的云计算资源任务调度算法的研究[J]. 计算机应用研究, 2019, 36(10): 3022-3026.

    Google Scholar

    [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

    CrossRef Google Scholar

    [12] 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.

    Google Scholar

    [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

    CrossRef Google Scholar

    [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.

    Google Scholar

    [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

    CrossRef Google Scholar

  • 加载中
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Figures(1)  /  Tables(4)

Article Metrics

Article views(687) PDF downloads(121) Cited by(0)

Access History

Other Articles By Authors

Cloud Computing Adaptive Algorithm Based on VIKOR and User QoS Priority

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-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所示.

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

    最优-最差多准则决策的步骤如下:最终用户依赖专家组的判断,并针对其请求的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的权重. 通过求解上述问题,得到优选准则的最优权重.

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

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

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

  • 为了实现云计算环境的动态自适应,满足不同任务的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、吞吐量、虚拟机利用率方面均有明显的提高. 未来的工作是进一步完善算法模型,使其更加切合实际应用场景,并针对特定的使用场景,对算法进行针对性的优化.

Figure (1)  Table (4) Reference (15)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return