Les réseaux de capteurs sans fil contiennent de nombreux nœuds capables de recueillir et de transmettre des données de manière autonome. Optimiser la collecte de données est une tâche importante pour ces réseaux. Cette optimisation passe par trois axes: 1. L'agrégation des paquets pour réduire le trafic dans le réseau.2. Éviter les interférences et les collisions de paquets. 3. Une bonne stratégie de déploiement des nœuds. D'abord, nous avons travaillé sur l'agrégation de données dans les réseaux de capteurs. Cette technique permet au réseau de réduire la consommation d'énergie en éliminant les paquets redondants, et en combinant plusieurs paquets pour les envoyer en un seul paquet. Dans notre travail, nous avons considéré les applications temps réel dans les réseaux de capteurs. Nous avons proposé une solution qui combine un clustering multi-niveaux avec un mécanisme de transmission de données entre les clusterheads qui favorise l'agrégation. En outre, nous avons développé une nouvelle approche distribuée pour construire un backbone virtuel dans les réseaux de capteurs. Les nœuds du backbone sont les nœuds d'agrégation. Cette technique permet de réduire la consommation d'énergie et améliore la tolérance aux pannes et ainsi augmente la quantité de données qui atteint la station de base. Ensuite, nous nous sommes concentrés sur la façon dont les capteurs accèdent au canal de transmission via les protocoles MAC afin de diminuer le risque de collision des paquets. L'originalité de notre travail est lié à l'utilisation des nœuds mobiles et les applications temps réel dans les réseaux de capteurs sans fil. En effet, ces deux critères ont toujours été traités de façon séparée. Toute approche développée qui vise à améliorer la performance du réseau ne fonctionne bien qu'avec une bonne stratégie de déploiement sur le terrain. Par conséquent, nous proposons une nouvelle solution pour estimer les positions des différents composants du réseau et nous fournissons un nouvel outil pour aider les techniciens sur terrain lors de l'installation de ces composants. Notre solution de déploiement a été appliquée à un réseau de compteurs intelligents appelé EverBlu. Ce système est une solution de collecte de données sans fil développée par Itron. Il est adapté à tout type de compteur (eau, gaz et chaleur) et pour différentes topologies de sites, que ce soit en milieu urbain ou rural / Wireless sensor networks (WSNs) contain many nodes able to collect and transmit data autonomously. Optimizing data collection is an important issue in these networks. This optimization goes through three axis: 1. Packet aggregation to reduce the traffic in the network. 2. Avoiding interference and packets collision. 3. A good deployment strategy in field. We firstly worked on data aggregation in WSNs which enables the network to reduce energy consumption by removing redundant packets, and by combining packets together and sending them as one packet. In our research, we considered real-time applications in WSNs. For these networks, we proposed a solution that combines a multi-level clustering with a data transmission mechanism between cluster heads that promotes aggregation. In addition, we developed a new distributed approach to construct a virtual backbone in a WSN. The nodes inside the backbone are the aggregator nodes. This technique reduces the energy consumption and enhances fault tolerance which increases the amount of data that reaches the sink even when some nodes fail in the network. Then, we focus on how the sensors access to the transmission channel via Medium Access Control (MAC) protocols in order to decrease the risk of packets collision. The originality of our work is related to mobile nodes and real-time WSN applications. In fact, these two criteria were always treated independently. Any developed approach that aims to enhance the network performance works well only with a good deployment strategy in field. Therefore we propose a new solution to predict the different network components and we provide a new tool to assist the technicians in field while installing these components. Our deployment solution was applied to a smart metering network called EverBlu. This system is a wireless data collection solution developed by Itron. It is suitable for any meter type (Water, Gas and Heat) and for various site topologies, either in urban or rural environments

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Les codes correcteurs d’erreurs Non-Binaires Low Density Parity Check (NB-LDPC) sont connus pour avoir de meilleure performance que les codes LDPC binaires. Toutefois, la complexité de décodage des codes non-binaires est bien supérieure à celle des codes binaires. L’objectif de cette thèse est de proposer de nouveaux algorithmes et de nouvelles architectures matérielles de code NB-LDPC pour le décodage des NBLDPC. La première contribution de cette thèse consiste à réduire la complexité du nœud de parité en triant en amont ses messages d’entrées. Ce tri initial permet de rendre certains états très improbables et le matériel requis pour les traiter peut tout simplement être supprimé. Cette suppression se traduit directement par une réduction de la complexité du décodeur NB-LDPC, et ce, sans affecter significativement les performances de décodage. Un modèle d’architecture, appelée "architecture hybride" qui combine deux algorithmes de l’état de l’art ("l’Extended Min Sum" et le "Syndrome Based") a été proposé afin d’exploiter au maximum le pré-tri. La thèse propose aussi de nouvelles méthodes pour traiter les nœuds de variable dans le contexte d’une architecture pré-tri. Différents exemples d’implémentations sont donnés pour des codes NB-LDPC sur GF(64) et GF(256). En particulier, une architecture très efficace de décodeur pour un code de rendement 5/6 sur GF(64) est présentée. Cette architecture se caractérise par une architecture de check node nœud de parité entièrement parallèle. Enfin, une problématique récurrente dans les architectures NB-LDPC, qui est la recherche des P minimums parmi une liste de taille Ns, est abordée. La thèse propose une architecture originale appelée first-then-second minimum pour une implantation efficace de cette tâche. / The Non-Binary Low Density Parity Check (NB-LDPC) codes constitutes an interesting category of error correction codes, and are well known to outperform their binary counterparts. However, their non-binary nature makes their decoding process of higher complexity. This PhD thesis aims at proposing new decoding algorithms for NB-LDPC codes that will be shaping the resultant hardware architectures expected to be of low complexity and high throughput rate. The first contribution of this thesis is to reduce the complexity of the Check Node (CN) by minimizing the number of messages being processed. This is done thanks to a pre-sorting process that sorts the messages intending to enter the CN based on their reliability values, where the less likely messages will be omitted and consequently their dedicated hardware part will be simply removed. This reliability-based sorting enabling the processing of only the highly reliable messages induces a high reduction of the hardware complexity of the NB-LDPC decoder. Clearly, this hardware reduction must come at no significant performance degradation. A new Hybrid architectural CN model (H-CN) combining two state-of-the-art algorithms - Forward-Backward CN (FB-CN) and Syndrome Based CN (SB-CN) - has been proposed. This hybrid model permits to effectively exploit the advantages of pre-sorting. This thesis proposes also new methods to perform the Variable Node (VN) processing in the context of pre-sorting-based architecture. Different examples of implementation of NB-LDPC codes defined over GF(64) and GF(256) are presented. For decoder to run faster, it must become parallel. From this perspective, we have proposed a new efficient parallel decoder architecture for a 5/6 rate NB-LDPC code defined over GF(64). This architecture is characterized by its fully parallel CN architecture receiving all the input messages in only one clock cycle. The proposed new methodology of parallel implementation of NB-LDPC decoders constitutes a new vein in the hardware conception of ultra-high throughput rate decoders. Finally, since the NB-LDPC decoders requires the implementation of a sorting function to extract P minimum values among a list of size Ns, a chapter is dedicated to this problematic where an original architecture called First-Then-Second-Extrema-Selection (FTSES) has been proposed.

