X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/5206fb7212f724b5887553f7128e19122fc33719..72071c0edb5719dd735986e8fa4147d224583e87:/CHAPITRE_02.tex diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex index 7b56933..9a986d7 100755 --- a/CHAPITRE_02.tex +++ b/CHAPITRE_02.tex @@ -4,7 +4,7 @@ %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\chapter{Related Literatures} +\chapter{Related Works on Coverage Problems} \label{ch2} \section{Introduction} @@ -14,32 +14,36 @@ The main objective of deploying a large number of wireless sensor nodes in the t The energy resource limitation of wireless sensor nodes has been considered as a big challenge in order to operate the WSN with less energy consumption whilst fulfill the coverage requirement. The main objective of scattering the wireless sensor nodes over the area of interest is to collect the sensed data of the physical phenomena for processing or reporting, where there are two types of reporting for sensed data in WSNs~\cite{ref138} like event-driven and on-demand. In the latter, the monitoring base station start the reporting operation by transmitting a request to the wireless sensor nodes so as to send their sensed data to the base station; for example, the inventory tracking application. In the former, the reporting operation is triggered by one or more wireless sensor nodes within the physical phenomena by transmitting their sensed data to the controlling base station; for instance, the forest fire detection application. The hybrid scheme of the two types is more flexible. -The ultimate goal of the coverage is to assure that each point in the sensing field is within the sensing range of at least one sensor node. Some applications require high reliability to perform their tasks, so they need that every point in the sensing field is covered by more than one sensor node. In order to avoid the lack in monitoring the area of interest, it is necessary that the WSN are deployed with high density so as to exploit the overlapping among the sensor nodes and to prevent malfunction of sensor nodes in severe environments. The overlap can be exploited by choosing the minimum number of sensor nodes to perform the main tasks of the WSN in the sensing field and putting the rest sensor nodes in very low power sleep mode so as to prolong the network lifetime. This exploitation manner is called sensor activity scheduling that aims to set the activity state of each sensor node in the WSN so that the sensing field can be monitored for a long time as possible. The required level of coverage should be guaranteed by the activity-based scheduling scheme~\cite{ref139}. Many scheduling algorithms have been described in~\cite{ref58,ref57}. +The ultimate goal of the coverage is to ensure that each point in the sensing field is within the sensing range of at least one sensor node. Some applications require high reliability to perform their tasks, so they need that every point in the sensing field is covered by more than one sensor node. In order to avoid the lack in monitoring the area of interest, it is necessary that the WSN are deployed with high density so as to exploit the overlapping among the sensor nodes and to prevent malfunction of sensor nodes in severe environments. The overlap can be exploited by choosing the minimum number of sensor nodes to perform the main tasks of the WSN in the sensing field and putting the rest sensor nodes in very low power sleep mode so as to prolong the network lifetime. This exploitation manner is called sensor activity scheduling that aims to set the activity state of each sensor node in the WSN so that the sensing field can be monitored for a long time as possible. The required level of coverage should be guaranteed by the activity-based scheduling scheme~\cite{ref139}. Many scheduling algorithms have been described in~\cite{ref58,ref57}. -This dissertation focuses on the problem of covering the area of interest as long as possible. Several proposed approaches to extend the network lifetime whilst maintaining the coverage have been viewed in this chapter. M. Cardei and J. Wu~\cite{ref113} have been surveyed the different coverage formulation models and their assumptions, as well as the solutions provided. In~\cite{ref105}, several coverage problems are presented from different angles, where the models and assumptions, as well as proposed solutions in the literatures, are described. In this dissertation, the main contribution of previous works that deal with the coverage problem have been addressed. We end this chapter by focusing on two algorithms, GAF~\cite{GAF} and DESK~\cite{DESK}, since they have used for comparison against our coverage protocols. +%This dissertation focuses on the problem of covering the area of interest as long as possible. Several proposed approaches to extend the network lifetime whilst maintaining the coverage have been viewed in this chapter. M. Cardei and J. Wu~\cite{ref113} have been surveyed the different coverage formulation models and their assumptions, as well as the solutions provided. In~\cite{ref105}, several coverage problems are presented from different angles, where the models and assumptions, as well as proposed solutions in the literatures, are described. In this dissertation, the main contribution of previous works that deal with the coverage problem have been addressed. We end this chapter by focusing on two algorithms, GAF~\cite{GAF} and DESK~\cite{DESK}, since they have been used for comparison against our coverage protocols. -\section{Coverage Algorithms} -\label{ch2:sec:02} +%\section{Coverage Algorithms} +%\label{ch2:sec:02} -\indent This section is dedicated to the various approaches proposed in the +\indent This chapter is dedicated to the various approaches proposed in the literature for the coverage lifetime maximization problem, where the objective is to optimally schedule sensors' activities in order to extend network lifetime -in WSNs. Cardei and Wu~\cite{ref113} provide a taxonomy for coverage algorithms in WSNs according to several design choices: +in WSNs. +In~\cite{ref105}, several coverage problems are presented from different angles, where the models and assumptions, as well as proposed solutions in the literatures, are described. +M. Cardei and J. Wu~\cite{ref113} have been surveyed the different coverage formulation models and their assumptions, as well as the solutions provided. They provide a taxonomy for coverage algorithms in WSNs according to several design choices: \begin{enumerate} [(i)] \item Sensors scheduling algorithm implementation, i.e. centralized or distributed/localized algorithms. \item The objective of sensor coverage, i.e. to maximize the network lifetime or - to minimize the number of sensors during a sensing round. + to minimize the number of active sensors during a sensing round. \item The homogeneous or heterogeneous nature of the nodes, in terms of sensing or communication capabilities. \item The node deployment method, which may be random or deterministic. \item Additional requirements for energy-efficient and connected coverage. \end{enumerate} -The choice of non-disjoint or disjoint cover sets (sensors participate or not in many cover sets), coverage type ( area, target, or barrier), coverage ratio, coverage degree (how many sensors are required to cover a target or an area) can be added to the above list. +From our point of view, the choice of non-disjoint or disjoint cover sets (sensors participate or not in many cover sets), coverage type ( area, target, or barrier), coverage ratio, coverage degree (how many sensors are required to cover a target or an area) can be added to the above list. -Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. Many centralized and distributed algorithms for activity scheduling have been proposed in the literature and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and the only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near-optimal) solution based only on local information. 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. +Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. This chapter concentrates only on area coverage and target coverage problems because it is possible to transform the area coverage problem to target ( or point) coverage problem and vice versa. We exclude the barrier coverage problem from this discussion about the coverage problem because it is outside the scope of this dissertation. 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 algorithms for activity scheduling have been proposed in the literature and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and the only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near-optimal) solution based only on local information. 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. \subsection{Centralized Algorithms} @@ -110,12 +114,12 @@ In \cite{GAF}, Xu et al. have described an algorithm, called Geographical Adapti \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{Figures/ch2/GAF1.jpeg} +\includegraphics[scale=0.8]{Figures/ch2/GAF1.jpeg} \caption{ Example of fixed square grid in GAF.} \label{gaf1} \end{figure} -The fixed grid is defined where, each two adjacent grids, for example, A and B in figure\ref{gaf1}, all the 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 two possible sensor nodes in two adjacent grid such as, B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$ so as to satisfy the definition of fixed square grid. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of grid C. So, +The fixed grid is defined where, each two adjacent grids, for example, A and B in figure\ref{gaf1}, all the 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 two possible sensor nodes in two adjacent grid such as, B and C in figure~\ref{gaf1}, should not be greater than the radio communication range $R_c$ so as to satisfy the definition of fixed square grid. For instance, the sensor node \textbf{2} of grid B can communicate with the sensor node \textbf{5} of grid C So, \begin{eqnarray} r^2 + \left(2r \right)^2 \leq R_c^2 @@ -129,7 +133,7 @@ The sensor nodes in GAF can be in one of the three states: active, sleep, or dis \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{Figures/ch2/GAF2.jpeg} +\includegraphics[scale=0.8]{Figures/ch2/GAF2.jpeg} \caption{ Example of fixed square grid in GAF.} \label{gaf2} \end{figure} @@ -141,7 +145,7 @@ In~\cite{DESK}, the author have designed a novel distributed heuristic, called D \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{Figures/ch2/DESK.jpeg} +\includegraphics[scale=0.6]{Figures/ch2/DESK.jpeg} \caption{ DESK network time line.} \label{desk} \end{figure}