Titre de l'invention

Procédé de diffusion de paquets de données dans un réseau de nœuds mobiles et terminal associé.

Arrière-plan de l'invention

L'invention se situe dans le domaine des réseaux de communication ad-hoc.

Plus précisément, l'invention concerne la diffusion d'informations à travers un réseau ad-hoc formé de manière dynamique par une pluralité de nœuds mobiles communicants et se déplaçant selon des voies de circulation d'un réseau géographique déterminé dans lequel chaque nœud est apte à se localiser.

L'invention trouve une utilisation privilégiée mais non limitative dans les réseaux ad-hoc véhiculaires communément dénommés VANETs (« Vehicular Ad-hoc NETworks »), dans lesquels chaque nœud de communication est constitué par un véhicule se déplaçant selon des voies de circulation d'un réseau routier et en particulier, dans des environnements urbains.

La diffusion d'informations à travers ce type de réseaux trouve de nombreuses applications, telles que la diffusion d'informations relatives au trafic routier pour les systèmes de transport intelligents (« I ntelligent

Transportation Systems ») afin d'améliorer la sécurité et le confort des conducteurs.

Dans un article intitulé « Urban multihop broadcast protocol for inter-vehicule communication Systems » publié dans VANET' 04 :

Proceedings of the 1 ^st AQM International Workshop on Vehicular Ad Hoc

Networks, Philadelphia, PA, USA : ACM Press, Sept. 2004, pp. 76-85, G.

Korkmaz, E. Ekici, F. Ozgϋner, et LJ. Ozgϋner décrivent un protocole de diffusion de paquets de données par sauts multiples pour un système de communication inter-véhiculaire adapté à un environnement urbain.

Ce protocole utilise en combinaison deux types de diffusion de paquets : une diffusion locale au niveau de chaque intersection et une diffusion directionnelle entre deux intersections successives.

Ce protocole prévoit l'utilisation de répéteurs fixes placés au niveau de chaque intersection et destinés à transférer les paquets de données aux nœuds localisés au niveau d'une intersection, lors de l'étape

de diffusion locale. Lorsqu'un nœud porteur d'un paquet émis par le répéteur quitte une intersection et s'engage sur une voie de circulation, celui-ci participe à l'étape de diffusion directionnelle. Lors de cette étape de diffusion directionnelle, le nœud porteur du paquet envoie le paquet à son nœud voisin le plus éloigné, qui devient un nœud émetteur et transmet à son tour le paquet à son voisin le plus éloigné, sans utiliser d'informations relatives à la topologie du réseau.

Un inconvénient de ce type d'approche est qu'elle nécessite l'installation de répéteurs fixes au niveau de chaque intersection. Cette installation est fastidieuse et peut s'avérer coûteuse notamment lorsque l'étendue du réseau routier couvert par le réseau ad hoc inter-véhiculaire est vaste.

Objet et résumé de l'invention La présente invention permet de pallier aux inconvénients mentionnés ci-avant, en proposant un procédé de diffusion d'au moins un paquet de données dans un réseau formé par une pluralité de nœuds mobiles aptes à se déplacer dans un espace géographique.

Le procédé comprend une étape de diffusion locale au niveau d'une zone prédéterminée de l'espace géographique, appelée cellule, lors de laquelle ledit au moins un paquet de données est diffusé aux nœuds mobiles présents dans la cellule.

Conformément à la présente invention, le procédé comprend en outre : - une étape de réception dudit au moins un paquet de données;

- une étape de sélection au cours de laquelle le nœud mobile détermine s'il est candidat à la diffusion du paquet de données dans la cellule;

- une étape d'élection du nœud candidat en tant que nœud diffuseur du paquet de données dans la cellule, en fonction d'un temps de parcours estimé du nœud candidat vers le centre de la cellule.

L'étape de diffusion locale est mise en œuvre lorsque le nœud diffuseur se situe à proximité du centre de la cellule.

D'une part, l'étape de diffusion par un nœud diffuseur préalablement élu et localisé à proximité du centre d'une cellule permet d'émuler une infrastructure classique, en évitant l'installation et la maintenance d'équipements (répéteurs) destinés à diffuser des paquets de

données. En effet, un nœud élu diffusant un paquet de données à tous ses nœuds voisins localisés au voisinage du centre d'une cellule joue ponctuellement le rôle d'un répéteur qui serait installé au centre de cette cellule Ainsi, une cellule peut être vue comme une zone de diffusion activable par un nœud diffuseur, cette zone devenant active lorsqu'un nœud candidat est élu nœud diffuseur au niveau de la cellule et lorsqu'il existe des nœuds récepteurs du paquet localisés à l'intérieur de cette zone. L'élection du nœud diffuseur en fonction du temps de parcours estimé permet l'activation d'une cellule à intervalles de temps réguliers et par conséquent la diffusion du paquet de données de manière périodique.

Ainsi, la présente invention apporte une solution facile à mettre en œuvre, peu coûteuse et flexible en termes de déploiement, pour diffuser des paquets de données dans un réseau ad-hoc au niveau d'un ensemble de zones géographiques prédéfinies. La présente invention permet de diffuser des paquets de données de manière décentralisée, sans nécessiter d'échange d'informations de localisation entre les différents nœuds constitutifs du réseau. D'autre part, l'élection d'un nœud diffuseur au niveau de chaque cellule permet de désigner un nœud unique responsable de la diffusion du paquet de données dans une zone géographique, évitant ainsi de surcharger inutilement la bande passante du réseau ad-hoc par de multiples émissions. Selon une autre caractéristique de la présente invention, lors de ladite étape de sélection, le nœud mobile détermine qu'il est candidat à la diffusion du paquet de données à condition qu'il se dirige vers le centre de la cellule et qu'il soit localisé dans une zone d'ancrage centrée sur le centre et incluse dans la cellule. En déterminant de manière autonome un temps d'attente qui lui est propre, chaque nœud candidat participe au processus d'élection qui s'effectue de manière distribuée/décentralisée, évitant ainsi l'installation de toute infrastructure. Ceci est particulièrement avantageux pour déployer de nouvelles zones de diffusion à travers un réseau géographique étendu.

