Dans cette thèse, nous nous sommes intéressés aux réseaux urbains considérés par le projet ANR ARESA2 qui sont principalement des réseaux de capteurs et actionneurs hétérogènes : l'hétérogénéité est causée par la coexistence des noeuds capteurs à faibles ressources et des noeuds actionneurs riches en ressources. Ces derniers devraient être utilisés de manière différenciée par le réseau. C'est dans ce contexte que se déroule cette thèse dans laquelle nous avons étudié des algorithmes d'auto-organisations et de routage s'appuyant sur l'hétérogénéité. Au début, nous nous sommes intéressés à l'auto-organisation dans un contexte hétérogène. Se basant sur l'idée que les ressources au niveau des noeuds actionneurs doivent être exploitées afin de réduire la charge de communication au niveau des noeuds capteurs, nous avons proposé un protocole d'auto-organisation appelée Far-Legos. Far-Legos permet de profiter de la puissance d'émission des actionneurs pour apporter une information de gradient au niveau des capteurs. Les actionneurs initient et construisent une topologie logique. Cette dernière sera utilisée pour faciliter la phase de collecte de données à partir des noeuds capteurs vers les noeuds actionneurs. Ensuite, nous nous sommes intéressés aux liens asymétriques causés par la présence de différents types de noeuds avec différentes portées de transmission. Ces liens asymétriques, causés par l'hétérogénéité au niveau des noeuds constituant le réseau, peuvent détériorer les performances des protocoles de routage qui ne tiennent pas compte de ce type de liens. Pour éviter la dégradation de ces protocoles de routage, nous introduisons une nouvelle métrique de calcul de gradient ou de rang. Celle-ci sera utile pour détecter et éviter les liens asymétriques au niveau de la couche réseau pour le protocole de routage RPL. Nous présentons aussi une adaptation du protocole de collecte de données basé sur Legos pour détecter et éviter ces liens asymétriques. Enfin, nous nous sommes intéressés à l'exploitation de ces liens asymétriques. Nous proposons ainsi un protocole de collecte de données dédiés aux réseaux hétérogènes contenant des liens asymétriques appelé AsymRP. AsymRP est un protocole de routage dédié au trafic de collecte de données basé sur une connaissance de voisinage à 2-sauts combinée avec l'utilisation des messages d'acquittements (ACKs) implicites et une technique de routage de messages ACKs explicites. Cette proposition tire profit des liens asymétriques afin d'assurer une collecte de données fiable.

Important sujet de recherche dans les télécommunications contemporaines, les réseaux de capteurs sont des réseaux sans fil constitués de plusieurs nœuds pouvant communiquer entre eux. Chaque capteur est autonome et possède une durée de vie limitée, liée à la taille de sa batterie. Dans ce contexte, l’énergie est une ressource critique qui peut être économisée en minimisant le nombre de paquets émis. De part la nature du médium radio, les données transmises subissent des pertes du canal. La fiabilisation de données dans ce contexte n’est pas simple et devient d’autant plus problématique lorsque la taille de réseau augmente. C’est dans ce contexte que s’inscrit cette thèse qui vise à fournir une technique de fiabilisation des transmissions dans un réseau de capteur. Pour cela, nous proposons de mettre en oeuvre un mécanisme de transmission qui exploite le code fontaine. Ce code est sans rendement et les symboles de redondance sont générés à la volée. Il permet de fiabiliser la transmission avec l’utilisation d’un canal de retour limité. Le code fontaine permet d’alléger le mécanisme de contrôle des transmissions tout en assurant un lien complètement fiable, ce qui permet de réduire la latence et la consommation énergétique d’une transmission. Afin d’optimiser la performance globale du réseau, nous étudions également dans cette thèse le cas où les nœuds sont autorisés à coopérer pour le relayage multi-sauts de paquets destinés à des nœuds distants. Nous montrons dans cette thèse que la technique de codage réseau permet d’introduire de la diversité d’information et ainsi d’améliorer la performance globale de transmissions multi-sauts mono-chemin. Ce résultat a été étendu à la transmission coopérative pour laquelle nous avons à la fois pu exploiter la diversité d’information et la diversité spatiale. / This thesis is dedicated to the deployment of fountain codes and network coding in a wireless sensor network (WSN). A WSN is composed of sensor nodes with restricted capacities : memory, energy and computational power. The nodes are usually randomly scattered across the monitored area and the environment may vary. In the presence of fading, outage and node failures, fountain codes are a promising solution to guaranty reliability and improve transmission robustness. The benefits of fountain codes are explored based on an event-driven WSNet simulator considering realistic implementation based on standard IEEE802.15.4. Fountain codes are rateless and capable of adapting their rate to the channel on the fly using a limited feedback channel. In this thesis, we highlight the benefits brought by fountain code in terms of energy consumption and transmission delay. In addition to the traditional transmission with fountain code, we propose in this thesis to study the network coding transmission scheme where nodes are allowed to process the information before forwarding it to their neighbors. By this means, we can say that packet diversity is exploited as each individual packet is unique and contains different representations of binary data. Redundancy is thus optimized since repetitions are avoided and replaced with diversified information. This can further lead to an overall improved performance in cooperative communication where nodes are allowed to assist in relaying packets from the source the destination. We highlight in this thesis the benefits of fountain code combined to network coding and show that it leads to a reduction in transmission delay and energy consumption. The latter is vital to the life duration of any wireless sensor network.

