LHL-立方体互连网络及其性质

并行计算系统一直是计算机科学中的重要研究领域,其互连网络的拓扑性质对整个网络的性能起着非常重要的作用.目前已经提出多种互连网络,其中超立方体具有对数级的直径、高连通度、对称性等很好的性质,故被用作多种并行机的处理器连接的拓扑结构.然而,超立方体并非所有性质都是最优的互连网络,且超立方体的许多变型结构具有许多比超立方体更好的性质,其中已经证明了局部扭立方体在直径、Hamilton连通性等方面都优于超立方体.给出在超立方体与局部扭立方体的顶点间的一种连接方式--超连接,从而得到一种称为LHL-立方体的新型网络,并对这种网络的以下性质进行了研究:顶点连通度、边连通度、Hamilton连通性、直径.研究结果表明,一个n维LHL-立方体是一个具有2n个顶点和n2n-1条边的n-正则图,n维LHL-立方体的顶点连通度和边连通度均为n,且是Hamilton连通的,直径上界为[n/2 ]+3.     

HCH-立方体的Hamilton连通性

新型并行计算系统的研制依赖于对新型互连网络结构及其性质的研究。超立方体及其变型——交叉立方体具有优点,也具有缺点。文献[1]给出了在超立方体与交叉立方体的顶点之间的一种连接——超连接,从而得到了一种称为HCH-立方体的互连网络,文章证明了当n≥4,HCH-立方体任意两个顶点之间存在Hamilton路径,即HCH-立方体是Hamilton连通的,而超立方体不是Hamilton连通的。这表明HCH-立方体具备了交叉立方体在Hamilton连通性方面的性质。文章还给出了在n维HCH-立方体中构造任意两个顶点之间Hamilton路径的算法,该算法的时间复杂度为O(N),其中N=2n,为n维HCH-立方体的顶点个数。     

泡形互连网络的条件连通性度量

n维泡形网络是设计大规模多处理机系统时最常用的互连网络拓扑结构之一,它以n维泡形图Bn为数学模型。F是连通图G的顶点子集,使得G-F不再连通且G-F的每个连通分支都有至少有n个顶点的F的势叫做G的Rk连通度。Rk连通度是衡量网络可靠性的一个重要参数。一般来说,网络的Rk连通度越大,其可靠性越高。研究了n维泡形网络的 k连通性;证明了在n维泡形网络中,当n≥3时,其R1连通度为2n-4;当n≥4 时,其R2连通度为4n-12。     

在PMC模型下单向k元n立方体的诊断度

图的连通度和诊断度是与互连网络的可靠性密切相关的两个参数,而[g]好邻连通度和[g]好邻诊断度是比连通度和诊断度更精确的指标。[k]元[n]立方体是多处理机系统的最常用网络之一,而单向[k]元[n]立方体是指具有单向边的[k]元[n]立方体。证明了当[k≥3,n≥3]时,单向[k]元[n]立方体在PMC模型下的[1]好邻连通度是[k(n-1)],诊断度是[n]且[1]好邻诊断度是[kn-1]。     

超立方体中基于极大安全通路矩阵的容错路由

n维超立方体结构的多处理机系统在并行与分布式处理中具有良好的性能,随着多处理机系统规模的增大,系统出现链路与节点故障的概率也随之增大,因此设计容错性更强的路由算法对n维超立方体结构的多处理机系统具有重要意义.针对超立方体结构的多处理机系统中存在链路故障的情况,提出了用于最优通路记录的极大安全通路矩阵(maximum safety path matrices,简称MSPMs)这一概念,给出了一种建立MSPMs及其容错路由算法.证明了MSPMs通过n-1轮邻节点之间的信息交换,能以矩阵的形式记录最多的最优通路     

交叉扭立方体互联网络及其性质

扭N立方体是近年来提出的一种新型变体网络结构.通过X-变换操作使得存在2n个顶点的超立方体的网络直径从N减少到N-1,减少了网络规模增大时所需要的网络开销,从而受到了广泛的欢迎.与超立方体一样,扭N立方体也存在缺点,如果增加扭N立方体的维数,会成倍增加扭N立方体的顶点个数.为了解决这一问题,本文通过扭N立方体的结构,提出了交叉扭立方体的定义,并给出了相应的拓扑结构网络图,证明了交叉扭立方体的部分子网与超立方体网络同构,同时研究了交叉扭立方体的网络直径、连通度等问题.通过上述拓扑结构的基本性质的研究,得到了交叉扭立方体的性能优于扭N立方体的重要结论.     

平衡超立方体的故障容错性

