Optimizing RFID tag-inventorying algorithms

Maximizing the rate at which Radio Frequency IDentification (RFID) tags can be read is a critical issue for end-users of RFID technology as well as for RFID hardware manufacturers. Supply chain applications typically involve tags for which the reader-tag communication is regulated by a protocol that enforces a slotted Aloha scheme. This article shows how to dynamically adjust the parameter of this scheme as a function of the number of tags remaining and the last-used value of the parameter, such that the total amount of time required to read a given set of tags is minimized. To do so, several variations of this stochastic shortest path problem are formulated as Markov decision processes, which are then solved for the optimal policies by exploiting the models' decomposability. Computational results indicate that the optimal policies are complex and static heuristics perform poorly but that a myopic heuristic performs nearly optimally under the current cost structure when the reader processes all slots before selecting a new parameter value.