基于圖譜的交互電網(wǎng)臨界點(diǎn)搜索算法

2015-12-25 05:35:59劉春

上海電力大學(xué)學(xué)報(bào) 2015年4期

劉春

(上海電力學(xué)院電氣工程學(xué)院, 上海200090)

摘要:構(gòu)建了符合當(dāng)前交互電網(wǎng)實(shí)際的模型及連鎖故障機(jī)制,并提出了一種基于圖譜的算法來搜索對(duì)網(wǎng)絡(luò)安全影響最大的臨界點(diǎn),對(duì)這些臨界點(diǎn)加以重點(diǎn)保護(hù)可以有效地提高網(wǎng)絡(luò)魯棒性.該算法以代數(shù)連通性來評(píng)估故障后網(wǎng)絡(luò)連通性,不需要搜索最大連通分量,仿真結(jié)果證明其在執(zhí)行效率和速度方面有較為明顯的優(yōu)勢.

關(guān)鍵詞：交互電網(wǎng); 圖譜; 代數(shù)連通性; 臨界點(diǎn)

收稿日期：2014-09-24

作者簡介：通訊劉春(1982-),女,碩士,講師,湖北孝感人.主要研究方向?yàn)殡娏ο到y(tǒng)信息化處理.E-mail:liuchun@shiep.edu.cn.

中圖分類號(hào)：TM711;TM715文獻(xiàn)標(biāo)志碼： A

收稿日期：2014-09-24

作者簡介：通訊高亮(1960-),男,教授,山西太原人.主要研究方向?yàn)殡娏ο到y(tǒng)繼電保護(hù)、智能化變電站技術(shù).

ResearchonCriticalPointSearchAlgorithmofInteractiveGridBasedonMapSpectrum

LIUChun

(School of Electrical Engineering,Shanghai University of Electric Power, Shanghai200090, China)

Abstract:The topology of interdependent power grid is modeled,with more real world characters taken into account,as well as the propagating mechanism of cascading failures.An efficient algorithm is also proposed based on Graph Spectrum Theory,for detecting the critical nodes of interdependent power grid,which is the first step of protection.In this approach,the robustness of leftover power grid after cascading failure is evaluated in the metric of algebraic connectivity,instead of giant connected component,whose searching procedure takes much running time.The experimental results highlight the advantage of this approach in speed.

Keywords:interdependentpowergrid;graphspectrum;algebraicconnectivity;criticalnodes

隨著信息科學(xué)的發(fā)展,越來越多的大型人造網(wǎng)絡(luò)傾向于彼此耦合、信息交互,典型的例子有電力網(wǎng)、社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)與通信網(wǎng)的交互.這種交互固然提高了這些大型人造網(wǎng)絡(luò)的智能化水平,但也存在一些不可忽視的負(fù)面效應(yīng).已有的研究結(jié)果表明，在面對(duì)隨機(jī)攻擊和蓄意攻擊時(shí)，交互網(wǎng)絡(luò)比單個(gè)網(wǎng)絡(luò)表現(xiàn)得更加脆弱,因此近年來引起了廣泛的關(guān)注.文獻(xiàn)[1]至文獻(xiàn)[7]對(duì)交互網(wǎng)絡(luò)和單個(gè)網(wǎng)絡(luò)的魯棒性均有涉及,得出的共同結(jié)論是交互網(wǎng)絡(luò)比單個(gè)網(wǎng)絡(luò)更加脆弱.這是因?yàn)樵诎l(fā)生連鎖故障時(shí),故障并不僅僅在單個(gè)耦合網(wǎng)絡(luò)中傳播,還通過這兩個(gè)網(wǎng)絡(luò)的交互引起反饋效應(yīng),使得故障影響的范圍更廣.文獻(xiàn)[3]從滲流的角度分析了交互性對(duì)于網(wǎng)絡(luò)相變的影響,結(jié)果表明,在單個(gè)網(wǎng)絡(luò)中發(fā)生的是連續(xù)的二階相變,而在交互網(wǎng)絡(luò)中發(fā)生的是不連續(xù)的一階相變,這對(duì)網(wǎng)絡(luò)的保護(hù)十分不利.文獻(xiàn)[4]進(jìn)一步指出,要使得交互網(wǎng)絡(luò)的相變由一階退化為二階,應(yīng)減小兩個(gè)網(wǎng)絡(luò)間的耦合程度.文獻(xiàn)[1]和文獻(xiàn)[5]分別對(duì)交互網(wǎng)絡(luò)在面對(duì)隨機(jī)和蓄意攻擊時(shí)的魯棒性進(jìn)行了分析,認(rèn)為交互網(wǎng)絡(luò)在兩種攻擊下都會(huì)比單個(gè)網(wǎng)絡(luò)顯得更脆弱.上述文獻(xiàn)都是基于通用的網(wǎng)絡(luò)模型,并無特別針對(duì)某種實(shí)際的網(wǎng)絡(luò),得出的結(jié)論也較有一般性；通常采用無標(biāo)度模型來建模,用于評(píng)估脆弱度或者魯棒性的參數(shù)也基本為度、中心度等通用的參數(shù),不帶有具體網(wǎng)絡(luò)的特征，因此應(yīng)用到具體的網(wǎng)絡(luò)中時(shí),與實(shí)際情況存在一定的差距.文獻(xiàn)[6]針對(duì)的是電網(wǎng)和通信網(wǎng)組成的交互網(wǎng)絡(luò),提出了在交互電網(wǎng)中確定臨界節(jié)點(diǎn)的兩種算法.所謂的臨界節(jié)點(diǎn)指的是其失效會(huì)對(duì)整個(gè)網(wǎng)絡(luò)造成最大損失的節(jié)點(diǎn).很顯然，在網(wǎng)絡(luò)的設(shè)計(jì)階段就應(yīng)該對(duì)于這些臨界節(jié)點(diǎn)予以重點(diǎn)保護(hù).文獻(xiàn)[7]仍然采用的是無標(biāo)度網(wǎng)絡(luò)模型,但是電網(wǎng)和通信網(wǎng)所取的冪律分布指數(shù)β分別在2.5~4和2.2~2.6之間,符合實(shí)際電網(wǎng)和Internet網(wǎng)絡(luò)的特性.

