聶 萌, 李喜同, 陳波濤,王 磊,吳翠娟（．國(guó)網(wǎng)菏澤供電公司，山東菏澤,74000；．山東安信源信息技術(shù)有限公司，山東濟(jì)南,5000）

?

基于圖論的電力網(wǎng)絡(luò)快速拓?fù)浞治黾巴負(fù)鋶u建立的新方法研究

聶 萌1, 李喜同1, 陳波濤1,王 磊1,吳翠娟2
（1．國(guó)網(wǎng)菏澤供電公司，山東菏澤,274000；2．山東安信源信息技術(shù)有限公司，山東濟(jì)南,250100）

摘要：本文通過(guò)對(duì)電力網(wǎng)絡(luò)拓?fù)浼巴負(fù)鋶u的研究分析，提出了一種基于圖論的電力網(wǎng)絡(luò)快速拓?fù)浞治黾巴負(fù)鋶u建立的新方法，本方法利用圖論識(shí)別分析方法，對(duì)電力系統(tǒng)進(jìn)行拓?fù)浞治觯C合考慮廣度、深度優(yōu)先搜索算法的優(yōu)缺點(diǎn)，充分利用深度優(yōu)先對(duì)環(huán)路網(wǎng)絡(luò)的搜索優(yōu)勢(shì)，采用遍歷算法，實(shí)現(xiàn)了電力網(wǎng)絡(luò)快速拓?fù)浞治黾巴負(fù)鋶u的建立。

關(guān)鍵詞：圖論；網(wǎng)絡(luò)拓?fù)浞治?；拓?fù)鋶u；遍歷；回溯

0　引言

電力系統(tǒng)的運(yùn)行和發(fā)展導(dǎo)致電力網(wǎng)絡(luò)的規(guī)模越來(lái)越大，電力系統(tǒng)拓?fù)浞治鲈陔娋W(wǎng)運(yùn)行控制和分析計(jì)算中起著至關(guān)重要的作用，網(wǎng)絡(luò)拓?fù)浞治鰹闋顟B(tài)估計(jì)、潮流計(jì)算等電力系統(tǒng)分析軟件高級(jí)應(yīng)用提供基礎(chǔ)網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)，同時(shí)智能電網(wǎng)系統(tǒng)實(shí)時(shí)、超實(shí)時(shí)仿真系統(tǒng)要求電力系統(tǒng)拓?fù)浞治鼋Y(jié)果越來(lái)越精確，速度越來(lái)越快。這都給電力系統(tǒng)拓?fù)浞治龅臏?zhǔn)確性，快速性提出了更高的要求。在各種拓?fù)浔孀R(shí)算法中，采用最廣泛的是搜索算法，包括廣度、深度優(yōu)先搜索算法以及各種變形，但是這些算法在實(shí)際使用過(guò)程中，需要完全占用CPU時(shí)間，并且速度達(dá)不到理想的需要。

本文提出一種基于圖論的快速拓?fù)浞治鏊惴?，綜合考慮廣度、深度優(yōu)先搜索算法的優(yōu)缺點(diǎn)，有效的規(guī)避了廣度優(yōu)先搜索對(duì)于環(huán)路較多網(wǎng)絡(luò)情況沒(méi)有回溯過(guò)程的缺點(diǎn)，同時(shí)充分利用深度優(yōu)先對(duì)環(huán)路網(wǎng)絡(luò)的搜優(yōu)勢(shì)索，可以節(jié)省大量的CPU時(shí)間，大大提高拓?fù)浞治鏊俣取?/p>

1　圖論拓?fù)浔孀R(shí)分析描述

電力系統(tǒng)是由各種電氣元件通過(guò)線路或變壓器連接在一起的整體，在研究電力網(wǎng)絡(luò)拓?fù)潢P(guān)系時(shí)，可將整個(gè)電力系統(tǒng)抽象成一個(gè)圖。圖是抽象支路和節(jié)點(diǎn)的集合，它反映圖中所包含的各支路之間的聯(lián)結(jié)關(guān)系。且圖論方法在網(wǎng)絡(luò)拓?fù)浞治錾蠎?yīng)用較廣，特別適用于解決電力網(wǎng)絡(luò)拓?fù)浞治鱿嚓P(guān)問(wèn)題。

