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

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

作　　者：韦冬雪[1] 郑嘉利[1] 李亮亮[1] 姚富士[1] 

机构地区：[1]广西大学计算机与电子信息学院,南宁530004

出　　处：《计算机科学》2013年第10期52-55,64,共5页Computer Science

基　　金：广西自然科学基金面上项目(2011GXNSFA018169);广西自然科学基金青年项目(2012GXNSFBA053160);广西科学研究与技术开发计划课题(12118017-9A)资助

摘　　要：在改进型自适应多叉数防碰撞算法(IAMS)基础上,提出了一种新颖的自适应算法。该算法根据碰撞位数来自适应地选择搜索方式。当阅读器检测到两个碰撞位时,对最高碰撞位置"0"和置"1"来进行二叉树搜索;当碰撞位数大于2时,记录最高最低碰撞位,设置最高最低碰撞位的比特数,采用四叉树搜索方式。在matlab平台上,对3种算法进行了对比仿真实验。仿真结果与分析表明,与后退式二进制搜索算法和IAMS相比,该算法在搜索次数上平均减少了46.7%,31.52%,吞吐量平均提高了85.8%,24.22%,传输数据量平均减少了85.3%,82.54%。This paper proposed an adaptive binary search algorithm based on IAMS. The adaptive algorithm chooses bi-nary-tree or quad-tree search adaptively by the number of collisions. In this algorithm, if the number of detected colli- sions 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 mini- mum collisions, then starting the quad-tree search. Finally we simulated the 3 algorithms on Matlab platform. The re-sults 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.

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

分 类 号：TN92[电子电信—通信与信息系统] TP312[电子电信—信息与通信工程]