多分辨率社團結構挖掘在故障定位中的應用

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

(空軍工程大學 工程學院二系自動測試系統實驗室，西安 710038)

軍用系統對于容錯性及強生存性有著很高的要求，并且具有在地域上分散，結構上呈分布式的特殊性，使得軍用的分布式裝備具有眾多的功能節點以及復雜的交聯關系，對其進行快速故障定位已經成為武器裝備測試與診斷領域的一個研究重點。目前對候選故障源進行定位的常用方法有基于故障傳播有向圖和符號有向圖的研究方法及基于定性模型的方法，但是由于分布式系統處于多變環境中，需要在動態變化和難以預測的狀態條件下高效地維護和運行，常規的故障定位方法難以獲得正確的結果。例如使用粗?；椒ǎ?］，可對基于時間的復雜序列進行符號化，但不適用于結構復雜呈現網狀結構的系統的約簡和推理。使用案例庫搜索方法［2］，由于案例庫規模會隨時間擴大，會造成搜索效率降低。

復雜網絡理論是運用網絡思維，將客觀世界中的實體抽象為網絡節點，關聯關系抽象為網絡中的邊，從網絡本身的結構特點出發，進行網絡性能的研究［3］。近年來，運用復雜網絡理論對復雜系統的性能進行研究正成為熱點。復雜網絡的社團結構是指在整個網絡中，節點之間的交聯關系不是均勻的，整個網絡由若干個由節點構成的“社團”構成，社團內部節點之間的關系相對緊密，社團之間的交聯關系相對稀疏［4-5］。通過對復雜網絡的社團結構進行發掘，對理解網絡內部結構，系統運行機理有著重要的意義。

1 多分辨率社團結構模型

運用復雜網絡理論對現實系統建模時，網絡的節點代表復雜系統的部件、設備或模塊，邊代表部件之間的交聯關系，社團結構體現的是復雜系統中的交聯關系、模塊化或層次性結構。

1.1 網絡定義

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

節點集合V={si|si為系統部件}，

邊集合E={ei，j|節點si指向sj的有向邊}。

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

自律分散測試系統由分擔功能的原子節點構成。在這樣的系統中，原子節點由外界的輸入信息或從其他原子節點接收的信息驅動，而且這個原子節點的處理結果會傳給其他原子節點，其他原子節點依次進行類似的處理。這一驅動條件也包含多個輸入的邏輯與(AND)、邏輯或(OR)等情況。因此，通過原子節點間的協調，可以實現系統整體的功能［6］。運用復雜網絡理論對自律分散系統建模，可以表達原子節點間功能聯合、協調關系，并加進驅動條件。

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

對于一個有4個原子節點的自律分散系統來說，其模型如圖1(a)所示，原子節點之間的數據驅動關系，依據輸入、輸出，作為模型節點中的有向邊，圖1(b)為模型的可達矩陣。

圖1 自律分散系統的模型Fig.1 Model of autonomous decentralized system

