Ad-hoc On-demand Distance Vector
# Ad-hoc On-demand Distance Vector

AODV (pour Ad hoc On Demand Distance Vector) est un protocole de routage destiné aux réseaux mobiles (réseau ad hoc). Il est à la fois capable de routage unicast et multicast. Il est libre de boucle, auto-démarrant et s'accommode d'un grand nombre de nœuds mobiles (ou intermittents). Lorsqu'un nœud source demande une route, il crée les routes à la volée et les maintient tant que la source en a besoin. Pour les groupes multicast, AODV construit une arborescence. Ce protocole de routage est peu gourmand en énergie et ne nécessite pas de grande puissance de calcul, il est donc facile à installer sur de petits équipements mobiles.

La première publication faisant état de AODV apparaît lors du proceedings of the 2nd IEEE workshop on mobile computing systems and application. La démarche visait à normaliser les différents protocoles du MANET (Mobile Ad-hoc NETworks) pour les réseaux ad hoc. L'intérêt du routage dynamique ad hoc apparaît dès 1996 dans des articles comme Dynamic source routing in ad hoc wireless networks (1996). L'appropriation par la communauté technique de ce protocole entraîne de nombreuses évolutions et adaptations. Le nombre de publications qui s'en sont ensuivies a atteint un pic d'une centaine par an en 2004 et 2005 montrant l'intérêt porté à ce protocole lors de cette période. La mise à disposition par les opérateurs de réseaux à coût raisonnable et disposant d'une couverture proche de 100 % restreint l'intérêt des réseaux ad hoc.

L'intérêt majeur des réseaux ad-hoc est qu'ils sont très facile à mettre en place et pour un coût faible. Quelques expériences furent tentées, comme le « Réseau Citoyen » en Belgique. D'autres exemples existent de par le monde, en Afrique, ou le projet (SARI) en Inde. son utilisation pourrait pallier une couverture opérateur limitée. L'armée (Projet FELIN) ou la sécurité civile réfléchit à l'intérêt de cette organisation pour pallier une défaillance générale en cas de catastrophe naturelle par exemple.

## Description technique

### Principe de fonctionnement

AODV définit cinq types de messages distincts, référencés à l'Internet Assigned Numbers Authority (IANA), transmis via le port UDP 654. Parmi ces messages ce sont les requêtes RREQ(route request) et les réponses RREP (route reply) qui permettent de construire ses routes utilisées pour relayer les informations sur le réseau.

Lorsqu’un nœud source veut établir une route vers une destination pour laquelle il ne possède pas encore de chemin, il diffuse en broadcast un paquet RREQ. Si une réponse RREP est reçue alors l’opération de découverte de route est terminée. Dans le cas contraire, au bout d’un délai d’attente NET_TRANVERSAL_TIME, il rediffuse le message RREQ et attend une période supérieure à la première. En l'absence de réponse RREP, ce processus peut être répété jusqu'à RREQ_RETRIES fois (par défaut RREQ_RETRIES = 2). S'il n’y a toujours pas de réponse au bout des trois (ou RREQ_RETRIES + 1) tentatives, le processus de recherche de route est abandonné. Une nouvelle demande de route sera initiée au bout d’un délai de 10 s. Un nœud recevant un paquet RREQ émettra alors un paquet RREP (route reply) s'il est la destination ou s'il possède une route vers la destination avec un numéro de séquence supérieur ou égal à celui du paquet RREQ sinon il rediffuse le paquet RREQ. Les nœuds conservent chacun une trace des IP sources et des identifiants de diffusion des paquets RREQ. Dans le cas où ils reçoivent un paquet RREQ qu’ils ont déjà traité, ils le suppriment.

Une fois que la source a reçu les paquets RREP, elle peut commencer à émettre des paquets de données vers la destination. Si, ultérieurement, la source reçoit un RREP contenant un numéro de séquence supérieur ou égal, mais avec un nombre de sauts plus petits, elle mettra à jour son information de routage vers cette destination et commencera à utiliser la meilleure route. Une route est maintenue aussi longtemps qu’elle continue à être active, c'est-à-dire tant que des données transitent entre la source et la destination. Le lien expire quand il n’y a plus de données en transit sur le lien et au bout d'un délai appelé ACTIVE_ROUTE_TIMEOUT. En cas de coupure du lien, le nœud extrémité émet un paquet RERR (Route Error) vers le nœud source pour le prévenir que la destination est désormais injoignable. Si le nœud source veut toujours obtenir une route vers cette destination, il doit recommencer le processus de découverte de route.

La figure ci-dessous illustre une recherche de route à l’initiative du nœud ${\mathcal {A}}$ et en direction de ${\mathcal {J}}$ et les différentes tables de routages constituées. La diffusion du message RREQ à partir de ${\mathcal {A}}$ se fait en broadcast vers tous ses voisins. Lorsque ${\mathcal {J}}$ reçoit le message il retourne un message RREP à ${\mathcal {A}}$ en passant par ${\mathcal {H}}$, ${\mathcal {G}}$ et ${\mathcal {D}}$.

La figure ci-dessous illustre le flux de requêtes lors de l'établissement d'une connexion entre deux nœuds. La fin du schéma représente la rupture des échanges entre des nœuds en cours de transmission des données.

### Formats des messages

**Message RREQ**

Le message RREQ de demande de route, est le message d'interrogation des routes disponibles. Il est constitué d'une trame de 24 octets :

