胡文建，王長寧，楊宇皓，李旭東，孫 靜，楊 陽

(國網(wǎng)河北省電力有限公司石家莊供電分公司，石家莊 050051)

0 引言

電力通信網(wǎng)是智能電網(wǎng)重要組成部分，是保證智能電網(wǎng)安全、穩(wěn)定運營的關(guān)鍵因素[1-2]。為提高電力通信網(wǎng)安全性和穩(wěn)定性，網(wǎng)絡(luò)管理人員必須實時掌握電力通信網(wǎng)設(shè)備的運行狀況。但是，現(xiàn)有網(wǎng)絡(luò)管理系統(tǒng)采用SNMP協(xié)議，被管設(shè)備周期性的給網(wǎng)絡(luò)管理系統(tǒng)上報設(shè)備運行信息，容易導(dǎo)致網(wǎng)絡(luò)發(fā)生故障后才被管理人員發(fā)現(xiàn)，而且被管設(shè)備上報的信息不便于故障定位和恢復(fù)。

為解決此問題，主動探測技術(shù)被提出[3]，并且在故障管理領(lǐng)域得到了較多的應(yīng)用。在主動探測技術(shù)中，探測站點的選擇對網(wǎng)絡(luò)運行狀態(tài)信息的獲取起到了非常關(guān)鍵的作用。如果探測站點選擇的合適，會極大減少主動探測過程給網(wǎng)絡(luò)帶來的負面影響。如何通過選擇較少的探測站點實現(xiàn)對網(wǎng)絡(luò)的主動監(jiān)控，已成為當(dāng)前的一個研究熱點[4-5]。一般來說，探測站點的選擇是基于網(wǎng)絡(luò)中節(jié)點的位置和路由協(xié)議等信息進行選擇[6]。根據(jù)選擇過程不同，可分為固定周期選擇探測站點模型[7]和交互式探測站點選擇模型[8]2種。固定周期選擇探測站點模型一次性求解出所有合適的探測站點，雖然計算時使用的網(wǎng)絡(luò)模型比較復(fù)雜，但是一次性就可以求解出最佳的探測站點集合。交互式探測選擇方法每次只選擇一個最優(yōu)的探測站點，經(jīng)過多次優(yōu)化，最終得到最佳的探測站點集合。但是該方法需要經(jīng)過多次重復(fù)計算，而且每次計算網(wǎng)絡(luò)節(jié)點的信息增益都需要花費大量的時間。考慮到當(dāng)前的電力通信網(wǎng)規(guī)模比較大，如果采用交互式探測站點選擇方法，需要進行多次計算，工作量較大。

為解決電力通信網(wǎng)規(guī)模較大導(dǎo)致探測站點部署效率低的問題，基于電力通信網(wǎng)的特性提出了探測站點選擇的策略，基于網(wǎng)絡(luò)內(nèi)在特征的電力通信網(wǎng)探測站點選擇算法，從電力通信網(wǎng)的網(wǎng)絡(luò)節(jié)點中，選擇最少的網(wǎng)絡(luò)節(jié)點作為探測站點，通過發(fā)送探測監(jiān)控到所有網(wǎng)絡(luò)節(jié)點的運行狀態(tài)信息，以最少的探測站點達到最好的探測效果。

1 電力通信網(wǎng)絡(luò)特征

1.1 動態(tài)路由特性

在電力通信網(wǎng)中，一般來說，網(wǎng)絡(luò)設(shè)備都啟用了動態(tài)路由協(xié)議。鑒于動態(tài)路由協(xié)議在路由選擇時具有動態(tài)特性，所以，探測是否經(jīng)過某個網(wǎng)絡(luò)節(jié)點具有概率性。

為了描述從探測站點發(fā)送探測到網(wǎng)絡(luò)節(jié)點x的探測路徑是否經(jīng)過網(wǎng)絡(luò)節(jié)點nj，文中使用概率公式進行描述。使用P(PSPath(x)，nj)表示從探測站點集合PS中的探測站點發(fā)送探測到網(wǎng)絡(luò)節(jié)點x的探測路徑經(jīng)過網(wǎng)絡(luò)節(jié)點nj的概率。

1.2 探測路徑的重疊特性

