RFID 无线通信迂回式随机树形防冲突算法
射频识别RFID （RadioFrequencyIdentification） 技术相对于传统的磁卡及IC 卡技术具有非接触、阅读速度快、无磨损等特点， 在最近几年里得到快速发展。RFID 系统主要由三部分组成， 即电子标签（tag）、读写器（reader） 以及天线（antenna）， 是一种非接触式的自动识别系统。随着RFID系统的不断增多， 多个电子标签同时将信号送入一个读写器的读写通道必然会产生信道争用问题， 如何减少数据碰撞从而快速有效的在规定时间内读取出所有电子标签的信息成为一个难点。
解决碰撞问题的算法有ALOHA算法、分隙ALOHA算法和二进制树形搜索算法， 但这几种算法都有一个共同的缺陷： 信道利用率比较低。本文提出了一种新的反碰撞算法， 这种算法是在传统的二进制树算法基础上， 通过迂回式反碰撞算法， 利用二进制位取值的互异（即非0 即1）的特性， 以及连续两位发生冲突（即00， 01， 10， 11）， 可同时识别出1~4 个标签， 进而提高阅读器识别标签的效率， 在信道利用率上远远优于其它算法。
1 射频识别系统的工作原理
射频识别系统的工作频段有低频， 中频， 高频， 超高频及微波之分， 而在工业中通常采用13.56MHz 的频率。对于从阅读器与电子标签间数据传递， 通常采用振幅键控ASK （AmplitudeShiftKeying）、频移键控FSK(FrequencyShiftKeying)和相移键控PSK
（PHASEShiftKeying）。ASK 和PSK 常被使用， 因为它们特别容易解调， 其原理参见图1。由图1 中可知， 当有多于1个的标签在阅读器的作用范围内时， 且传递的数据0/1 交错时， 将会出现1个标签谐振，
1个标签失谐的情况。这时就阅读器则很难通过判断输出端的高低电位来读出标签的内部信息， 这就是我们要解决的碰撞问题。
2 二进制搜索算法原理
二进制搜索算法， 是以一个独特的序列号(UID)来识别标签为基础的， 为了能辨认出阅读器中数据碰撞比特位的准确位置， 传统采用曼彻斯特编码。该编码采用电平的上升沿和下降沿来表示数值位。本文中假设上升沿编码为逻辑“0”， 下降沿编码为逻辑“1”， 若状态跳变， 视为无效数据且作为错误码被识别。如在多标签的环境中当同时有上升沿和下降沿同时存在是， 则会互相抵消从而无状态跳变， 以此阅读器判断发生碰撞的准确位数而再次搜索。假设有6 个RFID 标签， 其相应EPC代码为8 位， 利用曼彻斯特编码能准确识别出碰撞位的示意图如图2 所示， 图中用红色部分为碰撞位。
从图中可知， 阅读器检测出D2， D3， D4， D6， D7 位出现碰撞，从而可以判断出在同一区域内存在多个RFID标签。
本文约定在阅读器作用范围内的所有标签能在同一时刻同步传送响应数据， 以便准确地监测碰撞位的发生。为了便于表述算法， 还需要引入4 种命令：
1） REQUEST： 表示阅读器发送一个呼叫参数给区域内标签， 所有标签的EPC 与之进行“与运算”， 结果全为0
的标签将各自的EPC返回至阅读器。在第1 次询问时， 呼叫参数应全为0， 即Request 命令为： Request(00000000)，
这样区域内所有标签都会应答。
2） SELECT： 用某个（事先确定的） EPC 作为参数发送给标签。具有相同EPC
的标签将以此作为执行其他命令（例如读出和写入数据）的切入开关， 即选择这个标签。
3） READ/DATA： 选中的标签将存储的数据发送给阅读器）。
