基于回溯的RFID防碰撞算法

董光祯，陈庆奎，2

（1.上海理工大学 光电信息与计算机学院，上海200093；2.上海理工大学 上海市现代光学系统重点实验室，上海200093）

0 引 言

随着RFID 的应用逐渐普及［1－3］，当阅读器的识别范围出现多个标签时就产生标签争抢信道的通信碰撞问题，严重影响RFID 系统的性能［4］。为了有效改善RFID 系统的通信性能，由通信中的防碰撞算法进而产生了标签防碰撞算法。现行的标签防碰撞算法主要分为确定性的和随机性的防碰撞算法［5－7］。确定性的防碰撞算法主要是基于轮询的思想：借用二叉树的数据结构，将处于碰撞的标签分成左右两个子树（0／1），先查询左子树（0），若没有碰撞，则正确识别标签，执行相应操作，若产生碰撞继续划分左右子树（00／01），依次类推，直到识别出左子树（0）中的所有标签，再依此查询右子树（1）。由于二进制防碰撞算法的实用性更好，在这方面的研究相对较多，不同的研究人员对此提出各种各样的改进型算法［8－12］，但随着标签数量增加，识别速率都有不同程度下降，文献［8］中提出了一种基于后退式二进制搜索算法的改进算法，该算法有效地缩减了阅读器的查询次数，但标签返回信息的数据传输过程中仍有一定的数据冗余；文献 ［9，10］是基于跳跃式动态树形反碰撞算法的改进，两种算法都是通过一次性确定碰撞位然后在此基础上轮询检测，优化了查询次数，但其问题都是传输的命令位数过多，数据冗余量大；文献［11］中提出的改进算法没有充分利用已有的信息，标签识别过程中回送重复信息，随着标签ID 及数量的增长，势必会使系统处理过多的不必要数据，从而使系统通信性能下降。文献［12］提出了借用堆栈以及队列的思想优化标签识别过程，但因为其引入了过多的命令而使多标签识别过程随标签增多性能增加并不是很明显。本文在分析研究现有的二进制防碰撞算法的基础上，提出一种基于回溯的借助堆栈不间断轮询防碰撞算法，该算法通过减少标签识别过程中的迭代次数和发送数据量来提高RFID 系统的通信性能。

1 不间断轮询防碰撞算法

1.1 算法采用的编码及交互命令

实现二进制搜索算法的前提是能够辨别出在阅读器中数据冲突位的准确位置，为此数据编码采用曼彻斯特编码［4，13］。阅读器和应答器之间的交互命令除传统算法中的REQUEST、SELECT、READ／WTITE、UNSELECT 命令外［8，11］，增加POP、PUSH 命令。在动态二进制算法中，虽然已经减少一些不必要的序列传输和数据通信量［11］，但不能有效的把数据传输量减少到最低，同样，也不能很好的减少不必要的算法迭代。在本算法中将阅读器的发送命令修改为当前碰撞位，即发送命令只发送一位，应答器的返回信息是当前碰撞位的后面一位，这样数据发送量将进一步优化。

1.2 算法过程描述

（1）阅读器指令：二进制防碰撞算法中，可有效识别碰撞位，而数据相同的非碰撞位在传输指令中是没有实际意义的，因此，可以将动态二进制中的发送指令精简为一位（碰撞位），即每次发生碰撞阅读器发送搜索指令时，只发送当前碰撞位的搜索值0 或者1。首次搜索还是以REQUEST（NULL，8）作为当前区域所有标签的激活指令，此时所有标签应答，阅读器标记所有碰撞位，继续最高碰撞位ID（XH）为0的标签响应，将（XH）压栈，暂时静默最高碰撞位为1的标签。如此重复，直到阅读器正确识别出一个标签。再回溯到发生碰撞的最低位，阅读器将命令REQUEST（ID（XL），1）出栈发送，重复此过程直到区域内的所有标签正确识别。阅读器和标签的状态转移和工作流程图如图1、图2所示。

（2）算法描述：设待识别标签序列号SN 位数为n，若第i位发生碰撞则标记碰撞位为Xi，最高碰撞位为XH，最低碰撞位为XL，首先阅读器发送req（null，n），所有静默计数器为0 的标签响应，阅读器检测并标记碰撞位，将［ID（XH），1］压栈，此位置为1的标签静默计数器加1，继续响应碰撞位值为0的标签，如此进行直到没有碰撞发生正确识别出标签，然后查询堆栈将［ID（XL），1］出栈，每出栈一次所有静默标签的静默计数器减1，如此循环直至阅读器范围内的标签被正确识别，如上所述，发送一次命令之后肯定会有一个标签被识别并处理，如此发送的命令数即为所有标签SN 的碰撞位数k＋1，数据传输量为SN 的长度n。

图1 标签状态转移图、工作流程

图2 阅读器工作流程

