计算机科学 ›› 2017, Vol. 44 ›› Issue (Z6): 252-257.doi: 10.11896/j.issn.1002-137X.2017.6A.058
林政宽,王铭成,郭莉莉,杜满意
LIN Cheng-kuan, WANG Ming-cheng, GUO Li-li and DU Man-yi
摘要： Mesh网络是较早研究的且现在仍然是最为重要的、最有吸引力的网络模型之一。因其结构、规则简单及良好的可扩展性,易于VLSI(超大规模集成电路)的实现,网格(Mesh)网络不仅成为了许多理论研究的基础模型,而且也是许多大型多处理器并行计算机系统所采用的拓扑结构。给出了两种故障情形下的最短路由算法:1)当Mesh的行数大于等于3且列数大于等于3、出现一个矩形故障区域时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度；2)当Mesh的行数≥3且列数≥3、某个结点及其k跳以内的邻居结点出现故障时,给出了任意两个无故障结点间的最短路由算法,并且计算出了路径长度。
| [1] HARARY F,HAYES J P,WU H J.A survey of the theory of hypercube graphs[J].Computers and Mathematics with Applications,1988,5(4):277-289. [2] 杨靖,徐迈,赵伟,等.传感器网络中一种能量高效的数据收集算法[J].系统工程与电子技术,2011,33(3):650-655. [3] 朱永利,于永华,李丽芬.数据收集传感器网络的多模层次网络构建[J].计算机工程,2011,37(2):111-113. [4] 潘文虎,张瑞华.WSN中基于移动sink的高效数据收集算法[J].计算机工程,2011,37(18):94-96. [5] WANG D.Embedding Hamiltonian cycles into folded hyper-cubes with faulty links[J].Journal of Parallel and Distributed Computing,2001,61(4):545-564. [6] EFE K.The crossed cube architecture for parallel computation[J].IEEE Transactions on Parallel and Distributed Systems,1992,3(5):513-524. [7] ABRAHAM S,PADMANABHAN K.The twisted cube topology for multiprocessors:A study in network asymmetry[J].Journal of Parallel and Distributed Computing,1991,13(1):104-110. [8] LOURI A,SUNG H.An optical multi-mesh hypercube:a scalable optical interconnection network for massively parallel computing[J].Journal of Lightwave Technology,1994,12(4):704-716. [9] LILLEVIK S L.The Touchstone 30 Gigaflop DELTA Prototype[C]∥Proceedings of the Sixth Distributed Memory Computing Conference.1991:671-677. [10] LENOSKI D,LAUDON J,GHARACHORLOO K,et al.The Stanford DASH Multiprocessor[J].IEEE Computer,1992,25(3):63-79. [11] AGARWAL A,BIANCHINI R,CHAIKEN D,et al.The MIT alewife machine:architecture and performance[J].International Symposium on Computer Architecture,1998,23(12):2-13. [12] Intel.A touchstone DELTA system description[R].Intel Advanced Information,Intel Corporation.Portland,Oregon,Technical Report,1991. [13] SEITZ C L,ATHAS W C.The architecture and programming of the Ametek series 2010 multicomputer[C]∥Conference on Hypercube Concurrent Computers & Applications:Architecture.ACM,1988:33-37. [14] 孙凝晖,徐志伟.曙光2000超级计算机系统软件的设计[J].计算机学报,2000,23(1):9-20. [15] YU Z G,WANG X Y,SHEN K L,et al.A general methodology to design deadlock-free routing algorithms for mesh networks[M]∥Algorithms and Architectures for Parallel Processing.Springer International Publishing,2015:478-491. [16] 胥大成,樊建席,张书奎.基于2D-Mesh的容错路由算法[J].计算机科学,2012,39(3):113-117. [17] 袁利永,朱艺华,邱树伟.无线传感mesh网络的分段地址分配策略及其路由[J].计算机科学,2016,43(6):116-121,155. [18] 王高才,陈建二,陈松乔,等.Mesh网络路由算法容错性的概率分析[J].计算机学报,2004,27(3):319-327. [19] 刘家俊,顾华玺,王长山.mesh优先级容错路由[J].计算机工程与应用,2009,5(4):105-107. [20] 王高才,王国军,陈建二,等.Mesh 网络容错单播路由算法[J].中南工业大学学报,2003,34(6):657-660. |
| No related articles found! |
|
||
首页