基于二进制防碰撞算法的RFID定位系统的设计

2 多标签的防碰撞算法
要实现多目标识别，必然要解决下述问题：在一个读写器的范围内有多个电子标签时，由于所有电子标签都采用同一工作频率，故当多个电子标签同时传输数据就会产生数据冲突，使各电子标签之间的传输相互干扰，进而导致信息的丢失，这就是通常所说的碰撞问题。在电子标签和读写器的通信过程中一般会有3种形式的碰撞：标签碰撞、读写器干扰、标签干扰。本文主要研究标签碰撞。
二进制搜索法又名二叉树搜索法，所有用二进制唯一标签的电子标签的ID号可以看成一棵完全二叉树。在读写器作用范围内，同步向读写器发送信号的标签ID号也构成一棵二叉树。读写器根据信号碰撞的情况反复对完全二叉树的分枝进行筛选，最终找出这棵二叉树。在寻找的过程当中逐一确定作用区域内响应的标签，同时也完成了它们与读写器之间的信息交换。
接下来将通过一个实例对二进制搜索算法具体实现过程进行详细的说明。采用ID为8位的4个标签，其ID分别为10110010、10100011、101 10011、11100011。
二进制搜索步骤如下：
①读写器设置筛选条件ID11111111，向标签发送请求。
②阅读区内的所有标签均符合筛选条件，响应读写器的请求，发送各自的ID。
③读写器检测到第2、4、8位发生碰撞，即1X1X001X读写器将碰撞的最高位置0，其余低位置1，重新设定筛选
条件ID10111111，向标签发送请求。
④标签10110010、10100011、10110011响应读写器请求，发送各自的ID。
⑤读写器检测到第4、8位发生碰撞(即101X001X)，读写器将碰撞最高位置0，其余低位置1，重新设定筛选条件为ID10101111，向标签发送请求。
⑥标签10101111响应读写器的请求，发送ID号。
⑦读写器检测到没有碰撞发生，成功识别出标签10100011，然后使标签10100011处于休眠状态，完成对标签的读写。
⑧渎写器重新设定筛选条件为ID11111111，重复识别过程，直至所有标签识别出来。
二进制搜索算法的识别示意图如图4所示。

3 定位算法
LANDMARC定位算法是一种经典的基于有源RFID的室内定位算法，设计的思想是采用额外的固定参考标签(或称为辅助标签)，这些参考标签在该定位系统中作为参考点使用，通过参考点的信号强度值与待定位标签的信号强度值之间的比较，计算出待定位标签的坐标。由于读写器获得到的相邻标签的RSSI也是相近的，所以LANDMARC算法通过比较阅读器接收到的待定位标签与参考标签强度值的大小来求得离待定标签距离的几个参考标签，然后根据这几个最相邻参考标签的坐标，并结合它们的权重，用经验公式计算出待定位标签的坐标。LANDMARC方法具有较高的定位精度，可扩展性好，能处理比较复杂的环境，是一种经常使用的定位方法。
LANDMARC定位算法具有3个特点：
◆采用多个低廉的标签代替昂贵的读写器，节省了开支；
◆可以较好地适应环境所引起的动态因素；
◆定位信息与其他定位技术比较，更加精确、可靠。
LANDMARC定位算法支持移动和动态的属性，可以更好地完成一些接近实时传感的工作。当然，辅助标签和阅读器摆放的位置对定位的精度有一定的影响。
LANDMARC定位算法采用了一种称为“最邻近距离”的思想。理论上，当某个待定位标签与参考标签的距离相临近，那么它们在同一个RF ID阅读器中所获得的信号强度值应该也是相临近的，基于这种思想以及在实验中得到的一些经验公式，可以求解出待定位标签的坐标位置。
无线信号的接收信号强度和信号传输距离的关系可以用式(1)来表示，其中RSSI是接收信号强度，d是收发节点之间的距离，n是信号传播因子，EAF是环境因子(即实际实验环境对理论实验结果的影响因数)，射频参数A定义为距读写器1 m时接收到信号平均能量的绝对值。
RSSI=-(A+10nlgd)-EAF (1)
可以看出，常数A和n的值决定了接收信号强度和信号传输距离的关系。射频参数A和n用于描述网络操作环境。射频参数A被定义为dBm表示距发射机1 m时接收到信号平均能量的绝对值，如平均接收能量是-20 dBm，那么参数A就被定义为20。射频参数n指出了信号能量随着收发器距离增加而衰减的速率，其数值的大小取决于无线信号传播的环境。通过大量的验证，在开旷的操场上得到了环境因子EAF的大概值为13.6 dBm，A取46dBm，n取3．5 dBm。
通过中值策略取得RSSI值，依据式(1)可得到待定位标签到读写器的直线距离，3个读写器的位置分别是p1(x1，y1)，p2(x2，y2)．p3(x3，y3)。则待定位的坐标计算如下式：

为了确定当前实验环境的RSSI的情况，做了如下实验。在距离读写器0 m开始，以0．5 m为间隔一直到35 m的摆放标签，并分别采集各点的RSSI值10次，再求平均值。从结果可以看出RSSI值与距离变化的情况基本与理论符合，可以作为实验数据使用。RSSI随距离的变化曲线如图5所示。