周文越，呂飛鵬

(四川大學(xué) 電氣信息學(xué)院，四川 成都 610065)

0 引言

隨著電網(wǎng)的規(guī)模逐漸擴(kuò)大，并逐漸形成了相互嵌套的復(fù)雜網(wǎng)絡(luò)[1，2]。這加大了繼電保護(hù)整定計(jì)算的難度，作為復(fù)雜環(huán)網(wǎng)方向保護(hù)整定計(jì)算的第一個(gè)步驟，計(jì)算MBPS是整個(gè)整定計(jì)算的基礎(chǔ)，也是計(jì)算量最大的一個(gè)部分。

現(xiàn)有的計(jì)算MBPS的方法基本上可分為兩種。一種是基于圖論的方法求解 MBPS[3～8]，這種方法清晰直觀，理論上能求得最優(yōu)解，但構(gòu)造電網(wǎng)有向簡單回路矩陣已經(jīng)被證明是與網(wǎng)絡(luò)規(guī)模呈指數(shù)復(fù)雜性的 NP完全問題 (NP Complete Problem)，即不可能在多項(xiàng)式計(jì)算時(shí)間下得到最優(yōu)解，因此，當(dāng)電網(wǎng)規(guī)模擴(kuò)大到一定程度之后，其計(jì)算量和復(fù)雜性是難以接受的，并且在尋找到簡單回路后，還需進(jìn)行二次規(guī)劃才可以得到MBPS。另一種是基于保護(hù)配合的方法[9～12]，因與網(wǎng)絡(luò)規(guī)模呈多項(xiàng)式復(fù)雜性，因此收斂速度比圖論算法更快，減小了計(jì)算量，但同時(shí)，因算法的實(shí)現(xiàn)完全基于對全網(wǎng)保護(hù)配合依賴關(guān)系集的動態(tài)搜索調(diào)整，具有一定隨機(jī)性，在對大規(guī)模復(fù)雜環(huán)網(wǎng)進(jìn)行計(jì)算時(shí)，計(jì)算仍較繁瑣，而且得到的斷點(diǎn)集基數(shù)很難達(dá)到最小。

本文提出了一種計(jì)算MBPS的新方法，首先將網(wǎng)絡(luò)分割成若干個(gè)不可分連通圖，然后找出每個(gè)子圖的斷點(diǎn)2－樹 (定義2)，之后便可以確定子圖的MBPS，將每個(gè)子圖的MBPS相加便可得到整個(gè)網(wǎng)絡(luò)的 MBPS。計(jì)算簡單、快速，且得到的MBPS基數(shù)可達(dá)最小。

1 網(wǎng)絡(luò)分解

現(xiàn)代電網(wǎng)通常是由多個(gè)子網(wǎng)組成，每個(gè)子網(wǎng)之間由聯(lián)絡(luò)線連接，且子網(wǎng)之間不存在回路。因此，根據(jù)這一特點(diǎn)，在計(jì)算MBPS前，可將網(wǎng)絡(luò)分解為幾個(gè)子網(wǎng)絡(luò)，這將大大降低計(jì)算復(fù)雜性。分割網(wǎng)絡(luò)的關(guān)鍵是找到網(wǎng)絡(luò)的割節(jié)點(diǎn)，所謂割節(jié)點(diǎn)是指:對于一個(gè)連通圖G，若在割節(jié)點(diǎn)處斷開網(wǎng)絡(luò)，則連通圖G會被分解成若干個(gè)互不連通的子圖?？捎梦墨I(xiàn)[13]提出的廣度優(yōu)先搜索技術(shù)網(wǎng)絡(luò)的割節(jié)點(diǎn)。其基本思想為將網(wǎng)絡(luò)中的節(jié)點(diǎn)編號后，按節(jié)點(diǎn)編號依次消去節(jié)點(diǎn)以及與其相連的支路。從剩余節(jié)點(diǎn)出發(fā)，將其能搜索到的節(jié)點(diǎn)數(shù)與剩余網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)比較，若不相等，則該消去節(jié)點(diǎn)為割節(jié)點(diǎn)。另外，對于終端線路，除終端節(jié)點(diǎn)外的所有的節(jié)點(diǎn)都為割節(jié)點(diǎn)，因此在搜索割節(jié)點(diǎn)時(shí)可先去掉終端線路。

