WDM网络中组播传送的几种优化算法研究（硕士学位论文）.doc

《WDM网络中组播传送的几种优化算法研究（硕士学位论文）.doc》由会员分享，可在线阅读，更多相关《WDM网络中组播传送的几种优化算法研究（硕士学位论文）.doc（71页珍藏版）》请在沃文网上搜索。

1、分类号 密级UDC 编号中 国 科 学 院硕士学位研究生学位论文WDM网络中组播传送的几种优化算法研究冉 敏指导教师 高随祥 教授 中国科学院研究生院博士生导师 申请学位级别 硕士 学科专业名称 计算机应用技术 论文提交日期 2005年3月 论文答辩日期 2005年5月 培养单位 中国科学院研究生院（本部） 学位授予单位 中国科学院研究生院 答辩委员会主席 声 明本人声明：本论文是我个人在导师指导下进行的研究工作的结晶及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做出的任何贡献均已在论文中作了明确的说明

2、并表示了谢意。签名： 日期：关于论文使用授权的说明中国科学院研究生院有权保留该论文的复印件，允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存该论文。签名： 导师签名：日期：摘 要随着网络流量呈指数方式持续快速增长，人们对带宽的要求越来越高。能够在一根光纤里传输多个光信号的光波分复用（WDM）网络，被认为是下一代网络中解决带宽问题的最具潜力的光网络之一。而组播作为一种点到多点的通信模式，其应用对带宽和服务的要求越来越高。因此，在WDM网络中进行组播传送会取得更好的传输效率。受到经费和技术的限制，光网络中的可用波长数、波长转换数等等网络资源通常是有限的。因

3、此，如何选择一种合理的波长分配和路由算法来提高和优化WDM网络的组播传输性能，日益成为人们关注的热点问题。本文作者从如下两个角度研究了该问题：一是约束条件下的网络优化算法，主要研究了构造时延受限的最小代价组播树算法。二是基于对组播路由和网络性能有重要影响的最小波长数和最小波长转换次数，研究并提出了两种组播路由近似算法，来构造一棵波长数较少或者波长转换次数最小的组播树。论文的主要工作如下：1、作者通过在蚂蚁选路的概率中加入成本因素，并且只增加优秀路径上的信息素，从而对现有蚁群算法进行了改进，加快了其收敛速度。作者将改进的蚁群优化算法与分层图相结合，提出了一种构造时延受限的最小代价组播树的并行算法

4、。2、作者利用拉格朗日松驰因子将成本函数加入到时延目标函数中，从而使时延受限最小成本组播问题简化为求最小成本组播树问题。通过修正拉格朗日松驰因子，最终得到一棵满足时延限制的最小成本组播树。该算法将时延和成本两种不相关的因素组合起来,是一种简单易行的方法。3、本文根据组播业务对服务质量要求的高低，提出了两种寻找较少波长数的方法。在节省波长资源的基础上，提出了跳数较少且阻塞率较低的波长路由算法。4、针对波长转换对网络传输时延和传输代价的增加，本文给出了一种构造波长图的新方法，并基于这种方法，提出了构造一棵波长转换次数最少或所用波长数最少的组播树方法，从而减少了波长转换所耗费的代价和时延。上述几种算

5、法都已通过仿真算例验证了其有效性，为相关的研究工作提供了参考和借鉴。关键词：WDM网络；组播；路由与波长分配VAbstractAs the Internet traffic continues to increase exponentially, more and more critical needs upon the bandwidth are putting forward. The optical Wavelength Division Multiplexing (WDM) network ,which can transfer several optical signals in a

6、 single optical fiber, is seen as a promising approach to solve the bandwidth problem in next generation networks. Multicast means one-to-many communication. Multicast applications have raised tremendous challenges in bandwidth and service. So, supporting efficient multicast in WDM networks becomes

7、eminent.Constrained by the price and technology, the network resources, such as the number of wavelengths , wavelength converts and so on, are usually limited. How to choose a reasonable Routing and Wavelength Assignment(RWA) algorithm to improve and optimize the multicast transmission performance i

8、n WDM networks is becoming an important issues.In this dissertation, the author studies this issues from two sides as follows: The first one is to consider the network optimization under the constraint condition, maily studies the multicast algorithms which can construct a sub-minimal cost tree unde

