论文部分内容阅读
摘要：本文在调研GIS系统应用在配电管理的基础上，阐述了市场经济条件下对配电GIS中网络拓扑算法研究的必要性，在充分分析目前网络拓扑算法主流两种算法树搜索法和邻接矩阵法优劣后，提出根据人工智能，继续改进已有网络拓扑分析算法的三个方向，为改进的网络拓扑分析算法工作提供了有价值的参考建议。
关键词：网络拓扑；算法；配电GIS
中图分类号：TM711 文献标识码：A 文章编号：1001-828X（2012）11-0-02
引言
地理信息系统（Geographic Information System）起源于20世纪60年代。随着地球科学、计算机技术、大地测量技术、航空技术和信息科学的发展，逐步形成了新的技术系统——地理信息系统。从广义上讲，地理信息系统是加工空间数据成为信息的工具，这些信息通常与地球上某些部分明确相连并用于各种工程决策。
配电GIS系统又称为AM/FM/GIS，是一种面向配电网管理的专业GIS，一般基于通用GIS平台结合专业特点二次开发而成，是GIS在电力信息系统中的一种延伸。配电GIS是地理信息系统在配电系统中的应用，可以提供配电网管理所需的地理层和设备层的基础数据。
配电GIS的最基本特征是在电子地图背景上进行配电网的管理，一般都基于某个地理信息平台开发，目前国外上比较成功的有：Arc/Info、SmallWorld、MapInfo等，国内的有GeoStar、GrowGIS、SuperMap等。目前的配电GIS系统一般都采取客户端/服务器（C/S）构架或浏览器/服务器（B/S）构架或二者同时具备，同时支持多用户分布式处理。
在配电GIS系统中，配电网络拓扑是配电网分析和优化的基础。配电网是一种和地理信息密切相关的网络，线路以及配电设备和用户的分布都有明显的地理特征，在配电网络运行中许多操作都依赖于长度、距离、范围、相对位置等地理因素，地理信息系统在配电网中的应用提高了配电网的管理水平，因此基于地理信息系统（GIS）的配电网络拓扑成为人们最关注的问题之一。
大量文獻对配电网络拓扑进行了研究，早期通过人工输入的方法将配电网的接线关系填入特定的数据结构中，这些方法不仅需要人工录入大量的数据且其数据结构通用性、可扩充性差、占用存储空间大。后来发展到先基于矢量图自动生成配电网络的原始拓扑，再转化为适合电力应用的拓扑数据。这类方法虽然提高了建模的效率，但是其数据结构复杂、参与配电网络拓扑建模的设备种类众多，尤其是在配电网规划、设计中配电网的接线图绘制往往不规范，仍然需要大量的人机交互，造成配电网规划、设计的效率低下。
一、配电网拓扑分析算法分析
电力系统网络拓扑分析的任务是处理开关信息的变化，形成新的网络接线，为网络分析的各种应用软件开发奠定基础。配电潮流、短路计算、网络重构等都使用网络各组成部分之间的电气联系这类信息。在实时运行时，这类信息必须随时更新，否则，从一个不能正确反映实际网络电气联系的结构出发所进行的各种计算将会导致错误的结果。
通常网络接线分析包括两个步骤：母线分析和电气岛分析。母线分析是将闭合开关连接在一起的节点集合定义为一个母线；电气岛分析是将线路和变压器连接在一起的母线集合定义为一个“岛”。既有电源又有负荷的“活岛”在物理上对应带电部分；“死岛”在物理上对应停电部分。“活岛”用于计算，“死岛”没有计算意义，但对指导检修却非常重要。常用的网络拓扑分析算法包括树搜索法和邻接矩阵法。
二、树搜索法
树搜索法是目前针对网络拓扑分析的最常用的方法，树搜索法是通过搜索节点的相邻节点的方法来进行网络的拓扑分析，的常用的树搜索法包括深度优先搜索法（Deep First Search，简称DFS）和广度优先搜索法（Bread First Search，简称BFS）。
1.深度优先搜索法
深度优先搜索法的具体搜索过程是这样的：DFS在访问图中某一起始定点V后，访问V的任意相邻节点V1；再从V1出发，访问与V1相邻但还未访问过的节点V2；再从V2出发，进行类似的访问，……如此进行下去，直到到达所有相邻节点都被访问过的节点U为止。接着，退回一步，返回到前一次刚访问的节点，看是否还有其它没有被访问过的相邻节点。如果有，则访问此节点，之后再从此节点出发进行与前述类似的访问；如果没有就再退回一步进行搜索。重复上述过程，直到连通图中所有节点都被访问过为止。
以图1为例，深度优先搜索法的一个可能的节点访问顺序是：V1，V2，V6，V10，V7，V8，V9，V3，V4，V5。
2.广度优先搜索法
广度优先搜索法的具体搜索过程是这样的：BFS在访问图中某一起始定点V后，由V出发，依次访问V的各个未被访问过的相邻节点V1，V2，…，Vt，再依次访问V1，V2，…，Vt各个未被访问过的相邻节点，如此进行，直到连通图内所有节点都被访问过为止。
以图1为例，广度优先搜索法的一个可能的节点访问顺序是：V1，V2，V6，V3，V7，V10，V4，V5，V8，V9。
由于此种网络拓扑分析方法是利用堆栈技术进行搜索，对所有结点分配母线号，当开关状态发生变化后，重新在每个厂站内进行搜索，并重新为母线编号。这种针对局部网络状态的变化而采取的大范围搜索，不可避免的造成了时间上的浪费。
3.深度优先搜索法与广度优先搜索法比较
深度优先搜索法的算法是一个递归的过程，将深度搜索法的具体搜索过程设计成一个递归函数可以使得程序的编制比较简单和清晰。广度优先搜索法不是一个递归的过程，必须采用一个队列，将某个顶点的未访问的邻接顶点依次放入队列中，然后从队列的头依次取出每个顶点进行访问。图中的每一个顶点进队列一次且仅进队列一次。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的节点，便于向下一层访问。由于队列的操作遵循先进先出的原则，因此在处理过程中，只有在前一步的所有状态处理完后，才能处理后面一步的状态。访问中将线路作为树中的节点数据，与被访问节点属同一线路级别的节点地址放在节点的右链域；比被访问节点的线路级别低的节点地址放入节点的左链域。 三、邻接矩阵法
邻接矩阵通过自乘可以得到全接通矩阵。邻接矩阵法主要通过邻接矩阵的自乘运算得到全接通矩阵，再运用全接通矩阵来判断网络各节点之间的连通关系。
邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=（V，E）是一个图，其中V={v1，v2，…，vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：①对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零，有向图则不一定如此。②在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。③用邻接矩阵法表示图共需要n2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1 2 … （n-1）=n（n-1）/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。
在文献中提出了一种基于关联矩阵的电网拓扑辨识算法。该算法使用节点-支路关联矩阵表示配电网络的基本拓扑结构，定义了矩阵的“与-或”乘法运算，利用连通性的传递性质，实现对配电网络的拓扑辨识。在此基础上，利用节点-支路关联矩阵和节点-节点连通矩阵的对称性，提出了加快计算的技术和实现方法。
文献中把配电网映射成节点-支路模型，形成节点-支路的邻接矩阵，并在此基础上提出了配电网连通域的概念。在文献中重点阐述了连通域的分离算法和基于DFS进行拓扑分析的流程并在配电网动态拓扑着色中进行了运用，以实现各种复杂结构的电力网的网络拓扑分析，该文献中提出矩阵结构的网络拓扑技术，可具有很好的通用性和很强的可扩展性。同时，建立网络拓扑矩阵与电网接线结.构相互对应，具有运用灵活和修改方便的优点。
邻接矩阵算法的优点：可以清晰、直观的表示网络拓扑图的连接情况；但是也存在着明显的缺点：消耗内存空间，在系统运行时消耗内存多；浪费存储空间，因为对于n个顶点的图来说，需要n个存储单元，需要的存储空间大。
四、结束语
网络拓扑分析算法一直都是业界研究的重点，其应用范围广，在许多领域都有其重要的指导意义。客观地说，目前并不存在一种求解拓扑问题的最佳算法，如前文所述的各个算法都有其应用的局限性：树搜索法追求精确解，但是忽略了算法的时间消耗；而邻接矩阵法改进算法则是追求时间快，但是在求解的空间消耗上结果上往往不能让人满意。笔者认为今后在网络拓扑分析的算法研究上应该把握3个方面：继续改进已有网络拓扑分析算法；采用人工智能的思想，创造新的网络拓扑分析算法；集合各个算法的优点，进行混合网络拓扑分析算法的研究。目前这些相关方向业界人士都有所涉及，也都取得了一定成效，相信在不久的将来，网络拓扑分析算法问题一定会有更好的解决方案。
参考文献：
[1]江南，于雪英.地理信息系统及其展望[J].电力系统自动化，2003（18）.
[2]邱家驹，李军.配电网络地理信息系统[J].电力系统自动化，1997，21（3）：13-16.
[3]何春林.配电GIS功能和实现方法初探[J].中国电力，2001（S1）：52-55，59.
[4]张磊.基于组件的配电网地理信息系统的研究与开发[D].北京：华北电力大学，2002.
作者简介：魏凤霞（1965-），女，河南滑县人，2006年毕业于山西大學行政管理专业，经济师，现从事信息系统运维管理工作。
关键词：网络拓扑；算法；配电GIS
中图分类号：TM711 文献标识码：A 文章编号：1001-828X（2012）11-0-02
引言
地理信息系统（Geographic Information System）起源于20世纪60年代。随着地球科学、计算机技术、大地测量技术、航空技术和信息科学的发展，逐步形成了新的技术系统——地理信息系统。从广义上讲，地理信息系统是加工空间数据成为信息的工具，这些信息通常与地球上某些部分明确相连并用于各种工程决策。
配电GIS系统又称为AM/FM/GIS，是一种面向配电网管理的专业GIS，一般基于通用GIS平台结合专业特点二次开发而成，是GIS在电力信息系统中的一种延伸。配电GIS是地理信息系统在配电系统中的应用，可以提供配电网管理所需的地理层和设备层的基础数据。
配电GIS的最基本特征是在电子地图背景上进行配电网的管理，一般都基于某个地理信息平台开发，目前国外上比较成功的有：Arc/Info、SmallWorld、MapInfo等，国内的有GeoStar、GrowGIS、SuperMap等。目前的配电GIS系统一般都采取客户端/服务器（C/S）构架或浏览器/服务器（B/S）构架或二者同时具备，同时支持多用户分布式处理。
在配电GIS系统中，配电网络拓扑是配电网分析和优化的基础。配电网是一种和地理信息密切相关的网络，线路以及配电设备和用户的分布都有明显的地理特征，在配电网络运行中许多操作都依赖于长度、距离、范围、相对位置等地理因素，地理信息系统在配电网中的应用提高了配电网的管理水平，因此基于地理信息系统（GIS）的配电网络拓扑成为人们最关注的问题之一。
大量文獻对配电网络拓扑进行了研究，早期通过人工输入的方法将配电网的接线关系填入特定的数据结构中，这些方法不仅需要人工录入大量的数据且其数据结构通用性、可扩充性差、占用存储空间大。后来发展到先基于矢量图自动生成配电网络的原始拓扑，再转化为适合电力应用的拓扑数据。这类方法虽然提高了建模的效率，但是其数据结构复杂、参与配电网络拓扑建模的设备种类众多，尤其是在配电网规划、设计中配电网的接线图绘制往往不规范，仍然需要大量的人机交互，造成配电网规划、设计的效率低下。
一、配电网拓扑分析算法分析
电力系统网络拓扑分析的任务是处理开关信息的变化，形成新的网络接线，为网络分析的各种应用软件开发奠定基础。配电潮流、短路计算、网络重构等都使用网络各组成部分之间的电气联系这类信息。在实时运行时，这类信息必须随时更新，否则，从一个不能正确反映实际网络电气联系的结构出发所进行的各种计算将会导致错误的结果。
通常网络接线分析包括两个步骤：母线分析和电气岛分析。母线分析是将闭合开关连接在一起的节点集合定义为一个母线；电气岛分析是将线路和变压器连接在一起的母线集合定义为一个“岛”。既有电源又有负荷的“活岛”在物理上对应带电部分；“死岛”在物理上对应停电部分。“活岛”用于计算，“死岛”没有计算意义，但对指导检修却非常重要。常用的网络拓扑分析算法包括树搜索法和邻接矩阵法。
二、树搜索法
树搜索法是目前针对网络拓扑分析的最常用的方法，树搜索法是通过搜索节点的相邻节点的方法来进行网络的拓扑分析，的常用的树搜索法包括深度优先搜索法（Deep First Search，简称DFS）和广度优先搜索法（Bread First Search，简称BFS）。
1.深度优先搜索法
深度优先搜索法的具体搜索过程是这样的：DFS在访问图中某一起始定点V后，访问V的任意相邻节点V1；再从V1出发，访问与V1相邻但还未访问过的节点V2；再从V2出发，进行类似的访问，……如此进行下去，直到到达所有相邻节点都被访问过的节点U为止。接着，退回一步，返回到前一次刚访问的节点，看是否还有其它没有被访问过的相邻节点。如果有，则访问此节点，之后再从此节点出发进行与前述类似的访问；如果没有就再退回一步进行搜索。重复上述过程，直到连通图中所有节点都被访问过为止。
以图1为例，深度优先搜索法的一个可能的节点访问顺序是：V1，V2，V6，V10，V7，V8，V9，V3，V4，V5。
2.广度优先搜索法
广度优先搜索法的具体搜索过程是这样的：BFS在访问图中某一起始定点V后，由V出发，依次访问V的各个未被访问过的相邻节点V1，V2，…，Vt，再依次访问V1，V2，…，Vt各个未被访问过的相邻节点，如此进行，直到连通图内所有节点都被访问过为止。
以图1为例，广度优先搜索法的一个可能的节点访问顺序是：V1，V2，V6，V3，V7，V10，V4，V5，V8，V9。
由于此种网络拓扑分析方法是利用堆栈技术进行搜索，对所有结点分配母线号，当开关状态发生变化后，重新在每个厂站内进行搜索，并重新为母线编号。这种针对局部网络状态的变化而采取的大范围搜索，不可避免的造成了时间上的浪费。
3.深度优先搜索法与广度优先搜索法比较
深度优先搜索法的算法是一个递归的过程，将深度搜索法的具体搜索过程设计成一个递归函数可以使得程序的编制比较简单和清晰。广度优先搜索法不是一个递归的过程，必须采用一个队列，将某个顶点的未访问的邻接顶点依次放入队列中，然后从队列的头依次取出每个顶点进行访问。图中的每一个顶点进队列一次且仅进队列一次。为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的节点，便于向下一层访问。由于队列的操作遵循先进先出的原则，因此在处理过程中，只有在前一步的所有状态处理完后，才能处理后面一步的状态。访问中将线路作为树中的节点数据，与被访问节点属同一线路级别的节点地址放在节点的右链域；比被访问节点的线路级别低的节点地址放入节点的左链域。 三、邻接矩阵法
邻接矩阵通过自乘可以得到全接通矩阵。邻接矩阵法主要通过邻接矩阵的自乘运算得到全接通矩阵，再运用全接通矩阵来判断网络各节点之间的连通关系。
邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=（V，E）是一个图，其中V={v1，v2，…，vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：①对无向图而言，邻接矩阵一定是对称的，而且对角线一定为零，有向图则不一定如此。②在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。③用邻接矩阵法表示图共需要n2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵中剔除了左上右下对角线上的0元素后剩余的元素，故只需1 2 … （n-1）=n（n-1）/2个单元。无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。
在文献中提出了一种基于关联矩阵的电网拓扑辨识算法。该算法使用节点-支路关联矩阵表示配电网络的基本拓扑结构，定义了矩阵的“与-或”乘法运算，利用连通性的传递性质，实现对配电网络的拓扑辨识。在此基础上，利用节点-支路关联矩阵和节点-节点连通矩阵的对称性，提出了加快计算的技术和实现方法。
文献中把配电网映射成节点-支路模型，形成节点-支路的邻接矩阵，并在此基础上提出了配电网连通域的概念。在文献中重点阐述了连通域的分离算法和基于DFS进行拓扑分析的流程并在配电网动态拓扑着色中进行了运用，以实现各种复杂结构的电力网的网络拓扑分析，该文献中提出矩阵结构的网络拓扑技术，可具有很好的通用性和很强的可扩展性。同时，建立网络拓扑矩阵与电网接线结.构相互对应，具有运用灵活和修改方便的优点。
邻接矩阵算法的优点：可以清晰、直观的表示网络拓扑图的连接情况；但是也存在着明显的缺点：消耗内存空间，在系统运行时消耗内存多；浪费存储空间，因为对于n个顶点的图来说，需要n个存储单元，需要的存储空间大。
四、结束语
网络拓扑分析算法一直都是业界研究的重点，其应用范围广，在许多领域都有其重要的指导意义。客观地说，目前并不存在一种求解拓扑问题的最佳算法，如前文所述的各个算法都有其应用的局限性：树搜索法追求精确解，但是忽略了算法的时间消耗；而邻接矩阵法改进算法则是追求时间快，但是在求解的空间消耗上结果上往往不能让人满意。笔者认为今后在网络拓扑分析的算法研究上应该把握3个方面：继续改进已有网络拓扑分析算法；采用人工智能的思想，创造新的网络拓扑分析算法；集合各个算法的优点，进行混合网络拓扑分析算法的研究。目前这些相关方向业界人士都有所涉及，也都取得了一定成效，相信在不久的将来，网络拓扑分析算法问题一定会有更好的解决方案。
参考文献：
[1]江南，于雪英.地理信息系统及其展望[J].电力系统自动化，2003（18）.
[2]邱家驹，李军.配电网络地理信息系统[J].电力系统自动化，1997，21（3）：13-16.
[3]何春林.配电GIS功能和实现方法初探[J].中国电力，2001（S1）：52-55，59.
[4]张磊.基于组件的配电网地理信息系统的研究与开发[D].北京：华北电力大学，2002.
作者简介：魏凤霞（1965-），女，河南滑县人，2006年毕业于山西大學行政管理专业，经济师，现从事信息系统运维管理工作。