Update by Ali

[ThesisAli.git] / CHAPITRE_02.tex

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
old mode 100644 (file)
new mode 100755 (executable)
index 130fd0b..7b56933
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -9,13 +9,14 @@
 
 \section{Introduction}
 \label{ch2:sec:01}
 
 \section{Introduction}
 \label{ch2:sec:01}

-The main objective of deploying a large number of wireless sensor nodes in the target area of interest is to construct a WSN, which is responsible for monitoring and observation the sensing field, and detecting the required important event in the area of interest. The coverage problem represents the principle requirement in these applications. The main question that shared by these applications is how can the deployed wireless sensor nodes monitor the physical phenomenon properly. The coverage can be considered as one of the QoS (Quality of Service) parameters, and it is closely related with energy consumption. It represents the sensing task supplied by the wireless sensors in WSNs. 
+The main objective of deploying a large number of wireless sensor nodes in the target area of interest is to construct a WSN, which is responsible for monitoring and observation the sensing field, and detecting the required important event in the area of interest. The coverage problem represents the principle requirement in these applications. The main question that shared by these applications is how can the deployed wireless sensor nodes monitor the physical phenomenon properly. The coverage can be considered as one of the QoS (Quality of Service) parameters, and it is closely related to energy consumption. It represents the sensing task supplied by the wireless sensors in WSNs. 

 
 

-The energy resource limitation of wireless sensor nodes have been considered as a big challenge in order to operate the WSN with less energy consumption, while fulfill the coverage requirement. The the main objective of scattering the wireless sensor nodes over the area of interest is to collect the sensed data of the physical phenomena for processing or reporting, where there are two types of reporting for sensed data in WSNs~\cite{ref138} like event-driven and on-demand. In the latter, the monitoring base station start the reporting operation by transmitting a request to the wireless sensor nodes so as to send their sensed data to the base station, for example, the inventory tracking application. In the former, the reporting operation is triggered by one or more wireless sensor nodes within the physical phenomena by transmitting their sensed data to the controlling base station, for instance, the forest-fire detection application. The hybrid scheme of the two types is more flexible. 

 
 

-The ultimate goal of the coverage is to assure that each point in the sensing field is within the sensing range of at least one sensor node. There are some applications require high reliability to perform their tasks, so they need that every point in the sensing field is covered by more than one sensor node. In order to avoid the lack in monitoring the area of interest, it is necessary that the WSN are deployed with high density so as to exploit the overlapping among the sensor nodes and to prevent malfunction of sensor nodes in severe environments. The overlap can be exploited by choosing the minimum number of sensor nodes to perform the main tasks of the WSN in the sensing field and putting the rest sensor nodes in very low power sleep mode so as to prolong the network lifetime. This exploitation manner is called sensor activity scheduling that aims to set the activity state of each sensor node in the WSN so that the sensing field can be monitored for a long time as possible. The required level of coverage should be guaranteed by the activity based scheduling scheme~\cite{ref139}. There are many scheduling algorithms have been described in~\cite{ref58,ref57}.
+The energy resource limitation of wireless sensor nodes has been considered as a big challenge in order to operate the WSN with less energy consumption whilst fulfill the coverage requirement. The main objective of scattering the wireless sensor nodes over the area of interest is to collect the sensed data of the physical phenomena for processing or reporting, where there are two types of reporting for sensed data in WSNs~\cite{ref138} like event-driven and on-demand. In the latter, the monitoring base station start the reporting operation by transmitting a request to the wireless sensor nodes so as to send their sensed data to the base station; for example, the inventory tracking application. In the former, the reporting operation is triggered by one or more wireless sensor nodes within the physical phenomena by transmitting their sensed data to the controlling base station; for instance, the forest fire detection application. The hybrid scheme of the two types is more flexible. 

 
 

