学位论文 > 优秀研究生学位论文题录展示

基于WDM双环网的波长分配及网络嵌入算法研究

作　者: 夏磊
导　师: 刘方爱
学　校: 山东师范大学
专　业: 计算机应用技术
关键词: 双环网并行计算光互连网络波长分配网络嵌入
分类号: TN929.1
类　型: 硕士论文
年　份: 2007年
下　载: 40次
引　用: 0次
阅　读: 论文下载

内容摘要

传统的通信技术已经很难满足不断增长的通信容量的要求。许多新的通信技术应运而生,全光通信凭借其高带宽、低延迟、抗干扰能力强等优点成为最重要的通信技术之一。而基于波分复用(Wavelength Division Multiplexing,简称WDM)的全光网络已成为通信网络的重要研究方向,也是未来最具潜力的通信网络。由于现实中的技术限制,波长成为全光网络中最宝贵的资源。如果能够充分利用单根光纤中可以同时传输多路波长信号的特性,把较为复杂的通信模式嵌入在简单的光互连网络中,设计好的路由算法可以大大减少网络中所需的波长数,也可以通过优化设计大大简化互连网络的结构。波长分配是光网络设计的基本问题。设计波长分配算法是洞察光网络通信能力的基本方法,可以提高光网络中波长的利用率,改善整个网络的性能。已经证明该问题在大多数网络结构中是NP难的,所以对于这类问题具有重要的研究价值。采用光互连网络作为并行体系结构的通信网络是发展的必然趋势。不同的并行算法具有不同的通信模式,如何在光互连网上实现这些通信模式,是当前一个颇受关注的研究领域。网络嵌入是互连网络研究的一个重要方向。高效的嵌入会提高并行程序的运行效率。因此互连网络的嵌入问题也引起了研究者们的广泛关注。双环网络(Double-Loop Network,简称DLN)是一种重要的互连网络拓扑结构。它具有对称性、简单性和可扩展性等优点,具有比环网更好的抗毁性能和更短的平均通信时间,在计算机互连网络或分布式系统的拓扑结构中有很好的应用前景。本文讨论了将几个重要并行算法的通信模式嵌入在WDM双环网上的波长分配问题,其中包括数值分析领域中最基本的矩阵乘问题、在数字信号处理及图像处理等领域中广泛应用的快速傅立叶变换FFT、人工神经网络中的BP算法和Hopfield算法,并且讨论了两个网络嵌入问题,其中包括双环网嵌入RP(k)网络和mesh嵌入双环网。本文做的主要研究工作如下:(1)分析了并行矩阵乘算法中的ddd算法,基于WDM双环网,提出了一种嵌入算法MRDR,在此基础上分析了在WDM双环网上实现并行矩阵乘的波长分配问题,得到在此算法中所需的最小波长数为2,并给出了理论证明。(2)分析了在数字信号处理、图像处理等领域有着广泛应用的快速傅立叶变换(FFT)。基于WDM双环网,提出一种递归的嵌入算法FFT-DLN,针对四种基本嵌入算法生成法、对折嵌入算法、顺序映射和逆序映射,得到在WDM双环网上实现并行FFT的通信模式所需的波长数均为N/8(N≥8)。通过分析发现,对于相同规模的傅立叶变换,递归的对折嵌入算法和逆序映射具有更短的执行时间。(3)分析了在联想记忆、模式识别等方面有着广泛应用的Hopfield网络模型。基于WDM双环网,讨论了在其上实现Hopfield通信模式的波长分配问题,提出了一种路由策略及波长分配方案,在此基础上给出了实现Hopfield算法所需的波长数。(4)分析了人工神经网络中的并行BP算法。基于WDM双环网,讨论了在其上实现并行BP算法的波长分配问题,提出了一种路由策略及波长分配方案并进行了仿真实验,对实验结果进行了分析。(5)基于互连网络RP(k)和双环网,构造了10*k个节点的双环网结构,提出了一种将双环网嵌入RP(k)的算法DLN-RP(k),此算法得到的四个性能参数拓展、负载、延伸、拥挤度分别为1,1,2,2,并证明了此结果为最优值。(6)设计了双环网的结构,讨论了将n*n的mesh嵌入双环网的算法,证明了此算法得到的四个性能参数分别为1,1,1,1,即嵌入算法的最优值。

全文目录

摘要  5-7
ABSTRACT  7-9
第一章绪论  9-16
  1.1 研究背景和意义  9-10
  1.2 研究现状  10-11
  1.3 理论基础  11-16
第二章并行数值算法在WDM 双环网上的波长分配  16-29
  2.1 并行矩阵乘在WDM 双环网上的波长分配  16-23
  2.2 并行FFT 的通信模式在WDM 双环网上的波长分配  23-29
第三章人工神经网络中的并行计算问题在WDM 双环网上的波长分配  29-41
  3.1 HOPFIELD 网络在WDM 双环网上的波长分配  29-35
  3.2 并行BP 算法在WDM 双环网上的波长分配  35-41
第四章双环网与其他网络结构间的网络嵌入  41-48
  4.1 MESH 嵌入双环网  41-43
  4.2 双环网嵌入RP(K)网络  43-48
第五章结论及进一步的工作  48-50
  5.1 本文的主要工作和创新点  48-49
  5.2 进一步的工作  49-50
论文作者在学期间发表的学术论文目录  50-51
参考文献  51-54
致谢  54

基于WDM双环网的波长分配及网络嵌入算法研究

内容摘要

全文目录

相似论文