基于深度優(yōu)先遍歷算法的配電網(wǎng)拓撲動態(tài)檢測

胡 榮,未召弟,符 楊

(上海電力學院電力與自動化工程學院,上海 200090)

配電系統(tǒng)自動分析是配電管理系統(tǒng)(DMS)的重要功能,其主要內(nèi)容包括配電網(wǎng)的拓撲分析、潮流計算、可靠性計算、結(jié)構(gòu)優(yōu)化或網(wǎng)絡(luò)重構(gòu)、故障定位隔離與恢復等.網(wǎng)絡(luò)拓撲分析功能解決配電網(wǎng)電氣拓撲的建模問題,是其他高級功能的基礎(chǔ)［1,2］.在進行結(jié)構(gòu)優(yōu)化、網(wǎng)絡(luò)重構(gòu)、故障恢復操作時,各種開關(guān)狀態(tài)組合會產(chǎn)生多種拓撲結(jié)構(gòu),不僅會出現(xiàn)孤島,而且可能出現(xiàn)環(huán)路.因此,需對兩種情形進行判斷,確保生成配電網(wǎng)輻射狀網(wǎng)架,以尋找滿足目標函數(shù)最優(yōu)的網(wǎng)架結(jié)構(gòu).根據(jù)圖論概念,將配電網(wǎng)拓撲結(jié)構(gòu)視為無向圖.目前多數(shù)文獻［3-5］采用鄰接表來存儲無向圖,物理模型不夠直觀,文獻［6］采用矩陣染色法對拓撲結(jié)構(gòu)僅作連通性分析.本文采用鄰接矩陣存儲方法和深度優(yōu)先遍歷算法,動態(tài)檢測網(wǎng)絡(luò)拓撲模型.

1 配電網(wǎng)絡(luò)拓撲結(jié)構(gòu)的對象描述

1.1 配電網(wǎng)絡(luò)拓撲結(jié)構(gòu)的數(shù)學模型

建立實用模型,實現(xiàn)圖模一體化,是網(wǎng)絡(luò)拓撲分析功能的關(guān)鍵.配電網(wǎng)絡(luò)拓撲結(jié)構(gòu)類似于一種數(shù)據(jù)結(jié)構(gòu)——圖.根據(jù)有關(guān)圖論知識,配電系統(tǒng)拓撲結(jié)構(gòu)圖可表示為:

式中:V—— 包括電源、負荷側(cè)配變在內(nèi)的 n個節(jié)點的非空集;

D—— 邊的集合(配電網(wǎng)饋線集合).

如圖 1所示,當兩節(jié)點的連接不涉及方向關(guān)系時,圖為無向圖,配電網(wǎng)絡(luò)拓撲圖為無向圖.當兩節(jié)點之間存在邊(有連接關(guān)系)時,兩節(jié)點互為鄰接點,對應(yīng)邊用(V1,V2)表示.對于無向圖,若每對節(jié)點之間都有路徑直接或間接相通,則該圖為連通圖.因此,無向圖 1為連通圖.

圖1 圖狀結(jié)構(gòu)G

從邏輯結(jié)構(gòu)看,圖是一種非線性結(jié)構(gòu),任意兩個節(jié)點都可能存在關(guān)系,因而圖的存儲方法也有很多.本文采用更直觀形象的鄰接矩陣存儲方法,利用網(wǎng)基結(jié)構(gòu)矩陣 Dn×n作為鄰接矩陣來描述配電網(wǎng)拓撲結(jié)構(gòu),以及取決于配電線路的架設(shè)、線路開關(guān)的狀態(tài)和網(wǎng)絡(luò)運行方式的配電網(wǎng)的潛在連接方式［7］.若圖 1代表某一小型配電系統(tǒng),則其網(wǎng)基結(jié)構(gòu)矩陣為:

在配電分析系統(tǒng)中,配電網(wǎng)拓撲結(jié)構(gòu)信息經(jīng)DSCADA系統(tǒng)實時采集并傳遞給 GIS動態(tài)生成,其網(wǎng)基結(jié)構(gòu)矩陣 Dn×n隨拓撲結(jié)構(gòu)的變化而動態(tài)變化,因此需要快速有效的算法進行動態(tài)檢測,實現(xiàn)結(jié)構(gòu)優(yōu)化、故障定位和隔離,以及供電快速恢復等高級功能.

1.2 配電系統(tǒng)拓撲結(jié)構(gòu)中的孤點和環(huán)路