確定臨界節(jié)點(diǎn)是提高網(wǎng)絡(luò)魯棒性的第一步,本文的設(shè)計(jì)目標(biāo)也在此.但是對(duì)于在此過程中如何計(jì)算網(wǎng)絡(luò)的損失,本文采用了不同的角度.一般認(rèn)為，網(wǎng)絡(luò)的損失是丟失了最多的連通節(jié)點(diǎn),因此在計(jì)算網(wǎng)絡(luò)損失時(shí)必須統(tǒng)計(jì)故障后網(wǎng)絡(luò)剩余最大連通分量的長度，這就需要復(fù)雜的搜索算法,在網(wǎng)絡(luò)規(guī)模較大時(shí)尤為困難.本文采用了代數(shù)連通性來取代最大連通分量長度去衡量剩余網(wǎng)絡(luò)的魯棒性，代數(shù)連通性已被證明可以直接反應(yīng)網(wǎng)絡(luò)的拓?fù)涮匦?而且計(jì)算復(fù)雜度低于搜索最大連通分量.仿真結(jié)果表明，該方法可以提高算法的效率.

1代數(shù)連通性

設(shè)有無向圖G(V,E)有N個(gè)頂點(diǎn),頂點(diǎn)集為V,邊集為E,鄰接矩陣為A.節(jié)點(diǎn)i的度表示為deg(i),將所有節(jié)點(diǎn)的度寫成一個(gè)對(duì)角陣D,則稱D為G的度矩陣.圖G的拉普拉斯矩陣L(G)定義為:

(1)

也可寫成:

(2)

可見L為半正定對(duì)稱陣,因此其所有特征值非負(fù).L的所有特征值的集合即稱為圖G的拉普拉斯譜.將L的所有特征值按從小到大的順序排列為0=λ1(G)≤λ2(G)≤λ3(G)…≤λN(G),其中λ2(G)稱為圖G的代數(shù)連通性,該特征值對(duì)應(yīng)的特征向量定義為費(fèi)德勒向量(FieldVector).[9]

代數(shù)連通性λ2(G)也稱為譜隙(SpectralGap),反應(yīng)了網(wǎng)絡(luò)中節(jié)點(diǎn)連接的緊密程度.當(dāng)λ2(G)→0時(shí)網(wǎng)絡(luò)趨于不連通,而當(dāng)ελ2(G)→1時(shí)網(wǎng)絡(luò)趨于全連通.這里的ε是與網(wǎng)絡(luò)規(guī)模相關(guān)的正則化常數(shù).著名的Courant-Fisher定理給出了λ2(G)的解法為:

(3)

式(3)中0=(0,0,…,0)T和1=(1,1,…,1)T為λ1(G)=0對(duì)應(yīng)的特征值.[10]

