Avec le déploiement de la technologie WiFi ces dernières années, les réseaux locaux sans fil connaissent un grand succès auprès des institutions et les réseaux ad hoc suscitent un réel intérêt auprès de la communauté de R&D. Parallèlement, avec l'émergence des services multimédias dans les réseaux mobiles, des travaux pour l'introduction de la qualité de service dans les réseaux ad hoc ont été proposés. Les études existantes sont souvent basées sur des hypothèses limitées et inadaptées aux propriétés des réseaux ad hoc. Dans cette thèse, nous proposons d'abord un protocole de routage avec différenciation de terminaux qui maximise les liens sans fil de haute qualité. Le but d'une telle approche est de prendre en compte l'hétérogénéité des nœuds dans les réseaux ad hoc et de supporter les situations où des terminaux mobiles peuvent accepter ou refuser la fonction de routage. Notre proposition apporte une solution aux variations des capacités des liens sans fil en routant les paquets de préférence à travers les routeurs collaboratifs ayant une grande capacité de transmission dans le but de maintenir une meilleure qualité de lien (grand débit) des routes dans le réseau. Nous prouvons ensuite la nécessité d'une gestion multicouches de la qualité de service dans un tel environnement. Cela permet de définir une stratégie de QoS en plusieurs couches de communication dans le but de prendre en considération les contraintes liées aux spécificités des réseaux mobiles ad hoc. Une combinaison des mécanismes de qualité de service au niveau IP et MAC (IEEE 802.11) est étudiée. De plus le principe de routage avec différenciation de terminaux décrit ci-dessus a été combiné avec la gestion de la qualité de service IP et MAC. Un autre volet de la thèse traite l'aspect de contrôle de topologie dans les réseaux ad hoc. Il consiste à contrôler la morphologie du réseau en utilisant la mobilité d'un ensemble de routeurs dédiés. Le principe est d'utiliser positivement la mobilité, qui est habituellement subie dans le réseau, afin d'améliorer les performances de ce dernier. Ainsi, des stratégies de déploiement des routeurs dédiés sont étudiées (dans un réseau ad hoc autonome ou interconnecté à une infrastructure) dans le but d'offrir une meilleure connectivité ou pour assurer un meilleur support de la qualité de service des applications temps réel. Pour les deux stratégies, le problème a été formulé comme un problème de programmation linéaire entière mixte. Cette thèse a été réalisée dans le cadre du projet ITEA Ambience. Dans ce contexte, nous avons entre autres contribué à la réalisation d'une plate-forme, qui illustre un exemple d'applications des réseaux ad hoc où des mécanismes décrits dans les parties précédentes sont utilisés afin d'améliorer les performances du système et répondre aux besoins des utilisateurs mobiles, dans un contexte hétérogène sécurisé. Mots-clés : Qualité de service, IEEE 802.11, Différenciation de services, Hétérogénéité des nœuds, Routage ad hoc, Contrôle de topologie, Routeurs dédiés, Connectivité.

