h维墙式环托  

The h-Dimensional Wall Torus

作　　者：陈协彬[1] 

机构地区：[1]漳州师范学院数学系,漳州363000

出　　处：《计算机学报》2003年第1期77-83,共7页Chinese Journal of Computers

基　　金：福建省自然科学基金 (F0 0 0 18)

摘　　要：定义了h维墙式环托hDWT :给定偶数ni 4 ,i=1,2 ,… ,h .h维墙式环托hDWT(n1,n2 ,… ,nh)是一个(h +1) 正则的二部图 ,可由h维普通环托hDOT(n1,n2 ,… ,nh)删除每个节点的h - 1条连边而得到 .它是节点对称的且有最优容错度h +1.若n1=maxi ni,则其直径与hDOT的直径相同 .hDOT可嵌入到hDWT中 ,其伸张度为 3,拥塞度为min{h ,4 } .因而hDOT上现有的算法都能移植到hDWT上 ,且有常数的减速比 ;提出一种简单的自主路由算法 ,该算法实现了hDWT上的任意两个节点间的最短路径 .通过把删除的度重新添加到每个节点上 ,得到增强型hDWT ,它比hDOT有小得多的直径 ,且包含一些有用的互联拓扑结构 .h维墙式网孔hDWM可由hDWT删除所有的回卷边而得到 ,它的许多性质与hDWT的性质相类似 .The h dimensional wall torus is defined. Given even numbers n i 4,i=1,2,..., h . The h dimensional wall torus hDWT(n 1 ,n 2 ,...,n h ) is an ( h+1) regular bipartite graph obtained from the h dimensional ordinary torus hDOT(n 1 ,n 2 ,...,n h ) by deleting h-1 links from each node. It is of node symmetry and has fault tolerance h+1 . If n 1 = max in i , then its diameter is the same as hDOT. hDOT can be embedded in hDWT with dilation 3 and congestion min{ h ,4}. As a result, all existed algorithms on hDOT can be ported to hDWT with constant slow down. A simple self routing algorithm is proposed, which provides the shortest path between any two nodes on hDWT . By adding some deleted degrees back to each node, the enhanced hDWT has a much better diameter than hDOT , and contains usual interconnection topologies. The h dimensional wall mesh hDWM can be obtained from hDWT by deleting the wrap around links, its many properties are similar to that of hDWT .

关 键 词：互联网络 h维墙式环托 容错度 自主路由算法 

分 类 号：TP393.4[自动化与计算机技术—计算机应用技术]