基于多約束的電力通信網(wǎng)最大不相交路由選擇機(jī)制

黃漢華，唐 元，蔣 燁

（廣西電網(wǎng)公司電力調(diào)度控制中心，廣西 南寧 530022）

基于多約束的電力通信網(wǎng)最大不相交路由選擇機(jī)制

黃漢華，唐 元，蔣 燁

（廣西電網(wǎng)公司電力調(diào)度控制中心，廣西 南寧 530022）

在智能電網(wǎng)中，提高業(yè)務(wù)服務(wù)質(zhì)量并進(jìn)一步降低網(wǎng)絡(luò)風(fēng)險是目前主要的研究方向。如何選擇一條高可靠、穩(wěn)定而且低風(fēng)險的路由是智能電網(wǎng)中最關(guān)鍵的一環(huán)?，F(xiàn)有的很多算法考慮的因素過于單一而導(dǎo)致優(yōu)化程度不夠。所以，文章結(jié)合業(yè)務(wù)通道壓力與電力通信網(wǎng)的特殊性因素，提出了一種基于多條件約束下的最大不相交主備用路由選擇機(jī)制，并且通過某省電網(wǎng)通信拓?fù)溥M(jìn)行了仿真，闡述了該算法的優(yōu)越性。

電力通信網(wǎng)；最大不相交；路由；選擇機(jī)制；多約束

隨著智能電網(wǎng)的快速發(fā)展，電力系統(tǒng)呈現(xiàn)出多系統(tǒng)間協(xié)同通信日益頻繁的特點。電力系統(tǒng)生產(chǎn)部門也對電力通信網(wǎng)提出了更高的要求和標(biāo)準(zhǔn)。所以，在智能電網(wǎng)中，如何有效降低電力通信安全風(fēng)險成為電力系統(tǒng)亟需解決的問題之一。并且，隨著電力系統(tǒng)的規(guī)模不斷擴(kuò)大，現(xiàn)階段的路由算法難以滿足需求的不斷提高。因此，提高電力通信網(wǎng)的業(yè)務(wù)服務(wù)質(zhì)量（Quality of Service，QoS）[1]并進(jìn)一步降低網(wǎng)絡(luò)風(fēng)險以適應(yīng)不斷擴(kuò)大的需求是目前的主要研究方向。

電力通信網(wǎng)在部署業(yè)務(wù)時，通常采用基于可用性路由（Availability-Aware Routing，AAR）[2]和基于負(fù)載均衡（Load Balancing，LB）[3-6]的路由分配策略。文獻(xiàn)[2]在AAR的基礎(chǔ)上提出了可靠性更高的3W算法。LB算法方面，文獻(xiàn)[3]采用啟發(fā)式KSP算法，KSP算法的一種實現(xiàn)策略，求出前K條帶寬最大的路由，實現(xiàn)可靠性的提高。然而3W算法的缺陷在于會出現(xiàn)業(yè)務(wù)過于集中的現(xiàn)象，無法保證服務(wù)質(zhì)量，而LB算法僅以帶寬為考慮因素，沒有考慮業(yè)務(wù)的權(quán)重和壓力均衡。所以，文獻(xiàn)[4]考慮了SDN網(wǎng)絡(luò)中的負(fù)載均衡，文獻(xiàn)[5]和文獻(xiàn)[6]基于電力通信網(wǎng)中的業(yè)務(wù)重要度論述了負(fù)載均衡，比3W和一般的LB算法有更高的可靠性。但是，這些算法都沒有考慮關(guān)鍵業(yè)務(wù)的備用路由，所以關(guān)鍵業(yè)務(wù)的服務(wù)質(zhì)量提高有限。

按照電力行業(yè)的要求，電力通信網(wǎng)中的關(guān)鍵業(yè)務(wù)如繼電保護(hù)等需要配置主備用雙路由來保證該業(yè)務(wù)的高可靠性[7]。其次，需要結(jié)合設(shè)備老化情況、動力環(huán)境情況、光纜特性（如是否同類型光纜、是否跨高速/高鐵光纜等）等電力通信網(wǎng)中的特殊因素來規(guī)劃路由。針對以上問題并結(jié)合電力通信網(wǎng)的實際狀況，本文提出一種基于多條件約束下的最大不相交主備用路由算法（Multi-Constrained Maximally Disjoint Routing Algorithm，MCMDRA）。

采用多約束條件下的路由分配策略可以使得業(yè)務(wù)路由滿足多種約束，能夠更好地保證可靠性和服務(wù)質(zhì)量，并且，對關(guān)鍵業(yè)務(wù)采用主備用路由方法，能夠給業(yè)務(wù)提供環(huán)路保護(hù)，進(jìn)一步降低了通信風(fēng)險。

