LoCostix

November 5th, 2012  |  Published in Research

Low Cost Smart-Labels for Logistic Processes in Retail

Sponsor: Bundesministerium für Bildung und Forschung (BMBF)

Projektdauer: 01.04.2006 bis 30.09.2008 (30 Monate)

Ziel des Projektes

Das Ziel des Projektes besteht darin das Inventurproblem im Einzelhandel zu lösen. Dazu sollen billige RFID-Tags mit gedruckten Antennen an jedem einzelnen Produkt angebracht werden. Durch Optimierungen der Kommunikationsprotokolle und mobile Lesegeräte soll dabei der gesamte Warenbestand überwacht werden können ohne zu jeder Zeit alle Tags auslesen zu können.

Aufgaben des TecO

Im Nachfolgenden werden die Probleme der Kommunikation mit passiven RFID-Transpondern im EPC Gen 2 Standard erläutert und Möglichkeiten zur Lösung aufgeführt. Hierbei liegt der Focus der Problembetrachtung auf dem Inventory-Problem, das die zentralen Aspekte der Forschung und der Analysen liefert.

Zum einen werden die Limitierungen des Standard EPC Gen 2 Protokolls dargestellt und dann im Detail Möglichkeiten zur Lösung der Probleme vorgeschlagen. Hierbei liegt der Focus auf dem entwickelten „GossipReading“ [Patent 2008].

Die im „GossipReading“ verwendeten Verbesserungen gliedern sich in drei Hauptaspekte:

  1. Optimierung des Kanal-Vielfachzugriffes: Hier wird das in dem EPC Gen 2 Protokoll verwendete Slotted-Aloha und dem damit verbundenen Packet-Acknowledge in der Reaktionsgeschwindigkeit bei Schätzungen verbessert.
  2. Analyse neuartiger Ansätze der Datenfusion: Verschiedene Systeme der RFID-Technologie und der Backend-Systeme besitzen individuelle Sichtweisen auf die Realität. Es wird nun versucht diese verschiedenen Sichtweisen miteinander zu kombinieren, um ein Maximum an Information für jedes beteiligte System herauszuholen.
  3. Analyse der Protokolllösungen: Die zuvor genannten Verbesserungen der Kommunikation und Datenfusion wird analysiert und mit realen Messdaten verglichen.

Ein weiterer Bestandteil dieses Dokumentes ist die Simulierbarkeit des Inventory-Scenarios. In wie weit ist die Simulation möglich, was ist der Fehler gegenüber der Realität und wie können die reellen Messungen analysiert werden, um eine Simulation zu ermöglichen.

Hierbei wurden zwei Ansätze analysiert. Eine Methode beschäftigt sich mit der Simulierbarkeit durch ein statistisches Modell. Die andere Methode ist die Strahlverfolgung (Raytracing), die häufig eine Anwendung in der statischen Umgebungsanalyse und Computergraphik findet.

Problemspezifizierung

Eine Verwendung von EPC Gen 2 für Pulk-Lesungen im Retail-Scenario bringt viele Probleme hervor, insbesondere mit dicht gepackten Umgebungen mit mehreren hundert RFID-Tanspondern. Diese mit RFID-Transpondern dicht gepackten Umgebungen sind jedoch im Inventory-Scenario fast ausschließlich anzutreffen.

Ein großes Problem hierbei ist das im EPC Gen 2 Standard verwendete Slotted-Aloha Kanalvielfachzugriffsverfahren. In diesem wird ein Zeitrahmen der Länge T=n*t in n gleichlange Zeitschlitze der Länge t aufgeteilt. Die Tags in Reichweite antworten nun auf die Anfrage des Lesegerätes innerhalb eines Zeitschlitzes. Welcher Zeitschlitz gewählt wird, wird vom Transponder zufällig bestimmt. Durch dieses Verfahren kann jedoch nicht garantiert werden, dass nicht zwei oder mehr Transponder den gleichen Zeitschlitz wählen und somit eine Datenkollision hervorrufen. Die Daten einer solchen Kollision sind für den Empfänger, das Lesegerät, verloren. Das Slotted-Aloha Kanalzugriffsprotokoll ist in Abbildung 1 illustriert.

Abbildung 1: Slotted-Aloha

Um nun die Anzahl der erfolgreich gesendeten Datenpakete der Transponder zu erhöhen, werden sukzessive Zeitrahmen zur Datenübertragung angestoßen. Für jeden neuen Zeitrahmen entscheidet jeder Transponder neu, in welchem Zeitschlitz er Daten senden will. Somit erhöht sich pro Zeitrahmen die Wahrscheinlichkeit, dass alle Tansponder ihre Daten erfolgreich senden konnten. Wie in Abbildung 2 illustriert, steigt somit die Wahrscheinlichkeit, dass alle Transponder erfolgreich übertragen konnten, zuerst langsam und dann schnell an. Gegen Ende ist nur noch ein geringer Anstieg der Wahrscheinlichkeit zu beobachten, was mit Sättigungsphase bezeichnet wurde.

Abbildung 2: Wahrscheinlichkeit für das Lesen aller Tags in Reichweite pro Zeitrahmen

Weitere Probleme bei der Kommunikation zwischen Lesegerät und Transponder sind physikalischer Natur. Eine kurze Liste soll exemplarisch einige der Probleme auflisten:

Abschattung
Steht ein Produkt vor einem anderen, was in Regalen des Einzelhandels zu erwarten ist, so wird durch das vordere Produkt die Energie die durch die Leseantenne gespeist wird teilweise abgeblockt. Es kann somit vorkommen, dass der Transponder am hinteren Produkt nicht genügend Energie bekommt um den Microchip zu versorgen. Mit mehreren Produkten in einer Reihe oder übereinander verschärft sich die Situation natürlich. Auch können sich die Transponder gegenseitig die Energie stehlen.
Reflektion
Sind die Regale in denen die Produkte zum Verkauf ausgestellt sind aus Metall gefertigt, so haben diese Regale Einfluss auf die Wellenausbreitung ausgehend von der Leseantenne. Reflektionen der Wellen können zu anderen Wegen führen, worüber die Transponder erreicht werden, als angenommen. Dies macht die Modellierung des Szenarios nahezu unmöglich.
Interferenz
Meist aufgrund von Reflektionen werden Interferenzen der Wellen hervorgerufenen. Diese bewirken eine unvorhersehbare Ausbreitung der Wellenenergie. Gewisse Bereiche können durch Interferenzen unerreichbar sein.

Zu den größten Problemen und stärksten Limitierung der Einsetzbarkeit von EPC Gen 2 zählt die Wechselwirkung der Wellen des verwendeten Frequenzbereiches mit auf Wasser basierenden Flüssigkeiten. Im Frequenzbereich von 865–869 MHz absorbiert Wasser den größten Teil der Wellenenergie. Für den Einzelhandel bedeutet dies, dass ein Großteil der Produktpalette so gut wie nicht durch RFID-Transponder identifizierbar ist. Die Situation verschärft sich noch, wenn die auf Wasser basierende Flüssigkeit in einem mit Metall versiegelten Tetra-Pack untergebracht ist. Diese Transponder an solchen Produkte sind wenn überhaupt nur wenige Zentimeter lesbar. Auch ist ein Transponder der durch ein solches anderes Produkt abgeschattet wird nicht zu lesen.

Es wurde nun versucht durch Anpassungen des Leseprotokolls, durch geschickte Applikationen und Modellierungen mit diesen Problemen umzugehen und eine verbesserte Performanz innerhalb des Inventory-Problems zu erreichen. Hierbei wurden, wie in folgenden Kapiteln beschrieben wird, vielversprechende Ansätze gefunden, jedoch auch Grenzen der Verbesserungen erkannt.

Protokolldesign

Optimierung des Kanal-Vielfachzugriff

Wie in der Problemspezifizierung beschrieben, muss bei EPC Gen 2 Transpondern um eine gewisse Wahrscheinlichkeit, dass alle Transponder in Reichweite geantwortet haben, zu erreichen eine gewisse Anzahl von Wiederholungen der Lese-Zeitrahmen durchgeführt werden. Es wird durch ein Protokoll die optimale Länge des Zeitrahmens festgestellt, welche von der Anzahl der Transponder in Reichweite abhängig ist. Je mehr Tags in Reichweite, desto länger wird der Zeitrahmen. Sind sehr viele Tags in Reichweite, so muss ein sehr langer Zeitrahmen sehr oft wiederholt werden, damit die gewünschte Lesewahrscheinlichkeit erreicht wird. Dies führt zu einer sehr langen Lesephase, die mitunter einige Minuten dauern kann. Da in dem gewählten Szenario immer sehr viele Transponder in Reichweite sind, wird die Lesezeit nie unter eine gewisse Schranke fallen.

