利用2－树计算环网方向保护配合最小断点集

周文越，吕飞鹏

(四川大学 电气信息学院，四川 成都 610065)

0 引言

随着电网的规模逐渐扩大，并逐渐形成了相互嵌套的复杂网络[1，2]。这加大了继电保护整定计算的难度，作为复杂环网方向保护整定计算的第一个步骤，计算MBPS是整个整定计算的基础，也是计算量最大的一个部分。

现有的计算MBPS的方法基本上可分为两种。一种是基于图论的方法求解 MBPS[3～8]，这种方法清晰直观，理论上能求得最优解，但构造电网有向简单回路矩阵已经被证明是与网络规模呈指数复杂性的 NP完全问题 (NP Complete Problem)，即不可能在多项式计算时间下得到最优解，因此，当电网规模扩大到一定程度之后，其计算量和复杂性是难以接受的，并且在寻找到简单回路后，还需进行二次规划才可以得到MBPS。另一种是基于保护配合的方法[9～12]，因与网络规模呈多项式复杂性，因此收敛速度比图论算法更快，减小了计算量，但同时，因算法的实现完全基于对全网保护配合依赖关系集的动态搜索调整，具有一定随机性，在对大规模复杂环网进行计算时，计算仍较繁琐，而且得到的断点集基数很难达到最小。

本文提出了一种计算MBPS的新方法，首先将网络分割成若干个不可分连通图，然后找出每个子图的断点2－树 (定义2)，之后便可以确定子图的MBPS，将每个子图的MBPS相加便可得到整个网络的 MBPS。计算简单、快速，且得到的MBPS基数可达最小。

1 网络分解

现代电网通常是由多个子网组成，每个子网之间由联络线连接，且子网之间不存在回路。因此，根据这一特点，在计算MBPS前，可将网络分解为几个子网络，这将大大降低计算复杂性。分割网络的关键是找到网络的割节点，所谓割节点是指:对于一个连通图G，若在割节点处断开网络，则连通图G会被分解成若干个互不连通的子图。可用文献[13]提出的广度优先搜索技术网络的割节点。其基本思想为将网络中的节点编号后，按节点编号依次消去节点以及与其相连的支路。从剩余节点出发，将其能搜索到的节点数与剩余网络节点数比较，若不相等，则该消去节点为割节点。另外，对于终端线路，除终端节点外的所有的节点都为割节点，因此在搜索割节点时可先去掉终端线路。

1.1 搜索割节点的步骤

(1)将网络的双回线和多回线用单支路代替，再去掉终端线路。形成网络的节点邻接矩阵A，A为n阶方阵，n为网络节点数。矩阵A的第i行第j列的元素aij等于连接第 i个节点与第j个节点的支路数。

(2)假设化简后的网络共有s个节点。定义数组searched为已搜索到的节点集合。为每个节点定义搜索状态标志CF，初始CF都为0，若节点已被搜索过，则置其CF为1。选择一个需判断的节点X，删除该节点在矩阵 A中对应的行和列。

(3)假设节点P为度数 (连接节点的支路数)最大的节点，则将节点P作为广度优先搜索的第一层，并归入searched数组，searched数组的元素个数m即为1，将节点P的CF置1。

(4)假设有k个节点与节点P直接相连，则将这k个节点全部置入searched数组，相应的，m变为k+1，同时将这些节点的 CF置1。然后将这k个节点作为搜索的第二层进行广度优先搜索，继续将与这k个节点相连的节点作为第三层。重复此过程，当搜索到searched数组中已包含的节点时，终止该条链路的搜索。当搜索到某一层的所有节点均包含在searched数组中时，终止搜索。

(5)若此次搜索结束后，m小于s－1，则节点X为割节点，反之则不是。

(6)若节点X不是割节点，选择下一个需判断的节点重复步骤 (2) ～ (5)寻找割节点。若节点X是割节点，则在节点X处断开网络，对各个子网重复步骤 (2) ～ (5)寻找割节点。

如图1所示的网络，在割节点1和4处断开网络可得图2所示的4个子图，每个子图都是一个不可分连通图。

图1 分解前的网络Fig.1 The whole network

图2 分解后的网络Fig.2 The partitioned network

将网络分解为若干个子图后，求解全网的MBPS转变成为求解每个子图的MBPS。需要特别说明的是，若子图为单条线路，如图2(d)所示，如果该线路为非终端线路，则该线路上的两个保护不用设为断点。因为在这种情况下，线路上的两个保护所需配合的主保护都在所连接的子网中，子网的整定顺序确定了，则这两个保护的整定顺序也就确定了;若该线路为终端线路，则需要将终端线路的首端保护设为断点。因为对于终端线路的首端保护，由于没有与之配合的主保护故需单独整定。

2 计算MBPS

2.1 断点2－树

首先给出图论中关于2－树的定义。

定义1:2－树是指连通图G的某个树T去掉了其中任何一树支的子图。2－树包含G的全部节点;不包含回路;且为两个连通片，其中一个部分亦为一个孤立节点。如图3所示，其中的粗线部分为一种2－树。

