梁 因 馬齊爽 徐 萍

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

潛通路分析［1］揭示的是電路中非器件失效而由于潛通路的存在所引起的系統(tǒng)功能異常.近幾年來(lái)，國(guó)內(nèi)外對(duì)于潛通路及潛通路分析的理論研究已經(jīng)基本趨于成熟，現(xiàn)有的潛通路分析方法已經(jīng)能夠解決大量電氣系統(tǒng)網(wǎng)絡(luò)的潛通路分析問(wèn)題.提高潛通路分析的智能化、自動(dòng)化是目前研究的一個(gè)趨勢(shì)［2－3］.

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

1 電路系統(tǒng)自動(dòng)分塊算法

1.1 電路網(wǎng)絡(luò)分塊理論

用電路的鄰接矩陣模型［5］對(duì)電路網(wǎng)絡(luò)進(jìn)行分塊處理，設(shè)電路系統(tǒng)圖G為一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向連通圖.對(duì)大型電氣網(wǎng)絡(luò)分塊等價(jià)于找到其模型的鄰接矩陣的點(diǎn)割集，使電路能夠分成兩個(gè)子網(wǎng)絡(luò)模塊.采用點(diǎn)切割的方法進(jìn)行分塊，可視為將分塊點(diǎn)分成了兩個(gè)相同節(jié)點(diǎn)，中間用導(dǎo)線(xiàn)連接，劃分模塊時(shí)將導(dǎo)線(xiàn)切割，可以保證電路中所有元件都將位于模塊中，便于子網(wǎng)絡(luò)模塊的等效.

例如對(duì)電路網(wǎng)絡(luò)分塊處理如圖1所示.

圖1 電氣網(wǎng)絡(luò)分塊示意圖

由圖1可知，子網(wǎng)絡(luò)模塊中的節(jié)點(diǎn)包括兩部分.

1)各個(gè)子網(wǎng)絡(luò)獨(dú)立占有的內(nèi)部結(jié)點(diǎn)集:

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

分塊后的各子網(wǎng)絡(luò)之間除了分塊點(diǎn)是聯(lián)系兩個(gè)模塊的部分外，其他電路子網(wǎng)絡(luò)模塊獨(dú)自占有的節(jié)點(diǎn)間不存在直接的聯(lián)系.如果在電路系統(tǒng)模型的鄰接矩陣中去掉這些分塊點(diǎn)，再進(jìn)行合理的排序，分塊對(duì)角陣的形式如下:

1.2 電路網(wǎng)絡(luò)分塊算法

電路系統(tǒng)分塊的算法采用類(lèi)似于復(fù)雜網(wǎng)絡(luò)中社區(qū)發(fā)現(xiàn)的基于Laplace矩陣的譜平分法［6］.當(dāng)把社區(qū)結(jié)構(gòu)看成是網(wǎng)絡(luò)的一個(gè)劃分時(shí)，社區(qū)發(fā)現(xiàn)在于尋找網(wǎng)絡(luò)固有的自然劃分，而不是按指定條件進(jìn)行劃分.同樣，在潛通路分塊分析中，對(duì)于電路系統(tǒng)網(wǎng)絡(luò)模型的分塊是希望能夠根據(jù)電路的拓?fù)浣Y(jié)構(gòu)形成自然劃分.

在對(duì)電路系統(tǒng)分塊前要先去掉電源點(diǎn)、地點(diǎn)以及它們與其他元件的連接關(guān)系，這樣電路網(wǎng)絡(luò)中的割點(diǎn)就會(huì)更加容易被辨別出來(lái)，而且并不影響對(duì)電路網(wǎng)絡(luò)拓?fù)涞姆治?

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

根據(jù)次小特征值λn－1對(duì)應(yīng)的特征向量xn－1=［y1，y2，…，yn］中元素的絕對(duì)值大小來(lái)選擇分塊點(diǎn)，步驟如下:

1)對(duì)xn－1中元素按絕對(duì)值大小重新排序得x′n－1，對(duì)鄰接矩陣按相應(yīng)順序重新排序得 C′n，對(duì)應(yīng)的電路網(wǎng)絡(luò)節(jié)點(diǎn)位置向量為U.

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

