CNR:A Cluster-Based Solution for Connectivity Restoration for Mobile WSNs

Mahmood ul Hassan,Amin Al-Awady,Khalid Mahmood,Shahzad Ali,Ibrahim Algamdi,Muhammad Kashif Saeed and Safdar Zaman

1Department of Computer Skills,Najran University,Najran,66241,Saudi Arabia

2Department of Information Systems,College of Science and Arts,King Khalid University,Mahayil Asir,63317,Saudi Arabia

3Department of Computer Science,Jouf University,Tabarjal,76769,Saudi Arabia

4Department of Computer Science,Community College Mahayil Asir,King Khalid University,Mahayil,63317,Saudi Arabia

5Federal Directorate of Education,Department of Computer Science,Islamabad,44000,Pakistan

Abstract: Wireless Sensor Networks (WSNs) are an integral part of the Internet of Things (IoT) and are widely used in a plethora of applications.Typically,sensor networks operate in harsh environments where human intervention is often restricted,which makes battery replacement for sensor nodes impractical.Node failure due to battery drainage or harsh environmental conditions poses serious challenges to the connectivity of the network.Without a connectivity restoration mechanism, node failures ultimately lead to a network partition, which affects the basic function of the sensor network.Therefore, the research community actively concentrates on addressing and solving the challenges associated with connectivity restoration in sensor networks.Since energy is a scarce resource in sensor networks, it becomes the focus of research, and researchers strive to propose new solutions that are energy efficient.The common issue that is well studied and considered is how to increase the network’s life span by solving the node failure problem and achieving efficient energy utilization.This paper introduces a Clusterbased Node Recovery (CNR) connectivity restoration mechanism based on the concept of clustering.Clustering is a well-known mechanism in sensor networks,and it is known for its energy-efficient operation and scalability.The proposed technique utilizes a distributed cluster-based approach to identify the failed nodes, while Cluster Heads (CHs) play a significant role in the restoration of connectivity.Extensive simulations were conducted to evaluate the performance of the proposed technique and compare it with the existing techniques.The simulation results show that the proposed technique efficiently addresses node failure and restores connectivity by moving fewer nodes than other existing connectivity restoration mechanisms.The proposed mechanism also yields an improved field coverage as well as a lesser number of packets exchanged as compared to existing state-of-the-art mechanisms.

Keywords: WSNs; CHs; CNR; transmission range; connectivity restoration;node failure; cluster; communication range

1 Introduction

Wireless sensor networks are widely incorporated into many application areas to perform specific tasks.The progress in wireless and sensor technologies has open many application areas in Wireless Sensor Networks (WSNs), such as battlefield surveillance, environment monitoring,healthcare, agriculture, and home automation [1].Wireless sensor networks have gained tremendous attention from the industrial and research community.The rapid growth of WSNs is happening because it is composed of inexpensive tiny devices, and the processing, sensing, and communication capabilities are integrated on a single chip that can work on a low-powered supply of energy.As a result, many wireless sensor nodes are deployed to handle sensing and computation tasks in WSNs.The area of interest for WSN is usually hostile, so the deployment of the wireless sensor nodes is without any pre-configured infrastructure.Thus, the connectivity and coverage restoration in WSN is a primary goal to be achieved in this paper.

The failure of sensor nodes partitions the coverage area into disjoint segments, making multiple functional segments of sensor nodes inaccessible.The failed nodes in a WSN break the network’s connectivity and cause the loss of important sensed information.The large-scale node damage in WSN causes numerous disjoint segments in the network, and information from the source sensor node to the base station cannot be routed.Thus, the network’s rapid connectivity restoration is essential for maintaining the network, observing and routing the critical data to the remote centers.The deployment of additional sensor nodes is often impossible in harsh environments.Therefore, the process of connectivity restoration should be self-healing and self-organized with efficient use of the existing sensor nodes.

Connectivity restoration plays a vital role in the operations of WSN.The tasks in WSN are distributed among all sensor nodes.Due to the resource-constrained characteristic of WSN,it is essential to efficiently use the power, energy, and transmission ranges of the sensor nodes.Clustering is important for achieving energy efficiency and scalability in WSNs.Nodes in a WSN can be combined in such a way that they form a hierarchical topology.This is achieved by making cluster heads, which are powerful nodes that manage many sensor nodes.Sensor nodes send their data readings to the respective cluster heads, which perform data aggregation and eliminate the redundant data before the data is forwarded to a sink node.The cluster head may fail, which requires re-selection of the cluster head.Several approaches have been proposed in the literature to select the primary and backup cluster heads for each sensor node.

A connectivity restoration mechanism based on the concept of clustering is introduced in this paper.The proposed technique is called Cluster-based Node Recovery (CNR).As connectivity restoration is based on clustering, it inherits all the advantages associated with clustering.To achieve connectivity restoration, CNR moves a fewer number of nodes than existing techniques.Our approach utilizes a recovery mechanism called Wireless Broadcast Advantage (WBA) to deal with one of the well-known drawbacks of clustering, known as disruption in inter-cluster communication.CNR uses a distributed cluster-based approach to identify the failed nodes.For the restoration of connectivity, the cluster heads play a significant role.By conducting the extensive simulation, it is proved that CNR outperforms most of the existing state-of-the-art approaches in multiple performance metrics.

The rest of the paper is organized as follows.Section 2 reviews the literature by explaining the work associated with the considered problem.Section 3 presents the research method, while Section 4 illustrates the results and analysis.The paper is concluded in Section 5.

2 Literature Review

The research in the sensor field started in the 1950s, and Sound Surveillance System (SOSUS)was the first introduced sensor network.The research community has contributed to the connectivity restoration, and a large amount of research work has been done that considers the constraints affecting the connectivity restoration process in WSN.Especially, all the techniques designed for connectivity restoration so far focus on node failure detection and recovery.The node failure is detected by failure detection, and it falls into single or collaborative diagnoses depending on the number of nodes that take part in the failure detection process.

The algorithm proposed in [2] uses a Markov chain controller to detect the faulty nodes through changes in the received aggregated path readings at the sink node.Sink nodes broadcast join messages in the network, and upon receiving this message, each node selects a suitable sink node by running an instance of the optimal path routing algorithms.During this process, there is a greater chance that the distribution of sensor nodes for each sink is not even.Therefore, all sink nodes collaborate to make the distribution even.In this case, each sensor node sets its associated sink as the destination node and sends a message containing its ID, list of its neighboring nodes,and IDs of nodes on the route to the sink.After receiving all this information, each sink node constructs an aggregated path.The sink nodes then set a time period for their associated nodes to transmit the data.Each sensor node sends data readings frequently within the permissible time.After receiving data readings, the sink constructs a data table for each sensor node.

The technique presented in [3] deals with failure detection in cluster-based WSNs with the help of neighbor’s coordination and a cluster head detector.The selection of a cluster head depends on the node’s residual energy.If the residual energy is greater than the given threshold,the node becomes a cluster head.The process executes until all cluster heads are selected.After the cluster head selection is finished, each of the remaining nodes has to join at least one cluster head.The cluster heads then start receiving information from their member nodes.If information is received within a specific time period, nodes are considered normal; otherwise, they are counted as dead.The cluster head then calculates the packet delivery ratio for the nodes from which information is received, and it sets an average value for the data packets delivery ratio.If the calculated packet delivery ratio is greater than the average value, the node is considered healthy;otherwise, it is declared a faulty node.

The fuzzy rule-based Faulty Node Classification and Management (FNCM) scheme proposed in [4] resolves the fault detection issue by classifying the sensor nodes according to their hardware status.The cluster head detects the transmitter circuit fault, whereas the node itself detects the receiver circuit, sensor circuit, and battery fault.The fuzzy logic linguistic variables are used to diagnose and declare the hardware status of sensor nodes.The system, based on the fuzzy logic rule, declares the nodes as normal, dead, busy, and idle based on the hardware status.The research work done in PADRA [5] demonstrates failure detection by one of the neighbors.The approach like MPADRA [6] involves two neighbors, whereas the RIM [7] engages all the neighbors for failure detection.

