超立方体多计算机系统的一个高效故障诊断算法

超立方体是一类广泛应用的互连拓扑结构,具有可并行处理的某些性质.在MM*模型下,针对于超立方体多计算机系统的诊断问题,提出了一个快速诊断算法,可以正确诊断出系统中所有的故障结点,其时间复杂度为O(Nlog22N),N是处理器总数.     

一种高效的基于局部扭曲立方体的悲观诊断算法

悲观诊断与精确诊断相比,可以提高系统的自诊断能力。局部扭曲立方体是超立方体的一种变体,具有可并行处理的某些性质。在PMC模型下,研究了局部扭曲立方体的诊断问题,提出了一个O(Nlog_2N)的悲观诊断算法,N是处理器总数。经典的YML算法所需时间为O(N~(2.5)),因此,该算法在时间复杂度方面是高效的。     

具有扩展局部连通性超立方体中的容错路由

在局部连通性的基础上,提出了针对超立方体网络Hn的扩展的局部k-维子立方体连通性概念,证明了具有扩展的局部k-维子立方体连通性的Hn中正确结点问是连通的;提出了超立方体网络Hn中基于扩展局部k-堆子立方体连通性的路由算法。     

k元n立方体网络的容错路由

本文提出了k元n立方的m子立方体连通图的定义,讨论了该图的连通性。利用k元n立方的m子立方体连通图的概念提出了可容纳大量错误结点的容错路由算法,并对算法的时间复杂度做了分析。     

确定周期序列k错线性复杂度的一个快速算法

文中提出GF(q)上计算周期为2pⁿ的序列k-错线性复杂度的一个快速算法(这里p和q是素数,并且q是一个模p²的本原根).新算法的计算复杂度为O(N)(这里N是序列的周期).     

具有大量错误结点的k元n立方体广播路由

本文在k元n立方的m子立方体连通图的基础上提出了可容纳大量错误结点的容错路由算法,并讨论了算法的时间步的上界。     

k-维子连通的超立方体中并行路由

本文在k-维子连通的超立方体网络的定义的基础上,构造任意两个结点U、V的min(dk(U),dk (V))条并行容错路由,同时讨论了每条路径的步长的上限。     

树形网络结构优化设计的新算法

本文提出了按约束条件进行树形计算机网络结构优化设计的两个新算法,即给定结点数N、每个结点的负载、链路的代价及链路的容量后,在符合某些约束条件下,求代价最小的树形拓扑结构。两个新算法的计算复杂性均为O(N~2),计算结果表明,新算法所得的结果与现有最好的试探算法相当,而计算的复杂性比现有算法小得多。     

基于增量二维主成分分析的非线性转子系统故障诊断方法

针对智能故障诊断实际应用中存在的故障样本难 以大量获取、面对新增故障类别需要 一个完整的再训练周期的实时性等问题,提出一种采用增量二维主成分分析(incremental t wo-dimensional principal component analysis,I2DPCA)对非线性裂纹转子系统进行故 障 诊断的方法。首先构建水平支撑的非线性裂纹转子系统模型及其动力学方程,分别探究不同 裂纹深度和质量偏心参数时系统振动响应的变化特征。其次将时域振动信号归一化为图像样 本,由I2DPCA算法提取具有高判别力的低维故障特征。在上述处理基础上,使用k-最近邻( k-nearest neighbor,KNN)分类算法进行识别率的计算。数值仿真及相关实验的研究结果 表 明,基于I2DPCA算法的故障诊断方法可以在高速区域及小样本情形下有效地区分不同故障状 况的信号,为裂纹转子系统的早期故障诊断提供了新的检测策略。     

交换超立方体的拓扑性质与嵌入问题研究

 交换超立方体(Exchanged hypercube)作为超立方体的一种变型网络,降低了网络规模增大时所需要的拓扑连接的开销.本文根据交换超立方体的图形化定义,得到交换超立方体的公式化定义,证明了交换超立方部分子网与超立方网同构,提出EHS(s,t)和EHT(s,t)的概念,并在此概念的基础上证明了交换超立方体中只存在长度不小于4的偶数圈,证明了交换超立方体的顶点连通度和边连通度都为min{s+1,t+1}.为使交换超立方体具有更广阔的应用范围,本文还提出了超立方体在交换立方网中的三种嵌入策略,证明了n=s+t+1时,n-1维超立方体Q_n-1能够同胚地嵌入到交换超立方体EH(s,t)中.     

