【毕业学位论文】（Word原稿）WDM网络中组播传送的几种优化算法研究-计算机应用技术

I 分类号 密级 编号 中 国 科 学 院 硕士学位研究生学位论文 络中组播传送的几种优化算法研究 指导教师 教授 中国科学院研究生院博士生导师 申请学位级别 硕士 学科专业名称 计算机应用技术 论文提交日期 2005 年 3 月 论文答辩日期 2005 年 5 月 培养单位 中国科学院研究生院（本部） 学位授予单位 中国科学院研究生院 答辩委员会主席 明 本人声明：本论文是我个人在导师指导下进行的研究工作的结晶及取得的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做出的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名： 日期： 关于论文使用授权的说明 中国科学院研究生院有权保留该论文的复印件，允许论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存该论文。 签名： 导师签名： 日期： 要 随着网络流量呈指数方式持续快速增长，人们对带宽的要求越来越高。能够在一根光纤里传输多个光信号的光波分复用（ 络，被认为是下一代网络中解决带宽问题的最具潜力的光网络之一。而组播作为一种点到多点的通信模式，其应用对带宽和服务 的要求越来越高。因此，在 络中进行组播传送会取得更好的传输效率。 受到经费和技术的限制，光网络中的可用波长数、波长转换数等等网络资源通常是有限的。因此，如何选择一种合理的波长分配和路由算法来提高和优化 络的组播传输性能，日益成为人们关注的热点问题。 本文作者从如下两个角度研究了该问题：一是约束条件下的网络优化算法，主要研究了构造时延受限的最小代价组播树算法。二是基于对组播路由和网络性能有重要影响的最小波长数和最小波长转换次数，研究并提出了两种组播路由近似算法，来构造一棵波长数较少或者波长转换次数 最小的组播树。 论文的主要工作如下： 1、作者通过在蚂蚁选路的概率中加入成本因素，并且只增加优秀路径上的信息素，从而对现有蚁群算法进行了改进，加快了其收敛速度。作者将改进的蚁群优化算法与分层图相结合，提出了一种构造时延受限的最小代价组播树的并行算法。 2、作者利用拉格朗日松驰因子将成本函数加入到时延目标函数中，从而使时延受限最小成本组播问题简化为求最小成本组播树问题。通过修正拉格朗日松驰因子，最终得到一棵满足时延限制的最小成本组播树。该算法将时延和成本两种不相关的因素组合起来 ,是一种简单易行的方法。 3、本 文根据组播业务对服务质量要求的高低，提出了两种寻找较少波长数的方法。在节省波长资源的基础上，提出了 跳数较少且阻塞率较低的波长路由算法。 4、针对波长转换对网络传输时延和传输代价的增加，本文给出了一种构造波长图的新方法，并基于这种方法，提出了构造一棵波长转换次数最少或所用波长数最少的组播树方法，从而减少了波长转换所耗费的代价和时延。 上述几种算法都已通过仿真算例验证了其有效性，为相关的研究工作提供了参考借鉴。 关键词： 络；组播；路由与波长分配V s to in a is as a to in in DM by as of so to a to DM is an In as is to a a is to to is of is of to a by or of in is as 1、 an of by to on On of it a to a a 2、 to to by it a by as a it is a 第 to 3、 to of of of in on a 4、 to by a to a on an to a of or of in is by in 第 目 录 摘 要 . 一章 引 言 . 1 络 . 络的 题 . 物理拓扑和逻辑拓扑 .组播 .络中的资源限制 . 波长连续性限制 . 波长转换限制 .论文的主要工作 .本文的结构 .二章 有关研究基础概述 . 8 描述 网络的模型 . 分层图模型 . 辅助图模型 . 矩阵模型 .络中点到点通信的路由与波长分配 . 路由选路策略 . 11 波长分配方法 . 一算法 .组播树及相关算法 . 最短路径树 (法 . 基于最小生成树的组播树算法 . 基于源节点和 目标节点的完全图寻优方法 .络中组播的路由及波长分配 . 光树的路由 . 常用的几类方法 .三章 基于蚁群系统的时延受限组播路由算法 . 21 问题提出 .问题定义 .蚁群算法 . 原理 . 基本的蚁群系统模型 . 基本蚁群算法的优缺点 . 改进型蚁群算法 .构造一个分层图模型 .络中基于蚁群算法的受限组播路由算法 . 算法描述 . 生成组播树 . 对信息素进行更新 .仿真 .第 结论 . 32 第四章 基于拉格朗日松驰的时延受限组播路由算法 . 34 问题的提出 . 34 问题定义 . 34 用 决 络中时延约束的最小成本组播树问题 . 36 拉格朗日松驰算法 (. 36 算法描述 . 36 算法步骤 . 38 仿真 . 38 结论 . 40 第五章 络中基于较少波 长的组播路由算法 . 41 问题的提出 . 41 问题的定义 . 41 用贪婪算法求出满足较少波长数的新的拓扑 图 . 42 构建连通的波长覆盖图 . 42 方法一：覆盖源节点和目标节点的较少波长集 . 43 方法二：找出覆盖所有链路所需的较少波长 . 44 两种方法的比较 . 45 生成一棵跳数和阻塞率较低的组播树 . 45 仿真 . 45 结论 . 48 第六章 基于最少波长转换次数的组播算法 . 49 问题定义 . 49 求最少波长转换次数 . 50 构造波长图 . 50 基于最少波长转换次数的最小成本树 . 50 求最少波长数的方法 . 51 基于最少波长转换次数进行波长和路由分配 . 52 仿真 . 52 结论 . 54 第七章 总结与展望 . 55 总结 . 55 未来的工作 . 56 参考文献 . 57 发表的学术论文情况 . 61 作者简历 . 62 致 谢 . 63 第一章 引言 第 1 页 第一章 引言 本章 介绍本论文的研究背景、一些基本概念以及本论文的研究意义和主要工作，主要 介绍一些与本论文相关的背景知识，包括 络和组播的基本概念， 及在 络中实现组播的资源限制等。 络 由于网络技术的飞速发展，多媒体技术的广泛应用，人们 对网络带宽的需求呈指数增长，最初铺设的光纤已无法满足网络发展的需要，再投资重新铺设的费用又太高，于是光纤网中的复用技术的研究受到广泛关注，并有多种复用技术被提出，其中波分复用（ 术 被认为是最具潜力的光网络中的复用技术之一，也 是现在人们普遍采用的一种复用方法。 波分复用技术最早应用在美国。它是指在一根光纤上同时传送多个不同波长的光载波。这样一来，原先在一根光纤上只能传送一个光载波的单一信道就变成了可传送不同波长光载波的多个信道，从而使 光纤的传输能力成倍增加。另外也可以利用不同波长沿不同方向传输来实现单根光纤的双向传输。 优势在于：由于能够在一根光纤上复用多个光业务流，所以 络61灵活地扩展带宽，降低复用成本。特别是在光交换机等全光器件引入后，光 光转换不再成为必须， 络的传输速度可得到进一步的提高。 络的 题 络中的通信是面向连接的通信，即通信双方在通信之前需要首先建立连接。建立连接的过程就是寻找一条路径，并为该路径的每条链路分配一个波长，使其满足全光传输的要求 。这一过程称为 络的路由与波长分配 ( 络与传统网络的主要区别之一是， 络的中间节点不能象传统网络那样缓存信息并以存储转发方式传输数据，而是以类似于线路交换的方式传输数据。因此，一旦通信请求不能立即获得可用波长，通信即告失败，这种情况称为阻塞 (为了在 络中实现有效通信，需要解决的中 国 科 学 院 研 究 生 院 硕 士 学 位 论 文 第 2 页 基本问题就是 题 61、 63。 由于光网络承载的业务需求正呈爆炸式增长，而目前光网络的可用资源（波长、光纤 等）却很有限。同时，如何在有限资源网络中为业务选择合适的路由和分配优化的波长对于网络资源的利用、管理和控制都有很大的影响。所以， 题成为 物理拓扑和逻辑拓扑 光网络中的物理拓扑是指光网络的物理节点和光纤链路互连的物理结构。光通道可以建立在物理拓扑图上，由物理路由和承载波长构成。逻辑拓扑是指在节点对间建立的所有光通道的集合。逻辑拓扑也叫虚拟拓扑，它是由光网络中的光通道和光树构成的。该方法是将每个波长作为一条虚链路，一根光纤就变成了多条链路，整个网络转换成 一个由可用波长（虚链路）组成的网络拓扑图。 组播 组播 (概念最早是 1988 年由 学的 出的。组播 是一种组通信机制，它是一 种从 源节点 (发送者 )将信息同时发送给多个目的节点 (接收者 )的通信方式。 所以，组播技术是通信网络将发起端的信息复制多份同时传递给多个接收端的一种信息传递技术，即点对多点的通信。当只有一个目标节点时，组播传送就成为单播传送。当除源节点外的所有节点都是目标节点时，组播就变成了广播。由于组播传送在某些共享链路上只需将信息发送 一次，而不必从源端对每一个目的端都发送一个信息副本，因此，与由多个点对点通信实现的点对多点通信方式相比，组播通信可以极大的节省带宽，有效地降低网络通信成本，增加网络通信能力，避免广播带来的泛洪问题。 组播在现代计算机网络中有广泛的应用，它能有效地支持那些对带宽要求较高的业务。需要组播技术支持的业务类型主要是一些带宽密集型的业务，如：视频会议、软件文件的传递和镜像站点的文件复制、虚拟现实游戏、互联网新闻信息的传播和电子邮件列表、远程教学、电子商务、视频点播、光存储网络 (0 等。 按请求的性质，可以 将组播分为静态组播和动态组播。所谓静态组播是指组播请求预先知道网络的全局状态，并且没有实时性要求，网络系统对一组请求统一调度。第一章 引言 第 3 页 与此相反，动态组播请求具有实时性，一旦到达，要求立即实现，所以也称为实时组播，通常是针对单个请求进行调度。 随着服务质量（ 念的引入，对组播传送的 量的要求也越来越高，它不仅需要将信息安全有效地传送到目的地，而且还对点到点的延迟、阻塞概率以及丢包率、传输成本等有严格的要求。在当前的通信网络中，带宽等网络资源相对于不断增长的通信需求 来说仍十分有限，如何在满足一定的 求下，用尽可能少的网络资源来完成组播传送业务是需要解决的一个现实问题。这就是带有 束的组播路由问题。 络因其较大的带宽和潜在的高速传输能力，自然被广泛应用在组播传送领域，这种应用利用了 络的高带宽和组播通信的高效率，从而有效地提高了网络的通信能力。因此， 络中的组播通信方法已成为人们关注的热点。 进行组播传送的。为了支持 播通信， 开关节点应该具有光分离能力，它能将一个输入信号分离成到不同输出链路的多个 信号。 络中的组播主要有如下几点优势： 1）在 包含了整个光拓扑结构及它的资源分布信息，在这一层，可根据每条链路的波长分配情况构造出一棵组播树。 2）光分离器的出现和使用，使得在 络中进行组播通信比电信号中的包复制更加有效。 3） 络中的组播传送不需要进行光 光的转换，这降低了点到点信息传输的延迟。 光通道 (光树 ( 络中两个常用的概念。光通道是指在网络中两个节点间的物理路径，它可以跨越多个光链路，是网络节点间的全光通信信道。光通 道的建立以可用波长为基础，按给定的规则为每条链路分配一个可用波长，中间节点直接使用光交换而不进行光电转换。该路径上的各链路被分配了相同的波长。当两条光路径同时经过同一链路时，它们必须使用不同的波长，这就是波长连续性限制。 为了支持 的组播， 人首次在波长路由网络中引入了光树的概念。光树是一条点对多点的光通路概念的归纳，它是将点到点的光连接方式中 国 科 学 院 研 究 生 院 硕 士 学 位 论 文 第 4 页 扩展为点到多点的光连接，就形成了光树。更准确地讲光树是点对多点没有环路的光通道。 在 络中组播传送一般是采用构建一棵组播树的方法 来解决。组播树(是一棵以源节点为树根，包含所有目的节点的树。在 络中进行组播传送就是要找到满足条件的树，组播树中的每条边对应一条光纤链路，并分配一个可用波长。 络中的资源限制 波长连续性限制 络系统的通信基础是光通道。在无波长转换器 ( 长路由网络中，求解 题要受下面两个条件的约束： 1）同一光纤中的不同光通道必须分配不同的波长，这是保证网络能够正常运行的限制条件。 2）波长 连续性限制：即每一个从源节点到目的节点的光通道中的所有链路上使用的波长都必须是相同的。当一条通路的中间结点没有波长转换器时，光路上连接的多条链路必须使用同一波长。 波长转换限制 尽管 络有助于带宽的扩展，但是系统的波长数目仍难以满足日益增长的通信需求。在 纤网络中，一对一的连接是由光路支持的。一条光路中的波长分配必须满足波长连续性的约束条件。这就使得当两个或多个使用相同波长的信号向相同的节点连接时造成波长竞争，即空闲的路由上没有一条端到端的空闲波长。这种情况会造成 络阻塞率的 大大提高。 在网络的一些节点上放置波长转换器，可适度放松波长连续性的限制。在网络中的一个节点放置波长转换器，则经过该节点的光通道就可通过波长转换器来改变所使用的波长，而不必遵守波长连续性的限制，这样可避免有共享链路的光通道发生阻塞。波长转换能够解决交叉连接中的波长竞争，使波长能够再分配和再利用，从而可有效地提高网络的灵活性和可扩展性，降低网络的阻塞率，同时也有利于网络的运行、管第一章 引言 第 5 页 理和控制。所以波长转换器的使用能很大程度地提高波长路由光网络的性能。 络中根据波长转换分为单跳系统 (多跳系统 (在单跳系统中一个通道的所有链路必须使用相同的波长。在多跳系统中，由于有波长转换器，所以从源到目的节点的光连接通道中可以是多个使用不同波长的光路径的组合。但由于全光转换器技术还不够成熟，目前波长转换器的价格也很昂贵，而且波长转换的使用会增加传输时延。因此在实际应用中还应根据网络业务需求权衡网络中设置的波长转换器的个数与费用。 光分离能力的限制 光分离能力是 络中组播传送的又一资源限制因素。图 1明了具有光分离能力的组播传送过程 与其它组播传送的不同之处。 图 1 (a)(b)(c)显示了从源节点 s 到两个目标节点 三种情况下建立组播传送的方法。图 (a)是在 建立源到目的节点的路由树，每个路由节点能复制数据包并把它传到它们的子节点。但这种方法需要在组播树的每个路由节点对每个数据包进行光 /电 /光（ O/E/O）的转换，从而造成一些不必要的传输和浪费。图 (b)中从源节点到每个目标节点建立一条虚拟的光通道（ 避免了 O/E/O 的转换。但是需要多条单向通道。这对带宽消耗较大，不适于大型的组播传送。图 (c)中的组 播是在实现的，它是通过光分离器在交叉连接处对数据包进行复制，然后再传到不同的目标节点。这种方法因为在公共的链路上只占用一次带宽，相比图 (b)所示的方法来说能更有效地节约带宽 11。这种 络中的组播传送方式对于象 这种对带宽要求高的服务中有很好的应用。 但是基于成本原因，在实际网络中，并不是每个开关节点都具有光分离能力，我们将具有光分离能力的节点叫 点，而不具有光分离能力的节点叫 点。因此，在实际应 用中也应该在光分离器的使s IP s s d1 1(a) IP s P s s d1 c) 2 1 IP s s d1 b) IP DM s 中