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

（92493部隊(duì)98分隊(duì) 葫蘆島 125000）

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 映射機(jī)制舉例

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

與的計(jì)算過程為：

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

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

2）對(duì)其分兩種情況進(jìn)行討論：

（1）當(dāng)Nc＝ηk（t），（t）＝（t）＝0時(shí)，染色體上的基因座都是弱勢(shì)基因值，不進(jìn)行運(yùn)算。

（2）當(dāng)Nc＞ηk（t）時(shí)，若ηk（t）＝0，則染色體的第k位上不存在弱勢(shì)基因，因此（t）＝若ηk（t）＞0則有

此不等式能夠成立的邊界條件為γk（t）≤ηk（t）≤γk（t）＋Nc。根據(jù)式（11）可知，γk（t）＋ηk（t）＜Ⅰk（t）。由上式可?。╰）＝min，1）×ε，其中ε∈［0，1］。相反，則有（t）＝（t）＝0?；诿庖哌z傳算法的故障定位方法的步驟如圖2所示。

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

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

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

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

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

圖3 仿真結(jié)果

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

5 結(jié)語

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

［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］．沈陽：東北大學(xué)，2010，12：22-40．

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

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