* Les quatre premiers octets sont constitués du champ Type sur 8 bits forcé à 1 indiquant qu'il s'agit d'un message RREQ. Les bits suivants : J, R, G, D, U décrits plus bas indiquent les différentes utilisations du message. Un champ reserved sur 11 bits mis à 0 laisse la possibilité d'évolution ultérieurs. Puis un champ de 8 bits indique le nombre de sauts.
* Les quatre octets suivants portent l'identification du message.
* Les quatre suivants l'adresse IP de la destination.
* Les quatre suivants le numéro de séquence de la destination. Les deux suivants l'adresse IP d'origine.
* Les quatre derniers sont destinés à l'identification de la transaction par la source IP.
* Le champ Type est forcé à 1.
* Le bit J : est positionné à 1 sur le message sortant en cas d'utilisation de multicast.
* Le bit R : est positionné à 1 sur le message retour en cas d'utilisation de multicast.
* Le bit G : Drapeau RREP gratuite, indique si un RREP gratuite doit être envoyé en unicast vers le nœud spécifiée dans le champ Adresse IP destination.
* Le bit D : Drapeau de destination seulement, indique que la destination seul peut répondre à cette RREQ.
* Le bit U : Numéro de séquence inconnue, indique à la destination que le numéro de séquence est inconnu.
* Reserved : Envoyés à 0, ignoré à la réception.
* Hop count : Le nombre de sauts à partir de l'adresse IP origine jusqu'au nœud de traitement de la demande.
* RREQ ID : Un numéro de séquence unique permet d'identifier les RREQ notamment lorsqu'elle est prise en association avec l'adresse IP d'origine.
* Destination IP Address : L'adresse IP destinataire pour laquelle une route est souhaitée.
* Destination Sequence Number : Le dernier numéro de séquence reçu par l'émetteur pour toute route vers le destinataire.
* Originator IP Address : L'adresse IP du nœud à l'origine de la demande de route.
* Originator Sequence Number : le numéro de séquence actuelle utilisée dans l'itinéraire pointant vers l'initiateur de la route demandée.

**Message RREP**

Le message RREP de réponse à la demande de route, est le message indiquant au demandeur les routes disponibles. Il est constitué d'une trame de 20 octets :

* Les quatre premiers octets sont constitués du champ Type sur 8 bits forcé à 2 indiquant qu'il s'agit d'un message RREP. les deux bits R et A décrits plus bas indiquent pour le premier qu'une route défectueuse est réparée, le deuxième pour sa part indique que ce message sera suivi d'un RREP-ACK. Puis 12 bits réservés pour évolution mis à 0. 5 bits de préfixe référençant le nœud pour les routages. Puis un champ de 8 bits indique le nombre de saut.
* Les quatre octets suivants portent l'identification du message.
* Les quatre suivants l'adresse IP de la destination.
* Les quatre suivants le numéro de séquence de la destination. Les deux suivants l'adresse IP d'origine.
* Les quatre derniers sont destinés à l'identification de la transaction par la source IP.
* Le champ Type : forcé à 2.
* Le bit R : Indicateur de réparation; utilisée pour le multicast.
* Le bit A : acquittement requis.
* Reserved : Envoyé à 0, ignoré à la réception.
* Prefix Size : Si non nul, la taille de préfixe à 5 bits indique que le saut suivant peut être utilisé pour tous les nœuds avec le même préfixe de *routage (tel que défini par le préfixe Taille) pour la destination demandée.
* Hop Count : Le nombre de sauts à partir de l'adresse IP origine à l'adresse IP de destination. Pour une route de multicast demandée, indique le *nombre de sauts à effectuer à chaque membre de l'arbre en envoyant l'RREP.
* Destination IP : L'adresse IP de la destination pour laquelle une route est fournie.
* Destination Sequence Number : Le numéro de séquence de la destination associée à l'itinéraire.
* Originator IP Address : L'adresse IP du nœud à l'origine du RREQ pour laquelle l'itinéraire est fourni.
* Lifetime : Le temps en millisecondes pendant lequel les nœuds recevant l'RREP peuvent considérer la route comme étant valide.

**Message RERR**

Le message RERR indiquant une route en erreur est le message retour signalant au demandeur les routes en erreur. Il est constitué d'une trame de 20 octets :

* Les quatre premiers octets sont constitués du champ Type sur 8 bits forcé à 3 indiquant qu'il s'agit d'un message RERR. le bit N décrit plus bas indique qu'une route défectueuse est réparée.
* Puis 15 bits réservés pour évolution mis à 0. Les 8 bits suivants indiquent le numéro de destination inaccessible.
* Puis sur quatre octets l'adresse IP de destination inaccessible.
* Les huit suivants indiquent si besoin le complément d'adresse.
* Le champ Type : forcé a 3.
* le bit N : Indicateur de non-suppression. Quand un nœud a effectué une réparation locale d'un lien. Les nœuds amont ne doivent pas supprimer la route.
* Reserved : Envoyé à 0, ignoré à la réception.
* DestCount : Le nombre de destinations inaccessibles inclus dans le message, doit être d'au moins de un.
* Unreachable Destination IP Address : L'adresse IP destinatrice qui est devenue inaccessible en raison d'une coupure de liaison.
* Unreachable Destination Sequence Number : Le numéro de séquence dans l'entrée de la table de routage pour la destination indiquée dans le champ précédent Destination IP inaccessible.

**Message RREP-ACK**

Le message RREP-ACK d'accusé de réception de route de repli, est le message indiquant la prise en compte d'une autre route disponible. Il est constitué d'une trame de 2 octets. Le premier octet est constitué du champ Type sur 8 bits forcé à 4 indiquant qu'il s'agit d'un message RREP-ACK. Les 8 bits suivant mis à 0 sont réservés pour évolution.

* Le champ Type : forcé à 4.
* Reserved : forcé à 0, ignoré à la réception.

## Motivation des acteurs

AODV a été expérimenté sur de nombreux moyens de communications (Wi-Fi, WiMAX, 4G, etc.) ainsi que des évolutions de ce protocole ont été développées pour être compatible avec des systèmes d’exploitation comme Linux et Windows.

### Études

**Spécifiques**

En octobre 2010 une étude a été publiée sur les réseaux de capteurs ainsi que sur les différents protocoles de routage dont AODV. Cette étude aborde les contraintes liées aux capteurs sans fil (consommation énergétique, la qualité de service, etc ), les perspectives futures d’utilisation de ces réseaux dans les domaines comme le médical, le militaire, dans des applications commerciales, mais aussi dans le domaine environnemental.

Cette étude cite des utilisations des réseaux de capteurs dans plusieurs milieux, tels que la maison intelligente, le milieu hospitalier, le milieu industriel, le milieu militaire...

En décembre 2010 le projet RISK (Réseaux hétérogènes intelligents pour Situation de Crise) a été proposé. Ce projet présente un réseau de crise pour la sécurité civile (pompiers) ayant pour support des capteurs sans fils constituant un réseau Ad hoc avec AODV comme routage réactif de référence.

Lors d’événements exceptionnels comme une catastrophe naturelle, ou d'événement culturel, sportif ou autre, il est envisageable de pallier rapidement l’absence d’infrastructures de communication.

