Abstract: Area detection and measuring is one of the fundamental
problems in Wireless Sensor Networks (WSN) because it mainly relates to the
continuity and functionality of any routing protocol within Region of Interest
(ROI). While there are holes in the ROI,
Field of movement tracking such as that of animals, people and vehicles can’t
be achieved. Also some phenomena such as fire spreading or water flood can be
controlled by calculating the area of the holes, resulting from the damaged
sensor networks. In this paper, a new mathematical wireless sensor hole detection
algorithm (Wireless Hole Detection) WHD is proposed to accurately estimate the
exact amount of coverage holes under random deployment of sensor nodes. WHD is
developed for achieving Quality of Service (QoS) in terms of power consumption,
and average hole detection time. The dynamic behavior of the proposed WHD
depends on executing the following
steps. Firstly, WHD algorithm cuts down the ROI into many cells using the
advantage of the grid construction to physically partition the ROI into many
small individual cells. Secondly, WHD algorithm works on each cell individually
by allocating the nearest three sensor nodes to each of the cell’s coordinates
by comparing their positions, WHD connects each cell’s coordinate points with the
selected sensor nodes by lines which constructs a group of triangles, then WHD calculates
the area of upcoming triangles. Repeating the previous step on all the cells,
WHD can calculates and locates each hole in the ROI. The performance evaluation
depends on the NS-2 Simulator as a
simulation technique to study and analyze the performance of WHD algorithm. Results
show that WHD outperforms in terms of average energy consumption and average
hole discovery time as compared with Path Density algorithm (PD) and noVel Coverage
Hole Discovery Algorithm (VCHDA).
Keywords: Wireless Sensor Networks,
WSN holes Coverage, Hole detection.
Sensor Network (WSN) is one of the new technologies for detecting and
monitoring life phenomenon. WSNs are composed of large number of sensor nodes
operated by small batteries, sensor nodes are mostly deployed in open and unprotected
environments. Sensor nodes are limited in communication capabilities and battery
power. Nowadays sensor nodes are deployed in large scale due to rapid technological
advances in micro- electro-mechanical systems (MEMS) and low-power wireless
communication 1. WSN’s applications are highly varied, such as target
tracking, environmental monitoring, and battlefield surveillance. WSN are
composed of hundreds or thousands of sensor nodes powered by batteries, they
are deployed in open environments to detect and collect information from the surrounded
phenomenon 2. Then transmit report messages to a remote base station 3. Various
applications are dependent on WSNs such as military field exploration, flood of
water, border protection and forest fires 4, 5, 6.
have unique characteristics due to their physical design, such as unreliability
of sensor nodes, undefined network topology, high computation and communication
power consumption and lots of storage difficulties
7, 8, So many challenges are presented in the solutions design and
applications development of WSNs. In the real life applications, sensor nodes
are randomly scattered over the ROI which allow the presence of some uncovered
areas (Holes) in the ROI which significantly degrade the network performance. The
hole is defined as the area within the ROI that is not covered by any living
sensor. The holes also can be created by the dynamic operations of the sensor nodes.
Sensor nodes usually vanished by impact of random deployment, over heat, movement
of animals, vehicles and people accidents. Such failures occur because sensor
nodes are static nodes and are randomly deployed 9, 10. The failure
of any part of the network directly affects the performance of the total network
locally and globally. The presence of holes in ROI definitely affect the
routing paths, may cause failure of the routing protocols or separation of the
network to many individual small networks.
the area region that is uncovered by any sensor node is considered as a hole, in
which events of interest cannot be accomplished. To overcome the holes
problems, the location of the holes and their areas must be determined, also alternative
sensors are used respectively to keep the sensor alive as much as possible 11. Therefore, holes
coverage and network connectivity are two most important aspects of WSNs 12, 13.
paper, we propose a new wireless sensor holes detection algorithm WHD which
enables the sensor nodes to detect all the holes areas within the ROI, and
calculates the holes areas to help the routing protocol to change its routing
paths or to put extra mobile nodes to heal the holes areas. The proposed WHD
algorithm uses the advantage of dividing the ROI by using the Grid theory 14
to divide ROI into many clusters, and it runs in two phases.
In phase one: WHD divides the ROI
into many equally cells by using the Grid algorithm, then it stores the exact
location of the four edges of each cell to use them in calculating the holes
In phase two: WHD algorithm works
on each single cell individually by determining the coordinates of its four edge
points and the coordinates of the nearest three (if possible) nodes to each cell’s
edge points, then WHD determines if the ranges of the selected sensor nodes
cover the cell’s edge point, if not means there is a hole and WHD begins to
calculate the hole area and its position, yes means that the sensing range of
the sensor nodes cover this coordinate point so there is no hole in that region
of the cell. Figure 1 shows how WHD determines the presence of a hole in a cell.
The rest of this paper is organized as
follows: Section 2 presents related work. Section 3 presents the contributions
of the research work. Section 4 describes the modeling assumptions and problem
goals. The Proposed WHD Algorithm is described in detail in Section 5. Section 6
represents the performance evaluation and the simulation results. Conclusion
and future work are presented in Section 7.
Figure. 1: A hole in one cell
2. Related Work
Two of the most essential and
common problems in WSN are holes area coverage and node connectivity. So many researchers
focused on maximizing coverage and enhancing connectivity across the ROI 10. Authors
in 15 presents strategies for efficient deployment in a mobile sensor
network, where the priority function is defined by a coverage priority of some proposed
points in the ROI. The coverage holes of the network for unequal sensing ranges
of the sensors is utilized by variable weighted Voronoi technique. Each sensor node
works on its Voronoi cell to detect the coverage holes, and then tries to
reduce their size by moving another direction. The weight of the vertices
inside the each Voronoi cell determines the target location of each sensor node.
The authors in 16 propose a novel
algorithm based on algebraic objects, such as Cech complex and Rips complex to accurately
gain information about coverage hole, it depends on the ratio between
communication and sensing radius of a sensor. The authors in 17 propose two novel
algorithms to detect the coverage holes in ROI. The holes borders and their
adjacent nodes can be easily detected by the first algorithm, Distributed
Sector Cover Scanning (DSCS), while locating the coverage holes is done by the
second algorithm, Directional Walk (DW).
by defining a
new deep sleeping technique the authors propose an energy efficient algorithm based on
the sentinel scheme to reduce the sleeping node detection density. Network life
time and power consumption are the factors to calculate the detection rate. In
addition, the coverage holes is addressed by using triangle coverage repair
procedure to heal the coverage hole.
The authors in 19
propose a method that reduces the complexity of the relocation of the initial
deployment and coverage hole healing of mobile sensor nodes in the hybrid WSNs.
Their method finds the ways to get the shortest distance movements for the
mobile nodes in WSNs. An adaptive threshold distance is used to eliminate some
mobile nodes, which are already occupied or situated within the threshold distance
from the optimal new positions. The authors in 20 propose an optimal sensor
deployment in ROI under different nodes communication ranges to achieve the
full coverage. They introduces a novel triangle based pattern called the
Diamond to easily detect and cover the holes while the nodes are in the same
The authors in 21
propose a coverage hole detection algorithms for detecting the holes boundary
in ROI, where sensor nodes can detect their points of intersection of their sensing
discs. The algorithm takes in consideration these points of intersection to
detect the boundaries of the coverage holes.
The authors in 22 propose an
algorithm based on the well-known Voronoi diagram. It can recognize the coverage
holes by comparing the size of voronoi cell to this corresponding node’s
sensing disc, and label the border nodes of coverage holes effectively by using
simple geometric calculations.
of the proposed research work:
In this section, authors
explain how to determine and calculate the total holes area and their breadth formed
in the ROI due to random deployments of sensor nodes or damaged sensor nodes by
any activities. This study enhances the performance of the applied routing
protocol on the network. The proposed WHD algorithm studies the ROI for ease of
building small cells, which increases the network life time and eliminates the direct
communication between sensor nodes and the base station.
Therefore, the main contributions of
the research work can be illustrated as follows:
a homogeneous ROI for ease and better dealing with randomly scattered sensor
nodes as shown in Figure 2.
Build WSN reliable model to
increase WSN life time by cutting down the ROI into many small pre-defined cells.
WHD operates in each single cell individually, then advertise the collected
data to base station according to the selected Routing protocol technique as
shown in Figure 3.
Eliminate the direct
communications between each sensor node and the base station, which consumes less power and raises the network lifetime.
Develop an NS-2 simulator
model, describing the performance evaluation of the proposed WHD Algorithm.
Assumption and Problem Goals
In this paper, some assumptions
are used regarding the WSNs:
a- Nodes are distributed randomly among a 2-dimentional space e.g. (X,
b- All sensor nodes are homogeneous and have the exact power supply
c- All sensor nodes have the same initial energy power.
Radio channel is equal, the
amount of energy consumption for transmitting and receiving a message is the
The sensing and the
communication ranges are the same for all sensor nodes.
f- Each node can determine its
location after deployment through GPS devices or other localization approaches.