Last update by Ali

[ThesisAli.git] / INTRODUCTION.tex

diff --git a/INTRODUCTION.tex b/INTRODUCTION.tex
index 715cab3f318503b2ef2a7f25847d18360167e6cf..ea364e69c3300c24aeaeef57dc30d55ab64d5d19 100644 (file)
--- a/INTRODUCTION.tex
+++ b/INTRODUCTION.tex
@@ -6,11 +6,12 @@
 
 \section*{1. General Introduction}  
 \addcontentsline{toc}{section}{1. General Introduction }
 
 \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.
 
 
 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 are 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.
 
 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.


@@ -18,12 +19,12 @@ Specifically, the energy-efficient protocols proposed in this dissertation focus
 
 \section*{2. Motivation of the Dissertation}
 \addcontentsline{toc}{section}{2. Motivation of the Dissertation }
 
 \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
-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 to be 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.
+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}
 \addcontentsline{toc}{section}{3. The Objective of this Dissertation}
 The primary objective of this dissertation is to develop energy-efficient distributed optimization protocols in wireless sensor networks that optimize both coverage and network lifetime. The developed protocols should schedule node activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime.
 \section*{3. The Objective of this Dissertation}
 \addcontentsline{toc}{section}{3. The Objective of this Dissertation}
 The primary objective of this dissertation is to develop energy-efficient distributed optimization protocols in wireless sensor networks that optimize both coverage and network lifetime. The developed protocols should schedule node activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime.


@@ -32,29 +33,31 @@ The proposed protocols should be able to combine two efficient techniques: netwo
 election and sensor activity scheduling based optimization, where the challenges include how to select the most efficient leader and the best representative active nodes which take the mission of monitoring during the current period.
 
  In addition, the developed optimization protocols should be able to perform a distributed optimization process, by subdividing into subregions the region of interest where the sensor nodes in each subregion collaborate to select the leader which execute the optimization algorithm. 
 election and sensor activity scheduling based optimization, where the challenges include how to select the most efficient leader and the best representative active nodes which take the mission of monitoring during the current period.
 
  In addition, the developed optimization protocols should be able to perform a distributed optimization process, by subdividing into subregions the region of interest where the sensor nodes in each subregion collaborate to select the leader which execute the optimization algorithm. 

- 
+\fi

 
 

-\section*{4. Main Contributions of this Dissertation}
- \addcontentsline{toc}{section}{4. Main Contributions of this Dissertation}
+\section*{3. Main Contributions of this Dissertation}
+ \addcontentsline{toc}{section}{3. Main Contributions of this Dissertation}

 %The coverage problem in WSNs is becoming more and more important for many applications ranging from military applications such as battlefield surveillance to the civilian applications such as health-care surveillance and habitant monitoring. 
 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)]
 %The coverage problem in WSNs is becoming more and more important for many applications ranging from military applications such as battlefield surveillance to the civilian applications such as health-care surveillance and habitant monitoring. 
 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. 
 
 \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 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.  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. 
 
 %\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. 

-
-\item We have designed a third protocol, called Perimeter-based Coverage Optimization (PeCO).
+ 
+\item We design a third protocol, called Perimeter-based Coverage Optimization (PeCO).

 %which schedules nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. This protocol is applied in a distributed way in regular subregions obtained after partitioning the area of interest in a preliminary step. It works in periods and is based on the resolution of an integer program to select the subset of sensors operating in active status for each period.  
 %which schedules nodes’ activities (wake up and sleep stages) with the objective of maintaining a good coverage ratio while maximizing the network lifetime. This protocol is applied in a distributed way in regular subregions obtained after partitioning the area of interest in a preliminary step. It works in periods and is based on the resolution of an integer program to select the subset of sensors operating in active status for each period.  

-We have proposed a new mathematical optimization model. Instead of  trying to cover a set of specified points/targets as in my previous protocols and most of the methods proposed in the literature, we formulate an integer program based on perimeter coverage of each sensor. The model involves integer variables to capture the deviations between the actual level of coverage and the required  level. The idea is that an optimal scheduling  will be  obtained by  minimizing a weighted sum of these deviations. This contribution is demonstrated in chapter 6.
+We have proposed a new mathematical optimization model. Instead of  trying to cover a set of specified points/targets as in previous protocols and most of the methods proposed in the literature, we formulate  a mixed-integer program based on perimeter coverage of each sensor. The model involves   variables to capture the deviations between the actual level of coverage and the required  level. The idea is that an optimal scheduling  will be  obtained by  minimizing a weighted sum of these deviations. This contribution is demonstrated in chapter 6.

 
 

-\item We add an improved model of energy consumption to assess the efficiency of our protocols. We conducted extensive simulation experiments using the discrete event simulator OMNeT++, to demonstrate the  efficiency of our protocols. We compared our proposed distributed optimization protocols to two approaches found in the literature: DESK~\cite{DESK} and GAF~\cite{GAF}. Simulation results based on multiple criteria (energy consumption, coverage ratio, network lifetime and so on) show that the proposed protocols can prolong efficiently the network lifetime and improve the coverage performance.
+\item %We add an improved model of energy consumption to assess the efficiency of our protocols. 
+We conducted extensive simulation experiments using the discrete event simulator OMNeT++, to demonstrate the  efficiency of our protocols. We compared our proposed distributed optimization protocols with two approaches found in the literature: DESK~\cite{DESK} and GAF~\cite{GAF}. Simulation results based on multiple criteria (energy consumption, coverage ratio, network lifetime and so on) show that the proposed protocols can prolong efficiently the network lifetime and improve the coverage performance.

 
 
 \end{enumerate}
 
 
 \end{enumerate}


@@ -66,7 +69,7 @@ We have proposed a new mathematical optimization model. Instead of  trying to co
 
 % \section{ Refereed Journal and Conference Publications}
  
 
 % \section{ Refereed Journal and Conference Publications}
  

-\section*{5. Dissertation Outline}
-\addcontentsline{toc}{section}{5. Dissertation Outline}
+\section*{4. Dissertation Outline}
+\addcontentsline{toc}{section}{4. Dissertation Outline}

 The dissertation is organized as follows: the next chapter presents a scientific background about wireless sensor networks. Chapter 2 states a review of the related literatures to the coverage problem in WSNs, prior works and current works. Evaluation tools and optimization solvers are investigated in chapter 3. Chapter 4 describes the proposed DiLCO protocol, while chapter 5 and 6 respectively present the MuDiLCO and PeCO protocols. Finally, we conclude our work in chapter 7.
  
 The dissertation is organized as follows: the next chapter presents a scientific background about wireless sensor networks. Chapter 2 states a review of the related literatures to the coverage problem in WSNs, prior works and current works. Evaluation tools and optimization solvers are investigated in chapter 3. Chapter 4 describes the proposed DiLCO protocol, while chapter 5 and 6 respectively present the MuDiLCO and PeCO protocols. Finally, we conclude our work in chapter 7.