启发式P圈构造算法的研究和改进

尼俊红，刘辛彤

（华北电力大学电子与通信工程系，河北保定 071000）

启发式P圈构造算法的研究和改进

尼俊红，刘辛彤

（华北电力大学电子与通信工程系，河北保定 071000）

针对经典P圈构造的Grow算法的缺陷，提出一种改进的NewGrow算法，利用先验效率对备选圈进行筛选，并在实际网络拓扑中进行了仿真。结果表明，该方法提高了备选P圈的质量，减少了构造P圈的数量，减轻了网络节点的负担，提高了网络资源利用率。

P圈；构造算法；先验效率

0 引 言

在光网络中，生存性技术尤为重要。P圈作为一种有效的光网络生存性保护技术，具有环网保护、快速恢复和网状保护高资源利用率的特点。

P圈的构造算法是P圈的基础，本文针对P圈的Grow算法，提出了NewGrow算法，进行了相关指标的对比分析，并在实际网络拓扑中进行了仿真。

1 P圈算法相关指标

1998年，W.D.Grover和D.Stamatelakis提出了P圈（预置圈）的概念［1］，P圈保护是利用网状网中的空闲链路资源预先设置的环形通道。其优势在于具有与环形结构相近的恢复速度以及与网状结构相近的资源利用率。P圈的构造是P圈保护的基础，可以为下一步的P圈配置提供优良的备选圈。P圈的构造是将网络拓扑中可能的基本圈和AE（先验效率）高的扩展圈作为备选圈，常用的启发式P圈构造算法包括SLA（跨接链路算法）、Sp-add（增加跨接链路算法）和Grow算法。

1.1P圈评价指标

P圈的评价指标包括AE、P圈个数、圈覆盖度以及圈的代价。AE能够直观地体现P圈的保护能力，同时也是评价指标中最重要的部分［2］。AE定义为一个P圈所能提供的保护链路数与该P圈所占链路数之比［2］。其计算公式为

式中，S为该网络拓扑中所有链路的集合；Ck为该P圈上任意一条圈所消耗的代价，即一个波长的空闲容量；Xp，k为该P圈可以为链路k提供的保护波长数。

P圈的个数是P圈构造过程中不能忽视的衡量指标，在覆盖整个网络拓扑的前提下，应保证所构造的P圈数量尽可能少，这样不但可以降低网络管理的复杂度，还可以减少网络节点的负担［3］。

对于链路型P圈而言，圈覆盖度［4］是一个P圈能保护的链路个数与网络中所有链路数N的比值，即圈覆盖度式中，Ap，i表示该P圈能否保护链路i，若i为圈上链路或者跨接链路，则Ap，i为1，若i既不是圈上链路也不是跨接链路，则Ap，i为0。圈覆盖度反应了圈的保护广度，其值越高，说明该P圈的保护范围越广，P圈性能越好。

圈的代价指的是该P圈所占用资源的多少，圈的代价=∑i∈SCi·Fp，i，式中，Ci表示该P圈在链路i上的代价值，Fp，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继续进行扩张，得到圈BCDEFAB，其中包含3条跨接链路BF、CF和DF，计算得AE=（3×2+6）/6=2，圈覆盖度=100%。

图3　Grow算法扩张过程

从AE和圈覆盖度两个衡量指标来看，3种算法构造P圈的性能优越程度依次为：Grow算法＞Sp-add算法＞SLA。网络拓扑较为复杂时，Grow算法对圈进行扩张的过程中，没有对P圈的AE进行选择，导致AE低的P圈也被扩张，增加了工作时间，同时也使最终构造的备选圈总体质量不高。

2 NewGrow算法

将改进的Grow算法命名为NewGrow算法，NewGrow算法考虑了AE的大小，对Sp-add算法扩张之后P圈的AE进行排序，引入参数K（K代表备选圈中选取的AE较高的P圈个数）。按照AE的大小对K个P圈继续进行扩张，这样可以避免将AE不高的P圈也进行扩张，在减少工作量的同时也提高了P圈的整体性能，使构造出的备选P圈更为优良。NewGrow算法流程如图4所示。

图4　NewGrow算法流程图

3 算法的仿真结果和性能比较

仿真采用COST239网络拓扑模型（11个节点，26条边），如图5所示。

图5　COST239网络拓扑图

使用MATLAB软件对COST239网络拓扑进行仿真。通过K值的选取，将NewGrow算法最终构造的P圈质量与Grow算法进行比较，验证New-Grow算法的性能。

图6所示为两种算法P圈个数对比。由图可见，NewGrow算法构造的P圈个数明显少于Grow算法，网络节点负担较轻。图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圈继续进行扩张后得到的备选圈组的性能要优于Grow算法构造的备选圈组。

图6　两种算法P圈个数对比

图7　两种算法平均AE对比

图8　两种算法圈覆盖度对比

图9　两种算法单位代价平均AE对比

4 结束语

本文对光网络中P圈构造算法进行了改进。针对应用较广的Grow算法存在的不足，提出了一种改进的NewGrow算法。NewGrow算法在对圈进行扩张时，以AE作为依据，对AE高的P圈进一步扩张，舍弃AE较低的P圈，提高备选P圈组的整体质量。仿真结果表明，当K值为2，即对备选P圈中AE较高的两个P圈进行进一步扩张后得到的P圈组，整体性能要优于经典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圈的启发式构造算法的研究［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系统信道估计和均衡。