多分辨率社團(tuán)結(jié)構(gòu)挖掘在故障定位中的應(yīng)用

禹 航，肖明清，胡雷剛，方甲永

(空軍工程大學(xué) 工程學(xué)院二系自動(dòng)測(cè)試系統(tǒng)實(shí)驗(yàn)室，西安 710038)

軍用系統(tǒng)對(duì)于容錯(cuò)性及強(qiáng)生存性有著很高的要求，并且具有在地域上分散，結(jié)構(gòu)上呈分布式的特殊性，使得軍用的分布式裝備具有眾多的功能節(jié)點(diǎn)以及復(fù)雜的交聯(lián)關(guān)系，對(duì)其進(jìn)行快速故障定位已經(jīng)成為武器裝備測(cè)試與診斷領(lǐng)域的一個(gè)研究重點(diǎn)。目前對(duì)候選故障源進(jìn)行定位的常用方法有基于故障傳播有向圖和符號(hào)有向圖的研究方法及基于定性模型的方法，但是由于分布式系統(tǒng)處于多變環(huán)境中，需要在動(dòng)態(tài)變化和難以預(yù)測(cè)的狀態(tài)條件下高效地維護(hù)和運(yùn)行，常規(guī)的故障定位方法難以獲得正確的結(jié)果。例如使用粗粒化方法［1］，可對(duì)基于時(shí)間的復(fù)雜序列進(jìn)行符號(hào)化，但不適用于結(jié)構(gòu)復(fù)雜呈現(xiàn)網(wǎng)狀結(jié)構(gòu)的系統(tǒng)的約簡(jiǎn)和推理。使用案例庫(kù)搜索方法［2］，由于案例庫(kù)規(guī)模會(huì)隨時(shí)間擴(kuò)大，會(huì)造成搜索效率降低。

復(fù)雜網(wǎng)絡(luò)理論是運(yùn)用網(wǎng)絡(luò)思維，將客觀世界中的實(shí)體抽象為網(wǎng)絡(luò)節(jié)點(diǎn)，關(guān)聯(lián)關(guān)系抽象為網(wǎng)絡(luò)中的邊，從網(wǎng)絡(luò)本身的結(jié)構(gòu)特點(diǎn)出發(fā)，進(jìn)行網(wǎng)絡(luò)性能的研究［3］。近年來(lái)，運(yùn)用復(fù)雜網(wǎng)絡(luò)理論對(duì)復(fù)雜系統(tǒng)的性能進(jìn)行研究正成為熱點(diǎn)。復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)是指在整個(gè)網(wǎng)絡(luò)中，節(jié)點(diǎn)之間的交聯(lián)關(guān)系不是均勻的，整個(gè)網(wǎng)絡(luò)由若干個(gè)由節(jié)點(diǎn)構(gòu)成的“社團(tuán)”構(gòu)成，社團(tuán)內(nèi)部節(jié)點(diǎn)之間的關(guān)系相對(duì)緊密，社團(tuán)之間的交聯(lián)關(guān)系相對(duì)稀疏［4-5］。通過(guò)對(duì)復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)進(jìn)行發(fā)掘，對(duì)理解網(wǎng)絡(luò)內(nèi)部結(jié)構(gòu)，系統(tǒng)運(yùn)行機(jī)理有著重要的意義。

1 多分辨率社團(tuán)結(jié)構(gòu)模型

運(yùn)用復(fù)雜網(wǎng)絡(luò)理論對(duì)現(xiàn)實(shí)系統(tǒng)建模時(shí)，網(wǎng)絡(luò)的節(jié)點(diǎn)代表復(fù)雜系統(tǒng)的部件、設(shè)備或模塊，邊代表部件之間的交聯(lián)關(guān)系，社團(tuán)結(jié)構(gòu)體現(xiàn)的是復(fù)雜系統(tǒng)中的交聯(lián)關(guān)系、模塊化或?qū)哟涡越Y(jié)構(gòu)。

1.1 網(wǎng)絡(luò)定義

定義1 系統(tǒng)模型S是由二元組表示S={V，E}，其中:

節(jié)點(diǎn)集合V={si|si為系統(tǒng)部件}，

邊集合E={ei，j|節(jié)點(diǎn)si指向sj的有向邊}。

定義2 模型的鄰接矩陣為P={Pi，j}，

自律分散測(cè)試系統(tǒng)由分擔(dān)功能的原子節(jié)點(diǎn)構(gòu)成。在這樣的系統(tǒng)中，原子節(jié)點(diǎn)由外界的輸入信息或從其他原子節(jié)點(diǎn)接收的信息驅(qū)動(dòng)，而且這個(gè)原子節(jié)點(diǎn)的處理結(jié)果會(huì)傳給其他原子節(jié)點(diǎn)，其他原子節(jié)點(diǎn)依次進(jìn)行類似的處理。這一驅(qū)動(dòng)條件也包含多個(gè)輸入的邏輯與(AND)、邏輯或(OR)等情況。因此，通過(guò)原子節(jié)點(diǎn)間的協(xié)調(diào)，可以實(shí)現(xiàn)系統(tǒng)整體的功能［6］。運(yùn)用復(fù)雜網(wǎng)絡(luò)理論對(duì)自律分散系統(tǒng)建模，可以表達(dá)原子節(jié)點(diǎn)間功能聯(lián)合、協(xié)調(diào)關(guān)系，并加進(jìn)驅(qū)動(dòng)條件。

考慮由N個(gè)原子節(jié)點(diǎn)(S1，S2，…，SN)組成的自律分散系統(tǒng)。假設(shè)各原子節(jié)點(diǎn)Si具有功能fi，其輸入為ui，此時(shí)輸出yi用下式表示:yi=fi(ui，y1，y2，…，yN)，其中，i=1，2，…，N。

對(duì)于一個(gè)有4個(gè)原子節(jié)點(diǎn)的自律分散系統(tǒng)來(lái)說(shuō)，其模型如圖1(a)所示，原子節(jié)點(diǎn)之間的數(shù)據(jù)驅(qū)動(dòng)關(guān)系，依據(jù)輸入、輸出，作為模型節(jié)點(diǎn)中的有向邊，圖1(b)為模型的可達(dá)矩陣。

圖1 自律分散系統(tǒng)的模型Fig.1 Model of autonomous decentralized system

如果系統(tǒng)內(nèi)部發(fā)生故障，系統(tǒng)重構(gòu)，原子節(jié)點(diǎn)間的拓?fù)潢P(guān)系發(fā)生改變，系統(tǒng)功能變化，系統(tǒng)結(jié)構(gòu)由變?yōu)?，此時(shí)，被驅(qū)動(dòng)的子系統(tǒng)變?yōu)樽酉到y(tǒng)(Si，Sk1'，Sk2'，…，Skn')，系統(tǒng)功能發(fā)生重構(gòu)，如圖2所示。原子節(jié)點(diǎn)S2失去后，系統(tǒng)模型變?yōu)閳D3(a)所述的拓?fù)浣Y(jié)構(gòu)，可達(dá)矩陣如圖3(b)所示。

圖2 系統(tǒng)故障時(shí)功能的重構(gòu)Fig.2 Function reconfiguration during system faulted

圖3 重構(gòu)后的模型及鄰接矩陣Fig.3 System model after function reconfiguration

1.2 社團(tuán)結(jié)構(gòu)

許多現(xiàn)實(shí)的復(fù)雜網(wǎng)絡(luò)中都存在著社團(tuán)結(jié)構(gòu)。2002年Girvan和Newman［4］首次提出了復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)概念，社團(tuán)就是網(wǎng)絡(luò)中的節(jié)點(diǎn)集合。社團(tuán)內(nèi)節(jié)點(diǎn)之間具有比較緊密的鏈接，而社團(tuán)之間節(jié)點(diǎn)的鏈接相對(duì)比較松散。目前，盡管社團(tuán)還沒(méi)有一個(gè)統(tǒng)一的、量化的定義，但這種定義已經(jīng)被廣大學(xué)者所接受。Radicchi等［7］提出了社團(tuán)結(jié)構(gòu)的強(qiáng)定義，即“在強(qiáng)的意義下，社團(tuán)是一個(gè)子圖，它內(nèi)部節(jié)點(diǎn)之間的聯(lián)系要大于剩余節(jié)點(diǎn)之間的聯(lián)系”。

