Update by Ali

diff --git a/ACRONYMS.tex b/ACRONYMS.tex
index c873dfd86648fc7674217b733a9c0ca69344d5f2..be974d9993dbb403a9524ee6669c530773ec3967 100644 (file)
--- a/ACRONYMS.tex
+++ b/ACRONYMS.tex
@@ -14,6 +14,7 @@
 \item[DILCO] Distributed Lifetime Coverage Optimization
 \item[MuDiLCO] Multiround Distributed Lifetime Coverage Optimization
 \item[PeCO] Perimeter-based Coverage Optimization
 \item[DILCO] Distributed Lifetime Coverage Optimization
 \item[MuDiLCO] Multiround Distributed Lifetime Coverage Optimization
 \item[PeCO] Perimeter-based Coverage Optimization

+\item[OMNeT++] Objective Modular Network Testbed

 \item[DESK] Distributed Energy-efficient Scheduling for K-coverage
 \item[GAF] Geographical Adaptive Fidelity
 \item[PDA] Personal Digital Assistant
 \item[DESK] Distributed Energy-efficient Scheduling for K-coverage
 \item[GAF] Geographical Adaptive Fidelity
 \item[PDA] Personal Digital Assistant


@@ -28,10 +29,58 @@
 \item[MAV] Micro Aerial Vehicle
 \item[ECG] Electrocardiogram
 \item[SCADA] Supervisory Control and Data Acquisition 
 \item[MAV] Micro Aerial Vehicle
 \item[ECG] Electrocardiogram
 \item[SCADA] Supervisory Control and Data Acquisition 

-\item[]
-\item[]
-\item[]
-\item[]
+\item[QoS]  Quality of Service
+\item[DSC] Disjoint  Set Covers
+\item[MIP] Mixed Integer Programming
+\item[LP] Linear Programming
+\item[GAS] Geometrically based Activity Scheduling 
+\item[NCG] Node Coverage Grouping
+\item[CG] Column Generation
+\item[MLP] Maximum-network Lifetime Problem
+\item[RMP] Restricted Master Problem
+\item[PS] Pricing Subproblem
+\item[GRASP] Greedy Randomized Adaptive Search Procedure
+\item[VNS] Variable Neighborhood Search
+\item[CSB] Cover Sets Balance
+\item[CNSC] Correlated Node Set Computing
+\item[HREF] High Residual Energy First
+\item[SHM] Structural Health Monitoring
+\item[ESA] Effective Sensing Area
+\item[MSCR] Maximum Sensing Coverage Region
+\item[DASSA] Distributed Adaptive Sleep  Scheduling Algorithm
+\item[DTGA] Distributed Truncated Greedy Algorithm
+\item[FIT]  Future Internet of the Things
+\item[GUI] Graphical User Interface
+\item[NED] NEtwork Description
+\item[ns-2] Network Simulator-2
+\item[OPNET] Optimized Network Engineering tool
+\item[GloMoSim]  Global Mobile System Simulator
+\item[SENSE] Sensor Network Simulator and Emulator
+\item[GTSNetS] Georgia Tech Sensor Network Simulator
+\item[GNU] GNU's Not Unix
+\item[GLPK] GNU Linear Programming Kit
+\item[MPS]  Mathematical Programming System
+\item[COIN-OR] Linear Programming 
+\item[BCP]  Branch Cut and Price
+\item[CBC]  COIN-OR Branch and Cut
+\item[OPL] Optimization Programming Language 
+\item[QP] Quadratic Programming 
+\item[QCP] Quadratically Constrained Programming
+\item[MILP] Mixed Integer Linear Programming
+\item[MIQP] Mixed-Integer Quadratic Programming
+\item[MIQCP] Mixed-Integer Quadratically Constrained Programming
+\item[AIMMS] Advanced Interactive Multidimensional Modeling System
+\item[AMPL] A Mathematical Programming Language
+\item[GAMS] General Algebraic Modeling System
+\item[MPL] Mathematical Programming Language
+\item[UAV] Unmanned Aerial Vehicle
+\item[WSNL] Wireless Sensor Node Leader
+\item[MCU]  Microcontroller Unit
+\item[CR] Coverage Ratio
+\item[EC] Energy Consumption
+\item[ASR] Active Sensors Ratio
+\item[] 
+

 \end{abbreviations}
 
    
\ No newline at end of file
 \end{abbreviations}
 
    
\ No newline at end of file

diff --git a/Abstruct.tex b/Abstruct.tex
index b75522b3db5867116e79f7bbc439afab96c24e6d..6e538cee51dba93432eb3aa33d19bdf5a7fd87ed 100644 (file)
--- a/Abstruct.tex
+++ b/Abstruct.tex
@@ -42,5 +42,5 @@ Extensive simulations are conducted using the discrete event simulator OMNET++ t
 the WSN lifetime and provides improved coverage performance.
 
 
 the WSN lifetime and provides improved coverage performance.
 
 

-\textbf{KEY WORDS:} Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling, Distributed Algorithms, Energy-efficiency.
+\textbf{KEY WORDS:} Wireless Networks, Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling, Distributed Algorithms, Centralized Algorithms, Robustness, Connectivity, Parallel Algorithms, Energy-efficiency, Heterogeneous Energy Network, Homogeneous Network.

 
 

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index c25e13d42a32b957de77b8c31b6fed202bab288b..0c823df431033ffaf92d95b3365d9b1b88c5f4f1 100644 (file)
--- a/CHAPITRE_02.tex
+++ b/CHAPITRE_02.tex
@@ -78,9 +78,9 @@ In a distributed algorithms, on the other hand, the decision process is localize
 \end{table}
 
 
 \end{table}
 
 

-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 makes our protocols more scalable for large networks, less energy consumer for communication, less processing power for decision, 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 disconnected in one subregion, it will not affect the other subregions of the sensing field.  There is no a 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 a predefined priority metrics. 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. 
+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 makes our protocols more scalable for large networks, less energy consumer for communication, less processing power for decision, 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 a 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 a predefined priority metrics. The resulted local optimal schedule of 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. 

 
 

-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. In table~\ref{Table1:ch2}, the "SET K-COVER" characteristic refers to the maximum number of disjoint or non-disjoint sets of sensors such that each set cover can assure the coverage for the whole region. The K-COVER algorithm provides a solution with K cover sets in each execution. The k-coverage characteristic refers to that every point inside the monitored area is always covered by at least k active sensors.
+Several algorithms to retain the coverage and maximize the network lifetime were proposed  in~\cite{ref113,ref101,ref103,ref105}. Table~\ref{Table1:ch2} summarizes the main characteristics of some coverage approaches in previous literatures. In table~\ref{Table1:ch2}, the "SET K-COVER" characteristic refers to the maximum number of disjoint or non-disjoint sets of sensors such that each set cover can assure the coverage for the whole region. The K-COVER algorithm provides a solution with K cover sets in each execution. The k-coverage characteristic refers to that every point inside the monitored area is always covered by at least k active sensors.

 
 
 
 
 
 


@@ -88,28 +88,33 @@ Several algorithms to retain the coverage and maximize the network lifetime were
 \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). 
 
 \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). 
 

-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}, suggest 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} design 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.
+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}, suggest 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} design 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.
 
 
 Their work builds upon previous work in~\cite{ref116} and the generated cover sets do not provide complete coverage of the monitoring zone.
 
 

-The authors in~\cite{ref115} propose 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}  present  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} formulate the maximum disjoint sets for maintaining target coverage and connectivity problem in WSN.  They propose a graph theoretical framework to study the joint problem of connectivity and coverage in a WSN with random deployment of nodes with no restrictions on the sensing and communication ranges of nodes. They propose heuristic algorithms to find the suitable number of nodes to guarantee connectivity and coverage while  maximizing network lifetime.
+The authors in~\cite{ref115} propose 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}  present  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} formulate the maximum disjoint sets for maintaining target coverage and connectivity problem in WSN.  They propose a graph theoretical framework to study the joint problem of connectivity and coverage in a WSN with random deployment of nodes with no restrictions on the sensing and communication ranges of nodes. They propose heuristic algorithms to find the suitable number of nodes to guarantee connectivity and coverage while  maximizing network lifetime.

 %This work did not take into account the sensor node failure, which is an unpredictable event because the two solutions are full centralized algorithms. 
 %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} present 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. They execute 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 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} introduce 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 of 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  is 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.
+Y. Li et al.~\cite{ref142} present 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. They execute a complete coverage algorithm to find full coverage sets with virtual radii and then transform to 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 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{ref229} introduce a near-optimal heuristic algorithm for solving the target coverage problem in WSN. The sensor nodes are organized into disjoint cover sets, each capable of monitoring all the targets of the region of interest. %Those covers sets are scheduled periodically. 
+Their algorithm  is 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 resolution of an integer programming.
+%exact method.

 
 
 
 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}
 
 
 
 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
+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
 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 authors explained that with a random deployment about seven times more nodes are required to supply full coverage compared to deterministic deployment. The work in~\cite{ref144} address 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 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 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 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 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}, 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 authors explained that with a random deployment about seven times more nodes are required to supply full coverage compared to deterministic deployment. 
+The work in~\cite{ref144} address 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 a few sensors as possible 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 them 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 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. %The generation of coverage bitmap by using  Minkowski technique, the network is able to providing the desired ratio of coverage. 
+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 WSN \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, and 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 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. 
+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 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, and 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 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 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}, consider 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}, formulate 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 are taken into consideration. This work does not take into account the energy constraint. H. Cheng et al.~\cite{ref119} define 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 introduce  a new Correlated Node Set Computing (CNSC) algorithm to  find the correlated node set for a given node. After that, they propose 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} explain 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 required 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 propose two approaches for dividing the deployed nodes into suitable cover sets.
+More recently, the authors in~\cite{ref118}, consider 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}, formulate 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 are taken into consideration. This work does not take into account the energy constraint. H. Cheng et al.~\cite{ref119} define 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 introduce  a new Correlated Node Set Computing (CNSC) algorithm to  find the correlated node set for a given node. After that, they propose 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} explain 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 required 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 propose two approaches for dividing the deployed nodes into suitable cover sets.

 
 
   
 
 
   


@@ -124,16 +129,17 @@ More recently, the authors in~\cite{ref118}, consider an area coverage optimizat
 
 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.
 
 
 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.
 

-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. Their solutions can be translated to distributed protocols to solve the coverage problem.
+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. 
+%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}. 
 
 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 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 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 fulfill 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, and choosing a smaller number of active sensors 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 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} express that 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 disk of sensor nodes and boundaries. They proposed two mechanisms for the converted target coverage problems to produce cover sets covering the sensing
+Cho et al.~\cite{ref145} propose 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 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 fulfill 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, and choosing a smaller number of active sensors 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 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 is 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 that the communication range of the sensor is smaller two times the sensing range of sensor. 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 disk 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.
 
 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 focused in more detail on two distributed coverage algorithms, GAF and DESK because we compared our proposed coverage optimization protocols with them during performance evaluation.
+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.

  
 
 \subsection{GAF}
  
 
 \subsection{GAF}


@@ -181,9 +187,9 @@ in the square grid.
 \subsection{DESK}
 \label{ch2:sec:03:2}
 
 \subsection{DESK}
 \label{ch2:sec:03:2}
 

-The authors in~\cite{DESK} design 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 satisfied. 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}. 
+The authors in~\cite{DESK} design 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 satisfied. 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}. 

 
 

-DESK is based on the result from \cite{ref133}. In \cite{ref133}, the whole area is k-covered if and only if the perimeters of all sensors are k-covered. The coverage level of perimeter of a sensor $s_i$ is determined by calculating the angle corresponding to the arc that each of its neighbors covers its perimeter. Figure~\ref{figp}~(a) illuminates such arcs whilst figure~\ref{figp}~(b) shows the angles corresponding with those arcs, which were posted into the range [0,2$ \pi $]. According to figure~\ref{figp}~(b), the coverage level of sensor $s_i$ can be calculated via traversing the range from 0 to  2$ \pi $.
+DESK is based on the result from \cite{ref133}. In \cite{ref133}, the whole area is K-covered if and only if the perimeters of all sensors are k-covered. The coverage level of perimeter of a sensor $s_i$ is determined by calculating the angle corresponding to the arc that each of its neighbors covers its perimeter. Figure~\ref{figp}~(a) illuminates such arcs whilst figure~\ref{figp}~(b) shows the angles corresponding with those arcs, which were posted into the range [0,2$ \pi $]. According to figure~\ref{figp}~(b), the coverage level of sensor $s_i$ can be calculated via traversing the range from 0 to  2$ \pi $.

 
 
 \begin{figure}[h!]
 
 
 \begin{figure}[h!]


@@ -218,7 +224,7 @@ w_{i} = \left \{
 \end{equation} 
 
 Where $\alpha, \beta,$ and $\eta$ are constant, z is a random number between [0; d], where d is a time slot, to avoid the case where two sensors having the same $w_i$ to be active at the same time. $l(e_i, r_i)$ is the function computing the lifetime of sensor $s_i$ in terms of its current remaining energy $e_i$ and its sensing range $r_i$. 
 \end{equation} 
 
 Where $\alpha, \beta,$ and $\eta$ are constant, z is a random number between [0; d], where d is a time slot, to avoid the case where two sensors having the same $w_i$ to be active at the same time. $l(e_i, r_i)$ is the function computing the lifetime of sensor $s_i$ in terms of its current remaining energy $e_i$ and its sensing range $r_i$. 

-DESK uses two types of messages, mACTIVATE message by which a sensor informs others that it becomes active, and mASK2SLEEP by which a sensor suggests a neighbor to go to sleep due to its uselessness. The concept of uselessness or a redundant neighbor refers to one that does not contribute to the perimeter coverage of the considered sensor.   This means that the segment of the perimeter of the considered sensor overlapping with that neighbor is already covered by active sensors.
+DESK uses two types of messages, mACTIVATE message by which a sensor informs others that it becomes active, and mASK2SLEEP by which a sensor suggests a neighbor to go to sleep due to its uselessness. The concept of uselessness or a redundant neighbor refers to one that does not contribute to the perimeter coverage of the considered sensor. This means that the segment of the perimeter of the considered sensor overlapping with that neighbor is already covered by active sensors.

 
 
 
 
 
 


@@ -346,7 +352,7 @@ This chapter describes some coverage proposed problems in the literature, with t
 The coverage problem is considered as an essential requirement for many applications in WSNs because the better coverage of an area of interest provides better sensing measurements of the physical phenomenon. 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 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 in WSNs. 
 %Whatever the case, this would result in a lower lifetime coverage in WSNs.  
 The coverage problem is considered as an essential requirement for many applications in WSNs because the better coverage of an area of interest provides better sensing measurements of the physical phenomenon. 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 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 in WSNs. 
 %Whatever the case, this would result in a lower lifetime coverage in WSNs.  

-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 that take into account the advantages of both centralized and distributed coverage approaches. This hybrid approaches can provide a good quality coverage and prolong the network lifetime.
+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. This hybrid approaches can provide a good quality coverage and prolong the network lifetime.

 
 
 
 
 
 

diff --git a/CHAPITRE_03.tex b/CHAPITRE_03.tex
index 4134bc4b807dd788df42eedf8eb1d89f8b5f357b..a4dd3fa806752aaa797a6bec7656e2f937cb2fb4 100644 (file)
--- a/CHAPITRE_03.tex
+++ b/CHAPITRE_03.tex
@@ -54,7 +54,7 @@ The WISEBED~\cite{ref183} is a large-scale WSN testbed  with a hierarchical arch
 \item \textbf{IoT-LAB:}
 
 IoT-LAB testbed~\cite{ref184,ref185} supplies a very large scale infrastructure service  appropriate for evaluating wireless sensor devices and heterogeneous communicating objects. IoT-LAB includes more than 2700 wireless sensor nodes deployed in six different regions in France.  Different kinds of wireless sensor nodes are available, with different processor architectures (MSP430, STM32, and Cortex-A8) and different wireless chips (802.15.4 PHY @ 800 MHz or 2.4 GHz). Sensor nodes are either mobile or fixed and can be used in different  topologies throughout all the regions. 
 \item \textbf{IoT-LAB:}
 
 IoT-LAB testbed~\cite{ref184,ref185} supplies a very large scale infrastructure service  appropriate for evaluating wireless sensor devices and heterogeneous communicating objects. IoT-LAB includes more than 2700 wireless sensor nodes deployed in six different regions in France.  Different kinds of wireless sensor nodes are available, with different processor architectures (MSP430, STM32, and Cortex-A8) and different wireless chips (802.15.4 PHY @ 800 MHz or 2.4 GHz). Sensor nodes are either mobile or fixed and can be used in different  topologies throughout all the regions. 

-IoT-LAB provides web-based reservation and tools for protocols and applications development, along with direct command-line access to the platform.  Wireless sensor nodes firmware can be constructed from  source and deployed on reserved nodes, application activity can be controlled and observed, power consumption or radio interference can be measured using the offered tools. IoT-LAB is a part of the FIT experimental platform, a set of supplementary elements that enable experimentation with innovative services for academic and industrial users.
+IoT-LAB provides web-based reservation and tools for protocols and applications development, along with direct command-line access to the platform.  Wireless sensor nodes firmware can be constructed from  source and deployed on reserved nodes, application activity can be controlled and observed, power consumption or radio interference can be measured using the offered tools. IoT-LAB is a part of the FIT (Future Internet of the Things) experimental platform, a set of supplementary elements that enable experimentation with innovative services for academic and industrial users.

 
 \end{enumerate}
 
 
 \end{enumerate}
 


@@ -99,7 +99,7 @@ Several simulation tools are available for WSNs, which vary in their characteris
 
 \item \textbf{NS2:} 
 
 
 \item \textbf{NS2:} 
 

-The Network Simulator-2 (ns-2)~\cite{ref191,ref192} is an open source, discrete event, network simulator. The major goal of ns-2 is to provide a simulation environment for wired as well as wireless networks to simulate different protocols with different network topologies. ns-2 is constructed using C++ and the simulation interface is provided via OTcl, an object-oriented dialect of Tcl. The network topology is determined by the users by writing OTcl scripts, and then the main program of ns-2 simulates this topology with fixed parameters. ns-2 provides a graphical view of the network by using network animator (NAM). NAM interface includes control features that allow researchers to forward, pause, stop, and control the simulation. ns-2 is the most common and widely used network simulator for scientific  research work.   
+The Network Simulator-2 (ns-2)~\cite{ref191,ref192} is an open source, discrete event, network simulator. The major goal of ns-2 is to provide a simulation environment for wired as well as wireless networks to simulate different protocols with different network topologies. ns-2 is constructed using C++ and the simulation interface is provided via OTcl, an object-oriented dialect of Tcl. The network topology is determined by the users by writing OTcl scripts, and then the main program of ns-2 simulates this topology with fixed parameters. ns-2 provides a graphical view of the network by using network animator (Nam). Nam interface includes control features that allow researchers to forward, pause, stop, and control the simulation. ns-2 is the most common and widely used network simulator for scientific research work.   

 
 The next version, ns-3, is considered as a new simulator and a final replacement of ns-2, not a simple extension~\cite{ref194}. The ns-3 project~\cite{ref193} was started in mid-2006 and is still under intensive development. Like ns-2, ns-3 is an open source, discrete-event network simulator targeted essentially for research and educational use~\cite{ref195}. ns-3 supports both simulation and emulation using sockets. It also provides a tracing facility to help users in debugging.
 
 
 The next version, ns-3, is considered as a new simulator and a final replacement of ns-2, not a simple extension~\cite{ref194}. The ns-3 project~\cite{ref193} was started in mid-2006 and is still under intensive development. Like ns-2, ns-3 is an open source, discrete-event network simulator targeted essentially for research and educational use~\cite{ref195}. ns-3 supports both simulation and emulation using sockets. It also provides a tracing facility to help users in debugging.
 


@@ -107,15 +107,15 @@ The next version, ns-3, is considered as a new simulator and a final replacement
 
 \item \textbf{OMNeT++:}
 
 
 \item \textbf{OMNeT++:}
 

-OMNeT++ (Objective Modular Network Testbed) is an open-source, free, discrete-event, component-based C++ simulation library, modular simulation framework for building network simulators~\cite{ref158,ref203}. Even if OMNeT++ is not a network simulator itself, it is very popular as a network simulation platform for both scientific and industrial communities. The major goal behind the development of OMNeT++ is to provide a strong simulation tool, which can be used by the academic and commercial researchers for simulating different types of networks in a distributed and parallel way~\cite{ref197}. OMNeT++ has an extensive graphical user interface (GUI) and intelligence support. It runs on Windows, Linux, Mac OS~X, and other Unix-like systems, and provides a component architecture for models. Components (modules) are first programmed in C++, then assembled into larger components and models using a high-level language (NED)~\cite{ref198}. Several simulation frameworks can be used with OMNeT++ such as INET, INETMANET, MiXiM, and Castalia, where each of them provides a set of simulation facilities (modelity and soon) and can be used for specific applications.  
+OMNeT++ (Objective Modular Network Testbed) is an open-source, free, discrete-event, component-based C++ simulation library, modular simulation framework for building network simulators~\cite{ref158,ref203}. Even if OMNeT++ is not a network simulator itself, it is very popular as a network simulation platform for both scientific and industrial communities. The major goal behind the development of OMNeT++ is to provide a strong simulation tool, which can be used by the academic and commercial researchers for simulating different types of networks in a distributed and parallel way~\cite{ref197}. OMNeT++ has an extensive Graphical User Interface (GUI) and intelligence support. It runs on Windows, Linux, Mac OS~X, and other Unix-like systems, and provides a component architecture for models. Components (modules) are first programmed in C++, then assembled into larger components and models using a high-level language (NED)~\cite{ref198}. Several simulation frameworks can be used with OMNeT++ such as INET, INETMANET, MiXiM, and Castalia, where each of them provides a set of simulation facilities (modelity and soon) and can be used for specific applications.  

 
 
 \item \textbf{OPNET:}
 
 
 
 \item \textbf{OPNET:}
 

-OPNET (Optimized Network Engineering tool)~\cite{ref192,ref200,ref201} is the first commercial simulation tool developed in 1987 for communication networks. It is a discrete event, object-oriented, general purpose network simulator, which is widely used in industry. It uses C and Java languages. It provides a comprehensive development environment for the specification, simulation, configuration, and performance analysis of the communication network. OPNET allows researchers to develop various models by means of a graphical interface. It provides different types of tools such as Probe Editor, Filter Tool, and Animation Viewer for data collection to model graph and animate the resulting output. Unlike ns-2, OPNET provides modeling for different sensor-specific hardware, such as physical-link transceivers and antennas. It includes sensor-specific models such as ad-hoc connectivity, mobility of nodes, node failure models, modeling of power-consumption, etc. OPNET is, a commercial simulator and the license is very expensive. This represents the main disadvantage of  that simulator.
+OPNET (Optimized Network Engineering tool)~\cite{ref192,ref200,ref201} is the first commercial simulation tool developed in 1987 for communication networks. It is a discrete event, object-oriented, general purpose network simulator, which is widely used in industry. It uses C and Java languages. It provides a comprehensive development environment for the specification, simulation, configuration, and performance analysis of the communication network. OPNET allows researchers to develop various models by means of a graphical interface. It provides different types of tools such as Probe Editor, Filter Tool, and Animation Viewer for data collection to model graph and animate the resulting output. Unlike ns-2, OPNET provides modeling for different sensor-specific hardware, such as physical-link transceivers and antennas. It includes sensor-specific models such as ad-hoc connectivity, mobility of nodes, node failure models, modeling of power-consumption, etc. OPNET is, a commercial simulator and the license is very expensive. This represents the main disadvantage of that simulator.

 
 
 
 

-\item \textbf{GloMoSim:}  
+\item \textbf{GloMoSim:} 

 
 GloMoSim (Global Mobile System Simulator)~\cite{ref202,ref204,ref205} is an open source, well-documented source code and scalable simulation environment developed in 1998 for mobile wireless networks. It uses a library called Parsec, which is an extension of C for parallel programming. The main feature of GloMoSim simulator is the parallel environment. A parallel network simulation is hard due to the communication among the simulated nodes on different machines. Several types of protocols and models are found in GloMoSim including TCP,
 IEEE 802.11 CSMA/CA, MAC, UDP, HTTP, FTP, CBR, ODMRP, WRP, DSR, MACA, Telnet, AODV, etc. It uses a VT visualization tool to observe and debug these protocols. The GloMoSim tool is designed to be extensible with all protocols implemented as modules in its library.  It also uses an object-oriented approach. 
 
 GloMoSim (Global Mobile System Simulator)~\cite{ref202,ref204,ref205} is an open source, well-documented source code and scalable simulation environment developed in 1998 for mobile wireless networks. It uses a library called Parsec, which is an extension of C for parallel programming. The main feature of GloMoSim simulator is the parallel environment. A parallel network simulation is hard due to the communication among the simulated nodes on different machines. Several types of protocols and models are found in GloMoSim including TCP,
 IEEE 802.11 CSMA/CA, MAC, UDP, HTTP, FTP, CBR, ODMRP, WRP, DSR, MACA, Telnet, AODV, etc. It uses a VT visualization tool to observe and debug these protocols. The GloMoSim tool is designed to be extensible with all protocols implemented as modules in its library.  It also uses an object-oriented approach. 

diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex
index 8fc2e395a422010c2e77d44344de23ed9ee597ee..07788db7d7e5875e673ddb9cc21c11eafad5766d 100644 (file)
--- a/CHAPITRE_04.tex
+++ b/CHAPITRE_04.tex
@@ -8,25 +8,6 @@
 \label{ch4}
 
 
 \label{ch4}
 
 

-\iffalse
-\section{Summary}
-\label{ch4:sec:01}
-In this chapter, a Distributed Lifetime Coverage Optimization protocol (DiLCO) to maintain
-the coverage and to improve  the  lifetime  in  wireless sensor  networks  is
-proposed.   The  area of  interest  is first  divided  into  subregions using  a
-divide-and-conquer  method and  then the  DiLCO protocol  is distributed  on the
-sensor nodes  in each  subregion. The DiLCO  combines two  efficient techniques:
-leader election  for each subregion, followed by  an optimization-based planning
-of activity  scheduling decisions for  each subregion. The proposed  DiLCO works
-into rounds during which a small  number of nodes, remaining active for sensing,
-is selected to ensure coverage so as to maximize the lifetime of wireless sensor
-network.   Each  round  consists   of  four  phases:  (i)~Information  Exchange,
-(ii)~Leader Election, (iii)~Decision, and (iv)~Sensing.  The decision process is
-carried out  by a leader node,  which solves an integer  program.  Compared with
-some existing protocols, simulation results  show that the proposed protocol can
-prolong the network lifetime and improve the coverage performance effectively.
-
-\fi

 
 \section{Introduction}
 \label{ch4:sec:01}
 
 \section{Introduction}
 \label{ch4:sec:01}

diff --git a/CHAPITRE_05.tex b/CHAPITRE_05.tex
index 6bb2bf521642514a6bb47aeef7b9a1422aebdccc..91014fb9ba229257a060435a5450f0267123a523 100644 (file)
--- a/CHAPITRE_05.tex
+++ b/CHAPITRE_05.tex
@@ -7,19 +7,6 @@
 \chapter{Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}
 \label{ch5}
 
 \chapter{Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}
 \label{ch5}
 

-\iffalse
-
-\section{Summary}
-\label{ch5:sec:01}
-Coverage and lifetime are two paramount problems in Wireless  Sensor Networks (WSNs). In this paper, a method called Multiround Distributed Lifetime Coverage
-Optimization  protocol (MuDiLCO)  is proposed  to maintain  the coverage  and to improve the lifetime in wireless sensor  networks. The area of interest is first
-divided  into subregions and  then the  MuDiLCO protocol  is distributed  on the sensor nodes in each subregion. The proposed MuDiLCO protocol works in periods
-during which sets of sensor nodes are scheduled to remain active for a number of rounds  during the  sensing phase,  to ensure coverage  so as  to maximize the
-lifetime of  WSN. The decision process is  carried out by a  leader node, which solves an  integer program to  produce the best  representative sets to  be used
-during the rounds  of the sensing phase. Compared  with some existing protocols, simulation  results based  on  multiple criteria  (energy consumption,  coverage
-ratio, and  so on) show that  the proposed protocol can  prolong efficiently the network lifetime and improve the coverage performance.
-
-\fi

 
 \section{Introduction}
 \label{ch5:sec:01}
 
 \section{Introduction}
 \label{ch5:sec:01}


@@ -268,8 +255,7 @@ large compared to $W_{\theta}$.
 \label{ch5:sec:04:01}
 We  conducted  a  series of  simulations  to  evaluate  the efficiency  and  the
 relevance  of our  approach,  using  the  discrete   event  simulator  OMNeT++
 \label{ch5:sec:04:01}
 We  conducted  a  series of  simulations  to  evaluate  the efficiency  and  the
 relevance  of our  approach,  using  the  discrete   event  simulator  OMNeT++

-\cite{ref158}. The simulation  parameters are summarized in Table~\ref{table3}.  Each experiment  for  a network  is  run over  25~different random topologies and  the results presented hereafter are  the average of these
-25 runs.
+\cite{ref158}. The simulation  parameters are summarized in Table~\ref{table3}.  Each experiment  for  a network  is  run over  25~different random topologies and  the results presented hereafter are  the average of these 25 runs.

 %Based on the results of our proposed work in~\cite{idrees2014coverage}, we found as the region of interest are divided into larger subregions as the network lifetime increased. In this simulation, the network are divided into 16 subregions. 
 We  performed  simulations for  five  different  densities  varying from  50  to
 250~nodes deployed  over  a  $50 \times  25~m^2  $  sensing field.  More
 %Based on the results of our proposed work in~\cite{idrees2014coverage}, we found as the region of interest are divided into larger subregions as the network lifetime increased. In this simulation, the network are divided into 16 subregions. 
 We  performed  simulations for  five  different  densities  varying from  50  to
 250~nodes deployed  over  a  $50 \times  25~m^2  $  sensing field.  More

diff --git a/CHAPITRE_06.tex b/CHAPITRE_06.tex
index 31e696c7a48eb1326567ace6ad3e0a5746b68608..bd0cdf85febd998495428df599c3c83ba193cb95 100644 (file)
--- a/CHAPITRE_06.tex
+++ b/CHAPITRE_06.tex
@@ -7,29 +7,6 @@
 \chapter{Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}
 \label{ch6}
 
 \chapter{Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}
 \label{ch6}
 

-\iffalse
-
-\section{Summary}
-\label{ch6:sec:01}
-
-The most important problem in a Wireless Sensor Network (WSN) is to optimize the
-use of its limited energy provision so that it can fulfill its monitoring task
-as long as  possible. Among  known  available approaches  that can  be used  to
-improve  power  management,  lifetime coverage  optimization  provides  activity
-scheduling which ensures sensing coverage while minimizing the energy cost. In
-this paper,  we propose such an approach called Perimeter-based Coverage Optimization
-protocol (PeCO). It is a  hybrid of centralized and distributed methods: the
-region of interest is first subdivided into subregions and our protocol is then
-distributed among sensor nodes in each  subregion.
-The novelty of our approach lies essentially in the formulation of a new
-mathematical optimization  model based on the  perimeter coverage level  to schedule
-sensors' activities.  Extensive simulation experiments have been performed using
-OMNeT++, the  discrete event simulator, to  demonstrate that PeCO  can
-offer longer lifetime coverage for WSNs in comparison with some other protocols.
-
-
-\fi
-

 
 \section{Introduction}
 \label{ch6:sec:01}
 
 \section{Introduction}
 \label{ch6:sec:01}


@@ -412,7 +389,7 @@ be active during at most 20 periods.
 
 The values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good
 network coverage and a longer WSN lifetime.  We have given a higher priority to
 
 The values  of $\alpha^j_i$ and  $\beta^j_i$ have been  chosen to ensure  a good
 network coverage and a longer WSN lifetime.  We have given a higher priority to

-the  undercoverage  (by  setting  the  $\alpha^j_i$ with  a  larger  value  than
+the undercoverage  (by  setting  the  $\alpha^j_i$ with  a  larger  value  than

 $\beta^j_i$)  so as  to prevent  the non-coverage  for the  interval~$i$ of  the
 sensor~$j$.  On the  other hand,  we have assigned to
 $\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute
 $\beta^j_i$)  so as  to prevent  the non-coverage  for the  interval~$i$ of  the
 sensor~$j$.  On the  other hand,  we have assigned to
 $\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute

diff --git a/Thesis.toc b/Thesis.toc
index 2e06f6fa028ea7b977df8c072eb9cf32a1faaddd..76885fc01778b26bb5a8f5cb61735888a69a69f5 100644 (file)
--- a/Thesis.toc
+++ b/Thesis.toc
@@ -5,103 +5,103 @@
 \contentsline {chapter}{List of Algorithms}{9}{chapter*.4}
 \contentsline {chapter}{List of Acronyms}{9}{chapter*.4}
 \contentsline {chapter}{abbreviations}{11}{chapter*.5}
 \contentsline {chapter}{List of Algorithms}{9}{chapter*.4}
 \contentsline {chapter}{List of Acronyms}{9}{chapter*.4}
 \contentsline {chapter}{abbreviations}{11}{chapter*.5}

-\contentsline {chapter}{Abstract}{13}{chapter*.6}
-\contentsline {chapter}{Introduction }{15}{chapter*.7}
-\contentsline {section}{1. General Introduction }{15}{section*.8}
-\contentsline {section}{2. Motivation of the Dissertation }{16}{section*.9}
-\contentsline {section}{3. The Objective of this Dissertation}{16}{section*.10}
-\contentsline {section}{4. Main Contributions of this Dissertation}{16}{section*.11}
-\contentsline {section}{5. Dissertation Outline}{18}{section*.12}
-\contentsline {part}{I\hspace {1em}Scientific Background}{19}{part.1}
-\contentsline {chapter}{\numberline {1}Wireless Sensor Networks}{21}{chapter.1}
-\contentsline {section}{\numberline {1.1}Introduction}{21}{section.1.1}
-\contentsline {section}{\numberline {1.2}Architecture}{22}{section.1.2}
-\contentsline {section}{\numberline {1.3}Types of Wireless Sensor Networks}{24}{section.1.3}
-\contentsline {section}{\numberline {1.4}Applications}{26}{section.1.4}
-\contentsline {section}{\numberline {1.5}The Main Challenges}{29}{section.1.5}
-\contentsline {section}{\numberline {1.6}Energy-Efficient Mechanisms of a working WSN}{31}{section.1.6}
-\contentsline {subsection}{\numberline {1.6.1}Energy-Efficient Routing}{31}{subsection.1.6.1}
-\contentsline {subsubsection}{\numberline {1.6.1.1}Routing Metric based on Residual Energy}{31}{subsubsection.1.6.1.1}
-\contentsline {subsubsection}{\numberline {1.6.1.2}Multipath Routing}{31}{subsubsection.1.6.1.2}
-\contentsline {subsection}{\numberline {1.6.2}Cluster Architecture}{32}{subsection.1.6.2}
-\contentsline {subsection}{\numberline {1.6.3}Scheduling Schemes}{32}{subsection.1.6.3}
-\contentsline {subsubsection}{\numberline {1.6.3.1}Wake up Scheduling Schemes}{32}{subsubsection.1.6.3.1}
-\contentsline {subsubsection}{\numberline {1.6.3.2}Topology Control Schemes}{35}{subsubsection.1.6.3.2}
-\contentsline {subsection}{\numberline {1.6.4}Data-Driven Schemes}{35}{subsection.1.6.4}
-\contentsline {subsubsection}{\numberline {1.6.4.1}Data Reduction Schemes}{36}{subsubsection.1.6.4.1}
-\contentsline {subsubsection}{\numberline {1.6.4.2}Energy Efficient Data Acquisition Schemes}{36}{subsubsection.1.6.4.2}
-\contentsline {subsection}{\numberline {1.6.5}Battery Repletion}{36}{subsection.1.6.5}
-\contentsline {subsection}{\numberline {1.6.6}Radio Optimization}{36}{subsection.1.6.6}
-\contentsline {subsection}{\numberline {1.6.7}Relay nodes and Sink Mobility}{37}{subsection.1.6.7}
-\contentsline {subsubsection}{\numberline {1.6.7.1}Relay node placement}{37}{subsubsection.1.6.7.1}
-\contentsline {subsubsection}{\numberline {1.6.7.2}Sink Mobility}{37}{subsubsection.1.6.7.2}
-\contentsline {section}{\numberline {1.7}Network Lifetime}{37}{section.1.7}
-\contentsline {section}{\numberline {1.8}Coverage in Wireless Sensor Networks }{38}{section.1.8}
-\contentsline {section}{\numberline {1.9}Design Issues for Coverage Problems}{40}{section.1.9}
-\contentsline {section}{\numberline {1.10}Energy Consumption Model}{41}{section.1.10}
-\contentsline {section}{\numberline {1.11}Conclusion}{42}{section.1.11}
-\contentsline {chapter}{\numberline {2}Related Works on Coverage Problems}{43}{chapter.2}
-\contentsline {section}{\numberline {2.1}Introduction}{43}{section.2.1}
-\contentsline {section}{\numberline {2.2}Centralized Algorithms}{45}{section.2.2}
-\contentsline {section}{\numberline {2.3}Distributed Algorithms}{48}{section.2.3}
-\contentsline {subsection}{\numberline {2.3.1}GAF}{50}{subsection.2.3.1}
-\contentsline {subsection}{\numberline {2.3.2}DESK}{52}{subsection.2.3.2}
-\contentsline {section}{\numberline {2.4}Conclusion}{54}{section.2.4}
-\contentsline {chapter}{\numberline {3}Evaluation Tools and Optimization Solvers}{57}{chapter.3}
-\contentsline {section}{\numberline {3.1}Introduction}{57}{section.3.1}
-\contentsline {section}{\numberline {3.2}Evaluation Tools}{57}{section.3.2}
-\contentsline {subsection}{\numberline {3.2.1}Testbed Tools}{58}{subsection.3.2.1}
-\contentsline {subsection}{\numberline {3.2.2}Simulation Tools}{59}{subsection.3.2.2}
-\contentsline {section}{\numberline {3.3}Optimization Solvers}{64}{section.3.3}
-\contentsline {section}{\numberline {3.4}Conclusion}{67}{section.3.4}
-\contentsline {part}{II\hspace {1em}Contributions}{69}{part.2}
-\contentsline {chapter}{\numberline {4}Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{71}{chapter.4}
-\contentsline {section}{\numberline {4.1}Introduction}{71}{section.4.1}
-\contentsline {section}{\numberline {4.2}Description of the DiLCO Protocol}{72}{section.4.2}
-\contentsline {subsection}{\numberline {4.2.1}Assumptions and Network Model}{72}{subsection.4.2.1}
-\contentsline {subsection}{\numberline {4.2.2}Primary Point Coverage Model}{73}{subsection.4.2.2}
-\contentsline {subsection}{\numberline {4.2.3}Main Idea}{74}{subsection.4.2.3}
-\contentsline {subsubsection}{\numberline {4.2.3.1}Information Exchange Phase}{75}{subsubsection.4.2.3.1}
-\contentsline {subsubsection}{\numberline {4.2.3.2}Leader Election Phase}{75}{subsubsection.4.2.3.2}
-\contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{75}{subsubsection.4.2.3.3}
-\contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{75}{subsubsection.4.2.3.4}
-\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{76}{section.4.3}
-\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{78}{section.4.4}
-\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{78}{subsection.4.4.1}
-\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{78}{subsection.4.4.2}
-\contentsline {subsection}{\numberline {4.4.3}Energy Consumption Model}{78}{subsection.4.4.3}
-\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{79}{subsection.4.4.4}
-\contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Subregions}{80}{subsection.4.4.5}
-\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Primary Point Models}{86}{subsection.4.4.6}
-\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{91}{subsection.4.4.7}
-\contentsline {section}{\numberline {4.5}Conclusion}{97}{section.4.5}
-\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{99}{chapter.5}
-\contentsline {section}{\numberline {5.1}Introduction}{99}{section.5.1}
-\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{100}{section.5.2}
-\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{100}{subsection.5.2.1}
-\contentsline {section}{\numberline {5.3}Primary Points based Multiround Coverage Problem Formulation}{101}{section.5.3}
-\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{103}{section.5.4}
-\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{103}{subsection.5.4.1}
-\contentsline {subsection}{\numberline {5.4.2}Metrics}{104}{subsection.5.4.2}
-\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{105}{subsection.5.4.3}
-\contentsline {section}{\numberline {5.5}Conclusion}{110}{section.5.5}
-\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{113}{chapter.6}
-\contentsline {section}{\numberline {6.1}Introduction}{113}{section.6.1}
-\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{114}{section.6.2}
-\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{114}{subsection.6.2.1}
-\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{117}{subsection.6.2.2}
-\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{117}{subsection.6.2.3}
-\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{118}{section.6.3}
-\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{120}{section.6.4}
-\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{120}{subsection.6.4.1}
-\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{121}{subsection.6.4.2}
-\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{122}{subsubsection.6.4.2.1}
-\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{122}{subsubsection.6.4.2.2}
-\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{123}{subsubsection.6.4.2.3}
-\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{123}{subsubsection.6.4.2.4}
-\contentsline {section}{\numberline {6.5}Conclusion}{126}{section.6.5}
-\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{127}{part.3}
-\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{129}{chapter.7}
-\contentsline {section}{\numberline {7.1}Conclusion}{129}{section.7.1}
-\contentsline {section}{\numberline {7.2}Perspectives}{130}{section.7.2}
-\contentsline {part}{Bibliographie}{146}{chapter*.13}
+\contentsline {chapter}{Abstract}{15}{chapter*.6}
+\contentsline {chapter}{Introduction }{17}{chapter*.7}
+\contentsline {section}{1. General Introduction }{17}{section*.8}
+\contentsline {section}{2. Motivation of the Dissertation }{18}{section*.9}
+\contentsline {section}{3. The Objective of this Dissertation}{18}{section*.10}
+\contentsline {section}{4. Main Contributions of this Dissertation}{18}{section*.11}
+\contentsline {section}{5. Dissertation Outline}{20}{section*.12}
+\contentsline {part}{I\hspace {1em}Scientific Background}{21}{part.1}
+\contentsline {chapter}{\numberline {1}Wireless Sensor Networks}{23}{chapter.1}
+\contentsline {section}{\numberline {1.1}Introduction}{23}{section.1.1}
+\contentsline {section}{\numberline {1.2}Architecture}{24}{section.1.2}
+\contentsline {section}{\numberline {1.3}Types of Wireless Sensor Networks}{26}{section.1.3}
+\contentsline {section}{\numberline {1.4}Applications}{28}{section.1.4}
+\contentsline {section}{\numberline {1.5}The Main Challenges}{31}{section.1.5}
+\contentsline {section}{\numberline {1.6}Energy-Efficient Mechanisms of a working WSN}{33}{section.1.6}
+\contentsline {subsection}{\numberline {1.6.1}Energy-Efficient Routing}{33}{subsection.1.6.1}
+\contentsline {subsubsection}{\numberline {1.6.1.1}Routing Metric based on Residual Energy}{33}{subsubsection.1.6.1.1}
+\contentsline {subsubsection}{\numberline {1.6.1.2}Multipath Routing}{33}{subsubsection.1.6.1.2}
+\contentsline {subsection}{\numberline {1.6.2}Cluster Architecture}{34}{subsection.1.6.2}
+\contentsline {subsection}{\numberline {1.6.3}Scheduling Schemes}{34}{subsection.1.6.3}
+\contentsline {subsubsection}{\numberline {1.6.3.1}Wake up Scheduling Schemes}{34}{subsubsection.1.6.3.1}
+\contentsline {subsubsection}{\numberline {1.6.3.2}Topology Control Schemes}{37}{subsubsection.1.6.3.2}
+\contentsline {subsection}{\numberline {1.6.4}Data-Driven Schemes}{37}{subsection.1.6.4}
+\contentsline {subsubsection}{\numberline {1.6.4.1}Data Reduction Schemes}{38}{subsubsection.1.6.4.1}
+\contentsline {subsubsection}{\numberline {1.6.4.2}Energy Efficient Data Acquisition Schemes}{38}{subsubsection.1.6.4.2}
+\contentsline {subsection}{\numberline {1.6.5}Battery Repletion}{38}{subsection.1.6.5}
+\contentsline {subsection}{\numberline {1.6.6}Radio Optimization}{38}{subsection.1.6.6}
+\contentsline {subsection}{\numberline {1.6.7}Relay nodes and Sink Mobility}{39}{subsection.1.6.7}
+\contentsline {subsubsection}{\numberline {1.6.7.1}Relay node placement}{39}{subsubsection.1.6.7.1}
+\contentsline {subsubsection}{\numberline {1.6.7.2}Sink Mobility}{39}{subsubsection.1.6.7.2}
+\contentsline {section}{\numberline {1.7}Network Lifetime}{39}{section.1.7}
+\contentsline {section}{\numberline {1.8}Coverage in Wireless Sensor Networks }{40}{section.1.8}
+\contentsline {section}{\numberline {1.9}Design Issues for Coverage Problems}{42}{section.1.9}
+\contentsline {section}{\numberline {1.10}Energy Consumption Model}{43}{section.1.10}
+\contentsline {section}{\numberline {1.11}Conclusion}{44}{section.1.11}
+\contentsline {chapter}{\numberline {2}Related Works on Coverage Problems}{45}{chapter.2}
+\contentsline {section}{\numberline {2.1}Introduction}{45}{section.2.1}
+\contentsline {section}{\numberline {2.2}Centralized Algorithms}{47}{section.2.2}
+\contentsline {section}{\numberline {2.3}Distributed Algorithms}{50}{section.2.3}
+\contentsline {subsection}{\numberline {2.3.1}GAF}{52}{subsection.2.3.1}
+\contentsline {subsection}{\numberline {2.3.2}DESK}{53}{subsection.2.3.2}
+\contentsline {section}{\numberline {2.4}Conclusion}{56}{section.2.4}
+\contentsline {chapter}{\numberline {3}Evaluation Tools and Optimization Solvers}{59}{chapter.3}
+\contentsline {section}{\numberline {3.1}Introduction}{59}{section.3.1}
+\contentsline {section}{\numberline {3.2}Evaluation Tools}{59}{section.3.2}
+\contentsline {subsection}{\numberline {3.2.1}Testbed Tools}{60}{subsection.3.2.1}
+\contentsline {subsection}{\numberline {3.2.2}Simulation Tools}{61}{subsection.3.2.2}
+\contentsline {section}{\numberline {3.3}Optimization Solvers}{66}{section.3.3}
+\contentsline {section}{\numberline {3.4}Conclusion}{69}{section.3.4}
+\contentsline {part}{II\hspace {1em}Contributions}{71}{part.2}
+\contentsline {chapter}{\numberline {4}Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{73}{chapter.4}
+\contentsline {section}{\numberline {4.1}Introduction}{73}{section.4.1}
+\contentsline {section}{\numberline {4.2}Description of the DiLCO Protocol}{74}{section.4.2}
+\contentsline {subsection}{\numberline {4.2.1}Assumptions and Network Model}{74}{subsection.4.2.1}
+\contentsline {subsection}{\numberline {4.2.2}Primary Point Coverage Model}{75}{subsection.4.2.2}
+\contentsline {subsection}{\numberline {4.2.3}Main Idea}{76}{subsection.4.2.3}
+\contentsline {subsubsection}{\numberline {4.2.3.1}Information Exchange Phase}{77}{subsubsection.4.2.3.1}
+\contentsline {subsubsection}{\numberline {4.2.3.2}Leader Election Phase}{77}{subsubsection.4.2.3.2}
+\contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{77}{subsubsection.4.2.3.3}
+\contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{77}{subsubsection.4.2.3.4}
+\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{78}{section.4.3}
+\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{80}{section.4.4}
+\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{80}{subsection.4.4.1}
+\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{80}{subsection.4.4.2}
+\contentsline {subsection}{\numberline {4.4.3}Energy Consumption Model}{80}{subsection.4.4.3}
+\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{81}{subsection.4.4.4}
+\contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Subregions}{82}{subsection.4.4.5}
+\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Primary Point Models}{88}{subsection.4.4.6}
+\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{93}{subsection.4.4.7}
+\contentsline {section}{\numberline {4.5}Conclusion}{99}{section.4.5}
+\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{101}{chapter.5}
+\contentsline {section}{\numberline {5.1}Introduction}{101}{section.5.1}
+\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{102}{section.5.2}
+\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{102}{subsection.5.2.1}
+\contentsline {section}{\numberline {5.3}Primary Points based Multiround Coverage Problem Formulation}{103}{section.5.3}
+\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{105}{section.5.4}
+\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{105}{subsection.5.4.1}
+\contentsline {subsection}{\numberline {5.4.2}Metrics}{106}{subsection.5.4.2}
+\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{107}{subsection.5.4.3}
+\contentsline {section}{\numberline {5.5}Conclusion}{112}{section.5.5}
+\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{115}{chapter.6}
+\contentsline {section}{\numberline {6.1}Introduction}{115}{section.6.1}
+\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{116}{section.6.2}
+\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{116}{subsection.6.2.1}
+\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{119}{subsection.6.2.2}
+\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{119}{subsection.6.2.3}
+\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{120}{section.6.3}
+\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{122}{section.6.4}
+\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{122}{subsection.6.4.1}
+\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{123}{subsection.6.4.2}
+\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{124}{subsubsection.6.4.2.1}
+\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{124}{subsubsection.6.4.2.2}
+\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{125}{subsubsection.6.4.2.3}
+\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{125}{subsubsection.6.4.2.4}
+\contentsline {section}{\numberline {6.5}Conclusion}{128}{section.6.5}
+\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{129}{part.3}
+\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{131}{chapter.7}
+\contentsline {section}{\numberline {7.1}Conclusion}{131}{section.7.1}
+\contentsline {section}{\numberline {7.2}Perspectives}{132}{section.7.2}
+\contentsline {part}{Bibliographie}{148}{chapter*.13}