一種改進的啟發(fā)式Ｐ圈構(gòu)造算法

摘 要:原有啟發(fā)式P圈構(gòu)造算法Grow沒有考慮到在對基本圈上的一條邊擴張時可能會抑制其他邊的擴張，從而失去一些先驗效率較高的P圈。針對這一缺點對Grow算法進行了改進。改進后的算法根據(jù)所有的圈上邊擴張后得到的P圈先驗效率的高低順序，優(yōu)先選擇引入的P圈具有最高先驗效率的邊進行擴張，因此每次擴張都最大可能地提高P圈的先驗效率，而且P圈平均跳數(shù)基本不變。仿真結(jié)果表明，此算法可以在減少備選P圈數(shù)量的同時，提高網(wǎng)絡(luò)的資源利用率。

關(guān)鍵詞:光網(wǎng)絡(luò); 保護; 生存性; 預(yù)置圈

中圖分類號:TP309文獻標志碼:A

文章編號:1001-3695(2009)09-3219-03

doi:10.3969/j.issn.1001-3695.2009.09.005

Improved heuristic algorithm for generating P-cycles

GAN Bao-bao， JIANG Hong-liang， SUN Xiao-yin， XU Rong-qing

(College of Optoelectronic Engineering， Nanjing University of Posts Telecommunications， Nanjing 210003， China)

Abstract:Since the existing heuristic algorithm named Grow did not consider that expansion on a cycle-link might restrict expansion on another one， therefore some P-cycles with high AE might be lost. For this reason， this paper improved Grow algorithm. Among all the on-cycle spans， the improved algorithm first chose the one which could get the P-cycle with the highest AE after expansion， so AE of P-cycle would be increased as high as possible， and average number of hops was more or less the same with Grow’s. Finally， the simulation results show that the algorithm can reduce the number of candidate P-cycles， and at the same time achieve better capacity utilization than Grow.

Key words:optical network; protection; survivability; preconfiguration cycle

自從波分復(fù)用技術(shù)廣泛應(yīng)用以來，通信網(wǎng)絡(luò)的容量大幅度提高[1]，給人們生活中的信息傳遞帶來了速度上的飛躍，但同時也帶來很大的風(fēng)險，一旦網(wǎng)絡(luò)中斷，其造成的損失可能是災(zāi)難性的。因此網(wǎng)絡(luò)生存性自然成為所有人關(guān)心的問題。在網(wǎng)絡(luò)生存性技術(shù)中，恢復(fù)時間和資源利用率是最重要的兩個評價標準。在已有的生存性技術(shù)中，環(huán)網(wǎng)可以實現(xiàn)快速的保護，但是資源利用率較低;格狀網(wǎng)有著較好的資源利用率，恢復(fù)時間卻遠大于環(huán)網(wǎng)。基于將兩者優(yōu)點結(jié)合起來的考慮，1998年，Grover等人[2]提出了P圈的概念，P圈是利用空閑資源預(yù)先在網(wǎng)絡(luò)中配置好的圈狀結(jié)構(gòu)，P圈和環(huán)網(wǎng)中的自愈環(huán)最大的不同是P圈不但可以提供圈上邊的保護，而且可以提供跨接邊的保護。

如圖1所示，圖中線條加粗部分是利用空閑資源配置好的P圈A-B-C-F-D-E-A。在圖2中，當(dāng)跨接邊AF失效時，P圈可以同時有兩條通路A-B-C-F和A-E-D-F提供保護;在圖3中，當(dāng)圈上邊AB失效時，P圈可以實現(xiàn)像自愈環(huán)一樣的自動倒換來保護A-B的通路。因此P圈可以為圈上邊提供一倍業(yè)務(wù)的保護，并保護跨接邊上兩倍的業(yè)務(wù)。P圈在保留了環(huán)網(wǎng)快速保護速度的同時提高了資源利用率，發(fā)展前景十分看好。

1 相關(guān)工作

