基于伪ID码的树型防碰撞算法

王 帅,杨恒新,杨 华

(南京邮电大学 电子与光学工程学院,南京 210023)

0 概述

无线射频识别(Radio Frequency Identification,RFID)是一种远距离识别技术[1],它主要通过空间耦合技术使阅读器和标签进行远程通信[2-4]。随着5G时代的到来,物联网的应用将更加广泛,而作为物联网核心技术之一的RFID技术也引起了人们更多的关注[5]。

RFID系统主要由阅读器、标签、计算机组成[6]。计算机通过控制阅读器与标签进行通信。在RFID系统中最主要的问题就是标签碰撞问题。当阅读器的识别区域内同时出现大量未识别标签时,阅读器发出查询指令,所有未识别标签同时回应,此时会发生数据碰撞,导致阅读器无法对标签进行正常识别[7]。针对这一问题,人们提出基于时分多路(Time Division Multiple Access,TDMA)、频分多路(Frequency Division Multiple Access,FDMA)、空分多路(Space Division Multiple Access,SDMA)和码分多路(Code Division Multiple Access,CDMA)等4种方式的防碰撞算法[8-9],其中应用最多的是时分多路的防碰撞算法。

时分多路(TDMA)防碰撞算法中的典型算法主要分为基于ALOHA的概率型算法和基于树的概率型算法。基于ALOHA的概率型算法主要有帧时隙(FSA)算法和动态帧时隙(DFSA)算法等[10-11],ALOHA算法简单,但吞吐率都不高。基于树的概率型算法主要有动态二进制搜索(DBST)算法[12-13]和碰撞跟踪树(CTT)算法等[14-15]。树型算法虽然比较复杂,但吞吐率较ALOHA型算法高。文献[16]提出一种基于查询树(QT)算法的混合查询树(IHQT)算法,在查询标签碰撞时,增加一个分支预测阶段,虽然可以有效避免空闲时隙,但大大增加了系统的复杂度。文献[2]提出一种位屏蔽多叉树搜索的防碰撞算法,主要通过屏蔽寄存器将标签ID中的非碰撞位进行屏蔽,用碰撞位生成新的ID号,从而避免空闲时隙,减少数据通信量,但在大规模标签识别时,同样会有树的深度过深导致吞吐率下降的问题。文献[17]提出一种改进的搜索树防碰撞算法,在标签数量多时使用多叉树进行识别,标签数量少时使用二叉树进行识别。该方法虽然可以减少部分空闲时隙,但不能完全避免。

在树类算法中,CTT算法[18]虽然避免了空闲时隙,但由于在标签数量多的情况下查询树的深度过深,导致算法吞吐率下降。针对这一问题,本文提出一种基于伪ID码的树型防碰撞算法,主要通过伪ID码对标签进行划分,从而降低树的深度,提高算法的识别效率。

1 碰撞跟踪树算法

碰撞跟踪树(Collision Tracking Tree,CTT)算法的核心思想是在查询树(QT)算法的基础上,根据曼彻斯特码检测到的碰撞,将最高碰撞位之前的信息加上最高碰撞位置0或1组成新的查询前缀,从而可以避免空闲时隙。

以标签0110、0101、0111、1010、1000为例,其识别过程如图1所示。

图1 CTT算法流程Fig.1 CTT algorithm processdure

从图1可以看出,CTT算法在查询上述5个标签时,没有产生空闲时隙。

假设识别区域内未识别标签数为n,内部结点数为tc,叶结点数为ts,总时隙数为N,则:

N=2(tc+1)+1

(1)

N=ts+tc+1

(2)

由于CTT算法不会产生空闲时隙,因此:

n=ts

(3)

由式(1)～式(3)可得:

N=2n-1

(4)

因此,算法的吞吐率为:

(5)

从吞吐率公式可以看出,当标签数量越来越多时,算法的吞吐率越低,则标签的识别速度越慢。

2 树型防碰撞算法

