%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
-%% CHAPITRE 04 %%
+%% CHAPTER 04 %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
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!]
\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
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}
\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
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}
$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
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.
\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
\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
\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
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}.
\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}
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
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}
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