Dans cette thèse, nous nous intéressons à l’application du codage réseau pour garantir la qualité de service (QoS) dans les réseaux sans fil multi-sauts. Comme le support de transmission est partagé, les réseaux sans fil souffrent de l’impact négatif des interférences sur la bande passante. Il est alors intéressant de proposer une approche basée sur le codage réseau qui prenne en compte ces interférences durant le processus de routage. Dans ce contexte, nous proposons d’abord un algorithme minimisant l’impact des interférences pour des flux unicast tout en respectant la bande passante qu’ils exigent. Puis, nous le combinons avec le codage réseau afin d’augmenter le nombre des flux acceptés et avec le contrôle de topologie pour améliorer davantage la gestion des interférences. Nous montrons par simulation l’intérêt de combiner les trois domaines : codage réseau, gestion des interférences et contrôle de topologie. Nous abordons également la gestion du délai pour les flux multicast et utilisons le codage réseau basé sur les générations (GBNC) qui combine les paquets par bloc. La plupart des travaux portant sur le GBNC considèrent une taille de génération fixe mais à cause des variations de l’état du réseau le délai de décodage et de récupération du bloc de paquets peut varier, dégradant la QoS. Pour résoudre ce problème, nous proposons une méthode qui ajuste la taille de la génération de façon dynamique pour respecter un certain délai de décodage avec prise en compte des contextes réseau et contenu. De plus, nous améliorons notre approche pour contrecarrer les pertes des acquittements. Puis, nous proposons de l’utiliser dans un réseau de domicile pour la diffusion de vidéo à la demande. Notre solution améliore la QoS et la qualité d’expérience pour l’utilisateur final sans équipement additionnel. Finalement, nous abordons un sujet plus théorique dans lequel nous présentons un nouveau réseau basé sur le schéma Butterfly pour des flux multi-sources multi-destinations. Nous caractérisons la taille du buffer du nœud source en utilisant la théorie des files d’attente et montrons qu’elle correspond aux résultats de simulation. / In this thesis we deal with the application of Network Coding to guarantee the Quality of Service (QoS) for wireless multi-hop networks. Since the medium is shared, wireless networks suffer from the negative interference impact on the bandwidth. It is thus interesting to propose a Network Coding based approach that takes into account this interference during the routing process. In this context, we first propose an algorithm minimizing the interference impact for unicast flows while respecting their required bandwidth. Then, we combine it with Network Coding to increase the number of admitted flows and with Topology Control to still improve the interference management. We show by simulation the benefit of combining the three fields: Network Coding, interference consideration and Topology Control. We also deal with delay management for multicast flows and use the Generation-Based Network Coding (GBNC) that combines the packets per blocks. Most of the works on GBNC consider a fixed generation size. Because of the network state variations, the delay of decoding and recovering a block of packets can vary accordingly degrading the QoS. To solve this problem, we propose a network-and content-aware method that adjusts the generation size dynamically to respect a certain decoding delay. We also enhance it to overcome the issue of acknowledgement loss. We then propose to apply our approach in a Home Area Network for Live TV and video streaming. Our solution provides QoS and Quality of Experience for the end user with no additional equipment. Finally, we focus on a more theoretical work in which we present a new Butterfly-based network for multi-source multi-destination flows. We characterize the source node buffer size using the queuing theory and show that it matches the simulation results.

Au cours des dernières années, les communications inter-véhicule (IVC) sont devenues un domaine de recherche intensif, en particulier dans le cadre des systèmes de transport intelligents. Il suppose que la totalité ou une partie des véhicules est équipé de dispositifs radio permettant la communication entre eux. La norme IEEE 802.11p (normalisé pour la communication des véhicules) devrait être la technologie de facto pour ces communications. En utilisant son mode ad hoc, cette technologie radio permet aux véhicules d'étendre la portée de leur communication en formant un réseau multi-saut sans fil Ad - hoc, également appelé Vehicle ad hoc NETwork (VANET). Cette thèse aborde un problème fondamental des VANET : la capacité du réseau. Deux modèles théoriques simples ont été proposés dans cette thèse pour calculer cette capacité: un « packing problem » (la traduction française nous est inconnue) et un modèle Markovien. Ils offrent des formules simples et fermées sur le nombre maximum d'émetteurs simultanés, et sur la distribution de la distance entre eux. Une borne supérieure sur cette capacité a été proposée. De plus, le modèle Markovien a permis de proposer une formule analytique sur la distribution spatiale des émetteurs. Ces quantités nous permettent, entre autres, de paramétrer le mécanisme d’accès au medium du 802.11p, comme par exemple le seuil du CCA (Clear Channel Assessment), amenant à une optimisation de la capacité du réseau. Afin de valider les différentes contributions théoriques de cette thèse, les résultats des modèles analytiques ont été comparés à des simulations effectuées avec le simulateur de réseau NS-3. Les paramètres de simulations ont été estimés à partir d’expérimentations réelles. De plus, différentes distributions de trafic (trafic de véhicules) ont été considéré afin d’évaluer leur impact sur la capacité du réseau. L’une des applications de cette thèse est le dimensionnement des applications de sécurité routière vis-à-vis de la consommation des ressources réseau. Dans ce cadre, nous nous sommes intéressés aux reconstructions de cartes. Il faut comprendre ICI LA reconstitution de l’environnement d’un véhicule (perception map). Ces applications utilisent des informations provenant de capteurs locaux et distants afin d’offrir un système d’aide à la conduite (conduite autonome, alerte sur des collisions, annonce de situations accidentogènes, etc.). Ces applications nécessitent une bande passante élevée. Notre étude théorique a montré que cette bande passante ne sera sans doute pas disponible en pratique dans les réseaux IEEE 802.11p. Par conséquent, UN algorithme adaptatif de contrôle de puissance a été proposé et optimisé pour cette application particulière. Nous avons montré que notre algorithme, par le biais d'un modèle analytique et d'un grand nombre de simulations que la capacité du réseau est augmentée de manière significative. / In recent years, Inter Vehicle Communication (IVC) has become an intensive research area, as part of Intelligent Transportation Systems. It supposes that all, or a subset of the vehicles is equipped with radio devices, enabling communication between them. IEEE 802.11p (standardized for vehicular communication) shows a great deal of promise. By using ad hoc mode, this radio technology allows vehicles to extend their scopes of communication and thus forming a Multi-hop wireless Ad-hoc NETwork, also called Vehicular Ad-hoc NETwork (VANET). This thesis addresses a fundamental problem of VANET: the network capacity. Two simple theoretical models to estimate this capacity have been proposed: a packing model and a Markovian point process model. They offer simple and closed formulae on the maximum number of simultaneous transmitters, and on the distribution of the distance between them. An accurate upper bound on the maximum capacity had been derived. An analytical formula on distribution of the transmitters had been presented. This distribution allows us to optimize Clear Channel Assessment (CCA) parameters that leads to an optimization of the network capacity.In order to validate the approach of this thesis, results from the analytical models are compared to simulations performed with the network simulator NS-3. Simulation parameters was estimated from real experimentation. Impact of different traffic distributions (traffic of vehicles) on the network capacity is also studied. This thesis also focuses on extended perception map applications, which use information from local and distant sensors to offer driving assistance (autonomous driving, collision warning, etc.). Extended perception requires a high bandwidth that might not be available in practice in classical IEEE 802.11p ad hoc networks. Therefore, this thesis proposes an adaptive power control algorithm optimized for this particular application. It shows through an analytical model and a large set of simulations that the network capacity is then significantly increased.

Les réseaux de capteurs sont au cœur des efforts de recherche de la communauté internationale depuis plusieurs années. Les domaines d'applications sont variés allant du suivi médical à la traçabilité alimentaire en passant par le bâtiment intelligent ou le monitoring urbain (pollution, bruit, consommation électrique...). Pour que ces réseaux denses, composés de centaines voire de milliers d'entités contraintes en énergie, en puissance de calcul et en communication puissent fonctionner et s'adapter aux différentes applications, il est nécessaire, selon nous, de recourir à l'auto-organisation. L'auto-organisation est un processus duquel émerge une structure globale provenant seulement des multiples interactions locales, sans références à la globalité du réseau. De nombreuses études traitent de l'évaluation de performances des stratégies d'auto-organisation. Mais le réseau est toujours considéré comme entièrement déployé, statique. Nous montrons qu'une analyse plus fine est possible pour caractériser les différentes stratégies d'auto-organisation durant la vie d'un réseau de capteurs sans fil en prenant en compte la dynamique du réseau malgré l'immobilité physique des capteurs. On propose de mettre en évidence les différentes phases de la vie d'un réseau de capteurs et de caractériser un ensemble de protocoles d'auto-organisation sur ces différentes phases ; c'est-à-dire d'en déterminer les comportements. Nous ne concevons pas l'auto-organisation comme une fin en soi, elle doit servir à résoudre des problématiques. Après avoir démontré par une série d'expérimentations dans des environnements réels, l'inadaptation de la mesure du signal reçu (RSSI) pour résoudre le défi de la localisation dans les réseaux de capteurs, nous montrons qu'il est possible de concevoir un protocole d'auto-organisation dédié à la localisation du voisinage : le Protocole de Localisation Qualitative: QLoP. Ce protocole permet de déterminer une distance qualitative en se basant uniquement sur le voisinage à 1 et 2 sauts. Nous montrons dans cette thèse que QLoP possède à la fois de bonnes propriétés pour estimer la proximité d'un nœud mais s'adapte aussi parfaitement aux changements de topologie induite par le déploiement de nouveaux capteurs ou la disparition d'autres. Les propriétés de QLoP, démontrées précédemment permettent de construire une topologie logique, le Relative Neighborhood Graph (RNG), de façon efficace. Cette topologie permet de favoriser les liens les plus robustes et d'acheminer ainsi les paquets même dans un environnement très bruité. Enfin, nous montrons que le choix de la couche MAC ainsi que la topologie influent grandement sur les performances d'un réseau de capteurs. Nous proposerons une solution utilisant les propriétés de QLoP afin de définir une couche MAC appropriée.

