2013 Proceedings IEEE INFOCOM An Efficient Protocol for RFID Multigroup Threshold-based Classification Wen Luo Yan Oiao Shigang Chen Department of Computer Information Science Engineering,University of Florida Abstract-RFID technology has many applications such as different countries or manufacturers in a port.One challenge object tracking,automatic inventory control,and supply chain is to determine whether the number of tags in each group is management.They can be used to identify individual objects or above or below a prescribed threshold value.The threshold count the population of each type of objects in a deployment area,no matter whether the objects are passports,retail may be set high to identify the populous groups,it may be products,books or even humans.Most existing work adopts a set to a level that triggers certain actions such as replenishing "flat"RFID system model and performs functions of collecting the stocks,or even multiple thresholds can be used to classify tag IDs,estimating the number of tags,or detecting the groups based on the range of their population sizes.Solving missing tags.However,in practice,tags are often attached to this multigroup threshold-based classification problem gives objects of different groups,which may represent a different product type in a warehouse,a different book category in a us a basic tool to access a large population of numerous library,etc.An interesting problem,called multigroup threshold- groups. based classification,is to determine whether the number of Precise classification requires us to know the precise objects in each group is above or below a prescribed threshold number of tags in each group.Tag identification protocols value.Solving this problem is important for inventory tracking [4,[5,[6],[7],[8],[9],[10l,[11]can do that,,but it takes applications.If the number of groups is very large,it will be inefficient to measure the groups one at a time.The best them significant time to complete if the number of tags is very existing solution for multigroup threshold-based classification large.One way to improve efficiency is relaxing the problem is based on generic group testing,whose design is however from accurate classification to approximate classification [2]. geared towards detecting a small number of populous groups where the classification accuracy can be tuned to meet a Its performance degrades quickly when the number of groups above the threshold become large.In this paper,we propose a pre-defined requirement.We may use cardinality estimation new classification protocol based on logical bitmaps.It achieves protocols [4].[5].[12],[13].[14]to estimate the number high efficiency by measuring all groups in a mixed fashion. of tags in each group,and classify the group based on In the meantime,we show that the new method is able to the estimation.However,those protocols are efficient when perform threshold-based classification with an accuracy that estimating a small number of large groups,but they are not can be pre-set to any desirable level,allowing tradeoff between time efficiency and accuracy. efficient when estimating a large number of small groups, because their execution time for each group is largely I.INTRODUCTION indifferent in group size,as we will demonstrate shortly. In [2],Sheng et al.apply group testing to approximately Radio-frequency identification(RFID)has rich application detect popular groups.When the number of groups above in cyber-physical systems for object tracking,automatic the threshold is small,their performance is good.However, inventory control,and supply chain management [1].[2].the performance of the group-testing-based solution degrades [3].Practical RFID systems widely exist for automatic toll quickly (in terms of the execution time)when the number of payment,access control to parking garages,object tracking, groups above threshold becomes large. theft prevention,tracking and monitoring.An RFID system In this paper,we propose a new classification protocol typically consists of three components:readers,tags and the that is scalable to a large number of groups.Its design is middleware software.Small RFID tags,each with a unique drastically different from traditional approaches that measure ID,are attached to objects,allowing an RFID reader to the size of one group at a time.It measures the sizes of quickly access the properties of each individual object or all groups together at once in a mixed fashion.Yet,the collect statistical information about a large group of objects.new protocol is able to perform threshold-based classification Much of the existing work on RFID systems is to design with an accuracy that can be pre-set to any desirable level, tag identification protocols that read the IDs from tags [4].allowing tradeoff between time efficiency and accuracy.Our [5],[6],[7],[8],[9],[10],[11].Other work designs efficient main contributions are summarized as follows: protocols to estimate the number of tags in a large RFID 1.We design an iterative protocol for threshold-based system [4],[5],[12],[13],[14],detects missing tags [15],classification in a multi-group RFID system based on logical [16],[17],or collects useful information [18]. bitmaps that share time slots uniformly at random among all This paper investigates a different problem.In practice, groups during the process of measuring their populations. tags are often attached to objects belonging to different We use the maximum likelihood estimation method to groups,for instance,different brands of shoes in a large shoe extract per-group information from the shared slots.Such store,different titles of books in a bookstore,and goods from slot sharing greatly reduces the amount of time it takes to 978-1-4673-5946-7/13/$31.00©20131EEE 890An Efficient Protocol for RFID Multigroup Threshold-based Classification Wen Luo Yan Qiao Shigang Chen Department of Computer & Information Science & Engineering, University of Florida Abstract—RFID technology has many applications such as object tracking, automatic inventory control, and supply chain management. They can be used to identify individual objects or count the population of each type of objects in a deployment area, no matter whether the objects are passports, retail products, books or even humans. Most existing work adopts a “flat” RFID system model and performs functions of collecting tag IDs, estimating the number of tags, or detecting the missing tags. However, in practice, tags are often attached to objects of different groups, which may represent a different product type in a warehouse, a different book category in a library, etc. An interesting problem, called multigroup threshold￾based classification, is to determine whether the number of objects in each group is above or below a prescribed threshold value. Solving this problem is important for inventory tracking applications. If the number of groups is very large, it will be inefficient to measure the groups one at a time. The best existing solution for multigroup threshold-based classification is based on generic group testing, whose design is however geared towards detecting a small number of populous groups. Its performance degrades quickly when the number of groups above the threshold become large. In this paper, we propose a new classification protocol based on logical bitmaps. It achieves high efficiency by measuring all groups in a mixed fashion. In the meantime, we show that the new method is able to perform threshold-based classification with an accuracy that can be pre-set to any desirable level, allowing tradeoff between time efficiency and accuracy. I. INTRODUCTION Radio-frequency identification (RFID) has rich application in cyber-physical systems for object tracking, automatic inventory control, and supply chain management [1], [2], [3]. Practical RFID systems widely exist for automatic toll payment, access control to parking garages, object tracking, theft prevention, tracking and monitoring. An RFID system typically consists of three components: readers, tags and the middleware software. Small RFID tags, each with a unique ID, are attached to objects, allowing an RFID reader to quickly access the properties of each individual object or collect statistical information about a large group of objects. Much of the existing work on RFID systems is to design tag identification protocols that read the IDs from tags [4], [5], [6], [7], [8], [9], [10], [11]. Other work designs efficient protocols to estimate the number of tags in a large RFID system [4], [5], [12], [13], [14], detects missing tags [15], [16], [17], or collects useful information [18]. This paper investigates a different problem. In practice, tags are often attached to objects belonging to different groups, for instance, different brands of shoes in a large shoe store, different titles of books in a bookstore, and goods from different countries or manufacturers in a port. One challenge is to determine whether the number of tags in each group is above or below a prescribed threshold value. The threshold may be set high to identify the populous groups, it may be set to a level that triggers certain actions such as replenishing the stocks, or even multiple thresholds can be used to classify groups based on the range of their population sizes. Solving this multigroup threshold-based classification problem gives us a basic tool to access a large population of numerous groups. Precise classification requires us to know the precise number of tags in each group. Tag identification protocols [4], [5], [6], [7], [8], [9], [10], [11] can do that, but it takes them significant time to complete if the number of tags is very large. One way to improve efficiency is relaxing the problem from accurate classification to approximate classification [2], where the classification accuracy can be tuned to meet a pre-defined requirement. We may use cardinality estimation protocols [4], [5], [12], [13], [14] to estimate the number of tags in each group, and classify the group based on the estimation. However, those protocols are efficient when estimating a small number of large groups, but they are not efficient when estimating a large number of small groups, because their execution time for each group is largely indifferent in group size, as we will demonstrate shortly. In [2], Sheng et al. apply group testing to approximately detect popular groups. When the number of groups above the threshold is small, their performance is good. However, the performance of the group-testing-based solution degrades quickly (in terms of the execution time) when the number of groups above threshold becomes large. In this paper, we propose a new classification protocol that is scalable to a large number of groups. Its design is drastically different from traditional approaches that measure the size of one group at a time. It measures the sizes of all groups together at once in a mixed fashion. Yet, the new protocol is able to perform threshold-based classification with an accuracy that can be pre-set to any desirable level, allowing tradeoff between time efficiency and accuracy. Our main contributions are summarized as follows: 1. We design an iterative protocol for threshold-based classification in a multi-group RFID system based on logical bitmaps that share time slots uniformly at random among all groups during the process of measuring their populations. We use the maximum likelihood estimation method to extract per-group information from the shared slots. Such slot sharing greatly reduces the amount of time it takes to 978-1-4673-5946-7/13/$31.00 ©2013 IEEE 2013 Proceedings IEEE INFOCOM 890