\usepackage{apalike}
\usepackage{SCITEPRESS}
\usepackage[small]{caption}
-
+\usepackage{color}
\usepackage[linesnumbered,ruled,vlined,commentsnumbered]{algorithm2e}
\usepackage{mathtools}
scheduling performed by each elected leader. This two-step process takes
place periodically, in order to choose a small set of nodes remaining active
for sensing during a time slot. Each set is built to ensure coverage at a low
- energy cost, allowing to optimize the network lifetime. More precisely, a
- period consists of four phases: (i)~Information Exchange, (ii)~Leader
- Election, (iii)~Decision, and (iv)~Sensing. The decision process, which
+ energy cost, allowing to optimize the network lifetime.
+ %More precisely, a
+ %period consists of four phases: (i)~Information Exchange, (ii)~Leader
+ %Election, (iii)~Decision, and (iv)~Sensing.
+ The decision process, which
results in an activity scheduling vector, is carried out by a leader node
- through the solving of an integer program. In comparison with some other
- protocols, the simulations done using the discrete event simulator OMNeT++
- show that our approach is able to increase the WSN lifetime and provides
- improved coverage performance. }
+ through the solving of an integer program.
+ {\color{red} Simulations are conducted using the discret event simulator OMNET++.
+ We refer to the characterictics of a Medusa II sensor for the energy consumption and the time computation.
+ In comparison with two other existing methods, our approach is able to increase the WSN lifetime and provides
+ improved coverage performance. }}
+
\onecolumn \maketitle \normalsize \vfill
leader) to carry out the coverage strategy. In each subregion the activation of
the sensors for the sensing phase of the current period is obtained by solving
an integer program. The resulting activation vector is broadcast by a leader
-to every node of its subregion.
+to every node of its subregion.
+
+{\color{red} Our previous paper ~\cite{idrees2014coverage} relies almost exclusively on the framework of the DiLCO approach and the coverage problem formulation.
+In this paper we strengthen our simulations by taking into account the characteristics of a Medusa II sensor ~\cite{raghunathan2002energy} to measure the energy consumption and the computation time.
+We have implemented two other existing approaches (a distributed one DESK ~\cite{ChinhVu} and a centralized one GAF ~\cite{xu2001geography}) in order to compare their performances with our approach.
+We also focus on performance analysis based on the number of subregions. }
+
The remainder of the paper continues with Section~\ref{sec:Literature Review}
where a review of some related works is presented. The next section describes
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.
-%For instance, in order to hide the occurrence of faults, or the sudden unavailability of
-%sensor nodes, some distributed algorithms have been developed in~\cite{Gallais06,Tian02,Ye03,Zhang05,HeinzelmanCB02}.
-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.
\subsection{Main idea}
\label{main_idea}
-
\noindent We start by applying a divide-and-conquer algorithm to partition the
area of interest into smaller areas called subregions and then our protocol is
executed simultaneously in each subregion.
Active-Sleep packet to know its state for the coming sensing phase.
-
-
-
\begin{algorithm}[h!]
\BlankLine
\section{\uppercase{Coverage problem formulation}}
\label{cp}
+{\color{red}
+We formulate the coverage optimization problem with an integer program.
+The objective function consists in minimizing the undercoverage and the overcoverage of the area as suggested in \cite{pedraza2006}.
+The area coverage problem is transformed to the coverage of a fraction of points called primary points.
+Details on the choice and the number of primary points can be found in \cite{idrees2014coverage}. The set of primary points is denoted by $P$
+and the set of sensors by $J$. As we consider a boolean disk coverage model, we use the boolean indicator $\alpha_{jp}$ which is equal to 1 if the primary point $p$ is in the sensing range of the sensor $j$. The binary variable $X_j$ represents the activation or not of the sensor $j$. So we can express the number of active sensors that cover the primary point $p$ by $\sum_{j \in J} \alpha_{jp} * X_{j}$. We deduce the overcoverage denoted by $\Theta_p$ of the primary point $p$ :
+\begin{equation}
+ \Theta_{p} = \left \{
+\begin{array}{l l}
+ 0 & \mbox{if the primary point}\\
+ & \mbox{$p$ is not covered,}\\
+ \left( \sum_{j \in J} \alpha_{jp} * X_{j} \right)- 1 & \mbox{otherwise.}\\
+\end{array} \right.
+\label{eq13}
+\end{equation}
+More precisely, $\Theta_{p}$ represents the number of active sensor
+nodes minus one that cover the primary point~$p$.
+In the same way, we define the undercoverage variable
+$U_{p}$ of the primary point $p$ as:
+\begin{equation}
+U_{p} = \left \{
+\begin{array}{l l}
+ 1 &\mbox{if the primary point $p$ is not covered,} \\
+ 0 & \mbox{otherwise.}\\
+\end{array} \right.
+\label{eq14}
+\end{equation}
+There is, of course, a relationship between the three variables $X_j$, $\Theta_p$ and $U_p$ which can be formulated as follows :
+\begin{equation}
+\sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, \forall p \in P
+\end{equation}
+If the point $p$ is not covered, $U_p=1$, $\sum_{j \in J} \alpha_{jp} X_{j}=0$ and $\Theta_{p}=0$ by defintion, so the equality is satisfied.
+On the contrary, if the point $p$ is covered, $U_p=0$, and $\Theta_{p}=\left( \sum_{j \in J} \alpha_{jp} X_{j} \right)- 1$.
+\noindent Our coverage optimization problem can then be formulated as follows:
+\begin{equation} \label{eq:ip2r}
+\left \{
+\begin{array}{ll}
+\min \sum_{p \in P} (w_{\theta} \Theta_{p} + w_{U} U_{p})&\\
+\textrm{subject to :}&\\
+\sum_{j \in J} \alpha_{jp} X_{j} - \Theta_{p}+ U_{p} =1, &\forall p \in P\\
+%\label{c1}
+%\sum_{t \in T} X_{j,t} \leq \frac{RE_j}{e_t} &\forall j \in J \\
+%\label{c2}
+\Theta_{p}\in \mathbb{N}, &\forall p \in P\\
+U_{p} \in \{0,1\}, &\forall p \in P \\
+X_{j} \in \{0,1\}, &\forall j \in J
+\end{array}
+\right.
+\end{equation}
+The objective function is a weighted sum of overcoverage and undercoverage. The goal is to limit the overcoverage in order to activate a minimal number of sensors while simultaneously preventing undercoverage. Both weights $w_\theta$ and $w_U$ must be carefully chosen in
+order to guarantee that the maximum number of points are covered during each
+period.
+}
+
+
+
+
+
+
+
+\iffalse
+
\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, the authors proposed an integer program which forces undercoverage
order to guarantee that the maximum number of points are covered during each
period.
+\fi
+
\section{\uppercase{Protocol evaluation}}
\label{sec:Simulation Results and Analysis}
\noindent \subsection{Simulation framework}
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.
connectivity is crucial because an active sensor node without connectivity
towards a base station cannot transmit any information regarding an observed
event in the area that it monitors.
-
-
+
\item {{\bf Coverage Ratio (CR)}:} it measures how well the WSN is able to
observe the area of interest. In our case, we discretized the sensor field
as a regular grid, which yields the following equation to compute the
subregions during the current sensing phase and $N$ is the total number of grid
points in the sensing field. In our simulations, we have a layout of $N = 51
\times 26 = 1326$ grid points.
-%The accuracy of this method depends on the distance between grids. In our
-%simulations, the sensing field has been divided into 50 by 25 grid points, which means
-%there are $51 \times 26~ = ~ 1326$ points in total.
-% Therefore, for our simulations, the error in the coverage calculation is less than ~ 1 $\% $.
-
-
\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
\begin{figure}[h!]
\centering
\includegraphics[scale=0.45]{R/EC.pdf}
-\caption{Energy consumption}
+\caption{Energy consumption per period}
\label{fig95}
\end{figure}
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.
-%In fact, a distributed method on the subregions greatly reduces the number of communications and the time of listening so thanks to the partitioning of the initial network into several independent subnetworks.
-%As shown in Figures~\ref{fig95} and ~\ref{fig50} , DiLCO-2 consumes more energy than the other versions of DiLCO, especially for large sizes of network. This is easy to understand since the bigger the number of sensors involved in the integer program, the larger the time computation to solve the optimization problem as well as the higher energy consumed during the communication.
+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 and the number of node, 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 communication overhead and a more
+difficult optimization problem. However, in comparison with DESK and GAF, our
+approach has a reasonable energy overcost.
\subsubsection{Execution time}
subregions. Thus, the optimal number of subregions can be seen as a trade-off
between execution time and coverage performance.
-%The DiLCO-32 has more suitable times in the same time it turn on redundent nodes more. We think that in distributed fashion the solving of the optimization problem in a subregion can be tackled by sensor nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required.
-
\subsubsection{Network lifetime}
In the next figure, the network lifetime is illustrated. Obviously, the lifetime
in $16$~subregions seems to be the most appropriate.
-
\section{\uppercase{Conclusion and future work}}
\label{sec:Conclusion and Future Works}
context a subdivision in $16$~subregions seems to be the most relevant. The
optimal number of subregions will be investigated in the future.
-
-
\section*{\uppercase{Acknowledgements}}
\noindent As a Ph.D. student, Ali Kadhum IDREES would like to gratefully
