毕业论文（设计）-RWA算法的研究.docx

RWA算法的研究摘要：本文研究了 WDM网中的选路与波长分配(RWA)问题主耍针对的是 有波长一致性限制的网络首先简单介绍了 WDM光传送网的一些基本概念然 后对WDM传送网的选路与波长分配(RWA)问题进行了分类，并综述了各种条件 下的RWA算法，对其进行了分类、比较最后在对以往算法分析和比较的基础 上，提出了一个新的RWA算法新算法中考虑了多个网络设计优化冃标，对网 络运营商有一定的参考价值关键词：WDM；选路与波长分配；优化算法；启发式算法AbstractThis study focuses on the routing and wavelength assignment (RWA) problem in WDM networks. Most of the attention is devoted to such networks operating under the wavelength-continuity constraint. Some concepts on WDM optical networking are studied first. Then we studied the associated research problems and challenges. Various RWA approaches are examined and compared. Finally, we proposed a new RWA algorithm, which include many factors of the WDM network and may be useful to a network maker.Keyword： WDM ； RWA； optimal algorithm； heuristic algorithm第一章 引 言波分复用(Wavelength Division Multiplexing一WDM)网络利用了光纤传输 链路的巨大带宽，随着WDM技术口趋成熟，WDM传输技术己经进入实用化和 商用化阶段。

WDM全光通信网是光纤通信未来发展的主要方向Z-o由丁光网 络对传输信号的速率和格式透明，具有灵活的波长选路和动态资源配置能力，可 以实现网络的动态重构，被认为是通信网络升级的首选方案如何利用现有的和 即将敷设的光纤连网，构成未来高速、大容量、多业务的WDM网络已经成为光 通信领域中的一个重大问题WDM网络节点处采用光分插复用器(OADM)或 光交叉连接设备(OXC)在光层建立光连接，即光通道(optical path),为高层 的多个逻辑电网络提供了高速、大容量的信息传送平台光通道的建立，要求在 传送网的物理结构中选择一条由业务源点到宿点的路由，并为其分配一定的波长 信道(参见图l.Do考虑到波长资源的重利用以及提高网络的阻塞性能，优化光 通道的选路和波长分配(Routing and Wavelength Assignment —RWA)方案成为 光通道层设计的核心问题RWA解决如何寻找一条合适的光通道并合理地分配 通道所使用的波长，使有限的资源充分发挥作用，以提供尽可能大的通信容量图1.1 WDM网建立的光通道在以下的文章中，首先介绍了 WDM网络中与RWA问题有关的一些基本概 念。

然后对RWA问题进行了分类讨论，并对己提出的RWA算法进行了研究、 总结在文章最后针对网状网提出了一种新的RWA算法、详细描述了该算法， 并把它和其它算法进行了比较2.1 WDM的定义光波分复用（WDM： Wavelength Division Multiplexing）技术是在一根光纤 中同时传输多波长光信号的一项技术具基本原理是在发送端将不同波长的光信 号组合起来（复用），并耦合到光缆线路上的同一根光纤中进行传输，在接收端 乂将组合波长的光信号分开（解复用），并作进一步处理，恢复出原信号后送入 不同的终端，因此将此项技术称为光波长分割复用，简称光波分复用技术oWDM 技术相当于在同一根光纤上创造了许多虚拟光纤，从而数倍乃至数十倍的提高了 传输容量2.2 WDM光传送网的分层结构分层结构是定义和研究光传送网的基础已发布的G.872建议（草案），以 明确在光传送网络加入光层，按建议，光层由光信道层，光复用段层和光传输层 组成，如图2.2.1 o光传送网络图2.2.1光通信网的分层结构光层221光信道层光信道层（optical channel layei*）负责为来自电复用段层的客户信息选择路由 和分配波长，为灵活的网络选路安排光信道连接，处理光信道开销，提供光信道层的检测，管理功能。

并在故障发生时，通过重新选路或直接把工作业务切换到 预定的保护路由来实现保护倒换和网络恢复222光复用段层光复用段层(optical multiplexing section layer)保证相邻两个波长复用传输设 备间多波长复用光信号的完整传输，为多波长信号提供网络功能其主耍包括： 为灵活的多波长网络选路重新安排光复用段功能；为保证多波长光复用段适配信 息的完整性处理光复用段开销；为网络的运行和维护提供光复用段的检测和管理 功能2.2.3光传输段层光传输段层(optical transmission section layer)为光信号在不同类型的光传输 媒质(如G.652,G.653,G.655光纤等)上提供传输能力，同时实现对光放大器或中 继器的检测和控制功能等通常会涉及以下问题：功率均衡问题、EDFA增益控 制问题和色散的积累和补偿问题2.3 WDM光传送网的拓扑结构任何通信网络都存在两种拓扑结构，即物理拓扑和逻辑拓扑(也称为虚拓 扑)其中物理拓扑表征网络节点的物理结构；逻辑拓扑表征网络节点间业务分 布情况图2.3.1中网络物理结构的一个例子11—16为物理链路，每根光纤上可采用多个波长。

接入点A-E OXC11 — 16物理链路图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)中用04表示图2.3.2（b）中，04,01是中间有0XC转接的；02,03,05是直接光路A-E 0XCU3 "（a）路由和波长分配 （b）逻辑结构图2.3.2 光路举例实际设计中，一种RWA情况是：提出所需建立的光路，为这种光路选取物 理路由并分配相应的波长例如，图2.3.2（b）中提出耍建立5条光路，图2.3.2（a） 就是一种选路和波长分配方案2.4 WDM光;传送网拓扑结构的主要议题在研究RWA问题的文献中，通常将网络支持的业务分为两类：1）静态业 务：给定一组连接建立请求，需要为这些请求寻找路由并在其路由上分配波长， 以使某些性能指标达到最优（如全网吞吐量最大、所需波长数和光纤数最少等 等；2）动态业务：光路请求随机到达和离开网络，相应当性能指标通常是光路 的阻塞率因此按照所支持的业务类型划分，RWA问题可分为静态RWA问题和 动态RWA问题。

