大型船舶電力系統快速拓撲分析新方法

張靈杰，孫建波，郭 晨

(1. 大連海事大學 輪機工程學院，遼寧 大連 116026；2. 大連海事大學 信息科學技術學院，遼寧 大連 116026)

大型船舶電力系統快速拓撲分析新方法

張靈杰1，孫建波1，郭 晨2

(1. 大連海事大學 輪機工程學院，遼寧 大連 116026；2. 大連海事大學 信息科學技術學院，遼寧 大連 116026)

為應對現代船舶朝著大型化、自動化發展的同時對船舶電力系統網絡拓撲監控能力提出的更高要求，本文提出一種大型船舶電力系統快速拓撲分析的新方法。首先，利用圖論拓撲信息數據模式將船舶電網拓撲信息錄入系統；其次，遍歷初始網絡拓撲形成母線，基于獨島搜索策略形成電氣島，完成靜態分析并生成拓撲信息數據庫；最后，利用節點標記法對受影響的母線進行連通性分析，并結合獨島搜索策略，實現船舶電力系統拓撲結構的動態更新。對某現代化大型集裝箱船舶電力系統進行驗證分析表明，本文方法結構簡便易于實現、滿足現代大型船舶電力系統拓撲分析的實時性與有效性需求。

船舶電力系統；拓撲分析；獨島搜索；動態跟蹤；圖論

0 引 言

船舶電網拓撲分析的主要功能是根據系統中的開關等設備的開合狀況，計算出電網的實時狀態，為船舶能量管理系統在監控和協調電力系統的運行、及時處理突發事件和異常情況、保障整個電力系統的安全穩定運行等方面提供網絡基礎數據信息。

船舶電網拓撲分析的實質是電氣連通性分析，根據電網中的開關等設備的工作狀態，利用建立的拓撲結構模型來描述電網各元件之間的連接關系[1]。傳統的連通性分析主要采用鄰接矩陣法或樹狀搜索法。鄰接矩陣法通過矩陣自乘運算得到全連通關系矩陣[2, 3]，算法原理簡單，但其計算量隨著網絡規模的擴大而呈指數級增長，且在處理稀疏網絡時不夠緊湊而占據較大存儲空間。樹狀搜索法主要包括深度優先搜索法（depth first search，DFS）和廣度優先搜索法（breath first search，BFS）。在樹搜索法的基礎上，許多學者嘗試采用局部拓撲與全局拓撲相結合、引進啟發式規

則搜索、采用面向對象建模技術等方法進行船舶電網拓撲分析[4 – 6]，在不同程度上提高了拓撲更新的實時性，卻使算法結構越發復雜，實現起來相當不易。隨著現代船舶容量不斷地增大，船舶電力系統網絡拓撲結構也變得更加復雜，對船舶電網拓撲分析的有效性、實時性以及算法結構的簡易性提出了新的挑戰。

基于當前研究狀況，應對現代船舶對電網拓撲分析實時性的挑戰，本文提出一種船舶電網拓撲分析的新方法。建立一種基于圖論理論的信息數據模型，將船舶電網結構錄入系統。靜態分析時，基于船舶電網初始母線分析的結果，利用獨島搜索策略進行電氣島分析，生成電網拓撲基本信息數據庫；在動態分析過程中，采用效率更高的節點標記法[8]對受影響的母線重新進行連通性分析，并基于該分析結果作進一步判斷，實現電網拓撲信息數據庫的動態更新。

1 船舶電力系統拓撲模型

1.1 船舶電網拓撲結構

圖1 船舶電力系統結構圖Fig.1Shipboard power system network

艦船電力系統拓撲結構包括供電網絡和配電網絡。與陸地電網不同的是，由于船舶機艙空間緊湊，供電網和配電網之間區分不明顯，許多線路兼具雙重功能。船舶電網多采用輻射狀、干饋線混合的配電方式，大功率或重要負載以饋線方式由發電機母線直接供電，小功率或次要負載以干線方式配電。圖1所示

為某現代化大型集裝箱船舶采用的典型的輻射狀干饋線混合式船舶電網拓撲結構示意圖。其中，G1 與 G2發電機組屬于同一分段母線，G3 與 G4 發電機組屬于同一分段母線，兩分段母線之間由聯絡開關連接成發電母線，經變壓器 T 降壓后，電網連接到低壓配電母線，低壓配電區又與應急發電機組 EG 以及岸電連接。

1.2 圖論模型

船舶電網是由電源、變壓器、母線、開關、刀閘、接地刀閘等設備通過導線連接而成，在結構上具有明顯的點線特征，非常適合利用圖論方法進行分析。在建立船舶電網拓撲結構的圖論模型時：將電源和負載看作電氣節點；變壓器、開關、刀閘、接地刀閘等二端元件看作連接電氣節點的支路。節點之間由支路相連，支路是否連通取決于支路上設備的工作狀態。

在圖論中，圖定義為由抽象的節點和邊組成的集合 G = {V，E}，其中 V = {v1，v2，...，vn} 為點集，E = {e1，e2，...，em} 為邊集。對于圖 G = {V，E}，可用數據表和鄰接矩陣2種標準方法來存儲其拓撲信息。船舶電網的拓撲結構圖屬于稀疏圖（邊的數量 |E| 遠小于節點數的平方 |V|2），適合采用形式緊湊的數據表來存儲拓撲信息。為節省存儲空間，本文采用支路表來記錄圖 G 的原始拓撲信息，表中每1行代表1條支路，記錄該支路的起始節點號、終止節點號等信息，并將支路類型分為：0 開關支路、1 關聯支路和2其他類型的支路（電力傳輸支路等）。如表1所示，支路的起始節點和終止節點按照電網設計時的潮流方向來判別。當船舶電網拓撲結構改變時，只要從數據表中添加或刪除相應行數據即可，維護方便。

表1 圖的錄入數據結構Tab.1Data structure

1.3 節點標記法

傳統的樹狀搜索法屬于基于節點類型的算法，即運算或搜索時平均考慮節點間的所有信息，不區分是否直接連接關系，這類算法在最壞情況下要遍歷所有節點之間的所有關系，因此效率必然是 0（N2）。文獻[7]提出的節點標記法把搜索主要放在了具有直接連接關系的支路上，僅需存儲支路兩端的節點，通過依次搜索并標記支路兩端節點的編號來劃分連通域區，搜索次數僅為支路總數，與節點總數無關，避免了許多無用的搜索，提高了效率，其算法流程如圖2所示。

圖2 節點標記法流程圖Fig.2Flow chart of node marking algorithm

該算法的主要思想是：用數組 Ns[N] 記錄每個節點連通狀態，Ns[N] 的值表示節點屬于哪個區域。算法依次掃描支路，不斷更新支路兩端相連的2個節點的連通狀態。掃描完畢后，如果 Ns[N] 中所有值都一樣，則網絡連通，否則根據 Ns[N] 的值可以判斷該節點屬于哪個區域。算法所需要存儲空間為 max{0（N），0（M）}，在最壞情況下算法的效率為 0（MN），邏輯運算為 0（MN），而且，由于算法中不含有乘法運算，計算速度很快，容易編程實現。文獻[8]將該算法與樹狀搜索法以及矩陣法進行對比分析，結果表明，節點標記法在算法效率上占據絕對優勢，能夠應對大規模網絡連通性分析，本文將在動態拓撲分析中利用該算法對受變動事件影響的母線進行動態拓撲連通性計算。

2 拓撲分析算法

船舶電網拓撲結構分析分為靜態分析和動態分析。靜態分析是對新入電網或發生大規模支路改造、投退的電網進行的全網遍歷生成行為，不考慮船舶電網支路開關的具體連通狀態，假設全部支路均閉合，對全網進行遍歷分析，生成反映電網結構固有連接關系的拓撲信息集合。動態分析是在電網支路連通情況發生改變時對已經生成的全網拓撲信息的修正行為，大多數情況下，船舶電網拓撲結構的改變都是由支路開關狀態的切換造成的，相對于全網而言屬于局部變

