Najnowsze artykuły
Technologie RFID i EPC | Wydajne i Efektywne Magazynowanie Danych RFID
4211
post-template-default,single,single-post,postid-4211,single-format-standard,ajax_fade,page_not_loaded,smooth_scroll,,qode-theme-ver-1.4.1,wpb-js-composer js-comp-ver-4.3.4,vc_responsive

Wydajne i Efektywne Magazynowanie Danych RFID

Wydajne i Efektywne Magazynowanie Danych RFID

20:51 08 Luty w Inne

Streszczenie

Technologia RFID (ang. Radio Frequency Identification) zaczyna być stosowana jako kluczowy element śledzenia obiektów oraz systemów zarządzania łańcuchowego, gdyż w przyszłości niemal każdy większy sprzedawca będzie używał systemów RFID w celu monitorowania dostaw produktów od dostawców do magazynów. Ze względu na strumieniową naturę odczytu RFID, urządzenia te generują duże ilości danych przy wysokich wskaźnikach produkcji. Zjawisko to jest tym ważniejsze, iż urządzenia RFID są tak tanie, że każdy pojedynczy przedmiot może być oznaczony i tym samym zostawiać „ślad” danych, poruszając się między różnymi lokacjami. Scenariusz ten stwarza nowe wyzwania odnośnie efektywnego i wydajnego wykorzystywania tak dużych ilości danych. W tym artykule została omówiona kwestia kompresji danych RFID w celu uruchomienia urządzeń o ograniczonych zasobach pamięci (takich jak komputery PDA), aby tworzyły zapytania odnośnie magazynów RFID. W szczególności została zarysowana stratna strategia dla malejących krotek zawierających informacje o przedmiotach dostarczanych do innego miejsca w łańcuchu dostaw.

Kategorie i Deskryptory Przedmiotowe

H.4 [Zastosowanie Systemów Informacyjnych]: Różne; E.4 [Kodowanie i Teoria Informacyjna]: Kompaktowanie i kompresja danych

Słowa kluczowe

RFID, magazynowanie danych, kompresja danych, odpowiadanie na prawdopodobne zapytania, systemy informacyjne.

 1. WSTĘP

Najświeższe usprawnienia technologiczne w zakresie umiejętności zbierania danych doprowadziły do wytworzenia mnóstwa strumieni danych w różnych scenariuszach aplikacyjnych. Strumienie danych są swoistym źródłem danych, gdyż są potencjalnie nieskończone i zawierają dane o ciągłym przepływie podczas mierzenia zjawisk fizycznych, takich jak poziomy temperatur, lub innych przejawów działalności człowieka, takich jak ilości kliknięć, rejestry połączeń telefonicznych itd. Strumienie danych mogą być generowane w różnych scenariuszach przez różne urządzenia. Artykuł ten dotyczy strumieni danych RFID, gdyż aplikacje zajmujące się tymi danymi stanowią kluczowy element w procesie śledzenia przedmiotów oraz systemach zarządzania łańcuchamidostaw.
Czasami znaczniki RFID są określane jako elektroniczne kody kreskowe. Faktycznie, znaczniki RFID emitują sygnał zawierający informację identyfikacyjną o produkcie. Znaczniki te mogą być użyte w celu śledzenia produktu od miejsca wyprodukowania, przez dystrybucję, aż do sprzedawców. Te cechy znaczników RFID otwierają nowe perspektywy zarówno na tle sprzętowym, jak i zarządzania danymi. W zasadzie RFID wygeneruje masę nowych danych, którymi należy zarządzać. Przede wszystkim chodzi tu o dane dotyczące czasu i miejsca, co pozwoli nie tylko określić konkretne położenie przedmiotu w całym łańcuchu dostawy, ale także ułatwi określenie trendów na rynku i pozwoli firmom na bardziej precyzyjne planowanie produkcji w zależności od sezonowych potrzeb konsumentów.
Co więcej, firmy szukają kolejnych sposobów używania RFID. Dla przykładu, producenci opon zamierzają użyć chipy RFID w swoich produktach w celu monitorowania zużycia bieżnika. Wiele firm farmaceutycznych planuje chipować opakowania z lekami w celu polepszenia wykrywalności i ułatwienia śledzenia kradzieży leków ściśle kontrolowanych. Linie lotnicze rozważają użycie RFID w częściach samolotów oraz dostawach w celu optymalizacji utrzymania samolotu oraz czasu obsługi naziemnej. Co więcej, Starbucks Corp. rozważa użycie chipów i czytników RFID, aby umożliwić dostawy po godzinach pracy tak, aby nie odciągać obsługi od ich głównego zadania, jakim jest sprzedaż kawy. Koniec końców, Departament Bezpieczeństwa docenił wartość rozszerzania globalnej infrastruktury RFID i zaproponował łańcuch sprzedaży obejmujący RFID jako kluczowy element transformacji systemu bezpieczeństwa.
We wszystkich w/w przypadkach generowane są naprawdę ogromne ilości danych. Owszem, w różnych scenariuszach aplikacje wykorzystują różne formy tego samego atrybutu linii produkcyjnej lub rozpatrują zaledwie niektóre atrybuty, takie jak cena przedmiotu, z pominięciem innych (np. kolor obiektu). Co więcej, dane RFID są ogólnie zbędne, gdyż pojedynczy przedmiot skanowany jest wielokrotnie przez ten sam czytnik. Właściwości te sprawiają, iż budowanie magazynów danych RFID stanowi wyzwanie. Budowa magazynu danych RFID została omówiona w [9], gdzie poruszono  również problem definiowania wydajnego modelu magazynowania obok technik podsumowywania i indeksowania danych. Konkretniej, w [9] przedstawiono model oparty na hierarchii podsumowań, zwany Kuboidami danych RFID zbieranych na różnych poziomach abstrakcji.
Istotnym problemem w projektowaniu systemów analizy danych RFID jest branie pod uwagę możliwości wystąpienia sytuacji, w której użytkownicy wyposażeni w urządzenia posiadające niewielkie zasoby pamięci (np. urządzenia przenośne czy laptopy) muszą dokonać analizy danych, gdy nie mogą połączyć się z głównym magazynem danych. Można temu zaradzić, dostarczając użytkownikom tym skompresowane zarysy danych w celu umożliwienia im dokonania zleconej analizy lokalnie, nawet z pewnym tolerowanym przybliżeniem. Dla przykładu można rozważyć sytuację zarządczyni, która podczas wizyty w lokalnym sklepie swojej firmy chciałaby zebrać informacje nt. łańcucha dostaw (takie jak czas przechowywania dóbr w poszczególnych magazynach, lub średnią ilość przedmiotów będących na danej trasie od magazynu do sprzedawcy).
W tym artykule został zaproponowany plan ramowy radzenia sobie z kompresją masywnych strumieni danych RFID. Główną ideą jest dostarczenie użytkownikom prosty, acz raczej mocny plan ramowy definiowania danych dlań interesujących, odpowiedniego poziomu ziarnistości  oraz ilości dostępnej pamięci, a także otrzymanie (stratnie) skompresowanego widoku pożądanych informacji, spełniającego wymagania pamięci. Konkretniej, strategia kompresji zaprezentowana przez autorów ma na celu wsparcie analizy danych RFID na urządzeniach przenośnych. Zdefiniowana została pasująca struktura danych dla potrzeb zbierania informacji generowanych za pomocą wielu czytników, w której brane pod uwagę są czas dotarcia przedmiotu do danej lokalizacji, czas opóźnienia oraz informacje dotyczące następnej lokacji docelowej w łańcuchu dostaw. Ze względu na ograniczone zasoby pamięci na urządzeniach PDA, zaprojektowano prosty, za to efektywny algorytm kompresji danych, oparty na potrzebach użytkownika. Chociaż kompresja może być stratna, podawana jest granica błędu co do przybliżonych odpowiedzi na zapytania, obliczona na podstawie danych stratnie skompresowanych.

