=Paper=
{{Paper
|id=Vol-2864/paper43
|storemode=property
|title=Topology Properties of Hierarchical Honeycomb Meshes
|pdfUrl=https://ceur-ws.org/Vol-2864/paper43.pdf
|volume=Vol-2864
|authors=Burhan Selcuk,Ayse Nur Altintas Tankul,Ali Karci
|dblpUrl=https://dblp.org/rec/conf/cmis/SelcukTK21
}}
==Topology Properties of Hierarchical Honeycomb Meshes==
https://ceur-ws.org/Vol-2864/paper43.pdf
Topology Properties of Hierarchical Honeycomb Meshes
Burhan Selcuka, Ayse Nur Altintas Tankul,a and Ali Karcib
a
Karabuk University, Department of Computer Engineering, Karabuk, Turkey
b
Inonu University, Department of Computer Engineering, Karabuk, Turkey
Abstract
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.
Keywords 1
Hierarchical honeycomb meshes, Interconnection network, Hamilton graph, Gray code,
Network topology, Routing
1. Introduction
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
CMIS-2021: The Fourth International Workshop on Computer Modeling and Intelligent Systems, April 27, 2021, Zaporizhzhia, Ukraine
EMAIL: bselcuk@karabuk.edu.tr (B. Selcuk); aysenuraltintas@karabuk.edu.tr (A. N. Altintas Tankul); ali.karci@inonu.edu.tr (A. Karci)
ORCID: 0000-0002-5141-5148 (B. Selcuk); 0000-0002-4188-010X (A. N. Altintas Tankul); 0000-0002-8489-8617 (A. Karci)
© 2021 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
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.
a.
b.
c.
d.
Figure 1: Different type of Hierarchical Honeycomb Network structure a. Oftadef et al. [10],b. Ajdari
et al. [9], c. Fang et al. [8] and d. Xu et al. [11].
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.
2. Preliminaries
2.1. Honeycomb Meshes (HM)
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])
2.2. Hierarchical Honeycomb Meshes (HHM)
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. Hierarchical Extended Fibonacci Cubes (HEFC)
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).
Figure 6. Hierarchical Extended Fibonnaci Cubes (HEFC(n)) [26].
3. Construction of HHM
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
n 1
(a b ) definition, summation is a b (bitwise-XOR operation).
i 0
i i i i
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) ) (a 3k b 3k ) = 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
c1 c0 d1 d0
a5 a4 a3 a2 a1a0 and b5b4b3 b2b1b0 can be illustrated by c1c0 and d1d 0 , respectively. The edges
ci d i 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
(000 || E(0) 010 || E(0) 011 || E(0)
E(1) =
001 || E(0) 101 || E(0) 100 || E(0) E' )
000 || {(000,010), (010,011), (011,001), (001,101), (101,100), (100,000)}
010 || {(000,010), (010,011), (011,001), (001,101), (101,100), (100,000)}
011 || {(000,010), (010,011), (011,001), (001,101), (101,100), (100,000)}
001 || {(000,010), (010,011), (011,001), (001,101), (101,100), (100,000)}
101 || {(000,010), (010,011), (011,001), (001,101), (101,100), (100,000)}
100 || {(000,010), (010,011), (011,001), (001,101), (101,100), (100,000)} E'
(000000,000010), (000010,000011), (000011,000001), (000001,000101), (000101,000100),
(000100,000000), (010000,010010), (010010,010011), (010011,010001), (010001,010101),
(010101,010100), (010100,010000)(011000,011010), (011010,011011), (011011,011001),
(011001,011101), (011101,011100), (011100,011000), (001000,001010), (001010,001011),
(001011,001001), (001001,001101), (001101,001100), (001100,001000), (101000,101010),
(101010,101011), (101011,101001), (101001,101101), (101101,101100), (101100,101000)
(100000,100010), (100010,100011), (100011,100001), (100001,100101), (100101,100100),
(100100,100000) E'
where the first order external edges are E' = {(000000,010000), (010000,011000), (011000,
001000), (001000,101000), (101000,100000), (100000,000000)} .
Figure 7: Labeling of HHM(0) and HHM(1).
Figure 8: Labeling of HHM(2).
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).
4. Topology properties of HHM
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
Figure 9: Base step for the mathematical induction.
Figure 10: Hamiltonian property proof for HHM(k).
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.
5. Routing of HHM
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 fault-
tolerant 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
s k = s 2i , k = 1,2, …, i = 0,1,2, …
s1 = s 2 0 = 010101 000001 = 010100
s 2 = s1 23 = 010100 001000 = 011100
s 3 = s 2 2 4 = 011100 010000 = 001100
s 4 = s 3 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 = 010101 101010 = 111111
s k = s 2i , k = 1,2, …, i = 0,1,2, …
s1 = s 2 0 = 010101 000001 = 010100
s 2 = 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).
6. Conclusions
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.
7. References
[1] T. Thomadsen, Hierarchical Network Design, PHD tesis Informatics Math. Model. - Tech.
Univ. Denmark, pp. 1–34, 2014.
[2] A. Liu, J. Yuan, S. Wang, and J. Li, On g-good-neighbor conditional connectivity and
diagnosability of hierarchical star networks, Discret. Appl. Math., vol. 293, pp. 95–113, 2021.
[3] J. R. Kim, J. U. Lee, and J. B. Jo, Hierarchical spanning tree network design with Nash genetic
algorithm, Comput. Ind. Eng., vol. 56, no. 3, pp. 1040–1052, 2009.
[4] V. H. Rabarijaona, F. Kojima, and H. Harada, Hierarchical mesh tree protocol for efficient
multi-hop data collection, IEEE Wirel. Commun. Netw. Conf. WCNC, vol. 2, pp. 2008–2013,
2014.
[5] A. Dehghani and K. RahimiZadeh, Design and performance evaluation of Mesh-of-Tree-based
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-of-
plane 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.