电力系统网络拓扑分析算法概述

［摘 要］随着电网状态估计技术的发展和使用计算机进行实时监控日益得到的广泛应用，无论是实时监控、在线潮流计算、状态估计都离不开对电力接线图的结构进行分析。本文重点概述了计算出网络的实时结构拓扑所采用的算法。

［关键词］算法 搜索 关联矩阵 OSPF协议 分电压等级 有色Petri法

引言

拓扑结构不仅是潮流分析、状态估计等高级应用的基础, 它是电力系统网络分析其他应用软件的基础，它的任务是根据电力网络中开关的开断状况，通过一定的算法计算出网络的实时结构拓扑，进而进行更高级运算以了解电力网络的运行状态和安全稳定性，或者得到拓扑数据供电力系统应用程序使用。同时拓扑分析的效果直接影响着工作人员进行故障估计、诊断和其他应用程序的使用效果。

一、深度或广度搜索法

早期的网络拓扑分析是利用堆栈技术进行搜索。一般是将拓扑结构表述为链表关系，用图论中的搜索技术，如深度优先搜索法和广度优先搜索法分析节点的连通性。这种方法一般需要建立反映拓扑结构的链表，通过处理链表实现拓扑分析，然后以搜索回溯的框架, 利用堆栈记录划分。由于其基本算法采用“堆栈”原理――先进后出的搜索逻辑，程序不可避免采用递归的实现形式，因此编程和维护较复杂，效率较低。况且当应用于实时网络分析时, 在运算时间上不能满足要求。

二、面向对象(OO)的启发式搜索算法

由于在电网的实际运行过程中，状态频繁发生变化的开关占少数，因此将追踪技术引入拓扑分析中，仅在开关状态发生改变时进行局部拓扑分析，可以减少拓扑分析的计算量。在完成网络的初始拓扑分析并构筑了电网的结点树之后，当电网发生开关变位事件时，根据开关变位只造成局都电网拓扑发生变化的特点，采用启发式搜索算法进行电网结点树拓扑的跟踪。针对不同的变位事件，分开关“开”和“合”两种情况进行分析。实现拓扑跟踪OO模型的启发式拓扑分析方法，利用OO技术可扩展拓扑算法的适用范围。

三、基于关联矩阵的集合划分算法

文献[4]是以SVG图形模型为基础，再结合CIM 和XML的特点，采用改进的集合划分方法---基于关联矩阵的网络拓扑分析方法，将拓扑分析与代数分析有机结合，这样可进一步提高计算效率。在改进方法中，先将连接点都新建成各个独立的拓扑点，其中连接点中包含了与拓扑点的关联信息，这样在归并拓扑点时就避免了遍历比较；在拓扑点归并过程中只销去拓扑点中的信息，而拓扑点对象依然存在，最后在进行一次总的导入。

四、基于OSPF协议的算法

目前获取网络拓扑普遍采用的方法是基于SNMP协议或ICMP协议的主动探测技术，但此类技术容易增加网络负担，影响其正常运行。文献[5]提出了一种基于OSPF协议数据库描述报文和链路状态更新报文的拓扑分析算法。因为OSPF协议报文中含有网络拓扑信息，为有效处理报文数据，所以采用这种算法。该算法的主要思想是：将OSPF协议报文按区域划分，采用模拟路由器的工作方式构造链路状态数据库，分别计算各个区域的拓扑，再利用边界路由器连接分散的拓扑得到完整的网络拓扑。

五、分电压等级算法

该拓扑分析方法只搜索断开开关所在的厂站电压等级，大大减小了搜索的空间，提高了网络拓扑分析的效率。其基本原理为：首先对所有状态发生变化的开关(或刀闸)信息进行扫描，根据开关信息判断开关的首末连接节点是否在同一电压等级。分级搜索法流程见图所示。

当开关状态发生变化时，可能会对初始拓扑节点编号造成以下几种影响：

(1)网络内开关操作后，未造成拓扑节点变化，连接节点仍属于同一拓扑节点；(2)开关开断后分裂出一个或多个拓扑节点；(3)开关闭合后删除一个或多个拓扑节点；(4)以上情况的组合。

在初始拓扑节点编号的基础上中，以上几种情况可以归结为两类来处理：

(1)新增的拓扑节点，其编号排在初始拓扑节点最大编号之后；(2)不增加新拓扑节点，采用初始拓扑节点编号。

这样，网络中任何开关操作对拓扑节点造成的任何影响都可以在初始拓扑节点的基础上归结为两类操作，简单明了，易于实现。

六、基本分析单元的有色Petri法

将整个电网拓扑分析问题分解为若干基本分析单元，采用基本分析单元的有色Petri网模型，只重新计算受开关状态变化影响的分析单元，减小了搜索的空间，可提高拓扑分析的效率。

七、结语

以上几种利用数据结构加上特定的算法来实现拓扑分析的改进方法，目的是为了加快拓扑的速度和效率，得到准确的拓扑结构。

参考文献：

[1] 于尔铿：电力系统状态估计．北京：水利电力出版社，1985

[2] 刘娜：电网拓扑结构分析研究.科技资讯，2008，18（20）

[3] 董张卓，孙启宏等．采用面向对象技术和方法的电力系统网络拓扑的快速跟踪．中国电机工程学报，1998，18(3)：178～181

[4] 周昊 袁泉等： 基于公共信息模型CIM和XML的电力系统拓扑分析软件.计算机应用与软件，2007 ，24（1）

[5] 王慧等：基于OSPF协议报文的网络拓扑分析算法.计算机工程.2008,34(6)

[6] 朱文东 刘广一 于尔铿等：电力网络局部拓扑的快速算法.电网技术，1996，20(3)：30一33

[7] 赖晓平 周鸿兴： 电力系统网络拓扑分析的有色Petri网模型.电网技术，2000，24(12)：5．10