9、r a given delay bound. While, the second sides is to study the optimization algorithm from two important objectives, which have great impact to the multicast routing and the network performance. One is the minimal number of wavelength conversions required, and the other is the minimal number of wave

10、lengths used . Two multicast routing approximation algorithms are proposed to construct a multicast tree by using minimal wavelength conversions or small number of wavelengths. The main work in this dissertation is summarized as follows:1、The author presents an ameliorated ant colony optimization al

11、gorithm , which increase the speed of convergence by adding the cost factor to the routing probability and updating the pheromone only on the good path. On the basis of combining it with wavelength graphs, the author proposes a multicast routing algorithm using parallel computing to construct a mini

12、mal cost multicast tree under a given delay bound. 2、The author uses the Lagrange relaxation to reduce the complexity of the delay-constrained least-cost multicast problem to the least-cost multicast tree issues by adding the cost function into the delay function. Finally, it can get a delay-constra

13、ined least-cost multicast tree by updating the Lagrange relaxation parameters. For this algorithm can combine the different factors (cost and dalay ) as a unified factor, it is a simple method to implementation. 3、Two ways are put forward to find the small number of wavelengths under the different r

14、equirements of the quality of service in multicast session. Based on saving the wavelength resource, this paper presents a RWA algorithm which has small hops and low block rate.4、According to the network transmission cost and the delay increased by wavelength conversions, this dissertation gives a n

15、ew way to construct a wavelength graphs. Based on this method, an algorithm are proposed to construct a multicast tree that the number of wavelength conversion or the number of wavelengths used in the tree is minimized. This algorithm reduce the costs and the delay worked by wavelength conversions.O

16、verall, simulations shows that these algorithms which presented in this paper can get satisfied solutions and provide some references for the related research works. keywords: WDM networks ; multicast ; Routing and Wavelength Assignment(RWA) 目 录摘 要I第一章 引言11.1 WDM网络11.1.1 WDM 网络的RWA问题11.1.2 物理拓扑和逻辑拓扑

17、21.2 组播21.3 WDM网络中的资源限制41.3.1 波长连续性限制41.3.2 波长转换限制41.4 论文的主要工作61.5 本文的结构7第二章 有关研究基础概述82.1 描述WDM光网络的模型82.1.1 分层图模型82.1.2 辅助图模型82.1.3 矩阵模型92.2 WDM网络中点到点通信的路由与波长分配102.2.1 路由选路策略112.2.2 波长分配方法122.2.3 RWA合一算法142.3 组播树及相关算法152.3.1 最短路径树(SPT)方法152.3.2 基于最小生成树的组播树算法162.3.3 基于源节点和目标节点的完全图寻优方法162.4 WDM网络中组播的路

18、由及波长分配172.4.1 光树的路由172.4.2 常用的几类方法18第三章 基于蚁群系统的时延受限组播路由算法213.1 问题提出213.2 问题定义213.3 蚁群算法233.3.1 原理233.3.2 基本的蚁群系统模型243.3.3 基本蚁群算法的优缺点253.3.4 改进型蚁群算法263.4 构造一个分层图模型263.5 WDM网络中基于蚁群算法的受限组播路由算法273.5.1 算法描述273.5.2 生成组播树293.5.3 对信息素进行更新293.6 仿真313.7 结论32第四章 基于拉格朗日松驰的时延受限组播路由算法344.1 问题的提出344.2 问题定义344.3 用L

19、R解决WDM网络中时延约束的最小成本组播树问题364.3.1 拉格朗日松驰算法(LR)364.3.2 算法描述364.3.3 算法步骤384.4 仿真384.5 结论40第五章 WDM网络中基于较少波长的组播路由算法415.1 问题的提出415.2 问题的定义415.3 用贪婪算法求出满足较少波长数的新的拓扑图425.3.1 构建连通的波长覆盖图425.3.2 方法一：覆盖源节点和目标节点的较少波长集435.3.3 方法二：找出覆盖所有链路所需的较少波长445.3.4 两种方法的比较455.4 生成一棵跳数和阻塞率较低的组播树455.5 仿真455.6 结论48第六章 基于最少波长转换次数的组