L'efficacité énergétique constitue l'objectif clef pour la conception des protocoles de communication pour des réseaux de capteurs radio multi-sauts. Beaucoup d'efforts ont été réalisés à différents niveaux de la pile protocolaire à travers des algorithmes d'agrégation spatiale et temporelle des données, des protocoles de routage efficaces en énergie, et des couches d'accès au médium avec des mécanismes d'ordonnancement permettant de mettre la radio en état d'endormissement afin d'économiser l'énergie. Pour autant, ces protocoles utilisent de façon importante des paquets de contrôle et de découverte du voisinage qui sont coûteux en énergie. En outre, cela se fait très souvent sans aucune interaction entre les différentes couches de la pile. Ces travaux de thèse s'intéressent donc particulièrement à la problématique de l'énergie des réseaux de capteurs à travers des protocoles de routage et d'accès au médium. Les contributions de cette thèse se résument de la manière suivante : Nous nous sommes tout d'abord intéressés à la problématique de l'énergie au niveau routage. Dans cette partie, les contributions se subdivisent en deux parties. Dans un premier temps, nous avons proposé une analyse théorique de la consommation d'énergie des protocoles de routage des réseaux radio multi-sauts d'appréhender au mieux les avantages et les inconvénients des uns et des autres en présence des modèles de trafic variables, un diamètre du réseau variable également et un modèle radio qui permet de modéliser les erreurs de réception des paquets. À l'issue de cette première étude, nous sommes parvenus à la conclusion que pour être économe en énergie, un protocole de routage doit avoir des approches similaires à celle des protocoles de routage géographique sans message hello. Puis, dans un second temps, nous introduisons une étude de l'influence des stratégies de relayage dans un voisinage à 1 saut sur les métriques de performance comme le taux de livraison, le nombre de messages dupliqués et la consommation d'énergie. Cette étude est suivie par une première proposition de protocole de routage géographique sans message hello (Pizza-Forwarding (PF)) exploitant des zones de relayage optimisées et sans aucune hypothèse sur les propriétés du canal radio. Dans le but de réduire considérablement la consommation de PF, nous proposons de le combiner avec une adaptation d'un protocole MAC asynchrone efficace en énergie à travers une approche transversale. La combinaison de ces deux approches montre un gain significatif en terme d'économie d'énergie avec des très bon taux de livraison et cela quels que soient les scénarios et la nature de la topologique. / Energy-efficient communication protocol is a primary design goal for Wireless Sensor Networks (WSNs). Many efforts have been done to save energy anywhere in the protocol stack through temporal and spatial data aggregation schemes, energy-aware routing protocols, activity scheduling and energy-efficient MAC protocols with duty cycle. However both control packets and beacons remain which induces a huge waste energy. Moreover, their design follows the classical layered approach with the principle of modularity in system development, which can lead to a poor performance in WSNs. This thesis focuses on the issues of energy in WSNs through energy-efficient routing and medium access control protocols. The constributions of this thesis can be summarized as follows: First, we are interested on the energy issues at the routing layer for multihop wireless sensor networks (WSNs). We propose a mathematical framework to model and analyze the energy consumption of routing protocols in multihop WSNs by taking into account the protocol parameters, the traffic pattern and the network characteristics defined by the medium channel properties, the dynamic topology behavior, the network diameter and the node density. In this study, we show that Beacon-less routing protocol should be a best candidate to save energy in WSNs. We investigate the performance of some existing relay selection schemes which are used by Beacon-less routing protocols. Extensive simulations are proposed to evaluate their performance locally in terms of packet delivery ratio, duplicated packet and delay. Then, we extend the work in multihop wiriless networks and develop an optimal solution, Enhanced Nearest Forwarding within Radius, which tries to minimize the per-hop expected number of retranmissions in order to save energy. We present a new beaconless routing protocol called Pizza-Forwarding (PF) without any assumption on the radio environment: neither the radio range nor symmetric radio links nor radio properties (shadowing, etc.) are assumed or restricted. A classical greedy mode is proposed. To overcome the hole problem, packets are forwarded to an optimal node in the two hop neighbor following a reactive and optimized neighborhood discovery. In order to save energy due to idle listening and overhearing, we propose to combine PF's main concepts with an energy-efficient MAC protocol to provide a joint MAC/routing protocol suitable for a real radio environment. Performance results lead to conclude to the powerful behavior of PFMAC.

La popularisation des véhicules a engendré des problèmes de sécurité et d’environnement. Desprojets ont été lancés à travers le monde pour améliorer la sécurité sur la route, réduire l’encombrementdu trafic et apporter plus de confort aux conducteurs. L’environnement des réseaux devéhicules est complexe et dynamique, les sources sont souvent hétérogènes, de ce fait les informationséchangées peuvent souvent être imparfaites. La théorie des fonctions de croyance modélisesouplement les connaissances et fournit des outils riches pour gérer les différents types d’imperfection.Elle est utilisée pour représenter l’incertitude, gérer les différentes informations acquises etles fusionner. Nous nous intéressons à la gestion des informations imparfaites échangées entre lesvéhicules concernant les événements sur la route. Les événements locaux et les événements étendusn’ayant pas les mêmes caractéristiques, les travaux réalisés les distinguent. Dans un environnementsans infrastructure où chaque véhicule a son propre module de fusion, l’objectif est de fournir auxconducteurs la synthèse la plus proche possible de la réalité. Différents modèles fondés sur desfonctions de croyance sont proposés et différentes stratégies sont étudiées : affaiblir ou renforcervers l’absence de l’événement pour prendre en compte le vieillissement des messages, garder lesmessages initiaux ou seulement le résultat de la fusion dans la base des véhicules, considérer la miseà jour du monde, prendre en compte l’influence du voisinage pour gérer la spatialité des embouteillages.Les perspectives restent nombreuses, certaines sont développées dans ce manuscrit commela généralisation des méthodes proposées à tous les événements étendus tels que les brouillards. / The popularization of vehicles has created safety and environmental problems. Projects havebeen launched worldwide to improve road safety, reduce traffic congestion and bring more comfortto drivers. The vehicle network environment is dynamic and complex, sources are often heterogeneous,and therefore the exchanged information may be imperfect. The theory of belief functionsoffers flexibility in uncertainty modeling and provides rich tools for managing different types of imperfection.It is used to represent uncertainty, manage and fuse the various acquired information.We focus on the management of imperfect information exchanged between vehicles concerningevents on the road. The carried work distinguishes local events and spatial events, which do nothave the same characteristics. In an environment without infrastructure where each vehicle is afusion center and creates its own vision, the goal is to provide to each driver the synthesis of thesituation on the road as close as possible to the reality. Different models using belief functionsare proposed. Different strategies are considered: discount or reinforce towards the absence of theevent to take into account messages ageing, keep the original messages or just the fusion result invehicle database, consider the world update, manage the spatiality of traffic jam events by takinginto account neighborhood. Perspectives remain numerous; some are developed in the manuscriptas the generalization of proposed methods to all spatial events such as fog blankets.

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