Des capteurs qui embarquent le logiciel AODV peuvent être utilisés dans divers autres domaines.

**Logiciels**

Le protocole AODV a été implémenté sur des systèmes d'exploitation. En 2004 le National Institute of Standards and Technology (NIST) adapte AODV sur le système d'exploitation Linux (Kernel 2.4).

Pour le système d'exploitation Windows XP, en 2005 ComNets de l'Université de Bremen crée une version UoBWinAODV version 0.15.

UoBJAdhoc version 0.21 est une implémentation de AODV sur JAVA développé par l'Universite de Bremen.

Une adaptation de AODV : FB-AODV (Flow-Based AODV) a été utilisé sur des mobiles avec Android comme système d'exploition pour former un réseau Ad hoc. Des tests ont été réalisés pour transmettre sur des liens Wi-Fi des SMS et de la VoIP (Voice over IP) entre les différents équipements mobiles.

**Réseaux supports**

Le protocole AODV a été adapté et testé sur différents types de support de transmission, sur des réseaux WPAN (Wireless Personal Area Network) a base de ZigBee/802.15.4 en utilisant AODV-UU.

R-AODV a été développé pour les réseaux Wi-Fi norme IEEE 802.11.

Des tests ont été menés sur des réseaux 4G (IMT-2000), sur des ondes électromagnétiques en milieu sous-marin mais aussi pour les réseaux WiMAX.

D'autres développements ont été réalisés sur des réseaux CDMA(Code Division Multiple Access), sur des réseaux 6LoWPAN.

En 2007 une expérimentation est réalisée sur un réseau utilisant la technologie Bluetooth. Pour cela une variante de AODV est créée : ADT-AODV.

**Matériels**

Le protocole de routage AODV peut être installé sur différents équipements comme les micro-capteurs de Réseau de capteurs sans fil mais aussi sur des PDA (Personal Digital Assistant), des ordinateurs portables...

Les équipements Qnode+ sont des points d’accès sans fil connectés à internet et font répéteurs pour les réseaux Mesh. Ils sont Auto configurable. En natif AODV est implémenté sur ces équipements.

L’ensemble de ces développements permettent de déployer des réseaux en mode Ad hoc sur des équipements (PDA, ordinateurs portables, réseaux de capteurs) munis des caractéristiques citées ci-dessus.

### Déploiements réels

Des constructions en grandeur réelle ont été réalisées dans plusieurs pays comme en Belgique avec le « Réseau Citoyen ». Ce réseau expérimental a été déployé dans la ville de Bruxelles sur des technologies sans fil (Wi-Fi, Wireless). La réalisation de ce réseau a démontré la facilité d’implémentation de ce type de réseau pour un coût inférieur à l’implémentation d’un réseau traditionnel.

En Inde dans la région de Madurai et du Tamil Nadu, le projet SARI(Sustainable Access in Rural India) a été inauguré en 2001.

En 2004 au Cameroun, « Cameroun Sans-Fil » permet de construire des réseaux dans des villages sans infrastructure de télécommunication. Chaque individu installe chez lui un PC avec une carte réseau Wi-Fi.

En 2009 une expérimentation de pilotage de robots est faite en utilisant AODV comme protocole de routage de message entre les machines. La transmission de ces messages se fait au moyen de capteurs Wi-Fi équipant chaque automate.

La société LocustWorld commercialise des solutions de réseau à base de Wi-Fi et utilise le protocole de routage AODV dans son offre commerciale « LocustWorld MeshAP Pro Clustering ». Le village de Cilcennin en Angleterre a choisi cette technologie pour raccorder ses habitants à Internet en l'absence d'infrastructure.

## Historique

Dès 1997, il est question d'AODV dans la publication du compte rendu de la conférence MobiCom 98 (4th annual ACM/IEEE international conference on Mobile computing and networking) qui a eu lieu en décembre 1997.

À cette occasion d'autres protocoles/algorithmes furent étudiés pour le routage MANET (Mobile Ad-hoc NETworks) :

* TORA: Temporally Ordered Routing Algorithm Basé sur un routage d'ordre temporel lié à l'établissement des routes.
* ZRP : Zone Routing Protocol Basé sur la création de zone de proximité, puis routage en bordure.
* IMEP : Internet MANET Encapsulation Protocol Offre la possibilité de véhiculer des algorithmes de routage ou de contrôle réseau.

En 1999, le protocol de routage AODV est décrit dans un document coécrit par Charles E.Perkins et Elizabeth M.Royer. Algorithme adapté à un réseau dynamique.

En 2000, AODV-BR est une évolution du protocole permettant la gestion du backup routing, ce qui sécurise les échanges (chemins alternatifs).

En 2000, AODV6 est une version adaptée pour IPv6 : évolution de la taille des messages pour prise en compte du format IPv6.

En 2000, MAODV est une évolution de AODV pour le Multicast qui servira de support en 2004 à la création d'un service DNS (Domain Name System) sur les réseaux ad-hoc : adaptation rapide à lien dynamique bi-directionnel.

En 2001, AOMDV est une adaptation du protocole AODV pour le Multipath : calcul de plusieurs routes, gain de 20 % en coût de routage par rapport à AODV.

En 2002, il est fait une comparaison des consommations d'énergie de 4 principaux protocoles de routage dans les réseaux MANET(DSR, AODV, TORA et DSDV).

En 2003, LB-AODV est une évolution permettant une meilleure efficacité de AODV par l'introduction de la Répartition de charge (load-balancing) : équilibrage et répartition de charge sur les liens.

En 2004, AODV-bis permet de limiter à des zones prédéfinies l'envoi de message de découverte de routes : réduction du nombre de messages.

En 2004, MTPR, une alternative à AODV est créée pour diminuer la consommation d'énergie lors de la découverte de routes.

En 2006, AODV-SEC est une évolution de AODV qui permet l'utilisation de certificats et de clés publiques.

En 2009, AODV-GT est une évolution pour la sécurisation des données échangées par AODV dans les réseaux MANET utilisés en cas de crise (eMANETs : emergency mobile ad hoc networks).

En 2010, EA-AODV : évolution de AODV pour diminuer la consommation d'énergie de AODV.

En 2010, S-AODV : adaptation de AODV pour les réseaux 6LoWPAN.

En 2011 RE-AODV : évolution du protocole AODV qui apporte un gain significatif en termes de délai de transmission des paquets et une diminution de la consommation d'énergie lors des découvertes de routes.

## Comparatifs avec d'autres protocoles ad-Hoc

Les protocoles de routage ad hoc peuvent être classés en trois groupes différents : proactifs, réactifs et hybrides.

Les protocoles proactifs : Dans les protocoles proactifs, les tables de routages sont déterminés au démarrage, et maintenues grâce à une mise à jour périodique.

Les protocoles réactifs : Dans les protocoles réactifs, les itinéraires sont déterminés quand ils sont requis (à la demande).

Les protocoles de routage hybride : Ces protocoles combinent les propriétés de base des deux premières classes de protocoles, en un seul. Autrement dit, ils sont à la fois réactifs et proactifs.

### Protocoles réactifs

Le protocole AODV est basé sur les algorithmes DSDV et DSR. AODV a un routage potentiellement moins couteux que DSR.

Le protocole DSR (Dynamic Source Routing) est similaire à AODV dans le sens où il forme une route à la demande quand un ordinateur veut transmettre. Cependant, il utilise le routage à la source au lieu de se baser sur la table de routage de chaque routeur intermédiaire. Le protocole DSR n'est pas très efficace dans les grands réseaux étant donné que chaque source doit avoir la vision du réseau. Le coût de maintenance des tables de routage est important. Mais pour les petits et moyens réseaux, il prend un avantage sur AODV, RMT ou TORA.

Le protocole ABR (Associativity-Based Routing) est un autre protocole de routage à la source Cependant, ABR est basée sur la stabilité, il ne prend pas en compte rapidement les ruptures de lien. Il n'utilisera pas forcément le plus court chemin vers la destination. Les chemins alternatifs ne seront pas immédiatement utilisés.

### Protocoles proactifs

Le protocole DSDV garantit les routes sans boucle. Il fournit un seul chemin vers une destination, qui est sélectionné en utilisant le vecteur de distance du plus court chemin dans l'algorithme de routage. DSDV introduit une charge importante sur le réseau en raison de la mise à jour périodique des messages, et la surcharge augmente en fonction de sa taille. Il n'est pas adapté à un réseau de grande échelle.

Le protocole WRP garantit également les routes sans boucles. grâce à des tables de routage temporaires en utilisant les informations reçues. Toutefois, WRP exige pour chaque nœud le maintien de quatre tables de routage. Ceci introduit une quantité de données importante en mémoire pour chaque nœud lié à la taille du réseau.

Le protocole CGSR est un protocole de routage hiérarchique où les nœuds sont regroupés en grappes. L'avantage de ce protocole est que chaque nœud maintient les routes de son cluster source, ce qui signifie que les coûts généraux de routage sont faibles. Cependant, il y a des surcoûts importants liés à l'entretien des grappes.

### Protocoles hybrides

Le protocole TORA Temporally-ordered routing algorith est basé sur le protocole LMR. L'avantage de TORA est qu'il réduit la portée des messages de contrôle des nœuds voisins, où le changement de topologie est survenue. Un autre avantage de TORA est qu'il supporte aussi le multicast.

L'inconvénient de TORA est que l'algorithme peut aussi produire temporairement des itinéraires invalides comme dans RMT.

Le protocole ZRP Zone Routing ProtocolLes nœuds sont dans une zone de routage, qui définit une plage (en saut) que chaque nœud doit maintenir pour assurer la connectivité du réseau de façon proactive.

Pour les nœuds de la zone de routage, les routes sont immédiatement disponibles. Pour ceux hors de la zone de routage, les itinéraires sont déterminés à la demande (soit réactive). L’avantage de ce protocole est qu'il a considérablement réduit les échanges par rapport aux protocoles purement proactifs.

C'est le nœud frontière qui d'une façon proactive maintient les routes vers la destination. L'inconvénient est qu'en cas de nombre de zone de routage important, le protocole peut se comporter comme un protocole proactif pur, tandis que pour de petites valeurs, il se comporte comme un protocole réactif.

Le protocole HECTOR : Energy effiCient Tree-based Optimized Routing protocol for wireless networks HECTOR est un protocole hybride efficace à base d'arbre de routage optimisé, basé sur deux jeux de coordonnées virtuelles. Un jeu est basé sur les coordonnées d'origine, et l'autre est basée sur les distances en nombre de saut des destinataires. L'algorithme qui transmet des paquets à son voisin optimise le ratio puissance/distance. Si le nœud n'existe plus, alors la transmission est faite au voisin qui réduit la distance des arbres et optimise les coûts. La supériorité de l'algorithme sur les alternatives existantes est qu'il y a une garantie de la livraison.

Le protocole MMDV : MMDV est un protocole de type hybride qui s'appuie sur AODV et est une amélioration du protocole AODV qui utilise les trajets multiples et l’inondation par la technique MPR. MMDV (Multipath and MPR based AODV). Dans sa phase proactive, les nœuds calculent leurs listes MPR et maintiennent des routes vers les voisins à deux sauts. Dans sa phase réactive, les nœuds maintiennent "deux" chemins pour chaque destination. Cette solution permet de minimiser la charge de routage et réduire la consommation de la bande passante tout en résolvant le problème de changements de topologie. Les performances de MMDV dépassent celles des protocoles AODV, OLSR et DSR.

### Études comparatives

**Outils pour simuler, visualiser**

Pour les études précédemment citées des outils de simulations ont été utilisés, parmi lesquels on peut citer :

* Network Simulator NS-2. Le logiciel NS, logiciel libre de simulation à événements discrets est fourni avec une interface graphique (NAM) permettant de démontrer le fonctionnement des réseaux, ce qui en fait un outil à la valeur pédagogique très intéressante.

Il est considéré par beaucoup de spécialistes des télécommunications comme le meilleur logiciel de simulation à événements discrets.

* OPNET (0ptimized Tool Engineering Network) fournit un environnement de développement complet pour l'analyse de spécification, de simulation et de la performance des réseaux de communication. Il est très proche de NS-2 comme le montre la conclusion de cette étude.
* OMNEST est utilisé pour étudier divers scénarios et alternatives de conception : conception architecturale, sans fil / filaire protocoles et de réseaux, basée sur file d'attente et d'autres systèmes. Ce logiciel permet de construire et d'évaluer des simulations dans un IDE intégré de simulation.
* JiST/MobNet: Combined Simulation, Emulation, and Real-world Testbed for Ad hoc Networks . Ce simulateur permet de tester une modélisation sur plusieurs plans.

