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.
-
-
-
+$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.
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.
+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 explained 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, 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.
+
+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.
+
+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 do 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.
-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}.
+%Various centralized methods based on column generation approaches have also been proposed in~\cite{ref120,ref121,ref122}.
\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 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.
-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}. 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 the 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.
+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}. Localized and distributed algorithms generally result in non-disjoint set covers.
-Cho et al.~\cite{ref145} proposed a distributed node scheduling protocol, which can retain sensing coverage needed by applications
-and increase 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 and by computing its ESA can determine whether it will be active or sleep. The suggested work permits to sensor nodes to be in sleep mode opportunistically whilst fulfill the needed sensing coverage.
+X. Deng et al. \cite{ref133} formulate the area coverage problem as a decision problem, whose goal is to determine whether every point in the area of interest is 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 neighboring to a sensor and $n$ is the total number of sensors in the network. Thier solutions can be translated to distributed protocols to solve the coverage problem.
-In~\cite{ref146}, the authors defined a maximum sensing coverage region problem (MSCR) in WSNs and then proposed a distributed algorithm to solve it. The
-maximum observed area fully covered by a minimum active sensors. In this work, the major property is to getting rid from the redundant sensors in high-density WSNs and putting them in sleep mode, and choosing a smaller number of active sensors so as to be sure that the full area is k-covered, and all events appeared in that area can be precisely and timely detected. This algorithm minimized the total energy consumption and increased the lifetime.
+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} proposed a distributed node scheduling protocol, which can retain sensing coverage needed by applications and increase 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 and by computing its ESA can determine whether it will be active or sleep. The suggested work permits to sensor nodes to be in sleep mode opportunistically whilst fulfill the needed sensing coverage. The authors in~\cite{ref146}, defined a maximum sensing coverage region problem (MSCR) in WSNs and then proposed a distributed algorithm to solve it. The maximum observed area fully covered by a minimum active sensors. In this work, the major property is to getting rid from the redundant sensors in high-density WSNs and putting them in sleep mode, and choosing a smaller number of active sensors so as to be sure that the full area is k-covered, and all events appeared in that area can be precisely and timely detected. This algorithm minimized the total energy consumption and increased the 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 the 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 was proposed~\cite{ref149}. A new coverage criterion and scheduling approach is proposed based on cycle partition. This method is capable of build a sparse coverage set in distributed way by means of only connectivity information. This work considers only the communication range of the sensor is smaller two times the sensing range of sensor. Shibo et al.~\cite{ref137} have expressed the area coverage problem as a minimum weight submodular set cover problem and proposed 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}, designed 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 disk of sensor nodes and boundaries. They proposed two mechanisms for the converted target coverage problems to produce cover sets can cover the sensing
+field completely. Simulations results show that this approach can prolong the lifetime of the network compared with other works.
-A graph theoretical framework for connectivity-based coverage with configurable coverage granularity was proposed~\cite{ref149}. A new coverage criterion and scheduling approach is proposed based on cycle partition. This method is capable of build a sparse coverage set in distributed way by means of only connectivity information. This work considers only the communication range of the sensor is smaller two times the sensing range of sensor.
+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 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.
-
-Shibo et al.~\cite{ref137} have expressed the coverage problem as a minimum weight submodular set cover problem and proposed 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.
+
-In \cite{ref160} authors transform the area coverage problem to the target
-coverage one taking into account the intersection points among disks of sensors
-nodes or between disk of sensor nodes and boundaries.
-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}
\contentsline {section}{\numberline {2.1}Introduction}{41}{section.2.1}
\contentsline {section}{\numberline {2.2}Centralized Algorithms}{43}{section.2.2}
\contentsline {section}{\numberline {2.3}Distributed Algorithms}{46}{section.2.3}
-\contentsline {subsection}{\numberline {2.3.1}GAF}{47}{subsection.2.3.1}
+\contentsline {subsection}{\numberline {2.3.1}GAF}{48}{subsection.2.3.1}
\contentsline {subsection}{\numberline {2.3.2}DESK}{49}{subsection.2.3.2}
\contentsline {section}{\numberline {2.4}Conclusion}{50}{section.2.4}
-\contentsline {chapter}{\numberline {3}Evaluation Tools and Optimization Solvers}{53}{chapter.3}
-\contentsline {section}{\numberline {3.1}Introduction}{53}{section.3.1}
-\contentsline {section}{\numberline {3.2}Evaluation Tools}{53}{section.3.2}
-\contentsline {subsection}{\numberline {3.2.1}Testbed Tools}{54}{subsection.3.2.1}
-\contentsline {subsection}{\numberline {3.2.2}Simulation Tools}{55}{subsection.3.2.2}
-\contentsline {section}{\numberline {3.3}Optimization Solvers}{60}{section.3.3}
-\contentsline {section}{\numberline {3.4}Conclusion}{63}{section.3.4}
-\contentsline {part}{II\hspace {1em}Contributions}{65}{part.2}
-\contentsline {chapter}{\numberline {4}Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{67}{chapter.4}
-\contentsline {section}{\numberline {4.1}Introduction}{67}{section.4.1}
-\contentsline {section}{\numberline {4.2}Description of the DiLCO Protocol}{68}{section.4.2}
-\contentsline {subsection}{\numberline {4.2.1}Assumptions and Network Model}{68}{subsection.4.2.1}
-\contentsline {subsection}{\numberline {4.2.2}Primary Point Coverage Model}{69}{subsection.4.2.2}
-\contentsline {subsection}{\numberline {4.2.3}Main Idea}{70}{subsection.4.2.3}
-\contentsline {subsubsection}{\numberline {4.2.3.1}Information Exchange Phase}{71}{subsubsection.4.2.3.1}
-\contentsline {subsubsection}{\numberline {4.2.3.2}Leader Election Phase}{71}{subsubsection.4.2.3.2}
-\contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{71}{subsubsection.4.2.3.3}
-\contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{71}{subsubsection.4.2.3.4}
-\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{72}{section.4.3}
-\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{74}{section.4.4}
-\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{74}{subsection.4.4.1}
-\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{74}{subsection.4.4.2}
-\contentsline {subsection}{\numberline {4.4.3}Energy Consumption Model}{74}{subsection.4.4.3}
-\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{75}{subsection.4.4.4}
-\contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Subregions}{76}{subsection.4.4.5}
-\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Primary Point Models}{82}{subsection.4.4.6}
-\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{87}{subsection.4.4.7}
-\contentsline {section}{\numberline {4.5}Conclusion}{93}{section.4.5}
-\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{95}{chapter.5}
-\contentsline {section}{\numberline {5.1}Introduction}{95}{section.5.1}
-\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{96}{section.5.2}
-\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{96}{subsection.5.2.1}
-\contentsline {section}{\numberline {5.3}Primary Points based Multiround Coverage Problem Formulation}{97}{section.5.3}
-\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{99}{section.5.4}
-\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{99}{subsection.5.4.1}
-\contentsline {subsection}{\numberline {5.4.2}Metrics}{100}{subsection.5.4.2}
-\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{101}{subsection.5.4.3}
-\contentsline {section}{\numberline {5.5}Conclusion}{106}{section.5.5}
-\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{109}{chapter.6}
-\contentsline {section}{\numberline {6.1}Introduction}{109}{section.6.1}
-\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{110}{section.6.2}
-\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{110}{subsection.6.2.1}
-\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{113}{subsection.6.2.2}
-\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{113}{subsection.6.2.3}
-\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{114}{section.6.3}
-\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{116}{section.6.4}
-\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{116}{subsection.6.4.1}
-\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{117}{subsection.6.4.2}
-\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{118}{subsubsection.6.4.2.1}
-\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{118}{subsubsection.6.4.2.2}
-\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{119}{subsubsection.6.4.2.3}
-\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{119}{subsubsection.6.4.2.4}
-\contentsline {section}{\numberline {6.5}Conclusion}{122}{section.6.5}
-\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{123}{part.3}
-\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{125}{chapter.7}
-\contentsline {section}{\numberline {7.1}Conclusion}{125}{section.7.1}
-\contentsline {section}{\numberline {7.2}Perspectives}{126}{section.7.2}
-\contentsline {part}{Bibliographie}{142}{chapter*.11}
+\contentsline {chapter}{\numberline {3}Evaluation Tools and Optimization Solvers}{55}{chapter.3}
+\contentsline {section}{\numberline {3.1}Introduction}{55}{section.3.1}
+\contentsline {section}{\numberline {3.2}Evaluation Tools}{55}{section.3.2}
+\contentsline {subsection}{\numberline {3.2.1}Testbed Tools}{56}{subsection.3.2.1}
+\contentsline {subsection}{\numberline {3.2.2}Simulation Tools}{57}{subsection.3.2.2}
+\contentsline {section}{\numberline {3.3}Optimization Solvers}{62}{section.3.3}
+\contentsline {section}{\numberline {3.4}Conclusion}{65}{section.3.4}
+\contentsline {part}{II\hspace {1em}Contributions}{67}{part.2}
+\contentsline {chapter}{\numberline {4}Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{69}{chapter.4}
+\contentsline {section}{\numberline {4.1}Introduction}{69}{section.4.1}
+\contentsline {section}{\numberline {4.2}Description of the DiLCO Protocol}{70}{section.4.2}
+\contentsline {subsection}{\numberline {4.2.1}Assumptions and Network Model}{70}{subsection.4.2.1}
+\contentsline {subsection}{\numberline {4.2.2}Primary Point Coverage Model}{71}{subsection.4.2.2}
+\contentsline {subsection}{\numberline {4.2.3}Main Idea}{72}{subsection.4.2.3}
+\contentsline {subsubsection}{\numberline {4.2.3.1}Information Exchange Phase}{73}{subsubsection.4.2.3.1}
+\contentsline {subsubsection}{\numberline {4.2.3.2}Leader Election Phase}{73}{subsubsection.4.2.3.2}
+\contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{73}{subsubsection.4.2.3.3}
+\contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{73}{subsubsection.4.2.3.4}
+\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{74}{section.4.3}
+\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{76}{section.4.4}
+\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{76}{subsection.4.4.1}
+\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{76}{subsection.4.4.2}
+\contentsline {subsection}{\numberline {4.4.3}Energy Consumption Model}{76}{subsection.4.4.3}
+\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{77}{subsection.4.4.4}
+\contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Subregions}{78}{subsection.4.4.5}
+\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Primary Point Models}{84}{subsection.4.4.6}
+\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{89}{subsection.4.4.7}
+\contentsline {section}{\numberline {4.5}Conclusion}{95}{section.4.5}
+\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{97}{chapter.5}
+\contentsline {section}{\numberline {5.1}Introduction}{97}{section.5.1}
+\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{98}{section.5.2}
+\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{98}{subsection.5.2.1}
+\contentsline {section}{\numberline {5.3}Primary Points based Multiround Coverage Problem Formulation}{99}{section.5.3}
+\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{101}{section.5.4}
+\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{101}{subsection.5.4.1}
+\contentsline {subsection}{\numberline {5.4.2}Metrics}{102}{subsection.5.4.2}
+\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{103}{subsection.5.4.3}
+\contentsline {section}{\numberline {5.5}Conclusion}{108}{section.5.5}
+\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{111}{chapter.6}
+\contentsline {section}{\numberline {6.1}Introduction}{111}{section.6.1}
+\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{112}{section.6.2}
+\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{112}{subsection.6.2.1}
+\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{115}{subsection.6.2.2}
+\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{115}{subsection.6.2.3}
+\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{116}{section.6.3}
+\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{118}{section.6.4}
+\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{118}{subsection.6.4.1}
+\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{119}{subsection.6.4.2}
+\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{120}{subsubsection.6.4.2.1}
+\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{120}{subsubsection.6.4.2.2}
+\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{121}{subsubsection.6.4.2.3}
+\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{121}{subsubsection.6.4.2.4}
+\contentsline {section}{\numberline {6.5}Conclusion}{124}{section.6.5}
+\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{125}{part.3}
+\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{127}{chapter.7}
+\contentsline {section}{\numberline {7.1}Conclusion}{127}{section.7.1}
+\contentsline {section}{\numberline {7.2}Perspectives}{128}{section.7.2}
+\contentsline {part}{Bibliographie}{144}{chapter*.11}
