Le Routage dans les réseaux Ad hoc

Caractéristiques des réseaux mobiles ad hoc

Un réseau mobile ad hoc est caractérisé par [RFC2501] :
• Une topologie dynamique causée d’une part par l’apparition et ladisparition fréquente des unités mobiles et d’autre part par la mobilité des noeuds (voir figure 2).
• Un déploiement rapide ne nécessitant aucune infrastructure préexistence ou de câblages.
• Une contrainte d’énergie: les noeuds du réseau sont alimentés par des sources d’énergie autonomes. Cette énergie doit être optimisée afin de relayer les messages vers d’autres mobiles lors du routage.
• Une bande passante limitée: le médium radio est partagé pour la communication sans fil entre les différentes unités mobiles.
• Une sécurité limitée: le réseau ad hoc utilise des ondes hertziennes pour la transmission des messages entre deux noeuds. Ces messages peuvent être interceptés par un tiers noeud malveillant qui se connecte au réseau.
• L’absence d’infrastructure: les réseaux ad hoc se distingue des autres réseaux mobiles par la propriété d’absence d’infrastructure préexistante. Les unités mobiles sont responsables d’établir et de maintenir la connectivite du réseau d’une manière continue. Cette caractéristique constitue un frein dans la gestion et le control du réseau surtout en ce qui concerne l’apport en qualité de service.

Routage dans les réseaux mobiles Ad hoc

Le routage est une méthode d’acheminement des informations à la bonne destination dans un réseau d’interconnexion. Le problème classique du routage consiste à déterminer un acheminement optimal des paquets de messages à travers un réseau.
Pour les réseaux ad hoc mobiles, caractérisés par une absence d’infrastructure, chaque noeud est susceptible d’être mis à contribution pour participer au routage et pour retransmettre les paquets d’un noeud qui n’est pas en mesure d’atteindre sa destination; tout noeud joue ainsi le rôle de station et de routeur [TAY]. Le problème consiste à trouver l’investissement de moindre coût en capacités nominales et de réserves qui assure le routage du trafic nominal et garantit sa surveillance en cas de n’importe quelle panne de lien ou de noeud.
Afin de maintenir la mobilité des noeuds dans un réseau ad hoc, le Groupe MANET a fait une extension des protocoles de routage de l’IP fixe :
– Inondation
– Vecteur de distance
– Routage à la source
– Etat du lien
Ainsi, deux familles ont été formées à partir de la normalisation MANET : les protocoles réactifs et les protocoles proactifs. Cette classification est basée sur la manière de création et de maintenance des routes lors de l’acheminement des données.

Les protocoles proactifs

Dans ces types de protocoles, les routes sont établies à l’avance par l’échange périodique des tables de routage. Ces tables de routage dynamiques permettent de tracer la route optimale. Ils sont basés sur la même philosophie des protocoles de routage des réseaux fixes. Les deux principales méthodes utilisées sont:
• la méthode Etat de Lien (« Link State »)
• la méthode du vecteur de Distance (« Distance Vector « )
Ces deux méthodes exigent une mise à jour périodique des données de routage qui doit être diffusée par les différents noeuds du réseau.
Nous allons décrire dans ce qui suit les protocoles les plus utilisés de cette classe.

Le protocole de routage DSDV (Destination Séquence Distance Vector)

Le protocole DSDV s’inspire du protocole RIP [RFC1058] et est basé sur l’algorithme distribué de Bellman-ford en rajoutant quelques améliorations [PER].
Chaque station mobile maintient une table de routage qui contient:
• Toutes les destinations possibles
• Le nombre de noeuds (ou de saut) nécessaire pour atteindre la destination
• Le numéro de séquence (SN: Sequence Number) qui correspond à un noeud de destination.
Le numéro de séquence est utilisé pour différencier les anciennes routes des nouvelles, ce qui évite la formation de boucle de routage (routing loop).
Pour la mise à jour des tables de routage dans une topologie qui change fréquemment, chaque noeud transmet périodiquement sa table de routage à ces voisins directs. La mise à jour dépend donc de deux paramètres : Le temps, c’est à dire la période de transmission, et es événements (ou les déclencheurs). La
mise à jour doit permettre à une unité mobile de pouvoir localiser, dans la plupart
des cas, une autre unité du réseau.
• Un paquet de mise à jour contient :
– Le nouveau numéro de séquence incrémenté, du noeud émetteur.
• Et pour chaque nouvelle route :
– L’adresse de la destination.
– Le nombre de noeuds (ou de sauts) séparant le noeud de la destination.
– Le numéro de séquence (des données reçues de la destination) tel qu’il a été estampillé par la destination.
Le protocole DSDV a permis d’éliminer les problèmes de boucle de routage et de « counting to infinity » (inexistence de mécanisme pour déterminer quand est ce que le réseau doit arrêter l’incrémentation de la distance qui correspond à une destination donnée).
Le principal défaut de DSDV réside dans la convergence des tables de routage.
Ce problème est causé par deux raisons, d’une part par la non synchronisation des échanges de vecteur de distance, et d’autre part par le fait qu’une route moins couteuse est remplacée dans la table de routage par une route plus couteuse, si et seulement si, le noeud ayant publié les deux routes est la même.
En outre, le protocole DSDV utilise une mise à jour périodique et basée sur les événements, ce qui cause un contrôle excessif dans la communication.

Le protocole de routage OLSR (Optimized Link State Routing Protocol)

