基于圖論的潛通路分塊分析方法

梁 因 馬齊爽 徐 萍

(北京航空航天大學 自動化科學與電氣工程學院，北京100191)

潛通路分析［1］揭示的是電路中非器件失效而由于潛通路的存在所引起的系統功能異常.近幾年來，國內外對于潛通路及潛通路分析的理論研究已經基本趨于成熟，現有的潛通路分析方法已經能夠解決大量電氣系統網絡的潛通路分析問題.提高潛通路分析的智能化、自動化是目前研究的一個趨勢［2－3］.

潛通路問題的產生是系統復雜性和設計人員有限的把握能力之間矛盾斗爭的結果［4］，進行潛通路分析時同樣面臨著電路系統過于復雜，而難以直觀把握這個問題.尤其是要將其與計算機技術相結合實現智能化、自動化的潛通路分析時，電路信息存儲在鄰接矩陣中，隨著電路系統規模的擴大，整體進行分析不僅會使分析時間增加，而且分析過程需要占據很大的存儲空間.因此本文提出了對大型復雜電路系統分塊分析的方法，將大型復雜電氣系統網絡進行分塊處理，對每一個子網絡模塊分別進行分析，再將每一個子網絡模塊等效成簡單的模型對整體電路進行分析，從而簡化分析過程的模型，提高潛通路分析自動化水平.

1 電路系統自動分塊算法

1.1 電路網絡分塊理論

用電路的鄰接矩陣模型［5］對電路網絡進行分塊處理，設電路系統圖G為一個具有n個節點的無向連通圖.對大型電氣網絡分塊等價于找到其模型的鄰接矩陣的點割集，使電路能夠分成兩個子網絡模塊.采用點切割的方法進行分塊，可視為將分塊點分成了兩個相同節點，中間用導線連接，劃分模塊時將導線切割，可以保證電路中所有元件都將位于模塊中，便于子網絡模塊的等效.

例如對電路網絡分塊處理如圖1所示.

圖1 電氣網絡分塊示意圖

由圖1可知，子網絡模塊中的節點包括兩部分.

1)各個子網絡獨立占有的內部結點集:

2)分塊點集:Q=［7］，該圖為單分塊點.

分塊后的各子網絡之間除了分塊點是聯系兩個模塊的部分外，其他電路子網絡模塊獨自占有的節點間不存在直接的聯系.如果在電路系統模型的鄰接矩陣中去掉這些分塊點，再進行合理的排序，分塊對角陣的形式如下:

1.2 電路網絡分塊算法

電路系統分塊的算法采用類似于復雜網絡中社區發現的基于Laplace矩陣的譜平分法［6］.當把社區結構看成是網絡的一個劃分時，社區發現在于尋找網絡固有的自然劃分，而不是按指定條件進行劃分.同樣，在潛通路分塊分析中，對于電路系統網絡模型的分塊是希望能夠根據電路的拓撲結構形成自然劃分.

在對電路系統分塊前要先去掉電源點、地點以及它們與其他元件的連接關系，這樣電路網絡中的割點就會更加容易被辨別出來，而且并不影響對電路網絡拓撲的分析.

圖G為 n階無向簡單連通圖［7］，其 Laplace矩陣的 n 個特征值為 λ1，λ2，…，λn，x1，x2，…，xn分別為對應特征向量，若λ1≥λ2≥…≥λn，則有 λi＞ 0，i=1，2，…，n－1，λn=0，且xn=［1，1，1，…，1］為特征值 λn=0對應的特征向量.對稱矩陣的任意兩個特征值所對應的特征向量都相互正交，所以 xi⊥xn，i=1，2，…，n －1.則 ?i≤n－1，都應該?j∈(1，n－1)使 xi=［y1，y2…，yj，yj+1，…，yn］，其中，?k≤j，yk＜ 0 ，且 ?k ＞ j，yk＞0.存在特征值λi→0，使其對應特征向量xi中的元素yj→0，且其對應的節點將電路網絡圖分成兩部分，該特征向量中正數元素即yk＞0對應的節點屬于一個子圖，另外的負數元素即yk＜0對應的節點屬于另一個子圖［8］.

根據次小特征值λn－1對應的特征向量xn－1=［y1，y2，…，yn］中元素的絕對值大小來選擇分塊點，步驟如下:

1)對xn－1中元素按絕對值大小重新排序得x′n－1，對鄰接矩陣按相應順序重新排序得 C′n，對應的電路網絡節點位置向量為U.

2)若|yk|=minx′n－1=min［|y1|，|y2|，…，|yn|］，則先選yk對應的節點uk為分塊點，判斷在鄰接矩陣C′n中去掉uk對應的行和列是否出現分塊對角陣.若出現，則該點就是電路系統的單分塊點，給出分塊情況即可.

