no more color

[JournalMultiPeriods.git] / article.tex

diff --git a/article.tex b/article.tex
index cd6a361dbcd853f68b6525ea50306275fcccc186..ed70b52271030df1fe6c5ade3585031169ab22c7 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -149,10 +149,10 @@ in~\cite{idrees2015distributed}.
 %more  interesting  to  divide  the  area  into  several  subregions,  given  the
 %computation complexity.
 
 %more  interesting  to  divide  the  area  into  several  subregions,  given  the
 %computation complexity.
 

-\textcolor{blue}{ Compared  to our  previous paper~\cite{idrees2015distributed},
-  in  this one  we study  the  possibility of  dividing the  sensing phase  into
-  multiple rounds.   In fact, in this  paper we make a  multiround optimization,
-  while it was a single round optimization in our previous work.  The idea is to
+\textcolor{black}{ Compared  to our  previous work~\cite{idrees2015distributed},
+  in  this paper  we study  the  possibility of  dividing the  sensing phase  into
+  multiple rounds.   We make a  multiround optimization,
+  while previously it was a single round optimization.  The idea is to

   take advantage  of the  pre-sensing phase  to plan  the sensor's  activity for
   several  rounds instead  of one,  thus saving  energy. In  addition, when  the
   optimization problem becomes  more complex, its resolution is  stopped after a
   take advantage  of the  pre-sensing phase  to plan  the sensor's  activity for
   several  rounds instead  of one,  thus saving  energy. In  addition, when  the
   optimization problem becomes  more complex, its resolution is  stopped after a


@@ -291,34 +291,13 @@ Indeed, each sensor  maintains its own timer and its  wake-up time is randomized
 \subsection{Assumptions and primary points}
 \label{pp}
 
 \subsection{Assumptions and primary points}
 \label{pp}
 

-\textcolor{blue}{Assumptions and coverage model are identical to those presented
-  in~\cite{idrees2015distributed}.}
-
-\iffalse
-We  consider a  randomly and  uniformly  deployed network  consisting of  static
-wireless sensors.  The sensors are  deployed in high density to ensure initially
-a high  coverage ratio  of the interested  area.  We  assume that all  nodes are
-homogeneous  in   terms  of  communication  and   processing  capabilities,  and
-heterogeneous  from the  point  of view  of  energy provision.   Each sensor  is
-supposed  to get information  on its  location either  through hardware  such as
-embedded GPS or through location discovery algorithms.
-   
-To model  a sensor node's coverage  area, we consider the  boolean disk coverage
-model   which  is  the   most  widely   used  sensor   coverage  model   in  the
-literature. Thus, each  sensor has a constant sensing range  $R_s$ and all space
-points within  the disk centered  at the sensor  with the radius of  the sensing
-range  is  said  to  be  covered  by  this sensor.   We  also  assume  that  the
-communication   range  satisfies   $R_c  \geq   2R_s$.   In   fact,   Zhang  and
-Zhou~\cite{Zhang05} proved that if  the transmission range fulfills the previous
-hypothesis, a complete coverage of  a convex area implies connectivity among the
-active nodes.\fi
-
-\textcolor{blue}{We  consider a  scenario where  sensors are  deployed in  high
-  density to ensure initially a high coverage ratio of the interested area. Each
+\textcolor{black}{The assumptions and the coverage model are identical to those presented
+  in~\cite{idrees2015distributed}. We  consider a  scenario in which  sensors are  deployed in  high
+  density to  initially ensure a high coverage ratio of the interested area. Each

   sensor  has  a  predefined  sensing  range $R_s$,  an  initial  energy  supply
   (eventually different  from each other)  and is  supposed to be  equipped with
   sensor  has  a  predefined  sensing  range $R_s$,  an  initial  energy  supply
   (eventually different  from each other)  and is  supposed to be  equipped with

-  module for  locating its geographical  positions. All space points  within the
-  disk centered at the sensor with the radius of the sensing range is said to be
+  a module to  locate its geographical  positions. All space points  within the
+  disk centered at the sensor with the radius of the sensing range are said to be

   covered by this sensor.}
 
 \indent Instead of working with the coverage area, we consider for each sensor a
   covered by this sensor.}
 
 \indent Instead of working with the coverage area, we consider for each sensor a


@@ -377,14 +356,14 @@ inside a subregion is less than or equal to 3.
 
 As can  be seen  in Figure~\ref{fig2},  our protocol  works in  periods fashion,
 where   each   period   is    divided   into   4~phases:   Information~Exchange,
 
 As can  be seen  in Figure~\ref{fig2},  our protocol  works in  periods fashion,
 where   each   period   is    divided   into   4~phases:   Information~Exchange,

-Leader~Election,  Decision, and  Sensing. \textcolor{blue}{Compared  to protocol
-  DiLCO described in~\cite{idrees2015distributed},} each sensing phase is itself
+Leader~Election,  Decision, and  Sensing. \textcolor{black}{Compared  to 
+ the DiLCO protocol described in~\cite{idrees2015distributed},} each sensing phase is itself

 divided into $T$ rounds of equal duration and for each round a set of sensors (a
 cover  set) is  responsible  for the  sensing  task. In  this  way a  multiround
 optimization process is performed  during each period after Information~Exchange
 and Leader~Election  phases, in order to  produce $T$ cover sets  that will take
 the           mission           of           sensing           for           $T$
 divided into $T$ rounds of equal duration and for each round a set of sensors (a
 cover  set) is  responsible  for the  sensing  task. In  this  way a  multiround
 optimization process is performed  during each period after Information~Exchange
 and Leader~Election  phases, in order to  produce $T$ cover sets  that will take
 the           mission           of           sensing           for           $T$

-rounds. \textcolor{blue}{Algorithm~\ref{alg:MuDiLCO} is  executed by each sensor
+rounds. \textcolor{black}{Algorithm~\ref{alg:MuDiLCO} is  executed by each sensor

   node~$s_j$ (with enough remaining energy) at the beginning of a period.}
 \begin{figure}[t!]
 \centering \includegraphics[width=125mm]{Modelgeneral.pdf} % 70mm
   node~$s_j$ (with enough remaining energy) at the beginning of a period.}
 \begin{figure}[t!]
 \centering \includegraphics[width=125mm]{Modelgeneral.pdf} % 70mm


@@ -421,7 +400,7 @@ rounds. \textcolor{blue}{Algorithm~\ref{alg:MuDiLCO} is  executed by each sensor
 \label{alg:MuDiLCO}
 \end{algorithm}
 
 \label{alg:MuDiLCO}
 \end{algorithm}
 

-\textcolor{blue}{As  already   described  in~\cite{idrees2015distributed}},  two
+\textcolor{black}{As  already   described  in~\cite{idrees2015distributed}},  two

 types of packets are used by the proposed protocol:
 \begin{enumerate}[(a)] 
 \item INFO  packet: such a packet  will be sent by  each sensor node to  all the
 types of packets are used by the proposed protocol:
 \begin{enumerate}[(a)] 
 \item INFO  packet: such a packet  will be sent by  each sensor node to  all the


@@ -503,8 +482,8 @@ determine the possibility  of activating sensor $j$ during round  $t$ of a given
 sensing phase.  We also consider primary  points as targets.  The set of primary
 points is denoted by $P$ and the set  of sensors by $J$. Only sensors able to be
 alive  during  at  least  one  round   are  involved  in  the  integer  program.
 sensing phase.  We also consider primary  points as targets.  The set of primary
 points is denoted by $P$ and the set  of sensors by $J$. Only sensors able to be
 alive  during  at  least  one  round   are  involved  in  the  integer  program.

-\textcolor{blue}{Note that the proposed integer  program is an extension of that
-  formulated  in~\cite{idrees2015distributed},  variables  are  now  indexed  in
+\textcolor{black}{Note that the proposed integer  program is an
+  extension of the one   formulated  in~\cite{idrees2015distributed},  variables  are  now  indexed  in

   addition with the number of round $t$.}
 
 For a  primary point  $p$, let $\alpha_{j,p}$  denote the indicator  function of
   addition with the number of round $t$.}
 
 For a  primary point  $p$, let $\alpha_{j,p}$  denote the indicator  function of


@@ -611,15 +590,6 @@ integer program contains  $A*T$ variables of type  $X_{t,j}$, $P*T$ overcoverage
 variables and $P*T$ undercoverage variables.  The number of constraints is equal
 to $P*T$ (for constraints (\ref{eq16})) $+$ $A$ (for constraints (\ref{eq144})).
 
 variables and $P*T$ undercoverage variables.  The number of constraints is equal
 to $P*T$ (for constraints (\ref{eq16})) $+$ $A$ (for constraints (\ref{eq144})).
 

-\iffalse
-\subsection{Sensing phase}
-
-The sensing phase consists of $T$ rounds. Each sensor node in the subregion will
-receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to
-sleep for each  round of the sensing  phase.  Algorithm~\ref{alg:MuDiLCO}, which
-will  be executed  by  each sensor  node~$s_j$  at the  beginning  of a  period,
-explains how the Active-Sleep packet is obtained.
-\fi

 
 \section{Experimental framework}
 \label{exp}
 
 \section{Experimental framework}
 \label{exp}


@@ -687,79 +657,19 @@ lifetime. Moreover,  it makes  the MuDiLCO protocol  more robust  against random
 network  disconnection due  to node  failures.  However,  too many  subdivisions
 reduce the advantage  of the optimization.  In fact, there  is a balance between
 the benefit from the optimization and the  execution time needed to solve it. In
 network  disconnection due  to node  failures.  However,  too many  subdivisions
 reduce the advantage  of the optimization.  In fact, there  is a balance between
 the benefit from the optimization and the  execution time needed to solve it. In

-the following  we have  set the number  of subregions  to~16 \textcolor{blue}{as
+the following  we have  set the number  of subregions  to~16 \textcolor{black}{as

   recommended in~\cite{idrees2015distributed}}.
 
 \subsection{Energy model}
   recommended in~\cite{idrees2015distributed}}.
 
 \subsection{Energy model}

-\textcolor{blue}{The      energy     consumption      model     is      detailed
+\textcolor{black}{The      energy     consumption      model     is      detailed

   in~\cite{raghunathan2002energy}.   It  is   based   on   the  model   proposed
   by~\cite{ChinhVu}. We refer to the sensor  node Medusa~II which uses an Atmels
   AVR ATmega103L  microcontroller~\cite{raghunathan2002energy} to  use numerical
   in~\cite{raghunathan2002energy}.   It  is   based   on   the  model   proposed
   by~\cite{ChinhVu}. We refer to the sensor  node Medusa~II which uses an Atmels
   AVR ATmega103L  microcontroller~\cite{raghunathan2002energy} to  use numerical

-  values.}   \textcolor{red}{Est-ce qu'il  faut en  ecrire plus  et redonner  le
-  tableau de valeurs?}
-
-\iffalse
-\subsection{Energy model}
-
-We  use an  energy consumption  model  proposed by~\cite{ChinhVu}  and based  on
-\cite{raghunathan2002energy} with slight  modifications.  The energy consumption
-for  sending/receiving the packets  is added,  whereas the  part related  to the
-sensing range is removed because we consider a fixed sensing range.
-
-For our  energy consumption model, we  refer to the sensor  node Medusa~II which
-uses an Atmels  AVR ATmega103L microcontroller~\cite{raghunathan2002energy}. The
-typical  architecture  of a  sensor  is composed  of  four  subsystems: the  MCU
-subsystem which is capable of computation, communication subsystem (radio) which
-is responsible  for transmitting/receiving messages, the  sensing subsystem that
-collects  data, and  the  power supply  which  powers the  complete sensor  node
-\cite{raghunathan2002energy}. Each  of the first three subsystems  can be turned
-on or  off depending on  the current status  of the sensor.   Energy consumption
-(expressed in  milliWatt per second) for  the different status of  the sensor is
-summarized in Table~\ref{table4}.
-
-\begin{table}[ht]
-\caption{The Energy Consumption Model}
-\centering
-\begin{tabular}{|c|c|c|c|c|}
-  \hline
-Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex]
-\hline
-LISTENING & on & on & on & 20.05 \\
-\hline
-ACTIVE & on & off & on & 9.72 \\
-\hline
-SLEEP & off & off & off & 0.02 \\
-\hline
-COMPUTATION & on & on & on & 26.83 \\
-\hline
-\end{tabular}
-
-\label{table4}
-\end{table}
-
-For the sake of simplicity we ignore the  energy needed to turn on the radio, to
-start up the sensor node, to move from one status to another, etc.
-Thus, when a sensor becomes active (i.e.,  it has already chosen its status), it
-can turn its radio  off to save battery.  MuDiLCO uses two  types of packets for
-communication. The size of the INFO  packet and Active-Sleep packet are 112~bits
-and 24~bits  respectively.  The value  of energy  spent to send  a 1-bit-content
-message is  obtained by using  the equation in  ~\cite{raghunathan2002energy} to
-calculate the  energy cost  for transmitting  messages and  we propose  the same
-value for receiving  the packets. The energy  needed to send or  receive a 1-bit
-packet is equal to 0.2575~mW.
-
-The initial energy of each node is  randomly set in the interval $[500;700]$.  A
-sensor node will  not participate in the  next round if its  remaining energy is
-less than  $E_{R}=36~\mbox{Joules}$, the minimum  energy needed for the  node to
-stay alive  during one round.  This  value has been computed  by multiplying the
-energy consumed in  active state (9.72 mW)  by the time in second  for one round
-(3600 seconds).   According to the interval  of initial energy, a  sensor may be
-alive during at most 20 rounds.
-\fi
+  values.}  

 
 \subsection{Metrics}
 
 
 \subsection{Metrics}
 

-\textcolor{blue}{To evaluate  our approach  we consider the  performance metrics
+\textcolor{black}{To evaluate  our approach  we consider the  performance metrics

   detailed in~\cite{idrees2015distributed},  which are: Coverage  Ratio, Network
   Lifetime  and  Energy  Consumption.   Compared to  the  previous  definitions,
   formulations of  Coverage Ratio and  Energy Consumption are enriched  with the
   detailed in~\cite{idrees2015distributed},  which are: Coverage  Ratio, Network
   Lifetime  and  Energy  Consumption.   Compared to  the  previous  definitions,
   formulations of  Coverage Ratio and  Energy Consumption are enriched  with the


@@ -828,21 +738,7 @@ indicate the energy consumed by the whole network in round $t$.
 %nodes  have  been drained  of  their  energy  or each  sensor  network monitoring  an area has become  disconnected.
 \end{enumerate}
 
 %nodes  have  been drained  of  their  energy  or each  sensor  network monitoring  an area has become  disconnected.
 \end{enumerate}
 

-\iffalse
-\begin{enumerate}
- \setcounter{5}
-\item {{\bf  Execution Time}:}  a sensor node  has limited energy  resources and
-  computing power, therefore it is important that the proposed algorithm has the
-  shortest possible execution  time. The energy of a sensor  node must be mainly
-  used for the sensing phase, not for the pre-sensing ones.
-  
-\item {{\bf Stopped simulation runs}:} a simulation ends when the sensor network
-  becomes disconnected (some nodes are dead and are not able to send information
-  to the base station). We report the number of simulations that are stopped due
-  to network disconnections and for which round it occurs.

 
 

-\end{enumerate}
-\fi

 
 \section{Experimental results and analysis}
 \label{analysis}
 
 \section{Experimental results and analysis}
 \label{analysis}


@@ -856,7 +752,8 @@ points. The  objective of this  comparison is to  select the suitable  number of
 primary points to be used by  a MuDiLCO protocol.  In this comparison, MuDiLCO-1
 protocol is used  with five primary point models, each  model corresponding to a
 number of primary  points, which are called Model-5 (it  uses 5 primary points),
 primary points to be used by  a MuDiLCO protocol.  In this comparison, MuDiLCO-1
 protocol is used  with five primary point models, each  model corresponding to a
 number of primary  points, which are called Model-5 (it  uses 5 primary points),

-Model-9, Model-13,  Model-17, and  Model-21. \textcolor{blue}{Note  that results
+Model-9, Model-13,  Model-17, and  Model-21. \textcolor{black}{Note
+  that the results

   presented in~\cite{idrees2015distributed}  correspond to Model-13  (13 primary
   points)}.
 
   presented in~\cite{idrees2015distributed}  correspond to Model-13  (13 primary
   points)}.
 


@@ -873,7 +770,7 @@ because it offers a good coverage ratio for a larger number of periods.
 
 \begin{figure}[t!]
 \centering
 
 \begin{figure}[t!]
 \centering

- \includegraphics[scale=0.5] {R2/CR.pdf} 
+ \includegraphics[scale=0.5] {R2CR.pdf} 

 \caption{Coverage ratio for 150 deployed nodes}
 \label{Figures/ch4/R2/CR}
 \end{figure} 
 \caption{Coverage ratio for 150 deployed nodes}
 \label{Figures/ch4/R2/CR}
 \end{figure} 


@@ -889,9 +786,9 @@ lifetime improvement.
 \begin{figure}[h!]
 \centering
 \centering
 \begin{figure}[h!]
 \centering
 \centering

-\includegraphics[scale=0.5]{R2/LT95.pdf}\\~ ~ ~ ~ ~(a) \\
+\includegraphics[scale=0.5]{R2LT95.pdf}\\~ ~ ~ ~ ~(a) \\

 
 

-\includegraphics[scale=0.5]{R2/LT50.pdf}\\~ ~ ~ ~ ~(b)
+\includegraphics[scale=0.5]{R2LT50.pdf}\\~ ~ ~ ~ ~(b)

 
 \caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$}
   \label{Figures/ch4/R2/LT}
 
 \caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$}
   \label{Figures/ch4/R2/LT}


@@ -922,7 +819,7 @@ the best coverage ratio up to round~80, after that MuDiLCO-5 is slightly better.
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

- \includegraphics[scale=0.5] {F/CR.pdf} 
+ \includegraphics[scale=0.5] {FCR.pdf} 

 \caption{Average coverage ratio for 150 deployed nodes}
 \label{fig3}
 \end{figure} 
 \caption{Average coverage ratio for 150 deployed nodes}
 \label{fig3}
 \end{figure} 


@@ -941,7 +838,7 @@ efficient manner.
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

-\includegraphics[scale=0.5]{F/ASR.pdf}  
+\includegraphics[scale=0.5]{FASR.pdf}  

 \caption{Active sensors ratio for 150 deployed nodes}
 \label{fig4}
 \end{figure} 
 \caption{Active sensors ratio for 150 deployed nodes}
 \label{fig4}
 \end{figure} 


@@ -961,7 +858,7 @@ in a subregion is still connected.
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

-\includegraphics[scale=0.5]{F/SR.pdf} 
+\includegraphics[scale=0.5]{FSR.pdf} 

 \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes}
 \label{fig6}
 \end{figure} 
 \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes}
 \label{fig6}
 \end{figure} 


@@ -977,9 +874,9 @@ network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$.
 \begin{figure}[h!]
   \centering
   \begin{tabular}{cl}
 \begin{figure}[h!]
   \centering
   \begin{tabular}{cl}

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC95.pdf}} & (a) \\
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{FEC95.pdf}} & (a) \\

     \verb+ + \\
     \verb+ + \\

-    \parbox{9.5cm}{\includegraphics[scale=0.5]{F/EC50.pdf}} & (b)
+    \parbox{9.5cm}{\includegraphics[scale=0.5]{FEC50.pdf}} & (b)

   \end{tabular}
   \caption{Energy consumption for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \end{tabular}
   \caption{Energy consumption for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}


@@ -1018,7 +915,7 @@ Figure~\ref{fig77} for different network sizes.
 
 \begin{figure}[ht!]
 \centering
 
 \begin{figure}[ht!]
 \centering

-\includegraphics[scale=0.5]{F/T.pdf}  
+\includegraphics[scale=0.5]{FT.pdf}  

 \caption{Execution Time (in seconds)}
 \label{fig77}
 \end{figure} 
 \caption{Execution Time (in seconds)}
 \label{fig77}
 \end{figure} 


@@ -1066,9 +963,9 @@ metrics, MuDiLCO-5 seems to be the best suited method compared to MuDiLCO-7.
 \begin{figure}[t!]
   \centering
   \begin{tabular}{cl}
 \begin{figure}[t!]
   \centering
   \begin{tabular}{cl}

-    \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT95.pdf}} & (a) \\
+    \parbox{9.5cm}{\includegraphics[scale=0.5125]{FLT95.pdf}} & (a) \\

     \verb+ + \\
     \verb+ + \\

-    \parbox{9.5cm}{\includegraphics[scale=0.5125]{F/LT50.pdf}} & (b)
+    \parbox{9.5cm}{\includegraphics[scale=0.5125]{FLT50.pdf}} & (b)

   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}
   \end{tabular}
   \caption{Network lifetime for (a) $Lifetime_{95}$ and 
     (b) $Lifetime_{50}$}