Reliability Evaluation Of Multi-state Network Systems

All of the network systems in the real word are designed to perform their intended tasks in a given environment.Due to the effect of the internal and external uncertainties,most of the systems and their components can perform their tasks with various distinctive levels of performance,which are referred to as multi-state systems.In contrast to the binary-state system model allowing for only two distinctive levels of performance for a system and its components,the multi-state system model can more accurately describe and characterize the complex behavior of a network system,and thus has gained more and more attention and application in the field of system performance analysis.Reliability is a fundamental attribute for the safe operation of any modern technological system.In a situation filled with various uncertainties,people are more focused on the service reliability of systems.Therefore,reliability has become a major concern in the planning,design,operation and management of systems.As the fundamental tool for measuring the performance of a complex system,reliability analysis aims at the quantification of the probability of failure of the system,and it offers us a more effective means to understand the relevant features of systems under failed state.Grounded on the reliability theory and network flow theory,this dissertation focuses on studying the multi-state minimal path algorithm/multi-state minimal cut algorithm for reliability evaluation of multi-state systems,the algorithm for reliability evaluation of multi-state systems under cost constraint,and the algorithm for reliability evaluation of maintainable multi-state systems.More specifically,the contents of the dissertation are summarized as follows:(1)The multi-state minimal path method is an important algorithm for reliability evaluation of multi-state systems,and solving multi-state minimal paths is the focus of the algorithm.Considering the drawbacks of the existing models with respect to multi-state minimal paths,a concept of lower bound of capacity is defined using the characteristic of multi-state minimal paths,and it is employed to construct an improved mathematical model.Grounded on the improved model,an efficient algorithm for solving multi-state minimal paths is presented,and it is also extended to solve multi-state minimal paths in undirected networks.Both theoretical analyses and numerical results indicate that the proposed algorithm is significantly more efficient in solving multi-state minimal paths.(2)The multi-state minimal cut method is also an important algorithm for reliability evaluation of multi-state systems,and solving multi-state minimal cuts is the focus of the algorithm.Given that lower capacity bound plays an important role in solving multi-state minimal cuts,a new technique is developed to find lower capacity bounds of edges grounded on which an improved model with respect to multi-state minimal cuts is established.Identifying duplicate multi-state minimal cuts is the most difficult and challenging task in solving multi-state minimal cuts.Based on the basic model of multi-state minimal cuts,the underlying reason for duplicate multi-state minimal cuts generated by different minimal cuts is well studied,and two important judging criteria are presented to identify duplicate multi-state minimal cuts.A new and more efficient algorithm,based on the theoretical results,is proposed to solve multi-state minimal cuts,and its time complexity is lower than or equal to that of the existing methods.Also,the experimental results indicate that the proposed algorithm is far more efficient in solving multi-state minimal cuts.(3)In addition to system reliability,operating cost is also an important indicator to measure the performance of systems in practical applications.Due to the limited resource,cost is closely associated with the operating efficiency of systems,and is an important factor the system administrator must take into account in the decision-making process.As a combination of system reliability and cost,system reliability under cost constraint is an integrated performance indicator for analyzing multi-state systems,and can be evaluated using multi-state minimal paths with cost constraint.To improve the efficiency of solving multi-state minimal paths with cost constraint,two effective schemes are presented to shorten the whole search space.First,the concept of lower bound of capacity is used to establish an improved mathematical model with respect to multi-state minimal paths with cost constraint.Second,a decomposition technique is utilized to divide the whole search space into several disjoint subspaces among which the unqualified subspaces are discarded,and only the rest are examined to solve multi-state minimal paths with cost constraint.Both theoretical analyses and experimental results indicate that the proposed algorithm is more practical and efficient in solving multi-state minimal paths with cost constraint.(4)Multi-state network system is essentially a deteriorating system,and it is necessary to carry out restoration work on the system when its service level cannot meet the requirement due to the degradation of system performance.A new reliability index is presented to assess the performance of a maintainable multi-state system.This reliability index not only considers the acceptable service level(capacity level)a system should provide,but also considers the overall cost of restoring the system from the failed state to its original state(the largest state).An efficient decomposition algorithm is presented to evaluate the reliability index.The algorithm first separates state vectors satisfying the capacity level from the entire search space,and then checks whether they meet the restoration cost constraint or not.The algorithm only requires some of specific state vectors,rather than all of state vectors,to be checked,and thus it outperforms the traditional method.