针对CTT算法中随着标签数量越多,吞吐率越低的问题,本文提出了伪ID码的概念,其主要是将标签通过伪ID码进行重新划分,使每个伪ID码只有一个或几个标签,然后根据CTT算法进行识别,从而提高算法的识别效率。

2.1 伪ID码

每个标签在伪ID码的范围内进行随机选取,令伪ID码的个数为L,识别范围内未识别标签的数量为n,则在单个伪ID码中,有t个标签同时选中的概率为:

(6)

当t=0时,即单个伪ID码没有标签选中,称为空ID码,其概率为:

(7)

当t=1时,即单个伪ID码只有1个标签选中,称为成功ID码,其概率为:

(8)

当t≥2时,即单个伪ID码有多个标签选中,称为碰撞ID码,其概率为:

P(t≥2)=1-P(t=0)-P(t=1)

(9)

因此,在L个伪ID码中,空伪ID码的期望为:

(10)

成功伪ID码的期望为:

(11)

碰撞伪ID码的期望为:

e≥2=L-e0-e1

(12)

令:

(13)

对式(1)求导,取极值后得:

L≈n+1

(14)

即当上式成立时,伪ID码中成功ID码的数量最多,识别成功ID码,无需CTT算法,可以直接进行识别。

为计算方便,令L≈n,此时在碰撞位ID码中:

(15)

(16)

(17)

图2给出了标签数(n)取不同值时,碰撞位ID码中不同标签数量的概率(P)值。

图2 碰撞位的概率值Fig.2 Probability value of collision position

从图2可以看出,随着标签数量的增加,P(t=2)稳定在0.18,P(t=3)稳定在0.06,P(t=4)基本为0。因此,当L≈n时,每个伪ID码中最多包含3个标签,此时应用CTT算法,算法吞吐率最高。

2.2 标签数量预测

目前研究人员已经提出了多种标签数量预测方法,如Vogt算法、Chen’s算法、Vahedi’s算法、Q算法等[19-20]。上述算法计算都比较复杂,本文采取一种简单的基于泊松分布的标签数量预测方法为[21]:

n′=S+2.39×C

(18)

假设未识别标签数n′应用成功数S与碰撞数C的2.39倍之和来加以预测。

标签预测的具体步骤如下:

步骤1阅读器向识别区域内的所有标签发送Q,Q的初始值设为8。

步骤2标签在接收到Q值后,利用随机数生成器,在1～2Q中随机选择一个数,进行相应的短暂延时,然后向阅读器发送一个非常短的长度为2 bit的预约帧。

步骤4根据n′=S+2.39×C,计算出识别范围内标签的大概数量。

2.3 算法主体流程

算法首先由标签预测算法识别出识别范围内标签的大概数量,然后由伪ID码进行划分,如果识别过程中发生碰撞,就通过CTT算法进行识别,直到识别范围内的所有标签都识别完毕。

步骤1阅读器通过标签预测算法,得到识别区域内未识别标签的大概数量n。

步骤2阅读器向标签发送n。标签在接收到n后,利用随机数生成器随机产生1～n内的任意一个数作为自己的伪ID码,同时,阅读器设立初始值为0的变量i,变量i用于判断是否识别完所有的伪ID码。

步骤3若i≤n,则转到步骤4;否则,结束算法,所有标签识别完毕。

步骤4阅读器向标签发送i。标签在接收到i后,判断自己的伪ID码是否与i相等,如果相等则进行回应。

步骤5阅读器在相应的时间内判断是否有标签进行回应。若没有,则i=i+1,转到步骤3;否则继续执行步骤6。

步骤6阅读器判断标签回应的数据是否发送碰撞。若有则利用CTT算法进行识别,并向识别完成的标签发送静默指令;否则直接识别回应的标签,识别完成后,向其发送静默指令。最后执行i=i+1,转到步骤3。

算法流程如图3所示。

图3 树型防碰撞算法主体流程Fig.3 Main procedure of the tree auti-collision algorithm

3 性能分析

3.1 阅读器查询次数分析

在算法实现过程中,阅读器主要通过伪ID码和碰撞时的CTT算法进行查询,则阅读器总查询次数Q的表达式为:

Q=QID+QCTT

(19)

若ID码的个数为L,则:

QID=L

(20)

由式(4)可知,CTT算法的查询次数为N=2n-1。但是在本文算法中,由于在发送碰撞时,已经检测出了碰撞位,因此本文算法中CTT算法的实际查询次数为N=2n-2。

本文算法中CTT算法的总查询次数为:

QCTT=L×P(t=2)×(2×2-2)+L×P(t=3)×

(2×3-3)+L×P(t=4)×(2×4-3)

(21)

在式(21)中,本应计算P(t=5)、P(t=6)等,但因为其值太小,同时为了书写方便,将其省略。

将式(20)、式(21)代入式(19),得:

Q=L+L×P(t=2)×2+L×P(t=3)×3+L×P(t=4)×5

(22)

同时,每个标签的平均查询次数为:

(23)

3.2 吞吐率分析

算法的吞吐率S的表达式为:

(24)

4 仿真结果与分析

本文将改进算法、CTT算法、QT算法在吞吐率、阅读器总查询次数、标签平均查询次数3个方面进行比较,算法仿真在Matlab平台上进行运行。采用蒙特卡洛仿真方法进行仿真,仿真参数如表1所示。算法仿真结果如图4～图6所示。

表1 仿真参数设置Table 1 Simulation parameter settings

图4 3种算法阅读器总查询次数比较Fig.4 Comparison of total query number of readersof three algorithms

图5 3种算法标签平均查询次数比较Fig.5 Comparison of average query number of tagsof three algorithms

图6 3种算法吞吐率比较Fig.6 Comparison of throughput rates of three algorithms

图4是3种算法的阅读器总查询次数的比较结果。在同样标签数的情况下,本文改进算法所需的总查询次数最少,QT算法的总查询次数最多。这是因为CTT算法在QT算法的基础上引入了曼彻斯特码碰撞检测,消除了空闲时隙,而本文改进算法则利用伪ID码机制,避免了CTT生成树过深的问题,进一步减少了查询次数。但标签数量为1 000时,QT算法的总查询次数为3 110,CTT算法的总查询次数为2 013,改进算法的总查询次数为1 684,因此改进算法的总查询次数相比CTT算法、QT算法分别减少了16%和45%。

图5是3种算法的标签平均查询次数的比较结果。QT算法随着标签数量的增加,其平均查询次数逐渐减少,逐渐稳定在2.9左右,而CTT算法由于避免了空闲时隙,一直平稳在2.0上,改进算法由于减少了树的深度,其标签的平均查询次数,随着标签数的增多,也一直维持在1.65上。因此,改进算法的标签平均查询次数相比CTT算法、QT算法分别减少了17%和43%。

图6是3种算法的吞吐率比较结果。由图6可见,改进算法的吞吐率比CTT算法、QT算法的吞吐率都要高。改进算法的吞吐率主要维持在0.575,CTT算法的吞吐率主要维持在0.5,而QT算法的吞吐率主要维持在0.33左右。因此,改进算法的吞吐率相比于CTT算法、QT算法分别提高了15%和74%。

5 结束语

本文在CTT算法的基础上提出一种基于伪ID码的树型防碰撞算法。利用伪ID划分未识别标签,然后运用CTT算法进行识别。通过该方法可以将树型算法查询标签的数量控制在3个以内,虽然伪ID码会产生部分空闲时隙,但在成功时隙中可以直接识别标签,而不需要利用树型算法进行查询,降低了算法的复杂度。仿真结果表明,改进算法在总查询次数、标签平均查询次数和吞吐率方面均优于CTT算法和QT算法。在实际应用过程中,可以大致预测出阅读器识别范围内的未识别标签数量,因此本文算法具备实际的应用价值。