基于多叉树自动布局的设备供电路径展现方法(学报).doc

第25卷增刊 电 网 技 术 3文章编号、中图分类号、文献标识码及学科分类号： 基于多叉树自动布局技术的设备供电路径展现方法许先锋1，范盛柳2，庄卫金1，孙名扬1(1.中国电力科学研究院，北京市 100192；2.徐州供电公司，徐州市 221400）Display Method of Power Supply Path Based On Multi-Tree Auto Layout TechnologyXU Xianfeng1, FAN Shengliu2,SUN Mingyang1,ZHUNG Weijin1(1.China Electric Power Research Institute, Beijing 100192;2.Xuzhou Power Supply Company,Xuzhou 221400)第25卷增刊电 网 技 术13 ABSTRACT: The Dispatching working staff monitor and analyse power supply path by power flow diagram in current energy management system.The power flow diagram is difficult to satisfy dispatching working staffs requirement of monitor because it is complex and static.A new display method for showing power supply path based on multi-tree auto layout technology is proposed.First,the power supply path is searched by network topology.Then it is shown dynamically using multi-tree auto layout technology.The test verify the correctness and feasibility of the proposed method.KEY WORDS：energy management system; multi-tree;auto layout;power supply path摘要：目前在能量管理系统(EMS)中，调度员主要通过全网潮流图对设备供电路径进行监视和分析。全网潮流图静态而复杂，难以满足调度员快速直观的观察需要。本文提出了一种基于多叉树自动布局技术的设备供电路径展现方法。根据电网实时运行方式，通过网络拓扑分析搜索设备的供电路径，利用多叉树自动布局技术实现设备供电路径的动态展现。针对某地级电网的测试验证了算法的可行性。关键词：能量管理系统；多叉树；自动布局；供电路径1 引言目前在能量管理系统中，调度员主要通过全网潮流图对设备供电路径进行监视和分析。全网潮流图是自动化人员根据电网结构的变化定期维护而成的静态图形。随着电网规模的不断扩大，全网潮流图日益复杂，电网运行方式也变换频繁，单纯依靠人工在全网潮流图上沿着线路走向，根据开关状态逐级穿越变电站分析供电路径的方法原始而低效。利用计算机技术动态、智能的实现设备供电路径的搜索和展现，是智能调度发展的未来趋势。文献4-12研究了潮流图和配网单线图的自动生成技术，主要解决潮流图的自动布局和自动布线技术。从计算机理论的角度来看，全网潮流图是图状结构。变电站对应图的结点，连接变电站的线路对应图的边。图状结构纷繁复杂，难以直观观察结点之间的拓扑连接联系。与图相比，多叉树的结点采用分层排列，层次分明，边和边没有交叉，通路清晰，便于快速把握结点间的拓扑连接关系。多叉树自动布局算法已经有相关文献介绍1，但将多叉树运用于电力系统供电路径展现中尚未见文献提及。本文提出了一种基于多叉树自动布局技术的设备供电路径展现方法。本方法首先读取电网模型信息，然后根据电网实时运行方式通过网络拓扑分析逐级搜索设备的供电路径，最后利用多叉树自动布局技术实现设备供电路径的动态展现。2多叉树自动布局技术2.1算法的基本思想全网潮流图是个图状结构，从一个变电站出发，沿着线路搜索其供电路径时，可能需要经过多个变电站才能到达最终的电源点。也就是说，利用多叉树展现不同设备的供电路径时，多叉树的层数、结点数目是不定的。为了实现多叉树的自动布局，本文在设计时遵循以下基本思想：(1)、多叉树的根结点位于第一层。(2)、多叉树不同层的结点布置在不同的纵坐标(Y坐标)上。同层的结点布置在相同的纵坐标上。层间距保持一致。(3)、多叉树的父结点位于其子结点的上一层。(4)、在横坐标(X坐标)上，父结点位于其最左子结点和最右子结点的中间。(5)、同一个父结点的叶子结点X坐标之间间距保持一致。(6)、任意层数的多叉树结点和边均不会重叠、交叉。(7)、先确定多叉树结点的X坐标和Y坐标，然后确定边的起点坐标和终点坐标。2.2结点Y坐标的计算多叉树的自动布局实质上是确定每个结点的X坐标、Y坐标和每条边的起点坐标和终点坐标。结点Y坐标的计算可以采用递归算法，先设定根结点的Y坐标和层距，然后利用下面公式进行递归：结点Y坐标=父结点Y坐标+层距 (1)根节点的Y坐标设置为默认值，默认值可以取100pixel。算法流程图如下：图1 结点Y坐标计算流程Fig.1 Flow chart of computational procedure of nodes Y-coordinate2.3结点X坐标的计算对于多叉树自动布局来说,由于多叉树的层数、结点总数、每个结点的子结点数不确定，因此结点X坐标的计算是自动布局的难点。在1.2计算结点Y坐标时，由于根结点位于第一层，因此先确定根结点的Y坐标。很容易理解，在计算结点X坐标时，我们需要先确定多叉树最左端结点的X坐标。如图2所示，需要先确定结点5的横坐标。图2 多叉树示意图Fig.2 Diagram of multi-tree 从根结点1开始出发，采用递归算法逐级搜索其最左的子结点，直到该结点是叶子结点为止。这样就可以搜索到结点5。多叉树最左端叶子结点的X坐标可以根据用户的需要设置为默认值，默认值可以取100pixel。 确定多叉树最左端结点的X坐标后，以此结点出发，采用递归算法，逐个计算各结点的X坐标。根据结点的类型，算法主要思路如下：(1)、叶子结点X坐标的计算在多叉树中，叶子结点是指没有子结点的结点。本文又将叶子结点分为有左兄弟的叶子点和无左兄弟的叶子结点。在图2中，结点6、结点7、结点9、结点11是有左兄弟的结点，结点5、结点8、结点10、结点12是无左兄弟的叶子结点。有左兄弟的叶子结点的X坐标计算公式如下：叶子结点X坐标=左兄弟结点X坐标+间距 (2)间距可以根据美观需要，设置为默认值。无左兄弟的叶子结点的X坐标的计算比较复杂。以结点12为例，为了保持结点不交叉和结点X坐标之间间距一致，结点12的横坐标应该等于结点9的横坐标加上间距。也就是说一棵子树的最左端结点的X坐标等于其左子树的最右端的结点的X坐标加上间距。从结点12搜索结点9的算法如下：1)、首先从结点12开始，递归搜索父结点，直到父结点有左兄弟结点为止。从图可知，结点12的父结点结点10没有左兄弟结点，继续搜索结点10的父结点4，结点4有左兄弟结点，搜索结束。2)、从结点4得到其左兄弟结点3。3)、从结点3递归搜索其最右子结点，直到叶子结点为止。可以得到结点9。在编程实现时，为了减少搜索的次数，一般在父结点中记录下其最右子结点的X坐标。比如，在结点3中记录下结点9的X坐标。这样在计算结点12的坐标时，只需要搜索到结点3即可。(2)、父结点X坐标的计算在子节点X坐标计算结束后，可以计算其父节点X坐标。父结点X坐标=(最左子结点X坐标+最右子结点X坐标)/2 (3)如图，结点2的X坐标计算如下：结点2的X坐标=(结点5的X坐标+结点7的X 坐标)/2 (4)(3)、结点X坐标计算流程结点X坐标详细计算流程如图3所示。图3 结点X坐标计算流程图Fig.3 Flow chart of computational procedure of nodes Y-coordinate2.4边的坐标计算 确定了多叉树各结点的X坐标和Y坐标之后，连接父子结点的边的起点和终点坐标就很容易确定。边的起点X坐标=父结点X坐标+父结点宽度/2 (5)边的起点Y坐标=父结点Y坐标+父结点高度 (6)边的终点X坐标=子结点X坐标+子结点宽度/2(7)边的终点Y坐标=子结点Y坐标 (8)式中结点的宽度和高度是指绘制时图元的宽度和高度。3设备供电路径搜索目前，各级调度管辖的电网规模越来越大。为了保证供电可靠性，每个变电站经常采用多路电源供电方式。快速判断设备的供电路径对于调度员把握电网实时工况具有重要的实用价值。3.1设备供电路径的搜索我们在这里定义的设备供电路径，是指根据电网实时运行方式，从用户点选的设备出发，沿着变压器和线路进行搜索，直到搜索到系统中最高电压等级母线为止，沿途经过的厂站和线路的集合定义为供电路径。 在这里先定义下逻辑母线的概念。逻辑母线是电网拓扑分析中的基本概念，它指通过零个或多个闭合断路器和隔离开关相连的若干节点，最终表示了非开断设备之间的连接关系在可以和物理母线明显区别的前提下，逻辑母线常简称为母线2。本文介绍的供电路径搜索采用广度优先搜索算法。首先根据用户点选的设备，获得与其同一个逻辑母线的变压器绕组，判断该绕组是否是变压器高压侧绕组，如果是高压侧绕组，获得与高压侧绕组同一个逻辑母线的线路。如果该绕组不是高压侧绕组，则根据变压器模型数据获得高压侧绕组。然后沿着线路继续向对端厂站搜索，直到搜索到最高电压等级母线为止，记录下搜索时经过的起始厂站和线路。并利用下列数据结构进行存储。maplong,vectorpair st_line_vec;其中map的key代表一个厂站，map的value表示以此厂站为搜索起点所得到的对端厂站-线路对。下面举例说明。用户在图形上点选负荷A，搜索到和负荷A同一个逻辑母线的变压器A的低压侧绕组，根据变压器模型数据得到变压器A的高压侧绕组，继续获得和高压侧绕组同一个逻辑母线的线路，得到线路A，沿着线路A搜索到变电站B，然后沿着线路B继续向下一个变电站搜索。图4 供电路径搜索示意图Fig.4 Diagram of searching procedure of power supply path3.2 T接厂站的处理在电力系统中，经常有T接线和多T接线的供电方式。T接线或多T接线是指一条线路同时给多个变电站供电的接线方式。在EMS系统中，为了建模需要，通常将T接点作为T接站，将一条线路分解为多条线段，如图5所示。每条线段分别连接T接站和变电站。图5 T接线路示意图Fig.5 Diagram of T connection mode line由于系统中T接线很多，如果每个T结点都作为一个新的T接站进行维护，将导致维护工作量大。因此，在实际应用中，很多T接点常常作为一个T接站进行维护，这种维护方式使不同的线路在拓扑上互相连接，导致供电路径搜索结果错误。如图5所示。线路1和线路2本来拓扑上无直接联系，但因为定义在同一个T接站，因此在拓扑搜索时，线路1可以直接搜索到线路2，导致搜索错误。 图6 T接站示意图Fig.6 Diagram of T connection mode station 针对此问题，本文进行了如下处理：(1)根据线路ID进行过滤。当从一条线段搜索到T接站时，如果该T接站连接多条线段，根据线段所对应的线路ID进行过滤，只有线路ID和搜索起始的线路ID一致的线段才推入搜索队列，继续进行搜索。(2)T接站动态生成。当多条T接线的T结点定义为同一个T接站，在显示时，就会出现多条不相关的线路连接到同一个结点上，导致展现效果错误。本文在搜索时，每次搜到同一个ID的T接站时，将该T接站ID加上动态偏移值，作为新的T接站处理。考虑到一个EMS系统内的厂站数目一般不会超过10000，动态偏移值可取10000。3.3环路的处理电力系统是个图状结构，因此在搜索设备供电路径时,常常会通过不同的供电路径搜索到同一个变电站的情况，也就是说搜索路径构成了环。我们知道多叉树只能展现辐射状的网络结构，无法展现环状的结构。因此需要对不同路径搜索到同一个变电站的情况做特殊处理。同T接站动态生成相仿，在搜索过程中，对于重复出现的厂站也采取动态生成方法。即每次搜索到同一个ID的厂站时，将该厂站的ID加上动态偏移量，在多叉树上作为不同的结点进行展现。4总体实现 基于多叉树自动布局的设备供电路径展现的总体实现逻辑框图如下：图7 设备供电路径展现流程图Fig.7 Flow chart of display power supply path 本方法和EMS的人机界面相结合。首先用户在图形上点选一个设备，系统根据选择的设备进行供电路径搜索，将搜索到的厂站和线路形成多叉树结构，然后初始化多叉树各结点，计算多叉树的层数，建立父子结点关系，采用递归算法计算每个结点的x,y坐标，最后自动绘制多叉树，通过人机界面展现给用户。5应用情况 作为新一代调度自动化系统D5000的子功能，本方法已经成功运用在某地调D5000项目中，并于2011年12月通过专家组的项目评审。图8 设备供电路径展现图Fig.8 Diagram of display power supply path从图8中可以清楚的看出,110kV城南变属于500kV车坊变供电片区,且有多条回路进行供电。6结语 本文提出了一种基于多叉树自动布局的设备供电路径展现方法,该方法实现了供电路径的动态生成和展示，改变了多年来完全依靠人工维护图形的传统设计模式。该设计思想可以继续运用于供电范围动态展示、转供路径动态展示、片网图动态展示等功能开发中，可以减轻自动化人员的维护工作量，便于调度人员快速把握电网运行方式，大大提高了调度自动化系统的智能化水平，为下一代EMS系统的开发提供了新的思路。参考文献1 陈建. 多叉树的绘制算法研究与实现. 福建商业高等专科学校学报, 2008,12(6):94-98 2 林桂伍. 多叉树结构及其实现. 福州大学学报, 1995, 32 (1):15-19.3 龚成明. 旁路代的识别算法. 江苏电机工程, 2004, 23(4):10-12.4 刑佳磊,杨洪耕,何亚平. 地区电网运行单线图. 电力系统自动化, 2010, 34 (4):59-63.5 刘秀玲,王洪瑞,王永青. 配电网图形系统框架模型和供电路径分析的改进. 电力系统自动化, 2006, 30 (20):45-48.6 刘秀玲,王洪瑞,王永青. 配电网图形系统框架模型和供电路径分析的改进. 电力系统自动化, 2006, 30 (20):45-48.7 章坚民,王云,谷炜等. 调度大屏输电网潮流图自动生成. 电力系统自动化, 2009, 33 (24):43-48.8 杨晓波,陈邦泽. 二叉树的可视化实现. 软件, 2011, 32 (12):24-27.9 徐蔚,任雷,徐政. 电力系统潮流图自动生成软件的设计和实现. 电力系统及其自动化学报, 2008, 20(4):46-50.10 沈伟,吴文传,张伯明. 能量管理系统中电网潮流单线图自动生成算法. 电力系统自动化, 2010, 34 (6):48-5211 陈超英,刘秀玲. 一种提高电力系统图形分析智能化的方法. 继电器, 2000, 28(8):28-31.12 宋适宇,何光宇,徐彭亮,等. 输电网单线图的自动生成算法. 电力系统自