20、播算法496.1 问题定义496.2 求最少波长转换次数506.2.1 构造波长图506.2.2 基于最少波长转换次数的最小成本树506.3 求最少波长数的方法516.4 基于最少波长转换次数进行波长和路由分配526.5 仿真526.6 结论54第七章 总结与展望557.1 总结557.2 未来的工作56参考文献57发表的学术论文情况61作者简历62致 谢63第39页第一章 引言第一章 引言本章介绍本论文的研究背景、一些基本概念以及本论文的研究意义和主要工作，主要介绍一些与本论文相关的背景知识，包括WDM网络和组播的基本概念，WDM网络中组播传送的优势，以及在WDM网络中实现组播的资源限制等。

21、1.1 WDM网络由于网络技术的飞速发展，多媒体技术的广泛应用，人们对网络带宽的需求呈指数增长，最初铺设的光纤已无法满足网络发展的需要，再投资重新铺设的费用又太高，于是光纤网中的复用技术的研究受到广泛关注，并有多种复用技术被提出，其中波分复用（Wavelength Division Multiplexing, WDM）技术被认为是最具潜力的光网络中的复用技术之一，也是现在人们普遍采用的一种复用方法。波分复用技术最早应用在美国。它是指在一根光纤上同时传送多个不同波长的光载波。这样一来，原先在一根光纤上只能传送一个光载波的单一信道就变成了可传送不同波长光载波的多个信道，从而使光纤的传输能力成倍增加

22、。另外也可以利用不同波长沿不同方向传输来实现单根光纤的双向传输。WDM的优势在于：由于能够在一根光纤上复用多个光业务流，所以WDM网络61-64可灵活地扩展带宽，降低复用成本。特别是在光交换机等全光器件引入后，光-电-光转换不再成为必须，WDM网络的传输速度可得到进一步的提高。 1.1.1 WDM 网络的RWA问题WDM网络中的通信是面向连接的通信，即通信双方在通信之前需要首先建立连接。建立连接的过程就是寻找一条路径，并为该路径的每条链路分配一个波长，使其满足全光传输的要求。这一过程称为WDM网络的路由与波长分配(Routing and Wavelength Assignment，RWA)。W

23、DM网络与传统网络的主要区别之一是，WDM网络的中间节点不能象传统网络那样缓存信息并以存储转发方式传输数据，而是以类似于线路交换的方式传输数据。因此，一旦通信请求不能立即获得可用波长，通信即告失败，这种情况称为阻塞(Blocked)。为了在WDM网络中实现有效通信，需要解决的基本问题就是RWA问题61、63。由于光网络承载的业务需求正呈爆炸式增长，而目前光网络的可用资源（波长、光纤等）却很有限。同时，如何在有限资源网络中为业务选择合适的路由和分配优化的波长对于网络资源的利用、管理和控制都有很大的影响。所以，RWA问题成为WDM光传送网络中的核心问题之一。 1.1.2 物理拓扑和逻辑拓扑光网络中

24、的物理拓扑是指光网络的物理节点和光纤链路互连的物理结构。光通道可以建立在物理拓扑图上，由物理路由和承载波长构成。逻辑拓扑是指在节点对间建立的所有光通道的集合。逻辑拓扑也叫虚拟拓扑，它是由光网络中的光通道和光树构成的。该方法是将每个波长作为一条虚链路，一根光纤就变成了多条链路，整个网络转换成一个由可用波长（虚链路）组成的网络拓扑图。1.2 组播组播(Multicast)的概念最早是1988年由Stanford大学的Steve Deering提出的。组播是一种组通信机制，它是一种从源节点(发送者)将信息同时发送给多个目的节点(接收者)的通信方式。所以，组播技术是通信网络将发起端的信息复制多份同时传

25、递给多个接收端的一种信息传递技术，即点对多点的通信。当只有一个目标节点时，组播传送就成为单播传送。当除源节点外的所有节点都是目标节点时，组播就变成了广播。由于组播传送在某些共享链路上只需将信息发送一次，而不必从源端对每一个目的端都发送一个信息副本，因此，与由多个点对点通信实现的点对多点通信方式相比，组播通信可以极大的节省带宽，有效地降低网络通信成本，增加网络通信能力，避免广播带来的泛洪问题。组播在现代计算机网络中有广泛的应用，它能有效地支持那些对带宽要求较高的业务。需要组播技术支持的业务类型主要是一些带宽密集型的业务，如：视频会议、软件文件的传递和镜像站点的文件复制、虚拟现实游戏、互联网新闻信

