Research On Techniques For Large-scale RFID Tag Identification, Detection And Estimation

As the fourth industrial revolution begins, people are becoming more and more aware of how necessary it is to integrate the emerging IT technology into traditional industry. And R-FID technology will replace the traditional bar-code technology as one of the most important auto-identification techniques in the future smart production. However, during the process of promoting RFID technology, we are still facing many key problems and technical challenges that solicit effective solutions. This thesis mainly pays attention to three crucial challenges in large-scale RFID systems, including serious signal collisions, privacy security, and power limi-tation of active tags. Based on the existing methods and previous work, this thesis studies three types of important tag information collection problems, which are abnormal tag identification, abnormal tag detection, and tag cardinality estimation. The detailed research content and novelty are summarized as follows.Tag identification is one of the problems that attracted attention from both academic and industrial in the infancy stage of RFID research, however, the problem of identifying a small number of abnormal tags from a large number of normal tags is still not addressed well, and the performance of the existing solutions still has a large room to be improved. Hence, in the first research content of this thesis, the author focuses on abnormal tag identification, and stud-ies two sub-problems of missing tag identification and unknown tag identification, respectively. For missing tag identification, we find that the low frame utilization incurs the performance bot-tleneck of the existing related protocols. Hence, this thesis proposes the multi-hashing based missing tag identification protocol, in which the reader sends lightweight bitmaps in an iterative manner to guide the tags to perform multiple hashing processes, thereby improving the ratio of singleton slots in the time frame. Although multi-hash approach could improve the frame utilization, it is not cost-free, excessive hashing may deteriorate the overall time-efficiency in-stead. Hence, this thesis proposes a plenty of theoretical analysis to investigate the impact of hashing times on the protocol performance to find the best trade-off point between hashing cost and frame utilization. Simulation results demonstrate that the multi-hashing based missing tag identification protocol proposed in this thesis significantly reduces the time cost than the state-of-the-art protocol. For unknown tag identification, this thesis finds that all the existing protocols separately consider the unknown tag labeling phase and unknown tag identification phase. The information obtained from the labeling phase is not fully utilized, which leaves the huge improvement space in terms of time-efficiency. To this end, this thesis proposes a new data structure called XOR Bloom Filter, which could not only label the unknown tags, but also significantly reduce the tag collisions during the process of collecting unknown tag IDs. The simulation results reveal that the proposed XOR Bloom Filter-based unknown tag identification protocol could guarantee the predefined accuracy, and improve the time-efficiency.In the first research content, this thesis studies the problem of abnormal tag identification, i.e., exactly identifying the IDs of abnormal tags. In practice, blindly executing heavy identi-fication protocol may waste much time and energy but fails to identify any abnormal tag IDs. A proper solution is to first execute a lightweight abnormal tag detection protocol to decide whether this system contains abnormal tags. Only when finding the existence of abnormal tags, the heavy abnormal tag identification protocol will be invoked. Hence, the lightweight abnormal tag detection is also of great importance, which is the second research content of this thesis. In terms of abnormal tag detection, this thesis mainly studies the problem of unknown tag detec-tion. The existing protocols use the traditional bloom filter data structure to detect the existence of unknown tags. To ensure the detection false positive is below a given threshold, the size of the bloom filter should be proportional to the number of tags, which results in the bad scalability in large-scale RFID systems. This thesis combines the sampling idea and traditional bloom filter to propose the sampling bloom filter, based on which we propose a highly accurate detection protocol that simultaneously takes time-efficiency and energy-efficiency into consideration. The simulation results demonstrate that, given the same detection accuracy constraints, the sampling bloom filter-based unknown tag detection protocol outperforms the existing protocols in terms of both time-efficiency and energy-efficiency.In the application scenario of inventory management, the manager only needs to know the number of remaining tags to determine the stock replenishment. For this purpose, there is no need to exactly identify the tag IDs, and we only need to know the approximate number of tags. In terms of tag cardinality estimation, this thesis studies the problem of RFID estimation with the presence of blocker tag and the problem of Top-k query in multi-category RFID systems, respectively. For the RFID estimation with presence of blocker tag, this thesis takes the first step to formally define the problem. And extensive simulation results reveal that none of the exist-ing estimation protocols could eliminate the interferences from blocker tag when estimating the cardinality of genuine tags. Therefore, all the existing RFID estimation protocols fail to return correct estimation results. This thesis exploits the status changes of slots, and uses the statisti-cal methodology to propose the accuracy-ensured genuine tag cardinality estimation protocol. A plenty of analysis is proposed to guarantee the predefined estimation accuracy. Simulation results demonstrate that the proposed protocol is even faster than the fastest tag identification protocol. For the Top-k query in multi-category RFID systems, this thesis first proposes the basic query protocol, in which the tags in the same category always respond to the reader with a random single-one geometric string in the same slot. The reader exploits the combined signal obtained from homogeneous slot to estimate the size of the corresponding category, and dynam-ically eliminate the small tag categories that are definitely out of the top-k set. This thesis also proposes extensive theoretical analysis to guarantee the query accuracy. Then, this thesis pro-poses a supplementary protocol called segmented perfect hashing to establish bijective mapping between the tag categories and slots, in order to improve the frame utilization. This thesis also investigates the impact of hashing segment size on the communication cost and computation cost to find the best trade-off point between them. The simulation results demonstrate that the proposed Top-k query protocol has better query speed than the existing protocol.