RFID多标签防碰撞算法研究

摘 要：把RFID电子标签附着在目标物体上，利用RFID阅读器读取电子标签的信息可以实现物置的确定。但是多个标签同时向阅读器发送信号时，就会发生碰撞，因此，在RFID系统中加入标签防碰撞算法，使阅读器正确、高效地读取标签信息尤为重要。本文介绍了ALOHA算法及其改进算法，并找出了改进算法中的一些待解决问题。

关键词：防碰撞 时隙 动态ALOHA算法

中图分类号：TP301.6 文献标识码：A 文章编号：1672-3791（2012）12（c）-0020-02

RFID技术是一种非接触自动识别技术，它利用无线射频信号在阅读器和电子标签之间进行双向数据传输。同一时刻可能有多个标签向阅读器发送数据造成信号干扰，这称为标签碰撞。因此，需要一种防碰撞技术来解决信号干扰问题，解决碰撞的算法称为防碰撞算法。传统的解决碰撞问题的方法有四种：空分多址（SDMA）法、频分多址（FDMA）法、码分多址（CDMA）法和时分多址（TDMA）法[1]。目前，时分多址（TDMA）法是射频识别系统解决碰撞问题的常用方法[2]。本文主要研究基于TDMA的不确定性碰撞算法ALOHA算法及其改进算法。

1 ALOHA算法

1.1 纯ALOHA算法

纯ALOHA算法是最简单的随机防碰撞算法。纯ALOHA算法中标签随机的选择一个时间点发送数据。如果该标签不被识别，即有碰撞发生，那么该标签就会随机退避一段时间，独立地再次选择一时间点重新发送数据，直至成功。如图1是纯ALOHA算法的模型。

纯ALOHA算法存在的问题是：如果退避区间太大，识别标签所需要的时间会很长；如果退避区间很小，会导致碰撞的次数增加，需要退避的次数就多，这样不但识别效率很低，而且识别时间也没有改善。纯ALOHA算法简单易行，但只能获得18.4%的吞吐率[1]。

1.2 时隙ALOHA算法

在纯ALOHA算法的基础上，人们引入时隙ALOHA算法。时隙ALOHA算法是把时间看成一个个连续片段，每一个片段称为一个时隙。一般一个时隙长度等于或稍大于电子标签和阅读器的数据交换时间。该算法中电子标签只能在时隙的开始时刻发送数据，这样或成功发送或完全碰撞，避免了纯ALOHA算法的部分碰撞，使碰撞周期减半，因此系统吞吐率比纯ALOHA提高了一倍[1]。如图2是帧时隙ALOHA算法的模型。

时隙ALOHA算法存在的问题是：每一个电子标签征用每一个时隙的几率是相等的，无论其在上一个时隙中是否被识别。即：上一时隙已经被成功识别的标签在下一个时隙被识别的几率和上一时隙未被识别的标签是相等的，这样就可能导致上一时隙已经被成功识别过的标签在下一时隙又被识别，而上一时隙未被识别的标签仍然不能被识别。这样，标签识别效率就比较低。

1.3 帧时隙ALOHA算法

针对时隙ALOHA算法中的问题，人们又引入了帧时隙ALOIHA算法。帧是指包含若干个时隙的时间段。主要思想是对阅读器引入时隙计数器和去活命令，对电子标签引入一个随机数产生器。

假设每帧包含的时隙数L，阅读器的时隙计数器从1～L计数。电子标签的随机数产生器，用来产生1～L之间的一个随机数。阅读器的时隙计数器初始值是1，且每经过一个时隙长度时隙数自动加1。识别过程开始时阅读器向其覆盖范围内所有电子标签发送一个包含时隙数L的命令，电子标签的随机数生成器生成一个1～L之间的随机数，当该随机数与阅读器的时隙计数器计数值相同时，电子标签向阅读器发送数据。标签被成功识别后，阅读器向其发送去活命令，使之退出识别系统直至当前帧结束。在一帧完成后，阅读器开始时隙数仍为L的新帧。

