電力系統網絡拓撲分析算法概述

［摘 要］隨著電網狀態估計技術的發展和使用計算機進行實時監控日益得到的廣泛應用，無論是實時監控、在線潮流計算、狀態估計都離不開對電力接線圖的結構進行分析。本文重點概述了計算出網絡的實時結構拓撲所采用的算法。

［關鍵詞］算法 搜索 關聯矩陣 OSPF協議 分電壓等級 有色Petri法

引言

拓撲結構不僅是潮流分析、狀態估計等高級應用的基礎， 它是電力系統網絡分析其他應用軟件的基礎，它的任務是根據電力網絡中開關的開斷狀況，通過一定的算法計算出網絡的實時結構拓撲，進而進行更高級運算以了解電力網絡的運行狀態和安全穩定性，或者得到拓撲數據供電力系統應用程序使用。同時拓撲分析的效果直接影響著工作人員進行故障估計、診斷和其他應用程序的使用效果。

一、深度或廣度搜索法

早期的網絡拓撲分析是利用堆棧技術進行搜索。一般是將拓撲結構表述為鏈表關系，用圖論中的搜索技術，如深度優先搜索法和廣度優先搜索法分析節點的連通性。這種方法一般需要建立反映拓撲結構的鏈表，通過處理鏈表實現拓撲分析，然后以搜索回溯的框架， 利用堆棧記錄劃分。由于其基本算法采用“堆棧”原理——先進后出的搜索邏輯，程序不可避免采用遞歸的實現形式，因此編程和維護較復雜，效率較低。況且當應用于實時網絡分析時， 在運算時間上不能滿足要求。

二、面向對象(OO)的啟發式搜索算法

由于在電網的實際運行過程中，狀態頻繁發生變化的開關占少數，因此將追蹤技術引入拓撲分析中，僅在開關狀態發生改變時進行局部拓撲分析，可以減少拓撲分析的計算量。在完成網絡的初始拓撲分析并構筑了電網的結點樹之后，當電網發生開關變位事件時，根據開關變位只造成局都電網拓撲發生變化的特點，采用啟發式搜索算法進行電網結點樹拓撲的跟蹤。針對不同的變位事件，分開關“開”和“合”兩種情況進行分析。實現拓撲跟蹤OO模型的啟發式拓撲分析方法，利用OO技術可擴展拓撲算法的適用范圍。

三、基于關聯矩陣的集合劃分算法

文獻[4]是以SVG圖形模型為基礎，再結合CIM 和XML的特點，采用改進的集合劃分方法---基于關聯矩陣的網絡拓撲分析方法，將拓撲分析與代數分析有機結合，這樣可進一步提高計算效率。在改進方法中，先將連接點都新建成各個獨立的拓撲點，其中連接點中包含了與拓撲點的關聯信息，這樣在歸并拓撲點時就避免了遍歷比較；在拓撲點歸并過程中只銷去拓撲點中的信息，而拓撲點對象依然存在，最后在進行一次總的導入。

四、基于OSPF協議的算法

目前獲取網絡拓撲普遍采用的方法是基于SNMP協議或ICMP協議的主動探測技術，但此類技術容易增加網絡負擔，影響其正常運行。文獻[5]提出了一種基于OSPF協議數據庫描述報文和鏈路狀態更新報文的拓撲分析算法。因為OSPF協議報文中含有網絡拓撲信息，為有效處理報文數據，所以采用這種算法。該算法的主要思想是：將OSPF協議報文按區域劃分，采用模擬路由器的工作方式構造鏈路狀態數據庫，分別計算各個區域的拓撲，再利用邊界路由器連接分散的拓撲得到完整的網絡拓撲。

五、分電壓等級算法

該拓撲分析方法只搜索斷開開關所在的廠站電壓等級，大大減小了搜索的空間，提高了網絡拓撲分析的效率。其基本原理為：首先對所有狀態發生變化的開關(或刀閘)信息進行掃描，根據開關信息判斷開關的首末連接節點是否在同一電壓等級。分級搜索法流程見圖所示。

當開關狀態發生變化時，可能會對初始拓撲節點編號造成以下幾種影響：

(1)網絡內開關操作后，未造成拓撲節點變化，連接節點仍屬于同一拓撲節點；(2)開關開斷后分裂出一個或多個拓撲節點；(3)開關閉合后刪除一個或多個拓撲節點；(4)以上情況的組合。

在初始拓撲節點編號的基礎上中，以上幾種情況可以歸結為兩類來處理：

(1)新增的拓撲節點，其編號排在初始拓撲節點最大編號之后；(2)不增加新拓撲節點，采用初始拓撲節點編號。

這樣，網絡中任何開關操作對拓撲節點造成的任何影響都可以在初始拓撲節點的基礎上歸結為兩類操作，簡單明了，易于實現。

六、基本分析單元的有色Petri法

將整個電網拓撲分析問題分解為若干基本分析單元，采用基本分析單元的有色Petri網模型，只重新計算受開關狀態變化影響的分析單元，減小了搜索的空間，可提高拓撲分析的效率。

七、結語

以上幾種利用數據結構加上特定的算法來實現拓撲分析的改進方法，目的是為了加快拓撲的速度和效率，得到準確的拓撲結構。

參考文獻：

[1] 于爾鏗：電力系統狀態估計．北京：水利電力出版社，1985

[2] 劉娜：電網拓撲結構分析研究.科技資訊，2008，18（20）

[3] 董張卓，孫啟宏等．采用面向對象技術和方法的電力系統網絡拓撲的快速跟蹤．中國電機工程學報，1998，18(3)：178～181

[4] 周昊 袁泉等： 基于公共信息模型CIM和XML的電力系統拓撲分析軟件.計算機應用與軟件，2007 ，24（1）

[5] 王慧等：基于OSPF協議報文的網絡拓撲分析算法.計算機工程.2008，34(6)

[6] 朱文東 劉廣一 于爾鏗等：電力網絡局部拓撲的快速算法.電網技術，1996，20(3)：30一33

[7] 賴曉平 周鴻興： 電力系統網絡拓撲分析的有色Petri網模型.電網技術，2000，24(12)：5．10