]> AND Private Git Repository - ThesisAli.git/commitdiff
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
Update by Ali 15-1-2015
authorali <ali@ali>
Thu, 15 Jan 2015 22:12:38 +0000 (23:12 +0100)
committerali <ali@ali>
Thu, 15 Jan 2015 22:12:38 +0000 (23:12 +0100)
CHAPITRE_01.tex
CHAPITRE_02.tex
Thesis.tex
Thesis.toc
bib.bib
entete.tex

index 76780d90864b3375f4346131ecaa8b18f446130f..971dbebb563a2e15b7a906ba1382531ef3aea2e1 100644 (file)
@@ -407,6 +407,7 @@ In this section, two energy consumption models are explained. The first model ca
 
 
 \subsection{Radio Energy Dissipation Model}
 
 
 \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
 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}
 
 
 \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
 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.
 \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$.
 
 
 value for receiving the packets. The energy  needed to send or receive a 1-bit packet is equal to $0.2575~mW$.
 
 
index 5b7f45dff57f641e25e94e5a61dfc5ae631a3298..7aaafbe96ecb147af931eae2e6829b2ab5320f55 100644 (file)
@@ -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. 
 
 
 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.
 
 
 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  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  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}}  &    &  \\
 &\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.
 \section{Conclusion}
 \label{ch2:sec:05}
 This chapter has been described some coverage problems proposed in the literature, and their assumptions and proposed solutions.
index 9017b01cc5ae566d735d54c4367f68bf7ea4f575..b190ff539343f978e5d413e50036fb7feba6ffda 100644 (file)
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %% Introduction générale
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %% Introduction générale
-%\include{INTRODUCTION}
+\include{INTRODUCTION}
 
 \part{Scientific Background}
 
 \part{Scientific Background}
-%% Architectures de calcul parallèle
-
 % set the page numbers to be arabic, starting at page 1 %
 \setcounter{page}{1}
 \pagenumbering{arabic}
 % set the page numbers to be arabic, starting at page 1 %
 \setcounter{page}{1}
 \pagenumbering{arabic}
 
 \part{Contributions}
 %% 
 
 \part{Contributions}
 %% 
-%\include{CHAPITRE_03}
+\include{CHAPITRE_03}
 
 
-%% 
-%\include{CHAPITRE_04}
+\include{CHAPITRE_04}
 
 %% 
 %\include{CHAPITRE_05}
 
 %% 
 %\include{CHAPITRE_05}
index c5df802737baf60775cefd6f4dfdf073dc6a3562..35fa59d979c08ffd5d95061b973e3a699ff2c290 100644 (file)
@@ -1,9 +1,15 @@
 \select@language {english}
 \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}
 \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}
 \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 {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 fb391352d6290a3a7eee48a8273ecdaf93d1dd9b..57df98c3dfc40d7d7f73006402ceff19e204201e 100644 (file)
--- a/bib.bib
+++ b/bib.bib
@@ -1579,3 +1579,42 @@ wireless sensor networks",
   publisher={Morgan Kaufmann Publishers}
 }
 
   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}
+}
index 128f76ecbe0f0fe25ce018aea0ec44b6eadf0c82..6dc76f51a32916f176f8f357e692d12aa5cddc8c 100644 (file)
 \usepackage{enumerate}
 \usepackage[english]{babel}
 \usepackage{booktabs}
 \usepackage{enumerate}
 \usepackage[english]{babel}
 \usepackage{booktabs}
-
+%\usepackage{graphicx}
+%\usepackage{subfig}
+\usepackage{multirow}
+\usepackage{array}
 
 \newcommand*\rot{\rotatebox{90}}
 \newcommand*\OK{\ding{51}}
 
 \newcommand*\rot{\rotatebox{90}}
 \newcommand*\OK{\ding{51}}
@@ -38,6 +41,8 @@
         #3%
     \end{tabular}%
 }
         #3%
     \end{tabular}%
 }
+
+
 %%--------------------
 %% Use the style dedicated to PhD thesis from SPIM-UFC
 \UseExtension{spimufcphdthesis}
 %%--------------------
 %% Use the style dedicated to PhD thesis from SPIM-UFC
 \UseExtension{spimufcphdthesis}