Grid-Based Hole Recovery Mechanism Using Virtual Force in Hybrid WSNs

Abstract

Sensor nodes are typically empowered with scarce energy resources and limited computing functionality in wireless sensor networks. However, nonuniform random deployment, depletion, and failure of sensor nodes will lead to generating coverage hole in the entire network. These hole problems to occur result in reducing the data transmission performance or in additional power consumption. Consequently, the hole problem is an important factor for the coverage completeness to prolong the network lifetime in wireless sensor networks. We have proposed a hole recovery mechanism based on the grid architecture in hybrid wireless sensor networks. Moreover, virtual force theory is utilized to determine which mobile node should enforce the recovery task. Based on the simulation results, the proposed mechanism is demonstrated to be able to prolong the network lifetime more than 10% with other proposed mechanisms. Otherwise, the proposed mechanism could maintain much more rounds for at least 80% network coverage ratio than other mechanisms.

1. Introduction

The rapid progress of wireless communication and electronics in microsensing MEMS technologies has made wireless sensor networks possible. Recently, wireless sensor networks (WSNs) have been identified as one of the most important wireless communication technologies [1]. A WSN usually consists of a large number of sensor nodes equipped with a wireless antenna whose communication range is limited. In WSNs, each sensor node performs a sensing task to detect specific events and is responsible for gathering data to return to the Sink node or Base station. Applications of WSNs such as environmental monitoring [1], health monitoring [2], target tracking [3], and intrusion detection [4] are common. A significant difficulty in designing these networks is the battery energy, which limits the lifetime and quality of the networks. Therefore, algorithms for WSNs must have low communication overhead, rely as much as possible on local information, adapt to failures and changes in network conditions, and produce results in a timely fashion.

The sensing coverage is one of the most important issues in improving the performance of WSNs [5]. The effectiveness of traditional WSNs is determined to a large extent by the coverage provided by the sensor deployment. In the initial deployment phase, a random deployment of sensor nodes is usually desirable. However, random deployment does not always lead to effective coverage, especially if the sensors are overly clustered and there is a small concentration of sensors in certain parts of the sensor field. The hole problem is one of the fundamental problems in WSNs, and ensuring the region of interest is completely covered at all time is a very important objective [6]. The definition of a hole is as follows: given a set of sensors and a target area, no coverage hole exists in the target area, if every point in that target area is covered by at least k sensors, where k is the required degree of coverage for a particular application [7]. There are several reasons for the existence of this type of hole as follows: (1) the nodes are energy constrained, and the energy may be exhausted by sensing and transmitting; (2) some natural disaster may cause nodes to break down; (3) the initial distribution of sensor nodes is too uneven.

Researchers have begun to consider sensor nodes that are capable of controlled mobility [8], and many algorithms and protocols have been proposed to assign mobile nodes (MNs) to recover the hole and achieve balanced coverage. The hybrid sensor network architecture has been discussed in recent years. In this network system, static and mobile sensor nodes are used to maintain a high coverage ratio or improve network performance.

Grid-based hole recovery mechanism is discussed in this paper as a way to maintain a high coverage ratio and prolong the network lifetime. In addition, the virtual force algorithm [9–11] is used to determine which mobile node should recover the hole according to the distance and residual energy. There are two phases in our mechanism: the network initiation phase and the network maintenance phase. After the deployment of static nodes, the sink determines the hole information and assigns the mobile sensor node to recover it in the network initiation phase. In maintaining high coverage, the network maintenance phase assigns nodes to replace the grid head nodes when their energy is exhausted.

The organization of the paper is as follows. In Section 2, we review the research on topics related to sensor deployment in WSNs, and the details of the proposed mechanism are discussed. The simulation results and analysis are presented in Section 3. Finally, Section 4 draws conclusions and presents future research directions.

2. Grid-Based with Virtual Force Hole Recovery Mechanism (GVF)

In this paper, we propose a hole recovery mechanism (Grid-based with Virtual Force Hole Recovery Mechanism, GVF) in hybrid sensor networks. The system framework is shown in Figure 1. The virtual force formulation considers the distance and remaining energy in the proposed mechanism for increasing the whole network lifetime. The network will enter the network initiation phase after randomly deploying the static sensor nodes. There are three steps in this phase, namely, gridding, hole detection, and hole recovery. In the gridding phase, the entire network will be partitioned into several uniform grids with the same length. The grid head will be selected randomly in each grid at this phase because each has the same remaining energy. The grid head node will later be replaced by the node with the most remaining energy. In the hole detection phase, the sink determines the location and size of the hole. The sink utilizes the grid information table to identify the status of each grid. Then, the sink maintains the hole grid information table to recognize the hole grid. The sink will determine which mobile node will recover the hole in the hole recovery phase. The assignment will be decided according to the virtual force of each pair of the mobile node and hole grid. The mobile node with the maximum virtual force in the virtual force matrix will be selected by the sink to recover the corresponding hole grid. After the network initiation phase, the network maintenance phase will involve monitoring the network to maintain the connectivity of the whole network to discover and recover the occurrence of hole grids. Any mobile node located between the sink and the new hole grid will be considered for reducing the recovery duration. The sink will select the mobile nodes located between the sink and the new hole grid as the candidate nodes. The sink checks whether the remaining energy levels of the candidate mobile nodes are higher than the threshold or not. The candidate mobile node with maximum virtual force will be selected to recover the new hole grid to reduce the recovery duration. Otherwise, the sink will select the neighboring mobile nodes with the maximum virtual force in the virtual force matrix. The system is terminated when the coverage ratio is lower than the threshold.

Figure 1

System framework.

Network environment is a two-dimensional hybrid sensor network that includes mobile nodes and static nodes. The sensing ranges of all sensor nodes are set as R and synchronized. The mobile nodes will be deployed at one hop distance away from the sink to minimize the transmission energy consumption of asking the mobile node to recover the hole grid. Meanwhile, the static sensor nodes are randomly deployed in entire network field. Next, the static sensor nodes will determine the location using the localization mechanism. Here, the location of nodes will be identified with two-dimensional coordinates, where sink is set to $Loc (0,0)$ .

2.1. Virtual Force Formulation

We now describe the virtual forces and virtual force calculation in the proposed algorithm. Let $F_{i j}$ denote the force between mobile node $s_{i}$ and grid j. Note that $F_{i j}$ is determined by the distance and remaining energy. $F_{i j}$ can be expressed by the following [12]:

\begin{matrix} F_{i j} = \frac{m_{i} m_{j}}{d {(i, j)}^{l}}, \end{matrix}

(1)

where

d (i, j)

is the distance between mobile node

s_{i}

and grid j;

m_{i}

is the remaining energy of mobile node

s_{i}

;

m_{j}

is the priority of grid j, whose value is usually 1; and l is the distance coefficient.

2.2. Network Initiation Phase

There are three steps in the network initiation phase, namely, the gridding phase, the hole detection phase, and the hole recovery phase.

2.2.1. Gridding Phase

The entire network will be divided into several identical grids. The length of each grid will be set to d, where $d = \sqrt{2} R / 2$ . This parameter could guarantee that each grid needs just one node to complete the sensing task. The whole WSN will be divided into several grids, each assigned a grid number (Grid $(x, y)$ ). The sink will create a grid information table (GIT) with the grid coordinates information, as shown in Table 1, where Grid $(x, y)$ is the grid number; and Left_Bottom $(x_{1}, y_{1})$ , Left_Top $(x_{2}, y_{2})$ , Right_Bottom $(x_{3}, y_{3})$ , and Right_Top $(x_{4}, y_{4})$ are the coordinates of left bottom, left top, right bottom, and right top boundary coordinates, respectively.

Table 1

Grid information table.

Grid ( $x, y$ )	Left_Bottom $(x_{1}, y_{1}$ )	Left_Top ( $x_{2}, y_{2}$ )	Right_Bottom ( $x_{3}, y_{3}$ )	Right_Top ( $x_{4}, y_{4}$ )
Grid ( $0,0$ )	$Loc (0,0)$	$Loc (0, d)$	$Loc (d, 0)$	$Loc (d, d)$
Grid ( $0,1$ )	$Loc (0, d)$	$Loc (0,2 d)$	$Loc (d, d)$	$Loc (d, 2 d)$
⋮	⋮	⋮	⋮	⋮

