Les réseaux sans fil multi-saut (WMN : Wireless multi-hop Networks) sont passés du stade de simple curiosité pour revêtir aujourd'hui un intérêt certain aussi bien du point de vue de la communauté de recherche que des opérateurs de réseaux et services. En analysant les services et applications fournis au sein des réseaux WMNs, nous pouvons constater que certaines applications telles que la visioconférence, la VoIP, etc sont sensibles au délai et nécessitent une certaine qualité de service (QoS). D'autres applications telles que le transfert de fichier, le streaming vidéo, etc. sont gourmands en terme d'utilisation de bande passante. Par conséquent, les architectures de communication des réseaux WMNs doivent intégrer des mécanismes de routage efficaces et adaptés pour répondre aux besoins des services et applications envisagés. Dans cette thèse, Nous nous intéressons à la problématique du routage dans les réseaux WMNs. Notre objectif est de proposer une nouvelle approche de routage qui prend en compte différents métriques de coûts. Tout d'abord, nous avons montré que le routage sous contraintes multiples est un problème NP complet et que trois étapes sont nécessaires à la conception d'une nouvelle solution de routage: (i) modélisation de l'interférence, (ii) l'estimation de la de la bande passante restante, (iii) l'estimation du délai à un saut. Suivant cette vision, nous avons proposé deux variantes du protocole de routage OLSR (SP-OLSR, S2P-OLSR) se basant sur la métrique SINR. Les résultats des simulations ont montré l'intérêt de la proposition dans un contexte de communication vocale (VoIP). Ensuite, nous avons proposé un algorithme d'estimation d'interférence à 2 sauts (2-HEAR) afin d'estimer la bande passante disponible. Puis, et sur la base de cet algorithme, nous avons proposé une nouvelle métrique de routage pour les WMNs: Estimated Balanced Capacity (EBC) en vue de parvenir à l'équilibrage de charge entre des différents flux. La dernière question abordée dans cette thèse est celle de l'estimation du délai à un saut. La solution proposée donne une borne du délai en se basant sur un modèle de file d'attente de type G/G/1. Enfin, nous avons englobé toutes les précédentes contributions pour mettre en place une nouvelle approche de routage hybride sous contraintes multiples. Ce protocole comporte une partie proactive utilisant la nouvelle métrique de routage (EBC) et une partie réactive qui permet de prendre en compte le délai relative à une connexion donné. / There is a growing interest in wireless multi-hop networks (WMNs) since there are promising in opening new business opportunity for network operators and service providers. This research field aims at providing wireless communication means to carry different types of applications (FTP, Web browsing, video streaming, in addition to VoIP). Such applications have different constraints and their specific requirements in terms of Quality of Service (QoS) or performance metrics (delay jitter, end-to-end delay). We examine, in this thesis, the problem of routing in WMNs. Our main goal is to propose a new multi-metrics routing capable to fit these particular needs. In this thesis, we make several contributions toward WMN multi-constrained routing. First, we show that the multi-constrained path finding problem is NP-Complete and inherently a cross-layer issue, and that three steps are necessary to design the multi-metric routing protocol: (i) modeling of the inferring signal, (ii) estimation of the remaining bandwidth, (iii) estimation of the one-hop delay. Second, moving in such direction, we propose two enhanced versions of the OLSR routing protocol. The suggested protocols consider the SINR as a routing metric to build a reliable topology graph. Performance evaluation shows that utilizing such routing metric helps to improve significantly the VoIP application quality in the context of ad hoc network while maintaining a reasonable overhead cost. Third, we have proposed a 2-Hop interference Estimation Algorithm (2-HEAR) in order to estimate the available bandwidth. Then, and based on such algorithm, we have proposed a novel routing metric for WMNs: Estimated Balanced Capacity (EBC) in order to achieve load-balancing among the different flows. The next issue tackled in this thesis is the one-hop delay estimation, the one-hop delay is estimated by means of an analytical model based on G/G/1 queue. Finally, we have encompassed all the previous contributions to address our main goal, i.e. the design of a multi-constrained routing protocol for WMNs. A hybrid routing protocol is then proposed. This protocol is a junction of two parts : a proactive part that makes use of the previously estimated constraint, and a reactive part, which is triggered ”on demand” when news applications are expressed.

