A Near-Optimal Protocol for the Grouping Problem in RFID Systems

摘要

Radio frequency identification (RFID) has been widely used in many fields such as object tracking and inventory management. For RFID systems, grouping is a fundamental issue which can support efficient multicast transmissions, dynamic tag management, and accurate aggregate queries. Existing grouping protocols have drawbacks of unknown theoretical communication time, high computational cost on the server end and inability to deal with unexpected tags which are those tags whose IDs have not been collected by readers. In this paper, we would like to address the above limitations and consider a more general grouping problem that allows an arbitrary number of unexpected tags to present. Our objective is to design a protocol that guarantees the reader to efficiently and correctly notify each known tag of its group-ID, while the probability that an unexpected tag is mistakenly notified of any group-ID is smaller than a pre-determined value. In this paper, we first obtain a lower bound on the communication time for solving this generalized grouping problem. Then, we propose a near-optimal protocol, called OPT-G, and prove that its communication time approximately equals the lower bound. Finally, we report extensive simulation results that demonstrate OPT-G's near-optimal performance and its superiority over existing baseline schemes.