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

摘要

传统的通信技术已经很难满足不断增长的通信容量的要求.许多新的通信技术应运而生,全光通信凭借其高带宽、低延迟、抗干扰能力强等优点成为最重要的通信技术之一.而基于波分复用(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,即嵌入算法的最优值.