Dans les systèmes Store and Forward (S&F), le routage comme moyen d'optimisation a été largement étudie mais aucune règle générale n'a pu être établie. Des paramètres et des méthodes d'évaluation spécifiques à ces systèmes n'ont pas encore été définis. Jusqu'à présent seuls des critères appartenant aux réseaux traditionnels étaient utilises (temps, longueur de la route). Or la tolérance aux délais du réseau s&f minimise l'importance de ces critères. De ce fait, pour ces systèmes, il est nécessaire d'employer des mécanismes et des critères mieux adaptent à leurs caractéristiques. Cette étude a pour but de montrer que le routage dans les systèmes s&f peut être aborde a partir de perspectives nouvelles. Pour ce faire, nous utilisons une politique de routage pré calcule depuis la source. Nous présentons un état de l'art sur les systèmes s&f, leurs mécanismes et leurs scénarios d'application. Nous proposons un outil de calcul de routes pour un scenario de communications par satellite compose par deux constellations. Cet instrument est conçu à partir des techniques utilisées dans les systèmes de transport. Nous proposons ensuite un ensemble de nouvelles métriques pour le routage dans les systèmes s&f. Ces métriques permettent de caractériser le système s&f à partir de leur nature propre et d'établir des politiques de routage mieux adaptées à leurs conditions de fonctionnement. Enfin nous présentons les développements possibles dans cette thématique

Les réseaux de radios cognitives sont composés d'appareils cognitifs et agiles capables de changer leurs configurations à la volée en se basant sur l'environnement spectral. Cette capacité offre la possibilité de concevoir des stratégies d'accès au spectre dynamiques et flexibles dans le but d'utiliser d'une manière opportuniste une portion du spectre disponible. Toutefois, la flexibilité dans l'accès au spectre engendre une complexité accrue dans la conception des protocoles de communication. Notre travail s'intéresse au problème de routage dans les réseaux de radios cognitives à multi-sauts. Dans ce document, nous proposons un protocole de routage réactif qui permet la coexistence entre les utilisateurs premiers et secondaires, la diminution des interférences et l'augmentation du débit de transmission de bout en bout. Les simulations présentées démontrent l'efficacité de l'algorithme proposé en termes de débit moyen de bout en bout et de la gestion des chemins interrompus par l'arrivée d'un utilisateur premier. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : réseaux de radios cognitives, radio cognitive, routage réactif, multi-sauts, utilisateur premier, utilisateur secondaire.

Les réseaux à radios cognitives sont des réseaux émergeants donnant une possibilité d'accès dynamique au spectre dans le but de l'utiliser de façon plus efficace. Le problème de routage dans ce type de réseaux est assez complexe vu l'aspect dynamique et flexible d'un environnement cognitif opportuniste. Notre travail consiste à suggérer une solution de routage efficace et performante en débit et délai de transmission de bout en bout. Dans ce mémoire, nous proposons un nouveau protocole de routage réactif en s'inspirant des protocoles de routage déjà existant dans les réseaux sans fil classiques car ils présentent une grande maturité. Les simulations effectuées démontrent que l'algorithme permet d'atteindre un débit de transmission élevé avec un petit délai de transmission de bout en bout, ainsi qu'un bon maintien de chemins face à l'activation de transmission d'utilisateurs primaires. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : réseaux à radios cognitives, routage réactif, multi-interface, utilisateur primaire, utilisateur secondaire.

