基于割节点辨识的电网局部拓扑跟踪方法

刘大勇，靳彦辉，李秀杰

（国网长春供电公司，长春 130021）

电网拓扑分析是电力系统各种实时应用软件的基础［1－5］。一般情况下，开关变位只会引起电网局部拓扑结构发生变化，因此，提高电网局部拓扑跟踪方法的效率对于保证这些应用软件的实时性具有至关重要的作用。

开关闭合后，不需要拓扑搜索，局部拓扑跟踪过程简单。开关断开后，首先在厂站内进行拓扑搜索，判断开关断开是否引起节点分裂。若节点发生分裂，则继续网络搜索，判断是否发生电气岛分裂，并根据网络搜索结果划分电气岛。由于网络搜索的节点规模远大于厂站搜索的节点规模，开关变位后拓扑跟踪的效率主要取决于网络搜索的效率。目前，大多数文献在节点分裂后，直接对全网展开搜索，确定电气岛是否发生分裂及电气岛划分［3－5］。事实上，电力系统实际运行中，只有少数节点处发生节点分裂，才会引起电气岛分裂，故这些方法大大降低了局部拓扑跟踪的效率。由图论知识可知，只有割节点分裂才可能引起电气岛分裂。本文将割节点的辨识引入到局部拓扑跟踪过程中，把割节点分为辐射型和环网型两类，提出了割节点分裂引起电气岛分裂的判据，可以避免无效的网络搜索。

1 割节点的辨识方法

1.1 割节点分类

将电网抽象为简单无向图G。根据割节点在电网拓扑图中的位置，将割节点分为辐射型和环网型两类。

辐射型割节点必须同时满足两个条件：一是其连接的所有支路都是割支路；二是其移除后，只存在一个包含回路的连通子图。除辐射型割节点以外的所有割节点均为环网型割节点，见图1。

辐射型和环网型割节点具有不同的特点，应采取不同的辨识方法。

图1 两类割节点示意图

1.2 辐射型割节点辨识

由图论知识可知，树中的支路均为割支路，除根节点和叶子节点外全是割节点。根据辐射型割节点的定义，该类型割节点位于电网拓扑图的终端，具有树的结构特征。

记节点Vi的度为D（Vi），Vi的下一层节点为与Vi直接相连但未添加到任何搜索路径链表的节点，Vi的上一层节点为与Vi直接相连且已添加到搜索路径链表的节点。以图2所示的辐射型割节点搜索过程示意图为例，辨识算法如下。

a.以D（Vi）的节点作为首节点，建立搜索路径链表。每一个节点对应一条搜索路径链表，将所有搜索路径链表置未终止标志，见图2中的F1、F2和F3。

b.选择任一条未终止的搜索路径链表Fi，搜索Fi末节点的下一层节点Vnext。根据Vnext的节点度特征分以下3种情况处理：若D（Vnext）＝k＋1（k＝1），k表示Vnext上一层节点数量，将Vnext添加到Fi，如图2中添加到F2中的V4；若D（Vnext）＝k＋1（k＞1），将Vnext添加到Fi，终止Vnext上一层k个节点对应的k条搜索路径链表。以Vnext为首节点建立一条新的搜索路径链表，见图2 中的F4；若D（Vnext）＞k＋1（k＞1），则将Vnext添加Fi后终止Fi，见图2中的F5。

c.当所有搜索路径链表都终止时，停止搜索，转步骤d；否则，转步骤b。

d.分析图G的所有搜索路径链表，根据不同链表首节点和末节点的对应关系形成搜索树，见图2中的所有搜索路径链表形成的搜索树。

搜索树中，除节点度为1的节点和根节点外，全是辐射型割节点。遍历图G的所有搜索树，保存全网的辐射型割节点。

1.3 环网型割节点辨识

环网型割节点的辨识本质上需要全网的拓扑连接信息。因为节点阻抗矩阵元素包含了全网拓扑连接信息，所以利用局部节点的互阻抗和自阻抗就可以辨识环网型割节点［6］。

图2 辐射型割节点搜索过程

假设V为待辨识的环网型割节点，与V直接相连的k节点记为｛Vi｜i＝1，2，…，k｝。当V从图中G移除后，原图分裂为m个连通子图。根据这k个节点所属的连通子图，将其划分为m个节点集，记为，见图3a，算法步骤如下。

a.将全网等值到V及其相连的k个节点上。对等值节点阻抗矩阵求逆并逻辑化，得到等值节点邻接矩阵［1］。删除邻接矩阵中V对应的行和列，将剩余k个节点置未访问标志。取m＝1，清空

