基于分组映射的防碰撞查询树算法

doi:10.19678/j.issn.1000-3428.0055410

计算机工程 ›› 2020, Vol. 46 ›› Issue (8): 184-189,196. doi: 10.19678/j.issn.1000-3428.0055410

基于分组映射的防碰撞查询树算法

董轩江, 李世宝, 蔡丽萍, 袁静

中国石油大学(华东) 计算机与通信工程学院, 山东青岛 266580

收稿日期:2019-07-08 修回日期:2019-08-16 发布日期:2019-08-21
作者简介:董轩江(1994-),男,硕士研究生,主研方向为射频识别通信;李世宝,副教授、硕士;蔡丽萍,高级工程师、硕士;袁静,硕士研究生。
基金资助:
国家自然科学基金（61872385）；中央高校基本科研业务费专项资金（18CX02134A，18CX02137A，19CX05003A-4）。

Anti-collision Query Tree Algorithm Based on Group Mapping

DONG Xuanjiang, LI Shibao, CAI Liping, YUAN Jing

College of Computer and Communication Engineering, China University of Petroleum(East China), Qingdao, Shandong 266580, China

Received:2019-07-08 Revised:2019-08-16 Published:2019-08-21

摘要/Abstract

摘要： 针对射频识别防碰撞系统多标签识别效率低、识别时隙长的问题，提出一种基于双重分组和对位映射的防碰撞查询树算法。按照识别码位数和异或运算结果对标签进行横向和纵向双重分组，并分别赋予不同的组标签，再基于对位映射规则根据组标签和识别码得到不同的映射数据。在此基础上，阅读器利用映射规律反推出碰撞信息得到查询前缀，并对碰撞信息进行分组、解码、入栈和出栈，最终完成标签识别。仿真结果表明，与传统查询树算法、八叉树搜索算法、A4PQT以及GBAQT算法相比，该算法能有效减少识别总时隙数，提高系统效率。

关键词: 射频识别, 标签防碰撞算法, 查询树, 双重分组, 映射机制

Abstract: To address the low efficiency caused by the long time slots of multi-tag identification in Radio Frequency Identification(RFID)-based anti-collision system,this paper proposes an anti-collision query tree algorithm based on aligning mapping and double grouping.The tags are horizontally grouped according to the number of digits of identification codes and vertically grouped according to the XOR results of identification codes.Different group labels are assigned to different groups.Then based on the contraposition mapping rules,different mapping data are obtained according to the group label and identification code.On this basis,the reader uses the mapping law to implement backward reasoning for the collision information,so as to obtain the query prefix.Finally,the collision information is grouped,decoded,pushed and popped out of the stack to complete tag identification.Simulation results show that compared with the traditional query tree algorithm,octree search algorithm,A4PQT and GBAQT algorithm,the proposed algorithm can effectively reduce the total number of time slots and improve system efficiency.

Key words: Radio Frequency Identification(RFID), tag anti-collision algorithm, query tree, double grouping, mapping mechanism

中图分类号:

TP301.6

董轩江, 李世宝, 蔡丽萍, 袁静. 基于分组映射的防碰撞查询树算法[J]. 计算机工程, 2020, 46(8): 184-189,196.

DONG Xuanjiang, LI Shibao, CAI Liping, YUAN Jing. Anti-collision Query Tree Algorithm Based on Group Mapping[J]. Computer Engineering, 2020, 46(8): 184-189,196.

https://www.ecice06.com/CN/Y2020/V46/I8/184

图/表 12

20200819135534

20200819135537

20200819135540

20200819135544

20200819135547

20200819135550

20200819135553

20200819135558

20200819135601

20200819135605

20200819135608

20200819135611

参考文献

