基于融合鄰接矩陣的多時(shí)態(tài)局域電網(wǎng)拓?fù)浞治黾夹g(shù)

趙光，臧志斌，李 偉，項(xiàng)衛(wèi)山，龍燕軍

（廈門億力吉奧信息科技有限公司，福建廈門 361001）

電網(wǎng)拓?fù)浞治鍪请娏芾砼c維護(hù)系統(tǒng)中的關(guān)鍵組成部分，對其進(jìn)行深入研究具有重要意義[1-3]。隨著電力系統(tǒng)的發(fā)展，電網(wǎng)規(guī)模也在逐漸擴(kuò)大，傳統(tǒng)的鄰接矩陣分析方法在針對大面積搜索時(shí)，出現(xiàn)了計(jì)算量大幅增加、計(jì)算效率偏低等問題。因此，亟需建立新的拓?fù)浞椒▉砻鎸θ找嫱癸@的矛盾。

針對上述問題，文中以傳統(tǒng)鄰接矩陣為基礎(chǔ)，提出了一種多時(shí)態(tài)局域電網(wǎng)拓?fù)浞治黾夹g(shù)。其基本思想是：在計(jì)算全連通矩陣的過程中同時(shí)采用鄰接和連通矩陣的自乘，且在此過程中用計(jì)算出的新的連通矩陣元素來更新老元素及其對稱位置的元素，以此來提升網(wǎng)絡(luò)拓?fù)涞姆治鲇?jì)算效率，并減少計(jì)算過程中的內(nèi)存占用。

1 矩陣?yán)碚摲治?/h2>

1.1 鄰接矩陣

鄰接矩陣（Adjacency Matrix，AM）是一種在數(shù)據(jù)結(jié)構(gòu)中對“圖”中元素關(guān)系進(jìn)行描述的方法[4-7]。鄰接矩陣中存儲了拓?fù)鋱D內(nèi)所包含的邊或弧的信息，這類信息能夠較為直觀地反映出圖中相鄰節(jié)點(diǎn)之間的連接關(guān)系。

假設(shè)圖G包含n個(gè)節(jié)點(diǎn)，且節(jié)點(diǎn)間的邊沒有方向，則稱該圖為無向圖，而其所對應(yīng)的鄰接矩陣M為n×n階方陣。對于文中所研究的電網(wǎng)網(wǎng)絡(luò)結(jié)構(gòu)而言，其就可以被視為一張無向圖，因此文中理論分析也主要集中在無向圖中。在無向圖中，當(dāng)兩個(gè)節(jié)點(diǎn)之間存在邊或弧時(shí)，所構(gòu)建的鄰接矩陣對應(yīng)位置元素為1，反之則為0。值得注意的是，鄰接矩陣主對角線位置元素的值代表了節(jié)點(diǎn)本身的自連接情況，在文中統(tǒng)一設(shè)置為1。圖1 為一個(gè)六節(jié)點(diǎn)電網(wǎng)拓?fù)鋵?yīng)的無向圖。

圖1 六節(jié)點(diǎn)電網(wǎng)拓?fù)錈o向圖

圖1 對應(yīng)的鄰接矩陣如下所示：

由鄰接矩陣的定義與示意圖可以看出，無向圖對應(yīng)的鄰接矩陣有兩個(gè)特點(diǎn)：1）鄰接矩陣為對稱方陣，即矩陣行與列數(shù)目相同且關(guān)于主對角線對稱；2）該矩陣主對角線上的元素相同，在不同文獻(xiàn)中會根據(jù)不同需求設(shè)置最優(yōu)值，常見的值包括0、1 和∞等。

鄰接矩陣進(jìn)行網(wǎng)絡(luò)拓?fù)涞膬?yōu)勢在于能夠清晰、直觀地表示出其中網(wǎng)絡(luò)相鄰節(jié)點(diǎn)的連接信息。然而在節(jié)點(diǎn)增加的同時(shí)，該矩陣所需的存儲空間也會進(jìn)一步提高，這便導(dǎo)致在搜索面積較大時(shí)會造成計(jì)算量的大幅增加。

1.2 全連通矩陣