化，理論上講只需對連通性發生變化的支路進行拓撲動態追蹤即可完成全網拓撲連通信息更新任務。

2.1 靜態遍歷

采用廣度優先搜索法（breath first search，BFS）進行圖的初始遍歷搜索。BFS 算法是圖論中最常用的搜索算法之一，相對于深度優先搜索法（depth first search，DFS），廣度優先搜索法對拓撲圖中的每個節點進行訪問僅一次，而深度優先搜索法因需要回溯，許多節點被重復訪問，增加了計算開銷。船舶電網多采用輻射狀、干饋線混合的配電方式，閉環設計，開環運行，圖中環路較少，使得 BFS 的搜索效率明顯高于 DFS。

BFS 搜索方法的主要思想為：從起始節點 v1開始，標記為已讀；而后以節點 v1的鄰接節點為第1層子節點依次進行訪問，并標記為已讀；接著依次訪問每個第1層子節點的下一層節點并標記為已讀，依此類推，直到圖中所有頂點都被訪問為止。

船舶電網拓撲分析主要包括母線分析和電氣島分析。母線分析的任務是將通過閉合開關連接在一起的節點合并為一條母線并為該母線編號，電氣島分析的任務是將通過特定支路連接在一起的母線合并為一個電氣島并給該島編號。

1）母線分析過程

①利用廣度優先搜索策略，從船舶電網中任意母線節點開始，搜索與該節點通過閉合開關所在支路相連接的所有節點，并依次將搜索到的節點和支路的所屬母線屬性設置為當前母線。當訪問到的支路類型為變壓器支路時，則返回到上一層搜索其他節點；

②若當前母線所連接的所有節點和支路均已被訪問，該母線已形成，則從其他任意未被訪問過的母線節點開始另一母線搜索；

③重復以上過程，直到船舶電網中所有節點和支路均被訪問過，結束母線搜索任務。

2）電氣島分析過程

船舶電網拓撲分析中，全網的電氣島分析通過重復獨島搜索過程來實現：

①初始化母線所屬電氣島標志；

②任選一個未標記電氣島標志的母線，并啟動一次獨島搜索；

獨島搜索過程為：給當前所選擇的母線賦置新的電氣島標志；查找與當前電氣島相交且投入運行的變壓器支路，將當前電氣島標志賦給變壓器支路對端節點所在母線，標記已經訪問過的變壓器支路；重復上一步，直至當前電氣島沒有變壓器支路或變壓器支路均未投入運行，則當前電氣島已形成，本次電氣島分析結束。

③重復上一步，直到船舶電網中所有母線均被訪問過，結束電氣島分析任務。

2.2 動態跟蹤

船舶電網拓撲分析的最終目標是生成能夠反映電網實時運行狀態的拓撲信息集合。船舶電網的支路連通狀態隨時可能因船舶運行工況的不同而改變，因此，船舶電網拓撲分析必須能動態地跟蹤網絡拓撲變化。

以往船舶電網動態分析常根據開關所在支路類型以及開關的開合情況進行組合式分類分析，尤其是當支路從閉合狀態轉換到斷開狀態時，需要從斷開支路兩端節點分別開始搜索電氣連通的節點集，判斷2個節點集是否相同，并以此判斷結果為依據重新對電網進行拓撲分析和調整。這種類型的動態分析方法缺點也比較明顯：一是在算法設計之初需要充分考慮所有支路和開關的不同類型，建模工作量大；二是要對支路類型與開關狀態的組合進行窮舉分析，增加了復雜度；三是搜索動作開關支路的兩端節點的各自連通節點集并判斷2個節點集是否相同需要較大的計算開銷，降低了動態分析的實時性。

基于以上分析，本文對船舶電網拓撲分析的動態跟蹤算法進行改進，當發生開關事件時，首先討論事件是“閉合”還是“斷開”，因為一條支路只能歸屬一個電氣島，所以在該電氣島內，搜索事件發生支路兩端節點之間的連通性，最后根據搜索結果作進一步分析即可完成動態跟蹤任務。

