Computer Science ›› 2017, Vol. 44 ›› Issue (Z6): 252-257.doi: 10.11896/j.issn.1002-137X.2017.6A.058

Previous Articles     Next Articles

Shortest Routing Algorithm Based on Target Node in Mesh Network with Faulty Area

LIN Cheng-kuan, WANG Ming-cheng, GUO Li-li and DU Man-yi   

  • Online:2017-12-01 Published:2018-12-01

Abstract: Mesh network is studied early and it is still one of the most important and attractive network models at pre-sent.Because of its simple,regular and scalable structure,and it is useful for the implementation of VLSI (Very Large Scale Integrated Circuit),Mesh network has not only become the basic model of many theoretical studies,but also the topology structure of many large multiprocessor and parallel computer systems.A mesh with m rows and n columns is denoted by Mm,n.In this paper,we gave the shortest routing algorithm under two different kinds of faulty area.1)We gave a routing algorithm to find the shortest path between any two fault-free nodes in Mm,n with m≥3 and n≥3,and calculated the length of the path obtained by the algorithm when there is a rectangular faulty region.2)We gave a routing algorithm to find the shortest path between any two fault-free nodes in Mm,n with m≥3 and n≥3,and calculated the length of the path given by the algorithm when there exists such a situation that a node and its k-hop neighbours are faulty.

Key words: Shortest routing algorithm,Fault-tolerant routing algorithm,Mesh network

[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!
Full text



No Suggested Reading articles found!