Effets de la mobilité sur les protocoles de routage dans les réseaux ad hoc

:Venire de fm d'aude pour Mention

du diplume dingellieur kat ell illfunnatique

Dim BecayeaTeremcheiciat

SJTTaire

Introductiongénérale ....................................................................................1

Chapitre 1 : Les environnements mobiles..............................................................4

I. Introduction .............................................................................................4

II. Réseaux de mobiles et réseaux sans fil .............................................................4 III.Les principes de transmission radioélectrique......................................................6 IV. les défauts des transmissions radioélectriques...................................................6

IV. 1 l'Environnement du signale...............................................................6

IV.2 les Interférences.............................................................................6 V.les spécificités de la communication sans fil........................................................8

VI. Classifications des réseaux sans fil.................................................................9

VI. 1 Classifications suivant la portée des unités mobiles........................................9 VI.1-1 Réseaux personnels sans fil ou WPAN...................................................9 VI. 1 -2Réseaux locaux sans fil ou WLAN (Wireless Local Area Network)................11 V.1-3 Réseau métropolitain sans fil ou WMAN(Wireless Metropolitan Area Network). 13

VI.2. Classification suivant l'infrastructure...........................................................20

VII. Conclusion...........................................................................................30 Chapitre 2 : Etude des protocoles de routage dans les réseaux Ad hoc.... .......................31 I.Introduction..............................................................................................31

II. Routage dans les réseaux Ad Hoc..................................................................32

II.1Modes de communication dans les réseaux Ad Hoc..................................... 32

II.2. Les protocoles de routage dans les réseaux Ad Hoc........................................32

II.2.1 Les protocoles de routage proactif........................................................33 II.2.1.1 Le protocole de routage DSDV................................................. 36 II.2.1.2 Le protocole de routage OLSR......................................................37

II.2.2 Les protocoles de routage réactifs.........................................................39 II.2.2.1 Le protocole de routage DSR.........................................................40 II.2.2.2 Le protocole de routage AODV......................................................43

II.2.3 Les protocoles de routage hybrides.......................................................46 II.2.3.1 Le protocole de routage ZRP.........................................................47 II.2.3.2 Le protocole de routage CBRP.......................................................48

III. Conclusion............................................................................................50

Chapitre 3 : Les modèles de mobilité dans les réseaux ad hoc.....................................52

I. Introduction............................................................................................52

II. Les modèles individuels .............................................................................52

II.1 Les modèles sans mémoire......................................................................52 II.1.1 Random Walk(RW).........................................................................52 II.1.2 Random Waypoint(RWP)............................................................. 53 II.1.3 Random Direction(RD).....................................................................55 II.1.4 Restricted Random Waypoint.............................................................55

II.2 Les modèles avec mémoire.....................................................................56 II.2.1 Boundless....................................................................................56 II.2.2 Gauss Markov ...............................................................................57 II.2.3 Markovian Random Path ..................................................................59 II.2.4 City Section (CS)............................................................................60 II.2.5. Le modèle de mobilité avec obstacles...................................................61

III. Les modèles de groupe ..............................................................................63 III.1. Le modèle exponentiel aléatoire corrélé.....................................................63 III.2. Modèle de mobilité de colonne ...............................................................63 III-3. Le modèle de mobilité de communauté nomade (NCMM)...............................64 III-4. Le modèle de mobilité de poursuite..........................................................65 III-5. Le modèle de mobilité d'un groupe avec point de référence(RPGM)...................66

IV. Discussions sur les modèles de mobilité..........................................................67 V. Conclusion.............................................................................................69

Chapitre 4 : Simulation et interprétation des résultats...............................................70

I. Introduction.............................................................................................70

II. Environnements de simulation......................................................................70

II.1 Définitions et concepts ..........................................................................70

a. Système discret et système continu ...........................................................70

b. Simulation par événement discret ............................................................71

c. Simulateur .......................................................................................71

d. Intérêt de la simulation ........................................................................71

II.2 les simulateurs ...................................................................................72
II.3 Philosophie de NS2 .............................................................................73
a. Le langage TCL (Tool Command Language) ..............................................73

b. le OTcl ............................................................................................74

II.4 Script de simulation et Spécifications de nos implémentations ...........................76 II.2.1.Le Simulateur................................................................................76 II.4.2Le Scheduler (Planificateur d'événements)...............................................76 II.4.3 Architecture du réseau......................................................................77

a. N°ud .........................................................................................77

b. Lien...........................................................................................77

c. Les Agents ...................................................................................77

d. La gestion de la file d'attente .............................................................77 II.4.4 Spécification de nos implémentations....................................................78 II.5 Visualisation et extractions des résultats...................................................80

II.5.1 Visualisation ..............................................................................80

II.5.2 Le traceur..................................................................................81

III Simulation et interprétation des résultats .........................................................84

III.1 Les facteurs de simulation .....................................................................84

III.2 Les métriques mesurées........................................................................84 III.2.1 Packet Delivery Fraction (PDF)..........................................................84 III.2.2. Average End to End Delay (AVG)......................................................85 III.2.3 Le Normalized Routing Load (NRL)....................................................85

III.3. Simulation du OLSR ...........................................................................85 III.3.1. Variation de la vitesse.....................................................................86 III.3.2. Variation du temps de pause.............................................................88

III.4 Simulation du AODV ..................................................................89

III.4.1. Variation de la vitesse ..................................................................89

III.4.2. Variation du temps de pause .......................................................91 IV. Conclusion ...........................................................................................92 Conclusiongénérale......................................................................................94 Référence bibliographique et annexes.................................................................96

Liste des Tableaux et Figures

Tableau 1.1 : Exemple de réseau mobile et/ou sans fil ............................................5 Tableau 1.2 : Les principales évolutions de la norme 802.11 ...................................12 Tableau 1.3 : Les Générations des réseauxcellulaires ..............................................20

Figure1.1 : FDMA .................................................... .............................. 7 Figure1.2 : TDMA ......................................................................................7 Figure1.3 :CDMA .......................................................................................8 Figure 1.4 : Schéma de connexion de terminaux Bluetooth .....................................10

Figure 1.5 : Réseaux cellulaires ......................................................................14 Figure 1.6 : Composants d'un réseau GSM .......................................................15 Figure 1.7 : Fractionnement des cellules en zones dans la technologie UMTS ...............17 Figure1.8 : Le modèle des réseaux mobiles avec infrastructure. ...................... 21 Figure 1.9 : Exemple de réseaux ah doc ............................................................22

Figure 1.10 : Noeud caché dû à la distance .......................................................24 Figure 1.11 : Noeud caché dû à un obstacle .......................................................24 Figure 1.12 : Problème des noeuds exposés .......................................................25

Figure 1.13 : Le backoff et le defering ............................ ............... ............... 26 Figure 1.14 : Exemple de variation du backoff ...................................................27 Figure 1.15 : Mise à jour du Network Allocation Vector (NAV).................................28

Figure 1.16 : Configuration où l'EIFS est nécessaire ............................................29 Figure 1.17 : l'Extended Inter Frame Spacing IEFS ................................................29 Figure 2.1 : Modes de communication dans les réseaux mobiles ...............................32 Figure 2.2 : Exemple d'utilisation du DBF .........................................................34 Figure 2.3 : Mises à jour après coupure de lien dans DBF ......................................35 Figure 2.4 : Diffusion par inondation et diffusion optimisée ....................................38 Figure 2.5 : La découverte de chemins dans le DSR ...........................................42 Figure 2.6 : Les deux requêtes RREQ et RREP utiisées dans le protocole AODV ..........45 Figure 2.7 : Exemple de zone IARP dans ZRP ................................................48 Figure 2.8 : L'organisation du réseau dans le CBRP .............................................49

Figure 3.1 : Random Walk (Voyage pendant un temps de t s) ...................... 53

Figure 3.2 : Random Walk (Déplacement d'une distance d) ......................... 53 Figure 3.3 : Random Waypoint ....................................................................54 Figure 3.4 : Random Direction .....................................................................55

Figure 3.5 : Restricted RWP ............................................................... 56 Figure3.6 : Boundless................................................. .............................. 56 Figure 3.7 : Changement de la valeur moyenne d'angle ...........................................58 Figure3.8 : Gauss Markov ............................................................................58 Figure 3.9 : Schéma de passage pour le Markovian Random Path................................59 Figure 3.10 : Markovian Random Path................................................................60 Figure3.11 : City ............................................................. .........................61

Figure 3.12 : Mouvements avec obstacles utilisant le diagramme de vornoï.......... 62
Figure 3.13 : Movement des noeuds utilisant le modèle Column ............................. 64

Figure3.14 : Column...................................................................................64 Figure 3.15 Nomadic Community.....................................................................65 Figure.3.16 : Modèle de mobilité de communauté nomade...................................... 65 Figure3.17 : Purse ......................................................................................66 Figure 3.18 : Mouvements de 3 n°uds utilisant le modèle RPGM ..............................67 Figure 4.1 : Topologie de la section de ville considérée ...........................................80 Figure.4.2 : Network AniMator (NAM)..............................................................82 Figure 4.3 : OLSR_vitesse_AVG.....................................................................86 Figure 4.4 : OLSR_vitesse_NRL.............................................................. 86 Figure 4.5 : OLSR_vitesse_PDF.......................................................................87 Figure 4.6 : OLSR_temps de pause_AVG............................................................88 Figure 4.7 : OLSR_temps de pause_NRL............................................................88 Figure 4.8 : OLSR_temps de pause_PDF.............................................................89 Figure 4.9 : AODV_vitesse_AVG.....................................................................90 Figure 4.10 : AODV_vitesse_NRL....................................................................90 Figure 4.11 : AODV_vitesse_PDF ..................................................................90 Figure 4.12 : AODV_temps de pause_AVG.........................................................91 Figure 4.13 : AODV_temps de pause_NRL..........................................................92 Figure 4.14 : AODV_temps de pause_NRL..........................................................92

Remerciements

Implémenté des modèles de mobilité des noeuds dans les réseaux Ad hoc est une entreprise longue et périlleuse. Nous ne saurions aboutir ce projet si ce n'est des conseils, des aides, des consolidations de la part des personnes qui sont, désormais, gravé à jamais dans notre mémoire.

Nous remercions tous les enseignants de l'UMMTO qui nous ont formé durant tout ce cycle d'ingénieur, La réussite de ce projet est dû, essentiellement, au savoir qui nous a été inculqué les années précédentes.

Nous remercions particulièrement les enseignants qui nous ont conseillé et diriger vers le droit chemin quand il le fallait.

Nous remercions tous nos camarades avec qui nous avons surmonté les problèmes dus à l'environnement de simulation.

Nous remercions également tous les anciens étudiants de l'université pour leurs aides.

Nous remercions Mr Tayeb pour avoir accepter d'être notre promoteur au sein du département et les membres du jury de soutenance qui ont accepté de juger ce travail.

INTRODUCTION GENERALE

Vu les avancées fulgurantes que connaît le monde informatique, nous assistons aujourd'hui à l'émergence de nouveaux appareils qui ont la particularité d'être mobiles, tels que les téléphones portables, les ordinateurs portables, les équipements GPS (Global Positionning System) et les PDAs (Personal Digital Assistant). Dans un souci d'établir des échanges d'information entre les utilisateurs possédant ces dispositifs mobiles, les réseaux sans fil voient le jour.

Les environnements mobiles offrent aujourd'hui une grande flexibilité d'emploi. Particulièrement, ils permettent la mise en réseau des sites dont le câblage serait trop onéreux à réaliser dans leur totalité, voire même impossible. Cette impossibilité est due au fait que les appareils mobiles changent constamment leurs emplacements. On cite l'exemple du projet hollandais NAFIN (Netherlands Armed forces Integrated Network), qui a visé d'améliorer les performances des forces militaires de l'air et de la mer, en intégrant la technologie des réseaux sans fil.

Contrairement à l'environnement statique, l'environnement mobile permet aux unités de calcul une libre mobilité et ne pose aucune restriction sur la localisation des usagers. La mobilité engendre des problèmes propres à l'environnement mobile : perte fréquente de connexion, un faible débit de communication et des ressources modestes et une capacité d'énergie limitée pour les mobiles.

Les réseaux sans fil peuvent être classifiés en deux catégories : les réseaux sans fils avec infrastructures, appelés parfois les réseaux cellulaires, et les réseaux sans infrastructures, appelés aussi réseaux ad hoc. Parmi les systèmes utilisant le modèle cellulaire, nous pouvons citer les réseaux GSM (Global System for Mobile) utilisé dans la téléphonie. Ces types de réseaux, requièrent d'importantes infrastructures logistiques et matérielles fixes telles que les stations de base.

Un inconvénient des réseaux cellulaires est qu'une fois le mobile n'a pas de station de base à sa portée, il ne pourra plus se connecter. Par contre dans les réseaux ad hoc cette contrainte est prise en compte. Dans ces réseaux, nous n'avons plus de notion de station de base, mais c'est les n°uds intermédiaires qui servent de passerelles ou de relais pour les autres n°uds mobiles du réseau. Un réseau ad hoc peut être défini comme étant une collection d'entités mobiles interconnectées par une technologie sans fil formant un réseau temporaire sans l'aide de toute administration centralisée ou de tout support fixe. Les réseaux ad hoc sont très utilisés dans le

domaine militaire. Du fait que le rayon de propagation des transmissions des hôtes soit limité, et afin que le réseau ad hoc reste connecté, il se peut qu'un hôte mobile se trouve dans l'obligation de demander de l'aide à un autre hôte pour pourvoir communiquer avec son correspondant qui peut être hors de sa portée de communication. Cette caractéristique parmi d'autres constitue la puissance des réseaux ad hoc. Cependant, un problème majeur dans les réseaux ad hoc est de trouver les routes optimales et fiables entre les n°uds mobiles.

En effet, le problème du routage dans les réseaux ad hoc est le défi le plus difficile à réaliser, car il s'agit de trouver une route optimale multi-sauts qui relie deux n°uds quelconques du réseau. Ce routage est donc un problème d'optimisation sous contraintes. Parmi ces contraintes, on cite les changements de topologies et la volatilité des liens, la capacité limitée de la bande passante, etc. La longueur du chemin entre un n°ud source et un n°ud destination peut ne pas être la seule métrique à optimiser. L'optimisation peut consister à une combinaison complexe de facteurs tels que le délai de bout en bout, la fiabilité et stabilité des liens, la durée de vie du chemin, la bande passante disponible sur les liens, le niveau d'énergie dans les batteries, etc.

La satisfaction de toutes ces contraintes rend difficile la conception d'un protocole de routage pour les réseaux ad hoc. De nos jours, plusieurs solutions ont été proposées dans la litt érature qui sont parfois très distinctes, ce qui rend difficile leur classification. On peut citer trois grandes familles de protocoles, à savoir les protocoles proactifs, réactifs et hybrides.

Les protocoles proactifs ont un mode de fonctionnement similaire à celui des réseaux filaires. Leur inconvénient majeur est la périodicité de leurs tâches et échouent face à des réseaux de grande taille et trop dynamiques.

Par contre, les protocoles réactifs englobent des algorithmes qui peuvent s'adapter aux conditions des réseaux avec un minimum de surcharge occasionnée.

Les protocoles hybrides combinent les avantages des deux approches réactive et proactive pour créer de nouveaux protocoles capables de faire face à la complexité des réseaux mobiles ad hoc.

Dans ce mémoire, nous nous sommes intéressé à l'impact de la mobilité des n°uds sur le fonctionnement général d'un protocole de routage d'un réseau ad hoc. Pour cela, nous avons effectué une évaluation de cet impact sur deux protocoles représentant chacun l'une des deux classes : proactive et réactive.

Ce mémoire est composé de quatre chapitres :

Dans le premier chapitre, nous faisons une étude des environnements sans fils où nous nous focalisons sur les réseaux ad hoc. Nous présentons les caractéristiques de plusieurs réseaux sans fil et les différences structurelles qui existent entre ces derniers.

Dans le deuxième chapitre nous étudions le routage dans les réseaux ad hoc en détaillant le fonctionnement de quelques protocoles proposés par l'IETF appartenant aux familles : réactive, proactive et hybride.

Dans le troisième chapitre, nous présentons les différents modèles de mobilité pour les n°uds d'un réseau ad hoc. Pour chaque modèle, nous expliquons le mode de fonctionnement et donnons quelques exemples classiques d'utilisation.

Dans le quatrième chapitre nous faisons une présentation du simulateur NS-2, la méthodologie qui a été utilisée pour nos simulations et enfin nous faisons une présentation des résultats obtenus avec l'interprétation de ces derniers.

Nous terminerons par une conclusion générale et quelques perspectives.