]> AND Private Git Repository - ThesisAli.git/blobdiff - CHAPITRE_02.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Update By Ali
[ThesisAli.git] / CHAPITRE_02.tex
index 29423d64d01f50c3437e51671538e921c8c742a4..0010116f97522789c69400b5a66e1d4a9bebaa4c 100644 (file)
@@ -44,9 +44,17 @@ 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 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 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. 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. 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.
 
 
-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. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst the energy consumption for computation is increased. 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. 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. Table~\ref{Table0:ch2} shows a comparison between centralized coverage algorithms and distributed coverage algorithms.
+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. 
+
+%%Table~\ref{Table0:ch2} shows a comparison between centralized coverage algorithms and distributed coverage algorithms.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\iffalse
 
 \begin{table}[h!]
 \caption{Centralized Coverage Algorithms vs Distributed Coverage Algorithms}
 
 \begin{table}[h!]
 \caption{Centralized Coverage Algorithms vs Distributed Coverage Algorithms}
@@ -75,8 +83,12 @@ In distributed algorithms, on the other hand, the decision process is localized
 \label{Table0:ch2}
 \end{table}
 
 \label{Table0:ch2}
 \end{table}
 
+\fi
 
 
-In this dissertation, the sensing field is divided into smaller subregions using divide-and-conquer method. The division continues until the distance between two sensors inside the subregion is 3 or 2 hops maximum. This division makes our protocols more scalable for large networks, less energy consumer for communication and processing, and more reliable against network failure. Our proposed protocols are distributed on the sensor nodes of the subregions. The protocols in each subregion work in independent and simultaneous way with the protocols in the other subregions. If the network is disconnected in one subregion, it will not affect the other subregions of the sensing field.  There is no fixed sensor node in the subregion for executing the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node to execute the optimization algorithm according to predefined priority metrics. The resulting local optimal schedule from optimization algorithm is applied within the subregion. The elected sensor node sends a packet to every sensor within the subregion to inform him to stay active or sleep during this period. Each optimization algorithm in a subregion provides locally an optimal solution, so the solution for the whole sensing field is near-optimal. 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+In this dissertation, the sensing field is divided into smaller subregions using a divide-and-conquer method. The division continues until the distance between two sensors inside the subregion is 3 or 2 hops maximum. This division makes our protocols more scalable for large networks, less energy consumer for communication and processing, and more reliable against network failure. Our proposed protocols are distributed on the sensor nodes of the subregions. The protocols in each subregion work in independent and simultaneous way with the protocols in the other subregions. If the network is disconnected in one subregion, it will not affect the other subregions of the sensing field.  There is no fixed sensor node in the subregion for executing the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node to execute the optimization algorithm according to predefined priority metrics. The resulting local optimal schedule from optimization algorithm is applied within the subregion. The elected sensor node sends a packet to every sensor within the subregion to inform him to stay active or sleep during this period. Each optimization algorithm in a subregion provides locally an optimal solution, so the solution for the whole sensing field is near-optimal. 
 
 Several algorithms to maintain the coverage and maximize the network lifetime were proposed  in~\cite{ref113,ref101,ref103,ref105}. 
 Table \ref{x11} summarizes the main characteristics of some coverage approaches in previous literatures. 
 
 Several algorithms to maintain the coverage and maximize the network lifetime were proposed  in~\cite{ref113,ref101,ref103,ref105}. 
 Table \ref{x11} summarizes the main characteristics of some coverage approaches in previous literatures. 
@@ -84,116 +96,6 @@ In this table, the "SET K-COVER" characteristic refers to the maximum number of
 
 
 
 
 
 
-\begin{table}[h!]
-
-\begin{flushleft}
-\centering
-\caption{Main characteristics of some coverage approaches in literature.} 
-\label{x11}
-    \begin{tabular}{@{} cl*{13}c @{}}
-       & & \\
-        & & \multicolumn{10}{c}{Characteristics} \\[2ex]
-        \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 Z. Abrams et al. (2004)~\cite{ref114}   & \OK &\OK & \OK &   &  &  &\OK & \OK &  & \OK &  &  &\\
-
-& \tiny M. Cardei and D. Du (2005)~\cite{ref115} &  & \OK &   & \OK &  &  & \OK & \OK &  & \OK &  &  &\\
-
-& \tiny S. Slijepcevic and M. Potkonjak (2001)~\cite{ref116} & & \OK & \OK &  & & & \OK & \OK &  & \OK &  &  &\\
-
-& \tiny Manjun and A. K. Pujari (2011)~\cite{ref117} &  & \OK &   & \OK &  &  & \OK &  & \OK &  &  &  &\\
-
-& \tiny M. Yang and J. Liu (2014)~\cite{ref118} &  & \OK & \OK &   &  &  & \OK &  & \OK &  &  &  & \\
-
-& \tiny S. Wang et al. (2010)~\cite{ref144}     &  & \OK & \OK &   &  &  & \OK &  & \OK &  & \OK &  & \\
-
-& \tiny C. Lin et al. (2010)~\cite{ref147}    &  & \OK  & \OK  &   &  &  & \OK &  & \OK &  &  &  & \\
-
-& \tiny S. A. R. Zaidi et al. (2009)~\cite{ref148}  &  & \OK  & \OK  &  &  &  & \OK &  & \OK &  &  &  & \\
-
-& \tiny Y. Li et al. (2011)~\cite{ref142} &   & \OK  & \OK  &  &  & \OK & \OK & \OK &  & \OK & & \OK &\\
-
-& \tiny H. M. Ammari and S. K. Das (2012)~\cite{ref152} & \OK & \OK & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\
-
-& \tiny L. Liu et al. (2010)~\cite{ref150}  &  & \OK  &   & \OK  &  & \OK &  & \OK &  & \OK &  &  &\\
-
-& \tiny H. Cheng et al. (2014)~\cite{ref119}   &  &  \OK & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
-
-& \tiny M. Rebai et al. (2014)~\cite{ref141}  &  & \OK & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
-
-& \tiny L. Aslanyan et al. (2013)~\cite{ref151} &  & \OK  & \OK &  &  &  & \OK &  & \OK & \OK & \OK &  &\\
-
-& \tiny X. Liu et al. (2014)~\cite{ref143}  &  & \OK  & \OK &  &  &  & \OK &  & \OK & \OK & \OK &  &\\
-
-& \tiny F. Castano et al. (2013)~\cite{ref120} &  & \OK &   &  \OK &  &  & \OK &  & \OK & \OK &  &  &\\
-
-& \tiny A. Rossi et al. (2012)~\cite{ref121}  &  & \OK &  & \OK &  & \OK & \OK &  & \OK & \OK &  & \OK &\\
-
-& \tiny K. Deschinkel et al. (2012)~\cite{ref122} &  & \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  F. Ye et al. (2003)~\cite{ref125}  & \OK &   &  \OK &   &  &  & \OK &  & \OK &  &  &  &\\
-
-& \tiny  H. Zhang and J. C. Hou (2005)~\cite{ref126}  & \OK & & \OK & & & & \OK &  & \OK &  & \OK &  &\\
-
-& \tiny  W. B. Heinzelman et al. (2002)~\cite{ref109}  & \OK & & \OK & & & & \OK &  & \OK &  & \OK &  &\\
-
-& \tiny  T. Yardibi and E. Karasan (2010)~\cite{ref127} & \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{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  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  Z. Liu et al. (2012)~\cite{ref135}   & \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  Y. Xu et al. (2001)~\cite{GAF}   & \OK &   & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
-
-& \tiny  C. Vu et al. (2006)~\cite{DESK}  & \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}{\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 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}}  &    &  \\
-
-        \cmidrule[1pt]{2-14}
-    \end{tabular}
-    \end{flushleft}
-
-
-
-\end{table}
 
 
 
 
 
 
@@ -239,13 +141,15 @@ X. Deng et al. \cite{ref133} formulate the area coverage problem as a decision p
 %Their solutions can be translated to distributed protocols to solve the coverage problem.
 
 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}. 
 %Their solutions can be translated to distributed protocols to solve the coverage problem.
 
 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. 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.
+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. 
+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.
 
 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 chose for comparison as competitor because it is famous, fast, and easy to implement, as well as many authors referred to it in many publications. In addition, DESK algorithm is also selected as competitor in the comparison because it 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 divides 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)}
@@ -344,6 +248,116 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e
 %The period the average 
 
 
 %The period the average 
 
 
+\begin{table}[H]
+
+\begin{flushleft}
+\centering
+\caption{Main characteristics of some coverage approaches in literature.} 
+\label{x11}
+    \begin{tabular}{@{} cl*{13}c @{}}
+       & & \\
+        & & \multicolumn{10}{c}{Characteristics} \\[2ex]
+        \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 Z. Abrams et al. (2004)~\cite{ref114}   & \OK &\OK & \OK &   &  &  &\OK & \OK &  & \OK &  &  &\\
+
+%& \tiny M. Cardei and D. Du (2005)~\cite{ref115} &  & \OK &   & \OK &  &  & \OK & \OK &  & \OK &  &  &\\
+
+& \tiny S. Slijepcevic and M. Potkonjak (2001)~\cite{ref116} & & \OK & \OK &  & & & \OK & \OK &  & \OK &  &  &\\
+
+& \tiny Manjun and A. K. Pujari (2011)~\cite{ref117} &  & \OK &   & \OK &  &  & \OK &  & \OK &  &  &  &\\
+
+& \tiny M. Yang and J. Liu (2014)~\cite{ref118} &  & \OK & \OK &   &  &  & \OK &  & \OK &  &  &  & \\
+
+& \tiny S. Wang et al. (2010)~\cite{ref144}     &  & \OK & \OK &   &  &  & \OK &  & \OK &  & \OK &  & \\
+
+& \tiny C. Lin et al. (2010)~\cite{ref147}    &  & \OK  & \OK  &   &  &  & \OK &  & \OK &  &  &  & \\
+
+& \tiny S. A. R. Zaidi et al. (2009)~\cite{ref148}  &  & \OK  & \OK  &  &  &  & \OK &  & \OK &  &  &  & \\
+
+& \tiny Y. Li et al. (2011)~\cite{ref142} &   & \OK  & \OK  &  &  & \OK & \OK & \OK &  & \OK & & \OK &\\
+
+& \tiny H. M. Ammari and S. K. Das (2012)~\cite{ref152} & \OK & \OK & \OK &  & \OK &  & \OK &  & \OK &  & \OK &  &\\
+
+& \tiny L. Liu et al. (2010)~\cite{ref150}  &  & \OK  &   & \OK  &  & \OK &  & \OK &  & \OK &  &  &\\
+
+& \tiny H. Cheng et al. (2014)~\cite{ref119}   &  &  \OK & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
+
+& \tiny M. Rebai et al. (2014)~\cite{ref141}  &  & \OK & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
+
+& \tiny L. Aslanyan et al. (2013)~\cite{ref151} &  & \OK  & \OK &  &  &  & \OK &  & \OK & \OK & \OK &  &\\
+
+& \tiny X. Liu et al. (2014)~\cite{ref143}  &  & \OK  & \OK &  &  &  & \OK &  & \OK & \OK & \OK &  &\\
+
+& \tiny F. Castano et al. (2013)~\cite{ref120} &  & \OK &   &  \OK &  &  & \OK &  & \OK & \OK &  &  &\\
+
+& \tiny A. Rossi et al. (2012)~\cite{ref121}  &  & \OK &  & \OK &  & \OK & \OK &  & \OK & \OK &  & \OK &\\
+
+& \tiny K. Deschinkel et al. (2012)~\cite{ref122} &  & \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  F. Ye et al. (2003)~\cite{ref125}  & \OK &   &  \OK &   &  &  & \OK &  & \OK &  &  &  &\\
+
+& \tiny  H. Zhang and J. C. Hou (2005)~\cite{ref126}  & \OK & & \OK & & & & \OK &  & \OK &  & \OK &  &\\
+
+& \tiny  W. B. Heinzelman et al. (2002)~\cite{ref109}  & \OK & & \OK & & & & \OK &  & \OK &  & \OK &  &\\
+
+& \tiny  T. Yardibi and E. Karasan (2010)~\cite{ref127} & \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{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  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  Z. Liu et al. (2012)~\cite{ref135}   & \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  Y. Xu et al. (2001)~\cite{GAF}   & \OK &   & \OK  &   &  &  & \OK &  & \OK &  &  &  &\\
+
+& \tiny  C. Vu et al. (2006)~\cite{DESK}  & \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}{\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 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}}  &    &  \\
+
+        \cmidrule[1pt]{2-14}
+    \end{tabular}
+    \end{flushleft}
+
+
+
+\end{table}
 
 
 
 
 
 
@@ -351,8 +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 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. 
-As shown in table \ref{Table0:ch2}, each of 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 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.