基于哈希和編輯距離算法的SCD雙層向量化與變更校驗(yàn)技術(shù)

01SCD配置文件及變更方式1.1

智能變電站SCD組成智能變電站SCD配置文件基于IEC618506標(biāo)準(zhǔn)中智能變電站的配置描述語言（substationconfigurationlanguage，SCL）編寫與建模。SCD模型中節(jié)點(diǎn)采用樹型層次結(jié)構(gòu)，包括頭文件描述（Header）、變電站模型（Substation）、通信模型（Communication）、數(shù)據(jù)類型模板（Datatypetemplates）、智能電子設(shè)備模型（intelligentelectronicdevice，IED）5個(gè)樹枝組成。樹枝由分支構(gòu)成，其分支含有多種枝葉，一般采用SCL元素描述，每種元素通過屬性描述解析。1.2

SCD變更方式智能變電站配置文件的差異主要包括配置變更和增減更換，如IED設(shè)備的增減和更換、虛端子的變化（變更/增減）、通信方式的變更等，這些差異在SCD文本中，表現(xiàn)為SCD文本相關(guān)元素發(fā)生修改、增加和刪減3種變更操作。當(dāng)SCD文件發(fā)生變更時(shí)，3種變更方式及可能出現(xiàn)的結(jié)果如表1所示。表1

SCD變更方式Table1

SCDchangemode不同智能變電站對SCD的變更要求不同，針對SCD文件變更，研究準(zhǔn)確快速校驗(yàn)技術(shù)至關(guān)重要。02SCD文本向量化模型計(jì)算表面文本相似度實(shí)現(xiàn)不同文本的比較可以找到SCD文件變更情況。針對原始文本和發(fā)生修改的文本，對字符串序列或字符的組合進(jìn)行計(jì)算處理，得到2個(gè)文本的字符匹配程度或距離，作為相似度的評判標(biāo)準(zhǔn)。在文本相似度的計(jì)算中常使用基于空間向量模型方法?？臻g向量模型將文本視為相互獨(dú)立的詞語，根據(jù)詞語出現(xiàn)的頻率，將其作為特征項(xiàng)并賦予不同的權(quán)重vi，以所有特征項(xiàng)的權(quán)重為分量構(gòu)成該文本的空間向量模型，修改前后文本T和T′的特征向量可以分別構(gòu)建為fT=[v1,v2,???,vn]，fT′=[v′1,v′2,???,v′n]。文構(gòu)建雙層向量模型結(jié)構(gòu)完成SCD文本校驗(yàn)，對SCD文本不再賦予權(quán)重值，直接將各部分元素及屬性抽象成向量化模型。第一層向量模型判斷SCD文本是否存在變化，并作為第二層向量模型校驗(yàn)的啟動(dòng)判據(jù)。2.1

SCD校驗(yàn)第一層向量模型SCD文本第一層向量模型由Header、Communication、IED節(jié)點(diǎn)元素和CRC校驗(yàn)碼組成。2.1.1基于Header部分的第一層向量建模Header部分包含SCD文件的版本信息、修訂信息、文件書寫工具標(biāo)識以及名稱映射等信息。其中全站CRC校驗(yàn)碼只有一種，與全站所有IED虛端子配置相關(guān)，任意IED虛端子配置發(fā)生變化時(shí)CRC都會(huì)發(fā)生變化。此部分第一層向量模型為式中：n1、n2分別為version和revision元素?cái)?shù)目；c為SCD全站虛端子配置CRC校驗(yàn)碼。2.1.2

基于Communication部分的第一層向量建模Communication部分發(fā)生網(wǎng)絡(luò)拓?fù)渥兓?、通信協(xié)議更改、硬件設(shè)備更換等會(huì)使站控層網(wǎng)和過程層網(wǎng)ConnectedAp元素及節(jié)點(diǎn)下的GSE和PhysConn元素發(fā)生變化。此部分第一層向量模型為式中：n1、n2、n3分別為ConnectedAp、GSE和PhysConn元素的數(shù)目。2.1.3

