Received date: January 28, 2019 Accepted date: February 18, 2019 Published date: February 25, 2019
Citation: Khan AS, Khan M, Nishar A, Nisar A (2018) A Novel Technique for Energy Optimization and Restoration of Connectivity in Wireless Sensor Networks. Am J Compt Sci Inform Technol Vol.7 No.1: 35 doi: 10.21767/2349-3917.100035
Copyright: © 2019 Khan MA, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
In applications of wireless sensor network, especially those attending in hostile environments such as reconnaissance in battlefield, are vulnerable to significant damage due to which single, multiple or simultaneous sensor nodes failure may occur and acquires the wireless sensor network separated into several partitions. The rapid recovery of partition network is essential for inter-node connectivity. Recently, number of approaches proposed for the restoration of inter-node connectivity. However, these approaches have not considered the efficient use of energy, coverage aware and connectivity restoration in integrated manners. This paper fills the gap in integrated manner. A novel technique for different cases of nodes failure is proposed. Initially, sensor nodes are very densely deployed and whole network is relocating after the deployment that each node relocates its position in half of the communication range of neighbor node. The effectiveness of proposed algorithm has been proved by simulation results.
Wireless sensor network; Node relocation; Failure recovery; Network connectivity; Topology repair
In recent years, number of applications has gaining interest in wireless sensor networks; especially they are applicable in harsh environments. In the setup of hostile application, such as reconnaissance of battlefield, surveillance of coast and border, rescue and search, outer space and deep oceans . Mainly, wireless sensor nodes are used for monitoring in the areas of health, home and military purposes because they are selfhealing, self-organized and fault tolerant. In application of military wireless sensor networks are widely used, they are applicable to different tasks in military, such military uses are command, control, targeting, communication and surveillance .
Wireless sensor nodes are small, having limited computing and processing power, and these sensor nodes are less expensive than old-fashioned sensor nodes. These sensors measure, sense and collect data from the environment, they can broadcast the sensed data to manipulator. These nodes consist of with a power supply, an actuator, memory, processing unit and radio. A variety of magnetic, chemical, thermal, optical, biological and mechanical sensors could be combined to the wireless sensor nodes to measure the properties of environment. Typically, wireless sensor nodes are deployed in hard-to-access areas, with very limited memory, a radio is fixed for communication to transmit the data to sink node. The central power source of sensor node is battery. Secondary power source that gather energy from external environment could be added such as solar cell, depending on the sensor nodes and the type of application .
The topology of network, scheme of deployment and size of the network is also affected by monitoring environment. In indoor environment, less number of nodes to cover large area. When the network is out-of-access then pre-planned network is not ideal [4-6]. A massive amount of sensor nodes are involved to make sure coverage of area and increase the reliability of collected information. It is expected that set of mobile nodes will be working, to collectively monitor an area, hunt certain activity or events and perform certain task. By attending in such tough situation, WSNs can reduce human risk and cost. Upon their distribution, it is expected that these nodes could be established a network, to coordinate their action and share information when contributing in the performance of task. Normally, in all activities sensor nodes need to collaborate with each other for the survivors of the network. Connectivity enable by nodes require staying within range. Only, connectivity of inter-node is not important to the usefulness of application, however some sensor nodes may possibly play vital role in keeping flow of data from sensors to the user terminal. Therefore, a sensor typically notifies its neighbor proceeding to moving therefore, topology of WSN becomes adjusted correspondingly . However, damage of node may be come across due to the lack of committed energy and due to the physical impairment given by unfriendly environment that WSN operates in.
The failed node could disturb the connectivity of network and disorder the collected sensed information. In worst case, the network could be separated into multiple segments and may stop working. To avoid negative effect on the activity, the connectivity of network should be restoring. Quick recovery of connectivity is necessary in order to maintain the network to observe activity. Deploying a redundant node instead of dead node is a slow process and is repeatedly impossible in hard and risky areas. Therefore the healing process should be selforganized comprising the survival nodes. Give the unsupervised and autonomous supervision of WSN, allowing the failure could be done in a categorized way. In addition, overall overhead of sensor nodes should be minimum in order to outfit the resource constraints. The number of approaches preferred the repositioning of survival node for the recovery of partitioned network [8-9]. However, these works have focused on recovery of connectivity-loss without observing the negative effects of repositioning nodes on energy consumption and coverage. Primarily, depends on sensing and communication ranges, along deployed redundant nodes. Formerly proposed algorithms for connectivity restoration may exclude some portion of the examined area uncovered by any node. Though coverage is a vital design parameter for sensor networks. Connectivity along with coverage may also be used to measure quality of service of wireless sensor network . Obviously connectivity and coverage have to be considered in an integrated manner. This paper proposes a novel technique for four different cases, considering efficient energy optimization in coverage and connectivity. Moreover, this technique contributes to fill this research gap. This proposed algorithm is applicable for four different scenario, initially, it is assume that nodes are randomly deployed then each node relocate itself in the half of communication range of neighbor node according to . In baseline technique, cascaded relocation toward fail node is done but for the effectiveness of our algorithm initial relocation is done by taking sink node as a reference. The energy consumption during initial relocation is neglected.
The main contribution of our technique is summarizing as follow:
• Firstly, Initial nodes are densely deployed and relocation of network is done after the random deployment.
• Secondly, In case of single cut-vertex node failure, there is no need of relocation of neighbor node for maintaining internode connectivity.
• Thirdly, In case of end node failure, neighbor nodes measure relative distance thus the node with multiple neighbor and less relative distance from fail node, move toward fail node in half of measure distance to fill coverage hole.
• Fourthly, In case of simultaneous cut-vertex nodes failure, each neighbor nodes relocate permanently in half of measure distance from fail nodes for the restoration of internode connectivity.
• Finally, In case of simultaneous end node failure, neighbor nodes relocate themselves permanently according to the above assumption to fill coverage gap. The simulation results shows that this technique has successfully minimized total distance travel, total number of moved nodes, number of exchange messages, percentage reduction in energy consumption and reduction in field coverage.
The relocation of wireless sensor node is deeply studied . Some algorithms allow movement on-demand while other allows post-deployment movement. In hostile environment designers could not place node in most effective areas by hand. Nodes are randomly deployed by helicopter. Some areas may receive dense amount of nodes while some areas may remain vacant. At the end inefficient network is developed, so it is necessary to deploy more nodes.
The number of approaches has only considerer connectivity. A technique is proposed to maximize nodes coverage without avoiding connectivity. Like RIM, mobility of nodes are exploited. For the better coverage of area, the repelling forces idea is proposed among nodes and from the deployment boundaries, due to which nodes are spread. However, the technique does not restore network disjoint problems caused by fail node. In robot networks similar technique is studied for the maintenance of connectivity . The 2-connected network means that there should be minimum two paths between each pair of nodes. The goal is to achieve such 2-desgree of connectivity under node failure. The technique is based on moving a pair of the robots to restore 2-connectivity which has been lost by fails robot. Finally, most related techniques in the literature are: C2AP consider post-deployment coverage and connectivity and increase coverage by spreading inter-connected nodes . A hierarchical architecture is proposed in COCOLA, where coverage is maximize without forwarding data path to 1-tier node by incrementally relocation of higher-tier nodes. Neither C2AP nor COCOLA deals with the failed node impact .
A cascaded movement technique is proposed for the recovery of node failure, in which fails node replaced with nearby node, which is replaced by another node and this process continue until reaching to redundant node . The techniques more related to our work are C3R and RIM [17,18]. C3R assume single or multiple neighbor nodes of failed node for the recovery, failed node is substituted by each neighbor nodes temporarily and get back to its original position after spending limited time at new location. DARA assume probability scheme for the identification of cut vertices and select a neighbor node to the failed node for relocation based on communication links number [17,19] Assume multimode repositioning in which all the neighbor nodes of failed node temporary relocate it. The RIM relocate fails node permanently through inward motion, requiring 1-hop neighbor information for relocation. This paper first address restoring connectivity, coverage and efficient use of energy in an integrated manner.
This paper is organized as follows. The next section shows the methodology of this novel technique, in section 3 simulation results are presented, and finally section 4 concludes this paper.
In our proposed algorithm we assume that all the sensor nodes are densely deployed in integrated manners, their sensing and communication ranges are equal. As all the nodes are deployed randomly in an area of interest, upon deployment nodes are assumed to discover each other. It is assume that initially each node relocate itself permanently according to  and assuming that each node should be present in Rc/2 (communication range) range of their neighbor nodes, remember only those nodes will be relocated themselves, having distance greater then Rc/2 from their neighbors nodes . It is also assume relocation take place from sink node and energy consumption during initial relocation is avoided. The following steps describe the initial relocation of nodes. The initial relocation is shown in Figure 1.
Pre failure knowledge and synchronization
This section explains the scenario for the deployments of nodes. We assume that all the nodes are homogenous; each node is deployed according to the initial definition. Here we assume that the sensing and communication range of all the nodes are same. We refer “Rc” as communication or sensing range because both are same according to assumption.
After the deployments of sensor network each node will broadcast HELLO message in half of its communication range (Rc/2) to introduce itself with neighbor . Each node will share its ID and position in acknowledgment (ACK) to the neighbor nodes within Rc/2 range, this information will be sufficient for the recovery if single or multiple node failure occurred. Each node periodically broadcast synchronization (SYN) message within Rc/2 range. According to the assumption all the nodes must move in same direction. When nodes S5 and S6 does not receive SYN message from neighbor “S7”, it assumes that node “S7” has failed. In this case S5, S6 and S8 send HELLO message toward the failure node direction in Rc range after that transmitting the ACK to each other. And update their list, after updating they start working and restore network as shown in Figure 2. Our algorithm can handle multiple Scenarios, each scenario is discussed below.
Upon detecting the failure of node there are two possibilities that the failure node is the cut vertex or not, either this is single node failure or multiple nodes failure. However, four different cases can arise, each case is discussed below. Node relocation before failure is presented in algorithm 1.
• Algorithm 1: Pseudo-Code for Node Relocation before failure
• If nodes >= Rc/2 to sink node
• Notify neighbors;
• Nodes move toward sink until => Rc/2 away
• If nodes <= Rc/2 to sink node
• Do not move;
• Notify neighbors;
• End If
• Else If nodes receive notification
• For all nodes >= Rc/2 distance to neighbors
• Cascaded movement toward neighbors until =Rc/2 away
• Notify neighbors;
• Broadcast HEARTBEAT;
• Relocation done;
• Each node exists in Rc/2 distance of neighbors
Case I (Cut-vertex failure)
If the failure node is cut vertex as shown in Figure 2, then the neighbor nodes send HELLO message by boosting the range to Rc in failure direction if they receive ACK then there will be no need of mobility to recover the network connectivity. Upon receiving the ACK they update their routing list and continue their operation. In this case the major issue were the restoration of network connectivity, network connectivity will restore without the mobility and as we know that more energy consume during mobility, as this algorithm also prefer coverage so these coverage holes will be fulfill by the neighbors by measuring overlapped distance according to . Cut-vertex failure is presented in algorithm 2.
Algorithm 2: Pseudo-Code for Cut-Vertex Failure
• If (S5,S6 & S8 detect S7 has failed)
• S5, S6 & S8 BROADCAST HEARTBEAT= Rc;
• Upon receiving ACK;
• Update routing table;
• Recovery done without movement;
Case II (End node failure)
If the failure node is not the node which participate in internode connectivity then in this case neighbor will measure the area of overlapped coverage with failure node according to the definition , however the node having much overlapped coverage area prefer to move toward the failure node location in (Rc/4) distance. And send HELLO message by boosting the range to Rc, after the receiving ACK from the neighbor nodes it start to continue operation.
In this scenario node S3 and S6 detect the failure of S4 shown in Figure 3, according to assumption that S4 is not cut vertex so fast recovery is not necessary, these neighbor nodes step forward toward measuring relative overlapped sensing area, as mention above in Figure 3 the overlapped area of S3 as compared to S6 is greater so, S3 move towards failure location only in Rc/4 distance and covered maximum area of failure node, and then boost HELLO message in the range of Rc distance after receiving the ACK it resume the activity shown in Figure 4. The end node failure is presented in algorithm 3.
Case III (Two cut-vertex node failure)
Figure 5 shows simultaneous nodes failure, In this case all the neighbor nodes sent HELLO message in the failure direction in Rc range, due to the failure of simultaneous nodes they did not receive ACK so, they broadcast a coordination message and start moving toward the failure nodes within range of Rc/2 and then send HELLO message upon receiving ACK, restore the connectivity shown in Figure 6. The permanent relocation is good for energy reservation and temporary relocation is better for efficient coverage, Figure 5 and 6 shows the scenario. The two cut-vertex node failure is presented in algorithm 4.
Algorithm 3: Pseudo-code (End node failure)
• If (S3 & S6 detect S4 fails)
• S3 & S6 calculate overlapped area
• S3 having greater overlapped
• S3 moves toward S4= Rc/4 from its origin;
• Broadcast HEARTBEAT start activity;
• Relocation done
Case IV (multiple end node failure)
It is assume in Figure 7, that simultaneous end nodes failure occur in WSN then a huge coverage hole may occur and we cannot compromise this failure in application like combat war, in this scenario the neighbors node send SYN message to adjacent neighbor and tell them that they are changing their location, after that these nodes will move toward the failure nodes in Rc/4 distance, upon reaching they broadcast HELLO message as mention in Figure 8, and continue the activity. In this case the neighbors can cover maximum area of the coverage of the failure nodes. The multiple end node failure is presented in algorithm 5.
Algorithm 4: Pseudo-code (Two cut-vertex node failure)
• If( S5, S6, S9, and S10 detect S7, S8 failure)
• Moving toward F, Rc/4 to its origin;
• BROADCAST HEARTBEAT;
• Start working;
• Connectivity restoration done;
Algorithm 5: Pseudo-code (multiple end node failure)
• If( S1, S5, S6 & S7 detect S2, S3, & S4 failure)
• Moving toward F, Rc/4 to its origin;
• BROADCAST HERATBEAT;
• Start working;
• Coverage enhancement done;
The initial relocation is the major factor of our proposed algorithm, this relocation based on some theorems and in this relocation we avoid the energy consumption, initially we want to relocate each node with neighbor in Rc/2 range. Following are the steps.
Theorem 1: Moving the neighbors until become Rc/2 away from each other.
Proof: In such a motion, the neighbors of sink node would must be located on the circumference of the circle cantered at sink node. After estimating the range if they are not in Rc/2 range or less, then start moving toward sink node and every node must follow these criteria according to its neighbour (relocated node). This relocation would be cascaded. Energy consumption during relocation is avoided for our algorithm.
Theorem 2: Guarantee that cut-vertex will not be introduced during initial relocation.
Proof: As in cascaded movement, where a first node moves motivates its neighbor nodes to follow, in our scenario first neighbor nodes of sink moves and after movement completion send HEARTBEAT to neighbor nodes, then they start movement after completion send ACK and then their neighbor nodes start relocation. And all the nodes will sustain their link with neighbor nodes at its new position.
Randomly dense deployed WSN topologies involve in experiment with varying communication ranges and number of nodes. Nodes number has been set to 100, 150, 200 and 250 in field with dimensions of 900×900 m2. However for our algorithm, experiments were conducted by varying the sensing and communication ranges. The initial energy of every node has been set to 100 joule avoiding the energy consumption in initial relocation.
Consumption of energy occurs due to communication, sensing and movement. Each experiment is done 20 times and then result is averaged. All the results are subjected to 88% confidence analysis interval and stays within 12% of simple mean. The results are comparing with baseline algorithms RIM and . The key difference between our algorithm and the baseline algorithms are that in our algorithm nodes relocate permanently with less travelled distance. In  multi-node relocation is temporary and continues while in RIM relocation is cascaded and permanent.
Figure 9 Shows the total distance travelled by all nodes until the restoration of connectivity is done. Our algorithm significantly outperforms both the RIM and  because it strives to move only nonfvia-critical nodes in order to avoid cascaded relocation. The performance advantage of our algorithm remains consistent even by increasing node communication ranges and densities. This is because our algorithm avoids the critical nodes movement that causes further partitioning of network. Furthermore, our algorithm performs cascaded relocation only when non-critical neighbor nodes failed.
Number of nodes moved
Figure 10 the total number of involved nodes in recovery process when baseline and our algorithm is applied. The simulated results confirm the advantage of our algorithm which moves fewer nodes than RIM and . This is because our algorithm limits the recovery scope and avoid continues and cascaded relocation. Furthermore, the performance of our algorithm remains almost same while varying communication ranges and number of nodes, which shows the great scalability.
Field coverage reduction
Figure 11 shows how coverage is effected by connectivitycentric techniques, the percentage reduction in field coverage is measure, overall our algorithm efficiently limit the coverage loss, the nodes having less coverage overlapped area in sparse networks. The field coverage under our algorithm is much better as decreases in case of baseline algorithms. Field coverage is highly reduced in the case of RIM. In case of proposed technique the overlapped coverage is higher, due to which substitute nodes have to move in small distance, or have not to move. When a node is relocated, its neighbor nodes mostly covered his home area. In sparse networks, less number of nodes are eligible for substitution of failed node and the larger region is remain uncovered during this relocation.
Number of message exchanged
Figure 12 shows the average number of packet exchanged during restoring connectivity under proposed technique and baseline techniques. Each broadcast is considered as a single message. The messaging overhead is minimum in case of proposed technique, while RIM exchanges maximum number of packets. This is because in proposed algorithm only neighbor are engaged in relocation, while in baseline techniques number of exchanged message overhead is more. The number of exchanged messages remains same in case of increased network connectivity for large Rc for proposed technique. The simulated results in Figure 12 based on one round and would be grown over time. However, the effectiveness of our technique is proved by simulated results.
Maintaining internode connectivity, coverage and efficient use of energy is very important in applications of wireless sensor networks, like reconnaissance of battlefield, surveillance of coast and border, rescue and search. Failure of single, multiple and simultaneous nodes can cause serious damage like partition of network and loss of coverage. To restore connectivity multiple issue like lack of coverage and waste of energy can occur. To overcome these major issues proposed algorithm is a reliable solution; according to this algorithm integrity is the vital factor to solve all these issues. The simulated results have proved the design achievements and confirmed the success of this algorithm.
All Published work is licensed under a Creative Commons Attribution 4.0 International License
Copyright © 2019 All rights reserved. iMedPub LTD Last revised : May 21, 2019