（信号与信息处理专业论文）波分复用光网络中的动态路由算法的研究.pdf

浙江工业大学硕士学位论文 波分复用光网络中的动态路由算法的研究 摘要 w d m 光网络技术是实现“全光网络”最高阶段的最有前景的 方案之一，路由与波长分配算法是在光网络资源受限的情况下的优 化算法，对合理进行网络优化，有效利用网络资源具有重要意义。 本论文对w d m 光网络中动态业务下的r w a 问题进行了研 究，主要从算法的目的、性能评价、影响算法的因素以及算法的实 现方法等方面，针对动态业务模型下的波长路由算法提出了相应的 解决方案。并综合应用数学建模、计算机仿真对所提出的方案进行 了详细地分析。论文的主要工作以及成果如下： 1 ) 对w d m 光网络动态r w a 问题进行了深入研究，总结前人的研 究成果，给出了w d m 光网络动态r w a 问题的物理模型和数学模 型。根据动态网络中节点是否具有波长转换功能，将动态路由问题 分为波长通道路由问题和虚波长通道路由问题分别进行探讨，并分 析了两种情况下的阻塞率情况。 2 ) 对波长转换受限光网络下的动态路由算法进行了研究，通过引入 链路综合代价、路由优化和波长优先级分层图，将三者结合对传统 a d m h 算法进行改进，提出了一种新的动态自适应路由算法，并进 行了计算机仿真，结果证明这种算法优于传统算法。 3 ) 对波长转换非受限光网络下的动态路由算法进行了研究并引入 了仿生学理论蚁群算法解决动态路由问题。对基础蚁群算法进 1 浙江工业大学硕士学位论文 行了深入研究，在此基础之上，通过改进寻路过程中链路综合权重 的设置、优化蚁群寻路的原理以及波长优先级等提出了两种改进型 算法，分别为基于流量限制和基于波长优先级的算法。进行了计算 机仿真，结果证明改进的算法优于传统算法。 上述研究结果发表了3 篇学术论文。 4 ) 参与了基于v c + + 平台的仿真软件w r o n r w a l 0 和 w r o n r w a 2 0 的设计开发，已经授权了2 项软件著作权。本仿真 软件对常见的算法、改进算法以及本研究组新提出的算法进行了实 现以及仿真验证，为理论分析提供数据支持。在此部分工作中，论 文作者主要负责路由算法的实现。 关键词：w d m 光网络，动态业务，r w a 算法，自适应路由，均 衡策略，蚁群算法，仿真 n 浙江工业大学硕士学位论文 s t u d yo nd y n a m i cr o u t i n ga l g o r i t h m s i nw d mo p t i c a ln e t w o r k s a b s t r a c t w d mi so n eo ft h em o s tp r o m i s i n gs o l u t i o n sf o rt h ei m p l e m e n to f a l l o p t i c a ln e t w o r k s r o u t i n g a n d w a v e l e n g t ha s s i g n m e n t ( r w a ) a l g o r i t h m sa r e k i n d so fo p t i m i z a t i o n a l g o r i t h m sw h e nt h en e t w o r k r e s o u r c e sa r er e s t r i c t e d f o rt h es a k eo fp r o p e rn e t w o r kd e s i g na n d e f f e c t i v eu t i l i z a t i o no fn e t w o r kr e s o u r c e s ，i ti sc r u c i a lf o rt h es t u d yo n 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 ta l g o r i t h m s t h i st h e s i s m a i n l ys t u d yo nr w ap r o b l e mi nw d mo p t i c a l n e t w o r k sw i t h d y n a m i ct r a f f i c t h ep e r f o r m a n c ee v a l u a t i o n ，e f f e c t f a c t o r sa n dt h ei m p l e m e n tm e t h o do fr w a a l g o r i t h m sa r es t u d i e d ，a n d t h ec o r r e s p o n d i n gs o l u t i o n sa r ep r o p o s e d f u r t h e r m o r e ，t h r o u g hm a t h m o d e la n d c o m p u t e rs i m u l a t i o n ，t h e s o l u t i o n sa r e a n a l y z e d a n d d i s c u s s e d m a i nw o r ko f t h i st h e s i si sa sf o l l o w s 1 ) t h ed y n a m i cr w ap r o b l e mi sf u r t h e rs t u d i e d ，t h es o l u t i o n sw h i c h a r ep r o p o s e db ys o m ef o r m e r sa r es u m m a r i z e d ，a n dt h ep h r s i c a lm o d e l a n dm a t hm o d e la b o u td y n a m i cr w ap r o b l e ma r e p r o p o s e d t h e p r o b l e mi s d i v i d e di n t ow p ( w a v e l e n g t hp a t h ) r o u t i n gp r o b l e ma n d v 、聊( v i s u a lw a v e l e n g t hp a t h ) r o u t i n gp r o b l e ma c c o r d i n gt ot h e w a v e l e n g t hc o n v e r s i o nn o d e s ，a n dm o r e o v e r ，t h eb l o c k i n gp r o b a b l yo f h i 浙江工业大学硕士学位论文 e a c hc a s ei sa n a l y z e d 2 ) t h ed y n a m i cr o u t i n ga l g o r i t h m si nw pn e t w o r k sa r es t u d i e d b y i n t r o d u c i n go v e r a l lc o s to fl i n k s ，o p t i m i z a t i o no fr o u t i n ga n dp r i o r i t y d i f f e r e n t i a lp l o to fw a v e l e n g t h ，t h et r a d i t i o n a la d m ha l g o r i t h mi s s t u d i e d ，a n dan o v e la d a p t i v ed y n a m i cr o u t i n ga l g o r i t h mi sp r o p o s e d f u r t h e r m o r e ，t h es i m u l a t i o nr e s u l t si nt e r m so fb l o c k i n gp r o b a b i l i t y s h o wt h a ti tp e r f o r m sb e t t e rt h a nt h eu a d i t i o n a la l g o r i t h m s 3 1t h ed y n a m i cr o u t i n ga l g o r i t h m si nv w pn e t w o r k sa r es t u d i e d b i o n i c so fa n tc o l o n yi si n t r o d u c e dt os o l v et h i sp r o b l e m o nb a s i so f t h er e d e f i n eo fo v e r a l ll i n kw e i g h t ，t h ef u n c t i o no fa n tc o l o n ya n d p r i o r i t yo f w a v e l e n g t h ，t w on o v e la l g o r i t h m sa r ep r o p o s e d a d d i t i o n a l l y , t h es i m u l a t i o nr e s u l t si nt e r m so fb l o c k i n gp r o b a b i l i t ys h o wt h a tt h e y p e r f o r mb e t t e rt h a nt h et r a d i t i o n a la l g o r i t h m s 4 ) t h es i m u l a t i o np l a t f o r mn a m e dw r o n - r w a i sd e v e l o p e d 。i tc a n p r o v i d ed a t as u p p o af o rt h e o r e t i c a la n a l y s i sb ys i m u l a t i o n r e s p o n s i b l e f o rr o u t i n ga l g o r i t h m s k e y w o r d s ：w d mo p t i c a ln e t w o r k ，d y n a m i ct r a f f i c ，r w a a l g o r i t h m ，a d a p t i v er o u t i n g ，e q u i l i b r i u m ，a n tc o l o n ya l g o r i t h m ， s i m u l a t i o n 浙江工业大学硕士学位论文 图列 图l 一1 光网络物理拓扑和逻辑拓扑4 图2 1网络物理结构举例9 图2 - 2 光路举例1 0 图2 3 固定路由算法1 4 图2 - 4 备用路由1 4 图2 - 5 简单光网络1 6 图2 - 6 波长通道光网络1 6 图2 - 7 混合光网络1 6 图2 - 8 根据网络状态进行选择的自适应路由1 7 图2 - 9 一个跳步数为h 的光连接例子一2 0 图2 - 1 0 波长转换增益g 与跳步数h 、波长数f 的关系2 2 图3 - la d m h 算法流程图2 7 图3 - 2 不同波长数对应的p 值( h = l - - 4 ) 3 0 图3 - 3 不同跳数数对应的b 值( w = l 1 5 ) 3 0 图3 4 波长连接数与优先级之间的关系3 l 图3 - 5 七节点网络仿真拓扑图3 3 图3 - 6 双纤4 波长光网络平均阻塞率随网络业务负载变化的曲线图3 4 图3 7 双纤8 波长光网络平均阻塞率随网络业务负载变化的曲线图3 4 图4 1 网络拓扑图( 前一数字代表节点距离，后一代表流量) 一4 0 图4 2 选路时间对比图4 l 图4 - 3 算法拥塞率比较4 3 图4 - 4 波长数区间对应链路等级4 6 图4 。51 4 节点n s f n i t 网络4 8 图4 6 网络负载均衡度( 平均链路等级) 比较4 9 图4 7 拥塞率比较一4 9 图5 1 计算机仿真流程图5 2 图5 2 仿真平台的结构图5 3 图5 - 3 菜单视图5 5 图5 - 4 工具栏5 5 图5 5 自定义拓扑5 6 图5 - 6 编号视图5 6 图5 7 权重视图5 6 图5 - 8 计算路由5 7 图5 - 9 显示路径 图5 - 1 0 打开文件 图5 1 1 拓扑显示 图5 一1 2 算法选择 图5 1 3 显示路径 5 7 5 7 5 8 5 8 5 8 v i l i 浙江工业大学硕士学位论文 表2 1 表3 - 1 表4 - 1 表4 2 表4 3 表4 - 4 表列 路由测度和最优路径2 0 不同网络对应的b 值 动态选择路由( 0 一1 9 ) 4 2 动态选择路由( o 一1 9 ) 4 2 链路等级和概率值( a - - 2 ) 4 6 链路等级和概率值( a 3 ) 4 7 i x 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 作者签名 给唧峰 日期：乃瞬胁f l - , , y 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密留。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 今竹峰 ，6 1 j i 从乙一 l 日期：知 年i 月衫_ 日 日期：砷年f 月矿日 浙江工业大学硕士学位论文 1 1w d m 光网络简介 第一章绪论 信息化、数字化、全球化、网络化是2 1 世纪人类社会的重要特征。网络作 为信息社会的主要载体，是全球最重要的基础设施之一。在信息网中，全球范 围内数据业务突飞猛进，新的应用层出不穷，电信网、互联网和广电网彼此渗 透，固定网和移动网交织重叠，电路交换与分组交换互相依存，无线上网、移 动上网、家庭网络和传感网络等蓬勃发展，人与人、人与机和机与机之间“处 处、时时”的任意互动，一个前所未有的、由量变到质变的技术和应用“井喷” 局面已经初见端倪。 光纤通信是目前实现高速、大容量传输的唯一使能技术，以光纤为基础的 光网络是构建信息社会的重要承载平台。光网络( o p t i c a l n e t w o r k s ) 是一个简 单通俗的名称，包容十分广泛。仅从字面上理解，它兼具“光”和“网络”两 层含义：前者代表由光纤提供的，大容量、长距离、高可靠的链路传输手段； 后者则强调在上述媒质基础上，利用先进的电子或光子交换技术，引入控制和 管理机制，实现多节点间的联网，以及针对资源与业务的灵活配置。随着网络 的快速演进以及由此产生的巨量业务需求，极大地促进了光网技术的进步，推 动光网络朝着更加智能、灵活、透明、优质和安全的方向发展。 波分复用( w d m ，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 和光交叉连接( o x c ，o p t i c a lc r o s sc o n n e c t ) 为基础的光网络层，实 现用户端到端的全光网连接，用一个纯粹的“全光网”消除光电转换的瓶颈， 将是未来的趋势。现在w d m 技术还是基于点到点的方式，但点到点的w d m 技术作为全光网通讯的第一步，也是最重要的一步，它的应用和实践对于全光 网的发展有举足轻重的影响。 1 1 1w d m 光网络发展过程 贝尔实验室于二十世纪八十年代中期提出创建基于波分复用( w d m ) 的 局域网的可能性，直接导致了全光网络财团的建立【”。在贝尔实验室、m i t 林 肯实验室以及d e c 公司( 现属康柏公司) 共同努力下建立的全光网络财团，曾 堑坚王些丕堂堡主堂焦丝銮 演示了基于无源波长选路创建局域或城域w d m 网络的技术可行性。继全光网 络财团之后，美国国防高等研究计划署( d a r p a ) 协同a t & t 、朗讯科技及几 家贝尔电话公司等组成了多波长光网络( m o n e t ) 财团，其目的是验证以长 距离w d m 传输以及波长交叉连接和分插复用技术为基础建立全国范围端到端 波长路由网络的可行性。近年来，高速宽带光网络的研究在国际上己形成热潮， 其中尤以美国、欧洲更为突出。光网络以其良好的透明性、波长路由特性、兼 容性和可扩展性，成为下一代高速( 超高速) 宽带网络的首选，具有很好的前 景。 光网络的发展过程大体可分为三个阶段【2 】： 第一阶段为线性光网络，由全电交换设备和“非交换”光元件组成，主要 技术是采用点到点的w d m 系统，网络节点为电节点，信号在光节点处需光电 转换。 第二阶段为各类“准全光网”，网络节点为光节点或光电混合节点，实现光 透明子网，但边缘节点仍需光电转换t 3 1 。光交换可分成光路光交换和分组光交 换二种类型【4 j 。光路光交换采用光交叉连接器件( o x c s ) 和光分插复用器件 ( o a d m s ，o p t i c a la d da n dd r o pm u l t i p l e x i n g s ) ，能直接在光路上对不同波长 的信号实现上下和交叉连接功能。分组光交换对光器件的性能要求更高，由于 目前光逻辑器件的功能还比较简单，不能完成控制部分复杂的逻辑处理功能， 因此国际上现有的分组光交换单元还要由电信号来控制，即所谓的电控光交换。 第三阶段是光网络的高级阶段，即光子分组交换网络，实现真正的光域交 换。其特征为光控光交换，除本节点外的信号的所有处理均保持在光域内进行。 采用了所有全光网的重要技术，如密集波分复用( d w d m ，d e n s ew a v e l e n g t h d i v i s i o nm u l t i # e x i n g ) 、光时分复用( o t d m ，o p t i c a lt i m ed i v i s i o n m u l t i p l e x i n g ) 、o a d m 、o x c 以及光交换等，并由这些技术构成各种各样规模 的干线网。由于网络对业务透明，可以传输各种业务。 从目前光网络技术的开发状况看，光网络的主要发展趋势为f 5 】： 从光技术的应用程度来看，将不断扩大光透明子网的覆盖范围，最终实 现全光通信网络的理想目标； 从复用方式来看，将向基于光分组的统计复用方式发展； 从交换选路方式来看，将采用光分组交换； 从组网方式来看，将沿着“点到点链、环多环网状网”的方向发展， 网络灵活性将按“静态一半动态动态”的方向发展； 从应用领域来看，光网络将沿着“主干网本地网城域网接入网一用户驻 地网”的次序逐步渗透。 2 浙江工业大学硕士学位论文 1 1 2w d m 光网络技术研究热点 ( 一) 光传送技术 大容量和高速率是w d m 光网络的发展趋势，这里主要分为增加波长信道 数量和扩大全光传送距离两个方面。 ( 1 ) 增加波长信道数量的技术 主要通过增加可用带宽和减小波道间隔。 可用带宽的增加主要取决于光器件，尤其是光放大器。扩展光放大器带宽 的主要技术有以下几种：基于新材料带增益均衡光滤波器的e d f a ；采用 平行配置使用e d f a 的两个增益波段；将局部增益平坦的e d f a 与光纤拉曼放 大器( f r a ) 结合使用；采用拉曼激光放大器；将掺稀土光纤放大器与f r a 进行组合。 减小波道间隔主要取决于光纤的非线性效应，光纤的优化设计能够较好地 克服非线性效应。 ( 2 ) 长距离全光传输技术 主要有三方面：新型光纤，如晶体光纤等：各类补偿技术，如色散补 偿、p m d 补偿等；光编码技术，包括差错控制编码，光分组编码等。 ( 二) 光交换，选路节点技术 主要解决光节点处任意光纤端口之间的光信号交换及选路。带宽粒度可以 是光线路级、波长级、分组级甚至比特级。目前及今后应用的主要是基于w d m 的光网络，主要的网络节点为o a d m 和o x c ，逯常由w d m 复用解复用器、 光交换矩阵、波长转换器和节点管理系统组成。主要完成光路的上下、光层的 带宽管理、光网络的保护、恢复和动态重构等功能。 从功能上看，o x c 、o a d m 都属于光路光交换节点设备，它们完成光纤和 波长级的粗粒度带宽处理，主要应用于目前正准备进入实用的w d m 光网络。 下一步的应用将是分组光交换节点，主要应用于光子分组交换网络，这种光节 点在分组级进行光交换选路，可更加灵活、有效地利用带宽。基于o a d m 的 比特级光交换节点对光器件的要求非常高，其关键技术主要包括光分组产生、 同步、缓存、再生、光分组头重写及分组之间的光功率均衡等。但这些技术对 光器件要求非常高，因此光分组交换节点离实用尚远。 ( 三) 光网络的控制和管理技术 光网络的控制和管理系统是实现光网络的重要组成部分，它通过用于光层 处理的开销通道和光层控制信令与管理信息对光网络进行有效的控制和管理， 如：边缘节点的带宽请求；网络拓扑、带宽资源、路由信息的传递；动态路由 选择和波长分配；网络保护、恢复、重新配置；以及对光设备和光通道进行性 能检测，完成各种管理功能等。 ( 四1 关键光器件技术 3 塑堡三、业盔堂堡主堂鱼笙皇 光网络的发展关键在于开发先进的光器件，其受限因素往往也在光器件。 w d m 光网络中的关键光器件主要有宽带光纤放大器、光开关、波长可调光源、 波长可调探测器、波长可调滤波器、波长转换器件和波长选路和交换器件等几 种。光器件技术与上述各类技术是紧密相连的，有的甚至是包含关系。 w d m 系统中的各类实用光器件目前正形成带有监控手段的模块，且功能 不断增加。目前各大公司正在全力开发以关键器件为主体的光放大中继模块、 光节点模块、补偿元件模块等。在光节点模块中，路由与波长分配技术是极其 关键的。 1 1 3w d m 光网络优化设计 w d m 光网络中的优化设计主要是指路由与波长分配( r w a ，r o u t i n ga n d w a v e l e n g t h a s s i g n m e n t ) 。波长路由光网络属于上述第三代光网络，它是由o x c 与光纤链路组成的任意的拓扑结构，它通过波长进行端到端之间的路由，即建 立源节点到目的节点之间的光通道( l i g h t p a t h ) 。网络的物理拓扑( 光纤链路和 网络节点的组合方式) 往往与节点之间光业务连接形成的逻辑拓扑不一致，如 图1 1 所示，实线和节点组成了物理拓扑，而逻辑拓扑由虚线和节点组成。 考虑到网络单元的功能受到限制( 如网络节点是否具有波长转换功能) ，物 理传输性能( 主要包括：误码率、信噪比、端到端带宽、串扰、光纤线性色散、 非线性效应) 造成一定程度的影响以及网络中实际可以使用的网络资源( 比如 波长和收发机数目) 非常有限，优化光通道的路由与波长分配成为光通道层设 计的核心问题【引。r w a 问题是指给定网络节点之间的业务( 光连接) 矩阵，根 据具体的网络条件为这些光连接选择源和目的节点之间的路由并为其分配相应 的波长，其结果必须在这两者之间形成合理的映射。 图1 1 光网络物理拓扑和逻辑拓扑 r w a 问题在数学上可以描述为一类规划问题，利用网络已知条件，如网络 物理拓扑图、业务矩阵和w d m 传输系统条件，结合波长一致性要求、波长数 限制和网络节点流量守恒等约束条件建立数学模型。得到的模型和多商品流问 题的模型相似，因此是一种非确定型多项式一完全( n p c ，n o n d e t e r m i n i s t i c 塑婆三些盔堂亟主堂丝堡銮 p o l y n o m i a l c o m p l e t e ) 组合优化问题，对于节点数少的网络，可以使用整数线 性规划算法求解，但是当网络规模较大时，只能根据不同的网络条件构造启发 式算法( h e u r i s t i ca l g o r i t h m ) 求解 7 1 。 波长路由( w r ，w a v e l e n g t hr o u t i n g ) 技术与路由和波长分配( r w a ) 技 术是两个不同的概念，二者既有联系又有区别。w d m 网络是由光通道将波长 路由器和端节点相互连接而构成的，而每个链路可支持好多信号格式，但它们 都被限定在波长粒度上。通过网络的信号路径由波长、源信号、网络交换的状 态信息以及选路中的波长改变信息等来共同决定，因而波长路由需要考察许多 方面的问题，包括单个连接的路由计算，拓扑信息的获得和发布，资源状态信 息的发布和可到达信息的发布。当向光网络提出连接请求时，要计算从源节点 通过网络到达宿节点的路由并合理地规划网络波长资源。所以，路由和波长分 配技术是解决波长路由的一个关键方面。 1 2w d m 光网络中r w a 算法技术发展状况 w d m 光网络中的路由问题包括两层含义：一是信令路由技术；二是业务 路由技术。信令路由是为信令消息寻找端到端的或下一条路径的技术，具体地 说就是在控制平面内部的信令通路，它通常通过p 网络的逐跳转发等路由机制 来实现。业务路由是为传送平面的通路连接寻找路径的技术，在光网络中它是 通过一些r w a 算法来实现。信令路由的完成为业务路由的实现提供了所需要 的网络资源和可达信息。 在普通的电层交换网络中，只涉及到为连接请求建立路由的问题。对于基 于波分复用的光层交换网络而言，由于其物理上的特殊性，在给定一个连接请 求之后，不仅需要为之计算路由和建立光通道，还要在全路径上分配波长，这 就是上文所提的r w a 问题。从路由与波长分配策略的角度出发，网络的结构、 业务模型以及网络对路由计算的约束条件都会对解决方案以及算法的设计产生 影响。图1 - 2 全面总结了目前w d m 光网络中r w a 算法技术的发展状况。 浙江工业大学硕士学位论文 图1 - 2w d m 光网络的路由与波长分配算法技术 1 3w d m 光网络的研究方法 由于整个光网络体系的纷繁复杂，所采用的设备和技术之多，使得人们很 难以准确的方式，对整个网络的性能进行精确的分析。就目前而言，所采用的 研究方法主要有以下两种方式1 8 】： 1 、建立试验网，研究某种类型的光网络的特性 然而试验网的规模毕竟很有限，难以探讨复杂网络环境下的路由算法、波 长分配算法的优劣。美国建立了m o n e t ，n t o n c 等光网络试验网；欧洲建立 了o p e n ，p h o t c i n 等试验网；中国也由上海交通大学建立了s h a o n e t 试验 网。但由于搭建一个试验网所需要的代价昂贵，所费时间较长，更改网络结构 困难，所以难以确保所测量的数据是实时的、充分的。因此，当前通过试验网 所能进行的研究还非常有限( 通常试验网被用于研究一些经过充分的仿真试验， 比较成熟的网络类型) 。 2 、采用软件仿真的方式 6 塑望三些盔堂塑主堂焦鲨塞 软件仿真具有速度快，代价低廉，可多次重复，研究范围可控等优势。仿 真内容可以是大到全国性的网络，小到单个节点的性能仿真，可以针对某一种 类型的协议，也可以是解决某个具体问题的算法，可适应的范围非常广泛。因 此采用计算机仿真成了目前网络研究中最主要的手段之一。即使使用搭建试验 网的方式进行研究，在搭建之前也必须经过充分的仿真，尽可能降低投资成本， 避免一些不确定的风险。目前国际上比较知名的光网络仿真软件有v p i 公司的 v p i 系列软件，o p n e t 公司的o p n e tm o d e l e r 软件，l i n u x 系统下的n s 等， 这些软件对于一些比较流行的网络类型作了归纳，是这些网络的规划、设计、 维护和管理的很好的助手。然而对于算法研究者来说，由于所碰到的问题通常 是新的，所建立的模型也是新的，所以自己设计程序来解决相应的问题是很有 必要的。 本文在进行算法比较时采用的是软件仿真的方式，软件平台是v c + + 。 1 4 主要工作和论文内容安排 本论文对w d m 光网络中动态业务下的r w a 问题进行了研究，主要从算 法的目的、性能评价、影响算法的因素以及算法的实现方法等，针对动态业务 模型下的波长路由算法提出了相应的解决方案。并综合应用数学建模、计算机 仿真对所提出的方案进行了详细地分析。论文的主要工作以及各章节的安排如 下： 第一章绪论。对w d m 光网络的发展过程，技术研究热点，以及发展趋势 做了归纳总结，并对w d m 光网络的优化设计以及r w a 算法的技术发展状况 做了归纳论述。 第二章对w d m 光网络动态r w a 问题进行了深入研究，总结前人的研究 成果，给出了w d m 光网络动态r w a 问题的物理模型和数学模型。根据动态 网络中节点是否具有波长转换功能，将动态路由问题分为波长通道路由问题和 虚波长通道路由问题分别进行论述，并分析了两种情况下的阻塞率情况，推导 并给出了阻塞率公式。 第三章对波长转换受限光网络下的动态路由算法进行了研究，通过引入链 路综合代价、路由优化和波长优先级分层图，将三者结合对传统a d m h 算法 进行改进，提出了一种新的动态自适应路由算法( p a d m h ) ，进行了计算机仿 真，结果证明这种算法优于传统算法。 第四章对波长转换非受限光网络下的动态路由算法进行了研究，并引入仿 生学理论一蚁群算法解决动态路由问题。对基础蚁群算法进行了深入研究，在这 基础之上，通过改进寻路中链路综合权重的设置、优化蚁群寻路的原理以及考 虑波长优先级等提出了两种改进型算法，分别为基于流量限制和基于波长优先 塑坚三些盔堂堡主堂垡堡塞 级的算法。进行了计算机仿真，结果证明这类算法优于传统算法。 第五章利用系统仿真原理，参与开发基于v c + + 平台的仿真软件 w r o n r w a l 0 和w r o n - r w a 2 0 ，并获得软件著作权登记。此仿真软件对常 见的算法、改进算法以及新提出的算法进行了实现，能够在统一的业务量模型、 仿真网络上对算法进行比较和分析，而且支持用户在自定义的网络拓扑上运行 软件中包含的算法。该软件为理论分析提供数据支持。作者主要负责路由算法 的实现。 第六章对论文工作做了总结，并对以后可开展的研究工作进行了展望。 浙江工业大学硕士学位论文 第二章w d m 光网络动态路由问题 w d m 光网络与传统网络相比，在物理基础和技术条件上的限制因素不同， 业务应用不同，因此在w d m 光网络中进行波长路由算法的研究有重要意义， 许多w d m 光网络独有的特性与r w a 问题密切相关。本章将重点对这些相关 的因素进行探讨，用数学方法对部分算法模型进行描述。 2 1w d m 光网络的物理模型 图2 - 1 是网络物理结构的一个例子【9 】，虚线内为光传送网。图中有5 个o x c ： a ，b ，c ，d ，e ；6 个具有光接口的电设备：s 。一瓯；6 个将o x c 连接起来的 物理链路：，一k 。一般一条物理链路包含一对光纤供双向使用，有的o x c 间 没有物理链路相连。但更多的情况是一条物理链路包含多根光纤供不同方向的 业务量使用。一根光纤上可采用多个波长。一般情况下，o x c 不直接和电设备 相连，只起光交叉连接作用。 弪鏊 图2 1网络物理结构举例 o x c 可分为无波长变换和有波长变换( 也可以是部分端口有波长变换或波 长变换的范围有限) 两种。无波长变换的o x c 的作用是将一根输入光纤上的 某一波长信号连到另一根输出光纤的同一波长上，即波长是连续的。有波长变 换则是将一根输入光纤上的某一波长信号连到另一根输出光纤的另一波长上。 适当地安排路由和分配波长，可为电设备间建立光路( 1 i g h t p a t h ) 。在一根光纤 上，不能为不同光路分配相同波长。图2 2 是为图2 1 建立的光路例子。将图 2 ，1 的光路连接用图2 2 ( b ) 来表示，称为逻辑结构，也称逻辑拓扑或虚拓扑。 塑望三些盔堂亟主堂鱼堡塞 例如，图2 2 ( a ) 中，节点b 与e 间的光路是经节点中的o x c 转接的，在图 2 2 ( b ) 中，用0 4 表示。图2 - 2 ( b ) 中，0 6 、d 4 、d l 都是中间有o x c 转接 的。d 、0 3 、o ；是直接光路。 这样建立的光路对信号是透明的，即信号可以是任意方式。 实际设计中，一种需求情况是：提出所需建立的光路，为这种光路选取物 理路由并分配相应的波长。例如，图2 2 ( b ) 中提出要建立6 条光路，图2 2 ( a ) 就是一种选路和波长分配方案。 ( a ) 路由和波长分配 逻辑结构 图2 - 2 光路举例 网络向分组化发展，图2 1 中的电设备可以是a t m 交换机或口路由器。 例如，连在端口b 2 的路由器可以通过光路伉和连在端口c 3 的路由器相连。 b 2 到c 3 可有多条路径，d 6 是最近的，也可以经过d 4 - g q 或0 4 - d 5 - d 1 一d 2 连接，但需要路由器转接，即电的多跳连接。a 与b 间没有光路，至少需经c 电跳连接一次。 实际设计中另一种需求情况是：提出各路由器间的所需业务量强度，设计 出逻辑拓扑并为其光路选取物理路由和分配波长。与根据光路需求情况进行设 计相比，增加了要考虑电的多跳。 2 2 动态r w a 问题的数学描述 2 2 1 网络中的节点和边 网络中的节点和边可表示为： v = v l ，v 1 1 ，。) ，1 s i 聆 e = q ，p l p 。) e = v p v g ，1 ，肌，1 - p ，q n ( 2 一1 ) ( 2 2 ) j 0 浙江工业大学硕士学位论文 网络的容量用矢量k ( m ，) 代表，m 是边的维数，即每个边的容量等于光 纤对数目乘以波长数目。 k = ( k ，) ，其中_ j ，是边e ，的容量l j m 。 ( 2 3 ) 源宿节点对定义为其间通信需求大于0 的两个节点。( 通信需求表示为每 个节点对之间所需建立的光路数) 。假设一个光路的容量为1 ，则它的建立需要 在其路由上的每根光纤中占用一个波长。 s 是源和宿节点对的集，数目是j 。 s = v i v 。iv i 和v ，之间的需求大于0 ，1 s i ，j n ) ( 2 4 ) 网络需求( 负载) 用需求矢量d q s ) 来表示，d 的所有元素都不为0 。网 络总的负载三是d 的元素的和。 d = ( z ) ，z = 源宿( 耐) 节点对晓间需求的光路数，j i s 。 ( 2 5 ) 2 2 2 流表示式和路由表示式 在路由问题中，需要为给定的流量负载寻找路由。在流( f l o w ) 表示式中， 基本的变量是每个源宿节点对产生的边上的流。在路由( r o u t i n g ) 表示式中， 需要列举出所有源宿节点对之间的所有路由，然后确定一个路由被使用多少次。 设r = r l , r 2 ，) 是所有可能的路由，它把s 中的每个源宿节点对连接起 来，数目为，( 在密集网络中，每个源宿节点对之间的路由数是随着网络的规 模呈指数增长的) 。 矩阵q 是路由和源宿节点对矩阵( r x s ) ，它确定一个路由与哪个源宿节点 对相关联。矩阵b 是路由和边矩阵( r x m ) ，它确定路由是由哪些边组成。 q = ( g ，。)如= 1 ，如果路由i 和源宿节点对j 相关联 g “= 0 ，其他l i r ，1 ，占 ( 2 6 ) b = ( )b = 1 ，如果边巳是路由i 的一部分 b 。i = 0 ，其他1 i ，l j m ( 2 7 ) 路由的长度是它所包含的边的数目f ，= ，l f ，。 ( 2 8 ) l = l ( 1 ) 流关系式表示路由 路由矩阵x 表示在所有单个弧上的每个源宿节点对引起的通信流的和。 浙江工业大学硕士学位论文 x = o 自) ，其中表示在边上源宿节点对_ j 之间的业务量，有l i m ， l ，j 。 限制条件： 1 ) 流守恒条件( 对网络中任意节点，流出该节点的业务量与流入节点的业务量 的差值等于该节点引入的业务量) ： i d 。，如果v 。是节点对k 的源点 x 止一x 止= d l ，如果v 。是节点对k 的宿点 ( 2 9 ) a 叫 。印 1 0 ，其他 2 ) 容量限制条件( 任意光纤链路容纳的波长通道数量有限) ： h k j ，l j i o 的情况下，g 反而随f 的增加而减少。另外，考虑 到g 是跳步数h 的函数，在f 较大的情况下，g 将和h 呈线性关系，由公式 ( 2 1 8 ) 可知。总之，在1 0 f o o 时，g 随着h 的增加而增加，这表明在规模 较大的网络中，光连接跳步数较大的情况下，虚拟光通道网络具有更大的灵活 性。 2 5 2p 与干扰连接有关时光通道的长度对阻塞率的影响 2 5 1 节的分析建立在p 与干扰连接无关的基础上。然而在实际情况中，只 要在图2 - 9 任意一段的任意一个波长存在干扰连接，各条边上的各个波长的占 有概率就会发生变化。本节对存在干扰连接的情况进行讨论。 继续采用图2 - 9 的网络，在节点f ，设旯为任意一条边上任意一个波长，干 扰连接可以进入或离开该光通道。为方便分析，做如下假设： 1 ) 同一条边上不同波长上的事件统计独立； 2 ) 不同边上同一波长上的事件统计独立i 3 ) 五在跳步数0 ( h o p 0 ：a 到节点1 ) 上被干扰的概率为0 ； 4 ) a 在i 条边上被干扰连接的占用只与兄在i 一1 条边上的状态有关，与别 的边上的状态无关； 5 ) 如果五在第i 一1 条边上被占用，那么占用旯的干扰连接在节点i 离开该 光通道的概率为异。如果干扰连接在节点i 不离开这条光通路，那么继续占用 丑 堑堑王些盔堂亟主堂笪笙塞 第i 条边上的五。没有干扰的连接在第h + 1 个节点离开； 6 ) 如果五在第i 1 条边上未被占用，那么一条干扰连接在节点i 进入这条 光通道并占用丑的概率为只，没有干扰的连接在第日+ 1 个节点进入该条光通 道。 7 ) 如果五在第i 一1 条边上被启用，而占用它的干扰连接在节点i 离开，同 时另一条干扰连接进入，并在第i 条边上占用五的概率为只。 由这些条件我们可以推导出： p ( a 在第i 条边被干扰连接占用l 旯在第f l 条边未被占用) = 只 ( 2 1 9 ) p ( 五在第f 条边被干扰连接占用【a 在第i 一1 条边被占用) = ( 1 一异) + 只# ( 2 2 0 ) a 在第i 条边被占用的概率为： 只= ( 1 一c + # 只) 只一1 + 只( 1 一p 一。) = p 1 一 1 一( 只+ 只一只只) 】1 ) ( 2 2 1 ) 其中p = 只，( 只+ 弓一只日) 。当建立的连接为虚通道时，得到下列概率： ，( 第i 条边上所有f 个波长全被占用) = 只7 ( 2 - 2 2 ) p ( 第i 条边上所有f 个波长全被占用i 第i 一1 条边上所有f 个波长全被占用