交换超立方网中的最短路径路由算法  

Shortest Path Routing Algorithm in Exchanged Hypercube Network

作　　者：梁家荣[1] 曹入辉[1] 郭晨[2] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004 [2]井冈山大学信息科学与传媒学院,江西吉安343009

出　　处：《计算机工程》2012年第20期64-67,71,共5页Computer Engineering

基　　金：国家自然科学基金资助项目(61064002);教育部新世纪优秀人才支持计划基金资助项目(NCET-06-0756)

摘　　要：针对交换超立方网络的最短路由问题,提出一个交换超立方网中的最短路径路由算法。利用图论的方法,通过引进子网的概念,研究交换超立方网的拓扑性质,给出节点各边可进行最短路径路由的充要条件,得到其时间复杂度为2O((s t))。理论分析和仿真结果表明,该算法可输出交换超立方网中任意两节点间的一条最短路径。Based on the problem of the shortest path between two nodes in the exchanged hypercube network,the method of the graph theory is employed to study the topological property of the exchanged hypercube network by introducing the concept of similare subnet,the sufficient and necessary conditions which guarantee some link of one node to become a candidate link of the shortest path,are presented.At the same time,a shortest path routing algorithm with time complexity on the exchanged hypercube network is obtained,the theoretical analysis and the simulation result show that above algorithm can output the shortest path between any two nodes in the exchanged hypercube network.

关 键 词：交换超立方网 相似子网 最短路径 路由算法 同构 映射 

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