P圈實用化的重點和難點在于如何利用空閑資源進行配置，以取得最好的保護效果，這是一個最優(yōu)化的問題。P圈概念提出以來，國內(nèi)外學(xué)者在關(guān)于P圈配置的問題上進行了很多研究，提出了很多方法，這些方法大致可以分為三類:a)完全最優(yōu)化方法，主要思想是先枚舉網(wǎng)絡(luò)拓撲中所有簡單圈作為備選P圈，再利用整數(shù)線性規(guī)劃(ILP)得到最優(yōu)化的解，如文獻[2]等。該方法對于小型網(wǎng)絡(luò)可以使用，當(dāng)網(wǎng)絡(luò)節(jié)點和鏈路數(shù)量很大時，計算所有簡單圈并且再去找到最優(yōu)化的解是非常復(fù)雜和困難的，需要耗費很長時間，因此這種方法不適合大型網(wǎng)絡(luò)。b)啟發(fā)式算法與最優(yōu)化方法結(jié)合，如文獻[3]等。該算法是指根據(jù)約束條件找到其中一部分性能比較好的圈，因此運算速度比傳統(tǒng)的枚舉法快得多，構(gòu)造的圈性能良好。此類方法先利用啟發(fā)式算法在網(wǎng)絡(luò)拓撲中構(gòu)造一定量的備選圈，然后利用這些備選圈進行最優(yōu)化組合得到最優(yōu)解。這仍然要用到線性規(guī)劃(LP)，需要大量的計算時間，不利于網(wǎng)絡(luò)擴展。c)完全啟發(fā)式算法，先利用啟發(fā)式算法構(gòu)造出性能較好的一定量的備選圈，再結(jié)合實際網(wǎng)絡(luò)中工作容量將可以實際提供保護能力較大的備選圈優(yōu)先配置，如文獻[4]等。文獻[5]提出了一種新的啟發(fā)式算法，將第一步構(gòu)造備選P圈和第二步選擇P圈結(jié)合為一步，根據(jù)實際網(wǎng)絡(luò)中P圈的冗余率來選擇冗余率最小的P圈，可以減少配置P圈的數(shù)量并提高資源利用率;但這種方法的整體性較差，算法應(yīng)用尚未成熟。

在已經(jīng)提出的這些啟發(fā)式算法里，2003年Stamatalakis等人[4]提出的CIDA-Grow算法計算時間極少，資源利用率接近最優(yōu)化的結(jié)果。其中Grow算法是用來構(gòu)造備選P圈，CIDA算法是用來配置P圈。筆者在對Grow算法的研究中發(fā)現(xiàn)，Grow算法在基本圈的擴張問題上沒有考慮到邊的擴張順序?qū)ψ罱K結(jié)果的影響，而邊的擴張順序不同，最終結(jié)果也是不同的。為了更好地選擇擴張邊的順序，本文提出了一種改進的算法mateGrow。

2 MateGrow算法的提出

2.1 P圈的評價標準

為了量化單個P圈的保護效率，本文定義一個性能指標[6]:先驗效率AE(P)，即這個P圈能保護的所有工作容量和配置這個圈所要消耗網(wǎng)絡(luò)容量的比值。

AE(P)=∑i∈sXp，i/∑i∈s，Xp，i=1Ci(1)

其中:s表示所有鏈路的集合，Ci表示每條鏈路上的代價，Xp，i表示這個P圈能夠為鏈路i提供的保護通路的個數(shù)。容易知道，當(dāng)鏈路i是圈上邊時，Xp，i=1;當(dāng)i是跨接邊時，Xp，i=2;當(dāng)i既不是圈上邊也不是跨接邊時，Xp，i=0。一個P圈具有比較多的跨接邊時，其先驗效率AE比較高。

2.2 SLA算法

文獻[7]提出了SLA(straddling link algorithm)，主要思想是將一條邊i的兩個端點作為起點和終點，在這兩點之間找出兩條節(jié)點分離的路，并且這兩條路都不包含邊i，則這兩條節(jié)點分離的路首尾連接就成為一個簡單P圈，這個P圈至少含有一條跨接邊i。SLA的速度很快，產(chǎn)生的P圈數(shù)量不超過所有邊的數(shù)量，但是因為產(chǎn)生的P圈一般只有一條跨接邊，其先驗效率AE很低。