Daraus ergibt sich nun ein Problem für mobile Lesegeräte, bei denen nicht bestimmt werden kann, wie lange sie an einer bestimmten Position zu verharren haben. Dieses Problem verschärft sich noch, wenn die Lesegeräte in einem konstant bewegten Zustand die Lesungen durchführen müssen. Hierbei kann es vorkommen, dass sich die Menge der Tansponder in Reichweite während eines Zeitrahmens ändert. Die Menge der Transponder ändert sich jedoch mit einer sehr großen Wahrscheinlichkeit zwischen den Zeitrahmen.

Zur Lösung der Probleme wurden zwei Ansätze entwickelt, die in Kombination benutzt werden. Zum Einen wurde eine Möglichkeit gefunden, eine gute Schätzung der Anzahl der Tags in Reichweite zu treffen und dies nur mit Ausführung eines Lese-Zeitrahmens. Zum Anderen wurde ein Verfahren entwickelt, das die Information der Position des Lesegerätes nutzt, um die Auswahl der Transponder auf eine Produktgruppe oder bestimmte handhabbare Untermenge zu beschränken.

Funktionsweise des Schätzverfahrens:

  1. Initiiere das Lesen für die Länge genau einen Zeitrahmens.
  2. Erfasse Anzahl von erfolgreichen Datenübertragungen, Anzahl von Kollisionen und Anzahl von leeren Zeitschlitzen für diesen einen Zeitrahmen.
  3. Berechne die Mindestanzahl der Transponder in Reichweite anhand folgender Formel: min. # Transponder = # erfolgreicher Datenübertragungen + 2 * # Kollisionen
  4. Berechne Schätzung > min # Transponder

Um das Schätzverfahren [Vogt 2002] effizient durchzuführen, muss der Zustandsautomat der Transponder-Chips vorzeitig abgebrochen werden. Durch ein Acknowledge System wird normalerweise garantiert, dass der jeweilige Transponder seine Daten absetzen kann. Hierbei sendet der Transponder solange in aufeinanderfolgenden Zeitrahmen bis er eine Bestätigung der erfolgreichen Datenübertragung bekommen hat. Das Schätzverfahren nutzt jedoch die Informationen über die Anzahl von Kollisionen, weshalb eine erfolgreiche Datenübertragung für jeden Transponder gar nicht notwendig ist.

Eine Schätzung der Anzahl der Transponder in Reichweite macht nicht viel Sinn, wenn nicht bekannt ist welche Art von Produkten in der Lesezone vorhanden sind. Wird ohne Auswahl geschätzt, hat die Schätzung ohne Abhängigkeit von der Genauigkeit keine Bedeutung. Unser Ansatz nutzt nun Informationen der Position und Orientierung der Leseantenne um eine einzelne Produktgruppe zu selektieren, bei der vermutet wird, dass sie vollständig in Reichweite liegt. Die Schätzung der Anzahl der Produkte ist nun nur auf die selektierte Produktgruppe beschränkt. Die Selektion der Produktgruppe wird nun je nach Position und Orientierung der Leseantenne solange durchgeführt, bis alle Produktgruppen im Ladengeschäft abgedeckt sind. Somit erhält man über die Zeit akkumuliert eine gute Schätzung des Inventars, wobei die einzelnen Schätzungen gegenüber normalen Lesungen ein Vielfaches an Performanz voraushaben.

Weitere Optimierungen des Kanalzugriffsverfahrens sind theoretisch denkbar und wurden z.T. mit Prototypen [Krohn, u. a. 2005.1][Krohn, u. a. 2005.2] simuliert, wozu jedoch Informationen bzgl. des „Receiving Signal Strength Indicator“ (RSSI) benötigt werden. Diese Informationen sind bei Standart-Lesegeräten nicht zugänglich und konnten auch innerhalb des Projektes nicht eingefordert werden.

Analyse neuartiger Ansätze der Datenfusion

