射频识别(Radio Frequency IDentification, RFID)是一种非接触式自动识别技术,在一个多标签的RFID系统中,由于标签和阅读器共用一个信道,当多个标签同时向阅读器发送数据时,就会发生数据碰撞,导致阅读器不能正确识别标签[1]。由于标签的能量低、处理能力弱、存储空间有限、没有数据侦测能力,很多传统的防碰撞算法都不适用于RFID[2]。现阶段的RFID防碰撞算法通常都是基于时分多址的方法,主要有基于ALOHA的不确定性算法和基于搜索树的确定性算法[3]。
ALOHA算法主要有:时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法等[4],这些算法相对比较简单,但随着标签数量的增大,其性能迅速恶化。为了改善其性能,有学者在此基础上提出了增强型动态帧时隙ALOHA算法[5]、分组动态帧时隙ALOHA算法[6]、分组自适应分配时隙ALOHA算法[7]等,其性能有所改善,但仍存在随机性大、性能不稳定、吞吐率低、效率不高等问题,且存在由于标签在长时间内不能被识别而导致的“饥饿”问题。
搜索数算法是确定性算法,不存在标签“饥饿”问题,主要有:二进制搜索树(Binary Search, BS)算法、后退式二进制搜索树(Regressive Binary Search, RBS)算法、动态二进制搜索树(Dynamic Binary Search, DBS)算法[8]等。BS算法是最基本的二进制搜索算法,RBS算法相对BS算法减少了搜索次数,DBS算法相对于BS算法则减少了冗余传输。在标签较多时,这些算法存在数据传输量大、搜索次数多等问题,对此,学者们又作了进一步的改进:文献[9]中提出一种四叉树搜索算法,根据碰撞位进行四叉树搜索,减少了搜索次数,但增加了空闲时隙;文献[10]中提出一种改进的多叉树搜索算法,根据碰撞位的不同来动态选择二叉树搜索或四叉树搜索,但并没有消除搜索过程中的空闲时隙;文献[11]对此作了改进,提出IAMS(Improved Adaptive Multi-tree Search)算法,通过碰撞因子来动态选择二进制或四进制搜索,同时,在四叉树时,通过查询最高两个碰撞位信息来消除空闲时隙,但却增加了查询时隙;文献[12]中提出一种增强型多叉树搜索算法——EBST(Enhanced RFID anti-collision algorithm Based on Search Tree)算法,根据相邻碰撞位的个数,通过查询搜索前缀命令,动态选择二叉树搜索、四叉树搜索或八叉树搜索,虽消除了空闲时隙,但还是增加了查询时隙,仍有较大的系统通信量。这些算法或多或少都存在算法较复杂、对标签处理能力要求较高、增加了空闲时隙或查询时隙等问题。
文献[13]中提出一种基于转换码的双时隙RFID搜索算法,这种算法仅在有连续三个碰撞位时为双时隙发送,其他情况则根据碰撞位情况采用二叉树或四叉树方法搜索,仍为单时隙发送,这种算法既没消除空闲时隙,又增加了查询时隙,系统性能提高有限。
综合ALOHA算法和搜索树算法的优点,本文提出了一种新的算法:计数型双时隙搜索(Counter and Bi-Slot Search, CBS)算法。CBS算法在每一次搜索中进行确定性的双时隙数据发送,不增加查询时隙,完全避免空闲时隙,能够大幅度减少标签搜索次数,提高搜索效率。
1 计数型双时隙防碰撞算法CBS算法在标签中仅设置一个时隙计数器,根据阅读器命令进行加减计数;同时,在阅读器中设置一个堆栈和一个控制寄存器,阅读器根据碰撞位信息、控制寄存器和堆栈数据信息发出请求命令,标签收到阅读器命令后,首先更新时隙计数器,确定哪些标签需要向阅读器返回数据,在哪个时隙向阅读器返回数据。
时隙计数器可以通过在标签中改变硬件电路来实现,也可以通过软件编程来实现。
时隙计数器的作用主要有:1) 确定应答标签范围,计数值为0和1的标签为应答标签。在本文中,应答标签的含义是指能够响应阅读器命令并需向阅读器返回数据的标签。2) 确定哪些标签在时隙1发送数据,哪些标签在时隙2发送数据:时隙计数器更新后,计数值为0的标签在时隙1发送数据,计数值为1的标签在时隙2发送数据。3) 减少阅读器和标签间收发数据的比特数。
阅读器堆栈和控制寄存器可确定阅读器请求命令参数,具体方法在下面的命令规则和算法步骤中进行详细讲解。
在以下论述中,假设标签ID的长度为L, 按位表示为:(L-1, …, 1, 0)。
1.1 命令规则为了便于描述算法,引入以下阅读器命令。
1) request(null):阅读器首次搜索请求命令,所有标签分两步执行命令:① 时隙计数器初始化,第L-1位为0的标签计数值为0,第L-1位为1的标签计数值为1;② 返回数据,计数值为0的标签在时隙1返回数据给阅读器,计数值为1的标签在时隙2返回数据给阅读器。
2) request(X,H):阅读器请求命令,其中X为两位二进制数。标签分两步执行命令:① 更新时隙计数器;② 返回数据,计数值为0的标签在时隙1返回数据给阅读器,计数值为1的标签在时隙2返回数据给阅读器。
更新时隙计数器的方法:
若X=00:计数值为0第H位为0的标签计数值不变,其余标签(计数值为0第H位为1的标签, 计数值大于0的标签)计数值加1;
若X=01:计数值为0第H位为1的标签计数值更新为1,其余标签计数值不变;
若X=10:计数值为1第H位为0的标签计数值更新为0,其余标签计数值不变;
若X=11:首先,所有标签计数值减1,然后计数值为1第H位为0的标签计数值更新为0。
1.2 算法原理每个标签都有两个时隙,阅读器根据碰撞位信息进行分类搜索,应答标签分为两组,计数值为0的一组在时隙1返回数据,计数值为1的一组在时隙2返回数据。
时隙按碰撞位情况可以分为识别时隙和冲突时隙。识别时隙分两种情况:一种情况是无碰撞位,则识别一个标签;一种情况是只有一个碰撞位,则直接识别两个标签。有两个或两个以上碰撞位的时隙为冲突时隙。
阅读器设堆栈,按先入后出的规则存取数据。
阅读器设置控制寄存器X,X是长度为两位的二进制数,初始值为00。当时隙1为冲突时隙,则X高位为0;当时隙1为识别时隙,则X高位为1。当时隙2为冲突时隙,则X低位为0;当时隙2为识别时隙,则X低位为1。
1) 阅读器初始化堆栈为空, 阅读器发送请求命令request(null)。
2) 所有标签响应命令,首先,初始化标签时隙计数器;接着,标签返回数据,计数值为0的标签在时隙1发送ID的L-2~0位数据给阅读器;计数值为1的标签在时隙2发送ID的L-2~0位数据给阅读器。
3) 阅读器在两个时隙接收数据,分以下四种情况:
① 两个时隙都为识别时隙:更新控制寄存器,X=11,转至步骤5)。
② 时隙1为识别时隙,时隙2为冲突时隙:更新控制寄存器,X=10;设时隙2最高碰撞位为H, 把H压入堆栈,转至步骤5)。
③ 时隙1为冲突时隙,时隙2为识别时隙:更新控制寄存器,X=01;设时隙1最高碰撞位为H, 把H压入堆栈。转至步骤5)。
④ 两个时隙都为冲突时隙:更新控制寄存器,X=00;设时隙1最高碰撞位为H, 阅读器发出请求命令request(00,H);设时隙2最高碰撞位为H′, 把H′压入堆栈。
4) 所有标签更新计数值后,计数值为0的标签在时隙1返回ID的H-1~0位数据给阅读器,计数值为1的标签在时隙2返回ID的H-1~0位数据给阅读器,转至步骤3)。
5) 阅读器选中已识别标签,读取标签数据,令标签为休眠态,休眠态标签不再响应阅读器命令。阅读器判定堆栈是否为空,若堆栈为空,搜索结束;若堆栈不为空,弹出堆栈数据,设为H, 若控制寄存器为X,则阅读器发出请求命令request(X,H)。
1.3 算法举例下面通过具体例子来说明RFID双时隙防碰撞算法搜索过程,假设阅读器作用范围内有8个标签,它们的ID号长度都为10 bit,分别为:A:0010110001,B:1010101010,C:0001110110,D:0001101011,E:0001100011,F:1101110001,G:1101010001, H:1010001010。搜索过程如表 1所示。其中的阅读器请求命令比特数是指阅读器请求命令参数的数据比特数,阅读器接收数据比特数即标签发送数据比特数。
第1次搜索:标签A、C、D、E时隙计数器计数值初始化为0,并在时隙1响应,标签B、F、G、H时隙计数器计数值初始化为1,并在时隙2响应,两个时隙都为冲突时隙;第2次搜索:标签C、D、E时隙计数器计数值仍为0,并在时隙1响应,标签A时隙计数器计数值更新为1,并在时隙2响应,时隙1为冲突时隙,时隙2无碰撞位,识别标签A;第3次搜索:标签D、E时隙计数器计数值仍为0,并在时隙1响应,标签C时隙计数器计数值更新为1,并在时隙2响应,时隙1只有1个碰撞位,识别标签D、E,时隙2无碰撞位,识别标签C;第4次搜索:标签B、H时隙计数器计数值更新为0,并在时隙1响应,标签F、G时隙计数器计数值更新为1,并在时隙2响应,时隙1只有一个碰撞位,识别标签B、H, 时隙2也只有一个碰撞位,识别标签F、G。
CBS算法搜索树如图 1所示。由图 1可见,每次搜索都有两个时隙,提高了搜索效率,搜索顺序是先搜索子集0标签,再返回搜索子集1标签。
CBS算法具有较小的搜索次数和通信数据比特数,以上述的8个标签为例,对IAMS算法、EBST算法和本文的CBS算法进行对比分析。
CBS算法的搜索次数为4,时隙1标签发送数据比特数为:9+7+4+8=28, 时隙2标签发送数据比特数也为28, 阅读器发送数据比特数为:5+4+5=14, 通信总比特数为:28+28+14=70。
IAMS算法是比较新的一种防碰撞方法,表 2是IAMS算法的搜索过程,其中“比特数”这一列的数据中“|”前面的数字表示阅读器发送数据比特数,后面的数字表示标签发送数据比特数。
IAMS算法根据碰撞因子来决定叉树,碰撞因子小于0.75用二叉树搜索,碰撞因子大于或等于0.75用四叉树搜索,由表 2可见,只有第1次搜索碰撞因子大于0.75,整个搜索过程只有一次四叉树搜索,其他都是二叉树搜索,其搜索次数为15,远大于CBS算法。
通信复杂度是指阅读器和标签间通信的数据比特数,IAMS算法阅读器发送数据总比特数为63,标签发送数据总比特数为144, 总的数据通信比特数为207,远大于CBS算法。
EBST算法在IAMS算法的基础上作了改进,表 3是EBST算法的搜索过程,其中“比特数”这一列的数据中“|”前面的数字表示阅读器发送数据比特数,后面的数字表示标签发送数据比特数。
EBST算法根据连续碰撞的位数来确定叉树,当连续3位或3位以上碰撞时,选择八叉树搜索;当仅连续两位碰撞时,选择四叉树搜索;当仅单独位碰撞时,选择二叉树搜索。在八叉树或四叉树搜索时,需要先查询碰撞前缀,其总搜索次数为14,略小于IAMS算法,远大于CBS算法。
EBST算法在3个连续碰撞位进行前缀查询时,其返回数据可能不足4,但阅读器接收数据仍按4 bit数据来处理,所以在此仍按4 bit来计算阅读器接收数据比特数。EBST算法阅读器发送数据总比特数为73, 标签发送数据总比特数为128,总的数据通信比特数为201,略小于IAMS算法,远大于CBS算法。
需要说明的是,虽是举例,但并没有特殊性,任意ID序列号的几个标签来比较,结果都大致相同。
CBS算法中涉及到的数据比较和标签分组,由于标签内有微处理器和存储器,可以通过软件编程来实现。
3 算法分析本文算法是确定性算法,能确保搜索并识别每一个标签,性能稳定可靠;相比传统的BS算法和RBS等算法,其搜索次数大大减少,通信复杂度大大降低;相比新近提出的IAMS算法和EBST算法,其搜索次数和通信复杂度也有很大改善。
3.1 搜索次数分析搜索次数是衡量RFID性能优劣的一个重要指标,本文算法搜索过程为二叉树搜索,根据二叉树搜索法的性质,对于任意一个二叉树,度为2的节点总比度为0的节点少一个,本文算法中,每一个度为2的节点对应一次搜索,度为0的节点对应标签的个数,设标签的个数为N, 则搜索次数为C′(N)为:
$ C'\left( N \right) = N - 1 $ | (1) |
再考虑只有一个碰撞位的情况,假设只有一个碰撞位的情况出现了P次,由于这种情况下直接识别两个标签,对应一个节点,所以CBS算法中,总的搜索次数C(N)为:
$ C(N) = N - P - 1 $ | (2) |
RBS算法搜索次数远小于BS算法,搜索次数为2N-1;但和CBS算法相比,RBS算法搜索次数又远多于CBS算法,相比RBS算法,CBS算法搜索次数减少了一半以上。
由式(2) 可看出,P越大,C(N)越小,当所有识别节点都仅一个碰撞位时,P最大,由于两个识别标签对应一个识别节点,则P的最大值为N/2, 这种极端情况下,总搜索次数最少:
$ C{(N)_{{\rm{MIN}}}} = N - P - 1 = N - \frac{N}{2} - 1 = \frac{N}{2} - 1 $ | (3) |
通信复杂度是指在完成标签搜索过程中,阅读器和标签间通信的数据比特数,较小的通信复杂度能减少标签的耗能,并提高搜索的速率。
CBS算法中,通信复杂度和最高碰撞位有关,假设标签ID长度为L,在第K次搜索中, 最高碰撞位为第HK位,很明显,0≤HK≤L-1, 忽略控制命令本身比特数,第K次搜索通信总比特数为:阅读器发送参数比特数+时隙1标签返回数据比特数+时隙2标签返回数据比特数。在CBS算法中,时隙1标签返回数据比特数和时隙2标签返回数据比特数相等,设为TK2,阅读器发送参数比特数设为TK1,则有:
$ {T_{K1}} = \left\lceil {{\rm{lb}}\;{H_K}} \right\rceil $ | (4) |
其中
$ {T_{K2}} = {H_K} $ | (5) |
则第K次搜索通信数据量为:
$ {T_K} = {T_{K1}} + 2{T_{K2}} = \left\lceil {{\rm{lb}}\;{H_K}} \right\rceil + 2{H_K} $ | (6) |
本文CBS算法总的通信数据比特数为:
$ T = \sum\limits_{i = 1}^{N - P - 1} {\left\lceil {{\rm{lb}}\;{H_K}} \right\rceil + 2\sum\limits_{i = 1}^{N - P - 1} {{H_K};0 \le {H_K}} \le L - 1} $ | (7) |
可见,总的搜索次数一定小于N,通信总数据比特数仅和每次搜索的最高碰撞位位置有关,每次搜索的数据比特数一般小于2L。
RBS算法通信数据比特数少于BS算法,通信数据比特数为2L(2N-1);但和CBS算法相比,RBS算法通信数据比特数又大于CBS算法。
实际的RFID系统中,阅读器和标签间的通信还包括控制命令的开销,由于本文算法搜索次数很少,减少了不少控制命令开销,实际应用中,更能显出算法低通信复杂度的优势。
4 算法仿真与分析前面通过理论分析得到了CBS算法的搜索次数和通信数据比特数,下面利用Matlab进行仿真,并与BS算法、RBS算法、IAMS算法和EBST算法进行对比。假设标签ID长度为96 bit, 阅读器和标签控制命令本身长度固定为10 bit。
图 2是几种算法的搜索次数比较。由图 2可见,CBS算法搜索次数远小于其他算法,标签数量越大,优势越明显,这是由于CBS算法在每次搜索过程中,都有两个时隙发送数据,一次搜索最多可以识别4个标签,大大提高了搜索的效率;和RBS算法相比,本文CBS算法搜索次数减少了一半以上;IAMS算法和EBST算法虽减少了空闲时隙,但却增加了查询高碰撞位的时隙,搜索次数仍远大于本文CBS算法。
图 3是几种算法的通信复杂度比较。由图 3可见,CBS算法通信比特数小于IAMS算法和EBST算法,更远小于DBS算法和RBS算法,IAMS算法和EBST算法都耗费了大量的查询高碰撞位的数据比特数,实际上,按这类算法的原理,分叉越多,耗费的查询比特数就越多,所以IAMS算法和EBST算法仍有较高的通信数据量。CBS算法在几个方面减少了通信比特数:一个是搜索次数最少,阅读器和标签控制命令本身耗费的数据比特数减少;另一个是采用了时隙计数器配合进行搜索,阅读器只需发送最高碰撞位的位置信息,标签只需要返回最高碰撞位以后的信息;再有就是当只有一个碰撞位时直接识别两个标签。正是由于这些措施和方法,使CBS算法通信数据比特数这一指标优于其他对比算法。
本文在搜索树防碰撞算法的基础上,借鉴ALOHA算法时隙的思想,提出了一种新的防碰撞算法——CBS算法。该算法通过时隙计数器,对标签进行逐级搜索,每次搜索中,应答标签分为两组,分别在两个时隙返回数据给阅读器,大大减少了搜索次数;同时,阅读器只发送最高碰撞位位置信息,标签只返回最高碰撞位以后的ID号,当只有一个碰撞位时,直接识别两个标签,大大减少了系统通信数据量。
由于标签的能量有限,处理能力弱,标签的算法应当尽量简单,而阅读器不存在严苛的能量问题和体积问题,可以适应比较复杂的算法。计数型双时隙防碰撞算法对此作了充分考虑,是一个符合标签实际的实用的算法。
无论是IAMS算法还是EBST算法,标签处理过程都相对比较复杂;CBS算法尽量把复杂算法让阅读器来处理,标签处理过程相对简单,耗能更小,易于实现,便于RFID系统的实际应用,是一种很有应用前景的防碰撞算法。
[1] | 王心妍, 杨博. 基于多进制查询树的多标签识别方法[J]. 计算机工程, 2015, 41(8): 95-99. (WANG X Y, YANG B. Multi-tag identification method based on multi-ary query tree[J]. Computer Engineering, 2015, 41(8): 95-99.) |
[2] | 王勇, 唐小虎, 张莉涓, 等. 基于鲁棒估计的最大前缀RFID防碰撞算法[J]. 计算机工程, 2015, 41(2): 303-307. (WANG Y, TANG X H, ZHANG L J, et al. Maximized prefix anti-collision algorithm for RFID based on robust estimation[J]. Computer Engineering, 2015, 41(2): 303-307.) |
[3] | 付钰, 钱志鸿, 孟婕, 等. 基于连续时隙预测的帧时隙Aloha防碰撞算法[J]. 电子学报, 2016, 44(9): 2081-2086. (FU Y, QIAN Z H, MENG J, et al. FSA anti-collision algorithm based on continuous slot prediction[J]. Acta Electronica Sinica, 2016, 44(9): 2081-2086.) |
[4] | 张小红, 张留洋. 无源RIFD自适应帧时隙防碰撞算法研究[J]. 电子学报, 2016, 44(9): 2211-2218. (ZHANG X H, ZHANG L Y. Research on passive RFID system adaptive frame slot anti-collision algorithm[J]. Acta Electronica Sinica, 2016, 44(9): 2211-2218.) |
[5] | WANG C-Y, LEE C-C, LEE M-C. An enhanced dynamic framed slotted ALOHA anti-collision method for mobile RFID tag identification[J]. Journal of Convergence Information Technology, 2011, 6(4): 340-351. DOI:10.4156/jcit |
[6] | LIN C-F, LIN F Y-S. Efficient estimation and collision-group-based anti-collision algorithms for dynamic framed-slotted ALOHA in RFID networks[J]. IEEE Transactions on Automation Science and Engineering, 2010, 7(4): 840-848. DOI:10.1109/TASE.2010.2042806 |
[7] | 张小红, 胡应梦. 分组自适应分配时隙的RFID防碰撞算法研究[J]. 电子学报, 2016, 44(6): 1328-1335. (ZHANG X H, HU Y M. Research on a grouped adaptive allocating slot anti-collision algorithm in RFID system[J]. Acta Electronica Sinica, 2016, 44(6): 1328-1335.) |
[8] | 薛建彬, 王文华, 张婷, 等. 基于计数机制的多状态二进制搜索防碰撞算法[J]. 计算机工程, 2013, 39(4): 309-313. (XUE J B, WANG W H, ZAHNG T, et al. Multi-state binary search anti-collision algorithm based on counting mechanism[J]. Computer Engineering, 2013, 39(4): 309-313.) |
[9] | 李宝山, 乔聪. 改进的二进制搜索防冲突算法[J]. 微电子学与计算机, 2014, 31(5): 94-97. (LI B S, QIAO C. An improved binary search anti-collision algorithm[J]. Microelectronics & Computer, 2014, 31(5): 94-97.) |
[10] | 林伟, 李景霞, 叶林锋. 基于多叉树搜索算法改进的RFID防碰撞算法[J]. 电子技术应用, 2013, 39(2): 130-133. (LIN W, LI J X, YE L F. An improved anti-collision algorithm based on multi-tree search in RFID[J]. Application of Electronic Technique, 2013, 39(2): 130-133.) |
[11] | 张学军, 蔡文琦, 王锁萍. 改进型自适应多叉树防碰撞算法研究[J]. 电子学报, 2012, 40(1): 193-198. (ZHANG X J, CAI W Q, WANG S P. One anti-collision algorithm based on improved adaptive multi-tree search[J]. Acta Electronica Sinica, 2012, 40(1): 193-198.) |
[12] | 韦冬雪, 郑嘉利, 黄庆欢, 等. 基于搜索树的增强型RFID防碰撞算法[J]. 计算机应用与软件, 2015, 32(11): 226-231. (WEI D X, ZHENG J L, HUANG Q H, et al. An enhanced RFID anti-collision algorithm based on search tree[J]. Computer Applications and Software, 2015, 32(11): 226-231. DOI:10.3969/j.issn.1000-386x.2015.11.053) |
[13] | 孙耀磊, 吴晓波, 陈元文, 等. 基于转换码的双时隙RFID防碰撞算法[J]. 自动化与仪器仪表, 2014(2): 134-136, 139. (SUN Y L, WU X B, CHEN Y W, et al. A bi-slot RFID anti-collision algorithm based on convertion code[J]. Automation and Instrumentation, 2014(2): 134-136, 139.) |