%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% %%
-%% CHAPITRE 03 %%
+%% CHAPTER 03 %%
%% %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
prolong the network lifetime and improve the coverage performance effectively.
-\section{DESCRIPTION OF THE DILCO PROTOCOL}
+\section{Description of the DiLCO Protocol}
\label{ch3:sec:02}
\noindent In this section, we introduce the DiLCO protocol which is distributed on each subregion in the area of interest. It is based on two efficient
-\section{COVERAGE PROBLEM FORMULATION}
+\section{Primary Points based Coverage Problem Formulation}
\label{ch3:sec:03}
\indent Our model is based on the model proposed by \cite{ref156} where the
objective is to find a maximum number of disjoint cover sets. To accomplish
interest of $(50 \times 25)~m^2 $ in such a way that they cover the field with a
high coverage ratio.
-We chose as energy consumption model the one described in chapter 1, section \ref{ch1:sec9:subsec2}. Each node has an initial energy level, in Joules, which is randomly drawn in $[500-700]$. If its energy provision reaches a value below the threshold $E_{th}=36$~Joules, the minimum energy needed for a node to stay active during
-one period, it will no longer take part in the coverage task. This value corresponds to the energy needed by the sensing phase, obtained by multiplying the energy consumed in active state (9.72 mW) by the time in seconds for one period (3,600 seconds), and adding the energy for the pre-sensing phases.
-According to the interval of initial energy, a sensor may be active during at most 20 periods.
+
+\subsection{Modeling Language and Optimization Solver}
+\label{ch3:sec:04:02}
+The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is employed to generate the integer program instance in a standard format, which is then read and solved by the optimization solver GLPK (GNU linear Programming Kit available in the public domain) \cite{glpk} through a Branch-and-Bound method.
+
+\subsection{Energy Consumption Model}
+\label{ch3:sec:04:03}
+
+\indent In this dissertation, we used an energy consumption model proposed by~\cite{ref111} and based on \cite{ref112} with slight modifications. The energy consumption for sending/receiving the packets is added, whereas the part related to the sensing range is removed because we consider a fixed sensing range.
+
+\indent For our energy consumption model, we refer to the sensor node Medusa~II which uses an Atmels AVR ATmega103L microcontroller~\cite{ref112}. The typical architecture of a sensor is composed of four subsystems: the MCU subsystem which is capable of computation, communication subsystem (radio) which is responsible for transmitting/receiving messages, the sensing subsystem that collects data, and the power supply which powers the complete sensor node \cite{ref112}. Each of the first three subsystems can be turned on or off depending on the current status of the sensor. Energy consumption (expressed in milliWatt per second) for the different status of the sensor is summarized in Table~\ref{table1}.
+
+\begin{table}[ht]
+\caption{The Energy Consumption Model}
+% title of Table
+\centering
+% used for centering table
+\begin{tabular}{|c|c|c|c|c|}
+% centered columns (4 columns)
+ \hline
+%inserts double horizontal lines
+Sensor status & MCU & Radio & Sensing & Power (mW) \\ [0.5ex]
+\hline
+% inserts single horizontal line
+LISTENING & on & on & on & 20.05 \\
+% inserting body of the table
+\hline
+ACTIVE & on & off & on & 9.72 \\
+\hline
+SLEEP & off & off & off & 0.02 \\
+\hline
+COMPUTATION & on & on & on & 26.83 \\
+%\hline
+%\multicolumn{4}{|c|}{Energy needed to send/receive a 1-bit} & 0.2575\\
+ \hline
+\end{tabular}
+
+\label{table1}
+% is used to refer this table in the text
+\end{table}
+
+\indent For the sake of simplicity we ignore the energy needed to turn on the radio, to start up the sensor node, to move from one status to another, etc. Thus, when a sensor becomes active (i.e., it has already chosen its status), it can turn its radio off to save battery. The value of energy spent to send a 1-bit-content message is obtained by using the equation in ~\cite{ref112} to calculate the energy cost for transmitting messages and we propose the same value for receiving the packets. The energy needed to send or receive a 1-bit packet is equal to $0.2575~mW$.
+
+
+%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_{th}=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), and adding the energy for the pre-sensing phases. According to the interval of initial energy, a sensor may be alive during at most 20 rounds.
\subsection{Performance Metrics}
-\label{ch3:sec:04:02}
+\label{ch3:sec:04:04}
In the simulations, we introduce the following performance metrics to evaluate
the efficiency of our approach:
\subsection{Performance Analysis for Different Subregions}
-\label{ch3:sec:04:03}
+\label{ch3:sec:04:05}
In this subsection, we are studied the performance of our DiLCO protocol for a different number of subregions (Leaders).
The DiLCO-1 protocol is a centralized approach on all the area of the interest, while DiLCO-2, DiLCO-4, DiLCO-8, DiLCO-16 and DiLCO-32 are distributed on two, four, eight, sixteen, and thirty-two subregions respectively. We did not take the DiLCO-1 protocol in our simulation results because it need high execution time to give the decision leading to consume all it's energy before producing the solution for optimization problem.
-\subsubsection{Coverage Ratio}
+\begin{enumerate}[i)]
+\item {{\bf Coverage Ratio}}
+%\subsubsection{Coverage Ratio}
%\label{ch3:sec:04:02:01}
In this experiment, Figure~\ref{Figures/ch3/R1/CR} shows the average coverage ratio for 150 deployed nodes.
\parskip 0pt
DiLCO-2 protocol gives near similar coverage ratio with other ones for first 10 rounds and then decreased until the died of the network in the round $18^{th}$ because it consumes more energy with the effect of the network disconnection.
As shown in the figure ~\ref{Figures/ch3/R1/CR}, as the number of subregions increases, the coverage preservation for area of interest increases for a larger number of rounds. Coverage ratio decreases when the number of rounds increases due to dead nodes. Although some nodes are dead, thanks to DiLCO-8, DiLCO-16 and DiLCO-32 protocols, other nodes are preserved to ensure the coverage. Moreover, when we have a dense sensor network, it leads to maintain the coverage for a larger number of rounds. DiLCO-8, DiLCO-16 and DiLCO-32 protocols are slightly more efficient than other protocols, because they subdivide the area of interest into 8, 16 and 32~subregions; if one of the subregions becomes disconnected, the coverage may be still ensured in the remaining subregions.
-\subsubsection{Active Sensors Ratio}
+\item {{\bf Active Sensors Ratio}}
+%\subsubsection{Active Sensors Ratio}
Figure~\ref{Figures/ch3/R1/ASR} shows the average active nodes ratio for 150 deployed nodes.
\begin{figure}[h!]
\centering
\end{figure}
The results presented in figure~\ref{Figures/ch3/R1/ASR} show the increase in the number of subregions led to increase in the number of active nodes. The DiLCO-16 and DiLCO-32 protocols have a larger number of active nodes but it preserve the coverage for a larger number of rounds. The advantage of the DiLCO-16 and DiLCO-32 protocols are that even if a network is disconnected in one subregion, the other ones usually continues the optimization process, and this extends the lifetime of the network.
-\subsubsection{The percentage of stopped simulation runs}
+\item {{\bf The percentage of stopped simulation runs}}
+%\subsubsection{The percentage of stopped simulation runs}
Figure~\ref{Figures/ch3/R1/SR} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes.
\begin{figure}[h!]
\centering
It can be observed that the DiLCO-2 is the approach which stops first because it applied the optimization on only two subregions for the area of interest that is why it is first exhibits network disconnections.
Thus, as explained previously, in case of the DiLCO-16 and DiLCO-32 with several subregions, the optimization effectively continues as long as a network in a subregion is still connected. This longer partial coverage optimization participates in extending the network lifetime.
-\subsubsection{The Energy Consumption}
+\item {{\bf The Energy Consumption}}
+%\subsubsection{The Energy Consumption}
We measure the energy consumed by the sensors during the communication, listening, computation, active, and sleep modes for different network densities and compare it for different subregions. Figures~\ref{Figures/ch3/R1/EC95} and ~\ref{Figures/ch3/R1/EC50} illustrate the energy consumption for different network sizes for $Lifetime95$ and $Lifetime50$.
\begin{figure}[h!]
\end{figure}
In fact, a distributed method on the subregions greatly reduces the number of communications, the time of listening and computation so thanks to the partitioning of the initial network in several independent subnetworks.
-\subsubsection{Execution Time}
+\item {{\bf Execution Time}}
+%\subsubsection{Execution Time}
In this experiment, the execution time of the our distributed optimization approach has been studied. Figure~\ref{Figures/ch3/R1/T} gives the average execution times in seconds for the decision phase (solving of the optimization problem) during one round. They are given for the different approaches and various numbers of sensors. The original execution time is computed as described in section \ref{ch3:sec:04:02}.
%The original execution time is computed on a laptop DELL with intel Core i3 2370 M (2.4 GHz) processor (2 cores) and the MIPS (Million Instructions Per Second) rate equal to 35330. To be consistent with the use of a sensor node with Atmels AVR ATmega103L microcontroller (6 MHz) and a MIPS rate equal to 6 to run the optimization resolution, this time is multiplied by 2944.2 $\left( \frac{35330}{2} \times 6\right)$ and reported on Figure~\ref{fig8} for different network sizes.
The DiLCO-32 protocol has more suitable times at the same time it turn on redundant nodes more. We think that in distributed fashion the solving of the optimization problem in a subregion can be tackled by sensor nodes. Overall, to be able to deal with very large networks, a distributed method is clearly required.
-
-\subsubsection{The Network Lifetime}
+\item {{\bf The Network Lifetime}}
+%\subsubsection{The Network Lifetime}
In figure~\ref{Figures/ch3/R1/LT95} and \ref{Figures/ch3/R1/LT50}, network lifetime, $Lifetime95$ and $Lifetime50$ respectively, are illustrated for different network sizes.
\begin{figure}[h!]
\label{Figures/ch3/R1/LT50}
\end{figure}
-
+\end{enumerate}
\subsection{Performance Analysis for Primary Point Models}
-\label{ch3:sec:04:03}
+\label{ch3:sec:04:06}
In this section, we are studied the performance of DiLCO~16 approach for a different primary point models. The objective of this comparison is to select the suitable primary point model to be used by DiLCO protocol.
In this comparisons, DiLCO-16 protocol are used with five models which are called Model~1( With 5 Primary Points), Model~2 ( With 9 Primary Points), Model~3 ( With 13 Primary Points), Model~4 ( With 17 Primary Points), and Model~5 ( With 21 Primary Points).
-\subsubsection{Coverage Ratio}
+
+
+\begin{enumerate}[i)]
+
+\item {{\bf Coverage Ratio}}
+%\subsubsection{Coverage Ratio}
In this experiment, we Figure~\ref{Figures/ch3/R2/CR} shows the average coverage ratio for 150 deployed nodes.
\parskip 0pt
\begin{figure}[h!]
It is shown that all models provide a very near coverage ratios during the network lifetime, with very small superiority for the models with higher number of primary points. Moreover, when the number of rounds increases, coverage ratio produced by Model~3, Model~4, and Model~5 decreases in comparison with Model~1 and Model~2 due to the high energy consumption during the listening to take the decision after finishing optimization process for larger number of primary points. As shown in figure ~\ref{Figures/ch3/R2/CR}, Coverage ratio decreases when the number of rounds increases due to dead nodes. Although some nodes are dead,
thanks to Model~2, which is slightly more efficient than other Models, because it is balanced between the number of rounds and the better coverage ratio in comparison with other Models.
-\subsubsection{Active Sensors Ratio}
+\item {{\bf Active Sensors Ratio}}
+%\subsubsection{Active Sensors Ratio}
Figure~\ref{Figures/ch3/R2/ASR} shows the average active nodes ratio for 150 deployed nodes.
\begin{figure}[h!]
\centering
model with less number of primary points uses less active nodes than the other models, which uses a more number of primary points to represent the area of the sensor. According to the results that presented in figure~\ref{Figures/ch3/R2/CR}, we observe that although the Model~1 continue to a larger number of rounds, but it has less coverage ratio compared with other models. The advantage of the Model~2 approach is to use less number of active nodes for each round compared with Model~3, Model~4, and Model~5; and this led to continue for a larger number of rounds with extending the network lifetime. Model~2 has a better coverage ratio compared to Model~1 and acceptable number of rounds.
-\subsubsection{The percentage of stopped simulation runs}
+\item {{\bf he percentage of stopped simulation runs}}
+%\subsubsection{The percentage of stopped simulation runs}
In this study, we want to show the effect of increasing the primary points on the number of stopped simulation runs for each round. Figure~\ref{Figures/ch3/R2/SR} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes.
\begin{figure}[h!]
As shown in Figure~\ref{Figures/ch3/R2/SR}, when the number of primary points are increased, the percentage of the stopped simulation runs per round is increased. The reason behind the increase is the increase in the sensors dead when the primary points increases. We are observed that the Model~1 is a better than other models because it conserve more energy by turn on less number of sensors during the sensing phase, but in the same time it preserve the coverage with a less coverage ratio in comparison with other models. Model~2 seems to be more suitable to be used in wireless sensor networks.
-\subsubsection{The Energy Consumption}
+\item {{\bf The Energy Consumption}}
+%\subsubsection{The Energy Consumption}
In this experiment, we study the effect of increasing the primary points to represent the area of the sensor on the energy consumed by the wireless sensor network for different network densities. Figures~\ref{Figures/ch3/R2/EC95} and ~\ref{Figures/ch3/R2/EC50} illustrate the energy consumption for different network sizes for $Lifetime95$ and $Lifetime50$.
\begin{figure}[h!]
\centering
We see from the results presented in Figures~\ref{Figures/ch3/R2/EC95} and \ref{Figures/ch3/R2/EC50}, The energy consumed by the network for each round increases when the primary points increases, because the decision for optimization process will takes more time leads to consume more energy during the listening mode. The results show that Model~1 is the most competitive from the energy consumption point of view but the worst one from coverage ratio point of view. The other Models have a high energy consumption due to the increase in the primary points, which are led to increase the energy consumption during the listening mode before producing the solution by solving the optimization process. In fact, we see that Model~2 is a good candidate to be used by wireless sensor network because it preserve a good coverage ratio and a suitable energy consumption in comparison with other models.
-
-\subsubsection{Execution Time}
+\item {{\bf Execution Time}}
+%\subsubsection{Execution Time}
In this experiment, we have studied the impact of the increase in primary points on the execution time of DiLCO protocol. Figure~\ref{Figures/ch3/R2/T} gives the average execution times in seconds for the decision phase (solving of the optimization problem) during one round. The original execution time is computed as described in section \ref{ch3:sec:04:02}.
\begin{figure}[h!]
They are given for the different primary point models and various numbers of sensors. We can see from Figure~\ref{Figures/ch3/R2/T}, that Model~1 has lower execution time in comparison with other Models, because it used smaller number of primary points to represent the area of the sensor. Conversely, the other primary point models have been presented a higher execution times.
Moreover, Model~2 has more suitable times and coverage ratio that lead to continue for a larger number of rounds extending the network lifetime. We think that a good primary point model, this one that balances between the coverage ratio and the number of rounds during the lifetime of the network.
-\subsubsection{The Network Lifetime}
+\item {{\bf The Network Lifetime}}
+%\subsubsection{The Network Lifetime}
Finally, we will study the effect of increasing the primary points on the lifetime of the network. In Figure~\ref{Figures/ch3/R2/LT95} and in Figure~\ref{Figures/ch3/R2/LT50}, network lifetime, $Lifetime95$ and $Lifetime50$ respectively, are illustrated for different network sizes.
\begin{figure}[h!]
As highlighted by figures~\ref{Figures/ch3/R2/LT95} and \ref{Figures/ch3/R2/LT50}, the network lifetime obviously increases when the size of the network increases, with Model~1 that leads to the larger lifetime improvement.
Comparison shows that the Model~1, which uses less number of primary points, is the best one because it is less energy consumption during the network lifetime. It is also the worst one from the point of view of coverage ratio. Our proposed Model~2 efficiently prolongs the network lifetime with a good coverage ratio in comparison with other models.
-
+\end{enumerate}
\subsection{Performance Comparison with other Approaches}
-\label{ch3:sec:04:04}
+\label{ch3:sec:04:07}
Based on the results, which are conducted from previous two subsections, \ref{ch3:sec:04:02} and \ref{ch3:sec:04:03}, we have found that DiLCO-16 protocol and DiLCO-32 protocol with Model~2 are the best candidates to be compared with other two approaches. The first approach, called DESK that proposed by ~\cite{DESK}, which is a full distributed coverage algorithm. The second approach, called GAF~\cite{GAF}, consists in dividing the region into fixed squares. During the decision phase, in each square, one sensor is chosen to remain on during the sensing phase time.
-\subsubsection{Coverage Ratio}
+\begin{enumerate}[i)]
+
+\item {{\bf Coverage Ratio}}
+%\subsubsection{Coverage Ratio}
In this experiment, the average coverage ratio for 150 deployed nodes has been demonstrated figure~\ref{Figures/ch3/R3/CR}.
\parskip 0pt
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.
-\subsubsection{Active Sensors Ratio}
+\item {{\bf Active Sensors Ratio}}
+%\subsubsection{Active Sensors Ratio}
It is important to have as few active nodes as possible in each round, in order to minimize the energy consumption and maximize the network lifetime. Figure~\ref{Figures/ch3/R3/ASR} shows the average active nodes ratio for 150 deployed nodes.
\begin{figure}[h!]
The results presented in figure~\ref{Figures/ch3/R3/ASR} show the superiority of the proposed DiLCO-16 protocol and DiLCO-32 protocol, in comparison with the other approaches. We have observed that DESK and GAF have 37.5 \% and 44.5 \% active nodes and DiLCO-16 protocol and DiLCO-32 protocol compete perfectly with only 17.4 \%, 24.8 \% and 26.8 \% active nodes for the first 14 rounds. Then as the number of rounds increases DiLCO-16 protocol and DiLCO-32 protocol have larger number of active nodes in comparison with DESK and GAF, especially from round $35^{th}$ because they give a better coverage ratio than other approaches. We see that DESK and GAF have less number of active nodes beginning at the rounds $35^{th}$ and $32^{th}$ because there are many nodes are died due to the high energy consumption by the redundant nodes during the sensing phase.
-\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/ch3/R3/SR} illustrates the percentage of stopped simulation
runs per round for 150 deployed nodes.
\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.
-\subsubsection{The Energy Consumption}
+
+\item {{\bf The Energy Consumption}}
+%\subsubsection{The Energy Consumption}
In this experiment, we have studied the effect of the energy consumed by the wireless sensor network during the communication, computation, listening, active, and sleep modes for different network densities and compare it with other approaches. Figures~\ref{Figures/ch3/R3/EC95} and ~\ref{Figures/ch3/R3/EC50} illustrate the energy consumption for different network sizes for $Lifetime95$ and $Lifetime50$.
\begin{figure}[h!]
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.
-\subsubsection{The Network Lifetime}
+
+\item {{\bf The Network Lifetime}}
+%\subsubsection{The Network Lifetime}
In this experiment, we have observed the superiority of DiLCO-16 protocol and DiLCO-32 protocol against other two approaches in prolonging the network lifetime. In figures~\ref{Figures/ch3/R3/LT95} and \ref{Figures/ch3/R3/LT50}, network lifetime, $Lifetime95$ and $Lifetime50$ respectively, are illustrated for different network sizes.
\begin{figure}[h!]
Comparison shows that DiLCO-16 protocol and DiLCO-32 protocol, which are used distributed optimization over the subregions, is the best one because it is robust to network disconnection during the network lifetime as well as it consumes less energy in comparison with other approaches. It also means that distributing the algorithm in each node and subdividing the sensing field into many subregions, which are managed independently and simultaneously, is the most relevant way to maximize the lifetime of a network.
+\end{enumerate}
+
\section{Conclusion}
\label{ch3: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
