Fast and Scalable Counterfeits Estimation for Large-Scale RFID Systems
Authors:
- 16 March 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 24 (2) , 1052-1064
Abstract
Many algorithms have been introduced to deterministically authenticate Radio Frequency Identification (RFID) tags, while little work has been done to address scalability issue in batch authentications. Deterministic approaches verify tags one by one, and the communication overhead and time cost grow linearly with increasing size of tags. We design a fast and scalable counterfeits estimation scheme, INformative Counting (INC), which achieves sublinear authentication time and communication cost in batch verifications. The key novelty of INC builds on an FM-Sketch variant authentication synopsis that can capture key counting information using only sublinear space. With the help of this well-designed data structure, INC is able to provide authentication results with accurate estimates of the number of counterfeiting tags and genuine tags, while previous batch authentication methods merely provide 0/1 results indicating the existence of counterfeits. We conduct detailed theoretical analysis and extensive experiments to examine this design and the results show that INC significantly outperforms previous work in terms of effectiveness and efficiency.Keywords
Funding Information
- Natural Sciences and Engineering Research Council of Canada (CRDPJ-445199-12)
- NSFC Young Scholar (61303196)
This publication has 25 references indexed in Scilit:
- Fast identification of mobile RFID tags2012
- Interference cancellation-based RFID tags identification2011
- Fast identification of the missing tags in a large RFID system2011
- Anticollision Protocols for Single-Reader RFID Systems: Temporal Analysis and OptimizationIEEE Transactions on Mobile Computing, 2010
- Efficient Continuous Scanning in RFID Systems2010
- Design and Implementation of PUF-Based "Unclonable" RFID ICs for Anti-Counterfeiting and Security Applications2008
- Handbook of Means and Their Inequalities2003
- Probabilistic counting algorithms for data base applicationsJournal of Computer and System Sciences, 1985
- Tree algorithms for packet broadcast channelsIEEE Transactions on Information Theory, 1979
- ALOHA packet system with and without slots and captureACM SIGCOMM Computer Communication Review, 1975