From our point of view, 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. This chapter concentrates only on area coverage and target coverage problems because it is possible to transform the area coverage problem to target ( or point) coverage problem and vice versa. We exclude the barrier coverage problem from this discussion about the coverage problem because it is outside the scope of this dissertation. 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.
+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. This chapter concentrates only on area coverage and target coverage problems because it is possible to transform the area coverage problem to target ( or point) coverage problem and vice versa. We have excluded the barrier coverage problem from this discussion about the coverage problems because it is outside the scope of this dissertation. 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 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.
+Many centralized and distributed coverage 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. The centralized algorithms have the advantage of requiring very low processing power from the sensor nodes which have usually limited processing capabilities. Indeed, 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 as the network size increases.
+In 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. 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 the centralized coverage algorithms and the distributed coverage algorithms.
-\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 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.
+\begin{table}[h]
+\caption{Centralized Coverage Algorithms vs Distributed Coverage Algorithms}
+\begin{center}
+\begin{tabular}{ |p{3cm}|p{5cm}|p{5cm}|}
+\hline
+
+\textbf{\begin{center} Characteristics \end{center}} & \textbf{\begin{center} Centralized Coverage Algorithms \end{center}} & \textbf{\begin{center} Distributed Coverage Algorithms \end{center}}\\ \hline
+
+\textbf{\begin{center} Computation \end{center}} & Require low processing power where the algorithm is executed only in one elected node. & Require large processing power due to execution the algorithm in every node in WSN. \\ \hline
-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 the lifetime of the network.
+\textbf{\begin{center} Communication \end{center}} & Require large power consumption for communication. & Require low power consumption for communication. \\ \hline
+
+\textbf{\begin{center} Decision \end{center}} & Ensure nearly or close to optimal solution. & Can not ensure optimal (or near-optimal) solution.\\ \hline
+
+\textbf{\begin{center} Redundancy \end{center}} & Provide less redundant active sensor nodes during monitoring the sensing field. & Provide more redundant active sensor nodes during monitoring the sensing field.\\ \hline
+
+\textbf{\begin{center} Energy Consumption \end{center}} & Energy consumption is large especially when the network size and/or density increase. & Energy consumption is low because they have lower communication cost. \\ \hline
+
+\textbf{\begin{center} Scalability \end{center}} & Scalable only with dividing the sensing field into smaller subregions. & More scalable for large networks. \\ \hline
+
+\textbf{\begin{center} Reliability \end{center}} & Less robust against sensor failure. & More robust against sensor failure. \\ \hline
+
+\end{tabular}
+\end{center}
+\label{Table0:ch2}
+\end{table}
-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 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.
+In this dissertation, the sensing field is divided into smaller subregions using divide-and-conquer method. The division continues until the distance between each two sensors inside the subregion is 3 or 2 hops maximum. This division have made our protocols more scalable for the large networks, less energy consumption for communication, less processing power for decision, more reliable against network failure, and a longer lifetime. 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 disconnected in one subregion, it will not effect on the other subregions of the sensing field. There is no a fixed sensor node in the subregion execute the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node according to a predefined priority metrics to execute the optimization algorithm. The local optimal schedule resulted from the 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 optimal solution, so the solution for all the sensing field is near-optimal.
-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.
+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.
-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: 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.
+\section{Centralized Algorithms}
+\label{ch2:sec:02}
+The major idea of most centralized algorithms 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 optimal or near-optimal solution since the algorithm has a global view of the whole network. Energy-efficient centralized approaches differ according to several criteria \cite{ref113}, such as the coverage objective (target coverage or area coverage), the node deployment method (random or deterministic), and the heterogeneity of sensor nodes (common sensing range, common battery 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.
+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}. For instance, Slijepcevic and Potkonjak \cite{ref116} propose an algorithm, which allocates sensor nodes in mutually independent sets to monitor an area divided into several fields. Their algorithm builds a cover set by including in priority the sensor nodes, which cover critical fields, that is to say, fields that are covered by the smallest number of sensors. The time complexity of their heuristic is $O(n^2)$ where $n$ is the number of sensors. M. Cardei et al.~\cite{ref227}, have suggested a graph coloring technique to achieve energy savings by organizing the sensor nodes into a maximum number of disjoint dominating sets, which are activated successively. They have defined the maximum disjoint dominating sets problem and they have produced a heuristic that computes the disjoint cover sets so as to monitor the area of interest. The dominating sets do not guarantee the coverage of the whole region of interest. Abrams et al.~\cite{ref114} designed three approximation algorithms for a variation of the set k-cover problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized.
+Their work builds upon previous work in~\cite{ref116} and the generated cover sets do not provide complete coverage of the monitoring zone.
-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 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{ref115} proposed a heuristic to compute the disjoint set covers (DSC). In order to compute the maximum number of covers, they first transform DSC into a maximum-flow problem, which is then formulated as a mixed integer programming problem (MIP). Based on the solution of the MIP, they design a heuristic to compute the final number of covers. The results show a slight performance improvement in terms of the number of produced DSC in comparison to~\cite{ref116}, but it incurs higher execution time due to the complexity of the mixed integer programming solving. Zorbas et al. \cite{ref228} presented B\{GOP\}, a centralized target coverage algorithm introducing sensor candidate categorization depending on their coverage status and the notion of critical target to call targets that are associated with a small number of sensors. The total running time of their heuristic is $0(m n^2)$ where
+$n$ is the number of sensors and $m$ the number of targets. Compared to algorithm's results of Slijepcevic and Potkonjak \cite{ref116}, their heuristic produces more cover sets with a slight growth rate in execution time. L. Liu et al.~\cite{ref150} formulated the maximum disjoint sets for maintaining target coverage and connectivity (MDS-MCC) problem in WSN. Two algorithms are proposed for solving this problem, the 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. Y. Li et al.~\cite{ref142} presented a framework with heuristic strategies to solve the area coverage problem. The framework converts 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 . This framework has four strategies, two of them are designed for the network where the sensors have fixed sensing range and the other two are for the network where the sensors have adjustable sensing range. The properties of the original algorithms can be maintained by this framework and the transformation process has a low execution time. The simulation results validate the efficiency of the four proposed strategies. More recently, Deschinkel and Hakem \cite{229} introduced a near-optimal heuristic algorithm for solving the target coverage problem in WSN. The sensor nodes are organized into disjoint cover sets by the resolution an integer programming problem. Each cover set is capable of monitoring all the targets of the region of interest. Those covers sets are scheduled periodically. Their algorithm able to construct the different cover sets in parallel. The results show that their algorithm achieves near-optimal solutions compared to the optimal ones obtained by the exact method.
-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.
+
+
+
+
+
+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. 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}, addressed 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 are clarified that with a random deployment about seven times more nodes are required to supply full coverage. The work in~\cite{ref144} addressed 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 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 area coverage method to divide the sensors of the WSN is 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 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. The problem of k-coverage over the area of interest in WSNs was 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, a four configuration protocols have proposed for treating the k-coverage in WSNs. Simulation results show that their protocols outperform an existing distributed k-coverage configuration protocol. The work that presented in~\cite{ref151} solved 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 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 defined the connected coverage problem as an optimization problem and a centralized genetic algorithm is used to find the solution.
+
+
+More recently, the authors in~\cite{ref118}, have considered 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}, formulated the problem of full grid area coverage problem 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. H. Cheng et al.~\cite{ref119} have defined 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 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. X. Liu et al.~\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 area 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 in~\cite{ref120,ref121,ref122}.
-\subsection{Distributed Algorithms}
-\label{ch2:sec:04}
+\section{Distributed Algorithms}
+\label{ch2:sec:03}
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,ref97}.
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.
+\subsection{GAF}
+\label{ch2:sec:03:1}
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.
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.
+\subsection{DESK}
+\label{ch2:sec:03:2}
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.
