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

Research on Hexagonal Torus Based on Cayley Graph

六度网络是一类平面图网络结构,将平面以等边三角形的形式进行分割,包括六度网孔网络和六度环绕网络.六度网孔网络不是规则网络,其边缘节点与内部节点的度不相等.通过对六度网孔网络的边缘节点建立环绕边就形成了规则的六度环绕网络,每个节点的度为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.