Channel-Oblivious Counting Algorithms for Large-Scale RFID Systems

Scalable, low-latency and accurate RFID counting algorithms have recently been proposed as a fundamental building block to support more complex query operations in a large-scale RFID system. One distinct feature of these algorithms is that they do not require explicit identification of individual tags and therefore can eliminate the latency bottleneck caused by serialization during multiple access control. However, these algorithms all assume reliable communications between the reader and the tags. While this assumption is also adopted by many tag-identification protocols in the current RFID standards, it is practically unachievable given the current technology and low-cost requirement of RFID tags. In fact, recent empirical studies have found that the communication between an RFID reader and a set of seemingly ``in-range{''} tags are still unreliable and highly non-deterministic due to the varying channel conditions. In this paper, we discuss the design and performance analysis of a set of channel-oblivious RFID counting algorithms which can estimate the size of a tag-set of interest over unreliable wireless channels. The proposed schemes can provide accurate cardinality estimates without any prior knowledge of the channel parameters. We first propose a series of algorithms and analyze their performance under a simplified memoryless lossy channel model. We then extend them to handle the impact due to backscattering effects and correlated losses found in practical RFID systems. Our proposed designs only require simple modifications to standard RFID tags and readers and can be implemented using current technologies with minimal increase in tag/reader cost. Our designs can also be extended to other RFID counting algorithms which assumed reliable communication channels.