1.3 多分辨率映射

由于復(fù)雜網(wǎng)絡(luò)具有層次性，即不同網(wǎng)絡(luò)中節(jié)點(diǎn)的組織結(jié)構(gòu)會(huì)呈現(xiàn)出不同的層次。較大的社團(tuán)中可能還會(huì)包括一些較小的社團(tuán)，并可能呈現(xiàn)出多層嵌套的狀態(tài)，在不同分辨率下對(duì)網(wǎng)絡(luò)進(jìn)行觀察，可以得到不同的網(wǎng)絡(luò)視圖，映射到自律分散系統(tǒng)的系統(tǒng)結(jié)構(gòu)層級(jí)，可以研究不同層級(jí)的系統(tǒng)結(jié)構(gòu);映射到自律分散系統(tǒng)的開(kāi)發(fā)邏輯范疇，可以得到不同層次的開(kāi)發(fā)邏輯。這樣的情形就是自律分散系統(tǒng)社團(tuán)結(jié)構(gòu)的多分辨率性。

如圖4所示的多分辨率社團(tuán)模型與自律分散系統(tǒng)的映射關(guān)系，分別顯示了多分辨率社團(tuán)模型在各層次與系統(tǒng)開(kāi)發(fā)邏輯以及系統(tǒng)結(jié)構(gòu)層級(jí)的映射關(guān)系。在底層，多分辨率社團(tuán)模型是典型的由節(jié)點(diǎn)和邊構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)，對(duì)應(yīng)自律分散系統(tǒng)開(kāi)發(fā)邏輯的可重構(gòu)單元(原子節(jié)點(diǎn))及系統(tǒng)結(jié)構(gòu)層級(jí)的實(shí)現(xiàn)元件層級(jí);通過(guò)對(duì)底層基本網(wǎng)絡(luò)進(jìn)行社團(tuán)挖掘進(jìn)行結(jié)構(gòu)約簡(jiǎn)，可以得到8個(gè)社團(tuán)，圖中由虛線劃分表示，社團(tuán)及其之間的交聯(lián)關(guān)系即構(gòu)成高分辨率社團(tuán)交聯(lián)結(jié)構(gòu)，并在此層級(jí)映射自律分散系統(tǒng)開(kāi)發(fā)邏輯中的系統(tǒng)體系邏輯以及系統(tǒng)結(jié)構(gòu)層級(jí)中的模塊結(jié)構(gòu)層級(jí);以社團(tuán)作為節(jié)點(diǎn)，即可得到較低分辨的社團(tuán)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，對(duì)社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行進(jìn)一步的社團(tuán)挖掘，可以得到3個(gè)更高層級(jí)的社團(tuán)，也就是低分辨率社團(tuán)交聯(lián)結(jié)構(gòu)，對(duì)應(yīng)自律分散系統(tǒng)開(kāi)發(fā)邏輯的功能模型以及系統(tǒng)結(jié)構(gòu)層級(jí)中的功能層級(jí)。圖4即為模型的通用映射關(guān)系，在具體研究中會(huì)依據(jù)實(shí)際進(jìn)行多分辨率建模，例如，在多重模塊嵌套的情形下，有四級(jí)分辨率下的社團(tuán)結(jié)構(gòu)模型。

圖4 社團(tuán)網(wǎng)絡(luò)多分辨率映射關(guān)系示意圖Fig.4 Multi-scale mapping relationship of community networks

由于自律分散系統(tǒng)的特殊性，具有資源動(dòng)態(tài)占有、結(jié)構(gòu)變化的特點(diǎn)，并具有多級(jí)模塊性、模塊內(nèi)部呈強(qiáng)耦合，模塊間呈弱耦合。因此，對(duì)自律分散系統(tǒng)進(jìn)行網(wǎng)絡(luò)建模，并運(yùn)用尋找網(wǎng)絡(luò)層次性社團(tuán)的發(fā)掘算法，對(duì)網(wǎng)絡(luò)進(jìn)行分層收縮約簡(jiǎn)，運(yùn)用系統(tǒng)結(jié)構(gòu)拓?fù)淠Ｐ瓦M(jìn)行系統(tǒng)結(jié)構(gòu)分析及故障傳播研究，對(duì)自律分散系統(tǒng)的快速故障定位有著重要意義。

2 社團(tuán)結(jié)構(gòu)發(fā)掘方法

2.1 基于適應(yīng)度函數(shù)局部最優(yōu)化的社團(tuán)發(fā)掘方法

對(duì)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的挖掘研究與圖論和計(jì)算機(jī)科學(xué)中的圖分割理論(Graph Partitioning)、社會(huì)學(xué)中的層次聚類方法(Hierarchical Clustering)等有密切的關(guān)系［8］。社團(tuán)挖掘的主要研究熱點(diǎn)集中在尋求一個(gè)合理而高效的算法來(lái)發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)中的社區(qū)［8-11］。研究者們已經(jīng)提出了許多有用的方法來(lái)挖掘網(wǎng)絡(luò)中的社區(qū)，如基于圖分解的方法(包括Spectral Bisection Method和Kernighan-Lin算法等)、基于社會(huì)學(xué)的方法(主要是層次聚類方法，包括單連接方法和完全連接方法等)和一些新的方法(包括去邊方法和集團(tuán)分析法等)［12-13］。

LFM算法是一種基于適應(yīng)度函數(shù)局部最優(yōu)化的方法，是基于極值優(yōu)化的思想進(jìn)行社團(tuán)結(jié)構(gòu)劃分的代表算法之一［14］。在LFM算法中，社團(tuán)的發(fā)現(xiàn)通過(guò)對(duì)定義適應(yīng)度函數(shù)fG進(jìn)行優(yōu)化取最大值來(lái)實(shí)現(xiàn):

式中fG+i(fG-i)是社團(tuán){G+i}({G-i})的適應(yīng)度函數(shù)值，反映了節(jié)點(diǎn)i加入(或被移除)社團(tuán)G后該社團(tuán)的適應(yīng)度。當(dāng)＞0，說(shuō)明點(diǎn)i加入社團(tuán)G后能使該社團(tuán)的適應(yīng)度增大，因而應(yīng)當(dāng)被包含在社團(tuán)G中;當(dāng)＜0，則點(diǎn)應(yīng)從社團(tuán)G中移除。

社團(tuán)挖掘的具體算法如下:

輸入:復(fù)雜網(wǎng)絡(luò)S={V，E}

輸出:社團(tuán)結(jié)構(gòu)集{G1，…，Gn}

步驟1:選擇一個(gè)孤立節(jié)點(diǎn)A作為社團(tuán)G的初始成員=0;

步驟2:依據(jù)式(1)計(jì)算社團(tuán)G的所有鄰居節(jié)點(diǎn)對(duì)G的適應(yīng)度貢獻(xiàn);

步驟3:選出適應(yīng)度函數(shù)值最大的鄰居節(jié)點(diǎn)，把它加到社團(tuán)G中，得到新的社團(tuán)G';

步驟4:根據(jù)式(2)重新計(jì)算社團(tuán)G'中所有節(jié)點(diǎn)對(duì)社團(tuán)G'的適應(yīng)度貢獻(xiàn);

步驟5:選出適應(yīng)度函數(shù)值為負(fù)的節(jié)點(diǎn)，將其從社團(tuán)G'中刪除，得到新的社團(tuán)G″;

步驟6:如果步驟5發(fā)生，則返回步驟4，如果所有節(jié)點(diǎn)的適應(yīng)度貢獻(xiàn)都為正，則返回步驟2。上述過(guò)程循環(huán)執(zhí)行，直到社團(tuán)G的的所有鄰居節(jié)點(diǎn)對(duì)G的貢獻(xiàn)值都為負(fù)值時(shí)停止。此時(shí)社團(tuán)G的適應(yīng)度函數(shù)達(dá)到了最大值，完成了第一個(gè)社團(tuán)的探測(cè)。

