Counting rFld Tags efficiently and Anonymously Hao Hants,Bo Shengt,Chiu C.Tant,Qun Lit,Weizhen Maof,Sanglu Lus fCollege of William and Mary,Williamsburg,VA,USA Northeastern University,Boston,MA,USA SState Key Laboratory of Novel Software Technology,Nanjing University,China Email:fhhan,cct,liqun,wm}@cs.wm.edu,shengbo@ccs.neu.edu,sanglu@nju.edu.cn Abstract-Radio Frequency IDentification (RFID)technology Prior work in [12]and [13]considers this problem by using has attracted much attention due to its variety of applications,e.g. probabilistic estimation based on the framed-slotted ALOHA inventory control and object tracking.One important problem in model.Unfortunately,the scanning time can be considerably RFID systems is how to quickly estimate the number of distinct tags without reading each tag individually.This problem plays a long due to the large frame size required.The performance crucial role in many real-time monitoring and privacy-preserving becomes worse when the mobile tags appear dynamically so applications.In this paper,we present an efficient and anonymous that counting them at a fixed time instant is not possible.That scheme for tag population estimation.This scheme leverages the is because the tags have to be scanned independently with each position of the first reply from a group of tags in a frame.Results counting consuming a long time from mathematical analysis and extensive simulation demonstrate that our scheme outperforms other protocols proposed in the In this paper,we propose a novel scheme for the reader to previous work. quickly estimate the number of distinct tags within a required accuracy.Our scheme is based on a new distinct element I.INTRODUCTION counting method [14],without reading either the actual or Radio Frequency IDentification(RFID)technology is widely pseudo IDs.The main idea of our algorithm is to utilize used in monitoring applications such as inventory control and the position of the first reply from a group of tags in a object tracking [1]-[7].Small RFID tags,each with a unique frame to infer the number of tags.Theoretical analysis and ID,are attached to items under monitoring.An RFID reader extensive simulation show that our scheme outperforms earlier can remotely collect these IDs later for verification.Due to RFID tag estimation schemes.Moreover,our scheme tries to the large number of deployed RFID tags,collecting all tag optimize incremental counting in a mobile environment.Note IDs for verification is inefficient.Some real-time applications. that our approach has a general purpose of counting RFID tags. such as counting the number of tags in a shipping portal,need Combined with other commands,it can be flexibly adopted in more efficient techniques to manage tag data.In this paper,we various applications. consider the problem of efficiently and anonymously estimating Our contributions are summarized as follows the cardinality of a large set of RFID tags with a desired We propose a novel anonymous estimating scheme which accuracy. does not collect the ID from each RFID tag,but is still Efficient techniques for estimating the number of RFID able to estimate the number of tags accurately. tags are important for applications when the time window for We present estimators for both static and dynamic sets of collecting tag data is small.These applications include real- tags.The static set specifies a snapshot of a set of tags, time monitoring or managing a large quantity of products and the dynamic set considers that tags can join or leave For example,a warehouse operator may need to perform a the set with time.Both our estimators are more efficient quick estimation of the number of products left in stock.Such than the existing protocols,even when the cardinality of applications demand efficient estimating schemes instead of the the tag set varies across many orders of magnitude. slow and unnecessary process of reading every tag ID. We propose a novel send-and-reply protocol among the Anonymity is another important issue when dealing with reader and tags to improve performance RFID tags attached to uniquely identifiable items such as The rest of our paper is as follows.Section II contains passports [8]or driver's licenses [9].Either broadcasting tag the related work.Section III presents our problem definition IDs in the open,or revealing IDs to the RFID reader may leak and system model.Section IV outlines the main idea of our personal information.For instance,an adversary could capture schemes.Section V details the algorithms.Our schemes are the communication between the reader and tags or compromise evaluated in Section VI,and Section VII concludes. the reader to track users'activities.Identifying each tag ID increases individual security and privacy risks.An alternative II.RELATED WORK way of providing anonymity is to use cryptographic protocols For a reader to successfully identify every tag in proxim- to mask the actual ID [10],[11].However,the cryptographic ity,collision arbitration protocols must be considered so that techniques require additional modification to the tag hardware, replies from multiple tags will not be garbled due to collision. as well as increase the computational complexity on both tags Collision arbitration protocols are divided into two approaches: and readers. ALOHA-based [15]-[17]and tree-based [18]-[20].In the firstCounting RFID Tags Efficiently and Anonymously Hao Han†§, Bo Sheng‡ , Chiu C. Tan† , Qun Li† , Weizhen Mao† , Sanglu Lu§ †College of William and Mary, Williamsburg, VA, USA ‡Northeastern University, Boston, MA, USA §State Key Laboratory of Novel Software Technology, Nanjing University, China Email: †{hhan, cct, liqun, wm}@cs.wm.edu, ‡ shengbo@ccs.neu.edu, § sanglu@nju.edu.cn Abstract—Radio Frequency IDentification (RFID) technology has attracted much attention due to its variety of applications, e.g., inventory control and object tracking. One important problem in RFID systems is how to quickly estimate the number of distinct tags without reading each tag individually. This problem plays a crucial role in many real-time monitoring and privacy-preserving applications. In this paper, we present an efficient and anonymous scheme for tag population estimation. This scheme leverages the position of the first reply from a group of tags in a frame. Results from mathematical analysis and extensive simulation demonstrate that our scheme outperforms other protocols proposed in the previous work. I. INTRODUCTION Radio Frequency IDentification (RFID) technology is widely used in monitoring applications such as inventory control and object tracking [1]–[7]. Small RFID tags, each with a unique ID, are attached to items under monitoring. An RFID reader can remotely collect these IDs later for verification. Due to the large number of deployed RFID tags, collecting all tag IDs for verification is inefficient. Some real-time applications, such as counting the number of tags in a shipping portal, need more efficient techniques to manage tag data. In this paper, we consider the problem of efficiently and anonymously estimating the cardinality of a large set of RFID tags with a desired accuracy. Efficient techniques for estimating the number of RFID tags are important for applications when the time window for collecting tag data is small. These applications include real￾time monitoring or managing a large quantity of products. For example, a warehouse operator may need to perform a quick estimation of the number of products left in stock. Such applications demand efficient estimating schemes instead of the slow and unnecessary process of reading every tag ID. Anonymity is another important issue when dealing with RFID tags attached to uniquely identifiable items such as passports [8] or driver’s licenses [9]. Either broadcasting tag IDs in the open, or revealing IDs to the RFID reader may leak personal information. For instance, an adversary could capture the communication between the reader and tags or compromise the reader to track users’ activities. Identifying each tag ID increases individual security and privacy risks. An alternative way of providing anonymity is to use cryptographic protocols to mask the actual ID [10], [11]. However, the cryptographic techniques require additional modification to the tag hardware, as well as increase the computational complexity on both tags and readers. Prior work in [12] and [13] considers this problem by using probabilistic estimation based on the framed-slotted ALOHA model. Unfortunately, the scanning time can be considerably long due to the large frame size required. The performance becomes worse when the mobile tags appear dynamically so that counting them at a fixed time instant is not possible. That is because the tags have to be scanned independently with each counting consuming a long time. In this paper, we propose a novel scheme for the reader to quickly estimate the number of distinct tags within a required accuracy. Our scheme is based on a new distinct element counting method [14], without reading either the actual or pseudo IDs. The main idea of our algorithm is to utilize the position of the first reply from a group of tags in a frame to infer the number of tags. Theoretical analysis and extensive simulation show that our scheme outperforms earlier RFID tag estimation schemes. Moreover, our scheme tries to optimize incremental counting in a mobile environment. Note that our approach has a general purpose of counting RFID tags. Combined with other commands, it can be flexibly adopted in various applications. Our contributions are summarized as follows. • We propose a novel anonymous estimating scheme which does not collect the ID from each RFID tag, but is still able to estimate the number of tags accurately. • We present estimators for both static and dynamic sets of tags. The static set specifies a snapshot of a set of tags, and the dynamic set considers that tags can join or leave the set with time. Both our estimators are more efficient than the existing protocols, even when the cardinality of the tag set varies across many orders of magnitude. • We propose a novel send-and-reply protocol among the reader and tags to improve performance. The rest of our paper is as follows. Section II contains the related work. Section III presents our problem definition and system model. Section IV outlines the main idea of our schemes. Section V details the algorithms. Our schemes are evaluated in Section VI, and Section VII concludes. II. RELATED WORK For a reader to successfully identify every tag in proxim￾ity, collision arbitration protocols must be considered so that replies from multiple tags will not be garbled due to collision. Collision arbitration protocols are divided into two approaches: ALOHA-based [15]–[17] and tree-based [18]–[20]. In the first