基于图论的射频识别阅读器防碰撞算法

徐亚峰，崔英花

(北京信息科技大学 信息与通信工程学院，北京 100020)

(*通信作者电子邮箱626751238@qq.com)

基于图论的射频识别阅读器防碰撞算法

徐亚峰*，崔英花

(北京信息科技大学 信息与通信工程学院，北京 100020)

(*通信作者电子邮箱626751238@qq.com)

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

射频识别；阅读器；工作效率；图论；资源调度

0 引言

近年来，随着物联网的飞速发展，射频识别(Radio Frequency IDentification，RFID)技术已经被广泛应用在多个领域，例如交通，物流，医疗保健，身识别(电子护照、二代身份证) ，图书馆，危险品管理，烟酒，票证防伪，旅游，军事，智能家居等[1]。然而伴随着RFID技术的广泛应用，RFID技术中的碰撞问题也日渐严重。理论上，阅读器能自动识别在其天线信号覆盖范围内的不同的标签，然而单个阅读器的工作区域是有限的，为了扩展覆盖区域，就需要多个阅读器组成阅读器网络。由于相邻阅读器在其信号交叠区域内会相互产生干扰，因此会发生阅读器碰撞问题[2]。

当一个阅读器附近有一个或多个有相同工作频率的阅读器时，阅读器收到的邻近阅读器的信号相当于噪声信号。如果阅读器与标签通信时，噪声功率与标签反射回的功率的比值超过了接收门限值，那么阅读器就无法正确识别该标签的信号。一般来说，阅读器的碰撞问题可以分为两类:一类是“阅读器-阅读器”(Reader to Reader Interference, RRI)碰撞，另一类是“阅读器-标签”(Reader to Tag Interference, RTI)碰撞[3-4]。如图1(a)所示，由于阅读器(v)的干扰范围(I)大于读取范围(r)[5-6]，阅读器v1处在v2的干扰信号范围内，标签(T)发送到阅读器v1的弱信号会受到来自阅读器v2的强信号的干扰，可能造成阅读v1与标签通信的失败。当某个标签处在两个或多个不同阅读器的阅读范围内时，且有一个以上阅读器同时与该标签通信，就会产生阅读器-标签碰撞。如图1(b)所示，阅读器v1和v2的阅读范围重叠，标签T位于重叠区域内，如果阅读器v1和v2的通信频率相同，且同时向该标签发信号时，标签会无法作出正确的响应。

图1 阅读器碰撞类型Fig. 1 Reader collision types

目前解决阅读碰撞问题的算法很多，这些算法可以被分为两种：一种是基于有效范围的算法，另一种是基于调度的算法[7]。基于有效范围的防碰撞算法核心思想是通过减小阅读器之间的重叠区域来减少阅读器之间的碰撞，这类算法只能使阅读器碰撞最少化，而不能完全消除阅读器的碰撞；而基于调度的防碰撞算法核心思想是防止阅读器同时发送信号给标签,以此避免碰撞发生，该类算法一直是防碰撞算法的主流[7-8]。

Colorwave算法[9]是基于分布式的时分复用型的防碰撞算法，所有阅读器通过同步机制组成一个阅读器网络，每个阅读器都被分配了对应的时隙(颜色)，对阅读器网络的时隙的分配就相当于图着色问题。但是Colorwave算法要求阅读器之间有严格的时间同步，然而Ad Hoc网络很难做到时间同步，阅读器也无法探测到发生在标签上的碰撞。另外，阅读器的移动会引起时隙重新分配，使整个系统的效率下降。

基于Q-Learning在线强化学习的防冲突算法HiQ[10]采用多层结构，通过与RFID系统的交流来学习阅读器层的冲突模式，动态地分配阅读器频率和时隙资源，从而实现防碰撞。但算法的多层结构使阅读器设计复杂，增加了硬件成本；而且移动阅读器会改变网络的拓扑结构，降低系统的效率。

文献[11]在分析Colorwave和HiQ算法后提出了一种邻近友好型防碰撞(Neighbor-Friendly Reader Anti-Collision，NFRA)算法。该算法采用的是基于服务器调度的时分复用型算法。中央服务器对区域内多个阅读器进行配置，然后根据排序命令为阅读器分配操作的优先次序，避免会相互干扰的阅读器在同一时间段内操作，从而减少整个阅读器网络的碰撞情况。但是该算法只考虑了RTI的问题没有考虑RRI的问题，并且排序机制是系统随机的机制，并不能最有效地分配每一个阅读器的工作优先次序，反而会增加系的等待时间，降低整体的效率。