Selon une autre caractéristique de la présente invention, lors de l'étape d'élection :

- le nœud candidat calcule un temps d'attente, la valeur du temps d'attente calculée étant d'autant plus faible que le temps de parcours estimé du nœud candidat vers le centre de la cellule est proche d'un intervalle de temps de référence prédéterminé;

- à l'issue du temps d'attente, le nœud candidat diffuse un message de notification informant qu'il est élu nœud diffuseur s'il n'a pas reçu un tel message de notification d'un autre nœud. Ainsi, le nœud diffuseur élu au niveau d'une cellule correspond au nœud candidat susceptible d'atteindre le centre de la cellule en un temps qui est le plus proche possible de l'intervalle de temps de référence.

De manière avantageuse, l'intervalle de temps de référence prédéterminé correspond à la périodicité souhaitée de l'étape de diffusion locale.

Ainsi, le paquet de données est diffusé au bout d'une durée proche de l'intervalle de temps de référence, assurant ainsi une diffusion périodique du paquet de données localement au niveau de chaque cellule. Selon une autre caractéristique de la présente invention, la cellule est délimitée par un rayon égal à la portée de transmission d'un nœud mobile et la zone d'ancrage est délimitée par un rayon égal à la moitié de la portée de transmission d'un nœud mobile.

De manière avantageuse, un nœud candidat venant d'être élu nœud diffuseur et se trouvant en périphérie de la zone d'ancrage, peut communiquer avec tous les nœuds localisés dans cette zone d'ancrage, et en particulier avec ceux situés en périphérie de la zone d'ancrage et diamétralement opposés au nœud élu. Ainsi, un nœud candidat peut être élu nœud diffuseur, à condition que la distance qui le sépare du centre de la cellule soit inférieure ou au plus égale à la moitié de la portée de transmission d'un nœud mobile, la zone d'ancrage ayant un diamètre égal à cette portée de transmission.

Selon une autre caractéristique de la présente invention, lors de l'étape d'élection, un nœud candidat effectue les sous-étapes suivantes :

- estimation de la durée de parcours nécessaire pour atteindre le centre de la cellule ;

- calcul d'une probabilité d'être élu en tant que nœud diffuseur au niveau de la cellule, le calcul de la probabilité étant adapté pour que la valeur de la probabilité d'être élu soit d'autant plus élevée que la durée de parcours estimée pour atteindre le centre de la cellule est proche de l'intervalle de temps de référence ; et

- calcul du temps d'attente en fonction de la probabilité d'être élu, le calcul du temps d'attente étant adapté pour que la valeur du temps d'attente soit d'autant plus faible que la probabilité d'être élu est élevée.

En élisant un nœud dont la durée de parcours estimée pour atteindre le centre de la cellule est la plus proche possible de la période de diffusion, on s'assure que lorsque le nœud élu diffuse le paquet, celui-ci se trouve à proximité du centre de la cellule.

Selon une autre caractéristique de la présente invention, la probabilité d'être élu en fonction de la durée de parcours estimée est déterminée selon une fonction de Gauss d'espérance égale à l'intervalle de temps de référence.

Cette fonction permet d'obtenir une probabilité maximale pour un nœud candidat dont la durée de parcours estimée pour atteindre le centre de la cellule correspond à l'intervalle de temps de référence et une probabilité d'autant plus faible que la valeur absolue de la différence entre la durée de parcours estimée et l'intervalle de temps de référence est élevée.

Selon une autre caractéristique de la présente invention, le temps d'attente WT est déterminé en fonction de la probabilité d'être élu, d'après la formule suivante : WT(P ₁ ) = WT _Max (1 - P/Pmax) + γ. où WT _Ma χ désigne le temps d'attente maximal allouable à un nœud mobile, P,/P _m ax désigne la probabilité normalisée d'être élu, et γ, est un nombre généré de manière aléatoire.

Ainsi, le temps d'attente est d'autant plus faible que la probabilité normalisée est proche de 1. De manière avantageuse, le nombre γ, généré de manière aléatoire permet d'attribuer des temps d'attente différents à des nœuds candidats ayant calculé une valeur de probabilité identique. Ceci est en particulier le cas, lorsque les temps d'attente estimés sont rigoureusement égaux ou bien de la forme suivante : At = T ± x où x est un nombre réel désignant une valeur de décalage temporel par rapport à l'intervalle de temps de référence T.

Selon une autre caractéristique de la présente invention, l'espace géographique est un réseau de circulation comprenant une pluralité de voies de circulation formant entre elles une pluralité d'intersections, et chaque cellule est associée à une intersection. Le procédé selon l'invention est particulièrement bien adapté à des réseaux routiers denses et étendus comprenant un grand nombre d'intersections au niveau desquelles les paquets de données doivent être diffusés. I l est particulièrement avantageux de positionner un point d'ancrage au niveau du centre de chaque intersection, de manière à former une zone de diffusion au niveau de chaque intersection. En effet, dans les zones urbaines, la concentration de véhicules (nœuds mobiles) est en général la plus dense au niveau d'une intersection qui constitue un passage obligé pour la plupart des véhicules.

Le procédé de diffusion décrit ci-dessus étant réalisé de manière décentralisée au niveau de chaque nœud, la présente invention vise également un nœud mobile d'un réseau comprenant une pluralité de nœuds mobiles communicants.

Chaque nœud mobile comprend :

- des moyens de réception aptes à recevoir au moins un paquet de données ; et

- des moyens de diffusion aptes à diffuser ledit au moins un paquet de données à des nœuds mobiles situés à l'intérieur d'une zone de portée du nœud considéré.

Conformément à la présente invention, le nœud mobile comporte en outre :