26、息的传播和电子邮件列表、远程教学、电子商务、视频点播、光存储网络(0SAN)等等。按请求的性质，可以将组播分为静态组播和动态组播。所谓静态组播是指组播请求预先知道网络的全局状态，并且没有实时性要求，网络系统对一组请求统一调度。与此相反，动态组播请求具有实时性，一旦到达，要求立即实现，所以也称为实时组播，通常是针对单个请求进行调度。随着服务质量（Quality of Service, Qos）概念的引入，对组播传送的Qos质量的要求也越来越高，它不仅需要将信息安全有效地传送到目的地，而且还对点到点的延迟、阻塞概率以及丢包率、传输成本等有严格的要求。在当前的通信网络中，带宽等网络资源相对于不断增长

27、的通信需求来说仍十分有限，如何在满足一定的Qos要求下，用尽可能少的网络资源来完成组播传送业务是需要解决的一个现实问题。这就是带有Qos约束的组播路由问题。WDM网络因其较大的带宽和潜在的高速传输能力，自然被广泛应用在组播传送领域，这种应用利用了WDM网络的高带宽和组播通信的高效率，从而有效地提高了网络的通信能力。因此，WDM网络中的组播通信方法已成为人们关注的热点。WDM网络中的组播是在WDM层进行组播传送的。为了支持WDM组播通信，WDM的开关节点应该具有光分离能力，它能将一个输入信号分离成到不同输出链路的多个信号。WDM网络中的组播主要有如下几点优势：1）在WDM层包含了整个光拓扑结构及

28、它的资源分布信息，在这一层，可根据每条链路的波长分配情况构造出一棵组播树。2）光分离器的出现和使用，使得在WDM网络中进行组播通信比电信号中的包复制更加有效。3）WDM网络中的组播传送不需要进行光-电-光的转换，这降低了点到点信息传输的延迟。光通道(Lightpath)和光树(Lighttree)是WDM网络中两个常用的概念。光通道是指在网络中两个节点间的物理路径，它可以跨越多个光链路，是网络节点间的全光通信信道。光通道的建立以可用波长为基础，按给定的规则为每条链路分配一个可用波长，中间节点直接使用光交换而不进行光电转换。该路径上的各链路被分配了相同的波长。当两条光路径同时经过同一链路时，它们

29、必须使用不同的波长，这就是波长连续性限制。为了支持WDM层的组播，Sahasrabuddhe等人首次在波长路由网络中引入了光树的概念。光树是一条点对多点的光通路概念的归纳，它是将点到点的光连接方式扩展为点到多点的光连接，就形成了光树。更准确地讲光树是点对多点没有环路的光通道。在WDM网络中组播传送一般是采用构建一棵组播树的方法来解决。组播树(Multicast Tree)就是一棵以源节点为树根，包含所有目的节点的树。在WDM网络中进行组播传送就是要找到满足条件的树，组播树中的每条边对应一条光纤链路，并分配一个可用波长。1.3 WDM网络中的资源限制1.3.1 波长连续性限制WDM网络系统的通信

30、基础是光通道。在无波长转换器(Wavelength Conversion)的WDM波长路由网络中，求解RWA问题要受下面两个条件的约束：1）同一光纤中的不同光通道必须分配不同的波长，这是保证网络能够正常运行的限制条件。2）波长连续性限制：即每一个从源节点到目的节点的光通道中的所有链路上使用的波长都必须是相同的。当一条通路的中间结点没有波长转换器时，光路上连接的多条链路必须使用同一波长。1.3.2 波长转换限制尽管WDM网络有助于带宽的扩展，但是系统的波长数目仍难以满足日益增长的通信需求。在WDM光纤网络中，一对一的连接是由光路支持的。一条光路中的波长分配必须满足波长连续性的约束条件。这就使得当

