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

　　引言

　　目前，有很多定位技术都可以对物体进行定位，但在小区域(如室内)定位服务中，现有的定位技术存在着一定的缺陷，如GPS技术用于停车场这种小区域的定位服务中，成本太高而且定位精度不高。其他技术如超声波技术、射频识别(Radio Frequency Identication，RFID)技术、IEEE802.11、超宽带(UWB)等，应用于室内定位服务，各有优劣。射频识别定位技术以其非接触、非视距、灵敏度高和成本低的优点，正成为定位系统的优选技术。然而，在实际应用中不可能只对一个标签定位，多标签定位必然会造成标签之间的碰撞，为了解决标签之间的碰撞问题，目前国内外所研究的防碰撞算法如下：多址技术(SDMA、TDMA、CDMA、FDMA)，ALOHA防碰撞算法，二进制防碰撞算法。其中二进制防碰撞算法易于实现且效率和精度高，近几年得到广泛运用。

　　1 设计方案

　　阅读器采用的是PIC16F877A微控制器，阅读器与标签都是利用模拟SPI口与CC2500射频模块的数字接口进行通信。作为阅读器部分的PIC 16F877A则用其TXD与RXD引脚通过MAX3232实现电平转换后，与PC机的串口相连以实现读写器读取数据的功能。

　　读写器与标签之间的射频信号通过空间耦合实现无线信息传递，读写器通过与标签的无线通信，获得接收信号强度指示(RSSI)值，再采用LANDMAR定位算法，就可以计算出目标的相对坐标位置，实现精确定位。在大多数情况下读写器在识别标签时难免会出现碰撞的问题，为了解决这一问题，利用二进制搜索法来防止多标签识别时发生碰撞。系统框图如图1所示。

　　1.1 微控制器

　　本系统读写器和标签都采用PIC16F877A作为微控制器。PIC16F877A是8位的高性价比微控制器，并且采用不同的宽度，便于实现全部指令的单字节化、单周期化，从而有利于提高CPU执行指令的速度。此外，数据存储空间比较大，拥有8K×14个字节Flash程序存储器、368×8个字节数据存储(RAM)空间、256×8个字节EEPROM数据存储空间。还具有8级的硬件堆栈、内部看门狗定时器、低功耗休眠模式、25 mA的吸入/拉出电流。外部具有3个定时器模块。它还具有2个16位捕捉器、2个16位比较器、2个10位PWM模块、10位多通道A/D转换器、通用同步异步接收/发送器等功能模块。它具有功耗低、驱动能力强、外接电路简单、寻址简单、指令条数少等优点。

　　微控制器PIC16F877A通过SPI接口与CC2500射频收发芯片实现数据的接收与发送。PC机可以利用串口调试助手发送命令，通过RS232串口连接读写器，控制读写器与标签之间的一切操作。

　　1.2 射频收发芯片

　　无线通信的通信距离、通信效率与其主芯片密切相关。CC2500是一种低成本的2.4 GHz射频收发芯片，为低功耗无线应用而设计。电路工作在2 400～2 483.5 Hz的ISM(工业、科学及医学)和SRD(短距离设备)频率波段。

　　射频收发芯片集成了一个数据传输可达500 kbps的高度可配置的调制解调器。通过开启集成在调制解调器上的前向误差校正选项，使性能得到提升。CC2500为数据处理、数据缓冲、突发数据传输、清晰信道评估、连接质量指示和电磁波激发提供广泛的硬件支持。CC2500在通信中空中接口的数据是以一个固定格式传输，读写器和标签之间的数据传输必须严格按照这个格式进行，否则无法通信。

　　导言、同步字与CRC校验在发送数据时是由CC2500硬件自动添加，在接收时由硬件自动去除。在信道特性较好的场合，为了提高识别速度，可设定16位的导言与16位的同步字。CC2500在固定长度通信模式下，可删去长度域;在可变长度通信模式，需要8位的长度域给出除去导言与同步字外所有数据负载的字节数。其数据格式如图2所示。

　　CC2500与MCU之间的接口通过SPI接口相连，MCU通过SPI接口向CC2500发送操作命令，配置其调制方式、工作频率等参数，通过命令配置其为接收状态、发送状态、空闲状态或休眠状态。

　　1.3 低功耗设计

