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.

CHAPITRE I : LES ENVIRONNEMENTS MOBILES

I Introduction

L'évolution rapide de la technologie dans le domaine de la communication sans fil, a permis aux usagers munis d'unités de calcul portables d'accéder à l'information indépendamment des facteurs : temps et lieu. Ces unités, qui se communiquent à travers leurs interfaces sans fil, peuvent être de diverses configurations : avec ou sans disque, des capacités de sauvegarde et de traitement plus ou moins modestes et alimentés par des sources d'énergie autonomes (batteries). L'environnement de calcul résultant est appelé environnement mobile. Cet environnement n'astreint plus l'usager à une localisation fixe, mais lui permet une libre mobilité tout en assurant sa connexion avec le réseau [Bad98].

Les environnements mobiles permettent une grande flexibilité d'emploi. En particulier, 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 (par exemple en présence d'une composante mobile). L'environnement mobile offre beaucoup d'avantages par rapport à l'environnement habituel. Cependant de nouveaux problèmes peuvent apparaître (le problème de routage par exemple), causés par les nouvelles caractéristiques du système. Les solutions conçues pour les systèmes distribués avec uniquement des sites statiques, ne peuvent pas donc être utilisées directement dans un environnement mobile. De nouvelles solutions doivent être trouvées pour s'adapter aux limitations qui existent, ainsi aux facteurs qui rentrent dans le jeu lors de la conception.

Ce chapitre a pour but de présenter l'environnement mobile, et les principaux concepts liés à ce nouvel environnement. Le chapitre introduit la technologie de communication sans fil utilisée par les réseaux mobiles; pour cela nous détaillons quelques principales notions nécessaires à la compréhension de ces systèmes. Le modèle de l'environnement étudié, dans ce chapitre, n'exclue pas l'existence d'une infrastructure préexistante (un ensemble de stations liées par un réseau filaire) puisque l'esprit de la communication est la même pour tous les réseaux mobiles.

II Réseaux de mobiles et réseaux sans fil

Les termes mobile et sans fil sont souvent utilisés pour décrire les systèmes existants, tels que le GSM, IS-95, IEEE 802.11, Bluetooth, etc. Toutefois, il est important de distinguer les deux catégories de réseaux que regroupent les concepts de mobile et de sans fil, de façon à éviter toute confusion [APV01].

Les réseaux de mobiles : Un utilisateur mobile est défini théoriquement comme un utilisateur capable de communiquer à l'extérieur de son réseau d'abonnement tout en conservant une même adresse. Les différents protocoles de signalisation à l'oeuvre dans les réseaux étant peu compatibles entre eux, on a souvent recours, pour pallier ce handicap, à des mécanismes de transcription de la signalisation de l'utilisateur pour l'adapter au réseau visiteur.

Les réseaux sans fil : Le concept de sans fil est étroitement associé au support de transmission. Un système est dit sans fil s'il propose un service de communication totalement indépendant de prises murales. Dans cette configuration, d'autres moyens d'accès sont exploités, tels que l'infrarouge ou les ondes hertziennes. Ces différentes interfaces ne sont toutefois pas sans faire naître de nouvelles difficultés.

Prenez l'exemple du téléphone sans cordon de résidence, DECT. Ce téléphone donne accès au RTC (réseau téléphonique commuté), le réseau classique du téléphone, ou au RNIS (Réseau numérique à intégration de services). Le support de communication utilise l'interface radio pour qu'un abonné puisse appeler depuis son jardin ou sa cuisine, mais ce dernier doit toujours rester au voisinage de son réseau d'abonnement. En cas de mobilité dépassant ces limites, l'utilisateur est contraint de contacter un opérateur local pour souscrire un nouvel abonnement.

Bien entendu, certains systèmes tels que le GSM offrent la mobilité et le sans-fil simultanément.

Le tableau 1.1 présente des exemples de réseaux acceptant des services << sans fil >>, << mobile >> ou les deux à la fois.

Système	Sans fil	mobile
GSM	Oui	Oui
IS95	Oui	Oui
UMTS	Oui	Oui
TCP/IP	Non	Non
IP Mobile	Non	Oui
ATM	Non	Non

Tableau 1.1 : exemple de réseau mobile et/ou sans fil

III Les principes de transmission radioélectrique

Découvert par le physicien allemand Heinrich Hertz en 1887, les ondes radioélectriques, support capital de la transmission sans fil sont basés sur le principe suivant :

L'accélération d'un électron crée un champ électromagnétique qui à son tour accélère d'autres électrons et ainsi de suite. Il est alors possible de provoquer le déplacement électromagnétique. Plus le nombre d'électrons déplacés est important, plus le signal est fort et plus sera grande sa portée, avec une vitesse proche de celle de la lumière [Tis99]. Un déplacement coordonné d'électrons peut alors servir pour le transfert d'information et constitue la base de la communication sans fil. L'approche standard de la transmission radio est le déplacement des électrons à une fréquence donnée. Des techniques de modulation et de multiplexage permettent d'adapter les signaux transmis, la bande passante du support de communication et de rentabiliser son utilisation.

IV les défauts des transm issions radioélectriques

Les modes de transmissions filaires fournissent des supports de transmissions, pour lesquels la théorie définit des modèles qui permettent de prévoir les défauts, parce que l'on sait contrôlé l'environnement. Cependant, la nature hertzienne et incontrôlable des liens de transmissions sans fil pose problème.

IV.1 l'Environnement du signale

Avec la transmission hertzienne, Les sources de perturbation du signal sont connues, leurs effets également. La transmission a lieu dans un milieu ouvert dans lequel les sources de perturbation se déplacent, chacune avec sa propre loi, à titre d'exemple les ondes crée par les orages peuvent brouiller le signal, le vent le fait bouger. A ceci peut s'ajouter les différents obstacles sur lesquels réfléchissent les ondes radioélectriques, par exemple le sol, les voitures. Nous tenons à mentionner que malgré les difficultés rencontrées grâce à la réflexion du signal, celle-ci peut avoir une contribution positive sur le bon acheminement de l'information.

IV.2 les Interférences

Dans la communication radiofréquence, une unité désirant entrée en communication utilise une fréquence radio. L'exploitation de la même fréquence radio, en même temps, par différentes unités conduit à une interférence, bien entendu, dans le cas où les unités se

trouvent l'un à la portée de l'autre. Pour palier à ce problème, une solution facile serait d'attribuer à chaque unité une bande de fréquence différente. Par défaut de la ressource bande de fréquence, cette solution limite considérablement le nombre d'abonné du réseau, ce qui n'est pas économique pour les opérateurs. Une autre solution consiste, notamment dans le radio téléphone cellulaire, à attribuer la fréquence à la demande. Une unité mobile, avant d'entamer une communication, demande un canal qui lui sera attribué en fonction de la saturation du réseau, une fois la transmission finie, le canal sera libéré.

Face au nombre croissant de demande d'abonnement dans les réseaux cellulaire, d'autres technique ont vue le jour : FDMA, TDMA et le CDMA.

- FDMA (Frequency Division Multiple Access) le spectre de fréquence est divisé en

plusieurs sous bandes qui sont chacune placée sur une fréquence spécifique du canal

(porteuse ou carrier), chaque porteuse ne peut transporter que le signal d'un seul

utilisateur (Voir figure 1.1).

- TDMA (Time Division Multiple Access) où la totalité de la bande de fréquences est offert à chaque utilisateur pendant un intervalle de temps (slot). (Voir figure 1.2)

- CDMA (Code Division Multiple Access) ou accès multiple par répartition de codes. En CDMA, les utilisateurs peuvent communiquer simultanément dans une même bande de fréquence. La distinction entre les différents utilisateurs s'effectue alors grâce à un code qui leur est attribué et connu exclusivement par l'émetteur et le récepteur. (Voir figure 1.3)

Figure 1.3 : CDMA

V. V les spécificités de la communication sans fil

Après les problèmes dus à la nature radiofréquence du lien de communication, l'opportunité donnée à l'utilisateur, celle de pouvoir communiquer là où il veut et quant il veut, ne vas pas sans Solutionner ceux posés par la mobilité.

· Mobilité

L'utilisateur des réseaux sans fil a la possibilité de se déplacer dans le réseau tout en gardant la même adresse, il peut accéder aux services offert par le réseau de n'importe où et à n'importe quel moment. Cela nécessite d'une part des mécanismes de localisation de l'utilisateur, et d'autre part une assurance de la continuité des communications en cours de déplacement (handover).

· Autonomie

Les unités mobiles ont une contrainte liée à la durée de vie des batteries, il faut économiser autant que possible les transmissions inutiles. Heureusement qu'actuellement les nouvelles technologies de mobiles présentent des durées plus importantes offrant aux mobiles une autonomie plus importante.

· Débit et portée faible

L'une des limites de la communication sans fil vient de la relative faiblesse de la bande passante des technologies utilisées. Plusieurs facteurs limitent la portée d'une transmission sans fil, comme la faible puissance du signal, les obstacles qui empêchent, atténuent, ou réfléchissent les signaux.

· Non sécurisé

Les réseaux sans fil offrent de nouvelles failles aux pirates. De part la nature immatérielle du support physique, l'écoute clandestine sur un réseau sans fil est facile. Il faut donc protéger l'accès aux ressources sans fil et aux informations qui circulent dans les trames. Les systèmes mobiles sont généralement équipés de processeurs moins puissants que les machines fixes, et ne peuvent se permettre d'effectuer de longs calculs demandés par les systèmes de cryptographie. L'énergie de la batterie est une ressource rare et pose également des problèmes de sécurité.

VI. Classifications des réseaux sans fil

Plusieurs technologies de réseaux sans fil existent qui se distinguent par la fréquence d'émission utilisée, le débit, la portée des transmissions et même le mode de fonctionnement. Plusieurs classifications peuvent être défini suivant ces caractéristiques. Dans le cadre de se mémoire, nous étudions deux de ces classifications à savoir : la classification selon la portée des sites et selon l'infrastructure utilisé.

VI.1 Classifications suivant la portée des unités mobiles

Il existe plusieurs technologies qui se distinguent d'une part par la fréquence d'émission utilisée mais également par le débit et la portée des transmissions.

C'est d'ailleurs cette dernière caractéristique qui permet de classer les réseaux sans fil, à l'instar des réseaux filaires, selon 4 grandes classes. Celles-ci sont donc définies en fonctions du périmètre géographique offrant une connectivité, plus communément appelées zone de couverture.

VI.1-1 Réseaux personnels sans fil ou WPAN

Le réseau personnel sans fil, WPAN (Wireless Personal Area Network) concerne les réseaux sans fil d'une faible portée : de l'ordre de quelques dizaines de mètres. Ce type de réseau sert généralement à relier des périphériques (imprimante, téléphone portable, appareils domestiques, ...) ou un assistant personnel (PDA) à un ordinateur sans liaison filaire ou bien à permettre la liaison sans fil entre deux machines très peu distantes.

Il existe plusieurs technologies utilisées pour les WPAN :

Norme créée en 1994 par Ericsson et validé sous le nom de IEEE 802.15.1 (IEEE : Institute of Electrical and Electronics Engineers), un de ses points forts est l'utilisation de petits composants utilisant de faibles puissances ce qui la rend particulièrement adapté à une utilisation au sein de petits périphériques.

Le standard Bluetooth se décompose en différentes normes :

· IEEE 802.15.1 définit le standard Bluetooth 1 .x permettant d'obtenir un débit de 1 Mbit/sec pour une portée de quelque dizaine de mètres ;

· IEEE 802.15.2 propose des recommandations pour l'utilisation de la bande de fréquence 2.4 GHz (fréquence utilisée également par le WiFi) ;

C'est une technologie peu onéreuse, grâce à la forte intégration des composants électroniques sur une puce unique de 9x9 mm. Les fréquences utilisées sont comprises entre 2400 et 2483,5 MHz (Cette bande ne demande pas de licence d'exploitation) avec un Débit de 1 Mbits/s théorique (730 Kbits/s réel) et une Portée d'au maximum 50m [APV01].

Un réseau WPAN construit à base de la technologie Bluetooth est appelé piconet, est formé d'un maître et de sept esclaves au plus. Le maître gère la communication au sein du piconet. Plusieurs piconets reliés entre eux forment ce qu'on appel scatternet.

La Figure 1.4 [APV01] montre qu'un noeud peut être esclave dans plusieurs piconets, comme il peut être maître d'un piconet et esclave dans un autre piconet.

Maître

Piconet 1

Esclave du piconet 1 et du piconet 2

Piconet 2

Maître du piconet 3 et Esclave du piconet 2

Piconet 3

Figure 1.4 : Schéma de connexion de terminaux Bluetooth

· Zigbee

Initiée par Motorola et ratifiée en août 2003 sous la norme IEEE 802.15.4 [IEE03].

Il Permet d'obtenir des liaisons sans fil à très bas prix et avec une très faible consommation d'énergie (fonctionnement de six à vingt-quatre mois avec une paire de piles AA). Particulièrement adaptée pour être directement intégré dans de petits appareils électroniques, capables d'opérer plusieurs mois sur batterie et de se relier ensemble en réseau (appareils électroménagers, hi-fi, jouets, ...) il est utilisé pour le repérage des menaces sur un champ de bataille, le relevé de compteurs, la climatisation "intelligente", la détection de risques d'incendie, ...

Sa transmission se fait dans la bande des 2.4 GHz globalement mais également 915 MHz en Amérique et 868 MHz en Europe, avec un Débits de 250 Kbits/s à 2.4 GHz (10 canaux), 40 Kbits/s à 915 MHz (6 canaux) et 20 Kbits/s à 868 MHz (1 canal), une Portée de 10 à 75 m selon la puissance utilisée, la géographie des lieux et les caractéristiques environnementales et une Interconnexion théorique de 255 matériels par réseau.

· Infrared data Association

IrDA (InfraRed Data Association) est un organisme à but non lucratif crée en 1993, fondé pour promouvoir les standards de communication point à point basés sur l'infrarouge. Il est Utilisé principalement pour l'échange d'informations entre outils communicants tels que les téléphones mobiles, les assistants personnels ou les ordinateurs portables.

Il utilise un Débits de 15,2 Kbits/s (version 1.0) et jusqu'à 4 Mbits/s (version 1.1), avec un Portée de 2 m en mode unidirectionnel.

VI.1-2 Réseaux locaux sans fil ou WLAN (Wireless Local Area Network)

Le réseau local sans fil, WLAN (Wireless Local Area Network) est un réseau permettant de couvrir l'équivalent d'un réseau local d'entreprise, soit une portée d'environ une centaine de mètres. Il permet de relier entre eux les terminaux présents dans la zone de couverture. Il existe plusieurs technologies concurrentes :

· Wifi

Norme publiée en juin 1997 par l'IEEE sous le nom de IEEE 802.11, soutenue par l'alliance WECA (Wireless Ethernet Compatibility Alliance), elle est basée sur une topologie cellulaire (au même titre que GSM ou UMTS) et permet de répondre à deux catégories d'architecture :

le mode Ad Hoc (point à point) et le mode Infrastructure (architecturé autour d'un point d'accès).

Le 802.1 1b a une transmission dans la bande des 2.4 GHz, un debit de 11 Mbits/s théorique, une portée de 100 m pour 10 mW, avec une modulation DSSS.

Le 802.1 1a (ou Wi-Fi 5) a une transmission dans la Bande des 5 GHz, un débit de 54 Mbit/s théoriques, une portée de 100 m pour 10 mW avec une modulation OFDM.

Le 802.1 1g a une transmission dans la Bande des 2.4 GHz, un débit de 54 Mbit/s théoriques, une portée : 100 m pour 10 mW, avec une modulation DSSS.

Le tableau suivant [GAS02] [Müh02] résume les principales évolutions de la norme 802.11.

Norme	Débits		Bandes de Fréquence	802.11
1Mbp/s 2Mbp/s	2.4GHz		802.11b
5.5 Mbp/s 11 Mbp/s	2.4 GHz		802.1 1a
Plus de 54 Mbp/s	5 GHz		802.1 1g
Plus de 54 Mbp/s	2.4 GHz

Tableau 1.2 : Les principales évolutions de la norme 802.11

· HiperLan (High Performance Radio LAN, versions 1 et 2)

HiperLAN (High Performance Radio LAN) est un standard européen initié par l'ETSI (European Telecommunications Standards Institute) en 1998, il est composé de 2 normes wireless de haut débit : HiperLAN1 [ETS98] et HiperLAN2 [ETS00]. Il a comme inconvénient de n'avoir aucun soutien pour le marché américain. Il a une transmission dans la Bande des 5 GHz, une modulation OFDM et une sécurité DES. HiperLAN 1 est pour les réseaux en mode Ad Hoc uniquement, avec un débit de 20 Mbits/s théorique. HiperLAN 2 est pour les réseaux en mode Infrastructure uniquement, avec un débit de 54 Mbits/s théorique.

· HomeRF

Lancée en 1998 par le HomeRF [NSL00] (Home Radio Frequency) Working Group, formé notamment par les constructeurs Compaq, HP, Intel, Siemens, Motorola et Microsoft, Cette technologie met en avant ses petits prix et sa facilité de mise en °uvre, elle Utilise la norme

DECT pour réaliser le transfert de la voix (protocole TDMA) et la norme 802.11 pour le transfert de données (CSMA/CA), elle permet de fournir de multiples canaux de voix de bonne qualité.

Elle utilise des architectures en modes Ad Hoc et Infrastructure, une transmission dans la bande des 2.4 GHz, un débit de 1,6 Mbits/s pour HomeRF1 ou 10 Mbits/s pour HomeRF2, avec une portée de 50 à 100 m, une modulation FHSS et une sécurité de Chiffrement à l'aide d'une clé de 128 bits.

VI.1-3 Réseau métropolitain sans fil ou WMAN (Wireless Metropolitan Area Network)

Ces réseaux sont connus sous le nom de Boucle Local Radio ou BLR [APV01]. En télécommunication, la boucle locale est la partie du réseau qui relie le terminal de l'utilisateur à un équipement de l'opérateur. La boucle locale radio n'est autre que la boucle locale dans laquelle le lien de communication entre l'utilisateur et le premier équipement de l'opérateur utilise des Ondes radios.

Dans ces systèmes, une antenne, qui couvre 3 à 15 km, est placée haut en vue directe avec des petites antennes installées chez les clients.

Parmi les technologies utilisées par les WMAN on peut citer :

· LMDS (Local Multipoint Distribution Service)

Le LMDS [APV01] est une technologie cellulaire "Point à multipoint": un émetteur central dessert un nombre élevé d'abonnés. Les systèmes LMDS modernes offrent une portée d'environ 5 à 6 km et utilisent des fréquences supérieures à 20 GHz. Ils autorisent des transmissions bidirectionnelles symétriques dotées de débits allant de 64 kbits/s à plusieurs Mbits/s, ainsi que la transmission de la voix. L'émetteur se présente sous la forme d'une tour bardée d'antennes, assez similaires aux antennes GSM. L'équipement de l'abonné se résume à une petite antenne (environ 25 cm de diamètre). Selon les constructeurs (Alcatel, Lucent, Nortel...), cet équipement fournit un débit maximal de 8 à 10 Mbits/s en voie montante et descendante sous la forme d'un bouquet de service voix et données. Un système comme Evolium LMDS, d'Alcatel, permet de raccorder jusqu'à 4000 utilisateurs sur le même concentrateur radio. Le débit agrégé du système s'élève à 155 Mbits/s en mode bidirectionnel (Full Duplex). Evolium LMDS effectue une allocation dynamique des ressources pour répartir, de façon optimale, la bande passante en fonction des besoins. Les débits peuvent s'améliorer lors des téléchargements, par exemple.

Les interfaces de transmission sur le LMDS ont été étudiées dans différents cadres : · La norme DAVIC d'origine américaine du groupe DAVIC qui est la plus utilisée,

· La norme DVB d'origine européenne issue des travaux du groupe DVB, qui est moins utilisée au niveau de la BLR mais plutôt utilisée au niveau des satellites.

· IEEE 802.16 [IEE03]