Ein drahtloses Multihop-Netzwerk (DMN) ist ein verteiltes Kommunikationssystem, welches vor allem die Fähigkeit zur automatischen Anpassung an sich ständig änderne Umgebungsbedingungen hat. Eine zentrale Fragestellung in DMNen ist, ob das Netzwerk partitioniert ist, ob also nicht mehr jeder Knoten mit jedem anderen Knoten kommunizieren kann. Um festzustellen, ob eine Partitionierung droht werden mit Hilfe von 2-Zusammenhangstests Brücken und Artikulationspunkte im Kommunikationsgraphen gesucht. Daraufhin können anschließend korrektive Aktionen eingeleitet werden um die Partitionierung zu verhindern und somit die Netzwerkverfügbarkeit zu erhöhen. Eine Vielzahl von 2-Zusammenhangstestverfahren wurde bereits erfolgreich bei drahtgebundenen Netzen eingesetzt. Allerdings sind diese Verfahren ungeeignet für drahtlose Netze, da die Ungenauigkeiten durch den häufigen Paketverlust in solchen Systemen bisher nicht berücksichtigt wurden. Mit Hilfe von stochastischen Modellen wird gezeigt, dass Fehler in der Entscheidungsfindung für DMNen bereits bei sehr einfachen Problemen wie der Link-Erkennung signifikant sein können. In dieser Arbeit werden daher verschiedene Verfahren präsentiert, die auch auf Grundlage unsicherer Informationen noch eine verlässliche Entscheidungsfindung ermöglichen. Die Arbeit präsentiert einen neuen verteilten Algorithmus zum Test auf 2-Zusammenhang, welcher Fehler durch Nachrichtenverlust berücksichtigt und gleichzeitig die Anzahl an Nachrichten reduziert. Basierend auf einer umfassenden Analyse der Einflüsse von Kommunikationsfehlern auf den Algorithmus, wurden Abstimmungsprozeduren entwickelt, die die Wahrscheinlichkeit von Fehlentscheidungen nochmals reduzieren. Zur weiteren Analyse werden die Algorithmen erstens in der Motelab-Umgebung und zweitens mit Hilfe von Simulationen untersucht. Die präsentierten Algorithmen zeigen überzeugende Ergebnisse unter variierenden Bedingungen, was ihre Anwendbarkeit in realen Szenarien unterstreicht. / Wireless multi-hop network (WMN) is a distributed communication system composed of autonomous processing nodes that is known for its ability to automatically adjust to rapidly changing conditions in the surrounding environment. Connectivity is one of the basic properties of a network. Removal of a bridge or an articulation point partitions a network. Biconnectivity testing identifies bridges and articulation points in a network, and once they are known corrective actions can be performed in order to improve network''s reliability. Numerous biconnectivity testing algorithms are successfully applied in graphs, wired networks and multiprocessor systems. However, they are inadequate for application in wireless networks since the frequent packet losses introduce uncertainty in the system which these algorithms cannot handle. The stochastic analysis shows that errors in decision-making in WMNs are considerable even for seemingly simple tasks such as the detection of links. The main contribution of this work is to provide means for accurate binary decision-making under uncertainty within the context of biconnectivity testing in WMNs. A distributed algorithm is developed that successfully handles the faults caused by message losses and simultaneously utilizes benefits of wireless communication to reduce message complexity from O(e) to O(n). Based on stochastic analysis of WMN topologies and a comprehensive analysis of impact of communication faults on algorithm''s behavior, the algorithm is extended by voting theory to reduce probability of erroneous decisions. The algorithm and the voting rules are evaluated in experiments in Motelab testbed and in the event-based simulator Jist/SWANS. The algorithm is accurate under various conditions which demonstrates its applicability in reality and capability of successful operation in presence of packet losses.

