·美法分析
数字技术与应用
DWDM网络中的静态RWA算法研究
冯雪首翔师彦象
（四川理工学院自动化与电子信息学院四川自黄643000)
摘要：静态RWA算法实际上是对光网络中配置的优化，周最少数目的波长建立网络的全选接，用录短的通道长度建立全速接；使己经建立的速接录优化，并遭演波长数量和通道长度的服制。本文给出儿种静态RWA算法。
关键词：RWA模拟速火LSP 中围分类号：TN929.11
文献标识码：A
由于光网络承载的业务需求呈爆炸式增长，雨目前光网络的可用资源有限，因此，如何在有限资源网络中为业务选择合适的路由和分配优化的波长将直接影响到网络的传输效率，路由和波长分配算法(RWA问题)也就成为一个核心问题之
本文就静态RWA算法给出几种算法，并进行总结。
1模拟退火算法
模拟退火算法"是将固体退火思想引人组合优化问题邻城而提出的一种解决大规模组合优化问题的算法，从考察实际的网络模型出发，根据端到端的业务需求，引人一种K路由算法的结果作为模拟退火算法和启发性算法备选路由集合，在链路带宽有限的条件下使用模拟退火算法和启发
性算法分
连接请求分配的总
基础上为所有或网络负载均
衡优化目标对资源分配进行优化，也就是
院从
整定靠开期，使用产
生器不断把目
前结构的解转变为邻近结构的解，而接受准则允许目标函数在有限范图内变坏，它由作用类似于物理过程中的温度T的控制参数t来决定，对于t的每一取值，算法持续
进行产生新
一接受或合弃的选代
过程，经过大量的解变换后，可以求得给定一控制参数t值时组合优化间题的相对最优解。然后减小t值，重复执行上述选代过程，当t趋于0时，系统亦越来越趋于平衡状态，最后，系统状态对应于组合优化间题的整体最优解。
2基于光路的静态RWA算法
基于光路的静态RWA算法是根据给定多条光路的连接需求和物理拓扑，力求使所用的资课波长数最小，在一定的波长数下使连接的光路数最大，并为每条光路选取路由并分配波长，为每条光路选取路由，通常可用熟知的最短路径算法，缺点是会使网络中某些部分有时过于拥挤，在波长数有限情况下会造成波长不够分配。改进的方法是采用选路算法使负载平衡，而
万方数据
文章编号：1007-9416(2010)11-0081-01
整数线性规划方法会使网络中一根光纤上的光路数尽量小，但在网络规模较大时较复杂。采用网络负载平衡的启发式路由算法能得到较优的结果，但不一定最优。采用支持优先级的备用路由算法制为网络中每个节点建立相应的路由信息表，每个节点对间都有多条路由可供选择，且不同路由链路分离。最简单的方法是选取k条量短路
一组路由分配波长时，着
径。为多条光路的一
发生波长数不够用，则通构成另
一组路由，再分配
求。对于波长分配变换，而每：
长连续的，且在
分配不同的波
换备用路由到完成要 C没有波长的光路波大同光路需
且采用的波长数量最小，
这个间题可以转化为
辅助图G(V，E）
的著色间题，波长分配相当于为G的节点著色，约束条件是相连的节点不能采用同一颌色，优化目标是使采用的颜色数最小。这个着色问题已有有效的算法，但较复杂。所以，采用一些启发式算法，对多条路由逐条分配波长"，
3MinLP算法与MinTH算法
光互联网中LSP的路由算法是一个NP-hard问题，解决该问题通常都采用分层图(L ayeredGraph，LG)模型，但LG模型存在如下缺陷：首先，在OX无波长转换能力的情况下，如果一条LSP被多跳光路承载LG模型要求这些光路的被长必须相同，但GMPLS规定波长本身可以被作为标记，承载LSP的光
一致，这样LG模型可能增
路的波长充许不
大网络对LSP建立请求的阻塞率，再者，LG 模型一般不考虑结点光收发器对网络阻塞率的影响，但如果结点光收发器受限，新建光路时可用光收发器数可能成为LSP选路的制约瓶颈。针对LG模型的缺陷，MPLS
ove
DWDM光网络路由算法中比较典型的是文献"提出的MinTH(Minimizing the numbe r of Traffic Hops)和MinLP(Minimizing the number of Light-Path)算法，MinTH力求使每个LSP的源，宿结点对跨越的光路跳数最小，而MinLP要求承载LSP所要新建的光路
数最少，MinTH算法主要考虑对单个LSP服务质量的满足，MinLP算法则考虑对网络链路资源的优化利用，
综上，对于静态RWA算法，波长连续性限制必须考虑，在一个给定的物理拓扑上去导找一个预先设定的逐辑拓扑。静态RW A应具有使网络的每个节点与其它的所有节点同时通信的能力，也就是全连接的能力，在静态的RWA算法中，对允许的路由和波长选择和排序与网络的状态无关，如
来在
个设计通道上没有可利用的波长，
基至在产。
在
主要求连接时，对该连接而言存
个空闲的被长的不同路由，这个连接
都将被阻塞，对静态RWA而言，业务需要通过一组预先设定的端到端之间的逻辑连接来实现，逻辑连接和光波长通道连接实
际上是等效的。参考文献
[1]李梓江.静态路由波长分配问题的研究
与算法实现[D].重庆大学，2006.
[2] Alexander Stepanoy and STL,Dr.Dobb" s Joumal,Mar.1995.
[3]李乐民.WDM光传送网的选路和波长分
配算法[].中兴通讯技术，2002.7.
[4] Chen C and Banerjee S.A new model f
or optimal routing and wavelength assig nment in wavelength division multiplexe d optical networks.IEEE INFOCOM 19 96,San Francigco,USA,April 1996:164-171.
a' nuz pe' Buez' z [s] A novel generic graph model for traffi C grooming in heterogeneous WDM me sh networks.IEEE/ACM Trans.on Net working,2003,11(2):295~299.
[6]乔俊峰等.WDM光阿络中支特优先级的
备用路由算法[1].计算机工程与应用，20 05.3.
Digital technology and application
数字技术与应用
81