La tomographie par rayons X permet un accès direct aux caractéristiques internes des billons scannés par l'intermédiaire des variations de densité et de teneur en eau. L'objectif de ce travail est de démontrer la faisabilité de la détection automatique de caractéristiques dans des billons à des fins d'analyses scientifiques. Nous disposons pour cela d'une base d'images tomographiques de 24 épicéas communs (Picea abies (L.) Karst.) obtenues avec un scanner médical. Les arbres sont représentatifs de différents statuts sociaux et proviennent de quatre peuplements du nord-est de la France, eux-mêmes sont représentatifs de plusieurs classes d'âge, de densité et de fertilité. Les procédures de détection développées sont les suivantes : - détection de la moelle dans les billons, y compris en présence de nœuds et/ou d'excentricité des cernes. La précision de la localisation est inférieure au millimètre ; - détection de la limite aubier/duramen dans les billons, y compris en présence des nœuds (principale source de difficulté). L'erreur sur le diamètre du duramen est de 1.8mm soit une erreur relative de 1.3%. ; - détection de la localisation des verticilles et une comparaison à une méthode optique ; - détection des nœuds individualisés. Cette procédure permet de compter les nœuds dans un billon et de les localiser (hauteur dans le billon et azimut); cependant, la validation de la méthode et l'extraction du diamètre et de l'inclinaison des branches reste à effectuer. Une application de ce travail a été l'analyse de la variabilité de la quantité d'aubier dans le tronc: en intra-arbre, la largeur d'aubier était constante sous la base du houppier; en inter-arbre, une forte corrélation avec la quantité de branches vivantes a notamment été mise en évidence. De nombreuses analyses sont envisageables à partir des résultats de notre travail, parmi lesquelles: l'étude architecturale des arbres avec le suivi de la moelle dans les billons et l'occurrence des prises de relais sur l'axe principal, l'analyse des variations radiales de la forme du duramen, l'analyse de la distribution des nœuds dans les billons.

