基于新颖跳跃式动态搜索的RFID防碰撞算法

doi:10.3724/SP.J.1087.2012.00288

计算机应用 ›› 2012, Vol. 32 ›› Issue (01): 288-291.DOI: 10.3724/SP.J.1087.2012.00288

基于新颖跳跃式动态搜索的RFID防碰撞算法

冯娜¹,潘伟杰¹,李少波¹,²,杨观赐²

1. 教育部现代制造技术重点实验室(贵州大学)，贵阳 550003
2. 中国科学院成都计算机应用研究所，成都 610041

收稿日期:2011-06-22 修回日期:2011-09-05 发布日期:2012-02-06 出版日期:2012-01-01
通讯作者: 潘伟杰
作者简介:冯娜(1984-)，女，内蒙古巴彦淖尔人，硕士研究生，主要研究方向：物联网；潘伟杰(1983-)，男，河南漯河人，博士研究生，主要研究方向：物联网、多目标优化；李少波(1973-)，男，湖南岳阳人，教授，博士生导师，主要研究方向：物联网、计算设计、制造业信息化；杨观赐(1983-)，男，湖南嘉禾人，博士研究生，主要研究方向：计算智能。
基金资助:
教育部新世纪优秀人才支持计划项目(NCET09-0094);国家863计划项目(2009AA043200)

RFID anti-collision algorithm based on novel jumping and dynamic searching

FENG Na¹,PAN Wei-jie¹,LI Shao-bo¹,²,YANG Guan-ci²

1. Key Laboratory of Advanced Manufacturing Technology (Guizhou University), Ministry of Education, Guiyang Guizhou 550003, China
2. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu Sichuan 610041, China

Received:2011-06-22 Revised:2011-09-05 Online:2012-02-06 Published:2012-01-01
Contact: PAN Wei-jie

摘要/Abstract

摘要： 扼要分析目前针对标签防碰撞问题采用的防碰撞算法优缺点的基础上，基于跳跃式动态搜索(JDS)算法的思想，提出了一种新颖的JDS标签防碰撞算法。算法将栈思想引入到新的跳跃式策略前后搜索中，避免出现空闲时隙。在读写器问询时，利用标签反馈信息记忆部分已知信息，采用不定长动态传输方式及调整策略识别标签的未知数据位，减少了读写器搜索次数及系统传输量。算法仿真结果表明，系统传输量大大减少，吞吐量有明显提高。

关键词: 无线射频识别, 防碰撞算法, 调整策略, 跳跃式搜索, 动态传输

Abstract: The paper briefly introduced the merits and shortcomings of the existing anti-collision algorithms. Based on the idea of Jumping and Dynamic Searching (JDS) algorithm, a Novel JDS (NJDS) algorithm for tags' anti-collision was proposed. The algorithm brought stack into the new jumping before and after searching strategy to reduce the number of collision slots and avoid idle slots. When requested by readers, it adopted dynamic transmission and variable length adjustment strategy, and used the known information remembered by the feedback tags' information to identify the unknown data bits of tags, which reduced the number of search of readers and the transmission of system. The analysis on simulation results indicates that the proposed algorithm performs significantly better than the existing anti-collision algorithms. The transmission is greatly reduced, and throughput of the system has increased significantly.

Key words: Radio Frequency Identification (RFID), anti-collision algorithm, adjustment strategy, jumping search, dynamic transmission

中图分类号:

冯娜潘伟杰李少波杨观赐. 基于新颖跳跃式动态搜索的RFID防碰撞算法[J]. 计算机应用, 2012, 32(01): 288-291.

FENG Na PAN Wei-jie LI Shao-bo YANG Guan-ci. RFID anti-collision algorithm based on novel jumping and dynamic searching[J]. Journal of Computer Applications, 2012, 32(01): 288-291.

参考文献

[1]

SCHOUTE F S. Dynamic frame length ALOHA ［J］. IEEE Transactions on Communications Letters, 1983, 31(4): 565-568.

[2]

王亚奇,蒋国平.基于分组机制的跳跃式动态二进制防碰撞算法［J］.自动化学报，2010,36(10):1390-1400.

[3]

王中祥,王俊宇,刘丹,等.BIS:一种降低空时隙开销的RFID防碰撞算法［J］.通信学报,2009,30(9):1-7.

[4]

程文青,赵梦欣,徐晶,等.改进的RFID动态帧时隙ALOHA算法［J］.华中科技大学学报:自然科学版,2007,35(6):14-16.

[5]

LEE S-R, JOO S-D, LEE C-W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification ［C］// Proceedings of the Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services. Washington, DC: IEEE Computer Society, 2005: 166-172.

[6]

LIN C-F, LIN F Y-S. Efficient estimation and collision-group-based anticollision algorithms for dynamic frame-slotted ALOHA in RFID networks ［J］. IEEE Transactions on Automation Science and Engineering, 2010, 7(4): 840-848.

[7]

CAPETANAKIS J I. Tree algorithms for packet broadcast channels ［J］. IEEE Transactions on Information Theory, 1979, 25(5): 505-515.

[8]

鞠伟成,俞承芳.一种基于动态二进制的RFID抗冲突算法［J］.复旦学报:自然科学版,2005,44(1):46-50.

[9]

WANG T-P. Enhanced binary search with cut-through operation for anti-collision in RFID systems ［J］. IEEE Communications Letters, 2006, 10(4): 236-238.

[10]

SHI X-L, SHI X-W, HUANG Q-L, et al. An enhanced binary anti-collision algorithm of backtracking in RFID system ［J］. Progress in Electromagnetics Research B, 2008, 4: 263-271.

[11]

SHI X-L, WEI F, HUANG Q-L, et al. Novel binary search algorithm of backtracking for RFID tag anti-collsion ［J］. Progress in Electromagnetics Research B, 2008, 9: 97-104.

[12]

余松森,詹宜巨,王志平,等.跳跃式动态树形反碰撞算法及其分析［J］.计算机工程,2005,31(9):19-21.

[13]

王雪,钱志鸿,胡正超,等.基于二叉树的RFID防碰撞算法的研究［J］.通信学报,2010,31(6):49-57.

[1]	吴恺凡, 殷新春. 基于随机运算符的轻量级匿名射频识别系统双向认证协议[J]. 计算机应用, 2021, 41(6): 1621-1630.
[2]	徐晓翔, 常相茂, 陈方进. 基于RFID标签阵列的睡眠期间呼吸量连续监测系统[J]. 计算机应用, 2020, 40(5): 1534-1538.
[3]	黄可可, 刘亚丽, 殷新春. 基于位重排变换的超轻量级RFID双向认证协议[J]. 计算机应用, 2019, 39(1): 118-125.
[4]	丁建立, 韩宇超, 王家亮. 基于粗精二次估计的RFID标签数目估算方法[J]. 计算机应用, 2017, 37(9): 2722-2727.
[5]	龙昭华, 宫腾飞. 基于非空时隙数的无线射频识别标签估算算法[J]. 计算机应用, 2016, 36(1): 101-106.
[6]	潘昊, 陈蒙. 物联网中无线射频识别读写器系统防碰撞算法优化[J]. 计算机应用, 2015, 35(1): 23-26.
[7]	李佳郑义平刘春龙. 内嵌安全机制的RFID防碰撞策略[J]. 计算机应用, 2014, 34(1): 99-103.
[8]	钱晓捷郭洪圆田阳光. 基于0-1分布的RFID标签估计算法[J]. 计算机应用, 2013, 33(08): 2128-2131.
[9]	陈荣伶王玉皞刘祎陈中平. 基于标签分组的RFID防碰撞算法[J]. 计算机应用, 2013, 33(08): 2132-2135.
[10]	袁正午段莉丹. 改进的基于堆栈存储的二进制搜索算法[J]. 计算机应用, 2012, 32(11): 3089-3091.
[11]	夏宏吴济文. 超高频RFID读写器系统的设计与实现[J]. 计算机应用, 2012, 32(08): 2369-2373.
[12]	张顺陈海进. 轻量级的无线射频识别安全认证协议[J]. 计算机应用, 2012, 32(07): 2010-2014.
[13]	唐有卢元元张翌维. 基于RFID系统的混沌动态扰动算法[J]. 计算机应用, 2012, 32(06): 1643-1645.
[14]	唐拥政王明辉王建东. EPC Gen2标准下强安全射频识别认证协议[J]. 计算机应用, 2012, 32(04): 968-970.
[15]	丁治国朱学永雷迎科王心灵. 基于启发式函数的多叉树防碰撞算法[J]. 计算机应用, 2012, 32(03): 665-668.

基于新颖跳跃式动态搜索的RFID防碰撞算法

RFID anti-collision algorithm based on novel jumping and dynamic searching

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics