Minimal Perfect Hashing-Based Information Collection Protocol for RFID Systems

Xin Xie, Xiulong Liu, Keqiu Li, Bin Xiao, Heng Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)


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.
Original languageEnglish
Article number7870596
Pages (from-to)2792-2805
Number of pages14
JournalIEEE Transactions on Mobile Computing
Issue number10
Publication statusPublished - 1 Oct 2017


  • perfect hashing
  • TDMA protocol
  • time-efficiency

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Minimal Perfect Hashing-Based Information Collection Protocol for RFID Systems'. Together they form a unique fingerprint.

Cite this