在研究WDM全光网的拓扑结构时，有两类相关的主耍问题需耍解决第 一类问题称为“网络设计”问题，即通过网络的业务需求分布（可以使业务流分 布）和物理拓扑，确定网络的配置，包括光纤对数、节点交叉连接的规模、需要 的光放大器以及光载波分插复用器等研究该问题可以在静态业务条件下优化波 长资源，使网络需耍的波长数冃最小由于在大多数实际场合中每根光纤复用的 波长数冃是固定的，如果一对光纤（双向传输）不能传输某链路上所有预分配的 业务，那么在该线路方向上将需要更多的光纤对，因此问题研究的优化冃标转化 为最小化光纤数H或交叉连接节点的规模等内容，或者是上述两方面的组合最 终的优化测度应当是网络的成本相应可以通过每条链路需要的光纤数冃以及光 纤链路长度等参数来衡量如果从光通道层来建立的角度分析，静态业务下的选 路和波长分配（RWA）问题相当于这一类“网络设计”问题第二类WDM全光网的拓扑结构问题成为“网络运营”问题即对给定的 网络（已知拓扑和资源），在已知和可以预测业务量的平均分布情况下，假设实 际业务需求的变化是随机的，则网络可能存在一定的阻塞率反应动态的选路和 波长选择算法质量的指标是在给定利用度条件下的阻塞概率。

由于具有波长变换 功能的节点可以提高光通道中波长的选择能力，因此在波长资源相同的情况下， VWP网络比WP网络具有更好的性能网络运营”问题可以看作动态业务条件 下的RWA问题2.5基于光路的RWA与基于运送分组业务的RWAWDM光传送网既可以支持传送电路交换方式的业务，乂可以支持传送分组 交换方式的业务在传送不同类型的业务时，光通道层拓扑结构设计有着不同的 特点当光传送网用于传送电路交换型业务时，和传统当交换网的接续比较 类似此时，业务需求以单一波长信道的容量为单位，通过路由选择和配置波长 建立用丁•业务传送的端到端光连接电路交换型光传送网面向的是连接型业务， 而未来的光网络还需要支持支持分组数抑（无连接型业务）的传送由丁•两种业 务类型有着本质的区别，因此在光层网络的优化冃标和优化策略方面存在明显不 同支持分组交换业务的光传送网，其设计的核心是解决最优化网络虚拓扑的问 题2.6波长通道网络和虚波长通道网络电复用段一个单位的信息（如SDH信号、PDH信号甚至模拟视频信号）在 光网络中传送始，需耍为它选一条路由并分配波长（RWA）O由于一根光纤中能够 复用的波长数有限，且任何两路信号在一根光纤中不能使用和同波长，所以波长 资源的分配是光层管理的一项重耍内容。

根据OXC能否提供波长转换功能，光 通道可以分为波长通道（WP: Wavelength Path）和虚波长通道（VWP: Virtual Wavelength Path）o波长通道是指OXC没有波长转换功能，光通道在不同的波长 复用段中必须使用相同波长实现为了建立一条波长通道，光通道层必须找到一 条链路，在构成这条链路的所有波长复用段中，存在一个共同的空闲波长如果 找不到这样一条链路，该通道创建请求失败虚波长通道是指利用OXC的波长 转换功能，使光通道在不同的波长复用段可以占用不同的波长，从而提高了波长 的利用率建立虚波长通道时，光通道层只需找到一条链路，其中每个波长复用 段都有空闲波长即可波长通道方式耍求光通道层在选路和分配波长时采用集中 控制方式，因为只有在掌握了整个网络所有复用段占用情况后，才可能为一个新 传送请求选一条合适的路由在虚波长通道运作方式下，确定通道的传送链路后， 各波长复用段的波长可以逐个分配，因此可以进行分布式控制这种方法可以大 大降低光通道层选路的复杂性由于复杂网络中任何两个节点间都可能存在多条 路由，因此必需有一套有效的RWA算法，根据网络的拓扑结构和冃前的状态， 为新传送请求选路并分配波长。

另外，当光通道层中允许接入分组信息时，还需 要相应的分组交换型的选路算法与WP方案相比，VWP方案的一个显著特点是通道由经过的光交叉连接（OXC）节点具有波长转换的能力WP方案存在波长全局分配的问题，增加了 光通道实现的复杂性；VWP方案不存在这一问题从网络和通道的扩展能力上 看，VWP技术优T WP技术采用VWP技术的网络，波长的重利用率和路由 选择的自由度都要高于采用WP技术的网络所以，在某一•物理网络中建立相同 数量的光通道，与VWP方案相比，WP方案需要使用更多的波长，换句话说， 对相同物理网络结构和同样数冃的波长，VWP网络可以建立更多的。