2.3 SP-Add和Grow算法

基于增加跨接邊的考慮，文獻[4]提出了SP-Add和Grow算法，SP-Add算法是在已有的簡單圈上進行擴張，將一條圈上邊i的兩個端點作為起點和終點，找到一條起點到終點的最短路徑s，這條路徑s與原來的圈是節(jié)點分離的;將邊i刪除，路徑s和P圈的剩下部分首尾連接組成了新的P圈，邊i變成了跨接邊，從而提高了圈的先驗效率AE。

Grow主要步驟是這樣的:a)用SLA在網(wǎng)絡(luò)拓撲圖中構(gòu)造一組P圈A;b)對A中的每個P圈上的每條邊運行SP-Add算法，得到一組P圈B;c)對于B中的每個P圈，在其圈上的一條邊運行SP-Add算法，得到一個新的P圈，這時在這個新的P圈上的一條邊上運行SP-Add算法。如果不能得到新的P圈，則接著在下一條邊上擴張;如果得到了新的P圈，那么每次得到新的P圈后，都將新的P圈作為擴張使用的基本圈，直到最終的P圈上的任何一條邊都不能再構(gòu)造新的P 圈。在這個過程的中間環(huán)節(jié)產(chǎn)生的P圈也將被保留，放在最終的備選P圈中。

為了更形象地說明Grow算法，舉例如下，在圖4中，假設(shè)一個基本圈為a-b-e-a，其先驗效率AE=3/3=1。在eb邊上使用SP-Add算法，得到新的P圈a-b-c-e-a，邊eb變成了跨接邊，新P圈先驗效率AE=6/4=1.5。接著對這個新的P圈上的邊bc進行擴張，找不到與原來的圈節(jié)點分離的路，可見bc邊不能擴張;此時轉(zhuǎn)向下一條邊ec，運行SP-Add算法得到又一個新的P圈a-b-c-d-e-a，這時新的P圈上任何一條邊都不能再擴張，算法終止。最終的P圈具有兩個跨接邊be和ce，顯然先驗效率AE=9/5=1.8，比原來提高了很多。

在上例中，如果在圈a-b-e-a中先選擇ae作為擴張邊，最終得到的圈為a-f-d-c-e-b-a，其先驗效率為2。可見，如果在同一個P圈上選擇擴張邊的順序不同，最終結(jié)果會有差異，這是因為一個圈上邊的擴張可能會抑制另外的邊進行擴張。而文獻[4]中提出的Grow算法沒有考慮到這一點，在P圈的擴張時沒有選擇邊的順序，會構(gòu)造一些質(zhì)量相對較低的P圈，這樣不但增加了備選P圈的數(shù)量，也非常可能降低其整體質(zhì)量。如果要將P圈所有可能的擴展結(jié)果都計算出來，又將大大增加計算的時間和P圈數(shù)，如何在減少P圈數(shù)量的同時增加或不降低其先驗效率，本文提出了mateGrow算法，文獻[8]的研究表明，降低P圈的數(shù)量可以減少管理上的負擔(dān)。

2.4 MateGrow算法

MateGrow算法的主要思想是這樣的，在對一個P圈擴張時，優(yōu)先選擇引進跨接邊較多的邊進行擴張。如果引進的跨接邊同樣多，優(yōu)先選擇引入圈上邊較少的邊進行擴張。在引入跨接邊和圈上邊同樣多的情況下，優(yōu)先選擇引入所有節(jié)點的平均度數(shù)較大的邊進行擴張。MateGrow算法的主要原理是這樣的:在引入跨接邊時，引入較多的跨接邊，其先驗效率AE更大;而跨接邊的數(shù)量相同時，圈上邊較少的P圈先驗效率AE更大。當(dāng)跨接邊和圈上邊的數(shù)量都相等時，度數(shù)較大的節(jié)點有更多的可能引入新的跨接邊。如圖2所示，假設(shè)以P圈d-c-e-d為基本圈，有兩條邊ce和ed可以進行擴張，引入跨接邊都為一條，而ce引入的新的圈上邊為兩條(cb和be)，de則為三條(ea、af和fd)。按照mateGrow算法，用ce進行擴張得到新的P圈d-c-b-e-d，接著以這個新的P圈為基礎(chǔ)圈，同樣有兩條邊be和ed可以選擇，但是以ed為擴張邊計算將得到兩條跨接邊ed和ab，而用be只能增加一條跨接邊be，應(yīng)該選擇ed為擴張邊，最終得到的P圈為d-c-b-e-a-f-d。

