分裂二进制追踪树标签防碰撞协议  

Novel Tag Anticollision Protocol with Splitting Binary Tracking Tree

作　　者：李占青 李光顺 吴俊华 孔令增 LI Zhan-qing;LI Guang-shun;WU Jun-hua;KONG Ling-zeng(School of Information Science and Engineering,Qufu Normal University,Rizhao276826,China)

机构地区：[1]曲阜师范大学信息科学与工程学院,日照276826

出　　处：《计算机科学》2017年第12期80-85,104,共7页Computer Science

基　　金：国家自然科学基金项目(61373027);山东省自然科学基金项目(ZR2012FM023);山东省优秀中青年科学家科研奖励基金(BS2014DX005);山东省高校科技计划项目(J14LN38);山东省研究生教育创新计划项目(SDYY14052);曲阜师范大学科技计划项目(xkj201525)资助

摘　　要：针对大规模RFID系统中的标签碰撞问题,提出了一种位追踪技术与最优分割理论相结合的标签防碰撞协议。该协议由二进制分裂过程与二进制追踪树识别过程这两个阶段组成。在分裂过程中,随机选择0或1可将当前响应标签集合进行二分,在得到可读时隙或空闲时隙时停止。在识别过程中,由于二分得到的左右子集合标签数近似相等,因此运用最优分割理论对左子集合标签数进行处理以得到右子集合的时隙数,自底向上在各右子集合上采用二进制追踪树时隙算法来完成对标签的识别。分裂过程简单、易实施,识别过程无需预先估计标签数量,对设备计算能力的要求低,设置最优分隔可明显减少空闲时隙。理论分析及仿真结果表明,该协议能够提高RFID系统的识别效率,在大规模RFID系统中性能更优。To solve the problem of tag collision in large scale RFID(Radio Frequency Identify)systems,a new tag anticollisionprotocol was proposed which combines the bit tracking technology and the optimal partition theory.The protocolconsists of two phases,namely,a binary splitting phase and a binary tracking tree identifying phase.The first phase repeatedly divides the set of the current response tags into two subsets by choosing"0"or"1"randomly until a readable slot or an idle slot is obtained.The second phase first handles the number of tags in the left subset by using the optimal partition theory to obtain the size of slots in the right subset.And then the second phase finishes the identification of tags by utilizing the binary tracking tree slot algorithm on all right subsets in a bottom-up manner.The splitting process is simple and easy to implement,and the recognition process is not required to estimate the number of tags in advance,so the computing power of the device is low,moreover,the optimal partition can obviously reduce the idle slots.Theoreticalanalysis and simulation results demonstrate that the protocol can improve identification efficiency and do better in large scale RFID system.

关 键 词：标签碰撞 位追踪 最优分割 二进制分裂 二进制追踪树 

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