A New and Efficient Approach Based on Binary Decision Diagram to Evaluate the K-terminal Reliability of Distributed Networks

摘要

This paper presents a new and efficient method based on binary decision diagram(BDD) to evaluate the K-terminal reliability of the distributed networks. Here the distributed network is modeled as a probabilistic graph G(V, E), where V is vertex set and E is the edge set. Two basic operation viz. contraction and deletion are used to make partitions the initial graph into the sub graphs. An efficient algorithm is proposed to make such partitions. Each partition is labeled by a partition string. Each of such partition string is inserted into a hash table in order to avoid duplicity. As the size of Binary Decision Diagram (BDD) is largely dependent on its ordering an efficient variable ordering is proposed. The Binary Decision Diagram(BDD) is constructed from the different partitions of the initial graph/sub graphs. In the algorithm only those partition of the graph/ sub graph are used for constructing the BDD that have no duplicity by using this variable ordering which is assured by searching the hash table. As in a BDD all the paths from the root to the leaves are disjoints, the probability of K-terminal connectivity is computed by traversing the BDD using Breadth first Search (BFS) method. For this computation of K-terminal reliability another algorithm is proposed which recursively compute the k-terminal reliability of the graph. The proposed method is well illustrated by taking a suitable example. The reliability of some important distributed networks such as Hypercube(HC), Twisted Hypercube(THC), Crossed cube(CC), Mesh, Torus are evaluated by the proposed method.