From: ali Date: Fri, 3 Apr 2015 13:17:01 +0000 (+0200) Subject: Update by Ali X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/commitdiff_plain/c8aeaf03fab9cb2dd9e45068f1cb29c3ed7984db Update by Ali --- diff --git a/CHAPITRE_01.tex b/CHAPITRE_01.tex index cc7cc74..7f4a43d 100644 --- a/CHAPITRE_01.tex +++ b/CHAPITRE_01.tex @@ -12,7 +12,7 @@ \section{Introduction} \label{ch1:sec:01} The wireless networking has received more attention and fast growth in the last decade. The growing demand for the use of wireless applications and emerging the wireless devices such as portable computers, cellular phones, and personal digital assistants (PDAs) have led to develop different infrastructures of wireless networks. The wireless networks can be classified into two classes based on the network architecture~\cite{ref154,ref155}: Infrastructure-based networks that consist of a fixed network structure such as cellular networks and wireless local-area networks -(WLANs); and Infrastructureless networks that constructed dynamically by the cooperation of the wireless nodes in the network, where each node capable of sending the packets and taking the decision based on the network status. Examples of such type of networks include mobile ad hoc networks and wireless sensor networks. Figure~\ref{WNT} shows the taxonomy of wireless networks. +(WLANs); and Infrastructureless networks that are constructed dynamically by the cooperation of the wireless nodes in the network, where each node is capable of sending the packets and taking the decision based on the network status. Examples of such type of networks include mobile ad hoc networks and wireless sensor networks. Figure~\ref{WNT} shows the taxonomy of wireless networks. \begin{figure}[h!] \centering @@ -22,14 +22,16 @@ The wireless networking has received more attention and fast growth in the last \label{WNT} \end{figure} -In recent years, there is increasing interest in Wireless Sensor Networks (WSNs) by many researchers around the world. WSNs are considered as one of the most researched fields in the last decade due to the extensive research in this discipline. It represents a special case of the Ad Hoc networks. Recent advances in wireless networking, Micro-Electro-Mechanical Systems (MEMS), and embedded computing technologies have led to construct low-cost, small-sized, and low-power sensor nodes. These sensor nodes can perform detection, computation, and data communication of surrounding environment. A WSN includes a large number of sensor nodes that can sense, process, and transmit data over a wireless communication. The sensor nodes communicate with each other by using multi-hop wireless communications and cooperate together to monitor the area of interest. The measured data is reported to a monitoring center called sink for further analysis~\cite{ref1,ref2}. The WSN receives the orders from the end user by means of the sink. These orders specify data aggregation, computation and delivery missions to wireless sensor nodes, after that the sensed measurements are received from the WSN by the sink~\cite{ref3}. The cooperation among the wireless sensor nodes in WSNs has been led to several advantages over the traditional wireless ad-hoc networks, like self-organization, rapid deployment, flexibility, and inherent intelligent-processing capability~\cite{ref5}. +In recent years, there is increasing interest in Wireless Sensor Networks (WSNs) by many researchers around the world. +%WSNs are considered as one of the most researched fields in the last decade due to the extensive research in this discipline. +It represents a special case of the Ad Hoc networks. Recent advances in wireless networking, Micro-Electro-Mechanical Systems (MEMS), and embedded computing technologies have led to construct low-cost, small-sized, and low-power sensor nodes. These sensor nodes can perform detection, computation, and data communication of surrounding environment. A WSN includes a large number of sensor nodes that can sense, process, and transmit data over a wireless communication. The sensor nodes communicate with each other by using multi-hop wireless communications and cooperate together to monitor the area of interest. The measured data is reported to a monitoring center called sink for further analysis~\cite{ref1,ref2}. The WSN receives the orders from the end user by means of the sink. These orders specify data aggregation, computation and delivery missions to wireless sensor nodes, after that the sensed measurements are received from the WSN by the sink~\cite{ref3}. The cooperation among the wireless sensor nodes in WSNs has been led to several advantages over the traditional wireless ad-hoc networks, like self-organization, rapid deployment, flexibility, and inherent intelligent-processing capability~\cite{ref5}. \section{Wireless Sensor Network Architecture} \label{ch1:sec:02} A typical WSN architecture consists of a set of a typical wireless sensor nodes, which are capable of sensing the surrounded physical phenomenon such as fire in the forest (see~figure~\ref{wsn}), and then send the sensed data to a controller node called a sink. One or more sink in WSN are responsible for collecting and processing the received sensed data, and then send that data through the Internet to the end-user. -In this WSN architecture, the basic element is a typical wireless sensor node that composed of four major units~\cite{ref17,ref18}: sensing, computation, communication, and power. In addition, there are three optional units, which can be combined with the sensor node such as localization system, mobilizer, and power generator. Figure~\ref{twsn} shows the components of a typical wireless sensor node~\cite{ref17}. +In this WSN architecture, the basic element is a typical wireless sensor node that is composed of four major units~\cite{ref17,ref18}: sensing, computation, communication, and power. In addition, there are three optional units, which can be combined with the sensor node such as localization system, mobilizer, and power generator. Figure~\ref{twsn} shows the components of a typical wireless sensor node~\cite{ref17}. \begin{figure}[h!] \centering @@ -41,9 +43,9 @@ In this WSN architecture, the basic element is a typical wireless sensor node th \begin{enumerate} [(I)] \item \textbf{Sensing Unit:} consists of two main parts: sensors and analog to digital converters (ADCs). It is responsible for sensing the physical phenomena. The analog signal produced by the sensors is converted into digital data by ADC. The resulted digital data is sent to the computation unit for further processing. -\item \textbf{Computation Unit:} The main purpose of this unit is to manage and manipulate the instructions that related to sensing, communication, and self-organization. This allows to the sensor node cooperates with other sensor nodes in order to perform the allocated sensing tasks. It is composed of a processor chip, an active short-term memory for storing the sensed data, an internal flash memory for storing program instructions, and an internal timer. +\item \textbf{Computation Unit:} The main purpose of this unit is to manage and manipulate the instructions that are related to sensing, communication, and self-organization. This allows the sensor node to cooperate with other sensor nodes in order to perform the allocated sensing tasks. It is composed of a processor chip, an active short-term memory for storing the sensed data, an internal flash memory for storing program instructions, and an internal timer. -\item \textbf{Communication Unit:} It is responsible for all data transmission and reception of the sensor node that are performed by the transceiver circuitry. A transceiver circuit is composed of a mixer, frequency synthesizer, voltage-controlled oscillator (VCO), phase-locked loop (PLL), demodulator, and power amplifiers, all of which consume valuable power~\cite{ref19}. +\item \textbf{Communication Unit:} It is responsible for all data transmission and reception of the sensor node that are performed by the transceiver circuitry. A transceiver circuit is composed of a mixer, frequency synthesizer, voltage-controlled oscillator (VCO), phase-locked loop (PLL), demodulator, and power amplifiers. They consume valuable power~\cite{ref19}. \item \textbf{Power Unit:} This unit represents the most significant part of wireless sensor node. It supplies the other units by the needed power. @@ -118,7 +120,7 @@ A network consists of a low-cost wireless sensor nodes, which are equipped with \item \textbf{Health-care Applications:} There is increasing interest and extensive research in the health-care applications. Two types of health-care systems are recognized~\cite{ref22}: vital status monitoring and remote health-care surveillance. In vital status monitoring applications, sick persons are wearing the sensors in order to oversee the state of their health and to allow medical staff to monitor and control the patient's status expeditiously. The most general used vital signs are ECG, pulse oximetry, body temperature, heart rate, and blood pressure~\cite{ref27}. These applications include mass-casualty disaster monitoring, vital sign monitoring in hospitals, and sudden fall or epilepsy seizure detection. On the other hand, remote health-care surveillance refers to the health services that do not require continuous existence of health care. These applications include elderly monitoring, providing support to a physically impaired person, gather clinically relevant information for rehabilitation supervision~\cite{ref28}, location tracking, and medication intake monitoring~\cite{ref27}. -\item \textbf{ Environment and agriculture Applications:} +\item \textbf{ Environment and agriculture Applications} \indent Several WSNs applications have been developed for the precision agriculture, cattle monitoring, and environmental monitoring. \indent Precision agriculture refers to the science of using the innovative and modern technology to improve the crop production. The WSNs are the main technology for developing of precision agriculture~\cite{ref29}. This technology contributes to increasing the agricultural yields, improving quality, and reducing costs whilst decreasing the damaging impact on the environment. The wireless sensors are distributed over the target field so as to monitor the main parameters such as soil moisture, atmospheric temperature, and creating a decision support system \cite{ref22}. The wireless sensors can be used in agricultural services like Irrigation, fertilization, pest control, animal and pastures monitoring, horticulture(e.g., greenhouse and viticulture)~\cite{ref30}. @@ -193,16 +195,16 @@ nodes in order to achieve their tasks efficiently. \label{emwsn} \end{figure} -\subsection{Energy-Efficient Routing:} +\subsection{Energy-Efficient Routing} \indent The energy-efficient routing is a significant factor in the design of WSN protocols in order to satisfy the main constraints in the hardware, power, and other resources of wireless sensor nodes~\cite{ref42}. Many challenging factors need to be taken into consideration in designing a routing protocol for WSN such as limited energy capacity, node deployment, sensor location, dynamic network, hardware resource constraints, data aggregation, latency, scalability, and fault tolerance. -\subsubsection{Routing Metric based on Residual Energy:} Lifetime maximization can be achieved by using the residual power of wireless sensor node as a routing metric that should be taken into account in executing the routing protocol in WSNs. The routing protocols should be concentrated on the remaining power of sensor nodes during taking the decision to select the next hop toward the destination. They should not only depend on the shortest path solution. They prioritize routes on the basis of an energy metric (sometimes with other routing metrics). Therefore, it is called energy-aware routing protocols.~\cite{ref45,ref46}. +\subsubsection{Routing Metric based on Residual Energy} Lifetime maximization can be achieved by using the residual power of wireless sensor node as a routing metric that should be taken into account in executing the routing protocol in WSNs. The routing protocols should be concentrated on the remaining power of sensor nodes during taking the decision to select the next hop toward the destination. They should not only depend on the shortest path solution. They prioritize routes on the basis of an energy metric (sometimes with other routing metrics). Therefore, it is called energy-aware routing protocols.~\cite{ref45,ref46}. -\subsubsection{Multipath Routing:} Represents an efficient strategy that provides reliability, security, and load balancing in order to forward packets in a limited energy and constrained resources (computation, communication, and storage) networks like WSNs~\cite{ref50}. The single path routing is simple and scalable, but it is not efficient for energy-constrained networks such as WSNs. Many multipath routing protocol summarized in~\cite{ref50,ref51}. +\subsubsection{Multipath Routing} Represents an efficient strategy that provides reliability, security, and load balancing in order to forward packets in a limited energy and constrained resources (computation, communication, and storage) networks like WSNs~\cite{ref50}. The single path routing is simple and scalable, but it is not efficient for energy-constrained networks such as WSNs. Many multipath routing protocol summarized in~\cite{ref50,ref51}. -\subsection{Cluster Architectures:} +\subsection{Cluster Architectures} \indent In this strategy, the wireless sensor nodes are grouped into several groups that called clusters, each group of wireless sensor nodes are managed by a single sensor node, which is called cluster head. The cluster head takes the responsibility for managing the activities of the wireless sensor nodes in the cluster and it communicates and coordinates with other cluster heads or with the base station in the WSN. This mechanism conserves the energy in WSNs by means of~\cite{ref43,ref22}: @@ -217,7 +219,7 @@ nodes in order to achieve their tasks efficiently. \indent In addition, the clustering supports network scalability in WSNs~\cite{ref43,ref44}. The clustering approach represents an efficient mechanism for scalability of WSN and providing energy-efficient data aggregation by minimizing the consumption of a limited energy by means of grouping the sensor nodes and organizing them hierarchically. Several important design considerations that should be taken into account during designing clustering algorithms such as limited energy, network lifetime, limited abilities, application dependency, secure communication, cluster formation, cluster head selection, synchronization, data aggregation, repair mechanisms, and Quality of Service (QoS)~\cite{ref161}. -\subsection{Scheduling Schemes:} +\subsection{Scheduling Schemes} \indent Many scheduling schemes have been suggested so as to decrease the energy depletion and improve the lifetime of WSNs~\cite{ref58,ref59}. These schemes deal with scheduling the states of wireless sensor nodes and putting the idle sensor nodes into sleep mode (i.e, turn off the radio unit) to save the energy. Figure~\ref{wsns} summarizes the scheduling schemes in WSNs. In this figure, the scheduling schemes are classified into two main branches~\cite{ref56,ref57}: \begin{itemize} @@ -234,7 +236,7 @@ nodes in order to achieve their tasks efficiently. \end{figure} -\subsubsection{Wake up Scheduling Schemes:} +\subsubsection{Wake up Scheduling Schemes} \indent This section demonstrates the scheduling schemes from the point of view of schedule composition process and the framework of the wake-up schedule. In these scheduling schemes, the wake-up interval refers to the period of time at which the radio unit is turned on so as to send or receive the packets. On the other hand, the sleep interval refers to a period of time at which the radio unit is turned off so as to retain the energy of wireless sensor node. Some schemes divide the time into equal length durations of time and are called slotted schemes. The other schemes work with the time in continuous way and are called unslotted schemes. The sleep and wake up intervals are defined for the unslotted schemes, whilst for the slotted schemes, these intervals are represented as multiple slots. The wake-up schedule represents a set of a wake-up and sleep intervals, which are produced for one period. This schedule replicates to each period and it can be changed by the wake-up scheduling scheme during the different periods of time. The final goal of this wake-up schedule is to permit to exchange the data among the wireless sensor nodes in WSN during the wake-up interval. As shown in figure~\ref{wsns}, the requirement for synchronization has been categorized the wake-up scheduling into three categories~\cite{ref57}: @@ -280,7 +282,7 @@ nodes in order to achieve their tasks efficiently. -\subsubsection{Topology Control Schemes:} +\subsubsection{Topology Control Schemes} \indent The topology control schemes deal with the redundancy in the WSNs. The WSN is always deploying with high density and in a random way, where a large number of wireless sensor nodes are usually throwing by the airplane over the area of interest. The purpose of deploying a dense WSN is to cope with the sensor failure during or after the WSN deployment and to maximize the network lifetime by means of exploiting the overlapping among the sensor nodes in the network by putting the redundant sensor nodes into sleep mode in order to benefit from it later. The major goal of topology control protocols is to dynamically adapt network topology based on requirements of application so as to minimize the number of active sensor nodes, achieve the tasks of the network, and prolong the network lifetime~\cite{ref56,ref22}. Many factors can be used to decide which sensor nodes should be turned on or off and when. The topology control schemes have been classified into two categories~\cite{ref56}: @@ -291,7 +293,7 @@ nodes in order to achieve their tasks efficiently. \end{enumerate} -\subsection{Data-Driven Schemes:} +\subsection{Data-Driven Schemes} \indent Data-driven approaches aim to decrease the amount of data sent to the sink whilst maintaining the accuracy of sensing within an acceptable level. Therefore, removing unwanted data during the transmission and restriction the sensing tasks during data acquisition can be participating in reducing the energy consumption in WSNs. %Several data-driven schemes have been proposed in~\cite{ref86,ref87,ref88,ref89,ref90}. @@ -303,26 +305,26 @@ Data driven schemes are classified into two main approaches~\cite{ref59,ref22}: \subsubsection{Energy Efficient Data Acquisition Schemes} are concentrated on the energy consumption reduction in the sensing unit. These schemes are divided into adaptive sampling, hierarchical sampling, and model-based active sampling. In adaptive sampling, the amount of data that acquired from the transducer can be reduced by spatial or temporal correlation between data. These approaches are more efficient to be used in centralized fusion, but it consumes more energy due to requiring a high processing. While, the hierarchical sampling are more efficient when there are different types of sensors are installed on the nodes. These approaches are more energy efficient and application specific. The model-based approaches are similar to data prediction schemes. These approaches aim to decrease the data samples by using computed models and conserve the energy by means of data acquisition. %\end{enumerate} -\subsection{Battery Repletion:} +\subsection{Battery Repletion} \indent In the last years, extensive researches have been focused on energy harvesting and wireless charging techniques. These solutions represent alternate energy sources to recharge wireless sensor batteries without human intervention~\cite{ref91,ref59}. -\subsubsection{Energy Harvesting:} In energy harvesting, several sources of environmental energy have been developed so as to enable the wireless sensors to acquire energy from the surrounding environment like solar, wind energy, vibration based energy harvesting, radio signals for scavenging RF power, Thermoelectric generators, and shoe-mounted piezoelectric generator to power artificial organs~\cite{ref59}. +\subsubsection{Energy Harvesting} In energy harvesting, several sources of environmental energy have been developed so as to enable the wireless sensors to acquire energy from the surrounding environment like solar, wind energy, vibration based energy harvesting, radio signals for scavenging RF power, Thermoelectric generators, and shoe-mounted piezoelectric generator to power artificial organs~\cite{ref59}. -\subsubsection{Wireless Charging:}In wireless charging, the wireless power can be transmitted between the devices without requiring to the connection between the transmitter and the receiver. These techniques are participating in increasing the availability of WSNs and prolonging the network lifetime. Wireless charging in WSNs can be performed by using two manners: magnetic resonant coupling and electromagnetic radiation~\cite{ref22}. +\subsubsection{Wireless Charging}In wireless charging, the wireless power can be transmitted between the devices without requiring to the connection between the transmitter and the receiver. These techniques are participating in increasing the availability of WSNs and prolonging the network lifetime. Wireless charging in WSNs can be performed by using two manners: magnetic resonant coupling and electromagnetic radiation~\cite{ref22}. -\subsection{Radio Optimization:} +\subsection{Radio Optimization} \indent In wireless sensor node, the radio is the most energy-consuming unit for draining the battery power. Extensive researches have been focused on decreasing the power depletion due to wireless communication by means of optimizing the radio parameters such as coding and modulation schemes; transmission power and antenna direction; and cognitive radio and Cooperative communications schemes~\cite{ref22}. -\subsection{Relay nodes and Sink Mobility:} +\subsection{Relay nodes and Sink Mobility} \indent The relay node placement and the mobility of the sink can be considered as energy-efficient strategies, which are used to minimize the consumption of the energy and extend the lifetime of WSNs. %\begin{enumerate} [(I)] -\subsubsection{Relay node placement:} +\subsubsection{Relay node placement} In WSN, some wireless sensor nodes in a certain region may die and this creates a hole in the WSN. This problem can be solved by placing the wireless sensor nodes in sensing field using optimal distribution or by deploying a small number of relay wireless sensor nodes with powerful capabilities. The major goal of relay nodes is the communication with other wireless sensor nodes or relay nodes~\cite{ref52}. This solution can enhance the power balancing and avoiding the overloaded wireless sensor nodes in a particular region in WSN. -\subsubsection{Sink Mobility:} +\subsubsection{Sink Mobility} In the WSNs include a static sink, the wireless sensor nodes, which are near the sink drain their power more rapidly compared with other sensor nodes, and this leads to WSN disconnection and limited network lifetime~\cite{ref53}. Sending all the data in WSN to the sink maximizes the overload on the sensor nodes near to sink. In order to overcome this problem and prolong the network lifetime, it is necessary to use a mobile sink to move within the area of WSN so as to collect the sensory data from the static sensor nodes over a single hop communication. The mobile sink avoids the multi-hop communication and conserves the energy at the static sensor nodes near to the base station, extending the lifetime of WSN~\cite{ref54,ref55}. @@ -411,7 +413,7 @@ The coverage protocols have proposed in this dissertation use the binary disc se -\section{Design Issues for Coverage Problems:} +\section{Design Issues for Coverage Problems} \label{ch1:sec:11} \indent Several design issues should be considered in order to produce solutions for the coverage problems in WSNs. These design issues can be classified into~\cite{ref103}: @@ -433,7 +435,7 @@ The coverage protocols have proposed in this dissertation use the binary disc se \end{enumerate} -\section{Energy Consumption Modeling:} +\section{Energy Consumption Modeling} \label{ch1:sec:9} \indent The WSNs have been received a lot of interests because the low energy consumption of the sensor nodes. One of the most critical issues in WSNs is to reduce the energy consumption of the limited power battery of the sensor nodes so as to prolong the network lifetime as long as possible. In order to model the energy consumption, four states for a sensor node are used~\cite{ref140}: transmission, reception, listening, and sleeping. In addition, two states should be taken into account: computation and sensed data acquisition. The main tasks of each of these states include: diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex index ee59f56..e977bf7 100644 --- a/CHAPITRE_02.tex +++ b/CHAPITRE_02.tex @@ -195,7 +195,7 @@ DESK is based on the result from \cite{ref133}. In \cite{ref133}, the whole area \begin{figure}[h!] \centering -\includegraphics[scale=0.4]{Figures/ch2/DESK.eps} +\includegraphics[scale=0.45]{Figures/ch2/DESK.eps} \caption{ DESK network time line.} \label{desk} \end{figure} @@ -219,7 +219,7 @@ DESK uses two types of messages, mACTIVATE message by which a sensor informs oth Typically, the algorithm works as follows. At the beginning of each round, no sensors are active. All sensors are in listening mode, i.e. all wait for the time to make a decision while still doing sensing job. All the sensor nodes collect the information (coordinates, current residual energy, and sensing range) from the one-hop neighbors. It stores this information into a list L in the increasing order of the angle $\alpha $ . Each sensor node set its timer to $w_i$ and initially it is proposed that all of its neighbors need it to join the network. When the sensor node $s_j$ joins the network, it broadcasts a mACTIVATE message to inform all of its 1-hop neighbors about its status change. Its neighbors execute the perimeter coverage model to recalculate its coverage level. If it finds any neighbor u that is useless in covering its perimeter, i.e., the perimeter that u covers was covered by other active neighbors, it will send mASK2SLEEP message to that sensor. When the sensor node receives mASK2SLEEP message, it updates its counter $n_i$, contribution $c_i$ to coverage level, and recalculate waiting time $w_i$. It then check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e., it receives mASK2SLEEP message from all of its neighbors), then it will send message mGOSLEEP to all of its neighbors telling them that it is about to go to sleep, and set a timer $R_i$ for waking up in next round and at last go to sleep. If the sensor node receives mGOSLEEP message, it removes the neighbor sending that message out of its list L. All the sensors have to decide its status in the decision phase. After that, the active sensors perform the sensing task during the sensing phase. - +The period the average \begin{table} diff --git a/INTRODUCTION.tex b/INTRODUCTION.tex index 891c222..847f097 100644 --- a/INTRODUCTION.tex +++ b/INTRODUCTION.tex @@ -6,14 +6,14 @@ \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 the physical dangerous environment such as volcanoes, nuclear reactors, forest fires, or military battles. 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. -WSN is an ad hoc wireless networks, which consists of a large number of wireless cheap devices called sensors. Sensor node able to 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 take these constraints into account on the sensors 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 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. -Since the network lifetime depends on sensor lifetime, the power depletion represents the most significant part during designing of the WSN protocols because of 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 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 focuses on the area coverage problem in WSNs. The major goal of the area coverage problem is to ensure monitoring the entire sensing field for a long time as possible. The area coverage problem is closely related to the performance of WSNs in many applications, such as monitoring the 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. \section*{2. Motivation of the Dissertation} @@ -21,37 +21,40 @@ Specifically, the energy-efficient protocols proposed in this dissertation focus 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. -Although many works on energy-efficient coverage problem are 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 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? \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. +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. The proposed protocols should be able to combine two efficient techniques: network leader -election and sensor activity scheduling based optimization, where the challenges include how to select the most efficient leader in each subregion and the best representative active nodes, which take the mission of monitoring during the current period. +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 on the subregions where the sensor nodes in each subregion collaborate to select the leader by which the optimization algorithm is executed. + 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. \section*{4. Main Contributions of this Dissertation} \addcontentsline{toc}{section}{4. 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 design a distributed optimization protocols so as to extend the lifetime of the WSNs. We summarize the main contributions of our research as follows: +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 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 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 that focuses on the area coverage problem with the objective of maximizing the network lifetime. Our proposition, the Distributed Lifetime Coverage Optimization (DILCO) protocol, maintains the coverage and improves the lifetime in WSNs. DILCO protocol presented in chapter 4 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 broadcast by a leader to every node of its subregion. +\item We design, 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 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 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. +\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. %\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 new 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. We have proposed a new mathematical optimization model. Instead of trying to cover a set of specified points/targets as in 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. So that an optimal scheduling will be obtained by minimizing a weighted sum of these deviations. This contribution is demonstrated in Chapter 6. +\item We have designed 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. +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. -\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 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. \end{enumerate} @@ -65,5 +68,5 @@ The main contributions in this dissertation concentrate on design a distributed \section*{5. Dissertation Outline} \addcontentsline{toc}{section}{5. 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 WSN, the prior works, and the current works. The evaluation tools and optimization solvers have been investigated in chapter 3. Chapter 4 describes the the proposed DiLCO protocol. Chapter 5 presents the MuDiLCO protocol. The PeCO protocol is illustrated in chapter 6. 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. diff --git a/Thesis.toc b/Thesis.toc index 46995c1..031cca9 100644 --- a/Thesis.toc +++ b/Thesis.toc @@ -17,27 +17,27 @@ \contentsline {section}{\numberline {1.4}Wireless Sensor Network Applications}{22}{section.1.4} \contentsline {section}{\numberline {1.5}The Main Challenges in Wireless Sensor Networks}{25}{section.1.5} \contentsline {section}{\numberline {1.6}Energy-Efficient Mechanisms in Wireless Sensor Networks}{27}{section.1.6} -\contentsline {subsection}{\numberline {1.6.1}Energy-Efficient Routing:}{27}{subsection.1.6.1} -\contentsline {subsubsection}{\numberline {1.6.1.1}Routing Metric based on Residual Energy:}{27}{subsubsection.1.6.1.1} -\contentsline {subsubsection}{\numberline {1.6.1.2}Multipath Routing:}{28}{subsubsection.1.6.1.2} -\contentsline {subsection}{\numberline {1.6.2}Cluster Architectures:}{28}{subsection.1.6.2} -\contentsline {subsection}{\numberline {1.6.3}Scheduling Schemes:}{28}{subsection.1.6.3} -\contentsline {subsubsection}{\numberline {1.6.3.1}Wake up Scheduling Schemes:}{29}{subsubsection.1.6.3.1} -\contentsline {subsubsection}{\numberline {1.6.3.2}Topology Control Schemes:}{31}{subsubsection.1.6.3.2} -\contentsline {subsection}{\numberline {1.6.4}Data-Driven Schemes:}{32}{subsection.1.6.4} +\contentsline {subsection}{\numberline {1.6.1}Energy-Efficient Routing}{27}{subsection.1.6.1} +\contentsline {subsubsection}{\numberline {1.6.1.1}Routing Metric based on Residual Energy}{27}{subsubsection.1.6.1.1} +\contentsline {subsubsection}{\numberline {1.6.1.2}Multipath Routing}{28}{subsubsection.1.6.1.2} +\contentsline {subsection}{\numberline {1.6.2}Cluster Architectures}{28}{subsection.1.6.2} +\contentsline {subsection}{\numberline {1.6.3}Scheduling Schemes}{28}{subsection.1.6.3} +\contentsline {subsubsection}{\numberline {1.6.3.1}Wake up Scheduling Schemes}{29}{subsubsection.1.6.3.1} +\contentsline {subsubsection}{\numberline {1.6.3.2}Topology Control Schemes}{31}{subsubsection.1.6.3.2} +\contentsline {subsection}{\numberline {1.6.4}Data-Driven Schemes}{32}{subsection.1.6.4} \contentsline {subsubsection}{\numberline {1.6.4.1}Data Reduction Schemes}{32}{subsubsection.1.6.4.1} \contentsline {subsubsection}{\numberline {1.6.4.2}Energy Efficient Data Acquisition Schemes}{32}{subsubsection.1.6.4.2} -\contentsline {subsection}{\numberline {1.6.5}Battery Repletion:}{33}{subsection.1.6.5} -\contentsline {subsubsection}{\numberline {1.6.5.1}Energy Harvesting:}{33}{subsubsection.1.6.5.1} -\contentsline {subsubsection}{\numberline {1.6.5.2}Wireless Charging:}{33}{subsubsection.1.6.5.2} -\contentsline {subsection}{\numberline {1.6.6}Radio Optimization:}{33}{subsection.1.6.6} -\contentsline {subsection}{\numberline {1.6.7}Relay nodes and Sink Mobility:}{33}{subsection.1.6.7} -\contentsline {subsubsection}{\numberline {1.6.7.1}Relay node placement:}{33}{subsubsection.1.6.7.1} -\contentsline {subsubsection}{\numberline {1.6.7.2}Sink Mobility:}{34}{subsubsection.1.6.7.2} +\contentsline {subsection}{\numberline {1.6.5}Battery Repletion}{33}{subsection.1.6.5} +\contentsline {subsubsection}{\numberline {1.6.5.1}Energy Harvesting}{33}{subsubsection.1.6.5.1} +\contentsline {subsubsection}{\numberline {1.6.5.2}Wireless Charging}{33}{subsubsection.1.6.5.2} +\contentsline {subsection}{\numberline {1.6.6}Radio Optimization}{33}{subsection.1.6.6} +\contentsline {subsection}{\numberline {1.6.7}Relay nodes and Sink Mobility}{33}{subsection.1.6.7} +\contentsline {subsubsection}{\numberline {1.6.7.1}Relay node placement}{33}{subsubsection.1.6.7.1} +\contentsline {subsubsection}{\numberline {1.6.7.2}Sink Mobility}{34}{subsubsection.1.6.7.2} \contentsline {section}{\numberline {1.7}Network Lifetime in Wireless Sensor Networks}{34}{section.1.7} \contentsline {section}{\numberline {1.8}Coverage in Wireless Sensor Networks }{35}{section.1.8} -\contentsline {section}{\numberline {1.9}Design Issues for Coverage Problems:}{36}{section.1.9} -\contentsline {section}{\numberline {1.10}Energy Consumption Modeling:}{37}{section.1.10} +\contentsline {section}{\numberline {1.9}Design Issues for Coverage Problems}{36}{section.1.9} +\contentsline {section}{\numberline {1.10}Energy Consumption Modeling}{37}{section.1.10} \contentsline {section}{\numberline {1.11}Conclusion}{39}{section.1.11} \contentsline {chapter}{\numberline {2}Related Works on Coverage Problems}{41}{chapter.2} \contentsline {section}{\numberline {2.1}Introduction}{41}{section.2.1}