基于最短路徑敏感度的光網(wǎng)絡(luò)關(guān)鍵鏈路識別

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

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

0 引 言

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

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

1 最短路徑敏感度

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

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

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

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

根據(jù)這一定義，Q值越大，網(wǎng)絡(luò)效能越差。若網(wǎng)絡(luò)節(jié)點均為理想的，那么，Q值受網(wǎng)絡(luò)結(jié)構(gòu)和鏈路權(quán)重影響。在網(wǎng)絡(luò)結(jié)構(gòu)保持不變的情況下，鏈路權(quán)重增加，會導(dǎo)致Q值增大。這意味著，鏈路狀態(tài)的惡化，會使網(wǎng)絡(luò)效能變差。把Q值隨鏈路權(quán)重的變化率定義為最短路徑敏感度。第d條鏈路的最短路徑敏感度表達式為

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

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

2 關(guān)鍵鏈路識別方法

2.1 確定鏈路權(quán)重

由前述內(nèi)容可知，鏈路權(quán)重決定了最短路徑的選擇結(jié)果，決定關(guān)鍵鏈路的排序。根據(jù)電力光網(wǎng)絡(luò)的需求，本文考慮3種鏈路權(quán)重場景，分別是：路徑跳數(shù)最少、路徑時延最小和路徑可靠性最高。

(1) 路徑跳數(shù)最少

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

(2) 路徑時延最小

設(shè)光纜信號的傳輸時延為5 μs/km，光網(wǎng)絡(luò)設(shè)備的信號處理時延為50 μs。在不考慮數(shù)據(jù)分組傳輸時延的條件下，鏈路權(quán)重可表示為

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

(3) 路徑可靠性最高

設(shè)光纜每千米的不可靠性為5×10-7，光網(wǎng)絡(luò)設(shè)備的不可靠性為5×10-5，鏈路權(quán)重可表示為

因為電力光網(wǎng)絡(luò)的可靠性非常高，所以鏈路和節(jié)點的串聯(lián)不可靠性近似等于二者之和，路徑的整體不可靠性等于各環(huán)節(jié)不可靠性之和。這種運算規(guī)律與最短路徑算法相一致，由此得到的最短路徑就是最可靠路徑。

2.2 計算最短路徑敏感度

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

2.3 鏈路關(guān)鍵性指標排序

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

2.4 算法描述

鏈路識別方法流程如圖1所示。算法首先輸入網(wǎng)絡(luò)拓撲結(jié)構(gòu)、鏈路長度、時延參數(shù)和可靠性參數(shù)；然后，生成關(guān)聯(lián)矩陣和3種不同的鏈路權(quán)值，兩次重復(fù)計算最短路徑長度得到最短路徑敏感度；最后，將敏感度指標按升序排列得到鏈路排序，從而達到關(guān)鍵鏈路識別的目的。

圖1 鏈路識別方法流程圖

算法的關(guān)鍵環(huán)節(jié)是求解網(wǎng)絡(luò)的最短路徑。本文直接調(diào)用Matlab R2014a軟件的graphallshortestpaths(G)函數(shù)，實現(xiàn)對中規(guī)模電力光網(wǎng)絡(luò)的最短路徑計算。

3 算 例

3.1 算例說明

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

表1 實例網(wǎng)絡(luò)的相關(guān)參數(shù)

表1中的m、n和L等參數(shù)通過對實例網(wǎng)絡(luò)的統(tǒng)計得到，Do和De由參考文獻[15]整理得到，F(xiàn)o和Fe來源于實例網(wǎng)絡(luò)年度運行分析報告的統(tǒng)計數(shù)據(jù)；HT和T是根據(jù)實例網(wǎng)絡(luò)規(guī)模和鏈路長度分布情況，假設(shè)得到的。

實例網(wǎng)絡(luò)拓撲如圖2所示。圖中粗線部分表示識別出的關(guān)鍵鏈路示例。

圖2 實例網(wǎng)絡(luò)拓撲

3.2 結(jié)果分析

(1) 最關(guān)鍵鏈路識別

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

表2 前10最關(guān)鍵鏈路排序

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

(2) 最不關(guān)鍵鏈路識別

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

表3 10個最不關(guān)鍵鏈路排序

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

圖2標出了相應(yīng)鏈路的關(guān)鍵性信息。紅色和粉色粗線最為關(guān)鍵鏈路，綠色粗線為最不關(guān)鍵的鏈路。另外，從網(wǎng)絡(luò)的物理結(jié)構(gòu)上看，識別出的關(guān)鍵鏈路屬于網(wǎng)絡(luò)骨干鏈路。

(3) 均值與方差

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

圖3 3種關(guān)鍵鏈路識別結(jié)果

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

圖4 特殊鏈路關(guān)鍵性排序不一致情況

根據(jù)最短路徑敏感度分析結(jié)果，實例網(wǎng)絡(luò)全局的關(guān)鍵鏈路識別結(jié)果如表4所示。

表4 敏感度指標的分布參數(shù)

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

3.3 討論

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

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

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

圖5 部分實際網(wǎng)絡(luò)

總體看來，綜合采用3種不同的識別方法是必要的，可發(fā)現(xiàn)更多的網(wǎng)絡(luò)特征，提供更加豐富的參考信息。

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

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

4 結(jié)束語

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