Les protocoles de routage

Les protocoles de routage

Les RCSF se caractérisent par leurs ressources limitées en mémoire et en énergie [28, 29].

La consommation d’énergie peut augmenter de façon drastique lorsque le nombre d’évènements du protocole de routage est important. La table de routage, et donc la mémoire utilisée, peut augmenter dans le cas de réseaux denses. Plusieurs protocoles de routage ont été développés pour garantir l’efficacité des RCSF en termes de consommation énergétique et de mémoire [30]. Le routage par inondation [1] est un des algorithmes de routage les plus simples. L’information est envoyée en broadcast à travers tout le réseau jusqu’à ce que celle-ci atteigne sa destination. Hormis le fait de sa simplicité, ce protocole peut générer plusieurs problèmes de redondance, de chevauchement, et de consommation aveugle des ressources. Le routage par rumeur [1] essaie d’éviter les problèmes de redondance du routage par inondation, en sélectionnant un noeud du voisinage comme relai de façon aléatoire.

Les noeuds gardent aussi une copie de chaque paquet envoyé afin d’éviter la redondance, ce qui augmente les délais de transmission et surtout la consommation des ressources. Le protocole SPIN (Sensor Protocol for Information via Negotiation) [1, 28-30] utilise des techniques de négociation afin d’éliminer les problèmes de redondance de données dans le routage. Chaque noeud effectue un suivi de la consommation de ses ressources ce qui influence ses décisions lors des négociations. Les négociations se font à travers des paquets d’avertissement, de requête et de données [1]. D’autres protocoles ont été développés spécialement pour les RCSF, comme la diffusion directe, PEGASIS, TEEN, … [30].

Introduction au protocole AODV

Le protocole de routage AODV (Ad-Hoc On-Demand Distance Vector) [33] est destiné aux réseaux ad hoc à noeuds mobiles. C’est un protocole multihop, adaptatif et dynamique par rapport aux conditions de la topologie, et permet d’éviter les situations de boucle fermée dans le routage. Ce protocole utilise trois types de paquets, RREQ (Route Request), RREP (Route Response), et RERR (Route Error). Ces messages sont reçus à travers le protocole UDP en allouant une adresse IP à chaque noeud. Quand une source cherche une route vers une destination, une requête RREQ est envoyée en broadcast à tout le voisinage. Chaque noeud recevant cette requête envoie de nouveau cette requête jusqu’à ce que celle-ci atteigne sa destination. La route est validée en renvoyant une réponse RREP via le chemin inverse de la requête jusqu’à sa source. Chaque noeud recevant la requête sauvegarde dans sa table l’adresse du hop précédent. Le hop suivant est reconnu dès la réception de la réponse. Quand un lien est reconnu « rompu » avec un noeud, un message d’erreur est envoyé aux autres noeuds pour les prévenir que la route vers les destinations qui ne sont plus disponibles. Une réparation de la route est alors effectuée, soit par la source de la requête ou bien par le noeud se trouvant au niveau du lien brisé.

Génération et acheminement des requêtes RREQ

La requête est générée par un noeud si celui-là ne connait pas la destination ou qu’une route préalablement valide a été invalidée ou a expiré. Le numéro de séquence de destination dans la RREQ est le dernier numéro de séquence de destination connu, sinon un indicateur de numéro de séquence inconnu est activé. Avant la transmission (en Broadcast) du paquet, la source sauvegarde le RREQ ID et l’adresse IP de la source (sa propre adresse) pour l’instant actuel. De cette manière, si la source reçoit le même paquet, celle-ci ne le retransmet pas. La source ne devrait pas générer plus qu’un maximum de paquets RREQ générés (RREQ_RATELIMIT) par seconde. Si une route n’est pas reçue en un temps inférieur à NET_TRA VERSAL_TIME millisecondes, la source peut générer un nouveau RREQ jusqu’à un maximum de retransmissions RREQ_ RETRIES. Les paquets de DATA en attente d’une route (en attente d’une RREP après la génération d’une requête RREQ) doivent être bufférisés en mode FIFO. Si le RREQ_RATELIMIT pour une certaine destination est atteint, tous les paquets de DATA qui lui sont destinés doivent être rejetés. Quand un noeud reçoit une requête, celui-ci crée ou remet à jour le hop précédent si celui-là n’a pas de numéro de séquence valide dans sa table de routage. Par la suit, le noeud vérifie s’il a déjà reçu le paquet RREQ avec la même adresse IP source et le même RREQ ID dans le dernier intervalle PATH DESCOVERY TIME. Si une requête est acceptée, le compteur de hops est incrémenté d’une unité. Ensuite, le noeud établit la route inverse vers la source de la requête. Cette route sera nécessaire si ce noeud doit acheminer une RREP vers la source de la requête. Quand une route est créée, les actions suivantes sont entreprises:

Les notations du protocole TORA Chaque noeud est identifié par un identificateur unique i. Ce noeud i dispose d’une série de voisins k, formant ainsi des liens (i, k). Un lien peut être un lien non dirigé, un lien descendant (de i vers k), ou un lien montant (de k vers i). Le protocole TORA assigne à chaque noeud un quintuplé appelé « hauteur » défini par : (tau[i], oid[i], r[i], delta[i], i). Ce quintuplé se compose de deux parties, les trois premières valeurs représentent le niveau de référence, et les deux dernières, le décalage (Offset) du noeud. Pour la première partie, la valeur tau[i] représente l’ instant de la rupture de lien. La valeur oid[i] représente l’identificateur du noeud qui a défini le niveau de référence. La valeur r[i] représente un bit qui indique si le niveau de référence a été changé par rapport à la valeur originale. La première valeur de la deuxième partie du quintuplé est la valeur delta[i], qui est un entier utilisé dans le but d’ordonner les noeuds en fonction du niveau de référence. La valeur i représente l’unique identificateur de chaque noeud. Le protocole TORA est déroulé pour chaque destination. Initialement, chaque noeud (autre que la destination) dispose d’une hauteur indéfinie (NULL), hauteur = (-, -, -, -, i).

La destination dispose d’une hauteur zéro, hauteur = (0, 0, 0, 0, j). Chaque noeud maintient, en plus de sa hauteur, toutes les hauteurs de ses voisin k, qui sont initialisées à NULL, à moins que la destination soit un de ces voisins, dans ce cas, elle est initialisée à zéro. Chaque noeud i maintient une table de statuts des liens avec ses voisins k. Le statut d’un lien est déterminé par la hauteur. Si la hauteur d’un voisin k est supérieure à celle du noeud i, le lien est marqué montant (UP). Si la hauteur y est inférieure, le lien est marqué descendant (DN). Si la hauteur du voisin k est NULL, le lien est marqué non dirigé. Enfin, si la hauteur du noeud i est NULL, le lien est marqué descendant (DN) avec tous les voisins qui ont une hauteur non NULL. Quand un noeud i établit un nouveau lien avec un voisin k, une nouvelle entrée est ajoutée à la table de hauteurs de ce noeud i, et est mise à la valeur NULL (-, -, -, -, k).

Mécanismes de création des routes

La table de routage de chaque noeud dans le protocole DSDV doit contenir la liste de toutes les destinations possibles ainsi que le nombre de hops pour les atteindre. Chaque route vers une destination est décrite par un numéro de séquence. Comme le réseau est mobile, les changements de topologie doivent être pns en considération dans les tables de routage. Pour cela, chaque noeud doit transmettre de façon périodique à tous ses voisins l’information sur sa table de routage et, surtout, chaque nouvelle mise-à-jour de celle-ci. Le processus de transmission des mises-à-jour est géré par le protocole DSDV de façon à apporter au noeud une connaissance quasiment continue de la topologie qui l’entoure. À chaque fois qu’un noeud détecte une nouvelle information sur la topologie (du fait d’un déplacement d’un noeud, nouvelle route vers une destination, nouveau numéro de séquence, … ), cette information est propagée après un certain délai. Ce délai est choisi comme décrit dans [36] de telle façon à ne pas se précipiter pour propager cette information au cas où une meilleure mise-à-jour arrive juste après. De cette manière, le débit des misesà- jour est limité. Les paquets de mises-à-jour contiennent des informations sur l’adresse de la destination, le nombre de hops nécessaires pour l’ atteindre, et le numéro de séquence de cette destination. Chaque noeud partage sa table de routage avec le réseau, où il inclut son numéro de séquence.

Table des matières

