%\articletype{GUIDE}
-\title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime \\
- in Wireless Sensor Networks}}
-
-\author{Ali Kadhum Idrees$^{a, b}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$ and Rapha\"el Couturier $^{a}$
-$^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, University of Franche-Comt\'e,
- Belfort, France}}
-$^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}} }
-
-
-
+\title{{\itshape Perimeter-based Coverage Optimization \\
+ to Improve Lifetime in Wireless Sensor Networks}}
+
+\author{Ali Kadhum Idrees$^{a,b}$, Karine Deschinkel$^{a}$$^{\ast}$\thanks{$^\ast$Corresponding author. Email: karine.deschinkel@univ-fcomte.fr}, Michel Salomon$^{a}$ and Rapha\"el Couturier $^{a}$
+ $^{a}${\em{FEMTO-ST Institute, UMR 6174 CNRS, \\
+ University Bourgogne Franche-Comt\'e, Belfort, France}} \\
+ $^{b}${\em{Department of Computer Science, University of Babylon, Babylon, Iraq}}
+}
+
\maketitle
\begin{abstract}
A WSN consisting of $J$ stationary sensor nodes randomly and uniformly
distributed in a bounded sensor field is considered. The wireless sensors are
deployed in high density to ensure initially a high coverage ratio of the area
-of interest. We assume that all the sensor nodes are homogeneous in terms of
+of interest. All the sensor nodes are supposed to be homogeneous in terms of
communication, sensing, and processing capabilities and heterogeneous from the
energy provision point of view. The location information is available to a
sensor node either through hardware such as embedded GPS or location discovery
-algorithms. We consider a Boolean disk coverage model, which is the most widely
-used sensor coverage model in the literature, and all sensor nodes have a
+algorithms. A Boolean disk coverage model, which is the most widely used sensor
+coverage model in the literature, is considered and all sensor nodes have a
constant sensing range $R_s$. Thus, all the space points within a disk centered
at a sensor with a radius equal to the sensing range are said to be covered by
-this sensor. We also assume that the communication range $R_c$ satisfies $R_c
-\geq 2 \cdot R_s$. In fact, \citet{Zhang05} proved that if the transmission
+this sensor. We also assume that the communication range $R_c$ satisfies $R_c
+\geq 2 \cdot R_s$. In fact, \citet{Zhang05} proved that if the transmission
range fulfills the previous hypothesis, the complete coverage of a convex area
implies connectivity among active nodes.
%\newpage
\begin{figure}[h!]
\centering
-\includegraphics[width=62.5mm]{figure3.eps}
+\includegraphics[width=57.5mm]{figure3.eps}
\caption{Sensing range outside the WSN's area of interest.}
\label{figure3}
\end{figure}
The WSN area of interest is, in a first step, divided into regular homogeneous
subregions using a divide-and-conquer algorithm. In a second step our protocol
will be executed in a distributed way in each subregion simultaneously to
-schedule nodes' activities for one sensing period. Node Sensors are assumed to
+schedule nodes' activities for one sensing period. Sensor nodes are assumed to
be deployed almost uniformly over the region. The regular subdivision is made
such that the number of hops between any pairs of sensors inside a subregion is
less than or equal to 3.
\begin{figure}[t!]
\centering
-\includegraphics[width=85mm]{figure4.eps}
+\includegraphics[width=80mm]{figure4.eps}
\caption{PeCO protocol.}
\label{figure4}
\end{figure}
sensor~$j$.
\end{itemize}
$I_j$ refers to the set of coverage intervals which have been defined according
-to the method introduced in subsection~\ref{CI}. For a coverage interval $i$,
+to the method introduced in Subsection~\ref{CI}. For a coverage interval $i$,
let $a^j_{ik}$ denote the indicator function of whether sensor~$k$ is involved
in coverage interval~$i$ of sensor~$j$, that is:
\begin{equation}
obtained by multiplying the energy consumed in the active state (9.72 mW) with
the time in seconds for one period (3600 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.
+be active during at most 20 periods. Information exchange to update the coverage
+is executed every hour, but the length of the sensing period could be reduced
+and adapted dynamically. On the one hand a small sensing period would allow to
+be more reliable but would have result in higher communication costs. On the
+other hand the choice of a long duration may cause problems in case of nodes
+failure during the sensing period.
The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good
network coverage and a longer WSN lifetime. Higher priority is given to the
microcontroller (6~MHz) having a MIPS rate equal to 6, the original execution
time on the laptop is multiplied by 2944.2 $\left(\frac{35330}{2} \times
\frac{1}{6} \right)$. Energy consumption is calculated according to the power
-consumption values, in milliWatt per second, given in Table~\ref{tab:EC}
+consumption values, in milliWatt per second, given in Table~\ref{tab:EC}.
based on the energy model proposed in \citep{ChinhVu}.
-% Questions on energy consumption calculation
-% 1 - How did you compute the value for COMPUTATION status ?
-% 2 - I have checked the paper of Chinh T. Vu (2006) and I wonder
-% why you completely deleted the energy due to the sensing range ?
-% => You should have use a fixed value for the sensing rangge Rs (5 meter)
-% => for all the nodes to compute f(Ri), which would have lead to energy values
-
\begin{table}[h]
\centering
-\caption{Energy consumption}
+\caption{Power consumption values}
\label{tab:EC}
\begin{tabular}{|l||cccc|}
\hline
- {\bf Sensor status} & MCU & Radio & Sensor & {\it Power (mW)} \\
+ {\bf Sensor status} & MCU & Radio & Sensing & {\it Power (mW)} \\
\hline
LISTENING & On & On & On & 20.05 \\
ACTIVE & On & Off & On & 9.72 \\
The modeling language for Mathematical Programming (AMPL)~\citep{AMPL} is used
to generate the integer program instance in a standard format, which is then
read and solved by the optimization solver GLPK (GNU linear Programming Kit
-available in the public domain) \citep{glpk} through a Branch-and-Bound method.
-
-% No discussion about the execution of GLPK on a sensor ?
+available in the public domain) \citep{glpk} through a Branch-and-Bound method.
+In practice, executing GLPK on a sensor node is obviously intractable due to the
+huge memory use. Fortunately, to solve the optimization problem we could use
+commercial solvers like CPLEX \citep{iamigo:cplex} which are less memory
+consuming and more efficient, or implement a lightweight heuristic. For example,
+for a WSN of 200 sensor nodes, a leader node has to deal with constraints
+induced by about 12 sensor nodes. In that case, to solve the optimization
+problem a memory consumption of more than 1~MB can be observed with GLPK,
+whereas less than 300~kB would be needed with CPLEX.
Besides PeCO, three other protocols will be evaluated for comparison
purposes. The first one, called DESK, is a fully distributed coverage algorithm
in~\citep{idrees2014coverage}. Let us notice that PeCO and DiLCO protocols are
based on the same framework. In particular, the choice for the simulations of a
partitioning in 16~subregions was made because it corresponds to the
-configuration producing the best results for DiLCO. The protocols are
-distinguished from one another by the formulation of the integer program
-providing the set of sensors which have to be activated in each sensing
-phase. DiLCO protocol tries to satisfy the coverage of a set of primary points,
-whereas PeCO protocol objective is to reach a desired level of coverage for each
-sensor perimeter. In our experimentations, we chose a level of coverage equal to
-one ($l=1$).
+configuration producing the best results for DiLCO. Of course, this number of
+subregions should be adapted according to the size of the area of interest and
+the number of sensors. The protocols are distinguished from one another by the
+formulation of the integer program providing the set of sensors which have to be
+activated in each sensing phase. DiLCO protocol tries to satisfy the coverage of
+a set of primary points, whereas PeCO protocol objective is to reach a desired
+level of coverage for each sensor perimeter. In our experimentations, we chose a
+level of coverage equal to one ($l=1$).
\subsubsection{Coverage Ratio}
obtained with the four protocols. DESK, GAF, and DiLCO provide a slightly better
coverage ratio with respectively 99.99\%, 99.91\%, and 99.02\%, compared to the
98.76\% produced by PeCO for the first periods. This is due to the fact that at
-the beginning PeCO protocol puts to sleep status more redundant sensors (which
-slightly decreases the coverage ratio), while the three other protocols activate
-more sensor nodes. Later, when the number of periods is beyond~70, it clearly
-appears that PeCO provides a better coverage ratio and keeps a coverage ratio
-greater than 50\% for longer periods (15 more compared to DiLCO, 40 more
-compared to DESK). The energy saved by PeCO in the early periods allows later a
-substantial increase of the coverage performance.
+the beginning DiLCO and PeCO protocols put to sleep status more redundant
+sensors (which slightly decreases the coverage ratio), while the two other
+protocols activate more sensor nodes. Later, when the number of periods is
+beyond~70, it clearly appears that PeCO provides a better coverage ratio and
+keeps a coverage ratio greater than 50\% for longer periods (15 more compared to
+DiLCO, 40 more compared to DESK). The energy saved by PeCO in the early periods
+allows later a substantial increase of the coverage performance.
\parskip 0pt
\begin{figure}[h!]
sensor-testbed to evaluate it in real world applications.
-\subsection{Acknowledgements}
-The authors are deeply grateful to the anonymous reviewers for their constructive advice, which improved the technical quality of the paper. As a Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the University of Babylon - Iraq for financial support and Campus France for the received support. This work is also partially funded by the Labex ACTION program (contract ANR-11-LABX-01-01).
+\subsection*{Acknowledgements}
+The authors are deeply grateful to the anonymous reviewers for their
+constructive advice, which improved the technical quality of the paper. As a
+Ph.D. student, Ali Kadhum IDREES would like to gratefully acknowledge the
+University of Babylon - Iraq for financial support and Campus France for the
+received support. This work is also partially funded by the Labex ACTION program
+(contract ANR-11-LABX-01-01).
\bibliographystyle{gENO}
\bibliography{biblio} %articleeo
