Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
Les protocoles MAC mono-canal proposés pour le standard IEEE 802.11
Le protocole MAC 802.11 prend en charge deux modes de fonctionnement, à savoir la fonction de coordination distribuée (Distributed Coordination Function DCF) et la fonction de coordination par point (Point Coordination Function, PCF). Le mode DCF offre un service best-effort c’est-à-dire sans priorité et sans garantie, tandis que le mode PCF a été conçu pour prendre en charge le trafic en temps réel dans des configurations de réseau sans fil basé sur une infrastructure [23] [24]. Le mode DCF n’utilise aucun type de contrôle centralisé, toutes les stations sont autorisées à concurrencer pour le support partagé simultanément.
Le protocole IEEE 802.11 DCF : le mode DCF est essentiellement basé sur le principe du CSMA/CA. Pour réduire la probabilité de collisions, la DCF applique un mécanisme d’évitement des collisions (CA Collision Avoidance), où les stations effectuent une procédure de temporisation (backoff) avant d’engager une transmission. Après avoir détecté le support inactif pendant une durée minimale appelé espace inter trame DCF (DIFS Interframe), les stations continuent à détecter le support pour un temps aléatoire supplémentaire appelé le temps de temporisation (backoff). Une station initie sa transmission que si le medium reste inactif pendant ce temps aléatoire supplémentaire. La durée de ce temps aléatoire est déterminée individuellement par chaque station. Une nouvelle valeur aléatoire indépendante est choisie pour chaque nouvelle tentative de transmission. Il en résulte aucun mécanisme pour différencier entre les stations et leur trafic, et donc pas de support de la QoS (Quality of service) dans le DCF. Si le médium est très occupé en raison d’interférences ou d’autres transmissions alors qu’une station décompte son compteur d’attente, la station s’arrête de décompter et diffère l’accès au support jusqu’à ce que le medium devienne inactif pendant un nouveau DIFS. Cela se produit, par exemple, lorsque la durée de temporisation aléatoire d’une station est plus longue que celle d’au moins une autre station. Les stations qui différent leur accès au support parce qu’elles ont détecté que le médium était occupé ne sélectionnent pas une nouvelle durée de temporisation aléatoire, mais continuent à décompter les slots de temps de la temporisation différée après détection à nouveau du support à l’état inactif. La figure 1 illustre le temps de l’accès au canal en mode DCF.
Chaque nœud sélectionne une temporisation aléatoire uniformément distribué dans [0, CW], où CW est la taille actuelle de la fenêtre de contention (Contention Window CW). Il diminue le compteur de temporisation d’une unité pour chaque slot de temps libre (d’inactivité du canal). La transmission commence quand le timer de temporisation atteint zéro. Lorsqu’il y a des collisions, lors de la transmission, ou en cas d’échec de la transmission, le nœud double la valeur de CW jusqu’à ce qu’elle atteigne la valeur maximale CWmax. Par la suite, le nœud commence le processus de temporisation à nouveau, et retransmet le paquet lorsque la temporisation est terminée. Si la limite maximale d’échec de transmission est atteinte, la retransmission doit s’arrêter, CW est remis à la valeur initiale CWmin, et le paquet sera rejeté.
Comme le mode DCF n’utilise aucun type de contrôle centralisé, toutes les stations sont autorisées à concurrencer simultanément pour le support partagé. Par contre, la méthode d’accès PCF dont le fonctionnement est contrôlée par un équipement central (polling master), le coordinateur, qui scrute toutes les stations et donne les droits d’émettre, par un processus appelé « polling » [24]. La fonction PCF est implémentée au-dessus de la DCF. Etant donné que, d’une part le coordinateur est à portée de tous les autres nœuds et, d’autre part, utilise l’espace PIFS (PCF IFS), plus court que l’espace DIFS, tout autre trafic asynchrone est exclu une fois qu’il obtient le média lors du polling et de la réception des réponses.
Il faut aussi signaler que le protocole MAC 802.11 ne prend pas en charge le concept de la différenciation des trames avec des priorités différentes. Ainsi donc la DCF fournit un accès au canal avec des probabilités égales à toutes les stations qui concurrencent pour l’accès au canal de manière distribuée [24].
L’amendement de la norme IEEE 802.11e introduit la différenciation de trafic et des services sur la couche MAC afin qu’il puisse fournir des flux multimédias avec le respect de leurs exigences de qualité de service et en temps réel en plus de trafic best effort [25].
Ainsi donc, la EDCA (Enhanced Distributed Channel Access) autrement appelé EDCF (Enhanced DCF) a été proposée pour améliorer la fonction DCF en introduisant la priorisation du trafic [25]. L’IEEE 802.11 EDCA fournit un accès au médium basé sur la contention et distribué qui peut prendre en charge la différenciation de service entre les classes de trafic AC (Access Categories) : AC_BK (background traffic), AC_BE (best effort traffic), AC_VI (video traffic) et AC_VO (voice traffic), dont chacune a sa propre file d’attente de transmission et ses propres paramètres d’accès au canal tels que :
ü AIFSN (Arbitrary interframe space number) : utilisé à la place de DIFS, Chaque AC (Access Categories) commence sa procédure de backoff quand le canal est inactif pendant une période de AIFSN au lieu de DIFS (Le SIFSN est au moins égal à DIFS). Ainsi donc le trafic le moins prioritaire utilisera la plus grande valeur de AIFSN.
ü Contention Window CW (CWmin et CWmax): Un nombre aléatoire est tiré à partir de cet intervalle pour le mécanisme de backoff. Chaque catégorie de trafic concurrence l’accès au canal avec différents paramètre de CWmin et CWmax, ainsi la valeur minimale CWmin est utilisée par les classes de trafics de plus haute priorité.
ü Transmission opportunity (TXOP) limit: La durée maximale pendant laquelle un nœud peut transmettre un maximum de flux après avoir obtenu l’accès au canal.
La valeur minimale de CWmin pour chaque AC (Access Categories) peuvent être différentes les unes des autres. L’attribution de valeurs plus petites de CWmin aux classes de haute priorité peut assurer que les classes de haute priorité obtiennent plus TXOPs que ceux de faible priorité. L’idée de CWmin est similaire pour CWmax.
En conclusion, même si l’objectif primordial du protocole est d’assurer la qualité de service dans le réseau, puisque l’accès au medium du protocole EDCA est basé sur la contention, il faut donc qu’il y’ait au préalable un rendez-vous entre les nœuds avant toute transmission ; dès que le réseau est saturé, la QoS sera rapidement remise en cause et surtout quand il s’agit du multi-saut. Peut-être en exploitant tous les canaux dédiés à la norme 802.11 et utilisant un protocole d’accès multi-canal adéquat, que la QoS sera assuré au minimum.
L’accès multi-canal mono interface
Le protocole du canal de contrôle dédié
Le canal de contrôle dédié [1] [3] [4] [12] [38] [39] est un protocole de rendez-vous unique, chaque nœud est muni d’une interface de contrôle et d’une interface de données. L’interface de contrôle est fixée de façon permanente sur un canal commun (appelé canal de contrôle) pour l’échange des trames de contrôle. L’interface de données peut basculer entre les canaux restants (appelés canaux de données) pour la transmission de données. L’idée principale du protocole est d’isoler les trames de contrôle de celles de données en affectant un canal fixe pour échanger des trames de contrôle RTS et CTS, et pour éviter ainsi les interférences entre les trames de contrôle et les paquets de données. Plusieurs travaux considèrent le protocole multi-interface, alors qu’El Fatni et al. [12] le considèrent parmi les protocoles mono-interfaces multi-canal.
Le principe de fonctionnement du protocole est le suivant : lorsqu’une paire de nœuds A et B veut échanger des données, l’émetteur A envoie une trame RTS qui contient une liste des canaux libres dans sa zone de portée sur le canal de contrôle. Le récepteur B choisit un canal libre commun parmi les canaux de la liste envoyés par A en répondant par une trame CTS, qui comprend le canal sélectionné pour le transfert de données. A et B commutent alors leurs interfaces sur le canal sélectionné et commencent à transmettre des données. Les trames RTS et CTS incluent également le NAV(Network Allocation Vector) pour informer les voisins de A et B de la durée pendant laquelle le canal sera occupé. Dans [12], les auteurs utilisent une troisième trame de contrôle supplémentaire RES (Reservation) aux deux trames RTS et CTS pour confirmer la réservation du canal. La figure 4 explique le principe de canal de contrôle dédié. L’intérêt de ce protocole est qu’il simplifie la diffusion d’une trame, puisqu’il y a une interface radio fixée de manière permanente sur le canal de contrôle, ainsi la diffusion (broadcast) sera réalisée sur ce canal. L’inconvénient de ce protocole est qu’il n’est pas une solution du problème majeur multi-canal du terminal caché et de la surdité. Comme le canal de contrôle est unique, si plusieurs nœuds tentent de conclure des accords pour transmettre des données, le canal de contrôle deviendra un goulot d’étranglement. Ainsi pendant la période des transmission des données les nœuds n’ont aucune information concernant les rendez-vous établis sur le canal de contrôle et, ainsi donc ignorent les informations sur les canaux de données réservés pendant cette période. Ce manque d’information conduisant aux problèmes suivants: 1) le problème multi-canal de surdité où un nœud cherche à établir un rendez-vous avec un autre nœud se trouvant sur autre canal en émission ou en réception des données. 2) le problème multi-canal du nœud caché survient dans le cas où deux établissent un rendez-vous et commutent sur un canal qui est déjà occupé par un autre pair de nœud. Nous remarquons aussi que pendant le transfert des données, le canal de contrôle n’est pas utilisé, ceci prouve que, l’approche du canal de contrôle dédié gaspille aussi de la bande passante. 3)
dans le cas multi-saut, il faudrait trouver une solution pour diffuser à plus que 1 saut, les trames RTS, CTS (et RES éventuellement) aux nœuds qui peuvent gêner les échanges.
Principe de fonctionnement du protocole de saut indépendant
Dans SSCH chaque nœud adopte une ou plusieurs paires (canal, germe) d’initialisation (4 au maximum), chaque nœud saute entre les différents canaux disponibles en utilisant ses propres séquences de saut de canal. Les séquences de sauts de canal sont conçues de telle sorte que les nœuds se chevauchent les uns avec les autres au moins une fois dans un cycle. Plus précisément,
l’ordonnancement de saut de chaque nœud peut être déterminé par un ensemble de paires (canal, germe) que nous pouvons noter autrement (Chi, Si). S’il y a n canaux disponibles dans le système, le ∈ 1, n-1 , canal est un nombre entier appartenant à l’i tervalle Chi et les germes est un nombre entier tirer aléatoirement dans l’intervalle Si ainsi Ch constituera un cycle périodique entre [0, n- ∈i 0, n-1 1]. Le nœud ainsi incrémente chacun des canaux dans sa liste d’ordonnancement en utilisant le germe et le processus se répète continuellement suivent l’équation : Chi ← (Chi + Si modulo n, qui se traduit de la manière suivante :
Nouveau_Canal= (Ancien_Canal + germe) modulo Nombre_de_Canaux.
Les nœuds apprennent les ordonnancements des uns et des autres en diffusant périodiquement leurs paires (canal, germe), ainsi chaque nœud diffuse sa paire(canal, germe) une fois par slot. En considérant la couple (canal, germe) pour le choix d’un prochain canal, quatre cas possible peuvent se présenter entre deux nœuds :
1) ayant les mêmes canaux et mêmes germes
2) ayant à la fois différent canaux et différentes germes
3) ayant les mêmes canaux mais différent germes
4) ayant les mêmes germes mais différents canaux
Les nœuds ne se chevauchent jamais pendant un cycle que dans le quatrième cas lequel aboutit au problème de partition logique, mais ils le seront au moins une fois dans les autres cas. Ainsi le
quatrième cas ne sera résolu que lorsqu’un slot de parité est ajouté à la fin du cycle (Canalparité = germe).
La method d’accès multi-canal 802.15.4e TSCH (Time Slotted Channel Hopping)
Introduction TSCH
La méthode d’accès IEEE 802.15.4e a été publiée en 2012 comme un amendement au protocole de contrôle d’accès au médium défini par la norme IEEE 802.15.4 (2011) et qui a pour but d’améliorer les performances de la norme IEEE 802.15.4 en terme de latence et de fiabilité en exploitant plusieurs canaux simultanément. Elle adopte deux méthodes d’accès principales : l’accès multiple à répartition dans le temps (TDMA) et l’accès multi-canal [5]. Le concept initial de ce protocole, provient du protocole TSMP (Time synchronized mesh protocol) qui a été étudié en 2008 [9]. L’un des objectifs principaux de la méthode d’accès TSCH est d’étendre les applications de la norme IEEE 802.15.4 au delà du domaine industriel, par exemple les maisons intelligents, la localisation…, mais aussi améliorer la conservation de l’énergie des nœuds dans les réseaux. A cet effet, il est classiquement prévu d’utiliser des calendriers d’ordonnancement (schedule), des slotframes ajustables,… L’une des principales caractéristiques de TSCH est la communication multi-canal, basée sur le saut de canal.
IEEE 802.15.4e TSCH ne modifie pas la couche physique initialement prévue, il peut donc fonctionner sur tout matériel qui est conforme à la norme IEEE 802.15.4. Il se focalise seulement sur la couche MAC. Comme dans la norme IEEE 802.15.4 initiale, un PAN est formé par un coordinateur de PAN en charge de la gestion de l’ensemble du réseau, et, éventuellement, un ou plusieurs coordinateurs qui sont responsables d’un sous-ensemble de nœuds. La méthode d’accès TSCH peut être utilisée sur des topologies de réseau en étoile, arbre, maillée partielle ou totale [42].
Plusieurs travaux essaient d’améliorer la performance du TSCH dans différents contextes, dans [43], les auteurs à travers des méthodes analytiques et par simulations tentent d’analyser l’influence de nombre des canaux sur le délai pris par un nouveau nœud afin de rejoindre le réseau. Puis que le nouveau nœud qui cherche à rejoindre le réseau doit garder la radio toujours allumée pour recevoir le beacon diffusé par le PAN. Un délai long est source de gaspillage de l’énergie.
Principe de fonctionnement de la méthode d’accès multi-canal 802.15.4e TSCH
La structure de la slotframe
Dans un PAN TSCH, le concept de supertrame est remplacé par une trame de slots (slotframe). C’est un ensemble des slots temporels qui se répètent continuellement au cours du temps [42]. La principale différence entre le slotframe et la supertrame est que les nœuds du réseau sont supposées partager une notion commune du temps, ainsi le slotframe se répète automatiquement sans la nécessité des trames beacons afin d’initier des communications entre les différents nœuds du réseau. Le nombre de slots de temps dans une slotframe donnée (influençant ainsi la taille du slotframe) détermine combien de fois chaque slot de temps se répète, en établissant ainsi un ordonnancement (schedule) de communication [42]. La durée d’un slot de temps n’est pas définie dans la norme. Un slot de temps est suffisamment grand [42], [45] pour permettre l’émission d’une trame de taille maximale de 127 octets et le renvoi de son acquittement justifiant la bonne réception de cette trame. Contrairement à la supertrame classique de 802.15.4, les slotframes, et les slots de temps affectés à un nœud dans le slotframe peuvent être initialement communiqués par beacon, mais sont généralement configurés par une couche supérieure du nœud qui rejoint le réseau [42] [48]. TSCH n’impose pas une taille de slotframe. Elle est variable en fonction des besoins de l’application. Plus une slotframe est courte, plus souvent un slot de temps se répète, entraînant ainsi plus de bande passante disponible pour le nœud qui s’en sert, mais aussi une consommation d’énergie plus importante. Pour conserver l’énergie, des longues slotframes sont préférables [46].
Le mode de synchronisation en utilisant l’accès TSCH
Pour assurer la communication multi-canal slottée, dans un réseau TSCH, les nœuds doivent maintenir une synchronisation fine. Tous les nœuds sont supposés être équipés d’une horloge locale qui permet de maintenir une trace du temps. Cependant, puisque les horloges dans les différents nœuds dérivent les unes par rapport aux autres, les nœuds voisins doivent se resynchroniser périodiquement entre eux. Chaque nœud doit synchroniser périodiquement son horloge réseau à au moins un de ses voisins, et il doit fournir également son horloge réseau à ses voisins. Il appartient donc à l’entité (le coordinateur de PAN) qui gère le calendrier de connaître et contrôler une base de temps commune à chaque nœud.
A l’inverse d’autres protocoles de synchronisations, TSCH n’utilise pas de trames balises ou beacons pour la synchronisation d’horloge. Lorsqu’un nœud a reçu une trame de données, il renvoie une trame ACK avec des informations de synchronisation pour corriger la dérive de l’horloge. Cela signifie que les nœuds voisins peuvent se resynchroniser les uns aux autres quand ils échangent des trames de données.
Deux types de méthodes sont définies dans IEEE 802.15.4e (2012) pour permettre à un nœud de se synchroniser dans un réseau TSCH : (i) la synchronisation basée sur l’acquittement ; (ii) et la synchronisation basée sur les trames de données. Dans les deux cas, le récepteur de la trame émise calcule la différence de temps entre l’instant d’arrivée prévue de la trame et son arrivée effective [42] [49].
Pour la synchronisation basée sur l’acquittement, le récepteur fournit des informations de synchronisation au nœud émetteur dans son accusé de réception. Dans ce cas, c’est le nœud émetteur de la trame initiale de data qui se synchronise à l’horloge du récepteur de cette même data.
Pour la synchronisation basée sur des trames de data, le récepteur utilise le delta calculé (par le récepteur) pour ajuster sa propre horloge. Dans ce cas, c’est le nœud récepteur qui se synchronise sur l’horloge de l’émetteur.
Quand il y a du trafic dans le réseau, les nœuds qui communiquent implicitement se resynchronisent en utilisant les trames de données qu’ils échangent. En l’absence de tout trafic de données, s’ils n’ont pas communiqué pendant un certain temps, les nœuds peuvent échanger des trames de données fictives (vides) et ainsi utiliser la trame d’acquittement pour se resynchroniser. Les nœuds doivent se synchroniser périodiquement sur la source de temps de leurs voisins afin d’éviter la dérive de leur horloge.
En bilan, différentes politiques de synchronisation sont possibles dans TSCH. Les nœuds peuvent aussi garder la synchronisation exclusivement en échangeant des beacons améliorés (Enhanced Beacons EB) [42] [49]. Un réseau PAN TSCH est formé lorsqu’un nœud, généralement le coordinateur du PAN, annonce la présence du réseau en envoyant ces EB. Les nœuds déjà dans le réseau envoient périodiquement des EBs pour annoncer la présence du réseau. Lorsqu’un nouveau nœud rejoint le réseau, il écoute les EBs afin de synchroniser au réseau TSCH. On trouve dans les EBs les informations sur les slots de temps qui permettent aux nouveaux nœuds de se synchroniser au réseau. Pour rester synchronisés, les nœuds doivent avoir la même notion du début et de la fin de chaque slot de temps, les informations sur les sauts de canal et la taille du slotframe [42] [49].
Les nœuds peuvent également rester synchronisée en émettant périodiquement des trames valides à une source de temps voisine et utiliser l’acquittement pour se resynchroniser.
Cependant la norme 802.15.4e TSCH définit seulement les mécanismes pour qu’un nœud se synchronise à la source du temps de son voisin, malheureusement elle ne fournit des informations, pour une synchronisation complète multi-saut du réseau, elle précise simplement que cette fonctionnalité est à la charge de la couche supérieure [12].
Finalement, plusieurs méthodes de synchronisation ont été imaginées et proposées dans le standard, la bonne méthode à utiliser dépend des exigences du réseau.
Notons aussi que certains travaux ont abordés l’ordonnancement et la synchronisation TSCH dans un mode distribué [45], et plus encore dans un contexte multi-canal multi-saut [53].
Le protocole de canal dédié multi-interface
Le canal dédié multi-interface [12] [32], à la différence du canal dédié mono-interface, les nœuds ici sont équipés de deux interface conduisant à un mode de fonctionnement différent du contexte mono-interface. Ainsi donc une interface est dédiée aux trames de contrôle, tandis que l’autre interface servira aux transmissions des données. L’interface de contrôle est fixée de façon permanente sur le canal de contrôle dont le rôle est d’affecter un canal des données après négociation entre les deux nœuds. Par contre l’autre l’interface dédiée aux canaux peut commuter dynamiquement entre les canaux des données pour l’émission ou la réception des trames des données, ce principe de fonctionnement est illustré sur la figure 15. Pendant le transfert des données un nœud à travers son interface de contrôle continue à écouter le canal de contrôle et maintient donc une liste d’information sur l’usage des canaux de données et les rendez-vous établis entre les nœuds. Pour émettre une trame de données, l’émetteur vérifie d’après sa liste deux conditions : si le récepteur n’utilise son interface de données, et il y a un canal de données libre ou il sera libre pendant une durée égale à la durée d’échange d’une trame de contrôle. Cette approche, par rapport au contexte mono-interface, réduit les problèmes multi-canal du terminal caché grâce à son interface fixée de façon permanente sur le canal de contrôle, au coût radio non négligeable.
Evolution multi-canal de la méthode d’accès aléatoire Aloha slottée : simplicité et réduction du trafic de service par rapport à un accès contrôlé
Nous avons donc constaté que les méthodes d’accès multi-canal avec RDV ne sont pas une solution simple et optimale aux problèmes classiques rencontrés dans les méthodes d’accès mono-canal (problème du nœud caché…), puisque ces derniers suscitent encore d’autres problèmes (surdité…), surtout quand il s’agit d’un réseau multi-saut où il existe très peu des solutions optimales car faisant souvent recours à l’utilisation des trames de contrôles afin d’établir le RDV. En multi-saut, les nœuds se trouvant au-delà d’un saut ne sont pas souvent conscients des RDV pris en local et, ainsi peuvent perturber les transmissions qui se déroulent suite aux RDV.
Pour des telles raisons, nous nous orientons vers une solution protocolaire MAC simple, en proposant une méthode d’accès multi-canal sans RDV basée sur l’Aloha slottée afin d’éviter la propagation et la négociation des RDV, et ainsi réduire le trafic de services par rapport à un accès contrôlé. Nous espérons que cette réduction permettra à combler les lacunes liées à la faible performance native d’Aloha de 18% (tout de même doublée dans sa version slottée comme nous allons le rappeler plus bas).
Selon la topologie de la figure 25, en utilisant la méthode d’accès multi-canal multi-saut sans RDV, la transmission de A vers R n’empêche pas leurs voisins de choisir des canaux différents pour transmettre leurs données figure 26. Ainsi plusieurs transmissions concurrentes se déroulent au même moment sur les canaux disponibles dans une même zone d’interférence mono-canal.
Rappel sur le protocole SiSP de synchronisation des nœuds
Diffusion des horloges et consensus
On vient de le voir, la synchronisation des nœuds est un mécanisme très important, plus particulièrement dans un réseau de capteurs sans fil, permettant aux nœuds capteurs dans le réseau d’avoir une différence entre leurs horloges subjectives la plus faible possible. Pour parvenir à une synchronisation globale dans un réseau sans fil ad hoc, un protocole appelé SiSP (Simple Synchronisation Protocol) pour la synchronisation des nœuds dans le réseau a été imaginé dans [62]. C’est un protocole scalable qui n’introduit pas de contraintes de hiérarchie dans la topologie du réseau, à l’inverse d’autres comme le très connu RBS [63]. Le protocole de synchronisation SiSP est basé sur un algorithme simple permettant aux nœuds du réseau en quelques itérations d’obtenir par consensus une horloge partagée (SCLK) obtenue par la méthode de la moyenne.
Le principe d’échange des horloges est simplement basé sur un seul type de message : SYNC dont la charge utile contient la valeur de SCLK (horloge partagée) du nœud au moment de la création du message SYNC. Le message est diffusé de manière simple (sans MAC) comme dans le mode diffusion des trames beacons de 802.15.4. Ainsi par exemple, le message SYNC peut être simplement encapsulé par exemple dans la charge utile des beacons 802.15.4. On peut aussi imaginer que cette horloge est émise dans un champ supplémentaire de toute trame, qu’elle soit diffusée (cas idéal) ou pas (dans ce cas-là, il faut compter sur un trafic important du réseau entre tous les nœuds. Nous en reparlerons plus tard…
Chaque nœud maintient deux variables principales, à savoir : le SCLK (horloge partagée) et le LCLK (horloge locale). Le nœud écoute durant 99 tops d’horloge (si on se base sur 1 émission toutes les 100 incrémentations) tandis qu’il calcule la moyenne de toutes les horloges reçues (RCLK) de ses voisins avec son propre SCLK. Pendant ce temps-là, son SCLK est modifiée par la valeur de chaque moyenne.
Au 100ième top d’horloge, le nœud diffuse sa valeur SCLK et les voisins appliquent le même algorithme en effectuant le calcul de la moyenne (SCLK= (SCLK+RCLK / 2)). Chaque fois qu’on atteint le top d’horloge 100, le message SYNC est diffusé. Après un certain nombre de cycles, en fonction du nombre de nœuds et de la topologie, une horloge de consensus globale est obtenue dans tous les nœuds du réseau, car le résultat de la division est arrondi puisque le SCLK est une valeur entière. L’horloge (SCLK) de consensus est obtenue de manière décentralisée, sans aucune prérogative hiérarchique. La figure 30, montre un exemple de principe de fonctionnement du protocole SiSP où, on observe des échanges des messages SYNC entre deux nœuds A et B.
On voit ici que le nœud A est mis en marche avant le nœud B jusqu’à ce que son horloge locale atteigne la valeur 380. A un moment donné, les nœuds partageront la même valeur de SCLK. Le principe simple du protocole SiSP montre que, lorsqu’un message SYNC est reçu, chaque nœud calcule la moyenne entre les valeurs de RCLK et SCLK, et le résultat de ce calcul est considéré comme la nouvelle valeur de SCLK. Si RCLK et SCLK sont égaux (à l’arrondi prés), cela signifie que l’horloge SCKL du nœud est la même que celle de son voisin.
Méthode d’accès MAC multi-canal sans RDV proposée
Nous allons dans cette partie, présenter la méthode d’accès multi-canal aléatoire, donc sans RDV, adaptée ainsi aux topologies multi-sauts, que nous proposons dans un premier temps. Cette méthode d’accès de base, sera ensuite enrichie par diverses options permettant de l’améliorer, en fonction des cas d’études et d’applications.
Hypothèses pour la mise en œuvre de la méthode d’accès multi-canal de base
Dans la méthode d’accès multi-canal que nous proposons, nous supposons un nombre des nœuds Net un nombre des canaux C. On suppose aussi que le nombre des nœuds est supérieur au nombre de
canaux (donc N>C), ce qui est le cas le plus courant et le plus complexe à régler. Le réseau est composé classiquement de nœuds (dans notre prototypage, ce seront des nœuds WiNo) qui sont initialement mono-interface (une seule radio par nœud), donc à un instant donné, un nœud peut soit émettre soit recevoir sur un canal Ck(k=1, 2, 3…) parmi les canaux C1, C2, C3… disponibles mais, le nœud ne peut pas effectuer les deux opérations à la fois (c’est-à-dire émission et réception sur un même canal en même temps, ou 2 émission ou 2 réceptions en même temps). Nous considérons aussi une topologie à plat, sans hiérarchie, avec une disposition des nœuds nécessitant généralement un certain nombre de sauts (que nous pouvons noter NS: Nombre de Saut avec NS=1, 2, 3…). Si par exemple NS=1, ceci veut dire que le nœud a fait un saut pour atteindre sa destination, si NS=2 il a fait deux sauts, etc. On considère aussi qu’il n’y a pas de nœuds isolés puisqu’il existe toujours au moins un lien entre un nœud et le reste du réseau.
Pour la synchronisation des nœuds dans le réseau, nous utilisons comme vu ci-dessus le protocole SiSP développé par l’équipe IRT à l’IUT de Blagnac, qui permet une discrétisation de l’échelle du temps en tranche ou slots. Chaque slot a une durée qui équivaut à l’émission d’une trame d’une longueur égale par exemple lors de notre implémentation à 57 octets (type de la trame de données, adresse source, destination, numéro de séquence et, charge utile), et son acquittement (type de la trame d’acquittement, adresse source, destination, numéro de séquence). Chaque cycle commence par un slot réservé pour les émissions et les réceptions des beacons qui sont utilisés pour émettre les informations utiles à SiSP et la MAC (horloges, informations de voisinage et de connaissance sur l’utilisation de canaux que nous verrons plus tard).
Nous supposons que dans chaque cycle, les slots pairs sont réservés uniquement pour les émissions et les réceptions des beacons sur les différents canaux disponibles. Le premier slot (dont le numéro est 0) du cycle est donc un slot pair de beacons, le second slot est un slot de DATA/ACK.
En début de slot pair, chaque nœud commence par décider aléatoirement s’il émet un beacon dans ce slot ou s’il se met en écoute pour recevoir le beacon d’un autre nœud.
Soit le paramètre P la probabilité d’écouter ou d’émettre le beacon: si par exemple P=0.1, le nœud émet en moyenne 1 beacon sur 10 slots (P=1/10) et peut donc ainsi recevoir pendant les 9 autres slots.
Dans nos hypothèses, le médium radio est supposé réaliste, on estime que le taux d’erreur binaire BER (Bit Error Rate) typique est de 10-5.
Chaque trame dispose d’un CRC 16 bits (CCITT) pour la détection des erreurs. Dans cette méthode d’accès multi-canal où les diffusions sont nombreuses, il n’y a pas d’acquittement négatif (NACK).
Nous considérons uniquement des acquittements positifs (ACK) quand une trame de données (toujours en unicast) est bien reçue. Les beacons qui sont diffusés ne sont pas acquittés. Les ACK considérés ici sont des ACK de niveau MAC, donc à un seul saut.
Nous considérons aussi que le trafic applicatif n’engendre pas de débordement. La couche 7 est juste présente pour évaluer la couche 2 multi-canal dans notre testbed présenté au chapitre suivant.
La couche 3 permettant d’acheminer une donnée d’un nœud émetteur vers un nœud récepteur est basée dans un premier temps sur un routage aléatoire : quand un nœud reçoit une trame de donnée, il tire au sort un voisin de destination pour lui propager cette donnée si cette trame n’est pas pour lui (elle ne porte pas son adresse de destination). La table de voisinage de niveau 2 maintenue par chaque nœud est ici utilisée également par cette couche 3 (cross-layer). Un historique est géré afin d’éviter les boucles : un couple {adresse globale source, numéro de paquet} est utilisé pour différencier les paquets. Un numéro de paquet ou numéro de séquence est utilisé (par exemple sur 8 bits).
|
Table des matières
Chapitre 1 Etat de l’art des méthodes d’accès multi-canal pour les réseaux locaux sans fil
1.1 Etat de l’art et problématique
1.1.1 Les méthodes d’accès mono-canal proposées pour les réseaux locaux sans fil
1.1.2 Les méthodes d’accès multi-canal mono-saut
1.1.3 Méthode d’accès multi-canal multi-saut
1.1.4 Intérêt des approches étudiées dans le contexte multi-saut
1.2 Conclusion
Chapitre 2 Proposition d’une méthode d’accès multi-canal multi-saut
2.1 Objectifs et justification des choix
2.1.1 Introduction
2.1.2 Augmentation des débits et réduction des délais d’attente en émission
2.1.3 Topologie multi-sauts
2.1.4 Autres problèmes de RDV en multi-saut liés aux chemins
2.1.5 Evolution multi-canal de la méthode d’accès aléatoire Aloha slottée : simplicité et réduction du trafic de service par rapport à un accès contrôlé
2.2 Rappel de la méthode d’accès Aloha slottée mono-canal
2.2.1 Principe de fonctionnement de l’Aloha pur
2.2.2 Principe de fonctionnement de l’Aloha slotté mono-canal
2.3 Rappel sur le protocole SiSP de synchronisation des noeuds
2.3.1 Diffusion des horloges et consensus
2.3.2 Exemples de résultats de SiSP
2.4 Méthode d’accès MAC multi-canal sans RDV proposée
2.4.1 Hypothèses pour la mise en oeuvre de la méthode d’accès multi-canal de base
2.4.2 Principe de fonctionnement de la méthode d’accès multi-canal basée sur l’Aloha slotté
2.4.3 Options d’améliorations et paramétrages optimaux
2.5 Conclusion
Chapitre 3 Implémentation du protocole MAC multi-canal sans RDV et analyse de performance
3.1 Introduction
3.2 Présentation des noeuds WiNo utilisé pour l’implémentation et testbed de la couche MAC multi-canal multi-saut sans RDV
3.3 Métriques pour l’étude des performances
3.4 L’accès mono-canal
3.4.1 Les automates mono-canal de transmissions des trames de données
3.4.2 Les formats des trames
3.4.3 Les séquences des trames
3.4.4 Topologie de test pour accès mono-canal avec récepteur à portée d’un seul émetteur
3.4.5 Analyse de performances d’un récepteur à portée radio de 2 émetteurs
3.4.6 Accès mono-canal sans RDV, topologie avec émetteur générant des trafics vers 2 récepteurs
3.5 L’accès multi-canal
3.5.1 Automates de transmissions multi-canal
3.5.2 Analyse de performances d’un récepteur à portée radio de 2 émetteurs
3.5.3 Accès multi-canal sans RDV, cas d’un émetteur générant des trafics vers 2 récepteurs93
3.6 L’accès multi-canal avec stratégie de rémanence sur le précédent canal d’émission et de réception
3.6.1 Analyse de performances
3.7 Conclusion
3.8 Modèle analytique de la méthode d’accès multi-canal aléatoire sans Rendez-vous
3.8.1 Modèle analytique mono-saut
3.8.2 Modèle analytique multi-saut
3.9 Méthode d’accès multi-canal avec stratégie de rémanence testbed Ophelia
3.9.1 Intérêt de l’accès multi-canal par rapport au mono-canal
3.9.2 Cas de deux récepteurs et plusieurs émetteurs (contexte multi-saut)
3.10 Conclusion
Télécharger le rapport complet