3)若不出現(xiàn)分塊對(duì)角陣的形式，則增加一個(gè)x′n－1中絕對(duì)值次小的元素對(duì)應(yīng)的結(jié)點(diǎn)做分塊點(diǎn)，再進(jìn)行判斷，直到出現(xiàn)分塊對(duì)角陣把電路網(wǎng)絡(luò)分成兩個(gè)子網(wǎng)絡(luò)模塊為止.

該算法每次將電路網(wǎng)絡(luò)分成兩塊，如果電路規(guī)模過(guò)大，可以分別對(duì)子網(wǎng)絡(luò)進(jìn)一步分塊，直到得到滿(mǎn)意的規(guī)模為止.

2 分塊后的子網(wǎng)絡(luò)模塊等效

電路網(wǎng)絡(luò)分塊的結(jié)果為各個(gè)子網(wǎng)絡(luò)模塊所包含的點(diǎn)的編號(hào)以及其鄰接矩陣.運(yùn)用現(xiàn)有的潛通路分析方法和工具，對(duì)各子網(wǎng)絡(luò)模塊分別進(jìn)行潛通路分析.再將子網(wǎng)絡(luò)模塊等效成一些更簡(jiǎn)單的模型，完成對(duì)整個(gè)電路網(wǎng)絡(luò)的潛通路分析.

2.1 子網(wǎng)絡(luò)模塊等效模型的類(lèi)型

子網(wǎng)絡(luò)模塊等效就是將每個(gè)子網(wǎng)絡(luò)模塊當(dāng)作一個(gè)特殊器件來(lái)處理.根據(jù)對(duì)電路元件等效的方法對(duì)子網(wǎng)絡(luò)進(jìn)行等效.由電路系統(tǒng)網(wǎng)絡(luò)模型的建立方法［2］可知，電路網(wǎng)絡(luò)結(jié)點(diǎn)包括電路節(jié)點(diǎn)和電路元件，電路元件又包括受控類(lèi)元件、可變狀態(tài)元件和固定狀態(tài)元件.由于子網(wǎng)絡(luò)模塊可能包含各類(lèi)基本電氣元件，將其分為3種情況.

用組成器件的結(jié)點(diǎn)和結(jié)點(diǎn)間的連接關(guān)系矩陣表示該特殊器件.在子網(wǎng)絡(luò)模塊的等效過(guò)程中直接用一個(gè)結(jié)點(diǎn)描述其電氣特性，而關(guān)鍵分析子網(wǎng)絡(luò)模塊對(duì)外的連接端點(diǎn)與其連接關(guān)系.如3端網(wǎng)絡(luò)的結(jié)點(diǎn)等效模型為圖2所示.

圖2 3端網(wǎng)絡(luò)結(jié)點(diǎn)等效模型

多端子網(wǎng)絡(luò)模塊等效時(shí)其模型取決于端點(diǎn)間的組合情況，n端網(wǎng)絡(luò)等效模型共有種可能的情況，具體情況由其內(nèi)部的電氣元件的組合狀態(tài)決定.設(shè)3端網(wǎng)絡(luò)的N1和N2為開(kāi)關(guān)，N3為電阻，等效模型有4種情況如圖3所示.

圖3 3端網(wǎng)絡(luò)的等效模型情況

2.2 子網(wǎng)絡(luò)模塊等效模型的判斷方法

選擇合適的子網(wǎng)絡(luò)模塊的等效模型，先要對(duì)子網(wǎng)絡(luò)模塊的內(nèi)部元件狀態(tài)進(jìn)行分析，主要是可控類(lèi)元件和可變狀態(tài)元件.將其狀態(tài)組合加入到子網(wǎng)絡(luò)模塊的鄰接矩陣中，對(duì)新的鄰接矩陣進(jìn)行分析，找到合適的等效模型.子網(wǎng)絡(luò)模塊的等效采用經(jīng)典算法——圖的深度優(yōu)先搜索(DFS，Depth－First Search)［9］.

