Load Balancing in Large-Scale RFID Systems

Large-scale radio frequency identifer (RFID) systems are being increasingly deployed in many applications such as supply chain automation. An RFID system consists of inexpensive, uniquely-identifiable tags that are mounted on physical objects, and readers that track these tags (and hence these physical objects) through RF communication. For many performance measures in large-scale RFID systems, the set of tags to be monitored needs to be properly balanced among all readers. In this paper we, therefore, address this load balancing problem for readers -- given a set of tags that are within range of each reader, which of these tags should each reader be responsible for such that the cost for monitoring tags across the different readers is balanced, while guaranteeing that each tag is monitored by at least one reader. In particular, we study dfferent variants of the load balancing problem. We first present centralized solutions to these variants. We show that a generalized variant of the load balancing problem is NP-hard and hence present a 2-approximation algorithm. We next present an optimal centralized solution for a specialized variant. Subsequently, we present a localized distributed algorithm that is probabilistic in nature and closely matches the performance of the centralized algorithms. Although probabilistic, our localized algorithms guarantee that each tag is continuously monitored by some reader at every instant. Finally we present detailed simulation results that illustrate the performance of the localized distributed approach, how it compares with the centralized optimal and near-optimal solutions, and how it adapts the solution with changes in tag distribution and changes in the reader topology. Our results demonstrate that our schemes achieve very good performance even in highly dynamic large-scale RFID systems.

Download this report (PDF)

Return to tech report index