Memoire Online - Etude sur les protocoles de routage d'un réseau sans fil en mode Ad Hoc et leurs impacts. "cas de protocoles OLSR et AODV"

Travail de fin du cycle présenté et défendu en vue de l'obtention de titre d'Ingénieur Informaticien

Option : Techniques de Maintenance Directeur : MIZONZA BANTIKO DIOR Ingénieur Informaticien

EPIGRAPHE

« Il appartient à un Ingénieur de s'assurer que tout ce
qu'il a conçu et créé est capable de résister à toute
charge!!! »

DEDICACE

Mon âme bénit l'Eternel et n'oublie aucun de ses bienfaits car celui qui exerce mes mains aux combats !

A mon regretté Papa Joseph MONDONGA ANGASA qui n'a pas pu voir ce jour si longtemps attendu, que son âme repose en paix !

A mon oncle, Honorable Rabbin KPENUMO et votre chère épouse Augustine WEBINA, vous m'avez toujours montré votre sens d'un bon parent.

A mon cher ami, Ingénieur Guylain KONGAWI, pour ton soutien tant scientifique, matériel et financier, en voici le fruit.

A mes frères et soeurs, Bébé MONGONZA MONDONGA, Mamie BASETEBI MONDONGA, Lyly MONDONGA, SABINA MONDONGA, Sylvain NGALA MONDONGA, Aime TONDI MONDONGA, Michel LONGINA MONDONGA, Nene BALIWE MONDONGA, Cédric MOTUTA MONDONGA, Patrick KONGAWI MONDONGA, voici l'exemple à suivre.

3
REMERCIEMENTS

Nous serons ingrats si nous ne remercions pas tous ceux qui nous ont assistés moralement, financièrement et matériellement durant notre premier cycle et pendant la rédaction de ce Travail qui constitue le premier document mis sur le marché intellectuel.

Nous citons tous les Professeurs, Chefs des Travaux et Assistants de l'Institut Supérieur de l'Informatique, Programmation et Analyse, section de Techniques de Maintenance pour leur formation scientifique, morale et professionnelle à notre bénéfice.

Nous remercions en particulier l'Ingénieur MIZONZA BANTIKO qui a accepté de diriger ce Travail, en dépit de toutes ses multiples occupations.

Nos familles qui se sont battues pour la réussite de cette formation, Ma tante Julienne EPUNZA et mon regretté père MBOTI, Soeur Hélène MONGONZA, Papa MABELE et maman Jacqueline, Ir. ABUBAMBI et maman MT ABUBAMBI, Lokadi MONDONGA, Philo NZELO, Oncle Patrice KONGAWI, Oncle Victor PALAIYA, Oncle PENZE KPADO, Valentin ZANZU, Joël BONA, Ir. Jacques MBOTI, Willy MBOTI, Jean-Jules MBOTI, Ir. Antoine MBOTI et sa femme Bibi, Zéphirin MBOTI, Thyno MBOTI, Rock MEKOYO, Maitre Paulin MABELE, Freddy MOKOMBO, Bijoux MOKOMBO, Cally MOKOMBO, Solution MOKOMBO, Ir. Pithou MOKOMBO, Tonton MOKOMBO, Verra MOKOMBO, Aymard BEMBIADE, Sandra MOOLO, Martine WENUNGBAKA, Ange DAWABINA, Thierry NAKOLE, Plangi BOLOGELE, Blaise KOTO, Olivier KASAI, Famille MAKWETA, Père R. MANZINGA, Père Martinien, Monsieur Joachim Taila, Oncle JP DONZO.

A nos chers amis et connaissances : Ir. Georges ZANDELE LEMOTO, Ir. Xavier BANGABUTU `'mon pote», Ir. Anderson LILEKA MATCHO, Ir. Frederick KAMWANGA, Ir. DINGOLE, Ir. Benjamin NDOMBE, Ir. Jules NZENGE, Ir. Bienvenu ABENDO, Hon. John WATEWANGI, Donat LEKANGBI, Maitre Olivier MONDONGE, Tonton Mike EMBOLE, Patrick AZUBA, Marlène AZUBA, Elfrid AZUBA `'ma soeur», Tonton BOSUNZA, JR KOLI, La rose BELI, Nora IPANGA, Noëlla ILAMBA, JP NGOLI, Trésor Arthur KAMBO, Clovis ZENGO, TRESOR DJADI, Germain WAIMBA, Patrick MONDONGA, Patience ZOMA, Dénis MODA, Blaisette MODA, Jeannine LEKELE, Blandine ABELE, Marie KENGE, Fidelie KABENA, Francine BATAMBA, Nelly BOIKA.

Nous présentons aussi nos remerciements à tous nos camarades, amis de lutte, de l'I.S.I.P.A pour la collaboration durant ces trois années d'Etudes, nous citons en passant DieuMerci MBUWA, Ben MBUYULU, Hergé NGOMBE, Ghyslain MAYALA, Yves MBIYE, Elie MENA, Ali KIBUNDILA, Ady KASONGO, Puma MAFITI, Erick KASIGWA, Bertilla DIEBENGE, NONO sarko, Nelly TSHILOBO, Cédric MUKE, John KABEYA, Hugor BODIKO, Josué NGALAMULUMBE et tous les restes dont les noms n'étaient pas sur les doigts pendant la rédaction de cette liste.

LES ABREVIATIONS

INTRODUCTION GENERALE

1. PROBLEMATIQUE

Le développement technologique qu'a connu le monde d'aujourd'hui a touché tous les domaines, particulièrement le secteur de la communication qui connait une évolution considérable par l'apparition de la technologie sans fil.

La technologie sans fil permet l'établissement d'une communication sans fil dans des environnements mobiles qui offrent 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, voire même impossible. Les réseaux mobiles sans fil, peuvent être classés en deux classes (les réseaux avec infrastructure et les réseaux sans infrastructure). Plusieurs systèmes utilisent le modèle de réseau avec infrastructure et connaissent un très fort épanouissement à l'heure actuelle, mais requièrent un important kit matériel fixe.

La contrepartie des réseaux fixes sont les réseaux mobiles ad hoc. Un réseau ad hoc peut être défini comme une collection d'entités mobiles interconnectées par une technologie sans fil formant un réseau temporaire sans l'aide de toute administration centralisée ou de tout support fixe. Aucune supposition ou limitation n'est faite sur la taille du réseau ou sur la mobilité des noeuds, cela veut dire qu'il est possible que le réseau ait une taille très énorme.

Dans un réseau ad hoc les sites mobiles doivent former un tout pour réaliser les taches facilement, dont les autres réseaux ne les permettent pas. Les applications des réseaux Ad hoc sont nombreuses, on cite l'exemple classique de leur application dans le domaine militaire et les autres applications de tactique comme les opérations de secours et les missions d'exploration.