　　本定位系统的标签采用电池供电，是有源标签。而电池是一种消耗性的电源，工作时间短。为了延长车载卡的工作时间，需要进行电源管理，以降低功耗。当前大多数的电源管理方法采用一种周密设计的唤醒、休眠方法。但大多数情况下，唤醒周期的大部分时间是无用的，消耗能量。本系统中采用一种无线触发唤醒的电源管理方法。在这种方法中，有源标签进入休眠模式后就会一直保持睡眠状态，在读写器没有发送出特定频率的无线信号时，它是不会被唤醒的。当然，这个特定频率的无线信号会立即唤醒休眠的标签。这样，就节省了在唤醒前和监测期间的电源消耗。唤醒脉冲通过特定频率传送，而数据通信采用另外的无线频率传送。一旦读写器与标签建立通信连接后，双方便跳到由读写器指定的固定频率上工作，这样即使车场中其他标签在无线通信范围内也不会被唤醒，避免了同频干扰。无线触发唤醒电路主要由无源元件构成，其基本电路如图3所示。

　　2 多标签的防碰撞算法

　　要实现多目标识别，必然要解决下述问题：在一个读写器的范围内有多个电子标签时，由于所有电子标签都采用同一工作频率，故当多个电子标签同时传输数据就会产生数据冲突，使各电子标签之间的传输相互干扰，进而导致信息的丢失，这就是通常所说的碰撞问题。在电子标签和读写器的通信过程中一般会有3种形式的碰撞：标签碰撞、读写器干扰、标签干扰。本文主要研究标签碰撞。

　　二进制搜索法又名二叉树搜索法，所有用二进制唯一标签的电子标签的ID号可以看成一棵完全二叉树。在读写器作用范围内，同步向读写器发送信号的标签ID号也构成一棵二叉树。读写器根据信号碰撞的情况反复对完全二叉树的分枝进行筛选，最终找出这棵二叉树。在寻找的过程当中逐一确定作用区域内响应的标签，同时也完成了它们与读写器之间的信息交换。

　　接下来将通过一个实例对二进制搜索算法具体实现过程进行详细的说明。采用ID为8位的4个标签，其ID分别为10110010、10100011、101 10011、11100011。

　　二进制搜索步骤如下：

　　①读写器设置筛选条件ID<11111111，向标签发送请求。

　　②阅读区内的所有标签均符合筛选条件，响应读写器的请求，发送各自的ID。

　　③读写器检测到第2、4、8位发生碰撞，即1X1X001X读写器将碰撞的最高位置0，其余低位置1，重新设定筛选

　　条件ID<10111111，向标签发送请求。

　　④标签10110010、10100011、10110011响应读写器请求，发送各自的ID。

　　⑤读写器检测到第4、8位发生碰撞(即101X001X)，读写器将碰撞最高位置0，其余低位置1，重新设定筛选条件为ID<10101111，向标签发送请求。

　　⑥标签10101111响应读写器的请求，发送ID号。

　　⑦读写器检测到没有碰撞发生，成功识别出标签10100011，然后使标签10100011处于休眠状态，完成对标签的读写。

　　⑧渎写器重新设定筛选条件为ID<11111111，重复识别过程，直至所有标签识别出来。

　　二进制搜索算法的识别示意图如图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所示。

　　本文用了3个读写器，且相互不产生碰撞，9个待定位标签进行实际定位。9个待定位标签分别放在3×3的正方形区域各个点上，临近的参考标签之间相隔2 m，具体放置的示意图如图6所示。

　　为了直观地看出定位的误差，将理论坐标和实际坐标列出定位误差，如表1所列，求出定位时产生的误差。

　　通过LANDMARC定位算法可以看出定位的精度效果还是很明显的，基本保持在1 m，效果还是相当不错的，实现了RFID的精确定位。

　　4 软件设计

　　软件的开发以MPLAB IDE 7.4为平台，应用C语言进行编写，提高了软件设计开发的工作效率，增强了程序代码的可靠性、可读性和可移植性。具体的软件设计流程如图7所示。

　　结语

　　本文主要介绍了一种基于PIC16F877A和CC2500的RFID定位设计方案，对硬件模块和软件模块进行了详细的介绍，对二进制搜索法防碰撞算法和LANDMARC定位算法进行了详细的介绍，并且利用LANDMARC定位算法保证室内定位的精度。在实际的实验中采集到大量数据，通过对数据分析验证了定位系统的可行性和准确性。