b.任选一个未访问的节点Vi添加到。根据等值节点邻接矩阵，以Vi为起点进行广度优先搜索。将搜索到的节点置已访问标志并添加到

c.当已访问的节点数等于k时，停止搜索，转步骤d；否则m＝m＋1，转步骤b。

d.若m＝1，则V不是割节点；若m＞1，则V是割节点。

应用以上算法，遍历除辐射型割节点外的所有节点，保存全网的环网型割节点。

图3 割节点分裂示意图

1.4 割节点分裂引起电气岛分裂的判据

由于辐射型割节点分裂必然导致电气岛分裂，只需讨论环网型割节点分裂引起电气岛分裂的判据。记环网型割节点V分裂成两个节点Vi1，Vi2且与Vi1，Vi2直接相连的节点集合为和见图3b。根据环网型割节点的辨识结果，其分裂引起电气岛分裂的判据如下：

任取割节点V的一个节点集，则只属于或只属于，即或

2 电气岛划分方法

2.1 辐射型割节点处电气岛划分方法

当电气岛在辐射型割节点处发生分裂，根据辐射型割节点辨识过程的搜索树信息，可以快速划分电气岛，划分步骤如下。

c.将搜索到的节点划分为一个电气岛，电网中剩下的节点划分为另一个电气岛。

该方法本质上是确定了网络搜索的方向。处于该搜索方向上的电气岛仅包含少数节点且没有回路，故避免了网络搜索方向的不确定性以及网络搜索方法对复杂环网适应性差给搜索效率带来的不利影响。

2.2 环网型割节点处图形分割方法

在电网拓扑图的环网型割节点处，离线地将图分割为若干连通子图。当电气岛在环网型割节点处发生分裂，根据图的分割方式和分割顺序，可以直接划分电气岛。

雪莲原产于喜马拉雅山脉，扎根于高山草甸土之中。雪莲不喜欢生长在平缓地区，只有在海拔三四千米左右的高原山坡和冰碛岩缝之中才能看到它的身影。高山地带的气候十分寒冷，可以低至零下几十摄氏度，并且常年风雪交加，再加上空气稀薄缺氧，一般的植物在这样恶劣的环境中根本无法存活，但是雪莲这种菊科草本植物却可以在如此严峻的气候条件下顽强地活下来。

谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的分割问题［7］。一方面，割节点移除后，同一连通子图内的节点存在较强的电气联系，任意两个连通子图之间节点无联系，各连通子图属于理想的分离簇；另一方面，谱聚类算法只需图的相似矩阵信息。相似矩阵描述了电网中两个节点的相似度，可以用割节点移除后图的邻接矩阵作为相似矩阵，所以，利用谱聚类算法分割图形具有分割准确、编程实现简单，不受网络结构影响等优点。选用Perona和Freeman提出的基于最小割集准则的谱聚类算法，算法的步骤如下：

建立图G的相似矩阵W，即割节点移除后图G的邻接矩阵；求相似矩阵W的最大特征值对应的特征向量X；遍历特征向量X的元素，将Xi＝0的节点划分为一个连通子图，剩下的节点划分为另一个连通子图。

该谱聚类算法每次只能进行图的二剖分。若割节点移除后图形分割为m（m＞2）个连通子图，则依次移除割节点与其节点集的连接支路，应用谱聚类算法分割出一个连通子图，直到原图被分割为m个连通子图。

a.任选一个割节点并保存到DCutNum［1］。

b.在待分割的连通子图中移除DCutNum［i］，利用谱聚类算法分割得到mi个连通子图。将每一个连通子图包含的节点集合保存到对应的，再把当前割节点DCutNum［i］添加到每一个

c.若i等于所有环网型割节点的个数，则图形分割结束；否则，在分割得到的连通子图中选择下一个割节点并保存到DCutNum［i＋1］，转步骤b。

图4 电网拓扑图分割示意图

从以上分割过程可以看出：电网拓扑图以递归的方式被分割为若干连通子图。因为每一次分割总是在已经分割得到的连通子图中进行，所以图形分割的计算量随着次数的增加显著减小。

2.3 环网型割节点处电气岛划分方法

假设在割节点DCutNum［i］处发生电气岛分裂。根据DCutNum［i］的 分 裂 方 式，形 成 节 点 集 合和。确 定DCutNum［i－1］所 在 的，并 判 断与是否存在交集。若存在交集，则将与存 在 交 集 的合 并 在 一 起 划 分 为 一个电气岛，剩下的节点划分为另一个电气岛。

