一种减少通信复杂度的RFID搜索树防碰撞算法*

莫 磊，唐 斌，房梦旭

(1.成都航空职业技术学院 信息工程学院，成都 610100；2.四川省高校校企联合“航空电子技术”应用技术创新基地，成都 610100)

0 引 言

典型的射频识别(Radio Frequency Identification,RFID)系统一般由电子标签和阅读器组成[1]，其防碰撞问题主要有三种情况，分别是一个阅读器作用范围内有多个标签、多个阅读器作用范围内有一个标签和多个阅读器作用范围内有多个标签，涉及的问题主要有多标签碰撞问题和多阅读器碰撞问题。由于标签的成本低、能量少、内存小、计算处理能力弱，RFID防碰撞问题的难点主要集中在多标签防碰撞方面。本文针对第一种情况进行研究。在这种情况下，由于所有的电子标签与阅读器共用一个信道，当有多个标签处于同一阅读器的作用范围内，在同一时刻向阅读器发送数据时就会发生碰撞，导致阅读器不能读取标签数据[2]。

现阶段多标签防碰撞算法一般是基于时分多路的方法，主要有基于二进制搜索树的防碰撞算法和基于ALOHA的防碰撞算法[3]。ALOHA算法是一种基于概率统计的防碰撞算法，读取量大，速度快，但很多情况下读取率达不到100%，存在由于多次读不到某一标签而出现“饥饿”问题[4]。二进制树算法是一种确定性算法，不存在“饥饿”问题，读取率可以达到100%，但通信量大，读取时间长[5]。本文重点研究二进制树算法。

在搜索树算法中，除了总时隙指标以外，通信复杂度也是非常重要的指标，它是识别所有标签所需传送的总比特数[6]，在查询时隙相同的情况下，单位时隙通信数据量越少，则通信复杂度越低。本文以二叉树搜索为载体，重点讨论单位时隙的通信复杂度问题。首先介绍现有的典型二叉树搜索算法，接着提出了一种减少通信复杂度(Reducing Communication Complexity，RCC)的防碰撞算法，最后对几种算法进行了比较和仿真，结果表明本文算法明显优于现有的二叉树搜索算法。

1 传统搜索树防碰撞算法

基本二进制搜索(Binary Search,BS)算法[7]的主要思想是，把处于碰撞状态的标签分成子集0和子集1，先查询子集0，若无碰撞，则识别出一个标签；若有碰撞，再把子集0分成00子集和01子集，先查询子集00，这样不断查询下去，最终可识别出一个标签；接着再从头开始搜索，循环往复，直到识别出所有标签[8]。

基本二进制搜索算法在识别出一个标签后，再从头开始搜索，识别效率低下。后退式二进制搜索(Regressive Binary Search,RBS)防碰撞算法[9]对此作了改进，当识别出一个标签后，不是从头开始搜索，而是回到上一节点开始搜索，这样，搜索次数大大减少，搜索效率得到较大提高。

在基本二进制搜索算法中，每一次搜索，标签的数据总是被完整地传给阅读器，数据传送时间长、耗能多。动态二进制搜索(Dynamic Binary Search,DBS)防碰撞算法[10]对此作了改进，阅读器只发送部分数据给标签，另一部分标签已知的数据则不予发送；标签只返回部分数据给阅读器，另一部分阅读器已知的数据则不予发送，阅读器发送的数据和标签返回的数据都是动态变化的。通过动态搜索，阅读器和标签每个时隙发送的数据比特数减少，提高了搜索速率。

碰撞树(Collision Tree,CT)算法[11]是一个优秀的二叉树算法，它根据阅读器检测到的碰撞位信息直接生成两个新的前缀，根据前缀对标签进行搜索，ID和前缀相符合的标签响应命令并反馈前缀以后的ID数据给阅读器。CT算法大幅度提高了RFID多标签识别的性能，开启了基于碰撞树的防碰撞算法系列，并成为该算法系列的代表算法[12]。

