高鑫

摘要针对基于贝叶斯疑似度（Bayesian Suspected Degree，BSD）故障定位算法依赖于故障先验概率和条件概率的缺陷，设计了基于最大症状覆盖率（Maximum Covering Rate algorithm，MCRA）的故障定位算法。MCRA算法以二分图作为故障传播模型，引入了症状覆盖率概念。通过启发式的探测策略，对症状域中每个故障求解症状覆盖率。如果前k个最大症状覆盖率所对应的故障完全覆盖可观察症状集合时，则将这k个故障作为定位结果。MCRA突破了缺乏历史故障统计与分析而无法获取故障发生先验概率和条件概率的限制，利用症状覆盖率实现对贝叶斯疑似度的近似估计，实现在缺乏历史故障统计数据故障定位中的应用。

关键词故障定位；网络管理；DVB-RCS；二分图；故障传播模型

中图分类号：TP393 文献标识码：A 文章编号：1671-7597（2014）12-0032-03

故障定位是从症状和故障之间的非确定性对应关系推理出故障所在精确位置的过程。基于图论的故障定位不受样本条件的限制，成为一种有效的故障定位方法[1]，分为两部分：故障传播模型[2]（Fault Propagation Model，FPM）的建立和故障定位技术。二分图作为一种特殊的因果图[3]，简化了故障与症状之间的耦合关系，具有较低的计算复杂度，因此采用基于二分图的FPM。建立FPM之后将故障定位问题转化为遍历二分图，从故障集合中寻找出对症状集合的最小覆盖。现有求解症状集合最小覆盖的故障定位算法[4-6]依赖于故障发生先验概率和条件概率，而它们受历史数据统计和专家主观判断的影响，使得这类算法无法适用于缺乏历史统计数据的故障定位应用中。

借鉴贝叶斯疑似度算法（Bayesian Suspected Degree，BSD）[4]设计了基于最大症状覆盖率（Maximum Covering Rate Algorithm，MCRA）算法，使得MCRA算法不依赖于故障发生先验概率和条件概率。

1基于二分图的FPM

为基于二分图的FPM，由故障节点集合F、症状节点集合S、边集合组成。与均非空且，其中n表示故障节点的数量，m表示症状节点的数量。表示故障节点引发症状节点出现的因果关系。图1表示了由3个故障节点和4个症状节点组成的基于二分图的故障传播模型。

图1基于二分图的故障传播模型

2MCRA故障定位算法

通过借鉴贝叶斯疑似度提出了症状覆盖率的概念，使得MCRA具有和基于贝叶斯疑似度的求解症状集合最小覆盖算法相同的时间复杂度。同时MCRA不依赖于故障先验概率和条件概率，实现在缺乏历史数据统计故障定位系统中应用。

2.1 相关概念定义及算法分析

设症状域，代表与症状相关联的所有故障的集合；故障域，代表与相关联的所有症状的集合。

定义1：故障在观察到的症状节点集合中解释症状数量与其在症状节点集合S中解释症状数量的比值称为症状覆盖率，其表达式如式（1）所示。

（1）

MCRA故障定位算法的主要思想为：通过启发式的探测策略，找出最有可能产生这些症状的故障，实现对的最小覆盖；对症状域中每个故障求解症状覆盖率，构成集合，并按症状覆盖率大小进行排序。当中前k个最大症状覆盖率所对应的故障完全覆盖了可观察到的症状时，就认为找到了最小覆盖集合。

MCRA故障定位算法对故障加入最小覆盖集合的评估方法进行了修改，由引发集合中出现症状的绝对数量转变为出现症状的比例，放大了集合中备选故障之间的差别。将加入至最小覆盖集合之后，也未对所对应的症状从中删除。这两方面可以避免绝对数量过少而使得绝对数量也过少，也避免了因为删除交叉症状引起后续备选故障选择的误差，从而导致故障被加入最小覆盖集合之前而丢弃情况的发生。同时对中备选故障仅需要一次症状覆盖率，降低了时间复杂度。

2.2 MCRA算法

执行故障定位后的输出能够对做出最优解释的故障假设集合H具有以下性质：1）中的每个症状可被故障假设中的至少一个故障所解释；2）故障假设集合H所包含的故障，具有可能产生中的症状。MCRA算法步骤如下：

Begin

1）故障假设集合Φ，初始化症状集Φ；

2）找出中每一个症状的可能故障源，构成待选故障集合；

；

3）对应中的每一个故障，计算其症状覆盖率，加入集合中；按症状覆盖率对集合中故障降序排序；

4）依次取出循环执行，直到；

获取所对应的；如果，则，；

5）输出故障假设集合。

End

在最坏情况下，所有可观察的症状都出现，即，每一个故障只能解释一个症状，即。MCRA对求解一次症状覆盖率，其时间复杂度为O（），较MCA故障定位算法降低了倍。实现了更快速地完成故障定位，可以将其应用于实时系统的故障定位中。

3数值实例

本节首先建立故障定位仿真模型，然后分别利用MCRA、BSD以及最大覆盖故障定位算法（Max Covering Algorithm，MCA）来执行故障定位。对不同算法所产生结果进行比较，并分析其中的原因。采用检测率（Detection Rate，DR）和检测率方差（Variance of Detection Rate，VDR）来评估它们的性能，其定义如式（2）和式（3）：

（2）

（3）

其中，表示实际发生的故障集合，表示由故障定位算法所输出的故障假设集合，表示故障场景中的仿真案例数量。

表1仿真模型参数

仿真参数 参数取值

节点之间距离d 集合{1，2，3，…，100}中随机取值

仿真案例数量 500

故障发生概率 服从[0.001，0.01]的均匀分布

故障与症状之间的条件概率 服从（0，1）的均匀分布

网络节点数量 10-100

OR 50%

故障定位仿真模型运行在配置为1.8GHz Inter（R） Core（TM）2 Duo CPU和内存为2.0GB的计算机中进行，其参数如表1所示。首先随机产生包含n个节点的无向网络G，网络G中边的权值随机产生，表示节点之间的距离d。利用普里姆（Kruskal）算法求出网络G的最小生成树，利用迪杰斯特拉（Dijkstra）算法求出最小生成树中任意两节点之间的路径，得出路径矩阵。网络G中的边称为链路（Link），根据路径矩阵可知一条路径由多个链路构成。如果一条链路出现中断，则导致了多条路径出现异常。因此，将链路中断表示为故障，而将路径的异常现象表示为症状。显然，一个故障的发生将引起多个症状的出现。在网络G中，故障总数量为，症状总数量为。然后通过遍历路径矩阵，确定故障集合F与症状集合S之间的映射关系，建立基于二分图的FPM 。故障发生概率和故障和症状之间的条件概率都随机产生。

在每一个仿真案例中，随机选择故障集合作为发生的故障，设定集合包括实际发生故障数量为1，2，3，4，6的比例为30%，25%，20%，15%，10%。从症状集合S中随机选取实际能够观察到的症状集合表示为可观察症状集合，故障观察率（OR）为。从所有症状中随机选择个症状构成可观察症状集合，之后取与中故障可引发症状的集合的交集，构成实际症状集合。分别利用MCRA、BSD以及MCA算法来确定故障原因，并分析不同故障定位算法的性能。

按仿真场景参数取值来执行仿真，图2对MCRA、BSD以及MCA算法所取得的故障检测率进行了比较。由图2可知，MCRA的故障检测率为74.00%~99.80%，平均为96.87%；BSD的故障检测率为76.67%~99.70%，平均为96.79%；MCA的故障检测率为78.58%~95.93%，平均为92.10%。

endprint

图2故障检测率比较

图3故障检测率方差比较

按仿真场景参数取值来执行仿真，图3对MCRA、BSD以及MCA算法所取得的故障检测率方差进行了比较。由图3可知，MCRA的故障检测率方差为0.000602~0.088112，平均为0.0097；BSD的故障检测率方差为0.001019~0.073509，平均为0.0099；MCA的故障检测率为方差0.013985~0.069121，平均为0.0261。

图4给出了故障误判率的比较结果。由某一故障而引发对应症状出现的数量具有一定的不确定性，而所引发症状也具有一定的随机性。MCRA在无法获取故障发生的先验概率和条件概率的条件下，通过计算症状覆盖率来评估每个故障发生的可能性，实现了与BSD近似相同的故障检测率。同时在集合中不删除故障可以解释的症状，直到覆盖整个为止，避免了因为删除交叉症状引起后续备选故障选择的误差。MCA算法只找出解释症状数量最多的故障加入至故障假设集合，只是考虑了出现症状的绝对数量；从中删除symptom（f）的形成新的，直至，影响了后续备选故障的准确选择。在仿真场景中任意数量网络节点的情况下，MCRA和BSD算法的故障检测率始终高于MCR算法的故障检测率。