-This dissertation focuses on the problem of covering the area of interest  as long as  possible. There are several proposed approches to extend the network lifetime, while maintaing the coverage have been syrvayed in this chapter.  M. Cardei and J. Wu~\cite{ref113} have been surveyed the different coverage formulation models and their assumptions, as well as the solutions provided. In~\cite{ref105}, several coverage problems are presented from different angles, where the models and assumptions as well as proposed solutions in the literatures are described. In this dissertation, the main contribution of previous works that deal with  the coverage problem have been addressed. We end this chapter by focusing on two algorithms, GAF~\cite{GAF} and DESK~\cite{DESK}, since they have been used for comparisons against our coverage protocols.
+The ultimate goal of the coverage is to assure that each point in the sensing field is within the sensing range of at least one sensor node. Some applications require high reliability to perform their tasks, so they need that every point in the sensing field is covered by more than one sensor node. In order to avoid the lack in monitoring the area of interest, it is necessary that the WSN are deployed with high density so as to exploit the overlapping among the sensor nodes and to prevent malfunction of sensor nodes in severe environments. The overlap can be exploited by choosing the minimum number of sensor nodes to perform the main tasks of the WSN in the sensing field and putting the rest sensor nodes in very low power sleep mode so as to prolong the network lifetime. This exploitation manner is called sensor activity scheduling that aims to set the activity state of each sensor node in the WSN so that the sensing field can be monitored for a long time as possible. The required level of coverage should be guaranteed by the activity-based scheduling scheme~\cite{ref139}. Many scheduling algorithms have been described in~\cite{ref58,ref57}.
+
+This dissertation focuses on the problem of covering the area of interest  as long as  possible. Several proposed approaches to extend the network lifetime whilst maintaining the coverage have been viewed in this chapter.  M. Cardei and J. Wu~\cite{ref113} have been surveyed the different coverage formulation models and their assumptions, as well as the solutions provided. In~\cite{ref105}, several coverage problems are presented from different angles, where the models and assumptions, as well as proposed solutions in the literatures, are described. In this dissertation, the main contribution of previous works that deal with  the coverage problem have been addressed. We end this chapter by focusing on two algorithms, GAF~\cite{GAF} and DESK~\cite{DESK}, since they have used for comparison against our coverage protocols.

 
 
 \section{Coverage Algorithms} 
 
 
 \section{Coverage Algorithms} 


@@ -38,47 +39,41 @@ in WSNs. Cardei and Wu~\cite{ref113} provide a taxonomy for coverage algorithms
 The choice of non-disjoint or disjoint cover sets (sensors participate or not in many cover sets), coverage type ( area, target, or barrier), coverage ratio, coverage degree (how many sensors are required to cover a target or an area) can be added to the above list.
 
 
 The choice of non-disjoint or disjoint cover sets (sensors participate or not in many cover sets), coverage type ( area, target, or barrier), coverage ratio, coverage degree (how many sensors are required to cover a target or an area) can be added to the above list.
 
 

-Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. Many centralized algorithms and distributed algorithms for activity scheduling have been proposed in the literature, and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near optimal) solution based only on local information. Several algorithms to retain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref153,ref103,ref105}. Table~\ref{Table1:ch2} summarized the main characteristics of some coverage approaches in previous literatures.
+Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. Many centralized and distributed algorithms for activity scheduling have been proposed in the literature and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and the only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near-optimal) solution based only on local information. Several algorithms to retain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref101,ref103,ref105}. Table~\ref{Table1:ch2} summarized the main characteristics of some coverage approaches in previous literatures.

 
 
 \subsection{Centralized Algorithms}
 \label{ch2:sec:03}
 
 
 \subsection{Centralized Algorithms}
 \label{ch2:sec:03}

