基于二分圖的艦艇編隊網(wǎng)絡(luò)故障定位方法＊

（92493部隊98分隊 葫蘆島 125000）

1 引言

造成艦艇編隊網(wǎng)絡(luò)不穩(wěn)定的原因很多，但很大程度上是因為故障處理不夠及時或?qū)收咸幚矸磻^于強烈造成的。當故障發(fā)生后，網(wǎng)絡(luò)系統(tǒng)通常需要在全網(wǎng)絡(luò)進行大規(guī)模故障信息通告，這種通告不僅會造成鏈路負載的增加，也會使節(jié)點因頻繁處理故障信息而出現(xiàn)網(wǎng)絡(luò)振蕩的現(xiàn)象，影響了網(wǎng)絡(luò)的穩(wěn)定性［1］。

網(wǎng)絡(luò)故障定位是根據(jù)觀察到的故障癥狀信息推理出故障所在位置的過程。作為故障診斷中最為復雜和耗時的環(huán)節(jié)，其效果和效率對于后期的故障排除至關(guān)重要。而早期故障診斷主要是靠專家來通過人工完成，但是目前網(wǎng)絡(luò)系統(tǒng)的規(guī)模不斷擴大及網(wǎng)絡(luò)復雜性的增加，人工的診斷方法已經(jīng)不能適應需求。因此需要研究與開發(fā)一套可以智能地進行網(wǎng)絡(luò)故障診斷的技術(shù)［2］。

2 將故障診斷轉(zhuǎn)化成0-1規(guī)劃問題

在進行故障診斷時，我們把實際所觀察到的發(fā)生故障的集合用故障S的子集C來表示，C中沒有包含的故障就認為是沒有發(fā)生［3］。為便于對網(wǎng)絡(luò)的故障診斷進行研究，在此提出如下假設(shè)：

1）假定各故障之間相互無依賴關(guān)系，彼此互不影響；

2）假定事件和故障間因果映射的強度固定不變。也就是說，不論故障ti是否發(fā)生或者何時發(fā)生，事件ci總能以相同的概率強度發(fā)生。

通過基于二分圖的故障診斷，從候選的故障集合T內(nèi)找出故障假設(shè)X?T，使得此故障假設(shè)能夠發(fā)生的概率最大，即

式中c′代表網(wǎng)絡(luò)中能夠觀察到的事件的集合。由貝葉斯公式可得：

為了可以突出地描述問題，本文定義了一個k維的向量。其中k表示網(wǎng)絡(luò)中的所有可能出現(xiàn)的故障個數(shù)，每個故障ti與故障假設(shè)X之間存在著以下關(guān)系：

因為P（c′）為常數(shù)，所以求式（2）的最大值問題就變?yōu)榍笫剑?）的最大值問題。

在基于二分圖的網(wǎng)絡(luò)故障模型里有：

綜合式（1）～式（5），就可得到基于二分圖的網(wǎng)絡(luò)故障診斷問題最后的目標函數(shù)：

式中T＊表示故障集合T減掉與觀察事件所對應故障集合T′的值，即T′＝T-T＊。根據(jù)故障診斷和定位的原理，對每一個觀察事件ci而言，其最優(yōu)解中應至少含有一個故障ti，即當＞0時，有故障ti存在。因此，在網(wǎng)絡(luò)的故障診斷中，對每一個能夠觀察到的事件，其結(jié)果中一定至少存在一個故障與之對應。假設(shè)矩陣B是由關(guān)聯(lián)矩陣所得到的一個結(jié)果矩陣，其中，矩陣每一行代表一個事件ci所對應故障，即這些故障將一定會

式中，代表一個維的列向量。將式（4）取對數(shù)，就可以得到式（8）。

因此，可以將網(wǎng)絡(luò)故障的診斷問題轉(zhuǎn)化成以下的最小化求解問題：

從式（10）能夠得出網(wǎng)絡(luò)故障的診斷問題在實質(zhì)上就是一個求解0-1最優(yōu)化的問題。通常0-1規(guī)劃問題采用窮舉法來求解，另外也有分枝定界方法及拉格朗日方法等。其中，分支定界求法是特殊的一種隱枚舉方法，但是故障診斷中，目標的松弛下界不易求解，因此該方法計算量很大。因此，本文采用基于免疫遺傳進化的算法來求解此最優(yōu)化問題。

3 基于免疫遺傳算法的定位方法求解

