（信号与信息处理专业论文）业务疏导算法在光城域网状网中的研究.pdf

中文摘要 中文摘要 随着网络业务量的爆炸性增长以及高性能的光网络设备( 如光交叉连接器 o x c 、光分插复用器o a d m ) 的出现，波分复用技术成为下一代骨干网络的核心 技术。在光网络中的每个波长可以以相当高的速率传输( 如o c 一4 8 、o c 1 9 2 、 o c 7 6 8 ，对应的速度为2 5 g b s 、1 0 g b s 、4 0 g b s ) ，然而在实际应用中，每个 业务的通信速率往往远远低于一个波长的最高传输速率，例如o c l 、o c 3 、 o c 1 2 ( 5 1 8 4 m b s 、1 5 5 5 2 m b ，s 、6 2 2 0 8 m b s ) 。显然，为每个业务提供一个专用 波长，资源利用率低且不经济。因此在w d m 光网络中，需要研究如何有效地 为这些低速业务建立连接。疏导技术可解决这个问题。 城域网是数据骨干网和长途电话网在城域范围内的延伸和覆盖，承担着集团 用户、商用大楼、智能小区等的业务接入和电路出租业务。城域网将是运营收入 的主要来源。建设城域网、实现城市信息化，无疑是全民信息化的重点内容和前 期目标。随着宽带业务需求发展和潜在的巨额利润，更多的网络运营商和业务提 供商，将进入这一领域。 本论文主要研究w d m 城域网状网中的业务量疏导问题，其中主要以静态业 务量为分析对象，研究静态业务量疏导可用于城域w d m 业务量疏导网络的规划 设计以及w d m 网络中较大周期的虚拓扑重配置应用。本文首先介绍了w d m 光 网络以及光城域嘲的基本理论和发展动向。然后介绍了基于免疫原理的自适应算 法。最后着重介绍如何利用自适应免疫算法解决在网络波长数和收发器数限制的 情况下，最大化网络的吞吐量，同时兼顾业务连接端到端的时延的业务疏导问题。 本论文的重点是把自适应免疫算法运用到虚拓扑的优化中，通过算法逐代的“进 化”虚拓扑，从而在若干代以后得到整个问题的最优解或近似最优解。自适应免 疫算法收敛速度快，具有良好的全局寻优和局部求精能力，通过与m r u 算法和 m s t 算法的比较，我们发现，自适应免疫算法能充分利用网络资源，提高网络 吞吐量。 关键词：w d m 光城域网；业务量疏导；虚拓扑；自适应免疫算法 三兰三竺垒兰三兰堡! ：兰堡篁兰 a b s t r a c t w i t hm ee x p l o s i v ei n c r e a s ei nn e t w o r kt r a 历ca n dm ee m e 略e n c eo fh i g h p e r f o m l 柚c eo p t i c a ln e t w o r ke q u i p m e n t ，s u c ha so p t i c a lc r o s s c o 皿e c t ( o x c ) 卸d o p t i c a la d d d m pm u l t i p l e x e r ( o a 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 ) 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 fn 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 sa i l d m e t r on e t w o r k s i no p t i c a ln e t w o r k ，e v e r yw a v e l e n g mc a nb eo p e r a t c da tv e r y1 1 i 曲 s p e e d ，e g o c 一4 8 ，o c 一1 9 2a n d0 c 一7 6 8 ( t h ec o r r e s p o n d i n gr a t e sa r e2 5 g b s ， 10 g b sa n d4 0 g b s ，r e s p e c t i v e l y ) h o w e v e ri na c t u a i n e t w o r k s ，t h e r ei sah u g e b a n d w i d t hg a pb c t w e e nt h ec a p a c i t yo fa w a v e l e n 舀ha n dt h eb a r i d w i d t hr e q u i r e db y l o w i a t et r a 伍cs t r e a m s ，e g ，o c l ，o c 一3a n d0 c 一1 2 ( t h ec o r r c s p o n d i n gr a t e sa r e 51 8 4 m b s ，1 5 5 5 2 m b sa n d6 2 2 0 8 m b s ，r e s p e c t i v e l y ) ，t ba c c o m m o d a t es u c hk i n do f i o w r a t et r a f h cs t r e a m s ( o rc a l l e dc o n n e c t i o n s ) w i t ho n el i g h t p a mw i hl e a dt o i n e 瓶c i e n tr e s o u r c eu t i l i z a t i o n s oi ti sn e c e s s a r yt oi n v e s t i g a t eh o wt oe 伍c i e n t l ys e t u pc o 加e c c i o n s 南rt h e s et r a 衔cs t r e a m so nw d m 叩t i c a 】n e t w o r k s t h 衢cg m o m i n g c a nm e e tt h i sp r o b l e m m e t r on e t w o r ki se x t e n s i b i l i t ya n do v e r c a s tb yd a t ab a c k b o n en e t w o r ka n dl o n g _ d i s t a i l c et d e p h o n en e t w o r ki nm e t r oa r e a ，i th a so ni t ss h o u l d e r s 叩e r a t i o na c c e s s a n dt e l e 曲o n e l e l l do p e r a t i o no ng r o u pu sc r b u s i n e s sb u i l d i n g ，i n t e l l i g e n th o u s ea n d s oo n m c t mn e t w o r kw i l ib e c o m em a i ns o u r c eo no p e r a t i o ne a m i n g i ti sn o td o u b t t h a t b u i l d i n gm e t mn e t w o r k ，a c h i e v i n gi n f o n n a t i o n c i t yi s t h ek e yc o l l t e n ta 1 1 d p m p h a s eg o a l o ni n f o 吼a t i o n c i v i l w i t ht h e d e v e l o p m e n t d e l l l a n do nb r o a d b a n d w i d ma n dp o t e n t i a lh u g ep r o f i t ，m o r ca n dm o r en e t w o r k 叩e r a t o ra n do p e 础o n o p e r a t o rw i l lc o m ei n t ot h i sa r e a n i sa r t i c l em a i n l ys t u d yt m 伍cg r o o m i n gp r o b l e mw h i d lf o c u s 。do ns t a t i ct m 街c g r o o m i n go nw d m m e t r o m e s hn e t w o r k s t a t i ct r a f f i c 霉d o m i n gr e s e a r c hc a n u s ef o r l a y o u td e s i 毛面n go fw d m 黟o o m i n gn e t w o r k ，o rr e d e s i g n i n go fn e m o r kv h t u a l t o p o l o g ya f t e ral o n gp e r i o d f i r s tw ei n 仃o d u c em eb a s i cm e o 叫a 1 1 dd e v e l o p m e n to n w d m o 州c a ln 酣0 r ka n dm e 锄o p c i c a ln e “v o r k ，a n dt h 锄i n t 砌u c et h ea d 印c i v e h i m m u n ee v o l u t i o n a r ya l g o r i m m ( a i e a ) a t l a s ti n t m d u c eh o wt ou s ea i e a t os o l v e t r a 伍cg r o o m i n gp f o b l e mo nm a x i m i z i n gn e t w o r km m u 曲p u ta sm ef i r s to p t i m a l o b j e c t i v ea n dm i n j m i z i n ge n d t o e n dd e l a ya st h es e c o n do p t i m a lo b j e c t i v ew i t hm e 1 i m i t so fw a v d e n g t hn u m b e rp e rf i b e r8 i l dt r a n s c e i v e r sn u m b e rp e rn o d e t h ek e yo f t h i sa r t i c l ei su s i n ga i e at oo p t i m i z ev i r m a lt o p o l o g y t og e t l eo p t i m a ls o l u t i o nb y e v o l v e dv i r t u a l t o p o l o g yg e n e r a t i o na n dg e n e r a t i o n a i e ac o n v e r g e sq u i c k l y ，a n dh a s s a t i s f a c t o r yc a p a b i i i t i e so f 百o b a ia 【l dl o c a l r e s e a r c h w h i l ec o m p 耐n g w i t hm r ua n d m st w ef o u n di tc a nm a k em en e t w o r kh a v eh i g hu t i l i z a t i o na n dg o o dt h r o u g h p u t k e y w o r d s ：w d mo p t i c a lm e t r o n e t w o r k ；t m m cg m o m i n g ；v i r t u a l t o p o l o g y ；a d 印t i v e i m m u n ee v o l u t i o n a r ya l g o n t h m ( a i e a ) i i i 第一章绪论 第一章绪论 在光网络中的每个波长可以以相当高的速率传输( 如o c 一4 8 、o c 一1 9 2 、 0 c 一7 6 8 ，对应的速度为2 5 g b s 、1 0 g b s 、4 0 g b s ) ，然而在实际应用中，每个 业务的通信速率往往远远低于一个波长的最高传输速率，例如o c 1 、o c 3 、 o c 1 2 ( 5 1 8 4 m b s 、1 5 5 5 2 m b s 、6 2 2 0 8 m b s ) 。为每个业务提供一个专用波长， 资源利用率低且不经济。因此在w d m 光网络中，需要研究如何有效地为这些 低速业务建立连接。为了便于读者对后续研究有更好的理解，本章首先介绍 w d m 光网络发展情况，接着介绍解决w d m 光网络中高带宽光路和低速业务 问的优化设计技术一业务量疏导以及业务量疏导的研究现状，最后简单介绍本文 的主要贡献和内容安排。 1 1 w d m 光网络发展概述 1 1 1 波分复用技术( w d m ) 随着个人计算机和国际互联网络( i n t e m e t ) 的进一步普及，以及电子商务、 会议r 乜视、远程教育、远程医疗、视频点播等多种宽带业务的f 1 益兴起，基于i p 的数据业务量得到爆炸式增长。囡此这需要对传送网络的整体构架、技术模式、 组网方式以及业务节点的实现方式等方砥进行改造，以满足网络业务这种指数增 长的需求卜”。 为了能够满足列带宽需求呈指数增长的需要，人们开发出了波分复用 ( w a v e l e n 晷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 技术就是为了充分利用单模光纤低损耗区带来的巨大带宽资源，根据每一信道光 波频率的( 或波长) 不同，将光纤的低损耗窗口划分为若干个信道，把光波作为 信道的载波，在发送端采用波分复用器( 合波器) 将不同规定波长的信号光载波 合并起来送入一根光纤进行传输；在接收端，再用波分复用器( 分波器) 将这些 不同波长承载不同信号的光载波进行分离的一种复用方式。波分复用原理如下图 l 一1 所示【3 】。 广东工业大学工学硕士学位论文 光发射机 光中继放大 光接收机 图l 一1 波分复用原理图 f i g 1 一lt h ee l e m e n to f 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 1 1 2 从点到点传输系统到w d m 光网络 近几年由于市场的驱动和技术上的重大突破，波分复用系统发展十分迅猛： l u c e n t 率先推出8 2 5 g b i “s 系统；而后c i e n a 推出了1 6 2 5 g b i t s 系统。目 前1 6 n i t s 的w d m 系统已经商用，l u c e n t 和n o t e l 两公司提供的该类产品都 采用1 6 0 1 0 g b i t s 方案结构；n e c 和a 1 c a t e l 公司的w d m 分别实现了总量 为1 0 9 n i t s ( 2 7 3 4 0 g b i t s ) 和l o 2 t b i t s ( 2 5 6 4 0 g b i “s ) 的传输系统。西门 子的研究人员同前宣布1 6 0 g ( 即使用光时分复用技术把不同的l o g 信道集成 到一个波长上) 技术将在未来两年内获得大规模应用t n ”。 普通的点到点波分复用通信系统尽管有巨大的传输容量，但只是提供了原始 的传输带宽。为了将传统的点到点w d m 所提供的巨大原始带宽转化为实际组 网可以灵活应用的带宽，需要在传输节点处引入灵活的光节点实现光层联网，构 筑w d m 光传送网络。波分复用技术不仅仅可以充分利用光纤中的带宽，而且其 多波长的特性还具有光通道直接联网的优势，为进一步组成以光予交换为交换体 的多波长光纤网络提供了基础】。最常用的光网络节点主要有用于网间交叉连接 的光交叉连接器o x c 、能够提供本地业务上路和下路( a d d d r o p ) 功能的光分 插复用器o a d m ( 如图1 2 所示) 。 a d d a ) 光分插复用器o a d mb ) 光交叉连接器o x c 图l 一2o a d m ，0 x c 原理图 f i g 1 21 1 l ee l c r n e n to f o a d m ，o x c 2 l 2 n 第一章绪论 o x c 的功能类似s d h 网络中的数字交叉连接器( d x c ) ，一个波长信道上 的信号直接交换到出口光纤的相应波长上去( 如果没有使用波长变化器时，出口、 入口波长必须相同；如果使用了波长变换器，出口、入口波长可以不同) 。o a d m 节点的功能也类似于s d h 网络中的分插复用器( a d m ) ，但也是直接以光信号 作为操作对象。o a d m 节点只需要选定具有本地业务的波长上下路，而其它波 长无阻塞地通过网络节点。由于具有灵活疏导能力的o x c 和o a d m 可以将 不在本地下路的大量业务从光层旁路掉，因此不仅减轻了网络节点所要处理的业 务量，降低了对网络节点规模的要求，而且也降低了网络节点的成本。由于光交 叉连接器o x c 、光分插复用器o a d m 等技术的不断进步和成熟，使得光网络 组网方式从点到点传输系统向w d m 联网的光传送网络发展m 一。l 。 1 1 3w d m 光传输技术向城域网渗透 城域网是跨接在接入网与广域骨干网之间实现业务的本地分流和向长途骨 干网的汇聚的网络部分。随着经济的发展，电信新业务不断涌现，带宽需求急剧 膨胀，人们开始考虑在城域网中采用w d m 技术。近几年，国际上儿大研究光通 信的公司( 如l u c e l l t ，a 1 c a t e l 等) 都在这方面作了一定的研究并提出了解决方 案和研制了相关的产品。在城域网中应用w d m 技术，不仅可以解决光纤短缺的 问题，还可以给网络提供更多的功能和更大的灵活性。w d m 系统为城域网提供 了一个通用的光层传输平台，能承载各种不同的业务，能提供以波长为基础的业 务，特别适应城域网中业务类型多的特点。同时，w d m 技术还能扩大网络的服 务范围和改进服务质量。另外，w d m 具有很强的可配置性，这对于业务种类不 确定的城域网来说，增加了刚络的可扩展性和可重构性。w d m 的一个最大优点 是初期成本较低，便于获得投资回报”，。 1 2w d m 光网络中的业务疏导问题 1 2 1 疏导技术 在w d m 光网络中，为了充分利用带宽，一个波长上传输的通信速率常较高， 例如o c 4 8 、0 c 1 9 2 、o c 7 6 8 ( 对应的速度为2 5 g b ，s 、1 0 g b s 、4 0 g b ，s ) 。然 广东工业大学工学硕士学位论文 而在实际应用中，每个业务的通信速率与一个波长上的可通速率相比常是较低 的，例如o c 一1 、o c 3 、o c 1 2 ( 5 1 8 4 m b s 、1 5 5 5 2 m b s 、6 2 2 0 8 m b s ) 。显然， 为每个低速业务提供一个专用波长，资源利用率低且不经济。并且由于光纤中波 长数目的限制、网络节点中光收发器数目的限制( 一个光路的建立需要在其两个 终点各使用一个光收发器) 等，不可能为每个业务连接建立端到端的独立光路连 接。因此为了降低网络建设成本和运营成本，提高网络性能，需要为这些低速业 务有效地建立端到端的连接。疏导( g r o o m i n g ) 技术可以解决这个问题。 在光网络中不同的域可以使用不同复用技术实现疏导h a 卅： ( 1 ) 空分复用( s p a c e d i v i s i o nm u l t i p l e x i n g ，s d m ) 技术：将物理空间分区以 达到提高传输系统的容量。例如，将多根光纤捆绑到一根光缆上，或者多个光缆 作为一个链路连接网络中相邻两节点。 ( 2 ) 频分复用( 舶q u e n c y - d i v i s i o nm u l t i p l e x i n g ，f d m ) 技术：将频谱分成不 重叠的一系列独立的通道。光网络中的波分复用w d m 或者密集波分复用 d w d m 技术即是采用了f d m 技术。 ( 3 ) 时分复用( t i m e d i v i s i o nm u l t i p l e x i n g ，t d m ) 技术：在时域内将带宽分 成固定长度的时隙( s l o t ) 。使用t d m 技术，多路信号只要在时间上不重叠可 以共享一个波长。 ( 4 ) 动态统计复用技术：在i p ，m p l so v e r w d m 的体系结构巾，一个w d m 波长通道可以被多个i p 业务流通过“虚电路”方式共享。 在w d m 光网络中业务量疏导( t r a f f i cg r o o m i n g ) 技术是指利用t d m 技术 有效地将低速业务流汇聚到高速的波长通道光路中传输。 1 2 2 业务量疏导定义 业务量疏导问题可以如此描述【】0 】：给定一个网络配置，包括物理链路、每个 网络节点的光收发器数目、每根光纤的波长数目以及波长容量，业务量疏导就是 为一组具有各种低速带宽粒度的业务连接请求建立光路以有效地安排下这些连 接请求，同时优化网络的性能。业务量疏导就是将低速业务连接( 或者业务流) 汇聚到一个波长上传输，低速业务流可以通过一条光路到达目的网络节点( 单跳 业务量疏导，s i n 西e h o pt r a m cg r o o m i n g ) ，也可以通过多跳光路到达目的( 多跳 4 第一章绪论 业务量疏导，m u l t i _ h o pt r a m cg r o o m i n g ) 。 低速业务连接请求可以是静态的，可以是动态的。所谓静态就是已知所有低 速业务连接请求( 即各个节点对之间的各种颗粒的连接请求) ，这些业务连接请 求构成业务需求矩阵。所谓动态就是业务连接请求动态到达，动态离去。业务量 疏导根据业务静态与否可以分为：静态业务量疏导和动态业务量疏导两类一。 静态业务量疏导是预先给出所有低速业务连接需求，计算路由和分配波长。 这种计算可以是离线( o 雄1 i n e ) 的，即不需实时计算。静态业务量疏导是一个特 殊的虚拓扑设计问题，即为已知的低速业务量建立合理的光路，形成最优的逻辑 拓扑( 虚拓扑) ，疏导各个业务连接。它所考虑的是如何从全局优化的角度来为所 有连接需求计算路由。其优化目标是在给定的低速业务量需求下： ( 1 ) 使网络成本最小，减少网络中电终端设备如a d m 数目或者光端口设备 如o x c 数目，也可以是最小化光路数目； ( 2 ) 给定光收发器数目限制、光纤波长数日限制，以达到最大化整个网络的 吞吐量。 通常把静态业务量疏导分为三个子问题加以解决：a 、虚拓扑构建子问题， 确定物理拓扑上需要建立的一组光路需求r ( 光路就是指两个节点例的一条全 光通道，它可能经过一条或者多条光纤链路。该光路只在源宿节点分别进行电光、 光电转换) ；b 、光路路卜与波长分配( r o u t i n ga n d w a v e l e n g m a s s i 口m e n t ，r w a ) 子问题，为前面的光路需求r 解决相应的r w a 问题；c 、低速业务流选路子 问题( 疏导子问题) ，在虚拓扑上实现低速业务的选路。 在动态业务量疏导中，低速业务连接请求随机、顺序到达网络，要求进行实 时疏导、路由与波长分配( g m o m i n g r o u t i n ga n d w a v e l e n g ma s s i g m n c n t ，g r w a ) 计算，但是一个连接维持一段有限时问后又被拆除。动念业务量疏导目标一般都 是有效地选择疏导路由和合理分配网络资源，以使业务连接建立的阻塞率最低。 1 2 3 业务量疏导研究现状 近几年来业务量疏导作为光网络的一项关键技术已经引起了业界的广泛关 注与研究。由于环网具有很强的自愈能力，很多网络是采用环形结构来组网的， 前几年业务量疏导研究主要基于s d h ，w d m 环网w 】。文献 1 1 】证明了环网中的 广东工业大学工学硕士学位论文 业务量疏导问题为n p 完全问题，为单集线器环提出了优化算法，减少电a d m 设备。文献 1 5 】通过把波分复用环中的业务疏导问题归结为组合优化问题，提出 了一种基于遗传算法的业务疏导算法。 近一年来，由于网状结构能够提供快速和有效的容量配爱，良好的抗毁能力 现已成为长距离骨干网的主要组网方式，光城域网也开始由环形网向网状网过 渡。网状网中的业务量疏导成为关注的热点一】。山于虚拓扑设计和r 、a 问题 都是n p 完全问题，光网络中业务量疏导是一个n p 完全问题，因此一般采用 一些启发式算法加以解决。文献 1 6 】研究了逻辑拓扑上的业务量疏导问题，首先 提出了一个线性规划模型解决网状网中的静态业务量疏导问题，接着提出一个启 发式算法最小化光收发器数日。文献 1 7 】提出了在w d m 网状网中支持业务量 疏导的两种节点结构模型，并使用线性规划解决静态业务量疏导问题，并提出两 个以最大化网络吞吐量为目标的启发式算法，通过与线性规划方案所得结果进行 比较，评估了启发式算法的性能。文献 1 8 1 9 】分别对动态的业务量疏导问题进 行了研究。 1 3 本论文的主要贡献和内容安排 本文主要对自适应免疫算法用于w d m 光城域网状网的静态业务量疏导这一 领域进行深入研究。利用自适应免疫算法，定义每个网络结构中的虚拓扑结构为 免疫系统中带有独特受体细胞，将网络容纳的业务量与业务矩阵的总业务量的比 值作为细胞亲和力程度( 适应度) ，通过模仿免疫系统的进化原理对其随机产生 的一系列虚拓扑进行优化优化，最终产生较优的虚拓扑结构，使其能容纳更多的 业务量。通过自适应免疫算法，我们不仅证明了运用自适应免疫算法处理业务量 疏导问题的可行性而且证明了运用此算法可达到更好的网络吞吐量。 本文的内容安排如下： 第二章介绍了光城域网的基本组成和发展方向以及光城域网状网的业务量 疏导问题：第三章对本文采用的自适应免疫算法的原理和基本步骤进行介绍；第 四章详细介绍如何利用自适应免疫算法对城域网状网的业务量进行疏导。第五章 对此算法产生的结果进行分析，并做出结论。最后是全文总结。 第二章光城域网状网的业务量疏导 第二章光城域网状网的业务量疏导 我国城市地区经济发达，各类商业用户及普通用户密集，既是传统话音和数 据业务的主要消费集中地，也是宽带业务需求急剧增长的地方。城域网是数据骨 干网和长途电话网在城域范围内的延伸和覆盖，承担着集团用户、商用大楼、智 能小区等的业务接入和电路出租业务。城域网将是运营收入的主要来源。建设城 域网、实现城市信息化，无疑是全民信息化的重点内容和前期目标。随着宽带业 务需求发展和潜在的巨额利润，更多的网络运营商和业务提供商，将进入这一领 域【2 。m 2 “。 本章首先介绍了基于w d m 技术的光城域网的基本概念，然后分析了光城域 网状网的业务疏导问题，并提出了本文对此问题的研究目标和方法。 2 1 基于w d m 技术的光城域网络 2 1 1 城域光网络 城域网( m e t m p o l i t a na r e an c t 、r k ，m a n ) 的概念源自于数据通信。随着 数据通信的发展，根据网络覆盖的地理范围的大小，网络被分为局域网( l a n ) 、 城域例( m a n ) 、广域网( w a n ) ，可以类比于电话通信中的p b x 网、市话网、 长话网。如图2 一l 所示： 接入网：星型城域网：环形骨干网：网孔型 ： 图2 一l 城域网络的分级 f i g 2 一lk i y e r so f m a n 广东工业大学工学硕士学位论文 城域网的概念是在2 0 世纪8 0 年代后期引出的。城域网有三个特性： ( 1 ) 覆盖区域比校园网大、比广域网小； ( 2 ) 连接两个或两个以上的局域网； ( 3 ) 通常覆盖整个城区及郊区。 根据美国i e e e 8 0 2 局域网标准委员会的最初定义，城域网是以光纤为通信媒 体，能提供高速率，支持数据、话音和图形的综合业务传输，在跨度为5 0 1 0 0 k m 的城市覆盖范围内实现高速带宽传输的数据通信网络。虽然，城域网开始是与 局域网相对应的计算机网络概念，指的是城域范围的计算机网络，但是将其延伸 到整个通信网络后，则泛指运营商在城市及郊区范围内提供多种业务的所有网 络，它是以宽带光传输为开发平台，通过各类网关实现话音、数据、图像、多媒 体、i p 接入和各种增值业务及智能业务，并与各运营商长途网和p s t n 互通的本 地综合业务网络口“。 城域网处于骨干网络的边缘会聚节点，主要功能是进行本地业务的接入、会 聚、传输和交换，同时面向骨干网会聚和吸收业务量。城域网是一种主要面向企 事业用户的，最大可覆盖城市及郊区范围的，可提供丰富业务和支持多种通用协 议的公用网，实际是一种带有某些广域特点的本地应用型公用网络，可以说城域 网的关键特性是公用多业务网，从而带来一系列有别于其他网络的特点。 城域网既不同于局域网，又不同于广域网。城域网与广域网( 长途网) 的主 要区别首先是容量，广域网或长途网注重传输容量，而城域网注重交换容量；其 次是覆盖距离的缩小，典型广域网的传输距离可达数千里；再有是支持的客户层 信号不同，广域网目前只支持s d h ，而城域网需要支持各种客户信号：最后是 容许的成本不同，广域网的成本可由成千上万的大量用户共享，因而可以容许较 高的成本，而城域网不行。特别是城域网的成本关键是节点，而非线路，而骨干 网恰好相反。城域网与局域网的主要区别首先是网络性质的不同，局域网是企事 业专用网，而城域网是面向公用网应用和多用户环境的；其次是传输距离的扩展， 典型局域网的传输距离为数公里，而城域网可扩展到5 0 1 5 0 k m ；最后是业务范 围的扩展，典型局域网通常主要提供数据业务，而城域网的业务范围不仅有数据， 还有话音和图像，是全业务网络。 在点到点线性w d m 系统广泛应用于骨干网后，适用于城域网的w d m 系统 第二章光城域网状网的业务量疏导 正在蓬勃发展。在城域网中应用w d m 技术，不仅可以解决光纤短缺问题，还可 以给网络提供更多的功能和更大的灵活性。w d m 系统为城域网提供了一个通用 的光层传输平台，能承载各种不同的业务，特别适应城域网中业务类型多的特点， 同时w d m 技术还能扩大网络的服务范围和改进服务质量。另外w d m 具有很强 的可配置性，这对于业务种类不确定的城域网来说，增加了网络的可扩展性和可 重构性。 2 1 2 城域光网络的基本结构 城域光网络可以分为核心层、汇聚层和接入层，其网络结构如图2 2 所示。 其中，核心层完成整个网络的高速信息交互和与省际传输网的互联互通，提供大 容量的业务调度能力和多业务传输能力；汇聚层负责汇集分散的接入点，完成一 定区域内业务的汇聚和疏导，提供强大的业务汇聚能力，使网络具有良好的可扩 展性；接入层主要完成各种类型用户和业务的接入。 图2 2 城域光网络的基本组网结构 f i g 2 2 t h e b a s i c 6 锄e o f o p t i c a l m a n 9 广东工业人学工学硕士学位论文 2 1 3 城域光网络的拓扑结构 通俗的说，拓扑就是网络的形状。任何通信网络都存在两种拓扑结构，那就 是物理拓扑和虚拓扑( 也称逻辑拓扑) 。其中物理拓扑表征网络节点的物理结构； 虚拓扑表征网络节点的业务分布情况o ，。 物理拓扑结构 网络的物理拓扑就是网络节点的物理连接关系，从组成上讲，它是网络节点 与光缆链路的集合。在波分复用技术发展的早期，点到点的连接是唯一的应用方 式。随着节点技术的发展，w d m 组网技术得到了人们的重视。光分插复用器 ( o a d m ) 以及光交叉连接器( o x c ) 设备的出现使各种物理拓扑在光网络中 的实现成为可能。除简单的点到点的连接方式外，基本的物理拓扑有以下几种， 线形、星形、环形、树形和网状形。如图2 3 所示。 线形星形环形树形 网状形 图2 3 光网络基本物理拓扑结构 f i g 2 3t h eb a s i cp h ：，s i c a lt o p o l o g yo f o p t i c a ln e t w o i k 目前在城域数据业务中的变化捉摸不定，主要是因为由用户应用驱动的要求 一直在变。数据需求不断超过大多数的f 占计，地理覆盖面也不断扩大。这促使业 务提供商寻找解决方案，好让它们基于快速变化的用户数量和业务需求来开设或 扩大他们的服务，甚至网络设施。因此，网络物理拓扑的灵活性就成了一个重要 的要求，网络物理拓扑的任何限制都是不希望的。目前城域网的物理拓扑大多是 基于s o n e t s d h 环的。但近年来运营商和制造商对w d m 网状网都十分关注， 因为它有很强的波长交换一选路机制。光交叉连接( o x c ) 是非常灵活的网元， 同时具有点到点和环插分的功能。网状网光层选路能更好的适配2 层和3 层的选 路策略( 如i p 和a t m 等) 。事实上，网状网连接的资源配置比基于环的选路更 加有效。网状网拓扑结构几乎不需要仔细的规划，业务提供商可以按照需要来逐 渐扩大他们的网络基础设施，从而降低建设与运行费用。 综上而述，网状城域网由于其具有良好的可移植性和可扩展性，配置速度快， 0 第二章光城域网状网的业务量疏导 容量利用率高，具有网络恢复功能和运营成本低等特点正逐渐使城域网由环形网 向网状网过渡。 虚拓扑结构 网络的虚拓扑就是网络节点的逻辑连接关系，从组成上讲，它是网络节点与 光路( 光路就是指两个节点问的一条全光通道，它可能经过一条或者多条光纤链 路。该光路只在源宿节点分别进行电光、光电转换) 的集合，比较常见的有星形、 环形、网状形。如图2 4 所示( 一个双向箭头代表两条光路) 。 图2 4 光网络基本虚拓扑结构 f i g 2 4t h eb a s i cv i r t u a lt o p o l o g yo f o p t i c a ln e t w o r k 在城域环形网的物理拓扑结构中，其虚拓扑结构一般为星形( 单星或双星) ， 在这种结构中，只有存在物理连接的节点之问才有业务联系。这样，没有物理连 接的节点之间的通信将要通过所有中问节点的中转才能实现。此种拓扑很大程度 上丧失了全光通信网络的灵活性。在城域网状嘲的物理拓扑结构中，其虚拓扑结 构为网状形，这种虚拓扑结构有很强的生存能力，这也是本文要采用的虚拓扑结 构。 2 2 光城域网状网业务量疏导问题分析 如上一章所述，在w d m 光网络中，为了充分利用带宽，一个波长上传输的 通信速率常较高，然而在实际应用中，每个业务的通信速率与一个波长上的可通 速率相比常是较低的，如何有效的为低速业务流建立连接是w d m 骨干网和城域 网都要解决的问题。在本文中我们主要对光城域网状网中的业务量疏导问题进行 研究。 广东_ t 业大学工学硕士学位论文 2 2 1 研究对象 本文研究的对象是具有业务疏导能力的光城域网状网，为此我们可以构建一 个网状物理拓扑结构，在光城域网状网拓扑结构的研究中，通常采用n s f n e t 的t 1 骨干网络的物理拓扑结构作为分析对象”。本文以该物理拓扑结构作为城 域网状物理拓扑进行研究，一方面由于该拓扑结构具有较为详细的结构数据，另 一方面也有利于对本研究的结果进行比较。n s f n e t 的t l 骨干网络包含了1 4 个节点2 2 条链路。如下图2 5 所示： 2 图2 5n s f n e t 的物理拓扑结构 f j g 2 5t h ep h y s i c a lt o p o l o g yo f n s f n e t 在业务量疏导问题分析中，为了实现各种业务连接请求，必须在各网络节点 中先建立光路( 光路就是指两个节点问的一条全光通道，它可能经过一条或者多 条光纤链路。该光路只在源宿节点分别进行电光、光电转换) 。一组光路的集合 构成了网络的虚拓扑结构。一个业务连接请求可能要经过一条或多条光路传输。 w d m 网络节点必须具备两个主要功能：( 1 ) 波长路由功能( w a v d e n 舀hr o u t i n g ) ； ( z ) 本地上下路功能( l o c a la d d d r o p ) 。本文研究采用的网络节点的结构如图2 6 所示。网络节点主要由波长交换矩阵和业务疏导矩阵组成，t 和r 分别为节 点的发射器阵列和接收器阵列。非本地业务可以直接通过波长交换矩阵直接交换 到输出端口，而具有本地业务上下的波长( 图2 6 中粗线部分) 通过光收发器 进入到疏导矩阵中处理( 将本地低速业务流复接入波长或将波长中低速业务从波 长中提取出来) ，在此网络节点可以上下路的波长数目受限于光收发器的数目r 第二章光城域网状网的业务量疏导 和t 【 。 光 2 2 2 研究目标 低速二下业务流 图2 6 网络节点结构图 f i g 2 6t h es t r u c t u r eo f n e t w o r kn o d e 本文的研究目标是特定的网络拓扑条件下( 节点数，链路数) ，给定业务量 连接矩阵，在提供的有限的网络资源内满足最大化网络的吞i j 土量。 2 2 3 研究的方法 近年来，免疫算法得到了长远的发展，在机器学习、过程控制、多峰函数优 化、模式识别、数据分析等方面都有应用1 2 5 。】。本文利用此算法来解决网状网中 的业务量疏导问题。主要利用免疫算法进行网状网的虚拓扑结构设计，使其能满 足网络得最大吞吐量。 在本文中，首先在所给的限制条件下随机构建若干虚拓扑结构，然后分别对 这若干个虚拓扑结构中的每个虚结构分别进行分析( 根据虚拓扑结构为每一业务 连接请求分配路由波长，然后计算其可容纳的最大业务量，以此作为评价此虚拓 扑结构的适应度) ，用免疫算法对这组虚拓扑结构进行优化，以此得到最佳或近 似最佳的虚拓扑。整个的流程如图2 7 所示。 广东工业大学工学母j 士学位论文 2 3 本章小结 随机产生一组满足限 制条件的虚拓扑结构 i 根据给定业务量矩阵计 算每一虚拓扑的适应度 i 用自适应免疫算法对群体 进行进化，寻找最优个体 图2 7 算法流程 f i g 2 7t h ef l o wo fa l g o t h m 本章详细介绍了光城域网的出来、光城域网的基本结构、网络拓扑结构及城 域网的发展趋势：阐明了城域网和骨干网、接入网的区别与联系。同时指明了本 文要研究的内容、实现的目标和采用的方法。 1 4 第三章免痤算法简介 第三章免疫算法简介 在网络优化、计算机科学、控制工程及超大规模集成电路设计等领域存在 大量优化问题，对于其中很多n p 完全问题，传统优化方法易陷入局部最优解， 并且当问题规模增大时，往往由于算法的时问复杂性太大而丧失了可行性。近年 来，以遗传算法( g a ) ，模拟退火( s a ) ，禁忌搜索( t s ) 为代表的智能优化算 法为n p 完全问题的解决提供了新的途径。s a 和t s 虽具有全局寻优能力， 然而其串行的搜索结构使得其搜索效率不高。g a 虽具有高度的并行性和全局 性，但其局部搜索不是很有效，且常出现进化缓慢的现象m l 。近年来，基于生物 免疫原理的免疫算法得到了长远的发展，在机器学习、过程控制、多峰函数优化、 模式识别、数据分析等方面都有应用m t ，”w 。本章重点介绍了生物免疫系统的原 理以及基于免疫原理的自适应免疫算法的实现。 3 1 生物免疫系统 3 1 1 免疫系统简介 免疫系统是m 免疫组织器官、免疫细胞和免疫分子组成的一个复杂系统、它 是抵抗细菌、病毒和其它致病因子入侵的基本防御系统。免疫细胞和免疫分子一 直监管着机体，它们几乎能够识别所有外来的感染细胞和物质，并把它们与自身 未被感染的细胞区分开来。当病原体( 抗原) 进入机体时，免疫系统能够识别它， 并产生抗体对付入侵的病原体( 抗原) ，达到消灭病原体( 抗原) 的目的口：”：。 3 1 2 免疫系统的进化机理 免疫系统中有大量带有独特受体的b 细胞，每个b 细胞受体的形状可用一个 n 维实向量描述，因此可表示为n 维欧几里德空间中一点，称此空间为欧几里德 形状空问。两b 细胞的受体形状越相似，它们在形状空问中距离越近。当抗原 侵入机体时，b 细胞受体与抗原形状互补程度越大，二者问亲和力越高，从而更 易结合。b 细胞群体通过如下进化过程产生抗体m 删： 广东工业大学- t 学顾士学位论文 ( 1 ) 选出与入侵抗原亲和力高的b 细胞。 ( 2 ) 该b 细胞分裂为若干子b 细胞，称为克隆扩增。子b 细胞受体形状在母 细胞的基础上发生微小变异，即超突变。b 细胞通过克隆扩增在形状空间中的小 邻域内产生若干子b 细胞，以在局部范围内搜索亲和力更高的b 细胞。 ( 3 ) 在克隆扩增生成亲和力更高的子b 细胞的同时，也产生了亲和力低的子 b 细胞。一些亲和力低的子细胞删除其受体并生成新受体，称为受体修饰。受体 修饰使得子b 细胞可能突变为形状空间中离其较远的点，以避免在寻求高亲和力 b 细胞的过程中陷入局部最优。 ( 4 ) 一些亲和力低的子b 细胞死亡，同时骨髓产生一些新的b 细胞加入群体， 以保持群体的多样性。 经过若干世代的选择、克隆扩增、受体修饰和骨髓产生新b 细胞的过程，最 终产生了亲和力很高的b 细胞。该b 细胞分化为浆细胞，产生与受体形状相同