电力网络拓扑分析与源流路径链生成算法

陈 彬， 于继来

(1.哈尔滨工业大学电气工程系， 哈尔滨 150001；2.福建省电力有限公司电力科学研究院， 福州 350007)

电力网络拓扑分析与源流路径链生成算法

陈 彬1，2， 于继来1

(1.哈尔滨工业大学电气工程系， 哈尔滨 150001；2.福建省电力有限公司电力科学研究院， 福州 350007)

为快速、准确和全面地求取电力网络源流路径链，提出了一种新型的网络拓扑分析与源流路径链生成算法。该算法首先根据电网某一拓扑结构及其潮流状态形成有向图和送端节点-送电支路邻接表，然后进行两轮拓扑分析，快速生成源流路径树，并由此获取相关的源流路径链。此算法无需通过基于图论邻接终点矩阵的复杂运算，简便快捷。此外，该算法可用于求解电力网络发生局部拓扑和局部潮流流向变化后的路径链局部修改问题。

电力网络； 拓扑分析； 有向图； 源流路径链

电力市场环境下的许多问题都要求掌握电能在不同运行状态下不同网络元件间流动和分配的细节，而如何获得电能在某一源流对之间传输路径的具体构成[1，2]，即电力网络源流路径链的拓扑关系，则是解决上述与路径构成有关问题的前提和关键。然而，在实际电力系统中，电力网络拓扑结构错综复杂，潮流分布状态实时改变，使得电力网络源流路径具有为数众多、交错重叠、变化频繁的特点，这对路径链的求取造成了较大困难。

为快速、准确和全面地求取电力网络源流路径链，本文基于网络拓扑分析方法对电力网络源流路径进行研究，提出了一种新型的网络拓扑分析与源流路径链生成算法。该算法能够进行电力网络源流路径拓扑关系分析，并求取全网源流路径链集合，结合电力网络基电气原理和电气规律，可应用于求解源供电路径、负荷流受电路径、源流对供受电路径、支路源供电路径、支路流受电路径等方面的电气剖分。

1 电力网络有向图的形成

图论作为一种适用于求解与网络拓扑有关问题的成熟理论，在电力系统中得到了广泛应用[3～6]。将一定状态下的电力网络处理为有向图，是源流路径链生成算法的基础。

据图论[7，8]，图由一个顶点集合加一个连接不同顶点对的边集合组成。若将一定状态下的电力网络节点抽象为顶点，支路抽象为边，边的方向取该状态下有功潮流实际流向，则一定状态下的电力网络将被抽象为一个有向图D(V，U)，其中电网节点集合抽象为顶点集合V，以有功潮流方向为正方向的送电支路集合抽象为有序积V×V的子集U，送电支路抽象为U的元素弧au，v，u为弧a的起点，v为终点，分别表示送电支路的送、受端节点。电力系统如图1所示，其状态对应的有向图如图2所示。

图1 6母线电力系统

图2 6母线电力系统有向图

假定研究系统不存在环流。若存在环流，则在生成有向图前将环流拆开。通过对电力网络中某一源的送电路径进行拓扑分析可得，某一源的电能从源出发通过不同的支路集合送到相关的流集合，形成了从某一源出发的源流路径链集合。在图论中，这种集合可抽象为有向图D(V，U)的一棵有向生成树T，它是D(V，U)的一个生成子图而且又是一棵树(无圈连通无向图)，源所在的节点抽象为T的根，流所在的节点抽象为T的叶，其他节点抽象T的分枝顶点，送电支路抽象为T的树枝。图3为对图1系统节点1上的源(简称源1)送电路径进行拓扑分析得到的有向生成树。

图3 源1作为根顶点的有向生成树

同理，在从某一源出发的源流路径链集合中，每一条源流路径链都可以抽象为树T中的一条从根可达对应某一流的分枝顶点的有向道路M，M的长度称为叶的层数。图4为从源1有向生成树中得到的一条从源1到节点6的流(简称流6)的有向道路。

图4 有向道路

2 网络拓扑分析与源流路径链生成算法

在形成的有向图中，集中了全网的源流路径链。然而，各个源流对之间的路径链不是相互独立的，它们在部分拓扑关系上以交错重叠的形式存在，即某一有向边(对应原网络某一条送电支路)可能为不同的源流路径链共用。如何快速准确地从有向图中分析出全网源流之间的拓扑关系，并形成相关的源流路径链集合，这是获得源流路径链的关键。

