Last update by Ali

[ThesisAli.git] / CHAPITRE_02.tex

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index 0010116f97522789c69400b5a66e1d4a9bebaa4c..43a86922b8ec0dd9b28c2b68aa834c36872f5cc4 100644 (file)
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -44,7 +44,7 @@ This chapter concentrates only on area coverage and target coverage problems bec
 This dissertation mainly focuses on the area coverage problem, where the ultimate goal is to choose the minimum number of sensor nodes to cover the whole sensing field. 
 %We have focused mainly on the area coverage problem. Therefore, we represent the sensing area of each sensor node in the sensing field as a set of  primary points and then achieving full area coverage by covering all the points in the sensing field. The ultimate goal of the area coverage problem is to choose the minimum number of sensor nodes to cover the whole sensing region and prolonging the lifetime of the WSN. 
 
 This dissertation mainly focuses on the area coverage problem, where the ultimate goal is to choose the minimum number of sensor nodes to cover the whole sensing field. 
 %We have focused mainly on the area coverage problem. Therefore, we represent the sensing area of each sensor node in the sensing field as a set of  primary points and then achieving full area coverage by covering all the points in the sensing field. The ultimate goal of the area coverage problem is to choose the minimum number of sensor nodes to cover the whole sensing region and prolonging the lifetime of the WSN. 
 

-Many centralized and distributed coverage algorithms for activity scheduling have been proposed in the literature, based on different assumptions and objectives. In centralized algorithms, a central controller (base station) makes all decisions and distributes the results to sensor nodes. The centralized algorithms have the advantage of requiring very low processing power from the sensor nodes (except for the base station) which have usually limited processing capabilities.  On the contrary, the exchange of packets in large WSNs may consume a considerable amount of energy in a centralized approach compared to a distributed one. The exchange of packets is between the sensor nodes and the base station. The centralized algorithms ensure nearly or close to optimal solution . They provide less redundant active sensor nodes during monitoring the sensing field. Moreover, centralized approaches usually suffer from the scalability and reliability problems, making them less competitive than the network size increases.
+Many centralized and distributed coverage algorithms for activity scheduling have been proposed in the literature, based on different assumptions and objectives. In centralized algorithms, a central controller (base station) makes all decisions and distributes the results to sensor nodes. The centralized algorithms have the advantage of requiring very low processing power from the sensor nodes (except for the base station) which have usually limited processing capabilities.  On the contrary, the exchange of packets in large WSNs may consume a considerable amount of energy in a centralized approach compared to a distributed one. The exchange of packets is between the sensor nodes and the base station. Centralized algorithms provide solutions  close to optimal solutions. They provide less redundant active sensor nodes during monitoring the sensing field. But, centralized approaches usually suffer from the scalability and reliability problems, making them less competitive when the network size increases. 

 
 In distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only informations from neighboring nodes are used for the activity decision. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give an optimal (or near-optimal) solution based only on local informations. They provide more redundant active sensor nodes during monitoring the sensing field. The exchange of packets is between the sensor nodes and their neighbors. Distributed algorithms are more robust against sensor failure.  Moreover, a recent study conducted in \cite{ref226} concludes that there is a threshold in terms of network size to switch from a distributed to a centralized algorithm. 
 
 
 In distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only informations from neighboring nodes are used for the activity decision. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give an optimal (or near-optimal) solution based only on local informations. They provide more redundant active sensor nodes during monitoring the sensing field. The exchange of packets is between the sensor nodes and their neighbors. Distributed algorithms are more robust against sensor failure.  Moreover, a recent study conducted in \cite{ref226} concludes that there is a threshold in terms of network size to switch from a distributed to a centralized algorithm. 
 


@@ -114,7 +114,7 @@ Y. Li et al.~\cite{ref142} present a framework with heuristic strategies to solv
 
 In the case of non-disjoint algorithms~\cite{ref117,ref167,ref144,ref147,ref118}, 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}. 
 
 In the case of non-disjoint algorithms~\cite{ref117,ref167,ref144,ref147,ref118}, 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}, address 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 in~\cite{ref148}, address 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 work in~\cite{ref144} addresses 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 explain that GAS is capable to monitor the target area by using the fewest number of sensors and it can produce as many cover sets as possible. A novel area coverage method to divide the sensors 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 those in the same group are supposed to be similar. They prove 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 a premature assumption that sensors near to each other sense similar data. 
 The problem of k-coverage  over the area of interest in WSNs is 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, four configuration protocols are proposed for treating the k-coverage in WSNs. Simulation results show that their protocols outperform an existing distributed k-coverage configuration protocol. The work presented in~\cite{ref151} solves 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 is generated in each round and based on this bitmap,  it is decided which sensors stay active or go to sleep. They check the connection of the graph via laplacian of the adjacency graph of active sensors in each round. They define the connected coverage problem as an optimization problem and a centralized genetic algorithm is used to find the solution. Recent studies show an increasing interest in the use of exact schemes to solve optimization problems in WSNs \cite{ref230,ref231,ref121,ref122,ref120}. Column Generation (CG) has been widely used to address different versions of Maximum-network Lifetime Problem (MLP). CG decomposes the problem into a Restricted Master Problem (RMP) and a Pricing Subproblem (PS). The former maximizes lifetime using an incomplete set of columns and the latter is used to identify new profitable columns.  
 %%%A. Rossi et al.~\cite{ref121} introduce an efficient implementation of a genetic algorithm based on CG to extend the lifetime and maximize target coverage in wireless sensor networks under bandwidth constraints. The authors show that the use of metaheuristic methods to solve PS in the context of CG allows to obtain optimal solutions quite fast and to produce high-quality solutions when the algorithm is stopped before returning an optimal solution. More recently, 
 %%%The work in~\cite{ref144} addresses 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 explain that GAS is capable to monitor the target area by using the fewest number of sensors and it can produce as many cover sets as possible. A novel area coverage method to divide the sensors 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 those in the same group are supposed to be similar. They prove 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 a premature assumption that sensors near to each other sense similar data. 
 The problem of k-coverage  over the area of interest in WSNs is 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, four configuration protocols are proposed for treating the k-coverage in WSNs. Simulation results show that their protocols outperform an existing distributed k-coverage configuration protocol. The work presented in~\cite{ref151} solves 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 is generated in each round and based on this bitmap,  it is decided which sensors stay active or go to sleep. They check the connection of the graph via laplacian of the adjacency graph of active sensors in each round. They define the connected coverage problem as an optimization problem and a centralized genetic algorithm is used to find the solution. Recent studies show an increasing interest in the use of exact schemes to solve optimization problems in WSNs \cite{ref230,ref231,ref121,ref122,ref120}. Column Generation (CG) has been widely used to address different versions of Maximum-network Lifetime Problem (MLP). CG decomposes the problem into a Restricted Master Problem (RMP) and a Pricing Subproblem (PS). The former maximizes lifetime using an incomplete set of columns and the latter is used to identify new profitable columns.  
 %%%A. Rossi et al.~\cite{ref121} introduce an efficient implementation of a genetic algorithm based on CG to extend the lifetime and maximize target coverage in wireless sensor networks under bandwidth constraints. The authors show that the use of metaheuristic methods to solve PS in the context of CG allows to obtain optimal solutions quite fast and to produce high-quality solutions when the algorithm is stopped before returning an optimal solution. More recently, 


@@ -122,7 +122,7 @@ The problem of k-coverage  over the area of interest in WSNs is addressed in~\ci
 
 More recently, 
 %%%the authors in~\cite{ref118} consider 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. 
 
 More recently, 
 %%%the authors in~\cite{ref118} consider 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}, formulate the problem of full grid area coverage problem using two integer linear programming models: the first, is in model that takes into account only the overall coverage constraint; the second, both the connectivity and the full grid coverage constraints are taken into consideration. This work does not consider the energy constraint. H. Cheng et al.~\cite{ref119} define 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 introduce  a new Correlated Node Set Computing (CNSC) algorithm to  find the correlated node set for a given node. After that, they propose a High Residual Energy  First (HREF) node selection algorithm to minimize the number of active nodes. X. Liu et al.~\cite{ref143} explain 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 required to have the coverage area of individual nodes, but only based on a function deciding whether a set of sensor nodes is capable of satisfy the requested monitoring task for a certain area. They propose two approaches for dividing the deployed nodes into suitable cover sets.
