基于二分图的舰艇编队网络故障定位方法＊

（92493部队98分队 葫芦岛 125000）

1 引言

造成舰艇编队网络不稳定的原因很多，但很大程度上是因为故障处理不够及时或对故障处理反应过于强烈造成的。当故障发生后，网络系统通常需要在全网络进行大规模故障信息通告，这种通告不仅会造成链路负载的增加，也会使节点因频繁处理故障信息而出现网络振荡的现象，影响了网络的稳定性［1］。

网络故障定位是根据观察到的故障症状信息推理出故障所在位置的过程。作为故障诊断中最为复杂和耗时的环节，其效果和效率对于后期的故障排除至关重要。而早期故障诊断主要是靠专家来通过人工完成，但是目前网络系统的规模不断扩大及网络复杂性的增加，人工的诊断方法已经不能适应需求。因此需要研究与开发一套可以智能地进行网络故障诊断的技术［2］。

2 将故障诊断转化成0-1规划问题

在进行故障诊断时，我们把实际所观察到的发生故障的集合用故障S的子集C来表示，C中没有包含的故障就认为是没有发生［3］。为便于对网络的故障诊断进行研究，在此提出如下假设：

1）假定各故障之间相互无依赖关系，彼此互不影响；

2）假定事件和故障间因果映射的强度固定不变。也就是说，不论故障ti是否发生或者何时发生，事件ci总能以相同的概率强度发生。

通过基于二分图的故障诊断，从候选的故障集合T内找出故障假设X⊆T，使得此故障假设能够发生的概率最大，即

式中c′代表网络中能够观察到的事件的集合。由贝叶斯公式可得：

为了可以突出地描述问题，本文定义了一个k维的向量。其中k表示网络中的所有可能出现的故障个数，每个故障ti与故障假设X之间存在着以下关系：

因为P（c′）为常数，所以求式（2）的最大值问题就变为求式（4）的最大值问题。

在基于二分图的网络故障模型里有：

综合式（1）～式（5），就可得到基于二分图的网络故障诊断问题最后的目标函数：

式中T＊表示故障集合T减掉与观察事件所对应故障集合T′的值，即T′＝T-T＊。根据故障诊断和定位的原理，对每一个观察事件ci而言，其最优解中应至少含有一个故障ti，即当＞0时，有故障ti存在。因此，在网络的故障诊断中，对每一个能够观察到的事件，其结果中一定至少存在一个故障与之对应。假设矩阵B是由关联矩阵所得到的一个结果矩阵，其中，矩阵每一行代表一个事件ci所对应故障，即这些故障将一定会

式中，代表一个维的列向量。将式（4）取对数，就可以得到式（8）。

因此，可以将网络故障的诊断问题转化成以下的最小化求解问题：

从式（10）能够得出网络故障的诊断问题在实质上就是一个求解0-1最优化的问题。通常0-1规划问题采用穷举法来求解，另外也有分枝定界方法及拉格朗日方法等。其中，分支定界求法是特殊的一种隐枚举方法，但是故障诊断中，目标的松弛下界不易求解，因此该方法计算量很大。因此，本文采用基于免疫遗传进化的算法来求解此最优化问题。

3 基于免疫遗传算法的定位方法求解

算法的总体思路为：为增强种群动态环境下探索的力度，在遗传的同时引进了杂合映射的思想来防止种群进化信息出现停滞。为了使个体能够对故障进行更快响应，在检测到系统可能发生故障时，将有价值的原记忆信息重新进行激活。将和故障状态最能够相匹配的个体遗传和变异，一方面扩大搜索的空间，另一方面兼顾寻找最优解速度。从而使种群可以更快地追踪系统的状态变化。

图1 映射机制举例

假定在t代种群中进行遗传的个体数目以概率pd进行选择［6］。将数目较少的基因座的值叫做该基因座的弱势基因值，反之称为强势基因值。按照杂合子的原理，通过适应性地调整强弱势基因值的数量来对基因的突变概率进行控制。用与来分别代表弱势基因值与强势基因值间映射的概率。映射关系举例如图1所示。

与的计算过程为：

1）设种群数目是NP，编码长度是L。Ⅰk（t）代表第t代个体中第k个基因座的弱势基因值的期望个数，用γk（t）、ηk（t）分别代表非遗传个体与遗传个体中的第k个基因值是弱势基因值的个体数目，从而得到