1）支路斷開

支路斷開對電網拓撲結構變化的影響最為復雜，在更新“斷開”事件船舶電網拓撲過程中，如果發生在變壓器支路或引起母線分割的支路，需要電氣島分析，則只從斷開支路的起始與終止節點所屬母線開始執行獨島搜索程序。基于該思想，在電氣島分析時，只將搜索限制在受影響的母線范圍內，不更改其他電氣島，如此可有效減少計算量，提高算法的實時性。

①檢測斷開支路是否為變壓器支路：如果是，則不必更改母線，對斷開支路的起始與終止節點所屬母線進行獨島搜索，然后結束程序；如果不是，執行下一步。

②提取斷開支路所在母線中所有支路，利用節點標記法搜索該母線的連通性：如果仍然連通，則支路斷開后只是在該母線內少了一條環路，不必分離母線，不必更改電氣島，結束本次分析；如果不連通，

則搜索結果已將原母線分割，進一步對分割后的子母線進行獨島搜索。

③根據分析結果更新船舶電網拓撲連通信息，結束本次任務。

2）支路閉合

①檢查閉合支路兩端節點的電氣島標志是否一致。

②如果電氣島標志一致，意味著只是電氣島中多了一條連接支路，電氣島標志無需改變。進一步判斷閉合支路是否為變壓器支路：如果是變壓器支路，則不必更改閉合支路兩端節點所屬母線標志；如果不是變壓器支路，則進一步判斷兩端節點所屬母線標志是否一致，如果一致則母線標志也無需改變，不一致則合并母線。

③如果電氣島標志不一致，則閉合支路將兩個獨立的電氣島合并到了一起，合并電氣島，合并母線。

2.3 拓撲分析完整框架

在完成電網拓撲的靜態遍歷和動態跟蹤算法設計之后，即可建立船舶電網拓撲分析的完整流程：首先輸入船舶電網拓撲結構的節點支路信息，讀取一次支路工作狀態，之后啟動靜態分析算法生成船舶電網拓撲的連通信息數據庫，在此基礎上，通過獲取支路狀態變化信息來啟動拓撲動態跟蹤算法，從而實時更新船舶電網拓撲連通信息數據庫，實現船舶電網拓撲分析任務。完整的分析流程如圖3所示。

圖3 船舶電網拓撲分析完整流程Fig.3The full flow chart of shipboard power system topology analysis

3 算例分析

以圖1所示船舶電力系統為例，對本文所提船舶電網拓撲分析方法進行驗證和討論。將圖1中船舶電力系統抽象成由點集和邊集連接成的拓撲模型，并對點和邊進行編號，得到等效拓撲結構如圖4所示，共包括6個電源（4 臺主發電機、1 臺應急發電機以及 1個岸電接口）、77 個節點、79 條支路（63 條開關支路、14 條變壓器支路以及2個電力輸送支路）、29 個負載（24 個普通負載和5臺大功率電動機負載）。

船舶電網的初始網絡狀態為：主發電機 G1，G2，G3 和 G4 投入運行，其余電源退出運行；開關支路b5，b7，b20 斷開，其余開關支路全部閉合；變壓器支路全部投入運行。利用本文方法對船舶電網拓撲分析過程表述如下：

1）靜態分析

按照表1數據格式錄入船舶電網拓撲結構，然后進行船舶電網拓撲結構的靜態分析，利用廣度優先搜索算法遍歷全網劃分母線，并對母線進行電氣島分析，母線和電氣島分析結果分別如表2和 表3所示。

①事件 1：在初始網絡狀態的基礎上，假設變壓器 T1 退出運行。

變壓器 T1 退出運行，屬支路“斷開”事件。經判斷，支路 T1 為變壓器支路；不必分離母線，對支路T1 的起始節點 n1 所屬母線1以及終止節點 n45 所屬母線2進行獨島搜索，搜索結果為母線1和母線2仍然在同一電氣島內，關聯支路 T1 從電氣島1內剔除，其他電氣島不變；更新拓撲信息。

