Sélection et contrôle de modes de déplacement pour un robot mobile autonome en environnements naturels

Les méthodes d’accès mono-canal proposées pour les réseaux locaux sans fil 

Récemment, des nombreuses méthodes d’accès MAC ont été proposées par différents travaux pour les réseaux sans fil en général et les réseaux ad hoc en particuliers et qui avaient abordé diverses questions très pertinentes, parmi lesquelles, les problèmes des nœuds cachés, les nœuds exposés, et les problèmes des collisions, etc. Certaines de ces méthodes mono-canales ont été par la suite sérieusement travaillées afin de les adapter aux transmissions multi-canal dans le but de réduire les différents problèmes rencontrés par l’accès au medium mono-canal. Dans ce chapitre d’état de l’art, nous évoquons brièvement les principales méthodes d’accès monocanal proposées généralement pour les réseaux sans fil ; ensuite nous abordons les différents problèmes d’accès au médium mono-canal qui ont suscité d’autres méthodes d’accès multi-canal avec des contraintes spécifiques, dont quelques approches de bases ont été proposées afin de résoudre ces problèmes. Nous introduisons aussi le contexte multi-canal multi-saut qui a été déjà étudié par certains travaux précédents et qui fait aussi l’objet d’étude de cette thèse. 

Contrôle d’accès au médium dans les réseaux sans fil 

Dans les réseaux sans fil, pour que tous les nœuds mobiles utilisent le même spectre de fréquence (canal physique), le contrôle d’accès au médium (MAC) joue un rôle primordial dans la coordination de l’accès au canal entre les nœuds afin que l’information passe d’un nœud à un autre. L’objectif principal du protocole MAC est de coordonner l’accès au canal entre plusieurs nœuds pour atteindre une meilleure utilisation du canal. En d’autres termes, la coordination de l’accès au canal devrait réduire au minimum ou d’éliminer l’incidence de collisions et d’optimiser la réutilisation spatiale en même temps. Nous allons d’abord décrire les protocoles MAC basés sur la contention où les nœuds accèdent au medium de manière aléatoire et compétitive pouvant conduire à de probables collisions puisque, chaque émetteur émet quand il peut, ainsi donc la probabilité pour que deux nœuds émettent au même moment n’est pas à exclure. On peut citer entre autres parmi ces protocoles : Aloha, Aloha slotté, CSMA et CSMA/CA. Les méthodes d’accès sans contention font recours à des méthodes de multiplexage permettant aux différents nœuds du réseau d’accéder au canal de façon équitable. Les nœuds suivent un certain 14 ordonnancement qui leurs garanti un temps de transmission sans collision. L’exemple de ces protocoles : le TDMA (Time Division Multiple Access), le FDMA (Frequency Division Multiple Access), et le CDMA (Code Division Multiple Access). Parmi ceux-ci, TDMA est le plus couramment utilisé dans les réseaux ad hoc. Dans la méthode d’accès TDMA, le canal est généralement organisé en trames, où chaque trame prend place dans nombre fixe de slots de temps. Les hôtes mobiles négocient un ensemble de slots de temps TDMA dans lesquels ils transmettent leurs trames. Si un contrôleur centralisé existe, il est en charge de l’attribution des slots pour les nœuds de la zone qu’il contrôle. De cette façon, les transmissions sont sans collisions, et il est possible de planifier des transmissions de nœud selon un critère d’équité ou de qualité de service. En général, les protocoles sans contention fonctionnent en mode centralisé, surtout sur de topologies statiques, ou encore sur certains petits réseaux dédiés à des applications de taille limitée en nombre de nœuds. Dans un environnement dynamique, distribué et multi-saut, elles sont difficiles à mettre en œuvre. Par contre les protocoles basés sur la contention sont plus adaptés au contexte distribué et au concept de l’auto-organisation . 

Les protocoles MAC basés sur la contention 

La méthode d’accès ALOHA ou ALOHA pur

