Edge Metric Dimension of Honeycomb and Hexagonal Networks for IoT

Sohail Abbas，Zahid Raza，Nida Siddiqui，F(xiàn)aheem Khan and Taegkeun Whangbo，＊

1Department of Computer Science，College of Computing and Informatics，University of Sharjah，Sharjah，27272，UAE

2Department of Mathematics，College of Sciences，University of Sharjah，Sharjah，27272，UAE

3Artificial Intelligence Lab，Department of Computer Engineering，Gachon University，Seongnam，13557，Korea

Abstract: Wireless Sensor Network (WSN) is considered to be one of the fundamental technologies employed in the Internet of things (IoT); hence，enabling diverse applications for carrying out real-time observations.Robot navigation in such networks was the main motivation for the introduction of the concept of landmarks.A robot can identify its own location by sending signals to obtain the distances between itself and the landmarks.Considering networks to be a type of graph，this concept was redefined as metric dimension of a graph which is the minimum number of nodes needed to identify all the nodes of the graph.This idea was extended to the concept of edge metric dimension of a graph G，which is the minimum number of nodes needed in a graph to uniquely identify each edge of the network.Regular plane networks can be easily constructed by repeating regular polygons.This design is of extreme importance as it yields high overall performance;hence，it can be used in various networking and IoT domains.The honeycomb and the hexagonal networks are two such popular mesh-derived parallel networks.In this paper，it is proved that the minimum landmarks required for the honeycomb network HC(n)，and the hexagonal network HX(n)are 3 and 6 respectively.The bounds for the landmarks required for the hex-derived network HDN1(n) are also proposed.

Keywords: Edge metric dimension;internet of things;wireless sensor network;honeycomb network;hexagonal network;hex-derived networks

1 Introduction

Honeycomb and Hexagonal networks[1]have been widely studied in various research domains，such as wireless sensor networks，wireless networks[2–6]and cellular networks，in order to study and analyze various issues like routing， [7–9] location management and target tracking [10–12]， energy conservation [13–15]， and interference estimation [16].These networks and application domains are applicable to the IoT as well[17–24].The concept of metric basis and metric dimension for the purpose of robot navigation within a graph-structured framework was initially studied in [25].Recently，the concept of robots and drones have also been proposed in such network structures for various application reasons [26].For example， drones/robots might be used in wireless sensor networks to gather samples for maintenance inspection or regular data collection acting as a mobile sink.Similarly，they can also be used to recharge the batteries of dying sensors on-the-fly.

Suppose an IoT scenario where a robot/drone is dropped somewhere unknown in a network and can move from node to node.Some vertices in the graph behave as landmarks， and the robot can measure its distance in the graph to any landmark.The objective of this work is to find the fewest number of landmarks so that the robot can determine its current node by only using the distances to the landmarks.While dealing with navigation problems，networks are referred to as graphsG，the elements of the metric basis as landmarks，the minimum size of the metric basis as metric dimensiondim(G) and the remaining vertices as nodes and identified the metric dimension of certain simple categories of graphs.The concept of metric basis also yielded significant applications in chemistry，drug design，image processing and combinatorial optimization[27].

But what if the robot takes edges into consideration while calculating distance to any landmark.Can the robot still measure its distance in the graph to any landmark such that the landmarks distinguish the edges instead of vertices?A metric basisSof a connected graphGuniquely identifies all the nodes ofGby means of distance vectors.One could think that the edges of the graph are also identified bySwith respect to the distances toS.However，this does not happen.For instance，F(xiàn)ig.1 shows an example of a graph，where no metric basis uniquely recognizes all the edges of the graph.

Figure 1:The simple graph G

It can be observed that the graphGof Fig.1 satisfies thatdim(G) = 2.But for each one of the metric bases，there exist at least a pair of edges which is not distinguished by the corresponding metric basis as shown in Tab.1.For the metric basis{a，b}the edgesacandadare equidistant from it while for the metric basic{c，d}，the edgesadandbdare equidistant and so on.In this sense，a natural question is:Are there some sets of vertices/nodes which uniquely identify all the edges of a graph?To answer this，a new parameter was recently introduced in which the question is to whether there are some sets of nodes which can uniquely identify all the edges of a graph[28].

