基于ALOHA分区的多周期防碰撞搜索算法

摘要/Abstract

摘要： 在射频识别系统中，标签用于传递信息，在阅读器有效作用范围内，多个标签同时响应从而发生碰撞的情况不可避免，标签发生碰撞会降低系统的识别效率。为了提高系统的标签识别效率，本文在已有防碰撞算法的基础上提出一种基于ALOHA分区的多周期防碰撞搜索算法。该算法首先根据待识别标签数目划分相应时隙帧长，然后在发生碰撞的时隙内利用多周期防碰撞搜索算法识别标签，能够有效降低碰撞发生概率，提高标签识别效率。该算法可应用到数量庞大的标签识别系统中，对这类系统具有一定优势。理论分析与实验结果表明：该算法能够有效减少算法时隙数，提高系统的标签识别效率。

关键词: RFID, 防碰撞算法, ALOHA, 多叉树搜索, 标签识别

Abstract: In the RFID system, tags are used to transmit information. Within the effective function range of the reader, multiple tags respond at the same time and thus collision is inevitable. The collision of tags will reduce the recognition efficiency of the system. In order to improve the efficiency of label recognition, this paper proposes a multi-cycle anti-collision search algorithm based on ALOHA partition and the existing anti-collision algorithms. Firstly, the frame length of the corresponding time slot is divided according to the number of tags to be recognized. Then, the multi-cycle anti-collision search algorithm is used to identify the tags in the time slot where the collision occurs, which can effectively reduce the probability of collision and improve the efficiency of tag recognition. This algorithm can be applied to a large number of label recognition systems, and has certain advantages over these systems. Theoretical analysis and experimental results show that the algorithm can effectively reduce the number of algorithmic time slots and improve the efficiency of label recognition.

Key words: RFID, anti-collision algorithm, ALOHA, multi-tree search, tag identification

薛伟莲, 李雪娇, 陈杰. 基于ALOHA分区的多周期防碰撞搜索算法[J]. 计算机与现代化, 2021, 0(11): 95-99.

XUE Wei-lian, LI Xue-jiao, CHEN Jie. A Multi-period Anti-collision Tree Search Algorithm Based on ALOHA Partition[J]. Computer and Modernization, 2021, 0(11): 95-99.

参考文献［22］

［1］	宋建华,何帅,姚慧. 多阅读器协作的RFID标签树形防碰撞算法［J］. 电子学报, 2020,48(8):1558-1564.
［2］	李勇,王琼. 多电子标签识别的RFID防碰撞方法［J］. 南京邮电大学学报(自然科学版), 2019,39(4):33-38.
［3］	许仙明,吴敏,吴静进,等. 基于RFID技术的自适应分组标签防碰撞算法研究［J］. 现代电子技术, 2019,42(24):55-58.
［4］	胡黄水,张国,王宏志,等. 一种基于等区域划分的RFID防碰撞算法［J］. 吉林大学学报(理学版), 2020,58(1):120-126.
［5］	刘亮,邢焕革,郭金卫. 奇偶区域搜索反碰撞算法及其仿真分析［J］. 计算机工程与设计, 2010,31(12):2740-2743.
［6］	王静. RFID系统防碰撞算法的研究［D］. 北京:华北电力大学, 2016.
［7］	魏福禄,刘攀,李志斌,等. 基于动态帧时隙ALOHA的危险品运输RFID防碰撞算法［J］. 沈阳工业大学学报， 2020，42（5）：540-544.
［8］	袁莉芬,杜余庆,何怡刚,等. 可并行识别的分组动态帧时隙ALOHA标签防碰撞算法［J］. 电子与信息学报, 2018,40(4):944-950.
［9］	张小红,周伟辉. 动态帧时隙的二进制树RFID防碰撞算法研究［J］. 系统仿真学报, 2018,30(3):1063-1073.
［10］	LEE S R, JOO S D, LEE C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification［C］// Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services. 2005:166-172.
［11］	YU S S, ZHAN Y J， WANG Y H. RFID anti-collision algorithm based on bi-directional binary exponential index［C］// 2007 IEEE International Conference on Automation and Logistics. 2007:2917-2921.
［12］	许建真,郭惠婕,曹雷. 基于优先级的RFID防碰撞算法研究［J］. 南京邮电大学学报(自然科学版), 2017,37(5):56-61.
［13］	南敬昌,樊爽,李蕾,等. 新型锁位式混合查询树射频识别防碰撞算法［J］. 计算机科学与探索, 2019,13(5):765-774.
［14］	侯培国,王志轩,严晨. 基于RFID标签的防碰撞算法改进［J］. 计算机科学, 2019,46(S2):359-362.
［15］	吴劲松. 一种基于二叉树与多叉树搜索的RFID防碰撞算法研究［J］. 电子设计工程, 2020,28(14):59-62.
［16］	汤宏斌,周尚波. 基于锁位的奇偶分区二进制树算法［J］. 重庆邮电大学学报(自然科学版), 2017,29(3):416-420.
［17］	JIA X L， FENG Q Y， MA C Z． An efficient anti-collision protocol for ＲFID tag identification［J］． IEEE Communications Letters， 2010，14(11):1014-1016．
［18］	JIA X L， FENG Q Y， YU L S． Stability analysis of an efficient anti-collision protocol for ＲFID tag identification［J］． IEEE Transactions on Communications， 2012，60(8):2285-2294．
［19］	李川,苏健,刘克雄,等. 基于查询树的防碰撞算法性能分析与研究［J］. 电子学报, 2018,46(11):2671-2678.
［20］	贾小林,冯全源,雷全水. 基于碰撞树的多周期RFID标签识别防碰撞算法研究［J］. 西南科技大学学报, 2014,29(1):39-44.
［21］	严利辉,史长琼,陈蓉,等. 基于奇偶分组的多周期RFID标签防碰撞算法［J］. 计算机工程, 2016,42(2):312-315.
［22］	周伟辉,蒋年德,闫成成,等. 基于ALOHA和多叉树的混合型RFID防碰撞算法［J/OL］. 东华理工大学学报(自然科学版):1-4［2021-01-29］. http://kns.cnki.net/kcms/detail/36.1300.N.20200628.1439.002.html.

