X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/d6d8c544df886c9662e0200ee2a41ebdfd670cb0..e37d5744049f24cc066915783983db40c3ea51c5:/CHAPITRE_04.tex?ds=sidebyside diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex old mode 100755 new mode 100644 index b715471..9770cc7 --- a/CHAPITRE_04.tex +++ b/CHAPITRE_04.tex @@ -9,22 +9,20 @@ -\section{Summary} +\section{Introduction} \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} @@ -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. - -\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:\\ @@ -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})) $. -\begin{figure}[h!] + + +\begin{figure} %[h!] \centering - \begin{multicols}{3} + \begin{multicols}{2} \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} - + + \subsection{Main Idea} @@ -333,7 +334,7 @@ $w_{U}$ & $|P|^2$ % 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 @@ -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. -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} @@ -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} -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} -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}} @@ -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} -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}} @@ -768,11 +768,7 @@ Comparison shows that DiLCO-16 protocol and DiLCO-32 protocol, which are used di \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.