Network Reliability Models And Applications In Cyber-Physical Systems And Multi-State Networks

This thesis mainly studies network reliability models and the application in the new type of networks.Network reliability is an important parameter to evaluate the performance of cyber-physical systems and described as the connectivity probability between nodes,which is helpful for the design of the optimal allocation scheme for nodes or links in the system.The exact computation of multi-state two-terminal network reliability is a difficult and significant problem.Diameter constraints can effectively control the path through which network flows pass,and has a positive effect on the approximate calculation of multi-state two-terminal re-liability.The detailed content is liseted as follows:In Chapter 1,we elaborate the theory,development and application of network reliability,introduce topologies of computer networks and research on uniformly optimal/worst graphs,and explain different types of networks,relevant research and problems on reliability.Chapter 2 shows the models and optimization of network reliability,considers diameter constrained binary-state network and multi-state network reliability models,and further pre-sents the mathematical representation of the new reliability model,i.e.k-reliability.This chapter gives an algorithm to compute k-reliability and analyzes the uniformly optimal and worst cases of k-reliability in classes of graphs ?(n,n-1)and ?(n,n):the uniformly worst and optimal graphs in class ?(n,n-1)are respectively chain and star.There does not exist uniformly optimal graph in class ?(n,n)in the light of k-reliability.The ring with cut-vertices and the number of nodes in the ring is 3(n>3).In addition,this chapter defines s,K-opposite tree to compute the reliability from node set K to node s.In Chapter 3,the application and algorithms of reliability models in cyber-physical sys-tems and multi-state networks are studied.In cyber-physical systems,k-reliability well ex-plains the operation probability of the system and reflects the connectivity of nodes in net-works,providing basis for estimation of potential cascading failures.In particular,the net-work with regular inter-link allocation strategy is homogeneous to the network with maxi-mum k-reliability in class of graphs with 2n nodes and nd edges when the information of in-tratopology is unknown.In the design of the approximation algorithm of multi-state two-terminal reliability,this chapter utilizes diameter constraint to control paths through which network flow passes,gives sufficient and necessary conditions for detecting irrelevant arcs and propose an approximation algorithm by controlling the diameter D.At the same time,the reliability with diameter constraint is also an important parameter that can reflect the per-formance of the flow network.Chapter 4 presents the illustrations of networks and analyzes relevant numerical results.The results of experiments well verifies the theorems of the former chapters:for cyber-physical systems,the experiment results show the correctness of highest reliability of regular interedge allocation strategy;for multi-state networks,diameter constraint leads to important computation gains when computing multo-state two-terminal reliability.The effect of diameter constraint is good.For other networks,this chapter applies models of network re-liability into social networks and evaluates the reliability between a user and a group of other users.