Die verschiedenen Systeme die im Einzelhandel und der Logistik eingesetzt werde, besitzen verschiedene Informationen über die reelle Situation. In einem Ladengeschäft besitzt das Backend-System sehr viele Informationen über den Eingang der Waren, den Status der Bestellungen und des Lagers. Ein RFID-System ist immer informiert welche Produkte gerade verkauft werden und die Lesegeräte an den Regalen haben Informationen über das Inventar in den Regalen.

Ein Ansatz der nun helfen soll die einzelnen Systeme zu optimieren, ist eine intelligente Datenfusion. Hierbei werden die Informationen der jeweiligen anderen Systeme genutzt, um z.B. Selektionsmasken der Lesegeräte zu setzen. Durch intelligentes Selektieren kann die Anzahl der Tags in Reichweite des Lesegerätes signifikant reduziert werden, z.B. wenn nur fehlplatzierte Produkte gefunden werden sollen, können alle typischen ausgeblendet werden. Der Informationsaustausch zwischen Backend-System (ERP) und Mobilen-Lesegeräten ist in Abbildung 3 schematisch dargestellt.

Abbildung 3: Kommunikation von ERP und RFID-Reader im GossipReading

Ein weiterer Vorteil der intelligenten Steuerung der Selektionsmasken durch Backend-Informationen ist die verbesserte Erreichbarkeit der Tags. Es können bestimmte Tags ausgeschaltet werden, die vor blockierten Tags vermutet werden. Somit absorbiert der blockierende Tag nicht mehr die Energie, die der blockierte zum Senden benötigt.

Weitere Vorteile sind denkbar, müssen jedoch in Testläufen evaluiert werden. Das Problem der Testläufe war jedoch, dass verwendete Lesegeräte nur sehr simple Selektionsmasken unterstützten, mit denen jeweils nur ein Tag selektiert werden konnte. Diese Art der Selektierung entspricht nicht den Anforderungen des EPC Gen2 Air Interface, das die Grundlage unserer Optimierung darstellte.

Evaluierung der Protokolllösungen / Early Prototyping

Ein frühes Prototyping sollte die grundsätzlichen Funktionsweisen der verschiedenen Optimierungsstrategien analysieren. Hierzu wurden Particle-Computer [Decker, u.a. 2005] verwendet, eine vom TecO entwickelte Kommunikationsplattform, die im gleichen Frequenzbereich kommuniziert wie UHF-Tags. Es konnten somit vor dem Einsatz von RFID grundlegende Mechanismen evaluiert werden [Krohn, u. a. 2005.1]. In diesem frühen Stadium wurde auch schon das Einzelhandelszenario evaluiert [Krohn, u. a. 2005.2].

Eine Evaluierung der Protokolllösungen mit EPC Gen2 erwies sich als schwieriger wie angenommen, da die zur Verfügung stehenden Reader gewisse Anforderungen des EPC Gen2 Air Interface nicht erfüllen konnten und auch innerhalb der Projektlaufzeit ein entsprechender Support nicht gefunden werden konnte. Die Evaluierung der neuartigen Datenfusion und die Optimierung des Kanalvielfachzugriffs war somit innerhalb EPC Gen2 nicht möglich. Für die Evaluierung der Software-Modelle musste ein Trick angewendet werden, da auch für diese die notwendige Information über die RSSI (Receiving Signal Strength Indicator) von den Lesegeräten nicht bereitgestellt wird. Es wurde die Dämpfung der Antennenenergie sukzessive erhöht um den Punkt zu bestimmen, an dem der jeweilige Tag nicht mehr gelesen werden konnte. Diese Methodik liefert ähnliche Informationen wie die RSSI, benötigt jedoch wesentlich mehr Zeit pro Messpunkt und Transponder. Um diese Methodik trotzdem anwenden zu können wurde eine automatisierte Messeinrichtung (Abbildung 4) erstellt, mit der vollautomatisch Messreihen durchgeführt werden konnte.

Abbildung 4: (Links) automatische Messeinrichtung vor Regalen mit getagter Ware, (Mitte) automatische Messeinrichtung, (Rechts) Lesegerät im beweglichen Wagen der Messeinrichtung.

Die automatische Messeinrichtung wurde unter anderem auch für die Evaluierung der im Projekt gefertigten Transponder im Einzelhandelsszenario eingesetzt [Kestel 2008].

Simulation / Software-Modelle

