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

(國網(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í)時(shí)掌握電力通信網(wǎng)設(shè)備的運(yùn)行狀況。但是，現(xiàn)有網(wǎng)絡(luò)管理系統(tǒng)采用SNMP協(xié)議，被管設(shè)備周期性的給網(wǎng)絡(luò)管理系統(tǒng)上報(bào)設(shè)備運(yùn)行信息，容易導(dǎo)致網(wǎng)絡(luò)發(fā)生故障后才被管理人員發(fā)現(xiàn)，而且被管設(shè)備上報(bào)的信息不便于故障定位和恢復(fù)。

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

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

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

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

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

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

1.2 探測(cè)路徑的重疊特性

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

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

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

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

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

1.3 最大故障數(shù)目

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

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

2.1 算法流程

文中提出的基于網(wǎng)絡(luò)內(nèi)在特征的電力通信網(wǎng)探測(cè)站點(diǎn)選擇算法如圖2所示。該算法以探測(cè)站點(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)作為探測(cè)節(jié)點(diǎn)。下面對(duì)各個(gè)步驟進(jìn)行詳細(xì)解釋。

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

在步驟1中，新建探測(cè)站點(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個(gè)探測(cè)節(jié)點(diǎn)；如果存在多個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都有最大的度數(shù)，計(jì)算每個(gè)節(jié)點(diǎn)到其它節(jié)點(diǎn)的鏈路距離，選擇鏈路距離最短的核心節(jié)點(diǎn)作為第1個(gè)探測(cè)節(jié)點(diǎn)。假設(shè)第1個(gè)被選擇的探測(cè)節(jié)點(diǎn)為u，則采用公式(3)計(jì)算探測(cè)節(jié)點(diǎn)u對(duì)于網(wǎng)絡(luò)節(jié)點(diǎn)集合中任意網(wǎng)絡(luò)節(jié)點(diǎn)的探測(cè)路徑概率。

式中:w，v∈N。

在步驟3中，以最小化陰影節(jié)點(diǎn)集合為目標(biāo)，從網(wǎng)絡(luò)節(jié)點(diǎn)集合N中選擇下一個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)作為探測(cè)節(jié)點(diǎn)。在步驟4中，分析第3步得到的每個(gè)節(jié)點(diǎn)的獨(dú)立路徑數(shù)量PathCount(nj)。當(dāng)PathCount(nj)大于等于最大故障數(shù)量k時(shí)，網(wǎng)絡(luò)節(jié)點(diǎn)nj可以被探測(cè)站點(diǎn)探測(cè)到。當(dāng)PathCount(nj)小于最大故障數(shù)量k，但是等于網(wǎng)絡(luò)節(jié)點(diǎn)nj的度數(shù)時(shí)，此時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)nj可以被探測(cè)站點(diǎn)探測(cè)到。否則，表明網(wǎng)絡(luò)節(jié)點(diǎn)nj仍然還是陰影節(jié)點(diǎn)，需要進(jìn)一步尋找探測(cè)節(jié)點(diǎn)。此時(shí)，將網(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 探測(cè)節(jié)點(diǎn)的選擇過程

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

a.在網(wǎng)絡(luò)節(jié)點(diǎn)集合N中選擇下一個(gè)探測(cè)站點(diǎn)時(shí)，使用公式(4)計(jì)算候選探測(cè)站點(diǎn)c提供的到達(dá)陰影節(jié)點(diǎn)x的獨(dú)立探測(cè)路徑的非重疊函數(shù)BF，用于判斷陰影節(jié)點(diǎn)x是否屬于候選探測(cè)站點(diǎn)c的陰影節(jié)點(diǎn)。其中，n∈PSPath(x)∩Path(c，x)，表示“探測(cè)站點(diǎn)集合中的探測(cè)站點(diǎn)到達(dá)候選探測(cè)站點(diǎn)c的路徑”與“候選探測(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是候選探測(cè)站點(diǎn)c的陰影節(jié)點(diǎn)，并將x加入c的陰影節(jié)點(diǎn)集合S(c)。

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

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

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

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

為驗(yàn)證本文提出的基于網(wǎng)絡(luò)內(nèi)在特征的電力通信網(wǎng)探測(cè)站點(diǎn)選擇算法PSA-NF的性能，實(shí)驗(yàn)中將此算法與隨機(jī)選擇探測(cè)站點(diǎn)算法PSA-RD進(jìn)行了比較。比較的指標(biāo)包括選擇的探測(cè)站點(diǎn)數(shù)量和選擇探測(cè)站點(diǎn)的時(shí)長。實(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ù)對(duì)算法的影響，生成了平均度數(shù)為4和平均度數(shù)為7兩種網(wǎng)絡(luò)拓?fù)?。每次?shí)驗(yàn)中，設(shè)定故障同時(shí)發(fā)生的最大數(shù)量為4個(gè)。

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

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

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

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

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

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

4 結(jié)束語

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