[1] NING Huansheng,XU Qunyu.Research on global Internet of things' developments and it's lonstruction in china[J].Acta Electronica Sinica,2010,38(11):2590-2599.(in Chinese) 宁焕生,徐群玉.全球物联网发展及中国物联网建设若干思考[J].电子学报,2010,38(11):2590-2599.
[2] HSU C H,CHAO H,HYUK PARK J.Threshold jumping and wrap-around scan techniques toward efficient tag identification in high density RFID systems[J].Information Systems Frontiers,2011,13(4):471-480.
[3] ALI K,HASSANEIN H,TAHA A E M.RFID anti-collision protocol for dense passive tag environments[C]//Proceedings of the 32ndIEEE Conference on Local Computer Networks.Dublin,Ireland:IEEE Press,2007:819-824.
[4] LI Meng,QIAN Zhihong,ZHANG Xu,et al.Slot-predicting based ALOHA algorithm for RFID anti-collision[J].Journal on Communications,2011,32(12):43-50.(in Chinese) 李萌,钱志鸿,张旭,等.基于时隙预测的RFID防碰撞ALOHA算法[J].通信学报,2011,32(12):43-50.
[5] ZANELLA A.Adaptive batch resolution algorithm with deferred feedback for wireless systems[J].IEEE Transactions on Wireless Communications,2012,11(10):3528-3539.
[6] ZHU L,YUM T.Optimal framed aloha based anti-collision algorithms for RFID systems[J].IEEE Transactions on Communications,2010,58(12):3583-3592.
[7] LAW C,LEE K,SIU K Y.Efficient memoryless protocol for tag identification (extended abstract)[C]//Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications.Boston,USA:ACM Press,2000:75-84.
[8] YI Jiang,ZHANG Ruonan.An adaptive combination query tree protocol for tag identification in RFID systems[J].IEEE Communications Letters,2012,16(8):1192-1195.
[9] YANG C N,HU L J,LAI J B.Query tree algorithm for RFID tag with binary-coded decimal EPC[J].IEEE Communications Letters,2012,16(10):1616-1619.
[10] HUSH D R,WOOD C.Analysis of tree algorithms for RFID arbitration[C]//Proceedings of1998IEEE International Symposium on Information Theory.Cambridge,USA:IEEE Press,1998:107.
[11] JIA Xiaolin,FENG Quanyuan,YU Lishan.Stability analysis of an efficient anti-collision protocol for RFID tag identification[J].IEEE Transactions on Communications,2012,60(8):2285-2294.
[12] YAN Lihui,SHI Changqiong,CHEN Rong,et al.Multi-cycle anti-collision algorithm for RFID tag based on parity packet[J].Computer Engineering,2016,42(2):312-315.(in Chinese) 严利辉,史长琼,陈蓉,等.基于奇偶分组的多周期RFID标签防碰撞算法[J].计算机工程,2016,42(2):312-315.
[13] WU Weide,GU Tianqi,MIAO Changsheng.Research on anti-collision algorithm of RFID tag based on energy optimization[J].Computer Measurement and Control,2020,28(3):218-221,226.(in Chinese) 吴维德,顾天琪,苗长胜.基于能量优化的射频识别标签防碰撞算法研究[J].计算机测量与控制,2020,28(3):218-221,226.
[14] LANDALUCE H,PERALLOS A,ZUAZOLA I J G.A fast RFID identification protocol with low tag complexity[J].IEEE Communications Letters,2013,17(9):1704-1706.
[15] JAYADI R,LAI Y C,LIN C C.Efficient time-oriented anti-collision protocol for RFID tag identification[J].Computer Communications,2017,112:141-153.
[16] LANDALUCE H,PERALLOS A,ONIEVA E,et al.An energy and identification time decreasing procedure for memoryless RFID tag anticollision protocols[J].IEEE Transactions on Wireless Communications,2016,15(6):4234-4247.
[17] ZHANG Degan,WANG Xiang,SONG Xiaodong,et al.A novel approach to mapped correlation of ID for RFID anti-collision[J].IEEE Transactions on Services Computing,2014,7(4):741-748.
[18] GUO Zhenjun,SUN Yingfei.Anti-collision algorithm of RFID system based on grouped tag[J].Journal of Electronics & Information Technology,2017,39(1):250-254.(in Chinese)郭振军,孙应飞.基于标签分组的RFID系统防碰撞算法[J].电子与信息学报,2017,39(1):250-254.
[19] FU Yu,QIAN Zhihong,CHENG Chao,et al.Bit arbitration query tree anti-collision algorithm based on grouping mechanism[J].Journal on Communications,2016,37(1):123-129.(in Chinese)付钰,钱志鸿,程超,等.基于分组机制的位仲裁查询树防碰撞算法[J].通信学报,2016,37(1):123-129.
[20] ZHANG Wei,GUO Jiayun,TANG Xueming,et al.An efficient adaptive anticollision algorithm based on 4-ary pruning query tree[J].International Journal of Distributed Sensor Networks,2013,9(12):105-115.