Le protocole OLSR [RFC 3626] a été proposé afin de résoudre le problème de convergence des tables de routage. Il se base sur le protocole de routage OSPF (Open Shortest Path First) des réseaux filaires. Cette classe de protocole se distingue par le fait que les noeuds collectent des informations par rapport à l’état des liens. Pour le protocole OLSR, cette collecte d’informations sur l’état des liens dans le voisinage est réalisée par chaque noeud grâce aux messages HELLO diffusés périodiquement par les 1-voisins (c’est-à-dire les voisins à un saut).
Ces messages contiennent :
• la liste des noeuds avec lesquels l’émetteur a des liens bidirectionnels,
• la liste des noeuds que l’émetteur peut entendre (ils entretiennent un lien unidirectionnel vers lui),
• la liste des noeuds que l’émetteur a choisis comme MPR.
Afin de disséminer ces informations, le protocole OLSR définit un sousensemble C de noeuds appelés relais-multi-points (MPR Multi Point Relay) qui est responsables de la diffusion des messages de contrôle. Ce sous-ensemble C est sélectionné par chaque noeud i parmi les 1-voisins de telle sorte que C couvre tous les noeuds pouvant être atteints en deux sauts par i. chaque noeud annonce périodiquement à ses voisins, les noeuds qui a été désignés comme MPRs, lesquels sont responsables de la diffusion dans le réseau de l’état des liens avec les noeuds voisins.
La diffusion de ces messages HELLO permet aux noeuds du réseau de stocker, dans leur table des voisins, une vision à deux sauts de leur voisinage et de calculer l’ensemble de leurs MPR. Cet ensemble est recalculé dès qu’un changement est détecté dans le voisinage à deux sauts.
La diffusion sur la totalité du réseau (via les MPR) de messages de contrôle de topologie (TC messages1) donne l’information topologique nécessaire au routage. Ces messages contiennent, pour chaque MPR, la liste des noeuds qui l’ont choisi. Grâce à ces messages, les noeuds peuvent maintenir une table de topologie, indiquant le dernier saut pour chaque destination.

Les protocoles réactifs

Les protocoles de routage réactifs créent les tables de routage à la demande. Ainsi, ils génèrent à priori moins de message de contrôle que les protocoles proactifs. Lorsqu’un noeud désire transmettre, une procédure de découverte de route est lancée vers la destination. Le processus de recherche de route se décompose en deux étapes: la première correspond à la diffusion d’une requête de localisation de la destination, la deuxième consiste à collecter les réponses. Plusieurs protocoles ont été proposés selon différents contextes. Nous allons décrire dans ce qui suit quelques protocoles proactifs.

Le protocole de routage DSR (Dynamic Source Routing)

Le protocole DSR est basé sur la technique du routage à la source. La question principale est comment obtenir un itinéraire de la source pour une certaine destination. La procédure de recherche est déclenchée lorsque la source désire transmettre vers une destination pour laquelle elle ne détient pas de route valide [RFC 4728], [DSR].
L’opération de découverte de routes, permet à n’importe quel noeud du réseau ad hoc de découvrir dynamiquement un chemin vers un noeud quelconque du réseau. Un hôte initiateur de l’opération de découverte, diffuse un paquet requête de route (Route Request) qui identifie l’hôte cible (la destination).
Si l’opération de découverte est réussie, l’hôte initiateur reçoit un paquet réponse de route (Route Replay) qui liste la séquence de noeuds à travers lesquels la destination peut être atteinte. En plus de l’adresse de l’initiateur, le paquet requête de route contient un champ enregistrement de route, dans lequel est accumulée la séquence des noeuds visités durant la propagation de la requête de route dans le réseau (voir la figure 4 (1)). Le paquet requête de route, contient aussi un identificateur unique de la requête. Dans le but de détecter les duplications de réceptions de la requête de route, chaque noeud maintient une liste de couples [adresse source, identificateur de requête], des requêtes récemment reçues.

La maintenance de route

La seconde phase de l’algorithme est appelée maintenance de route. Elle est responsable de l’amélioration des routes pendant la communication. Le protocole ARA n’a pas besoin d’aucun paquet spécial pour cette tache. Une fois que les FANT et BANT établissent les chemins de phéromone entre la source et les destinations, les paquets de données « transmis » sont utilisés pour assurer la maintenance. Par analogie à la nature, les chemins établis ne gardent pas leurs valeurs de phéromone de façons permanentes. Quand un noeud Vi relaie un paquet de données vers la destination à un noeud voisin Vj, ARA incrémente la valeur de phéromone de l’entrée (Vd, Vj, φ) par Δφ c’est-à-dire le chemin vers la destination est renforcé par les données de paquets.

La phase de détection des erreurs de route

La troisième et dernière phase du protocole ARA est la détection des erreurs de route qui sont principalement causés par la mobilité des noeuds et sont donc très fréquents dans les réseaux ad hoc. L’implémentation d’ARA intègre la fonction IEEE 802.11 [BRE] de la couche MAC. Ceci permet à ARA de détecter les erreurs de routes grâce à la non réception d’accusés (acknowledgement) sur la couche MAC. Si un noeud reçoit un message de ROUTE_ERROR pour un certain lien, il enregistre d’abord ce lien en mettant la valeur de phéromone à 0. Plus tard, le noeud recherche un lien alternatif dans sa table de routage. S’il y a un autre itinéraire à la destination elle enverra le paquet par l’intermédiaire de ce chemin. Autrement, le noeud informe ses voisins, espérant qu’ils pourront expédier le paquet vers la destination. Si le paquet n’atteint pas la destination, le noeud de source doit lancer un nouveau procédé de découverte d’itinéraire.