Routage Avec Qos Dans Aodv

Ministère de L'Enseignement Supérieur et de la Recherche Scientifique

Université Mouloud MAMMERI de TIZI-OUZOU Faculté du Génie Electrique et d'Informatique Département d'Informatique

Présenté pour obtenir le titre d’ingénieur d’état Spécialité : INFORMATIQUE Option : INFORMATIQUE INDUSTRIELLE

Thème

Routage avec Qualité de Service dans AODV Présenté par Houari MAOUCHI Encadreurs : Mme Mr

Nadia NOUALI Nadir BOUCHAMA

Maitre de recherche CERIST Attaché de recherche CERIST

Année 2008 -2009

In the Name of Allah, the Benificent, the Merciful

My prayer and my sacrifice and my life and my death are surely for Allah, Allah, the Lord of the worlds Le Saint Coran

ii

DÉDICACES

A ma chère mère pour ses sacrifices depuis qu’elle m’a mis au monde, A la mémoire de mon père, A ma tante Zhira, ma deuxième mère, A mes frères et mes sœurs, A mon cousin et mon ami Zoubir et son frère Merzak, A toute ma grande famille, A tous mes amis dont la liste est longue, Enfin à tous ceux que j’aime et ceux qui m’aiment, J’exprime mes sentiments les plus profonds Et leur dédie ce modeste travail.

iii

REMERCIEMENTS

En premier lieu, je remercie le Bon Dieu de m’avoir donné la force et le courage pour accomplir ce travail et qui m’a procuré ce succès. Mes très vifs remerciements vont à l’encontre de mes encadreurs M eme Nadia NOUALI et Mr. Nadir BOUCHAMA, pour avoir accepté de m’encadrer et de m’orienter tout au long de ce travail, je les remercie une deuxième fois pour leur patience, leur sympathie et leurs conseils. Je

remercie

département

vivement

tous

d’Informatique de

les

enseignants

l’université

de

Mouloud

Mammeri de TIZI-OUZOU pour tous les efforts qu’ils ont fournis toute au long de cette formation. Je remercie également les membres du jury qui ont accepté de juger ce travail. Que toute personne qui, d'une manière ou d'une autre, m’a aidé et encouragé à l'aboutissement de ce travail, trouve ici l'expression de mes sincères reconnaissances.

iv

Table des matières Table des Matières …...………………………………………………………………………. v Table des Figures . . …………………………………………………………………………..viii Liste des tableaux …………….……………………………………………………………… x Introduction Générale ………………………………………………………………………..01

Chapitre I : Généralités sur les réseaux sans fil 1 introduction………………………………………………………………………………...04 2 Les réseaux sans fil … …………………………………………………………………...04 2.1 Historique ..………………………………………………………………………….04 2.2 Définition…………………………………………………………………………….05 2.3 Caractéristiques ……………………………………………………………………...05 2.4 Classification des réseaux sans fil ………………………………………………….... 05 2.4.1 Selon la zone de couverture……………………………………………………. 05 2.4.2 Selon le mode de fonctionnement ……………………………………………....06 2.4.3 Selon la topologie du réseau……………………………………………………. 08 3 Présentation de la norme 802.11…………………………………………………………... 09 3.1 Le modele de référence OSI ….…………………………………………………… 09 3.2 Les réseaux sans fil et le modèle OSI ………………………………………….........11 3.3 Le standard 802.11…..……………………………………………………………. 11 3.3.1 Couche physique ……………………………………………………………...11 3.3.2 la couche liaison de données ……………………………………………….. 12 3.3.2.1 la sous-couche LLC (Logical Link Control) ……..………………….………12 3.3.2.2 la sous-couche MAC (Medium Access Control) .. ………………………..… 12 3.4 Les différentes dérivées de la norme 802.11 …..…………………………………....16 4 Les réseaux mobiles ad hoc …………………………………………………………………17 4.1Définition……………………………………………………………………………..17 4.2 Modélisation………………………………………………………………………… 17 4.3Domaines d’application des réseaux ad hoc………………………….……………….. 18 4.4 Les caractéristiques des réseaux ad hoc ……….………………………………………18 Conclusion ……………………………………………………………………………………19

Chapitre II : Routage dans les réseaux mobiles ad hoc 1 Introduction …..……………………………………………………………………………21 2 Définitions…………..………………………………………………………………………21 3 Problématique du routage dans les réseaux mobile ad hoc ….………………………………22 4 Taxonomie des protocoles de routage dans les MANETs …...………………………………22 4.1 Selon l’architecture…………………………………………………………………… 23 4.1.4 Les protocoles de routage plat (ou uniformes) …….…………….……………...23 4.1.2 Les protocoles de routage hiérarchiques (ou non uniformes)…………………….24 4.2 Selon l’algorithme utilisé …..………….…………………………………………... . 25 4.3 Les catégories de protocoles de routage MANET…...…..…………………………… 25 4.3.1 les protocoles proactifs…………………………………………………………...25 4.3.2 Les protocoles réactifs…………………………………………………………... 26 4.3.3 Les protocoles hybrides …….……...…………………………………………….26

v

5 Description de quelques protocoles MANETs …………………………………………….. 26 5.1 OLSR…………………………………………………………………………………..27 5.2 TBRTF ………………………………………………………………………………...27 5.3 DSR……………………………………………………………………………………27 6 Etude détaillée du protocole AODV ………………………………………………………..28 6.1 Table de routage et paquets de contrôle …………..…………………………………….28 6.2 Numéro de séquence ……….………………………………………………………….30 6.3 Principe de fonctionnement ………...…………………………………………………..31 6.3.1 Découverte d'une route………………………………………………………….. 31 6.3.2 Maintenance des routes……..….………..………………………………………..32 6.3.3 Gestion de la connectivité locale….………….…………………………………....33 6.4 AODV : Avantages et inconvénients ………………….………………………………... 33 7 Autres protocoles…………………………………………………………………………....34 Conclusion………………………………………………………………………..…………34

Chapitre III : Qualité de service dans les réseaux mobiles ad hoc 1 Introduction……………………………………………………………………………….. 36 2 Définition de la Qualité de service………………………………………………………….36 3 Les métriques de la qualité de service …………………………………………………….. 36 3.1 La bande passante………………………………………………………………………37 3.2 Délai de bout en bout………………………………………………………………….. 37 3.3 La gigue : (variation du délai) ………….………………………………………………..37 3.4 La perte de paquets………….…………………………………………………………..37 4 Les besoins d’applications de la QoS………………………………………………………...38 5 Exemple de besoins de QoS : la voix sur IP (VoIP)…………………………………………38 5.1 Les paramètres de la voix sur IP………………………………………………………...38 5.1.1 Les différents échantillonnages……………………………………………………39 5.1.2 Le délai de bout en bout…..……………………………………………………….39 5.1.3 La gigue……………………………………………………………………………39 5.1.4 La perte de paquets……………...…………………………………………………40 6 La QoS dans Les réseaux mobiles ad hoc …...………………………………………………40 7 Solutions de QoS dans les MANETs ………………………………………………………. 41 7.1 Modèles de qualité de service ………………………………………………………...41 7.2 Solutions au niveau de la couche MAC ………………………………………………...42 7.2.1 Différenciation de services pour 802.11 …..……………………………………… 42 7.2.2 MACA/PR (Multihop Access Collision Avoidance with Piggyback Reservation)……………42 7.2.3 IEEE 802.11e………..…………………………………………………………… 42 7.3Protocoles de signalisation………………………………………………………………43 7.4 Routage avec QoS……...……………………………………………………………… 43 7.4.1 Objectifs du routage avec QoS…………………………………………………….44 7.4.2 Difficulté de routage avec QoS dans les MANETs ……………………………. 44 7.5 Protocole de routage avec QoS ……………………………………………………….44 Conclusion…………………………………………………………………………………...45

Chapitre IV : Conception 1 Introduction ………………………………………………………………………………...47 2 le routage AODV avec QoS………………………………………………………………...47 2.1 Estimation du délai dans les MANETs………..………………………………………...48 2.2 Estimation du délai à 1 saut radio……………………………………………………… 48 2.2.1 Détermination du délai dans la file d’attente…………………………………….48

vi

2.2.2 Détermination du délai de propagation………………………………………….50 2.3 Détermination du délai multi sauts…………………………………………………….52 3 Intégration dans AODV…………………………………………………………………….52 3.1 Extension de la RREQ …..……………………………………………………………..52 3.2 Extension des messages HELLO………………………………………………………..53 3.3 Mécanisme de routage AODV avec QoS……………………………………………….53 3.3.1Découverte des routes……………………………………………………………53 3.3.2 Maintenance des routes…………………………………………………………..54 3.4 Limitations …………………………………………………………………………….55 4 Diagramme de séquence…………………………………………………………………….57 5 Diagramme de classes……………………………………………………………………….57 Conclusion ……………………………………………………………………………………59

Chapitre V : Implémentation 1 Introduction ………………………………………………………………………………...61 2 Présentation d’AODV sous NS-2…………………………………………………………... 61 3 Présentation du protocole mac-802_11 sous NS-2 ………………………………………….62 4 Structure des nœuds AODV et AODV-D sous NS-2 ……………………………………..62 5 Implémentation d’AODV-D sous NS-2…………………………………………………...63 5.1 Estimation du délai au niveau de la couche MAC…………………………………… 64 5.1.1 Estimation de la bande passante libre sur un nœud…………………………... 64 5.1.2 Récupération du paramètre λ …………….…………………………………..66 5.1.3 Le délai dans la file d’attente R ………………………………………………67 5.1.4 Estimation du délai de propagation ;;;;…………………………………………67 5.1.5 Le délai à un saut … ;;……………………………………………………….69 6 Les modifications au niveau de la couche réseau…………………………………………….69 6.1Le format du paquet RREQ dans AODV-D ………………………………………… 69 6.2Le format du paquet RREP dans AODV-D…………………………………………...70 6.3 Contrôle d’admission ………………………………………………………………70 6.4 La probabilité de collision …….……………………………………………………...72 7 Les exigences de QoS……………………………………………………………………….73 Conclusion…………………………………………………………………………………….74

Chapitre VI : Simulation et discussion des résultats 1 Introduction………………………………………………………………………………...76 2 Intérêt et nécessité de la simulation………………………………………………………….76 3 Modèle de simulation………………………………………………………………………...76 3.1 Modèle de trafic…………………………………………………………………………77 4 Métriques de simulation mesurées…..………………………………………………………..78 5 Scénario de simulation……………….………………………………………………………78 6 Simulation et discussion ……………..………………………………………………………79 6.1 Délai de bout en bout…..……………………………………………………………….79 6.2 La variation de délai (la gigue) ………………………………………………………….80 6.3 La perte de paquets……………………………………………………………………..81 Conclusion…..…………………………………………………………………………………82 Conclusion générale et perspectives……………………………………………………………83 Bibliographie .…….…..…….…..………………………………….…………………………. 85 Annexes………………………………………………………………………………………..91

vii

Table des figures 1. 1 :Topologie totalement connectée 1 .2 : Topologie à station de base. 1.3: Topologie à routage interne. 1.4 Topologie hybride. 1.5: Classification des réseaux sans fil. 1.6 : Exemple de mode infrastructure. 1.7 : Exemple de mode ad Hoc. 1.8 : Le modèle de référence OSI. 1.9 : 802.11 et le modèle OSI. 1.10 : La couche PHYSIQUE dans le réseau sans fil. 1.11 : Étalement de Spectre à Séquence Directe DSSS. 1.12: Comparaison des technologies d’accès au canal radio. 1.13. Le problème du nœud caché et des nœuds exposés. 1.14 – Le mécanisme RTS/CTS. 1.15: La modélisation d'un réseau ad hoc. 2.1 : Modes de communication dans les réseaux. 2.2 : Taxonomie des protocoles de routage ad hoc. 2.3 : Routage plat. 2.4 : Routage hiérarchique. 2.5 : La propagation du paquet RREQ. 2.6 : Le chemin pris par RREP. 3.1 : Exemple de besoins de QoS. 3.2 : Solutions de QoS pour les réseaux ad hoc. 3.3 : Exemples de routage avec QoS. 4.1 : Modélisation d’un nœud 802.11 par une file M/M/1/K. 4.2 : Exemple de la bande passante libre sur deux nœuds d’un MANET. 4.3 : Découverte de routes dans AODV-D 4.4 : Chemin de RREP. 4.5 : L'organigramme d'exécution de AODV-D. 4.6 : L’organigramme d’exécution de RREQ pour AODV-D.

viii

4.7 : Diagramme de séquence d’AODV-D 4.8 : Diagramme de classes d’AODV-D 5.1 : Structure des nœuds AODV et AODV-D sous NS-2.

5.2 : Les méthodes appelées par AODV-D (découverte de route). 6.1 : Pile protocolaire mis en place 6.2 : Scenario de simulation utilisé. 6.3 :Délai de bout en bout du flux CBR1 avec AODV-D et AODV. 6.4 : Evolution de la gigue pour AODV. 6.5 : Evolution de la gigue pour AODV-D. A.1 : Une simple utilisation de NS2. A2 : Arborescence de dérivation des classes C++ du simulateur. A3 : Arborescence des fichiers de la distribution NS. A5 : exemple de fichier trace. A.5 : Fenêtre de visualisation de NAM. A.6 : Structure d’un nœud mobile sous NS-2.

ix

Liste des tableaux 1.1 Famille de IEEE 802 sans fil. 1.2 La famille d’IEEE 801.11. 2.1 Les principaux protocoles MANET. 2.2 Format du message RREQ. 2.3 Format du message RREP. 2.4 Format du message RERR. 3.1 : Les principaux codecs et leurs Vitesses d’échantillonnage. 3.2 : Les seuils du délai pour un codec G711. 3.3 :Les exigences de QoS pour la VoIP.

3.4 :Exemples de protocoles de routage avec QoS. 4.1 : Format du message RREQ dans AODV-D. 4.2 : Format du message HELLO dans AODV-D. 6.1. Paramètres de simulation utilisés.

6.2 : Paramètres de déroulement de la simulation. 6.3 : Taux de perte de paquets pour AODV-D et AODV standard. A1 : Les principaux composants de NS-2. A2 : Ltructure d’une ligne du fichier trace.

x

Introduction générale On assiste ces dernières années à une importante évolution dans le domaine des télécommunications, conduite par la commercialisation et l’émergence des appareils de communications sans fil (tels que les téléphones cellulaires, les ordinateurs portables, les assistants personnels, . . . etc.) et la convergence des réseaux fixes et mobiles. L’utilisateur passe ainsi de l’âge de l’ordinateur personnel à l’âge du traitement de l’information à travers plusieurs infrastructures. Il a accès à l’information n’importe où et n’importe quand. En 1999, l'IEEE (Institute of Electrical and Electronics Engineers) a standardisé le protocole d'accès au médium radio 802.11 visant à assurer la communication entre ordinateurs personnels utilisant le médium radio. Aujourd'hui, le protocole IEEE 802.11 est largement utilisé dans les réseaux locaux sans fil. On peut distinguer deux modes de communication dans un réseau sans fil. Dans le premier cas, toute transmission de données doit passer par un point fixe (nommé point d’accès) et ce même si deux mobiles communicants sont proches. Cette entité particulière joue le rôle de routeur à l’intérieur du réseau local sans fil et souvent de passerelle vers un réseau filaire. Chaque point d’accès administre alors une zone géographique et assure éventuellement la liaison avec d’autres zones, avec un réseau local filaire ou avec l’Internet. Les réseaux cellulaires (GSM, GPRS, UMTS) peuvent être considérés comme étant une forme particulière de réseau avec point d’accès. Dans le second mode de communication, chaque mobile du réseau a la possibilité de communiquer directement avec tous ses voisins, c’est-à-dire tous les nœuds capables de recevoir le signal envoyé et de le comprendre. Chaque mobile peut se connecter, se déplacer ou se déconnecter du réseau à tout moment. Il n’y a aucune infrastructure fixe à priori et les mobiles n’ont aucune connaissance de leur environnement. Si chaque mobile d’un tel réseau a la possibilité de router des paquets, il est alors possible de communiquer au delà de sa distance d’émission. On parle alors de réseaux mobiles ad hoc ou MANET (pour Mobile Ad hoc Network). Les avantages qu’offre un réseau ad hoc le rendent plus adéquat pour le déploiement des applications utilisées dans les situations critiques telles que la communication dans un champ de bataille, dans les opérations de secours et la gestion des catastrophes en général. Cependant, un tel réseau est subit à un nombre de contraintes qui rendent un tel déploiement très complexe On peut citer essentiellement : les contraintes de médium radio, le caractère fortement dynamique, et l’absence d’une administration centralisée. En effet, Chaque nœud du réseau doit participer dans le routage des paquets à travers le réseau, jouant ainsi le rôle d'un routeur et d’un terminal en même temps. Pour cela un protocole de routage distribué est nécessaire. Plusieurs protocoles de routage ont été proposés pour les réseaux mobiles ad hoc, ces protocoles de routage peuvent être classifiés suivant la manière de création et de maintenance de routes lors de l'acheminement selon plusieurs critères. Le groupe de travail MANET (Mobile ad hoc NETwork) de l'IETF (Internet Engineering Task Force) se préoccupe de la normalisation des protocoles ad hoc fonctionnant sous IP. Dans ce cadre, AODV, OLSR, DSR sont actuellement l’objet d’une RFC grâce à leurs caractéristiques intéressantes, ces protocoles fonctionnent en mode best effort. Cependant, ils ne permettent pas de garantir une qualité de service (QoS).

-1xi

Pour certaines applications telles que les applications multimédia ou temps réel le service best effort n’est pas du tout suffisant. De telles applications exigent des garanties en terme de certains critères de qualité de service (un minimum de bande passante, un délai max à ne pas dépasser.etc...). En effet, il semble important d’adapter les MANETs pour supporter un certain niveau de QoS dans le but de déploiement des applications exigeantes. Ce travail s'inscrit dans le cadre du projet adopté par le CERIST (Centre de Recherche sur l’Information Scientifique et Technique) intitulé « Le pervasive computing pour l’aide à la gestion de situations d’urgence et de catastrophes ». La finalité du travail effectué dans ce mémoire est de faire une extension du protocole AODV en le rendant sensible à une métrique de QoS, à savoir le délai de bout en bout. Ce mémoire est organisé en six chapitres : Le premier chapitre donne un état de l’art des réseaux sans fil et des différents concepts liés à ce type de réseaux, ainsi qu’une description de la norme IEEE 802.11. Enfin, il précise les notions de base des réseaux mobiles ad hoc et les principales caractéristiques des MANETs ainsi que les contraintes qui en découlent. Le deuxième chapitre traite les principes du routage dans les réseaux mobiles ad hoc. Il s’intéresse plus précisément à la problématique du routage et les contraintes liées aux MANETs. Il décrit également les principaux protocoles proposés et leurs classifications. Enfin il présente une étude détaillée du protocole AODV. Le troisième chapitre introduit le concept de qualité de service ainsi qu’un état de l’art sur les solutions existantes, plus particulièrement le routage avec QoS dans les MANETs. Le quatrième chapitre est consacré à la conception du protocole AODV-D qui est une extension d’AODV en termes du délai, il décrit également la méthode d'estimation du délai utilisée. Le cinquième chapitre donne des détails de l’implémentation de ce qui a été conçu dans le chapitre quatre. Le sixième chapitre est consacré aux simulations et discussions des résultats. Nous terminerons par une conclusion générale et quelques perspectives pour des travaux futurs.

-2xii

Chapitre I

Généralités sur les réseaux sans fil

Chapitre I

Généralités sur les réseaux sans fil

Généralités sur les réseaux sans fil 1 Introduction Les communications sans fil ont un rôle crucial à jouer au sein des réseaux informatiques. Elles offrent des solutions ouvertes pour fournir de la mobilité ainsi que des services essentiels là où l’installation d’une infrastructure n’est pas possible. Les réseaux sans fil (Wireless Networks) constituent de plus en plus une technologie émergente permettant à ses utilisateurs un accès à l’information et aux services électroniques indépendamment de leurs positions géographiques. Le succès de ce type de réseaux ces dernières années est suscité par un grand intérêt de la part des particuliers, des entreprises et du milieu industriel. En effet, ce type de réseaux est perçu comme une nouvelle alternative complémentaire aux réseaux filaires traditionnels [1]. Dans ce chapitre, nous allons parler de la technologie de communication sans fil utilisée dans les réseaux mobiles, pour cela nous détaillons quelques principales notions nécessaires à la compréhension de ces systèmes, ainsi qu’une présentation globale de la norme 802.11. Ensuite, nous allons voir les classifications principales des réseaux sans fil et les différentes technologies utilisées dans chaque catégorie, enfin le chapitre introduit le concept des réseaux mobiles ad hoc, la définition, les caractéristiques, et les domaines d’application.

2 Les réseaux sans fil 2.1 Historique Aux environs de 1940, la première ère de l'informatique moderne fit son apparition. Rapidement, l'adaptation des technologies de télécommunications à l'informatique fut incontournable. En 1957, le ministère de la défense américain crée l'agence pour les projets de recherche avancée : ARPA (Advanced Research Projects Agency). A la fin des années 60 les chercheurs de l'ARPA ont créé L'ARPANET, réseau destiné à relier entre elles les différentes universités du pays, qui grâce à la standardisation du modèle TCP/IP (Transmission Control Protocol/Internet) Protocol, évoluera vers l'Internet que nous connaissons actuellement. Jusqu’à la fin des années 1980, la technologie sans fil a surtout été utilisée dans le cadre de la radio, de la télévision ou des communications réservées à d’importants organismes comme l’armée. C’est l’arrivée des téléphones cellulaires GSM (Global System for Mobile communications) qui a offert à tous la possibilité de communiquer de n’importe où, avec n’importe qui. En 1997, alors que l’attention est accaparée par le succès d’Internet, un événement est passé inaperçu sauf pour quelques spécialistes et observateurs :l’adoption du standard IEEE 802.11 ou Ethernet sans fil. Exploitant la bande de fréquence de 2,4 GHz, le 802.11 plafonne à un débit de 2 Mbits/s au maximum. Ce précurseur est suivi de plusieurs déclinaisons dont le célèbre Wi-Fi (Wireless Fidelity) qui connaît un grand succès. Il désigne les différentes déclinaisons de la norme IEEE 802.11 qui permet à plusieurs ordinateurs de communiquer sans fil en utilisant comme support les ondes radio. Les câbles disparaissent enfin [5].

4

Chapitre I

2.4

Généralités sur les réseaux sans fil

Définition

Un réseau sans fil peut être considéré comme un système de transmission de données, dont le but est d’assurer une liaison indépendante de l’emplacement des entités informatiques qui composent le réseau [1]. Les réseaux sans fil sont basés sur une liaison utilisant des ondes radioélectriques (radio et infrarouges) en lieu et place des câbles habituels. Grâce aux réseaux sans fil, un utilisateur a la possibilité de rester connecté tout en se déplaçant dans une zone géographique plus ou moins étendue. Les deux termes ‘mobile’ et ‘sans fil’ sont souvent confondus, le terme sans fil désigne la nature des liens utilisés dans l’interconnexion des différents composants du réseau, alors que le terme ‘mobile’ désigne la possibilité de déplacement des utilisateurs du réseau suite à l’utilisation des liens sans fil. En effet, on peut dire que tous réseau mobile est un réseau sans fil, et le contraire n’est pas toujours vrais. Il existe plusieurs technologies se distinguant d’une part par la fréquence d’émission utilisée ainsi que le débit et la portée des transmissions. Les réseaux sans fil permettent de relier très facilement des équipements distants d’une dizaine de mètres à quelques kilomètres.

2.4

Caractéristiques

L’utilisation d’une interface sans fil introduit nombres de différences par rapport à la communication par câble. Tout d’abord, le spectre radio, et donc la capacité disponible pour le transfert de données sont limités par la réglementation. La bande de fréquence occupée par un réseau mobile ne peut être étendue. Cette restriction limite également le débit disponible imposant la nécessité d’une utilisation efficace du canal. Ensuite, la qualité des liens radio peut varier avec le temps au gré des diverses interférences et de la mobilité des usagers. Cette situation mène donc à un taux d’erreurs de transmission plus important que sur un réseau filaire et surtout à un taux très fluctuant. Une des différences majeures entre ces deux types de réseaux reste tout de même le caractère dynamique d’un réseau sans fil. Le point d’accès d’une entité sur un réseau filaire est fixe alors que dans le cas d’un réseau sans fil, l’usager peut se connecter depuis différents lieux et peut même changer de point d’accès au cours de sa connexion. Le problème est alors dans un premier temps de retrouver un utilisateur dans le réseau et donc un chemin permettant de l’atteindre. Dans un deuxième temps, il faut pouvoir maintenir sa connexion de façon transparente et ce, malgré sa mobilité et ses changements de zone de communication. Un autre aspect important est que l’accès physique aux données d’un réseau sans fil est non sécurisé. En effet, si dans le cas d’un réseau filaire on peut protéger les points d’accès et les câbles reliant les différents postes, dans le cas d’un réseau sans fil, n’importe qui peut écouter le réseau et donc récupérer les données transitant par l’interface air. Ceci va donc impliquer l’utilisation de mécanismes de chiffrement et d’authentification afin d’assurer la confidentialité des données [5].

2.4 Classification des réseaux sans fil Les réseaux sans fil peuvent être classés selon divers critères :la zone de couverture, la topologie et le mode de fonctionnement.

5

Chapitre I

Généralités sur les réseaux sans fil

2.4.1 Selon la zone de couverture Une classification classique concerne l’étendue géographique, Ils sont divisés en quatre classes.

a) Réseaux personnels sans fil (WPAN) Le réseau personnel sans fil noté (WPAN pour 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.

b) Réseaux locaux sans fil (WLAN) Le réseau local sans fil (WLAN pour 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.

c) Réseaux métropolitains sans fil (WMAN) Le réseau métropolitain sans fil (WMAN pour Wireless Metropolitan Area Network) est connu sous le nom de Boucle Locale Radio (BLR). Les WMAN sont basés sur la norme IEEE 802.16. La boucle locale radio offre un débit utile de 1 à 10 Mbit/s pour une portée de 4 à 10 kilomètres, ce qui destine principalement cette technologie aux opérateurs de télécommunication.

d) Réseaux étendus sans fil (WWAN) Le réseau étendu sans fil (WWAN pour Wireless Wide Area Network) est également connu sous le nom de réseau cellulaire mobile. Il s'agit des réseaux sans fil les plus répandus puisque tous les téléphones mobiles sont connectés à un réseau étendu sans fil. Les différentes technologies utilisées dans chaque catégorie et leurs caractéristiques sont regroupées dans le tableau 1.1[20]. Catégorie Standard Technologies

WPAN IEEE 802.15 Bluetooth HomeRF Zigbee IR(infrarouge) quelques dizaines de mètres

WLAN IEEE 802.11 Wifi HyperLAN2

WMAN IEEE 802.16 WiMax

WWAN IEEE 802.20 GSM GPRS UMTS

une centaine de mètres

quelques dizaines une centaine de kilomètres de kilomètres

<1 Mbps

2 à 54 Mbps

Jusqu'à 70 Mbps

Point à point Équipement à équipement

Réseau d'entreprise

Couverture Débit Applications

10 à 384 Kbps Fixe, accès au GSM dernier kilomètre PDA...

Tab 1.1 : La famille de l’IEEE 802 sans fil.

6

Chapitre I

Généralités sur les réseaux sans fil

2.4.2 Selon la topologie du réseau Une deuxième classification moins classique consiste à classifier les réseaux sans fil suivant la topologie et l’infrastructure utilisée. utilisée. Les topologies que l’on peut identifier sont les suivantes [9] :

• Topologie totalement connectée Tous les nœuds du réseau s'entendent et il n'y a donc nul besoin de protocole de Routage (Figure 1.1).

Lien sans fil Nœud

Fig. 1 .1 Topologie totalement connectée

• Topologie à station de base Ce modèle met en œuvre une station de base qui centralise les communications entre les nœuds du réseau. L'unique moyen de communication pour un nœud est de passer par la station de base (Figure : 1.2).

Fig. 1.2 1. : Topologie à station de base.

• Topologie à routage interne Dans cette architecture, les nœuds ne s'entendent pas tous. Le réseau se base sur un routage interne entre ses membres (Figure (Fig 1.3).

Fig. 1.3: 1. Topologie à routage interne.

7

Chapitre I

Généralités sur les réseaux sans fil

• Topologie combinée ou hybride Consiste à un mélange de type de réseaux, combinant une architecture filaire avec des réseaux sans fil (Figure : 1.4). Liens sans fil

Lien filaire

Fig. 1.4: Topologie hybride

2.4.3 Selon le mode de fonctionnement Les réseaux sans fil, peuvent être classés en deux classes : les réseaux avec infrastructure et les réseaux sans infrastructure. Le standard IEEE 802.11 définit les deux modes de fonctionnement (figure 1.5).

Les réseaux sans fil

Les réseaux avec infrastructure

Les réseaux sans infrastructure

Fig. 1.5: Classification des réseaux sans fil

a)Les réseaux avec infrastructure Dans ce cas, toute transmission de données doit passer par un point (nommé point d'accès) et ce même si deux mobiles communicants sont proches. Cette entité particulière joue le rôle de routeur à l’intérieur du réseau sans fil et souvent de passerelle vers un réseau filaire. Chaque point d'accès administre alors une zone géographique et assure la liaison avec d'autres zones, avec un réseau filaire ou avec internet (fig1.6). Les réseaux cellulaires (GSM, UMTS) peuvent être considérés comme étant une forme particulière de réseau avec point d'accès.

8

Chapitre I

Généralités sur les réseaux sans fil Point d’accès Réseaux statiques

Zone de couverture Unités mobiles Fig. 1.6 : Exemple de mode infrastructure.

b) Les réseaux sans infrastructure ou ad hoc Dans ce mode de communication, chaque mobile (appelé aussi nœud) du réseau a la possibilité de communiquer directement avec tous ses voisins, c'est à dire tous les nœuds capables de recevoir le signal envoyé et de le comprendre. Chaque nœud peut se connecter, con se déplacer ou se déconnecter du réseau a tout moment. Il n'y a aucune infrastructure. On parle alors des réseaux ad hoc ou MANET (Mobile ( Ad hoc NETwork).

Fig. 1.7 : Exemple de mode ad Hoc.

3 Présentation de la norme 802.11 3.1 Le model de référence OSI Proposé en 1984 par l’ISO (International Standards Organisation), le modèle OSI (Open ( System Interconnection)) est devenu une norme internationale servant de guide aux mises en réseau .Ce modèle de référence n’est pas une architecture de réseaux parce qu’il ne spécifie pas réellement les services et protocoles utilisés dans chaque couche ; il décrit simplement ce que chaque couche doit faire. Ainsi le modèle n’est rien de moins qu’une pile de couches exerçant chacune des fonctions bien définies : ces couches sont au nombre de 7 comme l’illustre la figure 1.8 [3].

9

Chapitre I

Généralités sur les réseaux sans fil

• La couche physique : s’occupe de la transmission des bits de façon brute sur un canal de communication .Sa conception doit être telle que l’on soit sûr que, lorsqu’un côté envoie un bit à 1, on reçoit de l’autre côté un bit à 1, et non un bit à 0. • La couche liaison de données : sa tâche est de prendre un moyen de transmission brut et de le transformer en une ligne qui parait exempte d’erreur de transmission à la couche réseau. • La couche réseau : permet de gérer le sous réseau de communication dont elle doit connaître la topologie .Cette gestion comprend : le contrôle de flux et le routage de paquets ainsi que leurs adressage. • La couche transport : sa fonction de base est d’accepter des données de la couche session de les découper en plus petite unités, de les passer à la couche réseau et de s’assurer que tous les morceaux arrivent correctement de l’autre côté . • La couche session : permet à des utilisateurs travaillant sur différentes machines d’établir des sessions entre eux (gestion du dialogue …etc.). • La couche présentation : à la différence des autres couches, celle-ci s’intéresse à la syntaxe et à la sémantique de l’information transmise.

• La couche application : joue le rôle d’interface pour l’accès des applications aux services du réseau. [3].

Fig.1.8 : le modèle de référence OSI. APDU : Application Protocol Data Unit. PPDU : Presentation Protocol Data Unit. SPDU : Session Protocol Data Unit. TPDU : Transport Protocol Data Unit.

10

Chapitre I

Généralités sur les réseaux sans fil

3.2 Les réseaux sans fil et le modèle OSI Le modèle OSI est conçu initialement pour répondre aux besoins des réseaux filaires, les réseaux sans fil ont des caractéristiques différentes des réseaux filaires (mobilité, qualité du signal…). Malgré ces particularités, le passage au monde sans fil a gardé le principe de conception en couche du modèle OSI .Comme tous les standards IEEE 802, le standard 802.11 se concentre sur les deux premiers niveaux, la couche physique et la couche liaison de données.

Fig. 1.9 :802.11 et le modèle OSI.

3.3 Le standard IEEE 802.11 Normalisé par l’IEEE en 1997, le protocole 802.11 est le standard le plus répandu dans le monde des réseaux sans fil. Grâce a sans succès commercial, il est devenu non seulement le dominant dans le mode infrastructure mais aussi dans les travaux et publications scientifique sur les réseaux ad hoc. Le standard 802.11 s'attache à définir les couches basses du modèle OSI pour une liaison sans fil utilisant des ondes électromagnétiques, c'est-à-dire : • La couche physique :(notée parfois couche PHY) • La couche liaison de données : constituée de deux sous-couches : le contrôle de la liaison logique (Logical Link Control, ou LLC) le contrôle d'accès au support (Media Access Control, ou MAC). La couche physique définit la modulation des ondes radioélectriques et les caractéristiques de la signalisation pour la transmission de données, tandis que la couche liaison de données définit l'interface entre le bus de la machine et la couche physique, notamment une méthode d'accès proche de celle utilisée dans le standard Ethernet et les règles de communication entre les différentes stations. La norme 802.11 propose en réalité trois couches physiques [5].

3.3.1 Couche physique Initialement, le standard IEEE 802.11 admet les trois spécifications différentes de la couche physique : FHSS (Frequency Hoping Spread Spectrum), DSSS (Direct Sequence Spread Spectrum) et IR (InfraRed), auxquelles 802.11a a rajouté la technique OFDM (Fig 1.10) [4].

11

Chapitre I

Généralités sur les réseaux sans fil

Couches supérieures 802.11 2 Mbps

802.11b 11 Mbps

802.11a/g 54Mbps

FHSS

DSSS

OFDM

Infra Rouge

PHY

Fig 1.10 : La couche PHYSIQUE dans le réseau sans fil.

• FHSS : (Étalement de Spectre avec Saut de Fréquences) FHSS (Frequency Hopping Spread Spectrum) est Utilisée dans les réseaux 802.11b et d’autres technologies sans fil, cette technologie utilise la technique de saut de fréquence. Son principe est de diviser la bande passante en 79 sous-canaux de 1 MHz de largeur de bande offrant chacun, un débit allant de 1 à 2 Mbps avec un codage binaire. L’émetteur et le récepteur s’accordent sur une séquence de sauts de fréquence porteuse et les données sont envoyées successivement sur les différents sous canaux en évitant (de manière temporaire) d’utiliser les sous canaux fortement perturbés. Chaque communication sur le réseau s’effectue suivant un schéma de saut différent et cela de façon à minimiser le risque que deux émissions utilisent le même sous canal [1].

• DSSS : (Étalement de Spectre à Séquence Directe) Le DSSS (Direct Sequence Read Spectre) est une couche physique utilisant une technique radio. C’est une technologie de transmission par spectre étalé, où la porteuse est successivement modulée par l’information et par un code pseudo aléatoire de débit beaucoup plus important. Le signal résultant occupe donc une bande très importante. Dans cette technique, la bande des 2.4 GHz est divisée en 14 sous-canaux de 22MHz (fig 1.11). Cette technique offre des débits de transmission allant de 5.5 à 11 Mbps. Avec comme avantages : – Une densité spectral faible du signal transmis, car ce dernier est large bande. – Une sécurité assurée, tant que le code d’étalement reste secret [1].

Fig. 1.11 : Étalement de Spectre à Séquence Directe DSSS

12

Chapitre I

Généralités sur les réseaux sans fil

• OFDM : (Multiplexage par Répartition Orthogonale de la Fréquence) La technologie OFDM (Orthogonal Frequency Division Multiplexing) représente une technique de modulation numérique des signaux, utilisée entre autres pour les systèmes de transmissions mobiles à haut débit de données. Elle consiste à répartir le signal sur un grand nombre de sous porteuses orthogonales modulées individuellement à bas débit. Ainsi, des normes telles que 802.11a et 802.11g peuvent offrir des débits théoriques jusqu’à 54 Mbps, là où la norme 802.11b qui n’est pas OFDM, se limite à 11 Mbps [1].

• Infrarouge En utilisant un faisceau de lumière, ce mode est basé sur l’utilisation des mêmes fréquences que celles utilisées sur les fibres optiques. Malgré que la lumière infrarouge possède une large bande passante offrant par conséquent des débits relativement importants, la portée de ce type de communications reste faible. En revanche, les infrarouges peuvent pénétrer à travers le verre, mais pas à travers des obstacles opaques, ce qui représente un avantage en terme de sécurité. Mais, comme les réseaux infrarouges sont sensibles aux interférences lumineuses, la coupure du faisceau lumineux implique l’interruption de la transmission.

3.3.2 La couche liaison de données La couche liaison de données a pour objectif de réaliser l’acheminement sans erreur de blocs d’informations sur la liaison physique c’est à dire sur le circuit de données reliant deux commutateurs adjacents. Afin d’effectuer une transmission correcte, la couche liaison de données attache des en-têtes et des caractères aux paquets de données à transmettre. Dans ce cas, les messages échangés sont appelés trames MAC ou MPDU (MAC Protocol Data Unit). Ceux ci seront encapsulés par la suite dans des trames de niveau physique appelées PLCPPDU (Physical Level Control Protocol-PDU).

3.3.2.1 La sous-couche LLC (Logical Link Control) La sous-couche LLC (spécification IEEE 802.2), qui est indépendante des mécanismes d’accès au support physique, représente une partie de la couche de liaison de données. Elle présente les caractéristiques de fiabilité grâce au séquencement et à la retransmission des données en cas de détection d’erreurs.

3.3.2.2 La sous-couche MAC (Medium Access Control) La sous-couche MAC, permet à un hôte de communiquer avec plusieurs périphériques en même temps. En effet, la sous-couche MAC est nécessaire pour gérer les accès au canal de communication, car l’un des problèmes majeurs des réseaux sans fil consiste à savoir qui a le droit d’émettre à un moment donné [1]. La norme IEEE 802.11 définit deux modes d’accès au médium au niveau MAC : • Le mode centralisé (Point Coordination Function, PCF) : peut être utilisé lorsque les communications sont gérées par une station de base fixe. • Le mode distribué (Distributed Coordination Function, DCF) : 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 est utilisé dans le cas des réseaux ad hoc [17]. Des protocoles ont été proposés afin de résoudre ces problèmes d’accès. Dans ce qui suit nous présentons un échantillon de ces techniques dans le cadre des réseaux sans fil [1]. 13

Chapitre I

Généralités sur les réseaux sans fil

• FDMA : (Accès Multiple par Répartition en Fréquence) L’idée est de diviser le spectre en canaux et d’affecter à chaque interlocuteur ou chaque message (un à la fois), un canal fréquentiel. Cette affectation est alors basée sur le principe du premier arrivé, premier servi ou FIFO (First In First Out). En pratique, le message utilisé sert à moduler une fréquence porteuse (à l’origine en amplitude, parfois avec suppression de porteuse) et les différentes porteuses ainsi modulées sont juxtaposées. Du côté du récepteur, des filtres sélectifs isolent les différentes porteuses démodulées et si les fréquences porteuses sont parfaitement connues ou restituées, une démodulation cohérente (synchrone) est effectuée [1].

• TDMA (Accès Multiple par Répartition dans le Temps) Dans cette technique, les canaux sont multiplexés sous la forme d’intervalles de temps de telle façon que chaque correspondant ou chaque message occupe la totalité de la bande mais pendant un temps très court (accès à toute la bande passante allouée pour le système de transmission). Avec le TDMA, les échantillons issus d’un message sont intercalés avec ceux des autres. Ainsi, le tri de ses échantillons se fait du côté du récepteur. Le fait que le TDMA présente une gestion complexe, il faut ajouter des bits de signalisation et de synchronisation, mais cette technique offre un coût réduit pour la station de base, ainsi qu’une souplesse de modification sur les débits transmis [1].

• CDMA (Accès Multiple par Répartition en Code) Ici, tous les utilisateurs accèdent simultanément à la totalité de la bande, ils sont distingués à la réception grâce à des codes pseudo-aléatoires personnels. Ce qui permet d’avoir une bonne immunité au bruit et la possibilité d’utiliser la diversité de fréquences, ainsi que le cryptage. La technique CDMA utilise des modulations à étalement de spectre qui peuvent être réalisées par saut de fréquence ou par séquence directe. En effet, le CDMA est très souple au niveau des débits transmis, mais relativement complexe car elle peut nécessiter une égalisation à la réception et un contrôle de la puissance d’émission [1]. La figure 1.12 montre une comparaison entre les différentes techniques d’accès au canal radio décrites précédemment :

Fig. 1.12: Comparaison des technologies d’accès au canal radio.

14

Chapitre I •

Généralités sur les réseaux sans fil

CSMA/CA (Accès Accès Multiple avec Écoute de Porteuses/Évitement de Collisions) Collisions

Le CSMA/CA est une technique d’accès au médium utilisée dans les réseaux sans fil IEEE 802.11. Elle permet de traiter les problèmes des stations cachées et des stations exposées expos illustrés par la figure 1.13,, et d’éviter les collisions en utilisant le principe appelé évitement de collisions (Collision Avoidance).

A

B

C

A

B

C

D

Fig.1.13. Le problème du nœud caché et des nœuds exposés.

Dans cette technique, chaque nœud (souhaitant émettre des données) doit écouter le canal avant de tenter d’obtenir l’accès. Si le canal est occupé le nœud doit attendre la fin de la transmission en cours pour avoir le droit d’accès au médium. Lorsque le le canal devient libre, avant toutes choses, il faut qu’il le reste pour une période DIFS (DCF Inter-Frame Inter Space), si le canal reste libre durant le DIFS alors les nœuds qui veulent émettre choisissent un temps de temporisation appelé backoff [1] ; Le backoff est choisit au hasard dans un intervalle appelé Contention Window (CW)qui est par défaut [0 ;31] ; avec un time slot de 20 µs, le backoff va donc être compris entre 0 et 620 µs. et la taille de la fenêtre va doubler afin de diminuer les chances que de telles collisions se rép pètent. La borne inférieure de la Contention Window est toujours zéro, et la borne supérieure rieure (dont les valeurs autorisées autoris es par la norme ne sont que des puissances de 2 moins 1) va évoluer oluer entre les valeurs CWmin et CWmax définies par la norme [15]. Lorsque la temporisation expire, si le canal est inoccupé, ils peuvent commencer l’envoi de ses paquets. Dans le cas de plusieurs nœuds qui veulent accéder au canal, celui qui a choisi la temporisation la plus courte est donc celui qui gagne le droit d’accès et les autres doivent attendre simplement la fin de la transmission pour avoir le droit de tenter à nouveau l’accès au médium [1].. Le mécanisme de backoff limite les risques de collision mais ne les supprime pas complètement .due à cette insuffisance le 802.11 802.11 propose l’utilisation du mécanisme RTS/CTS (figure.1.14) [4].

Fig. 1.14 1 – Le mécanisme RTS/CTS.

15

Chapitre I

Généralités sur les réseaux sans fil

Un nœud vérifie si le médium est libre. Si le médium est occupé, l’émetteur attend qu’il se libère, puis attend un temps aléatoire avant d’émettre. Si personne n’est en train d’émettre, le nœud envoie un message de type RTS (Request To Send) contenant l’adresse de destination et la durée de la transmission pour demander la parole. Les autres nœuds savent donc que le médium sera occupé pendant cette durée. Le destinataire répond avec un message de type CTS (Clear To Send) qui indique qu’il est prêt à recevoir les données sans aucun risque de collision. Chaque paquet doit être acquitté et si aucun acquittement n’est reçu, le paquet est retransmis. Il faut noter que le temps qui sépare un paquet de données de son acquittement est appelé SIFS (Short Inter frame Space). Une autre fonction importante appelée écoute de la porteuse virtuelle fournie par le vecteur NAV (Network Allocation Vector). Le NAV représente une minuterie indiquant la durée pendant laquelle le médium sera réservé. Chaque nœud fixe le NAV à sa durée d’utilisation du médium, en incluant les trames nécessaires à la terminaison de l’opération en cours [1].

3.4 Les différentes dérivées de la norme 802.11 La norme IEEE 802.11 est la norme initiale offrant des débits de 1 ou 2 Mbps .Des révisions ont été apportées à la norme originale afin d'optimiser le débit (c'est le cas des normes 802.11a, 802.11b et 802.11g, appelées normes 802.11 physiques) ou bien préciser des éléments afin d'assurer une meilleure sécurité ou une meilleure interopérabilité. D’autres normes sont orientées vers l’amélioration de la qualité de service (QoS) tel que 802.11 e. Le tableau (tab 1.2) représente les principales dérivées de la norme 802.11 et leurs caractéristiques :

Norme 802.11

802.11a

802.11b 802.11e 802.11f 802.11g 802.11h 802.11i

caractéristiques -Date de normalisation : 1997 -Bande de fréquence : 2.4 GHz -Débit : théorique: 2 Mbps, réel:<1 Mbps -Portée théorique : 100 m -Date de normalisation : 1999 -Bande de fréquence : 5 GHz -Débit : théorique: 54 Mbps, réel:30 Mbps -Portée théorique : 50 m -Spécificité: 8 canaux radio -Date de normalisation : 1999 -Bande de fréquence : 2.4 GHz -Débit : théorique: 11 Mbps, réel:6 Mbps -Portée théorique : 100 m -Spécificité: 3 canaux radio Amélioration de la qualité de service (niveau MAC) pour le support audio et vidéo. Interopérabilité entre les points d'accès -Date de normalisation : 2003 -Bande de fréquence : 2.4 GHz -Débit : théorique: 54 Mbps, réel:30 Mbps -Spécificité: compatibilité 802.11b Adaptation de 802.11a aux normes d'émissions électromagnétiques Européennes. Amélioration de la sécurité des transmissions sur les bandes de fréquences 2.4 GHz et 5 GHz. 16

Chapitre I 802.11n 802.11k 802 .11r

Généralités sur les réseaux sans fil -Date de normalisation : 2006 -Débit : théorique: 500 Mbps -Implémente la technologie MIMO (Multiple Input Multiple Output) Apporte des améliorations dans le domaine de la mesure des ressources radio, but : d’arriver à une meilleure gestion et la maintenance des WLAN. -Date de normalisation : 2008 -Amélioration des performances de la VoIP (Voice over IP) Tab 1.2 –la famille de IEEE 801.11.

4 Les réseaux mobiles ad hoc L'évolution récente de la technologie dans le domaine de la communication sans fil et l'apparition des unités de calculs portables (les laptops par exemple), 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 ces notions de la mobilité à toutes les composantes de l'environnement. Ici, contrairement aux réseaux basés sur la communication cellulaire, aucune administration centralisée n'est disponible, ce sont les hôtes mobiles elles-mêmes qui forment, d'une manière ad hoc, 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, voire des centaines de milliers. Les réseaux ad hoc sont idéals pour les applications caractérisées par une absence (ou la non fiabilité) d'une infrastructure préexistante, telles que les applications militaires et les autres applications de tactique comme les opérations de secours (incendies, tremblement de terre..) et les missions d'exploration.

4.1 Définition Dans le RFC 2501[10] de IETF (Internet Engineering Task Force), qui représente l’organisme responsable de l’élaboration de standards pour Internet, définit les réseaux mobiles ad hoc (appelés généralement MANETs pour Mobiles Adchoc NETwork) de la manière suivante : " Un réseau ad hoc est un système autonome de plates-formes mobiles (par exemple un routeur interconnectant différents hôtes et équipements sans fil) appelées nœuds qui sont libres de se déplacer aléatoirement et sans contrainte. Ceci provoque des changements rapides et prédictibles de la topologie du réseau. Ce système peut fonctionner d’une manière isolée ou s’interfacer à des réseaux fixes au travers de passerelles. Dans ce dernier cas, un réseau ad hoc est un réseau d’extrémité".

4.2 Modélisation Un réseau mobile ad hoc peut être modélisé par un graphe Gt = (Vt , Et ) où : Vt : représente l'ensemble des nœuds (i.e. les unités ou les hôtes mobiles) du réseau. Et : modélise l'ensemble des connections qui existent entre ces nœuds. (Figure 1.15). Si e = (u, v) ∈ Et , cela veut dire que les nœuds u et v sont en mesure de communiquer directement à l'instant t [6].

17

Chapitre I

Généralités sur les réseaux sans fil

Fig. 1.151.1 La modélisation d'un réseau ad hoc.

4.3 Domaines d’application des réseaux ad hoc Les premières applications des réseaux ad hoc concernaient les communications et les opérations dans le domaine militaire. Cependant, avec l’avancement des recherches dans le domaine des réseaux et l’émergence des technologies technologies sans fil (ex : Bluetooth, IEEE 802.11 et Hiperlan) ; d’autres applications civiles sont apparues. On distingue [7] : • Les services d’urgence : opération de recherche et de secours des personnes, tremblement de terre, feux, inondation, dans le but de remplacer l’infrastructure filaire. • Le travail collaboratif et les communications dans des entreprises ou bâtiments : dans le cadre d’une réunion ou d’une conférence par exemple. • Home network : partage d’applications et communications des équipements mobiles. m • Applications commerciales : pour un paiement électronique distant (taxi) ou pour l’accès mobile à l’Internet, où service de guide en fonction de la position de l’utilisateur. • Réseaux de senseurs : pour des applications environnementales (climat, activité ac de la terre, suivi des mouvements des animaux, . . . etc.) ou domestiques (contrôle des équipements à distance). • Réseaux en mouvement : informatique embarquée et véhicules communicants. D'une façon générale, les réseaux ad hoc sont utilisés dans dans toute application où le déploiement d'une infrastructure 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.

4.4 Les caractéristiques ctéristiques des réseaux ad hoc Les MANET ont plusieurs caractéristiques particulières [10] : • Une topologie dynamique : les nœuds sont libre de se déplacer arbitrairement, ce qui fait que la topologie du réseau peut changer aléatoirement et rapidement n’importe quel moment,, et peut être constituée à la fois de liaisons unidirectionnelles ou bidirectionnelles. • Liaisons à débit variable et à bande passante limitée : les liaisons sans fil auront toujours une capacité inférieure à leurs homologues filaires. En plus, le débit d réel des communications sans fil après avoir déduit les effets des accès multiples, du bruit et des interférences, etc., est souvent inférieur au débit de transfert maximum de la liaison radio. • Utilisation limitée de l'énergie : Une partie des nœuds d'un MANET voire l'ensemble des nœuds, peut reposer sur des batteries ou un autre moyen limité pour leur énergie .Pour Pour ces nœuds, le plus important est sans doute de mettre en place pl des critères d'optimisation tion pour la conversation de l’énergie.

18

Chapitre I

Généralités sur les réseaux sans fil

• Sécurité physique limitée : Les réseaux sans fil sont généralement plus sensibles aux menaces physiques que les réseaux câblés. Les techniques existantes pour la sécurité des liaisons sont souvent appliquées au sein des réseaux sans fil pour réduire les risques d'attaques. Notons cependant un avantage dans le fait que le contrôle des réseaux MANET soit décentralisé ajoute à sa robustesse, contrairement aux problèmes pouvant survenir sur les points centraux dans les approches plus centralisées [10]. • L'absence d'infrastructure : 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 [8].

Conclusion L’évolution rapide de la technologie de télécommunication sans fil, a permet la manipulation de l’information à travers des unités de calculs portables. Ces unités ont des caractéristiques particulières et accèdent au réseau à travers une interface de communication sans fil. La mobilité et le nouveau mode de communication utilisé, engendrent de nouvelles caractéristiques propres à l’environnement mobile. Ces caractéristiques nous obligent à changer la vision classique aux problèmes liés aux différentes stratégies de routage proposées pour les réseaux filaires, ces stratégies deviennent plus en plus complexes quand il s’agit d’un réseau ad hoc. Les systèmes de communication cellulaire sont basés essentiellement sur l'utilisation des réseaux filaires (tel que Internet) et la présence des stations de base qui couvrent les différentes unités mobiles du système. Les réseaux mobiles "ad hoc" sont à l'inverse, des réseaux qui s'organisent automatiquement de façon à être déplorable rapidement, sans infrastructure fixe, et qui doivent pouvoir s'adapter aux conditions de propagation, aux trafics et aux différents mouvements pouvant intervenir au sein des nœuds mobiles. Dans ce chapitre, nous avons présenté plusieurs concepts de bases liés aux réseaux sans fil, notamment la norme IEEE 802.11 et les concepts des réseaux ad hoc. Dans le prochain chapitre nous allons étudier le concept de routage dans les réseaux mobiles ad hoc, et une description de quelques protocoles de routage MANET particulièrement le protocole AODV.

19

Chapitre II

Routage dans les réseaux mobiles ad hoc

Chapitre II

Routage dans les réseaux mobiles ad hoc

Routage dans les réseaux mobiles ad hoc 1 Introduction À l’inverse d’un réseau de télécommunication classique, L’architecture d’un réseau mobile ad hoc étant caractérisée par une absence d’infrastructure fixe préexistante, il doit s’organiser automatiquement de façon à être déployable rapidement et pouvoir s’adapter aux conditions de propagation, au trafic et aux différents mouvements des unités mobiles. Le principe du routage dans les réseaux avec infrastructure repose sur le fait que la source transmet un datagramme à une destination en l’envoyant préalablement au routeur le plus proche. Le paquet transite dans le réseau de routeur en routeur jusqu'à ce qu’il soit routé directement sur le destinataire. Or dans les réseaux mobiles ad hoc, ce système ne peut être appliqué. La notion de routeur n’existe pas et ce sont les terminaux eux même qui doivent prendre en charge le routage des paquets. Chaque nœud est susceptible d'être mis à contribution pour participer au routage et retransmettre les paquets ; tout nœud joue ainsi le rôle de station et de routeur [17]. MANET (Mobile ad hoc NETwork) [10] est un groupe de travail au sein de l’IETF (Internet Engineering Task Force) qui a émergé du groupe de travail « mobile IP». Le groupe MANET se concentre sur les protocoles de routage dans les réseaux mobiles ad hoc et se propose de standardiser des protocoles de routage au niveau IP. Les protocoles de routage doivent être totalement distribués, c'est à dire qu'aucune entité centrale ne doit tout commander, en plus, les protocoles doivent réagir aux changements imprévisibles et rapides de la topologie du réseau. Ce chapitre est consacré au routage dans les réseaux mobiles ad hoc, pour cela il introduit les différents concepts liés au routage dans les réseaux mobiles ad hoc ; les contraintes, une taxonomie des protocoles existants ; ainsi qu’une étude de quelques protocoles existants et une étude détaillée du protocole AODV qui est au centre des travaux de ce mémoire.

2 Définitions Le terme routage désigne l’ensemble des mécanismes mis en œuvre dans un réseau pour déterminer les routes qui vont acheminer les paquets d’un terminal émetteur à un terminal récepteur [43]. On distingue généralement deux entités : L’algorithme de routage est la partie du logiciel de la couche réseau qui a la responsabilité de décider sur quelle ligne de sortie un paquet entrant doit être retransmis [3].Le but d'un algorithme de routage est de permettre le calcul de route entre une source et une destination au sens d'un certain critère (plus court chemin par exemple), et la diffusion des informations nécessaires à ce calcul. Un protocole de routage est un ensemble de règles s’appliquant au format et à la signification des trames, paquets ou messages échangés entre entités paires au sein de la couche réseau [3].

21

Chapitre II

Routage dans les réseaux mobiles ad hoc

3 Problématique du routage dans les réseaux mobile ad hoc Les contraintes des réseaux mobiles ad hoc rendent l’application des protocoles de routage traditionnellement déployés dans les réseaux filaires inefficace, les principaux problèmes qui se posent sont : • La capacité limitée des liens (liens radio) : un protocole de routage ad hoc doit être efficace en bande passante utilisée. Il doit minimiser le trafic de contrôle (overhead) nécessaire à l’établissement et à la maintenance des routes afin de réduire la charge sur le réseau. • La nature variable des liens (unidirectionnelle ou bidirectionnelle) doit être prise en compte par le protocole de routage. • Les ressources matérielles restreintes des unités mobiles excluent les algorithmes exigeants en capacité de mémoire et de traitement. • Changements fréquents dans la topologie : l’algorithme d’obtention d’une route doit prendre en compte la mobilité des nœuds et rechercher la route la plus courte en nombre de sauts. En effet, le déplacement des unités mobiles peut remettre en cause la validité des informations de routage. • L’absence d’infrastructure ou d’administration fixes dans le réseau impose par ailleurs un fonctionnement distribué [2]. En effet l'étude et la mise en œuvre d'algorithmes de routage pour assurer la connexion des réseaux mobiles ad hoc au sens classique du terme (tout sommet peut atteindre tout autre), est un problème complexe. Il semble donc important que toute conception de protocole de routage doive étudier les problèmes suivants : • La 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 nœud s ou liens. • Offrir un support pour pouvoir effectuer des communications multipoints 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. • 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, délais de bout en bout,…etc.). Si la construction des chemins optimaux est un problème complexe, 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. • 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 [8].

4 Taxonomie des protocoles de routage dans les MANETs Les protocoles de routage dédiés aux réseaux ad hoc peuvent être caractérisés par leur catégorie (protocoles proactifs, réactifs ou hybrides), leur architecture (plate ou hiérarchique) ainsi que par leur type d’algorithmes (voir fig. 2.2) [2]. Avant de décrire les différentes classifications, il est bon de rappeler quels sont les principaux modes de communication dans les réseaux mobiles : la communication point à 22

Chapitre II

Routage dans les réseaux mobiles ad hoc

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 et la diffusion ou broadcast qui envoie un message à tous les nœuds du réseau. Ces trois modes de communication sont schématisés par la figure 2.1 [14].

Fig. 2.1 : Modes de communication dans les réseaux.

La figure 2.2 illustre une taxonomie des protocoles de routage pour les réseaux mobiles ad hoc : Routage Multipoint

Routage point à point

Hiérarchique

Sélection de voisins *OLSR ZRP

Diffusion

Plat

Partitionnement

Orientés topologie

GCSR CBRP HSR

Proactif GSR FSR *TBRPF

Réactif *DSR

Orientés Destination s

Proactif DSDV WRP

Réactif *AODV TORA DYMO

* protocoles RFC au niveau de l’IETF

Fig. 2.2 : Taxonomie des protocoles de routage ad hoc [16].

4.1

Selon l’architecture

La première classification des protocoles de routage ad hoc concerne le type de vision qu’ils ont du réseau et les rôles qu’ils accordent aux différentes unités mobiles.

4.1.1 Les protocoles de routage plat (ou uniformes) Ces protocoles considèrent que tous les nœuds sont égaux (fig.2.3). La décision d’un nœud de router des paquets pour un autre dépendra de sa position et pourra être remise en cause au cours du temps [15]. 23

Chapitre II

Routage dans les réseaux mobiles ad hoc

Fig.2.3 : Routage plat.

Les protocoles de routage uniformes peuvent être également regroupés selon les données qu'ils utilisent pour effectuer leur tâche [16] :

• Les protocoles orientés topologie Dans les protocoles orientés topologie, chaque nœud utilise comme données l'état de ses connexions avec ses nœud s voisins, cette information est ensuite transmise aux autres nœuds pour leur donner une connaissance plus précise de la topologie du réseau.

• Les protocoles orientés destinations Ces protocoles maintiennent pour chaque nœud destination une information sur le nombre de nœuds qui les en séparent (la distance) et éventuellement sur la première direction à emprunter pour y arriver (le vecteur).

4.1.2 Les protocoles de routage hiérarchiques (ou non uniformes) Les protocoles hiérarchiques fonctionnent en confiant aux mobiles des rôles qui varient de l’un à l’autre. Certains nœud s 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 nœud s qui sont reliés à lui. Un exemple est donné sur la figure 2.4, où le nœud N3 passe par les passerelles P1, P2 et P3 pour atteindre N7 [15].

Fig.2.4 : Routage hiérarchique.

On distingue deux modes de fonctionnement dans les protocoles hiérarchiques [16] :

24

Chapitre II

Routage dans les réseaux mobiles ad hoc

• Les protocoles à sélection de voisins

Dans les protocoles à sélection de voisins, chaque nœud sous-traite la fonction de routage à un sous-ensemble de ses voisins directs. • Les protocoles à partitionnement :

Pour les protocoles à partitionnement, le réseau est découpé en zones dans lesquelles le routage est assuré par un unique nœud maître (appelé aussi cluster-head).

4.2 Selon l’algorithme utilisé Une autre classification, héritée du monde filaire, est possible pour les protocoles de routage ad hoc: deux algorithmes de routage sont utilisés, les algorithmes à état de lien (Linkstate) et les algorithmes à vecteur de distance (distance Vector) [15].

• Les protocoles à état de lien (Link-state protocols) Les protocoles à état de liens cherchent à maintenir dans chaque nœud une carte plus ou moins complète du réseau où figurent les nœuds et les liens les reliant. A partir de cette carte il est possible de construire les tables de routage. Un des avantages de ce type de protocole est leur capacité à pouvoir facilement trouver des routes alternatives lorsqu’un lien est rompu. Il est même possible d’utiliser simultanément plusieurs routes vers une même destination, augmentant ainsi la répartition de la charge et la tolérance aux pannes dans le réseau. En contrepartie, si le réseau est étendu, la quantité d’informations à stocker et à diffuser peut devenir considérable.

• Les protocoles à vecteur de distance (distance Vector protocols) Ces protocoles ne conservent que la liste des nœuds du réseau et l’identité du voisin par lequel passer pour atteindre la destination par le chemin le plus court. A chaque destination possible sont donc associés un next-hop et une distance. Si un voisin envoie un paquet de contrôle dans lequel il indique être plus près d’une destination que le next-hop que l’on utilisait jusqu’alors, alors il le remplace dans la table de routage. Un des inconvénients de cette technique est la difficulté de conserver plusieurs routes alternatives au cas où celle qui est privilégiée serait rompue (on ne dispose que du next-hop, et on ne sait pas si la suite de la nouvelle route est indépendante de celle qui a été rompue).

4.3 Les catégories de protocoles de routage MANET Les protocoles développés pour les réseaux mobiles ad hoc peuvent être classifiés en trois grandes familles en tant que réactifs, proactifs ou hybrides [1].

4.3.1 les protocoles proactifs Dans le routage proactif, chaque nœud maintient une ou plusieurs tables contenant l’information de routage vers chaque autre nœud du réseau. Tous les nœuds mettent leurs tables à jour de façon à maintenir une vue consistante et réelle du réseau. Lorsque la topologie du réseau change, les nœuds propagent des messages de mise à jour à travers le réseau afin de garder cette consistance et de garder à jour l’information de routage pour l’ensemble du réseau. Ces protocoles diffèrent sur la manière par laquelle des changements 25

Chapitre II

Routage dans les réseaux mobiles ad hoc

de topologies sont distribués à travers le réseau et sur le nombre de tables nécessaires au routage. Il existe plusieurs protocoles connus de cette catégorie, à titre d’exemples, nous pouvons citer DSDV, GSR, FSR, HSR et ZHLS.

4.3.2 Les protocoles réactifs Dans cette deuxième catégorie de protocoles de routage dite routage à la demande, les routes ne sont pas maintenues vers tous les nœuds mais elles sont créées selon les besoins. Lorsqu’il y a un besoin de routage, un mécanisme de découverte de route est lancé dans le but d’obtenir une information spécifiée, inconnu au préalable et qui va rester valide tant que la destination est joignable ou jusqu’au moment où la route devienne inutile. Ici, la majorité des algorithmes utilisés sont basés sur le mécanisme d’apprentissage en arrière. Ce type de routage est lent à cause de la recherche des chemins, ce qui peut dégrader les performances des applications interactives. De plus, il est impossible de connaître la qualité au préalable d’un chemin (bande passante, délai, ..), tandis qu’une telle connaissance est importante pour les applications multimédia. A titre d’exemples, les protocoles appartenant à cette catégorie sont DSR, AODV et TORA.

4.3.3 Les protocoles hybrides Une troisième catégorie appelée les protocoles hybrides permet de combiner les deux concepts ; celui des protocoles proactifs et celui des protocoles réactifs. Généralement le réseau est divisé en deux zones et le principe est d’utiliser une approche proactive pour avoir des informations sur les voisins les plus proches, qui se trouvent au maximum à deux sauts du nœud mobile. Une approche réactive est utilisée au-delà de cette zone prédéfinie afin de chercher des routes. L’avantage de cette troisième catégorie de protocoles est le fait qu’elle s’adapte bien aux réseaux de grandes tailles. Cependant, cette approche a comme inconvénient de cumuler les points faibles des protocoles réactifs et ceux des protocoles proactifs, tels que les messages de contrôle périodique et le coût d’établissement d’une nouvelle route. Il existe plusieurs protocoles connus appartenant à cette catégorie de protocoles hybride, citons ZRP (Zone Routing Protocol) et CBRP (Cluster Based Routing Protocol).

5 Description de quelques protocoles MANETs De nombreux protocoles de routage ont été proposés pour les réseaux mobiles ad hoc. Les protocoles décrits dans ce qui suit sont issus du groupe de travail MANET de l’IETF. Ces protocoles sont représentatifs de diverses techniques et sont les plus avancés sur la voie d’une normalisation [15]. Ils font désormais l’objet d’une Request For Comment (RFC) au niveau de l’IETF. Les protocoles concernés (table 2.1) sont : OLSR (RFC 3626, octobre 2003) [18] et TBRPF (RFC 3684, février 2004) [12], ainsi que les protocoles réactifs : DSR (RFC 4728, février 2007)[13] et AODV (RFC 3561, juillet 2003) [11] ,ce dernier sera étudié en détails. Nom Catégorie Architecture Algorithme

DSR

AODV Réactifs plat plat Routage Vecteur source de distance

OLSR TBRPF Proactifs hiérarchique hiérarchique Etat de Etat de liens liens

Table 2.1 : les principaux protocoles MANET 26

Chapitre II

Routage dans les réseaux mobiles ad hoc

5.1 OLSR OLSR (Optimized Link State Routing) [18] est un protocole proactif à état de liens. Afin de maintenir à jour les tables de routage, chaque nœud implémentant OLSR diffuse régulièrement des informations sur son propre voisinage. Ces informations sont suffisantes pour permettre à chaque nœud de reconstruire une image du réseau et de trouver une route vers n’importe quelle destination. Cette diffusion ne se fait pas par une simple inondation (où chaque nœud retransmet simplement chaque nouveau paquet qu’il reçoit) ; OLSR optimise la diffusion grâce au système des relais multi-points (MPR : Multi-Points Relays). Chaque nœud choisit dans ses voisins directs un sous-ensemble minimal de nœuds qui lui permettent d’atteindre tous ses voisins à deux sauts. La diffusion des informations sur les liens utilisés pour le routage se fait ensuite uniquement par les relais multi-points ; la couverture totale du réseau est assurée tout en limitant sensiblement le nombre de réémissions. Afin de choisir ses relais multipoints, un nœud a besoin de connaître complètement la topologie de son voisinage à deux sauts ; cela est réalisé grâce à l’envoi périodique de paquets hello contenant la liste des voisins connus à un saut [15].

5.2 TBRPF TBRPF (Topologie Dissémination Based on Reverse-Path Forwarding) [12] est un protocole de routage proactif à état de liens. Chaque nœud maintient en permanence un arbre dont il est la racine et qui fournit les chemins les plus courts pour tous les autres nœud s .TBRPF est constitué de deux parties complémentaires : la découverte des voisins et le routage proprement dit. La découverte des voisins est assurée par un mécanisme de paquets hello diffusés régulièrement au voisinage direct. Ces paquets hello contiennent la liste des voisins du nœud, et permettent ainsi de connaître rapidement la topologie complète du réseau à deux sauts. Il faut noter que TBRPF emploie une technique de hello différentiels où seuls les changements de topologie sont notifiés (diminuant ainsi la taille moyenne des paquets et autorisant leur envoi à une plus grande fréquence). La partie routage quant à elle est basée sur un échange des arbres de routage entre nœuds voisins, conduisant progressivement à la diffusion de l’information dans l’ensemble du réseau. Là encore seules des parties d’arbres sont échangées. Normalement, un nœud ne diffuse qu’un sous-arbre à deux niveaux dont il est la racine. Au premier niveau apparaissent les liens vers tous les voisins directs du nœud, et au deuxième niveau un unique lien vers chaque voisin à deux sauts (on peut noter ici une certaine similitude avec le mécanisme des relais multi-points d’OLSR). En conjonction avec ce système de base, TBRPF peut également ajouter des informations sur d’autres liens à l’arbre diffusé, avant de réagir plus vite en cas de changement de la topologie. A noter enfin que dans un souci d’économie de bande passante, les sous-arbres et les paquets hello sont regroupés autant que possible dans un même paquet (on parle d’agrégation ou piggybacking puisque l’on profite des paquets hello pour envoyer en même temps les sous- arbres) [15].

5.3 DSR DSR (Dynamic Source Routing) [13] est un autre protocole réactif. Il se différencie des autres en particulier parce qu’il pratique le source routing : l’émetteur précise dans l’en-tête de chaque paquet la liste des nœuds qu’il devra traverser pour atteindre sa destination. Ce type de routage présente certains avantages particulièrement intéressants ; il autorise en particulier la source à conserver dans sa table de routage plusieurs chemins valides vers une même 27

Chapitre II

Routage dans les réseaux mobiles ad hoc

destination. Le choix du chemin emprunté pourra donc être fait indépendamment pour chaque paquet, et permettre un meilleur équilibrage de la charge du réseau ou une meilleure réactivité aux changements de topologie. Dans la pratique, DSR est structuré en deux sousparties complémentaires : la recherche de route et la maintenance de route. La recherche de route se fait par inondation : un paquet de recherche est diffusé de proche en proche jusqu’à la destination. Au fur et à mesure, les identifiants des nœuds traversés sont ajoutés dans le paquet de recherche de route. Quand elle reçoit ce paquet, la destination sait donc déjà quel chemin il a emprunté, et obtient ainsi (en l’inversant) la route pour retourner à la source. A la réception, les paquets de recherche ayant suivi des chemins différents, la destination répond sur les chemins inverses, et la source aura ainsi finalement plusieurs chemins valides pour l’atteindre.

6 Etude détaillée du protocole AODV AODV (Ad hoc On demand Distance Vector) est un protocole de routage conçu par Charles E. Perkins et Elizabeth M. Royer et spécifié dans le RFC 3561 [11]. C'est un protocole basé sur le principe des vecteurs de distance et appartient à la famille des protocoles réactifs. Il représente essentiellement une amélioration de l'algorithme proactif DSDV mais réduit l'overhead (nombre de diffusions de messages) en ne calculant les routes que sur demande (AODV). Ce protocole utilise les deux mécanismes "découverte de route" et "maintenance de route", en plus du routage " nœud par nœud " et construit les routes par l'emploi d'un cycle de requête "route request/route reply" [20]. AODV utilise le principe des numéros de séquence afin de maintenir la consistance des informations de routage. A cause de la mobilité des nœuds dans les réseaux mobiles ad hoc, les routes changent fréquemment ce qui fait que les routes maintenues par certains nœuds, deviennent invalides. Les numéros de séquence permettent d'utiliser les routes les plus nouvelles ou autrement dit les plus fraîches (fresh routes) [17].

6.1 Table de routage et paquets de contrôle 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 [17]: • L’adresse IP 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 qui garantit qu’aucune boucle ne peut se former. • Liste des voisins actifs (origine ou relais d’au moins un paquet pour la destination pendant un temps donné). • Le temps d’expiration de l’entrée de la table. • Un tampon de requête afin qu’une seule réponse soit envoyée par requête. A chaque utilisation d’une entrée, son temps d’expiration est remis à jour (temps courant + active route time). Si une nouvelle route est nécessaire, ou si une route disparaît, la mise à jour de ces tables s'effectue par l'échange de trois types de messages entre les nœuds [17] :
RREQ (Route Request): Message de demande de route ;
RREP (Route Reply): Message de réponse à un RREQ ;
RERR (Route Error): Message qui signale la perte d'une route. Le format des paquets est donné ci-dessous: 28

Chapitre II

Routage dans les réseaux mobiles ad hoc

RREQ: contient essentiellement les champs suivants [11] : Type

J |R |G | D |U

Reserved Hop Count RREQ ID Destination IP Address Destination Sequence Number Originator IP Address Originator Sequence Number

Tab. 2.2 : Format du message RREQ.

• Type (8 bits): ce champ indique le type de paquet, dans ce cas il prend la valeur 1. • Flags (drapeaux) (5 bits): ce champ contient cinq flags (J, R, G, D, U) tel que ;
J (Join flag) et R (Repair flag) sont réservé pour le multicast ;
G (Gratuitous RREP flag) indique si un message RREP spécifique doit être envoyé à la destination dans le cas où un nœud intermédiaire possède un chemin à la destination.
D (Destination only flag) ce drapeau indique si seulement la destination qui doit répondre à la requête ou pas.
U (Unknown sequence number) indique le numéro de séquence de la destination est inconnu. • Réserved (11 bits): initialisé à la valeur 0 et ignoré à la réception du message. • Hop Count (8 bits): il contient le nombre de sauts parcourus par RREQ. • RREQ ID: il identifie la requête parmi les requêtes envoyées par la même source. • Destination IP Address: l'adresse IP de destination pour laquelle une route est désirée. • Destination Séquence Number: Le dernier numéro de séquence reçu dans le passé par le créateur pour n'importe quelle route vers la destination. • Originator IP Adress: l'adresse IP de la source de la requête. • Originator Sequence Number: Le nombre de séquence courant de la source contenue dans la table de routage de ce nœud s. RREP: contient essentiellement les champs suivants [11] : Type

R|A

Reserved Prefix Sz Destination IP Address Destination Sequence Number Originator IP Address Lifetime

Hop Count

Tab. 2.3 : Format du message RREP.

• Type (8 bits): ce champ indique le type de paquet, dans ce cas il prend la valeur 2. • Flags (drapeaux) (2 bits): ce champ contient deux flags ;
R (Repair flag) : utilisé pour le multicast.
A (Acknowledgment required): indique si la source doit envoyer un acquittement pour le message RREP. • Reserved (9 bits): initialisé à la valeur 0 et ignoré à la réception du message. 29

Chapitre II

Routage dans les réseaux mobiles ad hoc

• Préfix Sz(5 bits): si la valeur de ce champs est différente de zéro, ce dernier indique que le nœud prochain peut être utilisé pour chaque nœud demandant cette destination et qui possède la même valeur de Prefix Sz. • Hop Count (8 bits): il contient le nombre de sauts entre la source jusqu'à la destination. • Destination IP Address : l’adresse IP de la destination du paquet RREQ. • Destination Sequence Number : le numéro de séquence de la destination associé à cette route. • Originator IP Adress : l’adresse IP du nœud qui crée la requête. • Lifetime : le temps pour lequel chaque nœud qui reçoit RREP considère que la route est valide. RERR: Un message d'erreur de route contient essentiellement les champs suivants [11]: Type

N Reserved DestCount Unreachable Destination IP Address (1) Unreachable Destination Sequence Number (1) Tab. 2.4 : Format du message RERR.

• Type (8 bits): la valeur de ce champ prend 3 dans le message RRER. • Flag (1 bits): il contient un drapeau (N: No delete flag), celui-ci est indicatif lorsqu'un nœud est capable de réparer le lien, et informe les nœuds suivants qu'ils ne doivent pas supprimer le chemin. • Reserved (15 bits): initialisé à la valeur 0 et ignoré à la réception du message. • DestCount (8 bits): il indique le nombre de destinations inaccessibles incluses dans ce message. Ce champ doit être supérieur ou égal à un. • Unreachable Destination IP Address:l'adresse IP des destinations inaccessibles pour la raison de cassure de lien. • Unreachable Destination Sequence Number : le nombre de séquence de la liste des destinations inaccessibles qui se trouve dans le champ Unreachable Destination IP Address.

6.2 Numéro de séquence L'algorithme de Bellman Ford est un algorithme qui trouve le plus court chemin entre deux nœuds. Les protocoles à vecteur de distance sont en général sujets au problème de boucles de routage (routing loops) et de comptage à l’infini (counting to infinity) de l'algorithme de Bellman-Ford qu'ils utilisent. Certaines parties du réseau se trouvent isolées du reste, et les nœuds composants vont croire qu'ils peuvent atteindre les nœuds desquels ils sont coupés en passant par leurs voisins. Il s'en suit un phénomène de bouclage dans lequel les nœuds injoignables se voient attribuer des distances de plus en plus grandes. Dans le cas d'AODV, ces problèmes sont résolus par l'utilisation de numéros de séquence pour les messages de contrôle [15]. Chaque nœud possède un numéro de séquence. Il est le seul habilité à l'incrémenter. Ce numéro personnel ne peut être incrémenté que dans deux situations :  Avant d'entreprendre un processus de recherche de route par l'envoi d'un paquet RREQ, le nœud incrémente son numéro.  Avant de répondre à un message RREQ par un message RREP, le numéro de séquence doit être remplacé par la valeur maximale entre son numéro de séquence actuel et celui contenu dans le message RREQ. Ce numéro accompagne son adresse dans les messages 30

Chapitre II

Routage dans les réseaux mobiles ad hoc

de contrôle et permet aux autres de distinguer les messages importants des messages redondants. Le numéro de séquence est utilisé aussi pour la mise à jour de la table de routage, celle-ci ne s'effectue que si les conditions suivantes sont observées:  Le numéro de séquence du paquet de contrôle est strictement supérieur au numéro de séquence présent dans la table.  Les numéros de séquence (de la table et du paquet) sont égaux mais, la distance en sauts du paquet plus 1 est inférieure à la distance actuelle dans la table de routage.  Le numéro de séquence pour cette destination est inconnu. Cette façon de procéder garantit la création de routes sans boucles [17].

6.3 Principe de fonctionnement Deux étapes sont observées [17] ; la première est la découverte d’une route, et la deuxième est la maintenance des routes :

6.3.1 Découverte d'une route Un nœud diffuse une requête de route (RREQ), dans le cas où il aurait besoin de connaître une route vers une certaine destination et qu'une telle route n'est pas disponible (Fig 2.5).Cela peut arriver si la destination n'est pas connue au préalable, ou si le chemin existant vers la destination a expiré sa durée de vie ou il 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. Après la diffusion du RREQ, la source attend le paquet réponse de route (RREP). Si ce dernier n'est pas reçu durant une certaine période (appelée RREP_WAIT_TIME), la source peut rediffuser une nouvelle requête RREQ. Quand un nœud de transit (intermédiaire) envoie le paquet de la requête à un voisin, il sauvegarde aussi l'identificateur du nœud à partir duquel la première copie de la requête est reçue.

Fig. 2.5 : La propagation du paquet RREQ.

31

Chapitre II

Routage dans les réseaux mobiles ad hoc

Cette information est utilisée pour construire le chemin inverse (Fig 2.6), qui sera traversé par le paquet réponse de route de manière unicast (cela veut dire qu'AODV supporte seulement les liens symétriques). Puisque le paquet RREP 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 (temps d'expiration, numéro de séquence et prochain saut). Afin de limiter le coût dans le réseau, AODV propose d'étendre la recherche progressivement. Initialement, la requête 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.

Fig. 2.6 : Le chemin pris par RREP.

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é à l'application .La destination renvoie un message RREP, ce message peut donc être acheminé vers la source. Chaque nœud traversé incrémentera le nombre de sauts. Et ajoutera une entrée à sa table pour la destination. Une réponse adéquate peut aussi être donnée par un nœud situé entre la source et la destination. Dans ce cas l'obtention de routes bidirectionnelles est néanmoins possible grâce au drapeau "Gratuitous RREP". Le nœud intermédiaire enverra alors en plus un RREP vers la destination. Les nœuds entre le nœud intermédiaire et la destination ajouteront donc à leur table une entrée vers la source du RREQ. Cette disposition permettra à la destination d'envoyer directement des paquets à la source sans devoir procéder à la recherche d'une route. C'est utile lors de l'établissement de communications TCP pour l'envoi du premier ACK [20].

6.3.2 Maintenance des routes Afin de maintenir des routes consistantes, une transmission périodique du message "HELLO " (qui est un RREP avec un TTL (Time To Live) de 1) est effectuée. Si trois messages " HELLO " ne sont pas reçus consécutivement à partir d'un nœud voisin, le lien en question est considéré défaillant. Les défaillances des liens sont, généralement, dues à la mobilité du réseau ad hoc. 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 avec le nœud qui le suit dans le chemin de routage, devient défaillant, le nœud p diffuse un 32

Chapitre II

Routage dans les réseaux mobiles ad hoc

paquet UNSOLICITED RREP, avec une valeur de numéro de séquence égale à l'ancienne valeur du paquet RREP incrémentée d'une, 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. 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ées sans dépasser une certaine période (appelée active timeout period). Une entrée de la table du routage est active, si elle est utilisée par un voisin actif. Le chemin reliant la source et 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 participantes dans le 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 [18]. La maintenance peut être résumée dans les trois points suivants :  Des messages HELLO périodiques pour détecter les coupures de liens.  Si la source se déplace, la procédure de détermination de route peut être réinitié.  Si un nœud intermédiaire ou la destination se déplacent, un RREP spécial est émis au nœud source (reconstruisant la route au passage).

6.3.3 Gestion de la connectivité locale Lorsqu'un nœud reçoit un paquet en Broadcast, il met à jour ses informations de connectivité locale pour s'assurer qu'elles incluent ce voisin. Si aucun paquet n'est émis aux voisins actifs pendant le dernier hello_interval, un nœud va envoyer un HELLO (RREP non sollicité) contenant :  son identité.  son numéro de séquence (non modifié pour les HELLO).  time to live de 1 pour ne pas être retransmis.  liste des nœuds pour lesquels il a reçu un HELLO [18].

6.4 AODV : Avantages et inconvénients Des études comparatives montrent que certains protocoles sont plus performants que d'autres selon les caractéristiques du réseau. Ces études ont montré que le protocole AODV semble convenir à des réseaux à forte mobilité et semble performant dans les réseaux de faible densité [16]. Parmi les inconvénients du protocole de routage AODV, est le fait qu'il 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 ceux utilisés par les protocoles basés sur les algorithmes de recherche des plus courts chemins. L'avantage de ce protocole est qu'il ne présente pas de boucle de routage et évite le problème du "comptage à l'infini" de Bellman Ford. En effet, ce dernier 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 qui offre une convergence rapide quand la topologie du réseau ad hoc change [8]. Un autre avantage de ce protocole est sa simplicité, à titre d'exemple, le draft de DSR mesure 111 pages, le RFC de OLSR fait 75 pages, alors que celui d'AODV a une taille de 37 pages. Ensuite son ancienneté et sa maturité, AODV existe depuis longtemps et beaucoup de 33

Chapitre II

Routage dans les réseaux mobiles ad hoc

travaux ont déjà été réalisés à son propos et il a fait l'objet de simulations comparatives détaillées. Ce sont des critères assez subjectifs qui conduisent au choix d’AODV [20].

7 Autres protocoles De nombreux autres protocoles de routage ont été proposés pour les réseaux mobiles ad hoc. Dans la catégorie des protocoles hiérarchique on peut citer Cluster- Head Gateway Switcher Routing (CGSR) présenté dans [21]. Certains autres protocoles nécessitent l’emploi de matériels externes, Par exemple Temporaly-Ordered Routing Algorithm (TORA) [22] a besoin que les mobiles soient synchronisés. D’autres utilisent le système GPS pour estimer la direction géographique de la destination et ne faire intervenir qu’une sous-partie du réseau dans la phase de construction des routes. Alors que beaucoup de protocoles cherchent à minimiser le nombre de sauts (minimum shortest path), certains protocoles enfin s’attachent à prendre d’autres critères en considération. ABR [23] (Associativity-Based Routing) par exemple privilégie les liens les plus stables (mobiles qui restent longtemps dans le voisinage les uns des autres). SSR [24] (Signal Stability Routing) travaille à partir des informations de niveau de signal et cherche à maximiser la durée de vie du réseau en agissant sur la puissance d’émission de chaque mobile séparément [15].

Conclusion Si le routage dans son contexte général est une tâche complexe, les caractéristiques des MANETs rendent la conception d’un protocole de routage efficace plus complexe. De nombreux protocoles de routage ont été développés pour les MANETs faisant face aux contraintes spécifiques de ce type de réseaux. Ces protocoles peuvent être classés selon plusieurs critères : leur architecture, les algorithmes utilisés, les politiques de routages, etc. L’établissement des routes par ces protocoles se fait seulement suivant le critère classique : le plus court chemin ; il suffit d’assurer la connectivité entre une source et une destination. Cependant ce critère n’est pas du tout suffisant pour des applications comme le multimédia par exemple qui exigent des garanties particulières (la bande passante, le délai…etc.). En effet, il est nécessaire de penser à d’autres solution de routage optimales en termes de certains critères si nous voulons déployer de telles application dans un environnement ad hoc, on parle alors de la notion du routage avec qualité de service. Dans ce chapitre nous avons vu le concept de routage dans les réseaux mobiles ad hoc, les contraintes, une taxonomie des différents protocoles existants, ensuite nous avons décrit les principaux protocoles proposés pour les MANETs, en fin nous avons détaillé le fonctionnement du protocole AODV pour être l’objet de notre étude. Le choix du protocole AODV est justifié par les avantages cités dans la section 6.4. Dans le chapitre suivant nous allons étudier la notion de qualité de service, particulièrement le routage avec qualité de service, dans le but de faire une extension du protocole AODV pour garantir des exigences de la qualité de service.

34

Chapitre III

Qualité de service dans les réseaux mobiles ad hoc

Chapitre III

QoS dans les réseaux mobiles ad hoc

Qualité de Service dans les réseaux mobiles ad hoc

1 Introduction La performance d’un réseau est un élément fondamental et nécessaire pour une utilisation efficace d’applications, notamment les applications qui exigent une qualité de service (QoS, Quality of Service) telles que la téléphonie, la vidéo à la demande, la vidéo conférence ou encore les applications temps réels. Le déploiement de telles applications dans les MANETs représente de nombreux intérêts. Cependant on doit faire face à plusieurs défis et difficultés, et trouver des solutions fiables qui aident à l’intégration de la qualité de service dans ce genre de réseaux. Comme nous l’avons vu dans le chapitre 2, le groupe MANET de l’IETF a proposé plusieurs protocoles de routage pour les réseaux mobiles ad hoc. Ceux ci fonctionnent en mode best effort c'est-à-dire : au mieux. Cependant, ils ne permettent pas de garantir une qualité de service. Généralement, la recherche sur la qualité de service dans les réseaux mobiles ad hoc touche à plusieurs domaines ; Les modèles de QoS, la différentiation au niveau de la couche MAC (Medium Access Control), les protocoles de signalisation et Le routage avec QoS. Dans ce chapitre, on s’intéressera aux solutions de la QoS dans les MANETs, plus particulièrement au routage avec QoS, pour ce faire nous présentons d’abord les principales notions de qualité de service, la définition, les métriques, les solutions et le problème de routage avec QoS dans les MANETs.

2 Définition de la Qualité de service La recommandation E.800 du CCITT (Consultative Committee for International Telegraph and Telephone) définit la qualité de service (QoS pour Quality of Service ou QdS pour (Qualité de Service) comme : « l’effet général de la performance d’un service qui détermine le degré de satisfaction d’un utilisateur du service ». Cette définition reflète la perception de la qualité de service de point de vue d’un utilisateur [19]. Dans le RFC 2386 [25], la QoS est définit comme un ensemble de besoins à assurer par le réseau pour le transport d’un trafic d’une source à une destination. Ces besoins peuvent être traduits en un ensemble d’attributs pré-spécifiés et mesurables en terme de : • Délai de bout en bout, • Variance de délai (gigue), • Bande passante, • Pertes de paquets.

3 Les métriques de la qualité de service Les principaux aspects connus de la qualité de service sont : la bande passante, le délai de bout en bout, la gigue (variation du délai), et les pertes de paquets (souvent exprimée en termes de taux d’erreurs).

36

Chapitre III

QoS dans les réseaux mobiles ad hoc

Les métriques de QoS peuvent être additives, concaves ou multiplicatives ;
Une métrique additive Am est définie comme

h

∑ Li ( m ) où

Li est la valeur de la

i=0

métrique m sur le lien Li , Li ∈ P .h représente la longueur du chemin P .
Une métrique concave définit la valeur minimale sur un chemin comme suit : Cm = min( Li (m)) , Li (m) ∈ P .

P et représenté


Une métrique multiplicative représente le produit des valeurs des métriques de QoS, elle est définie comme le produit des Li (m) avec i allant de 1 à h, Li(m) ∈ P [17]. La bande passante est une métrique concave, alors que le délai et la gigue sont des métriques additives. La disponibilité d’un lien, basée sur des critères comme la probabilité de perte du lien quant à elle est une métrique multiplicative [7].

3.1 La bande passante La bande passante représente la source de transmission qu’occupe ou reçoit un flot. La gestion de la bande passante est un élément important pour la garantie de la qualité de service [17].

3.2 Délai de bout en bout Le terme « délai » englobe en réalité trois aspects temporels différents : 1. le délai de propagation, déterminé par la distance physique qui sépare la source de la destination. 2. le délai d’attente et de traitement des paquets à l’intérieur des files d’attente, déterminé par la charge du réseau, ainsi que les politiques de traitement de l’information dans les routeurs pour obtenir une fluidité maximale de l’écoulement de l’information. 3. le délai de transmission dépendant de la taille des flots. Ce paramètre est aussi étroitement lié à l’utilisation du réseau et au partage de la bande passante disponible. Garantir le délai, implique la nécessité de mettre en œuvre des mécanismes permettant de gérer au mieux l’acheminement de l’information vers la destination en un temps minimal, tenant compte des trois natures de délais précédemment cités [19].

3.3 La gigue : (variation du délai) La gigue correspond à la variation du délai de transmission de bout en bout entre les différents paquets d’un flot à travers un réseau. La gigue est due principalement aux délais de traitement variables dans les nœuds du réseau. Ce paramètre nuit automatiquement à la qualité de service demandée.

3.4 La perte de paquets Elle se produit lorsqu'il y a des erreurs d'intégrité sur les données. La perte de paquets se produit principalement lorsque l'intensité du trafic sur les liens de sorties devient supérieure à leur capacité d'écoulement [20].

37

Chapitre III

QoS dans les réseaux mobiles ad hoc

4 Le besoin en QoS des d’applications Au début de l’apparition des réseaux mobiles ad hoc, l’objectif été d’assurer la communication entre les nœuds on utilisant le service « best effort ». Mais pour des applications telles que le multimédias, téléphonie, jeux, applications critiques, communications dans un champ de bataille, etc. ce service n’est pas suffisant. Ces applications sont exigeantes en terme de certains critères (bande passante, délai.. etc.). Suivant le type de l’application, les besoins de QoS sont différents. Par exemple, pour les applications temps réel, comme la voix et la vidéo, le délai de bout en bout d’un paquet doit être borné, autrement le paquet est inutile. Les applications non temps réel, comme le transfert de fichiers ou la messagerie, quant à elles se focalisent sur la fiabilité des communications [7]. La figure 3.1 montre un exemple des besoins de quelques applications de la qualité de service particulièrement des deux métriques : bande passante et délai de bout en bout [19].

Fig.3.1 : exemple de besoins de QoS.

5 Exemple de besoins de QoS : la voix sur IP (VoIP) La VoIP (Voice over Internet Protocol) est un ensemble de technologies qui permettent le transport de la voix numérisée sur les réseaux à commutation de paquets au lieu des réseaux à commutation de circuits classique (PSTN, Public Switched Telephony Network). La VoIP sert surtout à la ToIP (Telephony over IP). La finalité du travail effectué dans ce mémoire est de faire une extension du protocole AODV en lui rend sensible à une métrique de QoS on améliorant les performances de la voix sur IP dans les réseaux mobiles ad hoc. En effet il est nécessaire de connaître les besoins de QoS de cette application. Pour cela nous traitons dans ce qui suit la voix sur IP, et ses différentes caractéristiques et paramètres.

5.1 Les paramètres de la voix sur IP La problématique de qualité de la voix sur IP est particulière car la voix attend de son transporteur autre chose que les données. La transmission de données classique (fichiers, messages, transactions …) ne supporte aucune perte en ligne sous peine de graves conséquences pour l’interprétation et l’utilisation de ces données, mais elle supporte en revanche une dérive importante en terme de durée d’acheminement. Le comportement attendu pour la voix est exactement inverse : 1% ou 2% de perte de données de voix en ligne ne sont pas trop gênants pour la qualité du service de VoIP, mais en

38

Chapitre III

QoS dans les réseaux mobiles ad hoc

revanche une variation fréquente de 100 ms sur le délai de transit est catastrophique et rend le service inutilisable [48]. Les principaux paramètres influents en VoIP sont, les échantillonnages (codecs), le délai de bout en bout, la gigue et les pertes de données.

5.1.1 Les différents échantillonnages Le paramètre d’échantillonnage ou codec (pour compression / décompression) est structurant en VoIP. Le codec détermine à quelle vitesse la voix est échantillonnée et dimensionne par la même le flux de données numériques que va générer la transformation d’un échantillon temporel de voix analogique. Les codecs sont répertoriés par leur nom à l’ITU(International Telecommunication Union). Les codecs les plus utilisés et leurs vitesses d’échantillonnage sont les suivants : codec G.711 G.726 G.726 G.728 G.729 G.723.1 MPMLQ G.723.1 ACELP

Vitesse d’échantillonnage 64 kbps 32 kbps 24 kbps 16 kbps 8 kbps 6.3 kbps 5.3 kbps

Tab 3.1 : les principaux codecs et leurs Vitesses d’échantillonnage.

5.1.2 Le délai de bout en bout Le délai de bout en bout (ou end-to-end Delay) est un des paramètres critiques influençant fortement la QoS d’un service de voix sur IP. C’est le temps que va mettre en moyenne un paquet IP contenant un échantillon de voix pour traverser l’infrastructure entre deux interlocuteurs [48]. Les recommandations G.114 et G.131 de l’ITU-T stipulent que la valeur recommandée pour le délai de transit de la voix de bout en bout ne doit pas dépasser 150ms pour un codec G711, pour un autre codec cette valeur n’est pas la même (tableau3.2). Délai de bout en bout

Effet sur la qualité perçue

<100-150ms

délai non détectable

150-400ms

qualité acceptable

Plus de 400

Délai inacceptable ; conversation non compréhensible Tab. 3.2 : les seuils du délai pour un codec G711.

5.1.3 La gigue La variation du délai(ou gigue) est la conséquence du fait que tous les paquets contenant des échantillons de voix ne vont pas traverser le réseau à la même vitesse. Cela crée une déformation de la voix ou un hachage.

39

Chapitre III

QoS dans les réseaux mobiles ad hoc

La gigue est indépendante du délai de transit. Le délai peut être court et la gigue importante ou inversement. La gigue est une conséquence de congestions passagères sur le réseau, ce dernier ne pouvant plus transporter les données de manière constante dans le temps. La valeur de la gigue va de quelques ms à quelques dizaines de ms.

5.1.4 La perte de paquets Une perte de données régulière mais faible est moins gênante en voix sur IP que des pics de perte de paquets espacés mais élevés. En effet l’écoute humaine s’habituera à une qualité moyenne mais constante et en revanche supportera peu de soudaines dégradations de la QoS. Le taux de perte en VoIP est en générale de quelques pourcents à des dixièmes de pourcent. Le tableau 3.3 présente les seuils de valeurs pour les paramètres critiques et les conséquences constatées pour la qualité de service de la VoIP en codec G.711 64 kbps [48]: qualité métrique Délai de bout en bout Gigue Perte de paquets

Bonne D < 150 ms G < 20 ms P < 1%

Moyenne

Mauvaise

150 ms < D < 400 ms 400 ms < D 20 ms < G < 50 ms 50 ms < G 1% < P < 3% 3% < P

Tab.3.3 : les exigences de QoS pour la VoIP.

6 La QoS dans Les réseaux mobiles ad hoc La qualité de service a été largement étudiée dans les réseaux filaires. Le réseau ATM (Asynchronous Transfert Mode) a considéré le support de la QoS pour les trafics en plusieurs classes [7]. Des solutions ont été proposées par l’IETF pour améliorer le réseau Internet afin de fournir la QoS aux communications multimédia. Les groupes de l’IETF se sont penchés sur deux idées [19] : IntServ [27] (Integrated Services), et DiffServ [28] (Differentiated Services). Malheureusement aucune de ces solutions ne peuvent être utilisée directement dans les MANETs [30]. En effet il est très difficile de garantir une quelconque qualité de service à une application dans un réseau mobile ad hoc. Car, il faut prendre en considération les spécificités de ces réseaux, à savoir : la bande passante limitée, le changement dynamique de la topologie en fonction du temps, le manque d’information complète sur l’état du réseau, ainsi que l’absence d’une administration centralisée ce qui implique une gestion distribuée du trafic nécessaire au fonctionnement du réseau. En outre, la communication entre les stations mobiles étant sans fil, la qualité du lien sans fil reste peu fiable, et susceptible à des variations suivant la configuration et l’état du réseau [7]. Donc assurer une QoS dans les MANETs revient à « fournir une fonctionnalité complexe dans un environnement très dynamique où les ressources sont rares » [30]. Dans ce contexte, plusieurs solutions pour la QoS dans les MANETs ont été proposées par la communauté scientifique pour pallier aux problèmes liés aux contraintes spécifiques des réseaux mobiles ad hoc. Dans ce qui suit, nous allons présenter les solutions les plus permanentes.

7 Solutions de QoS dans les MANETs Les solutions de QoS pour les réseaux mobiles ad hoc peuvent être classifiées en quatre catégories (figure 3.2) [30]: Les modèles de QoS, la différentiation au niveau de la couche MAC (Medium Access Control), les protocoles de signalisation, et le routage avec QoS. 40

Chapitre III

QoS dans les réseaux mobiles ad hoc

Solutions de QoS dans les MANETs

Protocoles de signalisation

Routage avec QoS

Différentiation Couche MAC

Interviennent à une couche ou sous-couche du modèle de référence OSI

Modèles de QoS Approches Inter couche CROSS LAYER

Fig.3.2 - solutions de QoS pour les réseaux ad hoc.

En réalité, ces solutions ne sont pas indépendantes. En effet, pour construire un bon modèle de qualité de service, les autres composants de QoS (routage QoS, protocole de signalisation, protocole MAC avec QoS) doivent coopérer pour atteindre cet objectif. En outre, Un protocole MAC QoS est un composant essentiel de la qualité de service dans les MANET, toutes les couches supérieures (routage QoS et protocole de signalisation) dépendent du protocole MAC avec QoS [32].

7.1 Modèles de qualité de service Un modèle de qualité de service définit quels types de service peuvent être fournis dans un réseau et certains mécanismes utilisés afin d'offrir ces services (quelles fonctionnalités doit fournir le protocole de routage, quelle est l'architecture des nœuds, etc.) [32]. Les modèles les plus connus dans le monde filaire sont :
IntServ (Integrated services) : spécifié dans le RFC 1633 [27], ce modèle propose une architecture à base de réservation de ressources pour chaque flot. Cette dernière s’effectue au moyen du protocole RSVP (Resource Reservation Setup Protocol), Cependant, IntServ n’est pas propice à des réseaux de grande envergure [19].
DiffServ (Differentiated Services) : spécifié dans le RFC 2475[28], ce modèle fonde son concept sur une gestion de trafic par classe, sur des méthodes de conditionnement du trafic à l’entrée du réseau et sur le marquage de celui-ci en fonction de son appartenance à une classe, Trois principaux services de DiffServ sont mis en œuvre : le service « BestEffort » pour les paquets à traiter « au-mieux » comme le fait Internet actuellement ; le service « Assured Forwarding » pour des classes à priorité plus grande enfin le service « Expedited Forwarding » pour les classes les plus prioritaires [19]. • FQMM (Flexible Quality of service Model for Mobile ad hoc networks)

FQMM est un modèle de QoS proposé pour les MANETs. Les concepteurs du modèle FQMM prennent en compte le fait que les réseaux ad hoc pourraient, à terme être connectés à des réseaux filaires de type Internet. Il apparaît dès lors nécessaire d'offrir un mécanisme de qualité de service suffisamment proche des protocoles filaires afin de s'interfacer avec ces derniers. Le modèle FQMM se situe entre les deux modèles IntServ et DiffServ, il définit plusieurs classes de service dont la plus haute permet à chaque flux de spécifier les contraintes qui lui sont propres. FQMM définit trois types de nœuds : les nœuds d'entrée (émetteurs), les nœuds intermédiaires et les nœuds de sortie (récepteurs). Compte tenu du fait que dans un réseau ad hoc, chaque nœud assure la fonction de routeur, chaque mobile joue différents rôles pour différents flux. Le conditionnement du trafic (lissage, marquage, etc.) est à la charge des 41

Chapitre III

QoS dans les réseaux mobiles ad hoc

émetteurs. FQMM requiert l'utilisation d'un protocole de routage capable d'offrir une certaine QoS, c'est à dire capable de rechercher des routes satisfaisant certaines contraintes [32].

7.2 Solutions au niveau de la couche MAC La plupart des protocoles proposés pour la couche MAC dans les réseaux mobiles ad hoc s'intéressent aux problèmes d'accès au médium ainsi qu'à la fiabilité des communications. Très peu s'attaquent aux problèmes de réservation de trafic et de garanties de QoS. Récemment, des schémas de différenciation de service au niveau MAC ont été proposés.

7.2.1 Différenciation de services pour IEEE 802.11 Le principe est de doter le protocole IEEE 802.11 d’un mécanisme de priorités entre les trames afin de concevoir des mécanismes de différenciation de services efficaces. Pour ce faire, les auteurs de [29] proposent d’adapter certains paramètres de la fonction de coordination distribuée (DCF) du protocole 802.11 selon les priorités des paquets. Ces paramètres peuvent être adaptés dynamiquement afin d’offrir un mécanisme de priorités au protocole 802.11 :  Lorsqu'une collision survient, les délais avant retransmission sont allongés aléatoirement. Il est possible d'incrémenter ces délais différemment selon le niveau de priorité.  Il est possible d'utiliser différentes valeurs du délai de silence avant une transmission (DIFS) selon le niveau de priorité de la transmission.  Enfin, il est possible de limiter la longueur des trames selon le niveau de priorité, les trames peu prioritaires occupant le canal moins longtemps [32].

7.2.2 MACA/PR (Multihop Access Collision Avoidance with Piggyback Reservation) Ce protocole propose de fournir des garanties de bande passante pour les applications temps réel via une réservation. Il permet d'établir des connexions temps réel à un saut seulement. Il utilise un dialogue RTS/CTS avec acquittement, et différencie la politique d'accès au médium selon la nature des flux. Pour le trafic prioritaire, une seule demande d'autorisation à transmettre (RTS/CTS) au début du flux est utilisée. Dans chaque paquet, des informations sur l'ordonnancement du paquet suivant sont incluses pour empêcher les voisins d'entrer en collision avec les prochains paquets [20].

7.2.3 IEEE 802.11e Actuellement en cours d’évaluation, la spécification du draft IEEE 802.11e [31] propose le support de la QoS dans les réseaux sans fil avec une nouvelle fonction de contrôle EDCA (Enhanced Distributed Channel Access), considérée comme la nouvelle version de la fonction DCF. EDCA introduit quatre catégories de trafics (TC). Les priorités sont contrôlées par les stations en modifiant le schéma d’accès de base (DCF). 802 .11e propose aussi une fonction de coordination hybride (HCF) Plus flexible que la fonction PCF, HCF est utilisée par les points d’accès pendant la période d’accès contrôlée (CAP), qui peut commencer à n’importe quel moment durant la ‘superframe’. Autrement dit, ça lui permet d’avoir accès au médium pour faire passer un trafic ayant des contraintes de QoS [7].

7.3

Protocoles de signalisation

Le but des protocoles de signalisation est de fournir un moyen de propager des informations de contrôle à travers un réseau. Les informations transmises peuvent être de 42

Chapitre III

QoS dans les réseaux mobiles ad hoc

différentes natures. Il peut s’agir d’informations topologiques, de demandes de recherche de routes satisfaisant certaines contraintes ou encore de rapports sur l’état du réseau et la disponibilité des ressources. Concevoir un protocole de signalisation consiste à définir les données à échanger afin de réaliser une tache particulière ainsi que la manière de les échanger [32]. La signalisation permet de réserver et de mettre à jour les ressources, d'initialiser et d'arrêter le trafic ainsi que de renégocier le profil du trafic. Elle peut s'effectuer à l'intérieur des paquets de données (signalisation in band) ou grâce à des paquets explicites de contrôle (signalisation out band) [20].  INSIGNIA

INSIGNIA est un protocole de signalisation in-band (la signalisation est incluse dans les entêtes des paquets de données) permettant d’effectuer des réservations de bande passante dans les réseaux ad hoc. INSIGNIA offre des garanties sur la base d’une granularité par flot aux applications adaptatives capables de modifier leur comportement en fonction de la quantité de bande passante qui leur est allouée. Chaque application spécifie deux niveaux de qualité de service. Le niveau de base permet de spécifier la bande passante minimale nécessaire au trafic et le niveau amélioré, le débit optimal à atteindre lorsque les ressources sont disponibles. Ce protocole a été conçu pour réagir rapidement aux changements de topologie. INSIGNIA n’est pas lié à un protocole de routage particulier [32].

7.4 Routage avec QoS Dans le RFC 2386 [25], le routage avec QoS est défini comme étant : « Un mécanisme de routage dans lequel les chemins sont déterminés en fonction des connaissances sur la disponibilité des ressources du réseau ainsi que l'exigence de qualité de service de flux ». En d’autres termes l’auteur de [33] le définit comme étant : « un processus d’établissement et de maintenance de routes optimales satisfaisant un certain critère sur la qualité de la transmission de données ». Les algorithmes de routage traditionnels ont été proposés pour router les données sans tenir compte des contraintes spécifiques ou à des demandes des utilisateurs. Ainsi, ils sont inadaptés aux applications qui nécessitent le support de la qualité de service. Le routage avec QoS est un élément clé pour réaliser une architecture de QoS pour les réseaux mobiles ad hoc. Le protocole de routage QoS peut informer une source sur la bande passante et la disponibilité (en termes de QoS) de la destination. Cette connaissance va permettre l'établissement de connections avec qualité de service. Les exemples illustrés dans la figure 3.3 montrent la différence entre un protocole classique et un protocole avec QoS ; dans le premier, la route choisie est celle passée par les nœuds B, C et F est au lieu du plus court chemin passé par D, E car elle satisfait le besoin de la QoS de la bande passante demandée. Dans le deuxième la route choisie est B E F car elle satisfait le besoin du délai.

43

Chapitre III

QoS dans les réseaux mobiles ad hoc <5>

<4>

<70>

<20>

B

S

<4> <2>

E

: bande passante Besoin en QoS: Bp≥4

F <2>

<25>

<60>

<4> Plus court chemin

D

<50> <30>

<70>

<3> <3>

D

S

<5>

C

B

C

E

F <70>

: Délai Besoin en QoS:D≤150 Plus court chemin

<40>

1

D

Chemin satisfaisant la QoS

2

D

Chemin satisfaisant

la QoS

Fig. 3.3 - exemples de routage avec QoS.

7.4.1 Objectifs du routage avec QoS Le routage avec QoS cherche à atteindre les trois objectifs suivants [25]: 1. Détermination dynamique de chemins possible : le routage QoS peut déterminer parmi de nombreux choix, un chemin répondant aux exigences de QoS et qui est réalisable de bout en bout. 2. Optimisation de l'utilisation des ressources : le routage QoS peut aider dans l’utilisation efficace des ressources en améliorant la capacité totale du réseau. 3. Permettre une dégradation gracieuse des performances du réseau.

7.4.2 Difficulté de routage avec QoS dans les MANETs Dans le cas du routage avec qualité de service, le but n'est pas simplement de trouver le meilleur chemin selon un certain critère mais de trouver le meilleur chemin admissible. On ajoute un certain nombre de contraintes sur les routes afin de déterminer leur éligibilité. Par exemple, on peut vouloir rechercher une route disposant d'une certaine quantité de bande passante pour un trafic vidéo. Toute route satisfaisant un certain critère quantitatif peut être qualifiée de route assurant une certaine qualité de service [33]. Si l’on peut considérer que cet objectif sera bientôt atteint dans les réseaux locaux filaires, les réseaux ad hoc présentent un grand nombre de spécificités qui rendent la conception d’un tel algorithme de routage avec QoS très difficile. Les réseaux ad hoc sont avant tout des réseaux radio, la propagation radio dans l’air est soumise à des contraintes spécifiques. Les ondes radio sont extrêmement sensibles à leur environnement. Le multi hop exigé par l’absence d’une administration de base implique une gestion distribuée de la fonction du routage et l’ajout d’une métrique de la qualité de service rende le mécanisme d’établissement des routes plus compliqué. En fin les changements de topologie dans les réseaux ad hoc exigent de recalculer les routes avec QoS, et répondre assez rapidement sans dégrader leur niveau de QoS. Par conséquent, des ressources additionnelles sont consommées (bande passante, batterie, etc.) [7].

7.4.3 Protocoles de routage avec QoS Plusieurs protocoles de routage avec QoS ont été proposés par la communauté scientifique pour les MANETs faisant face aux contraintes spécifique de ces réseaux. Ces protocoles se distinguent par plusieurs critères ; selon les métriques de QoS intégrées, ….la plupart sont des extensions des protocoles best effort existants.

44

Chapitre III

QoS dans les réseaux mobiles ad hoc

Le tableau 3.4 décrit quelques protocole de routage avec QoS représentatifs avec les différents caractéristiques et techniques de fournir la qualité de service au niveau de la couche réseau. Chacun de ces protocoles aborde les problèmes de l’estimation de la bande passante et du délai, la découverte de routes avec QoS, la réservation des resources, et l’approche utilisée dans la maintenance des routes, les protocoles présentés dans ce tableau sont décrits dans [47]. Protocole de routage CEDAR

Architecture

Hiérarchique

Ticketbased

plat

OLSRbased

hiérarchique

AQOR

plat

ADQR

plat

TDR

plat

BEQR

plat

Métrique de QoS

Bande passante Bande passante /délai Bande passante Bande passante /délai Bande passante Bande passante Bande passante

découverte de routes

Réservation de ressources

Prise en compte des cassures de liens

Routes redondantes

Non

Proactive /réactive

Oui

Non

Non

Non

réactive

Oui

Non

Oui

Oui

Proactive

Non

Non

Non

Oui

réactive

Oui

Non

Non

Non

réactive

Oui

Oui

Oui

Non

réactive

Oui

Oui

Non

Oui

réactive

Non

Non

Non

Estimatimation de délai/bande passante

Tab.3.4 : exemples de protocoles de routage avec QoS.

Conclusion Avec les avantages qu’offrent un MANET par rapport à d’autres types de réseaux, le déploiement de nouvelles applications dans ces réseaux représente plusieurs intérêts. Pour certaines applications, telles que le multimédia, l’introduction de la QoS dans les MANETs est devenue une nécessité. Plusieurs solutions ont été proposées à plusieurs niveaux pour atteindre cet objectif. Selon le cas, ces solutions peuvent toucher une ou plusieurs couches du réseau, la solution qui touche plus de niveaux est la solution la plus efficace. Dans notre étude on s’intéressera plus particulièrement à la couche réseau, en essayant d’établir un routage efficace en termes de certains critères de la QoS. Ce présent chapitre discute le concept de QoS dans les MANETs, plus particulièrement le routage avec QoS et les problèmes rencontrés dans le contexte ad hoc. Dans le prochain chapitre, nous allons étudier les détailles de la conception d’un protocole de routage avec QoS ; il s’agit d’une extension du protocole AODV étudié en détails dans le chapitre 2 on lui rend sensible à une métrique de QoS.

45

Chapitre IV

Conception

Chapitre IV

Conception

- 46 -

Chapitre IV

Conception

Conception 1 Introduction Deux approches sont possibles pour la conception d’un protocole de routage avec QoS :
Approche révolutionnaire qui consiste à concevoir un nouveau protocole avec de nouvelles fonctionnalités.
Approche évolutionnaire qui consiste à faire des extensions des protocoles best effort existants ou d’apporter des améliorations à un protocole de routage avec QoS en ajoutant d’autres métriques par exemple. Dans le cadre de cette étude nous avons choisi cette dernière pour deux raisons ; la première qu’il est plus efficace et facile et encore moins coûteux d’améliorer un travail existant qu’à refaire un autre travail de nouveau. La deuxième est qu’une extension d’un protocole existant est plus compatible avec la version originale ce qui permet l’utilisation des deux à la fois et facilite l’interconnexion des deux plate formes fonctionnant avec l’ancienne et la nouvelle version du protocole. Le protocole concerné par cette étude est le protocole AODV étudié en détail dans le chapitre II. Comme nous l’avons vu, les chemins établis par le protocole AODV standard ne permettent pas de garantir des critères de qualité de service. C'est pourquoi il semble important de faire une extension de ce protocole afin d'assurer une certaine qualité de service. L’intégration de la QoS dans AODV a pour objectifs :
Améliorer la QoS dans les réseaux mobiles ad hoc.
Introduire une métrique plus appropriée que la distance (nombre de sauts).
Évaluer les performances d’AODV afin de tester son efficacité pour des applications exigeantes en QoS. Dans cette partie, nous allons discuter les spécifications d’une solution qui intègre la QoS dans le protocole AODV basée sur la métrique délai de bout en bout. Le choix de la métrique délai de bout en bout est justifié par le besoin de déploiement des applications sensible à cette métrique dans les MANETs telles que la VoIP. Pour ce faire, nous avons commencé d’abord par la description de la méthode d’estimation du délai qui sera utilisée pour aider AODV à intégrer cette métrique. Par la suite, nous expliquons les modifications nécessaires ajoutées à la structure d’AODV ainsi que le nouveau mécanisme de fonctionnement basé sur la recherche de routes assurant la métrique délai de bout en bout, et une anatomie le l’agent de routage AODV avec QoS à travers quelques diagrammes UML (Unified Modeling language).

2 Le routage AODV avec QoS Plusieurs travaux ont visé à améliorer les performances du protocole AODV. Nous pouvons citer à titre d’exemple : AOMDV (Ad-hoc on-demand multipath distance vector) [34], AODVM (Ad hoc On-Demand Distance Vector Multipath)[35], AODV-BR (AODV with Backup Routes) [36], EAODV(An Extended AODV protocol) [37], et QAODV (QoS Ad Hoc On-Demand Distance Vector)[38]. Ces travaux essayent d’apporter des améliorations au protocole AODV en termes de certains critères en utilisant des méthodes et techniques diverses. Dans cette étude, nous nous intéressons plus particulièrement à la métrique délai de bout en bout. - 47 -

Chapitre IV

Conception

Afin de concevoir un protocole de routage avec QoS basé sur le délai comme métrique, Une méthode d’estimation du délai est indispensable, pour cela, nous allons d’abord effectuer une étude d’une méthode d’estimation du délai. La méthode adoptée dans cette étude est basée sur le travail de C. Sarr dans [42].

2.1 Estimation du délai dans les MANETs La méthode la plus classique d’estimer le délai consiste à calculer la différence entre le temps d’envoi et le temps de réception d’un paquet donné. Cette méthode n’est pas précise car, elle est basée sur l’hypothèse de synchronisation des unités mobiles, ce qui est difficile à assurer dans un réseau ad hoc. En effet, d’autres travaux sont effectués, Une chronologie de ces travaux est présentée dans [42]. La plupart de ces travaux essayant d’estimer le délai et qui se basent sur la modélisation de la fonction DCF de 802.11 faite par Bianchi [44], cependant, les hypothèses effectuées dans le modèle de Bianchi, ne sont pas réalistes et ne peuvent être adaptées pour le calcul du délai dans un environnement ad hoc multi-sauts [42]. Ces hypothèses sont :
Le nombre n de stations en compétition est connu et constant ;
La probabilité de collision est constante et indépendante ;
Cette probabilité de collision est la même pour tous les nœuds ;
Les nœuds sont tous dans la même zone de communication. Il n’y a donc pas de phénomène de stations cachées, ni d’interférences. Toutes ces hypothèses fondamentales permettent de simplifier les chaînes de Markov obtenues et de les résoudre, ce qui ne sera pas le cas dans des réseaux ad hoc multi-sauts.

2.2 Estimation du délai à un saut Le délai de bout en bout est une métrique additive. Il est égal à l’ensemble des délais à un saut radio sur le chemin menant de la source à la destination. Ce dernier peut se décomposer en deux parties :
Le délai entre l’instant où le paquet entre dans la file d’attente du nœud émetteur et l’instant où il est passé à la couche MAC.
Le délai s’écoulant entre le moment où le paquet est reçu par la couche MAC jusqu’à la réception de l’acquittement correspondant par le nœud récepteur, Un paquet se trouvant à une station quelconque provient de deux sources : les paquets générés localement au niveau du nœud considéré et les paquets routés qui passent par ce nœud. Ainsi, chaque nœud du réseau peut jouer le rôle de nœud source, routeur ou destination.

2.2.1 Détermination du délai dans la file d’attente Un nœud sans fil de type 802.11 peut être vu comme un buffer qui se remplit par des paquets entrants provenant des couches supérieures. Ainsi un seul serveur fournit le traitement nécessaire pour ces paquets. Le système être modélisé par une file d’attente M/M/1/K (comme indiqué dans la figure 4.1), possédant les propriétés suivantes :
L’arrivée des clients suit une loi exponentielle de paramètre λ .
Le traitement des clients suit également une loi exponentielle de paramètre µ .
Il y a un seul serveur pour le traitement des clients entrants.
La taille de la file est bornée par la valeur K . Un client est alors perdu s’il y a déjà K clients dans le système [42]. - 48 -

Chapitre IV

Conception Queue µ

λ Client

Serveur n(t)≤K

Fig. 4.1- Modélisation d’un nœud 802.11 par une file M/M/1/K.

Le paramètre λ représente le débit désiré par l’application qui est explicitement fourni lors de la phase de requête de route avec QoS. Le paramètre µ représente la bande passante libre autour de ce nœud. Cette valeur peut être estimée en calculant le pourcentage de temps libre TL qui sera ensuite multiplié par la capacité maximale du médium radio Cmax suivant la formule :

µ = TL × C

m ax

…………...……………..4.1

La modélisation du taux de service µ par la bande passante résiduelle (libre) d’un nœud permet de prendre en compte deux facteurs :
Le temps s’écoulant entre l’instant où le mobile rentre dans la file d’attente et l’instant où il la quitte.
Le temps que le mobile doit attendre au niveau MAC avant de pouvoir émettre ses paquets, le médium étant occupé par des transmissions voisines. En effet, la bande passante libre n’est pas la même sur tous les nœuds du réseau. Cela dépend du trafic passant par le nœud et de l’activité des transmissions des nœuds voisins. La figure 4.2 montre un exemple de la variation de la bande passante libre dans le temps sur deux nœuds du réseau obtenu par simulation (pour une capacité du médium de 11Mbps).

Fig. 4.2- Exemple de la bande passante libre sur deux nœuds d’un MANET. - 49 -

Chapitre IV

Conception

Le délai d’un paquet dans la file d’attente de l’émetteur n’est autre que le temps moyen de séjour noté R d’un client arrivant dans la file, donnée par la loi de Little : R=

ρ 1 − (Κ +1) ρ Κ + Κρ Κ +1 1 1− ρ 1− ρΚ λ

Avec : ρ =

λ µ

Ce temps de service diverge lorsque ρ = 1. Nous allons donc calculer la limite de R quand ρ → 1 de ce temps de service. On obtient donc comme résultat :

1 1 lim R = (Κ +1) ρ →1 2 λ

D’où l’expression finale de R est donnée par :

ρ 1 − (Κ +1) ρ Κ + Κρ Κ+1 1 Si ρ ≠ 1 1− ρ 1− ρ Κ λ R=

………………..……….4.2

1 1 (Κ +1) Si ρ = 1 2 λ

2.2.2 Détermination du délai de propagation Le délai de propagation est le délai qui s’écoule depuis l’arrivée d’un paquet à la couche MAC jusqu’à la réception du paquet d’acquittement en provenance du nœud récepteur, incluant toutes les retransmissions en cas de collision.
Soit P la probabilité de collision sur le lien considéré.
Soit n le nombre de retransmissions associées à la probabilité de collision p.
Soit X la variable aléatoire représentant le nombre de retransmissions. On a donc les égalités suivantes en terme de probabilité : P( X = 0) = p 0 (1 − p) P( X = 1) = p1 (1 − p) P( X = 2) = p 2 (1 − p) . . . j P( X = j ) = p (1 − p) Pour j ≤ 6

Dans la norme IEEE 802.11 le nombre maximum de retransmissions est fixé à 7 donc : P( X = 7) = p 7 P ( X = i) = 0 Si i ≥ 8

On remarque que le facteur (1 − p) n’est pas présent lorsque X = 7 , car après 7 retransmissions sans réception d’un acquittement, le paquet de données correspondant est droppé par la couche MAC. Nous pouvons donc en déduire l’espérance de la variable aléatoire X correspondant au nombre moyen de retransmissions n : - 50 -

Chapitre IV

Conception 6

n = E ( X ) = ∑ i. p i (1 − p ) + 7 p 7 i =0

Pour obtenir une expression simplifiée de n en fonction de p on utilise les résultats sur la dérivabilité des sommes géométriques : 6

On sait que : ∑ p i = i =0

1 − p7 1− p

En dérivant cette expression par rapport à la variable p on obtient : 7

⇒ ∑ p i −1 = i =0

6 p7 _ 7 p6 + 1 (1 − p ) 2

En multipliant l’expression par (1 − p ). p on obtient finalement : 7

n = ∑ p i (1 − p ) = i =0

6 p8 _ 7 p7 + p (1 − p )

………..…………..…4.3

De plus, selon la norme IEEE 802.11, à chaque collision la taille de la fenêtre de contention est doublée ainsi à la i eme collision successive ( i ≤ 7 selon la norme IEEE 802.11) la taille de la fenêtre de backoff est de 2i CWmin . Le backoff étant une loi uniforme, à chaque stage de backoff nous prendrons la valeur moyenne pour représenter la valeur du backoff qui sera choisi pour le paquet qui va être émis. Ainsi le délai de propagation sur le canal noté D prop est donné par la formule : n 1 D prop = ∑ ( DIFS + 2i CWmin + Tm ) 2 i =o n 1 1 D prop = ( n + 1)( DIFS + Tm ) + CWmin ∑ 2i 2 i =o 2 1 D prop = (n + 1)( DIFS + Tm ) + CWmin (2n+1 − 1) ……………………..4.4 2

Tm représente le temps moyen de propagation d’un paquet sur le médium. Cette valeur est constante lorsque la capacité du médium est la même en tout point. C’est le temps nécessaire pour transmettre les en-têtes MAC, physique et les données du paquet à émettre. Ainsi le délai sur un lien d’un paquet de taille m noté D est : D = R + D prop ………………………………………..4.5

Comme le montre la formule ci-dessus, le délai de transmission dépend de la probabilité de collision entre un nœud émetteur et le récepteur. Si on considère un seul émetteur, ce taux de collision n’est pas le même vers l’ensemble de ces nœuds voisins. Ainsi, le délai est différencié suivant le voisin vers lequel en veut envoyer les donnés. La probabilité de collision peut être estimée en utilisant l’envoi périodique des messages HELLO. Chaque nœud calcule cette probabilité avec la formule suivante : p=

Nombre de paquets HELLO entrés en collision …………………….. 4.6 Nombrede paquets HELLO que l’on devrait recevoir

Le nombre de paquets entrés en collision est le nombre de paquets que l’on devrait recevoir duquel on soustrait le nombre de paquets effectivement reçus durant une période de mesure. Cette estimation n’est toujours pas assez précise, car les paquets HELLO peuvent être influencés par une congestion ou une défaillance des liens que par des collisions. Toute fois, cette problématique n’est pas prise en compte dans cette étude [42]. - 51 -

Chapitre IV

Conception

2.3 Détermination du délai multi sauts Le délai est une métrique additive, autrement dit le délai moyen de bout en bout entre une source s et une destination d noté Ds ,d est égal à la somme des délais Di moyens des liens constituants ce chemin. D s ,d =

∑

i∈[ s , d ]

Di

…......…………………………….. 4.7

3 Intégration dans AODV Pour introduire la qualité de service dans AODV, un contrôle d’admission est nécessaire pour permettre la vérification des conditions de la QoS demandée. L’idée repose sur l’ajout d’un ou plusieurs champs dans les paquets de contrôle. Les informations qui contiennent ces champs seront utilisées pour faciliter le contrôle d’admission effectué lors de l’établissement des routes. Selon le principe de fonctionnement adopté, nous avons modifié le format de deux paquets ; la requête de route RREQ, et les messages HELLO. Dans le contexte de cette étude, nous essayons dans ce qui suit de mettre en œuvre les modifications nécessaires pour que la méthode d’estimation du délai décrite précédemment soit intégrée dans le protocole AODV. Le principe de ces extensions et de fonctionnement du protocole AODV modifié est inspiré du draft [39] de l’IETF. Pour distinguer le protocole AODV standard de l’extension faite dans ce travail, nous avons appelé notre protocole: AODV-D (pour Ad-hoc On-demand Distance Vector with Delay constraints), ou AODV avec contraints délai.

3.1 Extension de la RREQ La requête de route est étendue pour inclure trois nouveaux champs, le premier spécifie le délai maximum demandé à l’application, le deuxième pour la bande passante désirée et le troisième est réservé au délai un saut calculé à la réception de la requête de route. Ces champs seront utilisés pendant la diffusion de la requête de recherche de routes pour effectuer un contrôle d’admission au niveau de chaque nœud intermédiaire. J |R |G | D |U Type Reserved Bande passante désirée Délai max demandé RREQ ID Destination IP Address Destination Sequence Number Originator IP Address Originator Sequence Number

Hop Count Délai un saut calculé

Tab.4.1 : Format du message RREQ dans AODV-D.

- 52 -

Chapitre IV

Conception

3.2 Extension des messages HELLO Les messages HELLO sont étendus pour inclure un nouveau champ, il spécifie la probabilité de collision calculée à l’aide des messages HELLO suivant la formule 4.6 décrite précédemment, cette valeur sera récupérer par la couche MAC lors de l’envoi de ces messages afin de calculer le délai de propagation suivant les formules 4.3 et 4.4. Type

R|A

Reserved Prefix Sz Destination IP Address Destination Sequence Number Originator IP Address Lifetime Probabilité de collision

Hop Count

Tab.4.2 : Format du message HELLO dans AODV-D.

3.3 Mécanisme de routage AODV-D 3.3.1 Découverte des routes Puisque le protocole AODV-D est inspiré du protocole AODV, il garde la plupart de ces mécanismes de fonctionnement avec des modifications pendant la diffusion de la requête de découverte des routes. En plus, pour faciliter le contrôle d’admission effectué lors de la diffusion de RREQ, une approche proactive sera utilisée pour estimer le délai de propagation au niveau de chaque lien actif. En utilisant la diffusion périodique des messages HELLO effectuer par le protocole AODV, chaque nœud déduit alors la valeur de la probabilité de collision au niveau de chaque lien à l’aide de l’équation 4.6 ce qui lui permet de calculer le délai de propagation sur le lien concerné avec les équations 4.3 et 4.4. Une autre valeur sera calculée périodiquement est la bande passante résiduelle (libre) pour chaque nœud à l’aide de l’équation 4.1. Celle-ci sera utilisée lors de la réception d’une RREQ (après la récupération de la bande passante désirée) pour le calcul du délai probablement passé dans la file d’attente du nœud considéré à l’aide de l’équation 4.2. On déduit alors le délai à un saut D par une simple addition avec le délai de propagation suivant l’équation 4.5, le délai un saut D sera marqué dans le champ dédié de la RREQ pour une utilisation dans le contrôle d’admission effectué par le protocole AODV-D Si un nœud source veut communiquer avec un autre nœud qui n’a pas une route valide dans sa table de routage pour cette destination, une procédure de découverte de route est initiée. Le nœud source diffuse d’abord une requête RREQ à travers le réseau, Quand un nœud intermédiaire reçoit une RREQ, il vérifie d’ abord s’il existe une route valide dans la table de routage s’il existe une route il renvoi un RREP vers la source, sinon, avant de retransmettre le message, il effectue un contrôle d’admission pour tester le délai. Celui-ci consiste à comparer la valeur du champ « délai max demandé » de la requête RREQ avec le délai calculé. Si ce dernier est inférieur à celui du message RREQ alors cette valeur sera soustraite de la valeur du RREQ, ensuite le message sera diffusé vers la destination. Sinon la RREQ sera dropé directement par ce nœud intermédiaire. Dans ce cas, la source doit retransmettre une autre RREQ jusqu’à un certain nombre de fois comme le fait le protocole AODV standard (figure 4.3). - 53 -

Chapitre IV

Conception

Fig.4.3- découverte de routes dans AODV-D.

Quand la destination reçoit la RREQ, elle fait le même contrôle, s’il est vérifié, elle envoie une requête RREP en mode unicast vers la source par le chemin inverse pour la validation de la route concernée (figure 4.4), chaque nœud intermédiaire doit mettre à jour sa table de routage. La communication entre la source et la destination peut alors avoir lieu en respectant le délai requis par la source, jusqu’à ce que l’une des extrémités ferme la connexion, ou jusqu’à ce que la route utilisée se brise ou se dégrade.

Fig.4.4 : chemin de RREP.

3.3.2 Maintenance des routes Pour la maintenance des routes, le protocole AODV-D maintient le même mécanisme de que le protocole AODV standard. Les cassures des routes sont détectées grâce à l’envoi périodique des messages HELLO. Si un nœud ne reçoit pas un message HELLO d'un certain voisin durant un intervalle de temps prédéfini, il marque les routes utilisant ce voisin comme invalides et envoie un message d’erreur RERR aux voisins en amont de la route. Seule la source initie de nouveau une procédure de découverte de route après avoir reçu le message d'erreur. L’utilisation des messages HELLO habituels pour l’estimation du délai permet une minimisation du trafic de contrôle destiné généralement à de telles taches. Cela offre deux avantages : d’un coté les routes établies assurent les exigences de QoS en termes de délai de bout en bout. De l’autre coté il n’y aurait pas un trafic supplémentaire surchargeant le réseau, ce qui a une influence sur le délai à cause de l’augmentation de la probabilité de collisions et des interférences. L’organigramme d’exécution du protocole AODV-D est présenté dans la figure 4.5. - 54 -

Chapitre IV

Conception

Fig. 4.5 - L'organigramme d'exécution de AODV-D.

3.4 Limitations La partie touchée par les modifications concerne seulement la phase de découverte de routes c'est-à-dire la diffusion de la requête RREQ (voire figure 4.6). En effet, la solution présentée dans la section précédente permet au protocole AODV-D d’assurer un certain degré de qualité de service de telle sorte que toutes les routes établies respectent la métrique délai de bout en bout. Cependant aucune garantie n’est fournie pendant la transmission des paquets de données. Si le délai augmente sur un chemin après la validation de ce lui ci, aucun mécanisme de détection et de maintenance de telles situations n’est fournie. Autrement dit, la QoS offerte est relâchée (soft QoS). - 55 -

Chapitre IV

Conception

CA : contrôle d’admission.

Fig. 4.6 : L’organigramme d’exécution de RREQ pour AODV-D. - 56 -

Chapitre IV

Conception

4 Diagramme de séquence La figure 4.7 illustre le diagramme de séquence qui résume les principales opérations effectuées par le protocole AODV-D. Il montre également l’enchainement des principales étapes par lesquelles doit passer AODV-D pendant la phase de découverte de routes et l’emplacement du contrôle d’admission effectué par les nœuds intermédiaires et la destination.

Fig. 4.7 : Diagramme de séquence d’AODV-D.

5 Diagramme de classes La figure 4.8 montre le diagramme de classes du protocole AODV-D [46]. Notons ici que le diagramme a gardé la même structure que celui d’AODV. Les modifications effectuées concerne certains attributs et opérations et non les classes eux même ; On n’a pas ajouté des classe ni éliminé d’autres. La conception du protocole AODV-D a été faite autour de la classe pivot AODV. C’est la classe de tous les objets participant à l’exécution du protocole sur les nœuds. Ces objets occupent la couche réseau dans chaque nœud. La classe AODV utilise les objets des classes: BroadcastTimer, HelloTimer, NeighborTimer, RouteCacheTimer, LocalRepairTimer, aodv_rtable et aodv_rqueue pour maintenir les états (valeurs de ces attributs), et c’est au niveau de cette classe que les modifications du protocole AODV sont introduites en ajoutant quelques fonctionnalités concernant le contrôle d’admission qui vérifie la métrique de QoS considérée. Les composants touchés par les modifications sont marquées en gras dans la figure 4.8. Le point d’entrée de la classe AODV est la méthode recv( ). A partir de cette méthode on fait appel à toutes les autres fonctions de la classe AODV. Parmi eux, la fonction recvAODV( ), celle-ci fait appel la fonction recvrequest( ), et c’est exactement ici que le contrôle d’admission est effectué. - 57 -

Chapitre IV

Conception

Fig. 4.8 : Diagramme de classes d’AODV-D. - 58 -

Chapitre IV

Conception

Conclusion Ce présent chapitre décrits les spécifications d’une solution qui permet d'étendre le protocole AODV pour garantir de la QoS en termes de délai de bout en bout. Il détaille également le principe de fonctionnement du nouveau protocole et la méthode d'estimation du délai utilisée. Ce chapitre a été dédié à la conception de AODV-D. nous y avons abordé les principaux diagrammes UML qui montrent les relations entre les différentes classes du protocole. Ces classes sont en grande partie, basées sur les classes AODV. Le prochain chapitre sera consacré aux détails de l’implémentation du protocole AODV-D modifié sous le simulateur NS-2 (network simulator 2).

- 59 -

Chapitre V

Implémentation

Chapitre V

Implémentation

- 60 -

Chapitre V

Implémentation

Implémentation 1 Introduction Avec l’évolution des réseaux sans fil et l’élaboration de plusieurs normes pour ces réseaux, et avec le besoin des simulations dans le contexte de l’évaluation des performances, de nombreux simulateurs des réseaux ont été développés. Les simulateurs les plus connus sont : NS-2 (Network Simulator 2), OPNET et GloMoSim/Qualnet [15]. Dans le cadre de notre étude, nous avons choisi le simulateur NS-2 (voir annexe A) développé à Lawrence Berkeley National Laboratory (LBNL). C’est le simulateur de réseaux le plus utilisé par la communauté des chercheurs dans les MANETs. NS-2 offre plusieurs avantages ; nous pouvons citer [38]:
Il est open source et gratuit. Il englobe les contributions de nombreux chercheurs à travers le monde.
Il peut être étendu à d'autres modèles grâce à sa conception orientée objet et son implémentation en C++.
Il est riche en modèles et en protocoles pour les environnements filaires et mobiles.
Il fournit des résultats fiables sous forme de fichier trace riche en informations que l'utilisateur peut exploiter.
Il est bien documenté. Les ressources bibliographiques relatives à sa conception et son implémentation sont très nombreuses.
Il est utilisé dans plus de 43% des travaux de recherche dans le domaine du routage dans les réseaux MANETs.
Il inclut les implémentations de quatre protocoles de routage dans les MANETs à savoir : AODV, DSDV, DSR et TORA. En plus de ces avantages, l’approche évolutive que nous avons choisie dans cette étude justifie notre choix de NS-2, car une implémentation du protocole AODV existe déjà, il suffit donc d’y apporter les modifications nécessaires qui permettent d’intégrer la QoS dans AODV en appliquant la méthode décrite dans le quatrième chapitre. Ce présent chapitre est consacré aux détails de l’implémentation du protocole AODV-D sous NS-2. Pour ce faire, nous présentons d’abord les différents fichiers et modules concernés par les modifications. Ensuite nous décrivons les modifications nécessaires du protocole IEEE 802.11 pour intégrer la méthode d’estimation du délai adoptée, et enfin, les nouvelles méthodes ajoutées, les changements dans le format des paquets, et le mécanisme de fonctionnement de l’agent de routage AODV-D.

2 Présentation d’AODV sous NS-2 L’implémentation du protocole AODV sous NS-2 a été faite autour des fichiers sources situés dans le répertoire : \cygwin\...\ns-allinone-2.33\ns-2.33\aodv. Les fichiers concernés sont les suivants : • aodv.h : c’est le fichier principal (header) dans lequel sont définis tous les timers (temporisateurs) nécessaires, et l’agent de routage qui exécute les fonctionnalités du protocole. • aodv.cc : dans lequel tous les timers, les Tclhooks (liens entre les composants c++ et ceux d’OTcl) sont implémentés, ainsi que l’agent de routage et ces fonctionnalités. - 61 -

Chapitre V

Implémentation

• aodv_packet.h : ici sont déclarés tous les types de paquets qu’utilise AODV dans les échanges entre les nœuds du réseau. • aodv_rtable.h : le fichier header où la table de routage est déclarée. • aodv_rtable.cc : implémentation de la table de routage. • aodv_rqueue.h : ce fichier définit la file d’attente utilisée par le protocole de routage et la déclaration des différentes fonctions et méthodes utilisées qui servent à la manipulation de cette file. • aodv_rqueue.cc : il contient l’implémentation de la file et de fonctionnalités. • aodv_logs.cc : destiné à la gestion de la connectivité locale entre les nœuds du réseau. Pour plus de détails d’implémentation du protocole AODV sous NS-2 et la relations entre ces fichiers et avec d’autres fichiers ainsi que les différentes classes et méthodes utilisées, voir [45].

3 Présentation du protocole MAC-802.11 sous NS-2 Le simulateur NS-2 implémente également le protocole Mac_802.11 qui sera utilisé dans cette étude au niveau MAC. L’implémentation de ce dernier est faite dans le répertoire /ns.2.33/mac autour des fichiers suivant : • mac-802_11.h : c’est le fichier header dans lequel la classe de base Mac802_11 est déclarée ainsi que tous ces composants et attributs nécessaires au fonctionnement du protocole. il définit aussi les formats de paquets de contrôle utilisés. • mac-802_11.cc : dans lequel sont implémentées toutes les fonctionnalités du protocole • mac-timers.h : dans lequel sont déclarés tous les Timers utilisés. • mac-timers.cc : ici les Timers déclarés dans mac-timers.h sont implémentés. Dans ce qui suit, nous décrivons les modifications nécessaires apportées à ces fichiers pour implémenter la méthode d’estimation du délai décrite précédemment.

4 Structure des nœuds AODV et AODV-D sous NS-2 La classe Node est la classe de base qui permet l’instanciation des objets nœuds dans le simulateur NS-2. MobileNode héritée de la classe Node permet la création des nœuds mobiles. Elle offre les fonctionnalités nécessaires au fonctionnement de ce type de nœuds comme le mouvement et la possibilité d’envoyer et de recevoir des paquets dans un canal de transmission. Les composants de la mobilité tels que le mouvement, la mise à jour périodique de la position du nœud, et le maintien des frontières de la topologie sont implémentés en C++. Tandis que les composants réseau (MAC, LL, Classifier ...) plantés dans le nœud sont implémentés en OTcl. La figure 5.1 montre que la structure du nœud AODV-D est légèrement différente de celle utilisée pour AODV standard. Les principales différences sont : • couche MAC : le protocole 802.11 intègre un mécanisme d’estimation du délai afin de l’utiliser par l’agent de routage AODV-D alors que le standard ne procède pas cette fonctionnalité. • couche réseau : la nouvelle structure a comme entée l’agent de routage AODV-D au lieu de l’agent AODV standard, la différence entre les deux est que le premier effectue un contrôle d’admission pour les requêtes de route entrantes afin de vérifier la métrique délai de bout en bout exigé par l’application. - 62 -

Chapitre V

Implémentation

• Couche application : dans le cas AODV-D, l’agent applicatif est capable d’initialiser les besoins en QoS. Ceci est le cas général. Dans notre cas, nous avons procédé comme dans la section 7 de ce chapitre.

Fig. 5.1 : structure des nœuds AODV et AODV-D sous NS-2.

5 Implémentation d’AODV-D sous NS-2 Dans cette partie, nous allons discuter les détails d’implémentation du protocole AODV-D sous le simulateur NS-2. Il s’agit d’une extension du protocole AODV tout en gardant le protocole IEEE 802.11 au niveau MAC. Afin de faciliter cette phase, nous avons gardé les mêmes noms des classes et des fichiers. L’extension étudiée consiste en l’intégration de la QoS dans AODV en termes du délai de bout en bout, une méthode d’estimation du délai sera intégrée au niveau de la couche MAC en ajoutant les modifications nécessaires au protocole MAC_802.11.

- 63 -

Chapitre V

Implémentation

5.1 Estimation du délai au niveau de la couche MAC L’estimation du délai est faite au niveau de la couche MAC, car elle est plus simple et pertinente. La prise en compte des interférences et des flux voisins ne nécessite pas l’ajout d’un trafic de contrôle supplémentaire ce qui est en opposition avec la nature réactive du protocole AODV. Dans la méthode d’estimation adoptée nous avons décomposé le délai à un saut en deux parties : le délai dans la file d’attente noté R et le délai de propagation noté D prop . Pour le premier, nous l’avons calculé avec l’équation 4.2. Cette équation dépend de deux paramètres : Le premier est le paramètre λ qui représente le débit désiré par l’application qui est explicitement fourni lors de la phase de requête de route avec QoS. Le deuxième est Le paramètre µ qui représente la bande passante libre (appelée aussi résiduelle) autour de ce nœud. Celle ci sera calculée à chaque période T. Pour le deuxième, il dépend de la probabilité de collision au niveau du nœud récepteur, celle-ci est calculée périodiquement avec l’équation 4.5. Ensuite, nous calculons le nombre de retransmissions possible avec l’équation 4.3, enfin en déduit le délai de propagation D prop par l’equation4.4. Le délai un saut est obtenu alors par une simple addition suivant la formule 4.7. Dans ce qui suit, nous décrivons les modifications nécessaires dans le protocole IEEE 802.11 qui permettent l’estimation du délai un saut à l’aide de l’implémentation des équations décrites précédemment.

5.1.1 Estimation de la bande passante libre sur un nœud Pour estimer la bande passante libre, des modifications dans le fichier mac_802.11.cc sont nécessaires, plus précisément la classe Mac.802_11. La méthode adoptée pour calculer la bande passante libre est basée sur le calcul du pourcentage du temps libre autour d’un nœud. Cette information n’est pas disponible dans la base des informations de la classe MAC802.11 originale. L’idée est simple, il s’agit d’ajouter un temporisateur (Timer), à chaque période (T) il teste l’objet MAC802.11. Le temporisateur est déclaré dans le fichier mac_timers.h et implémenté dans le fichier mac_timers.cc comme le montre le code suivant : Listing 5.1 : Implémentation du Timer. Void bandwidthTimer::handle(Event *) { busy_ = 0; paused_ = 0; stime = 0.0; rtime = 0.0; mac->bandwidthHandler(); T = (MinHelloInterval + ((MaxHelloInterval - MinHelloInterval) * Random::uniform()))/1; assert(T>=0); rtime = T; Scheduler::instance().schedule(this, &intr,rtime); }

- 64 -

Chapitre V

Implémentation

Le temporisateur T est choisi aléatoirement entre les deux valeurs : MinHelloInterval et définis par le protocole AODV pour envoyer les messages HELLO. A l’expiration du temporisateur, la fonction bandwidthHandler()(dans laquelle nous avons fait la mise à jour de la bande passante libre) est appelée. Un objet MAC802.11 est soit en émission, soit en réception sinon il est libre. La classe MAC802.11 originale implémente deux méthodes pour la mise à jour de son état. A chaque envoi (données, RTS, CTS, ACK) la méthode SetTxState est appelée, et à chaque réception c’est la méthode SetRxState qui est appelée. On peut déduire le taux d’occupation du medium par le nœud en introduisant deux variables, la première représente le temps de toutes les transmissions (Send_time) et la deuxième représente celui de toutes les réceptions (Rcv_time) pendant la fenêtre de temps (T). La mise à jour des variables (Send_time) et (Rcv_time) est introduite dans les méthodes SetRxState et SetTxState respectivement dans le fichier \ns2.33\mac\mac_802.11.cc (voir listing5.2): MaxHelloInterval

Listing 5.2 : mise à jour des temps d’émission et de réception inline void Mac802_11::setRxState(MacState newState) { rx_state_ = newState; checkBackoffTimer(); double time=0.0;

//le temps de la réception.

if (rx_state_ == MAC_RECV) { time = txtime(pktRx_); } else if

(rx_state_ == MAC_ACK)

{ time = txtime(phymib_.getACKlen(),basicRate_); } else if (rx_state_ == MAC_RTS) { time = txtime(phymib_.getRTSlen(),basicRate_); } else if

(rx_state_ == MAC_CTS)

{ time = txtime(phymib_.getCTSlen(),basicRate_); } Rcv_time += time; //mise à jour de Rcv_time. } inline void Mac802_11::setTxState(MacState newState) { tx_state_ = newState; checkBackoffTimer(); double time = 0.0; //le temps de la réception. if (tx_state_ == MAC_SEND) { time = txtime(pktTx_); } else if

(tx_state_ == MAC_ACK)

- 65 -

Chapitre V

Implémentation

{ time = txtime(phymib_.getACKlen(),basicRate_); } else if (tx_state_ ==MAC_RTS) { time = txtime(phymib_.getRTSlen(),basicRate_); } else if (tx_state_ == MAC_CTS) { time = txtime(phymib_.getCTSlen(),basicRate_); } Send_time += time; //mise à jour de Send_time. }

Une fois Rcv_time et Send_time connus, nous pouvons calculer le taux d’occupation du médium (Busy_time ) par la relation suivante : Busy_time = Rcv_time + Send_time/T Le pourcentage du temps libre (free_time) sera égal à (1- Busy_time). La bande passante libre autour d’un nœud est égale la capacité du médium Cmax multipliée par le pourcentage du temps libre free_time (équation 4.1). Pour ce faire, nous avons introduit une nouvelle méthode à la classe mac_802.11 qui fait un calcule périodique de la bande passante libre (paramètre µ ) ainsi que la mise à jour de Rcv_time et Send_time. La méthode est bandwidthHandler(), son code est donné dans listing 5.3 : Listing 5.3 : mise à jour de la bande passante libre. void Mac802_11 :: bandwidthHandler() { busy_time = (Rcv_time+Send_time)/mhbwTimer_.T; free_time = (1-busy_time); freebw_ = free_time * dataRate_ ;//la bande passante libre. Rcv_time = Send_time = 0.0; }

5.1.2 Récupération du paramètre λ Le paramètre λ qui représente la bande passante désirée, est fourni avec la requête RREQ. Pour le récupérer au niveau MAC, nous avons autorisé le protocole 802.11 d’accéder directement à l’entête du paquet RREQ. La méthode RecvDADA() qui est dans le fichier \ns-2.33\mac\mac_802.11.cc est le point de service qui passe le paquet reçu par la couche MAC à la couche réseau, et c’est ici que nous récupérons la bande passante désirée ( λ ) afin de calculer le délai dans la file d’attente R .

- 66 -

Chapitre V

Implémentation

5.1.3 Le délai dans la file d’attente R Une fois les deux paramètres λ et µ connus, on peut déduire le délai dans la file d’attente R avec l’équation 4.2. Pour ce faire nous avons ajouté une nouvelle variable Q_delay à la classe Mac_802.11 (représente la valeur de R) qui sera calculée au niveau de la méthode RecvDADA() à chaque fois qu’on reçoit un paquet de type RREQ comme le montre le listing 5.4 : Listing 5.4 : Code permettant l’estimation du délai dans la file. void Mac802_11::recvDATA(Packet *p) { struct hdr_cmn *ch = HDR_CMN(p); ……………………….. double free, req_bw, rho, q ; struct hdr_aodv *ah_= HDR_AODV(p); struct hdr_aodv_request *rq_= HDR_AODV_REQUEST(p); if (ch->ptype() == PT_AODV) { if (ah_->ah_type == AODVTYPE_RREQ) { req_bw = rq_->bw_req; //récupération de paramètre λ de la RREQ. free = freebw_; // la bande passante libre (le parameter µ rho = req_bw/free; q = 50.0; // la taille de la file. if (rho < 1.0) { Q_delay = (rho*(1.0-((q+1.0)*pow(rho,q))+(q*pow(rho,q+1.0)))) /((1.0-rho)* free *(1.0 - pow(rho,q))) ; //le délai R dans la file d’attente avec la formule 4.2. } } }

5.1.4 Estimation du délai de propagation La deuxième partie du délai un saut est le délai de propagation qui est le délai s’écoulant entre le moment où le paquet est reçu par la couche MAC jusqu’à la réception de l’acquittement correspondant par le nœud récepteur y compris toutes les retransmissions possibles dues aux collisions. La méthode qu’on a choisie est basée sur l’estimation de la probabilité de collision à l’aide de l’envoi périodique des messages HELLO. L’implémentation de cette méthode est faite au niveau de la couche réseau par le protocole AODV. Elle sera discutée dans les sections suivantes. Le délai de propagation est calculé au niveau de la couche MAC. En utilisant l’envoi périodique des messages HELLO pour passer la valeur de la probabilité de collision à la couche Mac, cela est fait au niveau de la méthode sendData() dans le fichier mac_802.11.cc juste avant l’envoi du paquet HELLO. Cette valeur sera enregistrée dans la variable p_collision ajoutée à la classe Mac_802.11 comme le montre le listing 5.5 :

- 67 -

Chapitre V

Implémentation

Listing 5.5 : Récupération de la probabilité de collision. void Mac802_11::sendDATA(Packet *p) { hdr_cmn* ch = HDR_CMN(p); struct hdr_mac802_11* dh = HDR_MAC802_11(p); ………………………………………………………… struct hdr_aodv *ah_= HDR_AODV(p); struct hdr_aodv_reply *rp_ = HDR_AODV_REPLY(p); if(ch->ptype() == PT_AODV) { if(ah_->ah_type == AODVTYPE_HELLO) { p_collision = rp_->collision;///récupération de la probabilité de collision des messages HELLO. } } ………………………………………………………… pktTx_ = p; }

Une fois la probabilité de collision connue on peut calculer le délai de probagation avec les equations 4.3 et 4.4. Pour implémenter ces équations nous avons ajouté une nouvelle variable D_prop_estimation à la class Mac_802.11 dans le fichier\ns-2.33\mac\mac_802.11.cc, la mis à jour de la valeur de cette variable sera faite au niveau de la méthode RecvDADA() à chaque fois que celle-ci est invoquée (listing 5.6) : Listing 5.6 : Estimation du délai de propagation. void Mac802_11::recvDATA(Packet *p) Double N ; ……………………………………………………………………… if (p_collision > 0.0) { nbr_retransmit=(5.0*pow(p_collision,8.0)-7.0*(pow(p_collision,7.0)) +p_collision)/(1.0- p_collision); //nombre de retransmission calculé avec l’équation 4.3 if (nbr_retransmit <= 0.0) { N = 0.0 ; } else { N = floor(nbr_retransmit); } } D_prop_estimation =(N+1.0)*(phymib_.getDIFS()+txtime(ch->size(),dataRate_)) +(0.5*phymib_.getCWMin()*phymib_.getSlotTime()*(pow(2.0,N+1.0)-1.0)); // délai de propagation calculé avec l’équation 4.4. ……………………………………………………………………….

- 68 -

Chapitre V

Implémentation

5.1.5 Le délai à un saut Dans la même fonction (RecvDADA()), avant de passer le paquet à la couche réseau (le protocole AODV-D dans notre cas), nous calculons le délai un saut par une simple addition entre les deux variables D_prop_estimation et Q_delay, nous le recopions en suite dans le paquet RREQ afin de l’utiliser dans le contrôle d’admission par le protocole AODV-D (listing 5.7) : Listing 5.7 : copie du délai un saut dans la RREQ . ………………………… rq_->one_hop_delay = Q_delay

+ D_prop_estimation;

……………………….. uptarget_->recv(p, (Handler*) 0); }

6 Les modifications au niveau de la couche réseau Après avoir terminé avec l’estimation du délai au niveau MAC, passons maintenant à la couche réseau. C’est à ce niveau que l’agent de routage AODV exécute ces différentes fonctionnalités. Pour simplifier l’implémentation des modifications nous avons gardé le même nom de l’agent et les mêmes fonctionnalités (la gestion des paquets de contrôle, de la table de routage…).

6.1 Le format du paquet RREQ dans AODV-D Trois champs sont ajoutés au format du paquet RREQ : Le premier représente le délai_max à ne pas dépasser (exigé par l’application), le deuxième concerne la bande passante désirée (le paramètre λ ), le dernier est réservé au délai un saut calculé au niveau de la couche MAC. La modification du paquet est faite dans le fichier aodv_packet.h qui contient toutes les déclarations des paquets AODV (listing 5.8): Listing 5.8 : extension du paquet RREQ . Struct hdr_aodv_request { u_int8_t rq_type; // u_int8_t reserved[2]; u_int8_t rq_hop_count; u_int32_t rq_bcast_id; nsaddr_t rq_dst; u_int32_t rq_dst_seqno; nsaddr_t rq_src; u_int32_t rq_src_seqno; double rq_timestamp; latency double double double MAC }

max_delay; bw_req; one_hop_delay;

Packet Type // // // // // // // //

Hop Count Broadcast ID Destination IP Address Destination Sequence Number Source IP Address Source Sequence Number when REQUEST sent; used to compute route discovery

// délai demandé par l'application // bande passante demandée //le délai un saut calculé au niveau

- 69 -

Chapitre V

Implémentation

6.2 Le format du paquet RREP dans AODV-D Le format des paquets RREP a été modifié en ajoutant un champ qui est réservé à la probabilité de collision (voir listing5.9). Ce champ sera rempli lors de l’envoi des messages HELLO (notons ici que les messages HELLO utilisent le format des paquets RREQ) : Listing 5.9 : extension du paquet RREP. struct hdr_aodv_reply { u_int8_t rp_type; u_int8_t reserved[2]; u_int8_t rp_hop_count; nsaddr_t rp_dst; u_int32_t rp_dst_seqno; nsaddr_t rp_src; double rp_lifetime; double collision; double rp_timestamp; //used to

// Packet Type // // // //

Hop Count Destination IP Address Destination Sequence Number Source IP Address // Lifetime // probabilité de collision // when corresponding REQ sent; compute route discovery latency

6.3 Contrôle d’admission L’agent de routage AODV reçoit les paquets provenant des couches supérieures ou inférieurs par la méthode recv( ) située dans le fichier aodv.cc. Si le paquet est venu de la couche MAC. L’agent de routage va tester le type de paquet avec la méthode recvAODV(p) située toujours dans le même fichier. Si ce paquet est une RREQ, la méthode recvRequest(p) est appelée. Selon le cas, le paquet sera ignoré en appelant la méthode drop (p) ou bien rediffusé par la méthode forward( ) vers les voisins. Les différentes méthodes appelées lors de la découverte de routes par le protocole AODV-D sont présentées dans la figure 5.2 [46]. Dans AODV standard la requête de route est dropée par un nœud pour deux raisons : soit le nœud est la source elle-même c'est-à-dire qu’elle a reçu sa propre requête, Soit le paquet est déjà passé par ce nœud. Une troisième raison est ajoutée dans AODV-D, il s’agit d’un contrôle d’admission qui teste la métrique délai, puisque les paramètres de QoS (délai max et bande passante désirée) sont fournis avec la RREQ, le contrôle d’admission sera effectué au niveau de la méthode recvRequest() en introduit les modifications nécessaires. Ces modifications consistent à comparer le champ délai_max (le délai demandé par l’application) du paquet RREQ avec le délai un saut récupéré de la couche MAC. Si ce dernier est supérieur au délai max, le paquet sera dropé, sinon on fait une mise à jour du champ délai max par une soustraction du délai calculé du délai max (listing5.10).

- 70 -

Chapitre V

Implémentation

Fig.5.2 : les méthodes appelées par AODV-D (découverte de route). Listing 5.10 : contrôle d’admission. void AODV::recvRequest(Packet *p) { struct hdr_ip *ih = HDR_IP(p); struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p); aodv_rt_entry *rt; /* * Drop if: * - I'm the source * - I recently heard this request. * - le délai n'est pas suffisant. (Exigences de QoS). */ if(rq->rq_src == index) { #ifdef DEBUG fprintf(stderr, "%s: got my own REQUEST\n", __FUNCTION__); #endif // DEBUG Packet::free(p); return; } if (id_lookup(rq->rq_src, rq->rq_bcast_id)) { #ifdef DEBUG fprintf(stderr, "%s: discarding request\n", __FUNCTION__); #endif // DEBUG

- 71 -

Chapitre V

Implémentation

Packet::free(p); return; } /*controle d’admission*/ if (rq->max_delay >= rq->one_hop_delay) { rq->max_delay = rq->max_delay - rq->one_hop_delay; } else { #ifdef DEBUG fprintf(stderr, "%s: délai insuffisant\n", __FUNCTION__); #endif // DEBUG Packet::free(p); return; }

…………. forward((aodv_rt_entry*) 0, p, DELAY); }

6.4 La probabilité de collision La probabilité de collision est estimée à l’aide de l’envoi périodique des messages HELLO suivant l’équation 4.5. Pour ce faire, nous avons utilisé les méthodes existant par le protocole AODV pour la gestion de voisinage :nb_insert(), nb_delete() et nb_purge()q,en ajoutant les quatre variables suivantes à la classe AODV : • nbr_neighbors : pour compter le nombre de voisins actifs, à chaque fois que la fonction nb_insert()est appelée on incrémente de 1 et à chaque fois que la méthode nb_delete() est appelée en décrémente de 1. • nbr_ph_rsv : pour le nombre de paquets HELLO effectivement reçus pendant la période mesure, à chaque fois la méthode revcHello() est appelée on incrémente de 1. • nbr_ph_must_rsv : c’est le nombre de paquets HELLO que l’on devra reçus pendant la période de mesure, qui est égale à : nbr_neighbors * la période de mesure * le temps séparant deux messages HELLO (on a choisi la valeur MaxHelloInterval pour s’assurer que tous les voisins ont envoyé leurs messages HELLO). la mis à jour de la valeur de cette variable est faite au niveau de la méthode nb_purge()qui est appelée périodiquement. • p_coll : au niveau de la même méthode, on calcule la probabilité de collision avec l’équation 4.6 comme le montre le code donné dans le listing 5.11 : Listing 5.11 : mis à jour de la probabilité de collision. void AODV::nb_purge() { AODV_Neighbor *nb = nbhead.lh_first; AODV_Neighbor *nbn; double now = CURRENT_TIME;

- 72 -

Chapitre V

Implémentation

if (nbr_neighbors >= 1.0){ nbr_ph_must_rsv = nbr_neighbors*MaxHelloInterval*3;//3 seconde (période de mesure). p_coll = (nbr_ph_must_rsv - nbr_ph_rsv)/nbr_ph_must_rsv; //calcule de la probabilité de collision avec l’équation 4.6. nbr_ph_rsv = 0.0; for(; nb; nb = nbn) { nbn = nb->nb_link.le_next; if(nb->nb_expire <= now) { nb_delete(nb->nb_addr); } } }

7 Les exigences de QoS Dans le cas général, les exigences de QoS sont fournies par l’application. Selon le type de l’application, les demandes sont multiples (délai, bande passante, gigue…). Ceci nécessite la création d’un agent applicatif qui est capable d’envoyer des paquets exigeant une QoS. Ces exigences seront récupérées par l’agent de routage avec QoS afin de les utiliser dans les différentes phases d’établissement des routes. Dans notre cas, nous supposons que le trafic circulant à travers le réseau est de même type (VoIP par exemple) et exige donc les mêmes contraintes de QoS. En effet, nous n’avons pas créé un agent applicatif exigeant la QoS, mais ces derniers seront initialisés directement par l’agent de routage AODV-D, l’objectif étant de tester l’approche d’estimation du délai choisie et le mécanisme de routage avec QoS intégré dans le protocole AODV. Pour ce faire, nous avons ajouté trois variables à la classe AODV : • req_bandwitdh et req_delay : Ces deux variables servent à spécifier les exigences en bande passante et/ou délai respectivement. Cela est fait au niveau de la méthode sendRequest()en remplissant les deux champs réservés par les valeurs de ces deux variables. • QoS_factor : cette variable est utilisée pour indiquer au protocole AODV si le contrôle d’admission sera effectué ou non ; si elle est égale à 1, le contrôle est exécuté, sinon il sera ignoré. Pour une meilleure flexibilité, nous avons choisi d’initialiser ces variables à partir de l’interface Tcl. Cela est fait par l’utilisation de la fonction bind()qui sert à autoriser l’accès au variables C++ via Tcl, en ajoutant les lignes suivantes au constructeur de la classe AODV dans le fichier aodv.cc (listing 5.12) : Listing 5.12 : autoriser l’accès au paramètre de QoS via l’interface Tcl. Mac802_11::Mac802_11() : Mac(), phymib_(this), macmib_(this), mhIF_(this), mhNav_(this), {

…………………………………… bind("req_bandwitdh",&req_bandwitdh); bind("req_delay",&req_delay); bind("QoS_factor",&QoS_factor);

…………………………………… }

- 73 -

Chapitre V

Implémentation

Pour initialiser ces variables il suffit d’ajouter les commandes suivantes dans notre script Tcl (listing 5.13): Listing 5.13 : commandes Tcl pour initialiser les paramètres de QoS. Agent/AODV set QoS_factor “valeur souhaitée” Agent/AODV set req_bandwitdh Agent/AODV set req_delay

Après avoir terminé avec les modifications nécessaires dans le code, une recompilation de NS-2 est nécessaire, cela est fait par la commande make : Une fois cela est fait sans erreurs, le protocole AODV-D peut être utilisé dans des simulations afin de vérifier les résultats et les comparer avec celles du protocole AODV standard.

Conclusion Ce chapitre a été consacré aux détails de l’implémentation du protocole AODV-D, il donne d’abord une présentation globale de la structure du protocole AODV sous Network Simulator 2. Il discute ensuite les modifications apportées à ce protocole dans le but d’introduire la qualité de service dans ce protocole en terme de délai de bout en bout. Enfin, il introduit une description des modifications apportées au protocole IEEE 802.11 utilisé au niveau MAC afin d’implémenter la méthode d’estimation du délai adoptée dans cette étude qui est nécessaire pour effectuer un contrôle d’admission par AODV-D. Dans le chapitre suivant, nous allons décrire une série de simulations réalisées à l’aide du simulateur NS-2 dans le but d’évaluer les performances du protocole AODV-D, et de le comparer avec AODV standard afin d’analyser les avantages et les inconvénients de cette extension.

- 74 -

Chapitre VI

Simulation et discussion des résultats

Chapitre VI

Simulation et Discussion des Résultats

75

Chapitre VI

Simulation et discussion des résultats

Simulation et Discussion des Résultats 1 Introduction Dans les deux chapitres précédents, nous avons développé un protocole de routage avec QoS dans les réseaux mobiles ad hoc. Il s’agit d’une extension du protocole AODV qui le rend capable d’assurer l’établissement des routes qui satisfont la contrainte de délai de bout en bout dans le but d’améliorer les performances des applications sensibles à cette métrique. Afin de valider et d’évaluer le mécanisme de routage avec QoS mis en place, l’implémentation des modifications apportées au protocole AODV a été réalisée sous le simulateur NS-2. Nous avons utilisé la version 2.33 installée sous Cygwin (un émulateur Unix sous Windows XP). Le choix de ce dernier est motivé par ces caractéristiques citées dans le chapitre précédent. Dans ce chapitre, nous allons présenter une série de simulations réalisées à l’aide du simulateur NS-2. Les objectifs de ces simulations sont les suivants : • Evaluer les performances du protocole AODV-D selon certains paramètres de mesure ; • Comparer les deux protocoles AODV et AODV-D ; • Conclure l’impact des modifications apportées au protocole AODV ainsi que les avantages et inconvénients de la solution.

2 Intérêt et nécessité de la simulation L'évaluation de performances des protocoles de routage peut se faire en utilisant trois techniques, à savoir : la méthode analytique, les mesures, et enfin la simulation. Le recours à la simulation présente de nombreux avantages. En effet, elle est plus rapide, moins coûteuse en ressources, répétable et permettant d'isoler des paramètres qui peuvent parfois affecter les performances. De plus, il existe des scénarios très difficiles à étudier dans la réalité [20].

3 Modèle de simulation Le modèle de simulation précise les paramètres de simulation à utiliser dans l'environnement de simulation. Ces paramètres sont offerts par le simulateur NS-2 et sont paramétrables via les scripts Tcl. Le simulateur NS-2 implémente les différentes couches nécessaires (application, transport, routage, MAC et physique) pour la simulation d’un réseau ad hoc. Le tableau 6.1 résume les différents paramètres utilisés dans les simulations.

76

Chapitre VI

Simulation et discussion des résultats

Paramètres

Valeurs

Protocole de routage Modèle de propagation Couche MAC Portée de transmission Capacité du canal Trafic d'application Taille des paquets Temps de simulation Surface de simulation

AODV /AODV-D Two-ray ground 802.11/DCF avec CSMA/CA 250 mètres 5.5 Mbps CBR (Continuous Bit Rate) 1000 octets 40 secondes 1000*1000 m²

Tab. 6.1. Paramètres de simulation utilisés.

3.1 Modèle de trafic Puisque le but de nos simulations est d’analyser les propriétés de l’extension du protocole AODV, nous avons choisi que les sources de trafics soient à débit constant CBR (Constant Bit Rate). Le trafic entre les nœuds est généré en initialisant des connexions de trafics de type CBR qui commencent à des instants fixés via le script de simulation comme le montre le tableau 6.2. La taille des paquets de données est de 1000 octets. Nous n’avons pas employé des sources de trafic TCP par exemple parce que TCP offre une charge conforme à l’état du réseau, c'est-à-dire, le trafic TCP change les temps auquel il envoie des paquets en se basant sur sa perception de la capacité du réseau de délivrer ces paquets [17]. Le schéma des piles protocolaires mis en place pour cette série de simulation est présenté dans la figure 6.1. Application

CBR

Transport

UDP

Routage

MAC

AODV

AODV-D

Mac_802.11 Fig 6.1 : Pile protocolaire mise en place 77

Chapitre VI

Simulation et discussion des résultats

4 Métriques de simulation mesurées Les simulations sont faites par rapport à trois paramètres, dans le but de tester le protocole sur différents aspects. Ces paramètres sont : le délai de bout en bout, la gigue et le taux de perte de paquets. Nous avons choisi ces trois derniers car ils sont les plus influents sur la qualité de la VoIP comme nous l’avons vu dans le chapitre 3 (section5.1). Cela nous montre une vision globale sur les améliorations possibles apportées à cette application par le nouveau mécanisme de routage avec QoS mis en place dans cette étude. Les trois métriques mesurées sont les suivantes : • Le délai de bout en bout (End to End Delay) : est le temps qui sépare le moment d'envoi 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 de bout en bout par rapport à tous les paquets générés pendant la simulation, puis nous calculons la moyenne. Cette métrique représente l'efficacité du protocole en termes de temps de réponse et en termes du choix des chemins optimaux (moins de nœuds de congestion et plus de stabilité) [20]. • La gigue (jitter) : représente la variation du délai d’acheminement des paquets entre la source et la destination. Elle est obtenue en calculant la différence entre le délai du paquet N et le délai du paquet N+1. Cette métrique nous permet de connaitre la stabilité des connexions établies à travers le réseau au cours du temps, et l’impact de la politique utilisée par le protocole de routage pour le choix de la route sur cette stabilité. • Le taux de perte de paquets : c’est le rapport entre le nombre de paquets perdus (par toutes les destinations du trafic) et le nombre de paquets émis (par toutes les sources du trafic) [20]. La métrique opposée au taux de perte de paquets est le taux de délivrance des paquets PDR (Packet Delivery Ratio) : c’est le rapport entre le nombre de paquets reçus et le nombre de paquets émis. 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ées envoyés.

5 Scénario de simulation Afin de présenter le nouveau mécanisme de sélection des route effectué par le protocole AODV-D et l’effet de celui-ci sur la qualité de service demandée par le trafic circulant à travers le réseau, nous avons mis en place le scénario présenté dans la figure 6.2. Ce dernier nous permet également de le comparer avec le mécanisme d’établissement des routes par AODV standard. Pour ce faire, nous avons procédé comme suit : Nous voulons mesurer les performances de la connexion 6 – 9 (CBR1), celui-ci dispose de deux chemins ; le plus court chemin passant par les nœuds 10 –15, et l’autre passant par les nœuds 0 – 5. Le premier, est surchargé par deux connexions : CBR2 entre les nœuds 11 et 13. Et CBR3 entre les nœuds 10 et 14. Sur le deuxième, une seule connexion est établie entre les nœuds 1 et 3. Chaque nœud est séparé avec son voisin direct par une distance de 200m, cela assure que le flux est passé par tous les nœuds du chemin. 78

Chapitre VI

Simulation et discussion des résultats

Fig 6.2- Scénario de simulation utilisé.

Le tableau 6.2 résume le déroulement de la simulation et les principaux paramètres utilisés pour chaque flux.

Flux CBR1 CBR2 CBR3 CBR4

Débit (Kbps) 80 380 380 620

Début 15 5 10 20

Fin 35 25 30 35

Tab 6.2 : Paramètres de déroulement de simulation.

6 Simulation et discussion 6.1 Délai de bout en bout La figure 6.3 montre les résultats obtenus concernant la métrique délai de bout en bout pour chaque paquet du flux CBR1.

Fig 6.3 : Délai de bout en bout du flux CBR1 avec AODV-D et AODV standard. 79

Chapitre VI

Simulation et discussion des résultats

Discussion Avant la seconde 25, on remarque que les délais obtenus par le protocole AODV standard sont beaucoup plus élevés par rapport à AODV-D. Cela est justifié par le fait que ce dernier ayant exigé un délai max de 150 ms pour accepter la route, et donc a choisi la route passant par les nœuds 0 – 5 ayant plus de sauts mais moins encombrée par d’autres transmissions (seul le flux CBR4 est actif). Le léger dépassement de 150ms a été produit après la validation de la route par le protocole de routage, dans ce cas on a dit que le mécanisme ne possède aucune garantie pour le délai pendant la transmission des données. Par contre, le protocole AODV standard a choisi la route qui passe par les nœuds 10 – 15 selon le critère classique ; le plus court chemin. Cette route est surchargée par deux connexions (les flux CBR2 et CBR3), ce qui provoque des délais importants (jusqu’à 700ms). Cela est justifié par l’augmentation du délai passé dans les files d’attente des nœuds intermédiaires à cause des congestions. Après la seconde 25 le flux CBR3 est arrêté, on remarque que les délais pour AODV standard ont des valeurs proches de celles obtenues par AODV-D. Cela est justifié par le fait que la seule différence est le nombre de sauts des chemins choisis par les deux protocoles. D’une manière générale, on peut dire que le protocole AODV-D semble plus performant que celui standard dans les conditions de simulation décrites en termes de délai de bout en bout.

6.2 La variation de délai (la gigue) Toujours pour le même scénario, on obtient les résultats présentés dans les figures 6.4 et 6.5 qui représentent l’évolution de la gigue du flux CBR1 au cours du temps de la simulation pour les protocoles AODV-D et AODV.

Fig 6.4 : Evolution de la gigue pour AODV.

80

Chapitre VI

Simulation et discussion des résultats

Fig 6.5 : Evolution de la gigue pour AODV-D.

Discussion Lorsque le protocole AODV standard est activé, les variations de délai sont plus fréquentes et ont des délais plus important (jusqu’à 300 ms et dépasse souvent 100 ms) surtout avant la seconde 25. Cela est justifié toujours par le choix du plus court chemin sans aucune contrainte (le chemin passant par 10 – 15 dans notre cas), ce dernier est perturbé par d’autres connexions. Après la 25ième seconde la route est libérée et la connexion se stabilise. Pour le protocole AODV-D, le choix de la route est soumis à la contrainte du délai qui ne doit pas dépasser 150 ms, en effet, la route choisie est la plus stable en terme du délai et par conséquence, la gigue obtenue a des valeurs au maximum de 150 ms et ne dépasse pas 50 ms dans la plupart du temps, ce qui est acceptable pour une qualité moyenne de la VoIP par exemple (voir le tableau 3.3 dans le chapitre 3).

6.3 La perte de paquets Le tableau 6.3 résume les résultats obtenus pour chaque flux pour la perte de paquets avec le même scenario de simulation précédent. Protocole

AODV

AODV-D

Flux

CBR1

CBR2

CBR3

CBR4

CBR1

CBR2

CBR3

CBR4

Paquets envoyés paquets reçus Paquets perdus

200

951

951

1396

200

951

951

1396

193

916

951

1396

200

951

951

1396

7

35

0

0

0

0

0

0

Taux de perte %

3.5%

3.68%

0%

0%

0%

0%

0%

0%

Tab 6.3 : Taux de perte de paquets pour AODV-D et AODV standard. 81

Chapitre VI

Simulation et discussion des résultats

Discussion Les résultats présentés dans le tableau nous montrent que les simples scenarios et paramètres de simulation utilisés ne provoquent pas des taux de perte importants dans la plupart des cas. Mais on remarque des différences entre les deus protocoles. Lorsque le protocole AODV standard est activé, les flux CBR1 et CBR2 ont subis des taux de pertes de 3.5% et 3.68% respectivement. Cela est justifié par le choix de la route 10 – 15 qui est déjà surchargée par les deux flux CBR2 et CBR3 ; l’ajout du flux CBR1 à cette route, à provoqué ces pertes à cause du manque de ressources et des congestions. Lorsque le protocole AODV-D est activé, le critère de choix de la route avec contrainte du délai a permis de choisir la route 1 – 5. Cette route est plus stable car, seul le flux CBR4 est actif. Dans ce cas, chaque route est surchargée par deux connexions ce qui permet de créer des transmissions de données plus stable et donc des pertes faibles de paquets voir nulle comme les résultats obtenus dans notre cas.

Conclusion Les simulations effectuées dans ce présent chapitre nous a montré la différence entre les deux protocoles AODV et AODV-D. La comparaison entre les deux protocoles nous a permis de dégager le comportement d’AODV-D face aux connexions demandant un certain délai suite a l’intégration du nouveau mécanisme de routage. Nous concluons également que la mise en œuvre d’un tel mécanisme de routage ayant une importante influence sur la stabilité du réseau. En effet, le routage avec contraints de délai peut apporter des améliorations à des applications exigeant des ressources de QoS telles que la voix sur IP. Il rend également la mise en œuvre de telles applications dans un réseau mobile ad hoc plus efficace. Il faut noter ici que le scénario simple que nous avons réalisé dans ce chapitre a juste le but de connaître la différence entre le comportement des deux protocoles. Toutefois, les performances réelles du protocole AODV-D ne peuvent être déduites par ce simple scénario. Il est, en effet, important de concevoir des scénarios pertinents (tels que des scenarios aléatoires en utilisant les modèles de mobilité offerts par NS-2) conduisant à une évaluation plus précise du comportement du protocole.

82

Conclusion générale & Perspectives Les réseaux ad hoc trouvent des applications dans plusieurs domaines tels que les communications dans un champ de bataille, la gestion de catastrophes naturelles, les communications de groupes, etc. Récemment, ces réseaux attirent de plus en plus d’attention grâce leurs avantages. Le revers de la médaille est que plusieurs problèmes comme la sécurité, l’économie d’énergie, la scalabilité, et la qualité de service (QoS) doivent être solutionnés pour permettre un large déploiement. Dans le cadre de ce mémoire, l’objectif était d’analyser le protocole de routage AODV opérant dans les réseaux mobiles ad hoc. Une extension de ce protocole est faite en termes du délai de bout en bout. Le but est de le rend plus adapté à des applications telles que la voix sur IP (VoIP). Le travail réalisé dans ce mémoire s’inscrit dans le cadre des solutions proposées pour l’approvisionnement en qualité de service relâchée (soft QoS) dans les réseaux ad hoc. En effet, vu les caractéristiques de tels environnements, on ne peut s’attendre à une qualité de service ferme (hard QoS). La recherche en qualité de service dans les réseaux ad hoc se focalise sur quatre axes principaux, à savoir : (i) les modèles de QoS, (ii) les protocoles de signalisation, (iii) les protocoles MAC sensibles à la QoS, et enfin (iv) le routage avec QoS. D’après l’étude que nous avons menée, plusieurs protocoles de routage avec QoS ont été proposés dans la littérature, aussi bien pour les réseaux filaires que pour les réseaux ad hoc. Nous pouvons classifier toutes ces propositions en deux grandes catégories : solutions évolutionnaires et solutions révolutionnaires. La première catégorie de solutions vise à étendre des protocoles best effort existants alors que la deuxième vise à concevoir un protocole de routage avec QoS à partir de rien (from scratch). Nous avons opté pour la première approche pour des raisons de simplicité et de compatibilité avec les protocoles « best effort ». Par ailleurs, nous avons pris « le délai » comme métrique de routage. Pour concevoir notre protocole baptisé AODV-D (AODV with Delay constaints), nous nous sommes basés sur les travaux de Sarr et al pour estimer le délai d’attente au niveau de la sous-couche MAC et sur le draft de Perkins et al, auteurs du protocole AODV pour le mécanisme de fonctionnement. Par la suite, nous avons procédé à l’implémentation de notre protocole sous NS-2 (Network Simulator 2) en réutilisant le code source du protocole AODV rajouté d’autres composantes nécessaires. En phase finale du projet, nous avons évalué notre solution. Les résultats préliminaires de simulation ont montré que notre protocole donne de bonnes performances en termes de délai de bout en bout, de gigue, et de perte de paquets.

83

-

-

-

Notons enfin que ce travail nous a ouvert le champ vers d’autres extensions que nous citons ici en guise de perspectives : Evaluer AODV-D par rapport à d’autres métriques telles que la consommation en énergie, le temps d’établissement d’une route, et l’overhead généré, d’une part ; et par rapport à d’autres scénarios d’autre part ; Etendre le même travail à un autre protocole réactif qui est DSR et faire la comparaison avec AODV-D ; Comparer l’approche routage avec contraintes de délai avec l’approche routage multi-chemins pour l’amélioration des délais de bout en bout. On peut imaginer par exemple comparer AODV-D avec AOMDV Etendre notre protocole pour faire un routage multi-contraintes : on peut, par exemple, faire un routage à deux métriques (bande passante et délai) ou à trois métriques (bande passante, délai, et énergie) ;

84

Bibliographie

[1] : Mohamed BRAHMA « Étude de la QoS dans les Réseaux Ad hoc : « Intégration du Concept de l’Ingénierie du Trafic ». Thèse de doctorat. Université de HAUTE ALSACE (décembre 2006). [2] : Farid JADDI «CSR: une extension hiérarchique adaptative du protocole de routage ad hoc DSR » .Thèse de doctorat. Institut National Polytechnique de Toulouse, Octobre 2006. [3] : Andrew TANENBAUM « réseaux, architecture, protocoles, application » InterEditions, Paris 1990. [4] : Ahmed HABBOUCHI, Ismail LAOUFI « Conception cross layer et intégration de la QoS dans le protocole de routage DSR » mémoire d’ingéniorat, école militaire polytechnique (EMP) Année 2007. [5] : Michaël Hauspie « Contributions à l'étude des gestionnaires de services distribués dans les réseaux ad hoc » thèse de doctorat, Université des Sciences et Technologies de Lille, Année : 2005. [6] :M.KHEMIS et H.TOUATI, « Etude et simulation des protocoles de routage dans les réseaux ad hoc ».mémoire d’ingéniorat 2002/2003, université de TIZI OUZOU. [7] : Rabah MERAIHI : « Gestion de la qualité de service et contrôle de topologie dans les réseaux ad hoc » thèse de doctorat, Ecole nationale supérieure des télécommunications, France. janvier 2005. [8] : Tayeb LEMLOUMA « Le Routage dans les Réseaux Mobiles Ad Hoc »Université des Sciences et de la Technologie Houari Boumèdiene, Septembre 2000. [9] : Anis LAOUITI : « Unicast et multicast dans les réseaux ad hoc sans fil », thèse de doctorat, université de Versailles, juillet 2002. [10]: S. Corson , J. Macker « Mobile Ad hoc Networking (MANET) Network Working Group” January 1999.ftp://ftp.nordu.net/rfc/rfc2501.txt [11] C. Perkins, E. Belding-Royer, S.Das: «Ad hoc On-Demand Distance Vector (AODV) Routing, Network Working Group, July 2003: ftp://ftp.nordu.net/rfc/rfc3561.txt [12] M. Lewis R. Ogier, F. Templin. « Topology Dissemination Based on Reverse-Path Forwarding (TBRPF) » draft IETF, 2003. [13]Yih-Chun Hu.David B. Johnson, David A. Malts: «The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR) (draft IETF), 2003. [14] : Van der Meerschen Jérôme « Hybridation entre les modes ad hoc et infrastructure dans les réseaux de type Wi-Fi » Université Libre de Bruxelles année 2005-2006

85

[15] : Dominique Dhoutaut, « Etude du standard IEEE 802.11 dans le cadre des réseaux ad hoc : de la simulation à l'expérimentation » L’Institut National des Sciences Appliquées de Lyon Thèse Décembre 2003. [16] :Jean-Marc Percher et Bernard Jouga «Détection d’intrusions dans les réseaux ad hoc » Ecole Supérieure d´Electronique de l’Ouest (ESEO) France. [17] : Meriam Dawoud, « Analyse du protocole AODV » rapport de stage, Université Paul Sabatier-I.R.I.T, 2005/2006. http://phdgroup.org/LebaneseUniversityArchive/CSTI/20052006/5.pdf. [18]: Philippe Jacquet Thomas Clausen. RFC 3626 «Optimized Link State Routing Protocol (OLSR), (draft IETF) 2003. [19]: Leila TOUMI : « Algorithmes et mécanismes pour la qualité de service dans les réseaux hétérogènes » Thèse de doctorat, Institut National Polytechnique de Grenoble, décembre 2002 [20] : Meriem BELGAID Saida OUHAB « Routage et qualité de service dans AODV et OLSR » Mémoire 2006-2007 Université A/Mira de Bejaïa. [21]:C. Chiang, H. Wu, W. Liu, and M. Gerla: « Routing in Clustered Multihop, Mobile Wireless Networks In Mobile Wireless Networks», The IEEE Singapore International Conference on Networks, 1997. [22] Vincent D. Park and M. Scott Corson. « A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks». In INFOCOM (3), pages 1405–1413, 1997. [23]: C-K Toh. « A Novel Distributed Routing Protocol To Support Ad-Hoc Mobile Computing». In IEEE 15th Annual Int’l. Phoenix Conf. Comp. and Commun, 1996. [24]:R. Dube, C. Rais, K. Wang, and S. Tripathi. « Signal stability based adaptive routing (SSA) for ad hoc mobile networks. In Signal stability based adaptive routing (SSA) for ad hoc mobile networks, IEE Personal Communication., February 1997. [25]E. Crawley, R. Nair, B.Rajagopalan, and H. Sandick., « A Framework for QoSbasedRouting in the Internet», IETF RFC 2386, Aug. 1998. ftp://ftp.nordu.net/rfc/rfc2386.txt. [27]: R. Braden, D. Clark, and S. Shenker. «Integrated services in the internet architecture» :an overview. Internet Request For Comments RFC 1633, IETF, June 1994. ftp://ftp.nordu.net/rfc/rfc1633.txt. [28]: S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss. « An architecture for differentiated services». Internet Request For Comments RFC 2475, IETF, December1998. ftp://ftp.nordu.net/rfc/rfc2475.txt. [29]:Ian and C.Castelluccia « Dierentiation mechanisms for IEEE 802.11. In to appear in IEEE Infocom 2001, april 2001. [30]:K. Wu and J. Harms « QoS Support in Mobile Ad Hoc Networks». Crossing Boundariesthe GSA Journal of University of Alberta, Volume 1, n° 1. pages 92- 106. Nouvembre 2001

86

[31]: IEEE 802.11 WG, Wireless Medium Access Control (MAC) and Physical Layer (PHY) spécifications : Medium Access Control (MAC) Enhancement for Quality of Service (QoS IEEE 802.11e/Draft 3.0, May 2002. [32]: Claude Chaudet «Qualité de service et réseaux ad hoc – un état de l’art » rapport de recherche, institut national de recherche en informatique en automatique NRIA, novembre 2001. [33] : Claude Chaudet «Routage QoS et réseaux ad hoc : de l’état de lien à l’état de nœud » rapport de recherche INRIA, Janvier 2003. [34] M.K Marina, and S.R Das. «Ad hoc on-demand multipath distance vector routing. Wiley Wireless Communications and Mobile Computing», vol. 6(7), 2006, pp. 969–988. [35] Z. Ye, S. V. Krishnamurthy, and S. K. Tripathi. «A routing framework for providing robustness to node failures in mobile ad hoc networks». Elsevier Ad Hoc Networks Journal, vol 2(1) 2004, pp. 87–107. [36] S.-J. Lee, and M. Gerla: « AODV-BR: Backup Routing in Ad hoc Networks. », the IEEE Wireless Communications and Networking Conference (WCNC 2000). Vol 3, September 2000 pp. 1311–1316. [37] :Hui.Yao .Zhang, Marek.Bialkowski, Garry.Einicke and Jhon.Homer «An extended AODV protocol for VoIP application in mobile ad hoc network», SITEE, university of Brisbane Australia(2007). [38]: Shan Gong « Quality of Service Aware Routing Protocols for Mobile Ad Hoc Networks» these de magister, HUT communication laboratory Finlande (2006). [39]: C. Perkins and E. Belding-Royer: « Quality of Service for Ad hoc On-Demand Distance Vector Routing » (work in progress), draft IETF, Oct 2003. [40] : P. Anelli & E. Horlait «NS-2: Principes de conception et d'utilisation» [41] : Baptiste BUXANT «Simulation et évaluation d’un algorithme de contrôle de congestion pour Internet» Université Catholique de Louvain, année 2001-2002. [42] : Cheikh SARR « De l’apport d’une évaluation précise des ressources de la qualité de service des réseaux ad hoc basés sur IEEE802.11 » thèse de doctorat, Institut Nationale des Sciences Appliquées de Lion, année 2007. [43] : Antoine MAHUL «Apprentissage de la qualité de service dans les réseaux multiservice : application au routage optimale sous contraintes » université BLAISE PASCAL - CLERMONTFERRAND II, novembre 2005. [44]: Giuseppe Bianchi « Performance analysis of IEEE802.11 distributed coordination function » IEEE Journal on selected Areas in communication, volume18 (3): pages 535 -547 mars 2000. [45]: http://dropzone.tamu.edu/~prajjwal/ns2/main.html [46]: Sebastian Roschke « Implementation of Feedback Mechanism into AODV based on NS2». Un papier pulpier le 2007-05-16. Hasso Plattner-Institute for software systems engineering 87

[47]: Lei Chen and Wendi B. Heinzelman (University de Rochester USA) «A Survey of Routing Protocols that Support QoS in Mobile Ad Hoc Networks», IEEE Network. November/December 2007. [48]: « la qualité de service en voix sur IP » Accellent , www.accellent-group.com. [49] : http://www.chez.com/brunogarcia/Unix/Docs/awk.html

88

Liste des Abbreviations AODV Ad hoc On demand Distance Vector AODV-D Ad hoc On demand Distance Vector with Delay constraints CBR Constant Bit Rate CBRP Cluster Based Routing Protocol CSMA/CA Carrier Sense Multiple Access with Collision Avoidance CTS Clear To Send CW Contention Window DCF Distributed Coordination Function DIFS DCF Inter Frame Spacing DSDV Distance Source Distance Vector routing protocol DSR Distance Source Routing DSSS Direct Sequence Spread Spectrum EIFS Extended Inter Frame Spacing FHSS Frequency Hoping Spread Spectrum GHz Géga-Hertz GPRS General Packet Radio Service GSM Global System for Mobile Communication HiperLAN2 HIgh Performance Radio LAN 2.0 IEEE Institute of Electrical and Electronical Engineers IETF Internet Engineering Task Force INRIA Institut National de Recherche en Informatique et en Automatique IP Internet Protocol IR Infra Red ISO International Organization for Standardization ITU International Telecommunication Union MAC Medium Access Control MACA/PR Multihop Access Collision Avoidance with Piggyback Reservation MANET Mobile Ad hoc NETwork Mbps Méga bits par seconde MPR MultiPoint Relay NAV Network Allocation Vector NS-2 Network Simulator 2 OFDM Orthogonal Frequency Division Multiplex OLSR Optimized Link State Routin OSI Open Systems Interconnection PCF Point Coordination Function PDA Personal Digital Assistant PDR Paquet Delevery Ratio PIFS PCF Inter Frame Spacing QoS Quality of Service RERR Route ERRor RFC Request For Comments RREP Route REPly RREQ Route REQuest RTS Request To Send SIFS Short Inter Frame Spacing TBRPF Topology Dissemination Based on Reverse-Path Forwarding TCP Transmission Control Protocol ToIP Telephony over IP 89

UDP UMTS VoIP WiFi WLAN WMAN WPAN WWAN ZRP

User Datagram Protocol Universal Mobile Telecommunication System Voice over Internet Protocol Wireless Fidelity Wireless Local Area Network Wireless Metropolitan Area Networks Wireless Personal Area Networks Wireless Wide Area Networks Zone Routing Protocol

90

Annexes

-

Annexe A : Network Simulator 2 A.1 Présentation de Network Simulator 2 NS2 (Network Simulator 2) est un simulateur à évènements discrets développé dans un but de recherche. Il fournit un environnement assez détaillé permettant entre autre de réaliser des simulations d’IP, TCP, du routage et des protocoles multicast aussi bien sur des liens filaires que sans fil [15]. NS-2, est aujourd’hui le simulateur de réseau probablement le plus utilisé par la communauté scientifique des réseaux. Il a été le fruit de la collaboration entre l’université de Berkeley, USC (University of Southern California) et Xerox PARC dan lse cadre du projet VINT (Virtual Inter Network Testbed). Ce projet est soutenu par le DARPA(Defense Advanced Research Projects Agency). NS-2 est un outil de recherche très utile pour le design et la compréhension des protocoles. Il sert aussi bien dans l’étude des protocoles de routage qu’à l’étude des réseaux mobiles où les communications par satellites. NS-2 permet à l’utilisateur de définir un réseau et de simuler les communications entre les nœuds. Le simulateur utilise le langage orienté objet OTCL dérivé de TCL pour la description des conditions de simulation sous forme de script. Dans le script l’utilisateur fournit la topologie du réseau, les caractéristiques des liens physiques, les protocoles utilisés, le type de trafic généré par les sources, les événements, etc. Si le script écrit en OTCL permet une utilisation (édition, modification des simulations) facilitée du simulateur, les routines sont elles écrites en C++ pour avoir une plus grande puissance de calculs. Le résultat d’une simulation est un fichier texte contenant tous les fichiers événements de la simulation. Un traitement ultérieur de ce fichier permet d’en soustraire l’information souhaitée. Par ailleurs, le simulateur permet la création d’un fichier d’animation (d’extension .tr), permettant de visualiser la simulation sur l’interface graphique NAM. Cette visualisation fournit une représentation du graphe du réseau sur laquelle on peut voir les paquets circuler, suivre le niveau des files d’attente et observer le débit courant des liaisons. La figure A1 présente une simple utilisation de NS-2 [41].

Fig. A1 : Une simple utilisation de NS-2.

91

Annexes

-

A.2 Installation de NS-2 NS-2 est conçu initialement pour fonctionner sur les systèmes d'exploitation Unix et Linux, mais il existe un moyen pour son installation sur un système Windows 2000/XP; il s'agit de l'émulateur Cygwin qui offre un environnement Linux sous Windows. Cygwin est téléchargeable à partir d'Internet dans l'url : http:// www.cygwin.com. Le simulateur NS-2 est fourni sous forme d'un paquetage qui regroupe tous les fichiers nécessaires à son installation. On le trouve sous le nom : ns-allinone-version.tar.gz. (ns-allinone-2.33.tar.gz est utilisé dans notre simulation).

A.2.1 Installation de NS-2 sous Windows Avant de commencer à installer NS-2, il faut tout d'abord installer cygwin. Pour ce faire suivre les étapes suivantes :

A.2.1.1 Installation de cygwin 1. Télécharger cygwin à partir de son emplacement sur internet. 2. lancer l'installation on cliquant sur le bouton suivant. 3. choisir le chemin a partir de quel il s'installe: install from local directory. 4. choisir le chemin d'installation. 5. choisir Next. 6. sélectionner les packages à installer en activant install. 7. choisir Next. 8. terminer l'installation on cliquant sur terminer. 9. choisir OK.

A.2.1.2 Installation de NS-2 Après avoir installer cygwin, on doit suivre les étapes suivantes pour installer NS-2: 1. Télécharger NS-2 à partir de son emplacement sur internet. 2. Copier le dossier ns-allinone, dans le dossier /home/. 3. cliquer sur l'icône cygwin, la fenêtre noir s'affiche. 4. décompresser le: tar zxvf ns-allinone-2.33.tar.gz 5. accéder au répertoire ns-allinone-2.33: cd ns-allinone-2.33 6. taper la commande ./install. 7. Configuration finale: une fois ceci fait, notre NS-2 est installé, il nous reste de le configurer. D'habitude, on configure le fichier .bashrc mais avec cygwin, il y'a une autre alternative plus facile: (a) Copier ns.exe qui est sur ns-allinone-2.33/ns-2.33 et le coller sur cygwin/bin (b) Copier nam.exe qui est sur ns-allinone-2.33/nam-1.11 et le coller sur cygwin/bin Ainsi notre configuration est terminée.

92

Annexes

-

A.3 Les composants disponibles dans NS-2 La liste des principaux composants actuellement disponible dans NS-2 sont représentés par catégorie da le tableau suivant : Application Transport

Web, ftp, telnet, générateur de trafic (CBR, ...). TCP, UDP, RTP, SRM.

Routage

Statique, dynamique (vecteur distance) et routage multipoint (DVMRP, PIM). RED, DropTail, Token bucket. CBQ, SFQ, DRR, Fair queueing. CSMA/CD, CSMA/CA, lien point à point ;

Gestion de file d'attente Discipline de service Système de transmission

Tab A1 : Les principaux composants de NS-2.

A.4 Les langages utilisés dans NS-2 NS-2 utilise deux langages parce qu’il réalise deux types de choses. D’une part, le simulateur doit être efficace dans la manipulation de bytes, de paquets et d’entêtes et dans l’application d’algorithmes sur de grandes quantités de données. Dans ce cas la vitesse d’exécution est primordiale et prend le pas sur le temps de compilation, l’utilisation du C++ s’impose. D’autre part, l’utilisateur souhaite changer rapidement ses scénarios de simulation, dans ce cas OTCL offre une bonne solution [40]. NS-2 permet à l’utilisateur de définir un réseau et de simuler les communications entre les nœuds. Le simulateur utilise le langage orienté objet OTCL dérivé de TCL pour la description des conditions de simulation sous forme de script. Dans le script l’utilisateur fournit la topologie du réseau, les caractéristiques des liens physiques, les protocoles utilisés, le type de trafic généré par les sources, les événements, etc. Si le script écrit en OTCL permet une utilisation (édition, modification des simulations) facilitée du simulateur, les routines sont elles écrites en C++ pour avoir une plus grande puissance de calculs. Un grand nombre de classes sont prédéfinies et mettent en œuvre plusieurs types de protocoles, de files d’attentes, de sources et algorithmes de routage.

A.5 Architecture de NS-2 A.5.1 Arborescence des classes compilées Un grand nombre de classes sont prédéfinies et mettent en œuvre plusieurs types de protocoles, de files d’attentes, de sources et algorithmes de routage [41].La figure A.2 représente l'arborescence de classes utilisées par le simulateur [40].

93

Annexes

-

Fig. A2 : Arborescence de dérivation des classes C++ du simulateur.

TclObject : C’est la racine de toutes les autres classes à la fois dans l'arborescence compilée et interprétée. La classe TclObject constitue donc la classe de base de la plupart des autres classes. Tous les objets du modèle de simulation sont des instances de la classe TclObject. Cette classe sert aux objets dont la création est initiée par l'interpréteur. Elle possède les interfaces nécessaires aux liaisons entre les variables qui doivent être visibles à la fois en C++ et OTcl. Elle définit la fonction command () qui est très utile pour ajouter des commandes à l'interpréteur. La classe TclObject ainsi que les autres sources du répertoire tclcl sont partagées entre NS-2 et le projet MASH de Berkeley. Dans la hiérarchie des classes OTcl, le nom de la classe racine se nomme autrement et porte le nom de SplitObject. NsObject : c’est une sous-classe de la classe TclObject mais reste cependant une superclasse aux autres classes. La principale différence avec la classe TclObject tient à ce qu'elle soit capable de recevoir des paquets et traiter des événements. Elle hérite de la classe Handler. Cette classe constitue la principale racine des objets dans NS-2. Elle contient les fonctions communes nécessaires au simulateur et définit la fonction virtuelle : void recv (Packet *, Handler* callback =0)=0; Cette fonction est une fonction générique utilisée par tous les objets dérivés de NsObject pour recevoir un paquet. Elle est réellement définie par les sousclasses :
Application : Classe mère de toutes les applications (ftp, telnet, web)
Agent : La classe agent fournit des méthodes utiles au développement de la couche transport et à d'autres protocoles du plan de signalisation ou de gestion. C'est la classe de base pour définir des nouveaux protocoles dans NS-2. Elle fournit l'adresse locale et de destination, les fonctions pour générer les paquets, l'interface à la classe Application. Actuellement NS-2 comporte de nombreux agents citons: UDP, protocoles de routage, différentes versions de TCP, RTP, etc. [20].
Node : un nœud peut être une machine hôte, un switch, un routeur, une passerelle, etc. Chaque nœud contient au minimum les composants suivants : 1. Une adresse ou un identificateur (id_) automatiquement incrémenté par une unité (à partir de 0) quand les nœuds sont crées. 2. Une liste de noeuds voisins (neighbor_). 94

Annexes

-

3. Une liste d'agents (agent_). 4. Un identificateur du type du nœud (nodetype_). 5. Un module de routage. Queue : la classe mère de tous les buffers (DropTail, RED) LinkDelay : cette classe simule le délai de propagation et le temps de transmission sur les liens du réseau. Avec la classe Queue, cette classe simule les couches 1 et 2 d'Internet. Packet : la classe de tous les paquets circulant sur le réseau. TimerHundler : la classe mère de tous les timers(temporisateurs) utilisés par les protocoles du réseau [20].

A.5.2 Arborescence des fichiers La distribution de NS-2 comprend principalement 3 répertoires (figureA3) [41]: - NS-2, l'application NS. Ce répertoire contient l'ensemble des fichiers .h et .cc de NS-2. - nam-1, l'outil de visualisation des résultats de la simulation: l'animateur réseau. - tclcl, sources du code assurant la liaison entre l'interpréteur et le simulateur. L’un des principaux fichiers est: tcl-object.tcl.

Fig. A3 : Arborescence des fichiers de la distribution NS-2.

A.6 Le modèle de réseau sous NS-2 Un modèle de réseau sous NS-2 est constitué de quatre composants essentiels : • Les nœuds de réseau : endroits où est généré le trafic, ou nœuds de routage ; • Les liens de communication entre les réseaux. • Les agents de communication, représentant les protocoles de niveau transport (TCP, UDP) ; ces agents sont attachés aux nœuds et connectés l’un à l’autre, ce qui représente un échange de données (cnnexion TCP, flux UDP). • Les applications qui génèrent le trafic de données selon certaines lois (CBR, VBR), et se servent des agents de transport [17].

A.7 Traitement des résultats dans NS-2 Après le déroulement de la simulation, NS-2 donne un fichier trace qui est un fichier texte contenant tous les événements de la simulation. Le traitement de ce fichier permet d’en soustraire l’information souhaitée [40]. Chaque événement est représenté dans le fichier trace 95

Annexes

-

avec une ligne qui contient douze champs. Le tableau A.2 donne une vision des la structure d’une ligne du fichier trace sous NS-2 : Event

Time

From node

To node

Pkt type

Pkt size

Flags

Fid

Src addr

Dst addr

Seq num

Pkt id

Tab A2 : Structure d’une ligne du fichier trace.

1. Action effectuée sur le paquet. Un ”+” signifie que le paquet est reçu dans une file, un ”-” signifie que le paquet quitte la file, un ”s” signifie que le paquet est envoyé, un ”d” signifie que le paquet est jeté (dropé) et un ”r” signifie que le paquet est réceptionné par un agent. 2. Instant où l’action est effectuée. 3. Nœud de départ du lien concerné. 4. Nœud d’arrivée du lien concerné. 5. Type de paquet. 6. Taille du paquet en bytes. 7. Flags. 8. Identificateur de flux. 9. Agent de départ. 10. Agent d’arrivée. 11. Numéro de séquence. 12. Identificateur unique pour chaque paquet. La figure A4 illustre un exemple détaillé d’une ligne d’un fichier trace sous NS-2 :

+ 0 .002048 1 3 cbr 256 --------------- 0 1.0 Type événement + enqueue - dequeue r receive d drope s send

Time

Type trafic

Taille paquet

Id flux

7.0

8

9

Num seq paquet

Source dest Source et dest Entre lesquelles l’évènement est passé

Adresse de la source et destination du paquet

Id unique du paquet

Fig A4 : Exemple de fichier trace.

En plus des fichiers traces qu’offre le simulateur NS-2, il permet de visualiser les événements de la simulation à travers une interface graphique NAM (figure A5) :

96

Annexes

-

Fig A5 – Fenêtre de visualisation de NAM.

A.8 Structure d’un nœud mobile sous NS-2 La figure A6 décrit la structure d’un nœud sans fil dans NS-2. Elle montre le travail interne du flux dans le nœud sans fil. Le nœud reçoit toujours des paquets à l'entrée du nœud. Le paquet passe par le classificateur où son champ d'adresse est examiné. Les agents sont les connecteurs. Quand les connecteurs reçoivent les paquets, ils exécutent certaines fonctions et livrent les paquets vers leurs voisins ou les ignorent. Il existe plusieurs types de connecteurs effectuent différentes fonctions, par exemple, l'agent, Link Layer, couche MAC et d'interface réseau.

Fig. A6 : Structure d’un nœud mobile sous NS-2.

97

Annexes

-

A.9 Les différents modèles de mobilité sous NS-2 Puisque les réseaux ad hoc (MANET) sont souvent analysés par des simulations, leurs résultats d’exécution dépendent légèrement des paramètres de réseau de simulation. Ainsi, l’évaluation d’un protocole de routage ad hoc dépend de choisir soigneusement un modèle de mobilité pour illustrer les mouvements réalistes des utilisateurs. Les modèles de mobilité d’entité représentent les nœuds mobiles dont les mouvements sont indépendant l’un de l’autre. D’autre part, les modèles de mobilité de groupe représentent les nœuds mobiles dont les mouvements dépendent l’un de l’autre et ils tendent à être plus réalistes dans les applications impliquant la communication de groupe [20].

A.9.1 Le modèle Radom Way Point (RWP) Dans ce modèle la mobilité des nœuds est typiquement aléatoire et tous les nœuds sont distribués uniformément dans l’espace de simulation. En effet il consiste en : • Le placement d’un certain nombre de mobiles dans une zone carrée de laquelle ils ne peuvent sortir. • L’affectation d’une position, d’une vitesse et d’une destination initiale à chaque mobile. • Le déroulement proprement dit de la simulation, où à chaque fois que les mobiles atteignent leur destination dans le carré, ils repartent vers une autre destination choisie aléatoirement après un éventuel temps de pause. Du fait de la simplicité de ce modèle, il n’est pas toujours adapté pour décrire des comportements de mobilité complexes [20].

A.9.2 Le modèle Random Walk Ce modèle est développé pour imiter un mouvement imprévisible. Un nœud mobile dans ce modèle se déplace de son endroit courant à un nouvel endroit en choisissant aléatoirement une direction et une vitesse suivant lesquelles il se déplace. La nouvelles vitesse et direction toutes les deux sont choisies dans des gammes prédéfinies, [speedmin, speedmax] et [0, 2π] respectivement. Un nœud mobile atteignant la frontière de simulation, rebonds avec l’angle déterminé par la direction entrante et puis continue le long du nouveau chemin.

A.9.3 Le modèle aléatoire de direction (random direction model) Il vient comme une modification sur le modèle de RWP. Dans RWP, la probabilité d’un nœud mobile de choisir une nouvelle destination située au centre du la zone de simulation ou une destination qui nécessite un déplacement par le centre est haute. Ce modèle essaye d’alléger ce comportement, fournissant un nombre constant de voisins dans toute la simulation. Les nœuds mobiles choisissent une direction aléatoire suivant laquelle ils se déplacent en tant que modèle de mobilité de random walk, où ils se déplacent vers la frontière de la simulation dans cette direction. Une fois que la frontière est atteinte, le nœud mobile fait une pause pendant le temps indiqué, choisit une autre direction angulaire entre (0 et 180) continue alors le processus.

98

Annexes

-

Conclusion Dans cette partie, nous avons présenté une brève description de l'outil de simulation NS-2. Nous avons décrit les langages utilisés dans ce simulateur, citons tcl et OTcl. Puis nous avons décrit l'architecture générale de son utilisation, l'arborescence et la hiérarchie des différentes classes existantes. Un point important est visualisé, c'est l'étude et la création des environnements mobiles dans ce simulateur ainsi l'extraction et le traitement des résultats.

99

Annexes

Annexe B :

-

Langage AWK

B.1 Présentation AWK est un outil qui permet d'effectuer des recherches, simples ou complexes, dans des fichiers textes. C'est un langage de programmation datant de 1977, date de son apparition dans le monde Unix. Il tire son nom des trois programmeurs qui l'ont développé : Alfred V. Aho, Peter J. Weinberger et Brian W. Kernighan [49]. Cette utilitaire a été crée dans le but de remplacer les commandes grep et sed. Sa grande souplesse lui a permis de connaître un succès immédiat. Et de nouvelles versions sont apparues au fil du temps : nawk et gawk. Aujourd'hui encore, cet utilitaire est toujours utilisé du fait de sa ressemblance avec le langage C, de sa souplesse et de sa présence sur la majorité des systèmes d'exploitation Unix. Il est encore utilisé en administration système et dans les scripts Shell en tant que commande. Awk fonctionne en lisant des données. Ces données peuvent être ainsi traitées par l'utilisateur. Utilisateur qui peut choisir de lire des données provenant de fichiers ou du canal de l'entrée standard. Par conséquent, awk a pour but premier de jouer un rôle de filtre bien qu'il ne se limite pas qu'à cela.

B.2 Syntaxe générale d'un programme awk Un programme awk est constitué de trois grandes sections :

• La section initiale : Les commandes qu'elle contient sont lues et traitées avant la lecture du fichier en entrée. C'est le bon endroit pour initialiser des variables par exemple ou pour ouvrir des fichiers auxiliaires. Elle commence par le mot clef BEGIN et est entourée d'une paire d'accolades.

• La section terminale : Comme son nom l'indique, la section terminale n'est traitée qu'une fois le fichier en entrée fermé. Typiquement, c'est l'endroit idéal pour fermer des fichiers auxiliaires ou réaliser des statistiques. Bref, tout ce qui ne peut se faire qu'une fois toutes les données connues et traitées. Elle est introduite par le mot clef END et est entourée d'une paire d'accolades.

• La section des règles : C'est la section où nous mettons les lignes de code de traitement du fichier. Elle est appelée ainsi, car, nous spécifions des règles d'activation pour les ordres de AWK. Chaque ensemble de commandes est ceint d'une paire d'accolades et précédé d'une portée. Celle ci peut être sous la forme d'une expression régulière entourée par des slash / mais également toute expression arithmétique permettant de discriminer les lignes, par exemple, des conditions sur le nombre de champs. Elle peut également être vide, auquel cas, les commandes seront appliquées à toutes les lignes.

100

Annexes

-

B.3 Exécution d'un programme AWK Il y a deux façons générales d'exécuter des instructions AWK [31]:

1. pour des applications simples : L’instruction d'exécution est sous la forme :

awk 'program' fichier1 ... fichier n • 'program': est une liste d'instructions se présentant sous la forme : Pattern action 1; action 2; ... ; action n. • fichier1 ... fichier n:liste des fichiers de données en entrée. La commande exécute le programme, fichier par fichier, sur chaque ligne de façon séquentielle, ou s'il n'y a pas de fichier en entrée, prend le standard input en tant que fichier d'entrée.

2. pour des applications plus complexes : On ouvre un fichier d'instructions awk et l'exécution s'effectue par la commande :

awk -f fichierprog liste optionnelle de fichiers de données. • fichierprog : est le fichier d'instructions awk enregistré sous l'extension .awk. La commande exécute séquentiellement le programme se trouvant dans le fichier programme sur chaque ligne des fichiers en entrée.

101

Annexes

-

Annexe C : codes source C.1 script Tcl # Define optioNS set val(chan) Channel/WirelessChannel set val(prop) Propagation/TwoRayGround set val(netif) Phy/WirelessPhy set val(mac) Mac/802_11 set val(ifq) Queue/DropTail/PriQueue set val(ll) LL set val(ant) Antenna/OmniAntenna set val(ifqlen) 50 set val(nn) 16 set val(rp) AODVD/AODV set val(x) 1000 set val(y) 1000 set val(stop) 40

;# channel type ;# radio-propagation model ;# network interface type ;# MAC type ;# interface queue type ;# link layer type ;# antenna model ;# max packet in ifq ;# number of mobilenodes ;# routing protocol ;# X dimension of topography ;# Y dimension of topography ;# time of simulation end

Mac/802_11 set dataRate_ 5.5Mb Mac/802_11 set basicRate_ 1Mb

;# 802.11 data transmission rate ;# 802.11 basic transmission rate

# parametres de QoS Agent/AODV set QoS_factor 1 Agent/AODV set req_bandwitdh 0.08 Agent/AODV set req_delay 0.150

;# activer /désactiver le contrôle d’admission. ;# bande passante demandée. ;# délai max à ne pas dépasser.

# préparation des fichiers traces set ns [new Simulator] set tracefd [open simplecbr.tr w] set fd [open freebw.tr w] set namtrace [open simwrlscbr.nam w] $ns trace-all $tracefd $ns namtrace-all-wireless $namtrace $val(x) $val(y) # set up topography object set topo [new Topography] $topo load_flatgrid $val(x) $val(y) create-god $val(nn) #création et configuration des noeuds. $ns node-config -adhocRouting $val(rp) \ -llType $val(ll) \ -macType $val(mac) \ -ifqType $val(ifq) \ -ifqLen $val(ifqlen) \ -antType $val(ant) \ 102

Annexes

-propType $val(prop) \ -phyType $val(netif) \ -channelType $val(chan) \ -topoInstance $topo \ -agentTrace ON \ -routerTrace ON\ -macTrace OFF\ -movementTrace OFF for {set i 0} {$i < $val(nn) } { incr i } { set node_($i) [$ns node] }

# Définition des locations initiales des noeuds for {set j 0} {$j <= 5 } { incr j } { set posicion_x [expr ($j % 10) * 200 ] $node_($j) set X_ $posicion_x $node_($j) set Y_ 800.0 $node_($j) set Z_ 0.0 } for {set j 10} {$j <= 15 } { incr j } { set posicion_x [expr ($j % 10) * 200 ] $node_($j) set X_ $posicion_x $node_($j) set Y_ 200.0 $node_($j) set Z_ 0.0 } $node_(6) set X_ 0.0 $node_(6) set Y_ 400.0 $node_(6) set Z_ 0.0 $node_(7) set X_ 0.0 $node_(7) set Y_ 600.0 $node_(7) set Z_ 0.0 $node_(8) set X_ 1000.0 $node_(8) set Y_ 600.0 $node_(8) set Z_ 0.0 $node_(9) set X_ 1000.0 $node_(9) set Y_ 400.0 $node_(9) set Z_ 0.0 #création de quatre connexioNS de type cbr. #cbr1 entre le noeud 6 et 9. set udp1 [new Agent/UDP] $ns attach-agent $node_(6) $udp1 set null1 [new Agent/Null] $ns attach-agent $node_(9) $null1 $ns connect $udp1 $null1 set cbr1 [new Application/Traffic/CBR] $cbr1 attach-agent $udp1 $cbr1 set packet_size_ 1000 103

Annexes

-

$cbr1 set rate_ 0.08Mb $ns at 15.0 "$cbr1 start" $ns at 35.0 "$cbr1 stop" #cbr2 entre le noeud 11 et 13. set udp2 [new Agent/UDP] $ns attach-agent $node_(11) $udp2 set null2 [new Agent/Null] $ns attach-agent $node_(13) $null2 $ns connect $udp2 $null2 set cbr2 [new Application/Traffic/CBR] $cbr2 attach-agent $udp2 $cbr2 set packet_size_ 1000 $cbr2 set rate_ 0.38Mb $ns at 5.0 "$cbr2 start" $ns at 25.0 "$cbr2 stop" #cbr1 entre le noeud 10 et 14. set udp3 [new Agent/UDP] $ns attach-agent $node_(10) $udp3 set null3 [new Agent/Null] $ns attach-agent $node_(14) $null3 $ns connect $udp3 $null3 set cbr3 [new Application/Traffic/CBR] $cbr3 attach-agent $udp3 $cbr3 set packet_size_ 1000 $cbr3 set rate_ 0.38Mb $ns at 10.0 "$cbr3 start" $ns at 30.0 "$cbr3 stop" #cbr1 entre le noeud 1 et 4. set udp4 [new Agent/UDP] $ns attach-agent $node_(1) $udp4 set null4 [new Agent/Null] $ns attach-agent $node_(4) $null4 $ns connect $udp4 $null4 set cbr4 [new Application/Traffic/CBR] $cbr4 attach-agent $udp4 $cbr4 set packet_size_ 1000 $cbr4 set rate_ 0.62Mb $ns at 17.0 "$cbr4 start" $ns at 35.0 "$cbr4 stop" #procedure pour afficher la bande passante libre toutes les secondes proc record {} { global fd NS node_ mac_ freebw_ set time 1.0 set free [[$node_(1) set mac_(0)] set freebw_] set now [$NS now] puts $fd "$now $free" 104

Annexes

-

$ns at [expr $now+$time] "record" } $ns at 1.0 "record" # definition des position initiales #pour le visualisateur nam. for {set i 0} {$i < $val(nn)} { incr i } { $ns initial_node_pos $node_($i) 30 } # fin de la simulation for {set i 0} {$i < $val(nn) } { incr i } { $ns at $val(stop) "$node_($i) reset"; } $ns at $val(stop) "$ns nam-end-wireless $val(stop)" $ns at $val(stop) "stop" $ns at 39.01 "puts \"end simulation\" ; $ns halt" proc stop {} { global NS tracefd namtrace fd $ns flush-trace close $tracefd close $fd close $namtrace } $ns run

105

Annexes

-

C.2 Script Awk BEGIN { max_packet_id = 0; totalreceved = 0; PDR = 0.0; totalsend = 0; total_time = 0.0; } { action = $1; time = $2; layer = $4; type = $7; id_paquet = $6;

if (id_paquet > max_packet_id ) max_packet_id = id_paquet ; if ( action == "s" && layer == "AGT"){ if ( start_time[id_paquet] == 0 ) start_time[id_paquet] = time; } if (action != "D" ){ if (action == "r" && layer == "AGT") end_time[id_paquet] = time; }else { end_time[id_paquet] = -1; } if ((layer == "AGT") &&(action == "r")) totalreceved ++; if ((layer == "AGT") && (action == "s")) totalsend ++; }

106

Annexes

-

END {

for ( id_paquet = 0; id_paquet <= max_packet_id; id_paquet++ ) { start = start_time[id_paquet]; end = end_time[id_paquet]; end_to_end = end - start;

if ( start < end ){ total_time = total_time + end_to_end;

printf("%d %f end_to_end);

%f

%f

\n", id_paquet, start, end,

} } delay = total_time/totalreceved; PDR

= totalreceved/totalsend;

PLR

= 1.0 - PDR;

printf("%f

%f

%f

%f

%d

%d \n", delay, PDR, PLR,

totalreceved, totalsend); }

107

Résumé L’approvisionnement en Qualité de Service (QoS) est l’une des problématiques majeures posées dans les réseaux mobiles ad hoc(MANETs). Une bonne solution de QoS est généralement construite à base de plusieurs briques dont le routage avec QoS. Contrairement au routage « au mieux », le routage avec QoS permet de chercher des routes assurant une certaine QoS par rapport à une métrique bien définie. Par conséquent, il est mieux adapté pour les applications multimédia ou temps réel. Dans ce travail, nous nous intéressons à garantir le délai de bout en bout dans le protocole AODV. Notre protocole de routage ave QoS baptisé AODV-D (AODV with Delay constraints) a comme brique principale l’estimation du délai par une file M/M/1/K, un contrôle d’admission sera effectué par la suite pour vérifier le délai. Les résultats préliminaires de simulation sous NS-2 ont montré une amélioration significative des performances selon les trois métriques principales de la VoIP. Mots clés: réseau ad hoc, IEEE 802.11, protocoles de routage, qualité de service (QoS), AODV, simulateur NS-2.

Abstract Quality of Service (QoS) provisioning is one of the major problems in mobile ad hoc networks (MANETs). A good solution of QoS is generally built upon several blocks, of whom QoS routing. Contrary to « best effort », routing, QoS routing makes it possible to search routes ensuring QoS according to a given metric. Consequently, it is more adapted for multimedia or real time applications. In this work, we are interested in guaranteeing end to end delay in the AODV protocol. Our QoS routing protocol named AODV-D (AODV with Delay constraints) has as principal building block delay estimation by an M/M/1/K queue. Thereafter, an admission control is carried out to check the delay. The preliminary results of simulation under NS-2 showed a significant improvement of the performances according to the three principal metrics of VoIP. Keywords: ad hoc network, IEEE 802.11, routing protocols, quality of service (QoS), AODV, NS-2 simulator.