Heuristic And Root Node Selection Methods Research In BDD-Based Network Reliability Analysis

With the development of science and technology, network has gradually become a part of people’s daily lives. Network reliability analyze has become a hot issue. In many methods of network reliability analysis, BDD-based network reliability analysis because its high efficiency is often used for network reliability analysis. BDD-based network reliability analysis algorithm consists three main steps, look for a better performance network variable ordering, construct a BDD model equivalent to the original network, calculate the network’s reliability. When using the BDD analysis method for network reliability, efficiency calculation is directly related to the size of BDD.Large-scale BDD model will reduce the computational efficiency and the timeliness is poor. So in network reliability analysis, using small-scale BDD model on calculate the network’s reliability is necessary.When generating the BDD model, at first we need to choose a heuristic strategy for edge ordering. However, there is a huge difference between the sizes of BDD model which using different heuristic strategies. The smaller size of the BDD,the better performance of the heuristic strategy is. Therefore, the problem of how to select the smallest size of BDD model to calculate the network reliability is equivalent to how to find the heuristic strategy. In addition, before using the heuristic strategy to ordering, we should select a root node at first. The sizes of BDD that generated by different root nodes could have a huge difference. So, how to find a high-performance edge ordering root node is also equally important.This paper has made some research of choosing a heuristic and a high-performance root node that relate to the computational efficiency in network reliability analysis, the specific work of this paper mainly as follows:(1) On the side of how to choose a better performance heuristic strategy. First, we introduced the selection method of TSBS measure-based. Then introduced a new selection method which based on Fax & IFmax (Maximum Size of Boundary Sets & Index of Fmax). Last compared the performance of the two selection methods in the complex networks. We found that the measure Fmax & IF max is better than the measure TSBS in most cases. However, because of the edge ordering problem is NP problem and the complex network is small world effect and scale-free property, so it can not be guaranteed that using the proposed selection method can get the best results every time,but it will get optimum results in most cases.(2) How to choose high-performance root node to perform edge searching using a particular heuristic in BDD-based network reliability analysis. First, we introduced the measure TSBS and IFBSH which is existed in the regular network,and applied the two measure in complex networks. In most cases, the selection method based on TSBS will be able to choose better performance root node. However, the TSBS is irrelevant to{s, t},so in this case we should use the selection method which is based on IFBSH.But,when choosing the root node, IFBSH is used as secondary only when the heuristic results have same TSBS.In summary, this paper studied on choosing a heuristic and choosing a high-performance root node to perform edge searching using a particular heuristic in BDD-based network reliability analysis. And given the heuristic and root node selection methods for network reliability analysis of complex network. It’s guideline for edge ordering in BDD-based network reliability analysis.