A Quasi-Optimal Probabilistic Fault Localization Algorithm in Communication Networks

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...

Full description

Saved in:
Bibliographic Details
Published in:电子学报：英文版 2011, Vol.20 (1), p.151-154
Main Author: LIAO Jianxin ZHANG Cheng LI Tonghong ZHU Xiaomin
Format: Article
Language:English
Subjects:
启发式算法
并发故障
故障定位算法
故障设置
穷举搜索
通信系统
通信网络
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1022-4653