-The major approach is to divide/organize the sensors into a suitable number of cover sets where  each set completely covers an interest region and to activate these cover sets successively. The centralized algorithms always provide nearly or close  to optimal solution since the  algorithm has global view  of the whole network. Note that  centralized algorithms have the advantage  of requiring very low  processing  power from  the  sensor  nodes,  which  usually  have  limited processing  capabilities. The main drawback of this kind of approach is its higher cost in communications, since the node that will make the decision needs information from all the sensor nodes. Moreover, centralized approaches usually suffer from the scalability problem, making them less competitive as the network size increases.
+The major approach is to divide/organize the sensors into a suitable number of cover sets, where each set completely covers an interest region and to activate these cover sets successively. The centralized algorithms always provide nearly or close to the optimal solution since the algorithm has a global view of the whole network. Note that  centralized algorithms have the advantage of requiring very low  processing  power from  the sensor nodes,  which  usually have limited processing  capabilities. The main drawback of this kind of approach is its higher cost in communications, since the node that will make the decision needs information from all the sensor nodes. Moreover, centralized approaches usually suffer from the scalability problem, making them less competitive as the network size increases.
+

 
 The first algorithms proposed in the literature consider that the cover sets are disjoint: a sensor  node  appears  in  exactly one of the generated cover sets~\cite{ref114,ref115,ref116}. 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.
     
 
 The first algorithms proposed in the literature consider that the cover sets are disjoint: a sensor  node  appears  in  exactly one of the generated cover sets~\cite{ref114,ref115,ref116}. 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 lifetime of the network.  
+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 geometric-based activity scheduling scheme, named GAS, to fully cover the target area in WSNs. The authors deals with 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.
+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 in the WSN, 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 a NP-hard problem. So, a heuristic algorithm of NCG with time complexity of $O(n^3)$ is proposed.
+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.
 
 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 spacial 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.  
+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, 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.
+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.
+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.
 
 
 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 in 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 adjancy 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 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 divide the deployed nodes into suitable cover sets, which can be used to prolong the network lifetime. 
+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. 

  
  

-Various centralized  methods  based on column generation approaches have also been proposed~\cite{ref120,ref121,ref122}.
-
+Various centralized  methods  based on column generation approaches have also been proposed in~\cite{ref120,ref121,ref122}.

 
 
 
 
 
 


@@ -86,12 +81,12 @@ Various centralized  methods  based on column generation approaches have also be
 \label{ch2:sec:04}
 
 In distributed and localized coverage  algorithms, the required  computation to schedule the  activity of  sensor nodes  will be done  by the  cooperation among neighboring nodes. These  algorithms may require more computation  power for the processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers.
 \label{ch2:sec:04}
 
 In distributed and localized coverage  algorithms, the required  computation to schedule the  activity of  sensor nodes  will be done  by the  cooperation among neighboring nodes. These  algorithms may require more computation  power for the processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers.

-Many distributed algorithms have been  developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref129}. 
+Many distributed algorithms have been  developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref97}. 

 
 

-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}. 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 the 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.  
+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}. 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 the 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.  

 
 Cho et al.~\cite{ref145} proposed a distributed node scheduling protocol, which can retain sensing coverage needed by applications
 
 Cho et al.~\cite{ref145} proposed a distributed node scheduling protocol, which can retain sensing coverage needed by applications

-and increase 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 and by compute it's ESA can be determine whether it will be active or sleep. The suggested  work permits to sensor nodes to be in sleep mode opportunistically whilst fulfill the needed sensing coverage.
+and increase 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 and by computing its ESA can determine whether it will be active or sleep. The suggested  work permits to sensor nodes to be in sleep mode opportunistically whilst fulfill the needed sensing coverage.

 
 In~\cite{ref146}, the authors defined a maximum sensing coverage region problem (MSCR) in WSNs and then proposed a distributed algorithm to solve it. The
 maximum observed area fully covered by a minimum active sensors. In this work, the major property is to getting rid from the redundant sensors  in high-density WSNs and putting them in sleep mode, and choosing a smaller number of active sensors so as to be sure  that the full area is k-covered, and all events appeared in that area can be precisely and timely detected. This algorithm minimized the total energy consumption and increased the lifetime.
 
 In~\cite{ref146}, the authors defined a maximum sensing coverage region problem (MSCR) in WSNs and then proposed a distributed algorithm to solve it. The
 maximum observed area fully covered by a minimum active sensors. In this work, the major property is to getting rid from the redundant sensors  in high-density WSNs and putting them in sleep mode, and choosing a smaller number of active sensors so as to be sure  that the full area is k-covered, and all events appeared in that area can be precisely and timely detected. This algorithm minimized the total energy consumption and increased the lifetime.