31、两个或多个使用相同波长的信号向相同的节点连接时造成波长竞争，即空闲的路由上没有一条端到端的空闲波长。这种情况会造成WDM网络阻塞率的大大提高。在网络的一些节点上放置波长转换器，可适度放松波长连续性的限制。在网络中的一个节点放置波长转换器，则经过该节点的光通道就可通过波长转换器来改变所使用的波长，而不必遵守波长连续性的限制，这样可避免有共享链路的光通道发生阻塞。波长转换能够解决交叉连接中的波长竞争，使波长能够再分配和再利用，从而可有效地提高网络的灵活性和可扩展性，降低网络的阻塞率，同时也有利于网络的运行、管理和控制。所以波长转换器的使用能很大程度地提高波长路由光网络的性能。WDM网络中根据波长转

32、换分为单跳系统(single-hop system)和多跳系统(multihop system)。在单跳系统中一个通道的所有链路必须使用相同的波长。在多跳系统中，由于有波长转换器，所以从源到目的节点的光连接通道中可以是多个使用不同波长的光路径的组合。但由于全光转换器技术还不够成熟，目前波长转换器的价格也很昂贵，而且波长转换的使用会增加传输时延。因此在实际应用中还应根据网络业务需求权衡网络中设置的波长转换器的个数与费用。sIP router ssWDM switchd1d2图1-1 (a) IP multicastsLight splittingIP router ssWDM switchd1d

33、2(c) WDM multicast21IP router ssWDM switchd1d2(b) IP multicast via WDM unicasts1.3.3 光分离能力的限制光分离能力是WDM网络中组播传送的又一资源限制因素。图1-1说明了具有光分离能力的组播传送过程与其它组播传送的不同之处。图1-1中(a)(b)(c)显示了从源节点s到两个目标节点d1、d2在三种情况下建立组播传送的方法。图(a)是在IP层建立源到目的节点的路由树，每个路由节点能复制数据包并把它传到它们的子节点。但这种方法需要在组播树的每个路由节点对每个数据包进行光/电/光（O/E/O）的转换，从而造成一些不必要

34、的传输和浪费。图(b)中从源节点到每个目标节点建立一条虚拟的光通道（Lightpath），避免了O/E/O的转换。但是需要多条单向通道。这对带宽消耗较大，不适于大型的组播传送。图(c)中的组播是在WDM层实现的，它是通过光分离器在交叉连接处对数据包进行复制，然后再传到不同的目标节点。这种方法因为在公共的链路上只占用一次带宽，相比图(b)所示的方法来说能更有效地节约带宽11。这种WDM网络中的组播传送方式对于象HDTV等这种对带宽要求高的服务中有很好的应用。但是基于成本原因，在实际网络中，并不是每个开关节点都具有光分离能力，我们将具有光分离能力的节点叫MC（Multicast capable）节

35、点，而不具有光分离能力的节点叫MI（Multicast Incapable）节点。因此，在实际应用中也应该在光分离器的使用成本和网络带宽两者间进行权衡。1.4 论文的主要工作本文所研究的问题是WDM网络中建立组播连接的过程和方法。针对WDM网络中组播的路由与波长分配问题，结合现有的一些算法，对受限组播树问题及组播树优化问题进行了分析研究，并基于不同的约束条件和优化目标，提出了相应的算法，以提高组播通信中的服务质量，优化网络性能、节省网络资源。本文的主要贡献包括：1、针对时延约束下的成本优化问题，提出了两种启发式算法。对于有约束的组播问题最常见的就是求解满足时延受限且成本最小的组播树。这个问题已

36、证明是NP-hard问题7。由于时延和成本是两个相互独立的参数值，满足最小成本的路径可能时延值会超过最大限制，所以在解决这种问题时，一般很难找到最优解，通常都是采用启发式算法，寻找满意解。在本文中，作者引入了蚁群算法。利用蚁群算法的并行性和鲁棒性，对基本蚁群算法进行了改进，将该算法应用在WDM网络组播问题的求解中，使问题能够真正地并行处理，并能得到较好的满意解。此外，在求解过程中，还充分考虑到波长转换器对时延和成本的影响，更适合于实际问题。此外，在本文中，作者还引入拉格朗日松驰因子来解决时延约束条件下的最小成本组播树问题。通过拉格朗日松驰因子，将时延和成本进行整合，作为一个参考因子，并通过调节

