Last update by Ali

[ThesisAli.git] / CHAPITRE_06.tex

diff --git a/CHAPITRE_06.tex b/CHAPITRE_06.tex
index aeb9ffa180d52a7d581b48a9a76a4ec31f5b3b9f..66f0e6a60a94373c698e2f3f696b9dc13ab15d1e 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:
 


@@ -132,7 +132,7 @@ In the PeCO protocol,  the  scheduling  of  the  sensor nodes'  activities  is f
 
 \noindent 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. 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.
 
 
 \noindent 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. 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.
 

-As  shown in  Figure~\ref{fig2}, node  activity  scheduling is  produced by  our protocol in a periodic manner. Each period is divided into 4 stages: Information (INFO)  Exchange,  Leader Election,  Decision  (the  result of  an  optimization problem),  and  Sensing.   For  each  period, there  is  exactly  one  set  cover responsible for  the sensing task.  Protocols  based on a periodic  scheme, like PeCO, are more  robust against an unexpected  node failure. On the  one hand, if a node failure is discovered before  taking the decision, the corresponding sensor
+As shown in  Figure~\ref{fig2}, node  activity  scheduling is  produced by  our protocol in a periodic manner. Each period is divided into 4 stages: Information (INFO)  Exchange,  Leader Election,  Decision  (the  result of  an  optimization problem),  and  Sensing.   For  each  period, there  is  exactly  one  set  cover responsible for  the sensing task.  Protocols  based on a periodic  scheme, like PeCO, are more  robust against an unexpected  node failure. On the  one hand, if a node failure is discovered before  taking the decision, the corresponding sensor

 node will  not be considered  by the optimization  algorithm. On  the other hand, if the sensor failure happens after  the decision, the sensing task of the network will be temporarily affected: only  during the period of sensing until a new period starts, since a new set cover will take charge of the sensing task in the next period. The energy consumption and some other constraints can easily be taken  into  account since  the  sensors  can  update  and then  exchange  their information (including their  residual energy) at the beginning  of each period. However, the pre-sensing  phases (INFO Exchange, Leader  Election, and Decision)
 are energy consuming, even for nodes that will not join the set cover to monitor the area.
 
 node will  not be considered  by the optimization  algorithm. On  the other hand, if the sensor failure happens after  the decision, the sensing task of the network will be temporarily affected: only  during the period of sensing until a new period starts, since a new set cover will take charge of the sensing task in the next period. The energy consumption and some other constraints can easily be taken  into  account since  the  sensors  can  update  and then  exchange  their information (including their  residual energy) at the beginning  of each period. However, the pre-sensing  phases (INFO Exchange, Leader  Election, and Decision)
 are energy consuming, even for nodes that will not join the set cover to monitor the area.
 


@@ -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}\;
            }
       


@@ -209,7 +209,14 @@ The sensors  inside a same  region cooperate to  elect a leader.   The selection
 \item larger  remaining energy;
 \item and then  in case  of equality,  larger index.
 \end{enumerate}
 \item larger  remaining energy;
 \item and then  in case  of equality,  larger index.
 \end{enumerate}

-Once chosen, the leader collects information  to formulate and solve the integer program  which allows  to construct  the set  of active  sensors in  the sensing stage.
+Once chosen, the leader collects information  to formulate and solve the integer program  which allows  to construct  the set  of active  sensors in  the sensing stage. \textcolor{blue}{The flowchart of PeCO protocol executed in each sensor node is presented in Figure \ref{flow6}.} 
+
+\begin{figure}[ht!]
+\centering
+\includegraphics[scale=0.45]{Figures/ch6/Algo3.pdf} % 70mm
+\caption{The flowchart of PeCO protocol.}
+\label{flow6}
+\end{figure} 

 
 
 \section{Perimeter-based Coverage Problem Formulation}
 
 
 \section{Perimeter-based Coverage Problem Formulation}


@@ -287,7 +294,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 +320,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 +407,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.