Update by Ali

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.
 

diff --git a/CONCLUSION.tex b/CONCLUSION.tex
index 099f6db5d9064a69043dd5435dcf2e68498c1514..b18938780e99bab4e711e0fa122445a6b911229d 100644 (file)
--- a/CONCLUSION.tex
+++ b/CONCLUSION.tex
@@ -28,7 +28,7 @@ In chapter 6, we have proposed an approach called Perimeter-based Coverage Optim
 the objective of maintaining a good  coverage ratio while maximizing the network
 lifetime. 
 %in order to optimize the lifetime coverage, so that it provides activity scheduling which ensures sensing coverage as long as possible.
 the objective of maintaining a good  coverage ratio while maximizing the network
 lifetime. 
 %in order to optimize the lifetime coverage, so that it provides activity scheduling which ensures sensing coverage as long as possible.

- Like DiLCO and MuDiLCO, the PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new integer program during the decision phase.  The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs.
+ Like DiLCO and MuDiLCO, the PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new mixed-integer program during the decision phase.  The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs.

 
 Finally, we outline some interesting issues that will be considered in our perspectives which are discussed in more detail next.
 
 
 Finally, we outline some interesting issues that will be considered in our perspectives which are discussed in more detail next.
 


@@ -38,14 +38,13 @@ Finally, we outline some interesting issues that will be considered in our persp
 In this dissertation, we have focused on the lifetime area coverage optimization problem and we were interested only in energy-efficient distributed protocols, considering static homogeneous sensor nodes. Several parameters, constraints, and requirements can have an important impact on the coverage performance in WSNs.
 Thus, various scenarios parameters might need to be taken into consideration in the future, such as fault-tolerance, k-coverage, $\alpha$-coverage, adjustable sensor’s sensing range network, heterogeneous network, mobility, etc.
 
 In this dissertation, we have focused on the lifetime area coverage optimization problem and we were interested only in energy-efficient distributed protocols, considering static homogeneous sensor nodes. Several parameters, constraints, and requirements can have an important impact on the coverage performance in WSNs.
 Thus, various scenarios parameters might need to be taken into consideration in the future, such as fault-tolerance, k-coverage, $\alpha$-coverage, adjustable sensor’s sensing range network, heterogeneous network, mobility, etc.
 

-In chapter 4,  we have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms. 
-%A period will still consist of 4 phases, but the decision phase will compute the schedules for several sensing rounds which, aggregated together, define a kind of meta-sensing round. 
-The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead.
+In chapter 4,  we have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. 
+%We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms.  The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead.

 
 
 We also plan to design and propose a heterogeneous integrated optimization protocol in WSNs. This protocol would integrate three energy-efficient (coverage, routing and data aggregation) protocols so as to extend the network lifetime in WSNs. The sensing, routing, and  aggregation jobs are also challenges in WSNs. This integrated optimization protocol will be executed by each cluster head, a leader node in our protocols. The cluster head will be selected in a distributed way and based on local information.
 
 
 
 We also plan to design and propose a heterogeneous integrated optimization protocol in WSNs. This protocol would integrate three energy-efficient (coverage, routing and data aggregation) protocols so as to extend the network lifetime in WSNs. The sensing, routing, and  aggregation jobs are also challenges in WSNs. This integrated optimization protocol will be executed by each cluster head, a leader node in our protocols. The cluster head will be selected in a distributed way and based on local information.
 

-We plan to extend our PeCO protocol so that the schedules are planned for multiple sensing periods. We also want to improve our mathematical model to take into account heterogeneous sensors from both energy and node characteristics point of views. 
+We plan to extend our PeCO protocol so that the schedules are planned for multiple sensing periods. We consider the use of optimization methods such as particle swarm optimization or evolutionary algorithms to obtain quickly near optimal solutions. The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead.  We also want to improve our mathematical model to take into account heterogeneous sensors from both energy and node characteristics point of views. 

 
 Finally, it would be interesting to implement our protocols using a sensor-testbed to evaluate it in real world applications.
 
 
 Finally, it would be interesting to implement our protocols using a sensor-testbed to evaluate it in real world applications.