啟發(fā)式P圈構(gòu)造算法的研究和改進(jìn)

尼俊紅，劉辛彤

（華北電力大學(xué)電子與通信工程系，河北保定 071000）

啟發(fā)式P圈構(gòu)造算法的研究和改進(jìn)

尼俊紅，劉辛彤

（華北電力大學(xué)電子與通信工程系，河北保定 071000）

針對(duì)經(jīng)典P圈構(gòu)造的Grow算法的缺陷，提出一種改進(jìn)的NewGrow算法，利用先驗(yàn)效率對(duì)備選圈進(jìn)行篩選，并在實(shí)際網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行了仿真。結(jié)果表明，該方法提高了備選P圈的質(zhì)量，減少了構(gòu)造P圈的數(shù)量，減輕了網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)擔(dān)，提高了網(wǎng)絡(luò)資源利用率。

P圈；構(gòu)造算法；先驗(yàn)效率

0 引 言

在光網(wǎng)絡(luò)中，生存性技術(shù)尤為重要。P圈作為一種有效的光網(wǎng)絡(luò)生存性保護(hù)技術(shù)，具有環(huán)網(wǎng)保護(hù)、快速恢復(fù)和網(wǎng)狀保護(hù)高資源利用率的特點(diǎn)。

P圈的構(gòu)造算法是P圈的基礎(chǔ)，本文針對(duì)P圈的Grow算法，提出了NewGrow算法，進(jìn)行了相關(guān)指標(biāo)的對(duì)比分析，并在實(shí)際網(wǎng)絡(luò)拓?fù)渲羞M(jìn)行了仿真。

1 P圈算法相關(guān)指標(biāo)

1998年，W.D.Grover和D.Stamatelakis提出了P圈（預(yù)置圈）的概念［1］，P圈保護(hù)是利用網(wǎng)狀網(wǎng)中的空閑鏈路資源預(yù)先設(shè)置的環(huán)形通道。其優(yōu)勢(shì)在于具有與環(huán)形結(jié)構(gòu)相近的恢復(fù)速度以及與網(wǎng)狀結(jié)構(gòu)相近的資源利用率。P圈的構(gòu)造是P圈保護(hù)的基礎(chǔ)，可以為下一步的P圈配置提供優(yōu)良的備選圈。P圈的構(gòu)造是將網(wǎng)絡(luò)拓?fù)渲锌赡艿幕救虯E（先驗(yàn)效率）高的擴(kuò)展圈作為備選圈，常用的啟發(fā)式P圈構(gòu)造算法包括SLA（跨接鏈路算法）、Sp-add（增加跨接鏈路算法）和Grow算法。

1.1P圈評(píng)價(jià)指標(biāo)

P圈的評(píng)價(jià)指標(biāo)包括AE、P圈個(gè)數(shù)、圈覆蓋度以及圈的代價(jià)。AE能夠直觀地體現(xiàn)P圈的保護(hù)能力，同時(shí)也是評(píng)價(jià)指標(biāo)中最重要的部分［2］。AE定義為一個(gè)P圈所能提供的保護(hù)鏈路數(shù)與該P(yáng)圈所占鏈路數(shù)之比［2］。其計(jì)算公式為

式中，S為該網(wǎng)絡(luò)拓?fù)渲兴墟溌返募?；Ck為該P(yáng)圈上任意一條圈所消耗的代價(jià)，即一個(gè)波長(zhǎng)的空閑容量；Xp，k為該P(yáng)圈可以為鏈路k提供的保護(hù)波長(zhǎng)數(shù)。

P圈的個(gè)數(shù)是P圈構(gòu)造過(guò)程中不能忽視的衡量指標(biāo)，在覆蓋整個(gè)網(wǎng)絡(luò)拓?fù)涞那疤嵯?，?yīng)保證所構(gòu)造的P圈數(shù)量盡可能少，這樣不但可以降低網(wǎng)絡(luò)管理的復(fù)雜度，還可以減少網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)擔(dān)［3］。

對(duì)于鏈路型P圈而言，圈覆蓋度［4］是一個(gè)P圈能保護(hù)的鏈路個(gè)數(shù)與網(wǎng)絡(luò)中所有鏈路數(shù)N的比值，即圈覆蓋度式中，Ap，i表示該P(yáng)圈能否保護(hù)鏈路i，若i為圈上鏈路或者跨接鏈路，則Ap，i為1，若i既不是圈上鏈路也不是跨接鏈路，則Ap，i為0。圈覆蓋度反應(yīng)了圈的保護(hù)廣度，其值越高，說(shuō)明該P(yáng)圈的保護(hù)范圍越廣，P圈性能越好。