一个基于并行集团的系统级故障概率诊断算法

概率诊断算法是系统级故障诊断研究的一个重要方面,本文提出了一种基于并行集团的概率诊断算法-PGSFPD算法,并设计了一个系统级故障诊断软件仿真系统,对诊断算法进行仿真,分析比较各算法的性能,仿真结果表明PGSFPD算法性能优于经典的概率诊断算法-Somani & Agrawal算法,可在只需较少测试数的情况下,在保持很高诊断正确率的同时,大大降低系统的规模.     

A Method for Evaluating All the Minimal Cuts of a Graph

This paper presents a new technique to determine all minimal cuts for all the sink nodes in a non-planar network. The algorithm uses a subset method and an iterative process to achieve high efficiency. For an N-sink node network there are (2N - 1) possible combinations of nodes (non-empty subsets). These subsets are checked against several conditions to see if they can be transformed into minimal cutsets. An iterative process is used to generate these non-empty subsets efficiently so that the number of subsets to be checked is about (2N - 1)/2. Since this algorithm generates all the minimal cutsets for all nodes in one operation, it is faster compared to conventional methods which compute for one sink node at a time. Tests using random graphs showed a small cpu time per minimal cutset.     

On-line routing and wavelength assignment for dynamic traffic in WDM ring and torus networks

