+%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.
+
+Many distributed algorithms have been developed to perform the scheduling to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref97}. Localized and distributed algorithms generally result in non-disjoint set covers.
+
+X. Deng et al. \cite{ref133} formulate the area coverage problem as a decision problem, whose goal is to determine if all points in the area of interest are monitored by at least k sensors. The 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 neighbors of a sensor and $n$ is the total number of sensors in the network.
+%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.
+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.
+
+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)}
+\label{ch2:sec:03:1}
+
+GAF is developed by Xu et al. \cite{GAF}, it uses geographic location information to divide the area of interest into a fixed square grids. Within each fixed square grid, it keeps only one node staying awake to take the responsibility of sensing and communication. Each sensor node uses its GPS to associate itself with a point in the grid. Figure~\ref{gaf1} gives an example of fixed square grid in GAF.
