A Fault-Handling Method for the Hamiltonian Cycle in the Hypercube Topology

Adnan A.Hnaif,Abdelfatah A.Tamimi,Ayman M.Abdalla and Iqbal Jebril

Faculty of Science and Information Technology,Al-Zaytoonah University of Jordan,Amman,11733,Jordan

Abstract:Many routing protocols,such as distance vector and link-state protocols are used for fnding the best paths in a network.To fnd the path between the source and destination nodes where every node is visited once with no repeats,Hamiltonian and Hypercube routing protocols are often used.Nonetheless, these algorithms are not designed to solve the problem of a node failure, where one or more nodes become faulty.This paper proposes an effcient modifed Fault-free Hamiltonian Cycle based on the Hypercube Topology (FHCHT) to perform a connection between nodes when one or more nodes become faulty.FHCHT can be applied in a different environment to transmit data with a high-reliability connection by fnding an alternative path between the source and destination nodes when some nodes fail.Moreover,a proposed Hamiltonian Near Cycle(HNC)scheme has been developed and implemented.HNC implementation results indicated that FHCHT produces alternative cycles relatively similar to a Hamiltonian Cycle for the Hypercube, complete, and random graphs.The implementation of the proposed algorithm in a Hypercube achieved a 31% and 76% reduction in cost compared to the complete and random graphs,respectively.

Keywords: Hamiltonian cycle; hypercube; fault tolerance; routing protocols;WSN; IoT

1 Introduction

State-of-the-art technology, especially the Internet of Things (IoT), has increased the demand for Wireless Sensor Networks (WSNs).A WSN is a network of nodes that communicate with each other, sense the environment, and transmit the collected data via wireless links.A sensor network employs small, lightweight, battery-powered devices, known as sensor nodes [1–4].In WSNs, each sensor node is equipped with a wireless communication module.The goal of sensor networks is to monitor a specifc type of data within a particular area.For example, a sensor network can monitor the humidity, the temperature of the surrounding area, fre hazard, traffc status, or wildlife habitat [5–8].Several routing algorithms, such as distance vector and link-state routing protocols [9,10], may be used to connect the nodes of the network, or [11] to connect the nodes of thead hocnetwork.

Although WSNs can successfully distribute data collection for IoT applications, they have limited reliability because one or more nodes may become faulty [12] or need to be secured [13].A sensor network may fail to monitor the surrounding area adequately due to the failure of some modules (such as the presence of factory defects in the sensor units), environmental factors, or battery power depletion.These failures will inevitably lead to a breakdown in the data transmission process between the source and the destination nodes and compromise the quality of service of the entire network [14].

Furthermore, the nature of the region plays an essential role in the distribution of sensors and may increase repair challenges.For example, a geographic territory with steep terrain is not easily accessible for repairing faulty sensors.Therefore, a failure could lead to the partitioning of the network into disjoint blocks, and to changing the routing path.

The problem of a complete halt in any communication network occurs when no message can be delivered towards its destination due to faulty nodes.Consequently, no communication occurs through the sensor nodes until the network administrator takes exceptional action to handle the problem, which usually requires a long time.Hamiltonian and Hypercube Routing Protocols can be used to solve the faulty node problem and therefore have been used in many applications to avoid deadlock issues [15].

Hamiltonian routing protocols employ either a Hamiltonian path or a Hamiltonian cycle.The Hamiltonian path requires visiting each node of the graph exactly once during the routing process.When the end node is the same as the start node, it becomes a Hamiltonian cycle [6].

A Hypercube is either a graphical representation of some nodes and edges or is the set of all n-bit strings denoted by {0,1}nin a single unit in any dimension n, which is called n-cube [16].

A complete graph, denoted by Kn, is a graph where n is the number of nodes with an edge that links each pair of separate nodes.The graph is assumed to be simple; i.e., it contains no loops or multiple edges.

A connected graph G is a graph where each pair of nodes is connected by a simple path.

This paper will present a modifed Hamiltonian cycle protocol implemented on a Hypercube graph to fnd an alternative cycle in case of the occurrence of one or more faulty nodes.Additionally, a new simulator, called HNC, has been designed and implemented to verify the effcacy of this protocol.