2.5 MateGrow算法產(chǎn)生備選P圈的性能檢驗

本文對Italian(21個節(jié)點36條邊)、COST239(11個節(jié)點26條邊)、NSF(14個節(jié)點21條邊)和USA(28個節(jié)點45條邊)四種網(wǎng)絡(luò)進行構(gòu)造備選P圈的仿真，步驟如下:a)對網(wǎng)絡(luò)拓撲運行SLA算法產(chǎn)生一組P圈A;b)對A中每個P圈上的每條圈上邊運行SP-Add算法得到一組P圈B;c)對B中每個P圈運行mateGrow算法得到一組P圈C1。作為對比，同樣運行Grow算法得到另外一組P圈C2，Grow算法中擴張邊的順序是順時針或者逆時針。因為a)b)產(chǎn)生的P圈是相同的，僅比較c)產(chǎn)生的P圈C1、C2。表1中的代價代表實際的物理距離。

在表1中可以看到，NSF網(wǎng)絡(luò)中mateGrow和Grow算法得到的P圈數(shù)量和質(zhì)量是一樣的，這是因為NSF網(wǎng)絡(luò)的節(jié)點和邊的數(shù)量較少，在擴張時沒有很多選擇空間。表2的Italian網(wǎng)絡(luò)中，mateGrow算法得到P圈數(shù)量減少了三分之一的情況下，平均AE仍然稍微高于Grow，而且跳數(shù)和代價均少于Grow算法。在USA、COST239中，如表3和4，mateGrow算法的優(yōu)勢更加明顯，在P圈數(shù)量減少的情況下，平均AE高于Grow算法，圈平均代價相對較低，只是COST239中的平均跳數(shù)稍高一點。以上所得到的結(jié)果是因為在圈擴張時選擇了質(zhì)量較高的P圈，而丟棄了質(zhì)量相對較低的P圈，不像Grow算法那樣沒有選擇地進行擴張。MateGrow算法選擇較好的邊進行擴張可以保證每次所得到的P圈都是這次計算的最佳選擇，該理論分析和計算的結(jié)果是一致的。

3 容量分配的仿真及數(shù)據(jù)分析

P圈的先驗效率只表示其潛在的保護能力。在實際網(wǎng)絡(luò)中，P圈的保護能力取決于其保護的實際工作容量和自身配置所消耗的空閑容量的比值。本文定義一個指標——保護效率[9]ER(P):

ER(P)=∑i∈lWp，i/∑i∈lSp，i(2)

其中:Wp，i表示當(dāng)前情況下鏈路i上的可以被該P圈保護的工作流量，Sp，i表示配置此P圈在鏈路i上所消耗的空閑容量。利用保護效率的大小順序就可以選擇保護效率高的P圈優(yōu)先配置到網(wǎng)絡(luò)中去。文獻[4]提出的CIDA算法正是基于這樣的原理，這是一種啟發(fā)式算法，耗時短，效果接近最優(yōu)化的解法。

現(xiàn)在使用mateGrow和Grow算法構(gòu)造的P圈，分別都加上SLA算法、最小圈算法[4]產(chǎn)生的P圈作為兩組備選P圈，再用CIDA算法進行仿真。在USA、Italian、COST239中，網(wǎng)絡(luò)連接的需求是任意的，每條邊上的工作流量的最高限制為20，分別取5組任意的網(wǎng)絡(luò)連接需求，將P圈配置到網(wǎng)絡(luò)中去，保證工作容量的100%保護。假設(shè)空閑容量是足夠的，容量以波長為單位。兩組算法分別記為CIDA-Grow和CIDA-mateGrow。

在表5中看到，要對Italian網(wǎng)絡(luò)的工作流量提供100%的保護，用CIDA-mateGrow和CIDA-Grow所需要的空閑容量相比，除第三組mateGrow的223略多于Grow的221以外，其他幾組都少于后者，整體需要的空閑容量顯然更少;mateGrow算法少用了19個波長，在實際配置的P圈數(shù)量上，兩者總體上相差不大，前者比后者少用一個圈。表6、7中顯示的結(jié)果與表5中相似，只有在個別組中CIDA-Grow算法比CIDA-mateGrow有非常微小的優(yōu)勢。但總體來說，mateGrow算法產(chǎn)生的P圈的性能要好于Grow算法，mateGrow算法分別少用了5和19個波長。不同網(wǎng)絡(luò)中mateGrow算法比Grow算法節(jié)省資源的比例是不同的，因為不同網(wǎng)絡(luò)的度數(shù)不同，在圈擴張時所具有的選擇空間不同，這符合理論分析，可見，用mateGrow算法構(gòu)造的備選P圈多數(shù)情況下可以提高資源利用率。

4 結(jié)束語

Grow算法在構(gòu)造P圈時具有速度快、效率高的優(yōu)點，但Grow算法沒有考慮擴張邊的順序選擇對于結(jié)果的影響。本文提出的mateGrow算法是在Grow算法的基礎(chǔ)上改進的，它優(yōu)先選擇引入先驗效率較高的邊去擴張，這樣做的好處在于:a)每次擴張都選擇了先驗效率最高的P圈，提高了備選P圈整體的先驗效率;b)丟棄了一些先驗效率較低的P圈，減少了備選P圈的數(shù)量;c)本算法沒有以增加計算量或者增加備選P圈的平均跳數(shù)作為代價，相反多數(shù)情況下會減少其平均跳數(shù)。仿真結(jié)果表明，用mateGrow產(chǎn)生的備選P圈來進行容量配置，可以得到好于Grow算法的資源利用率。

參考文獻:

[1]韋樂平.光網(wǎng)絡(luò)的發(fā)展、演進和面臨的挑戰(zhàn)[J].中興通訊技術(shù)，2002，8(4):1-5.

[2]GROVERW D， STAMATELAKIS D. Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration[C]//Proc of IEEE International Conference on Communications. Atlanta: IEEE Press，1998: 537-543.

[3]KANG B， HABIBI D， LO K， et al. An approach to generate an efficient set of candidate P-cycles in WDM Mesh networks[C]//Proc of IEEE Asia-Pacific Conference on Communications. 2006: 1-5.

[4]DOUCETTE J， HE D， GROVER W D， et al. Algorithmic approaches for efficient enumeration of candidate P-cycles and capacitated P-cycle network design[C]//Proc of the 4th International Workshop on Design ofReliable Communication Networks. 2003:212-220.

[5]DRID H， COUSIN B， LAHOUD S， et al.Multi-criteria P-cycle network design[C]//Proc of the 33rd IEEE Conference on Local Computer Networks. 2008: 361-366.

[6]GROVER W D， DOUCETTE J. Advances in optical networks design with P-cycles: joint optimization and pre-selection of candidate P-cycles[C]//Proc of IEEE/LEOS Summer Topical Meeting. 2002:49-50.

[7]ZHANG Han-xi， YANG O.Find protection cycles in DWDM networks[C]//Proc of IEEE International Conference on Communication. 2002:2756-2760.

[8]ONGUETOU D P， GROVER W D.P-cycle network design: from fewest in number to smallest in size[C]//Proc of International Workshop on Design of Reliable Communication Networks. 2007:3161-3168.

[9]ZHANG Zhen-rong， ZHONG Wen-de， MUKHERJEE B. A heuristic method for design of survivable WDM network with P-cycles[J]. IEEE Communications Letters， 2004， 8(7): 467-469.