\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}
\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 have based the energy consumption model on \cite{ref112}}.
+\textbf{In this dissertation, we have based the energy consumption model on \cite{ref112}. This model will be detailed in Section \ref{ch4:sec:04:03}}.
%\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. 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.
+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 when 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.
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 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. GAF algorithm is chosen for comparison as a competitor because it is famous and easy to implement, as well as many authors referred to it in many publications. DESK algorithm is also selected as competitor in the comparison because it works into rounds fashion (network lifetime divides into rounds) similar to our approaches, as well as DESK is a full distributed coverage approach.
+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. GAF algorithm is chosen for comparison as a competitor because it is famous and easy to implement, as well as many authors referred to it in many publications. DESK algorithm is also selected as competitor in the comparison because it works into rounds fashion (network lifetime divided into rounds) similar to our approaches, as well as DESK is a full distributed coverage approach.
\subsection{Geographical Adaptive Fidelity (GAF)}
r \leq \dfrac{R_c}{\sqrt{5}}
\end{eqnarray}
-The sensor nodes in GAF can be in one of the folling three states: Active, Sleeping, or Discovery. Figure~\ref{gaf2} shows the state transition diagram. Each sensor node is initiated with discovery state.
+The sensor nodes in GAF can be in one of the following three states: Active, Sleeping, or Discovery. Figure~\ref{gaf2} shows the state transition diagram. Each sensor node is initiated with discovery state.
In discovery state, the radio of each sensor node is turned on. Thereafter, the discovery messages are exchanged among the sensor nodes within the same grid. The discovery message consists of four fields, node id, grid id, estimated node active time (enat), and node state. The node uses its location and grid size to determine the square grid id.
\begin{figure}[h!]
\label{ch2:sec:05}
This chapter describes some coverage problems in the literature, with their assumptions and proposed solutions.
The coverage is considered as an essential requirement for many applications in WSNs because the better the coverage of an area of interest is, the better the sensing measurements of the physical phenomenon also is. 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 the one hand, the full centralized coverage algorithms provide optimal or near optimal solution with low computation power for the sensors (except for the base station) but they deplete the battery power due to the communication overhead, so 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 the communication between neighbors may be large especially for dense networks. Distributed coverage algorithms are reliable and scalable. 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. Such an hybrid approach can provide a good quality coverage and prolong the network lifetime.
+Many coverage algorithms for maintaining the coverage and improving the network lifetime in WSNs were proposed. On the one hand, the full centralized coverage algorithms provide optimal or near optimal solution with low computation power for the sensors (except for the base station) but they deplete the battery power due to the communication overhead, so 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 the communication between neighbors may be large especially for dense networks. Distributed coverage algorithms are reliable and scalable. The two coverage approaches have 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. Such an hybrid approach can provide a good quality coverage and prolong the network lifetime.
%In this dissertation, we use linear programming because we used integer programs to optimize the coverage and the lifetime in WSNs.
In this dissertation, we optimize the coverage and the lifetime in WSNs and the problem is formulated through linear programming. These kind of models allow to obtain optimal solutions satisfying an objective (for instance, maximize coverage) under constraints (for instance, available remaining energy).
-The remainder of this chapter is organized as follows. The next section is devoted to the evaluation tools for evaluating and validating the performance of proposed algorithms and protocols. Section \ref{ch3:3} gives the most popular free and commercial linear optimization solvers to solve the linear programming problems. Finally, we give concluding remarks in section \ref{ch3:4}.
+The remainder of this chapter is organized as follows. The next section is devoted to the evaluation tools for evaluating and validating the performance of proposed algorithms and protocols. Section \ref{ch3:3} gives the most popular free and commercial linear optimization solvers to solve linear programming problems. Finally, we give concluding remarks in section \ref{ch3:4}.
\section{Evaluation Tools}
\label{ch3:2}
\item \textbf{WISEBED:}
-The WISEBED~\cite{ref183} is a large-scale WSN testbed with a hierarchical architecture that consists of four major parts: wireless sensor nodes, gateways, portal server, and overlay network. The lowest level of the hierarchy corresponds to the WSN in which a set of these sensor nodes is connected to the gateway to provide access to the other remaining sensor nodes. The gateways are connected to a portal server, which not only supervises the WSN, but also allows user interactions with the testbed. Each WISBED site includes separate portal server. The major goal of this testbed is to provide a multi-level infrastructure of interconnected testbeds of large scale wireless sensor networks for research purposes. It provides an interdisciplinary approach which integrates the hardware, software, algorithms, and data. WISEBED provides heterogeneous large-scale structure because it brings several heterogeneous small-scale devices together to form a large-scale network structure. It provides the research with different quality networks due to the heterogeneous structure of the network.
+The WISEBED~\cite{ref183} is a large-scale WSN testbed with a hierarchical architecture that consists of four major parts: wireless sensor nodes, gateways, portal server, and overlay network. The lowest level of the hierarchy corresponds to the WSN in which a set of these sensor nodes is connected to the gateway to provide access to the other remaining sensor nodes. The gateways are connected to a portal server, which not only supervises the WSN, but also allows user interactions with the testbed. Each WISBED site includes separate portal server. The major goal of this testbed is to provide a multi-level infrastructure of interconnected testbeds of large scale wireless sensor networks for research purposes. It provides an interdisciplinary approach which integrates the hardware, software, algorithms, and data. WISEBED provides heterogeneous large-scale structure because it brings several heterogeneous small-scale devices together to form a large-scale network structure.
+%It provides the research with different quality networks due to the heterogeneous structure of the network.
\end{table}
-Several sensor nodes testbeds are available to support the research efforts in WSNs, but only a few of them provide common evaluation goals for a large number of users~\cite{ref187,ref181}. However, all the WSN testbeds have usually many common properties, such as a typical number of sensors of the order of hundreds and sometimes only tens of nodes; the deployment of the sensor nodes in a static grid topology; metrics and debug information are obtained via wired connections. Therefore, the WSN testbeds impose strong limitations on the WSNs in terms of size and topology. Moreover, the cost of performing an experiment on a testbed is much higher than through a simulation because setting up the experiments, instrumenting the nodes, gathering the metrics on the performance, and so on is so expensive. For evaluating the systems and protocols on a large sensor networks, the simulation tools are the better choice due to the costs for hardware and maintenance~\cite{ref186}. Hence, the simulation tools stay the most practical tools to obtain a feedback on the performance of a new solution~\cite{ref180}.
+Several sensor nodes testbeds are available to support the research efforts in WSNs, but only a few of them provide common evaluation goals for a large number of users~\cite{ref187,ref181}. However, all the WSN testbeds have usually many common properties, such as a typical number of sensors of the order of hundreds and sometimes only tens of nodes; the deployment of the sensor nodes in a static grid topology; metrics and debug information are obtained via wired connections. Therefore, the WSN testbeds impose strong limitations on the WSNs in terms of size and topology. Moreover, the cost of performing an experiment on a testbed is much higher than through a simulation because setting up the experiments, instrumenting the nodes, gathering the metrics on the performance, and so on is so expensive. For evaluating the systems and protocols on large sensor networks, the simulation tools are the better choice due to the costs for hardware and maintenance~\cite{ref186}. Hence, the simulation tools stay the most practical tools to obtain a feedback on the performance of a new solution~\cite{ref180}.
\subsection{Simulation Tools}
\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 previous protocols and most of the methods proposed in the literature, we formulate a 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.
+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 a mixed-integer program based on perimeter coverage of each sensor. The model involves 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 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.
%Ensuite, nous avons étudié le problème de l'optimisation multi-ronde de la zone de couverture dans un réseau de capteurs sans fil. Nous avons proposé le protocole d'optimisation multi-ronde distribué de la durée de vie de couverture (MuDiLCO) pour étudier la possibilité de fournir plusieurs ensembles de n\oe uds de capteurs de couverture pour la phase de surveillance. Ce protocole travaille également en périodes pendant lesquelles les ensembles de capteurs sont programmés pour rester actifs pour un certain nombre de rondes durant la phase de surveillance, pour assurer la couverture et maximiser la durée de vie du réseau. Le processus de décision est toujours effectué par le n\oe ud leader qui résout un programme entier pour définir un meilleur ensemble de capteurs à être utilisé pendant les rondes de la phase de surveillance.
Enfin, nous avons proposé un protocole d'optimisation de la
-couverture basé sur la couverture DU périmètre des capteurs (PeCO), qui est aussi un protocole distribué sur les n\oe uds de capteurs dans chaque sous-région. Notre contribution dans ce protocole consiste essentiellement dans la proposition d'un nouveau modèle d'optimisation basé sur le périmètre de couverture pour l'ordonnancement de l'activité des capteurs. Ce modèle de couverture est résolu par le leader durant la phase de décision pour définir un ensemble de capteurs actifs pour la phase de surveillance.
+couverture basé sur la couverture du périmètre des capteurs (PeCO), qui est aussi un protocole distribué sur les n\oe uds de capteurs dans chaque sous-région. Notre contribution dans ce protocole consiste essentiellement dans la proposition d'un nouveau modèle d'optimisation basé sur le périmètre de couverture pour l'ordonnancement de l'activité des capteurs. Ce modèle de couverture est résolu par le leader durant la phase de décision pour définir un ensemble de capteurs actifs pour la phase de surveillance.
Nous avons effectué plusieurs simulations en utilisant le simulateur à évènements discrets OMNeT++ pour valider l'efficacité de nos protocoles. Nous avons pris en considération les caractéristiques d'un capteur Medusa II pour la consommation d'énergie et le temps de calcul. En comparaison avec deux autres méthodes existantes, nos protocoles ont la capacité d'augmenter la durée de vie du réseau de capteurs et d'améliorer les performances de couverture.