本文在NFRA算法基础上提出一种基于图形着色理论的新型防碰撞算法，同时考虑阅读器两种类型的碰撞，将整个阅读器网络以组来划分，每个组内阅读器可以在同一时隙内操作，从而可以给每组分配一个工作时隙；并且尽可能使组内成员数达到最大，减少所用的时隙数。而组内潜在的干扰问题则通过分配不同的频率来解决。阅读器操作的优先次序以组为单位，按组内成员数由大到小的顺序来分配时隙。该算法能有效提升阅读器单位时间内的操作数量，减少系统的等待时间，提高阅读器网络的整体工作效率。

1 相关工作

本文首先定义下面的一些符号。如图1所示，用vi表示一个阅读器，ri表示vi的读取范围(即vi所能确定标签的距离范围)，Ii表示vi的干扰范围(即vi的信号能对其他阅读器信号产生影响的距离范围)，dij表示阅读器vi和vj之间的距离。假设所有的阅读器都具有相同的读取范围，当满足下面的条件时，两个阅读器vi和vj之间将会产生RTI 问题，即：

dij

(1)

在这种情况下，阅读器vi和vj必须在不同的时隙进行操作才能避免发生冲突。

当满足下面的条件时，RRT和RTI都会发生：

dij

(2)

在这种情况下，阅读器vi和vj必须以不同的频率进行操作才能避免发生冲突。

假设在某个固定的区域里放置了大量的阅读器，中央服务器的信号能到达该区域内的任何阅读器，并且服务器知道所有阅读器的位置信息,同时能给阅读器分配时隙和频率资源。在给定的时间内，操作的阅读器数量越多，效率越高。提出的阅读器防碰撞算法的目的就是在给定时间内尽可能最大化工作的阅读器数量，最小化碰撞次数。

文献[11]的NFRA算法开始让服务器广播一个配置命令(Arrangement Command，AC)，这个命令包含开始的回合数和随机数(随机数从1到N，N的取值取于阅读器的数量)。当阅读器接收到配置命令后，各自生成自己1-N的随机数，随后服务器发送排序命令(Ordering Command， OC)，当阅读器自身的随机数和OC命令的值相同时，阅读器就向周围广播beacon信号，来确定是否会有碰撞发生，如果发现会与相邻阅读器产生碰撞，阅读器将发送覆盖帧(Overriding Frame，OF)给邻近阅读器，使邻近阅读器不会接受下一次的OC命令直到本回合结束，继续等待下一回合的AC命令。那么其他没有接收到OF的阅读器，等待本回合下一个OC命令，若有与OC命令值相同的阅读器，将重复上面的过程。

假设有如图2所示的一个阅读器场景，服务器开始向它覆盖的区域广播AC命令，阅读器收到命令后产生的随机数(本例中随机数范围是1到3)。为方便表示，图2中用i-j表示产生随机数为i的阅读器vj，如下面的描述中阅读器2-1即指产生随机为2的阅读器v1。这个过程完成后，服务器广播值为1的OC命令，生成的随机数1的阅读器开始向邻居阅读器发送beacon信号，来确定周围是否有相同随机数的阅读器存在。从图2可以看到所有随机数为1的阅读器之间都在各自的干扰范围之外，不会产生干扰，然后这些阅读开始工作读取在它们工作区域里的标签。同时，服务器开始广播值为2的OC命令，那么阅读器2-1和2-2都开始发送beacon信号，发现它们之间会产生相互干扰。产生干扰的阅读器会放弃本回合的标签识别过程，直到下回合的AC命令。因为在上一个值为1的OC命令阶段，阅读器2- 4收到来自邻近阅读器1-2的OF命令，因此阅读器2- 4也不会工作。只有阅读器2-3会尝试进行标签的识别工作。服务器又开始广播值为3的OC命令，生成随机数3的阅读器重复上述类似的操作。阅读器3-1和3-2由于不会发生相互碰撞，也没有收到任何来自邻近阅读器的OF命令，因此可以尝试识别标签。类似的阅读器2- 4，阅读器3-3也不能对标签进行识别工作。

