Update with Ali

[ThesisAli.git] / CHAPITRE_06.tex

diff --git a/CHAPITRE_06.tex b/CHAPITRE_06.tex
index aeb9ffa180d52a7d581b48a9a76a4ec31f5b3b9f..33c8fa3d4f52faf855ee6679076e57206277a74c 100644 (file)
--- a/CHAPITRE_06.tex
+++ b/CHAPITRE_06.tex
@@ -17,7 +17,7 @@
 In this chapter,  we propose an approach called Perimeter-based Coverage Optimization
 protocol (PeCO). 
 %The PeCO protocol merges between two energy efficient mechanisms, which are used the main advantages of the centralized and distributed approaches and avoids the most of their disadvantages. An energy-efficient activity scheduling mechanism based new optimization model is performed by each leader in the subregions. 
 In this chapter,  we propose an approach called Perimeter-based Coverage Optimization
 protocol (PeCO). 
 %The PeCO protocol merges between two energy efficient mechanisms, which are used the main advantages of the centralized and distributed approaches and avoids the most of their disadvantages. An energy-efficient activity scheduling mechanism based new optimization model is performed by each leader in the subregions. 

-The scheme is similar to the one described in section \ref{ch4:sec:02:03}. But in this approach, the optimization model is based on the perimeter coverage model in order to produce the optimal cover set of active sensors, which are taken the responsibility of sensing during the current period. 
+The scheme is similar to the one described in section \ref{ch4:sec:02:03}. But in this approach, the optimization model is based on the perimeter coverage model in order to produce the optimal cover set of active sensors, which are taking the responsibility of sensing during the current period. 

 
 
 The rest of the chapter is organized as follows. The next section is devoted to the PeCO protocol description and section~\ref{ch6:sec:03} focuses on the coverage model formulation which is used  to schedule the activation  of sensor nodes.  Section~\ref{ch6:sec:04} presents simulation results and discusses the comparison with other approaches. Finally, concluding remarks   are  drawn in section~\ref{ch6:sec:05}.
 
 
 The rest of the chapter is organized as follows. The next section is devoted to the PeCO protocol description and section~\ref{ch6:sec:03} focuses on the coverage model formulation which is used  to schedule the activation  of sensor nodes.  Section~\ref{ch6:sec:04} presents simulation results and discusses the comparison with other approaches. Finally, concluding remarks   are  drawn in section~\ref{ch6:sec:05}.


@@ -57,8 +57,8 @@ arcs.
 \end{figure} 
 
 Figure~\ref{pcm2sensors}(b) describes the geometric information used to find the locations of the  left and right points of  an arc on the perimeter  of a sensor node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the
 \end{figure} 
 
 Figure~\ref{pcm2sensors}(b) describes the geometric information used to find the locations of the  left and right points of  an arc on the perimeter  of a sensor node~$u$ covered by a sensor node~$v$. Node~$v$ is supposed to be located on the

-west  side of  sensor~$u$,  with  the following  respective  coordinates in  the sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates, the euclidean distance between nodes~$u$ and $v$ is computed as follow: $Dist(u,v)=\sqrt{\vert
-  u_x  - v_x  \vert^2 +  \vert u_y-v_y  \vert^2}$, 
+west  side of  sensor~$u$,  with  the following  respective  coordinates in  the sensing area~: $(v_x,v_y)$ and $(u_x,u_y)$. From the previous coordinates, the euclidean distance between nodes~$u$ and $v$ is computed as follow: $Dist(u,v)=\sqrt{\left( 
+  u_x  - v_x  \right)^2 +  \left( u_y-v_y  \right)^2}$, 

 
 while  the angle~$\alpha$  is obtained through  the formula:
 
 
 while  the angle~$\alpha$  is obtained through  the formula:
 


@@ -180,8 +180,8 @@ protocol applied by a sensor node $s_j$ where $j$ is the node index in the WSN.
         \emph{ Use the same previous cover set for current sensing stage}\;
       }
       \Else{
         \emph{ Use the same previous cover set for current sensing stage}\;
       }
       \Else{

-            \emph{Update $a^j_{ik}$; prepare data for IP~Algorithm}\;
-            \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{A}\right)\right\}$ = Execute Integer Program Algorithm($A$)}\;
+            \emph{Update $a^j_{ik}$; prepare data for MIP~Algorithm}\;
+            \emph{$\left\{\left(X_{1},\dots,X_{k},\dots,X_{A}\right)\right\}$ = Execute MIP Algorithm($A$)}\;

             \emph{A.PreviousSize = A.CurrentSize}\;
            }
       
             \emph{A.PreviousSize = A.CurrentSize}\;
            }
       


@@ -287,7 +287,9 @@ With the performance metrics, described in section \ref{ch4:sec:04:04}, we evalu
 In  order to  assess and  analyze  the  performance  of  our protocol  we  have implemented PeCO protocol in  OMNeT++~\cite{ref158} simulator.  
 %Besides PeCO, three other protocols,  described in  the next paragraph,  will  be  evaluated for comparison purposes. 
 %The simulations were run  on a laptop DELL with an Intel Core~i3~2370~M (2.4~GHz) processor (2  cores) whose MIPS  (Million Instructions Per Second) rate  is equal to 35330. To  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)$.  The modeling  language for Mathematical Programming (AMPL)~\cite{AMPL} is  employed 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) \cite{glpk} through a Branch-and-Bound method.
 In  order to  assess and  analyze  the  performance  of  our protocol  we  have implemented PeCO protocol in  OMNeT++~\cite{ref158} simulator.  
 %Besides PeCO, three other protocols,  described in  the next paragraph,  will  be  evaluated for comparison purposes. 
 %The simulations were run  on a laptop DELL with an Intel Core~i3~2370~M (2.4~GHz) processor (2  cores) whose MIPS  (Million Instructions Per Second) rate  is equal to 35330. To  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)$.  The modeling  language for Mathematical Programming (AMPL)~\cite{AMPL} is  employed 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) \cite{glpk} through a Branch-and-Bound method.

-PeCO protocol is  compared with three other approaches. DESK \cite{DESK}, GAF~\cite{GAF}, and DiLCO~\cite{Idrees2} is  an improved version of a research work we presented in~\cite{ref159}, where DiLCO protocol is described in chapter 4. Let us notice that the PeCO and  the DiLCO protocols are  based on the  same scheme. In  particular, the choice for the simulations of a partitioning in 16~subregions was chosen because it corresponds to the configuration producing the better 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$).
+PeCO protocol is  compared with three other approaches. DESK \cite{DESK}, GAF~\cite{GAF}, and DiLCO~\cite{Idrees2}.
+ %is  an improved version of a research work we presented in~\cite{ref159}, where DiLCO protocol is described in chapter 4. 
+ Let us notice that the PeCO and  the DiLCO protocols are  based on the  same scheme. In  particular, the choice for the simulations of a partitioning in 16~subregions was chosen because it corresponds to the configuration producing the better 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$).

 
 
 
 
 
 


@@ -311,7 +313,7 @@ appears that  PeCO provides a better  coverage ratio and keeps  a coverage ratio
 \label{ch6:sec:04:02:02}
 
 Having the less active sensor nodes in  each period is essential to minimize the energy consumption  and thus to  maximize the network  lifetime.  Figure~\ref{fig444} shows the  average active nodes ratio  for 200 deployed nodes.   We observe that DESK and  GAF have 30.36  \% and  34.96 \% active  nodes for the  first fourteen rounds, and  DiLCO and PeCO  protocols compete perfectly  with only 17.92  \% and 20.16 \% active  nodes during the same  time interval. As the  number of periods increases, PeCO protocol  has a lower number of active  nodes in comparison with
 \label{ch6:sec:04:02:02}
 
 Having the less active sensor nodes in  each period is essential to minimize the energy consumption  and thus to  maximize the network  lifetime.  Figure~\ref{fig444} shows the  average active nodes ratio  for 200 deployed nodes.   We observe that DESK and  GAF have 30.36  \% and  34.96 \% active  nodes for the  first fourteen rounds, and  DiLCO and PeCO  protocols compete perfectly  with only 17.92  \% and 20.16 \% active  nodes during the same  time interval. As the  number of periods increases, PeCO protocol  has a lower number of active  nodes in comparison with

-the three other approaches, while keeping a greater coverage ratio as shown in Figure \ref{fig333}.
+the three other approaches, while keeping a greater coverage ratio as shown in Figure \ref{fig333}. \\ 

 
 \begin{figure}[h!]
 \centering
 
 \begin{figure}[h!]
 \centering


@@ -398,7 +400,7 @@ $\alpha$ & $\beta$ & $Lifetime_{50}$ & $Lifetime_{95}$ \\ \hline
 \label{ch6:sec:05}
 
 In this chapter, we have studied the problem of  Perimeter-based Coverage Optimization in WSNs. We have designed  a new protocol, called Perimeter-based  Coverage Optimization, which schedules nodes'  activities (wake up  and sleep  stages) with the  objective of maintaining a  good coverage ratio  while maximizing the network  lifetime. This protocol is  applied in a distributed  way in regular subregions  obtained after partitioning the area of interest in a preliminary step. It works in periods and
 \label{ch6:sec:05}
 
 In this chapter, we have studied the problem of  Perimeter-based Coverage Optimization in WSNs. We have designed  a new protocol, called Perimeter-based  Coverage Optimization, which schedules nodes'  activities (wake up  and sleep  stages) with the  objective of maintaining a  good coverage ratio  while maximizing the network  lifetime. This protocol is  applied in a distributed  way in regular subregions  obtained after partitioning the area of interest in a preliminary step. It works in periods and

-is based on the resolution of an integer program to select the subset of sensors operating in active status for each period. Our work is original because it proposes for  the first  time an  integer program  scheduling the  activation of sensors  based on  their perimeter  coverage level,  instead of  using a  set of targets/points to be covered. We  have carried out  several simulations  to  evaluate the  proposed protocol. The simulation  results  show   that  PeCO  is  more   energy-efficient  than  other approaches, with respect to lifetime,  coverage ratio, active sensors ratio, and energy consumption.
+is based on the resolution of an mixed-integer program to select the subset of sensors operating in active status for each period. Our work is original because it proposes for  the first  time an  integer program  scheduling the  activation of sensors  based on  their perimeter  coverage level,  instead of  using a  set of targets/points to be covered. We  have carried out  several simulations  to  evaluate the  proposed protocol. The simulation  results  show   that  PeCO  is  more   energy-efficient  than  other approaches, with respect to lifetime,  coverage ratio, active sensors ratio, and energy consumption.

 
 %We plan to extend our framework so that the schedules are planned for multiple sensing periods. We also want  to improve our integer program to  take into account heterogeneous sensors  from both  energy  and node  characteristics point of views. Finally,  it   would  be   interesting  to  implement   our  protocol   using  a sensor-testbed to evaluate it in real world applications.
 
 
 %We plan to extend our framework so that the schedules are planned for multiple sensing periods. We also want  to improve our integer program to  take into account heterogeneous sensors  from both  energy  and node  characteristics point of views. Finally,  it   would  be   interesting  to  implement   our  protocol   using  a sensor-testbed to evaluate it in real world applications.