De nos jours, la voiture est devenue le mode de transport le plus utilisé, mais malheureusement, il est accompagné d’un certain nombre de problèmes (accidents, pollution, embouteillages, etc.), qui vont aller en s’aggravant avec l’augmentation prévue du nombre de voitures particulières, malgré les efforts très importants mis en œuvre pour tenter de les réduire ; le nombre de morts sur les routes demeure très important. Les réseaux sans fil de véhicules, appelés VANET, qui consistent de plusieurs véhicules mobiles sans infrastructure préexistante pour communiquer, font actuellement l’objet d'une attention accrue de la part des constructeurs et des chercheurs, afin d’améliorer la sécurité sur les routes ou encore les aides proposées aux conducteurs. Par exemple, ils peuvent avertir d’autres automobilistes que les routes sont glissantes ou qu’un accident vient de se produire. Dans VANET, les protocoles de diffusion (broadcast) jouent un rôle très important par rapport aux messages unicast, car ils sont conçus pour transmettre des messages de sécurité importants à tous les nœuds. Ces protocoles de diffusion ne sont pas fiables et ils souffrent de plusieurs problèmes, à savoir : (1) Tempête de diffusion (broadcast storm) ; (2) Nœud caché (hidden node) ; (3) Échec de la transmission. Ces problèmes doivent être résolus afin de fournir une diffusion fiable et rapide. L’objectif de notre recherche est de résoudre certains de ces problèmes, tout en assurant le meilleur compromis entre fiabilité, délai garanti, et débit garanti (Qualité de Service : QdS). Le travail de recherche de ce mémoire a porté sur le développement d’une nouvelle technique qui peut être utilisée pour gérer le droit d’accès aux médias (protocole de gestion des émissions), la gestion de grappe (cluster) et la communication. Ce protocole intègre l'approche de gestion centralisée des grappes stables et la transmission des données. Dans cette technique, le temps est divisé en cycles, chaque cycle est partagé entre les canaux de service et de contrôle, et divisé en deux parties. La première partie s’appuie sur TDMA (Time Division Multiple Access). La deuxième partie s’appuie sur CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) pour gérer l’accès au medium. En outre, notre protocole ajuste d’une manière adaptative le temps consommé dans la diffusion des messages de sécurité, ce qui permettra une amélioration de la capacité des canaux. Il est implanté dans la couche MAC (Medium Access Control), centralisé dans les têtes de grappes (CH, cluster-head) qui s’adaptent continuellement à la dynamique des véhicules. Ainsi, l’utilisation de ce protocole centralisé nous assure une consommation efficace d’intervalles de temps pour le nombre exact de véhicules actifs, y compris les nœuds/véhicules cachés; notre protocole assure également un délai limité pour les applications de sécurité, afin d’accéder au canal de communication, et il permet aussi de réduire le surplus (overhead) à l’aide d’une propagation dirigée de diffusion. / Nowadays, the car has become the most popular mode of transport, but unfortunately its use is accompanied by a number of problems (accidents, pollution, congestion, etc.). These problems will get worse with the increase in the number of passenger cars, despite very significant efforts made to reduce the number of road deaths, which is still very high. Wireless networks for vehicles called VANET (Vehicle Ad Hoc Networks), were developed when it became possible to connect several mobile vehicles without relying on pre existing communication infrastructures. These networks have currently become the subject of increased attention from manufacturers and researchers, due to their potential for improving road safety and/or offering assistance to drivers. They can, for example, alert other drivers that roads are slippery or that an accident has just occurred. In VANETs, broadcast protocols play a very important role compared to unicast protocols, since they are designed to communicate important safety messages to all nodes. Existing broadcast protocols are not reliable and suffer from several problems: (1) broadcast storms, (2) hidden nodes, and (3) transmission failures. These problems must solved if VANETs are to become reliable and able to disseminate messages rapidly. The aim of our research is to solve some of these problems while ensuring the best compromise among reliability, guaranteed transmission times and bandwidth (Quality of Service: QoS). The research in this thesis focuses on developing a new technique for managing medium access. This protocol incorporates the centralized management approach involving stable clusters. In this technique, time is divided into cycles; with each cycle being shared among the control and service channels, and is divided into two segments. The first is based on TDMA (Time Division Multiple Access) while the second is based on CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) to manage access to the medium. Furthermore, our protocol adaptively adjusts the time consumed in broadcasting safety messages, thereby improving channel capacity. It is implemented in the MAC (Medium Access Control), and centralized in stable cluster heads that are able to adapt to the dynamics of vehicles. This protocol provides a centralized and efficient use of time intervals for an exact number of active vehicles, including hidden nodes/vehicles. Our protocol also provides time intervals dedicated to security applications for providing access to communication channels, and also reduces overhead via directed diffusion of data. Keywords: Ad-hoc networks, VANET, Vehicle, Periodic Safety Messages, broadcast protocols, contention-free.

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