2. PLAN ARTYKUŁU

W rozdziale 3 podany jest przegląd niektórych prac powiązanych z zarządzaniem danymi RFID. W rozdziale43 zostały opisane szczegóły dotyczące cech danych RFID oraz scenariuszy aplikacyjnych. W rozdziale 5 został zdefiniowany zaproponowany przez autorów model danych, jak również algorytm kompresji. Natomiast w rozdziale 5 zostały przedstawione wnioski.

3. POWIĄZANE PRACE

Kwestie wydajnego zarządzania danymi RFID badano w nawiązaniu do różnych scenariuszy aplikacyjnych. Konkretnie, zarządzanie danymi RFID zostało zbadane w [9], gdzie prześledzono problem definiowania wydajnego modelu magazynowania wraz z technikami podsumowywania oraz indeksowania danych. Ściśle mówiąc, w [9] zaproponowano model eliminujący redundancję obecną w danych RFID. Dla przykładu, zaproponowany model przypisuje wielu odczytom RFID ten sam znacznik pochodzący od tego samego czytnika, parami (timein, timeout). Aby dalej kompresować dane RFID, rejestrowane jest jedno przejście w przypadku przedmiotów pakowanych razem (np. płyty CD w tej samej palecie). W końcu przedstawiono model oparty o hierarchię podsumowania, zwany Kuboidami danych RFID zebranych na różnych poziomach abstrakcji w celu umożliwienia przeprowadzenia analizy różnych typów danych.
W [14], w celu śledzenia danych została wykorzystana macierz znaczników RFID. W kwestii szczegółów, zerane zostały trajektorie, a następnie oznaczone przedmioty w celu wyodrębnienia zjawiska typowej czynności (np. dobra pokonujące tę samą ścieżkę w łańcuchu dostaw).
Zważywszy na zadanie główne, jakim jest wysyłanie zapytań do świata fizycznego (czujniki przewodowe lub bezprzewodowe mogą być zaprojektowane niemal tak samo, jak sieci czytników RFID), problem reprezentowania i kwestionowania strumieni danych został niedawno zbadany, jako że ilość aplikacji, generujących olbrzymie ilości danych przepływających w sposób ciągły poprzez sieci komunikacyjne, wzrosła. W szczególności wiele prac badawczych odnosiło się do kwestii tworzenia (przybliżonych) odpowiedzi na zapytania wydane w (nieskończonym) strumieniu danych. Wiele z niedawno zaproponowanych systemów skupiało się na zarządzaniu odczytów sieci czujników, które to mogłoby być uznane za bardziej ogólną sprawę strumieniowania danych RFID.
W [11] zanalizowano wymagania pojemnościowe algorytmów operujących na strumieniach danych i stąd też tworzących tylko jedno (lub niewielką ilość) przejście (przejść) poprzez dane wejściowe. Mówiąc bardziej szczegółowo,  problem został podjęty z innej perspektywy, tj. porównując algorytmy jedno- kontra wieloprzejściowe, deterministyczne kontra ulosowione oraz dokładne kontra szacunkowe. W [3, 4] omówiono problem modelowania nieskończonych strumieni danych oraz odpowiadania na zapytania ciągłe, a także zaprezentowano architekturę zarządzania strumieniem danych.
Gdy dozwolone są przybliżone odpowiedzi na zapytania (zarówno zapytania tradycyjne, jak i w formie strumieni danych), powstają nowe ciekawe wyzwania, badane w wielu ostatnich pracach. W [1] zaproponowano łączone streszczenia w celu dostarczenia przybliżonych odpowiedzi na złożone, zbiorcze zapytania. Streszczenia te usprawniają tradycyjne techniki oparte na statystycznym podsumowywaniu kompletnych zestawów danych. W [6] opisano system obliczania wydajnego podpisu z potężnych strumieni danych. Każdy podpis przechwytuje główne cechy każdej transakcji (np. w przypadku strumienia połączenia telefonicznego będzie on składał się z numeru telefonu dzwoniącego, numeru telefonu odbierającego połączenie oraz pierwszej i ostatniej wieży telefonicznej użytej przy połączeniu). Dla każdego strumienia danych istnieje podział pomiędzy fizycznym zapisem strumienia danych, a ich logiczną reprezentacją. W [2] opisano mechanizm przetwarzania zapytania zwany Eddies, który w sposób ciągły porządkuje operatory w planie zapytań w trakcie jego działania. Wprowadzają one zwłaszcza pojęcie barier synchronizacyjnych oraz momentów symetrii. Wreszcie w [8] opisano nową klasę próbek, zwanych soplami. Sople są to próbki, które dostosowują się do zmian w nakładzie pracy, w oparciu o istotność krotki w związku z wydanymi zapytaniami.

4. GŁÓWNE CECHY DANYCH RFID

System RFID składa się z trzech komponentów: znacznika, czytnika oraz aplikacji używającej dane RFID. Znaczniki składają się z anteny oraz silikonowego chipu zawartego w szkle lub plastiku. Znaczniki dla celów komercyjnych zawierają niewielką ilość informacji. Na przykład, wiele rodzajów znaczników zawiera jedynie liczbę kodową (określaną jako Elektroniczny Kod Produktu (ang. Electronic Product Code, epc)). Obecnie, 96-bitowy epc jest dominującą wersją i zawiera informacje o wytwórcy, kategorię przedmiotu oraz numer seryjny identyfikujący konkretny monitorowany przedmiot. W kwestii trybu transmisji, znaczniki mogą być pasywne, aktywne lub półaktywne. Aktywny znacznik zawiera jakiś rodzaj źródła energii, podczas gdy pasywne działają wyłącznie w oparciu o sygnał radiowy wysyłany przez czytnik. Większość aplikacji RFID używa dziś pasywnych znaczników, ponieważ są one znacznie tańsze w produkcji. Jednakże brak zasilania narzuca znaczne ograniczenia w zakresie zdolności znacznika do dokonywania obliczeń i komunikowania się z czytnikiem. Musi się on znajdować w zasięgu czytnika, aby działać poprawnie. Znaczniki półaktywne używają baterii dla podtrzymania działania chipu, jednak nie w celu komunikacji z czytnikiem. Czytniki lub odbiorniki RFID składają się z modułu radiowego, jednostki sterującej oraz anteny w celu wysyłania zapytań do znaczników drogą radiową (RF). Zawierają one także interfejs komunikujący się z aplikacją (np. kasą w sklepie). Czytniki mogą być przenośne lub zainstalowane w specyficznych miejscach w celu zapewnienia możliwości odczytu znaczników, gdy te przechodzą przez strefę zapytania, tj. strefę, w której czytnik może odczytać znacznik. Strefy zapytania są miejscami, które muszą być monitorowane na potrzeby aplikacji.
W celu wyjaśnienia typowych cech aplikacji RFID, rozważony zostanie łańcuch dostaw, jak na Obrazku 1. Łańcuch od gospodarstwa rolnego do konsumenta posiada wiele etapów. Na każdym z nich dobra są dostarczane do kolejnego etapu, jednak w pewnych przypadkach niektóre z nich można pominąć.

f

f

Rys.1 Łańcuch dostaw

Poniżej zostaną rozróżnione trzy typy czytników:

  1. cykl życia dóbr zaczyna się w wyznaczonej strefie (np. na etapie produkcji, gdzie dobra są znaczone i skąd zaczynają wędrówkę po łańcuchu dostaw) i w związku z tym czytnik w strefie tej rejestruje wyłącznie wprowadzenie dóbr do systemu. Czytnik taki określany jest mianem czytnika źródła.
  2. czytnik na ostatnim etapie cyklu życia dóbr (gdzie znacznik podlega zniszczeniu) określa się mianem czytnika celu.
  3. czytnik na etapach pośrednich cyklu życia dóbr (który rejestruje obecność znaczników w strefie, w której się znajduje) określa się mianem czytnika pośredniego.

Dane RFID mogą być wykorzystywane przez tradycyjne systemy operacyjne zarządzania danymi w celu wykonywania zadań operacyjnych takich, jak dostarczanie dóbr, pakowanie itp., oraz przez aplikacje analizujące dane używane w celu wsparcia zarządców w podejmowaniu decyzji na strategicznym poziomie. W następnym rozdziale zostanie rozpatrzony ten drugi typ aplikacji.

4. ARCHITEKTURA WSPARCIA WYDAJNEGO (SZACOWANEGO) ODPOWIADANIA NA ZAPYTANIA DOT. DANYCH RFID
Strumień RFID składa się z uporządkowanego zbioru źródeł n (np. czytników znaczników) umiejscowionych w różnych pozycjach, oznaczonych przez {r1,…,rn}, generujących n niezależnych strumieni danych, reprezentujących odczyty znaczników. Każdy strumień RFID można postrzegać jako ciąg trójwierszy <idr, epc, τs>, gdzie:

  1. idr {1, .., n} stanowi identyfikator czytnika znaczników (zaobserwować należy, iż przenosi on bezwarunkowo informacje o położeniu przestrzennym czytnika);
  2. epc stanowi kod produktu odczytywany przez źródło identyfikowane poprzez idr;
  1. τs stanowi znak czasu, np. wartość wskazującą na czas produkcji epc przez źródło idr.

W zaprezentowanym modelu, epc jest identyfikatorem powiązanym z pojedynczą skanowaną jednostką (może to być paleta lub pojedynczy przedmiot, w zależności od poziomu ziarnistości wybranego na potrzeby znakowania monitorowanych dóbr). Produkowane przez źródła strumienie danych są wyłapywane przez System Kompresji Strumienia Danych RFID (ang. RFID Data Stream Compression System, RfidDSCS), wykonujący następujące zadania:

RFIDAcquire: zbiera strumienie danych RFID pochodzące z wielu źródeł i przechowuje je w kompaktowej formie;

OnDemandCompress: po otrzymaniu żądania od klienta (PDA), kompresuje wskazane porcje danych i wysyła wynikowe streszczenie do urządzenia wysyłającego żądanie.

RFIDAcquire jest zadaniem wykonywanym w locie, podczas gdy nadchodzą nowe odczyty. Składa się ono z utrzymywania bezstratnego streszczenia odczytów, w których to stosuje się technikę kompresji stratnej. OnDemandCompress wykonuje się, gdy użytkownik domaga się interesujących go porcji danych.

Architektura RfidDSCS została przedstawiona na Obrazku 2.

 Rys. 2Rys. 2 System kompresji strumienia danych.

System Kompresji Strumienia Danych RFID utrzymuje pośredni magazyn lokalny danych RFID, który przechowuje skompresowane informacje o przedmiotach, ich ruchach, kategoriach produktów oraz ich lokalizacjach, a także jest wykorzystywany w celu dostarczania skompresowanych danych RFID na żądanie wysyłane przez urządzenia PDA. Informacje o ruchach przedmiotów przechowywane są w stosunku StayAndGo, zaś informacje o kategoriach produktów i ich lokalizacjach przechowywane są odpowiednio w stosunku ProductCategories i Locations. Związki te reprezentują odpowiednio hierarchię produktów i lokacji. Związek EPCProducts utrzymuje powiązanie pomiędzy epc, a kategorią produktu, tj. każdy epc jest powiązany z krotką na najbardziej szczegółowym poziomie hierarchii Product. Na końcu czytniki RFID stanowią najbardziej szczegółowy poziom w hierarchii Location.

Wnikając bardziej w szczegóły, główną charakterystykę hierarchii Product i Location można opisać następująco:

ProductCategories: hierarchia ta bierze pod uwagę, przy użyciu różnych poziomów ziarnistości, różnice pomiędzy produktami. Dno hierarchii grupuje przedmioty o wspólnych cechach, podczas gdy pośrednie poziomy reprezentują różne zbiory, które można rozpatrzeć (np. chleb → pieczywo → łatwo psujące się → art. spożywcze);

Locations; w hierarchii tej pojedyncze czytniki znajdują się na jej dnie, zaś pośrednie etapy stanowią regiony o tym samym celu (np. czytnik → rząd → magazyn → port → miasto).

StayAndGo zawiera (zagnieżdżone) krotki formy <idt, L, C, τa, τl,DL>, gdzie idt stanowi identyfikator krotki, L lokację, C parę <M, liczba> gdzie M stanowi kategorię produktu epc reprezentowanych przez krotkę oraz liczba stanowi ich liczbę, τa i τl oznaczają następująco czas dotarcia i czas oczekiwania spędzony przez epc w danej lokacji L, zaś DL oznacza zbiór par <did, perc>. Para <did, perc> reprezentuje to, że ułamek perc z epc reprezentowanego przez krotkę tid przemieścił się w kierunku lokacji oznaczonej krotką did. RFIDAcquire zbiera i przetwarza odczyty RFID, dostarczając krotki do dodania do StayAndGo. Warto zauważyć, iż przedstawienie ruchu przedmiotów w relacji StayAndGo musi gwarantować, że nie nastąpi żadna utrata informacji w związku z ruchami przedmiotów pogrupowanymi na podstawie kategorii i lokacji produktów, gdy szczegółowe informacje o epc zostaną utracone.

PRZYKŁAD 1. Możliwa utrata informacji o ruchach przedmiotów pogrupowanych pogrupowanych na podst. kategorii i lokacji podczas grupowania nadchodzących odczytów w tabeli StayAndGo może być zrozumiana poprzez wyjaśnienie następującego scenariusza. Rozpatrywany jest system składający się z pięciu czytników RFID (lokacje r1,…, r5) i 20 przedmiotów (ołówków) należących do kategorii „Ołówki”: 10 ołówków zbliża się do czytnika r1 w czasie 0, pozostaje w tej lokacji przez 10 jednostek czasu i opuszcza ją, przemieszczając się w kierunku r3, gdzie przybywa w czasie 15. Wtedy, 6 z tych ołówków opuszcza lokację r3 w czasie 20 i przemieszcza się w kierunku lokacji r4. Przybywają do  r4 o czasie 25 i pozostają tam przez 5 jednostek czasu. Pozostałe 4 ołówki opuszczają lokację r3 o czasie 20 w kierunku lokacji r5.Przybywają doń o czasie 25 i pozostają tam przez 5 jednostek czasu.

Co więcej, kolejne 10 ołówków przybywa do czytnika r2 o czasie 0 i pozostaje tam przez 5 jednostek czasu. Opuszczają to miejsce i przemieszczają się w kierunku lokacji r3, do której przybywają o czasie 15. Wtedy, 4 spośród tych ołówków opuszczają lokację r3 o czasie 20, przemieszczając się w kierunku lokacji r4. Przybywają doń o czasie 25 i pozostają tam przez 5 jednostek czasu.

Pozostałe 6 ołówków opuszcza lokację r3 o czasie 20, poruszając się w kierunku r5. Przybywają tam o czasie 25 i pozostają przez 5 jednostek czasu.

            Scenariusz ten przedstawia Obrazek 3, gdzie linie ciągłe reprezentują ruchy ołówków wchodzących do systemu w lokacji r1, a linie przerywane oznaczają ołówki wchodzące do systemu w lokacji r2.

 Rys. 3

Rys. 3 Krótki przepływ przez czytniki

 

Zostanie najpierw rozpatrzony przypadek, gdy relacja StayAndGo przedstawia opisany wyżej scenariusz za pomocą następujących krotek: t1 = <1, l1, < Ołówek, 10>, 0, 10, [<3, 1>]>,

t2 = 2, l2, Ołówek, 10, 0, 10, [3, 1], t3 = 3, l3, Ołówek,

20, 10, 25, [4, 0.5, 5, 0.5] 1. Stosując ten przykład StayAndGo nie da się udzielić odpowiedzi na zapytanie o treści „ile ołówków przemieszczono od czytnika r1 do czytnika r4?”, gdyż ołówki, które zostały wprowadzone do systemu przez czytnik r1 ulegają przemieszaniu z tymi, które do systemu trafiły poprzez czytnik r2 w krotce t3.

            Jako że StayAndGo powinien przechowywać informacje o ruchu ołówków bezstratnie, w/w przykład nie powinien wynikać z RFIDAcquire. Bezstratne przedstawienie ruchów ołówków jest przykładem StayAndGo zawierającym następujące krotki: t1 = <1, l1, < Ołówek, 10>, 0, 10, [<3.1, 1>]>, t2 = <2, l2, < Ołówek, 10>, 0, 10, [<3.2, 1>]>,

t3.1 = <3.1, l3, < Ołówek, 10>, 10, 25, [<4.1, 0.6>, <5.1, 0.4>]>

t3.2 = <3.2, l3, < Ołówek, 10>, 10, 25, [<4.2, 0.4>, <5.2, 0.6>]>.

                OnDemandCompress ma na celu spełnianie żądań wydawanych za pośrednictwem komputerów PDA. Każde żądanie określa potrzebne dane oraz ich poziom ziarnistości w hierarchii ProductCategories oraz ProductLocations, jak również ilość miejsca dostępnego na skompresowane dane. Dane RFID wysyłane do PDA składają się z żądanych fragmentów relacji ProductCategories i ProductLocations (uzyskiwanych poprzez dostosowywanie relacji pierwotnej do odpowiedniego poziomu ziarnistości) oraz danych dotyczących ruchów przedmiotów przechowywanych w relacji zwanej RFIDMove tworzonej na urządzeniu PDA, które zgłosiło żądanie.
Schematy RFIDMove oparte są na StayAndGo. RFIDMove zawiera (zagnieżdżone) krotki w formie <idt, L, PCs, τa, τl,DL>, gdzie idt, L, τa, τl oraz DL posiadają tę samą semantykę nadaną krotkom w StayAndGo, zaś  PCs stanowi zbiór w formie {<M1, c1>, <M2, c2>,…, <Mn, cn>}, gdzie dla każdego i [1..n], Mi oznacza kategorię produktu na wybranym poziomie ziarnistości, zaś c1 oznacza ilość przedmiotów w każdej kategorii produktów. Należy zaobserwować, że idt, L, τa, τl oraz DLodnoszą się do każdej kategorii produktu obecnej w  PCs.

W celu lepszego wyjaśnienia powyższego modelu, Obrazek 4 przedstawia przykład łańcucha dostaw opartego na technologii RFID, składającego się z czterech czytników odpowiadających dwóm różnym lokacjom, oznaczonym jako l1 i l2, a także trzem kategoriom produktów (makaron, pomidory i fasola zielona) przedstawionym na tabeli jako odpowiednio P, T oraz GB. Początkowo do lokacji l1 dociera 10 opakowań makaronu, 8 puszek pomidorów i 5 puszek fasoli zielonej, po czym towary te przemieszczają się dalej w łańcuchu dostaw, zaś czas latencji wyrażany jest w minutach.

5.  KOMPAKTOWE PRZEDSTAWIANIE ODCZYTÓW

W rozdziale tym zostaną opisane czynności dokonywane przez RFIDAcquire w celu kompaktowego przedstawiania odczytów w relacji StayAndGo. Architektura modułu RFIDAcquire przedstawiona została na Obrazku 5.

 Rys. 5

Rys. 5 Moduł architektury RFID

Jak widać na załączonym obrazku, RFIDAcquire wykonuje dwa zadania (Merge oraz Consolidate):

 Merge łączy poszczególne sąsiadujące odczyty, odnoszące się do tego samego epc i tego samego czytnika, w krotki w formie <idr, epc, τa, τl> (odczyt zamrożony), które są następnie przekazywane do Consolidate. Odczyt zamrożony <idr, epc, τa, τl>stanowi, że produkt zidentyfikowany poprzez epc przybył o czasie  τa do rzędu powiązanego z czytnikiem idr, a następnie pozostał weń przez τl jednostek czasu. Stąd też τa oznacza czas przybycia, zaś τl czas latencji.

Consolidate odpowiada za konsolidację odczytów zamrożonych poprzez scalanie odczytów pochodzących od tego samego czytnika, o tym samym czasie przybycia i latencji, a także odnoszących się do epc tej samej kategorii produktów. Dalsze ograniczenia stosuje się wobec pogrupowanych odczytów, gdyż relacja StayAndGo ma gwarantować, że żadna informacja o ruchach produktów nie zostanie utracona. Szczegółowy opis tych ograniczeń zostanie zawarty w dalszej części tego rozdziału, gdzie opisane zostaną czynności wykonywanych w ramach Consolidate.

RFIDAcquire korzysta z dwóch stadialnych relacji: UpdatableReadings oraz UpdatableStays. Krotka w UpdatableReadings występuje w formie <idr, epc, τa, τl> i posiada tę samą semantykę, co odczyt zamrożony, lecz można ją zaktualizować podczas dostarczania nowych odczytów z czytnika idr. Dla każdego epc, przedstawiana jest najwyżej jedna krotka w UpdatableReadings. Gdy pojawiają się nowe odczyty (w formie trójwiersza <idr, epc, τs>), mogą nastąpić trzy sytuacje:

–         UpdatableReadings nie zawiera żadnej krotki powiazanej z epc: wtedy nowa krotka <idr, epc, τs, 0> wstawiana jest w UpdatableReadings (co oznacza, że przybycie epc do rzędu z czytnikiem idr zostało zarejestrowane o czasie τs – czas latencji początkowo wynosi 0);

–         UpdatableReadings zawiera krotkę powiązaną z epc utworzonym przez r: oznacza to, że od poprzedniego odczytu pobranego dla epc produkt ten pozostawał w rzędzie monitorowanym przez r. Stąd też krotka <idr, epc, τa, τl> jest aktualizowana już w UpdatableReadings poprzez wykonanie zadania τl = τs τa.

–         UpdatableReadings zawiera krotkę powiązaną z epc utworzonym przez czytnik r‚ gdyidr =/= idr:oznacza to, że od poprzedniego odczytu pobranego dla epc produkt ten został przemieszczony z rzędu monitorowanego przez r’ do rzędu powiązanego z r. W związku z tym wykonywane są dwie czynności: po pierwsze, krotka <idr, epc, τa, τl> już na etapie UpdatableReadings jest zeń usuwana i przekazywana do Consolidate; wtedy krotkę <idr, epc, τs, 0> wstawia się do UpdatableReadings.

Należy zaobserwować, że odczyt jest zamrożony, co oznacza, że opisuje on sytuację, która nie może ulec zmianie do momentu dostarczenia nowych odczytów. W zasadzie odczyt zamrożony <idr, epc, τa, τl> oznacza, że produkt epc dotarł do rzędu monitorowanego przez czytnik r o czasie τa, pozostawał weń przez okres τl, po czym został dalej przemieszczony do innej lokacji.

