边故障k元n立方体中经过匹配的指定二不交路覆盖

对边故障k元n立方体网络中经过匹配的指定二不交路覆盖的存在性问题进行了探讨。设Q_(n)^(k)是一个k元n立方体网络,其中n≥4、k≥4是偶数,M是Q_(n)^(k)的匹配,F是Q_(n)^(k)的故障边集。若(u,u′)和(v,v′)是Q_(n)^(k)中任意2条不相邻的边,满足{u,v}∩V(M)=Ф和(u′,v′)∈M,则当M+F≤2n-7时,在Q_(n)^(k)-F中存在2条顶点不相交的路Pu,u′和Pv,v′,经过匹配M且V(Pu,u′)∪V(Pv,v′)=V(Q_(n)^(k))。

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

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

故障k元n立方体网络中的多播容错路由算法

本文在k元n立方的m子立方体连通的k元n立方体网络中,讨论了多播容错路由算法,使得k元n立方体网络中多播路由不止适合结点故障、也适合链路故障,同时讨论了算法的时间复杂度。

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

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

k元n立方并行容错路由

本文讨论了k元n立方并行容错路由问题,给出了k元n立方并行容错路由并行条数的一个下界,也给出每条路径步长的一个下界,证明过程同时也可转化为求并行路径的算法。

k元n立方网络的k圈排除问题的递归算法

为了度量以k元n立方网络为底层网络拓扑的并行计算机系统的容错能力,通过构造k元n立方网络中使得所有的k元1立方子网都发生故障的最小节点集合的方法,提出求解其k元1立方子网排除点割集的一种递归算法;证明了要使k元n立方网络中所有k元1立方子网都发生故障至少需要破坏掉kn-1个节点。结果表明,在不超过kn-1-1个节点被破坏的情况下,以k元n立方网络为底层拓扑构建的并行计算机系统中依然存在无故障的k元1立方子网。

基于k元n立方体拓扑的无线传感器网络广播策略

研究了无线传感器网络的广播策略,提出一个冲突避免立方体广播算法CACB(Collision Avoidance Cube Broadcast)。CACB基于对k元n立方体结构的网络研究广播策略。CACB算法采用时钟准同步的方法,按照为序寻径的方式,确定每一个时间步应该如何去路由信息。实验使用OPNET软件进行仿真,仿真结果表明基于k元n立方体的无线传感器网络的广播算法CACB和传统的广播策略相比,能够减少最大端到端的时延,降低网络冲突,减少节点能量消耗,延长整个网络寿命,提高了网络的吞吐量。

K元N立方体网络均匀跨步通信模式的性能分析与优化

K元N立方体网络是高性能计算机常用的一种网络结构.均匀跨步通信是高性能计算最重要的通信模式之一.针对K元N立方体网络均匀跨步通信模式,推导出其性能下限的理论公式,采用自行开发的网络模拟器模拟了多种结构、多种跨步值和多种消息长度的传输性能.最后针对节点重映射和消息分割两种优化措施进行了模拟和分析.模拟结果显示,4元N立方体网络具有良好的All-to-all性能,接近All-to-all性能最好的K元N树网络.

边故障k元n立方体的超级哈密顿交织性

k元n立方体(记为Qkn)是优于超立方体的可进行高效信息传输的互连网络之一。Qkn是一个二部图当且仅当k为偶数。令G[V0,V1]是一个二部图,若(1)任意一对分别在不同部的顶点之间存在一条哈密顿路,且(2)对于任意一点v∈Vi,其中i∈{0,1},V1-i中任意一对顶点可以被G[V0,V1]-v中的一条哈密顿路相连,则图G[V0,V1]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的,所以研究网络的容错性就尤为重要。针对含有边故障的Qkn,其中k≥4是偶数且n≥2,证明了当其故障边数至多为2n-3时,该故障Qkn是超级哈密顿交织图,且故障边数目的上界2n-3是最优的。

在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。

k元n立方体的条件容错强Menger边连通性

研究了k元n立方体的强Menger边连通度,并证明了k元n立方体Q■(n≥2,k≥3)是3n-3条件容错强Menger边连通的.

有遗失边的k元n立方体在MM*模型下的局部诊断度

一个多重处理器系统的诊断度是一个非常重要的研究课题,它是度量多重处理器系统故障诊断的重要参数。作为重要的互连网络拓扑结构,k元n立方体具有许多良好的性质。在本文中,我们研究了k元n立方体Qnk(n≥3,k≥6)在MM*模型下的局部诊断度,证明了Qnk(n≥3,k≥6)即使存在2n-2条遗失边仍具有强局部诊断性,并且证明了2n-2是最优值。

扩展k元n立方体的1-好邻诊断度

现如今,一个多重处理器系统的诊断度是一个非常重要的研究课题,它是度量多重处理器系统故障诊断能力的重要参数。2012年,Peng等人提出了一个新的系统故障诊断方法,称为g好邻诊断度,它限制每个非故障顶点至少有g个非故障邻点。n维扩展k元n立方体是超立方体的一个重要变形。在本文中,我们证明了扩展k元n立方体在PMC模型下和MM*模型下的1-好邻诊断度是8n-9(n≥4,k≥4)。

含故障边的k元4立方体中的哈密尔顿性

对于大量的并行系统而言,k元n立方体网络Q^(k)_(n)是最流行的互连网络之一。对k元4立方体网络中的容错哈密尔顿性进行研究,证明了在Q^(k)_(4)中,k≥4是偶数,若|F|≤13,且δ(Q^(k)_(4)-F)≥3时,Q^(k)_(4)-F中仍有哈密尔顿圈,其中F是Q^(k)_(4)中的故障边集。

扭n立方体中的边不交Hamilton圈

网络图的Hamilton性是图论、计算机网络理论中的重要研究议题,超立方体及其变体由于其良好的网络参数、拓扑结构吸引了众多学者的关注和研究,并将之广泛地应用于许多实际领域中.结合Lee距离Gray码理论证明了扭n立方体中存在[n/2]个边不交Hamilton圈,并且给出这些边不交Hamilton圈的生成方法.