Next, the sink broadcasts this information on the grid number to each static sensor node. Because the initial energy of each static sensor node is set to the same value, each grid selects the grid head node randomly in this phase. Afterward, the grid head node will be replaced by the grid node with the most residual energy.

2.2.2. Hole Detection Phase

The sink will broadcast the hole detection request, Det_Hole_Message, to all grid head nodes in the hole detection phase. The message forwarding procedure is shown in Figure 2. The grid head node first checks whether it has received the Det_Hole_Message and then sends the Det_Hole_Ack message to the sink and forwards the Det_Hole_Message to the neighboring grids if the grid head node has not yet received this message. Otherwise, the grid head node will drop the message. Figure 3 shows the message format of the Det_Hole_Message. Packet_type indicates the type of the packet. Loc $(x, y)$ shows the geographical information of the transmitter. Sensor_type indicates the type of transmitter, namely, a sink or static sensor node.

Figure 2

Message forwarding procedures in hole detection phase.

Figure 3

Format of the Det_Hole_Message message.

The packet format of the Det_Hole_Ack is shown in Figure 4. Packet_type indicates the type of packet. Grid $(x, y)$ shows the transmitting grid number.

Figure 4

Format of the Det_Hole_Ack message.

The sink modifies the flag field of GIT upon receiving the Det_Hole_Ack message from the grid head nodes, as shown in Table 1. The sink marks the flag field as 1 if it received the Det_Hole_Ack message from the corresponding grid. Assume that the transmission duration for transmitting a message with range R is T. The sink sets the timer to $T_{i}$ when it receives the Det_Hole_Ack message, where i indicates the transmitted grid number. Figure 5 shows the flowchart of the hole detection mechanism.

Figure 5

Procedures of hole detection phase.

When the sink receives the Det_Hole_Ack from the grid head node from Grid $(x, y)$ , it updates the flag field with 1 in GIT and initializes the timer. Afterward, the sink checks whether the Det_Hole_Ack message from the neighboring grid is received before $T_{i} + 2 T$ . The sink updates the flag field of the corresponding grid with 0 in GIT if the Det_Hole_Ack is not received before $T_{i} + 2 T$ . Otherwise, the sink checks whether the corresponding flag field is set to 1 or not if the timer does not exceed $T_{i} + 2 T$ . The flag field will be set to 1 if it has not been set before. In addition, the sink checks whether the GIT is completed or not. If not, the sink continues to receive the Det_Hole_Ack message from other grid head nodes. The system will enter the hole recovery phase if the GIT is completed.

2.2.3. Hole Recovering Phase

Table 2 shows the hole grid information table (HGIT). Grid $(x, y)$ indicates the grid number. Hole_ID is assigned by the sink to identify the hole grid. Moreover, the MN_ID will be marked with the corresponding mobile sensor node in this phase.

Table 2

Hole grid information table.

Grid ( $x, y$ )	Hole_ID	MN_ID
( $1,0$ )	1
( $0,2$ )	2

As mentioned before, the sink takes the remaining energy and the distance as the factor of virtual force formulation. The value of $m_{i}$ is the same in (1) because every mobile node is equipped with the same energy level in the network initiation phase. Consequently, the primary consideration in selecting the mobile node will be the distance in this phase. The sink maintains $M \times N$ virtual force matrix (VFM) to record the virtual force information between each pair of mobile node and hole grid, where M is the number of mobile nodes and N is the number of hole grids. Consider

\begin{matrix} |\begin{vmatrix} 156.25 & 236.68 & \dots & F_{m - 1, (1,0)} & F_{m, (1,0)} \\ 59.17 & 51.02 & \dots & F_{m - 1, (0, - 2)} & F_{m, (0, - 2)} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ F_{1, (5, - 6)} & F_{2, (5, - 6)} & \dots & F_{m - 1, (5, - 6)} & F_{m, (5, - 6)} \end{vmatrix}| . \end{matrix}

(2)

Each hole grid will be allocated one mobile node by the sink to achieve complete connectivity of the network from VFM. The sink will assign the mobile node according to the following procedures in the hole recovery phase. Figure 6 is the flowchart of selecting MNs in hole recovering phase.

Figure 6

Procedures of selecting MNs.

The sink selects the mobile node with the maximum VF for each hole grid after receiving information from the VFM. Afterward, the sink checks whether there exists any mobile node that has been selected more than once. The sink assigns the mobile node to the corresponding hole grid with the maximum VF if such a duplication exists. Afterwards, the sink assigns other mobile nodes to the remaining hole grids with maximum VF from VFM and checks for duplication. The sink triggers the mobile nodes to recover the hole grids if there is no duplication.

2.3. Network Maintenance Phase

In WSNs, the energy of the nodes will be exhausted by several actions, such as sensing, receiving, and transmitting data [11]. Hole problems may ensue when the nodes run out of energy. In the network maintenance phase, the sink will assign MNs to recover the grids whose nodes have exhausted the energy. Here, the sink will first select the MN with the shortest distance to the hole grid from HGIT to reduce the hole repair time and maintain network coverage. Afterward, the sink will assign another MN to recover the original hole grid to maintain network connectivity.

The procedures of the network maintenance phase are shown in Figure 7. The grid head node will transmit the Hole_Repairing_Request (HRR) to the sink when the remaining energy of the grid head node is lower than the threshold. The sink updates the HGIT for the new hole grid and calculates the value of $D_{current}$ , which is the distance between the sink and the new hole grid. The sink checks if there exist mobile nodes for which $D_{s}$ is smaller than $D_{current}$ . $D_{s}$ indicates the distance between the mobile node and the sink. The sink selects the mobile node with the maximum VF from VFM if there is no mobile node for which $D_{s}$ is smaller than $D_{current}$ . The sink checks whether there exist mobile nodes for which $D_{g}$ is smaller than $D_{current}$ . $D_{g}$ indicates the distance between the mobile node and the new hole grid. The sink selects the mobile node with the maximum VF from VFM if there is no mobile node for which $D_{g}$ is smaller than $D_{current}$ . The sink selects the mobile with maximum VF for which the residual energy is higher than the threshold $T_{recover}$ from the candidate mobile nodes for which $D_{g}$ is smaller than $D_{current}$ . Afterward, the sink will reallocate the other mobile nodes to recover the hole grid.

Figure 7

Procedures of network maintaining phase.

3. Simulation and Results

3.1. Simulation Environment

In our experiments, a number of sensor nodes are randomly deployed in a square field. The static sensor nodes are randomly deployed and equipped with the same capacities for energy, computing, transmitting, sensing, and receiving. The mobile sensor nodes have the same functionalities as the static sensor nodes with the addition of mobility. The performance of the proposed protocol (GVF) was compared with the following other hole recovery mechanisms: bidding protocol [13], Energy-Efficient Coverage Hole Self-Repair in Mobile Sensor Networks (DSEPA) [14], and on-demand [15]. The aim of the experiments is to measure the system lifetime, coverage ratio, message complexity, energy consumption, and average moving distance. Table 3 lists the environmental parameters of the simulation [16–18].

Table 3

Simulation parameters.

Parameter	Values	Parameter	Values
Monitor area	150 m × 150 m	Energy consumption (moving state)	11.2 J/m
Communication radius	20 m	Energy consumption (idle state)	0.727 J/s
Sensing radius	6 m	Energy consumption (transmitting)	0.986 J/s
Initial energy of mobile node	100 J	Energy consumption (receiving)	0.751 J/s
Initial energy of static node	20 J	Number of static sensors	100

3.2. Simulation Results

Figure 6 illustrates the message complexity of those mechanisms. The bidding protocol needs to calculate the bids of all mobile nodes. For this reason, the whole network must transmit far more messages than others to allocate the mobile nodes to recover the coverage hole. In DSEPA and on-demand, the allocation of the mobile node will be determined by the sink. The sink sends the requests to the designated mobile nodes to recover the hole. As shown in Figure 8, the bidding protocol must transmit more messages when the number of mobile nodes increases. Otherwise, the message complexity would not increase with the mobile node ratio in other mechanisms because the assignment is decided by the sink. Here, the DSEPA and on-demand mechanisms require more messages than GVF because of the overlapping sensing areas of the mobile nodes.

Figure 8

Simulation result for the message complexity.

Figure 9 shows the coverage ratio simulation results. Thirty mobile nodes are deployed. The coverage ratio of the bidding protocol decreases faster than in the other cases. Nodes waste a large amount of energy in transmitting the information from all mobile nodes for assignment decisions. DSEPA and on-demand mechanisms need to assign more mobile nodes than GVF to recover the hole. Hence, both mechanisms transmit more messages to trigger mobile nodes for recovery than GVF. For this reason, they will exhaust the energy of the nodes in transmitting requests and thus decrease the coverage ratio of the network. GVF decreases the number of mobile nodes necessary to recover the hole. Hence, the remaining mobile nodes could take over the task of maintaining the network connectivity.

Figure 9

Simulation result for the coverage ratio.

Figure 10 demonstrates the energy consumption of these mechanisms. As mentioned before, the bidding protocol calculates the bid of all mobile nodes to assign the mobile node. It will cause substantial energy depletion to transmit this information and calculate the assignments. The assignments of the mobile nodes will be decided by the sink in other mechanisms. In other words, the main energy consumption in these mechanisms for hole recovery will be the request messages sent to the mobile nodes. Therefore, the GVF will cost less energy than the others due to allocating less mobile nodes.

Figure 10

Simulation result for the energy consumption.

The network lifetime results are illustrated in Figure 11, which shows that the proposed mechanism has better performance than others. DSEPA calculates the empty point of each pair of pilot points, which leads to energy consumption by the static nodes to discover hole information and empty point locations. On-demand will assign more mobile nodes to recover the hole than GVF, with much higher overlap of the sensing area of the mobile nodes. The mobile nodes will waste energy due to sensing the same information as a result of the overlap. Eventually, this situation will cause the mobile node to run out of energy, and another hole problem will arise. For the bidding protocol, energy will be exhausted in computing the bids of all mobile nodes and in transmitting this information.

Figure 11

Simulation result for the system lifetime.

4. Conclusions

Advances in wireless communication and microelectromechanical systems (MEMSs) have enabled the development of low-cost, low-power, multifunctional, tiny sensor nodes that can sense, process, and communicate with one another over short distances. A sensor node by itself has severe resource constraints, including low battery power, limited signal processing, limited computation and communication capabilities, and a small amount of memory. Optimal resource management and assuring reliable QoS are two of the most fundamental requirements in wireless sensor networks. Sensor deployment strategies play a very important role in providing better QoS, which relates to the issue of how well each point in the sensing field is covered. As we know based on the experimental records, coverage hole problems may exist in the sensor networks if the random deployment strategy is used to deploy the static sensor nodes. In this paper, we have proposed a grid-based with virtual force hole recovery mechanism for hybrid wireless sensor networks. The whole network will be divided into grids to ensure the coverage ratio and connectivity. In addition, the virtual force has been taken into consideration for allocating the mobile nodes to recover the hole grid. The proposed hole recovery mechanism could resolve the hole problem and maintain a high coverage ratio in hybrid wireless sensor networks. Furthermore, it could enhance network performance and prolong the network lifetime.

There are several significant issues in wireless sensor networks, which include routing, target tracking, and data aggregation. Addressing these issues could result in better performance in high-connectivity network systems. In our future work, we will design efficient mechanisms addressing these issues based on the proposed network system.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

Biagioni

E. S.

Bridges

K. W.

The application of remote sensor technology to assist the recovery of rare and endangered species

International Journal of High Performance Computing Applications 2002 16 3 315 324

10.1177/10943420020160031001

2-s2.0-2342625573

Schwiebert

Gupta

S. K. S.

Weinmann

Research challenges in wireless networks of biomedical sensors

Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MobiCom '01)

July 2001

Rome, Italy

ACM

151 165

10.1145/381677.381692

Chen

J.-F.

Wang

Y.-H.

Huang

K.-F.

Chang

T.-W.

Grid-based mobile target tracking mechanism in wireless sensor networks

Journal of Communications 2010 5 6 475 482

2-s2.0-78651526590

Roman

Zhou

Lopez

Applying intrusion detection systems to wireless sensor networks

Proceedings of the 3rd IEEE Consumer Communications and Networking Conference (CCNC '06)

January 2006

640 644

10.1109/ccnc.2006.1593102

2-s2.0-33749041485

Mahboubi

Habibi

Aghdam

A. G.

Sayrafian-Pour

Distributed deployment strategies for improved coverage in a network of mobile sensors with prioritized sensing field

IEEE Transactions on Industrial Informatics 2013 9 1 451 461

10.1109/TII.2012.2225436

2-s2.0-84871729095

Zhang

Wang

Liu

HDRE: coverage hole detection with residual energy in wireless sensor networks

Journal of Communications and Networks 2014 16 5 493 501

10.1109/JCN.2014.000088

Huang

C.-F.

Tseng

Y.-C.

The coverage problem in a wireless sensor network

Proceedings of the International Conference on ACM Wireless Sensor Networks and Applications

September 2003

115 121

2-s2.0-1542286906

Sibley

G. T.

Rahimi

M. H.

Sukhatme

G. S.

Robomote: a tiny mobile robot platform for large-scale ad-hoc sensor networks

Proceedings of the IEEE International Conference on Robotics and Automation

May 2002

Washington, DC, USA

1143 1148

2-s2.0-0036055448

Aliouane

Benchaiba

HACH: healing algorithm of coverage hole in a wireless sensor network

Proceedings of the 8th International Conference on Next Generation Mobile Apps, Services and Technologies (NGMAST '14)

September 2014

Oxford, UK

IEEE

215 220

10.1109/NGMAST.2014.35

10.

Mahfoudh

Khoufi

Minet

Laouiti

GDVFA: a distributed algorithm based on grid and virtual forces for the redeployment of WSNs

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '14)

April 2014

Istanbul, Turkey

3040 3045

10.1109/wcnc.2014.6952969

11.

Pantazis

N. A.

Nikolidakis

S. A.

Vergados

D. D.

Energy-efficient routing protocols in wireless sensor networks: a survey

IEEE Communications Surveys & Tutorials 2013 15 2 551 591

10.1109/surv.2012.062612.00084

2-s2.0-84877583241

12.

Yang

Cao

Tan

A new self-deployment algorithm in hybrid sensor network

Proceedings of the IEEE Intelligent Information Technology Application

December 2008

Shanghai, China

268 272

10.1109/iita.2008.77

2-s2.0-62949129313

13.

Wang

Cao

La Porta

A bidding protocol for deploying mobile sensors

Proceedings of the 11th IEEE International Conference on Network Protocols (ICNP '03)

November 2003

Atlanta, Ga, USA

80 91

14.

T. J.

Shi

Energy-efficient coverage hole self-repair in mobile sensor networks

Proceedings of the IEEE International Conference on New Trends in Information and Service Science (NISS '09)

July 2009

Beijing, China

1297 1302

10.1109/niss.2009.249

2-s2.0-70449553543

15.

Shiu

L.-C.

Lee

C.-Y.

Song

T.-W.

Yang

C.-S.

On-demand deployment algorithm for a hybrid sensor network

Proceedings of the 5th International Conference on Embedded and Ubiquitous Computing (EUC '08)

December 2008

Shanghai, China

IEEE

697 702

10.1109/EUC.2008.124

2-s2.0-63149198890

16.

Wang

Cao

La Porta

A bidding protocol for deploying mobile sensors

Proceedings of the IEEE Network Protocols

November 2003

Atlanta, Ga, USA

80 91

17.

T. J.

Shi

Energy-efficient coverage hole self-repair in mobile sensor networks

Proceedings of the International Conference on New Trends in Information and Service Science (NISS '09)

June-July 2009

Beijing, China

IEEE

1297 1302

10.1109/niss.2009.249

2-s2.0-70449553543

18.

Shiu

L.-C.

Lee

C.-Y.

Song

T.-W.

Yang

C.-S.

On-demand deployment algorithm for a hybrid sensor network

Proceedings of the IEEE International Conference on Embedded and Ubiquitous Computing (EUC '08)

December 2008

Shanghai, China

IEEE

697 702

10.1109/euc.2008.124

2-s2.0-63149198890