大型船舶电力系统快速拓扑分析新方法

张灵杰，孙建波，郭 晨

(1. 大连海事大学 轮机工程学院，辽宁 大连 116026；2. 大连海事大学 信息科学技术学院，辽宁 大连 116026)

大型船舶电力系统快速拓扑分析新方法

张灵杰1，孙建波1，郭 晨2

(1. 大连海事大学 轮机工程学院，辽宁 大连 116026；2. 大连海事大学 信息科学技术学院，辽宁 大连 116026)

为应对现代船舶朝着大型化、自动化发展的同时对船舶电力系统网络拓扑监控能力提出的更高要求，本文提出一种大型船舶电力系统快速拓扑分析的新方法。首先，利用图论拓扑信息数据模式将船舶电网拓扑信息录入系统；其次，遍历初始网络拓扑形成母线，基于独岛搜索策略形成电气岛，完成静态分析并生成拓扑信息数据库；最后，利用节点标记法对受影响的母线进行连通性分析，并结合独岛搜索策略，实现船舶电力系统拓扑结构的动态更新。对某现代化大型集装箱船舶电力系统进行验证分析表明，本文方法结构简便易于实现、满足现代大型船舶电力系统拓扑分析的实时性与有效性需求。

船舶电力系统；拓扑分析；独岛搜索；动态跟踪；图论

0 引 言

船舶电网拓扑分析的主要功能是根据系统中的开关等设备的开合状况，计算出电网的实时状态，为船舶能量管理系统在监控和协调电力系统的运行、及时处理突发事件和异常情况、保障整个电力系统的安全稳定运行等方面提供网络基础数据信息。

船舶电网拓扑分析的实质是电气连通性分析，根据电网中的开关等设备的工作状态，利用建立的拓扑结构模型来描述电网各元件之间的连接关系[1]。传统的连通性分析主要采用邻接矩阵法或树状搜索法。邻接矩阵法通过矩阵自乘运算得到全连通关系矩阵[2, 3]，算法原理简单，但其计算量随着网络规模的扩大而呈指数级增长，且在处理稀疏网络时不够紧凑而占据较大存储空间。树状搜索法主要包括深度优先搜索法（depth first search，DFS）和广度优先搜索法（breath first search，BFS）。在树搜索法的基础上，许多学者尝试采用局部拓扑与全局拓扑相结合、引进启发式规

则搜索、采用面向对象建模技术等方法进行船舶电网拓扑分析[4 – 6]，在不同程度上提高了拓扑更新的实时性，却使算法结构越发复杂，实现起来相当不易。随着现代船舶容量不断地增大，船舶电力系统网络拓扑结构也变得更加复杂，对船舶电网拓扑分析的有效性、实时性以及算法结构的简易性提出了新的挑战。

基于当前研究状况，应对现代船舶对电网拓扑分析实时性的挑战，本文提出一种船舶电网拓扑分析的新方法。建立一种基于图论理论的信息数据模型，将船舶电网结构录入系统。静态分析时，基于船舶电网初始母线分析的结果，利用独岛搜索策略进行电气岛分析，生成电网拓扑基本信息数据库；在动态分析过程中，采用效率更高的节点标记法[8]对受影响的母线重新进行连通性分析，并基于该分析结果作进一步判断，实现电网拓扑信息数据库的动态更新。

1 船舶电力系统拓扑模型

1.1 船舶电网拓扑结构

图1 船舶电力系统结构图Fig.1Shipboard power system network

舰船电力系统拓扑结构包括供电网络和配电网络。与陆地电网不同的是，由于船舶机舱空间紧凑，供电网和配电网之间区分不明显，许多线路兼具双重功能。船舶电网多采用辐射状、干馈线混合的配电方式，大功率或重要负载以馈线方式由发电机母线直接供电，小功率或次要负载以干线方式配电。图1所示

为某现代化大型集装箱船舶采用的典型的辐射状干馈线混合式船舶电网拓扑结构示意图。其中，G1 与 G2发电机组属于同一分段母线，G3 与 G4 发电机组属于同一分段母线，两分段母线之间由联络开关连接成发电母线，经变压器 T 降压后，电网连接到低压配电母线，低压配电区又与应急发电机组 EG 以及岸电连接。

1.2 图论模型

船舶电网是由电源、变压器、母线、开关、刀闸、接地刀闸等设备通过导线连接而成，在结构上具有明显的点线特征，非常适合利用图论方法进行分析。在建立船舶电网拓扑结构的图论模型时：将电源和负载看作电气节点；变压器、开关、刀闸、接地刀闸等二端元件看作连接电气节点的支路。节点之间由支路相连，支路是否连通取决于支路上设备的工作状态。

在图论中，图定义为由抽象的节点和边组成的集合 G = {V，E}，其中 V = {v1，v2，...，vn} 为点集，E = {e1，e2，...，em} 为边集。对于图 G = {V，E}，可用数据表和邻接矩阵2种标准方法来存储其拓扑信息。船舶电网的拓扑结构图属于稀疏图（边的数量 |E| 远小于节点数的平方 |V|2），适合采用形式紧凑的数据表来存储拓扑信息。为节省存储空间，本文采用支路表来记录图 G 的原始拓扑信息，表中每1行代表1条支路，记录该支路的起始节点号、终止节点号等信息，并将支路类型分为：0 开关支路、1 关联支路和2其他类型的支路（电力传输支路等）。如表1所示，支路的起始节点和终止节点按照电网设计时的潮流方向来判别。当船舶电网拓扑结构改变时，只要从数据表中添加或删除相应行数据即可，维护方便。

表1 图的录入数据结构Tab.1Data structure

1.3 节点标记法

传统的树状搜索法属于基于节点类型的算法，即运算或搜索时平均考虑节点间的所有信息，不区分是否直接连接关系，这类算法在最坏情况下要遍历所有节点之间的所有关系，因此效率必然是 0（N2）。文献[7]提出的节点标记法把搜索主要放在了具有直接连接关系的支路上，仅需存储支路两端的节点，通过依次搜索并标记支路两端节点的编号来划分连通域区，搜索次数仅为支路总数，与节点总数无关，避免了许多无用的搜索，提高了效率，其算法流程如图2所示。

图2 节点标记法流程图Fig.2Flow chart of node marking algorithm

该算法的主要思想是：用数组 Ns[N] 记录每个节点连通状态，Ns[N] 的值表示节点属于哪个区域。算法依次扫描支路，不断更新支路两端相连的2个节点的连通状态。扫描完毕后，如果 Ns[N] 中所有值都一样，则网络连通，否则根据 Ns[N] 的值可以判断该节点属于哪个区域。算法所需要存储空间为 max{0（N），0（M）}，在最坏情况下算法的效率为 0（MN），逻辑运算为 0（MN），而且，由于算法中不含有乘法运算，计算速度很快，容易编程实现。文献[8]将该算法与树状搜索法以及矩阵法进行对比分析，结果表明，节点标记法在算法效率上占据绝对优势，能够应对大规模网络连通性分析，本文将在动态拓扑分析中利用该算法对受变动事件影响的母线进行动态拓扑连通性计算。

2 拓扑分析算法

船舶电网拓扑结构分析分为静态分析和动态分析。静态分析是对新入电网或发生大规模支路改造、投退的电网进行的全网遍历生成行为，不考虑船舶电网支路开关的具体连通状态，假设全部支路均闭合，对全网进行遍历分析，生成反映电网结构固有连接关系的拓扑信息集合。动态分析是在电网支路连通情况发生改变时对已经生成的全网拓扑信息的修正行为，大多数情况下，船舶电网拓扑结构的改变都是由支路开关状态的切换造成的，相对于全网而言属于局部变

化，理论上讲只需对连通性发生变化的支路进行拓扑动态追踪即可完成全网拓扑连通信息更新任务。

2.1 静态遍历

采用广度优先搜索法（breath first search，BFS）进行图的初始遍历搜索。BFS 算法是图论中最常用的搜索算法之一，相对于深度优先搜索法（depth first search，DFS），广度优先搜索法对拓扑图中的每个节点进行访问仅一次，而深度优先搜索法因需要回溯，许多节点被重复访问，增加了计算开销。船舶电网多采用辐射状、干馈线混合的配电方式，闭环设计，开环运行，图中环路较少，使得 BFS 的搜索效率明显高于 DFS。

BFS 搜索方法的主要思想为：从起始节点 v1开始，标记为已读；而后以节点 v1的邻接节点为第1层子节点依次进行访问，并标记为已读；接着依次访问每个第1层子节点的下一层节点并标记为已读，依此类推，直到图中所有顶点都被访问为止。

船舶电网拓扑分析主要包括母线分析和电气岛分析。母线分析的任务是将通过闭合开关连接在一起的节点合并为一条母线并为该母线编号，电气岛分析的任务是将通过特定支路连接在一起的母线合并为一个电气岛并给该岛编号。

1）母线分析过程

①利用广度优先搜索策略，从船舶电网中任意母线节点开始，搜索与该节点通过闭合开关所在支路相连接的所有节点，并依次将搜索到的节点和支路的所属母线属性设置为当前母线。当访问到的支路类型为变压器支路时，则返回到上一层搜索其他节点；

②若当前母线所连接的所有节点和支路均已被访问，该母线已形成，则从其他任意未被访问过的母线节点开始另一母线搜索；

③重复以上过程，直到船舶电网中所有节点和支路均被访问过，结束母线搜索任务。

2）电气岛分析过程

船舶电网拓扑分析中，全网的电气岛分析通过重复独岛搜索过程来实现：

①初始化母线所属电气岛标志；

②任选一个未标记电气岛标志的母线，并启动一次独岛搜索；

独岛搜索过程为：给当前所选择的母线赋置新的电气岛标志；查找与当前电气岛相交且投入运行的变压器支路，将当前电气岛标志赋给变压器支路对端节点所在母线，标记已经访问过的变压器支路；重复上一步，直至当前电气岛没有变压器支路或变压器支路均未投入运行，则当前电气岛已形成，本次电气岛分析结束。

③重复上一步，直到船舶电网中所有母线均被访问过，结束电气岛分析任务。

2.2 动态跟踪

船舶电网拓扑分析的最终目标是生成能够反映电网实时运行状态的拓扑信息集合。船舶电网的支路连通状态随时可能因船舶运行工况的不同而改变，因此，船舶电网拓扑分析必须能动态地跟踪网络拓扑变化。

以往船舶电网动态分析常根据开关所在支路类型以及开关的开合情况进行组合式分类分析，尤其是当支路从闭合状态转换到断开状态时，需要从断开支路两端节点分别开始搜索电气连通的节点集，判断2个节点集是否相同，并以此判断结果为依据重新对电网进行拓扑分析和调整。这种类型的动态分析方法缺点也比较明显：一是在算法设计之初需要充分考虑所有支路和开关的不同类型，建模工作量大；二是要对支路类型与开关状态的组合进行穷举分析，增加了复杂度；三是搜索动作开关支路的两端节点的各自连通节点集并判断2个节点集是否相同需要较大的计算开销，降低了动态分析的实时性。

基于以上分析，本文对船舶电网拓扑分析的动态跟踪算法进行改进，当发生开关事件时，首先讨论事件是“闭合”还是“断开”，因为一条支路只能归属一个电气岛，所以在该电气岛内，搜索事件发生支路两端节点之间的连通性，最后根据搜索结果作进一步分析即可完成动态跟踪任务。

1）支路断开

支路断开对电网拓扑结构变化的影响最为复杂，在更新“断开”事件船舶电网拓扑过程中，如果发生在变压器支路或引起母线分割的支路，需要电气岛分析，则只从断开支路的起始与终止节点所属母线开始执行独岛搜索程序。基于该思想，在电气岛分析时，只将搜索限制在受影响的母线范围内，不更改其他电气岛，如此可有效减少计算量，提高算法的实时性。

①检测断开支路是否为变压器支路：如果是，则不必更改母线，对断开支路的起始与终止节点所属母线进行独岛搜索，然后结束程序；如果不是，执行下一步。

②提取断开支路所在母线中所有支路，利用节点标记法搜索该母线的连通性：如果仍然连通，则支路断开后只是在该母线内少了一条环路，不必分离母线，不必更改电气岛，结束本次分析；如果不连通，

则搜索结果已将原母线分割，进一步对分割后的子母线进行独岛搜索。

③根据分析结果更新船舶电网拓扑连通信息，结束本次任务。

2）支路闭合

①检查闭合支路两端节点的电气岛标志是否一致。

②如果电气岛标志一致，意味着只是电气岛中多了一条连接支路，电气岛标志无需改变。进一步判断闭合支路是否为变压器支路：如果是变压器支路，则不必更改闭合支路两端节点所属母线标志；如果不是变压器支路，则进一步判断两端节点所属母线标志是否一致，如果一致则母线标志也无需改变，不一致则合并母线。

③如果电气岛标志不一致，则闭合支路将两个独立的电气岛合并到了一起，合并电气岛，合并母线。

2.3 拓扑分析完整框架

在完成电网拓扑的静态遍历和动态跟踪算法设计之后，即可建立船舶电网拓扑分析的完整流程：首先输入船舶电网拓扑结构的节点支路信息，读取一次支路工作状态，之后启动静态分析算法生成船舶电网拓扑的连通信息数据库，在此基础上，通过获取支路状态变化信息来启动拓扑动态跟踪算法，从而实时更新船舶电网拓扑连通信息数据库，实现船舶电网拓扑分析任务。完整的分析流程如图3所示。

图3 船舶电网拓扑分析完整流程Fig.3The full flow chart of shipboard power system topology analysis

3 算例分析

以图1所示船舶电力系统为例，对本文所提船舶电网拓扑分析方法进行验证和讨论。将图1中船舶电力系统抽象成由点集和边集连接成的拓扑模型，并对点和边进行编号，得到等效拓扑结构如图4所示，共包括6个电源（4 台主发电机、1 台应急发电机以及 1个岸电接口）、77 个节点、79 条支路（63 条开关支路、14 条变压器支路以及2个电力输送支路）、29 个负载（24 个普通负载和5台大功率电动机负载）。

船舶电网的初始网络状态为：主发电机 G1，G2，G3 和 G4 投入运行，其余电源退出运行；开关支路b5，b7，b20 断开，其余开关支路全部闭合；变压器支路全部投入运行。利用本文方法对船舶电网拓扑分析过程表述如下：

1）静态分析

按照表1数据格式录入船舶电网拓扑结构，然后进行船舶电网拓扑结构的静态分析，利用广度优先搜索算法遍历全网划分母线，并对母线进行电气岛分析，母线和电气岛分析结果分别如表2和 表3所示。

①事件 1：在初始网络状态的基础上，假设变压器 T1 退出运行。

变压器 T1 退出运行，属支路“断开”事件。经判断，支路 T1 为变压器支路；不必分离母线，对支路T1 的起始节点 n1 所属母线1以及终止节点 n45 所属母线2进行独岛搜索，搜索结果为母线1和母线2仍然在同一电气岛内，关联支路 T1 从电气岛1内剔除，其他电气岛不变；更新拓扑信息。

②事件 2：在初始网络状态的基础上，假设支路b37 退出运行。

支路 b37 是开关支路，该事件类型为“断开”。支路 b37 不属于变压器支路；支路 b37 属于母线 1，利用节点标记法对母线1内所有支路进行连通性分析，经计算，断开后支路 b37 的起始节点 n76 与终止节点n11 在原母线1内不再连通，母线1被分割成两条子母线，将支路 b37 的终止节点 n11 所属子母线重新编号为母线 16，起始节点 n76 所属子母线仍保留为母线1，对母线 1、母线 16 进行独岛搜索；电气岛分析结果为原电气岛1中独立出一个新电气岛 4，包含母线6，7，8，9，16，成员关联支路 T3，T4，T5 以及T6，其余网络不变；更新拓扑信息。

③事件 3：在事件1的基础上，支路 b20 投入运行。

支路 b20 为开关支路，该事件为“闭合”。检查支路 b20 两端节点电气岛标志；两端节点电气岛标志一

致，均为电气岛 1，表示支路 b20 的闭合使得原电气岛内多了一条连通支路，电气岛标志无需改变；进一步，由于该支路不属于关联支路，且支路两端节点所属母线分别为母线2和母线 3，则将母线3合并到母线2集合内，将支路 b20 也并入新的母线2内，将母线3 以后的母线编号各自减一重新编号；更新拓扑信息。

图4 船舶电网拓扑结构示意图Fig.4The topological diagram of shipboard power system

表2 母线分析结果Tab.2The bus analysis result

表3 电气岛分析结果Tab.3The island analysis result

通过3例事件的处理结果可证明本文所提方法在船舶电网拓扑分析中的有效性。尤其是在处理动态跟踪问题时，由于采用了效率较高的节点标记法，不仅使本文拓扑分析方法的实时性得到保障，更使算法结构得到简化而易于实现。

4 结 语

本文针对船舶电网拓扑分析问题提出一种新方法。新定义了基于图论模型的信息存储格式，将船舶电网拓扑录入系统；在静态分析中，利用广度优先搜索（BFS）对船舶电网进行初始母线分析，在此基础上利用独岛搜索策略进行电气岛分析；在动态分析过程中，利用节点标记法对受影响的母线重新进行连通性分析，并基于该分析结果作进一步判断，从而实现船舶电网的动态跟踪任务。最后以某现代化大型集装箱船舶电网为例进行了验证计算，结果表明，本文所提方法结构简便易于实现，满足现代大型船舶电力系统拓扑分析的实时性与有效性需求。

[1]姚玉斌, 王丹, 吴志良, 等. 方程求解法网络拓扑分析[J]. 电力自动化设备, 2010, 30(1): 79–83. YAO Yu-bin, WANG Dan, WU Zhi-liang, et al. Network topology analysis by solving equations[J]. Electric Power Automation Equipment, 2010, 30(1): 79–83.

[2]马静, 张俣妤, 马伟, 等. 基于关联矩阵标记法与回路矩阵的电网拓扑分析[J]. 电力系统自动化, 2014, 38(12): 74–80. MA Jing, ZHANG Yu-yu, MA Wei, et al. Power network topological analysis based on incidence matrix notation method and loop matrix[J]. Automation of Electric Power Systems, 2014, 38(12): 74–80.

[3]王增平, 张晋芳, 张亚刚. 基于开关路径函数集的新型厂站内网络拓扑方法[J]. 中国电机工程学报, 2013, 33(1): 137–145. WANG Zeng-ping, ZHANG Jin-fang, ZHANG Ya-gang. A novel substation configuration identification algorithm based on the set of breaker-path functions[J]. Proceedings of the CSEE, 2013, 33(1): 137–145.

[4]梅念, 石东源, 段献忠. 基于图论的电网拓扑快速形成与局部修正新方法[J]. 电网技术, 2008, 32(13): 35–39. MEI Nian, SHI Dong-yuan, DUAN Xian-zhong. A novel method for fast power network topology formation and partial revision based on graph theory[J]. Power System Technology, 2008, 32(13): 35–39.

