基于最短路徑敏感度的光網絡關鍵鏈路識別

田云飛，彭玲艷，程紫運，韓東升，靳攀潤

(1.國網甘肅省電力公司 經濟技術研究院，蘭州 730050； 2.華北電力大學 電氣與電子工程學院，河北 保定 071003)

0 引 言

在電力光網絡中，對業務產生較大影響的鏈路稱為關鍵鏈路。關鍵鏈路的工作狀態對通信業務具有重要影響。為了客觀準確地識別電力光網絡的關鍵鏈路，有必要對鏈路關鍵性的量化模型及其識別算法開展深入研究。關鍵鏈路識別方法的研究成果主要包括：基于復雜網絡理論的全局和局部效能測度[1]；考慮業務需求和鏈路流量的測度[2]；基于節點對連通性的測度[3]；基于介中心度的測度[4]；基于加權自然連通度的測度[5]；文獻[6]給出了4種提高算法效率的加速技術；文獻[7-9]采用多種測度綜合的方法，保證識別結果更符合實際；文獻[10]給出了光纜長度服從一般極值分布的結論，并用來估計光纜和光放大器數量，甚至用來選擇光調制方式[11]；文獻[12]和[13]分別提出了兩種最短路徑長度的概率分布函數，用來間接得到網絡規劃與設計所需要的基礎數據。

在實際工程中，關鍵鏈路識別結果用于光網絡容量設計[7]和網絡運行質量評估[14]。同時，關鍵鏈路識別對網絡規劃設計和運行管理具有輔助決策作用。然而，現有研究成果存在效率低和針對性不強的問題，很少考慮“最小路徑時延”和“最高路徑可靠性”這兩種電力光網絡重點關注的測度。鑒于此，本文將以最短路徑敏感度為基礎，綜合考慮路徑跳數、時延和可靠性因素，來實現高效、靈活的電力光網絡關鍵鏈路識別。

1 最短路徑敏感度

電力光網絡可用無向、無環、有權圖表示，即G=(V,E,W)，式中：V為節點集，|V|=m；E為鏈路集，|E|=n；W為鏈路權重集，|W|=n。現實網絡中的光傳輸設備等價為節點，光纜等價為鏈路。鏈路權重可以有多種不同的物理含義。若鏈路權重設為1，則表示信息傳輸跳數為1；若鏈路權重為光纜長度，則表示實際的物理距離。同理，鏈路權重可以靈活地表示傳輸時延、不可靠性和傳輸容量等網絡性能參數。由于電力通信網更加關注實時性和可靠性，所以電力光網絡采用時延和可靠性作為鏈路權重更符合實際。

設圖G中的節點s和t之間存在多條路徑，并構成路徑集合，記為P(s,t)，s,t∈V，其中|P|=m(m-1)/2。任意一條路徑都是鏈路的集合，其長度等于路徑所包含鏈路的權重之和。第k條路徑的長度為

式中：wr(Pk(s,t))為路徑Pk(s,t)所包含第r條鏈路的權重；LPk(s,t)為路徑Pk(s,t)的長度。

如若任何兩節點間僅選擇一條最短路徑，那么，可以用全部最短路徑長度的平均值表示網絡效能，即

根據這一定義，Q值越大，網絡效能越差。若網絡節點均為理想的，那么，Q值受網絡結構和鏈路權重影響。在網絡結構保持不變的情況下，鏈路權重增加，會導致Q值增大。這意味著，鏈路狀態的惡化，會使網絡效能變差。把Q值隨鏈路權重的變化率定義為最短路徑敏感度。第d條鏈路的最短路徑敏感度表達式為

式中：wd為第d條鏈路的權重；W0為初始鏈路權向量。將式(2)帶入式(3)，并化簡，得到

對式(4)規范化后可得：

2 關鍵鏈路識別方法

2.1 確定鏈路權重

由前述內容可知，鏈路權重決定了最短路徑的選擇結果，決定關鍵鏈路的排序。根據電力光網絡的需求，本文考慮3種鏈路權重場景，分別是：路徑跳數最少、路徑時延最小和路徑可靠性最高。

(1) 路徑跳數最少

設路徑權重wr=1，利用最短路徑法得到基于跳數的最短路徑，路徑長度可實現跳數最少的目標。最短路徑敏感度可根據式(5)計算得到。