图2 多阅读器网络Fig. 2 Multi-reader network

从图2中可以发现，如果仅仅只考虑时间的问题，第一个OC命令可以同时工作的阅读器不仅仅只是3个，实际上是5个，它们分别是阅读器1-1,1-2,1-3,2-1和3-1。由于阅读器本身的数值是随机生成的，所以无法保证最大化同一时间段内可操作的阅读器个数，使得本可以工作的阅读器不得不闲置等待下一次的OC命令，造成资源的浪费。如果处于密集区域的阅读器产生的随机数值越小那么就意味着它在OC命令到来之时就越有优先工作的可能。如果阅读器的分布如图3所示，可以看出阅读器v5和v6处于最密集的区域当中。假设阅读器v5生成的随机数是1，那么第一个OC命令到来时，阅读器v5就要周围的阅读器发送beacon信号，邻近的6个阅读器都将被禁止在当前AC命令下工作。相反如果处于相对较稀疏区域的阅读器v4生成的随机数是1，那么被禁止在当前AC命令下工作的阅读器只有3个。从图3中可以知道，最坏的情况是阅读器v5和v7生成的随机数是1，周围其他的8个阅读器都将被限制工作，直到下个AC命令的到来；而最好的情况是处于边缘稀疏区域的阅读器生成的随机数是1，例如阅读器v2,v4,v7和v9，这种情况下被限制工作的阅读器是6个。如果阅读器的数量是巨大的，那么将能极大地改善整个阅读器网络资源的利用，提高系统的工作效率。

图3 密集阅读器网络例子Fig. 3 Example of dense reader network

通过上面的分析，可以知道上述缺陷都是由于随机这个机制所导致的，并且NFRA算法也没有考虑到RRI的问题。回到图2中，当阅读器2-1和2-2使用相同的频率同时向周围发送beacon信号，由于干扰的存在，邻近阅读器并不一定能正确接收这个beacon信号，那么阅读器之间的干扰依然会存在。 因此需要解决潜在的频率干扰问题，同时最大化每个OC命令可操作的阅读器数量。这就是本文提出的算法所需要解决的事情。

2 本文算法

对于一个密集的RFID阅读器网络，如果把阅读器vi看成是一个点，那么整个阅读器网络就可以看作是由这些点连成的无向图G=(V,E)。其中：V代表无向图中点的集合(阅读器集合)，这些点被称为顶点；E表示一组不同的无序顶点所组成的边。本文后面都用G来表示阅读器网络。

首先来讨论时隙的问题。在密集的阅读器网络G中来对阅读器vi进行分组，阅读器的分组要满足下面的条件：

1) 组内阅读器任意两个成员vi,vj之间满足：

dij>ri+rj

(3)

此时任意两个阅读器vi,vj之间对于时隙的分配满足：

|t(vi)-t(vj)|∈T

(4)

其中T是图着色问题中的T-设置{0}，此处表示组内任意两个阅读器成员可以在同一个时隙内工作。

2) 组内阅读器成员数是极大的。当阅读器网络G中任意不属于该组的阅读器vk加入该组后，会导致：

|t(vi)-t(vk)|∉T

(5)

即组内再增加任何一个阅读器后都会有干扰产生，不能在同一时隙内工作。

由于组内阅读器成员可以在同一个时隙内工作，那么每一组就可以代表一个时隙ti，时隙的先后顺序要取决于组内阅读器的成员数，按照数量由大到小的顺序进行排序。按颜色对阅读器网络分组，每一种颜色代表一个时隙，下面进行详细分析。

如果两个阅读器v1,v2之间满足式(1)，那么就把这两个阅读器看作相邻的，即(vi,vj)∈E。整个RFID阅读器网络就可以看成一个或多个无向图Gi。阅读器网络G的着色，就是分配颜色ci到阅读器vi，使两相邻的阅读器不会被分配到同一种颜色。颜色被定义为一组非负的整数，用集合来C={c1,c2,…,cN}表示，在这里每一种颜色都可以看作是一个时隙，即C={c1,c2,…,cN}→T′={t1,t2,…,tN}。在分配颜色时，定义最少的颜色为图形的色度数量，色度用χ(G)来表示，那么N=χ(G)就是所需要的时隙数。

