基于網絡內在特征的電力通信網探測站點選擇算法

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

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

0 引言

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

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

為解決電力通信網規模較大導致探測站點部署效率低的問題，基于電力通信網的特性提出了探測站點選擇的策略，基于網絡內在特征的電力通信網探測站點選擇算法，從電力通信網的網絡節點中，選擇最少的網絡節點作為探測站點，通過發送探測監控到所有網絡節點的運行狀態信息，以最少的探測站點達到最好的探測效果。

1 電力通信網絡特征

1.1 動態路由特性

在電力通信網中，一般來說，網絡設備都啟用了動態路由協議。鑒于動態路由協議在路由選擇時具有動態特性，所以，探測是否經過某個網絡節點具有概率性。

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

1.2 探測路徑的重疊特性

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

圖1 包含2個探測站點的網絡拓撲示意

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

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

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

1.3 最大故障數目

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

2 探測站點選擇算法

2.1 算法流程

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

圖2 基于網絡內在特征的電力通信網探測站點選擇算法

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

式中:w，v∈N。

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

2.2 探測節點的選擇過程

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

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

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

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

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

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

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

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

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

圖3 平均度數為4的網絡拓撲的探測站點數量比較

圖4 平均度數為7的網絡拓撲的探測站點數量比較

圖5 和圖6的探測選擇時長的比較結果可知，算法PSA-NF和算法PSA-RD的探測選擇時長都隨著網絡拓撲規模的增加而增加。其中，算法PSA-RD的探測選擇時長增加較慢，算法PSANF的探測選擇時長增加較快。圖5和圖6的比較可知，隨著網絡拓撲中網絡節點平均度數增加，2種算法的探測選擇時長都在增加。

圖6 平均度數為7的網絡拓撲的探測選擇時長比較

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

4 結束語

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