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

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