RWA算法的研究.doc

RWA算法的研究.doc

《RWA算法的研究.doc》由会员分享，可在线阅读，更多相关《RWA算法的研究.doc（28页珍藏版）》请在冰点文库上搜索。

RWA算法的研究

RWA算法的研究

摘要：

本文研究了WDM网中的选路与波长分配（RWA）问题。

主要针对的是有波长一致性限制的网络。

首先简单介绍了WDM光传送网的一些基本概念。

然后对WDM传送网的选路与波长分配（RWA）问题进行了分类，并综述了各种条件下的RWA算法，对其进行了分类、比较。

最后在对以往算法分析和比较的基础上，提出了一个新的RWA算法。

新算法中考虑了多个网络设计优化目标，对网络运营商有一定的参考价值。

关键词：

WDM；选路与波长分配；优化算法；启发式算法

Abstract

Thisstudyfocusesontheroutingandwavelengthassignment（RWA）probleminWDMnetworks.Mostoftheattentionisdevotedtosuchnetworksoperatingunderthewavelength-continuityconstraint.SomeconceptsonWDMopticalnetworkingarestudiedfirst.Thenwestudiedtheassociatedresearchproblemsandchallenges.VariousRWAapproachesareexaminedandcompared.Finally,weproposedanewRWAalgorithm,whichincludemanyfactorsoftheWDMnetworkandmaybeusefultoanetworkmaker.

Keyword：

WDM；RWA；optimalalgorithm；heuristicalgorithm

第一章引言

波分复用（WavelengthDivisionMultiplexing—WDM）网络利用了光纤传输链路的巨大带宽，随着WDM技术日趋成熟，WDM传输技术已经进入实用化和商用化阶段。

WDM全光通信网是光纤通信未来发展的主要方向之一。

由于光网络对传输信号的速率和格式透明，具有灵活的波长选路和动态资源配置能力，可以实现网络的动态重构，被认为是通信网络升级的首选方案。

如何利用现有的和即将敷设的光纤连网，构成未来高速、大容量、多业务的WDM网络已经成为光通信领域中的一个重大问题。

WDM网络节点处采用光分插复用器（OADM）或光交叉连接设备（OXC）在光层建立光连接，即光通道（opticalpath），为高层的多个逻辑电网络提供了高速、大容量的信息传送平台。

光通道的建立，要求在传送网的物理结构中选择一条由业务源点到宿点的路由，并为其分配一定的波长信道（参见图1.1）。

考虑到波长资源的重利用以及提高网络的阻塞性能，优化光通道的选路和波长分配（RoutingandWavelengthAssignment—RWA）方案成为光通道层设计的核心问题。

RWA解决如何寻找一条合适的光通道并合理地分配通道所使用的波长，使有限的资源充分发挥作用，以提供尽可能大的通信容量。

图1.1WDM网建立的光通道

在以下的文章中，首先介绍了WDM网络中与RWA问题有关的一些基本概念。

然后对RWA问题进行了分类讨论，并对已提出的RWA算法进行了研究、总结。

在文章最后针对网状网提出了一种新的RWA算法、详细描述了该算法，并把它和其它算法进行了比较。

第二章WDM传送网的一些基本概念

2.1WDM的定义

光波分复用（WDM：

WavelengthDivisionMultiplexing）技术是在一根光纤中同时传输多波长光信号的一项技术。

其基本原理是在发送端将不同波长的光信号组合起来（复用），并耦合到光缆线路上的同一根光纤中进行传输，在接收端又将组合波长的光信号分开（解复用），并作进一步处理，恢复出原信号后送入不同的终端，因此将此项技术称为光波长分割复用，简称光波分复用技术。

WDM技术相当于在同一根光纤上创造了许多虚拟光纤，从而数倍乃至数十倍的提高了传输容量。

2.2WDM光传送网的分层结构

分层结构是定义和研究光传送网的基础。

已发布的G.872建议（草案），以明确在光传送网络加入光层，按建议，光层由光信道层，光复用段层和光传输层组成，如图2.2.1。

光传送网络

电路层

电通道层

电复用段层

光信道层

光复用段层

光层

光传输段层

物理层（光纤）

图2.2.1光通信网的分层结构

2.2.1光信道层

光信道层（opticalchannellayer）负责为来自电复用段层的客户信息选择路由和分配波长，为灵活的网络选路安排光信道连接，处理光信道开销，提供光信道层的检测，管理功能。

并在故障发生时，通过重新选路或直接把工作业务切换到预定的保护路由来实现保护倒换和网络恢复。

2.2.2光复用段层

