RFID阅读器网络分布式自适应信号覆盖算法研究*

戴宏跃，廖 慧

（广州科技贸易职业学院智能制造学院，广州 511442）

0 引言

近年来，随着物联网应用的发展，RFID技术得到了越来越广泛的应用，特别是物流[1－2]、仓管、图书管理等相关领域，许多场景需要密集部署RFID阅读器网络来探测整个目标区域，因此，必须考虑系统的信号冲撞问题。信号冲突问题比较复杂，学术界在这方面有较多的研究[3－4]。目前解决多阅读器信号冲突问题的代表算法有基于调度与基于功率控制的防冲突算法，其中基于调度的算法主要是基于时分和频分多路工作，调度附近阅读器在不同时间或频率上工作，以避免信号冲突，这方面已有较深入的研究，王帅[5]针对CTT[6]算法在标签数量增加而吞吐率降低的情况，提出了基于伪ID码的树型防碰撞算法（IDCTT算法）。基于功率控制的防信号冲突算法主要通过调整阅读器功率大小，减少阅读器的信号重叠以达到放冲突的目的，主要算法有王红军等[7]提出的多重优化的分布式无线覆盖探测算法。这些算法虽然在一定程度上缓解了冲突情况，但是系统结构复杂，建立和维护网络时需消耗大量资源。Carbunar B等[8]则针对RFID阅读器网络，提出了一种通过消除冗余阅读器（Redundant Reader Elimination，RRE）算法以提高阅读器网络的覆盖效率，但是RRE算法的实际效果并不理想，如图1所示，在读写区域互相重叠的阅读器，覆盖同样数量的标签的场景下，打断如图所示的连续结变得十分困难，图中，阅读器R1~R5覆盖T1~T8个标签，最优方案是只需要R2和R4保持活动，如果运行RRE算法，此时R4认为拥有T5~T8，R3认为拥有T3~T6，R2又认为拥有T1~T4，导致R2、R3和R4都需要保持活动。而且随着区域中阅读器与标签的数量增多，系统规模的增大，这种情况将变得更加严重，甚至在最坏的情况下需要2r－1个阅读器保持活动状态，而实际上只需要r个阅读器。

图1 连续结问题Fig.1 The difficulty of interrupting continuous node

从RRE算法的仿真的结果来看，其效果并不理想。基于此，本文提出了一种阅读器分布式适应性覆盖（Distributed Adaptive Coverage，DAC）算法。该算法旨在把RFID系统中相关的冗余阅读器找出来，后续可以使用相关命令关闭这些冗余阅读器，是整个系统具有最优数量的阅读器工作。

1 DAC算法设计

在提出本文的算法之前，首先根据实际情况，做如下设定。

（1）DAC算法可以应用与任何数量的RFID阅读器与标签，认为阅读器与标签的拓扑结构在某一短时间段内是固定的。阅读器网络中不存在能够协调阅读器之间工作行为的中央控制器。DAC算法不依赖于阅读器之间的通信能力。

（2）每个阅读器都有自己唯一的ID，用来作为信息交流的身份识别。

（3）本文仅仅考虑无源标签，因此，标签以接收到的信号的能量来应答阅读器的相关命令。

（4）标签具有有限的存储空间，其中一部分是只读的，用来存储唯一的标识；一部分是可读写的，供阅读器读写。

（5）标签具有命令匹配能力。根据不同的命令能做出不同的反应，或者根据命令不同的参数做出相应的动作。

（6）当多个标签应答同一个命令时，阅读器具有冲突探测能力。

1.1 DAC算法过程

为了提高阅读器的覆盖效率，探测出并关闭或休眠RFID阅读器网络中的冗余阅读器，减少覆盖重数，本文提出了该DAC算法。在阅读器网络拓扑中，假设阅读器之间不能直接通信，但是由于有可读写的标签存在，能够存储它所属阅读器的请求信息，因此可以利用标签作中间媒介，阅读器之间可以间接进行信息传递。每个阅读器具有预先收集其读写区域内所有标签信息，阅读器网络中所有阅读器都能执行该功能。阅读器在不同的时隙中工作，最大可能地避免冲突情况的发生，然后再执行DAC算法。DAC算法主要由3步组成。

（1）每个阅读器在随机时隙中收集它所覆盖的标签数目，保证每个阅读器能尽快获取本身所覆盖标签数。

（2）每个阅读器尝试将它所覆盖的标签数目以及阅读器本身的ID写入其所覆盖的所有标签中，但是标签仅仅存储最大数目值及相应阅读器的ID。具体实现过程是每个阅读器都发送包含阅读器ID与它所覆盖标签数目的写入标签命令，命令的格式如图2所示，处于该阅读器读写区域内的标签收到命令后，首先进行命令参数匹配，如果命令中包含的标签数目比标签已存在的数值大，即认为命令有效，执行写操作，将标签内已存储的标签数目值与阅读器ID数据刷新。反之，如果命令中包含的标签数目比标签已存在的数值小，则不作响应。

图2 标签命令结构Fig.2 The command structure of the tag

（3）阅读器查询读写区域内的每个标签，读取标签中所存储的阅读器ID。对于某一覆盖较多标签的阅读器，其读写区域内的多个标签可能同时具有该阅读器的ID，因为该阅读器覆盖了这些标签，而且标签数目较多，因此在前一步的工作中该阅读器可能已将自己的ID写入这些标签，导致该阅读器在这一步操作中，在多个标签中获取到该ID值。至少能获取一个标签ID的阅读器保留活动状态，而没有获取到任何ID的阅读器可以安全关闭，由于该阅读器所覆盖的标签数目较少，而且该阅读器所覆盖的所有标签同时已被其他的覆盖标签数目较多的处于活动状态的阅读器所覆盖，这样在前一步的操作中，该阅读器所覆盖的标签已将其存储的ID值更新了。

为了避免冲突情况，提高工作的可靠性，阅读器对它所覆盖标签发送的命令可以在上述设置的随机时隙内重复发送。

1.2 DAC算法实现

根据前面对标签命令的设计，定义如图3所示的描述标签的主要数据结构，各变量的含义如图中注释所示。

图3 标签的数据结构Fig.3 Data structure of the tag

图4所示为读写标签的C语言算法过程的伪代码，算法描述了在可读写标签中，如果阅读器发送过来的命令为写标签命令，则首先比较命令中的覆盖标签数值与标签内现存的值，如果命令中的覆盖标签数目值大于标签内现存的值，则更新标签内该值与阅读器ID（图中第6~9行）。当接收到的命令为读命令，则标签返回一个包含存储在标签里的标签标识符、阅读器ID与覆盖值的数据包。

图4 读写标签算法过程伪代码Fig.4 The pseudo codeof reading and writing tag

图5所示为探测冗余阅读器算法过程伪代码，概要描述了阅读器与可读写标签的一般过程。首先，阅读器获取覆盖标签数目值（第8~14行），在连续的第n个时帧中选择一个随机时隙，领用DetectCount（）方法探测阅读器的覆盖标签数，算法中为了避免冲突，保证获取的是阅读器覆盖标签数目的最大值，算法中循环操作了Frame_cnt次，这里Frame_cnt表示每个帧的时隙数，根据系统设置而定。获得阅读器的覆盖标签数目值后，接着将获取的覆盖标签数目值试图写入阅读器所覆盖的标签中（第16~20行）。同样，为了保证完全正确写入所覆盖区域中的全部标签，算法也循环操作了Frame_cnt次。接着阅读器读取覆盖区域内标签数据，获取标签的标识码，以及对应的标签数目值、阅读器ID，并将这些数据暂存阅读器数据列表Tags[]中（第23~28行），供下一步使用。最后阅读器分析该数据列表，统计数据列表中的阅读器ID等于读器本身的ID的个数，然后判断该阅读器是否为冗余阅读器（第29~40行）。

图5 探测冗余阅读器算法过程伪代码Fig.5 The pseudo code detecting redundancy reader

当某一阅读器确定为冗余阅读器以后，就可以通过相关命令关闭该阅读器，减小阅读器信号的冲撞，提高阅读器信号的覆盖效率。因此，对于同一区域，相同标签情况下，算法能够探测出的冗余阅读器数量越多，说明需要开启的阅读器数量越少，即只需要少量阅读器就能实现对整个区域的信号覆盖。

2 仿真结果与分析

在第一个试验中，在500 m×500 m的区域，随机部署了500个阅读器，标签的数目从1 000~8 000，为了减小阅读器信号覆盖的重数，避免信号冲突，本文重检测DAC算法与RRE算法找出的冗余阅读器数目的能力，图6所示为该试验的仿真结果。从仿真的结果可以看出，对于小规模部署的标签数目，两种算法都比较接近，因为在小规模部署的标签时，信号冲撞的情况相对较少，两种算法差别不大。但是随着区域中标签数量的增多，两算法探测到的冗余阅读器数量也随之减少。但DAC算法探测出的冗余阅读器数量一直比RRE算法的数量大，说明同一区域内，DAC算法支撑下，能探测出更多的冗余阅读器，所需活动阅读器的数量更少，覆盖效率更高。

图6 使用验证

图6 冗余阅读器数量随标签数量变化关系Fig.6 The relationship between the number of redundant reader and tags

图7所示为当标签数量恒为4 000，随机部署的阅读器的数量从50增加到1 000时，DAC与RRE算法探测出冗余阅读器数量情况。从图中显示的结果来看，当阅读器总数很少的时候，即阅读器部署稀疏的情况来说，很少有冗余阅读器问题，随着阅读器总数量的增多，阅读器部署的密度的越来越大，信号冲撞问题加剧，于是出现了越来越多的冗余阅读器，对比可以看出，DAC的结果一直在RRE之上，说明需要活动的阅读器相对较少，只需要少量的阅读器就能完成整个区域的信号覆盖，从另一方面说了DAC算法的高性能。

图7 冗余阅读器数量随阅读器总数量变化情况Fig.7 Redundant reader number with the total number of reader

3 结束语

本文分析了RFID系统相关的信号防冲撞算法的优缺点，根据RFID阅读器网络的特点，重点研究分析RRE算法存在的问题，提出了一种分布式适应性覆盖算法（DAC），仿真结果表明，在相同环境下，DAC算法能够探测到冗余阅读器的数量更多，在该算法支持下，需要活动的阅读器数量更少，信号冲撞的情况便随之降低，验证了DAC算法能在密集环境下的性能明显优于RRE算法，具有很好的适应性，可以有效提高阅读器网络的覆盖效率，减小信号冲突，达到了预期的目的。