The failure recovery process enables the network to perform its services at the pre-failure level or continues its services with graceful degradation.In terms of the participant nodes that take part in the recovery process, the recovery schemes proposed so far can be classified into single schemes or cooperative schemes.For example, the PADRA uses a single elected neighbor to trigger and execute the recovery process, whereas the RIM and C3R [8] make all the neighbors participate in the recovery process.Similarly, the work in DARA [9] and PADRA offer two-hop information and cascaded relocation for recovery, which incurs much overhead.By contrast, the RIM and the C3R only maintain 1-hop neighbor information.The model presented in [10] adopts various approaches like the centralized approach and distributed approach by introducing mobile robots.A different approach involves three routing protocols (PEGASIS, LEACH, and VGA) proposed in [11] is based on the fact that different transmission ranges are possible to prolong the network lifetime.

The F2CRA and P3CRA algorithms presented in [12] restore the connectivity by providing two vertex-disjoint and three vertex-disjoint paths between every pair of network nodes.The Connectivity Restoration with Assured Fault Tolerance (CRAFT) algorithm proposed in [13] is designed in such a way that it forms the Backbone Polygon (BP) around the center of the partitioned network area.Relay Nodes (RNs) play a vital role in enhancing the connectivity and coverage in an area of interest at a low cost.RNs use two non-overlapping paths that connect each outer partition to the BP and ensure the connectivity restoration of the network.

In [14], the authors propose a novel connectivity restoration technique called Intelligent On-Demand Connectivity Restoration for Wireless Sensor Networks (IDCRWSN).IDCRWSN efficiently utilizes the residual energy and partial transmission range of the sensor nodes in an integrated manner to restore the network connectivity.The simulation results and analysis of IDCRWSN prove that the proposed technique is energy efficient and can better handle node failure.Moreover, the baseline approaches in [14] require large numbers of nodes to participate in the connectivity restoration process, which results in more moved nodes.This major drawback of the baseline approaches can be solved by the IDCRWSN technique.

Efficient Solution for Connectivity Restoration (ESCR) [15] is an energy-efficient technique,which aims to restore the network with an efficient consumption of residual energy and least node movement.Meanwhile, only the node that is near the faulty node and has more energy can participate in the network restoration.In [16], the authors have proposed an energy-efficient connectivity restoration technique called Distributed Energy Efficient Node Relocation (DEENR).This technique consumes less energy during the mobility of sensor nodes, and no communication or mobility model is considered for performance evaluation of this technique.

Considering all the schemes mentioned above for node failure and connectivity restoration in WSNs, it is observed that excessive processing is required to restore wireless sensor network connectivity.To the best of our knowledge, CNR is an efficient technique that adopts a distributed cluster-based approach and imposes less overhead on the sensor nodes while detecting node failure and restoring the connectivity.

3 Research Method

3.1 Problem Formulation

This research proposes a new technique for connectivity restoration that can overcome the drawbacks of the existing techniques.The following assumptions are made for the development of the proposed technique.

? A set of N sensor nodes are randomly deployed in a geographic region.

? There are two types of sensor nodes:Cluster Heads (CHs) and ordinary sensor nodes.

? Cluster heads are assumed to be powerful sensor nodes in terms of processing and battery.

? Ordinary sensor nodes are sensor nodes that are less powerful than the CHs and have motion capabilities.

? Cluster heads are responsible for identifying failed nodes.As the ordinary nodes send information periodically to CHs, there is no need for any additional control messages.

3.2 Energy Model

Each node in WSNs tries to find its neighboring nodes by sending heartbeat messages.It is assumed that every node saves the 1-hops information of the nodes.Every node first sends several beacon messages with different signal strengths to check the forwarding capabilities.Then,other neighboring nodes in the range listen to these messages and return corresponding values.The distance between the nodes is calculated through the Received Signal Strength Indicator(RSSI) [17].The RSSI scheme uses much less energy and does not require time synchronization.Also, it shows the relationship between the received signal energy, transmitted energy, and distance between the nodes.Eqs.(1)–(5) are applied by RSSI in WSNs to find the quality of the link in WSN.

The reason for selecting the RSSI scheme are low power consumption, no time synchronization, and low complexity.There is a relationship between the energy transmitted and the wireless signal energy received that is needed for calculating the distance among nodes [18].This mechanism is used just for the recovery of failure nodes.This relationship is clearly shown in Eq.(1), whereEris the transmitted energy between two actor nodes,ris the distance, andβis the transmission factor for the path loss that depends on the environment.

The logarithm is calculated through the following equation:

In this equation,10logEis the energy represented in dBm.Therefore, Eq.(2) can be written as:

Hereγandβrepresent the link between the signal transmission distance and the received signal.It is supposed that there are no obstacles between the forwarding and receiving sensor nodes.Based on this concept, the energy transmission of wireless signals at a distanceris calculated as:

For two nodes having a distancer, the signals are received with the energy:

λ= 1/ frequency of a node

Agt & Agr = an antenna gain

w = failure element of actor node

r = node distance

The residual energy of a node can be calculated as:

The residual energy notations and their description are listed in Tab.1.

Table 1:Residual energy notation and their description

3.3 System Model

It is considered that nodes are randomly deployed in an area of interest.All nodes have the same transmission range denoted asRc.It is assumed that all the nodes are divided into multiple clusters with a controlling cluster head for each cluster.The first step during the network operation is the selection of the cluster head.The cluster heads are selected based on the residual energy of the sensor nodes.For the details of the cluster head selection, the user can refer to one of our previous works [19].Once the cluster heads are selected, then the ordinary nodes start to send information to the cluster head.The cluster head is responsible for collecting sensed information from the ordinary nodes and the identification of the failed nodes.All nodes associated with a single cluster head are referred to as its neighbors.Each ordinary node periodically sends the sensed information to the cluster head.After collecting information from all neighboring nodes, the cluster head sends the accumulated information to the sink in a multi-hop fashion.The formation of clusters and inter-cluster communication is illustrated in Fig.1.Clustering is an efficient approach in terms of energy consumption because it requires fewer messages to be exchanged among nodes, leading to a substantial increase in the network lifetime.

Figure 1:Formation of clusters and inter-cluster communication

Clustering can be regarded as an effective approach that can further be utilized to detect node failures in the network.Each cluster head contains all the neighbors’information, such as their locations, their IDs, their energy levels, etc.This information is exchanged by using the Hello messages.Each cluster head keeps track of the energy levels for the neighboring nodes.Meanwhile,a threshold calledEtis defined.If a cluster head does not receive a message from a neighboring nodeNi, it checks whether theEt(Ni)of that node during the previous exchange of the message is below the threshold.If both of these conditions are met, then it assumes that the nodeNihas failed.In the next step, the cluster head decides whether the neighbors of the failed node need to be moved toward the failed node.

3.4 Clustering-Based Node Relocation(CNR)

This section explains the working principle of our proposed protocol called Clustering-based Node Relocation (CNR).As introduced in the previous section, CNR makes effective use of clustering for the identification of failed nodes.Once the cluster head detects a failed node, it has to make an important decision regarding the neighboring nodes’movement toward the failed node.The cluster head knows the location of each neighboring node, communication range (Rc),and sensing Range (Rs).The cluster head calculates the sensing area (Ae) that is affected by the failed node.Aecan be seen as the intersection of the three sensing ranges of nodesC,D, andF,as shown in Fig.2.We define a threshold calledAt, which serves as a guideline for neighboring nodes’movement toward the failed node.Atis highly dependent on the particular application or the situation.We assumeAtto be 20 percent of the area of the cluster.IfAeexceeds the threshold value, then the cluster head calculates the distanced1andd2for each neighboring node of the failed node, as shown in Fig.2.The excessive movement of each neighboring node toward the failed node may also reduce the overall sensing area.Therefore, it may not be beneficial for a specific neighbor to move toward the failed node.The cluster head calculates the effective distanceDeffecto move each neighbor.