光复用段层（opticalmultiplexingsectionlayer）保证相邻两个波长复用传输设备间多波长复用光信号的完整传输，为多波长信号提供网络功能。

其主要包括：

为灵活的多波长网络选路重新安排光复用段功能；为保证多波长光复用段适配信息的完整性处理光复用段开销；为网络的运行和维护提供光复用段的检测和管理功能。

2.2.3光传输段层

光传输段层（opticaltransmissionsectionlayer）为光信号在不同类型的光传输媒质（如G.652,G.653,G.655光纤等）上提供传输能力，同时实现对光放大器或中继器的检测和控制功能等。

通常会涉及以下问题：

功率均衡问题、EDFA增益控制问题和色散的积累和补偿问题。

2.3WDM光传送网的拓扑结构

任何通信网络都存在两种拓扑结构，即物理拓扑和逻辑拓扑（也称为虚拓扑）。

其中物理拓扑表征网络节点的物理结构；逻辑拓扑表征网络节点间业务分布情况。

图2.3.1中网络物理结构的一个例子。

l1—l6为物理链路，每根光纤上可采用多个波长。

图2.3.1网路的物理拓扑

图2.3.2（a）为上图建立光路的例子。

在一根光纤上不能为不同光路分配相同波长。

图2.3.2（a）的光路连接用图2.3.2（b）表示即为逻辑拓扑。

例如图2.3.2（a）中，节点B与节点E间的光路是经过节点A中的OXC转接的，在图2.3.2（b）中用O4表示。

图2.3.2（b）中，O4,O1是中间有OXC转接的；O2,O3,O5是直接光路。

（a）路由和波长分配（b）逻辑结构

图2.3.2光路举例

实际设计中，一种RWA情况是：

提出所需建立的光路，为这种光路选取物理路由并分配相应的波长。

例如，图2.3.2（b）中提出要建立5条光路，图2.3.2（a）就是一种选路和波长分配方案。

2.4WDM光传送网拓扑结构的主要议题

在研究RWA问题的文献中，通常将网络支持的业务分为两类：

1）静态业务：

给定一组连接建立请求，需要为这些请求寻找路由并在其路由上分配波长，以使某些性能指标达到最优（如全网吞吐量最大、所需波长数和光纤数最少等等）；2）动态业务：

光路请求随机到达和离开网络，相应当性能指标通常是光路的阻塞率。

因此按照所支持的业务类型划分，RWA问题可分为静态RWA问题和动态RWA问题。

在研究WDM全光网的拓扑结构时，有两类相关的主要问题需要解决。

第一类问题称为“网络设计”问题，即通过网络的业务需求分布（可以使业务流分布）和物理拓扑，确定网络的配置，包括光纤对数、节点交叉连接的规模、需要的光放大器以及光载波分插复用器等。

研究该问题可以在静态业务条件下优化波长资源，使网络需要的波长数目最小。

由于在大多数实际场合中每根光纤复用的波长数目是固定的，如果一对光纤（双向传输）不能传输某链路上所有预分配的业务，那么在该线路方向上将需要更多的光纤对，因此问题研究的优化目标转化为最小化光纤数目或交叉连接节点的规模等内容，或者是上述两方面的组合。

最终的优化测度应当是网络的成本相应可以通过每条链路需要的光纤数目以及光纤链路长度等参数来衡量。

如果从光通道层来建立的角度分析，静态业务下的选路和波长分配（RWA）问题相当于这一类“网络设计”问题。

第二类WDM全光网的拓扑结构问题成为“网络运营”问题。

即对给定的网络（已知拓扑和资源），在已知和可以预测业务量的平均分布情况下，假设实际业务需求的变化是随机的，则网络可能存在一定的阻塞率。

反应动态的选路和波长选择算法质量的指标是在给定利用度条件下的阻塞概率。

由于具有波长变换功能的节点可以提高光通道中波长的选择能力，因此在波长资源相同的情况下，VWP网络比WP网络具有更好的性能。

“网络运营”问题可以看作动态业务条件下的RWA问题。

2.5基于光路的RWA与基于运送分组业务的RWA

WDM光传送网既可以支持传送电路交换方式的业务，又可以支持传送分组交换方式的业务。

在传送不同类型的业务时，光通道层拓扑结构设计有着不同的特点。

当光传送网用于传送电路交换型业务时，和传统当电话交换网的接续比较类似。

此时，业务需求以单一波长信道的容量为单位，通过路由选择和配置波长建立用于业务传送的端到端光连接。

电路交换型光传送网面向的是连接型业务，而未来的光网络还需要支持支持分组数据（无连接型业务）的传送。

