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

被引：70

作者：

余松森

詹宜巨

彭卫东

赵振宇

机构：

[1] 广东工业大学自动化学院

[2] 广东省科学院自动化工程研制中心

[3] 广东工业大学机电学院

[4] 广东工业大学机电学院广州南昌大学计算机系

[5] 南昌

[6] 广州

来源：

计算机工程与应用 | 2004年 / 16期

关键词：

后退式索引; 反碰撞; RFID; Manchester编码; 数学归纳法; 物元网; 复杂度;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

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

引用

页码：26 / 28

页数：3