Adaptive Cleaning For RFID Data Streams
Adaptive Cleaning for RFID Data StreamsShawn Ryan JefferyMinos GarofalakisMichael FranklinElectrical Engineering and Computer SciencesUniversity of California at BerkeleyTechnical Report No. TechRpts/2006/EECS-2006-29.htmlMarch 27, 2006
Copyright 2006, by the author(s).All rights reserved.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission.
Adaptive Cleaning for RFID Data StreamsShawn R. JefferyMinos GarofalakisMichael J. FranklinUC BerkeleyIntel Research BerkeleyUC BerkeleyABSTRACTA major impediment to the widespread adoption of RFIDtechnology is the unreliability of the data streams producedby RFID readers; a 30% drop rate is not uncommon forRFID deployments. To compensate, most RFID middlewaresystems provide a “smoothing filter”, a sliding-window aggregate that interpolates for lost readings. Typically, thesemiddleware systems require the application to fix the sizeof the smoothing window in order to produce clean RFIDdata. Window-size selection, however, is a non-trivial problem: the window must be large enough to smooth lost readings but small enough to accurately capture tag movement.Furthermore, the ideal size may change over the course ofthe RFID deployment.In this paper, we propose SMURF, the first declarative,adaptive smoothing filter for RFID data cleaning. SMURFmodels the unreliability of RFID readings by viewing RFIDstreams as a statistical sample of tags in the physical world,and exploits techniques grounded in sampling theory todrive its cleaning processes. Through the use of tools suchas binomial sampling and π-estimators, SMURF continuously adapts the smoothing window size in a principledmanner to provide accurate RFID data to applications.1.INTRODUCTIONRFID (Radio Frequency IDentification) technologypromises revolutions in areas such as supply chain management and ubiquitous computing enabled by pervasive,low-cost sensing and identification [17]. One of the primary factors limiting the widespread adoption of RFIDtechnology is the unreliability of the data streams producedby RFID readers [8, 22]. The observed read rate (i.e.,percentage of tags in a reader’s vicinity that are actuallyreported) in real-world RFID deployments is often in the60 70% range [8, 20, 22]; in other words, over 30% of thetag readings are routinely dropped. Even higher drop ratesare possible depending on environmental characteristics(e.g., in the presence of metal [18]).Unfortunately, such error rates render raw RFID streamsessentially useless for the purposes of higher-level applications (such as accurate inventory tracking). Instead, RFIDmiddleware systems are typically deployed between the readers and the application(s) in order to correct for droppedreadings and provide “clean” RFID readings to applicationlogic. The basic data-cleaning mechanism in most such systems is a temporal “smoothing filter”: a sliding window overthe reader’s data stream that interpolates for lost readingsfrom each tag within the time window [19, 23]. The goal, ofFigure 1: Tension in setting the smoothing-windowsize for tracking a single tag (dark bars indicate thetag is present/read): small windows fail to fill indropped readings (false negatives); large windowsfail to capture tag movement (false positives).course, is to reduce or eliminate dropped readings by givingeach tag more opportunities to be read within the smoothingwindow. While the APIs for RFID middleware systems vary,smoothing filter functionality can be expressed as a simplified stream query (e.g., in CQL [6]) as shown in Query 1 (fora 5 second window).Query 1 CQL Smoothing Filter to Correct for DroppedReadings.SELECTdistinct tag idFROMrfid readings stream [Range ’5 sec’]GROUP BY tag idTypically, the RFID middleware system requires the application to fix the smoothing window size (as in the aboveCQL statement). Setting the window size, however, is anon-trivial task: the ideal smoothing-window size needs tocarefully balance two opposing application requirements (asshown in Figure 1): ensuring completeness for the set oftag readings (due to reader unreliability) and capturing tagdynamics (due to tag movements in and out of the reader’sdetection field).– Completeness: To ensure that all tags in the reader’s detection range are read, the smoothing window must be largeenough to correct for reader unreliability. Small windowsizes cause readings for some tags to be lost, leading to falsenegatives (i.e., tags mistakenly assumed to have exited thereader’s detection range) and, consequently, a large underestimation bias (e.g., always under-counting the tag population). Adjusting the window size for completeness dependson the reader’s read rate, which, in turn, depends on boththe type of reader and tag as well as physical surround-
ings [13, 18].accurate, unbiased data to applications. (Section 3)– Tag Dynamics: Using a large smoothing window, on theother hand, risks not accurately detecting tag movementswithin the window, leading to false positives (i.e., tags mistakenly assumed to be present after they have exited thereader’s detection range). In the worst case, the windowmay smooth over one or more tags leaving and returning,thus completely missing the variation in the underlying “signal” (Figure 1). Adjusting the window size for tag dynamicsdepends on the movement characteristics of the tags, which,in turn, can vary significantly depending on the application;for instance, a tag sitting on a shelf exhibits a very differentmovement pattern from a tag on a conveyor belt.Any RFID deployer must seriously consider and study thefactors governing the window size as discussed above whendesigning a cleaning scheme for raw RFID streams; in fact,ascertaining environment characteristics and configuring thehardware and middleware to account for these factors represents a large portion of the monetary and time cost of suchdeployments [31]. Furthermore, no single window size is expected to be effective over the lifetime of a deployment; thus,either the window size must be repeatedly reconfigured, orthe quality of the data suffers.The fundamental issue with any static windowing approach is that the window size is a non-declarative, low-levelparameter that should not be exposed to the applicationlevel. Conceptually, what the application expects from theRFID middleware is a stream of readings that represent anaccurate picture of reality; in other words, the applicationis only interested in accurately capturing a true underlying“signal” (such as individual tag readings or tag populationcounts) over time. Requiring the application to fix asmoothing-window size, however, essentially forces theapplication to decide beforehand exactly how to producethis “accurate” data stream. An Adaptive Smoothing Filter for RFID Data.Building on SMURF’s sampling-based foundation, wepropose two novel, adaptive smoothing mechanisms for (a)cleaning the readings of single tag using techniques based onbinomial sampling [12] (per-tag cleaning), and (b) cleaningan aggregate signal (e.g., count) over a tag population basedon π- (or Horvitz-Thompson) estimators [28] (multi-tagcleaning). (Section 4)Our Contributions. In this paper, we introduce SMURF(Statistical sMoothing for Unreliable RFid data), the firstdeclarative, adaptive smoothing filter for cleaning raw RFIDdata streams. Unlike conventional techniques, SMURF doesnot expose the smoothing window parameter to the application; instead, it determines the “right” window size automatically and continuously adapts it over the lifetime of thesystem based on observed readings.The main challenge for an adaptive smoothing schemeis to distinguish between periods of dropped readings andperiods when a tag has moved. To address this problem,SMURF uses a sampling-based approach. One of the keyideas behind SMURF’s adaptive algorithms is that RFIDdata streams can be modeled as a random sample of thetags in a reader’s detection range. Through this samplebased view of observed RFID readings, SMURF employsalgorithms grounded in statistical sampling theory to driveits adaptive smoothing techniques. More concretely, ourcontributions can be summarized as follows. A Sampling-based View of RFID Data Streams.SMURF exploits a novel view of RFID unreliability bymodeling observed RFID readings as an unequal-probabilityrandom sample of tags in the physical world. This allowsSMURF to balance the tension between reader unreliabilityand tag dynamics in a principled, statistical manner, bycontinuously adapting the smoothing strategy to provide An Experimental Study Validating the Effectiveness of SMURF’s Cleaning Algorithms. We present adetailed experimental study using various schemes to cleanboth synthetic and real RFID data streams. First, thesetests show that there is no single static window size thatworks well in all environments (reader and tag behavior),motivating the need for an adaptive approach. Second, wedemonstrate SMURF’s ability to adapt its data-cleaningstrategy to a wide range of reader characteristics and tagbehaviors; in an environment with changing conditions,SMURF reduces overall error by a factor of more than 3compared to the best environment-specific static window.(Section 5)SMURF is designed to be a component in a pipeline of operators responsible for low-level RFID data processing taskssuch as cleaning, filtering, and spatial processing (see proposals such as ALE [5] and ESP [20, 21]). SMURF would beresponsible for smoothing RFID readings from each readerbefore the streams are sent to other modules for additionalprocessing. We believe that SMURF’s sampling-based foundation offers a powerful conceptual framework for effectiveRFID data-cleaning tools. The set of techniques proposed inthis paper can be directly incorporated in RFID middlewareplatforms to yield systems that (1) are substantially easierto configure and maintain; and, (2) produce more reliableRFID data, regardless of the deployment environment.In the next section, we provide a general background onRFID technology and detail RFID reader unreliability.2.RFID BACKGROUNDRFID Technology Primer. RFID is an electronic tagging and tracking technology designed to provide non-lineof-sight identification. For the purposes of this paper, a typical RFID installation consists of three components: readers,antennae, and tags.A reader uses antennae to communicate with tags using RF signals to produce lists of IDs in its detection field.Tags may either be active (battery-powered) or passive (noon-board battery). We focus on passive tags, as they arethe most widespread variety of RFID tags. Tags store aunique identifier code (e.g., a 64 or 96-bit ID for EPCGlobaltags [16]). Although there exists RFID technology for multiple frequencies, we focus on 915 MHz technology, which hasa long detection range (roughly 10-20 feet) and is typical ofsupply chain management applications.Readers interrogate nearby tags by sending out an RFsignal. Tags in the area respond to these signals with theirunique identifier code. An interrogation cycle is one iteration through the reader’s protocol that attempts to determine all tags in the reader’s vicinity.The results of multiple reader interrogation cycles are typ-
10.80.80.60.6Read RateRead Rate10.40.20.200.40510Distance (ft.)152000510Distance (ft.)1520(a) Alien reader with Alien Squiggle tag under con- (b) Sensormatic reader with Alien I2 tag under noisyconditions.trolled conditions.Figure 2: RFID reader profiles for a single tag under different conditions. Error bars represent one standarddeviation.ically grouped into what we term epochs.1 An epoch may betection region [25], giving high detection probabilities (readspecified as a number of interrogation cycles or as a unit ofrates at or above 95%); and, (2) The reader’s minor detectime. A typical epoch range is 0.2-0.25 seconds [1, 30]. Fortion region, extending from the end of the major detectioneach epoch, the reader keeps track of all the tags it has idenregion to the edge of the reader’s full detection range, wheretified, as well as additional information such as the numberthe read rate drops off linearly (with some variation) to zeroof interrogation responses for each tag and the time at whichat the end of the detection range.the tag was laet read. Readers store this information interThe main difference between our observed profiles lies innally in a tag list (Table 1) which is periodically transferredthe percentage of the reader’s detection range correspondingto readers’ clients (either synchronously or asynchronously).to its major detection region. For instance, the major detecFor more information on RFID technology, see [33].tion region corresponds to roughly 75% of the full detectionrange for the profile in Figure 2(a), whereas it makes up onlyTag IDResponses Timestamp25% of the range in the profile in Figure 2(b). Note that our8576 2387 2345 8678911:07:05profiles are consistent with the results of in-depth commer8576 4577 3467 2357111:07:05cial studies of the performance of many different tags and8576 3246 3267 5685711:07:06readers under highly-controlled conditions [14].Table 1: Example reader tag list.We also profile the readers to determine how they respondto the presence of multiple tags in their detection ranges. ForRFID Reader and Tag Performance. To better unthese tests (not shown here), we suspend 10 tags in the samederstand the unreliability of RFID readings, we profile twoplane as the reader and measure the average read rate forRFID readers with different tags in two environments. Our100 epochs at varying distances from the reader. While theprofiling methodology is as follows. We suspend a single tagoverall properties of the observed profile does not change (weat varying distances in the same plane as the antenna. Forstill find a clear separation between a major and minor deevery 6-inch increment of distance from the reader, we meatection region), the overall read rate in the major detectionsure the read rate (number of responses to interrogations)region typically drops significantly to around 80%. Addifor 100 epochs.tional tests show that the read rate in the major detectionOur profiling experiments use two types of readers, theregion stays somewhat constant, at least up to 25 tags inAlien ALR-9780 [3] and the Sensormatic Agile 2 [29], withthe reader’s detection range.three types of tags (Alien “I2”, “M”, and “Squiggle” [4]).We use these observations in the design of some ofWe test various combinations of these readers and tags inSMURF’s cleaning mechanisms and in the implementationtwo environments. Our first environment, a large, wideof a realistic RFID data generator for evaluating ouropen room with little metal present, represents a controlledtechniques.environment for RFID technology: we eliminate many ofthe causes of degraded read rates [18]. Our second profiling3. RFID DATA STREAMS: A STATISTICALenvironment, a lab with metal objects such as desks andcomputer equipment, represents a noisy environment.SAMPLING PERSPECTIVEFigure 2 depicts the results from two different profilingGiven the inherent unreliability of RFID readings, one ofexperiments that are representative of the 8 different proour key observations is that observed RFID data streamsfiles we collected. (The plots show the read rate of the tagtypically do not provide a complete, authoritative pictureat distances ranging from 0 to 20 feet.) All of the profilesof the true population of tags in the physical world. Espehave similar properties despite being generated using difcially for tags outside a reader’s major detection region, sevferent readers, tags, and environments. First, the overalleral readings may be missed, causing some tags to becomedetection range of all readers and tags profiled remains rel“invisible” during a time window. These errors, of course,atively constant at 15-20 feet. Second, within each reader’simply that typically only a subset of the tag population isdetection range, there are two distinct regions: (1) The areaactually observed. On the other hand, a lack of readingsdirectly in front of the reader, termed the reader’s major defrom a tag may not be due to missed readings but rather1In ALE terms, an epoch is a read cycle [5].because the tag moved out of the detection field. The inherent tension between completeness of readings and captur-
ing tag dynamics (i.e., signal transitions) only exacerbatesthe problem: signals with a high degree of variability (e.g.,counting highly-mobile tags) require short smoothing windows in order to capture rapid changes in the measurementdata; but, obviously, a smaller window leads to more missedreadings and more severe and systematic underestimation.The conventional solution of increasing the window size toguarantee completeness simply does not work here, as it cancause signal variations to be lost (“smoothed out”) due toaggregation.Rather than striving for completeness, our proposed adaptive smoothing filter, SMURF, captures tag dynamics whilecompensating for lost RFID readings in a principled, statistical manner. The key idea is that the observed RFIDreadings can be viewed as a random sample of the population of tags in the physical world. In the remainder of thissection, we briefly explain the details of this process and thechallenges in designing SMURF.Mapping RFID Readings to a Sampling Process:SMURF Methodology and Challenges. Consider anepoch t. Recall from Section 2 that an epoch is the atomicunit of detection and is considerably smaller than the expected window size; that is, epochs represent our basic “timeunits”, many of which make up a smoothing window [19, 23].Without loss of generality, let Nt denote the (unknown)size of the underlying tag population at epoch t, and letSt {1, . . . , Nt } denote the subset of tags observed (“sampled”) by the reader during that epoch. SMURF essentiallyviews St as an unequal probability random sample of thetag population. Specifically, for each tag i St , SMURFemploys the response-count information for tag i stored inthe reader tag list (Table 1) in conjunction with the knownnumber of interrogation cycles per epoch to derive a perepoch sampling probability pi,t . This sampling probabilitypi,t is empirically estimated as the observed read rate fortag i during that epoch; for instance, assuming a readerconfiguration with a total number of 10 interrogation cyclesper epoch, the sampling probabilities for the first and second tags in Table 1 would be px78,t 0.9 and px57,t 0.1,respectively. Of course, these sampling probabilities differacross tags and can also vary over time as the observed tagsmove within reader’s detection range.Our key insight of viewing each RFID epoch as a“sampling trial” enables SMURF’s novel, statistics-drivenperspective on adaptive RFID data cleaning. In a nutshell,SMURF views the observed readings over a smoothingwindow (i.e., a sequence of consecutive epochs) as theresult of repeated random-sampling trials, and employstechniques and estimators grounded in statistical samplingtheory to reason about the underlying physical-worldphenomena and drive its adaptive RFID data cleaningalgorithms. More specifically, SMURF uses the statisticalproperties of the observed random sample to appropriately adapt the size of its smoothing window based on(1) completeness requirements and, (2) signal transitionsdetected as “statistically-significant” changes in the underlying tag readings. Further, even for window sizesthat are necessarily small (to capture fast-varying signals),SMURF uses sampling-based estimators [12, 28] to provideaccurate, unbiased estimat
RFID technology and detail RFID reader unreliability. 2. RFID BACKGROUND RFID Technology Primer. RFID is an electronic tag-ging and tracking technology designed to provide non-line-of-sight identification. For the purposes of this paper, a typi-cal RFID installation consists of three c
RFID technology, RFID detection, RFID applications, RFID in management, RFID components. 1. Introduction . RFID, which stands for Radio Frequency Identification, is an automatic identification technology used for retrieving from or storing data on to RFID Tags without any physical contact [1]. An RFID system primarily comprises of RFID Tags .
RFID technology this year, with 8% in full deployment The average annual RFID budget is estimated at 550,000, reaching 770,000 by 2007 23% of companies polled are piloting RFID technology, while 38% plan to evaluate RFID technology in the next two years By 2015, 1.3 million people are estimated to be working in the RFID industry
Spec2000 RFID chapter usable - A350 initiative - RFID apps/tools developed - Delta implemented RFID across fleets - RFID applications sold on open market - A&D format approved by EPC - Airlines start to engage - Airbus compatibility testing lab - Delta RFID baggage deployment. Brief History of Aviation RFID. 2002. 2004. 2006 .
Bruksanvisning för bilstereo . Bruksanvisning for bilstereo . Instrukcja obsługi samochodowego odtwarzacza stereo . Operating Instructions for Car Stereo . 610-104 . SV . Bruksanvisning i original
in the RFID field on the THU screen that matches the RFID Tag put on the THU. Q: Is RFID part specific? Does each part or P/N need an RFID label? A: No. RFID is shipment specific. Labels are attached to the THU exterior packaging. Q: What is t
3.3 Radio Frequency Identification 54 3.3.1 RFID Historic Background 54 3.3.2 RFID System Overview 54 3.3.3 Principles of RFID Operation 58 3.3.4 The Electronic Product Code System 63 3.3.5 RFID and Biometrics 65 3.3.6 Challenges of RFID Implementation 67 3.4 Wireless Senso
Progress of RFID research RFID background and basics Evolving coreness of control points The future of RFID – IP Hourglass analogy 26. Outline RFID Case Study. 27. Progress of RFID Research June-September
ACCOUNTING AND REPORTING 13th Edition FINANCIAL ACCOUNTING AND REPORTING ELLIOTT AND ELLIOTT Financial Accounting & Reporting is the most up-to-date text on the market. Now fully updated in its 13th edition, it includes extensive coverage of International Accounting Standards (IASs) and International Financial Reporting Standards (IFRSs). This market-leading text offers students a clear, well .
