Novel RFID anti-collision algorithm based on the Monte-Carlo query tree search

Tag collision is a pressing issue in radio frequency identification systems which significantly lowers the system performance if not mitigated carefully. This paper presents the Monte-Carlo Query Tree Search (MCQTS) method as a novel and fast anti-collision algorithm. This method combines the capabilities of the conventional Monte-Carlo Tree Search and Query Tree by applying a few heuristics on the tree traversal to raise the chance of facing the most promising states. The collision mitigation based on the MCQTS is presented and its performance in terms of time, and space (memory) complexity is analytically verified. Simulations are performed, and the effects of tree size, number of tags, and tag ID length on the performance of the proposed method are investigated. The results are compared to the previously presented tree-based algorithms, and it is shown that for typical tag lengths, the MCQTS method performs between 3.89% and 62.06% (in average) faster than the conventional methods for multi-tag identification.

Automated summary

This paper presents a novel and fast anti-collision algorithm called Monte-Carlo Query Tree Search (MCQTS), which combines the capabilities of traditional Monte-Carlo Tree Search and Query Tree. By applying heuristics on the tree traversal, this method increases the chance of encountering the most promising states. The collision mitigation based on MCQTS is validated in terms of time and space complexity and its performance is compared to conventional methods for multi-tag identification.