基于multi-agent的自主调度算法的研究
发布时间：2018-07-28 20:31
【摘要】：大规模和异构性是现今网络技术的快速发展方向,传统的网络体系结构和资源分配调度策略等已经没有办法满足网络的发展需要,尤其是在那些用来进行大计算量任务的分布式系统中。其问题是在于大规模的网络计算系统中,计算节点或存储节点等呈现出分散的、分布的特点,而且各种节点之间也是不尽相同的。这些节点的异构性就导致了一些常用的分配算法很难适用,因此就需要多种不同的分配策略。除此之外,大规模网络计算系统(网格计算、云计算)向商用化发展,它需要满足的外部用户的需求也更加的多样化、复杂化,对系统提供服务的时效性、可靠性、安全性等的要求也越来越高;计算系统的服务商要在满足用户任务需求的情况下,降低自身运营成本,这样才能使得大规模网络计算系统健康有效的长久发展下去。因此,对大规模计算系统中的多性能优化、建模以及算法的研究是十分必要的。本文对于上述大规模网络计算系统中出现的问题,给出了基于multi-agent的自主调度的算法,算法考虑了任务时效性和可靠性两种性能要求,对任务进行划分并且在计算节点中分配。算法求解中使用到了通用生成函数和模拟退火算法,最后通过实验对模型进行了验证。首先,在前人工作的基础上进行研究,根据大规模网络计算系统和人工智能中多代理系统的机制,将两者结合起来,构造基于multi-agent的大规模自主计算系统模型。在建立的模型的基础上,提出任务划分和计算节点的分配算法。当系统收到用户的计算服务请求时,本系统会根据服务的信息进行分析,以确定任务是最短服务时间原则还是最低可靠性原则,并据此将之划分成多个小的、可并行执行的、耦合度低的EB(可执行模块),并将这些模块分配给计算节点进行执行。其次,提出对系统各性能的评估数学模型,对任务执行的时效性、可靠性进行评估,然后再借助通用生成函数技术来对各个指标进行快速计算,提出基于最短服务时间和最低可靠性原则的服务计算模型。最后,针对本文中提出的优化问题,采用模拟退火算法来对其进行求解,并且实际仿真实验对其进行验证并求得不同原则下的任务划分和计算节点的分配,最终获得问题的相对全局最优解。
[Abstract]:Large-scale and heterogeneity are the rapid development direction of network technology nowadays. The traditional network architecture and resource allocation and scheduling strategy have been unable to meet the needs of network development. Especially in distributed systems that are used for large computational tasks. The problem lies in the scattered and distributed characteristics of computing nodes or storage nodes in large-scale network computing systems. Due to the heterogeneity of these nodes, some common allocation algorithms are difficult to apply, so many different allocation strategies are needed. In addition, large-scale network computing systems (grid computing, cloud computing) to commercial development, it needs to meet the needs of external users more diversified, complex, to provide services to the system timeliness, reliability, The requirement of security and so on is higher and higher. The service providers of computing system should reduce their own operating cost in order to make the large-scale network computing system develop healthily and effectively for a long time. Therefore, it is necessary to study multi-performance optimization, modeling and algorithms in large-scale computing systems. In this paper, an algorithm of autonomous scheduling based on multi-agent is presented to solve the problems in large-scale network computing systems. The algorithm takes into account the requirements of timeliness and reliability of tasks, divides the tasks and allocates them in computing nodes. The general generating function and simulated annealing algorithm are used in the solution of the algorithm. Finally, the model is verified by experiments. Firstly, based on the previous work, according to the mechanism of large-scale network computing system and multi-agent system in artificial intelligence, a large-scale autonomous computing system model based on multi-agent is constructed by combining the two mechanisms. On the basis of the established model, a task partition algorithm and an algorithm for computing node assignment are proposed. When the system receives the user's request for computing service, the system will analyze the information of the service to determine whether the task is the principle of minimum service time or the principle of minimum reliability, and divide it into several small, parallel execution. The EB (executable module) with low coupling degree is assigned to the computing node for execution. Secondly, a mathematical model for evaluating the performance of the system is proposed to evaluate the timeliness and reliability of task execution, and then to calculate each index quickly with the help of general-purpose generating function technology. A service computing model based on the principle of minimum service time and minimum reliability is proposed. Finally, in view of the optimization problem proposed in this paper, simulated annealing algorithm is used to solve the problem, and the actual simulation experiment verifies it and obtains the task partition and calculation node allocation under different principles. Finally, the relative global optimal solution of the problem is obtained.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02;TP301.6
，
本文编号：2151488
[Abstract]:Large-scale and heterogeneity are the rapid development direction of network technology nowadays. The traditional network architecture and resource allocation and scheduling strategy have been unable to meet the needs of network development. Especially in distributed systems that are used for large computational tasks. The problem lies in the scattered and distributed characteristics of computing nodes or storage nodes in large-scale network computing systems. Due to the heterogeneity of these nodes, some common allocation algorithms are difficult to apply, so many different allocation strategies are needed. In addition, large-scale network computing systems (grid computing, cloud computing) to commercial development, it needs to meet the needs of external users more diversified, complex, to provide services to the system timeliness, reliability, The requirement of security and so on is higher and higher. The service providers of computing system should reduce their own operating cost in order to make the large-scale network computing system develop healthily and effectively for a long time. Therefore, it is necessary to study multi-performance optimization, modeling and algorithms in large-scale computing systems. In this paper, an algorithm of autonomous scheduling based on multi-agent is presented to solve the problems in large-scale network computing systems. The algorithm takes into account the requirements of timeliness and reliability of tasks, divides the tasks and allocates them in computing nodes. The general generating function and simulated annealing algorithm are used in the solution of the algorithm. Finally, the model is verified by experiments. Firstly, based on the previous work, according to the mechanism of large-scale network computing system and multi-agent system in artificial intelligence, a large-scale autonomous computing system model based on multi-agent is constructed by combining the two mechanisms. On the basis of the established model, a task partition algorithm and an algorithm for computing node assignment are proposed. When the system receives the user's request for computing service, the system will analyze the information of the service to determine whether the task is the principle of minimum service time or the principle of minimum reliability, and divide it into several small, parallel execution. The EB (executable module) with low coupling degree is assigned to the computing node for execution. Secondly, a mathematical model for evaluating the performance of the system is proposed to evaluate the timeliness and reliability of task execution, and then to calculate each index quickly with the help of general-purpose generating function technology. A service computing model based on the principle of minimum service time and minimum reliability is proposed. Finally, in view of the optimization problem proposed in this paper, simulated annealing algorithm is used to solve the problem, and the actual simulation experiment verifies it and obtains the task partition and calculation node allocation under different principles. Finally, the relative global optimal solution of the problem is obtained.
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.02;TP301.6
，
本文编号：2151488
本文链接：https://www.wllwen.com/guanlilunwen/ydhl/2151488.html