Les réseaux de capteurs sans fils (WSN) sont composés d'un très grand nombre de capteurs, capables de mesurer des paramètres physiques de l'environnement, de mettre en forme l'information obtenue et de la communiquer aux autres capteurs grâce à une interface radio. Les capteurs étant en général déployés sur de très grandes étendues géographiques, l'énergie nécessaire pour les faire fonctionner est fournie par une batterie embarquée sur le capteur. En général, il est difficile de recharger les batteries une fois les capteurs déployés. Economiser l'énergie est donc une préoccupation constante lors de la conception des capteurs et des protocoles de communication utilisés, de manière à prolonger la durée de vie du réseau. Dans ce but, les capteurs transmettent leurs données avec des puissances d'émission très faibles. Avec de telles puissances d'émission, un message ne peut être transmis que sur quelques dizaine de mètres. De ce fait, lorsqu'un capteur détecte un événement, le message est transmis en mode ad-hoc multisauts jusqu'au puits, un nœud spécifique du réseau, qui récolte toutes les informations et est capable de réagir de manière adéquate. Dans cette thèse, nous donnons d'abord un état de l'art avancé sur les WSN. Ensuite nous analysons l'impact du cycle d'endormissement et des liens non fiable sur la couche de routage. A partir des résultats analytiques, nous proposons trois méthodes originales, simples et efficaces pour construire des coordonnées virtuelles en prenant en compte la non fiabilité des liens dans les WSN. En prenant en compte le cycle d'endormissement et les contraintes temps-réel, nous proposons deux protocoles cross-layer qui ont de bons taux de livraison et qui permettent de respecter des contraintes temporelles. Pour pallier à la dynamicité des réseaux de capteurs sans fil, nous proposons un protocole de routage robuste qui adapte ses paramètres quand la topologie change. Enfin, nous concluons et donnons quelques perspectives. / Wireless Sensor Networks (WSNs) are composed of a large number of battery-powered sensor nodes that have the ability to sense the physical environment, compute the obtained information and communicate using the radio interfaces. Because sensor nodes are generally deployed on a large and wild area, they are powered by embedded battery. And it is difficult to change or recharge the battery, thus to reduce the energy consumption when sensors and protocols are designed is very important and can extend the lifetime of WSNs. So sensor nodes transmit packets with a lower transmission power (e.g. OdBm). With this transmission power, a packet can only be transmitted dozens of meters away. Therefore, when a sensor detects an event, a packet is sent in a multi-hop, ad-hoc manner (without fixed infrastructure and each sensor is able to relay the packet) to the sink (specific node which gathers information and reacts to the network situation). In this thesis, we first give an elaborate state of the art of WSNs. Then the impacts of duty-cycle and unreliable links or the performances of routing layer are analyzed. Based on the analytical results, we then propose three new simple yet effective methods to construct virtual coordinates under unreliable links in WSNs. By further taking the duty-cycle and real-time constraints into consideration we propose two cross-layer forwarding protocols which can have a greater delivery ratio and satisfy the deadline requirements. In order to have protocols for the WSNs that have dynamic topology, we then propose a robust forwarding protocol which can adapt its parameters when the topology changes. At last, we conclude this thesis and give some perspectives.

