Étiquettes communicantes

Le code-barres, ancêtre de l’étiquette RFID

Chaque semaine, des milliards de codes-barres sont imprimés pour marquer des objets et permettent ainsi une saisie automatique des données numériques. Le code-barres, tout comme la carte à puce, sont des trentenaires bien portants : c’est en juin 1974, dans l’Ohio, que le premier article fut « scanné ». Pour la petite histoire, il s’agissait d’un paquet de chewing-gum. En Angleterre, ce fut une boîte de thé et en France, un paquet de galettes de Fouesnant… Développé par IBM en 1973 à la demande d’un consortium formé par les supermarchés américains, le code-barres a été mis dans le domaine public afin de lui donner un coût quasi-nul et de favoriser ainsi son utilisation. Trente-quatre ans plus tard, son utilisation est quasi-généralisée et notons que la grande distribution ne représente que 50 % de son utilisation. Des technologies se développent aujourd’hui non seulement pour pouvoir identifier les objets — c’est déjà le cas avec les codes-barres —, mais surtout pour stocker des données, une nouvelle possibilité offerte par les étiquettes électroniques RFID (en anglais RFID tags). Ces étiquettes embarquent non seulement plus de mémoire qu’un simple code-barres mais en plus, elles ne sont pas figées durant la vie de l’objet, ce qui permet des applications telles que la traçabilité par exemple.

L’étiquette intelligente

En quoi les étiquettes électroniques diffèrent-elles des codes-barres ? Elles vont encore plus loin, elles rendent les objets communicants ! Leur principale fonction est cachée dans l’acronyme « RFID » pour Radio Frequency Identification : elles permettent d’identifier les produits et les objets sur lesquels elles sont placées en utilisant les ondes radio pour transmettre l’information. L’étiquette RFID, contrairement à son ancêtre le code-barres, ne nécessite ni une vue directe de l’étiquette, ni une manipulation de l’objet pour effectuer une lecture. Pour que celle-ci soit possible, il suffit que l’étiquette soit présente dans le champ électromagnétique du lecteur. Les lecteurs, ce sont par exemple ces portiques que l’on trouve à la sortie des grands magasins et qui ont la fâcheuse habitude de « bipper » lorsque l’on oublie de payer un produit « taggué », mais aussi des lecteurs intégrés aux rayonnages pour faciliter l’inventaire et la gestion des stocks. La lecture des informations est ainsi rendue possible, certes, mais elle n’est pas garantie si plusieurs étiquettes sont présentes, car il existe un risque de collision qui rendrait les informations incompréhensibles.

Un chef d’orchestre : le lecteur

Les étiquettes dites intelligentes sont en effet des composants informatiques très rudimentaires, avec une mémoire, une antenne, mais pas d’alimentation en énergie, et avec un mode de communication bien particulier. Tout d’abord, les étiquettes ne sont activées que lorsqu’elles sont dans le champ électromagnétique du lecteur et elles ne peuvent pas s’entendre les unes les autres. Cette spécificité rend impossibles les techniques utilisées dans les couches MAC (Media Access Control) classiques— des couches de gestion d’accès à un canal radio —, comme l’écoute de la porteuse qui consiste à écouter si le canal est libre. Par contre, le lecteur peut être entendu par toutes les étiquettes, même si elles sont en train d’émettre. Ceci place d’emblée le lecteur comme le chef d’orchestre des communications afin d’éviter les collisions et donc les pertes d’informations.

Étiquettes électroniques RFID.
© INRIA / Photo C. Lebedinsky.

Les premières tentatives de solution pour éviter les collisions ont pourtant ignoré cette possibilité et ont exploité les attentes aléatoires d’une façon similaire au protocole ALOHA. Ainsi, avant d’émettre, une étiquette attend une durée aléatoire. Malheureusement, ce type de protocoles est réputé – à raison – pour gaspiller la bande passante (environ 33 % seulement de la bande passante est occupée utilement). De plus, l’attente aléatoire doit être correctement paramétrée pour que l’algorithme fonctionne efficacement. Une attente trop courte amène trop de collisions tandis qu’une attente trop longue allonge le temps d’identification. Toutefois, ces petits inconvénients représentent bien peu de choses par rapport aux bénéfices apportés par ces algorithmes. Grâce à eux, on ne perd que très peu de tags et leur lecture a été accélérée : on peut maintenant lire jusqu’à 240 tags par seconde.

Parcours d’arborescence

D’autres propositions, basées sur le parcours d’arborescence, ont mis à profit le rôle de chef d’orchestre. Le principe n’est pas réellement nouveau puisqu’il était mis en œuvre par l’armée américaine lors de la seconde guerre mondiale afin de détecter certaines maladies : pour savoir qui est porteur, on teste un mélange constitué des échantillons sanguins de tous les soldats. Si le test est positif, on sépare les soldats en deux groupes et on réitère l’opération jusqu’à isoler les soldats porteurs.

Nul besoin de test sanguin pour nos étiquettes. On teste simplement s’il y a une collision ou une identification. À chaque collision, on utilise les bits constituant les identifiants pour séparer les « soldats-étiquettes ». Ainsi, la première requête du lecteur est « y a-t-il une étiquette présente ? » S’il y a une identification, le processus est terminé. S’il y a une collision, le lecteur demande « y a-t-il une étiquette dont l’identifiant commence par 0 ? » et mémorise (par exemple, dans une pile) qu’il doit interroger les étiquettes dont l’identifiant commence par 1. S’il y a à nouveau une collision, le lecteur passe aux étiquettes commençant par 00 et mémorise qu’il faudra consulter les identifiants 01. Le processus est répété jusqu’à ce que toutes les étiquettes soient identifiées.

Effet lointain-proche

Le parcours d’arborescence peut être assez séduisant, car il est déterministe et la durée moyenne d’identification est linéaire en fonction du nombre d’étiquettes présentes. Néanmoins, il requiert que deux étiquettes n’aient pas un même identifiant. De plus, le canal de communication souffre de « l’effet lointain-proche » qui fait que l’émission d’une étiquette éloignée du lecteur est totalement masquée par l’émission d’une étiquette proche. Mieux, l’étiquette proche sera reçue sans collision et l’étiquette lointaine sera perdue si le processus de parcours de l’arbre n’est pas réitéré. En tout état de cause, l’étiquette lointaine devra attendre un nouveau parcours de l’arbre pour être prise en compte, ce qui lui laisse plus d’opportunité de sortir du champ du lecteur sans être recensée.

Autre conséquence de cet effet lointain-proche (également connu sous le nom d’éblouissement), les acquittements d’identification doivent clairement désigner l’étiquette identifiée, car dans le cas mentionné ci-dessus, un simple « OK » validerait les deux étiquettes simultanément, ce qui signifierait la perte de l’étiquette la plus éloignée. Une première solution est de donner l’identifiant de l’étiquette entendue. On dit alors « OK étiquette numéro 010…11 » et comme on fonctionne sous l’hypothèse d’unicité de l’identifiant, tout fonctionne correctement. Sauf que le canal dans le sens du lecteur vers l’étiquette est plutôt lent – jusqu’à quatre fois plus lent que dans le sens inverse – et qu’il doit être utilisé avec précaution pour respecter les limitations de rayonnement électromagnétique. Une autre solution est d’utiliser le taux d’excitation de l’étiquette, qui est fonction de la distance et de l’orientation de l’étiquette. On définit plusieurs niveaux d’excitation de manière à être sûr que si deux étiquettes ont le même niveau d’excitation, elles ne peuvent être affectées par l’effet d’éblouissement. Ce niveau est transmis simultanément avec les identifiants. Il suffit alors au lecteur de donner le niveau d’excitation de l’étiquette reçue correctement pour éviter de valider à tort les étiquettes lointaines.

Rondes adaptatives

S’affranchissant de la contrainte de l’identifiant unique, les protocoles par rondes adaptatives ont, eux aussi, un temps d’identification linéaire par rapport au nombre d’étiquettes. Dans ces protocoles, le lecteur annonce une ronde subdivisée en un certain nombre de slots. Chaque étiquette non identifiée choisit aléatoirement un des slots pour émettre. Si le nombre de slots est trop court, on obtient de nombreuses collisions et si, au contraire, la taille de la ronde est trop grande, on observe beaucoup de slots vides. Le but du lecteur est de choisir la bonne longueur de ronde. Le problème est alors qu’il faut connaître le nombre d’étiquettes encore actives. Un exercice de probabilités élémentaires montre qu’en moyenne le nombre d’étiquettes identifiées, le nombre de slots vides et la taille de la ronde sont liés par une équation très simple permettant d’estimer le nombre d’étiquettes – sauf lorsqu’il n’y a que des collisions car dans ce cas, on ne peut que constater qu’il faut voir plus grand.

Au-delà de l’anti-collision

Nous avons présenté ici les rudiments de l’anti-collision pour étiquettes électroniques. Les deux protocoles expliqués — parcours d’arborescence et rondes adaptatives — sont effectivement mis en œuvre dans les étiquettes actuelles. L’un des grands intérêts de la seconde solution est qu’il n’est absolument pas nécessaire de donner son identifiant pour transmettre une information. Ceci est une réponse triviale à la problématique du « respect de la vie privée » souvent soulevée par cette technologie. En effet, si une étiquette portée par une personne transmet son identifiant, qui est unique, à chaque fois qu’elle traverse le champ d’un lecteur, il y a un suivi implicite de la personne. Or, les protocoles d’anti-collision par parcours d’arborescence rendent obligatoire l’envoi de cet identifiant… ce qui rend difficile de construire au-dessus une application respectant la vie privée. Ceci ne constitue qu’une réponse partielle aux questions éthiques soulevées par cette technologie, mais montre bien que la technologie elle-même peut être porteuse de solutions.