一种改进的自适应多叉树防碰撞算法

doi:10.11896／j.issn.1002-137X.2018.11.008

摘要/Abstract

摘要： 针对传统自适应多叉树防碰撞算法在标签识别过程中存在的空闲时隙过多、阅读器与电子标签间的通信负载量过大等不足,提出了一种改进的自适应多叉树防碰撞算法(Improved Adaptive division Collision Tree algorithm,IACT)。该算法通过计算碰撞因子决定采用二叉树或四叉树。当采用二叉树时,若阅读器检测到碰撞位只有一位,则无需再次发送命令即可以直接识别出标签;采用四叉树时,阅读器首先发送一命令,要求标签返回最高两个碰撞位对应的编码,然后根据编码得到碰撞信息。在标签中加入计数器,使用最高两个碰撞位和计数器值作为查询命令,响应的电子标签将序列号的后缀信息发送给阅读器处理。算法性能分析和实验仿真表明,IACT算法能有效减少系统总时隙,降低了通信负载开销,提高了标签识别效率。

关键词: 标签识别算法, 防碰撞, 碰撞位, 自适应多叉树

Abstract: Aiming at the disadvantages of the traditional adaptive division collision tree algorithm in the process of tag identification such as many idle time slots,large communication overhead between the reader and tags,this paper pre-sented an improved adaptive division collision tree algorithm (IACT).The algorithm determines the adoption of the binary-tree or quad-tree by calculating collision factor.As for the binary-tree,if the collision-bit is only one,tags can be identified directly without sending commands again.As for the quad-tree,reader first sends a command for tags to return the corresponding coding of the highest two collision bits,and obtains collision information through encoding.The reader takes the value of counter and the highest two collision bits as the parameter of query command by using the counter,and tags only send the postfix of ID to the reader.The performance analysis and simulation results show that IACT algorithm can effectively reduce the total timeslot consumption and the communication load,and improve the re-cognition efficiency as well.

Key words: Adaptive division collision tree, Anti-collision, Collision bits, Tag identification algorithm

中图分类号:

TN92

王汉武, 于涛. 一种改进的自适应多叉树防碰撞算法[J]. 计算机科学, 2018, 45(11): 66-69. https://doi.org/10.11896／j.issn.1002-137X.2018.11.008

WANG Han-wu, YU Tao. Enhanced Adaptive Division Anti-collision Algorithm[J]. Computer Science, 2018, 45(11): 66-69. https://doi.org/10.11896／j.issn.1002-137X.2018.11.008

参考文献

[1]SUN Q Y,ZHANG H J,MO L F.Dual-reader wireless protocols for dense active RFID identification[J].International Journal of Communication Systems,2011,24(11):1431-1444.
[2]LIU X,ZHANG S G,XIAO B,et al.Flexible and Time Efficient Tag Scanning with Handheld Readers[J].IEEE Transactions on Mobile Computing,2016,15(4):1-13.
[3]YANG X,WU H F,ZENG Y,et al.Capture-aware estimation for the number of RFID tags with lower complexity[J].IEEE Communications Letters,2013,17(10):1873-1876.
[4]ZHANG S G,LIU X,WANG J X,et al.Accurate Range-Free Localization for Anisotropic Wireless Sensor Networks[J].ACM Transactions on Sensor Networks,2015,11(3):1-28.
[5]SHENG Z G,HONG D F,WEN G J.An Effective Frame Brea- king Policy for Dynamic Framed Slotted Aloha in RFID[J].IEEE Communications Letters,2016,20(4):692-695.
[6]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.
[7]ZHU S Q,JIN X F,JIN L B.A Octree-based Grouping Recoding RFID Anti-collision Algorithm[C]∥2015 6th IEEE International Conference on Software Engineering and Service Science (ICSESS).2015:758-761.
[8]LIU X,XIAO B,ZHU F,et al.Let’s work together:Fast Tag Identification by Interference Elimination for Multiple RFID Readers[C]∥Proc.of the IEEE ICNP.Singapore,2016:1-10.
[9]JIA X,FENG Q,YU L.Stability analysis of an efficient anti-collision protocol for RFID tag identification[J].IEEE Transactions on Communications,2012,60(8):2285-2294.
[10]BU K,XU M J,LIU X,et al.Toward Fast and Deterministic Clone Detection for Large Anonymous RFID System[C]∥Proc.of the 11th IEEE International Conference on Mobile Ad Hoc and Sensor Systems.Philadelphia,PA,USA,2014:416-424.
[11]TAN W J,ZHANG S S,TIAN Z H.Research on RFID anti-collision algorithm based on regressive-style binary search[J].Computer Application and Software,2012,29(5):191-194.(in Chinese)
樊文静,张姗姗,田智慧.基于后退式二进制搜索的RFID防碰撞算法的研究[J].计算机应用与软件,2012,29(5):191-194.
[12]BU K,LIU X,LUO J Q,et al.Unreconciled Collisions Uncover Cloning Attacks in Anonymous RFID Systems[J].IEEE Tran-sactions on Information Forensics and Security,2013,8(3):429-439.
[13]DING Z G,ZHU X Y,GUO L,et al.An adaptive anti-collision algorithm based on multi-tree search[J].Acta Automatica Sinica,2010,36(2):237-241.(in Chinese)
丁治国,朱学永,郭立,等.自适应多叉树防碰撞算法研究[J].自动化学报,2010,36(2):237-241.
[14]SONG J H,GUO Y J,HAN L S.An adjustive hybrid tree anti-collision algorithm for RFID multi-tag identification[J].Acta Electronica Sinica,2014,42(4):685-689.(in Chinese)
宋建华,郭亚军,韩兰胜.自调整混合树RFID多标签防碰撞算法[J].电子学报,2014,42(4):685-689.
[15]REN S J,HAO Y S,XU B H,et al.A new anti-collision algorithm based on adjustive multi-tree[J].Computer Measurement and Control,2015,23(12):4180-4183.(in Chinese)
任少杰,郝永生,许博浩,等.一种新的自调整多叉树防碰撞算法[J].计算机测量与控制,2015,23(12):4180-4183.

