啟發(fā)式P圈構造算法的研究和改進

尼俊紅，劉辛彤

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

啟發(fā)式P圈構造算法的研究和改進

尼俊紅，劉辛彤

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

針對經典P圈構造的Grow算法的缺陷，提出一種改進的NewGrow算法，利用先驗效率對備選圈進行篩選，并在實際網絡拓撲中進行了仿真。結果表明，該方法提高了備選P圈的質量，減少了構造P圈的數(shù)量，減輕了網絡節(jié)點的負擔，提高了網絡資源利用率。

P圈；構造算法；先驗效率

0 引 言

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

P圈的構造算法是P圈的基礎，本文針對P圈的Grow算法，提出了NewGrow算法，進行了相關指標的對比分析，并在實際網絡拓撲中進行了仿真。

1 P圈算法相關指標

1998年，W.D.Grover和D.Stamatelakis提出了P圈（預置圈）的概念［1］，P圈保護是利用網狀網中的空閑鏈路資源預先設置的環(huán)形通道。其優(yōu)勢在于具有與環(huán)形結構相近的恢復速度以及與網狀結構相近的資源利用率。P圈的構造是P圈保護的基礎，可以為下一步的P圈配置提供優(yōu)良的備選圈。P圈的構造是將網絡拓撲中可能的基本圈和AE（先驗效率）高的擴展圈作為備選圈，常用的啟發(fā)式P圈構造算法包括SLA（跨接鏈路算法）、Sp-add（增加跨接鏈路算法）和Grow算法。

1.1P圈評價指標

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

式中，S為該網絡拓撲中所有鏈路的集合；Ck為該P圈上任意一條圈所消耗的代價，即一個波長的空閑容量；Xp，k為該P圈可以為鏈路k提供的保護波長數(shù)。

P圈的個數(shù)是P圈構造過程中不能忽視的衡量指標，在覆蓋整個網絡拓撲的前提下，應保證所構造的P圈數(shù)量盡可能少，這樣不但可以降低網絡管理的復雜度，還可以減少網絡節(jié)點的負擔［3］。

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

圈的代價指的是該P圈所占用資源的多少，圈的代價=∑i∈SCi·Fp，i，式中，Ci表示該P圈在鏈路i上的代價值，F(xiàn)p，i表示網絡拓撲中鏈路i的權值，即鏈路i的代價［5］。

1.2三種經典P圈算法的性能比較

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

圖1　SLA擴張過程

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

圖2　Sp-add算法擴張過程

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

圖3　Grow算法擴張過程

從AE和圈覆蓋度兩個衡量指標來看，3種算法構造P圈的性能優(yōu)越程度依次為：Grow算法＞Sp-add算法＞SLA。網絡拓撲較為復雜時，Grow算法對圈進行擴張的過程中，沒有對P圈的AE進行選擇，導致AE低的P圈也被擴張，增加了工作時間，同時也使最終構造的備選圈總體質量不高。

2 NewGrow算法

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

圖4　NewGrow算法流程圖

3 算法的仿真結果和性能比較

仿真采用COST239網絡拓撲模型（11個節(jié)點，26條邊），如圖5所示。

圖5　COST239網絡拓撲圖

使用MATLAB軟件對COST239網絡拓撲進行仿真。通過K值的選取，將NewGrow算法最終構造的P圈質量與Grow算法進行比較，驗證New-Grow算法的性能。

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

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

圖7　兩種算法平均AE對比

圖8　兩種算法圈覆蓋度對比

圖9　兩種算法單位代價平均AE對比

4 結束語

本文對光網絡中P圈構造算法進行了改進。針對應用較廣的Grow算法存在的不足，提出了一種改進的NewGrow算法。NewGrow算法在對圈進行擴張時，以AE作為依據(jù)，對AE高的P圈進一步擴張，舍棄AE較低的P圈，提高備選P圈組的整體質量。仿真結果表明，當K值為2，即對備選P圈中AE較高的兩個P圈進行進一步擴張后得到的P圈組，整體性能要優(yōu)于經典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ā)式構造算法的研究［J］.光通信技術，2010，34（9）：16-19.

［4]張沛，鄧宇，黃善國，等.WDM網絡中p圈保護算法［J］.北京郵電大學學報，2007，30（1）：127-131.

［5]江雪敏.WDM光網絡及多層網絡生存性的研究［D］.成都：電子科技大學，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-），女，河北保定人。副教授，博士，主要研究方向為OFDM系統(tǒng)信道估計和均衡。