Brevet FR3087989A1 — publié le 20200501

PROCEDE ET DISPOSITIF DE TRANSMISSION SANS FIL DE DONNEES DANS DES RESEAUX Domaine de l'invention L'invention se situe dans le domaine des communications sans fil, et concerne plus particulièrement un procédé et un dispositif de transmission de données dans les réseaux sans fil maillés. Etat de la Technique Dans les réseaux de communication sans fil, la transmission d'un 10 fichier de données (102) d'un noeud source 'S' vers un noeud destination 'D' s'opère généralement via un ensemble de noeuds relais 'Ni' qui constitue un chemin de communication sans fil multi-bonds, tel que cela est illustré schématiquement sur la figure 1. Les noeuds intermédiaires 'ni' sont des relais de communication sans fil qui ne peuvent pas émettre et 15 recevoir simultanément. Ce mode de communication est communément appelé mode « half-duplex ». La technologie sans fil peut exploiter par exemple des ondes radio électromagnétiques, ou bien selon un autre exemple, des ondes acoustiques en milieu sous-marin. Dans ces environnements, le débit de communication d'un noeud à son voisin est 20 limité et la latence de communication n'est pas négligeable, en particulier s'il s'agit de communication acoustique. Par ailleurs, la distance entre les noeuds intermédiaires est supposée généralement être proche de la distance (en termes de portée radio) maximale offerte par la technologie sans fil utilisée. Il s'ensuit qu'une communication directe sur deux bonds 25 est typiquement impossible, un noeud récepteur est supposé détecter seulement les signaux émis par ses deux noeuds voisins immédiats. Aussi, un premier défi est de transmettre un fichier le plus rapidement possible d'un noeud émetteur au noeud destination à travers un réseau multi-bonds. 2 Une approche simple consiste à transmettre le fichier de données (102) depuis le noeud source `S' sur le premier bond (par abus de langage pour désigner la transmission vers le premier noeud intermédiaire `N1'), puis sur le second bond, etc., jusqu'à atteindre le noeud cible (D), comme cela est illustré en figure 2, à l'exemple des réseaux DTN (V. Cerf. et al., « Delay-Tolerant Networking Architecture », RFC 4838, April 2007). Les inconvénients de cette approche est qu'elle sous utilise les capacités de transmission en parallèle de fragments de fichiers sur plusieurs bonds. Une autre approche, dite multi-fragmentaire, consiste à fragmenter le fichier complet, puis à transmettre successivement les fragments de fichier (i.e. des paquets de données) sans attendre qu'un fragment « Fn soit arrivé à destination avant de transmettre un fragment « Fn+1 ». La figure 3 illustre un tel séquencement multi-bonds multi-fragments (3 fragments dans le cas illustré). Cette approche est plus efficace que la transmission du fichier complet, car elle exploite le parallélisme pour accélérer la transmission. Dans le cas illustré, il est possible d'utiliser jusqu'à trois bonds en parallèle. Le gain est d'autant plus élevé que le nombre de bonds est important, puisque d'un côté (l'approche de la figure 2) il y a l'utilisation simultanée d'un seul lien de communication, et de l'autre côté (l'approche de la figure 3) il s'agit d'une utilisation simultanée pouvant atteindre le tiers des liens de communication. La limite cependant est qu'il n'est pas possible d'aller au-delà du taux d'utilisation de un bond sur trois. Quand une transmission est en cours sur un bond `n', il n'est pas possible d'avoir des transmissions en cours sur les bonds 'n+1' et `n+2'. Autrement dit, il peut y avoir à un moment donné, au plus 1 bond sur 3 qui est utilisé pour transmettre un fragment. Ceci se comprend en considérant que deux bonds successifs ne peuvent pas être simultanément actifs en transmission, car un noeud devrait alors à la fois émettre et recevoir, et en considérant aussi qu'en cas de transmissions actives sur des bonds 'n' et 'n+2', il y aurait un noeud qui reçoit des signaux issus de ses deux voisins immédiats et qui ne pourrait alors 3 décoder ni l'un ni l'autre car chacun est une interférence pour l'autre. Cela conduit à la survenue d'une « collision ». Pour pallier ces inconvénients et réaliser une approche optimale (i.e. parallélisation de la transmission en multi-bonds), une solution 5 consiste à séquencer dans le temps les fragments émis par le premier noeud. Une fois un fragment « Fn » transmis par ce noeud, ce dernier est mis en état d'attente pendant le temps nécessaire à ce que le fragment Fn ait été reçu et envoyé par les deux prochains noeuds sur le chemin vers le destinataire, puis à transmettre le fragment Fn+1 une fois ce 10 temps d'attente expiré. Si les temps de transmission sont reproductibles, ce séquencement simple peut suffire à garantir un comportement optimal. Cependant, cette solution n'est pas satisfaisante car elle suppose de fixer un temps de pause (i.e. état d'attente) arbitraire et elle ne permet pas de s'adapter à la diversité des conditions de transmissions telle qu'on 15 peut l'observer en pratique. En effet, les bonds n'ont souvent pas la même distance, ils ne souffrent pas du même niveau d'interférence, etc. Aussi pour contourner ces difficultés, il est possible d'augmenter le temps de pause. En prenant un temps de pause correspondant au temps nécessaire pour propager un fragment sur trois bonds lorsque les 20 conditions de transmissions sont bonnes (c'est-à-dire que les bonds ne sont pas en limite et que les niveaux d'interférence sont faibles) et en multipliant ce temps par deux, voire par trois, il est probable que tout risque de collision dans la transmission multi-fragments multi-bonds soit évité. Par contre, les performances d'un tel système sont très sous 25 optimales, puisque la vitesse de transmission du fichier de bout en bout sera très inférieure à ce qu'elle pourrait être. Par ailleurs et plus généralement, la problématique évoquée dans le contexte des réseaux linéaires existe dans le contexte des réseaux maillés ou « mesh » selon l'anglicisme consacré. La figure 4 illustre 30 schématiquement un contexte de réseau mesh, où en général un noeud passerelle assure le passage entre le réseau mesh et le réseau Internet. 4 Ce noeud passerelle (ou Gateway en anglais) est alors la destination 'D' (ou respectivement la source 'S') de toutes les données émises (ou respectivement reçues) par les noeuds 'Ni' du réseau mesh. Une fois établi un chemin de routage entre un noeud du réseau mesh et le noeud 5 passerelle, la problématique est alors de savoir comment séquencer la transmission de fragments de fichiers sur ce chemin de façon à transmettre un volume de données le plus rapidement possible du noeud source au noeud passerelle. Les réseaux mesh sont généralement constitués de noeuds qui 10 n'ont pas la capacité d'émettre et de recevoir en même temps. Lorsqu'un noeud doit transmettre un paquet de données à l'un de ses voisins, il existe le risque que ce paquet ne soit pas reçu si une collision est intervenue du fait de la transmission simultanée d'un autre paquet par un noeud voisin qui a perturbé le noeud récepteur. Ce phénomène peut être 15 réduit par l'application d'une fonction d'écoute du canal avant transmission : un noeud qui doit transmettre un paquet va écouter le canal de transmission pour s'assurer qu'il est silencieux, puis va basculer en mode émission et transmettre le paquet. Cependant, ce principe ne peut que réduire et non éviter le risque 20 de collision, et ce pour deux raisons majeures : La détection d'absence de signal émis (silence du canal) reste une notion relative : le noeud émetteur peut considérer que le canal est silencieux alors que le canal n'est en fait pas silencieux du point de vue du noeud récepteur qui peut percevoir des signaux émis par ses 25 propres voisins, lesquels peuvent être indétectables pour le noeud émetteur ; et Le silence du canal avant la transmission d'un paquet ne signifie pas l'exclusivité du canal pendant cette transmission. Deux noeuds voisins devant émettre peuvent détecter le silence du canal simultanément, et 30 basculer en mode transmission simultanément aussi, ce qui provoque des transmissions simultanées et donc des risques de collision. 5 Pour contourner cette difficulté, des extensions au principe CSMACA (« Carrier Sense Multiple Access with Collision Avoidance ») permettent de prévoir des messages d'acquittement du paquet reçu par le récepteur. Le paquet peut alors être répété jusqu'à réception d'un 5 acquittement, de sorte que la transmission est finalement effective même s'il y a des collisions. Des compteurs aléatoires de retransmission sont alors introduits pour éviter le risque de collisions « à répétition ». Le principe CSMA-CA est défini par exemple par l'IEEE (Institute of Electrical and Electronics Engineers) dans les normes WiFi IEEE 802.11. 10 Une variante au principe CSMA-CA peut consister dans la mise en place de mécanismes de réservation via des signaux ou messages courts RTS ( 4 octets, codes ASCII: 'p','i','n','g Au niveau MAC, un message de sondage « ping » est adressé au noeud parent du noeud enfant initiateur du message de sondage ping. 14 Ces messages sont envoyés régulièrement, jusqu'à réception d'un message « pong ». La figure 7 montre un cas où deux premiers messages « ping » (illustrés par les traits pointillés) ne sont pas reçus par le noeud parent NB, afin d'illustrer que des défauts de communication 5 peuvent exister. Selon l'exemple, le troisième message « ping » qui est envoyé est bien reçu par le noeud parent NB. Le noeud NB envoie (704) à son tour un message de sondage de type « yin » vers son parent, le noeud Nc qui est aussi le noeud grand-parent du noeud initial NA. La structure d'un message court de type yin est représentée ci-après dans 10 un mode de réalisation où le nom du message est le contenu du message en code ASCII : Message "yin" => 3 octets, codes ASCII : 'y','i','n' Au niveau MAC, un message de sondage « yin - est adressé au noeud parent du noeud initiateur du message yin. 15 A réception du message yin, le noeud Nc envoie (706) un message de réponse court de type « yang » au noeud NB qui à réception, envoie (708) un message de réponse de type « pong » au noeud NA. La structure du message court de type yang et du message court de type pong est représentée ci-après dans un mode de réalisation où le 20 nom du message est le contenu du message en code ASCII : Message "yang" => 4 octets, codes ASCII: 'y','a','n','g' Message "pong" => 4 octets, codes ASCII: 'p','o','n','g' Au niveau MAC, un message de réponse au sondage « yang » est adressé au noeud parent qui a envoyé le message de sondage « yin », et 25 un message de réponse au sondage « pong « est adressé au noeud enfant qui a envoyé le message de sondage initial « ping ». 15 Pour des raisons de simplification de la description, les messages (yin, yang, pong) sont considérés envoyés et reçus sans défaut de communication, bien que différents scenarios d'échec de communication puissent être envisageables sur ces messages, comme par exemple la 5 perte d'un ou plusieurs messages « yin » ou « yang » ou « pong ». Avantageusement, comme le message « ping » est envoyé par le noeud initial NA à intervalles réguliers, ce dernier va recevoir à un moment donné, une réponse par message de réponse au sondage « pong caractérisant l'état de disponibilité des deux noeuds suivants NB et Nc 10 dans le chemin de routage, et ce en dépit d'un ou plusieurs défauts de communication ayant pu engendrer des pertes de message (c'est-à-dire des transmissions de messages qui ne donnent pas lieu à réception dans le noeud récepteur cible). A réception du message de réponse au sondage « pong », le 15 noeud NA s'engage dans la transmission (710) d'un premier fragment de données à destination du noeud suivant NB. Dans l'exemple de la figure 7, la transmission d'un fragment de données est subdivisée en l'envoi successivement de trois paquets illustrés par le regroupement des trois flèches en traits pointillés. Dans une réalisation pour réseau mesh 20 acoustique où un noeud est constitué d'un modem et de son contrôleur, à chaque transmission d'un paquet du contrôleur de modem acoustique vers son modem acoustique, le modem peut répondre par un signal «OK » indiquant que le paquet a bien été mis en file d'attente et qu'il va être envoyé sur le canal acoustique. 25 Le procédé général de transmission peut comporter un mécanisme de retransmission sélective. Si au bout d'un délai arbitraire, le noeud récepteur n'a pas reçu la totalité des paquets attendus, il envoie vers le noeud émetteur une demande de réémission des paquets manquants. Ce mécanisme suppose des structures des entêtes de paquets qui 16 renseignent le récepteur sur l'index du paquet reçu dans le fragment ainsi que sur l'index du fragment dont ce paquet est issu. Dans d'autres modes de réalisation, le fragment de données est envoyé en un seul paquet de données. Le procédé général de 5 transmission peut comporter un mécanisme de retransmission de l'ensemble du fragment. Si au bout d'un délai donné l'émetteur n'a pas reçu un signal venant du récepteur le notifiant de la bonne réception (message de type « natif »), il retransmet l'intégralité du fragment, c'est-à-dire tous les paquets le composant dans l'hypothèse où le fragment est 10 divisé en un ensemble de paquets. Une fois le fragment de données reçu par le noeud suivant NB, le procédé général de transmission peut effectuer une vérification de l'intégrité du fragment reçu. Cette vérification suppose l'existence d'un champ de contrôle inclus dans la trame du fragment reçu. Ce champ de 15 contrôle peut être calculé par un algorithme de hash, par exemple de type « MD5 » portant sur les données contenues dans le fragment. De manière bien connue, le récepteur effectue de nouveau le calcul de ce hash et si le résultat correspond avec le hash reçu, le fragment reçu peut être déclaré intègre. 20 Revenant à la figure 7, si et quand le noeud suivant NB a établi l'intégrité du fragment reçu, ce dernier notifie (712) au noeud émetteur NA la bonne réception dudit fragment. Pour cela il envoie vers le noeud émetteur NA des messages de type « notif » à intervalles réguliers, jusqu'à recevoir (714) du noeud NA en retour un message de type 25 « noted » l'informant qu'il a bien été notifié. La figure 7 illustre aussi la notion d'état associé à chaque noeud. Au départ, le noeud initial NA qui dispose d'un fragment de données à transmettre se trouve dans un état de (pinging) dans lequel il envoie (702) des signaux de sondage courts « ping » au noeud suivant NB jusqu'à 17 recevoir (708) de ce dernier le signal de réponse au sondage « pong ». Une fois le message « pong » reçu, le noeud NA passe dans un état de transmission (Tx) où il peut transmettre le fragment vers le noeud NB. Il demeure dans cet état jusqu'à recevoir du noeud NB le message de 5 notification. A réception de ce message (Notif.) le noeud NA entre dans l'état (Idle) en attendant la réception d'un nouveau fragment. Dans le même temps où le noeud NA émetteur passe à l'état (pinging) puis (Tx) puis (Idle), le noeud NB joue le rôle de récepteur et de notificateur, et passe successivement dans les états (Ide), (Rx) et (Notif.). 10 Plus précisément, le noeud NB passe de l'état (Idie) à l'état (Rx) à réception (706) du message de réponse au sondage « yang » issu du noeud Nc. Puis, lorsqu'il a reçu (710) la totalité du fragment et vérifié son intégrité, il passe à l'état (Notif.). Enfin lorsqu'il reçoit (714) du noeud NA le message « noted », il passe dans l'état « pinging » car il vient de recevoir 15 (710) un fragment qu'il doit à son tour transmettre au noeud suivant Nc. Il est à noter que le noeud NB se retrouve alors dans l'état où se trouvait le noeud NA au début de la séquence. Le noeud NB s'engage alors dans la transmission du fragment vers le noeud Nc en suivant une même séquence que celle suivie par le noeud NA précédemment avec un 20 sondage en deux bonds (716, 718, 720, 722), l'envoi du fragment (724) et la notification (726, 728). Le noeud NB passe par les états successifs de (Pinging), puis (TX), puis (Idle). Le noeud Nc joue le rôle de récepteur et suit une séquence identique à celle suivie précédemment par le noeud NB quand il est récepteur du noeud NA, en passant par les états successifs de 25 (Rx), puis (Notif.), puis (Pinging). En complément, les différents états dans lesquels un noeud peut se trouver sont aussi illustrés sur la machine d'état de la figure 8. Dans un mode de réalisation pour un réseau mesh de modem acoustiques, trois machines d'état différentes peuvent être 18 implémentées : une pour contrôler le modem embarqué dans le véhicule autonome sous-marin, une pour contrôler chaque modem du réseau mesh et une pour contrôler le modem associé à la passerelle. La figure 8 illustre une représentation simplifiée d'une machine d'état (800) pour un 5 modem du réseau mesh. La gestion du réveil d'un modem n'est pas illustrée, et le premier état (802) d'un modem est représenté par son « éveil » (ou « waking up en anglais). En effet, un modem étant alimenté par batterie, il convient de limiter sa consommation autant que possible pour maximiser la durée de 10 vie de la batterie avant recharge. Pour cela les modems ont la capacité de « s'endormir » et de se réveiller sur réception de signaux acoustiques. Une fois endormi, le modem consomme peu sur la batterie. Quand un modem est dans l'état d'éveil, le contrôleur de modem s'assure de la fonctionnalité du modem en vérifiant sa réponse à des commandes 15 simples. Cet état est introduit du fait de l'asynchronisme entre le contrôleur de modem et le modem associé. Il est possible qu'au réveil le contrôleur de modem devienne fonctionnel avant le modem, il convient donc que le contrôleur « patiente » en interrogeant le modem acoustique, jusqu'à ce que celui-ci fournisse une réponse caractéristique de son état 20 éveillé et opérationnel. Le contrôleur passe alors dans un état « Prêt » (814) (ou « Ready » en anglais) où il est prêt. Si le contrôleur mesh passe à l'état « Ready » c'est qu'il a été réveillé. Il peut avoir été réveillé pour différentes raisons. L'une de ces raisons peut être qu'il doit contribuer à la dissémination d'une notification dans le réseau mesh, laquelle notification 25 pourra être récupérée par le véhicule autonome sous-marin (AUV) lorsqu'il s'attachera (en termes de communication) à un noeud du réseau mesh. Si le noeud a été réveillé pour participer à la transmission d'un rapport de l'AUV vers la passerelle, il entre dans un état dit « waking_up » où la première chose à faire pour transmettre un rapport de I'AUV à la 30 passerelle consiste à « réveiller » tous les modems qui sont sur le chemin 19 de l'AUV vers la passerelle. Une fois tous réveillés, ces modems sont sensés garder l'état éveillé jusqu'à ce qu'ils aient traités tous les fragments allant du premier fragment reçu jusqu'au dernier fragment du rapport (ou bien jusqu'à ce qu'un délai d'expiration soit atteint). Ils 5 peuvent ensuite s'endormir à nouveau. Une fois que l'AUV s'est attaché à un noeud du réseau mesh dans le but de transmettre un rapport, il demande au noeud sélectionné de réveiller son parent, lequel va réveiller son parent à son tour, etc, jusqu'à atteindre le noeud passerelle. Si un noeud est réveillé pour transmettre un rapport vers la 10 passerelle, le premier état dans lequel il rentre est un état dans lequel il s'efforce de réveiller son noeud parent. Il s'agit de l'état d'éveil (802). Dans cet état, il envoie un message acoustique dénommé « wakeup » en broadcast jusqu'à recevoir de son parent une confirmation d'éveil concrétisée par un message dit « isup ». Une fois le message « isup 15 reçu du parent, le contrôleur de modem entre dans un état d'attente « idle » (804). Il est à noter que des collisions ne sont pas exclues entre les messages « wakeup » et les messages « isup ». Pour éviter que des situations de collisions systématiques perdurent, les messages 20 « wakeup » ne sont pas émis à intervalles réguliers. Par exemple la période entre deux messages « wakeup » peut être de 2 ou 3 secondes, le choix étant alors fait sur un critère purement aléatoire. Une fois l'état « idle » atteint, un noeud mesh est disponible pour relayer des fragments vers le noeud parent. Les noeuds mesh suivent 25 nécessairement la séquence d'états suivante: Etat hile (804) => Etat Rx (806) => Etat Notif. (808) => Etat Ping. (810) => Etat Tx (812) => Etat kilo (804) Ainsi, un noeud mesh attend un prochain fragment en état « Ide » (804), puis le reçoit en état « Rx » (806), puis notifie la bonne réception au 20 noeud enfant qui lui a transmis ce fragment en état « Notif.» (808), puis entre dans l'état « Ping. » (810) pour un sondage à deux bonds où il s'assure de l'état de disponibilité de son parent et de son grand-parent, puis entre dans l'état de transmission ou de retransmission c REVENDICATIONS1. Un procédé mis en oeuvre par ordinateur pour transmettre dans un réseau sans fil, des blocs de données constitués de plusieurs fragments de données, le réseau comprenant une pluralité de noeuds définissant entre des triades de noeuds des relations enfant/parent/grand-parent, le procédé comprenant au moins les étapes suivantes opérées entre un noeud enfant, un noeud parent et un noeud grand-parent : envoyer depuis un noeud enfant un message de sondage enfant/parent, dit message « ping », vers un noeud parent; envoyer depuis le noeud parent ayant reçu le message « ping », un message de sondage parent/grand-parent, dit message « yin », vers un noeud grand-parent; envoyer depuis ledit noeud grand-parent ayant reçu le message « yin », un message de réponse au sondage parent/grand-parent, dit message « yang », vers ledit noeud parent ; envoyer dudit noeud parent ayant reçu le message « yang », un message de réponse au sondage enfant/parent, dit message « pong », vers ledit noeud enfant ; et - transmettre un fragment de données du noeud enfant audit noeud parent. 2. Le procédé selon la revendication 1 dans lequel les étapes sont répétées pour plusieurs triades de noeuds enfant/parent/grand-parent, sur un chemin de routage depuis un noeud source émetteur de données jusqu'à un noeud destinataire des données. 22 3. Le procédé selon la revendication 1 ou 2 dans lequel l'étape d'envoyer un message c 4. Le procédé selon l'une quelconque des revendications 1 à 3 dans 5 lequel l'étape d'envoyer un message « yang » est opérée si le noeud grand-parent est disponible. 5. Le procédé selon l'une quelconque des revendications 1 à 4 dans lequel les triades de noeuds enfant/parent/grand-parent sont 10 prédéfinies. 6. Le procédé selon l'une quelconque des revendications 1 à 5 dans lequel l'étape de transmission des données consiste à transmettre successivement des paquets de données. 15 7. Le procédé selon l'une quelconque des revendications 1 à 6 comprenant de plus une étape de vérification de l'intégrité des données reçues. 20 8. Le procédé selon l'une quelconque des revendications 1 à 7 dans lequel les messages de sondage « oing », « yin » et les messages de réponse au sondage « yang », « pong », sont des messages courts codés en ASCII. 25 9. Un dispositif pour transmettre dans un réseau sans fil des blocs de données constitués de plusieurs fragments de données, le dispositif comprenant des moyens pour mettre en oeuvre les étapes du procédé selon l'une quelconque des revendications 1 à 8. 10. Le dispositif selon la revendication 9 dans lequel le réseau sans fil est un réseau maillé. 23 11. Le dispositif selon la revendication 10 dans lequel le réseau maillé est un réseau maillé comprenant une pluralité de modems acoustiques dont un modem est un noeud source correspondant à un véhicule sous-marin autonome et un modem est un noeud passerelle vers un 5 navire, le dispositif permettant la transmission de données relatives à des rapports de mesure, depuis le véhicule sous-marin autonome vers le navire. 12. Le dispositif selon la revendication 11 dans lequel chaque modem est 10 couplé respectivement à un contrôleur de modem, notamment par une liaison série RS232. 13. Le dispositif selon l'une quelconque des revendications 9 à 12 dans lequel les moyens pour opérer les étapes du procédé selon l'une 15 quelconque des revendications 1 à 8 sont une machine d'état. 14. Un produit programme d'ordinateur, ledit programme d'ordinateur comprenant des instructions de code non transitoire permettant d'effectuer les étapes du procédé selon l'une quelconque des 20 revendications 1 à 8, lorsque ledit programme est exécuté sur un ordinateur.