Autour de la réservation de bande passante dans les réseaux ad hoc

Equité de l’accès au  médium : étude d’un cas pathologique

Le protocole IEEE 802.11 est ses déclinaisons ont été con¸cus à l’origine afin de constituer des réseaux locaux sans fil administrés par une ou plusieurs stations de base. Grˆace à son succès commercial, il est très rapidement devenu incontournable dans le monde des réseaux ad hoc. L’écrasante majorité des publications scientifiques dans ce domaine suppose maintenant que le protocole d’accès au médium sousjacent est celui de la norme IEEE 802.11 ou du moins qu’il a le même comportement. En conséquence, les performances de ce protocole ont été largement étudiées. De très nombreuses simulations ont été réalisées au moyen de simulateurs reconnus, quelques expérimentations ont été menées et le comportement de ce protocole a été modélisé de différentes manières. La plupart des études cherchent à évaluer les performances brutes de ce protocole, telles que le débit maximal pouvant être atteint, le délai moyen, la stabilité des liens, l’influence du nombre de mobiles en concurrence dans le réseau sur ces paramètres ou encore l’impact de perturbations sur les performances du réseau. Si le comportement de ces réseaux est maintenant prévisible dans de nombreux cas, il est possible de dénombrer quelques cas pathologiques mettant en défaut ce protocole. Dans ce chapitre, nous nous intéresserons à l’un de ces scénarios dans lequel un problème de performance lié à un déséquilibre dans la topologie du réseau affecte l’un des émetteurs. Nous avons choisi d’adopter une approche théorique afin d’évaluer les performances de cette configuration. En effet, lors d’expérimentations, il est difficile de maˆıtriser tous les paramètres de l’environnement et les simulations fournissent parfois des résultats erronés. L’approche consistant à modéliser ce scénario nous a donc paru être la plus à même de refléter précisément le comportement du protocole d’accès au médium tel qu’il est décrit dans le standard tout en s’affranchissant des problèmes liés à la propagation radio dépendants de la couche physique utilisée. Ce chapitre présente tout d’abord en section 1.2 quelques éléments de propagation radio, ainsi que le protocole d’accès au médium commun aux différentes révisions de la norme IEEE 802.11 en section 1.3 . Un état de l’art des différentes modélisations du comportement de ce protocole est présenté en section 1.4. Le scénario étudié est ensuite décrit et modélisé sous forme de chaˆıne de Markov en temps discret en section 1.5. Les performances ainsi déterminées sont alors étudiées et comparées à des résultats obtenus par simulation et par expérimentation.

Le protocole IEEE 802.11

Le protocole 802.11 de l’Institute of Electrical and Electronics Engineers (IEEE) [IEE97], parfois nommé Wi-Fi, définit plusieurs couches physiques et une couche d’accès au médium pour les réseaux locaux sans fil (Wireless Local Area Networks — WLAN). Si, dans sa première version définie en 1997, des transmissions infrarouges étaient envisagées, les versions les plus récentes du standard telles que IEEE 802.11b [IEE99a], IEEE 802.11g [IEE03] ou encore IEEE 802.11a [IEE99b] sur la base desquelles sont construites l’essentiel des cartes d’interface commercialisées, s’adressent principalement à des transmissions radiofréquences. Les différentes couches physiques définissent différents codages permettant d’assurer une transmission sans fil fiable et un multiplexage de plusieurs canaux de transmission. Elles rendent possible des transmissions à des puissances limitées dans les bandes de fréquences libres, en particulier la bande de fréquences dédiée aux mondes industriel, scientifique et médical (ISM) située aux alentours de 2, 4 GHz, 13 dans laquelle à la fois les Etats-Unis, l’Europe et le Japon autorisent des transmissions sans licence. La ´ première déclinaison de cette norme définissait, en sus des transmissions infrarouges, les modalités de transmission dans cette bande de fréquences allant de 2 400 MHz à 2 495 MHz. Elle proposait d’utiliser différentes techniques d’étalement de spectre. L’étalement par saut de fréquences (Frequency Hopping Spread Spectrum — FHSS) utilisé par la norme IEEE 802.11 divise la bande de fréquence en 75 canaux d’une largeur de 1 MHz. Une allocation aléatoire d’une séquence de fréquences permet de multiplexer efficacement plusieurs transmissions et offre une bonne résistance aux interférences en bande, c’est-à-dire aux interférences causées par des signaux émis dans la même bande de fréquences que le signal utile. En effet, un récepteur FHSS large bande peut être considéré comme un ensemble de récepteurs en bande étroite changeant de fréquences régulièrement et de fa¸con aléatoire ou pseudo-aléatoire. La probabilité pour que deux signaux utilisent la même bande étroite simultanément est donc réduite. Cependant, le débit résultant est relativement faible et ce mode de transmission n’est utilisé que pour des transmissions à 1 Mbit/s ou 2 Mbit/s. L’étalement de spectre par séquence directe (Direct Sequence Spread Spectrum — DSSS) transmet chaque bit en utilisant onze changements d’état du signal. L’émission de chaque bit correspond à la transmission d’une séquence appelée séquence de Barker composée de onze chips. Cette technique autorise des transmissions à une vitesse de 1 M baud permettant, elle aussi d’obtenir un débit de 1 M bit/s en utilisant une modulation DBPSK (Differential Binary Phase Shift Keying) ainsi qu’un débit de 2 M bit/s en utilisant une modulation DQPSK (Differential Quadrature Phase Shift Keying). La bande de fréquences est alors divisée en 14 canaux d’une largeur de 22 MHz se recouvrant partiellement. Ce type de techniques permet en outre d’aboutir à des durées d’initialisation du système plus rapides que les systèmes FHSS. L’étalement de spectre à haut débit par séquence directe (High Rate Direct Sequence Spread Spectrum — HR-DSSS) permet, par l’ajout d’un encodage de type CCK (Complementary Code Keying), d’atteindre des débits de 11 M bit/s et est à la base de la déclinaison la plus utilisée à ce jour du standard, IEEE 802.11b. Enfin, le multiplexage orthogonal en répartition de fréquences (Orthogonal Frequency Division Multiplexing — OFDM) utilise des techniques proches de celles qui sont utilisées par l’ADSL dans la bande de fréquences allant de 5150 MHz à 5350 MHz et permet d’atteindre des débits physiques de 54 M bit/s. Cette technique, utilisée dans IEEE 802.11a et compatible avec le standard européen Hiperlan/2 [ETS00a, ETS00d, ETS00e, ETS00b, ETS00c, ETS00f, ETS00g], présente quelques propriétés intéressantes, comme une bonne immunité aux problèmes d’évanouissement multitrajets, c’est-à-dire aux problèmes liés aux interférences causées par plusieurs instances du même signal ayant suivi des chemins de longueur différentes et arrivant déphasés au niveau du récepteur. Ces multiples signaux se combinent alors, pouvant s’annuler s’ils sont en opposition de phase. Le principe de HR-DSSS est robuste face à ce type de perturbations, mais limite la portée de transmission. La plupart des protocoles pour réseaux ad hoc n’utilisent cependant pas les possibilités de multiplexage offertes par ces techniques. Affecter un unique canal à un réseau ad hoc particulier permet de faire coexister plusieurs réseaux ad hoc indépendants dans la même zone géographique. Un changement de canal au sein d’un même réseau poserait en outre des problèmes liés à la dynamicité du réseau. Au-dessus de ces différentes couches physiques, la norme définit un unique protocole d’accès au médium, pouvant fonctionner dans deux modes distincts, afin de gérer les accès concurrents à un même médium partagé. Ce protocole fait partie de la famille des protocoles de gestion des accès multiples par détection de porteuse avec évitement de collisions (Carrier Sense Multiple Access with Collision Avoidance — CSMA/CA) [KT75]. Il associe un mécanisme de détection de porteuse avant transmission à un mécanisme d’attente aléatoire permettant de limiter le nombre et l’impact des collisions. Quelle que soit la technique de transmission mise en œuvre, les signaux émis sont soumis aux lois de la propagation radio. Que ces problèmes apparaissent sur l’unique canal utilisé par le réseau ou sur un canal particulier dédié à la signalisation, ils n’en demeurent pas moins présents et peuvent affecter les performances du réseau, ne serait-ce que de fa¸con transitoire. Afin de définir le niveau de qualité de service pouvant être raisonnablement offert dans ces réseaux, il est indispensable de connaˆıtre précisément le comportement des couches sous-jacentes. 1.2 Elements de propagation radio ´ La transmission par ondes infrarouges étant devenue anecdotique pour le standard IEEE 802.11, L’essentiel des émissions de trames au moyen de tels matériels a lieu dans des bandes de fréquences de 14 type micro-ondes. Au niveau physique, un terminal souhaitant transmettre une trame émet sur le canal radio un signal à une certaine puissance dont la limite est fixée légalement et est dépendante de chaque pays. Le tableau 1.1 résume les puissances autorisées en France (à l’exception de certains départements d’outremer) en juillet 2004. Bande de fréquences en extérieur en intérieur 2 400 MHz – 2 454 MHz 100 mW 100 mW 2 454 MHz – 2 483,5 MHz 10 mW 100 mW 5 150 MHz – 5 250 MHz interdit 200 mW 5 250 MHz – 5 350 MHz interdit 200 mW1 ou 100 mW2 5 470 MHz – 5 725 MHz interdit interdit Tab. 1.1 – Puissances isotropes rayonnées équivalentes (PIRE) autorisées en France (source : Autorité de Régulation des Télécommunications) Le signal se propage alors dans l’air et est atténué et modifié par divers phénomènes avant de parvenir à chaque station dans une zone géographique. La taille et la forme de cette zone de réception est définie par les antennes de l’émetteur et des récepteurs potentiels. La figure 1.1(a) représente en coordonnées polaires le résultat d’une mesure réalisée par Guillaume Villemaud dans la chambre anécho¨ıque1 de l’université de Limoges de la somme des puissances re¸cue en polarisations horizontale et verticale en faisant varier la position du récepteur sur un cercle à une distance constante de l’émetteur. Cette mesure a été réalisée en utilisant une carte Wi-Fi standard installée dans un ordinateur portable. La puissance mesurée est loin d’être constante et la zone de couverture est loin d’être circulaire. A partir de ces mesures, ` il est possible de déduire une mesure du gain en émission de l’antenne d’un récepteur Wi-Fi standard et donc d’obtenir l’allure de la zone de couverture. Cette allure est représentée en figure 1.1(b) dans le cas d’un modèle de propagation des signaux radio simple (espace libre). Cette mesure n’est valable que pour un ordinateur donné équipé d’une carte donnée et dans un environnement particulier. Toutefois, on peut remarquer que la zone de couverture est nettement plus étendue dans la direction de l’antenne que dans les autres, confirmant ainsi les résultats d’expérimentations obtenus par Dominique Dhoutaut et présentés dans [Dho02]. distance de couverture (m) distance de couverture (m) (b) Distance atteignable pour une puissance donnée (modèle de propagation de type espace libre) Fig. 1.1 – Caractéristiques d’une antenne de carte Wi-Fi standard (Orinoco / WaveLan) 1Avec mécanisme de contrˆole de puissance et sélection dynamique de fréquences 2Sans mécanisme de contrˆole de puissance mais avec sélection dynamique de fréquences 1Une chambre anécho¨ıque est une pièce dont les murs absorbent les ondes radio, empêchant ainsi toute réflexion et permettant ainsi de mesurer les caractéristiques d’un signal non-perturbé. 15 La qualité de réception du signal radio va directement affecter le taux d’erreurs bit. Si le nombre d’erreurs est suffisamment faible pour autoriser la correction des erreurs, le décodage des informations est possible et les données sont transmises avec succès. La spécification des cartes d’interface Avaya indique qu’un taux d’erreur-bit inférieur à 10−5 est nécessaire au décodage des informations. Divers phénomènes peuvent affecter la qualité du signal transmis. En premier lieu, les signaux radio subissent un affaiblissement fonction de la distance qu’ils parcourent et des milieux qu’ils traversent. La propagation radio est, dans le cas général, un phénomène complexe. En espace libre, c’est-à-dire sans obstacles tels que des bˆatiments, on peut considérer qu’un signal émis avec une puissance Pt (en Watts) sera re¸cu à une distance d (en mètres) avec une puissance Pr (en Watts) donnée par l’équation de Friis en espace libre : Pr(d) = Gt · Gr · λ 2 L · (4 · π · d) 2 · Pt, o`u Gt et Gr sont les gains des antennes émettrice et réceptrice, L le facteur de perte hors propagation dans le système et λ est la longueur d’onde (en mètres) du signal. La puissance du signal décroˆıt en fonction du carré de la distance. Ce modèle est quelque peu simpliste et ne rend pas vraiment compte de l’affaiblissement pouvant survenir dans un environnement urbain ou à l’intérieur de bˆatiments. En environnement réel, un signal se propageant dans toutes les directions de l’espace va se réfléchir contre différents obstacles, comme des bˆatiments ou tout simplement le sol. Ces différentes instances du signal parcourront des distances différentes avant d’atteindre la destination, et pourront ainsi arriver déphasées, et atténuer la qualité du signal initial. Considérer une simple réflexion sur le sol permet d’obtenir une bonne approximation à grande distance. Cette approximation consiste à considérer que l’on se trouve en espace libre jusqu’à une distance de 20 · ht · hr/λ, hr et ht représentant les hauteurs des antennes réceptrice et émettrice. Au-delà de cette distance, la puissance du signal s’exprime par : Pr = Gt · Gr · h 2 t · h 2 r d 4 · Pt. Cette formulation n’est toujours qu’une approximation des conditions réelles de propagation radio et ne rend compte que d’une réflexion sur le sol. Certains phénomènes comme la diffraction au passage des ouvertures, l’absorption par différents matériaux ou les réflexions contre les différents objets de l’environnement sont dépendants du scénario d’utilisation et ne peuvent être généralisés. La propagation en environnement complexe est communément approchée en considérant un affaiblissement en fonction de l’inverse de la distance à la puissance α. α est une constante dépendant de l’environnement. Elle vaut 2 en espace libre, entre 2 et 5 en environnement urbain et varie de 1, 6 à 6 en intérieur. Le signal, en plus de l’affaiblissement dˆu au milieu, est aussi perturbé par différentes sources de bruit. Dans une bande de fréquence de largeur B Hz, à une température de T K, on considère qu’à cause de l’agitation aléatoire des électrons dans les circuits du récepteur, un bruit thermique blanc de puissance PN = k · T · B perturbe tout signal, k étant la constante de Boltzmann (k = 1, 379 · 10−23 W · Hz−1 · K−1 ). Cependant, les principales perturbations pouvant altérer un signal sont dues aux autres signaux émis dans la même bande de fréquence. Les signaux émis simultanément par plusieurs stations vont s’entremêler et devenir difficiles voire impossibles à décoder. Une analogie commune permettant de conceptualiser les transmissions radio est celle de la parole. Une parole est analogue à un signal radio ; son émission est le plus souvent diffuse et atteint tous les correspondants dans un certain voisinage. Si plusieurs interlocuteurs parlent simultanément, les mots s’entremêlent et la conversation est difficile voire impossible à suivre. Le critère sur le signal permettant un décodage correct des informations doit donc prendre en compte non seulement la qualité du signal re¸cu mais aussi les perturbations dues aux signaux interférents. Il s’exprime par le rapport entre la puissance du signal re¸cu et la puissance du bruit, ce bruit prenant en compte l’ensemble des perturbations : SNR = PR PN + PPautressignaux . Les cartes d’interface basées sur la norme IEEE 802.11 permettent actuellement de décoder des signaux dont le rapport signal sur bruit dépasse un certain seuil, fonction de la modulation utilisée. Les données fournies par le constructeur des cartes Orinoco indiquent qu’un rapport signal sur bruit supérieur à 16 dB est nécessaire pour décoder des signaux à 11 M bit/s. Ce seuil vaut 11 dB pour un 16 débit de 5, 5 M bit/s, 7 dB pour un débit de 2 M bit/s et 4 dB pour un débit de 1 M bit/s. Cette valeur nommée seuil du rapport signal sur bruit, qui sera notée par la suite SNRthreshold, limite la réutilisation spatiale, c’est-à-dire la possibilité d’effectuer deux transmissions simultanées sans qu’elles n’interfèrent, c’est-à-dire sans collision. Si l’on néglige le bruit thermique et si l’on se place en espace libre, ceci se traduit par l’impossibilité pour un récepteur situé à une distance d d’un émetteur de décoder le signal si un autre terminal émet un signal à la même puissance dans un rayon de √ SNRthreshold · d, soit jusqu’à plus du triple de la distance entre l’émetteur et le récepteur dans notre cas. Dans un modèle d’affaiblissement en 1/dα, ce rayon devient √α SNRthreshold ·

Lorsque plusieurs sources d’interférences s’ajoutent, cette distance est évidemment accru

A l’image des réseaux filaires, les collisions entre plusieurs trames rendent impossible le décodage ` des informations. Toutefois, la propagation des ondes hertziennes dans l’air est sensiblement différente de la propagation d’une onde électrique dans un cˆable ou d’une onde lumineuse dans une fibre optique. En conséquence les mécanismes permettant d’assurer une transmission relativement fiable au niveau liaison doivent être adaptés. En particulier, la couche d’accès au médium définie par le standard IEEE 802.11, bien que basée sur les principes d’Ethernet, diffère sensiblement des protocoles d’accès au médium filaires. 

Description du protocole d’accès au médium

La norme IEEE 802.11 définit deux modes d’accès au médium adaptés aux transmissions radio : le mode centralisé (Point Coordination Function — PCF) peut être utilisé lorsque les communications sont gérées par une station de base fixe et le mode distribué (Distributed Coordination Function — DCF) est utilisé à la fois pour les communications via une station de base et pour les communications directes de mobile à mobile. C’est ce dernier mode qui sera utilisé dans le cas des réseaux ad hoc. Les collisions, dans un environnement tel que celui décrit à la section précédente, conduisent le plus souvent à la perte des deux trames incriminées. Il semble donc peu judicieux de laisser les différents terminaux émettre comme bon leur semble. L’évaluation du protocole d’accès au médium ALOHA [Abr70], dont le principe est de laisser les terminaux émettre dès qu’ils ont une trame à transmettre, a en effet montré qu’avec des trafics suivant une loi de Poisson de paramètre λ, le débit utile résultant était égal à λe−2λ . Les travaux de Kleinrock et Tobagi [TK75a] montrent que ce débit, fonction directe de la fréquence de génération des trames n’excède pas 18 % de la capacité du médium. Laisser les terminaux transmettre à leur guise ne conduit donc pas à une utilisation de la bande passante efficace. Plusieurs améliorations sont envisageables afin d’utiliser au mieux la bande passante en réduisant les collisions. Tout d’abord, il est possible de ne pas émettre si le médium est occupé. Les terminaux attendent alors que le canal se libère avant d’émettre un signal. Ce principe simple constitue la base des protocoles dits à détection de porteuse (Carrier Sense Multiple Access — CSMA). Cette famille regroupe entre autres des protocoles tels qu’Ethernet [MB76] ou le protocole IEEE 802.3 [IEE85] dont l’efficacité peut atteindre 95 %.

Principes de base

Ethernet ajoute à ce mécanisme un procédé de détection de collision. Il peut être classé parmi les protocoles de type CSMA/CD (Carrier Sense Multiple Access with Collision Detection). Chaque station, au fur et à mesure de la transmission d’une trame, compare le signal présent sur le médium à celui qu’elle émet. Une différence indique alors une collision et la transmission est arrêtée, libérant le canal pour d’autres transmissions. Ce procédé ne peut cependant pas être appliqué dans un contexte radio. En effet, le fort affaiblissement des signaux radio rend impossible la détection d’un signal perturbateur par l’émetteur. La puissance per¸cue d’un tel signal serait en effet beaucoup trop faible en comparaison de la puissance du signal émis. De surcroˆıt, les collisions ont un impact à la réception et non à l’émission. La présence d’un signal interférant au niveau de l’émetteur ne fournit aucune indication sur le niveau de bruit au niveau du récepteur. La DCF du protocole IEEE 802.11 met donc en œuvre un certain nombre de mécanismes visant non pas à détecter les collisions mais à les éviter. Elle fait à ce titre partie de la famille CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance). Compte tenu de l’impossibilité pour les émetteurs de mesurer la qualité du signal au niveau du récepteur, chaque récepteur doit acquitter toute trame qui lui est explicitement destinée et cet acquittement constituera la seule indication sur le succès de la transmission dont disposera l’émetteur. Ce  mode de fonctionnement est très proche de celui du protocole d’accès au médium MACAW [BDSZ94], dont la DCF de la norme IEEE 802.11 s’inspire très largement. Lorsqu’un terminal re¸coit une trame de données, il procède à une détection d’erreurs au moyen d’un CRC standard IEEE sur 32 bits. Si la trame ne contient pas d’erreur, il renvoie à l’émetteur un acquittement. L’intervalle de temps séparant la fin de la réception de la trame de données et le début de l’émission de l’acquittement est égal à une valeur constante SIF S (Short Inter Frame Spacing). Il n’est évidemment pas possible d’acquitter les trames diffusées (broadcast), du fait de l’impossibilité pour l’émetteur de recevoir plusieurs acquittements simultanés. Aussi n’y a-t-il aucune garantie sur la bonne réception de ce type de trames. Lorsqu’un terminal désire transmettre une trame, il s’assurera tout d’abord que le médium est libre durant un temps constant DIF S (DCF Inter Frame Spacing) plus long que SIF S afin de donner une priorité absolue aux acquittements. Le cas échéant, il effectue la transmission, puis attend l’acquittement correspondant de la part du récepteur. L’absence de réception de cet acquittement provoque la retransmission de la trame et ce processus sera répété jusqu’au succès de l’opération ou jusqu’à atteindre le nombre maximal de retransmissions autorisé. Dans ce dernier cas, la trame est détruite. La détection de porteuse permet d’éviter certains cas de figure dans lesquels deux émissions simultanées provoqueraient une collision au niveau d’un récepteur. Cependant, il est impossible de distinguer par ce biais les situations dans lesquelles deux émissions simultanées ne provoqueraient pas de collision, à l’image du scénario représenté en figure 1.2. Dans cette configuration, les émetteurs B et C se trouvent en zone de détection de porteuse, c’est-à-dire que les émissions de l’un bloque le mécanisme de détection de porteuse de l’autre. Cependant, les deux récepteurs sont suffisamment éloignés des émetteurs perturbateurs pour autoriser la simultanéité des deux communications. Ce problème, connu comme le problème de la station exposée conduit à une sous-utilisation de la capacité du canal radio.