+M. Rebai et al.~\cite{ref141}, formulate the problem of full grid area coverage problem using two integer linear programming models: the first, is a model that takes into account only the overall coverage constraint; the second, both the connectivity and the full grid coverage constraints are taken into consideration. This work does not consider the energy constraint. H. Cheng et al.~\cite{ref119} define 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 introduce  a new Correlated Node Set Computing (CNSC) algorithm to  find the correlated node set for a given node. After that, they propose a High Residual Energy  First (HREF) node selection algorithm to minimize the number of active nodes. X. Liu et al.~\cite{ref143} explain 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 required to have the coverage area of individual nodes, but only based on a function deciding whether a set of sensor nodes is capable of satisfy the requested monitoring task for a certain area. They propose two approaches for dividing the deployed nodes into suitable cover sets.

 
 
   
 
 
   


@@ -142,14 +142,14 @@ 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 works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, distributed energy-efficient, and distributed clustering methods respectively, which aim at extending the network lifetime, while the coverage is ensured.
 
 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 works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, distributed energy-efficient, and distributed clustering methods respectively, which aim at extending the network lifetime, while the coverage is ensured.
 

-In this dissertation, we focus in more details on two distributed coverage algorithms: GAF and DESK, because we compared our proposed coverage optimization protocols with them during performance evaluation. GAF algorithm is chosen for comparison as a competitor because it is famous and easy to implement, as well as many authors referred to it in many publications. DESK algorithm is also selected as competitor in the comparison because it works into rounds fashion (network lifetime divides into rounds) similar to our approaches, as well as DESK is a full distributed coverage approach. 
+In this dissertation, we focus in more details on two distributed coverage algorithms: GAF and DESK, because we compared our proposed coverage optimization protocols with them during performance evaluation. GAF algorithm is chosen for comparison as a competitor because it is famous and easy to implement, as well as many authors referred to it in many publications. DESK algorithm is also selected as competitor in the comparison because it works into rounds fashion (network lifetime divided into rounds) similar to our approaches, as well as DESK is a full distributed coverage approach. 

  
 
 \subsection{Geographical Adaptive Fidelity (GAF)}
  
 
 \subsection{Geographical Adaptive Fidelity (GAF)}


@@ -164,7 +164,7 @@ GAF is developed by Xu et al. \cite{GAF}, it uses geographic location informatio
 \label{gaf1}
 \end{figure}
 
 \label{gaf1}
 \end{figure}
 

-For two adjacent squares grids, (for example, A and B in figure~\ref{gaf1}) all 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 sensor nodes in two adjacent squares, such as B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of square grid C. Thus, 
+For two adjacent squares grids, (for example, A and B in Figure~\ref{gaf1}) all 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 of 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 sensor nodes in two adjacent squares, such as B and C in Figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of square grid C. Thus, 

 
 
 \begin{eqnarray}
 
 
 \begin{eqnarray}


@@ -179,7 +179,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 the folling three states: Active, Sleeping, or Discovery. Figure~\ref{gaf2} shows the state transition diagram. Each sensor node is initiated with discovery state. 
+The sensor nodes in GAF can be in one of the following three states: Active, Sleeping, 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. Thereafter, the discovery messages are exchanged among the sensor nodes within the same grid. The discovery message consists of four fields, node id, grid id, estimated node active time (enat), and node state. The node uses its location and grid size to determine the square grid id.   
 
 \begin{figure}[h!]
 In discovery state, the radio of each sensor node is turned on. Thereafter, the discovery messages are exchanged among the sensor nodes within the same grid. The discovery message consists of four fields, node id, grid id, estimated node active time (enat), and node state. The node uses its location and grid size to determine the square grid id.   
 
 \begin{figure}[h!]


@@ -202,7 +202,7 @@ one sensor node (based on the remaining energy of sensor nodes inside the fixed
 DESK is a novel distributed heuristic to ensure that the energy consumption among the sensors is balanced  and the lifetime  maximized  while  the coverage  requirement is satisfied~\cite{DESK}. This heuristic  works in  rounds, it requires  only  one-hop neighbor information, and each  sensor decides its status (Active or  Sleep) based on the perimeter coverage model from~\cite{ref133}. 
 
 %DESK is based on the result from \cite{ref133}. 
 DESK is a novel distributed heuristic to ensure that the energy consumption among the sensors is balanced  and the lifetime  maximized  while  the coverage  requirement is satisfied~\cite{DESK}. This heuristic  works in  rounds, it requires  only  one-hop neighbor information, and each  sensor decides its status (Active or  Sleep) based on the perimeter coverage model from~\cite{ref133}. 
 
 %DESK is based on the result from \cite{ref133}. 

-In DESK \cite{ref133}, the whole area is K-covered if and only if the perimeters of all sensors are K-covered. The coverage level of a sensor $s_i$ is determined by calculating the angle corresponding to the arc that each of its neighbors covers its perimeter. Figure~\ref{figp}~(a) illuminates such arcs whilst Figure~\ref{figp}~(b) shows the angles corresponding with those arcs in the range [0,2$ \pi $]. According to figure~\ref{figp}~(a) and (b), the coverage level of sensor $s_i$ can be calculated as follows.
+In DESK \cite{ref133}, the whole area is K-covered if and only if the perimeters of all sensors are K-covered. The coverage level of a sensor $s_i$ is determined by calculating the angle corresponding to the arc that each of its neighbors covers its perimeter. Figure~\ref{figp}~(a) illuminates such arcs whilst Figure~\ref{figp}~(b) shows the angles corresponding with those arcs in the range [0,2$ \pi $]. According to Figure~\ref{figp}~(a) and (b), the coverage level of sensor $s_i$ can be calculated as follows.

 %via traversing the range from 0 to  2$ \pi $.
 For each sensor $s_j$ such that $d(s_i,s_j)$ $<$ $2R_s$, we calculate the angle of $s_i$'s arc, denoted by [$\alpha_{j,L}$, $\alpha_{j,R}$], which is perimeter covered by $s_j$, where $\alpha= arccos(d(s_i, s_j)/2R_s)$ and $d(s_i,s_j)$ is the Euclidean distance between $s_i$ and $s_j$. After that, we locate the points $\alpha_{j,L}$ and $\alpha_{j,R}$ of each neighboring sensor $s_j$ of $s_i$ on the line segment $[0, 2\pi]$. These points are sorted in ascending order into a list L. We traverse the line segment from 0 to $2\pi$ by visiting each element in the sorted list L from the left to the right and determine the perimeter coverage of $s_i$. Whenever an element $\alpha_{j,L}$ is traversed, the level of perimeter coverage should be increased by one. Whenever an element $\alpha_{j,R}$ is traversed, the level of perimeter coverage should be decreased by one. 
 
 %via traversing the range from 0 to  2$ \pi $.
 For each sensor $s_j$ such that $d(s_i,s_j)$ $<$ $2R_s$, we calculate the angle of $s_i$'s arc, denoted by [$\alpha_{j,L}$, $\alpha_{j,R}$], which is perimeter covered by $s_j$, where $\alpha= arccos(d(s_i, s_j)/2R_s)$ and $d(s_i,s_j)$ is the Euclidean distance between $s_i$ and $s_j$. After that, we locate the points $\alpha_{j,L}$ and $\alpha_{j,R}$ of each neighboring sensor $s_j$ of $s_i$ on the line segment $[0, 2\pi]$. These points are sorted in ascending order into a list L. We traverse the line segment from 0 to $2\pi$ by visiting each element in the sorted list L from the left to the right and determine the perimeter coverage of $s_i$. Whenever an element $\alpha_{j,L}$ is traversed, the level of perimeter coverage should be increased by one. Whenever an element $\alpha_{j,R}$ is traversed, the level of perimeter coverage should be decreased by one. 
 


@@ -234,7 +234,6 @@ w_{i} = \left \{
   \dfrac{\eta}{n_i^\alpha l(e_i,r_i)^\beta} * W + z & \mbox{if $e_i \geq e_{threshold}$} \\
   W & \mbox{otherwise,}\\
 \end{array} \right.
   \dfrac{\eta}{n_i^\alpha l(e_i,r_i)^\beta} * W + z & \mbox{if $e_i \geq e_{threshold}$} \\
   W & \mbox{otherwise,}\\
 \end{array} \right.

-%\label{eq12} 

 \notag
 \end{equation} 
 
 \notag
 \end{equation} 
 


@@ -260,6 +259,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 &  &  &\\
 


@@ -345,9 +345,9 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 
 & \tiny  X. Deng et al. (2005)~\cite{ref133}  & \OK &   & \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}{\OK}}  &    &  \\
+&\textbf{\textcolor{red}{ \tiny DiLCO Protocol (2015)}}                  &  \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}}   &   &   & \textbf{\textcolor{red}{\OK}}  & \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}} &   &\textbf{\textcolor{red}{\OK}}  &    &  \\

 
 

-&\textbf{\textcolor{red}{ \tiny MuDiLCO 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}{\OK}}  &\textbf{\textcolor{red}{\OK}}  &    &  \\
+&\textbf{\textcolor{red}{ \tiny MuDiLCO Protocol (2015)}}    &  \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}}   &   &   & \textbf{\textcolor{red}{\OK}}  & \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}} & \textbf{\textcolor{red}{\OK}}  &\textbf{\textcolor{red}{\OK}}  &    &  \\

 
 &\textbf{\textcolor{red}{ \tiny PeCO Protocol (2015)}}                  &  \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}}   &   &   & \textbf{\textcolor{red}{\OK}}  & \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}} &   &\textbf{\textcolor{red}{\OK}}  &    &  \\
 
 
 &\textbf{\textcolor{red}{ \tiny PeCO Protocol (2015)}}                  &  \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}}   &   &   & \textbf{\textcolor{red}{\OK}}  & \textbf{\textcolor{red}{\OK}}   &   & \textbf{\textcolor{red}{\OK}} &   &\textbf{\textcolor{red}{\OK}}  &    &  \\
 


@@ -365,7 +365,7 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 \label{ch2:sec:05}
 This chapter describes some coverage problems in the literature, with their assumptions and proposed solutions.
 The coverage is considered as an essential requirement for many applications in WSNs because the better the coverage of an area of interest is, the better the sensing measurements of the physical phenomenon also is. Therefore, many extensive researches have been focused on that problem. These researches aim at designing mechanisms that efficiently manage or schedule the sensors after deployment, since sensor nodes have a limited battery life.
 \label{ch2:sec:05}
 This chapter describes some coverage problems in the literature, with their assumptions and proposed solutions.
 The coverage is considered as an essential requirement for many applications in WSNs because the better the coverage of an area of interest is, the better the sensing measurements of the physical phenomenon also is. Therefore, many extensive researches have been focused on that problem. These researches aim at designing mechanisms that efficiently manage or schedule the sensors after deployment, since sensor nodes have a limited battery life.

-Many coverage algorithms for maintaining the coverage and improving the network lifetime in WSNs were proposed. On the one hand, the full centralized coverage algorithms provide optimal or near optimal solution with low computation power for the sensors (except for the base station) but they deplete the battery power due to the communication overhead, so 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 the communication between neighbors may be large especially for dense networks. Distributed coverage algorithms are reliable and scalable. The two coverage approaches has advantages and disadvantages. Therefore, each approach can be used based on the application requirements. We conclude from this chapter that it is desirable to introduce an hybrid approach to take into account the advantages of both centralized and distributed coverage approaches. Such an hybrid approach can provide a good quality coverage and prolong the network lifetime.
+Many coverage algorithms for maintaining the coverage and improving the network lifetime in WSNs were proposed. On the one hand, the full centralized coverage algorithms provide optimal or near optimal solution with low computation power for the sensors (except for the base station) but they deplete the battery power due to the communication overhead, so 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 the communication between neighbors may be large especially for dense networks. Distributed coverage algorithms are reliable and scalable. The two coverage approaches have advantages and disadvantages. Therefore, each approach can be used based on the application requirements. We conclude from this chapter that it is desirable to introduce an hybrid approach to take into account the advantages of both centralized and distributed coverage approaches. Such an hybrid approach can provide a good quality coverage and prolong the network lifetime.

 
 
 
 
 
 


@@ -384,11 +384,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.