Alias WiMax, nouvelle norme développée pour offrir des réseaux sans fil longue distance et haut-débits. Basée sur des fréquences allant de 2 à 10GHz, il pourra offrir un débit allant jusqu'a 130 Mbitp/s. En pratique on pourra avoir un débit de 70 Mbitp/s (par secteur radio et par canal de 20MHz) sur une couverture d'une dizaine de kilomètres. WiMax devrait permettre l'extension des connexions Internet haut-débit aux zones non couvertes par l'ADSL

VI.1-4 Réseaux étendus sans fil ou WWAN (Wireless Wide Area Network)

Les réseaux étendus sans fil ont connu un essor sans précédent dans le monde de la technologie. Ils sont basés sur le système cellulaire et concerne le radiotélephone. Le système cellulaire subdivise la zone de couverture du réseau en sous zone appelé cellule, Chaque cellule est couverte par une station de base qui fait office d'intermédiaire entre les terminaux de la cellule et reste du réseau. Les stations de base utilisent les ondes hertziennes comme boucle local. De ce fait, deux stations de base adjacentes doivent utiliser des fréquences différentes pour parer au problème d'interférence.

La figure 1.5 [HYB05] illustre l'architecture cellulaire et la réutilisation de la fréquence.

Il existe plusieurs générations selon l'évolution du mode de communication et plusieurs normes.

F5 F2 F3 F7 F1 F4

F4 F6 F5
F7 F1

Figure 1.5: Réseaux cellulaires

Standards Européens

· GSM (Global System for Mobile communication)

C'est en 1982, lors de la Conférence Européenne des Postes et Télécommunications (CEPT) que fut créé le Groupe Spécial Mobile (GSM). Celui-ci avait pour objectif de spécifier un système de normes européennes pour les radiocommunications. En 1992, le GSM est rebaptisé << Global System for Mobile communications >> ; ce changement de nom symbolise le passage du concept de laboratoire au produit commercial.

Le GSM autorise l'envoi et la réception de messages courts (SMS : Short Message Services), la transmission de données en mode circuit, ainsi qu'un grand nombre de services supplémentaires [Tis99].

La bande de fréquence de cette norme européenne s'élève à l'origine à 900 MHz. Elle a été ensuite mise en oeuvre avec des fréquences autour de 1800 MHz [Rah93] [AgF99]. La Figure 1.6 illustre les différents composants constituants un réseaux GSM.

Figure 1.6 : Composants d'un réseau GSM.

· les stations de base ou BTS (Base Transceiver Station) : ce sont les antennes qui sont chargées de communiquer avec les téléphones portables. La zone de communication couverte par une station de base est appelée cellule - d'où le terme << réseau cellulaire >> ;

· les contrôleurs de station de base ou BSC (Base Station Controller) : ces composants sont chargés de gérer un ensemble de stations de base ;

· les centres de commutation de service mobile ou MSC (Mobile-service Switching Centre) qui doivent organiser les communications dans le réseau ;

· les enregistreurs de localisation de visiteurs ou VLR (Visitor Location Register) : ces bases de données, associées aux centres de commutation, stockent des informations de localisation précises sur des utilisateurs mobiles ;

· l'enregistreur de localisation nominal ou HLR (Home Location Register) qui est une base de données centrale - éventuellement dupliquée - contenant les informations sur les abonnés (dont une information de localisation comme la zone de localisation) ;

· le centre d'authentification des abonnés ou AUC (AUthentification Centre) qui est une base de données chargée d'assurer l'authentification des utilisateurs.

· GPRS (General packet Radio Service)

Une évolution du GSM, le GPRS [Tis99] est vu comme étant un conduit, permett ant aux applications situées dans un terminal mobil de se connecter à des bases de données. Il présente l'avantage de faire une taxation selon le volume de donnée transmis et non pas sur la duré de la communication. Ceci s'explique par la non utilisation de l'interface radio durant toutes la duré de la communication grâce à la commutation de paqué. Avec ce mode de transmission le GPRS offre des débit variable compris entre 9,6 kbits/s et 17 1,2 kbits/s.

· UMTS (Universal Mobile Telecommunications System)

Désigne une technologie retenue au niveau de la normalisation internationale dans la famille dite "IMT 2000" comme norme pour les systèmes de télécommunications mobiles de troisième générat ion [BFM97] [AgF99].

L'UTMS permet des améliorations par rapport au GSM, notamment :

· Un accès plus rapide à Internet depuis les téléphones portables, par un accroissement significatif des débits des réseaux de téléphonie mobile.

· Amélioration de la qualité des communications en tendant vers une qualité d'audition proche de celle de la téléphonie fixe.

· Etablissement d'une norme compatible à l'échelle mondiale, contrairement aux technologies actuelles (les normes utilisées aux Etats-Unis et au Japon ne sont pas toutes compatibles avec le GSM).

· Tend à résoudre le problème croissant de saturation des réseaux GSM, en particulier dans les grandes villes.

· Utilisation du codage DS-CDMA (Direct Sequence - Code Division Multiple Access) qui, outre un nombre important d'avantages, permet la réutilisation de la même bande de fréquence pour toutes les cellules voisines (avec GSM, les cellules voisines ne peuvent utiliser les même bandes de fréquence car elles interfèrent les unes avec les autres d'où un arrangement minutieux et compliqué de bandes de fréquence des cellules).

Les technologies développées autour de la norme UMTS conduiront à une amélioration significative des vitesses de transmission avec des débits supérieurs à 3 84Kbp/s et pouvant aller jusqu'à 2Mbp/s (en zone urbaine, avec une mobilité réduite).

Une des grandes nouveautés réside dans le fractionnement des cellules en zones (voir Figure 1.7) qui offrent des débits variables en fonction de la mobilité [BFM97]: zone intérieure et urbaine, zone urbaine, zone suburbaine et agricole, et enfin zone globales.

Zone 1 intérieure et urbaine : communication permanente, densité élevée d'utilisateurs, vitesse maximale de déplacement jusqu'à 10 km/h et débit assuré de 2 Mbp/s.

Zone 2 urbaine : micro-cellules utilisées pour les lieux publiques, rayon de service de plusieurs centaines de mètres, densité assez élevée d'utilisateurs, vitesse jusqu'à 120 km/h et débit de 480 kbp/s.

Zone 3 suburbaine et agricole : macro-cellules pour densités de population moyennes, rayon de service de plusieurs kilomètres, mobilité moyenne assurée (jusqu'à 500 km/h et débits de 384 kbp/s pour les vitesses moyennes (120 km/h) ou 144 kbp/s pour les vitesses élevées. Zone 4 globales : tout ce qui n'est pas couvert par les zones 1 à 3 à savoir, zones peu peuplées, océans, déserts, montagnes, etc. Le MSS (Mobile Satellite Systems) doivent couvrir ces zones. La mobilité atteint les 1000 km/h avec un débit de 144 kbp/s. En principe, les satellites doivent assurer une couverture partout où l'infrastructure cellulaire fait défaut.

Figure 1.7: Fractionnement des cellules en zones dans la technologie UMTS

Standards Américains

· IS-54 et IS-136

L'IS-54 est basé sur la méthode d'accès TDMA et a été implémenté par certains opérateurs cellulaires aux côtés de leurs réseaux analogiques en 800 MHz. Ce standard a également été retenu pour être utilisé dans le cadre des réseaux PCS (Personal Communication Services) large bande sous l'appellation IS-136 [HSJ98] [Cou99].

· IS-95 ou N-CDMA

Qualcomm a développé une technologie basée sur la technique d'accès CDMA (Code Division Multiple Access) [AgF99]. L'IS-95 ou N-CDMA (Narrowband CDMA) est censé supporter 10 à 15 fois la capacité des réseaux AMPS (AMPS : Advanced Mobile Phone System) contre un gain de 3 pour l'IS-54 [Gar00].

La norme IS-95 a commencé à être retenue dans quelques pays en dehors des Etats-Unis en particulier en Asie et en Amérique du Sud.

Un standard japonais PDC (Personal Digital Cellular system)

Lancé par DoCoMo qui a rajouté une sur-couche de communication par paquets appelée PDC-P. La norme japonaise de radiotéléphonie cellulaire numérique s'appuie, comme le GSM, sur le mode d'accès TDMA et fonctionne dans deux bandes de fréquences : 800 MHz et 1,5 GHz. Cette norme est intéressante, et commence à prendre place dans d'autres régions, car elle est le support d'accès du service I-Mode qui est un service d'Internet mobile utilisant le format des données cHTML (Compact HTML) qui est une déclinaison allégée du HTML adaptée aux terminaux mobiles. L'avantage du I-Mode par rapport à la technologie Wap, c'est que l'i-mode permet de ne garder le terminal connecté que le temps nécessaire aux transferts des données.

Les réseaux cellulaires peuvent être classés en 3 générations suivant leurs développement chronologique [GHJ99].

La première génération est analogique, nous citons à titre d'exemple les systèmes :

- AMPS (Advanced Mobile Phone System): développé par Bell Labs en 1970, la première

utilisation commerciale était au Etats Unis en 1983. Il exploite la bonde de fréquence de

800 MHz.

- NMT 450 (Nordic Mobile Telephones/450): développé par Ericsson et Nokia. Travail sur la bande de 450 MHz.

- NMT 900 (Nordic Mobile Telephones/900): l'utilisation de la bande de 900 MHz au lieu de 450 MHz.

- TACS (Total Access Communications System) : développé par Motorola. Il est similaire à AMPS. Il utilise la bande de 900 MHz. Il a été utilise la première fois au Royaume Uni en 1985.

- C-Netz : utilisé principalement en Allemagne et en Australie, utilise la bande de 450 MHz.

- RC2000 (RadioCom 2000) : Un system Français lancé en novembre 1985.

Les systèmes de radiotéléphonie cellulaire ont vu, après une première génération constituée uniquement de réseaux analogiques, l'arrivée des technologies numériques au début des années 1990 en Europe (GSM) et au Japon (PDC). Les Etats-Unis ont suivi quelques années plus tard (IS-136 et IS-95).

Il existe une génération 2+ (dite aussi 2.5 G) avec le GPRS, évolution du système GSM. Celui-ci permet la commutation de paquets et des débits de 105 KBits/s. Dans ce cas, IPV4 est obligatoire.

La troisième génération permet d'utiliser IP dans un contexte multimédia. Les terminaux peuvent avoir une adresse fixe, certaines normes comme l'UMTS impose IPv6. Le nom générique pour les différentes normes 3G est IMT-2000.

Tableau 1.3: Les Générations des réseaux cellulaires.

VI.2. Classification suivant l'infrastructure

· Réseaux sans fil avec infrastructure

Dans ce mode de fonctionnement le réseau est obligatoirement composé d'un point d'accès appelé station de base (SB), munis d'une interface de communication sans fil pour la communication directe avec les sites ou unités mobiles (UM), une station de base couvre une zone géographique limitée, une unité mobile est rattachée à un moment donné qu'à une station de base lui offrant tous les services tant que l'UM est à l'intérieure de la zone de couverture de la SB.

La SB fait office de pont entre réseau filaire et réseau sans fil, permett ant de relier une UM à une unité connecté à un site fixe. La SB est aussi le point de passage de la transmission d'une UM à une autre UM. Si les deux UM dépendent de la même SB, la trame est simplement relayée par la SB. Si les deux UM sont à deux SB différentes, une trame échangée entre les

deux UM doit être relayée par le réseau filaire qui relie les deux point d'accès. Les points d'accès peuvent être répartis sur tous le réseau filaire, agrandissant d'autant la couverture du réseaux sans fil.

Figure 1.8 : Le modèle des réseaux mobiles avec infrastructure.

Au cours de communication une UM peut sortir de la zone de couverture de son point d'accès, entrant dans une autres zone (handover), pour assurer la continuité de la communication l'ancienne SB envoie les informations de l'UM à la nouvelle SB qui va allouer un canal de communication à l'unité mobile.

· Réseaux sans fil sans infrastructure (ad hoc)

-Définition

Il s'agit d'un mode Point à Point, ne nécessitant pas de points d'accès. Il permet de connecter les stations quand aucun point d'accès n'est disponible. L'absence d'infrastructure oblige les UM à jouer le rôle de routeurs [CCL03].

La Figure 1.9 montre l'exemple de l'UM A qui peut envoyer à l'UM C malgré que cette dernière n'est pas dans la portée de l'UM A, pour faire elle envoie les messages à l'UM B qui va les envoyer à l'UM C.

UMA

UMB

UMC

Portée de l'UM

Figure 1.9: Exemple de réseaux ah doc.

Les réseaux ad hoc ont des typologies instables, ceci est dû aux déplacements fréquents des UM. D'autre part, la portée des transmissions radio étant limitée, le relayage est rendu obligatoire, et il faut donc que les UM forment ce réseau ad hoc et coopèrent pour transmettre les messages d'une source à une destination. Les chemins utilisés et les noeuds traversés sont déterminés par un protocole de routage dédié, c'est d'ailleurs la raison pour laquelle les réseaux ad hoc sont dits réseaux à routage interne ou aussi réseaux sans fil multi-saut (multi-hop wireless ad hoc networks) [CCL03].

Beaucoup de problèmes sont liés aux réseaux ad hoc : l'allocation des fréquences, problème des noeuds cachés et des noeuds exposés [BCG04].

- Application

Les applications ayant recours aux réseaux ad hoc couvrent un très large spectre, incluant les applications militaires et de tactique, les bases de données parallèles, l'enseignement à distance, les systèmes de fichiers répartis, la simulation distribuée interactive et plus simplement les applications de calcul distribué ou méta-computing.

D'une façon générale, les réseaux ad hoc sont utilisés dans toute application où le déploiement d'une infrastructure réseau filaire est trop contraignant, soit parce que difficile à mettre en place, soit parce que la durée d'installation du réseau ne justifie pas de câblage à demeure.

L'intérêt est dans un premier temps de pouvoir assurer une connexion au réseau tout en permett ant la mobilité de l'utilisateur. De plus, le câblage n'est plus nécessaire, ce qui représente un avantage certain dans de nombreux cas : -Mise en place d'un réseau dans un

bâtiment classé "monument historique". -Mise en place d'un réseau de courte durée (chantiers, expositions, locaux loués, formations). -Confort d'utilisation : tous les participants d'une réunion sont automatiquement interconnectés. - Gain en coût pour la mise en place d'un réseau dans tout bâtiment non préalablement câblé.

Les réseaux ad hoc sont très utiles dans des situations imprévues telle que les catastrophes naturelles, les incendies, où il sera indispensable de disposer rapidement d'un réseau pour organiser les secours et les opérations de sauvetage.

Les réseaux ad hoc sont aussi utilisés pour avoir accès aux environnements hostiles à l'homme tels que des cratères des volcans pour surveiller leurs activités ou bien le long d'une faille géologique.

Ils sont aussi utilisés dans les réseaux de MESH

- Allocation des fréquences

Il est impossible de mettre en place un mécanisme d'allocation de fréquences dans les réseaux ad hoc. Dans les réseaux sans fil avec infrastructure, c'est la station de base qui attribue les fréquences de manière à assurer que deux stations voisines aient des fréquences différentes pour éviter le problème des interférences. Dans les réseaux ad hoc, pour garantir la connectivité, comme il n'y a pas d'infrastructure fixe et que tous les noeuds sont susceptibles de bouger ou de disparaître, il est plus simple et moins coûteux de travailler avec une seule fréquence. On utilise alors un multiplexage TDD (Time Division Duplex). La réutilisation spatiale reste possible, mais un noeud qui émet empêche l'accès au canal radio pour tous les mobiles se trouvant dans un voisinage étendu au tour de lui.

- Problème des noeuds cachés

Le problème du noeud caché se produit lorsque deux unités mobiles ne peuvent pas s'entendre l'une et l'autre du fait qu'un obstacle les empêche de communiquer entre elles ou que la distance qui les sépare est trop grande.

A

B

C

A

Obstacle

B

C

Figure 1.10: N°ud caché dû à un obstacle. Figure 1.11 : N°ud caché dû à la distance.

En Figure 1.10 l'obstacle empêche le noeud A de savoir l'activité du noeud C, et empêche le noeud C de savoir l'activité du noeud A. Ainsi les deux noeuds A et C peuvent entamer simultanément des communications vers le noeud B, ceci provoquera une collision au niveau du noeud B, car les bandes de fréquences utilisées par les noeuds au sein d'un réseau ad hoc sont identiques.

En Figure 1.11 le noeud A ne détecte pas l'activité du noeud C, car A n'est pas dans la zone de couverture de C, et aussi C ne détecte pas l'activité du noeud A. alors les deux noeuds A et C vont s'autoriser à émettre en même temps vers le noeud B, ce qui amène à une collision au niveau de ce dernier.

Il faut bien noter que sous la plupart des simulateurs cette configuration ne se produira jamais car les zones de détection de porteuse (où on reçoit les signaux mais on ne peux pas les déchiffrés) étant parfaitement circulaires et d'un rayon double de la zone de couverture (on arrive à déchiffrer les signaux reçus, et donc on s'aperçoit s'il s'agit d'une donnée ou d'un message de contrôle), A se trouverait dans la zone de détection de porteuse de C et réciproquement. Mais dans la réalité, l'expérience a montré que ce type de collision était tout à fait possible [Dho03].

- Problème des noeuds exposés

Considérons le cas présenté en Figure 1.12 où une station B initie une communication vers une station A, la station C écoute le canal radio, elle entend donc une communication en cours, car C est dans la zone de couverture de B. Dans ce cas la station C déduit qu'elle ne peut pas entamer une communication avec D, or si C transmettait, elle ne crée pas une collision dans les régions où D et A se situent. Ce problème diminue les performances du réseau en terme de bande passante.

A B C D

Figure 1.12: Problème des noeuds exposés.

Pour régler ces problèmes la norme 802.11 a défini des techniques d'accès au medium spécifiques aux réseaux sans fils.

- Les techniques d'accès au canal de transmission

CSMA/CA

La norme IEEE 802.11 [IEE03] définit deux modes d'accès au médium adaptés aux transmissions radio : le mode centralisé (Point Coordination Function PCF) peut être utilisé lorsque les communications sont gérées par une station de base fixe et le mode distribué (Distributed Coordination Function DCF) est utilisé à la fois pour les communications via une station de base et pour les communications directes de mobile à mobile. C'est ce dernier mode qui sera utilisé dans le cas des réseaux ad hoc.

Le fonctionnement du mécanisme CSMA/CA est le suivant [IEE03]: une station qui souhaite émettre écoute le canal radio, lorsque ce dernier devient libre, il faut qu'il reste encore libre pendant une période DIFS (DCF Inter-Frame Space), Si le canal est resté libre durant toute cette période, alors la station attend encore un temps backoff extrait aléatoirement dans un intervalle appelé Contention Windows (CW), qui est par défaut [0. .31], avant d'émettre. Ainsi, si plusieurs mobiles veulent émettre, il y a peu de chances pour qu'ils aient choisi la même durée (backoff). Celui qui a choisi le plus petit backoff va commencer à émettre (tant que la canal est libre les backoff seront décrémentés, et lorsque le backoff d'une station atteint zéro, elle est autorisée à émettre), et les autres vont alors se rendre compte qu'il y a à nouveau de l'activité sur le canal et vont attendre.

La Figure 1.13 montre le déroulement des communications entre deux mobiles " source 1" et " source2" qui veulent envoyer simultanément des données vers un autre mobile " destination", dans cette exemple les backoff tirés par les mobiles " source1" et " source2" sont 3 et 5 respectivement. Une fois ce tirage effectué, tant que le canal reste libre, les mobiles

décrémentent leur backoff. Dès que l'un d'eux a terminé (ici la source 1), il émet. L'autre mobile, dès qu'il détecte le regain d'activité sur le canal stoppe la décrémentation de son backoff et entre en période de defering.

Figure 1.13: Le backoff et le defering.

Il faut noter que le temps de pause qui sépare un paquet de données de son acquittement est appelé SIFS (Short Inter-Frame Space) et qu'il est plus court que DIFS. Le mobile en période de defering ne pourra reprendre la décrémentation de son backoff que si le canal est à nouveau libre pendant DIFS. Le fait que SIFS soit plus court empêche que la décrémentation ne reprenne de manière inopportune entre les données et leur acquittement (l'envoie des ACK est favorisé que l'envoie des données).