相关文章 11

[1]	陈博琛, 唐文兵, 黄鸿云, 丁佐华. 基于改进人工势场的未知障碍物无人机编队避障 Pop-up Obstacles Avoidance for UAV Formation Based on Improved Artificial Potential Field 计算机科学, 2022, 49(6A): 686-693. https://doi.org/10.11896/jsjkx.210500194
[2]	袁源, 郑嘉利, 石静, 王哲, 李丽. 基于Q-learning的RFID多阅读器防碰撞算法 Anti-collision Algorithm Based on Q-learning for RFID Multiple Readers 计算机科学, 2019, 46(6): 124-127. https://doi.org/10.11896/j.issn.1002-137X.2019.06.018
[3]	侯培国, 王志轩, 严晨. 基于RFID标签的防碰撞算法改进 Improvement of Anti-collision Algorithm Based on RFID Tag 计算机科学, 2019, 46(11A): 359-362.
[4]	单朴芳,郑嘉利,岳世彬,杨子薇. 增强型四叉树RFID防碰撞算法 Enhanced Four-fork Tree RFID Anti-collision Algorithm 计算机科学, 2016, 43(Z11): 271-274. https://doi.org/10.11896/j.issn.1002-137X.2016.11A.063
[5]	黄庆欢,郑嘉利,韦冬雪,邓林. 基于维码数的RFID混合防碰撞算法 Mixed RFID Anti-collision Algorithm Based on Dimensional Code Number 计算机科学, 2014, 41(Z11): 10-14.
[6]	任守纲,杨帆,王浩云,熊迎军,徐焕良. 基于判决门限的RFID防碰撞Q值算法 Decision Threshold-based Q Algorithm for RFID Anti-collision 计算机科学, 2014, 41(8): 154-157. https://doi.org/10.11896/j.issn.1002-137X.2014.08.034
[7]	任守纲,杨帆,徐焕良. 一种双权重参数的RFID防碰撞Q值算法研究 Research on Double Weight Parameter Anti-collision Q Value Algorithm in RFID System 计算机科学, 2014, 41(4): 256-259.
[8]	曹峥,杨林,谢辉. RFID安全防碰撞搜索协议的设计与分析 Design and Analysis of Secure Anti-collision Search Protocol for RFID 计算机科学, 2014, 41(4): 116-119.
[9]	夏静满,肖国强,陈凯,詹春梅. 基于混合溢出树搜索的帧时隙ALOHA防碰撞算法 Framed Slotted ALOHA Anti-collision Algorithm Using Hybrid Spill-tree 计算机科学, 2014, 41(12): 67-69. https://doi.org/10.11896/j.issn.1002-137X.2014.12.015
[10]	韦冬雪,郑嘉利,李亮亮,姚富士. 一种新颖的自适应多叉树防碰撞算法的研究 Study of Novel Adaptive Multi-tree Anti-collision Search Algorithm 计算机科学, 2013, 40(10): 52-55.
[11]	钱晓军,朱颖,吉根林. 一种改进的物联网二进制防碰撞算法 Improved Binary Anti-collision Algorithm for Internet of Things 计算机科学, 2012, 39(9): 24-27.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed