基于网络自动布局算法的电网可视化研究

吴立桐 陈宇 庞永恒 苗立莉

摘要：传统的电网拓扑图创建和编辑是需要耗费大量的时间和人力，为此研究了一种在给定电力线路数据和节点初始坐标的情况下自动生成电网布局的方法。使用自动布局算法通过重新组织总线以消除交叉和锐角来改善拓扑布局以实现较好的拓扑可视化效果。应用实例表明，通过该方法所创建的电网拓扑图包含较少的交叉数和锐角，能够明显改善网络图形的可视化效果。

关键词：电网布局;力定向图;可缩放矢量图形;网络字段布局算法;电网可视化

中图分类号：TP391

文献标志码：A

ResearchonAutomaticLayoutAlgorithmofVisualablePowerGrid

WULitong1，CHENYu1，PANGYongheng2，MIAOLili1

（1.NingheSupplyBranch，StateGridTianjinElectricPowerCompany，Tianjin300010，China;

2.CollegeofInformationScienceandEngineering，NortheasternUniversity，Shenyang110819，China）

Abstract：Thetraditionalgridtopologycreationandeditingtakesalotoftimeandlabor.Forthisreason，thisstudydescribesamethodtoautomaticallygeneratethegridlayoutaftergivingthepowerlinedataandtheinitialcoordinatesofthenodes.Thisapproachusesanautomaticlayoutalgorithmtoimprovetopologybyreorganizingthebustoeliminatecrossoversandsharpcornersforbettertopologyvisualization.Theapplicationexampleshowsthatthegridtopologymapcreatedbythismethodcontainsfewercrossoversandacuteangles，whichcansignificantlyimprovethevisualizationofnetworkgraphics.

Keywords：gridlayout;forceorientationmap;scalablevectorgraphics;networkfieldlayoutalgorithm;gridvisualization

0引言

电网拓扑以图形展示给电力工程师，将帮助电力工程师更直观地了解可能发生的电气现象。一般这些电网拓扑图是使用用户界面中提供的图形工具手动创建的。随着网络规模的扩大，创建、更新和维护这些图表的过程变得费事费力，且人工创建的图形可视化效果无法得到保证[13]。为此本研究重点关注了用力定向算法自动构造电网基本布图的课题。基本布局是指在二维平面上为电网节点分配坐标，使分支线路的交叉点最小化，并且图形整洁清晰。力定向算法的目标是从初始布局开始，通过移动保持连接的节点来实现网络的最终布局，从而实现美观的网络可视化[45]。算法原理是将整个网络模拟为一个虚拟的物理系统，在节点处具有相互排斥的电荷，这些具有电荷的节点也被模拟的机械弹簧力所吸引。对系统进行迭代模拟，直到各节点上的所有库伦力和机械力平衡，各节点上的净合力可忽略不计，达到低能量稳定状态[68]。本研究首先介绍了基本自动布局算法，并通过一个简单的示例对该算法的实现进行阐述。随后列出了在更大规模的电网上实现该算法所面临的一些实际问题，并描述了解决方法。最后将该算法应用于42总线系统，并对其初始布局和最终布局进行了比较，以证明该算法地有效性。

1自动布局算法

1.1力定向图

力定向图是由一类称为力定向算法的算法生成的，用于计算简单无向图的布局[9]。力定向算法的目标是通过模拟整个图形作为一个物理系统来实现一个美观的图形布局。这种算法只使用图结构中包含的信息，而不依赖于特定领域的知识。用这些算法生成的图是无交叉的（在平面图的情况下），并且趋向于显示对称性布局[1011]。

该算法首先将虚拟电荷附加到节点。假设网络的每个分支都包含一个虚构的弹簧。因此，在节点网络中电荷使得节点之间存在互相排斥的作用力，而弹簧则试图使与分支线路连接的节点之间存在互相吸引的作用力。在任何时刻，该网络系统都具有以电和机械形式存储的某些能量，这些能量通过各自的力相互作用。最终，系统稳定在低能状态，这对应于电力拓扑网络的最佳的可视化表达效果。

1.2算法描述

图形由二维平面上的节点和节点之间的分支线路组成。算法目标是通过移动节点来重新组织图形，而无需更改连接以实现无交叉布局。每个节点上有两种类型的力：库伦力和机械力。

1）节点k上的库伦力计算。

令（xk，yk）表示节点k的坐标，节点k和j之间的距离p为Dk-j=（xk-xj）2+（yk-yj）2，則节点k和j上的点电荷作用在节点k上的库仑力的大小[12]如式（1）。

e，k-j=Q2Q2k-j（1）

其中Q是每个节点上的电荷。

该库伦力还将具有指向节点j的节点k的两个方向。库伦力的x和y分量的计算方法[13]如式（2）。

e，k-j=Q2xk-xjD3k-j-

iyk-yiD3k-j（2）

式（2）是库伦力的复数形式，其中实部在x轴方向上，虚部在y轴方向上。作用于节点k的合力如式（3）。

e，k=∑Nj-1e，k-j（3）

2）节点k上的机械力计算。节点k和i之间的机械力大小如式（4）。

m，k-j=sKDk-j（4）

如果节点j和k连接，则s=1，s=0，否则K是弹簧常数。使用式（5）计算机械力在节点连线平行方向的分量。

m，k-j=sK[（xk-xj）+i（yk-yi）]（5）

因此，节点k上的机械合力如式（6）。

m，k=∑Nj=1m，k-j（6）

3）作用在节点k上的合力是如式（7）。

t，k=e，k+m，k（7）

库伦力和机械力的合力将用于更新网络中节点的速度和位置。首先假设所有节点的初始速度为0，则第（r+1）次迭代中第k个节点的速度如式（8）。

r+1，k=γr，k+t，km（8）

其中γ是减速因子，t，k是节点k上的合力，m是节点的质量。每个节点的坐标分别更新如式（9）。

（xk，yk）r+1=（xk，yk）r+（r+1）（9）

重复该过程直到达到停止标准或达到最大迭代次数。如果迭代中任何节点所经历的力的最大值低于预设阈值，则停止迭代计算。该停止标准用数学形式可以表示为max（t，k）

1.3算法说明

使用4节点拓扑网络对上述算法进行解释，如图1所示。

在图1中，左上角为原点（0，0），向右方向为正x轴，向下方向为正y轴。相应地，4个节点坐标（x，y）分别为：节点1（100，100）、节点2（200，100）、节点3（100，200）和节点4（200，200）。网络有5个线路，线路对应的节点对分别为：12、13、23、34、14。由图1可以看出，线路14和23彼此交叉，因此网络的初始布局不美观。下面利用力定向算法重新对网络图进行布局，尽可能避免交叉。

其中一个节点的位置是固定的，其他节点相对于固定节点移动。首先固定节点4的初始坐标值（200，200）。接下来，移动节点1，并利用公式1和公式2计算节点2、3和4作用于它的库伦力。每个节点上的电荷值假定为10个单位，弹簧常数也假定为10个单位。这些参数的实际单位并不相关，因为电荷和弹簧只是虚构的，算法只关注对作用在节点上的相对库伦力和机械力。所计算出的库伦力如表1的第三列所示。

需要注意，这些库伦力是同时具有大小和方向的复数，其中实部代表x轴方向，虚部代表y轴方向。随后继续计算机械力。再次固定节点4的坐标位置，并使用等式（4）和（5）计算节点1上的机械力。所计算得出的节点1相对于节点2、3和4的三个机械力如表1第四列所示。每个节点的合力是机械力和库伦力的相加，如图2所示。

应选择合适的电荷和弹簧常数，以便使库伦力和机械力相互比较，因此如果一种力在另一种力中占主导地位的因素很大，那么力定向算法的性能就会很差。

本例中的相关参数取值为：Q=10，K=10，γ=0∶9，m=50。第一次迭代后，坐标为：节点1（100.76，100.76）、节点2（199.23，99.68）、节点3（100.76，199.23）和节点4（200，200）。

在4节点网络的情况下，经过300次迭代计算最终达最优拓扑布局，如图3所示。

在迭代过程中的网络总能量的变化如图4所示。

可以注意到，最终布局没有分支的交叉，可视化效果相对于图1有明显提升。

2仿真分析

在将力导向图算法应用于较大电力网络布局时，需要对一些输入参数和具体流程进行优化调整，以使算法能够发挥最优性能。

2.1算法调整

首先是调整弹簧常数。作为线路参数之一，弹簧常数的大小会影响自动布局算法的性能。具有低电抗的线路应具有较高的机械吸引力，因此应该分配较高的弹簧常数，反之则分配较低的弹簧常数[1415]。在数学上，每条线路的弹簧常数，如式（10）。

K=K01（z+ε）（10）

式中K0是默认的弹簧常数，z是线路的阻抗，ε是弹簧常数阈值。在z值接近零的情况下，需要该限制来限制弹簧常数的大小。

其次是去除网络中的锐角。在大型电网中，力导向图算法创建的拓扑图中由于角节点被另一组节点排斥而出现无法消除的尖角。如图5（a）所示。

节点1和2组成为锐角。锐角定义为两节点边缘之间的角度小于20°。在力导向图算法中，节点6是固定的，而节点1和2必须穿过节点3，4和5，以便消除尖角。但来自节点3、4和5的排斥库伦力不允许这样做，因此该算法无法消除这些锐角，如图5（b）所示。所以需要通过以下列方式调整算法的迭代过程来解决这个问题。首先，准备了两个节点及其邻居的列表;随后使用它们的坐标计算每两个节点的角度，如果该角度小于所定义的锐角角度，则锐角的坐标将被其邻居的中点坐标替换;然后继续上述迭代过程，直至没有锐角为止或到达迭代次数上限。在本仿真实验中，当检测到尖角时，节点1将跳到节点6和4的中点，节点2将跳到节点5和6的中点。最后获得无交叉、无锐角的布局，如图5（c）所示。

经过优化调整的算法实现，如图6所示。

2.2数据

总线数据和分支线路数据被视为输入文件，以逗号分隔值（csv）格式准备。总线数据包括第一列中的节点名称和后面两列中的节点的初始坐标。分支数据包括节点与前两列中的节点之间的连接。线路的电阻和电抗也可任选地包括在接下来的两列中。如果可用，这些值可用于修改弹簧常数。修改后的总线数据将由程序生成，并具有初始总线数据的确切结构，但具有新的重新排列的坐标值。

2.3程序

作为算法的核心，坐标计算程序实现对节点坐标的计算。坐标计算器读取输入文件以获取电网的初始结构。该算法还需要输入以下参数：（1）电荷Q：这是假定在每个节点处存在的虚拟电荷;（2）默认弹簧常数K0;（3）最大迭代次数;（4）停止标准中的最小合力Fmin;（5）减速因子;（6）锐角的最大角度θsharp。坐标计算程序基于这些参数对所有节点坐标进行更新并将最终坐标写入修改的总线数据文件。电网初始结构由另一个程序创建。该程序创建初始和最终布局的图形表示。图6中的总线数据和分支线路数据文件用于创建初始布局，而修改的总线数据用于创建最终布局。

2.4布局的可视化

使用可缩放矢量图形（SVG）技术对所生成的拓扑布局进行可视化显示。SVG是一种基于XML的矢量图像格式，用于支持交互性和动画的二维图形。SVG是面向文档的通用解决方案，可以适应所有主流浏览器的、基于开放标准的、面向文档的通用图形描述格式。因此本算法使用SVG技术来描述网络布局的可视化图形。以下是对应于如图1所示的4节点系统的初始布局文件（initial.svg）。

<？xmlversion="1.0"standalone="no"？>

<！DOCTYPEsvgPUBLIC"//W3C//DTDSVG1.1//EN"

"http：//www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">

xmlns="http：//www.w3.org/2000/svg"

xmlns：xlink="http：//www.w3.org/1999/xlink">

1

2

3

4

上述文件（initial.svg）由布局創建程序通过读取总线和分支线路数据生成。initial.svg文件在浏览器中打开时将以图形形式显示。

2.542总线的电网自动布局

在辽宁省西部地区的42总线电网系统上对本研究的电网拓扑布局算法进行了测试。电网中节点坐标（即总线数据）如下所示：节点1（374，160）、节点2（542，83）、节点3（808，138）、节点4（827，213）、节点5（809，312）、节点7（501，829）、、节点10（496，760）、节点11（360，88）、节点17（970，799）、节点41（921，739）、节点45（925，693）、节点50（827，714）、节点55（936，508）、节点60（856，508）、节点67（594，341）、节点98（922，832）、节点100（925，763）、节点103（677，678）、节点108（853，400）、节点115（917，268）、节点116（580，252）、节点125（474，154）、节点130（486，341）、节点148（468，199）、节点149（921，188）、节点167（909，140）、节点175（285，545）、节点191（208，564）、节点195（107，548）、节点202（176，457）、节点207（333，262）、节点211（618，539）、节点213（451，263）、节点223（455，400）、节点224（491，479）、节点234（402，625）、节点236（22，538）、节点237（118，453）、节点257（163，723）、节点258（102，655）、节点259（254，703）、节点265（223，645）。