- des moyens de sélection aptes à déterminer si ledit nœud mobile est candidat à la diffusion dudit paquet de données dans une zone prédéterminée d'un espace géographique associé audit réseau, appelée cellule; - des moyens d'élection aptes à élire le nœud candidat en tant que nœud diffuseur destiné à diffuser ledit au moins un paquet de données dans la cellule, en fonction d'un temps de parcours estimé du nœud candidat vers le centre de la cellule ; et

- des moyens d'activation aptes à activer les moyens de diffusion lorsque ledit nœud diffuseur se situe à proximité du centre de la cellule.

Selon une autre caractéristique de la présente invention, les moyens de sélection sont aptes à déterminer que le nœud mobile est candidat à la diffusion du paquet de données si le nœud mobile se dirige vers le centre de la cellule et s'il est localisé dans une zone d'ancrage centrée sur le centre et incluse dans la cellule.

Selon une autre caractéristique de la présente invention, le terminal comprend en outre :

- des moyens d'estimation pour estimer la durée de parcours nécessaire pour atteindre le centre de la cellule ; - des premiers moyens de calcul pour calculer une probabilité d'être élu en tant que nœud diffuseur au niveau de la cellule, les premiers moyens de calcul étant adaptés à calculer une valeur de probabilité qui est d'autant plus élevée que la durée de parcours estimée pour atteindre le centre de la cellule est proche de l'intervalle de temps de référence; et - des deuxièmes moyens de calcul pour calculer un temps d'attente en fonction de la probabilité d'être élu, les deuxièmes moyens de calcul étant adaptés à calculer une valeur de temps d'attente qui est d'autant plus faible que la probabilité d'être élu est élevée.

Ainsi, les deuxièmes moyens de calcul permettent de calculer un temps d'attente dont la valeur est d'autant plus faible que le temps de parcours estimé du nœud candidat pour atteindre le centre de la cellule est proche de l'intervalle de temps de référence prédéterminé.

Selon une autre caractéristique de la présente invention, les premiers moyens de calcul sont adaptés à déterminer la valeur de la probabilité d'être élu en fonction de la durée de parcours estimée selon une fonction de Gauss d'espérance égale à l'intervalle de temps de référence.

Selon une autre caractéristique de la présente invention, les deuxièmes moyens de calcul sont adaptés à déterminer le temps d'attente en fonction de la probabilité d'être élu, d'après la formule suivante : WT(P) = WT _M ax(1 - P/Pmax) + γ où WT _Max désigne le temps d'attente maximal allouable à un nœud mobile, P/P _ma χ désigne la probabilité normalisée d'être élu, et γ est un nombre généré de manière aléatoire. La présente invention vise également un système de communication sans fil comprenant une pluralité de nœuds mobiles,

lesdits nœuds se déplaçant selon des voies de circulation d'un réseau de circulation déterminé, ledit système étant caractérisé en ce que chaque nœud est un nœud mobile selon la présente invention tel que décrit ci- dessus. En variante, les différentes étapes du procédé de diffusion de paquets de données décrit ci-avant sont déterminées par des instructions de programmes d'ordinateurs.

En conséquence, l'invention vise également un programme d'ordinateur exécuté sur des moyens de traitement (processeur) d'un terminal, le programme comportant des instructions pour l'exécution des étapes du procédé de diffusion de paquets de données décrit ci-dessus, lorsque ce programme est exécuté par un ordinateur.

Ce programme peut utiliser n'importe quel langage de programmation et être sous la forme de code source, de code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable.

L'invention vise également un support d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur comprenant des instructions pour l'exécution des étapes du procédé de diffusion de paquets de données décrit ci-avant, lorsque ledit programme est exécuté sur un ordinateur et plus particulièrement sur des moyens de traitement (processeur) d'un terminal communicant sans fil.

Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en particulier téléchargé sur un réseau de type I nternet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté

pour exécuter ou pour être utilisé dans l'exécution du procédé de routage de paquets de données selon l'invention.

Brève description des dessins D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif et sur lesquels :

- la figure 1 illustre de manière schématique un réseau routier urbain à travers lequel circulent les nœuds d'un réseau ad-hoc et dans lequel la présente invention est mise en œuvre ;

- la figure 2 illustre sous forme d'organigramme, les étapes du procédé selon l'invention mises en œuvre pour la diffusion locale d'un paquet de données au niveau d'une intersection du réseau routier ; - la figure 3 illustre de manière schématique, un exemple de scénario dans lequel un ensemble de nœuds candidats est sélectionné pour l'élection d'un nœud diffuseur au niveau d'une intersection, conformément à la présente invention ;

- la figure 4 illustre sous forme d'organigramme, les étapes du procédé selon l'invention mises en œuvre pour l'élection d'un nœud diffuseur au niveau d'une intersection parmi les nœuds candidats sélectionnés, conformément à la présente invention ;

- la figure 5A illustre sous forme graphique, un premier exemple de la probabilité d'élection d'un nœud candidat conformément à la présente invention ;

- la figure 5B illustre sous forme graphique, un deuxième exemple de la probabilité d'élection d'un nœud candidat conformément à la présente invention ;

- la figure 5C illustre sous forme graphique, le nombre de nœuds mobiles dans une file d'attente au niveau d'une zone périphérique d'une intersection en fonction du temps d'arrivée d'un nœud ;

- la figure 6 illustre de manière schématique, un exemple de scénario dans lequel un nœud diffuseur est élu au niveau d'une intersection; - la figure 7 illustre de manière schématique, un exemple de scénario dans lequel un paquet de données est diffusé par le nœud

diffuseur élu au niveau d'une intersection et une étape de propagation directionnelle du paquet est amorcée vers des intersections voisines ; et

- la figure 8 illustre de manière schématique, la diffusion du paquet de données entre deux intersections successives, lors de l'étape de propagation directionnelle.

Description détaillée d'un mode de réalisation