本文提出一种新型的网络拓扑分析与源流路径链生成算法(流程见图5)。该算法首先根据生成的有向图建立送端节点-送电支路邻接表，然后从每一个源节点开始，以逐层推进的方式进行处理。在每一层，先进行第一轮拓扑分析，利用邻接表添加相邻送电支路和相关节点，在生成不完整源流路径树后进行第二轮拓扑分析，对当前不完整树的有向道路集合进行遍历，获得新的源流路径链，然后再推进到下一层重复进行两轮拓扑分析，直到生成该源对应的完整路径树。此路径树集合包含了电力网络中所有源、流或源流对之间的路径链的具体构成情况。通过对电力网络中的所有源逐一进行上述拓扑分析及路径树的生成，最终可获得整个电力网络全部源流路径树集合。

下面将从送端节点-送电支路邻接表的建立、源流路径树的生成和源流路径链的获取三个方面对该算法进行阐述。

图5 路径链生成算法流程

2.1 送端节点-送电支路邻接表的建立

邻接表形式具有时间复杂度等优点，本文参照邻接表结构对生成的电力网络有向图建立送端节点-送电支路邻接表，以存储和表示电力网络有功潮流分布的拓扑结构关系。

邻接表以顶点出发的单链表的方式存放数据，有向图的顶点集合V作为邻接表的送端节点集合。对集合V中的某一元素，例如送端节点vi，其对应的单链表存放由节点vi发出的所有送电支路的集合Ui。若某节点无送电支路，此节点可看作送电支路条数为0的送端节点。此外，在形成邻接表的过程中，还必须考虑母线上既有源(电源)又有流(负荷)的情况，如图2中的节点1，源1到流1存在源流电气供求关系。为保证求得的源流路径链能够包含此种节点源供应就地节点流的特例，可在求取源流路径链时不将节点1上的源流进行合并简化，而是假设源1经过一条虚拟送电支路与流1发生电气供求关系。这样，在最终形成的送端节点-送电支路邻接表中，就不会遗漏节点源供应就地节点流的特例情形。

根据图3，可生成图6的送端节点-送电支路邻接表。此表考虑了图1网络状态下源1节点功率送出支路的情况，可从中分析电力网络拓扑关系和所有网络源流路径链的构成。

图6 送端节点-送电支路邻接表

2.2 源流路径树的生成

为快速、准确和全面地获取全网源流路径链集合，需对电力网络有向图进行拓扑分析，得到以每一个源为根顶点的全网源流路径树集合。本文基于广度优先搜索的拓扑分析方法，提出利用已建立的送端节点-送电支路邻接表，对有功潮流分布拓扑关系进行分析，逐层推进，遍历全网，最终生成全网源流路径树集合。

以图2所示有向图为例，应用送端节点-送电支路邻接表得到所有相关联的送电支路，逐一添加为树枝，并以每层送电支路的受端节点作为下一层的分枝顶点。如利用图6所示的邻接表生成源流路径树的具体步骤如图7所示。

从以上分析过程可知，对电力网络有向图进行第一轮拓扑分析，在处理每一层节点时，其邻接的所有送电支路都会被添加到源流路径树中，无需遍历全网支路，更无需对已形成的路径进行回溯，从而显著提高了拓扑分析的效率和准确性。同时，某一源的源流路径树集中了从该源出发的所有源流路径链，拓扑关系集中明了，有利于进行第二轮拓扑分析，从而快速准确地获取相关的源流路径链。

2.3 源流路径链的获取

在电力网络有向图中，一条源流路径链可以抽象为在以对应源为根的源流路径树中的一条从根可达对应流的分枝顶点的有向道路，这条道路是其所经过树枝即送电支路集合的有序构成。由源流路径树生成过程可知，同一个流节点在树中出现的次数常常不止一次，而且流不仅出现在叶顶点上，还出现在分枝顶点上。这是因为在电力网络中，流可以从不同的路径链汲取某一源送出的电能，这种普遍存在的源流供求特性增加了电力网络路径链的数量和求取难度。

针对这种特性，需对正在生成的源流路径树进行第二轮拓扑分析，并根据树中流节点的分布，在生成完整源流路径树的同时，得到从对应源出发的所有源流路径链，最终求取全网源流路径链集合。

