（信号与信息处理专业论文）wdm网中的路由和波长分配算法.pdf

声明尸明 本人郑重声明：此处所提交的硕士学位论文w d m 网中的路由和波长分配算 法，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研究工作和取得 的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 学位论文作者签名： 匡i 叁! 臣日期： 夕d j 一 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校可允许学位论文被查阅或借阅；学校可以学术交流为 目的复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播学 位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：匿遁谚卜 导师签名：序宦晦 e l期：型 华北电力大学硕士学位论文 摘要 随着全球i n t e r n e t 业务呈现出爆炸式增长的趋势，基于波分复用的w d m 光网络 技术已成为下一代骨干网络的首选技术。关于选路和波长分配的r w a 问题是w d m 光传送网中的一个重要问题。本文在综合了国内外大量文献基础上，提出了一种新 的多目标的优化算法m p o a 算法。该算法分析网络中各个链路的具体情况，综合 路由上可用波长总数、跳数信息，优化动态业务下的网络资源的配置。接着本文对 m o p a 算法进行了改进，提出了新的动态路由算法g m o a 算法，计算机仿真表明 两种算法都具有良好的阻塞率性能。最后本文给出了两种关于w d m 网中部分节点 具有波长转换能力的算法，并对它们进行了仿真和比较分析。 关键词：全光网，波长路由，动态路由算法，波长变换，阻塞率 a b s t r a c t w i t ht h ee x p l o s i v ei n c r e a s ei ni n t e r n e tt r a f f i c ，t h e r ei sa ne x p l o s i v eg r o w t ht r e n do f i n t e r n e tt r a f f i c ，t h ee m e r g e n c eo fh i g hp e r f o r m a n c eo p t i c a ln e t w o r kd e v i c e sm a k e w a v e l e n g t hd i v i s i o nm u l t i p l e x i n g ( w d m ) t e c h n o l o g yb e c o m e st h ec o r et e c h n o l o g yo f n e x tg e n e r a t i o nb a c k b o n en e t w o r k s r w ai sa ni m p o r t a n ti s s u ei nw d mn e t w o r k s b a s e do nm a n ya r t i c l e s ，an e wd y n a m i ca l g o r i t h mb a s e do nt h el a y e r e dg r a p hm o d e lc a l l e d m u l t i o b j e c to p t i m a la l g o r i t h m ( m p o a ) i sp r o p o s e d ad i s t i n g u i s h e df e a t u r eo fm o a a l g o r i t h mi st h a ti te m p l o y sm o r ea c c u r a t en e t w o r ki n f o r m a t i o nt h a nt h ee x i s t i n ga l g o r i t h m s o nt h ea v a i l a b i l i t yo fb o t ht h en u m b e ro fa v a i l a b l ew a v e l e n g t h sa n dt h eh o p so ft h el i g h t - p a t h i nd e c i d i n gt h er o u t i n ga n dt h ew a v e l e n g t ha s s i g n m e n t t h ed e t a i l e di n f o r m a t i o np e rl i n ki s a n a l y z e da n dt h ea l l o c a t i o no fn e t w o r kr e s o u r c e si so p t i m i z e du n d e rd y n a m i cs e r v i c et r a f f i c t h e nt h i sp a p e rp r o p o s e sam o d i f i e da l g o r i t h m ( g m o a ) b a s e do nt h em p o a a l g o r i t h m s i m u l a t i o nr e s u l t ss h o wt h a tt h et w oa l g o r i t h m sp e r f o r mb e t t e rt h a no t h e rp r o p o s e d a l g o r i t h m s a tl a s tt w od i f f e r e n ta l g o r i t h m sw i t hp a r t i a lw a v e l e n g t hc o n v e r s i o na r ei n t r o d u c e d a n dt h e i rp e r f o r m a n c ei sa l s oa n a l y z e d w a n gb o t a o ( s i g n a la n di n f o r m a t i o np r o c e s s i n g ) d i r e c t e db y p r o f t a n gl i a n g r u i k e yw o r d s ：a l l - o p t i c a ln e t w o r k s ，w a v e l e n g t hr o u t i n gn e t w o r k ，d y n a m i c r o u t i n ga l g o r i t h m ，w a v e l e n g t hc o n v e r s i o n ，b l o c k i n gp r o b a b i l i t y 0 3 ： 专 学位论文 第二章w d h 光网络中的路由与波长分配算法 2 1w d m 波长路由网络5 2 2 路由与波长分配算法概述6 2 3 静态r w a 问题7 2 4 动态r w a 问题8 2 5 图论及算法仿真介绍1 0 2 5 1 图论相关知识1 0 2 5 2 网络拓扑模型1 3 2 5 3r w a 算法的仿真1 4 2 6 小结1 6 第三章一种新的动态路由算法” 3 1 引言17 3 2 相关算法17 3 3 多目标优化算法( m p o a ) 2 1 3 3 1 分层图模型2 1 3 3 2 算法数学描述2 2 3 3 3 算法复杂度分析2 3 3 3 4 算法仿真及结果分析2 3 ： 4 小结2 5 第四章改进的动态路由算法2 6 4 1 引。言2 6 4 2g m o a 算法2 6 4 2 1 算法描述2 6 4 2 2 算法复杂度分析2 7 4 2 3 算法仿真及结果分析2 7 4 3m p o a 与g m o a 算法的比较2 9 i i l 1 2 4 5 华北电力大学硕士学位论文 4 4 小结3 1 第五章两种部分波长可变的动态路由算法3 2 5 1 引言3 2 5 2 算法描述3 4 5 2 1l g w c 算法的数学描述3 4 5 2 2v - r w a 算法的数学描述3 5 5 3 算法仿真结果3 6 5 4 小结3 8 第六章总结3 9 参考文献4 0 致谢4 4 在学期间发表论文和参加科研情况4 5 光导纤维以及 1 9 7 0 年康宁公司成功制造第一根2 0 d b k m 的光纤预示着光纤通信时代的到来。光纤 有着巨大的频带资源和优异的传输特性，是实现高速率、大容量传输的最理想物理 媒质1 1 】。传统的s o n e t s d h 技术需要电的时分复用( t o m ，t i m ed i v i s i o n m u l t i p l e x i n g ) ，这些都对电子器件的速率要求很高，而电领域的处理速度由于受量 子理论的限制，提高的速度有限，目前认为4 0 g b s 是单个波长最高实用化的速率， 这些都使传统的s o n e t s d h 技术越来越不能适应高速数据网络发展的要求。近几年 来，密集波分复用技术的发展提供了利用光纤带宽的有效途径，使点到点的光纤大 容量传输技术取得了突出进展。w d m 技术由于能充分利用光纤的巨大带宽，正在 成为骨干长途网中最具吸引力的技术【2 3 】。技术对网络的升级扩容、发展宽带新业务、 充分挖掘和利用光纤带宽能力，特别是在现有光纤用完而铺设十分困难的情况下实 现超高速通信具有十分重要的意义。而光交叉连接( o x c ，o p t i c a lc r o s s c o n n e c t e d ) 技术和光分插复用( o a d m ，o p t i c a la d d d r o pm u l t i p l e x i n g ) 技术引入使得w d m 网络 成为具有高度灵活性和生存性的光网络【4 】。 全光网是新一代网络，是在光域上进行传输和交换的下一代的新型网络。全光 网的传输方式是全光方式，取消光电光转换，在网络节点和交换上实现全光路由 和交换。但鉴于光信号处理困难，在光交换、光存储等技术尚未取得突破性进展自玎 还难于实现基于i p 分组的全光交换，目前还不能做到实用化的、完全的全光网。从 现有的光纤通信网演进到伞光网，将有一个发展过程。全光网的发展过程是在点到 点的w d m 光纤系统皋础上，从采用光分插复用器和光交又连接光节点的w d m 光传 送网，发展到存光域【：传输和交换的全光分组交换刚。 波分复川技术，特刖址街集波分复川( d w d m ) 技术，i 叮以允分挖拥 光纤的fi 大带 宽资源，使一根光纤的传输容量比单波长传输增加几倍至几十倍。目自订商用化的为每 光纤3 2 个波长，最高达到1 6 0 个波长，实验室已达到1 0 0 0 个波长。近些年来，商用 的d w d m 系统传输容量已达4 0 0 g b i g s ，而1 0 t b i t s 的总容量也已突破，c i e n a 公司 已经研发1 6 t b i t s 的系统，朗讯贝尔实验室的科研人员认为商用的d w d m 系统容量 最高将达到1 0 0 t b i t s 。截止至u 2 0 0 7 年，商用最高光纤传输容量为1 6 t b i t s ，使用波段 也从c 波段到l 波段，甚至s 波段。我国多个运营商的网络应用的是朗讯以及北电网 络提供的采用1 6 0 xl o g b i t s 方案的产品。以1 0 g b i t s 为基础的d w d m 系统已逐渐成为 华北电力人学硕士学位论文 核心网的主流。d w d m 系统除了波长数和传输容量不断增加外，光传输距离也从 6 0 0 k m 左右大幅度扩展至i u 2 0 0 0 k m 以上。1 2 8 t b i t s ( 1 2 8 x 1 0 g b i t s ) 的d w d m 系统已达 到无中继传输8 0 0 0 km ；实验室最高记录已达4 0 g b i v s 无电再生传1 0 0 0 0 k m 5 s 】。 w d m 技术的主要特点有：可以利用光纤的巨大带宽资源，使一根光纤的传输 容量比单波长传输增加几倍至几十倍。w d m 技术可充分利用单模光纤的巨大带宽 ( 约2 5 t h z ，相当2 5 0 0 0 g s ) ，如此大的带宽，可以说完全解决我们的网络带宽问 题；适应各种信号。由于同一光纤中传输的信号波长彼此独立，因而可以传输特性 完全不同的信号，完成各种电信业务信号的综合和分离，包括数字信号和模拟信号， 以及p d h 信号和s d h 信号的综合与分离；透明传输。波分复用通道对数据格式是透 明的，即与信号速率及电调制方式无关。一个w d m 系统可以承载多种格式的“业务” 信号，a t m 、i p 或者将来有可能出现的信号。w d m 系统完成的是透明传输，对于“业 务”层信号来说，w d m 的每个波长就像“虚拟”的光纤一样；扩容方便。在网络扩充 和发展中，w d m 是理想的扩容手段，对于早期的芯数不多的光纤系统，利用此技 术，不必做较大改动，就可以轻松扩容。w d m 也是引入宽带新业务( 例如c a t v 、 h d t v 和b i s d n 等) 的方便手段，增加一个附加波长即可引入任意想要的新业务或 新容量；网络生存性好。利用w d m 技术选路来实现网络交换和恢复，从而可能实 现未来透明的、具有高度生存性的光网络；节省成本。在国家骨干网的传输时，e d f a 的应用可以大大减少长途干线系统s d h 中继器的数目，从而减少成本。距离越长， 节省成本就越多 9 , 1 0 】。 从发展趋势看，形成一个以w d m 技术及光交换技术为基础的光网络层，建立 纯粹的w d m 光网，接入i p 等多种业务信号己成为光通信发展的必然趋势，它完全符 合传送网的分层化，并简化了网络结构，提高了网络的可靠性，并且与业务和承载 信号无关，特别是自动交换光网络( a s o n ) t i2 】技术的成熟更是赋予了w d m 光网络 优异的性能，具用重要的现实和长远意义，已成为新世纪引人瞩目的新一代传送网。 1 2 国内外研究现状 w d m 光传送m 络足个全新的技术，它涉及的领域：作常广泛。| f 丽人们时 w d m 光传送网络的研究正在兴起，并且形成了几大研究热点。 首先，w d m 光传送网中选路及波长分配( r o u t i n ga n da s s i g n m e n to f w a v e l e n g t h r w a ) i h 题【1 3 】。其指的是给定一组节点间的全光连接( 光路呼叫) 请求：( 1 ) 寻找从源 节点到目的节点的路由；( 2 ) 在这些路由上分配波长。路由和波长分配问题是一个 n p c 问题【l4 1 。网络所支持的业务一般可分为两类，一是静态业务：业务分布长时间 保持不变。呈现出均匀性和对称性。二是动态业务：业务的分布随时发生变化。往 往呈现出不均匀性和非对称性。按照所支持的业务类型划分，路由和波长分配问题 2 华北电力大学硕士学位论文 可分为静态的路由和波长分配( 简称静态r w a ) 和动态的路由和波长分配( 简称动态 r w a ) 问题【 屯。 静态r w a 问题是相对于静态业务量而言的。静态业务流量是指所有节点对之 间的连接请求是预先给定且不随时间变化的，即源节点和目的节点的连接关系是给 定不变的。当所有连接建立好后，连接将保持不变。此时网络不会建立新的连接， 也不会拆除已建好的连接。解决静态r w a 问题时，要研究的是如何利用有限的波 长建立尽可能多的光通道，所得到的是逻辑拓扑( l o g i c a lt o p o l o g y ) ，又常称为虚 拓手b ( v i r t u a lt o p o l o g y ) 一】。它以网络物理拓扑的节点为节点，由光路实现的虚链路 连接而成。所以可以说静态的r w a 算法为逻辑拓扑的生成架构了一个理论基础。 动态r w a 问题是相对于动态业务量而言的。动态业务流量是指节点对之间的连接 请求不是预先给定的，而是随着时间变化动态到来的，当连接建立好并保持一段时 间后又会被拆除。是指支持动态业务的路由和波长分配，也就是对于一组随机到达 的光连接请求选择路由并分配波长，且在通信结束时拆除光通道，相应的性能指标 通常是光路连接请求的阻塞率，动态r w a 要为每一条光通路建立请求做实时的 r w a 计算。好的选路算法会显著地减小阻塞率，而各种波长分配算法的性能差别 不大，同时采用较好选路算法的分层图法比将选路和波长分配割裂的方法的阻塞率 要小。选路可分为三类：固定路由、备用路由和自适应路由。分配波长有多种方法，。： 如随机波长分配算法( r 算法) 、首先适合算法( f f 算法) 、最大总数算法( m a x s u m ) 等。综上所述，当前常用解决r w a 问题的方法是把r w a 强行拆成两个独立的子问 题，路由子问题和波长分配子问题，分别加以解决。但是，这样却忽略了路由选择 和波长分配之问的关联性，对大型网络的解的最优性缺乏保证，且基于线性规划【1 3 】 之类的传统优化算法虽能保证找到全局最优解，但因其时间复杂度高很难运用于实 际大型网络。 其次，波长通道、虚波长通道与部分虚波长通道问题。波长通路( w p ，w a v e l e n g t h p a t h ) ，到端的通信需要使用同一条空闲波长建立连接，但是它带来了波长连续性的 限制，降低了波k 的- i j 重用性。随着技术的发展，光网络中引人了波长转换器，克 服了波k 连续。陀的限：叭建j 口了虚波长通路( v w p ，v i r t u a lw a v e l e n g t hp a t h l ，从而 允分地利用了波k 资源，降低了网络的f 5 j i 塞率。这种办案的缺点足波k 转换器价格 昂贵。所以考虑部分波长变换的r w a 算法已经成为一个令人关注的热点。 最后，w d m 光传送网的q o s 问题、w d m 网与现有网络技术( a t m ，i p 等) 的 结合以及网络自愈生存技术的研究也都也越来越受到关注。w d m 网正朝着融入更 多业务、能进行灵活的资源配置和生存性更强的方向发展【2 1 1 。 华北电力大学硕十学位论文 1 3 本文主要工作和内容安排 本文主要研究了w d m 光网络中的路由问题。通过对经典的路由算法进行研究， 提出了综合考虑光通道容量及路由跳数的动态路由算法一多目标优化算法m p o a ， 以及在此算法基础上改进的算法g m o a 。文中还给出了一种考虑部分波长变换的备 用路由算法。本文内容安排如下： 第一章介绍了w d m 光网络产生的背景、发展及其波长路由结构和r w a 问题 的研究现状。 第二章首先就静态r w a 和动态r w a 问题，对路由和波长分配算法进行了综述， 然后简单介绍了图论基础知识及r w a 算法仿真的计算机实现方法。 第三章综合考虑光通道容量和路由跳数两个因素通过进行优化，提出了一种综 合考虑这两个因素的动态路由算法m p o a 。文中深入研究了网络光纤数、可用波 长数和网络负载对算法性能的影响。计算机仿真结果表明，与传统的路由算法相比， 算法能有效降低网络的阻塞率，优化网络资源配置，提高网络的性能。 第四章提出了另一种改进m p o a 的动态路由算法一g m o a 。两种算法相比，在 相同网络资源的情况下，g m o a 算法比m p o a 就有更好的性能。 第五章给出了几种在w d m 光网络中考虑部分波长变换的路由算法，对这几种 算法进行了分析与比较。计算机仿真结果表明，具有波长变换动态算法增强了网络 的抗毁性，能充分利用有限网络资源，降低阻塞率。 第六章对全文工作进行总结并对今后的研究工作做出了展望。 4 华北电力大学硕士学位论文 第二章w d m 光网络中的路由与波长分配算法 2 1w d m 波长路由网络 波长路由网络( w a v e l e n g t hr o u t e do p t i c a ln e t w o r k s ，w r o n s ) t 2 2 , 2 3 】是由波长路由 节点和一系列点到点的光纤连接而组成的。它是通过光通道( 1 i g h t p a t h ) 来实现通信 的，光通道就是网络节点之间的全光通信信道，可以跨越多个光链路。它的节点具 有路由功能。每个节点能够按照网络中的端到端的连接进行选择性的输出，而不是 将信息发往所有的输出端，因此可以节省大量的网络终端设备，可以大大提高网络 的数据吞吐能力、简化网路管理和减少电层的网络设备。并可以在空间上重新利用 波长。波长路由网能接受连接请求，按需建立连接，具有较高的波长利用率，主要 用于长距离、大范围的广域骨干网中。波长路由节点中最重要的器件就是光交叉连 接器( o p t i c a lw a v e l e n g t hc r o s s c o n n e c t i o n ，o x c ) ，光交叉连接器的输入输出端口分 为中继栈( t r u c k ) 端口和本地( 1 0 c a l ) 端口，中继栈端口通过光纤与其它波长路由节点相 连，本地端口则用于本地业务的上下路。所有业务的起点和终点都在本地端口。当 光交叉连接器只含两个中继端口时，相应的节点被称为光分差复用器( o p t i c a la d d d r o pm u l t i p l e x ，o a d m ) 。o a d m 可以看成o x c 结构的功能简化。光交叉连接器由波 长复用器，解复用器，交换矩阵组成，还有可能包含波长转换器。 根据光路中经过的节点是否具有波长变换能力，光路可以分成两类：波长路径 ( w a v e l e n g t hp a t h ，w p ) 和虚波长路径( v i r t u a lw a v e l e n g t hp a t h ，v w p ) 2 4 2 6 1 。对于w p ， 网络节点不具备波长变换( w a v e l e n g t hc o n v e r s i o n ) f l 邑力，网络通过在光路所经过的所 有链路上分配相同的波长为用户提供光连接，即一条光通道从输入端口到输出端口 上的波长应该相同，即必须遵循波长连续性限制( w a v e l e n g t h c o n t i n u i t yc o n s t r a i n t ) 原 则。相反，v w p 则要灵活得多，v w p 的路由肖点卜配置波长转换器( w a v e l e n g t h c o n v e r t e r ) ，因此町以在一个端剑端的连接所经过的各个链路段上分配不同的波长， 从而使得v w p 连接的：，路和波k 分眦l 叮以按j ( 饵段链路，逐段考虑。v w p 连接_ i 需 要和w p 连接那样在全网范幽内考虑波长分配问题，这样v w p 连接的波长利用率比 w p 高。如图2 1 所示【z 7 1 ，对于w p ，由a 至i j b 的通路：a 。1 2 3 4 b ；如果节点具有波 长转换功能，则不必满足这一限制，如图2 1 所示的由d 至i j c 的通路：d 65c 。其中， a 、b 、c 、d 代表业务接入站( 包括收发机) ，1 6 表示波长路由交换机( 可能包含波长 转换器) 。 5 华北电力大学硕士学位论文 图2 1由o x c 节点和光链路组成的网络拓扑 显然，波长转换器在提高网络性能方面起着十分重要的作用。但是在目前的技 术水平条件下，波长转换器还是一种比较昂贵的器件，不太可能全网所有节点均配 备为w c ，所以有必要也对介于二者之间的情况，即网络中只有部分节点为波长转 换器的情况进行分析，以找到网络造价和性能之间的最佳平衡点。 此外，从w d m 光网络的选路方式上看有两种典型的网络结构；广播与选择网 ( b r o a d c a s ta n ds e l e c tn e t w o r k ) 和波长选路网( w a v e l e n g t hr o u t e dn e t w o r k ) 。从承载的 业务角度看，w d m 网络可分为静态业务网络和动态业务网络，静态业务网络类似 与永久式虚电路( p v c ) ，两个节点问的路由及分配的波长都是固定的，而动态业务 网络则像半永久式虚电路( s p v c ) 或交换式虚电路【2 8 2 9 1 。 2 2 路由与波长分配算法概述 w d m 光网络是由网络节点和连接节点的光纤链路构成的，不同波长的光信道 复用在同一+ 根光纤中传输。光网络的节点能交叉连接输入和输出的光信道，具有动 态鼋构光网络的特性。当客户层业务到达时，w d m 光网络需要给每条、务分配路 由和选择波长，建：征光通道传送业务。我们称为客户层到达的业务选择路【j 和分配 波k 的j 、u j 题为路波k 分配( r o u t i n ga n dw a v e l e n g t ha s s i g n m e n t ) | u j 题，简称 r w a 。虽然w d m 光网络己经取得了巨大的进步，但由于各种物理的、技术的限制 因素，使得光网络还不能提供我们所要求的物理性能，因此就存在对现有可用资源 的高效利用和优化问题。r w a 问题是最优化网络性能的核心问题之一。然而，r w a 问题又是一类n p 完备性问题( n o n d e t e r m i n i s t i cp o l y n o m i a l c o m p l e t e ) 。n p 完备性问 题是非特定多项式( n p ) i h 题中的一类，具有下述性质：1 ) 这类问题中任何一个问题 至今未找到多项式时间算法；2 ) 如果这类问题中存在一个问题有多项式时间算法， 那么这类问题就有多项式时间的算法。根据n p 完备性问题的性质可知，无法找到 6 华北电力大学硕士学位论文 关于任意复杂度r w a 问题的时间算法。由于计算资源有限，只能对规模有限的网 络优化给出r w a 问题的解答。对大型网络，求其完全解将非常耗时，通常将r w a 问题强行分为路由子问题和波长分配子问题，在实际的算法研究中可以分解成两步 骤： 第一：按照某种优化目标，寻找从源节点到目的节点的路由； 第二：在满足一定优化性能的情况下为这些路由分配波长； 有时上述两个过程要反复进行，直到得到最优的网络配置。 对于路由子问题，处理的基本原则是选取最短路由，主要有两种策略，固定路 由选路策略( f i x e dr o u t i n g ) 以备用路由选路策略( a l t e r n a t er o u t i n g ) 1 1 , 1 3 , 3 0 - 3 3 l 。固定 路由策略是指，选路是在网络业务请求到达前完成的，网络拓扑给定后，按照标准 最短路径算法( 如d j i k s t r a 或f l o y d 算法) 为每个节点对分配一条固定的光通道。网络 运行中，节点对间的通信连接总是建立在预定好的路由上。这种方法简单、速度快， 但却无法随网络业务的动态变换自适应调节节点对间的路由，因此会导致网络性能 的劣化，阻塞率较高，而且在该算法下网络不具备链路故障恢复能力。备用路由策 略指的是，为每个节点对预先确定多条备用路由，并按一定的优先级顺序排列。排 在最前面的称为主路由，其它的视为备用路由。当业务到达时，安排列顺序依次分 配给业务，当业务阻塞时，选择次优路由。与固定路由方案相比，备用路由策略使一 网络的阻塞率大大降低，并且使网络具有故障恢复能力，但其时间复杂度也有所提 高。 研究r w a 问题时，通常将网络支持的业务分为两类：( 1 ) 静态业务，给定一组 光路请求，需要为这些请求寻找路由并在其路由上分配波长，以使某些性能指标达 到最优( 如全网的吞吐量最大，所需波长数和光纤数最小等) ；( 2 ) 动态业务，光路请 求随机到达和离丌网络，相应的性能指标通常是光路的阻塞率。按照所支持的业务 类型划分，r w a 问题町分为静态r w a 和动念r w a 问题。下面分别给出解决静态 和动态r w a 问题的常用方法。 2 3 静态r w a 问题 静态r w a 是指在尽可能少占用波长和光纤等网络资源的情况下，为已知的光 路建立请求选取路由和分配波长。静态r w a 算法通常用于网络运营初期，可以离 线进行，因此对计算时间要求不是很高，而计算结果的优化程度是其目标。对于静 态r w a 问题，可以将其分解成路由子问题和波长分配子问题来考虑，也可以用线 性规划或者分层图模型将路由和波长分配作为整体来处理。下面简要介绍这些方 法。 7 华北电力大学硕十学位论文 ( 1 ) 分层图模型【3 4 3 6 】 分层图中每一层对应一个波长，称为一个波长平面，此时相应的r w a 问题简 化为在分层图中寻找从源节点到目的节点的最小代价通路问题。分层图是针对r w a 问题提出的新的数学模型，资源优化效果好，但在解决大型问题时耗费的时间长。 ( 2 ) 图的着色法【1 9 , 3 7 1 这种算法也是将路由和波长分配拆分成两个子问题考虑，其中路由子问题可以 采用固定路由或备用路由加以解决。波长分配问题则采用着色图法：将光通道映射成 着色图上的顶点，有共享链路的光通道之间用无向弧连接。通过对着色图上的相连 顶点着色，完成路由的选择与波长的分配。着色的要求是相连的顶点不使用相同颜 色，意义为经过同一链路的光通道需要分配不同的波长，着色的目标是所用的颜色 数目最少，意义为网络所使用的波长数最少。这种算法优化性能较好，但是时间复 杂度较高。 ( 3 ) 线性规划 将静态r w a 问题归结为一类线性规划问题，建立以最小化波长或光纤数为目 标的l p 模型，求解l p 方程实现网络的优化目标。该模型属于一个n p c 问题，对 于较小规模的网络可以直接采用，对于较大规模的网络则不太适合。另外，其优化 目标比较固定，且灵活性较差。 2 4 动态r w a 问题 动态r w a 是指在实时业务条件下的路由选择与波长分配问题。此时光路连接 请求是随机到达的，并且已建立的连接在维持一段时问后会被释放，因此动态r w a 算法要求具有实时性，且一般以业务的阻塞率作为其优化目标。现有的理论分析都 将呼叫到达过程假定为泊松过程。下面对无波长变换的动念r w a 问题，给出其在 固定路由和备用路山策略下的常见波长分配的启发式算法，并简要分析各其性能。 假设网络中共有条链路，链路，上二有m ，根光纤，每根光纤支持个波长。 l ( p ) 代表通路p 上所有链路的集合，l ，( ，五) 代表链路，在波长五上的剩余信道数， 受波k 连续性限：制，任意通路p 在波k 兄，i ：的i ，j j j 信道数尸 ( p ，五) = m i n ( ，五) ， 如果丘( ，五) = p c ( p ，五) ，则称，为通路p 的瓶颈链路。p + 为新到达的业务请求对应的 路由，a ( p + l 代表通路p 上的可用波长集，g p + l 代表与p + 有共享链路，且仍具有 可用信道的通路的集合。d ( a ，b ) 为指示函数，当a = b 时，取值为l ，否则取o ；u ( 口) 为单位阶跃函数，当a 0 时取值为1 ，否则取o 。 ( 1 ) 随机波长分配( r a n d o m ，r ) t 1 9 , 3 8 , 3 9 】 首先遍历所有波长，确定在选定路由上的可用波长集合，再从中随机选取一个 分配给光通道。这种算法不必考虑当前网络资源的占用情况，所以时间复杂度低， 8 华北电力人学硕士学位论文 为o ( w 1 ，但对于网络性能的改善不明显。 ( 2 ) 首次命中( f i r s t f i t ，f f ) 【”j 将所有波长按某种规则统一编号，在可用波长集中搜索编号最小的波长来建立 光路。与随机波长分配算法相比，f f 不必搜索全部波长，而是找到可用波长就停 止，计算量更小，且算法的阻塞性能要好于随机分配。其时间复杂度为d f 1 。 ( 3 ) 最小使用( l e a s t u s e d ，l u ) d 2 1 该算法根据网络目前状态统计出各波长的使用情况，选择使用率最低的可用波 长。这种算法的出发点是平衡所有波长的负载，将网络流量均匀分摊到各个波长上， 需要利用网络资源的占用情况。假设所有链路上光纤数的上界为f ，则其时间复杂 度为o ( w z , f 1 ，高于r 和f f 。 ( 4 ) 最大使用( m o s t u s e d ，m u ) 3 2 】 这种算法与l u 正相反，优先选取使用率最高的可用波长，其时间复杂度同l u 一样，为o ( w l f ) 。实践证明该算法的效率明显优于前3 种算法，它有助于将网络 负载集中在少数波长上，这样可以减少网络的波长需求。 ( 5 ) 最小乘积( m i n p r o d u c t ，m p ) 【4 0 】 该算法主要是针对多纤网设计的，在单纤网中相当于f f 算法。它根据网络当 前状态，计算出业务选定路由上各链路的各波长已被占用的信道数的乘积，选取具 有最小乘积的可用波长建立光路。按照式( 2 1 ) 选取的波长来建立通路p 。最小乘 积算法使得波长信道在光纤中更加集中，从而降低每段链路的光纤数。假设网络中 所有路由的链路数的上界为k ，则该算法的时间复杂度为o ( k w l 。 m p = 魄、兀( m t ( z ，五) ) ( 2 - 1 ) 。e l ( d ) ( 6 ) 最小负载( l e a s t l o a d ，l l ) t ”j 该算法也是针对多纤网而设计的，在单纤网中相当于f f 算法。在算法中，首 先确定选定路由上负载最重的链路，即瓶颈链路，接着计算所有可用波长在该链路 卜的空闲信道数，选取具有最大剩余信道数的波长。其优化目标可以表示为： 2 嬲勰m i nl ,(，)(2-2) ( 7 ) 最大和法( m a x s u m ，m ) 1 4 1 4 2 1 基本思想是对于一个光路连接请求，除待分配的连接本身外，计算对该连接分 配某波长后网络其它通路所剩余的可用信道数的总和，取其中最大值对应的波长来 建立连接。该算法的目标是保证分配该波长后全网所有通路的可用信道数最大。具 体计算时，在给定路由p 上对所有的可用波长，依次计算将某波长分配给该连接后， 网络中其它所有与该连接有共享链路的通道在该波长上减少的可用信道数的总和， 选取总和最小的波长建立连接。即计算将波长分配给连接后，满足式( 2 3 ) 的波长。 9 华北电力大学硕士学位论文 f、l 肛飘e g ( p ) u l t e l ( 勘。( 咖) m 川j ( 8 ) 相对容量损失( r e l a t i v ec a p a c i t yl o s s ，r c l ) 4 3 】 该算法基于m ，m y 致力于将绝对空闲容量最大化，而r c l 则致力于将相对 空闲容量最大化。具体为对所有的波长，依次计算为该通路分配该波长后，其它各 通道上减少的可用信道数与其相应的可用信道总数的比值，累加此比值，从中选取 比值最小的波长。该算法公式表示如下： r、 u l d ( 厶( ，) ，( p ，) ) l r c l = 新，磊) 上型b 一 ( 2 - 4 ) j e a ( p + ) 而r c l 算法不仅考虑到了各相关业务( 即与新光路有共享链路的通路) 上减少的总 信道数这一绝对值，而且基于各相关业务之间的情况也是不同的，r c l 用相对值来 描述新光路的建立对全网状态的影响，较m e 的描述更加精确，且在性能上也优于 m 。 ( 9 ) 最小影响( l e a s ti n f l u e n c e ，l i ) 4 4 , 4 5 】 任意光路p 在波长国上的可用信道数( p ，a ) ) = m i n l c ( 1 ，彩) ，( ，p ) 。如果 t ( ，( - 0 ) = 只( p ，缈) ，则称链路，为p 在国上的瓶颈链路。g ( p ) 表示p 的“邻域”即与p 有共享链路，并且可用信道总数不小于，的光路集合，该集合中的光路称为p 的相 关光路。l i 算法选择波长的目标是对全网其它相关光路建立请求造成的瓶颈总和最 小( 即对其他通路的影响最小) 。 此外，还有用于保护较长光通道波长预留( r s v ) 和保护门限( t h r ) 【3 8 】算法：这 两种算法改善了单跳和多跳光路在阻塞率方面的差异，即保护较长的光通道，提高 了网络的公平性。还有一些新的算法被提出，例如相对最小影响法( r e l a t i v el e a s t i n f l u e n c e ，r l i ) 等【4 5 1 。综上，算法依据的信息越多，其性能就越好，但性能的改善 是以存储量和处理时i 日l 的增加为代价的。 2 5 图论及算法仿真介绍 2 5 1 图论相关知识 通信网络的拓扑结构可以用图论学的相关知识来描述。一个图由两部分组成： 一部分是节点，图的术语中也称之为顶点； 常，图的任意一对顶点间都允许有一条边。 上说，图是最基本的数据结构。 l o 另一部分是顶点的偶对，称之为边。通 树和链表也可看作受限图，从某种意义 华北电力大学硕七学位论文 图可用g ( v ，e ) 来表示，每个图都包括一个顶点集合v ( g = v l ，v 2 , - - , 聊 ) 和一个 边集合e ( e = e l ，p 2 ，e r a ) ，其中e 中每条边都是v 中某一对顶点的连接。顶点总 数记为川，边的总数记为例。边数较少的图称为稀疏图，边数较多的图称为密集 图。 如果图中的边限定为一个顶点指向另一个顶点，则此图称为有向图。如果图中 的边没有方向性，则称之为无向图。光网络中由于每条链路都可在其连接的两个节 点间的任一方向进行通信，因此，代表它的图应是无向图。 如果图中各顶点均带有标号，则称之为标号图。通过某条边连接的两个顶点是 相邻的，称它们为邻接点。连接一对邻接点u 、v 的边被称为与顶点u 、v 相关联的 边，记作( u ，v ) 。每条边都可能附有权值。边上标有权值的图称为带权图。由于光 传输系统的高速性，物理链路的长度可以使用链路通过的节点跳数( h o p s ) 直接表示。 如果从顶点m 到顶点m + ( f 七) 的边均存在，则称顶点序列( 1 ，+ i ，咋) 构成 一条长度为k j l 的路径。如果路径上各顶点均不同，则称此路径为简单路径。路 径长度是指路径包含的边的数目。如果一条路径将某个顶点连接到它本身，且其长 度大于等于3 ，称此路径为回路。 图中某节点i 的度数等于与该节点相关联的边数。如果一个节点的度数为零， 称它为孤岛。一个具有n 个顶点的图g ，在去掉任意k 1 个顶点后( 1 = k = n ) 所得 的子图仍连通，而去掉k 个顶点后的图不连通，则称图g 是连通的，k 称作图g 的点连通度。 当给定光网络的物理拓扑结构，可以用一个无向图g ( v ，e 1 来表示。每个顶点 对应实际网络中的光交叉连接节点，而边对应连接两个节点| 日j 的一组光纤对。假设 每条光纤有五个波长的集合，w 2 表示网络中源目的节点对之间的总通道数。 可以用图中的顶点来代表网络的节点，图中的边来代表网络中的链路。图有两 种常用的表示方法【46 1 。图2 2 ( b ) 一个