如果系統內部發生故障，系統重構，原子節點間的拓撲關系發生改變，系統功能變化，系統結構由變為，此時，被驅動的子系統變為子系統(Si，Sk1'，Sk2'，…，Skn')，系統功能發生重構，如圖2所示。原子節點S2失去后，系統模型變為圖3(a)所述的拓撲結構，可達矩陣如圖3(b)所示。

圖2 系統故障時功能的重構Fig.2 Function reconfiguration during system faulted

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

1.2 社團結構

許多現實的復雜網絡中都存在著社團結構。2002年Girvan和Newman［4］首次提出了復雜網絡的社團結構概念，社團就是網絡中的節點集合。社團內節點之間具有比較緊密的鏈接，而社團之間節點的鏈接相對比較松散。目前，盡管社團還沒有一個統一的、量化的定義，但這種定義已經被廣大學者所接受。Radicchi等［7］提出了社團結構的強定義，即“在強的意義下，社團是一個子圖，它內部節點之間的聯系要大于剩余節點之間的聯系”。

1.3 多分辨率映射

由于復雜網絡具有層次性，即不同網絡中節點的組織結構會呈現出不同的層次。較大的社團中可能還會包括一些較小的社團，并可能呈現出多層嵌套的狀態，在不同分辨率下對網絡進行觀察，可以得到不同的網絡視圖，映射到自律分散系統的系統結構層級，可以研究不同層級的系統結構;映射到自律分散系統的開發邏輯范疇，可以得到不同層次的開發邏輯。這樣的情形就是自律分散系統社團結構的多分辨率性。

如圖4所示的多分辨率社團模型與自律分散系統的映射關系，分別顯示了多分辨率社團模型在各層次與系統開發邏輯以及系統結構層級的映射關系。在底層，多分辨率社團模型是典型的由節點和邊構成的網絡結構，對應自律分散系統開發邏輯的可重構單元(原子節點)及系統結構層級的實現元件層級;通過對底層基本網絡進行社團挖掘進行結構約簡，可以得到8個社團，圖中由虛線劃分表示，社團及其之間的交聯關系即構成高分辨率社團交聯結構，并在此層級映射自律分散系統開發邏輯中的系統體系邏輯以及系統結構層級中的模塊結構層級;以社團作為節點，即可得到較低分辨的社團網絡拓撲結構，對社團網絡結構進行進一步的社團挖掘，可以得到3個更高層級的社團，也就是低分辨率社團交聯結構，對應自律分散系統開發邏輯的功能模型以及系統結構層級中的功能層級。圖4即為模型的通用映射關系，在具體研究中會依據實際進行多分辨率建模，例如，在多重模塊嵌套的情形下，有四級分辨率下的社團結構模型。

圖4 社團網絡多分辨率映射關系示意圖Fig.4 Multi-scale mapping relationship of community networks

由于自律分散系統的特殊性，具有資源動態占有、結構變化的特點，并具有多級模塊性、模塊內部呈強耦合，模塊間呈弱耦合。因此，對自律分散系統進行網絡建模，并運用尋找網絡層次性社團的發掘算法，對網絡進行分層收縮約簡，運用系統結構拓撲模型進行系統結構分析及故障傳播研究，對自律分散系統的快速故障定位有著重要意義。

2 社團結構發掘方法

2.1 基于適應度函數局部最優化的社團發掘方法

對網絡社團結構的挖掘研究與圖論和計算機科學中的圖分割理論(Graph Partitioning)、社會學中的層次聚類方法(Hierarchical Clustering)等有密切的關系［8］。社團挖掘的主要研究熱點集中在尋求一個合理而高效的算法來發現復雜網絡中的社區［8-11］。研究者們已經提出了許多有用的方法來挖掘網絡中的社區，如基于圖分解的方法(包括Spectral Bisection Method和Kernighan-Lin算法等)、基于社會學的方法(主要是層次聚類方法，包括單連接方法和完全連接方法等)和一些新的方法(包括去邊方法和集團分析法等)［12-13］。

LFM算法是一種基于適應度函數局部最優化的方法，是基于極值優化的思想進行社團結構劃分的代表算法之一［14］。在LFM算法中，社團的發現通過對定義適應度函數fG進行優化取最大值來實現:

式中fG+i(fG-i)是社團{G+i}({G-i})的適應度函數值，反映了節點i加入(或被移除)社團G后該社團的適應度。當＞0，說明點i加入社團G后能使該社團的適應度增大，因而應當被包含在社團G中;當＜0，則點應從社團G中移除。

社團挖掘的具體算法如下:

輸入:復雜網絡S={V，E}

輸出:社團結構集{G1，…，Gn}

步驟1:選擇一個孤立節點A作為社團G的初始成員=0;

步驟2:依據式(1)計算社團G的所有鄰居節點對G的適應度貢獻;

步驟3:選出適應度函數值最大的鄰居節點，把它加到社團G中，得到新的社團G';

步驟4:根據式(2)重新計算社團G'中所有節點對社團G'的適應度貢獻;

步驟5:選出適應度函數值為負的節點，將其從社團G'中刪除，得到新的社團G″;

步驟6:如果步驟5發生，則返回步驟4，如果所有節點的適應度貢獻都為正，則返回步驟2。上述過程循環執行，直到社團G的的所有鄰居節點對G的貢獻值都為負值時停止。此時社團G的適應度函數達到了最大值，完成了第一個社團的探測。

步驟7:然后繼續選取孤立節點重復以上過程，直到網絡中所有節點都已經被劃分到至少一個社團為止。

在這個社團挖掘的過程中，有部分節點會被劃分到不止一個社團中去，這就是所謂的“騎墻節點”，體現了社團結構的重疊性。

2.2 多分辨率社團結構約簡方法

多分辨率約簡指在保持復雜網絡基本特性的基礎上實現網絡中節點和邊的數量規模的約簡。

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

在2.2節對網絡社團結構進行挖掘的基礎上，將每個社團進一步抽象為一個節點，將社團之間的連接抽象為節點間的連接邊，從而得到一個新的分辨率下的由社團節點組成的約簡網絡，這里，每個社團節點用社團中拓撲勢值最大的節點作為代表，根據上述思想，遞歸地對網絡進行約簡，形成自底向上多分辨率的上的網絡視圖，最終得到適應需求的約簡網絡。

進行多分辨率收縮約簡分析可以按照以下的方法進行:

步驟1: 執行社團發現算法，獲得網絡社團結構信息;

步驟2: 將網絡中的社團收縮成節點，社團之間的聯系抽象成邊，形成新的網絡拓撲圖;

步驟3: 按照社團分區密度判斷網絡拓撲圖是否滿足分辨率要求，如滿足，轉到步驟4，否則轉到步驟1;

步驟4 退出，已找到符合要求的約簡社團網絡結構圖。

鑒于實際網絡存在的重疊性與層次性共存的特點，考慮從邊的角度來確定分區密度，并使用層次分區密度的值作為劃分網絡的α值。

假定C={C1，C2，…，CN}是對包含有E條邊的網絡進行社團劃分的結果，網絡被分為N個社團。第Nth社團包含的邊的個數為mN，mN=。這些邊所覆蓋的節點為nN。

層次分區密度的定義［15］為:

如圖5所示，即為使用分區密度作為參數對層次樹進行劃分的示意，取不同的分區密度即可得到不同分辨率下的網絡社團結構。該算法的時間復雜度主要取決于社團的大小和其重疊的程度。最壞情況下，即當社團規模和節點數n在同一數量級時，時間復雜度為O(n2)，通常的實際系統中，基于重疊的程度，計算常常進行得更快。

圖5 分區密度對層次樹的劃分Fig.5 Arrangement tree division by density

3 故障源定位方法

3.1 故障源回溯遞階推理

故障源的遞階推理方法采用雙向協同推理，并集成廣度優先和相容性原則的方法。該方法即依據測試結果，先在全系統的低分辨率結構網絡模型中進行推理，根據故障現象確定故障部件可能位于的社團節點，然后進入該社團節點的高分辨率模型中進行進一步推理，后繼續擴展分辨率，遞歸推理，直至獲得滿足故障診斷要求的分辨率的故障源預判社團。

在滿足診斷要求的分辨率下的故障社團內部進行進一步的故障源定位。獲取故障源所在的社團結構圖，根據社團內數據域交聯關系構造有向圖Gi=(Vi，Ei)，Vi是社團內節點集合，Ei是社團內邊的集合;用Ai表示Gi的鄰接矩陣，可求出Ai的可達矩陣;求的對角矩陣P*，得到Gi的較大的強連通圖;按照強連通圖將系統有向圖簡化為有向樹，根據有向樹的傳遞關系，依次排除故障節點中的可達節點，即可定位故障源節點。

3.2 故障源社團可能性排序

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

通過對故障源候選節點集合中的各個故障源進行故障可能性Pw的計算，建立了故障可能性的排序。由于先驗概率的失效性，排序只能作為進一步進行故障源定位的參考。

4 應用驗證實例

自律分散測試系統(ADTS)的體系結構如圖6所示。該結構中，包括新型ATE和新型TUA。ATE采用雙環形結構，其中，原子節點為測試儀器，數據域為測試網絡。原子節點以鏈接為媒介與其他節點相連接，構成測試網絡。TUA中包括TUA控制器，電源，信號調理板卡和人機界面等，由具有自我重構功能的重構單元(Configurable Unit，CU)構成，重構單元之間通過相互組合與協作來實現對UUT信號的采集、處理。

圖6 自律分散測試系統的體系結構Fig.6 Structure of autonomous decentralized test system

經復雜網絡模型輸出得到自律分散測試系統的網絡拓撲如圖7，各節點單元表示原子節點，由于系統底層結構復雜，系統節點眾多，初級網絡結構規模龐大，篇幅所限，圖7所示的是經過初級社團挖掘后得到的次高分辨率下的社團拓撲結構，映射到自律分散測試系統在此層級的功能節點如表1所示:

表1 各節點對應的自律分散測試系統原子節點Tab.1 Atom nodes of autonomous decentralized test system

本文通過在此分辨率結構下進行進一步挖掘并進行結構約簡，驗證本文提出的故障源快速定位方法。按照系統的功能關系，生成網絡拓撲結構圖，如圖7所示。首先，按照 2.1所述算法，進行進一步社團結構挖掘，并按照2.2所述約簡算法對網絡結構進行收縮，按照樹狀結構記錄各級收縮的社團，生成如圖8所示網絡層次樹圖。

圖7 系統網絡拓撲結構圖Fig.7 Topology of system

根據故障現象集，依據網絡層次樹進行故障回溯遞階推理，采用3.3中的故障源定位方法，依據故障特征確定故障源位于低分辨率社團中，進一步展開該社團，進行逐步推理，直至獲取故障源，逐步展開推理的過程如圖9所示。

圖9中灰色的社團及節點表示不再進行搜索的社團空間，按照社團為基本單位進行逐步推理時搜索空間顯著縮小，搜索時間縮短。推理結束后，故障源定位到3、7、13，即系統的一般電平信號接口、升壓降壓氣路、壓力檢測控制氣路。下面根據故障概率對故障源節點進行故障可能性排序。根據先驗知識，系統在此分辨率層級的各測試點故障概率比值為(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)。

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

另外對4組故障現象集進行故障源搜索，并將推理所獲得的故障源與實際故障源進行對比驗證獲得的結果如表2所示。

表2 推理及驗證結果Tab.2 Reasoning and validating result

5 結論

本文將復雜網絡理論應用于分布式系統結構分析，并將多分辨率建模思想與社團結構挖掘方法結合，提出了多分辨率模型映射的新觀點，以及基于多分辨率社團結構挖掘的自律分散系統故障定位方法。將該方法應用于自律分散測試系統的故障定位，實驗結果表明，該方法能夠定位自律分散測試系統的故障源，在先驗知識具備的情形下，可以給出故障源可能性排序作為參考。

［1］張佃中，譚小紅，王 智，等.基于等概率粗?；膹碗s度算法及其應用［J］.系統仿真學報，2008，20(15):4096-4098，4013.

［2］李鋒剛.基于優化案例推理的智能決策技術研究［D］.合肥:合肥工業大學，2007.

［3］汪小帆，李 翔，陳關榮.復雜網絡理論及其應用［M］.北京:清華大學出版社，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］森欣司.自律分散系統入門——從系統概念到應用技術［M］.北京:科學出版社，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，Farkas I.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature.2005，435:814-818.

［14］ Lancichinetti A，Fortunato 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.