1.1 搜索割節(jié)點(diǎn)的步驟

(1)將網(wǎng)絡(luò)的雙回線和多回線用單支路代替，再去掉終端線路。形成網(wǎng)絡(luò)的節(jié)點(diǎn)鄰接矩陣A，A為n階方陣，n為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)。矩陣A的第i行第j列的元素aij等于連接第 i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)的支路數(shù)。

(2)假設(shè)化簡后的網(wǎng)絡(luò)共有s個(gè)節(jié)點(diǎn)。定義數(shù)組searched為已搜索到的節(jié)點(diǎn)集合。為每個(gè)節(jié)點(diǎn)定義搜索狀態(tài)標(biāo)志CF，初始CF都為0，若節(jié)點(diǎn)已被搜索過，則置其CF為1。選擇一個(gè)需判斷的節(jié)點(diǎn)X，刪除該節(jié)點(diǎn)在矩陣 A中對應(yīng)的行和列。

(3)假設(shè)節(jié)點(diǎn)P為度數(shù) (連接節(jié)點(diǎn)的支路數(shù))最大的節(jié)點(diǎn)，則將節(jié)點(diǎn)P作為廣度優(yōu)先搜索的第一層，并歸入searched數(shù)組，searched數(shù)組的元素個(gè)數(shù)m即為1，將節(jié)點(diǎn)P的CF置1。

(4)假設(shè)有k個(gè)節(jié)點(diǎn)與節(jié)點(diǎn)P直接相連，則將這k個(gè)節(jié)點(diǎn)全部置入searched數(shù)組，相應(yīng)的，m變?yōu)閗+1，同時(shí)將這些節(jié)點(diǎn)的 CF置1。然后將這k個(gè)節(jié)點(diǎn)作為搜索的第二層進(jìn)行廣度優(yōu)先搜索，繼續(xù)將與這k個(gè)節(jié)點(diǎn)相連的節(jié)點(diǎn)作為第三層。重復(fù)此過程，當(dāng)搜索到searched數(shù)組中已包含的節(jié)點(diǎn)時(shí)，終止該條鏈路的搜索。當(dāng)搜索到某一層的所有節(jié)點(diǎn)均包含在searched數(shù)組中時(shí)，終止搜索。

(5)若此次搜索結(jié)束后，m小于s－1，則節(jié)點(diǎn)X為割節(jié)點(diǎn)，反之則不是。

(6)若節(jié)點(diǎn)X不是割節(jié)點(diǎn)，選擇下一個(gè)需判斷的節(jié)點(diǎn)重復(fù)步驟 (2) ～ (5)尋找割節(jié)點(diǎn)。若節(jié)點(diǎn)X是割節(jié)點(diǎn)，則在節(jié)點(diǎn)X處斷開網(wǎng)絡(luò)，對各個(gè)子網(wǎng)重復(fù)步驟 (2) ～ (5)尋找割節(jié)點(diǎn)。

如圖1所示的網(wǎng)絡(luò)，在割節(jié)點(diǎn)1和4處斷開網(wǎng)絡(luò)可得圖2所示的4個(gè)子圖，每個(gè)子圖都是一個(gè)不可分連通圖。

圖1 分解前的網(wǎng)絡(luò)Fig.1 The whole network

圖2 分解后的網(wǎng)絡(luò)Fig.2 The partitioned network

將網(wǎng)絡(luò)分解為若干個(gè)子圖后，求解全網(wǎng)的MBPS轉(zhuǎn)變成為求解每個(gè)子圖的MBPS。需要特別說明的是，若子圖為單條線路，如圖2(d)所示，如果該線路為非終端線路，則該線路上的兩個(gè)保護(hù)不用設(shè)為斷點(diǎn)。因?yàn)樵谶@種情況下，線路上的兩個(gè)保護(hù)所需配合的主保護(hù)都在所連接的子網(wǎng)中，子網(wǎng)的整定順序確定了，則這兩個(gè)保護(hù)的整定順序也就確定了;若該線路為終端線路，則需要將終端線路的首端保護(hù)設(shè)為斷點(diǎn)。因?yàn)閷τ诮K端線路的首端保護(hù)，由于沒有與之配合的主保護(hù)故需單獨(dú)整定。

2 計(jì)算MBPS

2.1 斷點(diǎn)2－樹

首先給出圖論中關(guān)于2－樹的定義。

定義1:2－樹是指連通圖G的某個(gè)樹T去掉了其中任何一樹支的子圖。2－樹包含G的全部節(jié)點(diǎn);不包含回路;且為兩個(gè)連通片，其中一個(gè)部分亦為一個(gè)孤立節(jié)點(diǎn)。如圖3所示，其中的粗線部分為一種2－樹。

圖3 斷點(diǎn)2－樹示意圖Fig.3 The schematic drawing of break point 2－tree

在圖3中，邊集S1= {a，e}和S2= {g}構(gòu)成2－樹。余下的邊構(gòu)成集合 S3= {c，b，d，h，f}，在本文中定義S3這樣的集合為2－樹補(bǔ)集。

定義2:在圖G中，有一種特殊的2－樹，這種2－樹補(bǔ)集里的每一條邊都連接了2－樹的兩個(gè)不同部分，即邊的兩個(gè)頂點(diǎn)分別在2－樹的不同部分，本文稱這樣的2－樹為斷點(diǎn)2－樹。如圖3所示的2－樹，對于補(bǔ)集S3里的邊c，其頂點(diǎn)1和3分別在集合 S1和 S2中，S3中的其它4條邊 b，d，h，f亦是如此，故此2－樹為斷點(diǎn)2－樹。

2.2 計(jì)算子網(wǎng)MBPS原則

對于網(wǎng)絡(luò)中的每一個(gè)方向保護(hù)，可以用一個(gè)箭頭表示，箭頭的方向指向被保護(hù)線路，如圖4(a)所示。求取最小斷點(diǎn)集等同于求這樣一個(gè)問題:在網(wǎng)絡(luò)中盡可能少的放置箭頭，當(dāng)沿任意方向走過網(wǎng)絡(luò)中的任意回路時(shí)，至少將經(jīng)過兩個(gè)箭頭，其中一個(gè)箭頭的方向與所走方向相同，另一個(gè)箭頭的方向與所走方向相反，則被放置的箭頭所代表的保護(hù)組成網(wǎng)絡(luò)的MBPS。如圖4(b)所示，該圖上的箭頭所代表的保護(hù)表示了一種圖4(a) 的MBPS。

上述求取 MBPS的原則證明如下:MBPS的求解可歸結(jié)為圖論中的最小反饋邊集問題，即給定一個(gè)有向圖G，找到一個(gè)具有最小基數(shù)的邊集E，從G中去掉E中的邊，G的所有回路將被解環(huán)。將網(wǎng)絡(luò)中的方向保護(hù)用箭頭表示后，每一個(gè)箭頭等價(jià)于有向圖中的一條有向邊，則網(wǎng)絡(luò)中的任意一個(gè)回路必定對應(yīng)有向圖中兩個(gè)方向相反的有向回路，要斷開這兩個(gè)有向回路就必須斷開每個(gè)有向回路的一條有向邊，也就對應(yīng)于網(wǎng)絡(luò)中回路的兩個(gè)方向相反的箭頭。最少箭頭放置方案對應(yīng)MBPS。

圖4 方向保護(hù)示意圖Fig.4 The schematic drawing of direction protective relay

2.3 計(jì)算子網(wǎng)MBPS方法

根據(jù)2.2所提出的原則。本文通過如下方法尋找子網(wǎng)的MBPS。

S1和S2中的邊構(gòu)成網(wǎng)絡(luò)的斷點(diǎn)2－樹，S3為2－樹補(bǔ)集。在S3里的每一條邊靠近S1的一端放置箭頭，則這些箭頭所代表的保護(hù)即為MBPS。如圖4(b)所示。

上述方法證明如下:S1和S2構(gòu)成網(wǎng)絡(luò)的斷點(diǎn)2－樹，由于S1和S2中不包含任意回路，因此要形成回路必須包含S3中的邊。S3中的邊的兩個(gè)頂點(diǎn)分別在S1和S2中，因此S3中的邊構(gòu)成了網(wǎng)絡(luò)的一個(gè)割集。當(dāng)沿任意方向走過網(wǎng)絡(luò)的任意一條回路時(shí)，必定會經(jīng)過S3中的一條邊進(jìn)入S1，然后經(jīng)過S3中的另一條邊離開S1。則必然存在S3中的兩條邊，其靠近S1一端上的箭頭，一個(gè)與所走方向同向另一個(gè)反向。因此按上述方法放置箭頭，則任意回路必定會包含至少一個(gè)與所走方向相反的箭頭和一個(gè)與所走方向相同的箭頭。