<p>With the constant development of wireless technologies, the usageof wireless devices tends to increase even more in the future.Wireless multi-hop networks (WMNs) have emerged as a keytechnology to numerous potential scenarios, ranging from disasterrecovery to wireless broadband internet access. The distributedarchitecture of WMNs enables nodes to cooperatively relay othernode's packets. Because of their advantages over other wirelessnetworks, WMNs are undergoing rapid progress and inspiringnumerous applications. However, many technical issues still existin this field. In this thesis we investigate how Voice over IP(VoIP) and peer-to-peer (P2P) application are influenced bywireless multi-hop network characteristics and how to optimizethem in order to provide scalable communication.We first consider the deployment of VoIP service in wirelessmulti-hop networks, by using the Session Initiation Protocol (SIP)architecture. Our investigation shows that the centralized SIParchitecture imposes several challenges when deployed in thedecentralized wireless multi-hop environment. We find that VoIPquality metrics are severely degraded as the traffic and number ofmultiple hops to the gateway increase. In the context ofscalability, we further propose four alternative approaches whichavoid current limitations.In the second part of this thesis we tackle the network capacityproblem while providing scalable VoIP service over wirelessmulti-hop networks. The performance evaluation shows the influenceof intra and inter-flow interference in channel utilization, whichdirect impacts the VoIP capacity. In order to avoid the small VoIPpacket overhead, we propose a new adaptive hop-by-hop packetaggregation scheme based on wireless link characteristics. Ourperformance evaluation shows that the proposed scheme can increasethe VoIP capacity by a two-fold gain.The study of peer-to-peer applicability over wireless multi-hopnetworks is another important contribution. A resource lookupapplication is realized through structured P2P overlay. We showthat due to several reasons, such as characteristics of wirelesslinks, multi-hop forwarding operation, and structured P2Pmanagement traffic aggressiveness the performance of traditionalP2P applications is rather low in wireless multi-hop environments.Therefore, we suggested that a trade-off between the P2P lookupefficiency and the P2P management traffic overhead can be achievedwhile maintaining the overlay network consistency in wirelessmulti-hop networks.</p>

Wireless communication has seen a tremendous growth in the last decades. Continuing on this trend, wireless multi-hop networks  are nowadays used or planned for use in a multitude of contexts, spanning from Internet access at home to emergency situations. The Transmission Control Protocol (TCP) provides reliable and ordered delivery of a data and is used by major Internet applications such as web browsers, email clients and file transfer programs. TCP traffic is also the dominating traffic type on the Internet. However, TCP performs less than optimal in wireless multi-hop networks due to packet reordering, low link capacity, packet loss and variable delay. In this thesis, we develop novel proposals for enhancing the network and transport layer to improve TCP performance in wireless multi-hop networks. As initial studies, we experimentally evaluate the performance of different TCP variants, with and without mobile nodes. We further evaluate the impact of multi-path routing on TCP performance and propose packet aggregation combined with aggregation aware multi-path forwarding as a means to better utilize the available bandwidth. The last contribution is a novel extension to multi-path TCP to  enable single-homed hosts to fully utilize the network capacity. / <p>Opponent changed. Prof. C. Lindeman from the University of Leipzig was substituted by Prof. Zhang.</p>

Traditional Ad Hoc network wireless communication in the past years have contributed tremendously to the dawn of wireless mesh networks (WMNs) which have so far been able to provide a significant improvement in capacity and scalability. Routing metrics which form the basic element for the routing protocol in this innovative communication technology is a call for concern as they must take into consideration the wireless medium network characteristics in order to provide a optimum appreciable QoS performance. In the past many single-radio routing metrics have been proposed for Ad Hoc networks which are not compatible with the multi-radio routing scenario demanded by WMNs. In our work, we provide a comparative analysis of most recently proposed multi-radio routing metrics for WMNs. We begin by providing an overview of the features of a wireless mesh network thereby presenting a better understanding of some of the research challenges of WMNs. Also, since single-radio routing forms the basis of multi-radio routing, we in this regard provide a review of some single-radio routing metrics. In our comparative analysis, an overview of routing protocols for WMNs is provided enabling an understanding of the demands to be included in a routing metric to ensure efficient routing in WMNs since different routing protocols may impose different demands; we then identify the requirements of multi-radio routing metrics from which we base our comparative analysis.