由于两种业务类型有着本质的区别，因此在光层网络的优化目标和优化策略方面存在明显不同。

支持分组交换业务的光传送网，其设计的核心是解决最优化网络虚拓扑的问题。

2.6波长通道网络和虚波长通道网络

电复用段一个单位的信息（如SDH信号、PDH信号甚至模拟视频信号）在光网络中传送始，需要为它选一条路由并分配波长（RWA）。

由于一根光纤中能够复用的波长数有限，且任何两路信号在一根光纤中不能使用相同波长，所以波长资源的分配是光层管理的一项重要内容。

根据OXC能否提供波长转换功能，光通道可以分为波长通道（WP:

WavelengthPath）和虚波长通道（VWP:

VirtualWavelengthPath）。

波长通道是指OXC没有波长转换功能，光通道在不同的波长复用段中必须使用相同波长实现。

为了建立一条波长通道，光通道层必须找到一条链路，在构成这条链路的所有波长复用段中，存在一个共同的空闲波长。

如果找不到这样一条链路，该通道创建请求失败。

虚波长通道是指利用OXC的波长转换功能，使光通道在不同的波长复用段可以占用不同的波长，从而提高了波长的利用率。

建立虚波长通道时，光通道层只需找到一条链路，其中每个波长复用段都有空闲波长即可。

波长通道方式要求光通道层在选路和分配波长时采用集中控制方式，因为只有在掌握了整个网络所有复用段占用情况后，才可能为一个新传送请求选一条合适的路由。

在虚波长通道运作方式下，确定通道的传送链路后，各波长复用段的波长可以逐个分配，因此可以进行分布式控制。

这种方法可以大大降低光通道层选路的复杂性。

由于复杂网络中任何两个节点间都可能存在多条路由，因此必需有一套有效的RWA算法，根据网络的拓扑结构和目前的状态，为新传送请求选路并分配波长。

另外，当光通道层中允许接入分组信息时，还需要相应的分组交换型的选路算法。

与WP方案相比，VWP方案的一个显著特点是通道由经过的光交叉连接（OXC）节点具有波长转换的能力。

WP方案存在波长全局分配的问题，增加了光通道实现的复杂性；VWP方案不存在这一问题。

从网络和通道的扩展能力上看，VWP技术优于WP技术。

采用VWP技术的网络，波长的重利用率和路由选择的自由度都要高于采用WP技术的网络。

所以，在某一物理网络中建立相同数量的光通道，与VWP方案相比，WP方案需要使用更多的波长，换句话说，对相同物理网络结构和同样数目的波长，VWP网络可以建立更多的光通道。

从通道波长的管理角度比较，WP方案要求对全网进行集中控制，而VWP方案可能采取链路到链路的分布式控制。

在整个网络范围内，WP技术要求波长绝对精确，VWP技术则只要保证波长从链路到链路相对精确即可。

在WP方案中，如果无法找到一条从源节点到目的节点由相同空闲波长的光通道，就会发生波长阻塞，而使通道建立努力失败；而VWP方案只在通道中某个链路没有空闲的波长信道时才会使通道建立请求失败。

综上可知，RWA问题可以相应的分为基于WP网络的RWA问题与基于VWP网络的RWA问题。

与WP网络相比VWP网络求解RWA问题需增加波长一致性的限制，相邻通道分配不同的波长，其物理意义是对任意一条光路径而言，在它经过的所有链路段上必须保持同一波长信道。

2.7波长变换器作用

波长变换器是解决全光网中波长路由竞争的关键器件，是充分发挥WDM带宽资源的必要手段。

为了对波长变换的用途和作用有一个直观的了解，首先让我们来考虑图2.7.1的网络，它包含两个交叉连接节点和5个接入点（A到E）。

若要建立两节点之间的全光连接，例如A和C的连接，如果没有波长变换器，这条光路上的所有连接必须采用同一波长，这就是所谓的波长连续性限制。

对电路交换网而言，仅当该级别的链路容量都被占用时，才会发生阻塞，而对于波长路由网络，却远非如此。

如图2.7.2（a）所示，在网络中建立了两个光通道，节点1和2之间采用波长，节点2和3之间的波长是，现在假设要在1、3之间建立一条光通道，即使节点1、3之间的每个链路都有空闲的波长也不一定能建立这个光通道，这是因为在两个链路上可得到的波长是不同的。

因此，与电路交换网络相比，波长路由网络将遭受更大的阻塞。

图2.7.1全光波长路由网络图2.7.2波长连续性限制

