LRST：低冗余搜索树防碰撞算法

doi:10.3969/j.issn.1000-436x.2014.06.014

通信学报 ›› 2014, Vol. 35 ›› Issue (6): 110-115.doi: 10.3969/j.issn.1000-436x.2014.06.014

LRST：低冗余搜索树防碰撞算法

黄琼¹,凌江涛¹,张敏²,阳小龙²

¹ 重庆邮电大学移动通信技术重点实验室，重庆400065
² 北京科技大学先进网络技术与新业务研究所，北京100083

出版日期:2014-06-25 发布日期:2017-06-29
基金资助:
国家重点基础研究发展计划（“973”计划）基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;长江学者和创新团队发展计划基金资助项目;重庆市科委重点实验室专项经费基金资助项目

LRST: searching tree anti-collision algorithm with low-redundancy

Qiong HUANG¹,Jiang-tao LING¹,Min ZHANG²,Xiao-long YANG²

¹ Key Laboratory of Mobile Communication Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
² Institute of Advanced Network Technology and New Services, University of Science and Technology Beijing, Beijing 100083, China)

Online:2014-06-25 Published:2017-06-29
Supported by:
The National Basic Research Program of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;Changjiang Scholars and Innovative Research Team in University;The Special Fund of Chongqing Key Laboratory

摘要/Abstract

摘要：

针对RFID标签防碰撞树型算法在识别过程中因询问命令过多、过长而产生大量冗余数据导致通信开销过大的问题，在后退式动态搜索树算法的基础上提出一种低冗余搜索树防碰撞算法（LRST）：为减少询问次数，提出了“一问两答”询问方式，即碰撞标签根据最高碰撞位比特分别在第一个时隙或第二个时隙响应；为减小询问命令的长度，用计数器替代标签中的前缀匹配电路，使算法不再需要前缀作为询问命令的标识参数；此外，提出的预测识别和标签屏蔽机制规避了不必要的询问。理论分析和仿真结果表明，通信开销大大降低。

关键词: RFID, 防碰撞, 搜索树, 低冗余

Abstract:

During the RFID tag identification process, the tree-based anti-collision algorithms usually incur large amount of redundant data due to an excess of long query commands,which increases the communication overhead. To resolve this problem, a searching tree anti-collision algorithm with low-redundancy on the basis of regressive-style dynamic searching tree algorithm was proposed. In order to reduce the number of queries, a novel query mode was developed, i.e., single query with duo responses. Depending on the most significant collided bit, the collided tags respond in the first or second slot separately. In order to reduce the length of query command, the prefix matching circuit in tag was replaced with a counter, which eliminated the prefix as the parameter of query command. The predictive identification and block-ing technique were also introduced to avoid unnecessary queries. Theoretical analysis and simulation results show that the communication overhead is greatly reduced.

Key words: RFID, anti-collision, searching tree, low-redundancy

黄琼,凌江涛,张敏,阳小龙. LRST：低冗余搜索树防碰撞算法[J]. 通信学报, 2014, 35(6): 110-115.

Qiong HUANG,Jiang-tao LING,Min ZHANG,Xiao-long YANG. LRST: searching tree anti-collision algorithm with low-redundancy[J]. Journal on Communications, 2014, 35(6): 110-115.

图/表 11

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

参考文献 11

[1]	LIU H C . The approaches in solving passive RFID tag collision prob-lems[J]. Radio Frequency Identification Fundamentals and Applica-tions, 2010,3: 49-56.
[2]	KLAIR D K C , CHIN K W , RAAD R . A survey and tutorial of RFID anti-collision protocols[J]. IEEE Communications Surveys＆ Tutorials, 2010,12(3):400-421.
[3]	FINKENZELLER K . RFID-Handbook Fundamentals and Applica-tions in Contactless Smart Cards and Identification (2nd Edition)[M]. HoboRen: Jahn: Wiley and Sons Inc, 2003.
[4]	SHIH B Y , CHEN C W , CHEN C Y . Merged search algorithms for radio frequency identification anticollision[J]. Mathematical Problems in Engineering, 2012,2012: 1-20.
[5]	YU S S , ZHAN Y J , WANG Z P . Anti-collision algorithm based on jumping and dynamic searching and its analysis[J]. Computer Engi-neering, 2005,31: 19-20.
[6]	HU J G , LIN K , WANG D M . A novel anti-collision algorithm for RFID system[A]. Program for the IEEE International Conference on RFID-Technology and Applications, Guangzhou, China, 2010.302-307.
[7]	KIM S S , KIM Y H , LEE S J . An improved anti collision algorithm using parity bit in RFID system[A]. Korea Seventh IEEE International Symposium on Network Computing and Applications[C]. 2008.224-227.
[8]	JIA X L , FENG Q Y , YU L H . Stability analysis of an efficient anti-collision protocol for RFID tag identification[J]. IEEE Transac-tions on Communications, 2012,60(8): 2285-2294.
[9]	DANG F , YANG X L , LONG K P . Spray and forward: efficient rout-ing based on the Markov location prediction model for DTN[J]. Sci-ence China Information Sciences, 2012,55(2): 433-440.
[10]	周艳聪，孙晓晨顾军华 . 一种改进二进制防碰撞算法研究[J]. 计算机应用研究， 2012,29(1): 256-262. ZHOU Y C , SUN X C , GU J H . Research on improve binary anti-collision algorithm[J]. Application Research of Computers, 2012,29(1): 256-262.
[11]	王雪，钱志鸿，胡正超 . 基于二叉树的 RFID 防碰撞算法的研究[J]. 通信学报， 2010,31(6): 49-57. WANG X , QIAN Z H , HU Z C . Research on RFID anti-collision al-gorithms based on binary tree[J]. Journal on Communications, 2010,31(6): 49-57.

[1]	李骜, 王卓, 于晓洋, 陈德运, 张英涛, 孙广路. 多核低冗余表示学习的稳健多视图子空间聚类方法[J]. 通信学报, 2021, 42(11): 193-204.
[2]	张莉涓, 范明秋, 雷磊, 王勇, 袁代数. 捕获效应下基于比特检测的多分支树RFID标签识别协议[J]. 通信学报, 2021, 42(11): 205-216.
[3]	付钰,钱志鸿,程超,刘晓慧. 基于分组机制的位仲裁查询树防碰撞算法[J]. 通信学报, 2016, 37(1): 123-129.
[4]	张兴，韩冬，曹光辉，贾旭. 基于PRESENT算法的RFID安全认证协议[J]. 通信学报, 2015, 36(Z1): 65-74.
[5]	王雪,钱志鸿,刘晓慧,程超. 改进的树型结构RFID防碰撞算法[J]. 通信学报, 2015, 36(7): 129-137.
[6]	吴海锋,曾玉. 物理层的超高频RFID标签信号分离[J]. 通信学报, 2015, 36(2): 20-28.
[7]	朱大立，荣文晶，王思叶，庞娜. 基于树形模型的轻量级RFID组证明协议[J]. 通信学报, 2015, 36(11): 15-24.
[8]	杨茜，吴海锋，曾玉. 捕获效应下RFID标签的CATPE防冲突协议[J]. 通信学报, 2014, 35(7): 26-222.
[9]	袁红林，包志华. 基于对数谱射频指纹识别的RFID系统信息监控方法[J]. 通信学报, 2014, 35(7): 11-93.
[10]	袁红林,包志华,严燕. 基于对数谱射频指纹识别的RFID系统信息监控方法[J]. 通信学报, 2014, 35(7): 86-93.
[11]	杨茜,吴海锋,曾玉. 捕获效应下RFID标签的CATPE防冲突协议[J]. 通信学报, 2014, 35(7): 215-222.
[12]	黄琼，凌江涛，张敏，阳小龙. LRST：低冗余搜索树防碰撞算法[J]. 通信学报, 2014, 35(6): 14-116.
[13]	杨玉龙,彭长根,周洲,张晓培. 基于Edwards曲线的移动RFID安全认证协议[J]. 通信学报, 2014, 35(11): 132-138.
[14]	杨玉龙，彭长根，周洲，张晓培. 基于Edwards曲线的移动RFID安全认证协议[J]. 通信学报, 2014, 35(11): 15-137.
[15]	陈兵，郑嘉琦. 轻型的RFID安全认证协议LAP[J]. 通信学报, 2013, 34(Z1): 1-7.

LRST：低冗余搜索树防碰撞算法

LRST: searching tree anti-collision algorithm with low-redundancy

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 11

相关文章 15

Metrics

推荐阅读 0