]> AND Private Git Repository - ThesisAli.git/blobdiff - CHAPITRE_04.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Update by Ali
[ThesisAli.git] / CHAPITRE_04.tex
old mode 100755 (executable)
new mode 100644 (file)
index b715471..9770cc7
@@ -9,22 +9,20 @@
 
 
 
 
 
 
-\section{Summary}
+\section{Introduction}
 \label{ch4:sec:01}
 \label{ch4:sec:01}
-In this chapter, a Distributed Lifetime Coverage Optimization protocol (DiLCO) to maintain
-the coverage and to improve  the  lifetime  in  wireless sensor  networks  is
-proposed.   The  area of  interest  is first  divided  into  subregions using  a
-divide-and-conquer  method and  then the  DiLCO protocol  is distributed  on the
-sensor nodes  in each  subregion. The DiLCO  combines two  efficient techniques:
-leader election  for each subregion, followed by  an optimization-based planning
-of activity  scheduling decisions for  each subregion. The proposed  DiLCO works
-into rounds during which a small  number of nodes, remaining active for sensing,
-is selected to ensure coverage so as to maximize the lifetime of wireless sensor
-network.   Each  round  consists   of  four  phases:  (i)~Information  Exchange,
-(ii)~Leader Election, (iii)~Decision, and (iv)~Sensing.  The decision process is
-carried out  by a leader node,  which solves an integer  program.  Compared with
-some existing protocols, simulation results  show that the proposed protocol can
-prolong the network lifetime and improve the coverage performance effectively.
+Energy efficiency is  a crucial issue in wireless  sensor networks since the sensory consumption, in  order to  maximize the network  lifetime, represents  the major difficulty when designing WSNs. As a consequence, one of the scientific research challenges in  WSNs, which has  been addressed by  a large amount  of literature
+during the  last few  years, is  the design of  energy efficient  approaches for coverage and connectivity~\cite{ref94}.   Coverage reflects how well a sensor  field is  monitored. On  the one  hand, we  want to  monitor the  area of interest in the most efficient way~\cite{ref95}.  On the other hand, we want to use  as little energy  as possible.   Sensor nodes  are battery-powered  with no means  of recharging  or replacing,  usually  due to  environmental (hostile  or
+unpractical environments)  or cost reasons.   Therefore, it is desired  that the WSNs are deployed  with high densities so as to  exploit the overlapping sensing regions of some sensor  nodes to save energy by turning off  some of them during the sensing phase to prolong the network lifetime.
+
+In this chapter, we design  a protocol that focuses on the area  coverage problem with  the objective  of maximizing  the network  lifetime. Our  proposition, the Distributed  Lifetime  Coverage  Optimization  (DiLCO) protocol,  maintains  the coverage  and improves  the lifetime  in  WSNs. 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.  Our 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  broadcast by a leader to every node of its subregion.
+
+The remainder of this chapter is organized as follows. The next section is devoted to the DiLCO protocol description. Section \ref{ch4:sec:03} gives the primary points based coverage problem formulation which is used to schedule the activation of sensors. Section \ref{ch4:sec:04} shows the simulation
+results obtained using the discrete event simulator OMNeT++ \cite{ref158}. They fully demonstrate the usefulness of the proposed approach. Finally, we give concluding remarks in section \ref{ch4:sec:05}.
+
 
 
 \section{Description of the DiLCO Protocol}
 
 
 \section{Description of the DiLCO Protocol}
@@ -60,8 +58,7 @@ There are five possible status for each sensor node in the network:
 \subsection{Primary Point Coverage Model}
 \label{ch4:sec:02:02}
 \indent Instead of working with the coverage area, we consider for each sensor a set of points called primary points. We also assume that the sensing disk defined by a sensor is covered if all the primary points of this sensor are covered. By  knowing the  position (point  center: ($p_x,p_y$))  of  a wireless sensor node  and it's $R_s$,  we calculate the primary  points directly based on the proposed model. We  use these primary points (that can be increased or decreased if necessary)  as references to ensure that the monitored  region  of interest  is  covered by the selected  set  of sensors, instead of using all the points in the area. 
 \subsection{Primary Point Coverage Model}
 \label{ch4:sec:02:02}
 \indent Instead of working with the coverage area, we consider for each sensor a set of points called primary points. We also assume that the sensing disk defined by a sensor is covered if all the primary points of this sensor are covered. By  knowing the  position (point  center: ($p_x,p_y$))  of  a wireless sensor node  and it's $R_s$,  we calculate the primary  points directly based on the proposed model. We  use these primary points (that can be increased or decreased if necessary)  as references to ensure that the monitored  region  of interest  is  covered by the selected  set  of sensors, instead of using all the points in the area. 
-
-\indent  We can  calculate  the positions of the selected primary
+We can  calculate  the positions of the selected primary
 points in the circle disk of the sensing range of a wireless sensor
 node (see figure~\ref{fig1}) as follows:\\
 
 points in the circle disk of the sensing range of a wireless sensor
 node (see figure~\ref{fig1}) as follows:\\
 
@@ -92,22 +89,26 @@ $X_{23}=( p_x + R_s * (\frac{- 1}{2}), p_y + R_s * (\frac{\sqrt{3}}{2})) $\\
 $X_{24}=( p_x + R_s * (\frac{- 1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $\\
 $X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $.
 
 $X_{24}=( p_x + R_s * (\frac{- 1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $\\
 $X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $.
 
-\begin{figure}[h!]
+
+\begin{figure} %[h!]
 \centering
 \centering
- \begin{multicols}{3}
+ \begin{multicols}{2}
 \centering
 \centering
-\includegraphics[scale=0.20]{Figures/ch4/fig21.pdf}\\~ ~ ~ ~ ~(a)
-\includegraphics[scale=0.20]{Figures/ch4/fig22.pdf}\\~ ~ ~ ~ ~(b)
-\includegraphics[scale=0.20]{Figures/ch4/principles13.pdf}\\~ ~ ~ ~ ~(c) 
-\hfill
-\includegraphics[scale=0.20]{Figures/ch4/fig24.pdf}\\~ ~ ~(d)
-\includegraphics[scale=0.20]{Figures/ch4/fig25.pdf}\\~ ~ ~(e)
-\includegraphics[scale=0.20]{Figures/ch4/fig26.pdf}\\~ ~ ~(f)
+\includegraphics[scale=0.33]{Figures/ch4/fig21.pdf}\\~ ~ ~ ~ ~ ~ ~ ~(a)
+\includegraphics[scale=0.33]{Figures/ch4/principles13.pdf}\\~ ~ ~ ~ ~ ~(c) 
+\hfill \hfill
+\includegraphics[scale=0.33]{Figures/ch4/fig25.pdf}\\~ ~ ~ ~ ~ ~(e)
+\includegraphics[scale=0.33]{Figures/ch4/fig22.pdf}\\~ ~ ~ ~ ~ ~ ~ ~ ~(b)
+\hfill \hfill
+\includegraphics[scale=0.33]{Figures/ch4/fig24.pdf}\\~ ~ ~ ~ ~ ~ ~(d)
+\includegraphics[scale=0.33]{Figures/ch4/fig26.pdf}\\~ ~ ~ ~ ~ ~ ~(f)
 \end{multicols} 
 \caption{Wireless Sensor Node represented by (a)5, (b)9, (c)13, (d)17, (e)21 and (f)25 primary points respectively}
 \label{fig1}
 \end{figure}
 \end{multicols} 
 \caption{Wireless Sensor Node represented by (a)5, (b)9, (c)13, (d)17, (e)21 and (f)25 primary points respectively}
 \label{fig1}
 \end{figure}
-
+    
 
 
 \subsection{Main Idea}
 
 
 \subsection{Main Idea}
@@ -333,7 +334,7 @@ $w_{U}$ & $|P|^2$
 % is used to refer this table in the text
 \end{table}
 
 % is used to refer this table in the text
 \end{table}
 
-Simulations with five  different node densities going from  50 to 250~nodes were
+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
 interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
 performed  considering  each  time  25~randomly generated  networks,  to  obtain
 experimental results  which are relevant. The  nodes are deployed on  a field of
 interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
@@ -689,7 +690,7 @@ In this experiment, the average coverage ratio for 150 deployed nodes has been d
 
 It has been shown that DESK and GAF provide a little better coverage ratio with 99.99\% and 99.91\% against 99.1\% and 99.2\% produced by DiLCO-16 and DiLCO-32 for the lowest number of rounds. This is due to the fact that DiLCO protocol versions put in sleep mode redundant sensors using optimization (which lightly decreases the coverage ratio) while there are more nodes are active in the case of DESK and GAF.
 
 
 It has been shown that DESK and GAF provide a little better coverage ratio with 99.99\% and 99.91\% against 99.1\% and 99.2\% produced by DiLCO-16 and DiLCO-32 for the lowest number of rounds. This is due to the fact that DiLCO protocol versions put in sleep mode redundant sensors using optimization (which lightly decreases the coverage ratio) while there are more nodes are active in the case of DESK and GAF.
 
-Moreover, when the number of rounds 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. This is because they optimized 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 leads to continue for a larger number of rounds and prolonging the network lifetime; although some nodes are dead, sensor activity scheduling of our protocol chooses other nodes to ensure the coverage of the area of interest. 
+Moreover, when the number of rounds 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. This is because they optimized 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 rounds 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. 
 
 \item {{\bf Active Sensors Ratio}}
 %\subsubsection{Active Sensors Ratio} 
 
 \item {{\bf Active Sensors Ratio}}
 %\subsubsection{Active Sensors Ratio} 
@@ -707,16 +708,15 @@ The results presented in figure~\ref{Figures/ch4/R3/ASR} show the superiority of
 
 \item {{\bf The percentage of stopped simulation runs}}
 %\subsubsection{The percentage of stopped simulation runs}
 
 \item {{\bf The percentage of stopped simulation runs}}
 %\subsubsection{The percentage of stopped simulation runs}
-The results presented in this experiment, is to show the comparison of DiLCO-16 protocol and DiLCO-32 protocol with other two approaches from point of view of stopped simulation runs per round.
-Figure~\ref{Figures/ch4/R3/SR} illustrates the percentage of stopped simulation
-runs per round for 150 deployed nodes. 
+The results presented in this experiment, are to show the comparison of DiLCO-16 protocol and DiLCO-32 protocol with other two approaches from the point of view of stopped simulation runs per round.
+Figure~\ref{Figures/ch4/R3/SR} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes. 
 \begin{figure}[h!]
 \centering
 \includegraphics[scale=0.8]{Figures/ch4/R3/SR.pdf} 
 \caption{Percentage of stopped simulation runs for 150 deployed nodes }
 \label{Figures/ch4/R3/SR}
 \end{figure} 
 \begin{figure}[h!]
 \centering
 \includegraphics[scale=0.8]{Figures/ch4/R3/SR.pdf} 
 \caption{Percentage of stopped simulation runs for 150 deployed nodes }
 \label{Figures/ch4/R3/SR}
 \end{figure} 
-It has been observed that DESK is the approach, which stops first because it consumes more energy for communication as well as it turn on a large number of redundant nodes during the sensing phase. On the other  hand DiLCO-16 protocol and DiLCO-32 protocol have less stopped simulation runs in comparison with DESK and GAF because it distributed the optimization on several subregions in order to optimizes the coverage and the lifetime of the network by activating a less number of nodes during the sensing phase leading to extend the network lifetime and coverage preservation. The optimization effectively continues as long as a network in a subregion is still connected.
+It has been observed that DESK is the approach, which stops first because it consumes more energy for communication as well as it turns on a large number of redundant nodes during the sensing phase. On the other  hand DiLCO-16 protocol and DiLCO-32 protocol have less stopped simulation runs in comparison with DESK and GAF because it distributed the optimization on several subregions in order to optimize the coverage and the lifetime of the network by activating a less number of nodes during the sensing phase leading to extending the network lifetime and coverage preservation. The optimization effectively continues as long as a network in a subregion is still connected.
 
 
 \item {{\bf The Energy Consumption}}
 
 
 \item {{\bf The Energy Consumption}}
@@ -737,7 +737,7 @@ In this experiment, we have studied the effect of the energy consumed by the wir
 \label{Figures/ch4/R3/EC50}
 \end{figure} 
 
 \label{Figures/ch4/R3/EC50}
 \end{figure} 
 
-The results show that DiLCO-16 protocol and DiLCO-32 protocol are the most competitive from the energy consumption point of view. The other approaches have a high energy consumption due to activating a larger number of redundant nodes as well as the energy consumed during the different modes of sensor nodes. In fact,  a distributed method on the subregions greatly reduces the number of communications and the time of listening so thanks to the partitioning of the initial network into several independent subnetworks. 
+The results show that DiLCO-16 protocol and DiLCO-32 protocol are the most competitive from the energy consumption point of view. The other approaches have a high energy consumption due to activating a larger number of redundant nodes, as well as the energy consumed during the different modes of sensor nodes. In fact,  a distributed method on the subregions greatly reduces the number of communications and the time of listening so thanks to the partitioning of the initial network into several independent subnetworks. 
 
 
 \item {{\bf The Network Lifetime}}
 
 
 \item {{\bf The Network Lifetime}}
@@ -768,11 +768,7 @@ Comparison shows that DiLCO-16 protocol and DiLCO-32 protocol, which are used di
 
 \section{Conclusion}
 \label{ch4:sec:05}
 
 \section{Conclusion}
 \label{ch4:sec:05}
-A crucial problem in WSN is to schedule the sensing activities of the different nodes  in order to  ensure both  coverage of  the area  of interest  and longer
-network lifetime. The inherent limitations of sensor nodes, in energy provision, communication and computing capacities,  require protocols that optimize the use
-of the  available resources  to  fulfill the sensing  task. To address  this problem, this chapter proposes a  two-step approach. Firstly, the field of sensing
-is  divided into  smaller  subregions using  the  concept of  divide-and-conquer method. Secondly,  a distributed  protocol called Distributed  Lifetime Coverage
-Optimization is applied in each  subregion to optimize the coverage and lifetime performances. In a subregion,  our protocol  consists in  electing a  leader node
-which will then perform a sensor activity scheduling. The challenges include how to  select the most efficient leader in each  subregion and  the  best representative set of active nodes to ensure a high level of coverage. To assess the performance of our approach, we  compared it with two other approaches using many performance metrics  like coverage ratio or network  lifetime. We have also studied the  impact of the  number of subregions  chosen to subdivide the  area of interest, considering  different  network  sizes. The  experiments  show  that increasing the  number of subregions improves  the lifetime. The  more subregions there are, the  more robust the network is against random disconnection resulting from dead nodes.  However, for  a given sensing field and network size there is an optimal number of  subregions. Therefore, in case of our simulation context  a subdivision in  $16$~subregions seems to be the most relevant.
+A crucial problem in WSN is to schedule the sensing activities of the different nodes  in order to ensure both of  coverage of  the area  of interest  and longer network lifetime. The inherent limitations of sensor nodes, in energy provision, communication and computing capacities,  require protocols that optimize the use of the  available resources  to  fulfill the sensing  task. To address  this problem, this chapter proposes a  two-step approach. Firstly, the field of sensing
+is  divided into  smaller  subregions using  the  concept of  divide-and-conquer method. Secondly,  a distributed  protocol called Distributed  Lifetime Coverage Optimization is applied in each  subregion to optimize the coverage and lifetime performances. In a subregion,  our protocol  consists in  electing a  leader node, which will then perform a sensor activity scheduling. The challenges include how to  select the most efficient leader in each  subregion and  the  best representative set of active nodes to ensure a high level of coverage. To assess the performance of our approach, we  compared it with two other approaches using many performance metrics  like coverage ratio or network  lifetime. We have also studied the  impact of the  number of subregions  chosen to subdivide the  area of interest, considering  different  network  sizes. The  experiments  show  that increasing the  number of subregions improves  the lifetime. The  more subregions there are, the  more robust the network is against random disconnection resulting from dead nodes.  However, for  a given sensing field and network size there is an optimal number of  subregions. Therefore, in case of our simulation context  a subdivision in  $16$~subregions seems to be the most relevant.