電力網絡拓撲分析與源流路徑鏈生成算法

陳 彬， 于繼來

(1.哈爾濱工業大學電氣工程系， 哈爾濱 150001；2.福建省電力有限公司電力科學研究院， 福州 350007)

電力網絡拓撲分析與源流路徑鏈生成算法

陳 彬1，2， 于繼來1

(1.哈爾濱工業大學電氣工程系， 哈爾濱 150001；2.福建省電力有限公司電力科學研究院， 福州 350007)

為快速、準確和全面地求取電力網絡源流路徑鏈，提出了一種新型的網絡拓撲分析與源流路徑鏈生成算法。該算法首先根據電網某一拓撲結構及其潮流狀態形成有向圖和送端節點-送電支路鄰接表，然后進行兩輪拓撲分析，快速生成源流路徑樹，并由此獲取相關的源流路徑鏈。此算法無需通過基于圖論鄰接終點矩陣的復雜運算，簡便快捷。此外，該算法可用于求解電力網絡發生局部拓撲和局部潮流流向變化后的路徑鏈局部修改問題。

電力網絡； 拓撲分析； 有向圖； 源流路徑鏈

電力市場環境下的許多問題都要求掌握電能在不同運行狀態下不同網絡元件間流動和分配的細節，而如何獲得電能在某一源流對之間傳輸路徑的具體構成[1，2]，即電力網絡源流路徑鏈的拓撲關系，則是解決上述與路徑構成有關問題的前提和關鍵。然而，在實際電力系統中，電力網絡拓撲結構錯綜復雜，潮流分布狀態實時改變，使得電力網絡源流路徑具有為數眾多、交錯重疊、變化頻繁的特點，這對路徑鏈的求取造成了較大困難。

為快速、準確和全面地求取電力網絡源流路徑鏈，本文基于網絡拓撲分析方法對電力網絡源流路徑進行研究，提出了一種新型的網絡拓撲分析與源流路徑鏈生成算法。該算法能夠進行電力網絡源流路徑拓撲關系分析，并求取全網源流路徑鏈集合，結合電力網絡基電氣原理和電氣規律，可應用于求解源供電路徑、負荷流受電路徑、源流對供受電路徑、支路源供電路徑、支路流受電路徑等方面的電氣剖分。

1 電力網絡有向圖的形成

圖論作為一種適用于求解與網絡拓撲有關問題的成熟理論，在電力系統中得到了廣泛應用[3～6]。將一定狀態下的電力網絡處理為有向圖，是源流路徑鏈生成算法的基礎。

據圖論[7，8]，圖由一個頂點集合加一個連接不同頂點對的邊集合組成。若將一定狀態下的電力網絡節點抽象為頂點，支路抽象為邊，邊的方向取該狀態下有功潮流實際流向，則一定狀態下的電力網絡將被抽象為一個有向圖D(V，U)，其中電網節點集合抽象為頂點集合V，以有功潮流方向為正方向的送電支路集合抽象為有序積V×V的子集U，送電支路抽象為U的元素弧au，v，u為弧a的起點，v為終點，分別表示送電支路的送、受端節點。電力系統如圖1所示，其狀態對應的有向圖如圖2所示。

圖1 6母線電力系統

圖2 6母線電力系統有向圖

假定研究系統不存在環流。若存在環流，則在生成有向圖前將環流拆開。通過對電力網絡中某一源的送電路徑進行拓撲分析可得，某一源的電能從源出發通過不同的支路集合送到相關的流集合，形成了從某一源出發的源流路徑鏈集合。在圖論中，這種集合可抽象為有向圖D(V，U)的一棵有向生成樹T，它是D(V，U)的一個生成子圖而且又是一棵樹(無圈連通無向圖)，源所在的節點抽象為T的根，流所在的節點抽象為T的葉，其他節點抽象T的分枝頂點，送電支路抽象為T的樹枝。圖3為對圖1系統節點1上的源(簡稱源1)送電路徑進行拓撲分析得到的有向生成樹。

