Localized algorithms for redundant readers elimination in RFID networks

摘要

Redundant readers elimination is one of the fundamental optimization research problems in RFID networks. The problem is NP-hard and can be solved approximately using best known centralised set cover algorithms. However, either distributed or localised solutions for this problem are much more realistic and useful in practice. Different distributed and a few local algorithms are known in the literature. We propose a set of cellular automaton based algorithms for the redundant readers elimination optimization problem that are strictly local. We compare the performance of our algorithms in terms of eliminating redundant readers, tag read/write operation with other local algorithms and establish that our algorithms give much better results. We also compare our algorithms with the best known centralised approximation algorithms and find very competitive results even though our algorithms are localised.