算法的總體思路為：為增強種群動態(tài)環(huán)境下探索的力度，在遺傳的同時引進了雜合映射的思想來防止種群進化信息出現(xiàn)停滯。為了使個體能夠?qū)收线M行更快響應，在檢測到系統(tǒng)可能發(fā)生故障時，將有價值的原記憶信息重新進行激活。將和故障狀態(tài)最能夠相匹配的個體遺傳和變異，一方面擴大搜索的空間，另一方面兼顧尋找最優(yōu)解速度。從而使種群可以更快地追蹤系統(tǒng)的狀態(tài)變化。

圖1 映射機制舉例

假定在t代種群中進行遺傳的個體數(shù)目以概率pd進行選擇［6］。將數(shù)目較少的基因座的值叫做該基因座的弱勢基因值，反之稱為強勢基因值。按照雜合子的原理，通過適應性地調(diào)整強弱勢基因值的數(shù)量來對基因的突變概率進行控制。用與來分別代表弱勢基因值與強勢基因值間映射的概率。映射關(guān)系舉例如圖1所示。

與的計算過程為：

1）設(shè)種群數(shù)目是NP，編碼長度是L。Ⅰk（t）代表第t代個體中第k個基因座的弱勢基因值的期望個數(shù)，用γk（t）、ηk（t）分別代表非遺傳個體與遺傳個體中的第k個基因值是弱勢基因值的個體數(shù)目，從而得到

令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。根據(jù)式（11）可知，γk（t）＋ηk（t）＜Ⅰk（t）。由上式可取（t）＝min，1）×ε，其中ε∈［0，1］。相反，則有（t）＝（t）＝0?；诿庖哌z傳算法的故障定位方法的步驟如圖2所示。

4 算法的性能測試與結(jié)果分析

按照式（10）產(chǎn)生模板T，然后將其與目標串（第t代個體）X做“異或”（“⊕”）運算，異或運算的規(guī)則為0⊕0＝0，0⊕1＝1，1⊕1＝0。若在模板T中的某一位值是1，則進行位運算操作后，目標串X的相應位就發(fā)生變化（由0變?yōu)?，或由1變?yōu)?）。而模板的位值是0時，目標串X中相應的位則會保持不變。因此，可將T的位值是1的位和模板的長度之比看作是故障率的大小。下面定義幾個參數(shù)：

設(shè)網(wǎng)絡(luò)Ni中隨機產(chǎn)生鏈路故障數(shù)為，故障集為Wi，故障的定位結(jié)果為?Wi。故障檢測率誤檢率

圖2 基于免疫遺傳算法的故障定位方法設(shè)計步驟

在仿真中，本文所提的算法與IHU（Incremental Hypothesis Updating）算法和窮舉法作對比，分別得到了TP、FP及故障診斷時間T的值。仿真的結(jié)果如圖3所示。

圖3 仿真結(jié)果

從圖3可以看出，隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加，網(wǎng)絡(luò)規(guī)模的擴大，三種方法的性能都有所降低，其中窮舉法由于在網(wǎng)絡(luò)規(guī)模增大情況下復雜性的增加而性能迅速降低，但是從總體上來說，免疫遺傳定位法的性能始終優(yōu)于其余兩種方法。免疫遺傳算法的故障定位檢測率始終保持在0．95以上，誤檢率能保持在0．02以下，這與基于免疫遺傳算法的數(shù)據(jù)計算準確性有關(guān)，故障定位時間與IHU 算法相差不大，但明顯低于窮舉法。

5 結(jié)語

本文提出了基于免疫遺傳算法的故障定位機制，仿真結(jié)果表明其有效性良好。尤其當網(wǎng)絡(luò)規(guī)模較大或適中時，其優(yōu)勢則體現(xiàn)更加明顯。這主要因為當網(wǎng)絡(luò)規(guī)模較大時，歷史的記憶信息可對相似網(wǎng)絡(luò)狀況下的網(wǎng)絡(luò)尋優(yōu)有很好的指導意義。

［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］楊嬌．二分圖網(wǎng)絡(luò)故障傳播模型與故障診斷算法研究［D］．沈陽：東北大學，2010，12：22-40．

［7］王洪峰，汪定偉，楊圣祥．動態(tài)環(huán)境中的進化算法［J］．控制與決策，2007，22（2）：127-131．

［8］劉黎黎，汪定偉．基于雜合機制的免疫遺傳算法在動態(tài)問題中的應用［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．