L'efficacité du transport des marchandises en ville est un sujet complexe préoccupant les autorités locales depuis de nombreuses années. Les enjeux sont immenses, une meilleure organisation du trafic devant permettre d'augmenter la sécurité, réduire les nuisances, minimiser les coûts. La Logistique Urbaine vise à concevoir des systèmes de distribution des marchandises en ville permettant d'acheminer les flux dans les meilleures conditions à la fois pour la communauté et les transporteurs. Cette thèse se deroule dans le cadre du projet ANR MODUM qui propose un système basé sur un anneau de Centres de Distribution Urbains (CDU) situés autour d'une ville. La première partie étudie ce système d'un point de vue stratégique et tactique. Le Multicommodity-Ring Location Routing Problem aborde les décisions concernants l'installation et la connexion en anneau des CDU en simplifiant les détails plus tactiques. Trois méthodes ont été developpées et testées sur un jeu d'instances exhaustif se révélant très efficaces. The Multicommodity-Ring Vehicle Routing Problem est le problème dérivé que l'on obtient quand l'anneau est fixé. Une approche de type Branch&Price est proposée pour ce problème. La deuxième partie porte sur le Vehicle Routing Problem with Intermediate Replenishment Facilities, un problème plus tactique qui se produit dans un système logistique lorsque les véhicules peuvent se recharger auprès des points de remplissage et effectuer plusieurs tournées lors d'une même journée. Plusieurs algorithmes exacts ont été developpés et testés. Les résultats obtenus sur des jeux d'instances tirés de la littérature sont prometteurs. / Urban freight transport is a matter of increasing concern in the economic, commercial, social and environmental operations of our cities, due to the constantly increasing growth and urbanization of the civilization. An improved managem ent of the traffic related to the freight transport can have a positive impact in many respects : security, congestion of the road network, noise and air pollution, costs. City Logistics studies the dynamic management of urban freight transport in order to deliver distribution systems solutions that may be suitable for both the community and freight carriers. This thesis originates from the ANR Project MODUM, which proposes a freight distribution system based on a ring of Urban Distribution Centers (UDCs) located in the outskirts of a city. In the first part, this system is studied from both a strategic and a tactical point of view. The Multicommodity-Ring Location Routing Problem (MRLRP) considers long-term decisions, i.e. the installation of the UDCs and the ring connection, without disregarding more tactical aspects. The MRLRP has been tackled by three solution methods, which proved effective on a large set of test instances. In the second part of the thesis, the Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) is studied. The VRPIRF is a more tactical problem that arises in City Logistics each time both the multi-trip and the multi-depot features, i.e. the possibility for a vehicle to be reloaded at one of a set of facilities, are present. Several exact algorithms, namely two of type Branch&Cut and two of type Branch& Price, have been developed for this problem. computational experiments on benchmark instances taken from the literature have been conducted to assess their performance, leading to very promising results.

Le routage dans les réseaux de capteurs, est un service essentiel qui transmet les lectures des capteurs à certains points de collecte de données dans le réseau sur la base des relais multi-saut. Cette tâche est particulièrement difficile car elle doit être réalisé d'une manière efficace au niveau de consommation de ressources et avec une quantité limitée d'informations disponible. La facilité de mise à l'échelle et l'utilisation d'information local pour fonctionner ont permis au routage géographique être considéré comme une approche prometteuse. Cependant, lors de son implémentation, certains problèmes subsistent en raison des difficultés pratiques. Dans ce travail de recherche, deux problématiques inhérentes aux protocoles de routages géographique ont été étudiés: i) Le coût associé: aux évanouissements liés aux obstacles et aux multi-trajets suivis par un signal transmis sur un canal radio, aux changements rapides des conditions physiques du canal de transmission and ii) l'administration de resources affectés à chaque noeud appartenant au réseau. Afin de résoudre ce problème, deux protocoles ont été présentés: un protocole de routage géographique avec communications coopératives, Beaconless Cooperative Geographic cross-layer protocol for ad hoc and sensor networks (CoopGeo) et un protocole de routage basé sur le principe d'extension de couverture: Relay-Aware Cooperative Routing (RACR). / In Wireless Sensor Networks, the routing task is an essential service that forwards the sensor readings to some data collection points in the network on the basis of the multi-hop relaying. The routing task is particularly challenging as it should be realized in an energy efficiency manner with limited amount of information. Geographic routing is a promising approach because of its good scalability and local information use, but when deploying such approach, some problems still remain because of some practical difficulties. In this thesis, some techniques have been explored to address two issues in geographic routing protocols: i) Cost associated to: the wireless channel impairments due to fading, mobility patterns or high dynamic environment and ii) the management of constrained resources of the nodes. To tackle these issues, two protocols were presented: a beaconless Cooperative Geographic cross-layer protocol for ad hoc and sensor networks (CoopGeo) and a Relay-Aware Cooperative Routing protocol (RACR). CoopGeo deals the wireless impairments by means of a cross-layer framework where a beaconless geographic routing approach was used to build the route not only in a local manner, but also on the y worked with a relay selection mechanism to exploit the broadcast nature of the wireless communications. The RACR protocol exploits the coverage extension as a result from node cooperation to improve the non-cooperative geographic routing. It is an alternative to scenarios where network resources like energy should be preserved while respecting a Symbol Error Rate constraint (SER).