37、松驰因子的值，改变时延和成本因素在求解组播树过程中所占的比重，从而找到满意解。该方法计算简单，容易实现。2、从节省网络资源出发，针对所用波长数或波长转换次数最小为优化目标，提出了两种优化算法。基于波长连续性的限制以及波长转换器在网络中个数有限的情况，所需最少波长数或最少波长转换次数是WDM网络组播传送的一项重要指标。波长转换器的可用性会影响到路由选择能否进行，但过多地使用波长转换同时也会增加网络时延和网络成本。在一般网络中，组播树中所使用的波长数越少，通常情况下，意味着波长转换次数也会越少8。所以，常常通过优化组播树中所用的波长数来减少整个组播树的时延和成本。本文基于不同的业务需求，利用贪婪算

38、法提出了两种求较少波长数的算法。该算法简单易行，能够得到满意解。此外，本文还提出了一种新的构造波长图的方法，并利用该波长图得到了一种求最少波长转换次数或最少波长数的方法。1.5 本文的结构本文的内容共分为7章，各章的内容安排和论文的组织结构如下：第1章：介绍本论文的研究背景、一些基本概念以及本论文的研究意义和主要工作。第2章：介绍组播及WDM网络当前的研究状况。第3章：将蚁群系统引入WDM网络组播问题的求解中，利用分层图的方法，充分考虑了波长转换对时延和成本的影响，提出了一种基于蚁群系统的时延受限组播路由算法。第4章：针对时延和成本两种约束条件，采用拉格朗日松驰因子将时延和成本两项参数统一起来

39、，提出了一种时延约束的最小成本组播路由方法。第5章：对已有的求最小波长数方法进行了改进，得到两种根据不同业务要求求较少波长数的方法。第6章：给出一种基于最少波长转换次数的组播算法：通过将原网络拓扑图转换成一种波长图，然后依据所得波长图，得到组播所需的最小波长转换次数或最小波长数。在此基础上，得到跳数较小的组播树。第7章：总结全文，提出进一步的研究设想和建议。第二章 有关研究基础概述第二章 有关研究基础概述2.1 描述WDM光网络的模型2.1.1 分层图模型分层图模型是一个三维模型，其基本思想是将原始网络拓扑图G(V,E,W)复制W次，转换为波长图WG=(Vwg,Ewg)，然后在这个三维波长图上

40、来计算源节点到目的节点之间的最短路径。分层图上的每一层对应一个波长，也称一波长平面。光网络的分层图对业务的路由和波长选择是在不同的波长层面上完成的，即在同一波长层面上完成了路由和波长的选择。当有波长转换器时，可通过分层图中不同波长层面的相同节点间的链路相连来表示波长间的转换，并用波长转换的权值来表示该链路的权值。分层图模型的生成方法是：1）N=W*n表示分层图WG的顶点数，n为原始网络G的节点数，W为波长数。将N个顶点以超网格形式排列成W行、n列，每行n个顶点表示原始图G的n个顶点，每列W个顶点表示W个波长，每行称为一个波长面。则Vwg=vij,1iW, 1jn。2）在第i行，若原始顶点j与k

41、之间有边相连，并且波长i是可用的，则Vij与Vik之间用一条边相连，取其成本值为Cjk，时延值为jk。其中Cjk和jk是原网络拓扑图G(V,E,W)中连接节点j与k之间链路的成本和时延。3）在具有波长转换的顶点k，若该波长转换器可以将波长i转换为波长j，则在顶点Vik与Vjk之间增加一条边，其成本Ck(i,j)定义为实际转换成本，延迟时间dk(i,j)定义为实际转换时间。2.1.2 辅助图模型辅助图模型是根据WDM光网络中的光通道建立起来的一种网络模型。它将原网络中的每条光通道用一个节点表示。当不同的光通道通过同一链路时，这两个光通道节点就用一条边连接起来。由此构造出原网络的辅助图模型。2.1