One challenge that may occur for the restoration of connectivity is inter-cluster communication.As all nodes in the network are mobile, there is always a possibility of disruption of connectivity among the cluster heads.To handle such disruption, we use a simple technique called WBA [20].The phenomenon is that when a wireless message is broadcasted, it is received not only by the receiver but also by the intermediate nodes that are located between the source and destination.Those nodes are called guard nodes.The Fig.1.below shows that nodesC,F, andK(illustrated in blue color) are guard nodes.These nodes play an important role if the two cluster heads go beyond each other’s communication range.The idea is simple.When a cluster head sends an inter-cluster communication message to the other cluster head, these guard nodes receive the message.They wait for an acknowledgment from the other cluster head.The absence of an acknowledgment message indicates connectivity disruption between the two cluster heads.These guard nodes set a timer based on the residual energy such that the timer of a node with a higher energy level expires first and retransmits the inter-cluster message toward the destination cluster head.This technique can mitigate the connectivity disruption among the cluster heads.

Figure 2:Detection of failed node and node relocation within a cluster

?

4 Results and Analysis

To compare the propos ed protocol with the existing baseline protocols, we utilized the INET framework [21] of the OMNeT++ simulator.The performance of the proposed protocol was compared with three existing techniques, including C3R [8], VCR [22], and IDCRWSN [14].The performance metrics used for comparison were the average number of nodes moved, the total distance moved to restore connectivity, the percentage of coverage reduction, and the total number of exchanged packets.The simulation parameters are listed in Tabs.2 and 3 explains the objectives of the baseline algorithms.

Table 2:Simulation parameters and their description

Table 3:Compared baseline techniques

To analyze Algorithm 1, we need to count how many times one instruction is executing in the algorithm.For this purpose, we used the frequency count method shown in Tab.4, which is also called the step cunt method.

Cost=n*c1+n*c2+n*c3+n*c4+n*n*c5+n*n*c6+n*n*c7+n*n*c8+n*n*c9

Cost=n*(c1+c2+c3+c4)+n*n*(c5+c6+c7+c8+c9)

Cost=(c5+c6+c7+c8+c9)*n*n+(c1+c2+c3+c4)*n+0

Cost=(c5+c6+c7+c8+c9)*n2+(c1+c2+c3+c4)*n+0

The cost is of the formf(n)=an2 + bn+c.It means that the function it produces is a quadratic equation, so the complexity of this algorithm isO(n2).

Table 4:Frequency count method for algorithm analysis

4.1 Number of Nodes Moved

Fig.3 shows the performance of all considered protocols in terms of the average number of nodes moved during connectivity restoration.It can be seen from the figure that among all the considered protocols, C3R results in the highest number of nodes moved.The major reason for this phenomenon is cascaded relocation, where a large number of nodes need to move toward the failed node for the connectivity restoration process.Similarly, VCR also results in a higher average number of nodes to be moved for the connectivity restoration process.Due to the excessive movement of neighboring nodes for the connectivity restoration process, both VCR and C3R result in a higher percentage reduction of field.IDCRWSN performs better than C3R and VCR because a special node, called care-taker, moves on-demand to restore the connectivity.Our proposed protocol CNR performs better than the considered protocols.The benefit of using clustering for node relocation is exhibited in the figure.The increase of the number of nodes increases the average number of nodes moved for all considered protocols.However, for CNR, a decline can be observed in the average number of nodes moved as the network’s total number of nodes is increased.The major reason behind this phenomenon is that as we increase the number of nodes in the network, the number of nodes in each cluster also increases.As the movement of nodes toward the failed node is controlled by the cluster head, the decision is based on the reduction in the sensing area.Therefore, more nodes in a cluster indicate moving fewer nodes.

