Counting and Identifying Problems Involving RFID Tags

March 2, 2009
Mudd 535
Hosted by: Prof. Gil Zussman
Speaker: Thyaga Nandagopal, Bell labs


Given a large set of RFID tags, we are interested in counting the number of tags that are present, and optionally, identifying them in the shortest time possible. One could use a deterministic approach, or use a randomized strategy to go about these problems. However, these tags are very simple and do not have even many basic computing capabilities. Deterministic approaches take a long time to compute an answer, while pure random strategies might work, but may not be very accurate.

In this talk, I present a pseudo-random strategy that utilizes a uniform hash function to accurately count and identify all tags present with high probability. These algorithms run in time linear to the number of tags present, t. Our approach significantly outperforms existing algorithms in this space. The method that we use for counting tags also preserves the privacy of the tags, which is a significant factor in ensuring the widespread adoption of RFID tags.


Thyaga Nandagopal is a Member of Technical Staff in the Networking Research Lab at Bell Labs, Alcatel-Lucent, based in Murray Hill, NJ. He received his Ph.D. in Electrical Engg from the University of Illinois at Urbana-Champaign in 2002. and has dual M.S. degrees in Electrical Engg and Mathematics from the University of Illinois. His research interests include scheduling, optimization, routing and network architectures for both wired and wireless networks.

500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University