交叉立方体网络上的一种双向搜索路由算法  

Bidirectional seeking routing algorithm in crossing cube

作　　者：王敏[1] 高太平[1] 刘桂枝[1] 刘宏英[1] 

机构地区：[1]山西大学计算机与信息技术学院,太原030006

出　　处：《计算机工程与应用》2007年第35期123-125,共3页Computer Engineering and Applications

基　　金：国家自然科学基金( the National Natural Science Foundation of China under Grant No.10471081);山西省自然科学基金( the Natural Science Foundation of Shanxi Province of China under Grant No.2007011043)

摘　　要：交叉立方体是近年提出的一种互联网络。虽然直径大约是超立方体直径的一半,但由于节点连接方式比超立方体复杂,所以在交叉立方体中利用节点编码研究路由算法比在超立方体中复杂的多。针对交叉立方体互联网络节点编码的特点,在理论分析的基础上采用双向搜索的方法,给出了一个基于交叉立方体节点编码的多项式路由算法,证明了在交叉立方体上采用该算法求得的任意两节点间的路长不超过该交叉立方体的直径。Crossing cube which has been proposed recently is a kind of interconnection networks.Although its diameter is about half of hypercube＇s,researching routing algorithm by vertices＇ labels is much more complicated in crossing cube than that in hypercube since vertices of crossing cube link complicatedly.In this paper,considering labels＇ characteristics of vertices in crossing cubes,we give a polynomial routing algorithm of crossing cube adopting bidirectional seeking method by theoretic analysis,and prove that length of path obtained by this algorithm is not more than crossing cube＇s diameter.

关 键 词：交叉立方体 编码 双向搜索 路由算法 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]