步驟7:然后繼續(xù)選取孤立節(jié)點(diǎn)重復(fù)以上過(guò)程，直到網(wǎng)絡(luò)中所有節(jié)點(diǎn)都已經(jīng)被劃分到至少一個(gè)社團(tuán)為止。

在這個(gè)社團(tuán)挖掘的過(guò)程中，有部分節(jié)點(diǎn)會(huì)被劃分到不止一個(gè)社團(tuán)中去，這就是所謂的“騎墻節(jié)點(diǎn)”，體現(xiàn)了社團(tuán)結(jié)構(gòu)的重疊性。

2.2 多分辨率社團(tuán)結(jié)構(gòu)約簡(jiǎn)方法

多分辨率約簡(jiǎn)指在保持復(fù)雜網(wǎng)絡(luò)基本特性的基礎(chǔ)上實(shí)現(xiàn)網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的數(shù)量規(guī)模的約簡(jiǎn)。

網(wǎng)絡(luò)的樹(shù)狀圖可以體現(xiàn)出網(wǎng)絡(luò)的層次性，選取不同的位置對(duì)樹(shù)狀圖進(jìn)行劃分即可以得到不同規(guī)模的社團(tuán)。運(yùn)用分區(qū)密度α刻畫(huà)樹(shù)狀圖，對(duì)網(wǎng)絡(luò)進(jìn)行劃分。較小的α值能把網(wǎng)絡(luò)劃分為一些規(guī)模較大的社團(tuán)，較大α則對(duì)應(yīng)數(shù)量較多的小社團(tuán)。通過(guò)選擇一系列α值對(duì)網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分就能夠得到社團(tuán)結(jié)構(gòu)的層次性。社團(tuán)結(jié)構(gòu)還有一個(gè)重要特征就是其具有重疊性［13］，它指社團(tuán)中存在一些“騎墻節(jié)點(diǎn)”，它們同時(shí)被多個(gè)社團(tuán)包含，屬于這些社團(tuán)的交叉部分。經(jīng)過(guò)采用多個(gè)分區(qū)密度的定位，可以得到整個(gè)網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)，并且從邊的角度對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行分析，保留了社團(tuán)之間的邊聯(lián)系信息。為了適應(yīng)不同分辨率下故障源搜索的需要，通過(guò)社團(tuán)搜索，對(duì)網(wǎng)絡(luò)進(jìn)行約簡(jiǎn)分析。多分辨率約簡(jiǎn)分析的目的是根據(jù)需要獲得適當(dāng)分辨率的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。

在2.2節(jié)對(duì)網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)進(jìn)行挖掘的基礎(chǔ)上，將每個(gè)社團(tuán)進(jìn)一步抽象為一個(gè)節(jié)點(diǎn)，將社團(tuán)之間的連接抽象為節(jié)點(diǎn)間的連接邊，從而得到一個(gè)新的分辨率下的由社團(tuán)節(jié)點(diǎn)組成的約簡(jiǎn)網(wǎng)絡(luò)，這里，每個(gè)社團(tuán)節(jié)點(diǎn)用社團(tuán)中拓?fù)鋭?shì)值最大的節(jié)點(diǎn)作為代表，根據(jù)上述思想，遞歸地對(duì)網(wǎng)絡(luò)進(jìn)行約簡(jiǎn)，形成自底向上多分辨率的上的網(wǎng)絡(luò)視圖，最終得到適應(yīng)需求的約簡(jiǎn)網(wǎng)絡(luò)。

進(jìn)行多分辨率收縮約簡(jiǎn)分析可以按照以下的方法進(jìn)行:

步驟1: 執(zhí)行社團(tuán)發(fā)現(xiàn)算法，獲得網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)信息;

步驟2: 將網(wǎng)絡(luò)中的社團(tuán)收縮成節(jié)點(diǎn)，社團(tuán)之間的聯(lián)系抽象成邊，形成新的網(wǎng)絡(luò)拓?fù)鋱D;

步驟3: 按照社團(tuán)分區(qū)密度判斷網(wǎng)絡(luò)拓?fù)鋱D是否滿足分辨率要求，如滿足，轉(zhuǎn)到步驟4，否則轉(zhuǎn)到步驟1;