The rest of this paper is organized as follows.Section 2 provides graph-theory preliminaries on the Hamiltonian path and cycle and Hypercube graphs.Section 3 reviews related works.In Section 4, the theorems lying behind the proposed algorithm are proven and the general idea of the algorithm is introduced and explained briefy.The algorithm and pseudo code of the algorithm’s components are given in Section 5, where the simulation results are shown in Section 6.Finally, Section 7 concludes the paper followed by the list of references.

2 Preliminaries

This section reviews and discusses some basic concepts and defnitions of the Hamiltonian and Hypercube topologies.

Defnition 1 (Hamiltonian Path):In a graphG, a Hamiltonian Path is a path that contains every node ofG[17].

Defnition 2 (Hamiltonian Cycle):In a graphG, a cyclec?ofG, which contains every node ofG, is said to be a Hamiltonian cycle.In this case,Gis called a Hamiltonian graph [18].

Defnition 3 (Hypercube):A Hypercube, Q_n, is a graph whose node set V consists of the n-dimensional Boolean vectors, i.e., vectors with binary coordinates 0 or 1, where two nodes are adjacent whenever they differ in exactly one coordinate [6].Fig.1 shows an example of a 4-dimensional Hypercube.

Figure 1:A 4-dimensional hypercube

Luca Trevisan [19] proved the following theorem.

Theorem 1:For everyn≥2, the n-dimensional Hypercube has a Hamiltonian cycle.

Consequently, we propose solving the faulty node problem in the Hamiltonian cycle routing protocol for the Hypercube.HypercubeQnwith 2nnodes is an undirected graph where each node is labeled with a binary number that differs from each of its adjacent nodes in exactly one bit.The parity of the node is determined based on the number of 1’s in its binary-number label; i.e.,the parity is 0 if the number of ones is even and otherwise it is 1.

The n-Hypercube graph also called the n-cube graph and commonly denoted as Qnor 2n,is the graph whose vertices are the 2knodes?1,...,?nwhere?i=0 or 1 and two vertices are adjacent if the nodes differ in exactly one coordinate.

In addition, HypercubeQnis not Hamiltonian if all edges are going in one direction and of the same parity of faulty nodes.Consequently, [20] showed that the Hypercube is Hamiltonian ifn≥4.Accordingly, there are two edges of different parity ifQnhas n ≥4 and is free of faulty nodes.

Hsieh et al.[21] presented two theorems.The frst theorem verifed that there exists a faultfree Hamiltonian path in an n-dimensional Mobius cube (denoted byMQn) with up to n ?1 faulty nodes for n ≥4.The second theorem showed that a fault-free cycle with a length between 4 and 2n faulty nodes can be tested in a faulty Mobius cubeMQnwith up to n ?2 faulty nodes for n ≥2.

In order to fnd the most extended cycle in an n-dimensional Hypercube graph G, [22]proposed a twisted Hypercube-like network (THLN) with up to 2n ?9 faulty nodes (F).They showed that(G ?F)contains a Hamiltonian cycle when(δ(G ?F)>2)and(G ?F)include a near Hamiltonian cycle given that(δ(G ?F)≤1).Fig.2 shows a 4-dimensional Hypercube with Hamiltonian cycle.

Figure 2:A 4-dimensional hypercube with Hamiltonian cycle

3 Related Work

This section discusses the traditional Hamiltonian cycle, Hamiltonian path, and Hypercube used to connect nodes.Ammerlaan et al.[18], proved that a Hamiltonian cycle exists between the kth and (n–k)th level of the n-dimensional Hypercube by using the Gray code counting system.To obtain the Gray code counting system, the exclusive-OR operation is computed between the consecutive bits of the corresponding binary number.Other researchers, like [20], implemented an algorithm to detect any Hamiltonian cycle in the cube.They considered an edge u a neighbor of an edge v if u and v are neighbors in Qn and the node(n,v)/∈F is healthy; otherwise, no Hamiltonian cycle is possible.Furthermore, [23] presented a theorem to ensure the existence of a Hamiltonian path in a graph.They assumed G=(V,E)to be a connected graph.For non-adjacent edges, there should be e(u)ande(v)=δ(c,v)≥n+1 and then G will have a Hamiltonian path.

Xiaofan et al.[24] described the properties of the Hypercube, where a single volumetric unit in any dimension is a Hypercube.All edges that meet at a node are perpendicular to each other.A unique digit of length ‘n’ could label each node if the Hypercube is positioned in the origin of the coordinate system.The number of nodes resulting in a unique binary word is equivalent to the possible binary strings of length ‘n’ and can be calculated as the number of nodes=2n.Likewise, [24] designed a layered structure of a Hypercube graph and noted that each corresponding string (node) can be grouped based on the number of ones.Any edge connects two or more nodes if the difference between the nodes is only one bit.can be used to calculate theith number of nodes, and between node layers i andi+1 there exists an edge layer containing(n ?i),or equivalently,(i+1)edges.

Guo et al.[25] devised a new condition of diagnosability to enhance the diagnosability issue.The conditional diagnosability implies that not all neighbors of any edge fail at the same time.Similarly, they proposed that any system is called conditionally t-diagnosable when each pair of the set of the faulty nodes (F0, F1) is distinguishable for |F|≤t and proved that tc(EH(s,t))=3s ?2 for t ≥s>2.

Zhang et al.[22] proposed an architecture called THLN for several multiprocessor systems using Hamiltonian connectivity, based on twisted Hypercube-like networks to improve the communication cost between processors.In addition, they proved that the graph G is an n-dimensional THLN for n ≥5 and F is a subset of V(Gn)∪E(Gn)with |F|.Moreover, they showed that for the node pair(u,v)in the graph Gn ?F, there exists an(n ?2)fault-tolerant Hamiltonian path,except for(u,v)because it is a weak node-pair in Gn ?F.

Liu et al.[26] proved two theorems for the n-dimensional twisted Hypercube Hn.The frst theorem proved that Hn has a fault-free Hamiltonian cycle if the number of the faulty nodes>n?2.The second theorem proved that Hn has a faulty open Hamiltonian path if the number of faulty nodes>n?3 for any pair of non-faulty nodes.Nikolaev et al.[27] introduced an algorithm to fnd a Hamiltonian decomposition of the 4-regular multigraph called the variable neighborhood search (VNS) algorithm.The main objective of VNS is to solve the traveling salesperson problem.For nonadjacent nodes, given two Hamiltonian cycles:x and y, if the graph G(x ∪y)contains a Hamiltonian decomposition into node-disconnect cycles z and w different from x and y, then the corresponding nodes xu and yu are not adjacent.

Chen [28] considered the problem of existing faulty nodes in the Hamiltonian cycle that contains a direct link connection between nodes and avoids the faulty nodes in an n-cube Qn.The author showed that all edges of the matching node M lie on a fault-node-free Hamiltonian cycle in Qn if Qn contains 2n?4?|M| faulty edges and the maximum allowed number of faulty edges is sharp when |M|=1 or |M|=2.

4 Modifed Hamiltonian Cycle Based On Hypercube Topology

Theorem 2:Let G be a Hypercube graph with a degree (n ≥2).If A, B, and C are nodes in G, then there exists at least one Hamiltonian path from A to C through B* whereB?∈G and B?B.

Let G(V,E,w)be a Hypercube graph, where V is the union of all ith node1,2,3,...,The set of nodes in the ith layer can be assigned as shown by Eq.(1)

Let E ?V×V be the set of edges and ‘w’be the function that assigns a non-negative weight w to every edge.Then, the number of edges from any vi,jnode will be w（vi,j,v?）where v?can be calculated by Eq.(2)

In general, the number of all edges in the ith node layer of a Hypercube contains anedge layer.

Proof:Let A=vi,j∈v then:

Case 1:See Eq.(3)

and since(n ≥2)then there is at least (See Eq.(4))

Such that B?B and w(A,B?)exist.

Case 2:See Eq.(5)