第二轮是在逐层生成某一源节点对应树的同时对已生成的不完整树进行逐层遍历。首先，当第一轮拓扑分析生成树的第1层时，遍历从根顶点到第1层的分枝顶点所构成的当前有向道路集合，若某一条有向道路的某端顶点为流节点，则可以由该有向道路生成新的源流路径链，添加到从该源出发的源流路径链集合中。然后，遵照第1层同样步骤逐层推进，直到完整的源流路径树生成为止。此时，所得到的源流路径链集合集中了从该源出发的所有源流路径链。

图7 基于广度优先搜索的路径树的生成

对图7所示的各层源流路径生成树进行第二轮拓扑分析，逐层生成新的源流路径链，从而得到从源节点1出发的所有源流路径链。需要注意的是，只有流节点(负荷节点)才需要生成路径链，具体步骤如图8所示。

(a) 步骤1

(b) 步骤2

(c) 步骤3

(d) 步骤4

从以上分析过程可知，在第一轮拓扑分析的基础上进行第二轮拓扑分析，不仅无需重新遍历源流路径树，不增加算法的时间复杂度，提高了拓扑分析的速度，而且还得以在生成源流路径树的同时获取了源流路径链集合，并保证了电力网络源流路径拓扑分析结果的准确和完备。

3 电力网络源流路径链的局部修改方法

在电力系统实际运行中，电力网络结构或运行方式不断变化，导致源流供求关系常常变化，同时也可能引起源流路径链的频繁变化。在正常运行情况下，这种变化往往是局部的，很少涉及全网，然而现有的采用邻接矩阵求取源流路径的方法[1～4]一般不是要重新生成邻接矩阵，就是要对算法做出较大的修改。

针对此问题，本文提出了一种电力网络源流路径链的局部修改算法。在生成全网源流路径链集合后，若局部电力网络发生拓扑或潮流流向变化，该算法首先对邻接表中对应的支路链表进行局部调整，然后，根据邻接表的变化直接修改源流路径树，最后由路径树调整得到的有向道路变化，修改部分源流路径链。该算法无需对整个电力网络进行源流路径拓扑剖分，只需对全网源流路径链集合做出局部调整即可。

3.1 送端节点-送电支路邻接表的局部调整

局部电力网络中的拓扑或潮流分布变化，在拓扑关系上一般表现为某些支路的拓扑或有功潮流方向发生改变。路径链的局部修改算法根据这个特点，在生成全网源流路径链集合后，只需对变化支路的两端节点在送端节点-送电支路邻接表中对应的支路链表进行局部调整，其他支路链表保持不变，而无需重新建立送端节点-送电支路邻接表。

针对支路拓扑变化或有功潮流变向的不同情况，下面介绍对应的邻接表调整方法。

(1)对发生支路闭合的情况，即新增支路，设某一条新增的支路(对应有向图的弧)为au，v，并设有功潮流从u流向v，则u为支路送端节点，v为支路受端节点。对此情况，在送端节点-送电支路邻接表中，只需将送端节点u的支路链表增加这条新增支路au，v即可。

(2)对发生支路开断的情况，即减少支路，设某一条减少的支路为au，v，并设原有功潮流从u流向v，则u为支路送端节点，v为支路受端节点。对此情况，在送端节点-送电支路邻接表中，只需从送端节点u的支路链表中去除这条支路au，v即可。

(3)若发生有功潮流变向的情况，设某一条变向的支路为au，v，并设原有功潮流从u流向v，则u为支路送端节点，v为支路受端节点，发生变向后，有功潮流从v流向u，则v为支路送端节点，u为支路受端节点。对此情况，在送端节点-送电支路邻接表中，只需从送端节点u的支路链表中去除支路au,v，同时在送端节点v的支路链表中增加支路au，v即可。

3.2 源流路径树的局部修改

在第一轮拓扑分析过程中，在源流路径树上逐层添加送端节点及送电支路时，送端节点-送电支路邻接表同步记录与源流路径树的关联，即送电支路链表中的每一条送电支路被哪些源流路径树共用以及在哪一层被添加到路径树中。因此，当某一支路发生拓扑变化或有功潮流变向后，在局部调整邻接表后，可根据邻接表中该支路的原有关联记录对源流路径树进行局部调整，在每一棵相关源流路径树中逐层修改有关联的送端节点和送电支路，而无需再进行第一轮拓扑分析生成整棵源流路径树。

