基于圈积的新型Cayley图互联网络模型

doi:10.3969/j.issn.1000-565X.2011.02.026

华南理工大学学报（自然科学版） ›› 2011, Vol. 39 ›› Issue (2): 153-158.doi: 10.3969/j.issn.1000-565X.2011.02.026

• 计算机科学与技术 • 上一篇

基于圈积的新型Cayley图互联网络模型

张震¹肖文俊¹王晓明²

1．华南理工大学计算机科学与工程学院，广东广州 510006；2．暨南大学计算机科学系，广东广州 510632

收稿日期:2010-02-09 修回日期:2010-10-10 出版日期:2011-02-25 发布日期:2011-01-02
通信作者: 张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究 E-mail:zhang2003174@yahoo.com.cn
作者简介:张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究
基金资助:
国家自然科学基金资助项目(60773083)；广东省科技厅基金资助项目(8151063201000022)；暨南大学中央高校基本科研业务费专项资金资助项目(1 1610307)

A New Type of Cayley Graph Model for Interconnection Networks Based on Wreath Product

Zhang Zhen¹ Xiao Wen-jun¹ Wang Xiao-ming²

1. The south China university of technology, computer science and engineering college, guangdong guangzhou 510006; 2. Jinan university computer science, guangdong guangzhou 510632

Received:2010-02-09 Revised:2010-10-10 Online:2011-02-25 Published:2011-01-02
Contact: 张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究 E-mail:zhang2003174@yahoo.com.cn
About author:张震(1975-)，男，在职博士生，暨南大学讲师，主要从事互联网络、并行分布式处理系统研究
Supported by:
国家自然科学基金资助项目(60773083)；广东省科技厅基金资助项目(8151063201000022)；暨南大学中央高校基本科研业务费专项资金资助项目(1 1610307)

摘要/Abstract

摘要： 为了构建适合大规模网络结构的模型,文中提出了一种新型Cayley图互联网络模型WG2nm,当n≥3时,其节点度为m＋3,当n=2时,其节点度为m＋2.文中还给出了该网络模型的路由算法,得到了其直径上界为﹂5n/2」,并对该网络模型的嵌入性进行了分析.将WG2nm与其它网络模型进行分析比较,发现WG2nm模型能够以更小的代价构造大规模网络结构.

关键词: 互联网络, Cayley图, 路由算法, 网络直径, 嵌入性

Abstract:

Proposed in this paper is a new type of Cayley graph model for building large-scale interconnection networks,namely WG2mn,whose node degree is m＋3 when n≥3 and is m＋2 when n=2.A routing algorithm for the proposed model is also presented,and the upper bound of the algorithm diameter is deduced as 5n/2」.Moreover,the embedding properties of the model are analyzed.It is found that WG2mn is superior to other network models because it helps to construct large-scale interconnection networks with lower cost.

Key words: interconnection networks, Cayley graph, routing algorithm, network diameter, embeddability

张震肖文俊王晓明. 基于圈积的新型Cayley图互联网络模型[J]. 华南理工大学学报（自然科学版）, 2011, 39(2): 153-158.

Zhang Zhen Xiao Wen-jun Wang Xiao-ming. A New Type of Cayley Graph Model for Interconnection Networks Based on Wreath Product[J]. Journal of South China University of Technology (Natural Science Edition), 2011, 39(2): 153-158.

[1]	李梅生肖文俊赖正文张占英韩冬. 一种具有小世界性常数度的数据中心网[J]. 华南理工大学学报（自然科学版）, 2017, 45(7): 63-68.
[2]	康文雄许耀钊. 节点约束型最短路径的分层Dijkstra 算法[J]. 华南理工大学学报（自然科学版）, 2017, 45(1): 66-73.
[3]	徐方张沪寅徐宁汪志勇. 基于上下文认知的高能效路由算法[J]. 华南理工大学学报（自然科学版）, 2015, 43(5): 139-144.
[4]	侯剑儒陈晓敏. 改进的 SpaceWire 路由算法[J]. 华南理工大学学报（自然科学版）, 2013, 41(9): 95-99,106.
[5]	李岚肖文俊. 基于Cayley 图的跨层定向扩散路由算法[J]. 华南理工大学学报(自然科学版), 2012, 40(6): 118-125.
[6]	李岚肖文俊魏文红. 基于Borel亚循环拓扑的无线传感器网络路由算法[J]. 华南理工大学学报(自然科学版), 2012, 40(4): 30-36.
[7]	张文柱赵贝. 基于梯度和模糊神经网络的容迟网络路由算法[J]. 华南理工大学学报(自然科学版), 2012, 40(3): 57-63.
[8]	陈凤超李融林. 基于路由代价的无线传感器网络蚁群路由算法[J]. 华南理工大学学报（自然科学版）, 2011, 39(5): 36-43.
[9]	魏文红, 肖文俊. 一种具有小世界特征的结构化P2P覆盖网络[J]. 华南理工大学学报（自然科学版）, 2009, 37(10): 66-72.
[10]	李领治郑洪源吴庆丰丁秋林. 基于扩张方法的选播路由算法[J]. 华南理工大学学报（自然科学版）, 2006, 34(6): 79-83.

基于圈积的新型Cayley图互联网络模型

A New Type of Cayley Graph Model for Interconnection Networks Based on Wreath Product

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价