（3）识别过程：假设在活动区域内有8个8位的标签，下面以这8个标签的识别过程来简要说明这个算法的原理和过程：A：10110100；B：10110101；C：10100101；D：10100100；E：11010101；F：11010100；G：11000100；H：11000101。在这个算法中，需要一块存储空间来对未碰撞的位和当前阅读器已发送的指令进行存储。其具体执行过程如下：

1）Reader发送request（null，8）命令，激活区域内所有标签（静默计数器q＝0），并且标签应答。Reader解码得到的ID 为1？？？010？，对未碰撞位进行存储（1xxx010x）。碰撞位为6、5、4、0，碰撞位数为4位；

2）将最高碰撞位ID（6）压栈，将最高碰撞位值为1的标签静默，即静默EFGH 标签；此时静默计数器数值为1；

3）ABCD 响应，第五位发生碰撞，（ID（5），0）响应，静默AB；其静默计数器为1，将EFGH 静默计数器的值加1；

4）CD 响应，第四位发生碰撞，（ID（4），0）响应，静默C；同时之前的静默标签静默计数器加1；

5）D 响应，无碰撞发生，正确识别，回溯至（ID（0），1）；同时发送一次激活命令，所有静默标签的静默计数器减1；

6）C响应，无碰撞，正确识别，回溯至（ID（4），1）；同时所有静默标签的静默计数器减1；

图3 标签识别过程

7）AB响应，重复过程3）～6），AB正确识别；

8）重复过程2）～7），EFGH 正确识别；

图3所示为标签识别的过程图。在图3 中，描述了标签识别及算法的回溯过程。根据算法搜索过程，在阅读器发出当前搜索指令后，该图反映了标签响应情况，体现了标签被识别时所接受的搜索指令，还能够直观的得出搜索全部标签时，阅读器所需要发送指令的次数。通过识别过程所发送指令，能够得到阅读器搜索迭代数，进一步的计算数据通信量。

1.3 算法性能分析

（1）迭代数分析：假设阅读器区域内有N 个ID 为M位待识别标签，其中碰撞位为x位。通过图3所示的标签识别过程可知，不间断轮询的标签防碰撞算法识别全部标签需要的轮询次数见表1（当有一个碰撞位时，阅读器可以同时识别两个标签）。

表1 标签数量与迭代数的关系

即使在最不理想的情况下，标签数目N＝2x，最大迭代数为2X－1。如果由于在实际运用中，N 的值可能会小于2x，查询迭代数也会相应减少。在这里，假设标签数目为最大。所以，识别单个标签所需的查询次数为

（2）数据通信量分析：

数据的传输时间取决于ID 的长度和搜索次数。在动态二进制搜索算法中，阅读器平均每次传送ID 的平均长度为V，其中M 为标签长度

阅读器识别全部标签的总传输数据量为S

在本算法中，阅读器只发送一位，因为借用了堆栈，命令发送次数减半，因此，阅读器识别全部标签总传输量为

当标签ID 位较长时，在动态二进制算法中，所需要传送的通信数量会随着ID 的长度而相应增大，同时也不能避免某些位重复传送，大大影响了系统的识别速度；在本算法中，阅读器发送指令只发送一位碰撞位的值，即使在ID较长的情况下，利用堆栈可以有效减少发送次数，因而也不会影响系统的传送速率。

2 实验分析

实验环境：根据动态二进制算法和基于回溯的不间断轮询防碰撞算法原理，在NS2环境［14］下仿真比较了相关算法的特性。设定标签ID 为8 位、16 位、64 位。因为跳跃式动态二进制的性能明显好于动态二进制防碰撞算法［8］，以下仿真分析只是比较跳跃式动态二进制与不间断轮询算法。以下为实验分析结果：

实验1：迭代次数比较

二进制搜索算法识别率较高，没有错误判决的问题，然而其时延比较长，泄露信息较多，安全性较差，其信道利用率可达43%，当待识别标签数目为n时，二进制识别算法和动态搜索算法平均识别一个标签需查询log2n＋1次。而不间断轮询的回溯搜索算法识别n个标签的查询次数是2n－1次。除激活命令外本算法每次查询阅读器发送和接受的命令都是1bit。当标签数量较多时，本算法的有效性是明显的。算法性能比较见表2。

表2 算法性能比较

仿真结果如图4所示，图4（a）为识别所有标签的总的迭代次数，图4（b）为平均识别单个标签所需迭代次数。通过对比可以看出，不间断轮询的防碰撞算法明显优于跳跃式二进制搜索算法，尤其在标签数目较多的情况下。

图4 算法性能仿真比较

实验2：数据传输量分析

由图5可见，跳跃式动态二进制防碰撞算法随着标签ID 的增长，其所需的数据传输量急剧增长，而不间断轮询的防碰撞算法发送的数据量不受标签ID 位数的影响。

实验3：系统吞吐量分析

图5 传输数据量比较

因为改进后的算法在数据传输量和迭代次数上有一定的优化，所以系统吞吐率有明显提升，仿真结果如图6所示。

图6 系统吞吐率比较

3 结束语

本文在动态二进制搜索算法的基础上，对阅读器和标签的交互命令以及搜索算法进行了相应改进，进而提出了利用堆栈进行回溯的不间断轮询防碰撞算法。该算法优化了阅读器和标签之间的数据传输量，减少了阅读器识别区域内标签所需的迭代次数，提高了标签的识别速度。仿真验证表明，该算法性能明显优于传统跳跃式动态二进制算法。本算法需要在标签序列号一端占用一定的数据空间以标记标签的静默程度，接下来的工作是将本算法应用于不同频段的RFID 融合识别系统。

［1］SUN Qibo，LIU Jie.Internet of things：Summarize on concepts，architecture and key technology problem ［J］.Journal of Beijing University of Posts and Telecommunications，2010，33（3）：1－9 （in Chinese）.［孙琪博，刘杰.物联网：概念、架构与关键技术研究综述 ［J］.北京邮电大学学报，2010，33（3）：1－9.］

［2］Ngai EWT，Karen KL Moon，Frederick J Riggins，et al.RFID research：An academic literature review（1995－2005）and future research directions ［J］.Int J Production Economics，2008，112 （2）：510－520.

［3］Kang dong，Shi Xiqin.RFID core technology and typical application development case ［M］.Beijing：Posts ＆ Telecom Press，2008.

［4］Jia Xiaolin，Feng Quanyuan，Ma Chengzhen.An efficient anti－collision protocol for RFID tag identification ［J］.IEEE Communications Letters，November2010，14 （11）：1014－1016.

［5］Dheeraj K Klair，Chin Kwan－Wu，RaadRaad.A survey and tutorial of rfid anti－collision protocols ［J］.IEEE Communications Surveys ＆Tutorials，2010，12 （3）：400－421.

［6］KANG Dong，SHI Xiqin，LI Yongpeng.The core technology and case of typical applications of radio frequency identification（RFID） ［M］.Beijing：Post＆Telecom Press，2008 （in Chinese）.［康东，石喜勤，李勇鹏.射频识别 （RFID）核心技术与典型应用开发案例 ［M］.北京：人民邮电出版社.2008］.

［7］Mohammed Al－Medhwahi.AbdulsalamAlkholidi.A new hybrid frame ALOHA and binary splitting algorithm for anti－collision in RFID systems software ［C］／／International Conference on Telecommunications and Computer Networks，2010：219－224.

［8］FAN Wenjing，ZHANG Shanshan，TIAN Zhihui.Research on RFID anti－collision algorithm based on regressive－style binary search ［J］.Computer Applications and Software，2012，29（5）：191－194 （in Chinese）.［樊文静，张姗姗，田智慧.基于后退式二进制搜索的RFID防碰撞算法的研究 ［J］.计算机应用与软件，2012，29 （5）：191－194.］

［9］GUO Hongyi，LI Sudan.An improved anti－collision algorithm based on binary－tree searing of jumping and dynamic ［J］.Computer＆Telecommunication，2009 （3）：57－59 （in Chinese）.［郭洪役，郦苏丹.一种基于跳跃式动态树的二进制搜索改进算法 ［J］.电脑与电信，2009 （3）：57－59］

［10］WANG Yaqi.An improved anti－collision algorithm of RFID system ［J］. Microcontroller＆Embedded Systems，2007（9）：15－17 （in Chinese）.［王亚奇.一种改进的RFID 系统反碰撞算法 ［J］.单片机与嵌入式系统应用，2007 （9）：15－17.］

［11］JIANG Lifen，LU Guizhang，XIN Yunwei.Research on anticollision algorithm in Radio frequency identification system［J］.Computer Engineering and Applications，2007，43（15）：29－32 （in Chinese）. ［姜丽芬，卢桂章，辛运帏.射频识别系统中的防碰撞算法研究 ［J］.计算机工程与应用，2007，43 （15）：29－32.］

［12］HUO Hua，WANG Yongjie.RFID anti－collision algorithm based on parallel processing ［J］.Computer Engineering，2011，37 （6）：263－265 （in Chinese）. ［霍华，王永杰.基于并行处理的RFID 防冲突算法 ［J］.计算机工程，2011，37 （6）：263－265.］

［13］DENG Yiwen，ZHANG Hongyu.Study on the anti－collision algorithm of the RFID read／write device ［J］.Electronic Design Engineering，2011，19 （19）：31－34 （in Chinese）. ［邓一文，张红雨.RFID高频读写器防碰撞算法研究 ［J］.电子设计工程，2011，19 （19）：31－34.］

［14］ZHANG Hongbin，RONG Mengtian，DENG Xiaodong.Research on RFID system simulation tool based on NS ［J］.Computer Simulation，2008，25 （2）：127－135 （in Chinese）.［张宏斌，戎蒙恬，邓晓东.基于NS的RFID 系统仿真工具研究 ［J］.计算机仿真，2008，25 （2）：127－135.］