P2-Packing问题参数算法的改进

P₂-Packing问题是一个典型的NP难问题.目前这个问题的最好结果是时间复杂度为O^*(2^5.301k)的参数算法,其核的大小为15k.通过对P₂-packing问题的结构作进一步分析,提出了改进的核心化算法,得到大小为7k的核,并在此基础上提出了一种时间复杂度为O^*(2^4.142k)的参数算法,大幅度改进了目前文献中的最好结果.     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2n个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,(5(2n?5/3(}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用(N/3+N/4(个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略

针对无线传感器网络中传输时延长、传输冲突大和吞吐量低等问题,提出了一种在Multi-Radio Multi-Channel无线传感器网络中信道分配和路由策略.该策略动态地建立k元n立方体拓扑结构,使用优化的静态信道分配算法提高节点的吞吐量,使用维序寻径的路由算法减少传输冲突.该方法适用于网络节点稠密、节点相互之间通信冲突大的情况,并且在单跳和多跳的网络环境下均适用.实验结果表明,基于k元n立方体这一拓扑结构的信道分配和路由策略与传统方法相比,有效地减少了端到端时延,降低了网络冲突,减少了节点能量消耗,延长了网络寿命,提高了网络吞吐量.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2^n/8)的处理机在O(2^7n/16)的时间和O(2^13n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(2^5n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

Multi-log2N交换网络的性能分析模型及控制算法

高速多平面交换网络解决了其内部冲突问题,但需要相应的路由控制算法的辅助,否则,内部冲突不能彻底解决.这是因为包在输入级路由平面的选择不够恰当,容易导致路由冲突的产生.因此,根据冲突链路集的思想,给出一种Multi-log₂N交换网络的控制算法.该算法控制分组在路由平面间的选择,不仅能够适用于RNB和SNB,还能实现单播和多播的控制,保障Multi-log₂N完全实现无阻塞.另一方面,Multi-log₂N消除了内部的链路冲突,提高了交换速率,但对其交换性能缺乏系统的理论分析.给出一种基于嵌入式马尔可夫链的分析模型,对Multi-log₂N网络中队列的使用及分组在队列中的平均等待时间、平均队长等相关性能指标进行了系统的分析,为基于Multi-log₂N的光交换节点的设计提供了良好的理论依据.     

改进k值自动获取VDBSCAN聚类算法

针对DBSCAN聚类算法不能对变密度分布数据集进行有效聚类,VDBSCAN算法借助k-dist图来自动获取各个密度层次的数据对象的邻域半径,解决了具有不同密度层次分布数据集的聚类问题. k-VDBSCAN算法通过对k值的自动获取,减小了VDBSCAN中参数k对最终聚类结果的影响. 针对k值的自动获取,在原有的k-VDBSCAN聚类算法基础上,依据数据集本身,利用数据对象间距离的特征,提出了一种k值改进自动获取聚类算法. 理论分析与实验结果表明,新的改进算法能够有效的自动获得参数k的值,并且在聚类结果、时间效率方面都有明显的提高.     

一类可分离SAT问题的O(1.890n)精确算法

布尔可满足性问题（SAT）是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题（k-SAT）,从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O（（2-2/k）ⁿ）,当k=3时,最好算法时间复杂度为O（1.308ⁿ）.而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足性问题（3-RSSAT）,证明了3-RSSAT是NP完全问题,给出了一般SAT问题3-正则可分离性的O（1.890ⁿ）判定算法.然后,利用矩阵相乘算法的研究成果,给出了3-RSSAT问题的O（1.890ⁿ）精确算法,该算法与子句长度无关.     

完全析取范式群判定SHOIN(D)-可满足性

针对非循环概念提出了一种对SHOIN(D)-概念可满足性进行判断的方法——CDNF(complete disjunctive normal form)算法.该算法通过把非循环定义的概念描述本身构建成分层次的析取范式群,并通过子句重用技术阻止无谓的子概念扩展,这样的析取范式群具有可满足性自明性,从而可以实现对SHOIN(D)-概念可满足性的直接判断.该算法基本上消除了判断过程中描述重复的现象,从而在空间、时间性能上都比Tableau算法有更好的表现.     

三维水下传感网相异k-覆盖改进虚拟力算法

水下传感器的覆盖控制研究对于合理分配网络的空间资源,更好地完成环境感知、信息获取任务以及提高网络生存能力都具有重要的意义.实际情况中,水下监测区域往往需要不均匀的覆盖.现有的研究偏重于“事件驱动”概念,但不同区域的不同k-覆盖需求并未得到重视.针对UWSNs 相异k-覆盖需求区域的覆盖优化部署这一研究方向,基于浮标、锚、与浮标通过有线电缆连接通信的水下传感器模型,分析了相异k-覆盖需求区域所需的节点数下限,提出了一种基于相异k-覆盖需求的改进虚拟力算法k-ERVFA(k-equivalent radius virtual force algorithm).仿真实验结果表明,相比经典的虚拟力算法,在相同最大迭代次数和相同节点数的情况下,该算法在牺牲1-覆盖需求区域的1-覆盖率仅1.21%~3.89%的情况下,能够同比提高相应区域的2-、3-覆盖率分别达到17.42%~44.3%和28.95%~49.53%,取得了很好的部署效果,说明了k-ERVFA 算法的正确性与有效性.     

A practical interconnection network RP(k) and its routing algorithms

Based on Petersen graph, a new interconnection network, the RP(k) network, is devel-oped and the properties of the RP(k) network are investigated. The diameter of the RP(k) network is [ k/2] + 2 and its degree is 5. We prove that the diameter of the RP(k) network is much smaller than that of the 2-D Torus network when the number of nodes in interconnection networks is less than or equal to 300. In order to analyze the communication performance in a group of nodes, we propose the concepts of the optimal node groups and the diameter of the optimal node groups. We also show that the diameter of the optimal node groups in the RP(k) network is less than that in the 2-D Torus net-work. Especially when the number of nodes in an optimal node group is between 6 and 100, the diam-eter of the optimal node groups in the RP(k) network is half of that in the 2-D Torus network. Further-more based on the RP(k) network we design a set of routing algorithms which are point-to-point rout-ing, permutation routing, one-to-al     

并行LU分解的通信模式在WDM环网上的波长分配算法

波长分配是光网络设计的基本问题，设计波长分配算法是洞察光网络通信能力的基本方法．不同的并行算法具有不同的通信模式，如何在光互连网上实现这些通信模式，是当前一个颇受关注的研究领域．本文基于WDM环网络，针对矩阵的并行LU分解，构造了一种并行LU分解的通信模式，讨论了将该通信模式嵌入在环形光网络中的波长分配问题．在解决该问题的过程中，得到了将一种特殊的二分图结构的通信模式嵌入在环网中的波长分配算法．通过分析和证明得到了在WDM环网上实现该并行LU分解通信模式所需的最小波长数．     

The embedding of rings and meshes into RP(k) networks

Copyright by Science in China Press 2004 Interconnection networks, as an important means in parallel processing systems, are investigated widely[1,2]. Recently a class of lower-degree networks is proposed[2—4]. In ref. [3] we have investigated a constant degree network, called RP(k) network. Com-pared with rings and 2-D mesh networks, the RP(k) network has many good properties. The RP(k) network has a much smaller diameter than that of 2-D meshes when the number of network nodes is less …     

一种实用的互联网络RPn(k)及其路由算法

基于环的简单扩展性和Petersen图的短直径,提出了一类新型互联网络RPn(k),研究了该互联网络的性质,它不但具有正则性和良好的可扩展性,还具有比RP(k)互联网络更短的网络直径、更好的可分组性以及更小的网络构造开销。最后,讨论了RPn(k)网络的路由问题,给出了点点路由算法,其通信效率为[k/2]+2n个时间步。在节点个数相同时,RPn(k)比RP(k)网络上的路由算法的通信效率有明显提高。     

一种在立方环网络上加总线的方法

本文提出一种在立方环网络（ＣＣＣ）上加总线的方法，对于小规模的ＣＣＣ网络，这种方法能使其直径降为３；而对于大规模的ＣＣＣ网络，能使其直径降为原来的２／３以下，并且还可以使网络中各结点的度降为≤２。     

并行BP算法在WDM环网上的波长分配

波长分配是光网络设计的基本问题,设计波长分配算法是洞察光网络通信能力的基本方法。不同的并行算法具有不同的通信模式,如何在光互联网上实现这些通信模式,同时优化波长分配问题,是当前一个颇受关注的研究领域。神经网络计算的一个重要特点是大规模并行计算,该文基于WDM环网络,讨论了在其上实现并行BP算法的波长分配问题,设计了将完全二分图结构Kmn,通信模式嵌入环网的方案,给出了在WDM环网络上实现并行BP算法所需的最小波长数。     

双环网嵌入RP(k)网络

网络嵌入是互连网络研究的一个重要方向,通过网络嵌入可以用一种拓扑结构模拟另一种结构,高效的嵌入会提高并行程序的运行效率。构造了10*k个节点的双环网结构,基于文献[3]提出的互连网络RP(k),提出了一种将双环网嵌入RP(k)的算法DLN-RP(k),此算法得到的4个性能参数为拓展、负载、延伸、拥挤度分别为1,1,2,2,并证明了该结果为最优值。     

基于超立方体环连接的Petersen图互联网络研究

基于环的简单扩展性，Petersen图的短直径与超立方体互联网络中节点的高可连接性相结合，提出了一种新型互联网络RHP(n)(Ringed Hypercube Connected Petersen)，并对其特性进行了研究．证明了RHP(n)网络不但具有正则性以及良好的可扩展性，同时还具有比Q、HP(n)网络更短的直径和更小的构造开销．另外，还基于RHP(n)网络分别给出了其上的单播和广播路由算法，证明了其通信效率分别为n-1和n-1．     

FFT通信模式嵌入环形光网络及其性能分析

在分析互连网络的性能时常常利用一些特殊的通信模式。而快速傅立叶变换(FFT)在数字信号处理、概率论等领域中具有非常广泛的应用。因此,该文针对FFT的Cormen并行迭代算法中的通信模式,提出两种嵌入算法,将其嵌入环形光网络中。并且分析了在这两种嵌入方式下,FFT算法在环形光网络中的拥挤度和时间复杂度。并对这两种算法进行了比较。最后,得到利用上面的嵌入算法将蝶形网络嵌入环形光网络的嵌入方法并分析了其嵌入拥挤度。     

A spanning multichannel linked hypercube: a gradually scalableoptical interconnection network for massively parallel computing

A new, scalable interconnection topology called the Spanning Multichannel Linked Hypercube (SMLH) is proposed. This proposed network is very suitable to massively parallel systems and is highly amenable to optical implementation. The SMLH uses the hypercube topology as a basic building block and connects such building blocks using two-dimensional multichannel links (similar to spanning buses). In doing so, the SMLH combines positive features of both the hypercube (small diameter, high connectivity, symmetry, simple routing, and fault tolerance) and the spanning bus hypercube (SBH) (constant node degree, scalability, and ease of physical implementation), while at the same time circumventing their disadvantages. The SMLH topology supports many communication patterns found in different classes of computation, such as bus-based, mesh-based, and tree-based problems, as well as hypercube-based problems. A very attractive feature of the SMLH network is its ability to support a large number of processors with the possibility of maintaining a constant degree and a constant diameter. Other positive features include symmetry, incremental scalability, and fault tolerance. It is shown that the SMLH network provides better average message distance, average traffic density, and queuing delay than many similar networks, including the binary hypercube, the SBH, etc. Additionally, the SMLH has comparable performance to other high-performance hypercubic networks, including the Generalized Hypercube and the Hypermesh. An optical implementation methodology is proposed for SMLH. The implementation methodology combines both the advantages of free space optics with those of wavelength division multiplexing techniques. A detailed analysis of the feasibility of the proposed network is also presented