\usepackage{epsfig}
\usepackage{caption}
\usepackage{multicol}
-
+\usepackage{times}
\usepackage{graphicx,epstopdf}
\epstopdfsetup{suffix=}
\DeclareGraphicsExtensions{.ps}
\begin{document}
+%\title{ Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks}
\title{Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks}
-
%Activity Scheduling for Coverage and Lifetime Optimization in Wireless Sensor Networks}
% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
-\author{\IEEEauthorblockN{Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier }
-\IEEEauthorblockA{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte, Belfort, France \\
+\author{\IEEEauthorblockN{Ali Kadhum Idrees, Karine Deschinkel, Michel Salomon, and Rapha\"el Couturier}
+\IEEEauthorblockA{FEMTO-ST Institute, UMR 6174 CNRS \\
+University of Franche-Comt\'e, Belfort, France \\
Email: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel, michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr}
%\email{\{ali.idness, karine.deschinkel, michel.salomon, raphael.couturier\}@univ-fcomte.fr}
%\and
One of the fundamental challenges in Wireless Sensor Networks (WSNs)
is the coverage preservation and the extension of the network lifetime
continuously and effectively when monitoring a certain area (or
-region) of interest. In this paper a coverage optimization protocol to
+region) of interest. In this paper, a coverage optimization protocol to
improve the lifetime in heterogeneous energy wireless sensor networks
is proposed. The area of interest is first divided into subregions
using a divide-and-conquer method and then the scheduling of sensor node
active for sensing, is selected to ensure coverage. Each round
consists of four phases: (i)~Information Exchange, (ii)~Leader
Election, (iii)~Decision, and (iv)~Sensing. The decision process is
-carried out by a leader node which solves an integer program.
+carried out by a leader node, which solves an integer program.
Simulation results show that the proposed approach can prolong the
network lifetime and improve the coverage performance.
\end{abstract}
-%\keywords{Area Coverage, Wireless Sensor Networks, lifetime Optimization, Distributed Protocol.}
+\begin{IEEEkeywords}
+Area Coverage, Network lifetime, Optimization, Scheduling, Distributed Protocol.
+\end{IEEEkeywords}
+%\keywords{Area Coverage, Network lifetime, Optimization, Distributed Protocol}
\IEEEpeerreviewmaketitle
\section{Introduction}
-\noindent Recent years have witnessed significant advances in wireless
-communications and embedded micro-sensing MEMS technologies which have
-led to the emergence of wireless sensor networks as one of the most promising
-technologies~\cite{asc02}. In fact, they present huge potential in
-several domains ranging from health care applications to military
-applications. A sensor network is composed of a large number of tiny
-sensing devices deployed in a region of interest. Each device has
-processing and wireless communication capabilities, which enable it to
-sense its environment, to compute, to store information, and to deliver
-report messages to a base station.
-%These sensor nodes run on batteries with limited capacities. To achieve a long life of the network, it is important to conserve battery power. Therefore, lifetime optimisation is one of the most critical issues in wireless sensor networks.
-One of the main design issues in Wireless Sensor Networks (WSNs) is to
-prolong the network lifetime, while achieving acceptable quality of
-service for applications. Indeed, sensor nodes have limited resources
-in terms of memory, energy, and computational power.
-
-Since sensor nodes have limited battery life and without being able to
-replace batteries, especially in remote and hostile environments, it
-is desirable that a WSN should be deployed with high density because
-spatial redundancy can then be exploited to increase the lifetime of
-the network. In such a high density network, if all sensor nodes were
-to be activated at the same time, the lifetime would be reduced. To
-extend the lifetime of the network, the main idea is to take advantage
-of the overlapping sensing regions of some sensor nodes to save
-energy by turning off some of them during the sensing phase.
-Obviously, the deactivation of nodes is only relevant if the coverage
-of the monitored area is not affected. Consequently, future softwares
-may need to adapt appropriately to achieve acceptable quality of
-service for applications. In this paper we concentrate on the area
+\noindent The fast developments in the low-cost sensor devices and wireless communications have allowed the emergence the WSNs. WSN includes a large number of small , limited-power sensors that can sense, process and transmit
+ data over a wireless communication . They communicate with each other by using multi-hop wireless communications , cooperate together to monitor the area of interest, and the measured data can be reported
+ to a monitoring center
+called, sink, for analysis it~\cite{Ammari01, Sudip03}. There are several applications used the WSN including health, home, environmental, military,and industrial applications~\cite{Akyildiz02}.
+The coverage problem is one of the fundamental challenges in WSNs~\cite{Nayak04} that consists in monitoring efficiently and continuously the area of interest. The limited energy of sensors represents the main challenge in the WSNs design~\cite{Ammari01}, where it is difficult to replace and/or
+ recharge their batteries because the the area of interest nature (such as hostile environments) and the cost. So, it is necessary that a WSN deployed with high density because spatial redundancy can then be exploited to increase the lifetime of the network . However, turn on all the sensor nodes, which monitor the same region at the same time leads to decrease the lifetime of the network. To extend the lifetime of the network, the main idea is to take advantage of the overlapping sensing regions of some sensor nodes to save energy by turning off some of them during the sensing phase~\cite{Misra05}. WSNs require energy-efficient solutions to improve the network lifetime that is constrained by the limited power of each sensor node ~\cite{Akyildiz02}.
+In this paper, we concentrate on the area
coverage problem, with the objective of maximizing the network
lifetime by using an adaptive scheduling. The area of interest is
divided into subregions and an activity scheduling for sensor nodes is
discovery phase to exchange information between sensors of the
subregion, in order to choose in a suitable manner a sensor node to
carry out a coverage strategy. This coverage strategy involves the
-solving of an integer program which provides the activation of the
+solving of an integer program, which provides the activation of the
sensors for the sensing phase of the current round.
The remainder of the paper is organized as follows. The next section
% Section~\ref{rw}
reviews the related work in the field. Section~\ref{pd} is devoted to
the scheduling strategy for energy-efficient coverage.
-Section~\ref{cp} gives the coverage model formulation which is used to
+Section~\ref{cp} gives the coverage model formulation, which is used to
schedule the activation of sensors. Section~\ref{exp} shows the
simulation results obtained using the discrete event simulator OMNeT++ \cite{varga}. They fully demonstrate the usefulness of the
proposed approach. Finally, we give concluding remarks and some
%\item Barrier Coverage An objective to determine the maximal support/breach paths that traverse a sensor field. Barrier coverage is expressed as finding one or more routes with starting position and ending position when the targets pass through the area deployed with sensor nodes~\cite{Santosh04,Ai05}.
%\end{itemize}
-{\bf Coverage}
+\subsection{Coverage}
+%{\bf Coverage}
The most discussed coverage problems in literature can be classified
into two types \cite{ma10}: area coverage (also called full or blanket
Target coverage problem is to cover only a finite number of discrete
points called targets. This type of coverage has mainly military
applications. Our work will concentrate on the area coverage by design
-and implementation of a strategy which efficiently selects the active
+and implementation of a strategy, which efficiently selects the active
nodes that must maintain both sensing coverage and network
connectivity and at the same time improve the lifetime of the wireless
-sensor network. But requiring that all physical points of the
+sensor network. But, requiring that all physical points of the
considered region are covered may be too strict, especially where the
sensor network is not dense. Our approach represents an area covered
by a sensor as a set of primary points and tries to maximize the total
minimizing overcoverage (points covered by multiple active sensors
simultaneously).
-{\bf Lifetime}
+\subsection{Lifetime}
+%{\bf Lifetime}
Various definitions exist for the lifetime of a sensor
network~\cite{die09}. The main definitions proposed in the literature are
active sensor node without connectivity towards a base station cannot
transmit information on an event in the area that it monitors.
-{\bf Activity scheduling}
+\subsection{Activity scheduling}
+%{\bf Activity scheduling}
Activity scheduling is to schedule the activation and deactivation of
sensor nodes. The basic objective is to decide which sensors are in
central controller (a node or base station) informs every sensors of
the time intervals to be activated.
-{\bf Distributed approaches}
+\subsection{Distributed approaches}
+%{\bf Distributed approaches}
Some distributed algorithms have been developed
in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02} to perform the
into rounds, where each round has a self-scheduling phase followed by
a sensing phase. Each sensor broadcasts a message containing the node ID
and the node location to its neighbors at the beginning of each round. A
-sensor determines its status by a rule named off-duty eligible rule
+sensor determines its status by a rule named off-duty eligible rule,
which tells him to turn off if its sensing area is covered by its
neighbors. A back-off scheme is introduced to let each sensor delay
the decision process with a random period of time, in order to avoid
%In this paper we focus on centralized algorithms because distributed algorithms are outside the scope of our work. Note that centralized coverage algorithms have the advantage of requiring very low processing power from the sensor nodes which have usually limited processing capabilities. Moreover, a recent study conducted in \cite{pc10} concludes that there is a threshold in terms of network size to switch from a localized to a centralized algorithm. Indeed the exchange of messages in large networks may consume a considerable amount of energy in a localized approach compared to a centralized one.
-{\bf Centralized approaches}
+\subsection{Centralized approaches}
+%{\bf Centralized approaches}
Power efficient centralized schemes differ according to several
criteria \cite{Cardei:2006:ECP:1646656.1646898}, such as the coverage
The first algorithms proposed in the literature consider that the cover
sets are disjoint: a sensor node appears in exactly one of the
generated cover sets. For instance, Slijepcevic and Potkonjak
-\cite{Slijepcevic01powerefficient} propose an algorithm which
+\cite{Slijepcevic01powerefficient} propose an algorithm, which
allocates sensor nodes in mutually independent sets to monitor an area
divided into several fields. Their algorithm builds a cover set by
-including in priority the sensor nodes which cover critical fields,
+including in priority the sensor nodes, which cover critical fields,
that is to say fields that are covered by the smallest number of
sensors. The time complexity of their heuristic is $O(n^2)$ where $n$
-is the number of sensors. \cite{cardei02}~describes a graph coloring
-technique to achieve energy savings by organizing the sensor nodes
-into a maximum number of disjoint dominating sets which are activated
+is the number of sensors. In~\cite{cardei02}, a graph coloring
+technique is described to achieve energy savings by organizing the sensor nodes
+into a maximum number of disjoint dominating sets, which are activated
successively. The dominating sets do not guarantee the coverage of the
whole region of interest. Abrams et
al.~\cite{Abrams:2004:SKA:984622.984684} design three approximation
\cite{Cardei:2005:IWS:1160086.1160098} propose a method to efficiently
compute the maximum number of disjoint set covers such that each set
can monitor all targets. They first transform the problem into a
-maximum flow problem which is formulated as a mixed integer
+maximum flow problem, which is formulated as a mixed integer
programming (MIP). Then their heuristic uses the output of the MIP to
compute disjoint set covers. Results show that this heuristic
provides a number of set covers slightly larger compared to
%More recently Manju and Pujari\cite{Manju2011}
In the case of non-disjoint algorithms \cite{Manju2011}, sensors may
-participate in more than one cover set. In some cases this may
+participate in more than one cover set. In some cases, this may
prolong the lifetime of the network in comparison to the disjoint
cover set algorithms, but designing algorithms for non-disjoint cover
sets generally induces a higher order of complexity. Moreover, in
algorithm~\cite{garg98}, provably near
the optimal solution, is also proposed.
-{\bf Our contribution}
+\subsection{Our contribution}
+%{\bf Our contribution}
-There are three main questions which should be addressed to build a
+There are three main questions, which should be addressed to build a
scheduling strategy. We give a brief answer to these three questions
to describe our approach before going into details in the subsequent
sections.
\cite{pc10}, both centralized and distributed algorithms have their
own advantages and disadvantages. Centralized coverage algorithms
have the advantage of requiring very low processing power from the
- sensor nodes which have usually limited processing capabilities.
+ sensor nodes, which have usually limited processing capabilities.
Distributed algorithms are very adaptable to the dynamic and
scalable nature of sensors network. Authors in \cite{pc10} conclude
that there is a threshold in terms of network size to switch from a
- localized to a centralized algorithm. Indeed the exchange of
+ localized to a centralized algorithm. Indeed, the exchange of
messages in large networks may consume a considerable amount of
energy in a centralized approach compared to a distributed one. Our
work does not consider only one leader to compute and to broadcast
%The working phase works in rounding fashion. Each round include 3 steps described as follow :
\subsection{Leader election phase}
-This step includes choosing the Wireless Sensor Node Leader (WSNL)
+This step includes choosing the Wireless Sensor Node Leader (WSNL),
which will be responsible for executing the coverage algorithm. Each
subregion in the area of interest will select its own WSNL
independently for each round. All the sensor nodes cooperate to
%\noindent We try to produce an adaptive scheduling which allows sensors to operate alternatively so as to prolong the network lifetime. For convenience, the notations and assumptions are described first.
%The wireless sensor node use the binary disk sensing model by which each sensor node will has a certain sensing range is reserved within a circular disk called radius $R_s$.
-\noindent We consider a boolean disk coverage model which is the most
+\indent We consider a boolean disk coverage model which is the most
widely used sensor coverage model in the literature. Each sensor has a
constant sensing range $R_s$. All space points within a disk centered
at the sensor with the radius of the sensing range is said to be
%We choose to representEach wireless sensor node will be represented into a selected number of primary points by which we can know if the sensor node is covered or not.
% Figure ~\ref{fig:cluster2} shows the selected primary points that represents the area of the sensor node and according to the sensing range of the wireless sensor node.
-\noindent Instead of working with the coverage area, we consider for each
+\indent Instead of working with the coverage area, we consider for each
sensor a set of points called primary points. We also assume that the
sensing disk defined by a sensor is covered if all the primary points of
this sensor are covered.
monitored region of interest is covered by the selected set of
sensors, instead of using all the points in the area.
-\noindent We can calculate the positions of the selected primary
+\indent We can calculate the positions of the selected primary
points in the circle disk of the sensing range of a wireless sensor
node (see figure~\ref{fig2}) as follows:\\
$(p_x,p_y)$ = point center of wireless sensor node\\
%To satisfy the coverage requirement, the set of the principal points that will represent all the sensor nodes in the monitored region as $PSET= \lbrace P_1,\ldots ,P_p, \ldots , P_{N_P^k} \rbrace $, where $N_P^k = N_{sp} * N^k $ and according to the proposed model in figure ~\ref{fig:cluster2}. These points can be used by the wireless sensor node leader which will be chosen in each region in A to build a new parameter $\alpha_{jp}$ that represents the coverage possibility for each principal point $P_p$ of each wireless sensor node $s_j$ in $A^k$ as in \eqref{eq12}:\\
-\noindent Our model is based on the model proposed by
+\indent Our model is based on the model proposed by
\cite{pedraza2006} where the objective is to find a maximum number of
disjoint cover sets. To accomplish this goal, authors proposed an
-integer program which forces undercoverage and overcoverage of targets
+integer program, which forces undercoverage and overcoverage of targets
to become minimal at the same time. They use binary variables
$x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our
-model, we consider binary variables $X_{j}$ which determine the
+model, we consider binary variables $X_{j}$, which determine the
activation of sensor $j$ in the sensing phase of the round. We also
consider primary points as targets. The set of primary points is
denoted by $P$ and the set of sensors by $J$.
should be covered by at least one sensor and, if it is not always the
case, overcoverage and undercoverage variables help balancing the
restriction equations by taking positive values. There are two main
-objectives. First we limit the overcoverage of primary points in order to
+objectives. First, we limit the overcoverage of primary points in order to
activate a minimum number of sensors. Second we prevent the absence of monitoring on
some parts of the subregion by minimizing the undercoverage. The
weights $w_\theta$ and $w_U$ must be properly chosen so as to
wireless sensor node when transmitting or receiving packets. The
energy of each node in a network is initialized randomly within the
range 24-60~joules, and each sensor node will consume 0.2 watts during
-the sensing period which will last 60 seconds. Thus, an
+the sensing period, which will last 60 seconds. Thus, an
active node will consume 12~joules during the sensing phase, while a
sleeping node will use 0.002 joules. Each sensor node will not
participate in the next round if its remaining energy is less than 12
-joules. In all experiments the parameters are set as follows:
+joules. In all experiments, the parameters are set as follows:
$R_s=5~m$, $w_{\Theta}=1$, and $w_{U}=|P^2|$.
We evaluate the efficiency of our approach by using some performance
\subsection{The percentage of stopped simulation runs}
-We will now study the percentage of simulations which stopped due to
+We will now study the percentage of simulations, which stopped due to
network disconnections per round for each of the three approaches.
Figure~\ref{fig6} illustrates the percentage of stopped simulation
runs per round for 150 deployed nodes. It can be observed that the
-simple heuristic is the approach which stops first because the nodes
+simple heuristic is the approach, which stops first because the nodes
are randomly chosen. Among the two proposed strategies, the
centralized one first exhibits network disconnections. Thus, as
explained previously, in case of the strategy with several subregions
during one round. They are given for the different approaches and
various numbers of sensors. The lack of any optimization explains why
the heuristic has very low execution times. Conversely, the strategy
-with one leader which requires to solve an optimization problem
+with one leader, which requires to solve an optimization problem
considering all the nodes presents redhibitory execution times.
Moreover, increasing the network size by 50~nodes multiplies the time
by almost a factor of 10. The strategy with two leaders has more
distributed method is clearly required.
\begin{table}[ht]
-\caption{The execution time(s) vs the number of sensors}
+\caption{THE EXECUTION TIME(S) VS THE NUMBER OF SENSORS}
% title of Table
\centering
single global optimization problem by partitioning it in many smaller
problems, one per subregion, that can be solved more easily.
-In future work, we plan to study and propose a coverage protocol which
+In future work, we plan to study and propose a coverage protocol, which
computes all active sensor schedules in one time, using
optimization methods such as swarms optimization or evolutionary
algorithms. The round will still consist of 4 phases, but the
- decision phase will compute the schedules for several sensing phases
- which, aggregated together, define a kind of meta-sensing phase.
+ decision phase will compute the schedules for several sensing phases,
+ which aggregated together, define a kind of meta-sensing phase.
The computation of all cover sets in one time is far more
difficult, but will reduce the communication overhead.
% use section* for acknowledgement