由文獻(xiàn)[14]可知，對于不可分連通圖其最少斷點(diǎn)的數(shù)目 (最小基數(shù))為

式中:NL為網(wǎng)絡(luò)連支數(shù)。對網(wǎng)絡(luò)進(jìn)行分割后，每個(gè)子網(wǎng)絡(luò)都是不可分連通圖，因此滿足式 (1)的成立條件。對于任意一個(gè)不可分連通圖，其2－樹補(bǔ)集中邊的數(shù)量也為NL+1。因此可得出結(jié)論，對于任意一個(gè)子網(wǎng)一定能找出至少一個(gè)斷點(diǎn)2－樹，進(jìn)而利用本文所出的方法求出子網(wǎng)的MBPS。將所求得的子網(wǎng)MBPS相加便可得到全網(wǎng)的MBPS。

因此，可以看出本文求MBPS的核心是找到網(wǎng)絡(luò)的2－樹以此得到斷點(diǎn)2－樹。文獻(xiàn)[15]給出了一種快速求取2－樹的方法。在此之前先給出關(guān)聯(lián)矩陣的定義。

定義3:在有向圖G中，V= {v1，．．vn} 和E={e1，．．．en}分別為有向圖的頂點(diǎn)集和邊集，定義n行m列矩陣M為有向圖G的關(guān)聯(lián)矩陣，矩陣中的元素為

式中:mij為矩陣M中的第 i行第j列元素。本文所涉及的都為無向圖，因此在求關(guān)聯(lián)矩陣之前需要將每條邊任意加上方向以得到該無向圖對應(yīng)的有向圖。

由于任意一個(gè)2－樹所含邊的數(shù)量為 Nv－2(Nv為網(wǎng)絡(luò)頂點(diǎn)數(shù))，因此首先列出待求子網(wǎng)絡(luò)的所有 Nv－2條邊的組合，對于圖3有: {a，b，c}、{a，b，d}、{a，b，f} …分別取出關(guān)聯(lián)矩陣中相應(yīng)邊對應(yīng)的列得關(guān)聯(lián)子矩陣。根據(jù)文獻(xiàn)[13]可知:若某關(guān)聯(lián)子矩陣的秩為 Nv－2，則對應(yīng)的邊可組成該子網(wǎng)絡(luò)的2－樹。

由于2－樹將網(wǎng)絡(luò)分成兩個(gè)部分，因此可以按照兩部分對應(yīng)的頂點(diǎn)將2－樹關(guān)聯(lián)子矩陣進(jìn)行分塊，然后根據(jù)2－樹關(guān)聯(lián)子矩陣元素間的關(guān)系可確認(rèn)該2－樹是否為斷點(diǎn)2－樹。以圖3所示網(wǎng)絡(luò)為例說明此過程。

對于圖3所示網(wǎng)絡(luò)，首先給每一條邊任意加上方向得到有向圖，如圖5所示。

圖5 圖3對應(yīng)的有向圖Fig.5 The digraph of fig 3

然后，列出所有三條邊組成的子圖的關(guān)聯(lián)子矩陣，這里以邊集 {a，e，g}為例，得到其關(guān)聯(lián)子矩陣，每行代表一個(gè)頂點(diǎn)，每列代表一條有向邊。

可求出 rank(Ma，e，g) =3，因此邊集 {a，e，g}構(gòu)成該網(wǎng)絡(luò)的一個(gè)2－樹。2－樹兩部分別包含頂點(diǎn) {1，2，4}和 {3，5}，按此將關(guān)聯(lián)子矩陣分塊。從 Ma，e，g中可以看出邊 a，e只與第一部分{1，2，4}相關(guān)，邊g只與第二部分 {3，5}相關(guān)，根據(jù)斷點(diǎn)2－樹的定義，可判斷該2－樹為斷點(diǎn)2－樹。

