Update by Ali

[ThesisAli.git] / CHAPITRE_02.tex

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index 0010116f97522789c69400b5a66e1d4a9bebaa4c..fdd5ded8fe412ddf56b28ac0c4ac19c02ae89d4d 100644 (file)
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -142,7 +142,7 @@ X. Deng et al. \cite{ref133} formulate the area coverage problem as a decision p
 
 Distributed  algorithms typically operate in rounds for a predetermined duration. At the beginning of each  round, a sensor exchanges information with its neighbors and makes a  decision to either remain turned on or  to go to sleep for  the round. This decision is  basically made on simple greedy criteria like the largest uncovered area \cite{ref130} or maximum uncovered targets \cite{ref131}. 
 Cho et al.~\cite{ref145} propose a distributed node scheduling protocol, which can retain sensing coverage needed by applications and increases network lifetime via putting in sleep mode some redundant nodes. In this work, the Effective Sensing Area (ESA) concept of a sensor node is used, which refers to the sensing area that is not overlapping with another sensor's sensing area. A sensor node can determine whether it will be active or turned off by computing its ESA. The suggested work permits sensor nodes to be in sleep mode opportunistically whilst fulfilling the needed sensing coverage. 
 
 Distributed  algorithms typically operate in rounds for a predetermined duration. At the beginning of each  round, a sensor exchanges information with its neighbors and makes a  decision to either remain turned on or  to go to sleep for  the round. This decision is  basically made on simple greedy criteria like the largest uncovered area \cite{ref130} or maximum uncovered targets \cite{ref131}. 
 Cho et al.~\cite{ref145} propose a distributed node scheduling protocol, which can retain sensing coverage needed by applications and increases network lifetime via putting in sleep mode some redundant nodes. In this work, the Effective Sensing Area (ESA) concept of a sensor node is used, which refers to the sensing area that is not overlapping with another sensor's sensing area. A sensor node can determine whether it will be active or turned off by computing its ESA. The suggested work permits sensor nodes to be in sleep mode opportunistically whilst fulfilling the needed sensing coverage. 

-Bahi et al. \cite{ref236,ref237} propose a distributed localisation algorithm and a scheduling method to maintain the coverage and improve the network lifetime. They suggest a mobile beacon to divide the area of interest into unit squares using Hilbert space filling curve method.  They exploit the localization phase to construct sets of active nodes. They provide a local activity scheduling approach for the sensor nodes in the region to ensure the area coverage and to prolong the network lifetime. The experiment results show an improvement in the network lifetime due to reducing the energy consumed by the localisation and coverage algorithms. 
+J. M. Bahi et al. \cite{ref236,ref237} propose a distributed approach which consists of two steps: nodes localization and coverage scheduling. They suggest a mobile beacon to divide the area of interest into unit squares using Hilbert space filling curve method.  They exploit the localization phase to construct sets of active nodes. They provide a local activity scheduling approach for the sensor nodes to ensure the area coverage and to prolong the network lifetime. The experiment results show an improvement in the network lifetime using their proposed distributed approach. 

 The authors in~\cite{ref146} define a Maximum Sensing Coverage Region problem (MSCR) in WSNs and then propose a distributed algorithm to solve it. The maximum observed area is fully covered by a minimum active sensors. In this work, the major property is to get rid of the redundant sensors  in high-density WSNs and putting them in sleep mode. In addition,  a smaller number of active sensors is chosen so as to ensure the full area is k-covered, and all events appearing in that area can be precisely and timely detected. This algorithm minimizes the total energy consumption and increases the network lifetime. The Distributed  Adaptive Sleep  Scheduling  Algorithm (DASSA) \cite{ref127} does not require location information of sensors while  maintaining connectivity and  satisfying a user-defined coverage target. In DASSA, nodes use residual energy levels and feedback from the sink for scheduling the activity  of their neighbors. This feedback mechanism reduces the randomness  in scheduling  that would otherwise occur due to the absence of location information.
 A graph theoretical framework for connectivity-based area coverage with configurable coverage granularity is proposed~\cite{ref149}. A new coverage criterion and scheduling approach is proposed based on cycle partition. This method is able to build a sparse coverage set in distributed way by means of only connectivity information. This work only considers  that the communication range of the sensor is two times smaller than the sensing one. Shibo et al.~\cite{ref137} express the area coverage problem as a minimum  weight submodular set cover problem  and propose a Distributed Truncated Greedy Algorithm (DTGA) to solve it. They take  advantage from both temporal and spatial correlations between  data sensed by different sensors, and leverage prediction, to improve  the lifetime. The authors in \cite{ref160} design an energy-efficient approach to area coverage problems by transforming the area coverage problem to the target coverage problem taking into account the  intersection points among disks of sensors nodes or between disc of sensor nodes and boundaries. They propose two mechanisms for the converted target coverage problems to produce cover sets covering the sensing
 field completely. Simulations results show that this approach can prolong the lifetime of the network compared with other works.
 The authors in~\cite{ref146} define a Maximum Sensing Coverage Region problem (MSCR) in WSNs and then propose a distributed algorithm to solve it. The maximum observed area is fully covered by a minimum active sensors. In this work, the major property is to get rid of the redundant sensors  in high-density WSNs and putting them in sleep mode. In addition,  a smaller number of active sensors is chosen so as to ensure the full area is k-covered, and all events appearing in that area can be precisely and timely detected. This algorithm minimizes the total energy consumption and increases the network lifetime. The Distributed  Adaptive Sleep  Scheduling  Algorithm (DASSA) \cite{ref127} does not require location information of sensors while  maintaining connectivity and  satisfying a user-defined coverage target. In DASSA, nodes use residual energy levels and feedback from the sink for scheduling the activity  of their neighbors. This feedback mechanism reduces the randomness  in scheduling  that would otherwise occur due to the absence of location information.
 A graph theoretical framework for connectivity-based area coverage with configurable coverage granularity is proposed~\cite{ref149}. A new coverage criterion and scheduling approach is proposed based on cycle partition. This method is able to build a sparse coverage set in distributed way by means of only connectivity information. This work only considers  that the communication range of the sensor is two times smaller than the sensing one. Shibo et al.~\cite{ref137} express the area coverage problem as a minimum  weight submodular set cover problem  and propose a Distributed Truncated Greedy Algorithm (DTGA) to solve it. They take  advantage from both temporal and spatial correlations between  data sensed by different sensors, and leverage prediction, to improve  the lifetime. The authors in \cite{ref160} design an energy-efficient approach to area coverage problems by transforming the area coverage problem to the target coverage problem taking into account the  intersection points among disks of sensors nodes or between disc of sensor nodes and boundaries. They propose two mechanisms for the converted target coverage problems to produce cover sets covering the sensing
 field completely. Simulations results show that this approach can prolong the lifetime of the network compared with other works.


@@ -260,6 +260,7 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
         \multicolumn{2}{c}{\footnotesize Coverage Approach} & \mcrot{1}{l}{50}{\footnotesize Distributed} & \mcrot{1}{l}{50}{\footnotesize Centralized} & \mcrot{1}{l}{50}{ \footnotesize Area coverage} & \mcrot{1}{l}{50}{\footnotesize Target coverage} & \mcrot{1}{l}{50}{\footnotesize k-coverage} & \mcrot{1}{l}{50}{\footnotesize Heterogeneous nodes}& \mcrot{1}{l}{50}{\footnotesize Homogeneous nodes} & \mcrot{1}{l}{50}{\footnotesize Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize Non-Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize SET K-COVER } & \mcrot{1}{l}{50}{\footnotesize Work in Rounds or Periods}  & \mcrot{1}{l}{50}{\footnotesize Adjustable Radius}  \\
         \cmidrule[1pt]{2-14}
 
         \multicolumn{2}{c}{\footnotesize Coverage Approach} & \mcrot{1}{l}{50}{\footnotesize Distributed} & \mcrot{1}{l}{50}{\footnotesize Centralized} & \mcrot{1}{l}{50}{ \footnotesize Area coverage} & \mcrot{1}{l}{50}{\footnotesize Target coverage} & \mcrot{1}{l}{50}{\footnotesize k-coverage} & \mcrot{1}{l}{50}{\footnotesize Heterogeneous nodes}& \mcrot{1}{l}{50}{\footnotesize Homogeneous nodes} & \mcrot{1}{l}{50}{\footnotesize Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize Non-Disjoint sets} & \mcrot{1}{l}{50}{\footnotesize SET K-COVER } & \mcrot{1}{l}{50}{\footnotesize Work in Rounds or Periods}  & \mcrot{1}{l}{50}{\footnotesize Adjustable Radius}  \\
         \cmidrule[1pt]{2-14}
 

+& \tiny J. M. Bahi et al. (2008)~\cite{ref236,ref237}   & \OK  &  & \OK  &   &  &   & \OK &  \OK &  &  &  &  &\\

 
 %& \tiny Z. Abrams et al. (2004)~\cite{ref114}   & \OK &\OK & \OK &   &  &  &\OK & \OK &  & \OK &  &  &\\
 
 
 %& \tiny Z. Abrams et al. (2004)~\cite{ref114}   & \OK &\OK & \OK &   &  &  &\OK & \OK &  & \OK &  &  &\\
 


@@ -384,11 +385,6 @@ Many coverage algorithms for maintaining the coverage and improving the network
 
 
 
 
 
 

-%Many coverage algorithms for maintaining the coverage and improving the network lifetime in WSNs were proposed. On one hand, the centralized coverage algorithms provide optimal or near optimal solution with low computation power but they deplete the battery power due to the communication overhead, as well as they are not scalable for large size networks. On the other hand, the distributed coverage algorithms provide a lower quality solution in comparison with centralized approaches and consume more power for computation but they are reliable, scalable, and provide low communication overhead on the WSNs.   
- %none of them ensure the coverage for the sensing field with optimal minimum number of active sensor nodes, and for a long time as possible. In full centralized algorithms, the optimal solutions can be given by using optimization approaches, but in the same time, a high energy is consumed for the execution time of the algorithm and the communications among the sensors in the sensing field. Therefore, the  full centralized approaches are not a good candidate to be used especially in large WSNs. Whilst, a fully distributed algorithms can not give optimal solutions because these algorithms use only local information of the neighboring sensors, but in the same time, the energy consumption during the communications and executing the algorithm is highly lower. Whatever the case, this would result in a shorter lifetime coverage in WSNs
-
-
-% Several centralized approaches have been demonstrated, where they are concentrated on modeling the coverage problem and provide the maximum cover set so as to extend the network lifetime. The proposed algorithms are executed in a central node and based on global information. The central node transmits the resulted schedule to other nodes in the network. Even if the centralized algorithms have been produced optimal or near optimal solutions, It seems to be difficult and unpractical to apply the full centralized approaches in WSNs. On the other hand, many distributed algorithms have been described. These approaches seem to be more realistic to be used in WSNs from point of view of designer, but they can not assure optimal or near optimal solutions so as to extend the network lifetime as long time as possible.