\item[GUI] Graphical User Interface
\item[NED] NEtwork Description
\item[ns-2] Network Simulator-2
-\item[OPNET] Optimized Network Engineering tool
+\item[OPNET] Optimized Network Engineering Tool
\item[GloMoSim] Global Mobile System Simulator
\item[SENSE] Sensor Network Simulator and Emulator
\item[GTSNetS] Georgia Tech Sensor Network Simulator
-Wireless sensor networks (WSNs) have recently received a great deal of research attention due to their wide range of potential applications. Many important characteristics are provided by the WSNs which make them different from other wireless ad-hoc networks. These characteristics are imposed lots of limitations on the WSNs that would lead to several challenges in the network. These challenges might include coverage, topology control, routing, data fusion, security, and many others. One of the main research challenges faced in wireless sensor networks is to preserve continuously and effectively the coverage of an area of interest to be monitored, while simultaneously preventing as much as possible a network failure due to battery-depleted nodes.
+Wireless sensor networks (WSNs) have recently received a great deal of research attention due to their wide range of potential applications. Many important characteristics provided by the WSNs make them different from other wireless ad-hoc networks. Furthermore, these characteristics impose lots of limitations that lead to several challenges in the network. These challenges include coverage, topology control, routing, data fusion, security, and many others. One of the main research challenges faced in wireless sensor networks is to preserve continuously and effectively the coverage of an area of interest to be monitored, while simultaneously preventing as much as possible a network failure due to battery-depleted nodes.
In this dissertation, we highly focus on the area coverage problem, energy-efficiency is also the foremost requirement. We have considered distributed optimization protocols with the ultimate objective of prolonging the network lifetime. The proposed distributed optimization protocols (including algorithms, models, and solving integer programs) should be energy-efficient protocols. To address
this problem, this dissertation proposes two-step approaches. Firstly, the sensing field is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of our proposed distributed optimization protocols is distributed and applied on the
sensor nodes in each subregion so as to optimize the coverage and the lifetime performances. In this dissertation, three coverage optimization protocols are proposed. These protocols combine two efficient techniques: leader election for each subregion, followed by an optimization-based planning of sensor activity scheduling decisions for each subregion.
-First, we propose a protocol called Distributed Lifetime Coverage Optimization (DILCO). In this protocol, the lifetime is divided into periods. Each period consists of 4 phases: information exchange, leader election, decision, and sensing. The decision process is
+First, we propose a protocol called Distributed Lifetime Coverage Optimization (DiLCO). In this protocol, the lifetime is divided into periods. Each period consists of 4 phases: information exchange, leader election, decision, and sensing. The decision process is
carried out by a leader node, which solves an integer program in order to provide only one cover set of active sensor nodes to ensure coverage during the sensing phase of the current period.
Then we address the problem of a multiround optimization of the area coverage problem in WSNs. The Multiround Distributed Lifetime Coverage Optimization (MuDiLCO) protocol is suggested so as to study the possibility of providing multiple cover sets of sensors for the sensing phase. MuDiLCO protocol also works in periods
Last but not least, we propose a Perimeter-based Coverage Optimization (PeCO) protocol which is also distributed among sensor nodes in each subregion.The novelty of our approach lies essentially in the formulation of a new
-mathematical optimization model based on the perimeter coverage level to schedule sensors' activities. A new integer program coverage model is solved by the leader during the decision phase so as to provide only one cover set of sensors for the sensing phase.
+mathematical optimization model based on a perimeter coverage level to schedule sensors' activities, whereas we used primary points coverage model in the two previous models. A new integer program coverage model is solved by the leader during the decision phase so as to provide only one cover set of sensors for the sensing phase.
Extensive simulations are conducted using the discrete event simulator OMNET++ to validate the efficiency of each of our proposed protocols. We refer to the characteristics of a Medusa II sensor for the energy consumption and the time computation. In comparison with two other existing methods, our protocols are able to increase
the WSN lifetime and provide improved coverage performance.
-\textbf{KEY WORDS:} Wireless Networks, Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling, Distributed Algorithms, Centralized Algorithms, Robustness, Connectivity, Parallel Algorithms, Energy-efficiency, Heterogeneous Energy Network, Homogeneous Network.
+\textbf{KEY WORDS:} Wireless Sensor Networks, Area Coverage, Network Lifetime, Distributed Optimization, Scheduling.
\item \textbf{OPNET:}
-OPNET (Optimized Network Engineering tool)~\cite{ref192,ref200,ref201} is the first commercial simulation tool 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. OPNET allows researchers to develop 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 model graph and animate the resulting output. Unlike ns-2, 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. OPNET is, a commercial simulator and the license is very expensive. This represents the main disadvantage of that simulator.
+OPNET (Optimized Network Engineering Tool)~\cite{ref192,ref200,ref201} is the first commercial simulation tool 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. OPNET allows researchers to develop 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 model graph and animate the resulting output. Unlike ns-2, 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. OPNET is, a commercial simulator and the license is very expensive. This represents the main disadvantage of that simulator.
\item \textbf{GloMoSim:}
\section{Conclusion}
-In this dissertation, we have concentrated on proposing a distributed optimization protocols so as to prolong the lifetime of wireless sensor networks. We have addressed the problem of the area coverage and the lifetime optimization in wireless sensor networks. The ultimate goal is the coverage preservation and the extension of the network lifetime continuously and effectively when monitoring a certain area of interest.
+In this dissertation, we have concentrated on on the design of distributed optimization protocols so as to prolong the lifetime of wireless sensor networks. We have addressed the problem of the area coverage and the lifetime optimization in wireless sensor networks. The ultimate goal is the coverage preservation and the extension of the network lifetime continuously and effectively when monitoring a certain area of interest.
The first part of the dissertation has presented the scientific background including WSNs, brief survey of related works, and evaluation tools as well as optimization solvers.
-In chapter 4, we have proposed an optimization protocol called Distributed Lifetime Coverage Optimization protocol (DiLCO), which optimizes the coverage and the lifetime of a wireless sensor network. DiLCO protocol is distributed in each sensor node in the subregions of the sensing field. It is implemented in each subregion simultaneously and independently. The proposed DiLCO protocol is a periodic protocol where each period consists of 4 phases: information exchange, leader election, decision, and sensing. The sensor nodes collaborate in each subregion to elect the leader. The leader applies activity scheduling based optimization in order to provide only one optimal set of active sensor nodes that takes the mission of sensing during this period. The performance of our DiLCO protocol has been evaluated by a series of simulations. We have presented a comparison between our proposed protocol and two other existing protocols known in the literature: DESK and GAF. The experimental results have validated our protocol and showed its efficiency in the optimization of the coverage and the lifetime compared to the two references.
+In chapter 4, we have proposed an optimization protocol called Distributed Lifetime Coverage Optimization protocol (DiLCO), which optimizes the coverage and the lifetime of a wireless sensor network. DiLCO protocol is distributed in each sensor node in the subregions of the sensing field. It is implemented in each subregion simultaneously and independently. The proposed DiLCO protocol is a periodic protocol where each period consists of 4 phases: information exchange, leader election, decision, and sensing. The sensor nodes collaborate in each subregion to elect the leader. The leader applies activity scheduling based optimization in order to provide only one optimal set of active sensor nodes that takes the mission of sensing during this period. The performance of our DiLCO protocol has been evaluated by a series of simulations. We have presented a comparison between our proposed protocol and two other existing protocols known in the literature: DESK and GAF. The experimental results have validated our protocol and showed its efficiency in the optimization of the coverage and the lifetime compared to the two benchmarking methods.
Next, we propose in chapter 5 a method called Multiround Distributed Lifetime Coverage Optimization protocol (MuDiLCO), which is an extension of the DiLCO protocol introduced in chapter 4. MuDiLCO implemented an activity scheduling based optimization in order to provide multiple sets of active sensor nodes, for several rounds in the sensing phase. We have thus introduced an improved coverage optimization model that make a multiround optimization, whilst it was a single round optimization in DiLCO. We have conducted many simulations comparing the proposed MuDiLCO protocol for different number of rounds, as well as with DiLCO, DESK, and GAF.
\section{Perspectives}
+In this dissertation, we have focused on the lifetime area coverage optimization problem and we were interested only in energy-efficient distributed protocols, considering static homogeneous sensor nodes. Several parameters, constraints, and requirements can have an important impact on the coverage performance in WSNs.
+Thus, various scenarios parameters might need to be taken into consideration in the future, such as fault-tolerance, k-coverage, $\alpha$-coverage, adjustable sensor’s sensing range network, heterogeneous network, mobility, etc.
-In this dissertation, we have focused on the lifetime area coverage optimization problem and we have interested only in energy-efficient distributed protocols. Various scenarios might need to be taken into consideration such as fault-tolerance, k-coverage, $\alpha$-coverage, adjustable sensor’s sensing range network, heterogeneous network, mobility, etc. In the future, we will concentrate on the following work:
-
-In chapter 4, We have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms. A period will still consist of 4 phases, but the decision phase will compute the schedules for several sensing rounds which, aggregated together, define a kind of meta-sensing round. The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead.
+In chapter 4, we have studied the impact of the number of subregions chosen to subdivide the area of interest, considering different network sizes. The optimal number of subregions will be investigated in the future. We also plan to study and propose a coverage protocol, which computes all active sensor schedules in one time, using optimization methods such as particle swarm optimization or evolutionary algorithms. A period will still consist of 4 phases, but the decision phase will compute the schedules for several sensing rounds which, aggregated together, define a kind of meta-sensing round. The computation of all cover sets in one step is far more difficult, but will reduce the communication overhead.
We also plan to design and propose a heterogeneous integrated optimization protocol in WSNs. This protocol would integrate three energy-efficient (coverage, routing and data aggregation) protocols so as to extend the network lifetime in WSNs. The sensing, routing, and aggregation jobs are also challenges in WSNs. This integrated optimization protocol will be executed by each cluster head, a leader node in our protocols, in the wireless sensor network. The cluster head will be selected in a distributed way and based on local information.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\emph{ \begin{center} \Large Techniques d'Optimisation Couverture Distribuée pour Améliorer la Durée des Réseaux de Capteurs sans Fil \end{center}}
+\emph{ \begin{center} \Large Techniques Distribuées d'Optimisation de la Couverture des Réseaux de Capteurs sans Fil pour Améliorer leur Durée de Vie \end{center}}
%\emph{ \begin{center} \large By \end{center}}
\emph{ \begin{center} \large Ali Kadhum Idrees \\ Université de Franche-Comt\'e, 2015 \end{center}}
%\emph{ \begin{center} \large The University of Franche-Comt\'e, 2015 \end{center}}
\emph{ \begin{center} \large Encadrants: Raphaël Couturier, Karine Deschinkel, and Michel Salomon \end{center}}
-Les réseaux de capteurs sans fil ont suscité beaucoup d'intérêt dans le domaine de la recherche au cours des dernières années en raison de leur large gamme d'applications potentielles. Ils fournissent de nombreuses caractéristiques importantes qui les rendent différents des autres réseaux ad-hoc sans fil. Néanmoins ces caractéristiques imposent beaucoup de limitations susceptibles de créer plusieurs défis dans le domaine des réseaux. Ces défis pourraient inclure la couverture, le contrôle de topologie, le routage, la fusion de données, la sécurité, et bien d'autres. L'une des principales problématiques de recherche étudiée dans les réseaux de capteurs sans fil est la préservation de la couverture d'une zone à surveiller d'une manière permanente et efficace, tout en empêchant autant que possible le dysfonctionnement du réseau en raison de déchargement de batterie de certains n\oe uds.
+Les réseaux de capteurs sans fil ont suscité beaucoup de travaux de recherche au cours des dernières années en raison de leur large gamme d'applications potentielles. Les caractéristiques des noeuds capteurs imposent des contraints enterme de consommation d'énergie et de capacité de traitement qui rendent caduque les protocoles des réseaux ad-hoc sans fil, avec de nombreux défis à résoudre. Parmi ces défis, on peut noter la préservation de la couverture, le contrôle de la topologie, le routage, la fusion de données, la sécurité, etc. La préservation de la couverture d'une région à surveiller, de manière permanente et efficace, tout en empêchant autant que possible un dysfonctionnement du réseau en raison du déchargement de la batterie de certains n\oe uds, est une des problématique de recherche majeures.
-Dans cette thèse, nous nous sommes intéressés au problème de la zone de couverture ainsi qu'à l'efficacité énergétique qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudiés les protocoles d'optimisation distribués avec l'objectif ultime de prolonger la durée de vie du réseau. Les protocoles d'optimisation distribués proposés (y compris les algorithmes, les modèles et la résolution des programmes entiers) doivent être efficaces en terme d'énergie. Pour résoudre ce problème, nous avons proposé de nouvelles approches en deux phases. Dans un premier temps, le champ de surveillance est divisé 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 appliqué sur les n\oe uds de capteurs dans chaque sous-régions afin d'optimiser la couverture et la durée de vie du réseau. Dans cette thèse, nous avons proposé trois protocoles distribués pour l'optimisation de la couverture. Ces protocoles permettent de combiner deux techniques efficaces: une élection de leader pour chaque sous-région, suivie par un processus d'optimisation de l'ordonnancement d'activité de décisions des capteurs pour chaque sous-région.
-Premièrement, nous avons proposé un protocole appelé optimisation distribuée de la durée de vie de la couverture (DILCO). Dans ce protocole, la durée de vie est divisée en périodes. Chaque période se compose de quatre phases: échange d'informations, élection de leader, décision et surveillance. Le processus de décision est effectué par le n\oe ud leader, qui résout un programme entier permettant de définir un seul ensemble de n\oe uds de capteurs actifs pour assurer la couverture durant une période.
+Dans cette thèse, nous nous sommes intéressés au problème de la préservation de la couverture, ainsi qu'à l'efficatité qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudiés les protocoles d'optimisation distribués avec l'objectif ultime de prolonger la durée de vie opérationnelle du réseau. Les protocoles proposés doivent être efficaces en terme de consommation énergétique induite par les calculs et les communications. Pour résoudre le problème, nous avons proposé des nouvelles approches en deux étapes. 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. Dans un second temps, un de nos protocoles est exécuté par chacun des noeuds capteurs 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 noeud leader dans chaque sous-région, suivie par la mise en oeuvre par celui-ci d'un processus de décision via l'optimisation de l'ordonnancement d'activité des noeuds capteurs de sa sous-région.
+
+
+
+
+
+
+
+Le premier protocole proposé est appelé DiLCO, pour Distributed Lifetime Coverage Optimization. Dans ce protocole, la durée de vie est divisée en périodes. Chaque période se compose de quatre phases: échange d'informations, élection de leader, décision et surveillance. Le processus de décision est effectué par le n\oe ud leader, qui résout un programme entier permettant de définir un seul ensemble de n\oe uds de capteurs actifs pour assurer la couverture durant une période.
Ensuite, nous avons étudié le problème de l'optimisation multi-ronde de la zone de couverture dans un réseau de capteurs sans fil. Nous avons proposé le protocole d'optimisation multi-ronde distribué de la durée de vie de couverture (MuDiLCO) pour étudier la possibilité de fournir plusieurs ensembles de n\oe uds de capteurs de couverture pour la phase de surveillance. Ce protocole travaille également en périodes pendant lesquelles les ensembles de capteurs sont programmés pour rester actifs pour un certain nombre de rondes durant la phase de surveillance, pour assurer la couverture et maximiser la durée de vie du réseau. Le processus de décision est toujours effectué par le n\oe ud leader qui résout un programme entier pour définir un meilleur ensemble de capteurs à être utilisé pendant les rondes de la phase de surveillance.
Enfin, nous avons proposé le protocole d'optimisation de la couverture basé sur le périmètre (PeCO) qui est aussi un protocole distribué sur les n\oe uds de capteurs dans chaque sous-région. Notre contribution dans ce protocole consiste essentiellement dans la proposition d'un nouveau modèle mathématique de l'optimisation basé sur le périmètre de couverture pour l'ordonnancement de l'activité des capteurs. Un nouveau programme entier du modèle de couverture est résolu par le leader durant la phase de décision pour définir un ensemble de capteurs de couverture pour la phase de surveillance.
-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.
+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.
-\textbf{MOTS-CLÉS:} Réseaux sans fil, Réseaux de capteurs sans fil, Zone de couverture, Durée de vie du réseau, Optimisation, Ordonnancement, Algorithmes distribués, Algorithmes centralisés, Robustesse, Connectivité, Algorithmes parallèles, Efficacité énergétique, \'Energie des réseaux hétérogènes, Réseaux homogènes.
+\textbf{MOTS-CLÉS:} Réseaux sans fil, Réseaux de capteurs sans fil, Zone de couverture, Durée de vie du réseau, Optimisation, Ordonnancement, Algorithmes distribués, Algorithmes centralisés, Robustesse, Connectivité, Efficacité énergétique, \'Energie des réseaux hétérogènes, Réseaux homogènes, Simulation des Réseaux, Evaluation de Performance, Les Communications sans Fil Ecologiques et le Réseautage.
\addcontentsline{toc}{chapter}{List of Algorithms}
\setlength{\parindent}{0.5cm}
-
%\addcontentsline{toc}{chapter}{List of Abbreviations}
%% Remerciements
\include{ACRONYMS}
\addjury{x1}{y1}{Examiner}{Professor at University of}
\addjury{x2}{y2}{Examiner}{Professor at University of}
\addjury{x3}{y3}{Examiner}{Professor at University of}
-\addjury{x4}{y4}{Examiner}{Professor at University of}
+%\addjury{x4}{y4}{Examiner}{Professor at University of}
\addjury{Raphaël}{Couturier}{Supervisor}{Professor at University of Franche-Comt\'e}
\addjury{Karine}{Deschinkel}{Co-Supervisor}{Assistant Prof. at University of Franche-Comt\'e}
\addjury{Michel}{Salomon}{Co-Supervisor}{Assistant Prof. at University of Franche-Comt\'e}
%%--------------------
%% Set the English abstract
\thesisabstract[english]{
-
+In this dissertation, we highly focus on the area coverage problem, energy-efficiency is also the foremost requirement. We have considered distributed optimization protocols with the ultimate objective of prolonging the network lifetime. The proposed distributed optimization protocols (including algorithms, models, and solving integer programs) should be energy-efficient protocols. To address this problem, this dissertation proposes two-step approaches. Firstly, the sensing field is divided into smaller subregions using the concept of divide-and-conquer method. Secondly, one of our proposed distributed optimization protocols is distributed and applied on the sensor nodes in each subregion so as to optimize the coverage and the lifetime performances. In this dissertation, three coverage optimization protocols are proposed. These protocols combine two efficient techniques: leader election for each subregion, followed by an optimization-based planning of sensor activity scheduling decisions for each subregion. Extensive simulations are conducted using the discrete event simulator OMNeT++ to validate the efficiency of each of our proposed protocols. We refer to the characteristics of a Medusa II sensor for the energy consumption and the time computation. In comparison with two other existing methods, our protocols are able to increase the WSN lifetime and provide improved coverage performance.
}
-\thesiskeywords[english]{ }
+\thesiskeywords[english]{ Wireless Networks, Wireless Sensor Networks, Area Coverage, Network Lifetime, Optimization, Scheduling, Distributed Algorithms, Centralized Algorithms, Robustness, Connectivity, Energy-efficiency, Heterogeneous Energy Network, Homogeneous Network, Network Simulation, Performance Evaluation, Wireless Green Communications and Networking.}
%%--------------------
%% Set the French abstract
\thesisabstract[french]{
+Dans cette thèse, nous nous sommes intéressés au problème de la zone de couverture ainsi qu'à l'efficacité énergétique qui est une exigence essentielle dans un réseau de capteurs sans fil. Nous avons étudiés les protocoles d'optimisation distribués avec l'objectif ultime de prolonger la durée de vie du réseau. Les protocoles d'optimisation distribués proposés (y compris les algorithmes, les modèles et la résolution des programmes entiers) doivent être efficaces en terme d'énergie. Pour résoudre ce problème, nous avons proposé de nouvelles approches en deux phases. Dans un premier temps, le champ de surveillance est divisé 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 appliqué sur les n\oe uds de capteurs dans chaque sous-régions afin d'optimiser la couverture et la durée de vie du réseau. Dans cette thèse, nous avons proposé trois protocoles distribués pour l'optimisation de la couverture. Ces protocoles permettent de combiner deux techniques efficaces: une élection de leader pour chaque sous-région, suivie par un processus d'optimisation de l'ordonnancement d'activité de décisions des capteurs pour chaque sous-région. 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.
}
-\thesiskeywords[french]{ }
+\thesiskeywords[french]{Réseaux sans fil, Réseaux de capteurs sans fil, Zone de couverture, Durée de vie du réseau, Optimisation, Ordonnancement, Algorithmes distribués, Algorithmes centralisés, Robustesse, Connectivité, Efficacité énergétique, \'Energie des réseaux hétérogènes, Réseaux homogènes, Simulation des Réseaux, Evaluation de Performance, Les Communications sans Fil Ecologiques et le Réseautage. }
%%--------------------