令ND≤NP／2，则由（t）∈［0，1］得

2）对其分两种情况进行讨论：

（1）当Nc＝ηk（t），（t）＝（t）＝0时，染色体上的基因座都是弱势基因值，不进行运算。

（2）当Nc＞ηk（t）时，若ηk（t）＝0，则染色体的第k位上不存在弱势基因，因此（t）＝若ηk（t）＞0则有

此不等式能够成立的边界条件为γk（t）≤ηk（t）≤γk（t）＋Nc。根据式（11）可知，γk（t）＋ηk（t）＜Ⅰk（t）。由上式可取（t）＝min，1）×ε，其中ε∈［0，1］。相反，则有（t）＝（t）＝0。基于免疫遗传算法的故障定位方法的步骤如图2所示。

4 算法的性能测试与结果分析

按照式（10）产生模板T，然后将其与目标串（第t代个体）X做“异或”（“⊕”）运算，异或运算的规则为0⊕0＝0，0⊕1＝1，1⊕1＝0。若在模板T中的某一位值是1，则进行位运算操作后，目标串X的相应位就发生变化（由0变为1，或由1变为0）。而模板的位值是0时，目标串X中相应的位则会保持不变。因此，可将T的位值是1的位和模板的长度之比看作是故障率的大小。下面定义几个参数：

设网络Ni中随机产生链路故障数为，故障集为Wi，故障的定位结果为⊆Wi。故障检测率误检率

图2 基于免疫遗传算法的故障定位方法设计步骤

在仿真中，本文所提的算法与IHU（Incremental Hypothesis Updating）算法和穷举法作对比，分别得到了TP、FP及故障诊断时间T的值。仿真的结果如图3所示。

图3 仿真结果

从图3可以看出，随着网络节点数的增加，网络规模的扩大，三种方法的性能都有所降低，其中穷举法由于在网络规模增大情况下复杂性的增加而性能迅速降低，但是从总体上来说，免疫遗传定位法的性能始终优于其余两种方法。免疫遗传算法的故障定位检测率始终保持在0．95以上，误检率能保持在0．02以下，这与基于免疫遗传算法的数据计算准确性有关，故障定位时间与IHU 算法相差不大，但明显低于穷举法。

5 结语

本文提出了基于免疫遗传算法的故障定位机制，仿真结果表明其有效性良好。尤其当网络规模较大或适中时，其优势则体现更加明显。这主要因为当网络规模较大时，历史的记忆信息可对相似网络状况下的网络寻优有很好的指导意义。

［1］Liu L L，Wang D W，Ip W H．A permutation-based dual genetic algorithm for dynamic optimization problems［J］．Soft Computing，2008，13（7）：725-738．

［2］Howard F．Lipson，David A．Fisher．Survivability-A New Technical and Business Perspective on Security［C］／／Proceedings of the New Security Paradigms Workshop，1999：76-81．

［3］Nancy R．Mead，Robert J．Ellison．Survivable Net-work Analysis Method［EB／OL］．http：／／www．cert．org／archive／pdf／00tr013．pdf，2000．

［4］Harmer P K，Williams P D，Gunsch G H，et al．An artificial immune system architecture for computer security applications［J］．IEEE Transactions on Evolutionary Computation，2002，6（3）：252-280．

［5］Hong Zheng，Jingxin Zhang，Saeid Nahavandi．Learning to detect objects by artificial immune approaches［J］．Future Genaration Computer Systems，2004，20：1197-1198．

［6］杨娇．二分图网络故障传播模型与故障诊断算法研究［D］．沈阳：东北大学，2010，12：22-40．

［7］王洪峰，汪定伟，杨圣祥．动态环境中的进化算法［J］．控制与决策，2007，22（2）：127-131．

［8］刘黎黎，汪定伟．基于杂合机制的免疫遗传算法在动态问题中的应用［J］．控制与决策，2009，12（24）：1841-1845．

［9］Zhang Q．Probabilistic Reasoning based on Dynamic Causality Tree Diagrams［J］．Reliability Engineering and System Safety，1994，46：209-220．

［10］Garza C L，Pablo N J，Garza C M，et al．Fault diagnosis of industrial systems with Bayesian networks and neural networks［J］．Computer Science，2008，5317（11）：998-1008．

［11］Li Qing，Xu J Z．Power system fault diagnosis based on subjective Bayesian approach［J］．Automation of Electric Power Systems，2007，31（15）：46-50．