Un germe équidimensionnel réduit d'espace analytique est dit quasi-odinaire s'il admet une projection finie sur un espace lisse, dont le lieu discriminant est un diviseur à croisements normaux. Le thème de ce travail est la généralisation aux germes quasi-ordinaires de liens connus entre divers invariants des germes de courbes planes. Dans le premier chapitre nous présentons une vision d'ensemble du concept de racine approchée d'un polynôme. Nous insistons sur les applications à l'étude des germes de courbes planes, en montrant que pour la plupart de ces applications, le concept plus général de semi-racine est suffisant. Au début du deuxième chapitre nous utilisons la géométrie torique pour construire une normalisation des germes quasi-ordinaires. Pour les germes irréductibles, de dimension 2 et dimension de plongement 3, nous donnons un algorithme explicite de normalisation, puis nous leur associons de manière intrinsèque un semi-groupe. Nous en déduisons une nouvelle preuve de l'invariance des exposants caractéristiques normalisés. Le concept de semi-racine est essentiel dans notre démarche. Dans le troisième chapitre nous donnons un théorème de factorisation pour la dérivée d'un polynôme quasi-ordinaire, lorsque cette dérivée est elle-même quasi-ordinaire. Ceci généralise un théorème connu sur la structure des courbes polaires des germes de courbes planes. Pour le formuler, nous introduisons l'arbre d'Eggers-Wall, qui permet de factoriser les germes comparables en fonction de leur contact avec le germe étudié. Dans le dernier chapitre nous interprétons topologiquement l'arbre d'Eggers-Wall et la factorisation des germes comparables, dans le cas des germes de courbes planes. Pour cela, nous prouvons un théorème général sur la localisation à isotopie près des noeuds isolables et sédentaires dans les variétés compactes, orientables et irréductibles de dimension 3, dont le bord est formé uniquement de tores.

L'équation de transport, dans le régime fortement collisionnel admet une limite asymptotique de diffusion. Les discrétisations angulaires comme la méthode des ordonnées discrètes Sn où le développement tronqué en harmonique sphérique Pn préservent aussi cette limite de diffusion. Par conséquent, il est intéressant de construire pour de tels systèmes des méthodes de volumes finis sur maillages non structurés qui préservent cette limite de diffusion pour des grilles grossières. En effet, ces modèles peuvent être couplés avec des codes hydrodynamiques Lagrangiens qui génèrent des maillages très tordus. Pour commencer, on considère la discrétisation angulaire la plus simple de l'équation de transport appelée le modèle P1. Après une rapide introduction sur les méthodes 1D, on commence par modifier le schéma acoustique en dimension deux avec la méthode de Jin-Levermore. Le schéma ainsi obtenu n'est pas convergent dans le régime de diffusion car le schéma de diffusion valide n'est pas consistant sur maillages non structurés. Pour résoudre ce problème, on a proposé de nouvelles méthodes valides sur maillages non structurés. Ces méthodes sont basées sur un autre formalisme des méthodes de volumes finis ou les flux sont localisés aux interfaces, couplé avec la méthode de Jin-Levermore. On obtient deux schémas convergents qui dérivent sur les schémas asymptotic preserving 1D. Le schéma limite de diffusion obtenu est un nouveau schéma pour lequel on a donné une preuve de convergence. Dans un second temps, on a proposé une extension du travail réalisé pour le modèle P1 dans le cadre des discrétisations angulaires d'ordres élevés. Pour obtenir une discrétisation asymptotic preserving pour ces modèles on a utilisé une décomposition entre la discrétisation angulaire de premier ordre et les discrétisations angulaires d'ordres supérieurs. Enfin on a étudié la discrétisation du problème d'absorption/émission présent en transfert radiatif ainsi que la discrétisation du modèle non linéaire M1. L'approximation du modèle M1 est basé sur un couplage entre un schéma Lagrange+projection pour une reformulation du modèle M1 et la méthode de Jin-Levermore. La méthode numérique obtenue préserve la limite asymptotique, l'inégalité d'entropie et le principe du maximum associé au système sur maillages non structurés.

