Adaptive tree grouping and blind separation anti-collision algorithm for radio frequency identification system

doi:10.11772/j.issn.1001-9081.2015.01.0019

Abstract

Abstract:

For the low tag identification rate problem caused by that reader can not identify multiple tags simultaneously in single-antenna Radio Frequency Identification (RFID) system, combined with multi-antenna technology and the grouping of binary tree slots based on tags ID sequence, an adaptive tree grouping and blind separation anti-collision algorithm for RFID system was proposed. In the presented algorithm, by adjusting query code length of reader according to the number of antennas in RFID system and sending a query signal, the eligible response tags were assigned to the appropriate slots so that the number of tags in each slot was less than or equalled to the number of antennas and met Blind Source Separation (BSS) system conditions which could identify tags, so as to achieve the purpose of identifying tags simultaneously and quickly. Compared with the Blind Separation and Dynamic Bit-slot Grouping (BSDBG) algorithm using the same multi-antenna technology, the simulation results show that the tag identification speed of the proposed algorithm increases from 20% to 69% and the tag identification rate improves from 60% to 88% when the number of antennas is from 4 to 32, while it has low complexity, low hardware overhead and it is relatively simple to implement and conducive to the promotion and use.

Key words: multi-antenna, binary tree, anti-collision, Blind Source Separation (BSS), identification rate

摘要：

针对单天线射频识别(RFID)系统中阅读器不能同时识别多个标签造成标签识别率较低的问题,结合多天线技术及基于标签ID号序列的二叉树时隙分组提出了一种自适应树形分组的盲分离RFID系统防碰撞算法.首先根据RFID系统中天线的个数调整阅读器查询码码长并发送查询信号,将符合条件的响应标签分配到相应的时隙中,使每一个时隙中的标签数小于或者等于阅读器的天线数,满足盲源分离(BSS)的多天线系统识别标签的条件,从而达到同时且快速识别多个标签的目的.仿真结果表明,与同样采用多天线技术的基于位隙动态分组的盲分离(BSDBG)算法相比,当天线个数为4~32时,所提算法的标签识别速度提高了20%~69%,标签识别率提高了60%~88%,同时该算法复杂度低,硬件开销小,实现相对简单,有利于推广和使用.

关键词: 多天线, 二叉树, 防碰撞, 盲源分离, 识别率

CLC Number:

MU Yuchao, ZHANG Xiaohong. Adaptive tree grouping and blind separation anti-collision algorithm for radio frequency identification system[J]. Journal of Computer Applications, 2015, 35(1): 19-22.

穆宇超, 张小红. 自适应树形分组的盲分离射频识别系统防碰撞算法[J]. 计算机应用, 2015, 35(1): 19-22.

References

[1] LI Q, LIU H, ZHANG X. An anti-collision algorithm based on une-qual timeslots in radio frequency identification system [J]. Journal of Electronics & Information Technology, 2011, 33(11): 2628-2633.(李青青,刘洪武,张小林.一种基于不等长时隙的射频识别防碰撞算法[J].电子与信息学报,2011,33(11):2628-2633.)
[2] ZHOU Y, SUN X, GU J. Research on improved binary anti-collision algorithm [J]. Application Research of Computers, 2012, 29(1): 256-259.(周艳聪,孙晓晨,顾军华.一种改进二进制防碰撞算法研究[J].计算机应用研究,2012,29(1):256-259.)
[3] ZHANG G, ZHANG S, ZHANG Y. Reader anti-collision algorithm based on random slot for RFID systems [J]. Journal of Beijing University of Aeronautics and Astronautics, 2013, 39(6): 782-786.(张光山,张烁,张有光.基于随机时隙的RFID读写器防冲突方法[J].北京航空航天大学学报,2013,39(6):782-786.)
[4] LI P, SUN L, WU J, et al. Research on RFID anti-collision hybrid algorithm based on discrete processing [J]. Journal on Communications, 2013, 34(8): 10-17.(李平,孙利民,吴佳英,等.基于可离散处理的RFID防碰撞混杂算法研究[J].通信学报,2013,34(8):10-17.)
[5] WANG C, LIU C, XU H, et al. An enhanced binary tree-based anti-collision algorithm [J]. Journal of Hunan University: Natural Sciences, 2013, 40(8): 97-101.(王春华,刘迟时,徐浩,等.一种改进的基于二叉树的防碰撞算法[J].湖南大学学报:自然科学版,2013,40(8):97-101.)
[6] ZHAO Z, LU H, SHANG J. Algorithm for underdetermined blind signal separation based on constrained NMF [J]. Application Research of Computers, 2011, 28(5): 1843-1845.(赵知劲,卢宏,尚俊娜.基于约束NMF的欠定盲信号分离算法[J].计算机应用研究,2011,28(5):1843-1845.)
[7] NAQVI S M, YU M, CHAMBERS J A. A multimodal approach to blind source separation of moving sources [J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(5): 895-910.
[8] DONG J, YANG T, LI X, et al. Research on the applicability of the blind source separation of harmonic components [J]. Journal of Harbin Engineering University, 2014, 35(4): 1-8.(董建超,杨铁军,李新辉,等.简谐成分的盲源分离适用性研究[J].哈尔滨工程大学学报,2014,35(4):1-8.)
[9] LI H, JIA Z, WANG H, et al. UHF RFID anti-collision algorithm based on blind separation and dynamic bit-slot grouping [J]. Journal on Communications, 2012, 33(4): 47-53.(栗华,贾智平,王洪君,等.基于动态位隙分组盲分离的UHF RFID防碰撞算法[J].通信学报,2012,33(4):47-53.)
[10] SUN Y, HAWRYLAK P J, MICKLE M H. Application of ICA in collision resolution for passive RFID communication [C]// Proceedings of the 2009 World Congress on Engineering and Computer Science. San Francisco: [s.n.], 2009: 1292-1297.
[11] BLETSAS A, KIMIONIS J, DIMITRIOU A G, et al. Single-antenna coherent detection of collided FM0 RFID signals [J]. IEEE Transactions on Communications, 2012, 60(3): 756-766.
[12] XI X, ZHU H, GAO F, et al. Power frequency noise reduction technique of tactile sensor signal using matched filter and ICA [J]. Journal of Central South University: Science and Technology, 2013, 44(S2): 145-149.(席旭刚,朱海港,高发荣,等.匹配滤波和ICA消除触觉传感器工频噪声[J].中南大学学报:自然科学版,2013,44(S2):145-149.)
[13] XU X, GAO J, FAN Z. Methods for estimation of the number of sources in blind source separation [J]. Journal of Hefei University of Technology: Natural Science, 2008, 31(1): 1-4.(徐小红,高隽,范之国.盲信号分离中信号源数目估计方法研究[J].合肥工业大学学报:自然科学版,2008,31(1):1-4.)

[1]	WANG Shuai, YANG Xiaodong. RFID tag number estimation algorithm based on sequential linear Bayes method [J]. Journal of Computer Applications, 2018, 38(11): 3287-3292.
[2]	CHEN Yonghong, GUO Lili, ZHANG Shibing. Energy efficiency analysis of relay assisted cellular network [J]. Journal of Computer Applications, 2018, 38(10): 2965-2970.
[3]	DING Jianli, HAN Yuchao, WANG Jialiang. Estimation method for RFID tags based on rough and fine double estimation [J]. Journal of Computer Applications, 2017, 37(9): 2722-2727.
[4]	MO Lei, CHEN Wei, REN Ju. Anti-collision algorithm for RFID based on counter and bi-slot [J]. Journal of Computer Applications, 2017, 37(8): 2168-2172.
[5]	XU Guoyu, WANG Yingfeng, MA Xiaofei, WANG Kefeng, YAN Ruoyu. Hybrid algorithm for identifying error signatures in hierarchical identity based cryptography batch verification [J]. Journal of Computer Applications, 2017, 37(1): 217-221.
[6]	YE Weidong, YANG Tao. Single-channel vibration signal blind source separation by combining extreme-point symmetric mode decomposition with time-frequency analysis [J]. Journal of Computer Applications, 2016, 36(10): 2933-2939.
[7]	LONG Zhaohua, GONG Tengfei. Estimation algorithm of radio frequency identification tags based on non-empty slot number [J]. Journal of Computer Applications, 2016, 36(1): 101-106.
[8]	ZHANG Guangyu, CHEN Hong, CAI Xiaoxia. Blind source separation method for mixed digital modulation signals based on RobustICA [J]. Journal of Computer Applications, 2015, 35(8): 2129-2132.
[9]	YAN Hongwen, ZHOU Yamei, PAN Chu. Novel K-medoids clustering algorithm based on breadth-first search [J]. Journal of Computer Applications, 2015, 35(5): 1302-1305.
[10]	WANG Donghui, HAN Jianmin, ZHUANG Jiaqi. Efficient memory management algorithm based on segment tree and its space optimization [J]. Journal of Computer Applications, 2015, 35(12): 3368-3373.
[11]	FU Hui, WU Bin, HAN Dongxuan, HUANG Yangqiang. Fast visual optimization defogging algorithm based on atmospheric physical model [J]. Journal of Computer Applications, 2015, 35(11): 3316-3320.
[12]	JIN Zefen, WU Chuankun. Enhanced tag anti-collision algorithm based on multi-bit identification for radio frequency identification [J]. Journal of Computer Applications, 2015, 35(1): 10-14.
[13]	PAN Hao, CHEN Meng. Optimization of anti-collision algorithm for radio frequency identification reader system in Internet of things [J]. Journal of Computer Applications, 2015, 35(1): 23-26.
[14]	LI Jia ZHENG Yiping LIU Chunlong. Embed safety mechanism of a RFID anti-collision strategy [J]. Journal of Computer Applications, 2014, 34(1): 99-103.
[15]	GUO Dong WANG Wei ZENG Guoshun. Distributed data storage method based on consistent tree distribution [J]. Journal of Computer Applications, 2013, 33(12): 3432-3436.