Distributed algorithms for the RFID coverage problem
Distributed algorithms for the RFID coverage problem
复制标题
DOI：
10.1109/icc.2013.6654773
复制
发表时间：
2013-06
期刊：
影响因子：
--
通讯作者：
Ahmed Jeddah;M. Khair;H. Mouftah
中科院分区：
文献类型：
--
作者：
Ahmed Jeddah;M. Khair;H. Mouftah
我们介绍了用于解决RFID覆盖问题的分布式算法，该问题被定义为寻找覆盖每个标签的最小数量的RFID读取器。算法依赖于标签存储器的读写轮次。第一种算法称为贪婪分布消去法(GDE)，它的灵感来自于集合覆盖问题的贪婪近似算法，并与之等价。我们的第二个贡献是一个随机化算法，它可以在一个或多个读/写循环中运行(称为随机和随机+)。利用从这些算法中得出的概念，我们引入了GDE-RANDOM+算法，它通过与RAN-DOM+相结合进一步提高了GDE的非冗余读取器数量。
We introduce distributed algorithms for the RFID coverage problem, which is defined as finding the minimum amount of RFID readers that cover every tag. The algorithms depends on rounds of writes and reads in/from the tags' memories. The first algorithm, called Greedy Distributed Elimination (GDE), is inspired of, and equivalent to, the greedy approximation algorithm of the set cover problem. Our second contribution is a randomized algorithm that can run in one or more write/read rounds (called RANDOM and RANDOM+). Using concepts concluded from these algorithms, we introduce algorithm GDE-RANDOM+ which improves further the number of non-redundant readers of GDE by integrating it with RAN-DOM+.