Consolidate wykorzystuje nadchodzące odczyty zamrożone do tworzenia nowych krotek, które następnie umieszczane są w relacji StayAndGo. W tym celu korzysta ono z relacji UpdatableStays, zawierającej krotki w formie <idt, idr,EPC, τa, τl>, gdzie idt oznacza identyfikator krotki, zaś EPC stanowi zbiór epc należących do jednej kategorii produktów. Właściwie krotka w UpdatableStays przedstawia grupy epc, które ułożono razem w jednej lokacji podczas tego samego odstępu czasowego i które razem przemieszczano aż do lokacji docelowej. Mówiąc bardziej formalnie, krotka t = <idt, idr,EPC, τa, τl> w UpdatableStays posiada następującą semantykę: przedmioty pojawiające się w EPC przybyły o czasie τa do rzędu powiązanego z czytnikiem idr, po czym pozostały tam przez okres τl jednostek czasu. W związku z tym  τa oznacza czas przybycia, zaś τl czas latencji. Co więcej, albo wszystkie produkty w EPC po raz pierwszy pojawiły się w systemie o czasie τa, albo pojawiają się pogrupowane w każdej krotce w UpdatableStays, która zawiera co najmniej produkt występujący w EPC, o czasie przybycia mniejszym niż τa, np. gdy krotka <idt , idr ,EPC’, τa, τl> w Updatable Status przyjmuje wartość taką, że jeżeli EPC EPC = τa τa wtedy EPC EPC’. Wreszcie na każdy epc i na każdy czytnik RFID przypada maksymalnie jedna krotka w UpdatableStays.

Zanim zostaną zdefiniowane czynności wykonywane przez Consolidate, zostanie zaprezentowanych kilka uwag. Określiwszy epc, nadaje się mu kategorię produktu, jako PC(epc), a określiwszy zbiór EPC składający się z epc przynależących do tej samej kategorii produktu, nadaje się ją zbiorowi jako PC(EPC). W końcu, określiwszy epc oraz chwilę τ, oznaczany jest zbiór krotek w UpdateStays, zawierający epc o czasie przybycia mniejszym niż  τ, jako Tp(epc, τ), np. Tp(epc, τ) = {<idt, idr,EPC, τa, τl> UpdatableStays | epc EPC ∧  τaτ}. Krotka w Tp(epc, τ) z najwyższym czasem przybycia oznaczana jest jako lastTp(epc, τ) (jeżeli Tp(epc, τ) jest zbiorem pustym, lastTp(epc, τ) zwraca pustą krotkę < >).

Należy zaobserwować, że skoro na każdą krotkę t w UpdatableStays twierdzi się, że albo wszystkie przedmioty należące do t przybyły do systemu po raz pierwszy o czasie  τ, albo pojawiają się pogrupowane w każdej krotce w UpdatableStays, która zawiera przynajmniej jeden produkt występujący w t i, której czas przybycia wynosi mniej niż  τ, następuje, iż dla każdej pary epc’, epc” występującej w krotce t w UpdatableStays uważa się, że lastTp(epc’, τ) = lastTp(epc”, τ), gdzie τ oznacza czas przybycia t. W związku z tym określiwszy krotkę <idt, idr,EPC, τa, τl> w UpdatableStays,  za pomocą lastTp(EPC, τ) unikatową krotkę lastTp(epc, τ), gdzie epc EPC.

            Zostaną teraz opisane czynności wykonywane przez Consolidate. Gdy nowy odczyt zamrożony <idr, epc, τa, τl> zostanie otrzymany przez Consolidate, może nastąpić jedna z następujących sytuacji:

Updatable Stays zawiera krotkę <idt, idr,EPC, τa, τl> s. t. PC(epc) = PC(EPC):

w tym przypadku, jeżeli UpdatableStays zawiera krotkę <idtidr ,EPC’, τa, τl> s. t. PC(epc) = PC(EPC’),  a lastTp(epc, τa) pokrywa się z lastTp(EPC’, τa), krotka <id’t,idr,EPC’, τa, τl> w UpdatableStays podlega aktualizacji przez krotkę <id’t,idr,EPC’ {epc}a,τl>, w przeciwnym razie krotka <idtidr ,EPC, τa, τl>, gdzie id’t stanowi nowo wygenerowany identyfikator krotki, jest wstawiana w UpdatableStays.

UpdatableStays nie zawiera żadnej krotki <idt, idr,EPC, τa, τl> s. t. PC(epc) = PC(EPC):

w tym przypadku krotka <idtidr ,EPC, τa, τl>, gdzie id’t stanowi nowo wygenerowany identyfikator krotki, jest wstawiana w UpdatableStays


W obu przypadkach dla każdej krotki t’ = <idt, id’r,EPC’,τ’a, τ’l> w UpdatableStays, co do której epc EPC’ oraz spełniającej warunki:

Tp(EPCa) jest zbiorem pustym, oraz

albo  idr stanowi czytnik docelowy, albo dla każdego epc’ w EPC’ istnieje krotka <idt, id’r,EPC’,τ’a, τ’l> w UpdatableStays, wobec której epc’ EPC” i τ”a > τ’a

t’ usuwa się poprzez UpdatableStays i wstawiana jest nowa krotka w StayAndGo.

Nowa krotka wstawiona w StayAndGo przybiera formę <id’t, id’r, C’, τ’a, τ’l,DL’>, gdzie

C’ = <PC(EPC’),|EPC’|>, a

 DL’ to lista par zawierających parę

<idt, > dla każdej krotki <idt”,id”r,EPC”,τ”a, τ”l> w UpdatableStays spełniającej następujące warunki:

1. EPC’ EPC” =/= ∅, oraz

2. dla każdej krotki <idt*, id*r,EPC*,τ*a, τ*l> w UpdatableStays z EPC’ EPC* EPC’ EPC” przyjmuje się, że τ*aτ”a.

6.  KOMPRESOWANIE I WYSYŁANIE DANYCH DO URZĄDZEŃ PDA