Table 1:Metric basis of G and equidistant edges

LetG=(V，E)be a connected graph.Letx∈Vbe a node ande=uv∈Ebe an edge，then the distance between the nodexand the edgeeis defined asdG(e，x)=min{dG(u，x)，dG(v，x)}.A nodex distinguishesany two edgese，fifdG(x，e) ≠dG(x，f).A setS?Vis an edge metric generator(EMG)forGif for any two distinct edgese1 ande2，there exists at least one nodev∈Ssuch that the distancesdG(e1，v)anddG(e2，v)are different.An EMG with the smallest size is referred to as an edge metric basis(EMB)forG，and its size is an edge metric dimension(EMD)，which is denoted byedim(G).Another useful approach for an EMG is as follows.Given an ordered set of nodesS=(s1，s2，...，sd)of a connected graphG，for any edgeeinG，the d-vector(ordered d-tuple)is referred to asr(e|S)=(dG(e，s1)，dG(e，s2)，...，dG(e，sd))as the edge metric representation ofewith respect to S.In this sense，Sis an EMG forGif and only if for every pair of different edgese1，e2 ofG，r(e1|S) ≠r(e2|S)[29].

In[29]，it was proved that theedim(G)=1 if and only if it is a path.They also proved that pathsPn，cyclesCnand complete graphsKnare families of graphs for whomdim(G)=edim(G).

The determination of EMD is NP hard problem.Hence，one has to consider particular classes of graphs.In[30，31]，the author characterized the graphs for whichedim(G)=n-1.The EMD of some graph products was computed in terms of the graphs of the products[32].

In this paper the following have been proved:

·The EMD of Honeycomb networks is 3.

·The EMD of Hexagonal networks is 6.

·The upper bound of two extensions of these networks called the Hex derived networks is proposed.

The rest of the manuscript is organized as follows.Section 2 provides the background of honeycomb and hexagonal networks along with their applications plus the related research in this domain.In Section 3， the edge metric dimension of the honeycomb and hexagonal networks are discussed where the resolving set for the HDN1(n) network is presented.The paper is concluded in the Section 4 while highlighting the limitations and future direction of the proposed work.

2 Background and Related Work

The honeycomb networks are built by recursively using the hexagonal tessellation[33].The honeycomb network can be easily built from simple hexagons in various ways.HC(1)is just a simple hexagon.Adding one hexagon to each edge of this hexagon gives usHC(2).Similarly，HC(n)can be obtained in the same manner.The network cost， defined as the product of degree and diameter， is better for honeycomb networks than for the two other families based on square(mesh-connected computers and tori) and triangular (hexagonal meshes and tori) tessellations.Honeycomb networks provide simple and optimal routing， broadcasting， and semigroup computation algorithm.Honeycomb networks have major applications in mobile base stations， sensor networks， image processing， and computer graphics.The topological properties of honeycomb networks，their routing as well as torus honeycomb networks have been studied in[33].

On the other hand，the hexagonal network which was introduced in[34]is made of a minimum of six triangles and denoted byHX(2)whereasHX(1)does not exist.HX(3)comes from adding a series of triangles aroundHX(2).This pattern can be extended toHX(n).It is easy to see thatnis the number of nodes on any one of the outermost edges of the hexagonal network，see Fig.2.

Figure 2:Honeycomb HC(4)and hexagonal HX(5)networks

Hexagonal networks also have many applications in wireless communication systems，where the cellular concept plays an important role in solving the problem of spectral congestion and capacity.Hence， the hexagonal concept of model coverage plays an important role in such cellular network communications.

Multiprocessor interconnection networks are often required to connect thousands of homogeneously replicated processor-memory pairs，each of which is called a processing node.Instead of using a shared memory， all synchronization and communication between processing nodes for program execution is often done via message passing.Design and use of multiprocessor interconnection networks have recently drawn considerable attention due to the availability of inexpensive， powerful microprocessors and memory chips [34，35].Regular plane tessellations can be easily constructed by repeating regular polygons.This design is of extreme importance for direct interconnection networks as it yields high overall performance.

