光纤通信网络中的路由与波长分配
文献类型：学位论文
| 作者 | 帅天平 |
| 学位类别 | 博士 |
| 答辩日期 | 2005 |
| 授予单位 | 中国科学院声学研究所 |
| 授予地点 | 中国科学院声学研究所 |
| 关键词 | 全光网络 单播 多播 路由 波长分配 波长转换 性能比 |
| 其他题名 | Routing and Wavelength Assignment in Optical Fiber Networks |
| 中文摘要 | 我们在本论文主要是讨论全光波分复用（WDM, Wavelength Division Mul-tinlex）网络中的一些路由（Rotlting）与波长分配（Wavelength Assignment）的优化问题．这是最近十几年来在通信网络领域人们所关注的一个热点问题，得到了广泛研究．在第一章，我们叙述了相关问题的背景和研究意义，并对己有的相关研究成果进行了综述．论文余下内容分为两大部分．第一部分包括第二、第三和第四章，主要研究单跳系统（Single-hop system）中光网络的路由与波长分配问题，此时波长分配要求满足波一长连续性约束．第二部分包括第五章和第六章，主要讨论多跳系统（Multihop System）中单个多播路由与波长分配问题：给定网络拓扑G（V,E）。中间节点配有波长转换器（Wavelength Converter），各边上可用波长集｛ω（e）|e∈E｝及一个多播通信请求，在各种优化目标下对此请求进行路由与波长分配．在第二章，我们研究了在波长不一致分布下的单播通信（Unicast，即由一个点到另一个点的通信）路由与波长分配问题：给定网络拓扑，网络的可用波长及一组单播通信请求集，选取一个通信请求子集，对该子集上的每一请求进行路由并分配一个波一民，满足任何两个具有共同边的请求所赋波长不同（即波长无冲突）．目标是所选取的子集的基数（或权重）最大．我们证明了上述问题即使对总线网络（LineNetworks，即网络的拓扑结构是一条线）也是NP-难解的．相应的，对路径给定情形，我们给出了总线网络、环网络和树网络上的近似比为告，树环网上的近似比为合和一般网络上近似比为命的多项式时间近似算法，这里d是最优解的平均路长，另外，我们还考虑了对每一个单播请求带有利润（权）和路径不定的情形．给出了相应网络的多项式时间近似算法，并分析了算法的近似性能比．在第三章，我们考虑多个多播通信（Multicast，即由一个点到多个点的通信）请求的路由与波长分配问题：给定一组多播通信请求集，要求对每一请求进行路由并分配波长，即给每一多播请求建立一棵包其含源点和目的点的子树，分配给它一个波长，满足波长连续性要求和无波长冲突，目标是使所用的波长数最少．我们证明了在二叉树上该问题是多项式可解的．我们同时也指出树上的波长分配可由星网络（StarNetworks）上的波长分配得到．但是，在星网络上的波长分配问题等价于一般图上的顶点着色，不存在近似比小于等于饥彭p（o＜ρ＜1/2）的近似算法，除非NP=ZPP，这里饥为星网络的边数．我们给出了基于向量包装（VectorPacking）的FFDofMaxilnumSum思想的近似算法，其性能比不超过（√m＋1）（logT/√(m+1)+1），这里饥和：分别是星网络的边数和请求数．另外。对线性规划松弛与约整（RelaxationandRounding）的近似算法也进行了探讨．对环上的多播路由与分配则有近似比为3.6的近似算法．最后，我们给出了树环网上波长分配的一个近似比为2△的近似算法，△为顶点最大度数．在第四章，我们考虑了允许有限个目的点下路（Drop-offs）的单个多播通信路由问题．在这种情形下，一个多播连接的路由由多个光树组成，每一光树以源点为根，包含的可下路的目的点数目是有限的，比如说：无个．我们证明了对k三2时问题是多项式时一间可解的．对凡全3的一般情形是NP-难解的，对此我们给出了一个基于Homilton圈的近似算法，其近似性能比不超过4．在第五章，我们讨论的多播路由与波长分配问题的目标是使得所用的波长数目最少为求此问题，我们推广了集合覆盖（setCover）概念，提出连通集合覆盖（ConnectedSetCover）问题，对此问题进行了研究．我们由连通集合覆盖问题来求解多播路由与波长分配问题．我们证明了对固定波长转换（FixedWavelengthConversion）模式有多项式时间的最优算法，而在有限或全波长转换（Limited＆FullWaveingthConversion）模式则有近似比为2（logn+1）的近似算法，这里几是网络的节点数．在第六章，我们研究的多播路由与波长分配问题有如下两个目标：（1），极小化源点到目的点的最大波长转换次数；（2），极小化波长转换总次数．我们证明了前者是多项式可解的．而后者显然是NP一难解的，因此我们给出了一个近似算法，它是通过把问题转化成群组Steiner树来求解．另外，我们考虑同时优化这两个目标或者要求某一目标具Qos（QualityofService，即服务质量）限制下的优化问题，我们证明，给任意定常数a＞1和（1），（2）两目标下的两棵最优多播树，可以由此出发得到一棵多播树，它的源点到目的点的最大转换次数不超过最优次数的a倍，而波一长转换总次数不超过最优波长转换总次数的1＋2/(a-1)倍. |
| 英文摘要 | In this thesis, we study a number of optimization problems concerning routing and wavelength assignment in All-optical WDM networks. We first describe backgrounds and some concepts of optical networks, and then review some results in this area related to our work. The thesis consists of two parts. The first part includes Chapters 2, 3, and 4. We focus on routing and wavelength assignment problem in single-hop system, where wavelength assignment must satisfy wavelength continue constraint. The second part includes Chapters 5 and 6. We study the routing and wavelength assignment problem for single multicast in multihop system. We are given a multicast request and need to find a multicast tree and assignment wavelength to each link to optimize some objectives. In Chapter 2, we consider the unicast routing and wavelength assignment problem under nonuniform wavelength distribution in optical networks. We show that the problem is NP-hard even for line networks. We then propose 1/2-approximation algorithms for line, ring, and tree networks, 1/5-approximation algorithm for trees of rings, a 1/d+1-approximation algorithm for general networks with pre-specified routes, where d is an average length of paths in optimal solution. We also study the case where the route of each request is not pre-specified. At last, the case for each request associated with a profit is considered. In Chapter 3, we consider the multiple multicast routing and wavelength assignment problem for minimizing the total number of wavelengths used. We prove that the problem can be solved in polynomial time when the network topology is a binary tree. We also show that there does not exist a TO3~P-approximation algorithm for any given o < ρ < 1/2 unless NP=ZPP, where m is the number of edges in the star network. We then propose a （√m＋1）（logT/√(m+1)+1） -approximation algorithms for star network based on FFD of Maximum Sum algorithm for vector packing and an algorithm based on LP relaxation and rounding technique, respectively, where r is the number of requests. In the end, we propose a 3.6-approximation algorithm for ring network and 2A-approximation algorithm for wavelength assignment in trees of rings, where A is a maximum degree of trees of rings . In Chapter 4, we consider the multicast routing and wavelength assignment in optical networks with limited Drop-offs. In this case, the route of a multicast connection consists of a set of light-trees, each of them is rooted at the source node and contains no more than a limited number, say k, destination nodes due to the power loss of dropping optical signal off at destination nodes. We first prove that this problem can be solved in polynomial time for k = 2 and NP-hard for k > 3. We then propose a 4-approximation algorithm for the problem for k>3. In Chapter 5, we study multicast routing and wavelength assignment problem for minimizing the total number of wavelengths used. To solved it, we introduce a connected set cover problem. We transform our problem into a connected set cover problem and show that for fixed wavelength conversion, the problem is polynomial solvable. For limited and full wavelength conversions, a 2 + 2 log n-approximation algorithm was proposed for general network, where n is the number of nodes in the networks. In Chapter 6, we study the problem similar to Chapter 4 with different objectives. We are given a multicast request and need to find a multicast tree and assignment wavelength to each link such that: (1) the maximum wavelength conversion between source and each destination nodes is minimized, and (2) the total number of wavelength conversions needed is minimized. We propose an optimal algorithm based on shortest path algorithm for objective (1) and an approximation algorithm based on group Steiner tree algorithm for objective (2). We then propose an algorithm for given two optimal multicast tree for above two objective to find a multicast tree that approximately satisfies two objectives simultaneously. |
| 语种 | 中文 |
| 公开日期 | 2011-05-07 |
| 页码 | 86 |
| 源URL | [http://159.226.59.140/handle/311008/884]  |
| 专题 | 声学研究所_声学所博硕士学位论文_1981-2009博硕士学位论文 |
| 推荐引用方式 GB/T 7714 | 帅天平. 光纤通信网络中的路由与波长分配[D]. 中国科学院声学研究所. 中国科学院声学研究所. 2005. |
入库方式： OAI收割
来源：声学研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。