Que le phénomène découle d’une prise de conscience des conséquences sur l’environnement, d’une opportunité économique ou d’une question de réputation et de commerce, la réduction des émissions de gaz à effets de serre est récemment devenue un objectif de premier plan. Les individus, les entreprises et les gouvernements effectuent un effort important pour réduire la dépense énergétique de multiples secteurs d’activité. Parallèlement, les technologies de l’information et de la communication sont de plus en plus présentes dans la plupart des activités humaines et l’on a estimé que 2% des émissions de gaz à effets de serre pouvaient leur être attribuées, cette proportion atteignant 10 % dans les pays fortement industrialisés [1, 2]. Si ces chiffres paraissent raisonnables aujourd’hui, ils sont certainement appelés à croître à l’avenir. À l’heure du cloud computing, les infrastructures de calcul et de communication demandent de plus en plus de performance et de disponibilité et imposent l’utilisation de matériels puissants et engendrant une consommation d’énergie importante du fait de leur fonctionnement direct, mais aussi à cause du refroidissement qu’ils nécessitent. En outre, les contraintes de disponibilité imposent une conception d’architectures redondantes et dimensionnées sur une charge crête. Les infrastructures sont donc souvent sous-utilisées et adapter leur niveau de performance à la charge effectivement constatée constitue une piste d’optimisation prometteuse à divers niveaux. Si l’on adopte un strict point de vue environnemental, l’objectif du Green Networking consiste à réduire le volume d’émissions de gaz à effets de serre dues au processus de communication. L’utilisation de sources d’énergie renouvelables ou d’électronique de faible consommation (par exemple asynchrone) constituent des pistes évidentes d’amélioration. / The reduction of power consumption in communication networks has become a key issue for both the Internet Service Providers (ISP) and the research community. Ac- cording to different studies, the power consumption of Information and Communication Technologies (ICT) varies from 2% to 10% of the worldwide power consumption [1, 2]. Moreover, the expected trends for the future predict a notably increase of the ICT power consumption, doubling its value by 2020 [2] and growing to around 30% of the worldwide electricity demand by 2030 according to business-as-usual evaluation scenarios [15]. It is therefore not surprising that researchers, manufacturers and network providers are spending significant efforts to reduce the power consumption of ICT systems from dif- ferent angles. To this extent, networking devices waste a considerable amount of power. In partic- ular, their power consumption has always been increased in the last years, coupled with the increase of the offered performance [16]. Actually, power consumption of network- ing devices scales with the installed capacity, rather than the current load [17]. Thus, for an ISP the network power consumption is practically constant, unrespectively to traffic fluctuations. However, actual traffic is subject to strong day/night oscillations [3]. Thus, many devices are underutilized, especially during off-peak hours when traffic is low. This represents a clear opportunity for saving energy, since many resources (i.e., routers and links) are powered on without being fully utilized. In this context, resource consolidation is a known paradigm for the reduction of the power consumption. It consists in having a carefully selected subset of network devices entering a low power state, and use the rest to transport the required amountof traffic.

