基于二叉树分解的自适应防碰撞算法

丁治国; 郭立; 朱学永; 汪赵华

doi:10.3724/SP.J.1146.2008.00836

基于二叉树分解的自适应防碰撞算法

doi: 10.3724/SP.J.1146.2008.00836

丁治国^{①②;郭立},
郭立,
朱学永,
汪赵华

基金项目:

高等学校博士学科点专项科研基金(20020358033)资助课题

计量
- 文章访问数: 3427
- HTML全文浏览量: 65
- PDF下载量: 973
- 被引次数: 0
出版历程
- 收稿日期: 2008-07-02
- 修回日期: 2008-12-08
- 刊出日期: 2009-06-19

An Adaptive Anti-collision Algorithm Based on Binary-Tree Disassembly

摘要

摘要: 该文提出了一种基于二叉树分解的自适应防碰撞算法。新算法利用标签EPC的唯一性，通过时隙分配估计标签的分布情况，对发生碰撞的时隙进行二叉树搜索，从而将一个庞大且复杂的二叉树分解成多个简单的小子二叉树，简化了搜索流程。通过引入碰撞堆栈，并根据时隙状态自适应得调整搜索路径，从而进一步减少搜索的时隙数及提高了时隙的吞吐量。理论和仿真实验证明了新算法的有效性，即在待识别的标签数量较多时，可有效的减少识别时间，提高搜索效率。
- 射频识别; 防碰撞算法; 二叉树分解; 碰撞堆栈
Abstract: A new adaptive anti-collision algorithm based on binary-tree disassembly is proposed in this paper. In order to enhance the search efficiency, a big and complex binary-tree is disassembled to several small and simple binary-trees by estimating the distributing of tags. The introduction of the collision stack, as well as adjusting the search paths adaptively based on the state of slots, the performance of the new algorithm is improved further, including reducing the search timeslots and improving the throughput of timeslots. Theory and computer simulations show that the new anti-collision algorithm is practical, especially when the number of tags is large.

HTML全文

参考文献(1)

Finkenzeller K. RFID Handbook: Fundamentals andApplications in Contactless Smart Cards and Identification.John Wiley Sons. 2003.[2]Hwang Tae-Wook, Lee Byong-Gyo, and Kim Young-Soo.Improved anti-collision scheme for high speed identificationin RFID system. First International Conference onInnovative Computing, Information and Control, Beijing,China, 2006, Vol.2: 449-452.[3]Cha Jae-Ryong and Kim Jae-Hyun. Novel anti-collisionalgorithms for fast object identification in RFID system.,11th International Conference on Parallel and DistributedSystems Workshops, Fukuoka, Japan, 2005, Vol.2: 63-67.[4]Myung Jihoon, Lee Wonjun, and Srivastava J. Adaptivebinary splitting for efficient RFID tag anti-collision. IEEECommunications Letters, 2006, 10(3): 144-146.[5]Lai Yuan-Cheng and Lin Chih-Chung. A pair-resolutionblocking algorithm on adaptive binary splitting for RFID tagidentification[J].IEEE Communications Letters.2008, 12(6):432-434[6]Myung Jihoon and Lee Wonjun. Adaptive binary splitting: aRFID tag collision arbitration protocol for tag identification.2nd International Conference on Broadband Networks,Boston, United States, 2005, Vol.1: 347-355.[7]Myung J, Lee W, and Shih T. An adaptive memorylessprotocol for RFID tag collision arbitration[J].IEEE Trans. onMultimedia.2006, 8(5):1096-1101[8]杜海涛, 徐昆良等. 基于返回式树形搜索的反碰撞算法. 云南大学学报, 2006, 28(Sl): 133-136.Du Hai-tao and Xu Kun-liang, et al.. An anti-collisionalgorithm based on binary-tree Searching of backtracking.Journal of Yunnan University, 2006, 28(Sl): 133-136.[9]余松森, 詹宜巨等. 基于后退索引的二进制树形搜索反碰撞算法及其实现. 计算机工程与应用, 2004, 26(16): 26-28.Yu Song-sen and Zhang Yi-ju, et al.. An anti-collisionalgorithm based on binary-tree searching of regressive indexand its practice. Computer Engineering and Application, 2004,26(16): 26-28.

施引文献

资源附件(0)

访问统计