基于锁位的奇偶分区二进制树算法

汤宏斌，周尚波

(1.重庆第二师范学院 数学与信息工程系，重庆 400067；2.重庆大学 计算机学院，重庆 400044)

基于锁位的奇偶分区二进制树算法

汤宏斌1，2，周尚波2

(1.重庆第二师范学院 数学与信息工程系，重庆 400067；2.重庆大学 计算机学院，重庆 400044)

无线射频识别(radio frequency identification, RFID)是物联网的技术核心，防碰撞技术则是FRID必须面对的问题，针对二进制树算法时延较长，寻呼次数过多，效率低下的特点，在现有改进的二进制树算法基础上，提出一种奇偶区域锁位的二进制树算法。通过将寻呼区域划分为奇偶2个区域，并进行分区搜索，在每个搜索周期内，自动识别1位或2位碰撞标签，减少了寻呼次数，以提高搜索效率；采取增加锁位寻呼指令，将标签的应答位数限制在只传送发生碰撞的比特上，由于每次寻呼的时候，已经检测出的比特位无需再传输，可以减少总的传输比特数量，大大降低了传输时延，理论分析和仿真结果都表明该算法的有效性和优越性。

无线射频识别；奇偶区域； 锁位；防碰撞 ；二进制树

0 引 言

无线射频识别(radio frequency identification, RFID)技术在多标签识别中的关键是防碰撞问题。目前，常用的防碰撞算法都是基于时分多路(time division multiple access, TDMA)算法，防碰撞算法可根据标签的响应方式不同分为 ALOHA算法和二进制树算法2种。ALOHA算法有个致命的缺点是：标签有可能出现不被识别的情况[1-4]，二进制树算法可以全部识别标签，但缺点是识别周期较长[5-6]。

基本二进制树(binary search, BS)的防碰撞机制是以标签序列编号UID(ubiquitous identification)的唯一性为基础。第一次寻呼时，阅读器发出全1的查询指令，所有标签都做出响应，若只有一个标签，则无碰撞；若有多个标签，则肯定会发生碰撞，阅读器再次寻呼时，将碰撞最高位置0，高于此位的不变，低于此位的置1，以此方式来缩小响应标签的范围，不断迭代，直至识别到一个标签。之后，以类似的方法识别下一个标签，直至识别完所有标签[7]。

有多种改进的二进制树算法，典型的有动态二进制树算法(dynamic binary search, DBS)，它克服了基本二进制树算法ID不能太长的限制、时延大、信道利用率低等缺点，当阅读器检测到冲突时，下一次的Request命令，只发送没有冲突的高位信号，这样减少了传输数据量，提高了传输效率[8]。后退式二进制树搜索算法(regressive binary search, RBS)，每次识别一个标签后不用回到根节点，而是根据记忆退回到父节点，相比于BS算法，减少了搜索的冗余次数[9]。修剪枝二进制树搜索算法(pruning binary search,PBS)要求阅读器发送命令时，作用区域内的所有标签都应答，阅读器根据返回的信息识别出是空闲时隙、碰撞时隙还是有效时隙。检测为空闲时隙时，剪掉对应的子树；为碰撞时隙时，将请求指令延伸到下一个子树；为有效时隙，读出相应的标签。这种算法适合UID较长、标签数量多的情况，缺点是实现较困难[10]。锁位后退防碰撞(bit-locking back off, BLBO)算法通过锁定碰撞位，可以减少标签返回应答的位数，缺点是应答次数并没有多少改进[11]。自适应二叉树搜索算法(adaptive binary search, ABS)要求每个标签拥有一个计数器，用来记录当前的UID比较位,阅读器发送某个比较位，只有相一致的标签才响应，并将下一位发送给阅读器，并更新计数器。阅读器根据收到的UID，判断时隙为空闲、碰撞还是有效，而自适应地识别标签。该算法不仅搜索效率低，而且因为增加了计数器而增加了标签的成本[12]。其他如[13]提出奇偶分区的搜索算法，即将搜索区域分为奇数区域和偶数区域，来减少搜索次数。[14]利用2个比特数组代替栈队列，每个比特数组的大小不依赖于标签数量，减小了存储空间，提高了吞吐率。[15]是一种锁位算法，每次寻呼，只传输锁定的冲突位，来降低传输时延。

上述各种算法相对于基本的二进制树算法，在性能上都有较大的提高，我们在此基础上，提出一种改进的奇偶区域锁位算法。该算法运用奇偶分区的方法，减少了寻呼次数；采用锁位的方法，使得标签在应答时不需要传输完整的UID，减少了传输时延。理论分析和仿真结果表明，该算法能够有效地解决标签的碰撞问题，并实现标签的快速、高效地读取。

1 奇偶区域锁位算法

1.1 算法约定和相关指令