2 RCC算法

2.1 算法原理

算法的核心思想有两个：一是减少阅读器搜索的次数；二是减少搜索时阅读器和标签间通信的数据比特数。

在传统的二进制搜索法中，通过前缀对标签进行搜索，存在阅读器反复发送标签已知数据的问题。在本文算法中，阅读器不再发送标签搜索前缀，而是通过发送前缀长度信息，结合标签是否为当前响应子集对标签进行分类搜索，可有效避免阅读器重复发送数据。

在标签中设置前缀长度寄存器Q和响应标志寄存器R。在Q中存储前缀长度信息，R的取值为0或1，以区分和搜索当前0子集和1子集，实现返回式搜索。

当发现只有一个碰撞位时，可直接识别出两个标签，减少了标签搜索的次数，进一步提高了标签搜索的速率。

2.2 算法命令

设标签ID长度为N，按位表示为[N-1，N-2，…，1，0]。前缀长度寄存器Q的初始值为0，响应标志寄存器R的初始值为0。在阅读器设置堆栈存储区，存储1子集前缀长度信息，并按后进先出的原则对数据进行存取。

为了便于理解，先介绍几个阅读器命令。

(1)request(ε)：初始搜索命令。收到此命令的标签发送序列号给阅读器。

(2)request(0,P)：0子集搜索命令。标志寄存器R为0的标签响应命令，更新前缀长度寄存器Q为P，设K=N-P-1，第K位为‘0’的标签返回第K-1～0位数据给阅读器，第K位为‘1’的标签更新标志寄存器R为1。

(3)request(1,P)：1子集搜索命令。标志寄存器R为1，前缀长度寄存器Q为P的标签响应命令，设K=N-P-1，返回第K-1～0位数据给阅读器，同时更新标志寄存器R为0。

2.3 算法流程

算法实现步骤如下：

Step1 阅读器发送request(ε)请求命令。

Step2 所有收到请求命令标签同时发送序列号数据给阅读器。

Step3 阅读器检测数据并根据数据位碰撞情况作出相应的处理。若没有接收到任何数据，则说明在阅读器附近没有标签，转至Step 6；若接收到数据，但没有任何碰撞，则可识别一个标签，转至Step 5；若检测到只有一个序列号数据位发生碰撞，则可直接识别两个标签，转至Step 5；若检测到有两个或两个以上的序列号数据位发生碰撞，设最高序列号碰撞位为标签的第K位，则P=N-K-1，阅读器把P值存储到阅读器堆栈区；阅读器发送request(0，P)请求命令。

Step4 标志寄存器R为0的标签响应命令，更新前缀长度寄存器Q为P，设K=N-P-1，第K位为‘0’的标签返回第K-1～0位数据给阅读器，第K位为‘1’的标签更新标志寄存器R为1，转至Step 3。

Step5 阅读器识别出标签序列号，对标签数据进行读写，让标签处于“无声”状态。

Step6 阅读器弹出堆栈存储区数据，若堆栈为空，则搜索结束；若堆栈不为空，设数据为P，阅读器发送request(1,P)请求命令。

Step7 前缀长度寄存器Q为P的标签响应命令，设K=N-P-1，返回第K-1～0位数据给阅读器，同时更新标志寄存器R为0。

Step8 跳至Step 3。依此循环，直到堆栈为空，识别出所有标签。

算法流程如图1所示。

图1 RCC算法流程

2.4 算法举例

假设阅读器作用范围内有4个标签，序列号为10位，即N=10，如表1所示。

表1 标签及其序列号

RCC防碰撞算法识别标签过程见表2。识别4个标签，总共用了7个时隙，在总时隙数上小于BS算法和DBS算法，与CT算法相同；在通信复杂度上，由于通信时阅读器只发送前缀长度信息和标签只返回碰撞位以后信息，通信数据比特数少于CT算法，更少于BS算法和DBS算法。