以图4为例简要说明以上方法。若在DCutNum［3］处发生电气岛分裂，且由DCutNum［3］的分裂方式可得与存在交集，与存在交集。因为包含DCutNum［2］，所以将中的节点划分为一个电气岛，剩下的节点划分为另一个电气岛。

在环网型割节点处划分电气岛只需做多次交集和并集运算，计算量小，不需要在线网络搜索。

根据前述方法得到电网局部拓扑跟踪的流程见图5。

3 算例分析

以IEEE 39节点系统为研究对象，将其抽象为简单图（见图6）。

3.1 辐射型割节点的辨识

以V33和V34为首节点建立搜索路径链表形成搜索树为例，搜索过程见图7，图中○为搜索路径表终止标志，d为节点度，n为上一层节点数。由图7可知，该搜索树包含3条搜索路径链表：F1＝（34，20，19）、F2＝（33，19）、F3＝（19，16），其对应的辐射型割节点为V20、V19。

3.2 环网型割节点的辨识

以V26的辨识为例。应用环网型割节点辨识算法可得：m＝2，。故V26是环网型割节点。

全网的割节点辨识结果见图8。从图8 可知，全网共有2个辐射型割节点，9个环网型割节点和28个普通节点。当开关变位引起节点分裂后，至少有28/39＝71.8%的概率不需要进行网络搜索，故大幅度提高了局部拓扑跟踪的效率。

3.3 利用谱聚类算法分割图形

以移除割节点V16的图形分割为例。由环网型割节点辨识结果可知，V16移除后全网分割为3个连通子图且，故需要进行两次图形分割。

图5 电网局部拓扑跟踪流程图

图6 IEEE39节点系统简单图

在原图中，移除V16与的连接支路，利用谱聚类算法分割得到和，然后，在连通子图中，移除V16与的连接支路，将继续分割为和（见图8）。

3.4 辐射型割节点处划分电气岛

图7 搜索树形成过程

假设辐射型割节点V19分裂且。由图7的搜索树可知，包含V19的父节点V16，故将节点集合｛19，33，20，34｝划分为一个电气岛，剩下的节点划分为另一个电气岛。

3.5 环网型割节点处划分电气岛

按表1的所示的图形分割顺序分割原图，结果见图9。

表1 图形分割顺序

以割节点V16分裂划分电气岛为例。假设V16分裂后。根据V16的节点集合及，应用电气岛分裂判据可知，V16分裂后电气岛将发生分裂。根据全网图形分割结果，得到移除V16后的连通子图节点集合为：

由以上电气岛划分过程可知，在辐射型割节点处划分电气岛，只需搜索节点数少且没有环网的局部电网，搜索速度快且不受复杂环网结构的影响；在环网型割节点处划分电气岛，只需做多次集合运算，计算量小且避免了在线网络搜索。总之，基于割节点辨识的电网局部拓扑跟踪方法可以显著提高局部拓扑跟踪的效率。

图8 全网的割节点和在处的图形分割结果

图9 全网分割结果

4 结论

开关变位后，在大多数节点处发生节点分裂不会引起电气岛分裂。若节点分裂后直接网络搜索，大大降低了拓扑跟踪的效率。本文提出的局部拓扑跟踪方法具有以下优点。

a.当节点分裂后，可以判定节点分裂是否引起电气岛分裂，避免了大量的无效网络搜索；

b.在辐射型割节点处发生电气岛分裂，通过确定网络搜索方向，只需搜索包含少量节点的无环局部网络，就可以划分电气岛；

c.在环网型割节点处发生电气岛分裂，只需做多次集合运算，就可以划分电气岛，计算量小，无需在线网络搜索。

［1］ 张晋芳，王增平，张亚刚，等.基于虚拟阻抗的厂站内拓扑分析新方法［J］.电工技术学报，2011，26（02）：187－194.

［2］ 徐岩，宋艳争，张亚刚，等.基于广域测量系统的改进电网拓扑结构识别［J］.电网技术，2010，34（09）：88－93.

［3］ 宋少群，朱永利，于红.基于图论与人工智能搜索技术的电网拓扑跟踪方法［J］.电网技术，2005，29（19）：45－49.

［4］ 梅念，石东源，段献忠.基于图论的电网拓扑快速形成与局部修正新方法［J］.电网技术，2008，32（13）：35－39.

［5］ 陈星莺，孙恕坚，钱锋.一种基于追踪技术的快速电力网拓扑分析方法［J］.电网技术，2004，28（05）：22－24.

［6］ 段献忠，杨雄平，石东源.基于电气耦合路径分析的割支路和割节点辨识算法［J］.中国电机工程学报，2007，27（34）：26－32.

［7］ 蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述［J］.计算机科学，2008，35（7）：14－18.