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

doi:10.11896/j.issn.1002-137X.2017.12.016

计算机科学 ›› 2017, Vol. 44 ›› Issue (12): 80-85.doi: 10.11896/j.issn.1002-137X.2017.12.016

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

李占青,李光顺,吴俊华,孔令增

曲阜师范大学信息科学与工程学院日照276826,曲阜师范大学信息科学与工程学院日照276826,曲阜师范大学信息科学与工程学院日照276826,曲阜师范大学信息科学与工程学院日照276826

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受国家自然科学基金项目(61373027),山东省自然科学基金项目(ZR2012FM023),山东省优秀中青年科学家科研奖励基金(BS2014DX005),山东省高校科技计划项目(J14LN38),山东省研究生教育创新计划项目(SDYY14052),曲阜师范大学科技计划项目(xkj201525)资助

Novel Tag Anticollision Protocol with Splitting Binary Tracking Tree

LI Zhan-qing, LI Guang-shun, WU Jun-hua and KONG Ling-zeng

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 针对大规模RFID系统中的标签碰撞问题,提出了一种位追踪技术与最优分割理论相结合的标签防碰撞协议。该协议由二进制分裂过程与二进制追踪树识别过程这两个阶段组成。在分裂过程中,随机选择0或1可将当前响应标签集合进行二分,在得到可读时隙或空闲时隙时停止。在识别过程中,由于二分得到的左右子集合标签数近似相等,因此运用最优分割理论对左子集合标签数进行处理以得到右子集合的时隙数,自底向上在各右子集合上采用二进制追踪树时隙算法来完成对标签的识别。分裂过程简单、易实施,识别过程无需预先估计标签数量,对设备计算能力的要求低,设置最优分隔可明显减少空闲时隙。理论分析及仿真结果表明,该协议能够提高RFID系统的识别效率,在大规模RFID系统中性能更优。

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

Abstract: To solve the problem of tag collision in large scale RFID (Radio Frequency Identify) systems,a new tag anti-collision protocol was proposed which combines the bit tracking technology and the optimal partition theory.The protocol consists 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.Theoreti-cal analysis and simulation results demonstrate that the protocol can improve identification efficiency and do better in large scale RFID system.

Key words: Tag collision,Bit tracking,Optimal partition,Binary splitting,Binary tracking tree

李占青,李光顺,吴俊华,孔令增. 分裂二进制追踪树标签防碰撞协议[J]. 计算机科学, 2017, 44(12): 80-85. https://doi.org/10.11896/j.issn.1002-137X.2017.12.016

LI Zhan-qing, LI Guang-shun, WU Jun-hua and KONG Ling-zeng. Novel Tag Anticollision Protocol with Splitting Binary Tracking Tree[J]. Computer Science, 2017, 44(12): 80-85. https://doi.org/10.11896/j.issn.1002-137X.2017.12.016

参考文献

[1] XIA J M,XIAO G Q,CHEN K,et al.Framed slotted ALOHA anti-collision algorithm using hybrid spill-tree[J].Computer Science,2014,1(12):67-69.(in Chinese) 夏静满,肖国强,陈凯,等.基于混合溢出树搜索的帧时隙ALOHA防碰撞算法[J].计算机科学,2014,1(12):67-69.
[2] ZHOU F,JIN D,HUANG C,et al.Optimize the power consumption of passive electronic tags for anti-collision schemes[C]∥Proceedings of the 5th International Conference on Association for Science and Information on Coffee.New York:IEEE Press,2003:1213-1217.
[3] CHEN W C,HORNG S J,FAN P.An enhanced anti-collision algorithm in RFID based on counter and stack[C]∥Proceedings of the Second International Conference on Systems and Networks Communications.New York:IEEE Press,2007:1-4.
[4] CHEN Y H,HORNG S J,RUN R S,et al.A novel anti-collision algorithm in RFID systems for identifying passive tags[J].IEEE Transactions on Industrial Informatics,2010,6(1):105-121.
[5] ZHANG L,ZHANG J,TANG X.Assigned tree slotted Aloha RFID tag anti-collision protocols[J].IEEE Transactions on Wireless Communications,2013,2(11):5493-5505.
[6] LAI Y C,HSIAO L Y,CHEN H J,et al.A Novel Query Tree Protocol with Bit Tracking in RFID Tag Identification[J].IEEE Transactions on Mobile Computing,2012,2(10):2063-2075.
[7] LAI Y C,HSIAO L Y,LIN B S.Optimal Slot Assignment for Binary Tracking Tree Protocol in RFID Tag Identification[J].IEEE/ACM Transactions on Networking,2015,3(1):255-268.
[8] WANG X,JIA Q X,GAO X,et al.Highly efficient RFID adaptive tracking tree anti-collision algorithm[J].Journal of Jilin University (Engineering and Technology Edition),2015,5(4):1225-1233.(in Chinese)王鑫,贾庆轩,高欣,等.高效无线射频识别自适应型跟踪树防碰撞算法[J].吉林大学学报(工学版),2015,5(4):1225-1233.
[9] WANG X,JIA Q X,GAO X,et al.Research on grouping n-ray tracking tree RFID anti-collision algorithm[J].Acta Electronica Sinica,2016,4(2):437-444.(in Chinese) 王鑫,贾庆轩,高欣,等.分组N叉跟踪树型RFID防碰撞算法研究[J].电子学报,2016,4(2):437-444.
[10] HU Y M,ZHANG X H.Research of an adaptive searching anti-collision algorithm for RFID based on information-bit encoding[J].Acta Electronica Sinica,2016,4(8):1791-1798.(in Chinese) 胡应梦,张小红.基于信息位编码的自适应搜索RFID防碰撞算法研究[J].电子学报,2016,4(8):1791-1798.
[11] LA P T,MASELLI G,PETRIOLI C.Anticollision protocols for single-reader RFID systems:temporal analysis and optimization[J].IEEE Transactions on Mobile Computing,2011,0(2):267-279.
[12] WU H F,ZENG Y,FENG J H.Passive RFID tag anti-collision binary tree slotted protocol without tags quantity estimation[J].Journal of Computer Research and Development,2012,49(9):1959-1971.(in Chinese) 吴海锋,曾玉,丰继华.无标签数估计的被动RFID标签防冲突二进制树时隙协议[J].计算机研究与发展,2012,9(9):1959-1971.
[13] WU H,ZENG Y,FENG J,et al.Binary tree slotted ALOHA for passive RFID tag anticollision[J].IEEE Transactions on Parallel and Distributed Systems,2013,4(1):19-31.
[14] SU J,SHENG Z,XIE L,et al.Idle-Slots elimination based binary splitting (ISE-BS) anti-collision algorithm for RFID[J].IEEE Communications Letters,2016,20(12):2394-2397.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

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

Novel Tag Anticollision Protocol with Splitting Binary Tracking Tree

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0