关键词: 故障诊断, 近似算法, 动态贝叶斯, 时间复杂度

Abstract:

Fault management is one of the most important parts of network management. It is a challenge problem to quickly and accurately locate the faults of network. Bayesian networks model is a prominent way to solve that problem, but it is limited when the state of the nodes changes over time. Present algorithms based on Bayesian networks model may solve the problem with higher accuracy, but the algorithms are very compex and not proper for large scale of network. A new efficient inference algorithm that can diagnosis multifault in dynamic Bayesian networks is proposed. Then, by analysis of its complexity, it is proven that the approximation algorithm has a much lower time complexity than the lower bound of exact algotithm in the dynamic Bayesian networks. Finally, the experiments show that the accuracy of the new algorithm is slightly lower than the exact inference algorithm, but its efficiency is much higher than the exact inference algorithm. This new algorithm can be applied to the large communication networks.

Key words: fault diagnosis, approximation algorithm, dynamic Bayesian networks, computational complexit