安 李, 范九伦

(西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

网状光网络预置圈的一种启发式构造

安 李, 范九伦

(西安邮电大学 通信与信息工程学院, 陕西 西安 710121)

为了提高预置圈(P圈)先验效率，减少备选P圈个数，给出一种基于圈扩张策略的相交圈合并算法。利用跨接链路算法计算基础P圈，在其中找出两个相交P圈，以及它们之间的相交节点，对其进行相加合并，生成新的P圈。以先验效率为筛选标准，将性能较好的新P圈加入备选P圈，丢弃性能较差的P圈。针对Italy和Cost239两个网络拓扑进行算法仿真，结果表明，所给算法能够提高P圈先验效率，并将备选P圈个数减少一半，性能优于P圈启发式构造算法中的扩展算法(Grow Algorithm)。

光网络；生存性；预置圈；先验效率

光通信承载着通信网络中80%以上的信息流量[1]。利用波分复用技术[2]，单条光纤可以同时发送多束不同波长的光信息，每束光波最高可达40 Gb/s的数据传输率[3]。为了保证网络正常运行，光网络的生存性技术成为研究热点。

预置圈(Pre-configuration cycle, P圈)是一种基于环结构的格状网络保护方案[4]，利用空闲资源预先设置的环形通道实现对网状网络的快速保护。P圈可以同时对圈上链路和跨接链路提供保护路径，兼有网状网络的高容量效率与环状网络恢复时间短的优势，为网络生存性技术提供了一个可靠保障。

P圈的构造算法，可以分为完全优化算法[5]、联合优化算法[6]和完全启发式算法[7]。完全启发式算法过程简单且计算时间短，是构造P圈的理想选择。

扩展算法(The Grow Algorithm, Grow算法)[7]是启发式P圈构造算法中的一个典型算法，它是一种以跨接链路算法(The Straddling Link Algorithm，SLA)[8]和边增加算法(The Span-Add Algorithm, Sp-Add)[7]为基础的重复迭代的过程。Grow算法产生的P圈先验效率高、资源利用率大，但此算法在计算过程中会产生数目过多的备选P圈，给网络管理带来了困难。

本文拟针对Grow算法中的不足，给出一种相交圈合并(Intersecting Cycles Merge, ICM)算法，即以SLA算法所产生的P圈为基础，寻找两两相交的P圈进行合并，并以先验效率(Prior Efficiency, PE)为筛选标准，丢弃性能较差的P圈，以此降低备选P圈的数量，解决因Grow算法产生备选P圈过多而带来的网络管理问题。

1 P圈评价标准

衡量P圈构造优劣的参数有[9]先验效率、P圈的个数、平均跳数和平均代价。

一个P圈的先验效率是指被保护的最大工作容量与配置此圈消耗的网络容量的比值[10]。以S表示P圈中所有链路的集合，Xi和Ci分别表示P圈对链路i提供的保护路径数量和提供保护的代价(代价可以是链路的物理距离、费用、带宽等)，且

则P圈的先验效率可表示为

由上式可知，P圈的跨接链路越多，其先验效率就越高，潜在的保护效率也就越高，因此，先验效率越高的P圈，其性能也就越好。

P圈的个数是衡量P圈性能好坏的第二个重要指标，在不降低先验效率的前提下，P圈的数量越少，网络管理的负担越小[11]。

2 相交圈合并算法

为了在不影响先验效率的前提下减少P圈的数目，先以SLA算法所计算出来的P圈为基础，通过两个相交P圈之间的相加，生成新的P圈。

如图1所示，在图1(a)中，有两个相交P圈，第一个P圈节点为2，3，11，8，5，第二个P圈节点为5，4，11，10，7，两个P圈的相交节点为5和11，以这两个相交节点为扩张点,经过圈的相加,可以得到图1(b)中的P圈，其节点为2，3，11，10，7，5。

(a) 相交P圈

(b) 合并后的P圈

在对两个相交P圈进行相加运算时，应该选择相交节点数最少的P圈，相交节点数越少，得到的新P圈的先验效率高的可行性就越大。相加完成后，需要比较新P圈与合并前的两个P圈的先验效率的大小，若新P圈的先验效率较大，则将此P圈加入到备选P圈中,否则，舍弃此P圈。算法具体步骤如下。

算法输入 网络物理拓扑G=(N,S)，其中N为网络中所有节点的集合，S是网络中所有双向链路的集合。

算法输出 P圈个数，平均PE，平均跳数，平均代价。

步骤1 在网络中，利用SLA算法构造出一组基础圈集合A，其元素个数为M。

步骤2 对A中第i个P圈(i从1开始)寻找与其相交的P圈，并记录下相交节点。若相交P圈的个数大于等于2，选择相交节点数最少的P圈，经过圈相加，得到一个新的P圈。

步骤3 判断新P圈的PE是否大于等于合并前两个P圈的PE，若是，将新P圈加入备选圈集合，否则，舍弃新P圈，查找并删除重复圈。

步骤4 计算备选圈集合中P圈个数M0，若M0>M，更新集合A中P圈个数M，返回步骤2。否则，不再产生新的P圈，算法结束。

3 算法性能检验

为了检验算法性能的好坏，对Italy(21个节点,36条链路)和Cost239(11个节点,26条链路)两个网络拓扑(图2)进行构造P圈的仿真，其中跳数为圈上链路数，代价为圈上链路的物理距离。

(a) Italy网络

(b) Cost239网络

表1和表2分别给出了在Italy和Cost239这两种网络拓扑中，Grow算法和ICM算法的输出结果。

表1 Italy网络中ICM算法与Grow算法对比

表2 Cost239网络中ICM算法与Grow算法对比

由表1和表2可见，ICM算法在平均PE和平均跳数两指标上略高于Grow算法，在平均代价方面，两算法基本持平，不相上下，但ICM算法构造的P圈数近乎是Grow算法所构造P圈数的一半，其优势较为明显。

4 结束语

ICM算法以SLA算法算出的P圈为基础，通过两个相交P圈之间的相加，生成新P圈，并对新P圈的质量进行判断，将性能较好的P圈加入到最终的备选圈中。经检验，该算法在增加先验效率的同时，可将备选P圈数目减少约一半，能够大大降低管理上的负担。

[1] 韦乐平.光网络的发展、演进和面临的挑战[J].中兴通讯技术,2002,8(4):1-5.

[2] 张亮,巩稼民,张玲.WDM网中一种考虑优先级的多播共享段保护[J].西安邮电学院学报,2010.15(3):43-46.

[3] 巩稼民,李欢,张博.40Gb/s光通信系统驱动放大器设计[J].西安邮电大学学报,2014,19(4):85-89.

[4] Grover W D, Stamatelakis D. Cycle-oriented distributed pre-configuration: ring-like speed with mesh-like capacity for self-planning network restoration[C]//Proceedings of International Conference on Communications. Atlanta: IEEE, 1998: 537-543.

[5] Mylonakis S. Optical WDM mesh networks with dedicated optical path protection with finite differences[C]//Proceedings of IEEE 5th International Conference on Networking and Services, Valencia: IEEE,2009:76-85.

[6] Kang B, Habibi D, Lo K, et al. An approach to generate an efficient set of candidate P-cycles in WDM Mesh networks[C]//Proceedings of International Conference on Communications. Busan: IEEE, 2006:1-5.

[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]//Proceedings of the 4th International Workshop on the Design of Reliable Communication Networks. Alaska: IEEE, 2003: 212-220.

[8] Zhang Hanxi, Yang O O. Finding protection cycles in DWDM networks[C]//Proceedings of International Conference on Communications. New York: IEEE, 2002: 2756-2760.

[9] 张沛, 邓宇,黄善国, 等. WDM网络中P圈保护算法[J]. 北京邮电大学学报,2007,30(1):127-131.

[10] Grover W D, Doucette J. Advances in optical networks design with P-cycles, joint optimization and pre-selection of candidate P-cycles[C]//Proceedings of LEOS Summer Topical Meeting. Quebec Mont Tremblant: IEEE, 2002: 49-50.

[11] Onguetou D P, Grover W D. P-cycle network design: from fewest in number to smallest in size[C]//Proceedings of International Workshop on Design of Reliable Communication Networks. Edmonton: IEEE, 2007: 3161-3168.

[责任编辑:瑞金]

A heuristic construction based on P-cycle in mesh optical network

AN Li, FAN Jiulun

(School of Communication and Information Engineering, Xi’an University of Posts and Telecommunications, Xi’an 710121, China)

In order to increase the prior efficiency of pre-configuration cycle(P-cycle), and reduce the number of candidate P-cycles, an intersecting cycles merge algorithm based on cycle expansion strategy is proposed. Firstly, the straddling link algorithm is used to calculate the basic P-cycles. Secondly, two intersecting P-cycles with their intersection nodes are found from the basic P-cycles, and merged into a new one. Thirdly, the prior efficiency is chosen as the standard, the better performance of the new P-cycle is combined with candidate P-cycles, and the poor performance of P-cycle is discarded. Simulation on Italy and Cost239 network topologies show that, the new algorithm can increase the prior efficiency of P-cycles and also reduce the number of candidate P-cycles more than half. Therefore the performance of new algorithm is better than that of the Grow algorithm.

optical networks, survivability, P-cycle, prior efficiency

10.13682/j.issn.2095-6533.2015.04.006

2014-11-07

国家自然科学基金资助项目(61340040，61202183)

安李(1988- )，女，硕士研究生，研究方向为光纤通信。E-mail: 497480556@qq.com 范九伦(1964- ),男，博士，教授，博士生导师，从事模式识别、信号与信息处理等研究。E-mail：jiulunf@163.com

TN929.11

A

2095-6533(2015)04-0029-03