rfid防碰撞算法

‘壹’ aloha提升下载速度

aloha算法可以提升下载速度。
Aloha算法是一种非常简单的TDMA算法，该算法被广泛应用在RFID系统中。这种算法多采取标签先发言的方式，即标签一进入读写器的阅读区域就自动向读写器发送其自身的ID，随即标签和读写器间开始通信。
ALOHA算法是随机接入算法的一种，当标签要发送数据信息时，它可以在任意时间段随机发送，把它称为纯ALOHA算法。为了解决标签碰撞问题，RFID系统采取两种类型的防碰撞算法，一种是确定性防碰撞算法，如二进制搜索算法、动态二进制搜索算法、跳跃式动态树型算法、查询树算法、动态查询树算法、后退索引搜索算法等。确定性防碰撞算法在整个识别过程不存在随机性，提高了信号传输速率，信道的利用率比较高，性能稳定，但是算法存在复杂度大、系统识别时延大等缺点，当标签数过多时，系统效率降低。

‘贰’ 如何解决rfid系统的防碰撞问题

RFID射频识别技术近年来广受关注，被应用于众多领域，其中UHF(超高频)频段RFID应用最为广泛。UHF RFID国际标准有ISO/IEC 180006 Type A、Type B、Type C三类，Type C类标准是最新制定的，在数据速率、调制方式等方面都要优于其他两种。本文针对Type C类标准中的防冲突算法进行研究，分析该标准采用的防冲突算法在面对快速运动标签群时的处理情况。

本文基于特定背景，快速运动的电子标签群源源不断地笔直经过UHF RFID读卡器的识别范围，如图1所示。

图1 快速运动的UHF RFID标签群

在正常情况下，当RFID电子标签读卡器范围内存在大量静止电子标签，RFID电子标签读卡器可通过防冲突算法，完成所有电子标签的识别工作;但当电子标签群运动起来，并达到一定的速度时，是否可以在有限时间内完成电子标签的读取工作是一个问题，其关键因素是防冲突算法。

能否有效地完成快速移动电子标签群的读取工作，直接影响系统的稳定性以及可靠性。未来用于快速运动标签群的UHF RFID自动识别系统将越来越多，因此本课题的研究具有一定的前瞻性以及现实意义。

1 UHF RFID介绍

射频识别(Radio Frequency Identification，RFID)是一种无线射频识别技术，它利用射频信号通过空间耦合(交变磁场或电磁场)实现无接触信息传递，并通过传递的信息识别目标。RFID的工作频段分为低频(LF)、高频(HF)、超高频(UHF)和微波(MW)，其中UHF RFID(860~960 MHz)具有读写速度快、识别距离远、抗干扰能力强、标签小等优点，被广泛应用。

1.1 协议标准

国际上主要有3个RFID技术标准体系组织：全球产品电子编码中心(EPC Global)、ISO/IEC和日本Ubiquitous ID Center(UID)。ISO/IEC 18000是基于物品管理的RFID的国际标准，按频率不同分为7个部分，其中ISO/IEC 180006规定UHF频段，针对860~930 MHz的无线接触通信空气接口参数。ISO/IEC 180006系列标准包括Type A、Type B、Type C三类标准，其主要区别在于标签识别中的编码方式以及防冲突算法等。

1.2 防冲突算法

防冲突算法是射频识别系统中的多路存取法，它是射频识别系统实现标签快速识别的关键。RFID系统识别多标签时，当有2个或者2个以上标签同时发送数据就会产生数据的干扰，这种干扰称为标签冲突。因此，在RFID系统中必须建立有效的仲裁机制来避免冲突的发生。

目前在RFID系统中使用最广泛的防冲突算法大多基于时分多址(TDMA),每个标签在某个时隙占用信道与读卡器通信，当产生冲突则暂时退避，重新选择时隙再次与读卡器通信，从而实现系统的防冲突工作。

1.3 研究背景

本文的研究基于快速运动标签群不间断地经过读卡器识别范围的特定背景。如果运动标签群速度过慢，读卡器在新标签到来之前已经完成了场内所有标签的识别工作，不会出现漏读现象，但是在这种情况下，系统识别效率就会大大降低;而当运动标签群达到一定速度时，读卡器将进行标签的防冲突处理，因为新标签的加入会产生部分标签一段时间内不被识别到，随着标签移动离开射频范围，就会出现漏读现象。

