改进的FRID防碰撞算法仿真研究

【摘 要】分析了动态二进制树防碰撞算法的基本原理，提出了动态二进制树防碰撞的改进算法。运用MATLAB对不同防碰撞算法的搜索时间及搜索次数进行了仿真，仿真结果表明，改进算法缩短了搜索时间、减少了搜索次数，验证了理论分析及改进算法的正确性与可行性。

【关键词】FRID；防碰撞算法；改进算法；仿真研究

0 引言

近年来，射频识别（Radio Frequency Identification）这一自动识别技术在制造、物流、交通运输[1-2]、防伪、医疗和跟踪等应用方面获得了广泛的应用[2-3]。

RFID技术具有多目标识别显著优点，但与此同时，多目标识别势必造成多标签上行信号的数据冲突，从而给FRID系统的数据完整性带来极大威胁[4-5]。研究表明，合适的防碰撞算法能够有效地减缓数据冲突对系统数据完整性的威胁[6]。

针对RFID技术中的数据冲突及其碰撞现象，文献[7，8]提出了各种各样的改进算法。

本文提出了一种动态二进制树防碰撞的改进算法，并对其进行了仿真研究。

1 基本二进制树防碰撞算法原理

为实现此算法，在此规定两个将要使用的指令：

1）请求指令Request（SN）：此指令自带有一个参数SN，当电子标签（ET）接收到阅读器发出的Request指令后，自动将其序列号与接收到的SN值进行比较。若自身序列号的值不大于阅读器发出的SN值，ET便将自己的序列号馈送给阅读器。

2）休眠指令Sleep（SN）：该指令亦带一个参数SN，当ET接收到阅读器发送的此指令后，迅速将自己的序列号与接收到的SN值比较。如自己序列号与接收到的SN值相等，则该ET被识别出来，开启休眠模式，从此不再响应系统发出的Request指令，除非重新上电。

基本二进制树防碰撞算法流程如图1所示：

图1 基本二进制树算法流程

根据图1所示流程，阅读器即可按照序列号从小到大的顺序挨个识别出所有在阅读器识别范围内的所有电子标签（ET）。

2 防碰撞算法的改进研究

下面对二进制防碰撞算进行改进，改进后的算法步骤为：

Step1： 初始化SN，使SN值最大。

Step2：阅读器发送Request指令，此指令附带一个参数SN，设该参数的长度x，ET在接收到指令后，首先将自己序列号中的高1～x位与接收到的Request指令中参数SN的大小进行比较，若不大于接收到的参数SN，则将该ET剩余位发送至阅读器。

Step3：阅读器依据曼彻斯特编码法则检测出最高及次高碰撞位。若发生碰撞，找出最高及次高碰撞位，将最高及次高碰撞位分别置00、10、01、11，然后依次执行Step2；否则读取该标签信息，而后执行Step4。

Step4：阅读器向成功识别的标签发送休眠指令sleep，使ET进入休眠模式，直至重新上电。然后，采取后退策略从上一层碰撞节点取得下一次Request所需参数。

Step5：返回Step2，直到成功识别出所有

3 仿真实验

运用MATLAB分别对各种算法的搜索次数、搜索时间进行仿真研究，仿真结果如图2所示。

图2 各种算法搜索次数的比较（标签为8位）

从图2可以看出，就搜索次数而言，基本二进制树算法与动态二进制树算法基本相同，而改进算法比基本二进制树算法、动态二进制树算法和后退式算法均要少点些，但其优势并不显著。

各种算法搜索时间与搜索次数的对比基本一致，由于搜索次数要少一些，所以改进算法的耗时要比后退式算法短一些，但后退式算法的耗时与改进算法的耗时差异很小。

4 结论

分析了动态二进制树防碰撞算法的基本原理，提出了动态二进制树防碰撞的改进算法。运用MATLAB对不同防碰撞算法的搜索时间及搜索次数进行了仿真，仿真结果表明，改进算法缩短了搜索时间、减少了搜索次数。

【参考文献】

[1]萧耀友，等.基于二进制树分解的动态防碰撞算法[J].通信技术，2011，1（44）：99-108.

[2]Myung， Jihoon Lee， Wonjun， Srivastava， Jaideep. Adaptive binary splitting for efficient RFID tag anti-collision[Z]. IEEE Communications Letters. 2006.

[3]孙耀磊，等.一种改进的四叉树RFID防碰撞算法[J].计算机工程与应用，2014，50（4）：63-68.

[4]RYU J， LEE H， SEOK Y， etal. A hybrid query treeprotocol for tag collision arbitration in RFID systems[Z]. Proceedings of IEEE InternationalConference on Communications. 2007.

[5]周红妹，等.一种改进的二进制防碰撞算法[J].常州大学学报，2013，25（4）：48-51.

[6]KIM Y， KIM S， LEE S， etal. Improved 4-ary query tree algorithm for anti-collision in RFID system[Z]. International Conference on Advanced Information Networking and Applications. 2009.

[7]SEOL J H， KIM S W. Collision-resilient multi-state query tree protocol for fast RFID tag identification[Z]. Computational Intelligence and Security . 2006.

[8]夏小勤，胡佳佳.基于动态树形RFID防碰撞算法的研究[J].科技广场，2014（03）.