7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

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
Murali Kodialam1,*, Wing Cheong Lau2,*, Thyaga Nandagopal1,*
  • 1: Bell-Labs, Alcatel-Lucent, NJ, USA.
  • 2: The Chinese University of Hong Kong, Hong Kong.
*Contact email: muralik@alcatel-lucent.com, wclau@ie.cuhk.edu.hk, thyaga@alcatel-lucent.com

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.