表2 RCC防碰撞算法识别过程

表2(续)

2.5 算法分析

由2.4节可以看出，RCC算法和CT算法相比，搜索次数和通信复杂度都进一步减少。

2.5.1 搜索次数

CT算法的搜索次数为2N-1次[11]；设阅读器接收数据中仅出现一个碰撞位的情况为H次，则RCC防碰撞算法的搜索次数为2N-2H-1次，次数少了2H次。

2.5.2 通信复杂度

由于阅读器仅发送查询前缀长度信息，标签仅返回碰撞位以后信息，阅读器和标签间的通信数据量大大减少。假设标签序列号长度为N，搜索前缀长度为L，则每个查询时隙中，CT算法的通信数据比特数为N，RCC算法的通信数据比特数为(lbL+N-L)，RCC算法相比CT算法每个查询时隙减少了(L- lbL)比特通信数据量。

2.6 算法仿真

为了检验和比较算法的性能，利用Matlab软件对算法进行了仿真。假设信道是理想的，标签ID的长度为128 b，标签数量在0～100之间变化，仿真100次取平均值，不计控制命令前缀、后缀及检验冗余等开销，对查询时隙和通信复杂度等指标进行仿真和比较。

2.6.1 总时隙数

图2为总时隙数对比图，由图可见，BS算法和DBS算法的总时隙数大致相同，具有最大的总时隙数；CT算法和RBS算法的总时隙数大致相同；所有算法中RCC算法的总时隙数最小。这是由于RCC算法通过标志寄存器和堆栈存取实现了返回式搜索，且在只有一个碰撞位时直接识别两个标签。

图2 总时隙数对比

2.6.2 单位时隙通信复杂度

图3为单位时隙通信复杂度对比图，即平均每个查询时隙阅读器和标签间数据通信比特数。由图可见，在每个查询时隙中，BS算法和RBS算法具有大致相同的通信复杂度，CT算法和DBS算法具有大致相同的通信复杂度，所有算法中RCC算法具有最小的通信复杂度。这是由于RCC算法中阅读器仅发送前缀长度信息，标签仅返回前缀以后比特信息，大大减少了数据通信量。

图3 单位时隙通信复杂度对比

2.6.3 总通信复杂度

图4为总通信复杂度即完成所有标签识别所需要的通信数据比特数对比。由图可见，BS算法具有最大的总通信复杂度。这是由于BS算法不仅具有最大的总时隙数，还具有最大的单位时隙通信复杂度。在标签数较大时，DBS算法比RBS算法具有更大的通信复杂度。这是由于DBS算法的总时隙数大于RBS算法，但单位时隙通信复杂度小于RBS算法，且随着标签数的增大，DBS算法总时隙数的增长斜率逐渐增大。所有算法中，RCC算法具有最小的总通信复杂度。

图4 总通信复杂度对比

由仿真结果可以看出，本文算法和传统二叉树搜索算法相比，阅读器和标签间的数据通信量更少，阅读器识别时间更快，因此，本文算法优于传统的二叉树搜索算法。

3 结 论

本文对现有的二叉树搜索算法进行了分析和比较，并提出了一个新的解决方案，在标签中设置前缀长度寄存器以便存储前缀长度信息，设置标志寄存器以便区分和搜索标签0子集和1子集，阅读器仅需发送前缀长度信息即可对标签进行分类搜索，同时，在阅读器设置堆栈存储区，按后进先出的原则存储标签前缀序列号长度信息，配合后退式算法进行标签搜索；在阅读器接收数据只有一个碰撞位时，直接识别两个标签。这些措施有效减少了二叉树算法中阅读器搜索标签的次数，减少了阅读器和标签间的数据通信量，减少了标签的能量消耗，减少了阅读器识别标签的时间，提高了阅读器搜索标签的效率。