基于保護(hù)矩陣和網(wǎng)絡(luò)化簡的最小斷點集計算新方法

， ，

(國網(wǎng)景德鎮(zhèn)供電公司,江西 景德鎮(zhèn) 333000)

0 前 言

求取最小斷點集是復(fù)雜環(huán)網(wǎng)方向保護(hù)整定計算的核心問題。已有計算方法[1，2]一次計算只能隨機(jī)得到最小斷點集(minimum break point set,MBPS)的一個解, 此解具有多樣性問題。斷點整定原則具有特殊性，不與相鄰保護(hù)配合整定，存在誤動的可能，若斷點保護(hù)在系統(tǒng)中處于較重要位置，則系統(tǒng)故障時，其誤動會對系統(tǒng)安全穩(wěn)定運(yùn)行產(chǎn)生較大影響。故在確保斷點集基數(shù)最小的前提下，盡量選取重要度低的保護(hù)作為斷點，以減小故障時斷點對系統(tǒng)的影響?；诰W(wǎng)絡(luò)化簡和保護(hù)配合關(guān)系的MBPS求取方法[1]，平行線路判據(jù)是其算法核心之一，由于在網(wǎng)絡(luò)化簡過程中僅依賴動態(tài)的保護(hù)配合關(guān)系，沒有能夠有效利用網(wǎng)絡(luò)節(jié)點支路拓?fù)渎?lián)接信息，對平行線路判別存在缺陷，在實際應(yīng)用中對某些大型復(fù)雜網(wǎng)絡(luò)無法求出MBPS。文獻(xiàn)[2]提出從多組同基MBPS中選取最優(yōu)解的解決方法，但是所提指標(biāo)不能全面衡量保護(hù)重要度，存在局限性，且需利用文獻(xiàn)[1]的方法求出多組MBPS之后再基于選優(yōu)指標(biāo)從中選取一組，算法較為復(fù)雜，計算量較大，平行線路判據(jù)問題也未解決。故有必要對文獻(xiàn)[1]、文獻(xiàn)[2]中的算法進(jìn)行改進(jìn)和完善。

以節(jié)點重要度和線路介數(shù)評估保護(hù)重要度，形成保護(hù)三類矩陣，以保護(hù)歸屬矩陣判斷平行線路，以保護(hù)關(guān)聯(lián)矩陣計算保護(hù)入度和出度，以保護(hù)重要度矩陣作為選取斷點的依據(jù)之一，以化簡步驟對其進(jìn)行動態(tài)調(diào)整，并按斷點選取原則選取斷點，通過算例可獲取最優(yōu)MBPS。

1 保護(hù)矩陣

1.1 保護(hù)重要度矩陣

形成該矩陣之前需評估各保護(hù)重要度，下面綜合節(jié)點重要度和線路介數(shù)進(jìn)行衡量。

1.1.1 節(jié)點重要度

節(jié)點k的重要度定義為[2]

(1)

式中,η(G)為網(wǎng)絡(luò)G的凝聚度；η(G(k))為節(jié)點k收縮后所得網(wǎng)絡(luò)G(k)的凝聚度。

為了將節(jié)點重要度和下節(jié)的線路介數(shù)綜合應(yīng)用于評估保護(hù)在系統(tǒng)中的重要度，需對其進(jìn)行歸一化處理，使之具有可參照性。將節(jié)點k的重要度與所有節(jié)點的重要度之和的比值定義為節(jié)點k的歸一化重要度為

(2)

式中,I(k)與I(i)分別為節(jié)點k、節(jié)點i歸一化前的重要度。

1.1.2 線路介數(shù)

最短電氣路徑和最短電氣距離的概念見文獻(xiàn)[3]，使用有權(quán)電網(wǎng)模型中的邊權(quán)連接矩陣，利用Dijkstra最短路徑算法可以找出網(wǎng)絡(luò)中任意兩節(jié)點之間的最短電氣路徑[4]。