Reproduction de : Habilitation à diriger des recherches : Sciences physiques : Lille 1 : 2006. / N° d'ordre (Lille 1) : 547. Synthèse des travaux avec publications reproduites en annexe. Curriculum vitae. Titre provenant de la page de titre du document numérisé. Bibliogr. p. 417-425. Liste des publications et communications.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

De nombreuses recherches ont constaté l'importance des molécules d'ARN, car ils jouent un rôle vital dans beaucoup de procédures moléculaires. Et il est accepté généralement que les structures des molécules d'ARN sont la clé de la découverte de leurs fonctions.Au cours de l'enquête de structures d'ARN, les chercheurs dépendent des méthodes bioinformatiques de plus en plus. Beaucoup de méthodes in silico de prédiction des structures secondaires d'ARN ont émergé dans cette grosse vague, y compris certains qui sont capables de prédire pseudonoeuds, un type particulier de structures secondaires d'ARN.Le but de ce travail est d'essayer de comparer les méthodes de l'état de l'art pour prédiction de pseudonoeud, et offrir aux collègues des idées sur le choix d’une méthode pratique pour la seule séquence donnée. En fait, beaucoup d'efforts ont été fait dans la prédiction des structures secondaires d'ARN parmi lesquelles le pseudonoeud les dernières décennies, contribuant à de nombreux programmes dans ce domaine. Certaines enjeux sont soulevées conséquemment. Comment est-elle la performance de chaque méthode, en particulier sur une classe de séquences d'ARN particulière? Quels sont leurs pour et contre? Que pout-on profiter des méthodes contemporaines si on veut développer de nouvelles? Cette thèse a la confiance dans l'enquête sur les réponses.Cette thèse porte sur très nombreuses comparaisons de la performance de prédire pseudonoeuds d'ARN par les méthodes disponibles. Une partie principale se concentre sur la prédiction de signaux de déphasage par deux méthodes principalement. La deuxième partie principale se concentre sur la prédiction de pseudonoeuds qui participent à des activités moléculaires beaucoup plus générale.Dans le détail, la deuxième partie du travail comprend 414 pseudonoeuds de Pseudobase et de la Protein Data Bank, ainsi que 15 méthodes dont 3 méthodes exactes et 12 heuristiques. Plus précisément, trois grandes catégories de mesures complexes sont introduites, qui divisent encore les 414 pseudonoeuds en une série de sous-classes respectivement.Les comparaisons se passent par comparer les prédictions de chaque méthode basée sur l'ensemble des 414 pseudonœuds, et les sous-ensembles qui sont classés par les deux mesures complexes et la longueur, le type de l'ARN et de l'organisme des pseudonœuds.Le résultat montre que les pseudo-noeuds portent une complexité relativement faible dans toutes les mesures. Et la performance des méthodes modernes varie de sous-classe à l’autre, mais diminue constamment lors que la complexité de pseudonoeuds augmente. Plus généralement, les méthodes heuristiques sont supérieurs globalement à celles exacts. Et les résultats de l'évaluation sensibles sont dépendants fortement de la qualité de structure de référence et le système d'évaluation. Enfin, cette partie du travail est fourni comme une référence en ligne pour la communauté bioinformatique. / Lots of researches convey the importance of the RNA molecules, as they play vital roles in many molecular procedures. And it is commonly believed that the structures of the RNA molecules hold the key to the discovery of their functions.During the investigation of RNA structures, the researchers are dependent on the bioinformatical methods increasingly. Many in silico methods of predicting RNA secondary structures have emerged in this big wave, including some ones which are capable of predicting pseudoknots, a particular type of RNA secondary structures.The purpose of this dissertation is to try to compare the state-of-the-art methods predicting pseudoknots, and offer the colleagues some insights into how to choose a practical method for the given single sequence. In fact, lots of efforts have been done into the prediction of RNA secondary structures including pseudoknots during the last decades, contributing to many programs in this field. Some challenging questions are raised consequently. How about the performance of each method, especially on a particular class of RNA sequences? What are their advantages and disadvantages? What can we benefit from the contemporary methods if we want to develop new ones? This dissertation holds the confidence in the investigation of the answers.This dissertation carries out quite many comparisons of the performance of predicting RNA pseudoknots by the available methods. One main part focuses on the prediction of frameshifting signals by two methods principally. The second main part focuses on the prediction of pseudoknots which participate in much more general molecular activities.In detail, the second part of work includes 414 pseudoknots, from both the Pseudobase and the Protein Data Bank, and 15 methods including 3 exact methods and 12 heuristic ones. Specifically, three main categories of complexity measurements are introduced, which further divide the 414 pseudoknots into a series of subclasses respectively. The comparisons are carried out by comparing the predictions of each method based on the entire 414 pseudoknots, and the subsets which are classified by both the complexity measurements and the length, RNA type and organism of the pseudoknots.The result shows that the pseudoknots in nature hold a relatively low complexity in all measurements. And the performance of contemporary methods varies from subclass to subclass, but decreases consistently as the complexity of pseudoknots increases. More generally, the heuristic methods globally outperform the exact ones. And the susceptible assessment results are dependent strongly on the quality of the reference structures and the evaluation system. Last but not least, this part of work is provided as an on-line benchmark for the bioinformatics community.

