单堆栈查询码递增深度混合查询树防碰撞算法  

The Anti-collision Algorithm of Single-stack Query Code with Incremental Hybrid Query Tree

作　　者：周艳玲[1] 曹晶 张云翔 ZHOU Yan-ling;CAO Jing;ZHANG Yun-xiang(Department of Artificial Intelligence and Big Data,Hefei University,Hefei,Anhui 230601,China)

机构地区：[1]合肥学院人工智能与大数据学院,安徽合肥230601

出　　处：《沧州师范学院学报》2022年第1期31-37,共7页Journal of Cangzhou Normal University

基　　金：安徽省高校优秀人才培养资助项目“物联网融合环境下的RFID系统防碰撞方案的研究”,编号:gxgwfx2019065;安徽省高等学校省级质量工程大规模在线开放课程(MOOC)示范项目“Java Web技术I”,编号:2019mooc270;安徽省高校教学研究项目“高校智能化实验报告管理系统的设计与实现研究”,编号:2019jyxm0379.

摘　　要：标签碰撞问题是影响射频识别技术(RFID)系统性能的主要问题.概率性标签防碰撞算法存在标签饥饿现象而无法识别部分标签.提出一种确定性的查询树算法,即单堆栈查询码递增深度混合查询树防碰撞算法,它通过生成新的查询码和标签识别两个功能来成功地实现标签的防碰撞.该算法利用设置初始查询码为11码,在每次碰撞后生成的查询码均增加两位码位的方式,它不仅保证了以最少的查询码查询最长的标签位,而且大大地节省了内存空间,查询码所形成的查询树为深度优先遍历混合树.该算法引入单堆栈存储机制,查询码采用深度优先遍历算法.在整个标签识别过程中,改进了查询码生成树的结构,分支节点的度为2或4,这种深度优先遍历和单堆栈机制的结合,有效地缩短了识别时间、节省了内存空间、降低了标签碰撞次数,减少了空查询次数,并且算法简单,容易实现,标签数目增加不会影响算法的效率.Label collision is the main problem that affects the performance of the radio frequency identification(RFID)system.Some tags cannot be identified due to tag starvation in probabilistic tag anti-collision algorithm.This paper proposes a deterministic query tree algorithm,that is,a single-stack query code incremental hybrid query tree,which successfully implements tag anti-collision by generating new query codes and tag identification functions.This algorithm sets11 codes as the initial query code.The query code generated after each collision adds two code points.It not only ensures that the longest tag bit is queried with the least query code,but also greatly savesthe memory space,and the query tree formed by the query code is a depth-first traversal hybrid tree.The algorithm introduces a single-stack storage mechanism,and the query code uses a depth-first traversal algorithm.In the entire tag recognition process,the structure of the query code generation tree is improved,and the degree of branch nodes is 2 or 4.This combination of depth-first traversal and single-stack mechanism effectively shortens the recognition time,saves memory space,and reduces the number of tag collisions and empty queries.This algorithm is simple and easy to implement,and its efficiency will not be affected by the increasing number of tags.

关 键 词：RFID 查询树 防碰撞算法 查询码 深度遍历 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]