介數(shù)[5]反映了邊在整個網(wǎng)絡(luò)中的作用和影響力，其值為網(wǎng)絡(luò)中經(jīng)過該邊的最短路徑個數(shù)。將線路s的介數(shù)β(s)定義為電網(wǎng)中經(jīng)過該線路的最短電氣路徑個數(shù)為

(3)

式中,Nij(s)為任意節(jié)點i與節(jié)點j之間最短電氣路徑經(jīng)過線路s的次數(shù)。

將線路s的介數(shù)與所有線路的介數(shù)之和的比值定義為線路s的歸一化介數(shù)為

(4)

式中,β(s)、β(r)分別為線路s、線路r歸一化前的介數(shù)。

1.1.3 保護(hù)重要度

為評估保護(hù)在系統(tǒng)中的重要度，以節(jié)點重要度和線路介數(shù)對其進(jìn)行綜合衡量，定義保護(hù)t的重要度為

(5)

與保護(hù)關(guān)聯(lián)的節(jié)點歸一化重要度以及所保護(hù)的線路歸一化介數(shù)越大，則該保護(hù)重要度越大。應(yīng)優(yōu)先選擇重要度低的保護(hù)作為斷點，這樣能降低斷點保護(hù)對系統(tǒng)穩(wěn)定運(yùn)行的影響。

由式(3)、(4)、(5)算出全網(wǎng)各保護(hù)的重要度，組成保護(hù)重要度矩陣I。

I=[t1t2…tv…tn]T

(6)

式中,t為保護(hù)重要度;v為編號；n為保護(hù)總數(shù)。

1.2 保護(hù)歸屬矩陣

保護(hù)歸屬矩陣用于描述保護(hù)關(guān)聯(lián)節(jié)點和支路，且其元素隨網(wǎng)絡(luò)化簡而動態(tài)調(diào)整。該矩陣行號為節(jié)點編號，列號為線路編號，若保護(hù)r在節(jié)點n和線路l交匯處，則第n行第l列為r，若n與l間無直接拓?fù)溥B接，則第n行第l列為0。圖1的保護(hù)歸屬矩陣為

1.3 保護(hù)關(guān)聯(lián)矩陣

保護(hù)關(guān)聯(lián)矩陣用于描述保護(hù)間的相互配合關(guān)系,且其元素也隨網(wǎng)絡(luò)化簡而動態(tài)調(diào)整。該矩陣元素定義如下。

(7)

圖1 簡單電力系統(tǒng)

根據(jù)定義，圖1的保護(hù)關(guān)聯(lián)矩陣如下。

保護(hù)i的入度(In-degree)等于依賴于保護(hù)i的后備保護(hù)個數(shù)，其出度(Out-degree)等于保護(hù)i依賴的主保護(hù)個數(shù)。該矩陣第i行所有元素之和即為其出度，簡稱Od，第i列所有元素之和即為其入度，簡稱Id。從上面的保護(hù)關(guān)聯(lián)矩陣可知：保護(hù)5的Od為2，Id為2。

2 網(wǎng)絡(luò)化簡

2.1 化簡原則

對應(yīng)于有向圖的網(wǎng)絡(luò)化簡原則[1,6]并基于保護(hù)三大矩陣，對網(wǎng)絡(luò)進(jìn)行化簡，其化簡原則和順序如下。

①對于Id或Od為0或被選為斷點的保護(hù)，把保護(hù)三大矩陣中與其關(guān)聯(lián)的元素置0。終端線路首端保護(hù)出度為0，將其選為斷點。②對于Id為1的保護(hù)t，若保護(hù)關(guān)聯(lián)矩陣的第t列的非0元素在第j行且t≠j，則把保護(hù)關(guān)聯(lián)矩陣第t行元素賦予第j行，并將第t行全賦0，保護(hù)重要度矩陣第t個元素置0，保護(hù)歸屬矩陣中為t的元素替換為j。③對于出度為1的保護(hù)t，保護(hù)關(guān)聯(lián)矩陣的第t行的非零元素在第j列且t≠j。把保護(hù)關(guān)聯(lián)矩陣第t列元素賦予第j列，并將第t列全賦0，保護(hù)重要度矩陣第t個元素置0，保護(hù)歸屬矩陣中為t的元素替換為j。④對于保護(hù)t，若保護(hù)關(guān)聯(lián)矩陣第t行第t列為1，將其選為斷點，并把保護(hù)三大矩陣中與保護(hù)t關(guān)聯(lián)元素置0。

