Research Article
Identifying RFID Tag Categories in Linear Time
@INPROCEEDINGS{10.1109/WIOPT.2009.5291639, author={Murali Kodialam and Wing Cheong Lau and Thyaga Nandagopal}, title={Identifying RFID Tag Categories in Linear Time}, proceedings={7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks}, publisher={IEEE}, proceedings_a={WIOPT}, year={2009}, month={10}, keywords={RFID Category identification probabilistic counting}, doi={10.1109/WIOPT.2009.5291639} }- Murali Kodialam
Wing Cheong Lau
Thyaga Nandagopal
Year: 2009
Identifying RFID Tag Categories in Linear Time
WIOPT
IEEE
DOI: 10.1109/WIOPT.2009.5291639
Abstract
Given a large set of RFID tags, we are interested in determining the categories of tags that are present in the shortest time possible. Since there can be more than one tag present in a particular category, pure randomized strategies that rely on resolving individual tags are very inefficient. Instead, we rely on a pseudo-random strategy that utilizes a uniform hash function to accurately identify all t categories present among a given set of ψ tags with high probability. We propose two algorithms: (a) a single frame algorithm that determines the optimal frame size, and (b) a probabilistic version where the frame size is fixed, and we select the probability to minimize the number of frames needed for identification. Both of these algorithms run in time linear to the number of categories present, t. We show that our approach significantly outperforms existing algorithms for category identification. The performance of our algorithms is within a constant factor of the lower bound.