RWA算法的研究.doc

RWA算法的研究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 MultiplexingWDM）网络利用了光纤传输链路的巨大带宽，随着WDM技术日趋成熟，WDM传输技术已经进入实用化和商用化阶段。WDM全光通信网是光纤通信未来发展的主要方向之一。由于光网络对传输信号的速率和格式透明，具有灵活的波长选路和动态资源配置能力，可以实现网络的动态重构，被认为是通信网络升级的首选方案。如何利用现有的和即将敷设的光纤连网，构成未来高速、大容量、多业务的WDM网络已经成为光通信领域中的一个重大问题。WDM网络节点处采用光分插复用器（OADM）或光交叉连接设备（OXC）在光层建立光连接，即光通道（optical path），为高层的多个逻辑电网络提供了高速、大容量的信息传送平台。光通道的建立，要求在传送网的物理结构中选择一条由业务源点到宿点的路由，并为其分配一定的波长信道（参见图1.1）。考虑到波长资源的重利用以及提高网络的阻塞性能，优化光通道的选路和波长分配（Routing and Wavelength Assignment RWA）方案成为光通道层设计的核心问题。RWA解决如何寻找一条合适的光通道并合理地分配通道所使用的波长，使有限的资源充分发挥作用，以提供尽可能大的通信容量。 图1.1 WDM网建立的光通道在以下的文章中，首先介绍了WDM网络中与RWA问题有关的一些基本概念。然后对RWA问题进行了分类讨论，并对已提出的RWA算法进行了研究、总结。在文章最后针对网状网提出了一种新的RWA算法、详细描述了该算法，并把它和其它算法进行了比较。第二章 WDM传送网的一些基本概念2.1 WDM的定义 光波分复用（WDM：Wavelength Division Multiplexing）技术是在一根光纤中同时传输多波长光信号的一项技术。其基本原理是在发送端将不同波长的光信号组合起来（复用），并耦合到光缆线路上的同一根光纤中进行传输，在接收端又将组合波长的光信号分开（解复用），并作进一步处理，恢复出原信号后送入不同的终端，因此将此项技术称为光波长分割复用，简称光波分复用技术。WDM技术相当于在同一根光纤上创造了许多虚拟光纤，从而数倍乃至数十倍的提高了传输容量。2.2 WDM光传送网的分层结构分层结构是定义和研究光传送网的基础。已发布的G.872建议（草案），以明确在光传送网络加入光层，按建议，光层由光信道层，光复用段层和光传输层组成，如图2.2.1。光传送网络电路层电通道层电复用段层光信道层光复用段层光 层光传输段层物理层（光纤）图2.2.1光通信网的分层结构2.2.1光信道层 光信道层(optical channel layer)负责为来自电复用段层的客户信息选择路由和分配波长，为灵活的网络选路安排光信道连接，处理光信道开销，提供光信道层的检测，管理功能。并在故障发生时，通过重新选路或直接把工作业务切换到预定的保护路由来实现保护倒换和网络恢复。2.2.2光复用段层 光复用段层(optical multiplexing section layer)保证相邻两个波长复用传输设备间多波长复用光信号的完整传输，为多波长信号提供网络功能。其主要包括：为灵活的多波长网络选路重新安排光复用段功能；为保证多波长光复用段适配信息的完整性处理光复用段开销；为网络的运行和维护提供光复用段的检测和管理功能。2.2.3光传输段层 光传输段层(optical transmission section layer)为光信号在不同类型的光传输媒质（如G.652,G.653,G.655光纤等）上提供传输能力，同时实现对光放大器或中继器的检测和控制功能等。通常会涉及以下问题：功率均衡问题、EDFA增益控制问题和色散的积累和补偿问题。 2.3 WDM光传送网的拓扑结构任何通信网络都存在两种拓扑结构，即物理拓扑和逻辑拓扑（也称为虚拓扑）。其中物理拓扑表征网络节点的物理结构；逻辑拓扑表征网络节点间业务分布情况。图2.3.1中网络物理结构的一个例子。l1l6为物理链路，每根光纤上可采用多个波长。 图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.4 WDM光传送网拓扑结构的主要议题在研究RWA问题的文献中，通常将网络支持的业务分为两类：1）静态业务：给定一组连接建立请求，需要为这些请求寻找路由并在其路由上分配波长，以使某些性能指标达到最优（如全网吞吐量最大、所需波长数和光纤数最少等等）；2）动态业务：光路请求随机到达和离开网络，相应当性能指标通常是光路的阻塞率。因此按照所支持的业务类型划分，RWA问题可分为静态RWA问题和动态RWA问题。在研究WDM全光网的拓扑结构时，有两类相关的主要问题需要解决。第一类问题称为“网络设计”问题，即通过网络的业务需求分布（可以使业务流分布）和物理拓扑，确定网络的配置，包括光纤对数、节点交叉连接的规模、需要的光放大器以及光载波分插复用器等。研究该问题可以在静态业务条件下优化波长资源，使网络需要的波长数目最小。由于在大多数实际场合中每根光纤复用的波长数目是固定的，如果一对光纤（双向传输）不能传输某链路上所有预分配的业务，那么在该线路方向上将需要更多的光纤对，因此问题研究的优化目标转化为最小化光纤数目或交叉连接节点的规模等内容，或者是上述两方面的组合。最终的优化测度应当是网络的成本相应可以通过每条链路需要的光纤数目以及光纤链路长度等参数来衡量。如果从光通道层来建立的角度分析，静态业务下的选路和波长分配（RWA）问题相当于这一类“网络设计”问题。第二类WDM全光网的拓扑结构问题成为“网络运营”问题。即对给定的网络（已知拓扑和资源），在已知和可以预测业务量的平均分布情况下，假设实际业务需求的变化是随机的，则网络可能存在一定的阻塞率。反应动态的选路和波长选择算法质量的指标是在给定利用度条件下的阻塞概率。由于具有波长变换功能的节点可以提高光通道中波长的选择能力，因此在波长资源相同的情况下，VWP网络比WP网络具有更好的性能。“网络运营”问题可以看作动态业务条件下的RWA问题。2.5基于光路的RWA与基于运送分组业务的RWA WDM光传送网既可以支持传送电路交换方式的业务，又可以支持传送分组交换方式的业务。在传送不同类型的业务时，光通道层拓扑结构设计有着不同的特点。当光传送网用于传送电路交换型业务时，和传统当电话交换网的接续比较类似。此时，业务需求以单一波长信道的容量为单位，通过路由选择和配置波长建立用于业务传送的端到端光连接。电路交换型光传送网面向的是连接型业务，而未来的光网络还需要支持支持分组数据（无连接型业务）的传送。由于两种业务类型有着本质的区别，因此在光层网络的优化目标和优化策略方面存在明显不同。支持分组交换业务的光传送网，其设计的核心是解决最优化网络虚拓扑的问题。2.6波长通道网络和虚波长通道网络电复用段一个单位的信息（如SDH信号、PDH信号甚至模拟视频信号）在光网络中传送始，需要为它选一条路由并分配波长(RWA)。由于一根光纤中能够复用的波长数有限，且任何两路信号在一根光纤中不能使用相同波长，所以波长资源的分配是光层管理的一项重要内容。根据OXC能否提供波长转换功能，光通道可以分为波长通道(WP: Wavelength Path)和虚波长通道(VWP: Virtual Wavelength Path)。波长通道是指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(Nondeterministic PolynomialComplete,非确定型多项式完全)组合优化问题，可以用整数线性规划（ILP）来寻找最优解，但这种优化方法的复杂性随网络规模的增大而急剧增加，当网络规模较大时因运算时间太长而无法接受。因此工程上常将RWA问题拆成选路子问题和波长分配子问题。方案二：选路与波长分配作为两个子问题来解决选路和波长分配这两个子问题也都是典型的NP-C 组合优化问题。图3.3.1是对目前已有算法的分类： 图3.3.1 算法分类这里首先把求解过程分成选路和波长分配两部分。每一子问题中又分成两步，即寻找与选择，最后按照所用的具体算法进行分类。图3.3.2、3.3.3分别给出了解决选路和波长分配问题的算法的具体实现方法。寻 找选 择寻找方法寻找顺序选择顺序选择规则最短路径法-加权最短路径最大流量优先 随机k-最短路径-随机固定最长优先最短优先随机固定概率最小顺序算法（贪婪算法）随机循环(random rounding)启发式组合算法整数线性规划最优化图3.3.2选路算法(1)选路算法：在选路问题中，考虑所有可能的源目的对是不实际的，因为计算时间随着网络规模的增长成指数增长。因此，寻找功能通常由最短路径算法及它的变种（variations）实现。在k最短路径算法中（即：有多个备选路由），选择功能由顺序算法或组合优化算法来实现。顺序算法（也叫贪婪算法）是最简单的一种。它按顺序为每一条光路进行选择，这其中需要考虑两方面：选择顺序、选择规则。选择顺序是指先为哪一个光连接选择路由，选择规则是从备选路由中选择的标准。 图3.3.2解释了选路算法：最短路径（SPShortest path）：最短路径算法寻找从源节点到目的节点的一条最短的光路。加权最短路（WSPWeighted shortest path）：加权最短路算法是一种最短路算法，但是链路代价可以随着已建立的路由数动态的变化。因此，它需要一个寻找顺序。例如：最大业务量优先（Largest traffic first）：从需要建立的光路中优先选择业务量最大的光路来寻找路由；随机（Random）机制以随机的顺序来选择需要建立的光路。但是这种方法不需要选择功能，因为它也是只为每个源目的对选择一个路由。K最短路径（K-SPK-shortest path）：k-最短路径算法为每一源目的对寻找多个路径，k个备选路由增加了选路的灵活性。然而，选路问题变成了选择问题：为所有的源目的对选择一个代价（跳数或链路代价）最小的路由。选择功能如下： 1）顺序算法（贪婪算法）选择顺序* 随机（Random）机制从所有未建立路由的光连接中以随机的方式选择；* 固定（Fixed）机制把光连接按某种规则排序（如按链路数降序），然后依次选取；* 最长路优先(Longest-first)机制把光通路按通路的长度（跳数或代价）由大到小排序，先选长路由；* 最短路优先（Shortest-first）机制把光通路按通路的长度（跳数或代价）由大到小排序，先选短路由。选择规则* 随机机制：从备选路由中随机选取一条。* FF(Firstfit)机制：从备选路由中选择第一个符合条件的路由。* 概率（probability）机制：依一定的概率从备选路由中选择一条路由。* 链路最小权重（minimumweighted link）优先机制：选择所有链路上已经建立的路由数最小的路由。2）组合算法最优化算法（Optimal algorithm）：这是一个多商品流问题，用整数线性规划可以得到最优解。最优化选择可得到最优的结果，但是网络规模较大时计算的复杂程度是无法忍受的。启发式算法（Heuristic algorithm）：启发式算法是根据概念推出的优化算法，能得到较优的结果，但不一定是最优。它降低了组合空间（combination space），在所设计的规则指导下修改所选的路由，多次循环以靠近优化目标，直到循环无法得到更优结果为止。 寻 找选 择 寻找顺序寻找规则选择顺序选择规则所有波长-随机固定最长优先最短优先随机FF(First fit)最少使用最多使用顺序算法（贪婪算法）GA（遗传算法）SA（模拟退火算法）Random Rounding（随机循环）TABU（禁忌搜索）启发式组合算法穷尽式搜索程序最优化图3.3.3 波长分配算法(2)波长分配算法：对于没有波长转换功能的网络，波长分配算法为已选定的路由分配波长，需满足波长一致性的要求。波长分配问题可以转化为一个辅助图的着色问题。从图3.3.2中可见，波长分配问题也可分为寻找和选择。任何一个可用波长都可以分配给已选路由，所以寻找问题很简单。剩下的问题就是怎样可用波长中进行选择：哪一个可以最大化波长的利用率。同选路问题相似，选择可以进一步分为顺序算法和组合算法。1）顺序算法（贪婪算法）选择顺序 * 邻居数最大优先（Largest number of neighbor-first）机制选择邻居数最大的路由首先分配波长。* 可用波长最大优先（Largest available wavelength-first）机制把路由按可用波长数多少从大到小排序；* 业务量最大优先（Largest traffic-first）机制按路由业务量大小确定波长分配顺序。* 最长路优先（Longest path-first）机制依每条路中的跳数（hop count）顺序来选路。* 最短路优先（Shortest path-first）机制按与最长路优先机制现反的顺序选路。* 随机机制以随机的方式选路。选择规则* FF(First fit)机制依波长编号选第一个可用波长。* 最多使用优先（Most used first）机制为当前路由选择最多使用的波长。* 最少使用优先（Least used first）机制为当前路由选择最少使用的波长。* 随机机制：随机的分配一个波长。2）组合算法最优化算法：可以采用穷尽式（exhaustive）搜索，但由于这是一个NP-C问题，不适用于大规模的网络。启发式算法：启发式算法可以有效地用于图着色问题，进一步分为： * 遗传算法（GA-Genetic algorithm）：遗传算法仿用生物的进化与遗传，根据“优胜劣汰”原则，使所要求解决的问题从初始解逐步地逼进最优解。在许多情况下，遗传算法优于传统的优化方法。该算法允许所求得的问题是非线形的和不连续的，并能从整个可行解空间寻找全局最优解，避免只得出局部最优解。同时，由于其搜索最优解的过程是有指导性的，避免了一般优化算法的维数灾难问题。 * 模拟退火算法（SA-Simulated annealing algorithm）：模拟退火算法是局部搜索算法的扩展。它不同于局部搜索之处是以一定的概率选择领域中费用值大的状态。理论上说它是一个全局最优算法。 * 禁忌搜索算法（TABU algorithm）：禁忌算法是局部领域搜索算法的推广，是人工智能在组合优化算法中的一个成功应用。禁忌算法的特点是采用了禁忌技术。所谓禁忌技术就是禁止重复前面的工作。为了回避局部领域搜索陷入局部最优的主要不足，禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，一次来跳出局部最优点。文献5中对以上几种启发式算法应用于图着色问题进行了研究，对比表明禁忌搜索算法的性能最好。 第四章 动态RWA算法4.1动态RWA问题分析所谓动态RWA问题,是指在实时业务条件下的光通道路由选择和波长分配优化问题。此时光通道的连接请求是随机到达的，并且已建立的连接在维持任意一段时间后会被撤销，这一点和普通电话网中的呼叫处理过程十分类似。由于需要建立的光通道数量和位置是不固定的，并且随时在不断变化，因此以资源优化（最小化波长数目）为目标已不能反映实际情况的要求，根据动态业务的特点应当选择服务性能指标（呼损率/阻塞率）作为动态RWA问题的优化目标。建立连接时选择阻塞率最小的方案，同时也意味着在有限的网路资源下能够支持建立数量尽可能多的光通道连接。4.2动态RWA解决方案：方案一：选路与波长分配作为一个整体的问题来解决采用分层图（layered-graph）的方法可以将选路和波长分配一步完成。OXC中的光开关是空间域的连接，波长分配是频率域的连接，从提供通道的角度看，空域和频域的作用是一致的。分层图将空域和频域结合起来，绘出一张新的通道图，动态RWA问题成为在分层图中选取一条通道的问题。各种动态选路的算法都可考虑，目标是阻塞率最小。方案二：选路与波长分配作为两个子问题来解决通常由于计算量的问题，对于大型网络的RWA方案一不可行。即使是启发式算法计算量也非常大。更实际的方法是把它分成选路和波长分配两个子问题，这样做的代价是结果不如以方案一来求解优化。目前已提出了许多种启发式方法，现总结如下。（1）选路子问题：有三种基本的方法来解决此问题：固定路由、固定备用路由和自适应路由。固定路由(Fixed routing)：对于给定的源目的对最简单的方法是选固定路由。通常用固定最短路由。用标准的最短路径算法（如Dijkstra或Bellman-Ford算法）预先为每个源目的对算出最短路由。当请求到达时，用预先决定的路由来建立光路。显然，这种方法的缺点是选路决定不是依据网络当前的状态。这可能导致网络中的一些链路过分拥塞，而其他的链路空闲。这将导致高的阻塞率。固定备用路由(Fixed-alternate routing)：这是固定路由的一种改进，一个请求的路由从预先决定的固定路由列表中选择。这种方法叫固定备用路由选路。当请求到达时，源节点将要通过一些标准（如最小跳数）在被选路由中选择一个最佳路由，然后在该路由上建立光通道。这种方法比固定路由的阻塞率低。自适应路由(Adaptive routing)：自适应路由中，源节点到目的节点的路由由当前网络的状态（即所有进行中的连接信息）决定。自适应路由的一个典型形式是自适应最短代价路径（adaptive shortest-cost-path）选路。当一个连接请求到达时，源节点根据网络当前状态计算连接的最短路径，如果没有可用路由则阻塞。这种方法的优势是它降低了阻塞率。（2）波长分配子问题：当连接请求到达时，必须运用在线（on-line）算法来分配波长以使阻塞率最小。到目前为止已有提出了许多启发式算法，下面介绍几种常见的：随机（Random）波长分配：从该路由上已建光路所使用的波长之外，随机地另选一个波长。最先适用（First FitFF）波长：将波长编号，从低到高依次观察是否已在该路由上建立光路使用，首先找到的就被使用。最大总数（Max Sum-MS）算法：思路是按分配后网络中仍可容纳的光路数最大为目标来分配波长。采用该算法的阻塞率优于FF算法（但有时差别不大），代价是增加复杂性。最少使用波长（Least UsedLU）：这种方法是为了使波长的负载均衡而提出了，它优先选用利用率小的波长来满足连接请求。但是这种机制引入了大量的通信开销来搜集有关信息计算波长的利用情况，因此此方案不可取。最多使用波长(Most Used MU)：与LU相反，这种方法优先选用利用率高的波长。由于MU保留了极少使用的波长，节省了空闲资源，因而它的性能会比LU好。MU的通信开销与LU相同。在参考文献2中共介绍了11种波长分配算法，并对这些方法进行了比较。对于将选路和波长分配分两步进行的算法，仿真表明，影响阻塞率的主要是选路算法。好的选路算法会显著地减小阻塞率，而各种波长分配算法的性能差别不大。因此，在工程上可采用一种自适应算法加简易的FF波长分配算法。第五章 一种新的RWA算法5.1新算法的提出以往RWA问题的研究提出了许多优化目标，包括全网吞吐量最大、所需波长数和光纤数最少等等。在文献9中提出一种新的优化目标：最大化连接可得的总利润。在该文中给出相应的RWA算法可描述如下：用Dijkstra算法给出利润最大的路径，然后用贪婪算法来分配波长。但该文中并没有考虑网络的其它参数（如路径长度等），实际中网络运营商往往希望在获得最大利润的同时能节省资源。因此本文针对无波长转换WDM网络提出了一种新的RWA算法，它的优化目标为：在有限的资源下，建立的光路连接可获得最大利润、最短路径并尽量减少所用的波长数目。我们提出新算法的目的有两个：一是尽量把多目标结合起来，折中考虑；二是针对这个目标给出一个比较完善的算法描述。路径最短即要求光通道经过的光纤长度最小，这对有许多节点组成，且节点之间距离较大的网络是非常重要的，因为这可以减少色散和噪声积累。波长是网络的一个重要资源，所以应尽量减少波长使用的数目。5.2问题的数学描述5.2.1网络的假设：1） 所有光纤中的复用波长数相同；2） 网络节点无波长转换功能；3） 对于给定的链路用无论用哪个波长成本都是相同的。5.2.2符号定义输入参数：无向图G(V,A)：对于一给定网络，其物理拓扑可用它表示。其中V为节点集，A为边集；n=|V|,L=|A|, n表示节点个数，L表示边的个数。则V=, A=,；D：流量矩阵=2表示在节点和节点之间有两个连接请求；：长度矩阵；如果( ) A 则 =；C：开销矩阵；如果连接( ) A则=；E：收入矩阵表示满足节点和节点之间的连接请求所得的收入；：表示每一链路可用波长数；：允许光通道的最大长度(由传输系统的物理条件限制)。常量：表示节点和节点之间的备用路由数；：表示在第r个路由上连接节点到节点的开销；：表示在第r个路由上连接节点到节点的路径长度；：如果第j条边用来做从节点到节点第r个路由则=1否则=0。变量：=1表示从节点到节点的连接占用第r个路由、第k个波长。5.2.3数学模型：目标函数： max = （1）式子（1）表示总利润（总收入总开销）最大 minimize = （2）式子(2)表示光通道总长度最短。如果假设每段路径的长度相等（不妨都取为1）则上式表示光通道的跳数最小，此时优化目标就变为光通道的跳数最小。为了算法简单我们考虑把两个目标综合在一起化成单目标问题来解决，这里采用的是将连接所得利润与该连接的路径长度相比作为优化目标，即 max 上式的物理意义可以理解为单位长度的利润最大或利润率最大，当每段路径的长度相等时可以理解为单位跳数的利润最大。minimize （3）在各个链路上建立的光连接所用波长数最小。约束条件： ， （4）在节点和节点之间建立的光路数，不超过连接请求数目。 j=1,L （5）对每条链路jA，在该链路上建立的光连接数不能超过可用波长数。，那么并不是所有的请求都能满足，所以只能从，.，选出个作为输出解。至于怎样选择可以作为一个背包问题来解决（参见5.3.2）。这一问题已有成熟的算法来解决，可以求出一个最佳解。 5.3.2 算法的一些解释：1) step1做的是选路工作，满足前两个目标：选出利润最大和路径最短的路径，也可以说成是单位长度的利润最大。2) step3中的辅助图的生成规则如下：.辅助图的节点代表连接的源目的节点对（不妨也相应的用来表示）；.如果两个连接中有共用的链路，则这两个连接所对应的源目的节点对所生成的辅助图的节点间存在一条边，参见图5.3.1。图5.3.1中，左面是一个网络的物理结构，中间是选好的路由及分配的波长，右面是我们需要着色的辅助图。为了避免网络中的波长冲突，辅助图中相邻的节点必须染成不同的颜色。这样波长分配问题就转化为辅助图的着色问题。图5.3.1 辅助图的生成3) 图着色问题：图的点着色问题是一个NP-C问题，所以必须采用启发式算法来获得实用解。现在已提出许多启发式算法，如贪婪算法（Greedy Algorithms）、模拟退火算法（SASimulated Annealing）、遗传算法（GAGenetic Algorithms）、禁忌搜索（TSTABU Search）等。其中禁忌搜索的性能最好（参见图5.3.25.3.3）。（注：图中的DSATUR是贪婪算法的一种） 图5.3.2 各种图着色算法运行时间对比 图5.3.3 不同算法着色所需颜色数对比4) 用禁忌搜索方法解图着色问题用禁忌搜索方法解图着色问题，可得出使所有的节点都被着色所需的最小颜色数k。算法中应用禁忌搜索算法，就是要对第三个目标（波长数最小）进行优化。 设辅助图为G(V,E)，其中V是节点集V=1,2,n,E是边集，E=（i , j）| i ,j V,（i , j）表示连接i , j 的一个边。若V 、V=，且内部的任何两个节点没有E中的边直接连接，则称（，）为V的一个划分。图的节点着色问题可以描述为：求一个最小的k，使得（，）为V的一个划分。对于给定n个节点的无向图，禁忌搜索算法求解图节点覆盖问题可以分为两步。第一步是给定一个常数k，考虑目标函数(，)|（）|+|()|+ +|()|, 其中|()|为中直接连接两个节点的边数。(，)为V的一个划分的充分必要条件是(，)0。第二步的主要工作是：对不满足(，)0的(，)进行优化计算，从而决定是否增加子集的个数k；从满足(，)0的划分中选择最小的划分数k。将解的形式用下面形式表示：，1，1jn其中表示的j个节点在的集合中。解的第x个分量变化为：,从原在第集合中改变到第集合中。每一个解S的邻域由那些满足上面的变化且只有一个分量变化的解组成，共有nk个邻居(包含自身)，每一个节点（分量）可以选择k个划分集之一。禁忌： ）且（nbiterbestiternbmax）时，计算nbiter：nbiter1；产生N(S)的一个候选集,要求候选元素x是非禁忌的或是特赦的(x)A(S)；在中选目标值最有的解；若()A(S)，则A()：= A()1；否则若(S)A()，则A()： A(S)1；更新禁忌表；若()(bestsol)，则bestsol：；bestiter：nbiter；S：= 继续；结束。输出：计算中的最优解。5) 背包问题及其在算法中的应用背包问题是指有不同价值、不同重量的物品k件，求从这k件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和为最大。当算法中用到背包问题时，可以把算法中的参数与背包问题做如下对应：背包问题中的概念 算法中的参数 k件物品 ，.，物品的总重量 选出的的总个数 物品的限定重量 最多可用波长数物品的价值 中所有路径的利润率之和背包问题的解决及程序可见参考资料13。5.4新算法与原有算法的比较 将新算法与以往算法相比较而言可得出以下结论： 1新算法中考虑三个网络特性，是这三个特性的一个折中。现有的文献大多仅考虑众多网络优化的目标中的一个，这就大大地限制了它们的应用范围。网络的多目标优化将是未来RWA问题研究的一个趋势，怎样综合优化多个目标也是RWA算法研究的一个角度。2新算法在路径确定以后分配波长时是从整体考虑的，应用了现代优化算法中的禁忌搜索算法，并把它和背包问题结合起来而求得的解。解的优化程度主要取决于禁忌搜索的性能，而对比表明禁忌搜索在解决这类问题时的性能是很好的，所以得出的解也是接近最优的。3选路算法对减小利用的波长数目也有很大影响，而我们在新算法的选路问题中为了简单没有考虑这个因素，只是在分配波长时尽量优化这个目标。另外，我们在选路和波长分配问题中都采用的是启发式算法，所以最后得到的优化解不一定是最优解。结束语 WDM光传送网被认为是下一代高速广域骨干网的理想选择，就目前的研究状况而言，该领域内的下列问题有待进行深入研究。1）文中已指出，RWA算法的动态程度越高，其性能越好。但动态RWA算法基本上都是中心式算法，需要利用全网信息。从简单和便于扩展的角度出发，很有必要研究快速，高效的分布式算法。2）是否需要在WDM网中引入波长变换一直是光网研究领域的热点问题，波长变换究竟能对网络性能有多大的改善，否可用波长变换替代全功能波长变换以及如何引入部分波长变换等问题仍值得深入研究。3）由于实际铺设的光缆都含有多对光纤，研究多光纤网以充分利用资源是十分必要的。4）网络优化的目标很多，但现有文献大多仅考虑其中一个，其结果虽然在某一网络特性上达到了最优，但网络的代价由于缺少各个特性之间的均衡和折衷，并没有因为波长分配的优化而降低或没有达到最优。因此需要研究综合优化指标下的RWA算法。5）光网中出现故障（如链路和节点故障）时，特殊设计的RWA算法能够在一定程度上进行补偿。研究支持光层自愈的高效RWA算法是十分必要的。6）现有的理论分析都将呼叫到达过程假定为泊松过程。而近年对网络业务量的研究表明，这种业务模型在对业务特性的描述上有一定的缺陷，有必要采用新的业务模型（如自相似业务模型）开展研究。7）有必要研究如何将文献中若干动态RWA算法与网络的生存性中恢复问题相合，以提