2.2 平行線路優(yōu)化[1,7]

定義1，電網(wǎng)拓?fù)鋱D中直接連接兩個母線節(jié)點的2條及以上的線路稱為平行線路。

定義2，對于平行線路兩端的保護(hù)，任意一端的所有保護(hù)構(gòu)成的集合稱為一組平行線路保護(hù)對。

定義3，在同一條母線上，兩組及以上平行線路保護(hù)對構(gòu)成強(qiáng)關(guān)聯(lián)平行線路保護(hù)組。

定義4，對于兩組平行線路保護(hù)對，其所在兩母線間僅由一條線路相連，稱其為弱關(guān)聯(lián)平行線路保護(hù)組。

為解決文獻(xiàn)[1]平行線路判據(jù)問題，提出以歸屬矩陣判斷網(wǎng)絡(luò)平行線路、平行線路保護(hù)對、強(qiáng)關(guān)聯(lián)平行線路保護(hù)組、弱關(guān)聯(lián)平行線路保護(hù)組。

從歸屬矩陣中歸納平行線路判據(jù):兩列或多列任意同行元素或同為0，或同不為0(至少一行)，則對應(yīng)的線路為平行線路。但是仍有問題，如圖2所示。圖2(a)、(b)的保護(hù)歸屬矩陣分別如下所述。

圖2 比較圖

圖2(a)線路A和B平行，而圖2(b)線路A和B不平行。若圖2(a)、(b)中的保護(hù)2，4均被選為斷點，按化簡原則，兩個歸屬矩陣為

以上述判據(jù)判斷圖2(a)、(b)中的線路均為平行線路，但圖2(b)線路實際不平行。故有必要糾正該判據(jù)，加一個化簡原則：平行線路上的保護(hù)被選為斷點或者被刪除則歸屬矩陣對應(yīng)位置的元素為-1。故平行線路的判據(jù)為在歸屬矩陣中，兩(多)列有兩行同不為0 且同不為-1，或者一行同不為0且同不為-1而另一行同為-1，則這些列對應(yīng)的線路為平行線路。

按此原則化簡，則圖2(a)、(b)的歸屬矩陣為

以糾正后的判據(jù)判斷:圖2(a)線路平行，而圖2(b)線路不平行。

其他概念判據(jù)如下。

平行線路保護(hù)對判據(jù):由上述判據(jù)求出平行線路，其中同行非0且非-1元素對應(yīng)的保護(hù)構(gòu)成一組平行線路保護(hù)組。

強(qiáng)/弱關(guān)聯(lián)平行線路保護(hù)組判據(jù):以平行線路保護(hù)對所在行號為依據(jù)，若有兩組或多組平行線路保護(hù)對在保護(hù)歸屬矩陣中非0且非-1元素對應(yīng)行號相同，則其構(gòu)成一組強(qiáng)關(guān)聯(lián)平行線路保護(hù)組; 若有兩組平行線路保護(hù)對在保護(hù)歸屬矩陣中非0且非-1元素所在行號不同，且兩行中同列非0且非-1元素僅有一組相同，則其構(gòu)成一組弱關(guān)聯(lián)平行線路保護(hù)對。

3 斷點選取原則