W rozdziale tym opisaną opisane czynności wykonywane przez OnDemandCompress w celu spełnienia żądań użytkownika. Żądanie użytkownika stanowi trójwiersz w formie <pcGran, locGran, reqspace>, gdzie pcGran oznacza   poziom ziarnistości hierarchii kategorii produktu, locGran oznacza poziom ziarnistości hierarchii lokacji, zaś reqspace oznacza maksymalną przestrzeń pamięci dostępnej na urządzeniu użytkownika. OnDemandCompress uzyskuje dostęp do relacji StayAndGo, ProductCategories oraz Locations w celu uzyskania (stratnie) skompresowanego magazynu danych RFID, zawierającego relacje RFIDMove, PC, LOC, gdzie RFIDMove jest stratnie skompresowaną wersją StayAndGo, a PC (i odpowiednio LOC),  stanowi widok hierarchii kategorii produktu (i odpowiednio lokacji) o konkretnym poziomie ziarnistości. Co więcej,skoro w celu uzyskania relacji RFIDMove stosowana jest technika kompresji stratnej, najwyższy błąd względny wprowadzony podczas dokonywania kompresji stratnej jest również zwracany.
Algorytm 1 ukazany na Obrazku 6 implementuje funkcję OnDemandCompress. Algorytm 1 odbiera żądanie PDA jako dane wejściowe i uzyskuje dostęp do magazynu danych RFID (RW) w celu uzyskania stratnie skompresowanej wersji CR, określanej jako CRW, wymaganej przez PDA. Używa on jako lokalnej zmiennej trójwiersza pt w formie <t1, t2, e>, gdzie  t1 oraz t2 oznaczają krotki w RFIDMove, zaś e stanowi błąd względny wprowadzony poprzez scalanie  t1 z t2 (semantyka e zostanie wyjaśniona później w opisie funkcji merge). Trzy komponenty pt oznaczane są odpowiednio jako pt[1], pt[2], pt[3].
Funkcja OnDemandCompress najpierw tworzy początkową wersję CRW bez utraty jakichkolwiek informacji związanych z określonymi poziomami agregacji pcGran i locGran. Uzyskuje się ją poprzez odwoływanie się do funkcji project, która buduje relacje RFIDMove, PC, LOC, jak następuje:

Dla każdej krotki <idt, L, <M,c>, τa, τl,DL> w StayAndGo, funkcja projekt wstawia krotkę <idt, L’, {<M’,c>}, τa, τl,DL>, gdzie L’ oznacza lokację odpowiadającą L na poziomie agregacji locGran, zaś M’ oznacza kategorię produktu odpowiadającą M na poziomie agregacji pcGran;

PC i LOC uzyskuje się w trywialny sposób, poprzez rzutowanie ProductCategories i Locations na poziomy agregacji, odpowiednio locGran i pcGran.

Skompresowany magazyn danych RFID powstaje wtedy poprzez wielokrotne dobieranie pary krotek  t1, t2 w RFIDMove i zastępywanie ich unikatowymi krotkami powstającymi w wyniku scalania t1 z t2. Krotki wybrane do scalenia stanowią te, które wprowadzą najmniejszy błąd względny po ich scaleniu.
Niech
t = <idt, L, PCs, τa, τl,DL> – gdzie

PCs = {<  M1, c1>,, <Mn, cn>} i DL =

[<d1, perc1>, , <dm, percm>] – i t’ = <id’t, L, , τ’a, τ’l,DL’>  – gdzie PCs’ = {<M’1, c’1>,,<M’k,c’k>} i DL’ = [<d’1,perc1>,,dh,perch>]

stanowić będą dwie krotki w RFIDMove. Funkcja merge(t,t’) zwraca krotkę t” = <idt,L,PCs”,τ”a,τ”l ,DL”>, gdzie

 dt  oznacza nowo utworzony identyfikator krotki;

τ”a = [WZÓR], tj.  τ”a stanowi średnią ważoną   τ’a oraz  τ’a w odniesieniu do ilości przedmiotów w PCs’ i PCs;

τ”l  = [WZÓR], tj. τ”l stanowi średnią ważoną τ’l  i τl  w odniesieniu do ilości przedmiotów w PCs’ i PCs;

PCs” zawiera następujące pary:

◦      <M, c> jeżeli <M, c>  ∈ PCs i nie ma pary z kategorią produktu M w PCs’;

◦      <M, c + c’> jeżeli <M’, c’> ∈ PCs’ i nie ma pary z kategorią produktu M’ w PCs;

◦      <M, c + c’> jeżeli istnieje para <M, c> ∈ PCs i para <M, c’> ∈ PCs;

DL” zawiera następujące pary:

◦      [WZÓR] jeżeli <d, perc> ∈ DL i nie istnieje para z celem d w DL’;

◦      [WZÓR] jeżeli <d’, perc’> ∈ DL’ i nie istnieje para z celem d’ w DL;

◦      [WZÓR] jeżeli <d, perc> ∈ DL i <d, perc’> ∈ DL’;

Obliczenie najwyższego błędu względnego dla krotki t zwróconego z aplikacji funkcji merge do pary krotek w RFIDMove uzyskuje się przez obserwację pierwotnych krotek w relacji StayAndGo. Mówiąc bardziej szczegółowo, najwyższy błąd względny dla krotki t stanowi maksimum pomiędzy 1) najwyższym błędem względnym w stosunku do czasu przybycia, 2) najwyższym błędem względnym w stosunku do czasu latencji oraz 3) najwyższym względnym błędem procentowym dla każdego celu d wymienionego w t. W szczególności najwyższy błąd względny w stosunku do czasu przybycia jest najwyższą różnicą względną dla każdej krotki t’ w StayAndGo, która nadaje t pomiędzy czasem przybycia t i czasem przybycia t’. Podobnie najwyższy błąd względny czasów latencji dla t stanowi najwyższą różnicę względną dla każdej krotki t’ w StayAndGo, która nadaje t pomiędzy czasem latencji t i czasem latencji t’. Wreszcie najwyższy stosunkowy błąd procentowy dla każdego celu d wspomnianego w t stanowi najwyższą różnicę stosunkową dla każdej krotki t’ w StayAndGo, która nadaje t pomiędzy procentem epc na kategorię produktu, który przemieszcza się do d w t’ i procentem powiązanym z d w t.