Modélisation analytique, simulation de réseau, émulation de réseau et intégration des expériences du monde réel.

Le mémoire de Nouha Baccour de 2004 compare deux simulateurs pouvant traiter jusqu'à 10 000 nœuds.

* GloMoSim: a library for parallel simulation of large-scale wireless networks.
* NCTUns: The design and implementation of the NCTUns 1.0 network simulator

Le projet Senslab est un projet du programme « Télécommunications » de l’Agence nationale de la recherche (ANR) sur les « Very large open wireless sensor networks » initié en 2008 concernant les réseaux de capteurs à grandes échelles. Il s’inscrit dans le contexte des réseaux de capteurs sans fils et utilise des nœuds réels fixes ou mobiles. Ce programme a pour objectif de faciliter l’expérimentation de très grands réseaux de capteurs sans fils.

Le logiciel Wireshark Wireshark networkt Protocol Analyser (anciennement Ethereal) est un logiciel libre d'analyse de protocole, ou « packet sniffer », utilisé dans le dépannage et l'analyse de réseaux informatiques, le développement de protocoles, l'éducation et la rétro-ingénierie, mais aussi le piratage.

Wireshark reconnait 759 protocoles.

**Avec d'autres protocoles de MANET**

En 2010, une étude comparative a été menée entre DSR et AODV dans les réseaux VANET (Vehicular Ad-Hoc Network). Cette étude a démontré qu'AODV est plus adaptée que DSR pour une utilisation dans des voitures. En effet, les résultats montrent qu'en faisant varier la vitesse des véhicules le nombre de paquets perdus est moins important avec le protocole AODV qu'avec DSR.

En 2011 une étude comparative a été menée entre DSR, AODV et DSDV sur un réseau WiMAX. Lorsque les nœuds sont peu mobiles AODV est le protocole qui obtient les meilleurs résultats alors que DSR est supérieur lorsque la mobilité augmente. DSDV obtient dans tous les cas des résultats inférieurs aux deux autres protocoles.

En 2007, l'étude de Maamar montre l'impact de la mobilité, le nombre de nœuds (ou densité), l’énergie consommée par les nœuds et la variation de l’échelle, sur le taux de perte pour les protocoles (DSR, DSDV et L’AODV). De cette simulation effectuée avec NS-2, il en ressort entre autres que pour un protocole de transport TCP, la quantité d’énergie consommée est petite pour DSR, moyenne pour DSDV et importante pour l’AODV. Alors que pour le protocole UDP AODV prend la tête du classement. Concernant la mobilité c'est DSR qui est le plus efficace en utilisant TCP. L'augmentation du nombre de nœuds quant à lui permet de faire décroître le taux de perte en utilisant UDP. De ce fait la perte sur un réseau moins dense est énorme par rapport à un réseau contenant de plus en plus de nœuds, quel que soit le protocole utilisé (AODV, DSDV ou DSR). Enfin, concernant la variation de l'échelle c'est DSR qui s'en sort le mieux et concernant DSDV et AODV leur classement dépend de l'échelle. Il conclut que le choix de l’algorithme de routage dépend des contraintes précédemment citées et qu’il est intéressant de considérer et de combiner le maximum d’entre elles pour tirer les meilleurs profits.

En définitive, il est très difficile de comparer des protocoles de routage. Par exemple, dans le cas de OLSR et AODV, Hsu conclut que AODV est le plus performant tandis que Gauthier affirme que OLSR surpasse le protocole AODV. Bien évidemment, les deux résultats sont corrects mais le contexte d'étude est différent. En effet, dans son étude, Gauthier prend en compte l'impact des interférences radio ce que ne fait pas Hsu.

**Études spécifiques à AODV**

D'autres études se préoccupent des performances spécifiques à AODV. Cette évaluation est réalisée dans une approche comparative à la suite de la simulation de trois configurations réseau différentes en termes de dimensions du réseau (m²), nombre de nœuds (N) et densité de nœuds (N/km²). En entrée on utilise un modèle de trafic à débit constant et un modèle de mobilité aléatoire en augmentant la vitesse. Il en ressort les résultats suivants :

* Figure 1 - Graphique issu de l'étude de Nabil Tabbane en 2004
* Figure 2 - Graphique issu de l'étude de Nabil Tabbane en 2004
* Figure 3 - Graphique issu de l'étude de Nabil Tabbane en 2004
* Figure 4 - Graphique issu de l'étude de Nabil Tabbane en 2004
* Figure 5 - Graphique issu de l'étude de Nabil Tabbane en 2004

La figure 1 représente le taux des paquets livrés avec succès. Quand les nœuds sont presque immobiles ce taux est très proche des 100 %. Par contre on voit clairement l'influence négative de la vitesse de déplacement des nœuds et de la taille du réseau et du nombre de nœuds.

Les réseaux 1 et 2 ont un taux très semblable jusqu'à une vitesse de déplacement de 10 m/s. Au-dessus, ce taux va chuter pour le réseau 2 alors que pour le réseau 1, il est toujours supérieur à 90 %. Pour le réseau 3 le taux se dégrade dès l'augmentation de la mobilité des nœuds. Ceci est dû à une augmentation de la longueur des routes et par conséquent, les HELLO_MESSAGE échangés sont plus nombreux. En cas de coupure de liaison, le nœud source, pour qu'il en soit informé, doit attendre pendant un certain temps durant lequel les paquets de données en cours de route vont être perdus. Si nous réduisons la période d’émission des HELLO_MESSAGE pour détecter plus rapidement les liaisons cassées, il y aura alors plus de paquets de contrôle (HELLO_MESSAGE) aux dépens des paquets de données.

La figure 2 représente le trafic de contrôle. Il existe toujours une différence entre le trafic de contrôle pour chacun des 3 réseaux. C’est essentiellement les HELLO_MESSAGE qui font cette différence qui s'explique par les routes assez longues dans le réseau 2 et encore plus longues dans le réseau 3. Lorsque les nœuds sont peu mobiles le trafic de contrôle est quasiment le même pour les 3 réseaux. Cette propriété est due au fait que le protocole AODV est un protocole réactif qui n’agit qu’en cas de demande d’établissement de route. Le trafic de contrôle augmente avec la mobilité des nœuds. Cette augmentation est due à la fréquence des liaisons cassées provoquant l’émission des paquets RERR. Lorsque la vitesse de déplacement des nœuds augmente considérablement (15 m/s et 20 m/s), Nabil Tabbane observe que le trafic de contrôle devient de plus en plus indépendant de cette augmentation de mobilité et tend vers une valeur presque constante. Ceci montre que le protocole AODV est bien adapté aux changements fréquents de la topologie du réseau. Néanmoins, il faut trouver un compromis entre la dégradation du taux de livraison des paquets (figure 1) et le trafic de contrôle pour les réseaux fortement mobiles ; c’est-à-dire trouver les valeurs optimales des paramètres HELLO_INTERVAL et ALLOWED_HELLO_LOSS qui minimisent le taux de perte des paquets sans trop augmenter le trafic de contrôle sur le réseau.

La figure 3 représente le temps d'établissement d'une route. Elle montre globalement une bonne aptitude du protocole AODV à trouver une route dans le réseau. La vitesse de déplacement des nœuds a peu d'influence sur cette valeur qui tend vers une constante. Également, plus il y a de nœuds plus le temps d'établissement d'une route diminue.

La figure 4 nous donne le délai moyen pour acheminer un paquet de données depuis le nœud source jusqu’au nœud destination. Pour les 3 réseaux et pour les différentes vitesses de déplacement, le délai d’un paquet reste presque constant. En effet, si la mobilité des nœuds augmente, ceci va engendrer trop de liaisons rompues et donc les paquets qui sont déjà dans le buffer depuis un certain temps, sont directement éliminés ce qui fait que le délai n’est comptabilisé que pour les paquets ayant atteint leur destination. Cette suppression des paquets mis dans le buffer est la principale cause de l’augmentation du taux de perte des paquets lorsque la mobilité des nœuds augmente. La durée maximale pendant laquelle un paquet est autorisé à rester dans un buffer ne doit être trop longue car ceci va augmenter la consommation des ressources mémoire disponibles pour les buffers et augmenter le délai de bout en bout d’un paquet. Donc la fixation de cette durée varie selon que l’application exige un taux de perte faible sans grande importance pour le délai (transfert de fichier, base de données, etc.) ou bien que l’application exige un délai très court sans grande importance pour le taux de perte (vidéo, téléphonie, etc.). La figure 5 représente la longueur moyenne des routes. La première constatation est que le nombre de sauts que doit effectuer un paquet pour être acheminé du nœud source au nœud destination augmente avec la taille du réseau et du nombre de nœuds dans le réseau. Cependant, pour une configuration donnée (réseau 1 ou 2 ou 3), ce nombre augmente très faiblement avec la vitesse de déplacement des nœuds. Ceci vient confirmer la figure 4 puisqu'un nombre constant de sauts donne un délai de transmission d'un paquet constant. L'adaptabilité du protocole AODV vis-à-vis de la mobilité du réseau est au prix d’un taux de perte des paquets qui augmente avec cette mobilité.

À la suite de cette étude, Tabbane constate que le protocole AODV offre une bonne adaptabilité vis-à-vis de la mobilité des nœuds dans un réseau en termes de délai, de temps d’acquisition de route, de trafic de contrôle et de longueur de route. D’autre part, AODV présente un taux de livraison des paquets avec succès qui se dégrade avec l’augmentation de la mobilité des nœuds du réseau. Il ajoute qu’un autre travail de simulation reste nécessaire avant de conclure d’une manière définitive sur les performances de ce protocole. Ces simulations devront porter cette fois sur l’effet précis des paramètres internes du protocole AODV comme RREQ_RETRIES, HELLO_INTERVAL ou DELETE_PERIOD.

### Bilan

AODV fait partie des protocoles MANET les plus connus. Il a suscité et suscite encore de nombreux articles scientifiques. Son choix par rapport à d'autres protocoles MANET, qu'ils soient proactifs, hybrides ou même par rapport à d'autres protocoles réactifs doit être guidé par le réseau sur lequel il doit être mis en œuvre. Jean-Pierre Chanet propose un classement avec les avantages et les inconvénients des différentes catégories de protocoles de routage :

Issue du travail de Jean-Pierre Chanet :

| | Avantages | Inconvénients |
| - | - | - |
| Proactifs | Pas de temps de réaction Adaptés aux réseaux denses de taille moyenne Adaptés aux réseaux à forte mobilité | Trafic de contrôle important Capacité d'échange du réseau limitée Consommation énergétique plus importante |
| Réactifs | Trafic de contrôle faible Adaptés aux grands réseaux Consommation énergétique réduite | Temps de réaction long Problème en cas de forte mobilité des nœuds |

Il est dit explicitement que chaque famille de protocole de routage est plus ou moins adaptée à un type de réseau. Il convient donc de définir précisément les caractéristiques du réseau (taille, mobilité des nœuds, ressources des nœuds, volume d'information à échanger...) afin de bien choisir un protocole de routage adapté.

De même, la sécurité que l'on verra dans un paragraphe dédié est désormais une réflexion qu'il est nécessaire de mener parallèlement.

Enfin, si AODV est le plus adapté, comme l'évoque Nabil Tabbane dans sa conclusion, l'ajustement du paramétrage doit faire l'objet d'une étude à part entière.

## AODV et la sécurité

### Pour quelles menaces ?

Les recherches récentes sur les réseaux ad-hoc ne se focalisent que très peu sur les aspects sécurité. Pourtant leurs spécificités montrent à quel point les réseaux ad hoc sont vulnérables. Parmi ces vulnérabilités figurent :

* la transmission en milieu ouvert ;
* les problématiques de topologies dynamiques ;
* l'absence d’autorité centrale ;
* la nécessité d'une bonne coopération des nœuds ;
* l'hétérogénéité des participants avec pour certains des capacités restreintes.

Pour donner un exemple de vulnérabilité sur une transmission en milieu ouvert (sans fil), on peut mettre en avant l'exposition des nœuds à des problèmes d'intégrité physique. Une surveillance sismique par exemple, nécessite de lâcher des capteurs dans la nature. Ils deviennent alors physiquement accessibles. Un moyen de contourner ce problème est de mettre en évidence une attaque physique sur un élément. Autre exemple concret, le fait que les nœuds utilisent une transmission sans fil les rend également très sensibles une à Attaque par déni de service sur le canal radio.

Les autres vulnérabilités précédemment citées nous amènent à faire un focus sur le routage des réseaux ad hoc. Il est identifiée comme particulièrement sensible. Son fonctionnement nécessite entre autres, la bonne coopération de tous les nœuds, ce qui présente un risque s'il n'y a aucun contrôle des participants. Par conséquent l'authentification, l'intégrité, la confidentialité et la disponibilité doivent faire l'objet d'une attention particulière. Parmi les attaques liées aux problèmes d'authentification on peut citer le trou noir (blackhole). Cette attaque consiste à insérer un nœud malicieux ayant la capacité d'usurper l'identité d'un nœud valide. Le nœud en question pourra ainsi ignorer les données qu'il est censé faire transiter. L'attaque «grey hole», qui en est une variante, pourra ignorer seulement certains types de paquets. La figure ci-dessous décrit une attaque de type blackhole.

Dès lors qu'un nœud malicieux est intégré au réseau il devient possible de créer des boucles infinies ou de détourner du trafic pour consommer de l'énergie.

De même, si l'authentification est mal gérée, un attaquant peut s'attacher au réseau sans fil et injecter des messages erronées. L'intégrité des messages échangées est donc une exigence importante pour ces réseaux. Si l'intégrité physique des nœuds est également mal gérée un attaquant peut subtiliser un appareil, le corrompre avec un cheval de Troie par exemple, avant de le restituer discrètement à son propriétaire.

Enfin, la disponibilité reste un point difficile à gérer dans les réseaux sans fil ad hoc étant donné les contraintes qui pèsent sur ces réseaux. Notamment la topologie dynamique, les ressources limitées sur certains nœuds de transit et les communications sans fil.

### Quelles parades existent actuellement ?

**Solutions pour l'authentification**

L’absence d’infrastructure centralisée dans les réseaux sans fil ad hoc compromet l’utilisation directe des systèmes d’authentification basés sur la cryptographie à clé publique. En effet, ces systèmes d’authentification supposent l’utilisation de certificats établis par une autorité centrale. Le certificat, signé par l’autorité centrale, permet de garantir qu’une clé publique appartient bien à son propriétaire et non à un usurpateur. L’opération de vérification de certificat ne se limite pas à contrôler la signature de l’autorité centrale. Il est aussi nécessaire de s’assurer que le certificat est toujours en cours de validité́ et qu’il n’a pas été révoqué. Une révocation de certificat est indispensable si la clé privée du propriétaire a été volée ou divulgué. Il existe trois grands courants dans le domaine de l’authentification pour les réseaux sans fil ad hoc. Deux de ces orientations se basent sur l'établissement d’une clé secrète permettant par la suite l’authentification des participants. Toute la complexité réside en la manière d’établir cette clé. Les deux modèles basés sur une clé secrète sont:

* The key agreement : les participants s’entendent sur une clé secrète.

Concrètement, des solutions proposent l'utilisation de la méthode de Diffie-Hellman généralisée aux multiples participants. Chaque nœud possédant une partie de la clé résultante. Cette solution s'avère finalement compliquée à mettre en œuvre sur des réseaux ad hoc.

* The Duckling Security Policy Model : le modèle d’authentification élaboré par Ross Anderson et al. est basé sur une relation de type maître-esclave. Lors de sa première utilisation, un objet doit être marqué par son propriétaire. Lors de cette opération une clé secrète est échangée entre les deux entités via un canal supposé sûr. Néanmoins ce modèle n'est pas complètement satisfaisant notamment pour la gestion des clés qui ne peut être centralisée sans risque.
* Le troisième axe de recherche pour l’authentification au sein de réseaux sans fil ad hoc, se base sur une infrastructure à clés publiques (PKI) et cherche à s’affranchir du besoin d’une entité centrale de certification. Ce modèle proposé par Hubaux et al. se base sur une infrastructure à clés publiques auto-organisée. Chaque nœud en réseau établit des certicats pour les nœuds en qui il a confiance. Lorsque deux nœuds d'un réseau veulent communiquer sans connaissance au préalable l'un de l'autre, ils s'échangent leur liste de certificats et vont essayer de créer une chaîne de confiance entre eux. Supposons qu'un élément A veuille communiquer avec un nœud C, si A fait confiance à un troisième élément B et C fait aussi confiance à B, alors une chaîne de confiance entre A et C pourra être établie via B.

**Solutions pour l’Intégrité et l’Authentification des Messages**

Il s'agit là d'utiliser des signatures numériques ou des MACs. Une signature électronique ou un MAC (Message Authentication Code) apposé à un message a pour double objectif de permettre au destinataire d'authentifier l'origine de ce message et de lui prouver son intégrité. Leur implémentation fait appel aux fonctions de hachage et aux clés symétriques ou asymétriques. Dans le cas de l'usage de la cryptographie symétrique, on emploie exclusivement le terme de MAC, tandis que dans l’usage de la cryptographie asymétrique, on peut parler de MAC, mais on préférera le terme de signature électronique.

**Solutions pour la confidentialité**

La confidentialité quant à elle peut être est gérée grâce à une cryptographie symétrique peu gourmande en calcul et donc en énergie.

Cette liste de solutions n'est pas exhaustive, en effet Beghriche cite également des Mécanismes basés sur la réputation, des Mécanismes de micro-paiement, des Mécanismes basés sur la confiance ou bien encore des Systèmes de détection d'intrusion.

### Cas concrets d'études mettant en œuvre ces solutions

* SAODV Ce protocole est destiné à la sécurisation du protocole AODV. L’idée principale de SAODV consiste à utiliser des signatures afin d’authentifier la plupart des champs des paquets Route_Request et Route Reply et d’utiliser des chaines de hachage pour protéger l’intégrité du compteur de sauts. Ainsi, SAODV constitue-t-il une extension d’AODV avec des signatures, afin de contrer les attaques de type «usurpation d’identité».
* ARAN Ce protocole utilise la cryptographie à clés publiques pour sécuriser les routes. ARAN est un protocole à la demande, qui fournit un service d’authentification de saut en saut par le biais d’une infrastructure à clés publiques. Le principe d’ARAN est sécuriser le mécanisme de découverte de routes de nœuds en nœud. Ainsi lorsqu’un nœud désire envoyer un message, il génère, signe puis diffuse un paquet de type RDP (Route Discover Packet). Par la suite, chaque nœud intermédiaire recevant ce paquet vérifie le certificat du nœud précédent, appose son propre certificat et rediffuse le paquet. Une fois ce paquet arrivé au nœud destination, celui-ci vérifie à son tour le certificat et répond en unicast, par un message de type REP (reply packet) qui est à son tour vérifié de nœuds en nœuds.
* SEC-AODV utilisent également des certificats et une infrastructure de gestion de clés publiques.
* SAR Le protocole SAR (Security-aware Ad hoc Routing protocol) se base lui sur des procédés de chiffrement symétrique. Il a été élaboré à l’origine pour prévenir les attaques de type blackhole. SAR est conçu pour être employé conjointement avec des protocoles réactifs tels qu’AODV ou DSR. Il utilise la notion de “niveaux de confiance” pour établir la sécurité d’un chemin. Ainsi, lorsqu’un nœud désire établir une route avec un certain niveau de sécurité, il génère un nouveau paquet RREQ indiquant le niveau requis. Par la suite, le mécanisme de découverte de routes diffère légèrement du schéma classique des protocoles réactifs en ce sens que seuls les nœuds satisfaisant le niveau de sécurité requis peuvent rediffuser la requête à ses voisins.
* RIDAN (Real-time Intrusion Detection for Ad hoc Networks) qui propose une architecture initialement basée sur une recherche de détections d'attaques sur le protocole de routage OSPF. Cette solution est destinée à détecter des intrusions en temps réel (Système de détection d'intrusion).

