东 旭，房鑫炎，赵文恺，孙占功

（1.济南供电公司，山东 济南 250012；2.上海交通大学，上海 200240）

0 引言

随着电网规模日益增大与结构和运行方式日趋复杂，对能量管理系统（EMS）的自动化水平要求越来越高，要求能迅速、准确全面地掌握电力系统实际运行的状况，分析和预测系统运行趋势，对发生的各种问题提出相应对策，并能提供下一步的运行决策［1-3］。状态估计是EMS的主要组成部分，电网规模增大导致需要考虑的因素越来越多，所建立的状态方程数目巨大，传统的集中式状态估计很难满足大规模电网在线安全分析与在线安全自动预警的实时性与准确性要求［4］。

为解决在线安全分析的实时性问题，研究者们将集中式并行计算引入状态估计。文献［5］通过因子表路径树得到BBDF解耦的电网后，在Transputer上实现了并行状态估计。文献［6］提出了一种通过切割支路将网络分块的并行算法。文献［7］提出基于区域分解的并行算法并在PVM计算平台上实现状态估计的并行计算。传统的并行算法往往使用数据集中式存储方法，当电网结构发生改变时，数据收集与更新将占用很长时间，导致计算效率不高，很难达到在线计算实时性的要求。

随着分布式技术在电网中应用，将高效的分布式并行算法引入在线状态估计成为必然趋势。文献［8-12］把大系统分解为若干子系统，将子系统间边界联络线状态量作为约束条件计入目标函数，通过不同函数构造以及迭代方法，实现分布式状态估计的并行计算。文献［13］利用BBDF算法实现电网分块，在各子网边界上加装PMU，根据采集的数据进行独立计算。但上述算法存在如下问题：子网络的互联非常紧密，会给电网解耦计算造成很大通信开销；同时当电网的拓扑结构发生改变（比如区域互联），需要算法做出很大修正，导致无法满足电网在线安全计算要求。

针对上述算法的不足，本文基于嵌套BBDF网络解耦，提出一种新的分布式状态估计算法，按照电网系统的地理区域信息，利用边割集形成的嵌套分块对角加边形式，将电网的分布式状态估计在各个子区域内实现。

1 基于最小二乘法状态估计数学模型

电力系统状态估计的目的是应用经量测得到的物理量通过估计计算来求得能表征系统运行状态的状态变量。电力系统的运行状态可以用节点电压幅值、电压相角、线路有功与无功潮流、节点有功与无功注入等物理量来表示。状态估计中，状态变量与量测变量之间的关系为

通常情况下，状态矢量为电压的幅值与相角，量测矢量为有功潮流、无功潮流、节点注入功率与电压幅值。

由式（2）可以得到状态估计的迭代公式为

对上述迭代方程做如下变换，设

J＝HT（x）R-1H（x），y=HT（x）R-1［z-h（x）］，则式（3）可以简化为

式中：J为n×n阶雅可比矩阵；y为n维列向量。并行状态估计的计算量主要集中在此大规模稀疏线性方程组的求解，而求解此方程组的关键在于首先实现电网解耦。

2 基于嵌套BBDF的电网解耦

实际的电力系统是由节点数目相差不大的各分区按地理状况互联而成，按照电力系统的自然分区，将各个子区域间的关联节点取出，形成一个独立的边界分块，就形成了BBDF的形式，通过对边界块与对角块的分布式处理，就可以实现电网解耦。

由图1可见，空心圆为BBDF图中对角块的点，实心圆为BBDF图中边界块的点。因此利用电网图的边割可以得到BBDF的雅可比矩阵。

雅可比矩阵的对角加边形式是将其相应的BBDF图按照如下两个原则分布形成的：1）对角块随意放在矩阵对角线上；2）边界块放在矩阵的最右下角形成。 对比一般的BBDF矩阵［14-15］和按照边割集形成的BBDF矩阵，其差别在于对角块和边界块的邻接关系，前者强于后者。

图1 电网边割集BBDF分割

图2所示，边割集形成的BBDF矩阵，其某一对角块仅与边界块中的某一对角块有关联，而一般的BBDF矩阵，任意边界块跟整个边界块都有关联。这是因为边界块是各个对角块的边割并集的边导出子图，因此，各个对角块中的顶点仅仅只与各自对应的边割中的边所关联的一个顶点相邻接［16］，将边界块中开始位于同一个区域中的顶点排列在一起，则形成了与对角块相对应的分块对角矩阵，这些位于边界块中的小对角矩阵和对角块一一对应。基于边割集的BBDF划分方法一定程度上减小了边界块之间的数据通信量，但是当对角块内部节点数巨大的时候，对于其内部的数据操作（前代回代），仍然会造成很大的时间开销，因此有必要针对对角块进行类似的处理，进一步减少分布式算法的数据通信量。

图2 BBDF矩阵的对比

本文提出了基于边割集的嵌套BBDF算法，其基本的思想为：首先对电网进行基于边割集的BBDF划分，形成第1层（最外层）BBDF结构（经过稀疏排序技术处理，减少注入元的引入），然后对当前层的每一个对角块进行同样划分，在对角块内部形成同样的BBDF结构，内部的对角块之间的关联信息存放在对角块内部的边界块中。这样根据数学归纳法可以得到，第k层边界块只与k－1和k＋1层边界块相关联，使得同一层的边界块可以异步进行计算，消除同步等待过程。这样就形成了嵌套BBDF的结构，如图3所示。

图3 边割集形成的嵌套BBDF矩阵

该算法的步骤如下：

1）根据自然地理区域对电网进行初始划分，并完成相关顶点着色。

2）按照自外而内的顺序，形成各层BBDF的结构，并更新边界点着色信息。

若该层某顶点与该层其他对角块之间有关联，则对该顶点着该层边界块颜色；若该层某顶点与外层边界块之间有关联，则对该顶点着该层边界块颜色；若不满足以上条件，则对该顶点着该层对角块颜色。

3）若已经达到最内层嵌套数，则退出；否则返回第二步。

4）若电网中存在孤岛（电网为不连通图），则对各孤岛进行类似处理。

经过嵌套BBDF划分，能够保证第k+1层的对角块和第k层的边界块不连通。按照上述步骤对电网进行嵌套BBDF分割，就可以实现电网的分布式解耦。

3 分布式状态估计的并行计算

3.1 基于嵌套BBDF的数据分布式存储

本文设计了一套适用于嵌套BBDF算法的数据存储方式。原电网可根据各层的嵌套边界块实现分布式存储。对于第k层嵌套的每个边界块，将其内部的顶点和内部关联对应的电网数据存入文件Local中；与第k层边界块相关联的第k-1，k+1层嵌套边界块中的顶点及其关联边对应的电网数据，分别放在文件Inner和Outer中。同时为满足状态估计的需要，还要增加一个文件BS，用于存放平衡节点及其关联支路的数据。

图4 数据的分布式存储

由图4可见，在分布式结构中，每一个计算节点处理一个边界块。对于第k层边界块，其父进程处理第k-1层与之关联的边界块，子进程处理第k+1层与之关联的边界块。

这样的数据存储结构对于大电网拓扑信息改变的情况，这种存储方式对于数据的改动非常方便。当电网出现因为故障而导致支路开断，或者新增加一个节点的时候，只需要改变该节点与其相关信息存放的地方的数据信息即可。

3.2 分布式状态估计计算步骤

根据Local，Outer跟BS母线形成的雅可比矩阵

式中：J11为 Local母线形成的雅克比矩阵；J12、J21为Local母线与Outer母线的关联矩阵；Δx1为Local母线电压偏差向量；Δx2为Outer母线电压偏差向量；y1为Local母线功率偏差向量。

从所有子进程接收更新数据，形成更新矩阵ΔJ11和更新向量Δy1，分别更新J11和y1

式（6）经过前代后得

式（7）满足

式中：ΔJ22＝－L21×U12，Δy2＝－L21×Δz1。

对比式（7），ΔJ22为 Bi=0 时的，这意味着 ΔJ22和Δy2中的非零元即为父进程更新矩阵ΔJ11和更新向量Δy1中的数据。

从父进程得到解向量Δx2以后，对式 （7）进行Crout回代求解Δx1

为了能在每次迭代后更新雅可比矩阵，引入向量Δx0记录Inner母线电压偏差。

分布式状态估计计算的流程图如图5所示。迭代参数分别为：最大迭代次数MaxIterationCount、精度Precision、当前迭代次数i和解向量x模的最大值MaxDeviation。

4 算例仿真

利用C++实现图的边割集嵌套BBDF划分和并行状态估计，并行计算采用MPICH2实现。算例采用IEEE300、华东电网2806节点系统进行嵌套BBDF划分后，进行分布式状态估计的并行计算。

经过2层嵌套BBDF划分之后，两个系统各个边界块中包含的节点信息如图6、图7所示。

图6 IEEE300的嵌套BBDF结构

图7 华东电网2806系统的嵌套BBDF结构

图6和图7中，圆形中的数据为形成的嵌套BBDF结构中节点的数目（平衡节点单独存放）。

图8为IEEE300系统嵌套BBDF划分之后经过某次迭代形成的雅可比矩阵。由图中明显可以看到相隔两层嵌套的边界块之间，没有关联矩阵，这与边割集嵌套BBDF划分算法多得到的结论是一致的。

图8 IEEE300系统雅可比矩阵

嵌套BBDF分割算法及其数据存储方式，对于电网拓扑结构发生改变情况的处理，有非常明显的优势。 以华东电网2806系统为例，比如浙区1中，有几条支路改线或发生故障断线，或者新增加了几个电厂，这样的情况下，传统的集中式数据存储方式，需要对整个网络拓扑信息进行修改，必须由发生改变的那一层管理节点上报到上一层的管理系统，进行统一修改然后进行网络的拓扑重新计算。显而易见这样的存储方式根本无法满足大规模电网在线安全分析的超实时性要求。本文提出的数据存储方法，对于这样的情况，如果改动的节点与上一外层边界区没有关联，则只要更新浙区1中的相关拓扑信息即可；如果改动的节点与上一层边界相关联，则更新浙区1信息的同时上报上一层管理系统，然后只需改动与浙区1相关的信息即可，其他区域比如江苏，上海存放的数据信息不需要做任何改动，这样就大幅减小了数据更新所耗费的时间开销，为在线分布式状态估计的实现奠定基础。

为验证本文算法的有效性，用传统的串行状态估计算法与嵌套的BBDF算法进行比较，结果如表1所示。表中：IEEE300系统为算例1，华东2806系统为算例2。

表1 2层嵌套BBDF划分的分布式并行状态估计算性能比较

由表1可以看出，随着系统节点数的增加，并行效率的增长幅度在增大，这是因为分布式文件存储，减少了读取文件与网络拓扑结构的开销，进一步降低了并行状态估计的计算总量。

为验证该算法对于网络拓扑结构改变情况下的有效性，本文将浙江区域中的两条线路开断，如图7所示，一条线路位于浙区1中，该支路连接的两条母线，只与该区域中的节点相连而与其他区域没有关联；另一条线路位于浙区2中，其连接的两条母线均与外界母线有连接关系。本文采用三种算法对该情况进行仿真，分别为集中式串行算法、集中式并行算法、嵌套BBDF分布式并行算法。仿真结果见表2，三种算法分别以A、B、C来表示。

表2 华东2806系统拓扑改变时不同算法性能比较

由表2可以看出，当网络拓扑结构发生改变时候，本文算法在数据修正时间以及数据通信时间上面，都小于传统的集中式算法，并仍然保持了良好的并行效率。

本文还将嵌套BBDF分布式并行算法与集中式串行算法对于IEEE300系统在计算的精度上进行了比较，结果分别如图9和图10所示。

由图9和图10可以看出，基于嵌套BBDF的分布式并行状态估计算法与集中式串行算法相比误差很小，具有相同的估计精度，只是边界块节点的误差较大，但仍在估计精度范围之内。

图9 两种算法的电压幅值之差

图10 两种算法的电压相角之差

5 结语

提出的基于嵌套BBDF分割算法，按照地理区域进行嵌套BBDF解耦，所得到的第k层嵌套边界块仅与第k-1层和k+1层嵌套的边界块相关，大大减少边界块之间关联程度，实现电网的分层嵌套解耦，并使得分布式并行状态估计的计算总量大大降低。另外针对嵌套BBDF算法，本文采用分布式存储方式来对大电网的数据进行存放与更新，该方法不但对一般的电网状态估计有效，而且非常适用于当电网拓扑信息发生改变的情况，这对于电网的在线安全评估是非常有意义的。

［1］ 于尔铿.电力系统状态估计［M］.北京：水利电力出版社，1985.

［2］ 方勇杰，范文涛，陈永红，等.在线预决策的暂态稳定控制系统［J］.电力系统自动化，1999，23（1）：8-11.

［3］ 李碧君，薛禹胜，顾锦汶，等.电力系统状态估计问题的研究现状和展望［J］.电力系统自动化，1998，22（11）：53-60.

［4］ 黄茂民，区域电网的电力需求预测与预警技术研究［D］.华中科技大学，2008.

［5］ Kubokawa J，Sasaki H，Yorino N，et al.A parallel computation of state estimation by Transputer ［C］.International Conference on Advances in Power System Control，Operation and Management，Hongkong，China，1991.

［6］ 韩宇，周奕.基于并行协调算法的电力系统状态估计［J］.江苏电机工程，2007，11（26）：11-13.

［7］ 韩富春，任先成.电力系统状态估计的分布式并行处理［J］.太原理工大学学报，2003，11（34）：664-667.

［8］ Reza Ebrahimian，Ross Baldick.State Estimation Distributed Processing.IEEE Transactions on Power Systems，2000，15（4）.

［9］ Aguado J A，Perez C Molina，Quintana V H.Decentralized Power System State Estimation：A Decomposition-coordination Apporach.IEEE porto Power TechConerence，2001，9（3）.

［10］ George N K.A Partitioned State Estimation for External Network Modeling.IEEE Transactions on Power Systems，2002，17（3）：834-842.

［11］ Antonio J.Conejo，Sebastian de la，Miguel Canas.An Optimization Approach to Multiarea State Estimation.IEEE Transactions on Power Systems，FEB 2007，22（1）：213-221.

［12］ J.Batut，A.Renaud.Daily Generation Scheduling Optimization with Transmission Constraints：A New Class of Algorithms.IEEE Transaction on Power Systems，August 1992，7（3）：982-989.

［13］ Li Yan，Zhou Xiaoxin，Zhou Jingyang.A new algorithm or distributed Power System state estimation based on PMUs［C］.International Conference on Power Systems Technology，Chongqing，china，2006.

［14］ Vlach M.LU decomposition and forward-backward substitution of recursive bordered block diagonal matrices［J］.Electronic Circuits and Systems，1985，132（1）：24-31.

［15］ Zecevic A I，Siljak D D.Parallel solutions of very large sparse Lyapunov equations by balanced BBD decompositions ［J］.IEEE Trans.on Automatic Control，1999，44（3）：612-618.