基于信息预处理的分组动态二进制防碰撞算法

J4 ›› 2014, Vol. 36 ›› Issue (10): 2041-2046.

• 论文 • 上一篇

基于信息预处理的分组动态二进制防碰撞算法

周艳聪1,2,董永峰2,崔晓欣2,杨阔1

(1.天津商业大学信息工程学院，天津 300134;2.河北工业大学计算机科学与软件学院,天津 300401)

收稿日期:2014-06-11 修回日期:2014-08-02 出版日期:2014-10-25 发布日期:2014-10-25
基金资助:
天津市应用基础与前沿技术研究计划重点项目（12JCZDJC21200,14JCYBJC15900）;全国大学生创新创业训练计划项目(201310069016)

A grouping dynamic binary anti-collision algorithm
based on information preprocessing

ZHOU Yancong1,2,DONG Yongfeng2,CUI Xiaoxin2,YANG Kuo1

(1.School of Information Engineering,Tianjin University of Commerce,Tianjin 300134;
2.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China)

Received:2014-06-11 Revised:2014-08-02 Online:2014-10-25 Published:2014-10-25

摘要/Abstract

摘要：

针对现有二进制防碰撞算法通信数据量大、存在冗余信息的缺点，提出了一种新二进制防碰撞算法。新算法在阅读器与标签的首次通信中首先进行信息预处理，后继识别过程中只处理冲突位，然后利用每次探测得到的碰撞位信息构造二叉树。最高碰撞位之前的部分后接一个“0”为左子树，最高碰撞位之前的部分后接一个“1”+两个最高碰撞位之间的部分为右子树，在叶子结点实现标签的识别。该算法从阅读器和标签两方面同时进行改进，减少了通信量，提高了识别效率。

关键词: 信息预处理, 防碰撞, 二叉树, 射频识别

Abstract:

In order to overcome the shortcomings of binary anti-collision,such as more communication data and communication time,a novel dynamic binary anticollision algorithm is proposed.In the new algorithm,the ID information is preprocessed in the first communication between the reader and tags,and then only the collision bits are handled in the next process.The binarytree is constructed by the deleted collision bits accordingly.The bits before the highest collision bit followed by "0" constitute the left subtree.The bits before the highest collision bit followed by "1" and the bits between the highest collision bit and the second highest one constitute the right subtree. Then the tags are identified at leaf level.The new algorithm is improved for both reader and tags, so that it reduces the amount of communication data and improves the recognition efficiency.

Key words: information preprocessing;anti-collision;binary-tree;radio frequency identification

周艳聪1,2,董永峰2,崔晓欣2,杨阔1. 基于信息预处理的分组动态二进制防碰撞算法[J]. J4, 2014, 36(10): 2041-2046.

ZHOU Yancong1,2,DONG Yongfeng2,CUI Xiaoxin2,YANG Kuo1. A grouping dynamic binary anti-collision algorithm
based on information preprocessing [J]. J4, 2014, 36(10): 2041-2046.

参考文献［13］

［1］	Klair D K, KwanWu Chin, Raad R. A survey and tutorial of RFID anticollision protocols［J］. IEEE Communications Surveys and Tutorials, 2012,12(3):400421.
［2］	Law C，Lee K，Suik Y． Efficient memoryless protocol for tag identifycation［C］∥Proc of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications，2000: 7584．
［3］	Leongk S，Ngm L，Grassoa R，et al．Synchronization of RFID readers for dense RFID reader environments［C］∥Proc of International Symposium on Applications on Internet Workshops，2006: 295298．
［4］	He Mingxing， Horng Shijinn， Fan Pingzhi， et al. A fast RFID tag identification algorithm based on counter and stack［J］.Expert Systems with Applications，2011,38（6）：68296838.
［5］	Chen Y H，Horng S J，Tun R S．A novel anticollision algorithm in RFID systems for identifying passive tags［J］．IEEE Transactions on Industrial Informatics，2010，6(1):105121．
［6］	Vogt H.Multiple object identification with passive RFID tags systems［J］. Systems, Man and Cybernetics, 2002(3)：69.
［7］	Yu Songsen, Zhan Yiju, Peng Weidong, et al. An anticollision algorithm based on binarytree searching of regressive index and its practice［J］. Computer Engineering and Applications, 2004，40（16）：2628.(in Chinese)
［8］	Li Yizhang,Dai Xuefeng,Liu Shudong.RFID binary search algorithm to achieve improvement and anticollision ［J］.Journal of Qiqihar University,2009,25(1):2629.(in Chinese)
［9］	Hou Shengyu, Feng Feng. Improved binary tree anticollision algorithm in RFID system［J］. Computer Engineering and Applications, 2013, 49（4）：129133.(in Chinese)
［10］	Xiao Yaoyou,Hu Gang,Wei Qinwei,et al. Dynamic anticollision algorithm based on binarytree disassembling ［J］.Communications Technology,2011,44(1):99101.(in Chinese)
［11］	Wu Yueqian, Gu Daguang, Fan Zhenyue, et al. Comparison and analysis of anticollision in RFID system and improved algorithm［J］. Computer Engineering and Applications, 2009，45（3）：210213.(in Chinese)
［12］	Yuan Zhengwu，Duan Lidan. Enhanced binary search algorithm based on stack storage［J］.Journal of Computer Applications,2012,32(11):30893091.(in Chinese)
［13］	Jiang Yu, Ma Manfu. RFID bit match anticollision algorithm in Internet of Things［J］.Application Research of Computers, 2012,29（1）：8891.(in Chinese)
	附中文参考文献：
［7］	余松森, 詹宜巨, 彭卫东,等.基于后退式索引的二进制树形搜索反碰撞算法及其实现［J］.计算机工程与应用，2004,40(16):2628.
［8］	李宜章,戴学丰,刘树东.RFID二进制搜索算法的改进及其防碰撞实现［J］. 齐齐哈尔大学学报,2009,25(1):2629.
［9］	侯胜宇,冯锋. 一种改进的二叉树型RFID防碰撞算法［J］. 计算机工程与应用, 2013，49(4):129133.
［10］	萧耀友,胡钢,魏钦伟,等.基于二进制树分解的动态防碰撞算法［J］.通信技术,2011,44(1):99101.
［11］	吴跃前,辜大光,范振粤,等.RFID 系统防碰撞算法比较分析及其改进算法［J］. 计算机工程与应用, 2009，45(3):210213.
［12］	袁正午,段莉丹.改进的基于堆栈存储的二进制搜索算法［J］. 计算机应用,2012,32(11):30893091.
［13］	江雨,马满福. 物联网中RFID 位匹配防碰撞算法［J］. 计算机应用研究,2012,29(1):8891.

[1]	牛琨, 高仲合, 张凡. 面向整体区域的改进VIRE定位算法研究[J]. 计算机工程与科学, 2022, 44(09): 1602-1609.
[2]	杨帆1,2,任守纲3,徐焕良3,孙元昊2,杨星2. 基于比特估计的RFID标签数量估计算法[J]. 计算机工程与科学, 2020, 42(03): 449-455.
[3]	李松1，孙子文1,2. 基于PUF适用于大规模RFID系统的移动认证协议[J]. 计算机工程与科学, 2018, 40(06): 1046-1053.
[4]	何志军,何洪英,黄旭. 改进十字链表的存储方法在短路电流计算中的应用[J]. 计算机工程与科学, 2017, 39(04): 648-655.
[5]	魏国珩1,2，汪亚2，张焕国1. 面向RFID应用的GF(2m)域上ECC点乘运算的轻量化改进研究[J]. 计算机工程与科学, 2017, 39(01): 81-85.
[6]	胡应梦,张小红. 基于混沌加密的可同步更新RFID双向认证协议[J]. J4, 2016, 38(07): 1376-1383.
[7]	杨帆1，徐焕良2，谢俊1，任守纲2. 基于双空闲因子的RFID防碰撞算法研究[J]. 计算机工程与科学, 2016, 38(07): 1440-1446.
[8]	沈郭浩，马永涛,刘开华，赵宇. 非视距环境下室内RFID标签定位算法研究[J]. J4, 2016, 38(03): 454-459.
[9]	陈平华，陈传瑜. 基于满二叉树的二分K-means聚类并行推荐算法[J]. J4, 2015, 37(08): 1450-1457.
[10]	朱峰军1，武继刚1, 2，史雯隽1，姜桂圆3. 多选择软硬件划分问题的计算模型与动态规划算法[J]. J4, 2015, 37(04): 641-648.
[11]	张红泰，刘宏立，刘述钢. 基于满二叉树的RA码交织器设计[J]. J4, 2015, 37(04): 699-703.
[12]	张小红，穆宇超. 盲分离的帧时隙超高频RFID系统防碰撞算法[J]. J4, 2015, 37(03): 559-565.
[13]	李文晓，李建成，李聪，王震，尚靖. 一种面向无源RFID电子标签的电流灵敏放大器设计[J]. J4, 2014, 36(12): 2361-2366.
[14]	姚仲敏，姚天健，龙昭鹏，李强. 基于物联网技术的出租车调度系统设[J]. J4, 2014, 36(08): 1476-1481.
[15]	付华伟1，何小敏1，许亮1,3，李秀喜2，黄志平3. 基于RFID和遗传算法的实时炸药仓储优化操作[J]. J4, 2014, 36(02): 286-291.

基于信息预处理的分组动态二进制防碰撞算法

A grouping dynamic binary anti-collision algorithm
based on information preprocessing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［13］

相关文章 15

编辑推荐

Metrics

本文评价

基于信息预处理的分组动态二进制防碰撞算法

A grouping dynamic binary anti-collision algorithm based on information preprocessing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［13］

相关文章 15

编辑推荐

Metrics

本文评价

A grouping dynamic binary anti-collision algorithm
based on information preprocessing

参考文献［13］