1 問題建模

如圖1所示，在通信拓?fù)渲?，省級的電力通信網(wǎng)跨越多個地區(qū)，有可能橫穿高速高鐵，而且光纜類型不統(tǒng)一（OPWG/ADSS）。所以業(yè)務(wù)路由有可能使用多條光纜而且在多種光纜類型中不斷切換，這種現(xiàn)象會對業(yè)務(wù)質(zhì)量造成很大影響。同時，業(yè)務(wù)路由有可能跨越高速高鐵，這也是一種不容忽視的對QoS產(chǎn)生影響的因素。經(jīng)過大量調(diào)研，我們發(fā)現(xiàn)這些新因素對電力通信網(wǎng)的穩(wěn)定運行產(chǎn)生了很大影響。

為了解決該問題，首先引入節(jié)點風(fēng)險度（Node Risk Degree，NRD）[6]、邊風(fēng)險度（Edge Risk Degree，ERD）[6]、業(yè)務(wù)通道壓力（Service Path Pressure，SPP）、業(yè)務(wù)通道均衡度（Service Path Balance Degree，SPBD）、業(yè)務(wù)通道總壓力（Overall Service Path Degree，OSPD）、路由相交度（Route Interaction Degree，RID）、路由可靠度（Route Reliability Degree，RRD）[8]的概念。

1.1 節(jié)點風(fēng)險度

式中S(vi)為節(jié)點上承載的業(yè)務(wù)集合，P(vi)為節(jié)點i的失效概率，與可用度A(vi)相關(guān)。Wk為節(jié)點i承載的第k個業(yè)務(wù)的權(quán)重，權(quán)重指標(biāo)將在接下來的章節(jié)給出。風(fēng)險的定義是發(fā)生概率與產(chǎn)生的影響的乘積[9]。

圖1 電力通信網(wǎng)拓?fù)鋱D

1.2 邊風(fēng)險度

式中S(eij)為邊eij上承載的業(yè)務(wù)集合，Wk為邊eij承載的第k個業(yè)務(wù)的權(quán)重，P(eij)為邊eij的失效概率，與可用度相關(guān)。TTReij和TBFeij為修復(fù)時間（Time To Repair，TTR）和正常運行時間（Time Between Failure，TBF）[2]。其中SPP由NRD，ERD和使用年限決定。

1.3 業(yè)務(wù)通道壓力

式中c為承載業(yè)務(wù)的系數(shù)，在電力系統(tǒng)中，低電壓鏈路如220 kV線路因為需要有時會承載500 kV或者1 000 kV的高壓業(yè)務(wù)。當(dāng)出現(xiàn)低電壓鏈路承載高電壓業(yè)務(wù)時，ERD會乘以c常數(shù)。N為邊eij的使用年限?？紤]了電網(wǎng)的實際因素，在文獻(xiàn)[6]的基礎(chǔ)上，提出了業(yè)務(wù)通道壓力的概念。

1.4 業(yè)務(wù)通道均衡度

業(yè)務(wù)通道均衡度用來衡量整個網(wǎng)絡(luò)的通道壓力平均度，SPBD越小，每條通道的壓力越均衡。為業(yè)務(wù)通道壓力的平均值，為節(jié)點風(fēng)險度平均值。

1.5 業(yè)務(wù)通道總壓力

業(yè)務(wù)通道總壓力為整個網(wǎng)絡(luò)節(jié)點和通道的所有壓力之和。

1.6 路由相交度

路由的相交度（Route Interaction Degree，RID）表示路由的主備用路由共用的節(jié)點和邊占總節(jié)點和邊的個數(shù)的比例，由邊相交度（Edge Interaction Degree，EID）和節(jié)點相交度（Vertex Interaction Degree，VID）共同決定。實際情況中，邊的可靠度比節(jié)點的可靠度低得多，所以邊的相交度對路由的可靠性影響更大。所以，RID的大小首先取決于EID，相同情況下，才會使用節(jié)點相交度判別，當(dāng)且僅當(dāng)RID和VID都相等，兩個主備用路由的相交度才相等。

EID為公共邊的個數(shù)E(public)占E(route1∪route2)邊個數(shù)的比例，E(route1∪route2)代表主備路由邊的并集個數(shù)。VID為公共節(jié)點V(public)的個數(shù)占V(route1∪route2)節(jié)點個數(shù)的比例，V(route1∪route2)代表主備路由節(jié)點的并集個數(shù)。

