X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/blobdiff_plain/946555d85197e77a0b8f06b8ee4e4d2b6c788f3d..96d26524bede6118dd7d761c860d9180abf8fe99:/CHAPITRE_04.tex diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex index 0cdeebe..d09e8b3 100644 --- a/CHAPITRE_04.tex +++ b/CHAPITRE_04.tex @@ -1,6 +1,6 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% -%% CHAPITRE 04 %% +%% CHAPTER 04 %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -17,23 +17,29 @@ lifetime of WSN. The decision process is carried out by a leader node, which during the rounds of the sensing phase. Compared with some existing protocols, simulation results based on multiple criteria (energy consumption, coverage ratio, and so on) show that the proposed protocol can prolong efficiently the network lifetime and improve the coverage performance. -\section{MuDiLCO protocol description} +\section{MuDiLCO Protocol Description} \label{ch4:sec:02} \noindent In this section, we introduce the MuDiLCO protocol which is distributed on each subregion in the area of interest. It is based on two energy-efficient mechanisms: subdividing the area of interest into several subregions (like cluster architecture) using divide and conquer method, where the sensor nodes cooperate within each subregion as independent group in order to achieve a network leader election; and sensor activity scheduling for maintaining the coverage and prolonging the network lifetime, which are applied periodically. MuDiLCO protocol uses the same assumptions and network model that presented in chapter 3, section \ref{ch3:sec:02:01} and it has been used the primary point coverage model which is described in the same chapter, section \ref{ch3:sec:02:02}. -\subsection{Background Idea} +\subsection{Background Idea and Algorithm} \label{ch4:sec:02:02} The area of interest can be divided using the divide-and-conquer strategy into smaller areas, called subregions, and then our MuDiLCO protocol will be implemented in each subregion in a distributed way. -As can be seen in Figure~\ref{fig2}, our protocol works in periods fashion, +As can be seen in Figure~\ref{fig2}, our protocol works in periods fashion, where each is divided into 4 phases: Information~Exchange, Leader~Election, -Decision, and Sensing. Each sensing phase may be itself divided into $T$ rounds +Decision, and Sensing. The information exchange among wireless sensor nodes is described in chapter 3, section \ref{ch3:sec:02:03:01}. The leader election in each subregion is explained in chapter 3, section \ref{ch3:sec:02:03:02}, but the difference in that the elected leader in each subregion is for each period. In decision phase, each WSNL will solve an integer program to select which cover sets will be +activated in the following sensing phase to cover the subregion to which it belongs. The integer program will produce $T$ cover sets, one for each round. The WSNL will send an Active-Sleep packet to each sensor in the subregion based on the algorithm's results, indicating if the sensor should be active or not in +each round of the sensing phase. Each sensing phase may be itself divided into $T$ rounds and for each round a set of sensors (a cover set) is responsible for the sensing -task. In this way a multiround optimization process is performed during each +task. Each sensor node in the subregion will +receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to +sleep for each round of the sensing phase. Algorithm~\ref{alg:MuDiLCO}, which +will be executed by each node at the beginning of a period, explains how the +Active-Sleep packet is obtained. In this way a multiround optimization process is performed during each period after Information~Exchange and Leader~Election phases, in order to produce $T$ cover sets that will take the mission of sensing for $T$ rounds. \begin{figure}[ht!] @@ -43,45 +49,66 @@ produce $T$ cover sets that will take the mission of sensing for $T$ rounds. \end{figure} -This protocol minimizes the impact of unexpected node failure (not due to batteries -running out of energy), because it works in periods. - - On the one hand, if a node failure is detected before making the -decision, the node will not participate to this phase, and, on the other hand, -if the node failure occurs after the decision, the sensing task of the network -will be temporarily affected: only during the period of sensing until a new -period starts. - -The energy consumption and some other constraints can easily be taken into -account, since the sensors can update and then exchange their information -(including their residual energy) at the beginning of each period. However, the -pre-sensing phases (Information Exchange, Leader Election, and Decision) are -energy consuming for some nodes, even when they do not join the network to -monitor the area. - - -These phases can be described in more details as follow: -\subsection{Information Exchange Phase} -\label{ch4:sec:02:02:01} -The information exchange among the wireless sensor nodes is similar to that one which is described in chapter 3, sections \ref{ch3:sec:02:03:01}. - -\subsection{Leader Election phase} -\label{ch4:sec:02:02:02} -The leader election in each subregion is similar to that one which is described in chapter 3, sections\ref{ch3:sec:02:03:02}, but the difference in that the elected leader in each subregion is for each period. - -\subsection{Decision phase} -\label{ch4:sec:02:02:03} -Each WSNL will solve an integer program to select which cover sets will be -activated in the following sensing phase to cover the subregion to which it -belongs. The integer program will produce $T$ cover sets, one for each round. -The WSNL will send an Active-Sleep packet to each sensor in the subregion based -on the algorithm's results, indicating if the sensor should be active or not in -each round of the sensing phase. The integer program is based on the model +This protocol minimizes the impact of unexpected node failure (not due to batteries running out of energy), because it works in periods. + +On the one hand, if a node failure is detected before making the decision, the node will not participate to this phase, and, on the other hand, if the node failure occurs after the decision, the sensing task of the network will be temporarily affected: only during the period of sensing until a new period starts. + +The energy consumption and some other constraints can easily be taken into account, since the sensors can update and then exchange their information (including their residual energy) at the beginning of each period. However, the pre-sensing phases (Information Exchange, Leader Election, and Decision) are energy consuming for some nodes, even when they do not join the network to monitor the area. + + + +\begin{algorithm}[h!] + % \KwIn{all the parameters related to information exchange} +% \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)} + \BlankLine + %\emph{Initialize the sensor node and determine it's position and subregion} \; + + \If{ $RE_j \geq E_{R}$ }{ + \emph{$s_j.status$ = COMMUNICATION}\; + \emph{Send $INFO()$ packet to other nodes in the subregion}\; + \emph{Wait $INFO()$ packet from other nodes in the subregion}\; + %\emph{UPDATE $RE_j$ for every sent or received INFO Packet}\; + %\emph{ Collect information and construct the list L for all nodes in the subregion}\; + + %\If{ the received INFO Packet = No. of nodes in it's subregion -1 }{ + \emph{LeaderID = Leader election}\; + \If{$ s_j.ID = LeaderID $}{ + \emph{$s_j.status$ = COMPUTATION}\; + \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ = + Execute Integer Program Algorithm($T,J$)}\; + \emph{$s_j.status$ = COMMUNICATION}\; + \emph{Send $ActiveSleep()$ to each node $k$ in subregion a packet \\ + with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\; + \emph{Update $RE_j $}\; + } + \Else{ + \emph{$s_j.status$ = LISTENING}\; + \emph{Wait $ActiveSleep()$ packet from the Leader}\; + % \emph{After receiving Packet, Retrieve the schedule and the $T$ rounds}\; + \emph{Update $RE_j $}\; + } + % } + } + \Else { Exclude $s_j$ from entering in the current sensing phase} + + % \emph{return X} \; +\caption{MuDiLCO($s_j$)} +\label{alg:MuDiLCO} + +\end{algorithm} + + + + +\subsection{Primary Points based Multiround Coverage Problem Formulation} +%\label{ch4:sec:02:02} + +According to our algorithm~\ref{alg:MuDiLCO}, the integer program is based on the model proposed by \cite{ref156} with some modifications, where the objective is -to find a maximum number of disjoint cover sets. To fulfill this goal, the +to find a maximum number of disjoint cover sets. To fulfill this goal, the authors proposed an integer program which forces undercoverage and overcoverage of targets to become minimal at the same time. They use binary variables -$x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our model, we +$x_{jl}$ to indicate if sensor $j$ belongs to cover set $l$. In our model, we consider binary variables $X_{t,j}$ to determine the possibility of activating sensor $j$ during round $t$ of a given sensing phase. We also consider primary points as targets. The set of primary points is denoted by $P$ and the set of @@ -189,56 +216,9 @@ to guarantee that the maximum number of points are covered during each round. In our simulations priority is given to the coverage by choosing $W_{U}$ very large compared to $W_{\theta}$. -\subsection{Sensing phase} -\label{ch4:sec:02:02:04} -The sensing phase consists of $T$ rounds. Each sensor node in the subregion will -receive an Active-Sleep packet from WSNL, informing it to stay awake or to go to -sleep for each round of the sensing phase. Algorithm~\ref{alg:MuDiLCO}, which -will be executed by each node at the beginning of a period, explains how the -Active-Sleep packet is obtained. - -\begin{algorithm}[h!] - % \KwIn{all the parameters related to information exchange} -% \KwOut{$winer-node$ (: the id of the winner sensor node, which is the leader of current round)} - \BlankLine - %\emph{Initialize the sensor node and determine it's position and subregion} \; - - \If{ $RE_j \geq E_{R}$ }{ - \emph{$s_j.status$ = COMMUNICATION}\; - \emph{Send $INFO()$ packet to other nodes in the subregion}\; - \emph{Wait $INFO()$ packet from other nodes in the subregion}\; - %\emph{UPDATE $RE_j$ for every sent or received INFO Packet}\; - %\emph{ Collect information and construct the list L for all nodes in the subregion}\; - - %\If{ the received INFO Packet = No. of nodes in it's subregion -1 }{ - \emph{LeaderID = Leader election}\; - \If{$ s_j.ID = LeaderID $}{ - \emph{$s_j.status$ = COMPUTATION}\; - \emph{$\left\{\left(X_{1,k},\dots,X_{T,k}\right)\right\}_{k \in J}$ = - Execute Integer Program Algorithm($T,J$)}\; - \emph{$s_j.status$ = COMMUNICATION}\; - \emph{Send $ActiveSleep()$ to each node $k$ in subregion a packet \\ - with vector of activity scheduling $(X_{1,k},\dots,X_{T,k})$}\; - \emph{Update $RE_j $}\; - } - \Else{ - \emph{$s_j.status$ = LISTENING}\; - \emph{Wait $ActiveSleep()$ packet from the Leader}\; - % \emph{After receiving Packet, Retrieve the schedule and the $T$ rounds}\; - \emph{Update $RE_j $}\; - } - % } - } - \Else { Exclude $s_j$ from entering in the current sensing phase} - - % \emph{return X} \; -\caption{MuDiLCO($s_j$)} -\label{alg:MuDiLCO} - -\end{algorithm} - - + + \section{Experimental Study and Analysis} \label{ch4:sec:03} @@ -246,10 +226,8 @@ Active-Sleep packet is obtained. \subsection{Simulation Setup} \label{ch4:sec:03:01} We conducted a series of simulations to evaluate the efficiency and the -relevance of our approach, using the discrete event simulator OMNeT++ -\cite{ref158}. The simulation parameters are summarized in -Table~\ref{table3}. Each experiment for a network is run over 25~different -random topologies and the results presented hereafter are the average of these +relevance of our approach, using the discrete event simulator OMNeT++ +\cite{ref158}. The simulation parameters are summarized in Table~\ref{table3}. Each experiment for a network is run over 25~different random topologies and the results presented hereafter are the average of these 25 runs. %Based on the results of our proposed work in~\cite{idrees2014coverage}, we found as the region of interest are divided into larger subregions as the network lifetime increased. In this simulation, the network are divided into 16 subregions. We performed simulations for five different densities varying from 50 to @@ -316,7 +294,9 @@ reduce the advantage of the optimization. In fact, there is a balance between the benefit from the optimization and the execution time needed to solve it. Therefore, we have set the number of subregions to 16 rather than 32. -We have used an energy consumption model, which is presented in chapter 1, section \ref{ch1:sec9:subsec2}. The initial energy of each node is randomly set in the interval $[500;700]$. A sensor node will not participate in the next round if its remaining energy is less than $E_{R}=36~\mbox{Joules}$, the minimum energy needed for the node to stay alive during one round. This value has been computed by multiplying the energy consumed in active state (9.72 mW) by the time in second for one round (3600 seconds). According to the interval of initial energy, a sensor may be alive during at most 20 rounds. +We used the modeling language and the optimization solver which are mentioned in chapter 3, section \ref{ch3:sec:04:02}. In addition, we employed an energy consumption model, which is presented in chapter 3, section \ref{ch3:sec:04:03}. + +%The initial energy of each node is randomly set in the interval $[500;700]$. A sensor node will not participate in the next round if its remaining energy is less than $E_{R}=36~\mbox{Joules}$, the minimum energy needed for the node to stay alive during one round. This value has been computed by multiplying the energy consumed in active state (9.72 mW) by the time in second for one round (3600 seconds). According to the interval of initial energy, a sensor may be alive during at most 20 rounds. \subsection{Metrics} \label{ch4:sec:03:02} @@ -349,7 +329,7 @@ where $A_r^t$ is the number of active sensors in the subregion $r$ during round $t$ in the current sensing phase, $|J|$ is the total number of sensors in the network, and $R$ is the total number of subregions in the network. -\item {{\bf Network Lifetime}:} is described in chapter 3, section \ref{ch3:sec:04:02}. +\item {{\bf Network Lifetime}:} is described in chapter 3, section \ref{ch3:sec:04:04}. \item {{\bf Energy Consumption (EC)}:} the average energy consumption can be seen as the total energy consumed by the sensors during the $Lifetime_{95}$ or @@ -373,22 +353,27 @@ factor, corresponds to the energy consumed by the sensors in LISTENING status before receiving the decision to go active or sleep in period $m$. $E^{\scriptsize \mbox{comp}}_m$ refers to the energy needed by all the leader nodes to solve the integer program during a period. Finally, $E^a_t$ and $E^s_t$ -indicate the energy consummed by the whole network in round $t$. +indicate the energy consumed by the whole network in round $t$. -\item {{\bf Execution Time}:} is described in chapter 3, section \ref{ch3:sec:04:02}. +\item {{\bf Execution Time}:} is described in chapter 3, section \ref{ch3:sec:04:04}. -\item {{\bf Stopped simulation runs}:} is described in chapter 3, section \ref{ch3:sec:04:02}. +\item {{\bf Stopped simulation runs}:} is described in chapter 3, section \ref{ch3:sec:04:04}. \end{enumerate} -\subsection{Results analysis and Comparison } +\subsection{Results Analysis and Comparison } \label{ch4:sec:03:02} -\subsection{Coverage ratio} -\label{ch4:sec:03:02:01} + +\begin{enumerate}[(i)] + +\item {{\bf Coverage Ratio}} +%\subsection{Coverage ratio} +%\label{ch4:sec:03:02:01} + Figure~\ref{fig3} shows the average coverage ratio for 150 deployed nodes. We can notice that for the first thirty rounds both DESK and GAF provide a coverage which is a little bit better than the one of MuDiLCO. @@ -406,13 +391,16 @@ rounds, and thus should extend the network lifetime. \begin{figure}[ht!] \centering - \includegraphics[scale=0.5] {Figures/ch4/R1/CR.pdf} + \includegraphics[scale=0.6] {Figures/ch4/R1/CR.pdf} \caption{Average coverage ratio for 150 deployed nodes} \label{fig3} \end{figure} -\subsection{Active sensors ratio} -\label{ch4:sec:03:02:02} + +\item {{\bf Active sensors ratio}} +%\subsection{Active sensors ratio} +%\label{ch4:sec:03:02:02} + It is crucial to have as few active nodes as possible in each round, in order to minimize the communication overhead and maximize the network lifetime. Figure~\ref{fig4} presents the active sensor ratio for 150 deployed @@ -427,13 +415,15 @@ nodes in a more efficient manner. \begin{figure}[ht!] \centering -\includegraphics[scale=0.5]{Figures/ch4/R1/ASR.pdf} +\includegraphics[scale=0.6]{Figures/ch4/R1/ASR.pdf} \caption{Active sensors ratio for 150 deployed nodes} \label{fig4} \end{figure} -\subsection{Stopped simulation runs} -\label{ch4:sec:03:02:03} +\item {{\bf Stopped simulation runs}} +%\subsection{Stopped simulation runs} +%\label{ch4:sec:03:02:03} + Figure~\ref{fig6} reports the cumulative percentage of stopped simulations runs per round for 150 deployed nodes. This figure gives the breakpoint for each method. DESK stops first, after approximately 45~rounds, because it consumes the more energy by turning on a large number of redundant nodes during the sensing @@ -446,30 +436,37 @@ still connected. \begin{figure}[ht!] \centering -\includegraphics[scale=0.5]{Figures/ch4/R1/SR.pdf} +\includegraphics[scale=0.6]{Figures/ch4/R1/SR.pdf} \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes } \label{fig6} \end{figure} -\subsection{Energy consumption} \label{subsec:EC} -\label{ch4:sec:03:02:04} + + +\item {{\bf Energy consumption}} \label{subsec:EC} +%\subsection{Energy consumption} +%\label{ch4:sec:03:02:04} + We measure the energy consumed by the sensors during the communication, listening, computation, active, and sleep status for different network densities -and compare it with the two other methods. Figures~\ref{fig7}(a) +and compare it with the two other methods. Figures~\ref{fig7}(a) and~\ref{fig7}(b) illustrate the energy consumption, considering different network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$. + \begin{figure}[h!] - \centering - \begin{tabular}{cl} - \parbox{9.5cm}{\includegraphics[scale=0.5]{Figures/ch4/R1/EC95.pdf}} & (a) \\ - \verb+ + \\ - \parbox{9.5cm}{\includegraphics[scale=0.5]{Figures/ch4/R1/EC50.pdf}} & (b) - \end{tabular} - \caption{Energy consumption for (a) $Lifetime_{95}$ and - (b) $Lifetime_{50}$} - \label{fig7} -\end{figure} +\centering + %\begin{multicols}{1} +\centering +\includegraphics[scale=0.6]{Figures/ch4/R1/EC95.pdf}\\~ ~ ~ ~ ~(a) \\ +%\vfill +\includegraphics[scale=0.6]{Figures/ch4/R1/EC50.pdf}\\~ ~ ~ ~ ~(b) + +%\end{multicols} +\caption{Energy consumption for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$} +\label{fig7} +\end{figure} + The results show that MuDiLCO is the most competitive from the energy consumption point of view. The other approaches have a high energy consumption @@ -483,8 +480,11 @@ MuDiLCO-7, we should increase the number of subregions in order to have less sensors to consider in the integer program. -\subsection{Execution time} -\label{ch4:sec:03:02:05} + + \item {{\bf Execution time}} +%\subsection{Execution time} +%\label{ch4:sec:03:02:05} + We observe the impact of the network size and of the number of rounds on the computation time. Figure~\ref{fig77} gives the average execution times in seconds (needed to solve optimization problem) for different values of $T$. The original execution time is computed as described in chapter 3, section \ref{ch3:sec:04:02}. @@ -493,7 +493,7 @@ seconds (needed to solve optimization problem) for different values of $T$. The \begin{figure}[ht!] \centering -\includegraphics[scale=0.5]{Figures/ch4/R1/T.pdf} +\includegraphics[scale=0.6]{Figures/ch4/R1/T.pdf} \caption{Execution Time (in seconds)} \label{fig77} \end{figure} @@ -509,8 +509,12 @@ reduce the energy-overhead due to the three pre-sensing phases, on the other hand a leader node may waste a considerable amount of energy to solve the optimization problem. -\subsection{Network lifetime} -\label{ch4:sec:03:02:06} + + +\item {{\bf Network lifetime}} +%\subsection{Network lifetime} +%\label{ch4:sec:03:02:06} + The next two figures, Figures~\ref{fig8}(a) and \ref{fig8}(b), illustrate the network lifetime for different network sizes, respectively for $Lifetime_{95}$ and $Lifetime_{50}$. Both figures show that the network lifetime increases @@ -522,21 +526,27 @@ lifetime for a coverage over 95\% is greater than 38\% when switching from GAF to MuDiLCO-3. The slight decrease that can be observed for MuDiLCO-7 in case of $Lifetime_{95}$ with large wireless sensor networks results from the difficulty of the optimization problem to be solved by the integer program. -This point was already noticed in subsection \ref{subsec:EC} devoted to the +This point was already noticed in \ref{subsec:EC} devoted to the energy consumption, since network lifetime and energy consumption are directly linked. -\begin{figure}[t!] - \centering - \begin{tabular}{cl} - \parbox{9.5cm}{\includegraphics[scale=0.5]{Figures/ch4/R1/LT95.pdf}} & (a) \\ - \verb+ + \\ - \parbox{9.5cm}{\includegraphics[scale=0.5]{Figures/ch4/R1/LT50.pdf}} & (b) - \end{tabular} - \caption{Network lifetime for (a) $Lifetime_{95}$ and - (b) $Lifetime_{50}$} + +\begin{figure}[h!] +\centering +% \begin{multicols}{0} +\centering +\includegraphics[scale=0.6]{Figures/ch4/R1/LT95.pdf}\\~ ~ ~ ~ ~(a) \\ +%\hfill +\includegraphics[scale=0.6]{Figures/ch4/R1/LT50.pdf}\\~ ~ ~ ~ ~(b) + +%\end{multicols} +\caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$} \label{fig8} -\end{figure} +\end{figure} + + + +\end{enumerate} \section{Conclusion} @@ -566,3 +576,8 @@ subregion, that can be solved more easily. Nevertheless, results also show that it is not possible to plan the activity of sensors over too many rounds, because the resulting optimization problem leads to too high resolution times and thus to an excessive energy consumption. + + + + + \ No newline at end of file