Brevet FR3076159A1 — publié le 20190628

PROCEDE ET DISPOSITIF D'ALLOCATION DE CANAUX L'invention concerne notamment un procédé et un dispositif permettant d'allouer de manière optimale des canaux pour le partage de données entre plusieurs utilisateurs. Elle s'applique lorsque les utilisateurs sont des postes radios souhaitant échanger leurs positions, par exemple dans un système de communication. Elle trouve son application pour le partage récurrent d'informations entre utilisateurs, en minimisant la période de rafraîchissement correspondant à plusieurs sessions successives io assurant que chaque utilisateur U. puisse communiquer au moins une fois avec chacun des autres utilisateurs U. Pendant une période - dite de rafraîchissement - la plus petite possible, chaque utilisateur doit pouvoir communiquer à tous les autres utilisateurs une donnée personnelle, par exemple, sa position courante. 15 Quand l'environnement des utilisateurs est peu dense, lorsque deux utilisateurs sont en visibilité radio, la solution déterministe la plus simple et la plus efficace consiste à ce que chacun transmette tour à tour sa position. Il est aussi possible d'envisager des émissions rapprochées qui provoqueraient du brouillage en environnement dense et qui auraient une 20 période de rafraîchissement plus courte. La période totale de transmission est égale au nombre d'utilisateurs multiplié par la durée d'un créneau temporel ou slot de transmission. L'expression « visibilité ou en portée radio » signifie qu'un utilisateur est visible au sens radio et qu'il peut échanger des informations avec un autre utilisateur. 25 Dans un contexte dense d'utilisateurs, de nombreux utilisateurs sont en portée radio les uns des autres. Il est alors intéressant d'envisager un relayage coopératif où les utilisateurs transmettent, en plus de leur position, la position des utilisateurs qu'ils ont entendu précédemment, avec lesquels ils ont pu échanger des données. Dans l'optique d'un relayage 30 coopératif, la transmission successive sur un seul canal logique n'est pas pertinente car les utilisateurs, s'ils sont en portée radio, reçoivent les mêmes 2 informations simultanément. Ils ont donc peu ou pas d'informations utiles à transmettre en plus de leur position. La description qui suit fera appel aux termes définis ci-après. Les N utilisateurs émettent et écoutent selon un schéma périodique. La période 5 de ce schéma correspond à une trame ou une période. Les utilisateurs émettent sur C canaux logiques et écoutent les autres utilisateurs utilisant le même canal logique. Les utilisateurs d'un même canal logique émettent successivement sur le canal logique. Les allocations des canaux logiques aux utilisateurs sont modifiées plusieurs fois sur la durée de la trame. On appelle une session, la période pendant laquelle les utilisateurs restent affectés au même canal logique. Les différentes sessions constituant la trame peuvent être de durées différentes. Une période de rafraîchissement est définie comme le cumul des durées des t sessions successives pour assurer que chaque utilisateur U puisse communiquer au moins une fois avec chacun des autres utilisateurs Ui sa donnée personnelle. Pour un cas de doublet particulier, utilisateur, canal, (N, C), il est possible de chercher une solution spécifique en utilisant un solveur pour satisfaire au mieux la contrainte de minimisation de la période de rafraîchissement. On constate que des petites variations sur les paramètres N, C, n (n est de l'ordre de N/C) peuvent accroître considérablement la période minimale trouvée. L'un des objectifs est que le minimum atteint observé reste systématiquement proche de la borne théorique t* « combinatoire », i.e. le plus petit t tel que : t C n(n-1)/2 >= N(N-1)/2. ie t* N2/(n2 C). Une méthode connue consiste à utiliser une règle d'affectation pseudo aléatoire (i.e. tirer des partitions en groupe de n usagers « au hasard » à chaque session). Cette méthode présente l'inconvénient de connecter plusieurs fois les mêmes abonnés au cours des sessions successives constituant la période, et peut laisser au contraire un reliquat de couples d'abonnés sans connexion, qu'il faudra traiter par une ou plusieurs 3 sessions complémentaires particulières. De plus, cette solution est toujours loin de l'optimal désiré. Pour une session, le nombre de paires {i,j} d'utilisateurs connectés (i.e. Ui, Uj sont affectés au même canal) est : C n(n-1)/2. 5 Dans une session, une paire est donc connectée avec la probabilité : p = C n(n-1)/2 /( N(N-1)/2) C (n/N)2. Après t sessions, le nombre de paires toujours non connectées est donc de l'ordre de : (1-p)t N (N-1)/2 - (1 - C (n/N)2)t N2/2. io L'ordre de grandeur de t pour que le nombre de paires toujours non connectées après t sessions soit proche de 0 est donc tel que : t In((1 - C (n/N)2) + ln(N212) = In(1). Soit encore, sous l'hypothèse s = C (n/N)2 - ln(N212) t*. Le facteur multiplicatif « In(N2/2) » (typique du problème classique du « collecteur de coupons ») de la période de rafraîchissement de la solution « pseudo aléatoire » par rapport à la borne minimale t* n'est pas négligeable. L'un des objectifs de l'invention est de proposer une nouvelle approche 20 permettant d'allouer de manière optimale des canaux logiques de transmission, en faisant en sorte que deux utilisateurs quelconques appartenant à un réseau se voient au moins une fois sur la période de la trame et que, sur la durée d'une trame, deux utilisateurs quelconques soient affectés au moins une fois au même canal logique pendant une même 25 session. L'invention concerne un procédé pour allouer des canaux de communication à plusieurs utilisateurs dans un réseau, comportant au moins les étapes suivantes : a) définir un premier ensemble d'allocation composé des triplets suivants 30 (numéro de canal, numéro de slot, utilisateur attribué à un canal pour un siot donné) représentant l'allocation de C canaux de communication, pour les N 4 utilisateurs, sur une session temporelle composée de plusieurs créneaux temporels, en respectant C = e et C=cardinal d'un corps fini, b) générer à partir de la première matrice d'allocation des canaux, C autres 5 matrices, lesdites C matrices d'allocation étant générées en utilisant une fonction afin que chaque utilisateur voit les autres utilisateurs au moins une fois pendant la session. Selon une variante de réalisation l'ensemble d'allocation se présente sous la forme d'une matrice et en ce que la génération d'une io matrice d'allocation à partir de la première matrice d'allocation est obtenue en parcourant les colonnes et les lignes de la matrice en utilisant des droites de pentes variables. Dans le cas où la relation C = V-Ki n'est pas vérifiée, on choisit, par exemple, un nombre d'utilisateurs inactifs et on se ramène à traiter N'>N 15 utilisateurs, actifs ou inactifs, avec C = \Fe et on optimise la position des utilisateurs inactifs pour minimiser la taille de la trame. Dans le cas où le nombre de canaux disponibles est inférieur à la racine carré du nombre d'utilisateurs, on regroupe les utilisateurs en sous-groupes d'au plus k utilisateurs avec (k-1)*q2 infini, { (x,y) dans E, y = a(k) x + b(i) } 10 - si a(k) = infini, {(x,y) dans E , x = b(i)} Avec cette affectation, chaque utilisateur est connecté une fois et une seule fois avec un autre pendant les t = q+1 sessions. En effet, les q+1= sessions utilisent toutes les (q2+q) droites possibles, et par deux points ne 5 passe qu'une seule droite. Cette affectation est illustrée en figure 2 sur laquelle on a représenté deux matrices d'allocation de canaux où les colonnes correspondent à un slot, les lignes à des canaux à allouer, et le contenu de la matrice le numéro d'un utilisateur ou d'un groupe d'utilisateurs, couple, 10 triplet, par exemple. La première matrice M1 correspond à une droite de pente nulle (matrice de référence). La deuxième matrice M2 a été générée en parcourant la première matrice avec une droite de pente non nulle (pente 1). La figure 3 représente un exemple chiffré dans lequel on a représenté pour des soucis de clarté uniquement trois matrices, sur les douze. La 15 troisième matrice M12 est générée avec une pente infinie. Le procédé génère ainsi C+1 matrices d'allocation de canaux pour les utilisateurs. Cette variante de construction des matrices d'allocation de canaux est définie pour les cas de doublets (N, C) de la forme (q2, q) où q est le cardinal d'un corps fini (i.e., un nombre de la forme pk, p premier, k >= 1). 20 Selon une variante de réalisation, pour s'adapter aux cas où le nombre d'utilisateurs et/ou le nombre de canaux n'est pas idéal, deux techniques vont être explicitées. La première technique permet de s'adapter à un nombre d'utilisateurs qui n'est pas égal au carré du cardinal d'un corps fini. On 25 considère que le nombre d'utilisateurs est égal à N. Soit q le plus petit nombre adéquat (cardinal corps fini) tel que q2N (et q2 est différent N). Le principe est de considérer q2=N'>N utilisateurs pour la loi d'affectation et avec q2-N utilisateurs qui sont inactifs (ou virtuels). Si rien n'est optimisé, la période de la transmission complète est q*(q+1), si on 30 considère qu'une session de q utilisateurs a une durée égale à q. Il est possible, si N est sensiblement inférieur à q2, d'optimiser la durée. 11 Pour cela, si on a au moins k*q (k>=1) utilisateurs inactifs (i.e. : q2_ k*q N > q2_ (k+1)*q), on choisit de façon optimale les utilisateurs inactifs pour diminuer la période totale. Pour cela, on affecte sur une même session (la dernière), les k*q utilisateurs inactifs à k canaux logiques. Ces canaux 5 logiques ne contiennent que ces k*q utilisateurs inactifs. Cela revient à choisir, comme utilisateurs inactifs, des utilisateurs se trouvant sur le même canal logique lors de la dernière session de la période. Les q autres sessions contiennent au plus q-k utilisateurs par canal logique (les utilisateurs d'un canal logique sur une session se 10 répartissent sur tous les canaux logiques pour chacune des autres sessions), ce qui permet de diminuer de k la durée des autres sessions. La durée de trame (ou période) est donc de q+q*(q-k)=q*(q-k+1). Un exemple chiffré est donné ci-après. Soit N=110 utilisateurs, on prend q=11. q2=121. Il y a 11 canaux inactifs. On prend une loi sur les 15 canaux logiques aboutissant à 12 sessions de taille 11. Sur une session (par exemple la dernière), les utilisateurs du dernier canal logique sont inactifs. Les autres sessions n'ont que 10 utilisateurs pour chaque canal logique et ont donc une durée réduite à 10. La durée de la période peut donc être réduite à 10 pour chacune des 11 premières sessions et 11 pour la dernière 20 session soit 121 (au lieu de 132). La figure 4 indique les matrices correspondant à cette solution (seules 3 des matrices ont été représentées : les deux premières et la dernière). On gagne donc sur la durée de la période à chaque fois qu'il y a un multiple de 11 utilisateurs inactifs. Le gain se fait donc par palier (on aurait eu la même période totale avec 100 utilisateurs). 25 Cela revient à considérer les utilisateurs 0 à 109 sur la figure 3: pour les 11 premières matrices, les lignes sont de longueur 10. Une seconde technique permet de s'adapter dans le cas où le nombre de canaux logiques disponibles est insuffisant. On a q canaux logiques disponibles et le nombre d'utilisateurs est N>q2. On peut regrouper 30 les utilisateurs en groupes d'au plus k utilisateurs tels que (k-1)*q2 REVENDICATIONS1 - Procédé pour allouer des canaux de communication à plusieurs utilisateurs dans un réseau, comportant au moins les étapes suivantes : a) définir un premier ensemble d'allocation composé des triplets suivants (numéro de canal, numéro de slot, utilisateur attribué à un canal pour un slot donné) représentant l'allocation de C canaux de communication, pour les N utilisateurs, sur une session temporelle composée de plusieurs créneaux temporels, en respectant io C = V7 et C=cardinal d'un corps fini, b) générer à partir de la première matrice d'allocation des canaux, C autres matrices, lesdites C matrices d'allocation étant générées en utilisant une fonction afin que chaque utilisateur voit les autres utilisateurs au moins une fois pendant la session. 15 2 - Procédé selon la revendication 1 caractérisé en ce que l'ensemble d'allocation se présente sous la forme d'une matrice et en ce que la génération d'une matrice d'allocation à partir de la première matrice d'allocation est obtenue en parcourant les colonnes et les lignes de la 20 matrice en utilisant des droites de pentes variables. 3 - Procédé selon l'une des revendications 1 ou 2 caractérisé en ce que dans le cas où la relation C = el n'est pas vérifiée, on choisit un nombre d'utilisateurs inactifs et on se ramène à traiter N'>N utilisateurs, actifs ou 25 inactifs, avec C = ire et on optimise la position des utilisateurs inactifs pour minimiser la taille de la trame. 4 - Procédé selon l'une des revendications 1 à 3 caractérisé en ce que dans le cas où le nombre de canaux disponibles est inférieur à la racine carré du 30 nombre d'utilisateurs, on regroupe les utilisateurs en sous-groupes d'au plus 16 k utilisateurs avec (k-1)*q2 5 - Procédé selon la revendication 4 caractérisé en ce qu'un groupe 5 d'utilisateurs est composé de plusieurs sous-ensembles d'utilisateurs, tels que des couples, des triplets et/ou des utilisateurs seuls. 6 - Procédé pour le partage de données entre plusieurs utilisateurs comprenant l'étape d'allocation des canaux de communication selon l'une io des revendications 1 à 5 et une étape où les utilisateurs s'échangent leurs positions et les positions de leurs voisins en portée radio. 7 - Procédé selon la revendication 6 caractérisé en ce que les utilisateurs sont des postes radios. 15 8 - Dispositif pour allouer des canaux de communication à plusieurs utilisateurs Ui dans un réseau, caractérisé en ce qu'il comporte un dispositif (30) configuré pour exécuter les étapes du procédé selon l'une des revendications 1 à 7, des moyens de stockage de l'ensemble comportant 20 l'allocation des canaux C en fonction d'un slot S et pour un utilisateur. 9 - Dispositif selon la revendication 8 caractérisé en ce que chaque utilisateur est équipé d'un processeur (12i) configuré pour exécuter les étapes du procédé selon l'une des revendications 1 à 7. 25 - Dispositif selon l'une des revendications 8 ou 9 caractérisé en ce qu'un utilisateur est un poste radio et le réseau est un réseau de communication ad-hoc.