Minimal Perfect Hashing-Based Information Collection Protocol for RFID Systems

For large-scale RFID systems, this paper studies the practically important problem of target tag information collection, which aims at collecting information from a specific set of target tags instead of all. However, the existing solutions are of low time-efficiency because of two reasons. First, the serious collisions among tags due to hashing randomness seriously reduce the frame utilization, whose upper bound is just 36.8 percent. Second, they cannot efficiently distinguish the target tags from the non-target tags and thus inevitably collect a lot of irrelevant information on non-target tags, which further deteriorates the effective utilization of the time frame. To overcome the above two drawbacks, this paper proposes the minimal Perfect hashing-based Information Collection (PIC) protocol, which first leverages lightweight indicator vectors to establish a one-to-one mapping between target tags and slots, thereby improving the frame utilization to nearly 100 percent; and then uses the novel data structure called Minimal Perfect Hashing based Filter (MPHF) to filter out the non-target tags, thereby preventing them from interfering with the process of collecting information from target tags. Sufficient theoretical analyses are also presented in this paper to minimize the execution time of the proposed PIC protocol. Extensive simulations are conducted to compare the proposed PIC protocol with prior works side-by-side. The simulation results demonstrate that PIC significantly outperforms the state-of-the-art protocols in terms of time-efficiency.