（光学专业论文）wdm光网络动态业务流量的可重构疏导.pdf

内容提要内容提要随着光网络和波分复用技术的发展，流量疏导成为当今光网络研究中一个学术与商业价值并重的研究热点。在w d m 光网络中使用流量疏导技术不仅能够有效地降低网络成本，也能够使网络性能得到必要的优化。因而自从它在1 9 9 8 年被提出后就引起了国际上众多著名研究机构的广泛关注。由于这一问题是n p 难问题，各种现代启发性算法就成为解决这一问题的有力工具。为了适应当前网络中普遍存在的突发多变的业务分布，如i p 数据业务，我们引入了一种称为动态业务的网络可重构疏导的新型流量疏导概念。本文对这一疏导类型进行了定义、分类，并对这一疏导类型的特点、所使用的方法和应用范围进行较全面的论述。本文对动态业务的网络可重构疏导中的可变性业务可重构疏导进行详细的研究。对可变性业务可重构疏导的两种疏导方案，1 ) 最佳匹配疏导方案：2 ) 完全匹配疏导方案，分别提出了一组整数非线性规划方程。在此基础上，我们设计了两个使用业务分叉技术的遗传算法实现最佳匹配疏导和完全匹配疏导。为了证明上述算法的有效性，我们进行计算机模拟，并对模拟结果中所出现的各种情况进行了详细的比较和讨论，同时分析重构疏导的优越性。结果表明，本文所设计的算法取得了很好的优化效果，远远优于以往的疏导结果。关键词：光网络可重构流量疏导波分复用动态业务遗传算法a b s t r a c ta b s t r a c tw i t ht h ed e v e l o p m e n to fo p t i c a ln e t w o r ka n dw 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 y , t r a f f i cg r o o m i n 童b e c a m eo n eo ft h em o s ti m p o r t a n tp r o b l e m si no p t i c a ln e t w o r k sw i t hh i g hs c i e n t i f i ca n dc o m m e r c i a lv a l u e s e 伍c i e n tg r o o m i n go f 仃a 伍ci no p t i c a ln e t w o r kc a nn o to n l ye f f e c t i v e l yr e d u c et h en e t w o r kc o s t ，b u ta l s oo p t i m i z ei t sp e r f o r m a n c e s s oi th a sa r o u s e dm u c ha r e n t i o nf r o mm a n yf a m o u si n t e r n a t i o n a lr e s e a r c hi n s t i t u t e ss i n c ei t sa p p e a r a n c ei n1 9 9 8 a tp r e s e n t d u et ot h en p h a r dp r o p e r t yo ft h i sp r o b l e m 。m e t a - h e u r i s t i c sw i l lb et h em o s tp o w e r f u lt o o l sf o rt a c k l i n gt h e m i no r d e rt os a r i s f yt h ec h a n g e f u lt r a 艏cw h i c he x i s t sc o m m o n l yi nc u r r e n tn e t w o r k ，s u c ha si pt r a f f i c ，w ep r o p o s e dan e wc o n e 印to ft r a m cg r o o m i n g ，n a m e da sr e c o n f i g u r a b l eg r o o m i n gu n d e rd y n a m i ct r a f f i c ，i nt h i sp a p e r w ed e f i n e dt h i sn e wg r o o m i n gt y p ea n dc l a s s i f i e di t w h a t sm o r e w ed i s c u s s e di nd e t a i lt h ep r o p e r t i e s ，m e t h o d st os o l v ei t ，a n da p p l i c a t i o nr a n g eo f i t r e c o n f i g u r a b l eg r o o m i n go fr a n d o m 缸a 伍cw a ss t u d i e dp r o f o u n d l yi nt h i sp a p e r t w os e t so f i n t e g e rn o n l i n g e rp r o g r a me q u a t i o n sw e r ep r o p o s e dt od e s c r i b eb e s tf i tc u s ea n df u l lf i tc a s er e s p e c t i v e l y b a s e do nt h i s t w og e n e t i ca l g o r i t h m sw i t hs p l i t t i n gt r a f f i cm e t h o dw e r ea l s od e v e l o p e dt os o l v et h e s et w oc a s e sr e s p e c t i v e l y t ot e s t i f yt h ee f f i c i e n c yo ft h ea l g o r i t h m sp r o p o s e d ，c o m p u t e rs i m u l a t i o n sw e r ee a r r i e d0 u t a n dt h o n , w em a d ed e t a i l e dc o d a p a r i s o na n dd i s c u s s i o n so nt h e ma n da l s oa n a l y z e dt h em e r i to fr e c o n f i g u r a b l eg r o o m i n g 1 1 1 er e s u l t ss h o w sa l g o r i t h m sd e s i g n e di n t h i sp a p e ry i e l d e db e t t e rr e s u l t st h a n0 t h e r sp r e v i o u s l yu s e di nt h el i t e r a t u r e k e yw o r d s ：o p t i c a ln e t w o r k ，r e c o n f i g u r a b l eg r o o m i n go f t r a f f i c ，w d m ，d y n a m i ct r a f f i c ，g e n e t i ca l g o r i t h m第一章绪论第一章绪论第一节光网络中流量疏导的概念及其意义= 芒e 这高度信息化的社会里，信息的爆炸不断地刺激各种高容量的通信网络的迅猛发展，特别是近几年，在以口业务为代表的数据业务量喷气式增长和新型业务不断涌现所导致的巨大带宽需求的刺激下，只有光波技术才能为现有的及未来的宽带业务提供强有力的发展平台并使之造福人类。为了充分利用光纤的带宽资源，波分复用( w d m ) 技术以其扩容简单、成本低廉等优势运应而生 1 - v 。一般而言，流量疏导( t r a f f i cg r o o m i n g ) 研究的是如何将不同速率、不同类型的低速业务流打包成高速数据流，复用到一个波长上，以实现各种特定设计目的的过程。流量疏导是一个较新的研究课题，这一问题的提出是由于近年来波分复用( w d m ) 技术的应用，使得单根光纤可承载更多波长，而每个波长又可通过时分复用( t d m ) 的方式容纳许多低速业务流。在这样的系统中限制光网络潜在容量得到充分发挥的主要因素己不再是光纤的带宽，而是网络终端的复用器、交换机和路由器等电子设备的处理速度所带来的瓶颈效应口】。对于每个节点，我们可以通过流量疏导利用波长上下路复用器( w a d m ) 把节点所需的波长提取出来，而对其它不需要的波长进行光学旁路，从而减少节点处网络设备的信息处理量。波分复用的s o n 】玎环的节点结构如第一章绪论图1 1 所示，图中共有三个节点分别是a 、b 、c 。对于节点a ，波长九2 没有携带它的业务，因而在节点a 处被w a d m 旁路( 直接通过) ，而波长h 有携带到节点a 的业务，所以在节点a 处，被w a d m 提取出来。w a d mw a d mw a d m图i 1w d m 环网络的节点结构( 节点a ，b ，c )当有波长在网络节点下路时，就有一些低速业务流要从该波长所携带的高速业务流中被解复用，使这些业务信息为该节点所接收：或者有某些低速业务流要在该节点中被复用到该波长上，使这些业务信息可以从该节点传送到其它节点中去。例如，4 个o c 。3 业务流可被复用到一个o c 。1 2 业务流中，而1 6 个o c 3 业务流可被复用到一个o c 4 8业务流中。一个波长所能携带的低速业务流的个数称为业务粒度( t r a f f i cg r a n u l a r i t y ) 。对每一个在节点中上下路的波长都需要在该节点中放置一个a d m 复用器，图1 1 中有两个波长九l 、如在节点c 中上下路，因此在该节点中需要有两个a d m 复用器( 一个用于九l ，另一个用于九2 ) 。通过在每个终端节点上放置一个波长上，下路复用器( w 柚m ) ，便可以有选择地让某些波长在该节点处下路，而对其它未携带与该节点业务有关的波长则在该点处迸行光学旁路，这样，既降低了节点处所处理信息量，也减少了终端设备的使用量，从而减少了第一章绪论网络建造的费用。为了说明业务流量疏导所带来的效益，让我们来看一个例子。图1 2 给出了一个环状网络中业务流量疏导的例子。图中的业务信息按顺时针方向流动。设每个波长所携带业务信息量为一个o c - 4 8s o n e t 环( 即传输速率为2 5 g b s ) ，而每个节点对之间的业务需求量均为8 个o c 3 业务流，网络中的s o n e t 上下路复用器可将1 6 个o c 3 业务流复用到一个o c - 4 8 业务流中，因此每一波长均可携带相当于两对节点间的业务量。四个节点共有6 对业务量，因此共需三个波长。图1 2 ( a ) 表示没有进行流量疏导时的业务分配方案其中节点对l + 2 与3 h 4 间的业务量由波长九1 携带，2 , - - - 3 与1 4 间的业务量由波长k 携带，l h 3 与2 4 间的业务量由波长b 携带。在这种疏导方案中由于每一波长都在每一个节点中下路，因此每个节点都要配各3 个a d m ，共需要1 2 个a d m 。图1 2 ( b ) 表示同一环中进行适当的流量疏导后的业务分配方案。在这一方案中，每一节点都配上一个w a d m ，它只让那些携带与该节点业务有关的波长在该节点处下路，而将其它波长在该点处进行光学旁路。其业务量的分配情况如下：九- ：1 2 与l h 3 ，九2 ：2 + - 3 与2 4 ，k ：1 + 4 与3 付4 。在这种疏导方案中虽然仍用三个波长，但由于每个波长仅在三个节点处下路，因此，只要9 个a d m ，比未疏导的方案节约了3 个a d m 。由图1 2 ( b ) 也可以看出，第一个波长仅在节点1 、2 和3 处下路，因此只要在这三个节点中对该波长分别配备一个a d m 即可，其余的波长也是这种情况。在上述两种业务分配方案中，每一波长均工作于满负荷状态( 都携带1 6 个o c 3 业务流) ，但所用的a d m 数却不同。因此，经过适当的方法疏导后，不仅会减轻网络中节点上的电子设备的负担，还减少网络中的a d m ( 例如一个o c 4 8a d m 的价格为数十万美元) 的使用量。在大型网络中，由于疏导良好而产生的插分复用器用量的减少将带来网络建造成本的大幅度下降，从而产生十分可观的经济效益。由此可见，流量疏导是当今光网络设计中必须考虑的一个重要问题。第一章绪论( a ) 一个可能的无疏导方案4( b ) 另一个可能的已疏导的较优方案图1 2s o n e t i w d m 环网的业务流量疏导例子另一方面，已经证明，单向环网中的流量疏导问题为n p 难问尉吼，计算量随着网络中的节点的数量而呈指数增加，由此可知对一般的网络中的流量疏导的计算必将更为复杂。因此在流量疏导这个领域中，我们一般采用禁忌搜索算法、贪婪算法、遗传算法等现代启发性算法进行求解，此类算法主要用于优化计算。它们在复杂系统、多峰函数及组合问题的优化有着明显的优势，能够快速得到较优的解。总之，流量疏导是当今光网络研究中一个学术与商业价值并重的研究热点。在w d m 光网络中使用流量疏导技术不仅能够有效地降低网络成本，也能够使网络性能得到必要的优化【4 毛8 训。墨篱善盏第一章绪论第二节动态业务网络可重构疏导的分类在流量疏导中，根据网络中业务需求是否发生变化，把流量疏导分成两类：静态流量疏导与动态流量疏导。静态流量疏导是指对一组已知且不随时间变化的业务需求进行疏导，其目的是使用最少的a d m来支持这组业务 5 , 8 - 1 2 1 ；而动态流量疏导是对一组随时间变化的业务需求进行疏导，其目的是使用最少的a d m 来支持这组变化的业务 5 , 1 3 - 2 0 】。对于静态流量疏导，问题难度相对较小，在一些简单的网络拓扑如环形网，已有较多文献进行研究 5 , 8 - 1 2 】。而动态流量疏导因其研究难度大，所以涉及的文献较少 5 , 1 3 - 2 0 】。近几年来，p 业务的飞速发展，并且其本身又是一种突发性很强的数据业务，因而对于应用于此领域的动态流量疏导是很大的挑战，也进一步体现了应用于i p o v e r - w d m 中的流量疏导的巨大商业价值。动态流量疏导是目前光网络研究中的一个热点，本文将对一种新型动态业务流量的网络可重构( r e c o n f i g u r a b l e ) 疏导方式进行论述与分析。网络可重构指的是在流量疏导过程中，网络的虚拟拓扑或物理拓扑可根据需要进行重构。本文所定义的动态业务网络可重构疏导是指，在原来网络业务分布基础上，为满足新的业务需求而对网络进行重构( 包括光通道拆卸重建、节点的a d m 个数增减、业务分叉、网络粒度变化等) ，使其从一种拓扑结构转变为另一种新的拓扑结构，从而实现业务的动态流量疏导的一种新型动态流量疏导模型。由于动态流量疏导的难度比静态的要大得多，因此目前在国际上动态流量疏导的研究尚处于起步阶段，特别是有关动态业务流量网络可重构疏导的报道就更少了。在本文中，为了便于分析和研究，我们根据业务需求矩阵变化的特点及流量疏导的过程把动态业务流量网络可重构疏导分成两大类：( 1 ) 魔定拦 蝣腭磐刀垄张彩掰鸯席导正护逭甄l 司变性业务砜络司重掏昀流量疏导闯题( 以后为7 方便我钠稳毖形茄导为刁爻涩丝劳露耍菊瓣导) 。在第一种疏导类型中，假定网络中各节点间的业务变化的过程为已知，或可以预测，流量疏导的目的是对这一组随时间变化的业务需求进行疏导，以便用最少的a d m 及波第一章绪论长数来支持这组变化的业务。在第二种疏导类型中，网络中业务矩阵的变化过程未知，或无法预测。疏导的目的是在原有的网络构架中，在不增加a d m 数的情形下，把新到的业务尽可能多地装入到网络现有的波长中去，充分的利用现有的波长与a d m ，使新的业务需求到达时各节点间的业务阻塞率最小：或是在所增加的a d m 及波长数最少的情况下，尽可能把新的业务全部疏导到网络中去，以实现网络设计的优化。本文的后面章节着重研究第二类疏导，即可变性业务可重构疏导。第一种疏导类型实际上是一种离线疏导，即在网络投入实际运行之静对网络中的业务流量进行预测和优化。这种疏导类型中，网络的重构主要是在虚拟拓扑方面的重构。这种类型疏导一般是应用在网络中各个节点间的业务流量是按一定的规律变化的情形，因此我们可以将网络节点间业务流量的变化分为若干个时间段，用每一时间段内的平均值来近似代替段内的业务流量，从而构成一套业务需求矩阵，它可近似代表这个网络不同时刻业务分布的动态变化。在对这套业务需求进行疏导时可根据不同的阻塞特性将其分为严格无阻塞疏导及可重构无阻塞疏导两大类，其中严格无阻塞疏导不需对网络进行重构，而在可重构无阻塞疏导只需对网络的虚拟拓扑进行重构，即相同节点对间不同时刻的业务需求允许被疏导到不同的波长中以形成不同的虚拟拓扑。第二种疏导类型是一种在线疏导。即在网络正常运行时，网络中的大部分业务继续正常传输，只对少量发生变化的业务进行实时疏导。这种疏导类型中既虚拟拓扑方面的重构也有物理拓扑方面的重构。这种类型疏导主要应用于新来的业务需求分布没有规律性，是完全任意的情形。这种业务需求情况类似于现在的口数据业务，且更有具有普遍意义。此时，如果在不同业务需求分布到来时，没有把网络拓扑转变到一种更能适应新业务流量分布的拓扑结构，那么旧的网络可能就无法很好的满足新的业务流量分布，从而造成网络中各种资源利用率严重降低，所以利用一定的算法把网络的拓扑进行重构有着重大的意义。但由于这种疏导需要对网络的物理拓扑进行重构，在实际应用中第一章绪论如何操作还是一个需要解决的问题。为了更加直观对比这两种疏导类型的异同，本文把它们的特点归纳成表1 1 。表1 1两种疏导类型的比较第三节动态业务网络可重构疏导的研究现状现在对近几年w d m 光网络动态业务流量的可重构疏导的研究情况进行评述。1 3 1确定性业务网络可重构的流量疏导问题确定性业务网络可重构的流量疏导问题是针对离线( o f f - l i n e ) 的情况下进行流量疏导，即在网络投入实际运行之前进行流量疏导，在这类疏导问题中，主要将对其虚拟拓扑进行重构以满足动态变化的业务需求。例如，在s o n e t ( 同步光网络) 愚，d m 光环网中业务流量的智能疏导中，动态流量疏导是其中一个很重要的部分。具体操作是，首先根据动态流量的特性生成一套业务需求，然后对它们进行疏导。在疏导过程中根据阻塞特性把动态疏导分成严格无阻塞流量疏导和可重构第一章绪论无阻塞流量疏导问题。对于严格无阻塞流量疏导问题，由于在建立新业务时，所有新的业务请求都被分配在原来相同的波长上，即所有的业务请求都不必在不同的波长间进行调整，因此随着时间的变化，网络拓扑结构没有发生改变。而对于可重构无阻塞流量疏导，在建立新业务时，有部分新业务请求要在不同的波长问进行调整，重构了网络的虚拟拓扑 5 1 。在可重构无阻塞疏导问题的求解中，文献 5 】把遗传算法与局部启发性搜索相结合，形成混合遗传算法，并设计了二重染色体结构，可以在初步解码后对个体进行调整和优化，以获得最佳的优化效果。通过模拟所得结果，与严格无阻塞流量疏导相比，由可重构无阻塞疏导所得的a d m 数与波长数相对于最大业务需求的疏导结果有更明显的减少。并且，对于环中的业务需求强度越小，及环中的节点数越多的情形，疏导效果更好。另外，该文献的算法可一次性完成对波长分配、选路及整套业务需求疏导，使网络的a d m 数最优，使用的波长数也较少。与文献 1 7 1 相比，算法的有效性较高。1 3 2可交性业务网络可重构的流量疏导问题现在我们讨论可变性业务网络可重构的流量疏导问题。这是一种在线疏导，换句话说，此时网络上已有正在传输的业务，但由于新到来的业务完全任意，旧的网络拓扑无法很好的满足它。为了不让新的业务被阻塞，我们必须对网络拓扑( 主要是物理拓扑) 进行重构，以满足新的业务，且尽可能保持整个网络业务的正常传输( 只对少量必要的业务予以中断) ，实现可重构疏导。这类可重构疏导更具普遍意义，是一个新的研究方向。1 3 2 1 光环网中的疏导在光环网中为满足动态业务的需求，我们有两种解决方案：最佳匹配( b e s tf i t ) 方案及完全匹配( f u l lf i t ) 方案【2 。在最佳匹配( b e s tf i t ) 方案中，疏导的目的是在不增加a d m 情形下，尽可能多的把新的业务装入到网络现有的波长中去，以充分的利第一章绪论9用现有的波长与a d m 。但可能会使新业务需求中的某些节点间的业务受阻塞，无法完全满足新的业务需求。b e s tf i t 方案的优点是显而易见的，就是不用增加昂贵的a d m 就能在很大程度上满足新业务的需求。在这个方案中使用了贪婪算法( g r e e d ya l g o r i t h m ) 与禁忌搜索算法( t a b us e a r c h a l g o r i t h m ) 。在完全匹配( f u l lf i t ) 方案中，为了完全满足新的业务需求，可根掘需要向网络的某些节点增加a d m 和波长。因而此方案的优化目标是最小化重构后网络中所使用的a d m 数量( 原有的a d m 与新增的a d m两者总和) 。对于此方案，用两个阶段算法来实现。在第一个阶段，使用b e s tf i t 的方案来进流量疏导，第二阶段则是把第一阶段无法疏导的业务需求进行再次疏导，并增加相应的a d m 和波长。从本质上说，完全匹配方案的流量疏导是第一阶段疏导再加一个静态流量疏导。由于在第二阶段使用了禁忌搜索算法，与文献 9 】利用贪婪算法( g r e e d ya l g o r i t h m ) 及文献【1 2 利用模拟退火算法( s i m u l a t e da n n e a l i n g ) 进行求解相比，有以下几个优点：只需运行一次；多次试验结果稳定；可得较优结果。但在该方案中由于疏导后要动态增加新的a d m ，在实际操作过程中还有定的困难。1 3 2 2 格状网中的疏导由于现在使用的光网络拓扑主要是环形拓扑结构，因此上面讨论的均是环形拓扑结构中的疏导。但是随着各环形网络之间的联系逐渐加强，相互需要互传信息，因此很多的环形网就互连起来，形成了格状网( m e s hn e t w o r k ) ，这样环形网之间的业务传输的疏导问题也就成了格状网的流量疏导问题，同时由于格状网具有很强的生存性、连通性等优点，越来越多的网络采用了格状拓扑结构。因此格状网中的流量疏导也就成为一个值得我们重视的研究领域。文献 1 8 】是以最大化网络的吞吐量，最小化网络的传输延迟为优化目标进行动态疏导。作者提出了在格状网( m e s h n e t w o r k ) 中通过对业务流量一个周期的观察后，对必要的光通道进行拆卸和建立以满足第一章绪论1 0新的业务需求。每一次只允许调整一条光通道，而不影响其它业务。其中定义了观察周期( o b s e r v a t i o i l p e r i o d ) 。表示在多长时间开始对网络拓扑进行重构：水位标识( w a t e r m a r k ) ，其中又分为高水位标识( h i g hw a t e r m a r k ) 和低水位标识( 1 0 ww a t e r m a r k ) ，前者表示网络控制者设定的通道负载的最大值，后者则表示设定的通道负载的最小值，只要有光通道的负载不处于这两者之内，观察周期结束就对此通道进行相应的操作。在对1 9 个节点的格状网( m e s hn e t w o r k ) 运用启发性算法模拟计算，结果显示：观察周期越长，光通道被调整可能性就越高；大的高水位值，小的低水位值，被调整的光通道数就越少，相反，则被调整的光通道数就越多；平均业务权重跳距也随着光通道的调整发生了变化。在进行网络的拓扑重构时，基本上可把中断的业务数量降到最小。但是该方法的不足之处就是：它要求网络管理者要根据自己网络的特点，对以上就参数进行设置，以实现各种特定目的。这对网络管理者的索质要求很高，且没有具体的参数设置准则。文献( 1 9 】，利用格状网( m e s hn e t w o r k ) 中的通道保护的波长容量作为中间交换容量，对网络拓扑进行重构以满足新业务的需求，使得被中断业务量最小化，甚至完成了业务无损的网络拓扑重构，最后再还原通道保护的波长资源。当然，它是基于在重构过程中不使用通道保护的波长容量的假设。在启发性算法的应用上。使用了5 个不同的模块对光通道进行调整，分别是s w i t c h 、a p p e n d 、b a c k u p 、r e l e a s e 、d e l e t e ，另外加上一个对波长进行重分配的模块，最终达到减少业务中断目的。模拟结果表明，此算法能够非常有效的降低业务的中断，但也导致波长资源使用率不太高，即产生的虚拟拓扑不是最优的。1 3 3小结以上对近年来动态业务网络可重构疏导进行了简单的评述，由于各篇文章针对不同的逻辑拓扑和不同的优化对象，运用的计算方法也不相同，各有优点，也有一定的局限性。总的来说。以上文献都采用数学规划方程描述疏导模型，再用遗传算法、贪婪算法、禁忌搜索算第一章绪论法等启发性算法进行求解，能得到较优的结果。对于可预测的动态业务我们可以采用离线的可重构疏导。而对于随机变化的业务，如业务，可用在线的可重构疏导。但在线疏导问题具有很大的难度，对我们来说是一个很大的挑战。第四节本文的主要工作及结构本文的主要工作：1 ) 为了便于分析和研究，根据业务需求矩阵变化的特点及流量疏导的过程把动态业务网络可重构疏导分成两大类：( 1 ) 功启雒澎务网络可重构的流量疏导同题、吨、司变性业务两络可重构的流量琉导闻慝并对这两类型疏导的特点、所使用的方法和应用范围进行较全面的论述。2 1 首次提出了遗传算法及其局部启发性算法相结合的方法对动态业务进行网络可重构疏导，很好地解决了可芟丝业务胖可莺枷夕藐宣痈粤，硫氦在已有的文献中作者使用了贪婪( g r e e d y ) 算法和禁忌搜索( t a b us e a r c h ) 算法进行求解，而遗传算法在此领域内的应用尚属首次，且取得更优的结果。3 ) 在网络可重构疏导中引入了业务分叉技术，并把它与混合遗传算法结合起来，完成流量疏导，实现光网络资源的进一步优化，并研究了其在流量疏导中的优化作用。本文的结构如下：第一章介绍了流量疏导的概念及其意义；引入了一种新型的疏导类型，即动态业务网络可重构疏导，对它进行定义与分类，并分析了这种疏导类型的特点、所使用的方法与应用范围，最后综述了它们的研究近况。第二章介绍了遗传算法的原理、实现方法。对算法的流程、算法的各功能：染色体的编码、染色体的交叉变异和染色体的优胜劣汰选择进行了介绍。在第三章中，我们研究可变性业务可重构疏导的最佳匹配( b e s tf i t ) 疏导方案。首先把我们用到的概念、符号等进第一章绪论1 2行描述，之后简述一种业务分叉技术，然后给出解决b e s tf i t 方案的算法。最后，我们给出模拟计算的相关结果，并进行分析和讨论。第四章详细研究了可交性业务可重构疏导的完全匹配( f u l lf i t ) 疏导方案。在本章中，我们提出了另一个混合遗传算法用于解决该方案，得到计算机模拟结果，并迸行详细的分析和讨论。第五章总结全文，并对今后的研究工作做出展望。第二章遗传算法第二章遗传算法蚬代启发性算法( m e t a - h e u r i s t i c a l g o r i t h m s ) 是一种不依赖于具体问题，通用而高效的随机搜索方法。具备了将问题的解向优化方向引导的能力。它是由g 1 0 v e r 在1 9 8 6 年提出禁忌搜索算法时正式命名的l 孙】。常用的启发性算法，包括贪婪算法、模拟退火算法、禁忌搜索算法、遗传算法等。这类算法具有很强的局部爬山能力，对复杂系统、多峰函数、组合问题的优化有明显优势。它们在各种领域中都有着大量成功的应用实例。一般地，遗传算法( g e n e t i c a l g o r i t h m ，简称g a )得到的解的质量和运行时间都比较理想，因此，采用了遗传算法来实现光厨络的流量疏导。第一节遗传算法的生物基础一百多年前，达尔文( d a r w i n ) 刨立的进化论对生物学产生了极为深刻的影响，成为生物学最重要的个理论，恩格斯称誉其为1 9 世纪自然科学的三大发现之一。达尔文的进化论包括了三个基本要素：变异、遗传、选择【3 4 1 。变异是选择的基础，遗传是选择的保证，有利的变异和这些变异的遗传，需要通过不断地选择才能把它们保留和巩固下来，同时选择又促进了变异向有利的方向发展，从而创造出数目繁多的新物种。物种是经过第二章遗传算法1 4自然选择而发展而来，只有适应自然环境的物种才有机会继续繁殖下一代，让生命延续下去。而那些不适应自然环境的物种将逐渐被淘汰，最终消亡。下面我们对进化论的三个基本要素进行讨论：1 、变异变异是指同种生物世代之间或同代不同个体之间存在差异。生物体的变异主要表现为突变。这种变异有提高竞争力的、有损害竞争力的、有能遗传的、有不能遗传的。我们所感兴趣的是能遗传的有助于提高竞争力的变异。就变异而言，它可以分为两类：( 1 ) 染色体( c h r o m o s o m e ) 变异：指染色体数目、大小和结构的改变。它是在细胞复制时以极小的概率产生的某些复制差错，从而产生新的染色体。基因突变：是指脱氧核糖核酸上仅有一个核苷酸改变的变异。它也是染色体变异的一种，属于染色体结构发生变化。( 2 ) 基因( g e n e ) 重组：它是通过有性繁殖实现的。同源染色体( 父代个体对的染色体对) 基因相互交换，叫连锁互换：不同对染色体的随机组合所形成的重组，叫自由组合；有些d n a 片段能够改变自身的位置，叫转座因子。另外，变异产生的主要原因有两个：一是d n a 在复制过程中偶尔发生差错，即自发突变；二是人工诱发( 自然环境) ，即诱发突变。变异一方面能使个体具有更强的适应能力，另一方面也可能产生更不适应自然环境的个体。2 、遗传遗传就是子代总是保持和亲代相似。遗传性是一切生物所共有的特征，正是这种遗传性，使得生物能够把它的特性、性状传给后代，在后代中保持相似。现代遗传学研究表明，生物都具有遗传性，遗传学的建立和发展有力地推动和促进了进化论。3 、选择选择决定生物进化的方向。所谓选择是指生物具有保留和淘汰的第二章遗传算法特性。选择分为人工选择和自然选择，人工选择是在人为环境下，把对人有利的生物保留下，对人不利的个体淘汰掉。自然选择就是指生物在自然界的生存环境中适者生存。世界上所有形形色色的生物，都是在自然选择的影响下，在悠久的岁月中形成。自然选择的过程是通过生存斗争的过程来实现，生存斗争的结果，优胜劣汰，这样就保证了生物去适应环境。通过不断地自然选择，那些有利于生存的变异就遗传下去，日积月累，越来越大，逐步产生了新的物种。生物就是在遗传、变异的综合作用过程中，不断地向前发展和进化。选择是通过遗传和变异起作用的，变异为选择提供资料，遗传巩固与积累选择资料，而选择则能控制变异与遗传的方向。使变异和遗传向着适应环境的方向发展。虽然生物进化论揭示了生物长期自然选择的进化发展规律，然而科学家从中受到了启迪，进化论的自然选择过程蓄含一种搜索和优化的先进思想，将这种思想用于工程技术领域，发展起来的遗传算法，为解决许多传统的优化问题提供了途径【3 4 。3 6 】。第二节遗传算法遗传算法是起源于上个世纪6 0 年代自然和人工系统的自适应行为的研究，“遗传算法”一词最早是由b a g l e y 发明，同时他在1 9 6 7 年发表了第一篇有关遗传算法应用的论文【3 ”。其正式的表述于1 9 7 5 年由j o h n h o l l a n d 给出的【3 s 】，但是现在常用的形式及对它的系统研究则1 9 8 9年由d e g o l d b e r g 给出的 3 9 1 。本节中我们将对遗传算法的基本原理和一般结构作一概要的介绍。遗传算法是一种借鉴生物界自然选择和自然遗传学机理上的迭代自适应概率性搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构( 字符串) ，并且在串之间进行有组织但又随机的信息交换。伴随算法的运行，优良的品质被逐渐保留并加以组合，从而不断产生出新个体。新一代个体中包含着上代个体的大量信息，新一代个体不断地在总体特性上胜过旧的一代，从而使整个种群向前发展。遗传算法主要由选择( s e l e c t ) 、杂交( c r o s s o v e r ) 和变异( m u t a t i o n )第二章遗传算法1 6三个算符组成，分别模仿达尔文进化过程中的自然选择和种群遗传过程中发生的交配和突变等现象，构成遗传算法的基本操作。遗传算法应用于实际问题时，要对所研究问题的可能解以字符串的形式编码成一个个体( i n d i v i d u a l ) 或称为染色体( c h r o m o s o m e ) ，个体的集合称为种群( p o p u l a t i o n ) ，且每一个个体都表示问题的一个可能解。遗传算法以随机产生的一组初始种群( 初始解的集合) 为开始，然后在遗传算符如杂交、变异等作用下而产生新的一代，称为后代( o f f s p r i n g ) 。最后根据每个个体适应值( f i t n e s s ) 的大小选择部分后代以形成新一代种群，其中适应值大被选中的概率高，这样，新种群中的个体继承了上一代的一些优良性状，因而优于上一代。通过这样反复迭代而使种群不断朝着优化的方向进化，最终得到的适应值高的个体就是问题的最优解或次优解。标准遗传算法的操作步骤如下：为了更好的理解遗传算法的工作原理，我们把遗传算法表示成下面的流程图第二章遗传算法图2 1 遗传算法流程图在遗传算法中，适应值是对个体性能评估的一种指标，它与所求问题的目标解有直接对应的关系。一般而言，越接近目标值的个体适应值越大，个体在新的选择中被保留下来的概率也就越高，因而将算法引导向优化方向不断进行搜索，以获得最优解和次优解。杂交运算因其全局搜索能力成为主要的运算，变异运算因其局部搜索能力成为辅助运算。杂交运算通过交换父代中两个不同个体的部分信息。一方面使得原来种群中优良个体的特性能够在一定程度上保持，另一方面使算法能够探索新的解空间，从而使种群中的个体具有多样性。变异运算则通过随机改变个体中某些基因产生新的个体，有助于增加种群的多样性，避免早熟。选择运算对算法的性能有直接的影响，通常是通过对各个个体的适应值大小按轮盘选择方法或其他方法进行选择，第二章遗传算法选出新的个体组成新一代的种群。由于适应值较高的个体被选中的几率较大，后代种群的平均适应值会高于其父代种群，使种群向着优化的方向进化。遗传算法随着神经网络、人工生命、进化计算等研究的兴起，引起了人们越来越多的兴趣，并已应用于搜索问题、优化问题及机器学习、自编制程序、模式识别、人工神经网络等方面。遗传算法获得巨大成功的主要原因在于它具有如下一些突出特点：( 1 ) 普适性。遗传算法是对问题的解或参数的编码进行操作，而不是对问题本身，因而它对优化问题本身没有太多的数学要求。遗传算法对于待寻优函数基本无限制，它既不要求函数连续，更不要求可微：既可以是数学解析式所表达的显函数也可以是映射矩阵甚至是神经网络等隐函数，因而应用范围较广。( 2 ) 遗传算法是从初始种群( 问题解的集合) 开始并行操作，而不是从单一个体( 单个解) 开始。因而可以有效地防止搜索过程收敛于局部最优，而且有较大的可能求得全部的最优解。( 3 ) 隐含并行性。遗传算法可以在不增加额外的存贮和计算开销的情况下，在处理个个体的同时并行处理大约3 个模式。因而它能够用一个较小的种群来搜索大范围的解空间，从而极大地增强了这一算法的全局搜索和优化能力。( 4 ) 遗传算法在解空间内不是盲目穷举或完全随机的测试，而是一种启发式搜索，其搜索效率往往优于其他方法。( 5 ) 遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度，即以空间复杂度来代替时复杂度。( 6 ) 遗传算法通过目标函数来计算适应值，不需要其他的推导和辅助信息，从而对问题的依赖较小。第三节遗传算法在流量疏导中的应用上一节所描述的是标准遗传算法，而本文根据光网络流量疏导问第二章遗传算法1 9题的特点，对传统遗传算法迸行改进，所设计的遗传算法有别于标准遗传算法，其独到之处如下：1 ) 编码方式遗传算法主要是对种群中的个体加以操作，从而完成优化的。遗传算法不能直接处理问题空间的参数，而只能处理以基因链码形式表示的个体，因此必须将待优化问题的解的参数形式转换成基因链码表示，这一操作称为编码。编码问题实际是从问题空间向表达空间的映射。经典遗传算法通常采用二进制编码方式，这种方法简单易行且便于模式理论进行分析。但二制编码方式是一种离散的编码，对求解连续优化问题不合适，如：相邻整数的二进制编码可能有极大的h a m m i n g距离，如0 1111 ll 和1 0 0 0 0 0 0 ，这将降低遗传算法的搜索效率。而对高维问题的求解，二进制编码的位串将会很长。此外，二进制编码串长固定后，缺乏微调能力。因此，在本文中，由于我们所要编码的对象是业务流量，在任意两个节点间的业务需求均为整数。所我们采用整数编码方式，即使用十进制数字对业务需求进行编码。2 ) 杂交算符由于实际问题的解决需要，在编码过程中采用的编码方式上往往会有很大差别，人们为了实现各种特殊目的而设计了不同的遗传算符。在文中，我们使用的是文献( 4 0 】中提出的次序映射杂交算符( o r d e r - m a p p e d ) o m x 。这一算符的操作过程如下：a ) 两个父体上均匀随机选择两个点，由此定义的子串称为映射段；b ) 交换父体中被选中的两个子串，并在予串中填入原父体中未冲突的部分基因，产生两个部分后代个体( 冲突部分由x 表示) ；c ) 从选定的予串中挑出那些未出现在另一子串中的基因，并将它们按同一顺序( 升序或降序) 排列，并按这一顺序确定映射关系；d 1 根据上述映射关系填入由x 表示的剩余基因以产生两个完整后第二章遗传算法代。例如：第一步：从两个父代中，选择两个子串父代1 ：l 匕l 1 生- 三土蔓二削父代2 ：匝瞿互叠 三卫：田第二步：交换被选定的子串( 冲突部分由x 表示)后代t ：臣 墨三工；：1 i r 丑珂后代2 ：匝f i ! 兰圈习卫第三步：把未出现的基因，进行顺序( 升序或降序) 映射。和一团团与田田第四步：按上面的映射关系，填入由x 表示的基因产生两个后代。后代1 ：后代2 ：匪墨i 珀这一算符确保了杂交后后代中没有重复个体，因而没有非法个体产生。同时它在后代中尽可能保存了父代的原有顺序关系。此外，这种算符比其它同类算符更容易实现。3 ) 变异算符我们采用了数字串反转的变异算符( 这与经典遗传算法一致) ，例如：父代的数字串为e 鬯鋈篓匿麴篓! 习第二章遗传算法那么，我们随机选取此串中的两个点选择中了l 与9 ，然后，我们把1 到9 之间的这个子串( 如上图底色为灰色的子串) 反转变成如下图： 丑霞匿銎隳翌季? 田而在1 与9 之外的元素不变。我们以这种方式来实现遗传算法中的变异运算。4 ) 选择标准的遗传算法采用的选择方法很多，包括轮盘选择法( r o u l e t t ew h e e ls e l e c t i o n ) ，局部选择法( 1 0 c a ls e l e c t i o n ) ，截断选择法( t r u n c a t i o ns e l e c t i o n ) 和随机遍历抽样法( s t o c h a s t i cu n i v e r s a ls a m p l i n g ) 等。这些方法均是随机选择个体，被选择的机会与个体的适应度有关，适应值较大的个体有可能被多次选择，因而这种选择方式是动态的。考虑到演化策略在数值优化领域表现出来的优势【4 i 】，我们设计的算法采用了演化策略( e v o l u t i o ns t r a t e g i e s ) 的选择方法，即依次无重复地选择适应值大的个体，这个过程是确定的。在实际运箅中，我们发现这种选择方法能加快搜索速度。5 ) 带有局部优化的混合遗传算法简单遗传算法( s g a ) 在很多情况下不能得到理想的解，由于纯粹的遗传算法局部爬山的能力较差。许多研究者将梯度法、爬山法、模拟退火算法这一类有很强的局部搜索能力的算法融合入遗传算法，以改善个体的适应值，这构成一种新的混合遗传算法。许多研究表明，这种局部改进提高了遗传算法的求解质量和运行效率4 2 1 。因此。本文在使用遗传算法求解流量疏导问题时，采用了局部优化的方法对后代中的每个个体进行优化，使用了自适应个体( a d a p t i v ec h r o m o s o m e )的概念【1 0 l 4 0 】，即个体能在优化过程中自动适应外界环境，主动向局部最优方向调整，使搜索过程能以较高的效率取得理想的结果。第二章遗传算法第四节本章小结本章对遗传算法进行了具体的阐述。从遗传算法的生物基础、基本原理、一般框架到本文所使用的混和遗传算法的特性都进行了详尽的叙述和分析。另一方面，遗传算法都还有其它广泛的应用，如人工智能、神经计算等，且各种改进算法也在不断涌现，如文化遗传算法、协同演化算法等。当然，遗传算法作为一种启发性算法还存在了一些不足( 没有坚实的数学基础理论的支持，参数设置问题等等) ，这还有待进一步的发展与完善。第三章可变性业务可重构疏导的最佳匹配方案第三章可变性业务可重构疏导的最佳匹配方案为了便于分析和研究，我们根据业务需求矩阵变化的特点及流量疏导的过程把动态业务网络可重构疏导分成两大类：( 1 ) 礴启拦业务网络司重桷的流量疏导闯题；q 、可变性业务砜络司重构的流量疏导闻题( 以鑫为7 方便我们称屹转硫导为司变性韭务司重构琉导) ，铽于确定攫比务网络刃：重绚的藏量疏导问危甄文献 1 3 1 7 1 都进行深入的研究，也取得了一定的成效。而对于可变拦业务网络可蚕挎移流量蒴导膨g 的研究，才刚刚起步( 到目前到止，只有文献 2 0 涉及) ，但是由于它的更具有普遍意义和商业价值。因此，把它作为本文的研究对象。可变性业务可重构疏导问题被分成两种疏导方案：最佳匹配