[發明專利]基于網絡內在特征的電力通信網探測站點選擇算法

有效

• 申請號: 201910631794.4
• 申請日: 2019-07-12
• 公開（公告）號: CN110557275B
• 公開（公告）日: 2020-09-25
• 發明（設計）人: 莫穗江;王鋒;張欣欣;李瑞德;彭志榮;高國華;楊璽;湯銘華;陳嘉俊;張欣;梁英杰;廖振朝;李偉雄;童捷;張天乙
• 申請（專利權）人: 廣東電網有限責任公司;廣東電網有限責任公司江門供電局
• 主分類號: H04L12/24
• 分類號: H04L12/24;H04L12/26;H04L12/733
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 劉瑤云

本發明涉及電力診斷的技術領域，更具體地，涉及基于網絡內在特征的電力通信網探測站點選擇算法，包括以下步驟：S10.構建探測站點與陰影節點模型；S20.基于動態路由特性、探測路徑的重疊特性及最大故障數量特性，分析電力通信網的特性和探測站點選擇策略，從步驟S10中所述陰影節點集合中選擇第一個探測站點加入到探測站點集合中；S30.以最小化陰影節點集合為目標，從陰影節點模型SN中選擇下一個網絡節點作為探測站點；S40.基于最大故障數優化探測站點集合。本發明基于網絡內在特征分析、優化得到探測站點集合，通過選擇最少的網絡節點作為探測站點，可以通過發送探測監控到所有網絡節點的運行狀態信息，實現以最少的探測站點達到最好的探測效果。

技術領域

本發明涉及電力診斷的技術領域，更具體地，涉及基于網絡內在特征的電力通信網探測站點選擇算法。

背景技術

在故障診斷領域，探測站點的選擇標準是選擇能夠快速準確的完成故障定位、并且對網絡業務流量影響最小的網絡節點。當前的解決方案通常是將探測站點最優化部署問題轉換為最小頂點覆蓋問題。而該問題是存在多項式算法能夠解決的非決定性問題(NP問題)，現有解決方案都存在選擇的探測站點較多、成本較高的缺點，如：

中國專利CN201510530809.X公開了一種電力通信專網業務監測的探針部署方法和裝置，將電力通信網建模成一個頂點具有權重的無向圖，求解圖中的最小頂點覆蓋集，通過圖的最小頂點覆蓋集確定探測站點的部署規模，并基于節點權重給出探測站點的部署優先級。在主動監測的條件下，以最小化探測站點的部署代價和維護代價，減小了網絡探測對電力通信業務的影響。但是其無法解決等權重下的探測站點部署問題。

中國專利CN201610304469.3公開了一種基于改進貪心策略的探針部署方法，針對最小頂點覆蓋貪心策略中的最大度頂點不唯一問題，將電力數據網探測站點部署問題抽象為無向圖的最小頂點覆蓋問題，在傳統貪心策略的基礎上，限定覆蓋頂點選取方向且通過標記矩陣消除冗余頂點。但是，該算法過塑依賴節點的度數，若該節點的度數存在特殊值時，容易出現局部最優解的問題。

中國專利201910035585.3公開了一種基于貪婪算法的SDN矩陣網絡探針部署方法及設備，通過將SDN網絡矩陣轉換為無向圖，將圖中的點和邊按照是否可刪除進行判斷，通過遞歸算法將所有可刪除的點去除后，得到最終的探測站點部署節點分布圖，從而確定需要部署的探測站點位置。但是，該算法在構建網絡矩陣時對于網絡的拓撲進行了限制，如果應用到實際環境下的電力通信網，需要對網絡的拓撲進行較多的優化工作。

發明內容

本發明的目的在于克服現有技術的不足，提供一種基于網絡內在特征的電力通信網探測站點選擇算法，通過選擇較少的探測站點實現電力通信網的主動探測。

為解決上述技術問題，本發明采用的技術方案是：

提供一種基于網絡內在特征的電力通信網探測站點選擇算法，所述網絡包括有若干網絡節點，所述方法包括以下步驟：

S10.構建探測站點與陰影節點模型，使用p_i表示第i個探測站點，使用PS表示探測站點集合；使用n_j表示第j個網絡節點，使用N表示網絡節點集合，新建陰影節點集合SN，并將網絡節點集合N中所有網絡節點放入陰影節點集合；

S20.基于動態路由特性、探測路徑的重疊特性及最大故障數量特性，分析電力通信網的特性和探測站點選擇策略，從步驟S10中所述陰影節點集合中選擇第一個探測站點加入到探測站點集合中；

S30.以最小化陰影節點集合為目標，從陰影節點集合中選擇下一個網絡節點作為探測站點；

S40.基于最大故障數優化探測站點集合。