Abstract: Radio Frequency IDentification (RFID) systems often require multiple readers to ensure coverage of the entire target area. When there are too much readers, because of the mutual interference between the readers, the efficiency of the whole RFID system and the recognition efficiency are reduced. To resolve the problem, a new reader anti-collision algorithm based on graph theory was proposed. Firstly, the reader network was considered as a simple graph with time slot of the reader groups, the readers with the same time slot were regarded as a group, and the adjacent readers were assigned with different time slot, thus avoiding the interference caused by overlapping. At the same time, considering the frequency interference problem within the group of readers, the readers in the group with the same frequency were regarded as a group, and the adjacent readers were assigned with different frequency, thus avoiding the frequency collision caused by too large interference range. Next, according to the grouping information, the time slots and the frequency resources were assigned to each reader by the central server through the arrangement command. Finally, the working order of each group of readers was assigned by the central server through the ordering commands. The simulation results showed that compared with the Neighbor-Friendly Reader Anti-Collision (NFRA) algorithm, the average work efficiency of the proposed scheme was improved by 6.5 percentage points and the efficiency of a system with 1000 readers was improved by 9.5 percentage points. The results demonstrate that the proposed algorithm based on graph theory can optimize the number of working readers in the given time and reduce the number of idle readers.

Key words: Radio Frequency IDentification (RFID), reader, work efficiency, graph theory, resource scheduling

摘要： 射频识别（RFID）系统的运行往往需要多个阅读器，以保证覆盖整个目标区域。在密集的阅读器的环境中，由于阅读器之间存在相互干扰，会影响整个RFID系统的工作效率，降低识别效率。针对上述问题，提出一种新的基于图论的阅读器防碰撞算法。首先把阅读器网络看成简单图，以时隙对阅读器分组，同时隙阅读器为一组，相邻阅读器分配不同的时隙，以解决阅读器因读取范围交叉重叠而引起的干扰；同时考虑组内阅读器的频率干扰问题，同样以频率对组内阅读器再分组，同频率阅读器为一组，相邻阅读器分配不同频率，以解决因干扰范围过大而引起的频率碰撞问题；然后根据分组信息，中央服务器通过配置命令将时隙和频率资源调度分配给每个阅读器；最后通过时序命令控制每组阅读器的工作顺序。仿真结果显示，相比邻近友好型防碰撞（NFRA）算法，该算法平均工作效率提升了6.5个百分点；阅读器数量为1000时系统工作效率提升了9.5个百分点。新算法能优化给定时间内工作阅读器的数量，减少闲置等待的阅读器数量。

关键词: 射频识别, 阅读器, 工作效率, 图论, 资源调度