Decentralized RFID coverage algorithms using writeable tags

A Radio Frequency IDentification (RFID) reader network is as a collaboration of RFID readers that aim to cover (i.e., identify, monitor, and track) every RFID tag in a given area. The RFID coverage (RFC) problem is defined as follows. Given a reader network, assign to each tag t a specific reader v in its proximity such that v is responsible for covering t (called its owner), while minimizing the number of owner readers. The problem has applications in energy conservation and in eliminating readers and data redundancy from the reader networks. We introduce a number of decentralized algorithms for the RFID coverage problem: 1) algorithms RANDOM, RANDOM+, and MAX-MIN which are randomized algorithms that run in O(1) write/read rounds, 2) algorithm GDE which is an efficient decentralized implementation of the greedy set cover algorithm, and 3) an improvement of GDE which is called . Our algorithms assume that the RFID tags are writeable, where a writeable tag is a passive RFID tag with writeable memory. We show using simulation experiments that our algorithms outperform major RFID coverage algorithms in various scenarios with respect to a number of performance metrics.