LIAO Jianxin, ZHANG Cheng, LI Tonghong, et al., “A Quasi-Optimal Probabilistic Fault Localization Algorithm in Communication Networks,” Chinese Journal of Electronics, vol. 20, no. 1, pp. 151-154, 2011,
Citation:
LIAO Jianxin, ZHANG Cheng, LI Tonghong, et al., “A Quasi-Optimal Probabilistic Fault Localization Algorithm in Communication Networks,” Chinese Journal of Electronics, vol. 20, no. 1, pp. 151-154, 2011,
LIAO Jianxin, ZHANG Cheng, LI Tonghong, et al., “A Quasi-Optimal Probabilistic Fault Localization Algorithm in Communication Networks,” Chinese Journal of Electronics, vol. 20, no. 1, pp. 151-154, 2011,
Citation:
LIAO Jianxin, ZHANG Cheng, LI Tonghong, et al., “A Quasi-Optimal Probabilistic Fault Localization Algorithm in Communication Networks,” Chinese Journal of Electronics, vol. 20, no. 1, pp. 151-154, 2011,
The problem of fault localization, which needs to find the optimal hypothesis from all possible fault hypotheses, is theoretically proven to be NP-hard. In this paper, we propose a quasi-optimal probabilistic fault localization algorithm based on the observation that there are few concurrent faults in real communication systems. A heuristic algorithm is first used to estimate the real number of concurrent faults. According to this estimated number, we then perform exhaustive search over a small specific candidate fault set, in order to obtain the accurate explanation of the observed symptoms. Simulation shows that the algorithm is quasi-optimal, effective and efficient.