在现实生活中，满载货物的货车在通过读卡器识别范围时，要求系统快速有效地读取货车上所有货物的物品信息。货车通过读卡器的速度直接影响系统的工作效率，快速通过能节约大量时间和成本。

所以，如果要提高系统效率并且保证系统可靠性，移动标签群必须达到一个适中的速度，并且防冲突算法一定要对此种情况进行有效处理。本文研究ISO/IEC 180006 Type C的防冲突处理算法，分析其对快速运动标签群是否有可靠的对策和处理方式。

2 Type C防冲突算法

2.1 Aloha算法

常用的防冲突算法大多是基于Aloha算法——一种无规则的时分多址(TDMA)算法。Aloha算法规定标签周期性地发送数据给读卡器，数据传输时间只是周期时间的一小部分，标签传输中有很长时间的停歇，因此有一定概率使两个标签在不同时隙传输数据，以避免冲突。

基于Aloha算法出现了很多改进算法：时隙Aloha算法、帧时隙Aloha算法、动态帧时隙Aloha算法等。Type C采用的防冲突算法是随机时隙防冲突算法，其本质跟帧时隙Aloha机制一样。

2.2 随机时隙防冲突算法(SR)

随机时隙防冲突算法本质上与帧时隙Aloha机制类似，其帧长度为2Q,并且该机制根据标签应答情况来调整Q值，改变下一个识别周期的时隙数，让未识别标签重新选择。当一帧中出现过多的冲突时隙时，读卡器会提前结束该帧，并选择一个更大的Q值发送给标签群;当一个帧中出现过多的空闲时隙时，读卡器会提前结束该帧，并选择一个比较小的Q值发送给标签群。

随机时隙防冲突算法命令包括Query、QueryAdjust、Query Rep等,主要参数为时隙计数参数Q。协议中的Q值决定了防冲突时所用的时隙数,读卡器通过给标签发送相应命令改变标签状态，完成防冲突工作。协议规定标签有3个状态，如图2所示。

图2 电子标签状态图


当系统上电或信道空闲时，读卡器发送Query命令，启动清点周期，初始化一个识别周期，并决定哪些电子标签参与本轮识别周期。Query命令包含时隙计数参数Q，当接收到Quary命令时，RFID电子标签读卡器在识别区域内随机选择进入识别周期的标签，所有参与电子标签在(0，2Q-1)范围内选择一个随机数，并置入它们的时隙计数器。选到0值的电子标签变为应答状态，并响应读卡器，回答一个16机制随机数(RN16)给读卡器;没有选到0值的标签变为仲裁状态，等待下一条Query Adjust或Query Rep命令;没有进入本轮识别周期的电子标签保持休眠状态。

处于仲裁状态的电子标签每接收到一条Query Rep命令，它们的时隙计数器减一次，当时隙计数器减到0000h时，标签转变为应答状态，响应读卡器。当时隙计数器值为0000h，并且已经应答，但没有得到确认时，标签变为仲裁状态，当接收到下一条QueryRep命令时，签时隙计数器减一变为7FFFh，防止随后应答，直到标签接收到Query Adjust命令或者进入下一个识别周期。在2Q-1条QueryRep命令中，所有标签至少应答一次。

当电子标签时隙计数器同时达到0000h，并同时应答，会产生冲突;当标签时隙计数器都不等于0000h,读卡器接收不到响应。面对这两种情况，读卡器可能需要重新选定Q值，读卡器根据的自适应Q算法如图3所示。

图3 自适应Q算法

由自适应Q算法可知，当某一时隙出现冲突或者无响应的情况，Qfp的值会增大或减小，然后对Qfp四舍五入得到新的Q值。如果Q值发生变化，读卡器发送Query命令更新Q值，并使标签重新选择时隙计数器;否则继续发送QueryRep命令，让所有标签时隙计数器减一。自适应Q算法通过根据标签冲突以及无响应情况动态地改变Q值，从而改变时隙数，实现自适应防冲突。

3 存在的问题及解决方案

3.1存在的问题

本文的背景是快速运动标签群通过读卡器射频区域，该种情况必须注意的是，读卡器范围内的标签是动态变化的，随时都有新标签加入读卡器的识别范围，从而影响系统的防冲突处理。通过对ISO180006 Type C防冲突算法过程的研究，发现该算法在面对快速标签群时并未做有效的处理。