La présente invention va être maintenant décrite de manière détaillée, dans le cadre d'un réseau ad-hoc inter-véhiculaire (VANET : « Vehicular Ad-Hoc Networks ») formé par une pluralité de nœuds mobiles se déplaçant dans un espace géographique constitué par un réseau routier en zone urbaine.

La figure 1 représente de manière schématique un réseau routier comprenant une pluralité de voies de circulations L ₁ , L ₁₂ , L ₁₃ , L ₂ , L ₃ , L ₃₄ , L ₂₄ , L ₄ , U, U formant entre elles une pluralité d'intersections J ₁ , J ₂ , J ₃ , J ₄ . Dans cet exemple illustratif, les voies de circulation sont représentées rectilignes. Toutefois, la présente invention s'applique indifféremment à toute configuration de réseau routier comportant des voies de circulation curvilignes et formant entre elles des angles quelconques. Chaque nœud mobile membre du réseau ad-hoc inter- véhiculaire est constitué par un véhicule apte à se déplacer le long des voies de circulation L ₁ , L ₁₂ , L ₁₃ , L ₂ , L ₃ , L34, L ₂₄ , L ₄ , L ₅ , U et à travers les intersections J ₁ , J ₂ , J ₃ , J ₄ du réseau routier.

Chaque nœud est apte à se localiser à tout instant dans le réseau routier. Pour cela, chaque véhicule est équipé d'un appareil conventionnel de navigation assistée par satellite comprenant au moins : - un récepteur, par exemple de type GPS (« Global Positioning System ») ou Galileo, permettant d'obtenir à chaque instant ses propres coordonnées géographiques ; et - une carte routière numérique représentative du réseau routier couplée au récepteur GPS pour visualiser la position instantanée du nœud mobile sur la carte routière.

On pourrait également envisager, dans un autre mode de réalisation, que ces informations de localisation soient transmises au nœud mobile par un équipement dédié du réseau.

Chaque nœud est équipé d'un terminal de communication sans fil, constitué par exemple, d'un émetteur/récepteur Wi- Fi™, de sorte que chaque nœud est apte à communiquer avec ses nœuds voisins selon le protocole I EEE 802.11. En particulier, le terminal de communication est apte à diffuser des paquets de données. L'accès au canal de communication est géré de manière classique selon la fonction DCF (« Distributed Coordination Function ») du protocole I EEE 802.1 1.

Le terminal de communication sans fil embarqué dans le nœud mobile peut bien sûr fonctionner selon toute autre technologie sans fil, telle que la technologie infrarouge par exemple.

Par la suite, le terme « nœud voisin » d'un nœud de référence désignera tout nœud situé dans le domaine de portée de transmission du nœud de référence. A titre d'exemple, le domaine de portée de transmission d'un nœud mobile est délimité par un rayon de portée fixé à 250 mètres d'après les recommandations du standard DSRC (« Dedicated Short Range Communications »).

Comme représenté sur la figure 1 , un point d'ancrage virtuel Ci, C ₂ , C ₃ , C ₄ de coordonnées géographiques fixes est défini au centre de chaque intersection notée respectivement J-i, J ₂ , J3, J ₄ . Chaque point d'ancrage virtuel Ci, C ₂ , C ₃ , C ₄ est identifiable par tout nœud mobile, au moyen de son appareil de navigation. En particulier, à l'approche d'un point d'ancrage virtuel, chaque nœud est apte à déterminer la distance qui le sépare de ce point d'ancrage virtuel, à partir de ses propres coordonnées géographiques instantanées et de celles du point d'ancrage virtuel.

Une cellule de couverture Z ₁ , Z ₂ , Z ₃ , Z ₄ de rayon égal à la portée de transmission d'un nœud mobile (R=250 m) est définie au niveau de chaque intersection Ji, J ₂ , J ₃ , J ₄ , de sorte que le centre d'une cellule de couverture coïncide avec un point d'ancrage virtuel Ci, C ₂ , C ₃ , C ₄ . Ainsi, par la suite, le terme « point d'ancrage virtuel » désignera le centre d'une cellule de couverture. Chaque cellule de couverture Z ₁ , Z ₂ , Z ₃ , Z ₄ délimite une zone de diffusion locale, dans laquelle un paquet de données est destiné à être diffusé par un nœud diffuseur à des instants de diffusion intervenant périodiquement. L'intervalle de temps de référence T entre deux instants de diffusion successifs est préalablement déterminé au niveau de chaque

point d'ancrage virtuel. Dans cet exemple, on suppose que l'intervalle de temps de référence T est le même pour tous les points d'ancrage virtuels, de sorte que chaque paquet de données est diffusé au niveau de chaque intersection avec une même périodicité. Les étapes du procédé selon l'invention mises en œuvre pour la diffusion locale d'un paquet de données D au niveau d'une intersection J ₁ vont être maintenant décrites en référence aux figures 2 et 3.

Lors d'une étape de réception E ₁ , un paquet de données D à diffuser est reçu par l'ensemble des nœuds situés dans la cellule de couverture Z ₁ de l'intersection J ₁ .

Dans cet exemple, on suppose que le paquet de données D est initialement inséré dans le réseau ad-hoc par une borne de diffusion fixe (non représentée) installée au bord d'une voie de circulation. Cette borne est située par exemple au niveau d'un point d'entrée d'une zone urbaine, de sorte que des nœuds entrant dans cette zone transportent le paquet de données D vers des intersections.

Lors d'une étape de sélection E ₃ , un ensemble de nœuds candidats 2, 3, 5, 7 à l'élection d'un nœud diffuseur est sélectionné au niveau de l'intersection J ₁ , le nœud diffuseur ayant pour fonction de diffuser le paquet de données D dans la cellule de couverture Z ₁ .

Lors de l'étape de sélection E ₃ , chaque nœud porteur du paquet de données D s'attribue le statut de nœud candidat, à condition qu'il se dirige vers le point d'ancrage virtuel C ₁ et qu'il soit localisé dans une zone d'ancrage A ₁ incluse dans la cellule de couverture Z ₁ , suite à la réception du paquet de données D lors de l'étape de réception E ₁ .

Par définition, la zone d'ancrage A est une zone centrée sur le point d'ancrage virtuel C ₁ et délimitée par un rayon R/2 égal à la moitié du rayon R de la cellule de couverture Z ₁ , c'est-à-dire à la moitié de la portée de transmission d'un nœud mobile (R/2 = 125 mètres), comme représenté sur la figure 3.

Ainsi, sur réception du paquet de données D, chaque nœud porteur du paquet de données D, détermine s'il est localisé dans la zone d'ancrage A- Pour cela, il vérifie au moyen de son appareil de navigation, si la distance qui le sépare du point d'ancrage virtuel C ₁ est inférieure à R/2 (moitié de la portée de transmission d'un nœud). En cas de vérification positive, le nœud détermine au moyen de son appareil de

navigation, s'il se déplace en direction du point d'ancrage virtuel C ₁ . Si tel est le cas, le nœud s'attribue le statut de nœud candidat. Tel est le cas des nœuds référencés 2, 3, 5, 7 localisés dans la zone d'ancrage A, comme représente sur la figure 3. Les nœuds référencés 1 , 4, 6 ne sont pas retenus en tant que nœuds candidats étant donné qu'ils s'éloignent du point d'ancrage virtuel C ₁ , bien qu'ils soient localisés dans la zone d'ancrage A-

De manière avantageuse, chaque nœud est apte à déterminer de manière autonome, s'il est candidat à l'élection du nœud diffuseur. Ainsi, la sélection des nœuds candidats s'effectue de manière totalement distribuée au niveau de chaque nœud, sans nécessiter d'échange d'informations entre les nœuds ni d'élément d'infrastructure centralisée.

Lors d'une étape d'élection E ₅ , un nœud diffuseur 7 est élu parmi l'ensemble des nœuds candidats 2, 3, 5, 7 préalablement déterminés lors de l'étape de sélection Eb. Cette élection s'effectue en fonction de la comparaison du temps de parcours estimé pour atteindre le point d'ancrage virtuel C ₁ par rapport à l'intervalle de temps de référence T déterminé entre deux instants de diffusion successifs au niveau du point d'ancrage virtuel. De manière avantageuse, l'élection du nœud diffuseur 7 pour assurer la diffusion du paquet de données D dans la cellule de couverture Z ₁ à un instant donné, permet d'optimiser l'utilisation de la bande passante du réseau ad-hoc, en évitant que plusieurs nœuds diffusent simultanément le même paquet de données D dans la même cellule de couverture Z ₁ . Lors d'une étape de portage E ₇ , le nœud diffuseur préalablement élu porte le paquet de données D à proximité du point d'ancrage virtuel C ₁ .

Lors d'une étape de diffusion locale E ₉ , le nœud diffuseur élu diffuse le paquet de données D à tous ses nœuds voisins, lorsqu'il se trouve au voisinage du centre de l'intersection J ₁ , de sorte que tous les nœuds se trouvant à cet instant dans la cellule de couverture de l'intersection reçoivent le paquet de données D.

L'étape d'élection E ₅ du nœud diffuseur 7 va maintenant être décrite de manière détaillée en référence aux figures 4, 5, 6. Cette étape d'élection E ₅ comprend un ensemble de sous-étapes décrites en référence

à la figure 4 et exécutées indépendamment par chaque nœud candidat 2, 3, 5, 7 préalablement sélectionné lors de l'étape de sélection E ₃ .

L'étape d'élection E ₅ commence à partir du moment où un ensemble de nœuds candidats 2, 3, 5, 7 est constitué (sous-étape d'amorçage Eξ50) au sein de la cellule de couverture Z-

Lors d'une première sous-étape de calcul E51, chaque nœud candidat estime une durée de parcours δt nécessaire pour atteindre le point d'ancrage virtuel Q, tel que : δt = δt _w + δt _m où :

δt _w désigne le temps d'attente du nœud au niveau de la périphérie d'une intersection ; et

δt _m désigne le temps nécessaire pour atteindre le centre de l'intersection à partir du moment où le nœud a traversé la zone périphérique de l'intersection, ce temps étant calculé en fonction de la vitesse du nœud et de sa distance à parcourir pour atteindre le centre de l'intersection.

Le temps d'attente δt _w occasionné par un feu tricolore au niveau de la zone périphérique d'une intersection est calculé en fonction du temps d'arrivée t _a du nœud d'après l'expression ci-dessous :

_{δ .} , C) (Expression 0) t _r : durée d'une phase pendant laquelle le feu tricolore est rouge

(secondes) t _g : durée d'une phase pendant laquelle le feu tricolore est vert (secondes)

C : durée d'un cycle (secondes) Q(t) : longueur de la file d'attente à l'instant t (véhicules)

Qo : longueur de la file d'attente initiale (véhicules) q : débit moyen d'arrivée au niveau du feu (véhicules /secondes) s : débit de départ au niveau du feu (véhicules /secondes) t _a : temps d'arrivée du nœud au niveau du feu (secondes) t _c : instant à partir duquel la file d'attente est vide (secondes)

δt _w (t) : temps d'attente à l'instant t (secondes)

La longueur de la file d'attente Q(t) à l'instant t est un nombre de véhicules déterminé d'après la fonction représentée graphiquement sur

la figure 5C. Comme illustré, un cycle de durée C est constitué des deux phases suivantes :

- une première phase de durée t _r , pendant laquelle le feu est rouge et pendant laquelle le nombre de véhicules dans la file d'attente augmente ; - une deuxième phase de durée t _g , pendant laquelle le feu est vert et pendant laquelle le nombre de véhicules dans la file d'attente diminue.

On suppose que la file d'attente est pleine (Q _ma χ) au moment où le feu passe du rouge au vert (changement de phase) et qu'à l'instant t _c , la file est vide. Si la file d'attente se vide avant que le feu passe au rouge, la file d'attente s'est totalement vidée. Dans ce cas, le temps t _c tombe dans l'intervalle de temps t _g définissant la deuxième phase comme illustré sur la figure 5C et la valeur Q ₀ = O au début du cycle suivant. Dans le cas contraire, Q ₀ ≠ O. Le temps t _c est calculé d'après l'expression suivante :

s - q

Pour calculer le temps δt _m , chaque nœud candidat calcule, au moyen de son appareil de navigation, la distance qui le sépare du point d'ancrage virtuel C ₁ , à partir de ses propres coordonnées géographiques et de celles du point d'ancrage virtuel. Chaque nœud candidat calcule ensuite au moyen de son appareil de navigation, la durée de parcours δt _m estimée pour atteindre le point d'ancrage virtuel C ₁ , en fonction de sa vitesse de déplacement v, et de la distance qui le sépare de ce point d'ancrage virtuel C ₁ . Bien évidemment, la durée de parcours δt _m est d'autant plus courte que la vitesse du nœud est élevée et/ou que la distance qui le sépare du point d'ancrage virtuel G ₁ est faible.

Ainsi les nœuds candidats référencés 2, 3, 5, 7 selon le scénario de la figure 6, déterminent de manière autonome leur temps de parcours respectif noté δt ₂ , δt ₃ , δt ₅ , δt ₇ en fonction de leur vitesse V ₂ , V ₃ , V ₅ , V ₇ respective et de leur distance de séparation respective par rapport au point d'ancrage virtuel G ₁ .

On considère le cas particulier, où les nœuds référencés 2 et 7 estiment des temps de parcours « symétriques » par rapport à l'intervalle de temps de référence T, de sorte que δt = T ± x où x désigne un nombre réel ; ainsi, par exemple : δt ₂ = T + x et δt ₇ = T - x.

On suppose en outre qu'au moment de l'obtention de la vitesse V ₅ du nœud 5, celui-ci est arrêté à un feu tricolore F, de sorte que sa vitesse est nulle (V ₅ =O), et que par conséquent, son temps de parcours estimé δt ₅ est supérieur à celui des autres nœuds : δt ₇ < δt ₂ < δt ₅ . Enfin, le nœud mobile 3 étant le nœud candidat le plus proche du point d'ancrage virtuel C ₁ et se déplaçant vers celui-ci C ₁ à une vitesse non nulle (v ₃ >0), son temps de parcours δt ₃ estimé est faible par rapport à celui des autres nœuds, tel que δt ₃ < δt ₇ < δt ₂ < δt ₅ .

Lors d'une deuxième sous-étape de calcul E ₅₂ , chaque nœud candidat calcule, au moyen de son système de navigation, une probabilité d'être élu en tant que nœud diffuseur. Chaque probabilité est déterminée en fonction de la durée de parcours estimée δt calculée lors de la première sous-étape de calcul E51 et en fonction de l'intervalle de temps de référence T. Pour cela, chaque nœud candidat 2, 3, 5, 7 calcule la probabilité d'être élu P (notée respectivement P ₂ , P ₃ , P5, P ₇ ) en fonction de sa durée de parcours estimée δt, (notée respectivement δt ₂ , δt ₃ , δt ₅ , δt ₇ ) en appliquant par exemple une fonction de Gauss classique représentée graphiquement sur la figure 5A et définie par l'expression suivante : P(δ0 ≡ (.Expression 1 ) où δt, est le temps de parcours estimé du i ^θmθ nœud candidat pour qu'il atteigne le point d'ancrage virtuel C ₁ ; σ est une constante temporelle correspondant à la largeur temporelle à mi-hauteur de la gaussienne représentative de la fonction P(δt) ; et T correspond à la valeur moyenne de la fonction P(δt,) et désigne l'intervalle de temps de référence entre deux instants de diffusion successifs au niveau du point d'ancrage C ₁ .

La valeur de la constante temporelle σ est définie en fonction de l'intervalle de temps de référence T et de la précision désirée pour l'élection du nœud diffuseur. Cette sélection sera d'autant plus sélective que la valeur de la constante temporelle est faible. Dans le cas extrême où σ=0, la gaussienne devient une impulsion de Dirac δ _τ telle que δ _τ (T)= 1 et δτ(t)=O pour tout t≠T. Dans ce cas, chaque nœud diffuseur est un nœud candidat pour lequel la valeur du temps de parcours estimé pour atteindre le centre de la cellule correspond précisément à celle de l'intervalle de temps de référence T. En pratique, il est peu probable de trouver pendant

chaque cycle de diffusion, un nœud candidat tel que son temps de parcours estimé soit exactement égal à T. Par conséquent, la valeur de σ sera choisie non nulle et ajustée, pour permettre à un nœud candidat dont le temps de parcours estimé est suffisamment proche de T d'être élu à chaque cycle de diffusion. La valeur de l'intervalle de temps de référence T ne pourra pas excéder une valeur de référence maximale T _max qui correspond au temps de parcours moyen pour traverser une intersection à une vitesse moyenne. De manière générale, la valeur de T sera choisie en fonction du type d'application considérée. En particulier, pour la diffusion d'informations relatives à la sécurité routière, l'intervalle de temps de référence T sera choisi suffisamment faible pour tenir compte du caractère éphémère des informations diffusées.

Dans cet exemple, la probabilité d'être élu P(δt) est calculée selon une fonction de Gauss. Bien évidemment, l'homme du métier pourra utiliser toute autre fonction dont la valeur maximale est atteinte pour δt = T et permettant d'obtenir une valeur de probabilité d'autant plus faible que la différence | T-δt| est élevée.

Ainsi, selon une variante de réalisation, la probabilité P est déterminée selon une fonction « triangle » représentée graphiquement sur la figure 5B et définie par l'expression suivante:

