基于拉格朗日松弛和次梯度法的网络故障定位新方法  

Novel fault localization approach based on Lagrangian relaxation and subgradient method

作　　者：郑秋华[1,2] 姚敏[2] 钱沄涛[2] 

机构地区：[1]杭州电子科技大学计算机学院,杭州310018 [2]浙江大学计算机学院,杭州310027

出　　处：《系统工程理论与实践》2008年第11期155-164,共10页Systems Engineering-Theory & Practice

基　　金：浙江省科技计划重点项目(2006C21001)

摘　　要：在分析当前主要的非确定性故障定位方法基础上,提出了一种新的网络故障定位方法.该方法通过在现有二分图故障传播模型中加入虚假故障因素,提出改进的二分图故障传播模型,在该模型基础上,将故障定位问题转化为一个0-1规划的最小化问题,然后利用拉格朗日松弛和次梯度方法对问题进行求解.与现有的主要故障定位方法相比,该方法不仅具备检测系统中虚假告警的能力,而且能有效地降低故障定位时间.仿真实验表明,该方法准确率高,诊断速度快.On the basic of comparison of current non-deterministic fault localization methods, a novel approach based on lagrangian relaxation and subgradient method is proposed. By considering false faults, we present an improved bipartite graph fault propagation model. Then the localization problem is transformed into a problem of 0-1 program, and lagrangian relaxation and subgradient method are adopted to solve this 0-1 program problem. Comprised with other method, this algorithm has not only the ability to detect spurious alarms, but also can decrease the diagnosis time. Simulation results show that this algorithm gets a high accuracy and a less diagnosis time.

关 键 词：网络故障定位 二分图模型 0-1规划 拉格朗日松弛 次梯度 

分 类 号：TP393.07[自动化与计算机技术—计算机应用技术]