Figure 3:Average number of nodes moved in VCR, C3R, and IDCRWSN

4.2 Coverage Reduction

Fig.4 illustrates the percentage of reduction in field coverage for different communication ranges of the nodes.As the communication range increases, the field coverage reduction decreases for all considered protocols.C3R and VCR perform worse than the other considered protocols.The major reason is the cascaded relocation of excessive nodes, which causes holes in the coverage and results in a drastic reduction in the field coverage.IDCRWSN is based on a centralized approach, where the care-taker nodes are responsible for the connectivity restoration.The centralized control limits the coverage reduction more in IDCRWSN than those in VCR and C3R.Our proposed technique CNR outperforms all the baseline techniques in terms of reduction in field coverage.The percentage of reduction in field coverage is less for higher transmission ranges.

Figure 4:Percentage reduction in field coverage

4.3 Total Distance Moved During Relocation

The total distance moved by all nodes in the network during connectivity restoration is illustrated in Fig.5.The number of nodes in the network varies between 20 to 200.It can be observed in Fig.5 that as the number of nodes increases, the total distance moved during relocation increases for all the baseline protocols (VCR, C3R, and IDCRWSN).However, for our proposed protocol CNR, as the number of nodes in the network increases, the total distance moved during relocation decreases.This is due to the inherent characteristics of clustering.Clustering performs very well in scalability.Therefore, as the number of nodes in the network increases, the probability of finding a suitable neighbor close to the failed node also increases.Therefore, a fewer number of nodes need to be relocated to achieve connectivity restoration.Moreover, CNR also moves the least number of nodes for relocation and does not rely on cascaded relocation, which substantially reduces the total distance moved during relocation.Fig.5 shows two different variations of the CNR withAtequals to 10 percent and 20 percent, respectively.It can be observed from the figure thatAtaffects the performance.ReducingAtresults in a slight increase in the total distance moved during relocation because reducing the thresholdAtresults in moving more relocation nodes.

Figure 5:Nodes vs.moved distance

4.4 Number of Exchanged Packets

The proposed CNR exchanges the least number of packets among all other baseline techniques.Clustering reduces the number of transmitted packets and thus achieves better energy efficiency.Moreover, Fig.6 confirms the scalability of the proposed technique.As the number of nodes increases, the total number of transmitted packets increases for all baseline techniques.Our proposed technique CNR results in the least number of packets transmitted.One major reason for this is the use of clustering to reduce the number of control packets.Moreover, avoiding the excessive movement of the neighboring nodes of a failed node also results in the transmission of fewer packets.

Figure 6:Total number of exchanged packets

5 Conclusion

In this paper, we proposed a novel connectivity restoration technique based on clustering.It moved the least number of nodes when compared to existing techniques for connectivity restoration.Moreover, it also utilized a recovery mechanism called “wireless broadcast advantage”to dealing with connectivity disruption during inter-cluster communication.Besides, our approach utilized a distributed cluster-based approach to identify the failed nodes, and cluster heads played an important role in the restoration of connectivity.In this work, we compared our technique CNR with a variety of baseline techniques.The proposed technique took full advantage of clustering and outperformed all the other considered techniques in terms of multiple performance metrics.

The future work will be conducted in two possible dimensions.The first dimension will involve developing an analytical model for the proposed solution under different mobility models.Further,the second dimension will consider implementing the proposed solution on real sensor nodes and doing extensive performance evaluation.

Acknowledgement:The authors extend their appreciation to the Deanship of Scientific Research at Najran University for funding this work through Research Groups under Grant Number (NU/ESCI/17/093).We appreciate the linguistic assistance provided by TopEdit(www.topeditsci.com) during the preparation of this manuscript.

Funding Statement:This research is funded by Najran University Saudi Arabia, under the research Project Number (NU/ESCI/17/093).URL:www.nu.edu.sa

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