基于最短路徑算法的繼電保護數(shù)據(jù)模型結(jié)構(gòu)及搜索優(yōu)化

王文煥，郭鵬，詹榮榮，楊國生，李妍霏，李俊恒

(電網(wǎng)安全與節(jié)能國家重點實驗室(中國電力科學研究院有限公司)，北京 100192)

0 引 言

繼電保護專業(yè)管理包括保護裝置狀態(tài)評價、動作分析，涵蓋消缺、檢修、反措、技改、巡檢巡視的全壽命周期管理，分布在繼電保護統(tǒng)計分析及運行管理、繼電保護狀態(tài)評價及狀態(tài)檢修、繼電保護及故障信息系統(tǒng)、故障錄波聯(lián)網(wǎng)系統(tǒng)、在線監(jiān)視與智能診斷系統(tǒng)、變電站配置描述(substation configuration description，SCD)文件管控系統(tǒng)等多個繼電保護專業(yè)軟件系統(tǒng)中。繼電保護專業(yè)信息獲取手段日趨豐富，信息完整性不斷提升，然而，不同信息系統(tǒng)相對獨立、數(shù)據(jù)交互受限，難以為繼電保護專業(yè)管理提供全局應用支撐。以交直流混聯(lián)大電網(wǎng)運行對繼電保護的更高要求為目標，并伴隨著大數(shù)據(jù)與人工智能技術的快速發(fā)展，繼電保護專業(yè)管理正在經(jīng)歷不同繼電保護專業(yè)系統(tǒng)數(shù)據(jù)融合、深化繼電保護全局應用的專業(yè)發(fā)展過程。目前繼電保護數(shù)據(jù)模型是以數(shù)據(jù)對象間的基本關聯(lián)關系為依據(jù)，通過業(yè)務過程將數(shù)據(jù)對象間關聯(lián)關系組織起來的。但是，各種類型繼電保護裝置眾多，不同類別、不同特性保護裝置包含的數(shù)據(jù)對象豐富，不同數(shù)據(jù)對象的特性、數(shù)據(jù)量、訪問流量有相當差異，例如臺賬數(shù)據(jù)約150萬條，告警數(shù)據(jù)約2億條，缺陷數(shù)據(jù)約100萬條，數(shù)據(jù)對象間的關聯(lián)特性不同，包括一對一、一對多、多對一、多對多關系等，數(shù)據(jù)模型結(jié)構(gòu)合理性對繼電保護業(yè)務應用訪問數(shù)據(jù)的效率產(chǎn)生直接的影響，有必要考慮不同數(shù)據(jù)對象特性、數(shù)據(jù)量、訪問流量的差異性，以及不同數(shù)據(jù)對象間的關聯(lián)關系，對繼電保護專業(yè)模型結(jié)構(gòu)和數(shù)據(jù)訪問路徑進行優(yōu)化，提升專業(yè)應用對海量異構(gòu)數(shù)據(jù)的訪問效率。

繼電保護數(shù)據(jù)結(jié)構(gòu)主要包括結(jié)構(gòu)化數(shù)據(jù)、半結(jié)構(gòu)化數(shù)據(jù)和非結(jié)構(gòu)化數(shù)據(jù)，業(yè)務應用端通常采用結(jié)構(gòu)化數(shù)據(jù)建模，相比其他2種數(shù)據(jù)模型結(jié)構(gòu)，在數(shù)據(jù)檢索效率上具備明顯優(yōu)勢。但隨著繼電保護專業(yè)數(shù)據(jù)體量的增加，繼電保護專業(yè)軟件系統(tǒng)普遍面臨數(shù)據(jù)查詢效率下降的問題，數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化程度不足是其中的主要原因。在繼電保護數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化方面，文獻[1]研究了基于IEC 61850的智能電子設備(intelligent electronic device，IED)數(shù)據(jù)結(jié)構(gòu)優(yōu)化設計方法，文獻[2]提出了基于統(tǒng)一建模語言(unified modeling language，UML)和可擴展標記語言(extensible markup language，XML)的數(shù)據(jù)結(jié)構(gòu)模型優(yōu)化方法，文獻[3]提出了適用于非結(jié)構(gòu)化數(shù)據(jù)(如錄波、定值單等)及半結(jié)構(gòu)化數(shù)據(jù)(如SCD、SPCD等XML格式數(shù)據(jù))的數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化方法，文獻[4]提出了基于Petri網(wǎng)的UML形式化結(jié)構(gòu)建模方法。上述研究對繼電保護數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化方面起到一定作用，但仍缺少數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化程度指標、主站端結(jié)構(gòu)化數(shù)據(jù)的模型結(jié)構(gòu)優(yōu)化方法的研究。