圈的代價(jià)指的是該P(yáng)圈所占用資源的多少，圈的代價(jià)=∑i∈SCi·Fp，i，式中，Ci表示該P(yáng)圈在鏈路i上的代價(jià)值，F(xiàn)p，i表示網(wǎng)絡(luò)拓?fù)渲墟溌穒的權(quán)值，即鏈路i的代價(jià)［5］。

1.2三種經(jīng)典P圈算法的性能比較

SLA［6］的擴(kuò)張過(guò)程如圖1所示。以鏈路BF構(gòu)造出基本圈BCFAB，其中包含一條跨接鏈路BF，計(jì)算得AE=（4+2）/4=1.5，圈覆蓋度=5/9= 55.56%。

圖1　SLA擴(kuò)張過(guò)程

Sp-add算法［7］的擴(kuò)張過(guò)程如圖2所示。對(duì)SLA擴(kuò)張后的基本圈BCFAB中鏈路CF進(jìn)行擴(kuò)張，得到圈BCDFAB，其中包含兩條跨接鏈路BF、CF，計(jì)算得AE=（2×2+5）/5=1.8，圈覆蓋度= 7/9=77.78%。

圖2　Sp-add算法擴(kuò)張過(guò)程

Grow算法的擴(kuò)張過(guò)程如圖3所示。對(duì)經(jīng)過(guò)Sp-add擴(kuò)張后的圈BCDFAB中的鏈路FD繼續(xù)進(jìn)行擴(kuò)張，得到圈BCDEFAB，其中包含3條跨接鏈路BF、CF和DF，計(jì)算得AE=（3×2+6）/6=2，圈覆蓋度=100%。

圖3　Grow算法擴(kuò)張過(guò)程

從AE和圈覆蓋度兩個(gè)衡量指標(biāo)來(lái)看，3種算法構(gòu)造P圈的性能優(yōu)越程度依次為：Grow算法＞Sp-add算法＞SLA。網(wǎng)絡(luò)拓?fù)漭^為復(fù)雜時(shí)，Grow算法對(duì)圈進(jìn)行擴(kuò)張的過(guò)程中，沒(méi)有對(duì)P圈的AE進(jìn)行選擇，導(dǎo)致AE低的P圈也被擴(kuò)張，增加了工作時(shí)間，同時(shí)也使最終構(gòu)造的備選圈總體質(zhì)量不高。

2 NewGrow算法

將改進(jìn)的Grow算法命名為NewGrow算法，NewGrow算法考慮了AE的大小，對(duì)Sp-add算法擴(kuò)張之后P圈的AE進(jìn)行排序，引入?yún)?shù)K（K代表備選圈中選取的AE較高的P圈個(gè)數(shù)）。按照AE的大小對(duì)K個(gè)P圈繼續(xù)進(jìn)行擴(kuò)張，這樣可以避免將AE不高的P圈也進(jìn)行擴(kuò)張，在減少工作量的同時(shí)也提高了P圈的整體性能，使構(gòu)造出的備選P圈更為優(yōu)良。NewGrow算法流程如圖4所示。

圖4　NewGrow算法流程圖

3 算法的仿真結(jié)果和性能比較

仿真采用COST239網(wǎng)絡(luò)拓?fù)淠Ｐ停?1個(gè)節(jié)點(diǎn)，26條邊），如圖5所示。

圖5　COST239網(wǎng)絡(luò)拓?fù)鋱D

使用MATLAB軟件對(duì)COST239網(wǎng)絡(luò)拓?fù)溥M(jìn)行仿真。通過(guò)K值的選取，將NewGrow算法最終構(gòu)造的P圈質(zhì)量與Grow算法進(jìn)行比較，驗(yàn)證New-Grow算法的性能。

