Efficient group labeling for multi-group RFID systems

Ever-increasing research effort has been dedicated to multi-group radio frequency identification (RFID) systems where all tags are partitioned into multiple groups, such as group-level queries, and multi-group missing tag detection. However, it is assumed in the existing work that all tags know their individual group IDs, which thus leaves group labeling problem unaddressed. To tackle the under-investigated problem, this paper is devoted to devising an efficient group labeling protocol to inform each tag of its corresponding group ID fast and accurately. To this end, we employ multiple seeds to build a Composite Indicator Vector (CIV) indicating the assigned seed in each slot, which reduces transmissions of useless information and thus improves time efficiency. Specifically, we first theoretically show that the Seed Assignment Problem (SAP) arising in establishing the CIV is NP-hard and then develop a myopic approximation algorithm. Finally, the simulation results confirm the superiority of the proposed protocol over the state-of-the-art solution in terms of time efficiency.