基于遗传算法的Web服务器集群负载均衡的研究

发布时间：2018-01-26 16:47

本文关键词： 负载均衡调度遗传算法 Mean-Variance模型自适应阈值算法　出处：《浙江理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：负载调度机制是通过最小化响应时间及最大化节点利用率的目的,选择网络中适当的节点进行负载分配。但是,负载均衡的构建是个NP完全问题。服务集群在实现负载均衡这一领域已取得了许多研究成果,虽然传统调度算法操作简单,但对于多个复杂的因素相互交集和约束组合而成的现实环境,这些点到点式的算法在搜索过程中往往会产生大量错误的峰值点,从而影响了最佳分配组合的判定。适应于多个领域的遗传算法,它的本质是一种求解问题的高度并行性全局搜索算法,在基于遗传算法的负载均衡研究中,适应度函数是评估请求分配组合优劣的标准。对此,本文提出引入Mean-Variance模型改进负载均衡算法中的适应度函数。采用投资选择模型Mean-Variance来设置服务集群中节点利用率的权重,通过Lagrange Multiplier以最小化任务完成时间为条件来获得最优的权重,该方式提高了服务集群中任务调度的准确性和有效性。针对服务集群的负载均衡研究,本文的主要贡献包括三个方面:(1)在遗传算法的编码设计中,本文提出采用三维十进制对空间的候选解进行编码设计。在三维十进制编码中,每个解被编码为由三个属性表示的十进制数组。其中每个数组中的字符串具有固定大小的量化值,量化负载是根据肯尼迪宇航中心服务器日志文件中任务的比重进行量化。在搜索空间中的每个节点都有字符串代表,而且其代表的字符串是唯一的。因此三维十进制编码设计提高了遗传调度操作的准确性。(2)通过深入研究和分析基于遗传算法的负载均衡方法,针对适应度函数作为评判分配组合的精确性问题,本文引入Mean-Variance模型构建适应度函数。通过投资组合选择模型Mean-Variance进行最小化响应时间,可得到每个服务器资源利用率的权重,从而获得最优的分配组合。改变了传统适应度函数中节点利用率的简单叠加模式,使得执行时间和节点利用率得到了改善,提高负载均衡策略的有效性。(3)本文采用Mean-Variance模型构建适应度函数,使得负载均衡算法中的执行时间和节点利用率得到了有效性计算。但调度算法中仍旧会出现部分服务超载运行的不均衡现象。对此,提出自适应阈值算法,根据目前的系统负载和新调度任务的负载得到单个服务器的负载均值,同时系统设置了重阈值和轻阈值,如果超过重阈值或低于轻阈值则此服务器将是不正常运作,将被认定为不可接受分配任务的服务器。因此可接受分配服务器的自适应阈值策略给负载平衡机制添加了灵活性,给负载均衡系统增加了一个重要保障。本文设计并实施了一系列实验,在不同服务环境及参数设计下与其他模型进行比较。仿真结果表明本文提出的优化的负载均衡算法在节点利用率和响应时间方面使服务集群得到了更好的均衡。
[Abstract]:Load scheduling mechanism is to minimize the response time and maximize the node utilization, select the appropriate nodes in the network for load distribution. The construction of load balancing is a NP-complete problem. A lot of research results have been made in the field of load balancing in the service cluster, although the traditional scheduling algorithm is simple to operate. However, for the real environment where many complex factors are intersected and combined with constraints, these point-to-point algorithms often produce a large number of wrong peak points in the search process. Therefore, the decision of optimal allocation combination is affected. Genetic algorithm is suitable for many fields. Its essence is a highly parallel global search algorithm for solving the problem, in the research of load balancing based on genetic algorithm. Fitness function is the criterion to evaluate the combination of request allocation. In this paper, Mean-Variance model is introduced to improve the fitness function of load balancing algorithm, and the investment selection model Mean-Variance is used to set the node utilization in service cluster. The weight of the rate. The optimal weight is obtained by using Lagrange Multiplier to minimize the completion time of the task. This method improves the accuracy and effectiveness of task scheduling in service cluster. The main contributions of this paper include three aspects: 1) in the coding design of genetic algorithm. In this paper, we propose to encode the candidate solution of space by using three-dimensional decimal system, which is used in three-dimensional decimal coding. Each solution is encoded as a decimal array represented by three attributes, where the string in each array has a fixed quantization value. The quantization load is quantized according to the proportion of tasks in the Kennedy Aerospace Center server log file. Each node in the search space is represented by a string. Therefore, 3D decimal coding design improves the accuracy of genetic scheduling operations. 2) through in-depth research and analysis of load balancing methods based on genetic algorithm. This paper aims at the accuracy of fitness function as an evaluation of allocation combination. This paper introduces Mean-Variance model to construct fitness function and minimizes response time through portfolio selection model Mean-Variance. The weight of each server resource utilization ratio can be obtained, and the optimal allocation combination can be obtained, which changes the simple superposition mode of node utilization in the traditional fitness function. Make the execution time and node utilization improved, improve the effectiveness of load balancing strategy. 3) this paper uses Mean-Variance model to construct fitness function. The execution time and node utilization in the load balancing algorithm are calculated effectively. However, in the scheduling algorithm, part of the service overload will still be unbalanced. To this end, an adaptive threshold algorithm is proposed. According to the current system load and the load of the new scheduling task, the average load of a single server is obtained. At the same time, the system sets a heavy threshold and a light threshold. This server is not working properly if it exceeds the heavy threshold or falls below the light threshold. The adaptive threshold policy of the acceptable allocation server adds flexibility to the load balancing mechanism. This paper designs and implements a series of experiments. Compared with other models under different service environment and parameter design, the simulation results show that the optimized load balancing algorithm proposed in this paper makes the service cluster more balanced in terms of node utilization and response time.
【学位授予单位】：浙江理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18;TP368.5

【相似文献】