the DiLCO protocol, followed in Section~\ref{cp} by the coverage model
formulation which is used to schedule the activation of
sensors. Section~\ref{sec:Simulation Results and Analysis} shows the simulation
-results. The paper ends with a conclusion and some suggestions for further work
+results. The paper ends with a conclusion and some suggestions for further work
in Section~\ref{sec:Conclusion and Future Works}.
\section{\uppercase{Literature Review}}
\label{sec:Literature Review}
-\noindent In this section, we summarize some related works regarding the coverage
-problem and distinguish our DiLCO protocol from the works presented in the
-literature.
-
-The most discussed coverage problems in literature
-can be classified into three types \cite{li2013survey}: area coverage \cite{Misra} where
-every point inside an area is to be monitored, target coverage \cite{yang2014novel} where the main
-objective is to cover only a finite number of discrete points called targets,
-and barrier coverage \cite{Kumar:2005}\cite{kim2013maximum} to prevent intruders from entering into the region of interest. In \cite{Deng2012} authors transform the area coverage problem to the target coverage problem taking into account the intersection points among disks of sensors nodes or between disk of sensor nodes and boundaries.
-{\it In DiLCO protocol, the area coverage, i.e. the coverage of every point in
- the sensing region, is transformed to the coverage of a fraction of points
- called primary points. }
-
+\noindent In this section, we summarize some related works regarding the
+coverage problem and distinguish our DiLCO protocol from the works presented in
+the literature.
+
+The most discussed coverage problems in literature can be classified into three
+types \cite{li2013survey}: area coverage \cite{Misra} where every point inside
+an area is to be monitored, target coverage \cite{yang2014novel} where the main
+objective is to cover only a finite number of discrete points called targets,
+and barrier coverage \cite{Kumar:2005}\cite{kim2013maximum} to prevent intruders
+from entering into the region of interest. In \cite{Deng2012} authors transform
+the area coverage problem to the target coverage problem taking into account the
+intersection points among disks of sensors nodes or between disk of sensor nodes
+and boundaries. {\it In DiLCO protocol, the area coverage, i.e. the coverage of
+ every point in the sensing region, is transformed to the coverage of a
+ fraction of points called primary points. }
The major approach to extend network lifetime while preserving coverage is to
divide/organize the sensors into a suitable number of set covers (disjoint or
-non-disjoint), where each set completely covers a region of interest, and to
+non-disjoint), where each set completely covers a region of interest, and to
activate these set covers successively. The network activity can be planned in
advance and scheduled for the entire network lifetime or organized in periods,
-and the set of active sensor nodes is decided at the beginning of each period \cite{ling2009energy}.
-Active node selection is determined based on the problem requirements (e.g. area
-monitoring, connectivity, power efficiency). For instance, Jaggi et al. \cite{jaggi2006}
-address the problem of maximizing network lifetime by dividing sensors into the maximum number of disjoint subsets such that each subset can ensure both coverage and connectivity. A greedy algorithm is applied once to solve this problem and the computed sets are activated in succession to achieve the desired network lifetime.
-Vu \cite{chin2007}, Padmatvathy et al. \cite{pc10}, propose algorithms working in a periodic fashion where a cover set is computed at the beginning of each period.
-{\it Motivated by these works, DiLCO protocol works in periods, where each period contains a preliminary
- phase for information exchange and decisions, followed by a sensing phase
- where one cover set is in charge of the sensing task.}
-
-Various approaches, including centralized, or distributed
-algorithms, have been proposed to extend the network lifetime.
-In distributed algorithms~\cite{yangnovel,ChinhVu,qu2013distributed},
-information is disseminated throughout the network and sensors decide
-cooperatively by communicating with their neighbors which of them will remain in
-sleep mode for a certain period of time. The centralized
+and the set of active sensor nodes is decided at the beginning of each period
+\cite{ling2009energy}. Active node selection is determined based on the problem
+requirements (e.g. area monitoring, connectivity, power efficiency). For
+instance, Jaggi et al. \cite{jaggi2006} address the problem of maximizing
+network lifetime by dividing sensors into the maximum number of disjoint subsets
+such that each subset can ensure both coverage and connectivity. A greedy
+algorithm is applied once to solve this problem and the computed sets are
+activated in succession to achieve the desired network lifetime. Vu
+\cite{chin2007}, Padmatvathy et al. \cite{pc10}, propose algorithms working in a
+periodic fashion where a cover set is computed at the beginning of each period.
+{\it Motivated by these works, DiLCO protocol works in periods, where each
+ period contains a preliminary phase for information exchange and decisions,
+ followed by a sensing phase where one cover set is in charge of the sensing
+ task.}
+
+Various approaches, including centralized, or distributed algorithms, have been
+proposed to extend the network lifetime. In distributed
+algorithms~\cite{yangnovel,ChinhVu,qu2013distributed}, information is
+disseminated throughout the network and sensors decide cooperatively by
+communicating with their neighbors which of them will remain in sleep mode for a
+certain period of time. The centralized
algorithms~\cite{cardei2005improving,zorbas2010solving,pujari2011high} always
provide nearly or close to optimal solution since the algorithm has global view
of the whole network. But such a method has the disadvantage of requiring high
communication costs, since the node (located at the base station) making the
-decision needs information from all the sensor nodes in the area and the amount of information can be huge.
-{\it In order to be suitable for large-scale network, in the DiLCO protocol, the area coverage is divided into several smaller
- subregions, and in each one, a node called the leader is in charge for
+decision needs information from all the sensor nodes in the area and the amount
+of information can be huge. {\it In order to be suitable for large-scale
+ network, in the DiLCO protocol, the area coverage 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.}
A large variety of coverage scheduling algorithms has been developed. Many of
the existing algorithms, dealing with the maximization of the number of cover
sets, are heuristics. These heuristics involve the construction of a cover set
by including in priority the sensor nodes which cover critical targets, that is
-to say targets that are covered by the smallest number of sensors \cite{berman04,zorbas2010solving}. Other
-approaches are based on mathematical programming formulations~\cite{cardei2005energy,5714480,pujari2011high,Yang2014} and dedicated
-techniques (solving with a branch-and-bound algorithms available in optimization
-solver). The problem is formulated as an optimization problem (maximization of
-the lifetime or number of cover sets) under target coverage and 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 DiLCO protocol, each leader, in each subregion, solves an integer
- program with a double objective consisting in minimizing the overcoverage and
- limiting the undercoverage. This program is inspired from the work of
- \cite{pedraza2006} where the objective is to maximize the number of cover
- sets.}
-
+to say targets that are covered by the smallest number of sensors
+\cite{berman04,zorbas2010solving}. Other approaches are based on mathematical
+programming formulations~\cite{cardei2005energy,5714480,pujari2011high,Yang2014}
+and dedicated techniques (solving with a branch-and-bound algorithms available
+in optimization solver). The problem is formulated as an optimization problem
+(maximization of the lifetime or number of cover sets) under target coverage and
+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 DiLCO
+ protocol, each leader, in each subregion, solves an integer program with a
+ double objective consisting in minimizing the overcoverage and limiting the
+ undercoverage. This program is inspired from the work of \cite{pedraza2006}
+ where the objective is to maximize the number of cover sets.}
\section{\uppercase{Description of the DiLCO protocol}}
\label{sec:The DiLCO Protocol Description}
preservation and energy conservation, applied periodically to efficiently
maximize the lifetime in the network.
-
\subsection{Assumptions and models}
\noindent We consider a sensor network composed of static nodes distributed
sensing range $R_s$, every space points within a disk centered at a sensor with
the radius of the sensing range is said to be covered by this sensor. We also
assume that the communication range $R_c \geq 2R_s$. In fact, Zhang and
-Zhou~\cite{Zhang05} proved that if the transmission range fulfills the previous
+Hou~\cite{Zhang05} proved that if the transmission range fulfills the previous
hypothesis, a complete coverage of a convex area implies connectivity among the
working nodes in the active mode.
1-bit-content message defined in~\cite{raghunathan2002energy} (we assume
symmetric communication costs), and we set their respective size to 112 and
24~bits. The energy required to send or receive a 1-bit-content message is thus
- equal to 0.2575 mW.
-
-Each node has an initial energy level, in Joules, which is randomly drawn in the
-interval $[500-700]$. If its energy provision reaches a value below the
-threshold $E_{th}=36$~Joules, the minimum energy needed for a node to stay
-active during one period, it will no longer take part in the coverage task. This
-value corresponds to the energy needed by the sensing phase, obtained by
-multiplying the energy consumed in active state (9.72 mW) by the time in seconds
-for one period (3,600 seconds), and adding the energy for the pre-sensing phases.
+ equal to 0.2575~mW.
+
+Each node has an initial energy level, in Joules, which is randomly drawn in
+$[500-700]$. If its energy provision reaches a value below the threshold
+$E_{th}=36$~Joules, the minimum energy needed for a node to stay active during
+one period, it will no longer take part in the coverage task. This value
+corresponds to the energy needed by the sensing phase, obtained by multiplying
+the energy consumed in active state (9.72 mW) by the time in seconds for one
+period (3,600 seconds), and adding the energy for the pre-sensing phases.
According to the interval of initial energy, a sensor may be active during at
most 20 periods.
\times 26 = 1326$ grid points.
\item {{\bf Energy Consumption}:} energy consumption (EC) can be seen as the
- total amount of energy consumed by the sensors during $Lifetime_{95}$ or
- $Lifetime_{50}$, divided by the number of periods. Formally, the computation
+ total amount of energy consumed by the sensors during $Lifetime_{95}$
+ or $Lifetime_{50}$, divided by the number of periods. Formally, the computation
of EC can be expressed as follows:
\begin{equation*}
\scriptsize
+ E^{a}_m+E^{s}_m \right)}{M},
\end{equation*}
-where $M$ corresponds to the number of periods. The total amount of energy consumed by
-the sensors (EC) comes through taking into consideration four main energy
-factors. The first one, denoted $E^{\scriptsize \mbox{com}}_m$, represents the
-energy consumption spent by all the nodes for wireless communications during
-period $m$. $E^{\scriptsize \mbox{list}}_m$, the next factor, corresponds to
-the energy consumed by the sensors in LISTENING status before receiving the
-decision to go active or sleep in period $m$. $E^{\scriptsize \mbox{comp}}_m$
-refers to the energy needed by all the leader nodes to solve the integer program
-during a period. Finally, $E^a_{m}$ and $E^s_{m}$ indicate the energy consumed
-by the whole network in the sensing phase (active and sleeping nodes).
-
+where $M$ corresponds to the number of periods. The total amount of energy
+consumed by the sensors (EC) comes through taking into consideration four main
+energy factors. The first one, denoted $E^{\scriptsize \mbox{com}}_m$,
+represents the energy consumption spent by all the nodes for wireless
+communications during period $m$. $E^{\scriptsize \mbox{list}}_m$, the next
+factor, corresponds to the energy consumed by the sensors in LISTENING status
+before receiving the decision to go active or sleep in period $m$.
+$E^{\scriptsize \mbox{comp}}_m$ refers to the energy needed by all the leader
+nodes to solve the integer program during a period. Finally, $E^a_{m}$ and
+$E^s_{m}$ indicate the energy consumed by the whole network in the sensing phase
+(active and sleeping nodes).
\end{itemize}
%\end{enumerate}
-
%\subsection{Performance Analysis for different subregions}
\subsection{Performance analysis}
\label{sub1}
\subsubsection{Coverage ratio}
Figure~\ref{fig3} shows the average coverage ratio for 150 deployed nodes. It
-can be seen that both DESK and GAF provide a coverage ratio which is slightly better
-compared to DiLCO in the first thirty periods. This can be easily explained by
-the number of active nodes: the optimization process of our protocol activates
-less nodes than DESK or GAF, resulting in a slight decrease of the coverage
-ratio. In case of DiLCO-2 (respectively DiLCO-4), the coverage ratio exhibits a
-fast decrease with the number of periods and reaches zero value in period~18
-(respectively 46), whereas the other versions of DiLCO, DESK, and GAF ensure a
-coverage ratio above 50\% for subsequent periods. We believe that the results
-obtained with these two methods can be explained by a high consumption of energy
-and we will check this assumption in the next subsection.
+can be seen that both DESK and GAF provide a coverage ratio which is slightly
+better compared to DiLCO in the first thirty periods. This can be easily
+explained by the number of active nodes: the optimization process of our
+protocol activates less nodes than DESK or GAF, resulting in a slight decrease
+of the coverage ratio. In case of DiLCO-2 (respectively DiLCO-4), the coverage
+ratio exhibits a fast decrease with the number of periods and reaches zero value
+in period~18 (respectively 46), whereas the other versions of DiLCO, DESK, and
+GAF ensure a coverage ratio above 50\% for subsequent periods. We believe that
+the results obtained with these two methods can be explained by a high
+consumption of energy and we will check this assumption in the next subsection.
Concerning DiLCO-8, DiLCO-16, and DiLCO-32, these methods seem to be more
efficient than DESK and GAF, since they can provide the same level of coverage
protocol. Indeed, the protocols DiLCO-16/50, DiLCO-32/50, DiLCO-16/95, and
DiLCO-32/95 consume less energy than their DESK and GAF counterparts for a
similar level of area coverage. This observation reflects the larger number of
-nodes set active by DESK and GAF.
+nodes set active by DESK and GAF. Now, if we consider a same protocol, we can
+notice that the average consumption per period increases slightly for our
+protocol when increasing the level of coverage, whereas it increases more
+largely for DESK and GAF. In case of DiLCO It means that even if a larger
+network allows to improve the number of periods with a minimum coverage level
+value, this improvement has a higher energy cost per period due to
+communications and a more difficult optimization. However, in comparison with
+DSK and GAF, our approach has a reasonable energy overhead.
\subsubsection{Execution time}
