一种改进的锁位-八叉树搜索算法

洪放 吕洪杰

摘要：本文介绍了RFID标签防碰撞算法，确定了一种改进的锁位—八叉树搜索算法，该算法实现了消除空闲时隙、避免了查询冗余，大幅度提高系统吞吐率和识别性能，减少识别时延。结果表明这种改进算法提高了结算的速率，节省了成本。

关键词：物联网;RFID;防碰撞算法;无人超市

随着物联网技术在智慧化城市各领域的广泛应用。RFID技术被大量使用在无人超市中，当多个标签同时向阅读器发送请求时，阅读器出现误判或是失效结论，这就是碰撞问题。它严重影响了物联网系统正常运转。因此多标签碰撞问题是无人超市结账系统中亟待解决的问题。

1 防碰撞简介

射频识别RFID始于1973年，用以取代传统条形码的使用，它通过非接触式电磁感应实现电子标签和读写器之间的信息交互，完成标签信息的传递。在这个RFID环境中，数以百计的顾客可能被放置在同一区域通过扫描大量的标签以达到所需的覆盖范围。这种密集的网络表现出大量的碰撞。这种碰撞导致数据收集吞吐量降低，增加识别延迟和网络效率下降。RFID系统中碰撞问题分为两种，标签碰撞和阅读器碰撞。

2 防碰撞算法

防碰撞算法分为非确定性防碰撞算法和确定性防碰撞算法，非确定性防碰撞算法具有低复杂度，工程容易实现等优点;但是存在标签饿死的情况。而确定性防碰撞算法识别率高，算法稳定且不存在标签饿死等现象，因此对于无人超市这类安全性要求较高的系统，大都采用确定性算法。

2.1 鎖位后退式二进制树搜索算法

锁位后退式二进制树搜索算法在成功识别出第一个标签后，阅读器不需要重新发送Request命令，而是直接锁位分组退回到上一层继续搜索，也就是返回到根节点，这就会降低搜索查询的次数。

Step1：阅读器像识别范围发送Request（11111111）命令，范围内标签接到指令后将自身ID发送给阅读器。

Step2：将标签的ID与命令比较，如果发生碰撞，就用曼彻斯特编码分析，按碰撞位的具体情况修改命令，将最高位置“0”，其余为设置为“1”，这样就得到了新的Request命令，因此能减少数据位冗余，从而减少传输量。

Step3：根据新生成的命令序列号，成功限制了一些标签应答，如果还发生碰撞，则重复第二步，直到选出下一个标签。

Step4：读写出选中的标签后，阅读器发送UNselect命令，则该标签不再响应。然后后退，从根节点读取下一个序列号。循环执行，一直到成功识别出所有标签。

锁位后退式二进制树搜索算法极大地减少了问询次数，提高了系统搜索效率。但是该算法并不像DBS算法那样能够减少每次识别所需传输量。锁位后退式二进制树搜索算法实现过程见表1。

2.2 一种改进的锁位-八叉树搜索算法

改进的锁位-八叉树搜索算法是在确定碰撞序列后，采用每三位为一组识别无空闲时隙的搜索方式，结合碰撞前缀和堆栈的使用，来达到降低查询次数，减少传输的数据量和时延，提高了系统的整体性能。具体操作步骤：

Step1：发送指令，判断碰撞。

阅读器发送长度与标签ID号位数相同的Request（11111..1）指令，收到该命令后所有标签向阅读器返回自身ID，且同步回复。如果无标签响应，则阅读器再次发送此指令等待;若只一个标签响应，则立即与该标签通信，读写相关信息，并在通信结束后令其静默，不再参与后续识别过程;如果发生碰撞，则阅读器可知有多个标签在其阅读范围内。

Step2：发生碰撞，发送锁位与碰撞前缀预测指令。

阅读器发现碰撞后，发送锁位与碰撞前缀预测指令，即Request（0101…001，111）指令，其中第一部分为根据每轮碰撞标签回复序列的清况，并将所有发生碰撞的比特位置1，未发生碰撞的比特位置0，形成的查询指令，这样当标签接收到此命令后即可将本轮识别中的碰撞位提取出来，在以后的防碰撞识别过程中均使用这个纯碰撞位序列来进行后续的识别，以减少传输过程中的数据量（每轮碰撞后均是这样操作，将进一步减少传输数据量）;在第一次碰撞后发送的此命令的第一部分长度为标签ID长度L，之后其长度为每轮标签回复序列的长度。第二部分为3位1，即为碰撞前缀预测命令，其作用为令标签返回本轮确定的碰撞序列的最高3位碰撞位，当标签收到此命令后，会将本轮确定出的碰撞序列的最高3位序列进行二一十进制转换后向阅读器发送，其发送规则采用之前所述的碰撞前缀预测规则，所有在此轮识别中发生碰撞的标签均如此回复。

Step3：判断碰撞前3位。

阅读器在收到所有返回信号后，即可判断出此轮发生碰撞的所有标签的前3位碰撞情况，因此确定出来的碰撞前缀即为存在的碰撞标签前缀，然后将此确定出来的碰撞前缀压入碰撞堆栈中保存。

Step4：取出栈首进行依次查询。

阅读器依次从碰撞堆栈中取出栈首的碰撞前缀进行查询，若仅有一个标签响应，即表明无碰撞发生，则此标签被阅读器成功识别，读写其相关信息，在与其通信结束后，发送Unselect指令令其静默，使其不再参与后续的标签识别过程;若仍有碰撞发生，则转至Step2，继续发送锁位与碰撞前缀预测指令，继续在此3位碰撞位之后的碰撞序列基础上确定新的碰撞序列，进行下一轮的3位碰撞位识别过程，若剩余的碰撞序列位数不足3位，则标签自动补充0至3位再向阅读器发送。如此操作，直至将此碰撞前缀分支中的标签全部识别出。

Step5：继续取栈首前缀查询，直至堆栈为空。

阅读器在识别完一个碰撞前缀下的所有标签后，会继续从碰撞堆栈中取出栈首前缀来进行此碰撞前缀分支下的标签查询，如此进行下去，直至将堆栈中的碰撞前缀均查询完，即碰撞堆栈为空后，则表示己将阅读器阅读范围内的所有标签识别完毕，算法结束。

设在阅读器工作范围内存在四个标签，分别为Tag1（ID：10001100）;Tag2（ID：10101010）;Tag3（ID：10101100）;Tag4（ID：10001110）。

阅读器首先发送Request（11111111） 指令，四个标签在接收到此命令后，均响应阅读器向其发送自身ID。阅读器经曼彻斯特译码后发现碰撞，译码结果为10x01xx0，即在第1， 2， 5位发生碰撞，于是发送锁位与碰撞前缀预测指令Request（00100110， 111），锁定标签碰撞序列并进行碰撞前缀预测。

阅读器端接收到的信号译码结果为000xx00x，即第0，3，4位发生碰撞，将碰撞位的位置信息进行相反过程的十一二进制转换后，得到000，011， 100，即为确定存在的碰撞前綴，将其压入碰撞堆栈中保存。在后续的识别中，阅读器依次从碰撞堆栈中取出栈首前缀查询，再需四次查询即可将此四个标签识别出来。

通过以上的改进，使得这种改进的锁位-八叉树搜索算法在大规模标签识别范围内，有效降低碰撞时隙，减少传输数据量，提高了系统吞吐率和整体识读性能，本改进算法的与原来的锁位后退算法的查询次数比减少了16.5%，系统吞吐率提高了10%，传输数据量减少47%，提高了识别性能。适合应用到无人超市中。

3 结语

本文针对锁位后退式二进制树搜索算法在应用到大规模标签时所需传输能量大、碰撞时询问次数过多的问题，提出了一种新的改进的锁位-八叉树搜索算法。这种算法在确定碰撞序列后，采用每三位为一组识别无空闲时隙的搜索方式，结合碰撞前缀和堆栈的使用，来达到降低查询次数，减少传输的数据量和时延，提高了系统的整体性能的目的。

参考文献：

[1] 尹鹏，吴连军，张望泉.物联网在生活当中的应用[J].中国战略新兴产业，2018（06）.

[2] 吴宏伟，李钊，沈雪.基于物联网技术的智能超市系统的开发与研究[J].福建电脑，2017（02）.

[3] 李尧.基于Zigbee的电子标签系统的设计与实现[J].电子设计工程，2016（02）.

[4] 吴必造，杨晓娇.RFID中的不确定性标签防碰撞算法简介[J].微型机与应用，2017（06）.

[5]  Wang H， Xiao S， Lin F， et al. Group improved enhanced dynamic frame slotted ALOHA anti-collision algorithm[J].The Journal of  Supercomputing，2014（03）.

[6] Duan L，Wang Z J，Duan F.An optimal dynamic frame slot-segment algorithm[C].InProceedings of the 2015 Workshop on Mobile Big Data. ACM， 2015.

[7] 潘思丞，王慧琴，张小红.静态环境中分组ALOHA防碰撞算法研究[[J].计算机工程与应用，2016（20）.

（作者单位：阜新市第一中等职业技术专业学校）