Etude et analyse de la stabilité des protocoles de routage dans les réseaux ad-hoc

Extrait du mémoire routage dans les réseaux ad-hoc

1.5.2 Protocoles Proactifs
Ce type d’algorithme est différent du précédant du fait qu’il est principalement basé sur la garde des tables de routage au niveau de chaque nœud du réseau. Chaque émetteur consulte sa table pour trouver une entrée vers la destination voulue.
Plusieurs algorithmes ont été proposés et même implémentés et testés. Exemple DSDV, CGSR, WRP et OLSR.
1.5.2.1 DSDV (Destination Sequenced Distance-Vector Routing [14])
Ce protocole est basé sur le mécanisme de routage classique de Bellman-Ford.
Chaque nœud du réseau maintient une table de routage vers toute destination possible. La mise à jour des tables de routage est faite périodiquement Pour alléger la charge du le réseau, il existe deux méthodes de mise à jour :
– Full dump : Des paquets transportant toute information disponible du routage et peut demander plusieurs NPDUs, leur transmission est occasionnelle.
– Incremental : Des paquets portent juste l’information de changement sur les tables de routage depuis la dernière mise à jour. Les nœuds maintiennent aussi une autre table où ils enregistrent les paquets envoyés.
1.5.2.2 CGSR (Clusterhead Gateway Switch Routing [17])
Ce protocole décompose la topologie en un groupe de clusters où dans chaque cluster un algorithme distribué est chargé d’élire un leader qui prend la responsabilité de tout le cluster (voir Figure 1.7). Plusieurs schémas de routage sont acceptés. L’allocation de la bande passante est aussi possible. CGSR utilise DSDV comme protocole de
routage fondamental, mais ici l’approche est hiérarchique où pour le routage il faut passer par les têtes de cluster. La gestion de ce système de têtes de cluster peut réduire les temps d’acheminements des paquets utiles. Une passerelle Gateway est le nœud chargé de router les paquets entre deux têtes de cluster. Le routage s’effectue dans l’ordre : Source – Tête de cluster – Gateway – ….. – Tête de cluster – Gateway –
Destination. Chaque nœud garde une table de membres de clusters et une autre table de routage. Elles sont mises à jour en utilisant DSDV. Avec ces deux tables chaque nœud sera en mesure de déterminer la tête de cluster le plus proche de sa destination.
Sur la figure 1.7, nous remarquons que le nœud 1 pour envoyer au nœud 8, il doit s’adresser à la tète de cluster auquel il appartient puis c’est elle qui prend en charge le reste du routage en passant par les Gateways et même d’autres têtes de clusters.
1.5.2.3 WRP (Wireless Routing Protocol)
Chaque nœud dispose de 4 tables
– Table de destination
– Table de routage
– Table des coûts des liens
– Table de la liste des messages à retransmettre (MRL)19
Chaque entrée de la table MRL contient :
– Numéro de séquence du message de mise à jour.
– Un compteur de retransmission.
– Un vecteur de flag des demandes d’acquittement avec une entrée par voisin.
– Une liste de mise à jour qui sera envoyée dans les messages de mise à jour
Les enregistrements de la MRL mis à jour depuis la réception d’un message de mise à jour doivent être retransmis aux voisins qui doivent accuser réception. Les messages sont envoyés seulement entre les nœuds voisins et contenant une liste de mise à jour (destination, distance à la destination, prédécesseur de la destination), aussi bien une liste de réponses indiquant quels nœuds devraient reconnaître la mise à jour. Les nœuds envoient des mises à jours après traitement de mise à jour reçue ou bien après  avoir détecter des changements dans les liens voisins. En cas de rupture de liens, un message de mise à jour est envoyé aux voisins qui à leurs tours mettent à jour leurs tables des distances et cherchent une nouvelle route par d’autres nœuds. Chaque changement est signalé par un message de mise à jour aux voisins. Sans les messages de mise à jours, les nœuds s’envoient mutuellement des paquets « hello » pour confirmer l’existence et la validité des liaisons sinon nous pourrions déduire qu’une liaison vient d’être perdu. Dans le cas d’une réception d’un nouveau « hello » envoyé par un nouveau nœud, nous l’insérons dans la table de routage et une copie de cette table sera envoyée au nouveau nœud. L’exception majeure de cet algorithme est qu’il évite le problème du « compte à l’infini » en obligeant chaque nœud d’effectuer des tests consistants sur les informations disponibles depuis les voisins.
Ainsi il n’y aura plus de boucle et un routage plus rapide est garanti.
1.5.2.4 OLSR (Optimized Link State Routing [16])
Protocole pro-actif présente une optimisation de « link state » dont:
– La réduction de l’impact de l’inondation sur le réseau, par la réduction du nombre de nœuds participants juste aux Multi-Points Relais [MPR], ce qui économise la bande passante.
– La minimisation de la taille des messages de contrôle, qui ne contiendront que l’information du voisinage de l’expéditeur mais pas de tous le réseaux.
– En plus des routes sans cycle qui sont garanties, OLSR offre des routes symétriques de plus court chemin.
Des paquets [TC] « Topology Control » sont périodiquement diffusés dans le réseau, ne transitent que par les [MPR] et ne contiennent que la liste des relais multipoints [MPR].
Un système d’élection des [MPR] est mis en place et chaque nœud élu reçoit l’information dans un message « hello ».
OLSR supporte l’adressage IP, où à chaque nœud est associé une adresse IP régulière, de plus il ne demande aucun changement sur le format des paquets IP. Le protocole n’intervient que sur la gestion de la table de routage.
1.5.3 Protocoles hybrides
Ce type de protocoles est un compromis entre les réactifs et les proactifs et ce sont des protocoles qui d’un côté utilisent une procédure de détermination de route sur demande mais de l’autre un coût de recherche limité.
ZRP (Zone Routing Protocol [18])
Le protocole ZRP est un modèle hybride entre un schéma proactif et un schéma réactif. Le principal problème dans l’élaboration d’un protocole de routage pour réseau ad hoc réside dans le fait que pour déterminer le parcours d’un paquet de données, le nœud source doit au moins connaître les informations permettant d’atteindre ses proches voisins (voir Figure 1.8 (a)). D’un autre côté, la topologie d’un tel réseau change fréquemment. De plus, comme le nombre de nœuds peut être élevé, le  nombre de destinations potentielles peut également l’être, ce qui requiert des échanges de données important et fréquents. Donc la quantité de données de mise à jour du trafic peut être conséquente. Cela est en contradiction avec le fait que toutes les mises à jour dans un réseau interconnecté ad hoc circulent dans l’air et donc sont coûteuses en ressources. Le protocole ZRP limite la procédure proactive uniquement aux nœud voisins et d’autre part, la recherche à travers le réseau (voir Figure 1.8 (b)),
est effectuée de manière efficace dans le réseau, contrairement à une recherche générale sur tout le réseau.
Sur la figure 1.8 (a), Le nœud source S est centré dans un grand cercle en pointillés qui délimite sa zone de routage à rayon 2, dans laquelle il se comporte comme les protocoles proactifs. Par contre, sur la figure 1.8 (b), pour atteindre sa destination D, le nœud S doit trouver le chemin avec des algorithmes réactifs parce que D est en dehors de sa zone de routage à rayon 2.
……..

Sommaire: Routage dans les réseaux ad-hoc

Table des matières
Liste des tableaux
Liste des graphiques
Liste des acronymes
Introduction
1. Description du projet
2. Objectifs du projet
3. Organisation du rapport
Chapitre 1. Les réseaux sans fil
1.1 Réseaux sans fil téléphonique (Couches de transport)
1.2 Réseaux sans fil informatiques
1.3 Les réseaux sans fil ad hoc
1.3.1 Caractéristiques des réseaux ad hoc
1.4 Le routage classique
1.4.1 Les Protocoles à État de Liaisons
1.4.2 Les protocoles à Vecteur de Distance
1.4.3 Source routing
1.4.4 Flooding
1.5 Protocoles de routage dans les réseaux ad hoc
1.5.1 Protocoles réactifs
1.5.1.1 AODV (ad hoc On-Demande Distance-Vector)
1.5.1.2 DSR (Dynamic Source Routing)
1.5.1.3 TORA (Tomporally Ordered Routing Algorithme)
1.5.2 Protocoles Proactifs
1.5.2.1 DSDV (Destination Sequenced Distance-Vector Routing)
1.5.2.2 CGSR (Clusterhead Gateway Switch Routing)
1.5.2.3 WRP (Wireless Routing Protocol)
1.5.2.4 OLSR (Optimized Link State Routing)
1.5.3 Protocoles hybrides
ZRP (Zone Routing Protocol)
1.6 Propriétés ciblées par les protocoles de routage des réseaux ad hoc
1.6.1 Distribution des opérations
1.6.2 Routes sans cycle
1.6.3 Opération à la demande
1.6.4 Liens unidirectionnels
1.6.5 La sécurité
1.6.6 Conservation d’énergie
1.6.7 Multi-routes
1.6.8 Le support de la qualité de service
1.7 Comparaison
Chapitre 2. Cadre Expérimental
Etude de simulation
2.1 Introduction
2.1.1 Les simulateurs de réseaux
2.1.1.1 Omnet ++
2.1.1.2 NS-2
2.1.1.3 SensorSIM
2.1.1.4 GlomoSim
2.1.1.5 QualNet
2.1.1.6 Jist / SWANS
2.1.1.7 JSim
2.1.1.8 Opnet Modeler
2.2 Simulateur NS
Chapitre 3. Étude de cadrage
3.1 Générateur de scripts
3.2 Paramètres de la simulation
3.2.1 Le modèle de topologie
3.2.2 Le modèle de propagation
3.2.3 Le modèle de trafic
3.2.4 Le modèle de mobilité
3.2.5 Le modèle d’énergie
3.3 Les variables de la simulation
3.3.1 Les protocoles simulés
3.3.2 Le nombre de nœuds
3.3.3 La mobilité
3.3.4 Les déplacements
3.3.5 Nombre de trafic TCP
3.3.6 Occupation de la bande passante
Chapitre 4. Calcul de la simulation
4.1 Métriques de simulation
4.1.1 Les paquets de control
4.1.2 Les paquets utiles
4.1.3 Les paquets perdus
4.1.4 Le trafic émis
4.1.5 Le trafic routé
4.1.6 Le temps d’attente forcé du médium
4.2. Variables de la simulation
4.2.1 Mobilité
4.2.2 Intensité de flux sortants
Chapitre 5. Résultats de la simulation
5.1 Résultats et discussions
5.1.1 Paquets de control (pqt/nœud)
5.1.2 Paquets utiles (pqt/nœud)
5.1.3 Paquets perdus (pqt/nœud)
5.1.4 Trafic émis (Koctet/nœud)
5.1.5 Trafic routé (Koctet/nœud)
5.1.6 Temps d’attente forcé du médium (Milliseconde/nœud)
5.2 Conclusions et perspectives
Bibliographie
Annexe A
Annexe B

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Etude et analyse de la stabilité des protocoles de routage dans les réseaux ad-hoc (1,20 MO) (Rapport PDF)
routage dans les réseaux ad-hoc

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *