DYMO Multi chemins à nœuds disjoints sans …Distance Vector) protocol to illustrate its benefits for WSN. The multipath routing under interferences influence has been slightly addressed

DEPARTEMENT D'INFORMATIQUE

MEMOIRE

Présenté par

BENDIMERAD Nawel

Pour obtenir

LE DIPLOME DE MAGISTER

Spécialité Informatique

Option : Analyse, Commande et Surveillance des Systèmes Industriels

Intitulé :

Soutenu le : / / à la salle de conférences de la Faculté des Sciences

Devant les membres du jury :

Président du jury KHELFI Mohamed Fayçal : Professeur - Université d’Oran

Encadreur HAFFAF Hafid : Professeur - Université d’Oran

Co-Encadreur KECHAR Bouabdellah : MA-A - Université d’Oran

Examinatrice MAIMOUR Moufida : MC-A - Université de Nancy I - France

Examinateur YAGOUBI Belabbas : MC-A - Université d’Oran

DYMO Multi-chemins à nœuds disjoints sans interférencespour les réseaux ZigBee/Standard IEEE 802.15.4

A mon père

Remerciements

ii

Remerciements

Je remercie en premier lieu Monsieur H. HAFFAF et Monsieur B. KECHAR, mes

directeurs de thèse pour m’avoir proposée ce passionnant sujet, pour leur encouragement,

leurs conseils et leur sympathie qui m’ont permis de mener à bien ce projet.

Je tiens particulièrement à témoigner ma profonde gratitude à Monsieur B. KECHAR,

pour sa disponibilité, son aide, ses critiques constructives, ses explications et suggestions et

surtout sa rigueur tout au long de la réalisation de ce projet.

Je remercie infiniment Monsieur M. F. KHELFI d’avoir accepté de présider le jury de

ce mémoire.

Je remercie très sincèrement Madame M. MAIMOUR ainsi que Monsieur B.

YAGOUBI pour l’immense honneur qu’ils me font en acceptant d’évaluer ce modeste travail.

Pour finir, merci à mes parents et à ma sœur dont les encouragements et la générosité

sont inestimables et à toute l’équipe «Analyse, Commande et Surveillance des Systèmes

Industriels» étudiants, enseignants et à leurs tête Monsieur L. SEKHRI.

Résumé

iii

Résumé

Nous proposons dans ce mémoire une amélioration du protocole DYMO (DYnamic

Manet On-demand), actuellement l’un des plus récents protocoles de routage réactifs mono-

chemin. Notre solution permet d’étendre ce protocole avec une approche de routage multi-

chemins dans une perspective de tolérance aux pannes dans les réseaux de capteurs sans fil

(RCSF) dont la topologie change fréquemment et d’assurer une qualité de service (QoS)

exprimée en termes de délai et de taux d’erreur. Nous avons implémenté et évalué également

cette approche de routage au préalable sur le protocole AODV (Ad hoc On-demand Distance

Vector) afin d’illustrer ses avantages pour les RCSF. Le routage multi-chemins avec la prise

en compte de l’interférence a été légèrement abordé dans ce mémoire.

Une analyse comparative des performances des protocoles de routage étudiés à l’aide du

simulateur NS2 montre clairement l’efficacité de l’approche multi-chemins combinée avec

des contraintes de QoS et son intérêt pour les RCSF. En effet, cette solution permet de résister

aux changements de topologie, réduire le trafic de contrôle ainsi que l’énergie consommée et

assurer un meilleur délai de transmission des données dans le réseau.

Mots Clés : Réseaux de capteurs sans fil, AODV, DYMO, routage multi-chemins, qualité de

service, évaluation de performance.

Abstract

iv

Abstract

In this thesis we propose an improvement of the protocol DYMO (DYnamic Manet On-

demand) which is currently one of the most recent reactive single path routing protocols. Our

solution allows to extend this protocol with a multipath routing approach in a fault tolerance

perspective for wireless sensor networks (WSN) with frequent topological changes and to

ensure a quality of service (QoS) in terms of delay and error rate metrics. We have also

implemented and evaluated this routing scheme previously on the AODV (Ad hoc On-demand

Distance Vector) protocol to illustrate its benefits for WSN. The multipath routing under

interferences influence has been slightly addressed in this thesis.

A comparative performance analysis of the routing protocols studied using NS2

simulator shows clearly the effectiveness of the multipath approach combined with QoS

constraints and his interest for WSN. In fact, this solution allows resisting to topological

changes, reducing traffic control and energy consumption and provides a better data

transmission delay in the network.

Keywords : Wireless sensor networks, AODV, DYMO, multipath routing, quality of service,

performance evaluation.

Table des matières

v

Table des matières

Remerciements............................................................................................... ii

Résumé............................................................................................................ iii

Abstract .......................................................................................................... iv

Table des matières .........................................................................................v

Liste des figures ............................................................................................. ix

Liste des tableaux .......................................................................................... xi

Liste des abréviations.................................................................................... xii

Introduction générale.................................................................................... 1

Chapitre I : Réseaux de Capteurs Sans Fil et Routage : Etat de l’art

I.1. Introduction ..................................................................................................................5I.2. Présentation des RCSF .................................................................................................5

I.2.1. Introduction aux réseaux Ad Hoc ......................................................................5I.2.2. Définition d’un RCSF .......................................................................................6I.2.3. Principaux types de RCSF ................................................................................7I.2.4. Architecture d’un nœud capteur ........................................................................8I.2.5. Systèmes d’exploitation pour les RCSF ............................................................9I.2.6. Communication dans les RCSF ........................................................................9I.2.7. Modèle de consommation d’énergie dans les RCSF .........................................11I.2.8. Facteurs et contraintes d’influence ....................................................................14I.2.9. Exemples de Standards MAC pour les RCSF ...................................................16I.2.10. Localisation des nœuds capteurs .....................................................................18I.2.11. Domaines d’applications .................................................................................19

I.3. Le routage dans les RCSF ............................................................................................21I.3.1. Protocoles de routage classés selon la structure du réseau ................................22

I.3.1.1. Routage linéaire ....................................................................................22I.3.1.2. Routage hiérarchique ............................................................................23I.3.1.3. Routage basé sur la localisation ............................................................23

I.3.2. Protocoles de routage classés selon le fonctionnement du réseau .....................23I.3.2.1. Routage basé sur la négociation............................................................24I.3.2.2. Routage basé sur les requêtes ...............................................................24I.3.2.3. Routage basé sur la cohérence ..............................................................24I.3.2.4. Routage basé sur la QoS .......................................................................24I.3.2.5. Routage basé sur l’approche multi-chemins .........................................26

I.3.3. Protocoles de routage classés selon le mécanisme de découverte de route .......30I.3.3.1. Classification des protocoles de routage Ad Hoc..................................30I.3.3.2. Description de quelques protocoles de routage MANET ......................32

I.4. Conclusion ...................................................................................................................35

Table des matières

vi

Chapitre II : Le protocole de routage AODV Multi-chemins avec Qualité

de Service

II.1. Introduction ................................................................................................................36II.2. Présentation du protocole de routage AODV ..............................................................36

II.2.1. Gestion de la table de routage..........................................................................37II.2.2. Découverte de route .........................................................................................38II.2.3. Maintenance de route.......................................................................................40

II.3. Présentation du protocole AODV_MQ .......................................................................41II.3.1. Format des messages de contrôle et de la table de routage de AODV_MQ......41

II.3.1.1. Le nouveau format du paquet RREQ ................................................41II.3.1.2. Le nouveau format du paquet RREP ................................................42II.3.1.3. La structure de la table de routage étendue ......................................42

II.3.2. Définition des métriques de QoS intégrées dans AODV_MQ ........................43II.3.2.1. Le délai (métrique additive) .............................................................43II.3.2.2. Le taux d’erreur (métrique multiplicative) .......................................44

II.3.3. Découverte de routes multiples avec AODV_MQ ..........................................45II.3.3.1. Traitement du paquet RREQ ............................................................46II.3.3.2. Traitement du paquet RREP ............................................................49

II.3.4. Découverte de routes multiples avec la prise en compte de l’interférence ...50II.3.5. Maintenance de routes ...................................................................................53

II.4. Conclusion ..................................................................................................................53

Chapitre III : Le protocole de routage DYMO Multi-chemins avec Qualité

de Service

III.1. Introduction ...............................................................................................................54III.2. Présentation du protocole de routage DYMO ............................................................54

III.2.1. Origines de DYMO .......................................................................................55III.2.2. Principe de fonctionnement..........................................................................55III.2.3. Format des messages DYMO ........................................................................56

III.2.3.1. Structure générale d’un message DYMO .....................................56III.2.3.2. Structure des messages de routage (MR)......................................56III.2.3.3. Structure du message d’erreur de route (RERR) ..........................57III.2.3.4. Exemple d’un MR.........................................................................58

III.2.4. Les opérations de la table de routage ...........................................................61III.2.4.1. Structure de la table de routage ....................................................61III.2.4.2. Evaluation de la validité des informations de routage .................62

III.2.5. La phase de découverte de route ..................................................................63III.2.5.1. Le rôle du nœud source ................................................................63III.2.5.2. Le rôle d’un nœud intermédiaire .................................................64III.2.5.3. Le rôle du nœud destinataire ........................................................64III.2.5.4. Exemple d’une procédure de découverte de route .......................65

III.2.6. La phase de maintenance de route ...............................................................66III.2.6.1. La gestion des liens actifs.............................................................66III.2.6.2. La génération d’un RERR.............................................................66III.2.6.3. Le traitement d’un RERR .............................................................67

Table des matières

vii

III.2.6.4. Exemple de dissémination d’un RERR.........................................68III.3. Présentation du protocole de routage DYMO_MQ....................................................69

III.3.1. Les extensions apportées aux MR et à la table de routage ...........................69III.3.1.1. Le nouveau format du message RREQ.........................................69III.3.1.2. Le nouveau format de la table de routage ....................................70

III.3.2. La découverte de routes multiples disjointes ...............................................71III.3.2.1. Traitement d’un MR par un nœud intermédiaire ..........................71III.3.2.2. Traitement d’un MR par un nœud destinataire .............................74

III.3.3. La maintenance de routes .............................................................................75III.4. Conclusion .................................................................................................................76

Chapitre IV : Implémentation et évaluation des performances

IV.1. Introduction ...............................................................................................................77IV.2. Implémentation du protocole de routage DYMO ......................................................77IV.3. Principales extensions apportées au protocole de routage DYMO............................80

IV.3.1. L’établissement de routes multiples.............................................................80IV.3.2. La sélection des chemins à nœuds disjoints .................................................82IV.3.3. L’intégration des contraintes de QoS ...........................................................84

IV.4. Extensions apportées pour le calcul du taux d’interférences dans AODV_M...........84IV.5. Environnement de simulation ...................................................................................85

IV.5.1. Présentation du simulateur NS2 ...................................................................85IV.5.2. Paramètres de simulation .............................................................................86IV.5.3. Les métriques de performance .....................................................................87

IV.6. Résultats d’évaluation et interprétations ...................................................................88IV.6.1. Variation de la densité du réseau .................................................................89

IV.6.1.1. Comparaison entre AODV, AODV_M et AODV_MQ.................89IV.6.1.2. Comparaison entre DYMO, DYMO_M et DYMO_MQ................92IV.6.1.3. Comparaison entre AODV et DYMO ..........................................94IV.6.1.4. Comparaison entre AODV_M et DYMO_M ................................97IV.6.1.5. Comparaison entre AODV_MQ et DYMO_MQ ..........................99

IV.6.2. Variation de la vitesse de déplacement des nœuds (mobilité) .....................102IV.6.2.1. Comparaison entre AODV et DYMO ...........................................102IV.6.2.2. Comparaison entre AODV_MQ et DYMO_MQ ...........................104

IV.6.3. Impact de la variation du seuil de tolérance d’interférence .........................106IV.7. Conclusion ................................................................................................................107

Conclusion générale ...................................................................................... 108

Perspectives .................................................................................................... 110

Bibliographie.................................................................................................. 111

Annexe A : Le simulateur NS2 : Aperçu du logiciel

A.1. Présentation ................................................................................................................116A.2. Architecture et implémentation ..................................................................................118A.3. La mobilité dans NS2 .................................................................................................119

Table des matières

viii

A.4. Présentation du langage Tcl........................................................................................120A.5. Technique de simulation ............................................................................................121A.6. Exemple d’un script Tcl d’un réseau de 100 nœuds ...................................................121

Annexe B : Le Langage AWK

B.1. Présentation ................................................................................................................126B.2. Syntaxe générale d’un programme AWK....................................................................126B.3. Exécution d’un programme AWK ...............................................................................127B.4. Script AWK de calcul des métriques de performance .................................................127

Annexe C : Installation et configuration du protocole DYMO

C.1. Introduction ...............................................................................................................130C.2. Etapes d’installation de DYMOUM ............................................................................130C.3. Configuration de DYMOUM ......................................................................................131

Liste des figures

ix

Liste des figures

I.1 : Exemples de nœuds capteurs .................................................................................7I.2 : Architecture d’un nœud capteur ............................................................................8I.3 : Architecture générale d’un RCSF ..........................................................................10I.4 : La pile protocolaire d’un RCSF.............................................................................11I.5 : Consommation de l’énergie au sein d’un nœud capteur........................................11I.6 : L’énergie consommée par un nœud capteur pour l’émission et la réception d’un

message de k bits ...................................................................................................12I.7 : Consommation de l’énergie électrique par un nœud capteur ................................13I.8 : ZigBee par rapport aux autres Standards ...............................................................17I.9 : Différence entre l’alliance ZigBee et le Standard 802.15.4 ...................................18I.10 : Taxonomie des protocoles de routage dans les RCSF ...........................................22I.11 : Les types de routage multi-chemins ......................................................................28I.12 : Emission d’un paquet dans le cas du routage par la source...................................34

II.1 : Format générale d’un paquet RREQ ......................................................................38II.2 : Format générale d’un RREP ..................................................................................39II.3 : Etablissement d’une route entre S et D ..................................................................39II.4 : Le nouveau format du paquet RREQ .....................................................................41II.5 : Le nouveau format du paquet RREP ......................................................................42II.6 : La structure étendue de la table de routage ............................................................42II.7 : Vérification du délai de transmission d’un chemin ...............................................44II.8 : Procédure de découverte de chemins avec une diffusion minimale ......................45II.9 : Organigramme de la réduction de diffusion des paquets RREQ ............................47II.10 : Organigramme de la sélection des chemins disjoints ........................................... 48II.11 : Organigramme de traitement d’un message RREP ................................................50II.12 : Format d’un message RREP pour le calcul du taux d’interférences......................51II.13 : Transmission des messages RREP et calcul du taux d’interférences.....................52

III.1 : Format d’un message DYMO .................................................................................56III.2 : Exemple d’un message DYMO de demande de route ............................................58III.3 : Format de la table de routage de DYMO ................................................................61III.4 : Le processus de découverte de route avec DYMO .................................................65III.5 : Génération et diffusion d’un message RERR .........................................................68III.6 : Le nouveau format d’un message de routage de type RREQ .................................70III.7 : La structure étendue de la table de routage ............................................................70III.8 : Organigramme de traitement d’un MR par un nœud intermédiaire .......................73III.9 : Organigramme de traitement d’un MR par un nœud destinataire ..........................75

IV.1 : DYMOUM : l’implémentation de DYMO................................................................79IV.2 : Procédure modifiée pour l’établissement de routes multiples, extraite de la classe

« dymo_re.h »..........................................................................................................80

Liste des figures

x

IV.3 : Procédure modifiée pour la sauvegarde de plusieurs entrées, extraite de la classe« dymo_re.c » ..........................................................................................................82

IV.4 : Procédure ajoutée pour le calcul du nombre de routes, extraite de la classe« rtable.c »...............................................................................................................82

IV.5 : Procédure ajoutée pour la sélection des chemins à nœuds disjoints, extraite de laclasse « dymo_re.c »................................................................................................83

IV.6 : Procédure ajoutée pour la sauvegarde des chemins disjoints dans le cache, extraitede la classe « dymo_re.c »......................................................................................83

IV.7 : Procédure ajoutée pour la vérification de la disjonction des chemins, extraite de laclasse « dymo_re.c »................................................................................................84

IV.8 : Test pour la vérification des contraintes de QoS, extrait de la classe« dymo_re.c » ..........................................................................................................84

IV.9 : Test pour le calcul du taux d’interférences, extrait de la classe « aodv.cc » ..........85IV.10 : Comparaison des performances entre AODV, AODV_M et AODV_MQ avec la

variation de la densité du réseau ............................................................................92IV.11 : Comparaison des performances entre DYMO, DYMO_M et DYMO_MQ avec la

variation de la densité du réseau .............................................................................94IV.12 : Comparaison des performances entre AODV et DYMO avec la variation de la

densité du réseau .....................................................................................................97IV.13 : Comparaison des performances entre AODV_M et DYMO_M avec la variation

de la densité du réseau .............................................................................................99IV.14 : Comparaison des performances entre AODV_MQ et DYMO_MQ avec la variation

de la densité du réseau .............................................................................................101IV.15 : Comparaison des performances entre AODV et DYMO avec la variation de la

mobilité des nœuds ..................................................................................................104IV.16 : Comparaison des performances entre AODV_MQ et DYMO_MQ avec la variation

de la mobilité des nœuds .........................................................................................106IV.17 : Le nombre de chemins trouvés par rapport au seuil de tolérance...........................107

A.1 : Cycle d’une simulation............................................................................................117A.2 : Structure d’un nœud mobile dans NS2....................................................................120

Liste des tableaux

xi

Liste des tableaux

I.1 : L’énergie dissipée par les principales fonctions d’un capteur.....................................14

IV.1 : Les paramètres de configuration de DYMOUM ...................................................... ....79IV.2 : Les paramètres de simulation .................................................................................. ....87IV.3 : Les différentes comparaisons pour l’évaluation ...................................................... ....89

A.1 : Principaux composants disponibles dans NS2.............................................................116

Liste des abréviations

xii


ADC Analog to Digital Converter

AODV Ad Hoc On-demand Distance Vector

AODV_M Ad Hoc On-demand Distance Vector Multipath

AODV_MQ Ad Hoc On-demand Distance Vector Multipath with Quality of service

AOMDV Ad Hoc On-demand Multipath Distance Vector

CGSR Clusterhead Gateway Switch Routing

CSMA/CA Carrier Sense Multiple Access with Collision Avoidance

DD Directed Diffusion

DSDV Dynamic destination Sequenced Distance Vector

DSR Dynamic Source Routing

DYMO DYnamic Manet On-demand

DYMO_M DYnamic Manet On-demand Multipath

DYMO_MQ DYnamic Manet On-demand Multipath with Quality of service

FFD Full Function Device

GAF Geographic adaptive fidelity

GEAR Geographic and Energy Aware Routing

GPS Global Positioning System

HSLS Hazy Sighted Link State

IEEE Institute of Electrical and Electronics Engineers

IETF Internet Engineering Task Force

IP Internet protocol

LEACH Low-Energy Adaptive Clustering Hierarchy

MAC Medium Access Control

MANET Mobile Ad hoc NETwork

MDYMO Multipath DYnamic Manet On-demand

MPR Multi Point Relay

MR Message de Routage

NAM Network AniMator

NDMR Node-Disjoint Multipath Routing

NS2 Network Simulator 2


xiii

OLSR Optimized Link State Routing

OTCL Object Tool Command Language

PEGASIS Power Efficient GAthering in Sensor Information Systems

QoS Quality of Service

RCSF Réseau de Capteurs Sans Fil

RERR Route ERRor

RFC Requests For Comments

RFD Reduced Function Device

RREP Route REPly

RREQ Route REQuest

SAR Sequential Assignment Routing

SMR Split Multipath Routing

SPIN Sensor Protocols for Information via Negotiation

TCL Tool Command Language

TLV Type Length Value

TORA Temporally-Ordered Routing Algorithm

UDP User Datagram Protocol

WLAN Wireless Local Area Networks

WPAN Wireless Personal Area Networks

WRP Wireless Routing Protocol

ZRP Zone Routing Protocol

Introduction générale

1


Au cours de ces dernières décennies, nous avons assisté à une miniaturisation du

matériel informatique. Cette tendance à la miniaturisation a apporté une nouvelle génération

de réseaux informatiques et télécoms présentant des défis importants. Les réseaux de capteurs

sans fil : RCSF (en anglais Wireless Sensor Networks : WSN) en sont l’une des technologies

visant à résoudre les problèmes de cette nouvelle ère de l’informatique omniprésente.

Les RCSF constituent une catégorie de réseaux sans fil comportant un très grand

nombre de nœuds. Ils sont également caractérisés entre autre par un déploiement très dense et

à grande échelle dans des environnements complexes, hostiles où la présence humaine est

presque impossible. Les nœuds capteurs déployés dans une zone à observer sont utilisés pour

l’acquisition des données et leur transmission à une station de traitement appelée

communément « Station de Base » ou « Sink ». En raison de leur petite taille, les ressources

disponibles sur un capteur sont très limitées, et la gestion d’énergie devient donc une

préoccupation de premier ordre.

Sur le plan applicatif, les RCSF ont connu un très grand succès, car ils détiennent un

potentiel qui révolutionne de nombreux secteurs de notre économie et notre vie quotidienne,

de la surveillance et la préservation de l’environnement, à la fabrication industrielle, en

passant par l’automatisation dans les secteurs de transport et de la santé, la modernisation de

la médecine, de l’agriculture, de la télématique et de la logistique.

Vu l’importance de ce type de réseau, de nombreuses recherches ont été menées plus

particulièrement sur les différentes couches protocolaires. Celles-ci visent essentiellement

deux objectifs : limiter la consommation énergétique et garantir une qualité de service (QoS).

L’introduction de la QoS dans les RCSF a été motivée d’une part, par l’apparition de

nouveaux capteurs équipés de dispositifs multimédia miniaturisés, capables de collecter des

données multimédia (image, son et vidéo) dont le transfert via le réseau doit obéir à certaines

métriques de QoS telles que la bande passante, délai, gigue, taux d’erreur, etc. D’autre part,

par l’existence d’applications typiques de surveillance de données critiques sensibles au

temps de réponse (délai) et exigeant une fiabilité de bout en bout dans la livraison des

données (taux d’erreur).


2

Pour atteindre les deux objectifs cités ci-dessus, un des défis majeurs rencontrés dans ce

type de réseaux est le développement de protocoles de routage efficaces pouvant garantir une

communication de qualité entre les différents nœuds du réseau.

A partir des caractéristiques peu communes de ces réseaux, de nombreux protocoles de

routage ont été proposés. En effet, certains travaux ont innové en proposant de nouvelles

solutions typiquement pour les RCSF. Par contre, d’autres investigations ont essayé d’adapter

les protocoles de routage des réseaux Ad Hoc pour les RCSF tels que le protocole de routage

réactif AODV.

Cependant, Une limitation de ces protocoles mono-chemin « unipath » est qu’ils ne

construisent qu’une seule route entre la source et la destination. Ainsi, lorsque la route tombe

en panne, les nœuds intermédiaires suppriment les paquets de données car ils ne disposent pas

d’une route alternative. Pour reprendre la transmission, la source sera obligée de lancer une

nouvelle découverte de route, ce qui entraine une augmentation du délai de bout en bout.

Une autre approche de protocoles permet de construire et de maintenir plusieurs routes

entre la source et la destination. Ce sont des protocoles multi-chemins « multipath ». Leur

objectif est d’augmenter la robustesse et la disponibilité des routes afin d’assurer plus de

fiabilité et d’économiser l’énergie consommée dans le réseau.

Les objectifs visés dans ce travail peuvent être résumés comme suit :

Etudier le protocole DYMO (DYnamic Manet On-demand) qui représente l’une des plus

récentes propositions en matière de routage pour les réseaux MANET. Il s’agit en quelque

sorte du successeur et de la fusion d’AODV et de DSR.

Apporter les extensions nécessaires à ce nouveau protocole pour la prise en compte de

multiples chemins à nœuds disjoints qu’on appelle aussi « chemins totalement disjoints »,

car ils ont ni nœuds ni liens en commun donc ils assurent une meilleure fiabilité en cas de

panne. Les chemins multiples peuvent être exploités soit d’une manière alternative, c’est-

à-dire, à un moment donné un seul chemin sera choisi, ou bien simultanément pour

l’équilibrage des charges dans le réseau. Dans le cadre de ce travail, nous avons adopté

l’approche alternative pour la tolérance aux pannes.

Augmenter le protocole DYMO Multi-chemins par des contraintes de QoS exprimées en

termes de délai et de taux d’erreur afin que ce nouveau protocole développé DYMO_MQ

(DYMO Multi-chemins avec QoS) puisse assurer plus de fiabilité de transmission des

données tout en prenant en considération les contraintes liées aux RCSF.


3

Etudier également le protocole AODV_MQ (AODV Multi-chemins avec QoS) qui a déjà

été proposé [1]. Cependant, nous avons revue et apporté des modifications au code source

de ce protocole pour garantir un routage multi-chemins efficace à nœuds disjoints avec les

mêmes contraintes de QoS que celles imposées par le protocole DYMO_MQ afin de

pouvoir effectuer par la suite une comparaison entre les deux protocoles. Ceux-ci sont

adaptés pour les RCSF où le changement de topologie est relativement fréquent.

Evaluer l’impact de l’interférence pour AODV_M sur la découverte de chemins multiples

et non pas sur leur exploitation (l’étude de cet aspect n’a pas été menée en profondeur, car

il est plus judicieux d’évaluer l’interférence engendrée dans le réseau dans le cas où les

chemins sont exploités en parallèle).

Enfin, prouver l’efficacité de l’approche multi-chemins combinée avec des contraintes de

QoS et évaluer les performances des protocoles de routage étudiés AODV_MQ et

DYMO_MQ à l’aide du simulateur NS2.

Le présent mémoire est organisé en quatre chapitres :

Dans le premier chapitre, nous proposons un état de l’art sur les RCSF par l’introduction

des différentes notions et concepts gravitant autour de cette thématique pour bien comprendre

leur fonctionnement ainsi que leurs différentes contraintes. Une attention particulière est

portée ensuite aux différentes techniques de routage dans ce type de réseau en mettant

l’accent sur le routage réactif multi-chemins avec QoS qui fait l’objet de cette étude.

Dans le deuxième chapitre, nous présenterons le protocole de routage AODV_MQ, la

version multi-chemins de AODV avec QoS. Nous allons d’abord décrire le protocole AODV

d’origine avec ses différentes techniques de routage. Nous exposerons en détail la procédure

de découverte de routes par AODV_MQ en explicitant les différents mécanismes de routages

utilisés tels que l’accumulation des chemins avec une diffusion minimale et l’intégration des

contraintes de QoS. Enfin, nous proposerons également une approche d’évaluation du taux

d’interférence pour AODV_M.

Le troisième chapitre est consacré au protocole de routage DYMO ainsi que sa version

multi-chemins avec QoS. Dans un premier temps, nous décrirons le protocole DYMO sous sa

version originale. Nous présenterons le nouveau format des messages de contrôle utilisés et le

détail des mécanismes de découverte et de maintenance de route mis en jeu dans le routage

avec ce protocole. Par la suite, nous détaillerons notre propre contribution basée sur le


4

protocole DYMO afin de le rendre multi-chemins avec QoS. Nous expliquerons notre stratégie

de découverte de routes multiples ainsi que la procédure de sélection des chemins disjoints.

Le quatrième chapitre constitue la partie implémentation et évaluation des performances

des protocoles de routage étudiés dans les chapitres précédents. Nous présenterons l’analyse

et les interprétations des différents résultats obtenus à l’aide du simulateur NS2 qui ont été

réalisées avec les protocoles de routage à chemin unique ainsi que leur version multi-chemins

avec QoS.

Nous terminons ce mémoire par une conclusion générale et quelques perspectives de

recherche futures.

Chapitre I. Réseaux de Capteurs Sans Fil et Routage : Etat de l’art

5

Chapitre I

Réseaux de Capteurs Sans Fil et Routage :Etat de l’art

I.1. Introduction

Les RCSF présentent un intérêt considérable et une nouvelle étape dans l’évolution des

technologies de l’information et de la communication. Cette nouvelle technologie suscite un

intérêt croissant vu la diversité de ses applications : santé, environnement, industrie, etc.

Dans la première partie de ce chapitre, nous présentons les RCSF, leur architecture de

communication, leurs différentes contraintes ainsi que leurs diverses applications.

Vue les ressources limitées de ce type de réseau et dont l’autonomie et la mobilité sont

d’une grande influence sur la procédure d’acheminement des données (routage) qui a fait

l’objet de notre étude. Nous consacrons la deuxième partie de ce chapitre aux différentes

techniques de routage utilisées par les RCSF.

I.2. Présentation des RCSF

Comme les RCSF sont considérés comme un type spécial de réseaux Ad Hoc, nous

allons d’abord commencer par une introduction sur les réseaux Ad Hoc et nous exposerons

ensuite d’une manière générale les notions de base sur les RCSF, afin d’en comprendre les

principes de ce type de réseaux, les caractéristiques et les facteurs qui influencent la

conception de ces réseaux.

I.2.1. Introduction aux réseaux Ad Hoc

Un réseau mobile Ad Hoc appelé généralement MANET (Mobile Ad hoc NETwork),

peut être défini comme une collection d’entités mobiles interconnectées par une technologie

sans fil, formant un réseau temporaire sans l’aide d’une infrastructure préexistante ou

d’administration centralisée [2] [3]. Ce sont les entités mobiles elles-mêmes qui forment,

d’une manière Ad Hoc, une infrastructure du réseau.


6

Les entités qui composent ce réseau possèdent un dispositif de communication sans fil

leur permettant de communiquer avec les entités situées dans leur voisinage. Chaque nœud

peut joindre directement ses voisins en utilisant son interface radio. Un nœud a la possibilité

d’atteindre n’importe quel autre nœud à l’intérieur du réseau en utilisant les nœuds

intermédiaires (situés entre la source et la destination) qui agissent en tant que nœuds relais.

Avec ce mode de fonctionnement, il est possible d’utiliser des protocoles de routage

proactifs, réactifs ou hybrides (voir section I.3.3.1 (pp. 30)).

Les réseaux Ad Hoc sont idéaux pour les applications caractérisées par une absence ou

la non fiabilité d’une infrastructure préexistante, telles que les applications militaires, les

opérations de secours (incendies, tremblement de terre, etc.) et les missions d’exploration [4].

I.2.2. Définition d’un RCSF

Un RCSF est un réseau de type Ad Hoc, constitué de nombreux dispositifs très petits

nommés « nœuds capteurs » variant de quelques dizaines d’éléments à plusieurs centaines [5],

parfois plus, communiquant généralement par ondes radio, ayant une zone de couverture

extrêmement réduite et déployés de manière très dense dans des environnements aussi

diverses qu’une maison, un commerce, un entrepôt, une ville, ou encore des environnements

hostiles comme un terrain militaire, un volcan, un site de tremblement de terre, ou même une

forêt.

La topologie Ad Hoc de ces réseaux provient en particulier de l’épuisement progressif

des batteries des capteurs, ce qui modifie la topologie du réseau au cours du temps.

Chaque nœud dans un RCSF est capable de détecter son environnement et de traiter les

données collectées au niveau local ou de les envoyer à un ou plusieurs points de collecte

appelés puits (ou Sink), à l’aide d’une communication sans fil [6] et dispose d’une source

énergétique ayant une durée de vie limitée et dont le remplacement ou le rechargement peut

s’avérer difficile ou parfois impossible.

Puisque la communication est consommatrice d’énergie, elle doit prendre en compte la

dégradation en énergie de chaque nœud participant au réseau en réalisant le maximum de

tâches tout en dépensant le moins possible d’énergie.

Les RCSF peuvent apporter de nombreux avantages pour une grande diversité de

secteurs d’application, comme la surveillance environnementale et de l’habitat, le contrôle de

la circulation et même l’amélioration des soins de santé.


7

I.2.3. Principaux types de RCSF

Il existe deux grands types de RCSF [7] :

Soit le réseau est constitué d’un ensemble de capteurs mobiles (figure I.1.a) évoluant dans

un environnement statique. Le but de tels réseaux est la plupart du temps l’exploration de

zones inaccessibles ou dangereuses. Les travaux de recherche sont souvent orientés

robotique, les nœuds jouant à la fois le rôle de capteur et d’actionneur.

Soit le réseau est constitué de nœuds capteurs stationnaires (figure I.1.b) servant à la

surveillance d’occurrence d’évènements sur une zone géographique. Ici, le réseau

n’effectue que la surveillance, les données mesurées sont acheminées en mode multi-sauts

vers le Sink qui est chargé, après réception, de mettre en œuvre les actions nécessaires. Le

Sink peut être connecté de manière filaire par exemple, à un autre réseau.

Remarque : Notre étude traite le problème du routage plus particulièrement dans les RCSF

mobiles.

a. Nœuds capteurs mobiles b. Nœuds capteurs stationnaires

Figure I.1 : Exemples de nœuds capteurs [8].


8

I.2.4. Architecture d’un nœud capteur

Un nœud capteur est constitué de quatre composantes principales illustrées sur la figure

I.2 suivante :

Unité de capture Unité de traitement

Alimentation en énergieTransfert de données

Figure I.2: Architecture d’un nœud capteur [9].

Unité de détection (sensing unit) : elle est composée de deux sous-unités. La première

est la sous-unité de capture constituée d’un ou de plusieurs capteurs selon la nature de la

cible à observer. Par exemple on peut avoir au sein d’un seul nœud capteur deux capteurs,

un pour la température et l’autre pour la pression. La deuxième sous-unité appelée ADC

(Analog to Digital Converter) qui permet de convertir le signal analogique produit par le

capteur, sur la base du phénomène observé, en un signal digital qui est par la suite fournit

à l’unité de calcul.

Unité de calcul (processing unit) : elle est généralement associée à une petite mémoire

pour le stockage des programmes. Elle gère les procédures permettant au nœud capteur de

collaborer avec les autres nœuds capteurs pour accomplir la requête assignée.

Unité de puissance(Batterie)

Capteur ADC

Mémoire

Processeur Transcei-ver

(ModuleRF)

Système de localisation del’environnement

Système de mobilité

Sourced’énergieexterne

ProtocolesNiveauLiaison

ProtocolesRéseau

Algorithmesd’agrégationde données


9

Unité radio (Transceiver unit) : elle est composée d’un circuit pour la réception des

messages, d’un circuit pour l’envoie des messages ainsi qu’un circuit pour amplifier le

signal. Notons que cette unité est celle qui consomme le plus d’énergie.

Unité d’énergie (power unit) : c’est une composante importante du nœud capteur sous la

forme d’une batterie. Elle fournie l’énergie nécessaire aux différentes unités pour

l’accomplissement de leurs tâches.

Selon les applications, il peut y avoir d’autres unités telles que [4]:

Unité de localisation (location finding system) : elle fournit des informations sur la

localisation (GPS : Global Positionning System) requise par certains protocoles.

Unité de mobilité (mobilizer) : elle est indispensable si le nœud capteur doit se déplacer

pour exécuter une tâche.

Unité de génération de puissance (power generator) : elle permet de générer de

l’énergie à partir de l’environnement (énergie solaire, énergie vibrationnelle, etc.).

I.2.5. Systèmes d’exploitation pour les RCSF

Les systèmes d’exploitation pour les RCSF sont des systèmes temps réel configurables

pour une tâche donnée et pour optimiser l’utilisation des ressources. Plusieurs systèmes

d’exploitation ont été proposés pour les RCSF parmi lesquels on trouve TinyOS [10], SOS

[11], Contiki [12], MANTIS [13]. TinyOS reste néanmoins le plus répandu pour les RCSF car

il répond aux exigences particulières des applications des RCSF. Il convient alors de

mentionner les propriétés qui rendent TinyOS aussi populaire pour ce genre de réseau [14] :

Une taille de mémoire réduite,

Une basse consommation d’énergie,

Des opérations robustes,

Applications orientées composants : TinyOS fournit une réserve de composants systèmes

utilisables au besoin,

Programmation orientée évènement : Généralement sur TinyOS, un programme s’exécute

suivant le déclenchement des événements. Sinon, les capteurs restent en veille ce qui

maximise la durée de vie du réseau.

I.2.6. Communication dans les RCSF

Les nœuds capteurs sont habituellement dispersés dans un environnement comme le

montre la figure I.3. Les nœuds capteurs ont des possibilités de rassembler des données et de

les acheminer vers le Sink, par une architecture multi-sauts. Le Sink peut communiquer avec


10

l’utilisateur final ou le décideur (Task Manager Node) par l’intermédiaire d’un réseau de

transport tel que l’Internet ou le satellite.

Figure I.3 : Architecture générale d’un RCSF [9].

La pile protocolaire d’un nœud capteur comprend les couches application, transport,

réseau, liaison de données et physique ; Ainsi que trois plans de gestion : le gestionnaire

d’énergie, le gestionnaire de mobilité et le gestionnaire des tâches (voir figure I.4).

Selon les tâches de capture, différents types de logiciel d’application peuvent être

établis et employés sur la couche application. La couche réseau prend le soin d’acheminer les

données fournies par la couche transport. Les algorithmes de routage doivent être économes

ou efficace en énergie. Puisque, l’environnement est bruyant et les nœuds capteurs peuvent

être mobiles, le protocole MAC doit être capable de réduire au minimum les collisions causées

par les émissions entre voisins. La couche physique adresse les besoins d’une modulation

simple et robuste, ainsi que des techniques de transmission et de réception. En outre, le

gestionnaire de puissance contrôle comment le nœud capteur emploie son énergie et comment

celle-ci est distribuée aux différentes unités qui composent le nœud capteur. Le gestionnaire

de mobilité surveille le voisinage pour savoir si un nœud capteur s’ajoute à son voisinage. Le

gestionnaire des tâches gère les tâches accomplies par le nœud capteur. Par exemple s’il y a

plusieurs nœuds capteurs pour observer le même objectif, il vaut mieux laisser cette tâche à

quelques nœuds capteurs seulement pour économiser de l’énergie.

Sink

Communicationmulti-sauts

Nœudscapteurs

La zone de déploiement

Station desupervision

Utilisateur


11

Figure I.4 : La pile protocolaire d’un RCSF [15].

I.2.7. Modèle de consommation d’énergie dans les RCSF

Un nœud capteur utilise son énergie pour réaliser trois actions principales comme le

montre la figure I.5:

L’acquisition des données,

La communication,

Le traitement des données.

L’énergie totale consommée par un nœud capteur est donnée par la formule suivante [16] :

traitementréceptionontransmissicapturetotal EEEEE (I.1)

Figure I.5 : Consommation de l’énergie au sein d’un nœud capteur [4].

1. Acquisition : l’énergie consommée pour effectuer l’acquisition des données scalaires n’est

pas très importante. Néanmoins, elle varie en fonction du phénomène observé et du type des

données collectées.

2. Communication : l’énergie totale pour la communication est la somme de l’énergie

consommée par le circuit de transmission, l’amplificateur (dont le but est d’amplifier le signal

selon la distance séparant l’émetteur et le récepteur), et le circuit de réception (voir figure I.6).

Modèle deBatterie

(Capacité limitée)

Modèle Capteur(Acquisition des données)

Modèle Radio(Communication)

Modèle CPU(Traitement des données)


12

d),( dkETx

Figure I.6 : L’énergie consommée par un nœud capteur pour l’émission et la réception d’un

message de k bits [15].

L’énergie consommée pour émettre un message de k bits sur une distance d est donnée

par la formule suivante [15] :

),()(),( dkEkEdkE ampTxTxTx (I.2)

L’énergie consommée pour recevoir un message de k bits est donnée par la formule

suivante [15] :

kEkE elecRx *)( (I.3)

Avec :

ampTxE : énergie d’amplification,

k : taille d’un message,

d : distance entre le nœud capteur « émetteur » et le nœud capteur « récepteur »,

Eelec : énergie de transmission/réception électronique,

Par conséquent, l’énergie consommée pour la transmission d’un message de k bits entre

deux nœuds capteurs avec une distance d est égale à :

)(),( kEdkEE RxTxTotal )(),()( kEdkEkEE RxampTxTxTotal (I.4)

)()()( 2 kEdkEkEE elecampTxelecTotal

)(kERx

kEelec *

),( dkETx

kEelec * 2** dkE ampTx

Circuit deRéception

Circuit deTransmission

Circuitd’Amplification

Paquet de K bits Paquet de K bits

Emetteur Récepteur

d


13

RADIO

On remarque que la transmission est l’opération qui consomme le plus d’énergie à cause

du facteur d’amplification.

3. Traitement des données :

L’énergie consommée pour les opérations de calcul est beaucoup plus faible que

l’énergie de communication car les données traitées en général par les RCSF que nous

considérons dans ce mémoire sont de type scalaire (température, humidité, vitesse du vent,

etc.). L’énergie nécessaire pour transmettre 1kb sur une distance de 100m est

approximativement équivalente à l’énergie nécessaire pour exécuter 3 millions d’instructions

avec une vitesse de 100 millions d’instructions par seconde MIPS [15]. Ce niveau peut être

dépassé en fonction des circuits installés dans les nœuds capteurs et des fonctionnalités

requises.

Le graphique de la figure I.7 montre l’énergie consommée pour chaque état et pour

chaque action réalisée par le nœud capteur. On voit clairement que la tâche de transmission

est la plus gourmande en énergie suivie de celle de la réception, alors que la tâche de capture

et celle du traitement sont négligeables.

Puissance (mW)

20

15

10

5

Capture CPU TX RX Inactif Mise en veille

Figure I.7 : Consommation de l’énergie électrique par un nœud capteur [15].

Le tableau suivant donne l’énergie dissipée pour une transmission, une réception et pour

l’amplification du signal [8].


14

Opération Energie dissipée

elecTxE

elecRxE

50 nJ/bit

ampTxE 100 pJ/bit/m2

Tableau I.1 : L’énergie dissipée par les principales fonctions d’un capteur [15].

L’énergie se dissipe pour les RCSF scalaires par ordre décroissant comme suit:

Radio (communication),

CPU (calcul, agrégation, protocoles, etc.),

Acquisition ou collecte.

I.2.8. Facteurs et contraintes d’influence

Les principaux facteurs et contraintes influençant l’architecture logicielle et physique

des RCSF sont détaillés ci-dessous [17] :

L’environnement

Les capteurs sont souvent déployés en masse dans des endroits hostiles tels que des

champs de bataille au delà des lignes ennemies, à l’intérieur de grandes machines, au fond

d’un océan, dans des champs biologiquement ou chimiquement souillés, etc. Par conséquent,

ils doivent pouvoir fonctionner sans surveillance dans des régions géographiquement

éloignées ou inaccessibles.

Modèle de livraison des données

Selon l’application, le modèle de livraison des données au Sink peut être continu,

périodique, dirigé par évènement ou par requête ou hybride.

Le passage à l’échelle

Le nombre de nœuds déployés pour un projet peut atteindre le million voir plus. Un

nombre aussi important de nœuds engendre un trafic énorme dans le réseau, ce qui entraine

des congestions et des erreurs de communication. Un tel déploiement, nécessite que le

protocole utilisé pour la communication soit capable de détecter les erreurs et de contrôler le

flux, et nécessite aussi que le nœud Sink soit équipé d’une capacité de stockage suffisante

pour accueillir les informations reçues à partir des nœuds capteurs.


15

La topologie du réseau

Le déploiement d’un grand nombre de nœuds nécessite une maintenance de la

topologie. Cette maintenance se fait en trois phases : déploiement, post-déploiement (les

capteurs peuvent bouger, ne plus fonctionner, etc.) et redéploiement des nœuds additionnels.

La connectivité

La densité élevée des nœuds dans les RCSF les empêche d’être complètement isolés les

uns des autres. Ceci, cependant, n’empêche pas la topologie du réseau d’être variable. En

outre, la connectivité dépend de la distribution aléatoire des nœuds.

La tolérance aux fautes

Certains nœuds capteurs peuvent générer des erreurs ou ne plus fonctionner à cause

d’un manque d’énergie, d’une défaillance matérielle ou d’une interférence. La tolérance aux

fautes est la capacité de maintenir les fonctionnalités du réseau sans interruption en cas de

défaillance d’un ou certain nombre de ses capteurs.

La tolérance aux intrusions

L’absence d’une protection physique des nœuds capteurs ainsi que la nature des liens

sans fil utilisés pour la communication, rendent le réseau vulnérable aux attaques

malveillantes. La tolérance aux intrusions implique la tolérance aux vulnérabilités, dont

certaines sont inévitables pour améliorer à la fois la sécurité et l’utilisation du réseau.

Le média de transmission

Afin d’être installés sans difficulté dans des zones ciblées et sans induire d’importants

coûts de câblage, les capteurs utilisent des liens radiofréquence pour coopérer entre eux au

sein du réseau.

Les contraintes matérielles

En plus de leurs petites dimensions, les capteurs subissent de fortes contraintes,

notamment d’énergie, de calcul et de stockage.

Dimension

La taille réduite des capteurs peut présenter de nombreux avantages en fonction de

l’utilisation prévue du système, et elle permet un déploiement flexible et simple du réseau.

Cependant, la puissance des batteries utilisées pour alimenter les nœuds capteurs est limitée,

par la petite taille de ces derniers.

Energie

Un nœud capteur est généralement muni d’une ou plusieurs piles normales et

irremplaçables pour alimenter tous ses composants, ce qui rend l’énergie la plus précieuse


16

ressource dans un RCSF. De ce fait, la faible consommation d’énergie est une exigence

principale pour les applications où une longue durée de vie du réseau est nécessaire.

Puissance de calcul

Les RCSF sont différents par rapport aux réseaux traditionnels. Parmi les points de

différence nous pouvons citer la puissance de calcul. Les nœuds capteurs utilisent des

microcontrôleurs de faibles fréquences. Par exemple, le nœud populaire, MICA, développé

par l’université de Berkeley et commercialisé par Crossbow [8], utilise un CPU Atmel de

7.37-MHz, 8-bit. Cette contrainte doit être considérée dans le développement d’applications

pour les RCSF [18].

I.2.9. Exemples de Standards MAC pour les RCSF

Dans cette partie, nous présentons quelques protocoles MAC proposés pour les RCSF.

Les Standards ZigBee et IEEE 802.15.4

ZigBee est un standard à faible débit et à faible puissance énergétique pour les WPAN

(Wireless Personal Area Networks). Il est caractérisé par une portée maximum de quelques

centaines de mètres et un faible débit (de 250 kbit/s maximum). La norme a été conçue pour

interconnecter des unités embarquées contraintes énergétiquement comme des capteurs, à des

unités de contrôle ou de commande.

La spécification ZigBee [19] propose une pile protocolaire propriétaire et légère. Elle

s’appuie sur la norme IEEE 802.15.4 [20] pour les couches physique et liaison et propose ses

propres couches supérieures (réseau, etc.) La distinction entre le standard ZigBee et le

standard IEEE 802.15.4 est illustrée par la Figure I.9.

La différence entre ZigBee et la plupart des autres WPAN se situe au niveau de

l’utilisation du médium ; ZigBee est optimisé pour une faible utilisation du médium partagé

par tous, par exemple 0,1% du temps. Typiquement, un module émetteur récepteur ZigBee

occupera le médium pendant quelques millisecondes en émission, attendra éventuellement

une réponse ou un acquittement, puis se mettra en veille pendant une longue période avant

l’émission suivante (on parle de somnolence), qui aura lieu à un instant prédéterminé. Cette

nécessité introduit des problématiques de recherche intéressantes, notamment au niveau des

couches liaison (temporisation et stockage des messages, accès original au médium) et réseau

(routage avec respect de contraintes énergétiques) [21].

ZigBee prévoit deux types d’entités réseau : les FFD (Full Function Device)

implémentent la totalité de la spécification alors que les RFD (Reduced Function Device) sont


17

des entités allégées dans un objectif de moindre consommation énergétique et de moindre

utilisation mémoire pour le microcontrôleur. Les entités RFD sont nécessairement des nœuds

terminaux du réseau car la pile réduite n’implémente pas le mécanisme de routage.

Typiquement, un capteur embarqué sera RFD et alimenté sur batteries, alors qu’une unité

centrale de traitement, alimentée par une source non contrainte énergétiquement (main

powered), sera FFD avec la fonction de routage.

La norme IEEE 802.15.4 prévoit deux topologies : étoile (star où tous les nœuds

communiquent avec un nœud central appelé coordinateur) ou point à point (peer to peer où

tous les nœuds à portée radio peuvent communiquer ensemble sans hiérarchie). Au dessus de

802.15.4, la couche réseau de ZigBee permet la création de réseaux maillés (mesh) grâce à un

routage automatique : c’est la topologie maillée, ou mesh topology.

La Figure I.8 présente la position de divers standards sur une échelle de portée et de

débit, afin de mieux situer les contraintes du standard ZigBee [22].

Figure I.8 : ZigBee par rapport aux autres Standards [22].

802.15.4(ZigBee)

802.15.1(Bluetooth)

802.11

802.11b (Wi-Fi)

802.11g - 802.11a - HiperLAN

802.15.3a (UWB)

WPAN

WLAN

WPAN

( 1 Gb/s)

> 110Mb/s

1 ~ 54Mb/s

1 Mb/s

20 ~ 250Kb/s

Débit

Indoor range (m)0 10 N * 100


18

Figure I.9 : Différence entre l’alliance ZigBee et le Standard 802.15.4 [22].

Le Standard IEEE 802.11

802.11 est un standard IEEE qui a été développé en 1997 et qui définit une couche

physique et une couche liaison de données pour les réseaux locaux sans fil. Originellement,

802.11 opère dans la bande de fréquences des 900 MHz et offre un débit jusqu’à 2 Mb/s. En

1999, 802.11 passe dans la bande des 2,4 GHz avec des débits allant toujours jusqu’à 2 Mb/s.

Deux autres extensions sont venues compléter cette norme en 1999 : 802.11b qui fonctionne

dans la bande de fréquences des 2,4 GHz et offre des débits jusqu’à 11 Mb/s et 802.11a qui

fonctionne dans la bande de fréquences des 5 GHz et qui offre des débits allant jusqu’à 54

Mb/s. Tout récemment, en 2003, l’extension 802.11g a été proposée. Elle fonctionne dans la

bande de fréquences des 2,4 GHz et offre des débits allant jusqu’à 54 Mb/s [22].

Remarque : Dans nos différentes simulations, nous avons utilisé la couche MAC IEEE

802.11.

I.2.10. Localisation des nœuds capteurs

Les nœuds capteurs sont déployés d’une façon Ad Hoc où il n’y a généralement aucune

connaissance préalable sur la position des nœuds. La localisation de ces derniers fait référence

au problème d’estimation de leurs coordonnées. La localisation peut être divisée en deux

classes :

1. La localisation granuleuse brute (Coarse grained localization).

2. La localisation granuleuse fine (Fine grained localization).

APPLICATION

Interface APPLICATION

SECURITE

COUCHE RESEAU

COUCHE MAC

COUCHE MAC

COUCHE PHY2.4GHz 915GHz 868MHz

Client

AllianceZigBee

IEEE802.15.4

Silicium Couche ZigBee Application


19

Dans le cas de la localisation granuleuse brute les nœuds capteurs peuvent être vus dans

une hiérarchie où on trouve un groupe de nœuds capteurs dans le réseau qui connaissent leurs

positions (via GPS). Ces nœuds capteurs diffusent des balises (beacons) dans le réseau

annonçant leur position. Les autres nœuds capteurs reçoivent ces balises et calculent leurs

positions en utilisant une ou plusieurs balises. Pour les nœuds capteurs qui n’ont pas accès à

ces nœuds de balise (beacon node), les nœuds capteurs ayant calculés leurs positions agissent

en tant que leurs nœuds de balise. Ceci est connu sous le nom de : multilatéralisation itérative.

Cependant, cette technique conduit à une accumulation d’erreurs de localisation. Dans les

méthodes de localisation granuleuses fines, on utilise l’analyse du temps de propagation du

signal, de sa puissance et de sa direction [4].

I.2.11. Domaines d’applications

La taille de plus en plus réduite des capteurs, leur coût de plus en plus faible, la large

gamme de types de capteurs disponibles (thermique, optique, vibrations, etc.) ainsi que le

support de communication sans fil utilisé, permettent aux RCSF d’envahir plusieurs domaines

d’applications [23].

Nous pouvons citer les domaines suivants : militaire, environnemental, domestique,

santé, sécurité, écologie, traçabilité, etc. Des exemples d’applications potentielles dans ces

différents domaines sont exposés ci-dessous [24].

Applications militaires

Comme dans le cas de plusieurs technologies, le domaine militaire a été le moteur initial

pour le développement des RCSF. Le déploiement rapide, l’auto-configuration et la tolérance

aux pannes des RCSF sont des caractéristiques qui font de ce type de réseaux un outil

appréciable dans un tel domaine. Déploiement sur un endroit stratégique ou difficile d’accès,

afin de surveiller toutes les activités des forces ennemies ou d’analyser le terrain avant d’y

envoyer des troupes (par la détection d’agents chimiques, biologiques ou de radiations par

exemple).

Applications liées à la sécurité

Diminuer considérablement les dépenses financières consacrées à la sécurisation des

lieux et à la protection des êtres humains tout en garantissant des résultats plus fiables.

La détection des altérations dans la structure d’un bâtiment, suite à un séisme ou au

vieillissement, par des capteurs intégrés dans les murs ou dans le béton.


20

La surveillance des mouvements afin de constituer un système de détection d’intrusions

distribué. L’aspect distribué rend plus complexe la possibilité de mettre hors d’usage ce

système de surveillance.

Applications environnementales

La dispersion de thermo-capteurs à partir d’un avion sur une forêt pour signaler un

éventuel début d’incendie dans le champ de captage.

Le semis de nœuds capteurs en même temps avec les graines dans les champs agricoles

pour pouvoir identifier les zones sèches et rendre l’irrigation plus efficace.

Le déploiement de nœuds capteurs sur les sites industriels, les centrales nucléaires ou

dans les raffineries de pétrole pour détecter des fuites de produits toxiques (gaz, produits

chimiques, éléments radioactifs, pétrole, etc.) et alerter les utilisateurs dans un délai

suffisamment court pour permettre une intervention efficace.

Applications médicales

Surveillance permanente des patients et une possibilité de collecter des informations

physiologiques de meilleure qualité facilitant ainsi le diagnostic de maladies grâce à des

micro-capteurs qui pourront être ingérés ou implantés sous la peau.

Les micro-caméras qui peuvent être ingérées, sont capables, sans avoir recours à la

chirurgie, de transmettre des images de l’intérieur d’un corps humain.

La création d’une rétine artificielle composée d’une centaine de micro-capteurs pour

améliorer la vision de l’œil.

Applications écologiques

L’intégration de plusieurs micro-capteurs dans le système de climatisation et de

chauffage des immeubles. Ainsi, la climatisation ou le chauffage ne sont déclenchés qu’aux

endroits où il y a des personnes présentes et seulement si c’est nécessaire. Le système

distribué peut aussi maintenir une température homogène dans les pièces. Utilisée à grande

échelle, une telle application permettrait probablement de réduire la demande mondiale en

énergie.

Applications de traçabilité et de localisation

Suite à une avalanche, il est nécessaire de localiser les victimes enterrées sous la neige

en équipant les personnes susceptibles de se trouver dans des zones à risque par des capteurs.

Ainsi, les équipes de sauvetage peuvent localiser plus facilement les victimes. Contrairement

aux solutions de traçabilité et de localisation basées sur le système de GPS, les RCSF peuvent

être très utiles dans des endroits clos comme les mines par exemple.


21

I.3. Le routage dans les RCSF

Au niveau de la couche réseau, le but principal est de trouver un chemin d’un nœud

capteur source vers le nœud destination (Sink) assurant une transmission fiable des données

mesurées en tenant compte des critères de routage fixés par l’application choisie.

Comme les nœuds capteurs exigent une gestion soigneuse des ressources, la plupart des

protocoles de routage dans les réseaux Ad Hoc s’adaptent mal aux particularités des RCSF.

D’où, la nécessité de les améliorer ou de développer de nouveaux protocoles. Dans le cadre de

notre étude, nous avons amélioré des protocoles de routage Ad Hoc afin de satisfaire les

contraintes des RCSF.

Cependant, plusieurs nouveaux protocoles de routage ont été proposés pour les RCSF.

Ces protocoles peuvent être classifiés selon différents paramètres. En considérant la structure

du réseau, on peut distinguer le routage linéaire, le routage hiérarchique et le routage basé

sur la localisation [23].

De plus, ces protocoles peuvent être classifiés par rapport à leur technique de routage

qui peut être soit le multi-chemins, à base de requêtes, à base de négociation, de QoS ou

basé sur la cohérence selon l’opération et l’objectif visés par le protocole.

Il existe aussi plusieurs protocoles inspirés des Réseaux Ad Hoc qui sont utilisés par les

RCSF, il s’agit des protocoles proactifs, réactifs et hybrides qui se distinguent selon la

manière dont le protocole désigne le chemin à emprunter par les données.

Une autre classe de protocoles de routage s’appelle « les protocoles de routage

coopératifs ». Dans le routage coopératif, les nœuds capteurs envoient des données à un nœud

central où les données peuvent être agrégées et utilisées pour un traitement ultérieur et

réduisent par conséquent le coût du chemin en termes d’utilisation d’énergie.

Afin de résumer les techniques de routage utilisées par les RCSF, une classification des

protocoles de routage est proposée sur la figure I.10 suivante :


22

Figure I.10 : Taxonomie des protocoles de routage dans les RCSF [25].

Dans le cadre de notre étude et afin d’atteindre les objectifs que nous nous sommes

fixés, à partir de cette classification nous nous sommes intéressés plus particulièrement aux

protocoles de routage basés sur l’approche multi-chemins avec QoS et sur la technique du

routage réactif, sachant que la structure du RCSF est linéaire. Les autres classes seront

présentées brièvement.

I.3.1. Protocoles de routage classés selon la structure du réseau

La structure fondamentale du réseau peut jouer un rôle significatif dans le

fonctionnement du protocole de routage dans les RCSF. Ces protocoles de routage sont

classifiés comme suit [26]:

I.3.1.1. Routage linéaire

Dans les réseaux linéaires, chaque nœud joue typiquement le même rôle et les nœuds

capteurs collaborent ensemble pour accomplir leur tâche. Cette classe de protocoles est très

proche de celle des protocoles centrés données (data centric), où la station de base envoie des

questions à certaines régions et attend la réception des données collectées par les nœuds

capteurs situés dans ces régions.

Les protocoles de routage les plus connus de cette classe sont les suivant:

Protocoles de routage dans les RCSF

Selon la structure du réseau Selon le fonctionnement du protocole Selon le mécanisme dedécouverte de route

Routagelinéaire

Routagehiérarchique

Routage basé surla localisation

Parnégociation

Parcohérence

Multi-chemins

Basé sur lesrequêtes

Basé surla QoS

Routageproactif

Routagehybride

Routageréactif


23

Le routage basé sur la négociation (SPIN : Sensor Protocols for Information via

Negotiation) [27].

La diffusion dirigée (DD : Directed Diffusion) [28]

I.3.1.2. Routage hiérarchique

Dans ce type de protocole des clusters sont créés et les nœuds peuvent jouer différents

rôles dans le réseau. Le but principal du routage hiérarchique est de maintenir efficacement la

consommation d’énergie des nœuds capteurs en les impliquant dans une communication

multi-sauts dans un cluster particulier (Clustering) où le coordinateur (Clusterhead) joue le

rôle d’une passerelle vers la station de base et en effectuant l’agrégation et la fusion des

données afin de diminuer le nombre de messages transmis au Sink.

Nous citons comme exemples de protocoles de cette classe les suivants :

Hiérarchie de regroupement adaptative à faible énergie (LEACH : Low-Energy

Adaptive Clustering Hierarchy) [29].

Assemblage à puissance efficace dans les systèmes d’information de capteurs

(PEGASIS : Power Efficient GAthering in Sensor Information Systems) [30].

I.3.1.3. Routage basé sur la localisation

Dans ce type de routage, les nœuds capteurs sont adressés au moyen de leurs

emplacements. La distance entre les nœuds voisins peut être estimée sur la base

des puissances du signal entrant. Les coordonnées relatives aux nœuds voisins peuvent être

obtenues en échangeant de telles informations. Alternativement, le positionnement des nœuds

peut être disponible directement en communiquant avec un satellite, en utilisant le GPS si les

nœuds sont équipés d’un petit récepteur GPS de basse puissance. Comme exemples de

protocoles de cette classe, nous citons :

GAF (Geographic adaptive fidelity) [31]

GEAR (Geographic and Energy Aware Routing) [32].

I.3.2. Protocoles de routage classés selon le fonctionnement du réseau

Selon leur fonctionnement, les protocoles de routage sont classés en cinq classes

différentes, qui seront discutées au cours de cette section.


24

I.3.2.1. Routage basé sur la négociation

L’idée principale du routage par négociation dans les RCSF est de supprimer

l’information dupliquée et d’empêcher les données redondantes d’être envoyées au prochain

capteur ou à la station de base en conduisant une série de messages de négociation avant que

la vraie transmission de données commence. Comme exemple d’un de ces protocoles qui

utilisent la négociation, on peut citer le protocole SPIN.

I.3.2.2. Routage basé sur les requêtes

Dans ce type de routage, le Sink génère des requêtes afin d’interroger les nœuds

capteurs. Ces requêtes sont exprimées par un schéma valeur-attribut. Les nœuds qui

détiennent les données requises doivent les envoyer au Sink à travers le chemin inverse de la

requête. Les requêtes émises par le Sink peuvent aussi être ciblées sur des régions spécifiques

du réseau. La diffusion dirigée est un exemple de ce type de routage.

I.3.2.3. Routage basé sur la cohérence

Généralement les nœuds capteurs coopèrent entre eux pour traiter les différentes

données propagées dans la zone réseau. Deux exemples de techniques de traitement sont

proposés dans les RCSF : le routage basé sur le traitement cohérent et le routage basé sur le

traitement non cohérent. Dans le routage à traitement non cohérent, les nœuds traitent

localement les données brutes avant qu’elles soient envoyées à d’autres nœuds pour

un traitement ultérieur. Les nœuds qui exécutent le traitement ultérieur s’appellent les nœuds

agrégatifs. Dans le routage cohérent, les données sont expédiées aux nœuds

agrégatifs après un traitement minimum. Le traitement minimum inclut typiquement des

tâches comme le pointage de temps, la suppression des doubles, etc. Pour les protocoles de

routage à efficacité énergétique, le choix de la technique de traitement cohérent est préférable.

I.3.2.4. Routage basé sur la QoS

La QoS est définie comme un ensemble de besoins à assurer par le réseau pour le

transport d’un trafic d’une source à une destination. Ces besoins peuvent être traduits en un

ensemble d’attributs ou métriques pré-spécifiés et mesurables en termes de [33]:

Délai de bout en bout,

Variance de délai (gigue),

Bande passante,

Pertes de paquets.


25

Les métriques de QoS peuvent être additives, concaves ou multiplicatives. La bande

passante est une métrique concave (la règle de composition définie la valeur minimale de

cette métrique sur un chemin), alors que le délai et la gigue sont des métriques additives (la

règle de composition définie la somme de toutes les valeurs de la métrique délai de tous les

liens d’un chemin). La disponibilité d’un lien, basée sur des critères comme la probabilité de

perte du lien quant à elle est une métrique multiplicative (la règle de composition définie le

produit de toutes les valeurs de la métrique perte de paquets de tous les liens d’un chemin).

Selon le type de l’application et ses besoins en QoS, ces métriques peuvent être

manipulées suivant trois approches :

Individuellement,

Sous forme d’une fonction mathématique coût combinant plusieurs

métriques en une seule,

En utilisant des heuristiques.

Bien que la deuxième approche semble être intéressante, elle pose par contre quelques

problèmes dans des situations réelles. En effet, elle ne donne aucune garantie à ce que tous les

besoins de QoS de l’application soient respectés. En plus, elle exige que toutes les métriques

aient une même règle de composition (additive, multiplicative ou concave) pour pouvoir les

combiner.

Deux modèles différents existent permettant d’obtenir une garantie de QoS : IntServ

(Integrated services) et DiffServ (Differentiated services). La première architecture de QoS a

été définie pour assurer aux différents flux de données des garanties sur le délai de bout en

bout, le débit, etc. L’architecture DiffServ définit plusieurs classes de trafic, les différents flux

s’intègrent à une de ces classes afin de bénéficier des garanties correspondantes.

Dernièrement, avec l’émergence des services multimédia temps réel, et les champs

variés des applications des RCSF, la QoS dans les RCSF est devenue un thème de recherche

qui a suscité beaucoup d’intérêts. Cependant, il est très difficile de garantir une quelconque

QoS à une application dans un RCSF, car il faut prendre en considération les spécificités de

ces réseaux, à savoir : la contrainte d’énergie et la bande passante limitée. En outre, la

communication entre les nœuds capteurs étant par voix radio, la qualité du lien sans fil reste

peu fiable, et susceptible à différentes interférences.

Selon le type d’application, les besoins de QoS sont différents. Par exemple, pour les

applications temps réel, comme la voix et la vidéo, le délai de bout en bout d’un paquet doit

être limité, autrement le paquet est inutile. Les applications non temps réel, comme le


26

transfert de données non urgentes, quant à elles se focalisent sur la fiabilité des

communications et l’optimisation de la consommation d’énergie.

Ci-dessous, nous allons présenter quelques travaux de recherche traitant la QoS au

niveau de la couche réseau dans le contexte particulier des RCSF.

SAR (Sequential Assignment Routing) [9] est l’un des premiers protocoles de routage

pour les RCSF qui présente la notion de QoS dans les décisions de routage. SAR est basé sur

le modèle DiffServ et l’approche multi-chemins. Il crée des arbres en prenant en compte la

métrique QoS, les ressources énergétiques de chaque chemin et le niveau de priorité de

chaque paquet. En utilisant ces arbres, des chemins multiples du Sink aux capteurs sont

formés. Un de ces chemins est choisi selon les ressources énergétiques et la QoS du chemin.

Le protocole SPEED [34] assure un temps limite au delà duquel les informations ne

sont plus prises en compte. Il introduit une notion de « temps réel » dans les RCSF. Son but

est d’assurer une certaine vitesse pour chaque paquet dans le réseau. Ainsi chaque application

estime le délai de bout en bout pour les paquets en divisant la distance au Sink par la vitesse

du paquet avant de prendre la décision d’accepter ou de refuser le paquet.

Ce protocole implique que chaque nœud doit maintenir des informations sur ses voisins. Il est

basé sur l’approche IntServ qui limite son utilisation à grande échelle.

I.3.2.5. Routage basé sur l’approche multi-chemins

A) Définition de l’approche multi-chemins

L’approche du routage multi-chemins a été l’une des directions courantes les plus

importantes dans le domaine du routage. Le concept du routage multi-chemins consiste à

trouver pour chaque nœud source et à tout moment un multiple choix de chemins lui

permettant d’atteindre une destination particulière. Les chemins multiples peuvent être utilisés

soit alternativement (l’approche que nous avons utilisé dans notre étude), c’est-à-dire à un

moment donné un seul chemin sera choisi, ou simultanément en utilisant plusieurs chemins en

même temps. Ces chemins peuvent aussi être classés en trois catégories principales à savoir :

les chemins à nœuds disjoints, à liens disjoints et non disjoints qui seront évoquées par la

suite, mais avant, nous allons citer les avantages apportés par cette approche.


27

B) Avantages du routage multi-chemins

Fiabilité

La fiabilité est un grand défi dans les RCSF parce que les paquets transmis peuvent être

perdus à cause des changements de la topologie du réseau, des conflits très importants au

niveau de l’accès au médium et de différents types d’interférences qui influencent sur le bon

fonctionnement des récepteurs radio sans fil. La fiabilité peut être définie par la probabilité

qu’un paquet généré par un nœud puisse atteindre sa destination. Cette probabilité augmente

si le nombre de chemins possibles augmente.

Equilibre consommation d’énergie/charge du trafic

Comme nous l’avons précisé auparavant que parmi les caractéristiques principales des

RCSF est que les nœuds capteurs sont équipés par des batteries à énergie limitée presque

impossible à recharger et que leur durée de vie dépend fortement de celle des batteries. Pour

le routage multi-sauts à chemin unique, chaque nœud dépend de ses voisins pour relayer les

paquets jusqu’à la destination. La perte de quelques nœuds, qui peut être due à l’épuisement

de l’énergie, peut causer un changement de topologie significatif, influence sur le

fonctionnement du réseau et donc sur sa durée de vie. Afin de maximiser cette durée de vie il

est préférable d’utiliser l’approche multi-chemins permettant de distribuer d’une façon

équitable la charge du trafic sur de multiples chemins.

Réduction du nombre de diffusions

Dans le routage avec un seul chemin, si ce dernier tombe en panne, une nouvelle

découverte de route doit être relancée, ce qui encombre le réseau par les messages diffusés

pendant cette phase. Par contre dans le routage multi-chemins, la procédure de découverte de

route ne doit être relancée que lorsque tous les chemins possibles tombent en panne.

QoS

Un objectif très important du routage multi-chemins est de fournir la QoS. Plus

précisément, la réduction du délai de livraison des paquets de bout en bout (moins de

découverte de nouveaux chemins, moins de nœuds en panne et moins de liens brisés), éviter

la congestion, etc.

Sécurité

L’approche multi-chemins améliore la sécurité de la communication qui est une

caractéristique très importante pour les réseaux. L’idée de base consiste en la transformation

ou la division d’un message secret en plusieurs parties (sous-messages) en utilisant l’une des


28

méthodes de cryptographie. Ces sous-messages seront envoyés sur de multiples chemins

indépendamment vers la destination.

C) Types de routage multi-chemins

Un protocole de routage multi-chemins consiste à découvrir des chemins multiples qui

peuvent exister entre une paire de nœuds capteurs (source-destination). Ces chemins peuvent

être à nœuds disjoints, à liens disjoints ou non disjoints [35]. La figure I.11 illustre ces trois

types de chemins.

Figure I.11 : Les types de routage multi-chemins (Dans (a), SXD, SYD, et SZD sont des

chemins à nœuds disjoints. Dans (b), SXYZD et SYD sont des chemins à liens disjoints.

Dans (c), les chemins SXD et SXYD ne sont pas disjoints) [35].

Chemins à nœuds disjoints

On les appelle aussi des chemins totalement disjoints, ils ont ni nœuds ni liens en

commun, ils assurent une bonne fiabilité par rapport aux chemins non disjoints et à liens

disjoints. En effet, avec des chemins à nœuds disjoints, quand un nœud tombe en panne ou un

lien est brisé, c’est un seul chemin qui sera défaillant, ce qui n’est pas le cas pour les deux

autres types (la raison pour laquelle nous avons choisi ce type de routage pour notre projet).

Chemins à liens disjoints

Ce sont des chemins qui n’ont aucun lien en commun mais peuvent avoir des nœuds en

commun.

Chemins non disjoints

Ce sont des chemins qui peuvent avoir des nœuds ou des liens en commun. Leur

principal avantage est qu’ils sont faciles à découvrir parce qu’ils n’ont aucune contrainte de

recherche des chemins, ils peuvent être à nœuds disjoints ou à liens disjoints.

S

X

Z

Y D

(b)

S

X

Z

Y D

(a)

S

X

Z

Y D

(c)


29

D) Exemples de protocoles de routage multi-chemins

Afin de remédier à la sensibilité des nœuds capteurs et d’assurer une meilleure QoS,

plusieurs protocoles de routage basés sur l’approche multi-chemins ont été proposés afin

d’améliorer les performances du réseau.

Le protocole SMR (Split Multipath Routing) proposé dans [36] est un protocole de

routage réactif, multi-chemins à la source basé sur DSR, dont le but est de construire le

maximum de chemins disjoints. La différence majeure avec DSR est dans le fait que les

nœuds intermédiaires ne répondent jamais avec un paquet RREP vers la source même s’ils

possèdent un chemin direct qui mène vers la destination, pour permettre d’avoir le maximum

de routes disjointes (à liens ou à nœuds disjoints). De plus, les RREQ dupliqués ne sont pas

directement supprimés par les nœuds intermédiaires comme dans le protocole à chemin

unique DSR, les RREQ seront diffusés si le champ du nombre de saut est inférieur ou égal à

ceux des RREQ déjà reçus. Le protocole SMR définit uniquement deux routes disjointes entre

une source et une destination pour la transmission des données.

Le protocole AOMDV [37] (Ad Hoc On-demand Multipath Distance Vector) qui se

base sur AODV (détaillé dans le chapitre suivant) permet de construire des routes multiples à

liens disjoints. Le but principal de la conception de ce protocole est de chercher plusieurs

routes pendant une même phase de découverte de routes mais on ne peut utiliser que la

meilleure en termes du nombre de saut pour la transmission des données entre une source et

une destination, les autres routes calculées ne seront utilisées que lorsque la route principale

devient invalide. AOMDV est basé sur le principe du « advertised hop count ». « advertised

hop count » d’un nœud i pour une destination d représente le nombre de saut maximal des

routes multiples disponibles pour i vers la destination d. Ce protocole permet d’accepter

seulement les routes alternatives ayant un nombre de saut inférieur à celui de « advertised hop

count ». Cette condition est nécessaire pour garantir des routes sans boucles de routage.

Le protocole MDYMO (Multipath DYnamic Manet On-demand) [38] est une version

multi-chemins de DYMO qui se base sur les mêmes principes que le protocole AOMDV et a

pour but de réduire le nombre de messages de contrôle afin d’améliorer les performances du

réseau.

Le protocole AODV_Multipath [39] est une extension aussi de AODV dont le but est

de découvrir de multiples routes à nœuds disjoints. Comme pour AOMDV les RREQ

dupliqués ne seront pas supprimés et la destination répond à toutes les requêtes afin de

maximiser le nombre de routes. Pour assurer la disjonction des nœuds, lorsqu’un nœud

intermédiaire détecte un message RREP d’un nœud voisin donc il supprime l’entrée


30

correspondante de la table des RREQ. Donc, contrairement à AOMDV, la disjonction des

nœuds est traitée lors de l’envoi des messages RREP vers la source.

Le protocole de routage à nœuds disjoints NDMR (Node-Disjoint Multipath Routing)

[39] se base également sur AODV, et permet de découvrir de multiples routes avec un

minimum de trafic de contrôle et de latence dans le réseau en ajoutant la caractéristique de

l’accumulation du chemin de DSR, donc chaque nœud intermédiaire doit ajouter sa propre

adresse dans le paquet RREQ ensuite le destinataire va procéder à la sélection des chemins à

nœuds disjoint (le protocole de routage AODV_MQ que nous avons amélioré emprunte

presque les mêmes techniques de routage que NDMR, les détails seront présentés dans le

chapitre suivant).

I.3.3. Protocoles de routage classés selon le mécanisme de découverte de route

Comme l’objectif de notre travail est d’adapter les protocoles de routage réactifs AODV

et DYMO pour les RCSF et puisque ces protocoles ont été conçus à l’origine pour les réseaux

Ad Hoc, nous présentons dans cette partie un aperçu sur les protocoles de routage les plus

utilisés dans ce type de réseau.

I.3.3.1. Classification des protocoles de routage Ad Hoc

Les protocoles de routage dans les réseaux Ad Hoc se basent sur les principes

fondamentaux du routage, qui sont : l’inondation, le vecteur de distance, le routage à la source

et l’état de lien.

De très nombreux protocoles de routage dynamiques pour les réseaux mobiles Ad Hoc

ont vu le jour ces dernières années, ces protocoles ayant tous pour vocation de tenir compte de

la réactivité des réseaux dans lesquels ils sont censés être mis en œuvre. Le groupe MANET

(créé par l’IETF en 1997 et principal organisme de normalisation des protocoles pour les

réseaux Ad Hoc) a entrepris de recenser et évaluer ces divers protocoles, et certains d’entre

eux (par exemple OLSRv2 [40] et DYMO ont récemment été sélectionnés en vue d’une

standardisation par l’IETF). Ces protocoles peuvent être classés en quelques grandes

«familles», énumérées et discutées brièvement ci-dessous [41].

A) Protocoles de routage proactifs

Dans le routage proactif (proactive routing ou table-driven routing), chaque noeud

s’efforce de maintenir constamment à jour sa propre table de routage, de sorte que lorsqu’un

paquet IP doit être émis (ou routé) par ce nœud, la route que ce paquet doit suivre soit d’ores


31

et déjà connue, et donc immédiatement exploitable. L’approche communément adoptée pour

réaliser ce type de routage consiste à faire en sorte que chaque nœud diffuse périodiquement

sa propre table de routage, et la mette par ailleurs à jour en fonction d’informations similaires

reçues de tous ses voisins.

Les avantages majeurs présentés par les protocoles de routage proactifs sont les bonnes

performances qu’ils permettent d’obtenir lorsqu’un paquet IP doit suivre une route dans

laquelle tous les nœuds-relais sont effectivement disponibles, et disposent chacun d’une table

de routage à jour.

Les inconvénients majeurs sont le surcoût important occasionné par le trafic de contrôle

nécessaire au maintien à jour des informations de routage, et des temps de réaction souvent

assez longs lorsque des changements dans la topologie du réseau obligent l’ensemble des

nœuds à corriger leurs tables de routage en conséquence [41].

Parmi cette famille de routages Ad Hoc proactifs on retrouve de nombreuses versions,

répertoriées ci-après :

OLSR (Optimized Link State Routing Protocol), CGSR (Clusterhead Gateway Switch Routing

protocol), DSDV (Dynamic Destination-Sequenced Distance Vector routing protocol), WRP

(Wireless Routing Protocol).

B) Protocoles de routage réactifs

Dans le routage réactif (reactive routing ou on-demand routing), les tables de routage

ne sont mises à jour que lorsque le besoin s’en fait sentir. L’approche générale est la suivante:

lorsqu’un nœud devant router un paquet IP vers une certaine direction constate que sa table de

routage ne contient aucune indication pour atteindre cette destination, il diffuse dans

l’ensemble du réseau un message de contrôle (RREQ) invitant tous les nœuds du réseau à

mettre à jour leur table de routage vis-à-vis de la destination visée. En règle générale, cette

mise à jour s’effectue aussi grâce à un second message de contrôle (RREP) initié par le nœud

destinataire lui-même, ce message remontant (en source-routing) vers le nœud qui cherche à

l’atteindre.

L’avantage majeur des protocoles reposant sur une approche réactive est que le surcoût

occasionné par la mise à jour des informations de routage est directement proportionné, au cas

par cas, aux flux de données circulant dans le réseau.

Les principaux inconvénients sont que ces protocoles nécessitent un temps de latence

conséquent avant qu’une route vers une certaine destination puisse être exploitée pour la


32

première fois (ou encore en cas de changements de topologie fréquents, obligeant à une

réactualisation fréquente des routes dans le réseau) [41].

De nombreux protocoles pouvant être qualifiés de réactifs sont listés ci-après :

AODV ( Ad Hoc On-demand Distance Vector) qui sera présenté dans le chapitre II, DSR

(Dynamic Source Routing), TORA (Temporally-Ordered Routing Algorithm routing protocol),

et le protocole DYMO (DYnamic Manet On-demand) qui sera expliqué plus en détail dans le

chapitre III.

C) Protocoles de routage hybrides

Les protocoles de routage dits « hybrides » (par exemple HSLS (Hazy Sighted Link

State) et ZRP (Zone Routing Protocol)) sont des protocoles qui combinent les approches

proactives et réactives afin de bénéficier du meilleur de ces deux techniques. Dans certains

cas, les protocoles hybrides s’appuient sur une approche proactive afin de créer des routes

principales couvrant à peu près toute la superficie du réseau. Ces routes passent par un certain

nombre de nœuds dits « actifs », à partir desquels le routage vers des nœuds passifs

avoisinants peut être effectué de manière réactive. On réalise ainsi un découpage du réseau en

un certain nombre de «grappes» (clusters) entre lesquelles le routage est assuré via l’approche

proactive, et au sein desquelles le routage réactif permet d’atteindre les nœuds en fonction des

besoins. On notera que la démarche inverse est également possible, le routage proactif étant

réalisé au sein de chaque grappe, et le routage réactif entre les différentes « grappes » du

réseau. Le découpage du réseau en «grappes» peut être réalisé, selon les cas, suivant des

critères de localisation géographique, ou sur la base d’un découpage purement logique du

réseau. Dans certains cas les «grappes» sont elles-mêmes définies de manière à constituer une

structure hiérarchisée, la position d’un nœud spécifique dans cette hiérarchie déterminant

alors la méthode de routage utilisée pour atteindre ce nœud [41].

I.3.3.2. Description de quelques protocoles de routage MANET

A) Le protocole de routage DSDV

L’algorithme DSDV [42] a été conçu spécialement pour les réseaux mobiles. Chaque

station mobile maintient une table de routage qui contient toutes les destinations possibles, le

nombre de saut pour atteindre la destination et le numéro de séquence qui correspond à un

nœud destination, permettant de distinguer les nouvelles routes des anciennes et d’éviter la

formation de boucles de routage. Les mises à jour des tables sont transmises périodiquement à

travers le réseau afin de maintenir la consistance des informations ce qui génère un trafic


33

important qu’il faut limiter. Pour cela, deux types de paquets de mise à jour sont utilisés : les

"fulls dump", contenant toutes les informations et des paquets plus petits, ne contenant que les

informations ayant changé depuis le dernier "fulls dump". Les mises à jour sont soit

incrémentale ou complète.

B) Le protocole de routage OLSR

OLSR [43] est un protocole de routage pour les réseaux MANET proactif et qui a été

formalisé sous la forme de la RFC 3626 [44]. Il se base sur du routage par état de lien, mais

optimise celui-ci en minimisant le trafic nécessaire pour que chaque nœud connaisse la

topologie du réseau grâce aux relais multipoints MPR (Multi Point Relay) [44].

Les MPR sont des nœuds élus qui assurent le relais de l’information dans le réseau.

Chaque nœud émet la liste de ses voisins mais seuls les nœuds MPR la rediffusent.

Le protocole OLSR est performant dans les réseaux denses car les MPR permettent de

limiter l’inondation du réseau. Par contre, en termes de consommation énergétique, il sollicite

beaucoup les nœuds capteurs car ils doivent émettre en permanence des messages et c’est en

émission que les supports radio consomment le plus : OLSR est difficilement applicable pour

les RCSF.

C) Le protocole de routage DSR

Dans cette sous-section, nous allons détailler un peu plus ce protocole car le but de

notre travail est d’étudier le nouveau protocole de routage DYMO et ce dernier a hérité en

partie des fonctionnalités de routage de DSR (pour l’accumulation des chemins).

DSR [45] (Dynamic Source Routing) est l’un des premiers protocoles de routage qui a

été proposé pour les réseaux Ad Hoc. Après de nombreuses années, il a été normalisé sous la

forme de la RFC 4728 [46]. Il s’agit d’un protocole réactif qui a la particularité de s’appuyer

sur un routage par la source. En effet, lorsqu’un paquet est émis, celui-ci contient toutes les

informations (la liste des nœuds par lesquels doit passer le paquet) qui sont nécessaires à son

acheminement jusqu’à la destination (voir figure I.12). Le protocole se décompose en deux

grandes phases : la découverte et la maintenance de route qui seront expliquées dans ce qui

suit.


34

Figure I.12 : Emission d’un paquet dans le cas du routage par la source [47].

Découverte de route

Lorsqu’un nœud cherche à émettre un paquet vers une destination pour laquelle il n’a

pas de route en cache, le nœud initie une découverte de route vers la destination, appelée alors

la cible, et met le paquet dans un tampon. Ce dernier sera automatiquement vidé après un

délai sans réponse [48].

Un message RREQ est envoyé en diffusion à l’aide d’un mécanisme d’inondation. Ce

message contient les informations nécessaires au bon fonctionnement de la découverte de

route, à savoir : l’adresse du nœud initiateur, l’adresse de la cible, un identifiant unique de la

requête, ainsi qu’une liste de tous les nœuds parcourus par le message. Cette liste est

évidemment différente pour chaque instance du message.

Lorsqu’un nœud reçoit un message RREQ, s’il n’est pas la cible de cette requête, alors il

détermine s’il doit retransmettre la requête. Celle-ci ne sera retransmise que si aucune requête

du même nœud initiateur avec le même identifiant n’a été reçue et si le nœud n’apparait pas à

la liste des nœuds parcourus par le message. Avant l’éventuelle retransmission, le nœud

s’ajoute à la liste des nœuds parcourus.

Si le nœud recevant le message RREQ est la cible de la requête, alors une réponse RREP

est envoyée au nœud initiateur. Cette réponse contient la liste des nœuds parcourus par le

message RREQ reçu.

Lorsque le nœud initiateur reçoit une réponse RREP, la route fournie est mise en cache

afin de pouvoir être réutilisée ultérieurement. Les paquets mis en tampon pour la cible sont

finalement émis.

Maintenance de route

Quand un nœud détecte un problème fatal de transmission, à l’aide de sa couche liaison,

un message RERR est envoyé à l’émetteur original du paquet. Le message d’erreur contient


35

l’adresse du nœud qui a détecté l’erreur et celle du nœud qui le suit dans le chemin. Lors de la

réception du paquet RERR par le nœud source, le nœud concerné par l’erreur est supprimé du

chemin sauvegardé, et tous les chemins qui contiennent ce nœud sont tronqués à ce point là.

Par la suite, une nouvelle opération de découverte de route vers la destination est initiée par

l’émetteur [49].

Parmi les avantages du protocole DSR utilisant la technique « routage source », le fait

que les nœuds de transit n’aient pas besoin de maintenir les informations de mise à jour pour

envoyer les paquets de données, puisque ces derniers contiennent toutes les décisions de

routage. En outre, dans ce protocole, il y a une absence totale de boucle de routage, car le

chemin source destination fait partie des paquets de données envoyés.

I.4. Conclusion

Les RCSF possèdent un large domaine d’applications, synonyme de futurs marchés

lucratifs. Ils possèdent leurs propres caractéristiques et leurs propres contraintes. Ils

nécessitent donc de relever de nombreux challenges techniques, le plus important étant celui

de l’optimisation de l’énergie des nœuds capteurs.

Afin de remédier à ce problème, plusieurs protocoles de routage ont été proposés. Parmi

les limitations qu’on reproche aux protocoles de routage actuellement utilisés dans les RCSF

figure le problème de la distribution non équilibrée de charge dans le réseau ainsi que la

génération d’un grand nombre de messages de contrôle à chaque rupture de lien, ce qui

dégrade considérablement les performances de ce type de réseau.

Le routage multi-chemins semble être une solution efficace pour les réseaux à forte

charge en permettant de prémunir contre le problème de rupture de routes.

Nous étudierons dans les prochains chapitres les protocoles de routage réactifs AODV et

DYMO ainsi que leur version multi-chemins avec QoS afin d’améliorer les performances des

RCSF en termes de fiabilité et d’économie d’énergie.

Chapitre II. Le protocole de routage AODV Multi-chemins avec Qualité de Service

36

Chapitre II

Le protocole de routage AODV Multi-cheminsavec Qualité de Service

II.1. Introduction

Ce chapitre est consacré au protocole de routage AODV ainsi que sa version multi-

chemins étendue par des métriques de QoS telles que le délai et le taux d’erreur. Les résultats

très intéressants obtenus lors de l’étude de ce protocole [56], nous ont permis de le prendre

comme base d’évaluation en le comparant avec le protocole DYMO qui fera l’objet du

chapitre III.

Nous présentons en premier lieu le protocole AODV d’origine en illustrant les différents

types de paquets de contrôle utilisés, la table de routage et son mécanisme de fonctionnement.

Nous décrivons ensuite le protocole de routage AODV_MQ qui est une amélioration de

AODV supportant le routage multi-chemins avec QoS en explicitant en détail les différentes

extensions apportées à ce protocole.

Nous proposons également une approche pour la découverte de chemins multiples

disjoints en prenant en considération le facteur d’interférence. Ce dernier est mesuré par le

taux d’interférences.

II.2. Présentation du protocole de routage AODV

Le protocole AODV (Ad hoc On-demand Distance Vector) [50] est un protocole de

routage réactif ce qui signifie qu’une route vers une certaine destination n’est construite que

lorsqu’elle est nécessaire.

AODV emprunte l’utilisation des numéros de séquence de DSDV pour actualiser ses

informations de routage et se prémunir des boucles [51], tandis que sa procédure de

découverte de route est dérivée de celle adoptée par DSR (voir section I.3.3.2 (pp. 33). La

principale différence avec DSR est que la route découverte est stockée au niveau de chaque

nœud plutôt que dans l’entête du paquet.


37

Ce protocole fonctionne à partir de trois types de messages [52] : RREQ (Route

Request), RREP (Route Reply) et RERR (Route ERRor) qui seront présentés dans ce qui suit.

II.2.1. Gestion de la table de routage

Le protocole AODV maintient les chemins d’une façon distribuée en gardant une table

de routage, au niveau de chaque nœud de transit appartenant au chemin cherché [53].

Une entrée de la table de routage contient essentiellement :

L’adresse IP de la destination,

L’adresse IP du nœud suivant,

Le nombre de saut nécessaire pour atteindre la destination,

Le numéro de séquence de la destination,

La liste des voisins actifs,

Le temps d’expiration de l’entrée de la table (temps au bout duquel l’entrée est

invalidée),

L’état de la route et autres avertissements (valide, invalide, à réparer, en cours de

réparation).

De plus chaque nœud utilise une table source-broadcast_id qui contient le dernier

broadcast_id de chaque source qui a diffusé un RREQ. Cette table est utilisée pour faire la

différence entre les nouvelles demandes de route et les anciennes.

Pour éviter le problème du comptage à l’infini de Bellman-Ford [50]. On a recours à

l’utilisation de numéros de séquence dans les tables de routage en plus de la distance.

Le numéro de séquence accompagne son adresse dans les messages de contrôle et

permet aux autres nœuds de distinguer les messages importants des messages redondants.

Une mise à jour de la table de routage ne s’effectue que si l’une des conditions

suivantes est vérifiée :

Le numéro de séquence du paquet de contrôle est strictement supérieur au numéro de

séquence contenu dans la table de routage.

Les numéros de séquence (de la table et du paquet) sont égaux mais la distance en

nombre de saut du paquet plus «1» est inférieure à la distance actuelle dans la table de

routage.

Le numéro de séquence pour cette destination est inconnu.


38

II.2.2. Découverte de route

Un nœud source souhaitant communiquer avec un nœud destinataire doit d’abord

consulter sa table de routage. S’il ne trouve pas localement toutes les informations sur la route

à suivre ; il diffusera un message de demande de route (RREQ) aux nœuds voisins (voir figure

II.3(a)).

Le format général d’un paquet RREQ est illustré sur la figure II.1 suivante :

Figure II.1 : Format générale d’un paquet RREQ.

Un paquet RREQ contient essentiellement les champs suivant :

Type : indique le type du message,

Nbr_saut : ce champ est incrémenté à chaque saut, il détermine le nombre de saut vers la

source du RREQ,

Brcst_id : représente la combinaison de l’identificateur de la source avec son numéro de

séquence,

Dst_id : indique l’identificateur de la destination désirée,

Dst_ns : correspond au numéro de séquence de la destination désirée,

Src_id : indique l’identificateur de la source du RREQ,

Src_ns : correspond au numéro de séquence de la source du RREQ,

TTL : désigne la durée de vie du paquet RREQ.

Le champ Dst_ns du paquet RREQ recevra la dernière valeur connue du numéro de

séquence associé au nœud destinataire qui est recopiée de la table de routage. Si le numéro de

séquence n’est pas connu, la valeur nulle sera prise par défaut. Le champ Src_ns du paquet

RREQ recevra la valeur du numéro de séquence du nœud source.

Si aucun RREP n’est reçu durant une certaine période (appelée RREP_WAIT_TIME), la

source peut rediffuser une nouvelle requête RREQ.

A chaque nouvelle diffusion, le champ Brcst_id du paquet RREQ est incrémenté pour

identifier une requête de route particulière associée à une adresse source. Si la requête RREQ

est rediffusée un certain nombre de fois (RREQ_RETRIES) sans la réception de réponse, un

message d’erreur doit être délivré à l’application.

Avant de faire suivre le paquet RREQ à ses voisins, un nœud intermédiaire sauvegarde

aussi l’identificateur du nœud à partir duquel la première copie de la requête a été reçue. Cette

type Nbr_saut Brcst_id Dst_id Dst_ns Src_id Src_ns TTL


39

information est utilisée pour construire le chemin inverse (voir figure II.3(b)), qui sera ensuite

emprunté par le paquet RREP de manière unicast (mono destinataire).

A la réception d’un message RREQ, la destination envoie un RREP, ce message peut

donc être acheminé vers la source et les nœuds intermédiaires vont également modifier leur

table de routage suivant les champs contenus dans le paquet RREP.

Le format général d’un paquet RREP est illustré sur la figure II.2 suivante :

Type Nbr_saut Dst_id Dst_ns Src_id TTL

Figure II.2 : Format générale d’un RREP.

Un paquet RREP contient essentiellement les champs suivant :

Type : indique le type du message,

Nbr_saut : ce champ est incrémenté à chaque saut, il détermine le nombre de saut vers la

source du RREP,

Dst_id : indique l’identificateur de la destination du RREP,

Dst_ns : correspond au numéro de séquence de la destination du RREP,

Scr_id : indique l’identificateur de la source du RREP,

TTL : désigne la durée de vie du paquet RREP.

Une réponse adéquate qu’on appelle RREP gratuit « Gratuitous RREP » peut être

générée par un nœud intermédiaire si celui-ci possède une route fraîche vers la destination. Le

nœud intermédiaire enverra en plus un RREP vers la destination [53].

SD

SD

RREQ(a) RREP (b)

Figure II.3 : Etablissement d’une route entre S et D [49].

1

6

2

3

4

5

7

1

2

3

4

5

6

7


40

La figure II.3 illustre la procédure de découverte de route avec AODV. Afin de

découvrir un chemin vers la destination (D), la source (S) diffuse un RREQ. Ce dernier est

rediffusé par les nœuds intermédiaires jusqu’à ce qu’il atteint la destination (D). A la

réception du premier RREQ, la destination (D) répond par un RREP qui va suivre le chemin

inverse vers la source (S).

II.2.3. Maintenance de route

AODV propose deux méthodes pour détecter la présence des nœuds voisins et donc pour

détecter la rupture d’un lien de communication. La première est basée sur l’envoie de

messages HELLO (qui est un RREP avec un TTL égale à «1») à intervalle régulier tandis que

la seconde repose sur les informations émanant directement de la sous couche MAC.

Si un lien se brise le long d’une route active. Le nœud précédant la cassure peut choisir

d’effectuer une réparation locale ou bien délivrer un message d’erreur listant l’ensemble des

destinations injoignables. Par conséquent, Une nouvelle phase de demande de route devra être

établie par le nœud d’origine [49].

En règle générale, les erreurs de routes et les liens brisés requièrent un traitement en

quatre étapes [54]:

rendre invalides des routes existantes,

lister les nœuds destinataires affectés par ces erreurs,

déterminer les éventuels voisins affectés par ces erreurs,

envoyer le message d’erreur RERR approprié à ces voisins.

Le format des messages d’erreur de route (RERR) se distingue des autres messages par

les informations suivantes :

N (No Delete Flag) : ce drapeau est utilisé si un nœud vient de réparer un lien local. Il indique

aux autres nœuds de ne pas supprimer la route de leur table de routage.

DestCount : ce champ indique le nombre de destinations inaccessibles annoncées dans le

message. Du fait de la nature des messages RERR, ce champ doit valoir au moins «1».

Unreachable Destination IP Address : dans ces champs, il est indiqué la liste des adresses IP

des différentes destinations inaccessibles concernées par ce message.

Unreachable Destination Sequence Number : dans ces champs, il est indiqué la liste des

numéros de séquence des différentes destinations inaccessibles concernées par ce message.


41

II.3. Présentation du protocole AODV_MQ

La découverte de route avec AODV consiste à rechercher un chemin unique entre la

source et la destination. Cependant, La défaillance de ce chemin implique une nouvelle

procédure de recherche de route, ce qui prend plus de temps et consomme plus d’énergie.

Pour remédier à ce problème, le protocole AODV_MQ utilise l’approche multi-chemins pour

découvrir des chemins à nœuds disjoints. L’avantage de tels chemins est que s’il y en a un qui

tombe en panne, ceci n’influence en aucun cas sur le bon état des autres chemins, ce qui

assure un bon degré de fiabilité et une tolérance aux pannes dans le réseau [1].

Dans ce qui suit nous allons présenter la nouvelle structure des messages de routage

utilisés par le protocole AODV_MQ, définir les métriques de QoS intégrées dans AODV_MQ

ainsi que les différentes techniques de routage utilisées pour la découverte de routes multiples

[55] [56]. Nous introduirons également la procédure de découverte de route avec la prise en

considération de l’interférence.

II.3.1. Format des messages de contrôle et de la table de routage de AODV_MQ

II.3.1.1. Le nouveau format du paquet RREQ

Afin de trouver de multiples chemins avec une certaine QoS, des extensions ont été

apportées au paquet RREQ. Le nouveau format du paquet RREQ est présenté sur la figure II.4

suivante :

Figure II.4 : Le nouveau format du paquet RREQ.

Les huit premiers champs (Type, Nbr_saut, Brcst_id, Dst_id, Dst_ns, Src_id, Src_ns,

TTL) ont été expliqués précédemment dans la présentation de AODV (section II.2.2 (pp. 38)).

Les nouveaux champs intégrés sont les suivants :

Liste_nd : ce champ contient la liste des nœuds du chemin qui sera utilisé ensuite par le Sink

pour la sélection des chemins disjoints,

T_délai : ce champ indique le délai nécessaire pour transmettre des données de la source vers la

destination,

T_erreur : ce champ contient la valeur du taux d’erreur du chemin jusqu’au nœud courant.

C’est grâce aux valeurs calculées à partir de ces deux derniers champs, que le nœud

courant décide de faire suivre ou bien de supprimer le paquet de routage afin d’assurer la QoS

demandée en termes de délai et de taux d’erreur.

Type Nbr_saut Brcst_id Dst_id Dst_ns Src_id Src_ns TTL Liste_nd T_délai T_erreur


42

II.3.1.2. Le nouveau format du paquet RREP

Le nouveau format du paquet RREP est illustré sur la figure II.5 suivante :

Type Nbr_saut Dst_id Dst_ns Src_id TTL Liste_nd

Figure II.5 : Le nouveau format du paquet RREP.

Le seul champ intégré dans le message RREP est le suivant :

Liste_nd : ce champ contient le chemin disjoint trouvé par le Sink et qui va être stocké dans la

table de routage du nœud source.

Les six premiers champs illustrés dans ce paquet ont été expliqués dans la section II.2.2

(pp.39).

II.3.1.3. La structure de la table de routage étendue

La table de routage contient la liste de tous les chemins vers la destination (Sink) et les

chemins inverses. Chaque chemin à nœuds disjoints trouvé lors de la phase de découverte de

routes (dans notre cas le nombre de chemins est fixé à trois au maximum) doit être sauvegardé

dans la table de routage.

La nouvelle structure de la table de routage est illustrée sur la figure II.6 suivante :

Src_id Dst_id Dst_ns Pro_saut1 Pro_saut_valide1 Nbr_saut1

Src_id Dst_id Dst_ns Pro_saut 2 Pro_saut_valide 2 Nbr_saut 2

Src_id Dst_id Dst_ns Pro_saut 3 Pro_saut_valide 3 Nbr_saut 3

Figure II.6 : La structure étendue de la table de routage.

Une entrée de la table de routage contient essentiellement les champs suivant :

Scr_id : indique l’identificateur de la source,

Dst_id : désigne l’identificateur de la destination,

Dst_ns : correspond au numéro de séquence de la destination,

Pro_saut 1 : indique le prochain saut du premier chemin vers la destination,

Pro_saut_valide 1 : représente un drapeau qui indique si le premier chemin est valide ou pas,

Nbr_saut 1 : contient le nombre de nœuds intermédiaires du premier chemin.

Troischemins aumaximum


43

II.3.2. Définition des métriques de QoS intégrées dans AODV_MQ

Les métriques de QoS exprimées en termes de délai et de taux d’erreur sont évaluées

pendant la phase de découverte des chemins (voir section II.3.3.1 (pp.46)) en utilisant le

message RREQ de la manière suivante :

II.3.2.1. Le délai (métrique additive)

C’est le temps maximal nécessaire pour une transmission de paquets du nœud source au

nœud destinataire (Sink). Chaque fois que le nœud intermédiaire reçoit un message RREQ, il

soustrait du délai indiqué dans le message RREQ le Tnœud. .

Tnoeud représente le temps d’attente maximal d’un paquet dans la file d’attente du nœud

plus le temps de propagation vers le prochain saut. Si le résultat est supérieur à zéro, le nœud

courant retransmet le paquet vers le prochain saut du chemin menant à la destination. Sinon, il

détruit le message dans le cas contraire. Ce qui réduit le nombre de paquets de contrôle dans

le réseau. Le Tnœud est calculé comme suit [1] :

propagattentenoeud TTT (II.1)

Avec :

Tattente : le temps d’attente maximal dans la file d’attente du nœud,

Tpropag : le temps de propagation vers le prochain saut.

Calcul du temps d’attente (Tattente)

UN

Tattente avec rec NNN (II.2)

Où :

U : le nombre de paquets envoyés en une seconde,

N : le nombre de paquets entrants dans la file d’attente en une seconde,

Nc : le nombre de paquets capturés par le nœud en une seconde,

Nre : le nombre de paquets reçus des voisins en une seconde.

Calcul du temps de propagation (Tpropag)

Tpropag = distij / Vij (II.3)

Avec :

Vij : la vitesse de propagation entre le nœud i et le nœud j,

distij : la distance entre le nœud i et le nœud j.


44

Remarque : Cette formule de calcul du temps d’attente doit être utilisée en cas où nous avons

plusieurs nœuds sources ce qui va engendrer plus de trafic dans le réseau, d’où la nécessité de

calculer d’une manière dynamique le temps d’attente au niveau de chaque nœud. Cependant,

en cas où nous avons juste une seule source, il est préférable d’utiliser le paramètre

NTT « Node Traversal Time » pour estimer le délai, qui existe déjà dans le code source de

AODV et qui est considéré comme constant de 30 ms.

La figure II.7 montre comment le message RREQ peut être diffusé ou rejeté par les

nœuds intermédiaires lors de la phase de découverte de routes. A chaque saut, le champ T_délai

du RREQ est modifié. La demande de chemin RREQ1 avec un T_délai = 100 est aboutie au

Sink avec un T_délai positif égal à (70 – 30 = 40), donc possibilité de trouver un chemin

disjoint qui satisfait la QoS délai. Par contre, RREQ2 avec T_délai = 50 n’aboutira jamais au

Sink, parce qu’au niveau du deuxième nœud intermédiaire, le T_délai devient négatif (20 – 30

= -10) et donc rejet du RREQ2.

Figure II.7 : Vérification du délai de transmission d’un chemin.

II.3.2.2. Le taux d’erreur (métrique multiplicative)

Un chemin qui assure une QoS est celui qui possède la plus petite valeur de taux

d’erreur (et par conséquent la plus grande valeur de taux de succès). Le taux d’erreur d'un

chemin est calculé à partir du message RREQ tel que la valeur du champ T_erreur représente le

produit des taux d’erreur de chaque nœud intermédiaire appartenant au chemin courant [1]

(chemin illustré sur la figure II.7) :

T_erreur = T (A, B) * T (B, C) * T (C, D) (II.4)

Avec:

A : désigne le premier nœud du chemin vers la destination,

B, C : représentent des nœuds intermédiaires,

A DB C

SinkSourceRREQ 1(T_délai = 100)

RREQ 1(T_délai = 70)



RREQ 2(T_délai = 20)Tnoeud = 30 Tnoeud = 30


45

D : désigne le nœud destinataire,

T (A, B) : indique la valeur du taux d’erreur du nœud A.

Le taux d’erreur de chaque nœud est calculé comme suit [1] :

jVjiD

jiT),(

*),( (II.5)

Tel que :

T (i,j) : définit la valeur du taux d’erreur entre un nœud i et un nœud j,

α: désigne un facteur,

D (i, j) : représente la distance entre i et j (nous l’avons fixé à 100 m),

Vj : indique l’espace inoccupé dans la file d’attente du nœud j.

II.3.3. Découverte de routes multiples avec AODV_MQ

La section suivante décrit le mécanisme de découverte de chemins disjoints, basé sur

l’accumulation des nœuds du chemin pendant la découverte et la mémorisation des plus

courts chemins afin de minimiser le nombre de messages de contrôle (overhead) dans le

réseau.

Paquets RREQ diffusésPaquets RREQ supprimésPaquets RREP envoyés

Figure II.8 : Procédure de découverte de chemins avec une diffusion minimale [56].

S

A

B

D

E

G

H

C F

<S,A>

<S,C>

<S,B>

<S,A,D> <S,A,D,G>

<S,B,E> <S,B,E,H>

<S,C,F>

<S,C,E> <S,C,E,H>

<S,C,D,G><S,C,D>

C1=<S,A,D,G,Sink>

C2=<S,C,F,Sink>

C3=<S,B,E,H,Sink>

Sink

C1

C2

C3


46

Lorsqu’un nœud source désire envoyer des données au nœud destinataire (Sink), il doit

d’abord vérifier si un chemin vers le Sink existe déjà dans sa table de routage, si ce n’est pas

le cas, le nœud source doit générer et diffuser un paquet RREQ. La valeur initiale du T_délai est

fixée par l’application cible et représente la valeur du délai nécessaire pour assurer une

transmission avec QoS.

II.3.3.1. Traitement du paquet RREQ

Dans ce qui suit nous décrirons les différentes fonctions des nœuds intermédiaires ainsi

que le nœud destinataire lors de la réception d’un message RREQ.

A) Le rôle d’un nœud intermédiaire et la réduction du nombre de messages de contrôle

Comme l’augmentation du nombre de messages de contrôle influe largement sur la

bande passante et surtout sur l’énergie associée aux nœuds capteurs qui est un paramètre très

important pour la communication et le traitement, donc la réduction du nombre de diffusion

de paquets de contrôle est essentielle pour économiser les ressources limitées du RCSF. Afin

de réduire ce nombre, nous avons opté pour une approche d’accumulation des nœuds du

chemin combinée avec des contraintes de délai et de taux d’erreur.

Lorsqu’un nœud intermédiaire reçoit un paquet RREQ, celui-ci doit d’abord mettre à

jour les valeurs du T_délai ainsi que du T_erreur. Si le délai est positif et le taux d’erreur est

inférieur à un seuil donc le paquet RREQ sera accepté, sinon il sera supprimé dans le cas

contraire.

Quand un nœud reçoit le premier RREQ, il doit sauvegarder la valeur du Nbr_saut

comme le nombre de saut du plus court chemin inverse de sa table de routage. Lorsque le

nœud reçoit le même RREQ d’un autre chemin, il compare le Nbr_saut de ce RREQ avec le

Nbr_saut du plus court chemin inverse sauvegardé. S’il trouve que le Nbr_saut du RREQ est

supérieur, donc il détruit ce RREQ. Sinon, le nœud ajoute son adresse à la liste du chemin et

diffuse le RREQ à ses voisins. Sur la figure II.8, on remarque qu’il existe 6 chemins possibles

à partir du nœud S au nœud C : <S,C> (1 saut), <S,A,C> (2 sauts), <S,B,C> (2 sauts),

<S,A,D,C> (3 sauts), <S,B,E,C> (3 sauts), <S,C,F,C> (une boucle de 3 sauts). Lorsque le

nœud C reçoit le premier RREQ venu du chemin <S,C>, il mémorise «1» comme le nombre

de saut du plus court chemin et détruit les cinq autres paquets RREQ.

Donc cette approche, qui est basée sur la mémorisation du plus court chemin inverse,

réduit le nombre de paquets RREQ pendant la phase de découverte de chemins disjoints et

garantie une absence totale de boucle de routage.

L’organigramme de la réduction de diffusion des paquets RREQ est illustré sur la figure II.9.


47

Oui

Non

Non

Oui

Oui

Non

Oui

Non

Oui Non

Oui

Figure II.9 : Organigramme de la réduction de diffusion des paquets RREQ.

Début

Recevoir un paquet RREQ

Lire l’adresse source du RREQ

L’adresse destination duRREQ = L’adresse du nœud ?

Lire l’adresse destination du RREQ

L’adresse source du RREQ= L’adresse du nœud ?

Mettre à jour la valeur du T_erreur

Mettre à jour la valeur du T_délai

T_délai > 0 et T_erreur < seuil ?

Brcst_id > RREQ_ID de latable source-broadcast_id ?

Brcst_id = RREQ_ID de latable source-broadcast_id ?

Lire le Nbr_saut du RREQ

Nbr_saut du RREQ < Nbr_sautdu plus court chemin inverse ?

Détruire le RREQ

RREQ_id = Brcst_id

Nbr_saut du plus court chemininverse = Nbr_saut du RREQ

Ajouter l’adresse du nœud dansListe_nd

Diffuser le paquet RREQ auxnœuds voisins

Fin

Procédure desélection des

chemins disjoints

Lire le Brcst_id du RREQ

Non


48

B) Le rôle du nœud destinataire et la sélection des chemins disjoints

Le Sink est responsable de la sélection et de la sauvegarde des chemins disjoints. A la

réception du premier RREQ (le plus court chemin : S-C-F-Sink) (voir figure II.8), le Sink va

d’abord sauvegarder la liste des nœuds de ce chemin Liste_nd dans son cache, générer ensuite

une réponse RREP contenant cette liste de nœuds et l’envoyer à travers le chemin inverse vers

la source. Si le Sink reçoit un autre paquet RREQ, il compare le chemin contenu dans ce

RREQ (Liste_nd) avec chaque chemin disjoint sauvegardé dans son cache. Si le nouveau

chemin n’à aucun nœud en commun (sauf la source et la destination) avec les autres chemins

disjoints, alors le Sink va l’accepter et le sauvegarder dans son cache. Sinon, le RREQ sera

détruit.

L’organigramme de la sélection des chemins disjoints est présenté sur la figure II.10.

Oui Non

Oui

Oui

Non

Figure II.10 : Organigramme de la sélection des chemins disjoints.

Début

Lire le Brcst_id du RREQ

Brcst_id > RREQ_id de la tablesource-broadcast_id ?

Brcst_id = RREQ_id de la tablesource-broadcast_id ?

RREQ_id = Brcst_id

Sauvegarder le chemin dans lecache

Le chemin Liste_nd estdisjoint avec le reste deschemins sauvegardés ?

Détruire le RREQ

Ajouter l’adresse de destinationà la liste des nœuds du chemin

Incrémenter le numéro deséquence

Générer un paquet RREP

Envoyer le paquet RREP aunœud à partir duquel le RREQ a

été reçu

Fin

Non


49

II.3.3.2. Traitement du paquet RREP

Nous décrirons dans ce qui suit le rôle des nœuds intermédiaires ainsi que le nœud

source lors de la réception d’un message RREP.

A) Le rôle d’un nœud intermédiaire

Lorsqu’un nœud intermédiaire reçoit un paquet RREP, celui-ci doit d’abord vérifier si le

numéro de séquence du RREP est supérieur ou égal à celui de la table de routage, si c’est le

cas, il va mettre à jour sa table de routage à partir du champ Liste_nd du RREP : il enregistre

l’ID du nœud destinataire et l’ID du nœud voisin à partir duquel le RREP a été reçu dans

l’entrée de route suivante de la table de routage. L’ID du nœud source et l’ID du nœud du

prochain saut vers la source seront enregistrés dans l’entrée de route inverse de la table de

routage. Enfin, le nœud intermédiaire expédie le message RREP vers la source à travers le

chemin inverse.

B) Le rôle du nœud source

Lorsque le premier paquet RREP arrive au niveau du nœud source, si la condition du

numéro de séquence est vérifiée, ce dernier doit enregistrer l’ID du nœud du prochain saut

vers la destination dans l’entrée de route suivante et peut commencer à l’utiliser pour envoyer

les paquets de données. Pour les autres paquets RREP qui arrivent par la suite au nœud

source, ils seront sauvegardés dans la table de routage comme chemins alternatifs utilisés en

cas où une rupture de lien est détectée. Vu la capacité de stockage restreinte des nœuds

capteurs, le nombre de chemins disjoints enregistrés dans la table de routage du nœud source

a été limité à trois au maximum.

L’organigramme de traitement d’un message RREP est illustré sur la figure II.11.


50

Non

Non Oui

Oui

Non

Non

Oui

Oui

Figure II.11 : Organigramme de traitement d’un message RREP.

II.3.4. Découverte de routes multiples avec la prise en compte de l’interférence

Dans ce mémoire, nous nous sommes focalisé sur l’étude du routage multi-chemins en

exploitant les chemins trouvés alternativement pour satisfaire un objectif de tolérance aux

pannes. Cependant, pour un travail futur, si on désire faire du parallélisme, c’est-à-dire,

Début

Recevoir un paquet RREP

Lire l’adresse destination du RREP

Dst_ns du RREP >=Dst_ns de la table de

routage ?

Envoyer le paquet RREP vers le prochain saut

Lire le Dst_ns du RREP

L’adresse destination duRREP = l’adresse du nœud ?

Lire la liste des nœuds du chemin

Mettre à jour la table de routage

Envoyer les paquets de données

Fin

Vérifier le nombre de routes existantes dans la tablede routage

Nombre de routes > 3 ?


Dst_ns du RREP >=Dst_ns de la table de

routage ?

Lire le Dst_ns du RREP


51

exploiter les différents chemins simultanément pour transmettre par exemple un trafic vidéo,

ceci, peut engendrer des problèmes d’interférence entre les chemins empruntés et dégrader par

conséquent les performances du réseau.

Afin de limiter les interférences dans le réseau tout en bénéficiant du routage multi-

chemins, nous proposons dans ce qui suit une manière de calculer le taux d’interférences de

chaque chemin trouvé lors de la procédure de découverte de routes avec AODV_M et choisir

par conséquent au niveau du nœud source juste les chemins qui présentent moins de risque

d’interférence.

Ce taux d’interférences est calculé par l’équation (II.6) [57] au niveau de chaque nœud

intermédiaire recevant un message RREP.

i

Ijij

i I

INT new

(II.6)

Avec:

Ti : le taux d’interférences du ième chemin disjoint qui a déjà atteint le nœud source,

Nj : la liste des nœuds voisins du nœud j,

Ii : l’ensemble des nœuds intermédiaires inclus dans le ième chemin,

Inew : l’ensemble des nœuds intermédiaire du RREP courant,

On note par |X| le nombre d’éléments de l’ensemble X.

Le nouveau format du message RREP pour le calcul du taux d’interférences est illustré

sur la figure II.12 suivante :

Type Nbr_saut Dst_id Dst_ns Src_id TTL Liste_nd Liste_nd_i Nbr_saut_i IF

Figure II.12 : Format d’un message RREP pour le calcul du taux d’interférences.

Les sept premiers champs (Type, Nbr_saut, Dst_id, Dst_ns, Src_id, TTL, Liste_nd) ont

été expliqués précédemment (voir section II.3.1.2 (pp. 42)).

Les nouveaux champs intégrés sont les suivants :

Liste_nd_i : ce champ contient la liste des nœuds du chemin qui a déjà été envoyé au

préalable au nœud source,

Nbr_saut_i : indique le nombre de saut du chemin précédent, utilisé pour calculer le nombre

de nœuds intermédiaires du chemin précédent.

IF : représente le taux d’interférences.


52

Le calcul du taux d’interférences est illustré plus en détail à travers l’exemple de la

figure II.13 suivante :

Paquets RREP

Figure II.13 : Transmission des messages RREP et calcul du taux d’interférences.

Après la diffusion du message RREQ, le Sink va accepter le premier RREQ et

transmettre le message RREP adéquat.

A la réception du deuxième RREQ, le Sink va d’abord vérifier si le chemin inclus dans

ce RREQ est disjoint avec les autres RREQ stockés dans son cache. Si c’est le cas, donc il va

générer un deuxième RREP et insérer la liste des nœuds du chemin précédent dans le champ

Liste_nd_i de ce RREP.

A la réception du second RREP par le premier nœud intermédiaire G, ce dernier va

calculer le taux d’interférences à l’aide de la formule (II.6) de la manière suivante :

i

Ijij

i I

INT new

21

),(),(),,(

1 FC

FCFDSinkT

Après avoir calculé le taux d’interférence à son niveau, le nœud intermédiaire doit

additionner la valeur trouvée avec celle qui existe déjà dans le champ IF (puisque c’est le

premier nœud intermédiaire donc la valeur antérieur de IF est nulle). La nouvelle valeur de

IF va être insérée ensuite dans ce dernier champ et le RREP sera expédié au nœud du prochain

saut (le nœud D).

A la réception de ce RREP par le nœud intermédiaire D, ce dernier va calculer le taux

d’interférences à l’aide de la formule (II.6) de la même manière que le nœud G comme suit:

23

),(),(),,,(

21

1 FC

FCGFCAT

S

A

B

D

E

G

H

C F

C2=<S,A,D,G,Sink>

C1=<S,C,F,Sink>

Sink


53

Ensuite le nœud D va inclure cette nouvelle valeur dans le champ IF et expédier le

RREP au nœud A.

Le nœud A va mettre à jour à son tour le champ IF du nouveau RREP reçu en effectuant

le même calcul comme suit :

2),(

),(),,(23

1 FC

FCDCST

Enfin, lorsque le RREP atteindra sa destination, le nœud source va consulter le champ

IF pour comparer sa valeur avec le seuil de tolérance. Dans cet exemple, le chemin

<S,A,D,G,Sink> n’a pas été accepté au niveau du nœud source car la valeur du taux

d’interférences de ce RREP excède le seuil de tolérance fixé par l’application (seuil fixé à «1»

par exemple).

II.3.5. Maintenance de routes

Si un lien se rompt d’une façon brusque, le nœud qui se trouve à l’extrémité du lien

avise les autres nœuds, qu’il n’est plus possible d’atteindre la destination en envoyant un

message RERR à travers le chemin inverse. En recevant un RERR, un nœud intermédiaire

marque la route vers cette destination comme invalide et renvoi à son tour le RERR vers ses

nœuds précurseurs à travers le chemin inverse. Après la réception d’un RERR, le nœud source

doit d’abord rendre invalide la route vers le nœud destinataire et sélectionner ensuite un autre

chemin à nœud disjoint alternatif à partir de la table de routage. Ceci, afin de poursuivre le

processus d’envoi de paquets de données ou bien initier une nouvelle procédure de découverte

de routes si tous les chemins sont épuisés [55].

II.4. Conclusion

Le protocole de routage AODV_MQ se base sur le principe de AODV. Cependant,

plusieurs extensions ont été apportées à ce dernier pour la recherche de multiples chemins à

nœuds disjoint qui vérifient des conditions de QoS.

Ce protocole multi-chemins sera utilisé par la suite pour effectuer différentes

simulations afin de le comparer avec le nouveau protocole DYMO multi-chemins avec QoS.

Dans le prochain chapitre, nous allons d’abord présenter le protocole de routage DYMO

qui est vue comme le successeur de AODV et expliciter ensuite toutes les modifications

effectuées sur le protocole DYMO pour assurer un routage multi-chemins à nœuds disjoints

avec des contraintes de QoS dans le but de satisfaire les exigences des RCSF.

Chapitre III. Le protocole de routage DYMO Multi-chemins avec Qualité de Service

54

Chapitre III

Le protocole de routage DYMO Multi-cheminsavec Qualité de Service

III.1. Introduction

Dans ce chapitre nous présentons le nouveau protocole de routage DYMO « DYnamic

Manet On-demand » en voie de standardisation par l’IETF qui est une évolution du protocole

AODV et qui vise à rendre celui-ci plus souple par l’utilisation d’un format de message

générique.

Nous proposons ensuite une extension multi-chemins à nœuds disjoints avec QoS de ce

protocole de routage afin d’en améliorer les performances et d’assurer plus de fiabilité dans le

réseau.

III.2. Présentation du protocole de routage DYMO

Le protocole DYMO représente l’une des plus récentes propositions en matière de

routage pour les réseaux MANET. Le but de ce nouveau protocole de routage est de garder le

meilleur des protocoles de la génération précédente en combinant les avantages de AODV et

de DSR. DYMO se base sur la technique de routage à la demande qui possède les

caractéristiques suivantes :

Un routage adapté aux réseaux à topologie dynamique qui minimise le nombre de

diffusion de messages de contrôle.

Une consommation d’énergie contrôlée et qui correspond aux routes effectivement

utilisées par les informations échangées.

Au cours de la première partie de ce chapitre, nous allons d’abord donner un bref aperçu

sur les idées à l’origine de la conception du protocole DYMO. Nous développons ensuite

toutes les spécificités du mode de routage employé par ce protocole en explicitant le format

des messages utilisés ainsi que la structure et les conditions de mise à jour de la table de

routage. Enfin, les mécanismes de découverte et de maintenance de routes seront expliqués et

illustrés par la suite à travers des exemples.


55

III.2.1. Origines de DYMO

DYMO n’est pas le premier protocole réalisé en vue d’apporter des améliorations à

AODV. Des travaux similaires ont déjà été menés auparavant comme ceux proposés par

Gwalani et al. [58] :

AODV avec accumulation du chemin (AODV-PA : AODV with Path Accumulation) [59]

a été étendu par la fonction d’accumulation du chemin inspirée de DSR. Ses développeurs ont

déduit que ce protocole améliore considérablement les performances du réseau par rapport à

AODV et il est mieux adapté aux réseaux à grande échelle.

AODVjr [60], dont les auteurs ont enlevé les éléments essentiels de AODV comme le

numéro de séquence, les RREP gratuits, le nombre de saut, les messages Hello, les messages

RERR et les listes des précurseurs. Ce qui reste est juste la découverte de route de base, en

utilisant les messages RREQ et RREP où seule la destination répond aux RREQ. A l’aide du

simulateur NS2 , ils ont conclu que AODVjr réalise presque les mêmes performances que

AODV, cependant, le nombre de messages de contrôle est inférieur.

En se basant sur AODV, DYMO a combiné les idées à l’origine de AODV-PA et

AODVjr. De AODV-PA (et DSR), il emprunte l’accumulation du chemin. En s’inspirant de

AODVjr, DYMO a enlevé aussi quelques fonctionnalités telles que les RREP gratuits, la liste

des précurseurs et les messages Hello (optionnels). Comparé à AODVjr, DYMO garde les

numéros de séquence, le nombre de saut et les messages RERR.

III.2.2. Principe de fonctionnement

DYMO est un protocole de routage réactif, se fondant sur le routage par vecteur de

distance. Son fonctionnement se base principalement sur deux mécanismes : La découverte et

la maintenance de route [61] (qui seront expliqués plus en détail respectivement dans les

sections III.2.5 (pp. 63) et III.2.6 (pp. 66)).

Lors de la procédure de découverte de route, le nœud source diffuse un message RREQ

à travers le réseau afin de trouver une route vers la destination. Durant ce processus de

dissémination, chaque nœud intermédiaire enregistre une route vers tous les nœuds dont

l’adresse est incluse dans le message, ajoute sa propre adresse et rediffuse ensuite le RREQ à

ses voisins. Lorsque le nœud destinataire reçoit un message RREQ, il génère un message

RREP qui sera envoyé d’une manière unicast vers le nœud source [62]. De manière similaire

au traitement d’un RREQ, chaque nœud intermédiaire qui reçoit un message RREP va prendre

note de toutes les informations de routage sauvegardées dans le message et ajouter sa propre

adresse. Lorsque le nœud source reçoit le RREP, la route sera alors établie dans les deux sens.


56

De surcroît, comme tout protocole de routage réactif, DYMO dispose d’un mécanisme

de maintenance de route pour reporter la coupure d’un lien aux autres nœuds. L’annonce des

pertes de connectivité se fait par le biais de la diffusion de messages RERR afin d’indiquer

aux autres nœuds la route dont la destination est inaccessible.

DYMO utilise le principe des numéros de séquence tout comme AODV afin d’éviter la

génération de boucles de routage [63]. Les numéros de séquence permettent aux nœuds de

déterminer l’ordre temporaire des messages de découverte de route en évitant ainsi

l’utilisation d’anciennes informations de routage.

Nous avons décrit, dans ce paragraphe, le fonctionnement de base du protocole DYMO.

Dans ce qui suit, nous présentons en détail le format des messages de contrôle utilisés par le

protocole DYMO.

III.2.3. Format des messages DYMO

III.2.3.1. Structure générale d’un message DYMO

Un message DYMO se compose d’une partie entête (header part) et d’une partie corps

(body part) du message. Le corps du message peut contenir 0-occurrence ou plus de blocs de

message TLV (Type-Length-Value block) qui désignent les attributs associés au message et 0-

occurrences ou plus de blocs d’adresses (adress block). Chaque bloc d’adresse est divisé

d’une partie entête d’adresse et d’une partie corps d’adresse. La partie corps d’adresse

contient à son tour 0-occurrence ou plus de blocs d’adresse TLV (les attributs associés à

chaque adresse). Cette représentation est illustrée sur la figure III.1 [65].

IP

header

UDP

header

Message

header

Message

TLV

Address header

(Zero or more

instances

Address TLV

(Zero or more

instances)

Figure III.1: Format d’un message DYMO.

III.2.3.2. Structure des messages de routage (MR)

Les MR sont utilisés pour diffuser des informations de routage dans le réseau. Il existe

deux types de messages DYMO qui sont considérés comme MR : RREQ et RREP. Ils

contiennent des informations ainsi que des fonctions similaires mais leurs règles de traitement

diffèrent légèrement [64]. La création et le traitement des MR sont décrits dans la section

III.2.5 (pp. 63).


57

Un MR nécessite les informations suivantes :

IP.SourceAddresse : indique l’adresse IP du nœud actuel qui envoi ce paquet,

IP.DestinationAddress : désigne l’adresse IP du nœud du prochain saut,

UDP.DestinationPort : indique le port UDP de la destination,

MsgHdr.HopLimit : représente le nombre de saut maximal qui reste à traverser par ce

message,

AddBlk.TargetNode.Address : correspond à l’adresse IP du nœud destinataire du message,

AddBlk.OrigNode.Address : désigne l’adresse IP du nœud source,

OrigNode.AddTLV.SeqNum : contient le numéro de séquence du nœud source.

Un MR peut inclure optionnellement les informations suivantes :

TargetNode.AddTLV.SeqNum : désigne le dernier numéro de séquence connu du nœud

destinataire,

TargetNode.AddTLV.Dist : correspond à la dernière distance connue vers la destination,

OrigNode.AddTLV.Dist : représente une métrique de la distance pour atteindre le nœud

source. Ce champ est incrémenté par «1» au niveau de chaque nœud intermédiaire,

AddBlk.AdditionalNode.Address : contient l’adresse IP d’un nœud supplémentaire. A Chaque

nœud supplémentaire (AdditionalNode.Address) doit être associé un numéro de séquence

(Node.SeqNum) dans le bloc d’adresse TLV,

AdditionalNode.AddTLV.SeqNum : désigne le numéro de séquence associé à cette information

de routage,

AdditionalNode.AddTLV.Dist : représente une métrique de la distance pour atteindre le nœud

supplémentaire (AdditionalNode.Address) associé. Ce champ est incrémenté par «1» au

niveau de chaque nœud intermédiaire.

III.2.3.3. Structure du message d’erreur de route (RERR)

Un message RERR est utilisé afin de notifier qu’une route n’est plus disponible pour

une ou plusieurs adresses IP. La création et le traitement d’un message RERR sont décrits

dans la section III.2.6 (pp. 66).

Un message RERR nécessite les informations suivantes [64] :

IP.SourceAddresse : désigne l’adresse IP du nœud actuel qui envoi ce paquet,

IP.DestinationAddress : indique l’adresse IP du destinataire du paquet,

UDP.DestinationPort : correspond au port UDP de la destination,

MsgHdr.HopLimit : représente le nombre de saut maximal qui reste à traverser par ce

message,


58

Target.SeqNum

tlv-length = 2

AddBlk.UnreachableNode.Adress : désigne l’adresse IP du nœud inaccessible.

Un message RERR peut inclure optionnellement l’information suivante :

UnreachableNode.AddTLV.SeqNum : correspond au dernier numéro de séquence connu du

nœud inaccessible.

III.2.3.4. Exemple d’un MR

Comme exemple concret d’un paquet utilisant une structure de message générique, un

paquet DYMO RREQ est présenté sur la figure III.2. Les premiers 8 octets du message

représentent l’entête du message et les octets qui suivent représentent le bloc d’adresses et

leurs blocs TLV associés. Les différents champs du message sont expliqués plus en détail dans

ce qui suit [66].

0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 1 2 3 4 5 6 7 8 9 3 1IP Header 0 0 0

UDP Header

Message Header

Message TLV Block

Message Body – Address Block

Message Body – Address Block TLV Block

Figure III.2 : Exemple d’un message DYMO de demande de route [66].

IP.SourceAddress

IP.DestinationAddress = LL-MANET-ROUTERS

IP TTL/HopLimit = 255

Destination Port = MANET

Msg-type :DYMORREQ

Msg-semanticsReserved U 0 0 1

Msg-size = 29

Msg-ttl Msg-hopcnt

Msg-tlv-block-size = 0

Head Length = 3 Head

Nbr of Tails = 2 Target.Tail Originator.Tail tlv-block-size…

tlv-block-size = 12 tlv-type :DYMOSeqNum

tlv-semanticsReserved 1 1 0 0

tlv-length = 4

Orig.SeqNum

tlv-type :DYMOHopCnt

tlv-semanticsReserved 1 1 0 0

Orig.HopCnt

Target.HopCnt


59

A) L’entête du message

Un entête de message se compose des champs suivants : msg-type, msg-semantics,

msg-size, et msg-tlv-block-size. Le MR illustré sur la figure III.2 est de type RREQ et a une

taille spécifiée de 29 octets, c’est-à-dire, la taille totale de l’entête et du corps du message.

Les champs msg-semantics représentent l’interprétation du reste de l’entête du message

car il peut inclure optionnellement des champs supplémentaires.

Les différents bits du champ msg-semantics sont interprétés comme suit :

Bit 12 : s’il est égal à «1», le message ne peut être expédié si le type du message est inconnu

au destinataire,

Bit 13 : s’il est égal à «1», le message source maintient les numéros de séquence pour chaque

type de message,

Bit 14 : s’il est égal à «1», les champs ttl et nombre de saut ne sont pas inclus,

Bit 15 : s’il est égal à «1», les champs d’adresse d’origine et de numéro de séquence ne sont

pas inclus.

Sur la figure III.2, on constate qu’après les champs du msg-size, l’entête du message

inclut également les champs ttl et nombre de saut. C’est pour cette raison que le bit 14 du

champ msg-semantics est égal à «0». Le champ msg-tlv-block-size vaut «0», ce qui signifie

qu’aucun bloc TLV ne suit l’entête du message.

B) Le corps du message

Le corps du message DYMO RREQ se compose d’un nombre d’adresses et des attributs

associés à ces adresses. Les adresses sont contenues dans un ou plusieurs blocs d’adresses et

les attributs sont contenus dans un bloc TLV suivant chaque bloc d’adresse.

Le bloc d’adresses

En supposant qu’une adresse peut être spécifiée comme une séquence de bits de la

forme head : tail, pour représenter un ensemble d’adresses sous une forme compacte, la plus

longue séquence d’octets les plus à gauche, l’entête, peut être divisé et avoir différentes

queues (tails), c’est-à-dire, des parties distinctes d’adresses. Et par conséquent, les adresses

contenues dans un bloc d’adresses partagent le même entête et possèdent différentes queues.

La figure III.2 illustre un exemple de bloc d’adresses contenant les adresses de

l’émetteur et du destinataire. Le premier champ de ce bloc désigne la taille de l’entête

spécifiant que l’entête est de 3 octets. Les 3 octets suivants donnent sa valeur actuelle.

Ensuite, figure le nombre de queues, qui dans ce cas indique que deux queues suivent. En


60

concaténant le champ de l’entête avec le champ de Target.Tail on obtient l’adresse IP du

destinataire du RREQ, de même pour le champ Originator.Tail afin d’obtenir l’adresse IP de

l’originaire du RREQ.

Par exemple, si les trois octets de l’entête sont égales à 192, 168 et 42 et les champs du

Target.Tail et du Originator.Tail contiennent 50 et 51, respectivement, l’adresse IP du

destinataire du RREQ sera égale à 192.168.42.50 et l’adresse IP de l’originaire sera égale à

192.168.42.51.

Le bloc TLV

Comme on peut le distinguer sur la figure III.2, les champs tlv-block-size spécifient que

la taille des TLV qui suivent est de 12 octets.

Un TLV se compose des deux champs suivants : tlv-type et tlv-semantics. Dépendant de

la valeur des bits du tlv-semantics, il peut inclure de plus les champs suivants : tlv-length, tlv-

index-start, tlv-index-stop, tlv-value. Le champ tlv-length donne la taille en octets des données

présentes dans le champ tlv-value. Les deux champs index permettent au TLV d’inclure une

séquence d’adresses.

Les bits du champ tlv-semantic sont interprétés comme suit (la numérotation est

interprétée à partir du dernier bit (le plus à droite sur la figure III.2)):

Bit 0 : le bit « novalue » ; s’il est égal à «1», le TLV ne contient pas les champs length et

value,

Bit 1 : le bit « extended » ; s’il est égal à «1» la taille du champ sera égale à 16 (sinon elle sera

égale à 8),

Bit 2 : le bit « noindex » ; s’il est égal à «1», les éléments index-stop et index-start ne sont pas

inclus,

Bit 3 : le bit « multivalue » ; s’il est égale à «1», le TLV inclut des valeurs séparées pour

chaque adresse spécifiée.

En observant le paquet DYMO RREQ sur la figure III.2, on remarque que les bits 2 et 3

sont égaux à «1» pour les deux TLV. Et par conséquent, les TLV ont inclus les champs length

et value et des valeurs séparés pour toutes les adresses. Cependant, les champs index-start et

index-stop n’ont pas été introduit.

Le premier TLV est de type DYMOSeqNum et possède une taille spécifiée de 4 octets

pour le champ value. Comme le bloc d’adresses associé contient deux entrées, le champ est

divisé en deux champs de même taille. Le premier donne le numéro de séquence de la

première adresse présente dans le bloc d’adresses, c’est-à-dire, le nœud source, et le champ de


61

la dernière valeur donne le numéro de séquence de la seconde adresse incluse dans le bloc

d’adresses, ce qui correspond dans ce cas au dernier numéro de séquence de la cible.

Le second TLV est de type DYMOHopCnt et a une taille spécifiée de 2 octets pour le

champ value. Ici encore, le champ est divisé en deux champs de même taille. Leurs valeurs

désignent le nombre de saut pour les deux adresses qui figurent dans le bloc d’adresses.

III.2.4. Les opérations de la table de routage

Chaque nœud dans le réseau maintient à jour une table de routage, dans laquelle il

enregistre les informations sur la topologie du réseau, obtenues à partir des messages de

contrôle. Nous présentons dans cette section, la structure de la table de routage ainsi que les

conditions exigées par le protocole DYMO afin de garantir des routes sans boucle de routage.

III.2.4.1. Structure de la table de routage

La structure de la table de routage est illustrée sur la figure III.3 suivante :

Route.

Address

Route.

Prefix

Route.

SeqNum

Route.

NextHopAddress

Route.

Forwarding

Route.

Broken

Route.

Dist

Figure III.3 : Format de la table de routage de DYMO [64].

Une entrée de la table de routage est composée des champs suivants [64] :

Route.Address : désigne l’adresse IP de la destination,

Route.Prefix : Indique que l’adresse associée est une adresse réseau au lieu d’une adresse

host,

Route.SeqNum : correspond au numéro de séquence associé à cette information de routage,

Route.NextHopAddress : désigne l’adresse IP du nœud du prochain saut vers

« Route.Address »,

Route.Forwarding : représente un drapeau indiquant si cette route peut être utilisée pour

expédier des paquets de données,

Route.Broken : représente un drapeau indiquant si cette route est rompue. Ce drapeau est

activé si le prochain saut devient inaccessible ou bien suite à un traitement d’un RERR.

Le champ suivant est optionnel :

Route.Dist : désigne une métrique qui indique le nombre de saut parcouru avant d’atteindre le

nœud « Route.Adress ».


62

Des durées de vie sont associées aux informations de routage. Les routes étant non

utilisées expirent après une certaine période de temps et sont supprimées de la table de

routage.

III.2.4.2. Evaluation de la validité des informations de routage

Etant donné une entrée de la table de routage (Route.SeqNum, Route.Dist, et

Route.Broken) et un nouveau MR (Node.SeqNum, Node.Dist, et le type du message

RREQ/RREP) arrivant d’un nœud particulier, les nouvelles informations de routage sont

classifiées comme suit [64] :

1. Anciennes

Si Node.SeqNum – Route.SeqNum < 0, l’information de ce MR est ancienne.

L’utilisation d’anciennes informations de routage n’est pas autorisée car ceci peut entrainer la

génération de boucles de routage.

2. Possibilité de boucle

Si Node.SeqNum == Route.SeqNum, l’utilisation de l’information incluse dans ce MR

peut entrainer des boucles ; dans ce cas d’autres informations doivent être prises en compte.

Si Route.Dist ou Node.Dist sont nulles ou inconnues ou bien Node.Dist > Route.Dist + 1,

donc l’information de routage peut générer des boucles.

3. Inférieures

Si les numéros de séquence sont égaux, l’information est inférieure dans plusieurs cas :

Cas 1 : Si Node.Dist == Route.Dist + 1 (la distance de la route est supérieure) et

Route.Broken == false ;

Cas 2 : Si Node.Dist == Route.Dist (distances de route égales), Route.Broken == false et ce

MR est un RREQ. Les conditions d’infériorité empêchent l’envoi de RREQ avec des distances

équivalentes.

4. Supérieures

Toute nouvelle information de routage qui ne correspond à aucune des contraintes

précédentes est sans boucle et meilleure que l’information qui existe déjà dans la table de

routage. Une information est toujours supérieure si Node.SeqNum - Route.SeqNum > 0.

Dans le cas où les numéros de séquence sont égaux, l’information est supérieure dans

les cas suivants :

Cas 1 : Si Node.Dist < Route.Dist.

Cas 2 : Si Node.Dist == Route.Dist + 1 et Route.Broken == true (une route brisée est

détectée).


63

Cas 3 : Si Node.Dist == Route.Dist et qu’il s’agit d’un RREP (les RREP avec la même

distance sont expédiés) ou Route.Broken == true.

III.2.5. La phase de découverte de route

Le mécanisme de découverte de route est le processus qui permet d’établir une route

vers une nouvelle destination à la demande du nœud source. Nous verrons dans cette partie le

détail de cette procédure ainsi que le rôle joué par chacun des nœuds du réseau (source, nœuds

intermédiaires, destination).

III.2.5.1. Le rôle du nœud source

Un nœud source souhaitant communiquer avec un nœud destinataire doit d’abord

consulter sa table de routage. S’il ne trouve pas localement toutes les informations sur la route

à suivre ; il diffusera un message de demande de route RREQ aux nœuds voisins.

Avant d’envoyer un message RREQ, le nœud source doit d’abord incrémenter son

propre numéro de séquence par «1» afin d’éviter la génération de boucles de routage.

La première adresse ajoutée dans le paquet RREQ correspond à l’adresse IP de la

destination pour laquelle il n’existe pas de route ; si une valeur antérieure de son numéro de

séquence est connue, donc elle doit être incluse également.

Ensuite, le nœud ajoute son adresse et son propre numéro de séquence au MR. Cette

information sera utilisée par les autres nœuds pour créer une route vers le nœud source, afin

de délivrer par la suite un RREP et de l’utiliser éventuellement pour l’envoi de leurs propres

paquets de données.

Le nombre de saut maximal recevra la valeur du « MSG_HOPLIMIT » qui est égale à

10 sauts. Ce champ permet de limiter la propagation de RREQ afin de réduire le nombre de

diffusions.

Après la génération d’un RREQ, le nœud source déclenche un compteur

« RREQ_WAIT_TIME » en attendant une réponse. Si à l’expiration dudit compteur aucun

message RREP n’est reçu, la source peut tenter de retransmettre un message RREQ.

Si après un nombre maximum « RREQ_TRIES » tentatives d’établissement de route, il

n’y a aucune réponse alors le processus est abandonné et tous les paquets de données destinés

pour le nœud cible seront supprimés.


64

III.2.5.2. Le rôle d’un nœud intermédiaire

Lorsqu’un nœud intermédiaire reçoit un MR, il doit d’abord vérifier si l’adresse du

nœud source correspond à son adresse auquel cas le message sera supprimé.

Après consultation de la table de routage, si aucune entrée n’existe au préalable vers le

nœud source, alors les nouvelles informations de routage sont considérées comme étant

« fraîches » et une nouvelle entrée dans la table de routage est créée. S’il existe déjà une

entrée alors, elle sera évaluée par rapport aux nouvelles informations de routage du MR en

suivant la procédure décrite dans la section III.2.4.2 (pp. 62). Si les informations du message

sont considérées supérieures, l’entrée de la table de routage sera mise à jour.

Si les informations de routage du nœud source ne sont pas supérieures alors le paquet

doit être supprimé et aucun traitement ne sera effectué.

Sinon, la valeur du nombre de saut sera incrémentée pour chaque adresse incluse dans le

message (excepté celle du nœud cible).

Ensuite, chaque adresse accumulée dans le MR doit être prise en compte pour créer ou

mettre à jour les entrées de la table de routage. Ceci, afin d’éviter la génération d’avantage de

RREQ vers ces destinations dans le cas où il existe des paquets de données à expédier à cet

instant ou dans un futur proche.

Si les informations de routage d’un nœud additionnel ne sont pas supérieures, donc elles

seront enlevées du paquet, pour qu’elles ne soient pas propagées dans le réseau.

Après le traitement d’un MR, un nœud peut ajouter ses propres informations de routage

additionnelles.

Enfin, le nombre de saut maximal « MsgHdr.HopLimit » est décrémenté de «1». Si

« MsgHdr.HopLimit » du Message est supérieur ou égale à «1» et qu’il s’agit d’un message

RREQ alors le message courant doit être diffusé aux autres nœuds voisins. S’il s’agit d’un

message RREP alors le MR est envoyé vers le nœud du prochain saut afin d’atteindre le

destinataire du RREP. S’il n’existe pas de route vers le destinataire alors un RERR doit être

envoyé au nœud originaire du RREP.

III.2.5.3. Le rôle du nœud destinataire

Si le nœud courant correspond au nœud destinataire, ce dernier doit mettre à jour sa

table de routage par rapport aux nouvelles informations de routage appartenant au MR

comme ça été décrit dans la section précédente.

S’il s’agit d’un message RREQ, donc le nœud destinataire doit répondre par un RREP

au nœud originaire du RREQ.


65

Tout d’abord, l’adresse d’origine ainsi que l’adresse cible du RREQ sont incluses dans

le paquet RREP.

Lorsque le destinataire crée un RREP, celui-ci doit incrémenter son propre numéro de

séquence « OwnseqNum » par «1» dans les cas suivants avant de l’ajouter au MR :

TargetNode.SeqNum – OwnSeqNum > 0

Ou bien TargetNode.SeqNum == OwnSeqNum et TargetNode.AddTLV.Dist (la

dernière valeur connue du nombre de saut) < OrigNode.AddTLV.Dist (le nombre

de saut traversés par ce RREQ pour atteindre le nœud destinataire)

Enfin, l’adresse IP de la destination du RREP recevra la valeur de l’adresse IP du

prochain saut de la route vers le destinataire du RREP.

S’il s’agit d’un message RREP, alors le nœud destinataire peut commencer à utiliser la

nouvelle route établie pour envoyer les paquets de données en attente dans son buffer.

III.2.5.4. Exemple d’une procédure de découverte de route

Figure III.4: Le processus de découverte de route avec DYMO [67].

2

3

1

4

7

6

58

9

RREQN. source: 2N. cible: 9

RREQN. source: 2N. cible: 9N. intermédiaire: 4

RREQN. source: 2N. cible: 9N. intermédiaire: 4N. intermédiaire:6

RREPN. source: 9N. cible: 2N. intermédiaire: 6N. intermédiaire: 4

RREPN. source: 9N. cible: 2N. intermédiaire: 6

RREPN. source: 9N. cible: 2

RREP

RREQ

Lien réseau


66

La figure III.4 illustre la procédure de découverte de route à travers un exemple simple.

Le nœud 2 (nœud source) désire communiquer avec le nœud 9 (nœud destinataire) donc

il diffuse un message RREQ dans le réseau.

Lorsque le nœud 2 entame la découverte de route, le RREQ contient initialement

l’adresse du nœud d’origine et du destinataire.

Quand le nœud 4 reçoit le RREQ, celui-ci installe une route vers le nœud 2 et ajoute sa

propre adresse au RREQ.

Un traitement identique est réalisé au niveau du nœud 6 qui installe une route vers le

nœud 2 avec un nombre de saut égale à 2 et le nœud 4 comme nœud du prochain saut.

Une fois que le message RREQ atteint le nœud 9, celui-ci contiendra 4 adresses et aura

traversé 3 sauts. Le nœud 9 traite le RREQ et met à jour sa table de routage en utilisant les

informations accumulées, et comme c’est le destinataire du RREQ, donc il crée de plus un

RREP comme réponse. Ce RREP est envoyé à travers la route inverse en unicast.

D’une manière similaire à la diffusion d’un RREQ, chaque nœud faisant suivre le RREP

y ajoute sa propre adresse et installe des routes aussi vers le nœud 9 et pour chaque adresse

contenue dans le message.

III.2.6. La phase de maintenance de route

La phase de maintenance de route est le deuxième mécanisme caractéristique des

protocoles de routage réactifs. Son objectif est de définir les actions à mener par les nœuds

pour garantir la connectivité locale et pour propager des annonces de rupture de liens aux

autres nœuds. Dans cette section, nous présentons le détail des opérations effectuées dans le

cadre de cette procédure.

III.2.6.1. La gestion des liens actifs

La rupture d’un lien dans le réseau peut être détectée par l’un des différents mécanismes

suivants :

Accusés de réception de la couche MAC (Link layer feedback),

La découverte du voisinage (Neighborhood discovery) [68],

La durée de vie de la route.

Lorsque qu’on détermine qu’un lien est brisé ou que le prochain saut est inaccessible, le

nœud courant doit enlever les routes à suivre affectées par cette rupture (celles avec un « Next

hop » inaccessible) et désactiver le flag « Route.Forwarding ».


67

III.2.6.2. La génération d’un RERR

Un RERR doit être généré immédiatement après la détection d’une rupture de lien d’une

route afin de notifier rapidement les autres nœuds qu’une route vers une certaine destination

n’est plus disponible [69].

A la création d’un nouveau RERR, l’adresse du premier nœud inaccessible (l’adresse IP

du paquet de données ou du paquet RREP) est insérée dans le bloc d’adresses

« AddBlk.UnreachableNode.Address ». Si le numéro de séquence de ce nœud inaccessible est

connu, il doit être inclus également dans le RERR. Les autres nœuds additionnels

inaccessibles qui dépendent du lien indisponible (les routes avec le même

« Route.NextHopAddress » et « Route.NextHopInterface ») doivent être ajoutés au RERR

comme entrées additionnelles. L’ajout d’information sur les nœuds inaccessibles notifie

chaque nœud qui traite le message de l’indisponibilité des routes additionnelles.

Le RERR est diffusé ensuite à l’ensemble des voisins. Cet envoi permettra de notifier

tous les nœuds à proximité qui peuvent dépendre du lien brisé actuel.

III.2.6.3. Le traitement d’un RERR

Lorsqu’un nœud reçoit un message RERR, il doit invalider les entrées de sa table de

routage concernées par chaque adresse inaccessible trouvée dans le message et qui répond aux

conditions suivantes :

1. L’adresse du prochain saut « Route.NextHopAddress » est la même que l’adresse

présente dans le RERR.

2. L’interface du prochain saut « Route.NextHopInterface » est la même que l’interface à

partir de laquelle le RERR a été reçu.

3. Le numéro de séquence de la route « Route.SeqNum » ou le numéro de séquence

présent dans le RERR « UnreachableNode.SeqNum » sont nuls «0» ou inconnus, ou

bien Route.SeqNum – UnreachableNode.SeqNum 0.

Lors du traitement, si « Route.SeqNum » est nul «0» ou inconnu et

« UnreachableNode.SeqNum » existe dans le RERR, alors « Route.SeqNum » peut recevoir la

valeur du « UnreachableNode.SeqNum ». Ceci permet d’éviter un traitement futur du RERR.

Si « Route.SeqNum » est connu et « UnreachableNode.SeqNum » n’est pas inclus dans le

RERR, alors « Route.SeqNum » peut être ajouté au RERR.


68

Ensuite, le nombre de saut maximal « MsgHdr.HopLimit » est décrémenté de «1». Si la

nouvelle valeur de ce dernier est supérieure à «1» et qu’il reste au moins un nœud inaccessible

dans le RERR, alors le RERR mis à jour doit être expédié vers le nœud du prochain saut.

Si le message RERR est reçu par le nœud source et il reste toujours des paquets de

données à envoyer, celui-ci peut initier une nouvelle procédure de découverte de route.

III.2.6.4. Exemple de dissémination d’un RERR

Le processus de dissémination d’un message RERR est illustré sur la figure III.5. Un

lien entre le nœud 6 et le nœud 9 se brise alors que le nœud 6 reçoit un paquet de données

pour le nœud 9. Et par conséquent, Le nœud 6 génère un message RERR qui sera propagé en

arrière vers le nœud 2. Seuls les nœuds possédant une entrée dans leur table de routage pour le

nœud 9 diffuseront à leur tour le message RERR. Sur l’exemple illustré sur la figure III.5,

comme aucun des nœuds 5, 7 et 10 n’utilise le nœud 6 comme prochain saut vers le nœud 9,

donc ils vont tous supprimer le RERR après avoir traité le message.

Remarque : Lorsqu’on dit qu’un lien est brisé, ça pourrait être juste le lapse de temps d’une

entrée de la table de routage d’un nœud qui a expiré donc l’entrée est devenue invalide.

Figure III.5: Génération et diffusion d’un message RERR [70].

2

1

3

4

7

6

5 8

9

10

RERR

Données

Lien réseau


69

III.3. Présentation du protocole de routage DYMO_MQ

Dans le reste de ce chapitre nous présentons notre contribution pour le protocole

DYMO . Notre objectif est d’apporter d’abord des modifications au protocole DYMO d’origine

de telle sorte à le rendre multi-chemins et d’ajouter ensuite des métriques de QoS afin qu’il

soit encore plus performant et mieux adapté aux contraintes des RCSF.

Nous avons appliqué pratiquement les mêmes techniques de routage multi-chemins

présentées dans le chapitre précédent sur le protocole DYMO en prenant en considération que

des chemins à nœuds disjoints qui seront exploités par la suite d’une manière alternative pour

la tolérance aux pannes.

Afin d’établir plusieurs routes à nœuds disjoints entre le nœud source et le nœud

destinataire lors d’une seule procédure de découverte de route, nous avons ajouté des

extensions à DYMO pour permettre la génération de plusieurs RREP.

L’accumulation des chemins qui existe déjà dans ce protocole a été exploitée dans le but

de décider de la disjonction des routes empruntées pour la transmission des données.

Des métriques de QoS ont été ajoutées aussi dans le paquet RREQ de la même manière

qu’avec AODV en vue de limiter le nombre de diffusions et de choisir aussi des chemins

optimales.

Dans la deuxième partie de ce chapitre, nous allons d’abord donner le nouveau format

du message de routage de type RREQ utilisé par le protocole DYMO_MQ ainsi que la

nouvelle structure de la table de routage étendue. La procédure de découverte de route par ce

protocole sera expliquée en détail par la suite à travers des organigrammes.

III.3.1. Les extensions apportées aux MR et à la table de routage

III.3.1.1. Le nouveau format du message RREQ

Comme la technique d’accumulation des chemins existe déjà dans DYMO, donc le

format d’un MR de type RREP n’a pas été modifié. Nous avons apporté des extensions

seulement pour les MR de type RREQ.

Le nouveau format du message RREQ de DYMO_MQ est illustré sur la figure III.6

suivante :


70

IP header UDP header MessageHeader

Message TLV Addr headerTarget node

Addr TLVTarget node

Addr headerOriginal node

Addr TLVOriginal

node

Addr headerAdditional

node

Addr TLVAdditional node

T_délai T_erreur

Figure III.6: Le nouveau format d’un message de routage de type RREQ.

Ce format de message RREQ représente une structure simplifiée des différents champs

qui peuvent être inclus dans un paquet RREQ. Ce dernier, contient les mêmes informations de

routage que celui de DYMO (voir sections III.2.3.1 et III.2.3.2 (pp. 56)) plus deux champs

supplémentaires pour assurer des contraintes de délai et de taux d’erreur :

T_délai : indique le délai nécessaire pour transmettre des données de la source à la

destination,

T_erreur : contient la valeur du taux d’erreur du chemin jusqu’au nœud courant.

Ces deux champs sont expliqués en détail dans le chapitre précédent (voir section II.3.2

(pp.43)).

III.3.1.2. Le nouveau format de la table de routage

Dans DYMO, la table de routage ne sauvegarde qu’une seule route pour chaque

destination, donc nous avons changé la procédure de mise à jour des routes de telle sorte à

avoir une entrée pour chaque chemin à nœud disjoint trouvé lors de la procédure de

découverte de routes.

Le nouveau format de la table de routage est illustré sur la figure III.7 suivante :

Route.

Address

Route.

Prefix

Route.

SeqNum

Route.

NextHopAddress1

Route.

Forwarding1

Route.

Broken1

Route.

Dist1

Route.

Address

Route.

Prefix

Route.

SeqNum

Route.

NextHopAddress2

Route.

Forwarding2

Route.

Broken2

Route.

Dist2

Route.

Address

Route.

Prefix

Route.

SeqNum

Route.

NextHopAddress3

Route.

Forwarding3

Route.

Broken3

Route.

Dist3

Figure III.7 : La structure étendue de la table de routage.

Dans la nouvelle structure de la table de routage de DYMO_MQ, nous avons plusieurs

entrées sauvegardées pour une même destination. Cependant le nombre de champs reste le


71

même pour chaque entrée (chaque champ est expliqué en détail dans la section III.2.4.1 (pp.

61)).

Comme nous l’avons déjà fait avec AODV_MQ, nous avons limité également pour

DYMO_MQ le nombre d’entrées pour chaque destination à trois afin d’économiser de

l’espace mémoire.

III.3.2. La découverte de routes multiples disjointes

La procédure de génération d’un message RREQ par un nœud source dans DYMO_MQ

est similaire à celle de DYMO (expliquée dans la section III.2.5.1 (pp. 63)).

Si un nœud désire envoyer des paquets de données à une certaine destination. Ce dernier

génère une requête de route (RREQ), dans le cas où aucune entrée vers cette destination n’est

disponible dans sa table de routage pour les raisons suivantes :

la destination n’est pas connue au préalable, ou

tous les chemins existants vers cette destination ont expiré leur durée de vie ou sont

devenus défaillants.

Le MR de type RREQ sera diffusé ensuite aux nœuds voisins afin de découvrir de

multiples routes qui mènent vers la destination.

III.3.2.1. Traitement d’un MR par un nœud intermédiaire

La différence entre DYMO et DYMO_MQ se situe dans le traitement des MR. Les deux

types de MR (RREQ et RREP) possèdent exactement les mêmes informations de routage et

des fonctions en commun.

A la réception d’un MR, le nœud courant doit d’abord vérifier s’il est lui-même

l’expéditeur de ce MR auquel cas le message sera ignoré. S’il s’agit du destinataire du MR

