1、I WDM 网络中组播传送的几种优化算法研究 摘 要 随着网络流量呈指数方式持续快速增长，人们对带宽的要求越来越高。能够在一根光纤里传输多个光信号的光波分复用（ WDM）网络，被认为是下一代网络中解决带宽问题的最具潜力的光网络之一。而组播作为一种点到多点的通信模式，其应用对带宽和服务的要求越来越高。因此，在 WDM 网络中进行组播传送会取得更好的传输效率。 受到经费和技术的限制，光网络中的可用波长数、波长转换数等等网络资源通常是有限的。因此，如何选择一种合理的波长分配和路由算法来提高和优化 WDM 网络的组播传输性 能，日益成为人们关注的热点问题。 本文作者从如下两个角度研究了该问题：一是约束
2、条件下的网络优化算法，主要研究了构造时延受限的最小代价组播树算法。二是基于对组播路由和网络性能有重要影响的最小波长数和最小波长转换次数，研究并提出了两种组播路由近似算法，来构造一棵波长数较少或者波长转换次数最小的组播树。 论文的主要工作如下： 1、作者通过在蚂蚁选路的概率中加入成本因素，并且只增加优秀路径上的信息素，从而对现有蚁群算法进行了改进，加快了其收敛速度。作者将改进的蚁群优化算法与分层图相结合，提出了一种构造时延受限的最小 代价组播树的并行算法。 2、作者利用拉格朗日松驰因子将成本函数加入到时延目标函数中，从而使时延受限最小成本组播问题简化为求最小成本组播树问题。通过修正拉格朗日松驰因
3、子，最终得到一棵满足时延限制的最小成本组播树。该算法将时延和成本两种不相关的因素组合起来 ,是一种简单易行的方法。 3、本文根据组播业务对服务质量要求的高低，提出了两种寻找较少波长数的方II 法。在节省波长资源的基础上，提出了 跳数较少且阻塞率较低的波长路由算法。 4、针对波长转换对网络传输时延和传输代价的增加，本文给出了一种构造波长图的新方法，并基于这种 方法，提出了构造一棵波长转换次数最少或所用波长数最少的组播树方法，从而减少了波长转换所耗费的代价和时延。 上述几种算法都已通过仿真算例验证了其有效性，为相关的研究工作提供了参考和借鉴。 关键词： WDM 网络；组播；路由与波长分配III A
4、bstract As 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 single optical fiber, is seen as a promising approach
5、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 eminent. Constrained by the price and technology, the n
6、etwork 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 in WDM networks is becoming an important issues. In thi
7、s 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 under a given delay bound. While, the second sides is to
8、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 wavelengths used . Two multicast routing approximation al
9、gorithms 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 algorithm , which increase the speed of convergence b
10、y 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 minimal cost multicast tree under a given delay bound.
11、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-constrained least-cost multicast tree by updating the Lag
12、range relaxation parameters. For this algorithm can combine the different factors (cost and dalay ) as a unified factor, it is a simple method 第 IV 页 to implementation. 3、 Two ways are put forward to find the small number of wavelengths under the different requirements of the quality of service in m
13、ulticast 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 new way to construct a wavelength graphs.
14、 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. Overall, simulations shows that these al
15、gorithms 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) 第 V 页 目 录 摘 要 . I 第一章 引言 . 1 1.1 WDM 网络 .1 1.1.1 WDM 网络的 RWA 问题 .1 1.1.2 物理拓扑和逻辑拓扑 .2 1.2 组播 .2 1
16、.3 WDM 网络中的资源限制 .4 1.3.1 波长连续性限制 .4 1.3.2 波长转换限制 .4 1.4 论文的主要工作 .6 1.5 本文的结构 .7 第二章 有关研究基础概述 . 8 2.1 描述 WDM 光网络的模型 .8 2.1.1 分层图模型 .8 2.1.2 辅助图模型 .8 2.1.3 矩阵模型 .9 2.2 WDM 网络中点到点通信的路由与波长分配 . 10 2.2.1 路由选路策略 . 11 2.2.2 波长分配方法 . 12 2.2.3 RWA 合一算法 . 14 2.3 组播树及相关算法 . 15 2.3.1 最短路径树 (SPT)方法 . 15 2.3.2 基于最
17、小生成树的组播树算法 . 16 2.3.3 基于源节点和目标节点的完全图寻优方法 . 16 2.4 WDM 网络中组播的路由及波长分配 . 17 2.4.1 光树的路由 . 17 2.4.2 常用的几类方法 . 18 第三章 基于蚁群系统的 时延受限组播路由算法 . 21 3.1 问题提出 . 21 3.2 问题定义 . 21 3.3 蚁群算法 . 23 3.3.1 原理 . 23 3.3.2 基本的蚁群系统模型 . 24 3.3.3 基本蚁群算法的优缺点 . 25 3.3.4 改进型蚁群算法 . 26 3.4 构造一个分层图模型 . 26 3.5 WDM 网络中基于蚁群算法的受限组播路由算法
18、 . 27 3.5.1 算法描述 . 27 3.5.2 生成组播树 . 29 3.5.3 对信息素进行更新 . 29 3.6 仿真 . 31 第 VI 页 3.7 结论 . 32 第四章 基于拉格朗日松驰的时延受限组播路由算法 . 34 4.1 问题的提出 . 34 4.2 问题定义 . 34 4.3 用 LR 解决 WDM 网络中时延约束的最小成本组播树问题 . 36 4.3.1 拉格朗日松驰算法 (LR) . 36 4.3.2 算法描述 . 36 4.3.3 算法步骤 . 38 4.4 仿真 . 38 4.5 结论 . 40 第五章 WDM 网络中基于较少波长的组播路由算法 . 41 5.
19、1 问题的提出 . 41 5.2 问题的定义 . 41 5.3 用贪婪算法求出满足较少波长数的新的拓扑图 . 42 5.3.1 构建连通的波长覆盖图 . 42 5.3.2 方法一：覆盖源节点和目标节点的较少波长集 . 43 5.3.3 方法二：找出覆盖所有链路所需的较少波长 . 44 5.3.4 两种方法的比较 . 45 5.4 生成一棵跳数和阻塞率较低的组播树 . 45 5.5 仿真 . 45 5.6 结论 . 48 第六章 基于最少波长转换次数的组播算法 . 49 6.1 问题定义 . 49 6.2 求最少波长转换次数 . 50 6.2.1 构造波长图 . 50 6.2.2 基于最少波长转
20、换次数的最小成本树 . 50 6.3 求最少波长数的方法 . 51 6.4 基于最少波长转换次数进行波长和路由分配 . 52 6.5 仿真 . 52 6.6 结论 . 54 第七章 总结与展望 . 55 7.1 总结 . 55 7.2 未来的工作 . 56 参考文献 . 57 第一章 引言 第 1 页 第一章 引言 本章 介绍本论文的研究背景、一些基本概念以及本论文的研究意义和主要工作，主要 介绍一些与本论文相关的背景知识，包括 WDM 网络和组播的基本概念， WDM网络中组播传送的优势，以及在 WDM 网络中实现组播的资源限制等。 1.1 WDM 网络 由于网络技术的飞速发展，多媒体技术的广
21、泛应用，人们对网络带宽的需求呈指数增长，最初铺设的光纤已无法满足网络发展的需要，再投资重新铺设的费用又太高，于是光纤网 中的复用技术的研究受到广泛关注，并有多种复用技术被提出，其中波分复用（ Wavelength Division Multiplexing, WDM）技术 被认为是最具潜力的光网络中的复用技术之一，也 是现在人们普遍采用的一种复用方法。 波分复用技术最早应用在美国。它是指在一根光纤上同时传送多个不同波长的光载波。这样一来，原先在一根光纤上只能传送一个光载波的单一信道就变成了可传送不同波长光载波的多个信道，从而使光纤的传输能力成倍增加。另外也可以利用不同波长沿不同方向传输来实现单
22、根光纤的双向传输。 WDM 的优势在于： 由于能够在一根光纤上复用多个光业务流，所以 WDM 网络61-64可灵活地扩展带宽，降低复用成本。特别是在光交换机等全光器件引入后，光 -电 -光转换不再成为必须， WDM 网络的传输速度可得到进一步的提高。 1.1.1 WDM 网络的 RWA 问题 WDM 网络中的通信是面向连接的通信，即通信双方在通信之前需要首先建立连接。建立连接的过程就是寻找一条路径，并为该路径的每条链路分配一个波长，使其满足全光传输的要求。这一过程称为 WDM 网络的路由与波长分配 (Routing and Wavelength Assignment， RWA)。 WDM 网络
23、与传统网络的主要区别之一是， WDM 网络的中间节点不能象传统网络那样缓存信息并以存储转发方式传输数据，而是以类似于线路交换的方式传输数据。因此，一旦通信请求不能立即获得可用波长，通信即告失败，这种情况称为阻塞 (Blocked)。为了在 WDM 网络中实现有效通信，需要解决的第 2 页 基本问题就是 RWA 问题 61、 63。 由于光网络承载的业务需求正呈爆炸式增长，而目前光网络的可用资源（波长、光纤等）却很有限。同时，如何在有限资源网络中为业务选择合适的路由和分配优化的波长对于网络资源的利用、管理和控制 都有很大的影响。所以， RWA 问题成为 WDM光传送网络中的核心问题之一。 1.1
24、.2 物理拓扑和逻辑拓扑 光网络中的物理拓扑是指光网络的物理节点和光纤链路互连的物理结构。光通道可以建立在物理拓扑图上，由物理路由和承载波长构成。逻辑拓扑是指在节点对间建立的所有光通道的集合。逻辑拓扑也叫虚拟拓扑，它是由光网络中的光通道和光树构成的。该方法是将每个波长作为一条虚链路，一根光纤就变成了多条链路，整个网络转换成一个由可用波长（虚链路）组成的网络拓扑图。 1.2 组播 组播 (Multicast)的概念最早是 1988 年由 Stanford 大学的 Steve Deering 提出的。组播 是一种组通信机制，它是一 种从 源节点 (发送者 )将信息同时发送给多个目的节点 (接收者
25、)的通信方式。 所以，组播技术是通信网络将发起端的信息复制多份同时传递给多个接收端的一种信息传递技术，即点对多点的通信。当只有一个目标节点时，组播传送就成为单播传送。当除源节点外的所有节点都是目标节点时，组播就变成了广播。由于组播传送在某些共享链路上只需将信息发送一次，而不必从源端对每一个目的端都发送一个信息副本，因此，与由多个点对点通信实现的点对多点通信方式相比，组播通信可以极大的节省带宽，有效地降低网络通信成本，增加网络通信能力，避免广播带来的泛洪问题。 组播在现代计算机网络中有广泛的应用，它能有效地支持那些对带宽要求较高的业务。需要组播技术支持的业务类型主要是一些带宽密集型的业务，如：视
26、频会议、软件文件的传递和镜像站点的文件复制、虚拟现实游戏、互联网新闻信息的传播和电子邮件列表、远程教学、电子商务、视频点播、光存储网络 (0 SAN)等等。 按请求的性质，可以将组播分为静态组播和动态组播。所谓静态组播是指组播请求预先知道网络的全局状态，并且没有实时性要求，网络系统 对一组请求统一调度。第一章 引言 第 3 页 与此相反，动态组播请求具有实时性，一旦到达，要求立即实现，所以也称为实时组播，通常是针对单个请求进行调度。 随着服务质量（ Quality of Service, Qos）概念的引入，对组播传送的 Qos 质量的要求也越来越高，它不仅需要将信息安全有效地传送到目的地，而
27、且还对点到点的延迟、阻塞概率以及丢包率、传输成本等有严格的要求。在当前的通信网络中，带宽等网络资源相对于不断增长的通信需求来说仍十分有限，如何在满足一定的 Qos 要求下，用尽可能少的网络资源来完成组播传送业务是需要解决的一个现实问 题。这就是带有 Qos 约束的组播路由问题。 WDM 网络因其较大的带宽和潜在的高速传输能力，自然被广泛应用在组播传送领域，这种应用利用了 WDM 网络的高带宽和组播通信的高效率，从而有效地提高了网络的通信能力。因此， WDM 网络中的组播通信方法已成为人们关注的热点。 WDM网络中的组播是在 WDM 层进行组播传送的。为了支持 WDM 组播通信， WDM 的开关节点应该具有光分离能力，它能将一个输入信号分离成到不同输出链路的多个信号。 WDM 网络中的组播主要有如