步驟4 退出，已找到符合要求的約簡(jiǎn)社團(tuán)網(wǎng)絡(luò)結(jié)構(gòu)圖。

鑒于實(shí)際網(wǎng)絡(luò)存在的重疊性與層次性共存的特點(diǎn)，考慮從邊的角度來(lái)確定分區(qū)密度，并使用層次分區(qū)密度的值作為劃分網(wǎng)絡(luò)的α值。

假定C={C1，C2，…，CN}是對(duì)包含有E條邊的網(wǎng)絡(luò)進(jìn)行社團(tuán)劃分的結(jié)果，網(wǎng)絡(luò)被分為N個(gè)社團(tuán)。第Nth社團(tuán)包含的邊的個(gè)數(shù)為mN，mN=。這些邊所覆蓋的節(jié)點(diǎn)為nN。

層次分區(qū)密度的定義［15］為:

如圖5所示，即為使用分區(qū)密度作為參數(shù)對(duì)層次樹(shù)進(jìn)行劃分的示意，取不同的分區(qū)密度即可得到不同分辨率下的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。該算法的時(shí)間復(fù)雜度主要取決于社團(tuán)的大小和其重疊的程度。最壞情況下，即當(dāng)社團(tuán)規(guī)模和節(jié)點(diǎn)數(shù)n在同一數(shù)量級(jí)時(shí)，時(shí)間復(fù)雜度為O(n2)，通常的實(shí)際系統(tǒng)中，基于重疊的程度，計(jì)算常常進(jìn)行得更快。

圖5 分區(qū)密度對(duì)層次樹(shù)的劃分Fig.5 Arrangement tree division by density

3 故障源定位方法

3.1 故障源回溯遞階推理

故障源的遞階推理方法采用雙向協(xié)同推理，并集成廣度優(yōu)先和相容性原則的方法。該方法即依據(jù)測(cè)試結(jié)果，先在全系統(tǒng)的低分辨率結(jié)構(gòu)網(wǎng)絡(luò)模型中進(jìn)行推理，根據(jù)故障現(xiàn)象確定故障部件可能位于的社團(tuán)節(jié)點(diǎn)，然后進(jìn)入該社團(tuán)節(jié)點(diǎn)的高分辨率模型中進(jìn)行進(jìn)一步推理，后繼續(xù)擴(kuò)展分辨率，遞歸推理，直至獲得滿足故障診斷要求的分辨率的故障源預(yù)判社團(tuán)。

在滿足診斷要求的分辨率下的故障社團(tuán)內(nèi)部進(jìn)行進(jìn)一步的故障源定位。獲取故障源所在的社團(tuán)結(jié)構(gòu)圖，根據(jù)社團(tuán)內(nèi)數(shù)據(jù)域交聯(lián)關(guān)系構(gòu)造有向圖Gi=(Vi，Ei)，Vi是社團(tuán)內(nèi)節(jié)點(diǎn)集合，Ei是社團(tuán)內(nèi)邊的集合;用Ai表示Gi的鄰接矩陣，可求出Ai的可達(dá)矩陣;求的對(duì)角矩陣P*，得到Gi的較大的強(qiáng)連通圖;按照強(qiáng)連通圖將系統(tǒng)有向圖簡(jiǎn)化為有向樹(shù)，根據(jù)有向樹(shù)的傳遞關(guān)系，依次排除故障節(jié)點(diǎn)中的可達(dá)節(jié)點(diǎn)，即可定位故障源節(jié)點(diǎn)。

3.2 故障源社團(tuán)可能性排序

根據(jù)回溯推理有可能得到多個(gè)故障源預(yù)判社團(tuán)，對(duì)于存在先驗(yàn)故障傳播能力評(píng)估指標(biāo)的自律分散系統(tǒng)，可以通過(guò)評(píng)估故障可能性，對(duì)故障源社團(tuán)進(jìn)行可能性排序，作為故障源定位的參考。故障可能性定義為Pw(vc)=W(e)×P(vc)，其中，vc為候選故障源部件;支路e為vc所在的不相容支路;F(vc)為部件vc發(fā)生故障的概率;W(e)∈［0，1］，根據(jù)系統(tǒng)工作原理和實(shí)踐經(jīng)驗(yàn)給出，它代表了該支路傳播故障的能力。