Dans cette thèse, nous nous sommes intéressés aux réseaux urbains considérés par le projet ANR ARESA2 qui sont principalement des réseaux de capteurs et actionneurs hétérogènes : l’hétérogénéité est causée par la coexistence des noeuds capteurs à faibles ressources et des noeuds actionneurs riches en ressources. Ces derniers devraient être utilisés de manière différenciée par le réseau. C’est dans ce contexte que se déroule cette thèse dans laquelle nous avons étudié des algorithmes d’auto-organisations et de routage s’appuyant sur l’hétérogénéité. Au début, nous nous sommes intéressés à l’auto-organisation dans un contexte hétérogène. Se basant sur l’idée que les ressources au niveau des noeuds actionneurs doivent être exploitées afin de réduire la charge de communication au niveau des noeuds capteurs, nous avons proposé un protocole d’auto-organisation appelée Far-Legos. Far-Legos permet de profiter de la puissance d’émission des actionneurs pour apporter une information de gradient au niveau des capteurs. Les actionneurs initient et construisent une topologie logique. Cette dernière sera utilisée pour faciliter la phase de collecte de données à partir des noeuds capteurs vers les noeuds actionneurs. Ensuite, nous nous sommes intéressés aux liens asymétriques causés par la présence de différents types de noeuds avec différentes portées de transmission. Ces liens asymétriques, causés par l’hétérogénéité au niveau des noeuds constituant le réseau, peuvent détériorer les performances des protocoles de routage qui ne tiennent pas compte de ce type de liens. Pour éviter la dégradation de ces protocoles de routage, nous introduisons une nouvelle métrique de calcul de gradient ou de rang. Celle-ci sera utile pour détecter et éviter les liens asymétriques au niveau de la couche réseau pour le protocole de routage RPL. Nous présentons aussi une adaptation du protocole de collecte de données basé sur Legos pour détecter et éviter ces liens asymétriques. Enfin, nous nous sommes intéressés à l’exploitation de ces liens asymétriques. Nous proposons ainsi un protocole de collecte de données dédiés aux réseaux hétérogènes contenant des liens asymétriques appelé AsymRP. AsymRP est un protocole de routage dédié au trafic de collecte de données basé sur une connaissance de voisinage à 2-sauts combinée avec l’utilisation des messages d’acquittements (ACKs) implicites et une technique de routage de messages ACKs explicites. Cette proposition tire profit des liens asymétriques afin d’assurer une collecte de données fiable. / In this thesis, we focused on urban wireless networks considered by the ANR project ARESA2. The networks considered by this project are heterogeneous networks. This heterogeneity is caused by the coexistence of sensor nodes with limited resources and actuator nodes with higher resources. Actuators nodes should be used differentially by the network. Hence designed protocols for WSANs should exploit resource-rich devices to reduce the communication burden on low power nodes. It is in this context that this thesis takes place in which we studied self-organizing and routing algorithms based on the heterogeneity. First, we are interested in self-organization protocols in a heterogeneous network. Based on the idea that resource-rich nodes must be exploited to reduce the communication load level on low-power nodes, we proposed self-organizing protocol called Far-Legos. Far-Legos uses the large transmit power of actuators to provide gradient information to sensor nodes. Actuators initiate and construct a logical topology. The nature of this logical topology is different inside and outside the transmission range of these resourceful nodes. This logical topology will be used to facilitate the data collection from sensor to actuator nodes. Second, we investigated the asymmetric links caused by the presence of heterogeneous nodes with different transmission ranges. The apparition of asymmetric links can dramatically decrease the performance of routing protocols that are not designed to support them. To prevent performance degradation of these routing protocols, we introduce a new metric for rank calculation. This metric will be useful to detect and avoid asymmetric links for RPL routing protocol. We also present an adaptation of data collection protocol based on Legos to detect and avoid these asymmetric links. Finally, we are interested in exploiting the asymmetric links present in the network. We proposed a new routing protocol for data collection in heterogeneous networks, called AsymRP. AsymRP, a convergecast routing protocol, assumes 2-hop neighborhood knowledge and uses implicit and explicit acknowledgment. It takes advantage of asymmetric links to ensure reliable data collection.

No description available.