Brevet FR2967004A1 — publié le 20120504

SYSTEME ET PROCEDE DE DECOUVERTE DE VOISINAGE POUR OBJETS COMMUNICANTS La présente invention concerne le domaine technique général des protocoles asynchrones de découverte de voisinage - c'est-à-dire des objets n'ayant pas d'horloge globale en commun - pour objets communicants. On entend, dans le cadre de la présente invention, par « objet communiquant », un objet comprenant un émetteur pour émettre un signal vers un autre objet communiquant et/ou un récepteur pour recevoir les signaux émis par un autre objet communiquant. Dans le cas de deux objets communiquant les deux objets communiquant peuvent être mobiles ou fixes - comme par exemple un téléphone, une borne radiofréquence fixe ou tout autre terminal mobile ou fixe connu de l'homme de métier. L'invention trouve des champs d'application dès lors que des objets communicants sont utilisés. Dans la suite, on utilisera indifféremment les termes « noeud » et « objet » pour désigner les objets communiquant. Présentation de l'art antérieur La présente invention concerne la découverte de voisinage par des objets communicants : pour un objet communiquant, la découverte de voisinage consiste à découvrir l'ensemble des objets présents dans son voisinage (i.e. proximité / entourage). La notion de voisinage est directement liée à la capacité de communication des objets. Un objet A est dit voisin de B si A peut recevoir des informations de B. Il est intéressant de noter que la relation de voisinage n'est pas nécessairement réciproque. La découverte de voisinage pour objets communiquant peut avoir plusieurs finalités. Il peut s'agir d'un processus élémentaire nécessaire à la mise en oeuvre d'autres protocoles ou services plus complexes, comme par exemple un protocole de routage ou un protocole de découverte de services. Il peut également être l'objectif même de l'application si par exemple c'est la proximité des objets qui vise à être mesurée. Dans tous les cas, la découverte de voisinage est une problématique largement adressée dans le domaine des réseaux de communication sans-fil simple ou multi-sauts, notamment les réseaux dit « ad hoc » (également connus sous l'acronyme « MANET » signifiant « Mobile Ad-Hoc Networks » en anglo-saxon), les réseaux de capteurs (également connus sous le sigle « WSN» signifiant « Wireless Sensor Networks » en anglo-saxon), ou encore les réseaux personnels (également connus sous l'acronyme « BANET » signifiant « Body Area Networks » en anglo- saxon), etc. Dans ces domaines, la découverte de voisinage est généralement réalisée par l'envoi périodique de période A d'un signal - par exemple un paquet « Hello » - entre les objets présents sur le réseau. Plus précisément, chaque objet communiquant comprend des moyens de contrôle adaptés pour commander l'activation/la désactivation d'un émetteur et d'un récepteur de l'objet. Les moyens de contrôle de l'objet activent périodiquement l'émetteur pendant une durée d'émission ~. Durant la durée d'activation d'émission de l'émetteur, le récepteur est désactivé par les moyens de contrôle. La période A est imposée par l'application et correspond à la période à laquelle les objets mobiles veulent évaluer / découvrir leur voisinage. Cette période est liée à la dynamique des apparitions et disparitions des noeuds du réseau. Par exemple, dans le cas de la détection de voisinage sur le quai d'une gare, la période A sera plus courte que dans le cas de la détection de voisinage dans une salle de cinéma où les personnes portant les objets communiquant restent à une même position plus longtemps. Comme illustré sur le schéma de la figure 1, avec les systèmes et procédés de l'art antérieur, lorsque l'émetteur TX d'un objet est désactivé - i.e. en dehors de la durée d'émission - le récepteur RX est activé. En d'autres termes, lorsque l'objet n'est pas en émission, il est en réception sur son interface de communication. Un objet présent sur le réseau doit donc à la fois annoncer ses informations et écouter les informations provenant de ses voisins. Ce mécanisme de découverte simple est notamment utilisé dans le cadre des protocoles de routage ad-hoc, et notamment ceux standardisés à l'IETF. Un inconvénient de ce protocole concerne les risques de collisions qui peuvent survenir si deux objets voisins choisissent d'émettre leur information simultanément. En effet, l'émission simultanée de deux objets communicants à un même instant entraîne des collisions systématiques entre les objets et une perte des informations transmises par ces deux objets. Afin d'éviter ces collisions, un décalage aléatoire b (également connu sous le nom anglo-saxon de «jitter») est généralement ajouté à la période d'inter-émission, comme illustré Figure 2. En d'autres termes, deux activations successives de l'émetteur par les moyens de contrôle sont espacées dans le temps d'une période A plus un décalage aléatoire b. Un inconvénient de ces protocoles illustrés aux figures 1 et 2 est qu'ils consomment beaucoup d'énergie. Un but de la présente invention est de proposer un système et un procédé de découverte de voisinage permettant de limiter l'énergie consommée par les objets mobiles. Résumé de l'invention A cet effet, l'invention propose un système de détermination de voisinage 20 dans un réseau sans fil, le système comprenant des premier et deuxième noeuds, chaque noeud étant programmé pour détecter périodiquement les noeuds situés dans son voisinage toutes les périodes de temps A, remarquable en ce que - le premier noeud comporte un émetteur et des moyens de contrôle pour activer l'émetteur pendant une durée d'émission inférieure à la période 25 de temps A, l'émetteur émettant un signal d'identification pendant la durée d'émission ; - le deuxième noeud comporte un récepteur et des moyens de contrôle pour activer le récepteur pendant une durée de réception a inférieure à la différence entre la période de temps A et la durée d'émission le 30 récepteur écoutant les signaux provenant des noeuds voisins pendant la durée de réception a, les moyens de contrôle du deuxième noeud activant le récepteur une seule fois par période de temps A. Avantageusement, les noeuds peuvent être mobiles ou fixes. Par exemple, un noeud peut être mobile et l'autre fixe, les deux noeuds peuvent être mobiles, ou les deux noeuds peuvent être fixes. L'utilisation du système ci-dessus dans un environnement d'objets fixes garde du sens et correspond à une découverte de voisinage utilisée dans des problèmes de type "auto-configuration" (configuration automatique d'un réseau ou d'un ensemble de machines). Un exemple d'application concerne la mise en place d'un référentiel de temps commun si une machine est prise comme référence de temps. Les objets fixes peuvent également avoir un fonctionnement discontinu ou non permanent, sans pour autant bouger, entraînant la nécessité de mettre en place une mesure de voisinage dynamique pour savoir qui est présent à un moment donné dans le réseau. Des aspects préférés mais non limitatifs du système selon l'invention sont les suivants : - les moyens de contrôle du premier noeud sont adaptés pour activer l'émetteur plusieurs fois sur la période de temps A, l'émetteur émettant un signal d'identification « Hello » à chaque activation ; - la durée de réception a est inférieure au double de la durée d'inter-émission 26 entre deux émissions successives de l'émetteur, et est supérieure ou égale à la somme de la durée d'émission et de la durée d'inter-émission 6 entre deux émissions successives de l'émetteur sur une même période A ; - la durée de réception a est égale à la somme de la durée d'émission et de la durée entre deux émissions successives de l'émetteur sur une 25 même période A ; - le pas entre deux activations successives de l'émetteur est égal à la somme : - de la durée d'émission , - de la durée d'inter-émission 6 séparant deux états activés 30 successifs de l'émetteur et - d'un décalage temporel b inférieur à la période de temps A. ; - la durée du décalage temporel est aléatoire ; - chaque noeud comprend un filtre pour ne prendre en compte qu'un seul signal d'identification par noeud voisin par période. L'invention concerne également un procédé de détermination de voisinage dans un réseau sans fil incluant des premier et deuxième noeuds, chaque noeud étant programmé pour détecter périodiquement les noeuds situés dans son voisinage toutes les périodes de temps A, remarquable en ce que qu'il comprend - l'activation d'un émetteur du premier noeud pendant une durée d'émission inférieure à la période de temps A, l'émetteur émettant un signal d'identification pendant la durée d'émission ; - l'activation d'un récepteur du deuxième noeud pendant une durée de réception a inférieure à la période de temps A, le récepteur écoutant les signaux provenant des noeuds voisins pendant la durée de réception a, le récepteur étant activé une seule fois par période de temps A. Avantageusement, le procédé peut comprendre plusieurs étapes d'activation de l'émetteur sur une période de temps A, l'émetteur émettant un signal d'identification à chaque activation. L'invention concerne également un produit programme d'ordinateur comportant un code programme enregistré sur un support de données lisible par un ordinateur pour exécuter le procédé décrit ci-dessus lorsque le programme d'ordinateur est appliqué à un ordinateur pour être exécuté. Brève description des dessins D'autres avantages et caractéristiques ressortiront mieux de la description qui va suivre de plusieurs variantes d'exécution, données à titre d'exemples non limitatifs, à partir des dessins annexés sur lesquels : - la figure 1 et 2 illustrent des procédés d'art antérieur relatifs à la découverte de voisinage pour objets communicants ; - la figure 3 illustre schématiquement un exemple d'objet communiquant ; - les figures 4 à 6 illustrent schématiquement différents exemples de procédés relatifs à la découverte de voisinage pour objet communiquant. Description détaillée de l'invention. En référence à la figure 3, on a illustré un exemple d'objet communicant. Cet objet communiquant comprend un émetteur 1 apte à émettre un signal, un récepteur 2 apte à recevoir le ou les signaux émis par d'autres objets communiquant et des moyens de contrôle 3 pour activer/désactiver l'émetteur 1 et le récepteur 2 de l'objet communicants. Un but de l'invention concerne la « découverte asynchrone de voisinage pour un objet communiquant mobile induisant une faible consommation d'énergie et minimisant les interférences. Les termes utilisés dans le paragraphe précédent sont définis ci-dessous : - découverte de voisinage : un objet communiquant doit découvrir les objets avec lesquels il peut communiquer autour de lui ; - asynchrone : les objets n'ont pas de référentiel temporel commun : la découverte ne peut donc pas s'appuyer sur une notion d'heure commune ; - objet mobile : objet pouvant entrer et sortir d'un réseau (mode de fonctionnement discontinu). Le processus de découverte est donc un processus dynamique et continu dans le temps qui doit permettre la détection d'évènements comme l'arrivée ou la disparition de voisins ; - faible consommation d'énergie : les objets sont généralement contraints et autonomes d'un point de vue énergétique. Le protocole doit donc minimiser la consommation énergétique des objets ; - minimisation des interférences : les interfaces de communication des objets sont contraintes. Le protocole doit donc chercher à minimiser l'utilisation du canal de communication et les interférences qu'il génère. Comme mentionné ci-dessus, un inconvénient des protocoles de découverte de voisinage existant concerne la consommation d'énergie. Ceci est dû au fait que les interfaces de communication restent en permanence en mode réception pour écouter les annonces des voisins. En effet, les interfaces radio dans leur technologie actuelle consomment la même quantité d'énergie pour écouter le support quel que soit l'activité sur celui-ci. En référence à la figure 4, on a illustré un exemple de procédé permettant de réduire la consommation d'énergie des objets communicants. Dans ce mode de réalisation, chaque objet communicant est programmé pour découvrir son voisinage périodiquement toutes les périodes A. Au cours d'une période A, les moyens de contrôle 3 activent l'émetteur 1 de l'objet une fois pendant une durée d'émission c au cours de laquelle un signal d'identification - par exemple « He//o » - est envoyé à l'attention des autres objets communicants du réseau. A la fin de la durée d'émission , les moyens de contrôle 3 désactivent l'émetteur 1. En ce qui concerne le récepteur 2 de l'objet, celui-ci est activé par les moyens de contrôle 3 durant une durée de réception a. Avantageusement, le récepteur 2 n'est activé qu'une seule fois par période A. On notera que dans le cas des procédés illustrés aux figures 1 et 2, le récepteur 2 est activé en permanence lorsque l'émetteur 1 est désactivé, de sorte que la durée de réception a du récepteur 2 est égale la différence entre la période de temps A et la durée d'émission . Au contraire, dans le mode de réalisation illustré à la figure 4, des phases d'inactivité du récepteur 2 sont mises en place au cours de la période A, ces phases d'inactivité incluant des instants auxquels l'émetteur 1 est inactif. Ainsi, sur une période de temps A, la durée de réception a est inférieure à la différence entre la période A et la durée d'émission et préférentiellement inférieure à la moitié de la période A. En réduisant le temps au cours duquel le récepteur 2 est actif sur une période A, ce mode de réalisation permet de réduire l'énergie consommée par le récepteur 2 et donc par l'objet communicant. Comme les objets ne sont pas synchronisés, l'écart temporel entre deux activations de l'émetteur 1 et l'écart temporel entre deux activations du récepteur 2 sont généralement choisis aléatoirement. Le processus de découverte devient alors stochastique et un voisin n'est découvert que si son émission coïncide temporellement avec la période de réception du objet voisin. Ce mécanisme de découverte permet donc de réduire considérablement la consommation d'énergie au prix d'une perte significative de la précision de découverte du voisinage. Pour améliorer la précision de découverte du voisinage tout en réduisant la consommation d'énergie, on propose un mode de réalisation dans lequel, sur une période A, on augmente la fréquence des annonces - c'est-à-dire que les moyens de contrôle activent plusieurs fois l'émetteur sur un même période A - afin de maximiser la probabilité de réception de ces annonces par un voisin. Le principe consistant à limiter le temps d'écoute de chaque objet est conservé pour optimiser la consommation énergétique. Les figures 5 et 6 illustrent les principaux paramètres mis en place pour l'invention. Chaque objet recherche ses voisins périodiquement à la période A. Le récepteur 2 est activé une seule fois par période A pendant une durée de réception a. L'émetteur 2 est quant à lui activé une pluralité de fois par les moyens de contrôle 3 sur une même période A. A chaque activation, l'émetteur 1 émet un signal d'identification pendant la durée d'émission c. De préférence, la durée de réception a est supérieure ou égale à la somme de la durée d'émission c et de la durée d'inter-émission 6 séparant deux états activés successifs de l'émetteur. Ceci permet de garantir que le récepteur d'un objet reçoive le message émis par l'émetteur d'un objet voisin au court d'une période. L'homme du métier aura compris que la durée d'inter-émission correspond à l'écart temporel séparant deux émissions successives par l'émetteur, c'est-à-dire à la durée durant laquelle l'émetteur est désactivé par les moyens de contrôle entre deux activations successives. On notera que lorsque la durée de réception a est choisie égale à la somme de la durée d'émission c et de la durée d'inter-émission 6, la consommation d'énergie au niveau de l'objet communiquant est minimale. Pour minimiser sensiblement la consommation d'énergie dans l'objet communiquant tout en maximisant la probabilité de découverte d'un voisin, la durée de réception a est préférentiellement comprise entre le double de la durée d'inter- émission 26, et la somme de la durée d'émission c et de la durée d'inter-émission o entre deux activations successives de l'émetteur sur une même période A : 26 +G . La probabilité de collision et d'interférence augmente avec la densité du voisinage. Plusieurs objets peuvent essayer d'envoyer leur information simultanément. Avantageusement, le pas entre deux activations successives de l'émetteur peut être égal à la somme : - de la durée d'émission c - de la durée d'inter-émission 6 séparant deux états activés successifs de l'émetteur et - d'un décalage temporel b (ou «jitter») inférieur à la période de temps A. L'utilisation d'un «jitter », aléatoire et particulier à chaque objet, b entre deux émissions permet de décaler les paquets, et donc de limiter les risques de collision et d'interférences entre les objets. Pour éviter de détecter plusieurs fois le même objet voisin au court d'un même période de temps A, chaque objet peut comprendre un filtre pour ne prendre en compte qu'une seule annonce d'un objet voisin par période. En effet, comme la durée de réception a peut être supérieure au temps inter-émission 6 des annonces, plusieurs annonces d'un même objet voisin peuvent être reçues pendant la durée de réception a. Dans le mode de réalisation illustré à la figure 5, l'émetteur 1 et le récepteur 2 sont synchronisés l'un par rapport à l'autre. Ainsi, les instants d'activation et de désactivation de l'émetteur et du récepteur sont identiques à chaque période A. Dans le mode de réalisation de la figure 6, l'émetteur et le récepteur sont désynchronisés l'un par rapport à l'autre. Les instants d'activation et de désactivation de l'émetteur varient d'une période A à l'autre. Comme expliqué précédemment, l'invention repose sur un jeux de paramètres de gestion des temps d'émission et de réception des objets permettant de faire varier dans une large gamme le mode de fonctionnement du protocole de découverte de voisinage et ainsi de pouvoir mettre en place un compromis entre coût énergétique et précision de découverte adapté en fonction de l'application visée. Les paramètres utilisés sont les suivants: - A : macro-période de découverte de voisinage, cette période est liée à l'application et correspond à la période à laquelle le l'objet ou noeud mobile veut évaluer / découvrir son voisinage. Cette période est liée à la dynamicité des apparitions et disparition des objets du réseau ; - 6 période d'inter-émission de signal d'identification (paquets "Hello") correspondant au temps durant lequel l'émetteur est en mode désactivé ; - : durée d'émission du signal d'identification (i.e. d'un paquet "Hello") correspondant au temps durant lequel l'émetteur est en mode activé ; - a : durée de réception correspondant au temps d'écoute sur le support, c'est-à-dire au temps durant lequel le récepteur est en mode activé ; - b : décalage permettant de désynchroniser l'émission de deux objets voisins. Ce paramètre sert à réduire les collisions systématiques. Chaque objet dans le réseau possède sa propre horloge, les objets ne sont synchronisés ni à l'initialisation ni durant l'utilisation du système. Chaque noeud est responsable de la gestion de son temps interne. L'activité réseau d'un objet dans la phase de découverte de voisinage est partagée entre temps d'écoute et annonces d'informations. Les annonces d'information sont des paquets dont le temps d'émission est égal à une durée ~. La macro-période A de calcul du voisinage comporte des annonces et une période d'écoute de durée a. La durée a est de référence supérieure au temps inter-émission 6 des annonces plus de façon que : 0>a >a (1) Les paramètres liés à l'implantation du protocole de découverte de voisinage sont : A=6,0 - A représente le rapport entre le temps inter-émission et la fenêtre d'écoute du protocole. Ce rapport sert à gérer les paramètres de densité dans le voisinage ainsi que les interférences entre les différents objets ; - B représente le rapport entre le temps d'écoute et la macro-période. Ce 25 rapport représente le facteur de réduction en énergie par rapport à une version où l'écoute est permanente. Les paramètres A et B ne sont pas indépendants et sont liés par la variable 6. Ils sont ici nommés de façon explicite par soucis de clarté de la présentation. La 30 consommation d'énergie du protocole peut-être facilement modélisée. Le temps d'activation de l'émetteur, état dans lequel la consommation est la plus significative, est donnée pour une macro-période par les relations suivantes : ETX - PTX xi x (3) (4) 11 ER), =PR), X(a -[ 13' ixt) (5) a -Et PTX et PRX sont les puissances consommées par la radio associées aux émissions et à la réception des paquets. Les applications numériques sur des matériels et des temporisations usuelles montrent que les paramètres du protocole de découverte de voisinage permettent d'optimiser et de minimiser la consommation d'énergie pour les applications. Le protocole de découverte de voisinage décrit ci-dessus peut être implanté soit sous forme d'un automate (machine à état) temporisé avec un seul compteur de temps, soit sous forme de deux tâches (process, thread) concurrents accédant à l'émetteur et au récepteur de l'objet : - la tâche d'écoute et de mesure du voisinage contrôlant le temps d'écoute du support est représenté par une tâche périodique de période A écoutant le medium pendant une durée a ; - la tâche gérant les émissions est une tâche périodique de période 6+ c: cette tâche est prioritaire et peut envoyer un message au milieu d'une période d'écoute déclenchée par la première tâche. Les deux tâches concurrentes dont le fonctionnement est illustré sur la Figure 20 6 permettent d'implanter correctement le protocole de découverte de voisinage de façon simple. Une implantation sous forme maître - esclave peut aisément être mise en place pour gérer un mode synchronisation précis d'un système distribué. Un noeud particulier du système sert de référence temporelle, ses paquets « Hello » contenant 25 un compteur à rebours, en temps ou en nombre de paquets, annonçant le temps restant avant la prochaine macro-période A. Ce mode de synchronisation permet à tous les noeuds présents dans le voisinage d'être synchronisé au début de la prochaine macro-période A. L'imprécision du système de synchronisation est uniquement liée aux variations de temps de propagation du message sur le medium 30 radio selon les distances des noeuds en écoute par rapport au noeud maître. Ce temps est négligeable, voire non mesurable, dans les architectures mobiles actuelles. L'homme du métier aura compris que de nombreuses modifications peuvent être apportées au procédé et système décrits ci-dessus sans sortir matériellement des nouveaux enseignements présentés ici. Par exemple, le lecteur appréciera que le système et le procédé décrits ci- dessus ne se limitent pas à la détection de deux objets communicants, et qu'il peut être mis en oeuvre dans le cas de « n » objets communicants, n étant un entier supérieur à deux. Par ailleurs, les objets communicants peuvent communiquer en utilisant différents types de signaux. Par exemple, les signaux émis et reçus par les objets peuvent être des signaux radiofréquence, ou infrarouge ou tout autre type de signaux connus de l'homme du métier permettant la mise en oeuvre d'une communication sans fil entre les objets Il est donc bien évident que les exemples qui viennent d'être donnés ne sont que des illustrations particulières en aucun cas limitatives. REVENDICATIONS1. Système de détermination de voisinage dans un réseau sans fil, le système comprenant des premier et deuxième noeuds, chaque noeud étant programmé pour détecter périodiquement les noeuds situés dans son voisinage toutes les périodes de temps A, caractérisé en ce que - le premier noeud comporte un émetteur (1) et des moyens de contrôle (3) pour activer l'émetteur (1) pendant une durée d'émission inférieure à la période de temps A, l'émetteur émettant un signal d'identification pendant la durée d'émission ; - le deuxième noeud comporte un récepteur (2) et des moyens de contrôle (3) pour activer le récepteur (2) pendant une durée de réception a inférieure à la différence entre la période de temps A et la durée d'émission le récepteur (2) écoutant les signaux provenant des noeuds voisins pendant la durée de réception a, les moyens de contrôle (3) du deuxième noeud activant le récepteur une seule fois par période de temps A. 2. Système selon la revendication 1, dans lequel les moyens de contrôle du premier noeud sont adaptés pour activer l'émetteur plusieurs fois sur la période de temps A, l'émetteur émettant un signal d'identification « Hello » à chaque activation. 3. Système selon la revendication 2, dans lequel la durée de réception a est inférieure au double de la durée d'inter-émission 26 entre deux émissions successives de l'émetteur, et est supérieure ou égale à la somme de la durée d'émission et de la durée d'inter-émission 6 entre deux émissions successives de l'émetteur sur une même période A. 4. Système selon l'une des revendications 2 ou 3, dans lequel la durée de réception a est égale à la somme de la durée d'émission et de la durée entre deux émissions successives de l'émetteur sur une même période A. 5. Système selon l'une des revendications 1 à 4, dans lequel le pas entre deux activations successives de l'émetteur est égal à la somme : - de la durée d'émission c , - de la durée d'inter-émission 6 séparant deux états activés successifs de l'émetteur et - d'un décalage temporel b inférieur à la période de temps A. 6. Système selon la revendication 5, dans lequel la durée du décalage temporel est aléatoire. 7. Système selon l'une des revendications précédentes, dans lequel chaque noeud comprend un filtre pour ne prendre en compte qu'un seul signal d'identification par noeud voisin par période. 15 8. Procédé de détermination de voisinage dans un réseau sans fil incluant des premier et deuxième noeuds, chaque noeud étant programmé pour détecter périodiquement les noeuds situés dans son voisinage toutes les périodes de temps A, caractérisé en ce que qu'il comprend 20 - l'activation d'un émetteur du premier noeud pendant une durée d'émission c inférieure à la période de temps A, l'émetteur émettant un signal d'identification pendant la durée d'émission c ; - l'activation d'un récepteur du deuxième noeud pendant une durée de réception a inférieure à la période de temps A, le récepteur écoutant les 25 signaux provenant des noeuds voisins pendant la durée de réception a, le récepteur étant activé une seule fois par période de temps A. 9. Procédé selon la revendication 8, lequel comprend plusieurs étapes d'activation de l'émetteur sur une période de temps A, l'émetteur émettant un signal 30 d'identification à chaque activation. 10. Produit programme d'ordinateur comportant un code programme enregistré sur un support de données lisible par un ordinateur pour exécuter le procédé selon 10l'une des revendications 8 ou 9 lorsque le programme d'ordinateur est appliqué à un ordinateur pour être exécuté.