考慮繼電保護數(shù)據(jù)對象間相互關聯(lián)，將數(shù)據(jù)對象抽象為網(wǎng)絡節(jié)點，數(shù)據(jù)對象間關聯(lián)關系抽象為網(wǎng)絡通路，繼電保護數(shù)據(jù)模型可以使用網(wǎng)絡形式予以表征。通過該模型網(wǎng)絡訪問繼電保護數(shù)據(jù)的便利程度可應用復雜網(wǎng)絡理論[5]進行分析。復雜網(wǎng)絡理論作為一種網(wǎng)絡分析方法，在電力系統(tǒng)連鎖故障預測領域取得一定的應用[6]。雖然復雜網(wǎng)絡方法無論是在理論和實際應用中都存在很多問題需要解決[7]，但它提供了通過網(wǎng)絡的宏觀參數(shù)來研究網(wǎng)絡結(jié)構(gòu)特性的視角，對于繼電保護數(shù)據(jù)模型網(wǎng)絡性能的評估具備一定的指導意義。

繼電保護數(shù)據(jù)模型搜索優(yōu)化可以轉(zhuǎn)化成搜索復雜網(wǎng)絡的最優(yōu)路徑。最短路徑算法是圖論中具有網(wǎng)絡特色和突出效果的理論分支，兼具悠久的研究歷史和現(xiàn)代應用價值，典型的最短路徑算法包括Dijkstra算法[8]、弗洛伊德(Floyd)算法[9]、Bellman-Ford算法[10]、單源最短路(shortest path faster algorithm，SPFA)算法[11]等。最短路徑算法在大數(shù)據(jù)技術查詢算法中也有應用，文獻[12]提出了適用于Hadoop平臺的最短路徑算法圖搜索算法，包括對分布式文件系統(tǒng)(hadoop distributed file system，HDFS)中大規(guī)模圖的分割，以及基于MapReduce的子圖內(nèi)查詢和子圖間查詢，提高了大規(guī)模圖最短路徑查詢的效率。文獻[13]基于雙向最短路徑算法對單詞和文本的相似性進行評估，建立知識庫中顆粒度比詞條更密的節(jié)點之間的超鏈接關系，實現(xiàn)單次和文本語義的相似性評估。

本文以提高繼電保護一體化數(shù)據(jù)模型的數(shù)據(jù)訪問效率為目標，分析繼電保護專業(yè)管理對一體化數(shù)據(jù)建模的需求，提出繼電保護數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化指標及優(yōu)化方法；考慮業(yè)務應用對數(shù)據(jù)對象訪問順序，依據(jù)數(shù)據(jù)對象間的關聯(lián)關系建立有向圖，將數(shù)據(jù)表映射為節(jié)點，將數(shù)據(jù)訪問順序映射為路徑，將數(shù)據(jù)表的查詢耗時映射為路徑長度，通過最短路徑算法對數(shù)據(jù)模型結(jié)構(gòu)和訪問順序進行優(yōu)化，提升專業(yè)應用對海量異構(gòu)數(shù)據(jù)的訪問效率。

1 繼電保護專業(yè)數(shù)據(jù)與數(shù)據(jù)模型

繼電保護的不同業(yè)務應用均是繼電保護專業(yè)管理的組成部分，不同業(yè)務應用的協(xié)同關聯(lián)是實現(xiàn)繼電保護專業(yè)管理的基本途徑，繼電保護專業(yè)數(shù)據(jù)發(fā)揮了不同業(yè)務應用間關聯(lián)紐帶的作用。圖1繪制了繼電保護基本業(yè)務的邏輯關系圖，以及繼電保護專業(yè)數(shù)據(jù)在業(yè)務應用間的流轉(zhuǎn)情況。

圖1所示的繼電保護專業(yè)數(shù)據(jù)中，直接上報或人工現(xiàn)場采集錄入的信息為基礎信息，包括1～10，以及20巡檢巡視結(jié)果中人工現(xiàn)場錄入部分。

圖1 繼電保護業(yè)務應用數(shù)據(jù)流簡圖

圖1中基礎信息外的其他信息是繼電保護專業(yè)應用對基礎信息進行處理和分析后，生成的分析結(jié)果，可以提供給其他專業(yè)應用或者用于信息展示。基礎信息的含義及數(shù)據(jù)量如表1所示。

表1 繼電保護基礎信息概覽表

繼電保護專業(yè)數(shù)據(jù)是支撐繼電保護業(yè)務實施的“血液”，而繼電保護數(shù)據(jù)模型是繼電保護業(yè)務應用訪問、處理專業(yè)數(shù)據(jù)的媒介。繼電保護數(shù)據(jù)模型一方面將取自不同數(shù)據(jù)源、分散獨立的專業(yè)數(shù)據(jù)組織起來，另一方面為支撐專業(yè)應用開展融合了基礎信息、中間變量和分析結(jié)論等類別信息。繼電保護數(shù)據(jù)模型具體涵蓋了：

1)物理實體的描述信息、配置信息，例如：繼電保護裝置等二次裝置，斷路器等一次設備，業(yè)務應用系統(tǒng)服務器、工控機、通訊裝置等實體設備的屬性描述信息；

2)信息對象的配置信息，包括繼電保護裝置等實體裝置涵蓋的信息對象的配置信息，例如，告警、動作、定值等信息節(jié)點的配置信息，工作電壓、光口強度等的配置信息等；

3)物理實體或信息對象間的關聯(lián)關系，例如，二次設備與一次設備的關聯(lián)關系，物理光纖與兩端的插件、端口的關聯(lián)關系，保護功能狀態(tài)與保護功能閉鎖的關聯(lián)關系等；

4)支撐業(yè)務應用的中間變量及變量關聯(lián)配置信息，例如，狀態(tài)評價算法的配置，算法的抽象變量，從歷史數(shù)據(jù)中提煉的對照標度，對抽象變量以及對照標度進行數(shù)學計算所得結(jié)果，算法的控制參數(shù)如迭代次數(shù)、收斂判據(jù)等；

5)大量的實體信息，即圖1中除一次設備信息、保護臺賬等物理實體配置信息外的保護設備功能配置及定值、運行狀況、運維記錄以及業(yè)務應用分析結(jié)論等實體信息。

2 繼電保護數(shù)據(jù)查詢效率的影響因素

繼電保護數(shù)據(jù)查詢效率取決于繼電保護數(shù)據(jù)模型結(jié)構(gòu)、級聯(lián)數(shù)據(jù)表訪問次序，以及數(shù)據(jù)庫層面的措施。這3個因素中，前兩個是從是否滿足繼電保護業(yè)務應用需求的角度確定的，第3個因素是從實現(xiàn)層面提出的，例如文獻[14]指出的索引、分區(qū)、結(jié)構(gòu)化查詢語言(structured query language，SQL)語句優(yōu)化等。本節(jié)主要考慮前2個因素。

2.1 繼電保護數(shù)據(jù)模型結(jié)構(gòu)

2.1.1 繼電保護數(shù)據(jù)模型網(wǎng)絡

繼電保護數(shù)據(jù)模型是將反映不同業(yè)務過程的數(shù)據(jù)表進行邏輯關聯(lián)和屬性組合的有機體系，將數(shù)據(jù)表抽象成節(jié)點，將數(shù)據(jù)表間的引用、級聯(lián)等關聯(lián)關系抽象成連線，繼電保護數(shù)據(jù)模型實質(zhì)上構(gòu)成了數(shù)據(jù)模型網(wǎng)絡。數(shù)據(jù)模型中任意一個數(shù)據(jù)對象屬性信息的變化或與其他數(shù)據(jù)對象關聯(lián)方式的變化均會改變數(shù)據(jù)模型網(wǎng)絡的結(jié)構(gòu)。查詢數(shù)據(jù)時，通常需要從給定條件所在的源數(shù)據(jù)表出發(fā)，進行一步搜索，得到滿足給定條件的數(shù)據(jù)及屬性信息；通過數(shù)據(jù)模型網(wǎng)絡的連線確定一張中間數(shù)據(jù)表，進行一步搜索，得到符合剛搜索到的屬性信息的數(shù)據(jù)，并獲取新的屬性信息，再通過數(shù)據(jù)模型網(wǎng)絡的連線確定下一張數(shù)據(jù)表，搜索新的數(shù)據(jù)和屬性信息，直至目標數(shù)據(jù)表，依據(jù)上一張數(shù)據(jù)表的數(shù)據(jù)和屬性信息搜索到目標數(shù)據(jù)。數(shù)據(jù)搜索共涉及到包含源數(shù)據(jù)表、中間數(shù)據(jù)表、目標數(shù)據(jù)表在內(nèi)的級聯(lián)數(shù)據(jù)表。例如，在統(tǒng)計不同型號保護裝置告警信息的業(yè)務中，需要查詢某條告警數(shù)據(jù)對應的保護裝置型號。數(shù)據(jù)搜索過程如圖2所示。以某告警數(shù)據(jù)為起點，通過該告警數(shù)據(jù)的告警配置Id屬性信息，在保護告警配置表搜索到符合該告警配置Id的數(shù)據(jù)以及數(shù)據(jù)集Id屬性信息，再在數(shù)據(jù)集表中搜索到符合該數(shù)據(jù)集Id的數(shù)據(jù)以及IED Id屬性信息，以此類推，最后，在保護裝置型號表中搜索符合保護裝置表搜索到的數(shù)據(jù)及裝置型號Id屬性信息的保護裝置型號目標數(shù)據(jù)。