We develop on-line routing and wavelength assignment (RWA) algorithms for WDM bidirectional ring and torus networks with N nodes. The algorithms dynamically support all k-allowable traffic matrices, where k denotes an arbitrary integer vector [k/sub 1/, k/sub 2/,... k/sub N/], and node i, 1 /spl les/ i /spl les/ N, can transmit at most k/sub i/ wavelengths and receive at most k/sub i/ wavelengths. Both algorithms support the changing traffic in a rearrangeably nonblocking fashion. Our first algorithm, for a bidirectional ring, uses [(/spl Sigma//sub i=1//sup N/ k/sub i/)/3] wavelengths in each fiber and requires at most three lightpath rearrangements per new session request regardless of the number of nodes N and the amount of traffic k. When all the k/sub i/'s are equal to k, the algorithm uses [kN/3] wavelengths, which is known to be the minimum for any off-line rearrangeably nonblocking algorithm. Our second algorithm, for a torus topology, is an extension of a known off-line algorithm for the special case with all the k/sub i/'s equal to k. For an R /spl times/ C torus network with R /spl ges/ C nodes, our on-line algorithm uses [kR/2] wavelengths in each fiber, which is the same as in the off-line algorithm, and is at most two times a lower bound obtained by assuming full wavelength conversion at all nodes. In addition, the on-line algorithm requires at most C - 1 lightpath rearrangements per new session request regardless of the amount of traffic k. Finally, each RWA update requires solving a bipartite matching problem whose time complexity is only O (R), which is much smaller than the time complexity O(kCR/sup 2/) of the bipartite matching problem for an off-line algorithm.     

基于采样的大规模图聚类分析算法

针对当前聚类方法（例如经典的GN算法）计算复杂度过高、难以适用于大规模图的聚类问题，本文首先对大规模图的采样算法展开研究，提出了能够有效保持原始图聚类结构的图采样算法（Clustering-structure Representative Sampling，CRS），它能在采样图中产生高质量的聚类代表点，并根据相应的扩张准则进行采样扩张.此采样算法能够很好地保持原始图的内在聚类结构.其次，提出快速的整体样本聚类推断（Population Clustering Inference，PCI）算法，它利用采样子图的聚类标签对整体图的聚类结构进行推断.实验结果表明本文算法对大规模图数据具有较高的聚类质量和处理效率，能够很好地完成大规模图的聚类任务.     

Fast Distributed Algorithms for Computing Separable Functions

The problem of computing functions of values at the nodes in a network in a fully distributed manner, where nodes do not have unique identities and make decisions based only on local information, has applications in sensor, peer-to-peer, and ad hoc networks. The task of computing separable functions, which can be written as linear combinations of functions of individual variables, is studied in this context. Known iterative algorithms for averaging can be used to compute the normalized values of such functions, but these algorithms do not extend, in general, to the computation of the actual values of separable functions. The main contribution of this paper is the design of a distributed randomized algorithm for computing separable functions. The running time of the algorithm is shown to depend on the running time of a minimum computation algorithm used as a subroutine. Using a randomized gossip mechanism for minimum computation as the subroutine yields a complete fully distributed algorithm for computing separable functions. For a class of graphs with small spectral gap, such as grid graphs, the time used by the algorithm to compute averages is of a smaller order than the time required by a known iterative averaging scheme.     

Connected dominating sets in disk graphs with bidirectional links

In this paper, we study the connected dominating set (CDS) problem in disk graphs. The CDS problem has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in unit disk graphs, in which each node has the same transmission range. However, in wireless ad hoc networks, the transmission ranges of all nodes are not necessary equal. In this paper, we introduce the CDS problem in disk graphs and present a constant approximation algorithm which can be implemented as a distributed algorithm.     

On the optimality of solutions of the max-productbelief-propagation algorithm in arbitrary graphs

Graphical models, such as Bayesian networks and Markov random fields (MRFs), represent statistical dependencies of variables by a graph. The max-product “belief propagation” algorithm is a local-message-passing algorithm on this graph that is known to converge to a unique fixed point when the graph is a tree. Furthermore, when the graph is a tree, the assignment based on the fixed point yields the most probable values of the unobserved variables given the observed ones. Good empirical performance has been obtained by running the max-product algorithm (or the equivalent min-sum algorithm) on graphs with loops, for applications including the decoding of “turbo” codes. Except for two simple graphs (cycle codes and single-loop graphs) there has been little theoretical understanding of the max-product algorithm on graphs with loops. Here we prove a result on the fixed points of max-product on a graph with arbitrary topology and with arbitrary probability distributions (discrete- or continuous-valued nodes). We show that the assignment based on a fixed point is a “neighborhood maximum” of the posterior probability: the posterior probability of the max-product assignment is guaranteed to be greater than all other assignments in a particular large region around that assignment. The region includes all assignments that differ from the max-product assignment in any subset of nodes that form no more than a single loop in the graph. In some graphs, this neighborhood is exponentially large. We illustrate the analysis with examples     

Duality and Rate Optimization for Multiple Access and Broadcast Channels With Amplify-and-Forward Relays

In this paper, we consider multihop multiple access (MAC) and broadcast channels (BC) where communication takes place with the assistance of relays that amplify and forward (AF) their received signals. For a two-hop parallel AF relay MAC, assuming a sum power constraint across all relays we characterize optimal relay amplification factors and the resulting optimal rate regions. We find the maximum sum rate and the maximum rate for each user in closed form and express the optimal rate pair (R₁, R₂) that maximizes mu₁R₁+mu₂R₂ as the solution of a pair of simultaneous equations. We find that the parallel AF relay MAC with total transmit power of the two users P₁+P₂=P and total relay power P_R is the dual of the parallel AF relay BC where the MAC source nodes become the BC destination nodes, the MAC destination node becomes the BC source node, the dual BC source transmit power is P_R and the total transmit power of the AF relays is P. The duality means that the rate region of the AF relay MAC with a sum power constraint P on the transmitters is the same as that of the dual BC. The duality relationship is found to be useful in characterizing the rate region of the AF relay BC as the union of MAC rate regions. The duality is established for distributed multiple antenna AF relay nodes and multiple (more than 2) hops as well.     

Connectivity Based k-Hop Clustering in Wireless Networks

In this paper we describe several new clustering algorithms for nodes in a mobile ad hoc network. The main contribution is to generalize the cluster definition and formation algorithm so that a cluster contains all nodes that are at distance at most k hops from the clusterhead. We also describe algorithms for modifying cluster structure in the presence of topological changes. We also proposed an unified framework for most existing and new clustering algorithm where a properly defined weight at each node is the only difference in otherwise the same algorithm. This paper studied node connectivity and node ID as two particular weights, for k=1 and k=2. Finally, we propose a framework for generating random unit graphs with obstacles.