①原則1:把終端線路首端保護(hù)選為斷點。②原則2:把強(qiáng)關(guān)聯(lián)平行線路保護(hù)組中的所有保護(hù)選為斷點并更新平行線路保護(hù)對。③原則3:把Id最大的平行線路保護(hù)對選為斷點，若存在多組，則把保護(hù)重要度之和最小的一組選為斷點并更新平行線路保護(hù)對。④原則4:把弱關(guān)聯(lián)平行線路保護(hù)組中的一個平行線路保護(hù)對選為斷點(按原則3選取)，若存在多組，則考慮所關(guān)聯(lián)母線所包含的保護(hù)個數(shù)最小的一組，若此時有多組該類平行線路保護(hù)組，則考慮保護(hù)重要度之和最小的一組，再按上述方法選擇斷點，并更新平行線路保護(hù)對。⑤原則5:選擇Id最大的保護(hù)為斷點，若最大Id的保護(hù)有多個，則選取重要度最大的保護(hù)為斷點。

4 算法步驟

這里算法步驟如下:①根據(jù)式(2)、(4)、(5)計算全網(wǎng)各保護(hù)的重要度。②形成保護(hù)歸屬矩陣、保護(hù)關(guān)聯(lián)矩陣、保護(hù)重要度矩陣并初始化BPS為空集。③若存在Od=0的保護(hù)，則運(yùn)用原則1將其選為斷點。④簡化網(wǎng)絡(luò)并更新保護(hù)三大矩陣。⑤若保護(hù)歸屬矩陣為空(即不包含非0且非-1元素)，則結(jié)束。⑥若無平行線路，則運(yùn)用原則5添加新斷點到BPS，再轉(zhuǎn)至步驟④。⑦若存在強(qiáng)關(guān)聯(lián)平行線路保護(hù)組，運(yùn)用原則2添加新斷點到BPS。⑧若存在平行線路保護(hù)對而存在強(qiáng)關(guān)聯(lián)平行線路保護(hù)組，則運(yùn)用原則3添加新斷點到BPS。⑨若存在弱關(guān)聯(lián)平行線路保護(hù)組，運(yùn)用原則4添加新斷點到BPS并轉(zhuǎn)至步驟④; 否則直接轉(zhuǎn)至步驟④。

5 算例分析

系統(tǒng)接線及保護(hù)分布如圖3所示。基于所提計算方法，可求解該網(wǎng)絡(luò)的最優(yōu)MBPS。

根據(jù)公式(5)算出網(wǎng)絡(luò)中38個保護(hù)的重要度，如表1所示。根據(jù)系統(tǒng)接線圖可得初始的保護(hù)重要度矩陣、保護(hù)歸屬矩陣、保護(hù)關(guān)聯(lián)矩陣，并設(shè)置BPS={}。

圖3 算例系統(tǒng)