圖1給出了兩個(gè)節(jié)點(diǎn)數(shù)和度分布完全相同的圖,但是直觀可以看出圖1a比圖1b的連接要弱.計(jì)算得出這兩個(gè)圖的代數(shù)連通性分別為0.438 4和1.000 0,與直觀觀察的結(jié)果相符.這是一個(gè)簡單的例子,現(xiàn)有文獻(xiàn)已經(jīng)證明代數(shù)連通性不僅直接反映系統(tǒng)的魯棒性,還與一些重要的圖變量有關(guān),[10-14]在此不再贅述.此外,代數(shù)連通性的計(jì)算可歸結(jié)為特征值求解或二次規(guī)劃問題,求解相對(duì)容易,尤其是在網(wǎng)絡(luò)規(guī)模較大時(shí),其速度優(yōu)勢更為明顯.

圖1　代數(shù)連通性與魯棒性的關(guān)系

(4)

2網(wǎng)絡(luò)模型

為了更接近實(shí)際的電力網(wǎng)與通信網(wǎng),本文電力網(wǎng)的模型采用IEEE-BUS系統(tǒng),通信網(wǎng)仍采用Internet網(wǎng)絡(luò)常用的無標(biāo)度模型.

根據(jù)文獻(xiàn)[3]和文獻(xiàn)[4]的結(jié)論,交互網(wǎng)絡(luò)的耦合不應(yīng)太強(qiáng),但耦合閾值的大小并無定論.此外,遵循兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的度正相關(guān)的策略進(jìn)行耦合可以提高魯棒性.因此,本文采用的耦合策略是部分耦合,首先計(jì)算兩個(gè)網(wǎng)絡(luò)中各節(jié)點(diǎn)的度并進(jìn)行排序,然后取度排序前50%的節(jié)點(diǎn)按排序產(chǎn)生一條耦合邊.這里的耦合邊在物理上對(duì)應(yīng)信息流和供電線路,也就是說,電力網(wǎng)中的節(jié)點(diǎn)通過耦合邊從通信節(jié)點(diǎn)獲取信息,同時(shí)向通信節(jié)點(diǎn)供電,當(dāng)電力節(jié)點(diǎn)失效時(shí),通信節(jié)點(diǎn)必然失效,反之則不然.這樣的設(shè)置符合當(dāng)前的實(shí)際情況.

在上述策略下生成交互網(wǎng)絡(luò)Γ(Gs,Gc,Esc),其中，Gs為電力網(wǎng)，Gs=(Vs,Es);Gc為通信網(wǎng)，Gc=(Vc,Ec);Esc為二者的耦合邊,即Esc={(u,v)|u∈Vs,v∈Vc}(其中u和v分別為Gs和Gc中的節(jié)點(diǎn)).

在連鎖故障機(jī)制方面,大部分文獻(xiàn)是假設(shè)交互網(wǎng)絡(luò)中的某一個(gè)網(wǎng)絡(luò)在節(jié)點(diǎn)失效時(shí),與之相連的本網(wǎng)節(jié)點(diǎn)以及耦合節(jié)點(diǎn)均失效.而實(shí)際電網(wǎng)及耦合通信網(wǎng)絡(luò)中的情況與此不同.連鎖故障首先是由電網(wǎng)中的節(jié)點(diǎn)失效引起的,但電網(wǎng)中節(jié)點(diǎn)失效的直接后果是全網(wǎng)的潮流重新分配,并不一定導(dǎo)致其鄰居節(jié)點(diǎn)失效.參照電網(wǎng)連鎖故障的經(jīng)典CASCADE模型的做法并不失一般性,本文假設(shè)Gs中某個(gè)節(jié)點(diǎn)失效的條件是其鄰居節(jié)點(diǎn)中失效的比例超過某一個(gè)閾值,Gc中節(jié)點(diǎn)失效的條件是其鄰居節(jié)點(diǎn)失效或耦合節(jié)點(diǎn)失效.

3GS-AN算法

建立交互網(wǎng)絡(luò)Γ(Gs,Gc,Esc)后,尋找其臨界點(diǎn)的問題可以重新描述為:

(6)

為了提高計(jì)算效率,考慮所求得的解u*必然是Gs中的關(guān)節(jié)節(jié)點(diǎn),[6]而不必在所有節(jié)點(diǎn)中搜索.所謂關(guān)節(jié)節(jié)點(diǎn)是指其本身失效會(huì)增加網(wǎng)絡(luò)連通子圖數(shù)目的節(jié)點(diǎn).根據(jù)文獻(xiàn)[8],圖G的連通子圖數(shù)目可以由拉普拉斯矩陣L的最小特征值λ1(G)=0的重?cái)?shù)Nλ1(G)求得.因此,僅考慮單個(gè)網(wǎng)絡(luò)時(shí),圖G的關(guān)節(jié)節(jié)點(diǎn)集合AC可表示為:

(7)

而在交互網(wǎng)絡(luò)中,由自身或耦合節(jié)點(diǎn)失效而引起連通子圖數(shù)目增加的節(jié)點(diǎn)都可以認(rèn)為是關(guān)節(jié)節(jié)點(diǎn).由于篇幅所限,具體算法不在本文中討論.根據(jù)式(7)求得的Gs和Gc中關(guān)節(jié)節(jié)點(diǎn)的集合分別為ACs和ACc,其流程如圖2所示.

圖2　 GS- AN算法流程

需要說明的是,GS-AN算法中用已失效點(diǎn)的鄰居節(jié)點(diǎn)是否滿足其鄰居節(jié)點(diǎn)失效比例大于閾值1/3作為故障繼續(xù)傳播的判據(jù),但這并非是惟一選擇.根據(jù)實(shí)際情況也可選用其他的判據(jù),而不影響到算法的主體性能.引發(fā)故障的初始節(jié)點(diǎn)可以有多個(gè),仍可以采用與GS-AN算法中類似的故障傳播機(jī)制.

4仿真結(jié)果

仿真實(shí)驗(yàn)中網(wǎng)絡(luò)模型的Gs分別采用節(jié)點(diǎn)數(shù)目為30,57,118,300的IEEE BUS系統(tǒng),Gc采用與Gs點(diǎn)數(shù)相同的無標(biāo)度模型,冪律指數(shù)β取2.2,先將兩個(gè)網(wǎng)絡(luò)中的節(jié)點(diǎn)按度排序,前50%的節(jié)點(diǎn)按序產(chǎn)生一條耦合邊.表1給出了IEEEBUS系統(tǒng)的代數(shù)連通性.[10]

表1　 IEEE BUS系統(tǒng)的代數(shù)連通性

圖3為不同節(jié)點(diǎn)數(shù)目下4個(gè)系統(tǒng)的性能比較.由圖3可知，較少的節(jié)點(diǎn)系統(tǒng)其λ2有較快的收斂速度,這是因?yàn)?00-BUS系統(tǒng)本身的λ2已經(jīng)很小,而其節(jié)點(diǎn)和邊的數(shù)目又是最多的,因此其故障傳播速度最慢,故其λ2下降速度不明顯.但最后的收斂點(diǎn)4個(gè)系統(tǒng)并無太大差別,這說明同樣數(shù)目的臨界節(jié)點(diǎn)失效在300-BUS系統(tǒng)中會(huì)引起更嚴(yán)重的后果,由此證明300-BUS系統(tǒng)的魯棒性最差,這與它具有最小的λ2是一致的.這一結(jié)論也提示我們,電網(wǎng)規(guī)模并不是越大越好,越大的電網(wǎng)可能越脆弱.

圖3　不同節(jié)點(diǎn)數(shù)目下的算法性能

圖4比較了3種算法的執(zhí)行速度.由圖4可以看出，本文提出的GS-AN算法更有優(yōu)勢,與設(shè)計(jì)算法時(shí)的預(yù)測相符.此外,3種算法有一個(gè)共同的趨勢,就是在故障的前半程λ2的下降速度相對(duì)較慢,而后半程則相對(duì)較快.這是因?yàn)榍鞍氤瘫群蟀氤痰氖Ｓ喙?jié)點(diǎn)多,鄰接矩陣、拉普拉斯矩陣都具有相對(duì)較大的維數(shù),因此計(jì)算的速度要慢一些.仿真結(jié)果表明，GS-AN算法在執(zhí)行效率和速度上均有優(yōu)勢,因此該算法用于動(dòng)態(tài)規(guī)劃也成為一種可能.

圖4　3種算法的執(zhí)行速度比較

5結(jié)語