为了识别碰撞的位置，一般对标签返回的信号采用Manchester编码，即通过电平变化的上下沿来表示数值位，若无状态跳变，视为非法数据，作为冲突被识别。

这里需要重新设计寻呼命令如下。

1)REUEST(UID)：请求(序列号)；

2)SELECT(UID)：选择(序列号)；

3)READ_DATA：读出数据；

4)REQUEST_E(UID，0)：标签各位之和为偶数的锁位寻呼。UID的取值约定为：阅读器发送偶数区冲突请求信号，阅读器根据收到的信号判断碰撞的bit位，将碰撞位置1，非碰撞位置0，作为新的锁位寻呼指令。电子标签对锁位指令的响应为：偶数区域标签在接到锁位命令后，将自己的UID和锁位命令进行比较，标签只需关注锁位命令中1对应的位，与1对应的最高位为0的标签响应，并将余下的几位返回给阅读器。如锁位命令有p位为1，则标签只需返回p-1位；

5)REQUEST_O(UID，0)：标签各位之和为奇数的锁位寻呼。约定与REQUEST_E(UID，0)类似，只不过将偶数区域改为奇数区域。

1.2 算法原理和流程

图1是奇偶区域锁位算法的流程图，该流程分2大部分。首先在偶区域执行锁位算法，再在奇区域执行锁位算法，因为奇区域与偶区域类似，图1中将其省略，只保留初始和结束框。

算法步骤描述如下。

1)阅读器发送REQUEST_E(111…111)指令，所有UID码值之和为偶数的标签对此指令响应，发送自己的UID码。

2)阅读器如若没有检测到信号，则转到步骤6)，否则转到步骤3)。

3)阅读器对所有响应的信号进行译码，判断有无碰撞发生，若无碰撞则阅读器发送SELECT和READ_DATA指令，选择此标签进行读写，再发送UNSELECT指令，使之睡眠；如果有碰撞，则转到步骤4)。

4)将发生碰撞的比特位置“1”，未发生碰撞的比特位置“0”。阅读器发出REQUEST_E(UID,0)指令，偶数区域的标签接到命令之后将自己的ID与UID进行比较，锁定发生碰撞的比特位，锁定的最高位为“0”的标签对此指令做出响应，并将锁定的剩余比特发送给阅读器。如没有碰撞，则发送SELECT和READ_DATA指令选择和读取标签，然后发送UNSELECT指令让其休眠。若有碰撞，阅读器需再次对其译码，以此迭代，重复上述动作，直到读取某个标签，再采用回退策略，返回到上一个父碰撞节点。同样的方法识别此节点的另一个分支。以此递归，直到识别出锁定最高比特位为“0”分支的所有标签。转到步骤5)。

图1 奇偶区域锁位算法流程Fig.1 Flow chart of the proposed method.

5)阅读器发送REQUEST_E(UID,1)指令，偶数区域锁定的最高位为“1”的标签对此指令做出响应，将自己锁定的剩余比特位发送给阅读器。如没有碰撞，则发送SELECT和READ_DATA指令选择和读取标签，然后发送UNSELECT指令让其休眠。若有碰撞，阅读器需再次对其译码，判断碰撞的准确比特位，重复上述动作，直到读取某个标签，再采用回退策略，返回到上一个碰撞节点，识别此节点的另一个分支。以此递归，直到识别出锁定最高比特位为“1”分支的所有标签。

6)识别完偶数区域，再用同样的方法识别奇数区域，直到所有的标签被识别出来。

2 算法性能分析

2.1 阅读器的寻呼次数

阅读器从第一次问询到识别出所有标签，共询问的次数即为寻呼次数。锁位后退防碰撞算法中，寻呼区内若有n个标签，则寻呼次数Q(n)[11]为Q(n)=2n-1

设奇区域和偶区域的标签个数分别为p和q，则总的寻呼次数为

Q(n)=Q(p)+Q(q)=(2p-1)+(2q-1)=

2(p+q)-2=2n-2

为了防止遗漏，即使奇区域(或偶区域)有0个标签，仍然要寻呼一次，此时，

Q(n)=Q(p)+Q(q)=1+(2q-1)=2q=2n

这种情况出现的概率为1/2n-1，故整体寻呼次数的概率为

Q(n)=2n×1/2n-1+(2n-2)×(1-1/2n-1)

(1)

(2)

很明显，当标签长度k和标签数n一定，碰撞位数x=2比x=1时的概率要大。这意味着在实际应用中，采用奇偶区域锁位算法要比(1)式的寻呼次数还要少。

2.2 传输时延

因为阅读器对相关命令的处理时间要远小于命令的传输时间，故一般分析RFID主要考虑传输时延[16]。传输时延是指阅读器发送询问指令到全部接受标签应答之间的时间。对于特定的系统，阅读器与标签间的传输速率恒定，传输时延就取决于寻呼次数及每次传输的数据长度，单位为bit。

