Brevet FR2803465A1 — publié le 20010706

La présente invention concerne une méthode d'accès aléatoire à une ressource partagee entre plusieurs utilisateurs. Plus particulièrement, l'invention concerne une méthode d'accès de type ALOHA et de préférence de typ ALOHA discrétisé (dit aussi Slotted ALOHA). Lorsque plusieurs utilisateurs partagent une même ressource (LAN, bande de fréquences radioélectriques ou satellitaires, trames par exemple), il faut définir des règles permettant à chaque utilisateur d'accéder à la ressource dans des conditions au mieux compatibles avec ses besoins de transmission. Il existe deux grandes familles de méthodes d'accès permettant de réaliser un tel partage: méthodes d'accès avec réservations dans lesquelles la ressource fait l'objet d'une répartition préalable en fonction des besoins de chaque utilisateur et les méthodes d'accès aléatoires dans lesquelles chaque utilisateur émet à son gré sans concertation préalable avec les autres, conflits d'accès étant alors gérés a posteriori. La Fig. 1 illustre un exemple de système dans lequel canal de transmission (RACH) est partagé entre plusieurs utilisateurs Ul, UZ ,... U,1 transmettant des paquets de données à un système S selon une méthode d'accès aléatoire. Lorsque le système reçoit un paquet de données, il vérifie son intégrité (par exemple grâce à une méthode de détection d'erreurs) et renvoie dans l'affirmative un accusé de réception sur un canal de contrôle (CC). La Fig. 2 donne un chronogramme simplifié du dialogue entre un utilisateur U; et le système S. L'utilisateur U; émet un paquet à l'instant L'intégrité des données est vérifiée à la réception par le système S et, dans l'affirmative, un accusé de réception est renvoyé par le système. Il est reçu par l'utilisateur Ui un temps TACK après l'émission. En revanche, si le paquet (émis à l'instant t3) est détecté comme corrompu par le système S, parce qu'il a subi par exemple une collision avec un paquet émis par un autre utilisateur, l'absence d'accusé de réception est détectée par l'utilisateur au bout du temps TACK et le paquet est émis a nouveau après un temps TRetransmit. D'autres techniques permettant la vérification de l'intégrité de la transmission sont également connues, notamment la technique CSMA/CD (Carrier Sense Multiple Access with Collision Detection) ne nécessitant pas d'accusé de réception sur un canal de contrôle. Selon cette technique, l'utilisateur écoute le canal partagé avant de transmettre et poursuit son écoute pendant la transmission. S'il se produit une collision, la transmission du paquet est avortée et une nouvelle transmission est tentée ultérieurement. Cette technique nécessite en revanche un circuit de détection d'interférence pour chaque utilisateur. Une méthode bien connue d'accès aléatoire à une ressource partagée est le protocole ALOHA. Selon une première version que l'on dénommera ALOHA purement aléatoire, chaque utilisateur émet à son gré et à un instant de transmission quelconque. Une séquence de transmission selon ce protocole est illustrée à la Fig. 3. Lorsque les paquets émis par deux utilisateurs quelconques U; et Uj se chevauchent, il y a collision (C) et les paquets collisés sont réémis ultérieurement après des retards respectifs TR; et TRj. d'éviter une répétition de collisions, et donc une situation de blocage (phénomène connu sous le nom de persistance dynamique), les retards de retransmission sont choisis distincts pour les différents utilisateurs. Plus précisément, chaque utilisateur dispose en propre d'une variable aléatoire fournissant ce retard ces variables aléatoires étant choisies de manière à présenter des moyennes différentes. Selon une seconde version, dite ALOHA discrétisée, des intervalles de transmission (slots) se répètent de manière périodique et les utilisateurs peuvent émettre ' leur gré à condition de respecter les intervalles de transmission. Les utilisateurs de la ressource partagée doivent synchroniser leurs instants d'émission. On montre cette contrainte permet d'obtenir une capacité de transmission double de celle du protocole ALOHA purement aléatoire. Une séquence de transmission selon le protocole ALOHA discrétisé est illustrée à la Fig. 4. Une collision (C) sur le canal RACH produit lorsque deux utilisateurs émettent pendant le même intervalle. La collision est alors complète et les paquets collidés doivent être réémis ultérieurement. Comme dans le cas précédent, les retards de retransmission sont fournis par des variables aléatoires de moyennes distinctes, et ce, afin de réduire la persistance dynamique. Les variables aléatoires doivent être aussi à valeurs discrètes dans (k*T,,,), k est entier et Tre# est la période de récurrence des intervalles de transmission maniere à ce qu'une retransmission coïncide avec un intervalle. La Fig. 5 représente un organigramme de fonctionnement d'un utilisateur accédant à une ressource partagée suivant le protocole ALOHA. Partant de son état de repos (50), l'utilisateur teste périodiquement (51) si un paquet de données est à transmettre. Si c'est le cas, une première variable aléatoire fournit (52) un instant de transmission TTra"S",it (à valeurs dans (k*Trz,) dans le cas de l'ALOHA discrétisé). L'utilisateur émet (53) à l'instant TT.it le paquet de données sur le canal partagé et attend l'accusé de réception. S'il est reçu (54), l'utilisateur retourne à son état de repos. Sinon il est conclu (54) à une collision et une seconde variable aléatoire fournit (55) un temps de retard TRd,. ;t (également à valeurs dans (k*T,,,) dans le de l'ALOHA discrétisé) au terme duquel il sera procédé à une nouvelle tentative de transmission (56). La politique d'accès aléatoire à une ressource partagée peut être aménagée le sens de la réservation et ceci pour différentes raisons. Tout d'abord, il se peut que les utilisateurs doivent effectuer des opérations parallèle à transmission. Dans certains cas, par exemple lorsque l'utilisateur doit utiliser ses ressources de transmission/ réception pour effectuer des mesures de paramètres sur le réseau ou d'autres réseaux d'accès, ces opérations sont exclusives de l'accès au canal partagé ou, le cas échéant, de la lecture des accusés de réception sur le canal de contrôle. Des plages temporelles sont alors réservées, plages dans lesquelles l'accès à la ressource partagée est interdit à l'utilisateur afin de le libérer pour des tâches prioritaires. Si l'accès se fait selon le protocole ALOHA discrétisé, les plages temporelles réservées pourront être des intervalles de transmission. Il se peut aussi qu'un utilisateur ait des besoins de transmission ou jouisse d'une priorité justifiant une réservation temporaire ou permanente d'une partie de la ressource. L'utilisateur ainsi privilégié pourra alors accéder à la ressource dans plages temporelles réservées, les autres utilisateurs étant exclus de tout accès aléatoire dans ces plages. Dans les deux cas de réservation exposés ci-dessus, tous les utilisateurs la ressource connaissent à l'avance les plages auxquelles ils ne peuvent accéder. Ces plages réservées perturbent toutefois le régime de l'accès aléatoire, et notamment la résolution la persistance dynamique. En effet, même pour une densité de plages réservées relativement faible, les instants de transmission/ retransmission obtenus par tirage des variables aléatoires peuvent tomber, éventuellement de manière répétée, à l'intérieur ces plages. II peut alors être tentant pour un utilisateur de s'écarter des valeurs obtenues par tirage de ses variables aléatoires. Ceci introduirait cependant un biais modifiant de manière incontrôlée les propriétés statistiques de l'accès à ressource et, en particulier, ne garantirait plus que le système sorte rapidement d'une situation de collision à répétition. La présente invention a pour but de permettre un contrôle du trafic et résolution de la persistance dynamique dans des systèmes à accès aléatoire avec réservation de plages temporelles. Ce but est atteint par une modification temporaire des variables aléatoires donnant instants de transmission/ retransmission en des variables aléatoires même moyenne mais de plus grande variance. Avantageusement, la violation de la réservation est établie lorsque l'instant de transmission du paquet de données tombe dans une plage temporelle réservée. Mais, elle peut etre aussi établie lorsque l'accusé de réception du paquet de données est attendu dans une plage temporelle réservée. Le protocole ALOHA est avantageusement un protocole ALOHA discrétisé les plages temporelles réservées sont des intervalles de transmission. Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres apparaîtront plus clairement à la lecture de la description suivante d'un exemple réalisation ladite description étant faite en relation avec les dessins joints, parmi lesquels la 1 représente le schéma de principe d'un système d'accès aléatoire à ressource partagée entre plusieurs utilisateurs; la Fig. 2 représente un chronogramme de transmission dans le système de la Fig. 1, la Fig. 3 représente une séquence de transmission selon le protocole ALOHA purement aléatoire, la Fig. 4 représente une séquence de transmission selon le protocole ALOHA discrétisé, la Fig. 5 représente un organigramme de fonctionnement d'un utilisateur selon un protocole de type ALOHA, la Fig. 6 représente une séquence de transmission utilisant une méthode d'accès aléatoire selon l'invention, la Fig. 7 représente un organigramme de fonctionnement d'un utilisateur utilisant méthode d'accès aléatoire selon l'invention. se placera à nouveau dans l'hypothèse d'une ressource partagée par plusieurs utilisateurs comme illustrée à la Fig. 1 et décrite plus haut. L'accès des utilisateurs à la ressource se fait suivant un mode aléatoire et par paquets. Pour un utilisateur donné, certaines plages temporelles sont réservées, soit parce qu'il doit effectuer des tâches particulières pendant ces plages (mesures sur le réseau, par exemple), soit parce qu'un utilisateur privilégié a réservé une partie de la ressource. La réservation peut être temporaire ou définitive, mais on supposera que chaque utilisateur connait ' l'avance (ou encore reçoit par le système) le programme des plages pendant lesquelles il ne peut accéder à la ressource. La Fig. 6 montre un exemple de séquence de transmission en présence plages réservées utilisant un protocole ALOHA discrétisé et modifié selon l'invention. Les plages réservées à considérer pour l'utilisateur Ui sont données par la ligne Ri pendant les plages notées (M), l'utilisateur Ui doit effectuer des tâches prioritaires, pendant les plages notées (X), un utilisateur privilégié interdit l'accès à la ressource. La ligne Ui indique les tentatives de transmission de paquets de données par l'utilisateur Ui. La ligne Uj indique les paquets transmis par l'utilisateur Uj et la ligne ACK les accusés de réception renvoyés par le système sur le canal de contrôle. Les tâches effectuées par l'utilisateur Ui sont représentées sur la ligne Ti. Les intervalles notés (T) correspondent à une transmission non collidée, (C) à une transmission collidée (M) â une tâche prioritaire. Lorsqu'un paquet est à transmettre, l'utilisateur Ui lui attribue un instant de transmission TT,.S,nir fourni par sa première variable aléatoire. Deux cas peuvent alors se présenter: si l'instant attribué est compatible avec la réservation, le paquet est émis à cet instant; si, en revanche, l'instant attribué viole la réservation, soit parce qu'il tombe dans une plage réservée (X ou M), soit encore parce que l'accusé de réception correspondant serait reçu au cours de l'exécution d'une tâche prioritaire le paquet ne peut etre transmis à l'instant attribué. Il est alors procédé, selon l'invention, à une modification temporaire de la (première) variable aléatoire en une variable aléatoire de même moyenne et de plus grande variance. La moyenne inchangée assure un contro des performances par le système, et la plus grande variance permet d'atteindre des valeurs d'instant de transmission ne violant plus la réservation. La valeur aléatoire modifiée fournit un nouvel instant de transmission qui est nouveau testé. nouvel instant conduit à nouveau à une violation, l'étape de modification est itérée. Selon un mode de réalisation avantageux, la modification s'effectue addition d'une variable aléatoire centrée et de loi donnée (discrète pour l'ALOHA discrétisé et continue pour l'ALOHA purement aléatoire). Reprenant l'exemple de la Fig. 6, la première variable aléatoire de Ui ayant fourni la valeur t16 pour la transmission d'un paquet et cet instant violant la réservation (tâche prioritaire (M)), la variable aléatoire est modifiée et un nouveau tirage est effectué. Le nouvel instant obtenu violant à nouveau la réservation pour la même raison, l'étape précédente est répétée. L'instant obtenu t19 ne violant pas la réservation, le paquet est transmis à cet instant. Lorsque le paquet de données est émis à un instant de transmission compatible avec la réservation (éventuellement après modification de la première variable aléatoire comme indiqué ci-dessus), il peut néanmoins encore subir une collision. La collision est détectée par l'utilisateur, par exemple si aucun accusé de réception n'est reçu pendant un temps donné TACx. . Si le paquet a été collidé, il est nécessaire de le retransmettre au bout d'un temps TR@,.a"s,r,ir après sa première transmission, le retard TR,t,,,,.smit étant fourni par une seconde variable aléatoire. L'instant de retransmission ainsi obtenu doit être testé pour vérifier sa compatibilité avec la réservation, Si c'est le cas le paquet est retransmis à l'instant obtenu ; sinon, il est procédé, selon l'invention, à une modification temporaire de la seconde variable aléatoire en une variable aléatoire de même moyenne et de plus grande variance. Comme plus haut, si le nouvel instant conduit à nouveau à une violation, l'étape de modification est itérée. La modification peut de la même façon être effectuée par addition d'une variable aléatoire centrée de loi donnée (discrète pour l'ALOHA discrétisé et continue pour l'ALOHA purement aléatoire). Chaque utilisateur garde ainsi une valeur moyenne de TR,tra"S",i Reprenant l'exemple de la Fig. 6, le paquet transmis en t6 étant collidé, un premier retard TRetra,s",i Le fonctionnement d'un utilisateur selon la méthode de l'invention est repris schématiquement dans l'organigramme la Fig. 7. Partant de son état de repos (700), l'utilisateur teste périodiquement (701) si un paquet de données est à transmettre. Si c'est le cas, la première variable aléatoire de l'utilisateur fournit (702) un instant de transmission TTT,,smrt. Cette valeur est testée (703) pour vérifier sa compatibilité avec la réservation. Dans la négative, la première variable aléatoire est modifiée (704) et nouvel instant de transmission TTr,,ns,,,h obtenu (704) est soumis à nouveau au test de compatibilité (703). Dans le cas contraire, l'utilisateur émet (705) à TT,,,"S"ùt le paquet de données sur la ressource partagée et attend l'accusé de réception. est reçu (706), l'utilisateur retourne à son état de repos. Sinon, il est conclu (706) à une collision et la seconde variable aléatoire fournit (711) un temps de retard TRt,a"S",â. L'instant de retransmission correspondant est testé (711) pour vérifier sa compatibilité avec la réservation. Dans la négative, la seconde variable aléatoire est modifiée (7 et un nouveau temps de retard est obtenu (712). L'instant de transmission correspondant est à son tour soumis au test de compatibilité (712). Si l'instant est compatible, l'utilisateur réémet (713) le paquet à cet instant puis attend l'accusé de réception. Dans la description ci-dessus la modification des variables aléatoires est temporaire. Elles peuvent retourner à leur initiale après un certain laps de temps ou un certain nombre de tirages afin d'assurer une stationnarité minimale. Les variables aléatoires sont en quelque sorte à variance élastique en fonction des contraintes de réservation. REVENDICATIONS 1) Méthode d'accès aléatoire d'un utilisateur à une ressource partagée selon un protocole de type ALOHA, l'instant de transmission d'un paquet de données par l'utilisateur étant fourni par au moins une variable aléatoire dans laquelle certaines plages temporelles d'accès à la ressource ont fait l'objet de réservation préalable, caracterisée en ce que ladite variable aléatoire est temporairement modifiée une variable aléatoire de même moyenne et de plus grande variance lorsque la transmission audit instant aboutirait à une violation de la réservation. Méthode d'accès aléatoire selon la revendication 1, caractérisée en ce la violation de la réservation est établie lorsque l'instant de transmission du paquet de données tombe dans une plage temporelle réservée. Méthode d'accès aléatoire selon la revendication 2, caractérisée en ce la violation de la réservation est aussi établie lorsque l'accusé de réception du paquet de données est attendu dans une plage temporelle réservée. Méthode d'accès aléatoire selon la revendication 2 ou 3, caractérisée en ce que le protocole ALOHA est un protocole ALOHA discrétisé et que les plages temporelles réservées sont des intervalles de transmission. 5) Méthode d'accès aléatoire selon l'une des revendications 1 à 4, caracterisée en ce qu'une première variable aléatoire fournit un premier instant de transmission (TTra",Smn)et que la première variable aléatoire est temporairement modifiée une variable aléatoire de même moyenne et de plus grande variance lorsque la transmission au premier instant aboutirait à une violation de la réservation. 6) Méthode d'accès aléatoire selon la revendication 5, caractérisée en que l'étape de modification de la première variable aléatoire consiste à lui ajouter une variable aléatoire centrée. Méthode d'accès aléatoire selon la revendication 6, caractérisée en ce si l'instant de transmission fourni par la première variable aléatoire telle que modifiée viole réservation, l'étape d'addition de la variable aléatoire centrée est itérée jusqu'à ce que l'instant de transmission fourni par la première variable aléatoire soit compatible avec la réservation. 8) Méthode d'accès aléatoire selon l'une des revendications 5 à 7, caractérisée en ce qu'une seconde variable aléatoire (TRe.,.ansn,it) fournit un second instant de transmission si le paquet transmis au premier instant est collidé et que la seconde variable aléatoire est temporairement modifiée en une variable aléatoire de même moyenne et de plus grande variance lorsque la transmission au second instant aboutirait à une violation de la réservation. 9) Méthode d'accès aléatoire selon la revendication 8, caractérisée ce que l'étape modification de la seconde variable aléatoire consiste à lui ajouter une variable aléatoire centrée. 10) Méthode d'accès aléatoire selon la revendication 9, caractérisée ce que, si l'instant transmission fourni par la seconde variable aléatoire telle que modifiée viole la réservation, l'étape d'addition de la variable aléatoire centrée est itérée jusqu'à que l'instant de transmission fourni par la seconde variable aléatoire soit compatible avec la réservation. 11) Méthode d'accès aléatoire selon l'une des revendications précédentes, caractérisée en ce que l'utilisateur effectue une mesure dans l'une au moins des plages temporelles réservées, par exemple réservées à la mesure de paramètres sur le réseau ou d'autres réseaux d'accès. 12) Méthode d'accès aléatoire selon l'une des revendications précédentes, caractérisée en ce que l'utilisateur est un poste mobile.