2.4 計(jì)算子網(wǎng)MBPS步驟

綜上所述，可得計(jì)算子網(wǎng)MBPS的步驟。

(1)給子網(wǎng)任意標(biāo)上方向，并形成子網(wǎng)的關(guān)聯(lián)矩陣。

(2)列出子網(wǎng)的所有Nv－2(Nv為網(wǎng)絡(luò)頂點(diǎn)數(shù))條邊的組合，分別形成相應(yīng)的關(guān)聯(lián)子矩陣，并根據(jù)子矩陣的秩找出子網(wǎng)的2－樹。

(3)根據(jù)2－樹的結(jié)構(gòu)，將關(guān)聯(lián)子矩陣分塊。根據(jù)斷點(diǎn)2－樹的定義，從2－樹中找出斷點(diǎn)2－樹。

(4)根據(jù)斷點(diǎn)2－樹對子網(wǎng)的劃分，利用本文2.3節(jié)提出的方法找出子網(wǎng)的MBPS。

3 算例分析

3.1 算例1

圖1所示網(wǎng)絡(luò)被分割成圖2所示的幾個(gè)子網(wǎng)絡(luò)后，子網(wǎng)絡(luò) (c)為一條線路，而又處于網(wǎng)絡(luò)中，因此保護(hù)5和19不需設(shè)為斷點(diǎn)。子網(wǎng)絡(luò)(b)和 (c)為平行線路，其斷點(diǎn)可設(shè)為頂點(diǎn)上的兩個(gè)保護(hù)，即保護(hù)1，2和保護(hù)17，18。子網(wǎng)絡(luò) (c)為一個(gè)較復(fù)雜的環(huán)網(wǎng)，找出斷點(diǎn)2－樹如圖6所示，該斷點(diǎn)2－樹由邊34，45和頂點(diǎn)7構(gòu)成。S1為頂點(diǎn) 7，S2為邊 34，45，S1為邊 37，47(兩條)，57。于是根據(jù)2.3提出的方法可得到該子網(wǎng)的 MBPS為 {8，10，12，13}。在求得每個(gè)子網(wǎng)的MBPS后便可得全網(wǎng)MBPS為 {1，2，17，18，8，10，12，13}。用文獻(xiàn)[9]提出的方法計(jì)算本算例，所得結(jié)果一致。

圖6 圖2(a)的斷點(diǎn)2－樹Fig.6 The break point 2－tree of fig 2 (a)

3.2 算例2

算例2接線圖如圖7所示。網(wǎng)絡(luò)中含有T形線路，因此需加入虛擬保護(hù)21，22，23，若求出的MBPS含虛擬保護(hù)，則舍去該 MBPS，取相應(yīng)子網(wǎng)其他斷點(diǎn)2－樹重新計(jì)算。將此網(wǎng)絡(luò)分割后可得圖8所示的 (a)、(b)、(c)部分。

圖7 算例2接線圖Fig.7 The network of the 2nd example

圖8 算例2分解后示意圖Fig.8 The sub-networks of the 2nd example

圖8中的 (b)和 (c)均為一條線路構(gòu)成的子網(wǎng)，而 (b)處在網(wǎng)絡(luò)中，不需設(shè)斷點(diǎn)， (c)處在網(wǎng)絡(luò)末端，將首端保護(hù)18設(shè)為斷點(diǎn)。

找到子網(wǎng) (a)的斷點(diǎn)2－樹，如圖9所示。該斷點(diǎn)2－樹由線路12，14，45，56和頂點(diǎn)3組成。S1為頂點(diǎn) 3，S2為邊 12，14，45，56，S1為邊12，36(兩條)，23，35。于是便可得該子網(wǎng)MBPS為 {6，7，8，9，10}。

圖9 圖7(a)的斷點(diǎn)2－樹Fig.9 The break point 2－tree of fig 7 (a)

將各個(gè)子網(wǎng)的斷點(diǎn)相加，便可得全網(wǎng)的MBPS為 {6，7，8，9，10，18}。所得結(jié)果與文獻(xiàn)[9]一致。

另外，可以看出利用本文的方法，若子網(wǎng)取不同的斷點(diǎn)2－樹可得到子網(wǎng)不同的MBPS，將各個(gè)子網(wǎng)的MBPS組合，便可得到多組全網(wǎng)的MBPS。