探測站點是指具備發(fā)送和接收探測數(shù)據(jù)包能力的網(wǎng)絡(luò)節(jié)點。通常，一個網(wǎng)絡(luò)節(jié)點被選為探測站點需要滿足2個條件:可以使用TCP或UDP協(xié)議發(fā)送和接收探測數(shù)據(jù)包；從該節(jié)點發(fā)送的探測數(shù)據(jù)包構(gòu)成的路徑與其它探測站點發(fā)送數(shù)據(jù)包構(gòu)成的路徑盡可能獨立，并且獨立路徑的數(shù)量盡可能多。從上述2個條件可知，處于網(wǎng)絡(luò)邊緣的節(jié)點一般不會被選擇為探測站點。因為處于網(wǎng)絡(luò)邊緣的節(jié)點具有較少的邊數(shù)，從而導(dǎo)致其不會具有較多的獨立路徑。文中使用pi表示第i個探測站點，使用PS表示探測站點集合。使用nj表示第j個網(wǎng)絡(luò)節(jié)點，使用N表示網(wǎng)絡(luò)節(jié)點集合。一般來說，從探測站點到目標(biāo)網(wǎng)絡(luò)節(jié)點的探測，都會經(jīng)過多條網(wǎng)絡(luò)鏈路l。為便于描述探測站點發(fā)出的探測路徑，文中使用P(p，nj)表示探測路徑p經(jīng)過網(wǎng)絡(luò)節(jié)點nj的概率。例如，圖1是包含2個探測站點的網(wǎng)絡(luò)拓撲示意，圖中A、G為2個探測站點。A→C的探測路徑和G→C的探測路徑是相互獨立的。但是，A→E的探測路徑和G→E的探測路徑中，C→D→E路徑是相互重疊的。此時，A→C和G→C的探測結(jié)果互相獨立，但是A→E和G→E的探測結(jié)果互相重疊。所以，相對于A、G 2個探測站點，網(wǎng)絡(luò)節(jié)點D和網(wǎng)絡(luò)節(jié)點E為陰影節(jié)點。

圖1 包含2個探測站點的網(wǎng)絡(luò)拓撲示意

為判斷2個探測路徑之間的獨立性，文中定義探測路徑p1和p2之間的非重疊函數(shù)為BF(I(p1，p2))，使用公式(1)進行計算。其中，nj∈node(p1)∩node(p2)表示探測路徑p1和p2經(jīng)過的節(jié)點的交集。該公式表示兩條路徑的非重疊概率。當(dāng)取值越大，表示2條探測路徑之間重疊的概率越小。

當(dāng)已選擇部分探測站點之后，在選擇新的探測站點時，以新探測站點到達陰影節(jié)點的探測路徑的獨立性為評判標(biāo)準(zhǔn)。例如，對于新的可選探測站點c，需要計算它到陰影節(jié)點x的探測路徑的獨立性。使 用 BF(I(PSPath(x)，Path(c，x)))表示新探測站點到達陰影節(jié)點的探測路徑的獨立性，使用公式(2)計算。其中，nj∈PSPath(x)∩Path(c，x)表示“已有探測到達陰影節(jié)點x的路徑”與“節(jié)點c到達陰影節(jié)點x的路徑”的重疊路徑所經(jīng)過的節(jié)點。

在獲得每一個新探測站點到達陰影節(jié)點的探測路徑BF取值后，可以將大于閾值Thd的BF取值對應(yīng)的新探測站點加入探測站點集合。

1.3 最大故障數(shù)目

在電力通信網(wǎng)中，當(dāng)只有一個故障時，可以通過在一個探測站點發(fā)送探測到所有網(wǎng)絡(luò)節(jié)點確定故障節(jié)點的位置。當(dāng)故障節(jié)點數(shù)量增加時，就需要更多的探測站點發(fā)送探測確定故障節(jié)點的位置。所以，電力通信網(wǎng)中故障節(jié)點的數(shù)量對探測站點的數(shù)量產(chǎn)生重要影響。根據(jù)長期運營數(shù)據(jù)可知，電力通信網(wǎng)中同時發(fā)生故障的次數(shù)非常少，基于此，文中設(shè)置電力通信網(wǎng)中同時發(fā)生故障的最大個數(shù)為k，非探測站點如果包含k條獨立的探測路徑，該節(jié)點即為可以被探測到的非陰影節(jié)點。但當(dāng)網(wǎng)絡(luò)節(jié)點nj的度數(shù)d小于k時，最多只能存在d條獨立的探測路徑。此時，只需找到d條獨立路徑，就可將網(wǎng)絡(luò)節(jié)點nj判斷為非陰影節(jié)點。

2 探測站點選擇算法

2.1 算法流程