With the constant development of wireless technologies, the usageof wireless devices tends to increase even more in the future.Wireless multi-hop networks (WMNs) have emerged as a keytechnology to numerous potential scenarios, ranging from disasterrecovery to wireless broadband internet access. The distributedarchitecture of WMNs enables nodes to cooperatively relay othernode's packets. Because of their advantages over other wirelessnetworks, WMNs are undergoing rapid progress and inspiringnumerous applications. However, many technical issues still existin this field. In this thesis we investigate how Voice over IP(VoIP) and peer-to-peer (P2P) application are influenced bywireless multi-hop network characteristics and how to optimizethem in order to provide scalable communication.We first consider the deployment of VoIP service in wirelessmulti-hop networks, by using the Session Initiation Protocol (SIP)architecture. Our investigation shows that the centralized SIParchitecture imposes several challenges when deployed in thedecentralized wireless multi-hop environment. We find that VoIPquality metrics are severely degraded as the traffic and number ofmultiple hops to the gateway increase. In the context ofscalability, we further propose four alternative approaches whichavoid current limitations.In the second part of this thesis we tackle the network capacityproblem while providing scalable VoIP service over wirelessmulti-hop networks. The performance evaluation shows the influenceof intra and inter-flow interference in channel utilization, whichdirect impacts the VoIP capacity. In order to avoid the small VoIPpacket overhead, we propose a new adaptive hop-by-hop packetaggregation scheme based on wireless link characteristics. Ourperformance evaluation shows that the proposed scheme can increasethe VoIP capacity by a two-fold gain.The study of peer-to-peer applicability over wireless multi-hopnetworks is another important contribution. A resource lookupapplication is realized through structured P2P overlay. We showthat due to several reasons, such as characteristics of wirelesslinks, multi-hop forwarding operation, and structured P2Pmanagement traffic aggressiveness the performance of traditionalP2P applications is rather low in wireless multi-hop environments.Therefore, we suggested that a trade-off between the P2P lookupefficiency and the P2P management traffic overhead can be achievedwhile maintaining the overlay network consistency in wirelessmulti-hop networks.

Un réseau sans fil multi-saut est un ensemble d’entités mobiles et/ou fixes formant un réseau dynamique temporaire avec ou sans l’aide de toute administration centralisée. Cette particularité rend le routage problématique en cas d’instabilité des éléments qui composent les communications non directes. Afin de palier ces problèmes, de nouvelles formes de routage sont utilisées comme le routage multi-chemin (MC). Le routage MC permet d’envoyer les données sur des chemins multiples et semble être une solution efficace pour ces réseaux. Le but de cette thèse est d’étudier les techniques de routage MC dans un contexte sans fil multi-saut en vue d’obtenir de meilleures performances. Nous avons choisi pour notre étude une extension MC du protocole OLSR, appelée MP-OLSR. Nous évaluons ses performances sous divers scénarios sous NS-2. Ces tests d’évaluation nous ont amenés à mettre en ´evidence deux problèmes dans MP-OLSR : la réactivité du protocole de routage MC suite à des ruptures de route et la stratégie de répartition des données sur les chemins multiples. Nous avons étudié la réactivité de tels mécanismes dans MP-OLSR. Nous avons proposé trois nouvelles techniques de réparation de pannes qui diminuent les temps de rétablissement d’une route et réduisent le taux de perte des flux transmis. Nous proposons aussi un mécanisme qui détecte la dégradation de la qualité des liens durant le transfert d’un trafic de données. Les informations déduites de ce mécanisme servent à adapter la proportion de trafic à affecter à chaque chemin selon les conditions réseaux. Cette nouvelle variante du protocole MP-OLSR est évaluée par simulation. / Wireless multi-hop networks consist of a collection of mobile and/or fixed nodes which dynamically exchange data with (or without) reliance on a (any) centralized administration. They are by definition self-organized. The frequent topological changes make multi-hop routing a crucial issue for these networks. To overcome these problems, new forms of routing schemes are used as the multipath routing (MP). MP routing uses multiple paths to send data and can be regarded as an effective solution for these networks. The purpose of this PhD thesis is to study the MP routing techniques in a wirelessmulti-hop context for better performance. We choose for our study a MP extension of OLSR, called MP-OLSR. We evaluate its performance under various scenarios in NS-2. These tests have led us to highlight two problems in MP-OLSR : the long recovery delays when facing network failure situations and the allocation strategy of data on multiple paths. We define and seek to evaluate the latency introduced by both protocols OLSR and MP-OLSR to find a new path after a link failure. We propose three new different recovery schemes and accordingly extend these original protocols in order to decrease theexpected latency and reduce the packet loss rate of transmitted flow. We also propose a mechanism which is able to detect the deterioration of the link quality during the transfer of data traffic. The information derived from this mechanism is used to adjust the proportion of traffic to be assigned to each path according to network conditions. This new version of MP-OLSR protocol is evaluated by simulation.

La tendance à la numérisation de nombreux secteurs industriels tels que l’automobile, l’agriculture, les transports, la gestion urbaine, etc. révèle la nécessité de nouveaux usages des services de communication point-à-multipoint, tels que la fourniture massive de mises à jour logicielles et livraison fiable de messages d’alerte à la population, etc. D’un autre côté, la mise en logiciel des réseaux de nouvelle génération, avec notamment l’adoption croissante des réseaux définis par logiciel (SDN), apporte au réseau la flexibilité et les capacités de programmation permettant de prendre en charge des services de distribution point-à-multipoint de manière rentable. Cette thèse contribue au problème général de la fourniture de services de communication point-à-multipoint avec des exigences de qualité de service (QoS) dans un réseau SDN multi-domaines. Il considère également que certains des domaines sont des réseaux multi-sauts sans-fil. Tout d’abord, une technique d’agrégation de topologie de domaine basée sur une arborescence de Steiner, combinée à un algorithme heuristique d’allocation de ressources, sont proposés pour prendre en charge des services point-à-multipoint couvrant plusieurs domaines. Ensuite, un service de découverte de topologie générique est proposé pour les réseaux multi-sauts sans-fil basés sur le SDN afin de permettre au contrôleur SDN de créer et de gérer une vue complète du réseau avec divers attributs de nœud et de liaison sans-fil. Le contrôleur peut alors exposer des vues personnalisées aux applications de contrôle du réseau, telles que, par exemple, l’application en charge de la fourniture de services point-à-multipoint sur un réseau multi-sauts sans-fil basé sur le paradigme SDN. Un algorithme basé sur la programmation linéaire en nombres entiers et un algorithme génétique sont également proposés pour l’allocation de liens virtuels point-à-multipoint sur un réseau sans-fil multi-radio, multi-canaux et multi-sauts basé sur SDN. Enfin, pour traiter le cas des services dynamiques point-à-multipoint, nous proposons un schéma de réallocation de ressources qui répond aux exigences changeantes tout en réduisant les interuptions de service. / The movement towards the digitalization of many industry sectors such as automotive, agriculture, transportation, city management, etc. is revealing the need for novel usages of point-to-multipoint network delivery services, such as massive delivery of software updates to objects, secure and reliable delivery of alert messages to population, etc. On another side, the softwarization of next generation networks, with amongst, the increasing adoption of Software Defined Networks (SDN) is bringing to the network the flexibility and programming capabilities that enable the support of point-to-multipoint delivery services in an efficient and cost-effective way. This PhD work contributes to the general problem of providing point-tomultipoint delivery services with Quality of Service (QoS) requirements in a multidomain SDN network. It also considers that some of the domains are wireless multi hop networks. First, a Steiner tree based network domain topology aggregation combined with a resource allocation heuristic algorithm is proposed to support point-to-multipoint delivery services that span multiple domains. Then, a generic topology discovery service is proposed for SDN based wireless multi-hop networks to let the SDN controller build and maintain a comprehensive view of the network with various node and wireless link attributes. From there, customized views can be exposed by the controller to network control applications, as, for instance, the application in charge of provisioning point-to-multipoint services on a SDN based wireless multi-hop network. An Integer linear programming based algorithm and a genetic algorithm are also proposed for the embedding of point-to-multipoint services on a SDN based multi-radio, multi-channel and multi-hop wireless network. Last, to address the case of dynamic point-to-multipoint services, we propose a resource reallocation scheme that meets the changing requirements while reducing service disruption.