然后来讨论频率干扰的问题，对于已经分好颜色ci的阅读器之间，虽然可以在同一时隙内工作，但由于阅读器的干扰范围远大于阅读器的识别范围，当阅读器之间不满足下面的条件：

dij>ri+Ij

(6)

假设服务器知道所有阅读器的位置信息，每个阅读器都有自己的ID，刚开始阅读器都处于静默状态，服务器后台通过程序运算分组(分配时隙)和分配频率完毕，按照组内成员数由大到小排序分配组号1到N(时隙的顺序)；然后开始向其传输范围内的阅读器广播分组的配置命令，命令格式如图4所示。阅读器收到配置命令后存储自己的分组信息和频率信息，然后服务器开始广播值为1的时序命令，收到时序命令的阅读器用自己存储的分组信息与之比较，若两者相同，那么阅读器被激活，用指定的频率开始工作。当所有组号为1的阅读器都开始工作，系统进入标签识别时间。完成识别后之后服务器又开始广播值为2的时序命令，类似组号为2的所有阅读器接开始识别工作。识别时间过后，广播值为3的时序命令，重复上述步骤直到所有的阅读器完成工作。

图4 服务器配置命令格式

Fig. 4 Server configuration command format

服务器分配资源控制阅读器步骤如下：

步骤1 服务器根据阅读器位置信息和式(3)对阅读器进行分组，此时分配的是时隙资源。

步骤2 服务器根据式(6)对步骤1中已经分好组的阅读器组内再分组，此时分配的是频率资源。

步骤3 服务器将分配好的时隙和频率资源通过如图4格式的AC命令广播给阅读器。

步骤4 阅读器接收存储服务分配的资源信息，等待服务器的OC命令。

步骤5 服务器广播第一个OC命令，阅读器将收到的OC命令和自己存储的时隙资源比较，如果两者值相同，那么开始工作；否则等待下个OC命令，直到所有阅读器工作完毕。

3 实例说明

假设有如图5(a)所示的一个相对密集的阅读器网络，图中阅读器的碰撞情况很严重，把每个阅读器vi看成是无向图G1的一个顶点，如果两个阅读之间的距离满足式(1)，那么就把这两个阅读器看作是相邻的，这些阅读器组成的无向图G1如图5(b)所示。

前面已经假设服务器知道所有阅读器的具体位置信息，所以服务器知道阅读器的分布状况，如图5(b)。如果用颜色c1给阅读器v1涂色，那么阅读器v2,v3,v4只能用除了颜色c1以外的颜色来涂色。由于阅读器v4处于相对密集的区域，那么先给阅读器v2,v3涂色上颜色c2，阅读器v4与阅读器v1,v2,v3都相邻只能选用颜色c1,c2以外的颜色c3。阅读器v5周围的阅读器只有v3和v4被涂上颜色c2和颜色c3，为了使选用的颜色数尽可能最少，用颜色c1给阅读器v5涂色，类似地，阅读器v7周围的阅读器v4和v5分别被涂上颜色c1和颜色c3，可以用颜色c2给它涂色。由于阅读器v8处于比较密集的区域，最后考虑给它涂色。同样，阅读器v6用颜色c1涂色，阅读器v9也可以用颜色c1涂色，阅读器v10用颜色c3涂色，最后剩下阅读器v8，其周围阅读器点分别使用过颜色c1,c2,c3，那么为了防止冲突，用颜色c4给它涂色，这样整个阅读器网络G1的顶点就着色完毕。G1被分为四组c1,c2,c3,c4，即所需时隙数N=χ(G1)=4，各组内阅读器成员个数分别为4，3，2，1。着色完成后的阅读器网络G1如图5(c)所示。

然后按组内成员大小来分配时隙的顺序，在上面的实例中，颜色c1的所有阅读器被分配t1，颜色c2的所有阅读器被分配t2，以此类推颜色c3对应时隙t3，颜色c4对应时隙t4。图5(c)中任意相邻的阅读器之间的颜色都不相同，也就是说在RFID阅读器网络G1中任意有识别区域相互交叉重叠的阅读器都被分配不同时隙，从而可以避免RTI的碰撞问题。

图5 密集阅读器转换与着色实例Fig. 5 Example for conversion and coloring of dense readers

在实际的RFID阅读器网络中，阅读器的数量巨大，那么相应的无向图的顶点也非常多，这种情况下通常采用贪心法来给无向图的顶点着色[12]，但是基本思想是一致的。

服务器在完成了上述工作后，已经对每个阅读器分配好了工作的时隙和频率，只需要向阅读广播资源配置命令，其格式如图4所示，阅读器接收到命令后存储被分配的资源信息，然后根据时序命令开始工作。

4 仿真与分析

阅读器防碰撞算法的目的是在没有相互干扰的情况下，尽可让更多的阅读器能同时工作，因此算法的性能可以用在给定的时间内同时工作的阅读器数量来评估。定义每毫秒工作的阅读器的数量为系统的工作效率。下面对本文算法和NFRA算法在同等条件下进行仿真比较。

在实际的仓储管理系统中，RFID系统需要对每个入库的产品进行数据的录入，管理盘点这些产品的数量等信息。为了能覆盖整个仓库的产品，系统必须在仓库中放置多个阅读器。

实验条件：假设有一个20 m×20 m的仓库，为了体现算法的一般性，在这个区域中随机放置数量不同的阅读器，阅读器数量分别为100，200，…，1 000；假设阅读的读取范围为2 m，干扰范围为6 m；阅读器识别100个标签需要的时间是0.46 ms,服务器的AC命令时长为2.83 ms，OC命令时长为1 ms[11]。由于在同等条件下是否考虑路径损耗都不会影响算法的性能比较，因此实验环境的路径损耗设置为理想环境。通过多次实验仿真取平均值，得到如图6所示的结果。

实验仿真结果表明，本文算法的工作效率要优于NFRA算法。当阅读器数目为100时，本文算法比NFRA算法的工作效率提升了1.5个百分点；阅读器数目为200时，系统效率提升3.1个百分点；当阅读器数目达到1 000时系统的效率提升了9.5个百分点；随着阅读器数量的增多，本文算法相比NFRA算法体现出更大的优越性，系统的平均工作效率提升了6.5个百分点。而且随着阅读器数量的不断增多，本文算法性能将趋于一个相对平稳的增长状态。

当阅读器数目越多，网络环境越密集，本文算法相比NFRA算法更加有效率，能更快速读取需被识别物体的信息。在实际庞大的仓储系统管理中，能够减少产品入库信息存储的时间，提高工作效率。

图6 算法性能比较Fig. 6 Performance comparison of algorithms

5 结语

本文针对密集环境下的阅读器碰撞问题进行了探讨，基于NFRA提出了一种新的防碰撞算法，利用简单图着色理论，同时考虑时隙和频率的分配问题，解决了NFRA算法由于随机机制导致的阅读器闲置和潜在的频率干扰问题，能在保证阅读器不产生干扰的情况下，使尽可能多的阅读器在同一时间工作，减少了闲置的阅读器数量。仿真结果表明，相比NFRA算法，本文算法的工作效率有不错的提升，并且工作效率的增量随着阅读器数量的增加而增加。但是该方法可能对中央服务器的性能要求比较高，阅读器的移动性问题还有待进一步研究。整体来说，本文算法能够解决密集环境下阅读器的碰撞问题，提高RFID系统的工作效率，具有较好的实际意义和价值。

References)

[1] 吴欢欢,周建平,许燕,等.RFID发展及其应用综述[J].计算机应用与软件,2013,30(12):203-206. (WU H H, ZHOU J P, XU Y, et al. A comprehensive review on RFID development and its application [J]. Computer Applications and Software, 2013, 30(12): 203-206.)

[2] 于惠钧,刘晓燕,朱永祥.RFID标签阅读器系统防冲突算法的研究[J]. 包装工程,2008,29(5):46-48. (YU H J, LIU X Y, ZHU Y X. Study on anti-collision algorithms in RFID reader system [J]. Packaging Engineering, 2008, 29(5): 46-48.)

[3] 刘玮,吴晓波,张伟伟,等.基于调度方式的阅读器防碰撞算法[J]. 包装工程,2014,35(21):127-131. (LIU W, WU X B, ZHANG W W, et al. An anti-collision algorithm based on schedule mode for reader [J]. Packaging Engineering, 2014, 35(21): 127-131.)

[4] 陈颖,张福洪.RFID传感网络中多阅读器碰撞算法的研究[J].传感技术学报,2010,23(2):265-268. (CHEN Y, ZHANG F H. Study on reader anti-collision algorithm in RFID sensor networks [J]. Chinese Journal of Sensors and Actuators, 2010, 23(2): 265-268.)

[5] 顾成喜,顾才东,龚伟.RFID环境下利用通报机制的分布式阅读器防冲突算法[J/OL].计算机应用研究, [2017- 06- 15]. http://www.arocmag.com/article/02- 2017- 06- 015.html. (GU C X, GU C D, GONG W. Distributed reader anti-collision algorithm using notification mechanism in RFID environments[J]. Application Research of Computers, [2017- 06- 15]. http://www.arocmag.com/article/02- 2017- 06- 015.html.

[6] 王宇,甘健侯.一种分布式全类型RFID阅读器碰撞解决方案[J].电子技术应用,2016,42(4):92-94,98. (WANG Y, GAN J H. A distributed anti algorithm for all types of RFID reader collision [J]. Application of Electronic Technique, 2016, 42(4): 92-94,98.)

[7] 郭雷勇,谭洪舟,高守平,等.RFID系统阅读器反碰撞算法分类与研究[J].计算机技术与发展,2009,19(9):13-16,20. (GUO L Y, TAN H Z, GAO S P，et al. Taxonomy and survey of RFID reader anti-collision protocols[J]. Computer Technology and Development, 2009, 19(9): 13-16, 20.)

[8] 李剑丹. RFID系统中多阅读器环境下防碰撞问题的研究[D].武汉：武汉理工大学,2014:4-14. (LI J D. Research of anti-collision problem for multiple readers in the RFID system[D].Wuhan: Wuhan University of Technology, 2014: 4-14.)

[9] WALDROP J, ENGLES D W, SARMA S E. Colorwave: an anticollision algorithm for the reader collision problem [C]// ICC 2003: Proceedings of 2003 IEEE International Conference on Communications. Piscataway, NJ: IEEE, 2003: 1206-1210.

[10] HO J, ENGELS D W, SARMA S E. HiQ: a hierarchical Q-learning algorithm to solve the reader collision problem [C]// SAINT Workshops 2006: Proceedings of the 2006 International Symposium on Applications and the Internet Workshops. Piscataway, NJ: IEEE, 2006: 88-91．

[11] EOM J-B, YIM S-B, LEE T-J. An efficient reader anticollision algorithm in dense RFID networks with mobile RFID readers [J]. IEEE Transactions on Industrial Electronics, 2009, 56(7): 2326-2336.

[12] 冯珊珊.基于图着色理论的聚类研究[D].太原:太原理工大学,2013.:14-17. (FENG S S. Research on clustering algorithm based on graph coloring theory [D]. Taiyuan: Taiyuan University of Technology, 2013: 14-17.)

This work is partially supported by the National Natural Science Foundation of China (61340005), the General Program of Beijing Municipal Natural Science Foundation (4132012), the Science and Technology Development Program of Beijing Municipal Education Commission (KM201411232011).

XUYafeng, born in 1990，M. S. candidate. His research interests include radio frequency identification.

CUIYinghua, born in 1973，Ph. D., associate professor. Her research interests include Radio frequency identification.

Anti-collisionalgorithmforreadersinradiofrequencyidentificationbasedongraphtheory

XU Yafeng*，CUI Yinghua

(SchoolofInformationandCommunicationEngineering,BeijingInformationScienceandTechnologyUniversity,Beijing100020，china)

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 1 000 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.

Radio Frequency IDentification (RFID)； reader； work efficiency； graph theory； resource scheduling

TP391.45; TN92

A

2017- 01- 24;

2017- 03- 14。

国家自然科学基金资助项目(61340005)；北京市自然科学基金面上项目(4132012)；北京市教委科技发展计划项目(KM201411232011)。

徐亚峰(1990—)，男，江西进贤人，硕士研究生，主要研究方向：无线射频识别； 崔英花(1973—)，女，吉林蛟河人，副教授，博士，主要研究方向：无线射频识别。

1001- 9081(2017)08- 2163- 05

10.11772/j.issn.1001- 9081.2017.08.2163