### Pour quelles performances ?

Malcolm Parsons montre l'effet négatif sur les performances des réseaux ad hoc soumis à des attaques de type blackhole ou encore de type wormhole en fonction de leur nombre. Pour ces tests il utilise le protocole AODV.

Sur le graphique ci-dessus, lorsque AODV est soumis à des attaques de type blackhole par exemple son PLR subit une augmentation importante.

La protection contre ces attaques n'est pas gratuite pour autant. Des recherches concernant la sécurisation du protocole AODV se préoccupent donc parallèlement de l'impact sur les performances. C'est le cas d'une étude datant de 2010 qui montre le coût engendré par la sécurisation de SAODV par rapport à AODV notamment. Les résultats de Balakrishna montrent que SAODV met 2,35 fois plus de temps que AODV pour obtenir une réponse RREP à une requête RREQ. Ceci est dû entre autres à la cryptographie qui augmente la taille des messages.

SRS_AODV utilise des fonctions cryptographiques robustes tout en minimisant la charge du calcul complexe. Cette étude montre entre autres que SRS_AODV établi ses routes plus rapidement que ARAN.

* Nombre de paquets reçus par la victime - Graphique issu de l'étude de Nesrine
* Temps moyen de bout en bout - Graphique issu de l'étude de Nesrine
* Overhead du routage - Graphique issu de l'étude de Nesrine

Les graphiques ci-dessus illustrent la comparaison qu'a effectué Nesrine et montrent que SRS_AODV est plus performant que AODV sur le temps moyen de bout en bout, l'overhead de routage et le nombre de paquets de données reçues par le nœud victime.

### Des attaques connues et des parades

Tableau présentant une liste d'attaques sur les réseaux ad hoc et leurs solutions :

| Attaques | Définition | Solutions proposées |
| - | - | - |
| Wormhole | Un attaquant pourrait rediriger le trafic entre deux zones géographiquement éloignées pour créer un vertex dans la topologie et ainsi avoir une bonne position géographique pour contrôler le trafic qui passe par lui. | Packet Leashes (Hu, Perrig et Johnson, 2003) |
| Attaque de routage | Un nœud malicieux pourrait perturber le fonctionnement d’un protocole de routage en modifiant les informations de routage, fabriquer les fausses informations de routage ou usurper l’identité d’un autre nœud | SEAD (Hu et al., 2003), ARAN (Sanzgiri et al., 2002), ARIADNE (Hu, Perrig et Johnson, 2005), SAODV (Zapata, 2002). |
| Jamming | C’est une attaque classique sur la disponibilité du canal de communication grâce à la génération massive d’une grande quantité d’interférence radio. | FHSS, DSSS (Liu et al., 2010). |
| Backhole attack | Le but de cette attaque est la falsification des informations de routage ou le détournement du trafic. | (Ramaswamy et al., 2006). |
| Attaque sur les ressources | Les réseaux MANET sont caractérisés par des ressources limitées (batterie et bande passante). Une attaque sur les ressources pourrait avoir des conséquences sur la disponibilité. | SEAD (Perkins et Bhagwat, 1994). |
| Attaque Byzantine | Grâce à cette attaque, un nœud malicieux altère les messages et pourrait créer des problèmes de boucle de routage, routage de paquets vers des chemins non optimaux, sélectionner les paquets à rejeter… Ce type d’attaque est difficile à détecter car le réseau semble fonctionner correctement. | OSRP (Awerbuch et al., 2002), (Awerbuch et al., 2004). |
| DoS | Ce type d’attaque consiste à envoyer délibérément des messages pour causer une saturation de la bande passante et paralyser le réseau. | SEAD (Perkins et Bhagwat, ARIADNE (Hu, Perrig et Johnson, 2005), SAODV (Zapata, 2002). |
| Divulgation d'information | L’échange des informations confidentielles doit être protégées contre l’écoute ou l’accès non autorisé. | SMT (Papadimitratos et Haas), SRP (Papadimitratos et Haas, 2002). |
| Répudiation | Ce type d’attaque a une conséquence sur l’intégrité des communications entre les nœuds dans le réseau. | ARAN (Sanzgiri et al., 2002). |
| Usurpation d'identité | L’usurpation d’identité a pour but la falsification des informations relatives aux identités. Ce qui pourrait conduire à l’isolement de nœuds, l’échange de fausses informations de routage et l’atteinte à la confidentialité et l’intégrité. | ARAN (Sanzgiri et al., 2002), SAODV (Zapata, 2002). |