@@ -102,8 +97,16 @@ The works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, dist
 
 Shibo et al.~\cite{ref137} have expressed the coverage problem as a  minimum  weight submodular set cover problem  and proposed 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. 
 
 
 Shibo et al.~\cite{ref137} have expressed the coverage problem as a  minimum  weight submodular set cover problem  and proposed 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. 
 

+In \cite{ref160}  authors  transform the  area  coverage  problem to  the  target
+coverage one taking into account the  intersection points among disks of sensors
+nodes or between disk of sensor nodes and boundaries.
+

 
 

-In \cite{ref84}, Xu et al. have described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses geographic location information to divide the area of interest into fixed square grids. Within each grid, it keeps only one node staying awake to take the responsibility of sensing and communication. Figure~\ref{gaf1} gives an example of fixed square grid in GAF.
+In \cite{ref133} authors prove  that  if  the perimeters  of sensors are sufficiently  covered it will be  the case for the  whole area. They provide an algorithm in $O(nd~log~d)$  time to compute the perimeter coverage of
+each  sensor,  where  $d$  denotes  the  maximum  number  of  sensors  that  are neighboring  to  a  sensor and  $n$  is  the  total  number of  sensors  in  the network.
+
+
+In \cite{GAF}, Xu et al. have described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses geographic location information to divide the area of interest into fixed square grids. Within each grid, it keeps only one node staying awake to take the responsibility of sensing and communication. Figure~\ref{gaf1} gives an example of fixed square grid in GAF.

 
 \begin{figure}[h!]
 \centering
 
 \begin{figure}[h!]
 \centering


@@ -112,7 +115,7 @@ In \cite{ref84}, Xu et al. have described an algorithm, called Geographical Adap
 \label{gaf1}
 \end{figure}
 
 \label{gaf1}
 \end{figure}
 

-The fixed grid is defined where, each two adjacent grids, for example, A and B in figure\ref{gaf1}, all the sensor nodes inside A can communicate with sensor nodes inside B and vice versa. Therefore, all the sensor nodes are equivalent from point of view the routing. The size of the fixed grid is based on the radio communication range $R_c$. It is supposed that the fixed grid is square with $r$ units on a side as shown in figure~\ref{gaf1}. The distance between the farthest two possible sensor nodes in two adjacent grid such as, B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$ so as to satisfy the definition of fixed square grid. For instance, the sensor node \textbf{2} of grid B can communicates with the sensor node \textbf{5} of grid C. So, 
+The fixed grid is defined where, each two adjacent grids, for example, A and B in figure\ref{gaf1}, all the sensor nodes inside A can communicate with sensor nodes inside B and vice versa. Therefore, all the sensor nodes are equivalent from the point of view the routing. The size of the fixed grid is based on the radio communication range $R_c$. It is supposed that the fixed grid is square with $r$ units on a side as shown in figure~\ref{gaf1}. The distance between the farthest two possible sensor nodes in two adjacent grid such as, B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$ so as to satisfy the definition of fixed square grid. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of grid C. So, 

 
 \begin{eqnarray}
 r^2 + \left(2r \right)^2 \leq R_c^2 
 
 \begin{eqnarray}
 r^2 + \left(2r \right)^2 \leq R_c^2 


@@ -122,7 +125,7 @@ or
 r \leq \dfrac{R_c}{\sqrt{5}} 
 \end{eqnarray}
 
 r \leq \dfrac{R_c}{\sqrt{5}} 
 \end{eqnarray}
 

-The sensor nodes in GAF can be in one of three states: active, sleep, or discovery. Figure~\ref{gaf2} shows the state transition diagram. Each sensor node is initiated with discovery state. In discovery state, the radio of each sensor node is turned on after that the discovery messages are exchanged among the sensor nodes so as to discover the other nodes within the same grid. The discovery message consisted of four fields like, node id, grid id, estimated node active time (enat), and node state. The node use its location and grid size to determine the grid id.   
+The sensor nodes in GAF can be in one of the three states: active, sleep, or discovery. Figure~\ref{gaf2} shows the state transition diagram. Each sensor node is initiated with discovery state. In discovery state, the radio of each sensor node is turned on after that the discovery messages are exchanged among the sensor nodes so as to discover the other nodes within the same grid. The discovery message consisted of four fields like, node id, grid id, estimated node active time (enat), and node state. The node uses its location and grid size to determine the grid id.   

 
 \begin{figure}[h!]
 \centering
 
 \begin{figure}[h!]
 \centering


@@ -131,10 +134,10 @@ The sensor nodes in GAF can be in one of three states: active, sleep, or discove
 \label{gaf2}
 \end{figure}
 
 \label{gaf2}
 \end{figure}
 

-The sensor node sets a timer to $T_d$ seconds after entering in discovery state. As soon as the timer fires, the sensor node broadcast its discovery message and enters in active state. The active sensor node sets a timeout value $T_a$ to define how long it can stay in active state. After $T_a$, the sensor node will return to the discovery state. Whilst, during its active state, it re-broadcasts its discovery message at intervals $T_d$ periodically. The sensor node with discovery or active state can change its state to sleep when it detects that some other equivalent node will handle routing inside the grid. The sensor nodes in the sleeping state wake up after a sleeping time $T_s$ and go back to the discovery state. In GAF, load balancing is performed by means of periodic election of the leader (i.e., the active node that handle the routing inside the fixed grid). A rank-based election algorithm has been used to elect the leader. It is based on the remaining energy of sensor nodes inside the fixed square grid so as to extend the network lifetime In proportionally with network density.
+The sensor node sets a timer to $T_d$ seconds after entering in the discovery state. As soon as the timer fires, the sensor node broadcast its discovery message and enters the active state. The active sensor node sets a timeout value $T_a$ to define how long it can stay in the active state. After $T_a$, the sensor node will return to the discovery state. Whilst, during its active state, it re-broadcasts its discovery message at intervals $T_d$ periodically. The sensor node with discovery or active state can change its state to sleep when it detects that some other equivalent node will handle routing inside the grid. The sensor nodes in the sleeping state wake up after a sleeping time $T_s$ and go back to the discovery state. In GAF, load balancing is performed by means of periodic election of the leader (i.e., the active node that handle the routing inside the fixed grid). A rank-based election algorithm has been used to elect the leader. It is based on the remaining energy of sensor nodes inside the fixed square grid so as to extend the network lifetime In proportionally with network density.

 
 
 
 

-In~\cite{ref132}, the author have designed a novel distributed heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), which  ensures that the energy consumption  among the sensors is balanced  and the lifetime  maximized  while  the coverage  requirement  is maintained. This heuristic  works in  rounds, requires  only  one-hop neighbor information, and each  sensor decides its status (active or  sleep) based on the perimeter coverage model from~\cite{ref133}. Figure~\ref{desk} shows the DESK network time line.
+In~\cite{DESK}, the author have designed a novel distributed heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), which  ensures that the energy consumption  among the sensors is balanced  and the lifetime  maximized  while  the coverage  requirement  is maintained. This heuristic  works in  rounds, requires  only  one-hop neighbor information, and each  sensor decides its status (active or  sleep) based on the perimeter coverage model from~\cite{ref133}. Figure~\ref{desk} shows the DESK network time line.

 
 \begin{figure}[h!]
 \centering
 
 \begin{figure}[h!]
 \centering