3.3 源流路径链的改变

在修改相关源流路径树中某一层的树枝和顶点时，这一层上的有向道路集合会有新增或减少的变化。在对本层产生的源流路径链子集进行修改时，依据有向道路的变化，增加或删去对应的源流路径链，得到这一层上新的源流路径链子集。

以上过程说明，只需根据相关源流路径树中的某些层上修改后的有向道路的变化，就能实现全网源流路径链集合的局部改变，反映电网源流供求关系的变化，而无需再进行第二轮拓扑分析。

4 算例分析

以New England 39节点系统为例进行分析，该系统电力网络结构与有功潮流分布见文献[9]。

4.1 电力网络源流路径链分析

根据第2.1节方法建立送端节点-送电支路邻接表，限于篇幅，这里只列出一部分计算过程和结果。表1列出了邻接表中与源32关联的送端节点及其送电支路链表。

表1 与源32关联的部分送端节点-送电支路邻接表

然后，按照第2.2节与第2.3节方法，利用送端节点-送电支路邻接表对电力网络源流路径链进行分析，从而得到全网源流路径树集合与全网源流路径链集合。具体数目如表2所示。图9为由第一轮拓扑分析得到的从源32出发的源流路径树，表3为由第二轮拓扑分析得到的从源32出发的源流路径链集合。

表2 全网拓扑分析结果

图9 从源32出发的源流路径树

表3 从源32出发的源流路径链集合

在本算例中，电力网络源流路径链生成算法首先运用送端节点-送电支路邻接表存储和表示电力网络有向图，能够直接提供第一轮拓扑分析中源32所需的关联送端节点和邻接送电支路。然后，由第一轮拓扑分析以生成源流路径树的形式获得从源32出发的源流路径链集合；接着，第二轮拓扑分析过程在第一轮拓扑分析逐层推进的同时，从第一轮拓扑分析得到的各层有向道路集合中获得新的源流路径链，从而在源流路径树生成的同时，得到了从源32出发的源流路径链集合。结果表明，运用该算法获取源流路径链，具有快速、准确、完备的特点。

4.2 电力网络源流路径链的局部分析

对于所给系统，将支路(12-13)开断，使网络拓扑和潮流分布均发生变化，运用该算法获取变化的源流路径链。限于篇幅，这里仅列出与源32有关的计算过程和结果。首先修改邻接表，表4列出了邻接表在支路开断后的送电支路的修改及其与从源32出发的源流路径树的关联。

表4 修改后的邻接表

然后根据表4对从源32出发的源流路径树进行局部修改，新的源流路径树如图10所示。最后，修改源流路径链，表5列出了增加的源流路径链，表6列出了减少的源流路径链。

图10 修改后的源流路径树

表5 增加的源流路径链

从以上计算过程可以看出，即使是网络拓扑和潮流分布均发生变化，也只需要通过本文提出的局部修改算法，对已得到的送端节点-送电支路邻接表和源流路径树进行较少的调整，就能得到变化的源流路径链。算例结果表明，算法缩小了拓扑分析范围，提高了分析效率，能较好地适应路径链频繁变化的特点。

表6 减少的源流路径链

5 结语

本文针对电力网络源流路径为数众多、交错重叠的特点，建立送端节点-送电支路邻接表存储和表示电力网络有向图，并在此基础上先进行两轮拓扑分析，以获得全网源流路径链集，该方法能够通过局部修改已生成的邻接表和路径树，获取变化后的源流路径链。算例结果表明，本文所提方法对求取在电力系统实际运行下的电能传输路径构成问题具有快速、准确、完备、适应性强的特点，为进一步求解电力网络源流路径相关问题[10～12]奠定了基础。

[1] 汤奕, 于继来, 周苏荃(Tang Yi, Yu Jilai, Zhou Suquan). 电力网络源流路径电气剖分算法(Electrical dissection algorithm of electric power network)[J]. 电力系统自动化(Automation of Electric Power Systems), 2006, 30(22): 28-33.