鄰接矩陣代表了網(wǎng)絡(luò)相鄰節(jié)點(diǎn)的連接關(guān)系，也被視為網(wǎng)絡(luò)的第一層連通關(guān)系。在對網(wǎng)絡(luò)拓?fù)鋱D的實(shí)際分析中，通常需要獲取到網(wǎng)絡(luò)任意兩個(gè)節(jié)點(diǎn)之間的連通狀態(tài)，而不僅局限于相鄰兩個(gè)節(jié)點(diǎn)。而全連通矩陣就是代表任意兩節(jié)點(diǎn)之間連通關(guān)系的矩陣。與鄰接矩陣相似，對于包含n個(gè)節(jié)點(diǎn)的無向圖而言，其所對應(yīng)的全連通矩陣T也為n×n階方陣，且主對角線設(shè)置為1，同時(shí)該矩陣也關(guān)于主對角線對稱。不同點(diǎn)在于矩陣中各元素的取值，全連通矩陣中各元素的值可以判斷對應(yīng)兩個(gè)節(jié)點(diǎn)間是否至少存在一條通路，若通路存在，則元素取值為1，反之為0。對于圖2 的八節(jié)點(diǎn)電網(wǎng)網(wǎng)絡(luò)拓?fù)鋱D，其所對應(yīng)的矩陣為：

圖2 八節(jié)點(diǎn)電網(wǎng)拓?fù)錈o向圖

實(shí)際上，無向圖的全連通矩陣可以由鄰接矩陣計(jì)算而來，兩者之間的數(shù)學(xué)關(guān)系可描述為：

通過對全連通矩陣進(jìn)行分析，可以得到電網(wǎng)中所存在的連通塊，常用的方法有行比較法與行掃描法兩種。

2 電網(wǎng)拓?fù)浞治?/h2>

2.1 電網(wǎng)拓?fù)湫枨蠓治?/h3>

對電網(wǎng)進(jìn)行拓?fù)浞治龅闹饕康脑谟诮Y(jié)合時(shí)間戳等信息，為其提供融入開關(guān)歷史狀態(tài)的拓?fù)浞治瞿芰Γ⑼ㄟ^對停電范圍、連通性分析、電源點(diǎn)追溯、拓?fù)錂z測和供電半徑等拓?fù)湎嚓P(guān)服務(wù)接口進(jìn)行功能擴(kuò)展，以實(shí)現(xiàn)基于開關(guān)歷史狀態(tài)的時(shí)態(tài)拓?fù)浞治瞿芰8-12]。其本質(zhì)上就是將電網(wǎng)中的節(jié)點(diǎn)/開關(guān)模型描述為母線/支路模型。

在電網(wǎng)的拓?fù)浞治鲋校妇€是指利用閉合開關(guān)相連接的節(jié)點(diǎn)集合。需要注意的是，開關(guān)的狀態(tài)并不會影響靜態(tài)的節(jié)點(diǎn)，但會影響母線[13-16]。電網(wǎng)拓?fù)浞治鲋饕妇€分析與電氣島分析兩個(gè)步驟：

1）母線分析：指利用閉合開關(guān)將相連的節(jié)點(diǎn)轉(zhuǎn)換為母線，并對其進(jìn)行編號，進(jìn)而形成唯一的母線號，且循環(huán)上述過程直至所有節(jié)點(diǎn)均與母線相關(guān)聯(lián)為止。

2）電氣島分析：該步驟建立在母線分析的基礎(chǔ)上，將支路相互連通的母線整合為一個(gè)電氣島。電氣島通常分為活島和死島兩種類型，區(qū)別在于是否包含電源與負(fù)荷，兩者都包含的電氣島稱之為“活島”，反之則稱為“死島”。

2.2 傳統(tǒng)鄰接矩陣分析

利用傳統(tǒng)鄰接矩陣可以進(jìn)行局域電網(wǎng)拓?fù)渲械哪妇€與電氣島分析，其分析過程主要由鄰接矩陣構(gòu)建、全連通矩陣計(jì)算以及母線/電氣島分析所組成，具體流程如圖3 所示。

圖3 傳統(tǒng)鄰接矩陣拓?fù)浞治隽鞒?/p>

利用傳統(tǒng)鄰接矩陣對電網(wǎng)拓?fù)渲械哪妇€進(jìn)行分析時(shí)，需要首先將電網(wǎng)模型抽象為便于處理的映射圖。在母線分析中，研究對象為電網(wǎng)內(nèi)部同一電壓等級內(nèi)的開關(guān)閉合狀態(tài)與兩側(cè)端點(diǎn)組成的網(wǎng)絡(luò)。映射方法為：將母線所研究網(wǎng)絡(luò)中的端點(diǎn)化作映射圖中的節(jié)點(diǎn)，節(jié)點(diǎn)之間是否存在邊的連接取決于網(wǎng)絡(luò)中的開關(guān)狀態(tài)。若兩端點(diǎn)之間存在閉合的開關(guān)，則對應(yīng)映射圖中的兩節(jié)點(diǎn)存在邊；反之，映射圖中兩節(jié)點(diǎn)不直接連接。將所研究網(wǎng)絡(luò)抽象到映射圖后，就可以構(gòu)建出對應(yīng)的鄰接矩陣，然后通過式（3）對該矩陣進(jìn)行n-1 次自乘，計(jì)算得出相應(yīng)的全連通矩陣；再通過歸于同一連通塊的節(jié)點(diǎn)構(gòu)成母線的規(guī)則進(jìn)行全連通矩陣分析，實(shí)現(xiàn)母線劃分。