②事件 2：在初始網絡狀態的基礎上，假設支路b37 退出運行。

支路 b37 是開關支路，該事件類型為“斷開”。支路 b37 不屬于變壓器支路；支路 b37 屬于母線 1，利用節點標記法對母線1內所有支路進行連通性分析，經計算，斷開后支路 b37 的起始節點 n76 與終止節點n11 在原母線1內不再連通，母線1被分割成兩條子母線，將支路 b37 的終止節點 n11 所屬子母線重新編號為母線 16，起始節點 n76 所屬子母線仍保留為母線1，對母線 1、母線 16 進行獨島搜索；電氣島分析結果為原電氣島1中獨立出一個新電氣島 4，包含母線6，7，8，9，16，成員關聯支路 T3，T4，T5 以及T6，其余網絡不變；更新拓撲信息。

③事件 3：在事件1的基礎上，支路 b20 投入運行。

支路 b20 為開關支路，該事件為“閉合”。檢查支路 b20 兩端節點電氣島標志；兩端節點電氣島標志一

致，均為電氣島 1，表示支路 b20 的閉合使得原電氣島內多了一條連通支路，電氣島標志無需改變；進一步，由于該支路不屬于關聯支路，且支路兩端節點所屬母線分別為母線2和母線 3，則將母線3合并到母線2集合內，將支路 b20 也并入新的母線2內，將母線3 以后的母線編號各自減一重新編號；更新拓撲信息。

圖4 船舶電網拓撲結構示意圖Fig.4The topological diagram of shipboard power system

表2 母線分析結果Tab.2The bus analysis result

表3 電氣島分析結果Tab.3The island analysis result

通過3例事件的處理結果可證明本文所提方法在船舶電網拓撲分析中的有效性。尤其是在處理動態跟蹤問題時，由于采用了效率較高的節點標記法，不僅使本文拓撲分析方法的實時性得到保障，更使算法結構得到簡化而易于實現。

4 結 語

本文針對船舶電網拓撲分析問題提出一種新方法。新定義了基于圖論模型的信息存儲格式，將船舶電網拓撲錄入系統；在靜態分析中，利用廣度優先搜索（BFS）對船舶電網進行初始母線分析，在此基礎上利用獨島搜索策略進行電氣島分析；在動態分析過程中，利用節點標記法對受影響的母線重新進行連通性分析，并基于該分析結果作進一步判斷，從而實現船舶電網的動態跟蹤任務。最后以某現代化大型集裝箱船舶電網為例進行了驗證計算，結果表明，本文所提方法結構簡便易于實現，滿足現代大型船舶電力系統拓撲分析的實時性與有效性需求。

[1]姚玉斌, 王丹, 吳志良, 等. 方程求解法網絡拓撲分析[J]. 電力自動化設備, 2010, 30(1): 79–83. YAO Yu-bin, WANG Dan, WU Zhi-liang, et al. Network topology analysis by solving equations[J]. Electric Power Automation Equipment, 2010, 30(1): 79–83.

[2]馬靜, 張俁妤, 馬偉, 等. 基于關聯矩陣標記法與回路矩陣的電網拓撲分析[J]. 電力系統自動化, 2014, 38(12): 74–80. MA Jing, ZHANG Yu-yu, MA Wei, et al. Power network topological analysis based on incidence matrix notation method and loop matrix[J]. Automation of Electric Power Systems, 2014, 38(12): 74–80.

[3]王增平, 張晉芳, 張亞剛. 基于開關路徑函數集的新型廠站內網絡拓撲方法[J]. 中國電機工程學報, 2013, 33(1): 137–145. WANG Zeng-ping, ZHANG Jin-fang, ZHANG Ya-gang. A novel substation configuration identification algorithm based on the set of breaker-path functions[J]. Proceedings of the CSEE, 2013, 33(1): 137–145.

[4]梅念, 石東源, 段獻忠. 基于圖論的電網拓撲快速形成與局部修正新方法[J]. 電網技術, 2008, 32(13): 35–39. MEI Nian, SHI Dong-yuan, DUAN Xian-zhong. A novel method for fast power network topology formation and partial revision based on graph theory[J]. Power System Technology, 2008, 32(13): 35–39.

