Enhanced Adaptive Division Anti-collision Algorithm
Computer Science

Computer Science ›› 2018, Vol. 45 ›› Issue (11): 66-69.doi: 10.11896／j.issn.1002-137X.2018.11.008

• Network & Communication • Previous Articles     Next Articles

Enhanced Adaptive Division Anti-collision Algorithm

WANG Han-wu, YU Tao   

  1. (College of Information Science and Engineering,Hunan University,Changsha 410082,China)
  • Received:2017-09-15 Published:2019-02-25

PDF (PC)

734

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

CLC Number: 

  • TN92
[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.
[1] YUAN Yuan, ZHENG Jia-li, SHI Jing, WANG Zhe, LI Li. Anti-collision Algorithm Based on Q-learning for RFID Multiple Readers [J]. Computer Science, 2019, 46(6): 124-127.
[2] HOU Pei-guo, WANG Zhi-xuan, YAN Chen. Improvement of Anti-collision Algorithm Based on RFID Tag [J]. Computer Science, 2019, 46(11A): 359-362.
[3] SHAN Pu-fang, ZHENG Jia-li, YUE Shi-bin and YANG Zi-wei. Enhanced Four-fork Tree RFID Anti-collision Algorithm [J]. Computer Science, 2016, 43(Z11): 271-274.
[4] HUANG Qing-huan,ZHENG Jia-li,WEI Dong-xue and DENG Lin. Mixed RFID Anti-collision Algorithm Based on Dimensional Code Number [J]. Computer Science, 2014, 41(Z11): 10-14.
[5] REN Shou-gang,YANG Fan,WANG Hao-yun,XIONG Ying-jun and XU Huan-liang. Decision Threshold-based Q Algorithm for RFID Anti-collision [J]. Computer Science, 2014, 41(8): 154-157.
[6] CAO Zheng,YANG Lin and XIE Hui. Design and Analysis of Secure Anti-collision Search Protocol for RFID [J]. Computer Science, 2014, 41(4): 116-119.
[7] REN Shou-gang,YANG Fan and XU Huan-liang. Research on Double Weight Parameter Anti-collision Q Value Algorithm in RFID System [J]. Computer Science, 2014, 41(4): 256-259.
[8] XIA Jing-man,XIAO Guo-qiang,CHEN Kai and ZHAN Chun-mei. Framed Slotted ALOHA Anti-collision Algorithm Using Hybrid Spill-tree [J]. Computer Science, 2014, 41(12): 67-69.
[9] FANG Cai-li,ZHENG Feng-bin and WANG Yu-jing. Study on Large-scale Smart Group Volume System Conflict Elimination Method [J]. Computer Science, 2013, 40(8): 258-260.
[10] 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.
[11] . Improved Design and Implementation of Adaptive Binary Searching Anti-collision Algorithm [J]. Computer Science, 2012, 39(Z11): 135-138.
[12] YANG Jian,WANG Yong-hua,CAI Qing-ling,ZHAN Yi-ju,WAN Pin. EHiQ:A RFID Reader MAC Protocol Based on Enhanced HiQ [J]. Computer Science, 2011, 38(7): 85-87.
[13] WANG Yong-hua,ZHAN Yi-ju,YANG Jian,CAI Qing-ling. New MAC Protocol Based on Frequency Hop-reservation for RFID Reader Networks [J]. Computer Science, 2010, 37(7): 42-45.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.