一种新颖的自适应多叉树防碰撞算法的研究

计算机科学 ›› 2013, Vol. 40 ›› Issue (10): 52-55.

一种新颖的自适应多叉树防碰撞算法的研究

韦冬雪,郑嘉利,李亮亮,姚富士

广西大学计算机与电子信息学院南宁530004;广西大学计算机与电子信息学院南宁530004;广西大学计算机与电子信息学院南宁530004;广西大学计算机与电子信息学院南宁530004

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受广西自然科学基金面上项目(2011GXNSFA018169),广西自然科学基金青年项目(2012GXNSFBA053160),广西科学研究与技术开发计划课题(12118017-9A)资助

Study of Novel Adaptive Multi-tree Anti-collision Search Algorithm

WEI Dong-xue,ZHENG Jia-li,LI Liang-liang and YAO Fu-shi

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 在改进型自适应多叉数防碰撞算法(IAMS)基础上,提出了一种新颖的自适应算法。该算法根据碰撞位数来自适应地选择搜索方式。当阅读器检测到两个碰撞位时,对最高碰撞位置“0”和置“1”来进行二叉树搜索；当碰撞位数大于2时,记录最高最低碰撞位,设置最高最低碰撞位的比特数,采用四叉树搜索方式。在matlab平台上,对3种算法进行了对比仿真实验。仿真结果与分析表明,与后退式二进制搜索算法和IAMS相比,该算法在搜索次数上平均减少了46.7%,31.52%,吞吐量平均提高了85.8%,24.22%,传输数据量平均减少了85.3%,82.54%。

关键词: RFID,防碰撞算法,二进制搜索算法,自适应

Abstract: This paper proposed an adaptive binary search algorithm based on IAMS．The adaptive algorithm chooses binary-tree or quad-tree search adaptively by the number of collisions．In this algorithm,if the number of detected collisions is 2,the reader will begin binary tree search by setting the maximum collision position "0" or "1"．If the number of detected collisions is more than two,the reader will record the position and set the bits value of the maximum and minimum collisions,then starting the quad-tree search．Finally we simulated the 3algorithms on Matlab platform．The results and analysis show that compared with the return binary search algorithm and IAMS,the average number of search instructions reduces 46.7%,31.52%,and throughput is increased by an average of 85.8%,24.22% and average 85.3%,82.54% reduction in the amount of data transmitted in our algorithm．

Key words: RFID,Collision anti-collision,Binary-tree search algorithm,Self-adaption

韦冬雪,郑嘉利,李亮亮,姚富士. 一种新颖的自适应多叉树防碰撞算法的研究[J]. 计算机科学, 2013, 40(10): 52-55. https://doi.org/

WEI Dong-xue,ZHENG Jia-li,LI Liang-liang and YAO Fu-shi. Study of Novel Adaptive Multi-tree Anti-collision Search Algorithm[J]. Computer Science, 2013, 40(10): 52-55. https://doi.org/

参考文献

[1] 江雨,马满福.物联网中RFID位匹配防碰撞算法[J].计算机应用研究,2012,9(1):88-91
[2] 王亚奇,蒋国平.基于分组机制的跳跃式动态二进制防碰撞算法[J].自动化学报,2010,6(10):1390-1400
[3] Bai Cheng-sen,Zhu Jiang.Research on an RFID anti-collisionimproved algorithm based on binary search[C]∥International Conference on Computer Application and System Modeling．2010:430-432
[4] Yeh M-K,Jiang J-R,Huang S-T．Adaptive splitting and pre-signaling for RFID tag anti-collision[J].Computer Comnunications,2009(32):1862-1870
[5] He Ming-xing,Horng S-J,et al．A Fast RFID Tag Identification Algorithm Based on Counter and Stack[J]．Expert Systems with Applications,2011(38):6829-6838
[6] Lai Yuan-Cheng,Lin C-C．Two Couple-Resolution Blocking Protocols on Adaptive Query Splitting for RFID Tag Identification[J]．IEEE Transactions on Mobile Computing,2012(11):1450-1463
[7] 丁治国,朱学永,等．自适应多叉树防碰撞算法研究[J].自动化学报,2010,6(2):237-241
[8] 张学军,蔡文琦,王锁萍.改进型自适应多叉数防碰撞算法的研究[J].电子学报,2012,1:193-198
[9] 樊文静,张姗姗,田智慧.基于后退式二进制搜索的RFID防碰撞算法的研究[J].计算机应用与软件,2012,9(5):191-194
[10] 张航,唐明浩,程晖.改进的返回式二进制防碰撞算法[J].计算机工程与应用,2011,47(25):208-211
[11] 冯娜,潘伟杰,李少波,等.基于新颖跳跃式动态搜索的RFID防碰撞算法[J].计算机应用,2012,2(1):288-291

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed