Etude et simulations des problèmes d'équité d'accès au canal dans les réseaux ad hoc

Promotion 2016/2017

République Algérienne Démocratique et Populaire
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique

Université Abderrahmane Mira de Béjaïa

Faculté des Sciences Exactes
Département d'Informatique

Mémoire de fin d'étude

En vue de l'obtention du diplôme de Master professionnel en informatique
Option : Administration et Sécurité des Réseaux Informatiques

Thème

Étude et simulation du problème d'équité

d'accès au canal dans les réseaux ad hoc

802.11

Présenté par: Encadré par:

( BELHOUL Menad. ( MEHAOUED Kamal.
( TAOURIRT Farid.

Devant le jury composé de :

( Président : METIDJI Rebiha.

( Examinateur¹ : AIT ABDELOUAHAB Yazid. ( Examinateur² : SELLAMI Linda.

Remerciements

Nous remercions nos familles respectives et particulièrement nos parents pour leurs soutiens qu'ils nous ont accordés tout au long de notre chemin.

Nous remercions notre encadreur M. MEHAOUED Kamel pour tout le temps qu'il nous a consacré, pour ses précieux conseils et pour son aide et son appui tout au long de notre travail.

Nous remercions tout particulièrement les membres du jury qui ont accepté de juger notre modeste travail.

Nous remercions nos amis.

Et à tous ceux qui ont contribué, de prés ou de loin à la réalisation de ce

travail.

Dédicaces

Je dédie ce travail à :

Mes parents.

Mon frère, mes quatre soeurs et leurs enfants.

Toute ma famille.

Tous mes amis et spécialement pour Yanis ATOUMI et Slimane SIROUKANE.

BELHOUL Menad

Je dédie ce travail à :

Mes parents.

Mes frères et soeurs.

Toute ma famille.

Tous mes amis et spécialement pour Salah et Massinissa SALHI et Hicham SADMI.

TAOURIRT Farid

I

Table des matières

Table des matières II

Table des figures IV

Liste des tableaux V

Liste des abréviations VI

Introduction générale 1

1 Les réseaux ad hoc 3

1.1 Introduction 3

1.2 Les réseaux sans fil 3

1.3 Classification des réseaux sans fil 3

1.3.1 Classification par type d'architecture réseaux 3

1.3.2 Classification par étendue de la zone de couverture 4

1.3.3 Classification par techniques d'accès au canal radio 5

1.4 Les réseaux mobiles ad hoc (MANET) 5

1.4.1 Définition 5

1.4.2 Caractéristiques des réseaux mobiles ad hoc 6

1.4.3 Domaines d'application 7

1.4.4 Problèmes et contraintes spécifiques des réseaux sans fils 8

1.5 Le routage dans les réseaux MANET 9

1.5.1 Classification des protocoles de routage ad hoc 10

1.5.2 Les différentes familles de protocoles de routage MANET 11

1.5.3 Avantages et inconvénients des familles des protocoles de routages MANET 13

1.5.4 Description de quelques protocoles de routages représentatifs 13

1.6 Conclusion 16

2 MAC IEEE 802.11 17

2.1 Introduction 17

2.2 Présentation de la norme IEEE 802.11 17

2.3 Extensions de la norme IEEE 802.11 17

2.4 Architecture en couches 18

II

Table des matières

2.4.1 La couche physique 19

2.4.2 La couche liaison de données 21

2.5 Étude du protocole MAC 802.11 21

2.5.1 Méthodes d'accès 22

2.5.2 Protocoles de la sous-couche MAC en mode DCF 22

2.6 Conclusion 28

3 Particularités de 802.11 dans un contexte ad hoc 29

3.1 Introduction 29

3.2 Le problème des noeuds cachés 30

3.3 Le problème des noeuds cachés asymétriques 31

3.4 Le problème des trois paires 32

3.5 Le problème des noeuds exposés 33

3.6 Le problème de la zone grize 34

3.7 Partage du canal par des flux à vitesses différentes 34

3.8 TCP et 802.11 35

3.9 Conclusion 36

4 Analyse et évaluation des performances 802.11 37

4.1 Introduction 37

4.2 Simulation de quelques problèmes d'équité802.11 37

4.2.1 Présentation de Network Simulator 2 (NS 2) 37

4.2.2 Noeud caché 38

4.2.3 Noeud exposé 39

4.2.4 Stations cachées asymétriques 41

4.2.5 Trois paires 42

4.3 Quelques solutions apportées aux problèmes d'équité 43

4.3.1 Les algorithmes de backoff 43

4.3.2 Le protocole MadMac 46

4.3.3 FWM (Fair Wireless MAC) 49

4.4 Conclusion 50

Conclusion générale 52

Bibliographie 57

Annexe 57

Table des figures

1.1	Le modèle des réseaux mobiles sans infrastructure.	4
1.2	Modélisation d'un réseau ad hoc	6
1.3	La mobilitédans les réseaux ad hoc	7
1.4	Routage »àplat». 10
1.5	Routage »hiérarchique». 11
1.6	Relais multipoints. 14
1.7	Recherche de route par inondation »AODV»	15
1.8	Exemple d'une zone de routge avec ñ = 2.	16
2.1	Étalement du spectre. 20
2.2	Changement de fréquence régulier pour réduire l'impact des interférences	20
2.3	Exemple de backoff exponentiel	23
2.4	Le backoff et le defering. 24
2.5	Accés au médium en mode RTS/CTS. 25
2.6	Configuration à quatre noeuds	26
2.7	Extended Inter Frame Spacing. 26
2.8	Mécanisme de fragmentation. 27
2.9	Fragmentation dans le mode DCF. 28
3.1	Les stations cachés	30
3.2	Les stations cachés asymétriques. 31
3.3	Les stations cachés asymétriques. 32
3.4	Le phénomène des noeuds exposés. 33
3.5	Le phénomène de la zone grize. 34
4.1	Le scénario du noeud caché	38
4.2	Résultat de la simulation du scénario (noeud caché)	39
4.3	Le scénario du noeud exposé	39
4.4	Résultat de la simulation du scénario (noeud exposé)	40
4.5	Le scénario des stations cachées asymétriques	41
4.6	Résultat de la simulation du scénario (stations cachées asymétriques)	42
4.7	Le scénario des trois paires	42
4.8	Résultat de la simulation du scénario (trois paires)	43
		III

IV

Table des figures

4.9 BEB 44

4.10 DIDD 44

4.11 MILD 44

4.12 BEB Inversé 45

4.13 Efficacitésur les 3 paires. 46

4.14 Efficacité: stations cachées. 46

4.15 á sur les 3 paires 46

4.16 á sur les stations cachées. 46

4.17 Une illustration simple de MadMac 47

4.18 Une illustration simple de MadMac sur la configuration des stations cachées 48

4.19 Performance de MadMac sur le scénario des stations cachées asymétriques. 48

4.20 Performance de MadMac sur le scénario des trois paires. 48

4.21 Performance de MadMac sur le scénario des stations cachées 49

4.22 Répartition des débits avec FWM; Scénario contention déséquilibrée. 50

4.23 Répartition des débits avec FWM; Scénario station cachée 50

Liste des tableaux

1.1	Comparaison des protocoles MANET. 13
2.1	Les différentes extensions de la norme IEEE 802.11	18
2.2	Modèle en couches de l'IEEE 802.11.	19
2.3	Comparaison entre les différentes technologies de transmission du 802.11	21
2.4	Intertrames et CW pour les différentes couches physiques. 27
4.1	Modèle PEPA des algorithmes de backoff	45
4.2	Comparaison de performances pour les situations caractéristiques	50
		V

VI

Liste des abréviations

AODV Ad-hoc On-demand Distance Vector.

BeB Binary Exponential Backoff.

BTMA Busy Tone Multiple Access.

BTS Base Transceiver Stastion.

CSMA/CA Carrier-Sense Multiple Acces with Collision Avoidance.

CTS Clear To Send.

CW Contention Window.

DBTMA Dual Busy Tone Multiple Access.

DCF DistributedCoordination Function.

DDoS Distributed Denial-of-Service attack.

DIDD Double Increase, Double Decrease.

DIFS DCF Inter-Frame Space.

DSSS Direct Séquence Spread Spectrum.

EIFS Extended Inter Frame Spacing.

FDMA Frequency Division Multiple Access.

FHSS Frequency Hoping Spread Spectrum.

FWM Fair Wireless MAC.

GPS Global Position System.

IEEE Institute of Electrical and Electronics Engineers.

IETF Internet Engineering Task Force.

IFS Inter-Frame Spacing.

IR Infra Red.

LLC Logical Link Control.

MAC Media Access Control.

Liste des tableaux

MANET Mobile Ad hoc NETworks.

MTU Maximum Transmission Unit.

NAV Network Allocation Vector.

OFDM Orthogonal Frequency Division Multiplexing.

OLSR Optimized Link State Routing Protocol.

OSI Open Systems Interconnection.

OSPF Open Shortest Path First.

PCF Point Coordination Function.

PEPA Performance Evaluation Proccess Algebra.

PNAV Probabiliste Network Allocation Vector.

RTS Request To Send.

SDMA Space Division Multiple Access.

SIFS Short Inter-Frame Space.

TDMA Time Division Multiple Access.

UDP User Datagram Protocol.

WLAN Wireless Local Area Networks.

WMAN Wireless Metropolitain Area Networks.

WPAN Wireless Persoanl Area Networks.
WWAN Wireless Wide Area Networks.

ZRP Zone Routing Protocol.

VII

1

Introduction générale

1-Contexte

Depuis que Marconi a réussi à emmètre le premier signal radio sans fil transatlantique en 1901, la communication sans fil n'a pas cesséd'attirer l'attention des ingénieurs [38]. Le rêve d'être toujours connectéet de » couper le cordon» de tous nos équipements de communication est entrain de se réaliser à une vitesse exponentiellement croissante.

Les réseaux ad hoc peuvent être considérés comme la généralisation ultime des réseaux sans fil. Ils se créent d'une manière spontanée et éliminent le besoin d'une infrastructure fixe qui se charge de l'administration centrale du réseau. La technologie ad hoc est très utile dans les régions rurales, pour les besoins de sauvetage dans les cas de désastre et sur les champs de bataille [33]. Le domaine militaire est à l'origine des réseaux ad hoc. En outre, ces réseaux sont peu couteux et faciles à déployer. Cependant, la communication dans cet environnement engendre de nouvelles caractéristiques; une déconnexion fréquente, un débit de communication et des ressources modestes, et des sources d'énergies limitées. Pour répondre à ces besoins, plusieurs standards sans fils suivent une évolution technologique. Parmi tous ces standards, la norme 802.11 a su s'imposer comme un standard de fait des réseaux sans fil.

La littérature s'accorde à dire que les problèmes rendant 802.11 sous-optimal proviennent de la sous-couche MAC. Le rôle principal de la couche MAC, comme suggérédans le modèle OSI, est de fournir une transmission fiable entre deux stations du réseau, elle est aussi responsable de la résolution de conflits pouvant survenir lorsque différentes stations tentent d'accéder au médium de communication en même temps, de plus, leurs offrir un accès équitable.

Depuis les années 90, plusieurs solutions ont étéproposées pour résoudre les problèmes liés ^àl'accès fiable et équitable que doit fournir la couche MAC des réseaux sans fil ad hoc. Ces solutions

peuvent être classifiées dans deux grandes catégories. L'une cherche à favoriser les stations étant dans les meilleures conditions pour transmettre leurs trames. En favorisant ces stations, le protocole

MAC permet ainsi d'augmenter l'efficacitédu réseau, mais il ne garantit pas l'équitéd'accès ^àtoute les stations. L'autre cherche à fournir un accès à toutes les stations. Ces solutions sont plus équitables mais moins efficaces par rapport à celles de la première catégorie.

Dans ce travail, nous allons nous intéresser à l'étude des problèmes liés à l'équitéd'accès au médium dans MAC 802.11 dans le but de mieux comprendre les causes de ceux-ci.

2

Introduction générale

2- Méthodologie de la recherche et organisation du document

En ce qui concerne la méthodologie de la recherche, nous avons effectuédes recherches bibliographique et consultédes sites web, quelques articles et thèses, ce qui nous a permis de cerner notre recherche.

Notre travail consiste à faire une étude sur les problèmes d'équitéd'accès au canal dans les réseaux ad hoc. Pour la réalisation de ce système et pour mener à bien notre travail, nous avons adoptéun plan qui s'articule autour de quatre chapitres:

V Dans le premier chapitre nous aborderons une présentation pratique des réseaux ad hoc, ce qui nous permettra d'aborder les réseaux sans fil et leurs classifications en générale et les réseaux mobiles ad hoc (MANET) en particulier. Les différentes familles et classifications des protocoles de routage (MANET), ainsi que certains avantages et inconvénients des familles de protocoles. Pour bien comprendre chaque famille nous allons faire une description de quelques protocoles de routages représentatifs.

V Le deuxième chapitre sera consacréà l'étude de MAC 802.11. Nous allons commencer par la présentation de la norme 802.11 et ces extensions, par la suite nous allons détailler son architecture en couches et présenter les méthodes d'accès et les protocoles de la sous-couche MAC en mode DCF.

V Le troisième chapitre intitulé»Particularités de 802.11 dans un contexte ad hoc», expose quelques problèmes qui peuvent parvenir dans les réseaux ad hoc, parmi eux les problèmes d'équitéd'accès au canal, ce qui nous permettra d'aborder notre dernier chapitre.

V Le dernier chapitre intitulé»Analyse et évaluation des problèmes 802.11» sera consacréen premier lieu pour la simulation de quelques problèmes d'équitéde 802.11 et la discussion des résultats obtenu. En second lieu, sur quelques solutions apportées aux problèmes d'équité.

Nous concluons ce manuscrit avec une conclusion générale et des perspectives d'évolution.

3

Chapitre 1

Les réseaux ad hoc

1.1 Introduction

Dans ce premier chapitre, nous allons commencer par la description des réseaux sans fil et leurs classifications. Ensuite nous allons présenter les réseaux mobiles ad hoc et leurs caractéristiques ainsi que leurs domaines d'application, et certain problèmes et contraintes liées à ce type de réseaux.

Le dernier point de ce chapitre sera consacréau routage dans les réseaux mobiles ad hoc. Les protocoles de routage sont classés suivant plusieurs critères et familles et chacune de ces familles ont des avantages et inconvénients. Tout cela, ainsi qu'une description de quelques protocoles de routages représentatifs, sera détaillé.

1.2 Les réseaux sans fil

Un réseau sans fils (en anglais wireless network) est un réseau qui connecte différentes machines ou systèmes entre eux par ondes radio. Grâce aux réseaux sans fils, un utilisateur a la possibilitéde rester connectétout en se déplaçant dans un périmètre géographique plus ou moins étendu. Le

développement constant de ces réseaux sans fil a amenéla création de nouvelles normes afin de mieux interconnecter les machines.

1.3 Classification des réseaux sans fil

Les réseaux sans fil peuvent avoir diverses classifications, selon l'architecture, la taille de la zone de couverture, et la technique d'accès au canal radio.

1.3.1 Classification par type d'architecture réseaux

1. Les réseaux avec usage entier d'infrastructure de communication

Dans ce type de réseaux, un noeud ne peut accéder au réseau qu'àtravers une infrastructure de communication déployée par le réseau. Cette infrastructure peut être un point d'accès (Access Point), un pont sans fil (Wireless Bridge), une station de base (Base Station Transceiver, BTS) ou autres. Le type d'infrastructure d'accès au réseau dépend de divers paramètres dont le type d'application du réseau, l'étendue du réseau, la couverture envisagée,

4

Chapitre 1. Les réseaux ad hoc

la mobilitédes noeuds, etc.

2. Les réseaux sans infrastructure de communication

Les réseaux ad hoc sont formés dynamiquement par la coopération d'un nombre aléatoire de noeuds indépendants. Aucun pré-arrangement n'est défini sur le rôle de chaque noeud et

les noeuds prennent des décisions en fonction de la situation du réseau sans avoir recours ^àdes infrastructures préexistantes.

FIGURE 1.1 - Le modèle des réseaux mobiles sans infrastructure.

3. Les réseaux avec usage partiel des infrastructures de communication (Mesh)

Ce type de réseau utilise des infrastructures de communications pour permettre de connecter le réseau sans fil à Internet. Toutefois, à la différence des réseaux avec usage entier d'infra-structures, les réseaux Mesh n'exigent pas une infrastructure de communication au voisinage immédiat de chaque noeud. Si le noeud ne détecte pas une infrastructure dans son voisinage, il utilise la technique multisauts pour en atteindre une. Cette architecture combine les deux modes de déploiement précédemment décrits.

1.3.2 Classification par étendue de la zone de couverture

1. Les réseaux personnel sans fil (Wireless Personal Area Networks, WPAN) Les réseaux PAN sans fil permettent aux utilisateurs d'effectuer des communications de courtes portées entre des équipements personnels sans fil.

2. Les réseaux locaux sans fil (Wireless Local Area Networks, WLAN) Ces réseaux permettent l'établissement d'un réseau, qui couvre l'équivalent d'un siège d'une entreprise. Les réseaux WLAN peuvent être de type infrastructures ou ad hoc.

5

Chapitre 1. Les réseaux ad hoc

3. Les réseaux sans fil métropolitains (Wireless Metropolitain Area Networks, WMan) Ces réseaux sont à base d'infrastructure qui permettent des connexions large bande entre sites existant au sein d'une même zone métropolitaine. À titre d'exemple, on peut citer les réseaux des campus universitaires.

4. Les réseaux étendus sans fil (Wireless Wide Area Networks, Wireless Wan) Ce sont des réseaux à base d'infrastructure dont les couvertures peuvent s'étendre sur une grande zone géographique couvrant des villes, voire des pays.

1.3.3 Classification par techniques d'accès au canal radio

1. Les réseaux TDMA (Time Division Multiple Access)

L'accès multiple à répartition dans le temps est un mode de multiplexage de communication qui consiste à répartir le temps disponible entre les différents usagers.

2. Les réseaux FDMA (Frequency Division Multiple Access)

L'accès multiple à répartition en fréquence est un mode d'accès au canal radio qui consiste à répartir une bande de fréquences donnée entre diverses communications simultanées.

3. Les réseaux CDMA (Code Division Multiple Access)

Le mode d'accès CDMA permet un accès partagésimultanéau canal radio sans partager

ni le temps ni la bande de fréquences entre les différents usagers. L'idée est d'affecter ^àchaque communication une séquence unique aléatoire de pseudo-codes, ce qui permettrait de

distinguer la communication envisagée des interférents à la réception au moment du décodage.

4. Les réseaux SDMA (Space Division Multiple Access)

Cette technique d'accès combine l'utilisation des antennes dites intelligentes (Smart Antennas) et l'exploitation d'informations sur la position du mobile pour adapter le diagramme de rayonnement de l'antenne à la position de ce dernier.

1.4 Les réseaux mobiles ad hoc (MANET) 1.4.1 Définition

Un réseau ad hoc est un concept qui a fait l'objet de recherches scientifiques depuis les années 1990. Une définition proprement dite de ce qui est un réseau ad hoc est difficile à mettre au point. Dans la littérature existante, le terme est utiliséde différentes manières. L'IETF (Internet Engineering Task Force) le corps responsable pour guider l'évolution d'Internet, fournit la définition suivante :

Un réseau ad hoc mobile (MANET)¹ est un système autonome de noeuds mobiles connectés par des liens sans fil. Les routeurs sont libres de se déplacer aléatoirement et de s'organiser arbitrairement; donc, la topologie du réseau peut changer rapidement et de façon imprévisible. Un tel réseau peut opérer dans un mode autonome, ou peut être reliéà Internet. Les MANET sont utiles

6

Chapitre 1. Les réseaux ad hoc

dans beaucoup d'applications parce qu'ils n'ont pas besoin de tout support de l'infrastructure. La communication se fait directement entre les noeuds ou à travers des noeuds intermédiaires qui agissent comme routeurs.

FIGURE 1.2 - Modélisation d'un réseau ad hoc

1.4.2 Caractéristiques des réseaux mobiles ad hoc

Les réseaux ad hocs se distinguent des réseaux cellulaires par plusieurs caractéristiques. Celles-ci doivent être prises en considération dans tout processus de conception de protocoles. Elles sont entièrement spécifiées dans la RFC 2501, [39] et résumées dans les paragraphes qui suivent : [1]

· Topologie dynamique : les raisons principales aux changements de topologie dans ces réseaux sont liées à des facteurs non contrôlables, tels que la mobilitédes noeuds (figure 1.3), les interférences et le bruit; et à des facteurs contrôlables; tel que la puissance de transmission [2], le mécanisme de mise en veille des noeuds pour la préservation de l'énergie, ainsi la topologie du réseau peut changer fréquemment d'une manière non prévisible.

· Contrainte d'énergie : les noeuds dans un réseau ad hoc sont alimentés typiquement par des batteries dont la capacitéen puissance est souvent limitée. Par conséquent, une batterie ne peut pas satisfaire les demandes d'énergie d'un noeud pour un fonctionnement normal durant une période de temps raisonnable.

· Capacitédes liens limitée et variable : celle-ci est limitée, par rapport à la capacitédes réseaux filaires, et peut varier au cours du temps pour au moins deux raisons principales : le changement des conditions de propagation et la variation des distances entre les noeuds.

1. MANET, acronyme de Mobile Ad hoc NETworks, est le nom d'un groupe de travail de l'IETF, crééen 1998, chargéde normaliser des protocoles de routage basés sur la technologie IP pour les réseaux ad hoc.

7

Chapitre 1. Les réseaux ad hoc

· Sécuritéphysique limitée : les réseaux ad hoc mobiles sont plus vulnérables par rapport aux autres réseaux filaires et cellulaires. Cette vulnérabilitéest due essentiellement à la nature du médium de propagation sans fil qui rend possibles certaines attaques malicieuses allant de l'écoute clandestine passive aux interférences actives. D'autres attaques redoutables, dues à la topologie du réseau, peuvent aussi être envisagées comme par exemple l'attaque WormHole² [3].

FIGURE 1.3 - La mobilitédans les réseaux ad hoc

1.4.3 Domaine d'application [4]

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

Parmi les domaines d'application les plus fondamentaux on peut citer :

· Domaine militaire : Lors d'interventions en milieu hostile, il peut être difficile ou trop encombrant d'utiliser un réseau à infrastructure. Les réseaux sans fil sont parfaitement bien adaptés à ce type d'environnement oùles déplacements restent peu rapides et peu soutenus.

· Urgences et catastrophes naturelles : Il sera indispensable de disposer rapidement d'un réseau qui remplace le réseau détruit pour organiser les secours et les opérations de sauvetage.

· Les applications industrielles : Des scénarios plus complexes dans le domaine industriel peuvent former un MANET.

· Aéronautique : Ce système peut être vu comme un réseau ad hoc mobile dont les noeuds sont les avions civils en vol. Grâce à plusieurs sauts successifs au travers d'avions relais, chaque avion doit pouvoir joindre le sol sans être à portée directe d'une station.

2. Dans une attaque WormHole, un attaquant reçoit des paquets dans un point du réseau, puis les encapsule vers un autre attaquant pour les réintroduire dans le réseau.

8

Chapitre 1. Les réseaux ad hoc

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

1.4.4 Problèmes et contraintes spécifiques des réseaux sans fils

De par la nature du canal radio, un certain nombre de problèmes se posent qui ne trouvent pas d'équivalent dans le monde filaire. On peut citer en particulier :

- Un débit plus faible : Par rapport à un équivalent filaire. Il faut donc que la gestion du réseau occupe la part la plus réduite possible des maigres ressources en bande passante.

- Une atténuation rapide du signal : En fonction de la distance (bien plus rapide que sur un câble) qui induit l'impossibilitépour un émetteur de détecter une collision au moment même oùil transmet. Dans un réseau filaire, un émetteur sait qu'il y a collision quand le signal qu'il lit sur le câble est différent de celui qu'il cherche à émettre . Dans un réseaux sans fil, un signal venant d'un autre noeud est tellement atténuépar la distance qu'il ne provoquera que des perturbations négligeables par rapport au signal émis localement.

- Les interférences : Les liens radios ne sont pas isolés et le nombre de canaux disponibles est limité, il faut donc les partager. Les interférences peuvent être de natures diverses. Par exemple, des émetteurs travaillant à des fréquences trop proches peuvent interférer entre eux.

L'environnement lui-même peut également produire des bruits parasites (certains équipements électriques, certains moteurs,.. .) qui interfèrent avec les communications. Il peut aussi déformer le signal et le rendre rapidement incompréhensible à cause des phénomènes d'atténuation, de réflexion ou de chemins multiples (l'atténuation et la réflexion varient en fonction des matériaux rencontrés; le problème des chemins multiples apparaît lorsque des réflexion d'une même onde par des chemins différents arrivent de manière décalée dans le temps au récepteur, se chevauchent, et forment un tout plus difficile à analyser).

Ces problèmes font que les taux d'erreurs de transmission dans les réseaux radio sont nettement plus élevés que dans les réseaux filaires. Cela a un impact non négligeable sur les protocoles de niveau supérieur. TCP (Transmission Control Protocol)en particulier est particulièrement vulnérable, car il interprète les pertes de paquets comme étant dues à de la congestion sur le réseau. Quand TCP détecte de la congestion, il cherche à l'atténuer en réduisant la taille de sa fenêtre d'émission [5]. Malheureusement, dans le cas présent, c'est exactement l'inverse qu'il faudrait faire, les paquets perdus doivent être réémis au plus vite. TCP Westwook [6] est une variante de TCP qui cherche à corriger ce problème en estimant la bande passante de bout en bout et en gérant différemment la réduction de la taille de sa fenêtre.

Il faut ajouter également que des interférences ou des changements persistants dans l'en-vironnement conduisent à une grande versatilitédes liens, qui peuvent apparaître ou être coupés de manière durable à tout moment.

9

Chapitre 1. Les réseaux ad hoc

- La puissance du signal : Non seulement elle est rapidement atténuée avec la distance, mais elle est également limitée par des réglementations très strictes. Un émetteurs ne peut donc dépasser une certaine puissance à l'émission.

- Contrainte d'énergie : Les applications relatives aux réseaux sans fil ont en général un caractère nomade et tirent leur autonomie de batteries. La puissance d'émission a un impact important sur la quantitéd'énergie utilisée, tout en la réduisant.

- Une faible sécurité: Le canal radio est très vulnérable aux attaques passives. Les protections ne pouvant pas se faire de manière physique, elles doivent être mises en place de manière logique, avec de la cryptographie ou éventuellement des antennes très directionnelles. Mais le canal radio restera vulnérable à un brouillage massif (attaque par déni de service (DDoS attack)).

- La mobilité: L'impact de la mobilitéest important à différents niveaux; du point de vue des couches basses (Physique et MAC »Media Access Control»), l'affectation des fréquences à des zones géographiques est inconcevable; d'autre part les mécanismes d'accès au médium utilisant des horloges globales seront également inutilisables (TDMA par exemple a besoin d'une grande synchronisation des horloges qui est impossible dans ce contexte). À un niveau plus élevé, dans les réseaux à stations de base (en particulier à grande échelle comme dans les réseaux de téléphonie mobile), le routage est effectuédans la partie fixe du réseau. Dans le cas des réseaux ad hoc, l'ensemble du routage doit fonctionner sur les mobiles et de façon totalement distribuée. Cela nécessite de nouveaux algorithmes et les contraintes à leur réalisation sont plus importantes.

- La qualitéde service : De nombreuses applications ont besoin de certaines garanties relatives par exemple au débit, au délai ou encore à la gigue. Dans les réseau ad hoc, ces garanties sont très difficiles à obtenir. Ceci est dùà la nature du canal radio d'une part(interférences et taux d'erreur élevés) et au fait que des liens entre des mobiles peuvent avoir à se partager les ressources (alors qu'en filaire, deux liens sont par définition indépendants). De ce fait, les protocoles de qualitéde service habituels (par exemple IntServ/RSVP ou Diff-Serv) ne sont pas utilisables directement dans le mode ad hoc et des solutions spécifiques doivent être proposés [7].

1.5 Le routage dans les réseaux MANET

Le routage est une méthode à travers laquelle une information donnée est transitée depuis un émetteur vers un destinataire. Le problème du routage ne se résume pas seulement à trouver un chemin entre les deux noeuds du réseau, mais encore à trouver un acheminement optimal et la transmission des paquets de données de qualité.

Chapitre 1. Les réseaux ad hoc

1.5.1 Classification des protocoles de routage ad hoc

Les protocoles de routage pour les réseaux ad hoc peuvent être classés suivant plusieurs critères. Le premier concerne le type de vision qu'ils ont sur le réseau et les rôles qu'ils accordent aux différents mobiles.

1.5.1.1 Routage hiérarchique, plat et localisation géographique

1. Les protocoles de routage ? à plat >-

La décision d'un noeud de router des paquets d'un autre noeuds dépendra de sa position car tous les noeuds sont considérés égaux. (figure 1.4).

2. Les protocoles de routage ? hiérarchique >-

La caractéristique du protocole de routage hiérarchique (figure 1.5) est le groupement mul-tiniveaux et la division logique des noeuds mobiles. Le réseau est diviséen groupes, et un représentant pour chaque groupe est élu. Les noeuds d'un groupe physique diffusent leurs informations de lieux entre eux et le chef de groupe récapitule l'information de son groupe et l'envoie aux chefs de groupes voisins [9].

3. Les protocoles de routage avec localisation géographique

L'ajout de tels protocoles globaux de localisation (Global Position) est de déterminer l'em-placement du mobile. En fait, le GPS (Global Position System) peut fournir de l'information sur l'emplacement avec une précision de quelques mètres. Il fournit aussi le réglage universel. Les satellites sont généralement utilisés pour accomplir cette tâche et tout dysfonctionnement de ces derniers affecte le réseau [8].

FIGURE 1.4 - Routage »àplat».

10

11

Chapitre 1. Les réseaux ad hoc

FIGURE 1.5 - Routage »hiérarchique».

1.5.1.2 Protocoles de routage à état de liens et à vecteur de distance

1. Protocoles à vecteurs de distance

Les algorithmes de routage à vecteur de distance (Bellman-Ford) transmettent d'un noeud à l'autre des copies périodiques d'une table de routage. Ces mises à jour régulières entre les noeuds permettent de communiquer les modifications de la topologie. Chaque noeud reçoit une table de routage des noeuds voisins auxquels il est directement connecté. L'algorithme cumule les distances afin de tenir à jour la base de données contenant les informations de topologie du réseau.

2. Protocoles à état de liens

Un protocole de routage à état de liens utilise un algorithme plus efficace (Dijkstra ou Shortest Path First). Les routeurs collectent l'ensemble des coûts des liens et construisent de leur point de vue l'arbre de tous les chemins. Les meilleures routes sont alors intégrées à la table de routage.

1.5.2 Les différentes familles de protocoles de routage MANET

Dans les travaux menés à l'IETF, plusieurs familles de protocoles se sont rapidement élaboré. Chaque protocole peut ainsi être classifiéen tant que proactif, réactif, ou hybride.

1. Les protocoles proactifs

Les protocoles de routage proactifs pour les réseaux mobiles ad hoc (MANET), sont basés sur le même principe de routage que les réseaux filaires. Ils maintiennent des tables de routage contenant de informations sur la topologie du réseau. Pour tout changement topologique, ils déclenchent des mises à jour dans le réseau afin d'avoir une vision globale du réseau. Les routes dans ce type de routage sont calculées à l'avance et tout noeud dispose à tout moment d'une route vers toute destination accessible du réseau. L'inconvénient de tels protocoles est la signalisation qui peut affecter la bande passante. L'avantage est qu'une route est toujours disponible entre une source et une destination sans pour autant déclencher des mécanismes de recherches de routes. Cependant, de tels protocoles présentent certaines défaillances dans

12

Chapitre 1. Les réseaux ad hoc

le cas de changement topologique fréquent et rapide. Un exemple de ce type de routage est le protocole (OLSR).

2. Les protocoles réactifs ou à la demande

Contrairement aux protocoles proactifs, les protocoles réactifs ne calculent la route que sur demande. La découverte de route RD (Route Discovery) se fait à travers des messages d'inon-dation; le noeud source, qui est à la recherche d'un chemin vers la destination, diffuse par inondation une requête dans le réseau. Lors de la réception de la requête, les noeuds intermédiaires essaient de faire apprendre le chemin au noeud source, et de sauvegarder la route dans la table envoyée. Une fois la destination atteinte, elle peut envoyer une réponse en utilisant le chemin tracépar la requête. Parmi les protocoles de routage réactif on cite (AODV).

3. Les protocoles de routages hybrides

Les protocoles hybrides combinent les approches réactive et proactive. Le principe est de connaitre le voisinage de manière proactive jusqu'àune certaine distance (par exemple trois ou quatre saut), au-delàde cette zone, une recherche réactive sera effectuée. Avec ce système, chaque noeud dispose immédiatement des routes de sa zone (caractérisépar le nombre de sauts), et lorsque la recherche doit être étendue en dehors de sa zone, chaque noeud qui reçois le paquet pourra répondre immédiatement si le destinataire est dans son propre voisinage, sinon il propage à son tour de manière optimisée le paquet hors de sa zone proactive. Un exemple de ce type de routage est le protocole (ZRP).

13

Chapitre 1. Les réseaux ad hoc

1.5.3 Avantages et inconvénients des familles des protocoles de routages MANET

Le tableau ci-dessous présente les principaux avantages et inconvénients des différents types de protocoles de routage dans les réseaux mobiles ad hoc.

Protocoles	Avantages	Inconvénients
Proactifs	Une route est toujours dis- ponible entre une source et une destination, rapide ce qui implique le gain du temps.	Le cout, dûau maintien de la topologie, génère une consommation continuelle de la bande passante.
Réactifs	La génération de trafic de contrôle ne se fait que lors- qu'il soit nécessaire.	L'inondation est un mécanisme très couteux, génération de délai important pour ouvrir une route entre deux nouds.
Hybrides	Il s'adapte bien au grands réseaux	Il combine les in- convénients des deux protocoles proactifs et réactifs.

TABLE 1.1 - Comparaison des protocoles MANET.

1.5.4 Description de quelques protocoles de routages représentatifs

Les protocoles décrits par la suite 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.

1. Optimized Link State Routing (OLSR)

OLSR [10] est un protocole proactif à état de liens. Afin de maintenir à jour les tables de routage, chaque noeud implémentant OLSR diffuse régulièrement des informations sur son propre voisinage. Ces informations sont suffisantes pour permettre à chaque noeud de reconstruire une image du réseau et de trouver une route vers n'importe quelle destination. Mais contrairement à des protocoles tel qu'OSPF¹, cette diffusion ne se fait pas par une simple inondation (oùchaque noeud retransmet simplement chaque nouveau paquet qu'il reçoit); OLSR optimise la diffusion grâce au système des relais multipoints (Multi-Points Relays : MPR).

Chaque noeud choisit dans ses voisins directs un sous-ensemble minimal de noeuds qui lui permettent d'atteindre tous ses voisins à deux sauts (voir figure 1.6). La diffusion des informations sur les liens utilisés pour le routage se fait ensuite uniquement par les relais multipoints; la couverture totale du réseau est assurée tout en limitant sensiblement le

14

Chapitre 1. Les réseaux ad hoc

nombre de réemissions. Afin de choisir ses relais multipoints, un noeud a besoin de connaitre complètement la topologie de son voisinage à deux sauts; cela est réaliségrâce à l'envoi périodique des paquets »hello» contenant la liste des voisins à un saut connus.

FIGURE 1.6 - Relais multipoints.

2. Ad-hoc On Demand Distance Vector (AODV)

AODV [11] est un protocole basésur le principe des vecteurs de distance et appartient à la famille des protocoles réactifs. Les protocoles à vecteur de distance sont en général sujets au problèmes de boucle et de comptage à l'infini de l'algorithme de Bellman-Ford qu'ils utilisent (certaines parties du réseau se trouvent isolées du reste, et les noeuds les composant croient qu'ils peuvent atteindre les noeuds desquels ils sont coupés en passant par leurs voisins. Il s'en suit un phénomène de bouclage dans lequel les noeuds 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. Quand une application a besoin d'envoyer des paquets sur le réseau et qu'une route est disponible dans la table de routage, AODV ne joue aucun rôle. S'il n'y a pas de route disponible, i1 va par contre en rechercher une. Cette recherche commence par une inondation de Paquets Route Request (RREQ). Chaque noeud traversépar un RREQ en garde une trace dans son cache et le retransmet. Quand les paquets de recherche de route arrivent à la destination (on a un noeud intermédiaire qui connait lui-même une route valide jusqu'àla destination), alors un paquet de réponse est généré(RREP) et il est envoyépar le

1. Open Shortest Path First (OSPF) est un protocole de routage interne IP de type à état de liens '. Il a ^étédéveloppéau sein de l'IETF à partir de 1987. La version actuelle d'OSPFv2 est décrite dans la RFC 2328 en 1997.

15

Chapitre 1. Les réseaux ad hoc

chemin inverse, grâce aux informations gardées dans les caches des noeuds traversés par les RREQ (voir figure 1.7).

AODV dispose d'un certain nombre de mécanismes optimisant son fonctionnement. L'inon-dation se fera par exemple au premier essai dans un rayon limitéautour de la source, et si aucun chemin n'est trouvé, alors elle sera étendue à une plus grande partie du réseau. En cas de rupture de certains liens, AODV va essayer de reconstruire localement les routes affectées en trouvant des noeuds suppléants (cette détection de rupture peut d'ailleurs se faire gràace à un mécanisme optionnel de paquets hello diffusés aux voisins directs uniquement). Si une reconstruction locale n'est pas possible, alors les noeuds concernés par la rupture des routes utilisant ce lien sont prévenus de sorte qu'ils pourront relancer une nouvelle phase de reconstruction complète.

FIGURE 1.7 - Recherche de route par inondation »AODV».

3. Zone Routing Protocole(ZRP)

Le protocole ZRP [12] est parmi les protocoles hybrides les plus citédans la littérature, ^àmi-chemin entre les deux familles de protocoles (proactif et réactif). Ainsi, chaque noeud

maintient une table de routage, dont les données sont régulièrement émises en diffusion pour tous les noeuds qui lui sont distants de moins d'une valeur (ñ) prédéfinie (routage proactif dans cette zone). Pour atteindre tout autre noeud qui n'apparaîtrait pas dans sa table de routage (une distance supérieure à (ñ)), un noeud a recours à un protocole de routage de type réactif, comme indiquédans la figure 1.8.

Ce type de protocole fournit un assez bon compromis en termes de diffusion pour les mises à jour. Cette tentative pour cumuler les qualités des deux approches se place en intermédiaire plus qu'en solution, parce qu'elle est moins efficace que les algorithmes de routage de base, en forte mobilitéou avec beaucoup de stations.

16

Chapitre 1. Les réseaux ad hoc

FIGURE 1.8 - Exemple d'une zone de routge avec ñ = 2.

1.6 Conclusion

L'étude effectuée sur les réseaux sans fil et en particulier sur les réseaux mobiles ad hoc nous a permis de connaître leurs différentes caractéristiques (Topologie dynamique, contrainte d'énergie, capacitédes liens limitée et variable, sécuritéphysique limitée). Nous avons constatéque leur apparition a certes facilitéla mise en oeuvre d'applications mobiles et ne supportant pas d'infrastructure préexistante (telles que les applications militaires et urgences et catastrophes naturelles), mais en revanche, a laisséémerger un bon nombre de problèmes.

Dans l'étude des protocoles de routage, nous avons commencépar présenter les trois classes de protocoles de routages selon le type de vision qu'ils ont sur le réseau : routage hiérarchique, plat et localisation géographique, et les trois familles : Proactifs, Réactifs et Hybrides, ainsi que les politiques et les méthodes d'acheminement sur lesquelles ils reposent, et leurs avantages et inconvénients. Par la suite nous avons donnéun exemple de protocole pour chacune des trois classes (OLSR, AODV, ZRP). D'autres protocoles existent évidemment, mais dans le cadre de note travail, nous contentons de ces protocoles, car le plus important pour nous est de comprendre le routage d'une manière globale, afin de mieux comprendre notre sujet d'étude. Le chapitre suivant vient pour mettre en claire le fonctionnement du protocole MAC 802.11.

17

Chapitre 2

MAC IEEE 802.11

2.1 Introduction

Dans ce deuxième chapitre, qui est dédiéà l'étude de MAC 802.11, nous allons premièrement présenter la norme IEEE 802.11 et ses extensions, ainsi que son architecture en couches. Ensuite nous allons paraphraser les méthodes d'accès et les protocoles de la sous-couche MAC en mode DCF.

2.2 Présentation de la norme IEEE 802.11

En février 1980, IEEE (Institute of Electrical and Electronics Engineers) a crééun comité, baptisé802 en raison de sa date de création, dont la principale tâche consiste a standardiser les réseaux locaux. Le groupe a étéinitiéen 1990, et la norme IEEE 802.11 encore appelée Wi-Fi par abus de langage et en référence avec le nom de la certification a vu le jour en 1997 [13, 14].

Les débits possibles varient entre 1 et 54 Mbit/s et les portées prévues varient entre quelques dizaines et quelques centaines de mètres. Cette norme est prévue pour fonctionner dans deux contextes; infrastructure et ad hoc [15].

Les principales fonctions du standard IEEE 802.11 sont :

1. La description des fonctions et des services nécessaires pour permettre aux mobiles d'opérer aussi bien dans un réseau à station de base (infrastructure) que dans un réseau autonome (ad hoc);

2. La définition des procédures de livraison asynchrones des paquets de la couche MAC;

3. La coexistence avec les autres normes sans fil, par exemple le Bluetooth ;

2.3 Extensions de la norme IEEE 802.11

Depuis 1997, des révisions ont étéapportées à cette norme, lui ajoutant des modes de fonctionnement plus performants. Les principales extensions proposées sont décrites dans le tableau suivant : [[16, 17]]

18

Chapitre 2. MAC IEEE 802.11

Norme	Caractéristiques
802.11	Dates 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
802.11a	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écompatibilité8 canaux radio
802.11b	Date de normalisation	1999
	Bande de fréquence	204 GHz
	Débit	théorique 11 Mbps - réel 6 Mbps
	Portée théorique	100 m
		Spécificité3 canaux radio
802.11e	Amélioration de la qualitéde service (niveau MAC) pour le support audio et vidéo (en 2005)
802.11g	Date de normalisation	2003
	Bande de fréquence	2.4 GHz
	Débit	théorique 54 Mbps - réel 30 Mbps
	Portée théorique	20 m
		Spécificitécompatibilité20 canaux
802.11h	Adaptation de 802.11a aux normes d'émission électromagnétiques européennes
802.11i	Amélioration de la sécuritédes transmissions sur les bandes de fréquences 2.4 GHz et 5 GHz
802.11k	Amélioration de la gestion radio (évite la surcharge et réduit les interférences) en 2007
802.11n	Date de normalisation	2007
	Bande de fréquence	2.4 et 5 GHz
	Débit	théorique 540 Mbps - réel 100 Mbps
	Portée théorique	90 m
		Spécificité26 canaux radio

TABLE 2.1 - Les différentes extensions de la norme IEEE 802.11

Pour toutes ces versions, la sécuritéde connexion est assurée par une carte SIM spécifique avec authentification qui permet une large mobilitéet les télépayements. Les débits de données peuvent atteindre, sous réserve, 11 Mbps à 220 mètres et 1 Mbps à 1 km (en vue directe).

La norme 802.11e offre des possibilités de qualitéde service (QoS) au niveau de la couche liaison de données de 802.11. Elle définit ainsi les besoins des différents paquets en terme de bande passante et de délai de transmission de telle manière à permettre des flux prioritaires.

2.4 Architecture en couches

La norme IEEE 802.11 définit les deux premières couches (basses) du modèle OSI, à savoir la couche physique et la couche liaison de données. Cette dernière est elle-même subdivisée en deux sous-couches, la sous-couche LLC (Logical Link Control) et la couche MAC (Medium Access Control).

Le tableau suivant (Tableau 2.2) illustre l'architecture du modèle proposépar le groupe de travail 802.11 comparée à celle du modèle OSI [18].

19

Chapitre 2. MAC IEEE 802.11

OSI Layer 2 Data Link Layer	802.11 Logical Link Control (LLC)
	802.11 Medium Access Control (MAC)
OSI Layer 1 Physical Layer (PHY)	FHSS	DSSS	IR	Wi-Fi 802.11b	Wi-Fi 802.11g	Wi-Fi5 802.11a

TABLE 2.2 - Modèle en couches de l'IEEE 802.11.

L'une des particularités de cette norme est qu'elle offre plusieurs variantes au niveau physique, tandis que la partie liaison est unifiée.

Bien que la norme 802.11 d'origine n'ai défini que trois couches physiques, les couches FHSS, DSSS, et IR, l'ajout ultérieur de Wi-Fi, de Wi-Fi 5 et de IEEE 802.11g n'a pas entraînéde changements radicaux dans la structure de la couche MAC.

Chaque couche physique 802.11/a/b/g est divisée en deux sous-couches:

· La sous-couche PMD (Physical Medium Dependent) qui gère l'encodage des données et effectue la modulation;

· La sous-couche PLCP (Physical Layer Convergence Protocol) qui s'occupe de l'écoute du support et fournit un CCA (Clear Channel Assessment) à la couche MAC pour lui signaler que le canal est libre.

2.4.1 La couche physique

Initialement, le standard IEEE 802.11 permet l'utilisation de trois couches physiques différentes (FHSS, DSSS et IR), auxquelles 802.11a a ajoutéODFM [19] :

- FHSS : Frequency Hoping Spread Spectrum. La plupart des interférences nuisibles aux transmissions radio n'agissent que sur des bandes de fréquence assez étroites. Si de telles interférences ont eu lieu au moment de transmission, le signal sera fortement dégradé. Une technique pour protéger le signal consiste à régulièrement changer de fréquence (figure 2.2). Les paquets envoyés sur la bande perturbée seront affectés, mais ils ne représenteront plus qu'une minoritédes transmissions et leur retransmission sera moins coûteuse. L'émetteur et le récepteur doivent connaître à l'avance le séquencement des sauts de fréquence, mais des informations portées par les paquets permettent à un mobile s'attachant au réseau de savoir à partir d'un paquet qu'il reçoit l'état du déroulement de la séquence .

- DSSS : Direct Sequence Spread Spectrum. Pour lutter contre les interférences importantes mais n'affectant que des plages de fréquences assez étroites, il existe la technique de l'étalement de spectre. Des manipulation sur le signal occuperont un spectre plus large. À la réception, une manipulation inverse est effectuée (figure 2.1). Cette technique est moins sensible aux interférences dues aux fréquences parasites à faible largeur spectrale.

20

Chapitre 2. MAC IEEE 802.11

FIGURE 2.2 - Changement de fréquence régulier pour réduire l'impact des interférences.

FIGURE 2.1 - Étalement du spectre.

- JR : Infra Red. (qui sera pas détaillédu fait de son absence du marché).

- OFDM : Orthogonal Frequency Division Multiplexing. Lorsqu'un signal radio est émis, l'onde sera réfracté, réfléchi et donc se divise sur les divers obstacles rencontrés. À l'arrivée, plusieurs chemins peuvent être empruntés, et leurs temps de parcours n'étant pas forcément les mêmes, multiples réfractions/réflexions d'une même onde s'interfèrent entre elles. Plus la différence de temps du parcours sera grand vis à vis de la durée de transmission totale du symbole, plus les chances que des réflexions/réfractions des symboles consécutifs se chevauchent. Pour augmenter le débit, l'approche traditionnelle consiste à réduire la durée d'un symbole, mais cela augmente aussi les problèmes de chemin multiple. OFDM propose donc d'utiliser des symboles plus longs, mais envoyés en parallèle.

Le tableau suivant résume les avantages et les inconvénients des différentes technologies de transmission du 802.11 :

21

Chapitre 2. MAC IEEE 802.11

Technique de transmission	Avantages	Inconvénients
DSSS	- Propose des vitesses de transmis- sions plus importantes.	- L'utilisation d'un seul canal pour la transmission, rend le système DSSS plus sensibles aux interférences.
FHSS	- Empêche une perte totale du si- gnal, grâce à la technique de trans- mission par saut. - Elle constitue une solution efficace dans un environnement oùil y a beaucoup de multi-trajets.	- faible largeur de bande par ca-nal ne lui permettant pas d'at-teindre des vitesses de transmissions élevées. - Utilisation de toute la largeur de bande, ce qui implique une charge supplémentaire sur le réseau.
OFDM	- Permet d'atteindre des vitesses de transmission jusqu'à54 Mbps pour la 802.11a et la 802.11g. -Offre un mécanisme de correction d'erreurs sur l'interface physique.
Infrarouge		- La transmission se fait avec une longueur d'onde très faible. - Une traversée des obstacles (murs, plafonds, cloisons...) n'est pas possible.

TABLE 2.3 - Comparaison entre les différentes technologies de transmission du 802.11.

2.4.2 La couche liaison de données

La couche liaison de données du protocole 802.11 est composée essentiellement de deux sous-couches :

- Logical Link Control (LLC) ; elle permet de fiabiliser le protocole MAC par un contrôle d'erreur et un contrôle de flux. La couche LLC utilise les mêmes propriétés que la couche LLC 802.11. Il est de ce fait possible de relier un WLAN à tout autre réseau local appartenant à un standard de l'IEEE.

- Médium Access Control (MAC) ; définit le protocole d'accès au support et est spécifique de L'IEEE 802.11.

2.5 Étude du protocole MAC 802.11

Le protocole MAC IEEE 802.11 peut opérer suivant deux configurations selon le cas oùle réseau est liéà une infrastructure ou autonome (Ad hoc). Et définit deux mode d'accès au canal : le mode DCF (Distributed Coordination Function) qui constitue le mode d'accès de base. Le mode optionnel porte le nom de PCF (Point Coordination Function).

22

Chapitre 2. MAC IEEE 802.11

DCF est basésur le mécanisme CSMA/CA (Carrier-Sense Multiple Acces with Collision Avoidance), conçu initialement pour le support des transmissions asynchrones de données. DCF peut aussi bien fonctionner en mode ad hoc qu'en mode infrastructure. Le mode PCF, basésur le pol-ling¹ des stations de façon centralisée sous la supervision d'une entitécentrale, ne fonctionnant ainsi qu'en mode infrastructure ou l'entitécentrale n'est autre que le point d'accès. Le point d'accès envoie des trames pour inviter les stations à émettre, la station répond ensuite par une trame de données si elle désire émettre, sinon elle passe la main. PCF a étéprincipalement conçu pour les transmissions synchrones, c'est-à-dire sensibles au délai.

2.5.1 Méthodes d'accès

1. Mode PCF Cette méthode d'accès est développée pour les services à contraintes temporelles qui sont gérés par une station de base fixe qui indiquera à chacune des méthodes qui lui sont rattachés, fonctionnant en mode DCF, à quel moment ils sont autorisés à émettre ou à recevoir leurs paquets de données. Cette méthode est particulièrement adaptée à la transmission de données audio ou vidéo .

2. Mode DCF Cette méthode d'accès au support est la méthode d'accès élémentaire aux 802.11, elle se base sur le principe d'égalitédes chances au support de transmission pour tous les utilisateurs. Elle fonctionne avec deux modes basique CSMA/CA (Carrier Sense Multiple access/Collision Avoidance) et celui en mode RTS/CTS (Request To Send/Clear To Send).

2.5.2 Protocoles de la sous-couche MAC en mode DCF

Le mode DCF est le mode d'accès de basse de la sous-couche MAC 802.11 qui utilise plusieurs techniques d'accès au medium pour résoudre la contention entre les différents émetteurs.

1. Algorithme BeB (Procédure de Backoff)

BeB (Binary Exponential Backoff)[20] est un algorithme exponentiel binaire qui a pour fonction de doubler la taille de la fenêtre de contention CW (Contention Window) à chaque échec de transmission d'un paquet suivant l'allure exponentielle comme il est montrédans la figure (2.3). La valeur du Backoff est alors tirée au sort dans une plus grande fenêtre de contention afin de réduire le risque que les stations qui ont subi une collision, de prendre la même valeur de Backoff. Elle est calculée à l'aide de la relation suivante :

BackoffTime = Random() × aSlotTime

- BackoffTime représente la valeur du Backoff;

- aSlotTime représente la durée d'un slot de temps défini par la couche physique de la norme;

1. Le Polling est une méthode d'accès qui désigne un matériel appeléprimaire, contrôleur ou maître comme administrateur de l'accès au canal.

23

Chapitre 2. MAC IEEE 802.11

- Random() est un nombre aléatoire choisi uniformément entre 0 et la taille de la fenêtre de contention CW.

L'augmentation de la taille de CW est bornée par la valeur _CWmax. Elle se stabilise sur cette valeur au bout de nbEssaiMin (nombre minimum de retransmissions). Si l'émission est toujours issue d'un échec au bout de nbEssaiMax (nombre maximum de retransmissions), le paquet sera détruit et la station traite le paquet suivant dans sa file d'attente. Par contre, si la transmission est réussie, la borne supérieure de la fenêtre CW est réinitialisée à la valeur initial CWmin.

FIGURE 2.3 - Exemple de backoff exponentiel.

2. Protocole CSMA/CA

CSMA/CA [19] (Carrier Sense Multiple access with Collision Avoidance) est un mécanisme d'écoute de la porteuse à accès multiple avec évitement de collision. L'idée retenue pour 802.11 est donc, lorsque le canal devient libre, d'attendre une période de durée aléatoire supplémentaire appelée backoff avant d'émettre. Ce mécanisme s'applique lorsque le canal devient libre aussi bien après une de nos propres émissions qu'après toute autre émission.

Ainsi, si plusieurs mobiles veulent émettre, il y a peu de chances pour qu'ils aient choisi la même durée. Celui qui a choisi le plus petit backoff commence à émettre, et les autres remarquent qu'il y a de l'activitésur le canal et attendent. la figure 2.4 schématise ce qui se passe lorsque deux mobiles à portée de communication veulent émettre vers un troisième et que le canal devient libre.

Lorsque le canal devient libre, il doit attendre une période DIFS (DCF Inter-Frame Space). Si le canal est restélibre durant toute cette période, les mobiles qui veulent émettre choisissent

24

Chapitre 2. MAC IEEE 802.11

un backoff aléatoire expriméen un nombre de time slots. Dans l'exemple de la figure 2.4, le mobile 1 a tiré3 et le mobile 2 a tiré5. Une fois ce tirage effectué, tant que le canal reste libre, les mobiles décrémentent leur backoff. Dès que l'un d'eux a terminé, il émet. L'autre mobile, dès qu'il détecte le regain d'activitésur le canal arrête la décrémentation de son backoff et entre en période de defering.

Il faut noter que le temps de pause qui sépare un paquet de données de son acquittement est appeléSIFS (Short Inter-Frame Space) et qu'il est plus court que DIFS. Le mobile en

période de defering ne pourra reprendre la décrémentation de son backoff que si le canal est ^ànouveau libre pendant DIFS. Le fait que SIFS soit plus court empêche que la décrémentation

ne reprenne de manière inopportune entre les données et leur acquittement. Lorsque les données du mobile 1 ont étéacquittées et que DIFS s'est écoulésans activitésur le canal, le mobile 2 peut reprendre la décrémentation de son backoff. Ici, aucun autre mobile ne vient l'empêcher de terminer et il peut donc envoyer ses données.

FIGURE 2.4 - Le backoff et le defering.

3. Mécanisme RTS/CTS

RTS/CTS [20] (Request To Send/Clear To Send) est une technique du contrôle d'accès optionnelle par réservation du canal avec des paquets de contrôle RTS et CTS, il est prop^osépour raffiner le mode basique (CSMA/CA) pour protéger les paquets de données contre les

collisions. Une station désirant émettre une trame de données, envoie au noeud destinataire une requête RTS (Request To Send) en lui demandant l'autorisation d'émission. RTS contient l'information de l'adresse de la destination ainsi que le champ de duration. À la réception de l'autorisation CTS, l'émetteur transmet sa trame de données (ou ses fragments). S'il y a échec de transmission du RTS, du CTS ou absence d'accuséde réception, toute la procédure doit être reprise (Figure 2.5).

Afin d'améliorer le contrôle d'accès au canal avec le mode RTS/CTS. NAV (Network Allocation Vector ou vecteur d'allocation), est utilisé. Les paquets RTS et CTS portent dans

25

Chapitre 2. MAC IEEE 802.11

leurs champs une indication de la durée de transmission totale restante qui représente le cycle de transmission en cours. De cette manière, les mobiles dans le voisinage qui reçoivent RTS ou CTS mettent leur NAV à la durée correspondante, et n'accèdent au canal qu'une fois le NAV est épuisé. Comme les collisions ne peuvent se produire que sur les paquets RTS ou CTS, ce mécanisme fournit une excellente protection pour les trames de grande taille. En contre parti, RTS/CTS introduit un overhead (perte de bande passante) et un délai de transmission plus important.

Pour remédier à cet inconvénient, la norme 802.11 a maintenu le mode DCF basique et propose de laisser le mode RTS/CTS en option, ce dernier est conditionnée par la taille de la trame de données qui doit dépasser un certain seuil, RTS threshold.

FIGURE 2.5 - Accés au médium en mode RTS/CTS.

4. Mécanisme EIFS

Dans la configuration présentée sur la figure 2.6, le noeud B détecte la porteuse de l'émetteur C sans pour autant comprendre ses messages (le signal est trop faible pour être décodé, mais suffisamment fort pour être reconnu comme tel). Les paquets envoyés par le récepteur ne sont quant à eux pas détectés du tout par le noeud de gauche (B). Dans cette situation, 802.11 impose l'utilisation d'un Extended Inter Frame Spacing (EIFS), afin d'éviter une collision au niveau de l'émetteur au moment du CTS et de l'acquittement par le récepteur. la figure 2.7 détaille ce qui se passe : L'émetteur envoie tout d'abord un paquet de contrôle RTS. Ce paquet est reçu par le récepteur, qui répondra par un CTS. Le noeud de gauche (B), lui, a détectéde l'activitéau moment du RTS mais sans comprendre le paquet. Le mécanisme de defering présentéprécédemment l'empêche d'émettre pendant l'envoi du RTS (canal occupé) et pendant une période DIFS consécutive (on est toujours obligéd'attendre que la canal ait étélibre pendant DIFS pour émettre). Mais DIFS est plus court que SIFS+CTS. Si jamais le mobile de gauche avait terminéde décrémenter son backoff trop vite, il aurait pu émettre pendant le CTS, causant une collision au niveau de l'émetteur. Pour protéger le CTS (et

26

Chapitre 2. MAC IEEE 802.11

de manière similaire l'acquittement), 802.11 impose qu'un noeud doit attendre pendant un temps EIFS lorsque le canal redevient libre mais que le paquet n'a pas étécompris, la longeur de EIFS étant suffisante pour que l'envoi du CTS ou de l'ACK se déroule dans de bonnes conditions.

FIGURE 2.6 - Configuration à quatre noeuds. FIGURE 2.7 - Extended Inter Frame Spacing.

5. Les intertrames IFS

Les temps intertrames (Inter-Frame Spacing)[20] permettent de varier la prioritéd'accès au médium de certains paquets. Plus l'intertrame est courte pour une station, plus son accès est prioritaire. Les quatre durées IFSs utilisées dans la norme 802.11 sont les suivantes :

1. SIFS (Short Inter-Frame Spacing) : c'est la durée la plus courte. Elle permet ^àl'accuséde réception ACK, au paquet de contrôle CTS ou au fragment suivant de précéder toute autre émission sur le canal qui veut débuter en même temps;

2. PIFS (Point Coordination Inter-Frame Spacing) : elle est employée dans le mode d'accès PCF par le point d'accès AP pour gagner l'accès au canal radio avant tout autre mobile. Sa valeur est égale à (SIFS + aSlotTime);

3. DIFS (Distributed Inter-Frame Spacing) : cette durée, plus longue que SIFS et PIFS, est égale à (SIFS + 2 × aSlotTime). Elle est utilisée avant l'envoi d'un paquet dans le mode d'accès DCF;

4. EIFS (Extented Inter-Frame Spacing) : cette durée est utilisée si la couche PHY détecte une activitésur le canal qu'elle ne comprend pas. EIFS assure la transmission d'accusés de réception provenant d'autres mobiles. C'est la durée la plus longe entre les IFSs. Elle est égale à (SIFS + _ACKtime + DIFS) (ou _ACKtime représente le délai de transmission de l'accuséde réception ACK). Si pendant le temps EIFS le mobile concernéintercepte un signal qui peut décoder, alors l'EIFS est interrompu et le mobile repasse au defering.

Les durées IFSs sont des éléments importants dans l'évaluation de performance de 802.11, car leurs valeurs influent directement sur l'utilisation globale de la bande passante par les stations.

27

Chapitre 2. MAC IEEE 802.11

Paramètres	802.11a	802.11b (FH)	802.11b (DS)	802.11 (High Rate)
aSlotTime (sis)	9	50	20	20
SIFS (sis)	16	28	10	10
PIFS (sis)	25	88	30	30
DIFS (sis)	34	128	50	50
EIFS (sis)	92.6	396	364	268 ou 364
aCWmin (SlotTime)	15	15	31	31
aCWmax (SlotTime)	1023	1023	1023	1023

TABLE 2.4 - Intertrames et CW pour les différentes couches physiques. 6. Mécanisme de fragmentation

La fragmentation[21] et un mécanisme proposépour réduire le taux d'erreurs par paquet. En raison du taux d'erreurs par bit élevédu canal radio, la probabilitéque le paquet soit erronéaugmente avec la taille de celui-ci. Ce mécanisme consiste à deviser (fragmenter) une trame MAC en un ensemble de fragments 2.8. Pour savoir si une trame doit être fragmentée, sa taille est comparée à un seuil dit »Fragmentation-Threshold».

Les fragments d'une même trame sont envoyés et acquittés séparément d'une manière séquentielle et seul une durée SIFS sépare deux séquences Fragment/ACK (Figure 2.9) afin de permettre à l'émetteur de ne libérer le canal qu'une fois l'envoi de tous ses fragments sera terminé. Dans le cas oùun ACK n'est pas reçu, l'émetteur libère le canal et essaie d'y accéder à nouveau. Il recommence la transmission à partir du dernier fragment non acquitté. Enfin, si le mécanisme RTS/CTS est utilisé, seul le premier fragment envoyéutilise les trames RTS/CTS.

FIGURE 2.8 - Mécanisme de fragmentation.

28

Chapitre 2. MAC IEEE 802.11

FIGURE 2.9 - Fragmentation dans le mode DCF.

2.6 Conclusion

Dans ce chapitre, nous avons présentéles principaux prérequis nécessaires à notre travail ^àsavoir l'étude de la norme IEEE 802.11 et ses principales extensions, et l'architecture en couches

(physique et liaison de données), par la suite nous nous somme intéressés à l'étude du protocole MAC 802.11, ses méthodes d'accès ainsi que les protocoles de la sous-couche MAC en mode DCF. Le chapitre suivant fera l'objet d'une synthèse sur les particularités de 802.11 dans un contexte ad hoc.

Chapitre 3

Particularités de 802.11 dans un

contexte ad hoc

29

3.1 Introduction

Le 802.11 a étéconçu dans l'optique des réseaux d'entreprises ou de hotspots organisés autour de stations de base. Nous avons vu que son faible coût, sa disponibilité(aussi bien commerciale que dans les simulateurs) et la possibilitéqu'il soit utilisépour des réseaux multi-sauts par la simple

adjonction de protocoles de routage de niveau supérieur, 802.11 est devenu le support privilég^iépour l'étude des réseaux ad hoc. Mais un certain nombre de problèmes apparaissent, qui peuvent être regroupés en plusieurs catégories :

- Des problèmes de topologie radio : Ils apparaissent lorsque les mobiles sont placés dans des configurations bien spécifiques (des mobiles ne pouvant communiquer qu'avec certains de leurs voisins, ou encore ne détecte les porteuses que de certains autres). Ces problèmes sont connus depuis longtemps dans le contexte des réseaux à stations de base. 802.11 intègre des solutions pour certains problèmes (ex : les noeuds cachés) et en laisse autres sans solutions. Mais lors du passage à des réseaux multisauts, ces problèmes dévoilent de nouvelles facettes qu'il est nécessaire de prendre en considération.

- Des problèmes liés aux débits multiples : Le 802.11 propose plusieurs vitesses de transmission parmi lesquelles les mobiles choisissent en fonction des conditions du canal (les vitesses les plus basses sont plus tolérantes aux perturbations radio et permettent une meilleure portée). Le fait de pouvoir utiliser plusieurs vitesses différentes va avoir des répercussions dans un réseau ad hoc. D'une part en terme de débit, puisque des problèmes déjàconnus dans les réseaux à stations de base risquent d'y être magnifiés. Et d'autre part en terme de connec-tivité, en particulier lorsque les protocoles de routage utilisent des paquets ayant une plus grande portée que les données qui doivent être envoyées ensuite.

- Des problèmes d'équitéentre des flux multiples et de débit total dans le réseau: Le 802.11 étant prévu pour fonctionner dans des configurations oùla plupart des mobiles sont à portée les uns des autres (ou dans le pire des cas voisins à deux sauts), ses performances dans des configurations multisauts sont nettement au-dessous des optimums théoriques, en terme de débit et d'équitéd'accès au canal.

30

Chapitre 3. Particularités de 802.11 dans un contexte ad hoc

3.2 Le problème des noeuds cachés

FIGURE 3.1 - Les stations cachés.

La station A et la station C ne se détectent pas, mais ont un récepteur commun. Dans ce cas, les stations A, et C perçoivent toujours le médium comme étant libre et ne sont ainsi jamais interrompues. Les transmissions simultanées des stations A et C provoquent des collisions au niveau de la station B qui n'émet jamais d'acquittement.

Dans le problème des »stations cachées» présentésur la figure 3.1 : deux stations indépendantes. non à portée de communication l'une de l'autre et ni en détection de porteuse, cherchent a envoyer

des paquets au même destinataire. Dans cette configuration, elles ne détectent pas leur activitéréciproque sur le médium radio et donc considèrent que le médium est libre et qu'elles peuvent

envoyer leurs paquets. Ces paquets peuvent alors entrer en collisions au niveau du récepteur qui ne comprend pas les paquets. Ces collisions provoquent l'augmentation des fenêtres de contention de chacune des stations. Cette augmentation permet d'accroître la probabilitépour une station de transmettre son paquet avec succès car le seul moyen qu'une transmission soit correcte est que celle-ci ait lieu pendant la période de décrémentation du backoff de la station en concurrence. La probabilitéd'une transmission correcte augmente quand les paquets transmis par les stations sont de petite taille. Notons que l'apparition des collisions et l'augmentation de la fenêtre de contention réduisent les performances du protocole MAC. Pour empêcher l'apparition d'une telle situation, le mode DCF fournit un mode optionnel d'échange de paquets de contrôle de petite taille appelés RTS et CTS. Avant de transmettre ses données, un émetteur envoie un paquet de contrôle RTS (Request To Send) à son destinataire. Tous les mobiles à portée de communication de l'émetteur qui ont reçu le RTS savent qu'une communication va avoir lieu. Comme la durée de la communication est précisée dans le paquet RTS, ces mobiles peuvent alors se bloquer et s'empêcher d'émettre pendant toute cette période. Cette opération est réalisée grâce au NAV (Network Allocation Vector) qui stocke la valeur de cette durée et qui joue le rôle d'horloge. Le récepteur qui reçoit le RTS renvoie un paquet de contrôle CTS (Clear To Send) s'il n'est pas lui-même bloquépar son NAV. Le CTS a le même effet que le RTS pour les mobiles à portée de communication du récepteur. À la réception du CTS, l'émetteur sait que le médium a étéréservéet qu'il peut donc émettre ses données.

31

Chapitre 3. Particularités de 802.11 dans un contexte ad hoc

3.3 Le problème des noeuds cachés asymétriques

FIGURE 3.2 - Les stations cachés asymétriques.

Les stations 0 et 2 ne sont pas dans la même zone d'émission et ont chacune un récepteur : les stations 1 et 3 respectivement. Dans ce cas, la station 0 perçoit toujours le médium comme étant libre et transmet ces paquets après une attente ininterrompue de son backoff. La station 2 transmet elle aussi ces paquets quasiment sans interruption à la station 3. Les transmissions simultanées des stations 0 et 2 provoquent des collisions au niveau de la station l qui n'émet jamais d'acquittement. La station 3 reçoit toujours correctement les paquets envoyés par la station 2. On a ici un déséquilibre entre les deux stations.

Le scénario précédent (les stations cachées) présente une certaine symétrie. Dans le scénario des stations cachées asymétriques présentésur la figure 3.2, seul un des deux émetteurs subit des collisions. Dans ce scénario, les deux émetteurs ont chacun deux récepteurs distincts. Ici, la station 0 se retrouve dans une situation de stations cachées alors que la station 2 se trouve dans une situation oùces transmissions sont correctes et elle ne perçoit jamais le médium comme étant occupé. Les collisions générées au niveau de la station 1 ainsi que l'augmentation du backoff qui s'ensuit pour la station 0 réduit fortement les performances du protocole MAC pour la station 0 et donc pour l'ensemble du réseau.

Notons que pour qu'une transmission soit correcte pour la station 0, elle ne doit pas excéder le temps de décrementation du backoff de la station 2. Le temps de décrémentation du backoff de la station 2 est toujours compris entre [0; _CWmin], ce qui n'était pas le cas dans le scénario des stations cachées. Il est aussi important de noter que l'utilisation des RTS et CTS dans ce scénario permet de rééquilibrer l'accès au médium des deux stations, celui-ci ne résout pas complètement le problème. En effet, la station 1 est bloquépar le NAV du RTS de la station 2 provoquant une non réponse aux RTS de la station 0.

32

Chapitre 3. Particularités de 802.11 dans un contexte ad hoc

3.4 Le problème des trois paires

FIGURE 3.3 - Les stations cachés asymétriques.

Les paires 0 et 2 sont complètement indépendantes l'une de l'autre mais partagent l'accès au médium avec la paire centrale (paire 1). Ce déséquilibre au niveau de la concurrence pour l'accès au médium entre les paires extérieures et la paire centrale provoque un défaut d'accès pour celle-ci. Dans ce scénario, la paire centrale doit attendre un recouvrement des périodes de décrémentation des paires extérieures pour pouvoir décrémenter son backoff.

Le scénario des trois paires présentésur la figure 3.3 montre un problème de défaut d'accès pour la paire centrale. Dans ce scénario, le problème ne vient pas des collisions mais de l'occupation du médium perçue par la paire centrale. Ici, les deux paires extérieures sont indépendantes l'une de l'autre, cependant elles sont en concurrence avec la paire centrale. Ce déséquilibre provoque un défaut d'accès pour la paire centrale car quand l'une des paires extérieures (paire 0 par exemple) accède au médium, elle bloque la paire centrale permettant ainsi à l'autre paire extérieure (paire 2) de décrémenter son backoff et d'envoyer son paquet. Quand la transmission de la paire 0 se termine, la transmission de la paire 2 peut encore être en cours, bloquant toujours la paire centrale. Ce blocage permet à la paire 0 d'accéder de nouveau au médium et ainsi de suite. Dans ce cas, la paire centrale ne perçoit quasiment jamais le médium comme étant libre et ne décrémente jamais son backoff.

33

Chapitre 3. Particularités de 802.11 dans un contexte ad hoc

3.5 Le problème des noeuds exposés

FIGURE 3.4 - Le phénomène des noeuds exposés.

Le problème des noeuds exposés apparaît dans des configurations comme celle présentée sur la figure 3.4. Ici, les noeuds B et C voudraient émettre respectivement vers A et D. En suivant le mécanisme de la DCF, celui qui a tiréle plus petit backoff accédera au canal et envoie son paquet, alors que l'autre détectera la porteuse du premier, et entrera en période de defering. Pourtant, si B et C émettaient en même temps, le signal de B au niveau de A serait largement supérieur à celui de C et suffisant pour une réception correcte. La situation serait l'inverse au niveau du noeud D, qui recevrait correctement le paquet de C, malgréle léger bruit venant de B. Dans cette situation, le DCF limite donc inutilement la bande passante totale du réseau. On peut noter que certains travaux s'intéressent au problème, notamment [22] qui propose l'utilisation d'un mécanisme de »parallel RTS» pour le résoudre en partie.

34

Chapitre 3. Particularités de 802.11 dans un contexte ad hoc

3.6 Le problème de la zone grize

FIGURE 3.5 - Le phénomène de la zone grize.

Nous avons vu que 802.11b utilise des vitesses de transmissions de 1 ou 2 Mbit/s pour les paquets qu'il diffuse, mais la vitesse de transmission pour les paquets envoyés en unicast peut s'élever jusqu'à11 Mbit/s. La plupart des protocoles de routage utilisent la diffusion pour construire ou maintenir les routes (les paquets Hello ou RouteRequest sont typiquement diffusés par exemple). Ces paquets sont donc émis à 2 Mbit/s et permettent de construire un certain nombre de routes dans le réseau. Mais lorsque les données sont ensuite envoyées à 11 Mbit/s sur ces routes, comme la portée de communication décroît avec l'augmentation de la vitesse, il est possible que des mobiles portant à portée des paquets de routage lents soient trop loin pour les paquets de données rapides.

Il en découle que les routes construites avec les paquets diffusés ne sont pas forcément exploitables ^àdes débits plus élevés. La zone concernée (la soustraction de la zone »rapide» à la zone» lente» plus

large) est appelée »zone grise» et ce problème avait étérelevéthéoriquement et expérimentalement dans [23].

3.7 Partage du canal par des flux à vitesses différentes

En sus du phénomène des zones grises, l'utilisation des débits multiples que propose 802.11 conduit à d'autres problèmes. Lorsque des mobiles implémentant 802.11 rencontrent de forts taux de pertes, la norme leur recommande de réduire leur vitesse d'émission (plus la vitesse est basse, plus le signal est résistant aux interférences et est compréhensible loin de l'émetteur). Mais, comme il l'est montréen détail dans [24], la méthode DCF d'accès au médium ne cherche pas à équilibrer les débits de plusieurs flux en contention, mais plutôt à donner à chaque paquet des chances équitables. Lorsque certains paquets sont envoyés à des vitesses élevées et d'autres à des vitesses lentes, cela se traduit par une alternance plus ou moins régulière entre eux. Les mobiles émettant leurs paquets très lentement vont donc » capturer» le canal pendant la majoritédu temps et diminuer le débit des autres mobiles qui ne prennent pourtant pas beaucoup de temps pour émettre leurs propres

35

Chapitre 3. Particularités de 802.11 dans un contexte ad hoc

paquets. Ainsi, dans un environnement de compétition entre plusieurs mobiles, si l'un d'entre eux émet à 1 Mbit/s, même si tous les autres travaillent à 11 Mbit/s, leurs débit utile sera très bas. Dans un environnement ad hoc, du fait du mécanisme de routage qui utilise en général les paquets diffusés à 2 Mbit/s (comme notéau paragraphe 3.4), beaucoup de liens ainsi découverts ne supporteront pas des débits élevées (5.5 ou 11 Mbit/s) et s'en tiendront au débit réduit de 2 Mbit/s. Les trafics sur les liens oùle 11 Mbit/s est possible seront donc le plus souvent affectés considérablement par ces autres liens plus lents.

3.8 TCP et 802.11

Une performance adéquate du protocole TCP est capitale pour le bon fonctionnement de la grande majoritédes réseaux informatiques. Quoique la performance du protocole TCP soit assez stable et satisfaisante dans les réseaux filaires, son application aux réseaux ad hoc présente des caractéristiques d'instabilitéet d'iniquité. Ces caractéristiques ont étédémontrées par des simulations dans plusieurs travaux comme [25], [26], [27]. En [25], les auteurs ont montréque le comportement du protocole TCP dans un réseau ad hoc à multisauts peut causer une baisse remarquable du débit total du réseau. Ce comportement indésirable devient très clair dans un réseau hybride.

On peut résumer les problèmes du protocole TCP dans les réseaux ad hoc aux points suivants:

1. Les problèmes de noeuds cachés et de noeuds exposés sont la cause de l'échec de livraison des trames 802.11 dans la plupart des cas [28]. Lorsqu'un noeud est incapable de livrer la trame à sa destination pour un certain nombre de fois, la couche MAC signale un échec de livraison à la couche réseau qui interprète cet échec comme une perte de route. La couche réseau recommence le processus de recherche de route qui dure normalement plus que le seuil de délai d'attente (timeout threshold) du protocole TCP, ce qui fait que la session du protocole TCP doit redémarrer à partir d'une taille de fenêtre (window size = 1) . Ceci représente une forte dégradation de performance et cause des périodes de débit nul.

2. La taille de fenêtre du protocole TCP est un facteur important qui influence la performance de ce protocole dans les cas des réseaux ad hoc. Plusieurs articles ont démontréque les fenêtres de petite taille présentent de meilleures performances (taille de l ou 2 dans la plupart des cas). Ceci est expliquépar le fait que dans les cas des fenêtres de large taille, si un noeud est incapable d'acquitter les trames transmises, le transmetteur devra renvoyer toutes les trames de cette fenêtre non acquittée ce qui cause une détérioration considérable pour le débit du protocole TCP.

3. Les trames du protocole TCP nécessitent un accuséde réception (ACK). Un noeud dans une situation de noeud exposé, malgrésa bonne réception d'une trame TCP, sera incapable de répondre par un ACK. Ignorant le résultat de sa transmission, le transmetteur continuera ses essais. À l'autre coté, les trames DATA auxquelles le récepteur est exposésont plus grandes que les trames de ACK et s'enchainent sans laisser une chance au noeud exposéd'acquitter les trames qu'il a reçues.

36

Chapitre 3. Particularités de 802.11 dans un contexte ad hoc

4. Le mécanisme du backoff exponentiel du 802.11 contribue aussi au problème du protocole TCP en favorisant toujours le noeud qui a captédernièrement le canal. Ce phénomène est connu par le nom de saisie du canal.

5. Le phénomène de saisie du canal peut aussi se produire au cas de deux connexions avec des nombres différents de sauts. On trouve que la connexion ayant un nombre inférieur de sauts saisira le canal et bloquera totalement l'autre connexion.

3.9 Conclusion

Dans ce chapitre, nous avons essayéde mener une étude complète sur la particularitéde 802.11 dans les réseaux ad hoc. Nous avons tentéde lister les différents problèmes de cette norme, et nous avons relevéles différents scénarios de base qui montrent l'iniquitéd'accès au canal (les trois pairs, les stations cachées asymétriques).

Dans le chapitre suivant nous allons entamer la phase de la simulation et discussion des résultat obtenu. Ensuite, nous allons énumérer quelques solutions apportées aux problèmes d'équité.

37

Chapitre 4

Analyse et évaluation des

performances 802.11

4.1 Introduction

Après avoir présentéles différents problèmes d'équitéd'accès au canal dans la norme MAC 802.11 dans le chapitre précèdent, nous allons nous intéresser à la simulations de ces dernier dans le but de mieux les comprendre.

Dans ce chapitre, en premier lieu nous allons commencer par présenter l'outil de simulation NS2, par la suite nous allons réaliser des simulations, des différents problèmes d'équitéd'accès au canal et discuter les résultats obtenu. En second lieu nous allons présenter quelques solutions visant à remédier à ces problèmes, à savoir, améliorations apportées sur le protocole 802.11 (algorithme de Backoff), les protocoles MadMac et FWM (Fair Wireless Mac).

4.2 Simulation de quelques problèmes d'équité802.11 4.2.1 Présentation de Network Simulator 2 (NS 2)

NS-2 est un outil (logiciel) de simulation libre à code source ouvert permettant l'étude, la conception et la gestion des protocoles pour les réseaux informatiques. Il a étédéveloppéà partir de méthodes de conception orientées objets dans le projet VINT(Virtual InterNetwork Testbed) associant plusieurs centres de recherche comme AT&T research institute, (ACIRI), Xerox PARC et Sun Microsystems [40]. NS-2 contient des librairies pour la génération des fonctions (topologie, trafic, routage, MAC, LLC,...) et des outils graphiques pour faciliter l'interprétation (Xgraph) et la visualisation (network animator NAM) des résultats. Il contient les fonctionnalités nécessaires pour l'étude des méthodes d'accès au médium, des algorithmes de routage point à point ou multipoint, des protocoles de transport, de session, de réservation de ressources.

Les objets proposés par ce simulateur, nous permettrons de faire une étude sur certains scénarios qui représentent des problèmes d'équitéd'accès au canal.

38

Chapitre 4. Analyse et évaluation des performances 802.11

4.2.2 Noeud ^caché

FIGURE 4.1 - Le scénario du noeud cach^é

Nous allons considérer le scénario des stations cachées décrit par la figure 4.1. n0 et n2 envoient des paquets TCP à n1 de 2000 octets. L'application simulée est un transfert FTP qui commence à t = 1s et qui se termine à t = 10s. La distance entre n0 et n1 est de 200m et la distance entre n1 et n2 est de 200m.

1

2

3

4

5

6

7

8

9

10

11

12

Les paramètres de la simulation sont les suivants :

Phy/WirelessPhy set CSThresh 2.28e-11

MAC/802 11 set dataRate 11 .0e6

Mac/802 11 set RTSThreshold 10000

$ns node-config -adhocRouting AODV \

-llType LL \

-macType Mac/802 11 \

-ifqType Queue/DropTail/PriQueue \

-ifqLen 50\

-antType Antenna/OmniAntenna \

-propType Propagation/TwoRayGround \

-phyType Phy/WirelessPhy \

-channelType Channel/WirelessChannel \

Chapitre 4. Analyse et évaluation des performances 802.11

FIGURE 4.2 - Résultat de la simulation du scénario (noeud caché)

Le graphe 4.2 ci-dessus représente le débit des noeuds n0 et n2 au cours du temps avec le standard 802.11. On peut remarquer que dans ce scénario le débit des noeuds a considérablement chutéà 1.8 Mbit/s. Or que la capacitédu canal est de 11 Mbit/s. L'explication tient dans le fait qu'au niveau du noeud n1 se produisent des collisions causées par la méconnaissance des noeuds n0 et n2 entre eux.

4.2.3 Noeud exposé

39

FIGURE 4.3 - Le scénario du noeud expo^sé

Nous allons considérer le scénario des stations exposées décrit par la figure 4.3. Le terrain considéréest de 800m sur 500m. Les coordonnées des points sont les suivantes : n0(100; 300), n1(300; 300), n2(500; 300) et n3(700; 200). On considère deux communications de type CBR avec des paquets de 250 octets et un intervalle entre deux paquets de 0.005 secondes :

- une communication du noeud 1 au noeud 0 commence à 0 seconde; - une communication du noeud 2 au noeud 3 commence à 0,5 seconde. - les communications se terminent à t = 10s.

40

Chapitre 4. Analyse et évaluation des performances 802.11

1

2

3

4

5

6

7

8

9

10

Les paramètres utilisés sont les suivants :

FIGURE 4.4 - Résultat de la simulation du scénario (noeud exposé)

Phy/WirelessPhy set CSThresh 30.5e-10

$ns node-config -adhocRouting DSDV \

-llType LL \

-macType Mac/802 11 \

-ifqType Queue/DropTail/PriQueue \

-ifqLen 50 \

-antType Antenna/OmniAntenna \

-propType Propagation/FreeSpace \

-phyType Phy/WirelessPhy \

-channelType Channel/WirelessChannel \

La figure 4.4 montre les résultats de la simulation des stations exposés. Nous avons remarquéque dans ce scénario le noeud n2 est dans une situation de famine, L'explication tient dans le fait

que le noeud n1 se met au defering car il détecte l'activédu noeud n2 sur le canal. Or que dans cette situation ce dernier peut envoyer des données au noeud n0 sans entrainer des collisions au niveau du noeud n2.

41

Chapitre 4. Analyse et évaluation des performances 802.11

4.2.4 Stations cachées asymétriques

FIGURE 4.5 - Le scénario des stations cachées asymétriques

Nous allons considérer dans le scénario des stations cachées asymétriques décrit à la figure 4.5, le noeud 0 est distant de 200 mètres du noeud 1, le noeud 1 est distant de 200 mètres du noeud 2 et le noeud 2 est distant de 200 mètres du noeud 3. On considère deux communications de type CBR avec des paquets de 250 octets et un intervalle entre deux paquets de 0.005 secondes :

- Une communication du noeud 0 au noeud 1 commençant à 0 seconde; - Une communication du noeud 2 au noeud 3 commençant à 0,5 seconde. - les communications se termine à t = 10s.

1

2

3

4

5

6

7

8

9

10

Les paramètres utilisés sont les suivants :

Phy/WirelessPhy set CSThresh 30.5e-10 $ns node-config -adhocRouting DSDV \

-llType LL \

-macType Mac/802 11 \

-ifqType Queue/DropTail/PriQueue \

-ifqLen 50 \

-antType Antenna/OmniAntenna \

-propType Propagation/FreeSpace \

-phyType Phy/WirelessPhy \

-channelType Channel/WirelessChannel \

Chapitre 4. Analyse et évaluation des performances 802.11

FIGURE 4.6 - Résultat de la simulation du scénario (stations cachées asymétriques)

Le graphe 4.6 représente le débit des noeuds 2 et 0 au cours du temps avec le standard 802.11. Le noeud 2 lèse complètement le noeud 0. L'explication tient dans le fait que pour le noeud 2 toutes ses transmissions réussissent. Il reçoit immédiatement le CTS et l'ACK du noeud 3. Le noeud 0 est dans la situation inverse. Le noeud 1 étant exposéau noeud 2, celui-ci est constamment le siège de collisions puisque le noeud 2 étant cachéau noeud 0, ce dernier envoi des RTS. Le noeud 1 ne reçoit donc aucun des RTS du noeud 0. Il ne renvoie donc aucun CTS plaçant le noeud 0 en situation de famine.

4.2.5 Trois paires

42

FIGURE 4.7 - Le scénario des trois paires

Le scénario des trois paires, décrit dans la figure 4.7. Le terrain considéréest de 700m sur 500m. Les coordonnées des points sont les suivantes : n0(200; 400), n1(500; 400), n2(800; 400), n3(200; 200), n4(500; 200) et n5(800; 200).

- Les deux communication, du noeud 0 au noeud 3 et du noeud 2 au noeud 5 commencent à 1 seconde;

43

Chapitre 4. Analyse et évaluation des performances 802.11

- une communication du noeud 1 au noeud 4 commence à 1,5 seconde. - les communications se termine à t = 10s.

1

2

3

4

5

6

7

8

9

10

11

12

Les paramètres de la simulation sont les suivants :

FIGURE 4.8 - Résultat de la simulation du scénario (trois paires)

Mac/802 11 set dataRate 11Mb

Mac/802 11 set basicRate 1Mb

Mac/802 11 set RTSThreshold 10000

$ns node-config -adhocRouting AODV \

-llType LL \

-macType Mac/802 11 \

-ifqType Queue/DropTail/PriQueue \

-ifqLen 50 \

-antType Antenna/OmniAntenna \

-propType Propagation/TwoRayGround \

-phyType Phy/WirelessPhy \

-channelType Channel/WirelessChannel \

La figure 4.8 montre les résultats de la simulation des trois paires. Nous voyons très bien dans ce scénario que l'émetteur du flot 1 (le noeud n1) souffre d'un accès particulièrement inéquitable. Il doit attendre que les noeuds n0 et n2 soient tous les deux au repos pour accéder au support. Ce qui le place dans une situation de famine.

4.3 Quelques solutions apportées aux problèmes d'équ^ité4.3.1 Les algorithmes de backoff

Dans cette section, nous présentons quelques algorithmes de backoff en utilisant PEPA (Performance Evaluation Proccess Algebra) [31]. Comparée aux autres composantes, la modélisation

44

Chapitre 4. Analyse et évaluation des performances 802.11

de nouveaux algorithmes de backoff est très simple. Les deux caractéristiques principales des algorithmes de backoff conçus pour les réseaux sans fil sont la méthode d'incrémentation et la méthode de décrementation, étant données les tailles de fenêtre de contention minimale et maximale.

Un algorithme simple à modéliser est l'algorithme nomméDouble Increase, Double Decrease

[29] ou DIDD. Cet algorithme est conçu pour être moins agressif que l'algorithme BEB implémen^tédans le standard de 802.11. Dans DIDD, après une collision, la fenêtre de contention est doublée,

comme avec BEB, et après un succès, celle-ci est divisée par deux. Dans cet algorithme, la fenêtre de contention n'est pas réinitialisée après un certain nombre de transmissions incorrectes.

FIGURE 4.9 - BEB

FIGURE 4.10 - DIDD

De la même manière, les algorithmes de backoff tels que Multiplicative Increase, Linear Decrease

[30] (MILD) oùla méthode de décrémentation est encore moins agressive que celle de DIDD, la méthode d'incrémentation reste la même.

FIGURE 4.11 - MILD

Pour une décrémentation linéaire de 32, c'est-à-dire qu'après une transmission correcte, la valeur de la nouvelle fenêtre de backoff est Max{CW_mi_n, _CWnew} tel que : CWnew = CW - 32. Ceci permet de limiter à 32 le nombre d'états de backoff possible.

Chapitre 4. Analyse et évaluation des performances 802.11

Un autre algorithme de backoff est le BEB inversé(Ineversed Binary Exponential Backoff), qui diminue sa fenêtre de contention par deux après une collision et se place dans l'état le plus grand après une transmission avec succès.

FIGURE 4.12 - BEB Inversé

BEB	BO i j	def =	(db i,f j).BO i j + (succ i,T).BO i 0 + (coll i,T).BO i (j + 1)
BEBinv	BO i j	def =	(db i, f (7 - j)).BO i j + (succ i, T).BO i 7 + (coll i, T).BO i (j - 1)
DIDD	BO i j	def =	(db i, f j).BO i j + (succ i, T).BO i (j - 1) + (coll i, T).BO i (j + 1)
MILD	BO i j	def =	(db i, f j).BO i j + (succ i, T).BO i (j - 1) + (coll i, T).BO i (2 X j + 1)

TABLE 4.1 - Modèle PEPA des algorithmes de backoff

Évaluation des performances

Pour évaluer les performances des stratégies de backoff, [31] utilise deux métriques (efficacitéet équité).

1. Éfficacité: les figures 4.13 et 4.14 montrent respectivement les temps d'occupation du canal radio pour le scénario des 3 paires et pour les stations cachées. Nous voyons sur la figure 4.13 que le temps d'occupation maximum pour la paire centrale ne dépasse pas 12%. Les courbes MILD, BEB et DIDD sont identique, ceci est dûau fait que sur ce scénario il n'y a pas de collisions, la fenêtre de contention reste donc la même. La figure 4.14 montre l'efficacitésur le scénario des stations cachées. L'algorithme DIDD et le plus efficace, suivi de BEB puis MILD et de BEB inversé.

45

Chapitre 4. Analyse et évaluation des performances 802.11

46

FIGURE 4.13 - Efficacitésur les 3 paires. FIGURE 4.14 - Efficacité: stations cachées.

2. Équité: les figures 4.15 et 4.16 représentent les courbes de l'équitépour les scénarios des stations cachées et des 3 pairs. La figure 4.15 montre que les 3 algorithmes BEB, DIDD et MILD ne sont pas équitables et que l'algorithme BEB inverséest le plus équitable des algorithmes.

FIGURE 4.15 - á sur les 3 paires. FIGURE 4.16 - á sur les stations cachées.

Après l'étude des algorithmes de backoff sur plusieurs topologies de réseaux sans fil différentes. Le premier résultat qui apparait est le compromis équité-efficacité. Les topologies et les algorithmes étudiés montrent que plus le backoff est efficace moins il est équitable.

4.3.2 Le protocole MadMac

Les solutions proposées dans la littérature modifient de manière probabiliste la méthode d'accès au médium. Cette modification de la méthode d'accès permet de diminuer ou d'augmenter de manière statistique les débits de chaque station. Peu de solutions hormis celle proposée dans [32], cherchent à fournir un ordonnancement explicite entre les stations. Or cet ordonnancement explicite est, selon [33], la clépour l'obtention d'un bon compromis équité-efficacité.

Chapitre 4. Analyse et évaluation des performances 802.11

4.3.2.1 Le principe du protocole MadMac

Pour obtenir une meilleure efficacité, MadMac n'effectue aucun échange d'informations. De plus, MadMac ne s'appuie que sur des informations déjàdisponibles dans 802.11.

1. Schéma de base

Si un noeud détecte qu'il partage le médium avec au moins une autre station, il met une variable booléenne, appelée SHARE à 1 et réduit son débit MAC par deux. Un temps d'at-tente _Twait est introduit avant chaque paquet à envoyer. Le but de ce temps est d'introduire un ordonnancement entre les noeuds en compétition. Une fois que _Twait, est écouléMadMac utilise l'algorithme classique d'accès au médium 802.11 pour envoyer son paquet. La figure 4.17 donne une illustration simple de MadMac.

FIGURE 4.17 - Une illustration simple de MadMac.

2. Gestion des collisions

Afin d'éviter les problèmes de collisions répétée, MadMac force les stations dans une telle situation à alterner leurs émissions. Pour cela, il introduit un temps d'attente plus grand que _Twait, appeléT_alt. Dès qu'une station réussit à envoyer son paquet qui a subi au moins k collisions, elle ajoute ce temps d'attente _Talt aux paquets suivants. Ce temps d'attente

s'arrête dès que la station détecte de l'activitésur le canal. Si en revanche, aucune activ^itén'est perçue, la station attend pendant _Talt. Après cette étape, lorsque le médium redevient

libre ou lorsque _Talt s'est écoulé, le noeud rentre dans le processus classique de 802.11 pour envoyer son paquet. La figure 4.18 décrit le fonctionnement du protocole sur la configuration des stations cachées (avec k = 2).

47

Chapitre 4. Analyse et évaluation des performances 802.11

FIGURE 4.18 - Une illustration simple de MadMac sur la configuration des stations cachées.

3. Le monopole du canal

Le protocole MadMac, ne fournit pas de solutions à ce monopole. Par conséquent, pour éviter le monopole il modifie sur ces stations la fenêtre de contention pour certains paquets. Après x (paramètre du protocole) envois de paquets consécutifs sans temps supplémentaire (SHARE est à 0), la fenêtre de contention pour le paquet x + 1 est dimensionnéà 2 fois la taille de la fenêtre de contention initiale de 802.11 puis à 4 fois la fenêtre de contention initiale pour le paquet 2x + 1. Ce processus est ensuite répétépour les paquets suivants. Ceci doit permettre aux stations pénalisées de pouvoir plus facilement émettre un paquet, ce qui mettra à jour la variable SHARE des stations monopolistiques et met donc un terme à ce monopole.

4.3.2.2 Évaluation

Les figures 4.21, 4.19 et 4.20 montrent les performances de MadMac, MBFAIR [34], PNAV [35] et 802.11 du point de vue de l'efficacitéet du point de vue de l'équité.

FIGURE 4.19 - Performance de MadMac sur le scénario des stations cachées asymétriques. Le débit global et l'index d'équitésont tracés suivant les deux axes des ordonnées (respectivement).

FIGURE 4.20 - Performance de MadMac sur le scénario des trois paires. Le débit global et l'index d'équitésont tracés suivant les deux axes des ordonnées (respectivement).

48

49

Chapitre 4. Analyse et évaluation des performances 802.11

FIGURE 4.21 - Performance de MadMac sur le scénario des stations cachées.

Ces résultats montrent que MadMac permet contrairement à 802.11 de fournir un bon compromis équité-efficacité. Bien que le protocole MadMac présente de bonnes performances, celles-ci sont liées aux paramètres qui le régissent. Les variables telles que x et k peuvent modifier considérablement les performances du réseau si elles sont mal dimensionnées.

4.3.3 FWM (Fair Wireless MAC) [37]

L'approche étudiée sous le nom de FWM s'inscrit dans la continuitéde DCF. Elle le rend opérant dans les situations inéquitables.

4.3.3.1 Le principe de FWM

Le principe est d'ajouter un canal de signalisation hors bande. Ce canal est exploitéselon un mode tonalitéd'occupation (busy tone) [36]. FWM vise à maintenir une synchronisation entre les noeuds voisins à l'aide de ce dernier, quand un noeud est en train de recevoir, il émet un signal d'occupation sur le canal de signalisation pour informer tous les émetteurs potentiels dans son voisinage (àportée de communication). La détection de la porteuse doit se faire en prenant en compte le canal de signalisation en plus du canal principal. Cependant, ce mécanisme seul est insuffisant pour assurer un accès équitable, il faut prendre en compte le non synchronisation du délai EIFS entre les noeuds. Certains noeuds sont contraints d'attendre un délai EIFS avant d'entreprendre la procédure d'accès au support. Cette différence du délai d'attente est une cause importante d'iniquitéd'accès. Plusieurs solutions sont étudiées, leur évaluation a montréque la plus équitable consiste à maintenir et synchroniser l'EIFS pour tous les émetteurs voisins d'un émetteur qui rencontre une situation oùil a dûactiver son EIFS. La synchronisation est faite par un signal émis sur un second canal de signalisation.

Chapitre 4. Analyse et évaluation des performances 802.11

4.3.3.2 Évaluation

Les figures 4.22 et 4.23 montrent respectivement le débit total écoulépour le scénario de contention déséquilibrée et les stations cachées.

FIGURE 4.22 - Répartition des débits avec FWM; Scénario contention déséquilibrée.

FIGURE 4.23 - Répartition des débits avec FWM; Scénario station cachée.

50

La table 4.2 donne une évaluation chiffrée des améliorations apportées par la présente proposition FWM.

Situation	DCF classique			FWM
	> x ·	u	F	>x ·	u	F
Contention déséquilibrée	176.80	0.92	0.68	89.00	0.66	0.99
Station cachée	88.66	0.15	0.5	88.14	0.15	0.99

TABLE 4.2 - Comparaison de performances pour les situations caractéristiques.

Comme on peut le constater, FWM atteint son objectif d'équité. Le débit total a légèrement chutémais l'équitéa fortement augmenté. Son principal reproche est d'utiliser des canaux de signalisation hors bande. Ces canaux demandent des composants (et donc présente un coût) pour la gestion des canaux supplémentaires. Les contraintes de mise en oeuvre de FWM restent cependant moindres par rapport à l'avantage apportéà la communication dans les réseaux ad hoc.

4.4 Conclusion

Dans ce chapitre, nous avons simuléquatre scénarios qui illustrent l'iniquitéd'accès au canal dans MAC 802.11. Le premier scénario est le problème du noeud caché. Nous avons remarquéque le débit chute considérablement à cause des collisions au niveau du noeud central. Le deuxième scénario est le noeud exposé, dans celui-ci nous avons remarquéune situation de famine pour le noeud exposécausépar le fait qu'il détecte l'activitéde son voisin qui émet vers une station qui est hors de sa portée. Le troisième scénario est celui des stations cachées asymétriques, dans ce cas nous avons remarquéaussi une situation de famine due au fait de la méconnaissance des activités

51

Chapitre 4. Analyse et évaluation des performances 802.11

du voisinage. Pour le dernier scénario, qui est le cas des trois paires, nous avons remarquéune famine au niveau de la paire centrale qui doit attendre que les deux autres paires soient en repos pour pouvoir accéder au support.

Plusieurs solutions ont étéproposées, et visent à résoudre le problème d'iniquitéd'accès au médium dans Mac 802.11. Parmi ces solutions nous avons présenté, les algorithmes du backoff, le MadMac et le FWM (Fair Wireless Mac). Après l'étude de ces trois solutions, nous avons conclus que celles-ci ont apportédes améliorations par rapport au protocole MAC 802.11, et que toute autre solution proposédoit avoir un bon compromis entre l'équitéet l'efficacité.

52

Conclusion générale

Dans ce projet, nous nous sommes intéresséà un problème ouvert et qui selon nous l'est encore, celui de l'équité. Nous nous sommes attachéà étudier l'effet de l'équitéau niveau de la couche MAC 802.11 dans un contexte ad hoc. D'une manière générale, notre travail peut être résuméen deux étapes principales : la mise en lumière des problèmes d'équitéet l'analyse de leurs impacts, ainsi que l'étude de quelques solutions apportées à ces problèmes.

Dans la première partie, nous avons voulu connaitre les paramètres qui influent sur l'équitédans 802.11. En effet, 802.11 étant le standard de fait dans les réseaux ad hoc, il nous paraissait

utile et nécessaire de bien comprendre son fonctionnement afin de comprendre par la suite les problèmes d'équitéqui le régissent.

Après l'étude, des problèmes d'équitéd'accès au canal sont apparus; certains mobiles sont dans un quasi-impossibilitéd'envoyer des messages pendant des périodes de temps prolongées. L'ana-lyse de ces problèmes (par simulation avec NS-2) nous a montréqu'ils trouvaient leur source dans la norme 802.11. Cette dernière a étéconçue pour des réseaux de base. Dans les configurations particulières des réseaux ad hoc que nous avons testé, elle est clairement mise en défaut. La nature du problème tient pour une bonne part dans l'inégalitédes mobiles faces aux interférences. En effet, certains mobiles subissent une combinaison des activités de mobiles voisins qui agissent indépendamment les uns des autres et qui indiquent à ce mobile que le canal est occupéen permanence, et l'empêche donc de façon durable d'y accéder.

Ce problème a étémis en relief dans le scénario des trois paires et les stations cachées asymétrique par la simulation.

La seconde partie présente quelques solutions apportées aux problèmes d'équité. En premier lieu, nous avons présentéplusieurs algorithmes de backoff qui permettent de diminuer ou d'aug-menter de manière statistique les débits de chaque station. Par la suite, nous avons présentédeux méthodes équitables qui sont une extension de 802.11, à savoir MadMac [33] et FWM (Fair Wireless Mac) [37]. De nombreuses simulations avec NS-2 montrent que MadMac présente de bonnes performances par rapport à 802.11. Celles-ci sont liées aux paramètres qui le régissent. Les variables telles que x et k peuvent modifier considérablement les performances du réseau si elles sont mal dimensionnées et les résultats de la méthode FWM montrent qu'il a atteint son objectif d'équité. Le débit a légèrement diminué, mais l'équitéa largement augmenté. Son principal reproche est d'utiliser des canaux de signalisations hors bande qui demandent des composants pour la gestion

53

Chapitre 4. Analyse et évaluation des performances 802.11

des canaux supplémentaires.

Nous avons conclu que ces solutions ont apportédes améliorations par rapport au protocole

standard 802.11. Et que toute autre solution proposédoit avoir un bon compromis entre l'équitéet l'efficacité.

En perspective nous aimerons approfondir la recherche sur les récentes propositions et projeter une large étude comparative sur les solutions et améliorations proposées, afin de proposer une amélioration qui offre un bon compromis entre l'équitéet l'efficacité.

54

Bibliographie

Bibliographie

[1] P. Allain-Dupréet N. Duhard Les armes secrètes de la décision. Guiliano éditeur, Paris, 1996.

[2] H. Liu, X. Jia, P. Wan, »On energy efficiency in wireless ad hoc networks», Book chapter on : Ad hoc and Sensor Networks, ISBN : 1-59454-396-8, Nova Sciences Publishers, Inc, pp.31-54, 2006.

[3] R. Poovendran, L. Lazos, »A graph theoretic framework for preventing the wormhole attack in wireless ad hoc networks», Wireless Networks (Kluwer Academic Publishers), Vol. 13, No. 27, pp. 27-59, 2006.

[4] C. Perkins, »Ad hoc Networking», Addison-Wesley, 2001.

[5] C. Holland and H. N. Vaidya. Analysis of TCP performance over mobile ad hoc networks. In Mobile Computing and Networking, pages 2019-230, 1999.

[6] S. Mascolo, C. Casetti, M. Gerla, M. Y. Sanadidi, and Ren Wang. TCP westwood : Bandwidth estimation for enhanced transport over wireless links. In Mobile Computing and Networking, pages 287-297, 2001.

[7] S. Chen and K. Naahrstedt. A distributed quality-of-service routing in ad-hoc networks. IEEE Journal on Selected Areas in Communications, 17(8), Auhust 1999.

[8] M. Frikha, Réseau ad hoc, routage, Qualitéde service et optimisation, La voisier, Paris, 2010.

[9] N. Badache, D. Djenourf, A. Derhabj and T. Lemlouma, Les protocoles de routage dans les résaux mobiles Ad Hoc, Laboratoire des logiciel de base, Vol 12, No. 02, 2002, pp. 77-112.

[10] P. Jackquet T. Clausen. RFC 3626. Optimized link State Routing Protocol(OLSR), 2003.

[11] S. Das C. Perkins, RFC 3561, Ad hoc On-Demand Distance Vector (AODV) Routing [en ligne], 2003, Memo.

[12] P. Samar, M. Pearlman, S. Haas, Independent zone routing : an adaptive hybrid routing framework for ad hoc wireless networks, IEEE/ACM Transactions on Networking 12 (4) (2004), pp 595-608, 2004.

[13] G. Pujolle, D. Males, Wi-Fi par la pratique, Eyrolles 2002.

[14] D. Trezentos. Standard pour réseaux sans fil : IEEE 802.11, Techniques de l'ingénieur, 2012.

55

Bibliographie

[15] M. Achir. Technologies basse consommation pour les réseaux ad-hoc, thèse de doctorat, Institut national polytechnique de Grenoble, Juillet 2005.

[16] K. RUNSER. Méthodologies pour la planification des réseaux locaux sans-fil, Thèse de doctorat, Institut national des sciences appliquées de Lyon, 2005.

[17] J. VAN DER MEERSCHEN. Hybridation entre les modes ad-hoc et infrastructure dans les réseaux de types wi-fi. Mémoire de fin d'étude en science appliquées, Universitélibre de Bruxelles, Facultédes science appliquées, 2006.

[18] M. Terré, Le Standard 802.11 Couche physique et couche MAC, Conservatoire National des Arts et Métiers, Mars 2007.

[19] D. Dhoutaut. Étude du standard IEEE 802.11 dans le cadre des réseaux ad hoc : de la simulation à l'expérimentation., thèse de doctorat, Institut National des Sciences Appliquées de Lyon, Décembre 2003.

[20] LAN MAN Standards Committee of the IEEE Computer Society. Part 11 : Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Spécificaiton. ANSI/IEEE Std 802.11, 2003.

[21] M. TOUMI. Evaluation des performances de réseau IEEE 802.11 mode ad hoc avec fragmentation. Thèse de magistère, Département d'Informatique, Universitéde Bejaia, 2006.

[22] A. Velayutham and H. Wang. Solution to the exposed node problem of 802.11 in wireless ad--hoc networks.

[23] H. Lundgren, E. Nordstr'om, and C. Tschudin. The gray zone problem in IEEE 802.11b based ad hoc networks. In ACM SIGMOBILE Mobile Computing and Communications Review, volume 6, pages 104--105, July 2002.

[24] M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda. Performance Anomaly of 802.11b. In Proceedings of INFOCOM 2003, San Francisco, 2003.

[25] K. Xu, S. Bae, S. Lee, and M. Gerla. Tcp behavior across multihop wireless networks and the wired internet. In WOWMOM'02 : Proceedings of the 5th ACM international workshop on Wireless mobile multimedia, pages 41--48, New York, NY, USA, 2002. ACM Press.

[26] K. Xu and M. Gerla. Tcp over an ieee 802.11 ad hoc network : Unfairness problems and solutions. Technical report, Computer Science Deptartment, University of California, Los Angeles, CA 90095, May 2002.

56

Bibliographie

[27] S. Xu and T. Saadawi. Revealing the problems with 802.11 medium access control protocol in multi--hop wireless ad hoc networks. Computer Networks, 38(4) :531--548, 2002.

[28] E. Thibodeau, M. Youssef, , and C. Alain. Investigating manet performance in a voip context. Canadian Conference an Electrical and Computer Engineering, 2006. IEEE CCECE 2006, May 2006.

[29] P. Chatzimisios, A. C. Boucouvalas, V. Vitsas, A. Vafladis, A. Oikonomidis, and P. Huang. A simple and effective backoff scheme for the IEEE 802.11 MAC protocol. In Cybernetics and Information Technologies, Systems and Applications (CITSA), July 2005.

[30] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang. MACAW : a media access protocol for Wireless LAN'S. In ACM SIGCOMM Computer Communication Review, pages 212--225, London, United Kingdom, 1994.

[31] T. Razaflndralambo, F. Valois. Modélisation et évaluation de performances des stratégies de backoff. Colloque Francophone sur l'Ingénierie des Protocoles - CFIP 2006, Oct 2006.

[32] H. Luo, S. Lu, and V. Bharghavan. A new model for packet scheduling in multihop wireless networks. In ACM Conference on Mobile Computing and Networking (MOBICOM), pages 76--86, Boston, Massachusetts, United States, 2000.

[33] T. Razaflndralambo. Performances des couches MAC dans les réseaux sans fil ad hoc : problèmes et solutions, thèse de doctorat, Institut National des Sicence Appliquées de Lyon, Juillet 2007.

[34] Z. Fang, B. Bensaou, and Y. Wang. Performance evaluation of a fair backoff algorithm for IEEE 802.11 DFWMAC. In ACM Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), pages 48--57, Lausanne, Switzerland, 2002.

[35] C. Chaudet, G. Chelius, H. Meunier, and D. Simplot-Ryl. Adaptive Probabilistic NAV t0 Increase Fairness in Ad Hoc 802.11 MAC. Ad Hoc and Sensor Wireless Networks : an International Journal (AHSWN), In Press., June 2005.

[36] F. A. Tobagi and L. Kleinrock, «Packet Switching in Radio Channels : Part II-The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution,» IEEE Transactions on Communication, vol. 23, no. 12, pp. 1417-1433, 1975.

[37] F. Harivelo, P. Anelli. Equitépour réseau ad hoc Wi-fl. Huitièmes Journées Doctorales en Informatique et Réseaux (JDIR'07), Jan 2007, Marne-la-Vallée, France. pp.77-86, 2007.

[38] M. Youssef. Amélioration de l'équitédu protocole IEEE 802.11 en mode ad hoc, Universitéde sherbrook,Facultéde génie électrique et génie informatique, Août 2006.

57

Bibliographie

Webographie

[39] www.datatracker.ietf.org

[40] www.isi.edu

1

Annexe A

1. Script TCL-OTCL

TCL est un langage conçu pour une utilisation par un développeur de l'application qui peut être participéà travers une demande ou pourrait être utilisépar une application de diverses manières, par exemple, pour permettre à un utilisateur de fournir une initialisation personnalisée pour l'application. L'OTCL est un TCL avec les extensions orientée objet. NS2 utilise otcl pour le programmeur de simulation pour créer les objets de réseau dans la mémoire et d'insérer des événements initiaux dans la file d'attente de l'événement.

2. NAM

NAM est un outil d'animation basésur tcl pour les traces de simulation de réseaux d'ob-servation et des traces de paquets du monde réel. Il prend en charge la topologie mise en page, l'animation au niveau du paquet, et divers outils de contrôle de données. 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.

3. Xgraphe

Xgraph est une application X-Windows qui inclut le traçage interactif et graphique, de portabilitéet de corrections de bugs. Donc, pour tracer les caractéristiques des paramètres NS2 comme le débit, la fin d'un retard de la fin, les paquets d'informations, etc peut être tracée en utilisant xgraph. Le fichier xgraph affiche les informations à propos de la surcharge avec la taille du réseau, Overhead est comparéavec quatre protocoles de routage comme AODV, DSR, DSDV et NEAODV. Les valeurs sont prises à partir des divers fichiers de trace.

1

2

3

4

5

6

Scriptes des simulations Noeud ^caché

set ns [ new Simulator]

set val(chan) Channel/WirelessChannel ;#Channel Type

set val ( prop) Propagation/TwoRayGround ;# radio-propagation model

set val( n e t i f ) Phy/WirelessPhy ;# network interface type

set val(mac) Mac/802 11 ;# MAC type

set val ( i f q ) Queue/DropTail/PriQueue ;# interface queue type

Annexe

7

8

9

10

11

12

13

14

15

16

set val ( l l ) LL ;# link layer type

set val ( ant) Antenna/OmniAntenna ;# antenna model

set val ( i f q l e n ) 50 ;# max packet in ifq

set val (nn) 3 ;# number of mobilenodes

set val(rp) AODV ;# routing protocol

set val(x) 500

set val(y) 500

Phy/WirelessPhy set CSThresh 2.28e-11

Mac/802 11 set dataRate 11Mb

Mac/802 11 set RTSThreshold 10000

17 # set up topography object

set topo [new Topography]

$topo load flatgrid $val (x) $val (y)

20

set namfile [open sample33.nam w]

#Tracing all the events and cofiguration

$ns namtrace-all-wireless $namfile $val (x) $val (y)

24

#Trace File creation

set tracefile [open sample33.tr w]

27

#Open the output files

set f0 [open node 0.tr w]

set f1 [open node 2.tr w]

31

#Tracing all the events and cofiguration

$ns trace-all $ t r a c e f i l e

34

# general operational descriptor- storing the hop details in the network

create-god $val (nn)

37

# configure the nodes

$ns node-config -adhocRouting $val ( rp ) \

40 -llType $val ( l l ) \

41 -macType $val (mac) \

42 -ifqType $val ( i f q ) \

43 -ifqLen $val ( i f q l e n ) \

44 -antType $val ( ant ) \

45 -propType $val (prop) \

46 -phyType $val ( n e t i f ) \

47 -channelType $val ( chan ) \

48 -topoInstance $topo \

49 -agentTrace ON \

50 -routerTrace ON \

51 -macTrace OFF \

52 -movementTrace ON

53

54 # Node Creation

55

38

39

35

36

32

33

28

29

30

25

26

21

22

23

18

19

2

Annexe

}

}

}

62

#Location fixing for a single node

76

# Label and coloring

for { set i 0} { $i < 3} { incr i } {

56

57

set node ( $i ) [ $ns node]

$node ( $i ) color black

63

$node (0) set X 50 .0

$node (0) set Y 10 .0

$node (0) set Z 0 .0

67

$node (1) set X 250 .0

$node (1) set Y 10 .0

$node (1) set Z 0 .0

71

$node (2) set X 450 .0

$node (2) set Y 10 .0

$node (2) set Z 0 .0

75

77

for { set i 0} { $i < 3} { incr i } {

78

79

$ns at 0 .1 »$node ( $i ) color blue»

$ns at 0 .1 »$node ( $i ) label Node$i»

for { set i 0} { $i < 3} { incr i } {

84 #Size of the node

85

86

87

$ns initial node pos $node ( $i ) 30

#Define a ' finish ' procedure

proc finish {} {

global f0 f1

#Close the output files

close $f0

close $f1

#Call xgraph to display the results

exec xgraph node 0.tr node 2.tr -geometry 800x400 &

exit 0

}

#Define a procedure which periodically records the bandwidth received by the

104 #three traffic sinks sink0 /1/2 and writes i t to the three files f0 /1/2 .

58

59

60

61

64

65

66

68

69

70

72

73

74

80

81

82

83

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

3

Annexe

131

$tcp0 set class 2

proc record {} {

global sink0 sink1 f0 f1

107 #Get an instance of the simulator

set ns [ Simulator instance]

#Set the time after which the procedure should be called again

set time 0 .1

#How many bytes have been received by the traffic sinks?

set bw0 [ $sink0 set bytes ]

set bw1 [ $sink1 set bytes ]

114 #Get the current time

set now [ $ns now]

#Calculate the bandwidth ( in MBit/s ) and write i t to the files

puts $f0 »$now [ expr $bw0/$time*8 /1000000]»

puts $f1 »$now [ expr $bw1/$time*8 /1000000]»

#Reset the bytes values on the traffic sinks

$sink0 set bytes 0

$sink1 set bytes 0

#Re-schedule the procedure

$ns at [ expr $now+$time ] » record»

}

#************Defining Communication Between node0 and node2 and node1 *******

set tcp0 [ new Agent/TCP]

set tcp1 [ new Agent/TCP]

130

132

set sink0 [ new Agent/TCPSink ]

set sink1 [ new Agent/TCPSink ]

135

$ns attach-agent $node (0) $tcp0

$ns attach-agent $node (1) $sink0

$ns attach-agent $node (2) $tcp1

$ns attach-agent $node (1) $sink1

140

$ns connect $tcp0 $sink0

$ns connect $tcp1 $sink1

143

set ftp0 [ new Application /FTP]

$ftp0 attach-agent $tcp0

$ftp0 set packetSize 2000

set ftp1 [ new Application /FTP]

$ftp1 attach-agent $tcp1

$ftp0 set packetSize 2000

152

153

105

106

108

109

110

111

112

113

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

133

134

136

137

138

139

141

142

144

145

146

147

148

149

150

151

4

5

Annexe

154 #Start logging the received bandwidth

Noeuds cachées asymétriques

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

$ns at 0 .0 » record»

$ns at 1 .0 » $ftp0 start»

$ns at 1 .0 » $ftp1 start»

#Stop the traffic sources

$ns at 10 .0 » $ftp0 stop»

$ns at 10 .0 » $ftp1 stop»

#Call the finish procedure after 11 seconds simulation time

$ns at 11 .0 » finish»

# Tell nodes when the simulation ends

#

for { set i 0} { $i < $val (nn) } { incr i } {

$ns at 10 .0 »$node ( $i ) reset»;

}

proc stop {} {

global ns namfile

$ns flush-trace

close $namfile

}

puts » Starting Simulation...»

$ns run

set ns [ new Simulator]

set val(chan) Channel/WirelessChannel ;#Channel Type

set val ( prop) Propagation/FreeSpace ;# radio-propagation model

set val( n e t i f ) Phy/WirelessPhy ;# network interface type

set val(mac) Mac/802 11 ;# MAC type

set val ( i f q ) Queue/DropTail/PriQueue ;# interface queue type

set val( l l ) LL ;# link layer type

set val ( ant ) Antenna/OmniAntenna ;# antenna model

set val ( i f q l e n ) 50 ;# max packet in i f q

set val (nn) 4 ;# number of mobilenodes

set val ( rp ) DSDV ;# routing protocol

set val(x) 700

set val(y) 500

Phy/WirelessPhy set CSThresh 30.5e-10

6

Annexe

18 19 20 21 22 23	# set up topography object set topo [ new Topography] $topo load f l a t g r i d $val (x) $val (y)
24	set namfile [ open sample33.nam w]
25
26	#Tracing all the events and cofiguration
27	$ns namtrace-all-wireless $namfile $val (x)	$val (y)
28
29
30	#Trace File creation
31	set t r a c e f i l e [ open sample33.tr w]
32
33	#Open the output files
34	set f0 [ open node 0.tr w]
35	set f1 [ open node 2.tr w]
36
37
38	#Tracing all the events and cofiguration
39	$ns trace-all $ t r a c e f i l e
40
41	# general operational descriptor- storing	the hop	details	in	the	network
42	create-god $val (nn)
43
44	# configure the nodes
45	$ns node-config -adhocRouting $val ( rp ) \
46	-llType $val ( l l ) \
47	-macType $val (mac) \
48	-ifqType $val ( i f q ) \
49	-ifqLen $val ( i f q l e n ) \
50	-antType $val ( ant ) \
51	-propType $val ( prop ) \
52	-phyType $val ( n e t i f ) \
53	-channelType $val ( chan ) \
54	-topoInstance $topo \
55	-agentTrace ON \
56	-routerTrace ON \
57	-macTrace OFF \
58	-movementTrace ON
59
60	# Node Creation
61
62	for { set i 0} { $i < 4} { incr i } {
63
64	set node ( $i ) [ $ns node]
65	$node ( $i ) color black
66

7

Annexe

67		}
68
69 #Location fixing for a single node
70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106		$node (0) set X 200 .0 $node (0) set Y 400 .0 $node (0) set Z 0 .0 $node (1) set X 400 .0 $node (1) set Y 400 .0 $node (1) set Z 0 .0 $node (2) set X 400 .0 $node (2) set Y 200 .0 $node (2) set Z 0 .0 $node (3) set X 600 .0 $node (3) set Y 200 .0 $node (3) set Z 0 .0 # Label and coloring for { set i 0} { $i < 4} { incr i } { $ns at 0 .1 »$node ( $i ) color blue» $ns at 0 .1 »$node ( $i ) label Node$i» } #Size of the node for { set i 0} { $i < 4} { incr i } { $ns initial node pos $node ( $i ) 30 } #Define a ' finish ' procedure proc finish {} { global f0 f1
107 #Close the output files
108 109		close $f0 close $f1
110 #Call xgraph to display the results
111 112 113 114 115		exec xgraph node 0.tr node 2.tr -geometry 800x400 & exit 0 }

8

116

117 118 119 120 121	Annexe
	#Define a procedure which periodically records the bandwidth received proc record {} { global sink0 sink1 f0 f1 #Get an instance of the simulator set ns [ Simulator instance]
122	#Set the time after which the procedure should be called	again
123	set time 0 .1
124	#How many bytes have been received by the traffic sinks?
125	set bw0 [ $sink0 set bytes ]
126	set bw1 [ $sink1 set bytes ]
127	#Get the current time
128	set now [ $ns now]
129	#Calculate the bandwidth ( in MBit/s ) and write i t to the	files
130	puts $f0 »$now [ expr $bw0/$time*8 /1000000]»
131	puts $f1 »$now [ expr $bw1/$time*8 /1000000]»
132	#Reset the bytes values on the traffic sinks
133	$sink0 set bytes 0
134	$sink1 set bytes 0
135	#Re-schedule the procedure
136	$ns at [ expr $now+$time ] » record»
137	}
138
139	#****************Defining Communication Between node0 and	all	nodes	**************
140
141
142	set tcp0 [ new Agent/TCP]
143	set tcp1 [ new Agent/TCP]
144
145	$tcp0 set class 2
146
147	set sink0 [ new Agent/TCPSink ]
148	set sink1 [ new Agent/TCPSink ]
149
150	$ns attach-agent $node (0) $tcp0
151	$ns attach-agent $node (1) $sink0
152	$ns attach-agent $node (2) $tcp1
153	$ns attach-agent $node (3) $sink1
154
155	$ns connect $tcp0 $sink0
156	$ns connect $tcp1 $sink1
157
158	set cbr0 [ new Application/ Traffic /CBR]
159	$cbr0 attach-agent $tcp0
160	$cbr0 set packetSize 250
161	$cbr0 set rate 6 Mb
162	$cbr0 set interval 0 .005
163
164	set cbr1 [ new Application / Traffic /CBR]

9

Annexe

$cbr1 attach-agent $tcp1

$cbr1 set packetSize 250

$cbr1 set rate 6 Mb

$cbr1 set interval 0 .005

#Start logging the received bandwidth

$ns at 0 .0 » record»

$ns at 0 .0 »$cbr0 start»

$ns at 0 .5 »$cbr1 start»

#Stop the traffic sources

$ns at 10 .0 »$cbr0 stop»

$ns at 10 .0 »$cbr1 stop»

#Call the finish procedure after 60 seconds simulation time

$ns at 11 .0 » finish»

# Tell nodes when the simulation ends

#

for { set i 0} { $i < $val (nn) } { incr i } {

$ns at 10 .0 »$node ( $i ) reset»;

}

proc stop {} {

global ns namfile

$ns flush-trace

close $namfile

}

puts » Starting Simulation...»

$ns run

Noeud ^exposé

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

1

2

3

4

5

6

7

8

9

10

11

12

set ns [ new Simulator]

set val(chan) Channel/WirelessChannel ;#Channel Type

set val(prop) Propagation/FreeSpace ;# radio-propagation model

set val ( n e t i f ) Phy/WirelessPhy ;# network interface type

set val(mac) Mac/802 11 ;# MAC type

set val ( i f q ) Queue/DropTail/PriQueue ;# interface queue type

set val ( l l ) LL ;# link layer type

set val ( ant ) Antenna/OmniAntenna ;# antenna model

set val ( i f q l e n ) 50 ;# max packet in i f q

set val (nn) 4 ;# number of mobilenodes

10

Annexe

set val(rp) DSDV ;# routing protocol

#set val(rp) DSR ;# routing protocol

#set val(rp) AODV ;# routing protocol

set val(x) 800

set val(y) 500

Phy/WirelessPhy set CSThresh 30.5e-10

# set up topography object

set topo [new Topography]

$topo load flatgrid $val (x) $val (y)

set namfile [open sample33.nam w]

#Tracing all the events and cofiguration

$ns namtrace-all-wireless $namfile $val (x) $val (y)

#Trace File creation

set tracefile [open sample33.tr w]

#Open the output files

set f0 [open node 1.tr w]

set f1 [open node 2.tr w]

#Tracing all the events and cofiguration

$ns trace-all $ t r a c e f i l e

# general operational descriptor- storing the hop details in the network

create-god $val (nn)

# configure the nodes

$ns node-config -adhocRouting $val ( rp ) \

- llType $val ( l l ) \

- macType $val (mac) \

- ifqType $val ( i f q ) \

- ifqLen $val ( i f q l e n ) \

- antType $val (ant ) \

- propType $val (prop) \

- phyType $val ( net i f ) \

- channelType $val ( chan ) \

- topoInstance $topo \

- agentTrace ON \

- routerTrace ON \

- macTrace OFF \

- movementTrace ON

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

11

Annexe

# Node Creation

for { set i 0} { $i < 4} { incr i } {

set node ( $i ) [ $ns node]

$node ( $i ) color black

}

#Location fixing for a single node

$node (0) set X 100 .0

$node (0) set Y 300 .0

$node (0) set Z 0 .0

$node (1) set X 300 .0

$node (1) set Y 300 .0

$node (1) set Z 0 .0

$node (2) set X 500 .0

$node (2) set Y 300 .0

$node (2) set Z 0 .0

$node (3) set X 700 .0

$node (3) set Y 300 .0

$node (3) set Z 0 .0

# Label and coloring

for { set i 0} { $i < 4} { incr i } {

$ns at 0 .1 »$node ( $i ) color blue»

$ns at 0 .1 »$node ( $i ) label Node$i»

}

#Size of the node

for { set i 0} { $i < 4} { incr i } {

$ns initial node pos $node ( $i ) 30

}

#Define a ' finish ' procedure

proc finish {} {

global f0 f1

#Close the output files

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111 112 113 114	Annexe
	close $f0 close $f1 #Call xgraph to display the results exec xgraph node 1.tr node 2.tr -geometry 800x400	&
115	exit 0
116	}
117
118
119
120	proc record {} {
121	global sink0 sink1 f0 f1
122	#Get an instance of the simulator
123	set ns [ Simulator instance]
124	#Set the time after which the procedure should be	called	again
125	set time 0 .1
126	#How many bytes have been received by the traffic	sinks?
127	set bw0 [ $sink0 set bytes ]
128	set bw1 [ $sink1 set bytes ]
129	#Get the current time
130	set now [ $ns now]
131	#Calculate the bandwidth ( in MBit/s ) and write i t	to the	files
132	puts $f0 »$now [ expr $bw0/$time*8 /1000000]»
133	puts $f1 »$now [ expr $bw1/$time*8 /1000000]»
134	#Reset the bytes values on the traffic sinks
135	$sink0 set bytes 0
136	$sink1 set bytes 0
137	#Re-schedule the procedure
138	$ns at [ expr $now+$time ] » record»
139	}
140
141	#********Defining Communication Between node0 and	all nodes *******
142
143
144	set tcp0 [ new Agent/TCP]
145	set tcp1 [ new Agent/TCP]
146
147	$tcp0 set class 2
148
149	set sink0 [ new Agent/TCPSink ]
150	set sink1 [ new Agent/TCPSink ]
151
152	$ns attach-agent $node (1) $tcp0
153	$ns attach-agent $node (0) $sink0
154	$ns attach-agent $node (2) $tcp1
155	$ns attach-agent $node (3) $sink1
156
157	$ns connect $tcp0 $sink0
158	$ns connect $tcp1 $sink1
159

12

13

Annexe

set cbr0 [ new Application / Traffic /CBR]

$cbr0 attach-agent $tcp0

$cbr0 set packetSize 250

$cbr0 set rate 6 Mb

$cbr0 set interval 0 .005

set cbr1 [ new Application / Traffic /CBR]

$cbr1 attach-agent $tcp1

$cbr1 set packetSize 250

$cbr1 set rate 6 Mb

$cbr1 set interval 0 .005

#Start logging the received bandwidth

$ns at 0 .0 » record»

$ns at 0 .0 »$cbr0 start»

$ns at 0 .5 »$cbr1 start»

#Stop the traffic sources

$ns at 10 .0 »$cbr0 stop»

$ns at 10 .0 »$cbr1 stop»

#Call the finish procedure after 60 seconds simulation time

$ns at 11 .0 » finish»

# Tell nodes when the simulation ends

#

for { set i 0} { $i < $val (nn) } { incr i } {

$ns at 10 .0 »$node ( $i ) reset»;

}

#$ns at 10 .0 »stop»

#$ns at 10 .01 »puts \»NS EXITING...\» ; $ns halt»

proc stop {} {

global ns namfile

$ns flush-trace

close $namfile

}

puts » Starting Simulation...»

$ns run

Les trois paires

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

1

2

3

set ns [ new Simulator]

#Fixing the co-ordinate of simulation area

14

Annexe

4 5 6 7 8	set val(x) 500 set val(y) 500 # Define options set val(chan) Channel/WirelessChannel ;# channel type set val ( prop) Propagation/TwoRayGround ;# radio-propagation model
9	set val( net i f ) Phy/WirelessPhy ;# network interface type
10	set val(mac) Mac/802 11 ;# MAC type
11	set val ( i f q ) Queue/DropTail/PriQueue ;# interface queue type
12	set val ( l l ) LL ;# link layer type
13	set val ( ant ) Antenna/OmniAntenna ;# antenna model
14	set val ( i f q l e n ) 50 ;# max packet in i f q
15	set val (nn) 6 ;# number of mobilenodes
16	set val ( rp ) AODV ;# routing protocol
17	set val (x) 500 ;# X dimension of topography
18	set val (y) 500 ;# Y dimension of topography
19	set val(stop) 10 .0 ;# time of simulation end
20
21	Mac/802 11 set dataRate 11Mb
22	Mac/802 11 set basicRate 1Mb
23	Mac/802 11 set RTSThreshold 10000
24
25
26	# set up topography object
27	set topo [ new Topography]
28	$topo load f l a t g r i d $val (x) $val (y)
29
30
31	set namfile [ open sample33.nam w]
32
33	#Tracing all the events and cofiguration
34	$ns namtrace-all-wireless $namfile $val (x) $val (y)
35
36
37	#Trace File creation
38	set t r a c e f i l e [ open sample33.tr w]
39
40	#Open the output files
41	set f0 [ open node 0.tr w]
42	set f1 [ open node 1.tr w]
43	set f2 [ open node 2.tr w]
44
45
46	#Tracing all the events and cofiguration
47	$ns trace-all $ t r a c e f i l e
48
49	# general operational descriptor- storing the hop details in	the	network
50	create-god $val (nn)
51
52	# configure the nodes

Annexe

53 $ns node-config -adhocRouting $val ( rp ) \

54 -llType $val ( l l ) \

55 -macType $val (mac) \

56 -ifqType $val ( i f q ) \

57 -ifqLen $val ( i f q l e n ) \

58 -antType $val ( ant ) \

59 -propType $val ( prop ) \

60 -phyType $val ( n e t i f ) \

61 -channelType $val ( chan ) \

62 -topoInstance $topo \

63 -agentTrace ON \

64 -routerTrace ON \

65 -macTrace OFF \

66 -movementTrace ON

67

68 # Node Creation

69

70

for { set i 0} { $i < 6} { incr i } {

71

72

73

74

75

76

set node ( $i ) [ $ns node]

$node ( $i ) color black

}

77 #Location fixing for a single node

78

79

80

81

$node (0) set X 200 .0

$node (0) set Y 400 .0

$node (0) set Z 0 .0

82

83

84

85

$node (1) set X 500 .0

$node (1) set Y 400 .0

$node (1) set Z 0 .0

86

87

88

89

$node (2) set X 800 .0

$node (2) set Y 400 .0

$node (2) set Z 0 .0

90

91

92

93

$node (3) set X 200 .0

$node (3) set Y 200 .0

$node (3) set Z 0 .0

94

95

96

97

$node (4) set X 500 .0

$node (4) set Y 200 .0

$node (4) set Z 0 .0

98

99

100

101

15

$node (5) set X 800 .0

$node (5) set Y 200 .0

$node (5) set Z 0 .0

16

Annexe

102 103 104 105		# Label and coloring
106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123		for { set i 0} { $i < 6} { incr i } { $ns at 0 .1 »$node ( $i ) color blue» $ns at 0 .1 »$node ( $i ) label Node$i» } #Size of the node for { set i 0} { $i < 6} { incr i } { $ns initial node pos $node ( $i ) 30 } #Define a ' finish ' procedure proc finish {} { global f0 f1 f2
124 #Close the output files
125 126 127 128 129 130 131 132 133 134 135 136 137 138 139		close $f0 close $f1 close $f2 #Call xgraph to display the results exec xgraph node 0.tr node 1.tr node 2.tr -geometry 800x400 & exit 0 } proc record {} { global sink0 sink1 sink2 f0 f1 f2 #Get an instance of the simulator set ns [ Simulator instance]
140 #Set the time after which the procedure should be called again
141 142 143 144 145 146 147 148 149 150		set time 0 .1 #How many bytes have been received by the traffic sinks? set bw0 [ $sink0 set bytes ] set bw1 [ $sink1 set bytes ] set bw2 [ $sink2 set bytes ] #Get the current time set now [ $ns now] #Calculate the bandwidth ( in MBit/s ) and write i t to the files puts $f0 »$now [ expr $bw0/$time*8 /1000000]» puts $f1 »$now [ expr $bw1/$time*8 /1000000]»
151 152 153 154 155 156			Annexe
			puts $f2 »$now [ expr $bw2/$time*8 /1000000]» #Reset the bytes values on the traffic sinks $sink0 set bytes 0 $sink1 set bytes 0 $sink2 set bytes 0 #Re-schedule the procedure
157			$ns at [ expr $now+$time ] » record»
158			}
159
160			#*******Defining Communication Between node0 and	all	nodes	*******
161
162
163			set tcp0 [ new Agent/TCP]
164			set tcp1 [ new Agent/TCP]
165			set tcp2 [ new Agent/TCP]
166
167			$tcp0 set class 2
168
169			set sink0 [ new Agent/TCPSink ]
170			set sink1 [ new Agent/TCPSink ]
171			set sink2 [ new Agent/TCPSink ]
172
173			$ns attach-agent $node (0) $tcp0
174			$ns attach-agent $node (3) $sink0
175			$ns attach-agent $node (1) $tcp1
176			$ns attach-agent $node (4) $sink1
177			$ns attach-agent $node (2) $tcp2
178			$ns attach-agent $node (5) $sink2
179
180			$ns connect $tcp0 $sink0
181			$ns connect $tcp1 $sink1
182			$ns connect $tcp2 $sink2
183
184			set cbr0 [ new Application/ Traffic /CBR]
185			$cbr0 attach-agent $tcp0
186			$cbr0 set packetSize 1500
187			$cbr0 set rate 6 Mb
188			$cbr0 set interval 0 .0001
189
190			set cbr1 [ new Application / Traffic /CBR]
191			$cbr1 attach-agent $tcp1
192			$cbr1 set packetSize 1500
193			$cbr1 set rate 6 Mb
194			$cbr1 set interval 0 .0001
195
196			set cbr2 [ new Application/ Traffic /CBR]
197			$cbr2 attach-agent $tcp2
198			$cbr2 set packetSize 1500
199			$cbr2 set rate 6 Mb

17

Annexe

200

201

202

203

204

205

206

207

208

209

221

222

223

224

225

226

227

228

229

230

231

$cbr2 set interval 0 .0001

#Start logging the received bandwidth $ns at 0 .0 » record»

$ns at 1 .0 »$cbr0 start» $ns at 1 .5 »$cbr1 start» $ns at 1 .0 »$cbr2 start»

210

211

212

213

214

#Stop the traffic sources $ns at 10 .0 »$cbr0 stop» $ns at 10 .0 »$cbr1 stop» $ns at 10 .0 »$cbr2 stop»

215

216

217

#Call the finish procedure after 60 seconds simulation time $ns at 11 .0 » finish»

218

219 # Tell nodes when the simulation ends

220 #

for { set i 0} { $i < $val (nn) } { incr i } {

$ns at 10 .0 »$node ( $i ) reset»;

}

proc stop {} { global ns namfile $ns flush-trace close $namfile }

puts » Starting Simulation...» $ns run

18

Résumé

La norme IEEE 802.11 est devenue un standard de la technologie sans fil. Cependant, son utilisation dans les réseaux ad hoc pose des problèmes de performance et en particulier, en terme d'équité d'accès au médium.

Dans ce mémoire nous avons mis en lumière les problèmes d'équité liées à la couche MAC 802.11 (par la théorie et la simulation) et l'analyse de leurs impacts.

Nous avons aussi fait l'étude de quelques solutions apportées à ces problèmes (algorithmes de backoff, MadMac et FWM).

Mots clés : Ad hoc, problèmes d'équité, IEEE 802.11, couche MAC, FWM, Bachoff, Mad-Mac, DCF, CSMA/CA, NS2.

Abstract

Computer systems continue to evolve and improve, so they are needed more and more in the management of the working environment of modern companies, this is related to their advantages provided in the field of databases and the simplification of the general management. The transport service Bejaia Regional Directorate of Sonatrach wants to automate the management of its fleet. To achieve this goal, we proposed to design and produce a 3-tier web application for an easy management, a convenient and efficient management of this departe-ment.

First, we chosed the 2TUP development process, we chosed to model our project.

On the other hand, for the realization of this application, we used a MySQL database server, as well as HTML, CSS, PHP, JavaScript. This with the Adobe Dreamweaver editor.

Keywords : Ad hoc, problems of equity, IEEE 802.11, MAC layer, FWM, Bachoff, Mad-Mac, DCF, CSMA/CA, NS2.