基于IED部分的第一層向量建模IED部分描述了IED的配置情況及其所包含的邏輯裝置、邏輯節(jié)點(diǎn)、數(shù)據(jù)對象和所具備的通信服務(wù)能力。此部分第一層向量模型為式中：n1、n2、n3、n4分別為IED設(shè)備、AccessPoint、LDevice、LN元素的數(shù)目。2.1.4

基于CRC校驗(yàn)碼的向量化建模IED部分有2種校驗(yàn)碼：一種是全站過程層虛端子配置CRC校驗(yàn)碼，另一種是IED過程層虛端子配置CRC校驗(yàn)碼。此部分第一層向量模型為式中：c1,c2,c3,?,cn分別為各IED裝置CRC校驗(yàn)碼。第一層向量中變更前SCD文本向量記為fk，變更后記為f′k，其中k代表第一層向量模型第k個(gè)部分。2.2

SCD校驗(yàn)第二層向量模型在第一層向量模型的基礎(chǔ)上，分別對Header、Communication和IED中關(guān)鍵性節(jié)點(diǎn)元素部分進(jìn)行第二層向量模型構(gòu)建。2.2.1

基于Header部分的第二層向量建模Header部分第二層向量模型為式中：f1,1、f1,2分別為用revision和version元素屬性值r1,r2,r3,?,rn和v1,v2,v3,?,vn構(gòu)建的向量模型。2.2.2

基于Communication部分的第二層向量建模Communication部分第二層向量模型為式中：f2,1、f2,2分別為用PhysConn和GSE元素的屬性值構(gòu)建的向量模型。2.2.3

基于IED部分的第二層向量建模IED部分第二層向量模型為式中：f3,i為用第i個(gè)IED設(shè)備構(gòu)成的向量模型；Ni為第i個(gè)IED設(shè)備的name屬性值；Ai、Di、Li分別為第i個(gè)IED設(shè)備的AccessPoint、LDevice和LN元素個(gè)數(shù)；Si、Mi、Gi分別為第i節(jié)點(diǎn)inputs中ExtRef屬性值。第二層向量模型中變更前后的SCD文本向量分別記為fk,i、f′k,i，其中k,i代表第二層向量模型第k個(gè)部分中第i個(gè)元素或IED設(shè)備。雙層向量模型的對應(yīng)關(guān)系如圖1所示。圖1

雙層向量關(guān)系框架

Fig.1

Thetwo-layervectorrelationshipframework

03SCD文本校驗(yàn)技術(shù)

基于空間向量構(gòu)建的SCD向量模型需要經(jīng)過相應(yīng)處理才可計(jì)算相似度，完成對比校驗(yàn)。3.1

基于哈希算法的SCD向量模型處理技術(shù)哈希算法是將任意長度的二進(jìn)制值映射為較短固定長度的二進(jìn)制值，可以處理復(fù)雜的文本，其映射過程為式中：{0,1}*為任意長度的文本位串；{0,1}n為長度為固定值n的二進(jìn)制位串。哈希算法對SCD文本向量處理的過程為：首先，應(yīng)用哈希函數(shù)對SCD文本向量f檢測，確定各向量元素的終止位置，動(dòng)態(tài)調(diào)節(jié)各向量的長度；然后，逐一掃描向量，應(yīng)用強(qiáng)哈希函數(shù)H計(jì)算第i個(gè)向量元素的哈希值ti；最后，將所有向量中的哈希值按照先后順序連接起來，得到哈希向量h=[t1,t2,t3,?,tn]，從而完成哈希處理轉(zhuǎn)化。將SCD文本向量f中長度為s的字符串Rs做哈希運(yùn)算，其函數(shù)表達(dá)式為式中：Ri為Rs第i個(gè)位置上的字符；mod為取模運(yùn)算。為了更有效處理SCD空間向量，可以利用定長滾動(dòng)指針對向量中元素逐字節(jié)進(jìn)行滾動(dòng)哈希計(jì)算，提高效率。若長度為s的指針移動(dòng)到結(jié)尾位置a，則計(jì)算的哈希值字符串為若指針向后移動(dòng)一個(gè)字節(jié)，字符串Rs,a+1為如果已知H(Rs,a)的值，則計(jì)算H(Rs,a+1)時(shí)，只需從H(Rs,a)中去除Ra?s+1產(chǎn)生的結(jié)果，再添加Ra+1的作用結(jié)果即可達(dá)到滾動(dòng)計(jì)算哈希值的目的。SCD文本向量求解哈希值的過程是對其進(jìn)行預(yù)處理，將SCD文本向量模型轉(zhuǎn)化為哈希向量模型。此向量模型為字符串的形式，因此求解SCD文本相似度問題轉(zhuǎn)化為求解字符串相似度問題。3.2