圖2 數(shù)據(jù)搜索示例

數(shù)據(jù)模型網(wǎng)絡是以數(shù)據(jù)表關系為基礎，以繼電保護信息對象轉(zhuǎn)化成的數(shù)據(jù)表為單元，構(gòu)成的網(wǎng)絡化的抽象結(jié)構(gòu)。繼電保護數(shù)據(jù)模型網(wǎng)絡可抽象為一張有向圖，根據(jù)數(shù)據(jù)表的關聯(lián)特性能夠確定有向圖中連線的方向，主要包括如下4種情形：

1)外鍵關聯(lián)。數(shù)據(jù)表通過外鍵引用其他數(shù)據(jù)表主鍵，查詢方向為從引用數(shù)據(jù)表指向被引用數(shù)據(jù)表，例如圖2中保護裝置表通過外鍵引用保護裝置型號表的主鍵—裝置型號Id，數(shù)據(jù)查詢方向如圖中標識所示；

2)唯一性字段關聯(lián)。數(shù)據(jù)表間通過唯一不重復的屬性字段建立關聯(lián)，查詢方向通常為雙向。例如圖2中保護裝置表與IED裝置表可通過具備唯一性的設備識別代碼屬性字段建立關聯(lián)，既可以從保護裝置表查詢到IED裝置表，也可以從IED裝置表查詢到保護裝置表，圖中僅示出了其中一個方向；

3)輔助表關聯(lián)。針對需要引用被引用數(shù)據(jù)表多條數(shù)據(jù)的應用場景，建立一張輔助表，通過外鍵分別指向兩張原始數(shù)據(jù)表。輔助表能夠靈活地表達原始表間多對一、多對多關系。由于輔助表僅用于配置原始數(shù)據(jù)表的關聯(lián)關系，在有向圖中可簡化為一條由原始引用表指向原始被引用表的連線。例如，母線保護裝置與線路、變壓器等多個一次設備有關，通過保護裝置與一次設備關系輔助表，能夠靈活地將母線保護裝置指向數(shù)量不確定的一次設備；

4)映射關聯(lián)。是應用經(jīng)模糊匹配或總結(jié)人工經(jīng)驗生成的匹配算法，或人工匹配的方式，對數(shù)據(jù)表中數(shù)據(jù)的屬性信息進行自動匹配分析，建立起的與其他數(shù)據(jù)表的關聯(lián)關系。這是一種間接的關聯(lián)方式，起因是2個數(shù)據(jù)表間客觀存在的關聯(lián)不易獲取，但通常是分析應用所需掌握的。映射關聯(lián)的方向常為外鍵關聯(lián)的逆向。例如，依據(jù)繼電保護裝置告警信息，來判斷裝置告警位置，需要依據(jù)告警信息的語義，以及保護裝置表中保護裝置Id，從板卡、回路數(shù)據(jù)表中搜索滿足保護裝置Id并且符合該告警信息語義的板卡數(shù)據(jù)或回路數(shù)據(jù)。為了后續(xù)應用的方便，在獲取到2個數(shù)據(jù)表中數(shù)據(jù)的關聯(lián)關系后，常建立一張映射表。

2.1.2 反映數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化程度的指標

一個優(yōu)異的、便于用戶查詢數(shù)據(jù)的數(shù)據(jù)模型結(jié)構(gòu)必然具備這樣一些特征，例如，數(shù)據(jù)表關聯(lián)關系被充分挖掘，數(shù)據(jù)模型網(wǎng)絡連接豐富，用戶搜索數(shù)據(jù)所需訪問的數(shù)據(jù)表的數(shù)目減少；關鍵節(jié)點常用于連接不同類別應用的數(shù)據(jù)表，數(shù)據(jù)模型中心節(jié)點或關鍵節(jié)點輕量化，搜索不同業(yè)務數(shù)據(jù)期間訪問樞紐數(shù)據(jù)表的耗時少，提升查詢的效率。這些特征可以應用復雜網(wǎng)絡理論[15]中的若干指標體現(xiàn)。

1)平均路長L。定義網(wǎng)絡中2個節(jié)點之間的距離dij為由一個節(jié)點(起始數(shù)據(jù)表)查詢到另一個節(jié)點(目標數(shù)據(jù)表)的最短路徑對應的距離，而2個相連節(jié)點(數(shù)據(jù)表)的距離為根據(jù)被引用數(shù)據(jù)表所含數(shù)據(jù)量折算成的查詢時間。在一個網(wǎng)絡中，平均路長L是指所有節(jié)點對之間距離的平均值，即

(1)

如果數(shù)據(jù)模型網(wǎng)絡豐富，通常能夠減少節(jié)點間最短路徑包含的連線數(shù)，減小dij及L；優(yōu)選關鍵節(jié)點能夠減少跨業(yè)務應用數(shù)據(jù)查詢訪問到該關鍵數(shù)據(jù)表所耗費的時間，并且最短路徑涵蓋關鍵節(jié)點的數(shù)據(jù)查詢項目數(shù)多，減小dij及L。

2)集群系數(shù)C。集群系數(shù)是一個衡量網(wǎng)絡節(jié)點集聚程度的概念。對網(wǎng)絡中的某一個節(jié)點i設有ki個節(jié)點和其相連，則ki個節(jié)點之間最多有ki(ki-1)/2條邊，設ki個節(jié)點之間現(xiàn)存ti條邊，則定義Ci為

(2)

然后對所有的Ci取平均值就可得到聚類系數(shù)C。

如果數(shù)學模型網(wǎng)絡豐富，網(wǎng)絡節(jié)點集聚程度高，Ci及C增加。

如果數(shù)據(jù)模型網(wǎng)絡豐富，節(jié)點間的連線數(shù)目增多，平均度數(shù)增加；關鍵節(jié)點通常有較大的度數(shù)，優(yōu)選關鍵節(jié)點后，訪問樞紐數(shù)據(jù)表的耗時減少，高度數(shù)節(jié)點的權(quán)重增加，平均度數(shù)增加。

2.2 級聯(lián)數(shù)據(jù)表訪問次序

在一套繼電保護數(shù)據(jù)模型網(wǎng)絡中，隨著模型網(wǎng)絡結(jié)構(gòu)的豐富，由給定信息所處的數(shù)據(jù)表出發(fā)，通過不同的訪問路徑，查詢到目標數(shù)據(jù)所需的查詢時間不同。文獻[16]擬合出典型的數(shù)據(jù)存儲架構(gòu)下，查詢一張數(shù)據(jù)表的平均事務響應時間為

(3)

式中：C1是查詢應用部署的服務器數(shù)目；k1是路由系數(shù)，在集群環(huán)境下為常數(shù)，典型值為65；R1是單次查詢的路由尋址次數(shù)。例如在Hadoop Database(HBase)架構(gòu)[17]下，R1取2(HBase0.94以下版本)或3(HBase0.96以上版本)[18]；k2是數(shù)據(jù)查詢系數(shù)，與查詢數(shù)據(jù)表所含數(shù)據(jù)量正相關，典型值為600；λ1表示查詢應用的優(yōu)化度，若完全執(zhí)行文獻[16]所述的數(shù)據(jù)庫查詢底層優(yōu)化措施數(shù)據(jù)庫查詢底層優(yōu)化措施，λ1可取0.1。

由式(3)可知，查詢單張數(shù)據(jù)表所耗費的時間主要取決于數(shù)據(jù)表所含數(shù)據(jù)量。通過一個數(shù)據(jù)模型網(wǎng)絡選取一條數(shù)據(jù)查詢路徑，包括初始查詢條件所在的源數(shù)據(jù)表、目標數(shù)據(jù)表以及中間數(shù)據(jù)表，對應的數(shù)據(jù)查詢效率既取決于該路徑途經(jīng)數(shù)據(jù)表的數(shù)目，又取決于該路徑上每張數(shù)據(jù)表的數(shù)據(jù)量。另外，上文數(shù)據(jù)表關聯(lián)的4種形式中，通過外鍵關聯(lián)、唯一性字段關聯(lián)兩種方式查詢數(shù)據(jù)僅需訪問被引用數(shù)據(jù)表一張表，通過輔助表關聯(lián)、映射關聯(lián)兩種方式查詢數(shù)據(jù)需要訪問輔助表(或映射表)和原始被引用表兩張表。

3 繼電保護數(shù)據(jù)模型結(jié)構(gòu)及搜索優(yōu)化

3.1 繼電保護數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化

3.1.1 數(shù)據(jù)模型結(jié)構(gòu)分層優(yōu)化

3.1.2 增加數(shù)據(jù)表間的引用關聯(lián)

對于滿足上述條件的兩張數(shù)據(jù)表，有兩種增加數(shù)據(jù)關聯(lián)的情形：

1)直接增補。目前數(shù)據(jù)模型網(wǎng)絡架構(gòu)不存在u1至v1的路徑P1(u1,v1)，即Ω(u1,v1)=φ，則建立u1至v1關聯(lián)，關聯(lián)形式可能是外鍵關聯(lián)、唯一性字段關聯(lián)、輔助表關聯(lián)和映射關聯(lián)；

2)遞推增補。目前數(shù)據(jù)模型網(wǎng)絡架構(gòu)已至少存在一條u1至v1路徑P2(u1,v1)，即Ω(u1,v1)≠φ，則u1中任一條數(shù)據(jù)均能通過數(shù)據(jù)查詢的方式與v1中的數(shù)據(jù)建立關聯(lián)，根據(jù)路徑P2(u1,v1)上表關聯(lián)的具體形式，u1至v1的關聯(lián)可能是外鍵關聯(lián)、唯一性字段關聯(lián)、輔助表關聯(lián)和映射關聯(lián)。

s.t.g[R(u,v)·Ω0(u,v)]≠0。

式中：k1、k2、k3為權(quán)重系數(shù)，若數(shù)據(jù)模型節(jié)點u與v間建立直接的關聯(lián)引用關系，則R(u,v)=1，否則，R(u,v)=0；Ω0(u,v)指在模型增補后，u至v是否存在搜索路徑，若存在Ω0(u,v)=1，否則Ω0(u,v)=0；g(a)為自定義函數(shù)，指向量a各元素的累乘。約束條件的物理意義是指經(jīng)直接增補或遞推增補后，不存在任一孤立的數(shù)據(jù)模型節(jié)點。

3.2 繼電保護數(shù)據(jù)模型搜索優(yōu)化

如圖2所示，數(shù)據(jù)查詢是按照一定次序依次執(zhí)行數(shù)據(jù)表查詢，從已知的條件信息逐步獲得所期望結(jié)果的過程，包括源數(shù)據(jù)表查詢、中間數(shù)據(jù)表查詢和目標數(shù)據(jù)表查詢。采用不同的查詢步驟其效率可能會差別很大。所以，繼電保護數(shù)據(jù)搜索優(yōu)化可轉(zhuǎn)化為一個最短路徑問題。

現(xiàn)將數(shù)據(jù)搜索優(yōu)化問題轉(zhuǎn)化為圖論中的最短路徑問題。以數(shù)據(jù)模型網(wǎng)絡為基礎，構(gòu)建有向圖G，將數(shù)據(jù)模型網(wǎng)絡的數(shù)據(jù)對象N’映射為G的節(jié)點N，數(shù)據(jù)表間的引用關聯(lián)R映射為G的邊E。對于邊e=(p,q)∈E，若可從p查詢到q，邊e的距離ω(e)為由p查詢數(shù)據(jù)表q所耗費的時間，如式(3)所示；對于邊e1=(q,p)∈E，若不可從q查詢到p，邊e1的距離ω(e1)為一個大數(shù)M。

設Ω(u,v)是G中以u,v為端點的路徑集合，W(P(u,v))表示路徑P(u,v)上邊距離之和，繼電保護數(shù)據(jù)模型優(yōu)化問題可表示為在圖G中求Ω(u,v)中的一條路徑P0(u,v)，使得

(4)

典型的最短路徑算法包括Dijkstra算法、Floyd算法、Bellman-Ford算法、SPFA算法等，不同算法的比較如表2所示。表中，ξ、ε分別表示圖的頂數(shù)與邊數(shù)。

表2 不同最短路徑算法的比較

級聯(lián)數(shù)據(jù)表訪問次序優(yōu)化屬于單源最短路徑算法，不存在邊的權(quán)重為負的特殊情況，并且，為滿足繼電保護業(yè)務應用的需要，繼電保護數(shù)據(jù)模型網(wǎng)絡的邊數(shù)ε并非遠小于ξ2，表2的4種算法中，Dijkstra算法是滿足級聯(lián)數(shù)據(jù)表訪問次序優(yōu)化需求且具有最小時間復雜度的算法，所以本文選擇Dijkstra算法進行級聯(lián)數(shù)據(jù)表訪問次序優(yōu)化。

Dijkstra算法[19]在電力系統(tǒng)領域已應用于最優(yōu)解列斷面搜索[20]、配電網(wǎng)孤島劃分[21]、黑啟動策略優(yōu)化[22]、電網(wǎng)故障定位[23]等方面。其基本步驟是：