如果能在中间节点进行波长变换，从一个波长转换到另一个波长，对光网络将是非常有利的。

如图2.7.2（b）所示，节点2的波长变换器把波长从变换到，在节点1、2中间应用波长，在节点2、3中间应用波长，从节点1到节点3的光通道便可建立。

在含有波长变换器的网络中，光通道能在不同的链路上用不同的波长而建立，从而大大提高网络的灵活性，消除光通道的波长冲突。

引入波长变换技术，可以实现波长的再利用，更有效地进行路由的选择，降低网络阻塞率，从而提高WDM网的灵活性和可扩充性。

波长变换器对WDM光网络的性能究竟有多大的改善，是近年来的一个热点课题。

现在比较一致的观点是：

波长变换器对一个波长数量固定，且业务量接近饱和的网络的作用不大；对于集中管理的网络和环形网的影响也不明显，而对大容量的网格形网，波长变换器的加入却能大大降低网络的阻塞率。

如果节点的数目加大，效果会更明显。

事实上，波长变换器的作用与WDM光网络的节点数、波长数、波长从源到宿所经过的节点数及业务量都密切相关。

鉴于波长转换器还未达到实用水平，本文主要针对无波长转换、基于光路交换网络的RWA问题进行了研究。

第三章静态RWA算法

基于光路的静态RWA算法是给定多条光路的连接需求和物理拓扑后为每条光路选取路由并分配波长。

3.1设计时的优化目标：

1）给定网络资源而最大化网络的某些特性，如可以建立的连接数、波长的复用率、可获得的利润等。

2）给定光连接数目而最小化所需要的网络资源数目或代价。

3.2设计时的约束条件：

1）波长一致性限制：

即每一个光通路所使用的波长在从源节点到目的节点的所有连路上都是相同的，这一限制是由网络的物理条件造成的。

2）同一光纤中的不同光通道必须分配不同的波长，这是保证网络能够正常运行的限制条件。

3.3解决方案：

方案一：

选路与波长分配作为一个整体的问题来解决

RWA这个优化问题是一个NP-C（NondeterministicPolynomial—Complete,非确定型多项式－完全）组合优化问题，可以用整数线性规划（ILP）来寻找最优解，但这种优化方法的复杂性随网络规模的增大而急剧增加，当网络规模较大时因运算时间太长而无法接受。

因此工程上常将RWA问题拆成选路子问题和波长分配子问题。

方案二：

选路与波长分配作为两个子问题来解决

选路和波长分配这两个子问题也都是典型的NP-C组合优化问题。

图3.3.1是对目前已有算法的分类：

图3.3.1算法分类

这里首先把求解过程分成选路和波长分配两部分。

每一子问题中又分成两步，即寻找与选择，最后按照所用的具体算法进行分类。

图3.3.2、3.3.3分别给出了解决选路和波长分配问题的算法的具体实现方法。

寻找

选择

寻找方法

寻找顺序

选择顺序

选择规则

最短路径法

------------

-----------

加权最短路径

最大流量优先

随机

k-最短路径

-----------

随机

固定

最长优先

最短优先

随机

固定

概率

最小

顺序算法

（贪婪算法）

随机循环（randomrounding）

启发式

组合

算法

整数线性规划

最优化

图3.3.2选路算法

（1）选路算法：

在选路问题中，考虑所有可能的源目的对是不实际的，因为计算时间随着网络规模的增长成指数增长。

因此，寻找功能通常由最短路径算法及它的变种（variations）实现。

在k－最短路径算法中（即：

有多个备选路由），选择功能由顺序算法或组合优化算法来实现。

顺序算法（也叫贪婪算法）是最简单的一种。

它按顺序为每一条光路进行选择，这其中需要考虑两方面：

选择顺序、选择规则。

选择顺序是指先为哪一个光连接选择路由，选择规则是从备选路由中选择的标准。

图3.3.2解释了选路算法：

·最短路径（SP－Shortestpath）：

最短路径算法寻找从源节点到目的节点的一条最短的光路。

·加权最短路（WSP－Weightedshortestpath）：

加权最短路算法是一种最短路算法，但是链路代价可以随着已建立的路由数动态的变化。

因此，它需要一个寻找顺序。

例如：

―—最大业务量优先（Largesttrafficfirst）：

从需要建立的光路中优先选择业务量最大的光路来寻找路由；

―—随机（Random）机制以随机的顺序来选择需要建立的光路。

但是这种方法不需要选择功能，因为它也是只为每个源目的对选择一个路由。

·K－最短路径（K-SP－K-shortestpath）：