(Pure ALOHA) ALOHA est le premier protocole d’accès aléatoire, le plus connu et simple : chaque fois qu’une station a un paquet à transmettre, alors il transmet simplement sans attendre ou vérifier si une autre station est déjà en cours de transmission. Les nœuds ne se préoccupent pas de l’état du canal. Le principe de fonctionnement est le suivant : à chaque fois qu’une station veut envoyer de données, alors elle émet son paquet sans se préoccuper de l’état du canal. Si elle ne reçoit pas un accusé de réception au bout d’un certain délai prédéfini, elle retransmet le paquet de la même manière après un délai d’attente aléatoire. Si au-delà d’un certain nombre de tentatives aucun acquittement n’a pas été reçu, alors il y a échec de la transmission. Au cas où plusieurs stations émettent des trames en même temps, il y aura donc un conflit d’accès et les paquets seront en collision. Cette méthode d’accès n’est pas avantageuse pour un réseau de grande taille et multi-saut. Un autre protocole a été proposé pour corriger les erreurs engendrées par ALOHA, appelé ALOHA slotté (Slotted-ALOHA ou SA) 

ALOHA slotté (Slotted-ALOHA) 

Cette méthode apporte une amélioration à ALOHA pur afin de réduire le nombre des collisions. Ainsi le temps est discrétisé en slots de temps d’une durée fixe appelée « slots » et les stations ne vont émettre qu’au début de chaque slot. Même avec ALOHA slotté, des collisions peuvent se produire lorsque deux paquets sont émis dans le même slot de temps. Toutefois, la probabilité de collision est réduite et le débit est amélioré [21] [22]. Dans le système slotté, tous les paquets transmis ont la même longueur et chaque paquet nécessite une unité de temps (appelée slot) pour la transmission. Les stations sont autorisées à commencer la transmission uniquement au début d’un slot et non pas à n’importe quel moment. L’inconvénient est 15 que, contrairement ALOHA pur, ALOHA slotté nécessite une synchronisation de temps global qui est un problème difficile en soi.

Le protocole CSMA 

Contrairement à ALOHA où les stations émettent leurs données quand elles veulent transmettre, pour les protocoles de détection de la porteuse, les stations écoutent le canal avant de transmettre. Chaque station écoute si le canal est libre, elle émet ses paquets de données ; s’il est occupé, elle diffère alors sa transmission selon une probabilité p de persistance d’écoute, d’où on distingue trois variantes du CSMA (Table 1) : persistent CSMA, non-persistent CSMA, et p-persistent CSMA. Ces protocoles diffèrent par l’action dont la station qui a un paquet à transmettre occupe après détection le canal au repos [19]. En CSMA persistent (persistent CSMA), le nœud écoute de manière permanente le canal, dès qu’il est libre, il émet ses données. Par contre, le protocole CSMA non persistant (non-persistent CSMA) a été proposé afin de corriger les défauts précédents : un nœud qui veut transmettre des données détecte le canal pour déterminer si aucun autre nœud n’a commencé à transmettre. Si le nœud détecte une activité sur le canal, il effectue une opération de temporisation (backoff) avant d’essayer de transmettre à nouveau. Lorsque le nœud ne détecte pas d’activité sur le canal, il transmet immédiatement ses données. Pour le protocole p-persistent CSMA, le nœud continue à détecter le canal lorsqu’il y a une activité sur ce canal, plutôt que de différer et de vérifier un peu plus tard. Lorsque le nœud ne détecte pas d’activité sur le canal, soit à la première tentative ou à la fin d’une transmission précédente par un autre nœud, il transmet avec une probabilité p, et diffère l’émission avec une probabilité 1-p  . Une autre version étendue de CSMA, appelé CSMA avec évitement de collision (CSMA/CA Carrier Sense Multiple Access with Collision Avoidance), ajoute des mécanismes pour limiter le nombre des paquets des données qui seront perdus lorsque les nœuds proches transmettent en même temps. Les réseaux sans fil cherchent à éviter les collisions plutôt que de les détecter, c’est ainsi que le CSMA/CA tente d’éviter les collisions en utilisant un échange de messages de contrôles pour réserver le canal sans fil avant chaque transmission de données. Le nœud émetteur transmet d’abord un message de contrôle : une demande d’envoi au récepteur (RTS Request To Send). Si le récepteur peut recevoir les données en cours, il répond avec un message de contrôle : prêt à émettre (CTS Clear To Send). Le nœud émetteur réessaie la transmission par la suite, s’il ne reçoit pas un CTS dans un certain délai. Après la bonne réception d’un CTS, l’émetteur transmet ses données.