alors la procédure de sélection des chemins disjoints est déclenchée (voir section III.3.2.2 (pp.

74).

Si le type du MR est un RREQ, lors de la diffusion du message, chaque nœud

intermédiaire met à jour la valeur du délai et du taux d’erreur comme ça été expliqué dans le

chapitre précédent (section II.3.2 (pp. 43)). Si les contraintes de QoS ne sont pas vérifiées ((le

délai < 0) et (le taux d’erreur > un seuil)) donc le paquet RREQ sera supprimé.

Quelque soit le type du MR (RREQ ou RREP), chaque nœud doit mettre à jour sa table

de routage en utilisant les informations de routage accumulées dans le MR en suivant la

procédure décrite dans la section III.2.4.2 (pp. 62) mais avec la modification de la condition

d’infériorité.


72

Afin de permettre l’établissement de multiples routes entre le nœud source et le nœud

destinataire nous avons enlevé la condition d’infériorité exprimée dans la section III.2.4.2

(pp.62) pour le nœud source et le nœud destinataire, car cette condition empêche la prise en

considération de routes supplémentaires s’il existe déjà une route valide au préalable dans la

table de routage.

La contrainte d’infériorité a été modifiée de la manière suivante :

Si les numéros de séquence sont égaux, l’information de routage est inférieure si le nœud

courant est différent du nœud destinataire et l’une des deux conditions suivantes est vérifiée :

Cas 1 : si Node.Dist == Route.Dist + 1 (la distance de la route est supérieure)

et Route.Broken == false ;

Cas 2 : si Node.Dist == Route.Dist (distances de route égales) et Route.Broken

== false et ce MR est un RREQ.

Après le traitement d’un MR, si les informations de routage ne sont pas supérieures

donc ce MR sera supprimé. Sinon, le nœud courant va mettre à jour sa table de routage,

ajouter ses propres informations de routage et diffuser ensuite le MR à tous ses voisins, s’il

s’agit d’un message RREQ ou bien expédier le MR en unicast au nœud du prochain saut si le

MR est de type RREP.

La procédure de traitement d’un MR par un nœud intermédiaire est illustrée par

l’organigramme de la figure III.8.


73

Non

Non

Non

Non Oui

Oui

Oui

Oui

Figure III.8 : Organigramme de traitement d’un MR par un nœud intermédiaire.

Début

Recevoir un MR

Lire l’adresse source du MR

L’adresse destination du MR= L’adresse du nœud ?

Lire l’adresse destination du MR

L’adresse source du MR =L’adresse du nœud ?

Mettre à jour la valeur du T_erreur

Mettre à jour la valeur du T_délai

T_délai > etT_erreur < seuil ?

Détruire le MR

Mettre à jour la table de routage par rapportà tous les nœuds accumulés

Ajouter l’adresse du nœud et les informationsde routage associées au RREQ

Diffuser le paquet RREQ auxvoisins du nœud

Fin

Procédure desélection des

chemins disjoints

Mettre à jour la table de routage parrapport à tous les nœuds accumulés

Ajouter l’adresse du nœud et lesinformations de routage associées au

RREP

Envoyer le paquet RREP vers leprochain saut

Consulter le champ du type du MR

Le MR est un RREQ ?


74

III.3.2.2. Traitement d’un MR par un nœud destinataire

Afin d’assurer une indépendance entre les différentes routes, DYMO_MQ utilise des

routes disjointes pour la transmission des données entre une source et une destination.

La sélection des chemins à nœuds disjoints se fait d’une manière centralisée au niveau

du nœud destinataire du MR pour les raisons suivantes :

Limiter la propagation de paquets RREP s’il s’agit du nœud destinataire du RREQ.

Refaire le test au niveau du nœud destinataire du RREP pour assurer une

disjonction complète des chemins empruntés.

A la réception d’un MR par un nœud destinataire, s’il s’agit du premier message alors, il

doit le sauvegarder dans son cache. Sinon, il doit comparer la liste des nœuds accumulés dans

le message avec chaque chemin à nœud disjoint déjà enregistré dans son cache. S’il n’existe

aucun nœud en commun donc le nouveau chemin sera sauvegardé. Sinon le MR sera

supprimé.

Si le MR est de type RREQ et qu’il vérifie la condition de disjonction, alors le nœud

destinataire doit mettre à jour sa table de routage par rapport à tous les champs de ce MR,

incrémenter son numéro de séquence, générer un message RREP et l’envoyer ensuite au nœud

du prochain saut à partir duquel le RREQ a été reçu.

Si le MR est de type RREP, il s’agit alors du nœud source qui a initié la requête de

découverte de routes. Celui-ci doit vérifier si le nombre d’entrées dans sa table de routage est

inférieur à trois. Si c’est le cas donc le RREP sera accepté, l’entrée correspondante vers la

destination sera mise à jour et enfin les paquets de données en attente de route peuvent être

envoyés à leur destination.

La procédure de traitement d’un MR par un nœud destinataire est exprimée à travers

l’organigramme de la figure III.9.


75

Non

Oui

Oui

Oui Non

Non

Oui

Non

Oui

Figure III.9 : Organigramme de traitement d’un MR par un nœud destinataire.

III.3.3. La maintenance de routes

La maintenance de routes dans DYMO_MQ se fait de la même manière qu’avec

DYMO , la différence se situe juste au niveau du nœud source, celui-ci doit d’abord invalider

la route utilisée actuellement vers cette destination et choisir ensuite une route alternative si

celle-ci est disponible dans la table de routage. Sinon, initier une nouvelle procédure de

Début

Lire le N°seq du MR

N°seq du MR > N°seq ducache ?

N°seq du MR = N°seq ducache ?

N°seq du cache = N°seq du MR

Sauvegarder le chemin dans le cache

Le chemin accumulé est disjointavec le reste des chemins

sauvegardés dans le cache ?

Détruire le MR

Incrémenter le numéro de séquence

Générer un paquet RREP

Envoyer le paquet RREP aunœud à partir duquel le RREQ a

été reçu

Fin

Consulter le champ du type du MR

Le MR est un RREQ ?

Vérifier le nombre de routesexistantes dans la table de routage


Envoyer les paquets de données

Nombre de routes < 3 ?


Non


76

découverte de routes si toutes les routes sauvegardées dans la table de routage ont expiré ou

sont devenues défaillantes.

III.4. Conclusion

Dans ce chapitre, nous avons présenté en détails toutes les fonctionnalités du nouveau

protocole de routage DYMO qui se base également comme le protocole AODV sur la

découverte et la maintenance de route. Cependant DYMO diffère par rapport à AODV sur les

points suivants :

DYMO est prévu pour être en partie extensible, ce qui explique l’optionalité de

certaines opérations.

DYMO bénéficie d’une structure générique de messages de routage ce qui permet de

réduire le temps de traitement des messages reçus au niveau des nœuds.

Dans le protocole DYMO, uniquement la cible d’une requête RREQ peut répondre à

celle-ci.

La liste des nœuds parcourus par les paquets RREQ et RREP peut être incluse dans les

messages, comme c’est le cas pour DSR. Cette information peut être utilisée afin de

connaître de manière partielle la topologie du réseau, et donc de disposer gratuitement

de certaines routes comme dans un routage proactif, mais sans souffrir de l’impact des

messages périodiques qu’un routage proactif peut connaître.

Enfin, le protocole DYMO à la capacité de gérer les groupes de nœuds dont l’adresse

IP comporte un préfixe commun.

Vue l’importance du routage multi-chemins pour les RCSF, nous avons apporté des

améliorations au protocole de routage DYMO de telle sorte à le rendre multi-chemins en

ajoutant aussi des métriques de QoS. Ceci, afin de réduire le nombre de messages de contrôle

dans le réseau et augmenter la robustesse et la disponibilité des routes.

Dans le prochain chapitre, nous allons décrire les différentes expérimentations réalisées

avec les protocoles AODV et DYMO ainsi que leur version multi-chemins (avec/sans QoS)

afin d’effectuer une comparaison de performance entre les protocoles de routage étudiés et de

prouver l’intérêt de l’utilisation de l’approche du routage multi-chemins pour les RCSF.

Chapitre IV. Implémentation et évaluation des performances

77

Chapitre IV

Implémentation et évaluation desperformances

IV.1. Introduction

L’objectif de notre travail consiste à étudier l’impact de l’approche multi-chemins

avec/sans QoS sur les protocoles de routage réactifs (AODV et DYMO) dans une perspective

de tolérance aux pannes dans les RCSF où le changement de topologie est relativement

fréquent.

Dans ce dernier chapitre nous allons d’abord décrire l’implémentation du nouveau

protocole DYMO et présenter ensuite l’environnement et les paramètres de nos simulations.

Nous procéderons ensuite à une comparaison entre les résultats des différentes

simulations réalisées avec les protocoles de routage à chemin unique ainsi que leur version

multi-chemins avec/sans QoS.

Enfin, nous présenterons les résultats obtenus en prenant en considération le facteur

d’interférence sur la découverte de chemins multiples.

IV.2. Implémentation du protocole de routage DYMO

Comme le protocole AODV (écrit en langage C++) existe déjà sous NS2 [71] donc nous

avons pu accéder directement au code source afin d’apporter des modifications pour le rendre

multi-chemins et ajouter ensuite des contraintes de QoS. Cependant, le protocole DYMO (écrit

en C et en C++), n’est pas intégré sous NS2.

Les différentes implémentations qui existent sur DYMO sont les suivantes :

DYMOUM, programmée par Fransisco J. Ros à l’université de Murcia. Elle fonctionne

sous le système linux et NS2 [72].

NIST-DYMO, programmée par Luke Klien-Bernt, développée à l’institut NIST (National

Institute of Standards and Technology) et qui fonctionne sous linux (sous plusieurs

versions de noyaux 2.4 et 2.6) [73].


78

DYMO for OPNET, une ancienne implémentation de DYMO pour OPNET , développée

par Koojana Kuladintihi et Carmelita Gorg à l’université de Brême [74].

EK-DYMO, par Kyungpook à l’université ETRI de la Corée [75].

DYMO-AU, implémentée par Rolf E. Thorup sous le système linux [76].

TYMO, par Romain Thouvenin, implémentation de DYMO sous TinyOS 2.0 [77].

DYMO for OMNeT++, par Christoph Sommer [78].

Pour notre projet nous avons choisi l’implémentation de la version 0.3 de DYMOUM

(correspondante au draft de la version 5 de DYMO) qui a déjà été testée avec des scénarios

réels et qui fonctionne très bien sous NS2. Nous avons téléchargé cette version à partir de leur

site officiel [72] et installé ensuite sous NS2 (version 2.29) (Voir Annexe C). Après avoir bien

étudié le code source nous avons apporté les extensions nécessaires dessus afin de rendre ce

protocole multi-chemins avec QoS.

Le diagramme de classe illustré sur la figure IV.1, représente les composants de base de

DYMOUM.

DYMOUM contient un message générique appelé « DYMO_element » qui effectue le

traitement approprié à chaque type de paquet reçu dans le réseau.

« rt_entry » représente la table de routage qui contient des informations sur le routage

comme l’adresse de destination, l’adresse du prochain saut, le nombre de saut, le numéro

de séquence, etc.

« UERR » représente un message d’erreur non-identifié.

« RERR » représente un message d’erreur qui contient toutes les adresses des nœuds

inaccessibles et qui sont stockées dans le bloc d’adresses « RERR_block ».

« Hello » représente un message utilisé pour la découverte des voisins.

L’élément de routage (Routing Element) « RE » est la partie principale où nous avons

apporté nos modifications, qui assure le traitement des messages RREQ et RREP utilisés

pour envoyer des informations de routage d’un nœud à un autre. Lorsqu’un nœud reçoit ce

type de message, il peut ajouter ses propres informations de routage dans le bloc

« RE_block ».


79

11

**

Figure IV.1 : DYMOUM : l’implémentation de DYMO.

Les paramètres de configuration du code source DYMOUM sont illustrés sur le tableau

suivant :

Nom Valeur

MSG_HOPLIMIT

ROUTE_TIMEOUT

ROUTE_AGE_MIN_TIMEOUT

ROUTE_SEQNUM_AGE_MAX_TIMEOUT

ROUTE_USED_TIMEOUT

ROUTE_DELETE_TIMEOUT

ROUTE_RREQ_WAIT_TIME

RREQ_TRIES

UNICAST_MESSAGE_SENT_TIMEOUT

10 sauts

5 secondes

1 seconde

60 secondes

ROUTE_TIMEOUT

5* ROUTE_TIMEOUT

2 secondes

3 fois

1 seconde

Tableau IV.1 : Les paramètres de configuration de DYMOUM [73].

DYMOUM

DYMO_element rt_entry

UERR RERR RE Hello

RERR_block RE_block


80

IV.3. Principales extensions apportées au protocole de routage DYMO

IV.3.1. L’établissement de routes multiples

Afin de permettre la génération de multiples chemins à nœuds disjoints, il faut tout

d’abord changer les conditions de mise à jour des entrées de la table de routage pour ne pas

supprimer tous les MR dupliqués et sauvegarder aussi plusieurs chemins alternatives vers la

même destination.

Dans la procédure illustrée sur la figure IV.2, nous avons changé la condition

d’infériorité (expliquée dans la section III.3.2.1 (pp. 71)) afin de pouvoir effectuer le

traitement d’autres MR même dans le cas où il existe déjà une route valide dans la table de

routage.

NS_STATIC NS_INLINE int re_info_type(RE *re, struct re_block *b, rtable_entry_t *e, u_int8_t is_rreq){

u_int32_t node_seqnum;int32_t sub;int i;assert(b);u_int32_t ifindex;// If the block was issued from one interface of the processing node,// then the block is considered stalefor (i = 0; i < DYMO_MAX_NR_INTERFACES; i++){

if (this_host.devs[i].enabled &&this_host.devs[i].ipaddr.s_addr == b->re_node_addr)

{return RB_SELF_GEN;

}}if (e){

node_seqnum = ntohl(b->re_node_seqnum);sub = ((int32_t) node_seqnum) - ((int32_t) e->rt_seqnum);if (sub < 0)

return RB_STALE;if (sub == 0 ){

if (e->rt_hopcnt == 0 || b->re_hopcnt == 0 || b->re_hopcnt > e->rt_hopcnt + 1)return RB_LOOP_PRONE;

if (e->rt_state == RT_VALID && (b->re_hopcnt > e->rt_hopcnt || (b->re_hopcnt == e->rt_hopcnt &&is_rreq))&& (re->target_addr != (u_int32_t) DEV_IFINDEX(ifindex).ipaddr.s_addr))

return RB_INFERIOR;}

}return RB_FRESH;

}

Figure IV.2 : Procédure modifiée pour l’établissement de routes multiples, extraite de la

classe « dymo_re.h ».


81

L’objectif du premier test inséré dans la procédure de la figure IV.3 est de limiter le

nombre de chemins stockés dans la table de routage à trois. Ensuite, nous avons modifié la

procédure de mise à jour afin de pouvoir sauvegarder dans la table de routage les routes

supplémentaires.

int NS_CLASS re_process_block(RE *re, struct re_block *block, u_int8_t is_rreq, rtable_entry_t *entry, structin_addr ip_src, u_int32_t ifindex){

struct in_addr dest_addr;u_int32_t seqnum;int rb_state;int route=0;rtable_entry_t *entry2;int cnt=0;

if (!block)return -1;

dest_addr.s_addr = block->re_node_addr;seqnum = ntohl(block->re_node_seqnum);

if((re->target_addr == (u_int32_t) DEV_IFINDEX(ifindex).ipaddr.s_addr)&& (!re->a)){cnt=rtable_count(dest_addr);if (cnt>2){

return -1;}}

// Increment block hop countblock->re_hopcnt++;rb_state = re_info_type(re, block, entry, is_rreq);if (rb_state != RB_FRESH){

dlog(LOG_DEBUG, 0, __FUNCTION__, "ignoring a %s RE block", (rb_state == RB_STALE ? "stale" :(rb_state == RB_LOOP_PRONE ? "loop-prone" : (rb_state == RB_INFERIOR ? "inferior" :"self-generated"))));

return -1;}// Create/update a route towards RENodeAddress

if (!entry){entry=rtable_insert(

dest_addr, // destip_src, // nxt hopifindex, // ifaceseqnum, // seqnumblock->prefix, // prefixblock->re_hopcnt, // hop countblock->g); // is gw

route = 1;}

if (!route){entry2=rtable_insert(

dest_addr, // destip_src, // nxt hopifindex, // ifaceseqnum, // seqnumblock->prefix, // prefixblock->re_hopcnt, // hop countblock->g);

}


82

else rtable_update(entry, // routing table entrydest_addr, // destip_src, // nxt hopifindex, // ifaceseqnum, // seqnumblock->prefix, // prefixblock->re_hopcnt, // hop countblock->g); // is gw

return 0;}

Figure IV.3 : Procédure modifiée pour la sauvegarde de plusieurs entrées, extraite de la

classe « dymo_re.c ».

La procédure de la figure IV.4 a été ajoutée pour parcourir la table de routage dans le

but de calculer le nombre de routes valides dont nous avons fait appel dans la procédure

illustrée sur la figure IV.3. Ceci, afin de limiter le nombre de chemins stockés dans la table de

routage à trois.

int NS_CLASS rtable_count(struct in_addr dest_addr){

dlist_head_t *pos;int count=0;dlist_for_each(pos, &rtable.l){

rtable_entry_t *e = (rtable_entry_t *) pos;if ((e->rt_dest_addr.s_addr == dest_addr.s_addr)&& (e->rt_state == RT_VALID)){

count +=1 ;}

}return count;

}

Figure IV.4 : Procédure ajoutée pour le calcul du nombre de routes, extraite de la classe

« rtable.c ».

IV.3.2. La sélection des chemins à nœuds disjoints

Les procédures ajoutées au code source pour la sélection des chemins à nœuds disjoints

sont décrites ci-dessous.

Le test illustré sur la figure IV.5 a été ajouté afin d’assurer une disjonction complète

entre les chemins empruntés pour la transmission des données.

A la réception d’un MR, le nœud destinataire doit comparer tous les nœuds accumulés

dans le MR avec les nœuds de chaque chemin stocké dans le cache. S’il existe un nœud en


83

commun, donc ce MR sera supprimé. Sinon, le nouveau chemin sera sauvegardé dans le

cache.

if((re->target_addr == (u_int32_t) DEV_IFINDEX(ifindex).ipaddr.s_addr)){node_addr.s_addr=re->re_blocks[0].re_node_addr;struct in_addr node;u_int32_t seqnum;seqnum= htonl(re->target_seqnum);

for (i = 1; i < re_numblocks(re); i++){node.s_addr=re->re_blocks[i].re_node_addr;

if (disj_path_find(node_addr, seqnum,node)){dlog(LOG_DEBUG, 0, __FUNCTION__, "ignoring RM");schedule_next_event();return;}

}for (i = 1; i < re_numblocks(re); i++){node.s_addr=re->re_blocks[i].re_node_addr;disj_path_add(node_addr,seqnum, node);}

}

Figure IV.5 : Procédure ajoutée pour la sélection des chemins à nœuds disjoints, extraite de

la classe « dymo_re.c ».

La procédure illustrée sur la figure IV.6 a été ajoutée pour la sauvegarde des nœuds du

nouveau chemin accepté dans le cache dont on a fait appel dans la procédure présentée sur la

figure IV.5.

disj_path_t *NS_CLASS disj_path_add(struct in_addr src_addr, u_int32_t seqnum, struct in_addr node){

disj_path_t *entry;if ((entry = (disj_path_t *)malloc(sizeof(disj_path_t))) == NULL){

dlog(LOG_ERR, errno, __FUNCTION__, "failed malloc()");exit(EXIT_FAILURE);

}entry->src_addr.s_addr = src_addr.s_addr;entry->seqnum = seqnum;entry->node.s_addr = node.s_addr;dlist_add(&entry->list_head, &DISJ_PATH);return entry;

}

Figure IV.6 : Procédure ajoutée pour la sauvegarde des chemins disjoints dans le cache,

extraite de la classe « dymo_re.c ».

La procédure illustrée sur la figure IV.7 sert à vérifier s’il existe un nœud en commun

entre le nouveau chemin inclus dans le MR et ceux qui sont déjà sauvegardés dans le cache.


84

disj_path_t *NS_CLASS disj_path_find(struct in_addr src_addr, u_int32_t seqnum, struct in_addr node){

dlist_head_t *pos;dlist_for_each(pos, &DISJ_PATH){

disj_path_t *entry = (disj_path_t *) pos;if ((entry->src_addr.s_addr == src_addr.s_addr) && (entry->seqnum == seqnum) && (entry->node.s_addr ==node.s_addr))

return entry;}return NULL;

}

Figure IV.7 : Procédure ajoutée pour la vérification de la disjonction des chemins, extraite de

la classe « dymo_re.c ».

IV.3.3. L’intégration des contraintes de QoS

Pour vérifier des contraintes de QoS, nous avons ajouté deux champs dans le message

RREQ (expliqués dans le chapitre précédent (section III.3.1.1 (pp. 69))).

Le test illustré sur la figure IV.8 correspond à la mise à jour de la valeur du délai et celle

du taux d’erreur à la réception d’un MR de type RREQ au niveau d’un nœud intermédiaire. Si

l’une des deux conditions n’est pas vérifiée donc le MR sera ignoré.

double nb=0;if((re->target_addr != (u_int32_t) DEV_IFINDEX(ifindex).ipaddr.s_addr)&&(re->a)){re->delai=re->delai-NODE_TRAVERSAL_TIME;nb=pq_len;re->t_err = re->t_err*(ALPHA*(100/(MAX_QUEUE_LEN-nb)));if ((re->delai <= 0.0) || (re->t_err > 0.001)){dlog(LOG_DEBUG, 0, __FUNCTION__, "ignoring RREQ");schedule_next_event();

return;}}

Figure IV.8 : Test pour la vérification des contraintes de QoS, extrait de la classe

« dymo_re.c ».

IV.4. Extensions apportées pour le calcul du taux d’interférences dans

AODV_M

Afin de choisir au niveau du nœud source les chemins qui engendrent le minimum

d’interférences, nous avons utilisé l’équation donnée dans le deuxième chapitre (section II.3.4


85

(pp. 50)) pour calculer le taux d’interférences au niveau de chaque nœud intermédiaire

recevant un message RREP.

Sur la figure IV.9, nous présentons la mise à jour de la valeur du taux d’interférences au

niveau de chaque nœud intermédiaire recevant un message RREP. Le nœud source doit

comparer par la suite cette valeur avec le seuil de tolérance exigé par l’application. Si la

valeur du taux d’interférence est supérieure au seuil de tolérance donc le RREP sera supprimé.

void AODV::recvReply(Packet *p) {int cp;int nb=0;double var=0;if (ih->daddr() != index) {voisin *n= voisinhead.lh_first;

for( ; n; n = n->vlink.le_next) {for( cp=1;cp<rp->rp_hop_count2 ; cp++) {

if (rp->noeud2[cp]==n->node)nb=nb+1;

}}

var=(rp->rp_hop_count2)-1;rp->overhear=rp->overhear+(nb/var);}if (ih->daddr() == index) {

if (rp->overhear>=1){#ifdef DEBUGfprintf(stderr, "%s: ignoring RREP \n", __FUNCTION__);#endif // DEBUGdrop(p, "ignoring RREP");Packet::free(p);return;

}}

}

Figure IV.9 : Test pour le calcul du taux d’interférences, extrait de la classe « aodv.cc ».

IV.5. Environnement de simulation

Nos différentes expérimentations ont été réalisées à l’aide du simulateur NS2.29 sous le

système d’exploitation Ubuntu version 8.04.

IV.5.1. Présentation du simulateur NS2

NS2 (Network Simulator) est aujourd’hui l’outil de simulation de réseaux le plus

puissant et le plus utilisé par la communauté scientifique. Il s’agit d’un simulateur à

évènements discrets, fruit de la collaboration entre l’université de Berkley, USC (University of


86

Southern California) et Xerox PARC dans le cadre du projet VINT (Virtual Inter Network

Testbed). Ce projet est soutenu par DARPA (Defence Advanced Research Projects Agency).

Il est principalement bâti avec les idées de la conception par objets, de réutilisabilité du

code et de modularité. C’est un logiciel dans le domaine public disponible sur l’Internet. Son

utilisation est gratuite. Le logiciel est exécutable tant sous Unix que sous Windows.

Il permet à l’utilisateur de définir un réseau et de simuler des communications entre les

nœuds de ce réseau. NS2 utilise le langage OTcl (Object Tool Command Language) dérivé de

Tcl. A travers ce langage, l’utilisateur décrit les conditions de la simulation : la topologie du

réseau, les caractéristiques des liens physiques, les protocoles utilisés, etc.

La simulation doit d’abord être saisie sous forme de fichier texte. NS2 utilise en entrée

ce fichier et génère en sortie un fichier trace contenant les résultats. Ensuite, on utilise le

programme NAM (Network AniMator) pour interpréter ces données et fournir une

représentation graphique (pour plus de détail voir Annexe A).

IV.5.2. Paramètres de simulation

Dans le but de tester l’effet de la variation de la densité du réseau sur les différentes

métriques de performance étudiées, nous avons varié le nombre de nœuds capteurs dans le

réseau de 30 jusqu’à 120 nœuds avec une source de trafic et une vitesse de déplacement égale

à 5 m/s.

Nous avons estimé aussi l’impacte de la variation de la mobilité des nœuds sur les

performances du réseau en variant la vitesse de déplacement des nœuds de 5 jusqu’à 23 m/s

avec un fichier d’expérimentation de 90 nœuds.

Dans nos différentes expérimentations, nous avons simulé quatre ruptures de liens pour

chaque protocole. Ceci a été réalisé par le déplacement de quatre nœuds capteurs. Ces nœuds

sélectionnés appartiennent aux chemins empruntés pour la transmission des paquets de

données.

Enfin, nous avons évalué également l’impacte de l’interférence sur la découverte de

chemins multiples afin d’estimer le nombre de chemins trouvés. Nous avons effectué pour

cela des simulations sur trois fichiers d’expérimentation de 100, 200 et 400 nœuds en variant

le seuil de tolérance, avec une seule source de trafic et une vitesse de déplacement de 5 m/s.

Remarque : Notre travail se fonde sur une topologie Ad Hoc pour un RCSF avec comme

couche basse IEEE 802.11.


87

Les nœuds capteurs sont déployés dans un champ de taille 1500×1500 m2 sous la forme

d’une grille.

Le reste des paramètres de simulation est illustré sur le tableau IV.2 suivant :

Paramètre Valeur

Type du canal Canal sans fil « wireless channel »

Modèle de propagation radio Two ray ground

Couche MAC CSMA/CA IEEE 802.11

Taux de transfert des données 32 kb/s

Politique de gestion de la file d’attente DropTail

Taille du buffer des nœuds 50 paquets

Portée de transmission 250 m

Protocoles de routage AODV, AODV_M, AODV_MQ, DYMO, DYMO_M,

DYMO_MQ

Modèle de trafic UDP/CBR

Energie initiale 15 Joules

Temps de simulation 100 s

Tableau IV.2 : Les paramètres de simulation.

IV.5.3. Les métriques de performance

Les performances des protocoles de routage étudiés sont évaluées selon les trois

métriques suivantes :

Le nombre de messages de contrôle

Nous avons analysé le nombre de messages de contrôle afin de démontrer la

performance de notre approche en termes de réduction de paquets de contrôle dans le réseau

qui influe directement sur la durée de vie du réseau (ressource d’énergie) et de fiabilité du

réseau (encombrement du réseau).

Ce paramètre nous informe sur la quantité de paquets de contrôle générés par le

protocole en question pour la recherche, l’établissement et le maintien des routes. Il est

calculé de la manière suivante :

Le nombre de messages de contrôle = Σ(Paquets de contrôle) (IV.1)


88

Le délai moyen de bout en bout

Etant donné que certaines applications exigent un certain délai de transfert, il serait

intéressant de calculer ce paramètre qui concrétise la durée moyenne pour transmettre un

paquet de données de bout en bout [79].

Le délai moyen de bout en bout = 1000)(

))()((1

usPaquetsreç

iTiT SR

N

i

(ms) (IV.2)

Avec :

N : le nombre de paquets,

TR(i) : l’instant où le paquet de données i est reçu par l’agent de transport destination,

TS(i) : l’instant où le paquet de données i est émis par l’agent de transport source.

L’énergie totale consommée

Comme la capacité énergétique des nœuds capteurs doit être utilisée efficacement afin

de maximiser la durée de vie du réseau, donc le protocole de routage adopté doit assurer une

gestion optimale de cette ressource.

Sa valeur correspond à l’énergie totale consommée par chaque nœud du réseau. En

général, la consommation d’énergie est proportionnelle au nombre de paquets traités et au

type du traitement effectué (émission/réception). L’énergie totale consommée est calculée en

utilisant la formule suivante [80] :

L’énergie totale consommée =

N

iresiiniti ee

1,, )( (IV.3)

Avec :

N : le nombre de nœuds,initie , : l’énergie initiale,

resie , : l’énergie résiduelle.

IV.6. Résultats d’évaluation et interprétations

Dans ce qui suit, nous allons présenter nos différents résultats de performance obtenus à

l’aide du simulateur NS2.

Les différentes comparaisons entre les protocoles étudiés sont résumées à travers le

tableau IV.3.


89

Remarque : L’intersection des cases en couleur correspond à une comparaison réalisée avec

les protocoles de routage étudiés.

AODV AODV-M AODV-MQ DYMO DYMO-M DYMO-MQAODVAODV-M inutileAODV-MQDYMODYMO-MDYMO-MQ

Tableau IV.3 : Les différentes comparaisons pour l’évaluation.

1. En variant la densité du réseau, nous avons effectué différentes comparaisons de nos

protocoles de routage afin de valider l’approche multi-chemins avec/sans QoS de la manière

suivante (illustrées en vert sur le tableau IV.3) :

AODV avec AODV_M et AODV_MQ.

DYMO avec DYMO_M et DYMO_MQ.

2. Nous avons réalisé des comparaisons aussi entre AODV et DYMO ainsi que sur leur version

multi-chemins avec/sans QoS afin de bien distinguer la différence entre les deux protocoles de

routage (illustrées en bleu sur le tableau IV.3) :

AODV avec DYMO.

AODV_M avec DYMO_M.

AODV_MQ avec DYMO_MQ

3. En variant la vitesse de déplacement des nœuds, nous avons réalisé ces deux

comparaisons : (illustrées en gris sur le tableau IV.3)

AODV avec DYMO.

AODV_MQ avec DYMO_MQ.

4. En utilisant AODV_M, nous avons varié le seuil de tolérance au niveau du nœud source

afin d’évaluer le nombre de chemins trouvés lors d’une seule procédure de découverte de

routes qui provoquent le minimum d’interférence dans le réseau.

IV.6.1. Variation de la densité du réseau

IV.6.1.1. Comparaison entre AODV, AODV_M et AODV_MQ

A) Le nombre de messages de contrôle

A partir de la figure IV.10 (a), nous remarquons une évolution croissante du nombre de

messages de contrôle en fonction de la densité du réseau surtout pour le protocole AODV car


90

celui-ci effectue une nouvelle découverte de route à chaque rupture de liens, donc le nombre

de messages de contrôle est plus important. Par contre, à chaque découverte de routes les

protocoles AODV_M et AODV_MQ essayent de sauvegarder au moins un chemin alternatif

afin de l’utiliser ultérieurement en cas de panne, ce qui explique la diminution du nombre de

diffusions de messages de contrôle. Enfin, le protocole AODV_MQ est plus performant car le

trafic dans le réseau est encore moins important grâce aux conditions imposées par les

contraintes de délai et de taux d’erreur.

B) Le délai moyen de bout en bout

Comme on peut le distinguer à partir de la figure IV.10 (b), Le délai moyen de bout en

bout est quant à lui inférieur dans le cas des simulations réalisées avec AODV_M et

AODV_MQ, ce qui signifie que les paquets transmis sont arrivés plus rapidement à leur

destination. Ceci est expliqué par l’utilisation des chemins alternatifs qui diminue

considérablement le temps écoulé entre l’émission et la réception des paquets de données en

cas de panne, contrairement à AODV où il est nécessaire de lancer à chaque rupture de lien

une nouvelle procédure de découverte de route, ce qui influence négativement sur les

performances du réseau surtout en termes de fiabilité. Le protocole AODV_MQ offre un délai

plus optimal car les chemins empruntés sont plus courts grâce aux contraintes de délai et de

taux d’erreur ajoutées.

C) L’énergie totale consommée dans le réseau

A partir des résultats illustrés sur la figure IV.10 (c), on peut observer que le protocole

AODV consomme plus d’énergie dans le réseau car celui-ci sollicite plus de nœuds capteurs

pour le processus de découverte de routes à chaque rupture de lien, contrairement à AODV_M

et AODV_MQ où les nœuds économisent de l’énergie en utilisant les chemins alternatives

déjà présents dans leur table de routage.


91

30 40 50 60 70 80 90 100 110 1200

100

200

300

400

500

600

700

800

900

Densité du réseau

Nom

bre

de

mes

sage

sd

eco

ntr

ôle

AODVAODV-MAODV-MQ

(a) Le nombre de messages de contrôle.

30 40 50 60 70 80 90 100 110 1206

8

10

12

14

16

18

20

Densité du réseau

Dé

lai

moy

en

debo

uten

bou

t(m

s)

AODVAODV-M

AODV-MQ

(b) Le délai moyen de bout en bout.


92

30 40 50 60 70 80 90 100 110 120100

200

300

400

500

600

700

800

900

Densité du réseau

Ene

rgie

tota

lec

onso

mm

ée

(Jou

les)

AODVAODV-MAODV-MQ

(c) L’énergie totale consommée.

Figure IV.10 : Comparaison des performances entre AODV, AODV_M et AODV_MQ avec

la variation de la densité du réseau.

IV.6.1.2. Comparaison entre DYMO, DYMO_M et DYMO_MQ


Comme on peut le distinguer sur la figure IV.11 (a), le nombre de messages de contrôle

généré par les protocoles DYMO_M et DYMO_MQ est inférieur que celui produit par DYMO

car le nombre de découverte de routes est limité pour les protocoles multi-chemins grâce à

l’utilisation des routes alternatives en cas de rupture de liens. Le protocole DYMO_MQ est

encore plus performant avec l’utilisation des métriques de QoS puisqu’il y a plus de

conditions imposées lors du traitement des messages RREQ et par conséquent moins de

paquets de contrôle diffusés dans le réseau.


A partir de la figure IV.11 (b), on peut constater que le délai moyen de bout en bout

pour les protocoles DYMO_M et DYMO_MQ est meilleur que celui de DYMO car ce dernier

perd un temps considérable à chaque procédure de découverte de routes, ce qui n’est pas le

cas pour les protocoles multi-chemins qui gagnent du temps en exploitant directement un

chemin alternatif en cas de panne. Le délai de bout en bout est encore plus restreint en


93

utilisant le protocole DYMO_MQ car le nombre de nœuds intermédiaires diminue grâce à la

condition imposée par la contrainte de délai au niveau des messages RREQ.


Comme on peut le remarquer sur la figure IV.11 (c), DYMO_M et DYMO_MQ

économisent plus d’énergie par rapport à DYMO car le nombre de diffusion de RREQ diminue

considérablement en ajoutant la technique du routage multi-chemins.

En utilisant le protocole DYMO_MQ les chemins sélectionnés sont plus courts grâce à la

contrainte de délai et avec l’intégration de la contrainte du taux d’erreur, ces chemins

empruntent des routes dont les nœuds intermédiaires disposent d’une file d’attente moins

saturée, ce qui minimise la congestion dans le réseau et diminue par conséquent l’énergie

consommée au niveau de chaque nœud.

30 40 50 60 70 80 90 100 110 1200

200

400

600

800

1000

1200

Densité du réseau

Nom

bre

dem

essa

ges

deco

ntrô

le

DYMODYMO-MDYMO-MQ



94

30 40 50 60 70 80 90 100 110 1206

8

10

12

14

16

18

20

Densité du réseau

Dél

aim

oyen

deb

out

en

bou

t(m

s)

DYMODYMO-MDYMO-MQ


30 40 50 60 70 80 90 100 110 120100

200

300

400

500

600

700

800

Densité du réseau

En

ergi

eto

tale

cons

om

mé

e(J

oule

s)

DYMODYMO-MDYMO-MQ


Figure IV.11 : Comparaison des performances entre DYMO, DYMO_M et DYMO_MQ avec

la variation de la densité du réseau.

IV.6.1.3. Comparaison entre AODV et DYMO


Sur la figure IV.12 (a) on voit clairement que le nombre de messages de contrôle

augmente plus rapidement en utilisant DYMO, ceci est dû au nombre de diffusions


95

important de messages RREQ, car contrairement à AODV un nœud intermédiaire même s’il

possède une route vers la destination dans sa table de routage, ne peut pas répondre à un

RREQ (gratuitous RREP de AODV) et par conséquent le RREQ est diffusé à travers tout le

réseau jusqu’au destinataire final.

L’accumulation des nœuds du chemin, peut diminuer d’un côté le nombre de diffusion

de RREQ. Mais d’un autre côté la mise-à-jour de la table de routage au niveau de chaque

nœuds pour la prise en compte de tous les nœuds accumulés dans les messages RREQ et

RREP peut entrainer la suppression de paquets et la génération ensuite de messages RERR.

Un autre inconvénient de l’accumulation des nœuds est la taille des paquets RREQ et

RREP qui augmente considérablement.


La figure IV.12 (b) représente l’évolution du délai moyen de bout en bout en fonction

du nombre de nœuds dans le réseau. Le protocole DYMO s’avère plus performant que AODV

car la topologie du réseau est découverte plus rapidement grâce à l’accumulation du chemin

puisqu’à chaque réception d’un message RREQ ou RREP les nœuds enregistrent et mettent à

jour une route dans leur table de routage vers chaque nœud dont l’information de routage est

accumulée dans le message de contrôle.

De plus, l’utilisation d’un format générique de messages de routage pour DYMO permet

de simplifier et de diminuer le temps de traitement des messages au niveau de chaque nœud

contrairement à AODV où chaque message possède son propre format (RREQ, RREP).


A partir de la figure IV.12 (c), on peut constater que l’énergie totale consommée varie

en fonction de la densité des nœuds dans le réseau car plus la densité du réseau augmente plus

la probabilité de collision entre deux messages de recherche de route sera élevée. Néanmoins,

le protocole DYMO économise plus d’énergie par rapport à AODV, car la découverte de route

est plus rapide et les chemins empruntés sont plus optimales.


96

30 40 50 60 70 80 90 100 110 1200

200

400

600

800

1000

1200

Densité du réseau

Nom

bre

de

mes

sage

sd

eco

ntr

ôle

AODVDYMO


30 40 50 60 70 80 90 100 110 1206

8

10

12

14

16

18

20

Densité du réseau

Dé

lai

moy

en

debo

uten

bou

t(m

s)

AODVDYMO



97

30 40 50 60 70 80 90 100 110 120100

200

300

400

500

600

700

800

900

Densité du réseau

Ene

rgie

tota

leco

nso

mm

ée(J

oul

es)

AODVDYMO


Figure IV.12 : Comparaison des performances entre AODV et DYMO avec la variation de

la densité du réseau.

IV.6.1.4. Comparaison entre AODV_M et DYMO_M


Comme nous avons pu le constater sur la figure IV.12 (a), le nombre de messages de

contrôle est inférieur avec AODV par rapport à DYMO grâce à l’utilisation des RREP gratuits

alors qu’avec DYMO un message RREQ doit atteindre sa destination avant la génération d’un

message RREP. Cependant, la version multi-chemins de AODV ne permet pas la génération

de messages RREP par un nœud intermédiaire afin que la destination puisse décider de la

disjonction des chemins. Donc, sur ce point, les deux protocoles de routage deviennent

équitables ce qui explique que le nombre de messages de contrôle décroit généralement en

utilisant DYMO par rapport à AODV (voir figure IV.13 (a)).

Le nombre de messages de contrôle dépend aussi du nombre de chemins à nœuds

disjoints trouvés lors d’une procédure de découverte de routes. Si le nombre de chemins est

supérieur ou égale à 2 donc le nombre de découverte de routes diminue considérablement et

nous obtenons un meilleur résultat que ça soit avec AODV_M ou DYMO_M.


98


En ajoutant la version multi-chemins aux deux protocoles AODV et DYMO on ne fait

qu’améliorer encore plus le délai de bout en bout car le nombre de diffusion de messages de

contrôle diminue pour les deux protocoles en utilisant des routes disponibles au préalable

dans la table de routage. Cependant, puisque le protocole DYMO de base offre un délai

inférieur par rapport à AODV donc, le meilleur délai de transmission de données a été obtenu

avec DYMO_M (voir figure IV.13 (b)).


A partir de la figure IV.13 (c), nous remarquons que DYMO_M économise plus

d’énergie par rapport à AODV_M car le temps de réponse offert par DYMO_M est meilleur

que celui de AODV_M et comme le code source de DYMO_M est plus simplifié en ajoutant

un format générique de messages de routage par rapport à AODV_M donc le temps de

traitement au niveau de chaque nœud est plus court, ce qui explique que l’énergie consommée

au niveau des nœuds intermédiaires est moins importante par rapport à AODV_M.

30 40 50 60 70 80 90 100 110 1200

200

400

600

800

1000

1200

Densité du réseau

Nom

bre

dem

essa

ges

deco

ntrô

le

AODV-MDYMO-M



99

30 40 50 60 70 80 90 100 110 1206

8

10

12

14

16

18

20

22

Densité du réseau

Dél

aim

oyen

deb

out

en

bou

t(m

s)

AODV-MDYMO-M


30 40 50 60 70 80 90 100 110 120100

200

300

400

500

600

700

800

900

Densité du réseau

En

ergi

eto

tale

cons

om

mé

e(J

oule

s)

AODV-MDYMO-M


Figure IV.13 : Comparaison des performances entre AODV_M et DYMO_M avec la

variation de la densité du réseau.

IV.6.1.5. Comparaison entre AODV_MQ et DYMO_MQ


Comme on peut le voir sur la figure IV.14 (a), le nombre de diffusion diminue

considérablement avec le routage multi-chemins combiné avec des contraintes de QoS pour


100

les deux protocoles. Cependant, nous avons obtenu plus de réduction du nombre de messages

de contrôle avec DYMO_MQ car nous avons trouvé plus de chemins disjoints lors des

simulations ce qui permet d’éviter la génération de nouvelles procédures de découverte de

routes même en cas de plusieurs ruptures de liens.


L’ajout des métriques de QoS à la version multi-chemins améliore le délai de bout en

bout pour les deux protocoles de routage. Généralement, ce délai est encore inférieur pour

DYMO_MQ car celui-ci, offre un temps de réponse meilleur que celui de AODV_MQ (voir

figure IV.14 (b)).


A partir de la figure IV.14 (c), on remarque que l’énergie totale consommée dans le

réseau diminue en utilisant le protocole DYMO_MQ par rapport à AODV_MQ, puisque

DYMO_M économise plus d’énergie par rapport à AODV_M. Donc, en ajoutant la QoS, les

nœuds intermédiaires vont traiter moins de paquets de contrôle grâce aux conditions

introduites par les contraintes de délai et de taux d’erreur et par conséquent ils réduisent

l’énergie consommée dans le réseau.

30 40 50 60 70 80 90 100 110 1200

100

200

300

400

500

600

700

800

Densité du réseau

No

mbr

ede

mes

sag

es

de

con

trôl

e

AODV-MQDYMO-MQ



101

30 40 50 60 70 80 90 100 110 1206

8

10

12

14

16

18

Densité du réseau

Dél

aim

oyen

deb

out

en

bou

t(m

s)

AODV-MQ

DYMO-MQ


30 40 50 60 70 80 90 100 110 120100

200

300

400

500

600

700

800

900

Densité du réseau

Ene

rgie

tota

leco

nso

mm

ée(J

oul

es)

AODV-MQDYMO-MQ


Figure IV.14 : Comparaison des performances entre AODV_MQ et DYMO_MQ avec la

variation de la densité du réseau.


102

IV.6.2. Variation de la vitesse de déplacement des nœuds (mobilité)

IV.6.2.1. Comparaison entre AODV et DYMO


Comme on peut le distinguer sur la figure IV.15 (a), la mobilité des nœuds influence

sur le nombre de messages de contrôle diffusés dans le réseau car lorsque les nœuds sont très

mobiles, le nombre de routes qui tombent en panne augmente rapidement ce qui entraine le

déclenchement de plusieurs procédures de recherche de route.

Malgré que DYMO d’origine génère plus de messages de contrôle, celui-ci réagit mieux

aux changements fréquents de topologie par rapport à AODV.


A partir de la figure IV.15 (b), nous constatons une dégradation du délai moyen de bout

en bout en fonction de la mobilité des nœuds pour le protocole AODV.

Quant au protocole DYMO, le délai moyen de bout en bout est toujours inférieur car la

procédure de routage de ce protocole est plus rapide que celle de AODV et par conséquent les

paquets de données sont acheminés avec un délai plus faible à leur destination.


On remarque clairement à partir des résultats illustrés sur la figure IV.15 (c), que

l’énergie consommée dans le réseau varie en fonction de la vitesse de déplacement des nœuds

pour les deux protocoles de routage, ceci à cause du changement fréquent de la topologie du

réseau qui influe énormément sur la ressource d’énergie des nœuds capteurs. En ce qui

concerne DYMO, l’énergie consommée au niveau des nœuds diminue par rapport à AODV car

les messages de routage sont traités rapidement grâce à leur format générique et à la simplicité

du code source.


103

4 6 8 10 12 14 16 18 20 22 24400

450

500

550

600

650

700

750

800

850

Vitesse de déplacement

Nom

bre

de

mes

sage

sd

eco

ntr

ôle

AODVDYMO

(a) Nombre de messages de contrôle.

4 6 8 10 12 14 16 18 20 22 2414.5

15

15.5

16

16.5

17

17.5


Dé

lai

moy

en

debo

uten

bou

t(m

s)

AODVDYMO

(b) Délai moyen de bout en bout.


104

4 6 8 10 12 14 16 18 20 22 24500

550

600

650


Ene

rgie

tota

leco

nso

mm

ée(J

oul

es)

AODVDYMO


Figure IV.15 : Comparaison des performances entre AODV et DYMO avec la variation de

la mobilité des nœuds.

IV.6.2.2. Comparaison entre AODV_MQ et DYMO_MQ


Comme nous pouvons le distinguer sur la figure IV.16 (a), en utilisant des protocoles

multi-chemins le nombre de messages de contrôle vari aussi en fonction de la mobilité des

nœuds dans le réseau car lorsque les nœuds sont très mobiles, le nombre de messages

d’erreur de route RERR va augmenter, donc les chemins stockés dans la table de routage vont

être épuisés rapidement ce qui engendre la production d’un nombre considérable de messages

de contrôle.


Sur la figure IV.16 (b), nous constatons une variation du délai de bout en bout en

fonction de la mobilité des nœuds pour les deux protocoles multi-chemins.

En augmentant la vitesse de déplacement des nœuds, nous avons pu conclure que

DYMO_MQ est plus performant par rapport à AODV_MQ car le délai moyen de bout en bout

obtenue lors de nos différentes simulation est meilleur que celui de AODV_MQ ce qui permet

d’assurer plus de fiabilité de transmission des données dans le réseau.


105


On voit clairement sur la figure IV.16 (c), qu’avec DYMO_MQ l’énergie consommée

dans le réseau est plus faible par rapport à AODV_MQ. Donc, nous pouvons déduire que la

version multi-chemins avec QoS apportée à DYMO assure plus de fiabilité et permet de

prolonger la durée de vie du réseau même en cas de changements fréquents de topologie.

4 6 8 10 12 14 16 18 20 22 24350

400

450

500

550

600

650


Nom

bre

dem

essa

ges

deco

ntrô

le

AODV-MQDYMO-MQ

(a) Nombre de messages de contrôle.

4 6 8 10 12 14 16 18 20 22 2413.5

14

14.5

15

15.5

16

16.5

17

17.5


Dél

aim

oye

nde

bou

ten

bout

(ms

)

AODV-MQDYMO-MQ

(b) Délai moyen de bout en bout.


106

4 6 8 10 12 14 16 18 20 22 24400

450

500

550

600

650

700


Ene

rgie

tota

leco

nso

mm

ée(J

oule

s)

AODV-MQDYMO-MQ


Figure IV.16 : Comparaison des performances entre AODV_MQ et DYMO_MQ avec la

variation de la mobilité des nœuds.

IV.6.3. Impact de la variation du seuil de tolérance d’interférence

Nous présentons dans cette section les résultats que nous avons obtenus en prenant en

considération le facteur d’interférence sur la découverte de chemins multiples.

Dans cette expérimentation, nous avons proposé d’estimer le nombre de chemins

trouvés par rapport au seuil de tolérance fixé au niveau du nœud source, afin de faire un

compromis entre la possibilité de trouver le maximum de chemin disjoints tout en assurant le

minimum d’interférences entre ces derniers.

A partir des résultats illustrés sur la figure IV.17, nous pouvons remarquer tout d’abord

que le nombre de chemins à nœuds disjoints trouvés diminue dans les réseaux très denses à

cause du nombre de nœuds intermédiaires qui augmente dans ce type de réseau.

On constate aussi que le seuil de tolérance influence sur le nombre de chemins trouvés.

En limitant le seuil de tolérance à «2» avec la variation de la densité du réseau, nous avons

obtenu le maximum de chemins, car dans ce cas (d’après les exemples de fichiers

d’expérimentation que nous avons simulé), on peut avoir jusqu’à deux nœuds du chemin

précédent qui appartiennent au voisinage de chaque nœud intermédiaire du chemin courant.

Avec un seuil de tolérance égale à «1,5», on obtient moins de chemins puisque nous avons au

maximum un seul nœud du chemin précédent qui appartient au voisinage d’un nœud


107

intermédiaire du chemin courant et par conséquent moins de nœuds qui s’interfèrent. Donc, si

on veut assurer le minimum d’interférences tout en bénéficiant du routage multi-chemins,

nous pouvons limiter le seuil de tolérance de telle sorte à accepter au moins deux chemins

disjoints.

0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 20

1

2

3

4

5

6

7

Seuil de tolérance

Nom

bre

de

che

min

s

100 Noeuds

200 Noeuds400 Noeuds

Figure IV.17 : Le nombre de chemins trouvés par rapport au seuil de tolérance.

IV.7. Conclusion

Dans ce chapitre, nous avons illustré nos différents résultats obtenus après avoir

implémenté nos protocoles de routage multi-chemins sous NS2.

Une analyse comparative des performances entre les versions multi-chemins avec/sans

QoS et les versions à chemin unique des protocoles de routage proposés montre clairement

l’efficacité de l’approche multi-chemins et son intérêt pour les RCSF, afin de faire face aux

changements de topologie et d’assurer une meilleure QoS dans le réseau.

A travers nos différents résultats, nous avons pu déduire que le protocole DYMO_MQ

fournit plus de fiabilité avec un meilleur délai de transmission de données par rapport à

AODV_MQ grâce à sa rapidité de traitement et au format générique de ses messages de

routage et permet par conséquent de minimiser l’énergie consommée dans le réseau.

Concernant l’étude de l’interférence, celle-ci n’a pas été menée en profondeur car c’est

plus pertinent de l’évaluer en exploitant les différents chemins en parallèle. Cependant, cette

approche a été implémentée dans le but d’estimer le nombre de chemins trouvés par rapport

au seuil de tolérance.

Conclusion générale

108


Les réseaux de capteurs sans fil (RCSF) sont une nouvelle technologie qui a pu voir le

jour avec le développement phénoménal de plusieurs domaines, tels que les technologies sans

fil, les télécommunications et les microprocesseurs embarqués. Les RCSF ont beaucoup de

succès, surtout à cause du coût relativement faible de leur déploiement et de leurs nombreuses

applications prometteuses.

Cependant, la topologie dynamique des RCSF et la limitation des ressources des

capteurs (énergie, calcul, mémoire et bande passante) représentent de nombreux défis pour la

conception de protocoles de routage qui visent à économiser ces ressource et assurer un

routage fiable avec une certaine qualité de service (QoS) surtout pour les applications dont les

données sont urgentes et importantes.

L’objectif de notre projet est d’améliorer la stratégie du routage existante en utilisant

des protocoles de routage multi-chemins avec QoS dans une perspective de tolérance aux

pannes dans les RCSF où le changement de topologie est relativement fréquent.

En premier lieu, nous avons donné un aperçu sur les RCSF ainsi que les différents

protocoles de routage qui existent pour ce type de réseau.

Ensuite, nous avons d’abord commencé par l’étude du protocole de routage AODV

multi-chemins avec QoS que nous avons amélioré afin d’assurer un routage fiable et réduire le

trafic de contrôle dans le réseau. Les résultats obtenus nous ont permis d’évaluer les

différentes extensions apportées à DYMO.

Nous nous sommes intéressés ultérieurement au nouveau protocole de routage DYMO

en voie de standardisation. Celui-ci, a hérité des fonctionnalités de AODV et des avantages de

DSR pour l’accumulation des nœuds du chemin. Après avoir illustré le mécanisme de routage

de ce protocole, nous avons apporté les extensions nécessaires pour le rendre multi-chemins à

nœuds disjoints en prenant en considération aussi les contraintes de QoS exprimées en termes

de délai et de taux d’erreur.

Nos contributions dans ce mémoire, se sont concrétisées, grâce à l’utilisation du

simulateur NS2, par une implémentation des protocoles de routage AODV_MQ et DYMO_MQ


109

et une étude comparative, selon certaines métriques de performance, entre les protocoles

multi-chemins développés ainsi que leur version à chemin unique afin de bien illustrer

l’avantage de l’approche de routage multi-chemins et de distinguer la différence entre les

deux protocoles AODV et DYMO .

Les évaluations par simulation, présentées et discutées au sein du dernier chapitre nous

ont permis de déduire ce qui suit :

Les extensions apportées aux deux protocoles proposés améliorent considérablement la

stratégie du routage en minimisant les effets d’inondations massives tout en assurant un

meilleur délai de transmission des données et en réduisant la consommation d’énergie

dans le réseau.

Vue l’originalité de la structure des messages de routage du protocole DYMO_MQ et sa

rapidité de traitement, celui-ci offre un délai plus optimal par rapport à AODV_MQ et

permet de prolonger la durée de vie du réseau même en cas de changements fréquents de

topologie.

Perspectives

110

Perspectives

Les travaux que nous avons effectués dans ce mémoire nous ouvrent de nombreuses

perspectives de recherche futures qui peuvent être résumées comme suit :

Utilisation du Standard ZigBee/IEEE 802.15.4

Dans nos différentes expérimentations, nous avons utilisé la couche basse IEEE 802.11.

Cependant, nous suggérons dans le futur l’utilisation du standard ZigBee car ce dernier offre

un ensemble de services pour les RCSF au-dessus de la couche IEEE 802.15.4, en particulier

pour la préservation de l’énergie, afin d’accroître l’autonomie du nœud capteur.

Multiplication du nombre de sources simultanément

Notre étude a été limitée à un seul nœud capteur source, et peut être étendue à plusieurs

sources génératrices de trafic simultanément dans un RCSF.

Exploitation des chemins

Dans notre travail, nous avons exploité les chemins d’une manière alternative dans une

perspective de tolérance aux pannes. Ces chemins peuvent être exploités aussi simultanément

afin d’assurer une répartition équilibrée de la charge dans le réseau.

Etude d’autres paramètres de performance

Ce travail peut être enrichi par la suite en considérant d’autres métriques de QoS telles

que le calcul de la bande passante afin de minimiser les interférences dans le réseau.

Optimisation de la taille des messages de contrôle

Afin de remédier aux problèmes de congestion liés à la taille des messages de contrôle

(RREQ, RREP) qui augmente, surtout lorsque le réseau est très large, nous proposons un

couplage de notre solution avec une approche de compression ou d’agrégation des adresses

des nœuds capteurs.

Comparaison de notre protocole multi-chemins avec d’autres protocoles existants

Dans notre étude nous avons comparé notre approche multi-chemins DYMO_MQ

seulement avec le protocole d’origine DYMO et le protocole multi-chemins AODV_MQ que

nous avons nous même amélioré. Il serait intéressant de comparer les performances de la

solution proposée avec des algorithmes de routage dédiés aux RCSF tels que le protocole

SPEED ou encore SAR.

Bibliographie

111

Bibliographie

[1] A. Benjerad, N. Boukhordj, Implémentation et évaluation de l’approche Multi-cheminspour le routage avec qualité de service dans les réseaux de capteurs sans fil, Mémoired’ingénieur, Université d’Oran Es-sénia, Oran, Algérie, Juin 2007.

[2] R. Meraihi, Gestion de la qualité de service et contrôle de topologie dans les réseauxad hoc, Thèse de doctorat, Ecole nationale supérieure des télécommunications, Paris,France, 2003.

[3] M. Hauspie, Contributions à l'étude des gestionnaires de services distribués dans lesréseaux ad hoc, Thèse de doctorat, Université des Sciences et Technologies de Lille,France, 2005.

[4] F. Khadidja, Techniques d’optimisation pour l’économie d’énergie dans les réseaux decapteurs sans fil, Mémoire de magister, Université d’Oran Es-sénia, Oran, Algérie,Juillet 2008.

[5] F. I. Benaribi, Application de la théorie de la redondance pour la surveillance d’unréseau de capteurs sans fil , Mémoire d’ingénieur, Université d’Oran Es-sénia, Oran,Algérie, Juin 2006.

[6] N. H. Vaidya, P. Bahl, S. Gupta, "Distributed fair scheduling in wireless LAN", SixthAnnual International Conference on Mobile Computing and Networking, Boston, USA,pp. 67-78, Août 2000.

[7] T. atteyne, Proposition et validation formelle d’un protocole MAC temps réel pourréseaux de capteurs linéaires sans fils, Mémoire de Master Recherche Informatique,Laboratoire CITI, Lyon, France, 2005.

[8] XBOW, Produit et technologie des RCSF, accessible via le lien :http://www.xbow.com/.

[9] Ian F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E.Cayirci, "A survey on sensornetworks", IEEE Communications Magazine, Vol. 40, pp. 102-116, Août 2002.

[10] TyniOS, TyniOS community, accessible via le lien : http://www.tinyos.net/.[11] C. Han, E. Kohler, M. Srivastava, R. Kumar, R. Shea, "A Dynamic Operating System

for Sensor Nodes", 3rd International Conference on Mobile Systems, Applications andServices Mobisys, Californie, Los Angeles, Juin 2005.

[12] A. Dunkels, B. Grönvall, T. Voigt, "Contiki- a Lightweight and Flexible OperatingSystem for Tiny Networked Sensors", 29th Annual IEEE International Conference onLocal Computer Networks, Kista, Suède, pp. 455–462, 2004

[13] C. Duffy, C. J. Sreenan, J. Herbert, U. Roedig, A Performance Analysis of MANTIS andTinyOS, Rapport technique, Université de Cork, Irelande, Novembre 2008.

[14] H. Alatrista, J. Mathieu, K. Gouaich S. Aliaga, Implémentation de protocoles sur uneplateforme de réseaux de capteurs sans fil, TER Master 1 Informatique, Université deMonpellier II, Monpellier, France, Avril 2008.

[15] B. Kechar, Technologie sans fil (WLAN), rapport de recherche, Université d’Oran Es-sénia, Oran, Algérie, 2006.

[16] A. Sinha, A. Chandrakasan , "Dynamic Power Management in Wireless SensorNetworks", IEEE Design & Test, Vol.18, N°2, pp.62-74, Mars 2001.

Bibliographie

112

[17] N. Lasla, La gestion de clés dans les réseaux de capteurs sans fil, Mémoire deMagister, Institut National de formation en Informatique (I.N.I), Oued-Smar, Alger,2007.

[18] M. Ilyas, I. Mahgoub, Handbook of Sensor Networks : Compact Wireless and WiredSensing Systems, Boca Raton, FL, USA, CRC PRESS, ISBN : EB-19157, 2005.

[19] ZigBee Alliance, accessible via le lien : http://www.zigbee.org.[20] C. Viallon, Optimisation de structures différentielles en technologie SiGe pour

applications en bande millimétrique. Application à la conception d'un mélangeurdoublement équilibré en bande K. Thèse de doctorat, Université Paul Sabatier UPS,Toulouse, France, Décembre 2003.

[21] Nam, Kyudon Choi, "A 2.4GHz low Power Low IF Receiver and Direct conversionTransmitter in 0.18 μm CMOS for IEEE 802.15.4 WPAN Applications". IEEETransactions on Microwave theory and technique. Vol. 55, n°. 4, Avril 2007.

[22] M. Camus, Architecture de réception RF très faible coût et très faible puissance.Application aux réseaux de capteurs et au standard ZigBee. Thèse de Doctorat,Université de Toulouse, Toulouse, France, Février 2008.

[23] K. Bakar, Techniques de compression et d’agrégation à efficacité énergétique dans lesRCSF. Thèse de magister. Université d’Oran Es-Senia, Oran, Algérie, Février 2008.

[24] G. Chalhoub, Réseaux de capteurs sans fil, Support de court, Clermont Université,Clermont-Ferrand, France, décembre 2009.

[25] J. N. Al-Karaki, A. E. Kamal, "Routing Techniques in Wireless Sensor networks: ASurvey", IEEE Wireless Communications, Vol. 11, N°. 6, pp. 6 – 28, Décembre 2004.

[26] J. N. Al-Karaki, "Analysis of Routing Security-Energy Tradeoffs in Wireless SensorNetworks", International Journal of Security and Networks (IJSN), Vol.1, N°.2, pp.147-157, Décembre 2006.

[27] W. Heinzelman, J. Kulik, and H. Balakrishnan, "Adaptive protocols for informationdissemination in wireless sensor networks", 5th Annual ACM/IEEE InternationalConference on Mobile Computing and Networking (MobiCom’99), Seattle, USA, pp.174-185, Août 1999.

[28] C. Intanagonwiwat, R. Govindan and D. Estrin, "Directed diffusion: A scalable androbust communication paradigm for sensor networks", 6th Annual ACM/IEEEInternational Conference on Mobile Computing and Networking (MobiCom'00),Boston, Massachusetts, pp. 56-67, Août 2000.

[29] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, "Energy-efficientcommunication protocol for wireless microsensor networks", 33rd HawaiiInternational Conference on System Sciences, Hawaii, USA, pp. 3005-3014, Janvier2000.

[30] S. Lindsey and C. S. Raghavendra, "PEGASIS: Power Efficient GAthering in SensorInformation Systems", IEEE Aerospace Conference, Big Sky, Montana, USA, pp.1125-1130, Mars 2002.

[31] V. Rodoplu and T.H. Ming, "Minimum energy mobile wireless networks", IEEEJournal of Selected Areas in Communications, Vol. 17, N°. 8, pp. 1333-1344, 1999.

[32] Y. Yu, D. Estrin, and R. Govindan, Geographical and Energy-Aware Routing: ARecursive Data Dissemination Protocol for Wireless Sensor Networks, Rapport derecherche, UCLA-CSD, Université de la Californi, Los Angeles, USA, May 2001.

Bibliographie

113

[33] X. Li, Multipath Routing and QoS Provisioning in Mobile Ad hoc Networks, Thèse dedoctorat. Department of Electronic Engineering Queen Mary, University de Londre,Angleterre, Avril 2006.

[34] T. He, J. A. Stankovic, C. Lu, T. F. Abdelzaher., "SPEED: A stateless protocol for real-time communication in sensor networks", International Conference on DistributedComputing Systems (ICDCF’03), Providence, Rhode Island, USA, pp. 533-532, Mai2003.

[35] S. Mueller, R.P.Tsany, D.Ghosal, Multipath Routing in Mobile Ad hoc Net work :Issuesand chalanges, Rapport de recherche, Université de Californie, Sandia NationalLaboratories, Californie, USA, 2004.

[36] S. Lee and M. Gerla, "Split multipath routing with maximally disjoint paths in Ad Hocnetworks", IEEE International Conference on Communication (ICC), Helsinki,Finland, pp. 3201-3205, 2001.

[37] V. Loscri, F. De Rango, S. Marano, "Ad hoc On-demand Multipath Distance Vectorrouting (AOMDV) over a distributed TDMA MAC protocol for QoS support inwireless ad hoc networks: integration issues and performance evaluation", EuropeanTransactions on Telecommunications, Vol.18, N°2, pp. 141-156, Mai 2006.

[38] J. J. Galvez, P. M. Ruiz, "Design and performance Evaluation of Multipath Extensionsfor the DYMO Protocol", 32nd IEEE Conference on Local Computer Networks,Dublin, Irlande, pp. 885-892, 2007.

[39] G. Parissidis, V. Lenders, M. May, and B. Plattner, "Multi-path Routing Protocols inWireless Mobile Ad Hoc Networks: A Quantitative Comparison", 6th InternationalConference on Next Generation Teletraffic and Wired/Wireless Advanced NetworkingNEW2AN, St.Petersburg, Russia, Vol. 4003, N°. 6, pp. 313-326, Mai 2006.

[40] T. Clausen and P. Jacquet, Optimized Link-State Routing Protocol (OLSR), RFC 3626,IETF, Octobre 2003.

[41] F. Guidec, Déploiement et support à l’exécution de services communicants dans lesenvironnements d’informatique ambiante, Mémoire de magister, Université deBretagne Sud, Morbihan, France, Juin 2008.

[42] M. Sedrati, L. Aouragh, L. Guettala, A. Bilami, "Etude des Performances desProtocoles de Routage dans les Réseaux Mobiles Ad-Hoc", 4th InternationalConference on Computer Integrated Manufacturing CIP’2007, Novembre 2007.

[43] P. Jacquet, P. Mühlethaler, T. Clausen, A. Laouiti, A. Qayyum, and L. Viennot,"Optimized link state routing protocol for ad hoc networks", 5th IEEE InternationalMulti Topic Conference (INMIC 2001), Lahore, Pakistan, pp.62-68, 2001.

[44] A. Qayyum, L. Viennot, and A. Laouiti, Multipoint Relaying : An Efficient Techniquefor flooding in Mobile Wireless Networks, rapport de recherche, INRIA, Rocquencourt,France, Fevrier 2000.

[45] D. B. Johnson, D. A. Maltz, "Dynamic Source Routing in Ad Hoc Wireless Networks",Mobile Computing, Imielinski and Korth, Eds, Kluwer Academic Publishers, Vol. 353,pp. 153–181, 1996.

[46] D. Johnson, Y. Hu, D. Maltz, The Dynamic Source Routing Protocol (DSR) for MobileAd Hoc Networks for IPv4, RFC 4728, IETF,2007.

[47] V. Untz, Les réseaux sans fil spontanés pour l’Internet Ambiant, Thèse de doctorat,Laboratoire d’informatique de Grenoble, France, décembre 2007.

[48] Y.C. Hu, D. B. Johnson, "Implicit source routes for on-demand ad hoc networkrouting", 2nd ACM international symposium on Mobile ad hoc networking &computing MobiHoc ’01, New York, USA, pp. 1-10, 2001.

Bibliographie

114

[49] N. Mansouri, Protocole de routage multi-chemin avec équilibrage de charge dans lesréseaux mobiles Ad Hoc, Mémoire d’ingénieur, Ecole supérieure des communicationsde Tunis, Tunisie, 2007.

[50] C. Perkins, E. Belding-Royer, S. Das, Ad hoc On-Demand Distance Vector (AODV)Routing, RFC3561, IETF, Juillet 2003.

[51] D. Elorrieta, Protocoles de routage pour l’interconnexion des réseaux Ad-Hoc etUMTS, Mémoire d’ingénieur, Université Libre de Bruxelles ULB, Belgique, 2007.

[52] H. Boukouna, Adaptation d’un protocole de découverte de services pour les réseauxAd-Hoc, Mémoire d’ingénieur, Université du Québec à Montréal, Canada, Septembre2008.

[53] M. Dawoud, Analyse du protocole AODV, Mémoire de DEA, Université Paul SabatierI.R.I.T, Toulouse, France, 2006.

[54] C. Louberry, Modèles de flux d’information et de composants permettant la réalisationd’applications par interconnexion de composants logiciels (d’interface et detraitement) et matériels (capteurs), Master Technologie de l’Internet, InstitutUniversitaire de Technologie Bayonne, Pays Basque, 2006.

[55] B. Kechar, Z. Bidai, H. Haffaf, "Node Disjoint Multipath Routing scheme with delayguarantee in Wireless Sensor Networks", International Conference on Web andInformation Technologies, Sidi Bel Abbes, Algérie, pp. 281-286, Juin 2008.

[56] N. Bendimerad, B. Kechar, Z. Bidai, H. Haffaf, "Multipath On-demand RoutingProtocol with Quality of Service for Wireless Sensor Networks", InternationalConference on Applied Informatics, Bordj Bou Arréridj, Algérie, pp. 34-39, Novembre,2009.

[57] D. Hwang, E. Kwon, J. Lim, "EASR: An Energy Aware Source Routing with DisjointMultipath Selection for Energy-Efficient Multihop Wireless Ad hoc Networks",International IFIP-TC6 Networking Conference, Vol. 3976, N°. 5, pp. 41-50, 2006.

[58] A. H. Al Muktadir, "Energy Consumption Study of OLSR and DYMO MANETRouting Protocols in Urban Area", National Conference on Communication andInformation Security, NCCIS, Dhaka, Bangladesh, pp. 131-137, 2007.

[59] S. Gwalani, E. M. Belding-Royer, and C. E. Perkins, "AODV-PA: AODV with pathaccumulation", IEEE International Conference on Communications (ICC’ 03),Anchorage, Alaska, Vol. 1, pp. 527–531, May 2003.

[60] Ian D. Chakeres and L. Klein-Berndt, "AODVjr, AODV simplified", ACMSIGMOBILE Mobile Computing and Communications Review, Vol. 6 , N°. 3, pp. 100-101, Juillet 2002.

[61] S. R. Abdul Aziz, N. A Endut, S. Abdullah and M. Norazman, "PerformanceEvaluation of AODV, DSR and DYMO routing protocol in MANET", Conference OnScientific&Social Research CSSR, Malaisie, pp. 219-228, Mars 2009.

[62] I. Dietrich, C. Sommer, F. Dressler, Simulating DYMO in OMNet++, rapport derecherche, Université d’Erlangen, Erlangen-Nurnberg, Allemagne, 2007.

[63] J. J. Galvez, P. M. Ruiz, "Design and Performance Evaluation of Multipath Extensionsfor the DYMO protocol", 7th IEEE International Workshop on Wireless LocalNetworks, Dublin, Ireland, pp. 885-892, 2007.

[64] I. Chakeres, C. Perkins, Dynamic MANET On-demand (DYMO) Routing, draft-ietf-manet-dymo-17, IETF, Mars 2009.

[65] P. Tran, C. Wibom, Simulation and Analysis of a Wireless Ad-hoc Network usingenergy aware DYMO, Mémoire d’ingénieur, Université de Lund, LTH, Suède, 2007.

Bibliographie

115

[66] R. E. Thorup, Implementing and Evaluating the DYMO Routing Protocol, Thèse dedoctorat. Université de AARHUS, Denemark, Fevrier 2007.

[67] D. Johnson, A. Lysko, "Comparison of MANET routing protocols using a scaled indoorwireless grid", Mobile Networks and Applications, Vol. 13, N°. 1-2 , pp. 82-96, Avril2008.

[68] C. Perkins, U. Herberg, R. Cole, I. Chakeres, Definition of Managed Objects forNeighborhood Discovery Protocol, draft-ietf-manet-nhdp-mib-0.2, IETF, Novembre2009.

[69] D. Johnson, Performance analysis of Mesh Networks in Indoor and Outdoor WirelessTestBeds, Mémoire d’ingénieur, Université de Pretoria, Afrique du sud, Octobre 2007.

[70] A. Rahman, S. AZAD, F. ANWAR, "Performance Analysis of On-Demand RoutingProtocols in Wireless Mesh Networks", Informatica Economica Journal, Vol. 13, N°. 2,pp. 120-127, 2009.

[71] The ns manual, accessible via le lien : http://www.isi.edu/nsnam/ns/tutorial/.[72] Francisco J. Ros MASIMUM, accessible via le lien:

http://masimum.dif.um.es/?Software:DYMOUM.[73] NIST-DYMO, accessible via le lien : https://sourceforge.net/projects/nist-dymo/.[74] DYMO for OPNET, accessible via le lien: http://www.fb1.uni-

bremen.de/comnets/opnet/.[75] EK-DYMO, accessible via le lien: http://monet.knu.ac.kr/dymo/.[76] R. E. Thorup, DYMO-AU, accessible via le lien :

http://www.daimi.au.dk/~rolft/wp/?page_id=17.[77] TYMO, accessible via le lien : http://tymo.sourceforge.net/.[78] C. Sommer, DYMO for OMNeT++, accessible via le lien : http://www7.informatik.uni-

erlangen.de/~sommer/omnet/dymo/.[79] S. Kammoun, Implémentation de la QoS sur un protocole de routage (multicast) Ad

hoc, Mémoire d’ingénieur, Ecole Supérieure des Communication de Tunis, Tunisie,2006.

[80] R. Vidhyapriya, P.T. Vanathi, "Energy Efficient Adaptive Multipath Routing forWireless Sensor Networks", IAENG International Journal of Computer Science, Vol.34, N°.1, pp. 56-64, Août 2007.

Annexe A. Le simulateur NS2 : Aperçu du logiciel

116

Annexe A

Le simulateur NS2 : Aperçu du logiciel

A.1. Présentation du simulateur réseau NS2

NS2 est un outil logiciel de simulation de réseaux informatiques. Il est principalement

bâti sur l’idée de la conception par objets, de la réutilisation du code et de modularité. Il est

devenu aujourd’hui un standard de référence dans ce domaine. C’est un logiciel dans le

domaine public disponible sur l’Internet. Son utilisation est gratuite. Le logiciel est exécutable

tant sous la plateforme Unix que Windows.

Le simulateur NS2 actuel est particulièrement bien adapté aux réseaux à commutation

de paquets et à la réalisation de simulations de petite taille. Il contient

des fonctionnalités nécessaires à l’étude des algorithmes de routage unipoint ou multipoint,

des protocoles de transport, de session, de réservation, des services intégrés et des protocoles

d’application. De plus le simulateur possède déjà une palette de systèmes de transmission,

d’ordonnanceurs et de politiques de gestion de files d’attente pour effectuer des études de

contrôle de congestion. Il permet à l’utilisateur de concevoir un réseau et de simuler les

communications entre les noeuds. Le simulateur utilise le langage orienté objet OTcl (Object

Tcl) dérivé du Tcl (Tool Command Language) pour la description des conditions de

simulation sous forme de script.

La liste des principaux composants actuellement disponible dans NS2 par catégorie est

illustrée sur le tableau suivant:

Application Web ftp, telnet, générateur de trafic (CBR, …)

Transport TCP, UDP, RTP, SRM

Routage Statique, dynamique (vecteur de distance) et routage

multipoint (DVMP, PIM)

Gestion de la file d’attente RED, DropTail, Token bucket

Discipline de service CBQ, SFQ, DRR, Fair queueing

Système de transmission CSMA/CD, CSMA/CA, lien point à point

Tableau A.1 : Principaux composants disponibles dans NS2.


117

Comme tout outil de simulation, NS2 permet l’étude de l’existant, la conception, la

validation et l’évaluation de performances et ceci dans le domaine des protocoles et

mécanismes réseaux. Il bénéficie aussi des avantages d’un simulateur de réseaux tels que la

flexibilité, l’étude des cas difficiles à reproduire dans la réalité, le faible coût des

expérimentations et la reproductibilité des résultats. D’autre part, il souffre de leurs

inconvénients tels que la simplification et l’abstraction du monde réel, la difficulté de tester

certaines choses, et la puissance de calcul requise qui croit avec la complexité du système

simulé. De plus NS2 souffre de l’état primitif aussi bien de ses outils de collecte et de

traitements des résultats que de son interface graphique et de la lenteur de correction des bugs.

L’utilisation de NS2 peut être :

De base : on utilise le simulateur tel quel (code fourni par les développeurs).

Intermédiaire : on ajoute des fonctionnalités sans modifier le cœur du simulateur.

Avancée : on développe son propre code (en C++) et on modifie le cœur du

simulateur.

La figure (A.1) illustre un cycle de simulation typique avec NS2.

Figure A.1 : Cycle d’une simulation.

Le résultat d’une simulation est un fichier texte contenant tous les évènements de la

simulation. Un traitement ultérieur de ce fichier permet d’en extraire l’information souhaitée.

Par ailleurs, le simulateur permet la création d’un fichier d’animation, permettant de

visualiser la simulation sur une interface graphique appelée NAM qui fournit une

Problème àétudier

Modèle desimulation

Analyse desrésultats

Exécution dessimulations

Modification dans NS2(code OTCL et/ou C++)

Création de scénariode simulation


118

représentation du graphe du réseau sur laquelle on peut voir circuler les paquets, suivre le

niveau des files d’attente, etc.

A.2. Architecture et implémentation

NS2 est développé en C++ et en OTcl. Il contient une hiérarchie de classes compilées

d’objets écrits en C++ et une hiérarchie de classes interprétées d’objets écrits en OTcl. Ces

deux hiérarchies sont étroitement liées. En effet, lorsque l’utilisateur crée un nouvel objet par

l’interpréteur OTcl, un objet correspondant, appelé objet reflet, est aussi crée dans la

hiérarchie compilée. D’ailleurs, des procédures d’appel entre OTcl et C++ sont mises en

place permettant ainsi à l’utilisateur d’accéder aux différents objets aussi bien en OTcl qu’en

C++.

Il est à noter que l’utilisation de deux langages permet la séparation entre les plans

«données» et «contrôle» (des échelles temporelles différentes). Le langage C++ est utilisé

pour le plan «données» pour traiter des événements au niveau paquet tels que la génération de

paquets IP et le traitement des paquets dans les routeurs. Quant au langage OTcl, il sert pour

le plan «contrôle» afin de pouvoir effectuer des traitements à des échelles temporelles plus

grandes et coder des modèles de trafic et/ou d’applications simples (application FTP :File

Transfert Protocol ).

L’OTcl permet aussi le contrôle des simulations par la définition des scénarios de

simulation (topologie du réseau, taille des files d’attentes des routeurs, etc.).

L’OTcl est un langage interprété qui ne demande pas de compilation. Il est utilisé pour

concaténer des objets, accéder aux objets à partir de l’interpréteur et configurer des

simulations. Ce langage rend l’utilisation du simulateur assez souple et convivial car il offre

de nombreux objets prédéfinis qui peuvent être utilisés pour simuler un grand nombre de

scénarios assez aisément.

Le langage C++ est utilisé pour créer des classes de base permettant de traiter un grand

nombre de données tels que le calcul des tables de routage, le mouvement des mobiles, etc.

On fait donc appel à ce langage pour programmer des agents adaptés à un comportement

particulier ou à un protocole spécifique.

Au plus bas niveau, il y a six classes qui définissent l’ensemble de la structure du

programme et fournissent les méthodes élémentaires. Il s’agit des classes Tcl, TclObject,

TclClass, TclCommand, EmbeddedTcl et InstVar. Elles définissent entre autres les méthodes

utilisées par C++ pour accéder à l’interpréteur, la hiérarchie, les principales commandes de

haut niveau et les méthodes pour accéder aux variables de C++ et OTcl.


119

La simulation est configurée, contrôlée et gérée à l’aide des interfaces fournies par la

classe OTcl Simulator. Cette classe fournit des procédures pour créer et gérer la topologie,

initialiser le format des paquets et choisir le planificateur d’évènements. Elle stocke

intérieurement des références à chaque élément de la topologie. Un script devra donc toujours

commencer par l’instanciation d’une variable de cette classe. L’utilisateur crée ensuite la

topologie à travers OTcl en utilisant les classes node et link qui sont les composants essentiels

de la topologie.

A.3. La mobilité dans NS2

L’implémentation originale de NS2 ne contient pas une extension pour la simulation des

réseaux mobiles. Les dernières versions du logiciel ont bénéficié de deux extensions de

mobilité :

Wireless Mobility Extension : projet développé par le CMU (Carnegie Mellon University)

Monarch Project,

Mobile IP Extension : projet développé par SunMicroSystem.

L’extension CMU nous offre une architecture protocolaire complète pour la simulation

des réseaux Ad Hoc, cette architecture implémente un modèle de canal physique, un protocole

MAC, le protocole ARP (Address Resolution Protocol) et quelques protocoles de routage Ad

Hoc.

Le modèle de propagation : ce modèle est utilisé pour déterminer si les données

transmises ont été correctement reçues ou pas. Ce modèle inclut les délais de propagation,

l’écoute du canal, la détection de la porteuse, etc.

Le protocole MAC : Le modèle de protocole MAC utilisé est le IEEE 820.11 Distributed

Coordination Function (DCF), donnant la possibilité de transmission point à point (Unicast)

et de diffusion généralisée (Broadcast).

L’interface physique : Chaque nœud mobile est équipé d’une interface physique pour la

transmission et réception des données. Cette interface offre une portée radio de 250m, un

débit maximal de 2 Mb/s et utilise une antenne omnidirectionnelle de gain unité. De plus,

cette interface contient les files d’attentes nécessaires pour dérouler les algorithmes de

routage.

Les données sont générées par la couche application, ensuite les paquets de données

atteignent l’agent de routage qui détermine la route que doit prendre le paquet puis le fait

passer à la couche LLC (Logical Link Control). Celle-ci utilise le protocole de résolution


120

d’adresse (ARP) pour la correspondance entre l’adresse IP du nœud destinataire et son adresse

physique (MAC). Le paquet est ensuite mis dans la file d’attente en attendant que le protocole

MAC décide de le faire passer à l’interface physique qui à son tour l’émet dans le canal radio.

Chaque interface physique qui reçoit un paquet, va y inscrire des informations

particulières puis fait appel au modèle de propagation. Celui-ci utilise alors les informations

qui ont été marquées sur le paquet durant son parcours par les différentes interfaces

physiques, pour estimer la puissance avec laquelle les données sont reçues. Si cette puissance

n’est pas au dessous d’un seuil de détection, alors le paquet est livré à la couche MAC, qui

s’assure de l’absence d’erreurs et de trace de collision, puis le met dans le module « Entry

Point » qui livre le paquet à un démultiplexeur.

Si le paquet a atteint sa destination, le démultiplexeur décide vers quelle application

aiguiller les données, sinon, le démultiplexeur fait passer le paquet à la couche réseau pour

qu’il soit relayé vers sa destination.

Figure A.2 : Structure d’un nœud mobile dans NS2.

A.4. Présentation du langage Tcl

Tcl est un langage de commande comme le Shell UNIX mais qui sert à contrôler les

applications. Son nom signifie Tool Command Language. Tcl offre des structures de

Routing Layer

Link Layer

Interface Queue

MAC Layer

Radio Interface

ARP

Channel


121

programmation telles que les boucles, les procédures ou les notions de variable. Il y a deux

principales façons de se servir de Tcl : comme un langage autonome interprété ou comme une

interface applicative d’un programme classique écrit en C ou C++. En pratique, l’interpréteur

Tcl se présente sous la forme d’une bibliothèque de procédures C qui peut être facilement

incorporée dans une application. Cette application peut alors utiliser les fonctions standards

du langage Tcl mais également ajouter des commandes à l’interpréteur.

A.5. Technique de simulation

La simulation des protocoles de routage des réseaux Ad Hoc s’articule autour de 4

grandes parties interdépendantes :

Pré-simulation : durant cette phase, nous allons générer le script principal en OTcl à faire

transmettre à NS2; ce script est généré automatiquement à partir de plusieurs modèles de

scripts Tcl pour les configurations et la manipulation de fichiers, ainsi qu’un script OTcl

contenant le code de génération du trafic sur le réseau et un autre script OTcl contenant les

instructions définissant le mouvement des nœuds dans le réseau. L’ensemble de ces fichiers

constitue un « scénario » de simulation.

Simulation : durant cette phase, NS2 va simuler les différents scénarios pendant une durée

bien déterminée. Le résultat de ces simulations se trouve dans des fichiers de trace générés par

NS2.

Post-simulation : dans cette phase, nous allons récupérer les fichiers de trace NS2 et en

extraire les résultats que nous voudrions visualiser ou interpréter. Cette extraction ainsi que

toute autre opération de calcul est assurée par plusieurs scripts en langage AWK ou PERL.

Pour notre projet nous avons choisi le langage AWK (celui-ci est présenté dans l’annexe B).

Exploitation des résultats : une fois les résultats calculés, les scripts AWK les

enregistrent dans des fichiers que nous pouvons ensuite sauvegarder ou bien utiliser avec

d’autres programmes pour tracer des courbes ou bien effectuer d’autres calculs comme

MatLab ou Excel. Pour notre projet, nous avons utilisé le langage MatLab qui est un langage

de haut niveau pour le calcul scientifique.

A.6. Exemple d’un script Tcl d’un réseau de 100 nœuds

#Les paramètres utilisés par les nœuds mobiles.

set val(chan) Channel/WirelessChannel ; # Type du canal

set val(prop) Propagation/TwoRayGround ; # Modèle de propagation radio


122

set val(netif) Phy/WirelessPhy ; # Type de l’interface réseau

set val(mac) Mac/802_11 ; # Couche MAC

set val(ifq) Queue/DropTail/PriQueue ; # Politique de gestion de la file d’attente

set val(ll) LL ; # Couche liaison

set val(ant) Antenna/OmniAntenna ; # Type d’antenne

set val(ifqlen) 50 ; # Taille du buffer des nœuds

set val(nn) 100 ; # Nombre de nœuds mobiles

set val(rp) AODV / DYMOUM ; # Protocole de routage

set val(x) 1500 ; # Largeur du champ de déploiement

set val(y) 1500 ; # Hauteur du champ de déploiement

set opt(energymodel) EnergyModel ; # Modèle d’énergie

set opt(initialenergy) 15 ; # Energie initiale

set opt(p_rx) 0.003 ; # Energie de réception

set opt(p_tx) 0.006 ; # Energie de transmission

set dismax 100.00 ; # Distance entre les nœuds

#On crée ensuite une instance du simulateur,

set ns_ [new Simulator]

#Le fichier de trace sera result.tr

set tracefd [open result.tr w]

$ns_ trace-all $tracefd

#Le fichier NAM sera multichemin.nam

set namtrace [open multichemin.nam w]

$ns_ namtrace-all-wireless $namtrace $val(x) $val(y)

#On crée la topologie réseau avec le champ de déploiement

set topo [new Topography]

$topo load_flatgrid $val(x) $val(y)

#L’objet god (General Operations Director) est utilisé pour stocker les informations globales à

#propos de l’environnement.

create-god $val(nn)

#Configuration des nœuds

set chan_1_ [new $val(chan)]

$ns_ node-config -adhocRouting $val(rp) \

-llType $val(ll) \

-macType $val(mac) \


123

-ifqType $val(ifq) \

-ifqLen $val(ifqlen) \

-antType $val(ant) \

-propType $val(prop) \

-phyType $val(netif) \

-topoInstance $topo \

-agentTrace ON \

-routerTrace ON \

-macTrace OFF \

-movementTrace OFF \

-energyTrace ON \

-energyModel $opt(energymodel) \

-initialEnergy $opt(initialenergy) \

-channel $chan_1_

#Utilisation d’une topologie en grille

set n [expr sqrt($val(nn))]

for {set xi 0} {$xi < [expr $n+1]} {incr xi} {

;}

set xi [expr $xi-1]

set t [expr $val(nn)/$xi]

for {set yi 0} {$yi <= [expr $t+1]} {incr yi} {

;}

set nb 0

set di [expr $val(x)/$xi]

set dj [expr $val(y)/$yi]

if {$di>$dismax} {

set di $dismax

}

if {$dj>$dismax} {

set dj $dismax

}

puts $n

puts $xi

puts $yi


124

puts $nb

puts $di

puts $dj

for {set j 1} {$j < $yi} {incr j} {

for {set i 1} {$i <= $xi} {incr i} {

if ($nb<$val(nn)) {

set node_($nb) [$ns_ node]

$node_($nb) random-motion 0

$ns_ at 0.002 "$node_($nb) start"

$node_($nb) set X_ [expr $i*$di]

$node_($nb) set Y_ [expr $j*$dj]

$node_($nb) set Z_ 0

$ns_ at 0 "$node_($nb) setdest [expr $i*$di] [expr $j*$dj] 0.386568985974"

set nb [expr $nb+1]

}

else {

break;

}

}

}

$ns_ at 1.0 "$node_(8) label \"SOURCE\""

$ns_ at 1.0 "$node_(88) label \"SINK\""

#Déplacement de quatre nœuds avec une vitesse de 5 m/s

$ns_ at 2.9 "$node_(48) setdest 200 1200 5.00"




#Configuration du trafic entre les nœuds

set cbr(0) [new Application/Traffic/CBR]

$cbr(0) set packetSize_ 128

$cbr(0) set rate_ 32kb

$cbr(0) set interval_ 0.05

set udp(0) [new Agent/UDP]

$ns_ attach-agent $node_(8) $udp(0)


125

$cbr(0) attach-agent $udp(0)

$ns_ color 0 red

set sink [new Agent/Null]

$ns_ attach-agent $node_(88) $sink

$ns_ connect $udp(0) $sink

for {set i 1} {$i < $val(nn)} {incr i} {

set udp($i) [new Agent/UDP]

set cbr($i) [new Application/Traffic/CBR]

$cbr($i) set packetSize_ 128

$cbr($i) set rate_ 32kb

$ns_ attach-agent $node_($i) $udp($i)

$cbr($i) attach-agent $udp($i)

$ns_ connect $udp($i) $sink

}

#L’instant ou la simulation va se terminer

for {set i 0} {$i < $val(nn) } {incr i} {

$ns_ at 100.0 "$node_($i) reset";

}

$ns_ at 100.0 "stop"

$ns_ at 100.01 "puts \"NS EXITING...\" ; $ns_ halt"

puts $tracefd "nbr $val(nn)"

proc stop {} {

global ns_ tracefd

$ns_ flush-trace

close $tracefd

exec ./nam multichemin.nam &

exit 0

}

#On lance la simulation

puts " Debut..."

$ns_ run

Annexe B. Le langage AWK

126

Annexe B

Le langage AWK

B.1. Présentation

AWK est un outil qui permet d’effectuer des recherches, simples ou complexes dans des

fichiers texte. C’est un langage de programmation datant de 1977, l’année de son apparition

dans le monde Unix. Le nom AWK est l’assemblage des initiales des noms des créateurs du

langage : Alfred V. Aho, Peter J. Weinberger et Brian W. Kernighan. Sa grande souplesse lui

a permis de connaître un succès immédiat. Aujourd’hui encore, cet utilitaire est toujours

utilisé du fait de sa ressemblance avec le langage C et de sa présence sur la majorité des

systèmes d’exploitation Unix. Il est encore utilisé en administration système et dans les scripts

Shell en tant que commande.

AWK fonctionne en lisant des données. Ces données peuvent être ainsi traitées par

l’utilisateur qui peut choisir de lire des données provenant de fichiers ou du canal de l’entrée

standard. Par conséquent, AWK a pour but premier de jouer un rôle de filtre bien qu’il ne se

limite pas qu’à cela.

B.2. Syntaxe générale d’un programme AWK

Un programme AWK est constitué de trois grandes sections :

La section initiale : les commandes qu’elle contient sont lues et traitées avant la lecture

du fichier en entrée. C’est le bon endroit pour initialiser des variables par exemple et donc

préparer la suite du programme. Elle commence par le mot clef « BEGIN » et doit être

obligatoirement suivie de son accolade ouvrante sur la même ligne.

La section terminale : comme son nom l’indique, la section terminale n’est traitée

qu’une fois le fichier en entrée fermé. Elle permet d’afficher les résultats du cœur du

programme ainsi que d’autres messages. Elle est introduite par le mot clef « END » et suivie

de son accolade ouvrante sur la même ligne.

La section des règles : c’est la section où nous mettons les lignes de code de traitement

du fichier. Chaque ensemble de commandes est spécifié entre accolades et précédé d’une

entrée.


127

B.3. Exécution d’un programme AWK

Il y a deux façons générales d’exécuter des instructions AWK :

1. Pour des applications simples

L’instruction d’exécution est sous la forme :

awk ‘program’ fichier … fichier n

‘program’ : est une liste d’instructions se présentant sous la forme :

Pattern action1 ; action2 ; … ; action n fichier 1 … fichier n : liste des fichiers de données en

entrées.

La commande exécute le programme, fichier par fichier sur chaque ligne de façon

séquentielle, ou s’il n’y a pas de fichier en entrée, elle prend le standard input en tant que

fichier d’entrée.

2. Pour des applications plus complexes

On prépare d’abord un fichier d’instruction AWK et l’exécution s’effectue par la

commande :

awk –f fichier_prog.awk fichier_trace.tr > fichier_resultat.tr

fichier_prog : est le fichier d’instructions AWK enregistré sous l’extension .awk

La commande exécute séquentiellement le programme se trouvant dans le fichier_prog

sur chaque ligne du fichier_trace.tr qui correspond au fichier trace obtenu après l’exécution

d’un script Tcl. Ensuite, le résultat sera affiché dans le fichier_resultat.tr.

B.4. Script AWK de calcul des métriques de performance

Les métriques de performance calculées à l’aide du langage AWK sont les suivantes :

Le nombre de messages de contrôle,

Le délai moyen de bout en bout,

L’énergie totale consommée dans le réseau.

BEGIN{

send_DYMO=0;

initialenergy =15;

E=0;

idHighestPacket = 0 ; idLowestPacket = 10000 ;

rStartTime = 1000.0 ; rEndTime = 0.0 ;

nSentPackets = 0 ; nReceivedPackets = 0 ;


128

rTotalDelay = 0.0 ;

}

{

strEvent = $1 ; rTime = $2 ; node = $3;

strAgt = $4 ;

idPacket =$6;

strType = $7 ;

#calcul du délai moyen de bout en bout

if (strType == "cbr" && strAgt == "AGT") {

if (strEvent == "s") {

nSentPackets += 1 ; rSentTime[ idPacket ] = rTime ;

if ( idPacket > idHighestPacket ) idHighestPacket = idPacket ;

if ( idPacket < idLowestPacket ) idLowestPacket = idPacket ;

}

if ( strEvent == "r") {

if ( rTime > rEndTime ) rEndTime = rTime ;

if ( rTime < rStartTime ) rStartTime = rTime ;

nReceivedPackets += 1 ;

rReceivedTime[ idPacket ] = rTime ;

rDelay[ idPacket ] = rReceivedTime[ idPacket ] - rSentTime[ idPacket] ;

}

}

}

{

#Pour le calcul du nombre de messages de contrôle pour AODV, il suffit de remplacer

#«DYMOUM» par «AODV»

if($1=="s"&& $7=="DYMOUM"){

send_DYMO++;

}

}

{

# Pour obtenir le nombre de nœuds

if($1=="nbr"){


129

n=$2;

}

}

{

# Calcul de l’énergie consommée

if ($1 == "r" || $1 == "d" || $1 =="s"|| $1=="f") {

node_id = $3

energy=$14

}

if ($1=="N"){

node_id = $5

energy=$7

}

finalenergy[node_id]=energy

}

END{

rTime = rEndTime - rStartTime ;

for ( i=idLowestPacket; ( i<idHighestPacket ); i+=1 )

rTotalDelay += rDelay[ i ] ;

rAverageDelay = rTotalDelay / nReceivedPackets ;

# Calcul de l’énergie consommé au niveau de chaque nœud

for (i in finalenergy) {

consumenergy[i]=initialenergy-finalenergy[i]

}

for (i=0; i<n; i++) {

E=E+consumenergy[i]

print("node",i, consumenergy[i])

}

printf"\n\nnombre de paquets de controle\t%d\n",send_DYMO;

printf"\n\nle delai moyen est de\t%f\n",rAverageDelay*1000;

printf"\n\nenergie totale consommée\t%f\n",E;

}

Annexe C. Installation et configuration du protocole DYMO

130

Annexe C

Installation et configuration du protocole

DYMO

C.1. Introduction

Pour notre implémentation nous avons choisi la dernière version disponible de DYMO

qui correspond à la version 3.0, nommée DYMOUM par son développeur principal Francisco

J. Ros. Le même code DYMOUM écrit en C et en C++ peut être utilisé sous Linux et NS2.

C.2. Etapes d’installation de DYMOUM

La version Linux

Pour l’installation de DYMOUM sous Linux il faut télécharger le package DYMOUM-

0.3.tgz à partir du site http://sourceforge.net/projects/dymoum/ et exécuter les étapes

suivantes :

$ tar zxvf dymoum-0.3.tgz

$ cd dymoum-0.3

$ make

$ make install # as root

La version NS2

Après avoir installé NS2 (Pour notre projet, nous avons installé la version ns-allinone-

2.29), il faut copier le package dymoum-0.3.tgz dans le répertoire ns-allinone-2.29/ns-2.29 et

exécuter les instructions suivantes :

$ cd ns-allinone-2.29/ns-2.29/

$ tar zxvf dymoum-0.3.tgz

$ ln -s ./dymoum-0.3 ./dymoum

$ patch -p1 < dymoum/dymoum_ns-2.29_v0.3.patch


131

$ ./configure

$ make distclean

$ ./configure

$ make

C.3. Configuration de DYMOUM

Une fois installé, DYMOUM peut être utilisé comme n’importe quel agent de routage

dans NS2, donc on peut utiliser la commande node-config pour attacher l’agent de routage aux

nœuds mobiles de la manière suivante :

$ns_ node-config -adhocRouting DYMOUM

Après la création des nœuds mobiles, on peut configurer tous les agents de routage

DYMOUM ensemble ou individuellement.

Les options de configuration de DYMOUM sont les suivantes :

debug_ : afficher les messages de débogage.

no_path_acc_ : désactiver la fonction d’accumulation du chemin.

reissue_rreq_ : tenter de nouvelles découvertes de routes après avoir échoué la première fois.

s_bit_ : Activer le S-bit de l’entête DYMO.

hello_ival_ : spécifie un intervalle entre les messages HELLO.

Remarque : Dans nos différents scripts Tcl, nous avons utilisé les paramètres par défaut.

Pour configurer tous les agents, il faut ajouter au script Tcl les commandes suivantes :

Agent/DYMOUM set debug_ true

Agent/DYMOUM set reissue_rreq_ false

Agent/DYMOUM set hello_ival_ 1

Pour configurer un seul agent, il faut ajouter les commandes suivantes:

set ra [$mobilenode agent 255]

$ra set reissue_rreq_ true

$ra set no_path_acc_ true

Après l’exécution du script Tcl, un fichier trace est obtenu en sortie. Le format d’un

fichier trace généré par DYMOUM est le suivant :


132

s 6.053808264 _15_ RTR --- 1 DYMOUM 48 [0 0 0 0] ------- [15:255 -1:255 1 0] [RE 0 0 28

10 0 1 21 0 0 [0 0 0 15 2]]

La ligne ci-dessus, indique que le nœud 15 a envoyé un paquet DYMOUM (avec une

taille de 48 bytes) qui désigne un message de routage «RE». Les informations spécifiques du

message DYMOUM sont indiquées à la fin de la ligne (à partir de «RE»). Les champs

correspondants sont les suivants :

Le bit m , le bit h , la taille , le ttl, le bit i , le bit a , l’adresse de destination, le numéro de

séquence de la destination et le nombre de saut.

Les informations entres crochets à la fin de la ligne représentent un bloc de routage avec

les champs suivants :

Le bit g, le préfixe, le nombre de saut, l’adresse du nœud dont les informations sont

accumulées et son numéro de séquence.

Remarque : Lorsque la fonction d’accumulation du chemin est activée, plusieurs blocs de

routage seront ajoutés au message de routage.

r 10.712966365 _2_ RTR --- 249 DYMOUM 32 [0 ffffffff 11 800] ------- [17:255 -1:255 1 0]

[RERR 0 0 12 10 0 [32 3]]

La ligne ci-dessus, indique que le nœud 2 à reçu un message RERR avec les champs

suivants :

le bit m, le bit h , la taille, le ttl et le bit i.

Le dernier bloc entre crochets contient les champs suivants :

l’adresse du nœud inaccessible et son numéro de séquence.

s 10.007533000 _1_ RTR --- 4 DYMOUM 28 [0 0 0 0] ------- [1:255 2:255 1 2]

[ECHOREPLY 8]

Lorsque le bit S est activé dans un message de type RREP (message de routage «RE»

avec le bit «A» désactivé), le nœud récepteur doit envoyer un paquet unicast au nœud

expéditeur. La ligne ci-dessus, illustre un message ECHOREPLY avec une taille de 8 bytes.

Documents

DYMO Multi chemins à nœuds disjoints sans …Distance Vector) protocol to illustrate its benefits for WSN. The multipath routing under interferences influence has been slightly addressed