1 引言
宽带视频、多媒体等业务的日益兴起,业务的快速增长,对广域骨干网的带宽提出了越来越高的要求。光纤上的波分复用技术(WDM)以它的传输容量大,对高层协议和技术适应性强,以及易于扩展等优点而备受青睐。因此,WDM光传送网被认为是下一代高速广域骨干网的最具竞争力的候选者[1]。
WDM光网络是由网络节点和连接节点的光纤链路构成的，不同波长的光信道复用在同一根光纤中传输。当客户层业务到达时，WDM光网络需要给每条业务选择路由和分配波长,建立光通道传送业务。这就是WDM网络的关键技术一路由与波长分配(RWA]问题。虽然WDM光网络已经取得了巨大的进步,但由于各种物理的、技术的限制因素，光网络还不能提供我们所要求的物理性能，因此就存在对现有可用资源的高效利用和优化问题，RWA问题是最优化网络性能的核心问题之一。本文针对这个问题，将波长分层图和网络图论的最大边不相关理论引入RWA问题中，提出了一种基于分层图的最大边不相关(LG-BEDP)算法。仿真表明，该算法可以有效节省网络波长资源,且易于实施。
2 研究背景
作为光网络的核心问题,静态RWA问题已被广泛研究,且已被证明是一个问题[2],多用一些启发式算法来解决。文献[4]提出一种整数线性规划(ILP)法，但该算法复杂度较高,且随网络规模急剧增大。本文的算法将网络图论中的最大边不相关理论和波长分层图模型结合起来解决这个问题,因此可同时进行选路和波长分配,且能有效优化网络资源。
2.1 RWA的最大边不相关问题
WDM网络巾,由于波长连续性的限制,不同业务对应的光路在网络拓扑中必须边不相关，因此，我们可以将图论中最大边不相关原理[5, 7]的一些解决方案应用到RWA问题中。RWA的最大边不相关问题可描述为：给定网络的物理拓扑和业务请求集合，分别从该集合中找到不同的业务分组，要求每个分组中的业务在物理拓扑上存在不相关路径，且分组中的业务个数尽可能地多。由于每个分组中的连接请求都符合边不相关的要求,因此,每组连接请求都可以分配相同的波长。
在此基础上,我们又引入了波长分层图模型，来共同解决静态RWA问题。
2.2 波长分层图模型
定义：网络的物理拓扑为G(V,E]V表示节点集合,E表示两条光纤形成的双向链路集合。设单根光纤中共有W个波长。
该物理拓扑的分层图LG (V*，E*)可以描述为：将物理拓扑复制W份,形成分层图中的W层。物理拓扑中的节点Vi就对应各个分层图中的{V1i,V2i，…Vwi}，链路ei就对应{e1i，e2i，…ewi}。并且原来的双向链路变成方向相反的两条有向链路。vi∈V，ei∈E,这样，分层图LG(V*,E*)的每一层都代表一个波长，我们从上到下对每一层所对应的波长进行编号，依次为λ1、λ2、…λw。
如图1(a)所示的物理网络变成分层图就如图1(b)所示.其中W=3,波长分层图的每一层所对应的波长依次为λ1、λ2、和λ3。
在波长分层图模型中，光路从源节点到目的节点必须要在同一个波长分层内，即满足波长连续性限制。对于一个连接请求，在波长分层图上进行选路，它所经过的路径，就是该光连接在物理拓扑上经过的路径，路径所在的波长分层，就是它所占用的波长。如图1(b)中，光连接(V5，V4)的路径是V35→V32→V33→V34，即该请求在物理拓扑中的路径为V5→V2→V3→V4，且该路径被分配的波长为λ3。因此，可以说波长分层图模型可以同时解决WDM网络中的选路和波长分配问题。
3 基于分层图的最大边不相关RWA算法
定义：网络物理拓扑为G(V，E)它所对应的分层图模型为LG(V*E*)：业务请求集合为D，集合中的某请求为d：波长数目为W;业务所对应的通路集合为P,通路pi跳数长度为
图2 ，要求每个通路的长度满足hi≤h，其中，m表示拓扑图中边的个数。diam(G)表示拓扑图的直径。
