计算机应用 ›› 2012, Vol. 32 ›› Issue (03): 665-668.DOI: 10.3724/SP.J.1087.2012.00665

• 人工智能 • 上一篇    下一篇

基于启发式函数的多叉树防碰撞算法

丁治国1,朱学永1,雷迎科2,王心灵1   

  1. 1.合肥电子工程学院 网络信息管理中心,合肥 230037;
    2.合肥电子工程学院 信息系,合肥 230037
  • 收稿日期:2011-09-06 修回日期:2011-11-14 发布日期:2012-03-01 出版日期:2012-03-01
  • 通讯作者: 丁治国
  • 作者简介:丁治国(1977-),男,安徽合肥人,讲师,博士,主要研究方向:射频识别、计算机网络;朱学永(1958-),男,安徽舒城人,教授,主要研究方向:计算机网络、信息安全;雷迎科(1976-),男,安徽安庆人,讲师,博士,主要研究方向:模式识别、机器学习;王心灵(1975-),女,安徽颍上人,讲师,博士,主要研究方向:计算机网络、信息安全。
  • 基金资助:

    安徽省自然科学基金资助项目(090412055)。

Multi-tree anti-collision algorithm based on heuristic function

DING Zhi-guo1, ZHU Xue-yong1, LEI Ying-ke2, WANG Xin-ling1   

  1. 1.Management Center of Network and Information, Electronic Engineering Institute of Hefei, Hefei Anhui 230037, China;
    2.Department of Information, Electronic Engineering Institute of Hefei, Hefei Anhui 230037, China
  • Received:2011-09-06 Revised:2011-11-14 Online:2012-03-01 Published:2012-03-01
  • Contact: Zhi GuoDIng
  • Supported by:

    Program of the Natural Sciences Foundation of Anhui China

摘要: 为克服传统二叉树防碰撞算法搜索效率低的缺点,提出了一种基于启发式函数的自适应多叉树防碰撞算法。新算法通过定义和计算启发式函数,有效地利用碰撞比特信息来估计节点内待识别标签的数量。新算法根据节点内的标签数量,可在不同节点和深度,自适应地调整搜索叉数,从而有效地提高了算法的搜索效率。理论分析和仿真实验证明:新算法克服了传统防碰撞算法的缺点,尤其在待识别标签数量较多场合,可有效地减少搜索和识别时间,提高射频识别系统的吞吐率。

关键词: 射频识别, 防碰撞算法, 启发式函数, 多叉树, 吞吐率

Abstract: In order to overcome the low efficiency of traditional binary-tree anti-collision algorithms, an adaptive multi-tree anti-collision algorithm based on heuristic function was presented in the paper. By defining the heuristic function which was computed by the number of collision bits, the new algorithm can estimate the number of tags in the branch effectively. Because the new algorithm can adjust the number of searching fork in different branches and depths dynamically, it improves the searching efficiency. The theoretical analyses and simulation results show that the new algorithm overcomes the deficiency of traditional algorithms. For the large number of tags in particular, it can reduce the searching and recognition time and increase the throughput of Radio Frequency IDentification (RFID) system.

Key words: Radio Frequency IDentification (RFID), anti-collision algorithm, heuristic function, multi-tree, throughput

中图分类号: