X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/5206fb7212f724b5887553f7128e19122fc33719..09d036d7e4b0662f9b52cc226c174cb79b096eb7:/CHAPITRE_02.tex

diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex
index 7b56933..b306630 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,40 +14,105 @@ 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 have excluded the barrier coverage problem from this discussion about the coverage problems 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 coverage 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. The centralized algorithms have the advantage of requiring very low processing power from the sensor nodes which have usually limited processing capabilities.  Indeed, the exchange of packets in large WSNs may consume a considerable amount
+of energy in a centralized approach compared to a distributed one. Moreover, centralized approaches usually suffer from the scalability and reliability problems, making them less competitive as the network size increases.
 
-\subsection{Centralized Algorithms}
-\label{ch2:sec:03}
-The major approach is to divide/organize the sensors into a suitable number of cover sets, where each set completely covers an interest region and to activate these cover sets successively. The centralized algorithms always provide nearly or close to the optimal solution since the algorithm has a global view of the whole network. Note that  centralized algorithms have the advantage of requiring very low  processing  power from  the sensor nodes,  which  usually have limited processing  capabilities. The main drawback of this kind of approach is its higher cost in communications, since the node that will make the decision needs information from all the sensor nodes. Moreover, centralized approaches usually suffer from the scalability problem, making them less competitive as the network size increases.
+In 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. 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. Table~\ref{Table0:ch2} shows a comparison between the centralized coverage algorithms and the distributed coverage algorithms.
+
+
+\begin{table}[h]
+\caption{Centralized Coverage Algorithms vs Distributed Coverage Algorithms}
+\begin{center}
+\begin{tabular}{ |p{3cm}|p{5cm}|p{5cm}|}
+\hline
+      
+\textbf{\begin{center} Characteristics \end{center}} & \textbf{\begin{center} Centralized Coverage Algorithms \end{center}} & \textbf{\begin{center} Distributed Coverage Algorithms \end{center}}\\ \hline
+     
+\textbf{\begin{center} Computation \end{center}} & Require low processing power where the algorithm is executed only in one elected node. & Require large processing power due to execution the algorithm in every node in WSN. \\ \hline
+
+\textbf{\begin{center} Communication \end{center}} & Require large power consumption for communication. & Require low power consumption for communication. \\ \hline
+
+\textbf{\begin{center} Decision \end{center}} & Ensure optimal (or near-optimal) solution.  & Can not ensure optimal (or near-optimal) solution.\\ \hline
+
+\textbf{\begin{center} Redundancy \end{center}} &  Provide less redundant active sensor nodes during monitoring the sensing field.  & Provide more redundant active sensor nodes during monitoring the sensing field.\\ \hline
+
+\textbf{\begin{center} Energy Consumption \end{center}} & Energy consumption is large especially when the network size and/or density increase. & Energy consumption is low because they have lower communication cost. \\ \hline
+
+\textbf{\begin{center} Scalability \end{center}} & Scalable only with dividing the sensing field into smaller subregions. & More scalable for large networks. \\ \hline
 
+\textbf{\begin{center} Reliability \end{center}} & Less robust against sensor failure. & More robust against sensor failure. \\ \hline
+  
+\end{tabular}
+\end{center}
+\label{Table0:ch2}
+\end{table}
+
+
+
+In this dissertation, the sensing field is divided into smaller subregions using divide-and-conquer method. The division continues until the distance between each two sensors inside the subregion is 3 or 2 hops maximum. This division have made our protocols more scalable for the large networks, less energy consumption for communication, less processing power for decision, more reliable against network failure, and a longer lifetime. Our proposed protocols are distributed on the sensor nodes of the subregions. The protocols in each subregion work in independent and simultaneous way with the protocols in the other subregions. If the network disconnected in one subregion, it will not effect on the other subregions of the sensing field.  There is no a fixed sensor node in the subregion execute the optimization algorithm. Each period of the network lifetime, the sensor nodes in the subregion cooperate in order to select a sensor node according to a predefined priority metrics to execute the optimization algorithm. The local optimal schedule resulted from the optimization algorithm is applied within the subregion. The elected sensor node sends a packet to every sensor within the subregion to inform him to stay active or sleep during this period. Each optimization algorithm in a subregion provides locally optimal solution, so the solution for all the sensing field is near-optimal. 
+
+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.
+
+
+\section{Centralized Algorithms}
+\label{ch2:sec:02}
+The major idea of most centralized algorithms is to divide/organize the sensors into a suitable number of cover sets, where each set completely covers an interest region and to activate these cover sets successively. The centralized algorithms always provide optimal or near-optimal solution since the algorithm has a global view of the whole network. Energy-efficient centralized approaches differ according to several criteria \cite{ref113}, such as the coverage objective (target coverage or area coverage), the node deployment method (random or deterministic), and the heterogeneity of sensor nodes (common sensing range, common battery lifetime). 
 
-The first algorithms proposed in the literature consider that the cover sets are disjoint: a sensor  node  appears  in  exactly one of the generated cover sets~\cite{ref114,ref115,ref116}. In the case of non-disjoint algorithms~\cite{ref117}, sensors may participate in more than one  cover set. In some cases, this may prolong the lifetime of the network in comparison  to the disjoint cover set algorithms, but designing  algorithms for  non-disjoint cover  sets generally  induces  a higher order  of complexity. Moreover, in  case of  a sensor's  failure, non-disjoint scheduling  policies are less resilient and reliable because a sensor may be involved in more than one cover sets.
+The first algorithms proposed in the literature consider that the cover sets are disjoint: a sensor  node  appears  in  exactly one of the generated cover sets~\cite{ref114,ref115,ref116}. For  instance,  Slijepcevic  and  Potkonjak \cite{ref116}   propose an algorithm, which allocates sensor nodes in mutually independent sets to monitor an area divided into  several fields.  Their algorithm builds  a cover  set by including in  priority the sensor  nodes, which cover  critical fields, that  is to  say, fields  that are  covered by  the smallest  number of sensors. The time complexity of  their heuristic is $O(n^2)$ where $n$ is the number of  sensors. M. Cardei et al.~\cite{ref227}, have suggested a graph coloring technique to achieve energy savings by organizing the sensor nodes into a maximum number of disjoint dominating sets, which are activated successively. They have defined the maximum disjoint dominating sets problem and they have produced a heuristic that computes the disjoint cover sets so as to monitor the area of interest. The dominating sets do not guarantee the coverage of the whole region of interest. Abrams et al.~\cite{ref114} designed  three  approximation algorithms  for a  variation of  the  set k-cover  problem, where  the objective is to partition the sensors into covers such that the number of covers that  include an area, summed over  all areas, is maximized.
+Their work builds upon previous work in~\cite{ref116} and the  generated cover sets do not provide complete coverage of the monitoring zone.
+
+
+The authors in~\cite{ref115} proposed  a heuristic  to compute  the  disjoint  set covers  (DSC).  In order  to compute the maximum number of  covers, they first transform DSC into a maximum-flow problem, which  is then formulated  as a  mixed integer programming  problem (MIP).  Based on  the solution  of the  MIP, they design a heuristic to compute  the final number of covers. The results show  a slight  performance  improvement  in terms  of  the number  of produced  DSC in comparison  to~\cite{ref116}, but it incurs  higher execution  time due to  the complexity of  the mixed integer programming solving. Zorbas  et  al.  \cite{ref228}  presented  B\{GOP\},  a  centralized target coverage  algorithm  introducing   sensor   candidate  categorization depending on their  coverage status and the notion  of critical target to  call  targets   that  are  associated  with  a   small  number  of sensors. The total running time of their heuristic is $0(m n^2)$ where
+$n$ is the number of sensors  and $m$ the number of targets. Compared to    algorithm's    results of  Slijepcevic and    Potkonjak \cite{ref116},  their   heuristic  produces  more cover sets with a slight growth rate in execution time. More recently, Deschinkel and Hakem \cite{229} introduced  a near-optimal heuristic algorithm for solving the target coverage problem in WSN. The sensor nodes are organized into disjoint cover sets by the resolution an integer programming problem. Each cover set is capable of monitoring all the targets of the region of interest. Those covers sets are scheduled periodically. Their algorithm  able to construct the different cover sets in parallel. The results show that their algorithm achieves near-optimal solutions compared to the optimal ones obtained by the exact method.
+
+
+
+
+In the case of non-disjoint algorithms~\cite{ref117}, sensors may participate in more than one  cover set. In some cases, this may prolong the lifetime of the network in comparison  to the disjoint cover set algorithms, but designing  algorithms for  non-disjoint cover  sets generally  induces  a higher order  of complexity. Moreover, in  case of a sensor's  failure, non-disjoint scheduling  policies are less resilient and reliable because a sensor may be involved in more than one cover sets. For instance,  Cardei et al.~\cite{ref167}
+present a  linear programming (LP)  solution and a greedy  approach to
+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}.
+    
+    
+   
+    
+    
+    
+    
+    
+    
+    
     
 In~\cite{ref118}, the authors have considered a 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.  
 
@@ -77,8 +142,8 @@ Various centralized  methods  based on column generation approaches have also be
 
 
 
-\subsection{Distributed Algorithms}
-\label{ch2:sec:04}
+\section{Distributed Algorithms}
+\label{ch2:sec:03}
 
 In distributed and localized coverage  algorithms, the required  computation to schedule the  activity of  sensor nodes  will be done  by the  cooperation among neighboring nodes. These  algorithms may require more computation  power for the processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers.
 Many distributed algorithms have been  developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref97}. 
@@ -105,17 +170,19 @@ nodes or between disk of sensor nodes and boundaries.
 In \cite{ref133} authors prove  that  if  the perimeters  of sensors are sufficiently  covered it will be  the case for the  whole area. They provide an algorithm in $O(nd~log~d)$  time to compute the perimeter coverage of
 each  sensor,  where  $d$  denotes  the  maximum  number  of  sensors  that  are neighboring  to  a  sensor and  $n$  is  the  total  number of  sensors  in  the network.
 
+\subsection{GAF}
+\label{ch2:sec:03:1}
 
 In \cite{GAF}, Xu et al. have described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses geographic location information to divide the area of interest into fixed square grids. Within each grid, it keeps only one node staying awake to take the responsibility of sensing and communication. Figure~\ref{gaf1} gives an example of fixed square grid in GAF.
 
 \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,19 +196,21 @@ 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}
 
 The sensor node sets a timer to $T_d$ seconds after entering in the discovery state. As soon as the timer fires, the sensor node broadcast its discovery message and enters the active state. The active sensor node sets a timeout value $T_a$ to define how long it can stay in the active state. After $T_a$, the sensor node will return to the discovery state. Whilst, during its active state, it re-broadcasts its discovery message at intervals $T_d$ periodically. The sensor node with discovery or active state can change its state to sleep when it detects that some other equivalent node will handle routing inside the grid. The sensor nodes in the sleeping state wake up after a sleeping time $T_s$ and go back to the discovery state. In GAF, load balancing is performed by means of periodic election of the leader (i.e., the active node that handle the routing inside the fixed grid). A rank-based election algorithm has been used to elect the leader. It is based on the remaining energy of sensor nodes inside the fixed square grid so as to extend the network lifetime In proportionally with network density.
 
+\subsection{DESK}
+\label{ch2:sec:03:2}
 
 In~\cite{DESK}, the author have designed a novel distributed heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), which  ensures that the energy consumption  among the sensors is balanced  and the lifetime  maximized  while  the coverage  requirement  is maintained. This heuristic  works in  rounds, requires  only  one-hop neighbor information, and each  sensor decides its status (active or  sleep) based on the perimeter coverage model from~\cite{ref133}. Figure~\ref{desk} shows the DESK network time line.
 
 \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}
