基于Cayley图的六度环绕网络研究  

Research on Hexagonal Torus Based on Cayley Graph

作　　者：张震[1] 肖文俊[2] 黄书强[3] 邓玉辉[1] 

机构地区：[1]暨南大学计算机科学系,广州510632 [2]华南理工大学软件学院,广州510641 [3]暨南大学网络与教育技术中心,广州510632

出　　处：《计算机学报》2014年第2期384-393,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(60973150;61272073;61373125);广东省自然科学基金重点项目(S2013020012865);广东省科技计划项目(2012B010100027;2012B091100161);广州市科技计划项目(2013Y4300017);广东省教育厅科技创新项目(2012KJCX0013;2013KJCX0018)资助~~

摘　　要：六度网络是一类平面图网络结构,将平面以等边三角形的形式进行分割,包括六度网孔网络和六度环绕网络.六度网孔网络不是规则网络,其边缘节点与内部节点的度不相等.通过对六度网孔网络的边缘节点建立环绕边就形成了规则的六度环绕网络,每个节点的度为6.但是由于环绕边的存在,使得六度环绕网络的通信算法实现复杂,网络直径也非常难于计算.六度环绕网络被证实是一种Cayley图模型,具有良好的对称性.但是基于Cayley图的六度环绕网络的最优路由算法、广播算法还没有得到,该网络模型的具体直径值也是未解问题.针对基于Cayley图的六度环绕网络模型,文中给出了一种简单的最优路由算法和一种基于陪集图理论的广播算法,并给出该网络模型的网络直径确切值.Hexagonal network belongs to the family of planar graphs including hexagonal mesh and torus. It uses equilateral triangle plane tessellation. Hexagonal mesh is not regular since the degrees of the nodes on the periphery are not equal to the degrees of the interior nodes. Hexagonal torus is a family of 6-regular graphs which can be used in multiprocessor interconnection network, where nodes on the periphery of a hexagonal mesh are wrapped around to achieve regularity and homogeneity. The communication algorithms of hexagonal torus are complicated, and its diameter is difficult to accurate. Hexagonal tori are considered a type of Cayley graphs. For the hexagonal torus based on Cayley graph, the optimal routing algorithm and broadcasting algorithm remain to be established, and the exact diameter is still an open problem. This paper develops an optimal routing and coset graph based broadcasting algorithm for hexagonal torus with the aid of its Cayley-formulations, and then gives the exact diameter of this network.

关 键 词：六度环绕网络 CAYLEY图 最优路由算法 广播算法 直径中图法 

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