A lot of research followed this and a host of generators，such as[36，37]，were introduced.However，these generators primarily focused on the differentiation of the nodes.The idea was that a network in which a metric generator can distinguish the vertices behaves like an accurate surveillance activated network.But，if there is an intruder which accesses the network not through its vertices，but by using some connections between them(edges)，then such intruder could not be identified，and in this sense，the surveillance fails in its commitment and some extra property is required in the network to be used effectively for this purpose[38].The honeycomb and hexagonal networks along with the security are studied in[39].Hence，such limitation can cause a major disadvantage from the application point of view.It is this shortcoming，that motivated the authors to explore a unique edge metric generator for this family of networks.

3 Result Discussions and Analysis

In this section， the EMD of the Honeycomb and hexagonal networks will be computed.The bounds for one of the hex derived networks will also be proposed.It is interesting to find that the EMD of honeycomb network and the hexagonal network are constant.For the hex-derived networks，it still needs to be seen whether an exact value for the EMD can be obtained or not.

3.1 Edge Metric Dimension of the Honeycomb Network

In this subsection，the EMD will be computed for the Honeycomb networkHC(n)，It is interesting to note that the EMD is the same as the metric dimension of the honeycomb network.This will provide a partial answer to the question about the families of graphs for which the EMD and the usual metric dimension are same.In order to prove the EMD for the honeycomb network，first the paths for this network are defined.LetαPi，βPjandγ Pkbe paths definingHC(n)such that 0 ≤i，j，k≤2n-1 as shown in the Fig.3.It is easy to see that each edge is the intersection of exactly two different paths.

Figure 3:Paths in honeycomb network-HC(4)

Theorem 1.Let HC(n)be the honeycomb network.Then edim(HC(n))=3.

Proof:This proof consists of two parts，where the first part is divided into three cases depending upon the paths， and the second part is divided into two cases.The first part of the proof is of forward inequality followed by proof of backward inequality thus leading to the equality itself.Since the honeycomb network is built recursively using the hexagonal tessellation， its properties exhibit symmetry across various dimensions.It is to explain these properties，that the proof is further divided into Cases，sometimes followed by sub-cases to further explain the unique cases underlying a particular pattern.

It will be proved thatR={α，β，γ}is a resolving set forHC(n).As one can see from Fig.3，thatHC(n)network consists of three types of edges with respect to each node inR.For simplicity，three types of edges with respect toαwill be taken.The case of the edges with respect to the other nodes ofRcan be resolved in a similar manner.Lete1 ande2 be any two edges ofHC(n).The following cases may ensue，depending on the types of edges.

Case 1:If both edgese1 ande2 belong to the same pathαPifor somei， then they will be distinguished byαitself.

Case 2:If both edgese1 ande2 are parallel such that they lie between two consecutive pathsαPiandαPi+1 for somei，that ise1 ande2 does not completely lie on any of these two consecutive paths，then again，they will be distinguished byα.

Case 3:Ife1 ande2 lie on two different pathsαPiandαPjsuch thati≠j， then all such pair of edgese1 ande2 will be automatically distinguished byαexcept the pair of edges for whomd(e1，α)=d(e2，α).In this situation，two possibilities may arise，i.e.，:Subcase 3a:Ife1，e2 ∈βPkfor somek，then we are in Case 1 for the nodeβ.Subcase 3b:Ife1，e2/∈βPkfor somek，then this happened only ife1 ∈βP2kande2 ∈βPl+1for somekandl，then it is easy to see thatd(e1，γ)＜d(e2，γ)and both edges will be distinguished byγ.Hence，theedim(HC(n))≤3.

Conversely，it can be proved that theedim(HC(n))≥3.On the contrary，suppose that there is a resolving set of cardinality two， sayS= {a， b} ∈V(HC(n)).Since each node ofHC(n) lies on some paths ofα，β，γ，let us consider all the nodes lying on the paths indexed byγ.So，if there exitsiandjsuch thata∈γ Piandb∈γ Pj，then the following two cases are to be considered:

Case 1:Ifi=j，it means that both the nodes ofSlie on a pathγ Piof even lengthl=2q.If the distance between them is denoted byd(a，b)=m.then two cases may arise depending uponm.

Subcase 1a:Ifm ＜l， then there will exist two edgese1 ande2 incident to one of the nodes ofSsaya， such that one of the edges lies on the pathγ Piand the other does not.It is easy to see thatd(e1|S)=d(e2|S)=(0，m).

Subcase 1b:Ifm=l，such thati=j≠nanda，b∈γ Pi，then there exists at least two edgese1 ande2 inγ Pi+1andγ Pi-1such thatd(e1|S)=d(e2|S)=(3，m-2)，a contradiction.Ifi=j=nanda，b∈γ Pn，then again there exists two edgese1 ande2 onγ P3 such thatd(e1|S)=d(e2|S)=(m+1，m+1)，a contradiction.

Case 2:Fori≠j，leta∈γ Piandb∈γ Pjsuch that they also lie onαProrβPs.Then we will be in Case 1 forαorβ.Ifa∈γ Piandb∈γ Pjsuch that they do not lie onαProrβPs，then the following possibilities may ensue:

·Ifd(a，b)＞3，then there exists at least two edgese1 ande2 with the following properties:e1 ande2 are incident on a node of the shortest path betweenaandb，and one of the edges saye1 lies on the shortest path.Hence，d(a，e1)=d(a，e2)=2 andd(e1|S)=d(e2|S).

·Ifd(a，b)=3，andaandblie on two deferent hexagons，then one can find two edgese1 ande2 such thatd(e1|S)=d(e2|S)=(0，3).

·Ifd(a，b)=3，andaandblie on the same hexagon，then one can find two edgese1 ande2 such thatd(e1|S)=d(e2|S)=(0，2).

·Ifd(a，b)=2，then one can find two edgese1 ande2 such thatd(e1|S)=d(e2|S)=(0，2).

·Ifd(a， b) = 1， then there exists two edgese1 ande2 such thatd(e1 |S) =d(e2 |S) = (0， 1).

Hence，theedim(HC(n))＞3 and the proof is finished.

3.2 Edge Metric Dimension of the Hexagonal Network

In order to prove this，the concept of the co-ordinate system of the hexagonal network is presented as adapted by Nocettiet al.[39].He introduced the three axes，X，YandZat an angle of 120 along the sides of any triangle within a hexagonal network as shown in the Fig.4.In this section，the EMD for the hexagonal networkHX(n)will be computed.It is interesting to note that the EMD is larger than the metric dimension of the hexagonal network.This will once again provide a partial answer to the question raised in[40]about the classification of families for which the EMD is larger than the usual metric dimension.

Figure 4:Coordinate system of hexagonal network-HX(5)

The concept of edge neighborhood of a node and state some properties of the same are introduced now.For any nodev∈V(HX(n))ande∈E(HX(n))，the edge neighborhood of a nodevis defined asE Np(v) = {e|d(e，v) =p} where 0 ≤p≤2n- 2.For the convenience of describing the edges， the lines parallel toX-axis are referred to asX-lines and follow the same concept for definingY-lines andZ-lines.Furthermore，a segment of anyX，YorZline is referred to asSX，SYandSZrespectively as shown in the Fig.4.The central node is labeled byoand the six corner nodes of the outer most hexagon as{α，β，γ，θ，σ，ψ}as shown in the Fig.5.

Figure 5:Neighborhoods of hexagonal network-HX(4)

Theorem 2.Let HX(n)be a hexagonal network.Then the edim(HX(n))=6

Proof.We will prove thatR={α，β，γ，θ，σ，ψ}is a resolving set forHX(n).

In order to proof thatR={α，β，γ，θ，σ，ψ}is a resolving set forG，the network is divided into 6 triangles namelyΔαoψ，Δβoα，Δγ oβ，Δθoγ，ΔσoθandΔψoσ.

The proof is presented in two steps.In the first step，it is proved that ife1 ande2 are two edges such thate1 ande2 belong to two different triangles，then they are distinguished by one of the nodes inR.In the second step，it is further proved that ife1 ande2 are two edges belonging to the same triangle，then once again they are distinguished by some node inR.