阅读器的请求命令和标签的应答命令作为数据帧，其首尾都有5个bit的空闲时间。阅读器在接受标签应答数据时，还需要多花1 bit的校验时间。阅读器记录返回响应的目标标签的ID需要2 bit时间。在识别了一个标签后，为使其进入休眠状态，阅读器要发送一个带该标签ID的UNSELECT指令，使其进入休眠状态。

若阅读器的工作范围内有n个标签，标签ID的长度为kbit，碰撞位有ybit。则阅读器和标签一次通信所需要的时间L0为：L0=2k+21；第2次锁位指令需要k+y+21比特时间；如果通信没有遇到碰撞，还需要2比特时间用来登记标签ID信息。需要经历L0=y+23比特时间，故二进制锁位算法[11]需要传输的所有比特长度L为

(3)

而奇偶区域锁位算法中，询问指令需要增加一位区分奇偶区域，故奇偶区域锁位算法总比特时间的均值为

从两者之差可以看出，当2n+k>y时，只用二进制锁位算法占优；反之，奇偶区域二进制锁位算法占优。其实，(4)式没有考虑到后者可以一次识别只有1位碰撞和只有2位碰撞的情况，从(2)式可以看出，当标签长度k=8，标签数n=5时，碰撞位数x=1的概率是14.6%，碰撞位数x=2的概率是44%。由此可知，实际碰撞次数要低于(4)式所表示的大小，下面我们通过仿真来看看效果。

3 仿真及分析

采用C++编程来验证算法的性能，在理想信道中改变标签的个数，冲突位随机产生，在此基础上，我们将本算法与BS及BLBO算法进行比较，之所以选择BS，是因为BS算法是所有改进算法的基础，而BLBO算法又是本文灵感的来源之一。

BS，BLBO及改进算法的寻呼次数比较如图2。图2中标签ID随机产生，数量在90之内变化，长度恒定为64 bit,实验次数为50次，再取结果的平均值。从图2中可知，3种算法中，改进算法占优。这是由于奇偶区域锁位算法，可以一次识别一个和2个冲突位，而另外2种算法只能一次识别一个冲突位。

图2 BS，BLBO及改进算法的寻呼次数比较Fig.2 Comparison of query-response number for BS, BLBO and proposed algorithm

由于传输时延比阅读器的处理时延大，为简化问题的处理，下面仿真只以传输时延作为参数来比较上述3种算法的性能。图3为BS，BLBO及改进算法的时延比较。

图3 BS，BLBO及改进算法的时延比较Fig.3 Comparison of latency performance for BS, BLBO and proposed algorithm

图3中标签的冲突位与标签的长度相等，传输时延随标签数的变化趋势。这里设定传输速率为100 kbit/s，从图3中看出，改进算法的传输时延要小于BS和BLBO算法，从前面算法分析中可以看出，BLBO算法与改进算法都有标签响应时只传输冲突位，因而比BS的传输时延大大减小。由于改进算法中阅读器在奇偶区域的第一次探询之后，每次探询还需多增加一位奇偶识别位，在不考虑一次识别2位冲突的情况下，理论上前者要比后者少寻呼一位，因此，两者在传输时延上并无较大的差别；在考虑一次识别两位冲突的情况下，由于后者寻呼次数减少，使得传输时延也比前者小。有趣的是图2和图3相比，随着标签数的增加，相应参数具有类似的形状变化，这是由各自算法的特性决定的。

4 结束语

本文结合BLBO算法和奇偶二进制树搜索算法的优点提出了改进算法。阅读器在奇偶区域分别进行锁位算法。锁位算法由于标签只传送冲突位，因此具有较低的时延。改进的算法在锁位的基础上引入奇偶区域，使得寻呼次数进一步减小。理论分析和仿真结果表明，改进算法的性能与常用的防碰撞算法相比，进一步提高了系统的识别效率。

[1] BILL G, HIMANSHU B. RFID essentials[M]. Farnham: O'Reilly Media, 2006.

[2] LIU L, LAI S. ALOHA-Based Anti-Collision gorithms Used in RFID System[C]//Wireless Communications, Networking and Mobile Computing. Wuhan: IEEE Press, 2006:1-4.

[3] CHO H, LEE W, BAEK Y. LDFSA: A Learning-Based Dynamic Framed Slotted ALOHA for Collision Arbitration in Active RFID Systems[C] //Advances in Grid and Pervasive Computing. Paris: Springer, 2007:655-665.

[4] LEE C, CHO H, KIM S W. An Adaptive RFID Anti-Collision Algorithm Based on Dynamic Framed ALOHA[J].IEICE TRANS.COMMUN,2008(E91-B):641-645.

[5] NANJUNDAIAH M，CHAUDHARY V. Improvement to the Anticollision Protocol Specification for 900MHz Class 0 Radio Frequency Identification Tag[C]//Advanced Information Networking and Applications. MIT Auto-ID Center: IEEE Press,2005:616-620.

[6] MYUNG J, LEE W, SRIVASTAVA J， et al. Tag-Splitting: adaptive collision arbitration protocols for RFID tag identification[J]. IEEE Transactions on Parallel and Distributed Systems, 2007, 18 (6): 763-775,

[7] FINKENZELLER K. RFID handbook:fundamentals and applications in contactlesssmart cards and identification[M]. 2nd. Hoboken, N.J: Wiley,2003.

[8] ABHYANKAR S, AGRAWALD P. Distributed Mobility Aware Route Selection for Wireless Ad Hoc Networks[C]// IEEE International Performance Conference on Computing and Communications. Phoenix, USA: IEEE，2002: 241-247.

[9] ZHU H J,XU R Y,High speed intra-body communication for personal health care[C]//Engineering in Medicine and Biology Society.Minneapolis：IEEE,2009:709-712.

[10] 余松森，詹宜巨．基于修剪枝的二进制树形搜索反碰撞算法与实现[J]．计算机工程，2005， 31 (16):217-230． YU Songsen, ZHAN Yiju. A Binary-tree Searching Anti-collision Algorithm Based on Pruning Away Branches and Its Practice[J]. Computer Engineering, 2005，31(16):217-230.

[11] 王雪，钱志鸿，胡正超，等 ．基于二叉树的RFID防碰撞算法的研究[J]．通信学报，2010，31(6):49-57. WANG Xue, QIAN Zhihong, HU Zhengchao, et al. Research on RFID anti-collision algorithms based on binary tree[J]. Journal on Communications,2010，31(6):49-57.

[12] 李伟亮，周熙．超高频RFID技术中防碰撞算法研究[J].无线通信技术，2012，01:59-62. LI Weiliang,ZHOU Xi.Anti-collision Algorithm in UHF RFID System[J].Wireless Communication Technology, 2012，01:59-62.

[13] 刘亮，邢焕革，郭金卫．奇偶区域搜索反碰撞算法及其仿真分析[J]．计算机工程与设计，2010,21(32)：2740-2743. LIU Liang, XING Huange, GUO Jinwei. Anti-collision algorithm based on odd-even zone search and its simulation analysis[J]. Computer Engineering and Design, 2010,21(32)：2740-2743.

[14] HAEJAE Jung. A Memory Efficient Anti-Collision Protocol to Identify Memoryless RFID Tags [J]. Inf Process Syst, 2015,11(1):95～103.

[15] JIANGANG J. Research on an Improved RFID Anti-collision Algorithm in the Internet of Things[J]. International Journal of Security and Its Applications, 2016, 10( 6):99-106.

[16] LAI Y C,HSIAO L Y.General Binary Tree Protocol for Coping with the Capture Effect in RFID Tag Identification[J]. IEEE COMMUNICATIONS LETTERS,2010,14(3):208-210.

(编辑：张 诚)

The Chongqin Foundation and Advanced Research Project (cstc2014jcyjA40037)

A bit-locking binary tree algorithm based on odd-even zone

TANG Hongbin1,2，ZHOU Shangbo2
(1.School of Mathematics and Information Engineering, Chongqing University of Education, Chongqing 400067, P.R. China; 2.College of Computer Science, Chongqing University, Chongqing 400044, P.R. China)

RFID technology is the core of the Internet of Things, Anti-collision technique is a key technique and research focus in the RFID system. In view of the inefficient of the binary tree algorithm with long delay and too much inquiry. This article is based on collision technology of radio frequency identification (RFID) technology. On the basis of many binary tree search algorithm existed, We present a new algorithm, which combine odd-even zone with bit-locking back off anti-collision algorithm. The inquiring area is divided into two zone, The dividing odd-even zone can improve the efficiency of search, while the bit-locking back off anti-collision algorithm can reduce transmission delay. Both theory and simulation results show the effectiveness and superiority of the algorithm.

radio frequency identification; odd-even zone; bit-locking; anti-collision; binary tree

2016-07-09

2017-04-21 通讯作者：汤宏斌 bin_tang78@163.com

重庆市基础与前沿研究计划项目(cstc2014jcyjA40037)

10.3979/j.issn.1673-825X.2017.03.021

TP391.03

A

1673-825X(2017)03-0416-05

汤宏斌(1972-)，男，安徽人，在职博士生，主要研究方向为视频信号处理、信息安全和深度学习。E-mail:bin_tang78@163.com。

周尚波(1963-)，男，广西宁明人，教授，博士生导师，主要研究方向为：人工神经网络、混沌及其控制理论、图像处理、信息安全、物理工程计算、计算机仿真。E-mail:shbzhou@cqu．edu．cn。