有固定波长转换器的全光环网波长分配算法

采用波分复用技术的全光网是目前宽带网络研究的方向之一,波长分配是其中主要的算法问题,具有重要的理论和应用价值.研究了具有任意固定波长转换器的环形光网上的波长分配问题.首先,提出了两个对环网上的请求集合预处理的算法,这两个算法可以将请求集合分解成一些连续的循环序列;然后,采用置换群来描述具有固定波长转换器的光环网,基于这种数学表示,提出了对环网上的波长信道进行分解的算法;基于这些算法,进一步提出了一个波长分配算法,该算法对于环形光网上的任意固定转换模式都能给出一个较好的波长分配方案.     

Optimal bandwidth utilization of all-optical ring with a converter of degree 4

In many models of all-optical routing,a set of communication paths in a network is given,and a wavelength is to be assigned to each path so that paths sharing an edge receive different wavelengths .The goal is to assign as few wavelengths as possible,in order to use the optical bandwidth efficiently.If a node of a network contains a wavelength converter,any path that passes through this node may change its wavelength .Having converters at some of the nodes can reduce the mumber of wavelengths required for routing,This paper presents a wavelength converter with degree 4and gives a routing algorithm which shows that any routing with load L can be realized with L wavelengths when a node of an all-optical ring hosts such a wavelength converter.It is also proved that 4 is the minimum degree of the converter to reach the full utilization of the available wavelengths if only one mode of an all-optical ring hosts a converter.     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

可重构造网孔机器上最小生成森林的边更新算法

最小生成森林的边更新在网络路由等方面有着重要的应用价值 .给定 n个结点的无向加权单图 G,该文首先在 n× n的二维可重构造网孔机器上提出了在 O(1)时间内判断 n个结点的无向图的连通性和在 O(logn)时间内求 n个结点的内向树中任一结点到根的路径两个算法 ,并在 n× n× n的三维可重构造网孔机器上提出了 O(1)时间内求 n个结点内向树中任一结点到根的路径的算法 .然后在上述算法的基础上提出了两个 G的最小生成森林的边更新算法 ,一个运行在 n× n的二维可重构造网孔机器上 ,时间复杂度是 O(logn) ,另一个运行在 n× n× n的三维可重构造网孔机器上 ,时间复杂度是 O(1) .     

网络最大流问题研究进展

网络最大流问题和它的对偶问题——最小截问题,是一对经典组合优化问题,它们在许多工程领域和科学领域有重要的应用,是计算机科学和运筹学重要的内容,最大流问题已经有40多年的研究历史,近年来,随着各种网络的飞速发展,最大流问题的研究也取得了很大的进展,对最大流问题研究做了详细的总结,并对下一步研究趋势进行了预测。     

一类实际网络中的最小截算法

讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n²logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.     

波分复用光传输网中波长路由算法的研究进展

光纤正迅速成为主干通信网的标准传介媒质．随着光学器件的发展，使得信号在传输过程中，除了在源、汇节点需要光电转换外，中间节点可保持光传输，这种通信网络叫光传送网．光传送网中的波分复用技术是将整个光纤的带宽分成多个信道，不同的信道可使用不同的波长来同时进行信息传输，从而增加了整个网络的带宽．在光传送网中，实现一个通信请求需要建立一条通信路径，并为该通信路径所经过的每条链上分配一个波长，即所谓波长路由．该文详细介绍了波分复用光传送网中波长路由算法的研究进展，内容包括波长分配算法、网络的信元阻塞率分析、容错和QoS波长路由、多播波长路由、最小化ADM数路由以及基于光或光电连接的并行机模型等．     

可重构造网孔机器上常数时间的最优异或算法及应用

逻辑异或和前缀异或是基本的逻辑运算 ,经常应用于各种算法中 .该文在规模为 N× N的可重构造网孔机器上提出了求 N个逻辑位的并行异或和并行前缀异或算法 ,其运行时间均为常数 .基于该并行异或算法 ,文中还提出了相同的模型下在常数时间判定一给定点是否在 N条边构成的平面多边形中和判定一给定点是否在 N个平面构成的空间多面体中的并行算法 .就实质而言 ,这些算法都是相应问题的第一个处理器数为线性、运行时间为常数的并行算法     

移动自组网中的最长生命期路径

动态拓扑是移动自组网区别于其他形式网络的本质特征,对其进行研究具有很大的理论价值和工业应用背景.提出一种方法,利用网络的最长生命期路径来研究其拓扑的动态性.在已有研究的基础上,改进了网络的数学模型,弥补了以往模型无法很好地描述移动自组网动态拓扑的缺陷,并在此基础上提出了最长生命期路贩径算法.利用该算法计算网络中的最长生命期路径,深入研究了其持续时间的分布规律.同时证明了使用最长生命期路径作为路由,可以使网络的重路由次数最少.模拟实验表明,利用对数正态分布可以很好地描述移动自组网的最长生命期路径持续时间.实验结果表明,与以往利用最短路径作为研究对象相比,最长生命期路径和最小重路由更适合用来衡量网络的动态性.     

可重构造网孔机器上简单多边形三角剖分的常数时间算法

简单多边形的三角剖分是计算几何的基本问题之一 ,在计算机图形学、地理信息系统及有限元方法等领域有许多重要的应用 .可重构造网孔机器是近几年出现的一种新的并行计算模型 ,由于其特有的灵活性 ,已经有很多领域的基本问题在这种模型上得到了研究 .该文在这种结构上考虑了简单多边形的三角剖分问题 :提出了一个将简单多边形分解为特殊单调多边形的算法 ,并在规模为 n× n的可重构造网孔机器上实现了常数时间分解单调多边形为特殊单调多边形的并行算法 ,基于这个算法得到了一个 n× n的机器上常数时间三角剖分单调多边形的算法 ;将这些算法稍加推广 ,并使用稍多的处理器 ,得到了一个在规模为 n× n1 ε(0 <ε<1为常数 )的可重构造网孔机器上三角剖分简单多边形的常数时间算法 .就目前了解到的情况而言 ,这分别是第一个在常数时间三角剖分单调多边形和简单多边形的并行算法