选择文件类型/文献管理软件名称

选择包含的内容

基于分组映射的防碰撞查询树算法

Anti-collision Query Tree Algorithm Based on Group Mapping

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	郭凯敏, 谢鑫, 马一杰, 齐恒, 李克秋. 大规模RFID系统中未知标签的快速可靠识别[J]. 计算机工程, 2023, 49(3): 192-202.
[2]	潘畲稣, 张继军, 张钊锋. 基于SRAM PUF稳定性处理的RFID标签密钥生成方案[J]. 计算机工程, 2020, 46(9): 149-153,162.
[3]	王帅, 杨恒新, 杨华. 基于伪ID码的树型防碰撞算法[J]. 计算机工程, 2020, 46(4): 177-182.
[4]	史志才, 王益涵, 张晓梅, 陈计伟, 陈珊珊. 一种具有隐私保护与前向安全的RFID组证明协议[J]. 计算机工程, 2020, 46(1): 108-113.
[5]	闫玉娟,李化,赵菊敏,李灯熬,刘佳. 基于CRFID和模式识别的跌倒检测系统[J]. 计算机工程, 2019, 45(6): 297-302,309.
[6]	魏访,邹志革. 满足后向安全的RFID标签组所有权转移协议[J]. 计算机工程, 2019, 45(4): 136-141.
[7]	卿哲嘉. 基于LPN具有一般中间人安全的两轮认证协议[J]. 计算机工程, 2019, 45(2): 129-133.
[8]	殷守军. 一种改进的安全RFID群组标签所有权转移协议[J]. 计算机工程, 2019, 45(2): 134-138,143.
[9]	宋宁佳, 崔英花. 基于GA-GRNN的RFID室内定位算法[J]. 计算机工程, 2019, 45(11): 298-302,308.
[10]	夏文涛, 潘森杉, 王良民. 一种面向RFID的超轻量级流密码算法[J]. 计算机工程, 2019, 45(10): 144-149.
[11]	付余路,张华,刘冉,梁高丽,何静,张红阳,肖宇峰. 融合RFID相位与激光的快速动态目标定位[J]. 计算机工程, 2018, 44(8): 308-314.
[12]	何伟健,陆江城,周灿煜,梁泳新,杨健. 基于时隙分组的超高频RFID防碰撞算法[J]. 计算机工程, 2018, 44(6): 283-287.
[13]	宋慧颖,高媛媛,沙楠. 一种有效提高RFID系统物理层安全性能的方法[J]. 计算机工程, 2018, 44(5): 119-123.
[14]	江岸,李向阳. 基于信息位分组的标签防碰撞算法[J]. 计算机工程, 2018, 44(3): 294-300.
[15]	宋梓旭,蒋毅,张若南,李彬. 一种优化Q值调整的RFID标签防碰撞算法[J]. 计算机工程, 2017, 43(9): 81-86.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于分组映射的防碰撞查询树算法

Anti-collision Query Tree Algorithm Based on Group Mapping

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献

相关文章 15

编辑推荐

Metrics

本文评价