and since(n ≥2)then there is at least (See Eq.(6))

Such that B?/B and w(A,B?)exist.

Case 3:See Eq.(7)and since(n ≥2)then there is at least (See Eq.(8))

Such that B?/B and w(A,B?)exist.

Consequently, there exists at least one Hamiltonian path from node A to node C through node B where w(A,B?)and w(B?,C)exist.

To introduce our own proposed algorithm (FHCHT) based on the above theorems, Fig.3 depicts the fowchart of the proposed modifed Hamiltonian Cycle based on Hypercube Topology.

Figure 3:A fowchart of the proposed FHCHT algorithm

To reduce the cost of transmission and avoid existing faulty nodes, the Hamiltonian cycle is used frst to label all nodes and to process the communication between nodes.This phase is called the initialization phase.As mentioned, the Hamiltonian cycle algorithm is used where the source address is the same as the destination address (start node = destination node).At this phase, all nodes are labeled either in binary or in decimal and the transmission phase is applied,which has two scenarios.The frst scenario is called the standard scenario where the packet is transmitted smoothly from the source node to the destination node using the Hamiltonian cycle without any obstacles.The second scenario is when one or more nodes do not work (faulty node).Here, FHCHT is applied to bypass these nodes and go to the next node through an intermediate node, and to fnd other possible paths.

5 Algorithms of the System

In this section, we introduce the two proposed algorithms:Extracting Hamiltonian Cycle and Applying FHCHT.

5.1 Extracting Hamiltonian Cycle

?

Matlab function to create hypercube graph is:G=hypercube (n)Step 2.Find an initial Hamiltonian cycle In order to create a Hamiltonian cycle, choose a starting node, then apply the shortest path algorithm, which will traverse all nodes and end up with the same starting node.For programming purposes, we replace the Hypercube node labels by node label +1 in the Hamiltonian cycle as shown in Fig.4 Matlab function to create hameltonian cycle is:hamPath=fndHam(Graph,Source,Source,totalNodes)

Figure 4:Initial Hamiltonian cycle

The code of the algorithm is as follows:

?

?

5.2 Applying FHCHT

Algorithm 2:Apply FHCHT Step 1.Do for the number of inactive nodes:Step 2.Select a random inactive node (i, j) from Graph G (V, E).Step 3.Apply Exclusive-OR (XOR) operations between the current node (i, j) and each of the previous and subsequent nodes of (i, j).Step 4.Connect the node before and the node after to create a near-Hamiltonian path using Theorem 2.Step 5.Repeat until the destination is reached.

The code for applying the algorithm is as follows:

The Code for Applying FHCHT Function newPath=re_route (n, off_nodes, hamPath)C=extract the elements of those indexes Indexes=fnd (C)newpath=newPath for i=1:length(indexes)for j=1:n node_before(i, j)=bitxor (newpath (indexes (i)?1),2 ∧(j ?1))node_after(i,j)=bitxor(newpath (indexes(i)+1),2 ∧(j ?1))f=intersect(node_before(i,node_after(i,:))f=f(f～=newpath (indexes (i)))new_node (i)=f (1)newpath (indexes (i))=new_node (i)End

Figs.5–7 show a near-Hamiltonian cycle with 1, 2 and 3 faulty nodes respectively.

Figure 5:A near-Hamiltonian cycle with one inactive node

Figure 6:A near-Hamiltonian cycle with two inactive nodes

Figure 7:A near-Hamiltonian cycle with three inactive nodes

6 Experimental Results and Analysis

In this section, we introduce the implementation of the proposed FHCHT algorithm and show the obtained simulation results.The simulation was run with Matlab 2019 on a laptop computer with Intel Core i5 Duo CPU 2900 4M, 4GB DDR3 RAM, and Windows 10 operating system.

As an example, let a Hypercube degree (n=4) and therefore the number of nodes will be 24=16, as illustrated in Fig.1.The frst step is the initialization of the Hypercube topology and then the extraction of the Hamiltonian cycle is applied.See Figs.2 and 4, respectively, where a packet runs through the highlighted path (depicted in red).

The packet format is shown in Tab.1.The input data of Tab.1 are listed below.

P_ID:packet ID, N_ID:Node ID, N_Node:Next Node, W_msg:Wakeup Message, Ack.:Acknowledgment, F_Nodes:Faulty Node(s) and A_Nodes:Alternative Node(s).

Table 1:Packet format

To fnd a near-Hamiltonian path after a faulty node(s) exists, apply Algorithm 2.If a full Hamiltonian cycle exists, then it exits and outputs the Hamiltonian cycle with no faulty nodes.Otherwise, the output is a near-Hamiltonian cycle with one or more loops.

To increase the effciency of the system, the source node will use Tab.2 for reference to avoid the faulty nodes in the subsequent routes when no updates are available.

Table 2:Source reference information

A subcase example is shown in Fig.4.In this example, suppose that node 4 and node 5 become faulty.Consequently, node 2 will send a wakeup message to node 4 and wait to receive an acknowledgment.If the acknowledgment is received, then go to node 4; otherwise, node 4 will be added to the faulty node feld, and FHCHT will be applied to fnd an alternative path from node 2 to node 3.

Additionally, we implemented a complete connected and random connected graphs with node degree greater than or equals 2, in order to compare the effciency and total cost, when we obtain a Hamiltonian or near-Hamiltonian cycle.Fig.8 depicts the complete graph with a Hamiltonian cycle.graph with two faulty nodes (node 4 and 5).

Figure 8:The complete graph with a Hamiltonian cycle

Tab.3 compares the results between a Hypercube, complete, and random graphs based on the number of nodes, the number of faulty nodes, and the name of faulty nodes, where all faulty nodes are selected randomly.The simulator was run on 8 and 16 nodes.For the simulation with 16 nodes, the execution was repeated with three different numbers of faulty nodes–nodes 3, 4,and 5 for all graphs.

Table 3:A comparison between the results of the Hypercube, completed, and random graphs

By applying Algorithm 2 twenty times with a fxed number of nodes with randomly generated faulty nodes, we got the results shown in Tab.4, where the number of graph edges in the Hypercube is equal ton?2n?1 and the number of edges in the complete graph equals(2n(2n?1)/2),where n is the Hypercube degree.

The results show that the time required for the complete graph was better than the time of the Hypercube, while the cost for the complete graph, measured by the number of edges, is greater than in the Hypercube.For instance, for a Hypercube with 16 nodes, the number of edges is 32,while in the complete graph for the same number of nodes the number of edges is 120, which was a signifcant difference between them.

Table 4:A comparison between the results of hypercube, completed, and random graphs based on the number of the randomly generated faulty nodes

At the same time, when we use a graph with a random number of edges to reduce cost, we cannot guarantee an existing Hamiltonian or near-Hamiltonian cycle.Thus, it is not preferable to choose a random number of edges.

7 Conclusion

In this study, a Modifed Fault-free Hamiltonian cycle based on the Hypercube Topology(FHCHT) and a Hamiltonian Near Cycle (HNC) simulator were developed to obtain one or more alternative paths between the source and the destination nodes in WSNs.FHCHT aims to solve a well-known faulty node problem.HNC was applied as follows.First, Hypercube connectivity was used to establish a connection path between the source and destination through a set of active nodes.Second, a random number was chosen to represent the number of faulty nodes.Third,HNC was applied to create and fnd the shortest path.

The results obtained from HNC confrmed that the proposed algorithm fnds multiple alternative paths between the source and destination nodes with the existence of many faulty nodes with an approximate 31% reduction of cost over the complete graph and a 76% reduction over the random graph.However, repeated runs for a Hypercube, complete and random graphs show that the Hypercube edges are fewer than the complete graph edges, which reduces the connection cost.Meanwhile, the random connected graph does not guarantee to obtain a Hamiltonian or near Hamiltonian cycle when a number of faulty nodes exist.The rectifed communication process should enhance the overall effcacy of WSN applications.

Acknowledgement:The authors would like to thank Al-Zaytoonah University of Jordan for supporting this research.

Funding Statement:The author(s) received no specifc funding for this study.

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