3)若不出現分塊對角陣的形式，則增加一個x′n－1中絕對值次小的元素對應的結點做分塊點，再進行判斷，直到出現分塊對角陣把電路網絡分成兩個子網絡模塊為止.

該算法每次將電路網絡分成兩塊，如果電路規模過大，可以分別對子網絡進一步分塊，直到得到滿意的規模為止.

2 分塊后的子網絡模塊等效

電路網絡分塊的結果為各個子網絡模塊所包含的點的編號以及其鄰接矩陣.運用現有的潛通路分析方法和工具，對各子網絡模塊分別進行潛通路分析.再將子網絡模塊等效成一些更簡單的模型，完成對整個電路網絡的潛通路分析.

2.1 子網絡模塊等效模型的類型

子網絡模塊等效就是將每個子網絡模塊當作一個特殊器件來處理.根據對電路元件等效的方法對子網絡進行等效.由電路系統網絡模型的建立方法［2］可知，電路網絡結點包括電路節點和電路元件，電路元件又包括受控類元件、可變狀態元件和固定狀態元件.由于子網絡模塊可能包含各類基本電氣元件，將其分為3種情況.

用組成器件的結點和結點間的連接關系矩陣表示該特殊器件.在子網絡模塊的等效過程中直接用一個結點描述其電氣特性，而關鍵分析子網絡模塊對外的連接端點與其連接關系.如3端網絡的結點等效模型為圖2所示.

圖2 3端網絡結點等效模型

多端子網絡模塊等效時其模型取決于端點間的組合情況，n端網絡等效模型共有種可能的情況，具體情況由其內部的電氣元件的組合狀態決定.設3端網絡的N1和N2為開關，N3為電阻，等效模型有4種情況如圖3所示.

圖3 3端網絡的等效模型情況

2.2 子網絡模塊等效模型的判斷方法

選擇合適的子網絡模塊的等效模型，先要對子網絡模塊的內部元件狀態進行分析，主要是可控類元件和可變狀態元件.將其狀態組合加入到子網絡模塊的鄰接矩陣中，對新的鄰接矩陣進行分析，找到合適的等效模型.子網絡模塊的等效采用經典算法——圖的深度優先搜索(DFS，Depth－First Search)［9］.

運用深度優先搜索，以其中一個對外連接的端點為起點，另外一個對外連接端點為終點，如果能找到一條兩個端點間的路徑，則等效時子網絡模塊通過這兩個端點有對外的連接關系;否則，沒有連接關系［10］.若是多端網絡，則多次使用深度優先搜索進行判斷即可.判斷過程如圖4所示.

圖4 深度優先搜索流程圖

3 潛通路分塊分析方法

對電路系統網絡分塊以及對子網絡模塊等效之后，關鍵是運用現有的潛通路分析方法和軟件對簡化后的電路系統進行潛通路分析.如果子網絡模塊有m個可控類元件和可變狀態元件，進行子網絡模塊等效時，需要分析的組合狀態的個數至少為2m.為了簡化分析，選擇一種先對假設等效模型進行潛通路分析，再根據出現潛通路的情況去分析組合狀態的方法，只需要分析出現潛通路時的組合狀態即可.具體分析步驟如下:

1)判斷子網絡模塊是幾端網絡，從而判斷其等效的結點個數;

2)對子網絡模塊的結點模型進行連接關系的組合，將所有的組合情況簡化等效并進行潛通路分析;

3)根據潛通路分析的結果，判斷出現潛通路情況時各個子網絡模塊的等效模型，用圖的深度優先搜索算法搜索路徑，分析此時子網絡模塊內部元件的組合狀態.

4 潛通路分塊分析案例

以圖5為例來簡述對于電路系統潛通路分塊分析的步驟.本文只闡述對電路系統的分塊過程以及分塊后子網絡模塊的等效過程.圖5是一個簡單的兩電源供電電路系統.

圖5 潛通路分塊分析示例電路圖

4.1 電路系統分塊

根據圖論的知識將其用圖論中的模型圖表示，對電路網絡模型進行處理，去掉電源和地節點以及它們與其他元件的連接關系.如圖6所示去掉虛線框中電源和地的節點以及連接關系.

圖6 電路網絡模型示意圖

該圖形處理后的鄰接矩陣是一個18×18的對稱矩陣:

對該鄰接矩陣用基于Laplace矩陣的譜平分法進行分塊，自動返回的分塊結果為:Vcut表示分塊點集，該圖具有兩個分塊點9和18.V1和P1分別代表第1個子網絡所包含的節點及其鄰接矩陣，其編號對應實際電路系統圖中的元件;V2和P2分別代表第2個子網絡的鄰接矩陣和節點.

4.2 子網絡模塊等效