通過(guò)對(duì)故障源候選節(jié)點(diǎn)集合中的各個(gè)故障源進(jìn)行故障可能性Pw的計(jì)算，建立了故障可能性的排序。由于先驗(yàn)概率的失效性，排序只能作為進(jìn)一步進(jìn)行故障源定位的參考。

4 應(yīng)用驗(yàn)證實(shí)例

自律分散測(cè)試系統(tǒng)(ADTS)的體系結(jié)構(gòu)如圖6所示。該結(jié)構(gòu)中，包括新型ATE和新型TUA。ATE采用雙環(huán)形結(jié)構(gòu)，其中，原子節(jié)點(diǎn)為測(cè)試儀器，數(shù)據(jù)域?yàn)闇y(cè)試網(wǎng)絡(luò)。原子節(jié)點(diǎn)以鏈接為媒介與其他節(jié)點(diǎn)相連接，構(gòu)成測(cè)試網(wǎng)絡(luò)。TUA中包括TUA控制器，電源，信號(hào)調(diào)理板卡和人機(jī)界面等，由具有自我重構(gòu)功能的重構(gòu)單元(Configurable Unit，CU)構(gòu)成，重構(gòu)單元之間通過(guò)相互組合與協(xié)作來(lái)實(shí)現(xiàn)對(duì)UUT信號(hào)的采集、處理。

圖6 自律分散測(cè)試系統(tǒng)的體系結(jié)構(gòu)Fig.6 Structure of autonomous decentralized test system

經(jīng)復(fù)雜網(wǎng)絡(luò)模型輸出得到自律分散測(cè)試系統(tǒng)的網(wǎng)絡(luò)拓?fù)淙鐖D7，各節(jié)點(diǎn)單元表示原子節(jié)點(diǎn)，由于系統(tǒng)底層結(jié)構(gòu)復(fù)雜，系統(tǒng)節(jié)點(diǎn)眾多，初級(jí)網(wǎng)絡(luò)結(jié)構(gòu)規(guī)模龐大，篇幅所限，圖7所示的是經(jīng)過(guò)初級(jí)社團(tuán)挖掘后得到的次高分辨率下的社團(tuán)拓?fù)浣Y(jié)構(gòu)，映射到自律分散測(cè)試系統(tǒng)在此層級(jí)的功能節(jié)點(diǎn)如表1所示:

表1 各節(jié)點(diǎn)對(duì)應(yīng)的自律分散測(cè)試系統(tǒng)原子節(jié)點(diǎn)Tab.1 Atom nodes of autonomous decentralized test system

本文通過(guò)在此分辨率結(jié)構(gòu)下進(jìn)行進(jìn)一步挖掘并進(jìn)行結(jié)構(gòu)約簡(jiǎn)，驗(yàn)證本文提出的故障源快速定位方法。按照系統(tǒng)的功能關(guān)系，生成網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，如圖7所示。首先，按照 2.1所述算法，進(jìn)行進(jìn)一步社團(tuán)結(jié)構(gòu)挖掘，并按照2.2所述約簡(jiǎn)算法對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行收縮，按照樹(shù)狀結(jié)構(gòu)記錄各級(jí)收縮的社團(tuán)，生成如圖8所示網(wǎng)絡(luò)層次樹(shù)圖。

