基于后退式索引的二进制树形搜索反碰撞算法及其实现

An Anti-collision Algorithm Based on Binary-tree Searching of Re gressive Index and its Practice

标签冲突是射频识别(RFID)技术的常见问题。解决此问题的反碰撞算法有ALOHA算法,二进制树形算法。这些算法同时对大量标签操作时,效率较低。该算法分析碰撞时的特点,提出:①碰撞发生时,根据碰撞的最高位,跳跃式向前搜索;②无碰撞时,采取后退策略。能够快速地识别所有标签。最终:识别N个标签,阅读器共需要问询2N-1次,平均问询次数2次。并用数学归纳法给予证明。最后,根据线索树的遍历思想给出软件实现。

Tag collision is a common problem in RFID.There are several methods so-called anti-collision to solve this problem,such as ALOHA,binary-tree algorithm and so on.But ,they are often low-efficient when operating a lot of tags at the same time.By analyzing the features of tag collision,this article has brought forward a new algorithm in due course:if collision occurs,There will be jumping search forward according to the highest bit of collision.Otherwise,Back-strategy will be adopted to identify all tags rapidly.So the reader needs2N-1times in order to identify N tags,the av-erage time is two.It is proved by mathematical induction.Finally,it is put into software basing on the traversing idea of threaded tree.