Honeycomb meshes can be seen widely in nature and are using in many different areas because of its properties. Using honeycomb meshes for constructing hierarchical structures has some advantages. In this study, hierarchical honeycomb meshes (HHM) are investigated. The construction of HHM is introduced with an example, topological properties of HHM explained in detail, a labeling algorithm in the process of the construction phase and also routing algorithms are given. This study shows a HHM(n) has a fractal structure and its graph is a Hamiltonian graph.
A network is formed with nodes and links that connect them. A hierarchical network is a type of network consists clusters that are disjoint group of nodes. Every cluster has one or more hub that is connected to other hubs by backbone links and similarly inside of these clusters nodes are also connected by cluster links. Different type of topologies can be used for cluster and backbone structure for hierarchical networks such as cluster networks are sparse like a star or a tree while backbone networks are denser like mesh, ring or fully interconnected [1].
Lia et al. worked on diagnosability and connectivity of hierarchical star network for forbidden faulty sets [2]. Kwak et al. studied on torus ring on multiprocessor systems and increased performance of an interconnecting network by altering a hierarchical ring. Hierarchical spanning tree is used for network designing by Kim et al. with Nash genetic algorithm and this work is more about designing backbone topology structure to increase overall routing performance [3]. Hierarchical mesh tree is used as a protocol for multi hop data collection efficiently by Rabarijaona et al. and had great results at MAC layer vin efficient routing for gathering multi-hop data in intelligent transportation system networks, wireless sensor networks, ad-hoc networks, etc. [4].On the other hand, Dehghani and RahimiZadeh used mesh tree for designing hierarchical wireless network on chip for multicore systems and evaluated its performance that has a competitive potential [5]. Hierarchical cubic network is also used for designing network. Zhao et. al used hierarchical cubic network for an interconnection network design [6] while Yun and Park shows hierarchical hypercube network is more suitable for building massively parallel computers as an interconnection network than hierarchical cubic network [7]. Honeycomb structure is also used for hierarchical network studies [8][9][10][11].
Honeycomb structure is a nature inspired pattern that can be found in biological systems and organic materials. It plays an important role in the functionality and survival of the thing it contains. In engineering, it is also important for designing materials because of its structural properties such as rigid, strong, lightweight structure for materials and also topological properties for network and connections. Engelmayr et al. used honeycomb for tissue engineering for cardiac anisotropy an get better results than previous studies [12]. It is also used in chemical engineering [13], satellite component research [14], computer graphics [15], station positioning for cellular phones [16], multiprocessor interconnection networks design [17][18] and in many different engineering area. Honeycomb mesh properties are also studied such as Hamilton properties [19], fractal properties [20][21], honeycomb networks in higher dimension [22][23], topological properties and communication algorithm of honeycomb networks [24].
In hierarchical honeycomb network (HHN) studies each of them have different way to form a hierarchical honeycomb network. Oftadef et al. construct a HHN by changing all tree edge vertex of a main honeycomb network cell with a smaller one and repeating the procedure [10]. Ajdari et al. also replace every three edge vertex of a base hexagonal network with a smaller hexagon but the construction of hierarchical network results differently [9] can be seen in Figure 1. Fang et al. uses different strategy 5. In the study of Xu et al., a self-similar hierarchical honeycomb structure is created by iteratively inserting sub-hexagons at the corners of the base hexagon and with an internal rib, the vertex of two adjacent sub-hexagons are connecting [11]. The 1st and 2nd order hierarchical structures are created by repeating this process. c.
In this study, a hierarchical honeycomb mesh (HHM) structure is presented. At first, the definition of honeycomb mesh (HM) is given, HHM is introduced and then hierarchical extended Fibonacci cubes are. The construction and topology properties of HHM are explained in detail. And lastly, routing algorithm on HHM is specified.
The honeycomb mesh can be explained as follow (see [24]):
Definition 1. Assume that the center of the honeycomb mesh is the origin of the z, y, and z axes and these axes are parallel to three direction of the edge of the mesh. There are two group of edges, and each node is in one of the groups that is black or white and can be called as black node or white node. If the edge is black than there can be three vectors to white nodes and x + = (1,0,0), y+ = (0,1,0) or z+ = (0,0,1) are the coordinates, while if the edge is white the vector to the black ones have coordinates as x- = (-1,0,0), y- = (0,-1,0) or z- = (0,0,-1) .
a b Figure 2: a. On Coordinates axis of honeycomb mesh, b. Brick drawing of HM(3).
It is known that nodes of Honeycomb mesh of dimension t can be coded by integer triples (u, v, w) such that - t +1 u, v, w t and 1 u + v + w 2 . Two nodes (u, v, w) and (u, v, w) are connected by an edge if and only if | u - u | + | v - v | + | w - w |= 1 (Lemma 1 in [24]). In Figure 3, the honeycomb meshes has labelled via this definition.
Figure 3: Three order of Honeycomb Meshes: a. HM(1), b. HM(2), and c. HM(3). (see [25])
Honeycomb Networks can be used for hierarchical fractal structure. In this section, we consider two variants of Hierarchical Honeycomb Meshes called HHM. HHM is suitable for creating this structure.
Figure 4: Hierarchical Honeycomb Meshes; zero order, 1st order, 2nd order. 2.3.
Definition 2. (Extended Fibonacci Cubes [26]) Assume EFC(n) = (V(n), E(n)), EFC(n -1) = (V(n -1), E(n -1)), and EFC(n - r) = (V(n - r), E(n - r)), r < n . Then, V(n) = {0 || V(n -1) 10 || V(n - 2)} . In EFC(n) , two different nodes can be connected to each other with an edge E(n) only if the label of those two nodes are similar except for one bit. As a starting point of recursion, V(3) = {0,1} and V(4) = {00,10,11,01}.
Definition 3. (Hierarchical Extended Fibonacci Cubes) The resulting interconnection network was given the name Hierarchical Fibonacci Cube (HFC(n)). The edges inside of a cluster named horizontal edges and the edges connect two different cluster named diagonal edges. Figure 5 depicts some HFC(n)s, with dashed lines reflecting diagonal connections. In terms of edges and nodes, an interconnection network can be described hierarchically if that is between hypercube and EFCk(n). Figure 5: a. HFC(3), b. HFC(4) and c. HFC(5) [26].
An EFC(n) is cluster that we select and let say | V(n) |= m , in any cluster any node can be represented with (i,j) that i is the cluster‘s node address and the node address inside of the cluster is j and the node (i,j) in the ith cluster can be connected directly to the node (j,i) in the jth cluster in that way m cluster can be connected. Every cluster in EFC(n) is addressed with using node addressing. In EFC(n) every edge is named horizontal edge and between clusters every edge is named diagonal edge. The interconnection network that is constructed with using m2 nodes is called Hierarchical Extended Fibonnaci Cube (HEFC(n)). Figure 6 shows some of the HEFC(n).
HHM(n) = (V(n), E(n)) can be constructed hierarchical using six HHM(n‐1) graphs n=1,2,3,…. The symbol "∥" is used for the concatenation of two strings in this paper. In the Hamming distance n1 (ai bi ) definition, summation is ai bi (bitwise-XOR operation). i0
Definition 4 (HHM(n)). Hierarchical Honeycomb Meshes have the following description. Then, for n > 0, HHM(n) = (V(n), E(n)) can be designed in the following way for n>0
HHM(n) = HHM(n -1) || HHM(0) where V(n) = V(n -1) || V(0) , V(0) = {000,010,011,001,101,100} and
(000 || E(n -1) 010 || E(n -1) 011|| E(n -1) E(n) =
001 || E(n -1) 101|| E(n -1) 100 || E(n -1) E' ) where E' = {(ei , e j ) | ei = abc and e j = dfg and (abc) (dfg) = 1 , the labels of ei and ej are same except abc of ei and dfg of ej} where m=0,3,6,…. Assume that v1 and v2 are two nodes whose labels are a(3k+2)a(3k+1)a3k…a1a0 and b(3k+2)b(3k+1)b3k…b1b0, respectively. By using one of the following conditions, we can get the ith order external edges:
(a(3k+2) b(3k+2) ) (a(3k+1) b(3k+1) ) (a3k b3k ) = 1,1 i k .
Example 1. HHM(1) can be constructed with integration of six HHM(0) graphs. There will be 36 nodes by concatenating 000,010,011,001,101,100 partial binary labels to all labels of nodes of HHM(0) where V(0) = {000,010,011,001,101,100}. Then there will be 6 edges. The labels c1c0 d1d0 a5a4a3 a2a1a0 and b5b4b3b2b1b0 can be illustrated by c1c0 and d1d0 , respectively. The edges ci di 1 for 1 i k are added to E(1). Figure 4 shows an example of HHM(1).
We get labelling of nodes and edges of HHM(1) as the follow: V(1) = V(0) || V(0) = {000,010,011,001,101,100}||{000,010,011,001,101,100} = 000 ||{000,010,011,001,101,100} 010 ||{000,010,011,001,101,100} 011|| {000,010,011,001,101,100} 001|| {000,010,011,001,101,100} 101||{000,010,011,001,101,100}100 || {000,010,011,001,101,100}, and
Algorithm 1. The recurrence relation of the following labelling algorithm on HHM(n) can be written as T(n)=T(n-1)+θ(1). Solving this recurrence relation, obtained running time of is T(n)=θ(n).
The Hamilton graph is the graph that contains Hamilton cycle which has a path visits each vertex only once and returned to the starting point. In this section of the study, The Hamiltonian properties of HHM(n) is analyzed.
Theorem 1. HHM(n) graphs are one type of a Hamiltonian graphs.
Proof. By using mathematical induction, the proof for this theorem can be done.
Base Step: k = 0, k = 1 or k = 2
Hypothesis Step: We are assuming that HHM(k-1) is a Hamiltonian graph.
Final Step: In Figure 10, HHM(k) is being a Hamiltonian graph can be seen. The HHM(k) includes six HHM(k-1) and there is a Hamiltonian path in each of these HHM(k-1) in Figure 10. HHM(k) that includes six Hamiltonian HHM(k-1) graphs and in HHM(k) there is Hamiltonian path showed in Figure 10.
Theorem 2. (i) Number of nodes in HHM(n) is 6n.
(ii) The recurrence relation E(n) = 6E(n -1) + 6 to calculate number of edges of HHM(n) with E(0)=0 initial value.
Proof. It can be easily proved that the theorem using mathematical induction. (see [27]) Corollary 1. Using gray code in the labeling of HHM(n) requires us to use excess bits, although it makes it easier to label. We need to use 3-bit Gray code for 6 nodes when n=1, 6-bit Gray code for 36 nodes when n=2, 9-bit Gray code for 216 nodes when n=3. Normally, it is enough to use 8 bits for labeling 216 nodes.
There are several routing techniques in honeycomb structure. Rais et al. assume each cell is a nod in the network and developed its routing strategy accordingly [28]. Zhang et al. gives 3 different algorithms on honeycomb mesh routing, a unicast routing algorithm XYZ-Route nodes in the network send messages to neighbor of its neighbor on anticlockwise direction with shortest path, a faulttolerant routing algorithm HFT-Rout provides communication between nodes including the fact that there are convex faults, and a multicast algorithm, named HMTREE-Route is used for routing a message in the presence of more than one destination along the same path as possible, also several copies can be distributed to different paths at the tree's crossroads during the routing process [29]. Also in the study of Stojmenovic XYZ-Route algorithm used [24].
In this section, the routing algorithms in HHM(n) will be investigated using the routing algorithms of hypercube [7]. Firstly, two examples are given. It is seen that a path cannot always be found as in hypercube in example 3.
Example 2. Let source node s = 010101 and destination node d = 101100 .
r = s d = 010101?101100 = 111001 sk = s 2i , k = 1,2,…, i = 0,1,2,… s1 = s 20 = 010101 000001 = 010100 s2 = s1 23 = 010100 001000 = 011100 s3 = s2 24 = 011100 010000 = 001100 s4 = s3 25 = 001100 100000 = 101100 = d The route is s1 s2 s3 s4 .
Example 3. Let source node s = 010101 and destination node d = 101010 .
r = s d = 010101101010 = 111111 sk = s 2i , k = 1,2,…, i = 0,1,2,… s1 = s 20 = 010101 000001 = 010100 s2 = s1 21 = 010100 000010 = 010110 (this node is not defined)
Algorithm 2. The following algorithm is calculated unicast routing in HHM(n) as example 2 and 3. The running time of the Algorithm2 is obtained as T(n)=θ(3n).
In this paper, we firstly define HHM(n) and investigate topology properties of HHM(n). The results obtained are given below: 1. HHM(n) has a fractal structure, that is self-repeating shapes that grow or shrink forever, forming the body in a similar object, 2. HHM(n) graph is a Hamiltonian graph, starting at any node of a graph, it crosses all nodes only once and can come to the starting node, 3. HHM(n) is scalable, 4. Number of nodes of HHM(n) is 6n, 5. The recurrence relation E(n) = 6E(n -1) + 6 to calculate number of edges of HHM(n) with E(0) = 0 initial value, 6. Deadlocks occur when the unicast routing algorithm on the HHM is similar to the unicast routing algorithm on the hypercubes. In future studies, this problem will be tried to be eliminated, 7. HHM is basically defined in a similar structure to HEFN. Both are built over the hypercube. Also, HHM and HEFN are isomorphic graphs because they have same adjacency spectrum. These similarities can be shown in detail in future studies.
hierarchical wireless network-on-chip for multicore systems, J. Parallel Distrib. Comput., vol. 123, no. July, pp. 100–117, 2019. [6] S. L. Zhao, R. X. Hao, and J. Wu, The generalized 4-connectivity of hierarchical cubic networks, Discret. Appl. Math., vol. 289, pp. 194–206, 2021. [7] S. K. Yun and K. H. Park, Hierarchical Hypercube Networks (HHN) for massively parallel computers, J. Parallel Distrib. Comput., vol. 37, no. 2, pp. 194–199, 1996. [8] J. Fang, G. Sun, N. Qiu, T. Pang, S. Li, and Q. Li, On hierarchical honeycombs under out-ofplane crushing, Int. J. Solids Struct., vol. 135, no. March, pp. 1–13, 2018. [9] A. Ajdari, B. H. Jahromi, J. Papadopoulos, H. Nayeb-Hashemi, and A. Vaziri, Hierarchical honeycombs with tailorable properties, Int. J. Solids Struct., vol. 49, no. 11–12, pp. 1413– 1419, 2012. [10] R. Oftadeh, B. Haghpanah, D. Vella, A. Boudaoud, and A. Vaziri, Optimal Fractal-Like
Hierarchical Honeycombs, Phys. Rev. Lett., vol. 104301, no. September, pp. 1–5, 2014. [11] X. Xu, Y. Zhang, J. Wang, F. Jiang, and C. H. Wang, Crashworthiness design of novel hierarchical hexagonal columns, Compos. Struct., vol. 194, no. March, pp. 36–48, 2018. [12] E. George C, M. Cheng, C. J. Bettinger, J. T. Borenstein, R. Langer, and L. E. Freed, Accordion-like Honeycombs for Tissue Engineering of Cardiac Anisotropy, Nat. Mater., vol. 7, no. May 2014, 2008. [13] B. Rajan, A. William, C. Grigorious, and S. Stephen, On Certain Topological Indices of
Silicate , Honeycomb and Hexagonal Networks, vol. 3, no. 5, pp. 530–535, 2012. [14] A. Boudjemai, R. Amri, A. Mankour, H. Salem, M. H. Bouanane, and D. Boutchicha, Modal Analysis and Testing of Hexagonal Honeycomb Plates Used for Satellite Structural Design, Mater. Des., vol. 35, pp. 266–275, 2012. [15] L. N. Lester and J. Sandor, Computer Graphics on a Hexagonal Grid, Comput. Graph., vol. 8, no. 4, 1985. [16] F. G. Nocetti, I. Stojmenovic, and J. Zhang, Addressing and Routing in Hexagonal Networks with Applications for Tracking Mobile Users and Connection Rerouting in Cellular Networks, IEEE Trans. PARALLEL Distrib. Syst., vol. 13, no. 9, pp. 963–971, 2002. [17] J. Carle, J. F. Myoupo, and D. Seme, All-to-all Broadcasting Algorithms on Honeycomb
Networks and Applications, Parallel Process. Lett., vol. 9, no. 4, pp. 539–550, 1999. [18] P. Manuel, B. Rajan, I. Rajasingh, and C. M. M, On minimum metric dimension of honeycomb networks, vol. 6, pp. 20–27, 2008. [19] A. N. Altintaş Tankül and B. Selçuk, On Hamiltonian Properties of Honeycomb Meshes,
Anatol. Sci., vol. 44, no. 1, pp. 184–190, 2019. [20] B. Selçuk and A. N. Altıntaş Tankül, Perfect Matching of Fractal Honeycomb Meshes, pp. 38– 46, 2019. [21] T. Zhang and K. Ding, A new Proof of Honeycomb Conjecture by Fractal Geometry Methods,
Front. Mech. Eng. China, no. April, 2013. [22] C. Science, Higher dimensional honeycomb networks, vol. 2, no. 4, pp. 391–420, 2001. [23] J. Carle, J. F. Myoupo, and I. Stojmenovic, Higher Dimensional Honeycomb Networks, J.
Interconnect. Networks, vol. 2, no. 4, pp. 391–420, 2001. [24] I. Stojmenovic, Honeycomb Networks : Topological Properties and Communication
Algorithms, vol. 8, no. 10, pp. 1036–1042, 1997. [25] D. Xu, J. Fan, X. Jia, S. Zhang, and X. Wang, Hamiltonian properties of honeycomb meshes,
Inf. Sci. (Ny)., vol. 240, pp. 184–190, 2013. [26] A. Karci, New Interconnection Networks: Fibonacci Cube and Extended Fibonacci Cubes
Based Hierarchic Networks, pp. 869–874, 2001. [27] A. Karci and B. Selçuk, A new hypercube variant : Fractal Cubic Network Graph Engineering Science and Technology , an International Journal A new hypercube variant : Fractal Cubic Network Graph, Eng. Sci. Technol. an Int. J., no. February 2015, 2014. [28] A. Rais, K. Bouragba, and M. Ouzzif, Routing and clustering of sensor nodes in the honeycomb architecture, J. Comput. Networks Commun., vol. 2019, 2019. [29] W. Zhang, X. Yang, Y. Liang, and Z. Huang, Routing algorithms in honeycomb meshes, Int. J.
Parallel, Emergent Distrib. Syst., vol. 24, no. 5, pp. 367–382, 2009.