圖3 源1作為根頂點的有向生成樹

同理，在從某一源出發的源流路徑鏈集合中，每一條源流路徑鏈都可以抽象為樹T中的一條從根可達對應某一流的分枝頂點的有向道路M，M的長度稱為葉的層數。圖4為從源1有向生成樹中得到的一條從源1到節點6的流(簡稱流6)的有向道路。

圖4 有向道路

2 網絡拓撲分析與源流路徑鏈生成算法

在形成的有向圖中，集中了全網的源流路徑鏈。然而，各個源流對之間的路徑鏈不是相互獨立的，它們在部分拓撲關系上以交錯重疊的形式存在，即某一有向邊(對應原網絡某一條送電支路)可能為不同的源流路徑鏈共用。如何快速準確地從有向圖中分析出全網源流之間的拓撲關系，并形成相關的源流路徑鏈集合，這是獲得源流路徑鏈的關鍵。

本文提出一種新型的網絡拓撲分析與源流路徑鏈生成算法(流程見圖5)。該算法首先根據生成的有向圖建立送端節點-送電支路鄰接表，然后從每一個源節點開始，以逐層推進的方式進行處理。在每一層，先進行第一輪拓撲分析，利用鄰接表添加相鄰送電支路和相關節點，在生成不完整源流路徑樹后進行第二輪拓撲分析，對當前不完整樹的有向道路集合進行遍歷，獲得新的源流路徑鏈，然后再推進到下一層重復進行兩輪拓撲分析，直到生成該源對應的完整路徑樹。此路徑樹集合包含了電力網絡中所有源、流或源流對之間的路徑鏈的具體構成情況。通過對電力網絡中的所有源逐一進行上述拓撲分析及路徑樹的生成，最終可獲得整個電力網絡全部源流路徑樹集合。

下面將從送端節點-送電支路鄰接表的建立、源流路徑樹的生成和源流路徑鏈的獲取三個方面對該算法進行闡述。

圖5 路徑鏈生成算法流程

2.1 送端節點-送電支路鄰接表的建立

鄰接表形式具有時間復雜度等優點，本文參照鄰接表結構對生成的電力網絡有向圖建立送端節點-送電支路鄰接表，以存儲和表示電力網絡有功潮流分布的拓撲結構關系。

鄰接表以頂點出發的單鏈表的方式存放數據，有向圖的頂點集合V作為鄰接表的送端節點集合。對集合V中的某一元素，例如送端節點vi，其對應的單鏈表存放由節點vi發出的所有送電支路的集合Ui。若某節點無送電支路，此節點可看作送電支路條數為0的送端節點。此外，在形成鄰接表的過程中，還必須考慮母線上既有源(電源)又有流(負荷)的情況，如圖2中的節點1，源1到流1存在源流電氣供求關系。為保證求得的源流路徑鏈能夠包含此種節點源供應就地節點流的特例，可在求取源流路徑鏈時不將節點1上的源流進行合并簡化，而是假設源1經過一條虛擬送電支路與流1發生電氣供求關系。這樣，在最終形成的送端節點-送電支路鄰接表中，就不會遺漏節點源供應就地節點流的特例情形。

根據圖3，可生成圖6的送端節點-送電支路鄰接表。此表考慮了圖1網絡狀態下源1節點功率送出支路的情況，可從中分析電力網絡拓撲關系和所有網絡源流路徑鏈的構成。

圖6 送端節點-送電支路鄰接表

2.2 源流路徑樹的生成

為快速、準確和全面地獲取全網源流路徑鏈集合，需對電力網絡有向圖進行拓撲分析，得到以每一個源為根頂點的全網源流路徑樹集合。本文基于廣度優先搜索的拓撲分析方法，提出利用已建立的送端節點-送電支路鄰接表，對有功潮流分布拓撲關系進行分析，逐層推進，遍歷全網，最終生成全網源流路徑樹集合。

