（计算机应用技术专业论文）基于wdm双环网的波长分配及网络嵌入算法研究.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的，本栏 可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：瑗碧刁 翩粹安1 矛暖 导师签字：了l 刁p j 呈 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂控可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：蚕舅石 一字：云) 身豫 签字日期：2 0 0 7 年s 月 1 日签字日期：2 0 0 年r 月1 日 山东师范大学硕士学位论文 基于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 ) 的全光网络已成为通信网络 的重要研究方向，也是未来最具潜力的通信网络。 由于现实中的技术限制，波长成为全光网络中最宝贵的资源。如果能够充分利用单根 光纤中可以同时传输多路波长信号的特性，把较为复杂的通信模式嵌入在简单的光互连网 络中，设计好的路由算法可以大大减少网络中所需的波长数，也可以通过优化设计大大简 化互连网络的结构。波长分配是光网络设计的基本问题。设计波长分配算法是洞察光网络 通信能力的基本方法，可以提高光网络中波长的利用率，改善整个网络的性能。已经证明 该问题在大多数网络结构中是n p 难的，所以对于这类问题具有重要的研究价值。 采用光互连网络作为并行体系结构的通信网络是发展的必然趋势。不同的并行算法具 有不同的通信模式，如何在光互连网上实现这些通信模式，是当前一个颇受关注的研究领 域。网络嵌入是互连网络研究的一个重要方向。高效的嵌入会提高并行程序的运行效率。 因此互连网络的嵌入问题也引起了研究者们的广泛关注。 双环网络( d o u b l e l 0 0 pn e t w o r k ，简称d l n ) 是一种重要的互连网络拓扑结构。它具有 对称性、简单性和可扩展性等优点，具有比环网更好的抗毁性能和更短的平均通信时间， 在计算机互连网络或分布式系统的拓扑结构中有很好的应用前景。 本文讨论了将几个重要并行算法的通信模式嵌入在w d m 双环网上的波长分配问题，其 中包括数值分析领域中最基本的矩阵乘问题、在数字信号处理及图像处理等领域中广泛应 用的快速傅立叶变换f f t 、人工神经网络中的b p 算法和h o p f i e l d 算法，并且讨论了两个网络 嵌入问题，其中包括双环网嵌入r p 网络和m e s h 嵌入双环网。 本文做的主要研究工作如下： ( 1 ) 分析了并行矩阵乘算法中的d d d 算法，基于w d m 双环网，提出了一种嵌入算法m r d r ， 在此基础上分析了在w d m 双环网上实现并行矩阵乘的波长分配问题，得到在此算法 中所需的最小波长数为2 ，并给出了理论证明。 山东师范大学硕士学位论文 ( 2 ) 分析了在数字信号处理、图像处理等领域有着广泛应用的快速傅立叶变换( f f a 3 。基于 w d m 双环网，提出一种递归的嵌入算法f f t - d l n ，针对四种基本嵌入算法生成法、 对折嵌入算法、顺序映射和逆序映射，得到在w d m 双环网上实现并行f f t 的通信模 式所需的波长数均为n 8 8 ) 。通过分析发现，对于相同规模的傅立叶变换，递归的 对折嵌入算法和逆序映射具有更短的执行时间。 ( 3 ) 分析了在联想记忆、模式识别等方面有着广泛应用的h o p f i e l d 网络模型。基于w d m 双环网，讨论了在其上实现h o p f i e l d 通信模式的波长分配问题，提出了一种路由策略 及波长分配方案，在此基础上给出了实现h o p f i e l d 算法所需的波长数。 ( 4 ) 分析了人工神经网络中的并行b p 算法。基于w d m 双环网，讨论了在其上实现并行 b p 算法的波长分配问题，提出了一种路由策略及波长分配方案并进行了仿真实验，对 实验结果进行了分析。 ( 5 ) 基于互连网络r p 和双环网，构造了1 0 * k 个节点的双环网结构，提出了一种将双环 网嵌入r p ( k ) 的算法d l n r p ，此算法得到的四个性能参数拓展、负载、延伸、拥挤 度分别为1 ，1 ，2 ，2 ，并证明了此结果为最优值。 ( 6 ) 设计了双环网的结构，讨论了将n * n 的m e s h 嵌入双环网的算法，证明了此算法得到的 四个性能参数分别为l ，1 ，1 ，1 ，即嵌入算法的最优值。 2 关键词：双环网；并行计算；光互连网络；波长分配；网络嵌入 分类号：t p 3 9 3 山东师范大学硕士学位论文 r e s e a r c ho nw a v e l e n g t h a s s i g n m e n ta n d n e t w o r ke m b e d d i n g b a s e do nw d md o u b l el o o pn e t w o r k s a b s t r a c t t h et r a d i t i o n a lc o m m u n i c a t i o nt e c h n o l o g yh a sb e e nd i 街c u l tt o s a t i s f yt h eg r o w t ho f i n f o r m a t i o nc a p a c i t y t h e nm a n yn e wc o m m u n i c a t i o nt e c h n o l o g i e sd i s a p p e a r e d a l l - o p t i c a l c o m m u n i c a t i o ni so n eo ft h o s et e c h n o l o g i e s ，a n dt h ew 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 ) t e c h n o l o g yh a sb e e nw i d e l ys t u d i e da n ds e l e c t e da st h ek e yt e c h n o l o g yf o rt h en e x tg e n e r a t i o n n e t w o r k ，b e c a u s eo f i t sa d v a n t a g e ss u c ha sh i g hb a n d w i d t ha n dl o wd e l a y b e c a u s eo ft h et e c h n i c a ll i m i t a t i o n , t h ew a v e l e n g t h sb e c o m et h em o s tp r e c i o u sr e s o u r c e so f a l l - o p t i c a ln e t w o r k s w i t ht h ed e v e l o p m e n to fw d mt e c h n o l o g y , w ec a nt a k ef u l la d v a n t a g e so f t h ep a r a l l e lt r a n s m i s s i o nc h a r a c t e r i s t i co fo p t i c a ln e t w o r k s ，w h i c hs u p p o r tm u l t i p l el i g h t p a t h si n t h es i n g l ef i b e r , t oe m b e dt h ec o m p l e xp a r a l l e lc o m m u n i c a t i o np a t t e r n si n t oo p t i c a ln e t w o r k s t h u s ，t h ep a r a l l e ln e t w o r kt o p o l o g i e sc a nb ec o n s i d e r a b l ys i m p l i f i e d w a v e l e n g t ha s s i g n m e n ti sa k e yt o p i ci no p t i c a lw d m n e t w o r k s t h ep u r p o s eo fw a v e l e n g t ha s s i g n m e n ti st oi n c r e a s et h e u t i l i z a t i o no f w a v e l e n g t ha n di m p r o v et h en e t w o r kp e r f o r m a n c e w a v e l e n g t ha s s i g n m e n tp r o b l e m w h i c hi sk n o w nt ob en p - h a r di sr e l a t i o n a lt ot h ec h r o m a t i cp r o b l e m t h e r e f o r e t h i sk i n do f p r o b l e mi so f g r e a tv a l u ef o rt h er e s e a r c ho nc o m p u t e rs c i e n c e o p t i c a lc o m m u n i c a t i o nb e c o m e sap r o m i s i n gn e t w o r k i n gc h o i c ef o rt h ei n t e r c o n n e c t i o n so f p a r a l l e la r c h i t e c t u r e s s i n c ed i f f e r e n tp a r a l l e la l g o r i t h m sh a v ed i f f e r e n tc o m m u n i c a t i o np a t t e r n s ， h o wt or e a l i z et h e s ec o m m u n i c a t i o np a t t e r n so no p t i c a li n t e r c o n n e e t i o n si sah o tr e s e a r c hf i e l d 1 1 地n e t w o r ke m b e d d i n gi sa l s oak e yt o p i co fi n t e r c o n n e c t i o nn e t w o r k s h i g h l ye f f e c t i v e e m b e d d i n g sc a ni m p r o v et h eo p e r a t i n ge f f i c i e n c yo f p a r a l l e lp r o g r a m s d l n ( d o u b l e - l o o pn e t w o r k ) i sa ni m p o r t a n ti n t e r e o n n e c t i o nn e t w o r kt o p o l o g y , w h i c hh a s m a n ya d v a n t a g e ss u c ha ss i m p l i c i t y , s y m m e t r y , e x t e n s i o ma n di th a sb e t t e rf a u l t - t o l e r a n c ea n d f e wa v e r a g ec o m m u n i c a t i o nt i m e i nt h i s p a p e r , w ed i s c u s s e dt h ew a v e l e n g t ha s s i g n m e n t so fe m b e d d i n gs e v e r a lp a r a l l e l c o m m u n i c a t i o np a t t e r n so nt h ed o u b l e - l o o pn e t w o r k , i n c l u d i n gt h ep r o b l e mo fp a r a l l e lm a t r i x m u l t i p l i c a t i o nf o rn u m e r i c a la n a l y s i sd o m a i n , f a s tf o u r i e rt r a n s f o r mf o rt h ed i g i t a ls i g n u l p r o c e s s i n ga n di m a g ep r o c e s s i n g ，b pa l g o r i t h ma n dh o p f i e l da l g o r i t h mi n a r t i f i c i a ln e u r a l n e t w o r k s t h en e t w o r ke m b e d d i n gi sa l s od i s c u s s e di nt h el a s tc h a p t e ro ft h i sp a p e r , i n c l u d i n g e m b e d d i n gd o u b l e - l o o pn e t w o r ko n t or p ( k ) a n de m b e d d i n gm e s ho n t od o u b l e - l o o pn e t w o r k t h em a i na e h i e v e m e n t so f t h i st h e s i sc a nb es u m m a r i z e da sf o l l o w s ： 3 山东师范大学硕士学位论文 ( 1 ) b a s e do nt h ew d md o u b l e l o o pn e t w o r k , t h ed d da l g o r i t h mo f p a r a l l e lm a t r i xm u l t i p l i c a t i o n i sa n a l y z e d t h ea l g o r i t h mm r d ri sd e s i g n e da n dt h ew a v e l e n g t ha s s i g n m e n to fr e a l i z i n g t h i sc o m m u n i c a t i o np a t t e r no nw d m d o u b l e - l o o pn e t w o r ki sd i s c u s s e d a n dt h em i n i l n u m n u m b e ro fw a v e l e n g t h sr e q u i r e dr e a l i z i n gt h i sc o m m u n i c a t i o np a r e r no nw d md o u b l e l o o p n e t w o r ki s2 ( 2 ) a nr e c u r s i v em a p p i n ga l g o r i t h mf f t - d l ni sg i v e n ，a n db a s e do ng e n e r a t i v em a p p i n g ，f o l i o m a p p i n g ，s e q u e n t i a lm a p p i n ga n dr e v e r s a lm a p p i n g ，w a v e l e n g t ha s s i g n m e n t so fr e a l i z i n g p a r a l l e lf f tc o m m u n i c a t i o np a t t e m so nw d md o u b l e - l o o pn e t w o r ka r ed i s c u s s e da n dt h e w a v e l e n g t hn u m b e r sr e q u i r e di sn 8 a n dt h r o u g ha n a l y s i s ，w ef i n dt h a tf o l i om a p p i n ga n d r e v e r s a lm a p p i n gh a v ef e wp e r f o r 幽gt i m ew i t ht h es a m en e t w o r ks c a l e ( 3 ) b a s e do nw d md o u b l e - l o o pn e t w o r k , w a v e l e n g t ha s s i g n m e n t so fr e a l i z i n gh o p f i e l dn e t w o r k o nw d m d o u b l e - l o o pn e t w o r ka r ed i s c u s s e d t h ec o m m u l l i c a t i o np a t t e r no f p a r a l l e lh o p f i e l d c ni si n 缸o d u c e d b ye m b e d d i n gt h ec o m p l e t eg r a p hc l ii n t ot h eo p t i c a lw d m d o u b l e - l o o p n e t w o r k , t h ew 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 sa r ed e s i g n e da n dt h en u m b e r so f w a v e l e n g t h s r e q u i r e dr e a l i z i n gh o p f i e l dn e t w o r k o nw d m d o u b l e l o o pn e t w o r k a r eg i v e n ( 4 ) b a s e do i lt h ew d md o u b l e - l o o pn e t w o r k , t h ew a v e l e n g t ha s s i g n m e n to fr e a l i z i n gp a r a l l e lb p a l g o r i t h mi nw d md o u b l e l o o pn e t w o r ki sd i s c u s s e dd u et ot h ep a r a l l e ln a t u r eo ft h e i n f o r m a t i o np r o c e s s i n gi na n n s b ye m b e d d i n gt h ec o m m u n i c a t i o np a t t e r no ft h ec o m p l e t e b i p a t t i r eg r a p hk i 蛐i n t ot h ew d md o u b l e l o o pn e t w o r k , ar o u t i n ga n dw a v e l e n g t h a s s i g n m e n ta l g o d t h mi sp r o p o s e d ，a n dt h er e s u l t sa g ea n a l y z e dv i as i m u l a t i o n ( 5 ) t h es t r u c t u r eo fd o u b l e - l o o pn e t w o r ki sd e s i g n e d 。a na l g o r i t h mo fe m b e d d i n g so fm e s ho n t o d o u b l e - l o o pn e t w o r ki sp r o p o s e d a n dt h ev a l u e so ff o u rp a r a m e t e r s ( e x p a n s i o n , l o a df a c t o r , d i l a t i o n , c o n g e s t i o n ) i sg i v e n , t h a ti s1 ，1 ，l ，1 ，w h i c hi so p t i m a l ( 6 ) t h ea r c h i t e c t u r eo ft h e1 0 + kd o u b l e - l o o pn e t w o r ki sd e s i g n e d , a n dt h ea l g o r i t h md l n r p a b o u tt h ee m b e d d i n g so fd o u b l e - l o o pn e t w o r ki n t op - p 0 0i sp r o p o s e d 1 1 1 ev a l u e so ff o u r p a r a m e t e r s ( e x p a n s i o n , l o a df a c t o r , d i l a t i o n , c o n g e s t i o n ) i sg i v e n , t h a ti sl ，1 ，2 ，2 ，a n dp r o v e n t d b e o p t i m a l 4 k e y w o r d s ：d o u b l e l o o pn e t w o r k , p a r a l l e lc o m p u t i n g ，o p t i c a l i n t e r c o n n c c t i o nn e t w o r k s ， w a v e l e n g t ha s s i g n m e n t , n e t w o r ke m b e d d i n g c l a s s 涵c a t i o n ：t p 3 9 3 山东师范大学硕士学位论文 第一章绪论 本章首先介绍了本文的研究背景、意义和研究现状，介绍了几个基本概念作为本文的 理论基础，同时引出本文所要讨论的问题，针对该问题，介绍了本文的基本内容和所做的 主要工作。 1 1 研究背景和意义 人类社会早已步入信息化时代，在这个时代人们对信息量的需求急剧增加，互联网上 的信息量也呈爆炸式增长，传统的通信技术已经很难满足不断增长的通信容量的要求。在 这种背景下，许多新兴的通信技术应运而生， 使用光纤作为传输介质进行通信的一种技术， 光通信技术就是其中的一种。光纤通信是指 它凭借光纤传输的高带宽、低延迟、传输透 明、抗电磁干扰等优点，成为最重要的通信技术之一。但在目前的光纤通信系统中，存在 着较多的光- 电、电光变换过程，而这些转换过程存在串扰、时钟偏移、高功耗等缺点， 在通信过程中很容易产生“信息瓶颈”现象。为了解决这一问题，产生了全光通信技术， 它是指数据从源节点到目的节点的传输过程都在光域内进行，传输过程中没有光电转换， 而其在各网络节点的交换采用全光网络交换技术，称这种技术为全光通信技术。而全光网 络就是在全光通信技术支持下的通信网络，它包括路由和波长分配两个基本问题。 基因测序、石油勘探、中长期气象预报、航天国防、核爆炸模拟、科学研究等行业需 要在高性能计算机的帮助下才能更好的完成工作。近几年，大规模事务处理、金融、政府 信息化、教育、企业、网络游戏等更广泛的领域对高性能计算的需求也迅猛增长。人类对 高性能计算能力的需求是永无止境的。并行计算是在并行计算机或分布式计算机等高性能 计算系统上所作的超级计算，是为了解决大规模、大数据量的大型科学计算而发展起来的 一门学科。由于种种因素的制约及使用计算机方式的改变，单台计算机系统的性能与功能 难以满足应用需求的情况下，由多个计算机节点经专门设计的互连网络紧密耦合而构成的 大规模并行处理系统，以及由多个自主的高性能节点经计算机网络连接组成的分布处理环 境，成为高性能计算机领域的重要研究方向。 近年来，基于波分复用( 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 l 】) 技术的全光网 已逐渐成为了通信网络的重要研究方向，波分复用技术将光纤中的带宽分成不同的通信信 道，不同的信道使用不同频率的波长进行通信，波分复用技术的使用使得光纤的传输速率 一下子跳跃到了t o p s 的范围。为此，采用波分复用技术的全光网成为互连网络的一个重要 5 山东师范大学硕士学位论文 研究方向。利用全光互连网络具有高宽带、低延迟等优点来进一步提高并行计算的速度有 着巨大的潜力，因此，光互连网络作为并行体系结构通信网络的发展趋势，引起学术界越 来越多的关注。全光网络中最基本也是最重要的问题就是波长分配问题，设计波长分配算 法是洞察光网络通信能力的基本方法。波长路由是指为每个通信请求分配一个路由，并 指定一个可用波长，波长分配算法的好坏直接影响到网络的性能。不同的并行算法具有不 同的通信模式，如何在光互连网络上实现这些通信模式并分析其波长分配问题，如何将不 同的通信模式嵌入在不同类型的光网络上使得嵌入所需的波长数目最优，是一个新的研究 课题。 网络嵌入嘲是互连网络研究的一个重要方向。高效的嵌入会提高并行程序的运行效率。 网络嵌入对于互连网络拓扑结构的研究有着重要的意义，通过网络嵌入可以用一种拓扑结 构模拟另一种结构。因此，互连网络上的嵌入问题引起研究者的广泛兴趣。随着波分复用 技术的发展，如果能够充分利用单根光纤中可以同时传输多路波长信号的特性，把较为复 杂的通信模式嵌入在简单的光互连网络中，可以通过优化设计大大简化互连网络的结构。 1 2 研究现状 对于光网络上的波长分配问题，已有很多结论。文献【3 】将h y p e r c u b e 通信模式嵌入到 线性阵列、环、m e s h 光网络结构中，分析了在其上实现h y p e r c u b e 通信模式的波长分配问 题，并给出了所需波长数。文献【4 】讨论了在光r p 网络上实现h y p e r c u b e 通信模式的波 长分配问题，同时得到了在环形光网络上实现n 维h y p e r e u b e 通信模式的波长分配算法， 并改进了文献 1 3 1 q b 的结论。文献 5 】基于顺序映射和移位逆序映射两种不同的嵌入方式， 分析了在一组规则w d m 光网络上实现并行f f t 的通信模式所需的波长数。文献【6 】基于 w d m 环网络，针对矩阵的并行l u 分解，构造了一种并行l u 分解的通信模式，讨论了将 通信模式嵌入在环形光网络中的波长分配问题。并在解决该问题的过程中，得到了将一种 特殊的二分图结构的通信模式嵌入在环网中的波长分配算法。文献【7 】给出了在线性阵列和 环形w d m 光网络上实现并行h o p f i e l d 通信模式所需波长数的下限值，分别设计了将并行 h o p f i e l d 通信模式嵌入在线性和环形w d m 光网络上的波长分配方案并给出了在该方案下 实现h o p f i e l d 网络所需的波长数。 对于网络嵌入问题，目前也有大量的结论璐4 ，这些研究集中在如何提高网络嵌入的 效率，衡量网络嵌入效率的参数通常有负载( l o a d ) 、拓展( e x p a n s i o n ) 、延伸( d i l a t i o n ) 、拥 挤度( c o n g e s t i o n ) ，大部分研究集中在m e s h 、环、h y p e r c u b e 、树和s t a r - g r a p h 等常用互连 6 山东师范大学硕士学位论文 网络拓扑结构的嵌入问题。还有很多文献讨论嵌入的容错问题【1 2 1 。文献【1 3 】讨论了将环和 二维m e s h 嵌入r p 网络的算法。文献【1 4 】讨论了超级交叉立方体互连网络上的圈嵌入问 题 。 虽然对于互连网络的嵌入问题和光网络波长分配的研究已经有了大量的结果，但从优 化光网络使用波长数的角度来分析嵌入问题还是一个新的研究方向，目前的结论还相对较 少，很多有意义的问题值得我们继续去研究和探讨。 1 3 理论基础 为了后文分析方便，下面我们给出有关的基本概念和基础知识。 1 3 1 并行计算 并行计算f 1 5 , 1 6 , 1 7 】是在并行计算机或分布式计算机等高性能计算系统上所做的超级计 算，是为了解决大规模、大数据量的大型科学计算而发展起来的一门学科，在很多重要的 领域里有着关键性的作用。一般将并行计算分为三部分：并行体系结构、并行算法和并行 程序设计，其中并行体系结构是并行计算的硬件基础，并行算法是并行计算的核心，并行 程序设计是并行计算的软件支持。这三者是相互关联的，在并行计算的几十年历史里都得 到了极大的发展。 并行体系结构研究的一个重要内容就是系统的互连网络，也就是如何将并行机系统中 的多个处理单元连接起来，实现处理单元之间的通信。互连网络可以分为两类：静态互连 和动态互连。在静态互连中处理单元间是固定连接的，在程序执行期间，这种点到点的连 接保持不变，常见的结构有一维线性阵列、二维网孔、树形连接、超立方体等，其中尤以 一维线性和二维网孔结构最为常见：相反，动态互连是由开关单元构成的，连接方式可以 按照应用程序的要求动态改变，典型的方式包括总线、交叉开关和多级互连网络。 随着光通信技术的发展，光通信技术不仅在电信网络和分布式的计算机网络中得到研 究和应用，同样也被应用于紧耦合的并行计算机中。由于这类网络具有强大的通信能力， 使得在它们上面设计出了很多高效的并行算法，甚至在很多方面算法的性能超过了经典的 理论模型p r a m ，而相对于p r a m 模型，这类网络又更易于实现，所以对于这类网络的研 究有重要的理论和实用价值。 7 山东师范大学硕士学位论文 1 3 2 双环网 双环网络【1 8 ，1 蚣o 】( d o u b l e l o o pn e t w o r k ，简称d l n ) 是- - 种重要的互连网络拓扑结构。 双环网络实质上是在环网的拓扑基础上构建的，它具有对称性、简单性和可扩展性等优点， 具有比环网更好的抗毁性能和更短的平均通信时间，在计算机互连网络或分布式系统的拓 扑结构中有很好的应用前景。近年来，对双环网络的研究主要集中在寻找紧优双环网络无 图1 1g ( 6 ：1 。2 ) 限族、对双环网络进行最优设计、寻径策略和算法等领域。 双环网的图论模型g ( n ；r ，d ：对于n 个节点o ，1 2 行一l ，从任一节点i 有且仅有一条 指向节点i + r ( m o d n ) 及一条指向节点f s ( m o d n ) 的弧( 分别称为【州边、【s 】边) ，其中，和j 是满足1 ，5 5 的情形) 的双环网结构，有以下定义： 山东师范大学硕士学位论文 双环网络中【+ 1 】边组成个环结构，称其为外环：【+ h 】边所组成的环称为内环q 为步长值) ， 网络中的节点沿着【+ 1 】边按顺时针编号，在有n 个节点的双环网中，节点依次编号为 0 ，1 2 以- 1 ； ( 1 ) 当n 为奇数时，构造双环网的网络结构为g ( 刀；1 ，b ，2 b ，这种构造方式使得内环也 构成一个环结构。例如当n = 7 时，g ( 7 ；1 ，3 ) 如图3 _ 3 所示，由外环o - l - 2 3 年5 - 6 - o 和内环 o 3 6 - 2 5 i - - 4 0 组成。 ( 2 ) 当n 为偶数时，构造双环网的网络结构为g ( n ；l ，2 ) ，在这种构造方式下存在一个外 环和两个内环，奇数编号的节点和偶数编号的节点分别构成一个环结构，分别称为偶内环 和奇内环。例如当n = 8 时，g ( s ；i ，2 ) 如图3 4 所示，外环为o 1 - 2 - 3 4 - 5 670 ，内环分别为 0 2 - 4 6 0 和1 3 5 ，1 。 圆：t 图3 3g ( 7 ；1 ，3 )图3 4g ( 8 ：i 2 ) 3 1 4c n 通信模式在w d m 双环网上的波长分配算法 根据前面所构造的双环网结构，分别提出一种路由策略及波长分配算法，并给出采用 这种策略所使用的波长数。由前面的定义，将双环网络划分为共享节点的多个环结构，分 别在这些环上进行路由和波长分配。 ( 1 ) 当n 为奇数时。构造的双环网结构为g ( 疗划n 26 ，网络中的所有链路构成一个外 环和一个内环。将n 个节点分为两组：偶数编号的节点为一组，奇数编号的节点为一组， 并且两组的节点个数分别为型n - 一i 。偶数编号的节点之间在内环上进行通信，奇数编号 22 的节点之间也在内环上进行通信，而偶数编号的节点与奇数编号的节点之间通过外环进行 通信。在每一个环上通信时采用文献【7 】中提出的奇偶最短路径策略，波长分配也采用本文 山东师范大学硕士学位论文 献中的策略，请参考文献 7 】，此处略。 ( 2 ) 当n 为偶数时，构造的双环网络结构为g ( n ；1 ，2 ) ，网络中所有的链路构成一个外环 和两个独立( 即无共享链路和节点) 的内环。将n 个节点分为两组：偶数编号的节点为一组， 奇数编号的节点为一组，并且两组的节点个数都为昙。偶数编号的节点之间在偶内环上进 二 行通信，奇数编号的节点之间在奇内环上进行通信，而偶数编号的节点与奇数编号的节点 之间通过外环进行通信。在每一个环上通信时采用文献 7 1 q = 提出的奇偶最短路径策略，波 长分配也采用本文献中的策略。 定理l 采用上述路由策略及波长分配算法，将c l i 通信模式嵌入w d m 双环网所需的波长 数为 w ( d l n ， 。良 证明：首先假设在外环上建立所有的连援，然后按照上画绳出趵蹯由策略，将一邵分惩援 请求转移到内环上。针对n 在不同情形下的双环网结构分析如下： ( 1 ) 当n 为奇数时，按照前面所述的分组方式，每一组节点都几乎均匀的分布在每一 个环结构上，据4 1 中所述各条链路上所分配波长的特点可以得出，内环上所需的波长数 为两个分组所需波长数的总和，外环上所需的波长数为! - 内环上的所需波长数根据 三竽，_ n - 广i 的不同情形又分为两种情况： 当三竽为偶数，_ n - _ 1 为奇数时，内环共用波长数为 b 嘲屯七嘲司= 警 此时外环所用波长数为t n 2 - i 一号竽= 止竽。 因为竺垫! ! 二垫二! ，所以在这种情形下，w d m 双环网上所需的波长数为 山东师范大学硕士学位论文 疗+ 2 n + 1 1 f 一 当_ n + - l 为奇数，_ n - - 1 为偶数时，内环共用波长数为 b 嘲 嘲啦嘲司= 一n 2 + 2 n - 3 此槲环翩波长数为丁n 2 - - 1 一学= 气竽。 因为b 2 + 2 n - 3 ! 二垫! ，所以在这种情形下，w d m 双环网上所需的波长数为 1 61 6 生垫二! 1 6 ( 2 ) 当n 为偶数时，按照前面所述的分组方式，每一组节点都均匀的分布在每一个环 结构上，据4 1 中所述各条链路上所分配波长的特点可以得出，两个内环上所需的波长数 相等，外环上所需的波长数为n 2 f + 2 n 两个内环上的所需波长数。根据兰的不同情形分为 两种情况： 当兰为徽时，每一个内环所需波长数为 1 i 詈1 2 + 矧 - 警 又两个内环是相互独立的，所 n 2 3 + 2 4 n - ，但在外环上却减少 了此值的两倍， i on 2 l + ，4 n 0 - ，所以外环所用波长数为蔓专翌一生素丝= 吾0 。 l5l oi 因为生1 6 百n 2 + 4 n ，所以在这种情形下，w d m 双环网上所需的波长数为吾6 3 2 l 当蛸2 奇数时铲伸环所需、波长数为l 2 一斗一n 2 - 4 3 2 8l2j8l 同理，两个内环所用波长数仍为百n 2 - 4 。外环的通信节点之间不存在距离为直径的通 信边，且奇数编号的节点与偶数编号的节点正好交叉分布，符合文献【7 】中在环网上实现并 山东师范大学硕士学位论文 波长分配策略，由文献【7 】中的结论得出外环上所需的波长数为丢( 訇2 + ；= 生素坚。 因为n2l+612盟，所以在这种情形下，wdm双环网上所需的波长数为n2l+61232 。 1 6 1 6 因此，定理1 成立。 3 1 5 结论 将本文结果与文献【7 】在环网上实现h o p f i e l d 网所需的波长数作比较，见表3 1 ，可以 发现，双环网上所需波长数近似为环网上的一半。尽管双环网所使用的光纤数恰是环网的 两倍，但因目前有限的技术水平导致波长资源的珍贵，这种代价是值得的。 表3 1双环网与环网所需波长数的比较 n567891 01 11 21 31 41 51 64 01 0 0 w ( r i n g n ，c n ) 3661 01 01 51 52 12 12 82 83 62 1 01 2 7 5 w ( d l n n 。c n ) 234467991 21 31 61 61 0 06 2 5 山东师范大学硕士学位论文 3 2 并行b p 算法在w d m 双环网上的波长分配 多层前馈网络的反向传播学习算法( b a c k p r o p a g a t i o n a l g o r i t h m ，简称b p ) 是一种重要的 人工神经网络学习算法，它已广泛用于各种诊断、预测、识别、工业控制等方面，是应用 最广泛的a n n 模型之一，如图3 5 所示。但是，由于该算法运算量大，特别是训练样本较 多时，无法满足实时运算的要求，因此不得不借助于并行处理机来虚拟实现神经网络。在 神经计算机中，随着神经元数目的增加，神经元之间连接数目会很快增加到不能容忍的地 输入层l i 隐含层曲 输出层k 图3 5b p 网络不意图 步。例如由1 0 4 个神经元构成的神经网络可能需要1 0 8 根连线，这样大的数目，用现有的技 术很难实现。在光纤通信中，采用波分复用的全光网是目前互连网络的一个重要研究方向， 利用全光互连网络具有高带宽、低延迟等优点来进一步提高大规模并行计算的速度有着巨 大的潜力。 在光网络的各种拓扑结构中，双环网络( d o u b l e - l o o p n e t w o r k ) 是一类重要的拓扑结构。 双环网络实质上是在环网的拓扑基础上构建的，它具有对称性、简单性和可扩展性等优点， 具有比环网更好的抗毁性能和更短的平均通信时间，因此被广泛用于计算机互连网络或分 布式系统的拓扑结构中。近年来，对双环网络的研究主要集中在寻找紧优双环网络无限族、 对双环网络进行最优设计、寻径策略和算法等领域【1 8 捌。 大量文献研究并行b p 算法【2 9 j ，本文基于w d m 双环网，讨论了在其上实现并行 b p 算法的波长分配问题，提出了一种路由策略及波长分配方案并进行了仿真实验，对实验 结果进行了分析与比较 3 2 1 并行b p 算法与k 。通信模式 文献 3 2 1 详细介绍t b p 厩j 络的组成、b p 算法的主要思想以及b p 网络运行的主要过程。 b p 网络包括输入层、隐含层和输出层三个部分，其中，输入层和输出层都只有一层，每层 3 l 山东师范大学硕士学位论文 有多个神经元。隐含层可以是一层，也可以是多层，各层含有多个神经元，且各层的神经 元数目可以相同，也可以不同，信号由输入层加权传到隐含层的第一层，经激励函数作用 后输出，其输出再经加权传至下一隐含层，由激励函数作用得到输出。如此下去，直到获 得最后一个隐含层的输出，再经加权传至输出层神经元，最后，经激励函数作用在输出层 得到实际输出结果。图3 5 是只含有一个隐含层的b p 网络示意图。 b p 算法的主要思想是把学习的过程分为两个阶段：正向传播阶段和反向传播阶段。其 中正向传播过程为：输入的样本从输入层经过隐单元一层一层进行处理，通过所有的隐含 层之后，传向输出层。在逐层处理的过程中，每一层神经元的状态只对下一层神经元的状 态产生影响。在输出层把现行输出和期望输出进行比较，如果现行输出不等于期望输出， 则进入反向传播过程。反向传播时，把误差信号按原来正向传播的通路反向传回并对每个