Résumé
Remerciements
Table des matières
Liste des tableaux
Liste des figures
Liste des symboles
Chapitre 1 – Introduction
Chapitre 2 – Les réseaux de capteurs sans fil
2.1 Introduction
2.2 Qu’est-ce qu’un nœud de capteur sans fil ?
2.2.1 Unité de traitement
2.2.2 Unité d’alimentation
2.2.3 Unité de communication
2.2.4 Unité de détection
2.3 Domaines d’utilisation des réseaux de capteurs sans fil
2.4 Le modèle OSI pour les réseaux de capteurs sans fil
2.4.1 Aspects de la couche Physique
2.4.2 Aspects de la couche MAC
2.4.3 Aspects de la couche réseau
2.4.4 Aspects de la couche de transport
2.4.5 Aspects de la couche d’application
2.5 Environnements de déploiement des RCSF
2.5.1 Le modèle espace libre
2.5.2 Le modèle Two-Ray Ground
2.5.3 Le modèle Shadowing
2.6 Description du système à l’étude
2.7 Conclusion
Chapitre 3 – Les protocoles de routage
3.1 Introduction
3.2 Les protocoles de routage utilisés dans les RCSF
3.2.1 Les protocoles propres aux RCSF
3.2.2 Les protocoles de routage ad hoc adaptés aux RCSF
3.3 Le protocole de routage AODV
3.3.1 Introduction au protocole AODV
3.3.2 Mécanismes de création des routes
3.3.3 Mécanismes de maintenance des routes
3.3.4 Caractéristiques supplémentaires
3.4 Le protocole de routage DSR
3.4.1 Introduction au protocole DSR
3.4.2 Mécanisme de création des routes
3.4.3 Mécanisme de maintenance des routes
3.4.4 Caractéristiques supplémentaires
3.5 Le protocole de routage TORA ……
3.5.1 Introduction au protocole TORA
3.5.2 Mécanismes de création des routes
3.5.3 Mécanismes de maintenance des routes
3.6 Le protocole de routage DSDV
3.6.1 Introduction au protocoles DSDV
3.6.2 Mécanismes de création des routes
3.6.3 Mécanismes de maintenance des routes
3.6.4 Caractéristiques supplémentaires
3.7 Le protocole de routage PUMA
3.7.1 Introduction au protocole PUMA
3.7.2 Mécanismes de création des routes
3.7.3 Mécanismes de maintenance des routes
3.8 Conclusion
Chapitre 4 – Les outils de simulation et environnement de test
4.1 Introduction
4.2 Le simulateur NS2
4.2.1 Introduction à NS2
4.2.2 Initialisation du simulateur
4.2.3 Les Agents
4.2.4 Les réseaux WLAN
4.2.5 Le modèle d’énergie
4.2.6 Démarrer NS2
4.2.7 Démarrer NAM
4.2.8 Le script TCL
4.2.9 Un nouveau protocole pour NS2
4.3 Ecrire le code Tel afin de définir le scénario de la simulation.Création d’un nouveau scénario dans NS2
4.3.1 Le script TCL
4.3.2 Fichiers de traçage des évènements
4.3.3 Traitement des fichiers de traçage
4.3.4 Exemple de simulation d’un réseau sans fil avec NS2
4.4 Conclusion
Chapitre 5 – Synthèse des résultats
5.1 Introduction
5.2 Les scénarios de simulation
5.3 Scénario 1
5.4 Scénario 2
5.5 Scénario 3
5.6 Scénario 4
5.7 Scénario 5 et 6
5.8 Scénario dans un environnement interne sans, ensuite avec mobilité
5.9 Critères d’évaluation des méthodes de routage
5.10 Résultats de simulations avec le modèle Two-Ray Ground
5.1 Résultats de simulations avec le modèle Shadowing
5.2 Résultats de simulations dans un environnement interne
5.3 Émulation de l’AODV dans un environnement interne et comparaison avec la simulation
5.3.1 Communications locales
5.3.2 Communications distantes
5.4 Conclusion
Chapitre 6 – Conclusion générale
Bibliographie
Annexe A – Le standard IEEE 802.15.4 (couches PHY et MAC)
La couche Physique (PHY
La couche MAC
Trame de données
Trame « Beacon
Trame d’acquittement (ACK
Trame de commande
Méthodes d’accès au canal
Structure de la Superframe
Valeurs par défaut de la Superframe
Chronologie des évènements
Base de temps
Annexe B – Scripts et codes
Code TCL pour la simulation du protocole AODV sous la couche MAC IEEE802.15.4
Attribution des positions de 2 nœuds
Script AWK pour l’AODV
Annexe C – Castalia Simulator
Le simulateur Castalia Simulator
Installation du logiciel Castalia Simulator
Caractéristiques du simulateur  
Composition d’un nœud de capteur selon Castalia Simulator
Annexe D – Le protocole de routage TBRPF (Topology broadcast based on reverse-path forwarding)  
Introduction au protocole TBRPF
Le module de découverte du voisinage
Les messages HELLO et la table de voisinage   
Le module de routage  
La table de routage  
Le message de maintenance de la topologie
Les opérations de routag

Télécharger le rapport complet