Nous proposons des méthodes simples et efficaces pour manipuler des expressions trigonométriques de la forme $F=\sum_{k} f_k\cos\tfrac{k\pi}{n}, f_k\in Z$ où $d<n$ fixé. Nous utilisons les polynômes unitaires de Chebyshev qui forment une base de $Z[x]$ avec laquelle toutes les opérations arithmétiques peuvent être exécutées aussi rapidement qu'avec la base de monômes, mais également déterminer le signe et une approximation de $F$, calculer le polynôme minimal de $F$. Dans ce cadre nous calculons efficacement le polynôme minimal de $2\cos\frac{\pi}{n}$ et aussi le polynôme cyclotomique $\Phi_n$. Nous appliquons ces méthodes au calcul des diagrammes de nœuds de Chebyshev $C(a,b,c,\varphi) : x=T_a(t), y=T_b(t), z=T_c(t+\varphi)$, ce qui permet de tester si une courbe donnée est un nœud, et aussi lister tous les nœuds de Chebyshev possibles quand un triple $(a,b,c)$ fixé en bonne complexité. / We propose a set of simple and fast algorithms for evaluating and using trigonometric expressions in the form $F=\sum_{k}f_k\cos\frac{k\pi}{n}$, $f_k\in Z$ where $d<n$ fixed. We make use of the monic Chebyshev polynomials as a basis of $Z[x]$. We can perform arithmetic operations (multiplication, division, gcd) on polynomials expressed in a Chebyshev basis (with the same bit-complexity as in the monomial basis), compute the sign of $F$, evaluate it numerically and compute its minimal polynomial in $Q[x]$. We propose simple and efficient algorithms for computing the minimal polynomial of $2\cos\frac{\pi}{n}$ and also the cyclotomic polynomial $\Phi_n$. As an application, we give a method to determine the Chebyshev knot's diagrams $C(a,b,c,\varphi) : x=T_a(t),y=T_b(t), z=T_c(t+\varphi)$ which allows to test if a given curve is a Chebyshev knot, and point out all the possible Chebyshev knots coressponding a fixed triple $(a,b,c)$, all of these computings can be done with a good bit complexity.