Du fait que la propagation de la portée des ondes radio des hôtes soit limité, et afin que le réseau Ad hoc reste connecté, (c'est à dire toute unité mobile peut atteindre toutes les autres), Il se peut que l'hôte destination ne soit pas dans la portée de communication de l'hôte source, ce qui nécessite l'emploi d'un routage saut par saut pour acheminer les paquets de messages à la bonne destination. Ce mécanisme d'acheminement de paquet ou le routage, consiste à utiliser des protocoles de routage capables d'assurer la connexion entre n'importe quelle paire de noeuds appartenant au réseau à tout moment. Ces protocoles doivent prendre en considération les changements topologiques ainsi que les autres caractéristiques du réseau ad hoc (bande passante, nombre de liens, ressources du réseau etc.).

2. HYPOTHESE

Pour que les deux ordinateurs se communiquent dans le Réseau Ad Hoc, il requiert un certain nombre de prérogatives à respecter scrupuleusement, notamment : la bande passante, la charge de la batterie, la distance entre les deux noeuds, nombre de liens, ressources du réseau etc ~

La mobilité des ordinateurs dans le réseau Ad Hoc occasionne le changement perpétuel de topologie et demande l'intervention des stations intermédiaires pour l'acheminement des paquets par saut par saut. Les protocoles OLSR et AODV sont les plus évolués dans la normalisation de problème de routage dans les réseaux Ad Hoc.

3.CHOIX ET INTERET DU SUJET

L'intérêt majeur de ce Travail sera pour nous, une prise en contact de la nouvelle technologie de l'information et communication précisément dans le réseau sans fil en mode Ad Hoc. Son avantage sera d'informer aux utilisateurs des entités mobiles le parcours que subissent leurs paquets et les différents problèmes que rencontrent les paquets dans les routages.

4.METHODES ET TECHNIQUES UTILISEES

Pour rédiger ce fameux Travail de fin de cycle, nous sommes partis, comme de nature, par la méthode descriptive. Nous avons en outre utilisé les techniques documentaires et de consultation qui nous a amené à consulter les livres et autres articles parlant de routage OLSR et AODV dans le réseau Ad Hoc, la consultation de certains sites concernés n'a pas été épargnée.

Nous avons aussi expérimenté les réseaux Ad Hoc nous-même avec le Simulateur de Réseaux «Network Simulator SN2 »

5.SUBDIVISION DU TRAVAIL

Notre travail entre dans le cadre de l'étude du mécanisme de routage dans les réseaux mobiles Ad hoc. Notre étude repose principalement sur les travaux de recherche qui ont été fait, et qui se font à l'heure actuelle, dans le but de comprendre le principe d'acheminement de données entre les hôtes mobiles du réseau ad hoc. Pour cela on a subdivisé le travail en quatre chapitres :

i' Le troisième chapitre traite le routage dans les réseaux Ad hoc en donnant quelques exemples de protocoles et leurs classifications selon différents critères.

i' Le quatrième chapitre est consacré à la présentation des deux protocoles de routage (AODV et OLSR) existant dans le contexte des réseaux ad hoc. Nous décrivons les principales caractéristiques et fonctionnalités de chacun d'eux, et leurs manières d'établir les routes entre les hôtes mobiles. Pour conclure ensuite par une simple comparaison entre ces deux protocoles.


	Chapitre Premier : Généralités sur le réseau sans fils (WI FI)

1.1. INTRODUCTION

En 1997, l'élaboration du standard IEEE¹ 802.11 (Institute of Electrical and Electronics Engineers) et son développement rapide fut un pas important dans l'évolution des réseaux locaux sans fil qui se soit en entreprise ou chez les particuliers. Elle a ainsi permis de mettre à la portée de tous un vrai système de communication sans fil pour la mise en place des réseaux informatiques hertziens. Ce standard a été développé pour favoriser l'interopérabilité du matériel entre les différents fabricants. Ceci signifie que les clients peuvent mélanger des équipements de différents fabricants afin de satisfaire leurs besoins. De plus, cette standardisation permet d'obtenir des composants à bas coût, ce qui a permis un succès commercial considérable au 802.11.

La norme IEEE 802.11 est un standard international décrivant les caractéristiques d'un réseau local sans fil (WLAN). Le nom Wi-Fi (contraction de Wireless Fidelity) correspond initialement au nom donné à la certification délivrée par la Wi-Fi Alliance, anciennement WECA² (Wireless Ethernet Compatibility Alliance). Par abus de langage (et pour des raisons de marketing) le nom de la norme se confond aujourd'hui avec le nom de la certification. Ainsi un réseau Wi-Fi est en réalité un réseau répondant à la norme 802.11 Dans ce qui suit nous utiliserons le terme Wi-Fi.

Dans ce chapitre, nous allons commencer par une présentation de la norme Wi-Fi ainsi que ses couches physique et liaison, ensuite nous décrirons le format des trames utilisé dans cette norme, enfin nous allons citer quelques-unes de ses extensions.

1.2. PRESENTATION DE LA NORME WI-FI (802.11)

La norme Wi-Fi est une technologie de réseau informatique qui décrit les couches physiques et MAC d'interfaces réseau radio et infrarouge. Elle offre des débits allant jusqu'à 54 Mbps (tout dépond du milieu) sur une distance de plusieurs centaines de mètres suivant les techniques et les éventuelles extensions de la norme employée. Dans la pratique, le Wi-Fi permet de relier des ordinateurs

² L'organisme chargé de maintenir l'interopérabilité entre les matériels répondant à la norme 802.11

portables, des ordinateurs fixes, des assistants personnels PDA (Personnal Data Assistant) ou tout type de périphérique à une liaison haut débit (11 Mbps ou supérieur).

Le Wi-Fi cible deux contextes d'utilisation distincts pour un réseau WiFi ayant chacun des caractéristiques propres. Il s'agit du mode infrastructure et du mode ad hoc (sans infrastructure). Ces deux modes de fonctionnement permettent de définir la topologie du réseau sans fil.

1.2.1 Description des couches de Wi-Fi :

La norme Wi-Fi définit les deux couches basses du modèle OSI d'un réseau sans fil de type WLAN (Wireless LAN), à savoir une couche liaison de données et une couche physique.

1.2.1.1 La couche physique :

La couche physique définit la modulation des ondes radioélectriques et les caractéristiques de la signalisation pour la transmission de données, elle propose plusieurs types de codage de l'information : DSSS, FHSS, IR, OFDM, toutes ces technologies permettent des débits de 1Mbps et 2Mbps.

C'est une méthode de modulation de signal, qui permet un étalement de spectre en séquence directe. La bande des 2,4 GHz est divisée en 14 canaux de 22 MHz espacés de 5 MHz. Les canaux adjacents se chevauchent partiellement (en cas où deux points d'accès utilisant les mêmes canaux ont des zones d'émission qui se recoupent, des distorsions du signal risquent de perturber la transmission) et seuls trois canaux sur les 14 étant entièrement isolés sont généralement utilisés pour éviter les interférences (ex. 1, 6, 11 ou 1, 7, 13 comme le montre la figure 1.2). Les données sont transmises intégralement sur l'un de ces canaux de 22 MHz, sans saut³.

3 B.GUARET -DUPORT. Les réseaux sans fil (Wi-Fi), Paris, Septembre 2004, P. 23

Cette technique consiste à découper la large bande de fréquence en un minimum de 75 canaux (hops ou saut d'une largeur de 1 MHz), puis de transmettre en utilisant une combinaison de canaux connue de toutes les stations de la cellule. Dans la norme Wi -Fi, la bande de fréquence de 2.4 GHz permet de créer 79 canaux de 1 MHz. La transmission se fait ainsi en émettant successivement sur un canal puis sur un autre pendant une courte période de temps (d'environ 400 ms), l'émetteur et le récepteur s'accordent sur une séquence de Sauts de fréquence porteuse pour envoyer les données successivement sur les différents sous-canaux.

Il est important de remarquer que FHSS et DSSS sont des mécanismes de signalisation fondamentalement différents l'un de l'autre et qu'aucune interopérabilité ne peut être envisagée entre eux.

Une liaison infrarouge permet de créer des liaisons sans fil de quelques mètres avec un débit qui peut atteindre quelques mégabits par seconde. Cette technologie est largement utilisée pour la domotique (télécommandes) mais souffre toutefois des perturbations dues aux interférences lumineuses.

Il est possible grâce à la technologie infrarouge d'obtenir des débits allant de 1 à 2 Mbit/s en utilisant une modulation appelée PPM (pulse position modulation). Cette dernière consiste à transmettre des impulsions à amplitudes constantes, et à coder l'information suivant la position de l'impulsion.

Le principe de cette technique consiste à diviser le signal que l'on veut transmettre sur différentes bandes porteuses, comme si l'on combinait ce signal sur un grand nombre d'émetteurs indépendants, fonctionnant sur des fréquences différentes. Un canal est constitué de 52 porteuses de 300 KHz de largeur, 48 porteuses sont dédiées au transport de l'information utile et 4 pour la correction d'erreurs appelées porteuses pilote, Huit canaux de 20 MHz sont définis dans la bande de 5 GHz (voir FIG 1.3).

1.2.1.2 La couche liaison de données :

La couche liaison de données a pour objectif de réaliser le transport des données et elle est constituée de deux sous-couches :

La couche LLC a été définie par le standard IEEE 802.2, elle permet d'établir un lien logique entre la couche MAC et la couche réseau du modèle OSI (transition vers le haut jusqu'à la couche réseau). Ce lien se fait par l'intermédiaire du Logical Service Access Point (LSA P).

La trame LLC contient une adresse en en-tête ainsi qu'une zone de détection d'erreur en fin de trame : le forward error correction (FEC) comme le montre la figure 1.4 :

Son rôle principal réside dans son système d'adressage logique, qui permet de masquer aux couches hautes les informations provenant des couches basses. Cela permet de rendre interopérables des réseaux complètements

différents dans la conception de la couche physique ou la couche MAC possédant la couche LLC.

La sous-couche MAC est spécifique à la norme Wi-Fi et définit deux nouveaux mécanismes qui assurent la gestion d'accès de plusieurs stations à un support partagé dans lequel chaque station écoute le support avant d'émettre, elle assure aussi le contrôle d'erreur permettant de contrôler l'intégrité de la trame à partir d'un CRC (voir format de trame). Elle peut utiliser deux modes de fonctionnement :

C'est un mode qui peut être utilisé par tous les mobiles, et qui permet un accès équitable au canal radio sans aucune centralisation de la gestion de l'accès (mode totalement distribué). Il met en oeuvre un certain nombre de mécanismes qui visent à éviter les collisions et non pas à les détecter. Dans ce mode tous les noeuds sont égaux et choisissent quand ils veulent parler. Ce mode peut aussi bien être lorsqu'il n'y a pas de station de base (mode ad hoc) que lorsqu'il y en a (mode infrastructure). Ce mode s'appuie sur le protocole CSMA/CA.

Un protocole CSMA/CA (Carier Sense Multiple Access with Collision Avoidance) utilise un mécanisme d'esquive de collision en imposant un accusé de réception systématique des paquets (ACK), ce qui signifie que pour chaque paquet de données arrivé intact, un paquet ACK est émis par la station de réception.

Ce protocole fonctionne de la manière suivante : Une station voulant émettre, doit d'abord écouter le support de transmission, s'il est occupé (par exemple, une autre station est en train d'émettre), alors, la station remet sa transmission à plus tard. Dans le cas contraire, la station est autorisée à transmettre.

La procédure de vérification se fait en utilisant deux types de messages, le premier est appelé RTS (Ready To Send) qui est envoyé par la station et contenant des informations sur le volume des données qu'elle souhaite émettre et sa vitesse de transmission. Le récepteur (généralement un point d'accès) répond

par un deuxième message qui est le CTS (Clear To Send), puis la station commence l'émission des données (voir FIG 1.5) :

A chaque paquet envoyé, l'émetteur doit recevoir un accusé de réception ACK (ACKnowledgement), qui indiquera qu'aucune collision n'a eu lieu.

Si l'émetteur ne reçoit pas de l'accusé de réception, alors il retransmet la trame après un ACK_TIMEOUT jusqu'à ce qu'il obtienne ou abandonne au bout d'un certain nombre de transmission.

Ce type de protocole est très efficace quand le support n'est pas surchargé, mais il y a toujours une chance que des stations émettent en même temps (collision). Cela est dû au fait que les stations écoutent le support, repèrent qu'il est libre, et finalement décident de transmettre, parfois en même temps qu'un autre exécutant, cette même suite d'opération.

Ces collisions doivent être détectées pour que la couche MAC puisse retransmettre le paquet sans avoir à repasser par les couches supérieures, ce qui engendrerait des délais significatifs.

Le (PCF) appelé mode d'accès contrôlé, est fondé sur l'interrogation à tour de rôle des stations, contrôlées par le point d'accès qui indiquera à chacun des mobiles qui lui sont rattachés quand ils doivent émettre leurs paquets. Durant la phase où le point d'accès impose l'ordre des transmissions, il n'y a pas de contention pour l'accès au canal.

Une station ne peut émettre que si elle est autorisée et elle ne peut recevoir que si elle est sélectionnée. Cette méthode est conçue pour les applications temps réel (vidéo, voix) nécessitant une gestion du délai lors des

transmissions de données. Cette méthode est optionnelle et ne fonctionne qu'en mode infrastructure.

1.3 FORMAT DES TRAMES

Le taux d'erreur de transmission sur les réseaux sans fils augmente généralement avec des paquets de taille importante, c'est la raison pour laquelle le Wi-Fi offre un mécanisme de fragmentation, permettant de découper une trame en plusieurs morceaux (fragments).

La norme Wi-Fi définit le format des trames échangées. Chaque trame est constituée d'un en-tête (appelé MAC header, d'une longueur de 30 octets), d'un corps et d'un FCS (Frame Sequence Check) permettant la correction d'erreur.

1.4 LES DIFFERENTES EXTENSIONS WI-FI

Le Wi-Fi est un regroupement de plusieurs normes IEEE 802.11 (802.1 1a, b, g, e, h,...), définissant la transmission de données via le medium «hertzien», elles se différencient principalement selon la bande passante, la distance d'émission, ainsi que le débit qu'elles offrent. Les principales extensions sont les suivantes:

1.4.1 La norme 802.11a :

La norme IEEE 802.11a (baptisé Wi-Fi 5) est définie en 2001. Elle permet d'obtenir un haut débit (54 Mbps théoriques, 30 Mbps réels). Son avantage par rapport aux normes 802.1 1b/g est qu'elle dispose d'une plus grande bande passante (5 GHz) donc peu encombrée, et offre des débits plus importants que 802.11 b (11 Mbps). IEEE 802.11 a utilisé une technique de modulation OFDM. Les inconvénients de cette norme sont sa faible portée (15m) et son incompatibilité avec 802.11b.

1.4.2 La norme 802.11b

Le terme Wi -Fi, fait référence à cette norme qui fut la première norme des WLAN utilisée par un grand nombre d'utilisateurs, elle a été approuvée le 16 Décembre 1999 par l'IEEE. La norme Wi-Fi permet l'interopérabilité entre les différents matériels existants, elle offre des débits de 11 Mbps, avec une portée de 300m dans un environnement dégagé. Elle fonctionne dans la bande des 2,4GHz, séparée en plusieurs canaux. Son inconvénient est le risque d'interférence avec

les appareils fonctionnant aux mêmes fréquences(four à microonde,matériel sans fils...)

1.4.3 La norme 802.11g

Cette norme a été développée en 2003. Elle étend la norme 802.11b, en augmentant le débit jusqu'à 54Mbps théorique (30 Mbps réels). Elle fonctionne aussi à 2,4GHz, ce qui rend les deux normes parfaitement compatibles.

Grâce à cela, les équipements 802.11b sont utilisables avec les points d'accès 802.11g et vice- versa. Cependant, 802.11g utilise la technique de modulation OFDM.

1.4.4 La norme 802.11e

Disponible depuis 2005. Elle vise à donner des possibilités en matière de qualité de service (QoS) au niveau de la couche liaison de données. Ainsi cette norme a pour but de définir les besoins des différents paquets en termes de bande passante et de délai de transmission de telle manière à permettre notamment une meilleure transmission de la voix et de la vidéo.

1.4.5 La norme 802.11h

Elle cherche à mieux gérer la puissance d'émission et la sélection des canaux dans la bande de 5 GHz. Elle vise aussi à rapprocher la norme 802.11 du standard Européen (HiperLAN 2) et être en conformité avec la réglementation européenne en matière de fréquence et d'économie d'énergie.

1.4.6 La norme 802.11i

Ratifié en juin 2004, cette norme décrit des mécanismes de sécurité des transmissions. Elle propose un chiffrement des communications pour les transmissions utilisant les technologies 802.11a, 802.11b et 802.11g. La 802.11i agit en interaction avec les normes 802.11b et 802.11g. Le débit théorique est donc inchangé, à savoir 11 Mbps pour la 802.11b et 45 Mbps pour la 802.11g⁴.

1.5 CONCLUSION

Les réseaux sans fil en général, et le Wi-Fi en particulier sont des technologies intéressantes et très utilisées dans de divers domaines comme

4 J-P HAUET. Aperçu sur les nouvelles communications sans fil et leurs applications dans l'industrie. Université de Nantes, Novembre 2004

l'industrie, la santé et le domaine militaire. Cette diversification d'utilisation revient aux différents avantages qu'apportent ces technologies, comme la mobilité, la simplicité d'installation (absence de câblage), la disponibilité (aussi bien commerciale que dans les expériences).

2.1. INTRODUCTION

Chapitre Deuxième : Préambule sur les réseaux AD HOC

L'évolution récente de la technologie dans le domaine de la communication sans fil et l'apparition des unités de calcul portables poussent aujourd'hui les chercheurs à faire des efforts afin de réaliser le but des réseaux : « L'accès à l'information n'importe où et n'importe quand ».

Le concept des réseaux mobiles ad hoc essaie d'étendre les notions de la mobilité à toutes les composantes de l'environnement. Ici, contrairement aux réseaux basés sur la communication avec infrastructure (cellulaire), aucune administration centralisée n'est disponible, ce sont les hôtes mobiles eux-mêmes qui forment une infrastructure du réseau. Aucune supposition ou limitation n'est faite sur la taille du réseau ad hoc, le réseau peut contenir des centaines ou des milliers d'unités mobiles.

Dans ce chapitre nous allons présenter les environnements mobiles et les principaux concepts liés à ces environnements. Nous commençons par la définition de cet environnement et les deux classes qui le constituent (mode infrastructure et mode sans infrastructure). Nous introduisons ensuite le concept des réseaux ad hoc et les caractéristiques inhérentes à ces réseaux. Enfin nous définissons quelques domaines d'application d'un réseau ad hoc.

2.2. LES ENVIRONNEMENTS MOBILES

Un environnement mobile est un système composé d'unités mobiles et qui permet à ses utilisateurs d'accéder à l'information indépendamment de leurs positions géographiques.

2.3 ARCHITECTURE DES ENVIRONNEMENTS MOBILES

Le réseau sans fil offre deux modes de fonctionnement, le mode avec infrastructure et le mode sans infrastructure ou mode ad hoc.

2.3.1 Le réseau mobile avec infrastructure :

En mode avec infrastructure, également appelé le mode BSS (Basic Service Set) certains sites fixes, appelés stations support mobile (Mobile Support Station) ou station de base (SB) sont munis d'une interface de communication sans fil pour la communication directe avec des sites ou unités mobiles (UM), localisés dans une zone géographique limitée, appelée cellule.

A chaque station de base correspond une cellule à partir de laquelle des unités mobiles peuvent émettre et recevoir des messages. Alors que les sites fixes sont interconnectés entre eux à travers un réseau de communication filaire, généralement fiable et d'un débit élevé. Les liaisons sans fil ont une bande passante limitée qui réduit sévèrement le volume des informations échangées. Dans ce modèle, une unité mobile ne peut être, à un instant donné, directement connectée qu'à une seule station de base.

2.3.2 Le réseau mobile sans infrastructure :

Le réseau mobile sans infrastructure également appelé réseau Ad hoc ou IBSS (Independent Basic Service Set) ne comporte pas l'entité « site fixe », tous les sites du réseau sont mobiles et se communiquent d'une manière directe en utilisant leurs interfaces de communication sans fil (voir FIG 2.3). L'absence de l'infrastructure ou du réseau filaire composé des stations de base, oblige les unités mobiles à se comporter comme des routeurs qui participent à la découverte et la maintenance des chemins pour les autres hôtes du réseau⁵.

5 Mathias Péron, Etude de l'équité dans les réseaux ad hoc, Master's thesis, Ecole Normale Supérieure de Lyon, P.23, 2003

2.4 Les réseaux mobiles ad hoc

2.4.1 Bref historique :

Le début des années 1970 voit, au sein du projet militaire Américain DARPA (The Defense Advanced Research Projects Agency), la naissance des premiers réseaux utilisant le médium radio. Ces réseaux disposaient déjà d'une architecture distribuée, partageaient le canal de diffusion en répétant des paquets pour élargir la zone de couverture globale. Par la suite, en 1983, les Sur vivable Radio Networks (SU RAN) furent développés par le DARPA. L'objectif était de dépasser les limitations (en particulier permettre le passage à des réseaux comportant énormément des noeuds, gérant la sécurité, l'énergie). Mais les recherches sur ces réseaux restaient exclusivement militaires. Ce n'est qu'avec l'arriver du protocole 802.11 de l'IEEE (Institute of Electrical and Electronics Engineers) qui permet de bâtir des réseaux sans fil autour de bases fixes, que la recherche civile s'empare à la fin des années 90 des problématiques liées à ces réseaux.

2.4.2 Définition :

Les réseaux ad hoc auxquels nous nous sommes intéressés sont ceux décrits et étudiés par le groupe de travail MANET (Mobil Ad hoc Network) de l 'IETF (Internet Engineering Tast Force) en France 2007. Une définition de ces réseaux est donnée formellement dans RFC 2501: « Un réseau ad hoc comprend des plates-formes mobiles (par exemple, un routeur interconnectant différents hôtes et équipements sans fil) appelées noeuds qui sont libres de se déplacer sans contrainte. Un réseau ad hoc est donc un système autonome de noeuds mobiles. Ce système peut fonctionner d'une manière isolée ou s'interfacer à des réseaux fixes au travers des passerelles⁶».

6 D. DHOUTA UT. Etude du standard IEEE 802.11 dans le cadre des réseaux ad hoc : de la simulation à l'expérimentation. Thèse de doctorat, Institut National des Sciences Appliquées, Lyon, France, 2003.

2.4.3 Modélisation d'un réseau ad hoc :

Un réseau ad hoc peut être modélisé par un graphe Gt = (Vt, Et). Où : Vt représente l'ensemble des noeuds (par exemple, les unités ou les hôtes mobiles) du réseau et Et modélise l'ensemble des connexions qui existent entre ces noeuds. Si e = (u, v). Et, cela veut dire que les noeuds u et v sont en mesure de communiquer directement à l'instant t.

La topologie du réseau peut changer à tout moment dans l'exemple suivant (F IG 1.4), le noeud A envoie un flux de données au noeud E, pour cela les données sont acheminées par les noeuds G et F. après le mouvement, nous remarquons que le routage des données devient plus complexe puisque le flux ne suit plus le chemin G et F, mais il doit parcourir tous les noeuds B,C,D,G ,F. le réseau est donc dynamique et imprévisible ce qui fait que la déconnexion des unités soit très fréquente.

FIG 2.4 Le changement de la topologie des réseaux ad hoc. 2.4.4. Les caractéristiques des réseaux ad hoc :

Les réseaux mobiles ad hoc sont caractérisés par ce qui suit: 2.4.4.1. L'absence d'infrastructure centralisée :

Les réseaux ad hoc se distinguent des autres réseaux mobiles par la propriété d'absence d'infrastructures préexistante et de tout genre d'administration centralisée. Les hôtes mobiles sont responsables d'établir et de maintenir la connectivité du réseau d'une manière continue.

2.4.4.2. Une topologie dynamique :

Les unités mobiles du réseau, se déplacent d'une façon libre et arbitraire. Par conséquent la topologie du réseau peut changer, à des instants imprévisibles, d'une manière rapide et aléatoire. Les liens de la topologie peuvent être unis ou bidirectionnels.

2.4.4.3 La contrainte d'énergie :

Les équipements mobiles disposent de batteries limitées, et dans certains cas très limitées tels que les PDA (Personal Digital Assistant), et par conséquent d'une durée de traitement réduite. Sachant qu'une partie de l'énergie est déjà consommée par la fonctionnalité du routage. Cela limite les services et les applications supportées par chaque noeud.

2.4.4.4 Une bande passante limitée :

Un des caractéristiques primordiales des réseaux basés sur la communication sans fil est l'utilisation d'un médium de communication partagé. Ce partage fait que la bande passante réservée à un hôte soit modeste.

2.4.4.5 L'hétérogénéité des noeuds :

Un noeud mobile peut être équipé d'une ou plusieurs interfaces radio ayant des capacités de transmission variées et opérant dans des plages de fréquence différentes. Cette hétérogénéité de capacité peut engendrer des liens asymétriques dans le réseau. De plus, les noeuds peuvent avoir des différences en terme de capacité de traitement (CPU, mémoire) de logiciel et de mobilité (lent, rapide). Dans ce cas, une adaptation dynamique des protocoles s'avère nécessaire pour supporter de telles situations.

2.4.4.6 Sécurité et Vulnérabilité :

Dans les réseaux ad hoc, le principal problème ne se situe pas tant au niveau du support physique mais principalement dans le fait que tous les noeuds sont équivalents et potentiellement nécessaires au fonctionnement du réseau. Les possibilités de s'insérer dans le réseau sont plus grandes, la détection d'une intrusion ou d'un déni de service plus délicate et l'absence de centralisation pose un problème de remontée de l'information de détection d'intrusions⁷.

2.4.4.7 Multihops :

Un réseau ad hoc est qualifié par « multihops » car plusieurs noeuds mobiles peuvent participer au routage et servent comme routeurs intermédiaires.

2.4.5 Les domaines d'applications des réseaux mobiles ad hoc :

La particularité du réseau Ad hoc est qu'il n'a besoin d'aucune installation fixe, ceci lui permettant d'être rapide et facile à déployer. Les applications tactiques comme les opérations de secours, militaires ou d'explorations trouvent en Ad Hoc, le réseau idéal. La technologie Ad Hoc intéresse également la recherche, des applications civiles sont apparues. On distingue :

i' Les services d'urgence : opération de recherche et de secours des personnes, tremblement de terre, incendies, dans le but de remplacer l'infrastructure filaire.

bâtiments : dans le cadre d'une réunion ou d'une conférence par exemple.
i' Applications commerciales : pour un paiement électronique distant (taxi)

i' Réseaux de senseurs : Les capteurs, chargés de mesurer les propriétés physiques des environnements (comme la température, la pression...), sont dispersés (le plus souvent lâchés d'un avion ou d'un hélicoptère) par centaines, voire par milliers sur le site, effectuent leurs mesures et envoient les résultats à une station par l'intermédiaire d'un routage ad hoc à travers le réseau.

i' Le cadre informatique : Dans le cadre de l'informatique, les réseaux ad hoc peuvent servir à établir des liens entre ses différents composants. Dans ce cas, on parle non plus de LAN (Local Area Network) mais de PAN (Personnal Area Network)

2.5 CONCLUSION

Le réseau Ad hoc manifeste beaucoup de simplicités et assez d'avantages par rapport aux autres réseaux (filaires et cellulaires) par sa facilité de déploiement en cas d'urgence ou de travaux temporaires dont les autres réseaux engendrent des frais importants. Cependant de nouveaux problèmes apparaissent, en effet l'absence d'une infrastructure centralisée fait du routage dans les réseaux ad hoc un problème très compliqué. Dans la plupart des cas, le noeud destination ne se trouve pas obligatoirement dans la portée du noeud source ce qui implique que l'échange des données entre les deux noeuds doit être effectué par des stations intermédiaires. Par ailleurs, la topologie de ces réseaux qui peuvent être continuellement mobile oblige les protocoles de routage à réagir rapidement.

Après avoir présenté l'environnement mobile ad hoc, une étude sur le routage dans cet environnement sera faite dans le chapitre prochain.

Chapitre Troisième : Routage dans les réseaux AD HOC

3.1 INTRODUCTION

Le routage est une méthode d'acheminement des informations vers la bonne destination à travers un réseau de connexion donnée, il consiste à assurer une stratégie qui garantit, à n'importe quel moment, un établissement de routes qui soient correctes et efficaces entre n'importe quelle paire de noeud appartenant au réseau, ce qui assure l'échange des messages d'une manière continue. Vu les limitations des réseaux ad hoc, la construction des routes doit être faite avec un minimum de contrôle et de consommation de la bande passante⁸.

Dans ce qui suit, nous décrirons brièvement la difficulté de routage dans les réseaux ad hoc et les différents mécanismes de routages apparus pour la résolution de ce problème.

3.2. APERCU SUR LES PROTOCOLES DU RESEAU

Un protocole est une méthode standard qui permet la communication entre des processus (s'exécutant éventuellement sur différentes machines), c'està-dire un ensemble de règles et de procédures à respecter pour émettre et recevoir des données sur un réseau. Il en existe plusieurs selon ce que l'on attend de la communication. Certains protocoles seront par exemple spécialisés dans l'échange de fichiers (le FTP), d'autres pourront servir à gérer simplement l'état de la transmission et des erreurs (c'est le cas du protocole ICMP), ...

3.3 LA DIFFICULTE DU ROUTAGE DANS LES RESEAUX AD HOC

De fait qu'un réseau ad hoc est un ensemble de noeuds mobiles qui sont dynamiquement et arbitrairement éparpillés d'une manière ou l'interconnexion entre les noeuds peut changer à tout moment. Il se peut qu'un hôte destination soit hors de la portée de communication d'un hôte source, ce qui nécessite l'emploi d'un routage interne par les noeuds intermédiaires afin de faire acheminer les paquets de message à la bonne destination.

En effet, la topologie évoluant constamment en fonction des mouvements des mobiles, le problème qui se pose dans le contexte des réseaux ad hoc est l'adaptation de la méthode d'acheminement utilisée avec le grand

8 J.CARSIQUE, N.DAUJEARD, A.LALLEMAND, and R.LADJADJ. Le routage dans les réseaux mobiles Ad hoc. 2003.

nombre d'unités existant dans un environnement caractérisé par de modestes capacités de calcul et de sauvegarde.

D'ailleurs dans la pratique il est impossible qu'un hôte puisse garder les informations de routage concernant tous les autres noeuds, dans le cas où le réseau serait volumineux.

3.4 LES CONTRAINTES DE ROUTAGES DANS LES RESEAUX AD HOC

L'étude et la mise en oeuvre d'algorithmes de routage pour assurer la connexion des réseaux ad hoc au sens classique du terme (tout sommet peut atteindre tout autre), est un problème complexe. L'environnement est dynamique et évolue donc au cours du temps, la topologie du réseau peut changer fréquemment. Il semble donc important que toute conception de protocole de routage doive étudier les problèmes suivants :

i' Minimisation de la charge du réseau : l'optimisation des ressources du réseau renferme deux autres sous problèmes qui sont l'évitement des boucles de routage, et l'empêchement de la concentration du trafic autour de certains noeuds ou liens.

i' Offrir un support pour pouvoir effectuer des communications multi-points fiables : Le fait que les chemins utilisés pour router les paquets de données puissent évoluer, ne doit pas avoir d'incident sur le bon acheminement des données. L'élimination d'un lien, pour cause de panne ou pour cause de mobilité devrait, idéalement, augmenter le moins possible les temps de latence.

i' Assurer un routage optimal : La stratégie de routage doit créer des chemins optimaux et pouvoir prendre en compte différentes métriques de coûts (bande passante, nombre de liens, ressources du réseau,... etc.). Si la construction des chemins optimaux est un problème dur, la maintenance de tels chemins peut devenir encore plus complexe, la stratégie de routage doit assurer une maintenance efficace de routes avec le moindre coût possible.

i' Le temps de latence : La qualité des temps de latence et de chemins doit augmenter dans le cas où la connectivité du réseau augmente.

3.5 CLASSIFICATION DES PROTOCOLES DE ROUTAGE

Vue la difficulté de routage dans les réseaux ad hoc, les stratégies existantes utilisent une variété de techniques afin de résoudre ce problème. Suivant ces techniques, plusieurs classifications sont apparues, parmi lesquelles nous allons citer :

3.5.1 Routage hiérarchique ou plat :

Le premier critère utilisé pour classifier les protocoles de routage dans les réseaux ad hoc concerne le type de vision qu'ils ont du réseau et les rôles qu'ils accordent aux différents mobiles.

Les protocoles de routage à plat : considèrent que tous les noeuds sont égaux (FIG 3.1). La décision d'un noeud de router des paquets pour un autre dépendra de sa position. Parmi les protocoles utilisant cette technique, on cite l'AODV ( Ad hoc On Demand Distance Vector)⁹.

Les protocoles de routage hiérarchique : fonctionnent en confiant aux mobiles des rôles qui varient de l'un à l'autre. Certains noeuds sont élus et assument des fonctions particulières qui conduisent à une vision en plusieurs niveaux de la topologie du réseau. Par exemple, un mobile pourra servir de passerelle pour un certain nombre de noeuds qui se seront attachés à lui. Le routage en sera simplifié, puisqu'il se fera de passerelle à passerelle, jusqu'à celle directement attachée au destinataire. Un exemple est donné sur la figure (FIG 3.2), où le noeud N3 passe par les passerelles P1, P2 et P3 pour atteindre N7. Dans ce type de protocole, les passerelles supportent la majeure partie de la charge du routage (les mobiles qui s'y rattachent savent que si le destinataire n'est pas dans leur voisinage direct, il suffit d'envoyer à la passerelle qui se débrouillera). Un exemple de protocole utilisant cette stratégie est l'OLSR (Optimized Link State Routing)

3.5.2 Le routage à la source et le routage saut par saut :

Le routage à la source : le routage à la source ou << source routing >> consiste à indiquer dans le paquet routé l'intégralité du chemin que devra suivre le paquet pour atteindre sa destination. L'entête de paquet va donc contenir la liste des différents noeuds relayeur vers la destination. Le protocole le plus connu basant sur cette classe est : DSR¹⁰.

Le routage saut par saut : le routage saut par saut ou <<hop by hop>> consiste à donner uniquement à un paquet l'adresse du prochain noeud vers la destination. AODV fait partie des protocoles qui utilisent cette technique.

3.5.3 Etat de lien et Vecteur de distance :

Autres classifications, hérité du monde filaire, est possible pour les protocoles de routage : les protocoles basés sur l'état des liens et sur le vecteur de distance. Les deux méthodes exigent une mise à jour périodique des données de routage qui doivent être diffusées 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 la technique 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 court existant dans le réseau.

Les protocoles basés sur l'état de lien : La famille des protocoles à état de liens se base sur les informations rassemblées sur l'état des liens dans le réseau. Ces informations sont disséminées dans le réseau périodiquement ce qui permet ainsi aux noeuds de construire une carte complète du réseau. Un noeud qui reçoit les informations concernant l'état des liens, met à jour sa vision de la topologie du réseau et applique un algorithme de calcul des chemins optimaux afin de choisir

le noeud suivant pour une destination donnée. En générale ces algorithmes se basent sur le principe de l'algorithme de Djikstra pour calculer les chemins les plus courts entre un noeud source et les autres noeuds du réseau. . Les principaux protocoles de routage dans les réseaux ad hoc qui appartiennent à cette classe sont les suivants : TORA¹¹ , OLSR et TBRPF¹².

Les protocoles basés sur le vecteur de distance : Les protocoles à vecteur de distance se basent sur un échange, entre voisins, des informations de distances des destinations connues. Chaque noeud envoie à ses voisins la liste des destinations qui lui sont accessibles et le coût correspondant. Le noeud récepteur met à jour sa liste locale des destinations avec les coûts minimums. Le processus de calcul se répète, s'il y a un changement de la distance minimale séparant deux noeuds, et cela jusqu'à ce que le réseau atteigne un état stable. Les calculs des routes se basé sur le principe de l'algorithme distribué de Bellman-Ford (DBF). Les protocoles de routage basés sur le vecteur de distance les plus connus pour les réseaux ad hoc sont : DSR, DSDV¹³ et AODV.

3.5.4 L'inondation :

L'inondation ou la diffusion pure, consiste à répéter un message dans tous les réseaux .Un noeud qui initie l'inondation envoie le paquet à tous ses voisins directe, de même si un noeud quelconque de réseau reçoit le paquet pour la première fois, il le rediffuse à tous les voisins, Ainsi de proche en proche le paquet inonde le réseau¹⁴(FIG 3.3).

Notons que les noeuds peuvent être anienes appliques (durant l'inondation) certain traitement de contrôle dans le but d'éviter certains problèmes, tel que le bouclage et la duplication des messages, Le mécanisme d'inondation est utilisé généralement dans la première phase du routage plus exactement dans la procédure de découverte des routes, et cela dans le cas où le noeud source ne connaît pas la localisation exacte de la destination.

14 S. KACI et N. KHOULALENE Proposition d'un protocole de routage avec différenciation de terminaux dans les réseaux ad hoc. Université A. Mira, Bejaia, Algérie, 2006

3.5.5 Le concept de groupe :

Dans la communication de groupe, les messages sont transmis à des entités abstraites ou groupes, les émetteurs n'ont pas besoin de connaître les membres du groupe destinataire. La gestion des membres d'un groupe permet à un élément de se joindre à un groupe, de quitter ce groupe, se déplacer ailleurs puis rejoindre le même groupe. C'est en ce sens que la communication de groupe assure une indépendance de la localisation, ce qui la rend parfaitement basées sur les groupes. Le concept de groupe facilite les taches de la gestion du routage (telles que les transmissions des paquets, l'allocation de la bande passante etc.) et cela en décomposant le réseau en un ensemble de groupes connectés.

3.5.6 Protocoles uniformes et non-uniformes :

Certains protocoles de routage n'utilisent pas tous les noeuds d'un réseau pour faire transiter les messages, au contraire ils en sélectionnent certains, en fonction du voisinage ou pour former des cellules. Ces protocoles sont dits non-uniformes. Ceux qui utilisent tous les noeuds du réseau capables de router sont appelés protocoles uniformes.

3.5.7 La classification de MANET :

C'est la classification qui nous intéresse et qu'on maintient pour la suite de ce chapitre. 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 : Proactif, Réactif et Hybride.

3.5.7.1 Les protocoles de routage proactifs :

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 noeuds du réseau) au niveau de chaque noeud du réseau, Les routes sont sauvegardées même 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. Le plus abouti de ces protocoles est OLSR.

Avec un protocole proactif, les routes sont disponibles immédiatement, ainsi l'avantage d'un tel protocole est le gain de temps lors d'une demande de route. Le problème est que, les changement de routes peuvent être plus fréquents que la demande de la route et le trafic induit par les messages de contrôle et de mise à jour des tables de routage peut être important et partiellement inutile, ce qui gaspille la capacité du réseau sans fil. De plus, la taille des tables de routage croit linéairement en fonction du nombre de noeud.

De ce fait, un nouveau type de protocole a apparu, il s'agit des protocoles de routage réactifs.

3.5.7.2 Les protocoles de routage réactifs :

Les protocoles de routage réactifs (dits aussi: protocoles de routage à la demande), représentent les protocoles les plus récents proposés dans le but d'assurer le service du routage dans les réseaux sans fils.

La majorité des solutions proposées pour résoudre le problème de routage dans les réseaux ad hoc, et qui sont évaluées actuellement par le groupe de travail MANET (Mobile Ad Hoc Networking working Groupe) de l'IETF (Internet Engineering Task Force), appartiennent à cette classe de protocoles de routage.

Les protocoles de routage appartenant à cette catégorie, créent et maintiennent les routes selon les besoins. Lorsque le réseau a besoin d'une route, une procédure de découverte globale de routes est lancée, et cela dans le but d'obtenir une information. Actuellement, le plus connu de ces protocoles est AODV.

A l'opposé des protocoles proactifs, dans le cas d'un protocole réactif, aucun message de contrôle ne charge le réseau pour des routes inutilisées ce qui permet de ne pas gaspiller les ressources du réseau. Mais la mise en place d'une route par inondation peut être coûteuse et provoquer des délais importants avant l'ouverture de la route et les retards dépassent bien souvent les délais moyens admis par les logiciels, aboutissant à une impossibilité de se connecter alors que le destinataire est bien là.

De ce fait, un nouveau type de protocole a apparu, il s'agit des protocoles de routage hybrides.

3.5.7.3 Les protocoles de routage hybrides :

Dans ce type de protocole, on peut garder la connaissance locale de la topologie jusqu'à un nombre prédéfini- a priori petit- de sauts par un échange périodique de trame de contrôle, autrement dit par une technique proactive. Les routes vers des noeuds plus lointains sont obtenues par schéma réactif, c'est-àdire par l'utilisation de paquets de requête en diffusion. Un exemple de protocoles appartenant à cette famille est DSR (Dynamic Source Routing), qui est réactif à la base mais qui peut être optimisé s'il adopte un comportement proactif. Un autre exemple est le protocole ZRP (Zone Routinier Protocol).

Le protocole hybride est un protocole qui se veut comme une solution mettant en commun les avantages des deux approches précédentes en utilisant une notion de découpe du réseau.

Cependant, il rassemble toujours quelques inconvénients des deux approches proactives et réactives.

3.6 CONCLUSION

Dans ce chapitre nous avons abordé la notion et les problèmes de routage dans les réseaux Ad hoc.

Comme nous avons vu, le problème de routage est loin d'être évident dans cet environnement, où ce dernier impose de nouvelles limitations par rapport aux environnements classiques. Les stratégies de routage doivent tenir compte des changements fréquents de la topologie, de la consommation de la bande passante qui est limitée, ainsi d'autres facteurs.

Finalement, nous avons présent vue classification de protocole de routage dans les environnements mobiles, avec quelques exemples pour les protocoles de routage proactif et réactif qui ont été conçu pour les réseaux Ad hoc,

Dans notre dernier chapitre nous allons nous détailler sur le fonctionnement de ces deux protocoles OLSR et AODV qui sont les plus avancés sur la voie d'une normalisation. Nous présenterons en outre leur impacts dans le routage d'un réseau sans en mode Ad-hoc.

Chapitre Quatrième : Protocoles de routage OLSR et AODV et leur impact dans le routage wi fi en mode ad hoc

4.1. INTRODUCTION

Lors de la transmission d'un paquet d'une source vers une destination, il est nécessaire de faire appel à un protocole de routage qui acheminera correctement le paquet par le «meilleur » chemin. Plusieurs protocoles ont été proposés au niveau ad hoc. Afin de comprendre leurs comportements dans des réseaux mobiles, nous nous sommes intéressés donc à faire une étude théorique sur quelques protocoles, pour cela, la première étape à faire est celle du choix des protocoles sur lesquels se baser. Notre choix s'est porté sur AODV et OLSR. En effet, ces protocoles montrent une meilleure qualification.

AODV et OLSR sont représentatifs de diverses techniques et sont les plus avancés sur la voie d'une normalisation. Le premier utilise un mécanisme de diffusion (broadcast) dans le réseau pour découvrir les routes valides. Le second est proactif, appelé OLSR (Optimized Link State Routing Protocole). Il utilise un mécanisme qui permet de designer un sous-ensemble de son voisinage responsable de la dissémination des informations de contrôle de topologie dans les réseaux à moindre coût.

Ces deux protocoles (AODV et OLSR) font désormais l'objet d'une Request For Comment(RFC), tandis que les autres sont à des versions assez stables de leurs drafts.

Dans ce chapitre, nous allons présenter ces deux protocoles, en commençant par une étude détaillée sur le protocole de routage AODV et sa manière d'agir, on décrira par la suite le protocole OLSR et son principe de fonctionnement et on finira par une brève comparaison entre ces deux protocoles de routage.

4.2. PRESENTATION DU PROTOCOLE DE ROUTAGE AODV «Ad hoc On demand Distance Vector»

4.2.1 Definition :

AODV est un protocole de routage réactif et basé sur le principe des vecteurs de distance, capable à la fois de routage unicast et multicast. Il représente essentiellement une amélioration de l'algorithme proactif DSDV¹⁵.

4.2.2. Le type des messages dans AODV :

- les messages de demande de route RREQ : Route Request Message. - les messages de réponse de route RREP : Route Reply Message.

En plus des messages cités avant, l'AODV utilise des paquets contrôle HELLO qui permettent de vérifier la connectivité des routes.

4.2.3 Le principe de numéro de séquence :

La circulation inutile des paquets de messages, qui peut arriver avec le DBF (Distribution de Bellman Ford), est intolérable dans les réseaux mobiles ad hoc, caractérisés par une bande passante limitée et des ressources modestes.

L'AODV utilise les principes de numéro de séquence afin d'éviter le problème des boucles infini et des transmissions inutiles de messages sur le réseau, en plus il permet de maintenir la consistance des informations de routage. A cause de la mobilité des noeuds dans le réseau ad hoc, les routes changent fréquemment ce qui fait que les routes maintenues par certains noeuds, deviennent invalides. Les numéros de séquence permettent d'utiliser les routes les plus nouvelles ou autrement dit les plus fraiches (fresh routes), un noeud mis à jour chaque fois qu'une nouvelle information provenant d'un message RREQ, RREP ou RERR, il incrémente son propre numéro de séquence dans les circonstances suivantes :

- Il est lui-même le noeud destination et offre une nouvelle route pour l'atteindre.

- Il reçoit un message AODV (RREQ, RREP, RERR) contenant de nouvelles informations sur le numéro de séquence d'un noeud destination.

- Le chemin vers une destination n'est plus valide. 4.2.4 Fonctionnement de protocole :

Dans cette partie nous détaillerons le fonctionnement de protocole AODV, en commençant d'abord par la manière dont il découvre les routes, nous parlerons par la suite sur la façon dont il maintient ces routes, une fois valides.

4.2.4.1 Découverte de route :

Lorsqu' un noeud veut émettre un message, il cherche dans sa table de routage si une route valide existe pour la destination qu'il souhaite atteindre, s'il n'en existe aucune, il se met à la recherche d'une route.

Cette tâche est réalisée par la diffusion de message RREQ sur une adresse de type broadcast au travers de réseau. Le champ numéro de séquence destination de paquet RREQ, contient la dernière valeur connue du numéro de séquence associé au noeud 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. Avant l'envoi du paquet RREQ, le noeud origine sauvegarde l'identificateur du message et l'adresse IP de façon à ne pas traiter le message dans le cas où un voisin le lui renverrait. Une fois la demande de route effectuée, le noeud demandeur se met en attente de réponses.

Quand un noeud de transit (intermédiaire) reçoit le paquet de la requête, il vérifie dans stable historique si cette requête a déjà été vue et traitée. Si le paquet est doublon, le noeud doit l'ignorer et arrêter le traitement. Dans le cas contraire le couple (@ source, ID de requête) sera inscrit dans la table historique pour rejeter le future doublon, et le noeud continue le traitement en cherchant la destination dans sa table de routage : s'il possède une route récente, à noter qu'une route est récente si le numéro de séquence de la destination dans la table est supérieure ou égale au numéro de séquence dans le paquet RREQ. Dans ce cas, le noeud envoi un paquet de réponse (RREP) à la source lui indiquant comment atteindre la destination. Autrement le noeud ne connait pas la route vers la destination : il incrémente le nombre de sauts et rediffuse le paquet.

Avant de l'envoi de paquet, le noeud intermédiaire sauvegarde l'adresse du noeud précédent et celle du noeud source à partir duquel la première copie de la requête est reçue. Cette information est utilisée pour construire le chemin inverse, qui sera traversé par le paquet réponse de la route de manière unicast (cela veut dire qu'AODV supporte seulement les liens symétriques).

notée dans les tables le champ hop count de message route RREP est incrémentée à chaque noeud traversé, une fois le noeud origine atteint, la valeur du champ hop count représente la distance en nombre de sauts pour aller du noeud source vers le noeud destination. Quand le noeud reçoit une réponse de route, le paquet est examiné, et une entrée pour la route vers la destination est inscrite dans la table de routage si au moins une de ces conditions est satisfaite :

> le numéro de séquence pour la destination dans le paquet de réponse est supérieure à la valeur présente dans la table de routage.

> les numéros de séquences sont égaux mais la nouvelle route est plus courte.

Afin de limiter le coût dans le réseau, AODV propose d'étendre la recherche progressivement, initialement, la requête RREQ est diffusée à un nombre de sauts limité. Si la source ne reçoit aucune réponse après un délai d'attente déterminé, elle retransmet un autre message de recherche en augmentant le nombre maximum de sauts. En cas de non réponse, Cette procédure est répétée un nombre maximum de fois avant de déclarer que cette destination est injoignable.

A chaque nouvelle diffusion, le champ Broadcast ID du paquet RREQ est incrémenté pour identifier une requête de route particulière associée à une adresse source. Si la requête RREQ est rediffusée un certain nombre de fois (RREQ.RETRIES) sans réception de réponse, un message d'erreur est délivré à l'application.

4.2.4.2 Maintenance des routes :

AODV maintient les routes aussi longtemps que celles-ci sont actives, une route est considérée active tant que des paquets des données transitent périodiquement de la source a la destination selon ce chemin. Lorsque la source stoppe d'émettre des paquets des données, le lien expirera et sera effacé des tables de routage des noeuds intermédiaires. Si un lien se rompt lorsqu'une route est active, le lien est considéré défaillant. Les défaillances des liens sont, généralement, dues à la mobilité du réseau ad hoc.

Afin de détecter cette défaillance, AODV utilise les messages de contrôle <<HELLO>> qui permettent de vérifier la connectivité ou plutôt l'activité des routes. Un noeud détermine l'activité d'une route en écoutant périodiquement les messages <<HELLO>> transmis par ses voisins. Si pendant un laps de temps, trois messages <<HELLO>> ne sont pas reçus consécutivement, le noeud considère

que le lien -vers ce voisin est cassé. Il envoie un message d'erreur (RERR) à la source et la route devient invalide¹⁶.

En fait, lors de la rupture d'un lien d'une route active, AODV tente de réparer la connectivité localement en diffusant une requête de recherche de route dans le voisinage. Si cette tentative échoue, alors la route est supprimée, et nouvelle recherche de route est lancée par la source.

4.2.5 Avantages et Inconvénients :

L'un des avantages d'AODV est l'utilisation de numéro de séquence dans les messages. Ces numéros de séquences permettent l'éviter les problèmes de boucles infinis et sont essentiels au processus de mise à jour de la table de routage.

Un autre avantage est le rappel de l'adresse IP du noeud origine dans chaque message. Ceci permet de ne pas perdre la trace du noeud à l'origine de l'envoi du message lors des différents relais.

Un inconvénient d'AODV est qu'il n'existe pas de format générique des messages. Chaque message a son propre format : RREQ, RREP, RERR.

4.3 PRESENTATION DU PROTOCOLE DE ROUTAGE OLSR (Optimized Link State Routing)

4.3.1 Définition :

OLSR est un protocole de routage proactif, conçu pour fonctionner dans un environnement mobile distribué sans aucune entité centrale le contrôlant et réagissant à la mobilité (réseaux Ad hoc). Il est utilisé dans les réseaux denses et peu mobiles.

Il représente une adaptation et une optimisation du principe de routage à état de lien pour les réseaux ad hoc. Il permet d'obtenir les routes de plus court chemin. L'optimisation tient au fait que dans un protocole à état de lien, chaque noeud déclare ses liens directs avec tous ses voisins à tout le réseau. Dans le cas d'OLSR, les noeuds ne vont déclarer qu'une sous partie de leur voisinage par l'utilisation de relais multipoints MPR (Multipoint Relay).

4.3.2 Le format du paquet OLSR :

Contrairement à AODV qui offre un format spécifique à chacun de ces messages, le protocole OLSR définit un format général du paquet, donné sur la figure. Ce format est unique pour tous les messages circulant sur le réseau.

En plus des messages d'échange de trafic de contrôle HELLO et TC (Topologie Control), le protocole OLSR propose deux autres types différents de messages: MID (Multiple Interface Declaration) et HNA (Host and Network Association)

Chaque paquet peut contenir plusieurs messages identifiés par un type. Ceci permet d'envoyer plusieurs informations à un noeud en une seule transmission. Selon la taille de MTU (Maximum Transfer Unit), un noeud peut ajouter de différents messages et les transmettre ensemble. Par conséquent différents types de messages peuvent être émis ensemble mais traités et retransmis différemment dans chaque noeud. Quand ce dernier reçoit un paquet, il examine les entêtes des messages et en détermine le type selon la valeur du champ message type. Dans OLSR, un message du control individuel est uniquement identifié par une adresse initiale (Originator address) et son numéro de séquence MSN (Message Sequence Num ber).

Le champ Originator address indique la source d'un message, par contre au champ MSN nous permet d'éviter le traitement et relayage multiple de même message pour un noeud.

Le routage des données, se fait saut par saut. Sur la base des informations reçus à partir des paquets de contrôle (HELLO et TC) envoyés par un noeud du réseau, chaque noeud / routeur calcule sa table de routage. Le protocole OLSR ne manipule pas directement les paquets de données. C'est la couche IP (réseau) qui prend en charge les paquets de données et les routes suivant les informations contenues dans sa table de routage. OLSR utilise le format standard des paquets I P pour envoyer les messages de contrôle.

4.3.3 Le principe de relais multipoint(MPR) :

Le concept des relais multipoint vise à réduire le nombre de messages de contrôle inutiles lors de l'inondation dans le réseau.

Le principe se base sur une règle (appelé règle de multipoint) : dont chaque noeud choisit une sous partie minimale de ses voisins symétriques à un saut, de tel sorte à pouvoir atteindre tout le voisinage à deux sauts (les voisins des voisins).

Cet ensemble de noeuds choisi, s'appelle « le relais multipoint » (MPR).Le relais multipoint porte des avantages du fait qu'il permet une diffusion optimisée en minimisant l'utilisation de la bande passante en évitant l'envoi périodique des messages de contrôle à tout le réseau. La diffusion par relais multipoint se fait différemment de la diffusion classique par inondation .Dans la diffusion classique par inondation un noeud retransmet un message s'il ne l'a pas déjà reçu. Par les relais multipoint on obtient une optimisation en ajoutant une condition : si le message n'est pas déjà reçu, et le noeud est considéré comme MPR pour le noeud dont il a reçu le message. Un noeud N1 qui ne fait pas parti de l'ensemble des MPR de noeud N2 reçoit et traite les messages envoyés par N2 mais ne les retransmette pas.

La figure donne un exemple de gain en nombre de messages transmis. Le nombre de messages dans l'inondation pure est de 54 messages, alors que dans le cas des Relais multipoint est de 34 messages.

OLSR fournit des routes optimales en nombre de sauts, il convient pour les grands réseaux grâce à son mécanisme de MPR, mais sans doute moins efficace pour de petits réseaux.

Les MPR d'une diffusion ne seront pas forcément les mêmes, puisque chaque noeud sélectionne ses MPR comme bon lui semble, donc chaque noeud N a son propre ensemble de MPR cet ensemble est dénoté MPR(N). Par conséquent un noeud MPR maintient des informations sur les noeuds qui l'ont choisi comme MPR. Cet ensemble s'appelle << le sélecteur de relais multipoint>> (MPR selector set).

4.3.4 Fonctionnent du protocole :

Dans ce qui suit, on va se détailler sur le fonctionnement de protocole OLSR en commençant d'abord par la détection de voisinage ensuite la sélection des relais multipoint, on parlera par la suite comment le protocole gère la topologie de réseau et on finira par ses messages MID et H NA. Pour bien comprendre le principe de fonctionnement d'OLSR, pour tout le reste de chapitre, on considère un réseau Ad hoc déployé avec 10 noeuds, chaque noeud est équipé d'une seule interface réseau.

4.3.4.1 Détection de voisinage :

Pour accomplir le choix des relais multipoint, chaque noeud doit déterminer ses voisins symétriques directs, mais vue la mobilité des réseaux Ad hoc, certains liens peuvent devenir asymétriques, par conséquent, il faut tester tous les liens dans les deux sens avant de les considérer valides. Pour cela OLSR propose le mécanisme de détection de voisinage, ce mécanisme est assuré par l'échange périodique des messages << HELLO >> qui contient des informations sur les voisins connus et l'état des liens avec ceux-ci. La fonction des messages <<HELLO >> est multiple. Il permet à un noeud de renseigner sa table de voisinage afin de connaitre ses voisins directs et leurs types de lien. Et comme chaque noeud

diffuse ce type de message, un noeud peut acquérir des informations sur les voisins de ses voisins directs, donc il aura la topologie du réseau à deux sauts.

A base de ses informations un noeud choisit ses MPR, après leur sélection, il les déclare dans une partie de message « HELLO ». Ceci permet à un noeud de savoir quels voisins l'ont choisi comme MPR, autrement dit de construire la liste M PRset. A la réception de message « HELLO », chaque noeud mis à jour sa table de voisinage pour sauvegarder ses voisins à un saut et leurs types de lien à savoir (symétriques, asymétriques ou MPR).

4.3.4.2 Gestion de topologie :

Vu que dans les réseaux Ad hoc, la topologie est totalement distribuée et les noeuds peuvent se déplacer, se connecter et se déconnecter facilement du réseau. Alors, il est indispensable de vérifier à chaque fois la topologie du réseau.

Le contrôle de la topologie ne se fait que par les noeuds élus comme MPR. Ces noeuds diffusent périodiquement des messages de contrôle de la topologie TC (Topology Control).

Le message TC contient l'adresse de générateur du message, l'adresse du noeud destinataire, le numéro de séquence et la durée de vie du message. Il envoit dans ce message l'ensemble des noeuds qui ont sélectionné ce noeud comme MPR (MPR selector_set). Cette information va aider les autres noeuds à construire leur table topologique, puis leur table de routage.

Dans l'exemple ci-après, nous présenterons l'ensemble des MPR choisis par chaque noeud. Les MPR_selestor de chaque noeud élu comme MPR ainsi que la table topologique du noeud A.

MPR(C) = {A, D} MPR(D) = {C, J} MPR(E) = Ø MPR(F) = {A, G} MPR(G) = {B, F} MPR(H) = {F} MPR(I) = {J} MPR(J) = {D}

Noeuds destinataire	Noeud du dernier saut	Numéro de séquence	Durée de vie
B	G	SN1	T1
C	D	SN2	T2
D	C	SN3	T3
F	G	SN4	T4
G	B	SN5	T5
H	F	SN6	T6
I	J	SN7	T7
J	D	SN8	T8
D	J	SN9	T9
G	F	SN10	T10

A 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.

4.3.4.3 Le calcul de la route :

Puisque le réseau est dynamique et sans infrastructures centralisé d'autres noeuds peuvent se connecter et déconnecter a tout moment, ce qui provoque le changement de la topologie du réseau et les liens entre les noeuds.

Le protocole OSLR est conçu pour trouver et recalculer les routes, il offre des routes optimales (nombre de sauts minimal) entre les noeuds de réseau. Pour calculer ces routes, il est indispensable de connaitre la topologie de réseau

(avoir la table topologique du réseau) et avoir la liste des voisins et leurs types de liens.

Une fois les routes sont trouvées, le noeud construit sa table de routage. La table de routage contient l'adresse de premier saut à suivre (R_dest_addr), adresse du noeud destinataire, le nombre de sauts qui sépare les deux noeuds ainsi que l'interface de noeuds local.

Dans la table ci - bas nous allons voir la table de routage associé au noeud A de l'exemple de la Figure.

Noeuds destinataire	Noeud suivant	Nombre de sauts	Interface
B	Directe	1	IF A
C	Directe	1	IF A
D	C	2	IF A
E	Directe	1	IF A
F	Directe	1	IF A
G	B	2	IF A
G	F	2	IF A
H	F	2	IF A
I	C	4	IF A

Tout changement dans la table topologique ou la table de voisinage provoque automatiquement la modification de la table de routage.

Par exemple, dans la figure suivante si le noeud D veut envoyer un message au noeud F, il a la possibilité d'emprunter deux routes, mais toujours OLSR prend la route optimale (en termes de nombre de sauts).

4.3.5 Les messages MID (Multiple Interface Declaration) :

Ces messages sont émis que par un noeud qui a des interfaces OLSR multiples, afin d'annoncer des informations sur la configuration de ses interfaces au réseau. Un message MID contient une liste d'adresses, L'adresse I_if_addr correspond à une interface ainsi que I_main_addr est l'adresse principale du noeud émetteur. La diffusion de ces messages se fait par les relais multipoints afin de minimiser le nombre de messages circulants sur le réseau.

4.3.6 Les messages HNA (Host and Network Association):

Ils sont émis que par un noeud qui a des interfaces non-MANET multiples, dont le but est de fournir la connectivité d'un réseau OLSR à un réseau non OLSR. Le noeud passerelle émet des messages HNA contenant une liste d'adresses des réseaux associés et de leurs masques réseau (netmasks).donc, les noeuds se trouvant dans les réseaux MANET vont construire des tuples pour tous les noeuds passerelles où chaque tuple contient :

V' A_geteway_addr : adresse principale du noeud passerelle. V' A_network_addr : adresse de sous réseau.

4.3.7 Avantages et inconvénients :

D'après la présentation ci-dessus du protocole de routage OLSR, nous remarquons qu'il offre des fonctionnalités très intéressantes tout en recherchant des routes optimales en termes de nombre de sauts, il diminue au maximum le nombre de messages de contrôle transmis sur le réseau, en utilisant la technique de sélection des MPR. OLSR gère convenablement la topologie du réseau, en expédiant périodiquement des messages TC et il peut contrôler l'utilisation

multiple des interfaces (messages MID) ainsi qu'OLSR offre la possibilité de communication entre un réseau MANET et un réseau filaire (messages HNA)

Tous ces avantages du protocole OLSR ne veut pas dire qu'il n'a pas d'inconvénients, or que le problème actuel d'OLSR est celui de la sécurité¹⁷. Malgré que ces dernières années beaucoup de recherches ont été faites pour améliorer sa protection contre les attaques, mais OLSR reste toujours vulnérable à certaines attaques.

4.4. CONCLUSION

OLSR et AODV, bien que de nature très différentes, sont très similaires en termes de performances. Dans un réseau très mobile, avec de fréquent changement de topologie, AODV a un petit avantage sur OLSR car les routes sont mises à jours plus rapidement. OLSR doit attendre plusieurs paquets Hello perdus avant de modifier l'état du lien et envoyer des informations de mise à jour. Par contre, dans un réseau plus statique, OLSR encombre moins le réseau qu'AODV qui émet beaucoup plus de messages à chaque découverte de route. En effet dans ce cas OLSR n'émet presque pas de message de mises à jour de la topologie.

Dans un réseau très dense, OLSR charge moins le réseau qu'AODV. Dans des réseaux moyens, OLSR et AODV sont équivalent. Lors de communications courtes, OLSR à un énorme avantages sur AODV car les routes sont disponible immédiatement. Dans la plupart des cas, les messages de contrôles d'AODV sont légèrement plus nombreux que ceux d'OLSR. AODV émets d'autant plus de paquets que le réseau est grand.

Ce chapitre a été axé le fonctionnement et le comportement de chacun des protocoles AODV et OLSR dans les réseaux Ad hoc et se finit par une petite comparaison entre eux, en faisant face à des avantages et inconvénients.

17 M. Aljnidi. Modèle, architecture et protocoles de sécurité pour les réseaux autonome mobiles. Thèse de L'ENST.2005

CONCLUSION GENERALE

Le problème du routage dans les réseaux sans fil en mode ad hoc est le défi le plus difficile à réaliser, car il s'agit de trouver une route optimale multisauts qui relie deux noeuds quelconques du réseau. Ce routage est donc un problème d'optimisation sous contraintes. Parmi ces contraintes, nous avons cité les changements de topologies et la volatilité des liens, la capacité limitée de la bande passante, etc. La longueur du chemin entre un noeud source et un noeud 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. Nous avons cité trois grandes familles de protocoles, à savoir les protocoles proactifs, réactifs et hybrides.

Dans ce Travail, nous nous sommes intéressés à l'impact de la mobilité des noeuds 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. Les protocoles AODV et OLSR.

Il ressort de tout ce qui précède que le protocole OLSR est un peu supérieur à AODV car s'il est équivalent dans la plupart des réseaux, il est meilleur dans certains cas particuliers comme des réseaux denses soit des réseaux où le trafic est important et composés de nombreuses et courtes connexions.

BIBLIOGRAPHIE

TABLE DES MATIERES

EPIGRAPHIE.....................................................................................................................

DEDICACE... ..................................................................................................................

...II REMERCIEMENTS............................................................................................................ .III

ABREVIATIONS...................................................................................................... IV

Etude sur les protocoles de routage d'un réseau sans fil en mode Ad Hoc et leurs impacts. "cas de protocoles OLSR et AODV"