\item[SENSE] Sensor Network Simulator and Emulator
\item[GTSNetS] Georgia Tech Sensor Network Simulator
\item[GNU] GNU's Not Unix
+\item[LP] Linear Programming
\item[GLPK] GNU Linear Programming Kit
\item[MPS] Mathematical Programming System
-\item[COIN-OR] Linear Programming
+\item[COIN-OR] COmputational INfrastructure for Operations Research
\item[BCP] Branch Cut and Price
\item[CBC] COIN-OR Branch and Cut
\item[OPL] Optimization Programming Language
Nodes are deployed over caves, mines, or underground and communicate through soil~\cite{ref9,ref10}. The most important applications in underground WSNs are structural monitoring, agriculture monitoring, landscape management, underground environment monitoring of soil, water or mineral and military border monitoring. The essential challenges of underground WSNs are the high levels of attenuation and signal loss in communication. Therefore, it needs a certain type of devices able to provide a robust wireless underground communication. The risk on these devices comes from unsuitable underground conditions, replacing or recharging the battery seems to be impossible, and the WSN deployment is expensive.
\item \textbf{Underwater WSNs:}
-This type of WSNs is composed of wireless sensor nodes deployed in the water such as the ocean~\cite{ref11,ref12}. Many challenges must be faced in this type of WSN such as the high cost of the underwater sensor devices; underwater wireless communication with limited bandwidth, high latency, signal fading, and long propagation delay problems; sparse deployment in which the wireless sensors should be able to self-organized to adapt to various condition of the ocean environment; the limited power of the node battery, and the difficulty to replace or recharge it. These challenges led to look for energy efficient underwater wireless communication mechanisms. The main underwater WSNs applications are seismic monitoring, disaster prevention monitoring, underwater robotics, pollution monitoring, equipment monitoring, and undersea surveillance and exploration. \\
+This type of WSNs is composed of wireless sensor nodes deployed in the water such as the ocean~\cite{ref11,ref12}. Many challenges must be faced in this type of WSN such as the high cost of the underwater sensor devices; underwater wireless communication with limited bandwidth, high latency, signal fading, and long propagation delay problems; sparse deployment in which the wireless sensors should be able to self-organized to adapt to various condition of the ocean environment; the limited power of the node battery, and the difficulty to replace or recharge it. These challenges lead to look for energy efficient underwater wireless communication mechanisms. The main underwater WSNs applications are seismic monitoring, disaster prevention monitoring, underwater robotics, pollution monitoring, equipment monitoring, and undersea surveillance and exploration. \\
\item \textbf{Multimedia WSNs:}
They consist of inexpensive wireless sensor nodes supplied with CMOS (Complementary Metal-Oxide-Silicon) cameras or microphones devices. The nodes are deployed in a pre-guided way to ensure the coverage. Multimedia WSN is capable of retrieving and storing audio, video, and image contents from the physical environment~\cite{ref13,ref14,ref15}. Multimedia WSN contributed in improving some existing WSN applications such as tracking and monitoring. The main challenges in multimedia WSN include: the processing, filtering, and compressing of multimedia data; the requested bandwidth and high energy consumption; Quality-of-Service provisioning is very difficult because of the link capacity and delays; it should combine different wireless techniques; energy-efficient cross-layer design; it needs flexible architecture to support various applications; and the deployment is based on the multimedia devices coverage.
WSNs can be incorporated into military command, control, communication, computing, intelligence,
surveillance, reconnaissance, and targeting systems. It permits to estimate the unexpected events such as natural disasters and threats; military surveillance to the battlefield, enemy forces, battle damage, and targeting; and nuclear, biological, and chemical attack detection and reconnaissance~\cite{ref19}.
-\indent According to Figure~\ref{WSNAP}, the public safety and military applications can be categorized into active intervention and passive supervision~\cite{ref22}. In active intervention systems, the wireless sensors are wore by the agents and the WSN devoted to the security of the team activities. During the work of the team, the leader will observe the agent's situation and the environmental factors. The main applications include emergency rescue teams, miners, and soldiers. In passive supervision systems, wireless static sensors are scattered over a large field in order to monitor a civil area or nuclear site for a longer time. These applications include surveillance and target tracking; emergency navigation; fire detection in a building; structural health monitoring; and natural disaster prevention such as in the case of tsunamis, eruptions or flooding.
+\indent According to Figure~\ref{WSNAP}, the public safety and military applications can be categorized into active intervention and passive supervision~\cite{ref22}. In active intervention systems, the wireless sensors are worn by the agents and the WSN devoted to the security of the team activities. During the work of the team, the leader will observe the agent's situation and the environmental factors. The main applications include emergency rescue teams, miners, and soldiers. In passive supervision systems, wireless static sensors are scattered over a large field in order to monitor a civil area or nuclear site for a longer time. These applications include surveillance and target tracking; emergency navigation; fire detection in a building; structural health monitoring; and natural disaster prevention such as in the case of tsunamis, eruptions or flooding.
\item \textbf{Transportation Systems Applications:}
\indent In this strategy, the wireless sensor nodes are grouped into several groups called clusters. Each group of wireless sensor nodes is managed by a single sensor node, which is called cluster head. The cluster head takes the responsibility for managing the activities of the wireless sensor nodes in the cluster and it communicates and coordinates with other cluster heads or with the base station in the WSN. This mechanism conserves the energy in WSNs by means of~\cite{ref43,ref22}:
\begin{enumerate}[(a)]
-\item Grouping wireless sensor nodes into clusters led to decrease the communication range within the cluster. Therefore, the energy needed for communication among the nodes inside the cluster is minimized.
+\item Grouping wireless sensor nodes into clusters lead to decrease the communication range within the cluster. Therefore, the energy needed for communication among the nodes inside the cluster is minimized.
\item Minimizing the energy-hungry operations such as collaboration and aggregation to the cluster head.
%\item Limiting the number of communications (transmitting and receiving) due to the fusion operation carried out by the cluster head.
\item The continuous changing of cluster head according to the residual energy led to balance the energy consumption among wireless sensor nodes inside the cluster.
\indent The sensing quality and capability can be assessed by a sensing coverage model obtained through the identification of a mathematical relationship between the point and the sensor node in the sensing field. In the real world, there are sometimes obstacles in the environment that affect the sensing range \cite{ref104}. Therefore, several sensing coverage models have been suggested according to application requirements and physical working environment such as~\cite{ref103}: boolean sector coverage, boolean disk coverage, attenuated disk coverage, truncated attenuated disk, detection coverage, and estimation coverage models. However, two main sensing coverage models have been used for simulating the performance of wireless sensors~\cite{ref104,ref105,ref106}:
\begin{enumerate}[(A)]
-\item \textbf{Binary Disc Sensing Model:} It is the simplest sensing coverage model in which every point in the sensing field can be sensed if it is within the sensing range of the wireless sensor node. Otherwise, the sensor node is not able to detect any point that is outside its sensing range. The sensing range in this model can be viewed as a circular disk with a radius equal to $R_s$. Assume that a sensor node $s_i$ is deployed at the position $(x_i,y_i)$. For any point P at the position $(x,y)$, equation \ref{eq1-ch1} shows the binary sensor model that expresses the coverage $C_{xy}$ of the point P by sensor node $s_i$ as follow
+\item \textbf{Binary Disc Sensing Model:} It is the simplest sensing coverage model in which every point in the sensing field can be sensed if it is within the sensing range of the wireless sensor node. Otherwise, the sensor node is not able to detect any point that is outside its sensing range. The sensing range in this model can be viewed as a circular disk with a radius equal to $R_s$. Assume that a sensor node $s_i$ is deployed at the position $(x_i,y_i)$. For any point P at the position $(x,y)$, Equation \ref{eq1-ch1} shows the binary sensor model that expresses the coverage $C_{xy}$ of the point P by sensor node $s_i$ as follow
\begin{equation}
C_{xy}\left(s_i \right) = \left \{
\begin{array}{l l}
\end{enumerate}
-The coverage protocols proposed in this dissertation use the binary disc sensing model for each wireless sensor node in a WSN because it is widely used in the literature. Moreover, it is easy to formulate the linear programs with it, whereas the probabilistic model is more complex and it is difficult to use it to create integer programs.
+The coverage protocols proposed in this dissertation use the binary disc sensing model for each wireless sensor node in a WSN because it is widely used in the literature. Moreover, it is easy to formulate linear programs with it, whereas the probabilistic model is more complex. % and it is difficult to use it to create integer programs.
%The coverage protocols have proposed in this dissertation use the binary disc sensing model as a sensing coverage model for each wireless sensor node in WSN.
\item $\textbf{Deployment Method}$ refers to the way by which the wireless sensor nodes are deployed over the target sensing field in order to build the wireless sensor network. Generally, the sensor nodes can be placed either deterministically or randomly in the target sensing field~\cite{ref107}. The method of placement can be selected based on the type of sensors, application, and the environment. In the deterministic placement, the deployment can be achieved in a friendly environment with a small number of sensor nodes. The random placement is preferred for a large number of sensor nodes or when the area of interest is inaccessible or hostile. The sensor network can be either dense or sparse. On the one hand, the dense deployment is preferable when it is necessary to provide a security robustness in WSNs. On the other hand, the sparse deployment is used when the dense deployment is expensive or when the maximum coverage is performed by a low number of sensor nodes.
-\item $\textbf{Coverage Degree}$ refers to how many sensor nodes are required to cover a target or an area. A point in the sensing field is said to be K-coverage if it is covered by at least K sensor nodes. Some applications need a high reliability to achieve their tasks. Therefore, the sensing field is deployed densely so as to perform a K-coverage for this field. The simple coverage problem consists of a coverage degree equal to one (i.e., K=1), where every point in the sensing field is covered by at least one sensor.
+\item $\textbf{Coverage Degree}$ refers to how many sensor nodes are required to cover a target or an area. A point in the sensing field is said to be K-covered if it is covered by at least K sensor nodes. Some applications need a high reliability to achieve their tasks. Therefore, the sensing field is deployed densely so as to perform a K-coverage for this field. The simple coverage problem consists of a coverage degree equal to one (i.e., K=1), where every point in the sensing field is covered by at least one sensor.
\item $\textbf{Coverage Ratio}$ is the percentage of the sensing field that fulfills the coverage degree of the application. If all the points in the sensing field are covered, the coverage ratio is $100\%$ and it can be called a complete coverage. Otherwise, it is said as partial coverage.
%Activity based Scheduling schedules the activation and deactivation of sensor nodes during the network lifetime.
-\item $\textbf{Activity based Scheduling}$ schedules the activation and deactivation of sensor nodes during the network lifetime. The basic objective is to decide which sensors are in what states (active or sleeping mode) and for how long, so that the application coverage requirement can be guaranteed and the network lifetime can be prolonged. Various centralized, distributed, and localized approaches have been proposed for activity scheduling. In distributed algorithms, each node in the network autonomously makes decisions on whether to turn on or turn off itself, using only local neighbor information. In centralized algorithms, a central controller (a node or base station) informs every sensor of the time intervals to be activated.
+\item $\textbf{Activity based Scheduling}$ schedules the activation and deactivation of sensor nodes during the network lifetime. The basic objective is to decide which sensors are in which states (active or sleeping mode) and for how long, so that the application coverage requirement can be guaranteed and the network lifetime can be prolonged. Various centralized, distributed, and localized approaches have been proposed for activity scheduling. In distributed algorithms, each node in the network autonomously makes decisions on whether to turn on or turn off itself, using only local neighbor information. In centralized algorithms, a central controller (a node or base station) informs every sensor of the time intervals to be activated.
\textbf{This dissertation deals with activity based scheduling to ensure the best coverage}.
\end{enumerate}
\noindent The typical parameters are set as: $E_{elec}$ = 50 nJ/bit, $\varepsilon_{fs}$ = 10 pJ/bit/$m^2$, $\varepsilon_{mp}$ = 0.0013 pJ/bit/$m^4$. In addition, the energy for data aggregation is set to $E_{DA}$ = 5 nJ/bit.
\indent The radio energy dissipation model considers only the energy consumed by the communication part of the sensor node. However, in order to achieve a more accurate model, it is necessary to take into account the energy consumed by other parts inside the sensor node such as computation and sensing units.
-\textbf{In this dissertation, we developed another energy consumption model that based on \cite{ref112}}.
+\textbf{In this dissertation, we have based the energy consumption model on \cite{ref112}}.
%\subsection{Our Energy Consumption Model:}
%\label{ch1:sec9:subsec2}
This dissertation mainly focuses on the area coverage problem, where the ultimate goal is to choose the minimum number of sensor nodes to cover the whole sensing field.
%We have focused mainly on the area coverage problem. Therefore, we represent the sensing area of each sensor node in the sensing field as a set of primary points and then achieving full area coverage by covering all the points in the sensing field. The ultimate goal of the area coverage problem is to choose the minimum number of sensor nodes to cover the whole sensing region and prolonging the lifetime of the WSN.
-Many centralized and distributed coverage algorithms for activity scheduling have been proposed in the literature, based on different assumptions and objectives. In centralized algorithms, a central controller (base station) makes all decisions and distributes the results to sensor nodes. The centralized algorithms have the advantage of requiring very low processing power from the sensor nodes (except for the base station) which have usually limited processing capabilities. On the contrary, the exchange of packets in large WSNs may consume a considerable amount of energy in a centralized approach compared to a distributed one. The exchange of packets is between the sensor nodes and the base station. The centralized algorithms ensure nearly or close to optimal solution . They provide less redundant active sensor nodes during monitoring the sensing field. Moreover, centralized approaches usually suffer from the scalability and reliability problems, making them less competitive than the network size increases.
+Many centralized and distributed coverage algorithms for activity scheduling have been proposed in the literature, based on different assumptions and objectives. In centralized algorithms, a central controller (base station) makes all decisions and distributes the results to sensor nodes. The centralized algorithms have the advantage of requiring very low processing power from the sensor nodes (except for the base station) which have usually limited processing capabilities. On the contrary, the exchange of packets in large WSNs may consume a considerable amount of energy in a centralized approach compared to a distributed one. The exchange of packets is between the sensor nodes and the base station. Centralized algorithms provide solutions close to optimal solutions. They provide less redundant active sensor nodes during monitoring the sensing field. But, centralized approaches usually suffer from the scalability and reliability problems, making them less competitive than the network size increases.
In distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only informations from neighboring nodes are used for the activity decision. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give an optimal (or near-optimal) solution based only on local informations. They provide more redundant active sensor nodes during monitoring the sensing field. The exchange of packets is between the sensor nodes and their neighbors. Distributed algorithms are more robust against sensor failure. Moreover, a recent study conducted in \cite{ref226} concludes that there is a threshold in terms of network size to switch from a distributed to a centralized algorithm.
In the case of non-disjoint algorithms~\cite{ref117,ref167,ref144,ref147,ref118}, sensors may participate in more than one cover set. In some cases, this may prolong the lifetime of the network in comparison to the disjoint cover set algorithms, but designing algorithms for non-disjoint cover sets generally induces a higher order of complexity. Moreover, in case of a sensor's failure, non-disjoint scheduling policies are less resilient and reliable because a sensor may be involved in more than one cover sets. For instance,
%%%Cardei et al.~\cite{ref167} present a Linear Programming (LP) solution and a greedy approach to extend the sensor network lifetime by organizing the sensors into a maximal number of non-disjoint cover sets. Simulation results show that by allowing sensors to participate in multiple sets, the network lifetime increases compared with related work~\cite{ref115}.
-The authors in~\cite{ref148}, address the problem of minimum cost area coverage in which full coverage is performed by using the minimum number of sensors for an arbitrary geometric shape region. A geometric solution to the minimum cost coverage problem under a deterministic deployment is proposed. The probabilistic coverage solution which provides a relationship between the probability of coverage and the number of randomly deployed sensors in an arbitrarily-shaped region is suggested.
+the authors in~\cite{ref148}, address the problem of minimum cost area coverage in which full coverage is performed by using the minimum number of sensors for an arbitrary geometric shape region. A geometric solution to the minimum cost coverage problem under a deterministic deployment is proposed. The probabilistic coverage solution which provides a relationship between the probability of coverage and the number of randomly deployed sensors in an arbitrarily-shaped region is suggested.
%%%The work in~\cite{ref144} addresses the area coverage problem by proposing a Geometrically based Activity Scheduling scheme, named GAS, to fully cover the area of interest in WSNs. The authors deal with a small area, called target area coverage, which can be monitored by a single sensor instead of area coverage, which focuses on a large area that should be monitored by many sensors cooperatively. They explain that GAS is capable to monitor the target area by using the fewest number of sensors and it can produce as many cover sets as possible. A novel area coverage method to divide the sensors called Node Coverage Grouping (NCG) is suggested~\cite{ref147}. The sensors in the connectivity group are within sensing range of each other and the data collected by those in the same group are supposed to be similar. They prove that dividing N sensors via NCG into connectivity groups is an NP-hard problem. So, a heuristic algorithm of NCG with time complexity of $O(n^3)$ is proposed. For some applications, such as monitoring an ecosystem with extremely diversified environment, it might be a premature assumption that sensors near to each other sense similar data.
The problem of k-coverage over the area of interest in WSNs is addressed in~\cite{ref152}. It is mathematically formulated and the spatial sensor density for full k-coverage is determined. The relation between the communication range and the sensing range is constructed by this work to retain the k-coverage and connectivity in WSN. After that, four configuration protocols are proposed for treating the k-coverage in WSNs. Simulation results show that their protocols outperform an existing distributed k-coverage configuration protocol. The work presented in~\cite{ref151} solves the area coverage and connectivity problem in sensor networks in an integrated way. The network lifetime is divided into a fixed number of rounds. A coverage bitmap of sensors of the domain is generated in each round and based on this bitmap, it is decided which sensors stay active or go to sleep. They check the connection of the graph via laplacian of the adjacency graph of active sensors in each round. They define the connected coverage problem as an optimization problem and a centralized genetic algorithm is used to find the solution. Recent studies show an increasing interest in the use of exact schemes to solve optimization problems in WSNs \cite{ref230,ref231,ref121,ref122,ref120}. Column Generation (CG) has been widely used to address different versions of Maximum-network Lifetime Problem (MLP). CG decomposes the problem into a Restricted Master Problem (RMP) and a Pricing Subproblem (PS). The former maximizes lifetime using an incomplete set of columns and the latter is used to identify new profitable columns.
%%%A. Rossi et al.~\cite{ref121} introduce an efficient implementation of a genetic algorithm based on CG to extend the lifetime and maximize target coverage in wireless sensor networks under bandwidth constraints. The authors show that the use of metaheuristic methods to solve PS in the context of CG allows to obtain optimal solutions quite fast and to produce high-quality solutions when the algorithm is stopped before returning an optimal solution. More recently,
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, is in 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 consider 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. 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 deciding 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.
+M. Rebai et al.~\cite{ref141}, formulate the problem of full grid area coverage problem using two integer linear programming models: the first, is 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 consider 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. 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 deciding 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.
\label{gaf1}
\end{figure}
-For two adjacent squares grids, (for example, A and B in Figure~\ref{gaf1}) all sensor nodes inside A can communicate with sensor nodes inside B and vice versa. Therefore, all the sensor nodes are equivalent from the point of view the routing. The size of the fixed grid is based on the radio communication range $R_c$. It is supposed that the fixed grid is square with $r$ units on a side as shown in Figure~\ref{gaf1}. The distance between the farthest sensor nodes in two adjacent squares, such as B and C in Figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of square grid C. Thus,
+For two adjacent squares grids, (for example, A and B in Figure~\ref{gaf1}) all sensor nodes inside A can communicate with sensor nodes inside B and vice versa. Therefore, all the sensor nodes are equivalent from the point of view of the routing. The size of the fixed grid is based on the radio communication range $R_c$. It is supposed that the fixed grid is square with $r$ units on a side as shown in Figure~\ref{gaf1}. The distance between the farthest sensor nodes in two adjacent squares, such as B and C in Figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of square grid C. Thus,
\begin{eqnarray}
\item \textbf{CLP:}
-The COIN-OR Linear Programming (CLP)~\cite{ref216,ref217} is a free, open-source, linear programming solver written in C++ programming language. It is reliable and able to tackle the very large linear optimization problems. The CLP is a part of the Coin-OR project that aims at creating open software for the operations research community. COIN-OR projects such as SYMPHONY, BCP (Branch Cut and Price), and CBC (COIN-OR Branch and Cut) also used CLP. It includes Dual and Primal Simplex algorithms, but it also contains an Interior Point algorithm. The CLP is available under the Eclipse Public License version 1.0, and the users interact with it through either an interactive command line or through a C++ API. The CLP is able to use the input MPS, Free MPS, and LP file formats.
+The COIN-OR Linear Programming (CLP)~\cite{ref216,ref217} is a free, open-source, linear programming solver written in C++ programming language. It is reliable and able to tackle the very large linear optimization problems. The CLP is a part of the Coin-OR project that aims at creating open software for the operations research community. COIN-OR projects such as SYMPHONY, BCP (Branch Cut and Price), and CBC (COIN-OR Branch and Cut) also uses CLP. It includes Dual and Primal Simplex algorithms, but it also contains an Interior Point algorithm. The CLP is available under the Eclipse Public License version 1.0, and the users interact with it through either an interactive command line or through a C++ API. The CLP is able to use the input MPS, Free MPS, and LP file formats.
\item \textbf{CPLEX:}
-The IBM ILOG CPLEX Optimization Studio (often informally referred to simply as CPLEX)~\cite{ref218,ref211} is a commercial, analytical decision support, and optimization software toolkit for fast development of optimization models using mathematical and constraint programming. It combines an integrated development environment (IDE) with the powerful Optimization Programming Language (OPL) and high-performance ILOG CPLEX optimizer solvers. The CPLEX is developed by IBM and is designed to tackle the large-scale (mixed integer) linear problems. The CPLEX optimizer includes a modeling layer called "Concert" that provides interfaces to the C++, C$\#$, Python, and Java languages. Furthermore, it provides a connection to Microsoft Excel and MATLAB. The CPLEX is capable of optimizing the business decisions with high-performance optimization engines. It develops and deploys optimization models quickly by using flexible interfaces and pre-constructed deployment scenarios. In addition, it creates real-world applications.
+The IBM ILOG CPLEX Optimization Studio (often informally referred to simply as CPLEX)~\cite{ref218,ref211} is a commercial, analytical decision support, and optimization software toolkit for fast development of optimization models using mathematical and constraint programming. It combines an integrated development environment (IDE) with the powerful Optimization Programming Language (OPL) and high-performance ILOG CPLEX optimizer solvers. The CPLEX is developed by IBM and is designed to tackle the large-scale (mixed integer) linear problems. The CPLEX optimizer includes a modeling layer called "Concert" that provides interfaces to the C++, C$\#$, Python, and Java languages. Furthermore, it provides a connection to Microsoft Excel and MATLAB. The CPLEX is capable of optimizing the business decisions with high-performance optimization engines. It develops and deploys optimization models quickly by using flexible interfaces and pre-constructed deployment scenarios. %In addition, it creates real-world applications.
\item \textbf{Gurobi:}
B. Meindl and M. Templ~\cite{ref212} studied the efficiency of above optimization solvers. They used a set of instances of difficult optimization problems called the attacker problems in order to achieve a performance comparison of GLPK, lp$\_$solve, CLP, GUROBI, and CPLEX optimization solvers. They considered a total of 200 problem instances for this study, 100 of these problem instances are based on problems with two dimensions, and 100 problem instances are three-dimensional.
-In tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} we report the result of their comparison the running times of the five linear program solvers to find solutions to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling.
+In tables~\ref{my-label1}, \ref{my-label2}, and \ref{my-label3} we report the result of their comparisons the running times of the five linear program solvers to find solutions to the 200 two-dimensional, 200 three-dimensional, and all 400 problem instances. In order to solve the attacker’s problem for a given problem instance, it is needed to both minimize and maximize any given problem. Therefore, a total of 400 problem instances had been solved when only 200 problem instances have been generated. The running time of the fastest solver has been scaled to one and the running times of the other linear solvers were scaled to reflect this scaling.
\begin{table}[h]
\item The GLPK comes with a stand-alone solver, a callable library, and the modeling language GMPL. The GMPL is compatible with AMPL and is extremely easy to learn.
\item Modeling language and solver can be used independently.
\item GUI is available for Windows, Mac OS X, and Linux. Java, Python, and Matlab interfaces are available.
-\item Database support and formatted text output.
-\item Exact simplex algorithm and branch-and-bound method are integrated with GLPK.
+%\item Database support and formatted text output.
+%\item Exact simplex algorithm and branch-and-bound method are integrated with GLPK.
\end{enumerate}
\section{Conclusion}
\label{ch3:4}
-\indent In this chapter, an overview of the evaluation tools for wireless sensor networks and optimization solvers has been presented. Major testbeds for wireless sensor network have been demonstrated. We have found that most researchers in the field of WSNs use the simulators to evaluate theirs works because they are free, easy to use, more flexible, and scalable for large WSNs. Several simulators for wireless sensor networks are described. The comparison among some types of network simulators show that OMNeT++ simulator is a good candidate to be used as performance evaluation tool to evaluate the efficiency of our protocols in this dissertation. This chapter also highlightes the optimization problem in WSNs and the most popular free and commercial linear optimization solvers. The commercial optimization solvers outperform the free optimization solvers. GLPK has been chosen as a good candidate to solve the proposed optimization problems in this dissertation because it is free, easy to use, and better than some other free optimization solvers.
\ No newline at end of file
+\indent In this chapter, an overview of the evaluation tools for wireless sensor networks and optimization solvers has been presented. Major testbeds for wireless sensor network have been demonstrated. We have found that most researchers in the field of WSNs use the simulators to evaluate theirs works because they are free, easy to use, more flexible, and scalable for large WSNs. Several simulators for wireless sensor networks are described. The comparison among some types of network simulators show that OMNeT++ simulator is a good candidate to be used as performance evaluation tool to evaluate the efficiency of our protocols in this dissertation. This chapter also highlights the optimization problem in WSNs and the most popular free and commercial linear optimization solvers. The commercial optimization solvers outperform the free optimization solvers. GLPK has been chosen as a good candidate to solve the proposed optimization problems in this dissertation because it is free, easy to use, and better than some other free optimization solvers.
\ No newline at end of file
\noindent We consider a sensor network composed of static nodes distributed independently and uniformly at random. A high-density deployment ensures a high coverage ratio of the interested area at the start. The nodes are supposed to have homogeneous characteristics from a communication and a processing point of view, whereas they have heterogeneous energy provisions. Each node has access to its location thanks, either to a hardware component (like a GPS unit) or a location discovery algorithm. Furthermore, we assume that sensor nodes are time synchronized in order to properly coordinate their operations to achieve complex sensing tasks~\cite{ref157}. Two sensor nodes are supposed to be neighbors if the euclidean distance between them is at most equal to 2$R_s$, where $R_s$ is the sensing range.
-\indent We consider a boolean disk coverage model which is the most widely used sensor coverage model in the literature. Thus, since a sensor has a constant sensing range $R_s$, each space point within a disk centered at a sensor with the radius of the sensing range is said to be covered with this sensor. We also assume that the communication range $R_c$ is at least twice the sensing range $R_s$ (i.e., $R_c \geq 2R_s$). In fact, Zhang and Hou~\cite{ref126} proved that if the transmission range fulfills the previous hypothesis, a complete coverage of a convex area implies connectivity among the working nodes in the active mode. we consider multi-hop communication.
+\indent We consider a boolean disk coverage model which is the most widely used sensor coverage model in the literature. Thus, since a sensor has a constant sensing range $R_s$, each space point within a disk centered at a sensor with the radius of the sensing range is said to be covered with this sensor. We also assume that the communication range $R_c$ is at least twice the sensing range $R_s$ (i.e., $R_c \geq 2R_s$). In fact, Zhang and Hou~\cite{ref126} proved that if the transmission range fulfills the previous hypothesis, a complete coverage of a convex area implies connectivity among the working nodes in the active mode. We consider multi-hop communication.
%We assume that each sensor node can directly transmit its measurements toward a mobile sink node.
%For example, a sink can be an unmanned aerial vehicle (UAV) flying regularly over the sensor field to collect measurements from sensor nodes. The mobile sink node collects the measurements and transmits them to the base station.
\begin{enumerate} [(i)]
\item \textbf{INFO packet:} sent by each sensor node to all the nodes inside a same subregion for information exchange.
-\item \textbf{ActiveSleep packet:} sent by the leader to all the nodes in its subregion to inform them to stay Active or to go Sleep during the sensing phase.
+\item \textbf{ActiveSleep packet:} sent by the leader to all the nodes in its subregion to inform them to stay Active or to go to Sleep during the sensing phase.
\end{enumerate}
There are five possible status for each sensor node in the network:
Simulations with five different node densities going from 50 to 250~nodes were
performed considering each time 25~randomly generated networks, to obtain
-experimental results which are relevant. The nodes are deployed on a field of
+experimental results which are relevant. The nodes are uniformly deployed on a field of
interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
high coverage ratio.
\subsection{Performance Analysis for Different Number of Primary Points}
\label{ch4:sec:04:06}
-In this section, we study the performance of DiLCO~16 approach for different numbers of primary points. The objective of this comparison is to select the suitable primary point model to be used by a DiLCO protocol. In this comparison, DiLCO-16 protocol is used with five models, which are called Model-5 (it uses 5 primary points), Model-9, Model-13, Model-17, and Model-21.
+In this section, we study the performance of DiLCO-16 approach for different numbers of primary points. The objective of this comparison is to select the suitable primary point model to be used by a DiLCO protocol. In this comparison, DiLCO-16 protocol is used with five models, which are called Model-5 (it uses 5 primary points), Model-9, Model-13, Model-17, and Model-21.
\begin{enumerate}[i)]
\end{figure}
The results presented in Figure~\ref{Figures/ch4/R2/ASR} show the superiority of the proposed Model-5, in comparison with the other models. The model with fewer number of primary points uses fewer active nodes than the other models.
-According to the results presented in Figure~\ref{Figures/ch4/R2/CR}, we observe that Model-5 continues to a larger number of periods with a better coverage ratio compared with other models. The advantage of Model-5 is to use fewer number of active nodes for each period compared with Model-9, Model-13, Model-17, and Model-21. This led to continuing for a larger number of periods and thus extending the network lifetime.
+According to the results presented in Figure~\ref{Figures/ch4/R2/CR}, we observe that Model-5 continues for a larger number of periods with a better coverage ratio compared with other models. The advantage of Model-5 is to use fewer number of active nodes for each period compared with Model-9, Model-13, Model-17, and Model-21. This led to continuing for a larger number of periods and thus extending the network lifetime.
\item {{\bf Stopped simulation runs}}
\label{Figures/ch4/R2/T}
\end{figure}
-They are given for the different primary point models and various numbers of sensors. We can see from Figure~\ref{Figures/ch4/R2/T}, that Model-5 has lower execution time in comparison with other models because it used the smaller number of primary points to represent the area of the sensor. Conversely, the other primary point models have presented higher execution times.
+They are given for the different primary point models and various numbers of sensors. We can see from Figure~\ref{Figures/ch4/R2/T}, that Model-5 has lower execution time in comparison with other models because it uses the smaller number of primary points to represent the area of the sensor. Conversely, the other primary point models have presented higher execution times.
Moreover, Model-5 has more suitable execution times and coverage ratio that lead to continue for a larger number of period extending the network lifetime. We think that a good primary point model is one that balances between the coverage ratio and the number of periods during the lifetime of the network.
\item {{\bf Network Lifetime}}
Moreover, when the number of periods increases, coverage ratio produced by DESK and GAF protocols decreases.
%This is due to dead nodes. However, DiLCO-16 protocol and DiLCO-32 protocol maintain almost a good coverage.
-GAF exhibits in particular a fast decrease. Our protocols also provide decreasing coverage ratio, but far more better than those of DESK and GAF. DiLCO-16 and DiLCO-32 clearly outperform DESK and GAF for number of periods between 32 and 103.
+GAF exhibits in particular a fast decrease. Our protocols also provide decreasing coverage ratio, but far less large than those of DESK and GAF. DiLCO-16 and DiLCO-32 clearly outperform DESK and GAF for number of periods between 32 and 103.
This is because they optimize the coverage and the lifetime in wireless sensor network by selecting the best representative sensor nodes to take the responsibility of coverage during the sensing phase.
%, and this will lead to continuing for a larger number of periods and prolonging the network lifetime. Furthermore, although some nodes are dead, sensor activity scheduling of our protocol chooses other nodes to ensure the coverage of the area of interest.
\end{figure}
-This protocol minimizes the impact of unexpected node failure (not due to batteries running out of energy), because it works in periods. On the one hand, if a node failure is detected before making the decision, the node will not participate during this phase. On the other hand, if the node failure occurs after the decision, the sensing task of the network will be temporarily affected: only during the period of sensing until a new period starts.
+%This protocol minimizes the impact of unexpected node failure (not due to batteries running out of energy), because it works in periods. On the one hand, if a node failure is detected before making the decision, the node will not participate during this phase. On the other hand, if the node failure occurs after the decision, the sensing task of the network will be temporarily affected: only during the period of sensing until a new period starts.
-The energy consumption and some other constraints can easily be taken into account since the sensors can update and then exchange their information (including their residual energy) at the beginning of each period. However, the pre-sensing phases (Information Exchange, Leader Election, and Decision) are energy consuming for some nodes, even when they do not join the network to monitor the area.
+%The energy consumption and some other constraints can easily be taken into account since the sensors can update and then exchange their information (including their residual energy) at the beginning of each period. However, the pre-sensing phases (Information Exchange, Leader Election, and Decision) are energy consuming for some nodes, even when they do not join the network to monitor the area.
\label{ch5:sec:03}
-According to Algorithm~\ref{alg:MuDiLCO}, the integer program is based on the model
-proposed by \cite{ref156} with some modifications, where the objective of our model is
-to find a maximum number of non-disjoint cover sets.
+%According to Algorithm~\ref{alg:MuDiLCO}, the integer program is based on the model proposed by \cite{ref156} with some modifications, where the objective of our model is to find a maximum number of non-disjoint cover sets.
%To fulfill this goal, the authors proposed an integer program which forces undercoverage and overcoverage of targets to become minimal at the same time. They use binary variables $x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our model,
-We consider binary variables $X_{t,j}$ to determine the possibility of activating
-sensor $j$ during round $t$ of a given sensing phase. We also consider primary
-points as targets. The set of primary points is denoted by $P$ and the set of
-sensors by $J$. Only sensors able to be alive during at least one round are
-involved in the integer program.
+%We consider binary variables $X_{t,j}$ to determine the possibility of activating sensor $j$ during round $t$ of a given sensing phase. We also consider primary points as targets. The set of primary points is denoted by $P$ and the set of sensors by $J$. Only sensors able to be alive during at least one round are involved in the integer program.
+We extend the mathematical formulation given in section \ref{ch4:sec:03} to take into account multiple rounds.
For a primary point $p$, let $\alpha_{j,p}$ denote the indicator function of
whether the point $p$ is covered, that is
covered).
\end{itemize}
-The first group of constraints indicates that some primary point $p$ should be
-covered by at least one sensor and, if it is not always the case, overcoverage
-and undercoverage variables help balancing the restriction equations by taking
-positive values. The constraint given by equation~(\ref{eq144}) guarantees that
-the sensor has enough energy ($RE_j$ corresponds to its remaining energy) to be
-alive during the selected rounds knowing that $E_{th}$ is the amount of energy
-required to be alive during one round.
+%The first group of constraints indicates that some primary point $p$ should be covered by at least one sensor and, if it is not always the case, overcoverage and undercoverage variables help balancing the restriction equations by taking positive values.
+The constraint given by equation~(\ref{eq144}) guarantees that the sensor has enough energy ($RE_j$ corresponds to its remaining energy) to be alive during the selected rounds knowing that $E_{th}$ is the amount of energy required to be alive during one round.
-There are two main objectives. First, we limit the overcoverage of primary
-points in order to activate a minimum number of sensors. Second we prevent the
-absence of monitoring on some parts of the subregion by minimizing the
-undercoverage. The weights $W_\theta$ and $W_U$ must be properly chosen so as
-to guarantee that the maximum number of points are covered during each round.
-%% MS W_theta is smaller than W_u => problem with the following sentence
-In our simulations, priority is given to the coverage by choosing $W_{U}$ very
-large compared to $W_{\theta}$.
+%There are two main objectives. First, we limit the overcoverage of primary points in order to activate a minimum number of sensors. Second we prevent the absence of monitoring on some parts of the subregion by minimizing the undercoverage. The weights $W_\theta$ and $W_U$ must be properly chosen so as to guarantee that the maximum number of points are covered during each round. In our simulations, priority is given to the coverage by choosing $W_{U}$ very large compared to $W_{\theta}$.
%\subsection{Active sensors ratio}
%\label{ch5:sec:03:02:02}
-It is crucial to have as few active nodes as possible in each round, in order to
-minimize the communication overhead and maximize the network
-lifetime. Figure~\ref{fig4} presents the active sensor ratio for 150 deployed
+%It is crucial to have as few active nodes as possible in each round, in order to minimize the communication overhead and maximize the network lifetime.
+Figure~\ref{fig4} presents the active sensor ratio for 150 deployed
nodes all along the network lifetime. It appears that up to round thirteen, DESK
and GAF have respectively 37.6\% and 44.8\% of nodes in active mode, whereas
MuDiLCO clearly outperforms them with only 23.7\% of active nodes. After the
\item We design a protocol, called the Distributed Lifetime Coverage Optimization (DILCO) protocol, which maintains the coverage and improves the lifetime in WSNs. DILCO protocol is presented in chapter 4. It is an extension of our approach introduced in \cite{ref159}. In \cite{ref159}, the protocol is deployed over only two subregions. In the DILCO protocol, the area of interest is first divided into subregions using a divide-and-conquer algorithm and an activity scheduling for sensor nodes is then planned by the elected leader in each subregion. In fact, the nodes in a subregion can be seen as a cluster where each node sends sensing data to the cluster head or the sink node. Furthermore, the activities in a subregion/cluster can continue even if another cluster stops due to too many node failures. DiLCO protocol considers periods, where a period starts with a discovery phase to exchange information between sensors of the same subregion, in order to choose in a suitable manner a sensor node (the leader) to carry out the coverage strategy. In each subregion, the activation of the sensors for the sensing phase of the current period is obtained by solving an integer program. The resulting activation vector is broadcasted by the leader to every node of its subregion.
\item %We extend our work that explained in chapter 4 and present a generalized framework that can be applied to provide the cover sets of all rounds in each period.
-The MuDiLCO protocol for Multiround Distributed Lifetime Coverage Optimization protocol, presented in chapter 5, is an extension of the approach introduced in chapter 4. In the DiLCO protocol, the activity scheduling based optimization is planned for each subregion periodically only for one sensing round. Whilst, we study the possibility of dividing the sensing phase into multiple rounds. In fact, we make a multiround optimization, while it was a single round optimization in our previous contribution. The activation of the sensors is planned for many rounds in advance compared with the previous approach.
+The MuDiLCO protocol for Multiround Distributed Lifetime Coverage Optimization protocol, presented in chapter 5, is an extension of the approach introduced in chapter 4. In the DiLCO protocol, the activity scheduling based optimization is planned for each subregion periodically only for one sensing round. We study the possibility of dividing the sensing phase into multiple rounds. In fact, we make a multiround optimization, while it was a single round optimization in our previous contribution. The activation of the sensors is planned for many rounds in advance compared with the previous approach.
%\item We devise a framework to schedule nodes to be activated alternatively such that the network lifetime is prolonged while ensuring that a certain level of coverage is preserved. A key idea in our framework is to exploit the spatial-temporal subdivision. On the one hand, the area of interest is divided into several smaller subregions and, on the other hand, the timeline is divided into periods of equal length. In each subregion, the sensor nodes will cooperatively choose a leader which will schedule nodes' activities, and this grouping of sensors is similar to typical cluster architecture.
\item We design a third protocol, called Perimeter-based Coverage Optimization (PeCO).
%which schedules nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. This protocol is applied in a distributed way in regular subregions obtained after partitioning the area of interest in a preliminary step. It works in periods and is based on the resolution of an integer program to select the subset of sensors operating in active status for each period.
-We have proposed a new mathematical optimization model. Instead of trying to cover a set of specified points/targets as in my previous protocols and most of the methods proposed in the literature, we formulate an integer program based on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations. This contribution is demonstrated in chapter 6.
+We have proposed a new mathematical optimization model. Instead of trying to cover a set of specified points/targets as in previous protocols and most of the methods proposed in the literature, we formulate mixed-integer program based on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required level. The idea is that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations. This contribution is demonstrated in chapter 6.
-\item We add an improved model of energy consumption to assess the efficiency of our protocols. We conducted extensive simulation experiments using the discrete event simulator OMNeT++, to demonstrate the efficiency of our protocols. We compared our proposed distributed optimization protocols to two approaches found in the literature: DESK~\cite{DESK} and GAF~\cite{GAF}. Simulation results based on multiple criteria (energy consumption, coverage ratio, network lifetime and so on) show that the proposed protocols can prolong efficiently the network lifetime and improve the coverage performance.
+\item %We add an improved model of energy consumption to assess the efficiency of our protocols.
+We conducted extensive simulation experiments using the discrete event simulator OMNeT++, to demonstrate the efficiency of our protocols. We compared our proposed distributed optimization protocols with two approaches found in the literature: DESK~\cite{DESK} and GAF~\cite{GAF}. Simulation results based on multiple criteria (energy consumption, coverage ratio, network lifetime and so on) show that the proposed protocols can prolong efficiently the network lifetime and improve the coverage performance.
\end{enumerate}
\contentsline {section}{\numberline {5.1}Introduction}{101}{section.5.1}
\contentsline {section}{\numberline {5.2}Description of the MuDiLCO Protocol }{101}{section.5.2}
\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 {section}{\numberline {5.4}Experimental Study and Analysis}{104}{section.5.4}
+\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{104}{subsection.5.4.1}
\contentsline {subsection}{\numberline {5.4.2}Metrics}{105}{subsection.5.4.2}
\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{106}{subsection.5.4.3}
\contentsline {section}{\numberline {5.5}Conclusion}{112}{section.5.5}
