网络全端可靠性仿真算法研究

Simulation Algorithm Approaches for All-terminal Network Reliability

全端可靠性是指整个网络所有端点之间保持连通的概率,如何准确计算网络可靠性是个NP-hard问题.文章通过选取逐次事件估计量,研究了网络可靠性的三种仿真算法:蒙特卡罗仿真方法 MCM(Monte Carlo Method),模块化抽样方法 BS(Blocking Sampling Method)、几何抽样方法 GS(Geomtretic Sampling Method).为了比较三种仿真方法的有效性和计算全端可靠性的精确性,采用方差缩减(variance-reduction)方法进行仿真检验,并给出和分析了实验结果,结果表明每种方法有各自的优缺点和适用范围.

All-terminal network reliability is the probability which is employed to describe the connection situation between all nodes of the whole network. How to compute network reliability reliably is an NP-hard problem. This thesis studies three simulation algorithm of network reliability, such as Monte Carlo Method, Blocking Sampling Method, and Geomtretic Sampling Method. In order to compare the effectiveness of the three methods and compute the accuracy of all-terminal network reliability, variance-reduction is used and the results of the experiment are given. Numerical examples demonstrate that each method has its advantages, disadvantages and scope of application.