基于最短路径算法的继电保护数据模型结构及搜索优化

王文焕，郭鹏，詹荣荣，杨国生，李妍霏，李俊恒

(电网安全与节能国家重点实验室(中国电力科学研究院有限公司)，北京 100192)

0 引 言

继电保护专业管理包括保护装置状态评价、动作分析，涵盖消缺、检修、反措、技改、巡检巡视的全寿命周期管理，分布在继电保护统计分析及运行管理、继电保护状态评价及状态检修、继电保护及故障信息系统、故障录波联网系统、在线监视与智能诊断系统、变电站配置描述(substation configuration description，SCD)文件管控系统等多个继电保护专业软件系统中。继电保护专业信息获取手段日趋丰富，信息完整性不断提升，然而，不同信息系统相对独立、数据交互受限，难以为继电保护专业管理提供全局应用支撑。以交直流混联大电网运行对继电保护的更高要求为目标，并伴随着大数据与人工智能技术的快速发展，继电保护专业管理正在经历不同继电保护专业系统数据融合、深化继电保护全局应用的专业发展过程。目前继电保护数据模型是以数据对象间的基本关联关系为依据，通过业务过程将数据对象间关联关系组织起来的。但是，各种类型继电保护装置众多，不同类别、不同特性保护装置包含的数据对象丰富，不同数据对象的特性、数据量、访问流量有相当差异，例如台账数据约150万条，告警数据约2亿条，缺陷数据约100万条，数据对象间的关联特性不同，包括一对一、一对多、多对一、多对多关系等，数据模型结构合理性对继电保护业务应用访问数据的效率产生直接的影响，有必要考虑不同数据对象特性、数据量、访问流量的差异性，以及不同数据对象间的关联关系，对继电保护专业模型结构和数据访问路径进行优化，提升专业应用对海量异构数据的访问效率。

继电保护数据结构主要包括结构化数据、半结构化数据和非结构化数据，业务应用端通常采用结构化数据建模，相比其他2种数据模型结构，在数据检索效率上具备明显优势。但随着继电保护专业数据体量的增加，继电保护专业软件系统普遍面临数据查询效率下降的问题，数据模型结构优化程度不足是其中的主要原因。在继电保护数据模型结构优化方面，文献[1]研究了基于IEC 61850的智能电子设备(intelligent electronic device，IED)数据结构优化设计方法，文献[2]提出了基于统一建模语言(unified modeling language，UML)和可扩展标记语言(extensible markup language，XML)的数据结构模型优化方法，文献[3]提出了适用于非结构化数据(如录波、定值单等)及半结构化数据(如SCD、SPCD等XML格式数据)的数据模型结构优化方法，文献[4]提出了基于Petri网的UML形式化结构建模方法。上述研究对继电保护数据模型结构优化方面起到一定作用，但仍缺少数据模型结构优化程度指标、主站端结构化数据的模型结构优化方法的研究。

考虑继电保护数据对象间相互关联，将数据对象抽象为网络节点，数据对象间关联关系抽象为网络通路，继电保护数据模型可以使用网络形式予以表征。通过该模型网络访问继电保护数据的便利程度可应用复杂网络理论[5]进行分析。复杂网络理论作为一种网络分析方法，在电力系统连锁故障预测领域取得一定的应用[6]。虽然复杂网络方法无论是在理论和实际应用中都存在很多问题需要解决[7]，但它提供了通过网络的宏观参数来研究网络结构特性的视角，对于继电保护数据模型网络性能的评估具备一定的指导意义。

继电保护数据模型搜索优化可以转化成搜索复杂网络的最优路径。最短路径算法是图论中具有网络特色和突出效果的理论分支，兼具悠久的研究历史和现代应用价值，典型的最短路径算法包括Dijkstra算法[8]、弗洛伊德(Floyd)算法[9]、Bellman-Ford算法[10]、单源最短路(shortest path faster algorithm，SPFA)算法[11]等。最短路径算法在大数据技术查询算法中也有应用，文献[12]提出了适用于Hadoop平台的最短路径算法图搜索算法，包括对分布式文件系统(hadoop distributed file system，HDFS)中大规模图的分割，以及基于MapReduce的子图内查询和子图间查询，提高了大规模图最短路径查询的效率。文献[13]基于双向最短路径算法对单词和文本的相似性进行评估，建立知识库中颗粒度比词条更密的节点之间的超链接关系，实现单次和文本语义的相似性评估。

本文以提高继电保护一体化数据模型的数据访问效率为目标，分析继电保护专业管理对一体化数据建模的需求，提出继电保护数据模型结构优化指标及优化方法；考虑业务应用对数据对象访问顺序，依据数据对象间的关联关系建立有向图，将数据表映射为节点，将数据访问顺序映射为路径，将数据表的查询耗时映射为路径长度，通过最短路径算法对数据模型结构和访问顺序进行优化，提升专业应用对海量异构数据的访问效率。

1 继电保护专业数据与数据模型

继电保护的不同业务应用均是继电保护专业管理的组成部分，不同业务应用的协同关联是实现继电保护专业管理的基本途径，继电保护专业数据发挥了不同业务应用间关联纽带的作用。图1绘制了继电保护基本业务的逻辑关系图，以及继电保护专业数据在业务应用间的流转情况。

图1所示的继电保护专业数据中，直接上报或人工现场采集录入的信息为基础信息，包括1～10，以及20巡检巡视结果中人工现场录入部分。

图1 继电保护业务应用数据流简图

图1中基础信息外的其他信息是继电保护专业应用对基础信息进行处理和分析后，生成的分析结果，可以提供给其他专业应用或者用于信息展示。基础信息的含义及数据量如表1所示。

表1 继电保护基础信息概览表

继电保护专业数据是支撑继电保护业务实施的“血液”，而继电保护数据模型是继电保护业务应用访问、处理专业数据的媒介。继电保护数据模型一方面将取自不同数据源、分散独立的专业数据组织起来，另一方面为支撑专业应用开展融合了基础信息、中间变量和分析结论等类别信息。继电保护数据模型具体涵盖了：

1)物理实体的描述信息、配置信息，例如：继电保护装置等二次装置，断路器等一次设备，业务应用系统服务器、工控机、通讯装置等实体设备的属性描述信息；

2)信息对象的配置信息，包括继电保护装置等实体装置涵盖的信息对象的配置信息，例如，告警、动作、定值等信息节点的配置信息，工作电压、光口强度等的配置信息等；

3)物理实体或信息对象间的关联关系，例如，二次设备与一次设备的关联关系，物理光纤与两端的插件、端口的关联关系，保护功能状态与保护功能闭锁的关联关系等；

4)支撑业务应用的中间变量及变量关联配置信息，例如，状态评价算法的配置，算法的抽象变量，从历史数据中提炼的对照标度，对抽象变量以及对照标度进行数学计算所得结果，算法的控制参数如迭代次数、收敛判据等；

5)大量的实体信息，即图1中除一次设备信息、保护台账等物理实体配置信息外的保护设备功能配置及定值、运行状况、运维记录以及业务应用分析结论等实体信息。

2 继电保护数据查询效率的影响因素

继电保护数据查询效率取决于继电保护数据模型结构、级联数据表访问次序，以及数据库层面的措施。这3个因素中，前两个是从是否满足继电保护业务应用需求的角度确定的，第3个因素是从实现层面提出的，例如文献[14]指出的索引、分区、结构化查询语言(structured query language，SQL)语句优化等。本节主要考虑前2个因素。

2.1 继电保护数据模型结构

2.1.1 继电保护数据模型网络

继电保护数据模型是将反映不同业务过程的数据表进行逻辑关联和属性组合的有机体系，将数据表抽象成节点，将数据表间的引用、级联等关联关系抽象成连线，继电保护数据模型实质上构成了数据模型网络。数据模型中任意一个数据对象属性信息的变化或与其他数据对象关联方式的变化均会改变数据模型网络的结构。查询数据时，通常需要从给定条件所在的源数据表出发，进行一步搜索，得到满足给定条件的数据及属性信息；通过数据模型网络的连线确定一张中间数据表，进行一步搜索，得到符合刚搜索到的属性信息的数据，并获取新的属性信息，再通过数据模型网络的连线确定下一张数据表，搜索新的数据和属性信息，直至目标数据表，依据上一张数据表的数据和属性信息搜索到目标数据。数据搜索共涉及到包含源数据表、中间数据表、目标数据表在内的级联数据表。例如，在统计不同型号保护装置告警信息的业务中，需要查询某条告警数据对应的保护装置型号。数据搜索过程如图2所示。以某告警数据为起点，通过该告警数据的告警配置Id属性信息，在保护告警配置表搜索到符合该告警配置Id的数据以及数据集Id属性信息，再在数据集表中搜索到符合该数据集Id的数据以及IED Id属性信息，以此类推，最后，在保护装置型号表中搜索符合保护装置表搜索到的数据及装置型号Id属性信息的保护装置型号目标数据。

图2 数据搜索示例

数据模型网络是以数据表关系为基础，以继电保护信息对象转化成的数据表为单元，构成的网络化的抽象结构。继电保护数据模型网络可抽象为一张有向图，根据数据表的关联特性能够确定有向图中连线的方向，主要包括如下4种情形：

1)外键关联。数据表通过外键引用其他数据表主键，查询方向为从引用数据表指向被引用数据表，例如图2中保护装置表通过外键引用保护装置型号表的主键—装置型号Id，数据查询方向如图中标识所示；

2)唯一性字段关联。数据表间通过唯一不重复的属性字段建立关联，查询方向通常为双向。例如图2中保护装置表与IED装置表可通过具备唯一性的设备识别代码属性字段建立关联，既可以从保护装置表查询到IED装置表，也可以从IED装置表查询到保护装置表，图中仅示出了其中一个方向；

3)辅助表关联。针对需要引用被引用数据表多条数据的应用场景，建立一张辅助表，通过外键分别指向两张原始数据表。辅助表能够灵活地表达原始表间多对一、多对多关系。由于辅助表仅用于配置原始数据表的关联关系，在有向图中可简化为一条由原始引用表指向原始被引用表的连线。例如，母线保护装置与线路、变压器等多个一次设备有关，通过保护装置与一次设备关系辅助表，能够灵活地将母线保护装置指向数量不确定的一次设备；

4)映射关联。是应用经模糊匹配或总结人工经验生成的匹配算法，或人工匹配的方式，对数据表中数据的属性信息进行自动匹配分析，建立起的与其他数据表的关联关系。这是一种间接的关联方式，起因是2个数据表间客观存在的关联不易获取，但通常是分析应用所需掌握的。映射关联的方向常为外键关联的逆向。例如，依据继电保护装置告警信息，来判断装置告警位置，需要依据告警信息的语义，以及保护装置表中保护装置Id，从板卡、回路数据表中搜索满足保护装置Id并且符合该告警信息语义的板卡数据或回路数据。为了后续应用的方便，在获取到2个数据表中数据的关联关系后，常建立一张映射表。

2.1.2 反映数据模型结构优化程度的指标

一个优异的、便于用户查询数据的数据模型结构必然具备这样一些特征，例如，数据表关联关系被充分挖掘，数据模型网络连接丰富，用户搜索数据所需访问的数据表的数目减少；关键节点常用于连接不同类别应用的数据表，数据模型中心节点或关键节点轻量化，搜索不同业务数据期间访问枢纽数据表的耗时少，提升查询的效率。这些特征可以应用复杂网络理论[15]中的若干指标体现。

1)平均路长L。定义网络中2个节点之间的距离dij为由一个节点(起始数据表)查询到另一个节点(目标数据表)的最短路径对应的距离，而2个相连节点(数据表)的距离为根据被引用数据表所含数据量折算成的查询时间。在一个网络中，平均路长L是指所有节点对之间距离的平均值，即

(1)

如果数据模型网络丰富，通常能够减少节点间最短路径包含的连线数，减小dij及L；优选关键节点能够减少跨业务应用数据查询访问到该关键数据表所耗费的时间，并且最短路径涵盖关键节点的数据查询项目数多，减小dij及L。

2)集群系数C。集群系数是一个衡量网络节点集聚程度的概念。对网络中的某一个节点i设有ki个节点和其相连，则ki个节点之间最多有ki(ki-1)/2条边，设ki个节点之间现存ti条边，则定义Ci为

(2)

然后对所有的Ci取平均值就可得到聚类系数C。

如果数学模型网络丰富，网络节点集聚程度高，Ci及C增加。

如果数据模型网络丰富，节点间的连线数目增多，平均度数增加；关键节点通常有较大的度数，优选关键节点后，访问枢纽数据表的耗时减少，高度数节点的权重增加，平均度数增加。

2.2 级联数据表访问次序

在一套继电保护数据模型网络中，随着模型网络结构的丰富，由给定信息所处的数据表出发，通过不同的访问路径，查询到目标数据所需的查询时间不同。文献[16]拟合出典型的数据存储架构下，查询一张数据表的平均事务响应时间为

(3)

式中：C1是查询应用部署的服务器数目；k1是路由系数，在集群环境下为常数，典型值为65；R1是单次查询的路由寻址次数。例如在Hadoop Database(HBase)架构[17]下，R1取2(HBase0.94以下版本)或3(HBase0.96以上版本)[18]；k2是数据查询系数，与查询数据表所含数据量正相关，典型值为600；λ1表示查询应用的优化度，若完全执行文献[16]所述的数据库查询底层优化措施数据库查询底层优化措施，λ1可取0.1。

由式(3)可知，查询单张数据表所耗费的时间主要取决于数据表所含数据量。通过一个数据模型网络选取一条数据查询路径，包括初始查询条件所在的源数据表、目标数据表以及中间数据表，对应的数据查询效率既取决于该路径途经数据表的数目，又取决于该路径上每张数据表的数据量。另外，上文数据表关联的4种形式中，通过外键关联、唯一性字段关联两种方式查询数据仅需访问被引用数据表一张表，通过辅助表关联、映射关联两种方式查询数据需要访问辅助表(或映射表)和原始被引用表两张表。

3 继电保护数据模型结构及搜索优化

3.1 继电保护数据模型结构优化

3.1.1 数据模型结构分层优化

3.1.2 增加数据表间的引用关联

对于满足上述条件的两张数据表，有两种增加数据关联的情形：

1)直接增补。目前数据模型网络架构不存在u1至v1的路径P1(u1,v1)，即Ω(u1,v1)=φ，则建立u1至v1关联，关联形式可能是外键关联、唯一性字段关联、辅助表关联和映射关联；

2)递推增补。目前数据模型网络架构已至少存在一条u1至v1路径P2(u1,v1)，即Ω(u1,v1)≠φ，则u1中任一条数据均能通过数据查询的方式与v1中的数据建立关联，根据路径P2(u1,v1)上表关联的具体形式，u1至v1的关联可能是外键关联、唯一性字段关联、辅助表关联和映射关联。

s.t.g[R(u,v)·Ω0(u,v)]≠0。

式中：k1、k2、k3为权重系数，若数据模型节点u与v间建立直接的关联引用关系，则R(u,v)=1，否则，R(u,v)=0；Ω0(u,v)指在模型增补后，u至v是否存在搜索路径，若存在Ω0(u,v)=1，否则Ω0(u,v)=0；g(a)为自定义函数，指向量a各元素的累乘。约束条件的物理意义是指经直接增补或递推增补后，不存在任一孤立的数据模型节点。

3.2 继电保护数据模型搜索优化

如图2所示，数据查询是按照一定次序依次执行数据表查询，从已知的条件信息逐步获得所期望结果的过程，包括源数据表查询、中间数据表查询和目标数据表查询。采用不同的查询步骤其效率可能会差别很大。所以，继电保护数据搜索优化可转化为一个最短路径问题。

现将数据搜索优化问题转化为图论中的最短路径问题。以数据模型网络为基础，构建有向图G，将数据模型网络的数据对象N’映射为G的节点N，数据表间的引用关联R映射为G的边E。对于边e=(p,q)∈E，若可从p查询到q，边e的距离ω(e)为由p查询数据表q所耗费的时间，如式(3)所示；对于边e1=(q,p)∈E，若不可从q查询到p，边e1的距离ω(e1)为一个大数M。

设Ω(u,v)是G中以u,v为端点的路径集合，W(P(u,v))表示路径P(u,v)上边距离之和，继电保护数据模型优化问题可表示为在图G中求Ω(u,v)中的一条路径P0(u,v)，使得

(4)

典型的最短路径算法包括Dijkstra算法、Floyd算法、Bellman-Ford算法、SPFA算法等，不同算法的比较如表2所示。表中，ξ、ε分别表示图的顶数与边数。

表2 不同最短路径算法的比较

级联数据表访问次序优化属于单源最短路径算法，不存在边的权重为负的特殊情况，并且，为满足继电保护业务应用的需要，继电保护数据模型网络的边数ε并非远小于ξ2，表2的4种算法中，Dijkstra算法是满足级联数据表访问次序优化需求且具有最小时间复杂度的算法，所以本文选择Dijkstra算法进行级联数据表访问次序优化。

Dijkstra算法[19]在电力系统领域已应用于最优解列断面搜索[20]、配电网孤岛划分[21]、黑启动策略优化[22]、电网故障定位[23]等方面。其基本步骤是：

1)u、v不相邻时，取ω(u,v)=∞；

2)令w(u0)=0；w(v)=∞，v≠u0；S0={u0}，i=0；

3)对每个vSi，用min{w(v),w(ui)+ω(ui,v)}替代w(v)；设ui+1是使w(v)取最小值的V(G)-Si中的顶，令Si+1=Si∪{ui+1}；

4)若i=ξ-1，停止；若i<ξ-1，用i+1替代i，转3)。

应用Dijkstra算法，在Θ(v,ε)=Ο(ξ2)步数内，可计算出u到v的最短路径P0(u,v)以及对应的检索时间duv，从而实现继电保护数据模型搜索优化。

4 案例分析

4.1 数据模型结构优化

为满足继电保护不同业务应用的需求，采用本文第3章的方法，建立图1中继电保护专业数据的数据模型，继电保护数据模型结构的局部如图3所示。图中列出了数据表的主键英文名、目前数据量及若干关键属性字段。

建立图3所示的继电保护数据模型时，考虑到不同实体间的层次关系，即

保护型号是一批保护装置共有的概念，以保护型号数据表为枢纽，能够将应用于同型号保护装置综合分析的相关数据表(图3中未示出)关联起来，满足保护装置群体性分析应用的需要。保护装置是具备独立功能的物理实体，以保护装置数据表为枢纽，能够将应用于保护装置全寿命周期管理类应用的相关数据表(例如图3中的缺陷管理及检修检验管理数据表)关联起来，满足保护装置个体分析、评价及管理应用的需要。保护装置部件是保护装置的细分，如图3中板卡所示，以保护装置部件数据表为枢纽，能够将细化到保护装置部件的分析应用相关数据表(图3中未示出)关联起来，使得对保护装置的分析、管理细化到装置部件。保护事件、告警、遥信、模拟量、定值、定值区、软压板等配置信息是保护装置的最小信息对象[24～26]，以配置信息数据表为枢纽，将保护装置在线信息(例如描述告警配置数据表中告警点发生时间、数据值等的告警信息)与配置信息有机组织起来，为建立与IEC 61850等模型的接口，以及在线信息的深化应用奠定良好条件(本节算例仅举告警信息一例)。可见，通过将数据模型对象按照其所描述实体的层次关系分层布局，实现了关键节点数据量的轻量化，提升继电保护专业数据的访问效率。

图3 继电保护数据模型架构示意图

增加数据表间的引用关联能够优化继电保护数据模型结构，以数据检索路径“告警信息→告警配置→数据集→IED装置→保护装置→板卡信息”为例，应用3.1.2节的方法构造计算模型，以增加模型间的引用关联与否R(u,v)作为变量，取k1=0.5，k2=0.3，k3=0.2。该检索路径上已有的关联关系如表3中“■”所示，可增加的引用关联如“□”所示。其中，“保护装置→板卡信息”可依据装置告警或异常现象，建立映射关联。模型中的变量R(u,v)的含义如表4所示。

在国产达梦数据库中搭建了仿真计算环境，按照图3数据模型引用关系及数据体量在数据库中生成了测试数据。由于本算例规模小，采用枚举法计算，得到优化的数据模型增补结果，如表3及表4的最后一列所示。

表3 实例中关联增补相关的数据模型列表

表4 模型增补变量详情

表5 模型关联增补后数据表的查询耗时

可见，上述路径仅具备增加“告警配置→IED装置”以及“告警配置→板卡信息”关联的必要，增加其他关联并不利于提高数据检索效率。为了说明本方法的有效性，以“告警配置”到“板卡信息”的关联为例。通过“告警配置→数据集→IED装置→保护装置→板卡信息”的递推序列，能够建立“告警配置”数据表中功能位置(POS_FUNCTION)属性项与“板卡信息”数据表中主键DEVBOARD_ID的关联，减少了数据查询遍历的数据表的数目，也便于实际应用中直接根据告警配置信息确定隐患板卡。增补结果如图3中虚线所示。

4.2 数据模型搜索优化

图3中由单装置软件版本检索保护型号数据时，存在两条路径：“单装置软件版本→同型号保护软件版本→保护型号”和“单装置软件版本→保护装置→保护型号”两条路径。由单装置软件版本查询同型号软件版本、保护装置的耗时分别为0.032、0.031 s，由同型号软件版本查询保护型号的耗时为0.009 s，由保护装置查询保护型号的耗时为0.262 s，第一条路径总耗时0.031 s，第二条路径总耗时0.038 s，应用Dijkstra算法可得最优路径为“单装置软件版本→同型号软件版本→保护型号”。

由告警信息检索板卡信息数据时，存在3条路径“告警信息→告警配置→数据集→IED装置→保护装置→板卡信息”(路径a)、“告警信息→告警配置→IED装置→保护装置→板卡信息”(路径b)和“告警信息→告警配置→板卡信息”(路径c)，3条路径上相邻数据模型间查询耗时如表5所示，应用Dijkstra算法可得最优路径为路径c。该路径直接将告警配置信息关联到终节点板卡信息表，省去了对数据集表、IED装置表、保护装置表的访问，访问数据表的数目最小。事实上，3个路径的耗时分别为：5.212、4.992、4.874 s，应用Dijkstra算法确定的数据最优访问路径与实际相符。

5 结 论

本文分析了继电保护专业管理对一体化数据建模的需求，从继电保护数据模型结构和级联数据表访问次序两方面提出了继电保护数据查询效率的影响因素，考虑业务应用对数据对象访问顺序，依据数据对象间的关联关系建立有向图，将数据表映射为节点，将数据访问顺序映射为路径，将数据表的数据量映射为路径长度，通过Dijkstra算法对数据访问顺序进行了优化，提升了专业应用对海量异构数据的访问效率。结论如下：

2)以提高数据模型访问效率为目标，应用Dijkstra算法提出了继电保护数据模型结构优化方法，包括增加数据表间的引用关联和数据模型结构分层优化，以及继电保护数据查询次序优化方法；

3)依据保护型号、保护装置、保护装置、配置信息等不同实体，建立了继电保护分层数据模型，增加了“告警配置→板卡信息”等数据表间的引用关联，优化了继电保护数据模型结构；应用Dijkstra算法对案例中具备多条数据访问路径的数据表访问次序进行了优化，提升了继电保护数据的查询效率。