(2) 路徑時延最小

設光纜信號的傳輸時延為5 μs/km，光網絡設備的信號處理時延為50 μs。在不考慮數據分組傳輸時延的條件下，鏈路權重可表示為

式中：Lr為鏈路長度，單位為km；wr為第r條鏈路時延與端節點時延之和，單位為μs。

(3) 路徑可靠性最高

設光纜每千米的不可靠性為5×10-7，光網絡設備的不可靠性為5×10-5，鏈路權重可表示為

因為電力光網絡的可靠性非常高，所以鏈路和節點的串聯不可靠性近似等于二者之和，路徑的整體不可靠性等于各環節不可靠性之和。這種運算規律與最短路徑算法相一致，由此得到的最短路徑就是最可靠路徑。

2.2 計算最短路徑敏感度

最短路徑敏感度的計算過程分兩步實現。首先，在網絡拓撲結構和鏈路權重已知的條件下，利用最短路徑法計算所有節點對之間的最短路徑長度；然后，選擇鏈路d，并將其權重賦值為惡化閾值，重新計算最短路徑長度。兩次計算得到兩組長度為Np的數據；最后，根據兩組數據的差判斷得到鏈路d的長度Nd，再根據式(5)計算最短路徑敏感度。

2.3 鏈路關鍵性指標排序

算法按照路徑跳數最少、時延最小和可靠性最高等3種最短路徑目標，分別得到鏈路關鍵性指標，采用升序排序可得到關鍵鏈路的順序。為便于描述，用HOP表示最少跳數，DEL表示最短時延，REL表示最可靠。

2.4 算法描述

鏈路識別方法流程如圖1所示。算法首先輸入網絡拓撲結構、鏈路長度、時延參數和可靠性參數；然后，生成關聯矩陣和3種不同的鏈路權值，兩次重復計算最短路徑長度得到最短路徑敏感度；最后，將敏感度指標按升序排列得到鏈路排序，從而達到關鍵鏈路識別的目的。

圖1 鏈路識別方法流程圖

算法的關鍵環節是求解網絡的最短路徑。本文直接調用Matlab R2014a軟件的graphallshortestpaths(G)函數，實現對中規模電力光網絡的最短路徑計算。

3 算 例

3.1 算例說明

為了驗證所提方法的可行性和正確性，本文選擇一個省級電力主干光網絡作為實例，對其進行關鍵鏈路識別，并對結果進行分析。實例網絡的相關參數如表1所示。

表1 實例網絡的相關參數

表1中的m、n和L等參數通過對實例網絡的統計得到，Do和De由參考文獻[15]整理得到，Fo和Fe來源于實例網絡年度運行分析報告的統計數據；HT和T是根據實例網絡規模和鏈路長度分布情況，假設得到的。

實例網絡拓撲如圖2所示。圖中粗線部分表示識別出的關鍵鏈路示例。

圖2 實例網絡拓撲

3.2 結果分析

(1) 最關鍵鏈路識別

在已知網絡拓撲結構和光鏈路物理長度的條件下，本文基于HOP、DEL和REL 3類路徑目標，分別進行關鍵鏈路識別。算法調用函數graphallshortestpaths(b,'Directed',false)，計算得到163組最短路徑敏感度。前10個最關鍵鏈路的排序情況如表2所示。

表2 前10最關鍵鏈路排序

由表2可知，實例網絡的最關鍵鏈路是編號為66的鏈路，其次是編號為53、77、163、21和75的鏈路。鏈路權重采用的測度不同，關鍵鏈路識別結果略有差別。HOP、DEL和REL 3種識別結果中排序前10的鏈路，絕大多數相同，如表2中加粗字體所示。但有些鏈路的排序發生了變化，如編號為18、40、41、48和49等的鏈路。這說明利用不同測度會得到不同識別結果。

(2) 最不關鍵鏈路識別

同理，根據163組最短路徑敏感度，可得到10個最不關鍵鏈路的排序情況，如表3所示。

表3 10個最不關鍵鏈路排序

由表3可知，實例網絡的最不關鍵鏈路是編號為68、56、147、142和29的鏈路。HOP、DEL和REL 3種不同的識別方法所得結果絕大多數相同，如表3中加粗字體所示。但部分鏈路的排序結果不盡相同，如編號為134、90、155、126和140的鏈路。