图4故障误判率比较

尽管在实际系统中无法准确获取故障发生的先验概率和转移概率，但BSD算法得出的故障检测率和误判率可以作为一种理论极限。MCRA通过计算症状覆盖率来代替贝叶斯疑似度，尽管在故障检测率方面可以实现和BSD算法一样的性能，但其故障检测率变化幅度也相对较大。原因是由于MCRA算法未考虑故障发生的先验概率和转移概率，得到最小覆盖集合所包括故障的数量多于BSD。

4结论

本文通过引入症状覆盖率而提出了以二分图作为故障传播模型的MCRA故障定位算法。MCRA利用症状覆盖率实现对贝叶斯疑似度的近似估计， 避免了依赖故障发生先验概率和条件概率的限制。如何将MCRA与主动故障定位技术相结合，利用探针来提升故障检测率并降低误检率成为下一步的研究内容。

参考文献

[1]郑秋华.网络故障智能定位关键技术的研究[D].杭州：浙江大学，2007.

[2]Steinder M， Sethi A S. Probabilistic Event-driven Fault Diagnosis Through Incremental Hypothesis Updating. IFIP/IEEE International Symposium on Integrated Network Management （IM）， Colorado Springs， USA， March 24-28，2003.

[3]Yemini S， Kliger A， Mozes S， et al. High Speed and Robust Event Correlation. Communications Magazine， 1996，34（5）：82-90.

[4]张成，廖建新，朱晓民.基于贝叶斯疑似度的启发式故障定位算法[J].软件学报，2010，21（10）：2610-2621.

[5]黄晓慧，邹仕洪，褚灵伟，等.Internet服务故障管理：分层模型和算法[J].软件学报，2007，18（10）：2584-2594.

[6]Steinder M， Sethi A S. Probabilistic Fault Localization in Communication Systems Using Belief Networks. IEEE/ACM Transactions on Networking，2004，12（5）：809-822.

endprint

图2故障检测率比较

图3故障检测率方差比较

按仿真场景参数取值来执行仿真，图3对MCRA、BSD以及MCA算法所取得的故障检测率方差进行了比较。由图3可知，MCRA的故障检测率方差为0.000602~0.088112，平均为0.0097；BSD的故障检测率方差为0.001019~0.073509，平均为0.0099；MCA的故障检测率为方差0.013985~0.069121，平均为0.0261。

图4给出了故障误判率的比较结果。由某一故障而引发对应症状出现的数量具有一定的不确定性，而所引发症状也具有一定的随机性。MCRA在无法获取故障发生的先验概率和条件概率的条件下，通过计算症状覆盖率来评估每个故障发生的可能性，实现了与BSD近似相同的故障检测率。同时在集合中不删除故障可以解释的症状，直到覆盖整个为止，避免了因为删除交叉症状引起后续备选故障选择的误差。MCA算法只找出解释症状数量最多的故障加入至故障假设集合，只是考虑了出现症状的绝对数量；从中删除symptom（f）的形成新的，直至，影响了后续备选故障的准确选择。在仿真场景中任意数量网络节点的情况下，MCRA和BSD算法的故障检测率始终高于MCR算法的故障检测率。

图4故障误判率比较

尽管在实际系统中无法准确获取故障发生的先验概率和转移概率，但BSD算法得出的故障检测率和误判率可以作为一种理论极限。MCRA通过计算症状覆盖率来代替贝叶斯疑似度，尽管在故障检测率方面可以实现和BSD算法一样的性能，但其故障检测率变化幅度也相对较大。原因是由于MCRA算法未考虑故障发生的先验概率和转移概率，得到最小覆盖集合所包括故障的数量多于BSD。

4结论

本文通过引入症状覆盖率而提出了以二分图作为故障传播模型的MCRA故障定位算法。MCRA利用症状覆盖率实现对贝叶斯疑似度的近似估计， 避免了依赖故障发生先验概率和条件概率的限制。如何将MCRA与主动故障定位技术相结合，利用探针来提升故障检测率并降低误检率成为下一步的研究内容。