[5]黃靖, 張曉鋒, 蔣心怡. 一種啟發式艦船電力網絡拓撲分析方法[J]. 電力系統及其自動化學報, 2008, 20(2): 110–116. HUANG Jing, ZHANG Xiao-feng, JIANG Xin-yi. Heuristic topology processor for the shipboard power system network[J]. Proceedings of the CSU-EPSA, 2008, 20(2): 110–116.

[6]呂昊, 王吉忠. 基于面向對象技術的艦船綜合電力系統電力網絡故障模擬及拓撲跟蹤[J]. 船電技術, 2010, 30(4): 28–33. LV Hao, WANG Ji-zhong. Malfunction simulation and topology tracking for shipboard integrated power system network based on object-oriented technology[J]. Marine Electric & Electronic Engineering, 2010, 30(4): 28–33.

[7]黃家棟, 羅偉強, 趙永強, 等. 兩種新的電網連通性分析快速算法[J]. 電力系統保護與控制, 2008, 36(17): 16–18, 50. HUANG Jia-dong, LUO Wei-qiang, ZHAO Yong-qiang, et al. Two new high-speed algorithms for electrical network connectivity analysis[J]. Power System Protection and Control, 2008, 36(17): 16–18, 50.

[8]黃正, 陳凡, 張雪嬌, 等. 電網拓撲分析算法的研究[J]. 南京工程學院學報(自然科學版), 2013, 11(2): 43–49. HUANG Zheng, CHEN Fan, ZHANG Xue-jiao, et al. Study on power network topology analytic algorithm[J]. Journal of Nanjing Institute of Technology (Natural Science Edition), 2013, 11(2): 43–49.

[9]WU Y J, TANG Y, HAN B, et al. A topology analysis and genetic algorithm combined approach for power network intentional islanding[J]. International Journal of Electrical Power & Energy Systems, 2015, 71: 174–183.

[10]FARROKHABADI M, VANFRETTI L. An efficient automated topology processor for state estimation of power transmission networks[J]. Electric Power Systems Research, 2014, 106: 188–202.

[11]甄洪斌, 張曉峰, 戚連鎖, 等. 基于拓撲識別的艦船電力系統自適應保護策略[J]. 艦船科學技術, 2011, 33(3): 53–56. ZHEN Hong-bin, ZHANG Xiao-feng, QI Lian-suo, et al. An adaptive protection scheme based on topology-recognition for shipboard electrical power systems[J]. Ship Science and Technology, 2011, 33(3): 53–56.

A fast topology analysis method for large shipboard power system network

ZHANG Ling-jie1, SUN Jian-bo1, GUO Chen2
(1. Marine Engineering College, Dalian Maritime University, Dalian 116026, China; 2. Information Science and Technology College, Dalian Maritime University, Dalian 116026, China)

In response to the increasing demand on the shipboard power system topological monitoring ability with the rapid development of modern ship toward large-scale and automation, this paper presents a novel fast topology analysis method for large shipboard power system. Firstly, input the shipboard power system topological information using the graph theory based data model; Secondly, traverse the initial network and generate the node bus and island to achieve the static global topology analysis, then generate the topological information database; Finally, after analyzing the connectivity of the affected node bus with the node marking algorithm, the dynamic tracking program is completed combining with the proposed isolated island search strategy. Verification and analysis is conducted on a modern large shipboard power system, the results indicate that the proposed fast topology analysis method fulfills the demands of modern large shipboard power system on real-time capability and effectiveness with relatively simple structure.

shipboard power system；topology analysis；isolated island search；dynamic tracking；graph theory

TM711

A

1672 – 7619(2016)11 – 0095 – 07

10.3404/j.issn.1672 – 7619.2016.11.020

2016 – 03 – 28；

2016 – 07 – 05

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

張靈杰(1989 – )，男，博士研究生，研究方向為船舶電力系統自動化及機電一體化。