-Recent studies show an increasing interest in the use of exact schemes to solve optimization problems in WSN \cite{ref230,ref231,ref121,ref122,ref120}. Column Generation (CG) has been widely used to address different versions of 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} introduced an efficient implementation of a genetic algorithm based 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, F. Castano et al. \cite{ref120} addressed the maximum network lifetime and the target coverage problem in WSNs with connectivity and coverage constraints. They considered two cases to schedule the activity of a set of sensor nodes, keeping them connected while network lifetime is maximized. First, the full coverage of the targets is required, and second only a fraction of the targets has to be monitored at any instant of time. They proposed an exact approach based on column generation and boosted by a greedy randomized adaptive search procedure (GRASP) and a variable neighborhood search (VNS) to address both of these problems. Finally, a multiphase framework combining these two approaches is constructed by sequentially using these two heuristics at each iteration of the column generation algorithm. The results show that combining the two heuristic methods enhances the results significantly.
+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 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,
+ F. Castano et al. \cite{ref120} address the maximum network lifetime and the target coverage problem in WSNs with connectivity and coverage constraints. They consider two cases to schedule the activity of a set of sensor nodes, keeping them connected while network lifetime is maximized. First, the full coverage of the targets is required, second only a fraction of the targets has to be monitored at any instant of time. They propose an exact approach based on column generation boosted by a Greedy Randomized Adaptive Search Procedure (GRASP) and a Variable Neighborhood Search (VNS) to address both of these problems. Finally, a multiphase framework combining these two approaches is constructed sequentially using these two heuristics at each iteration of the column generation algorithm. The results show that combining the two heuristic methods enhances the results significantly.