①保護(hù)23的Od=0，將其選為斷點并同步更新保護(hù)三類矩陣,BPS={23};保護(hù)7、8、31、32、36、37的入度均為1,以化簡原則2更新三類矩陣; 化簡后,平行線路保護(hù)集為{1, 2}、 {5, 6}、 {3, 4}、 {21, 22}、 {9, 10}、 {19, 20}、 {29, 30}、 {34, 35},其中{1, 2}、{3, 4}構(gòu)成一組強(qiáng)關(guān)聯(lián)平行保護(hù)對，將保護(hù)1、2、3、4選為斷點,同時更新三類保護(hù)和平行線路保護(hù)集合，BPS={23, 1, 2, 3, 4}。②這時,平行線路保護(hù)集為:{9,10}、 {19,20}、{29,30}、{34,35}。其中{19, 20}、{29, 30}構(gòu)成弱關(guān)聯(lián)平行保護(hù)對,根據(jù)斷點選取原則4選保護(hù)19、20作為斷點,并更新三類保護(hù)和平行線路保護(hù)集合,BPS={23, 1, 2, 3, 4, 19, 20}。③這時,平行線路保護(hù)集為:{29, 30}、{34, 35}。保護(hù)11、12的入度為1,以化簡原則2更新三類矩陣; 保護(hù)29、30、34、35的入度均為2,但是{29，30}的保護(hù)重要度之和的平均值小于{34,35}的,故選29、30作為斷點,更新三類矩陣,BPS={23, 1, 2, 3 , 4, 19, 20, 29, 30}。④此時,不存在平行線路,保護(hù)33的入度為0,按化簡原則1更新三類矩陣;保護(hù)34、35的入度為1,以化簡原則2更新三類矩陣,保護(hù)27的出度為1,再以化簡原則2更新三類矩陣,出現(xiàn)自環(huán)頂點28,將其選為斷點,以化簡原則4更新三類矩陣,BPS = {23 , 1, 2, 3, 4, 19, 20, 29, 30, 28}。⑤此時，網(wǎng)絡(luò)中無平行線路，按原則3選擇斷點。保護(hù)13、14、16、17的入度均為2，而保護(hù)13、14的保護(hù)重要度最小, BPS={23, 1, 2, 3, 4, 19, 20, 29, 30, 28, 13}或者{23 , 1, 2, 3, 4, 19, 20, 29, 30, 28, 14},并同時更新三類矩陣。⑥若把保護(hù)13選為斷點，保護(hù)9、10、17、24的入度均為1,以化簡原則2更新三類矩陣,保護(hù)15、18的出度均為1,以化簡原則3更新三類矩陣,出現(xiàn)自環(huán)頂點14、25,將其選為斷點,以化簡原則4更新三類矩陣,網(wǎng)絡(luò)只存在頂點16,保護(hù)歸屬矩陣為空,算法結(jié)束,MBPS= {23, 1, 2, 3, 4, 19, 20, 29, 30, 28, 13, 14, 25}。同理，若把14選為斷點,得到的MBPS是相同的。

表1 算例系統(tǒng)中所有保護(hù)的重要度

6 結(jié) 語

提出基于網(wǎng)絡(luò)化簡和保護(hù)三類矩陣求取MBPS計算方法，解決了平行線路判據(jù)問題，彌補(bǔ)了已有算法的不足?；诰仃囘\(yùn)算，效率高效，能夠?qū)崟r反映網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，符合電力系統(tǒng)實際情況。最后通過算例分析，證明所提算法的有效性和可行性。

[1] 劉丹,呂飛鵬.基于網(wǎng)絡(luò)化簡和配合關(guān)系的最小斷點集計算方法[J].電力系統(tǒng)自動化，2008，32(16)：24-27.

[2] 李運(yùn)坤,呂飛鵬,陳新,等．基于節(jié)點重要度估計的多組同基最小斷點集選取方法[J].電力系統(tǒng)自動化,2010,12(34):58-60．

[3] 曹一家,陳曉鋼,孫可.基于復(fù)雜網(wǎng)絡(luò)理論的大型電力系統(tǒng)脆弱線路識別[J]．電力自動化設(shè)備，2006，26(12)：1-5, 31．

[4] 樂陽，龔健雅.最短路徑算法的一種高效率實現(xiàn)[J].武漢測繪科技大學(xué)學(xué)報，1999, 24(3): 209-212.

[5] 王亮, 劉艷, 顧雪平,等.綜合考慮節(jié)點重要度和線路介數(shù)的網(wǎng)絡(luò)重構(gòu)[J].電力系統(tǒng)自動化，2010，34(12)：29-33.

[6] LIN Henming, JOU Jingyang. On Computing the Minimum Feedback Vertex Set of a Directed Graph by Contraction[J]. IEEE Trans on Computer-aideded Design of Integrated Circuits and Systems, 2000,19(3):295-307.

[7] Donghua Ye, Jing Ma, Zengping Wang. A Novel Method for Determining Minimum Break Point Set Based on Network Reduction and Relays Incidence Matrix[C]. Critical Infrastructure (CRIS), 2010 5th International Conference on,2010:1-5.