Partitioning of Tags for Near-Optimum RFID Anti-collision Performance

A novel anti-collision algorithm is proposed to maximize identification performance in slotted Aloha based radio frequency identification (RFID) systems. We observe much higher throughput can be achieved by identifying tags in a divide-and-conquer style, where the set of entire tags is partitioned into multiple subsets of roughly equal size and each subset is then identified in sequence. To quantify the throughput gain by partitioning, we introduce the notion of partitioning gain defined as an amount of throughput increased from partitioning. Our algorithm starts with initial blind partitioning and then attempts to estimate the tag population by identifying the first subset of tags. Once the estimation is obtained the remaining subsets of tags are repartitioned into an optimum number of subsets in order to maximize the partitioning gain. The proposed partitioning technique enables a faster yet accurate estimation on the number of contending tags and yields much higher throughput against previous non-partitioning approaches. Probabilistic analytical models are developed to investigate performance of our partitioning algorithm. Extensive simulations are also performed to validate the analytical results and demonstrate superiority of our algorithm. Numerical results show that throughput performance of our algorithm, let alone outperforming existing proposals, exceeds the commonly referenced theoretical limit of 1/e.