(.Expression 2) où τ est une constante réelle positive permettant de définir la largeur de la fonction triangle comme représenté sur la figure 5B ; P _Max correspond à la valeur de probabilité maximale telle que P _Max = P(T) = 1/τ de sorte que la somme de toutes les probabilités soit égale à 1 ; et T désigne l'intervalle de temps de référence.

Dans les cas représentés sur les figures 5A et 5B, la probabilité d'être élu P(δt) est d'autant plus élevée que la durée de parcours estimée δt pour atteindre le point d'ancrage virtuel Q est proche de l'intervalle de référence T. Autrement dit, la probabilité P est d'autant plus faible que la

différence | T-δt| est élevée. Ceci permet d'élire un nœud diffuseur dont la durée de parcours estimée pour atteindre le centre d'une cellule de couverture est d'autant plus proche de T.

Etant donné que les nœuds candidats 2 et 7 ont des temps de parcours estimés δt ₂ = T + x et δt ₇ = T - x respectivement, ces nœuds candidats 2 et 7 déterminent une probabilité d'être élu identique : P ₂ ≡ P(At ₂ ) = P7 ≡ P(δt ₇ ), comme illustré sur la figure 5A. Ainsi, les probabilités d'être élu pour les nœuds candidats 2, 3, 5, 7 représentés sur la figure 6 sont telles que P ₃ ≡ P(At ₃ ) < P(At ₅ ) < P ₂ = P7 comme illustré sur la figure 5A.

Lors d'une troisième sous-étape de calcul E ₅₃ , chaque nœud candidat calcule, au moyen de son appareil de navigation, un temps d'attente WT ₁ en fonction de la probabilité d'être élu P,≡ P(At ₁ ) obtenue à l'issue de la deuxième sous-étape de calcul (E ₅₂ ). Le temps d'attente WT ₁ est déterminé d'après l'expression suivante : r _ι (Expression 3) où WTMax est une constante réelle désignant le temps d'attente maximum allouable à un nœud candidat WT _MaX =WT ₁ (P ₁ = O), P,/P _ma χ désigne la probabilité d'élection normalisée du i ^θmθ nœud candidat, et γ, est un nombre réel généré de manière aléatoire.

Le temps WT ₁ déterminé selon l'expression 3 est d'autant plus court que la probabilité d'être élu P ₁ est élevée.

De manière avantageuse, l'utilisation du nombre γ, permet à plusieurs nœuds ayant des probabilités d'élection identiques de calculer un temps d'attente WT ₁ différent. C'est précisément le cas des nœuds 2 et 7 qui ont calculé la même valeur de probabilité P ₂ = P ₇ , le nombre aléatoire γ, permettant de les distinguer. Par exemple, en supposant que le nombre aléatoire γ ₂ généré pour le nœud 2 est supérieur au nombre aléatoire γ ₇ généré pour le nœud 7 (γ ₇ <γ ₂ ), les nœuds 7, 2 ont des temps d'attente WT ₇ , WT ₂ distincts, tels que WT ₇ < WT ₂ .

Le nœud candidat 3 dont la probabilité d'élection P(At ₃ ) est la plus faible (P(At ₃ ) < P(At ₅ ) < P(At ₂ ) = P(At ₇ )) calcule, d'après l'expression 3, un temps d'attente WT ₃ élevé, tel que WT ₃ > WT ₅ > WT ₂ > WT ₇ .

Dès lors que le temps d'attente WT ₁ est déterminé, chaque nœud candidat 2, 3, 5, 7 active un compteur initialisé avec sa valeur WT ₁

et décompte le temps à partir de cette valeur, lors d'une étape de décompte du temps EE ₅₄ , tant que le nœud n'est pas notifié de l'élection d'un nœud diffuseur.

Pour cela, lors d'une étape de test EE ₅₅ , chaque nœud candidat dont le compteur est activé, vérifie que son temps d'attente WT ₁ n'est pas écoulé. S son temps d'attente n'est pas écoulé, le nœud vérifie lors d'une étape de vérification EE ₅₆ , s'il a reçu un message de notification M indiquant qu'un nœud diffuseur a été élu, ce qui signifierait qu'un nœud candidat muni d'un temps d'attente plus court aurait déjà été élu nœud diffuseur (étape EE ₅₈ ). Tant qu'aucun nœud n'a diffusé le paquet de données D et que le temps d'attente WT ₁ d'un nœud donné n'est pas écoulé, ce nœud réitère les étapes EE ₅₄ , EE ₅₅ et EE ₅₆ . Si le nœud a reçu un message de notification, le compteur de ce nœud est désactivé et l'étape d'élection EE ₅ prend fin (étape EE ₅₈ ). Dès lors que le temps d'attente WT ₁ d'un nœud donné est écoulé et que le paquet de données D n'a été diffusé par aucun autre nœud jusqu'à cet instant, le nœud en question diffuse à tous ses nœuds voisins un message de notification M indiquant qu'il a acquis le statut de nœud diffuseur (étape EE ₅₈ ) marquant ainsi la fin de l'étape d'élection EE ₅ . En référence à la figure 6, les nœuds candidats 2, 3, 5, reçoivent le message de notification M les informant que le nœud 7 a été élu nœud diffuseur.

Dans l'exemple de la figure 6, le nœud candidat 7 ayant calculé le temps d'attente le plus faible (WT ₇ < WT ₂ < WT ₅ < WT ₃ ) est le premier nœud candidat à diffuser le message de notification M. De ce fait, il est élu nœud diffuseur 7. Sur réception du message de notification, les nœuds candidats restants 2, 3, 5 sont informés que le nœud 7 vient d'être élu nœud diffuseur, ce qui met fin à l'étape d'élection EE ₅ .

Etant donné que le nœud candidat 7 venant d'être élu est éloigné du point d'ancrage virtuel C ₁ d'une distance égale au plus à la moitié du rayon de transmission d'un nœud, on notera que celui-ci 7 peut transmettre le message de notification M à tous les nœuds situés dans la zone d'ancrage A- En particulier, si le nœud 7 s'était trouvé en périphérie de la zone d'ancrage A au moment de l'élection, c'est-à-dire à une distance égale à la moitié de la portée de transmission (R/ 2) du centre d'ancrage virtuel C ₁ , celui-ci aurait été apte à informer des nœuds

candidats localisés en périphérie de la zone d'ancrage A et diamétralement opposés par rapport à ce nœud 7. Dans ce cas limite, la distance séparant le nœud diffuseur élu 7 et les nœuds candidats restants aurait été égale au rayon de transmission d'un nœud. Lorsque le nœud diffuseur élu 7 arrive au niveau du point d'ancrage C ₁ de la cellule Z ₁ , il diffuse le paquet de données D à tous les nœuds voisins localisés dans cette cellule.

Les étapes du procédé décrit ci-dessus sont réitérées de sorte qu'un nœud diffuseur élu diffuse le paquet de données D à intervalles de temps régulier. Chaque itération définit un cycle, lors duquel le paquet de données est diffusé par un nœud diffuseur. En élisant à chaque cycle un nœud diffuseur dont le temps estimé pour atteindre le centre d'une intersection est le plus proche possible de l'intervalle de temps de référence T, on émule une infrastructure diffusant les données de manière périodique. Ainsi, l'intersection peut être considérée comme une zone de diffusion à l'intérieur de laquelle les données sont stationnaires.

Pour disséminer des données à travers l'ensemble du réseau routier, il est nécessaire d'assurer la transmission de ces données le long des voies de circulation qui relient les intersections entre elles. A cet effet, la présente invention prévoit une phase de diffusion progressive permettant de diffuser des données entre deux intersections successives, lors de laquelle un paquet de données est diffusé par un ensemble de nœuds diffuseurs élus successivement, au fur et à mesure que le paquet progresse le long d'une voie de circulation reliant les deux intersections successives.

La phase de propagation directionnelle est amorcée par des nœuds mobiles porteurs du paquet de données au niveau d'une intersection courante et se dirigeant en direction d'une intersection voisine, ces nœuds porteurs ayant reçu le paquet de données D préalablement diffusé par un nœud diffuseur dans une cellule de couverture.

Comme illustré sur la figure 7, le nœud diffuseur 7 localisé au centre de l'intersection J ₁ a diffusé le paquet de données D à tous ses voisins, et en particulier aux nœuds mobiles périphériques 20, 21 , 22 localisés en périphérie de la cellule de couverture Z ₁ et se déplaçant respectivement en direction d'une intersection voisine J-i, J ₃ , J ₂ . Le

transfert du paquet de données aux nœuds périphériques 20, 21 , 22 permet l'amorçage de la phase de propagation directionnelle vers chaque intersection voisine.

Comme illustré sur la figure 8, le paquet de données D est diffusé progressivement le long de la voie de circulation reliant deux intersections successives J ₁ et J ₂ , par des nœuds diffuseurs élus 22, 23, 27 successivement lors de la phase de propagation directionnelle.

La phase de propagation directionnelle permettant de propager le paquet de données de l'intersection J ₁ vers l'intersection J ₂ est mise en œuvre selon des algorithmes de diffusion connus de l'homme du métier.

Le terminal de communication sans fil de chaque nœud mobile comprend des moyens d'émission et de réception permettant à chaque nœud de diffuser et de recevoir les paquets de données D et les messages de notification M. L'appareil de navigation embarqué sur chaque nœud mobile comprend des moyens de traitement (processeur) aptes à effectuer de manière autonome et décentralisée, les étapes et sous-étapes relatives à l'élection d'un nœud diffuseur et décrites ci-avant.

L'appareil de navigation comprend des moyens logiciels aptes à déterminer si le nœud associé à l'appareil de navigation est candidat à la diffusion du paquet de données (moyens de sélection). Dans le cas où le nœud est candidat, l'appareil de navigation comprend en outre des moyens logiciels aptes à déterminer si ce nœud est élu nœud diffuseur (moyens d'élection). Dans le cas où le nœud est élu nœud diffuseur, l'appareil de navigation comprend en outre des moyens logiciels aptes à activer (moyens d'activation) les moyens d'émission du terminal de communication associé lorsque l'appareil de navigation détecte que le nœud se situe à proximité du centre de la cellule.

En particulier, les expressions mathématiques 0, 1 , 2, 3 décrites ci-avant sont programmées et sauvegardées dans une mémoire de l'appareil de navigation embarqué, puis exécutées par des moyens de traitement (processeur) associés au nœud

Applications industrielles Selon un premier exemple d'application, le procédé de diffusion selon l'invention est mis en œuvre pour disséminer des informations de

conditions de trafic utilisées pour optimiser le calcul du trajet d'un véhicule.

Selon un deuxième exemple d'application, le procédé de diffusion selon l'invention est mis en œuvre pour indiquer en temps réel à un automobiliste des places de parking disponibles aux alentours de sa position actuelle. On suppose que les places disponibles sont identifiées au niveau d'une borne qui diffuse périodiquement ces informations qui sont disséminées à travers les intersections par les véhicules (nœuds mobiles).

Selon un troisième exemple d'application, le procédé de diffusion selon l'invention est mis en œuvre sur un segment d'autoroute, pour disséminer des informations de sécurité routière dans une zone géographique où a lieu un événement (accident, travaux routiers) qui implique des modifications de circulation (ralentissements, contournements) pour les automobilistes. Dans ce cas, un paquet de données constituant un message d'alerte est généré manuellement ou automatiquement sur le lieu de l'événement. Ce paquet de données est propagé à partir de ce point jusqu'aux intersections avoisinantes où le paquet est diffusé à intervalles de temps réguliers conformément au procédé de diffusion selon l'invention. De cette manière, chaque véhicule (nœud mobile) circulant au niveau des intersections est alerté sur réception du paquet de données en pénétrant dans la zone d'alerte.