Etude de l'équité dans les réseaux ad-hoc

Mathias Péron
Rapport de stage MIM1 - 2003

 
 
Résumé
Ce rapport souhaite donner une description globale et précise du problème de l'équité au niveau de la couche réseau MAC et dresser l'éventail des algorithmes jusqu'ici proposés.
Après une courte présentation des réseaux ad-hoc, le lecteur trouvera la description constructive du protocole MAC standard de 802.11 suivant les problèmes qui ont été rencontrés. La seconde partie soulève des questions d'ordre général sur l'équité et explore l'ensemble des algortithmes connus. Suit une description formelle du phénomène d'inégalité. Les deux sections suivantes traitent d'inégalité due à des raisons protocolaires ou intrinsèques aux réseaux ad-hoc. Enfin les derniers paragraphes sont consacrés à l'algorithme que nous proposons et à décrire ce que de futurs travaux devraient aborder.

 
 
             

Table des matières

1  Introduction

Les réseaux ad-hoc sont des réseaux locaux utilisant le médium radio. Ils sont constitués d'entités sans fil et mobiles ne détenant aucun rôle préalable. Aucune station de base n'entre en jeu.
Ainsi, de par leur mobilité, leur déploiement rapide et le fait qu'ils ne nécéssitent aucune infrastructure fixe, les réseaux ad-hoc trouvent de nombreuses applications tant dans le civil, par exemple lors de catastrophes naturelles pour déployer les secours (avec des problématiques comme le ratachement à un réseau filaire. On parle de réseaux hybrides*) que dans le monde militaire où l'on a la conviction de l'enjeu de maîtriser la technologie ad-hoc (avec des applications comme les réseaux de capteurs: sensor-networks*).
Les problématiques ouvertes sont nombreuses (comme par exemple la phase d'admission d'un noeud , les garanties de sécurité et confidentialité et la qualité de service (QoS)). Pourtant, la plupart des recherches se sont focalisées jusqu'ici sur les problèmes de routage. Elles ont été menées sous l'hypothèse que la gestion du médium, confiée à la couche MAC (Medium Access Control), était sans faille.
Une couche MAC a été définie par l'IEEE dans le standard 802.11. Cependant, des recherches ont montré que son fonctionnement rencontrait de nombreuses défaillances dans le cadre des réseaux ad-hoc. Celle qui nous intéresse est le problème de l'accès équitable au médium de communication pour tous les mobiles du réseau. En effet, ne pas permettre à tous les mobiles d'accéder au réseau peut créer des dysfonctionnements importants.
Nous allons donc débuter notre réflexion par la compréhension du standard 802.11 dans la section 2. Nous approfondirons notre savoir des phénomènes qui mettent à mal l'équité dans les sections 3, 5 et 6. Pour terminer nous décrirons la solution proposée.

2  le protocole de l'IEEE 802.11

Le protocole 802.11 est un standard de l'IEEE qui définit une couche physique et une couche MAC pour les réseaux locaux sans fil. Le premier standard a été défini en 1997. Il opère sur la bande de fréquence 2.4 GHz et permet des débits de 2 Mb/s.
Actuellement les fabriquants de cartes réseaux sans fil s'en tiennent au standard 802.11b qui travaille dans la même bande de fréquence mais permet un débit de 11 Mb/s. Le protocole MAC de 802.11, d'ailleurs identique à celui de 802.11b, est connu sous le nom de DFWMAC.

2.1  Vue d'ensemble de DFWMAC

DFWMAC est un protocole de type CSMA/CA (Carrier Sense Multiple Access) c'est à dire qui opère dans un environnement à médium partagé où il tente de limiter les collisions (Collision Avoidance). En effet, il est impossible pour un mobile qui transmet de détecter s'il y a eu ou non collision, puisque la collision éventuelle se situe au niveau du mobile récepteur, et parceque le médium radio ne permet pas à l'émetteur d'écouter le médium pendant qu'il l'utilise. Le protocole ne peut donc qu'essayer d'éviter les collisions.
Dans cette optique, le protocole utilise des paquets d'acquittement -- on assure que le paquet de donnée a été transmis avec succès -- et un temps aléatoire afin de réguler les envois -- on réduit la probabilité de collision. L'algorithme d'envoi d'un paquet de donnée suivi d'un chronogramme explicatif sont donnés ci-dessous.
 
Attendre que le médium soit libre
Attente d'un temps fixe DIFS
pendant lequel le médium doit rester libre
Tirage aléatoire dans [0,CW] (Contention Window) de la valeur BACKOFF
(fenêtre de contention)
 
Tant que le médium est libre
décrémenter BACKOFF
 
Si BACKOFF est nul
envoi du paquet DATA
attente SIFS, correspondant au temps de transmission du paquet
réception du paquet ACK
 
Sinon retour au début, avec BACKOFF *restant*
 


Figure 1 : Cycle de transmission d'un paquet


L'idée générale est d'instaurer un temps d'attente où le médium doit être libre et statistiquement différent pour chaque mobile. Le tirage aléatoire s'effectue dans une fenêtre appellée fenêtre de contention CW. On assure ainsi une distribution équitable du médium. Un noeud ne peut pas non plus se trouver en situation de famine puisque son temps d'attente BACKOFF diminue à chaque échec de prise du médium jusqu'à la valeur nulle. Enfin la réception de l'acquitement (ACK) scelle la réussite de la transmission.

2.2  Diffusion radio et conséquences

Lorsque l'on transmet sur le médium radio, le signal est diffusé dans un espace que l'on peut assimiler à une sphère. Ci-dessous on a représenté un flux du noeud a au noeud b, avec leurs sphères de transmission/réception (on supposera leurs tailles identiques).
Tout noeud dans la zone (i) tombe sous le coup de la diffusion, broadcast en anglais, radio du noeud a. Il peut donc établir une communication avec a, mais il ne peut recevoir, c'est à dire interpréter, de signaux d'autres noeuds . On parle de noeuds exposés à une transmission.
La seconde zone (ii) délimite la portée de réception du noeud b. Ainsi s'il se trouve des noeud émetteurs dans cet espace, leur signal interférera en b avec celui produit par a et il y a collision.
Enfin notons que pendant l'émission de l'ACK, ces deux zones s'inversent.

         
 
(i) noeuds exposés aux
émissions de a

(ii) noeuds dont l'émission
interfère à la réception en b
 
 
 

Figure 2 : Problème de la diffusion radio


L'ensemble de ces noeuds (i) et (ii) sont sous la contrainte du flux ab, il sont en compétition d'accès au médium, en anglais contention1. Ceci nous mène à deux constations :
Afin de régler le problème, la norme 802.11 spécifie l'ajout au cycle de transmission d'un envoi de paquets de réservation du médium, nommés Request-To-Send (RTS) et Clear-To-Send (CTS), et envoyés respectivement par le transmetteur et le récepteur.
Le RTS2 est une demande d'allocation du médium et le CTS en est la réponse favorable et une injonction aux autres noeuds de rester inactifs (DEFER). Les paquets contiennent dans ce but un champ Duration3 (durée) qui spécifie le temps d'occupation du médium -- i.e. 2×SIFS+DATA+ACK.
Les chronogrammes dans le scénario des noeuds cachés sont donnés à la page suivante (Fig. 4)


Figure 4 : Le cycle de transmission avec les RTS/CTS


Le noeud c, touché par le CTS de b, ne peut débuter de transmission. Après lecture du CTS, il se place en attente DEFER, le mettant à égalité pour prendre le médium une fois que le noeud a a reçu l'acquitement.
Ainsi la zone (ii) est protégée des interférences par les RTS/CTS4. Notons que l'ensemble de ces messages de signalisation font du médium radio une ressource très coûteuse en terme d'accès (temps d'accès double à celui du filaire).

2.3  Des interférences

On distingue deux zones de transmission, la portée de communication (TR, Transmission range) où tout signal est parfaitement traité et compris et la portée de détection (SR, Sensing Range) qui constitue l'espace où un noeud détecte de l'activité mais n'est pas en mesure d'en tirer de l'information.


Lorsqu'un noeud détecte de l'activité dans son SR, il considère le médium occupé. Il se place alors en mode de détection de porteuse (CS, Carrier Sense) avant de reprendre son cycle de transmission.
Dans la figure 5 le noeud c se trouve dans cette situation : il ne détecte que du bruit de la part de a. Par contre il est trop éloigné de b pour le détecter.


Figure 5 : Une situation délicate


Or lorsque c se trouve dans la zone SR de l'emetteur, il n'a pas pu, à partir du RTS ou du DATA, conclure la valeur du champ Duration: il se positionne donc en CS et non en DIFFER, ce que l'on aperçoit sur les chronogrammes suivants.


Figure 6 : Chronogramme associé au scénario de la figure 5


On a montré ici le cas où c a réussi à débuter sa transmission -- le médium lui apparaît en effet libre -- alors que b émettait son acquitement. On a donc collision au noeud a5, repérée en gris foncé.
Il s'agit ici d'une faille qui oblige la norme à inclure un nouveau délai d'attente après chaque période CS, équivalent à SIFS+ACK+DIFS. Ce delai qui est nommé EIFS (Extended Inter Frame Space), permet la bonne réception des ACKs (ici en a) et de reporter le début du décompte du Backoff au même moment pour les deux noeuds concernés (a et c), afin que la prise du médium reste équitable.

2.4  De la mobilité

Il est clair que les mécanismes de RTS/CTS et à fortiori d'EIFS peuvent se révéler totalement inefficaces si les noeuds bougent durant la transmission, ou que d'autres entrent dans le réseau, créant des interférences. L'exemple le plus simple est celui d'un noeud qui une fois qu'il a recu un paquet de données s'éloigne trop de l'émetteur avant d'envoyer son acquitement.
Par la suite, on ne s'attardera pas sur la mobilité des noeuds mais sur des scénarii fixes où l'équité est discutée ou encore mise à mal. La description du protocole 802.11 étant terminée, il s'agit à présent de se questionner sur ce que l'on nomme équité.

3  Ce que devrait être l'équité

L'idée informelle d'équité est celle où un ensemble de noeuds en compétition pour le médium se partage la bande passante. Cette définition est une vision par noeud de l'équité. Cependant, on peut dans la situation suivante, à gauche, où tous les flux sont en compétition les uns avec les autres, vouloir que chaque flux détienne le même débit -- throughput en anglais -- plutôt que chaque noeud .
Signalons que 802.11 ne peut fournir d'autre vision que celle par noeud .

     
Figure 7 : Equité par flux


Dans la partie droite de la figure 7, en supposant que le flux 1 souffre de contention (réception brouillée par exemple) il devient illogique comme dans 802.11, d'appliquer la même valeur de CW pour le flux 2, lui faisant perdre du temps et donc du débit.
Fort de cette dernière constation, Bharghavan et al [2] proposent un protocole, MACAW, basé sur une application par flux de l'algorithme de Backoff. Celui-ci est d'ailleurs légèrement modifié: il double la fenête de contention CW à chaque collision à l'instar de BEB mais la décrémente à chaque paquet transmis avec succès, d'où son nom MILD (Multiplicative Increase Linear Decrease).
Nous retiendrons les deux idées suivantes: Dans ce sens, Ozugur et al [3] proposent le protocole CB-fair qui utilise la persistance. La persistance est la probabilité qu'une fois le Backoff expiré, la transmission s'effectue. Notons que 802.11 la spécifie à 1. Pour les chercheurs elle peut réguler les situations de compétition. Ainsi il propose d'appliquer un taux proportionnel au ratio du degré (au sens des flux) du récepteur sur le degré maximum des voisins du transmetteur, données qui sont diffusées à travers le réseau. Là encore l'algorithme de Backoff est modifié lorsqu'une transmission est sans erreur : on divise par deux la fenêtre de contention CW.
On retiendra surtout que l'on peut réguler les envois autrement qu'en modifiant simplement le paramètre CW. En effet la persistance est certainenement le meilleur moyen de modéliser une allocation du médium faîte à un noeud ou à un flux et ainsi éviter les compétitions d'accès.
Nos deux papiers précédents cherchent à modifier l'algorithme d'ajustement de la fenêtre de contention (CW), obtenant d'ailleurs de meilleurs résultats. En effet, l'algorithme BEB se résume en favoriser la dernière station ayant réussi une transmission. Il est évident que ceci va à l'encontre d'une station qui n'arriverait pas à transmettre. Une étude combinatoire sur les chargements du paramètre CW permettrait de dire s'il doit être réellement stabilisé ou fluctuant, mais aucune recherche n'a été menée sur ce sujet.
Il est à noter que les protocoles MACAW et CB-FAIR font figure de référence pour évaluer les performances de nouveaux protocoles. Ils améliorent sensiblement l'équité dans plusieurs scénarios par rapport au protocole de 802.11. Cependant nous allons nous intéresser à present à ce qu'ils ne résolvent pas et à exposer un point de vue plus large du problème.

4  Ce qu'est l'inégalité

4.1  Un scénario simple

Voici ci-dessous un scénario irrésolu par les protocoles vus précédement. Il s'agit de deux flux, avec le récepteur de l'un en portée de communication avec l'émetteur de l'autre. Certains parleront de noeud caché (0&2); d'autres de noeud exposé (1).

   
Figure 8 : Scénario noeuds cachés & exposés : résultats


A droite, le graphique6 représente le débit des noeuds 2 (courbe haute) et 0 au cours du temps (première phase : montée du débit, puis à 3s. débit maximum) sous 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 de 0. Il ne renvoie donc aucun CTS placant le noeud 0 en situation de famine.
Conséquence désastreuse de l'algorithme BEB -- qui s'applique ici du au non retour de CTS --, la fenêtre de contention CW du noeud 0 reste bloquée à la borne maximum écartant toute chance d'accès au médium.
Notons surtout que le noeud 2 n'a aucun retour d'information sur le problème. Il occupe le médium en toute bonne foi. Cette simulation nous a conduit à revoir le problème d'un point de vue plus global. C'est ce que traite le paragraphe suivant.

4.2  Approche théorique de l'équité

Il s'agit de proposer un modèle qui capture tous les cas de compétition. On définit un lien radio entre deux noeuds lorsque ceux-ci sont dans leur zone TR. Ces noeuds sont dits voisins (TR-voisinage). On parle aussi de SR-voisinage.


Soit un flux F. Si l'on se souvient des zones (i)(ii), définies dans la Fig. 2, un certain nombre de contraintes sont posées autour du flux ab. De plus, les zones s'inversent lors de l'émission des paquets CTSs/ACKs. Ainsi l'ensemble des flux qui mettent en jeu des noeuds se trouvant dans l'une de ces deux zones rentrera indubitablement en compétition avec le flux ab pour l'accès au médium.
La Fig. 9 résume de façon shématique l'ensemble des flux en compétition avec F.

--- lien TR où un flux serait en compétition avec F
- - lien SR
Ñ émetteur possible avec de la synchronisation: parallèleRTS*

Figure 9 : Dessin synoptique des flux en contention avec F


Le protocole 802.11 est bien loin de toutes ces considérations. Par contre, pas de celles de Bharghavan [4] qui propose de construire un flow contention graph G où les noeuds sont les flux du réseau et où les arêtes symbolisent l'existence de compétition entre eux.
La Fig. 10 donne un exemple de réseau et le graphe G correspondant. La première information qu'il fournie est que dans une même clique, un seul flux peut être utilisé.
Cependant une dernière étape de modélisation est nécessaire afin d'élire correctement les flux qui peuvent être actifs simultanément. Il s'agit de construire le ressource graphe, graphe biparti avec d'un côté des noeuds représentant les cliques maximales de G appelées serveurs et de l'autre côté les flux. On a alors une arête ssi le flux appartient à un serveur dans G.


         
Figure 10 : Dans l'ordre: exemple, flow contention graph G et ressource graph


Ainsi un protocole simple évitant toute situation de compétition pourrait être d'utiliser un système de jetons. Les serveurs disposent chacun d'un jeton et un flux peut être actif ssi il a reçu le jeton de chaque serveur auquel il est incident.
Ceci étant il reste à définir :
Algorithme résultant
Les mêmes chercheurs proposent d'appliquer V à l'aide de la persistance et que la fenêtre de contention CW soit unique à l'ensemble des flux d'une clique puisqu'ils sont tous en compétition pour utiliser un même médium.
Ils donnent un cadre général pour établir le vecteur V qui bien sûr dépend du graphe G. De nombreux chercheurs [5] se sont penchés sur le critère d'équité max-min afin d'allouer V. Les résultats sont difficilement évaluables. De plus des études menées per l'EPFL [6] ont montré que dans des scénarios simples il n'était pas souhaitable d'un point de vue de l'équité, d'utiliser ce critère d'allocation.
L'algorithme final que propose Bharghavan ne tient pas compte du graphe G pour les raisons invoquées au paragraphe précédent. Le vecteur d'allocation évolue selon les pertes que chaque flux subit. Les résultats sont sensiblement meilleurs que ceux de CB-FAIR et MACAW mais les simulations exposées mettent toujours en jeu des réseaux denses où certains problèmes peuvent être gommés, comme nous allons le voir au chapitre suivant.

5  Une inégalité protocolaire

Fort de ces résultats sur les compétitions d'accès, nous nous sommes demandés si l'inégalité ne pouvait pas apparaître sous d'autres aspects dans 802.11.
Le système de l'EIFS -- cf section 2.3 -- nous a alors interpellé. En effet, l'EIFS correspond à une attente obligatoire et sa condition de déclenchement -- après tout passage en détection de porteuse CS -- ne paraissait pas rendre compte de tous les cas possibles.
Ci-dessous deux scénarios, où le flux 01 est en mouvement -- 0 vers 0'. Les arcs en pointillés dénotent la zone SR du noeud 3; les liens en pointillés indiquent que deux noeuds sont dans leurs zone SR; les liens pleins, dans leur zone TR.

         
Figure 11 : Les deux problèmes de l'EIFS


Scénario de gauche
réalisé sans RTS/CTS, 0 en 0'. Supposons que 0 soit en CS dû au DATA transmis par 2. Il s'en suit un premier EIFS qui va être stoppé par la transmission de l'acquitement de 3. En effet comme 0 se trouve également dans la zone SR de 3 quand 0 est en 0', il se retrouve en CS. Automatiquement un second EIFS est ajouté, qui est inutile puisque la réception de l'ACK de 3 en 2 a déja été protégée (comme indiqué dans le chronogramme figure 12). l'EIFS devient alors une pénalité pour le noeud 0 qu'il subit à chaque fois qu'il souhaite débuter un cycle de transmission. La prise du médium est inéquitable.


Figure 12 : Large EIFS: chronograme -- sans RTS/CTS


Sur la partie gauche de la figure 14 (graphique des débits de 0 et 2), lors des 5 premières secondes, le noeud 0 est encore au-delà de la zone SR de 3, l'équité est visible. Puis le noeud 0 rentre dans la zone SR de 3, le noeud 2 prend alors le pas sur le noeud 0.
Scénario de droite
réalisé avec RTS/CTS, 0 en 0'. Il s'agit du même problème reporté sur le CTS. Lorsque le noeud 0 se trouve dans la zone SR de 3, il va se placer en CS lorsque 3 va émettre un CTS. Cette fois, l'EIFS étant plus court que le délai SIFS+DATA. Le noeud 0 pourrait être à même de commencer une transmission, puisqu'il n'a pas connaissance du noeud 2 et n'a pas pû tirer d'information du CTS. Si c'est ce qui se produit, deux collisions peuvent survenir (Fig 13). Une première avec le DATA de 2 au noeud 3. Si celle ci n'a pas eu lieu (le RTS est émis pendant le SIFS qui suit le DATA) une seconde a lieu avec l'ACK de 3 au noeud 1.


Figure 13 : Small EIFS: chronograme -- avec RTS/CTS


L'interprétation du graphique (partie droite de la figure 14 est plus difficile. La première partie correspond au moment où 0 est encore dans la zone TR de 3 (on se retrouve dans la configuration de la figure 8), occupant tout le médium. Puis 0 passe dans la zone SR de 3, cas que l'on vient de décrire. On remarque que son débit devient nul8. N'accédant pas au médium sa fenêtre de contention CW est au maximum. Enfin le noeud 2 émet mais à 60 % en dessous du débit maximal, confirmant l'analyse: le noeud 0 envoi toujours des RTS qui brouillent la réception au noeud 3.


Figure 14 : EIFS: résultats des simulations


Le problème a été reconnu également par Li et al. [7] dans d'autres configurations. Ils nomment le premier problème large-EIFS puisque l'EIFS est trop long par rapport à ce qu'il devrait être et le second small-EIFS puisque trop court pour rendre réellement compte de l'occupation du médium.
Ils proposent une solution basée sur l'idée que dans la zone SR, selon le temps passé en CS, on peut conclure si on se trouve dans l'une ou l'autre des deux situations. Une technique difficile à mettre en oeuvre et peu fiable.
La solution que nous proposons dans le dernier chapitre semble résoudre le problème.

6  Une inégalité intrinsèque

Au sein de notre laboratoire Dominique Dhoutaut [8] a mis à jour un scénario capable de déjouer bon nombre de protocoles. La simulation sera donc encore faite sous 802.11. Il s'agit du problème des trois paires nommé ainsi puisqu'il met en jeux trois flux parallèles.


Figure 15 : Le scénario des trois paires


Lorsque le flux central se trouve dans les zones SR des flux extérieurs, il souffre des problème de l'EIFS que nous venons de décrire. Cependant, même en suposant ce problème résolu, un second facteur intervient: la synchronisation. En effet, les deux paires extérieures ne sont pas obligées d'émettre en même temps, c'est-à-dire d'avoir leurs cycles de transmission en phase.

En effet, les noeuds 0 et 4 peuvent émettre de telle façon que leurs paquets DATA se chevauchent. Le chronogramme (Fig. 16) retrace les activités des noeuds lorsque 2 se trouve dans les zones SR des deux noeuds extérieurs. Le noeud 2 ne peut que se placer en détection de porteuse (CS), ad vitam et aeternam, sans même avoir la possibilité d'émetre un RTS.

         
Figure 16 : Les trois paires: chronogramme & résultats


Le graphique des débits montre que jusqu'à 5s, les noeuds 0, 2 et 4 ne se détectent pas. De 5s. à 23s. les noeuds 0 et 4 sont dans la zone SR du noeud 2. Cependant si l'inégalité apparaît instantanément elle n'est que plus franche à partir de la seconde 10. L'explication tient dans le fait que les flux extérieurs ne sont pas parfaitement désynchronisés, permettant au noeud 2 d'envoyer quelques RTS qui n'auront pas de réponse dû au problème de l'EIFS. La fenêtre de contention CW du noeud 2 grimpe à la valeur maximale. Son débit restera presque nul jusqu'à ce que les noeuds 0 et 4 arrivent dans la zone TR de 2, moment où l'équité est respectée.
Le problème des trois paires est le plus ennuyeux de tous et à deux titres: Ainsi, il s'agit bien d'un problème intrinsèque au médium radio, puisque des noeuds peuvent être en compétition avec d'autres noeuds sans qu'aucune communication claire soit possible entre eux sur ce même médium pour résoudre le problème.

7  Une solution

Il n'y a pas de recherche de solutions sans établir préalablement de bilan. Il est à noter que notre compréhension de la couche MAC des réseaux ad-hoc n'a pas suivi le même déroulement dans ce rapport que pendant le stage.
Celui-ci avait au programme la mise en place de protocoles récents. Nous avons choisi d'implémenter sous NetworkSimulation NS un algorithme de résolution de fenêtre de contention CW, proposé par M. Bensaou [9], afin de l'évaluer.
L'une des conclusions qu'on peut tirer des chapitres précédents est que le graphe de compétition G ne saisit pas la totalité des problèmes de l'équité, que ce soit dans le cas de notre premier scénario (Fig. 8) ou dans le cas des problèmes de l'EIFS. Tous ces flux appartiendraient à une même clique et à contrario de ce que proposait Bharghavan, ces flux ne sont pas tous identiquement dans la même situation et doivent avoir un paramètre CW différent. Il est donc capital de mettre au point un algorithme performant pour décider de sa valeur.
L'idée première de l'algorithme de Bensaou est que chaque noeud effectue un comptage des paquets (en terme de temps d'occupation du médium) qu'il envoie, correspondant à Wi et qu'il reçoit correspondant à Wo).
Une métrique est alors définie, l'index d'équité (FI, Fairness Index) égal à Wi/Wo×fo/fi, où fi est l'allocation faîte au noeud i et fo la somme de celles faîtes à ses voisins émetteurs (ensemble noté G).
Nous allons nous interesser au cas où l'allocation de tout un chacun est de 1. On a alors FI = Wi/Wo×|G|.
Bensaou propose alors que CW soit réajsuté de la manière suivante: chaque noeud double/divise de moitié sa fenêtre de contention selon si son index d'équité est supérieur/inférieur à 1.

Résultats
Dans leur rapport de recherche sont exposés les résultats obtenus avec le scénario décrit à la Fig 8, que nous nommerons A. Nous avons implémenté leur algorithme sous NS à la place de celui de 802.11 et, en effet, le débit des deux mobiles O & 2 est équitable bien qu'ils n'occupent à eux deux que 40% du médium. Cependant, en regardant l'évolution du paramètre CW au cours du temps, pour le noeud 2, nous nous sommes rendus compte que l'algorithme ne l'avait conduit qu'à stagner à la valeur maximale et de façon immédiate. Nous pouvons tirer quelques conclusions essentielles sur leur algorithme:

7.1  Un algorithme de résolution de fenêtre de contention

Nous n'avons cependant pas écarté l'idée d'espionner le médium. De plus l'avantage d'une telle solution est qu'elle s'intègre au protocole 802.11. Notre algorithme se trouve annexé à ce rapport. Nous allons à présent décrire ses deux phases, le comptage des paquets et l'ajustement de la fenêtre de contention.

Espionnage
le but est que chaque noeud détienne une estimation précise de Wo en bits/s. Afin d'effectuer un comptage réaliste il faut prendre en compte tous les noeuds qui sont en compétition. Nous allons nous baser sur la figure suivante (Fig. 17), qui remémore les zones (i) et (ii), pour dresser l'ensemble des données à récolter et comment les obtenir.


Figure 17 : Compétition entre les noeuds : aide au calcul de Wo


Ainsi le noeud b va communiquer dans son CTS son estimation de Wo. Celle-ci inclura autant le noeud a lui-même que d'autre noeud dont a a déja fait le compte. Ceci nous contraint à ce que les noeuds effectuent un comptage séparé pour chaque noeud l'environnant. Nos paquets CTS détiendront alors la liste L des noeuds estimés10 et la somme de ces estimations S. Afin d'évaluer son propre Wo, le noeud a n'a plus qu'à soustraire à S sa propre estimation des noeuds qu'il connaît (en correlation avec L), dont lui-même. La cardinalité de L lui permet enfin de connaître le nombre de noeuds avec lequel il est en compétition |G|.

Réajustement de CW
A partir des données de comptage, le calcul de FI intervient ainsi que celui de trois données importantes, qui sont l'évolution de FI, Wi et Wo depuis le dernier changement de la valeur de CW.
Celui-ci ne peut pas avoir lieu que sous trois conditions (On se place dans le cas où le noeud lèse ses voisins, ie FI>1, l'autre cas est symétrique). Ces conditions remplies, la valeur de CW est modifiée en la multipliant à la fois par l'évolution de FI et de celle de Wi. On assure ainsi que l'augmentation de la fenêtre de contention est équilibrée et prend en compte l'évolution propre du débit du noeud . De plus il n'est pas appliqué de facteur de multiplication supérieur à 2.

7.2  Résultats

Nous avons sélectionné ici deux de nos simulations. La première n'est autre que celle du scénario A. La seconde simule un scénario où le problème de l'EIFS se produit. Pour chacune les graphiques de l'évolution du débit, de CW et de FI au cours du temps sont donnés.

Scénario 1
le résultat quant au débit est très positif, puique non seulement l'équité est respéctée à contrario de ce que nous avions vu sous 802.11 (page 8) mais en plus les variations de débit subies par les noeuds sont faibles. L'index d'équité fait preuve de bonne stabilité.

         
Figure 18 : Scénario 1 -- évolution de FI au cours du temps


Quant à la variation de la fenêtre de contention, nous avons bien celle du noeud 2 plus haute que celle du noeud 0. Cependant elles sont anormalements hautes toutes les deux, ce qui se traduit par une perte du débit global (65% du médium occupé). Le problème vient du fait qu'au début de la simulation peu de données sont récoltées. Un paquet envoyé par l'un peut peser lourd dans l'évaluation de l'autre. Une fois cette période passée on acquiert une bonne stabilité du paramètre CW, mais bloqué à de trop hautes valeurs.

         
Figure 19 : Scénario 1 -- débit à gauche et évolution de CW à droite


Scénario 2
il s'agit des deux mêmes flux placés de telle sorte que tous soient à portée l'un de l'autre sauf les noeuds 0 et 3 qui se trouvent dans leur zone SR. Le noeud 0 souffre alors du problème large-EIFS lorsque le noeud 3 émet ses acquitements. Notons que sans ce problème ce scénario est traité équitablement par 802.11. Le graphique des débits montre à la fois ceux obtenus sous 802.11, où l'inégalité est manifeste, et ceux obtenus à l'aide de notre algorithme. Le débit total est encore amélioré par rapport à notre exemple précédent.

         
Figure 20 : Scénario 2 -- débits en regard de ceux expérimentés sous 802.11


La courbe la plus surprenante est celle de la fenêtre de contention. Pour les mêmes raison évoquées ci-dessus, les valeurs de CW commencent par augmenter fortement. Cependant elles gardent entre elles un écart significatif, que l'on peut donner comme la compensation de l'EIFS subit par le noeud 0 !
La courbe de l'index d'équité ne nous donne pas autant de satisfaction. Le fait que le noeud 2 évalue qu'il détient un débit double à celui de 0 provient du fait qu'il prend en compte les émissions de 1 dans son calcul de Wo, ce que ne peut pas faire le noeud 0 avec le noeud 3.

         
Figure 21 : Scénario 2 -- évolution de CW à gauche et de FI à droite


Ainsi l'algorithme que nous proposons c'est montré capable de résoudre le problème du noeud exposé ainsi que celui de l'EIFS.
Il reste que le débit global est parfois malmené, cependant moins qu'avec l'algorithme de Bensaou, qui d'ailleurs s'est révéllé inefficace dans le cas du deuxième scénario. Les protocoles MACAW et CB-FAIR ne résolvent pas non plus ces difficultés.
Il ne faut pas se voiler les yeux. il s'agit d'une approche prometteuse mais qui nécessite que soient réalisées des études combinatoires, ou encore de prouver formellement ses bienfaits. Il faut également trouver un moyen de contenir l'expansion de CW au prémices de l'algorithme.

8  Conclusion

Ainsi le problème de l'équité dans les réseaux ad-hoc au niveau de la couche MAC part du protocole 802.11, le standard actuel, qui ne donne que peu de garantie en la matière.
Si les chercheurs ont d'abord éclairé ce que devait être l'équité et les emplois de la fenêtre de contention et de la persistance, ils n'ont pas à travers leurs études théorique de la compétition au sein d'un réseau, capturé les problèmes réels que rencontre le partage du médium radio.
L'algorithme que nous avons proposé donne des résultats très satisfaisants tant pour les problèmes de noeuds exposés que ceux dus à l'EIFS. Par là même, il affirme l'utilité d'un algorithme réfléchi de résolution de fenêtre de contention.
Inéluctablement les chercheurs devront s'atteler à mieux modéliser l'ensemble des phénomènes engendrés par le médium radio. La complexité de celui-ci les entrainera certainement à se tourner vers d'autres solutions telles que les antennes intelligentes -- qui peuvent restreindre leur espace d'émission -- ou encore remmetre fondamentalement en cause les protocoles d'accès au médium actuels.

Références

[1]
Kaixin Xu, Mario Gerla, Sang Bae: How effective is the IEEE 802.11 RTS/CTS Handshake in Ad Hoc Networks ?, University of california
[2]
V. Bharghavan, A. Demers, S. Shenker, L. Zhang: MACAW: A Media Access Protocol for Wireless LANs, ACM SIGCOMM 1994
[3]
T. Ozugur, M. Naghshineh, P. Kermani, C. Olsen, B. Rezvani, J. Copeland: Balanced Media Access Methods for Wireless Networks, ACM MOBICOM 1998
[4]
Vaduvur Bharghavan, Thyagarajan Nandagopal, Tae-Eun Kim, Xia Gao: Achieving MAC Layer Fairness in Wireless packet Networks, Coordinated Science Laboratory, University of Illinois
[5]
Brahim Bensaou, Xiao Long Huang: On Max-min Fairness and Scheduling in Wireless Ad-Hoc networks, Hong-Kong University of Science and Technology
[6]
Bozidar Radunovic, Jean-Yves Le Boudec: Why Max-min Fairness Is Not Suitable For Multi-Hop Wireless Networks, Ecole Polytechnique Fédérale de Lausanne
[7]
Zhifei Li, Sukumar Nandi, Anil K. Gupta: Improving Fairness in IEEE 802.11 based MANETs using Enhanced Carrier Sensing, University of Singapore
[8]
Dominique Dhoutaut, Isabelle Guerin-Lassous: Impact of heavy traffic beyond communication range in multi-hops ad-hoc networks, Ecole Normale Supérieure de Lyon
[9]
Brahim Bensaou, Yu Wang: Fair Medium Access in 802.11 based Wireless Ad-Hoc Networks, Centre for Wireless Communications, National University of Singapore -- Mobihoc 2000
[10]
I. F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci: Wireless Sensor Networks: A Survey, Computer Networks, 38(4):393-422, March 2002.
[11]
Ad Hoc Mobile Wireless Networks, book Protocols and Systems de C-K Toh, éd Prentice Hall.
[12]
Aravind Velayutham, Haoli Wang: Solution to the Exposed Node problem of 802.11 in Wireless Ad-Hoc Networks, Departement of Computer Science, Iowa State University Ames

A  Curiosités

Cette première partie de l'appendice regroupe quelques problématiques et termes qui touchent aux réseaux ad-hoc. Ils ont été repérés dans le rapport à l'aide d'une étoile *. Ces notions ont été abordées lors de conférences ou de lectures solitaires. Ce sont donc des pistes à suivre pour s'immerger dans le monde des réseaux ad-hoc.

Réseaux Hybrides
(p.??) -- l'exemple qui nous intéresse, est celui d'un réseau ad-hoc relié à des stations de base, elles-mêmes reliées à l'internet filaire. Il s'agit d'élire au sein du réseau ad-hoc des clusters de noeuds avec en eux des leaders qui vont relayer l'ensemble des données aux stations de base. Il existe encore de nombreux problèmes comme par exemple, l'addressage IP au sein du réseau ad-hoc.

Sensor-Network
(p.??) -- ce sont des réseaux de capteurs à l'étude surtout dans le domaine militaire. L'idée est de déployer sur un espace étendu, un réseau dense de capteurs (chimiques, etc) et à l'aide par exemple d'avions survolant le réseau, de récolter les informations. Les deux problématiques essentielles sont la récolte des données au sein du réseau (les données sont d'abord routées vers certains noeuds ) et l'optimisation de l'énergie, donc du temps de vie de chaque capteur. Les noeuds responsables de l'envoi des données au moment de la collecte seront les premiers à ne plus avoir d'énergie. Il est par exemple proposé qu'au déploiement du réseau, les capteurs aient des autonomies différentes (cf le rapport de recherche [10]).

Protocoles de Routage
on distingue deux classes : les réactifs et les proactifs. Les premiers cherchent une route en inondant le réseau (i.e. tout noeud qui reçoit le message le retransmet) d'un message de recherche du destinataire. Un message retour est envoyé explicitant la route créée. La seconde approche utilise des tables de routage mais nécessite leur actualisation. Souvent, on définit dans le voisinage d'un noeud , l'ensemble des noeuds qui lui permettent d'accéder à son 2-voisinage afin d'optimiser les recherches et envois multiples de messages. En résumé, de beaux problèmes: cf [11] pour approfondir.

Parallèle RTS
(p.??) -- On voit que les deux noeuds marqués par Ñ (fig 9) pourraient en effet transmettre en parallèle au flux F si leurs cycles de transmission étaient en phase -- par exemple pour le flux noté à gauche, les émissions vont s'interférer aux émetteurs des flux, ce qui n'est pas gênant, mais pas les réceptions des CTSs/ACKs puisqu'elles interviendront au même moment. Pour apercevoir le mécanisme en détail, cf le protocole de Velayutham et al [12].

B  NetworkSimulator 2

NS est un simulateur de réseaux filaires et plus récemment de réseaux sans fils et ad-hoc. IL s'agit d'un projet open source, maintenu régulièrement, lancé par l'ISI (University of Southern California, USA).
Le code est écrit en C++ et le langage de script OTcl sert d'interface pour décrire les simulations.
NetworkSimulator est reconnu par la communauté scientifique et son fonctionnement a été validé tout au long de son développement. Cependant le code est conséquent et effectuer des modifications peut vite tourner au cauchemar. Nous avons mis en place plusieurs méthodes (activation des RTS/CTS, changement de la période EIFS, variation des zones SR/TR...), et des scripts permettant d'extraire des graphiques à partir des fichiers de trace.
Il est à noter qu'un logiciel de visualisation des simulations est fourni, nommé NAM. Le site internet de NS-2: http://www.isi.edu/nsnam/ns/

C  Algorithme

Le code ne peut réellement être imprimmé, car dissiminé dans de nombreux de fichiers. Il a donc été écrit sous forme algorithmique. Les commentaires sont en anglais, puisque il s'agit de code intégré à NetworkSimulator.
 
It is a distributed algorithm, which goal is to adjust the contention window of each node regarding to their send-rate and their received-rate. Written in C++ language it is designed to be included into ns2-simulator.

Nota: the algorithm works sending pieces of information in CTS about neighbourhood and accounting. It could be easily rewritten sending information in ACK.
Initialisation

  memory_time = 1;                   // seconds, period of data collect
  expunge_time = memory_time + 0.;   // seconds, period of silent-node recognition
  cycle = 10;                        // packets, number of packets send,received
                                     //   before recalling check_cw()   
  Fi = 1;                            // fairness index ( Wi over Wo ) 
  precis = 10e5;                     // a quotient to send Wo in integer type
                                     //   into CTS or ACK
  plus_ = 1;                         // meter of packets sends
  moins_ = 1;                        // meter of packets received
  C_ = 2;                            // percentage, error on Fi permitted 
        
every transmitions

  if (Fi < 1) increment(moins_);      // the fonction increment sets the variable to null
  if (Fi > 1) increment(plus_);       // when cycle is reached
                                             
  add(Wei, destination, packet_duration);
sending CTS

  add(CTS_packet, neighbourhood);     
  add(CTS_packet, sigma(Wo));
every receptions

  expunge(Wi, Wo);                       // a function to expunge the fifo data of packet
                                         //   accounting
  add_neighbour(source);                 // add the source in the neighbour list

  add(Wo, source, packet_duration);      // update packet accounting

  switch (packet_type) {
    case CTS: {
               if !(is_neighbour(destination)) add(Woo, source, RTS_duration);   
                             // the CTS packet is not for me and not for a node
                             //   that I heard => to exhib a three-flow transmission     
               recover(source_neighbourhood, source_Wo);         
              }
   case ACK:  if !(is_neighbour(destination)) add(Woo, source, DATA_duration);   
                             // ditto, the ACK packet is not for me and not for
                             //   node that I heard (field DATA size in in ACK frame)     
  }

compute (Wo_                 // with data received in CTSs, computes the global Wo
                             //   avoids conficts with personnal Wo, ie takes account
                             //   of my neighbourhood and the sending one's. That's
                             //   why we send the sum and the neighbourhood     
Fi = Wi / Wo;

if (Fi > (Fi +% C_)) {

  if ((plus_ == 0) && (Fi_evolution_i > 0.9)) 
    assign(cw_, cw_ * Wi_evolution * Fi_evolution);

  if (plus_ == 0) {
                   plus_ = 1;
                   remember(Fi, Wi);
                  }
} else
if (Fi > (Fi -% C_)) {

  if ((moins_ == 0) && (Fi_evolution_i < (1.1)) 
    assign(cw_, cw_ * Fi_evolution / Wo_evolution);

  if (moins_ == 0) {
                   moins_ = 1;
                   remember(Fi, Wo);
                  }
} else {

  if (moins_ == 0) moins_ = 1;
  if (plus_ == 0) plus_ = 1;
}

if (Fi < 1) increment(moins_);              
if (Fi > 1) increment(plus_);               

D  Equipe d'accueil et remerciements

Ces travaux ont été effetués au sein du laboratoire CITI (Centre d'Innovations en Télécommunications & Intégration de services), unité mixte de recherche (Inria, Insa Lyon) qui se situe sur le campus de l'Insa de Lyon.
Le CITI ne borne pas sa recherche sur les réseaux ad-hoc à l'étude la couche MAC. Bien au contraire, puisque les thèmes abordés vont du traitement du signal jusqu'aux problèmes de routage.
Ce stage s'est effectué sous la direction d'Isabelle Guérin-Lassous, chargée de recherche Inria et de ses deux étudiants en thèse, Dominique Dhoutaut et Claude Chaudet. Leurs dernières recherches portent sur l'allocation équitable de bande passante, des protocoles intégrant de la qualité de service pour les réseaux ad-hoc et les faiblesses du protocole MAC de 802.11.
C'est dans cette dernière thématique qu'ils souhaitaient aborder les problèmes d'équité. Ma contribution fournit à l'équipe un point de vue global sur le problème et des pistes de recherche. Elle met surtout en lumière des problèmes méconnus. Enfin le code implémenté sous NS-2 permetra de simuler rapidement un algorithme de gestion de fenêtre de contention plus performant.
Je les remercie vivement pour l'attention qu'ils m'ont portée et leur accueil chaleureux.
             

 
Serveur du CITI: http://citi.insa-lyon.fr




1
Nous utiliserons abusivement ce terme anglais
2
Les RTS/CTS ne sont pas activés en-deçà d'une certaine taille du paquet de données.
3
Les noeuds gardent trace des différentes valeurs de Duration dans le NAV (Network Allocation Vector)
4
Il est clair que les collisions sont reportées aux RTS et là encore l'algorithme BEB est appliqué. Les paquets RTS étant de très petite taille leur réémission est moins coûteuse que celle des paquets de données: cf les études de Xu et al. [1]
5
Le signal de c perçu par a est bien sûr plus faible que celui perçu de b mais suffisant pour déteriorer le paquet d'acquitement.Certains définissent des cas -- rares -- où selon les distances le noeud est capable d'isoler le signal de b.
6
Dans toutes les simulations qui ont été faites les noeuds travaillent au débit maximal. Les simulations ont été réalisées sous le simulateur NS-2 (cf Appendice).
7
On ne voit pas vraiment comment un noeud pourrait construire le graphe G lorsque des liens SR sépare des flux en compétition. Par exemple les flux 1 & 2 de la Fig. 10
8
On ne parlera plus d'inégalité mais d'iniquité !
9
Il est alors interessant d'utiliser un protocole de routage qui recherche des routes entre les mobiles avant d'effectuer l'envoi des paquets. Dans ce scénario, le noeud central n'aura pas le temps de les construire, empêchant tout envoi de paquet
10
Celle-ci peut-être conséquente. Il serait souhaitable qu'elle ne soit envoyée qu'une fois, et que par la suite seules les entrées/sorties de cette liste soient intégrées au paquet CTS.

Ce document a été traduit de LATEX par HEVEA.