Efficient RFID Grouping Protocols

The grouping problem in RFID systems is to efficiently group all tags according to a given partition such that tags in the same group will have the same group ID. Unlike previous research on unicast transmission from a reader to a tag, grouping provides a fundamental mechanism for efficient multicast transmissions and aggregate queries in large RFID-enabled applications. A message can be transmitted to a group of m tags simultaneously in multicast, which improves the efficiency by m times when comparing with unicast. This paper studies this practically important but not yet thoroughly investigated grouping problem in large RFID system. We start with a straightforward solution called the Enhanced Polling Grouping (EPG) protocol. We then propose a time-efficient Filter Grouping (FIG) protocol that uses Bloom filters to remove the costly ID transmissions. We point out the limitation of the Bloom-filter based solution due to its intrinsic false positive problem, which leads to our final ConCurrent Grouping (CCG) protocol. With a drastically different design, CCG is able to outperform FIG by exploiting collisions to inform multiple tags of their group ID simultaneously and by removing any wasteful slots in its frame-based execution. We further enhance CCG to make it perform better with very large groups. Simulation results demonstrate that our best protocol CCG can reduce the execution time by a factor of 11 when comparing with a baseline polling protocol.