A Mixed Integer Programming Based Recursive Variance Reduction Method for Reliability Evaluation of Linear Sensor Systems

摘要

Linear models have been successfully used to establish the connections between sensor measurements and source variables in sensor networks. Sensor failures are a leading concern during the estimation of these source variables that cannot be measured directly. The reliability of a sensor system is a probabilistic evaluation of the ability of a system to withstand sensor failures. Finding the exact reliability of a linear sensor system is proven to be a #P problem. Consequently, for most practical systems, it is highly unlikely to obtain exact solutions to this problem within a reasonable timeframe. A viable alternative is to estimate the reliability using the crude Monte Carlo method. However, this method is known to be inefficient for highly reliable systems. An improved Monte Carlo approach called the Recursive Variance Reduction (RVR) method is commonly used in the literature to obtain better reliable estimates. However, the accuracy of this method banks heavily on the approach used in finding minimal cut sets of the linear sensor system. In this paper, we introduce two enhanced RVR methods in which mixed integer programming algorithms are deployed to find minimal cut sets that significantly improve the accuracy of the overall RVR technique. A case study over a wide range of test instances is conducted to establish the efficiency of the proposed methods.