Ce travail de thèse présente trois contributions qui portent sur le routage et la fourniture de qualité de service dans les réseaux maillés sans fil basés sur IEEE 802.11. La première contribution définit une métrique de routage qui permet de sélectionner les chemins empruntant des liens avec de bonnes performances exprimées en termes d'interférences physiques (qui causent des pertes), d'interférences logiques (qui causent des délais) et de capacité. L'évaluation de cette métrique par rapport aux principales métriques de la littérature scientifique montre une amélioration des performances du réseau. La deuxième contribution concerne l'amélioration du mécanisme de maintenance de route le plus souvent utilisé par les protocoles de routage réactifs. Ce mécanisme considère qu'une route est coupée si l'un de ses liens observe plusieurs échecs successifs de retransmission. Nos études montrent que ces échecs sont assez souvent dûs à de problèmes transitoires sur les liens (bruit, interférence etc.). Nous avons donc proposé des algorithmes de maintenance de route qui appréhendent mieux les problèmes ponctuels ou soutenus sur les liens ce qui permet de prendre une décision cohérente et réfléchie quant à la coupure d'un lien (et donc d'une route). Les études de performances montrent une amélioration conséquente des performances globales du réseau. La dernière contribution propose un cadre pour la fourniture de la Qualité de Service (garantie de bande passante) dans les réseaux maillés multi-interfaces, multi-canaux. Ce cadre intègre un protocole de routage réactif couplé à un mécanisme de contrôle d'admission et de partage de charge. Ces derniers exploitent la diversité des liens entre nSuds voisins afin d'améliorer le taux d'admission des flux avec garantie de bande passante.

Au cours des dernières années, le trafic réseau nécessitant une qualité de service (QoS) a augmenté de façon exponentielle. Dans cette thèse, notre objectif est de trouver des routages dans les réseaux câblés et sans fil en prenant en compte les contraintes liées à la QoS et en minimisant le coût de la communication. Nous nous intéressons tout d’abord à la résolution du problème du chemin multi-contraint (MCP) pour lequel un algorithme exact efficace est proposé. Cet algorithme permet d'améliorer le temps d'exécution tout en maintenant la qualité de la solution. En ce qui concerne le problème de la diffusion multipoint (multicast) multi-contraint de coût minimal (MCMCM), une nouvelle formulation utilisant la Programmation Linéaire en Nombres Entiers est proposée. Elle permet de calculer les hiérarchies optimales, structures les plus pertinentes pour résoudre de manière exacte le problème MCMCM. Un algorithme de prétraitement efficace est également conçu pour accélérer le temps de résolution dans les réseaux de grande taille. En ce qui concerne le problème du routage avec QoS dans les « Low Power et Lossy Networks » (LLN), une solution basée sur une nouvelle fonction objective est présentée. Cette solution minimisant une longueur non linéaire est la première à prendre en compte un nombre quelconque de contraintes pour le routage avec QoS. Nous avons conçu un algorithme exact et deux algorithmes de routage heuristique pour résoudre ce problème dans les réseaux LLN avec QoS. / In recent years, the network traffic requiring Quality of Service (QoS) has been growing explosively. In this thesis, we study the multi-constrained QoS routing in networks. The objective is to find routes in wired and wireless networks taking into account constraints related to the QoS and minimizing the cost of the communication. We present several propositions. To solve the Multi-Constrained Path problem (MCP), an efficient exact algorithm is proposed. This algorithm is shown to be able to improve the execution time while maintaining the quality of the solution. Concerning the Multi-Constrained Multicast Minimum Cost problem (MCMCM), a new Integer Linear Programming (ILP) formulation is proposed to compute hierarchies, which are the exact solutions for MCMCM. An efficient preprocessing-based algorithm is also designed to accelerate the resolution time in large size networks. Regarding the problem of QoS routing in Low Power and Lossy Networks (LLNs), a new Objective Function (OF)-based solution is presented. This solution uses a non-linear length function. It is the first that takes into account any number of metrics and constraints for QoS routing. We designed an exact and two heuristic routing algorithms with QoS constraints for LLNs.

