Update by Ali

[ThesisAli.git] / CHAPITRE_02.tex

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index 73e685f3fb8c3bafbd32986190b589202b859f36..b306630203b4b3ccf89e7abd6c670afc7d57e4d4 100755 (executable)
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -92,17 +92,17 @@ Their work builds upon previous work in~\cite{ref116} and the  generated cover s
 
 
 The authors in~\cite{ref115} proposed  a heuristic  to compute  the  disjoint  set covers  (DSC).  In order  to compute the maximum number of  covers, they first transform DSC into a maximum-flow problem, which  is then formulated  as a  mixed integer programming  problem (MIP).  Based on  the solution  of the  MIP, they design a heuristic to compute  the final number of covers. The results show  a slight  performance  improvement  in terms  of  the number  of produced  DSC in comparison  to~\cite{ref116}, but it incurs  higher execution  time due to  the complexity of  the mixed integer programming solving. Zorbas  et  al.  \cite{ref228}  presented  B\{GOP\},  a  centralized target coverage  algorithm  introducing   sensor   candidate  categorization depending on their  coverage status and the notion  of critical target to  call  targets   that  are  associated  with  a   small  number  of sensors. The total running time of their heuristic is $0(m n^2)$ where
 
 
 The authors in~\cite{ref115} proposed  a heuristic  to compute  the  disjoint  set covers  (DSC).  In order  to compute the maximum number of  covers, they first transform DSC into a maximum-flow problem, which  is then formulated  as a  mixed integer programming  problem (MIP).  Based on  the solution  of the  MIP, they design a heuristic to compute  the final number of covers. The results show  a slight  performance  improvement  in terms  of  the number  of produced  DSC in comparison  to~\cite{ref116}, but it incurs  higher execution  time due to  the complexity of  the mixed integer programming solving. Zorbas  et  al.  \cite{ref228}  presented  B\{GOP\},  a  centralized target coverage  algorithm  introducing   sensor   candidate  categorization depending on their  coverage status and the notion  of critical target to  call  targets   that  are  associated  with  a   small  number  of sensors. The total running time of their heuristic is $0(m n^2)$ where

-$n$ is the number of sensors  and $m$ the number of targets. Compared to    algorithm's    results of  Slijepcevic and    Potkonjak \cite{ref116},  their   heuristic  produces  more cover sets with a slight growth rate in execution time.
+$n$ is the number of sensors  and $m$ the number of targets. Compared to    algorithm's    results of  Slijepcevic and    Potkonjak \cite{ref116},  their   heuristic  produces  more cover sets with a slight growth rate in execution time. More recently, Deschinkel and Hakem \cite{229} introduced  a near-optimal heuristic algorithm for solving the target coverage problem in WSN. The sensor nodes are organized into disjoint cover sets by the resolution an integer programming problem. Each cover set is capable of monitoring all the targets of the region of interest. Those covers sets are scheduled periodically. Their algorithm  able to construct the different cover sets in parallel. The results show that their algorithm achieves near-optimal solutions compared to the optimal ones obtained by the exact method.

 
 
 
 
 
 
 
 

-
-
-
-
-
-In the case of non-disjoint algorithms~\cite{ref117}, sensors may participate in more than one  cover set. In some cases, this may prolong the lifetime of the network in comparison  to the disjoint cover set algorithms, but designing  algorithms for  non-disjoint cover  sets generally  induces  a higher order  of complexity. Moreover, in  case of  a sensor's  failure, non-disjoint scheduling  policies are less resilient and reliable because a sensor may be involved in more than one cover sets.
+In the case of non-disjoint algorithms~\cite{ref117}, sensors may participate in more than one  cover set. In some cases, this may prolong the lifetime of the network in comparison  to the disjoint cover set algorithms, but designing  algorithms for  non-disjoint cover  sets generally  induces  a higher order  of complexity. Moreover, in  case of a sensor's  failure, non-disjoint scheduling  policies are less resilient and reliable because a sensor may be involved in more than one cover sets. For instance,  Cardei et al.~\cite{ref167}
+present a  linear programming (LP)  solution and a greedy  approach to
+extend the  sensor network lifetime  by organizing the sensors  into a
+maximal  number of  non-disjoint cover  sets. Simulation  results show
+that by allowing sensors to  participate in multiple sets, the network
+lifetime increases compared with related work~\cite{ref115}.