Funkcja selectMinErrorPair oblicza najwyższy błąd względny każdej pary krotek w RFIDMove zgodnie z w/w definicją i wybiera pary krotek o najmniejszej wartości najwyższego błędu względnego.

Na koniec zastąpienie pary krotek t, t’ w RFIDMove krotką t” zwracaną przez merge(t,t’) następuje poprzez zamianę w każdej krotce w RFIDMove celów odnoszących się albo do t, albo t’ wraz z t”. W przypadku, gdy oba t i t’ są wspomniane w liście celów DL pary <t, perc> i <t’, perc’> zastępuje się parą <t”,perc + perc’>.

7. WNIOSKI

W tym dokumencie został poruszony problem (stratnej) kompresji strumieni danych RFID. Została zdefiniowana właściwa struktura danych, przedstawiająca skompresowane magazyny RFID oraz zaproponowano architekturę, która pozwala zbierać odczyty pochodzące z dostępnych czytników RFID, a następnie przedstawiać je w kompaktowy sposób. Użytkownicy mogą zgłaszać żądania o uzyskanie stratnie skompresowanego widoku magazynu RFID, określając ilość dostępnego miejsca [w pamięci] i pożądany poziom ziarnistości. Architektura taka może być efektywnie wykorzystywana do zaspakajania informacyjnych potrzeb w kontekstach aplikacyjnych, gdy urządzenia użytkowników, takie jak komputery PDA, posiadają małe zasoby pamięci. Po otrzymaniu żądanych danych, użytkownicy mogą lokalnie

(tj. bez potrzeby łączenia się z serwerem) wysyłać zapytania w odniesieniu do nich. Różnice w błędach przybliżenia (ze względu na zastosowanie strategii stratnej kompresji danych) dostarczane wraz ze skompresowanymi danymi pozwalają użytkownikom określić dokładność zadań analitycznych wykonywanych na tych danych.

 

Źródła:

[1] S. Acharya, P. Gibbons, V. Poosala, and

S. Ramaswamy. Join Synopses for Approximate Query

Answering. In Proccedings of Nineteenth ACM

SIGACT-SIGMOD-SIGART Symposium on Principles

of Database Systems, Philadelphia, Pennsylvania,

USA, pages 275–286, 1999.

[2] R. Avnur and J. M. Hellerstein. Eddies: Continuously

adaptive query processing. In Proceedings of the ACM

SIGMOD international conference on Management of

data, Dallas, Texas, USA, pages 261–272, 2000.

[3] B. Babcock, S. Babu, M. Datar, R. Motwani, and

J. Widom. Models and Issues in Data Stream Systems.

In Twenty-first ACM SIGACT-SIGMOD-SIGART

Symposium on Principles of Database

Systems,Madison, Wisconsin, USA, pages 1–16, 2002.

[4] S. Babu and J. Widom. Continuous Queries over Data

Streams. SIGMOD RECORD, 30(3):109–120, 2001.

[5] S. S. Chawathe, V. Krishnamurthy, S. Ramachandran,

and S. Sarma. Managing RFID Data. In Proc. of the

30th VLDB Conference, pages 1189–1195, 2004.

[6] C. Cortes, K. Fisher, D. Pregibon, A. Rogers, and

F. Smith. Hancock: A Language for Extracting

Signatures from Data Streams. In Proceedings of the

sixth ACM SIGKDD international conference on

Knowledge discovery and data mining, Boston,

Massachusetts, United States, pages 9–17, 2000.

[7] C. Floerkemeier. RFID Handbook: Fundamentals And

applications in Contactless Smart Cards and

Identification. Wiley and Sons, 2003.

[8] V. Ganti, M. L. Lee, and R. Ramakrishnan. ICICLES:

Self-tuning Samples for Approximate Query

Answering. In Proceedings of 26th International

Conference on Very Large Data Bases, Cairo, Egypt,

pages 176–187, 2000.

[9] H. Gonzalez, J. Han, X. Li, and D. Klabjan.

Warehousing and Analyzing Massive RFID Data Sets.

In Proc. of the ICDE conference, page to appear, 2006.

[10] J. Han and M. Kamber. Data Mining: Concepts and

Techniques. Morgan Kaufmann, 2000.

[11] M. Henzinger, P. Raghavan, and S. Rajagopalan.

Computing on data streams. Technical Report

1998-011, Digital Systems Research Center, 1998.

Available at

http://www.research.digital.com/SRC/.

[12] Y. Hu, S. Sundara, T. Chorma, and J. Srinivasan.

Supporting RFID-based Item Tracking Applications in

Oracle DBMS Using a Bitmap Datatype. In Proc. of

the 31st VLDB Conference, pages 1140–1151, 2005.

[13] N. Jiang and L. Gruenwald. Research issues in data

stream association rule mining. SIGMOD, 2006.

[14] Y. Liu, L. Chen, J. Pei, Q. Chen, and Y. Zhao. Mining

frequent trajectory patterns for activity monitoring

using radio frequency tag arrays. In PerCom, pages

37–46, 2007.

[15] S. Sarma. Integrating RFID. ACM Queue, 2(7):50–57,

2004.

[16] S. E. Sarma, D. L. Brock, and K. Ashton. The

networked physical world. In White paper, MIT

Auto-ID Center, http://archive.epcglobalinc.org/

publishedresearch/MIT-AUTOID-WH-001.pdf, 2000.

[17] S. E. Sarma, S. A. Weis, and D. W. Engels. Rfid

systems, security and privacy implications. In White

paper, MIT Auto-ID Center,

http://archive.epcglobalinc.org/

publishedresearch/MIT-AUTOID-WH-014.pdf, 2002.

[18] D. Shuping and W. Wright. Geo-temporal

visualization of rfid providing global visibility of the

dod supply chain. Directions Magazine, 2005.

[19] F. Wang and P. Liu. Temporal Management of RFID

Data. In Proc. of the 31st VLDB Conference, pages

1128–1139, 2006.

Autorzy:  Bettina Fazzinga, Sergio Flesca, Filippo Furfaro, Elio Masciari

Dostępność artykułu: baza  ACM DIGITAL „Efficient and Effective RFID Data Warehousing”

Artykuł przetłumaczyła: Aleksandra Sałasznik

Data i miejsce: 19.02.2014, Wrocław