1)u、v不相鄰時，取ω(u,v)=∞；

2)令w(u0)=0；w(v)=∞，v≠u0；S0={u0}，i=0；

3)對每個vSi，用min{w(v),w(ui)+ω(ui,v)}替代w(v)；設ui+1是使w(v)取最小值的V(G)-Si中的頂，令Si+1=Si∪{ui+1}；

4)若i=ξ-1，停止；若i<ξ-1，用i+1替代i，轉(zhuǎn)3)。

應用Dijkstra算法，在Θ(v,ε)=Ο(ξ2)步數(shù)內(nèi)，可計算出u到v的最短路徑P0(u,v)以及對應的檢索時間duv，從而實現(xiàn)繼電保護數(shù)據(jù)模型搜索優(yōu)化。

4 案例分析

4.1 數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化

為滿足繼電保護不同業(yè)務應用的需求，采用本文第3章的方法，建立圖1中繼電保護專業(yè)數(shù)據(jù)的數(shù)據(jù)模型，繼電保護數(shù)據(jù)模型結(jié)構(gòu)的局部如圖3所示。圖中列出了數(shù)據(jù)表的主鍵英文名、目前數(shù)據(jù)量及若干關鍵屬性字段。

建立圖3所示的繼電保護數(shù)據(jù)模型時，考慮到不同實體間的層次關系，即

保護型號是一批保護裝置共有的概念，以保護型號數(shù)據(jù)表為樞紐，能夠?qū)糜谕吞柋Ｗo裝置綜合分析的相關數(shù)據(jù)表(圖3中未示出)關聯(lián)起來，滿足保護裝置群體性分析應用的需要。保護裝置是具備獨立功能的物理實體，以保護裝置數(shù)據(jù)表為樞紐，能夠?qū)糜诒Ｗo裝置全壽命周期管理類應用的相關數(shù)據(jù)表(例如圖3中的缺陷管理及檢修檢驗管理數(shù)據(jù)表)關聯(lián)起來，滿足保護裝置個體分析、評價及管理應用的需要。保護裝置部件是保護裝置的細分，如圖3中板卡所示，以保護裝置部件數(shù)據(jù)表為樞紐，能夠?qū)⒓毣奖Ｗo裝置部件的分析應用相關數(shù)據(jù)表(圖3中未示出)關聯(lián)起來，使得對保護裝置的分析、管理細化到裝置部件。保護事件、告警、遙信、模擬量、定值、定值區(qū)、軟壓板等配置信息是保護裝置的最小信息對象[24～26]，以配置信息數(shù)據(jù)表為樞紐，將保護裝置在線信息(例如描述告警配置數(shù)據(jù)表中告警點發(fā)生時間、數(shù)據(jù)值等的告警信息)與配置信息有機組織起來，為建立與IEC 61850等模型的接口，以及在線信息的深化應用奠定良好條件(本節(jié)算例僅舉告警信息一例)。可見，通過將數(shù)據(jù)模型對象按照其所描述實體的層次關系分層布局，實現(xiàn)了關鍵節(jié)點數(shù)據(jù)量的輕量化，提升繼電保護專業(yè)數(shù)據(jù)的訪問效率。

圖3 繼電保護數(shù)據(jù)模型架構(gòu)示意圖

增加數(shù)據(jù)表間的引用關聯(lián)能夠優(yōu)化繼電保護數(shù)據(jù)模型結(jié)構(gòu)，以數(shù)據(jù)檢索路徑“告警信息→告警配置→數(shù)據(jù)集→IED裝置→保護裝置→板卡信息”為例，應用3.1.2節(jié)的方法構(gòu)造計算模型，以增加模型間的引用關聯(lián)與否R(u,v)作為變量，取k1=0.5，k2=0.3，k3=0.2。該檢索路徑上已有的關聯(lián)關系如表3中“■”所示，可增加的引用關聯(lián)如“□”所示。其中，“保護裝置→板卡信息”可依據(jù)裝置告警或異常現(xiàn)象，建立映射關聯(lián)。模型中的變量R(u,v)的含義如表4所示。

在國產(chǎn)達夢數(shù)據(jù)庫中搭建了仿真計算環(huán)境，按照圖3數(shù)據(jù)模型引用關系及數(shù)據(jù)體量在數(shù)據(jù)庫中生成了測試數(shù)據(jù)。由于本算例規(guī)模小，采用枚舉法計算，得到優(yōu)化的數(shù)據(jù)模型增補結(jié)果，如表3及表4的最后一列所示。

表3 實例中關聯(lián)增補相關的數(shù)據(jù)模型列表