以圖2所示有向圖為例，應用送端節點-送電支路鄰接表得到所有相關聯的送電支路，逐一添加為樹枝，并以每層送電支路的受端節點作為下一層的分枝頂點。如利用圖6所示的鄰接表生成源流路徑樹的具體步驟如圖7所示。

從以上分析過程可知，對電力網絡有向圖進行第一輪拓撲分析，在處理每一層節點時，其鄰接的所有送電支路都會被添加到源流路徑樹中，無需遍歷全網支路，更無需對已形成的路徑進行回溯，從而顯著提高了拓撲分析的效率和準確性。同時，某一源的源流路徑樹集中了從該源出發的所有源流路徑鏈，拓撲關系集中明了，有利于進行第二輪拓撲分析，從而快速準確地獲取相關的源流路徑鏈。

2.3 源流路徑鏈的獲取

在電力網絡有向圖中，一條源流路徑鏈可以抽象為在以對應源為根的源流路徑樹中的一條從根可達對應流的分枝頂點的有向道路，這條道路是其所經過樹枝即送電支路集合的有序構成。由源流路徑樹生成過程可知，同一個流節點在樹中出現的次數常常不止一次，而且流不僅出現在葉頂點上，還出現在分枝頂點上。這是因為在電力網絡中，流可以從不同的路徑鏈汲取某一源送出的電能，這種普遍存在的源流供求特性增加了電力網絡路徑鏈的數量和求取難度。

針對這種特性，需對正在生成的源流路徑樹進行第二輪拓撲分析，并根據樹中流節點的分布，在生成完整源流路徑樹的同時，得到從對應源出發的所有源流路徑鏈，最終求取全網源流路徑鏈集合。

第二輪是在逐層生成某一源節點對應樹的同時對已生成的不完整樹進行逐層遍歷。首先，當第一輪拓撲分析生成樹的第1層時，遍歷從根頂點到第1層的分枝頂點所構成的當前有向道路集合，若某一條有向道路的某端頂點為流節點，則可以由該有向道路生成新的源流路徑鏈，添加到從該源出發的源流路徑鏈集合中。然后，遵照第1層同樣步驟逐層推進，直到完整的源流路徑樹生成為止。此時，所得到的源流路徑鏈集合集中了從該源出發的所有源流路徑鏈。

圖7 基于廣度優先搜索的路徑樹的生成

對圖7所示的各層源流路徑生成樹進行第二輪拓撲分析，逐層生成新的源流路徑鏈，從而得到從源節點1出發的所有源流路徑鏈。需要注意的是，只有流節點(負荷節點)才需要生成路徑鏈，具體步驟如圖8所示。

(a) 步驟1

(b) 步驟2

(c) 步驟3

(d) 步驟4

從以上分析過程可知，在第一輪拓撲分析的基礎上進行第二輪拓撲分析，不僅無需重新遍歷源流路徑樹，不增加算法的時間復雜度，提高了拓撲分析的速度，而且還得以在生成源流路徑樹的同時獲取了源流路徑鏈集合，并保證了電力網絡源流路徑拓撲分析結果的準確和完備。

3 電力網絡源流路徑鏈的局部修改方法

在電力系統實際運行中，電力網絡結構或運行方式不斷變化，導致源流供求關系常常變化，同時也可能引起源流路徑鏈的頻繁變化。在正常運行情況下，這種變化往往是局部的，很少涉及全網，然而現有的采用鄰接矩陣求取源流路徑的方法[1～4]一般不是要重新生成鄰接矩陣，就是要對算法做出較大的修改。

針對此問題，本文提出了一種電力網絡源流路徑鏈的局部修改算法。在生成全網源流路徑鏈集合后，若局部電力網絡發生拓撲或潮流流向變化，該算法首先對鄰接表中對應的支路鏈表進行局部調整，然后，根據鄰接表的變化直接修改源流路徑樹，最后由路徑樹調整得到的有向道路變化，修改部分源流路徑鏈。該算法無需對整個電力網絡進行源流路徑拓撲剖分，只需對全網源流路徑鏈集合做出局部調整即可。

3.1 送端節點-送電支路鄰接表的局部調整

局部電力網絡中的拓撲或潮流分布變化，在拓撲關系上一般表現為某些支路的拓撲或有功潮流方向發生改變。路徑鏈的局部修改算法根據這個特點，在生成全網源流路徑鏈集合后，只需對變化支路的兩端節點在送端節點-送電支路鄰接表中對應的支路鏈表進行局部調整，其他支路鏈表保持不變，而無需重新建立送端節點-送電支路鄰接表。

針對支路拓撲變化或有功潮流變向的不同情況，下面介紹對應的鄰接表調整方法。

(1)對發生支路閉合的情況，即新增支路，設某一條新增的支路(對應有向圖的弧)為au，v，并設有功潮流從u流向v，則u為支路送端節點，v為支路受端節點。對此情況，在送端節點-送電支路鄰接表中，只需將送端節點u的支路鏈表增加這條新增支路au，v即可。

(2)對發生支路開斷的情況，即減少支路，設某一條減少的支路為au，v，并設原有功潮流從u流向v，則u為支路送端節點，v為支路受端節點。對此情況，在送端節點-送電支路鄰接表中，只需從送端節點u的支路鏈表中去除這條支路au，v即可。

(3)若發生有功潮流變向的情況，設某一條變向的支路為au，v，并設原有功潮流從u流向v，則u為支路送端節點，v為支路受端節點，發生變向后，有功潮流從v流向u，則v為支路送端節點，u為支路受端節點。對此情況，在送端節點-送電支路鄰接表中，只需從送端節點u的支路鏈表中去除支路au,v，同時在送端節點v的支路鏈表中增加支路au，v即可。

3.2 源流路徑樹的局部修改

在第一輪拓撲分析過程中，在源流路徑樹上逐層添加送端節點及送電支路時，送端節點-送電支路鄰接表同步記錄與源流路徑樹的關聯，即送電支路鏈表中的每一條送電支路被哪些源流路徑樹共用以及在哪一層被添加到路徑樹中。因此，當某一支路發生拓撲變化或有功潮流變向后，在局部調整鄰接表后，可根據鄰接表中該支路的原有關聯記錄對源流路徑樹進行局部調整，在每一棵相關源流路徑樹中逐層修改有關聯的送端節點和送電支路，而無需再進行第一輪拓撲分析生成整棵源流路徑樹。

3.3 源流路徑鏈的改變

在修改相關源流路徑樹中某一層的樹枝和頂點時，這一層上的有向道路集合會有新增或減少的變化。在對本層產生的源流路徑鏈子集進行修改時，依據有向道路的變化，增加或刪去對應的源流路徑鏈，得到這一層上新的源流路徑鏈子集。

以上過程說明，只需根據相關源流路徑樹中的某些層上修改后的有向道路的變化，就能實現全網源流路徑鏈集合的局部改變，反映電網源流供求關系的變化，而無需再進行第二輪拓撲分析。

4 算例分析

以New England 39節點系統為例進行分析，該系統電力網絡結構與有功潮流分布見文獻[9]。

4.1 電力網絡源流路徑鏈分析

根據第2.1節方法建立送端節點-送電支路鄰接表，限于篇幅，這里只列出一部分計算過程和結果。表1列出了鄰接表中與源32關聯的送端節點及其送電支路鏈表。

表1 與源32關聯的部分送端節點-送電支路鄰接表