但是帧时隙ALOHA算法中如果总时隙数L远小于标签数目N，极有可能导致总有多于一个标签选同一时隙导致碰撞。如果隙数L远大于标签数目就造成了时隙的浪费。因此，又引入了动态帧时隙ALOHA算法。

1.4 动态帧时隙ALOHA算法

动态帧时隙ALOHA算法根据正确识别标签的时隙数和产生碰撞的时隙数来确定下一帧包含的时隙数，当电子标签数大于时隙数而造成过多碰撞时就增加下一帧的长度，反之则减小下一帧的长度，只有使时隙数与标签数量相当才能达到最佳吞吐率。但是，当标签数量远大于每帧的时隙数时，受硬件条件限制，帧长度增大有限（Lmax=256）[3]，电子标签碰撞率就会增大，识别电子标签的时间会急剧增加，系统的识别效率急剧降低。

1.5 动态帧时隙ALOHA算法的改进算法分析

针对动态帧时隙ALOHA算法中帧长度最大值受限的问题，很多学者都提出了改进的动态帧时隙ALOHA算法，其中最典型的一种改进思想是分组[3]。

基于分组的动态帧时隙ALOHA算法实际上是借用了确定性防碰撞算法的思想，即当标签数大于时隙允许最大值时，使一部分标签处于非响应状态不参与信道竞争，处于响应状态的标签被正确识别后阅读器向其发送去活命令，即使其处于非响应状态不参与信道竞争直至所有的标签都被正确识别。

基于分组的动态帧时隙ALOHA算法描述：（1）在动态帧时隙ALOHA算法的基础上估算出阅读器范围内标签个数N，如果N>256，阅读器向标签发送分组命令，把标签分为待命组和休眠组，每组标签数为256。（2）待命组标签数参与识别过程，其余标签分到休眠组暂时不参与识别过程。（3）当前帧结束后，待命组的标签自动休眠，休眠组的标签按顺序自动把状态变为待命状态。（4）重复（2）、（3）直至所有组的标签都被识别，返回（1）。

基于分组的动态帧时隙ALOHA算法在每帧内都能减少冲突，提高标签识别率。但是这个算法现在并不完美。存在的问题是：（1）由于标签在识别过程中有2种可能的状态，那么标签就必须有状态标志位，而且分组数越多标志位就越长，这就得增加标签携带信息量，给硬件设计增加了难度。（2）由于标签需要响应阅读器命令在两种状态间转换，这就增加了标签与阅读器交换数据的时间，在标签高速运动的状态下漏读率会增加。（3）由于标签被分为2组或更多组，阅读器在每帧时间内只能识别一组，如果有一组的标签数量远小于256，那么识别该组的帧内大部分时隙是空闲的，这就造成了识别时间浪费。（4）由于所有标签分多组识别，所以一个识别周期（识别完所有标签的帧数和）内标签总数是每个帧内标签数的和，这给统计标签总数增加难度。

2 结语

基于分组的动态帧时隙ALOHA算法是当今非确定性算法的主流改进算法，尽管改进方法各有差异，但是主题思想都是本文分析的参照确定性算法的思想，限制响应标签数量，将响应标签数限制在识别效率最高的标签数目之内。但是正如本文分析，这个改进思想还是存在一定缺陷，这就要求我们在以后的研究过程中继续优化算法解决这些问题，以快速、高效完成阅读器与电子标签的数据交换。

参考文献

[1] 姜丽芬，卢桂章，辛运帷.射频识别系统中的防碰撞算法研究[J].计算机工程与应用，2007，43（15）：29-32.

[2] 崔欣，.2008年全球RFID九大最具影响力事件[N].中国防伪报道，2009，2.

[3] 尹君，何怡刚，李兵，等.基于分组动态帧时隙的RFID防碰撞算法[J].计算机工程，2009，10，35（20）：268-269.

[4] 李宝山，罗春青.基于随机数传送的动态帧时隙ALOHA算法的研究[N].内蒙古科技大学报，2010，9，29（3）：254-255.