1.7 業(yè)務(wù)可靠度

式（12）定義了業(yè)務(wù)路由的可靠程度，R(vj)表示節(jié)點可靠度，R(ek)表示鏈路可靠度，式（13）衡量了業(yè)務(wù)的主備用路由的可靠性[8]。

圍繞上述定義，本文將基于業(yè)務(wù)通道壓力（SPP）來優(yōu)化網(wǎng)絡(luò)，使得業(yè)務(wù)通道均衡度降低，業(yè)務(wù)通道總壓力和主備用路由的相交度都盡可能地低。

2 基于業(yè)務(wù)通道壓力的主備用路由選擇機(jī)制

傳統(tǒng)的路由選擇算法在線路發(fā)生故障以后，需要排除掉故障的邊和節(jié)點通過再次運行為業(yè)務(wù)分配路由。但是，當(dāng)業(yè)務(wù)重要度很高時，這種做法效率低下，無法滿足現(xiàn)在的電力通信網(wǎng)對故障時間的要求。所以，關(guān)鍵業(yè)務(wù)的備份路由是非常有必要的。其次，若雙路由業(yè)務(wù)均采用單約束的最大不相交雙路由算法，會導(dǎo)致業(yè)務(wù)過于集中從而導(dǎo)致部分鏈路過于擁塞。另外，根據(jù)電網(wǎng)的實際運行情況，還需要考慮業(yè)務(wù)的光纜類型，是否跨越高速高鐵等因素。

文獻(xiàn)[8]在基于Bhandri算法的基礎(chǔ)上提出了一種電力通信網(wǎng)最大不相交雙路由配置方法。但是該算法基于Dijkstra作為主路由，而且配置的雙路由只考慮相交度。同時為了保證路由的最大不相交，該算法還會改變主路由，這種做法會導(dǎo)致部分鏈路節(jié)點的壓力過大。所以我們改進(jìn)了Bhandri算法，在保證主路由是不變的條件下尋找最大不相交備用路由。

多條件約束下的最大不相交主備用路由算法（Multiple Constraint Maximally Disjoint Routing Algorithm，MCMDRA）基于KSP和改進(jìn)的Bhandri算法，能夠降低網(wǎng)絡(luò)總壓力并且使得主備用路由的相交度最小。

（1）首先按照業(yè)務(wù)權(quán)重對需要分配的路由進(jìn)行排序，保證重要的業(yè)務(wù)先分配。

（2）基于KSP算法對該業(yè)務(wù)選取前K條最優(yōu)路由（即壓力最小的路由），然后進(jìn)行篩選。

篩選方法如下：首先將前K條業(yè)務(wù)按照0/A光纜切換次數(shù)從小到大排序。切換次數(shù)相等的情況下，則按照是否跨越高速高鐵排序，如果沒有跨越高速高鐵的路由的通道壓力比跨高速高鐵的線路壓力值低或者不高于某個適合的常數(shù)C，則將高通道壓力的路由排到前面。但是，若沒有跨越高速高鐵的SPP值比跨越高速高鐵的線路SPP值大于常數(shù)C，即則還是將跨越高速高鐵的路由排序到前面。

（3）排序完成后選取前兩條路由，分別使用改進(jìn)的Bhandri最大不相交路由算法為兩條路由選取備用路由，然后選擇相交度最小的雙路由作為該業(yè)務(wù)的主備用路由。

（4）為業(yè)務(wù)分配好路由以后，則由該業(yè)務(wù)引起的通道壓力值的改變需要更新到拓?fù)渲小?/p>

（5）所有業(yè)務(wù)分配完成，結(jié)束。否則，跳轉(zhuǎn)2[10-11]。

3 仿真分析

實驗從業(yè)務(wù)通道總壓力、業(yè)務(wù)通道均衡度、關(guān)鍵業(yè)務(wù)可靠性3個角度來分析算法的性能、業(yè)務(wù)通道總壓力和業(yè)務(wù)通道均衡度與SRBM算法，3W算法做了實驗對比。在關(guān)鍵業(yè)務(wù)的可靠性和業(yè)務(wù)的相交度上，與傳統(tǒng)的RF算法做了對比。實驗結(jié)果如圖2—3所示。

