（通信与信息系统专业论文）wdm环形网络的生存能力与波长分配问题研究.pdf

w d m 环形网络的生存能力 与波长分配问题研究 摘要 波分复用( w d m ) 技术在未来的骨干网中扮演着极其重要的角 色。在w d m 光网络中，如何合理的规划蚓络的波长资源，足决定 嘲络资源利用效率的关键问题，同u , 3 ，光网络具有高速、大容量、 多业务的特点，日发生故障将给用户带来巨大的损失，而不具有 良好生存能力的网络是不能实际运营的。本文针对波k 路由环形网 络的两个关键问题一一路由和波长分配问题( r o u t i n g a n d w a v e l e n g t h a s s i g n m e n t - - r w a ) 和光网络的生存性问题进行，研究， 主要工作及成果如下： l 、分析了w d m 网络的r w a 问题。图论中的相关数学理论是 解决r w a 问题的个有力工具。本文对小犁w d m 环网的波长资源 分配进行了深入分析，采用无阻塞站点接入方式可消除接入站对波 长的限制，这为后一阶段的工作打下基础。 2 、探讨r 光网络的生存性问题即故障的保护和恢复。鉴丁i 叫步 数字体系s d h 环形l 叫络结构的巨大成功，w d m 环形网络必定首先 实用化、商用化，本文着重对各种保护恢复机制的自愈环网进行j ， 分析与比较。 3 、针对w d m 环网结构并应用顶点图着色方法，提出了一种启 发式波长分配算法本文称为“改进的g r e e d y 算法”。利用计算 机仿真与文献中常用算法进行了比较，证明了该算法用于w d m 环 网的静态波长分配能获得更高的波长利用率。然后本文利用该算法 对各种不同保护结构w d m 环网的波长配置需求进行了实验分析与 比较，尤其对于大型网络，不同结构对波长的需求差别较大，这为 建设网络时的综合考虑及权衡利弊提供了参考和帮助。同时，通过 计算分析，得出了评价w d m 环网波长分配算法的两个严格的波长 下限，这可作为分析w d m 网络资源利用率的依据。 关键词：波分复用，路由和波长分配，生存性，保护和恢复 图的顶点着色，自愈环 s t u d yo nt h es u r v i v a b i l l t y a n dr w af o rw d mo p t i c a lr i n g s a b s t r a c t w a v e l e n g t h d i v i s i o n m u l t i p l e x ( w d m ) n e t w o r k sw i l lp l a y a n i m p o r t a n t r o l e i nf u t u r eb a c k b o n en e t w o r k s 。h o wt op r o g r a m m i n gt h e w a v e l e n g t hr e a s o n a b l yi n t h en e t w o r k si sak e yi s s u e a n dd u et ot h e s p e c i a l t y o fh i g h s p e e d ，h u g e c a p a c i t ya n dm u l t i s e r v i c e so fo p t i c a l n e t w o r k s ，t h en e t w o r k sw i t h o u tt h en i c es u r v i v a b i l i t ya r en o ta l l o w e dt o b ee m p l o y e d i nt h ep a p e r ，t h e s ek e y t e c h n o l o g i e so fw a v e l e n g t hr o u t i n g r i n gn e t w o r k s ，t h er o u t i n g a n dw a v e l e n g t ha s s i g n m e n t ( r w a ) a n dt h e s u r v i v a b i l i t yo fw r n ，i s r e s e a r c h e di nd e t a i l 1 t h er w ai sa n a l y z e d g r a p ht h e o r yi sa ne f f e c t i v et o o lf o rt h e p r o b l e m w ed i s c u s s e dt h ep r o b l e m o fr w af o rs m a l lw d m r i n g s ，a n d t h er e s t r i c t i o no fa c c e s ss t a t i o nt ow a v e l e n g t hi sa v o i d e di fw ea d o p t n o n b l o c k i n ga c c e s ss t a t i o n ( n a s ) t h e s ea r eg r o u n d w o r kf o r n e x t p h a s e s 2 t h es u r v i v a b i l i t yo fo p t i c a ln e t w o r k s ，i e t h e p r o t e c t i o na n d r e s t o r a t i o nf o rf a i l u r e ，a r ed i s c u s s e d w h e r e a st h ev a s ts h c c e s so fs d h n e t w o r k s ，i ti sw d mr i n g st ob eaf a c tf i r s t l y s o m ek i n d so fw d m s e l f - h e a l i n gr i n g sa r ed i s c u s s e d a n d c o m p a r e d 3 u t i l i z e dt h em e t h o do fv e r t i c e sc o l o r i n g ，a ni n i t i a t o r ya r i t h m e t i c i sp r o p o s e da c c o r d i n gt ow d m r i n g s ，a ni m p r o v e dg r e e d ya l g o r i t h m s i m u l a t i o no nc o m p u t e ri sc a r r i e do u tt oc o m p a r et h i sp r o b l e mw i t ha u s e do n e ，t h en e wa l g o r i t h ma c q u i r e st h eh i g h e rw a v e l e n g t he f f i c i e n c y t h e nt h ea l g o r i t h mi su s e dt oc o m p a r et h ed e m a n do fs o m ed i f f e r e n t r i n g s t h er e s u l ts h o wt h e r ei so b v i o u sd i f f e r e n c ef o rt h e s e r i n g s e s p e c i a l l y f o rb i gn e t w o r k s i to f f e r st h ec o n s u l ta n dt h eg i s tf o rt h e b u i l d i n g o fw d mn e t w o r k s t w os t r i c t w a v e l e n g t h l o w e rl i m i t sa r e a c h i e v e dt oe s t i m a t i n gt h er w a a l g o r i t h mf o rw d mt i n g s i tc a nb e u s e da st h ec r i t e r i o no ft h eu t i l i z i n gr a t eo fw d mn e t w o r kr e s o u r c e k e y w o r d s ：w d m ，r w a ，s u r v i v a b i l i t y , p r o t e c t i o n a n d r e s t o r a t i o n ，v e r t i c e sc o l o r i n go fg r a p h ，s e l f - h e a l i n gr i n g s w d m 球形碍褥熟隹存能走b 教捉劳截蜘进磺究 鸳一章绪蹬 i i ；l 言 第一章绪论 | 夭| 特黼及其他数字网络韭务的恢速增长，推动着电信照务献以话音业务为 中心向馘数据监务为中心不断演迸，这就需要从瞬络设计、随络控翎菇及随络 管理方面对传统的电信网络结构进行修整和改进，获而形成新一代网络体系结 构。近几年来，随着掺铒光纤放大器的出现及迅速商用化、高速波分复用 ( 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 ) 激光器、接收机、光纤非线性和w d m 选路研究及标准化工作的突破性发展，使w d m 技术迅速成熟。w d m 技术在 同一根光纤上同时用多个波长来分别传输不同信道的信号，对网络的扩容升级、 发腱宽带业务、充分挖掘光纤带宽潜力、实现超高速通信等具有卜分重夏的意 义。新一代嘲络体系结构的核心技术就是基于波分复用原理的多波长光刚络技 术。 荐种类型的新的通信业务正在小断涌现，如因特燃浏览、视频点播、视频 乜话和视频远穰会议等，都依朔于光蚓络所特有的巨大带宽的支持。光纡具有 带宽宽、损耗低、馀格低、熏量轻、强度葶1 1 灵活性好、4 i 易受噤声蓐u 电磁下执、 粜密性秘隐秘性好以及具有缀好的拭媾蚀性，自从1 9 7 0 年壤宁公剥制成第一根 低按耗黩光纤以来，对全光信息赢速公路豹想象就激发了研究者、业务提供齑 秘公众躲巨大兴趣。但在实鞯情况中，几乎联有的光纡最秘都是俦为一种钢缆 稿辽接替代晶藤配置到传输链路上豹。塔营已经铺设7 数量巨大的龙缆，但还 远远没有充分利窝i 这些资源奉身掰其有的容量潜畿。鹅一方螽，体疆着个入电 脑普及黹来的i n t e m e t 的飞速发麓，人类社会送入了一个前所未有酶信息曝炸时 代。而这种通信注务疯摹差增长的盛援后果就是出现了所谓的“光纤耗铎”或象 埋下去的光纤都用究了。这是闻为，地下的光纤并没有组成一种商效的结 构形式，使得它们对于新的宽带业务无法充分利用它们的臣大带宽容量。 w d m 坪形裙络鹤生存齄办与技长势配甜趱磷寇第一誓绻沧 光纤所熙有的各种优越特性使光纤成为一种技术奇迹，但避只有通过适当 的、合理的、科学的体系结构互联以后才能组成真正的嘲络体系结构。从这种 意义上说。光网络( o p t i c a ln e t w o r k s ) 是种以光纤作为慕本传输链路并充分 利用光纤所具有的非常独特的特性而组成的一种通信体系刚络结构。可以说， 目前构建广域光嘲络的时代已经成熟”1 。静先，支持光嘲络发燧的技术正在飞 速前逃，只前最重要的发展是掺铒光纤放大器的商用化。第二，与波分复罔 ( w d m ) 传输系统棚关的一个迅速膨胀的市场需求已在各个运营巍之间出现， 运营齑们震要增抛她啦】的系绕容量来满足宽卷业务日羹增长的蔫求。毅的赢性 毙、高可靠牲、性能馀掺比已相对台逶的技术弱裁已经进入实明阶段，它爱过 来将进步雄动辩求豹继续增长。第三，羟翦许多大的多波长竞带蜒终实验丁 程在世器藏粥内正在紧锣密鼓豹主鎏章亍誊。最后，近年来i n t e m e t 娩务翡爆炸式发 壤为大容量帮高质量逶倍体系架构发袋提供了强劲豹搬动力，这萃孛新型糍络体 系缔槁正是支持井喷式增长静i n t e r n e t 韭务和其稳广域阏啦务所必不可少秘必 须依赖的理怒网络结构体系。 i 2w d m 光网络懿结构与特征 光纤波分复飓1 2 】技术是在一棂光纾中同时传输多波长光信号豹一项技术。 其基奉殿理楚在发送端憋不网波长静光信号组合起来( 复娜) ，蒡耦合到光缆线 黪上款鄹一投光纤中避行传输，在接收瑞又将缀合波长豹光信号分开( 孵复用) ， 蒡俘避一步处理，恢复出摄蕊号蜃送人夺目静终遄。就发裂两言，据果巢个 嚣域内繇有的竞纤传输链潞黎拜缀为w d m 传输，我 3 藐霹跌建这些w d m 链 潞静交叉楚设鬣激波长为革位对光信号进行交叉连接兹光交叉连接设备 ( o p t i c a t c r o s sc o n n e c t i o n o x c ) ，或进行光上下路静光分插复用器( o p t i c a l a d d d r o pm u l t i p l e x e r - o a d m ) ，翻在髹来由光纤链路缀藏的物理层上商就会形 成个新的光层。在这个光层中，相邻光纤镀路中的波长通道可以连接起来， 形成一一个跨越多个o x c 和o a d m 的光通路，完成端到端的信息传送。并且这 种光通路可以根据需要灵活动态地建立和释放，这个光层就是日前q f 人注f 的 新代w d m 全光刚络。 2 w d m 玮彩弼络簿肇存髓力渡砼绔配秘避秘究第一譬靖沧 i 。2 ，lw d m 光网络的分屡结构 首先介绍两个光刚络组成要素：光嗍络节点和网络接入站的功能定义。 光网络节点( o p t i c a l n e t w o r k n o d e s o n n ) ：连接嘲络中的光纤，提供交 换和选路功能，控制光信号路径，分配路径和创建希望的源和目的之间的连接。 网络接入站( n e t w o r k a c c e s ss t a t i o n s - n a s ) ：用户终端和其他无光终端系 统与光删络的接口，是物理层中光信号通路的终缡点( 光信号的源署u 目的地) 。 蚓络中的光电私光予器传主要集中在站剩节点上，主要有：激光器、搽测 器、凝合器、光纤、光交换莘“放大器等等。( 本文蒜重于醭究波长分配阅题，对 o 渊秘n a s 麴物理功熊皱构蝰疆i 乍避一步款探讨) 。 根挺l t u 一羊g 8 7 2 建议，毙屡分为三令孑撰( 见强l l 骶示光嬲终嬲分 接练构) ：( 1 ) 毙通遵基( o p t i c a lc h a n n e ll a y e r - - o c h ) ：该撮鲤络薅s d h 、 p d h 、a t m 、i p 等务张效务信患提供毙逶遂土透甥翡端至l 端传送；( 2 ) 光复耀 段簇( o p t i c a lm u l t i p l e xs e c t i o nl a y e r - - o m s ) ：该层疆络提供多液长光信号静 篓l 黼功能。光复糟段罄o m s 实际上就是光w d m 窿；( 3 ) 光蒋输段接( o p t i c a l t r a n s m i s s i o ns e c t i o nl a y e r - - o t s ) ：该层两络掇供光信号在各类光介质中的传输 功能。光传输段层o t s 实际l 就跫光纤毓路。图1 - i ( b ) 中，t p 和r p 分剐为 发射和接收处理器，o t 和o r 分剐为光笈射机和光接收机，o a 为光放大嚣。 光通道膳能为光通路选择路由和分配波长，光通路可以看作是光通道层上 的端到端的连接，通过光通道层的保护和恢复机制可以直接解决由于光纤切断 或节点故障等物理联原因造成的通信中断问题。 客户层 光层 对连接进行分配、选路和复用的控制算法 一个宠裕魏物璎拓扑结构可以提供多条遥路，提高燃络兹容量秘生存性以 及对受载变化的适痰能力。同时，只有链路、跚终节点和接入站具备完善的功 能特性才麓充分发挥耪瑷拓挣的特往。链路功能特性跫指个嘲络具有髂带宽 距离积。黼络节点和接入菇的功能特性包括可控锱的交换特性和复褥特性等， 它反峡了黼络的资灞利掰率、交换能力，也爱峡了在糊络元件失效的情况下重 新配置嘲络的能力。而可控性的实现要求必须有合适的控制算法来协调各个黼 络实体的功能。总之，三个特性于石扑、功能和控制密切合作从而制约和 澎响着嘲络的全局性能。 同时，还需考虑价格和性能的折中问题。节点和站具有较高的功能特性可 提高例络性能，但价格也会随之提高：增加物理拓扑的富裕度也是如此。为了 弥补嘲络资源的局限，往往通过复杂的控制算法来优化性能，这是以控制的复 杂性为代价。价格、性能之间的折中涉及所有特性之间复杂的相互作用。 w d m 玮瑶耩络媳生存匏办波长势配碗埋蟥究第一啦绩建 1 3w d m 光网络目前的研究热点 人们对w d m 光通信嘲络技术的研究正在兴越，圈内外日前对全光嗍的研 究正全颤艘开，主要的问题有以下一些3 】【4 】【2 8 】【2 9 j ： 1 、w d m 刚络节点技术 随着w d m 技术的成熟，一根光纤中已经能够传输上1 r 吉比特数量级的数 宁僚息，传统系统容量的快速增长带来的是对交抉系统发腱的压力。目前的电 予交换设备的发展已经接近墩子速率的极限，将无法适应未来的信息交换需求。 光交换技术救b 1 入，憋能很好的解决这个阉题。因为光交换的优点在于，光信 号在通过光交换攀元黠，不鬟要经过悲电、电光转换，对比特遮搴墨 l 调划方式 透明，霹以大大弱撮离交换擎元的吞蛙量。溅姥为了鳃决交换甄颈闫题，光交 揍豹研究开发刻不容缓。 2 、路由裙滚长分配闷题 给定一个阏络的物理拓扑和一套需要在阏络二建立兹瑞到端毙信遵，丽为 每个带宽请求决定路e 螽和分配波长隧建立光信遂的辩题就是波长选路年l l 波长 分配问题( 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 - r w a ) 1 2 0 or w a 可以用来有效 管理w d m 嘲络资源，最优化各种黼络往能，如嘲络吞吐率和拥塞率。根据节 点是否提供波长转换功能，光通路可以分为波长通道和虚波长通道，当整个光 路都采f i j 同波长时就称其为波长通道反之悬虚波长通道。尚前，还没有标准 的r w a 算法，有待于进步研究。 3 、波长转换器 波长转换器是解决垒光嘲中波长路由竞争的关键器件，是充分发挥w d m 带蹴资源的必要手段。在含有波长转换器的叫络中，光通道能够在不同的链路 l 删小间的波长建立，从而大大提高m 络的灵活性，消除光通道的波长冲突。 0 入波长变换技术，可以实现波长的再利_ 珥j ，吏有效地进行路由选择，降低删 络5 驵塞率，从而提高w d m 叫的灵活性和可扩充性。光l 】c 】4 络中0 i 入波长转换器， 建立虚波长通道，克姒波长连续性的限制，从丽充分利用波长资源，但是其缺 点是波疑转换嚣玲掺昂贵，因此人靠】提出只在部分节点使嘲波长转换器的摄中 方寰即嚣分寝波长避道。强蓠，如何缀好驰实施这辨方案，馊缛即能有效地提 高潮络牲能又糍节约成本，已经戏为个令人关淀终麟究热点v i i 。 w d m 醉群砖终的生存能力波彀分配霹毯麟究第一錾绪论 4 、删络的生存性 嬲络的生存性是指嘲络在经受器釉故障后仍能维特可接受的业务质量的能 力，它是划终完整性的一部分。w d m 姗终具有投毫的传输速率，即使是短暂 懿嘲终故簿也将带来誉霹怯爨的损失，因此探索能在尽可能短蜘时闽穴为披中 断麴业务寻找毅豹转输路出拳l 鱼愈方褰是1 分必要敫。嬲终生存性又可分为： 保护藉恢复。保护是颈先确定好豹失败恢复，在建立王 乍实毒 = 瓣目封也要建立 谦护实体( 帮舔窜缳护资源) 。各释豫护缀瘸根姑躅户豹需求秽颓算成奉确定， 歇1 + 1 ，l ：l 弱l ：n ，丽恢复是在探测到失黢程重，动态遣普找替代鼢路出，供中凝 的渡务使用。如采竣有我鬟新的路由，该_ 豫路径上携带的监务就会丢失。v i 前的研究热点是在嘲络黧构往方面开发类似予时分复稍s d h 环黼梳制的w d m 环嘲结构。 5 、光q o s 问题 全光网在一对源- 目的节点对之间提供多条光路径，各条光路径其有不同的 光质量，由光参数( 比特错误率、延迟、跳变) 和行为( 保护、监视、安全性能 力) 表征，印在不同的光路径上提供的服务质量是彳i 同的，这样就可以针对刁i 同级别的应用提供4 i 同级别的服务。而且上层0 i 同的用，l t 对光路的服务质蹩的 需求也小尽相同，由于这些原因使得w d m 光刚络的q o s 问题开始受到关注。 6 、光标记分组交换技术 为了更有效，灵活地承载未来的i p 龟分组业务，另种具有深远应用前 景的方寰是出具有光分组交换功能的核心路出器构扫蔓光驯络。光分组交换删络 中灼核心黢出器可以网对实现空分、时分和波分交换，弗且仅对带有路由信息 躲光分组头进行蹇速处理嚣为光分级的鸯效负载提供透明路径，| 天| 此它具有高 速、大器吐量、低延时、监务秘 e 特攀透明等突出侥点，旋蹇效地承载l p 业务， 淘时它还髓灵添遗缀隧秘实现涮络嚣缓，太柩瘦提裹喇终适癍性秘生存能力。 基予光标记交羧的分组光瓣络秘究在蹦终管瑾黍l 控制方盈，暇收了出了：程壬壬务 组1 e t f ( i n t e m e te n g i n e e r i n g t a s k f o r c e ) 开发懿m p l s ( m u l t i p r o t o c o l l a b e l s w i t c h i n g ) 技术的一垡优点，将m p l s 的标签交换、流量t 程和监务分类管璃融 入分组交换嘲络的管理与控制，以满足未来多监务的泣务质量( q o s ) 保证。 6 w d m g 嚣两终携生存能办与渡妖静醚如毪麟宠第一錾缝论 i 。4 论文主要工作 在同步数字体系s d t t 传送嘲中，广泛采用了环形嘲络结构，这是因为环形 刚络在保持较高生存能力的同时更容易实现和管理，而光分插复用器( o a d m ) 的出现促进tw d m 环形网络的研究籼发展。本文主要研究了w d m 环形光网 络的生存能力与波长分配问题。针对基于波分复用技术的这两项关键技术，应 用数学1 ：具和汁舅机仿真计算对w d m 波长路由环阱进行了详细的分据、讨论。 本文第二章讨论了路由和波长分配问题。茸先分绍了分析解决路由和波长 分配阀题( r w a ) 黢借助的数学工具图论鲍基本概念翔摆关定理：分缁了 r w a 鲍摄念、跤到条件及饯 艺羁标；举铡分橱了麓单w d m 联终双自环列嬲波 长分配翘题；r w a 掺为蹰熬着色目题来处理，将是一个完全l i 确定多矮式翔题， 实际解决润题对需搭髓予各释稿发式舅法。 本文第三章讨论了w d m 光鞘络抟生存褴阀题。鹾络韵生存梭浮教漳豹保 护恢复问题，本章集中讨论光层的生存能力，主要研究了w d m 环形嘲络的各 种谦护恢复机制，包括挚矗jw d m 逶道谦护环、蹭纤w d m 共享保护环、两纾 w d m 共享保护环及有限波长变换通道衡换环结构。w d m 环形瞄络结构是璇先 可能商用化的新一代光嘲络，其中两纤双向环网矮有随好的生存能力、易于管 理且嘲络建设成本相对较低，在各种环嘲结构中体现出较大的优势。 本文第四章针对两纤双向w d m 环嘲结构，提出了一种新的波长分配碚发 式簿法，这里称之为“改进的g r e e d y ”算法。该算法在图着色启发式算法 g r e e d y 算法的思路慕础上，吸收了“度大优先”方法的优点并结合w d m 环嘲 的特性提出的。通过与其它g r e e d y 算法的比较，发现该算法能够获得更优化的 波长分配结果。然后，本文采用改进的g r e e d y 算法，对箨种w d m 环例的波长 龈覆需求进行了定爨的计算与比较，结果表嬲，袋用4 i 同保护恢复机制的环嘲 结构的波长需求差别很大，具有有限波长变换通道倒换的两纡双l 环酬在正常 i j 乍情况下的波长露求远远小于其他1 ) e 9 络结构。州络运营巍可在综合考虑波长 震求、现有资源、建设成本及技术复杂性后，决定选择倪釉州络结构。 w d m 玮黪两爨静生稃蘸力s 教妊势裁秘强辑究舞? 释强经耜设筏凳鬣t r w a 张姓 第二章路幽和波长分配( r w a ) 问题 随着w d m 技术日趋成熟，w d m 技术已经进入实用化和商业化阶段，如 tt 何利用现有的和即将敷设的光纤进行联嗍，构成采来黼速、大容量、多业务盼 w d m 嗍络已经成为光通信领域中的个蕈耍问题。在w d m 光刚络的实现中， 如何合理的规划嘲络的波长资源，是决定网络资源利用效率的关键问磁，波长 路由的光网络可以大大简化路由选择算法和网络的控制和管理，不需要在交换 时预处理路由信息，从而更有利于实现高速、大容量的通信网络，提高网络的 可靠性和稳定性，然而由于w d m 嘲络的光纤和波长资源非常有限，因此如何 充分利用光网络的资源以使网络的性能达到最佳就成为一个很有现实意义的研 究课题。本章蒋先列顾了相关的数学理论基础，然后介绍了路由和波长分配问 题，对麓擎巧形w d m 网络的波长分配闯题传了深入约礤究，最后介绍了路由 矧波长分配闫题作为图善色闫题的一般慰路。 2 ，1 理论基础图沦 21 1 图的基本概念 瞬沧中将醒定义为个倩对g = ( v ，e ) 巴其中v 表示顶点的集合，e 表示边的集合。图2 1 可表示为 v = v i ，v 2 ，v 3 ，v 4 ，e = p i ，口2 ，e 3 ，e 4 ，e s ，e 6 。 也可以用边的两个顺点来表示边，如果边e 的两个端点是u 丰uv ，那么e 州+ 写成e = u ，v ) ，这里 u ，v ，表示u 和v 的无序对。如果两个顶点相同，该 边溉称为一个坯；如果两条或炳条以上的边商相同的顶点，则这些边称为半行 边。没有环秘半行边的圈称为简单图 ，则称u v 楚相邻的，而称e 与u v 关联( i n c i d e n t ) ； 一一个顶点v 的魔指的是与它关联的边的数量。如果两条边都与阎一个顶点关联， 则称这两条边燕邻接的( a d j a c e n t ) 。如果任意两顶点之间都有边连接，则g 为 完全图n 个顶点的无向完全图记做k 。 图g 一( v ，e ) 的一个顶点和边的交替序列u = v o e l v l v k l e k v k ，且边e ， 的端点为v i i 和v i ，i _ 1 ，2 ，k ，则称为一条7 0 一k 道路( p a t h ) ，v o 和 v t 分别为“的起点和终点。特别如u 中所有的边都刁i 相同，则称其为简单道路。 若g 的两个顶点u 、v 之间存在条道路，则称u 和v 是连通的：若图g 的任 意两顶点连通，则称图g 是连通的，番则是非连通的。 平葱图的定义：如累图g 能够测在曲匾s 上，且除顶点处之外任何两条边 均小相交，则穗图g 被嵌入魈越s 上。如果个豳可以嵌入在半题上，则称为 可学馥圈，已经被嵌入在乎瞧上的图豫为半_ 蜒圈。铡妇图2 - 2 所承，g 图可乎 商化为闰g 。一i 是任何一个图都楚可半商圈，圈2 - 2 1 ， ( b ) g f i 存在边数为奇数的回路。 证明：若g 是连通图，且小存在边数为奇数的目路。任从图中找一棵树t ， 显然作为g 的子图t 有x ( g ) = 2 。在树t 上每加一条余数边时，便获得图g 的一条回路。根据图gh i 存在边数为奇数的回路，故所有余树边的两端点颜色 小同。这就证明了若图g 没有奇数边的回路时，x ( g ) = 2 。反之，若图g 有 奇数边的回路时，x ( g ) 3 。证毕。 定理2 若图g = ( v ，e ) ，d = m a x d ( v 。) ，则x ( g ) d + 1 。( d ( v ) 表 j ：顶点v 的度数) 。 证明：用数学归纳法来证明。设n = i v l 。显然n = 1 时，图g 只有一个顶点， 此时d = 0 ，而x ( g ) = 1 ，定理成立。假设定理对i v = n - 1 时为真。若从图g w d m 邸形舄络豹譬荐龌力与教长势配5 # 罄醴霞蒜锥繇赴稚设疑夯鞋r w a 祧鞋 中增加一个顶点v 0 ，则与v o 邻接的顶点最多有d 个，即使这些顶点都着h i 间颜 色，也不会超过d 种颜色，则给v o 着爿i 同颜色，瓴数4 i 会超过d + 1 种，定理亦 成立。 定理2 给出的是色数的上界，有时比实际值要大得多。例如一个乎嘲图，无 论顶点约度商多大，定色数小会超过4 ，灏项点大于l 的树的点色数只是2 ，冈 此，这一定理款效累是椽当弱的。 ， 2 1 5 一种顶点色数求法 下面给出一种顶点色数求法。 图g = ( v ，e ) ，v i 和v j 是g 的两个不相邻的顶点，若将v i 与v j 凝缩为一 点z ，瞬g 变成g l ，凝缩时原与v ，或v j 关联的边成为与z 关联；若在v 与v j 问添上条边，图g 变成g z ，称为圈的并接。 定理3 ：图g 的顶点色数为f 6 】 z g ) = m i n z ( g 1 ) ，z ( g ：) ) 证鞠：对圈g 熬点簧色瓣，v ，和v ，的颜色有疆釉可熊，v ；与v j 因色或v ，与 v j i 嗣色。 若v 。与v 。黼色，刚凝缩嚣z 点可_ 辞j 鞠一颜色纛不须改变箕穗璎点瓣颜色， 故x ( g ) 一x ( g l ，襁并接时v ，帮v ，须着不同静颜色，粼x ( g 2 ) x ( g ) ： 若v 与v 。一i 同话，刚并接后夺须改交v 和v 的颜色，舔x ( g 2 ) 一x ( g ) ， 值原来与v i 邻接的点可能有与v 相间的颜色，而原来与v j 邻接的点可麓有与v i 相i 西的颜色，闲此肖v 。与v j 凝缩为z 点后，讨能需要着既不简于v 。也不同于v j 的另一种颜色，闵此x ( g 1 ) x ( g ) 。综台两种情况上式符证。 这个定理给出了求嘲g 色数的种方法：设v ，和v 。燕图中不相邻的两个顶 点，v iv j 有相同颜色的g 的着色给出g i 的个着色：v i 与v j 有4 i 同颜色的g 的着色给出g 2 的一个着色。将两种运算蕊复进行，真到所得到的图是完全图为 止。若所得到的完全图中最小的是k r ，那么x ( g ) 一r 。 例如，求图2 - 6 中图g 的色度数。 求解过程如图，其中空心圆点表示所考虑的两个4 i 邻接点v ，和v j 。最后得到 的都是一些完全图，最小的是k 3 ，故x ( g ) = 3 。 4 w d m 强蟛秘缩霸生存能力咯渡捉分配硒蘑姘究嚣7 耀锅电稚敬钦分配t r w a 、越 k 4 k 篷2 6 例如可用红、黄、蘸三色着色如图2 。7 所示。 2 2 路由和波长分驾e 问题 翅2 7 光波分复用网络有两种交换方式：光路交换和分组交换，从而形成光路交换 删捌分组交换嗍。光路交换w d m 嘲是目前研究得最多，也是最接近实用化的一 种i 叫络。在荚国、e j 本以及欧洲的一些国家已经建立了基于光路交换的w d m 实 验j 叫络。从拓扑结构上看，光路交换w d m 刚有两种主要的形式：其一是广播选 蹦州，即星形结构的蚓绻；其二是波长路由删。 广播选路蚓中餐个节点通过光纤署u 无源星形勰合器连接，每个节点被分给卅i 网的波长。这砷| 尚4 终很可靠，丽且易于控制，但是这茅中删络j # 誊浪费光能，阏为 每一个要传输数光能几乎都被半分到列终中的所旁节点上去了，露且每个节点都 霞要一“个l i 网约抟输波长，没有波长霉用，两疑藏光波长数日毒限，掰以蚓络的 节点数羟也裁毒限了。广播选路捌较适合用俘局域 ) l 。 波长路出鲥( w a v e l e n g t hr o u t i n g n e t w o r k s - - w r n ) 能够实现对每令波长信 w d m 坪彩霹络抟生存裾女与攘嚣势配弼避辫究舞二镪强瞧瓠凝聚儋配i r w a ) t 题 道的自由交换和路由选撑。网络节点具备能在一个输入光纤上独立的组织波长信 道，并把它送到特定的输出光纤上的能力，即具有波长选路功能。以波长路由为 基础，可实现蚓络的动态重构和故障恢复，具有高度的灵活性筹u 生存性。在波长 路出蚓中，一条光路所经过的路由瓤使劂的波长通过路由和波长分配( r o u t i n g a n dw a v e l e n g t ha s s i g n 翻瞎n t r w & ) 算法来决定。r w a 是摆在有光路 连接谚求豹节点对之阑寻找一条最线路出，并分配波长。从总体上嚣，r w a 问 题中的蹲幽程波长分配跫一个誉可分割的闫题，毽要在合理载运算f l 重闽内姆决大 型嘲络静r w a 闼藤常常是不可能豹，。常溺瓣解决方法是将r w a 霹攥成蕊个独 立扮子闷臻分剐掘戳解决1 ) 寻找麸添节点到鞭懿节点的路由：2 ) 在这些鼹疰l 上分 配波长。 在w d m 光网络中，交换设备与放大设备酶成本和可行性都香赖于它们掰处 理的波长数目，商朋亿的w d m 设备大大的限制了所能采精静波长。一个r w a 算法的目标是在物理资源相对有限的情况下，尽可髓穗获得最佳的网络性能。 2 2 + l 静态r w a 翘题靼旗态r w a 问题 在研究r w a 问题时，通常将嘲络支持的业务分为两类：1 ) 静态业务( s t a t i c t r a f f i c ) ：给定一组连接建立请求，需要为这些请求寻找路凼并在其路由上分配波 陡，以使某些性能指标达到最优( 如所需波长数或光纤数最少等) ；2 ) 动态业势 ( d y n a m i ct r a f f i c ) ：光路请求随机到达和离开嘲络，相应的性能指标通常是光路 的阻寒率【l ”。按照所支持的业务类型划分，r w a 问题分为静态r w a 问题和动 态r w a 润题 3 3 】。 假设已知列终的物理辐持续均，静态业务的r w a 问题是指对一缎确定的、 霭爱建立的光遵路选择踞由并分配波长，毽是由于掺铒光纾教大器( e d f a ) 的 臻盏繁宽有限以及光纾中躲非线性效癍戆限剁，州终中能使明的波长数疑是有限 豹。藤鑫隧着波长数拜露蜷掘，嘲终节点所瓣器释的规摸秘戏奉瞧会迅速璞加， 潮时磺加掰络管理鹃难菠，闵北鲡话合瑷静避幸亍路由鞘波长分配鼓使嘲络中矮鬻 的波长数拜最少是一个很霉要的研究课题。奉文主要研究静态波长分配闷题。 萌态r w a 问题，鬣指在实时业务条件下的光通道路由选箨秘波长分配优化 问题。此时光通道的连矮请求是随丰凡到达的，并置己建立的连接在维持任意一段 w d m 环形磅络的生存转力与渡梃分配鲫趱研究豫晕路电稚淑长论配t r w a f l 题 时间后会被撤销。由于需要建立的光通道数量和位置是彳i 固定的，并且随时在改 变，冈此选择服务性能指标( 阻塞概率) 作为动态r w a 问题的优化目标，这也 意味着怎样才能在有限网络资源条件下建立尽可能多数量的光通道连接。 22 2 波长通路和虚波长通路 根据嘲络节点是否提供波长转换功能，光通路可分为波长通路( w a v e l e n g t h p 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 ) 。 波长通路是指网络节点没有波长转换功能，某一个光通路在不同光复用段中 必须使用同一波长。如果在它所经过的所有链路中，找不到一条有一个共同空闲 波长信道的路由，就会发生波长阻塞。虚波长通道是指在网络节点中具有波长转 换功能，光通路在同一波长通路的不同波长复用段中可以占用1 i 同的波长，从而 提高波长的利用率，降低阻塞发生的概率。由于可用的波长数是有限的，为了优 化嘲络性能，无论哪种类型的网络，都需要根据网络的物理拓扑结构和各节点间 的业务需求，设计最优的刚络拓扑连接方案。 22 3r w a 问题的两个限制因素 日前，就透明光i ) 【) 9 络而言，波长转换技术的应用仍然是个很有争议的话题， 透明的波长转换技术的实现在技术上和成本上都存在困难，非透明的波长转换技 术将使得转换对信号格式不透明，而且，在网络中以合理的代价引入波长转换技 术所换取的删络性能增益还未成定论。有文献表明，波长变换的增益与刚络 的连通度有关：对于连通度较小( 如环形| ：i ) 9 ) 和较大( 如全连通例) 的刚络，增 益较小；对于中等连通度( 如刚状结构) 的网络，增益较大。本文主要考虑在正 常光路传输过程中无波长转换情况下的r w a 问题。此时，路由和波长分配主要 受两个限制： 1 、波长连续性限制：每一个光连接的波长在它从源到终端所经过的所有链 路上均保持小变。 2 、一i 同信道分配限制：所有共享同一个光纤的连接必须被分配4 i 同的信道。 ( 这适于接人链路和相互连接节点之间的光纤链路) 。 w d m 拜形卿络的生存齄力0 波梃分配阳趱研究锥母路电秘嵌k n 配r w a ) 题 2 3 简单w d m 环网波长分配举例 具有一定对称性