運(yùn)用深度優(yōu)先搜索，以其中一個(gè)對(duì)外連接的端點(diǎn)為起點(diǎn)，另外一個(gè)對(duì)外連接端點(diǎn)為終點(diǎn)，如果能找到一條兩個(gè)端點(diǎn)間的路徑，則等效時(shí)子網(wǎng)絡(luò)模塊通過(guò)這兩個(gè)端點(diǎn)有對(duì)外的連接關(guān)系;否則，沒(méi)有連接關(guān)系［10］.若是多端網(wǎng)絡(luò)，則多次使用深度優(yōu)先搜索進(jìn)行判斷即可.判斷過(guò)程如圖4所示.

圖4 深度優(yōu)先搜索流程圖

3 潛通路分塊分析方法

對(duì)電路系統(tǒng)網(wǎng)絡(luò)分塊以及對(duì)子網(wǎng)絡(luò)模塊等效之后，關(guān)鍵是運(yùn)用現(xiàn)有的潛通路分析方法和軟件對(duì)簡(jiǎn)化后的電路系統(tǒng)進(jìn)行潛通路分析.如果子網(wǎng)絡(luò)模塊有m個(gè)可控類(lèi)元件和可變狀態(tài)元件，進(jìn)行子網(wǎng)絡(luò)模塊等效時(shí)，需要分析的組合狀態(tài)的個(gè)數(shù)至少為2m.為了簡(jiǎn)化分析，選擇一種先對(duì)假設(shè)等效模型進(jìn)行潛通路分析，再根據(jù)出現(xiàn)潛通路的情況去分析組合狀態(tài)的方法，只需要分析出現(xiàn)潛通路時(shí)的組合狀態(tài)即可.具體分析步驟如下:

1)判斷子網(wǎng)絡(luò)模塊是幾端網(wǎng)絡(luò)，從而判斷其等效的結(jié)點(diǎn)個(gè)數(shù);

2)對(duì)子網(wǎng)絡(luò)模塊的結(jié)點(diǎn)模型進(jìn)行連接關(guān)系的組合，將所有的組合情況簡(jiǎn)化等效并進(jìn)行潛通路分析;

3)根據(jù)潛通路分析的結(jié)果，判斷出現(xiàn)潛通路情況時(shí)各個(gè)子網(wǎng)絡(luò)模塊的等效模型，用圖的深度優(yōu)先搜索算法搜索路徑，分析此時(shí)子網(wǎng)絡(luò)模塊內(nèi)部元件的組合狀態(tài).

4 潛通路分塊分析案例

以圖5為例來(lái)簡(jiǎn)述對(duì)于電路系統(tǒng)潛通路分塊分析的步驟.本文只闡述對(duì)電路系統(tǒng)的分塊過(guò)程以及分塊后子網(wǎng)絡(luò)模塊的等效過(guò)程.圖5是一個(gè)簡(jiǎn)單的兩電源供電電路系統(tǒng).

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

4.1 電路系統(tǒng)分塊

根據(jù)圖論的知識(shí)將其用圖論中的模型圖表示，對(duì)電路網(wǎng)絡(luò)模型進(jìn)行處理，去掉電源和地節(jié)點(diǎn)以及它們與其他元件的連接關(guān)系.如圖6所示去掉虛線(xiàn)框中電源和地的節(jié)點(diǎn)以及連接關(guān)系.

圖6 電路網(wǎng)絡(luò)模型示意圖

該圖形處理后的鄰接矩陣是一個(gè)18×18的對(duì)稱(chēng)矩陣:

對(duì)該鄰接矩陣用基于Laplace矩陣的譜平分法進(jìn)行分塊，自動(dòng)返回的分塊結(jié)果為:Vcut表示分塊點(diǎn)集，該圖具有兩個(gè)分塊點(diǎn)9和18.V1和P1分別代表第1個(gè)子網(wǎng)絡(luò)所包含的節(jié)點(diǎn)及其鄰接矩陣，其編號(hào)對(duì)應(yīng)實(shí)際電路系統(tǒng)圖中的元件;V2和P2分別代表第2個(gè)子網(wǎng)絡(luò)的鄰接矩陣和節(jié)點(diǎn).

