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

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

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

0 引言

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

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

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

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é)點(diǎn)具有概率性。

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

1.2 探測路徑的重疊特性

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

圖1 包含2個探測站點(diǎn)的網(wǎng)絡(luò)拓?fù)涫疽?/p>

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

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

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

1.3 最大故障數(shù)目

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

2 探測站點(diǎn)選擇算法

2.1 算法流程

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

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

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

式中:w，v∈N。

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

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

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

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

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

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

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

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

3 探測站點(diǎn)選擇算法驗(yàn)證分析

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

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

圖3 平均度數(shù)為4的網(wǎng)絡(luò)拓?fù)涞奶綔y站點(diǎn)數(shù)量比較

圖4 平均度數(shù)為7的網(wǎng)絡(luò)拓?fù)涞奶綔y站點(diǎn)數(shù)量比較

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

圖6 平均度數(shù)為7的網(wǎng)絡(luò)拓?fù)涞奶綔y選擇時長比較

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

4 結(jié)束語

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