42、.3 矩阵模型WDM网络中，可以用矩阵来描述光网络模型。设网络图G(E,L)，E为顶点集，表示顶点的个数。N表示节点对编号，且满足1*(-1)/2。L表示链路集合，P表示备用路由集合。下面是几种常用的矩阵模型。1、邻接矩阵矩阵中Eij表示节点i到j的邻接关系。节点Ei和Ej间有权重不为无穷的链路直接相连时，则令Ei=Ej =1。邻接矩阵是对称的0-1二元素矩阵，描述光网络节点间的物理连接情况，表示为：2、节点对通路矩阵这个矩阵描述的是网络中节点对与通路的对应关系。设P=P1, P2, Pp为网络节点对的通路集合。NPij为节点对Ni间的通路与通路Pi的包含关系。若NPij=1，则节点对Ni间的

43、通路包含Pi。否则令NPij=0。其矩阵表示为：3、链路通路矩阵这个矩阵描述的是网络中链路与通路的相关关系，简称LP矩阵，也是一个0-1二元素矩阵。当链路Li包含在通路Pi中时，令LPij=1。否则令LPij=0。其矩阵表示为：4、波长链路矩阵这个矩阵描述的是光网络中每条链路中的剩余波长。WLij=表示链路j上的第i个波长的剩余信道数。其矩阵表示为：2.2 WDM网络中点到点通信的路由与波长分配WDM网络中点到点通信的路由与波长分配是RWA问题的最基本形式。一般根据连接需求，将WDM网络中的RWA问题可分为静态RWA和动态RWA问题。静态RWA问题是指为一组确定的、需要建立的光通道选择路由并为

44、它们分配波长。因此又叫静态光通道建立（SLE: Static Lightpath Establishment）问题。静态RWA的优化目标通常是用最小的网络资源（如光纤、波长数量）为静态业务建立光通道。动态RWA问题是指在实时业务条件下的光通道路由选择和波长分配优化问题。此时的动态业务的到达是按逐条方式随机到达，业务经历一段连接时间后将被拆除。动态RWA问题又叫动态光通道建立（DLE: Dynamic Lightpath Establishment）。动态RWA算法的优化目标通常是最小化网络的阻塞概率（Blocking Probability）或使连接数最大。通常采用启发式算法。由于RWA问题是

45、NP-C问题，要在合理的计算时间内解决大型网络的RWA问题是很困难的。通常是将RWA问题整体考虑或拆解成两个子问题考虑，即路由子问题和波长分配子问题。一般是先考虑路由子问题，然后逐一为光通道分配波长。有时选路与分配波长的过程要反复进行，直到使网络最优化为止。2.2.1 路由选路策略路由选路策略是指在业务到达时为它选择一条优化的物理路由的方法。目前文献中提到的主要有三种策略61,63。1、固定路由选路策略（Fixed Routing）这是一种最简单直接的选路策略。该策略是在业务到达前，为任意两个节点对确定一条固定的可用路由。一般采用最短路算法（比如Dijkstra算法和Bellman-Ford算

46、法）为每个节点对分配固定不变光通道。该方法简单、速度快，但需要较多的波长资源。有时会使网络中的某些链路过于拥挤，造成波长不够分配的情况，并且可能导致严重的流量阻塞。可采用负载均衡的选路方法予以改进。2、自适应的备用路由选路策略（Adaptive Alternated Routing）该策略是对任意两个节点对间预先确定多条备用路由，例如可采用K-Shortest算法选取K条最短路，也可通过整数线性规划方法得到一组路由集。当业务到达时，则从多条备用路由中选择一条最优路由。目前确定自适应备用路由的方法有两类：一类是预先为节点对之间确定多条备用路由，当连接请求到达时，从备用路由中依据网络状态动态地选择一条路由作为主路由；另一类则不需要预先确定备用路由，而是在连接请求到达时，才根据网络状态选择路由。自适应的备用路由选路策略因为是根据网络的实时状态动态地选择路由，所以阻塞率较低，但时间复杂度较高，因此在采用适应性路由方案时应当综合考虑性能和效率两个方面的要求。3、固定的备用路由选路策略(Fixed Alternated Routing)该策略是对任意两个节点对间确定多条备用路由，并按一定的优先级顺序排列，排在最前面的称为主路由，其它称为备用路由。