GRAPH THEORY APPLICATION FOR RELIABILITY EVALUATION AND OPTIMIZATION

Abstract

The present thesis highlights the use of graph theory in developing algorithms for reliability evaluation and optimization of general systems. Although some attempts have been made in the past in this direction, however much can be done to further exploit the potential of graph theory for improving upon the reliability evaluation and optimization techniques. Th" Thesis is the attempt in this direction. The presentation of the work begins with the systematic study of models of the different systems and their reliability graphs. Uptodate review of the available literature has been presented alongwith a discussion in the merits and demerits of each of the methods. Most of the methods available in the literature for reliability evaluation require the knowledge of the paths and cutsets as a starting point and subsequently use some boolean algebra technique for deriving reliability expression. In communication networks the grade of service depends upon the probability of a specified node being connected to aset of nodes. Therefore in such networks, one is interested in the reliability between source node and a set of nodes or between a set of nodes to another set of nodes, in order to establish a viable connection between them. Therefore, a. method should be available for enumeration of all the simple paths between a source node and a set of nodes with minimum efforts. This would not be economically achieved through the existing techniques. Therefore, an algorithm which offers an advantage over the existing ones with regard to the above

mentioned features, is developed. Another algorithm has also been developed for enumerating all minimal cutsets of the graph between a source node and a set of nodes. Both these algorithms are applicable to the networks consisting of branches and nodes which have finite non zero failure probability. The cutsets and pathsets are enumerated by the algorithms in an ascending order of cardinality. The global reliability is the probability that the network is atleast simply connected. This parameter is a measure of grade of service when it is desired that all nodes of the network should remain connected. In order to evaluate the global reliability of acommunication network the pathsets, i.e. the spanning trees of the reliability graph should be known. Therefore amethod for generating all the spanning trees of agraph has been developed. The spanning trees are genenerated from the incidence matrix of the graph and there fore the method is easy to apply and for moderately sized systems, the paths may be easily enumerated without the help of adigital computer. Another matrix method has also been developed, which makes use of incidence and connection matrices of agraph for the enumeration of all simple paths for the purpose of global reliability. Symbolic reliability evaluation is preferred over other methods when the system is such that it has a fixed configuration but subsystem failure probabilities change with time, in such cases once the reliability polynomial is known, we can evaluate the system reliability for changed failure probabilities by suhstituting new values. Many times

the reliability between different terminal pairs is desired for evaluating performance of a communication system. Computation time and memory requirement of the available methods varies in proportion to the number of terminal pairs for which reliability evaluation is desired. Two new algorithms for symbolic relia bility evaluation of reducible systems have been developed. These methods are fast and the efficiency of these algorithms increases with the increase in complexity of the system. A general computer program for complex systems reliability evaluation has been developed. This program is applicable to any system and provides solution very fast. Use of matrix sparsity has been made to reduce the memory requirements. Very few methods are available for calculating the global reliability of acommunication network. Amongst the many shortcomings, one major limitation of the available methods is decrease in efficiency with increase in the system complexity. Therefore an efficient method, for the global reliability evaluation of acommunication system, has been developed. The method is fast, simple and therefore requires less computer time and memory. The problem of redundancy allocation to complex systems has been analysed and the peculates in the optimum redundancy allocation to non series-parallel systems have been highlighted and it has been demonstrated that erroneous concepts have been used in many papers published earlier on this subject. A simple method of redundancy allocation to complex systems has also been developed by using the

pecularities of complex system optimum redundancy allocation. The method developed provides an integer solution and better results in comparison with some of the existing method. An algorithm for the enumeration of all the series-parallel graphs of given number of branches has been developed. The properties of reliability polynomial for a given network configuration have been studied. Further in case of a series-parallel network of equal probability branches, a synthesis procedure has been developed through which one can directly determine the configuration from the reliability polynomial. The problem of synthesising a communication net work with a given number of nodes consists of determining the optimal configuration of the graph which offers a specified value of reliability at minimum cost. A method for the above synthesis has also been developed. In short, the present work provides a number of efficient algorithms for the terminal and global reliability evaluation of communication systems besides providing a simple optimization technique in order to determine an optimal system configuration. It is hoped that with the introduction of new methodology described herein, the task of a reliability analyst will be made easier and less cumbersome which was the prime objective of this thesis.