Multi-Seed Group Labeling in RFID Systems

Ever-increasing research efforts have been dedicated to radio frequency identification (RFID) systems, such as finding top-k, elephant groups, and missing-tag detection. While group labeling, which is how to tell tags their associated group data, is the common prerequisite in many RFID applications, its efficiency is not well optimized due to the transmission of useless data with only one seed used. In this paper, we introduce a unified protocol called GLMS which employs multiple seeds to construct a composite indicator vector (CIV), reducing the useless transmission. Technically, to address Seed Assignment Problem (SAP) arising during building CIV, we develop an approximation algorithm (AA) with a competitive ratio 0.632 by globally searching for the seed contributing to the most useful slot. We then further design two simplified algorithms through local searching, namely cc-search-I and its enhanced version cc-search-II, reducing the complexity by one order of magnitude while achieving comparable performance. We conduct extensive simulations to demonstrate the superiority of our approaches.