安 李, 范九倫

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

網(wǎng)狀光網(wǎng)絡(luò)預(yù)置圈的一種啟發(fā)式構(gòu)造

安 李, 范九倫

(西安郵電大學(xué) 通信與信息工程學(xué)院, 陜西 西安 710121)

為了提高預(yù)置圈(P圈)先驗(yàn)效率，減少備選P圈個(gè)數(shù)，給出一種基于圈擴(kuò)張策略的相交圈合并算法。利用跨接鏈路算法計(jì)算基礎(chǔ)P圈，在其中找出兩個(gè)相交P圈，以及它們之間的相交節(jié)點(diǎn)，對(duì)其進(jìn)行相加合并，生成新的P圈。以先驗(yàn)效率為篩選標(biāo)準(zhǔn)，將性能較好的新P圈加入備選P圈，丟棄性能較差的P圈。針對(duì)Italy和Cost239兩個(gè)網(wǎng)絡(luò)拓?fù)溥M(jìn)行算法仿真，結(jié)果表明，所給算法能夠提高P圈先驗(yàn)效率，并將備選P圈個(gè)數(shù)減少一半，性能優(yōu)于P圈啟發(fā)式構(gòu)造算法中的擴(kuò)展算法(Grow Algorithm)。

光網(wǎng)絡(luò)；生存性；預(yù)置圈；先驗(yàn)效率

光通信承載著通信網(wǎng)絡(luò)中80%以上的信息流量[1]。利用波分復(fù)用技術(shù)[2]，單條光纖可以同時(shí)發(fā)送多束不同波長(zhǎng)的光信息，每束光波最高可達(dá)40 Gb/s的數(shù)據(jù)傳輸率[3]。為了保證網(wǎng)絡(luò)正常運(yùn)行，光網(wǎng)絡(luò)的生存性技術(shù)成為研究熱點(diǎn)。

預(yù)置圈(Pre-configuration cycle, P圈)是一種基于環(huán)結(jié)構(gòu)的格狀網(wǎng)絡(luò)保護(hù)方案[4]，利用空閑資源預(yù)先設(shè)置的環(huán)形通道實(shí)現(xiàn)對(duì)網(wǎng)狀網(wǎng)絡(luò)的快速保護(hù)。P圈可以同時(shí)對(duì)圈上鏈路和跨接鏈路提供保護(hù)路徑，兼有網(wǎng)狀網(wǎng)絡(luò)的高容量效率與環(huán)狀網(wǎng)絡(luò)恢復(fù)時(shí)間短的優(yōu)勢(shì)，為網(wǎng)絡(luò)生存性技術(shù)提供了一個(gè)可靠保障。

P圈的構(gòu)造算法，可以分為完全優(yōu)化算法[5]、聯(lián)合優(yōu)化算法[6]和完全啟發(fā)式算法[7]。完全啟發(fā)式算法過(guò)程簡(jiǎn)單且計(jì)算時(shí)間短，是構(gòu)造P圈的理想選擇。

擴(kuò)展算法(The Grow Algorithm, Grow算法)[7]是啟發(fā)式P圈構(gòu)造算法中的一個(gè)典型算法，它是一種以跨接鏈路算法(The Straddling Link Algorithm，SLA)[8]和邊增加算法(The Span-Add Algorithm, Sp-Add)[7]為基礎(chǔ)的重復(fù)迭代的過(guò)程。Grow算法產(chǎn)生的P圈先驗(yàn)效率高、資源利用率大，但此算法在計(jì)算過(guò)程中會(huì)產(chǎn)生數(shù)目過(guò)多的備選P圈，給網(wǎng)絡(luò)管理帶來(lái)了困難。

本文擬針對(duì)Grow算法中的不足，給出一種相交圈合并(Intersecting Cycles Merge, ICM)算法，即以SLA算法所產(chǎn)生的P圈為基礎(chǔ)，尋找兩兩相交的P圈進(jìn)行合并，并以先驗(yàn)效率(Prior Efficiency, PE)為篩選標(biāo)準(zhǔn)，丟棄性能較差的P圈，以此降低備選P圈的數(shù)量，解決因Grow算法產(chǎn)生備選P圈過(guò)多而帶來(lái)的網(wǎng)絡(luò)管理問(wèn)題。

1 P圈評(píng)價(jià)標(biāo)準(zhǔn)

衡量P圈構(gòu)造優(yōu)劣的參數(shù)有[9]先驗(yàn)效率、P圈的個(gè)數(shù)、平均跳數(shù)和平均代價(jià)。

一個(gè)P圈的先驗(yàn)效率是指被保護(hù)的最大工作容量與配置此圈消耗的網(wǎng)絡(luò)容量的比值[10]。以S表示P圈中所有鏈路的集合，Xi和Ci分別表示P圈對(duì)鏈路i提供的保護(hù)路徑數(shù)量和提供保護(hù)的代價(jià)(代價(jià)可以是鏈路的物理距離、費(fèi)用、帶寬等)，且

則P圈的先驗(yàn)效率可表示為

由上式可知，P圈的跨接鏈路越多，其先驗(yàn)效率就越高，潛在的保護(hù)效率也就越高，因此，先驗(yàn)效率越高的P圈，其性能也就越好。

P圈的個(gè)數(shù)是衡量P圈性能好壞的第二個(gè)重要指標(biāo)，在不降低先驗(yàn)效率的前提下，P圈的數(shù)量越少，網(wǎng)絡(luò)管理的負(fù)擔(dān)越小[11]。

2 相交圈合并算法