故障容错是衡量多处理器互连网络可靠性的重要方式之一。其中g-限制边连通度和g-限制连通度保证了剩下每个分支之间不连通且每个分支中节点的邻居数目不少于 g,能够更加精准地测量多处理器和多信道系统的容错性和可靠性。平衡超立方体是超立方体的一个变形,它特有的良好拓扑性质能够更好地满足多处理器系统和多种新型网络的需要。提出了n维平衡超立方体的{1,2}-限制边连通度和{1,2}-限制连通度,能够丰富以平衡超立方体为拓扑结构的网络容错性和可靠性的评价体系,并为平衡超立方体的故障诊断算法打下良好基础。     

超立方体网络下的自适应容错路由研究*

针对超立方体结构的多处理机系统出现故障的问题,对容错超立方体网络的局部连通性进行了研究。根据局部连通性的特点定义了相邻节点集合类的概念,提出并证明了求解两类相邻节点集合的公式。给出了满足任意子连通性条件的超立方体网络的自适应容错路由算法。该算法是分布式和基于局部信息的,可以预防死锁。仿真实验的结果表明算法是高效的,且构建的路径长度接近于最优路径长度。     

具有不连通子立方体的超立方体中广播路由

基于扩展的局部k—维子立方体连通的超立方体网络Hn,提出了超立方体网络Hn中新的广播容错路由算法。算法分析表明,基于扩展局部k—维子立方体连通的广播路由算法比基于局部k-子立方连通的广播路由算法提高了超立方体网络的容错性和通用性。     

扭立方体连接网络结构的研究与分析

根据交叉立方体（CQn）的结构与关联对的概念,对扭立方体连接网络（TNn）的结构特性进行了分析,证明了当[n5]时,TNn是不连通的,并且不连通的结点数占整个网络结点数的一半。通过分析扭立方体连接网络的错误所在,提出了一种新型网络结构——扭交叉立方体（TCQn）,证明了该网络结构是完全连通的,初步研究了其基本网络性质,如正则性,连通度,容错度,递归性等,表明TCQn具有与CQn同样优秀的网络性质。     

增广泡型网络的边连通性和限制边连通性

针对泡型网络边连通度和限制边连通度小、容错能力弱的弊端,采用在泡型网络中增加通信线路的方法构建了高可靠性的增广泡型网络。通过构造最小边割的方法,证实了n维增广泡型网络中去除任意不多于n-1条边时,该增广泡型网络的任意两个节点之间依旧连通;通过构造最小限制边割的方法,证实了在不产生孤立节点的条件下,n维增广泡型网络中去除任意不多于2n-3条边时,该增广泡型网络的任意两个节点之间依旧连通。依据上述结果,通过实例证明增广泡型网络的容错能力优于泡型网络。     

Causal connectivity of evolved neural networks during behavior

To show how causal interactions in neural dynamics are modulated by behavior, it is valuable to analyze these interactions without perturbing or lesioning the neural mechanism. This paper proposes a method, based on a graph-theoretic extension of vector autoregressive modeling and 'Granger causality,' for characterizing causal interactions generated within intact neural mechanisms. This method, called 'causal connectivity analysis' is illustrated via model neural networks optimized for controlling target fixation in a simulated head-eye system, in which the structure of the environment can be experimentally varied. Causal connectivity analysis of this model yields novel insights into neural mechanisms underlying sensorimotor coordination. In contrast to networks supporting comparatively simple behavior, networks supporting rich adaptive behavior show a higher density of causal interactions, as well as a stronger causal flow from sensory inputs to motor outputs. They also show different arrangements of 'causal sources' and 'causal sinks': nodes that differentially affect, or are affected by, the remainder of the network. Finally, analysis of causal connectivity can predict the functional consequences of network lesions. These results suggest that causal connectivity analysis may have useful applications in the analysis of neural dynamics.     

矿井巷道无线传感器网络连通性研究

连通问题是构建无线传感器网络时需要解决的首要问题。以矿井巷道为背景,介绍了节点按矩形、等腰三角形和线形排列的三种无线传感器网络结构。运用几何分析的方法,研究了节点通信半径和感应半径比值为任意的情况下三种网络结构的连通性,得出了网络要达到2、3连通时节点通信半径和感应半径的代数关系。并从网络连通度、系统生命周期和网络效率三个角度对网络性能进行仿真。仿真实验表明,在相同部署区域,矩形网络在达到网络连通性要求的情况下,更能有效利用节点资源,延长网络生命周期。     

Asymptotically optimal trade-off between local and global connectivity in wireless networks