配電系統(tǒng)多為環(huán)網(wǎng)設(shè)計,開環(huán)運行.每個用戶終端原則上必須備有雙側(cè)電源,一側(cè)電源在正常運行方式下對負荷供電,另一側(cè)作為緊急備用電源.配電網(wǎng)的這種設(shè)計及運行方式?jīng)Q定了配電網(wǎng)拓撲結(jié)構(gòu)圖中除源節(jié)點之外的每個節(jié)點都有且只有一個父鄰接點.若配電網(wǎng)絡(luò)不連通,即某節(jié)點沒有父鄰接點,意味著此負荷點沒有電源供電,稱之為孤島;若某節(jié)點有兩個或兩個以上父鄰接點,說明此負荷節(jié)點有多個電源,稱之為環(huán)路.

配電網(wǎng)環(huán)路有 2類［8］:一是 2個電源節(jié)點之間形成的環(huán)路,即從配電網(wǎng)的一個電源節(jié)點出發(fā),每個節(jié)點只經(jīng)過一次,到達本電源點或另一個電源節(jié)點的環(huán);二是負荷節(jié)點之間形成的環(huán)路,即從配電網(wǎng)的某一個節(jié)點出發(fā),每個節(jié)點只經(jīng)過一次,又回到這個節(jié)點的環(huán).配電網(wǎng)正常運行拓撲結(jié)構(gòu)中一般不允許出現(xiàn)孤島及環(huán)路.

文獻［6］對配網(wǎng)拓撲結(jié)構(gòu)作出連通性判斷,但未對環(huán)路作出分析.本文將基于圖狀配電網(wǎng)拓撲結(jié)構(gòu),采用高效算法實現(xiàn)配電網(wǎng)拓撲結(jié)構(gòu)的孤島和環(huán)路的動態(tài)檢測功能.

2 DFS算法在配電網(wǎng)拓撲結(jié)構(gòu)動態(tài)檢測中的應(yīng)用

為盡快找到最優(yōu)目標函數(shù)(網(wǎng)損最小、可靠性最高等)的網(wǎng)絡(luò)結(jié)構(gòu),需淘汰拓撲結(jié)構(gòu)不正常的網(wǎng)架結(jié)構(gòu).深度優(yōu)先遍歷算法(DFS)是一種人工智能算法,能夠自動尋優(yōu).其優(yōu)點是占內(nèi)存較少,通常情況下可不必完全遍歷即能找到最優(yōu)方案或接近方案,以節(jié)省計算時間,提高計算效率.

2.1 DFS算法原理

DFS算法進行遍歷的過程是從某個頂點出發(fā),沿著某條搜索路徑對圖中每個節(jié)點各做一次且僅做一次訪問［9］.原理如下:設(shè) x是當前被訪問節(jié)點,對 x做過訪問標記后,選擇一條從 x出發(fā)的未檢測過的邊(x,y).若發(fā)現(xiàn)節(jié)點 y已訪問過,則重新選擇另一條從 x出發(fā)的未檢測過的邊,否則沿邊(x,y)到達未曾訪問過的 y,對 y訪問并將其標記;從 y開始搜索,直到搜索完從 y出發(fā)的所有路徑,即訪問完 y所有子節(jié)點之后,才回溯到節(jié)點x,再選擇一條從 x出發(fā)的未檢測過的邊.上述過程直至從 x出發(fā)的所有邊都已檢測過為止.此時,若 x不是源點,則回溯到 x的父節(jié)點,直至圖中所有和源點有路徑相通的節(jié)點(即源點的所有子節(jié)點)都已被訪問過.若圖 1是連通圖,則遍歷過程結(jié)束,否則繼續(xù)選擇一個尚未被訪問的節(jié)點作為新源點,進行新的搜索過程.

2.2 配電網(wǎng)拓撲結(jié)構(gòu)動態(tài)檢測的機理分析

電源點是配電網(wǎng)潮流首端,因此從電源點開始逐個遍歷,進行標記,依次遍歷其鄰接點.若遍歷中搜索到其他電源點,或某負荷節(jié)點被訪問 2次,即可判斷拓撲結(jié)構(gòu)中存在環(huán)路;若遍歷過程結(jié)束,仍有某負荷節(jié)點不曾被訪問,則此負荷點為電源孤立節(jié)點;若遍歷結(jié)束后未發(fā)現(xiàn)孤點或環(huán)路,說明配電網(wǎng)拓撲結(jié)構(gòu)為正常運行的輻射、開式網(wǎng)狀.

