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]，阅读器v₁处在v₂的干扰信号范围内，标签(T)发送到阅读器v₁的弱信号会受到来自阅读器v₂的强信号的干扰，可能造成阅读v₁与标签通信的失败。当某个标签处在两个或多个不同阅读器的阅读范围内时，且有一个以上阅读器同时与该标签通信，就会产生阅读器-标签碰撞。如图 1(b)所示，阅读器v₁和v₂的阅读范围重叠，标签T位于重叠区域内，如果阅读器v₁和v₂的通信频率相同，且同时向该标签发信号时，标签会无法作出正确的响应。

目前解决阅读碰撞问题的算法很多，这些算法可以被分为两种：一种是基于有效范围的算法，另一种是基于调度的算法^[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所示，用v_i表示一个阅读器，r_i表示v_i的读取范围(即v_i所能确定标签的距离范围)，I_i表示v_i的干扰范围(即v_i的信号能对其他阅读器信号产生影响的距离范围)，d_ij表示阅读器v_i和v_j之间的距离。假设所有的阅读器都具有相同的读取范围，当满足下面的条件时，两个阅读器v_i和v_j之间将会产生RTI问题，即：

$ {d_{ij}} < {r_i} + {r_j} = 2r $

(1)

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

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

$ {d_{ij}} < {r_i} + {I_j} $

(2)

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

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

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

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

2 本文算法

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

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

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

$ {d_{ij}} > {r_i} + {r_j} $

(3)

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

$ \left| {t({v_i}) - t({v_j})} \right| \in T $

(4)

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

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

$ \left| {t({v_i}) - t({v_k})} \right| \notin T $

(5)

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

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

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

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

$ {d_{ij}} > {r_i} + {I_j} $

(6)

这时，如果阅读器使用相同的频率f_i就会产生相互干扰，因此需要给会产生频率干扰的阅读器分配不同的工作频带。同样，这些阅读器组成的网络用G′=(v′, E′)来表示，把距离不满足式(6) 的阅读器，看作是相邻的，即(v′_i, v′_j)∈E′。将阅读器看成一个或多个无向图G′_i。给图G′的着色，就是分配颜色c′_i到阅读器v′_i，这组颜色用集合C′={c′₁, c′₂, …, c′_M}来表示，这里每一种颜色可以看作为一个频率，即C′={c′₁, c′₂, …, c′_M}→F={f₁, f₂, …, f_M}那么所用最少的颜色数M=χ(G′)就是需要的频带数。

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

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

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

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

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

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

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

3 实例说明

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

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

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

接下来同样对组内的阅读器成员用图论的相关理论对它们进行涂色分配频率。这种情况下，当阅读器之间满足式(2)，就把这些阅读器看作是相邻的，把这些阅读器组成的无向图G′₁进行涂色分配频率，方法和上面类似，在此就不作重复讨论，这样又可以解决RRI的问题。

在实际的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算法更加有效率，能更快速读取需被识别物体的信息。在实际庞大的仓储系统管理中，能够减少产品入库信息存储的时间，提高工作效率。

5 结语

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