图3 断点2－树示意图Fig.3 The schematic drawing of break point 2－tree

在图3中，边集S1= {a，e}和S2= {g}构成2－树。余下的边构成集合 S3= {c，b，d，h，f}，在本文中定义S3这样的集合为2－树补集。

定义2:在图G中，有一种特殊的2－树，这种2－树补集里的每一条边都连接了2－树的两个不同部分，即边的两个顶点分别在2－树的不同部分，本文称这样的2－树为断点2－树。如图3所示的2－树，对于补集S3里的边c，其顶点1和3分别在集合 S1和 S2中，S3中的其它4条边 b，d，h，f亦是如此，故此2－树为断点2－树。

2.2 计算子网MBPS原则

对于网络中的每一个方向保护，可以用一个箭头表示，箭头的方向指向被保护线路，如图4(a)所示。求取最小断点集等同于求这样一个问题:在网络中尽可能少的放置箭头，当沿任意方向走过网络中的任意回路时，至少将经过两个箭头，其中一个箭头的方向与所走方向相同，另一个箭头的方向与所走方向相反，则被放置的箭头所代表的保护组成网络的MBPS。如图4(b)所示，该图上的箭头所代表的保护表示了一种图4(a) 的MBPS。

上述求取 MBPS的原则证明如下:MBPS的求解可归结为图论中的最小反馈边集问题，即给定一个有向图G，找到一个具有最小基数的边集E，从G中去掉E中的边，G的所有回路将被解环。将网络中的方向保护用箭头表示后，每一个箭头等价于有向图中的一条有向边，则网络中的任意一个回路必定对应有向图中两个方向相反的有向回路，要断开这两个有向回路就必须断开每个有向回路的一条有向边，也就对应于网络中回路的两个方向相反的箭头。最少箭头放置方案对应MBPS。

图4 方向保护示意图Fig.4 The schematic drawing of direction protective relay

2.3 计算子网MBPS方法

根据2.2所提出的原则。本文通过如下方法寻找子网的MBPS。

S1和S2中的边构成网络的断点2－树，S3为2－树补集。在S3里的每一条边靠近S1的一端放置箭头，则这些箭头所代表的保护即为MBPS。如图4(b)所示。

上述方法证明如下:S1和S2构成网络的断点2－树，由于S1和S2中不包含任意回路，因此要形成回路必须包含S3中的边。S3中的边的两个顶点分别在S1和S2中，因此S3中的边构成了网络的一个割集。当沿任意方向走过网络的任意一条回路时，必定会经过S3中的一条边进入S1，然后经过S3中的另一条边离开S1。则必然存在S3中的两条边，其靠近S1一端上的箭头，一个与所走方向同向另一个反向。因此按上述方法放置箭头，则任意回路必定会包含至少一个与所走方向相反的箭头和一个与所走方向相同的箭头。

由文献[14]可知，对于不可分连通图其最少断点的数目 (最小基数)为

式中:NL为网络连支数。对网络进行分割后，每个子网络都是不可分连通图，因此满足式 (1)的成立条件。对于任意一个不可分连通图，其2－树补集中边的数量也为NL+1。因此可得出结论，对于任意一个子网一定能找出至少一个断点2－树，进而利用本文所出的方法求出子网的MBPS。将所求得的子网MBPS相加便可得到全网的MBPS。

因此，可以看出本文求MBPS的核心是找到网络的2－树以此得到断点2－树。文献[15]给出了一种快速求取2－树的方法。在此之前先给出关联矩阵的定义。

定义3:在有向图G中，V= {v1，．．vn} 和E={e1，．．．en}分别为有向图的顶点集和边集，定义n行m列矩阵M为有向图G的关联矩阵，矩阵中的元素为

式中:mij为矩阵M中的第 i行第j列元素。本文所涉及的都为无向图，因此在求关联矩阵之前需要将每条边任意加上方向以得到该无向图对应的有向图。

由于任意一个2－树所含边的数量为 Nv－2(Nv为网络顶点数)，因此首先列出待求子网络的所有 Nv－2条边的组合，对于图3有: {a，b，c}、{a，b，d}、{a，b，f} …分别取出关联矩阵中相应边对应的列得关联子矩阵。根据文献[13]可知:若某关联子矩阵的秩为 Nv－2，则对应的边可组成该子网络的2－树。

由于2－树将网络分成两个部分，因此可以按照两部分对应的顶点将2－树关联子矩阵进行分块，然后根据2－树关联子矩阵元素间的关系可确认该2－树是否为断点2－树。以图3所示网络为例说明此过程。

对于图3所示网络，首先给每一条边任意加上方向得到有向图，如图5所示。

图5 图3对应的有向图Fig.5 The digraph of fig 3

然后，列出所有三条边组成的子图的关联子矩阵，这里以边集 {a，e，g}为例，得到其关联子矩阵，每行代表一个顶点，每列代表一条有向边。