然后進(jìn)行電氣島的分析，該分析過程與上述母線分析過程類似，不同之處在于電氣島分析的對象為輸入的局域電網(wǎng)，同樣需要將電網(wǎng)抽象為映射圖。具體過程可描述為：在母線分析完成的基礎(chǔ)上，將母線映射為映射圖節(jié)點(diǎn)，母線對應(yīng)節(jié)點(diǎn)之間是否存在邊主要取決于母線之間是否存在支路。若存在支路，則映射圖節(jié)點(diǎn)之間存在連接邊；否則，兩節(jié)點(diǎn)之間不存在邊相互連接。

2.3 融合鄰接矩陣分析

采用傳統(tǒng)鄰接矩陣法對電網(wǎng)進(jìn)行拓?fù)浞治鰰r(shí)，若電網(wǎng)規(guī)模較小，則拓?fù)浞治隹梢匀〉昧己玫男Ч５S著規(guī)模的擴(kuò)大，生成全連通矩陣所需進(jìn)行的n-1 次自乘會使得計(jì)算量大幅提高，分析耗時(shí)也會隨之顯著增加，從而難以滿足多時(shí)態(tài)電網(wǎng)的實(shí)時(shí)拓?fù)浞治鲂枨蟆榇耍闹刑岢隽艘环N融合鄰接矩陣分析算法，對傳統(tǒng)鄰接矩陣分析存在的問題進(jìn)行優(yōu)化。

融合鄰接矩陣的核心思想是：在計(jì)算全連通矩陣的過程中引入準(zhǔn)平方的思想，即僅在第一步采用鄰接矩陣的自乘，其余均通過鄰接矩陣得到連通矩陣的自乘，以形成所謂的“準(zhǔn)平方”。同時(shí)，在該過程中每計(jì)算出一個(gè)新的連通矩陣元素，就使用該新元素更新老元素及其對稱位置元素的值，進(jìn)而在提高網(wǎng)絡(luò)拓?fù)浞治鲇?jì)算效率的同時(shí)，減少了計(jì)算過程中的內(nèi)存占用。

利用準(zhǔn)平方思想對鄰接矩陣獲取全連通矩陣過程的優(yōu)化主要體現(xiàn)為：

式中，T代表連通矩陣，k為連通矩陣的級數(shù)，且當(dāng)k=1 時(shí)，則T(1)就代表原始鄰接矩陣M。

利用上式進(jìn)行全連通矩陣的計(jì)算，至多需要進(jìn)行l(wèi)og2(n-1)次矩陣計(jì)算，計(jì)算量顯著降低。

對于連通矩陣的節(jié)點(diǎn)更新，由于該矩陣描述的是拓?fù)鋱D節(jié)點(diǎn)之間的連通情況，在實(shí)際工程應(yīng)用中并不需要過于關(guān)注兩個(gè)節(jié)點(diǎn)為多少級連通，而僅需考慮是否連通。所以在計(jì)算全連通矩陣的過程中，每計(jì)算出一個(gè)元素，就可以用其去更新老元素，同時(shí)因?yàn)檫B通矩陣的對稱性，在更新老元素時(shí)，也可將對稱位置元素的值一并更新。這樣做不僅能將兩個(gè)節(jié)點(diǎn)的連通情況快速反映在矩陣中，還能夠進(jìn)一步提高算法的運(yùn)行效率。求取某階連通矩陣各元素的計(jì)算公式為：

式中，tij為連通矩陣T中的某一元素，n為矩陣維度。

3 實(shí)驗(yàn)與分析

為了驗(yàn)證文中所提基于融合鄰接矩陣的多時(shí)態(tài)局域電網(wǎng)拓?fù)浞治黾夹g(shù)的可行性與可靠性，與國內(nèi)某電力公司合作進(jìn)行了驗(yàn)證實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)環(huán)境

在實(shí)驗(yàn)開始前，利用VC++搭建了一套如圖4 所示的實(shí)驗(yàn)環(huán)境。該環(huán)境中除了關(guān)鍵的母線與電氣島分析模塊外，還增加了數(shù)據(jù)庫模塊以及人機(jī)交互模塊等。其中，數(shù)據(jù)庫模塊負(fù)責(zé)存儲局域電網(wǎng)中所有電氣元件的數(shù)據(jù)，人機(jī)交互模塊則可為操作人員提供可視化界面，操作人員通過該界面除了可以進(jìn)行元件運(yùn)行數(shù)據(jù)的查詢外，還能實(shí)現(xiàn)開關(guān)控制，并進(jìn)行電網(wǎng)元件的增加、修改與刪除等操作。