[2] 于继来, 汤奕(Yu Jilai, Tang Yi). 交流支路和节点的联合电气剖分(United electrical dissection of AC branch and bus)[J]. 中国电机工程学报(Proceedings of the CSEE), 2007, 27(16): 37-42.

[3] 赵金利, 张群华, 余贻鑫, 等(Zhao Jinli, Zhang Qunhua, Yu Yixin,etal). 输电网网架结构的谱聚类分析算法(Spectral clustering approach for structure analysis of transmission networks)[J]. 电力系统及其自动化学报(Proceedings of the CSU-EPSA), 2009, 21(4): 8-11,75.

[4] 车仁飞, 白树忠, 李仁俊(Che Renfei, Bai Shuzhong, Li Renjun). 配电网络拓扑分析与短路电流计算的实现(Implementation of topology analysis and short circuit calculation for distribution systems)[J]. 电力系统及其自动化学报(Proceedings of the CSU-EPSA), 2002, 14(6): 77-84.

[5] 黄健, 张尧, 李绮雯(Huang Jian, Zhang Yao, Li Qiwen). 蚁群算法在配电网重构的应用(Application of ant colony system in distribution reconfiguration)[J]. 电力系统及其自动化学报(Proceedings of the CSU-EPSA), 2007, 19(4): 59-64.

[6] 宋少群, 朱永利, 于红(Song Shaoqun, Zhu Yongli, Yu Hong). 基于图论与人工智能搜索技术的电网拓扑跟踪方法(A power network topology tracking method based on graph theory and artificial intelligence search technique)[J]. 电网技术(Power System Technology), 2005, 29(19): 45-49.

[7] 王朝瑞. 图论[M].3版.北京：北京理工大学出版社, 2001.

[8] 殷剑宏, 吴开亚. 图论及其算法[M]. 合肥：中国科学技术大学出版社, 2003.

[9] 陈彬,于继来(Chen Bin, Yu Jilai).电力网络源流路径链的双向电气剖分算法(Bidirectional electrical dissecting algorithm for power source and power flow path in power network)[J].电力系统自动化(Automation of Electric Power Systems), 2011, 35(18): 41-46.

[10]邵莹, 于继来(Shao Ying, Yu Jilai). 采用源流路径电气剖分信息的电网脆弱性评估(Power grid vulnerability assessment based on electrical dissection of the electric network)[J]. 中国电机工程学报(Proceedings of the CSEE), 2009, 29(31): 34-39.

[11]朱涛, 易善军, 于继来(Zhu Tao, Yi Shanjun, Yu Jilai). 基于电力网络源流路径电气剖分的联络线功率调控方法(Tie-line power regulation method based on electrical dissection for power source and power flow path in power network)[J]. 电网技术(Power System Technology), 2008, 32(11): 24-29,39.

[12]田伟帅, 于继来(Tian Weishuai, Yu Jilai). 基于电气剖分的转运电能损失估算方法(An electrical dissection based approximate method to assess electric energy loss due to power wheeling)[J]. 电网技术(Power System Technology), 2010, 34(3):123-128.

陈 彬(1982-)，男，工学硕士，工程师，研究方向为配电网规划、配电自动化、配电网运行状态在线评估、分布式能源在配电网中的应用等。Email:cb_fz@163.com

于继来(1965-)，男，博士生导师，教授，研究方向为电力系统分析与控制。Email:yupwrs@hit.edu.cn

AlgorithmofPowerNetworkTopologyAnalysisandPathChainsGeneration

CHEN Bin1，2， YU Ji-lai1

(1.Department of Electrical Engineering, Harbin Institute of Technology,Harbin 150001, China;2.Electric Power Research Institute of Fujian Electric Power Company Limited,Fuzhou 350007, China)

For obtaining path chains between sources and flows quickly, a new algorithm, which can analyze power network topology and generate path chains, was proposed in the paper. The algorithm firstly built directed graph and adjacency list between sending buses and sending branches based on the network topology and flow state; and then, it obtained path chain sets from the path chain trees which were generated through two rounds network topology. Getting rid of the adjacency matrix, the proposed algorithm is easier and faster. Moreover, it can change the path chains locally while the topology or the flow state changes in some part of the power network.

electric power network； topology analysis； directed graph； path chain between sources and flows

TM711

A

1003-8930(2012)01-0025-07

2011-10-18；

2011-12-02

国家自然科学基金资助项目(50477008)