From: ali Date: Mon, 5 Oct 2015 13:52:45 +0000 (+0200) Subject: Last update by Ali X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/ThesisAli.git/commitdiff_plain/df0ded57ac60ab03ead82d37326459a25812634a Last update by Ali --- diff --git a/CHAPITRE_04.tex b/CHAPITRE_04.tex index 7ed80e8..c634430 100644 --- a/CHAPITRE_04.tex +++ b/CHAPITRE_04.tex @@ -191,7 +191,14 @@ Active sensors in the period will execute their sensing task to preserve An outline of the protocol implementation is given by Algorithm~\ref{alg:DiLCO} which describes the execution of a period by a node (denoted by $s_j$ for a sensor node indexed by $j$). In the beginning, a node checks whether it has enough energy to stay active during the next sensing phase (i.e., the remaining energy $RE_j$ $\geq$ $E_{th}$ (the amount of energy required to be alive during one period)). If yes, it exchanges information with all the other nodes belonging to the same subregion: it collects from each node its position coordinates, remaining energy ($RE_j$), ID, and the number of one-hop neighbors still alive. Once the first phase is completed, the nodes of a subregion choose a leader to take the decision based on the criteria described in section \ref{ch4:sec:02:03:02}. %the following criteria with decreasing importance: larger number of neighbors, larger remaining energy, and then in case of equality, larger index. -After that, if the sensor node is leader, it will execute the integer program algorithm (see Section~\ref{ch4:sec:03}) which provides a set of sensors planned to be active in the next sensing phase. As leader, it will send an ActiveSleep packet to each sensor in the same subregion to indicate it if it has to be active or not. Alternately, if the sensor is not the leader, it will wait for the ActiveSleep packet to know its state for the coming sensing phase. +After that, if the sensor node is leader, it will execute the integer program algorithm (see Section~\ref{ch4:sec:03}) which provides a set of sensors planned to be active in the next sensing phase. As leader, it will send an ActiveSleep packet to each sensor in the same subregion to indicate it if it has to be active or not. Alternately, if the sensor is not the leader, it will wait for the ActiveSleep packet to know its state for the coming sensing phase. \textcolor{blue}{The flow chart of DiLCO protocol that executed in each sensor node is presented in \ref{flow4}.} + +\begin{figure}[ht!] +\centering +\includegraphics[scale=0.50]{Figures/ch4/Algo1.png} % 70mm +\caption{The flow chart of DiLCO protocol.} +\label{flow4} +\end{figure} %Primary Points based \section{Coverage Problem Formulation} diff --git a/CHAPITRE_05.tex b/CHAPITRE_05.tex index 6604d95..f1dafcd 100644 --- a/CHAPITRE_05.tex +++ b/CHAPITRE_05.tex @@ -92,7 +92,14 @@ The difference with MuDiLCO in that the elected leader in each subregion is for each round of the sensing phase. Each sensing phase is itself divided into $T$ rounds and for each round a set of sensors (a cover set) is responsible for the sensing task. %Each sensor node in the subregion will receive an ActiveSleep packet from leader, informing it to stay awake or to go to sleep for each round of the sensing phase. Algorithm~\ref{alg:MuDiLCO}, which will be executed by each node at the beginning of a period, explains how the ActiveSleep packet is obtained. In this way, a multiround optimization process is performed during each -period after Information~Exchange and Leader~Election phases, in order to produce $T$ cover sets that will take the mission of sensing for $T$ rounds. +period after Information~Exchange and Leader~Election phases, in order to produce $T$ cover sets that will take the mission of sensing for $T$ rounds. \textcolor{blue}{The flow chart of MuDiLCO protocol that executed in each sensor node is presented in \ref{flow5}.} + +\begin{figure}[ht!] +\centering +\includegraphics[scale=0.50]{Figures/ch5/Algo2.png} % 70mm +\caption{The flow chart of MuDiLCO protocol.} +\label{flow5} +\end{figure} %This protocol minimizes the impact of unexpected node failure (not due to batteries running out of energy), because it works in periods. On the one hand, if a node failure is detected before making the decision, the node will not participate during this phase. On the other hand, if the node failure occurs after the decision, the sensing task of the network will be temporarily affected: only during the period of sensing until a new period starts. diff --git a/CHAPITRE_06.tex b/CHAPITRE_06.tex index 33c8fa3..0ea4365 100644 --- a/CHAPITRE_06.tex +++ b/CHAPITRE_06.tex @@ -209,7 +209,14 @@ The sensors inside a same region cooperate to elect a leader. The selection \item larger remaining energy; \item and then in case of equality, larger index. \end{enumerate} -Once chosen, the leader collects information to formulate and solve the integer program which allows to construct the set of active sensors in the sensing stage. +Once chosen, the leader collects information to formulate and solve the integer program which allows to construct the set of active sensors in the sensing stage. \textcolor{blue}{The flow chart of PeCO protocol that executed in each sensor node is presented in \ref{flow6}.} + +\begin{figure}[ht!] +\centering +\includegraphics[scale=0.45]{Figures/ch6/Algo3.pdf} % 70mm +\caption{The flow chart of PeCO protocol.} +\label{flow6} +\end{figure} \section{Perimeter-based Coverage Problem Formulation} diff --git a/Thesis.toc b/Thesis.toc index 710f441..5f74a12 100644 --- a/Thesis.toc +++ b/Thesis.toc @@ -67,42 +67,42 @@ \contentsline {subsubsection}{\numberline {4.2.3.3}Decision phase}{82}{subsubsection.4.2.3.3} \contentsline {subsubsection}{\numberline {4.2.3.4}Sensing phase}{82}{subsubsection.4.2.3.4} \contentsline {section}{\numberline {4.3}Coverage Problem Formulation}{83}{section.4.3} -\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{84}{section.4.4} -\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{84}{subsection.4.4.1} -\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{84}{subsection.4.4.2} +\contentsline {section}{\numberline {4.4}Simulation Results and Analysis}{85}{section.4.4} +\contentsline {subsection}{\numberline {4.4.1}Simulation Framework}{85}{subsection.4.4.1} +\contentsline {subsection}{\numberline {4.4.2}Modeling Language and Optimization Solver}{85}{subsection.4.4.2} \contentsline {subsection}{\numberline {4.4.3}Energy Consumption Model}{85}{subsection.4.4.3} -\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{85}{subsection.4.4.4} +\contentsline {subsection}{\numberline {4.4.4}Performance Metrics}{86}{subsection.4.4.4} \contentsline {subsection}{\numberline {4.4.5}Performance Analysis for Different Number of Subregions}{87}{subsection.4.4.5} -\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Different Number of Primary Points}{93}{subsection.4.4.6} -\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{97}{subsection.4.4.7} +\contentsline {subsection}{\numberline {4.4.6}Performance Analysis for Different Number of Primary Points}{92}{subsection.4.4.6} +\contentsline {subsection}{\numberline {4.4.7}Performance Comparison with other Approaches}{98}{subsection.4.4.7} \contentsline {section}{\numberline {4.5}Conclusion}{104}{section.4.5} \contentsline {chapter}{\numberline {5}Multiround Distributed Lifetime Coverage Optimization Protocol}{105}{chapter.5} \contentsline {section}{\numberline {5.1}Introduction}{105}{section.5.1} \contentsline {section}{\numberline {5.2}Description of the MuDiLCO Protocol }{105}{section.5.2} \contentsline {section}{\numberline {5.3}Primary Points based Multiround Coverage Problem Formulation}{107}{section.5.3} -\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{108}{section.5.4} -\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{108}{subsection.5.4.1} -\contentsline {subsection}{\numberline {5.4.2}Metrics}{108}{subsection.5.4.2} -\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{109}{subsection.5.4.3} +\contentsline {section}{\numberline {5.4}Experimental Study and Analysis}{109}{section.5.4} +\contentsline {subsection}{\numberline {5.4.1}Simulation Setup}{109}{subsection.5.4.1} +\contentsline {subsection}{\numberline {5.4.2}Metrics}{109}{subsection.5.4.2} +\contentsline {subsection}{\numberline {5.4.3}Results Analysis and Comparison }{110}{subsection.5.4.3} \contentsline {section}{\numberline {5.5}Conclusion}{116}{section.5.5} \contentsline {chapter}{\numberline {6} Perimeter-based Coverage Optimization to Improve Lifetime in WSNs}{117}{chapter.6} \contentsline {section}{\numberline {6.1}Introduction}{117}{section.6.1} \contentsline {section}{\numberline {6.2}Description of the PeCO Protocol}{117}{section.6.2} \contentsline {subsection}{\numberline {6.2.1}Assumptions and Models}{117}{subsection.6.2.1} \contentsline {subsection}{\numberline {6.2.2}PeCO Protocol Algorithm}{120}{subsection.6.2.2} -\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{122}{section.6.3} -\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{123}{section.6.4} -\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{123}{subsection.6.4.1} -\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{124}{subsection.6.4.2} -\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{124}{subsubsection.6.4.2.1} -\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{124}{subsubsection.6.4.2.2} -\contentsline {subsubsection}{\numberline {6.4.2.3}Energy Consumption}{125}{subsubsection.6.4.2.3} -\contentsline {subsubsection}{\numberline {6.4.2.4}Network Lifetime}{125}{subsubsection.6.4.2.4} -\contentsline {subsubsection}{\numberline {6.4.2.5}Impact of $\alpha $ and $\beta $ on PeCO's performance}{126}{subsubsection.6.4.2.5} -\contentsline {section}{\numberline {6.5}Conclusion}{130}{section.6.5} -\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{131}{part.3} -\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{133}{chapter.7} -\contentsline {section}{\numberline {7.1}Conclusion}{133}{section.7.1} -\contentsline {section}{\numberline {7.2}Perspectives}{134}{section.7.2} -\contentsline {part}{Publications}{137}{chapter*.15} -\contentsline {part}{Bibliographie}{152}{chapter*.19} +\contentsline {section}{\numberline {6.3}Perimeter-based Coverage Problem Formulation}{123}{section.6.3} +\contentsline {section}{\numberline {6.4}Performance Evaluation and Analysis}{124}{section.6.4} +\contentsline {subsection}{\numberline {6.4.1}Simulation Settings}{124}{subsection.6.4.1} +\contentsline {subsection}{\numberline {6.4.2}Simulation Results}{125}{subsection.6.4.2} +\contentsline {subsubsection}{\numberline {6.4.2.1}Coverage Ratio}{125}{subsubsection.6.4.2.1} +\contentsline {subsubsection}{\numberline {6.4.2.2}Active Sensors Ratio}{125}{subsubsection.6.4.2.2} +\contentsline {subsubsection}{\numberline {6.4.2.3}Energy Consumption}{126}{subsubsection.6.4.2.3} +\contentsline {subsubsection}{\numberline {6.4.2.4}Network Lifetime}{126}{subsubsection.6.4.2.4} +\contentsline {subsubsection}{\numberline {6.4.2.5}Impact of $\alpha $ and $\beta $ on PeCO's performance}{127}{subsubsection.6.4.2.5} +\contentsline {section}{\numberline {6.5}Conclusion}{131}{section.6.5} +\contentsline {part}{III\hspace {1em}Conclusion and Perspectives}{133}{part.3} +\contentsline {chapter}{\numberline {7}Conclusion and Perspectives}{135}{chapter.7} +\contentsline {section}{\numberline {7.1}Conclusion}{135}{section.7.1} +\contentsline {section}{\numberline {7.2}Perspectives}{136}{section.7.2} +\contentsline {part}{Publications}{139}{chapter*.15} +\contentsline {part}{Bibliographie}{154}{chapter*.19} diff --git a/acknowledgements.tex b/acknowledgements.tex index 73480e8..7ef04e2 100644 --- a/acknowledgements.tex +++ b/acknowledgements.tex @@ -10,7 +10,7 @@ %Acknowledgement -First of all, I would like to offer my utmost gratitude to God, the creator of all things, and to thank him for his support and guidance to complete this journey. +%First of all, I would like to offer my utmost gratitude to God, the creator of all things, and to thank him for his support and guidance to complete this journey. The long journey of my Ph.D. study has finished. It is with great pleasure that I acknowledge my debts to those who have greatly contributed to the success of this dissertation. It was only through support and encouragement of many that I have been able to complete this amazing journey. @@ -21,6 +21,6 @@ Besides my supervisors, I would like to express my gratitude to Prof. Dr. YE-Q I I would like to gratefully acknowledge the University of Babylon, Iraq for financial support; Campus France and University of Franche-Comté for the received support. -My appreciation and thanks go to the members of the team AND (Algorithms and Distributed Digital) for the warm and friendly atmosphere in which he allowed me to work. So thank you to Jacques Bahi, Huu Quan Do, Bassam Alkindy, Abdallah Makhoul, Jean-Claude Charr, Jean-François Couchot, Ahmed Mostefaoui, Ahmed Fanfakh, Yousra Ahmed Fadil, Stéphane Domas, Arnaud Giersch, Christophe Guyeux, Mourad Hakem, David Laiyamani, Gilles Michel Perrot, Christien Salim, Carol Habib, Hassan Harb, and Ke Du. I would like to express my thanks and my best wishes to Ingrid Couturier for all the received assistance during my study. I would also like to express my thanks to Dr. Lilia Ziane Khodja, PostDoc at $LTAS-A\&M$, Liege, Belgium. I dare not risk missing to mention anyone’s name, so I will simply say 'thank you ALL for being there for me'. +My appreciation and thanks go to the members of the team AND (Algorithms and Distributed Digital) for the warm and friendly atmosphere in which he allowed me to work. So thank you to Jacques Bahi, Pierre-Cyrille HEAM, Huu Quan Do, Bassam Alkindy, Abdallah Makhoul, Huda AL-NAYYEF, Jean-Claude Charr, Jean-François Couchot, Ahmed Mostefaoui, Ahmed Fanfakh, Yousra Ahmed Fadil, Stéphane Domas, Pierre SAENGER, Zeinab FAWAZ, Arnaud Giersch, Christophe Guyeux, Mourad Hakem, David LAIYMANI, Gilles PERROT, Christian Salim, Bashar AL-NUAIMI, Santiago Costarelli, Carol Habib, Hassan MOUSTAFA HARB, and Ke Du. I would like to express my thanks and my best wishes to Ingrid Couturier for all the received assistance during my study. I would also like to express my thanks to Dr. Lilia Ziane Khodja, PostDoc at $LTAS-A\&M$, Liege, Belgium. I would like to thank Béatrice Domenge and Maxim Moureaux in the Reprographie service for all received assistance during my study. I would also like to thank Patricia Py in the Computer Department secretary. I dare not risk missing to mention anyone’s name, so I will simply say 'thank you ALL for being there for me'. Last but not the least, I would like to extend a warm appreciation to those families and friends who have been encouraging along the way. \ No newline at end of file diff --git a/entete.tex b/entete.tex index 2eca775..309653e 100644 --- a/entete.tex +++ b/entete.tex @@ -107,7 +107,7 @@ In this dissertation, we focus on the area coverage problem, energy-efficiency i %%-------------------- %% Set the French abstract \thesisabstract[french]{ -Dans cette thèse, nous nous sommes intéressés au problème de couverture ainsi qu'à l'efficacité énergétique qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudié des protocoles d'optimisation distribués avec l'objectif de prolonger la durée de vie du réseau. Pour résoudre le problème, nous avons proposé de nouvelles approches articulées en deux phases. Dans un premier temps, la région à surveiller est divisée en petites sous-régions en utilisant le concept de la méthode diviser pour mieux régner. Ensuite, l'un de nos protocoles d'optimisation distribués est exécuté par chaque n\oe ud capteur dans chaque sous-région, afin d'optimiser la couverture et la durée de vie du réseau. Nous proposons trois protocoles distribués qui combinent, chacun, deux techniques efficaces: l'élection d'un n\oe ud leader dans chaque sous-région, suivie par la mise en oeuvre par celui-ci d'un processus d'ordonnancement d'activité des n\oe uds capteurs de sa sous-région. Cet ordonnancement est porté par la formulation et la résolution de programmes linéaires. Pour les deux premiers protocoles, il s'agit de minimiser simultanément la non couverture ou la sous-couverture d'un ensemble de points particuliers. Pour le troisième protocole, le nouveau modèle propose repose sur la couverture du périmètre de chacun des capteurs. Nous avons effectué plusieurs simulations en utilisant le simulateur à évènements discrets OMNeT++ pour valider l'efficacité de nos protocoles proposés. Nous avons pris en considération les caractéristiques d'un capteur Medusa II pour la consommation d'énergie et le temps de calcul. En comparaison avec deux autres méthodes existantes, nos protocoles ont la capacité d'augmenter la durée de vie du réseau de capteurs et d'améliorer les performances de couverture. +Dans cette thèse, nous nous sommes intéressés au problème de couverture ainsi qu'à l'efficacité énergétique qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudié des protocoles d'optimisation distribués avec l'objectif de prolonger la durée de vie du réseau. Pour résoudre le problème, nous avons proposé de nouvelles approches articulées en deux phases. Dans un premier temps, la région à surveiller est divisée en petites sous-régions en utilisant le concept de la méthode diviser pour mieux régner. Ensuite, l'un de nos protocoles d'optimisation distribués est exécuté par chaque n\oe ud capteur dans chaque sous-région, afin d'optimiser la couverture et la durée de vie du réseau. Nous proposons trois protocoles distribués qui combinent, chacun, deux techniques efficaces: l'élection d'un n\oe ud leader dans chaque sous-région, suivie par la mise en oeuvre par celui-ci d'un processus d'ordonnancement d'activité des n\oe uds capteurs de sa sous-région. Cet ordonnancement est porté par la formulation et la résolution de programmes linéaires. Pour les deux premiers protocoles, il s'agit de minimiser simultanément la non couverture ou la sur-couverture d'un ensemble de points particuliers. Pour le troisième protocole, le nouveau modèle propose repose sur la couverture du périmètre de chacun des capteurs. Nous avons effectué plusieurs simulations en utilisant le simulateur à évènements discrets OMNeT++ pour valider l'efficacité de nos protocoles proposés. Nous avons pris en considération les caractéristiques d'un capteur Medusa II pour la consommation d'énergie et le temps de calcul. En comparaison avec deux autres méthodes existantes, nos protocoles ont la capacité d'augmenter la durée de vie du réseau de capteurs et d'améliorer les performances de couverture. }