在現(xiàn)有文獻(xiàn)關(guān)于無標(biāo)度交互網(wǎng)絡(luò)模型研究的基礎(chǔ)上,本文構(gòu)建了與通信網(wǎng)耦合的交互電力網(wǎng)模型,并參照當(dāng)前電網(wǎng)的實(shí)際運(yùn)行情況設(shè)計(jì)了連鎖故障傳播機(jī)制,提出了一種基于圖譜的算法來尋找交互電力網(wǎng)中的臨界節(jié)點(diǎn),為電網(wǎng)的安全保護(hù)提供有效的建議.與傳統(tǒng)算法中需要復(fù)雜的程序來搜索最大連通分量不同,該算法以連鎖故障后的代數(shù)連通性來評(píng)估剩余網(wǎng)絡(luò)的魯棒性,而代數(shù)連通性的求解可歸結(jié)為特征值計(jì)算或二次規(guī)劃問題,因此該算法能夠以較高的效率和較快的速度尋找到對(duì)網(wǎng)絡(luò)魯棒性影響最大的前k個(gè)臨界節(jié)點(diǎn).仿真結(jié)果證明了這一優(yōu)勢,由此可見該種算法還有用于動(dòng)態(tài)規(guī)劃的潛力.

除了代數(shù)連通性以外,圖譜的特征值可以從更多的角度反映圖的動(dòng)態(tài)和靜態(tài)特征,這將是下一步的研究方向.而對(duì)于已找到的臨界點(diǎn),如何對(duì)其加強(qiáng)保護(hù)來提高魯棒性同時(shí)又能保證其功能性,也是一個(gè)很有意義的研究課題.

參考文獻(xiàn)：

[1]BU8LDYREVSV,PARSHANIR,PAULG,et al.Catastrophiccascadeoffailuresininterdependentnetworks[J].Nature,2010(7291):1 025-1 028.

[2]GAOJ,BULDYREVSV,STANLEYHE,et al.Networksformedfrominterdependentnetworks[J].NaturePhys.,2011,8(1):40-48.

PARSHANIR,PAULG,et al.Catastrophiccascadeoffailuresininterdependentnetworks[J].Nature,2010(7291):1 025-1 028.

[2]GAOJ,BULDYREVSV,STANLEYHE,et al.Networksformedfrominterdependentnetworks[J].NaturePhys.,2011,8(1):40-48.

[3]PARSHANIR,BULDYREVSV,HAVLINS.Interdependentnetworks:reducingthecouplingstrengthleadstoachangefromafirsttosecondorderpercolationtransition[J].Phys.Rev.Lett.,2010,105(4):048701.

[4]SCHNEIDERCM,ARAUJONAM,HAVLINS,et al.Towardsdesigningrobustcouplednetworks[R].ScientificReports3,2013:1-7.

[5]HUANGX,GaoJ,BULDYREVSV,et al.Robustnessofinterdependentnetworksundertargetedattack[J].Phys.Rev.E,2011,83:065101(R).

[6]DUNGTNguyen,SHENYilin,MYTThai.Detectingcriticalnodesininterdependentpowernetworksforvulnerabilityassessment[J].IEEETrans.OnSmartGrid,2013,4(1):151-159.

[7]CHARLESDBrummitt,RAISSAMD’Souzab,LEICHTEA.Suppressingcascadesofloadininterdependentnetworks[C].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatedofAmerica,2012(12):680-689.

[8]XIELe,CHOIDae-Hyun,KARSoummya,et al.Fullydistributedstateestimationforwide-areamonitoringSystems[J].IEEETrans.OnSmartGrid,2012,3(3):1 154-1 169.

[9]SYDNEYA,SCOGLIOC,GRUENBACHERD.Theimpactofoptimizingalgebraicconnectivityinhierarchicalcommunicationnetworksfortransmissionoperationsinsmartgrids[C]∥InnovativeSmartGridTechnologies(ISGT),IEEEPES,2013,1(6):24-27.

[10]CHOPADEP,BIKDASHM.AnalyzingsmartpowergridandSCADAnetworkrobustnessusingthenodedegreedistributionandalgebraicconnectivityundervulnerabilityandWMDattacks[C]∥HomelandSecurity(HST),IEEEConferenceonTechnologies,2012:13-15.

[11]UniversityofWashington.Powersystemstestcasearchive[EB/OL].[2014-09-15].http:∥www.ee.washington.edu/research/pstca.

[12]FIELDERM.Algebraicconnectivityofgraphs[J].CzechoslovakMath,1973,98(23):298-305.

[13]BIYIKOGLU,TURKER,LEYDOLD,et al.LaplacianEigenvectorsofGraphs[M].Berlin:Springer,2007:15-26.

[14]JAMAKOVICA,UHLIGS.Influenceofthenetworkstructureonrobustness[C]∥15thIEEEInternationalConferenceonNetworking,2007:278-283.

BULDYREVSV,HAVLINS.Interdependentnetworks:reducingthecouplingstrengthleadstoachangefromafirsttosecondorderpercolationtransition[J].Phys.Rev.Lett.,2010,105(4):048701.