Energy Efficient Algorithms for the RFID Estimation Problem Tao Lif Samuel Wuts Shigang Chent Mark Yang§ Department of Computer Information Science Engineering Department of Epidemiology and Health Policy Research SDepartment of Statistics University of Florida,Gainesville,FL 32611,USA Abstract-RFID has been gaining popularity for inventory methods that estimate the number of tags with an accuracy control,object tracking,and supply chain management in ware- that can be arbitrarily set.This is called the RFID estimation houses,retail stores,hospitals,etc.Periodically and automatically problem.The follow-up work by Qian et al.[5]significantly estimating the number of RFID tags deployed in a large area has many important applications in inventory management and reduces the estimation time.It can be shown that even for theft detection.The prior work focuses on designing time-efficient the applications that require reading the actual IDs of all tags, algorithms that can estimate tens of thousands of tags in seconds. estimating the number of tags as a pre-processing step will We observe that,for a RFID reader to access tags in a large help make the main procedure of reading the IDs much more area,active tags are likely to be used.These tags are battery- efficient [3].Another advantage of estimating the number of powered and use their own energy for information transmission. However,recharging batteries for tens of thousands of tags is tags without reading the IDs is that it ensures the anonymity laborious.Unlike the prior work,this paper studies the RFID of the tags,which may be useful in privacy-sensitive scenarios estimation problem from the energy angle.Our goal is to reduce involving RFID-enhanced passports or driver's licences,where the amount of energy that is consumed by the tags during counting the number of people present is needed but revealing the estimation procedure.We design several energy-efficient their identities is not necessary. probabilistic algorithms that iteratively refine a control parameter to optimize the information carried in the transmissions from the Is time efficiency the only performance metric for the RFID tags,such that both the number and the size of the transmissions estimation problem?We argue that energy cost is also an are minimized. important issue that must be carefully dealt with.In any application that requires a RFID reader to access tags in a large I.INTRODUCTION area,it is likely that battery-powered active tags will be used. The radio-frequency identification (RFID)technology has Passive tags harvest energy from the radio signal of the reader been widely used in various commercial applications,including and use such minute amount of energy to deliver information inventory control,object tracking,and supply chain manage- back to the reader.Their typical reading range is only several ment.RFID tags (each storing a unique ID)are attached meters,which do not fit well with the big warehouse scenario. to goods at warehouses,merchandizes at retail stores,or Active tags use their own power to transmit.A longer reading equipment at hospitals,allowing an authenticated RFID reader range can be achieved by transmitting at higher power.They are to quickly access the properties of each individual item or also richer in resources for implementing advanced functions. collect the statistical information about a large group of items. Their price becomes less of a concern if they are used for This paper focuses on a RFID-enabled function that is very expensive merchandizes (such as refrigerators)or reused many useful in inventory management.Imagine a large warehouse times as goods moving in and out of the warehouse.But storing thousands of refrigerators,tens of thousands of furni- active tags also have a problem.They are powered by batteries. ture pieces,or hundreds of thousands of footwear.A national Recharging batteries for tens of thousands of tags is a laborious retail survey showed that administration error,vendor fraud operation,considering that the tagged products may stack up, and employee theft caused about 20 billion dollars lost a year making tags not easily accessible.To prolong the tags'lifetime [1].Hence,it is desirable to have a quick way of counting the and reduce the frequency of battery recharge,all functions that number of items in the warehouse or in each section of the involve large-scale transmission by many tags should be made warehouse.To timely detect theft or management errors,such energy-efficient.The prior work focuses on energy-efficient counting may be performed frequently. anti-collision protocols that minimize the energy consumption If each item is attached with a RFID tag,the counting of a mobile reader [6],[7]when the reader collects the IDs of problem can be solved by a RFID reader that receives the the tags.We believe this paper is the first to study energy- IDs transmitted (or backscattered)from the tags [2].However. efficient solutions for the RFID estimation problem (which reading the actual IDs of the tags can be time-consuming does not require reading the IDs of all tags). because so many of them have to be delivered in the same The paper has three major contributions.First,we observe low-rate channel and collisions caused by simultaneous trans- that there exists an asymmetry in energy cost.Solving the RFID missions by different tags make the matter worse.To address estimation problem incurs energy cost both at the RFID reader this problem,Kodialam and Nandagopal [3],[4]showed that and at the active tags.The asymmetry is that the energy cost the reading time can be greatly reduced through probabilistic at the tags should be minimized while the energy cost at theEnergy Efficient Algorithms for the RFID Estimation Problem Tao Li† Samuel Wu‡§ Shigang Chen† Mark Yang§ †Department of Computer & Information Science & Engineering ‡Department of Epidemiology and Health Policy Research §Department of Statistics University of Florida, Gainesville, FL 32611, USA Abstract—RFID has been gaining popularity for inventory control, object tracking, and supply chain management in ware￾houses, retail stores, hospitals, etc. Periodically and automatically estimating the number of RFID tags deployed in a large area has many important applications in inventory management and theft detection. The prior work focuses on designing time-efficient algorithms that can estimate tens of thousands of tags in seconds. We observe that, for a RFID reader to access tags in a large area, active tags are likely to be used. These tags are battery￾powered and use their own energy for information transmission. However, recharging batteries for tens of thousands of tags is laborious. Unlike the prior work, this paper studies the RFID estimation problem from the energy angle. Our goal is to reduce the amount of energy that is consumed by the tags during the estimation procedure. We design several energy-efficient probabilistic algorithms that iteratively refine a control parameter to optimize the information carried in the transmissions from the tags, such that both the number and the size of the transmissions are minimized. I. INTRODUCTION The radio-frequency identification (RFID) technology has been widely used in various commercial applications, including inventory control, object tracking, and supply chain manage￾ment. RFID tags (each storing a unique ID) are attached to goods at warehouses, merchandizes at retail stores, or equipment at hospitals, allowing an authenticated RFID reader to quickly access the properties of each individual item or collect the statistical information about a large group of items. This paper focuses on a RFID-enabled function that is very useful in inventory management. Imagine a large warehouse storing thousands of refrigerators, tens of thousands of furni￾ture pieces, or hundreds of thousands of footwear. A national retail survey showed that administration error, vendor fraud and employee theft caused about 20 billion dollars lost a year [1]. Hence, it is desirable to have a quick way of counting the number of items in the warehouse or in each section of the warehouse. To timely detect theft or management errors, such counting may be performed frequently. If each item is attached with a RFID tag, the counting problem can be solved by a RFID reader that receives the IDs transmitted (or backscattered) from the tags [2]. However, reading the actual IDs of the tags can be time-consuming because so many of them have to be delivered in the same low-rate channel and collisions caused by simultaneous trans￾missions by different tags make the matter worse. To address this problem, Kodialam and Nandagopal [3], [4] showed that the reading time can be greatly reduced through probabilistic methods that estimate the number of tags with an accuracy that can be arbitrarily set. This is called the RFID estimation problem. The follow-up work by Qian et al. [5] significantly reduces the estimation time. It can be shown that even for the applications that require reading the actual IDs of all tags, estimating the number of tags as a pre-processing step will help make the main procedure of reading the IDs much more efficient [3]. Another advantage of estimating the number of tags without reading the IDs is that it ensures the anonymity of the tags, which may be useful in privacy-sensitive scenarios involving RFID-enhanced passports or driver’s licences, where counting the number of people present is needed but revealing their identities is not necessary. Is time efficiency the only performance metric for the RFID estimation problem? We argue that energy cost is also an important issue that must be carefully dealt with. In any application that requires a RFID reader to access tags in a large area, it is likely that battery-powered active tags will be used. Passive tags harvest energy from the radio signal of the reader and use such minute amount of energy to deliver information back to the reader. Their typical reading range is only several meters, which do not fit well with the big warehouse scenario. Active tags use their own power to transmit. A longer reading range can be achieved by transmitting at higher power. They are also richer in resources for implementing advanced functions. Their price becomes less of a concern if they are used for expensive merchandizes (such as refrigerators) or reused many times as goods moving in and out of the warehouse. But active tags also have a problem. They are powered by batteries. Recharging batteries for tens of thousands of tags is a laborious operation, considering that the tagged products may stack up, making tags not easily accessible. To prolong the tags’ lifetime and reduce the frequency of battery recharge, all functions that involve large-scale transmission by many tags should be made energy-efficient. The prior work focuses on energy-efficient anti-collision protocols that minimize the energy consumption of a mobile reader [6], [7] when the reader collects the IDs of the tags. We believe this paper is the first to study energy￾efficient solutions for the RFID estimation problem (which does not require reading the IDs of all tags). The paper has three major contributions. First, we observe that there exists an asymmetry in energy cost. Solving the RFID estimation problem incurs energy cost both at the RFID reader and at the active tags. The asymmetry is that the energy cost at the tags should be minimized while the energy cost at the