Brevet FR2834597A1 — publié le 20030711

PROCÉDÉ ET DISPOSITIF POUR ÉTABLIR DES LIAISONS DE COMMUNICATION ENTRE DES SYSTÈMES DE COMMUNICATION MOBILES La présente invention concerne le domaine de la transmission, et plus particulièrement, un réseau de systèmes de communication mobiles fonctionnant avec des antennes directionnelles. L'accès multiple temporel (TDMA) est un exemple de schéma d'accès utilisé pour établir des liaisons de communication entre des systèmes de communication mobiles sans fil. Les liaisons de communication entre les systèmes de communication mobiles sans fil sont établies à l'intérieur d'une série de trames temporelles. Chaque trame temporelle est divisée en tranches de temps, chaque système de communication mobile sans fil recevant au moins une tranche de temps. Une antenne omni-directionnelle est utilisée typiquement par un système de communication mobile sans fil de telle sorte que les informations transmises par un système de communication mobile sont reçues par tous les autres systèmes de communication mobiles. Lorsque les systèmes de communication mobiles opèrent à une fréquence fixe, ils doivent transmettre à tour de rôle à l'intérieur de leurs tranches de temps respectives pour empêcher une interférence entre les canaux. Pour améliorer la qualité d'une liaison de communication entre deux systèmes de communication sans fil, une antenne directionnelle peut être utilisée. L'antenne directionnelle fournit un gain d'antenne accru dans une zone désirée qui est limitée en couverture tout en réduisant le gain d'antenne de la zone restante. Le brevet US n 5 767 807 de Pritchett décrit un système d'antennes phasé utilisé pour établir des liaisons de communication à l'intérieur d'un réseau de systèmes de communication sans fil. Le dispositif d'antenne phasé inclut des éléments parasites pour contrôler sélectivement la structure d'antenne. Le dispositif d'antenne phasé émet un signal omnidirectionnel lorsque la totalité des éléments parasites sont dans un état d'impédance supérieur, et émet un signal directionnel lorsqu'un nombre sélectionné d'éléments parasites sont placés dans un état d'impédance inférieur en réponse aux circuits de commutation. Plus particulièrement, le brevet'807 de Pritchett décrit l'acquisition, par un système de communication sans fil initiateur fixe à partir d'un système de communication sans fil récepteur fixe, d'une liste des systèmes de communication sans fil fonctionnant dans le réseau et d'une liste de tranches de temps respectives correspondante pour chaque système de communication sans fil. Une table est ensuite créée en fonction de la liste pour planifier les tranches de temps entre les systèmes de communication sans fil. Cependant, il existe toujours un besoin de planifier efficacement les tranches de temps pour les systèmes de communication sans fil fonctionnant avec des antennes directionnelles, particulièrement lorsque les systèmes de communication sans fil sont mobiles. Dans un tel réseau dynamique, les systèmes de communication mobiles entrent et sortent continuellement du réseau. Compte tenu de l'arrière-plan précédent, c'est donc un objet de la présente invention de planifier les tranches de temps d'une manière qui soit réactive aux variations des demandes de liaisons de communications pour systèmes mobiles sans fil. Ces objets, avantages et caractéristiques, ainsi que d'autres, selon la présente invention, sont fournis par un réseau de communication sans fil comprenant une pluralité de noeuds mobiles comprenant chacun un émetteur/récepteur, une antenne directionnelle connectée à l'émetteur/récepteur, et un contrôleur connecté à l'émetteur/récepteur. Le contrôleur planifie de manière préférée une tranche de temps semipermanente respective pour chaque trame temporelle pour établir une liaison de communication avec chaque noeud mobile avoisinant et laisse au moins une tranche de temps disponible dans chaque trame temporelle, et planifie la au moins une tranche de temps disponible pour servir également la liaison de communication avec un noeud mobile avoisinant en fonction de la demande de liaisons de communication. Le contrôleur dirige de manière préférée l'antenne directionnelle vers chaque noeud mobile avoisinant lors d'une communication avec celui-ci. L'antenne directionnelle peut être un système d'antennes phasé, une parabole ou des antennes à cornet, par exemple. L'utilisation d'antennes directionnelles focalise un signal HF dans une direction désirée. En conséquence, une pluralité de liaisons de communication peuvent être établies à l'intérieur d'une tranche de temps semipermanente planifiée, chaque liaison de communication incluant une paire différente de noeuds mobiles avoisinants. Chaque trame temporelle peut comporter jusqu'à N tranches de temps semi-permanentes et au moins 2N-1 tranches de temps disponibles. Un avantage lié au fait de limiter le nombre de tranches de temps semipermanentes est de simplifier la planification des tranches de temps. Le contrôleur peut affecter des niveaux de priorité aux liaisons de communication et éliminer une des liaisons de communication en fonction des niveaux de priorité pour rendre disponible une tranche de temps semi-permanente afin d'établir une liaison de communication avec un nouveau noeud mobile avoisinant. De plus, le contrôleur peut également affecter des niveaux de priorité aux liaisons de communication et planifier la au moins une tranche de temps disponible en fonction de ces niveaux de priorité. En d'autres termes, la planification des tranches de temps semi-permanentes est effectuée de manière distribuée. Une paire de noeuds mobiles avoisinants du réseau est capable de s'accorder sur une tranche de temps semi-permanente planifiée sans avoir à communiquer avec les autres noeuds mobiles. En conséquence, il n'existe pas un seul point de défaillance dans la planification des tranches de temps semi-permanentes à travers le réseau, puisque toute paire de noeuds mobiles ne compte pas sur les tranches de temps semi-permanentes affectées entre les autres noeuds avoisinants. Le contrôleur peut planifier une des tranches de temps semi-permanentes comme tranche de temps disponible si le nombre des liaisons de communication est inférieur à N. Ceci permet de gérer de manière avantageuse les demandes de liaisons de communication sur une base'selon les nécessités'pour les liaisons de communication existantes. Cependant, le contrôleur peut re-affecter la tranche de temps affectée à la demande à une tranche de temps semi-permanente si le nombre des liaisons de communication est à nouveau égal à N. Chaque liaison de communication est formée par un noeud mobile initiateur et un noeud mobile récepteur, et le noeud mobile initiateur peut transmettre une liste de tranches de temps semi-permanentes disponibles au noeud mobile récepteur. Le noeud mobile récepteur peut ensuite transmettre la sélection d'une des tranches de temps semi-permanentes au noeud mobile initiateur. Le noeud mobile initiateur peut ensuite confirmer la sélection de la tranche de temps semi-permanente sélectionnée au noeud mobile récepteur. Chaque noeud mobile peut comprendre en outre une antenne omni-directionnelle connectée à l'émetteur/récepteur pour échanger des informations positionnelles avec d'autres noeuds mobiles avoisinants. En outre, le dispositif d'antenne phasé peut générer simultanément plusieurs faisceaux d'antenne, dans lesquels le contrôleur dirige de manière préférée le dispositif d'antenne phasé vers plusieurs noeuds mobiles avoisinants à l'intérieur d'une tranche de temps semipermanente planifiée. Un autre aspect de la présente invention concerne un procédé pour établir des liaisons de communication pour une pluralité de noeuds mobiles, chaque noeud mobile comprenant un émetteur/récepteur, un dispositif d'antenne phasé connecté à l'émetteur/récepteur, et un contrôleur connecté à l'émetteur/récepteur. Le procédé comprend de manière préférée pour chaque noeud mobile la planification d'une trame de temps semi-permanente respective pour chaque trame temporelle pour établir une liaison de communication avec un noeud mobile avoisinant et laisser au moins une tranche de temps disponible dans chaque trame temporelle. La au moins une tranche de temps disponible est planifiée de manière préférée pour servir la liaison de communication avec un noeud mobile avoisinant en fonction de la demande de liaisons de communication. Le dispositif d'antenne phasé est dirigé de manière préférée vers chaque noeud mobile avoisinant lors d'une communication avec celui-ci. Chaque trame temporelle peut avoir jusqu'à N tranches de temps semi-permanentes et au moins 2N-1 tranches de temps disponibles. Le procédé peut inclure en outre la possibilité pour chaque noeud d'affecter des niveaux de priorité aux liaisons de communication et d'éliminer une des liaisons de communication en fonction des niveaux de priorité afin de rendre disponible une tranche de temps semi-permanente pour établir une liaison de communication avec un nouveau noeud mobile avoisinant. Ceci permet avantageusement à tout noeud mobile de répondre aux variations des demandes de liaisons de communication. La figure 1 est un diagramme illustrant un réseau de systèmes de communication mobiles selon la présente invention. La figure 2 est un schéma de principe plus détaillé illustrant une paire de systèmes de communication mobiles sans fil selon la présente invention. La figure 3 est un diagramme illustrant une trame de tranches de temps selon la présente invention. La figure 4 illustre la planification de tranches de temps disponibles du diagramme de réseau illustré sur la figure 2, selon la présente invention. La figure 5 est un diagramme d'état de niveau supérieur pour la planification de tranches de temps semi-permanentes et de tranches de temps disponibles selon la présente invention. La figure 6 est un diagramme illustrant un processus de planification de tranches de temps semipermanentes selon la présente invention. La figure 7 est un diagramme illustrant une tranche de temps semi-permanente planifiée pour une nouvelle liaison de communication selon la présente invention. La figure 8 est un diagramme illustrant un processus de planification de tranches de temps disponibles selon la présente invention. La figure 9 est un diagramme illustrant une tranche de temps disponible ajoutée à une liaison de communication selon la présente invention. Les figures 10 et 11 sont des diagrammes illustrant une tranche de temps semi-permanente planifiée pour une nouvelle liaison de communication en fonction de plusieurs faisceaux d'antenne simultanés provenant d'un dispositif d'antenne phasé selon la présente invention. La présente invention sera à présent décrite plus en détail ci-après en référence aux dessins annexés sur lesquels les modes de réalisation préférés de l'invention sont représentés. Cette invention peut, cependant, être mise en oeuvre sous plusieurs formes différentes et ne doit pas être considérée comme étant limitée aux modes de réalisation présentés ici. Ces modes de réalisation sont plutôt fournis pour que cette description soit exhaustive et complète, et traduise la portée de l'invention à l'homme du métier. Des numéros identiques référencent les mêmes éléments dans tout le document et les premières notations sont utilisées dans les autres modes de réalisation. Les dimensions des couches et des régions peuvent être exagérées dans les figures, pour plus de clarté. En référence initialement aux figures 1-2, un réseau de communication mobile sans fil 10 comprend une pluralité de noeuds mobiles sans fil 12a-12h. Chaque noeud mobile 12a-12h comprend un émetteur/récepteur 14, une antenne directionnelle 16 connectée à fémetteur/récepteur, et un contrôleur 18 connecté à l'émetteur/récepteur. Le contrôleur 18 inclut une unité de tranches de temps semi-permanentes 18a pour planifier une tranche de temps semi-permanente respective pour chaque trame temporelle afin d'établir une liaison de communication avec chaque noeud mobile avoisinant tout en laissant au moins une tranche de temps disponible dans chaque trame temporelle. Une unité de tranches de temps disponibles 18b planifie la au moins une tranche de temps disponible pour servir également la liaison de communication avec un noeud mobile avoisinant en fonction de la demande de liaisons de communication. En outre, le contrôleur 18 inclut une unité de direction d'antenne 18c pour diriger l'antenne directionnelle vers chaque noeud mobile avoisinant lors d'une communication avec celui-ci. Les noeuds mobiles sans fil 12a-12h fonctionnent dans un environnement mobile. Ces systèmes peuvent être basés au sol et/ou aéroportés, grâce à quoi ils entrent et ils sortent continuellement du réseau 10. L'antenne directionnelle 16 peut être un système d'antennes phasé, une parabole ou des antennes à cornet, par exemple. La transmission par l'intermédiaire d'une antenne directionnelle 16 permet de focaliser le signal HF dans une direction désirée. En contrôlant sélectivement la direction de la structure d'antenne entre une paire de systèmes de communication mobiles sans fil pour établir une liaison de communication entre ceux-ci, des liaisons de communication additionnelles peuvent être établies entre d'autres systèmes de communication sans fil à l'intérieur de la même tranche de temps semi-permanente planifiée. Ceci est illustré par la liaison de communication 27 opérant dans la tranche de temps 1 entre les noeuds mobiles 12c et 12e, et la liaison de communication 29 opérant également dans la tranche de temps 1 entre les noeuds mobiles 12a et 12b, comme illustré sur la figure 1. Cette caractéristique de la présente invention permet avantageusement aux ressources du réseau de communication mobile sans fil 10 d'être mieux utilisées. Le contrôleur 18 limite le nombre de liaisons de communication pour chaque noeud mobile sans fil 12a-12h à l'intérieur de chaque trame temporelle en fonction d'un nombre total de tranches de temps à l'intérieur de la trame. L'avantage lié au fait de limiter le nombre de liaisons de communication à une fraction du nombre total de tranches de temps à l'intérieur de la trame temporelle est de simplifier la planification des tranches de temps avec les noeuds avoisinants. Le nombre de liaisons de communication pour chaque noeud mobile sans fil 12a-12h à l'intérieur de chaque trame temporelle est inférieur ou égal à N, et le nombre total de tranches de temps à l'intérieur de chaque trame est supérieur ou égal à 2N-1. Outre le fait de simplifier la planification des tranches de temps, ce type de planification distribuée permet d'éviter les conflits. La planification distribuée permet à n'importe quelle paire de noeuds mobiles sans fil, telle que 12a et 12b, par exemple, de planifier une tranche de temps semi-permanente sans avoir à communiquer avec les autres noeuds mobiles sans fil. En d'autres termes, il n'y a pas de type maître/esclave centralisé de coordination avec la totalité des noeuds mobiles sans fil 12a-12h pour planifier les tranches de temps semipermanentes. Comme les tranches de temps parmi les noeuds mobiles sans fil 12a-12h sont planifiées de manière distribuée, il n'existe pas un seul point de défaillance dans le réseau de communication mobile sans fil 10. Le contrôleur 18 peut affecter des niveaux de priorité aux liaisons de communication et éliminer une des liaisons de communication en fonction des niveaux de priorité pour rendre disponible une tranche de temps semi-permanente afin d'établir une liaison de communication avec un nouveau noeud mobile avoisinant. L'affectation de niveaux de priorité aux liaisons de communication sera traitée plus en détail ci-dessous. De plus, le contrôleur 18 peut également affecter des niveaux de priorité aux liaisons de communication et planifier la au moins une tranche de temps disponible en fonction de ces niveaux de priorité. Le contrôleur 18 peut également planifier une des tranches de temps semi-permanentes comme tranche de temps disponible si le nombre de liaisons de communication est inférieur à N. Ceci permet de gérer de manière avantageuse les demandes de liaisons de communication sur une base'selon les nécessités'pour les liaisons de communication existantes. Cependant, le contrôleur 18 peut re-affecter la tranche de temps affectée à la demande à une tranche de temps semipermanente si le nombre des liaisons de communication est à nouveau égal à N, comme décrit également plus en détail ci-dessous. Chaque liaison de communication est formée par un noeud mobile initiateur, tel que le noeud 12a, et un noeud mobile récepteur, tel que le noeud 12b, et le noeud mobile initiateur transmet une liste de tranches de temps semi-permanentes disponibles au noeud mobile récepteur. Le noeud mobile récepteur 12b transmet ensuite la sélection d'une des tranches de temps semipermanentes au noeud mobile initiateur. Le noeud mobile initiateur 12a confirme ensuite la sélection de la tranche de temps semi-permanente sélectionnée au noeud mobile récepteur. Chaque noeud mobile peut comprendre en outre une antenne omni-directionnelle 20 connectée à l'émetteur/récepteur 14 pour échanger des informations positionnelles avec d'autres noeuds mobiles avoisinants. D'autres informations qui peuvent être échangées incluent des contraintes ressources et la détection de la présence d'un nouveau noeud voisin potentiel. En outre, le dispositif d'antenne phasé 16 peut générer simultanément plusieurs faisceaux d'antenne, dans lesquels le contrôleur 18 dirige le dispositif d'antenne phasé vers plusieurs noeuds mobiles avoisinants à l'intérieur d'une tranche de temps semipermanente planifiée. Le procédé a également pour objet un procédé pour établir des liaisons de communication pour une pluralité de noeuds mobiles 12a-12h, chaque noeud mobile comprenant un émetteur/récepteur 14, un dispositif d'antenne phasé 16 connecté à 1'émetteur/récepteur, et un contrôleur 18 connecté à l'émetteur/récepteur. Le procédé comprend pour chaque noeud mobile 12a-12h la planification d'une tranche de temps semi-permanente respective pour chaque trame temporelle afin d'établir une liaison de communication avec un noeud mobile avoisinant et laisser au moins une tranche de temps disponible dans chaque trame temporelle. La au moins une tranche de temps disponible est planifiée de manière préférée pour servir la liaison de communication avec un noeud mobile avoisinant en fonction de la demande de liaisons de communication. Le dispositif d'antenne phasé 16 est dirigé de manière préférée vers chaque noeud mobile avoisinant 12a-12h lors d'une communication avec celui-ci. Chaque trame temporelle peut avoir jusqu'à N tranches de temps semipermanentes et au moins 2N-1 tranches de temps disponibles. Le procédé inclut en outre la possibilité pour chaque noeud d'affecter des niveaux de priorité aux liaisons de communication et d'éliminer une des liaisons de communication en fonction des niveaux de priorité afin de rendre disponible une tranche de temps semi-permanente pour établir une liaison de communication avec un nouveau noeud mobile avoisinant. En outre, une tranche de temps disponible qui est couramment planifiée pour servir une liaison de communication particulière peut être réaffectée à une autre liaison de communication en fonction de la demande de liaisons. Ceci permet avantageusement à tout noeud mobile de répondre aux variations des demandes de liaisons de communication. La planification des tranches de temps semipermanentes et des tranches de temps disponibles sera à présent traitée plus en détail. Les détails relatifs au fait de diriger les antennes directionnelles 16 vers un noeud mobile récepteur 12a-12h seront omis, puisque cette caractéristique de la présente invention est déjà comprise par l'homme du métier. Dans le cadre de la description, on supposera que l'antenne directionnelle 16 est un dispositif d'antenne phasé. Comme l'homme du métier l'a facilement compris, un dispositif d'antenne phasé 16 inclut une pluralité d'éléments d'antennes et des déphaseurs respectifs qui peuvent être réglés pour produire un faisceau d'antenne ajustable dans une direction désirée. Le dispositif d'antenne 16 dirige ou balaie la structure d'antenne sans bouger physiquement l'antenne. Également dans le cadre de la description, plusieurs suppositions sont faites sur le réseau de communication mobile sans fil 10. En premier, il existe une bande de fréquence unique qui est un canal à haut débit de données, qui est partagé par tous les noeuds mobiles sans fil 12a-12h. Ce type de voie de transmission est en partage de temps entre tous les noeuds mobiles sans fil 12a-12h à la fois pour transmettre et pour recevoir. Toutes les tranches de transmission sont planifiées à l'avance. Une supposition est également faite selon laquelle un canal de service séparé à faible débit de données est fourni. Ce canal de service peut être utilisé pour la découverte des noeuds, l'entrée dans le réseau, et l'échange de diverses autres informations de service liées au contrôle des liaisons de données dont les requêtes de ressources. Ce canal de service est fourni par l'intermédiaire d'une antenne omni-directionnelle 20. Une bonne référence de synchronisation globale est également connue à tous les noeuds. Les termes noeuds mobiles sans fil et systèmes de communication mobiles sans fil 12a-12h sont interchangeables d'un bout à l'autre de la description suivante. Le réseau de communication mobile sans fil 10 inclut également la possibilité de localiser et de rechercher des noeuds mobiles de telle sorte que les systèmes d'antennes phasés 16 puissent être pointés avec précision lorsqu'une tranche de temps planifiée est disponible. Comme noté ci-dessus, une explication détaillée sur le pointage/repérage ne sera pas fournie ici. Une supposition est également faite que les systèmes d'antennes phasés 16 ont une largeur de faisceau de zéro. Cette supposition sera développée plus loin. En conséquence, nous pouvons supposer qu'une transmission par un noeud mobile donné sera reçue uniquement par le noeud mobile voisin auquel il tente de transmettre. Ceci permet une série moins restrictive de contraintes sur la planification des tranches de temps. Chaque liaison de communication recevra un numéro qui représente une tranche de temps planifiée à l'intérieur de laquelle il est possible de transmettre et de recevoir des données. Les contraintes sont les suivantes. Aucun noeud ne peut avoir plusieurs liaisons de communication portant le même numéro de tranche de temps. Une affectation de tranche de temps donnée s'appliquera à une liaison semi-duplex entre deux noeuds mobiles, et sera utilisée alternativement par les deux noeuds pour transmettre et pour recevoir. Ces deux contraintes impliquent qu'une tranche de temps affectée par un noeud mobile à un de ses noeuds voisins est contrainte par la tranche de temps précédente assignée par ce noeud aux autres liaisons. La planification des tranches de temps pour le dispositif d'antenne phasé 16 est illustrée sur la figure 1, qui montre un réseau 10 avec une connectivité de liaison basée sur des tranches de temps planifiées. Les tranches de temps sont planifiées de telle sorte que les noeuds mobiles sans fil 12a-12h savent quand pointer leur dispositif d'antenne phasé 16 respectif vers un noeud mobile sans fil avoisinant. Les liaisons de communication sont supposées être bidirectionnelles et sont utilisées de manière semiduplex dans laquelle chaque numéro de tranche de temps représente une tranche de temps et une opportunité de transmission dans chaque direction qui a lieu dans cette tranche de temps. Le terme Ntrame sera utilisé pour dénoter l'index de liaison maximal ou le nombre maximal de tranches de temps à l'intérieur d'une trame. Dans le cas de cet exemple, Ntrame = 6. La figure 3 illustre une trame représentative de tranches de temps. Dans la formulation la plus simple, chaque époque ou trame a n tranches et la valeur de n est mise à Ntrame. Sur la figure, nous voyons également comment une tranche de temps est utilisée pour que la liaison se connecte aux noeuds désignés par les noeuds A et B. Chaque tranche de temps est divisée en deux minitranches 22a, 22b. La première mini-tranche 22a (par exemple, la moitié de la tranche de temps) est utilisée pour les transmissions du noeud A à B. Puis, la direction de la liaison est inversée et la seconde mini-tranche 22b est utilisée pour les transmissions du noeud B à A. Pendant les périodes de transmission, plusieurs paquets peuvent être transmis. Comme indiqué, chaque mini-tranche 22a, 22b contient également un délai de garde 24a, 24b sélectionné selon les considérations suivantes. La distance maximale entre chaque paire de noeuds détermine le délai de propagation maximal qui peut être accordé. Une distance maximale de 100 miles correspond à environ 0,5 ms de délai de propagation. Un délai de garde est alloué à chaque mini-tranche 22a, 22b pour tenir compte de l'incertitude du délai de propagation et des délais de propagation inégaux entre toutes les paires de noeuds. À une distance maximale de 100 miles, un délai de garde de 0,5 ms est requis. L'allocation de délai de garde pour une distance maximale de 100 miles implique le besoin de faire des mini-tranches 22a, 22b dans l'ordre de 2 à 4 ms pour minimiser la perte d'efficacité du canal. À titre d'exemple, si nous supposons un débit de données de 50 Mb/s sur les liaisons de communication et une distance maximale de 100 miles, alors une mini-tranche de 4 ms implique 200.000 bits/mini-tranche (250 mini-tranches par seconde). La mini-tranche contiendra alors un délai de garde de 25.000 bits et 175.000 bits de données mission. Le contrôleur 18 peut également altérer chaque liaison établie pour affecter une priorité lorsque les tranches de temps disponibles sont planifiées. Comme expliqué plus en détail ci-dessous, des tranches de temps semi-permanentes (SP) et des tranches de temps affectées à la demande (DA) sont fournies à l'intérieur de chaque trame. Un objectif déclaré est d'augmenter la réutilisation des tranches de temps parmi plusieurs noeuds en même temps. Alors que le réseau mobile 10 de la figure 1 est limité dans le nombre total de noeuds et de liaisons de communication, il y a un certain nombre de cas d'utilisation parallèle des tranches de temps. Par exemple, les tranches de temps 1 et 2 sont utilisées chacune simultanément sur 3 liaisons de communication différentes, et la tranche de temps 6 est utilisée uniquement sur une seule liaison. Toutes les autres tranches de temps sont affectées à deux liaisons de communication. Nous pouvons définir un facteur de réutilisation qui indique le niveau moyen de réutilisation comme un rapport du nombre total d'affectations de tranches de temps dans le réseau (Ntrame) par rapport au nombre de tranches de temps assignées (Nb~Tranches~Assignées) : R = Nb~Tranches~Assignées/Ntrame (1) Pour le réseau exemple 10 de la figure 1, l'approche de réutilisation fournit un facteur de réutilisation de R = 14/6 = 2,333, indiquant qu'il existe en moyenne un peu plus de deux utilisateurs simultanés de chaque tranche de temps dans la planification du réseau. Il est évident que le facteur de réutilisation calculé pour n'importe quel algorithme de planification spécifique dépendra beaucoup de la taille et de la topologie du réseau. Une évaluation comparative complète doit considérer une variété de tailles et de topologies de réseau. Une limite inférieure de la valeur de Ntrame pour tout graphe peut être déterminée en notant que chaque noeud requiert au moins autant de tranches de temps que le noeud a de voisins, c'est-à-dire que le noeud requiert un nombre de tranches de temps au moins égal à son degré. Ntrame doit alors être au moins aussi grand que le degré de noeud maximal sur le graphe entier. Ainsi, si l'on désigne le degré du noeud i par dl la limite inférieure de Ntrame est Ntrame = maxi {di} (2) Pour le réseau exemple 10 illustré sur la figure 2, la partie de réutilisation reçoit la planification avec Ntrame égal au nombre minimum de tranches de temps qui doivent être utilisées selon l'équation (2). Il faut noter que plusieurs noeuds, à savoir tous les noeuds sauf le noeud 1, reçoivent moins de la totalité de la série de tranches de temps. Ainsi, un algorithme de planification évolué peut assigner des tranches additionnelles à certaines des liaisons sans introduire des conflits dans la planification. Les paragraphes suivants traitent essentiellement de la planification des tranches de temps pour générer l'ordonnancement des liaisons. D'autres problèmes liés au réseau d'antennes phasé global qui doivent être ensuite résolus incluent : 1) la découverte des noeuds et des voisins, 2) l'entrée dans le réseau, 3) le format et le protocole du canal de service dont les échanges de protocole pour la planification des mises à jour, et 4) le repérage et la localisation des noeuds voisins (peut inclure l'assistance du dispositif d'antenne phasé 16), et 5) un algorithme de routage pour une topologie de réseau dynamique. L'approche pour planifier les tranches de temps selon la présente invention est basée sur les principes suivants. Premièrement, un nombre spécifié de tranches de temps sont allouées comme tranches de temps semipermanentes (SP) planifiées pour une liaison donnée. Le reste des tranches de temps disponibles (DA) peut être alloué sur une base'assigné à la demande'aux noeuds/liaisons qui en ont le plus besoin. Ceci permet une flexibilité pour modifier l'ordonnancement sur une base'selon les nécessités'. Deuxièmement, comme expliqué ci-dessus, une limite du nombre maximal de tranches de temps assignées de façon semi-permanente est établie. Cette limite est un paramètre qui est sélectionné en fonction d'un réseau spécifique. Cette limite est également la limite supérieure du nombre de noeuds voisins disponibles, avec une seule tranche de temps SP par noeud. Troisièmement, comme expliqué également ci-dessus, une limite du nombre maximal de tranches de temps par trame est établie. Cette limite est un paramètre qui est également sélectionné en fonction d'un réseau spécifique. Cette limite est importante pour établir une limite de latence, puisqu'elle est détermine le temps de revisite maximal pour une opportunité de transmission d'une liaison. Quatrièmement, la relation entre le nombre de tranches de temps totales par trame, Ntrame, et la limite du nombre maximal de tranches de temps assignées de façon semi-permanente par trame est choisie de telle sorte que la planification des tranches de temps assignées de façon semi-permanente soit grandement simplifiée et que les conflits de planification puissent être évités de manière significative même avec une planification distribuée. En limitant le nombre maximal de tranches de temps assignées de façon semi-permanente par noeud à une certaine fraction du nombre total de tranches de temps par trame, le processus consistant à affecter de façon distribuée des tranches de temps assignées de manière semi-permanente est grandement simplifié. La limite supérieure du nombre de tranches de temps assignées de façon semi-permanente (et, par conséquent, le nombre maximal de noeuds voisins disponibles) sera désignée par N. Nous considérerons les valeurs de Ntrame telles que : Ntrame = 2N-1 (3) Supposons que tous les noeuds 12a-12h du réseau 10 soient connectés par des liaisons directionnelles, dans lesquelles chaque noeud a un dispositif d'antenne phasé 16 à faisceau unique avec un partage de faisceau par sauts de temps et pointage sur ses noeuds voisins. En outre, supposons que le nombre de voisins soit égal à N, et que la limite du nombre disponible de tranches de temps semi-permanentes (avec une tranche de temps SP allouée par voisin) soit fixe. Si la valeur fixe de Ntrame satisfait l'équation (3), alors tous les noeuds peuvent sélectionner une tranche de temps semi-permanente différente pour chacune de ces liaisons par un accord mutuel avec le voisin pour cette liaison sans tenir compte des liaisons sélectionnées par les autres noeuds situés à plus d'un saut. Ceci permet à chaque noeud de sélectionner sa tranche de temps semi-permanente pour la liaison à un noeud voisin d'une façon très directe en communiquant uniquement avec ce noeud voisin. Ce procédé peut être suivi pour un nombre allant jusqu'à N de noeuds voisins. Le point clé est de reconnaître que, comme la valeur de Ntrame augmente pour une valeur fixe de N, il existe moins de contraintes sur la capacité d'un noeud à sélectionner une tranche de temps qui n'entre pas en conflit avec le choix d'un voisin concernant une tranche de temps. Un noeud sélectionnant une tranche de temps pour une nouvelle liaison doit sélectionner une tranche de temps qui n'est pas en cours d'utilisation et que le voisin n'utilise pas actuellement. Si un noeud a couramment m voisins avec une seule tranche de temps assignée à chacune de ces liaisons aux voisins et qu'il ajoute une liaison à un nouveau noeud voisin, le noeud voisin peut alors utiliser au maximum (N-l) tranches de temps. Ainsi, si Ntrame est supérieur à (m+N-1), il y aura alors au moins une autre tranche de temps disponible que le noeud peut affecter à la nouvelle liaison. Le pire des cas, dans ce processus d'affectation, est celui dans lequel le noeud a déjà (N- 1) voisins et affecte la tranche de temps au Nième noeud voisin. Dans ce cas, Ntrame doit satisfaire l'équation (3) pour une tranche de temps additionnelle devant être garantie pour être disponible pour une affectation à la liaison du Nième voisin. Quelques observations supplémentaires seront faites concernant la façon dont cette propriété peut être exploitée dans l'approche de la planification de tranches de temps décrite. Premièrement, un noeud doit seulement coordonner la sélection de la tranche de temps semi-permanente devant être assignée pour une liaison directionnelle d'un voisin avec ce voisin. Le noeud demandant la liaison pourrait, par exemple, envoyer au voisin la liste des tranches de temps suggérées pour la liaison. Ceci en fonction des tranches de temps non utilisées pour les affectations SP. Cette liste pourrait être ordonnée en fonction d'autres facteurs qui seront traités ci-dessous, mais cela n'est pas nécessaire. Le noeud voisin peut ensuite sélectionner à partir de cette liste la tranche de temps qu'il préfère et retourner une réponse avec cette sélection. Ceci nous permet de définir un algorithme direct, pleinement distribué pour la planification des tranches de temps semi-permanentes. Si un noeud a moins de N voisins, alors plus d'une de ses N tranches de temps semi-permanentes disponibles peuvent être assignées à des liaisons individuelles. Cependant, dans ce cas, il n'y a pas de garantie que les N affectations puissent être effectuées par l'intermédiaire d'une coordination de noeuds voisin-àvoisin sans conflits. Par exemple, si N=6 et si un noeud a seulement 3 voisins mais que chacun de ces voisins a 6 voisins, le noeud pourra alors affecter uniquement une seule tranche de temps à chacune des liaisons avec ses 3 voisins. Pour simplifier notre algorithme, nous ne permettrons pas la planification de plusieurs tranches de temps SP par liaison. Cependant, toutes les tranches de temps inutilisées peuvent être allouées comme tranches de temps disponibles. Pour certains réseaux avec un très grand nombre de noeuds dans lesquels le nombre de voisins potentiels sera supérieur à la limite N, il y aura également un problème de contrôle de topologie qu'il faudra traiter. Le noeud devra choisir, parmi les voisins potentiels, ceux qui créent la topologie réseau optimale. Ce problème de contrôle de topologie est également relié au concept qui consiste à optimiser un réseau énergétiquement efficace. Dans le cas où le nombre de voisins potentiels est beaucoup plus grand que la limite N, une fonction de contrôle de topologie peut être utilisée pour sélectionner le noeud voisin auquel se connecter. Si nous affectons à Ntrame la valeur minimale autorisée par (3), chaque noeud pourra alors avoir un maximum de N tranches de temps semi-permanentes et un total de (2N-1) affectations de tranches de temps. Les tranches de temps assignées à la demande seront affectées sur une base qui permet de répondre le mieux possible à la charge de trafic. Comme pour les tranches de temps semi-permanentes, le noeud doit seulement coordonner la sélection des tranches de temps disponibles à assigner pour une liaison directionnelle d'un voisin avec ce voisin. Cela signifie qu'un voisin enverra une requête au voisin pour l'affectation de tranches de temps sur la liaison directionnelle, et recevra soit une autorisation de l'affectation soit un refus de la requête sur la même liaison. Un noeud demandant l'allocation d'une tranche de temps disponible DA à partir d'un noeud voisin le fera en fonction d'un besoin perçu de capacité additionnelle sur cette liaison. Ceci peut être lié à l'utilisation de liaisons à haut débit (création de files d'attente) basée sur des mesures à court terme et à long terme. La requête contiendra le nombre de tranches requises et une métrique, qui indique la priorité à attacher à la requête. La métrique peut indiquer la longueur de file d'attente comme mesure du besoin d'allocation de tranche de temps. Le noeud recevant la requête peut également recevoir des requêtes à partir d'autres noeuds voisins, qui peuvent entrer en conflit pour l'allocation de la même tranche de temps. Pour simplifier le protocole, un noeud doit avoir terminé de traiter une tâche d'une allocation de tranche de temps disponible DA avant de considérer l'allocation suivante. Ces allocations ne peuvent pas persister pendant une longue période de temps, car elles sont constamment sujettes à la préemption de devenir ré-allouées comme tranches de temps semi-permanentes suite aux changements de topologie, ou sujettes à une ré-allocation en raison de la demande de trafic changeante. La découverte des voisins et des liaisons sera à présent traitée. L'algorithme de planification de liaisons distribuées requiert la prise en charge d'un canal de service omni-directionnel pour certains échanges de protocole qui doivent avoir lieu avec un noeud voisin potentiel avant l'établissement de la liaison directionnelle avec ce noeud. De tels messages incluent le REQ~SPTS qui demande l'allocation d'une tranche de temps semi-permanente sur la liaison directionnelle à ce noeud. Outre le fait de prendre en charge les échanges de messages protocolaires qui prennent en charge directement le protocole défini dedans, le canal de service omni-directionnel doit prendre en charge la fonction de découverte des voisins et des liaisons. Ceci est généralement effectué par l'intermédiaire d'omni-transmissions périodiques par chaque noeud via une antenne omni-directionnelle 20 qui alerte tous les autres noeuds qui se trouvent à sa portée que les deux noeuds peuvent être des noeuds voisins. Plusieurs protocoles de routage ad hoc (dont OLSR) ont défini un tel protocole de prise en charge. Ces protocoles définis précédemment peuvent être adaptés pour prendre en charge cet algorithme de planification de liaisons distribuées. La fonction principale qui doit être exécutée par un tel protocole est de découvrir les nouveaux noeuds voisins potentiels et de les signaler à la fonction de contrôle de topologie. Une approche de la découverte des noeuds et des liaisons inclut la transmission périodique par chaque noeud de messages de signalisation sur le canal de contrôle pour notifier aux noeuds voisins sa présence et sa position. De plus, des messages d'état de liaisons sont transmis périodiquement pour notifier aux noeuds voisins l'identité de ses voisins radiophares (liste BN) et de ses noeuds voisins PA (liste PAN), et les tranches de temps assignées à ces noeuds. La partie découverte des liaisons de l'algorithme compare continuellement la liste des voisins de balisage bi-directionnel (BBN) à la liste PAN pour voir s'il existe des noeuds sur la liste BBN qui ne sont pas sur la liste PAN. Un tel noeud voisin devient un candidat au test de liaison pour déterminer si une liaison PA est possible. Selon cette approche, après un échange de messages de contrôle, la liaison directionnelle est testée pour déterminer si une communication fiable est possible. Si la communication est fiable, le nouveau noeud voisin est ajouté à la liste PAN. Ceci valide la communication dans la tranche de temps de test, mais pas nécessairement dans la tranche de temps qui peut être assignée à la liaison sur une base semi-permanente. Une approche consiste à procéder de cette manière ou une autre approche consiste à attendre qu'une tranche de temps SP soit assignée et à la tester dans cette tranche de temps. La fonction de contrôle de topologie peut être une fonction très directe si elle ne doit pas effectuer une optimisation de la topologie. Le but de cette fonction est de prendre la liste des noeuds de la liste PAN, les informations relatives à la fiabilité de ces liaisons, et les informations relatives à la topologie du réseau, et d'utiliser ces informations pour déterminer quels noeuds de la liste PAN deviendront des voisins PA. C'est la fonction qui optimise la topologie du réseau s'il existe des contraintes telles que le nombre de voisins PA qui ne permettent pas à tous les noeuds de la liste PAN de devenir des voisins PA. Avec les contraintes proposées d'une valeur fixe pour Ntrame et d'une valeur fixe pour N (le nombre maximal de tranches de temps semi-permanentes par noeud), on peut se soucier de l'utilisation de la topologie réseau. Cela sera certainement le cas si ces valeurs sont sélectionnées pour être des nombres très petits. Par exemple, si N = 3 était sélectionné avec Ntrame = 5, il peut s'avérer difficile de prévoir une topologie réseau bien connectée, lorsque nous ne pouvons pas avoir plus de 3 voisins pour chaque noeud, à moins qu'une fonction de contrôle de topologie intelligente n'ait utilisé soigneusement la topologie avant d'ajouter de nouveaux noeuds voisins PA. Et cela peut être le cas particulièrement pour un grand réseau. Ainsi, la fonction de contrôle de topologie doit créer une liste de priorité voisins (NP), qui est la liste PAN ordonnée dans un ordre de désirabilité comme voisins PA potentiels. Cette liste établira l'ordre de priorité dans lequel des voisins PA potentiels sont des tranches de temps planifiées. Cependant, notre problème initial est celui d'un petit réseau avec peut-être 15 noeuds. Dans ce cas, nous pouvons spécifier pour N une valeur comprise entre 5 et 8, et avoir toujours une faible latence. Il est très peu probable qu'il y ait des problèmes relatifs à l'utilisation de la topologie, puisque le fait d'autoriser 5 à 8 noeuds voisins permettra pratiquement à tous les voisins possibles d'être des voisins PA. Un second but de la fonction de contrôle de topologie est de générer l'événement de changement de topologie qui entraîne le changement d'état du processus de planification de liaisons et d'exécuter le processus de ré-allocation pour les tranches de temps SP. Une structure d'algorithme de planification de haut niveau sera à présent décrite. Le processus de planification a été formulé avec l'objectif de minimiser la complexité du processus, tout en tirant parti de l'approche générale illustrée ci-dessus. Le point clé pour contrôler ce processus de planification est de maintenir une structure de données précise à chaque nceud qui reflète l'état de l'ordonnancement de tranches de temps pour les futures tranches de temps assignées à la liaison avec chaque noeud voisin. Deux structures de données sont proposées : une base de données d'affectations de tranches et une base de données de messages de liaisons. Les états possibles des liaisons dans la structure de données pour une tranche de temps donnée de l'époque sont répertoriés dans le tableau 1. Le tableau décrit chaque état possible et donne la notation pour cet état. Le tableau 2 montre un exemple d'affectation de tranches DA, et les contenus indiquant les tranches de temps pour Ntrame = 9 (N = 5), les affectations d'état pour chaque état, et des exemples d'ID de voisins assignés pour chaque tranche de temps. Dans cet exemple, 4 voisins ont reçu des tranches de temps SP de telle sorte qu'un voisin additionnel peut être connecté avec ces contraintes. Il y a une tranche de temps libre qui peut être allouée comme tranche de temps DB ou offerte avec les tranches de temps DB pour être allouée comme tranche de temps SP si un nouveau noeud voisin est possible. L'utilisation de la base de données de messages de liaisons sera traitée plus loin dans l'explication détaillée des protocoles. L'exemple indique également l'utilisation de soustranches, par exemple 2 sous-tranches par tranche. C'est un concept à utiliser avec les allocations DA pour permettre une granularité plus fine. Dans ce cas, cela signifiera qu'une allocation de tranche de temps k, de sous-tranche 1 sera une allocation à une liaison de tranche de temps k sur les trames impaires. À l'inverse, une sous-tranche 2 indiquera une allocation de la tranche de temps sur les trames paires. TABLEAU 1 État des tranches de temps dans Notation la base de données (DB) . Libre Libre . Tranche de temps allouée SP SP Alloc . Tranche de temps allouée DA DA Alloc (peut être préemptée par un processus d'allocation SP ou par une ré-allocation DA) . Message de requête d'allocation SP~Req SP envoyé Message de réponse d'allocation SP~Reply SP envoyé Message de requête d'allocation DA~Req DA envoyé (peut être préempté par un processus d'allocation SP ou par une ré-allocation DA) . Message de réponse d'allocation DA~Reply DA envoyé (peut être préempté par un processus d'allocation SP ou par une ré-allocation DA) TABLEAU 2 Tranche de Sous-État ID de voisin temps tranche assigné 1 -- Libre -- 2 -- SP~Alloc 3 3 SP~Req 4 4 1 DA~Alloc 3 4 2 DA~Alloc 4 5 1 DA~Alloc 5 5 2 DA Alloc 3 '6 SPAlloc 5 '71, 2DAAlloc'8 8 2 DA Alloc 4 9 -- SP~Alloc 8 Le diagramme d'état de niveau supérieur pour le protocole de planification de liaisons est représenté sur la figure 5. Le diagramme montre deux processus indépendants 30 et 32 qui sont chargés de maintenir et de modifier la base de données d'allocations de tranches de temps. Sur la gauche se trouve le diagramme d'état du processus consistant à maintenir et à assigner des tranches de temps semi-permanentes (SP), c'est-à-dire le processus 30. Ce processus a la priorité sur les affectations faites par le processus 32 de droite, qui a la responsabilité d'assigner les tranches de temps disponibles (DA). Dans le chemin de processus 31, les tranches de temps qui peuvent être saisies sont les suivantes : libre, allouée DA, et en cours d'allocation DA. De même, dans le chemin de processus 33, les tranches de temps qui peuvent être saisies sont les suivantes : libre, allouée DA et également doit être réallouée. Cette base de données doit être contrôlée comme une base de données verrouillée de telle sorte que, pour tout état d'affectation de tranche de temps donné, seulement un des deux processus de planification puisse modifier cet état à un moment donné dans le temps. Une fois qu'un des processus a commencé à modifier l'état d'une affectation de tranche de temps particulière, l'état est verrouillé et l'autre processus ne peut pas le modifier avant qu'il soit libéré. À tout moment, chaque tranche de temps de la base de données est dans un de sept états, comme indiqué dans le tableau 1. Les tranches de temps disponibles sont dites être dans l'état libre, c'est-à-dire qu'elles ne sont pas assignées à une liaison à l'un de leurs noeuds voisins parce qu'un conflit de planification a empêché l'affectation ou parce que la tranche de temps est récemment devenue libre et n'a pas encore été planifiée. Comme indiqué, une tranche de temps dans l'état libre peut être planifiée soit comme tranche de temps SP, soit comme tranche de temps DA. Une tranche de temps qui a été allouée comme assignée SP peut être modifiée uniquement par le processus qui gère les tranches de temps SP. La tranche de temps peut être désallouée par ce processus si la topologie du réseau change ou si une topologie plus désirable est possible. Tant qu'une telle tranche de temps n'est pas retournée à l'état libre, le processus consistant à maintenir et à assigner les tranches de temps DA ne peut pas modifier son état. De plus, toute tranche de temps avec un état DB indiquant qu'elle est en cours d'assignation SP ne peut pas être allouée par le processus d'affectation DA. Ceci inclut les états indiquant que des messages de requête et de réponse SP ont été envoyés. Cependant, si l'état d'une tranche de temps est allouée DA, elle peut alors être réallouée par le processus d'affectation DA. Ceci peut avoir lieu si la charge du réseau indique qu'une ré-allocation de la tranche de temps DA est nécessaire. Par contre, le processus qui alloue les tranches de temps SP a la priorité. Outre le fait d'affecter les tranches libres, il peut saisir et réaffecter toutes les tranches de temps qui ont été assignées DA ou qui sont en cours d'assignation DA. Ceci est fait pour fournir un processus direct qui permet d'assurer qu'au moins une tranche de temps SP soit assignée à chaque noeud voisin pendant une trame de Ntrame tranches de temps. Les tranches de temps allouées SP retournent à l'état libre uniquement si la liaison est perdue, ou si la fonction de contrôle de topologie détermine qu'une liaison particulière ne doit plus être dans la liste des N liaisons de niveau supérieur à établir avec des noeuds voisins. La figure 5 illustre le fonctionnement de ce processus au niveau supérieur. Le processus d'affectation de tranches SP a une plus grande flexibilité dans l'allocation des tranches de temps. Il peut saisir davantage de tranches de temps à allouer que le processus DA, et il peut saisir des tranches de temps qui ont été allouées DA ou qui sont en cours d'allocation DA. Le processus SP peut recevoir divers événements de traitement, notamment des événements de changement de topologie à partir de la fonction de contrôle de topologie et des messages protocolaires. De tels événements peuvent inclure la perte de liaison à un voisin, la découverte d'un nouveau voisin, la réception d'un message de requête d'allocation SP à partir d'un noeud voisin, et la découverte qu'un changement de topologie doit avoir lieu pour ajouter une liaison à un voisin, interrompre une liaison, ou les deux. La notification des événements de changement de topologie inclura des données qui décriront le changement de topologie qui doit avoir lieu. Si l'événement décrit une perte d'une liaison, alors la seule action qui doit être entreprise est de changer l'état des tranches de temps appropriées dans la base de données d'affectations de tranches à libre . Si une liaison doit être ajoutée, le processus est plus complexe. Dans ce cas, le processus d'affectation de tranches SP initie des échanges de messages protocolaires avec le nouveau noeud voisin et modifie la base de données d'affectations de tranches. Ceci a finalement pour résultat l'accord entre les deux noeuds sur une affectation de tranche de temps pour la tranche SP assignée à cette liaison. Une seule tranche de temps SP doit être assignée à chaque liaison avec un voisin pour simplifier le protocole. Des détails supplémentaires de ce protocole sont décrits cidessous. Le processus d'affectation des tranches de temps DA suit une procédure similaire. Le processus d'affectation de tranches DA doit calculer les besoins en tranches de temps DA et les comparer avec les tranches de temps allouées pour déterminer si une nouvelle ré-allocation de tranches de temps est nécessaire. Si une ré-affectation de tranches DA est initiée, elle conduira également à une série d'échanges de messages protocolaires avec les noeuds voisins pour s'accorder sur les tranches de temps réaffectées. Le processus d'affectation de tranches DA peut réaffecter uniquement des tranches de temps qui sont dans l'état libre ou non assigné SP. Des détails supplémentaires sur le protocole et le processus consistant à déterminer quand une ré-affectation de tranches de temps DA est nécessaire seront décrits ci-dessous. L'allocation de tranches de temps semi-permanentes à des liaisons directionnelles sera à présent traitée. Dans la description de l'approche consistant à allouer N tranches de temps semi-permanentes, supposons que N soit fixe et choisi de façon intelligente en fonction de la taille du réseau et de l'environnement. Supposons également que Ntrame = 2N-1. Ntrame peut également être fixé à n'importe quelle valeur supérieure pour fournir des tranches de temps à la demande additionnelles, si cela est jugé utile pour l'environnement particulier du réseau et du trafic. Plusieurs fonctions importantes sont fournies par la fonction de contrôle de topologie. La liste de priorité voisins (NP) est générée par la fonction de contrôle de topologie et est utilisée pour indiquer les noeuds voisins PA préférés pour l'affectation de tranches de temps. Si la longueur de la liste NP est N ou inférieure, alors la fonction de contrôle de topologie génèrera des événements de changement de topologie en direction du processus d'affectation de tranches SP afin qu'il tente d'obtenir des affectations de tranches de temps pour la totalité de ces noeuds voisins. Si la longueur de la liste NP est supérieure à N, alors elle génèrera des événements de changement de topologie en direction du processus d'affectation de tranches SP pour obtenir des affectations de tranches de temps pour chacun des N noeuds de plus haute priorité de la liste NP. La liste NP change constamment en raison de la dynamique du réseau. Lorsque des liaisons PA sont défaillantes, le noeud est enlevé de la liste NP et la (les) tranche (s) de temps pour cette liaison sont alors sujettes à une ré-allocation. Ceci est pris en charge par la fonction de contrôle de topologie qui envoie un événement de suppression de liaison au processus d'affectation de tranches SP. De cette manière, la tranche de temps SP et toutes les tranches de temps DA allouées à cette liaison deviennent disponibles pour une ré-allocation à un autre noeud de la liste PA. Lorsque des tranches deviennent disponibles, le premier choix consiste à allouer la (les) tranche (s) aux noeuds voisins PA additionnels si c'est possible, compte tenu de l'état actuel de la liste NP. Si aucun noeud voisin additionnel ne peut être ajouté, la (les) tranche (s) peut/peuvent alors être réallouée (s) sur une base DA. La figure 6 montre un diagramme d'état du processus d'affectation de tranches SP. Afin de gérer le traitement des messages protocolaires, une base de données de messages de planification de liaisons est créée, comme représenté dans le tableau 3. Elle maintient l'état nécessaire à partir des échanges de protocole précédents à utiliser lorsque le message SP suivant arrive pour être traité. Le processus inactif fait de la gestion d'événements dans la mesure où il contrôle les événements reçus avant d'autoriser le changement d'un état à l'un des autres états. Ces opérations comportent la vérification des messages reçus pour déterminer s'ils sont compatibles avec l'état actuel de la base de données. Si un message est incompatible avec la base de données, il est rejeté. Certains délais peuvent indiquer que l'état DB doit être réinitialisé. Ce processus exécute cette fonction. TABLEAU 3 Nbr État de Délai Liste Tranche Sous-Num ID la des de tranche tries liaison tranches temps sélecde temps sélec-tionnée tionnée 1 SPAlloc----2 1 1 SPAlloc----2 2 1 DAAlloc----5 1 2 SP Alloc--J -- 2 SP-Alloc--4 2 2 DA-Alloc--5 2 3 SP~Req T2 Ls--1 4 SP Alloc----6 1 4SP Alloc--6J2 Il y a quatre types de messages de base requis dans le protocole d'affectation de tranches de temps SP, comme répertorié ci-dessous dans le tableau 4. L'utilisation de ces messages s'explique d'elle-même et elle est conforme à la description précédente. TABLEAU 4 Type de message Fonction du message REQSPTS Demande d'allocation d'une nouvelle tranche SP REPLYSPTS Réponse au REQSPTS reçu CONFIRM Réponse au REPLYSPTS reçu DELETETS Message indiquant l'allocation d'une tranche de temps supprimée Un exemple d'affectation de tranches de temps SP est illustré sur la figure 7. Les noeuds 1 et 2 ont tous deux 3 voisins avec les affectations de tranches de temps SP représentées pour chaque liaison. C'est pourquoi, ils peuvent ajouter une liaison additionnelle entre eux. Le protocole de planification de liaisons trouvera une tranche de temps acceptable pour l'allocation SP. L'échange de messages protocolaires correspondant est représenté dans le tableau 5. Le noeud 1 initie l'échange en envoyant un REQ~SPTS (L= (4,5, 6,7)) avec une liste d'au moins N tranches de temps candidates. Cette liste peut inclure toutes les tranches de temps libres et DA. Le noeud 1 utilise les tranches 1,2 et 3 pour les allocations SP à ses voisins, et sa liste L contient donc les autres tranches de temps 4,5, 6 et 7. Lorsque le message de requête est envoyé, les changements appropriés sont effectués aux structures de données de messages de planification de liaisons et de tranches de temps. Le noeud 2 utilise les tranches de temps 4,5 et 6 comme allocations SP pour ses liaisons à ses 3 voisins, et il sélectionne donc la tranche de temps 7 comme la seule pouvant fonctionner pour la nouvelle liaison. Il envoie ce choix dans le message de réponse. Lorsqu'un message de réponse est envoyé, les changements appropriés sont également effectués aux structures de données de messages de planification de liaisons et de tranches de temps. Enfin, lorsqu'un message Confirm est envoyé ou reçu, l'état des tranches de temps appropriées passe à alloué SP à la liaison (1,2) . Il faut noter également que si les noeuds 1 et 2 avaient déjà sélectionné 4 noeuds voisins, il serait toujours possible pour eux de trouver des tranches de temps communes avec lesquelles établir une liaison entre eux s'ils utilisent les mêmes tranches de temps avec au moins deux de leurs voisins. TABLEAU 5 Noeud 1 Noeud 2 Reçoit l'événement Ajout de liaison à partir de son contrôle de topologie pour une liaison du noeud 1 au noeud 2 Envoie Msg perdu REQ~SPTS (L= (4,5, 6, 7)) -7 Délai et nouvelle tentative Nouvel envoi -7 Reçu REQSPTS (L= (4,5, 6,7)) REQSPTS (L= (4,5, 6,7)) REPLYSPTS (Tranche 7) REPLYSPTS (Tranche reçu 7) Envoyer CONFIRM (Tranche 7)- > CONFIRM (Tranche 7) reçu Tranche 7 allouée à la Tranche 7 allouée à la liaison (1,2) liaison (1,2) Le pseudo code initial décrivant les processus requis sur la figure 6 a été développé. Plusieurs événements peuvent avoir lieu qui doivent être traités par le processus d'affectation de tranches SP 34. La gestion d'événements est exécutée dans le processus inactif, comme représenté dans le tableau 6. Quatre catégories d'événements sont représentées : message reçu, vérifier les délais, notification d'ajout de liaison à partir du contrôle de topologie, et défaillance de liaison ou suppression de liaison. Les messages reçus sont d'abord vérifiés par rapport à la base de données de messages de planification de liaisons pour s'assurer que le message est cohérent avec l'état actuel de la base de données. Par exemple, si nous avons envoyé une requête à un voisin, le message suivant attendu est une réponse. Pour simplifier ce protocole distribué, seule une tâche d'échanges de messages protocolaires SP à la fois est autorisée. Ceci est appliqué dans la procédure en recherchant dans la base de données si d'autres échanges de messages SP sont en cours avant d'initier une transition'd'ajout de liaison ou avant de traiter un message REQSPTS. Si un ajout de liaison ne peut pas être initié parce qu'une autre tâche de protocole SP est actuellement en cours, l'ajout de liaison sera repoussé en retardant et en re-planifiant ultérieurement lorsque l'autre processus sera terminé. Plusieurs tentatives sont autorisées pour gérer un conflit potentiel entre plusieurs noeuds tentant d'ajouter des liaisons simultanément. Ceci n'est pas sensé résoudre le problème d'une liaison HF non fiable. Ce dernier problème sera traité en utilisant un protocole de liaison sur le canal de service qui utilise ARQ et la retransmission pour récupérer les messages perdus/erronés. Ainsi, le protocole de planification distribuée peut supposer que les messages ne seront pas perdus. Ceci permet de simplifier le protocole. Lorsque le contrôle de topologie sélectionne un noeud voisin à partir de la liste NP pour se connecter en tant que nouveau voisin, il émet un événement de changement de topologie (ajout de liaison) qui (après les contrôles de cohérence dans le processus inactif) entraîne une transition à l'état d'ajout de liaison dans le processus d'affectation de tranches SP. TABLEAU 6 Procédure pour l'état inactif (Gestion d'événements SP) Case Type d'événement Message reçu : If le message reçu n'est pas cohérent avec l'état de la BD de messages de planification de liaisons pour ce Nbr~ID Rejeter le message Elseif type de message = REQSPTS If pas d'activité de messages SP en cours dans la BD de messages de planification de liaisons pour des ajouts de liaisons autres que la réception d'un message REQ~SPTS précédent de Nbr~ID Transition à l'état Traiter REQSPTS pour traiter le message Else Rejeter la nouvelle liaison et envoyer un message REPLYSPTS négatif à Nbr~ID End Elseif type de message = REPLY~SPTS Transition à l'état Traiter REPLYSPTS pour traiter le message Elseif type de message = CONFIRM Transition à l'état Traiter CONFIRM pour traiter le message Elseif type de message = DELETES Transition à l'état Traiter DELETES pour traiter le message End Vérifier les délais : Vérifier tous les délais If le délai a expiré pour une liaison dans l'état SP~Req Transition à l'état Ajout de liaison If le délai a expiré pour une liaison dans l'état SP~Reply Réinitialiser BD d'affectations de tranches pour la tranche de temps Ns et dans l'état Message de liaison de la BD de messages de planification de liaisons pour l'index Nbr ID End Notification d'ajout de liaison à partir du contrôle de topologie : If pas d'activité de messages SP en cours dans la BD de messages de planification de liaisons Transition à l'état Ajout de liaison pour ajouter Nbr~ID Else Reporter et replanifier Ajout de liaison End Défaillance de liaison ou suppression de liaison : Transition à l'état Suppression de liaison pour supprimer la liaison de Nbr~ID End End Le pseudo code pour le processus d'ajout de liaison est représenté au tableau 7. Il commence un processus qui requiert une coordination de l'affectation de tranches de temps SP et des échanges de messages protocolaires entre les deux noeuds voisins uniquement. Le noeud demandant la liaison envoie un message REQ~SPTS au noeud voisin candidat avec la liste des tranches de temps acceptables pour la liaison. La liste des tranches de temps candidates doit contenir au moins N tranches de temps dont au moins une tranche de temps semi-permanente SP. La liste peut également inclure éventuellement la totalité des N-l tranches de temps DA disponibles. Les tranches de temps disponibles ou à la demande peuvent être actuellement temporairement allouées pour un trafic à la demande. Cette liste sera ordonnée en fonction des priorités pour indiquer la préférence de tranche de temps qui entraîne le moins de perturbation dans les affectations de tranches de temps actuelles disponibles. En d'autres termes, la notation utilisée est qu'une tranche de temps n'est pas une tranche de temps SP à moins qu'elle n'ait déjà été allouée à une liaison de communication. L'une quelconque des 2N-1 tranches de temps peut être une tranche de temps SP. De cette manière, la liste des N tranches de temps envoyée est composée de tranches de temps libres ou d'une tranche de temps DA disponible. Il peut y avoir N-l tranches de temps SP, mais elles sont déjà allouées et ne sont pas sur la liste. Le message REQSPTS peut être envoyé jusqu'à MAXTRIES fois pour tenir compte des liaisons non fiables et des conflits avec d'autres affectations pouvant avoir lieu simultanément. Le délai dans la base de données de messages de planification de liaisons déclenche les nouvelles tentatives s'il n'y a pas de message REPLYSPTS du noeud voisin en réponse au message REQSPTS. Une fois le message REQSPTS envoyé, le processus retourne à l'état inactif pendant lequel d'autres événements peuvent être traités. TABLEAU 7 1 Procédure pour l'ajout de liaison au noeud Nbr ID (Génère un message REQ SPTS) If Numtries = MAX TRIES (Plus de tentatives) Réinitialiser l'état de la BD de messages de planification de liaisons pour l'index Nbr~ID (état de la liaison = libre et pas de délai pour une nouvelle tentative) Return à état inactif Else If tentative initiale au noeud Nbr ID Mettre Num tries = 1 dans la BD de messages de planification de liaisons pour l'index Nbr~ID Else Mettre Num tries = Num tries + 1 dans la BD de messages de planification de liaisons pour l'index Nbr~ID End Construire la liste Ls de tranches de temps pour offrir à Nbr ID Joindre la liste Ls au message REQSPTS et envoyer à Nbr ID Fixer le délai et l'état Message de liaison dans la BD de messages de planification de liaisons pour l'index Nbr~ID et dans la BD d'affectations de tranches Return à l'état inactif End Le voisin recevant un message REQ~SPTS aura sa transition de processus d'affectation de tranches SP à l'état REQ~SPTS de processus. La procédure pour traiter ce message est illustrée dans le tableau 8. Cette procédure prend la liste offerte de tranches de temps, Ls, et sélectionne sa tranche de temps préférée, Ns. Si le nombre de liaisons aux noeuds voisins, Num links, est inférieur à la limite N, la procédure sélectionne la tranche de temps qu'elle préfère à partir de cette liste. Puis, un message de réponse REPLY~SPTS avec cette sélection est envoyé. Si la liaison ne peut pas être acceptée ou s'il y a une autre affectation de tranche SP en cours, un message de réponse REPLYSPTS négatif est envoyé. La tranche de temps sélectionnée sera sélectionnée à partir d'une de ses N tranches de temps disponibles ou d'une de ses tranches de temps libres. Une tranche de temps disponible est soit une tranche de temps libre ou une tranche de temps DA disponible. Il y en aura au moins N si vous pouvons ajouter une autre liaison. Chaque noeud gère toujours ses tranches de temps de telle sorte qu'il y ait N tranches de temps disponibles à assigner comme tranches de temps semipermanentes (une à chacun des N noeuds voisins si autant de noeuds voisins sont disponibles). S'il accepte la liaison, alors il y aura au moins N-l autres noeuds voisins avec une tranche de temps semi-permanente allouée par noeud. La procédure fait également les modifications d'état appropriées dans la base de données de messages de planification de liaisons et dans la base de données d'affectations de tranches. TABLEAU 8 Procédure pour traiter un message REQ SPTS (de Nbr ID) If Num links Examiner la liste Ls des tranches de temps disponibles reçue à partir d'un noeud voisin potentiel Nbr~ID, comparer avec les allocations actuelles de la BD d'affectations de tranches, et sélectionner la meilleure affectation = Ns Faire les modifications appropriées à la BD d'affectations de tranches (la marquer comme SP~Reply) pour la tranche de temps Ns If la tranche de temps Ns était allouée DA Envoyer DELETE TS au noeud voisin qui a reçu la tranche de temps DA End Joindre le choix de tranche de temps, Ns, au message REPLY~SPTS et envoyer à Nbr~ID Fixer le délai et l'état Message de liaison (à SP~Reply avec la tranche de temps Ns) dans la BD de messages de planification de liaisons pour l'index Nbr~ID Return à l'état inactif Else Rejeter la nouvelle liaison et envoyer un message REPLYSPTS négatif à Nbr~ID Return à l'état inactif End Un message REPLY~SPTS reçu est traité comme représenté dans le tableau 9. Le choix de tranche de temps, Ns, reçu à partir du noeud voisin est extrait du message. Nous demanderons également au noeud de confirmer cette réponse avec un message CONFIRM positif ou négatif qui indique son accord pour l'utilisation de la tranche de temps allouée. Ce protocole de transfert tripartite élimine l'incertitude de l'issue du processus de planification. Si le message REPLY~SPTS est une réponse positive, le choix de tranche de temps, Ns, est alors examiné pour voir s'il y a toujours une affectation disponible d'une nouvelle tranche de temps SP pour la nouvelle liaison. Si elle est disponible, les modifications d'état appropriées dans les bases de données de messages de planification de liaisons et d'affectations de tranches sont alors effectuées. Puis, un message CONFIRM positif est retourné. Si le message REPLY~SPTS reçu est négatif, les bases de données de messages de planification de liaisons et d'affectations de tranches sont alors réinitialisées pour ce Nbr~ID. De même, si le choix de Ns n'est plus disponible, la base de données de messages de planification de liaisons est alors réinitialisée pour ce Nbr ID. Puis, un message CONFIRM négatif est envoyé au noeud voisin rejetant la liaison. TABLEAU 9 Procédure pour traiter un message REPLY SPTS de Nbr ID Extraire le choix de tranche de temps Ns du message REPLY SPTS de Nbr ID If (message REPLY~SPTS positif) and (le choix de Ns est toujours disponible dans la BD d'affectations de tranches) Faire les modifications appropriées dans la BD d'affectations de tranches (la marquer comme SP Reply) pour la tranche de temps Ns et dans l'état Message de liaison de la BD de messages de planification de liaisons pour l'index Nbr~ID If la tranche de temps NS était allouée DA Envoyer DELETETS au noeud voisin qui a reçu la tranche de temps DA End Créer un message CONFIRM pour Ns et l'envoyer à Nbr ID Incrémenter Num links Return à l'état inactif Elseif message REPLY~SPTS négatif Réinitialiser la DB d'affectations de tranches pour la tranche de temps Ns et dans l'état Message de liaison de la BD de messages de planification de liaisons pour l'index Nbr~ID Return à l'état inactif Else Réinitialiser l'état Message de liaison dans la BD de messages de planification de liaisons pour l'index Nbr ID Envoyer un message CONFIRM négatif à Nbr ID Return à l'état inactif End Le tableau 10 montre la procédure pour traiter les messages CONFIRM. Si le message CONFIRM est positif, la liaison est considérée comme ajoutée à la série de voisins. Le nombre de liaisons du noeud, Num links, est incrémenté. La tranche de temps assignée, Ns, est marquée SP~Alloc dans la base de données d'affectations de tranches, et l'état du message de liaison dans la base de données de messages de planification de liaisons est réinitialisé pour l'index Nbr~ID. Si le message est un CONFIRM négatif, les bases de données de messages de planification de liaisons et d'affectations de tranches sont réinitialisées pour ce Nbr~ID. TABLEAU 10 Procédure pour traiter un message CONFIRM de Nbr ID If message CONFIRM positif Faire les modifications appropriées dans la BD d'affectations de tranches (la marquer comme SP Alloc) pour la tranche de temps Ns Réinitialiser l'état Message de liaison dans la BD de messages de planification de liaisons pour l'index Nbr ID Incrémenter Num links Return à l'état inactif Else Réinitialiser la BD d'affectations de tranches (la marquer comme libre) pour la tranche de temps Ns Réinitialiser l'état Message de liaison dans la BD de messages de planification de liaisons pour l'index Nbr ID Return à l'état inactif End Il peut s'avérer nécessaire de désallouer une tranche de temps allouée pour une de plusieurs raisons. Si pendant le fonctionnement normal, une liaison est défaillante ou devient non fiable, c'est alors à la fonction de contrôle de topologie de résoudre le problème de liaison non fiable. Elle peut finalement générer un événement de changement de topologie (par exemple, une suppression de liaison) demandant au processus d'affectation de tranches SP de supprimer toutes les tranches assignées à la liaison. Les étapes impliquées dans cette procédure sont représentées dans le tableau 11. La liaison est désallouée en envoyant un message DELETE TS à partir du noeud demandant la désallocation de toutes les tranches de temps qui sont partagées avec l'autre noeud. De plus, les entrées appropriées de la base de données de messages de planification de liaisons et de la base de données d'affectations de tranches sont réinitialisées. TABEAU 11 Procédure de suppression de liaison du noeud Nbr ID (Génère un message DELETE TS) Extraire la liste de toutes les tranches de temps SP et DA, Ls, de la BD d'affectations de tranches assignées à la liaison à Nbr ID Construire un message DELETETS avec la liste Ls et l'envoyer à Nbr ID Réinitialiser la BD de messages de planification de liaisons pour l'index Nbr ID et la BD d'affectations de tranches pour toutes les tranches de temps de Ls Décrémenter Num links Return à l'état inactif La tableau 12 montre la procédure pour traiter un message DELETES reçu. La liste de tranches de temps désallouées, Ls, est extraite du message. Puis, l'état approprié dans la base de données d'affectations de tranches et dans la base de données de messages de planification de liaisons est réinitialisé. TABLEAU 12 Procédure pour traiter un message DELETE TS de Nbr ID Extraire la liste de tranches de temps, Ls, du message DELETES de NbrID Réinitialiser la BD d'affectations de tranches (la marquer comme libre) pour toutes les tranches de temps de la liste Ls Réinitialiser l'état Message de liaison dans la BD de messages de planification de liaisons pour toutes les tranches de temps de la liste Ls pour l'index Nbr~ID Décrémenter Num links Return à l'état inactif En résumé, l'objectif pour la fonction allouant les tranches de temps semi-permanentes est la connexion à un nombre de noeuds voisins aussi grand que possible, allant jusqu'à N. Si N noeuds voisins sont obtenus, chacun reçoit alors une seule tranche de temps semipermanente. Une fois qu'une nouvelle liaison est établie par ce protocole, les deux noeuds commenceront à opérer dans la tranche de temps SP nouvellement allouée. Ce fonctionnement testera la nouvelle liaison pour déterminer si une communication fiable peut être maintenue en utilisant la tranche de temps allouée. Ceci garantit qu'aucune interférence inhabituelle n'a lieu dans cette tranche de temps particulière. Si la liaison est testée comme non fiable, la fonction de contrôle de topologie sera alors notifiée pour que la tranche de temps puisse être désallouée et utilisée à d'autres fins. L'allocation de tranches de temps disponibles (à la demande) sera à présent traitée. Les tranches de temps disponibles doivent être allouées d'une manière qui est réactive aux demandes fluctuantes du trafic réseau. Supposons à nouveau que N soit fixe et choisi intelligemment en fonction de la taille et de l'environnement réseau. Supposons également que Ntrame = 2N-1. Pour permettre une granularité fine dans l'allocation de la capacité disponible, les tranches de temps seront divisées en mg sous-tranches de temps. Supposons pour le reste de la description suivante que mg = 2. Cela sera réalisé en définissant une soustranche de temps comme une allocation de tranche de temps spécifique qui se répète toutes les ms (ou seconde) trames. Une requête de tranches de temps disponibles d'un noeud à un noeud voisin est autorisée uniquement si au moins une tranche de temps semi-permanente est allouée pour la liaison entre ces deux noeuds. Lorsqu'une liaison a reçu au moins une tranche de temps semipermanente, un noeud peut alors demander une allocation périodique d'une tranche de temps toutes les ms (ou seconde) trames. Les messages utilisés pour planifier les tranches de temps disponibles peuvent être envoyés la liaison PA pour planifier les tranches de temps plusieurs trames avant qu'elles soient nécessaires, puisque la liaison a une allocation d'au moins une tranche de temps semi-permanente par trame. Un point clé pour une allocation efficace de tranches de temps disponibles est la mesure des exigences du trafic sur chaque liaison. Deux mesures seront requises. Premièrement, le trafic moyen mesuré envoyé sur une liaison (i, k) (en unités du nombre de tranches de temps par trame) sera désigné par Tlkse. Cette mesure inclura tout le trafic envoyé sur une ou plusieurs tranches de temps semi-permanentes par trame, ainsi que toutes les tranches de temps disponibles. De plus, nous avons également besoin de maintenir à jour une mesure actuelle de l'état de la file d'attente, Qik, pour une liaison (i, k). Des valeurs supérieures de Qik indiquent le besoin d'une allocation immédiate d'une ou plusieurs tranches de temps disponibles. Des montées occasionnelles de la demande peuvent produire des augmentations de Qik, qui doivent alors déclencher une requête de tranches de temps additionnelles de la capacité à la demande, jusqu'à ce que la taille de la file d'attente diminue. Le nombre total de tranches de temps (exprimé en quanta de tranche de temps avec ms = 2) allouées sur une liaison (i, k) sera désigné par N'. La demande en tranches de temps est définie comme suit : qui est une fonction du trafic mesuré plus la capacité additionnelle estimée requise qui est indiquée par la taille de la file d'attente. Puis, le nombre de tranches de temps requises sur cette liaison, T, feed, est comme suit : La métrique affectée à cette liaison est comme suit : Qui est une mesure du nombre estimé de tranches de temps additionnelles qui doivent être allouées à cette liaison par l'intermédiaire du mécanisme d'allocation de tranches DA. B est un terme d'écart qui peut nominalement être fixé à environ à de tranche de temps pour allouer une capacité excédentaire suffisante à chaque liaison pour éviter une importante mise en file d'attente. Alors que nous illustrons l'approche utilisant la métrique définie en (4), une variété d'autres formes de métrique peut également être utilisée comme base pour allouer les tranches de temps DA. La figure 8 montre un diagramme d'état du processus d'affectation de tranches DA 36. Le diagramme d'état et les échanges protocolaires sont similaires à ceux du processus d'affectation de tranches SP. Afin de simplifier le traitement de messages protocolaires, une seule tâche d'allocation de tranches de temps DA à la fois peut être en cours de traitement. Le processus inactif exécute la gestion d'événements dans la mesure où il vérifie les événements reçus avant d'autoriser un changement d'état à l'un des autres états. Ces opérations incluent ce qui suit. Contrôler les messages reçus pour déterminer s'ils sont cohérents avec l'état actuel de la base de données. Si un message est incompatible avec la base de données, il est rejeté. Certains délais peuvent indiquer que l'état de la base de données doit être réinitialisé. Ce processus exécute cette fonction. Il détermine également si l'affectation de tranches DA est optimale, compte tenu des besoins de charge de trafic du noeud. Il peut entraîner une transition à l'état ajouter une tranche DA, s'il détermine qu'une nouvelle tranche de temps DA doit être ajoutée à une liaison particulière. Il y a quatre types de messages de base requis dans le protocole d'affectation de tranches de temps DA, comme répertorié ci-dessous dans le tableau 13. Ils sont très similaires à ceux utilisés dans l'allocation de tranches SP. L'utilisation de ces messages s'explique d'elle-même et elle est conforme à la description précédente du processus d'allocation de tranches SP. TABLEAU 13 Type de message Fonction du message REQDATS Demande d'allocation d'une nouvelle tranche DA REPLY DATS Réponse au REQ~DATS reçu CONFIRM Réponse au REPLYDATS reçu DELETETS Message indiquant l'allocation d'une tranche de temps supprimée LINK METRIC Message diffusé aux noeuds voisins avec une métrique de liaison pour chaque liaison à un noeud voisin Un exemple d'affectation de tranches de temps DA est illustré sur la figure 9. Le noeud 1 désire ajouter une allocation de tranche de temps DA additionnelle pour sa liaison (1,2). L'échange de message protocolaire correspondant est représenté dans le tableau 5. Le noeud 1 initie l'échange en envoyant un REQDATS (L= (4.2, 5,6)) indiquant qu'il peut prendre en charge les allocations de toutes les tranches 5 et 6 et de la sous-tranche 4.2. Cette liste peut inclure toutes les tranches de temps libres et DA, dont les dernières sont moins requises. Lorsque le message de requête est envoyé, les changements appropriés sont effectués aux structures de données de messages de planification de liaisons et de tranches de temps. Le noeud 2 utilise les tranches de temps 1,3 et 6 comme allocations SP pour ses liaisons à ses 3 voisins, et les sous-tranches 2.1 et 3.2 comme allocations DA. Il peut sélectionner la sous-tranche 4.2 ou les deux sous-tranches de la tranche 5. Il choisit et envoie ce choix dans le message de réponse. Lorsqu'un message de réponse est envoyé, les changements appropriés sont également effectués aux structures de données de messages de planification de liaisons et de tranches de temps. Enfin, lorsqu'un message Confirm est envoyé ou reçu, l'état des tranches de temps appropriées passe à sous-tranche 4.2 allouée DA à la liaison (1,2) . TABLEAU 14 Noeud 1 Noeud 2 Détermine que la liaison du noeud 1 au noeud 2 requiert une tranche de temps DA additionnelle Envoie Msg perdu REQ~DATS (L= (4.2, 5, 6)) -7 Délai et nouvelle tentative Nouvel envoi -7 Reçu REQDATS (L= (4.2, 5,6,)) REQDATS (L= (4.2, 5,6)) REPLYDATS (Tranche REPLYDATS (Tranche 4.2) reçu 4.2) Envoyer CONFIRM (Tranche -7 CONFIRM (Tranche 4.2) reçu 4.2) Tranche 4.2 allouée DA à Tranche 4.2 allouée DA à la liaison (1,2) la liaison (1,2) L'approche suivante est utilisée à chaque noeud réseau pour allouer les (N-l) tranches de temps disponibles pour les liaisons directionnelles aux noeuds voisins. À l'aide de ces mesures, chaque noeud maintiendra continuellement la métrique de liaison, kt2A, car chacune de ses liaisons a reçu une tranche de temps semi-permanente. Chaque noeud utilisera cette métrique de liaison pour indiquer le besoin de tranches de temps de transmission additionnelles de chaque noeud voisin. Les plus grandes valeurs de Mlk'A indiquent les liaisons avec le plus grand besoin d'allocation de tranches de temps à la demande additionnelles. Une valeur positive de M, A indique le nombre de tranches de temps additionnelles requis, et une valeur négative indique le nombre de tranches de temps qui peuvent être rendues pour être réallouées. Comme les métriques Mill sont maintenues, si la plus grande métrique de liaison indique un besoin d'une allocation de sous-tranche additionnelle, et s'il existe des sous-tranches disponibles comme tranches libres ou comme allocation DA excédentaire à d'autres liaisons (indiqué à nouveau par une métrique faible), le processus passe alors à l'état ajouter une tranche DA et le processus consistant à rechercher une allocation de sous-tranche DA est initié. Comme pour les tranches de temps semi-permanentes, le noeud doit seulement coordonner la sélection de la tranche de temps DA à assigner pour une liaison directionnelle à un voisin avec ce voisin. Cela signifie qu'un voisin enverra une requête au voisin pour l'affectation de tranche de temps sur la liaison directionnelle, et recevra soit une autorisation de l'affectation soit un refus de la requête sur la même liaison. Le pseudo code initial décrivant les processus requis sur la figure 8 a été développé. Plusieurs événements peuvent avoir lieu qui doivent être traités par le processus d'affectation de tranches DA. La gestion d'événements est exécutée dans le processus inactif, comme représenté dans le tableau 6. Quatre catégories d'événements sont représentées : (1) message reçu, (2) vérifier les délais, (3) nouveau calcul des métriques de liaison, et (4) besoins de tranches de temps DA et suppression de tranches de temps DA. Les messages reçus sont tout d'abord vérifiés par rapport à la base de données de messages de planification de liaisons pour s'assurer que le message est compatible avec l'état actuel de la base de données. Par exemple, si nous avons envoyé une requête à un voisin, le message suivant attendu est une réponse. Afin de simplifier ce protocole distribué, une seule tâche d'échanges de messages protocolaires DA est autorisée à la fois. Ceci est appliqué dans la procédure en recherchant dans la base de données si d'autres échanges de messages DA sont en cours avant d'initier une transition ajouter la tranche DA, ou avant de traiter un message REQ~DATS. Si une tranche additionnelle ne peut pas être initiée parce qu'une autre tâche de protocole DA est actuellement en cours, l'ajout de tranche ne sera pas effectué. Elle peut être replanifiée naturellement à la prochaine opportunité de nouveau calcul des métriques de liaison et des besoins de tranches de temps DA. Les métriques de liaison seront recalculées périodiquement selon un calendrier préétabli. Une liaison qui a une métrique de liaison supérieure à un certain seuil, Max~metric~threshold, est un candidat pour obtenir une nouvelle sous-tranche DA. La liaison avec la métrique maximale qui excède ce seuil sera sélectionnée comme la liaison suivante à laquelle une nouvelle sous-tranche DA est allouée. Lorsqu'une nouvelle sous-tranche DA doit être allouée, si elle satisfait les conditions ci-dessus, une transition à l'état ajouter une tranche DA a alors lieu dans le processus d'affectation de tranches DA. TABLEAU 15 Procédure pour l'état inactif (Gestion d'événements DA) Case Type d'événement Message reçu : If le message reçu n'est pas cohérent avec l'état de la BD de messages de planification de liaisons pour ce Nbr~ID Rejeter le message Elseif type de message = REQDATS If pas d'activité de messages DA en cours dans la BD de messages de planification de liaisons pour des ajouts de liaisons autres que la réception d'un message REQ~DATS précédent de Nbr ID, transition à l'état Traiter REQDATS pour traiter le message Else Rejeter la nouvelle liaison et envoyer un message REPLYDATS négatif à Nbr~ID End Elseif type de message = REPLY~DATS Transition à l'état Traiter REPLYDATS pour traiter le message Elseif type de message = CONFIRM Transition à l'état Traiter CONFIRM pour traiter le message Elseif type de message = DELETE TS Transition à l'état Traiter DELETE TS pour traiter le message End Vérifier les délais : Vérifier tous les délais If le délai a expiré pour une liaison dans l'état DA Req, transition à l'état Ajouter une tranche DA If le délai a expiré pour une liaison dans l'état DA~Reply Réinitialiser la DB d'affectations de tranches pour la tranche de temps Ns et dans l'état Message de liaison de la BD de messages de planification de liaisons pour l'index Nbr~ID End Recalculer les métriques de liaison et les besoins en tranches de temps DA : Recalculer les métriques de liaison Envoyer les nouvelles métriques de liaison à tous les noeuds voisins dans un message LINK METRIC Trier les métriques de liaison et sélectionner Largest link metric If (pas d'activité de messages DA en cours dans la BD de messages de planification de liaisons) and (Largestlinkmetric > Maxmetricthreshold) Transition à l'état Ajouter une tranche DA pour ajouter une nouvelle affectation de tranche DA à Nbr ID End Suppression de tranche de temps DA : Transition à l'état Supprimer tranche de temps DA pour supprimer la tranche de temps de Nbr ID End Le pseudo code du processus de tranche DA additionnelle est illustré dans le tableau 16. Il commence un processus qui requiert une coordination de l'affectation de tranches de temps et des échanges de messages protocolaires entre les deux noeuds voisins uniquement. Le noeud demandant la liaison envoie un message REQ~DATS au noeud voisin candidat avec la liste de tranches de temps acceptables pour la liaison. La liste de tranches de temps candidates doit contenir toutes les sous-tranches libres et toutes les sous-tranches DA avec une métrique inférieure à un certain seuil, Minmetricthreshold. Les tranches de temps DA peuvent être actuellement temporairement allouées pour un autre trafic DA. Cette liste sera ordonnée en fonction des priorités pour indiquer la préférence de sous-tranche qui cause le moins de perturbation dans les affectations de tranches de temps à la demande en cours. L'ordre des priorités sera d'abord les tranches de temps libres, suivies des soustranches avec les métriques les plus faibles jusqu'à la métrique la plus grande inférieure à Minmetricthreshold. Afin de simplifier ce protocole distribué, une seule tâche d'échanges de messages protocolaires DA est autorisée à la fois. Ceci est appliqué dans la procédure inactive. Le message REQ~DATS n/est envoyé qu'une seule fois, mais il peut ne pas aboutir si le noeud voisin est actuellement en cours de traitement d'un autre échange protocolaire DA. Dans ce cas, le noeud recevra finalement un message REPLY~DATS négatif. La tentative d'ajout de tranche DA peut être renouvelée dans le cas où cette liaison a la plus grande métrique à la prochaine évaluation des métriques de liaison. Une fois le message REQ~DATS envoyé, le processus retourne à l'état inactif dans lequel d'autres événements peuvent être traités. TABLEAU 16 Procédure pour l'ajout d'une nouvelle sous-tranche DA à la liaison au noeud Nbr ID (Génère un message REQ DATS) Construire la liste Ls de tranches de temps (soustranches) pour l'offrir à Nbr ID à partir des tranches de temps libres et des sous-tranches DA avec une capacité excédentaire (Link~metric Minmetricthreshold) Joindre la liste Ls au message REQSPTS et l'envoyer à Nbr~ID Fixer le délai et l'état Message de liaison dans la BD de messages de planification de liaisons pour l'index Nbr ID et dans la BD d'affectations de tranches Le voisin recevant un message REQ~DATS verra son processus d'affectation de tranches DA passer à l'état REQSPTS. La procédure pour traiter ce message est représentée dans le tableau 17. Cette procédure prend la liste offerte de sous-tranches, Ls, et sélectionne sa sous-tranche préférée, Ns. La sous-tranche acceptée est la première sous-tranche de la liste, ls, qui est marquée libre dans la base de données d'affectations de tranches ou qui est allouée DA avec une métrique de liaison inférieure à Minmetricthreshold. Puis, un message de réponse REPLYDATS avec cette sélection est envoyé. Si la liaison ne peut pas être acceptée, ou s'il y a une autre affectation de tranche DA en cours, un message de réponse REPLYDATS négatif est envoyé. La procédure effectue également les modifications d'état appropriées dans la base de données de messages de planification de liaisons et dans la base de données d'affectations de tranches. TABLEAU 17 Procédure pour traiter un message REQ DATS (de Nbr ID) Examiner la liste des priorités Ls des sous-tranches disponibles reçue à partir de Nbr ID et la comparer avec les allocations en cours dans la BD d'affectations de tranches Sélectionner la meilleure affectation = Ns comme la sous-tranche de la liste qui est marquée libre dans la BD d'affectations de tranches ou qui est allouée DA avec Link metric Min metric threshold If aucune sous-tranche ne satisfait les conditions d'acceptation Rejeter la nouvelle liaison et envoyer un message REPLYDATS négatif à Nbr~ID Return à l'état inactif Else Faire les modifications appropriées à la BD d'affectations de tranches (la marquer comme DAReply) pour la tranche de temps Ns If la tranche de temps Ns était allouée DA Envoyer DELETE TS au noeud voisin qui a reçu la tranche de temps DA End Joindre le choix de tranche de temps, Ns, au message REPLY DATS et l'envoyer à Nbr~ID Fixer le délai et l'état Message de liaison (à DA~Reply avec la tranche de temps Ns) dans la BD de messages de planification de liaisons pour l'index Nbr~ID Return à l'état inactif End Un message REPLY~DATS reçu est traité comme représenté dans le tableau 18. Le choix de soustranche, Ns, reçu à partir du noeud voisin est extrait du message. Le noeud doit confirmer cette réponse avec un message CONFIRM positif ou négatif qui indique son accord pour utiliser la tranche de temps allouée. Comme indiqué dans le processus d'allocation SP, ce protocole de transfert tripartite élimine l'incertitude de l'issue du processus de planification. Si le message REPLY DATS est une réponse positive, le choix de sous-tranche, Ns, est alors examiné pour voir s'il y a toujours une affectation disponible d'une nouvelle sous-tranche DA pour la nouvelle liaison. Si c'est le cas, les modifications d'état appropriées dans les bases de données de messages de planification de liaisons et d'affectations de tranches sont alors effectuées. Puis, un message CONFIRM positif est retourné. Si le message REPLYSPTS reçu est négatif, les bases de données de messages de planification de liaisons et d'affectations de tranches sont alors réinitialisées pour ce Nbr~ID. De même, si le choix de Ns n'est plus disponible, la base de données de messages de planification de liaisons est alors réinitialisée pour ce Nbr~ID. Puis, un message CONFIRM négatif est envoyé au noeud voisin rejetant la liaison. TABLEAU 18 Procédure pour traiter un message REPYL DATS de Nbr ID Extraire le choix de tranche de temps Ns du message REPLYDATS de Nbr~ID If (message REPLY~DATS positif) and (le choix de Ns est toujours disponible dans la BD d'affectations de tranches) Faire les modifications appropriées dans la BD d'affectations de tranches (la marquer comme DA Reply) pour la tranche de temps Ns et dans l'état Message de liaison de la BD de messages de planification de liaisons pour l'index Nbr~ID If la tranche de temps Ns était allouée DA Envoyer DELETETS au noeud voisin qui a reçu la tranche de temps DA End Créer un message CONFIRM pour Ns et l'envoyer à Nbr ID Return à l'état inactif Elseif message REPLY~DATS négatif Réinitialiser la BD d'affectations de tranches pour la tranche de temps Ns et dans l'état Message de liaison de la BD de messages de planification de liaisons pour l'index Nbr~ID Return à l'état inactif Else Réinitialiser l'état Message de liaison dans la BD de messages de planification de liaisons pour l'index Nbr ID Envoyer un message CONFIRM négatif à Nbr~ID Return à l'état inactif End Le tableau 19 montre la procédure pour traiter des messages CONFIRM. Si le CONFIRM est positif, la soustranche sélectionnée doit être ajoutée à l'allocation de la liaison à Nbr~ID. La tranche de temps assignée, Ns, est marquée DA~Alloc dans la base de données d'affectations de tranches, et l'état du message de liaison dans la base de données de messages de planification de liaisons est réinitialisé pour l'index Nbr~ID. Si le message est un CONFIRM négatif, les bases de données de messages de planification de liaisons et d'affectations de tranches sont alors réinitialisées pour cette sous-tranche. TABLEAU 19 Procédure pour traiter un message CONFIRM de Nbr ID If message CONFIRM positif Faire les modifications appropriées dans la BD d'affectations de tranches (la marquer comme DA Alloc) pour la tranche de temps Ns Réinitialiser l'état Message de liaison de la BD de messages de planification de liaisons pour l'index Nbr~ID Return à l'état inactif Else Réinitialiser la BD d'affectations de tranches (la marquer comme libre) pour la tranche de temps Ns Réinitialiser l'état Message de liaison dans la BD de messages de planification de liaisons pour l'index Nbr ID Return à l'état inactif End Il peut s'avérer nécessaire de désallouer une tranche de temps allouée pour une de plusieurs raisons. Si pendant le fonctionnement normal, une liaison est défaillante ou devient non fiable, c'est alors à la fonction de contrôle de topologie de résoudre le problème de liaison non fiable. Elle peut finalement générer un événement de changement de topologie (par exemple, une suppression de liaison) demandant au processus d'affectation de tranches SP de supprimer toutes les tranches assignées à la liaison. Les étapes impliquées dans cette procédure sont représentées dans le tableau 11. La liaison est désallouée en envoyant un message DELETES à partir du noeud demandant la désallocation de toutes les tranches de temps qui sont partagées avec l'autre noeud. De plus, les entrées appropriées de la base de données de messages de planification de liaisons et de la base de données d'affectations de tranches sont réinitialisées. TABLEAU 20 Procédure pour supprimer une tranche de temps DA du noeud Nbr ID (Génère un message DELETE TS) Construire un message DELETETS contenant la soustranche DA, Ns, qui doit être supprimée et l'envoyer à NbrID Réinitialiser la BD de messages de planification de liaisons pour l'index Nbr~ID et la BD d'affectations de tranches pour la sous-tranche Ns Return à l'état inactif Le tableau 21 montre la procédure pour traiter un message DELETES reçu. La sous-tranche, Ls, à désallouer est extraite du message. Puis, l'état approprié dans la base de données d'affectations de tranches et dans la base de données de messages de planification de liaisons est réinitialisé. TABLEAU 21 Procédure pour traiter un message DELETE TS de Nbr ID Extraire la sous-tranche DA, Ns, du message DELETETS de Nbr~ID Réinitialiser la BD d'affectations de tranches (la marquer comme libre) pour la sous-tranche Ns Réinitialiser l'état Message de liaison dans la BD de messages de planification de liaisons pour la soustranche Ns Return à l'état inactif L'algorithme de planification de liaisons est également applicable à plusieurs faisceaux simultanés générés par le dispositif d'antenne phasé 16. Supposons l'extension à un système avec des noeuds, chacun employant plusieurs faisceaux d'antenne avec des récepteurs séparés, tel qu'un système phasé à faisceaux multiples (ou d'autres types d'antennes directionnelles, multiples). En outre, supposons que tous les noeuds ne doivent pas tous avoir le même nombre de faisceaux, c'est-à-dire que le noeud k a Bk faisceaux. C'est équivalent à Bk liaisons parallèles possibles à chaque tranche de temps. Nous étendons la discussion précédente (qui supposait un faisceau unidirectionnel) pour permettre aux faisceaux Bk d'être partagés en temps parmi une série de noeuds voisins plus grands que Bk. Même si les noeuds peuvent avoir chacun différents nombres de faisceaux, tous les noeuds doivent utiliser un format de tranche de temps commun et des trames avec un nombre de tranches de temps par trame pour chaque faisceau égal à Ntrame- Considérons une limite supérieure à chaque noeud k du nombre de tranches de temps assignées de façon semipermanente (SP) sur un quelconque de ses faisceaux Bk (et par conséquent le nombre maximal de noeuds voisins disponibles par faisceau) désignée par Nfaisceau. La valeur de Nfaisceau dépend uniquement du nombre de tranches de temps par trame et non du nombre de faisceaux. Comme dans (3), nous spécifierons que Nfaisceau doit satisfaire l'équation suivante : Ntrame = 2-Nfaisceau-1 (7) Supposons que tous les noeuds d'un réseau soient connectés par des liaisons directionnelles, où le noeud k a Bk faisceaux avec partage de faisceaux par sauts de temps et pointage sur ses noeuds voisins. En outre, supposons que le nombre de voisins autorisés par faisceau soit égal à Nfaisceau, la limite fixée du nombre possible de tranches de temps semi-permanentes autorisées par faisceau (avec une tranche de temps SP allouée par voisin). Si la valeur fixée de Nfaisceau pour chaque faisceau à chaque noeud voisin satisfait (7), tous les noeuds peuvent alors sélectionner une tranche de temps semipermanente différente pour chacune de ces liaisons et chacun de ses faisceaux par un accord mutuel avec le voisin de cette liaison sans tenir compte des couleurs sélectionnées par les autres noeuds situés à plus d'un saut. Ceci permet à chaque noeud de sélectionner ses Nfaisceau tranches de temps semi-permanentes pour chaque faisceau de manière très directe en communiquant uniquement avec son noeud voisin. En suivant cette stratégie, chaque noeud peut prendre en charge au moins voisins et chacun peut recevoir une seule tranche de temps SP avec pas plus de Nfaisceau telles tranches de temps allouées par faisceau. La vérification que Nfaisceau voisins par faisceau peuvent être pris en charge si (7) est satisfait suit directement à partir de la vérification de l'observation du cas de faisceau unique. Puis, si la totalité des Bk faisceaux ont leurs tranches de temps SP planifiées de la même façon, il est évident que le nombre de noeuds voisins qui peuvent être pris en charge est le produit du nombre de faisceaux et du nombre de voisins par faisceau résultant en (8). Un exemple d'affectation de tranches de temps SP entre deux noeuds avec un nombre inégal de faisceaux par noeud est représenté sur la figure 10. Dans cet exemple, le noeud 1 a 2 faisceaux et le noeud 2 a 3 faisceaux. Alors que les deux noeuds ont des nombres différents de faisceaux, les deux noeuds doivent utiliser la même structure de trame. Dans cet exemple, Ntrame = 5 tranches de temps par trame. À partir de (7) et de (8), cela permet au noeud 1 d'avoir un maximum de 6 voisins et au noeud 2 d'avoir un maximum de 9 voisins. Initialement, les deux noeuds ont un voisin de moins que le nombre maximal de voisins autorisés d'après les contraintes de (7) et de (8). Les allocations de tranches de temps/faisceaux SP sont représentées pour chaque liaison. Ces noeuds peuvent ajouter une liaison additionnelle entre eux tout en satisfaisant les contraintes de (7) et de (8). Le protocole de planification de liaisons trouvera un (e) faisceau/tranche de temps acceptable pour l'allocation SP pour chaque noeud, et il opère essentiellement de la même manière que dans le cas d'un faisceau unique. L'échange de message protocolaire correspondant est représenté dans le tableau 22. Le noeud 1 initie l'échange en envoyant un REQ~SPTS (L= (l, 2,3)) avec une liste d'au moins Nfaisceau tranches de temps candidates. Il faut noter que les 3 ID de faisceau sont désignés par a, b et c, et que le numéro de tranche est désigné par l'indice de l'ID de faisceau. Le noeud 1 doit identifier qu'il a utilisé les 3 tranches de temps SP possibles du faisceau a, mais qu'il a alloué uniquement 2 des 3 tranches de temps SP possibles de son faisceau b. Ainsi, il envoie une liste des 3 tranches de temps SP (disponibles sur le faisceau b) au noeud 2. Cette liste peut inclure toutes les tranches de temps libres et DA de ce faisceau. Lorsque le message de requête est envoyé, les changements appropriés sont effectués aux structures de données de messages de planification de liaisons et de tranches de temps. Le noeud 2 a précédemment alloué SP toutes les tranches de temps SP disponibles des faisceaux a et b pour ses liaisons à ses 8 voisins. * Ainsi, le faisceau c est le seul faisceau qui peut accepter une nouvelle allocation SP. Lorsqu'il reçoit le REQSPTS (L= (l, 2,3)) du noeud 1, il sélectionne le (la) faisceau/tranche de temps C3 comme le seul qui fonctionnera pour la nouvelle liaison (ayant précédemment alloué Ci et ci comme tranches de temps SP). Il envoie ce choix dans le message de réponse. Lorsqu'un message de réponse est envoyé, les changements appropriés sont également effectués dans les structures de données de messages de planification de liaisons et de faisceaux/tranches de temps. Enfin, lorsqu'un Confirm est envoyé ou reçu, l'état des tranches de temps appropriées passe à alloué SP à la liaison (1,2) . TABLEAU 22 Noeud 1 Noeud 2 Reçoit un événement d'ajout de liaison à partir de son contrôle de topologie pour une liaison du noeud 1 au noeud 2 Envoie REQ SPTS (L= (1,2, 3)) Envoi reçu REQ~SPTS (L= (1,2, 3) ) REPLYSPTS (tranche 3) Reçu e Envoie REPLY SPTS (tranche 3) Envoie CONFIRM (tranche 3)- > CONFIRM (tranche 3) reçu Faisceau/Tranche b3 Faisceau/Tranche C3 Alloué à la liaison (1,2) Alloué à la liaison (1,2) Les changements qui sont requis pour mettre en oeuvre l'algorithme/protocole de planification de faisceaux multiples sont directs et comme suit. Ajouter l'ID de faisceau comme variable dans l'état de la base de données de tranches de temps et de la base de données de messages de planification de liaisons. Utiliser (7) et (8) comme critères pour déterminer s'il est possible de planifier une nouvelle tranche de temps SP. Nous spécifions une valeur pour les paramètres Ntrame et Nbeam du réseau. Pour offrir une nouvelle tranche de temps SP à un voisin potentiel, l'algorithme doit d'abord trouver un faisceau pour lequel le nombre de voisins est inférieur à Nfaisceau. Ce faisceau peut ensuite être utilisé pour ajouter le nouveau voisin. Le message REQ SPTS que le noeud envoie à son voisin spécifiera Nfaisceau tranches de temps disponibles pour ce faisceau qui ne sont pas actuellement allouées SP. Lorsqu'il a reçu un message REQ~SPTS, le noeud doit rechercher un de ses faisceaux pour lequel le nombre de voisins est inférieur à Nfaisceau. Ce faisceau peut ensuite être utilisé pour ajouter le nouveau voisin. En comparant la liste de Nfaisceau tranches de temps du message REQ SPTS reçu aux Nfaisceau tranches de temps non allouées actuellement dans le faisceau sélectionné, au moins une tranche de temps peut être trouvée qui est commune aux deux listes. Cette tranche de temps peut être sélectionnée comme la tranche de temps à envoyer dans le message REPLY~SPTS. Une fois que le noeud émetteur aura reçu le message REPLYSPTS, les deux noeuds auront sélectionné leur faisceau et l'allocation de tranche de temps commune. Cet exemple supposait implicitement qu'une seule bande de fréquence est utilisée pour chacun des faisceaux. Dans ce cas, un noeud pourrait avoir plusieurs faisceaux communiquant simultanément sur la même bande sans interférence. Cette opération exempte d'interférence peut s'avérer difficile à prendre en charge en pratique. Une formulation similaire du problème pourrait être faite avec chaque faisceau opérant dans une bande de fréquence différente, c'est- à-dire que les faisceaux a, b et c de la figure 10 utilisent chacun une bande de fréquence différente. En ce qui concerne l'algorithme de planification, nous appliquerions les mêmes contraintes sur l'allocation de tranches de temps SP. Cependant, en allouant réellement les combinaisons tranches de temps/faisceaux, nous aurions besoin de trouver une allocation telle que les deux noeuds utilisent le même faisceau (ce qui est équivalent au fait d'utiliser la même bande) ainsi que la même tranche de temps. Ceci revient à rendre chaque combinaison faisceaux/tranches de temps différente de la perspective de planification. De cette manière, le nombre de tranches de temps disponibles est le nombre de faisceaux multiplié par la taille de trame. Dans ce cas, la contrainte relative à l'assignation de tranches de temps SP à des voisins potentiels est donnée par où B désigne le nombre de faisceaux. Cette contrainte sur le nombre de voisins est légèrement plus restrictive que celle de (7) et de (8) à cause de l'exigence que les noeuds partageant une tranche de temps SP doivent également utiliser le même canal faisceau/fréquence ainsi que la même tranche de temps. Pour l'exemple Ntrame = 5 et B = 3, la contrainte de (9) permet alors 8 voisins pour chaque noeud, tandis que les contraintes de (7) et de (8) permettront 9 voisins pour chaque noeud. L'exemple de problème de la figure 10 a 2 noeuds avec chacun 3 faisceaux, chaque faisceau opérant dans une bande de fréquence différente, c'est-à-dire que les faisceaux a, b, et c utilisent chacun une bande de fréquence différente. Supposons également que la taille de trame soit 5. Les deux noeuds ont déjà affecté 7 tranches de temps SP aux noeuds voisins et ainsi, d'après (9), ils peuvent ajouter chacun un voisin additionnel avec une tranche de temps SP leur permettant d'établir une liaison entre eux. Les tranches de temps SP affectées sont indiquées sur la figure, et les échanges de messages requis pour établir l'assignation de tranches de temps SP et la nouvelle liaison sont indiqués dans le tableau 23. L'échange de messages est initié par le noeud 1 en envoyant un message REQSPTS (L= (a4, as, b3, b4, bs, C3, C4, 05)) au noeud 2 qui doit inclure les 8 combinaisons faisceaux/tranches de temps qu'il n'a pas allouées précédemment comme tranches de temps SP. Dans cet exemple, le noeud 2 a déjà alloué 7 combinaisons faisceaux/tranches de temps qui n'étaient pas utilisées par le noeud 1 (qui étaient dans la liste des 8 combinaisons faisceaux/tranches de temps reçue dans le message REQ~SPTS). Ainsi, d'après (9), il doit y avoir au moins une combinaison faisceau/tranche de temps restante qu'il peut sélectionner pour l'allocation (es). C'est la combinaison faisceau/tranche de temps SP allouée à la liaison entre les noeuds 1 et 2 comme représenté à la fois sur la figure 11 et dans le tableau 23. TABLEAU 23 Noeud 1 Noeud 2 Reçoit un événement d'ajout de liaison à partir de son contrôle de topologie pour une liaison du noeud 1 au noeud 2 Envoie REQ~SPTS (L= (a4, a5,- Envoi reçu b3, b4, b5, C3, C4, C5)) REQSPTS (L= (a4, as, b3, b4, b5, C3, C4, C5)) REPLY~SPTS (faisceau/ REPLY SPTS tranche C5) reçu (faisceau/tranche cl) Envoie CONFIRM (faisceau/ CONFIRM reçu (faisceau/ tranche cl) tranche cl) Faisceau/Tranche C5 Faisceau/Tranche C5 Alloué à la liaison (1,2) Alloué à la liaison (1,2) La présente invention fournit ainsi un algorithme et un protocole de planification de liaisons complètement distribuées pour les réseaux d'antennes phasés. La description des détails sur l'algorithme/le protocole prenait le cas d'un faisceau unidirectionnel par noeud, qui est partagé en temps et pointé vers les noeuds voisins pendant la tranche de temps allouée pour cet accès. Cependant, l'approche peut être utilisée pour un nombre arbitraire de faisceaux dirigés par noeud. De nombreuses modifications et d'autres modes de réalisation de l'invention viendront à l'esprit de l'homme du métier tirant parti des enseignements présentés dans les descriptions précédentes et sur les dessins associés. C'est pourquoi, il faut comprendre que l'invention n'est pas limitée aux modes de réalisation spécifiques décrits, et que les modifications et les modes de réalisation doivent être inclus dans le cadre des revendications jointes. REVENDICATIONS 1. Réseau de communication sans fil comprenant : une pluralité de noeuds mobiles comprenant chacun un émetteur/récepteur, un dispositif d'antenne phasé connecté au dit émetteur/récepteur, et un contrôleur connecté au dit émetteur/récepteur pour planifier une tranche de temps semi-permanente respective pour chaque trame temporelle pour établir une liaison de communication avec chaque noeud mobile avoisinant et laisser au moins une tranche de temps disponible dans chaque trame temporelle, chaque trame temporelle ayant jusqu'à N tranches de temps semipermanentes et au moins 2N-1 tranches de temps disponibles, planifier la au moins une tranche de temps disponible pour servir également la liaison de communication avec un noeud mobile avoisinant en fonction de la demande en liaisons de communication, et diriger ledit dispositif d'antenne phasé vers chaque noeud mobile avoisinant pendant une communication avec celui-ci. 2. Réseau de communication sans fil selon la revendication 1, dans lequel ledit contrôleur affecte des niveaux de priorité aux liaisons de communication et élimine une des liaisons de communication en fonction des niveaux de priorité pour rendre disponible une tranche de temps semi-permanente afin d'établir une liaison de communication avec un nouveau noeud mobile avoisinant. 3. Réseau de communication sans fil selon la revendication 1, dans lequel ledit contrôleur affecte des niveaux de priorité aux liaisons de communication et planifie la au moins une tranche de temps disponible en fonction des niveaux de priorité. 4. Réseau de communication sans fil selon la revendication 1, dans lequel ledit contrôleur planifie une des tranches de temps semi-permanentes comme tranche de temps disponible si le nombre des liaisons de communication est inférieur à N. 5. Réseau de communication sans fil selon la revendication 4, dans lequel ledit contrôleur reaffecte la tranche de temps assignée à la demande à une tranche de temps semi-permanente si le nombre des liaisons de communication doit être égal à N. 6. Réseau de communication sans fil selon la revendication 1, dans lequel chaque liaison de communication est formée par un noeud mobile initiateur et un noeud mobile récepteur, et dans lequel ledit noeud mobile initiateur transmet une liste de tranches de temps semi-permanentes disponibles au dit noeud mobile récepteur. 7. Réseau de communication sans fil selon la revendication 6, dans lequel ledit noeud mobile récepteur transmet la sélection d'une des tranches de temps semi-permanentes au dit noeud mobile initiateur. 8. Réseau de communication sans fil selon la revendication 7, dans lequel ledit noeud mobile initiateur confirme la sélection de la tranche de temps semi-permanente sélectionnée au dit noeud mobile récepteur. 9. Réseau de communication sans fil selon la revendication 1, dans lequel chaque noeud mobile comprend en outre une antenne omni-directionnelle connectée au dit émetteur/récepteur pour échanger des informations positionnelles avec d'autres noeuds mobiles avoisinants. 10. Réseau de communication sans fil selon la revendication 1, dans lequel chaque noeud mobile comprend une pluralité d'émetteurs/récepteurs de telle sorte que ledit dispositif d'antenne phasé génère simultanément des faisceaux d'antenne multiples ; et dans lequel ledit contrôleur dirige ledit dispositif d'antenne phasé vers plusieurs noeuds mobiles avoisinants à l'intérieur d'une tranche de temps semipermanente planifiée. 11. Réseau de communication sans fil selon la revendication 10, dans lequel les faisceaux d'antenne multiples sont générés sur différentes fréquences. 12. Réseau de communication sans fil selon la revendication 1, dans lequel une pluralité de liaisons de communication sont établies à l'intérieur d'une tranche de temps semi-permanente planifiée, chaque liaison de communication incluant une paire différente de noeuds mobiles avoisinants. 13. Réseau de communication sans fil comprenant : une pluralité de noeuds mobiles comprenant chacun un émetteur/récepteur, une antenne directionnelle connectée au dit émetteur/récepteur, et un contrôleur connecté au dit émetteur/récepteur pour planifier une tranche de temps semi-permanente respective pour chaque trame temporelle pour établir une liaison de communication avec chaque noeud mobile avoisinant et laisser au moins une tranche de temps disponible dans chaque trame temporelle, planifier la au moins une tranche de temps disponible pour servir également la liaison de communication avec un noeud mobile avoisinant en fonction de la demande en liaisons de communication, et diriger ladite antenne directionnelle vers chaque noeud mobile avoisinant pendant une communication avec celui- ci. 14. Réseau de communication sans fil selon la revendication 13, dans lequel chaque trame temporelle a jusqu'à N tranches de temps semi-permanentes et au moins 2N-1 tranches de temps disponibles. 15. Réseau de communication sans fil selon la revendication 13, dans lequel ledit contrôleur affecte des niveaux de priorité aux liaisons de communication et élimine une des liaisons de communication en fonction des niveaux de priorité pour rendre disponible une tranche de temps semi-permanente afin d'établir une liaison de communication avec un nouveau noeud mobile avoisinant. 16. Réseau de communication sans fil selon la revendication 13, dans lequel ledit contrôleur affecte des niveaux de priorité aux liaisons de communication et planifie la au moins une tranche de temps disponible en fonction des niveaux de priorité. 17. Réseau de communication sans fil selon la revendication 13, dans lequel ledit contrôleur planifie une des tranches de temps semi-permanentes comme tranche de temps disponible si le nombre des liaisons de communication est inférieur à N. 18. Réseau de communication sans fil selon la revendication 17, dans lequel ledit contrôleur reaffecte la tranche de temps assignée à la demande à une tranche de temps semi-permanente si le nombre des liaisons de communication doit être égal à N. 19. Réseau de communication sans fil selon la revendication 13, dans lequel chaque liaison de communication est formée par un noeud mobile initiateur et un noeud mobile récepteur, et dans lequel ledit noeud mobile initiateur transmet une liste de tranches de temps semi-permanentes disponibles au dit noeud mobile récepteur. 20. Réseau de communication sans fil selon la revendication 19, dans lequel ledit noeud mobile récepteur transmet la sélection d'une des tranches de temps semi-permanentes au dit noeud mobile initiateur. 21. Réseau de communication sans fil selon la revendication 20, dans lequel ledit noeud mobile initiateur confirme la sélection de la tranche de temps semi-permanente sélectionnée au dit noeud mobile récepteur. 22. Réseau de communication sans fil selon la revendication 13, dans lequel chaque noeud mobile comprend en outre une antenne omni-directionnelle connectée au dit émetteur/récepteur pour échanger des informations positionnelles avec d'autres noeuds mobiles avoisinants. 23. Réseau de communication sans fil selon la revendication 13, dans lequel ladite antenne directionnelle comprend un dispositif d'antenne phasé. 24. Réseau de communication sans fil selon la revendication 23, dans lequel chaque noeud mobile comprend une pluralité d'émetteurs/récepteurs de telle sorte que ledit dispositif d'antenne phasé génère simultanément des faisceaux d'antenne multiples ; et dans lequel ledit contrôleur dirige ledit dispositif d'antenne phasé vers plusieurs noeuds mobiles avoisinants à l'intérieur d'une tranche de temps semipermanente planifiée. 25. Réseau de communication sans fil selon la revendication 24, dans lequel les faisceaux d'antenne multiples sont générés sur différentes fréquences. 26. Réseau de communication sans fil selon la revendication 13, dans lequel une pluralité de liaisons de communication sont établies à l'intérieur d'une tranche de temps semi-permanente planifiée, chaque liaison de communication incluant une paire différente de noeuds mobiles avoisinants. 27. Procédé pour établir des liaisons de communication pour une pluralité de noeuds mobiles, chaque noeud mobile comprenant un émetteur/récepteur, un dispositif d'antenne phasé connecté à l'émetteur/récepteur, et un contrôleur connecté à l'émetteur/récepteur, le procédé comprenant pour chaque noeud mobile les étapes consistant à : planifier une tranche de temps semi-permanente respective pour chaque trame temporelle pour établir une liaison de communication avec un noeud mobile avoisinant et laisser au moins une tranche de temps disponible dans chaque trame temporelle ; planifier la au moins une tranche de temps disponible pour servir également la liaison de communication avec un noeud mobile avoisinant en fonction de la demande en liaisons de communication ; et diriger le dispositif d'antenne phasé vers chaque noeud mobile avoisinant pendant une communication avec celui-ci. 28. Procédé selon la revendication 27, dans lequel chaque trame temporelle a jusqu'à N tranches de temps semi-permanentes et au moins 2N-1 tranches de temps disponibles. 29. Procédé selon la revendication 27, dans lequel chaque noeud affecte des niveaux de priorité aux liaisons de communication et élimine une des liaisons de communication en fonction des niveaux de priorité pour rendre disponible une tranche de temps semipermanente afin d'établir une liaison de communication avec un nouveau noeud mobile avoisinant. 30. Procédé selon la revendication 27, dans lequel chaque noeud affecte des niveaux de priorité aux liaisons de communication et planifie la au moins une tranche de temps disponible en fonction des niveaux de priorité. 31. Procédé selon la revendication 27, comprenant en outre l'étape consistant à planifier une des tranches de temps semi-permanentes comme tranche de temps disponible si le nombre des liaisons de communication est inférieur à N. 32. Procédé selon la revendication 31, comprenant en outre l'étape consistant à re-affecter la tranche de temps assignée à la demande à une tranche de temps semi-permanente si le nombre des liaisons de communication doit être égal à N. 33. Procédé selon la revendication 27, dans lequel chaque liaison de communication est formée par un noeud mobile initiateur et un noeud mobile récepteur, et dans lequel le noeud mobile initiateur transmet une liste de tranches de temps semi-permanentes disponibles au noeud mobile récepteur. 34. Procédé selon la revendication 33, dans lequel le noeud mobile récepteur transmet la sélection d'une des tranches de temps semi-permanentes au noeud mobile initiateur. 35. Procédé selon la revendication 34, dans lequel le noeud mobile initiateur confirme la sélection de la tranche de temps semi-permanente sélectionnée au noeud mobile récepteur. 36. Procédé selon la revendication 27, dans lequel chaque noeud mobile comprend en outre une antenne omnidirectionnelle connectée à l'émetteur/récepteur, le procédé comprenant en outre l'étape consistant à échanger des informations positionnelles avec d'autres noeuds mobiles avoisinants. 37. Procédé selon la revendication 27, dans lequel chaque noeud mobile comprend une pluralité d'émetteurs/récepteurs de telle sorte que le dispositif d'antenne phasé génère simultanément des faisceaux d'antenne multiples ; et qui comprend l'étape consistant à diriger le dispositif d'antenne phasé vers plusieurs noeuds mobiles avoisinants à l'intérieur d'une tranche de temps semi-permanente planifiée. 38. Procédé selon la revendication 37, dans lequel les faisceaux d'antenne multiples sont générés sur différentes fréquences. 39. Procédé selon la revendication 27, dans lequel une pluralité de liaisons de communication sont établies à l'intérieur d'une tranche de temps semipermanente planifiée, chaque liaison de communication incluant une paire différente de noeuds mobiles avoisinants. 40. Procédé pour établir des liaisons de communication pour une pluralité de noeuds mobiles, chaque noeud mobile comprenant un émetteur/récepteur, une antenne directionnelle connectée à l'émetteur/récepteur, et un contrôleur connecté à l'émetteur/récepteur, le procédé comprenant pour chaque noeud mobile les étapes consistant à : planifier une tranche de temps semi-permanente respective pour chaque trame temporelle pour établir une liaison de communication avec un noeud mobile avoisinant et laisser au moins une tranche de temps disponible dans chaque trame temporelle, chaque trame temporelle ayant jusqu'à N tranches de temps semipermanentes et au moins 2N-1 tranches de temps disponibles ; planifier la au moins une tranche de temps disponible pour servir également la liaison de communication avec un noeud mobile avoisinant en fonction de la demande en liaisons de communication ; et diriger l'antenne directionnelle vers chaque noeud mobile avoisinant pendant une communication avec celui- ci. 41. Procédé selon la revendication 40, dans lequel l'antenne directionnelle comprend un dispositif d'antenne phasé. 42. Procédé selon la revendication 40, dans lequel chaque noeud affecte des niveaux de priorité aux liaisons de communication et élimine une des liaisons de communication en fonction des niveaux de priorité pour rendre disponible une tranche de temps semipermanente afin d'établir une liaison de communication avec un nouveau noeud mobile avoisinant. 43. Procédé selon la revendication 40, dans lequel chaque noeud affecte des niveaux de priorité aux liaisons de communication et planifie la au moins une tranche de temps disponible en fonction des niveaux de priorité. 44. Procédé selon la revendication 40, comprenant en outre l'étape consistant à planifier une des tranches de temps semi-permanentes comme tranche de temps disponible si le nombre des liaisons de communication est inférieur à N. 45. Procédé selon la revendication 44, comprenant en outre l'étape consistant à re-affecter la tranche de temps assignée à la demande à une tranche de temps semi-permanente si le nombre des liaisons de communication doit être égal à N. 46. Procédé selon la revendication 40, dans lequel chaque liaison de communication est formée par un noeud mobile initiateur et un noeud mobile récepteur, et dans lequel le noeud mobile initiateur transmet une liste de tranches de temps semi-permanentes disponibles au noeud mobile récepteur. 47. Procédé selon la revendication 46, dans lequel le noeud mobile récepteur transmet la sélection d'une des tranches de temps semi-permanentes au noeud mobile initiateur. 48. Procédé selon la revendication 47, dans lequel le noeud mobile initiateur confirme la sélection de la tranche de temps semi-permanente sélectionnée au noeud mobile récepteur. 49. Procédé selon la revendication 40, dans lequel chaque noeud mobile comprend en outre une antenne omnidirectionnelle connectée à l'émetteur/récepteur, le procédé comprenant en outre l'étape consistant à échanger des informations positionnelles avec d'autres noeuds mobiles avoisinants. 50. Procédé selon la revendication 41, dans lequel chaque noeud mobile comprend une pluralité d'émetteurs/récepteurs de telle sorte que le dispositif d'antenne phasé génère simultanément des faisceaux d'antenne multiples ; et qui comprend l'étape consistant à diriger ledit dispositif d'antenne phasé vers plusieurs noeuds mobiles avoisinants à l'intérieur d'une tranche de temps semi-permanente planifiée. 51. Procédé selon la revendication 50, dans lequel les faisceaux d'antenne multiples sont générés sur différentes fréquences. 52. Procédé selon la revendication 40, dans lequel une pluralité de liaisons de communication sont établies à l'intérieur d'une tranche de temps semipermanente planifiée, chaque liaison de communication incluant une paire différente de noeuds mobiles avoisinants.