圖論中圖的頂點(diǎn)可以表示具體事物，圖的邊則表示事物之間的聯(lián)系。如果一條邊的兩個(gè)端點(diǎn)為同一個(gè)頂點(diǎn)，這條邊就稱(chēng)為自環(huán)。如果一對(duì)頂點(diǎn)間有兩條以上的邊相連，則稱(chēng)這些邊為平行邊。將圖論的方法應(yīng)用在電力網(wǎng)絡(luò)拓?fù)浞治鲋?，電氣元件的連接點(diǎn)可映射為圖的頂點(diǎn)，閉合的開(kāi)關(guān)(刀閘)、線路和變壓器等電氣元件可映射為圖的邊。那么在進(jìn)行電力網(wǎng)絡(luò)拓?fù)浞治鰰r(shí)，可直接將開(kāi)關(guān)、刀閘等無(wú)阻抗類(lèi)電氣元件兩端連接點(diǎn)歸并為一個(gè)拓?fù)潼c(diǎn)；將線路、變壓器和電抗器等阻抗類(lèi)電氣元件的拓?fù)潼c(diǎn)歸結(jié)到一個(gè)拓?fù)鋶u。采用該方法可以省去廠站識(shí)別過(guò)程，并且將各阻抗支路的識(shí)別過(guò)程進(jìn)行統(tǒng)一，程序?qū)崿F(xiàn)簡(jiǎn)單。

2　基于圖論的拓?fù)浞治?/h2>

本文將圖論的觀點(diǎn)應(yīng)用到電力網(wǎng)絡(luò)拓?fù)浞治鲋?，首先通過(guò)遍歷開(kāi)關(guān)、刀閘等無(wú)阻抗類(lèi)電氣元件連接點(diǎn)并建立連接點(diǎn)關(guān)系，基于連接點(diǎn)關(guān)系生成相應(yīng)拓?fù)潼c(diǎn)，然后通過(guò)遍歷線路變壓器等阻抗類(lèi)電氣元件拓?fù)潼c(diǎn)，建立拓?fù)潼c(diǎn)關(guān)系并生成拓?fù)鋶u，實(shí)現(xiàn)基于圖論的電力網(wǎng)絡(luò)快速拓?fù)浞治黾巴負(fù)鋶u建立。

2.1電氣連接點(diǎn)關(guān)系建立

連接點(diǎn)關(guān)系的建立，以線路及變壓器為邊界，遍歷電網(wǎng)連接點(diǎn)，根據(jù)開(kāi)關(guān)及刀閘的開(kāi)合狀態(tài)判斷連接點(diǎn)的連接關(guān)系。

假如，電網(wǎng)中共有連接點(diǎn)數(shù)量為n,建立數(shù)組容器ConnNode[n+1] 用于存儲(chǔ)連接點(diǎn)關(guān)系。具體步驟如下：

1、初始化容器ConnNode，清空容器所存數(shù)據(jù)；

2、依次遍歷n個(gè)連接點(diǎn)ConnNode[i] ；

3、找到連接點(diǎn)i所連接的所有開(kāi)關(guān)及刀閘；

4、遍歷所有開(kāi)關(guān)及刀閘。如果開(kāi)關(guān)或刀閘斷開(kāi)，則跳過(guò)；如果閉合，則記錄開(kāi)關(guān)或刀閘另一側(cè)的連接點(diǎn)到容器ConnNode[i] ；

5、判斷連接點(diǎn)是否遍歷完畢，如果沒(méi)有，則取下一個(gè)連接點(diǎn)i=i+1，轉(zhuǎn)到3；如果遍歷完畢，則結(jié)束。

經(jīng)過(guò)如上步驟，則連接點(diǎn)關(guān)系全部存儲(chǔ)到容器ConnNode中。

2.2基于連接點(diǎn)關(guān)系的拓?fù)潼c(diǎn)生成

在已經(jīng)獲得的連接點(diǎn)關(guān)系的基礎(chǔ)上，可以直接通過(guò)擴(kuò)充鄰接節(jié)點(diǎn)的方式生成拓?fù)潼c(diǎn)。

仍然以圖1為例，在生成的連接點(diǎn)關(guān)系容器ConnNode基礎(chǔ)上，遍歷ConnNode容器。由ConnNode[1] = {4,5}，可知連接點(diǎn){1,4，5}在同一個(gè)拓?fù)潼c(diǎn)，然后查找連接點(diǎn){4,5}相連的新連接點(diǎn)，找到ConnNode[4] = {1}；ConnNode[5] = {1}。即沒(méi)有新的連接點(diǎn)，一個(gè)拓?fù)潼c(diǎn)生成完畢，此拓?fù)潼c(diǎn)包含的連接點(diǎn)為{1,4,5}，同樣可以生成其他的拓?fù)潼c(diǎn){2,3,6}。至此，拓?fù)潼c(diǎn)生成完畢。

2.3拓?fù)潼c(diǎn)關(guān)系建立，拓?fù)鋶u生成

拓?fù)潼c(diǎn)關(guān)系的建立與連接點(diǎn)關(guān)系的建立類(lèi)似，只是不以開(kāi)關(guān)刀閘的狀態(tài)來(lái)判斷拓?fù)潼c(diǎn)的連接關(guān)系，而是以線路及變壓器的連接來(lái)判斷。

假如，共有拓?fù)潼c(diǎn)數(shù)量為n，建立數(shù)組容器TopoNode[n+1] 用于存儲(chǔ)拓?fù)潼c(diǎn)的連接關(guān)系。具體步驟如下：

1、初始化TopoNode容器，清空所有存儲(chǔ)數(shù)據(jù)；2、依次遍歷n個(gè)拓?fù)潼c(diǎn)TopoNode[i] ；

3、找到拓?fù)潼c(diǎn)i所連接的所有線路及變壓器；

4、遍歷找到的所有線路及變壓器。記錄其另一側(cè)的拓?fù)潼c(diǎn)到容器TopoNode [i] ；

5、判斷拓?fù)潼c(diǎn)是否遍歷完畢，如果沒(méi)有，則取下一個(gè)拓?fù)潼c(diǎn)i=i+1，轉(zhuǎn)到3；如果遍歷完畢，則結(jié)束。

拓?fù)鋶u的生成在拓?fù)潼c(diǎn)連接關(guān)系的基礎(chǔ)上，通過(guò)擴(kuò)充鄰接拓?fù)潼c(diǎn)的方式可以獲取整個(gè)拓?fù)鋶u。

3　算例分析

電網(wǎng)輸電網(wǎng)絡(luò)是一大型輸電電網(wǎng)，根據(jù)本文的拓?fù)浞治龇椒ǖ贸鼍W(wǎng)絡(luò)中包含2630個(gè)拓?fù)鋶u（包含很多孤島）， 3711個(gè)節(jié)點(diǎn)。本文優(yōu)化的拓?fù)溆?jì)算方法與傳統(tǒng)算法的計(jì)算時(shí)間見(jiàn)表1，從表中可以看出利用本文優(yōu)化的算法大大縮短了計(jì)算的時(shí)間。

表1　集中拓?fù)浞治龇椒ū容^

4　總結(jié)

本文提出的一種基于圖論的電力網(wǎng)絡(luò)快速拓?fù)浞治黾巴負(fù)鋶u建立的新方法，能夠?qū)D論的觀點(diǎn)應(yīng)用到電力網(wǎng)絡(luò)拓?fù)浞治鲋?，綜合廣度、深度優(yōu)先搜索算法的優(yōu)缺點(diǎn)。利用遍歷算法，遍歷開(kāi)關(guān)、刀閘等無(wú)阻抗類(lèi)電氣元件連接點(diǎn)并建立連接點(diǎn)關(guān)系，基于連接點(diǎn)關(guān)系生成相應(yīng)拓?fù)潼c(diǎn)，遍歷線路變壓器等阻抗類(lèi)電氣元件拓?fù)潼c(diǎn)，建立拓?fù)潼c(diǎn)關(guān)系，基于拓?fù)潼c(diǎn)關(guān)系生成拓?fù)鋶u，實(shí)現(xiàn)了電力網(wǎng)絡(luò)快速拓?fù)浞治黾巴負(fù)鋶u建立。且使用該方法的電力網(wǎng)絡(luò)拓?fù)浞治鼋Y(jié)果在精準(zhǔn)及速度上都優(yōu)先于其他方法，滿(mǎn)足了電力系統(tǒng)分析軟件對(duì)電力系統(tǒng)拓?fù)浞治鼋Y(jié)果越來(lái)越精確，速度越來(lái)越快的要求。

