Routage dans les VANETs

Routage dans les VANETs

L e routage des données permet d’assurer un relayage efficace des paquets vers la destination. Ainsi, déterminer le meilleur chemin et le maintenir se présente comme un processus assez complexe dans les réseaux VANETs. Cela est dˆu à la mobilité élevée des véhicules et les changements rapides de la topologie. Par conséquent, le choix d’un chemin devient crucial pour la conception des protocoles de routage de ces réseaux à forte dynamicité. Cependant, le routage reste l’un des principaux défis auquel il faut faire face. Dans ce chapitre, nous allons présenter en premier, les métriques de performance utilisées dans la sélection des routes dans les réseaux VANETs. Par la suite, nous exposerons une classification des protocoles de routage con¸cus ou réadaptés aux VANETs, tout en présentant certains protocoles de chaque classe. Enfin, nous allons comparer les protocoles examinés selon les métriques définies précédemment. 2.2 Métriques de choix des routes dans les VANETs L’acheminement des paquets d’une source vers une destination peut se faire de deux fa¸cons distinctes ; directement avec un seul saut si la source et la destination sont connectées directement l’une avec l’autre. Sinon, par étapes avec plusieurs sauts (multi-saut). Dans ce cas, la communication se fait via des nœuds intermédiaires positionnés entre la source et la destination. Lors d’une communication multi-saut, le chemin est choisi en fonction de divers facteurs [48] tels que : ˆ Le taux de livraison des paquets (Packet Delivery Ratio, PDR) : c’est le rapport entre le nombre total des paquets de données re¸cus par les nœuds destinations et le nombre total de paquets de données émis par les nœuds sources. ˆ Le cout du routage normalisé (Normalized Routing Load, NRL) : c’est le rapport entre le nombre total de tous les paquets de contrˆole de routage envoyés par tous les nœuds sur le nombre de paquets de données re¸cus aux nœuds de destination. ˆ La latence : c’est le temps écoulé entre le moment o`u un paquet de donnée est envoyé et celui o`u il est re¸cu par le destinataire correspondant.ˆ La bande passante : c’est le volume des paquets de données qui peut être transféré d’un nœud émetteur à un autre récepteur. Généralement, elle s’exprime sous la forme d’un débit binaire mesuré en bits par seconde (bps). ˆ La gigue : c’est la différence du délai de deux paquets successivement re¸cus.

Classification des protocoles de routage dans les VANETs 

le routage dans les VANETs à fait l’objet de plusieurs travaux dans la littérature .Dans le reste de cette section nous présentons une classification des protocoles proposées pour les réseaux VANETs tirée de [45], tout en examinant les caractéristiques principales de chaque classe. Cependant, les protocoles de routage peuvent être classés en trois grandes familles (voir la figure 2.1). ☞ Selon la stratégie du routage (proactif, réactif, hybrid). ☞ Selon le type du routage (Unicast, multicast (géocast), broadcast). ☞ Selon la structure du réseau (protocoles basés position, protocoles basés clustering). 

Selon la stratégie du routage

 Les protocoles de routage de cette famille utilisent les informations sur les liens qui existent entre les nœuds pour l’acheminement des paquets. Cette famille de protocoles peut être divisée en trois classes : proactifs, réactifs et hybrid. 

Protocoles de routage proactifs 

Les protocoles proactifs   sont similaires aux protocoles utilisés dans les réseaux filaires, qui utilisent les deux principales méthodes (état de lien et vecteur de distance).Chaque nœud garde une image globale de la topologie de tout le réseau dans une forme de tableaux. Ces derniers contiennent des informations concernant toutes les destinataires. Un nœud fait un échange périodique de messages de contrˆoles avec les autres nœuds pour maintenir ces tables de routage à jour. A base de ces tables il détermine le meilleur chemin ou route pour acheminer ` les données. Dans ce type de protocoles, la disponibilité immédiate de route lors du besoin est un gain de temps ; chaque nœud dispose à tout instant d’un chemin vers n’importe quel autre nœud du réseau. Cependant, la bande passante se diminue à cause du trafic généré par l’échange de paquets de contrˆoles. Parmi les protocoles basés sur ce principe : OLSR, FSR et GSRP [24]. Nous allons décrire dans ce qui suit l’un des protocoles les plus cité de cette classe : ☞ Le protocole OLSR (Optimized Link State Routing) OLSR [23] est un protocole de routage proactif à état de lien. Il offre des routes optimales en termes de nombre de sauts dans le réseau. Dans un protocole à état de lien chaque nœud déclare ses liens directs avec ses voisins à tout le réseau. Cependant, dans le protocole OLSR, les nœuds ne déclarent qu’une sous partie de leur voisinage. L’ensemble des voisins s’appelle l’ensemble de relais multipoint ou MPRs (Multi Point Relaying). Les routes sont construites à base de ces relais qui sont utilisés pour minimiser le trafic dˆu à la diffusion des messages de contrˆole dans le réseau. Au fait, le protocole OLSR effectue deux actions principales : ˆ Envoyer le message HELLO et déterminer les MPRs pour la détection de voisinage(voir la figure 2.2). ˆ L’intervention des messages TC (diffuser les informations de topologie), MID (pour publier la liste des interfaces de chaque nœud) et HNA (pour déclarer les sous-réseaux et hˆotes joignables par un nœud jouant le rˆole de passerelle) pour la gestion de topologie. 

Les protocoles de routage réactifs (on-demand driven) 

Dans les protocoles réactifs, le chemin n’est calculé que sur demande. L’opération de routage dans ce protocole comporte deux phases principales : ˆ La découverte de route pour l’acheminement de données vers une destination ; cette étape est assurée par la diffusion d’un message de recherche de route. ˆ La maintenance des routes existantes dans le cas de changement de la topologie du réseau. Le routage réactif minimise l’échange de messages de contrˆole ce qui lib`ere la bande passante. A l’instar les protocoles proactifs, la latence de recherche d’itinéraire est élevée dans ce type de routage. Parmi les protocoles les plus connus, on peut citer : DSR, AODV et TORA [28]. Dans le reste de ce paragraphe,nous allons décrire les protocoles AODV et DSR. ☞ Le protocole AODV (Ad-hoc On-Demand Distance Vector Routing) Le protocole AODV [27] est l’un des plus cél`ebres protocoles de routage réactifs. Les chemins sont découverts et maintenus à la demande. Lorsqu’un nœud émetteur souhaite envoyer des données à un nœud destinataire, la premi`ere étape consiste à diffuser à tous les nœuds du réseau un message RREQ (Route REQuest) de découverte de route. Par conséquent, lors de la réception d’un message RREQ, chaque nœud agit en fonction des cas de figure suivants : — Si il n’est pas le destinataire, alors le nœud retransmet le message RREQ en ajoutant sa propre adresse dans le chemin de routage. — Si il n’est pas le destinataire et si le message RREQ contient déjà sa propre adresse dans le chemin de routage, alors le nœud élimine le message sans le transmettre. — Si il est le destinataire, alors le nœud renvoie un message RREP (route reply) en suivant le chemin de routage contenu dans le message RREQ. — Au fait , le message RREP est le message de confirmation d’établissement d’une connexion entre émetteur et récepteur. D`es que l’émetteur re¸coit ce message, la communication peut commencer. — Ne re¸coit aucune réponse dans une période de temps donné, il supposera que le chemin n’est pas disponible. ☞ Le protocole DSR (Dynamic Source Routing) Le protocole DSR [26] reprend le principe du protocole DSDV. Ce protocole construit les tables de routages de fa¸con réactive en se basant sur l’état des liens. En effet, la modification de la table se fait seulement lorsque l’état des liens varie. De plus, il copie les IDs (identités) des nœuds traversés dans l’en-tête du message pour permettre au message de retrouver son chemin vers la source. De ce fait, le protocole DSR peut ainsi choisir des routes alternatives s’il les consid`ere comme meilleures. Il poss`ede ainsi une réactivité plus rapide que celle du protocole AODV en cas de perte de liaison avec un nœud. Toutefois, DSR ne fonctionne pas bien si la mobilité est tr`es élevée, et l’augmentation des noeuds à traverser causera l’augmentation de la taille des paquets.