Ce travail de thèse présente trois contributions qui portent sur le routage et la fourniture de qualité de service dans les réseaux maillés sans fil basés sur IEEE 802.11. La première contribution définit une métrique de routage qui permet de sélectionner les chemins empruntant des liens avec de bonnes performances exprimées en termes d’interférences physiques (qui causent des pertes), d’interférences logiques (qui causent des délais) et de capacité. L’évaluation de cette métrique par rapport aux principales métriques de la littérature scientifique montre une amélioration des performances du réseau. La deuxième contribution concerne l’amélioration du mécanisme de maintenance de route le plus souvent utilisé par les protocoles de routage réactifs. Ce mécanisme considère qu'une route est coupée si l'un de ses liens observe plusieurs échecs successifs de retransmission. Nos études montrent que ces échecs sont assez souvent dûs à de problèmes transitoires sur les liens (bruit, interférence etc.). Nous avons donc proposé des algorithmes de maintenance de route qui appréhendent mieux les problèmes ponctuels ou soutenus sur les liens ce qui permet de prendre une décision cohérente et réfléchie quant à la coupure d’un lien (et donc d'une route). Les études de performances montrent une amélioration conséquente des performances globales du réseau. La dernière contribution propose un cadre pour la fourniture de la Qualité de Service (garantie de bande passante) dans les réseaux maillés multi-interfaces, multi-canaux. Ce cadre intègre un protocole de routage réactif couplé à un mécanisme de contrôle d'admission et de partage de charge. Ces derniers exploitent la diversité des liens entre nœuds voisins afin d’améliorer le taux d’admission des flux avec garantie de bande passante / This thesis presents three contributions in the area of routing and Quality of Service for IEEE 802.11-based Wireless Mesh Networks. The first contribution defines a routing metric for the selection of route by taking into consideration the performance of wireless links in terms of physical interference (which causes packet losses), logical interference (which causes delay) and the capacity of the links. The performance evaluation of the proposed metric compared to the popular existing metrics shows an improvement in the performance of the network. The second contribution improves the route maintenance mechanism most often used by reactive routing protocols. The existing mechanism considers a route as broken if any of the links in the route experiences multiple successive transmission failures. Our study shows that the transmission failures are often caused by transient problems on the wireless link (noise, interference etc). We propose a novel mechanism of route maintenance which distinguishes between links with temporary or transient transmission problems compared to those with sustained problems in order to make a coherent decision about link breakage (and consequently route breakage). The performance evaluation shows a substantial improvement in the performance of the network. The final contribution proposes a framework for providing Quality of Service (bandwidth guarantee) in multi-radio multi-channel wireless mesh networks. The framework integrates a reactive routing protocol coupled with an admission control mechanism and load balancing. The framework exploits link diversity between neighboring nodes to improve the flow admission ratio with bandwidth guarantees

Les réseaux véhiculaires, connus sous le terme VANETs, sont des réseaux impliquant des communications entre deux ou plusieurs véhicules et éventuellement une communication avec des éléments d’infrastructure sur la route. Récemment, le concept de systèmes de transports intelligent a connu beaucoup d’intérêt. Les STI sont des systèmes utilisant les nouvelles technologies de communication sans fil appliquées au domaine du transport pour améliorer la sécurité routière, la logistique et les services d’information. Des défis majeurs ont besoin cependant d'être abordés pour offrir une communication sur la route sécurisée et fiable dans des environnements anonymes et quelquefois hostiles à la communication. Comme dans tout système de communication, les réseaux véhiculaires doivent opérer en respectant des contraintes en termes de qualité de service. Ces contraintes sont d’autant plus strictes quand il s’agit de fournir des services de sécurité sur la route. Ce projet vise à développer des techniques de communication véhiculaires pour le relayage d’informations de manière fiable et à faible délai entre véhicules voyageant à haute vitesse. Ces techniques devront permettre de respecter des contraintes temporelles sévères afin d’envisager leur utilisation dans des applications de sécurité sur la route. Pour ce faire, cette thèse proposera d’abord des techniques efficaces de dissémination d’informations utilisant des approches multi-métriques basées sur différentes mesures en temps-réel. Des méthodes de relayage seront proposées qui permettent de diminuer les délais d’acheminement et augmenter la probabilité de réception. Ces méthodes utiliseront, entre autres, des approches d’adaptation de la portée et/ou de la priorité des messages en fonction de leur type et de l’intérêt éventuels des véhicules récepteurs en la réception de ces messages. Dans un second volet, ce projet proposera des concepts et des méthodes afin de palier au problème de congestion dans les réseaux véhiculaires qui peut résulter conjointement à la dissémination d’informations. Ces concepts et méthodes viseront à respecter la fiabilité exigée par les applications de sécurité, tout en restant conforme aux nouveaux standards de communications véhiculaires.