表4 模型增補變量詳情

表5 模型關聯(lián)增補后數(shù)據(jù)表的查詢耗時

可見，上述路徑僅具備增加“告警配置→IED裝置”以及“告警配置→板卡信息”關聯(lián)的必要，增加其他關聯(lián)并不利于提高數(shù)據(jù)檢索效率。為了說明本方法的有效性，以“告警配置”到“板卡信息”的關聯(lián)為例。通過“告警配置→數(shù)據(jù)集→IED裝置→保護裝置→板卡信息”的遞推序列，能夠建立“告警配置”數(shù)據(jù)表中功能位置(POS_FUNCTION)屬性項與“板卡信息”數(shù)據(jù)表中主鍵DEVBOARD_ID的關聯(lián)，減少了數(shù)據(jù)查詢遍歷的數(shù)據(jù)表的數(shù)目，也便于實際應用中直接根據(jù)告警配置信息確定隱患板卡。增補結(jié)果如圖3中虛線所示。

4.2 數(shù)據(jù)模型搜索優(yōu)化

圖3中由單裝置軟件版本檢索保護型號數(shù)據(jù)時，存在兩條路徑：“單裝置軟件版本→同型號保護軟件版本→保護型號”和“單裝置軟件版本→保護裝置→保護型號”兩條路徑。由單裝置軟件版本查詢同型號軟件版本、保護裝置的耗時分別為0.032、0.031 s，由同型號軟件版本查詢保護型號的耗時為0.009 s，由保護裝置查詢保護型號的耗時為0.262 s，第一條路徑總耗時0.031 s，第二條路徑總耗時0.038 s，應用Dijkstra算法可得最優(yōu)路徑為“單裝置軟件版本→同型號軟件版本→保護型號”。

由告警信息檢索板卡信息數(shù)據(jù)時，存在3條路徑“告警信息→告警配置→數(shù)據(jù)集→IED裝置→保護裝置→板卡信息”(路徑a)、“告警信息→告警配置→IED裝置→保護裝置→板卡信息”(路徑b)和“告警信息→告警配置→板卡信息”(路徑c)，3條路徑上相鄰數(shù)據(jù)模型間查詢耗時如表5所示，應用Dijkstra算法可得最優(yōu)路徑為路徑c。該路徑直接將告警配置信息關聯(lián)到終節(jié)點板卡信息表，省去了對數(shù)據(jù)集表、IED裝置表、保護裝置表的訪問，訪問數(shù)據(jù)表的數(shù)目最小。事實上，3個路徑的耗時分別為：5.212、4.992、4.874 s，應用Dijkstra算法確定的數(shù)據(jù)最優(yōu)訪問路徑與實際相符。

5 結(jié) 論

本文分析了繼電保護專業(yè)管理對一體化數(shù)據(jù)建模的需求，從繼電保護數(shù)據(jù)模型結(jié)構(gòu)和級聯(lián)數(shù)據(jù)表訪問次序兩方面提出了繼電保護數(shù)據(jù)查詢效率的影響因素，考慮業(yè)務應用對數(shù)據(jù)對象訪問順序，依據(jù)數(shù)據(jù)對象間的關聯(lián)關系建立有向圖，將數(shù)據(jù)表映射為節(jié)點，將數(shù)據(jù)訪問順序映射為路徑，將數(shù)據(jù)表的數(shù)據(jù)量映射為路徑長度，通過Dijkstra算法對數(shù)據(jù)訪問順序進行了優(yōu)化，提升了專業(yè)應用對海量異構(gòu)數(shù)據(jù)的訪問效率。結(jié)論如下：

2)以提高數(shù)據(jù)模型訪問效率為目標，應用Dijkstra算法提出了繼電保護數(shù)據(jù)模型結(jié)構(gòu)優(yōu)化方法，包括增加數(shù)據(jù)表間的引用關聯(lián)和數(shù)據(jù)模型結(jié)構(gòu)分層優(yōu)化，以及繼電保護數(shù)據(jù)查詢次序優(yōu)化方法；

3)依據(jù)保護型號、保護裝置、保護裝置、配置信息等不同實體，建立了繼電保護分層數(shù)據(jù)模型，增加了“告警配置→板卡信息”等數(shù)據(jù)表間的引用關聯(lián)，優(yōu)化了繼電保護數(shù)據(jù)模型結(jié)構(gòu)；應用Dijkstra算法對案例中具備多條數(shù)據(jù)訪問路徑的數(shù)據(jù)表訪問次序進行了優(yōu)化，提升了繼電保護數(shù)據(jù)的查詢效率。