子網絡模塊等效時先分析其內部的電氣元件的類型.以P2子網絡模塊為例進行分析，其等效模型為1個3端網絡，用1個點P2表示其內部結構，用3個外結點表示其與外部的連接關系，其結點等效模型如圖2所示，其中U1=N1，U2=N2，U3=N3，P2=S3.

其可能的等效模型有5種，針對其內部電氣元件類型進行具體分析，結點1和結點9為開關元件，屬于受控類元件，其余元件都屬于固定狀態元件.因此，P2等效為一個受控類的特殊器件.把該模塊中開關元件的組合狀態加入到鄰接矩陣中.它包含了2個開關，其組合狀態有4種，U1U3=00，U1U3=01，U1U3=10，U1U3=11.

將其內部開關的組合狀態依次加入到鄰接矩陣P2中進行分析，例如將開關組合U1U3=00加入鄰接矩陣，可得新的鄰接矩陣為

用深度優先搜索判斷，可知其返回結果都為0，即此種開關組合狀態下，該子網絡模塊沒有通過任何端點連接到電路系統中，所以此時的等效模型為圖3a所示.依次對開關的其它組合狀態進行等效模型判斷，其結果如圖3所示.

相同的方法分析可得子網絡模塊P1的等效模型.將這些組合狀態分別運用到簡化的電路系統模型中進行潛通路分析即可，對于潛通路分析的步驟這里不再詳細闡述.

5 結論

本文針對現有潛通路分析算法在進行大型電路系統潛通路分析時面臨的占用過多的存儲空間以及計算時間過長等問題，改進算法對大拓撲電路采用分塊分析的方法.本文采用的潛通路分塊分析方法簡化了分析模型，提高了分析的速度，減少了分析算法所需的存儲空間以及分析過程的人工參與，節省了分析所用的資源，從而促進了潛通路分析的自動化水平的提高，具有很大的實用價值.

References)

［1］ 鄒濤，馬齊爽.基于網絡流仿真的潛通路分析方法［J］.北京航空航天大學學報，2012，38(4):546－550 Zou Tao，Ma Qishuang.Method based on network flow simulation for sneak circuit analysis［J］.Journal of Beijing University of Aeronautics and Astronautics，2012，38(4):546 － 550(in Chinese)

［2］ Zou Tao，Ma Qishuang.Research of sneak circuit analysis using network flow simulation［C］//Proceedings of IEEE 2012 Prognostics and System Health Management Conference，PHM－2012.Washington:IEEE Computer Society，2012:1 －5

［3］ 徐萍，馬齊爽，鄒濤.開關電路潛通路分析的一種方法［J］.北京航空航天大學學報，2011，37(3):360－363 Xu Ping，Ma Qishuang，Zou Tao.One sneak circuit analysis method for the switch circuit［J］.Journal of Beijing University of Aeronautics and Astronautics，2011，37(3):360 － 363(in Chinese)

［4］ Zou Tao，Ma Qishuang.The research of sneak circuit analysis based on artificial neural network［C］//Proceedings of the 7th International Conference on“Mathematical Methods in Reliability”:Theory，Methods，Applications.Beijing:Beijing Institute of Technology Press，2011:634 －638

［5］ 徐俊明.圖論及其應用［M］.2版.合肥:中國科學技術大學出版社，2004:24－27 Xu Junming.Graph theory and its application［M］.2nd ed.Hefei:University of Science and Technology of China Press，2004:24－27(in Chinese)

［6］ 謝福鼎，張磊，嵇敏，等.一種基于譜平分法的社團劃分算法［J］.計算機科學，2009，36(11):186 －188 Xie Fuding，Zhang Lei，Ji Min，et al.Community partitioning algorithm based on spectral bisection method［J］.Computer Science，2009，36(11):186 －188(in Chinese)

［7］ 張娜.復雜網絡社區結構劃分算法研究［D］.大連:大連理工大學，2009 Zhang Na.Partitioning methods for community structure in complex networks［D］.Dalian:Dalian University of Technology，2009(in Chinese)

［8］ 梁浩.圖的拉普拉斯矩陣和臨界群［D］.合肥:中國科學技術大學，2009 Liang Hao.Laplacian matrix and critical group of a graph［D］.Hefei:University of Science and Technology of China，2009(in Chinese)

［9］ 周泰.圖的深度優先遍歷算法及運用［J］.電腦編程技巧與維護，2011，17(16):93 －94 Zhou Tai.The DFS for graph and its application［J］.Computer Programming Skills＆ Maintenance，2011，17(16):93 － 94(in Chinese)

［10］ 杜恒，龔茜茹.圖的深度優先遍歷的C語言實現［J］.九江職業技術學院學報，2004，4(2):26－28 Du Heng，Gong Qianru.The C language of depth－first ergodicity of graph［J］.Journal of Jiujiang Vocational ＆ Technical College，2004，4(2):26 －28(in Chinese)