[1]	周静, 董国超, 邓祖强, 张金娈, 刘超, 牛永亮 . 基于随机Hash链的双向安全认证RFID协议[J]. 计算机与现代化, 2021, 0(03): 46-50.
[2]	位书敏，张永华，商玉芳. 轻量级移动RFID认证协议研究设计[J]. 计算机与现代化, 2016, 0(11): 74-78.
[3]	褚贵洋. 低成本的RFID网络所有权安全转移算法[J]. 计算机与现代化, 2016, 0(10): 84-87.
[4]	封慧英，周良. 基于滑动窗口的RFID自适应数据清洗算法[J]. 计算机与现代化, 2015, 0(1): 31-36.
[5]	林基艳1，李耀2. 酒后驾驶监控系统车载终端电子标签的设计[J]. 计算机与现代化, 2015, 0(1): 109-112.
[6]	马琰1, 蔡丽霞2,任晓娜2. 一种自适应帧长RFID标签防碰撞算法[J]. 计算机与现代化, 2014, 0(11): 113-116.
[7]	龚华明;阴躲芬. RFID中间件复杂事件处理模型[J]. 计算机与现代化, 2013, 1(9): 232-235.
[8]	时彦艳. 从数字图书馆到智慧图书馆的构建[J]. 计算机与现代化, 2013, 1(6): 192-194.
[9]	王震;吴方;卢恩荣;廖海霖;陈振健. 物联网环境下的餐饮服务系统设计与实现[J]. 计算机与现代化, 2013, 1(5): 142-144,.
[10]	舒远仲;朱玄华;田蕾;张丽;宋利康. 基于构件的RFID中间件管理模块的研究与开发[J]. 计算机与现代化, 2013, 1(3): 78-81.
[11]	陈月梅;蔡坚勇;陈由甲;黄永亮;林鸿. 基于RFID的室内车辆跟踪及定位仿真系统的设计与实现 [J]. 计算机与现代化, 2013, 1(2): 189-193.
[12]	王娜;杨国强. ActiveX技术在RFID系统开发中的应用 [J]. 计算机与现代化, 2013, 1(11): 136-138.
[13]	边江南;刘洪武. 基于无源RFID的最小包容圆自适应定位法[J]. 计算机与现代化, 2013, 1(1): 33-36.
[14]	阴躲芬;龚华明. RFID中间件数据处理模型研究与实现[J]. 计算机与现代化, 2012, 1(9): 200-202.
[15]	张雪. 基于RFID技术的铁路集装箱堆场系统中数据碰撞问题的研究[J]. 计算机与现代化, 2012, 1(9): 166-169.