然后，按照第2.2節與第2.3節方法，利用送端節點-送電支路鄰接表對電力網絡源流路徑鏈進行分析，從而得到全網源流路徑樹集合與全網源流路徑鏈集合。具體數目如表2所示。圖9為由第一輪拓撲分析得到的從源32出發的源流路徑樹，表3為由第二輪拓撲分析得到的從源32出發的源流路徑鏈集合。

表2 全網拓撲分析結果

圖9 從源32出發的源流路徑樹

表3 從源32出發的源流路徑鏈集合

在本算例中，電力網絡源流路徑鏈生成算法首先運用送端節點-送電支路鄰接表存儲和表示電力網絡有向圖，能夠直接提供第一輪拓撲分析中源32所需的關聯送端節點和鄰接送電支路。然后，由第一輪拓撲分析以生成源流路徑樹的形式獲得從源32出發的源流路徑鏈集合；接著，第二輪拓撲分析過程在第一輪拓撲分析逐層推進的同時，從第一輪拓撲分析得到的各層有向道路集合中獲得新的源流路徑鏈，從而在源流路徑樹生成的同時，得到了從源32出發的源流路徑鏈集合。結果表明，運用該算法獲取源流路徑鏈，具有快速、準確、完備的特點。

4.2 電力網絡源流路徑鏈的局部分析

對于所給系統，將支路(12-13)開斷，使網絡拓撲和潮流分布均發生變化，運用該算法獲取變化的源流路徑鏈。限于篇幅，這里僅列出與源32有關的計算過程和結果。首先修改鄰接表，表4列出了鄰接表在支路開斷后的送電支路的修改及其與從源32出發的源流路徑樹的關聯。

表4 修改后的鄰接表

然后根據表4對從源32出發的源流路徑樹進行局部修改，新的源流路徑樹如圖10所示。最后，修改源流路徑鏈，表5列出了增加的源流路徑鏈，表6列出了減少的源流路徑鏈。

圖10 修改后的源流路徑樹

表5 增加的源流路徑鏈

從以上計算過程可以看出，即使是網絡拓撲和潮流分布均發生變化，也只需要通過本文提出的局部修改算法，對已得到的送端節點-送電支路鄰接表和源流路徑樹進行較少的調整，就能得到變化的源流路徑鏈。算例結果表明，算法縮小了拓撲分析范圍，提高了分析效率，能較好地適應路徑鏈頻繁變化的特點。

表6 減少的源流路徑鏈

5 結語

本文針對電力網絡源流路徑為數眾多、交錯重疊的特點，建立送端節點-送電支路鄰接表存儲和表示電力網絡有向圖，并在此基礎上先進行兩輪拓撲分析，以獲得全網源流路徑鏈集，該方法能夠通過局部修改已生成的鄰接表和路徑樹，獲取變化后的源流路徑鏈。算例結果表明，本文所提方法對求取在電力系統實際運行下的電能傳輸路徑構成問題具有快速、準確、完備、適應性強的特點，為進一步求解電力網絡源流路徑相關問題[10～12]奠定了基礎。

[1] 湯奕, 于繼來, 周蘇荃(Tang Yi, Yu Jilai, Zhou Suquan). 電力網絡源流路徑電氣剖分算法(Electrical dissection algorithm of electric power network)[J]. 電力系統自動化(Automation of Electric Power Systems), 2006, 30(22): 28-33.

[2] 于繼來, 湯奕(Yu Jilai, Tang Yi). 交流支路和節點的聯合電氣剖分(United electrical dissection of AC branch and bus)[J]. 中國電機工程學報(Proceedings of the CSEE), 2007, 27(16): 37-42.

[3] 趙金利, 張群華, 余貽鑫, 等(Zhao Jinli, Zhang Qunhua, Yu Yixin,etal). 輸電網網架結構的譜聚類分析算法(Spectral clustering approach for structure analysis of transmission networks)[J]. 電力系統及其自動化學報(Proceedings of the CSU-EPSA), 2009, 21(4): 8-11,75.

