Spatio-temporal coverage optimization of sensor networks

Les réseaux de capteurs sont formés d’un ensemble de dispositifs capables de prendre individuellement des mesures d’un environnement particulier et d’échanger de l’information afin d’obtenir une représentation de haut niveau sur les activités en cours dans la zone d’intérêt. Une telle détection distribuée, avec de nombreux appareils situés à proximité des phénomènes d’intérêt, est pertinente dans des domaines tels que la surveillance, l’agriculture, l’observation environnementale, la surveillance industrielle, etc. Nous proposons dans cette thèse plusieurs approches pour effectuer l’optimisation des opérations spatio-temporelles de ces dispositifs, en déterminant où les placer dans l’environnement et comment les contrôler au fil du temps afin de détecter les cibles mobiles d’intérêt. La première nouveauté consiste en un modèle de détection réaliste représentant la couverture d’un réseau de capteurs dans son environnement. Nous proposons pour cela un modèle 3D probabiliste de la capacité de détection d’un capteur sur ses abords. Ce modèle inègre également de l’information sur l’environnement grâce à l’évaluation de la visibilité selon le champ de vision. À partir de ce modèle de détection, l’optimisation spatiale est effectuée par la recherche du meilleur emplacement et l’orientation de chaque capteur du réseau. Pour ce faire, nous proposons un nouvel algorithme basé sur la descente du gradient qui a été favorablement comparée avec d’autres méthodes génériques d’optimisation «boites noires» sous l’aspect de la couverture du terrain, tout en étant plus efficace en terme de calculs. Une fois que les capteurs placés dans l’environnement, l’optimisation temporelle consiste à bien couvrir un groupe de cibles mobiles dans l’environnement. D’abord, on effectue la prédiction de la position future des cibles mobiles détectées par les capteurs. La prédiction se fait soit à l’aide de l’historique des autres cibles qui ont traversé le même environnement (prédiction à long terme), ou seulement en utilisant les déplacements précédents de la même cible (prédiction à court terme). Nous proposons de nouveaux algorithmes dans chaque catégorie qui performent mieux ou produits des résultats comparables par rapport aux méthodes existantes. Une fois que les futurs emplacements de cibles sont prédits, les paramètres des capteurs sont optimisés afin que les cibles soient correctement couvertes pendant un certain temps, selon les prédictions. À cet effet, nous proposons une méthode heuristique pour faire un contrôle de capteurs, qui se base sur les prévisions probabilistes de trajectoire des cibles et également sur la couverture probabiliste des capteurs des cibles. Et pour terminer, les méthodes d’optimisation spatiales et temporelles proposées ont été intégrées et appliquées avec succès, ce qui démontre une approche complète et efficace pour l’optimisation spatio-temporelle des réseaux de capteurs.

Modélisation d'éléments finis pour les interactions fluide-structure

Cette thèse concerne la modélisation des interactions fluide-structure et les méthodes numériques qui s’y rattachent. De ce fait, la thèse est divisée en deux parties. La première partie concerne l’étude des interactions fluide-structure par la méthode des domaines fictifs. Dans cette contribution, le fluide est incompressible et laminaire et la structure est considérée rigide, qu’elle soit immobile ou en mouvement. Les outils que nous avons développés comportent la mise en oeuvre d’un algorithme fiable de résolution qui intégrera les deux domaines (fluide et solide) dans une formulation mixte. L’algorithme est basé sur des techniques de raffinement local adaptatif des maillages utilisés permettant de mieux séparer les éléments du milieu fluide de ceux du solide que ce soit en 2D ou en 3D. La seconde partie est l’étude des interactions mécaniques entre une structure flexible et un fluide incompressible. Dans cette contribution, nous proposons et analysons des méthodes numériques partitionnées pour la simulation de phénomènes d’interaction fluide-structure (IFS). Nous avons adopté à cet effet, la méthode dite «arbitrary Lagrangian-Eulerian» (ALE). La résolution fluide est effectuée itérativement à l’aide d’un schéma de type projection et la structure est modélisée par des modèles hyper élastiques en grandes déformations. Nous avons développé de nouvelles méthodes de mouvement de maillages pour aboutir à de grandes déformations de la structure. Enfin, une stratégie de complexification du problème d’IFS a été définie. La modélisation de la turbulence et des écoulements à surfaces libres ont été introduites et couplées à la résolution des équations de Navier-Stokes. Différentes simulations numériques sont présentées pour illustrer l’efficacité et la robustesse de l’algorithme. Les résultats numériques présentés attestent de la validité et l’efficacité des méthodes numériques développées.

Efficient algorithms to solve scheduling problems with a variety of optimization criteria

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d’ordonnancement de grande envergure. L’ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l’exécuter. La plupart des problèmes d’ordonnancement sont NP-Difficiles. Conséquemment, il n’existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d’ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d’explorer ces algorithmes d’ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l’arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d’ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d’optimisation n’est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d’exécuter une tâche au temps t dépend de t.

Critère de validation croisée pour le choix des modèles des petits domaines au niveau des unités

Ce mémoire s’intéresse à l’étude du critère de validation croisée pour le choix des modèles relatifs aux petits domaines. L’étude est limitée aux modèles de petits domaines au niveau des unités. Le modèle de base des petits domaines est introduit par Battese, Harter et Fuller en 1988. C’est un modèle de régression linéaire mixte avec une ordonnée à l’origine aléatoire. Il se compose d’un certain nombre de paramètres : le paramètre β de la partie fixe, la composante aléatoire et les variances relatives à l’erreur résiduelle. Le modèle de Battese et al. est utilisé pour prédire, lors d’une enquête, la moyenne d’une variable d’intérêt y dans chaque petit domaine en utilisant une variable auxiliaire administrative x connue sur toute la population. La méthode d’estimation consiste à utiliser une distribution normale, pour modéliser la composante résiduelle du modèle. La considération d’une dépendance résiduelle générale, c’est-à-dire autre que la loi normale donne une méthodologie plus flexible. Cette généralisation conduit à une nouvelle classe de modèles échangeables. En effet, la généralisation se situe au niveau de la modélisation de la dépendance résiduelle qui peut être soit normale (c’est le cas du modèle de Battese et al.) ou non-normale. L’objectif est de déterminer les paramètres propres aux petits domaines avec le plus de précision possible. Cet enjeu est lié au choix de la bonne dépendance résiduelle à utiliser dans le modèle. Le critère de validation croisée sera étudié à cet effet.

Étude numérique des phénomènes transitoires dans une turbine axiale de type hélice durant l’emballement

Ce mémoire présente l’étude numérique d’un emballement de turbine hydraulique axiale à échelle modèle. Cet état transitoire est simulé du point de meilleur rendement jusqu’à l’atteinte de 95% de la vitesse d’emballement. Pour ce faire, une méthodologie numérique est développée à l’aide du logiciel commercial ANSYS CFX en utilisant une approche "Unsteady Reynolds Averaged Navier-Stokes" avec modèle de turbulence k-ε. Cette méthodologie numérique a été validée grâce à des mesures expérimentales de pression acquises en situation d’emballement sur les aubes d’une roue de turbine axiale étudiée au Laboratoire de Machines Hydrauliques de l’Université Laval. La validation des simulations numériques a été réalisée grâce à des comparaisons dans les domaines temporel et fréquentiel entre les pressions mesurées expérimentalement et calculées numériquement. Les analyses fréquentielles en transitoire ont été effectuées à l’aide de transformées en ondelettes afin de représenter l’évolution temporelle du spectre de fréquence. Des analyses qualitatives de phénomènes hydrauliques prenant place dans la turbine sont aussi présentées. Les analyses effectuées ont permis de confirmer le développement d’un tourbillon en précession par rapport à la roue dans l’aspirateur provocant les fluctuations de pression dominantes à des fréquences subsynchrones. La comparaison entre les données expérimentales et numériques a permis de valider une stratégie de simulation transitoire et d’en définir les limites en vue de prochaines simulations d’emballement. Des tests supplémentaires sont suggérés pour améliorer la précision ou le niveau de confiance de la méthode.