]> AND Private Git Repository - ThesisAli.git/blobdiff - CHAPITRE_04.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Last update by Ali
[ThesisAli.git] / CHAPITRE_04.tex
index edbf25982eabb9f137a46b431527f700f164cb1b..c634430a8365f1bdadfac2262a8252867ff0e4ad 100644 (file)
@@ -66,12 +66,16 @@ $X_2=( p_x + R_s * (1), p_y + R_s * (0) )$\\
 $X_3=( p_x + R_s * (-1), p_y + R_s * (0)) $\\
 $X_4=( p_x + R_s * (0), p_y + R_s * (1) )$\\
 $X_5=( p_x + R_s * (0), p_y + R_s * (-1 )) $\\
 $X_3=( p_x + R_s * (-1), p_y + R_s * (0)) $\\
 $X_4=( p_x + R_s * (0), p_y + R_s * (1) )$\\
 $X_5=( p_x + R_s * (0), p_y + R_s * (-1 )) $\\
-$X_6= ( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (0)) $\\
-$X_7=( p_x + R_s *  (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
+%$X_6= ( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (0)) $\\
+$X_{6}=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
+%$X_7=( p_x + R_s *  (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
+$X_{7}=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
 $X_8=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
 $X_9=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
 $X_8=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
 $X_9=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
-$X_{10}=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
-$X_{11}=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
+%$X_{10}=( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
+$X_{10}= ( p_x + R_s * (\frac{-\sqrt{2}}{2}), p_y + R_s * (0)) $\\
+%$X_{11}=( p_x + R_s * (\frac{\sqrt{2}}{2}), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
+$X_{11}=( p_x + R_s *  (\frac{\sqrt{2}}{2}), p_y + R_s * (0))$\\
 $X_{12}=( p_x + R_s * (0), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
 $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
 $X_{14}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (\frac{1}{2})) $\\
 $X_{12}=( p_x + R_s * (0), p_y + R_s * (\frac{\sqrt{2}}{2})) $\\
 $X_{13}=( p_x + R_s * (0), p_y + R_s * (\frac{-\sqrt{2}}{2})) $\\
 $X_{14}=( p_x + R_s * (\frac{\sqrt{3}}{2}), p_y + R_s * (\frac{1}{2})) $\\
@@ -94,7 +98,7 @@ $X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $.
  \begin{multicols}{2}
 \centering
 \includegraphics[scale=0.33]{Figures/ch4/fig21.pdf}\\~ ~ ~ ~ ~ ~ ~ ~(a)
  \begin{multicols}{2}
 \centering
 \includegraphics[scale=0.33]{Figures/ch4/fig21.pdf}\\~ ~ ~ ~ ~ ~ ~ ~(a)
-\includegraphics[scale=0.33]{Figures/ch4/principles13.pdf}\\~ ~ ~ ~ ~ ~(c) 
+\includegraphics[scale=0.33]{Figures/ch4/fig23.pdf}\\~ ~ ~ ~ ~ ~(c) 
 \hfill \hfill
 \includegraphics[scale=0.33]{Figures/ch4/fig25.pdf}\\~ ~ ~ ~ ~ ~(e)
 \includegraphics[scale=0.33]{Figures/ch4/fig22.pdf}\\~ ~ ~ ~ ~ ~ ~ ~ ~(b)
 \hfill \hfill
 \includegraphics[scale=0.33]{Figures/ch4/fig25.pdf}\\~ ~ ~ ~ ~ ~(e)
 \includegraphics[scale=0.33]{Figures/ch4/fig22.pdf}\\~ ~ ~ ~ ~ ~ ~ ~ ~(b)
@@ -187,7 +191,14 @@ Active  sensors  in the  period  will  execute  their sensing  task  to preserve
 
 An outline of the  protocol implementation is given by Algorithm~\ref{alg:DiLCO} which describes the execution of a period  by a node (denoted by $s_j$  for a sensor  node indexed by  $j$). In  the beginning,  a node  checks whether  it has enough energy to stay active during the next sensing phase (i.e., the remaining energy $RE_j$ $\geq$ $E_{th}$ (the  amount of energy required to be alive during one period)). If yes, it exchanges information  with  all the  other nodes belonging to the same subregion:  it collects from each node its position coordinates, remaining energy ($RE_j$), ID, and  the number  of  one-hop neighbors  still  alive. Once  the  first phase  is completed, the nodes  of a subregion choose a leader to  take the decision based on the criteria described in section \ref{ch4:sec:02:03:02}.
 %the  following  criteria   with  decreasing  importance:  larger  number  of neighbors, larger remaining energy, and  then in case of equality, larger index. 
 
 An outline of the  protocol implementation is given by Algorithm~\ref{alg:DiLCO} which describes the execution of a period  by a node (denoted by $s_j$  for a sensor  node indexed by  $j$). In  the beginning,  a node  checks whether  it has enough energy to stay active during the next sensing phase (i.e., the remaining energy $RE_j$ $\geq$ $E_{th}$ (the  amount of energy required to be alive during one period)). If yes, it exchanges information  with  all the  other nodes belonging to the same subregion:  it collects from each node its position coordinates, remaining energy ($RE_j$), ID, and  the number  of  one-hop neighbors  still  alive. Once  the  first phase  is completed, the nodes  of a subregion choose a leader to  take the decision based on the criteria described in section \ref{ch4:sec:02:03:02}.
 %the  following  criteria   with  decreasing  importance:  larger  number  of neighbors, larger remaining energy, and  then in case of equality, larger index. 
-After that,  if the sensor node is  leader, it will execute  the integer program algorithm (see Section~\ref{ch4:sec:03})  which provides a set of  sensors planned to be active in the next sensing phase. As leader, it will send an ActiveSleep packet to each sensor  in the same subregion to  indicate it if it has to  be active or not.  Alternately, if  the  sensor  is not  the  leader, it  will  wait for  the ActiveSleep packet to know its state for the coming sensing phase.
+After that,  if the sensor node is  leader, it will execute  the integer program algorithm (see Section~\ref{ch4:sec:03})  which provides a set of  sensors planned to be active in the next sensing phase. As leader, it will send an ActiveSleep packet to each sensor  in the same subregion to  indicate it if it has to  be active or not.  Alternately, if  the  sensor  is not  the  leader, it  will  wait for  the ActiveSleep packet to know its state for the coming sensing phase. \textcolor{blue}{The flow chart of DiLCO protocol that executed in each sensor node is presented in \ref{flow4}.} 
+
+\begin{figure}[ht!]
+\centering
+\includegraphics[scale=0.50]{Figures/ch4/Algo1.png} % 70mm
+\caption{The flow chart of DiLCO protocol.}
+\label{flow4}
+\end{figure} 
 
 %Primary Points based 
 \section{Coverage Problem Formulation}
 
 %Primary Points based 
 \section{Coverage Problem Formulation}
@@ -342,7 +353,7 @@ The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is  employ
 
 \indent In this dissertation, we used an energy consumption model proposed by~\cite{DESK} and based on \cite{ref112} with slight  modifications.  The energy consumption for  sending/receiving the packets is added, whereas the  part related to the dynamic sensing range is removed because we consider a fixed sensing range.
 
 
 \indent In this dissertation, we used an energy consumption model proposed by~\cite{DESK} and based on \cite{ref112} with slight  modifications.  The energy consumption for  sending/receiving the packets is added, whereas the  part related to the dynamic sensing range is removed because we consider a fixed sensing range.
 
-\indent For our energy consumption model, we refer to the sensor node Medusa~II which uses an Atmel's  AVR ATmega103L microcontroller~\cite{ref112}. 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{ref112}. 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{table1}.
+\indent For our energy consumption model, we refer to the sensor node Medusa~II which uses an Atmel's  AVR ATmega103L microcontroller~\cite{ref112}. 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{ref112}. 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{tab:EC}.
 
 \begin{table}[h]
 \centering
 
 \begin{table}[h]
 \centering
@@ -350,7 +361,7 @@ The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is  employ
 \label{tab:EC}
 \begin{tabular}{|l||cccc|}
   \hline
 \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 \\
   \hline
   LISTENING & On & On & On & 20.05 \\
   ACTIVE & On & Off & On & 9.72 \\
@@ -504,7 +515,7 @@ As shown in Figures~\ref{Figures/ch4/R1/EC}(a) and~\ref{Figures/ch4/R1/EC}(b), D
 \item {{\bf Execution Time}}
 %\subsubsection{Execution Time}
 
 \item {{\bf Execution Time}}
 %\subsubsection{Execution Time}
 
-In this experiment, the execution time of the distributed optimization approach has been studied. Figure~\ref{Figures/ch4/R1/T} gives the average execution times in seconds for the decision phase (solving of the optimization problem) during one period. They are given for the different approaches and various numbers of sensors. The original execution time is computed as described in section \ref{ch4:sec:04:04}. \\ \\ \\ \\
+In this experiment, the execution time of the distributed optimization approach has been studied. Figure~\ref{Figures/ch4/R1/T} gives the average execution times in seconds for the decision phase (solving of the optimization problem) during one period. They are given for the different approaches and various numbers of sensors.  \\ \\% \\ \\ \\
 
 
 
 
 
 
@@ -515,7 +526,7 @@ In this experiment, the execution time of the distributed optimization approach
 \label{Figures/ch4/R1/T}
 \end{figure} 
 
 \label{Figures/ch4/R1/T}
 \end{figure} 
 
-We can see from Figure~\ref{Figures/ch4/R1/T} that DiLCO-32 has very low execution times in comparison with other DiLCO versions because it is distributed on larger number of small subregions.  Conversely, DiLCO-2 requires to solve an optimization problem considering half the nodes in each subregion and thus presents high execution times. Overall, to be able to deal with very large networks,  a distributed method is clearly required.
+The original execution time is computed as described in section \ref{ch4:sec:04:04}. We can see from Figure~\ref{Figures/ch4/R1/T} that DiLCO-32 has very low execution times in comparison with other DiLCO versions because it is distributed on larger number of small subregions.  Conversely, DiLCO-2 requires to solve an optimization problem considering half the nodes in each subregion and thus presents high execution times. Overall, to be able to deal with very large networks,  a distributed method is clearly required.
 
 \item {{\bf Network Lifetime}}
 %\subsubsection{The Network Lifetime}
 
 \item {{\bf Network Lifetime}}
 %\subsubsection{The Network Lifetime}