Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Routage dans les réseaux sans fil multi-sauts
Par nature, le routage dans les réseaux sans fil multi-sauts se base sur des algorithmes distribués. Étant donné que le déploiement de ce type de réseaux ne nécessite pas l’installation d’une infrastructure centralisée, chaque noeud le composant partage les mêmes rôles de relai et d’utilisateur. S’il existe aujourd’hui des méthodes pour perpage mettre de déployer facilement des applications centralisées telles que les réseaux virtuels type « overlay » ou SDN (Software Defined Networks) [3, 4], ces approches nécessitent une connaissance globale du réseau qu’il est difficile de fournir sans dégrader la capacité de ce dernier. En effet, chaque changement de l’état du réseau (topologie, trafic, interférence, …) nécessite l’envoi d’une information de mise à jour au contrôleur central qui recalculera ensuite les informations de routage à diffuser en retour à l’ensemble du réseau.
Pour éviter ce problème, les algorithmes de routage distribués implémentent des protocoles « légers » en termes de messages envoyés et placent le calcul des tables de routage au sein de chaque noeud. Nous pouvons distinguer deux types d’algorithmes de routage distribués :
Routage réactif Un noeud initie l’algorithme de calcul des routes au moment où il a un paquet à envoyer vers une destination pour laquelle il ne connait pas encore de chemin. Ce type de protocole dispose d’un coût en message extrêmement réduit et s’avère très efficace quand il est utilisé dans des réseaux de grande taille. En revanche, le délai induit par le calcul des routes rend ce type d’algorithme inefficace, en particulier lorsque sont considérées des applications pour lesquelles le délai est un critère de Qualité de Service (QoS).
Routage proactif Un noeud va régulièrement actualiser ses informations de routage en fonction des messages de mise à jour qui lui sont adressés par ses voisins. Ainsi, lorsqu’un noeud souhaite envoyer un paquet à une destination, la route est déjà connue et permet de résoudre le problème de délai des protocoles de routage réactifs. Toutefois, cette amélioration a un coût non négligeable en termes de transmissions de données. En effet, la plupart de ces protocoles utilisent des algorithmes de découverte de topologie afin de permettre aux noeuds de construire localement une topologie du réseau, complète ou partielle, à partir de laquelle ils peuvent calculer les routes vers tous les autres noeuds. Ces protocoles sont généralement efficaces pour des réseaux denses et permettent aux noeuds d’avoir une vision de l’état actuel du réseau.
Protocoles de routage réactifs
Dynamic Source Routing [5] (DSR) et Ad hoc On-Demand Distance Vector [6] (AODV) Routing sont les deux principaux protocoles de routage réactifs et représentent deux approches de routage différentes. DSR applique du routage à la source.
Plus précisément, le noeud source (le noeud souhaitant envoyer des données) fixe le chemin à suivre pour atteindre la destination (le noeud devant recevoir les données).
AODV, en revanche, utilise une table de routage. Cette table permet à un noeud souhaitant envoyer ou devant retransmettre des données vers une destination, de savoir le voisin vers lequel les transférer afin d’atteindre le noeud cible. Ce voisin est couramment appelé le prochain saut à suivre pour atteindre une destination donnée. Dans le cas où les informations de routage (chemin complet ou prochain saut) sont inconnues, la source initie un algorithme de découverte de chemin vers sa destination. Cet algorithme est similaire pour les deux protocoles. L’initiation de l’algorithme se fait par la diffusion d’un message de type Route Request (RREQ). Lorsque qu’un noeud reçoit un RREQ pour une destination en particulier, si ce noeud n’est pas la destination, alors il insère dans le message son identifiant afin de mettre à jour le chemin déjà parcouru par le paquet et le retransmettre à tous ses voisins. Lorsque la destination reçoit un RREQ, elle renvoie un message de réponse (RREP) vers la source, qui suit le chemin inverse du RREQ. Durant cette étape, les noeuds font suivre le RREP jusqu’à la source afin qu’elle puisse sauvegarder le chemin découvert. Avec AODV, les noeuds vont, en plus de retransmettre le RREP jusqu’à la source, inspecter le chemin contenu dans le message afin de remplir leur table de routage avec le prochain saut vers la destination. Enfin, pour chacun des noeuds, des mécanismes permettent de sélectionner le plus court chemin.
Si ces algorithmes sont efficaces pour calculer les meilleurs chemins reliant deux noeuds, il n’ont toutefois pas été définis en considérant la consommation énergétique et ne sont donc pas adaptés à des réseaux où ce critère est important.
C’est pourquoi des extensions ont été proposées pour ces protocoles afin de leur apporter des fonctionnalités en termes de consommation d’énergie. Dans [7], l’état énergétique d’un noeud permet de changer son comportement vis-à-vis du routage. Les auteurs définissent dans AODV trois états dans lesquels un noeud peut se trouver en fonction de son énergie résiduelle (charge restante). Un noeud est considéré comme étant dans un état normal si son énergie résiduelle est au-dessus d’un seuil prédéfini.
Sinon, le noeud est dans un état d’alerte, voire dans un état de danger si son énergie résiduelle passe sous un seuil critique.
Dans l’état normal, le noeud va suivre classiquement les spécifications de AODV.
Dans l’état d’alerte, le noeud va ajouter un délai avant de faire suivre les RREQs, de sorte que les chemins passants par ce noeud deviennent moins intéressants dans l’estimation des meilleurs chemins.
Dans l’état de danger, les RREQs sont bloqués afin de retirer ce noeud des potentiels relais du réseau.
Un mécanisme de Duty Cycle, qui sera présenté dans la partie 2.3.1, permet également d’éteindre temporairement les interfaces réseau des noeuds non utilisés pour une meilleure économie d’énergie. Dans [8], la durée de vie du réseau est améliorée par une sélection des chemins en fonction du délai de bout-en-bout et de la consommation énergétique. Plus précisément, le protocole AODV est modifié de sorte que la destination attende de recevoir plusieurs RREQs avant d’envoyer un RREP le long du chemin sélectionné. La durée de vie d’un chemin est calculée en fonction de l’énergie résiduelle minimale parmi les noeuds du chemin. En utilisant la valeur d’énergie résiduelle des noeuds, la notion de drain d’énergie des noeuds et l’estimation de la durée des sessions de flux, il est possible de sélectionner les chemins les plus à même de satisfaire dans leur totalité les flux entrants dans le réseau [9]. Une procédure proactive permet également d’éviter la rupture de la communication entre la source et la destination en calculant un chemin alternatif lorsque l’énergie résiduelle d’un noeud devient faible.
Cette approche montre des améliorations en termes de durée de vie du réseau et de QoS. Dans [10], la solution proposée intègre du contrôle de puissance de transmission avec des considérations énergétiques dans le protocole AODV. La destination répond de manière systématique à chaque RREQ et étend les messages RREPs avec un champ contenant l’énergie résiduelle des noeuds intermédiaires afin de sélectionner le chemin ayant la meilleure autonomie. Le contrôle de puissance intervient au niveau des noeuds intermédiaires au moment de faire suivre un paquet au prochain saut. Lorsqu’un noeud reçoit un paquet, il calcule la puissance de réception de ce dernier et renvoie cette valeur à l’émetteur pour que celui-ci puisse ajuster sa puissance de transmission en conséquence pour tous les autres paquets à suivre. Enfin, dans [11], les auteurs définissent une méthode d’optimisation bi-objectif afin de calculer une métrique de routage en fonction de la stabilité des routes et de l’énergie résiduelle des noeuds. De nouveau, cette approche vise à améliorer la durée de vie du réseau tout en fournissant des améliorations en termes de stabilité et de taux de paquets délivrés, ou PDR (Packet Delivery Ratio).
Concernant les travaux d’extension du protocole DSR, nous pouvons citer la solution proposée dans [12], qui utilise une approche similaire à [7] où les noeuds ayant une énergie résiduelle faible vont commencer à ajouter du délai dans la retransmission des RREPs. Cette approche a toutefois la particularité de rendre ce délai inversement proportionnel à la durée de vie estimée du noeud. Ainsi, plus l’énergie résiduelle d’un noeud diminue, plus le délai augmente, rendant les chemins passant par ce noeud inpage appropriés pour l’algorithme de routage. Toujours en se basant sur l’énergie résiduelle des noeuds, [13] propose une solution améliorant la durée de vie du réseau, les délais de bout-en-bout et la dissipation énergétique (le partage équitable de la consommation d’énergie entre les noeuds). Dans [14], les auteurs proposent un système de contrôle d’admission des flux se basant sur l’énergie et considèrent la possibilité pour les noeuds d’avoir accès à un système de recharge de batterie (panneau solaire, générateur hydraulique, …). Bien que ce travail soit présenté avec une application dans DSR, la métrique qui en résulte peut aussi être intégrée à des algorithmes de routage proactifs.
Enfin, [15] propose une extension s’appuyant sur une approche multi-chemins de DSR, en considérant l’énergie résiduelle des noeuds et leur taux de drain énergétique pour calculer les deux routes disjointes ayant la durée de vie la plus élevée.
Protocoles de routage proactifs
Le protocole Optimized Link State Routing [16] (OLSR) est l’un des protocoles de routage proactifs les plus populaires. Ce protocole définit plusieurs messages qui sont régulièrement diffusés dans le réseau afin de réaliser des tâches de découverte de topologie.
L’algorithme de diffusion est amélioré grâce à l’utilisation de Relais Multi-Points (MPR), seuls noeuds autorisés à faire suivre des paquets durant les phases de diffusion.
Les MPRs sont élus par les autres noeuds afin de leur permettre d’atteindre leur voisinage à deux sauts. Les messages HELLO et TC (Topology Control) sont les deux principaux messages nécessaires au protocole pour que les noeuds puissent calculer leur table de routage. Ainsi, chaque noeud diffuse pédiodiquement un message HELLO afin de notifier sa présence à ses voisins. Ces messages ne sont jamais retransmis au-delà du voisinage à un saut du noeud émetteur. Ils permettent de signaler les liens et de savoir s’ils sont ou non bidirectionnels. Un noeud recevant un message HELLO peut avoir une connaissance de son voisinage à deux sauts et de la nature des transmissions possibles avec ce dernier. Les messages TC sont des messages d’état de liaison, générés et diffusés par les MPRs afin d’informer l’ensemble du réseau de l’existence de leurs liens symétriques avec leurs voisins à un saut. Les noeuds recevant ces messages peuvent
alors (re)construire un graphe partiel de la topologie du réseau et calculer leur table de routage vers les destinations connues. Mais comme pour AODV et DSR, la spécification initiale du protocole OLSR ne prend pas en compte les aspects énergétiques du réseau.
Cependant, le protocole OLSR est conçu pour permettre l’intégration d’extensions.
Ainsi, il est proposé dans [17] de router des flux avec des critères de QoS, en définissant un nouveau type de MPRs (nommés QMPRs). La solution étend les messages HELLO et TC en ajoutant un label de QoS (bande passante disponible, délai, puissance de transmission, taux de perte, consommation énergétique, etc.) aux liens annoncés. Bien que les routes puissent ensuite être calculées de sorte à améliorer la qualité de service, cette spécification n’encourage pas l’économie d’énergie. Dans [18], les auteurs proposent une métrique se basant sur l’énergie résiduelle des noeuds et leur consommation pour modifier l’algorithme de sélection des MPRs. Puisque les MPRs servent de relais lors de la transmission des paquets, cette méthode tend à sélectionner des relais proposant une plus grande durée de vie. Un processus permet également aux noeuds de détecter les transmissions unicast qui ne leur sont pas destinées et d’éteindre leur interface réseau afin d’éviter de consommer l’énergie induite par la réception et le traitement de ces transmissions indésirables. Enfin, l’algorithme de routage permet de sélectionner les chemins offrant un coût énergétique minimal. Les fonctions de coût utilisées en général dans les réseaux impliquent les métriques MTPR (Maximum Transmission Power Routing) [19], MMBCR (Max-Min Battery Cost Routing) [20] et MDR (Minimum Drain Rate) [21].
Les résultats présentés montrent de bonnes performances vis-à-vis de la durée de vie du réseau, mais ne donnent rien concernant la consommation énergétique globale du réseau. Dans [22], les auteurs proposent de sélectionner les MPRs en fonction de la valeur réelle de l’énergie résiduelle et calculent les chemins en ayant le maximum. Cette approche permet une modeste amélioration en termes de PDR mais n’apporte aucune conclusion sur la consommation énergétique. Dans [23], les auteurs associent l’énergie résiduelle et la consommation énergétique des transmissions afin d’estimer la réserve d’énergie des noeuds dans le futur proche. Mais les résultats obtenus, qui montrent une amélioration vis-à-vis de la consommation énergétique en fonction de la mobilité (vitesse de déplacement des noeuds), ignorent l’impact de cette dernière sur le calcul des routes. La mobilité pouvant détruire des routes, des messages peuvent ne plus avoir de chemin à suivre et le nombre de transmissions dans le réseau se voit réduit significativement.
En 2014, [24] propose une nouvelle version du protocole OLSR. OLSRv2 dispose désormais de deux types de MPRs. Les uns permettent d’optimiser les phases de diffusion des paquets pour les besoins du protocole (plan de contrôle), les autres servent à définir la topologie à utiliser pour les communications des applications (plan de données). Cette extension intègre également nativement la possibilité de diffuser des métriques, standardisant ainsi leur utilisation dans le protocole. Enfin, il est proposé dans [25] de combiner OLSR à une méthode de clustering en utilisant des métriques basées sur l’énergie. Toutefois, les résultats ignorent aussi l’aspect énergétique du réseau pour se concentrer sur les performances de clustering de l’algorithme présenté, en fonction de la mobilité du réseau.
Contrôle de topologie
Le contrôle de topologie est un domaine largement étudié dans le but de réduire les interférences, améliorer les performances ou encore réduire la consommation énergétique des réseaux. Dans ce dernier cas, les travaux existants visent généralement à augmenter la durée de vie des réseaux de capteurs. Ainsi, [26] propose une solution permettant de réduire le coût énergétique des transmissions des paquets dans les réseaux de capteurs. Les noeuds créent de manière distribuée une topologie de sorte que leurs voisins directs soient atteignables avec une puissance de transmission minimale. La métrique MTPR [19] est utilisée pour le calcul des routes et un protocole de type Duty Cycle permet de réduire davantage la consommation énergétique des noeuds. Toutefois, cette solution se base sur la position géographique des noeuds pour établir la topologie du réseau, ce qui la rend moins intéressante pour des réseaux mobiles.
Dans [27], les noeuds sont configurés pour utiliser un ensemble fini de puissances de transmission et calculent la topologie correspondant à la puissance de transmission minimale commune à tous. Pour mettre en oeuvre cette solution, les noeuds doivent donc calculer toutes les topologies relatives aux différentes puissances de transmission disponibles, ce qui nécessite beaucoup de ressources. Dans [28], il est proposé de construire des clusters de noeuds connectés par un connected dominating set (CDS) [29], afin de créer un réseau coeur (backbone). Les noeuds peuvent ensuite choisir de rejoindre le backbone du réseau ou de se mettre en mode veille jusqu’à ce qu’ils aient des données à transmettre. Une fonction de rotation permet de changer les noeuds qui composent le backbone et ainsi améliorer la dissipation d’énergie du réseau.
Une autre approche utilisant des clusters de noeuds est introduite dans [30]. Ici, les noeuds n’élisent pas de leader (clusterhead) ou de passerelle. Ils sélectionnent une puissance de transmission qui est ensuite utilisée pour les communications intra-cluster.
Le routage est alors calculé en utilisant la métrique MTPR. Enfin, dans [31], les auteurs considèrent que les noeuds peuvent modifier dynamiquement leur puissance de transmission afin de changer la topologie du réseau à la demande. Ils utilisent des informations de trafic (demandes des flux) et un modèle d’interférence à N-sauts pour maximiser le taux d’acceptation des flux. Les résultats montrent de très bonnes performances en termes de charge et de débit, mais ne considèrent pas la consommation énergétique.
Extinction des noeuds
Éteindre un appareil électronique est un moyen simple et efficace de réduire sa consommation énergétique. Pour les noeuds des réseaux sans fil multi-sauts, cette approche est défendue par un modèle énergétique se basant sur des états énergétiques [1, 2]. Un noeud, ou son interface réseau sans fil, peut être dans plusieurs états d’activité différents au cours du temps, chacun ayant son propre niveau de consommation.
Dans les réseaux, quatre états énergétiques sont généralement utilisés, à savoir :
Mode Transmission (Tx) Un noeud est dans cet état lorsqu’il transmet des paquets. Il s’agit classiquement de l’état dans lequel le noeud consomme le plus.
Mode Réception (Rx) Pour un noeud, cet état est synonyme de réception d’un paquet qui lui est destiné. La consommation est considérée plus faible que dans l’état précédent, le noeud étant un peu plus passif, malgré l’activation des circuits pour décoder le paquet et envoyer les données à la couche applicative.
Mode Attente (Idle) Il s’agit généralement de l’état dans lequel un noeud passe le plus de temps, c’est-à-dire lorsque qu’il ne transmet ni ne réceptionne de paquet. Le noeud est en attente d’avoir des données à envoyer ou à recevoir.
Mode veille (Sleep) C’est l’état dans lequel un noeud consomme le moins d’énergie. En mode veille, il ne peut ni transmettre ni recevoir de données, ni même détecter l’arrivée d’un nouveau paquet. Cet état ne peut être quitté qu’en réponse à un signal de réveil (interruption utilisateur ou algorithmique).
L’objectif des méthodes d’économie d’énergie Duty Cycle [32] est de maximiser le temps que passe un noeud dans l’état Sleep tout en réduisant la dégradation de la QoS du réseau. En effet, plus un noeud passe de temps dans cet état, plus sa consommation moyenne diminue, mais moins il est réactif aux sollicitations du réseau (changements topologiques, transmissions de données, etc.).
De récents et intéressants travaux proposent de résoudre ce problème en intégrant dans les noeuds deux interfaces différentes de communication sans fil. Les systèmes Wake Up Radio (WuR) [33] associent une antenne de communication sans fil « classique », assurant la transmission des données dans le réseau, à une seconde fonctionnant à très faible puissance et ayant une capacité de transfert très faible. Cette seconde interface sans fil est utilisée par les noeuds pour envoyer un signal de réveil à leurs voisins en veille. Cette approche offre ainsi un bon compromis entre le mode Idle qui consomme davantage et le mode Sleep qui manque de réactivité. Elle reste cependant contraignante à mettre en place.
|
Table des matières
1 Introduction
1.1 Contexte
1.2 Contributions
1.3 Organisation du document
2 État de l’art
2.1 Routage dans les réseaux sans fil multi-sauts
2.1.1 Protocoles de routage réactifs
2.1.2 Protocoles de routage proactifs
2.2 Contrôle de topologie
2.3 Extinction des noeuds
2.3.1 Duty Cycle
2.3.2 Systèmes Wake Up Radio (WuR)
2.4 Agrégation
2.5 Conclusion
3 Agrégation de flux
3.1 Notations et modèle de réseau étudié
3.1.1 Topologie de réseau
3.1.2 Modèle d’interférences
3.2 Programmation linéaire en nombres entiers
3.2.1 Présentation
3.2.2 Un exemple
3.2.3 Modélisation d’un problème de routage – Cas du plus court chemin (ILP)
3.3 Minimisation de la consommation énergétique
3.3.1 Modèle énergétique proposé
3.3.2 Programme d’optimisation – Minimisation de l’énergie (MinEnergy)
3.3.3 Simulation et résultats numériques
Outils de simulation
Paramètres et scénarii de simulation
Mesures
Résultats de simulations
3.4 Minimisation du nombre de noeuds actifs
3.4.1 Programme d’optimisation – Routage avec Agrégation de flux (RA) 41
3.4.2 Résultats de simulation
3.5 Codage Réseau
3.5.1 Introduction au codage réseau
3.5.2 Application à l’agrégation de flux (RANC et RA+NC)
3.5.3 Résultats des simulations
3.6 Conclusion
4 Métrique d’agrégation de flux : FAME
4.1 Métrique d’agrégation de Flux : FAME
4.1.1 Intuition
4.1.2 Noeuds d’intérêt
4.1.3 Calcul de la métrique
4.1.4 Résultats de simulation
4.2 Prise en compte des interférences
4.2.1 Le problème des cliques
4.2.2 Approximation des cliques
4.2.3 Métrique d’agrégation de flux adaptative : A-FAME Hyperparamètre : seuil de réduction et base d’agrégation
4.2.4 Résultats de simulation
4.3 Conclusion
5 Application
5.1 Rappel sur le protocole de routage OLSR
5.2 OLSR avec agrégation de flux (A-OLSR)
5.3 Simulations
5.3.1 Network Simulator 3
5.3.2 Simulations et résultats numériques
Nouvelles mesures
Résultats
5.4 Conclusion
6 Conclusion et Perspectives
Publications
Télécharger le rapport complet
