Karine Deschinkel,~\IEEEmembership{}
Michel Salomon,~\IEEEmembership{}
and~Rapha\"el Couturier ~\IEEEmembership{}
- \thanks{The authors are with FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comt\'e,
+ \thanks{The authors are with FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comte,
Belfort, France. Email: ali.idness@edu.univ-fcomte.fr, $\lbrace$karine.deschinkel,
michel.salomon, raphael.couturier$\rbrace$@univ-fcomte.fr}}
this paper, we propose such an approach called Lifetime Coverage Optimization
protocol (LiCO). It is a hybrid of centralized and distributed methods: the
region of interest is first subdivided into subregions and our protocol is then
-distributed among sensor nodes in each subregion. A sensor node which runs LiCO
-protocol repeats periodically four stages: information exchange, leader
-election, optimization decision, and sensing. More precisely, the scheduling of
-nodes' activities (sleep/wake up duty cycles) is achieved in each subregion by a
-leader selected after cooperation between nodes within the same subregion. The
-novelty of our approach lies essentially in the formulation of a new
+distributed among sensor nodes in each subregion.
+%%RAPH abstract too long
+% A sensor node which runs LiCO
+%protocol repeats periodically four stages: information exchange, leader
+%election, optimization decision, and sensing. More precisely, the scheduling of
+%nodes' activities (sleep/wake up duty cycles) is achieved in each subregion by a
+%leader selected after cooperation between nodes within the same subregion.
+The novelty of our approach lies essentially in the formulation of a new
mathematical optimization model based on perimeter coverage level to schedule
sensors' activities. Extensive simulation experiments have been performed using
OMNeT++, the discrete event simulator, to demonstrate that LiCO is capable to
This paper makes the following contributions.
\begin{enumerate}
-\item We devise a framework to schedule nodes to be activated alternatively such
+\item We have devised a framework to schedule nodes to be activated alternatively such
that the network lifetime is prolonged while ensuring that a certain level of
coverage is preserved. A key idea in our framework is to exploit spatial and
- temporal subdivision. On the one hand the area of interest if divided into
- several smaller subregions and on the other hand the time line is divided into
+ temporal subdivision. On the one hand, the area of interest if divided into
+ several smaller subregions and, on the other hand, the time line is divided into
periods of equal length. In each subregion the sensor nodes will cooperatively
choose a leader which will schedule nodes' activities, and this grouping of
sensors is similar to typical cluster architecture.
-\item We propose a new mathematical optimization model. Instead of trying to
+\item We have proposed a new mathematical optimization model. Instead of trying to
cover a set of specified points/targets as in most of the methods proposed in
the literature, we formulate an integer program based on perimeter coverage of
each sensor. The model involves integer variables to capture the deviations
- between the actual level of coverage and the required level. So that an
+ between the actual level of coverage and the required level. Hence, an
optimal scheduling will be obtained by minimizing a weighted sum of these
deviations.
-\item We conducted extensive simulation experiments, using the discrete event
- simulator OMNeT++, to demonstrate the efficiency of our protocol. We compared
+\item We have conducted extensive simulation experiments, using the discrete event
+ simulator OMNeT++, to demonstrate the efficiency of our protocol. We have compared
our LiCO protocol to two approaches found in the literature:
DESK~\cite{ChinhVu} and GAF~\cite{xu2001geography}, and also to our previous
work published in~\cite{Idrees2} which is based on another optimization model
coverage model formulation which is used to schedule the activation of sensor
nodes. Section~\ref{sec:Simulation Results and Analysis} presents simulations
results and discusses the comparison with other approaches. Finally, concluding
-remarks are drawn and some suggestions given for future works in
+remarks are drawn and some suggestions are given for future works in
Section~\ref{sec:Conclusion and Future Works}.
% that show that our protocol outperforms others protocols.
The most discussed coverage problems in literature can be classified in three
categories~\cite{li2013survey} according to their respective monitoring
objective. Hence, area coverage \cite{Misra} means that every point inside a
-fixed area must be monitored, while target coverage~\cite{yang2014novel} refer
+fixed area must be monitored, while target coverage~\cite{yang2014novel} refers
to the objective of coverage for a finite number of discrete points called
targets, and barrier coverage~\cite{HeShibo}\cite{kim2013maximum} focuses on
preventing intruders from entering into the region of interest. In
sensors are sufficiently covered it will be the case for the whole area. They
provide an algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of
each sensor, where $d$ denotes the maximum number of sensors that are
-neighboring to a sensor and $n$ is the total number of sensors in the
+neighbors to a sensor and $n$ is the total number of sensors in the
network. {\it In LiCO protocol, instead of determining the level of coverage of
a set of discrete points, our optimization model is based on checking the
perimeter-coverage of each sensor to activate a minimal number of sensors.}
decisions, followed by a sensing phase where one cover set is in charge of the
sensing task.}
-Various centralized and distributed approaches, or even a mixing of these two
+Various centralized and distributed approaches, or even a mixing of these two
concepts, have been proposed to extend the network lifetime. In distributed
algorithms~\cite{yangnovel,ChinhVu,qu2013distributed} each sensor decides of its
own activity scheduling after an information exchange with its neighbors. The
-main interest of a such approach is to avoid long range communications and thus
+main interest of such an approach is to avoid long range communications and thus
to reduce the energy dedicated to the communications. Unfortunately, since each
-node has only information on its immediate neighbors (usually the one-hop ones)
+node has only information on its immediate neighbors (usually the one-hop ones)
it may take a bad decision leading to a global suboptimal solution. Conversely,
centralized
-algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always
+algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always
provide nearly or close to optimal solution since the algorithm has a global
view of the whole network. The disadvantage of a centralized method is obviously
-its high cost in communications needed to transmit to a single node, the base
-station which will globally schedule nodes' activities, data from all the other
-sensor nodes in the area. The price in communications can be very huge since
-long range communications will be needed. In fact the larger the WNS, the higher
-the communication and thus energy cost. {\it In order to be suitable for
- large-scale networks, in the LiCO protocol the area of interest is divided
- into several smaller subregions, and in each one, a node called the leader is
- in charge for selecting the active sensors for the current period. Thus our
- protocol is scalable and a globally distributed method, whereas it is
- centralized in each subregion.}
+its high cost in communications needed to transmit to a single node, the base
+station which will globally schedule nodes' activities, data from all the other
+sensor nodes in the area. The price in communications can be very huge since
+long range communications will be needed. In fact the larger the WNS is, the
+higher the communication and thus the energy cost are. {\it In order to be
+ suitable for large-scale networks, in the LiCO protocol, the area of interest
+ is divided into several smaller subregions, and in each one, a node called the
+ leader is in charge of selecting the active sensors for the current
+ period. Thus our protocol is scalable and is a globally distributed method,
+ whereas it is centralized in each subregion.}
Various coverage scheduling algorithms have been developed this last years.
Many of them, dealing with the maximization of the number of cover sets, are
energy constraints. Column generation techniques, well-known and widely
practiced techniques for solving linear programs with too many variables, have
also been
-used~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In LiCO
+used~\cite{castano2013column,rossi2012exact,deschinkel2012column}. {\it In the LiCO
protocol, each leader, in charge of a subregion, solves an integer program
which has a twofold objective: minimize the overcoverage and the undercoverage
of the perimeter of each sensor.}
