The reader collision problem

Abstract

We introduce the reader collision problem, the problem of allocating frequencies over time to radio frequency identification (RFID) tag readers such that their interference with one another is minimized. RFID systems are comprised of readers and tags. Readers communicate with tags using radio frequency (RF) signaling to obtain the identifier and other data stored on the tag. A reader may interfere with the operation of other readers in the RFID system. The two principal types of reader-to-reader interference are frequency interference, two or more readers communicating on the same frequency at the same time, and tag interference, two or more readers attempting to communicate with a particular RFID tag at the same time. All reader interference caused by the operation of an RFID reader is referred to as a reader collision. Reader collisions prevent the colliding readers from communicating with all of the tags in their respective reading zones; therefore, collisions must be avoided to ensure proper and timely communication with all tags. We define the reader collision problem and present several graph coloring formulations for variants of the problem.