根据算法的工作过程，当UR6258电子标签读卡器开始电子标签的识别工作，首先发送Query命令开启一个清点周期，高速运动标签群进入读卡器识别范围，上电进入休眠状态。读卡器在识别范围内选择部分标签进入清点周期，部分标签没有被选择而保持休眠状态，等待下一个清点周期的到来。当上一个清点周期结束，读卡器会发送Query命令开启新的清点周期，这时候读卡器识别范围内会有新加入的标签，读卡器会从所有标签中再次随机选择部分标签进入清点周期。新标签的加入导致部分标签可能始终无法进入清点周期，无法被识别到，然后离开读卡器识别范围。

另外一种情况是，电子标签进入清点周期后，在电子标签应答发生冲突或者未收到回复的情况下，时隙计数器由0000H减1变为FFFFH，避免随后应答。这时候会有两种情况：一种是由于碰撞或者无响应的情况导致Q值发生变化，这时允许所有标签重新随机选择一个值放入时隙计数器，在清点周期内获得再一次被识别的机会;如果冲突以及无响应现象没有导致Q值发生变化，那么在本轮清点周期结束后，它会同新进标签一起争取下一次进入清点周期的机会，所以会有几率无法进入清点周期，直到离开读卡器的识别范围。

假设运动标签群的运动速度为v,标签在读卡器识别范围内运动距离为d,那标签在识别范围内的时间t=v/d。假设读卡器进行一轮标签读取的时间为T，而标签被识别所需的周期为n(n为正整数)，那么当n·Tv/d，则会出现标签不被识别的情况。

以上两种情况的发生都可能会导致标签群中部分标签一段时间不被识别，通过读卡器的识别范围，从而造成系统的不可靠，出现漏读。

3.2 解决方案

针对快速运动标签群的识别，主要问题是新标签与旧标签争抢进入清点周期的机会，而旧标签在读卡器识别范围的时间有限。面对这种情况，解决问题切入点是让旧标签比新标签拥有更多的机会进入清点周期，或者直接不允许新标签与旧标签竞争，而是等待旧标签完成识别才开始新标签的识别工作。拟采用两种方法解决该问题。

第一种是基于标签到场时间的解决方案。标签进入射频范围内上电，标签内到场计时器开始计时，计时值为t，读卡器选定一个适当的计时值T，发送Query命令开始清点周期的同时发送T，标签把自己的计时值与读卡器所要求的T大小作比较：如果t

第二种是基于标签到场点名的办法。当某一时刻系统启动，读卡器开始发送Query命令进入清点周期之前发送点名命令，让识别范围内的标签由休眠状态进入到场状态。之后只选择到场状态的标签进入清点周期，待所有到场标签完成识别再进行新一轮点名。这种方案可以完全解决新旧标签的竞争问题。

结语

针对快速运动标签群的特殊背景，研究了ISO180006 Type C类标准的随机时隙防冲突算法(SR)，研究得知该算法并没有针对该种情况进行有效的处理，会出现漏读现象。在不改变原有算法本质的前提下提出了基于到场时间以及基于到场点名两种解决方案。
参考：http://www.rfidhb.com/rfid/knowledge/446.html

‘叁’ 关于RFID防碰撞算法中的Q值算法

Q=S/G,CN=1/Q,so C=G/(S*N)

‘肆’ 求解释RFID的防碰撞算法中的查询树QT算法麻烦详细说一下算法原理，如何防碰撞的谢谢~

查询树QT（QueryTree）是一种典型的树结构算法，其算法原理：读写器发送长度为k的prefix（前置代码，一般为置于一组号码前的数字或字母，表示所属区域等）；标签ID中前kbit与prefix匹配的tag反馈第(k+1)bit至最后1bit。如果读写器收到的标签ID碰撞，再分别将prefix加“1”和“0”，作为新的prefix发送出去。如果没有碰撞，就表明一个标签被识别了。

举例：设有三个标签ID分别为“010”，“011”，“100”，读写器的查询序列首先置为“0”、“1”，读写器先发送序列“0”进行查询，发生碰撞，此时将序列置为“00”、“01”，再次分别发送，序列“00”没有响应，序列“01”发生碰撞，将序列置为“010”、“011”，成功识别。回溯到序列“1”，只有标签“100”响应，成功识别。如图所示