Lorsque les données du mobile "station1" ont été acquittées et que DIFS s'est écoulé sans activité sur le canal, "Source2" peut reprendre la décrémentation de son backoff (qui est déjà à 2 unités). Ici, aucun autre mobile ne vient l'empêcher de terminer et il peut donc finalement envoyer ses données.

Le mécanisme de backoff limite les risques de collision mais ne les supprime pas complètement. Aussi, si une collision se produit (détectée grâce à l'absence d'acquittement), un nouveau backoff va être tiré au hasard. Mais à chaque collision consécutive, la taille de la fenêtre va doubler afin de diminuer les chances que de telles collisions se répètent. La borne inférieure de la Contention Window est toujours zéro, et la borne supérieure va évoluer entre

les valeurs aCWmin et aCWmax définies par la norme. La borne supérieure de la fenêtre est ré-initialisée à CWmin sitôt qu'un paquet a été transmis correctement (ou lorsque les timers de ré-émission expirent) [IEE03]. Un exemple d'évolution de la fenêtre de contention est donné sur la Figure 1.14.

Figure 1.14: Exemple de variation du backoff

D'autres mécanismes de gestion de la fenêtres de contention sont définis pour une meilleur utilisation du medium d'accès, dans [BFO96] la fenêtre est mis à jour selon le nombre de stations connectées.

Le mécanisme de la DCF, ne règle pas définitivement le problème des noeuds cachés, et des noeuds exposés, son but principal est de régulariser l'accès au medium de manière distribués, tout en essayant d'éviter les collisions.

RTS/CTS

Le mécanisme CSMA/CA cherche à éviter les collisions en écoutant l'activité sur le canal, cependant le problème des noeuds cachés n'est pas définitivement réglé par cette méthode. 802.11 [IEE03] propose un mécanisme utilisant des paquets de contrôle appelés Request To Send (RTS) et Clear To Send (CTS) introduit par [Kar90]. Un mobile qui veut émettre ne va plus directement envoyer son paquet de données, mais plutôt un petit paquet RTS pour lequel les chances de collision sont plus faibles. A ce paquet RTS, le destinataire va répondre par un petit paquet CTS qu'il diffuse à tout son voisinage. Les paquets RTS et CTS contiennent des

informations qui permettent de réserver le canal pour la durée de transmission des données qui vont suivre. Un mobile qui reçoit un CTS alors qu'il n'a pas envoyé (ni même détecté de RTS) sait que quelqu'un d'autre va émettre et doit donc attendre. Le mobile qui a envoyé le RTS sait, quand il reçoit le CTS correspondant, que le canal a été réservé pour lui et qu'il peut émettre.

Au niveau des mobiles, la réservation du canal est implémentée grâce au Network Allocation Vector (NAV). Dans chaque noeud, le NAV indique pour combien de temps le canal est utilisé par quelqu'un d'autre, indépendamment de ce qui est physiquement perçu sur le canal (on parle aussi de détection de porteuse 'logique'). Sur la Figure 1.15 sont présentées les mises à jour du NAV au niveau d'un mobile alors qu'une trame est échangée entre deux autres mobiles. Lorsque le noeud non concerné par l'échange reçoit le RTS, il sait grâce aux informations contenues dans ce dernier pour combien de temps il ne devra pas accéder luimême au canal.

Les CTS et les paquets de données vont aussi porter les informations de durée, afin que leur réception puisse mettre à jour le NAV, lorsque un mobile n'a pas reçu déjà le RTS (comme c'est la cas pour les noeuds cachés), il met à jour le NAV à la réception du CTS, et s'il ne reçoit pas le CTS, il met à jour le NAV lorsque il détecte qu'il y a envoie de données.

Figure 1.15: Mise à jour du Network Allocation Vector (NAV).

Le mécanisme RTS et CTS ne règle pas définitivement le problème des noeuds cachés, mais diminue le risque de collisions de données, en faite le risque collision persiste sur les messages de contrôle (RTS et CTS), mais cela est moins grave que les collisions de données.

EIFS

Le mécanisme RTS et CTS ne règle pas le problème de collision lorsque un noeud ne reçoit pas les paquets RTS, CTS et les données, comme c'est présentée sur la Figure 1.16 [Cha04], le noeud de gauche ("autre") détecte la porteuse de l'émetteur sans pour autant comprendre ses messages (le signal est trop faible pour être décodé, mais suffisamment fort pour être reconnu comme tel). Les paquets envoyés par le récepteur ne sont quant à eux pas détectés du tout par le mobile de gauche. Dans cette situation, 802.11 [IEE03] impose l'utilisation d'un Extended Inter Frame Spacing (EIFS), afin d'éviter une collision au niveau de l'émetteur au moment du CTS et de l'acquittement par le récepteur. La Figure 1.17 détaille ce qui se passe : L'émetteur envoie tout d'abord un paquet de contrôle RTS. Ce paquet est reçu par le récepteur, qui va y répondre par un CTS. Le mobile de gauche, lui, a détecté de l'activité au moment du RTS mais sans comprendre le paquet. Le mécanisme de defering l'empêche d'émettre pendant l'envoi du RTS (canal occupé) et pendant une période DIFS consécutive (on est toujours obligé d'attendre que la canal ait été libre pendant DIFS pour émettre). Mais DIFS est plus court que SIFS+CTS. Si jamais le mobile de gauche avait terminé de décrémenter son backoff trop vite, il aurait pu émettre pendant le CTS, causant une collision au niveau de l'émetteur. Pour protéger le CTS (et de manière similaire l'acquittement), 802.11 impose à un noeud d'attendre pendant un temps EIFS lorsque le canal redevient libre mais que le paquet n'a pas été compris; la longueur de EIFS étant suffisante pour que l'envoi du CTS ou de l'ACK se déroule dans de bonnes conditions.

SIFS SIFS SIFS DIFS

Destination
									Autre defer
EIFS				EIFS

DIFS tem^ps

Au

Figure 1.16: Configuration où l'EIFS est nécessaire. Figure 1.17: l'Extended Inter Frame Spacing (IEFS).

VII. CONCLUSION

Ce chapitre a été axé sur le concept des environnements mobiles et l'utilisation de la technologie de communication sans fil. L'évolution rapide qu'a connue la technologie sans fil récemment, a permit l'apparition de nouveaux systèmes de communication qui offrent plus d'avantages par rapport aux systèmes classiques. Les nouveaux systèmes n'astreignent plus l'usager à une localisation fixe, mais lui permet une libre mobilité.

La compréhension parfaite de la communication utilisée dans le nouvel environnement, nécessite la compréhension des notions de base de la technologie sans fil comme l'utilisation des ondes radio, la notion de bande passante, la réutilisation des fréquences, le portée d'une unité mobile « etc. Le but de ce chapitre a été de donner un aperçu général sur cette technologie qui ne cesse pas de croître.

Les environnements mobiles sont caractérisés par de fréquentes déconnexions et des restrictions sur les ressources utilisées, surtout si tous les usagers du système sont mobiles ce qui est le cas pour les réseaux ad hoc. Ces limitations transforment certains problèmes, ayant des solutions évidentes dans l'environnement classique, en des problèmes complexes et difficiles à résoudre. Parmi ces problèmes figure le problème de routage que nous allons discuter dans le deuxième chapitre.

CHAPITRE II : ETUDE DES PROTOCOLES DE ROUTAGE
DANS LES RESEAUX AD HOC

I. Introduction

Comme nous avons déjà vu, un réseau ad hoc est un ensemble de noeuds mobiles qui sont dynamiquement et arbitrairement éparpillés d'une manière où l'interconnexion entre les noeuds peut changer à tout moment. Dans la plupart des cas, l'unité destination ne se trouve pas obligatoirement dans la portée de l'unité source ce qui implique que l'échange des données entre deux noeuds quelconques, doit être effectué par des stations intermédiaires. La gestion de cet acheminement de données, ou routage, implique l'établissement d'une certaine architecture globale que l'on doit tenir compte de la mobilité des unités et de la versatilité du médium physique.

Le fait que les noeuds mobiles ne sont pas contrôlés par une seule entité implique que leur mouvement est très difficilement prévisible et que par conséquent la connectivité radio change au cours du temps. On est donc en présence de réseaux dont la topologie est dynamique et dont les noeuds ont des caractéristiques particulières (ressources d'énergie et de calcul limitées).

Ces spécificités des réseaux ad hoc font que les solutions de routage mises au point pour les réseaux filaires classiques ne sont pas du tout adaptées.

La stratégie (ou le protocole) de routage est utilisée dans le but de découvrir les chemins qui existent entre les noeuds. Le but principal d'une telle stratégie est l'établissement de routes qui soient correctes et efficaces entre une paire quelconque d'unités, ce qui assure l'échange des messages d'une manière continue.

Suivant la manière de création et de maintenance de routes lors de l'acheminement des données, les protocoles de routage peuvent être séparés en trois catégories,les protocoles proactifs, les protocoles réactifs et les protocoles hybrides. Les protocoles proactifs établissent les routes à l'avance en se basant sur l'échange périodique des tables de routage ; les protocoles réactifs cherchent les routes à la demande ; les protocoles hybrides utilisent une combinaison des deux techniques.

Dans ce chapitre, nous allons présenter les trois classes des protocoles de routage (Proactif, Réactif, Hybride) dans les réseaux Ad hoc en étudiant, dans chaque cas, quelques protocoles proposés par L'IETF; nous décrirons leurs principales caractéristiques et fonctionnalités qui permettent d'assurer l'acheminement des données entre les différentes unités mobiles.

II Routage dans les réseaux Ad Hoc

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

Avant de parler des protocoles de routage proprement dit, nous allons rappeler quels sont les principaux modes de communication dans les réseaux et particulièrement dans les réseaux Ad hoc :

- la communication point à point ou unicast, pour laquelle il y a une source et une seule destination ;

- la communication multipoint ou multicast, qui permet d'envoyer un message à plusieurs destinataires ;

-la diffusion ou broadcast, qui envoie un message à tous les noeuds du réseau. Ces trois modes de communication sont schématisés par la figure 2.1.

Unicast Multicast

Broadcast

Transmission

Groupe multicast

: Source

: Destination(s)

Figure 2.1 : Modes de communication dans les réseaux mobiles

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

Le routage dans les réseaux ad hoc est assez délicat étant donnée la nature changeante de la topologie de ce type de réseaux. De nombreux protocoles sont proposés pour résoudre le problème de routage multi saut (multihoping), chacun fondé sur différents concepts et reposant sur différentes hypothèses et intuitions. Les protocoles de routage peuvent être séparés en deux classes principales, à savoir proactif ou réactif, selon les manières dont les

routes sont créées et maintenues. On pourra ajouter une troisième classe, celle des protocoles hybrides qui sont une combinaison des protocoles proactifs et réactifs. Dans ce qui suit, nous présentons beaucoup plus en détail les principaux protocoles retenus par le groupe de travail MANET au sein de l'IETF.

II.2.1 Les protocoles de routage proactif

Les protocoles proactifs utilisent l'échange régulier de messages de contrôle pour maintenir au niveau de chaque noeud des tables de routage (qui associent à chaque destination ou groupe de destinations un voisin direct par lequel les paquets doivent être relayés) vers toute destination atteignable depuis celui-ci. Ces tables sont maintenues même quand les routes ne sont pas utilisées, cette approche permet de disposer d'une route vers chaque destination immédiatement au moment où un paquet doit être envoyé.

Les deux principales méthodes utilisées sont : la méthodes Etat de Lien ("Link State") [Per0 1] et la méthode du Vecteur de Distance ("Distance Vector") [PBh94]. Les deux méthodes exigent une mise à jour périodique des données de routage qui doit être diffusée par les différents noeuds de routage du réseau. Les algorithmes de routage basés sur ces deux méthodes, utilisent la même technique qui est celle des plus courts chemins, et permettent à un hôte donné, de trouver le prochain hôte pour atteindre la destination en utilisant le trajet le plus cours existant dans le réseau. Généralement le calcul du plus court chemin entre deux stations, est basé sur le nombre de n°uds mobile (on dit aussi le nombre de sauts) que comportent les différents chemins qui existent entre les deux noeuds. Mais on peut aussi associer des coûts aux liens de communication. Un coût peut matérialiser le taux de l'utilisation d'un lien, les délais relatifs de communication etc«.

a. Algorithme du vecteur de distance

Dans le vecteur de distance ou routage de bellman-Ford (distance vector routing) [Wei], chaque noeud du réseau maintient une table de routage qui comporte une entrée par n°ud du réseau, le prochain noeud à att eindre et le coût pour joindre cette destination. Périodiquement chaque noeud diffuse sa table de routage à ses voisins. Le n°ud voisin apprend ainsi ce que son voisin est capable de joindre. À la réception, le n°ud compare les informations reçues à sa propre base de connaissance de la façon suivante:

- Si la table reçue contient une entrée qui n'est pas déjà dans sa propre table, il incrémente le coût de cette entrée du coût affecté au lien par lequel il vient de recevoir et met cette entrée dans sa table. Il a ainsi appris une nouvelle destination et il rediffuse cette nouvelle table à ces voisins.

- Si la table contient une entrée qu'il connaît déjà, la procédure est la suivante :

Si le voisin qui a envoyé les mises à jour est le même figurant dans l'entrée considéré comme prochain n°ud à atteindre, donc seul le coût du chemin a changé, alors il met à jour sa table. Bien entendu ceci voudrait dire que le chemin a changé à partir du deuxième saut.

Sinon

Si Le coût calculé (coût reçu incrémenté du coût lien) est supérieur ou égale à l'information qu'il possède, il l'ignore. Dans le cas contraire il met à jour sa table.

De proche en proche chaque n°ud apprend la configuration du réseau et le coût des différents chemins. Cet algorithme n'est pas sans faille. En effet, la convergence des différentes tables peut être assez longue. De plus, le manque de coordination dans la mise à jour des tables de routage peut conduire à la modification de ceux-ci sous la base des données erronées, ce qui peut provoquer une boucle de routage (routing loops). En plus de cela, le DBF (Distributed

Bellman-Ford) ne possède pas de mécanisme précis qui peut déterminer quand est ce que le réseau doit arrêter l'incrémentation de la distance qui correspond à une destination donnée, ce problème est appelé : counting to infinity. Le paragraphe suivant élucide ces problèmes.

a-1. Boucle de routage :

Considérons la topologie du réseau Ad hoc suivant (figure 2.2).

A			B				C

A

A

0

B

B

1

2

B

C

B

A

C

B

B

C

0

2

1

B

A

C

A

B

C

0

1

1

Figure 2.2 : Exemple d'utilisation du DBF.

Nous avons trois n°uds qui maintiennent chacun une table de routage, la première colonne désignant la destination à atteindre ; la deuxième, le prochain n°ud et la troisième le coût, en terme du nombre de sauts, pour atteindre cette destination. Bien entendu, nous supposons que le réseau est déjà stable.

Imaginons maintenant qu'à un moment donné, le lien entre C et B ne soit plus actif. Apprenant la nouvelle, le n°ud B met à jour sa table en portant le coût du lien (B, C) à l'infini pour indiquer qu'il ne peut plus atteindre ce n°ud, donc ne diffuse plus cette route (la figure suivante illustre ce fait).

B	B	0		C	C		0	A
A	1		B	B	™		C
C	™		A	B	2

A

A

0

B B 1

C B 2

Figure 2.3 : Mises à jour après coupure de lien dans

Lors du prochain échange, A informe B qu'il peut atteindre C à un coût 2, B met sa table à jour qui devient ainsi :

B

A

C

A

A

B

0

3

1

Nous venons d'aboutir à une boucle, tout paqué que A reçoit à destination de C, il l'envoie à B, vice versa tout paqué que B reçoit à destination de C, il l'envoie àA.

a-2. Contage à l'infini :

Pour illustrer ce concept, considérons l'état précédent de notre topologie.

À l'échange suivant, A apprend que joindre C en passent par B a maintenant un coût de 3+1 Soit 4. Il met sa table à jour. À l'échange suivant B passe le coût à 5, puis A à 6 jusqu'à ce que le coût devienne l'infini.

b. Algorithme à Etat de lien :

Le principal défaut du routage vecteur distance provient du fait que les routeurs n'ont la connaissance d'un changement d'état du réseau que lorsque leur voisin le leur communique, ce qui peut être long. Pour palier ce défaut, le routage à état de lien procède différemment :

- chaque n°ud détermine le coût du lien qui lui est raccordé ;

- en cas de modification de cet état, le n°ud diffuse cette information dans le réseau, sous la forme (A, B, c), c'est-à-dire le lien entre les n°uds A et B a un coût de c ;

- Chaque n°ud entretient une table où figure pour chaque lien son coût (matrice de coût). À l'aide de ces informations, chaque n°ud peut reconstituer la cartographie complète du réseau en utilisant un Algorithme de recherche plus cour chemin dans un arbre, celui de Dijkstra est le plus utilisé.

Nous présentons par la suite deux protocoles, l'un basé sur l'état de lien, le OLSR, et l'autre, une amélioration du vecteur de distance, le DSDV.

II.2.1.1 Le protocole de routage DSDV

L'algorithme de routage appelé "Vecteur de Distance à Destination Dynamique Séquencée" ou DSDV (Dynamic Destination-Sequenced Distance-Vector) [Per01, BMJ98] a été conçu spécialement pour les réseaux mobiles. Il est basé sur l'idée classique de l'algorithme distribué de Bellman-Ford, DBF, en y apportant des solutions à ses éventuels problèmes. Ce protocole fonctionne de façon suivante :

Chaque n°ud maintient une table de routage qui contient :

· Toutes les destinations possibles.

· Le nombre de saut nécessaire pour atteindre la destination.

· Le numéro de séquences (SN : sequence number) qui correspond à un n°ud destination. Afin de maintenir la consistance des tables de routage dans une topologie qui varie rapidement, chaque noeud du réseau transmet périodiquement sa table de routage à ses voisins directs. Le noeud peut aussi transmettre sa table de routage si le contenu de cette dernière subit des changements significatifs par rapport au dernier contenu envoyé.

La mise à jour doit permettre à un n°ud de pouvoir localiser, dans la plupart des cas, une autre unité du réseau.

La mise à jour de la table de routage peut se faire de deux façons:

· Une mise à jour complète.

· Une mise à jour incrémentale.

Dans la mise à jour complète, le n°ud transmet la totalité de la table de routage aux voisins ce qui nécessite l'envoi de plusieurs paquets de données ; alors que dans une mise à jour incrémentale, juste les entrées qui ont subit un changement par rapport à la dernière mise à jour, sont envoyées ce qui réduit le nombre de paquets transmis.

Un paquet de mise à jour contient :

1- Le nouveau numéro de séquence incrémenté, du noeud émetteur.

Et pour chaque nouvelle route :

2- L'adresse de la destination.

3- Le nombre de noeuds (ou de sauts) séparant le noeud de la destination.

4- Le numéro de séquence (des données reçues de la destination) tel qu'il a été estampillé par la destination.

Les données de routage reçues par un n°ud, sont comparées avec les données déjà disponibles. La route étiquetée par la plus grande valeur du numéro de séquence (i.e. la route la plus récente), est la route utilisée. Si deux routes ont le même numéro de séquence, alors la route qui possède la meilleure métrique (nombre de sauts), est celle qui sera utilisée. Les

modifications faites sur les données de routage locales, sont immédiatement diffusées à l'ensemble courant des voisins. Les routes reçues par une diffusion, seront aussi envoyées quand le récepteur procédera à l'envoi de ses paquets de routage. Le récepteur doit incrémenter les métriques des routes reçues avant l'envoi, car le récepteur représente un noeud en plus, qui participe dans l'acheminement des messages vers la destination. Un lien rompu est matérialisé par une valeur infinie de sa métrique, i.e. une valeur plus grande que la valeur maximale permise par la métrique [PBh94].

Parmi les améliorations apportées au DBF classique, Le concept de numéro de séquence, qui Permet à tout moment de se renseigner sur la validité des routes, a permis au DSDV de résoudre le Problème de boucle de routage et du comptage à l'infini. Comme tout protocole de routage proactif, le DSDV connaît la route, ponctuellement, au moment même où un n°ud doit procéder à une transmission, ce qui permet d'être efficace en délais de transmission. Cependant, ce protocole ne résout pas la lenteur de la convergence des tables, qui est lui aussi hérite du DBF ; l'échange périodique des table de routage, pour maintenir les routes même si elle seront pas utilisés, génère un nombre de paquet de contrôle énorme . Pour finir, les auteurs de ce protocole l'ont renoncé aux profits du AODV [Per01].

II.2.1.2 Le protocole de routage OLSR

Optimized Link State Routing est un protocole par état de lien qui utilise une technique optimisée pour la diffusion des messages topologiques. La solution consiste à ne permettre qu'à un sous-ensemble de voisins de retransmettre les messages (voir FIG. 2.4) [CJL02, CJL01]. Ces voisins sont appelés les relais multipoint ou MPRs (multipoint relays).Chaque n°ud effectue la sélection de ses MPRs en se basant sur la connaissance de son voisinage à deux sauts. L'ensemble des MPRs doit être le plus petit possible, tout en assurant que la diffusion par leur intermédiaire permet d'atteindre le voisinage à deux sauts dans sa totalité. Le problème qui consiste à trouver le plus petit ensemble de MPRs est analogue au problème de la recherche d'ensemble dominant minimal dans un graphe. Dans OLSR, les noeuds appliquent une heuristique qui permet de se rapprocher de l'ensemble minimal dans la majeure partie des cas.

Source MPR

Figure 2.4 : Diffusion par inondation (à gauche) et diffusion optimisée (à droite)

Différents mécanismes sont utilisés dans le fonctionnement de ce protocole ce protocole.

a. Découverte de voisinage

Chaque noeud émet périodiquement des messages appelés HELLO qui contiennent essentiellement la liste des liens connus vers les voisins directs. La fonction de ces messages est multiple. Ils servent tout d'abord à détecter les voisins directs et la qualité des liens vers ceux-ci, à savoir s'ils sont symétriques ou asymétriques. Comme chaque noeud y publie la liste de ses voisins, il est possible pour un n°ud d'acquérir des informations sur son voisinage à deux sauts. Par ailleurs, une fois qu'un noeud a effectué la sélection de ses MPRs, il indique dans ses messages HELLO lesquels de ses voisins sont ses MPRs. Ceci permet à un n°ud de savoir quels voisins l'ont choisi comme MPR, autrement dit de constituer son ensemble de MPR-selectors.

b. Diffusion optimisée

Lorsque qu'un n°ud reçoit un message de contrôle OLSR, il le traite et ne le transmet que si l'émetteur du message (l'adresse source du message, qui peut être différente de l'adresse de l'émetteur si le message a été généré par un noeud distant) appartient à l'ensemble des MPRselectors. Cette technique permet de diffuser des messages dans tout le réseau en évitant la saturation.

c. Les messages topologiques

Les messages topologiques, appelés TC (topology control) ne sont émis par un noeud qu'à condition que son ensemble de MPR-selectors n'est pas vide, c'est-à-dire qu'il est MPR d'un

de ses voisins. Les messages contiennent la liste des MPR-selectors du n°ud. Les n°uds du réseau reconstituent donc une topologie globale mais partielle, puisque tous les noeuds atteignables sont connus, mais pas tous les liens. Cette topologie partielle est néanmoins suffisante pour calculer des chemins minimaux en nombre de sauts vers tout destination.

Le fait de ne permettre qu'aux MPRs de générer des messages TC permet de limiter la quantité de messages diffusés dans le réseau et le fait de ne diffuser que la liste des MPRselectors permet de limiter la taille des messages.

d. Les changements topologiques

À chaque changement de topologie, le calcul des routes vers toutes les destinations est déclenché pour mettre à jour les tables de routage. Par ailleurs, lorsque son ensemble de voisins directs ou à deux sauts change, un noeud doit effectuer la sélection de ses MPRs à nouveau.

e. Calcul des routes

Une fois que les n°uds auraient envoyé les TC (les liens qui leur lie aux MPRs), chaque Q°ud constitue sa matrice des coût et utilise un Algorithme de recherche de plus cour chemin dans un graphe pour tracez sa cartographie du réseau (méthode à état des liens).

Dans ce protocole, seuls les n°uds, pour lesquels le MPRs-selector est non vide, ont droit à diffuser les messages topologique. Si bien que la quantité de message de contrôle générer par le réseau est limité. La convergence des tables de routage est rapide dans la mesure où chaque Q°ud constitue sa cartographie du réseau au lieu d'attendre que leur voisin le leur communique. Pour ce qui est le délai de transmission, il est efficace vu la nature proactive du protocole. En fin, ce protocole montre tous ces avantages mais il n'y a aucun algorithme de recherche de plus court chemin qui résout complètement le problème de boucle de routage temporaire, aussi, les fonctions de calcules qui permettent à un n°ud de sélectionner ses MPRs sont très complexes.

II.2.2 Les protocoles de routage réactifs

Comme nous avons vu dans la section précédente, les protocoles de routage proactifs essaient de maintenir les meilleurs chemins existants vers toutes les destinations possibles (qui peuvent représenter l'ensemble de tous les n°uds du réseau) au niveau de chaque n°ud du réseau. Les routes sont sauvegardées mêmes si elles ne sont pas utilisées. La sauvegarde permanente des chemins de routage, est assurée par un échange continu des messages de mise à jour des chemins, ce qui induit un contrôle excessif surtout dans le cas des réseaux de grande taille.

Les protocoles de routages réactifs (à la demande) créent et maintiennent les routes selon les besoins. Lorsqu'un noeud à besoin d'une route, une procédure de découverte globale est lancée. Cette procédure s'achève par la découverte de la route ou lorsque toutes les permutations de routes possibles ont été examinées. La route trouvée est maintenue par une procédure de maintenance de routes jusqu'à ce que la destination soit inaccessible à partir du n°ud source ou que le n°ud source n'aura plus besoin de cette route.

La majorité des approches utilisées lors de la découverte des routes sont basées sur le mécanisme d'apprentissage en arrière (backward learning). Le noeud source, qui est à la recherche d'un chemin vers la destination, diffuse par inondation une requête dans le réseau. Lors de la réception de la requête, les noeuds intermédiaires essaient de faire apprendre le chemin au noeud source, et de sauvegarder la route dans la table envoyée. Une fois la destination atteinte, elle peut envoyer une réponse en utilisant le chemin inverse, un chemin full duplex est alors établit entre le noeud source et le noeud destination. Le travail peut être réduit, dans le cas où un noeud de transit posséderait déjà un chemin vers la destination. Une fois que le chemin est calculé, il doit être sauvegardé et mis à jour au niveau de la source, tant qu'il est en cours d'utilisation. Une autre technique pour tracer les chemins demandés, est la technique appelée "routage source". Dans cette dernière tous les paquets de données diffusent leur information de cheminement en tant que leur en-tête, donc la décision de cheminement est prise dès au départ ce qui permet d'éviter des boucles ; cependant pour des topologies fortement mobiles c'est inefficace, puisque le protocole devient imprécis en raison de l'invalidation d'itinéraire pendant la transmission de paquet.

La recherche des chemins dans le routage à la demande entraîne une lenteur qui peut dégrader les performances des applications interactives. Des exemples de protocoles de routage réactifs sont : AODV et DSR (Dynamic Source Routing Protocol).

II.2.2.1 Le protocole de routage DSR

Dynamic Source Routing (DSR) [JMH01] est un protocole réactif basé sur l'utilisation de la technique source routing (routage source). Le chemin à parcourir est contenu dans l'entête du paquet de données. Ainsi lorsqu'un noeud reçoit un paquet, il le route vers le noeud suivant dont l'adresse est indiquée dans l'entête.

Les deux opérations de base du protocole DSR sont : la découverte de routes et la maintenance de routes. L'opération de découverte de routes permet à n'importe quel n°ud du réseau de découvrir dynamiquement un chemin vers un n°ud quelconque du réseau. Un noeud initiateur de l'opération de découverte diffuse un paquet requête de route qui identifie

l'hôte cible. Si l'opération de découverte est réussie, le noeud initiateur reçoit un paquet réponse de route qui liste la séquence de n°uds par lesquels, la destination peut être atteinte. En plus de l'adresse de l'initiateur, le paquet requête de route contient un champ enregistrement de route, dans lequel est stockée la séquence des n°uds visités durant la propagation de la requête de route dans le réseau (voir la figure 2-5 (a)).

Au passage du paquet, chaque noeud stocke en mémoire chaque nouvelle route, pour une utilisation postérieure éventuelle. Si le noeud ne trouve pas de route correspondant à l'entête du paquet, alors il initialise une découverte de route. Ainsi un noeud intermédiaire n'est pas obligé de connaître et d'avoir une table de routage à jour pour l'ensemble du réseau, mais seulement pour les noeuds qui lui sont adjacents.

Ce protocole est simple dans sa démarche et sa mise en place. Il permet également au réseau d'être auto structurable et configurable. Il n'y a donc aucun message de mise à jour des tables de routage autres que ceux contenus dans les entêtes des paquets transitant dans le réseau. Le paquet requête de route contient ainsi un identificateur unique de la requête. Dans le but de détecter les duplications des réceptions de la requête de route, chaque n°ud du réseau ad hoc maintient une liste de couples <adresse de l 'initiateur, identificateur de requête> des requêtes récemment reçues.

[1, 2, 6]

Destination

2

6

[1]

Source

1

8

[1]

3

[1, 3]

[1]

[1. 3, 5]

[1, 3, 5, 7]

5

4

[1, 4]

7

[1, 2]

(a) Construction de l'enregistrement de route

[1, 2, 6]

[1, 2, 6]

2

6

[1, 2, 6]

Source Destination

1

8

3

5

4

7

(b) Utilisation de la route dans le DSR

Figure 2.5 : La découverte de chemins dans le DSR.

Lors de la réception d'un paquet requête de route par un n€ud p du réseau, le traitement suivant est effectué :

- Dans le cas où le couple <adresse de l'initiateur, identificateur de requête du paquet reçu> existe déjà dans la liste des requêtes récemment reçues, le paquet est ignoré.

- Dans le cas contraire, si l'adresse de p existe dans le champ enregistrement de route du paquet de la requête, le paquet est ignoré.

- Sinon, si l'adresse de p est la même que l'adresse de la destination, alors l'enregistrement de route (contenu dans le paquet de la requête) contient le chemin à travers lequel le paquet de la requête est passé avant d'atteindre le n€ud p. Une copie de ce chemin est envoyée dans un paquet réponse de route à l'initiateur (voir la figure 2-5(b)).

- Sinon, l'adresse de p est ajoutée dans l'enregistrement de route du paquet reçu, et le paquet est rediffusé (voir la figure 2-5(a)).

De cette manière, la requête de route est propagée dans le réseau jusqu'à ce qu'elle atteigne l'hôte destination qui va répondre à la source. Le fait d'ignorer la requête dans le cas où l'adresse du récepteur existe dans l'enregistrement de route garantit que la propagation d'une unique copie de la requête ne peut pas se produire à travers des boucles de n€uds.

Dans le but de retourner le paquet réponse de route à l'initiateur de l'opération de découverte, le n€ud destination doit connaître un chemin vers l'initiateur. Dans le cas où la destination n'a pas déjà gardé une telle route, le chemin spécifié dans l'enregistrement de route contenu dans

le paquet requête de route peut être inversé et utilisé (voir la figure 2-5(b)). Cependant, cela exige que les liens entre les n°uds participant à la route doivent être bidirectionnels, ce qui n'est pas vérifié dans certains environnements.

Afin de réduire le coût et la fréquence de la découverte de routes, chaque n°ud garde les chemins appris à l'aide des paquets de réponses. Ces chemins sont utilisés jusqu'à ce qu'ils soient invalides.

Afin d'assurer la validité des chemins utilisés, le protocole DSR exécute une procédure de maintenance de routes. Quand un n°ud détecte un problème fatal de transmission, un message erreur de route (route error) est envoyé à l'émetteur originel du paquet. Le message d'erreur contient 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 erreur de route par l'hôte 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 routes vers la destination est initiée par l'émetteur.

Après la découverte de route vers la destination, pour envoyer un paquet de donnée à un autre Q°ud, l'émetteur construit une route source et l'inclut en tête du paquet. La construction se fait en spécifiant l'adresse de chaque n°ud à travers lequel le paquet va passer pour atteindre la destination. Par la suite, l'émetteur transmet le paquet au premier n°ud spécifié dans la route source. Un n°ud qui reçoit le paquet et qui est différent de la destination supprime son adresse de l'entête du paquet reçu, puis le transmet au n°ud suivant identifié dans la route source. Ce processus se répète jusqu'à ce que le paquet atteigne sa destination finale.

Parmi les avantages du protocole DSR, on peut citer le fait que les n°uds de transite 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.

II.2.2.2 Le protocole de routage AODV

Ad Hoc On-Demand Distance-Vector Protocol (AODV) [Per01] est un protocole réactif basé sur le principe des protocoles de routage à vecteur de distance. Il est pour l'essentiel une combinaison de DSDV et de DSR. Il emprunte, à DSR ses mécanismes de découverte et de maintenance des routes << Route Discovery >> et << Route Maintenance >>; à DSDV, son routage << saut par saut >>, les numéros de séquences ainsi que la diffusion des mises à jour des tables de routage. Ce protocole fait l'objet d'un grand nombre de recherches dû à toutes ses

caractéristiques; il est en effet l'un des principaux protocoles au sein du groupe de recherche MANET.

Comme le fait DSR, AODV utilise une requête de route dans le but de créer un chemin vers une certaine destination. Cependant, 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é. Une entrée de la table de routage contient essentiellement :

- L'adresse de la destination.

- Le n°ud suivant.

- La distance en nombre de n°ud (i.e. le nombre de n°ud nécessaire pour atteindre la destination).

- Le numéro de séquence destination.

- Le temps d'expiration de l'entrée de la table.

Quand un noeud de transit envoie le paquet de la requête à un voisin, il sauvegarde aussi l'identificateur du noeud à partir duquel la première copie de la requête est reçue. Cette information est utilisée pour construire le chemin inverse (figure 2-6 (b)) qui sera traversé par le paquet réponse de route (cela induit que l'AODV ne supporte que les liens symétriques). Puisque le paquet réponse de route va être envoyé à la source, les n°uds appartenant au chemin de retour vont modifier leurs tables de routage suivant le chemin contenu dans le paquet de réponse.

Un n°ud diffuse une requête de route (RREQ : Route REQuest) dans le cas où il aurait besoin de connaître une route vers une certaine destination et qu'une telle route ne serait pas disponible (figure 2-6 (a)). Cela peut arriver si la destination n'est pas connue au préalable, ou si le chemin existant vers la destination est devenu défaillant (i.e. la métrique qui lui est associée est infinie). Le champ numéro de séquence destination du paquet RREQ contient la dernière valeur connue du numéro de séquence associé au n°ud destination, cette valeur 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 numéro de séquence source du paquet RREQ contient la valeur du numéro de séquence du n°ud source. Comme nous lavons déjà dit, après la diffusion du RREQ, la source attend le paquet réponse de route (RREP : Route REPly). Si ce dernier n'est pas reçu pendant une certaine période (appelée RREP_ WAIT_TIME), la source peut rediffuser une nouvelle requête RREQ. A chaque nouvelle diffusion, le champ Broadcast ID du paquet RREQ est incrémenté. 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 est délivré.

RREQ

2

RREQ

6

RREQ

RREQ

RREQ

5

RREQ

Source Destination

1

8

3

RREQ

RREQ

4

RREQ

7

(a)La propagation du paque RREQ

RREP

RREP

2 6

RREP

Source Destination

1

8

3

5

4

7

(b)Le chemin pris par RREP

Figure 2.6: Les deux requêtes RREQ et RREP utilisées dans le protocole AODV.

Afin de maintenir des routes consistantes, une transmission périodique du message "HELLO" est effectuée. Si trois messages "HELLO" ne sont pas reçus consécutivement à partir d'un Q°ud voisin, le lien en question est considéré défaillant. Les défaillances des liens sont, généralement, dues à la mobilité des n°uds dans le réseau. Les mouvements des n°uds qui ne participent pas dans le chemin actif n'affectent pas la consistance des données de routage. Quand un lien reliant un n°ud p à un n°ud qui le suit dans le chemin de routage devient défaillant, le n°ud p diffuse un paquet UNSOLICITED RREP, avec une valeur de numéro de séquence égale à l'ancienne valeur du paquet RREP incrémentée de un, et une valeur infinie

de la distance. Le paquet UNSOLICITED RREP est diffusé aux voisins actifs jusqu'à ce qu'il arrive à la source. Une fois le paquet est reçu, la source peut initier le processus de la découverte de routes.

L'AODV maintient les adresses des voisins à travers lesquels les paquets destinés à un certain n°ud arrivent. Un voisin est considéré actif, pour une destination donnée, s'il délivre au moins un paquet de donnée sans dépasser une certaine période (appelée active timeout period). Une entrée de la table de routage est active si elle est utilisée par un voisin actif. Le chemin reliant la source à la destination en passant par les entrées actives des tables de routage est dit un chemin actif. Dans le cas de défaillances de liens, toutes les entrées des tables de routage participant au chemin actif et qui sont concernées par la défaillance sont supprimées. Cela est accompli par la diffusion d'un message d'erreur entre les n°uds actifs.

Le protocole de routage AODV (tout comme le protocole DSR), n'assure pas l'utilisation du meilleur chemin existant entre la source et la destination. Cependant, des évaluations de performances récentes ont montré qu'il n'y a pas de grandes différences (en terme d'optimisation) entre les chemins utilisés par le protocole AODV et celles utilisées par les protocoles basés sur les algorithmes de recherche des plus courts chemins. De plus, le protocole AODV ne présente pas de boucle de routage et évite le problème du comptage à l'infini "counting to infinity" de Bellman-Ford, ce qui offre une convergence rapide quand la topologie du réseau est dynamique.

Dans les protocoles réactifs, plus le niveau de mobilité des n°uds est élevé, plus le nombre de demandes d'itinéraire augmente. En raison de cela, le délai d'attente moyen tend à devenir plus grand [Per00].

Le DSR est meilleur que le AODV dans tous les niveaux de mobilité et principalement dans les plus petits réseaux. Un tel comportement peut être justifié par la forme dont les itinéraires sont établis dans DSR. Cependant, dans de grands réseaux, AODV prend les dessus sur le DSR.

II.2.3 Les protocoles de routage hybrides

En plus des protocoles de routage proactifs et réactifs, il existe une famille de protocole de routage qui est une combinaison des deux précédents et est dite 'hybrides' par exemple ZRP (the Zone Routing Protocol) et CBRP (Cluster Based Routing Protocol).

Ils utilisent un protocole proactif, pour apprendre le proche voisinage par exemple voisinage à deux sauts ou trois sauts. Ainsi ils disposent des routes immédiatement dans le voisinage. Audelà de cette zone prédéfinie, le protocole hybride fait appel aux techniques des protocoles

réactifs pour chercher des routes. Avec ce découpage, le réseau est partagé en plusieurs zones, et la recherche de route en mode réactif peut être améliorée. A la réception d'une requête de recherche réactive, un n°ud peut indiquer immédiatement si la destination est dans le voisinage ou non, et par conséquent savoir s'il faut aiguiller ladite requête vers les autres zones sans déranger le reste de sa zone. Ce type de protocole s'adapte bien aux grands réseaux, cependant, il cumule aussi les inconvénients des protocoles réactifs : messages de contrôle périodiques, plus le coût d'ouverture d'une nouvelle route.

II.2.3.1 Le protocole de routage ZRP

ZRP [Haa97] est un protocole hybride. Chaque n°ud définit une zone autour de lui dans laquelle il va utiliser son protocole proactif. Le protocole proactif en lui-même n'est pas imposé par ZRP, et en principe il peut être tout type de protocole proactif. La zone du n°ud est limitée en nombre de sauts entre le centre et les n°uds frontière (voir figure 2.7). Autrement dit un n°ud appartient à la zone s'il est à x sauts au maximum du n°ud central. Les n°uds qui se trouvent à la limite de cette zone sont appelés les n°uds périphériques. Un deuxième protocole réactif opère en dehors de cette zone, qui permet de chercher une route vers une destination à l'extérieur. Ce protocole réactif qui n'est pas spécifié non plus, et intervient entre les différentes zones.

Lorsqu'un n°ud veut en joindre un autre, il regarde tout d'abord s'il est dans sa zone ou non. S'il est présent dans sa zone, alors la route est connue et disponible immédiatement grâce au protocole proactif ; sinon, une requête est envoyée aux n°uds périphériques qui à leur tour regardent si le n°ud recherché appartient à leurs zones respectives. Si c'est le cas, une réponse est envoyée à la source. Dans le cas contraire, le processus se poursuit de la même façon jusqu'à trouver le n°ud en question. Une réponse est alors formulée et renvoyée à la source. Chaque n°ud maintient une liste des requêtes traitées de manière à éviter les doublons qui seront détruits.

En résumé, ZRP définit donc deux types de protocoles l'un fonctionnant localement, et le deuxième fonctionnant entre les zones :

- IARP [ZHM01](IntrAzone Routing Protocol) offrant les routes optimales vers les destination qui se trouvent à l'intérieur de la zone à une distance déterminée, et tout changement est répercuté à l'intérieur seulement.(voir figure 2.7).

- IERP [ZHM01] (IntErzone Routing Protocol) quant à lui s'occupe de chercher des routes à la demande pour des destinations en dehors d'une zone.

Figure 2.7 : Exemple de zone TARP dans ZRP

En plus ZRP utilise un troisième protocole appelé BRP [ZHM01] (Broadcast Resolution Protocol). Ce protocole utilise les données sur la topologie fournies par le protocole TARP pour construire sa liste des n°uds de périphérique et la façon de les atteindre. Tl est utilisé pour orienter la propagation des requêtes de recherche de route de l'TERP dans le réseau.

Le routage et la maintenance de la route dépendent du protocole réactif utilisé. En d'autres termes, si le protocole utilise «source routing >> comme DSR, alors, des améliorations peuvent être faites pour raccourcir la route en cours d'utilisation. Ou encore sans« source routing >> à la façon d'AODV, il faudra corriger les tables de routage des n°uds. Mais, dans tous les cas, et grâce au protocole proactif, les liens défectueux contenus initialement dans le résultat de la recherche de route ont des chances d'être détournés en cours de communication.

II.2.3.2 Le protocole de routage CBRP

Dans le "Protocole de Routage Basé sur les Groupes" appelé CBRP (Cluster Based Routing Protocol), l'ensemble des noeuds du réseau est décomposé en groupes [Jia99]. Le principe de formation des groupes est le suivant : Un noeud p qui n'a pas de statut (i.e. qui n'est ni membre ni représentant de groupe), active un timer et diffuse un message "Hello". Lorsqu'un représentant de groupe reçoit le message "Hello", il envoie immédiatement une réponse à l'émetteur. Lors de la réception de réponse, le noeud p change son état "indécis" à l'état "membre". Sip dépasse un certain timeout en attendant la réponse et dans le cas où il possède un lien bidirectionnel vers au moins un noeud voisin, il considère lui-même un représentant de groupe. Dans le cas contraire, p reste dans l'état indécis et il répète la même procédure. A

cause des changements rapides de la topologie des réseaux ad hoc, l'attente des n°uds indécis est très courte.

Afin de sauvegarder la répartition des noeuds dans les groupes, chaque noeud maintient une table des voisins. Chaque entrée de cette table est associée à un voisin, elle indique l'état du lien (uni ou bidirectionnel), et le statut du voisin (membre ou représentant de groupe). Un représentant de groupe, maintient les informations des membres qui appartiennent à son groupe. Il possède aussi une table des groupes adjacents. Une entrée dans cette table est associée à un groupe voisin, elle contient : l'identificateur du groupe, et l'identificateur du noeud de liaison à travers lequel le groupe peut être atteint (voir la figure suivante).

La table des groupes adj acents Grou^pe Nd liaison Nd re^présentant

La table des voisins
Voisin Statut Etat de lien

1 3

Les membres du groupe

5

6

7

8

5 2

membre re^présent

5 8

uni d bi d.

1 3

6

Groupe2

7

2

5

8

1

3

4

Groupe3

9

Groupe1

Figure 2.8: L'organisation du réseau dans le CBRP.
Le routage dans le protocole CBRP se fait de la manière suivante : quand un noeud source
veut envoyer des données à un noeud destination, il diffuse par inondation une requête de
demande de chemin, et cela uniquement aux représentants des groupes voisins. Un
représentant de groupe qui reçoit la requête de demande, vérifie en utilisant sa table de
membres de groupes, l'existence du noeud destination dans son groupe. Si la destination
existe, le représentant y envoie directement la requête, dans le cas contraire, la requête est
diffusée aux représentants des groupes voisins. L'adresse des représentants des groupes est
incluse dans la requête de demande de chemin, un représentant de groupe ignore toute requête
déjà traitée. Quand la destination reçoit le paquet contenant la requête, elle répond par l'envoi
du chemin qui a été sauvegardé dans le paquet de la requête. Dans le cas où le noeud source

ne reçoit pas de réponse en expirant une certaine période, il envoie de nouveau une requête de demande de chemin.

Lors de l'acheminement des données, si un noeud détecte qu'un lien est défaillant, il fait retourner un message d'erreur à la source et il applique un mécanisme de réparation locale. Dans ce mécanisme, si un noeud p trouve qu'un noeud suivant n, ne peut pas être atteint, il essaie de vérifier si le noeud n ou le noeud qui vient après n, peuvent être atteints à travers un autre noeud voisin. Si l'un des deux cas est vérifié, les données sont envoyées en utilisant le chemin réparé.

III. Conclusion

Dans ce chapitre nous avons présenté quelques protocoles de routage du groupe MANET qui ont été proposés pour assurer le service de routage dans les réseaux mobiles ad hoc. Il existe G'autres protocoles qui ont été développés dans la littérature. Le groupe MANET qui a pour mission la normalisation des travaux qui sont effectués sur les réseaux ad hoc, s'efforce de trouver des protocoles adéquats et standards.

Nous avons décrit leurs principales caractéristiques et fonctionnalités afin de comprendre les stratégies utilisées dans l'acheminement des données entre les différents noeuds. Les protocoles proposés sont généralement classés en deux catégories : les protocoles proactifs et les protocoles réactifs. Les protocoles des deux catégories essayent de s'adapter aux contraintes imposées par les réseaux ad hoc, et cela en proposant une méthode qui soit de moindre coût en capacités et ressources, et qui garantit la disponibilité du routage en cas de panne de lien ou de n°uds. Les protocoles de routage étudiés offrent différents avantages qui sont en réalité complémentaires et préférables pour différents types d'applications. Les réseaux ad hoc doivent s'organiser automatiquement de façon à être déployables rapidement et pouvoir s'adapter aux conditions de propagation, au trafic et aux différents mouvements pouvant intervenir au sein des noeuds. Dans le but d'assurer la connectivité du réseau malgré l'absence d'infrastructure et la mobilité des stations, chaque n°ud est susceptible d'être mis à contribution pour participer au routage et pour retransmettre les paquets d'un n°ud qui n'est pas en mesure d'atteindre sa destination. Chaque n°ud joue ainsi le rôle de station et de routeur. Chaque n°ud participe donc à une stratégie de routage qui lui permet de découvrir les chemins existants, afin d'atteindre les autres n°uds du réseau. Après avoir fait une étude sur les protocoles de routage, nous présentons dans le prochain chapitre, différents types de mobilité des n°uds dans un réseau ad hoc. Cette étude nous

permettra d'avoir un jugement correct sur le fonctionnement de chaque protocole de routage par rapport à un type de mobilité bien défini.

CHAPITRE III : LES MODELES DE MOBILITE DANS LES RESEAUX AD HOC

I Introduction

Afin d'évaluer les performances d'un protocole, ce dernier doit être testé sous plusieurs modèle de mobilité des neuds. Un tel modèle doit être capable d'imiter le mouvement des noeuds tel que souhaité dans un certain scénario. Comme les domaines d'application des réseaux ad hoc sont très vastes et que ces réseaux ne sont pas encore utilisés, ceci rend l'obtention de telles traces impossible. D'où la nécessité d'utiliser des modèles synthétiques qui ont pour rôle d'exprimer le comportement des noeuds sans l'usage de traces réelles. Plusieurs modèles sont définis dans la litt érature afin de simuler le comportement des neuds. Ces modèles sont répartis en deux classes, selon le mode de déplacement des neuds. Dans la première classe (modèles de mobilité par entité), les neuds se déplacent indépendamment les uns des autres. Tandis que dans la deuxième (modèles de mobilité par groupe), les neuds se déplacent en groupe.

Nous allons donc étudier les différents modèles de mobilité afin d'avoir une vue sur les modèles existants.

II Les modèles individuels

Dans ces modèles, chaque noeud se déplace indépendamment des autres. Ces modèles peuvent être classés selon l'aspect aléatoire de leur mouvement, soit un mouvement absolument aléatoire sans aucune mémoire du passé, soit un mouvement souple où les variations de la vitesse, direction et position à chaque instant sont fonction de l'état précédent. II.1 Les modèles sans mémoire

Dans ces modèles, un noeud choisit une position et une vitesse d'une façon absolument aléatoire et sans aucune mémoire du passé. Dans ces modèles, on peut avoir fréquemment des comportements extrêmes des noeuds comme un arrêt soudain, une accélération soudaine et des tours brutaux. Les modèles existants dans cette catégorie sont :

II.1.1 Random Walk(RW)

Dans ce modèle, chaque neud dans la simulation choisit aléatoirement un angle de direction entre 0 et 2ir et une vitesse entre Vmin et Vmax. Le déplacement du noeud se fait pendant un temps t ou d'une distance d. D'après [San01], ce modèle était premièrement décrit mathématiquement par Einstein en 1926. A la fin de son voyage, le neud choisit une nouvelle

direction et une nouvelle vitesse et se déplace de nouveau. On peut bien remarquer que le changement de la direction et de la vitesse sont absolument aléatoires et indépendant du choix précédent. La Figure 3.1 montre le mouvement d'un noeud qui voyage pendant un temps de t secondes alors que dans la Figure 3.2, le noeud se déplace d'une distance d définie.

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

Figure 3.2 : Random Walk (Déplacement d'une distance d)

II.1.2 Random Waypoint(RWP)

Ce modèle était d'abord utilisé par Johnson et Maltz dans l'évaluation du protocole de routage DSR [JMH03] et était ensuite raffiné par les mêmes auteurs. Le Random Waypoint est pour modéliser tous les scénarios dans lesquelles, les noeuds se déplacent vers une destination, prennent un repos en arrivant, avant de se déplacer vers une autre destination et ainsi de suite. Dans ce modèle chaque noeud choisit aléatoirement, comme destination un point de

coordonnées (x, y) dans la surface de simulation, et une vitesse entre 0 et Vmax. Le noeud voyage vers la destination choisie avec la vitesse choisie. A l'arrivée, le noeud prend un temps de repos avant de choisir à nouveau une nouvelle destination et une nouvelle vitesse pour répéter le même processus. Des études ont été faites sur ce modèle puisqu'il est le modèle le plus utilisé dans les simulations dû à la facilité de son implémentation. Certaines études ont traité l'initialisation de ce modèle et le temps de convergence des simulations dans le cas où les n°uds commencent par prendre un temps de repos. Dans [YLN03], on montre que le Random Waypoint, dans sa forme courante, n'atteint pas un état d'équilibre, mais plutôt que la vitesse diminue sans interruption pendant que la simulation progresse, ce qui peut fausser les résultats. Basés sur les analyses faites, les auteurs proposent une solution simple qui est de choisir une valeur strictement positive pour la vitesse minimale. Dans l'article [NCB03], les auteurs montrent que la vitesse moyenne peut prendre plus que 1000 secondes du temps de simulation pour converger, si la vitesse minimale est petite. Les auteurs montrent comment implémenter un générateur de modèle de mobilité équilibré pour le Random Waypoint, vu que, si les valeurs initiales de la position et de la vitesse sont choisies d'une distribution stationnaire, la convergence est immédiate. Dans l'article [BHP02], on présente une analyse mathématique de quelques propriétés stochastiques du Random Waypoint et on donne un arrangement plus profond du comportement de ce modèle comme par exemple l'effet que les noeuds tendent à se déplacer au centre de la surface de simulation. On remarque que le Random Waypoint est proche du Random Walk à la différence près que la destination choisie est toujours un point intérieur à la surface de simulation, ce qui élimine tout effet de bord. La Figure 3.3 présente le déplacement d'un noeud utilisant le Random Waypoint.

II.1.3 Random Direction(RD)

Le Random Direction a été créé pour éviter l'effet de concentration des noeud au centre produit par le Random Waypoint [Bet01]. Dans ce modèle, chaque noeud choisit aléatoirement, comme dans le Random Walk, une direction qui est un angle entre 0 et 2ir et une vitesse entre Vmin et Vmax. La différence entre ce modèle et le Random Walk est qu'ici le noeud ne voyage pas pendant un certain temps ou d'une certaine distance mais se déplace suivant la direction choisie jusqu'à atteindre le bord de la surface de simulation où il prend un temps de repos. Une fois le temps de pause terminé, le noeud choisit de nouveau et aléatoirement une nouvelle direction et une nouvelle vitesse et répète le même processus. La Figure 3.4 montre un noeud utilisant le Random Direction comme modèle de mobilité. La position initiale du noeud est au centre de la surface de simulation. Le noeud commence à se déplacer et chaque fois il se déplace jusqu'au bord où il prend un temps de repos avant de changer sa direction et sa vitesse.

Figure 3.4 : Random Direction

II.1.4 Restricted Random Waypoint

Ce modèle était, pour la première fois, décrit dans [BGY0 1]. L'idée de ce modèle de mobilité est extraite du fait que la plupart des gens se déplacent pour un certain temps dans une même localité avant d'aller vers une autre localité. Donc dans ce modèle, la surface de simulation contient des rectangles qui représentent des villes liées par des autoroutes. Chaque n°ud utilise le Random Waypoint pour se déplacer dans l'une des villes un certain nombre de fois spécifiées par un paramètre, avant de voyager vers une autre ville où il va se déplacer pour un certain moment et ainsi de suite. La Figure 3.5 montre le déplacement d'un noeud utilisant le Restricted Random Waypoint. Les villes sont représentées par des rectangles. Le noeud se déplace de quatre étapes dans la même ville avant de voyager vers une autre ville.

Figure 3.5 : Restricted RWP

II.2 Les modèles avec mémoire

Dans ces modèles, appelés aussi corrélés, la vitesse et la direction à chaque instant, dépendent de l'instant précédant. Les modèles corrélés existants sont :

II.2.1 Boundless

Dans ce modèle la position et la vitesse d'un noeud à tout instant (t+At), dépendent de la

position et de la vitesse à l'instant t. La position (x,y)du mobile et sa vitesse í sont mises à jour chaque At unité de temps comme suit [Haa97] :

v(t+At)= min [max(v(t) + Av, 0), Vmax]; (1)

0(t+At)= 0(t) + A0 ; (2)

Vmax : La vitesse maximale.

Av : Le changement de vitesse distribuée uniformément entre [-Amax*At, Amax*At] Amax : Accélération maximale q'un noeud peut avoir.

AO : La variation de la distribution, distribuée uniformément entre [-a* At, a* At] a :Valeur maximale du changement d'angle q'un noeud peut avoir.

La figure 3.6 montre un exemple Pour une valeur de At =0.2s, si l'accélération maximale est de 100, on aura une variation de vitesse entre [-20, 20] donc la vitesse du noeud peut diminuer ou augmenter ; il en est de même pour la variation d'angle.

Le Boundless a un effet de bord différent des modèles déjà cités. Un noeud qui atteint le bord, continue pour sortir et rentrer de l'autre coté de la surface de simulation.

A cause de cet effet de bord, les noeuds dans ce modèle, se déplacent comme si les bords de la simulation n'existaient pas. L'action d'un noeud qui sort et rentre de l'autre côté, est semblable à celle d'un noeud qui sort définitivement de la simulation avec un nouveau qui arrive en même temps pour le remplacer.

II.2.2 Gauss Markov

Le modèle de mobilité Gauss Markov été proposé dans [LHa99]. Ce modèle était utilisé pour la simulation d'un protocole pour les réseaux ad hoc [Tol99]. Gauss Markov est un modèle de mobilité semblable à Boundless, dans le sens que la position et la vitesse à tout instant, dépendent de la position et de la vitesse au moment précédent. La vitesse, la direction et la position d'un noeud varient selon les formules suivantes :

íáíáíáí

=-+-+ -

(1)(1²)(3)

n n x_n

1 - 1

d ddd

= - +-+ -

(1)(1²)(4)

n n x_n

ááá

1 - 1

í n : Vitesse à un instant n.

d_n : Direction à un instant n.

á : Paramètre compris entre [0,1], utilisé pour faire varier l'aspect aléatoire du déplacement. í : Valeur fixe qui représente la vitesse moyenne lorsque n--co

d : Valeur fixe qui représente la direction moyenne lorsque n--co

í ^xn- 1 et dxn-1 : Variables aléatoires tirées d'une distribution Gaussienne.

Figure 3.7 : Changement de la valeur moyenne d'angle

Figure 3.8 : Gauss Markov

Un effet absolument aléatoire est obtenu en plaçant a = 0 et un effet linéaire est obtenu en plaçant1a = 1. Pour d'autres valeurs de a, la vitesse et la direction à chaque instant, sont calculées à partir de la valeur à l'instant précédant + une petite variation aléatoire tirée de la distribution gaussienne. Pour s'assurer qu'un noeud ne reste pas près d'un bord de la simulation, les noeuds sont poussés loin du bord quand ils sont à moins d'une certaine

distance du bord. Cet effet est réalisé en modifiant la valeur de la direction moyenne d au cours de la simulation. Par exemple, lorsqu'un noeud est proche du bord droit, la valeur de

d change à 1 80o, alors la nouvelle direction du noeud l'éloigne du bord de la simulation. La Figure 3.7 présente le schéma des variations de la valeur moyenne de direction qu'un noeud va prendre, une fois qu'il est proche d'une distance d (définie) de l'un des bords de la

simulation. La Figure 3.8 montre le déplacement d'un noeud utilisant le modèle Gauss Markov.

On peut bien remarquer pour les deux modèles déjà cités (Boundless et Gauss Markov), que les valeurs de la vitesse, de la direction et de la position à chaque instant, dépendent des valeurs à l'instant précédent ce qui crée un mouvement plus souple des noeuds.

II.2.3 Markovian Random Path

Le Markovian Random Path, appelé aussi A Probabilistic Version of Random Walk et qui était, pour la première fois, proposé par Chiang dans [Chi98], utilise une chaîne de Markov pour modéliser le mouvement d'un noeud. La chaîne de Markov est une suite de variables

aléatoires (Xn) telle que, pour chaque n, ^Xn+1 soit indépendante de Xk, pour k= n-1, et dépend uniquement de Xn. Dans ce modèle, les mouvements des noeuds sont séparés en

directions horizontales et verticales [CAV04], chaque direction représentant une variable aléatoire. La Figure 3.9 montre le schéma de la chaîne de Markov utilisée pour faire varier les coordonnés d'un noeud dans chaque mouvement :

Figure 3.9 - Schéma de passage pour le Markovian Random Path.

Fi^gure 3.10-Markovian Random Path

- L'état (0) : Garder les mêmes coordonnés (x, y).

- L'état (1) : La position incrémente.

- L'état (2) : La position décrémente.

- p et q sont les probabilités de passage d'un état à l'autre selon le schéma dans Figure 3.9.

Le déplacement est d'une distance d fixe. On a donc deux chaînes de Markov, une pour le déplacement suivant l'axe des x et l'autre pour le déplacement suivant l'axe des y. Selon la valeur des probabilités p et q, les coordonnés (x, y) d'un noeud vont augmenter, diminuer ou rester stables. Par exemple, pour une valeur élevée de p, un noeud a plus de chance de se déplacer en avant plutôt qu'en arrière. Voici un exemple de matrice qui peut être utilisée pour varier les coordonnés d'un noeud:

0	0.5	0.5 ?
P= ? 0.3 ?	0.7	0 ? ?
0.3	0	0.7 ? ?

Chaque nombre dans cette matrice, représente la probabilité de passage de l'état (numéro de ligne) à l'état (numéro de colonne). Le 0 situé dans la 2ème ligne, 3ème colonne, représente la probabilité de passage de l'état (2) à l'état (3).

La Figure 3.10 montre le déplacement d'un noeud utilisant le modèle « Markovian Random Path ».

II.2.4 City Section (CS):

Le City Section modélise le déplacement des noeuds (Voitures, camions, gens, . .) dans une vile. Dans ce modèle [Dav00], la surface de simulation, représentée par une grille, symbolise

des rues horizontales et verticales dans une ville. Au lieu de spécifier une vitesse maximale aux noeuds, on spécifie une vitesse limite pour les routes. Chaque noeud commence la simulation sur un point prédéfini, qui est l'intersection de deux routes. Le noeud choisit aléatoirement une destination, qui est aussi l'intersection de deux routes, et commence son voyage vers cette destination en choisissant le chemin qui nécessite le moins de temps pour arriver. A son arrivé, le noeud choisit une nouvelle destination et répète le même processus, sans prendre un temps de repos. Dans ce modèle, on peut utiliser les cartes géographiques réelles avec la possibilité d'avoir des règles de sécurité de conduite comme la distance entre deux noeuds consécutifs ou une limitation de la vitesse d'un noeud. Des modifications ont été faites sur ce modèle en combinant les cartes avec des obstacles pour essayer de créer un modèle plus proche de la réalité [JEB03]. Ces obstacles représentent des bâtiments à l'intérieur desquels les noeuds peuvent entrer et sortir. La Figure 3.11 représente le déplacement d'un noeud utilisant le City Section, du point (1,4) au point (5,1). Dans ce schéma, on a trois types de routes représentées par des lignes singulières, des points ou des lignes doubles avec des vitesses différentes pour chaque type de route.

Figure 3.11 : City

II.2.5. Le modèle de mobilité avec obstacles

Le modèle de mobilité avec obstacles [CJL01] a été conçu pour modéliser le mouvement des n°uds mobiles dans les terrains qui ressemblent à des topographies réelles. Des objets modélisent les bâtiments et d'autres structures qui empêchent les mouvements des n°uds, ainsi que leur transmission sans fil. En modélisant un tel terrain, un utilisateur peut définir les

positions, les formes et les tailles de ces objets. Ce modèle peut manipuler des formes et des positions arbitraires pour les objets, permettant de modéliser beaucoup de terrains réels. Le deuxième composant du modèle de mobilité est un graphe de mouvement qui représente les déplacements des n°uds. Ce graphe planaire est le diagramme de Voronoï [Bra05] des coins des obstacles (les arêtes sont des segments qui sont à une distance égale des deux coins d'un obstacle). Ainsi, ce modèle est basé sur l'intuition que les chemins tendent à se définir à mi-distance entre les bâtiments adjacents. Ce modèle permet également le mouvement par l'intérieur des bâtiments.

Le troisième composant du modèle est le choix des routes. Les n°uds utilisent les chemins les plus courts (en terme de distance euclidienne) pour se déplacer entre deux points du graphe du mouvement, c'est-à-dire qu'ils suivent le chemin le plus court dans le diagramme de Vornoï. Le placement des objets et des chemins les reliant sont calculés au début de la simulation et ne changent pas pendant toute la simulation. Les n°uds sont distribués au hasard le long des chemins, ils choisissent une destination et puis se déplacent vers cette destination en suivant le chemin le plus court à partir de sa position courante.

Figure 3.12 : Mouvements avec obstacles utilisant le diagramme de Vornoï

Ainsi, chaque n°ud calcule le chemin le plus court sur le graphe créé par les chemins et puis se déplace vers cette destination en utilisant le chemin calculé. Lorsqu'il atteint sa destination, le n°ud fait une pause pour une certaine période de temps. Il choisit alors une nouvelle destination, calcule le chemin le plus court pour l'atteindre, et reprend le mouvement. Les n°uds peuvent se déplacer à l'intérieur des bâtiments car le plus court chemin entre deux endroits peut exiger le passage par l'intérieur d'un bâtiment.

III. Les modèles de groupe

On remarque bien dans les modèles par entité déjà cités, qu'un noeud se déplace indépendamment des autres n°uds. Sa vitesse, position et direction de mouvement ne sont pas affectées par d'autres n°uds. Ces modèles singuliers ne sont capables de capturer que certains scénarios. Dans quelques applications comme les secours en cas de désastre ou les champs de bataille, la collaboration d'équipe existe, les membres d'une équipe suivent leur chef et les mouvements d'un membre peuvent être influencés par les membres du voisinage. Nous avons donc besoin des modèles de groupe pour simuler certains scénarios.

Dans un modèle de groupe, les n°uds se déplacent ensemble comme un groupe de soldats par exemple qui a une certaine mission à accomplir. Les modèles de groupe qui existent sont les suivants :

III.1. Le modèle exponentiel aléatoire corrélé

Dans ce modèle, le mouvement de chaque groupe est contrôlé indépendamment des autres groupes. A chaque étape de temps, un groupe se déplace d'une distance aléatoire dans une direction aléatoire. Chaque noeud change ses coordonnées polaires, qui sont une distance et un angle, selon la formule suivante [BAl96]:

bt bteer

(1) ()^1/ô õó ₁2/ô

+ = -+- -

- b (t) : position (r,e) d'un noeud ou d'un groupe de noeuds à un temps t. - r : Variable Gaussienne de variancec^y

- u : Vitesse d'un noeud.

- t : Variable permettant de régler le taux de changement de la position ancienne à la nouvelle position.

III.2. Modèle de mobilité de colonne

Dans ce modèle, chaque groupe de noeuds, peut avoir une ou plusieurs références. Une référence est un n°ud du groupe qui a pour rôle de guider les autres n°uds pendant leur déplacement. Au début de la simulation, les références de chaque groupe sont placées d'une façon formant une colonne et chaque noeud est placé en relation avec sa référence, autour de laquelle, il a le droit de se déplacer en utilisant l'un des modèles de mobilité par entité [San01]. Une référence peut avoir un seul noeud autour d'elle. La position de l'axe des références change de la manière suivante (Figure 3.13) :

Nouvelle_position (références) = ancienne_position (références) + vecteur anticipé.

Le vecteur anticipé est calculé suivant un angle aléatoire entre 0 et it radian (puisque le déplacement est seulement en avant) et une distance aléatoire.

référence

Nceud mobile

angle

Figure 3.13 - Mouvement des noeuds utilisant le modèle Column

Figure 3.14 : Column

La Figure 3.14 montre le déplacement d'un groupe formé de trois références, avec un seul noeud, utilisant le Random Walk, autour de chaque référence. Les références sont en noir alors que les autres noeuds sont en couleur.

III-3. Le modèle de mobilité de communauté nomade (NCMM)

Dans ce modèle, chaque groupe de noeuds possède un seul point référence en commun [San01]. Les noeuds de chaque groupe se déplacent autour de leur point référence en utilisant un modèle de mobilité par entité (Random Walk) et ne peuvent pas la dépasser d'une certaine distance, précisée dans les paramètres, et qui est la distance maximum entre un noeud et sa référence. Le déplacement d'une référence se fait aussi suivant un modèle singulier. La Figure 3.15 montre le déplacement d'un groupe de cinq noeuds, présentés en couleur, autour de leur référence qui est en noir. Les noeuds ainsi que la référence, utilisent le Random Walk.

Quand le point de référence change, tous les n°uds mobiles dans le groupe se déplacent vers le nouveau secteur défini par le point de référence et commencent à errer autour du nouveau point de référence (Figure 3.16).

Figure 3.15 : Nomadic Community

Figure 3.16 : Modèle de mobilité de communauté nomade

III-4. Le modèle de mobilité de poursuite

Le modèle de mobilité de poursuite contient, comme Nomadic Community, un seul point de référence. La différence est que la référence joue ici le rôle d'une cible qui est poursuivie par les autres noeuds, comme le mouvement d'un groupe de policiers essayant d'attraper un voleur. La position de chaque noeud dans le groupe varie de la manière suivante [San01]:

Nouvelle_position = position_ancienne + accélération (cible) + vecteur_aléatoire. Accélération (cible) est une information sur le déplacement de la cible et le vecteur aléatoire est le mouvement d'un noeud selon un modèle de mobilité singulier (Random Walk par exemple). Ce mouvement est limité puisqu'il s'agit de poursuivre la cible sans la dépasser. La Figure 3.17 illustre le déplacement d'un groupe utilisant le modèle Purse. Le noeud en blanc représente la référence.

Figure 3.17 : Purse

III-5. Le modèle de mobilité d'un groupe avec point de référence(RPGM)

Le modèle de mobilité d'un groupe avec point de référence noté RPGM (Referenced Point Group Mobility Model) [BMR02, Cla04] représente le mouvement aléatoire d'un groupe de n°uds aussi bien que le mouvement aléatoire de chaque n°ud individuellement dans le groupe. Les mouvements du groupe sont basés sur le chemin parcouru par un centre du groupe qui est utilisé pour calculer le mouvement du groupe par l'intermédiaire d'un vecteur

de mouvement GM qui peut être choisi aléatoirement ou être prédéfini.

Le mouvement du centre du groupe caractérise complètement le mouvement de son groupe (la direction et la vitesse). Les n°uds individuels se déplacent aléatoirement par rapport à leurs propres points de référence prédéfinis, dont les mouvements dépendent du mouvement du groupe.

La Figure 3.18 illustre le mouvement de 3 noeuds utilisant le modèle RPGM. Ainsi, à l'instant t, les 3 points noirs représentent les points de référence, RP (t) pour les trois n°uds. Le

modèle RPGM utilise le vecteur GM pour calculer les nouveaux points de référence, RP (t + 1), à l'instant t + 1). La nouvelle position de chaque n°ud est alors calculée par la

somme vectorielle du vecteur GM avec un vecteur aléatoire de mouvement, RM. La

longueur de RM est uniformément distribuée dans un disque qui a pour centre RP (t + 1), tandis que sa direction est uniformément distribuée dans [0.. 2?].

Le modèle RPGM a été conçu pour faire face à des scénarios tels qu'une avalanche après laquelle une équipe de secours se composant d'humains et de chiens, travaillent en coopération. Les guides humains (centre des groupes) tendent à définir un chemin général puisqu'ils connaissent habituellement l'endroit approximatif des victimes. Chacun des chiens crée son propre chemin aléatoire autour du secteur général choisi par leurs guides humains.

Figure 3.18 : Mouvements de 3 n°uds utilisant le modèle RPGM

IV. Discussions sur les modèles de mobilité [BGY01]

La performance d'un protocole de réseau ad hoc peut changer de manière significative quand il est testé avec différents modèles de mobilité, mais aussi quand le même modèle de mobilité est utilisé avec différents paramètres. De plus, le choix d'un modèle exige un modèle de trafic de données qui influence aussi sur la performance du protocole. Par exemple, quand on simule un modèle de mobilité de groupe, l'évaluation du protocole devra prendre en compte l'aspect local d'une partie du trafic à l'intérieur du groupe. La performance d'un protocole de réseau ad hoc devrait être évaluée avec le modèle de mobilité qui est le plus proche du scénario réel prévu, ce qui peut faciliter le développement du protocole de réseau ad hoc.

Le modèle de mobilité de promenade aléatoire, RW, avec un petit paramètre d'entrée (distance ou temps) produit un mouvement Brownien et, en conséquence, évalue fondamentalement un réseau statique quand il est utilisé pour l'évaluation de la performance. Par contre, avec l'utilisation d'un grand paramètre d'entrée, le modèle RW ressemble au modèle de mobilité RWP si on y ajoute des temps de pause. La différence principale entre ces deux modèles est que les n°uds simulant le modèle RWP ont plus tendance à se grouper au centre du secteur de simulation, que les n°uds simulant le modèle RW. Le modèle RWP est utilisé dans beaucoup d'études de protocoles de réseau ad hoc. Il est flexible, et il semble créer des modèles de mobilité réalistes. Un inconvénient de ce modèle est la ligne droite du mouvement suivi par le n°ud mobile qui se déplace vers la prochaine destination choisie.

Le modèle de mobilité de direction aléatoire, RD, est un modèle peu réaliste parce qu'il est peu probable que les dispositifs se disperseraient aléatoirement dans tout le secteur (un bâtiment ou une ville). En outre, il est peu probable qu'ils feront une pause seulement au bord

de la frontière d'un secteur. Le modèle de direction aléatoire modifié permet aux n°uds de faire une pause et de changer de direction avant d'atteindre la frontière du secteur de simulation. Cependant, cette version est identique au modèle de mobilité de promenade aléatoire, RW, en y ajoutant des temps de pause.

Le modèle de mobilité dans une région de simulation illimitée fournit des modèles de mouvement auxquels on pourrait s'attendre dans la réalité. En outre ce modèle est le seul qui permet aux noeuds mobiles de se disperser dans le secteur, en éliminant les effets de la frontière sur l'évaluation des performances. Cependant, les effets secondaires qui se produiraient en permettant aux noeuds mobiles de se déplacer autour d'un tore (torus) pourraient être considérables. Par exemple, un noeud mobile qui se déplace dans la même direction vers un noeud statique deviendra son voisin à plusieurs reprises.

Le modèle de mobilité Gauss-Markov fournit des modèles de mouvement auxquels on pourrait s'attendre dans la réalité si des paramètres appropriés sont choisis. En outre, la méthode utilisée pour forcer les noeuds à partir loin des bords du secteur de simulation (évitant ainsi les effets du bord de secteur) est intéressante.

Même si le modèle probabiliste de promenade aléatoire fournit des mouvements auxquels on pourrait s'attendre dans la réalité, choisir des paramètres appropriés pour sa matrice de probabilité peut être difficile.

Le modèle de mobilité des sections de ville, CS, semble créer des mouvements réalistes pour une section d'une ville, puisqu'il limite sévèrement le comportement des déplacements des noeuds mobiles. Ces noeuds n'ont pas la capacité d'errer librement sans se soucier des obstacles et d'autres règlements de trafic.

Concernant les cinq modèles synthétiques de mobilité de groupe pour les réseaux ad hoc, on pourrait dire que le modèle exponentiels aléatoire corrélé semble décrire théoriquement tout autre modèle de mobilité. Cependant, le choix des valeurs appropriées pour les paramètres IJ et o- est très difficile. Les modèles de colonne, de la communauté nomade et de poursuite sont des modèles utiles pour des scénarios réalistes spécifiques. Les modèles de mouvement qu'ils fournissent peuvent être obtenus en changeant les paramètres liés au modèle d'un groupe avec point de référence (RPGM). Enfin, un modèle de mobilité d'entité doit être conçu non seulement pour manipuler le mouvement d'un groupe de noeuds mobiles, mais aussi le mouvement des n°uds individuellement à l'intérieur du groupe.

Ce que tous ces modèles de mobilité ont en commun est que les modèles qu'ils créent ne sont pas nécessairement comparables aux mouvements dans la réalité. En particulier, les gens sur des campus universitaires ou dans des centre commerciaux ne se déplacent généralement pas

en directions aléatoires. Ils tendent à choisir une destination spécifique et à suivre un chemin bien défini pour atteindre cette destination. Le choix du chemin est influencé par les voies et les obstacles présents. Par exemple, sur un campus universitaire, les individus marchent généralement sur les chemins qui sont faits pour relier ensemble les bâtiments du campus, tandis que certains individus peuvent emprunter des chemins à travers les pelouses. En plus, les destinations ne sont typiquement pas aléatoires, mais sont des bâtiments, des bancs dans un parc, ou d'autres endroits spécifiques dans le campus.

V. Conclusion

Dans ce chapitre, nous avons vu différents modèles de mobilité pour les réseaux ad hoc.

Ces modèles ont été classifiés en deux catégories à savoir les modèles de mobilité par entité et les modèles de mobilité par groupe.

Dans les modèles d'entité, les déplacements des n°uds n'ont aucun rapport entre eux alors que dans les modèles de groupe, les déplacements des n°uds appartenant à un même groupe sont synchronisés.

Dans les prochains chapitres, nous allons voir l'impact de certains de ces types de mobilité sur les protocoles de routage en faisant des simulations avec des types de mobilité différents.

CHAPITRE IV : SIMULATION ET INTERPRETATION DES
RESULTATS

I Introduction

Suite à l'expansion impressionnante des réseaux informatiques un besoin de plus en plus pressant de recherches dans le domaine s'est fait sentir. Devant la complexité des problèmes concernés et la grande diversité des architectures rencontrées, de nombreuses solutions sont envisageables pour un même problème. Chacune des solutions envisagées doit alors être testée, évaluée, caractérisée et critiquée avant d'envisager son implémentation concrète dans un réseau. La simulation, un moyen permettant d'effectuer ces tests, est une technique de modélisation du monde réel sur une plate forme réduite, elle permet de représenter le fonctionnement d'un système composé de différents centres d'activités, de mettre en évidence leurs caractéristiques et les interactions entre eux, de décrire la circulation des différents objets traités par ce processus et enfin d'observer le comportement du système dans son ensemble et son évolution dans le temps.

Dans ce chapitre, nous parlerons des différents environnements de simulation tout en mettant l'accent sur le Network Simulateur (NS2) qui a été utilisé pour nos simulations. Nous parlerons des spécifications et modes d'utilisations des modèles de mobilités que nous avons implémenté avant de passer à l'interprétation des résultats pour les tests, qui en sont effectués, en considérant un protocole de routage pour la classe proactive et un pour la classe réactive.

II Environnements de simulation

II.1 Définitions et concepts

a. Système discret et système continu

On distingue deux types de systèmes de simulation : le système discret et le système continu.

Le système discret: Un système discret et un système dans lequel les variables décrivant un état ne changent de valeur qu'en un nombre fini de points sur l'axe de temps.

Le système continu: Un système continu est un système dans lequel le temps s'écoule de façon continue et dans lequel les variables peuvent changer de valeur à tout instant.

Il faut noter que tout système continu peut être discrétisé. Il suffit de le décomposer en activités pouvant être considérées comme instantanées et séparées par des intervalles de temps pendant lesquels il ne se passe rien de significatif.

b. Simulation par événement discret :

La simulation par événement discret désigne la modélisation d'un système réel tel qu'il évolue dans le temps, par une représentation dans laquelle les grandeurs caractérisant les systèmes (variables) ne changent qu'en un nombre fini de points isolés dans le temps. Ces points sont les instants où se passent les événements, c'est-à-dire le phénomène capable de modifier l'état du système et nous appelons événement tout changement d'état d'un système réel se produisant à un instant donné, ainsi que les actions qui accompagnent ou caractérisent ce changement.

La simulation par événement discret consiste alors à prendre en compte, dans la modélisation des tâches actives, les seuls instants où un événement se produit et à concentrer l'activité des tâches à simuler sur ces instants là.

c. Simulateur :

Nous appelons simulateur un programme qui met en °uvre un modèle de simulation. La première tache d'un simulateur est d'assurer que la chronologie des évènements soit respectée. A chaque occurrence d'un évènement, les actions qui sont associées à celui ci sont exécutées.

d. Intérêt de la simulation :

Une expérimentation directe effectuée sur le terrain peut se révéler coûteuse, irrationnelle ou même impossible. Il serait même inconcevable dans notre étude de mettre en °uvre un réseau Ad Hoc, de déplacer les n°uds et changer les paramètres pour comparer un algorithme de routage sous différents modèles de mobilité. C'est à cause des difficultés liées à l'expérimentation directe et dans le but aussi de pouvoir examiner facilement et rapidement les variantes du système étudié que l'on cherche à réaliser un modèle de ce système dont on peut analyser numériquement le comportement et sur la base de cette analyse, inférer le comportement du système réel lui même.

II.2 les simulateurs

Beaucoup de simulateurs pour les réseaux informatiques ont été développés pour répondre aux attentes des utilisateurs. Parmi ces simulateurs, nous pouvons citer :

· OPNET [KKa] : un simulateur à caractère commercial. Il fournit des outils optimisés pour créer et tester des modèles de réseaux. Il utilise un paradigme de modélisation hiérarchique dans chaque couche pour aider les utilisateurs à effectuer des simulations à évènement discrets de grande exactitude, et à récupérer les métriques voulues. OPNET est facile à utiliser et est relativement extensible.

· GloMosim[KfK05]: un simulateur basé sur un ensemble de modules et de bibliothèque chacune d'elles simule un aspect particulier des réseaux filaires ou sans fil sur une couche particulière du modèle OSI. GloMoSim est développé en langage PARSEC (Parallel Simulation Environnement for Complex Systems) qui permet la simulation parallèle des processus via les messages et les entités indépendantes. GloMoSim est extensible vers d'autres modèles via le langage PARSEC.

· QualNet [TNS] : produit commercial dérivé de GloMoSim.

· INSANE : le simulateur INSANE est conçu dans le but de tester les algorithmes IP sur ATM avec un trafic réel dérivé d'un trafic empirique mesuré.

· NetSim [ECE02] : ce simulateur est conçu pour fournir des simulations détaillées de ETHERNET incluant la détection des collisions.

· OMNeT++ [ECE02] : distribution libre, modulaire, orienté objet et à événements discrets écrit en C++. Il est conçu pour but général. Il permet la spécification de modèles à l'aide du langage NED.

· NS2 [TCL04] : simulateur à événements discrets, écrit en C++. Il est le simulateur le plus célèbre dans le domaine de la simulation des réseaux. Le projet de NS2 a débuté en 1989 avec le simulateur réseau REAL, et a connu plusieurs extensions via les

contributions de la communauté scientifique. Il permet des simulations filaires et sans fil. C'est ce dernier simulateur que nous avons utilisé pour nos simulations.

II.3 Philosophie de NS2

L'application NS est composée de deux éléments fonctionnels : un interpréteur et un moteur de simulation. Au moyen de l'interpréteur l'utilisateur est capable de créer le modèle de simulation, ce qui revient à assembler les différents composants nécessaires à l'étude. Les composants du modèle de simulation sont appelés objets ou encore instances de classe. Le moteur de simulation quant à lui effectue les calculs applicables au modèle préalablement construit par l'utilisateur via l'interpréteur [KfK05] [PaE99].

NS est un outil de simulation de réseaux de données. Il est développé en C++ avec une interface textuelle utilisant le langage OTcl (Object Tool Command Language) qui est une extension objet du langage de commande TCL (Tool Command Language).

Il est bâti autour d'un langage de programmation appelé Tcl dont il est une extension. Du point de vue de l'utilisateur, la mise en °uvre de ce simulateur se fait via une étape de programmation qui décrit la topologie du réseau et le comportement de ses composants, puis vient l'étape de simulation proprement dite et enfin l'interprétation des résultats. Cette dernière étape peut être prise en charge par des outils annexes, à titre d'exemple le xgraph et autres. Le NS2 est aussi accompagné d'outils de visualisation graphique, le nam, permett ant

D'ob server graphiquement le comportement des objets durant la simulation.

a. Le langage TCL (Tool Command Language)

Tcl est l'acronyme de "Tool Command Language" (langage de commandes outils). Tcl est en fait divisé en deux parties : un langage et une bibliothèque.

Tcl est un langage de programmation dont le but est de passer des commandes à des programmes interactifs tels que des éditeurs de texte, des débogueurs et des interpréteurs shell. Il possède une syntaxe simple et il est lui-même programmable : les utilisateurs de Tcl peuvent en effet écrire des procédures pour créer des commandes plus puissantes que celles fournies par l'ensemble préconstruit. La bibliothèque Tcl est constituée d'un analyseur syntaxique du langage Tcl, de routines implémentant les commandes prédéfinies de Tcl, et de procédures permettant à chaque application d'ajouter à Tcl des commandes additionnelles qui lui sont spécifiques. Le programme applicatif génère des commandes Tcl et les passe à l'analyseur syntaxique de Tcl pour l'exécution.

· Tcl fournit une syntaxe standard : une fois que les utilisateurs connaissent Tcl, ils seront capables de passer facilement des commandes à n'importe quelle application basée sur Tcl.

· Tcl parvient à une bonne « programmabilité ». Tout ce qu'une application nécessite est l'implémentation de quelques commandes spécifiques de bas niveau. Tcl fournit de nombreuses commandes utilitaires et une interface générique de programmation pour construire des procédures de commandes complexes. En utilisant Tcl, les applications ne nécessitent pas de ré-implémentation de ces caractéristiques.

· Les extensions à Tcl, telles que la boîte à outils Tk, fournissent des mécanismes pour la communication entre applications, en envoyant des commandes Tcl dans un sens et dans l'autre. La structure commune du langage Tcl rend plus aisée la communication entre applications.

Toutes applications qui utilisent tcl créent et utilisent un interpréteur tcl. Lorsque l'on tape ns, une série d'initialisation est faite, puis l'application passe en mode interactif, c'est-à-dire que l'interpréteur est prêt à recevoir une nouvelle commande; et on peut entrer des commandes tcl. Le retour à la ligne d'une commande provoque son exécution ; deux commandes sur une même ligne sont séparées par un point virgule.

Construire une application avec un interpréteur Tcl revient à inclure une bibliothèque Tcl qui définit les commandes de bases de Tcl dans l'application. Comme nous l'avons dit, l'interpréteur effectue l'analyse syntaxique et appelle la fonction C correspondant à la commande Tcl. Ajouter une commande Tcl consiste à établir un lien entre un mot et une fonction C. Le mot sera le nom de la commande Tcl. La fonction C est définie dans le code source de l'application. Au démarrage, l'application procède dans son main() aux initialisations nécessaires et passe la main à l'interpréteur. L'application passe en mode interactif à chaque commande tapée par l'utilisateur, la fonction C correspondante est appelée afin de réaliser la commande demandée.

b. le OTcl :

OTcl est une extension orientée objet de Tcl. Les commandes Tcl sont appelées pour un objet. En OTcl, les classes sont également des objets avec des possibilités d'héritage. La définition d'une classe commence par la directive Class. Les fonctions et les attributs d'une classe s'installent par la suite par les commandes instvar et insproc. L'utilisation instproc définit les méthodes de la classe de manière assez semblable à C++. Lors d'une instanciation en OTcl, le

constructeur de la classe appelle init{ } pour les initialisations et les traitements propres à l'objet. La méthode init{} est optionnelle, c'est à dire que si l'instanciation ne nécessite aucune initialisation il n'est pas nécessaire de la définir. On peut l'appeler également variable d'instance. La valeur de l'attribut appartient à l'objet. La commande instvar est utilisée dans une méthode pour mettre en correspondance une variable d'instance avec une variable locale à la méthode. Il n'est pas nécessaire de faire une déclaration préalable au niveau de la classe. Une déclaration d'une variable d'instance se fait à l'intérieur d'une méthode membre. Par exemple, pour déclarer la variable d'instance, il suffit d'écrire "$self instvar x". Le schéma général de déclaration d'une classe est le suivant:

Class <Nom de classe>

<Nom de classe> instproc init {args} {

# constructeur

...

}

<Nom de classe> instproc methode1 {args} {

$self instvar variable1 # variable membre de la classe

...

}

En NS, les objets sont créés par la commande new <nom de la classe> qui retourne une référence sur l'objet créé. Par exemple, la création d'une instance de Simulator est effectuée par la commande suivante:

set ns [new Simulator]

Les objets topologiques (noeud et lien) ont une syntaxe de création quelque peu différente. On n'utilise pas la commande new{} mais une procédure de la classe Simulator. Dans les deux cas, la classe est uniquement OTcl et la référence des instances de ces classes est mémorisée dans un tableau de la classe Simulator. Par exemple la création d'un noeud est effectuée avec la syntaxe suivante: $ns node.

Une fois créés, les objets sont manipulables avec les méthodes dont ils disposent. Ces méthodes proviennent de leur classe et de leurs super-classes. L'appel d'une méthode est effectué via l'objet. Le nom de la méthode est le premier argument qui suit la référence de l'objet comme c'est le cas pour créer un noeud. La méthode appelée est la première trouvée dans l'arbre d'héritage de l'objet. Les affectations sur les variables membres se font par la commande set{} et suivent le format général des commandes OTcl:

<référence instance> set <instance variable> <valeur>

II.4 Script de simulation et Spécifications de nos implémentations

Un script de simulation est un code écrit en Otcl permett ant de définir la topologie (n°uds, liens) du réseau à simuler. Il permet d'engendrer des événements à des instants données (déplacement des n°uds, début ou arrêt des transmissions...) et à activer des traces à des endroits pertinents. La compréhension d'un script de simulation passe par la compréhension des concepts de bases suivants : le simulateur, l'Ordonnanceur, les outils de statistiques, de visualisations, la génération de mouvement dans le cadre des réseaux Ad hoc, les Agents de trafic.

II.4.1 Le simulateur

Le simulateur est configuré, contrôlé, et exploité via l'interface fournit par la classe Simulator jouant le rôle d'API (Application Programming Interface). Cette interface permet de configurer la simulation et de choisir le type du planificateur d'événement utilisé pour la simulation. Un script de simulation commence généralement par la création d'une instance de cette classe et par l'appel des différentes méthodes pour la création des n°uds, de la topologie, du mouvement, ainsi que la configuration d'autres aspects de la simulation.

Lorsqu'un nouvel objet simulator est créé en Tcl, la procédure d'initialisation init { } exécute les opérations suivantes :

- créer l'Ordonnanceur

- créer un Agent Null, qui est utilisé comme destination pour les paquets perdus.

II.4.2 Le Scheduler (Planificateur d'événements)

L'Ordonnanceur est l'élément conducteur de la simulation (il fait avancer la simulation). Pour cela il choisit l'événement le plus proche en terme de temps, exécute les traitements qui lui sont associés, fait progresser le temps « simulé » et avance à l'événement suivant, sachant que ce dernier est défini par la classe Event et se caractérise par l'heure de déclenchement et par l'avènement à réaliser.

II.4.3 Architecture du réseau

La classes de bases utilisées pour définir l'architecture et la topologie du modèle est la classes Node, d'autre classe tel que Link permet, aussi, de définir la topologie du réseau dans le cas de simulation des réseaux filaires ou hybride.

a. Noeud :

La classe Node est une classe OTcl: elle n'a donc pas d'existence en tant que telle dans le simulateur. Cette classe et ses méthodes sont définies dans le fichier tcl/lib/ns-node.tcl. Un noeud est une collection de classifiers et d'agents. Le classifier démultiplexe les paquets. L'agent est habituellement l'entité d'un protocole.

b. Lien :

Le lien sert à relier les noeuds. Il modélise le système de transmission. Le lien est principalement caractérisé par un délai de propagation et une bande passante. C'est une classe OTcl qui regroupe un ensemble de composants dérivés de la classe Connector. Cette classe et ses méthodes sont définies dans le fichier tcl/lib/ns-link.tcl. Des liens plus sophistiqués peuvent être dérivés de cette classe. Dans la simulation de réseau Ad hoc, les liens ne sont pas définis explicitement comme reliant deux n°uds, ce qui est tout naturellement dû à la nature, sans fil, du réseau. De ce fait, les informations concernant les spécificités du canal sont fourni en guise de configuration du canal avant la créat ion des n°uds.

c. Les Agents :

Les agent jouent un rôle important dans les simulations .En effet les utilisateurs créent des n°uds sources ou récepteurs à partir de la classe agent. Ils font partie intégralement d'un n°ud, on peut les assimiler à la couche transport du modèle OSI. Les agents sont les points terminaux du réseau qui reçoivent ou délivrent les paquets à des applications. A chaque agent est attribué un port. L'adresse d'un agent se compose du numéro de son n°ud et son port. Actuellement il existe de nombreux agents dans NS.

d. La gestion de la file d'attente :

La gestion de la file d'attente sur les liens est implémentée dans la classe Queue ; les files d'attente actuellement disponibles dans NS sont :

- Droptail qui utilise la technique FIFO c'est la file d'attente par défaut

- RED (Random Early Detection)

- FQ (Fair Queuing)

- SFQ (Stochastic FQ)

- CBQ ( Class Based Queuing)

II.4.4 Spécification de nos implémentations

Notre travail consiste à implémenter des modèles de mobilité et y simulé le comportement des protocoles de routage. Pour cela, nous avons implémenté trois modules qui permettent de simuler quatre modèles de mobilités. Parmi lesquels, le modèle de mobilité à promenade aléatoire, le modèle de mobilité à promenade aléatoire avec pause, le modèle de mobilité à direction aléatoire et une version du modèle de mobilité à section de ville.

Pour nos implémentations, nous avons opté pour un environnement de programmation orienté objet qui, non seulement va de paire avec la philosophie de NS mais permet aussi de rendre efficace, évolutif, lisible, réutilisable et fiable le code généré.

Parmi les avantages de nos implémentations, la réduction du caractère aléato ire, tout en ayant des modèles mieux proche de réalité.

Utilisation :

Nous avons implémenté en java (jdk de sun) par conséquent il est nécessaire de compiler le code source pour avoir le fichier byte-code qui sera interprété par la machine virtuel java (jvm).

Les modules implémentés sont les suivants :

Mainly1 : Pour le modèle de promenade aléatoire et promenade aléato ire avec pause. Mainly2 : pour le modèle de mobilité à section de ville.

Mainly3 : pour le modèle de mobilité de direction aléatoire.

Pour compiler :

javac Mainly1.java

javac Mainly2.java

javac Mainly3.java

Ces commandes permettent de générer le fichiers byte-code.

Pour exécuter :

Les commandes :

Java Mainly1 ;

Java Mainly2 ;

Java Mainly3 ;

Afficheront à l'écran les paramètres nécessaires pour le déroulement des models. Par exemple pour le module Mainly1 cette sortie est :

-n <nombre de n°uds>

-x <la largeur de la zone de simulation>

-y <la longueur de la zone de simulation>

-v <vitesse>

-tp <temps de pause>

-t <durée de la simulation>

L'ordre dans laquelle apparaîtront ces paramètres est moins important vu la présence des tags. Pour le module Mainly 1, la génération d'un fichier de mouvement pour le modèle RWP ou le modèle RW dépend du permettre --tp (temps de pause). Autrement dit, si le temps de pause vaut 0 c'est le RW dans le cas contraire c'est le RWP qui sera généré.

Ex : java Mainly1 --n 50 --x 1000 --y 500 --t 100 --v 20 --tp 0 pour le RW.

java Mainly1 --n 50 --x 1000 --y 500 --t 100 --v 20 --tp 10 pour le RWP avec temps de pause 10.

Le nom du fichier de sorti, celui qui contiendra la définition des mouvements, est demandé après avoir valider la ligne de commande.

Le module Mainly3 est utilisé de façon très similaire que le module Mainly1.

Pour le module Mainly2, il est défini comme tout modèle de mobilité à section de ville, pour une situation géographique bien déterminé. Nous avons prévu deux types de route, ceux des périphériques, qui sont à grande vitesse (vitesse défini et fixe à 30 m/s) et ceux de l'intérieur pour lesquelles la vitesse ne peut dépasser le 20 m/s. c'est cela qui est fourni lors du passage des paramètres de la ligne de commande. La figure 4.1 illustre la topologie et les types de routes de la situation géographique considérer.

Contrairement aux autres models, pour effectuer une simulation dans une zone de 1000x500, l'utilisateur doit spécifier 1 200x700, comme taille de la zone de simulation, dans le script tcl ainsi que dans la spécification des paramètres du model de mobilité car l'espace défini par les coordonnée (x <=100)ou(x >= maxx-100 )ou(y <= 100) ou (y>= maxy -100) est inaccessible.

Hormis le fichier de mouvement, nous avons implémenté un générateur de trafic adapté à nos simulations. Ce générateur, « statique et dynamique », est intégré au script TCL de simulation.

Ligne à grande vitesse

Figure 4.1 : Topologie de la section de ville considérée

II.5 Visualisation et extractions des résultats:

NS est accompagné d'autres outils qui permettent de visualiser le comportement du réseau pendant la simulation, de générer un fichier de sorti contenant les événements qui se sont déroulés pendant la simulation.

II.5.1 Visualisation

Le NS offre un outil de visualisation le NAM(Network Animator) ; qui permet le suivi des états d'un grand nombre de n°uds, une analyse de l'échange de messages et des interactions dynamiques pour des trafics concurrents. Les outils de visualisation permettent à l'utilisateur d'accéder rapidement à une quantité importante d'informations et d'identifier visuellement les modèles de communication, leur permettant ainsi de mieux comprendre les interactions et les causalités. La figure 4.2 montre la fenêtre nam.

II.5.2 Le traceur

Le NAM ne permet pas de voir en détail tous les évènements qui se produisent lors de la simulation. Le traceur enregistre dans un fichier la totalité des événements produits lors de la simulation. La sortie du traceur est indispensable pour l'étude des statistiques. Ils existent plusieurs formats de fichier trace adapté au type de réseaux a simulé, les réseaux filaire, les réseaux satellite, les réseaux sans fil, les réseaux sans fil Ad hoc etc. Parlons du contenu de ce fichier pour les réseaux Ah hoc.

Ils existent deux formats de fichier dans les réseaux Ad hoc, l'ancien format et le nouveau format. Dans l'ancien format, le fichier est vu comme étant un ensemble de colonne dont le sens de chacun est prédéfini. Le paragraphe suivant est une partie d'un fichier trace basé sur l'ancien format.

s 1.152109107 _14_ RTR --- 0 AODV 48 [ 0 ffffffff d 800] [ 14:255 -
1:255 27 0] [ 0x2 4 1 [ 27 0] [ 2 4]] (REQUEST)

s 1.152380985 _40_ RTR --- 0 AODV 48 [ 0 ffffffff 19 800] [ 40:255 -
1:255 28 0] [ 0x2 3 1 [34 0] [9 4]] (REQUEST)

ü 1.152404561 _3_ RTR --- 0 AODV 48 [ 0 ffffffff 2a 800] [ 42:255 -
1:255 28 0] [ 0x2 3 1 [ 27 0] [ 2 4]] (REQUEST)

ü 1.152404686 _21_ RTR --- 0 AODV 48 [ 0 ffffffff 2a 800] [ 42:255 -
1:255 28 0] [ 0x2 3 1 [ 27 0] [ 2 4]] (REQUEST)

ü 1.152404707 _7_ RTR --- 0 AODV 48 [ 0 ffffffff 2a 800] [ 42:255 -
1:255 28 0] [ 0x2 3 1 [ 27 0] [ 2 4]] (REQUEST)

ü 1.152404740 _41_ RTR --- 0 AODV 48 [ 0 ffffffff 2a 800] [ 42:255 -
1:255 28 0] [ 0x2 3 1 [ 27 0] [ 2 4]] (REQUEST)

ü 1.152404770 _0_ RTR --- 0 AODV 48 [ 0 ffffffff 2a 800] [ 42:255 -
1:255 28 0] [ 0x2 3 1 [ 27 0] [ 2 4]] (REQUEST)

ü 1.152404901 _33_ RTR --- 0 AODV 48 [ 0 ffffffff 2a 800] [ 42:255 -
1:255 28 0] [ 0x2 3 1 [ 27 0] [ 2 4]] (REQUEST)

Figure 4.2 : Network AniMator (NAM)

Le nouveau format est constitué d'un ensemble de tag pour chaque événement, chaque tag porte le sens de l'information qui le suit, par conséquent nous pouvons voir ce format comme étant un ensemble de champs parmi lesquels nous avons.

Champ [0] : le premier champs, le seul a ne pas être défini par un tag, permet d'identifier le type d'événement qui s'est produit. Ce champ peut être : s (pour send) indiquant un envoie de paquet, r (pour receive) indiquant une réception de paquet, d (pour drop) indiquant une suppression de paquet et f (forware) pour un acheminement.

Champ [1] : défini par le tag «-t » indique l'avancement du temps de simulation, le temps de production de l'évènement.

Champ [2] et le Champ [3]: Donnent des informations sur l'actuel et prochain n°ud d'un paquet. --Hs pour le n°ud courant.

--Hd pour le pro chain n°ud à atteindre vers la destination

Champs [4], [5], [6] et [7] : ils dénote les propriétés d'un n°ud.

-Ni : pour l'identificateur du n°ud.

-Nx : pour l'abscisse du n°ud dans la zone de simulation.

-Ny : pour l'ordonnée du n°ud dans la zone de simulation.

-Nz : qui est toujours mis à zéro car NS permet de simuler un réseau Ad hoc uniquement sur une surface plane.

Champ [8] : défini par le tag --Ne : permet d'indiquer le niveau d'énergie.

Champ [9] : défini par le tag --Nl : permet d'indiquer le niveau de trace comme RTR pour routage etc.

Ils existent bien d'autres champs tels que :

-Nw permett ant de préciser la raison de suppression d'un paquet;

-Is permettant d'identifier, l'adresse et le port utilisé, du n°ud qui implémente l'agent émetteur.

-Id identifie, l'adresse et le port utilisé, du n°ud implémentant l'agent récepteur. -Mx : donnent des informations sur les paquets de niveau MAC.

-It : donne des informations concernant le type de paquet.

-Ii : précise l'identité du paquet.

Ce que nous venons de présenter n'est autre que le contenu standart d'un fichier trace basé sur le nouveau format. Ce format varie réellement en fonction des protocoles utilisés pour la simulation.

Ce nouveau format est très évolutif par rapport à l'ancien et permet de personnaliser le contenu du fichier trace. Pour l'étude des statiques, le parseur n'a plus besoin de connaître la signification d'une colonne pour en extraire des informations. Nous avons opté pour ce dernier format pour l'étude des statistiques, Pour cela nous avons implémenté un parser en java qui a pour rôle de parcourir le fichier trace et de calculer les paramètres dont nous avons besoin, PDF, NRL et AVG, (voir paragraphie III). Une section d'un fichier trace basé sur le nouveau format est illustrée dans le paragraphe suivant.

s -t 0.087760710 -Hs 8 -Hd -1 -Ni 8 -Nx 265.28 -Ny 241.83 -Nz 0.00 -Ne - 1.000000 -Nl RTR -Nw --- -Ma 0 -Md 0 -Ms 0 -Mt 0 -Is 8.255 -Id -1.255 -It message -Il 32 -If 0 -Ii 0 -Iv 32

r -t 0.088572985 -Hs 5 -Hd -1 -Ni 5 -Nx 202.81 -Ny 295.78 -Nz 0.00 -Ne - 1.000000 -Nl RTR -Nw --- -Ma 0 -Md ffffffff -Ms 8 -Mt 800 -Is 8.255 -Id - 1.255 -It message -Il 32 -If 0 -Ii 0 -Iv 32

r -t 0.088573004	-Hs	10	-Hd -1	-Ni	10 -Nx 266.53	-Ny 330.12 -Nz 0.00 -Ne -
1.000000 -Nl RTR	-Nw	---	-Ma 0	-Md	ffffffff -Ms	8 -Mt 800 -Is 8.255 -Id -
1.255 -It message	-Il	32	-If 0	-Ii	0 -Iv 32

III Simulation et interprétation des résultats :

III.1 Les facteurs de simulation

Parmi l'ensemble des paramètres réseau (qui sont très nombreux), nous avons deux paramètres qui sont en relation direct avec la mobilité. Il s'agit de la vitesse de déplacement et le temps de pause des n°uds. Les autres paramètre qui sont, aussi important, seront fixe car notre travaille est de mieux voir l'effet de la mobilité sur les protocoles de routages. Il est très difficile, voir impossible, de dire qu'un protocole de routage s'adapte mieux à un modèle de mobilité qu'un autre protocole de routage. Pour mieux voir l'effet de la mobilité sur les protocoles de routages, nous comparons le comportement d'un protocole de routage sous des modèles de mobilité différents. Nous simulons les deux protocoles de routage OLSR et AODV. Chaque protocole est comparé sous deux modèles de mobilité d'entité et un modèle de mobilité de groupe. Les valeurs des paramètres qui ne seront pas varié sont les suivantes :

La surface de simulation : 1000x500 m

Le temps de simulation : 200 s

Le temps de pause pour une variation de vitesse : 5 s

La vitesse pour une variation du temps de pause : 5 m/s

Nombre de connexions : 50.

Les modèles de mobilité utilisés : le RWP, le RD et le RPGM.

Nos Simulations ont été effectué sur le Mandriva 2006 avec le NS2.29. 1 sur une machine de 768 Mo de ram.

III.2 Les métriques mesurées

Il existe un grand ensemble de métriques sur la base desquelles nous pouvons mesurer la performance des protocoles de routage. Nous avons choisi les métriques que nous jugions les plus significatives pour mesurer la performance d'un protocole de routage à savoir : le PDF (Paquet Delivery Fraction), l'AVG (Average End to End Delay), et le NRL (Normalized Routing Load).

III.2.1 Packet Delivery Fraction (PDF)

Le taux de délivrance des paquets est le rapport entre le nombre de paquets reçus (par toutes les destinations du trafic) et le nombre de paquets émis (par toutes les sources de trafic). La métrique opposée au taux de délivrance de paquets est le taux de perte de paquets. Un taux de

délivrance de paquets élevé est équivalent à un taux de perte petit, et vice versa. Cette métrique représente la fiabilité du protocole pour expédier tous les paquets de donnés envoyés.

III.2.2. Average End to End Delay (AVG)

Le délai de bout en bout est le temps qui sépare le moment d'envoie d'un paquet de la couche transport de la source et le moment de réception de ce paquet par la couche transport de la destination. Il inclut le temps de latence pour la découverte de routes, le temps de passage dans les files d'attente des n°uds intermédiaires et le temps de transmission d'un saut vers un autre. Nous mesurons le délai moyen de bout en bout par rapport à tous les paquets reçus pendant la simulation, puis nous calculons la moyenne. Cette métrique représente l'efficacité du protocole en terme de temps de réponse et en terme du choix des chemins optimaux.

III.2.3 Le Normalized Routing Load (NRL)

Le NRL représente le nombre de paquets de routage émis pour chaque paquet de donnée reçu. Cette métrique nous permet d'évaluer pour chaque protocole, la surcharge provoquée pour l'envoi des paquets de contrôle.

III.3. Simulation du OLSR

Les versions du NS2 que nous avons à notre disposition n'inclus pas d'implémentation du protocole de routage OLSR. Nous avons effectué nos tests sur une implémentation du OLSR conforme au RFC 3626.Cette implémentation intègre toutes les fonctionnalités du OLSR [MAS], elle à été développée par J.Ros Francisco (Directeur de projet et développeur principal).

III.3.1. Variation de la vitesse

400 350 300 250

200

150 100 50

0

5 10 15 20 25 30 35

vitesse

RDIRECTION RPGM

RWP

90 80 70 60 50 40 30 20 10 0

5 10 15 20 25 30 35

vitesse

RDIRECTION RPGM

RWP

Figure 4.3 : OLSR_vitesse_AVG

2500
2000
1500
1000
500
0

5 10 15 20 25 30 35

vitesse

RDIRECTION RPGM

RWP

Figure 4.4 : OLSR_vitesse_NRL

Pour le AVG, nous remarquons que le OLSR donne de bon résultat pour le RWP que pour le RD. Le délai moyen de transmission dépend de plusieurs facteurs parmi lesquels, la longueur du chemin utilisé, en terme de nombre de saut, pour la transmission des paquets. Le RWP présente un inconvénient, vu du point imitation du comportement humain, qui s'avère avantagé dans cette situation, il s'agit de la concentration de n°uds au centre de la zone de simulation. Cette concentration réduit considérablement le nombre de n°ud intermédiaire sollicité pour l'envoie des données. Le RD, en résolvant le problème de concentration des n°uds au centre de la zone de simulation, augmente le nombre de saut par rapport au RWP, donc le délai moyen de transmission. Pour ce qui est le RPGM, contrairement à ce que à ce que nous avions passé, il donne des résultats moins satisfaisant que le RD et RWP. Ce que nous avions passé est que, dans ce model, le réseaux et constitué d'un ensemble de groupe dont les n°uds du même groupe se déplace en gardant probablement les mêmes distances. Nous pouvons déduire, de là, que les membre d'un même groupe ne se déplace quasiment les uns par rapport aux autres. Pour un envoie de paquet entre n°uds du même groupe, le temps d'émission est très efficace, non seulement, parce que les n°uds sont proche mais aussi la route crée est très stable.

Pour le NRL et le PDF, les résultats pour le RWP et RD sont très semblables

Lorsque la vitesse att eint 10 m/s, Ce qui n'est pas surprenant vu les similitudes qui existent entre ces deux models. A faible vitesse, le RWP est plus meilleure ; encore une concentration avec faible déconnexion explique cet état. Quant au RPGM, il donne des résultats moins satisfaisant que les deux modèles d'entité. Ce résultat justifie le choix de comparer un des modèles de mobilité de groupe avec nos implémentations. L'idée est d'illustré une différence au cas où les ressemblances des de deux modèles de mobilité d'entité ne permettraient pas de voir une différence. Nous pouvons lié ce résultat à la dispersion des groupes dans la zone de simulation. Le OLSR étant un protocole proactif, il essaie de maintenir les routes avant toute communication, pour ce faire des paquets de contrôles sont envoyé via le réseau. La dispersion des groupes peut conduire à l'échec, ou prolonger, la convergence des tables de routage. Ce qui fait que les premières transmissions de donnée provoquent d'autres recherches de route qui ont pour inconvénient d'augmenter le nombre de paquet de control mais aussi de diminuer le taux de paquet délivré dans le réseau.

III.3.2. Variation du temps de pause

350 300 250 200 150 100 50

0

0 5 10 15 20 25 30 35 40 45 50

pause time

RDIRECTION RPGM

RWP

90 80 70 60 50 40 30 20 10 0

0 5 10 15 20 25 30 35 40 45 50

pause time

RDIRECTION RPGM

RWP

Figure 4.6 : OLSR_temps de pause_AVG

2000 1800 1600 1400 1200

1000

800 600 400 200

0

0 5 10 15 20 25 30 35 40 45 50

pause time

RDIRECTION RPGM

RWP

Figure 4.7 : OLSR_temps de pause_NRL

Le temps de pause a pour effet de rendre le réseau plus stable, Autant le temps de pause et élève plus stable sera le réseau avec moins de déconnexion. L'effet que ce paramètre pourrait avoir sur le modèle RPGM est le maintien de la dispersion des groupes au sein de la zone de simulation. Quant aux deux modèle de mobilité d'entité, il se ressemblent mieux quant le temps de pause est élevé car le RWP provoque, dans ces situations, une concentration au centre et le RD, quant à lui, provoque une concentration sur les périphériques. Nous pouvons déduire, en se basant, sur les précédentes figures que la concentration des n°uds provoquée par le RD est plus efficace que celle réalisé par le RWP à faible temps de pause. C'est ces propriétés qui vérifient les résultas obtenus pour les trois paramètres (le AVG, le PDF et NRL). Nous remarquons que les deux modèles de mobilité d'entité donnent les mêmes résultats avec l'accroissement du temps de pause et c'est le RD qui emporte sur le RWP à faible temps de pause. Le RPGM donne des résultats moyens par rapport au deux modèles d'entité lorsque le temps de pause est faible, ce qui est dû à la redirection rapide des groupes vers centre de la zone de simulation, il est beaucoup moins meilleur dans le temps contraire.

III.4 Simulation du AODV

La version du NS2 sur laquelle nous avons effectuer nos simulations intègre une implémentation du protocole de routage AODV, implémentation que avons utilisé pour tester ce protocole de routage.

III.4.1. Variation de la vitesse

1200 1000 800

400
200
0

600

5 10 15 20 25 30 35

vitesse

RDIRECTION RWP

RPGM

Figure 4.9 : AODV_vitesse_AVG

10000
8000
6000
4000
2000
0

5 10 15 20 25 30 35

vitesse

RDIRECTION RWP

RPGM

Figure 4.10 : AODV_vitesse_NRL

100 80 60 40 20

0

5 10 15 20 25 30 35

vitesse

RDIRECTION RWP

RPGM

Figure 4.11 : AODV_vitesse_PDF

Nous remarquons que les deux modèles de mobilité d'entités donnent des résultats similaires lorsque la vitesse est élevée, dans le cas contraire c'est le RD qui est meilleure et ce quelque soit le paramètre (PDF, AVG, NRL). Ce résultat est contraire à celui obtenu pour le protocole de routage OLSR. Le AODV, contrairement au protocoles de routage OLSR, crée les routes à la demande en diffusant des requêtent de recherche de routes par inondation dans le réseau. Il y aura plus de rediffusion des requêtes lorsque le n°ud émetteur à beaucoup de voisin; ce qui explique la hausse du nombre de paquet de contrôle lorsqu'on passe du RD au RWP. L'efficacité dans la découverte de chemin influe immédiatement sur le temps de délivrance des paquets. Il nous semble qu'une découverte plus basée sur les périphériques est plus efficace, c'est ce que affirment les précédents résultats. Pour ce qui est le taux de délivrance de paquet, il est aussi lié à la découverte du chemin. Comparativement au deux modèles d'entités, le modèle RPGM donne des résultats moins meilleurs. Là aussi, comme çà été le cas

pour la plupart des simulations sur le OLSR, nous pouvons songé au problème de dispersion des groupes qui ne laisse indemne la découverte de route que déclanche le AODV.

III.4.2. Variation du temps de pause

1200 1000 800

400
200
0

600

0 5 10 15 20 25 30 35 40 45 50

pause time

RDIRECTION RPGM

RWP

Figure 4.12 : AODV_temps de pause_AVG

6000 5000 4000

2000
1000
0

3000

0 5 10 15 20 25 30 35 40 45 50

pause time

RDIRECTION RPGM

RWP

Figure 4.13 : AODV_temps de pause_NRL

100 90 80 70 60 50 40 30 20 10

0

0 5 10 15 20 25 30 35 40 45 50

pause time

RDIRECTION RPGM

RWP

Figure 4.14 : AODV_temps de pause_NRL

Contrairement aux cas de la variation de vitesse, nous observons que le RWP et RD donnent des résultats similaires pour le temps de délivrance de paquet ; pour le taux de paquet reçu et nombre de paquet de contrôle généré, le RWP, même s'il est très proche, est meilleur par rapport au RD. Dans tous les cas, le protocole de routage AODV donne des résultats plus satisfaisant sur les deux modèles d'entité par rapport au RPGM. L'effet du temps de pause est bien évidemment la stabilité du réseau, moins il y a de mouvement et plus les groupes seront dispersés. La dispersion des groupes dans le RPGM n'a pas d'impact important sur le nombre de paquet de contrôle généré dans la mesure où le processus de recherche de route n'est déclanché quant cas de besoin.

IV. Conclusion

Dans ce chapitre, nous avons parlé des environnements de simulation existant sur le marché en mett ant l'accent sur le NS2. Nous avons parler de la philosophie de NS2 en générale avant de passé en revu les modèles de mobilité que nous avons implémenté. Parmi ces modèles, nous avons utilisé le modèle de mobilité de promenade aléatoire avec pause et le modèle de mobilité de direction aléatoire pour y tester les protocoles de routage OLSR et AODV. Nous n'avons pas utilisé la version du modèle de mobilité de section de ville pour nos tests car les paramètres que nous avons choisi pour tester les protocoles de routages n'existe ou ne sont pas perçu de la manière dans ce modèle que dans les autres. En outre, nous avons testé les deux protocoles, évoquer précédemment, sur un modèle de mobilité de groupe, le RPGM, qui est implémenté par le groupe de recherche de T. Camp. D'une vu générale le OLSR donne de bon résultat, pour une variation de la vitesse, lorsqu'il est simulé sur RWP que sur le RD. Quant à la variation du de pause la tendance s'inverse. Pour le protocole AODV, la situation

est tout à fait le contraire de celui du OLSR. Dans tous les cas, les deux protocoles semblent donner de meilleur résultat lorsqu'ils sont simulés sur les deux modèles d'entité que sur le modèle de mobilité de groupe RPGM.

En fin, nous somme convaincu que les performances d'un protocole de routage varie en fonction du modèle de déplacement utilisé. Il est aussi important de noter que les paramètres passés en argument du générateur du fichier de mouvement peu très bien influé sur les résultats des simulations, par conséquent il est possible de simuler les mêmes protocoles de routage sur les mêmes modèles de mobilité et avoir, au finale, des résultats différents.

CONCLUSION GENERALE

Le domaine des environnements mobile est en pleine expansion actuellement, et présente de plus en plus une grande flexibilité d'emploi. Ils permettent aussi une présence de communication sans fil dans des sites où la mise en place du câblage est très difficile ou même impossible.

Les réseaux informatiques basés sur la communication sans fil sont classés en deux catégories : les réseaux avec infrastructure fixe préexistante, et les réseaux sans infrastructure. Dans la première catégorie, le modèle de la communication utilisé est généralement le modèle de la communication cellulaire. Dans ce modèle les unités mobiles sont couvertes par un ensemble de stations de base reliées par un réseau filaire, et qui assurent la connectivité du système. La deuxième catégorie essaie d'étendre les notions de la mobilité à toutes les composantes de l'environnement, toutes les unités du réseau se déplacent librement et aucune administration centralisée n'est disponible. Les réseaux de cette catégorie sont appelés : les réseaux ad hoc.

Dans le but d'as surer la connectivité du réseau malgré l'absence d'infrastructure , chaque n°ud est susceptible d'être mis à contribution pour participer au routage et pour retransmettre les paquets d'un n°ud qui n'est pas en mesure d'atteindre sa destination, tout n°ud joue ainsi le rôle de station et de routeur. Chaque n°ud participe donc à une stratégie de routage qui lui permet de découvrir les chemins existants, afin d'atteindre les autres n°uds du réseau. Une autre caractéristique des réseaux Ad hoc est l'adaptation des méthodes de routage classiques utilisées avec le grand nombre d'unités pouvant exister dans ce réseau. Pour résoudre ces problèmes, différentes stratégies de routage conçues pour les réseaux ad hoc ont été étudiées. Selon la manière de construction de chemins entre les stations sources et les stations destination, les stratégies (ou les protocoles) de routage sont divisées en trois classes : les protocoles réactifs, les protocoles proactifs et les protocoles hybrides. Les protocoles proactifs créent et maintiennent les routes en dehors de toutes communications ; les protocoles réactifs créent les routes à la demande et les protocoles hybrides procèdent par hybridation des deux techniques (proactive et réactive).

Les performances des solutions de routage proposées dépendent des paramètres tels que le nombre de n°ud du réseau, la charge du réseau, le modèle de déplacement des noeuds dans le réseau. Il existe deux types de modèle de mobilité, les modèles de mobilité de groupe et les modèles de mobilités d'entité. Dans le premier cas, le réseau est constitué d'un

ensemble de groupe pour lesquels le déplacement des membres d'un même groupe est synchronisé ; dans le second, chaque n°ud se déplace indépendamment des autres. Dans ce mémoire, nous avons implémenté quatre modèles de mobilités d'entités. Pour les tests, nous avons utilisé le Network Simulator (NS2) sur lequel nous avons simulé les protocoles de routage OLSR et AODV sous trois modèles de mobilité dont un modèle de mobilité de groupe implémenté par un groupe de recherche américain dirigé par J Camp.

Au terme de nos simulions, nous avons constaté que les performances des protocoles de routage varie en fonction des modèles de mobilité utilisé. La différence est plus en plus grandissant lorsque le même protocole de routage est simulé dans les mêmes conditions sous des modèles de mobilité de différent type.

En guise de guide pour les promotions futures; nous joignons à ce mémoire le code source d'un des modèles de mobilité que nous avons implémenté.

Perspectives :

Au terme de nos simulations et vu les résultats obtenus, une curiosité, tout naturelle, a été de simuler les protocoles de routage basé sur le concept de groupe sur les modèles de mobilités de groupe. Selon la logique, ces protocoles doivent atteindre toute leur performance lorsqu'ils sont simulés sur les modèles de mobilité de groupe.

En outre, si l'effet de la mobilité sur les protocoles de routage intéresse, en vrai, la communauté scientifique, le monde des réseaux ad hoc se verra doté, dans l'avenir, des protocoles de routages adapté à des modèles de mobilité précis. Aussi, il est important de souligner qu'il y a beaucoup à faire pour améliorer les modèles de mobilité existant pour les adapter, au mieux, au comportement humain. Un projet qui peut faire l'objet d'une chimère d'actualité est la réalisation de la communication entre modèle de mobilité et protocole de routage, cette pensée entre dans le cadre de la prédiction de mouvement dans les MANETS.