參考文獻(xiàn)

[1] 孫慶. 基于圖形數(shù)據(jù)庫(kù)的電力網(wǎng)絡(luò)拓?fù)涞姆椒ǖ难芯颗c應(yīng)用[D] ；南京，南京理工大學(xué)，2008，碩士論文

[2] 劉振亞. 智能電網(wǎng)技術(shù)[M] ；北京，中國(guó)經(jīng)濟(jì)出版社，2010：190-201

[3] 宋少群，朱永利，于紅. 基于圖論與人工智能搜索技術(shù)的電網(wǎng)拓?fù)涓櫡椒╗J] ；電網(wǎng)技術(shù)，2005,25（19）：45-49

[4] 宋艷爭(zhēng). 基于圖論搜索的快速網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)識(shí)別方法的研究[D] ；北京，華北電力大學(xué)，2009，碩士論文

[5] 徐俊明. 圖論及其應(yīng)用[M] ；合肥，中國(guó)科學(xué)技術(shù)大學(xué)出版社，2004

[6] 林濟(jì)鏗,覃嶺,羅萍萍. 基于圖形建模的電力系統(tǒng)拓?fù)浞治鲂路椒╗J] . 電力系統(tǒng)自動(dòng)化. 2005(22)

[7] 陳星鶯,孫恕堅(jiān),錢(qián)鋒. 一種基于追蹤技術(shù)的快速電力網(wǎng)拓?fù)浞治龇椒╗J] . 電網(wǎng)技術(shù). 2004(05)

[8] 胡繼芳,王寧. IEC61970與新一代EMS數(shù)據(jù)庫(kù)管理系統(tǒng)[J] .電力系統(tǒng)自動(dòng)化. 2000(24)

[9] 姚玉斌,王丹,吳志良,徐維克. 方程求解法網(wǎng)絡(luò)拓?fù)浞治鯷J] .電力自動(dòng)化設(shè)備. 2010(01)

[10] 蔡麗娟,張建成. 面向?qū)ο蠹夹g(shù)的電力網(wǎng)絡(luò)拓?fù)浞治鯷J] . 電氣時(shí)代. 2004(04)

[11] 龍啟峰,陳崗,丁曉群,丁穎,馬春生,黃文英. 基于面向?qū)ο蠹夹g(shù)的電力網(wǎng)絡(luò)拓?fù)浞治鲂路椒╗J] . 電力系統(tǒng)及[] 其自動(dòng)化學(xué)報(bào). 2005(01)

[12] 姚玉斌,宣儉,于娜,王丹,吳志良. 連通矩陣準(zhǔn)平方法網(wǎng)絡(luò)拓?fù)浞治鯷J] . 電力系統(tǒng)保護(hù)與控制. 2011(05)

Based on graph theory of electric power network topology analysis and topology island quickly set up a new method of research

Nie Meng1,Li Xitong1,Chen Botao1,Wang Lei2,Wu Cuijuan2
(1.State Grid Heze Electric Power Company,Heze of shandong province,250012 2.Shandong AnXinYuan Information Technology co.,LTD.,jinan of shandong province,250100)

Abstract：In this paper,based on the research of the power network topology and topological island analysis,this paper proposes a power network fast topology analysis based on graph theory and topological island to establish a new method,the method using the identification method of graph theory,topology analysis of power system,considering the advantages and disadvantages of breadth,depth first search algorithm,make full use of the depth first search advantage of loop network,using calendar calculation method,realized the power network topology analysis and the establishment of the topological island quickly.

Keywords：graph theory;network topology analysis;topological island;traverse;back trace