圖6所示為兩種算法P圈個(gè)數(shù)對(duì)比。由圖可見(jiàn)，NewGrow算法構(gòu)造的P圈個(gè)數(shù)明顯少于Grow算法，網(wǎng)絡(luò)節(jié)點(diǎn)負(fù)擔(dān)較輕。圖7所示為兩種算法平均AE對(duì)比。由圖可見(jiàn)，當(dāng)K值取1或2時(shí)，New-Grow算法構(gòu)造出的P圈平均AE要高于Grow算法；當(dāng)K值取3～5時(shí)，NewGrow算法構(gòu)造出的P圈平均AE要小于Grow算法。圖8反映了當(dāng)K值為2～4時(shí)，NewGrow算法構(gòu)造的P圈平均覆蓋度要高于Grow算法，其中當(dāng)K值取2時(shí)，圈的平均覆蓋度最大，表示該P(yáng)圈提供的保護(hù)范圍廣，性能最好。由圖9可知，當(dāng)K值取1～3時(shí)，NewGrow算法構(gòu)造P圈的單位代價(jià)平均AE高于Grow算法。綜合圖6～9，可判斷出當(dāng)K值取2時(shí)，即對(duì)AE較高的前兩個(gè)P圈繼續(xù)進(jìn)行擴(kuò)張后得到的備選圈組的性能要優(yōu)于Grow算法構(gòu)造的備選圈組。

圖6　兩種算法P圈個(gè)數(shù)對(duì)比

圖7　兩種算法平均AE對(duì)比

圖8　兩種算法圈覆蓋度對(duì)比

圖9　兩種算法單位代價(jià)平均AE對(duì)比

4 結(jié)束語(yǔ)

本文對(duì)光網(wǎng)絡(luò)中P圈構(gòu)造算法進(jìn)行了改進(jìn)。針對(duì)應(yīng)用較廣的Grow算法存在的不足，提出了一種改進(jìn)的NewGrow算法。NewGrow算法在對(duì)圈進(jìn)行擴(kuò)張時(shí)，以AE作為依據(jù)，對(duì)AE高的P圈進(jìn)一步擴(kuò)張，舍棄AE較低的P圈，提高備選P圈組的整體質(zhì)量。仿真結(jié)果表明，當(dāng)K值為2，即對(duì)備選P圈中AE較高的兩個(gè)P圈進(jìn)行進(jìn)一步擴(kuò)張后得到的P圈組，整體性能要優(yōu)于經(jīng)典Grow算法。

［1]Grover W D，Stamatelakis D.Cycle-oriented distributed preconfiguration：ring-like speed With mesh-like capacity for self-planning network restoration［C］// ICC 1998.Atlanta，GA：IEEE，1998：537-543.

［2]Grover W D，Doucette J.Advances in optical network design with p-cycles：Joint optimization and pre-selection of candidate p-cycles［C］//IEEE LEOS Summer Topicals Meetings 2001.MontTremblant，Quebec，Canada：IEEE，2002：49-50.

［3]姚曉宇，徐榮青，李亞玲.一種基于P圈的啟發(fā)式構(gòu)造算法的研究［J］.光通信技術(shù)，2010，34（9）：16-19.

［4]張沛，鄧宇，黃善國(guó)，等.WDM網(wǎng)絡(luò)中p圈保護(hù)算法［J］.北京郵電大學(xué)學(xué)報(bào)，2007，30（1）：127-131.

［5]江雪敏.WDM光網(wǎng)絡(luò)及多層網(wǎng)絡(luò)生存性的研究［D］.成都：電子科技大學(xué)，2007.

［6]ZHANG H，YANG O.Finding protection cycles in DWDM networks［C］//ICC 2002.New York，USA：IEEE，2002：2756-2760.

［7]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］// DRCN 2003.Edmonton，Canada：IEEE，2003：212-220.

Research and Improvement on the Algorithm of Heuristic P-cycle Construction

NI Jun-hong，LIU Xin-tong
（Electronics and Communication Engineering，North China Electric Power University，Baoding 071000，China）

：To solve the defects of P-cycle generating algorithm named Grow，a NewGrow algorithm is proposed in this paper. It first calculates all optional cycles’AE，and then expands the selecting candidate P-cycles.The simulation is conducted in the network topology.The simulation results show that the new method can improve the quality of P-cycles，and reduce the number of P-cycles，as well as the burden of network nodes and improve the network resource utilization.

P-cycle；generating algorithm；prior efficiency

TN915.01

A

1005-8788（2016）02-0019-03

10.13756/j.gtxyj.2016.02.006

2015-09-22

尼俊紅（1971-），女，河北保定人。副教授，博士，主要研究方向?yàn)镺FDM系統(tǒng)信道估計(jì)和均衡。