文中提出的基于網(wǎng)絡(luò)內(nèi)在特征的電力通信網(wǎng)探測站點選擇算法如圖2所示。該算法以探測站點數(shù)量達到最大值或陰影節(jié)點集合為空作為終止條件，從網(wǎng)絡(luò)節(jié)點中逐步選擇可以使陰影節(jié)點集合中陰影節(jié)點數(shù)量最少化的新的網(wǎng)絡(luò)節(jié)點作為探測節(jié)點。下面對各個步驟進行詳細解釋。

圖2 基于網(wǎng)絡(luò)內(nèi)在特征的電力通信網(wǎng)探測站點選擇算法

在步驟1中，新建探測站點集合PS，并初始化為空；新建陰影節(jié)點集合SN，并將網(wǎng)絡(luò)節(jié)點集合N中的所有網(wǎng)絡(luò)節(jié)點放入陰影節(jié)點集合。在步驟2中，選擇節(jié)點度數(shù)最大的網(wǎng)絡(luò)節(jié)點作為第1個探測節(jié)點；如果存在多個網(wǎng)絡(luò)節(jié)點都有最大的度數(shù)，計算每個節(jié)點到其它節(jié)點的鏈路距離，選擇鏈路距離最短的核心節(jié)點作為第1個探測節(jié)點。假設(shè)第1個被選擇的探測節(jié)點為u，則采用公式(3)計算探測節(jié)點u對于網(wǎng)絡(luò)節(jié)點集合中任意網(wǎng)絡(luò)節(jié)點的探測路徑概率。

式中:w，v∈N。

在步驟3中，以最小化陰影節(jié)點集合為目標(biāo)，從網(wǎng)絡(luò)節(jié)點集合N中選擇下一個網(wǎng)絡(luò)節(jié)點作為探測節(jié)點。在步驟4中，分析第3步得到的每個節(jié)點的獨立路徑數(shù)量PathCount(nj)。當(dāng)PathCount(nj)大于等于最大故障數(shù)量k時，網(wǎng)絡(luò)節(jié)點nj可以被探測站點探測到。當(dāng)PathCount(nj)小于最大故障數(shù)量k，但是等于網(wǎng)絡(luò)節(jié)點nj的度數(shù)時，此時網(wǎng)絡(luò)節(jié)點nj可以被探測站點探測到。否則，表明網(wǎng)絡(luò)節(jié)點nj仍然還是陰影節(jié)點，需要進一步尋找探測節(jié)點。此時，將網(wǎng)絡(luò)節(jié)點nj加入到陰影節(jié)點集合。當(dāng)判斷完所有的網(wǎng)絡(luò)節(jié)點之后，如果陰影節(jié)點集合不空，返回到步驟3。否則，算法結(jié)束。

2.2 探測節(jié)點的選擇過程

為了驗證網(wǎng)絡(luò)中是否還存在陰影節(jié)點，已有研究表明，當(dāng)網(wǎng)絡(luò)中的非探測站點都存在K條獨立的探測路徑時，已確定的探測站點集合可以檢測出任意K個非探測站點的故障。此時，電力通信網(wǎng)的網(wǎng)絡(luò)節(jié)點都屬于可探測節(jié)點，不存在陰影節(jié)點。在網(wǎng)絡(luò)節(jié)點中選擇探測節(jié)點時，以陰影節(jié)點集合中陰影節(jié)點數(shù)量最小化為目標(biāo)。下面對網(wǎng)絡(luò)節(jié)點集合N中選擇下一個網(wǎng)絡(luò)節(jié)點作為探測節(jié)點的過程進行說明。該步驟包括5個子過程。

a.在網(wǎng)絡(luò)節(jié)點集合N中選擇下一個探測站點時，使用公式(4)計算候選探測站點c提供的到達陰影節(jié)點x的獨立探測路徑的非重疊函數(shù)BF，用于判斷陰影節(jié)點x是否屬于候選探測站點c的陰影節(jié)點。其中，n∈PSPath(x)∩Path(c，x)，表示“探測站點集合中的探測站點到達候選探測站點c的路徑”與“候選探測站點c到達陰影節(jié)點x的路徑”的重疊鏈路經(jīng)過的網(wǎng)絡(luò)節(jié)點。

b.如果BF(I(PSPath(x)，Path(c，x)))＞T Hd，表明路徑PSPath(x)和路徑Path(c，x)是相互獨立的，將PathCount(c，x)的值加1；否則，陰影節(jié)點x是候選探測站點c的陰影節(jié)點，并將x加入c的陰影節(jié)點集合S(c)。

c.選擇可以使陰影節(jié)點數(shù)目最少的候選探測站點c作為探測站點，并將探測節(jié)點c加入探測站點集合PS中。

