From 00b2eae97f8480bf95d41419fb7277907fac6023 Mon Sep 17 00:00:00 2001 From: ali Date: Thu, 15 Jan 2015 23:12:38 +0100 Subject: [PATCH] Update by Ali 15-1-2015 --- CHAPITRE_01.tex | 4 ++- CHAPITRE_02.tex | 15 +++++++++- Thesis.tex | 9 ++---- Thesis.toc | 74 ++++++++++++++++++++++++++++++++++++++++++++----- bib.bib | 39 ++++++++++++++++++++++++++ entete.tex | 7 ++++- 6 files changed, 132 insertions(+), 16 deletions(-) diff --git a/CHAPITRE_01.tex b/CHAPITRE_01.tex index 76780d9..971dbeb 100644 --- a/CHAPITRE_01.tex +++ b/CHAPITRE_01.tex @@ -407,6 +407,7 @@ In this section, two energy consumption models are explained. The first model ca \subsection{Radio Energy Dissipation Model} +\label{ch1:sec9:subsec1} Since the communication unit is the most energy-consuming part inside the sensor node, and accordingly there are many authors used the radio energy dissipation model that proposed in~\cite{ref109,ref110} as energy consumption model during the simulation and evaluation of their works in WSNs. Figure~\ref{RDM} shows the radio energy dissipation model. \begin{figure}[h!] \centering @@ -441,6 +442,7 @@ The radio energy dissipation model have been considered only the energy consumed \subsection{Our Energy Consumption Model} +\label{ch1:sec9:subsec2} In this dissertation, the coverage protocols have been 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. 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 @@ -476,7 +478,7 @@ COMPUTATION & on & on & on & 26.83 \\ \end{table} For the sake of simplicity we ignore the energy needed to turn on the radio, to start up the sensor node, to move from one status to another, etc. -Thus, when a sensor becomes active (i.e., it has already chosen its status), it can turn its radio off to save battery. The value of energy spent to send a 1-bit-content message is obtained by using the equation in ~\cite{ref112} to calculate the energy cost for transmitting messages and we propose the same +Thus, when a sensor becomes active (i.e., it has already chosen its status), it can turn its radio off to save battery. The value of energy spent to send a 1-bit-content message is obtained by using the equation in ~\cite{ref112} to calculate the energy cost for transmitting messages and we propose the same value for receiving the packets. The energy needed to send or receive a 1-bit packet is equal to $0.2575~mW$. diff --git a/CHAPITRE_02.tex b/CHAPITRE_02.tex index 5b7f45d..7aaafbe 100644 --- a/CHAPITRE_02.tex +++ b/CHAPITRE_02.tex @@ -102,6 +102,14 @@ The works presented in~\cite{ref134,ref135,ref136} focus on coverage-aware, dist Shibo et al.~\cite{ref137} have expressed the coverage problem as a minimum weight submodular set cover problem and proposed a Distributed Truncated Greedy Algorithm (DTGA) to solve it. They take advantage from both temporal and spatial correlations between data sensed by different sensors, and leverage prediction, to improve the lifetime. +In \cite{ref160} authors transform the area coverage problem to the target +coverage one taking into account the intersection points among disks of sensors +nodes or between disk of sensor nodes and boundaries. + + +In \cite{ref133} authors prove that if the perimeters of sensors are sufficiently covered it will be the case for the whole area. They provide an algorithm in $O(nd~log~d)$ time to compute the perimeter-coverage of +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. @@ -248,12 +256,16 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e & \tiny L. Zhang et al. (2013)~\cite{ref136} & \OK & & \OK & & & \OK & \OK & & \OK & & \OK & &\\ -& \tiny S. He et al. (2012)~\cite{ref137} & \OK & \OK & \OK & & & & \OK & & \OK & & & &\\ +& \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 C. Vu et al. (2006)~\cite{ref132} & \OK & & \OK & & \OK & & \OK & & \OK & & \OK & &\\ +& \tiny X. Deng et al. (2012)~\cite{ref160} & \OK & & \OK & & & & \OK & & \OK & & & &\\ + +& \tiny X. Deng et al. (2005)~\cite{ref133} & \OK & & \OK & & \OK & & \OK & & \OK & & & &\\ + &\textbf{\textcolor{red}{ \tiny DiLCO Protocol (2014)}} & \textbf{\textcolor{red}{\OK}} & & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} & \textbf{\textcolor{red}{\OK}} & & & &\textbf{\textcolor{red}{\OK}} & & \\ &\textbf{\textcolor{red}{ \tiny MuDiLCO Protocol (2014)}} & \textbf{\textcolor{red}{\OK}} & & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} & \textbf{\textcolor{red}{\OK}} & & & \textbf{\textcolor{red}{\OK}} &\textbf{\textcolor{red}{\OK}} & & \\ @@ -271,6 +283,7 @@ check if its $n_i$ is decreased to 0 or not. If $n_i$ of a sensor node is 0 (i.e + \section{Conclusion} \label{ch2:sec:05} This chapter has been described some coverage problems proposed in the literature, and their assumptions and proposed solutions. diff --git a/Thesis.tex b/Thesis.tex index 9017b01..b190ff5 100644 --- a/Thesis.tex +++ b/Thesis.tex @@ -33,11 +33,9 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Introduction générale -%\include{INTRODUCTION} +\include{INTRODUCTION} \part{Scientific Background} -%% Architectures de calcul parallèle - % set the page numbers to be arabic, starting at page 1 % \setcounter{page}{1} \pagenumbering{arabic} @@ -48,10 +46,9 @@ \part{Contributions} %% -%\include{CHAPITRE_03} +\include{CHAPITRE_03} -%% -%\include{CHAPITRE_04} +\include{CHAPITRE_04} %% %\include{CHAPITRE_05} diff --git a/Thesis.toc b/Thesis.toc index c5df802..35fa59d 100644 --- a/Thesis.toc +++ b/Thesis.toc @@ -1,9 +1,15 @@ \select@language {english} -\contentsline {chapter}{Table of Contents}{vi}{chapter*.1} -\contentsline {chapter}{List of Figures}{vii}{chapter*.2} -\contentsline {chapter}{List of Tables}{ix}{chapter*.3} -\contentsline {chapter}{List of Algorithms}{xi}{chapter*.4} -\contentsline {part}{I\hspace {1em}Scientific Background}{xiii}{part.1} +\contentsline {chapter}{Table of Contents}{viii}{chapter*.1} +\contentsline {chapter}{List of Figures}{x}{chapter*.2} +\contentsline {chapter}{List of Tables}{xi}{chapter*.3} +\contentsline {chapter}{List of Algorithms}{xiii}{chapter*.4} +\contentsline {chapter}{Introduction }{xv}{chapter*.5} +\contentsline {section}{\numberline {0.1}General Introduction}{xv}{section.0.1} +\contentsline {section}{\numberline {0.2}Motivation of the Dissertation}{xvi}{section.0.2} +\contentsline {section}{\numberline {0.3}The Objective of this Dissertation}{xvi}{section.0.3} +\contentsline {section}{\numberline {0.4}Main Contributions of this Dissertation}{xvii}{section.0.4} +\contentsline {section}{\numberline {0.5}Dissertation Outline}{xviii}{section.0.5} +\contentsline {part}{I\hspace {1em}Scientific Background}{xix}{part.1} \contentsline {chapter}{\numberline {1}Wireless Sensor Networks}{1}{chapter.1} \contentsline {section}{\numberline {1.1}Introduction}{1}{section.1.1} \contentsline {section}{\numberline {1.2}Wireless Sensor Network Architecture}{2}{section.1.2} @@ -32,5 +38,59 @@ \contentsline {subsection}{\numberline {2.2.2}Distributed Algorithms}{29}{subsection.2.2.2} \contentsline {section}{\numberline {2.3}Conclusion}{32}{section.2.3} \contentsline {part}{II\hspace {1em}Contributions}{35}{part.2} -\contentsline {part}{III\hspace {1em}Conclusions and Perspectives}{37}{part.3} -\contentsline {part}{Bibliographie}{47}{chapter*.5} +\contentsline {chapter}{\numberline {3}Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{37}{chapter.3} +\contentsline {section}{\numberline {3.1}Summary}{37}{section.3.1} +\contentsline {section}{\numberline {3.2}DESCRIPTION OF THE DILCO PROTOCOL}{37}{section.3.2} +\contentsline {subsection}{\numberline {3.2.1}Assumptions and Network Model}{37}{subsection.3.2.1} +\contentsline {subsection}{\numberline {3.2.2}Primary Point Coverage Model}{38}{subsection.3.2.2} +\contentsline {subsection}{\numberline {3.2.3}Main Idea}{39}{subsection.3.2.3} +\contentsline {subsubsection}{\numberline {3.2.3.1}Information Exchange Phase}{40}{subsubsection.3.2.3.1} +\contentsline {subsubsection}{\numberline {3.2.3.2}Leader Election Phase}{41}{subsubsection.3.2.3.2} +\contentsline {subsubsection}{\numberline {3.2.3.3}Decision phase}{41}{subsubsection.3.2.3.3} +\contentsline {subsubsection}{\numberline {3.2.3.4}Sensing phase}{41}{subsubsection.3.2.3.4} +\contentsline {section}{\numberline {3.3}COVERAGE PROBLEM FORMULATION}{41}{section.3.3} +\contentsline {section}{\numberline {3.4}Simulation Results and Analysis}{43}{section.3.4} +\contentsline {subsection}{\numberline {3.4.1}Simulation Framework}{43}{subsection.3.4.1} +\contentsline {subsection}{\numberline {3.4.2}Performance Metrics}{44}{subsection.3.4.2} +\contentsline {subsection}{\numberline {3.4.3}Performance Analysis for Different Subregions}{45}{subsection.3.4.3} +\contentsline {subsubsection}{\numberline {3.4.3.1}Coverage Ratio}{45}{subsubsection.3.4.3.1} +\contentsline {subsubsection}{\numberline {3.4.3.2}Active Sensors Ratio}{46}{subsubsection.3.4.3.2} +\contentsline {subsubsection}{\numberline {3.4.3.3}The percentage of stopped simulation runs}{47}{subsubsection.3.4.3.3} +\contentsline {subsubsection}{\numberline {3.4.3.4}The Energy Consumption}{47}{subsubsection.3.4.3.4} +\contentsline {subsubsection}{\numberline {3.4.3.5}Execution Time}{49}{subsubsection.3.4.3.5} +\contentsline {subsubsection}{\numberline {3.4.3.6}The Network Lifetime}{49}{subsubsection.3.4.3.6} +\contentsline {subsection}{\numberline {3.4.4}Performance Analysis for Primary Point Models}{50}{subsection.3.4.4} +\contentsline {subsubsection}{\numberline {3.4.4.1}Coverage Ratio}{51}{subsubsection.3.4.4.1} +\contentsline {subsubsection}{\numberline {3.4.4.2}Active Sensors Ratio}{51}{subsubsection.3.4.4.2} +\contentsline {subsubsection}{\numberline {3.4.4.3}The percentage of stopped simulation runs}{52}{subsubsection.3.4.4.3} +\contentsline {subsubsection}{\numberline {3.4.4.4}The Energy Consumption}{53}{subsubsection.3.4.4.4} +\contentsline {subsubsection}{\numberline {3.4.4.5}Execution Time}{54}{subsubsection.3.4.4.5} +\contentsline {subsubsection}{\numberline {3.4.4.6}The Network Lifetime}{54}{subsubsection.3.4.4.6} +\contentsline {subsection}{\numberline {3.4.5}Performance Comparison with other Approaches}{56}{subsection.3.4.5} +\contentsline {subsubsection}{\numberline {3.4.5.1}Coverage Ratio}{56}{subsubsection.3.4.5.1} +\contentsline {subsubsection}{\numberline {3.4.5.2}Active Sensors Ratio}{57}{subsubsection.3.4.5.2} +\contentsline {subsubsection}{\numberline {3.4.5.3}The percentage of stopped simulation runs}{57}{subsubsection.3.4.5.3} +\contentsline {subsubsection}{\numberline {3.4.5.4}The Energy Consumption}{58}{subsubsection.3.4.5.4} +\contentsline {subsubsection}{\numberline {3.4.5.5}The Network Lifetime}{59}{subsubsection.3.4.5.5} +\contentsline {section}{\numberline {3.5}Conclusion}{60}{section.3.5} +\contentsline {chapter}{\numberline {4}Multiround Distributed Lifetime Coverage Optimization Protocol in Wireless Sensor Networks}{63}{chapter.4} +\contentsline {section}{\numberline {4.1}Summary}{63}{section.4.1} +\contentsline {section}{\numberline {4.2}MuDiLCO protocol description}{63}{section.4.2} +\contentsline {subsection}{\numberline {4.2.1}Background Idea}{63}{subsection.4.2.1} +\contentsline {subsection}{\numberline {4.2.2}Information Exchange Phase}{64}{subsection.4.2.2} +\contentsline {subsection}{\numberline {4.2.3}Leader Election phase}{64}{subsection.4.2.3} +\contentsline {subsection}{\numberline {4.2.4}Decision phase}{65}{subsection.4.2.4} +\contentsline {subsection}{\numberline {4.2.5}Sensing phase}{66}{subsection.4.2.5} +\contentsline {section}{\numberline {4.3}Experimental Study and Analysis}{66}{section.4.3} +\contentsline {subsection}{\numberline {4.3.1}Simulation Setup}{66}{subsection.4.3.1} +\contentsline {subsection}{\numberline {4.3.2}Metrics}{68}{subsection.4.3.2} +\contentsline {subsection}{\numberline {4.3.3}Results analysis and Comparison }{69}{subsection.4.3.3} +\contentsline {subsection}{\numberline {4.3.4}Coverage ratio}{69}{subsection.4.3.4} +\contentsline {subsection}{\numberline {4.3.5}Active sensors ratio}{69}{subsection.4.3.5} +\contentsline {subsection}{\numberline {4.3.6}Stopped simulation runs}{70}{subsection.4.3.6} +\contentsline {subsection}{\numberline {4.3.7}Energy consumption}{70}{subsection.4.3.7} +\contentsline {subsection}{\numberline {4.3.8}Execution time}{72}{subsection.4.3.8} +\contentsline {subsection}{\numberline {4.3.9}Network lifetime}{72}{subsection.4.3.9} +\contentsline {section}{\numberline {4.4}Conclusion}{73}{section.4.4} +\contentsline {part}{III\hspace {1em}Conclusions and Perspectives}{75}{part.3} +\contentsline {part}{Bibliographie}{85}{chapter*.6} diff --git a/bib.bib b/bib.bib index fb39135..57df98c 100644 --- a/bib.bib +++ b/bib.bib @@ -1579,3 +1579,42 @@ wireless sensor networks", publisher={Morgan Kaufmann Publishers} } +@inproceedings{ref156, + author = {F. Pedraza and A. L. Medaglia and A. Garcia}, + title = {Efficient coverage algorithms for wireless sensor networks}, + booktitle = {Proceedings of the 2006 Systems and Information Engineering Design Symposium}, + pages = {78-83}, + YEAR = {2006}, +} + +@book{ref157, + title={Handbook of sensor networks: algorithms and architectures}, + author={Stojmenovic, Ivan}, + volume={49}, + year={2005}, + publisher={John Wiley \& Sons} +} + +@ARTICLE{ref158, +author = {A. Varga}, +title = {OMNeT++ Discrete Event Simulation System}, +journal = {Available: http://www.omnetpp.org}, +year = {2003}, +} + +@inproceedings{ref159, + title={Coverage and Lifetime Optimization in Heterogeneous Energy Wireless Sensor Networks}, + author={Idrees, Ali Kadhum and Deschinkel, Karine and Salomon, Michel and Couturier, Rapha{\"e}l}, + booktitle={ICN 2014, The Thirteenth International Conference on Networks}, + pages={49--54}, + year={2014} +} + +@article{ref160, + title={Transforming Area Coverage to Target Coverage to Maintain Coverage and Connectivity for Wireless Sensor Networks}, + author={Deng, Xiu and Yu, Jiguo and Yu, Dongxiao and Chen, Congcong}, + journal={International Journal of Distributed Sensor Networks}, + volume={2012}, + year={2012}, + publisher={Hindawi Publishing Corporation} +} diff --git a/entete.tex b/entete.tex index 128f76e..6dc76f5 100644 --- a/entete.tex +++ b/entete.tex @@ -23,7 +23,10 @@ \usepackage{enumerate} \usepackage[english]{babel} \usepackage{booktabs} - +%\usepackage{graphicx} +%\usepackage{subfig} +\usepackage{multirow} +\usepackage{array} \newcommand*\rot{\rotatebox{90}} \newcommand*\OK{\ding{51}} @@ -38,6 +41,8 @@ #3% \end{tabular}% } + + %%-------------------- %% Use the style dedicated to PhD thesis from SPIM-UFC \UseExtension{spimufcphdthesis} -- 2.39.5