Case 1:Lete1 ande2 by two edges belongs to two different triangles.There are two subcases to consider depending upon the types of triangles.

Subcase 1a:Lete1 ande2 belong to two non-adjacent triangles.For simplicity let us take the two trianglesΔαoψandΔθoγsuch thate1 ∈Δαoψande2 ∈Δθoγ.Thene1 ∈E Np(α) such that 0 ≤p≤n- 1 ande2 ∈E Np(α) such thatn- 1 ≤p≤2n- 2.Hence， at all timese1 ande2 will be distinguished byα∈Rexcept whenp=n-1.In such a case，it is easy to see thate1 ande2 will be clearly distinguished byψ.

Subcase 1b:Lete1 ande2 belong to two adjacent triangles.Ife1 ande2 lie on the shared side of the two adjacent triangles，then they will fall under the restrictions of Case 2 discussed below.However，if the edgese1 ande2 are chosen such thate1 ∈Δαoψande2 ∈Δψoσsuch that they do not lie on the shared side then it is observed thate1 ∈E Np(α)such that 0 ≤p≤n-1 ande2 ∈E Np(α)such thatn-1 ≤p≤2n-3.Hence，e1 ande2 will be distinguished byα∈Rexcept whenp=n-1.In such a case，it is easy to see thate1 ande2 will be clearly distinguished byσ.Symmetry leads to similar reasoning for the cases of any pair of edges belonging to any pair of triangles in the network.

Case 2:Let the two edgese1 ande2 belong to the same triangle，sayΔψoσ.See Fig.5.In this case，the following is observed:

Subcase 2a:If the two edgese1 ande2 lie on the same segment of one of the co-ordinate axes，saySZof theZ-axis.Then it is easy to see that the two edgese1 ande2 are distinguished byψandγ.Similarly，if the edges belonged toSXorSY，then they will be distinguished byαandθorβandσrespectively.

Subcase 2b:If two edgese1 ande2 are parallel to each other and lie on the segments of one of the axes，saySXiandSXjfori≠j.Then it is clear to note that there exists distinct indicespandqsuch thate1 ∈E Np(β)ande2 ∈E Nq(β)and hence the edges are distinguished byβ.Similar observations will be observed if the edges belonged toSYorSZ.

Subcase 2c:If the two edgese1 ande2 lie on segments of two different axes， then the following two possibilities arise:

a) If two edges are incident on a node，for simplicity，it can be assumed thate1=bd∈SZifor somei，then the following two possibilities arise:

·Ife2=ab∈SXj forsomej，thene1 ande2 will be distinguished byα.

·Ife2=dc∈SXl forsomel，thene1 ande2 will be distinguished byβ.

Similarly，all other edges with a common node can be distinguished in a similar manner.

b) Ife1e2 are not incident edges，then they will be disguised byαexcept ife1，e2 ∈ENr(α).In such a case，if for simplicity lete1 ∈SX，thene1，e2 will be distinguished byβbecause they will lie in different neighborhoods ofβasd(e1，e2)≥1.Hence，edim(HX(n))≤6.

Conversely， LetS= {v1，v2，v3，v4，v5} ?V(G) such thatSis an EMG.Then three cases to be considered.

Case 1:IfSis such thatS∩Zn-1=Φ.Then there will always exist two edgese1 ande2 such thatd(e1|S)=d(e2|S).

Precisely，the two edges would be given bye1=rsande2=rtwherer，s，tare nodes belonging toV(G)such thatr∈Z(n-2)ands，t∈Z(n-1)and their co-ordinates arer=(-1，n-3，n-2)，s=(-1，n-2，n-1)，t=(-2，n-3，n-1).

Case 2:IfSis such thatS∩Zn-1{θ，σ} ≠Φ.Then there will always exist two edgese1 ande2 such thatd(e1|S)=d(e2|S).

Precisely，the two edges would be given bye1=orande2=oswhereo，r，sare nodes belonging toV(G)，o=(0，0，0)，r=(0，1，1)，s=(-1，0，1).

