基于扁平N叉树搜索的RFID防冲突算法

doi:10.13190/j.jbupt.2014.05.011

北京邮电大学学报 ›› 2014, Vol. 37 ›› Issue (5): 50-55.doi: 10.13190/j.jbupt.2014.05.011

基于扁平N叉树搜索的RFID防冲突算法

赵斌^1,2, 何泾沙^1,3, 黄娜¹, 屈会芳², 刘公政¹

1. 北京工业大学软件学院, 北京 100124;
2. 济宁学院计算机科学系, 山东曲阜 273155;
3. 北京京开投资开发股份有限公司低碳研究中心, 北京 100176

收稿日期:2013-12-01 出版日期:2014-10-28 发布日期:2014-11-07
作者简介:赵斌(1979- ), 男, 讲师, 博士生, E-mail: jnzhaobin@163.com;何泾沙(1961- ), 男, 教授, 博士生导师.
基金资助:
国家自然科学基金项目(61272500);山东省自然科学基金项目(ZR2013FQ024);山东省科学技术发展计划项目(2012RKA08002,2013RKA080070,2014RKB14122);山东省高校科技计划项目(J12LN70,J14LN80);北京市自然科学基金项目(4142008);北京市委、市政府重点工作及区县政府应急项目(Z131100005613030)

An Anti-collision Algorithm Based on Flat-N-tree Search for RFID

ZHAO Bin^1,2, HE Jing-sha^1,3, HUANG Na¹, QU Hui-fang², LIU Gong-zheng¹

1. School of Software Engineering, Beijing University of Technology, Beijing 100124, China;
2. Department of Computer Science, Jining University, Shandong Qufu 273155, China;
3. Low-carbon Research Center, Beijing Development Area Co, Beijing 100176, China

Received:2013-12-01 Online:2014-10-28 Published:2014-11-07

摘要/Abstract

摘要：

防冲突技术是无线射频识别(RFID)系统中的关键技术. 针对二进制搜索防冲突算法读取海量数据标签效率低的问题,通过分析标签数量为海量数据的特征以及标签编码的规律性,基于管理系统中海量数据标签的编码规律和现有二进制搜索算法思想,提出了适合于读取海量数据RFID标签的扁平N叉树搜索防冲突算法. 测试结果表明,该算法在标签总数大于一定数值时,其读取标签效率优于二进制搜索算法.

关键词: 无线射频识别系统, 防冲突, 海量数据, 扁平N叉树

Abstract:

The anti-collision technology is a key technology in the radio frequency identification (RFID) system. In order to avoid the low efficiency problem of reading massive data labels via the binary-tree search algorithm, by analyzing the character of mass data and the regularity of tags encoding, a flat-N-tree search anti-collision algorithm is proposed according to the regularity of massive data tags encoding and the principle of binary-tree search algorithm in the management systems, which is suitable for reading massive data RFID labels. The result shows that the reading efficiency of the multi-tree search algorithm is better than that of the binary-tree search algorithm when the total quantity of tags is greater than a certain value.

Key words: radio frequency identification system, anti-collision, mass data, flat-N-tree

中图分类号:

TN301.6

赵斌, 何泾沙, 黄娜, 屈会芳, 刘公政. 基于扁平N叉树搜索的RFID防冲突算法[J]. 北京邮电大学学报, 2014, 37(5): 50-55.

ZHAO Bin, HE Jing-sha, HUANG Na, QU Hui-fang, LIU Gong-zheng. An Anti-collision Algorithm Based on Flat-N-tree Search for RFID[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2014, 37(5): 50-55.

参考文献

[1] Finkenzeller K. RFID handbook: fundamentals and application in contact-less smart card and identification[M]. 2th ed. England: John Wiley & Sons Inc, 2003.

[2] Eom J B, Lee T J. An efficient framed-slotted ALOHA algorithm with pilot frame and binary selection for anti-collision of RFID tags[J]. IEEE Communications Letters, 2008, 12(11): 861-863.

[3] 胡桂兵, 邱雪松, 孟洛明. 基于信号稳定度提高RFID识别率的方法[J]. 北京邮电大学学报, 2012, 35(1): 55-58. Hu Guibing, Qiu Xuesong, Meng Luoming. An efficient method for RFID's discrimination stability[J]. Beijing University of Posts and Telecommunications, 2012, 35(1): 55-58.

[4] 袁开国, 郝昱文, 李争平, 等. RFID网络中基于Aloha防碰撞的标签数目的联合估计算法[J]. 北京邮电大学学报, 2014, 37(增): 72-76. Yuan Kaiguo, Hao Yuwen, Li Zhengping, et al. A hybrid tag number estimation scheme for Aloha based anti-collision algorithm in RFID networks[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(Sup): 72-76.

[5] 谢磊, 殷亚凤, 陈曦, 等. RFID数据管理: 算法、协议与性能评测[J]. 计算机学报, 2013, 36(3): 457-470. Xie Lei, Yin Yafeng, Chen Xi, et al. RFID data management: algorithms, protocols and performance evaluation[J]. Chinese Journal of Computers, 2013, 36(3): 457-470.

[6] 杜海涛, 徐昆良, 王威廉. 基于返回式二进制树形搜索的反碰撞算法[J]. 云南大学学报: 自然科学版, 2006, 28(S1): 133-136. Du Haitao, Xu Kunliang, Wang Weilian. An anti-collision algorithm based on binary-tree searching of backtracking[J]. Journal of Yunnan University: Natural Sciences Edition), 2006, 28(S1): 133-136.

[7] Djeddou M, Khelladi R, Benssalah M. Improved RFID anti-collision algorithm[J]. Aeu-international Journal of Electronics and Communications, 2013, 67(3): 256-262.

基于扁平N叉树搜索的RFID防冲突算法

An Anti-collision Algorithm Based on Flat-N-tree Search for RFID

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价