Differential estimation in dynamic RFID systems

Efficient estimation of tag population in RFID systems has many important applications. In this paper, we present a new problem called differential cardinality estimation, which tracks the population changes in a dynamic RFID system where tags are frequently moved in and out. In particular, we want to provide quick estimation on (1) the number of new tags that are moved in and (2) the number of old tags that are moved out, between any two consecutive scans of the system. We show that the traditional cardinality estimators cannot be applied here, and the tag identification protocols are too expensive if the estimation needs to be performed frequently in order to support real-time monitoring. This paper presents the first efficient solution for the problem of differential cardinality estimation. The solution is based on a novel differential estimation framework, and is named zero differential estimator. We show that this estimator can be configured to meet any pre-set accuracy requirement, with a probabilistic error bound that can be made arbitrarily small.