Brevet FR3057432A1 — publié le 20180413

PROCEDE ET SYSTEME POUR GERER L'ACCES AU CANAL DE COMMUNICATION L'invention concerne un procédé pour gérer l'accès au canal de communication notamment dans un réseau de communications sans fil, ad hoc, et pour un trafic sporadique et aléatoire contraint en délai. Les réseaux ad-hoc sans fil sont caractérisés par l'absence d'infrastructure fixe. Le contrôle d'accès au canal se fait, soit de manière statique où chaque noeud se voit réserver des ressources radio pour la transmission de son trafic, soit de manière centralisée où un noeud central est chargé de gérer l'accès pour les noeuds du réseau, ou encore d'une manière distribuée où chaque noeud accède au canal d'une manière aléatoire afin de réduire les conflits d'accès. Un trafic sporadique est un trafic qui se produit de manière irrégulière avec des paquets de faible, voire de très faible taille. La gestion d'accès au canal de ce type de trafic peut s'avérer délicate si on y ajoute une contrainte de qualité de service à respecter, comme un délai d'acheminement maximum à ne pas dépasser pour la distribution de paquets. L'art antérieur divulgue plusieurs solutions pour accéder au canal de communication. Une première solution est une solution d'accès statique qui exige de réserver un nombre adéquat de ressources pour le type de trafic sporadique, afin de prendre en compte la taille du réseau (nombre de noeuds à servir) et le délai maximum d'acheminement des paquets de données. De plus, cette solution n'est pas adaptée pour ce type de trafic, du fait de la nature aléatoire du trafic sporadique. Un deuxième type de solution est une solution d'accès centralisé. Cette solution nécessite que les noeuds réguliers demandent une autorisation d'accès au noeud désigné comme chef dans le réseau. Compte tenu de la faible taille des paquets pour les trafics sporadiques et du délai à respecter pour la distribution des paquets, le coût de cette signalisation en termes de ressource radio à y consacrer peut être supérieure au coût de la 3057432 2 réservation statique de ressources radio (sans signalisation de demande d'accès par les noeuds réguliers). Le standard IEEE 802.15.4 décrit par exemple dans le document, IEEE Std 802.15.4 (2006). Part 15.4: « Wireless medium access (MAC) and 5 physical layer (PHY) specifications for low-rate wireless personal area networks (WPANs) », donne une méthode pour les réseaux sans fil à faibles débits, faibles coûts et faibles consommations. Ce standard spécifie une couche de contrôle d'accès MAC centralisée qui supporte la transmission de données urgentes, via le mécanisme de créneaux temporels garantis ou 10 GTS (abréviation anglo-saxonne de Guaranteed Time Slots). Ce mécanisme est efficace pour des paquets dont la taille est largement supérieure à la taille de la signalisation nécessaire pour le GTS. Ceci limite son utilisation pour des trafics ayant des paquets de données très courts. Le standard IEEE802.11e décrit dans le document, « Wireless 15 Medium Access Control (MAC) and physical layer (PHY) specifications: Medium Access Control (MAC) Enhancements for Quality of Service (QoS) », 2005 , est adapté aux réseaux locaux sans fil. Il prend en compte le support de la qualité de service (QoS : Quality of Service) via le mécanisme d'accès de coordination hybride ou HCCA (connu sous l'expression anglo- 20 saxonne Hybrid Coordination Function Channel Access) où des opportunités de transmission sont allouées au flux nécessitant une certaine qualité de service QoS. Le standard IEEE 802.15.6 donné dans le document, « IEEE P802.15.6/D01, Wireless Medium Access Control (MAC) and Physical Layer 25 (PHY) Specifications for Wireless Personal Area Networks (WPANs) used in or around a body », May 2010, est bien adapté pour des réseaux de corps, expression connue de l'homme du métier. Ce standard définit un mécanisme similaire pour le support de trafics urgents via une période d'accès exclusive ou EAP (Exclusive Access Period). 30 L'art antérieur décrit aussi des mécanismes d'accès hybrides distribués utilisant des protocoles à base de protocoles CSMA/ALOHA 3057432 3 connus de l'homme du métier et d'accès multiples à répartition dans le temps ou TDMA (Time Divisional Multiple Access), qui essaient d'exploiter les avantages de chacun de ces modes d'accès. Il n'y a pas de contention avec le protocole TDMA pour les trafics prioritaires ou urgents, plus de flexibilité 5 avec les protocoles CSMA ou ALOHA pour les trafics moins prioritaires ou dans les situations de fortes charges, comme il est décrit par exemple dans le document de L. Sitanayah, C. J. Sreenan and K. N. Brown, « ER-MAC: A Hybrid MAC Protocol for Emergency Response Wireless Sensor Networks », in 2010 Fourth International Conference on Sensor Technologies and 10 Applications, 2010. Dans la suite de la description, les expressions suivantes sont utilisées : - Un slot correspond, par exemple, à un créneau temporel, plus généralement à une unité de transport, sa capacité de transport est 15 fixe, - Un slot réservé ou slot dédié est un slot réservé à un noeud, - Un slot partagé est un slot en libre accès à tous les noeuds du réseau qui peuvent le programmer pour la transmission de données, - Un cycle d'accès correspond à une période temporelle pendant 20 laquelle les noeuds du réseau tentent d'accéder au réseau, - La capacité résiduelle d'un slot est la capacité restante ou la place restante au niveau d'un slot pour la programmation d'une transmission de paquets de données additionnelles. Le mot « slot » par abus de langage pourra aussi désigner une unité 25 fréquentielle ou spatiale de communication pouvant être programmée pour la transmission de données. L'invention concerne un procédé ou protocole d'accès dans un réseau de communication comprenant plusieurs noeuds Mi émetteurs/récepteurs, l'échange de données ou de paquets de données se 30 faisant grâce à un protocole de communication utilisant une unité de 3057432 4 communication pour la programmation caractérisé en ce qu'il comporte au moins les étapes suivantes : a) au niveau d'un noeud Mi du réseau, à l'arrivée d'un nouveau paquet de données 1(P) de taille P, mesurer le temps Ts(k) qui sépare l'instant 5 d'arrivée de ce paquet 1(P) des instants d'occurrence t(k) de ses prochains slot dédiés qui sont dans la limite de Dmax avec k l'indice de tel slots, k= 1, , Ns tel que : Ts(Ns) Dmax, b) parmi les Ns slots trouvés dans le délai Dmax, déterminer le nombre de 10 slots Nsf qui ont une capacité résiduelle supérieure ou égale à la taille du nouveau paquet de données 1(P), Cr (k) P , o Si le nombre de slots Nsf est positif, alors programmer un slot parmi Nsf pour la transmission des données et mettre à jour l'information sur la capacité résiduelle de ce slot, 15 o Si le noeud ne trouve pas de slot dédié parmi les Ns slots qui présentent encore de la place pour la programmation (Nsf=O), alors compter le nombre de slots partagés Nab qui se trouvent dans le créneau temporel défini par la limite maximum de transmission Dmax , qui ont déjà été programmés pour une future transmission, et qui 20 disposent de place pour transporter le nouveau paquet: Nab = {k, tel que Ts(k) Dmax et Cr(k) 0, alors le noeud choisit aléatoirement un slot partagé parmi Nab , programme la transmission du nouveau paquet au niveau de ce slot partagé, et 25 met à jour l'information sur la capacité résiduelle de ce slot, o Si le nombre de slots partagés qui disposent encore de la place pour la programmation est nul, Nab = 0, alors le noeud compte le nombre de slots partagés Na! qui sont dans la limite de Dmax et qui n'ont pas déjà été programmés pour une future transmission: 3057432 5 Naf= Itic, tel que Ts(k) Dmax et Cr(k) = C}I, où C est la capacité de transport du slot, o Si le nombre de slots partagés Naf est positif, Naf > 0, alors le noeud choisit aléatoirement un slot partagé parmi Naf, programme 5 la transmission du nouveau paquet au niveau de ce slot partagé, et met à jour l'information sur la capacité résiduelle de ce slot, o S'il n'existe aucun slot partagé pour la transmission Naf = 0, alors le nouveau paquet est rejeté. On choisit, par exemple, de programmer le premier slot dédié 10 disponible pour la transmission du paquet de données. Le slot partagé peut aussi être choisi en utilisant un algorithme de choix aléatoire, de type ALHOA. Selon une autre variante de réalisation, le slot partagé à programmer est déterminé en fonction du taux d'occupation des slots 15 partagés. Un paquet de données à transmettre d'une taille supérieure à la capacité de transport du slot C peut être scindé en plusieurs sous-paquets de données, chaque sous-paquet étant traité comme un paquet. L'unité de transmission est un créneau temporel ou slot. 20 L'invention concerne aussi un système de communication dans un réseau comprenant N noeuds, lesdits N noeuds Mi communiquent entre eux en utilisant un protocole de communication, chaque noeud comprenant au moins un émetteur/récepteur, un processeur adapté à exécuter le procédé d'accès selon l'invention, chaque noeud souhaitant émettre et/ou recevoir 25 des données comporte au moins les modules suivants: o Un module émetteur/récepteur, o Un module de mesure du temps entre l'instant d'arrivée to d'un paquet de données à émettre et l'instant de démarrage d'une unité de transmission dans un délai maximum à respecter pour une qualité de 30 service requise, 3057432 6 o Une table mémorisant la programmation des slots partagés utilisés pour la transmission de données, o Un algorithme adapté à élire un slot à programmer pour la transmission de données. 5 Le système est par exemple équipé d'un algorithme aléatoire pour choisir le slot à programmer pour la transmission de données. L'algorithme de choix du slot dédié peut aussi être un algorithme tenant compte du taux d'occupation du slot, du nombre de paquets de données déjà programmés sur ce slot. 10 D'autres caractéristiques et avantages de la présente invention apparaîtront mieux à la lecture de la description qui suit d'exemples de réalisation donnés à titre illustratif, annexée des figures qui représentent : - Figure 1, une illustration de la solution statique selon l'art antérieur, - Figure 2, une illustration de la solution purement aléatoire selon l'art 15 antérieur, - Figure 3, un exemple de système de communication à accès hybride selon l'invention, - Figure 4, une illustration de la répartition de slots dédiés et de slots à accès aléatoire, 20 - Figure 5, un organigramme illustrant les étapes mises en oeuvre par le procédé selon l'invention, et - Figure 6 et figure 7, un schéma des étapes d'accès du procédé selon l'invention. La figure 1 illustre la pré-allocation de créneaux temporels ou slots 25 pour chaque noeud d'un réseau de communication, selon l'art antérieur. Pour un réseau avec N noeuds, dans l'exemple donné, deux slots par trame sont alloués au service. Ces slots sont alloués à tour de rôle pour chaque noeud du réseau. Pour un service exigeant un délai maximum Dmax pour la transmission des données et une durée de trame Tf, le nombre de slots par 30 trame que le système doit allouer au service pour respecter la contrainte sur le délai est de : 3057432 7 NTf Nop . Dmax Ce nombre peut se révéler important. De plus, étant donné la nature aléatoire du trafic, une solution statique ne permet pas de gérer les situations où les paquets de données arrivent en rafale (burst). 5 La figure 2 illustre une solution de l'art antérieur purement aléatoire avec contention, sans pré-allocation des slots, avec toutefois une allocation d'un nombre important de slots par trame pour le service afin de réduire la probabilité de collision d'accès. Dans l'exemple, pour un réseau de N noeuds Mi, deux slots 10 Sr2 ; Sr3, Sr4, par trame F sont alloués au service. Ces slots sont partagés par tous les noeuds du réseau et sont accessibles d'une manière aléatoire, i.e., un noeud choisit d'une manière aléatoire un slot d'émission parmi les slots partagés à venir qui sont alloués au service dans la limite du délai de transmission exigé. 15 La figure 3 illustre un exemple d'architecture système ou réseau de communication décentralisé comprenant N noeuds Mi (seuls trois noeuds sont représentés pour des raisons de simplification) permettant la mise en oeuvre du procédé selon l'invention. Le réseau décentralisé est, par exemple, un réseau de type ad-20 hoc. Les noeuds Mi communiquent entre eux grâce à la mise en oeuvre d'un protocole de communication, les échanges étant synchronisés selon une méthode connue de l'homme du métier. Un noeud Mi (M1, M2, M3, M4) est équipé d'un module émetteur/récepteur 11i, d'un processeur 12i adapté à exécuter les étapes du 25 procédé selon l'invention, d'un dispositif de mesure 13i de temps entre l'instant d'arrivée d'un paquet sur le noeud Mi et l'instant tdébut correspondant au début d'un slot, d'une base de données 14i permettant le stockage des informations relatives aux taux d'occupation de chacun des slots qui lui sont dédiés ou des slots partagés. Le noeud Mi comporte aussi un compteur 15i 30 qui permet de comptabiliser le nombre de slots. Un noeud connaît 3057432 8 initialement les slots dédiés qui lui sont attribués et les slots partagés. Il peut mémoriser sous forme d'un tableau par exemple, pour différents instants et différents slots, le taux d'occupation des slots (taille des données programmées pour la transmission sur un slot). Ceci reste vrai pour les slots 5 partagés. La figure 4 illustre un exemple de répartition de slots dédiés et de slots partagés, selon l'invention, pour un réseau synchronisé de taille N noeuds avec un accès en TDMA et une trame de durée Tf. Chaque slot a une capacité de transport C. Dans cet exemple, on considère un trafic avec 10 une exigence de délai maximum Dmax. Les paquets du trafic ont une taille P inférieure à la capacité de transport d'un slot, P 5 C. L'exemple de la figure 4 est donné avec les hypothèses suivantes : - Nap slots par trame sont alloués pour le service du trafic considéré, 15 - On définit un cycle d'accès composé de Ncyc slots sur les slots alloués au trafic, - Nd slots dédiés Sdi parmi Ncyc sont alloués statiquement à chaque noeud du réseau à tour de rôle, - N, slots aléatoires Sri parmi Ncyc sont accessibles d'une manière 20 aléatoire par tous les noeuds du réseau. La figure 4 illustre un exemple du système avec deux slots alloués au service du trafic considéré par trame, Nop = 2, quatre slots pour le cycle d'accès, Ncyc= 4, dont trois slots sont dédiés, Nd = 3 et un slot en accès aléatoire N, = 1 , deux slots dédiés Shi, Sd2, par trame impair F1 et un slot 25 dédié Sd3 et un slot partagé Sri par trame impair F2. Chaque noeud Mi dispose d'un slot qui lui est réservé à tour de rôle parmi les slots dédiés dans le cycle d'accès. Chaque noeud Mi connaît, pour chaque slot qui lui est dédié et pour chaque slot aléatoire sur lequel il a programmé une transmission de 3057432 9 l'information, la capacité résiduelle Cr de ce slot, i.e., place qu'il reste au niveau du slot pour être programmé pour la transmission de données. La figure 5 illustre les étapes mises en oeuvre par le procédé selon l'invention. 5 A l'arrivée d'un paquet de données 1(P) de taille P, 501, un noeud Mi mesure le temps Ts(k) qui sépare l'instant d'arrivée du paquet to du début de chacun de ses prochains slot dédiés Sdi qui sont dans la limite de Dmax (i.e. avant l'instant Dmax) avec k l'indice d'un slot , k = 1, ...,N5 tel que : (Ns) Dmax. 10 Parmi les Ns slots trouvés présents dans l'intervalle de temps limité par Dmax, le noeud Mi détermine, 502, le nombre Nsf de slots qui ont une capacité résiduelle Cr(k) supérieure ou égale à la taille P du paquet (Cr(k) P ), c'est-à-dire qu'au niveau du slot, il existe de la place pour la programmation du nouveau paquet l'P pour la transmission de données, 15 a) Si le nombre de slots Nsf est positif, alors le noeud Mi programme la transmission du nouveau paquet de données sur un des Nsf slots, par exemple dans le premier slot k=1, k = 1, ..., Nsf, 503, 504, b) Si le nombre de slots Nsf est nul, 505, alors le noeud Mi compte le nombre Nab de slots partagés Sr, qui se trouvent dans le créneau 20 temporel défini par la limite maximum de transmission Dmax , qui ont déjà été programmés pour une future transmission et qui disposent de place pour transporter le nouveau paquet, Nab = Ifk, tel que Ts(k) Dmax et Cr(k) 0, alors le noeud Mi choisit aléatoirement un slot partagé Sr, parmi Nab, programme la transmission du nouveau paquet au niveau de ce slot partagé Sr, et met à jour l'information sur la capacité résiduelle de ce slot 507, 3057432 10 - Si le nombre de slots partagés Sri qui disposent encore de la place pour la programmation est nul, Nab = 0, alors le noeud Mi compte le nombre de slots partagés Naf qui sont dans la limite de Dmax et qui n'ont pas déjà été programmés pour une future transmission: 5 Naf = Itk, tel que Ts(k) 0, alors le noeud choisit aléatoirement un slot parmi Naf et y programme la transmission du nouveau paquet, met à jour l'information sur la capacité résiduelle de ce slot 508, - S'il n'existe aucun slot partagé Sri pour la transmission, Na! = 0, 10 alors le nouveau paquet est rejeté, 509. La figure 6 illustre Ns slots dédiés/réservés présents dans le délai Dmax à partir de l'instant d'arrivée du paquet 601. La figure 7 illustre Nab slots partagés présents dans le délai Dmax à partir de l'instant d'arrivée du paquet 701. 15 Selon une variante de mise en oeuvre du procédé, un noeud va vérifier le taux d'occupation d'un slot partagé et choisir un slot partagé ayant le taux d'occupation le plus élevé pour programmer la transmission d'un paquet. Il est aussi possible d'utiliser un autre critère que le taux d'occupation pour choisir le slot. Par exemple, on pourrait utiliser une valeur 20 seuil et décider de la programmation du slot si le taux d'occupation est supérieur ou inférieur à cette valeur seuil. Dans les exemples donnés ci-avant, une unité de transmission correspond à un slot ou créneau temporel. Sans sortir du cadre de l'invention, toute unité autre que temporelle, permettant la transmission de 25 données dans un système de communication peut être considérée pour la mise en oeuvre du procédé selon l'invention. Par exemple, l'unité peut être un bloc ressource ou RB (Resource Block) comme défini par exemple dans la norme LTE, un code CDMA, un canal FDMA. Il est possible d'envisager une application avec une unité fréquentielle, spatiale ou bien une unité mixte 30 permettant le transport des données dans le système de communication. 3057432 11 Pour des paquets de données présentant une taille supérieure à l'unité de transport prévue par le protocole de transmission de données, un noeud pourra effectuer un prétraitement consistant à scinder le paquet en plusieurs sous-paquets ayant une taille inférieure à l'unité de transmission. 5 Le procédé et le système selon l'invention présentent notamment les avantages suivants : - les slots aléatoires permettent de gérer les situations où certains noeuds ont plusieurs messages à envoyer avant leurs prochains slots dédié ce qui offre plus de flexibilité qu'un accès statique, 10 - les slots dédiés permettent de réduire la charge sur les slots à accès aléatoire et donc de réduire les collisions par rapport à un accès aléatoire pur. Le procédé et le système selon l'invention offrent une meilleure efficacité pour la satisfaction de la qualité de service demandée que celle 15 offerte par les méthodes précitées de l'art antérieur et pour la gestion de l'accès au canal de communication dans un réseau sans fil pour des trafics sporadiques de faibles tailles contraints en délai. REVENDICATIONS1 - Procédé ou protocole d'accès dans un réseau de communication comprenant plusieurs noeuds Mi émetteurs/récepteurs, l'échange de données ou de paquets de données se faisant grâce à un protocole de communication utilisant une unité de communication pour la programmation caractérisé en ce qu'il comporte au moins les étapes suivantes : a) au niveau d'un noeud Mi du réseau, à l'arrivée d'un nouveau paquet de données 1(P) de taille P, mesurer le temps Ts(k) qui sépare l'instant d'arrivée de ce paquet 1(P) des instants d'occurrence t(k) de ses prochains slot dédiés qui sont dans la limite de Dmax avec k étant l'indice de tel slots, k = 1, ..., Ns tel que : Ts (Ns) Dmax, (501) , b) parmi les Ns slots trouvés dans le délai Dmax, déterminer le nombre de slots Nsf qui ont une capacité résiduelle supérieure ou égale à la taille du nouveau paquet de données 1(P), Cr(k) P , o Si le nombre de slots Nsf est positif, alors programmer un slot parmi Nsf pour la transmission des données et mettre à jour l'information sur la capacité résiduelle de ce slot, (503, 504), o Si le noeud ne trouve pas de slot dédié parmi les Ns slots qui présente encore de la place pour la programmation (Nsf=0), alors compter le nombre de slots partagés Nab qui se trouvent dans le créneau temporel défini par la limite maximum de transmission Dmax , qui ont déjà été programmés pour une future transmission, et qui disposent de place pour transporter le nouveau paquet: Nab = Ific, tel que T,(k) Dmax et Cr(k) 0, alors le noeud choisit aléatoirement un slot partagé parmi Nab, programme la 3057432 13 transmission du nouveau paquet au niveau de ce slot partagé et met à jour l'information sur la capacité résiduelle de ce slot, (507), o Si le nombre de slots partagés qui disposent encore de la place pour la programmation est nul, Nab = 0, alors le noeud compte le 5 nombre de slots partagés Naf qui sont dans la limite de Dmax et qui n'ont pas déjà été programmés pour une future transmission: Naf = Itic, tel que Ts(k) Dmax et Cr(k) = Cli, où C est la capacité de transport du slot, (508), o Si le nombre de slots partagés non encore programmés est positif, 10 Naf > 0, alors le noeud choisit aléatoirement un slot partagé parmi Naf, programme la transmission du nouveau paquet au niveau de ce slot partagé et met à jour l'information sur la capacité résiduelle de ce slot, (508), o S'il n'existe aucun slot partagé pour la transmission Naf = 0, alors 15 le nouveau paquet est rejeté, (509). 2 - Procédé selon la revendication 1 caractérisé en ce que l'on choisit de programmer le premier slot dédié disponible pour la transmission du paquet de données 20 3 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'on choisit le slot partagé en utilisant un algorithme de choix aléatoire, de type ALHOA. 25 4 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'on choisit le slot partagé à programmer en fonction du taux d'occupation des slots partagés. 3057432 14 5 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'on partage un paquet de données à transmettre en plusieurs sous- paquets de données, chaque sous-paquet étant traité comme un paquet. 5 6 - Procédé selon l'une des revendications précédentes caractérisé en ce que l'unité de transmission est un créneau temporel. 7 - Système de communication dans un réseau comprenant N noeuds, lesdits N noeuds Mi communiquent entre eux en utilisant un protocole de 10 communication, chaque noeud comprenant au moins un émetteur/récepteur, un processeur adapté à exécuter le procédé d'accès selon l'invention, chaque noeud souhaitant émettre et/ou recevoir des données comporte au moins les modules suivants : o Un module émetteur/récepteur (11i), 15 o Un module de mesure du temps (13i) entre l'instant d'arrivée to d'un paquet de données à émettre et l'instant de démarrage d'une unité de transmission dans un délai maximum à respecter pour une qualité de service requise, o Une table (14i) mémorisant la programmation des slots partagés 20 utilisés pour la transmission de données, o Un algorithme adapté à élire un slot à programmer pour la transmission de données. 8 - Système de communication selon la revendication 7 caractérisé en ce 25 qu'il comporte un algorithme aléatoire pour choisir le slot à programmer pour la transmission de données. 9 - Système de communication selon la revendication 8 caractérisé en ce que l'algorithme de choix du slot dédié est un algorithme tenant compte du 30 taux d'occupation du slot, du nombre de paquets de données déjà programmés sur ce slot.