Un réseau mobile ad hoc (Mobile Ad hoc Network, MANET) est un réseau sans fil, formé dynamiquement par un ensemble d'utilisateurs équipés de terminaux mobiles, sans l'utilisation d'une infrastructure préexistante, ou d'une administration centralisée. Les équipements utilisés dans les MANETs sont limités par la capacité de la batterie, la puissance de calcul et la bande passante. Les utilisateurs des MANETs sont libres de se déplacer, ce qui induit à des topologies dynamiques dans le temps. Toutes ces contraintes ajoutent plus de challenges aux protocoles et services de communications afin de fonctionner dans les MANETs. L'évolution des réseaux de 4ème génération (4G) est appelée à intégrer les MANETs avec les autres types de réseaux afin d'étendre leurs portées. Nous nous sommes intéressés dans la première partie de cette thèse à quelques challenges connus dans les MANETs en proposant des solutions novatrices utilisant des propriétés intéressantes des topologies de graphes. Dans un premier temps, nous avons effectué une étude sur la prédiction de la mobilité afin de maintenir une topologie d'ensemble dominant connecté dans les MANETs. Nous avons proposé dans un autre travail comment construire des topologies de graphes ayant des propriétés globales en se basant seulement sur des informations locales des nœuds mobiles. Ces topologies servent comme overlay aux MANETs. Nous avons proposé des algorithmes distribués pour construire des alliances offensives et défensives globales minimales. Nous avons aussi défini des heuristiques pour ces algorithmes afin de réduire les tailles des alliances obtenues. La première partie de cette thèse est achevée par la proposition d'un framework pour la conception et l'analyse des protocoles de contrôle de topologie dans les MANETs. Nous avons identifié les points communs des algorithmes de contrôle de topologie conçus pour les réseaux mobiles ad hoc et nous avons enrichi le simulateur NS-2 avec un ensemble d'extensions pour supporter le contrôle de topologie / We are interested in this thesis to graph-based approaches to deal with some challenges in networking, namely, graph topologies of mobile ad hoc networks (MANETs) and process model matchmaking in large scale web service. We propose in the first part: (1) a generic mechanism using mobility information of nodes to maintain a graph topology of the network. We show particularly, how to use the prediction of future emplacements of nodes to maintain a connected dominating set of a given MANET. (2) distributed algorithms to construct minimal global offensive alliance and global defensive alliance sets in MANETs. We also introduce several heuristics to get a better approximation of the cardinality of the alliance sets which is a desirable property for practical considerations. (3) a framework to facilitate the design and evaluation of topology control protocols in MANETs. We propose in the framework, a common schema for topology control based on NS-2 simulator and inspired from the commonalities between the components of the topology control algorithms in MANETs. In the second part, we focus on process model matchmaking. We propose two graph-based solutions for process model inexact matching to deal with high computational time of existing work in the literature. In the first solution, we decompose the process models into their possible execution sequences. After, we propose generic graph techniques using string comparator metrics for process model matchmaking based on this decomposition. In order to get better optimization of the execution time and to deal with process model matching in large scale web services, the second solution combines a spectral graph matching with structural and semantic proposed approaches. This solution uses an eigen-decomposition projection technique that makes the runtime faster