Holes Detection in Wireless Sensor Networks: A Survey

Published Online April 2014 in MECS DOI: 10.5815/ijmecs.2014.04.04

A wireless sensor networks (WSNs) consist of distributed autonomous sensor-nodes to monitor physical or environmental characteristics, such as temperature, humidity, sound, pollution levels, pressure, direction and wind speed etc. In WSNs, data is transferred from one sensor node to another sensor node through the network [1]. The WSNs are bi-directional. The applications of WSNs are military applications, many industrial and consumer applications, area monitoring etc [2].

Fig 1. An example of WSNs architecture.

A possible example of WSNs architecture is given in fig. 1, where red colored solid lines represent all the possible communication links and orange color dashed area represent sensing coverage, blue colored circles represent all the sensors. A black colored line represents communication lines between sender and receiver.

• A.    Subsystems in WSNs

A WSN consists of three subsystems those are [3]:

• 1)    Sensor subsystem: It senses the area with the help of properties like humidity, pressure, temperature etc.

• 2)    processing sub system:   It provides local

commutation processes on sensed message.

• 3)    Communication subsystem:    Each sensor

communicate with any other sensors by transferring the message.

• B.    Characteristics of a WSNs

The main characteristics [4] of WSNs are:

• •    Power consumption constrains for nodes using batteries or energy harvesting

• •    Ability to cope with sensor node failures

• •    Mobility of sensor nodes

• •   Communication

• •    Scalability to the large area of deployment

• •    Ability to monitor environmental conditions

• •    Ease of use

The rest of the paper is organized as follows. In Section II, holes in WSNs, different types of holes are discussed. In Section III, we have discussed existing solutions to hole detection. Proposed algorithm for hole detection is given in Section IV. Finally the paper concludes with future research direction in Section V.

Fig 2. Taxonomy of various types of Holes in WSNs.

• II.    Holes in WSN

Holes are one of the challenges in deployment of WSNs in a large area. Holes generally considered as a communication gap among sensor nodes. A taxonomy of various types of holes are given in Fig 2, they are coverage hole, Routing hole, Jamming hole, Sink/Black hole and Worm hole. A comparative study of various types of holes are given in Table 1 with their basic mechanisms and features.

Table 1: Comparative study of various types of holes.

Type	Sensor Node Status	Mechanism	Features
Coverage Hole	Alive	Coverage holes depend upon various factors, such as buildings, mountains, technologies, and radio frequency	Unintentional, communication is not possible in that region
Routing Hole	Dead (failured) or act as dead.	Due to failure of the sensor node, holes are created	Routing hole can be unintentional
Jamming Hole	Active	Due to radio frequency in the communication way among the sensors Jamming holes are created	Jamming hole can be unintentional or deliberate
Black/Sink Hole	Sender and Receiver are alive	When incoming or outgoing or both traffic is discarded, without informing the sender, then the data can not reach to its intended receiver	Caused for limited bandwidth and channel accessed by neighboring sensors
Worm Hole	Sender and Receiver Nodes are alive, but they are attacked by Denial of Service attack.	Malicious nodes create a tunnel among themselves. They start forwarding packets and receives from one part of the network to the other end of the tunnel using a separate communication radio channel,then worm holes are created.	It causes nodes located in different parts of networks to believe that they are neighbors, resulting in incorrect routing convergence

• A.    Coverage Hole

One main fundamental issue in WSNs is coverage problem (i.e. coverage holes). Coverage of a sensor node means that the geographic area where the sensor node can communicate with other sensor nodes in WSNs. Coverage of a sensor node mainly depends on two factors. These are - (i) the range (i.e. area) and sensitivity of that sensing nodes, and (ii) density and location of that sensing node in a given region.

Coverage holes depend upon various factors, such as buildings, mountains, technologies, and radio frequency etc. There are various types of coverage holes. These are described below:

Coverage problem in WSNs can be categorized into two sub types; they are “Based on static object (sensor)” and “Based on moving object (sensor)”.

• i.    Based on static sensor

Based on static sensor/object coverage problem in WSNs can be categorized into the following types:

• a)    Area Coverage: The main objective of any sensor network is to cover a geographical area. Sensors may cover a geographical area by different shapes as shown in fig. 3, they are circular-shaped or angle-shaped or triangular-shaped or square-shaped [5].

Angle    Triangular

Circular shaped

Square shaped

shaped     shaped

Fig 3. Different shapes in geographical area are covered by sensor.

Holes exist in a geographical area due to improper positioning of sensor nodes in that area as shown in fig. 4(a), fig. 5, fig. 7, fig. 9. But such problems can be solved by proper positioning of sensor nodes so that nodes can cover and sense the geographical area without any gap as shown in fig. 4(b), fig. 6, fig. 8, fig. 10.

Hole

Fig 4. (a)Hole in circular-shaped geographical area coverage (b) Circular-shaped geographical area coverage without hole.

Fig 5. Hole in Angular-shaped geographical area coverage.

Fig 6. Angular-shaped geographical area coverage without hole.

Fig 7. Hole in Triangular-shaped geographical area coverage.

Fig 10. Square-shaped geographical area coverage without hole.

• b)    Point Coverage : In the point coverage problem, the objective is to cover a set of points. Here, a particular point of area is covered and rest is not covered. This is due to insufficient of sensor nodes deployed than required.

Fig 11. Point Coverage.

• c)    Barrier Coverage: The barrier coverage is the coverage with the goal of minimizing the probability of undetected penetration through the barrier in sensor network.

In Fig 12, mountain is the barrier that separates both the area (a) and (b). Here, area (a) is covered by all the sensors. But, due to the barrier, area (b) is not covered by the sensors.

Fig 12. Barrier Coverage.

Fig 8. Triangular-shaped geographical area coverage without hole.

Fig 9. Hole in Square-shaped geographical area coverage.

• ii.    Based on moving sensor:

Based on moving sensors/objects coverage can be –

• a) Trap Coverage : A new model of coverage, called trap Coverage that scales well with large deployment region. A sensor network providing trap coverage guarantees that any moving object or phenomena can move at most a (known) displacement before it is guaranteed to be detected by the network, for any trajectory and speed.

In the below fig13, deployment, d is the diameter of the largest hole. Although the diameter line intersects this covered area, it still represents the largest displacement that a moving object can travel without being detected in the target region.

A comparative study of various types of coverage holes are given in Table 2.

Fig 13. Trap Coverage

• B.    Routing Hole :

Routing hole is one type of hole where either sensor nodes are not active or the active sensor nodes can not participate in the actual routing of the data due to several reasons. These holes in WSNs can be formed either due to some problems in wireless links or because of failure of sensor nodes due to several reasons such as battery depletion, external events (such as fire), natural obstacles or disaster suffered areas. Routing hole is shown in fig 14, where node c can not participate in routing process.

t able 2: A comparative study of different types of coverage.

Types of Coverage			Mechanism	Limitation	Benefit
S T AT I C SE NS OR S	A r e a C o v e r a g e	Circularshaped area coverage	Sensor covers a particular geographical area circularly.	When a large region is covered by circular shaped coverage, then, there may have some chances to become holes.	It covers some region around the sensor.
		Angleshaped area coverage	Sensor covers a particular Angle-shaped geographical area.	Unintentionally, when this type of hole occurs, then communication is not possible in that region.	For angle shaped region, it will be very useful when we want to covered an angle shaped area.
		Triangleshaped area coverage	Sensor covers a particular Triangle-shaped geographical area.	When this type of hole occurs, then communication is not possible in that region.	1)    Easy to maintain. 2)    Size of the hole is small.
		Squareshaped area coverage	Sensor covers a particular Square-shaped geographical area.	It also has probabilities to become holes.	1)    Easy to maintain. 2)    Size of the hole is small.
	Point Coverage		Sensors cover a set of points. A set of sensors randomly deployed to cover a set of points.	It covers small region.	It is simple to tackle.
	Barrier Coverage		The goal of barrier coverage is minimizing the probability of undetected penetration through the barrier (sensor network).	1)    At the time of covering the region, when the network is bent down from the barrier, then it does not cover the whole region. That time it covers small area. 2)    It is complex, trying to cover whole region. Because sensor waves can’t penetrate the wall or barrier. 3)    Sensors may not be conveniently placed.	1)    Number of waves is more in the region. Eg, area (a) in fig 13. 2)    Low bandwidth.
MO VI NG SE NS OR S	Trap Coverage		It scales well with large deployment region. Here, sensors are moving.	i)    A moving object can travel within the target region without being detected. so, there is a probability to make a hole. ii)    Very tough to maintain.	i)    Sensors cover the region dynamically . ii)    It uses moving sensors.

• D.    Sink/Black Hole:

In WSNs, black or sink holes means a place, where incoming or outgoing or both traffic is discarded, without informing the sender(source) that the data did not reach its intended receiver(destination). Black hole can be detected by checking the lost traffic. The creation of sink hole is caused for limited bandwidth and channel accessed by neighboring sensor nodes. [7].

High Traffic

Fig 16. Sink /Black Hole

C. Jamming Hole

A jamming hole is another type of hole that can occur in tracking applications when the sensor node is tracked with jammers by jamming the radio frequency being used for communication among all the sensor nodes, here sensor node is able to find another sensor node in WSNs, but unable to communicate among them because of communication jamming [5, 9].

Generally, jamming can be unintentional or deliberates.

Unintentional jamming results if one or more sensor nodes continuously use the wireless channels to deny the communication facility among all the neighboring sensor nodes. In deliberate jamming, the opposition sensor node is trying to impair the communication among all the sensors nodes of the WSNs by interfering with the communication ability of the sensor nodes [6].

Fig. 15 depicts an example of jamming hole where node 1 acts as jammer that radiates high radio frequency because of which all neighbor nodes cannot communicate with each other.

High Radio Frequency

Fig 15. Jamming Hole

Here jamming hole is roughly similar to the routing hole. But routing hole is more dangerous than jamming hole, because, in jamming hole sensor nodes are alive, but in routing hole, sensor nodes are dead or act as dead.

• E.    Worm Hole :

Worm hole is one kind of Denial Of Service(DOS) attack [8]. It is an active attack. Here, the contents of the original message are modified in some way. Fabrication causes DOS attack. Fabrication is possible in absence of proper authentication mechanism. Here all the malicious sensor nodes, located in different parts of WSNs, form tunnels among themselves. They start forwarding data packets received at one part of the WSNs to the other end of the tunnel using other communication channel. The receiving malicious sensor node then replays the message in other part of the WSNs. This causes sensor nodes located in different parts of WSNs to believe that they are neighbors, but resulting in incorrect routing convergence.

In Fig. 17, sensor node 3 and 6 create a tunnel between them, because of which sensor node 1 and 4 can not communicate with sensor node 5 and 2 respectively.

Next section gives an overview of existing solutions proposed by researcher to detect coverage hole in WSNs.

III.Existing Solutions to Hole detection

In this section, we present two different solutions for hole detection proposed by researchers, they are vornoi diagram and triangular oriented diagram.

• A.    Voronoi Diagram Approach

Voronoi diagram approach is used to detect a coverage hole and calculate the size of a coverage hole [10, 11]. Voronoi diagram consists of [12] N sensors s1, s2,…, sN. A plane area is divided into N cells. Each cell contains one sensor. Two Voronoi cells meet along a voronoi edge. A sensor node is a voronoi neighbour of other sensor node, if they both share a voronoi edge. Fig. 16 illustrates a Voronoi diagram approach in a plane area.

Fig 18. Illustration of using Voronoi diagram to detect a coverage hole and decide the hole size.

• B.    Triangular Oriented Diagram Approach

One of the solutions to hole detection problem is triangular structure. Authors [12] use the triangular oriented diagram to calculate the size of hole exactly. Fig. 19 shows triangular oriented structure that can be used to detect a coverage hole and calculate the size of a coverage hole [12].

Fig 19. Construction the triangular oriented structure.

Voronoi diagram approach has few limitations like-here shape of each cell is different. So, it is very tough to calculate the exact size of the hole. The limitation of triangular oriented structure is that, it is not a proper hole detection solution because, in a large WSNs, it is complex to connect the centre of three adjacent sensors. There are lots of research works going on in this area [13, 14, 15, 16, 17, 18] to find a good and effective solution to find hole in a wireless sensor network. In the next section, we propose a simple but efficient hole detection algorithm.

• IV .Proposed Algorithm for Hole Detection:

In this section, we have proposed a new algorithm to detect holes in WSNs, the proposed algorithm initially find out whether a sensor node is alive (active) or dead

(failure). When the sensor node is dead, then the geographical area is not covered by that sensor node, so this area will be treated as hole.

At first phase, cluster head sensor node sends a signal to each of the sensor node in the cluster geographically deployed over an area. If anyone of the sensor nodes replies to the cluster head node, then that sensor node is alive or active, otherwise sensor node is dead. Using this algorithm, we can easily find out the alive nodes and dead nodes (or can referred as hole) in WSNs. When a node is dead, then the sensing area of this node will detect a hole in that area.

Algorithm i : integer /* Counter */

N : integer /* Number of sensor nodes in the list of WSN s*/

List : array [0 to N-1] of integer /* A rray of sensor nodes */

Request : integer /* Sender Signal */

Reply : integer /* Receiver Signal */

Alive-node : integer /* Active sensor node */

Dead-node : integer /* Dead sensor node */

Begin for all (i=1 to N) do begin send(Request,node[i]); /* Send a request from master sensor node to the sensor node[i] in the list of WSNs */ wait(Reply,node[i]); /* Wait for replies from sensor node[i] to master node */

If (receiver(Reply)==1) then

Mark (Alive); /* When receiver sensor node[i] replies, then marks the sensor node[i] as alive */

Alive-node := Alive-node + 1; /* Count the number of alive nodes */

Else If (receiver(Reply) != 1) then

Mark (Dead); /* When receiver sensor node[i] does not reply, then marks the sensor node[i] as dead */

Dead-node := Dead-node + 1; /* Count the number of dead nodes */

End if ;

End for ;

End ;

We expect that the proposed algorithm for hole detection will work more efficiently than the others discussed in section III. Analysis and simulation of the proposed algorithm will be done in near future and we will do further research to find the exact solutions that will detect all type of the holes by minimizing the cost and maximizing the sensing area coverage with minimum number of sensor nodes. We will also try to find more efficient algorithm as a solutions to solve hole problem.

• V .conclusion and future research direction

In this paper, we considered the hole problem, which can be used to deal with sensor or node failure. We also proposed a simple and straight-forward algorithm to find out hole.

In future, we would like to find out the exact amount of hole and exact size of each hole to give the exact solution for the hole problem in WSNs. And also we would try to get maximum coverage without any hole by minimum sensors.