确定型标签防碰撞算法研究综述
2018-02-01张德慧李政
张德慧+李政
摘 要:确定型标签防碰撞算法是无线射频识别(Radio Frequency Identification,RFID)技术中一种关键性的标签防碰撞算法,可100%识别完毕所有待测标签。本文对确定型标签防碰撞算法的核心思想进行深入探讨,总结归纳不同确定型标签防碰撞算法的优缺点,结合现状,提出下一步研究方向。
关键词:RFID;标签防碰撞技术;确定型标签防碰撞算法
中图分类号:TP312 文献标志码:A
0 引言
RFID技术是一种非接触式的自动识别技术,在“万物皆可通过网络互联”的物联网时代,RFID技术以其自身独特的优势,如:阅读器可同时识别大量标签、标签信息可重复利用、标签体积形状多样化等,成为物联网中物体身份识别的关键技术。一个完整RFID系统由阅读器、标签和计算机系统组成。计算机系统向阅读器传达读取标签指令后,阅读器便发送该指令给处于其自身范围内的所有标签,激活的标签立即与阅读器建立通信。通信过程中,由于标签数量过多,容易产生信号冲突。因此,本文就标签碰撞问题研究标签防碰撞算法。
目前,标签防碰撞算法主要从4个方面入手空分多址(Space Division Multiple Access,SDMA),码分多址(Code Division Multiple Access,CDMA),频分多址(Frequency Division Multiple Access,FDMA),时分多址(Time Division Multiple Access,TDMA)。其中,TDMA是把整个通路容量按时间划分给多个用户,也是现在RFID标签防碰撞算法领域应用最为广泛的划分方式。基于TDMA技术的特点,又将标签防碰撞算法分为两类:一类是概率型的标签防碰撞算法,该算法中,标签通过随机选择时间点来响应阅读器,算法虽然简单易执行,但是容易造成“标签饥饿”现象。另一类是确定型的标签防碰撞算法,主要分为4种:二进制搜索树算法、动态二进制搜索树算法、回退式二进制搜索树算法、查询树算法,该类算法通过二进制编码逐一选择标签进行通信,可100%识别完所有待测标签,避免“标签饥饿”现象。
1 确定型标签防碰撞算法
1.1 二进制搜索树算法
阅读器向在它范围内的所有标签发送二进制位全为1的搜索指令,该指令长度与标签ID号长度相同。被激活的标签会将自身ID号位数与指令中的每一位进行比较。若ID号小于或等于该二进制指令,则对阅读器进行响应,下一次的读取指令与初始指令相同;否则,检测最高碰撞位,并将该位从“1”置为“0”,碰撞位之前的位数保持不变,作为下一次的搜索指令。直至标签全部搜索完毕,查询结束。假设有4个标签,分别为标签A:11010111、标签B:11100101、标签C:11101111、标签D:11010101,其二进制搜索树算法搜索过程可见表1。
总的搜索次数为式(1)所示,其中,N为待测标签总数量。
(1)
标签识别完毕传输的总信息量为式(2)所示:
(2)
1.2 动态二进制搜索树算法
动态二进制搜索树算法在二进制搜索树算法的基础上,保留算法思想,但减少了通信传输的信息量,检测到碰撞位时,碰撞位后面的所有二进制位全都成为冗余数据,步骤与二进制搜索树算法类似。依旧以上述4个标签为例,其动态二进制搜索树算法搜索过程可见表2。
标签识别完毕传输的总信息量为式(3)所示:
(3)
1.3 回退式二进制搜索树算法
回退式二进制搜索树算法算法以二进制搜索树算法为基础,修改了二进制搜索树算法的搜索规则,该算法中,每当阅读器成功识别一个标签之后,都要重新发一个二进制位数全为“1”的搜索指令,增加了总的查询次数。回退式二进制搜索树算法为了改进该弊端,在一个标签被成功读取之后,不会再重新发送一个二进制位数全为“1”的搜索指令,而是依据上一轮的搜索指令,将上一轮中的碰撞位从“0”修改为“1”,进行下一轮的标签读取。每一轮标签读取的命令码长度与标签ID号长度相同,依旧以上述4个标签为例,其回退式二进制搜索树算法搜索过程见表3。
总的搜索次数为式(4)所示:
Sum=2N-1 (4)
标签识别完毕传输的总信息量为式(5)所示:
Ctraffic=2L(2N-1) (5)
1.4 查询树算法
查詢树算法与之前的二进制搜索树算法、动态二进制搜索树算法和回退式二进制搜索树算法有所不同,阅读器在发送查询标签的初始化命令码时,会根据标签的ID特征,发送长度为K的前缀码,不再是发送和标签ID号相同的序列长度,被激活的标签将自己ID号的前K位与该前缀码相比较,若相同,则标签与阅读器建立通信,并把第“K+1”位至最后一位发送给阅读器,此时标签识别成功。若多个标签ID号的前K位与前缀码相同,则发生碰撞。假设标签为标签A:0010、标签B:1110、标签C:0001、标签D:1101其查询树算法搜索过程见表4。
结语
通过以上分析,在几种确定型标签防碰撞算法中,二进制搜索树算法在实现上相对简单,但是在执行过程中,重复性工作较多,搜索次数大,且识别标签所需信息通信量高,增加了系统的负担。动态二进制搜索树算法在通信量方面明显要低于BST算法,但搜索次数没有减少,与二进制搜索算法的搜索次数相同。回退式二进制搜索树算法不仅降低了搜索次数,还减少了信息通信量,但标签数量过多时,会增加系统搜索时间。查询树算法通信量少,但是随着标签数量增多,二叉分支也会增多,直到检测出没有响应的标签时,才终止查询,增加系统的搜索时间。
目前,针对确定型算法的研究主要集中在查询树算法上,众多研究学者通过对查询树中二叉树或者多叉树动态结合,来达到减少查询次数、降低信息通信量的目的。因此,为了后续的研究能够高效快速的开展,建议针对确定型标签防碰撞算法中的查询树算法重点研究,以取得更优良的算法。
参考文献
[1]Ying-Meng H U, Zhang X H. Research of an Adaptive Searching Anti-collision Algorithm for RFID Based on Information-Bit Encoding[J]. Acta Electronica Sinica, 2016.
[2]杨晓娇,吴必造.射频识别中确定性防碰撞算法研究[J].微型机与应用,2017,36(8):67-69.
[3]丁治国,雷迎科.基于优先级避让的防碰撞算法研究[J].计算机应用研究,2016,33(3):836-839.endprint