為使 DFS算法能夠快速高效檢測動態(tài)網(wǎng)絡(luò)拓撲結(jié)構(gòu),設(shè)置數(shù)組 visited［0,1,…,n-1］及環(huán)路判斷向量 path如下.

(1)數(shù)組 visited［0,1,…,n-1］的設(shè)置 由于圖中任一節(jié)點都可能與其他節(jié)點鄰接,在訪問了某節(jié)點之后,可能順著某條回路再次回到該節(jié)點.為了避免重復訪問同一個節(jié)點,必須標記每個已訪問的節(jié)點.為此,可設(shè)一數(shù)組 visited［0,1,…,n-1］,visited［i］的初值為 0,一旦訪問了節(jié)點 i之后,將其置為 1.

(2)環(huán)路判斷向量 path的設(shè)置 向量path記錄已訪問過且有可能產(chǎn)生環(huán)路的點,path［i］的值隨程序的進行會不斷變化,其原則是:訪問到某點后即將其放入 path中,若判斷完該點所有鄰接節(jié)點且沒有回路時,將該點從 path中刪除.

(3)動態(tài)檢測配電網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖的主要步驟 具體步驟如下.

第 1步 首先選取某個電源節(jié)點作為當前節(jié)點 i(1≤i≤n),把 visited［i］置為 1,表示該點已被訪問,并將 i放入堆棧 path中.

第 2步 從 0～N中依次取當前點 i的各級鄰接點 j,如果 j為另一電源點則說明存在一類環(huán)路;如果 j已被訪問過且 j不是當前節(jié)點 i的父節(jié)點,則說明存在二類環(huán)路;如果出現(xiàn)以上兩種情況中的一種,則程序記下環(huán)路,然后逐層退出遞歸,反之則把 j作為當前節(jié)點重新進行深度優(yōu)先遍歷.如果 j≥N則說明當前節(jié)點的所有連通節(jié)點已被處理完,此時把當前節(jié)點 i點從 path中移除,返回遞歸上一層.

第 3步 若上述判斷未發(fā)現(xiàn)環(huán)路,取出下一個電源點重復第 2步.

第 4步 判斷完所有電源點后,由所有的visited［i］統(tǒng)計從來沒有被訪問過的節(jié)點,若有,標記所有孤點,否則該拓撲結(jié)構(gòu)一切正常.配電網(wǎng)絡(luò)拓撲結(jié)構(gòu)的動態(tài)檢測流程見圖 2.

圖2 配電網(wǎng)絡(luò)拓撲結(jié)構(gòu)的動態(tài)檢測流程

根據(jù)流程圖編寫程序?qū)ε潆娋W(wǎng)絡(luò)拓撲結(jié)構(gòu)進行動態(tài)監(jiān)測,可以剔除存在孤島和環(huán)路的結(jié)構(gòu),以進一步提高配電網(wǎng)網(wǎng)絡(luò)重構(gòu)、故障恢復,以及尋找網(wǎng)損最小、可靠性最高的網(wǎng)架結(jié)構(gòu)的效率,并將檢驗結(jié)果以可視化界面給出,將核心算法封裝為模塊供高級功能調(diào)用,從而進一步提高計算效率.

3 算例應(yīng)用

在配電網(wǎng) GIS能夠直接讀取 DSCADA中的實時數(shù)據(jù)的前提下,只有配電網(wǎng)自動分析系統(tǒng)能夠辨識正常與非正常動態(tài)網(wǎng)絡(luò)結(jié)構(gòu),進行潮流計算、網(wǎng)架結(jié)構(gòu)優(yōu)化、可靠性計算,才有現(xiàn)實意義,才能構(gòu)建強大的配電網(wǎng)系統(tǒng).

本文采用鄰接矩陣的形式表示配電網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖,深度優(yōu)先搜索(DFS)算法進行圖的遍歷和搜索,編寫了“配電網(wǎng)拓撲結(jié)構(gòu)動態(tài)檢測”程序.為增強直觀可視性,利用 VC++6.0編程工具,實現(xiàn)了友好的人機交互界面,并將核心算法封裝為獨立模塊,以便潮流計算、網(wǎng)絡(luò)優(yōu)化或重構(gòu)等高級功能軟件的調(diào)用.圖 3為典型的復雜配電網(wǎng)［10］,此網(wǎng)架結(jié)構(gòu)中有 4個電源節(jié)點 S1,S2,S3,S4,50個負荷節(jié)點(1～50),實線表示原始線路,虛線表示可運行的線路.

圖3 典型的復雜配電網(wǎng)

分別對其各種非正常拓撲結(jié)構(gòu)進行動態(tài)檢測,如圖 4所示.界面中給出了各種配電網(wǎng)拓撲結(jié)構(gòu)的檢測信息,對部分故障的負荷節(jié)點進行標記(方框顯示).

由圖 4a中的“檢測信息”可知,此復雜配電網(wǎng)中負荷節(jié)點 38為孤點,即無電源對其進行供電.由圖 4b中的“檢測信息”可知,此配電網(wǎng)結(jié)構(gòu)中負荷節(jié)點 11,12,45,44,38,32,39,33,34,35,36為雙向電源供電,構(gòu)成了一類環(huán)路.圖 4c給出了二類環(huán)路的非正常拓撲結(jié)構(gòu),由“檢測信息”可知,11,12,45,44,38,15,14顯示均由電源 S2供電.

圖4 非正常拓撲結(jié)構(gòu)

為了驗證程序的運行效率,采用文獻［10］至文獻［12］的算例給出的網(wǎng)架結(jié)構(gòu)進行計算速度測算和正確率檢驗.對 3個算例可能出現(xiàn)的各種孤島和環(huán)路情況進行的 600次試驗表明,程序平均計算時間小于 1 ms,正確率達 100%,見表 1.

表1 程序運算效率驗證結(jié)果

由表 1可知,程序計算速度及穩(wěn)定可靠性均達到較高水平,完全可以高效地為配網(wǎng)重構(gòu)、故障恢復提供可信賴的網(wǎng)絡(luò)拓撲結(jié)構(gòu),檢驗結(jié)果驗證了涉及的思想、采用的方法的合理性與優(yōu)越性.

4 結(jié)束語

本文利用圖狀結(jié)構(gòu)進行配電網(wǎng)絡(luò)拓撲建模,采用深度優(yōu)先遍歷算法進行快速動態(tài)檢測,編程采用 VC++6.0軟件,建立了圖形用戶界面;將程序封裝為模塊,便于網(wǎng)絡(luò)重構(gòu)或故障恢復等高級功能軟件的調(diào)用.通過算例演示及軟件測試,驗證了軟件的正確性與優(yōu)越性.

［1］顧秀芳,關(guān)長余.配電網(wǎng)潮流計算的拓撲分析研究［J］.華北電力大學學報,2008,35(2):47-50.

［2］張宏,郭宗仁.基于節(jié)點—— 支路關(guān)聯(lián)矩陣的配電網(wǎng)饋線故障區(qū)域定位算法［J］.電力自動化設(shè)備,2004,24(1):27-29.

［3］馬志剛,基于遺傳模擬退火算法的配電網(wǎng)重構(gòu)研究［D］.南昌大學,2006.

［4］邱生,張焰.用鄰接表保存中壓配電網(wǎng)拓撲結(jié)構(gòu)［J］.電力自動化設(shè)備,2005,3(3):57-59.

［5］王林川,潘文明,梁棟,等.一種基于鄰接矩陣的算法在配電網(wǎng)重構(gòu)中應(yīng)用［C］∥電力系統(tǒng)與自動化專業(yè)第 24屆學術(shù)年會論文集,2008:367-369.

［6］崔巖.鄰接矩陣染色法及其在電力系統(tǒng)網(wǎng)絡(luò)拓撲分析中的應(yīng)用［J］.電力系統(tǒng)保護與控制,2008,36(16):52-56.

［7］劉健,畢鵬翔,楊文宇,等.配電網(wǎng)理論及應(yīng)用［M］.北京:中國水利水電出版社,2007:7-12.

［8］楊建軍,戰(zhàn)紅,劉揚.基于環(huán)路和改進遺傳算法的配電網(wǎng)絡(luò)重構(gòu)優(yōu)化［J］.高電壓技術(shù),2007,33(5):109-113.

［9］SAHNISartaj.Data structures,algorithms,and applications in C++［M］.Beijing:China Machine Press,2004:98-105.

［10］VLADIMIRO,MIRANDA,RANITO JV,etal.Genetic algorithms in optimalmultistage distribution network planning［J］.IEEE Trans on Power Systems,1994,9(4):1 927-1 933.

［11］MORADI Adel,FOTUHI-FIRUZABAD M.Optimal switch placement in distribution systems using trinary partic le swarm optim ization algorithm［J］.Trans.on Power Delivery,2008,23(1):271-279.

［12］W ATANABE Isamu,NODU Makoto.A genetic algorithm for optim izing switching sequence of service restoration in distribution systems［C］∥Proceedings of the 2004 Congress on Evolutionary Computation,2004:1683-1690.