為了在不影響先驗(yàn)效率的前提下減少P圈的數(shù)目，先以SLA算法所計(jì)算出來(lái)的P圈為基礎(chǔ)，通過(guò)兩個(gè)相交P圈之間的相加，生成新的P圈。

如圖1所示，在圖1(a)中，有兩個(gè)相交P圈，第一個(gè)P圈節(jié)點(diǎn)為2，3，11，8，5，第二個(gè)P圈節(jié)點(diǎn)為5，4，11，10，7，兩個(gè)P圈的相交節(jié)點(diǎn)為5和11，以這兩個(gè)相交節(jié)點(diǎn)為擴(kuò)張點(diǎn),經(jīng)過(guò)圈的相加,可以得到圖1(b)中的P圈，其節(jié)點(diǎn)為2，3，11，10，7，5。

(a) 相交P圈

(b) 合并后的P圈

在對(duì)兩個(gè)相交P圈進(jìn)行相加運(yùn)算時(shí)，應(yīng)該選擇相交節(jié)點(diǎn)數(shù)最少的P圈，相交節(jié)點(diǎn)數(shù)越少，得到的新P圈的先驗(yàn)效率高的可行性就越大。相加完成后，需要比較新P圈與合并前的兩個(gè)P圈的先驗(yàn)效率的大小，若新P圈的先驗(yàn)效率較大，則將此P圈加入到備選P圈中,否則，舍棄此P圈。算法具體步驟如下。

算法輸入 網(wǎng)絡(luò)物理拓?fù)銰=(N,S)，其中N為網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合，S是網(wǎng)絡(luò)中所有雙向鏈路的集合。

算法輸出 P圈個(gè)數(shù)，平均PE，平均跳數(shù)，平均代價(jià)。

步驟1 在網(wǎng)絡(luò)中，利用SLA算法構(gòu)造出一組基礎(chǔ)圈集合A，其元素個(gè)數(shù)為M。

步驟2 對(duì)A中第i個(gè)P圈(i從1開始)尋找與其相交的P圈，并記錄下相交節(jié)點(diǎn)。若相交P圈的個(gè)數(shù)大于等于2，選擇相交節(jié)點(diǎn)數(shù)最少的P圈，經(jīng)過(guò)圈相加，得到一個(gè)新的P圈。

步驟3 判斷新P圈的PE是否大于等于合并前兩個(gè)P圈的PE，若是，將新P圈加入備選圈集合，否則，舍棄新P圈，查找并刪除重復(fù)圈。

步驟4 計(jì)算備選圈集合中P圈個(gè)數(shù)M0，若M0>M，更新集合A中P圈個(gè)數(shù)M，返回步驟2。否則，不再產(chǎn)生新的P圈，算法結(jié)束。

3 算法性能檢驗(yàn)

為了檢驗(yàn)算法性能的好壞，對(duì)Italy(21個(gè)節(jié)點(diǎn),36條鏈路)和Cost239(11個(gè)節(jié)點(diǎn),26條鏈路)兩個(gè)網(wǎng)絡(luò)拓?fù)?圖2)進(jìn)行構(gòu)造P圈的仿真，其中跳數(shù)為圈上鏈路數(shù)，代價(jià)為圈上鏈路的物理距離。

(a) Italy網(wǎng)絡(luò)

(b) Cost239網(wǎng)絡(luò)

表1和表2分別給出了在Italy和Cost239這兩種網(wǎng)絡(luò)拓?fù)渲?，Grow算法和ICM算法的輸出結(jié)果。

表1 Italy網(wǎng)絡(luò)中ICM算法與Grow算法對(duì)比

表2 Cost239網(wǎng)絡(luò)中ICM算法與Grow算法對(duì)比

由表1和表2可見，ICM算法在平均PE和平均跳數(shù)兩指標(biāo)上略高于Grow算法，在平均代價(jià)方面，兩算法基本持平，不相上下，但I(xiàn)CM算法構(gòu)造的P圈數(shù)近乎是Grow算法所構(gòu)造P圈數(shù)的一半，其優(yōu)勢(shì)較為明顯。

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

ICM算法以SLA算法算出的P圈為基礎(chǔ)，通過(guò)兩個(gè)相交P圈之間的相加，生成新P圈，并對(duì)新P圈的質(zhì)量進(jìn)行判斷，將性能較好的P圈加入到最終的備選圈中。經(jīng)檢驗(yàn)，該算法在增加先驗(yàn)效率的同時(shí)，可將備選P圈數(shù)目減少約一半，能夠大大降低管理上的負(fù)擔(dān)。

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

[2] 張亮,鞏稼民,張玲.WDM網(wǎng)中一種考慮優(yōu)先級(jí)的多播共享段保護(hù)[J].西安郵電學(xué)院學(xué)報(bào),2010.15(3):43-46.

[3] 鞏稼民,李歡,張博.40Gb/s光通信系統(tǒng)驅(qū)動(dòng)放大器設(shè)計(jì)[J].西安郵電大學(xué)學(xué)報(bào),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] 張沛, 鄧宇,黃善國(guó), 等. WDM網(wǎng)絡(luò)中P圈保護(hù)算法[J]. 北京郵電大學(xué)學(xué)報(bào),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.

[責(zé)任編輯:瑞金]

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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61340040，61202183)

安李(1988- )，女，碩士研究生，研究方向?yàn)楣饫w通信。E-mail: 497480556@qq.com 范九倫(1964- ),男，博士，教授，博士生導(dǎo)師，從事模式識(shí)別、信號(hào)與信息處理等研究。E-mail：jiulunf@163.com

TN929.11

A

2095-6533(2015)04-0029-03