| 摘要: |
| 故障定位问题理论上已经证明为NP-Hard问题.为了降低计算复杂度,以概率加权的二分图作为故障传播模型,提出了一种基于贝叶斯疑似度的启发式故障定位算法(Bayesian suspected degree fault localization algorithm,简称BSD).引入贝叶斯疑似度,对所有故障仅计算一遍;同时采用增量覆盖方式,使算法具有较低的计算复杂度O(|F|×|S|).仿真实验结果表明,BSD算法具有较高的故障检测率和较低的故障误检率,即使在部分告警无法观察、告警丢失和虚假等情况下,算法依然具有较高的故障检测率.BSD算法具有多项式计算复杂度,可以满足大规模通信网故障定位的要求. |
| 关键词: 故障管理 故障诊断 故障定位 故障传播模型 贝叶斯公式 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Science Fund for Distinguished Young Scholars of China under Grant No.60525110 (国家杰出青年科学基金); the National Basic Research Program of China under Grant Nos.2007CB307100, 2007CB307103 (国家重点基础研究发展计划(973)); the Development Fund Project for Electronic and Information Industry of China (电子信息产业发展基金) |
|
| Heuristic Fault Localization Algorithm Based on Bayesian Suspected Degree |
|
ZHANG Cheng,LIAO Jian-Xin,ZHU Xiao-Min
|
| Abstract: |
| Fault localization has theoretically been proven to be NP-hard. This paper takes a weighted bipartite graph, as fault propagation model, and proposes a heuristic fault localization algorithm based on Bayesian suspected degree (BSD) to reduce the computational complexity. It introduces a metric of BSD, which needs only to be calculated once, and uses incremental coverage, which makes the algorithm a low computation complexity O(|F|×|S|). Simulation results show that the algorithm has a high fault detection rate as well as low false positive rate and performs well even in the presence of unobserved and suspicious alarms. The algorithm, which has a polynomial computational complexity, can be applied to a large-scale communication network. |
| Key words: fault management fault diagnosis fault localization fault propagation model Bayes’ formula |