Da das Einzelhandelsszenario ein Tag-Aufkommen von mehreren Tausend vorsieht, wobei pro Antenne durchaus mehrere hundert Tags in Reichweite sein können, ist die Simulation der Leseprozesse ein geeignetes Mittel um statistische Signifikanz zu erlangen. Um eine Simulation dynamisch berechnen zu können, muss ein Modell der reellen Zusammenhänge vorhanden sein. Ein Modell für RFID-Prozesse muss sehr viele komplexe physikalische Zusammenhänge, wie Reflexionen, Abschattung und Interferenzen der Mikrowellen abbilden. Außerdem muss es Wechselwirkungen von Tag und Verpackungsmaterial, Tag und Produkt und Tag und Tag berücksichtigen. Ein weiterer Aspekt der Modellierung sind die statistischen Eigenschaften des Kommunikationsprotokolls, welche gerade bei einer großen Anzahl von Transpondern und breitem Lesebereich schwer stabil zu modellieren sind.

Ein Modell kann auch zur Speicherung von Informationen und zur Validierung von Protokolloptimierungen und Datenfusion dienen. Eine Verbesserung der Leseeigenschaften kann eine genauere Modellierung bewirken, was wiederum Verbesserungen des Protokolls impliziert, usw. Die genaue und leistungsfähige Modellierung des Szenarios bewirkt eine optimiertes Resultat unserer Protokoll.- und Datenfusionsalgorithmen. Dies indiziert die zentrale Bedeutung der Modellierung. Die Kommunikation zwischen ERP und Reader-Applikation über das Modell und die Informationsspeicherung und -.extraktion der Reader-Applikation in und aus dem Modell sind schematisch in Abbildung 5 dargestellt.

Abbildung 5: (Links) Kommunikation von ERP und Reader-Applikation über Modell, (Rechts) Informationsaustausch von Reader-Applikationsbestandteilen und Modell.

Statistisches Modell

Erste Versuche wurden mit einer statistischen Modellierung gemacht. Diese Art der Modellierung versprach zunächst eine genügend leistungsfähiges Resultat bei geringen Berechnungszeiten. Da die Berechnungen über das Modell in Echtzeit geschehen sollten um auch die in Echtzeit ablaufenden Protokolle zu unterstützen, war eine geringe Berechnungszeit eine weitere zentrale Anforderung an das Modell.

Der Aufbau des Modells sieht vor, dass die Produkte, an denen sich die Transponder befinden, je nach Art des Produkts und der Verpackung eine gewisse Dämpfungswahrscheinlichkeit der Antennenenergie besitzen. Auf einer Strecke von Antenne zu dem jeweiligen Transponder „multiplizieren“ sich nun die jeweiligen Dämpfungswahrscheinlichkeiten. Je nach Anordnung der Produkte und der Position der Antenne zu diesen ergibt sich eine andere gesamte Dämpfungswahrscheinlichkeit pro Transponder. Diese Wahrscheinlichkeit wird nun mit der physikalisch anzunehmenden Energie verrechnet, die beim jeweiligen Tag ankommt. Eine schematische Darstellung der Modellierung findet sich in Abbildung 6.

Abbildung 6: (Links) Weg (grün) von Antenne zum zu lesenden Tag, (Rechts) Dichtefunktionen der einzelnen Produkte auf dem Weg zum zu lesenden Tag.

Erste Vergleiche von Daten der automatisierten Messeinrichtung und Modellberechnungen haben gezeigt, dass eine solche Modellierung nicht leistungsfähig genug ist. Weitere physikalische Aspekte, wie Reflektionen und Interferenzen, müssten miteinbezogen werden, damit eine genauere Modellbildung möglich wäre. Diese Aspekte sind jedoch nicht mehr nur statistisch zu modellieren, was zu der Idee eines anderen Ansatz des Raytracings geführt hat.

Raytracing

Für statische Umgebungen wurde der Ansatz des Raytracings für RFID schon eingesetzt und hat gezeigt, dass er adäquate Ergebnisse liefern kann [Bosselmann, u.a. 2006]. Die Berechnungen um eine gewisse Genauigkeit zu erlangen sind jedoch sehr aufwendig. Um eine Modellaussage in Echtzeit, mit einer bewegten Antenne als Grundlage, zu erhalten und dies für mehrere hundert Tags in Reichweite ist nur mit sehr viel Rechnungskapazitäten möglich. Da diese Kapazitäten innerhalb des Projektes nicht zur Verfügung standen und auch eine Implementierung und Evaluierung den Rahmen des Projektes gesprengt hätten, wurde dieser Ansatz nicht weiterverfolgt.

Dieses Dokument schließt mit einer Zusammenfassung und dem Literatur- und Quellenverzeichnis.

Zusammenfassung

In der Einführung wurde zunächst das Ziel dieses Dokumentes beschrieben und des weiteren eine Problemspezifizierung gegeben. Die Problemspezifizierung als Grundlage wurde dann die analysierten Möglichkeiten zur Optimierung des Kanal-Vielfachzugriffs geschildert. Hierbei lag der Fokus auf mobilen Lesegeräten, die ein vielfaches an Transpondern in Antennenreichweite bewältigen müssen, als stationäre Lesegeräte, deren Abdeckung optimiert werden kann. Eine Analyse neuartiger Ansätze der Datenfusion hat eine Methodik aufgezeigt, wie Backend-System und Leseapplikation von einem Datenaustausch profitieren können. Eine Evaluation hat gezeigt, dass die neuen Ansätze in Kombination eine höhere Leistungsfähigkeit bewirken, als die Standardverfahren. In einer Phase vor der eigentlichen Evaluierung wurde zuerst mit Protoypen getestet, ob die Verfahren den Ansprüchen genügen.

In einem weiteren Kapitel wurde die zentrale Bedeutung eines Modells zur Datenfusion und Informationsaustausch beschrieben. Es wurden zwei verschiedene Arten von Modellen beschieben, wobei ein statistisches Modell näher untersucht und evaluiert wurde.

Die Projektpartner

dm stellt die Produkte, Regale und den Laden für die Versuche, außerdem Fachwissen über Abläufe im Handel
  manroland ist für das Druckwesen zuständig, insbesondere das Drucken der Antennen mit leitfähiger Tinte
  NXP ist für die RFID-Chips und das Antennendesign zuständig
  PDS stellt die Lesegeräte und Antennen für die Versuche und zu Demonstrationen
  SAP erstellt einen Software-Prototyp inklusive Out-of-stock Warnung, Lagerbestand und einer Anzeige für fehlplatziert Ware.
  Im TecO werden die Lesemodelle untersucht, die Versuche aufgebaut, durchgeführt und analysiert, sowie Produkte und Regale für Demonstrationszwecke vorbereitet.
An der TU Chemnitz wird die Verbindung der RFID-Chips mit den gedruckten Antennen untersucht.

Ausgewählte Publikationen

Robert Kestel (2008) Parametrisierung und Evaluation eines RFID-Lesemodells(August 2007)

Christian Decker, Albert Krohn, Michael Beigl, Tobias Zimmer (2005) The particle computer system, Proc 4th Intl Conf Information Processing Sensor Networks IPSN 05, p. 443-448, IEEE Press, url, doi:10.1109/IPSN.2005.1440969

Albert Krohn, Michael Beigl, Christian Decker, Tobias Zimmer (2005) TOMAC- Real-Time Message Ordering in Wireless Sensor Networks Using the MAC Layer., 2nd International Workshop on Networked Sensing Systems (INSS), San Diego, USA, pdf

Albert Krohn, Tobias Zimmer, Michael Beigl, Christian Decker (2005) Collaborative Sensing in a Retail Store Using Synchronous Distributed Jam Signalling, International Conference on Pervasive Computing (Pervasive) 2005, Lecture Notes in Computer Science (LNCS) 3468 (ed.), p. 237-245, Springer Verlag, pdf

[Patent 2008]
Improving Registering of RFID-Transponder tags utilizing mobile readers on shopping carts, US Patent Nr. 12/046,371, 11.03.2008

[Vogt 2002]
Efficient Object Identification with Passive RFID Tags [pdf]
Harald Vogt
Pervasive 2002, p.98-113

[Bosselmann, u.a. 2006]
Ray Tracing Simulations for UHF Passive RFID Applications
P. Bosselmann, B. Rembold
15th IST Mobile and Wireless Communications Summit, Mykonos, Greece, 4-8 June, 2006

Tags:

Comments are closed.