4.2 子網(wǎng)絡(luò)模塊等效

子網(wǎng)絡(luò)模塊等效時(shí)先分析其內(nèi)部的電氣元件的類(lèi)型.以P2子網(wǎng)絡(luò)模塊為例進(jìn)行分析，其等效模型為1個(gè)3端網(wǎng)絡(luò)，用1個(gè)點(diǎn)P2表示其內(nèi)部結(jié)構(gòu)，用3個(gè)外結(jié)點(diǎn)表示其與外部的連接關(guān)系，其結(jié)點(diǎn)等效模型如圖2所示，其中U1=N1，U2=N2，U3=N3，P2=S3.

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

將其內(nèi)部開(kāi)關(guān)的組合狀態(tài)依次加入到鄰接矩陣P2中進(jìn)行分析，例如將開(kāi)關(guān)組合U1U3=00加入鄰接矩陣，可得新的鄰接矩陣為

用深度優(yōu)先搜索判斷，可知其返回結(jié)果都為0，即此種開(kāi)關(guān)組合狀態(tài)下，該子網(wǎng)絡(luò)模塊沒(méi)有通過(guò)任何端點(diǎn)連接到電路系統(tǒng)中，所以此時(shí)的等效模型為圖3a所示.依次對(duì)開(kāi)關(guān)的其它組合狀態(tài)進(jìn)行等效模型判斷，其結(jié)果如圖3所示.

相同的方法分析可得子網(wǎng)絡(luò)模塊P1的等效模型.將這些組合狀態(tài)分別運(yùn)用到簡(jiǎn)化的電路系統(tǒng)模型中進(jìn)行潛通路分析即可，對(duì)于潛通路分析的步驟這里不再詳細(xì)闡述.

5 結(jié)論

本文針對(duì)現(xiàn)有潛通路分析算法在進(jìn)行大型電路系統(tǒng)潛通路分析時(shí)面臨的占用過(guò)多的存儲(chǔ)空間以及計(jì)算時(shí)間過(guò)長(zhǎng)等問(wèn)題，改進(jìn)算法對(duì)大拓?fù)潆娐凡捎梅謮K分析的方法.本文采用的潛通路分塊分析方法簡(jiǎn)化了分析模型，提高了分析的速度，減少了分析算法所需的存儲(chǔ)空間以及分析過(guò)程的人工參與，節(jié)省了分析所用的資源，從而促進(jìn)了潛通路分析的自動(dòng)化水平的提高，具有很大的實(shí)用價(jià)值.

References)

［1］ 鄒濤，馬齊爽.基于網(wǎng)絡(luò)流仿真的潛通路分析方法［J］.北京航空航天大學(xué)學(xué)報(bào)，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］ 徐萍，馬齊爽，鄒濤.開(kāi)關(guān)電路潛通路分析的一種方法［J］.北京航空航天大學(xué)學(xué)報(bào)，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］ 徐俊明.圖論及其應(yīng)用［M］.2版.合肥:中國(guó)科學(xué)技術(shù)大學(xué)出版社，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］ 謝福鼎，張磊，嵇敏，等.一種基于譜平分法的社團(tuán)劃分算法［J］.計(jì)算機(jī)科學(xué)，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］ 張娜.復(fù)雜網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)劃分算法研究［D］.大連:大連理工大學(xué)，2009 Zhang Na.Partitioning methods for community structure in complex networks［D］.Dalian:Dalian University of Technology，2009(in Chinese)

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

［9］ 周泰.圖的深度優(yōu)先遍歷算法及運(yùn)用［J］.電腦編程技巧與維護(hù)，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］ 杜恒，龔茜茹.圖的深度優(yōu)先遍歷的C語(yǔ)言實(shí)現(xiàn)［J］.九江職業(yè)技術(shù)學(xué)院學(xué)報(bào)，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)