d.設(shè)置S(c)為新的陰影節(jié)點集合，使用公式(5)更新PathCount(n)。其中，公式(5)表示將網(wǎng)絡(luò)節(jié)點集合N中的每個網(wǎng)絡(luò)節(jié)點n的獨立路徑數(shù)量更新為加上探測站點c之后的獨立路徑數(shù)量。

e.如果陰影節(jié)點集合S(c)為空，或者探測站點集合PS中的探測站點數(shù)量超過允許的最大數(shù)量，算法結(jié)束。否則，返回第1步執(zhí)行。

3 探測站點選擇算法驗證分析

為驗證本文提出的基于網(wǎng)絡(luò)內(nèi)在特征的電力通信網(wǎng)探測站點選擇算法PSA-NF的性能，實驗中將此算法與隨機選擇探測站點算法PSA-RD進行了比較。比較的指標(biāo)包括選擇的探測站點數(shù)量和選擇探測站點的時長。實驗中使用BRITE[9]工具生成電力通信網(wǎng)拓撲。其中，網(wǎng)絡(luò)節(jié)點的數(shù)量從100到500，以50為步長進行增加。為了驗證網(wǎng)絡(luò)節(jié)點度數(shù)對算法的影響，生成了平均度數(shù)為4和平均度數(shù)為7兩種網(wǎng)絡(luò)拓撲。每次實驗中，設(shè)定故障同時發(fā)生的最大數(shù)量為4個。

實驗結(jié)果如圖3—6，其中圖3—4是探測站點數(shù)量的比較。圖5—6是探測選擇時長的比較。圖3和圖4的探測站點數(shù)量的比較結(jié)果可知，算法PSA-NF和算法PSA-RD的探測站點數(shù)量隨著網(wǎng)絡(luò)節(jié)點數(shù)量的增加都在增加。其中，算法PSARD的探測站點數(shù)量增加較快，算法PSA-NF的探測站點數(shù)量增加相對較慢。圖3和圖4的比較可知，隨著網(wǎng)絡(luò)拓撲中網(wǎng)絡(luò)節(jié)點平均度數(shù)增加，2種算法的探測站點的數(shù)量都在降低。

圖3 平均度數(shù)為4的網(wǎng)絡(luò)拓撲的探測站點數(shù)量比較

圖4 平均度數(shù)為7的網(wǎng)絡(luò)拓撲的探測站點數(shù)量比較

圖5 和圖6的探測選擇時長的比較結(jié)果可知，算法PSA-NF和算法PSA-RD的探測選擇時長都隨著網(wǎng)絡(luò)拓撲規(guī)模的增加而增加。其中，算法PSA-RD的探測選擇時長增加較慢，算法PSANF的探測選擇時長增加較快。圖5和圖6的比較可知，隨著網(wǎng)絡(luò)拓撲中網(wǎng)絡(luò)節(jié)點平均度數(shù)增加，2種算法的探測選擇時長都在增加。

圖6 平均度數(shù)為7的網(wǎng)絡(luò)拓撲的探測選擇時長比較

綜上所述，雖然本文算法PSA-NF在探測選擇時長方面比算法PSA-RD較長，但是本文算法在2種網(wǎng)絡(luò)拓撲中選擇的探測站點數(shù)量都相對較少。在當(dāng)前的云計算環(huán)境下，可以通過增加虛擬機分配提升運算環(huán)境，從而降低探測選擇時長。所以，本文算法適合當(dāng)前的網(wǎng)絡(luò)運行環(huán)境。

4 結(jié)束語

智能電網(wǎng)快速發(fā)展的環(huán)境下，電力通信網(wǎng)規(guī)模較大導(dǎo)致探測站點部署效率低的問題。為解決此問題，本文針對電力通信網(wǎng)的特性提出了探測站點選擇的策略，以網(wǎng)絡(luò)內(nèi)在特征為依據(jù)，將文中算法與傳統(tǒng)算法進行比較，文中算法從電力通信網(wǎng)的網(wǎng)絡(luò)節(jié)點中，通過選擇最少的網(wǎng)絡(luò)節(jié)點作為探測站點，可以通過發(fā)送探測監(jiān)控到所有網(wǎng)絡(luò)節(jié)點的運行狀態(tài)信息，即以最少的探測站點達到最好的探測效果。下一步將基于本文的研究成果，進一步分析網(wǎng)絡(luò)節(jié)點刪除和增加的環(huán)境下，如何快速更新探測站點集合，減少網(wǎng)絡(luò)節(jié)點變動對主動探測產(chǎn)生的影響。