[4] 車仁飛, 白樹忠, 李仁俊(Che Renfei, Bai Shuzhong, Li Renjun). 配電網絡拓撲分析與短路電流計算的實現(Implementation of topology analysis and short circuit calculation for distribution systems)[J]. 電力系統及其自動化學報(Proceedings of the CSU-EPSA), 2002, 14(6): 77-84.

[5] 黃健, 張堯, 李綺雯(Huang Jian, Zhang Yao, Li Qiwen). 蟻群算法在配電網重構的應用(Application of ant colony system in distribution reconfiguration)[J]. 電力系統及其自動化學報(Proceedings of the CSU-EPSA), 2007, 19(4): 59-64.

[6] 宋少群, 朱永利, 于紅(Song Shaoqun, Zhu Yongli, Yu Hong). 基于圖論與人工智能搜索技術的電網拓撲跟蹤方法(A power network topology tracking method based on graph theory and artificial intelligence search technique)[J]. 電網技術(Power System Technology), 2005, 29(19): 45-49.

[7] 王朝瑞. 圖論[M].3版.北京：北京理工大學出版社, 2001.

[8] 殷劍宏, 吳開亞. 圖論及其算法[M]. 合肥：中國科學技術大學出版社, 2003.

[9] 陳彬,于繼來(Chen Bin, Yu Jilai).電力網絡源流路徑鏈的雙向電氣剖分算法(Bidirectional electrical dissecting algorithm for power source and power flow path in power network)[J].電力系統自動化(Automation of Electric Power Systems), 2011, 35(18): 41-46.

[10]邵瑩, 于繼來(Shao Ying, Yu Jilai). 采用源流路徑電氣剖分信息的電網脆弱性評估(Power grid vulnerability assessment based on electrical dissection of the electric network)[J]. 中國電機工程學報(Proceedings of the CSEE), 2009, 29(31): 34-39.

[11]朱濤, 易善軍, 于繼來(Zhu Tao, Yi Shanjun, Yu Jilai). 基于電力網絡源流路徑電氣剖分的聯絡線功率調控方法(Tie-line power regulation method based on electrical dissection for power source and power flow path in power network)[J]. 電網技術(Power System Technology), 2008, 32(11): 24-29,39.

[12]田偉帥, 于繼來(Tian Weishuai, Yu Jilai). 基于電氣剖分的轉運電能損失估算方法(An electrical dissection based approximate method to assess electric energy loss due to power wheeling)[J]. 電網技術(Power System Technology), 2010, 34(3):123-128.

陳 彬(1982-)，男，工學碩士，工程師，研究方向為配電網規劃、配電自動化、配電網運行狀態在線評估、分布式能源在配電網中的應用等。Email:cb_fz@163.com

于繼來(1965-)，男，博士生導師，教授，研究方向為電力系統分析與控制。Email:yupwrs@hit.edu.cn

AlgorithmofPowerNetworkTopologyAnalysisandPathChainsGeneration

CHEN Bin1，2， YU Ji-lai1

(1.Department of Electrical Engineering, Harbin Institute of Technology,Harbin 150001, China;2.Electric Power Research Institute of Fujian Electric Power Company Limited,Fuzhou 350007, China)

For obtaining path chains between sources and flows quickly, a new algorithm, which can analyze power network topology and generate path chains, was proposed in the paper. The algorithm firstly built directed graph and adjacency list between sending buses and sending branches based on the network topology and flow state; and then, it obtained path chain sets from the path chain trees which were generated through two rounds network topology. Getting rid of the adjacency matrix, the proposed algorithm is easier and faster. Moreover, it can change the path chains locally while the topology or the flow state changes in some part of the power network.

electric power network； topology analysis； directed graph； path chain between sources and flows

TM711

A

1003-8930(2012)01-0025-07

2011-10-18；

2011-12-02

國家自然科學基金資助項目(50477008)