多态网络系统可靠性评估方法研究

发布时间：2018-07-24 13:17

【摘要】：现实生活中的网络系统都是在特定的条件下来执行既定的任务。由于受自身或外界不确定性因素的影响,系统及其组成单元在运行过程中一般会表现出多种不同的性能水平,这样的网络系统称之为多态网络系统。相对于二态网络系统模型(系统及其组成单元只有两种不同的性能水平),多态网络系统模型能够更准确地描述和刻画网络系统的复杂行为,在系统性能评估研究领域得到了越来越多的重视和应用。可靠性是现代技术系统安全运行的基本属性。在随机性因素相互交织的环境中,人们越来越重视系统提供服务的可靠性,因此,可靠性已经成为系统规划、设计、运行与管理的主要考量指标。作为评估复杂系统性能的基本工具,可靠性分析的主要目的之一在于对系统失效的可能性进行量化,它为人们提供了一种更有效的方式来理解系统在失效状态下的相关特性。本文根据可靠性理论及网络流理论,重点研究了多态网络系统可靠性评估的多态极小路方法/多态极小割方法,费用约束下的多态网络系统可靠性评估方法,以及可修复多态网络系统可靠性评估方法。更具体地讲,本论文的研究工作主要有以下几个方面:(1)多态极小路方法是多态网络系统可靠性评估的一种重要方法,该方法的核心是求解多态极小路问题。针对现有多态极小路数学模型的不足,根据多态极小路的特性定义了容量下界的概念,并利用容量下界构建了多态极小路的改进数学模型。在此基础上,提出了一种求解多态极小路的高效算法,并把该算法推广到求解无向网络的多态极小路。理论分析与数值试验都表明,提出的算法在求解多态极小路方面具有明显的效率优势。(2)多态极小割方法也是多态网络系统可靠性评估的一种重要方法,而求解多态极小路问题是该方法的核心。鉴于最小容量界在多态极小割问题中的重要作用,提出一种新的方法来寻找边的最小容量界;根据最小容量界,构建了多态极小割的改进数学模型。在多态极小割问题中,重复多态极小割的判定与识别是最艰巨也是最富有具挑战性的难题。从多态极小割的基本模型出发,深入研究了不同极小割产生重复多态极小割的深层次原因,并提出两个重要的判定准则来识别重复多态极小割。根据得到的理论结果,提出了一种新的、更高效的多态极小割求解算法,该算法的时间复杂度小于等于现有算法的时间复杂度,而数值试验的结果也表明,提出的算法在求解多态极小割方面具有显著的效率优势。(3)在实际应用中,除了可靠性指标之外,系统的运行费用也是衡量网络系统性能的重要指标之一。在资源约束条件下,费用问题关系网络系统运行的成本效率,是管理者在决策过程中必须要考虑的一个重要因素。把可靠性指标和费用指标结合起来考虑多态网络系统的综合性能指标—费用约束下的可靠性,该性能指标可以利用费用约束下的多态极小路来计算。为了提高费用约束下的多态极小路的搜索效率,提出两种有效的策略来缩减整个搜索空间。首先,利用容量下界的概念建立了费用约束下的多态极小路改进数学模型;其次,采用一种状态向量集分解方法把整个搜索空间分解成多个互不相交的子空间,丢弃那些不合格的子空间,而仅在剩下的子空间中寻找费用约束下的多态极小路。理论分析与数值试验都表明,提出的算法在求解费用约束下的多态极小路时更加实用、高效。(4)多态网络系统本质上是一个退化系统,当系统的性能发生退化而导致其服务水平不能够满足要求时,有必要对系统开展修复工作。针对可修复多态网络系统,提出了一个新的可靠性指标来衡量系统的性能。该可靠性指标不仅考虑网络系统应提供的可接受服务水平(即容量水平),而且考虑把网络系统从退化状态恢复到初始状态(最大状态)时的修复费用约束问题。提出了一种高效分解算法来计算该可靠性指标。该分解算法首先把满足容量水平的状态向量从整个状态向量空间中分离出来,然后再验证它们是否满足修复费用约束。由于只需对部分状态向量而不是全部状态向量进行枚举验证,该算法的计算效率明显胜过传统方法的计算效率。
[Abstract]:Network systems in real life perform the established tasks under specific conditions. Due to their own or external uncertainties, the system and its components generally show a variety of different performance levels during the process of operation. This network system is called a polymorphic network system. Relative to the two state network system. The model (system and its component units have only two different performance levels). The model of the polymorphic network system can describe and depict the complex behavior of the network system more accurately. It has gained more and more attention and application in the research field of system performance evaluation. Reliability is the basic attribute of the security operation of modern technical system. In the interwoven environment, people pay more and more attention to the reliability of the system providing services. Therefore, reliability has become the main index of system planning, design, operation and management. As a basic tool for evaluating the performance of complex systems, one of the main purposes of reliability analysis is to quantify the possibility of system failure. People provide a more effective way to understand the related characteristics of the system in the state of failure. Based on the reliability theory and the network flow theory, this paper focuses on the study of polymorphic polar approach / polymorphic minima method for the reliability evaluation of polymorphic network systems, the reliability evaluation method of multistate network system under cost constraints, and the repairable method. In particular, the research work of this paper mainly includes the following aspects: (1) the polymorphic path method is an important method for the reliability evaluation of the polymorphic network system. The core of this method is to solve the problem of polymorphic path. The characteristics of the polymorphic polar path define the concept of the lower bound and build the improved mathematical model of the polymorphic path by using the lower bound of capacity. On this basis, an efficient algorithm for solving polymorphic paths is proposed, and the algorithm is extended to the polymorphic minima for solving the undirected network. Both theoretical analysis and numerical experiments show that the proposed algorithm is proposed. The algorithm has obvious efficiency advantage in solving polymorphic path. (2) the method of polymorphic minimum cutting is also an important method for the reliability evaluation of polymorphic network system, and solving the problem of polymorphic path is the core of this method. In view of the important role of the minimum capacity boundary in the polymorphic minimum cut problem, a new method is proposed to find out. According to the minimum capacity bounds, an improved mathematical model for polymorphic minima is constructed according to the minimum capacity boundary. In the problem of polymorphic minimum cut, the determination and recognition of repeated polymorphic minima is the most difficult and the most challenging problem. From the basic model of the polymorphic minimum cut, the repeated polymorphic poles produced by different minimal cuts are deeply studied. Two important criteria are proposed to identify repeated polymorphic minimal cuts. According to the theoretical results obtained, a new and more efficient algorithm for solving polymorphic minimum cut is proposed. The time complexity of the algorithm is less than equal to the time complexity of the existing algorithm, and the results of numerical experiments show that the proposed algorithm is proposed. The method has significant efficiency advantages in solving polymorphic minima. (3) in practical applications, in addition to the reliability index, the operating cost of the system is also one of the most important indicators to measure the performance of the network system. In the resource constraints, the cost efficiency of the network system operation is necessary for the managers in the decision-making process. An important factor to be considered. Combining the reliability index with the cost index, considering the comprehensive performance index of the polymorphic network system, the reliability under the cost constraint, the performance index can be calculated using the polymorphic path under the cost constraint. In order to improve the search efficiency of the polymorphic pole under the cost constraint, two kinds of methods are proposed. The effective strategy to reduce the entire search space. First, the concept of the lower bound of capacity is used to establish the improved mathematical model of polymorphic polar path under the cost constraint. Secondly, a state vector set decomposition method is used to decompose the entire search space into multiple intersected subspaces, discarding those substandard subspaces, but only in the remaining subspaces. The theoretical analysis and numerical experiments show that the proposed algorithm is more practical and efficient in solving the polymorphic path under cost constraints. (4) the polymorphic network system is essentially a degraded system, when the performance of the system is degenerated and the service level can not meet the requirements, It is necessary to repair the system. For the repairable network system, a new reliability index is proposed to measure the performance of the system. The reliability index not only considers the acceptable service level (that is, capacity level) provided by the network system, but also considers the network system from the degenerate state to the initial state (the largest form). A high efficiency decomposition algorithm is proposed to calculate the reliability index. The decomposition algorithm first separates the state vectors that satisfy the capacity level from the whole state vector space, and then verifies that they satisfy the repair cost constraints. It is necessary for only partial state vectors but not all shapes. Enumeration of state vectors verifies that the computational efficiency of the algorithm is much better than that of traditional methods.
【学位授予单位】：北京交通大学
【学位级别】：博士
【学位授予年份】：2017
【分类号】：N945.17

【相似文献】