可求出 rank(Ma，e，g) =3，因此边集 {a，e，g}构成该网络的一个2－树。2－树两部分别包含顶点 {1，2，4}和 {3，5}，按此将关联子矩阵分块。从 Ma，e，g中可以看出边 a，e只与第一部分{1，2，4}相关，边g只与第二部分 {3，5}相关，根据断点2－树的定义，可判断该2－树为断点2－树。

2.4 计算子网MBPS步骤

综上所述，可得计算子网MBPS的步骤。

(1)给子网任意标上方向，并形成子网的关联矩阵。

(2)列出子网的所有Nv－2(Nv为网络顶点数)条边的组合，分别形成相应的关联子矩阵，并根据子矩阵的秩找出子网的2－树。

(3)根据2－树的结构，将关联子矩阵分块。根据断点2－树的定义，从2－树中找出断点2－树。

(4)根据断点2－树对子网的划分，利用本文2.3节提出的方法找出子网的MBPS。

3 算例分析

3.1 算例1

图1所示网络被分割成图2所示的几个子网络后，子网络 (c)为一条线路，而又处于网络中，因此保护5和19不需设为断点。子网络(b)和 (c)为平行线路，其断点可设为顶点上的两个保护，即保护1，2和保护17，18。子网络 (c)为一个较复杂的环网，找出断点2－树如图6所示，该断点2－树由边34，45和顶点7构成。S1为顶点 7，S2为边 34，45，S1为边 37，47(两条)，57。于是根据2.3提出的方法可得到该子网的 MBPS为 {8，10，12，13}。在求得每个子网的MBPS后便可得全网MBPS为 {1，2，17，18，8，10，12，13}。用文献[9]提出的方法计算本算例，所得结果一致。

图6 图2(a)的断点2－树Fig.6 The break point 2－tree of fig 2 (a)

3.2 算例2

算例2接线图如图7所示。网络中含有T形线路，因此需加入虚拟保护21，22，23，若求出的MBPS含虚拟保护，则舍去该 MBPS，取相应子网其他断点2－树重新计算。将此网络分割后可得图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)均为一条线路构成的子网，而 (b)处在网络中，不需设断点， (c)处在网络末端，将首端保护18设为断点。

找到子网 (a)的断点2－树，如图9所示。该断点2－树由线路12，14，45，56和顶点3组成。S1为顶点 3，S2为边 12，14，45，56，S1为边12，36(两条)，23，35。于是便可得该子网MBPS为 {6，7，8，9，10}。

图9 图7(a)的断点2－树Fig.9 The break point 2－tree of fig 7 (a)

将各个子网的断点相加，便可得全网的MBPS为 {6，7，8，9，10，18}。所得结果与文献[9]一致。

另外，可以看出利用本文的方法，若子网取不同的断点2－树可得到子网不同的MBPS，将各个子网的MBPS组合，便可得到多组全网的MBPS。

4 结论

本文基于图论中2－树的概念，提出了一种求解环网方向保护配合MBPS的新方法。相比于传统求解MBPS的方法，本文提出的方法相对简单，既不用寻找网络的简单回路，也不需要保护配合关系，通过寻找网络的2－树便可以得到MBPS，且所得MBPS基数最小。具有一定的应用价值。

[1]尚文洁，吉兴全，郑耀东，等．大规模电力系统无功优化的一种分解协调算法[J]．华北电力大学学报，2011，38(6):17－22

[2]艾欣，崔明勇，雷之力．电力系统连锁故障研究综述[J]．华北电力大学学报，2010，38(18):44－51．

[3]冯 艳，徐玉琴，沈志强．一种新的基于图论确定所有最小断点集方法[J]．电力自动化设备，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]陈绩，吕飞鹏，黄妹雅．确定复杂环网方向保护最小断点集的改进离散粒子群优化算法[J]．电网技术，2008，32(21):90－94．

[6]吴晨曦，盛四清，杜振奎，等．地区电网继电保护整定计算智能系统的研究[J]．继电器，2004，32(7):35－44．

[7]乐全明，顾永朋，吕飞鹏．基于GA的环网方向保护配合最小断点集的计算．继电器，2002，30(8):23－26．

[8]吕飞鹏，米麟书，姜可熏．环网方向保护配合最小断点集的神经计算方法．中国电机工程学报，1997，3(17):184－189．

[9]吕飞鹏．基于配合关系计算复杂环网保护最优配合顺序的新方法[J]．电力系统自动化，2005，29(24):65－69．

[10]郑静，万秋兰．函数相关算法在继电保护整定计算中的应用[J]．电力自动化设备，2003，23(1):37－39．

[11]吕飞鹏，刘 丹．基于蚁群算法计算环网保护配合最小断点集的新方法[J]．四川大学学报(工程科学版)，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]陈绩，吕飞鹏，黄姝雅．复杂环网保护配合的网络分割新算法[J]．继电器，2006，34(23):6－10．

[14]言昭．应用图论优化复杂环网继电保护整定配合的简便算法[J]．电力系统及其自动化学报，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．