X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/bef8475407e8dab9352fe300765cf553b56e4c9d..a29271f727a8d581837d3a09899d9f87117449ca:/CHAPITRE_02.tex?ds=sidebyside

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index 73e685f..fa405d1 100755
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -61,7 +61,7 @@ In a distributed algorithms, on the other hand, the decision process is localize
 
 \textbf{\begin{center} Communication \end{center}} & Require large power consumption for communication. & Require low power consumption for communication. \\ \hline
 
-\textbf{\begin{center} Decision \end{center}} & Ensure optimal (or near-optimal) solution.  & Can not ensure optimal (or near-optimal) solution.\\ \hline
+\textbf{\begin{center} Decision \end{center}} & Ensure nearly or close to optimal solution.  & Can not ensure optimal (or near-optimal) solution.\\ \hline
 
 \textbf{\begin{center} Redundancy \end{center}} &  Provide less redundant active sensor nodes during monitoring the sensing field.  & Provide more redundant active sensor nodes during monitoring the sensing field.\\ \hline
 
@@ -92,52 +92,25 @@ 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
-$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. L. Liu et al.~\cite{ref150} formulated the maximum disjoint sets for maintaining target coverage and connectivity (MDS-MCC) problem in WSN. Two algorithms are proposed for solving this problem, the heuristic algorithm and network flow algorithm. This work did not take into account the sensor node failure, which is an unpredictable event because the two solutions are full centralized algorithms. Y. Li et al.~\cite{ref142} presented a framework with heuristic strategies to solve the area coverage problem. The framework converts any complete coverage problem to a partial coverage one with any coverage ratio by means of executing a complete coverage algorithm to find a full coverage sets with virtual radii and transforming the coverage sets to a partial coverage sets by adjusting sensing radii .  This framework has four strategies, two of them are designed for the network where the sensors have fixed sensing range and the other two are  for the network where the sensors have adjustable sensing range. The properties of the original algorithms can be maintained by this framework and the transformation process has a low execution time. The simulation results validate the efficiency of the four proposed strategies. 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. 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}. The authors in~\cite{ref148}, addressed the problem of minimum cost area coverage in which full coverage is performed by using the minimum number of sensors for an arbitrary geometric shape region. A geometric solution to the minimum cost coverage problem under a deterministic deployment is proposed. The probabilistic coverage solution which provides a relationship between the probability of coverage and the number of randomly deployed sensors in an arbitrarily-shaped region is suggested. The authors are clarified that with a random deployment about seven times more nodes are required to supply full coverage. The work in~\cite{ref144} addressed the area coverage problem by proposing a geometrically based activity scheduling scheme, named GAS, to fully cover the area of interest in WSNs. The authors deal with a small area, called target area coverage, which can be monitored by a single sensor instead of area coverage, which focuses on a large area that should be monitored by many sensors cooperatively. They explained that GAS is capable to monitor the target area by using a few sensors as possible and it can produce as many cover sets as possible. A novel area coverage method to divide the sensors of the WSN is called node coverage grouping (NCG) is suggested~\cite{ref147}. The sensors in the connectivity group are within sensing range of each other, and the data collected by them in the same group are supposed to be similar. They are proved that dividing N sensors via NCG into connectivity groups is an NP-hard problem. So, a heuristic algorithm of NCG with time complexity of $O(n^3)$ is proposed.
+For some applications, such as monitoring an ecosystem with extremely diversified environment, It might be premature assumption that sensors near to each other sense similar data. The problem of k-coverage  over the area of interest in WSNs was addressed in~\cite{ref152}. It is mathematically formulated and the spatial sensor density for full k-coverage is determined. The relation between the communication range and the sensing range is constructed by this work to retain the k-coverage and connectivity in WSN. After that, a four configuration protocols have proposed for treating the k-coverage in WSNs. Simulation results show that their protocols outperform an existing distributed k-coverage configuration protocol. The work that presented in~\cite{ref151} solved the area coverage and connectivity problem in sensor networks in an integrated way. The network lifetime is divided into a fixed number of rounds. A coverage bitmap of sensors of the domain has been generated in each round and based on this bitmap,  it has been decided which sensors stay active or turn it to sleep. They checked the connection of the graph via laplacian of the adjacency graph of active sensors in each round. The generation of coverage bitmap by using  Minkowski technique, the network is able to providing the desired ratio of coverage. They defined the connected coverage problem as an optimization problem and a centralized genetic algorithm is used to find the solution. 
 
 
-
-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~\cite{ref118}, the authors have considered a linear programming approach to select the minimum  number of working sensor nodes, in order to preserve a  maximum coverage and to extend the lifetime of the network.  
-
-The work in~\cite{ref144} addressed the target area coverage problem by proposing a geometrically based activity scheduling scheme, named GAS, to fully cover the target area in WSNs. The authors deal with a small area (target area coverage), which can be monitored by a single sensor instead of area coverage, which focuses on a large area that should be monitored by many sensors cooperatively. They explained that GAS is capable to monitor the target area by using a few sensors as possible and it can produce as many cover sets as possible.
-
-A novel method to divide the sensors of the WSN is called node coverage grouping (NCG) suggested~\cite{ref147}. The sensors in the connectivity group are within sensing range of each other, and the data collected by them in the same group are supposed to be similar. They are proved that dividing N sensors via NCG into connectivity groups is an NP-hard problem. So, a heuristic algorithm of NCG with time complexity of $O(n^3)$ is proposed.
-For some applications, such as monitoring an ecosystem with extremely diversified environment, It might be premature assumption that sensors near to each other sense similar data.
-
-In~\cite{ref148}, the problem of minimum cost coverage in which full coverage is performed by using the minimum number of sensors for an arbitrary geometric shape region is addressed.  a geometric solution to the minimum cost coverage problem under a deterministic deployment is proposed. The probabilistic coverage solution which provides a relationship between the probability of coverage and the number of randomly deployed sensors in an arbitrarily-shaped region is suggested. The authors are clarified that with a random deployment about seven times more nodes are required to supply full coverage.
-
-Li et al.~\cite{ref142} presented a framework to convert any complete coverage problem to a partial coverage one with any coverage ratio by means of executing a complete coverage algorithm to find a full coverage sets with virtual radii and transforming the coverage sets to a partial coverage sets by adjusting sensing radii.  The properties of the original algorithms can be maintained by this framework and the transformation process has a low execution time.
-
-The problem of k-coverage in WSNs was addressed~\cite{ref152}. It mathematically formulated and the spatial sensor density for full k-coverage determined, where the relation between the communication range and the sensing range constructed by this work to retain the k-coverage and connectivity in WSN. After that, a four configuration protocols have proposed for treating the k-coverage in WSNs.  
-
-Liu et al.~\cite{ref150} formulated maximum disjoint sets problem for retaining coverage and connectivity in WSN. Two algorithms are proposed for solving this problem: the heuristic algorithm and the network flow algorithm. This work did not take into account the sensor node failure, which is an unpredictable event because the two solutions are full centralized algorithms.
-
-Cheng et al.~\cite{ref119} have defined a  heuristic algorithm called Cover Sets Balance  (CSB), which  chooses  a set  of  active nodes  using  the tuple  (data coverage range, residual  energy).  Then, they have introduced  a new Correlated Node Set Computing (CNSC) algorithm to  find the correlated node set for a given node. After that, they proposed a High Residual Energy  First (HREF) node selection algorithm to minimize the number of active nodes so as to prolong the network lifetime.
-
-In~\cite{ref141}, the problem of full grid coverage is formulated using two integer linear programming models: the first, a model that takes into account only the overall coverage constraint; the second, both the connectivity and the full grid coverage constraints have taken into consideration. This work did not take into account the energy constraint.
-
-The work that presented in~\cite{ref151} solved the coverage and connectivity problem in sensor networks in an integrated way. The network lifetime is divided into a fixed number of rounds. A coverage bitmap of sensors of the domain has been generated in each round and based on this bitmap,  it has been decided which sensors
-stay active or turn it to sleep. They checked the connection of the graph via laplacian of the adjacency graph of active sensors in each round.  the generation of coverage bitmap by using  Minkowski technique, the network is able to providing the desired ratio of coverage. They have been defined the connected coverage problem as an optimization problem and a centralized genetic algorithm is used to find the solution.
-
-The authors in~\cite{ref143} explained that in some applications of WSNs such as structural health monitoring (SHM) and volcano monitoring, the traditional coverage model which is a geographic area defined for individual sensors is not always valid. For this reason, they define a generalized coverage model, which is not need to have the coverage area of individual nodes, but only based on a function to determine whether a set of sensor nodes is capable of satisfy the requested monitoring task for a certain area. They have proposed two approaches to dividing the deployed nodes into suitable cover sets, which can be used to prolong the network lifetime. 
+More recently, the authors in~\cite{ref118}, have considered an area coverage optimization algorithm based on linear programming approach to select the minimum number of working sensor nodes, in order to preserve a  maximum coverage and to extend the lifetime of the network. The experimental results show that linear programming can provide a fewest number of active nodes and maximize the network lifetime coverage. M. Rebai et al.~\cite{ref141}, formulated the problem of full grid area coverage problem using two integer linear programming models: the first, a model that takes into account only the overall coverage constraint; the second, both the connectivity and the full grid coverage constraints have taken into consideration. This work did not take into account the energy constraint. H. Cheng et al.~\cite{ref119} have defined a heuristic area coverage algorithm called Cover Sets Balance  (CSB), which  chooses  a set  of  active nodes  using  the tuple  (data coverage range, residual  energy).  Then, they have introduced  a new Correlated Node Set Computing (CNSC) algorithm to  find the correlated node set for a given node. After that, they proposed a High Residual Energy  First (HREF) node selection algorithm to minimize the number of active nodes so as to prolong the network lifetime. X. Liu et al.~\cite{ref143} explained that in some applications of WSNs such as structural health monitoring (SHM) and volcano monitoring, the traditional coverage model which is a geographic area defined for individual sensors is not always valid. For this reason, they define a generalized area coverage model, which is not need to have the coverage area of individual nodes, but only based on a function to determine whether a set of sensor nodes is capable of satisfy the requested monitoring task for a certain area. They have proposed two approaches to dividing the deployed nodes into suitable cover sets, which can be used to prolong the network lifetime. 
  
+  
 Various centralized  methods  based on column generation approaches have also been proposed in~\cite{ref120,ref121,ref122}.
 
 
