%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\emph{ \begin{center} \Large Distributed Coverage Optimization Techniques for Improving
- Lifetime of Wireless Sensor Networks \end{center}}
+\emph{ \begin{center} \Large Distributed coverage optimization techniques for improving
+ lifetime of wireless sensor networks \end{center}}
%\emph{ \begin{center} \large By \end{center}}
\emph{ \begin{center} \large Ali Kadhum Idrees \\ University of Franche-Comt\'e, 2015 \end{center}}
%\emph{ \begin{center} \large The University of Franche-Comt\'e, 2015 \end{center}}
-Wireless sensor networks (WSNs) have recently received a great deal of research attention due to their wide range of potential applications. Many important characteristics provided by the WSNs make them different from other wireless ad-hoc networks. Furthermore, these characteristics impose lots of limitations that lead to several challenges in the network. These challenges include coverage, topology control, routing, data fusion, security, and many others. One of the main research challenges faced in wireless sensor networks is to preserve continuously and effectively the coverage of an area of interest to be monitored, while simultaneously preventing as much as possible a network failure due to battery-depleted nodes.
-
+%Wireless sensor networks (WSNs) have recently received a great deal of research attention due to their wide range of potential applications. Many important characteristics provided by the WSNs make them different from other wireless ad-hoc networks. Furthermore, these characteristics impose lots of limitations that lead to several challenges in the network. These challenges include coverage, topology control, routing, data fusion, security, and many others. One of the main research challenges faced in wireless sensor networks is to preserve continuously and effectively the coverage of an area of interest to be monitored, while simultaneously preventing as much as possible a network failure due to battery-depleted nodes.
In this dissertation, we highly focus on the area coverage problem, energy-efficiency is also the foremost requirement. We have considered distributed optimization protocols with the ultimate objective of prolonging the network lifetime. The proposed distributed optimization protocols (including algorithms, models, and solving integer programs) should be energy-efficient protocols. To address
this problem, this dissertation proposes two-step approaches. Firstly, the sensing field is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of our proposed distributed optimization protocols is distributed and applied on the
sensor nodes in each subregion so as to optimize the coverage and the lifetime performances. In this dissertation, three coverage optimization protocols are proposed. These protocols combine two efficient techniques: leader election for each subregion, followed by an optimization-based planning of sensor activity scheduling decisions for each subregion.
-Last but not least, we propose a Perimeter-based Coverage Optimization (PeCO) protocol which is also distributed among sensor nodes in each subregion.The novelty of our approach lies essentially in the formulation of a new
-mathematical optimization model based on a perimeter coverage level to schedule sensors' activities, whereas we used primary points coverage model in the two previous models. A new integer program coverage model is solved by the leader during the decision phase so as to provide only one cover set of sensors for the sensing phase.
+Last but not least, we propose a Perimeter-based Coverage Optimization (PeCO) protocol which is also distributed among sensor nodes in each subregion. The novelty of our approach lies essentially in the formulation of a new mathematical optimization model based on a perimeter coverage level to schedule sensors' activities, whereas we used primary points coverage model in the two previous models. A new integer program coverage model is solved by the leader during the decision phase so as to provide only one cover set of sensors for the sensing phase.
Extensive simulations are conducted using the discrete event simulator OMNeT++ to validate the efficiency of each of our proposed protocols. We refer to the characteristics of a Medusa II sensor for the energy consumption and the time computation. In comparison with two other existing methods, our protocols are able to increase
the WSN lifetime and provide improved coverage performance.
In this chapter, we propose an approach called Perimeter-based Coverage Optimization
protocol (PeCO).
%The PeCO protocol merges between two energy efficient mechanisms, which are used the main advantages of the centralized and distributed approaches and avoids the most of their disadvantages. An energy-efficient activity scheduling mechanism based new optimization model is performed by each leader in the subregions.
-The framework is similar to the one described in section \ref{ch4:sec:02:03}, but in this approach, the optimization model is based on the perimeter coverage model in order to producing the optimal cover set of active sensors, which are taken the responsibility of sensing during the current period.
+The framework is similar to the one described in section \ref{ch4:sec:02:03}. But in this approach, the optimization model is based on the perimeter coverage model in order to produce the optimal cover set of active sensors, which are taken the responsibility of sensing during the current period.
-The rest of the chapter is organized as follows. The next section is devoted to the PeCO protocol description and section~\ref{ch6:sec:03} focuses on the coverage model formulation which is used to schedule the activation of sensor nodes based on perimeter coverage model. Section~\ref{ch6:sec:04} presents simulations results and discusses the comparison with other approaches. Finally, concluding remarks are drawn in section~\ref{ch6:sec:05}.
+The rest of the chapter is organized as follows. The next section is devoted to the PeCO protocol description and section~\ref{ch6:sec:03} focuses on the coverage model formulation which is used to schedule the activation of sensor nodes. Section~\ref{ch6:sec:04} presents simulation results and discusses the comparison with other approaches. Finally, concluding remarks are drawn in section~\ref{ch6:sec:05}.
-\section{The PeCO Protocol Description}
+\section{Description of the PeCO Protocol}
\label{ch6:sec:02}
-\noindent In this section, we describe in details our Lifetime Coverage
-Optimization protocol. First we present the assumptions we made and the models
-we considered (in particular the perimeter coverage one), second we describe the
-background idea of our protocol, and third we give the outline of the algorithm
-executed by each node.
+%\noindent In this section, we describe in details our Lifetime Coverage Optimization protocol.
+First we present the assumptions we made and the models
+we considered (in particular the perimeter coverage one), second we describe the background idea of our protocol, and third we give the outline of the algorithm executed by each node.
\subsection{Assumptions and Models}
\label{ch6:sec:02:01}
-The PeCO protocol uses the same assumptions and network model that presented in section \ref{ch4:sec:02:01}.
+The PeCO protocol uses the same assumptions and network model than both DiLCO and MuDiLCO protocols. All the hypotheses can be found in section \ref{ch4:sec:02:01}.
The PeCO protocol uses the same perimeter-coverage model as Huang and Tseng in~\cite{ref133}. It can be expressed as follows: a sensor is said to be a perimeter covered if all the points on its perimeter are covered by at least one sensor other than itself. They proved that a network area is
$k$-covered if and only if each sensor in the network is $k$-perimeter-covered (perimeter covered by at least $k$ sensors).
First, we have the following sets:
\begin{itemize}
-\item $J$ represents the set of WSN sensor nodes;
+\item $J$ represents the set of sensor nodes;
\item $A \subseteq J $ is the subset of alive sensors;
\item $I_j$ designates the set of coverage intervals (CI) obtained for
- sensor~$j$.
+ sensor~$j$, which have been defined according to the method introduced in section~\ref{ch6:sec:02:01}.
\end{itemize}
-$I_j$ refers to the set of coverage intervals which have been defined according
-to the method introduced in section~\ref{ch6:sec:02:01}. For a coverage interval $i$,
-let $a^j_{ik}$ denotes the indicator function of whether sensor~$k$ is involved
+First, for a coverage interval $i$, let $a^j_{ik}$ denotes the indicator function of whether sensor~$k$ is involved
in coverage interval~$i$ of sensor~$j$, that is:
\begin{equation}
a^j_{ik} = \left \{
%Each node has an initial energy level, in Joules, which is randomly drawn in the interval $[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 more participate 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) with the time in seconds for one period (3600 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.
-The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good network coverage and a longer WSN lifetime as shown in Table \ref{my-beta-alfa}. We have given a higher priority to the undercoverage (by setting the $\alpha^j_i$ with a larger value than $\beta^j_i$) so as to prevent the non-coverage for the interval~$i$ of the
-sensor~$j$. On the other hand, we have assigned to
+The values of $\alpha^j_i$ and $\beta^j_i$ have been chosen to ensure a good network coverage and a longer WSN lifetime as shown in Table \ref{my-beta-alfa}. We set the values of $\alpha^j_i$ and $\beta^j_i$ to 0.6 and 0.4 respectively. We have given a higher priority to the undercoverage (by setting the $\alpha^j_i$ with a larger value than $\beta^j_i$) so as to prevent the non-coverage for the interval~$i$ of the sensor~$j$. On the other hand, we have assigned to
$\beta^j_i$ a value which is slightly lower so as to minimize the number of active sensor nodes which contribute in covering the interval.
\begin{table}[h]
\end{tabular}
\end{table}
-With the performance metrics, described in section \ref{ch4:sec:04:04}, we evaluate the efficiency of our approach. We use the modeling language and the optimization solver which are mentioned in section \ref{ch4:sec:04:02}. In addition, we use the same energy consumption model, presented in section \ref{ch4:sec:04:03}.
+With the performance metrics, described in section \ref{ch4:sec:04:04}, we evaluate the efficiency of our approach. We use the modeling language and the optimization solver which are mentioned in section \ref{ch4:sec:04:02}. In addition, we use the same energy consumption model, as previously, described in section \ref{ch4:sec:04:03}.
\subsection{Simulation Results}
\label{ch6:sec:04:02}
-In order to assess and analyze the performance of our protocol we have implemented PeCO protocol in OMNeT++~\cite{ref158} simulator. Besides PeCO, three other protocols, described in the next paragraph, will be evaluated for comparison purposes.
+In order to assess and analyze the performance of our protocol we have implemented PeCO protocol in OMNeT++~\cite{ref158} simulator.
+%Besides PeCO, three other protocols, described in the next paragraph, will be evaluated for comparison purposes.
%The simulations were run on a laptop DELL with an Intel Core~i3~2370~M (2.4~GHz) processor (2 cores) whose MIPS (Million Instructions Per Second) rate is equal to 35330. To be consistent with the use of a sensor node based on Atmels AVR ATmega103L microcontroller (6~MHz) having a MIPS rate equal to 6, the original execution time on the laptop is multiplied by 2944.2 $\left(\frac{35330}{2} \times \frac{1}{6} \right)$. 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.
-As said previously, the PeCO is compared with three other approaches. The first one, called DESK, is a fully distributed coverage algorithm proposed by \cite{DESK}. The second one, called GAF~\cite{GAF}, consists in dividing the monitoring area into fixed squares. Then, during the decision phase, in each square, one sensor is chosen to remain active during the sensing phase. The last one, the DiLCO protocol~\cite{Idrees2}, is an improved version of a research work we presented in~\cite{ref159}. Let us notice that PeCO and DiLCO protocols are based on the same framework. In particular, the choice for the simulations of a partitioning in 16~subregions was chosen because it corresponds to the configuration producing the better results for DiLCO. The protocols are distinguished from one another by the formulation of the integer program providing the set of sensors which have to be activated in each sensing phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, whereas PeCO protocol objective is to reach a desired level of coverage for each sensor perimeter. In our experimentations, we chose a level of coverage equal to one ($l=1$).
+PeCO protocol is compared with three other approaches. DESK \cite{DESK}, GAF~\cite{GAF}, and DiLCO~\cite{Idrees2} is an improved version of a research work we presented in~\cite{ref159}, where DiLCO protocol is described in chapter 4. Let us notice that PeCO and DiLCO protocols are based on the same framework. In particular, the choice for the simulations of a partitioning in 16~subregions was chosen because it corresponds to the configuration producing the better results for DiLCO. The protocols are distinguished from one another by the formulation of the integer program providing the set of sensors which have to be activated in each sensing phase. DiLCO protocol tries to satisfy the coverage of a set of primary points, whereas PeCO protocol objective is to reach a desired level of coverage for each sensor perimeter. In our experimentations, we chose a level of coverage equal to one ($l=1$).
\label{fig444}
\end{figure}
-\subsubsection{The Energy Consumption}
+\subsubsection{Energy Consumption}
\label{ch6:sec:04:02:03}
We studied the effect of the energy consumed by the WSN during the communication,
illustrate the energy consumption for different network sizes and for
$Lifetime95$ and $Lifetime50$. The results show that our PeCO protocol is the
most competitive from the energy consumption point of view. As shown in both
-figures, PeCO consumes much less energy than the three other methods. One might
-think that the resolution of the integer program is too costly in energy, but
-the results show that it is very beneficial to lose a bit of time in the
-selection of sensors to activate. Indeed the optimization program allows to
-reduce significantly the number of active sensors and so the energy consumption
-while keeping a good coverage level.
+figures, PeCO consumes much less energy than the three other methods. \\ \\ \\ \\ \\ \\
+
+One might think that the resolution of the integer program is too costly in energy, but the results show that it is very beneficial to lose a bit of time in the selection of sensors to activate. Indeed the optimization program allows to reduce significantly the number of active sensors and so the energy consumption while keeping a good coverage level.
\begin{figure}[h!]
\centering
-\subsubsection{The Network Lifetime}
+\subsubsection{Network Lifetime}
\label{ch6:sec:04:02:04}
-We observe the superiority of PeCO and DiLCO protocols in comparison with the
-two other approaches in prolonging the network lifetime. In
-Figures~\ref{fig3LT}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for
-different network sizes. As highlighted by these figures, the lifetime
-increases with the size of the network, and it is clearly largest for DiLCO
-and PeCO protocols. For instance, for a network of 300~sensors and coverage
-ratio greater than 50\%, we can see on Figure~\ref{fig3LT}(b) that the lifetime
-is about twice longer with PeCO compared to DESK protocol. The performance
-difference is more obvious in Figure~\ref{fig3LT}(b) than in
-Figure~\ref{fig3LT}(a) because the gain induced by our protocols increases with
- time, and the lifetime with a coverage of 50\% is far longer than with
+We observe the superiority of PeCO and DiLCO protocols in comparison with the two other approaches in prolonging the network lifetime. In
+Figures~\ref{fig3LT}(a) and (b), $Lifetime95$ and $Lifetime50$ are shown for different network sizes. As highlighted by these figures, the lifetime increases with the size of the network, and it is clearly largest for DiLCO and PeCO protocols. For instance, for a network of 300~sensors and coverage ratio greater than 50\%, we can see on Figure~\ref{fig3LT}(b) that the lifetime is about twice longer with PeCO compared to DESK protocol. The performance difference is more obvious in Figure~\ref{fig3LT}(b) than in Figure~\ref{fig3LT}(a) because the gain induced by our protocols increases with time, and the lifetime with a coverage of 50\% is far longer than with
95\%.
\begin{figure} [p]
In chapter 1, We started with a general overview on wireless sensor networks. We have described various concepts, mechanisms, types, applications, and challenges in WSNs. Several energy-efficient techniques so as to improve the network lifetime of WSNs have been presented. The coverage problem, the network lifetime, and the energy consumption modeling in WSNs have been explained. A brief survey about literature on coverage algorithms is achieved in chapter 2.
We have classified those works into centralized and distributed algorithms. We have given a brief comparison of the main characteristics of each approach. Finally we have included in chapter 3 a comparative study of different evaluation tools dedicated to WSNs. In addition, we have illustrated various commercial and free optimization solvers considering the main features of each one.
-In the second part of the dissertation, We have designed three new different optimization protocols, which schedules nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. We propose two-step approaches. Firstly, the field of sensing is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of the proposed optimization protocols is applied in each subregion in a distributed parallel way to optimize both coverage and lifetime performances. The proposed protocols combine two efficient mechanisms: network leader election and sensor activity scheduling, where the challenges include how to select the most efficient leader in each subregion, the best
+In the second part of the dissertation, We design three new different optimization protocols, which schedules nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. We propose two-step approaches. Firstly, the field of sensing is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of the proposed optimization protocols is applied in each subregion in a distributed parallel way to optimize both coverage and lifetime performances. The proposed protocols combine two efficient mechanisms: network leader election and sensor activity scheduling, where the challenges include how to select the most efficient leader in each subregion, the best
representative active nodes that will optimize the network lifetime while taking the responsibility of covering the corresponding subregion.
-In chapter 4, we have proposed an optimization protocol called Distributed Lifetime Coverage Optimization protocol (DiLCO), which optimizes the coverage and the lifetime of a wireless sensor network. DiLCO protocol is distributed in each sensor node in the subregions of the sensing field. It is implemented in each subregion simultaneously and independently. The proposed DiLCO protocol is a periodic protocol where each period consists of 4 phases: information exchange, leader election, decision, and sensing. The sensor nodes collaborate in each subregion to elect the leader. The leader applies activity scheduling based optimization in order to provide only one optimal set of active sensor nodes that takes the mission of sensing during this period. The performance of our DiLCO protocol has been evaluated by a series of simulations. We have presented a comparison between our proposed protocol and two other existing protocols known in the literature: DESK and GAF. The experimental results have validated our protocol and showed its efficiency in the optimization of the coverage and the lifetime compared to the two benchmarking methods.
+In chapter 4, we propose an optimization protocol called Distributed Lifetime Coverage Optimization protocol (DiLCO), which optimizes the coverage and the lifetime of a wireless sensor network. DiLCO protocol is distributed in each sensor node in the subregions of the sensing field. It is implemented in each subregion simultaneously and independently. The proposed DiLCO protocol is a periodic protocol where each period consists of 4 phases: information exchange, leader election, decision, and sensing. The sensor nodes collaborate in each subregion to elect the leader. The leader applies activity scheduling based optimization in order to provide only one optimal set of active sensor nodes that takes the mission of sensing during this period. The performance of our DiLCO protocol has been evaluated by a series of simulations. We have presented a comparison between our proposed protocol and two other existing protocols known in the literature: DESK and GAF. The experimental results have validated our protocol and showed its efficiency in the optimization of the coverage and the lifetime compared to the two benchmarking methods.
Next, we propose in chapter 5 a method called Multiround Distributed Lifetime Coverage Optimization protocol (MuDiLCO), which is an extension of the DiLCO protocol introduced in chapter 4. MuDiLCO implemented an activity scheduling based optimization in order to provide multiple sets of active sensor nodes, for several rounds in the sensing phase. We have thus introduced an improved coverage optimization model that make a multiround optimization, whilst it was a single round optimization in DiLCO. We have conducted many simulations comparing the proposed MuDiLCO protocol for different number of rounds, as well as with DiLCO, DESK, and GAF.
-In chapter 6, we have proposed an approach called Perimeter-based Coverage Optimization protocol (PeCO) in order to optimize the lifetime coverage, so that it provides activity scheduling which ensures sensing coverage as long as possible. Like DiLCO and MuDiLCO, PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new integer program during the decision phase. The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs.
+In chapter 6, we propose an approach called Perimeter-based Coverage Optimization protocol (PeCO) in order to optimize the lifetime coverage, so that it provides activity scheduling which ensures sensing coverage as long as possible. Like DiLCO and MuDiLCO, the PeCO protocol is distributed among sensor nodes in each subregion. The novelty of our approach, in comparison with DiLCO and MuDiLCO, lies essentially in the formulation of a new mathematical optimization model based on the perimeter coverage level to schedule sensors’ activities. A leader provides one schedule during the current period by executing the new integer program during the decision phase. The extensive simulation experiments have demonstrated that PeCO can offer longer lifetime coverage for WSNs.
-Finally, we outlined some interesting issues that will be considered in our perspectives which are discussed in more detail next.
+Finally, we outline some interesting issues that will be considered in our perspectives which are discussed in more detail next.
\section*{1. General Introduction}
\addcontentsline{toc}{section}{1. General Introduction }
-The enormous development of wireless networks, with the emergence of fourth and fifth-generation technology, are leading to the provision of various services to customers around the world that make the Internet more widely used. This kind of wireless networks may not be appropriate to be used in some sensitive areas that need to deploy a large number of wireless devices, which are able to sense, process, and communicate with each other in a distributed way, so as to collect the sensed measurements directly from physical dangerous environments such as volcanoes, nuclear reactors, forest fires, or military battle fields. Therefore, a specific type of wireless networks, called Wireless Sensor Network (WSN), has emerged to cope with these challenges.
+%The enormous development of wireless networks, with the emergence of fourth and fifth-generation technology, are leading to the provision of various services to customers around the world that make the Internet more widely used. This kind of wireless networks may not be appropriate to be used in some sensitive areas that need to deploy a large number of wireless devices, which are able to sense, process, and communicate with each other in a distributed way, so as to collect the sensed measurements directly from physical dangerous environments such as volcanoes, nuclear reactors, forest fires, or military battle fields. Therefore, a specific type of wireless networks, called Wireless Sensor Network (WSN), has emerged to cope with these challenges.
+Wireless sensor networks (WSNs) have recently received a great deal of research attention due to their wide range of potential applications. Many important characteristics provided by the WSNs make them different from other wireless ad-hoc networks. Furthermore, these characteristics impose lots of limitations that lead to several challenges in the network. These challenges include coverage, topology control, routing, data fusion, security, and many others. One of the main research challenges faced in wireless sensor networks is to preserve continuously and effectively the coverage of an area of interest to be monitored, while simultaneously preventing as much as possible a network failure due to battery-depleted nodes.
WSN is an ad hoc wireless networks, which consists of a large number of wireless cheap devices called sensors. A sensor node can perform communication, sensing, processing, and storage tasks with a limited capability. It can be used by human to monitor physical phenomena remotely and without any outside intervention. Wireless sensor nodes are self-contained units equipped with a radio transceiver, a microcontroller, a small memory, and a power source, usually a battery. These sensor nodes are cooperating together autonomously to perform the assigned tasks. The distributed self-organization and self-configuration capabilities of wireless sensor nodes enable myriad applications for monitoring, sensing and controlling the physical world.
-The sensor nodes have several limitations, such as the power source, processing capability, bandwidth, uncertainty of sensed data, and the vulnerability of sensor nodes to the physical world. These limitations have been tackled by many researchers during the last years, and consequently, many solutions taking these constraints into account have been proposed. Sensor nodes are battery-powered without means of recharging or replacing, usually due to environmental (hostile or unpractical environments) or cost reasons. %Since batteries are the most important limited resource inside sensor nodes, it is desirable that 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.
+The sensor nodes have several limitations, such as the power source, processing capability, bandwidth, uncertainty of sensed data, and the vulnerability of sensor nodes to the physical world. These limitations have been tackled by many researchers during the last years, and consequently, many solutions taking these constraints into account have been proposed. Most of sensor nodes are battery-powered without means of recharging or replacing, usually due to environmental (hostile or unpractical environments) or cost reasons. %Since batteries are the most important limited resource inside sensor nodes, it is desirable that 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.
Since the network lifetime depends on sensor lifetime, the power depletion represents the most significant part when designing of the WSN protocols due to the limited capacity of the sensor batteries. The major goal is to extend the network lifetime, taking into consideration the energy source limitations. Several energy-efficient approaches have been suggested to minimize the energy consumption and extend the network lifetime during monitoring a certain area by a WSN. %For example, one of the ways is to turn off the redundant sensors and put them in sleep mode to maintain the energy, whilst the active sensors perform the sensing coverage task during their life.
Specifically, the energy-efficient protocols proposed in this dissertation focus on the area coverage problem in WSNs. The major goal of the area coverage problem is to ensure monitoring the entire sensing field for as long as possible. The area coverage problem is closely related to the performance of WSNs in many applications, such as monitoring a battlefield, target detection, tracking, personal protection, animal habit monitoring, and homeland security.
\section*{2. Motivation of the Dissertation}
\addcontentsline{toc}{section}{2. Motivation of the Dissertation }
-One of the fundamental challenges in Wireless Sensor Networks (WSNs) is the coverage preservation and the extension of the network lifetime continuously and effectively when monitoring a certain area (or region) of interest. Since sensor nodes have limited battery life; since it is impossible to replace batteries, especially in remote and hostile
+One of the fundamental challenges in Wireless Sensor Networks (WSNs) is the coverage preservation and the extension of the network lifetime continuously and effectively when monitoring a certain area (or region) of interest. Since some sensor nodes have limited battery life; since it is impossible to replace batteries, especially in remote and hostile
environments, it is desirable that a WSN should be deployed with high density because spatial redundancy can then be exploited to increase the lifetime of the network. In such a high-density network, if all sensor nodes were activated at the same time, the lifetime would be reduced. To extend the lifetime of the network, the main idea is to take advantage of the overlapping sensing regions of some sensor nodes to save energy by turning off some of them during the sensing phase. Obviously, the deactivation of nodes is only relevant if the coverage of the monitored area is not affected.
-Although many works on energy-efficient coverage have been introduced, there is still need for a protocol which can schedule sensor nodes in an efficient way with: a minimum number of active sensors and less communication overhead so as to maintain the coverage and extend the network lifetime as long as possible. The main question is how to reduce the redundancy while maintaining a good coverage with minimum energy consumption?
+Although many works on energy-efficient coverage have been introduced, there is still need for strategies which can schedule sensor nodes in an efficient way with: a minimum number of active sensors and less communication overhead so as to maintain the coverage and extend the network lifetime as long as possible. The main question is how to reduce the redundancy while maintaining a good coverage with minimum energy consumption?
\iffalse
\section*{3. The Objective of this Dissertation}
The main contributions in this dissertation concentrate on designing distributed optimization protocols to extend the lifetime of WSNs. We summarize the main contributions of our research as follows:
\begin{enumerate} [i)]
-\item We devise a framework to schedule nodes to be activated alternatively such that the network lifetime is prolonged while ensuring that a certain level of coverage is preserved. A key idea in our framework is to exploit a spatial-temporal subdivision. On the one hand, the area of interest is divided into several smaller subregions. On the other hand, the timeline is divided into periods of equal length. In each subregion, the sensor nodes will cooperatively choose a leader which will schedule nodes' activities, and this grouping of sensors is similar to typical cluster architecture.
+\item We design a scheme to schedule nodes to be activated alternatively such that the network lifetime is prolonged while ensuring that a certain level of coverage is preserved. A key idea in our scheme is to exploit a spatial-temporal subdivision. On the one hand, the area of interest is divided into several smaller subregions. On the other hand, the timeline is divided into periods of equal length. In each subregion, the sensor nodes will cooperatively choose a leader which will schedule nodes' activities.
+%, and this grouping of sensors is similar to typical cluster architecture.
-\item We design a protocol, called the Distributed Lifetime Coverage Optimization (DILCO) protocol, which maintains the coverage and improves the lifetime in WSNs. DILCO protocol is presented in chapter 4. It is an extension of our approach introduced in \cite{ref159}. In \cite{ref159}, the protocol is deployed over only two subregions. In DILCO protocol, 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. 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 broadcasted by the leader to every node of its subregion.
+\item We design a protocol, called the Distributed Lifetime Coverage Optimization (DILCO) protocol, which maintains the coverage and improves the lifetime in WSNs. DILCO protocol is presented in chapter 4. It is an extension of our approach introduced in \cite{ref159}. In \cite{ref159}, the protocol is deployed over only two subregions. In the DILCO protocol, 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. 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 broadcasted by the leader to every node of its subregion.
\item %We extend our work that explained in chapter 4 and present a generalized framework that can be applied to provide the cover sets of all rounds in each period.
-The MuDiLCO protocol for Multiround Distributed Lifetime Coverage Optimization protocol, presented in chapter 5, is an extension of the approach introduced in chapter 4. In DiLCO protocol, the activity scheduling based optimization is planned for each subregion periodically only for one sensing round. Whilst, we study the possibility of dividing the sensing phase into multiple rounds. In fact, we make a multiround optimization, while it was a single round optimization in our previous contribution. The activation of the sensors is planned for many rounds in advance compared with the previous approach.
+The MuDiLCO protocol for Multiround Distributed Lifetime Coverage Optimization protocol, presented in chapter 5, is an extension of the approach introduced in chapter 4. In the DiLCO protocol, the activity scheduling based optimization is planned for each subregion periodically only for one sensing round. Whilst, we study the possibility of dividing the sensing phase into multiple rounds. In fact, we make a multiround optimization, while it was a single round optimization in our previous contribution. The activation of the sensors is planned for many rounds in advance compared with the previous approach.
%\item We devise a framework to schedule nodes to be activated alternatively such that the network lifetime is prolonged while ensuring that a certain level of coverage is preserved. A key idea in our framework is to exploit the spatial-temporal subdivision. On the one hand, the area of interest is divided into several smaller subregions and, on the other hand, the timeline is divided into periods of equal length. In each subregion, the sensor nodes will cooperatively choose a leader which will schedule nodes' activities, and this grouping of sensors is similar to typical cluster architecture.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\emph{ \begin{center} \Large Techniques d'Optimisation Distribuées de la Couverture pour Améliorer la Durée de Vie des Réseaux de Capteurs sans Fil \end{center}}
+\emph{ \begin{center} \Large Techniques d'optimisation distribuées de la couverture pour améliorer la durée de vie des réseaux de capteurs sans fil \end{center}}
%\emph{ \begin{center} \large By \end{center}}
\emph{ \begin{center} \large Ali Kadhum Idrees \\ Université de Franche-Comt\'e, 2015 \end{center}}
%\emph{ \begin{center} \large The University of Franche-Comt\'e, 2015 \end{center}}
\emph{ \begin{center} \large Encadrants: Raphaël Couturier, Karine Deschinkel et Michel Salomon \end{center}}
-Les réseaux de capteurs sans fil ont suscité beaucoup de travaux de recherche au cours des dernières années en raison de leur large gamme d'applications potentielles. Les caractéristiques des n\oe uds capteurs imposent des contraints enterme de consommation d'énergie et de capacité de traitement qui rendent caduque les protocoles des réseaux ad-hoc sans fil, avec de nombreux défis à résoudre. Parmi ces défis, on peut noter la préservation de la couverture, le contrôle de la topologie, le routage, la fusion de données, la sécurité, etc. La préservation de la couverture d'une région à surveiller, de manière permanente et efficace, tout en empêchant autant que possible un dysfonctionnement du réseau en raison du déchargement de la batterie de certains n\oe uds, est une des problématique de recherche majeures.
+Les réseaux de capteurs sans fil ont suscité beaucoup de travaux de recherche au cours des dernières années en raison de leur large gamme d'applications potentielles. Les caractéristiques des n\oe uds capteurs imposent des contraintes de consommation d'énergie et de capacité de traitement qui rendent caduque les protocoles des réseaux ad-hoc sans fil, avec de nombreux défis à résoudre. Parmi ces défis, on peut noter la préservation de la couverture, le contrôle de la topologie, le routage, la fusion de données, la sécurité, etc. La préservation de la couverture d'une région à surveiller, de manière permanente et efficace, tout en empêchant autant que possible un dysfonctionnement du réseau en raison du déchargement de la batterie de certains n\oe uds, est une des problématiques de recherche majeures.
-Dans cette thèse, nous nous sommes intéressés au problème de la préservation de la couverture, ainsi qu'à l'efficatité qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudiés les protocoles d'optimisation distribués avec l'objectif ultime de prolonger la durée de vie opérationnelle du réseau. Les protocoles proposés doivent être efficaces en terme de consommation énergétique induite par les calculs et les communications. Pour résoudre le problème, nous avons proposé des nouvelles approches en deux étapes. Dans un premier temps, la région à surveiller est divisée en petites sous-régions en utilisant le concept de la méthode diviser pour mieux régner. Dans un second temps, un de nos protocoles est exécuté par chacun des n\oe uds capteurs dans chaque sous-région, afin d'optimiser la couverture et la durée de vie du réseau. Nous proposons trois protocoles distribués qui combinent, chacun, deux techniques efficaces: l'élection d'un n\oe ud leader dans chaque sous-région, suivie par la mise en oeuvre par celui-ci d'un processus de décision via l'optimisation de l'ordonnancement d'activité des n\oe uds capteurs de sa sous-région.
+Dans cette thèse, nous nous sommes intéressés au problème de la préservation de la couverture, ainsi qu'à l'efficatité qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudié les protocoles d'optimisation distribués avec l'objectif ultime de prolonger la durée de vie opérationnelle du réseau. Les protocoles proposés doivent être efficaces en consommation énergétique induite par les calculs et les communications. Pour résoudre le problème, nous avons proposé des nouvelles approches en deux étapes. Dans un premier temps, la région à surveiller est divisée en petites sous-régions en utilisant le concept de la méthode diviser pour mieux régner. Dans un second temps, un protocole est exécuté par chacun des n\oe uds capteurs dans chaque sous-région, afin d'optimiser la couverture et la durée de vie du réseau. Nous proposons trois protocoles distribués qui combinent, chacun, deux techniques efficaces: l'élection d'un n\oe ud leader dans chaque sous-région, suivie par la mise en oeuvre par celui-ci d'un processus de décision via l'optimisation de l'ordonnancement d'activité des n\oe uds capteurs de sa sous-région.
Le premier protocole proposé est appelé DiLCO, pour Distributed Lifetime Coverage Optimization. Dans ce protocole, la durée de vie est divisée en périodes, avec chaque période qui est composée de 4 phases: échange d'informations entre les n\oe uds d'une sous-région, élection d'un n\oe ud leader, décision et surveillance. Le processus de décision est mis en oeuvre par le n\oe ud leader en résolvant un programme linéaire en nombres entiers qui permet de définir un seul ensemble de n\oe uds de capteurs devant être actifs pour assurer la couverture durant la période courante.
-Dans le second protocole, qui est une évolution de DiLCO, nous cherchons à construire simultanément plusieurs ensembles de n\oe uds de capteurs de couverture pour la phase de surveillance. Cette dernière est ainsi diviseé en "rondes" de surveillance, d'où le nom Multiround DiLCO ou MuDiLCO donné à ce protocole. Le processus de décision est toujours effectué par un n\oe ud leader, qui détermine les ensembles de n\oe uds capteurs à activer successivement via la résolution d'un nouveau programme linéaire en nombres entiers.
+Dans le second protocole, qui est une évolution de DiLCO, nous cherchons à construire simultanément plusieurs ensembles de n\oe uds de capteurs de couverture pour la phase de surveillance. Cette dernière est ainsi divisée en "rondes" de surveillance, d'où le nom Multiround DiLCO ou MuDiLCO donné à ce protocole. Le processus de décision est toujours effectué par un n\oe ud leader, qui détermine les ensembles de n\oe uds capteurs à activer successivement via la résolution d'un nouveau programme linéaire en nombres entiers.
%% The content of the PhD thesis
\begin{document}
-
% set the page numbers to be arabic, starting at page 1 %
\setcounter{page}{1}
\contentsline {section}{\numberline {5.5}Conclusion}{112}{section.5.5}
\contentsline {chapter}{\numberline {6} Perimeter-based Coverage Optimization to Improve Lifetime in WSNs}{113}{chapter.6}
\contentsline {section}{\numberline {6.1}Introduction}{113}{section.6.1}
-\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{113}{section.6.2}
+\contentsline {section}{\numberline {6.2}Description of the PeCO Protocol}{113}{section.6.2}
\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{113}{subsection.6.2.1}
\contentsline {subsection}{\numberline {6.2.2}PeCO Protocol Algorithm}{116}{subsection.6.2.2}
\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{118}{section.6.3}
\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{120}{subsection.6.4.2}
\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{120}{subsubsection.6.4.2.1}
\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{120}{subsubsection.6.4.2.2}
-\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{120}{subsubsection.6.4.2.3}
-\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{123}{subsubsection.6.4.2.4}
+\contentsline {subsubsection}{\numberline {6.4.2.3}Energy Consumption}{120}{subsubsection.6.4.2.3}
+\contentsline {subsubsection}{\numberline {6.4.2.4}Network Lifetime}{122}{subsubsection.6.4.2.4}
\contentsline {section}{\numberline {6.5}Conclusion}{126}{section.6.5}
\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{127}{part.3}
\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{129}{chapter.7}