圖2標出了相應鏈路的關鍵性信息。紅色和粉色粗線最為關鍵鏈路，綠色粗線為最不關鍵的鏈路。另外，從網絡的物理結構上看，識別出的關鍵鏈路屬于網絡骨干鏈路。

(3) 均值與方差

為了直觀表示各條鏈路的關鍵性，可視化3種關鍵鏈路識別方法得到的結果，如圖3所示。

圖3 3種關鍵鏈路識別結果

由圖可知，本文采用的3種識別方法所得結果絕大多數一致，個別鏈路存在差異。例如，鏈路40在HOP和REL方法中關鍵性排序在前10，而在DEL方法中排序為最不關鍵。鏈路41、48和49在HOP和REL方法中關鍵性排序落后，但在DEL方法中關鍵性排序超前。對這一現象的放大圖如圖4所示。

圖4 特殊鏈路關鍵性排序不一致情況

根據最短路徑敏感度分析結果，實例網絡全局的關鍵鏈路識別結果如表4所示。

表4 敏感度指標的分布參數

由表可知，最大值約為0.5，最小值為0，平均值約為0.05。這意味著，當一條最關鍵鏈路出現失效時，將有近50%的最短路徑受到影響，而不關鍵鏈路失效對最短路徑幾乎沒有影響。各類鏈路失效對網絡路徑的平均影響程度約為5%。標準差表征鏈路關鍵性差異化程度，其值越小，關鍵性越均衡，網絡效能越好。

3.3 討論

(1) 不同識別方法的必要性

本文以最短路徑敏感度為基本網絡效能測度對關鍵鏈路進行了識別。同時，本文又擴展到了基于HOP、DEL和REL等3種識別方法。實例驗證表明，這3種方法都能有效識別關鍵鏈路，且鏈路排序整體一致。利用Spearman相關系數檢驗，HOP_DEL為0.655，HOP_REL為0.986，DEL_REL為0.693。可見，HOP和REL兩種方法幾乎作用相同。

在特殊情況下，3種識別方法會得到不同結果。例如，鏈路40在HOP和REL方法中關鍵性非常高，但在DEL方法中卻最低。這種高步不一致的原因可以參考圖5加以分析。節點30和43之間存在兩條路徑，一條是鏈路40直接連接，另一條是41、48和49號3條鏈路串聯，其總長度低于鏈路40。這導致了識別結果不一致。

圖5 部分實際網絡

總體看來，綜合采用3種不同的識別方法是必要的，可發現更多的網絡特征，提供更加豐富的參考信息。

(2) 綜合考慮多種鏈路信息

鏈路的關鍵性不僅取決于網絡拓撲結構和鏈路長度，還與其他多種因素有關。以電力光網絡為例，光纜的類型主要有光纖復合架空地線(Optical Power Ground Wire, OPGW)、全介質自承式(All Dielectric Self Supporting, ADSS)光纜和普通光纜3種，其中OPGW可靠性和安全性最高。如果識別出的關鍵光纜是電壓等級較高的OPGW，那么電力通信網絡就能為業務質量提供保障。本文識別出的絕大多數最關鍵鏈路都是750 kV OPGW，這符合工程實際要求。另外，連接高電壓等級變電站和省市調度中心的鏈路應該具有較高的關鍵性，因為這些站點通常需要較大的傳輸容量，而且承載較重要的業務，所以節點信息需要融合到關鍵鏈路識別算法中去。為了保證高可靠性，電力光網絡對于沒有實現環形組網的鏈路通常采用雙光纜冗余配置，光纜冗余的相關信息也應該融合到關鍵鏈路識別中去。

4 結束語

本文針對電力光網絡關鍵鏈路識別問題，給出了基于最短路徑敏感度的3種有效識別關鍵鏈路的方法。研究結果表明，本文所提方法可以從跳數最少、時延最短和可靠性最高等3個方面對電力光網絡的關鍵鏈路進行有效識別，并具有實現簡單和一致性好等特點。研究結果能夠為電力通信網的規劃設計和運行維護提供參考。下一步的研究工作重點將放在融合電力通信網多源異構信息，綜合實現關鍵鏈路識別。