@@ -143,7 +146,7 @@ In~\cite{ref132}, the author have designed a novel distributed heuristic, called
 \label{desk}
 \end{figure}
 
 \label{desk}
 \end{figure}
 

-DESK works into rounds manner. The network lifetime divided into R rounds. Each round consists of two phases: decision phase and sensing phase. The length of round is dRound that means each sensor node executes this algorithm every dRound unit of time. The decision phase at the starting of each round should be taken within W unit of time, where $W<< dRound$ as shown in figure~\ref{desk}. All the sensor nodes should be temporarily wake up in the decision phase so as to decide its status. Every sensor node $s_i$ decides its status to be active or sleep after $w_i$ of waiting time. The waiting time $w_i$ is dynamic and it can be changed at any time based on the status of its sensor neighbors, the remaining energy of $s_i$, and its contribution $c_i$ in the coverage level of the network, where $c_i$ is defined as the number of the neighbors $n_i$ who need $s_i$ to be active. The waiting time has been defined as follow:
+DESK works into rounds manner. The network lifetime divided into R rounds. Each round consists of two phases: decision phase and sensing phase. The length of round is dRound that means each sensor node executes this algorithm every dRound unit of time. The decision phase at the starting of each round should be taken within W unit of time, where $W<< dRound$ as shown in figure~\ref{desk}. All the sensor nodes should be temporarily wake up in the decision phase so as to decide its status. Every sensor node $s_i$ decides its status to be active or sleep after $w_i$ of waiting time. The waiting time $w_i$ is dynamic and it can be changed at any time based on the status of its sensor neighbors, the remaining energy of $s_i$, and its contribution $c_i$ in the coverage level of the network, where $c_i$ is defined as the number of the neighbors $n_i$ who need $s_i$ to be active. The waiting time has been defined as follow

 
 \begin{equation}
 w_{i} = \left \{ 
 
 \begin{equation}
 w_{i} = \left \{ 


@@ -159,7 +162,7 @@ Where: $\alpha, \beta,$ and $\eta$ are constants, z is a random number between [
 
 Typically, the algorithm works as follows: all the sensor nodes collect the information (coordinates, current residual energy, and sensing range) from the one-hop neighbors and store it in a list L (in the increasing order) by executing the perimeter coverage model. Each sensor node set its timer to $w_i$ and initially it is proposed that all of its neighbors need it to join the
 network. When the sensor node $s_j$ joins the network,  it broadcasts a mACTIVATE message to inform all of its 1-hop neighbors about its status change. Its neighbors execute the perimeter coverage model to recalculate its coverage level. If it finds any neighbor u that is useless in covering its perimeter, i.e., the perimeter that u covers was covered by other active neighbors, it will send mASK2SLEEP message to that sensor. When the sensor node receives  mASK2SLEEP message, it updates its counter $n_i$, contribution $c_i$ and recalculate waiting time $w_i$. It then
 
 Typically, the algorithm works as follows: all the sensor nodes collect the information (coordinates, current residual energy, and sensing range) from the one-hop neighbors and store it in a list L (in the increasing order) by executing the perimeter coverage model. Each sensor node set its timer to $w_i$ and initially it is proposed that all of its neighbors need it to join the
 network. When the sensor node $s_j$ joins the network,  it broadcasts a mACTIVATE message to inform all of its 1-hop neighbors about its status change. Its neighbors execute the perimeter coverage model to recalculate its coverage level. If it finds any neighbor u that is useless in covering its perimeter, i.e., the perimeter that u covers was covered by other active neighbors, it will send mASK2SLEEP message to that sensor. When the sensor node receives  mASK2SLEEP message, it updates its counter $n_i$, contribution $c_i$ and recalculate waiting time $w_i$. It then

-check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e., it receives mASK2SLEEP message from all of its neighbors), then it will send message mGOSLEEP to all of its neighbors telling them that it is about to go to sleep, and set a timer $R_i$ for waking up in next round, and at last go to sleep. If the sensor node receives  mGOSLEEP message, it removes the neighbor sending that message out of its list L.
+check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e., it receives mASK2SLEEP message from all of its neighbors), then it will send message mGOSLEEP to all of its neighbors telling them that it is about to go to sleep, and set a timer $R_i$ for waking up in next round and at last go to sleep. If the sensor node receives  mGOSLEEP message, it removes the neighbor sending that message out of its list L.

 
 
 
 
 
 


@@ -210,9 +213,9 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 
 & \tiny K. Deschinkel et al. (2012)~\cite{ref122} &  & \OK  &   & \OK &  &  & \OK &  & \OK & \OK &  &  &\\
 
 
 & \tiny K. Deschinkel et al. (2012)~\cite{ref122} &  & \OK  &   & \OK &  &  & \OK &  & \OK & \OK &  &  &\\
 

-\rot{\rlap{Some Proposed Coverage Protocols in previous literatures}}

 
 

-& \tiny  A. Gallais et al. (2006)~\cite{ref123} & \OK & & \OK & &  & \OK & \OK &  & \OK &  & \OK & \OK &\\
+
+& \tiny  A. Gallais et al. (2008)~\cite{ref123} & \OK & & \OK & &  & \OK & \OK &  & \OK &  & \OK & \OK &\\

 
 & \tiny  D. Tian and N. D. Georganas (2002)~\cite{ref124} & \OK & & \OK & & & & \OK & & \OK & & \OK &  &\\
 
 
 & \tiny  D. Tian and N. D. Georganas (2002)~\cite{ref124} & \OK & & \OK & & & & \OK & & \OK & & \OK &  &\\
 


@@ -226,16 +229,20 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 
 & \tiny  S. K. Prasad and A. Dhawan (2007)~\cite{ref128} & \OK & &  & \OK & & & \OK &  & \OK &  & \OK &  &\\
 
 
 & \tiny  S. K. Prasad and A. Dhawan (2007)~\cite{ref128} & \OK & &  & \OK & & & \OK &  & \OK &  & \OK &  &\\
 

-& \tiny  S. Misra et al. (2011)~\cite{ref129} & \OK &   & \OK &  &  &  & \OK &  & \OK &  &  &  &\\
+& \tiny  S. Misra et al. (2011)~\cite{ref97} & \OK &   & \OK &  &  &  & \OK &  & \OK &  &  &  &\\

 
 & \tiny  P. Berman et al. (2005)~\cite{ref130}  & \OK & \OK & \OK &  &  &  & \OK &  & \OK & \OK &  &\\
 
 & \tiny  J. Lu and T. Suda (2003)~\cite{ref131} & \OK &   &  \OK &   &  &  & \OK &  & \OK &  & \OK &  &\\
 
 
 & \tiny  P. Berman et al. (2005)~\cite{ref130}  & \OK & \OK & \OK &  &  &  & \OK &  & \OK & \OK &  &\\
 
 & \tiny  J. Lu and T. Suda (2003)~\cite{ref131} & \OK &   &  \OK &   &  &  & \OK &  & \OK &  & \OK &  &\\
 

+
+

 & \tiny  J. Cho et al. (2007)~\cite{ref145}  & \OK &   &  \OK &   &  &  & \OK &  & \OK &  &  &  &\\
 
 & \tiny  V. T. Quang and T. Miyoshi (2008)~\cite{ref146}  & \OK &   & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\
 
 & \tiny  J. Cho et al. (2007)~\cite{ref145}  & \OK &   &  \OK &   &  &  & \OK &  & \OK &  &  &  &\\
 
 & \tiny  V. T. Quang and T. Miyoshi (2008)~\cite{ref146}  & \OK &   & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\
 

+\rot{\rlap{Some Proposed Coverage Protocols in previous literatures}} 
+

 & \tiny  D. Dong et al. (2012)~\cite{ref149}  & \OK &  & \OK &  &  &  & \OK &  & \OK &  & \OK &  &\\
 
 & \tiny  B. Wang et al. (2012)~\cite{ref134}  & \OK &  & \OK &  &  &  & \OK &  & \OK &  & \OK &  &\\
 & \tiny  D. Dong et al. (2012)~\cite{ref149}  & \OK &  & \OK &  &  &  & \OK &  & \OK &  & \OK &  &\\
 
 & \tiny  B. Wang et al. (2012)~\cite{ref134}  & \OK &  & \OK &  &  &  & \OK &  & \OK &  & \OK &  &\\


@@ -244,11 +251,15 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 
 & \tiny  L. Zhang et al. (2013)~\cite{ref136} & \OK &   & \OK &   &  & \OK & \OK &  & \OK &  & \OK &  &\\
 
 
 & \tiny  L. Zhang et al. (2013)~\cite{ref136} & \OK &   & \OK &   &  & \OK & \OK &  & \OK &  & \OK &  &\\
 

-& \tiny   S. He et al. (2012)~\cite{ref137}   & \OK & \OK  & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
+& \tiny  S. He et al. (2012)~\cite{ref137}   & \OK & \OK  & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
+
+& \tiny  Y. Xu et al. (2001)~\cite{GAF}   & \OK &   & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\

 
 

-& \tiny  Y. Xu et al. (2001)~\cite{ref84}   & \OK &   & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
+& \tiny  C. Vu et al. (2006)~\cite{DESK}  & \OK &   & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\

 
 

-& \tiny  C. Vu et al. (2006)~\cite{ref132}  & \OK &   & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\
+& \tiny  X. Deng et al. (2012)~\cite{ref160}  & \OK &   & \OK &  &  &  & \OK &  & \OK &  &  &  &\\
+
+& \tiny  X. Deng et al. (2005)~\cite{ref133}  & \OK &   & \OK &  & \OK &  & \OK &  & \OK &  &  &  &\\

 
 &\textbf{\textcolor{red}{ \tiny DiLCO Protocol (2014)}}                  &  \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}}   &   &   & \textbf{\textcolor{red}{\OK}}  & \textbf{\textcolor{red}{\OK}}   &   &  &   &\textbf{\textcolor{red}{\OK}}  &    &  \\
 
 
 &\textbf{\textcolor{red}{ \tiny DiLCO Protocol (2014)}}                  &  \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}}   &   &   & \textbf{\textcolor{red}{\OK}}  & \textbf{\textcolor{red}{\OK}}   &   &  &   &\textbf{\textcolor{red}{\OK}}  &    &  \\
 


@@ -267,13 +278,13 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 
 
 
 
 
 

+

 \section{Conclusion}
 \label{ch2:sec:05}
 This chapter has been described some coverage problems proposed in the literature, and their assumptions and proposed solutions.
 \section{Conclusion}
 \label{ch2:sec:05}
 This chapter has been described some coverage problems proposed in the literature, and their assumptions and proposed solutions.

-The coverage problem has been considered an essential requirement for many applications in WSNs, because better
-coverage of an area of interest provides better sensing measurements of the physical phenomenon. So, there are many extensive researches have been focused on those problem. These researches have been aiming at designing mechanisms that efficiently manage or schedule the sensors after deployment, since sensor nodes have a limited battery life.
-In spite of many energy-efficient protocols for maintaining the coverage and improving the network lifetime in WSNs were proposed, non 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 a full centralized algorithms, an 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, so, the  full centralized approaches are not good candidate to use it especially in large WSNs. Whilst, a full distributed algorithms can not give optimal solutions because this 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
-
+The coverage problem has been considered an essential requirement for many applications in WSNs because the better
+coverage of an area of interest provides better sensing measurements of the physical phenomenon. So, many extensive researches have been focused on that problem. These researches have aimed at designing mechanisms that efficiently manage or schedule the sensors after deployment, since sensor nodes have a limited battery life.
+In spite of many energy-efficient protocols for maintaining the coverage and improving the network lifetime in WSNs were proposed, 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. 
 
 
 % 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.