基于編輯距離算法的向量相似度計(jì)算方法編輯距離通過對字符串文本中某個(gè)字符進(jìn)行添加、刪減、更換的編輯操作完成相似度比較。經(jīng)過哈希計(jì)算得到的SCD文本向量由字符串組成，先結(jié)合編輯距離算法對其進(jìn)行計(jì)算處理得到字符串相似度，再完成SCD文本的校驗(yàn)。取SCD變更前后某一部分的兩個(gè)哈希向量h和h′中對應(yīng)的2個(gè)哈希值串E和F：E=e1,e2,e3,???,em，F(xiàn)=f1,f2,f3,???,fn，并分別將其作為第一行和第一列構(gòu)建關(guān)系矩陣L，L表示為式中：元素dij為哈希值串E和F之間的編輯距離，記為L(E,F)，表示哈希值串E變化到哈希值串F所需最少編輯操作次數(shù)。經(jīng)計(jì)算得到的各個(gè)字符串的編輯距離相加即可得到兩個(gè)向量h和h′的編輯距離L(h,h′)，則利用字符串相似度公式求出的文本相似度為式中：Ls(h)、Ls(h′)分別為SCD變更前后的哈希向量字符串總長度。3.3

基于回溯路徑法的定位校驗(yàn)回溯路徑法可以完成SCD變更文本定位校驗(yàn)。即將矩陣右下角元素dmn按一定規(guī)則上溯至左上角元素d00時(shí)，遍歷過的單元格從右下到左上走過的路徑，得到匹配結(jié)果可完成定位校驗(yàn)。對于字符串P=1349347685和Q=144032745，經(jīng)過計(jì)算可得到L(P,Q)=5，則匹配結(jié)果如圖2所示。圖2中，黑色表示未發(fā)生變化，紅色表示發(fā)生了變化，“_”表示字符增加或者刪減。圖2

匹配結(jié)果

Fig.2

Matchingresults

3.4

SCD文本校驗(yàn)流程SCD文本校驗(yàn)在雙層向量模型的基礎(chǔ)上完成。首先，對于SCD變更前后的2個(gè)文本，選擇Header、Communication、IED的相關(guān)元素和CRC校驗(yàn)碼分別進(jìn)行第一層向量模型的構(gòu)建；其次，進(jìn)行哈希計(jì)算得到哈希向量，編輯操作后得到其相似度；最后，判斷是否啟動(dòng)第二層SCD校驗(yàn)。結(jié)合智能變電站實(shí)際情況，由于變更后的SCD文本不會(huì)出現(xiàn)大面積的變動(dòng)，第一層向量計(jì)算的相似度設(shè)置閾值為0.78，用來作為判斷不可能出現(xiàn)的情況。第一層相似度不同情況及操作如表2所示。表2

第一層相似度計(jì)算情況及操作Table2

Similaritycalculationandoperationofthefirstlayer根據(jù)第一層SCD文本校驗(yàn)情況判斷啟動(dòng)第二層SCD文本校驗(yàn)。對判斷啟動(dòng)SCD部分進(jìn)行第二層向量建模，經(jīng)過哈希和編輯距離處理后計(jì)算第二層向量相似度，最后使用回溯路徑完成分析校驗(yàn)。SCD文件校驗(yàn)總流程如圖3所示。圖3

