Journal of Computer Applications ›› 2012, Vol. 32 ›› Issue (02): 343-346.DOI: 10.3724/SP.J.1087.2012.00343

• Network and communications • Previous Articles     Next Articles

Faulty link identification based on factor graph and sum product algorithm

LV Xiang-ling,ZHANG Zhi-yong,HU Guang-min   

  1. School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China
  • Received:2011-07-28 Revised:2011-09-23 Online:2012-02-23 Published:2012-02-01
  • Contact: LV Xiang-ling



  1. 电子科技大学 通信与信息工程学院,成都 611731
  • 通讯作者: 吕香玲
  • 作者简介:吕香玲(1987-),女,河南商丘人,硕士研究生,主要研究方向:故障链路诊断;
  • 基金资助:

Abstract: In order to estimate the prior probability of the link failure, the paper proposed a new method for estimating the link state distribution. The new scheme adopted the factor graph to describe the joint probability distribution between the link and the path, and used the sum-product algorithm to obtain the maximum posterior estimate of the state of the link, then used the failures probability of the link and the current measurement data to conclude the current state of the link. The simulation results show that, when the size of network reaches 400 nodes, the computation time of the new scheme is more than two orders of magnitude lower than the linear equations method, and has better scalability.

Key words: end-to-end measurement, faulty link identification, maximum posterior estimation, factor graph, sum product algorithm

摘要: 为求得网络内部链路的先验故障概率,提出一种估计链路状态分布的新方法。采用因子图模型描述链路状态和路径状态间的联合概率分布,并使用和积算法求得各链路状态的最大后验估计,然后利用估计出的链路故障概率和当前测量数据推断链路的当前状态。仿真结果表明,当网络规模达到400个节点时,所提方法的计算时间比联立方程组求解法低两个数量级以上,具有更好的可扩展性。

关键词: 端到端测量, 故障链路诊断, 最大后验估计, 因子图, 和积算法

CLC Number: