RFID (Radio Frequency IDentification)
Algorithmes probabilistes
Préliminaires
Il existe de nombreux algorithmes probabilistes. Je présenterai ici la méthode que j'ai également présentée dans le
cadre de ma présentation orale. Il s'agit de la méthode temporelle que j'ai mentionnée dans l'introduction à la gestion
de collisions, appelée "méthode des time slots" ou "méthode des créneaux de temps".
Cette méthode consiste à partager le temps périodiquement. La période choisie doit définir des slots (créneaux temporels)
pendant lesquels la station de base pourra dialoguer avec les transpondeurs. Chaque transpondeur se voit donc attribuer
un canal temporel spécifique durant lequel il sera autorisé à communiquer avec la station de base.
Voici une représentation du partage temporel de la méthode des time slots :
Procédure de l'algorithme
La première étape consiste, pour la station de base, à définir et annoncer la "hashValue" à tous les transpondeurs. La hashValue
est la valeur qui correspond au nombre de créneaux de temps alloués pour le dialogue.
Chaque transpondeur est alors invité à choisir arbitrairement un slot pendant lequel il pourra dialoguer avec le lecteur. Le
transpondeur peut soit déterminer une valeur aléatoire dans l'intervalle [1; hashValue] pour choisir un créneau, soit déterminer
son créneau en effectuant un calcul à l'aide de la hashValue et son UID (ou une partie de UID). Cette dernière méthode peut
garantir un meilleur résultat du fait de l'unicité de l'UID. Lorsque chaque transpondeur a déterminé son time slot, il y transmet
sa réponse à la station de base.
Pour chaque time slot alloué, deux cas de figure sont envisageables pour la station de base :
- Si le message reçu est bien interprété, alors il n'y a pas eu de collision. Cela signifie qu'un seul transpondeur a désigné ce créneau de temps. Dans ce cas, le lecteur fournit une commande de "Quit" au transpondeur pour lui indiquer que ce créneau lui est désormais dédié et que leurs échanges s'effectueront dans ce time slot périodique.
- Si le message reçu est incohérent, alors une collision est survenue. Cela signifie qu'au moins deux transpondeurs ont choisi ce créneau de temps. La station de base relance alors la procédure initiale pour les transpondeurs partageant le même créneau de temps.
Approche problématique
Que se passe-t-il s'il y a plus de transpondeurs que de créneaux de temps alloués par la station de base ? Comme vous pouvez vous
en douter, cette situation est assez problématique. Si trop peu de créneaux sont définis, alors certains time slots provoqueront constamment
des collisions. A l'inverse, nous pouvons imaginer que si trop de créneaux sont alloués, alors un gain de temps plus ou moins important sera
perdu, puisqu'il existera des slots durant lesquels aucune communication ne sera échangée.
C'est en cela que ce type d'algorithme est probabiliste. La station de base doit estimer le nombre de transpondeurs susceptibles d'être présents
dans le champ magnétique et cela est problématique. En fait, la valeur de la hashValue doit, ici, dépendre du type d'application de la RFID.
De nombreuses simulations ont été effectuées et démontrent que la solution optimale consiste à cibler le double du nombre de transpondeurs
espérés.
Intérêts
Les algorithmes probabilistes sont efficaces car :
- Des communications individuelles sont établies avec chaque transpondeur,
- Le nombre d'échanges est minimalisé, par conséquent les perturbations radioéclectriques sont réduites,
- Les risques de collision sont éliminés.