k-最短路径算法为每一源目的对寻找多个路径，k个备选路由增加了选路的灵活性。

然而，选路问题变成了选择问题：

为所有的源目的对选择一个代价（跳数或链路代价）最小的路由。

选择功能如下：

1）顺序算法（贪婪算法）

——选择顺序

*随机（Random）机制从所有未建立路由的光连接中以随机的方式选择；

*固定（Fixed）机制把光连接按某种规则排序（如按链路数降序），然后依次选取；

*最长路优先（Longest-first）机制把光通路按通路的长度（跳数或代价）由大到小排序，先选长路由；

*最短路优先（Shortest-first）机制把光通路按通路的长度（跳数或代价）由大到小排序，先选短路由。

——选择规则

*随机机制：

从备选路由中随机选取一条。

*FF（First－fit）机制：

从备选路由中选择第一个符合条件的路由。

*概率（probability）机制：

依一定的概率从备选路由中选择一条路由。

*链路最小权重（minimum－weightedlink）优先机制：

选择所有链路上已经建立的路由数最小的路由。

2）组合算法

－—最优化算法（Optimalalgorithm）：

这是一个多商品流问题，用整数线性规划可以得到最优解。

最优化选择可得到最优的结果，但是网络规模较大时计算的复杂程度是无法忍受的。

－—启发式算法（Heuristicalgorithm）：

启发式算法是根据概念推出的优化算法，能得到较优的结果，但不一定是最优。

它降低了组合空间（combinationspace），在所设计的规则指导下修改所选的路由，多次循环以靠近优化目标，直到循环无法得到更优结果为止。

寻找

选择

寻找顺序

寻找规则

选择顺序

选择规则

所有波长

------------

随机

固定

最长优先

最短优先

随机

FF（Firstfit）

最少使用

最多使用

顺序算法

（贪婪算法）

GA（遗传算法）

SA（模拟退火算法）

RandomRounding（随机循环）

TABU（禁忌搜索）

启发式

组合

算法

穷尽式搜索程序

最优化

图3.3.3波长分配算法

（2）波长分配算法：

对于没有波长转换功能的网络，波长分配算法为已选定的路由分配波长，需满足波长一致性的要求。

波长分配问题可以转化为一个辅助图的着色问题。

从图3.3.2中可见，波长分配问题也可分为寻找和选择。

任何一个可用波长都可以分配给已选路由，所以寻找问题很简单。

剩下的问题就是怎样可用波长中进行选择：

哪一个可以最大化波长的利用率。

同选路问题相似，选择可以进一步分为顺序算法和组合算法。

1）顺序算法（贪婪算法）

－—选择顺序

*邻居数最大优先（Largestnumberofneighbor-first）机制选择邻居数最大的路由首先分配波长。

*可用波长最大优先（Largestavailablewavelength-first）机制把路由按可用波长数多少从大到小排序；

*业务量最大优先（Largesttraffic-first）机制按路由业务量大小确定波长分配顺序。

*最长路优先（Longestpath-first）机制依每条路中的跳数（hopcount）顺序来选路。

*最短路优先（Shortestpath-first）机制按与最长路优先机制现反的顺序选路。

*随机机制以随机的方式选路。

－—选择规则

*FF（Firstfit）机制依波长编号选第一个可用波长。

*最多使用优先（Mostusedfirst）机制为当前路由选择最多使用的波长。

*最少使用优先（Leastusedfirst）机制为当前路由选择最少使用的波长。

*随机机制：

随机的分配一个波长。

2）组合算法

――最优化算法：

可以采用穷尽式（exhaustive）搜索，但由于这是一个NP-C问题，不适用于大规模的网络。

――启发式算法：

启发式算法可以有效地用于图着色问题，进一步分为：

*遗传算法（GA-Geneticalgorithm）：

遗传算法仿用生物的进化与遗传，根据“优胜劣汰”原则，使所要求解决的问题从初始解逐步地逼进最优解。

在许多情况下，遗传算法优于传统的优化方法。

该算法允许所求得的问题是非线形的和不连续的，并能从整个可行解空间寻找全局最优解，避免只得出局部最优解。

同时，由于其搜索最优解的过程是有指导性的，避免了一般优化算法的维数灾难问题。

*模拟退火算法（SA-Simulatedannealingalgorithm）：

模拟退火算法是局部搜索算法的扩展。

它不同于局部搜索之处是以一定的概率选择领域中费用值大的状态。

理论上说它是一个全局最优算法。

*禁忌搜索算法（TABUalgorithm）：

禁忌算法是局部领域搜索算法的推广，是人工智能在组合优化算法