We analyze large, random network topologies that arise in ad hoc or sensor networks. A fundamental requirement of communication in these systems is reachability, that is, to have a connected network topology. It is known, however, that the price for full connectivity is very high, as it requires unbounded local complexity, i.e., it forces the nodes to have infinitely growing degrees to achieve asymptotic connectivity. This means a lack of scalability, which is known to hold for a quite general class of random network topology models. Therefore, an important step in analyzing the performance of such networks is to explore the trade-off between the fraction of nodes that still belong to a connected component vs. a bound imposed on local connectivity, i.e., on the node degrees. We investigate this issue in a model that is more general than previously investigated random wireless network topology models. In our general model we derive an asymptotically optimal trade-off between node degrees and the fraction of nodes that form a connected component.     

求解网络连通度问题的新算法

连通度是评价网络系统连通状况及抗毁性的重要指标,也是网络结构的重要特征。针对现有算法在求解网络连通度时需要将原有网络转化为容量网络或进行其他变换的不足,受交通网络瘫痪事例的启发,提出了一种求解网络连通度的新算法。该算法通过引入点影响度和网络影响度来刻画各顶点在网络中的重要程度,不仅能求解网络连通度,同时还可以确定网络的最小点割,算法步骤简单、易于实现。最后算法分析和仿真实验表明了新算法的有效性。     

Graph theoretic characterization and reliability of the generalized Boolean n-cube network

In this paper, a general class of Boolean n-cube structures is investigated. The interconnection is based on a mixed radix number system which results in a variety of generalized Boolean n-cube structures for a given number of processors , where x and y are positive integers. A number of interesting properties of the network are revealed. By a constructive method, the node connectivity of this network is found. Finally, we show that the graph is super-λ and is an optimal reliable structure for interconnection networks.     

无线传感器网络部分覆盖算法及连通性研究

研究了无线传感器网络在部分覆盖下的节点配置及网络连通性问题。首先,基于最优正六边形拓扑架构,给出了节点密集分布条件下的覆盖率与相邻工作节点间距的解析关系,并在已有的最优完全覆盖算法OGDC的基础上进行了扩展和改进,从而得到了一种新的网络节点配置算法EGDC（Extended OGDC Algorithm）。该算法可以有效地选择出合适的工作节点以达到任意给定覆盖率下的部分覆盖。此外,还给出了一种检验和评价网络连通性的方法,通过该方法可以对网络的连通性进行量化分析,并给出了一项评价网络连通性的指标。仿真表明,EGDC可以有效地实现任意期望覆盖率下的网络配置并保持网络的连通。     

Robustness of regular ring lattices based on natural connectivity

It has been recently proposed that natural connectivity can be used to efficiently characterise the robustness of complex networks. The natural connectivity quantifies the redundancy of alternative routes in the network by evaluating the weighted number of closed walks of all lengths and can be seen as an average eigenvalue obtained from the graph spectrum. In this article, we explore both analytically and numerically the natural connectivity of regular ring lattices and regular random graphs obtained through degree-preserving random rewirings from regular ring lattices. We reformulate the natural connectivity of regular ring lattices in terms of generalised Bessel functions and show that the natural connectivity of regular ring lattices is independent of network size and increases with K monotonically. We also show that random regular graphs have lower natural connectivity, and are thus less robust, than regular ring lattices.     

无线传感器网络连通性研究

为优化无线传感器网络的配置参数,减少网络拓扑结构变化次数,需对其组网算法和连通性问题进行研究。从概率论角度出发研究了网络参数之间的关系,在分析了节点连通度概率分布模型后,推导出了节点通信半径、节点个数、监测区域、连通度之间的关系,并在此基础上给出了一种连通性好且节能的无线传感器网络组网算法。通过仿真实验对算法进行验证,实验结果表明使用该方法组建的无线传感器网络连通性好,有很好的应用前景。     

Coverage and connectivity issues in wireless sensor networks: A survey

Sensing coverage and network connectivity are two of the most fundamental problems in wireless sensor networks. Finding an optimal node deployment strategy that would minimize cost, reduce computation and communication overhead, be resilient to node failures, and provide a high degree of coverage with network connectivity is extremely challenging. Coverage and connectivity together can be treated as a measure of quality of service in a sensor network; it tells us how well each point in the region is covered and how accurate is the information gathered by the nodes. Therefore, maximizing coverage as well as maintaining network connectivity using the resource constrained nodes is a non-trivial problem. In this survey article, we present and compare several state-of-the-art algorithms and techniques that aim to address this coverage–connectivity issue.