EDGE Ordering Strategy For BDD-Based Network Reliability Analysis

In the network reliability analysis, using binary decision diagram technique to analyze the reliability of network can greatly improve the performance and efficiency. The BDD-based network reliability analysis mainly consists of three aspects:looking for a better network variable ordering, constructing a BDD equivalent to the original network, calculating the reliability of the generated BDD. And the crucial basis among these is to choose a good ordering strategy for the network edges. It can greatly improve the performance of BDD-based network reliability analysis algorithms.In the previous BDD-based network reliability analysis, depth-first search and breadth-first search are the widely-used heuristic strategies for edge ordering. Their performances were studied by many researchers, and the conclusion that performance of BFS is better than DFS was drawn on many cases (i.e., BFS can generate smaller size of BDD and spend less time than DFS). Recently, a new edge ordering strategy named priority ordering strategy was proposed. Analyzing these strategies and methods, we discovered several problems-(1) the network sample and scale tested in literature were finite, therefore strategy performance comparison is not systematic; (2) BFS is a kind of graph-based breadth search edge ordering strategy, it is unreasonable to make the ordering result depended on the numbering of network nodes; (3) with the increment of complexity of the real-world networks, these strategies might not meet the performance requirement. Thus, the design of high-performance edge ordering strategy is needed.The contribution of this thesis aims at edge ordering strategy research on BDD for network reliability analysis, including:(1) Performance analysis of the existing edge ordering strategies was studied in the regular networks. The performances of breadth-first search and priority ordering search were studied based on four kinds of benchmark regular network models. Some performance data such as binary decision diagram size and runtime under two strategies were compared emphatically through the experiments. The experimental results show that different ordering strategies fit the different network structures. These results are very important for choosing the optimal or suboptimal edge ordering strategy for the particular regular network.(2) The BFS strategy was improved in the complex network. BFS is an ordering strategy dependent on the node numbering of network, thus the ordering result is closely related with the node numbering. BFS ranking result is not only affected by the structure of the network, but also affected by artificial numbering, this is unreasonable. To improve the performance of BFS, the simple queue is replaced by priority queue attached the degree of node as the ordering parameter. And the priority of every node in priority queue is the number of unsorted edges incident to a node. Thus, we propose a novel edge ordering strategy which uses best first search based on the degree of nodes. The experimental results show that the performance of DBFS was better than BFS in complex networks.(3) The design of high quality performance edge ordering strategy based on boundary set is studied. The boundary set is an effective parameter in the process of constructing BDD. And there is a close correlation between the length of boundary set and the BDD size. Thus, a new edge ordering strategy named Snooker was proposed with the principle "the minimum length of boundary set", taking node degree as the main ordering parameter. The performances of Snooker and DBFS were compared in the samples of regular network and complex network respectively, and the research results show that the performance of Snooker was better than DBFS both in regular networks and complex networks.