4 結(jié)論

本文基于圖論中2－樹的概念，提出了一種求解環(huán)網(wǎng)方向保護(hù)配合MBPS的新方法。相比于傳統(tǒng)求解MBPS的方法，本文提出的方法相對簡單，既不用尋找網(wǎng)絡(luò)的簡單回路，也不需要保護(hù)配合關(guān)系，通過尋找網(wǎng)絡(luò)的2－樹便可以得到MBPS，且所得MBPS基數(shù)最小。具有一定的應(yīng)用價(jià)值。

[1]尚文潔，吉興全，鄭耀東，等．大規(guī)模電力系統(tǒng)無功優(yōu)化的一種分解協(xié)調(diào)算法[J]．華北電力大學(xué)學(xué)報(bào)，2011，38(6):17－22

[2]艾欣，崔明勇，雷之力．電力系統(tǒng)連鎖故障研究綜述[J]．華北電力大學(xué)學(xué)報(bào)，2010，38(18):44－51．

[3]馮 艷，徐玉琴，沈志強(qiáng)．一種新的基于圖論確定所有最小斷點(diǎn)集方法[J]．電力自動化設(shè)備，2008，35(6):87－90

[4]Damborg M J，Ramaswami R，Venkata S S，et al．Computer aided transmission protection system design，part I:algorithms[J]．IEEE Trans on Power Apparatus and Systems，1984，103(1):104 －114．

[5]陳績，呂飛鵬，黃妹雅．確定復(fù)雜環(huán)網(wǎng)方向保護(hù)最小斷點(diǎn)集的改進(jìn)離散粒子群優(yōu)化算法[J]．電網(wǎng)技術(shù)，2008，32(21):90－94．

[6]吳晨曦，盛四清，杜振奎，等．地區(qū)電網(wǎng)繼電保護(hù)整定計(jì)算智能系統(tǒng)的研究[J]．繼電器，2004，32(7):35－44．

[7]樂全明，顧永朋，呂飛鵬．基于GA的環(huán)網(wǎng)方向保護(hù)配合最小斷點(diǎn)集的計(jì)算．繼電器，2002，30(8):23－26．

[8]呂飛鵬，米麟書，姜可熏．環(huán)網(wǎng)方向保護(hù)配合最小斷點(diǎn)集的神經(jīng)計(jì)算方法．中國電機(jī)工程學(xué)報(bào)，1997，3(17):184－189．

[9]呂飛鵬．基于配合關(guān)系計(jì)算復(fù)雜環(huán)網(wǎng)保護(hù)最優(yōu)配合順序的新方法[J]．電力系統(tǒng)自動化，2005，29(24):65－69．

[10]鄭靜，萬秋蘭．函數(shù)相關(guān)算法在繼電保護(hù)整定計(jì)算中的應(yīng)用[J]．電力自動化設(shè)備，2003，23(1):37－39．

[11]呂飛鵬，劉 丹．基于蟻群算法計(jì)算環(huán)網(wǎng)保護(hù)配合最小斷點(diǎn)集的新方法[J]．四川大學(xué)學(xué)報(bào)(工程科學(xué)版)，2010，42(4):142－147．

[12]Yue Q M，Lu F P，Yu W Y，et al．A novel algorithm to determine minimum break point set for optimum cooperation of directional protection relays in multiloop networks[J]．IEEE Trans on Power Delivery，2006，21(3):1114－1119．

[13]陳績，呂飛鵬，黃姝雅．復(fù)雜環(huán)網(wǎng)保護(hù)配合的網(wǎng)絡(luò)分割新算法[J]．繼電器，2006，34(23):6－10．

[14]言昭．應(yīng)用圖論優(yōu)化復(fù)雜環(huán)網(wǎng)繼電保護(hù)整定配合的簡便算法[J]．電力系統(tǒng)及其自動化學(xué)報(bào)，1989，1(1):80－85．

[15]Bapeswara－Rao V V，Cristinel A．Determination of the Minimum Breakpoint Set of Directional Relay Networks Based on k-Trees of the Network Graphs．IEEE TRANSACTIONS ON POWER DELIVERY，2011，26(4):2318－2323．