圖2展示了業(yè)務(wù)通道總壓力隨業(yè)務(wù)個數(shù)的變化情況。通過實驗可以發(fā)現(xiàn)，在3種算法的比較下，MCMDRA算法比SRMB和3W算法有更低的通道總壓力，使得全網(wǎng)的可靠性得到提高。在通道壓力均衡度方面，圖3展示MCMDRA算法并不比SRMB算法更優(yōu)秀，只比3W算法稍好，因為MCMDRA算法考慮了跨越高速高鐵的因素和光纜類型切換次數(shù)的因素，這些因素對于電力通信網(wǎng)的可靠性也有很大的影響，所以優(yōu)先考慮該因素并適當(dāng)犧牲通道壓力均衡度是合理的。

4 結(jié)語

為了提高電力通信網(wǎng)的業(yè)務(wù)服務(wù)質(zhì)量，滿足電力通信網(wǎng)在實際運行中提出的新要求和新挑戰(zhàn)，本文提出了基于多條件約束下的最大不相交主備用路由算法。該算法改善了路由選擇只局限于通道壓力的單一因素，并且考慮電力通信網(wǎng)的實際情況。實驗表明，MCMDRA算法在業(yè)務(wù)可靠性上有進(jìn)一步的提高。接下來的工作將基于以上內(nèi)容，研究電力通信網(wǎng)的故障恢復(fù)機(jī)制，更好地保證電力通信網(wǎng)的服務(wù)質(zhì)量。

圖2 通道總壓力隨業(yè)務(wù)個數(shù)的變化情況

圖3 通道壓力均衡度隨業(yè)務(wù)個數(shù)的變化情況

[1] HUNG M H，WANG C H，HE Y.A real-time routing algorithm for end-to-end communication networks with QoS requirements[C].Matsue：2016 Third International Conference on Computing Measurement Control and Sensor Network（CMCSN），2016：186-189.

[2] TORNATORE M，DIKBIYIK F，MUKHERJEE B.(3W-)Availability-aware routing in optical WDM networks：when，where and at what time[C].Stockholm：2011 13th International Conference on Transparent Optical Networks，2011：1-5.

[3] LIU N，CHEN X.Overlay multicasting at a path-level granularity for multihomed service nodes[C].Nanjing：International Conference on Information Science and Technology，2011：939-946.

[4] ATTARHA S，HOSSEINY K H，MIRJALILY G，et al.A load balanced congestion aware routing mechanism for software defined networks[C].Tehran：2017 Iranian Conference on Electrical Engineering（ICEE），2017：2206-2210.

[5] XING N，XU S，ZHANG S，et al.Load balancing-based routing optimization mechanism for power communication networks[J].China Communications，2016（13）：169-176.

[6] 曾慶濤.基于風(fēng)險均衡的電力通信業(yè)務(wù)的路由分配機(jī)制[J].電子與信息學(xué)報，2013（6）：1318-1324.

[7] YU Z，MA F，LIU J，et al.An ef fi cient approximate algorithm for disjoint QoS routing[J].Mathematical Problems in Engineering，2013（6）：1-9.

[8] 何玉鈞，陳冉，張文正，等.一種電力通信網(wǎng)最大不相交雙路由配置方法[J].電力系統(tǒng)保護(hù)與控制，2016（5）：60-68.

[9] AVEN T.Practical implications of the new risk perspectives[J].Reliability Engineering amp; System Safety，2013（2008）：136-145.

[10] MARTINS E Q V，MANUEL F，PIRES A.A shortest paths ranking algorithm[J].European Journal of Operational Reaearch，1990（1）：188-191.

[11] BHANDARI R.Optimal diverse routing in telecommunication fiber networks[C].Toronto：INFOCOM 94 NETWORKING for Global Communications，IEEE，1994：1498-1508.

Maximum non-intersection routing selection mechanism of power communication network based on multiple constraints

Huang Hanhua, Tang Yuan, Jiang Ye
（Guangxi Power Grid Co., Ltd., Electric Power Dispatch amp; Control Center, Nanning 530022, China）

In the smart grid, improving the quality of business services and further reducing the network risk is the main research direction. How to choose a highly reliable, stable and low-risk routing is the most critical part of the smart grid. Many of the existing algorithms to consider the factors are too single and lead to the degree of optimization is not enough. Therefore, based on the special factors of traffic channel pressure and power communication network, this paper proposes a maximum non-intersection primary and secondary routing selection mechanism based on multi-condition constraints, and simulates it through a communication topology of a province’s power grid, and expounded the superiority of the algorithm.

power communication network; maximum non-intersection; routing; selection mechanism; multiple constraints

廣西電網(wǎng)公司科技項目；項目編號：040000〔2016〕030100ddkzzx00028。

黃漢華（1986— ），男，廣西南寧人，工程師，學(xué)士；研究方向：電力光通信。