稀疏矩阵在电网网络拓扑分析中的应用与研究

王惠中，朱宏毅，张荧，何英

（1. 兰州理工大学，甘肃 兰州 730050；2. 永登县供电公司，甘肃 兰州 730050）

电网拓扑分析是根据电网开关状态分析给出电网的拓扑结构，将电网表示成便于电力系统分析计算的模型。网络拓扑分析是电力系统仿真和分析计算的基础，其主要方法有搜索法[1-5]，因果映射法[6]，节点融合法[7-8]，邻接矩阵法[9-11]。通过对上述4种分析方法比较得出：在对电网拓扑分析中，矩阵法几乎能够适用于电力系统的任何接线方式，但该方法计算量太大，分析时间长。因此如何解决该问题是电网拓扑分析中的一个重要问题。目前，在工程应用中一般采用连通矩阵平方法和稀疏矩阵算法。在对电网拓扑分析中，采用连通矩阵平方法计算全连通矩阵可以有效地减少矩阵分析法的计算时间。在矩阵法的基础上采用了稀疏矩阵技术对电网网络进行拓扑分析，利用稀疏矩阵法“排零存储”、“排零运算”的方法[11]，只存储稀疏矩阵和系数矢量中的非零元及必要的检索信息，只取非零元参加运算，这样不仅减少了存储量，还提高计算速度。文献[12]提出的基于稀疏矩阵技术的网络拓扑分析方法使得计算速度明显提高，但是，还可以继续优化。

1 网络拓扑

1.1 电力网的网络拓扑分析

电力网的网络拓扑分析就是在站内拓扑分析的基础上，把站内相互连通节点分组编号，映射成为电网拓扑的结点，然后对电网的结点进行搜索，分析结点间的连通情况，对结点进行全网统一编号，辨识电网分成多少个子系统，把电网的物理模型转化为数学模型。其关键就是要建立各个厂站的结点邻接矩阵和各个电气岛的初始结点树。

1.2 邻接矩阵和连通矩阵

邻接矩阵表示的是节点之间的相邻接关系，即2个节点之间是否直接相连。对于具有n个节点的连通图，其邻接矩阵A是一个n阶方阵，且其行和列都对应于节点，当节点i和节点j相关联时，矩阵元素aij为1；当节点i和节点j不相关联时，aij为0。邻接矩阵表示节点间的一级连通关系。

如果邻接矩阵自乘则得到连通矩阵T，表示节点间一、二级连通关系，称为二级连通矩阵。连通矩阵的元素tij为1 时，表示节点i和节点j直接相连，或通过一个中间节点相连。邻接矩阵再乘以邻接矩阵，得到三级连通矩阵。重复这个过程，对于n个节点最多可得到n-1级连通关系，如果某级连通矩阵描述了节点间所有的连通关系，则称为全连通矩阵。

1.3 矩阵法

邻接矩阵自乘公式如下：

式中，A为邻接矩阵；T为连通矩阵；上标（k）表示该矩阵为k级连通矩阵。邻接矩阵表示节点间一级连接，因此邻接矩阵是一级连通矩阵，即T（k）=A。重复式（1）直到邻接矩阵的n-1次方，可得到全连通矩阵。通过对连通矩阵平方法可以快速得到全连通矩阵，由此得到平方法公式如下:

实际上求全连通矩阵需要的矩阵乘法次数要少于n-2次乘法运算。如果相邻2次求得的连通矩阵相同，即连通矩阵的元素不再发生变化，就已经得到全连通矩阵了。通过矩阵相乘得到的连通矩阵是一个稠密矩阵，并且其稠密的程度随着矩阵相乘的次数增加而增加。式（1）中2个相乘的矩阵之一是稠密矩阵，计算速度很慢。式（2）则需要log2（n-1）次矩阵乘法运算。实际上求全连通矩阵需要的矩阵乘法次数要少于上述次数。如果相邻2次求得的连通矩阵相同，即连通矩阵的元素不再发生变化，就已经得到全连通矩阵了。

2 稀疏矩阵法网络拓扑结构

矩阵法求全连通矩阵时一般不采用稀疏技术，而2个满阵存储的矩阵相乘是很浪费时间的，所以矩阵法的运算时间长，很难满足实时性的要求。为解决这一问题，本文利用了基于稀疏矩阵技术的矩阵法。式（1）2个相乘的矩阵中，连通矩阵是稠密矩阵，而邻接矩阵则是稀疏矩阵，可以对它应用稀疏矩阵技术。

2.1 布尔矩阵存储

邻接矩阵就是布尔矩阵，矩阵中的元素只有“0”和“1”，对非零元素存储时，不需要存储元素的值，只需要记录值为1的元素的行号和列号即可。

对邻接矩阵的存储，可以使用下列2个数组：

1）IA用来记录每个非零元素的列号；

2）JA用来记录每个非零元素的行号。

2.2 连通矩阵的计算

采用式（1）求连通矩阵时，连通矩阵元素的计算如式（3）所示。

连通矩阵为稠密矩阵，用一个n×n二维数组存储，邻接矩阵采用稀疏技术存储。由于邻接矩阵是对称的，其元素amj=ajm，因此式（3）可改写为

2.3 矩阵的对称性

邻接矩阵和连通矩阵都是对称阵，计算连通矩阵时，可以只计算矩阵的上三角元素，根据对称性可以直接写出下三角对称元素，即

2.4 节点优化编号

稀疏技术在实施时有2个关键点，一是排零存储和排零运算，二是节点优化编号。排零存储和排零运算能够有效避免对计算结果没有影响的元素的存储和计算，大大提高程序的计算速度。节点优化编号顺序会直接影响到矩阵A的因子表矩阵的系数度，也对计算效率有直接影响。

本文采用Tinney-2编号方法[12]。这种方法为半动态节点优化编号法或最小度算法。这种方法按最小出线度编号，不同点是在编号过程中及时排除已经被编号的节点发出的边对未编号节点的出线度的影响。选出某个出线度小的节点参与编号，按图上因子分解的办法模拟消去该节点，只进行网络结构变化的处理，而不进行真实的边权计算，这个已编号的节点及其发出的边不再参与后面的模拟消去运算。在剩下的未消去的子图上重复进行上述编号的过程。

2.5 全连通矩阵流程图

形成全连通矩阵的流程图见图1。连通矩阵计算时，仅需要对原连通矩阵中值为0的元素进行计算，值为1的元素无需计算。

2.6 稀疏矩阵的网络分析

本文在网络拓扑结构分析的过程中采用行扫描法分析全联通矩阵。由于可以通过全联通矩阵中一行的元素得知一个联通块中所包含的所有节点，即元素相应位置是1就意味着对应的2个节点向联通，所以只需要联通矩阵中属于同一个联通块的某一行矩阵元素即可判断出联通块的节点组成。

图1 全连通矩阵流程图Fig. 1 Flow chart of the connectivity matrix

图1中，i为矩阵的行；j为矩阵的列。

3 算例分析

本文算例为某一地区的电力系统，系统规模为：厂站156个，母线段752个，开关7 529个，输电线路302条，变压器225台，其中双绕组变压器122台，三绕组变压器103台，串联电抗器支路8条，无功补偿电容204个，无功补偿电抗21个。图2表示网络的部分示意图。

本文采用C语言进行编程来实现算法，开发环境采用的是Visual C++6.0。并且在主频2.13 GHz的PC机上进行的，通过不同的矩阵算法计算都得到了正确的网络拓扑分析结果，只是在需要进行的乘法次数和计算时间上有显著的差别。

图2 网络部分示意图Fig. 2 Schematic diagram of Network part

3.1 矩阵乘法次数比较

本文算法与2种传统算法进行比较，几种算法电气岛分析时矩阵乘法次数表见表1。

表1 电气岛分析时矩阵乘法次数Tab. 1 Electrical island analysis matrix multiplication

由表1可见，邻接矩阵自乘算法的矩阵乘法次数较多，连通平方算法可以明显减少矩阵乘法次数。而优化稀疏矩阵法的矩阵乘法次数也比邻接矩阵自乘法要少，与原稀疏矩阵算法相同，但是多于连通矩阵平方算法。

3.2 几种矩阵法计算时间比较

下面比较上述几种矩阵法在对算例进行拓扑分析时的计算时间，如表2所示。

表2 几种矩阵法所需时间Tab. 2 Time needed for several kinds of matrix method

由表2可知，连通矩阵平方算法比邻接矩阵自乘算法的计算速度明显要快，优化稀疏矩阵比邻接矩阵和连通矩阵平方算法都要快，而优化稀疏矩阵算法比原来稀疏矩阵算法运行的时间短。这是因为电气岛分析消耗了矩阵法的大部分计算时间。电气岛分析时，矩阵阶数很大，乘法运算时间长；而母线分析时在各个电压等级内进行，涉及的矩阵阶数较小。

4 结论

通过表1，表2数据对比，可得出优化稀疏矩阵法的乘法次数比邻接矩阵自乘少，与原稀疏矩阵算法相同；并且优化稀疏矩阵算法比邻接矩阵法，连通矩阵平方法和原来稀疏矩阵算法计算速度快。同时，还利用邻接矩阵的对称性，采用节点优化编号等手段来提高计算速度，效果比较明显，能够有效解决矩阵法的实用性问题。

[1] 徐俊明. 图论及其应用[M]. 合肥：中国科学技术大学出版社，2004.

[2] PHONGSAK D Y. IRAJ D. A topology-based algorithm for tracking network connectivity[J]. IEEE Trans on Power Systems，1995，10（1）：339-346.

[3] 陈星莺，孙恕坚，钱锋. 一种基于追踪技术的快速电力网拓扑分析方法[J].电网技术，2004，28（5）：22-24，34.CHEN Xingying，SUN Shujian，QIAN Feng. A fast power network topology analysis method based on tracking technology[J]. Power System Technology，2004，28（5）：22-24，34（in Chinese）.

[4] 陈竟成，张学松，汪峰，等. 配电网络建模与网络结线分析[J]. 电网技术，1999，23（5）: 52-54.CHEN Jingcheng，ZHANG Xuesong，WANG Feng，et al.Distribution network modeling and network connection analysis[J]. Power System Technology，1999，23（5）: 52-54（in Chinese）.

[5] 罗日成，李卫国. 配电网电气连通性分析的快速算法研究[J]. 电网技术，2004，28（24）: 52-55，84.LUO Richeng，LI Weiguo. Fast algorithm electrical distribution network connectivity analysis[J]. Power System Technology，1999，23（5）: 52-54（in Chinese）.

[6] 高晓萍，阎欣，单渊达. 一种基于因果映射的电力系统拓扑结构识别方法[J]. 电力系统自动化，1997，21（11）:29-30，41.GAO Xiaoping，YAN Xin，SHAN Yuanda. A power system topology identification method based on causal map[J].Electric Power Construction，1997，21（11）: 29-30，41（in Chinese）.

[7] 吴文传，张伯明. 基于图形数据库的网络拓扑及其应用[J]. 电网技术，2002，26（2）: 14-18.WU Wenchuan，ZHANG Boming. Based on the network topology and application of graph database[J]. Power System Technology，2002，26（2）: 14-18（in Chinese）.

[8] 董张卓，秦红霞. 采用面向对象技术和方法的电力系统网络拓扑的快速跟踪（一）[J]. 中国电机工程学报，1998，18（3）: 178-181.DONG Zhangzhuo，QIN Hongxia. Using object-oriented technology and the method of fast tracking of power system network topology（一）[J]. Proceedings of the CSEE，1998，18（3）: 178-181（in Chinese）.

[9] 王湘中，黎晓兰. 基于关联矩阵的电网拓扑辨识[J]. 电网技术，2001，25（2）: 10-12，16.WANG Xiangzhong，LI Xiaolan. Grid topology identification based on incidence matrix[J]. Power System Technology，2001，25（2）: 10-12，16（in Chinese）.

[10] 储俊杰. 变电所一次主接线电气连通性分析的数学模型[J]. 电力系统自动化，2003，27（1）：31-33，48.CHU Junjie. A substation main wiring，the mathematical model of electrical connectivity analysis[J]. Electric Power Construction，2003，27（1）：31-33，48（in Chinese）.

[11] 薛青鸿，吕智嘉，李亚峰. 基于矩阵法的660 MW机组回热系统火用损分析[J]. 热力发电，2011，40（4）：48-52.XUE Qinghong，L譈Zhijia，LI Yafeng. Based on the matrix method of regenerative system of 660 MW unit energy loss is analyzed[J]. Thermal Power Generation，2011，40（4）：48-52（in Chinese）.

[12] 张伯明，陈寿孙，严正著. 高等电力网络分析[M]. 清华大学出版社，2007.

[13] 姚玉斌，叶爽利，吴志良，等. 稀疏矩阵法网络拓扑结构分析[J]. 电力系统保护与控制，2011，39（23）：1-5.YAO Yubing，YE Shuangli，WU Zhiliang，et al. Analysis of network topology by the matrix method with sparse matrix techniques[J]. Power System Protection and Control，2011，39（23）: 1-5（in Chinese）.