RFID (Radio Frequency IDentification)

Algorithmes déterministes

Préliminaires

La première phase dans le déroulement de l'exemple d'algorithme déterministe que je vais présenter consiste à détecter si des transpondeurs sont présents dans le champ magnétique de la station de base. Pour cela, le lecteur constitue une requête générale d'1octet qui permettra aux transpondeurs aptes à répondre de le faire. La requête est propagée dans le champ et tous les transpondeurs pouvant l'interpréter constituent une réponse adéquate. Cette réponse est un acquittement générique de 2octets qui a le même format quel que soit le transpondeur. Chaque transpondeur identifié renvoie donc cet acquittement, signifiant ainsi sa présence.

NB : les acquittements étant tous identiques, la superposition des réponses ne pose aucun soucis. Le but de cette manoeuvre pour la station de base est simplement d'identifier qu'au moins un tag est présent dans son champ.


La station de base ayant détecté des transpondeurs, elle constitue alors une "trame de commande anticollision", dont le format est le suivant :


Le premier octet de cette trame (premier 8bits) est l'octet de sélection SEL. Il représente la commande de sélection pour interroger les UID de chaque transpondeur. L'octet SEL est composé de la manière suivante :

Le CLn signifie "Niveau de Cascade de rang n". Le Cascade Level est utile pour spécifier la taille des UID des transpondeurs. En effet, il existe des UID de tailles différentes :

Les 2ème et 3ème bits de poids faible (b2 et b3) permettent de spécifier le Cascade Level correspondant au format des UID. Cette valeur est modifiée durant l'algorithme. Le bit de poids le plus faible (b1), quant à lui, spécifie le mode d'anticollision utilisé : si la valeur est '0', la gestion anticollision est orientée octet par octet, si la valeur est '1', la gestion anticollision est orientée bit par bit. Le plus généralement, la gestion anticollision est orientée bit par bit.



Le second octet, NVB (Number of Valid Bits), correspond au nombre de bits valides. Il définit combien d'octets sont utiles dans la transmission et combien de bits de l'UID des transpondeurs doivent être considérés comme valides et pris en compte pour la suite de l'algorithme. L'octet NVB est composé de la façon suivante :

Les quatre bits de poids fort (b5 à b8) consituent le "bytecount", c'est-à-dire le nombre d'octets transmis par la station de base. Le bytecount est au moins égal à 2 : octet SEL + octet NVB au minimum. Il varie ensuite en fonction du nombre d'octets de données qui complètent la trame.
Les quatres bits de poids faible (b1 à b4) représentent le "bitcount", c'est-à-dire le nombre de bits de données additionnels.
Nous nous intéresserons surtout au bytecount.


Enfin, la trame peut être complétée avec 40 octets de données. Cela sera utile durant la procédure de l'algorithme que nous allons détailler.



Procédure de l'algorithme

La station de base a initialement assigné le CLn à la commande de sélection SEL. Puis, elle a transmis la première trame, constituée uniquement des octets SEL et NVB, afin d'identifier tous les transpondeurs par leurs UID. Les transpondeurs répondent donc à la trame en fournissant leurs UID respectifs. A ce niveau de l'algorithme, s'il y a des réponses simultanées et synchrones des transpondeurs, on est capable d'utiliser la correction bit à bit du code Manchester, mentionnée précédemment, pour résoudre les collisions bit à bit simples.

Voici un exemple simple de message reçu suite aux réponses de la part des transpondeurs :

Dans le message reçu, nous constatons qu'une première collision a eu lieu au niveau du 5ème bit. Nous allons donc commencer par traiter cette collision. Seuls les 4 premiers bits sont valides. Pour résoudre le problème, nous choisissons indépendamment de compléter ces 4 bits valides par un '0' ou par un '1'. En vérité, il est nécessaire d'étudier les deux cas pour poursuivre l'algorithme.

Considérons, dans un premier temps, que nous complétons les bits valides par un '0'. Nous obtenons alors la suite de bits valides : 00010. Le nombre de bits valides est donc placés à 5 dans la commande NVB. La station de base constitue alors une nouvelle trame composée de l'octet SEL et du nouvel octet NVB, puis elle complète cette trame en fournissant en données la suite des 5 bits valides.
Seuls les transpondeurs dont les UID commencent par la suite de bits valides, ici 00010, sont alors invités à re-communiquer leurs UID personnels. La collision au 5ème bit a donc été éliminée. Si une autre collision survient plus loin dans le message, alors la même méthode est appliquée, jusqu'à ce que chaque UID complet soit déterminé.

Nous avions, au préalable, choisi délibérément de compléter les bits valides avec un '0'. Nous effectuons donc, maintenant, la même opération en complétant la suite de bits valides avec un '1'. La suite de bits valides est alors : 00011. Puis chacune des étapes énoncées précédemment est accomplie.

Comme vous l'aurez compris, nous balayons donc, de proche en proche, toutes les solutions possibles d'UID, en éliminant une à une les collisions générées par la superposition des messages des transpondeurs. De cette manière, les UID de tous les transpondeurs sont déterminés comme par un parcours d'arbre :

Une fois que chaque transpondeur a été identifié par son UID unique, la station de base est en mesure de communiquer avec ce tag en utilisant son identifiant unique. De cette manière, les problèmes de collisions sont annihiliés.


Intérêts

Les algorithmes déterministes sont efficaces car :