SCD文件校驗(yàn)流程

Fig.3

SCDfileverificationprocess

04算例分析本文結(jié)合某500kV智能變電站新舊SCD文件進(jìn)行對比分析，并選擇IED部分進(jìn)行分析。4.1

IED部分第一層向量校驗(yàn)按照第一層空間向量模型進(jìn)行構(gòu)建，得到IED第一層的向量如表3所示。表3

IED第一層向量Table3

TheIEDfirstlayervector經(jīng)哈希算法處理后IED第一層哈希向量。經(jīng)編輯距離計(jì)算得到的L(h3,h′3)=78，則對第一層IED向量模型進(jìn)行相似度計(jì)算得到的S=0.8972＜1，由表2可知第二層SCD校驗(yàn)啟動(dòng)。4.2

IED部分第二層向量校驗(yàn)按照第二層空間向量模型進(jìn)行構(gòu)建，得到IED第二層部分向量如表4所示。表4

IED第二層向量Table4

IEDsecondlayervector選取f3,23和f′3,23向量中的S、M、G的部分節(jié)點(diǎn)進(jìn)行分析。對IED中部分哈希向量進(jìn)行編輯距離計(jì)算和相似度計(jì)算，得到的結(jié)果如表5所示。表5

各IED向量編輯距離和相似度Table5

TheIEDvectoreditdistanceandsimilarity由表5可知，IED第二層向量模型的相似度范圍為0~1。S=0表示IED設(shè)備發(fā)生了更換；S=1表示IED設(shè)備未發(fā)生變化；0＜S＜1表示IED設(shè)備存在增加、刪除和修改的變更操作，可以通過回溯路徑來定位判斷發(fā)生的變更方式。對相似度0＜S＜1的IED設(shè)備采用回溯路徑定位分析，其變更情況如圖4所示（選取部分發(fā)生變更的設(shè)備，圖中變更處箭頭指到下層節(jié)點(diǎn)）。圖4

增加、刪減、修改變更情況

Fig.4

Add,subtractandmodifychanges由圖4

a)可知，IED的某個(gè)設(shè)備Inputs節(jié)點(diǎn)元素發(fā)生了屬性增加的變化，變更后的Inputs元素下新增了兩列條目。由圖4

b)可知，IED的某個(gè)設(shè)備Inputs節(jié)點(diǎn)元素發(fā)生了屬性刪減的變化，變更后的Inputs元素下刪除了一列條目。由圖4c)可知，IED的某個(gè)設(shè)備Inputs節(jié)點(diǎn)元素發(fā)生了屬性值更換的變化，變更后的Inputs元素下兩列條目發(fā)生了更換。4.3

算法模型對比本文選擇鍵-值模型與所構(gòu)建的向量模型再次對算例中IED部分進(jìn)行校驗(yàn)并分析對比情況。兩模型校驗(yàn)對比情況如圖5所示。由圖5a)可以看出，向量模型在48s左右第一層向量校驗(yàn)結(jié)束，未啟動(dòng)第二層向量校驗(yàn)。而采用鍵-值模型進(jìn)行校驗(yàn)所用時(shí)間超過了100s，并且處理數(shù)據(jù)也多于向量模型校驗(yàn)。由圖5b)可以看出，在A點(diǎn)之前為向量模型的第一層校驗(yàn)，滿足啟動(dòng)條件后進(jìn)行第二層向量校驗(yàn)，在80s左右校驗(yàn)結(jié)束。而采用鍵-值模型校驗(yàn)所用時(shí)間超過了110s，且向量模型校驗(yàn)處理數(shù)據(jù)也少于鍵-值模型處理數(shù)據(jù)。圖5

鍵-值模型和向量模型校驗(yàn)對比

Fig.5

Verificationcomparisonofkey-valuemodelandvectormodel綜上所述，采用本文SCD向量模型進(jìn)行SCD文本校驗(yàn)相比于鍵-值