Updates completed

[LiCO.git] / PeCO-EO / articleeo.tex

diff --git a/PeCO-EO/articleeo.tex b/PeCO-EO/articleeo.tex
index b4925dbaa27323631f29c2c2f016d0f8f6db48a5..e98acfca079149e27934c481923585effe40ec06 100644 (file)
--- a/PeCO-EO/articleeo.tex
+++ b/PeCO-EO/articleeo.tex
@@ -12,13 +12,15 @@
 
 %\articletype{GUIDE}
 
 
 %\articletype{GUIDE}
 

-\title{{\itshape Perimeter-based Coverage Optimization to Improve Lifetime \\
-    in Wireless Sensor Networks}}
-
-\author{Ali Kadhum Idrees$^{a}$, 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}}}
-
+\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}
 \maketitle
 
 \begin{abstract}


@@ -231,16 +233,16 @@ and provides  improved coverage performance.  {\it  In the PeCO protocol,  a new
 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
 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
 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
 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.
 
 range fulfills the  previous hypothesis, the complete coverage of  a convex area
 implies connectivity among active nodes.
 


@@ -351,7 +353,7 @@ optimization algorithm.
 %\newpage
 \begin{figure}[h!]
 \centering
 %\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}
 \caption{Sensing range outside the WSN's area of interest.}
 \label{figure3}
 \end{figure}


@@ -363,7 +365,7 @@ optimization algorithm.
 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
 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.
 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.


@@ -389,7 +391,7 @@ of the application.
 
 \begin{figure}[t!]
 \centering
 
 \begin{figure}[t!]
 \centering

-\includegraphics[width=85mm]{figure4.eps}  
+\includegraphics[width=80mm]{figure4.eps}  

 \caption{PeCO protocol.}
 \label{figure4}
 \end{figure} 
 \caption{PeCO protocol.}
 \label{figure4}
 \end{figure} 


@@ -535,7 +537,7 @@ First, the following sets:
   sensor~$j$.
 \end{itemize}
 $I_j$ refers to the set of  coverage intervals which have been defined according
   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}
 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}


@@ -665,7 +667,12 @@ coverage task. This value corresponds to the energy needed by the sensing phase,
 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
 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
 
 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


@@ -741,19 +748,12 @@ be consistent  with the  use of  a sensor  node based  on Atmels  AVR ATmega103L
 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
 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}.
 
 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
 \begin{table}[h]
 \centering

-\caption{Energy consumption}
+\caption{Power consumption values}

 \label{tab:EC}
 \begin{tabular}{|l||cccc|}
   \hline
 \label{tab:EC}
 \begin{tabular}{|l||cccc|}
   \hline


@@ -772,9 +772,15 @@ based on the energy model proposed in \citep{ChinhVu}.
 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
 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
 
 Besides  PeCO,   three  other  protocols   will  be  evaluated   for  comparison
 purposes. The first one, called DESK,  is a fully distributed coverage algorithm


@@ -786,13 +792,14 @@ protocol~\citep{Idrees2}, is an improved version of a research work we presented
 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
 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}
 
 
 \subsubsection{Coverage Ratio}
 


@@ -800,13 +807,13 @@ Figure~\ref{figure5} shows  the average  coverage ratio  for 200  deployed nodes
 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
 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!]
 
 \parskip 0pt    
 \begin{figure}[h!]


@@ -969,6 +976,15 @@ account heterogeneous sensors from both energy and node characteristics point of
 views.  Finally,  it would  be interesting  to implement  PeCO protocol  using a
 sensor-testbed to evaluate it in real world applications.
 
 views.  Finally,  it would  be interesting  to implement  PeCO protocol  using a
 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).
+

 \bibliographystyle{gENO}
 \bibliography{biblio} %articleeo
 
 \bibliographystyle{gENO}
 \bibliography{biblio} %articleeo