Optimal distance-based clustering for tag anti-collision in RFID systems

Tag collisions can impose a major delay in radio frequency identification (RFID) systems. Such collisions are hard to overcome with passive tags due to their limited capabilities. In this paper, we look into the problem of minimizing the time required to read a set of passive tags. We propose a novel approach, the distance-based clustering, in which the interrogation zone of an RFID reader is divided into equal sized clusters (discs), and tags of different clusters are read separately. The novel contributions of this paper are the following. First, we provide a mathematical analysis to the problem and derive a closed-form formula relating delay to the number of tags and clusters. Second, we devise a method to efficiently find the optimal number of clusters. The proposed scheme can be augmented with any tree-based anti-collision scheme, and substantially improve its performance. Simulation results show that our approach makes significant improvements in reducing collisions and delay.