From: ali Date: Wed, 11 Mar 2015 19:01:26 +0000 (+0100) Subject: Update by Ali X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/commitdiff_plain/433012874584d03b48d32d4cdba05eeb3b28dbe6 Update by Ali --- diff --git a/CHAPITRE_01.tex b/CHAPITRE_01.tex index cc36301..cc7cc74 100755 --- a/CHAPITRE_01.tex +++ b/CHAPITRE_01.tex @@ -285,7 +285,7 @@ nodes in order to achieve their tasks efficiently. \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}: \begin{enumerate} [(I)] -\item \textbf{Location Driven Protocols} in which determining which wireless sensor node to turn on or off based on its location that should be known; for example, Geographical Adaptive Fidelity (GAF) protocol~\cite{ref84}. These schemes are called network coverage that describing how the sensing field is monitored using minimum number of wireless sensor nodes in order to achieve application requirements and prolong the network lifetime~\cite{ref102}. +\item \textbf{Location Driven Protocols} in which determining which wireless sensor node to turn on or off based on its location that should be known; for example, Geographical Adaptive Fidelity (GAF) protocol~\cite{GAF}. These schemes are called network coverage that describing how the sensing field is monitored using minimum number of wireless sensor nodes in order to achieve application requirements and prolong the network lifetime~\cite{ref102}. \item \textbf{Connectivity Driven Protocols} in which the wireless sensor nodes are activated or deactivated so that the sensing coverage and connectivity of WSN are assured such as Span protocol~\cite{ref85}. \end{enumerate} @@ -342,17 +342,17 @@ In the WSNs include a static sink, the wireless sensor nodes, which are near the \item The time spent by WSN until the death of the first wireless sensor node ( or cluster head ) in the network due to its energy depletion~\cite{ref162,ref163}. \item The time spent by WSN and has at least a specific set $\beta$ of alive sensor nodes in WSN~\cite{ref164,ref165}. -\item The time spent by WSN until the death of all wireless sensor nodes in WSN because they have depleted their energy~\cite{ref166}. +\item The time spent by WSN until the death of all wireless sensor nodes in WSN because they have depleted their energy~\cite{ref124}. \item For k-coverage, is the time spent by WSN in covering the area of interest by at least $k$ sensor nodes~\cite{DESK}. \item For 100 $\%$ coverage is the time spent by WSN in covering each target or the whole area by at least one sensor node~\cite{ref167}. \item For $\alpha$-coverage: the total time by which at least $\alpha$ part of the sensing field is covered with at least one node~\cite{ref168}; or is the time spent by WSN until the coverage ratio becomes less than a predetermined threshold $\alpha$~\cite{ref169}. \item The working time spent by the system before either the coverage ratio or delivery ratio become less than a predetermined threshold~\cite{ref170}. -\item The number of the successful data gathering trips~\cite{ref173}. +\item The number of the successful data gathering trips~\cite{ref53}. \item The number of sent packets~\cite{ref174}. \item The percentage of wireless sensor nodes that have a route to the sink~\cite{ref170}. \item The prediction of the total period of time during which the probability of ensuring the connectivity and k-coverage concurrently is at least $\alpha$~\cite{ref175}. \item The time spent by WSN until losing the connectivity or the coverage~\cite{ref171}. -\item The time spent by WSN until acceptable event detection ratio is not acceptable in the network~\cite{ref166}. +\item The time spent by WSN until acceptable event detection ratio is not acceptable in the network~\cite{ref124}. \item The time during which the application requirement is satisfied~\cite{ref172}. \end{enumerate} @@ -365,10 +365,10 @@ The network lifetime has been defined in this dissertation as the time spent by \label{ch1:sec:8} %\indent Energy efficiency is a crucial issue in wireless sensor networks since sensory consumption, in order to maximize the network lifetime, represents the major difficulty when designing WSNs. As a consequence, -One of the scientific research challenges in WSNs, which has been addressed by a large amount of literature during the last few years, is the design of energy efficient approaches for coverage and connectivity~\cite{ref94,ref101}. Coverage reflects how well a sensor field is monitored. On the one hand, we want to monitor the area of interest in the most efficient way~\cite{ref95}. On the other hand, we want to use as less energy as possible. Sensor nodes are battery-powered with no mean of recharging or replacing, usually due to environmental (hostile or unpractical environments) or cost reasons. Therefore, it is desired that the 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 most discussed coverage problems in literature can be classified into three types~\cite{ref96}: +One of the scientific research challenges in WSNs, which has been addressed by a large amount of literature during the last few years, is the design of energy efficient approaches for coverage and connectivity~\cite{ref94,ref101}. Coverage reflects how well a sensor field is monitored. On the one hand, we want to monitor the area of interest in the most efficient way~\cite{ref95}. On the other hand, we want to use as less energy as possible. Sensor nodes are battery-powered with no mean of recharging or replacing, usually due to environmental (hostile or unpractical environments) or cost reasons. Therefore, it is desired that the 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 most discussed coverage problems in literature can be classified into three types~\cite{ref102}: \begin{enumerate}[(i)] -\item \textbf{Area coverage}~\cite{ref97,ref153} where every point inside an area is to be monitored. The work in this dissertation deals with this type of coverage. -\item \textbf{Target coverage}~\cite{ref98,ref153} where the main objective is to cover only a finite number of discrete points called targets. +\item \textbf{Area coverage}~\cite{ref97,ref101} where every point inside an area is to be monitored. The work in this dissertation deals with this type of coverage. +\item \textbf{Target coverage}~\cite{ref98,ref101} where the main objective is to cover only a finite number of discrete points called targets. \item \textbf{Barrier coverage}~\cite{ref99,ref100} to prevent intruders from entering into the region of interest. \end{enumerate} diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex index 7aaafbe..bcf9002 100755 --- a/CHAPITRE_02.tex +++ b/CHAPITRE_02.tex @@ -38,7 +38,7 @@ in WSNs. Cardei and Wu~\cite{ref113} provide a taxonomy for coverage algorithms The choice of non-disjoint or disjoint cover sets (sensors participate or not in many cover sets), coverage type ( area, target, or barrier), coverage ratio, coverage degree (how many sensors are required to cover a target or an area) can be added to the above list. -Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. Many centralized algorithms and distributed algorithms for activity scheduling have been proposed in the literature, and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near optimal) solution based only on local information. Several algorithms to retain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref153,ref103,ref105}. Table~\ref{Table1:ch2} summarized the main characteristics of some coverage approaches in previous literatures. +Once a sensor nodes are deployed, a coverage algorithm is run to schedule the sensor nodes into cover sets so as to maintain sufficient coverage in the area of interest and extend the network lifetime. The WSN applications require (complete or partial) area coverage and complete target coverage. Many centralized algorithms and distributed algorithms for activity scheduling have been proposed in the literature, and based on different assumptions and objectives. In centralized algorithms, a central controller makes all decisions and distributes the results to sensor nodes. A distributed algorithms, on the other hand, the decision process is localized in each individual sensor node, and only information from neighboring nodes are used for the activity decision. Compared to centralized algorithms, distributed algorithms reduce the energy consumption required for radio communication and detection accuracy whilst increase the energy consumption for computation. Overall, distributed algorithms are more suitable for large-scale networks, but it can not give optimal (or near optimal) solution based only on local information. Several algorithms to retain the coverage and maximize the network lifetime were proposed in~\cite{ref113,ref101,ref103,ref105}. Table~\ref{Table1:ch2} summarized the main characteristics of some coverage approaches in previous literatures. \subsection{Centralized Algorithms} @@ -86,7 +86,7 @@ Various centralized methods based on column generation approaches have also be \label{ch2:sec:04} In distributed and localized coverage algorithms, the required computation to schedule the activity of sensor nodes will be done by the cooperation among neighboring nodes. These algorithms may require more computation power for the processing by the cooperating sensor nodes, but they are more scalable for large WSNs. Localized and distributed algorithms generally result in non-disjoint set covers. -Many distributed algorithms have been developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref129}. +Many distributed algorithms have been developed to perform the scheduling so as to preserve coverage, see for example \cite{ref123,ref124,ref125,ref126,ref109,ref127,ref128,ref97}. Distributed algorithms typically operate in rounds for a predetermined duration. At the beginning of each round, a sensor exchanges information with its neighbors and makes a decision to either remain turned on or to go to sleep for the round. This decision is basically made on simple greedy criteria like the largest uncovered area \cite{ref130} or maximum uncovered targets \cite{ref131}. The Distributed Adaptive Sleep Scheduling Algorithm (DASSA) \cite{ref127} does not require location information of sensors while maintaining connectivity and satisfying a user defined coverage target. In DASSA, nodes use the residual energy levels and feedback from the sink for scheduling the activity of their neighbors. This feedback mechanism reduces the randomness in scheduling that would otherwise occur due to the absence of location information. @@ -111,7 +111,7 @@ In \cite{ref133} authors prove that if the perimeters of sensors are suffici each sensor, where $d$ denotes the maximum number of sensors that are neighboring to a sensor and $n$ is the total number of sensors in the network. -In \cite{ref84}, Xu et al. have described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses geographic location information to divide the area of interest into fixed square grids. Within each grid, it keeps only one node staying awake to take the responsibility of sensing and communication. Figure~\ref{gaf1} gives an example of fixed square grid in GAF. +In \cite{GAF}, Xu et al. have described an algorithm, called Geographical Adaptive Fidelity (GAF), which uses geographic location information to divide the area of interest into fixed square grids. Within each grid, it keeps only one node staying awake to take the responsibility of sensing and communication. Figure~\ref{gaf1} gives an example of fixed square grid in GAF. \begin{figure}[h!] \centering @@ -142,7 +142,7 @@ The sensor nodes in GAF can be in one of three states: active, sleep, or discove The sensor node sets a timer to $T_d$ seconds after entering in discovery state. As soon as the timer fires, the sensor node broadcast its discovery message and enters in active state. The active sensor node sets a timeout value $T_a$ to define how long it can stay in active state. After $T_a$, the sensor node will return to the discovery state. Whilst, during its active state, it re-broadcasts its discovery message at intervals $T_d$ periodically. The sensor node with discovery or active state can change its state to sleep when it detects that some other equivalent node will handle routing inside the grid. The sensor nodes in the sleeping state wake up after a sleeping time $T_s$ and go back to the discovery state. In GAF, load balancing is performed by means of periodic election of the leader (i.e., the active node that handle the routing inside the fixed grid). A rank-based election algorithm has been used to elect the leader. It is based on the remaining energy of sensor nodes inside the fixed square grid so as to extend the network lifetime In proportionally with network density. -In~\cite{ref132}, the author have designed a novel distributed heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), which ensures that the energy consumption among the sensors is balanced and the lifetime maximized while the coverage requirement is maintained. This heuristic works in rounds, requires only one-hop neighbor information, and each sensor decides its status (active or sleep) based on the perimeter coverage model from~\cite{ref133}. Figure~\ref{desk} shows the DESK network time line. +In~\cite{DESK}, the author have designed a novel distributed heuristic, called Distributed Energy-efficient Scheduling for k-coverage (DESK), which ensures that the energy consumption among the sensors is balanced and the lifetime maximized while the coverage requirement is maintained. This heuristic works in rounds, requires only one-hop neighbor information, and each sensor decides its status (active or sleep) based on the perimeter coverage model from~\cite{ref133}. Figure~\ref{desk} shows the DESK network time line. \begin{figure}[h!] \centering @@ -234,7 +234,7 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e & \tiny S. K. Prasad and A. Dhawan (2007)~\cite{ref128} & \OK & & & \OK & & & \OK & & \OK & & \OK & &\\ -& \tiny S. Misra et al. (2011)~\cite{ref129} & \OK & & \OK & & & & \OK & & \OK & & & &\\ +& \tiny S. Misra et al. (2011)~\cite{ref97} & \OK & & \OK & & & & \OK & & \OK & & & &\\ & \tiny P. Berman et al. (2005)~\cite{ref130} & \OK & \OK & \OK & & & & \OK & & \OK & \OK & &\\ @@ -258,9 +258,9 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e & \tiny S. He et al. (2012)~\cite{ref137} & \OK & \OK & \OK & & & & \OK & & \OK & & & &\\ -& \tiny Y. Xu et al. (2001)~\cite{ref84} & \OK & & \OK & & & & \OK & & \OK & & & &\\ +& \tiny Y. Xu et al. (2001)~\cite{GAF} & \OK & & \OK & & & & \OK & & \OK & & & &\\ -& \tiny C. Vu et al. (2006)~\cite{ref132} & \OK & & \OK & & \OK & & \OK & & \OK & & \OK & &\\ +& \tiny C. Vu et al. (2006)~\cite{DESK} & \OK & & \OK & & \OK & & \OK & & \OK & & \OK & &\\ & \tiny X. Deng et al. (2012)~\cite{ref160} & \OK & & \OK & & & & \OK & & \OK & & & &\\ diff --git a/CHAPITRE_03.tex b/CHAPITRE_03.tex index 5ae861a..1c197aa 100755 --- a/CHAPITRE_03.tex +++ b/CHAPITRE_03.tex @@ -18,7 +18,7 @@ On the other side, the main challenges in the design of WSNs have given rise to Several proposed works in WSNs require evaluating the power depletion efficiently and accurately for network lifetime prediction. On the other hand, the wrong energy evaluation leads to waste of energy because the sensor nodes might be rendered useless long time before draining their energy. Furthermore, the sensor nodes might die in advance of the expected lifetime. However, evaluation experiments on actually deployed WSN suffer some constraints because the large number of sensor nodes, which are deployed in a hostile and inaccessible environments. Moreover, the analytical (or theoretical) models might be unrealistic for real world systems. Therefore, the energy consumption results by simulation and testbed evaluations give an alternative on time, precision and cost. In addition, the researchers can also evaluate and test their proposed works with simulation tools as well as testbed devices. -Two main evaluation tools for evaluating and validating large-scale wireless sensor networks performance: testbeds and simulations~\cite{ref176}. +Two main evaluation tools for evaluating and validating large-scale wireless sensor networks performance: testbeds and simulations~\cite{ref180}. \subsection{Testbed Tools} %~\cite{ref180} @@ -70,17 +70,17 @@ The ns-3 is considered a new simulator and a final replacement of ns-2, not an e \item \textbf{OMNeT++:} -OMNeT++ (Objective Modular Network Testbed) is an open-source, free, discrete-event, component-based C++ simulation library, modular simulation framework for building network simulators~\cite{ref196,ref203}. In spite of OMNeT++ is not a network simulator itself, it is obtained a global popularity as a network simulation platform for both scientific and industrial communities. The major goal behind the development of OMNeT++ is to provide a strong simulation tool, which can be used by the academic and commercial researchers for simulating different types of networks in a distributed and parallel way~\cite{ref197}. OMNeT++ has extensive graphical user interface (GUI) and intelligence support. It runs on Windows, Linux, Mac OS X, and other Unix-like systems. It provides a component architecture for models. Components (modules) are programmed in C++, then assembled into larger components and models using a high-level language (NED)~\cite{ref198}. Several simulation frameworks can be used with OMNeT++ such as INET, INETMANET, MiXiM, and Castalia, where each of them provides a set of simulation facilities and can be used for a specific applications. +The OMNeT++ (Objective Modular Network Testbed) is an open-source, free, discrete-event, component-based C++ simulation library, modular simulation framework for building network simulators~\cite{ref158,ref203}. In spite of OMNeT++ is not a network simulator itself, it is obtained a global popularity as a network simulation platform for both scientific and industrial communities. The major goal behind the development of OMNeT++ is to provide a strong simulation tool, which can be used by the academic and commercial researchers for simulating different types of networks in a distributed and parallel way~\cite{ref197}. OMNeT++ has extensive graphical user interface (GUI) and intelligence support. It runs on Windows, Linux, Mac OS X, and other Unix-like systems. It provides a component architecture for models. Components (modules) are programmed in C++, then assembled into larger components and models using a high-level language (NED)~\cite{ref198}. Several simulation frameworks can be used with OMNeT++ such as INET, INETMANET, MiXiM, and Castalia, where each of them provides a set of simulation facilities and can be used for a specific applications. \item \textbf{OPNET:} -OPNET (Optimized Network Engineering tool)~\cite{ref199,ref200,ref201} is the first commercial simulation tool that developed in 1987 for communication networks. It is a discrete event, object-oriented, general purpose network simulator, which is widely used in industry. It uses C and Java languages. It provides a comprehensive development environment for the specification, simulation, configuration, and performance analysis of the communication network. The OPNET permits researchers in developing the various models by means of a graphical interface. It provides different types of tools such as Probe Editor, Filter Tool, and Animation Viewer for data collection to the model graph and animate the resulting output. Unlike ns-2, the OPNET provides modeling for different sensor-specific hardware, such as physical-link transceivers and antennas. It includes sensor-specific models such as ad-hoc connectivity, mobility of nodes, node failure models, modeling of power-consumption, etc. The OPNET is commercial simulator and the license is very expensive. Therefore, this represents the main disadvantage of that simulator. +The OPNET (Optimized Network Engineering tool)~\cite{ref192,ref200,ref201} is the first commercial simulation tool that developed in 1987 for communication networks. It is a discrete event, object-oriented, general purpose network simulator, which is widely used in industry. It uses C and Java languages. It provides a comprehensive development environment for the specification, simulation, configuration, and performance analysis of the communication network. The OPNET permits researchers in developing the various models by means of a graphical interface. It provides different types of tools such as Probe Editor, Filter Tool, and Animation Viewer for data collection to the model graph and animate the resulting output. Unlike ns-2, the OPNET provides modeling for different sensor-specific hardware, such as physical-link transceivers and antennas. It includes sensor-specific models such as ad-hoc connectivity, mobility of nodes, node failure models, modeling of power-consumption, etc. The OPNET is commercial simulator and the license is very expensive. Therefore, this represents the main disadvantage of that simulator. \item \textbf{GloMoSim:} -GloMoSim(Global Mobile System Simulator)~\cite{ref202,ref204,ref205} is an open source, well-documented source code and scalable simulation environment developed in 1998 for mobile wireless networks. It uses a Parsec, which is an extension of C for parallel programming. The main feature of GloMoSim simulator is using parallel environment. The parallel network simulation is hard due to the communication among the simulated nodes on different machines. Several types of protocols and models are found in GloMoSim including TCP, +The GloMoSim(Global Mobile System Simulator)~\cite{ref202,ref204,ref205} is an open source, well-documented source code and scalable simulation environment developed in 1998 for mobile wireless networks. It uses a Parsec, which is an extension of C for parallel programming. The main feature of GloMoSim simulator is using parallel environment. The parallel network simulation is hard due to the communication among the simulated nodes on different machines. Several types of protocols and models are found in GloMoSim including TCP, IEEE 802.11 CSMA/CA, MAC, UDP, HTTP, FTP, CBR, ODMRP, WRP, DSR, MACA, Telnet, AODV, etc. It uses a VT visualization tool to observe and debug these protocols. The GloMoSim is designed to be extensible with all protocols implemented as modules in its library. It also uses an object-oriented approach. It is dividing the nodes, and each object is responsible for executing one layer in the protocol stack of every node for its given division. This mechanism minimizes the overhead of a large-scale sensor network. The GloMoSim supports a wide range of protocols and its configuration is easy. Due to the parallel processing nature, it supplies a fast simulation. The GloMoSim provides efficient simulation for IP networks whilst it does not support accurate simulation for many sensor network applications. Since 2000, the GloMoSim has been stopping releasing updates. It is currently updated as a commercial product called QualNet. diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex index ac6a480..603c6dd 100755 --- a/CHAPITRE_04.tex +++ b/CHAPITRE_04.tex @@ -30,21 +30,15 @@ prolong the network lifetime and improve the coverage performance effectively. \section{Description of the DiLCO Protocol} \label{ch4:sec:02} -\noindent In this section, we introduce the DiLCO protocol which is distributed on each subregion in the area of interest. It is based on two efficient -techniques: network leader election and sensor activity scheduling for coverage preservation and energy conservation, applied periodically to efficiently -maximize the lifetime in the network. +\noindent In this section, we introduce the DiLCO protocol which is distributed on each subregion in the area of interest. It is based on two efficient +techniques: network leader election and sensor activity scheduling for coverage preservation and energy conservation, applied periodically to efficiently maximize the lifetime in the network. \subsection{Assumptions and Network Model} \label{ch4:sec:02:01} -\noindent We consider a sensor network composed of static nodes distributed independently and uniformly at random. A high density deployment ensures a high -coverage ratio of the interested area at the start. The nodes are supposed to have homogeneous characteristics from a communication and a processing point of -view, whereas they have heterogeneous energy provisions. Each node has access to its location thanks, either to a hardware component (like a GPS unit), or a -location discovery algorithm. Furthermore, we assume that sensor nodes are time synchronized in order to properly coordinate their operations to achieve complex sensing tasks~\cite{ref157}. The two sensor nodes have been supposed a neighbors if the euclidean distance between them is at most equal to 2$R_s$. +\noindent We consider a sensor network composed of static nodes distributed independently and uniformly at random. A high-density deployment ensures a high coverage ratio of the interested area at the start. The nodes are supposed to have homogeneous characteristics from a communication and a processing point of view, whereas they have heterogeneous energy provisions. Each node has access to its location thanks, either to a hardware component (like a GPS unit) or a location discovery algorithm. Furthermore, we assume that sensor nodes are time synchronized in order to properly coordinate their operations to achieve complex sensing tasks~\cite{ref157}. The two sensor nodes have been supposed neighbors if the euclidean distance between them is at most equal to 2$R_s$. -\indent We consider a boolean disk coverage model which is the most widely used sensor coverage model in the literature. Thus, since a sensor has a constant -sensing range $R_s$, every space points within a disk centered at a sensor with the radius of the sensing range is said to be covered by this sensor. We also -assume that the communication range $R_c$ is at least twice the sensing range $R_s$ (i.e., $R_c \geq 2R_s$). In fact, Zhang and Hou~\cite{ref126} proved that if the transmission range fulfills the previous hypothesis, a complete coverage of a convex area implies connectivity among the working nodes in the active mode. We assume that each sensor node can directly transmit its measurements to a mobile sink node. For example, a sink can be an unmanned aerial vehicle (UAV) is flying regularly over the sensor field to collect measurements from sensor nodes. A mobile sink node collects the measurements and transmits them to the base station. +\indent We consider a boolean disk coverage model which is the most widely used sensor coverage model in the literature. Thus, since a sensor has a constant sensing range $R_s$, every space points within a disk centered at a sensor with the radius of the sensing range is said to be covered with this sensor. We also assume that the communication range $R_c$ is at least twice the sensing range $R_s$ (i.e., $R_c \geq 2R_s$). In fact, Zhang and Hou~\cite{ref126} proved that if the transmission range fulfills the previous hypothesis, a complete coverage of a convex area implies connectivity among the working nodes in the active mode. We assume that each sensor node can directly transmit its measurements toward a mobile sink node. For example, a sink can be an unmanned aerial vehicle (UAV) is flying regularly over the sensor field to collect measurements from sensor nodes. A mobile sink node collects the measurements and transmits them to the base station. During the execution of the DiLCO protocol, two kinds of packet will be used: @@ -65,19 +59,12 @@ There are five possible status for each sensor node in the network: \subsection{Primary Point Coverage Model} \label{ch4:sec:02:02} -\indent Instead of working with the coverage area, we consider for each -sensor a set of points called primary points. We also assume that the -sensing disk defined by a sensor is covered if all the primary points of -this sensor are covered. By knowing the position (point center: ($p_x,p_y$)) of a wireless -sensor node and its $R_s$, we calculate the primary points directly -based on the proposed model. We use these primary points (that can be -increased or decreased if necessary) as references to ensure that the -monitored region of interest is covered by the selected set of -sensors, instead of using all the points in the area. +\indent Instead of working with the coverage area, we consider for each sensor a set of points called primary points. We also assume that the sensing disk defined by a sensor is covered if all the primary points of this sensor are covered. By knowing the position (point center: ($p_x,p_y$)) of a wireless sensor node and it's $R_s$, we calculate the primary points directly based on the proposed model. We use these primary points (that can be increased or decreased if necessary) as references to ensure that the monitored region of interest is covered by the selected set of sensors, instead of using all the points in the area. \indent We can calculate the positions of the selected primary points in the circle disk of the sensing range of a wireless sensor node (see figure~\ref{fig1}) as follows:\\ + $(p_x,p_y)$ = point center of wireless sensor node\\ $X_1=(p_x,p_y)$ \\ $X_2=( p_x + R_s * (1), p_y + R_s * (0) )$\\ @@ -125,13 +112,13 @@ $X_{25}=( p_x + R_s * (\frac{1}{2}), p_y + R_s * (\frac{-\sqrt{3}}{2})) $. \subsection{Main Idea} \label{ch4:sec:02:03} -\noindent We start by applying a divide-and-conquer algorithm to partition the +\noindent We start by applying a divide-and-conquer algorithm to partition the area of interest into smaller areas called subregions and then our protocol is executed simultaneously in each subregion. \begin{figure}[ht!] \centering -\includegraphics[scale=0.60]{Figures/ch4/FirstModel.pdf} % 70mm +\includegraphics[scale=0.80]{Figures/ch4/FirstModel.pdf} % 70mm \caption{DiLCO protocol} \label{FirstModel} \end{figure} @@ -388,7 +375,7 @@ The modeling language for Mathematical Programming (AMPL)~\cite{AMPL} is emplo \subsection{Energy Consumption Model} \label{ch4:sec:04:03} -\indent In this dissertation, we used an energy consumption model proposed by~\cite{ref111} and based on \cite{ref112} with slight modifications. The energy consumption for sending/receiving the packets is added, whereas the part related to the sensing range is removed because we consider a fixed sensing range. +\indent In this dissertation, we used an energy consumption model proposed by~\cite{DESK} and based on \cite{ref112} with slight modifications. The energy consumption for sending/receiving the packets is added, whereas the part related to the sensing range is removed because we consider a fixed sensing range. \indent For our energy consumption model, we refer to the sensor node Medusa~II which uses an Atmels AVR ATmega103L microcontroller~\cite{ref112}. The typical architecture of a sensor is composed of four subsystems: the MCU subsystem which is capable of computation, communication subsystem (radio) which is responsible for transmitting/receiving messages, the sensing subsystem that collects data, and the power supply which powers the complete sensor node \cite{ref112}. Each of the first three subsystems can be turned on or off depending on the current status of the sensor. Energy consumption (expressed in milliWatt per second) for the different status of the sensor is summarized in Table~\ref{table1}. @@ -512,7 +499,7 @@ In this experiment, Figure~\ref{Figures/ch4/R1/CR} shows the average coverage ra \parskip 0pt \begin{figure}[h!] \centering - \includegraphics[scale=0.6] {Figures/ch4/R1/CR.pdf} + \includegraphics[scale=0.8] {Figures/ch4/R1/CR.pdf} \caption{Coverage ratio for 150 deployed nodes} \label{Figures/ch4/R1/CR} \end{figure} @@ -525,7 +512,7 @@ As shown in the figure ~\ref{Figures/ch4/R1/CR}, as the number of subregions inc Figure~\ref{Figures/ch4/R1/ASR} shows the average active nodes ratio for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R1/ASR.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R1/ASR.pdf} \caption{Active sensors ratio for 150 deployed nodes } \label{Figures/ch4/R1/ASR} \end{figure} @@ -536,7 +523,7 @@ The results presented in figure~\ref{Figures/ch4/R1/ASR} show the increase in th Figure~\ref{Figures/ch4/R1/SR} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R1/SR.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R1/SR.pdf} \caption{Percentage of stopped simulation runs for 150 deployed nodes } \label{Figures/ch4/R1/SR} \end{figure} @@ -550,7 +537,7 @@ We measure the energy consumed by the sensors during the communication, listenin \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R1/EC95.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R1/EC95.pdf} \caption{Energy Consumption for Lifetime95} \label{Figures/ch4/R1/EC95} \end{figure} @@ -560,7 +547,7 @@ The results show that DiLCO-16 and DiLCO-32 are the most competitive from the en As shown in Figures~\ref{Figures/ch4/R1/EC95} and ~\ref{Figures/ch4/R1/EC50}, DiLCO-2 consumes more energy than the other versions of DiLCO, especially for large sizes of network. This is easy to understand since the bigger the number of sensors involved in the integer program, the larger the time computation to solve the optimization problem as well as the higher energy consumed during the communication. \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R1/EC50.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R1/EC50.pdf} \caption{Energy Consumption for Lifetime50} \label{Figures/ch4/R1/EC50} \end{figure} @@ -573,7 +560,7 @@ In this experiment, the execution time of the our distributed optimization appro \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R1/T.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R1/T.pdf} \caption{Execution Time (in seconds)} \label{Figures/ch4/R1/T} \end{figure} @@ -588,7 +575,7 @@ In figure~\ref{Figures/ch4/R1/LT95} and \ref{Figures/ch4/R1/LT50}, network lifet \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R1/LT95.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R1/LT95.pdf} \caption{Network Lifetime for $Lifetime95$} \label{Figures/ch4/R1/LT95} \end{figure} @@ -600,7 +587,7 @@ letting the other ones sleep in order to be used later in next rounds, DiLCO-16 Comparison shows that DiLCO-16 protocol, which uses 16 leaders, is the best one because it is used less number of active nodes during the network lifetime compared with DiLCO-32 protocol. It also means that distributing the protocol in each node and subdividing the sensing field into many subregions, which are managed independently and simultaneously, is the most relevant way to maximize the lifetime of a network. \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R1/LT50.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R1/LT50.pdf} \caption{Network Lifetime for $Lifetime50$} \label{Figures/ch4/R1/LT50} \end{figure} @@ -623,7 +610,7 @@ In this experiment, we Figure~\ref{Figures/ch4/R2/CR} shows the average coverage \parskip 0pt \begin{figure}[h!] \centering - \includegraphics[scale=0.6] {Figures/ch4/R2/CR.pdf} + \includegraphics[scale=0.8] {Figures/ch4/R2/CR.pdf} \caption{Coverage ratio for 150 deployed nodes} \label{Figures/ch4/R2/CR} \end{figure} @@ -635,7 +622,7 @@ thanks to Model~2, which is slightly more efficient than other Models, because Figure~\ref{Figures/ch4/R2/ASR} shows the average active nodes ratio for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R2/ASR.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R2/ASR.pdf} \caption{Active sensors ratio for 150 deployed nodes } \label{Figures/ch4/R2/ASR} \end{figure} @@ -650,7 +637,7 @@ In this study, we want to show the effect of increasing the primary points on th \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R2/SR.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R2/SR.pdf} \caption{Percentage of stopped simulation runs for 150 deployed nodes } \label{Figures/ch4/R2/SR} \end{figure} @@ -663,14 +650,14 @@ As shown in Figure~\ref{Figures/ch4/R2/SR}, when the number of primary points ar In this experiment, we study the effect of increasing the primary points to represent the area of the sensor on the energy consumed by the wireless sensor network for different network densities. Figures~\ref{Figures/ch4/R2/EC95} and ~\ref{Figures/ch4/R2/EC50} illustrate the energy consumption for different network sizes for $Lifetime95$ and $Lifetime50$. \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R2/EC95.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R2/EC95.pdf} \caption{Energy Consumption with $95\%-Lifetime$} \label{Figures/ch4/R2/EC95} \end{figure} \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R2/EC50.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R2/EC50.pdf} \caption{Energy Consumption with $Lifetime50$} \label{Figures/ch4/R2/EC50} \end{figure} @@ -683,7 +670,7 @@ In this experiment, we have studied the impact of the increase in primary points \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R2/T.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R2/T.pdf} \caption{Execution Time(s) vs The Number of Sensors } \label{Figures/ch4/R2/T} \end{figure} @@ -697,7 +684,7 @@ Finally, we will study the effect of increasing the primary points on the lifeti \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R2/LT95.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R2/LT95.pdf} \caption{Network Lifetime for $Lifetime95$} \label{Figures/ch4/R2/LT95} \end{figure} @@ -705,7 +692,7 @@ Finally, we will study the effect of increasing the primary points on the lifeti \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R2/LT50.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R2/LT50.pdf} \caption{Network Lifetime for $Lifetime50$} \label{Figures/ch4/R2/LT50} \end{figure} @@ -729,7 +716,7 @@ In this experiment, the average coverage ratio for 150 deployed nodes has been d \parskip 0pt \begin{figure}[h!] \centering - \includegraphics[scale=0.6] {Figures/ch4/R3/CR.pdf} + \includegraphics[scale=0.8] {Figures/ch4/R3/CR.pdf} \caption{Coverage ratio for 150 deployed nodes} \label{Figures/ch4/R3/CR} \end{figure} @@ -744,7 +731,7 @@ It is important to have as few active nodes as possible in each round, in order \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R3/ASR.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R3/ASR.pdf} \caption{Active sensors ratio for 150 deployed nodes } \label{Figures/ch4/R3/ASR} \end{figure} @@ -759,7 +746,7 @@ Figure~\ref{Figures/ch4/R3/SR} illustrates the percentage of stopped simulation runs per round for 150 deployed nodes. \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R3/SR.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R3/SR.pdf} \caption{Percentage of stopped simulation runs for 150 deployed nodes } \label{Figures/ch4/R3/SR} \end{figure} @@ -772,14 +759,14 @@ In this experiment, we have studied the effect of the energy consumed by the wir \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R3/EC95.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R3/EC95.pdf} \caption{Energy Consumption with $95\%-Lifetime$} \label{Figures/ch4/R3/EC95} \end{figure} \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R3/EC50.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R3/EC50.pdf} \caption{Energy Consumption with $Lifetime50$} \label{Figures/ch4/R3/EC50} \end{figure} @@ -793,7 +780,7 @@ In this experiment, we have observed the superiority of DiLCO-16 protocol and Di \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R3/LT95.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R3/LT95.pdf} \caption{Network Lifetime for $Lifetime95$} \label{Figures/ch4/R3/LT95} \end{figure} @@ -801,7 +788,7 @@ In this experiment, we have observed the superiority of DiLCO-16 protocol and Di \begin{figure}[h!] \centering -\includegraphics[scale=0.6]{Figures/ch4/R3/LT50.pdf} +\includegraphics[scale=0.8]{Figures/ch4/R3/LT50.pdf} \caption{Network Lifetime for $Lifetime50$} \label{Figures/ch4/R3/LT50} \end{figure} diff --git a/CHAPITRE_05.tex b/CHAPITRE_05.tex index 9afbba1..ff82816 100755 --- a/CHAPITRE_05.tex +++ b/CHAPITRE_05.tex @@ -391,7 +391,7 @@ rounds, and thus should extend the network lifetime. \begin{figure}[ht!] \centering - \includegraphics[scale=0.6] {Figures/ch5/R1/CR.pdf} + \includegraphics[scale=0.8] {Figures/ch5/R1/CR.pdf} \caption{Average coverage ratio for 150 deployed nodes} \label{fig3} \end{figure} @@ -415,7 +415,7 @@ nodes in a more efficient manner. \begin{figure}[ht!] \centering -\includegraphics[scale=0.6]{Figures/ch5/R1/ASR.pdf} +\includegraphics[scale=0.8]{Figures/ch5/R1/ASR.pdf} \caption{Active sensors ratio for 150 deployed nodes} \label{fig4} \end{figure} @@ -436,7 +436,7 @@ still connected. \begin{figure}[ht!] \centering -\includegraphics[scale=0.6]{Figures/ch5/R1/SR.pdf} +\includegraphics[scale=0.8]{Figures/ch5/R1/SR.pdf} \caption{Cumulative percentage of stopped simulation runs for 150 deployed nodes } \label{fig6} \end{figure} @@ -458,9 +458,9 @@ network sizes, for $Lifetime_{95}$ and $Lifetime_{50}$. \centering %\begin{multicols}{1} \centering -\includegraphics[scale=0.6]{Figures/ch5/R1/EC95.pdf}\\~ ~ ~ ~ ~(a) \\ +\includegraphics[scale=0.8]{Figures/ch5/R1/EC95.pdf}\\~ ~ ~ ~ ~(a) \\ %\vfill -\includegraphics[scale=0.6]{Figures/ch5/R1/EC50.pdf}\\~ ~ ~ ~ ~(b) +\includegraphics[scale=0.8]{Figures/ch5/R1/EC50.pdf}\\~ ~ ~ ~ ~(b) %\end{multicols} \caption{Energy consumption for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$} @@ -493,7 +493,7 @@ seconds (needed to solve optimization problem) for different values of $T$. The \begin{figure}[ht!] \centering -\includegraphics[scale=0.6]{Figures/ch5/R1/T.pdf} +\includegraphics[scale=0.8]{Figures/ch5/R1/T.pdf} \caption{Execution Time (in seconds)} \label{fig77} \end{figure} @@ -535,9 +535,9 @@ linked. \centering % \begin{multicols}{0} \centering -\includegraphics[scale=0.6]{Figures/ch5/R1/LT95.pdf}\\~ ~ ~ ~ ~(a) \\ +\includegraphics[scale=0.8]{Figures/ch5/R1/LT95.pdf}\\~ ~ ~ ~ ~(a) \\ %\hfill -\includegraphics[scale=0.6]{Figures/ch5/R1/LT50.pdf}\\~ ~ ~ ~ ~(b) +\includegraphics[scale=0.8]{Figures/ch5/R1/LT50.pdf}\\~ ~ ~ ~ ~(b) %\end{multicols} \caption{Network lifetime for (a) $Lifetime_{95}$ and (b) $Lifetime_{50}$} diff --git a/CHAPITRE_06.tex b/CHAPITRE_06.tex index 6ac91bf..d7479d2 100755 --- a/CHAPITRE_06.tex +++ b/CHAPITRE_06.tex @@ -8,7 +8,7 @@ \label{ch6} -\section{summary} +\section{Summary} \label{ch6:sec:01} The most important problem in a Wireless Sensor Network (WSN) is to optimize the @@ -26,7 +26,7 @@ sensors' activities. Extensive simulation experiments have been performed using OMNeT++, the discrete event simulator, to demonstrate that PeCO can offer longer lifetime coverage for WSNs in comparison with some other protocols. -\section{THE PeCO PROTOCOL DESCRIPTION} +\section{The PeCO Protocol Description} \label{ch6:sec:02} \noindent In this section, we describe in details our Lifetime Coverage @@ -183,7 +183,7 @@ the area. \begin{figure}[t!] \centering -\includegraphics[width=95.5mm]{Figures/ch6/Model.pdf} +\includegraphics[scale=0.80]{Figures/ch6/Model.pdf} \caption{PeCO protocol.} \label{fig2} \end{figure} @@ -441,7 +441,7 @@ substantial increase of the coverage performance. \parskip 0pt \begin{figure}[h!] \centering - \includegraphics[scale=0.5] {Figures/ch6/R/CR.eps} + \includegraphics[scale=0.8] {Figures/ch6/R/CR.eps} \caption{Coverage ratio for 200 deployed nodes.} \label{fig333} \end{figure} @@ -463,7 +463,7 @@ Figure \ref{fig333}. \begin{figure}[h!] \centering -\includegraphics[scale=0.5]{Figures/ch6/R/ASR.eps} +\includegraphics[scale=0.8]{Figures/ch6/R/ASR.eps} \caption{Active sensors ratio for 200 deployed nodes.} \label{fig444} \end{figure} @@ -487,8 +487,8 @@ while keeping a good coverage level. \begin{figure}[h!] \centering \begin{tabular}{@{}cr@{}} - \includegraphics[scale=0.475]{Figures/ch6/R/EC95.eps} & \raisebox{2.75cm}{(a)} \\ - \includegraphics[scale=0.475]{Figures/ch6/R/EC50.eps} & \raisebox{2.75cm}{(b)} + \includegraphics[scale=0.8]{Figures/ch6/R/EC95.eps} & \raisebox{4cm}{(a)} \\ + \includegraphics[scale=0.8]{Figures/ch6/R/EC50.eps} & \raisebox{4cm}{(b)} \end{tabular} \caption{Energy consumption per period for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} \label{fig3EC} @@ -515,8 +515,8 @@ Figure~\ref{fig3LT}(a) because the gain induced by our protocols increases with \begin{figure}[h!] \centering \begin{tabular}{@{}cr@{}} - \includegraphics[scale=0.475]{Figures/ch6/R/LT95.eps} & \raisebox{2.75cm}{(a)} \\ - \includegraphics[scale=0.475]{Figures/ch6/R/LT50.eps} & \raisebox{2.75cm}{(b)} + \includegraphics[scale=0.8]{Figures/ch6/R/LT95.eps} & \raisebox{4cm}{(a)} \\ + \includegraphics[scale=0.8]{Figures/ch6/R/LT50.eps} & \raisebox{4cm}{(b)} \end{tabular} \caption{Network Lifetime for (a)~$Lifetime_{95}$ and (b)~$Lifetime_{50}$.} \label{fig3LT} @@ -535,7 +535,7 @@ size. DiLCO is better for coverage ratios near 100\%, but in that case PeCO is not ineffective for the smallest network sizes. \begin{figure}[h!] -\centering \includegraphics[scale=0.5]{Figures/ch6/R/LTa.eps} +\centering \includegraphics[scale=0.8]{Figures/ch6/R/LTa.eps} \caption{Network lifetime for different coverage ratios.} \label{figLTALL} \end{figure} diff --git a/Thesis.tex b/Thesis.tex index ea9beb0..55a4099 100755 --- a/Thesis.tex +++ b/Thesis.tex @@ -73,5 +73,5 @@ \addcontentsline{toc}{part}{Bibliographie} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - + \end{document} diff --git a/Thesis.toc b/Thesis.toc index 0c0901f..33c9ace 100755 --- a/Thesis.toc +++ b/Thesis.toc @@ -63,7 +63,7 @@ \contentsline {subsubsection}{\numberline {4.2.3.2}Leader Election Phase}{69}{subsubsection.4.2.3.2} \contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{69}{subsubsection.4.2.3.3} \contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{69}{subsubsection.4.2.3.4} -\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{69}{section.4.3} +\contentsline {section}{\numberline {4.3}Primary Points based Coverage Problem Formulation}{70}{section.4.3} \contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{71}{section.4.4} \contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{71}{subsection.4.4.1} \contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{72}{subsection.4.4.2} @@ -71,35 +71,35 @@ \contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{73}{subsection.4.4.4} \contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Subregions}{74}{subsection.4.4.5} \contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Primary Point Models}{79}{subsection.4.4.6} -\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{83}{subsection.4.4.7} -\contentsline {section}{\numberline {4.5}Conclusion}{88}{section.4.5} -\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{91}{chapter.5} -\contentsline {section}{\numberline {5.1}Summary}{91}{section.5.1} -\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{91}{section.5.2} -\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{92}{subsection.5.2.1} -\contentsline {subsection}{\numberline {5.2.2}Primary Points based Multiround Coverage Problem Formulation}{93}{subsection.5.2.2} -\contentsline {section}{\numberline {5.3}Experimental Study and Analysis}{95}{section.5.3} -\contentsline {subsection}{\numberline {5.3.1}Simulation Setup}{95}{subsection.5.3.1} -\contentsline {subsection}{\numberline {5.3.2}Metrics}{96}{subsection.5.3.2} -\contentsline {subsection}{\numberline {5.3.3}Results Analysis and Comparison }{97}{subsection.5.3.3} -\contentsline {section}{\numberline {5.4}Conclusion}{100}{section.5.4} -\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{103}{chapter.6} -\contentsline {section}{\numberline {6.1}summary}{103}{section.6.1} -\contentsline {section}{\numberline {6.2}THE PeCO PROTOCOL DESCRIPTION}{103}{section.6.2} -\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{103}{subsection.6.2.1} -\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{106}{subsection.6.2.2} -\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{107}{subsection.6.2.3} -\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{108}{section.6.3} -\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{110}{section.6.4} -\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{110}{subsection.6.4.1} -\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{111}{subsection.6.4.2} -\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{111}{subsubsection.6.4.2.1} -\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{112}{subsubsection.6.4.2.2} -\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{112}{subsubsection.6.4.2.3} -\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{112}{subsubsection.6.4.2.4} -\contentsline {section}{\numberline {6.5}Conclusion}{113}{section.6.5} -\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{117}{part.3} -\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{119}{chapter.7} -\contentsline {section}{\numberline {7.1}Conclusion}{119}{section.7.1} -\contentsline {section}{\numberline {7.2}Perspectives}{120}{section.7.2} -\contentsline {part}{Bibliographie}{136}{chapter*.6} +\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{86}{subsection.4.4.7} +\contentsline {section}{\numberline {4.5}Conclusion}{91}{section.4.5} +\contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{93}{chapter.5} +\contentsline {section}{\numberline {5.1}Summary}{93}{section.5.1} +\contentsline {section}{\numberline {5.2}MuDiLCO Protocol Description}{93}{section.5.2} +\contentsline {subsection}{\numberline {5.2.1}Background Idea and Algorithm}{94}{subsection.5.2.1} +\contentsline {subsection}{\numberline {5.2.2}Primary Points based Multiround Coverage Problem Formulation}{95}{subsection.5.2.2} +\contentsline {section}{\numberline {5.3}Experimental Study and Analysis}{97}{section.5.3} +\contentsline {subsection}{\numberline {5.3.1}Simulation Setup}{97}{subsection.5.3.1} +\contentsline {subsection}{\numberline {5.3.2}Metrics}{98}{subsection.5.3.2} +\contentsline {subsection}{\numberline {5.3.3}Results Analysis and Comparison }{99}{subsection.5.3.3} +\contentsline {section}{\numberline {5.4}Conclusion}{103}{section.5.4} +\contentsline {chapter}{\numberline {6}Perimeter-based Coverage Optimization to Improve Lifetime in Wireless Sensor Networks}{107}{chapter.6} +\contentsline {section}{\numberline {6.1}Summary}{107}{section.6.1} +\contentsline {section}{\numberline {6.2}The PeCO Protocol Description}{107}{section.6.2} +\contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{107}{subsection.6.2.1} +\contentsline {subsection}{\numberline {6.2.2}The Main Idea}{110}{subsection.6.2.2} +\contentsline {subsection}{\numberline {6.2.3}PeCO Protocol Algorithm}{111}{subsection.6.2.3} +\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{113}{section.6.3} +\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{114}{section.6.4} +\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{114}{subsection.6.4.1} +\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{115}{subsection.6.4.2} +\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{115}{subsubsection.6.4.2.1} +\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{115}{subsubsection.6.4.2.2} +\contentsline {subsubsection}{\numberline {6.4.2.3}The Energy Consumption}{117}{subsubsection.6.4.2.3} +\contentsline {subsubsection}{\numberline {6.4.2.4}The Network Lifetime}{117}{subsubsection.6.4.2.4} +\contentsline {section}{\numberline {6.5}Conclusion}{117}{section.6.5} +\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{121}{part.3} +\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{123}{chapter.7} +\contentsline {section}{\numberline {7.1}Conclusion}{123}{section.7.1} +\contentsline {section}{\numberline {7.2}Perspectives}{124}{section.7.2} +\contentsline {part}{Bibliographie}{139}{chapter*.6} diff --git a/bib.bib b/bib.bib index 9afddd8..0d22ad5 100755 --- a/bib.bib +++ b/bib.bib @@ -837,15 +837,6 @@ publisher={IEEE} } -@inproceedings{ref84, - title={Geography-informed energy conservation for ad hoc routing}, - author={Xu, Ya and Heidemann, John and Estrin, Deborah}, - booktitle={Proceedings of the 7th annual international conference on Mobile computing and networking}, - pages={70--84}, - year={2001}, - organization={ACM} -} - @article{ref85, title={Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks}, author={Chen, Benjie and Jamieson, Kyle and Balakrishnan, Hari and Morris, Robert}, @@ -954,14 +945,7 @@ year = {2010}, } -@article{ref96, - title={A Survey on Topology Control in Wireless Sensor Networks: Taxonomy, Comparative Study, and Open Issues}, - author={Li, Mo and Vasilakos, Athanasios V}, - journal={Proceedings of the IEEE}, - volume={101}, - number={12}, - year={2013} -} + @ARTICLE{ref97, author = "S. Misra and M. P. Kumar and M. S. Obaidat", @@ -1119,20 +1103,6 @@ ISSN={1089-7798},} organization={IEEE} } -@ARTICLE{ref111, -author = {Chinh Vu and Shan Gao and Wiwek Deshmukh and Yingshu Li}, -title = {Distributed Energy-Efficient Scheduling Approach for K-Coverage in Wireless Sensor Networks}, -journal ={MILCOM}, -volume = {0}, -isbn = {1-4244-0617-X}, -year = {2006}, -pages = {1-7}, -doi = {http://doi.ieeecomputersociety.org/10.1109/MILCOM.2006.302146}, -publisher = {IEEE Computer Society}, -address = {Los Alamitos, CA, USA}, -} - - @ARTICLE{ref112, title={Energy-aware wireless microsensor networks}, author={Raghunathan, Vijay and Schurgers, Curt and Park, Sung and Srivastava, Mani B}, @@ -1212,15 +1182,18 @@ address = {Los Alamitos, CA, USA}, publisher={Hindawi Publishing Corporation} } + @article{ref120, title={A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints}, author={Casta{\~n}o, Fabian and Rossi, Andr{\'e} and Sevaux, Marc and Velasco, Nubia}, journal={Computers \& Operations Research}, - pages={--}, - year={2013}, + volume={52}, + pages={220--230}, + year={2014}, publisher={Elsevier} } + @article{ref121, title={An exact approach for maximizing the lifetime of sensor networks with adjustable sensing ranges}, author={Rossi, Andr{\'e} and Singh, Alok and Sevaux, Marc}, @@ -1303,16 +1276,7 @@ address = {Los Alamitos, CA, USA}, publisher={Springer} } -@ARTICLE{ref129, - author = "S. Misra and M. P. Kumar and M. S. Obaidat", - title = "Connectivity preserving localized coverage algorithm for area monitoring using -wireless sensor networks ", - JOURNAL = {Computer Communications}, - VOLUME = {34}, - NUMBER = {12}, - PAGES = {1484-1496}, - YEAR = {2011}, -} + @INPROCEEDINGS{ref130, author = {P. Berman and G. Calinescu and C. Shah and A. Zelikovsky}, @@ -1331,19 +1295,6 @@ wireless sensor networks ", organization={IEEE} } -@ARTICLE{ref132, -author = {Chinh Vu and Shan Gao and Wiwek Deshmukh and Yingshu Li}, -title = {Distributed Energy-Efficient Scheduling Approach for K-Coverage in Wireless Sensor Networks}, -journal ={MILCOM}, -volume = {0}, -isbn = {1-4244-0617-X}, -year = {2006}, -pages = {1-7}, -doi = {http://doi.ieeecomputersociety.org/10.1109/MILCOM.2006.302146}, -publisher = {IEEE Computer Society}, -address = {Los Alamitos, CA, USA}, -} - @ARTICLE{ref133, author = "C.-F. Huang and Y.-C. Tseng", title = "The Coverage Problem in a Wireless Sensor Network", @@ -1424,6 +1375,7 @@ wireless sensor networks", organization={IEEE} } + @book{ref139, title={Wireless ad hoc networking: personal-area, local-area, and the sensory-area networks}, author={Wu, Shih-Lin and Tseng, Yu-Chee}, @@ -1554,17 +1506,6 @@ wireless sensor networks", publisher={IEEE} } -@article{ref153, - title={Coverage and connectivity issues in wireless sensor networks: A survey}, - author={Ghosh, Amitabha and Das, Sajal K}, - journal={Pervasive and Mobile Computing}, - volume={4}, - number={3}, - pages={303--334}, - year={2008}, - publisher={Elsevier} -} - @book{ref154, title={Wireless Ad Hoc and Sensor Networks: Theory and Applications}, author={Xiang-Yang Li}, @@ -1707,14 +1648,7 @@ year = {2012}, } -@inproceedings{ref166, - title={A coverage-preserving node scheduling scheme for large wireless sensor networks}, - author={Tian, Di and Georganas, Nicolas D}, - booktitle={Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications}, - pages={32--41}, - year={2002}, - organization={ACM} -} + @inproceedings{ref167, title={Energy-efficient target coverage in wireless sensor networks}, @@ -1778,13 +1712,6 @@ year = {2012}, organization={IEEE} } -@inproceedings{ref173, - title={Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting.}, - author={Olariu, Stephan and Stojmenovic, Ivan}, - booktitle={INFOCOM}, - pages={1--12}, - year={2006} -} @article{ref174, title={Lifetime analysis of reliable wireless sensor networks}, @@ -1809,15 +1736,6 @@ Communication, Control, and Computing}, } -@inproceedings{ref176, - title={On the accuracy of omnet++ in the wireless sensornetworks domain: simulation vs. testbed}, - author={Colesanti, Ugo Maria and Crociani, Carlo and Vitaletti, Andrea}, - booktitle={Proceedings of the 4th ACM workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks}, - pages={25--31}, - year={2007}, - organization={ACM} -} - @inproceedings{ref177, title={A survey of simulators, emulators and testbeds for wireless sensor networks}, author={Imran, Muhammad and Said, Abas Md and Hasbullah, Halabi}, @@ -1984,10 +1902,6 @@ ISSN={2153-0025},} title = {The Network Simulator - ns-3. [online],http://www.nsnam.org/.}, } -@misc{ref196, - title = {The OMNeT++. [online],http://omnetpp.org/.}, -} - @inproceedings{ref197, title={The OMNeT++ discrete event simulation system}, author={Varga, Andr{\'a}s and others}, @@ -2008,16 +1922,6 @@ ISSN={2153-0025},} organization={SCS European Publishing House} } -@article{ref199, - title={Network modelling and simulation tools}, - author={Rahman, Muhammad Azizur and Pak{\v{s}}tas, Algirdas and Wang, Frank Zhigang}, - journal={Simulation Modelling Practice and Theory}, - volume={17}, - number={6}, - pages={1011--1031}, - year={2009}, - publisher={Elsevier} -} @inproceedings{ref200, title={Network simulations with OPNET},