参考文献

[1]郑秋华.网络故障智能定位关键技术的研究[D].杭州：浙江大学，2007.

[2]Steinder M， Sethi A S. Probabilistic Event-driven Fault Diagnosis Through Incremental Hypothesis Updating. IFIP/IEEE International Symposium on Integrated Network Management （IM）， Colorado Springs， USA， March 24-28，2003.

[3]Yemini S， Kliger A， Mozes S， et al. High Speed and Robust Event Correlation. Communications Magazine， 1996，34（5）：82-90.

[4]张成，廖建新，朱晓民.基于贝叶斯疑似度的启发式故障定位算法[J].软件学报，2010，21（10）：2610-2621.

[5]黄晓慧，邹仕洪，褚灵伟，等.Internet服务故障管理：分层模型和算法[J].软件学报，2007，18（10）：2584-2594.

[6]Steinder M， Sethi A S. Probabilistic Fault Localization in Communication Systems Using Belief Networks. IEEE/ACM Transactions on Networking，2004，12（5）：809-822.

endprint

图2故障检测率比较

图3故障检测率方差比较

按仿真场景参数取值来执行仿真，图3对MCRA、BSD以及MCA算法所取得的故障检测率方差进行了比较。由图3可知，MCRA的故障检测率方差为0.000602~0.088112，平均为0.0097；BSD的故障检测率方差为0.001019~0.073509，平均为0.0099；MCA的故障检测率为方差0.013985~0.069121，平均为0.0261。

图4给出了故障误判率的比较结果。由某一故障而引发对应症状出现的数量具有一定的不确定性，而所引发症状也具有一定的随机性。MCRA在无法获取故障发生的先验概率和条件概率的条件下，通过计算症状覆盖率来评估每个故障发生的可能性，实现了与BSD近似相同的故障检测率。同时在集合中不删除故障可以解释的症状，直到覆盖整个为止，避免了因为删除交叉症状引起后续备选故障选择的误差。MCA算法只找出解释症状数量最多的故障加入至故障假设集合，只是考虑了出现症状的绝对数量；从中删除symptom（f）的形成新的，直至，影响了后续备选故障的准确选择。在仿真场景中任意数量网络节点的情况下，MCRA和BSD算法的故障检测率始终高于MCR算法的故障检测率。

图4故障误判率比较

尽管在实际系统中无法准确获取故障发生的先验概率和转移概率，但BSD算法得出的故障检测率和误判率可以作为一种理论极限。MCRA通过计算症状覆盖率来代替贝叶斯疑似度，尽管在故障检测率方面可以实现和BSD算法一样的性能，但其故障检测率变化幅度也相对较大。原因是由于MCRA算法未考虑故障发生的先验概率和转移概率，得到最小覆盖集合所包括故障的数量多于BSD。

4结论

本文通过引入症状覆盖率而提出了以二分图作为故障传播模型的MCRA故障定位算法。MCRA利用症状覆盖率实现对贝叶斯疑似度的近似估计， 避免了依赖故障发生先验概率和条件概率的限制。如何将MCRA与主动故障定位技术相结合，利用探针来提升故障检测率并降低误检率成为下一步的研究内容。

参考文献

[1]郑秋华.网络故障智能定位关键技术的研究[D].杭州：浙江大学，2007.

[2]Steinder M， Sethi A S. Probabilistic Event-driven Fault Diagnosis Through Incremental Hypothesis Updating. IFIP/IEEE International Symposium on Integrated Network Management （IM）， Colorado Springs， USA， March 24-28，2003.

[3]Yemini S， Kliger A， Mozes S， et al. High Speed and Robust Event Correlation. Communications Magazine， 1996，34（5）：82-90.

[4]张成，廖建新，朱晓民.基于贝叶斯疑似度的启发式故障定位算法[J].软件学报，2010，21（10）：2610-2621.

[5]黄晓慧，邹仕洪，褚灵伟，等.Internet服务故障管理：分层模型和算法[J].软件学报，2007，18（10）：2584-2594.

[6]Steinder M， Sethi A S. Probabilistic Fault Localization in Communication Systems Using Belief Networks. IEEE/ACM Transactions on Networking，2004，12（5）：809-822.

endprint