[5]黄靖, 张晓锋, 蒋心怡. 一种启发式舰船电力网络拓扑分析方法[J]. 电力系统及其自动化学报, 2008, 20(2): 110–116. HUANG Jing, ZHANG Xiao-feng, JIANG Xin-yi. Heuristic topology processor for the shipboard power system network[J]. Proceedings of the CSU-EPSA, 2008, 20(2): 110–116.

[6]吕昊, 王吉忠. 基于面向对象技术的舰船综合电力系统电力网络故障模拟及拓扑跟踪[J]. 船电技术, 2010, 30(4): 28–33. LV Hao, WANG Ji-zhong. Malfunction simulation and topology tracking for shipboard integrated power system network based on object-oriented technology[J]. Marine Electric & Electronic Engineering, 2010, 30(4): 28–33.

[7]黄家栋, 罗伟强, 赵永强, 等. 两种新的电网连通性分析快速算法[J]. 电力系统保护与控制, 2008, 36(17): 16–18, 50. HUANG Jia-dong, LUO Wei-qiang, ZHAO Yong-qiang, et al. Two new high-speed algorithms for electrical network connectivity analysis[J]. Power System Protection and Control, 2008, 36(17): 16–18, 50.

[8]黄正, 陈凡, 张雪娇, 等. 电网拓扑分析算法的研究[J]. 南京工程学院学报(自然科学版), 2013, 11(2): 43–49. HUANG Zheng, CHEN Fan, ZHANG Xue-jiao, et al. Study on power network topology analytic algorithm[J]. Journal of Nanjing Institute of Technology (Natural Science Edition), 2013, 11(2): 43–49.

[9]WU Y J, TANG Y, HAN B, et al. A topology analysis and genetic algorithm combined approach for power network intentional islanding[J]. International Journal of Electrical Power & Energy Systems, 2015, 71: 174–183.

[10]FARROKHABADI M, VANFRETTI L. An efficient automated topology processor for state estimation of power transmission networks[J]. Electric Power Systems Research, 2014, 106: 188–202.

[11]甄洪斌, 张晓峰, 戚连锁, 等. 基于拓扑识别的舰船电力系统自适应保护策略[J]. 舰船科学技术, 2011, 33(3): 53–56. ZHEN Hong-bin, ZHANG Xiao-feng, QI Lian-suo, et al. An adaptive protection scheme based on topology-recognition for shipboard electrical power systems[J]. Ship Science and Technology, 2011, 33(3): 53–56.

A fast topology analysis method for large shipboard power system network

ZHANG Ling-jie1, SUN Jian-bo1, GUO Chen2
(1. Marine Engineering College, Dalian Maritime University, Dalian 116026, China; 2. Information Science and Technology College, Dalian Maritime University, Dalian 116026, China)

In response to the increasing demand on the shipboard power system topological monitoring ability with the rapid development of modern ship toward large-scale and automation, this paper presents a novel fast topology analysis method for large shipboard power system. Firstly, input the shipboard power system topological information using the graph theory based data model; Secondly, traverse the initial network and generate the node bus and island to achieve the static global topology analysis, then generate the topological information database; Finally, after analyzing the connectivity of the affected node bus with the node marking algorithm, the dynamic tracking program is completed combining with the proposed isolated island search strategy. Verification and analysis is conducted on a modern large shipboard power system, the results indicate that the proposed fast topology analysis method fulfills the demands of modern large shipboard power system on real-time capability and effectiveness with relatively simple structure.

shipboard power system；topology analysis；isolated island search；dynamic tracking；graph theory

TM711

A

1672 – 7619(2016)11 – 0095 – 07

10.3404/j.issn.1672 – 7619.2016.11.020

2016 – 03 – 28；

2016 – 07 – 05

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

张灵杰(1989 – )，男，博士研究生，研究方向为船舶电力系统自动化及机电一体化。