节点之间的连接的分支线路数据为：（1，207）（1，125）（2，125）（2，130）（2，3）（3，4）（4，5）（5，211）（5，108）（5，115）（5，116）（7，10）（10，67）（10，234）（11，1）（11，125）（11，2）（17，41）（41，45）（45，50）（45，55）（45，108）（50，60）（50，103）（67，103）（98，17）（100，45）（100，60）（103，211）（108，116）（108，149）（115，148）（116，213）（116，125）（125，213）（125，130）（167，148）（167，3）（175，191）（175，234）（191，195）（191，202）（191，234）（195，202）（202，207）（207，213）（211，224）（213，223）（224，234）（236，195）（237，223）（237，224）（257，258）（257，265）（257，265）（258，259）（258，195）（259，191）（265，234）。

用于运行该系统的坐标计算器的参数是：Q=1.0，K0=0.3，最大迭代次数为2000，

Fmin=0.9，γ=0.7，并且θsharp=60°。初始布局和最终布局的仿真结果，如图7所示。

为了显示结果，图7中节点的编号从1到42连续进行，这对应于上面以相同顺序提到的总线数据坐标。由图7可以看出，最终布局包含较少数量的交叉和锐角线路，具有较好的可视化效果。

3总结

将力定向算法应用于电力系统网络自动布局生成的实例说明了该算法的有效性，同时指出了力定向布局算法的局限性，即对大型网络的可扩展性和存在锐角的问题。本研究通过对算法进行一些修改，解决了这些局限性，并指出了改进之处。未来本研究将在以下方向继续深入研究。首先是改进布局算法，使其适用于具有数百个节点乃至更大规模的

电网;其次是开发一个基于Web的平台，使该算法成为该平台的一个服务组件，任何用户都可以上传网络的初始布局并下载得到最终优化的电网布局;最后是在完成电网拓扑布局的基础上，增加更多维度电力系统数据的可视化，如总线名称、线路潮流、电压值等。

参考文献

[1]张喜涛，吴玲达，于少波，等.面向多层网络可视化的多力导引节点自动布局算法[J].计算机辅助设计与图形学学报，2019（4）：639646.

[2]周景贤，王文艳.基于节点分类的混合型网络拓扑布局算法[J].现代电子技术，2019，42（7）：9599.

[3]徐丽丽，董一鸿，王雄，等.基于Ksup稠密子图的大规模复杂网络概要算法及可视化[J].计算机辅助设计与图形学学报，2019，31（3）：400411.

[4]張野，王松，吴亚东.FMR：基于FR的快速多层次算法[J].图学学报，2019，40（1）：7886.

[5]陈炳坤，周虹.基于多层图布局算法的不确定性网络可视化方法[J].图学学报，2018，39（06）：11301138.

[6]周家智，尹令，张素敏.基于遗传模拟退火算法的布局优化研究[J].图学学报，2018，39（3）：567572.

[7]刘超，万莹.面向动态网络状态的数据可视化研究[J].信息技术，2018（5）：115120.

[8]苏凯，岳德鹏，YANGDi，等.基于改进力导向模型的生态节点布局优化[J].农业机械学报，2017，48（11）：215221.

[9]李学平，宋国彬，卢志刚.基于改进引力斥力算法的配电网馈线单线图分块布局[J].电力系统自动化，2017，41（23）：117122.

[10]陈力平，何博，王玲.基于节点相似度的力引导改进算法[J].计算机应用，2017，37（S2）：214218.

[11]周弦，梁霄，黄廷磊.基于节点中心性的时变复杂网络布局算法[J].系统工程与电子技术，2017，39（10）：23462352.

[12]汤颖，盛风帆，秦绪佳.基于改进力导引图布局的层级视觉抽象方法[J].计算机辅助设计与图形学学报，2017，29（4）：641650.

[13]吴丽贤，邓肃.基于GIS的配网单线图自动成图算法[J].信息技术，2016（8）：155158.

[14]周博曦，孟昭勇，吴文宣，等.辐射接线模式的配电馈线单线图自动绘制算法[J].中国电力，2015，48（12）：136140.

[15]陈连杰，赵仰东，韩韬，等.基于层次结构及模型驱动的配电网图形自动生成[J].电力系统自动化，2015，39（1）：226232.

（收稿日期：2019.07.06）