圖7 系統(tǒng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖Fig.7 Topology of system

根據(jù)故障現(xiàn)象集，依據(jù)網(wǎng)絡(luò)層次樹(shù)進(jìn)行故障回溯遞階推理，采用3.3中的故障源定位方法，依據(jù)故障特征確定故障源位于低分辨率社團(tuán)中，進(jìn)一步展開(kāi)該社團(tuán)，進(jìn)行逐步推理，直至獲取故障源，逐步展開(kāi)推理的過(guò)程如圖9所示。

圖9中灰色的社團(tuán)及節(jié)點(diǎn)表示不再進(jìn)行搜索的社團(tuán)空間，按照社團(tuán)為基本單位進(jìn)行逐步推理時(shí)搜索空間顯著縮小，搜索時(shí)間縮短。推理結(jié)束后，故障源定位到3、7、13，即系統(tǒng)的一般電平信號(hào)接口、升壓降壓氣路、壓力檢測(cè)控制氣路。下面根據(jù)故障概率對(duì)故障源節(jié)點(diǎn)進(jìn)行故障可能性排序。根據(jù)先驗(yàn)知識(shí)，系統(tǒng)在此分辨率層級(jí)的各測(cè)試點(diǎn)故障概率比值為(0.02，0.06，0.04，0.03，0.09，0.08，0.07，0.10，0.05，0.08，0.07，0.05，0.06，0.04，0.07，0.04，0.02，0.03)。

根據(jù)3.2節(jié)所述的故障源可能性排序方法可得，節(jié)點(diǎn)(社團(tuán))3、7、13的故障可能性分別為:P3=0.04×3=0.12，P7=0.07 ×4=0.28，P13=0.06 ×4=0.24。

另外對(duì)4組故障現(xiàn)象集進(jìn)行故障源搜索，并將推理所獲得的故障源與實(shí)際故障源進(jìn)行對(duì)比驗(yàn)證獲得的結(jié)果如表2所示。

表2 推理及驗(yàn)證結(jié)果Tab.2 Reasoning and validating result

5 結(jié)論

本文將復(fù)雜網(wǎng)絡(luò)理論應(yīng)用于分布式系統(tǒng)結(jié)構(gòu)分析，并將多分辨率建模思想與社團(tuán)結(jié)構(gòu)挖掘方法結(jié)合，提出了多分辨率模型映射的新觀點(diǎn)，以及基于多分辨率社團(tuán)結(jié)構(gòu)挖掘的自律分散系統(tǒng)故障定位方法。將該方法應(yīng)用于自律分散測(cè)試系統(tǒng)的故障定位，實(shí)驗(yàn)結(jié)果表明，該方法能夠定位自律分散測(cè)試系統(tǒng)的故障源，在先驗(yàn)知識(shí)具備的情形下，可以給出故障源可能性排序作為參考。

［1］張佃中，譚小紅，王 智，等.基于等概率粗粒化的復(fù)雜度算法及其應(yīng)用［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20(15):4096-4098，4013.

［2］李鋒剛.基于優(yōu)化案例推理的智能決策技術(shù)研究［D］.合肥:合肥工業(yè)大學(xué)，2007.

［3］汪小帆，李 翔，陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用［M］.北京:清華大學(xué)出版社，2006.

［4］Girvan M，Newman M E J.Community structures in social and biological［J］.Proceedings of the National Academy of Sciences of The United States Of America，2002，99(12):7821-7826.

［5］ Strogatz S H.Exploring complex networks［J］.Nature，2001，410:268-276.

［6］森欣司.自律分散系統(tǒng)入門(mén)——從系統(tǒng)概念到應(yīng)用技術(shù)［M］.北京:科學(xué)出版社，2008.

［7］ Radicchi F，Castellano C，Cecconi F，et al.Defining and identifying communities in networks［J］.Proceedings of the National Academy of Science USA，2004，101(9):2658-2663.

［8］ Newman M E J.The structure and function of complex networks［J］.SIAM Review，2003，45(2):167-256.

［9］ Janson S，Luczak T，Rucinski A.Random graphs［M］.New York:Wildy，2000.

［10］ Capocci A，Servedio V D P，Caldarelli G，et al.Detecting community in large networks［J］.Physica A，2005，352:669-676.

［11］ Barthelemy M.Betweenness centrality in large complex networks［J］.The European Physics Journal B，2004，38:163-168.

［12］ Newman M E J.Detecting community structure in the networks［J］.The European Physics Journal B，2004，38:321-330.

［13］ Palla G，Derenyi I，F(xiàn)arkas I.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature.2005，435:814-818.

［14］ Lancichinetti A，F(xiàn)ortunato S，Esz J A K.Detecting the overlapping and hierarchical community structure in complex networks［J］.New J.Phys，2009，11，033015.

［15］Ahn Y Y，Bagrow J P，Lehmann S.Link communities reveal multi-scale complexity in networks［D］.Bosten:Northeastern University，2010.