Case 3:SupposeS?{α，β，γ，θ，σ，ψ} such that |S| = 5.For simplicity let us considerS?{α，β，γ，θ，σ} such that |S| = 5.Then there exists two edgese1 ∈EN1(θ) ∩EN2n-1(ψ) ande2 ∈EN2n-1(α)∩EN2n-1(β)such thatd(e1|S)=d(e2|S)，e1 ande2 have a common node with coordinates(0，n–1，n–1).

Thus，all sets of 5 corner nodes of theHX(n)network generate similar equidistant edges.Hence，theedim(HX(n))≥6 which completes the proof.

3.3 Hex Derived Networks

In [41] two hex derived networks were introduced as they have much better connectivity as compared to the honeycomb and hexagonal networks.These areHDN1(n) andHDN2(n)， forn≥2 as shown in Fig.6.

Figure 6:HDN1(n)and HDN2(n)networks

TheHDN1(n)is a planar graph and was shown to have 9n2-15n+7 vertices and 27n2-51n+24 edges with a diameter of 2n-2.TheHDN2(n)graph was shown to have 9n2-15n+7 vertices and 36n2-72n+36 edges with a diameter of 2n-2.These two architecturesHDN1(n)andHDN2(n)have a few advantages over the hexagonal and honeycomb networks.The vertex-edge ratio ofHDN1(n)andHDN2(n)are the same as that of hexagonal and honeycomb networks.However，both these hexagonal and honeycomb networks are simulated by these hex derived networks with no extra cost.This is possible since the hex derived networks contain hexagonal and honeycomb.HDN1(n)is planar，and it accommodates in a given space more processors and wires than hexagonal and honeycomb.In[42]it was proved that the metric dimension ofHDN1(n) andHDN2(n) was between 3 and 4.In [43] it was proved that the metric dimension ofHDN1(n)=4.In this paper，a resolving set for the network ofHDN1(n) was formulated which would make an upper bound of the minimum resolving set forHDN1(n).The resolving setRcontains all the nodes of each Hexagon inside the network，except the central node.Hence， the EMD has to be greater than or equal to 12 and less than |R|， where |R|，depends on the types ofn;even or odd.

Here|R|，represents the upper bound of the proposed resolving set for the hex derived networkHDN1(n)，and k is any positive integer.

The comparison of the research is summarized in Tab.2.It is observed that the Metric dimension of HC(n)proposed in[41]and the edge metric dimension of these networks as proved in this research are the same.However， this research shows that the edge metric dimension of the HX(n) is greater than the metric dimension of HX(n)which was found out to be 3 in[41].While[42]was able to give a bound for both the hex derived networks and[43]found the exact value for HDN1(n)networks and this research is able to find the bounds for the HDN1(n)networks.

Table 2:Edge metric dimension comparison

4 Conclusion and Future Work

In this paper the edge metric dimension of honeycomb and hexagonal networks were studied which could effectively be utilized by wireless sensor networks in a IoT scenario，such as robot/drone navigation.After representing the network via a graph in terms of robots and landmarks， a robot could measure its distance in the graph to any landmark.The objective was to enable robot in finding out the fewest number of landmarks in order to determine its current node thereby using only the distances to the landmarks.It was proved that the minimum landmarks required for a honeycomb networkHC(n)and a hexagonal networkHX(n)are 3 and 6，respectively.The bounds were proposed for the landmarks required for the hex-derived networkHDN1(n)， i.e.， by finding out the resolving set for the network ofHDN1(n).However，the exact values of the number of landmarks required for hex derived networks are still unfound and the methodology proposed for the number of landmarks required for hex networks cannot be naturally extended to hex derived networks.Since the hex derived networks are more efficient in an IoT scenario， exact values for the number of landmarks for these hex-derived networks point towards a future direction of research.

Acknowledgement:The authors thank their families and colleagues for their continued support.

Funding Statement:No funding was received to support any stage of this research study.Zahid Raza is funded by the University of Sharjah under the Projects#2102144098 and#1802144068 and MASEP Research Group.

Conflicts of Interest:The authors declare that they have no conflicts of interest to report regarding the present study.