圖4 實(shí)驗(yàn)環(huán)境示意圖

需要注意的是，模塊一屬于電網(wǎng)拓?fù)涮幚淼撵o態(tài)部分，包含有電網(wǎng)各元件之間的實(shí)際連接關(guān)系，且開關(guān)狀態(tài)也只會影響對應(yīng)的開關(guān)數(shù)據(jù)；而模塊二則是電網(wǎng)拓?fù)涮幚淼膭?dòng)態(tài)部分，其數(shù)據(jù)變化時(shí)刻受到開關(guān)狀態(tài)的影響。

3.2 實(shí)驗(yàn)分析

為了體現(xiàn)文中算法的優(yōu)勢，此次設(shè)置了基于傳統(tǒng)鄰接矩陣分析法(算法1)和基于節(jié)點(diǎn)相消鄰接矩陣優(yōu)化法(算法2)作為對照組進(jìn)行實(shí)驗(yàn)。對比實(shí)驗(yàn)內(nèi)容包括電氣島矩陣乘法次數(shù)比較實(shí)驗(yàn)與拓?fù)浞治龊臅r(shí)實(shí)驗(yàn)。同時(shí)考慮到電網(wǎng)節(jié)點(diǎn)編號對實(shí)驗(yàn)結(jié)果的影響，還特別設(shè)置一組節(jié)點(diǎn)編號測試實(shí)驗(yàn)，以此進(jìn)一步挖掘文中算法的特性。

1）電氣島矩陣乘法次數(shù)比較實(shí)驗(yàn)

該實(shí)驗(yàn)是統(tǒng)計(jì)若干種算法在進(jìn)行電網(wǎng)電氣島分析時(shí)矩陣乘法的計(jì)算次數(shù)，計(jì)算次數(shù)越大，則速度越慢，算法性能也就越差，實(shí)驗(yàn)結(jié)果如表1 所示。

表1 電氣島矩陣乘法次數(shù)實(shí)驗(yàn)結(jié)果

由表1 結(jié)果可以看出，采用文中算法進(jìn)行電氣島分析時(shí)，矩陣乘法的計(jì)算次數(shù)明顯少于其他兩種算法，體現(xiàn)了該算法的優(yōu)勢。

2）拓?fù)浞治龊臅r(shí)實(shí)驗(yàn)

該項(xiàng)實(shí)驗(yàn)主要統(tǒng)計(jì)各類算法進(jìn)行母線與電氣島分析的耗時(shí)，以此體現(xiàn)算法的處理效率，實(shí)驗(yàn)結(jié)果如表2 所示。

表2 拓?fù)浞治龊臅r(shí)實(shí)驗(yàn)結(jié)果

由上述結(jié)果可以看出，文中算法的單項(xiàng)耗時(shí)與總耗時(shí)均為最短，充分體現(xiàn)了算法性能的優(yōu)越性。

3）節(jié)點(diǎn)編號測試實(shí)驗(yàn)

為了測試節(jié)點(diǎn)編號對文中算法性能的影響，設(shè)計(jì)了以下實(shí)驗(yàn)。實(shí)驗(yàn)分為兩組：按出線數(shù)由大到小的節(jié)點(diǎn)編號（編組1）和按出線數(shù)由小到大的節(jié)點(diǎn)編號（編組2），測試了兩組實(shí)驗(yàn)的拓?fù)浞治龊臅r(shí)情況，結(jié)果如表3 所示。

表3 節(jié)點(diǎn)編組測試實(shí)驗(yàn)結(jié)果

由該項(xiàng)實(shí)驗(yàn)結(jié)果可以看出，不同的節(jié)點(diǎn)編組方式對文中算法的運(yùn)行速度有較大的影響，且按出線數(shù)由大到小進(jìn)行節(jié)點(diǎn)編組的方式優(yōu)于從小到大的方式。因此在算法的后續(xù)使用中，也應(yīng)當(dāng)采用前一種節(jié)點(diǎn)編組方式來進(jìn)行。

4 結(jié)束語

文中在分析鄰接矩陣與全連通矩陣?yán)碚摰幕A(chǔ)上，提出了一種基于融合鄰接矩陣的多時(shí)態(tài)局域電網(wǎng)拓?fù)浞治黾夹g(shù)。該技術(shù)在傳統(tǒng)鄰接矩陣的基礎(chǔ)上，引入了準(zhǔn)平方及實(shí)時(shí)元素更新的思想，使得算法能夠在充分發(fā)揮鄰接矩陣進(jìn)行電網(wǎng)拓?fù)浞治鰞?yōu)勢的同時(shí)，減少其存在的問題。實(shí)驗(yàn)結(jié)果驗(yàn)證了文中算法的有效性，并體現(xiàn)了算法的良好性能。