RFID干货专栏｜16 碰撞算法、综合解决方案

RFID干货专栏概述

经过20多年的努力发展，超高频RFID技术已经成为物联网的核心技术之一，每年的出货量达到了200亿的级别。在这个过程中，中国逐步成为超高频RFID标签产品的主要生产国，在国家对物联网发展的大力支持下，行业应用和整个生态的发展十分迅猛。然而，至今国内还没有一本全面介绍超高频RFID技术的书籍。

为了填补这方面的空缺，甘泉老师花费数年之功，撰写的新书《物联网UHF RFID技术、产品及应用》正式出版发布，本书对UHF RFID最新的技术、产品与市场应用进行了系统性的阐述，干货满满！RFID世界网得到了甘泉老师独家授权，在RFID世界网公众号特设专栏，陆续发布本书内容。

扫码观看本章节视频讲解

3.3.2基于实际场景的多标签防碰撞算法——动态Q算法

01、标签数量N与Q的概率分析

从13.56MHz频段的ISO/IEC 14443协议、ISO/IEC 15693协议到900MHz频段的ISO/IEC 18000-6B/C协议，防碰撞协议在现有的技术中一般都基于两种基本算法：时隙ALOHA算法和二进制树的搜索算法。

3.3.1节的多标签碰撞算法是针对已知固定数量标签场景中所使用的方法。在不知道天线覆盖场内有多少标签时，Q怎么选择，如何最有效率地读取标签，就需要一个可以自动调节的Q算法来实现，称之为动态Q算法。

考虑一下，在标签数量未知的情况下如果Q是固定的一个数字，那么无论Q设什么样的数字都会存在很大问题。比如我们把Q设为4，如果场内有500张标签，一定会出现碰撞严重导致很难读全；如果场内标签只有1张或没有，又需要浪费许多时隙时间。这个时候就需要动态Q算法，即阅读器可以根据场内读取的标签数量以及效果进行动态的调整，如果标签多，Q就自动变大；如果标签少，Q就自动变小。那如何判断场内的标签数量呢？这需要从概率的角度着手进行分析。阅读器对标签的识别体现在每一个时隙上，根据3.2.1节中的分析，在一个时隙内可能发生三种情况，分别是一个标签返回：读取；多个标签返回：冲突；没有标签返回：空闲。在不考虑碰撞读取率时（A=0），这三种情况下根据标签数量为N、清点参数Q的清点效率F的概率表达式如下：

①只一个标签返回——读取：

②有多个标签返回——冲突：

③没有标签返回——空闲：

只是通过这样枯燥的算式，发现不了任何规律。不妨假设场内标签的数量为固定的一些数量，选用不同的Q时碰撞和无返回的概率是多少。假定场内的标签数量分别是：N=1、2、5、10、20、50、100、200、500、1000；动态Q=1、2、3、4、5、6、7、8、9、10。将这些参数带入式（3-6）得到读取的概率如表3-13所示；同理，带入式（3-7）和式（3-8）可得到表3-14碰撞概率和表3-15空闲概率。

从表3-13中可以明显的看到在标签数量N不同时，不同的Q的读取率是不同的，且读取率比较高的Q一般在附近。如N=10，在Q=3和Q=4 之间，此时读取率最高的为Q=3时的0.38和Q=4时的0.35。从表3-13中也可以看到，表格的左下角和右上角的概率基本都是0，左下角为时隙多标签少空闲的概率大导致读取率低；右上角时隙少标签多碰撞概率大导致读取率低。

在正常的多标签动态算法的过程中如果连续两个时隙的状态都是读取状态，就说明当前的Q与N非常合适，不需要进行Q的调整。

表3-13读取Q、N概率表

从表3-14碰撞Q、N概率中可以发现N越大碰撞概率越大，Q越小碰撞概率越大，该表格的右上角碰撞概率基本都为1，就是说100%发生碰撞，就需要把Q调大。

在正常的多标签动态算法的过程中，如果连续两个时隙的状态都是碰撞状态，就说明当前的Q相对于N太小，需要增大Q。也可以通过表3-14计算得出结论，假定当前状态为N=10，Q=2，碰撞概率为0.76，连续两次碰撞的概率为0.76×0.76=0.57，此概率大于50%，就需要将Q增大为3。通过表3-11已知N=10时Q=3或4为最合适的，刚好与之前的结论想吻合。

表3-14碰撞Q、N概率表

从表3-15中可知标签N越多空闲概率越小，Q越大空闲概率越大，该表格的左下角概率值都为1，就是说100%发生空闲，就需要把Q调小。

在正常的多标签动态算法的过程中如果连续两个时隙的状态都是空闲状态，就说明当前的Q相对于N太大，需要减小Q。读者也可以通过表3-15计算得出结论，假定当前状态为N=10，Q=5，碰撞概率为0.73，连续两次碰撞的概率为0.73×0.73=0.53，此概率大于了50%，就需要将Q减小为4。通过表3-11已知N=10时Q=3或4为最合适，刚好与之前的结论相吻合。

表3-15空闲Q、N概率表

02、动态Q的实例分析

经过上述的算法和概率分析，已经了解了Q变化的基本要领，但是在实际的案例中，阅读器的动态Q是如何设置的呢？笔者通过对主流阅读器的动态Q算法研究，总结了一套非常适合工程应用的动态Q方法，其步骤如下：

①Q=0 检测场内是否有标签；

②Q=3 初始化Q状态识别标签；

③连续碰撞2次，则Q+1；连续空闲2次，则Q-1，无连续碰撞和连续空闲则读取识别；

④连续发3次Q=0为空，确定全部识别，场中不剩下任何标签；

⑤掉电开启下一轮盘点。

该动态算法中，①首先发Q=0，看场内是否有标签，会出现3个情况，如果没有标签则跳转到⑤进行下一轮盘点；如果有一个标签则读取该标签数据跳转到④，确认场内没有标签后再跳转到⑤进行下一轮盘点；如果场内有多张标签则跳转到②Q=3 初始化Q状态进行识别标签再到③、④、⑤。

这里将步骤③和④的组合称之为基础动态Q策略，这个策略是最常用的动态Q策略，读者也可以开发类似的动态Q策略，比如监控多次识别的结果判断Q是否跳转等，不过实际测结果比基础动态Q策略的提升不会超过10%（笔者验证过大量AI动态Q策略，虽然优于基础动态Q策略，但进步不大且较为复杂）。

假定场内标签数量N=100，但是阅读器未知该信息，此时的多标签动态Q识别过程如下：

运行①Q=0，发生冲突、场内存在多个标签（N=100；时隙M=1）；

运行②Q=3，（N=100）；

运行③ Q=3时连续两次冲突Q=4（N=100；M=2）；

运行③ Q=4时连续两次冲突Q=5（N=100；M=2）；

运行③ Q=5时连续两次冲突Q=6（N=100；M=2）；

运行③ Q=6时连续进行读取，第一轮读取标签21个还剩79个（根据表（3-13）中Q=6、N=100概率给出数据33%×64=21，实际情况略有不同）（N=79；M=64）；

运行③ Q=6时继续进行读取，第二轮读取标签23个还剩56个（根据表（3-13）中Q=6、N=79概率为36%×64=23，实际情况略有不同）（N=56；M=64）；

运行③ Q=6时继续进行读取，第三轮读取标签24个还剩32个（根据表（3-13）中Q=6、N=56概率为37%×64=24，实际情况略有不同）（N=32；M=64）；

运行③ Q=6时继续进行读取，第四轮读取标签20个还剩12个（根据表（3-13）中Q=6、N=32概率为31%×64=20，实际情况略有不同）（N=12；M=64）；

运行③ Q=6时连续两次空闲，Q=5（N=12；M=2）；

运行③ Q=5时继续进行读取，第五轮读取标签8个还剩4个（根据表（3-13）中Q=5、N=12概率为26%×32=8，实际情况略有不同）（N=4；M=32）；

运行③ Q=5时连续两次空闲，Q=4（N=4；M=2）；

运行③ Q=4时连续两次空闲，Q=3（N=4；M=2）；

运行③ Q=3时继续进行读取，第六轮读取标签3个还剩1个（根据表（3-13）中Q=3、N=4概率为33%×8=3，实际情况略有不同）（N=1；M=8）；

运行③ Q=3时连续两次空闲，Q=2（N=1；M=2）；

运行③ Q=2时继续进行读取，第七轮读取标签1个还剩0个（根据表（3-13）中Q=2、N=1概率为25%×4=1，实际情况略有不同）（N=0；M=4）；

运行③ Q=2时连续两次空闲，Q=1（N=0；M=2）；

运行③ Q=1时连续两次空闲，Q=0（N=0；M=2）；

运行④取连续发3次Q=0 确定全部识别；

掉电重复下一轮盘点。

从上述识别过程中Q先变大再变小最终将所有标签都识别到，并确认场内没有遗漏的标签。虽然看起来非常繁琐，但是大大提高了识别效率。对识别效率的评估可以通过标签时隙比实现，即总共标签数量与总共时隙的比值，比值越高说明效率越高。标签数量N=100个，间隙数量就是把从1）到20）的所有时隙加起来M=319，那么标签时隙比为100÷319=31.3%，这是一个非常高的效率值。

为了让读者了解动态Q的优势，将其与固定Q算法进行对比。此处采用固定Q的最优方式，假设阅读器已知场内标签数量。在N=100时，已知Q=7具有最高的识别率，那么：

Q=7，N=100，读取率0.36*128=46个，（N=54；M=128）；

Q=7，N=54，读取率0.28*128=36个，（N=18；M=128）；

Q=7，N=18，读取率0.12*128=15个，（N=3；M=128）；

Q=7，N=3，读取率0.023*128=3个，（N=0；M=128）；

Q=7，N=0，读取率0个，（N=0；M=128）

从Q=7的固定Q可以看到一共运行5轮确定所有标签都被识别且M=640，对应的标签时隙比为15.6%。

再对比一下Q=6，N=100的情况，固定Q=6，那么：

Q=6，N=100，读取率0.33*64=21个，（N=79；M=64）；

Q=6，N=79，读取率0.36*64=23个，（N=56；M=64）；

Q=6，N=56，读取率0.37*64=24个，（N=32；M=64）；

Q=6，N=32，读取率0.31*64=20个，（N=12；M=64）；

Q=6，N=12，读取率0.16*64=10个，（N=2；M=64）；

Q=6，N=2，读取率0.031*64=2个，（N=0；M=64）；

Q=6，N=0，读取率0个，（N=0；M=64）。

从Q=6的固定Q可以看到一共运行7轮确定所有标签都被识别且M=448，对应的标签时隙比为22.3%。

再对比一下Q=5，N=100的情况，固定Q=5，那么：

Q=5，N=100，读取率0.135*32=4个，（N=96；M=32）；

Q=5，N=96，读取率0.147*32=5个，（N=91；M=32）；

Q=5，N=91，读取率0.163*32=5个，（N=86；M=32）；

Q=5，N=86，读取率0.181*32=6个，（N=80；M=32）；

Q=5，N=80，读取率0.204*32=7个，（N=73；M=32）；

Q=5，N=73，读取率0.232*32=7个，（N=66；M=32）；

Q=5，N=66，读取率0.262*32=8个，（N=58；M=32）；

Q=5，N=58，读取率0.297*32=9个，（N=49；M=32）；

Q=5，N=49，读取率0.334*32=11个，（N=38；M=32）；

Q=5，N=38，读取率0.367*32=12个，（N=26；M=32）；

Q=5，N=26，读取率0.367*32=12个，（N=14；M=32）；

Q=5，N=14，读取率0.290*32=9个，（N=5；M=32）；

Q=5，N=5，读取率0.138*32=4个，（N=1；M=32）；

Q=5，N=1，读取率0.031*32=1个，（N=0；M=32）；

Q=5，N=0，读取率0个，（N=0；M=32）。

从Q=5的固定Q可以看到一共运行15轮确定所有标签都被识别且M=480，对应的标签时隙比为20.8%。

关于其它固定Q的标签时隙比，这里不做更多的计算，但明显可以推论Q大于7时会有更多的空闲，导致M偏大，而Q小于5的会有大量的冲突，同样导致M偏大。在未知场内标签数量的情况下使用动态Q算法会比即使已知场内标签数量的固定Q算法效率高50%。因此应用中合理使用动态Q会大大提高多标签识别的效率和准确性。

3.3.3 多标签识别综合解决方案

由于近些年来超高频RFID的应用场景越来越多，面临的多标签识别和环境干扰等诸多挑战，尤其是阅读器厂商在设计和生产阅读器时并不知道客户的最终应用场景。因此阅读器的适应性需要很强，能够根据具体情况在多个场景中自动切换。本节将给出一套完整的解决方案，通过算法调节多个参数最终实现阅读器可以应对绝大多数的标签识别场景。

首先将所有超高频RFID识别的应用场景和需求总结如下：

场内标签数量：没有标签、1个标签，几十个标签，几百个标签或一两千个标签等多种可能性。

识别率：需要保证每一轮的识别将场中的标签全部都清点完毕，不能存在遗漏。

识别速度：在保证识别率的前提下需要保证尽可能最快的方式实现场内的标签识别。

现场环境：无论在实验室的良好环境中，还是在恶劣的工厂干扰环境中，都保证最优的识别率和识别速度。

覆盖范围：许多场景中标签分布比较分散，或标签的位置较差，需要更大的覆盖范围，保证对弱标签的识别效果。

根据上述需求，可以从本章学习的多个参数中找到解决问题的手段：

Session会话层，可以使已经被识别到的标签不再重复响应阅读器的命令。

BLF链路速率，既可以提供较高的链路速率实现高速识别，又可以提供较低的链路速率实现较高的灵敏度。

FM0/Miller编码，FM0可以提供高的链路速率实现高速识别，Miller8可以提供较好的抗干扰特性。

动态Q算法，可以实现不同数量的多标签识别率和最高效的清点率。

多天线场景：在多天线的场景中，不仅实现区域的覆盖，同时满足识别率和识别速度（增加多个天线可以增加覆盖范围和识别率，但多天线的场景中有大量的标签是重复覆盖的，需要采用Session解决重复识别的问题）。

上面的几条需求看似不可能完成的任务，但在超高频RFID的技术专家多年的努力研究下，最终找到了完美的解决方案。解决方案如下：

①、配置初始参数Session=1；TargetA到B; 初始天线=1。

②、配置BLF=640kHz；编码=FM0；Q=4。

③、基础动态Q策略（连续碰撞2次Q+1；连续空闲2次Q-1，无连续碰撞和连续空闲则读取识别；直至3次Q=0为空）。

④、配置BLF=40kHz；编码=Miller8；Q=3。

⑤、基础动态Q策略。

⑥、若存在多天线则跳转为下一个天线重复②到⑤，直至所有天线轮询一遍。

⑦、配置初始参数Session=1；TargetB到A; 初始天线=1。

⑧、②到⑤。

⑨、⑥。

⑩、掉电继续下一轮盘点。

上述策略的步骤为，首先采用最高速率的配置参数组合BLF=640kHz、编码=FM0将场中绝大多数容易识别的标签快速盘点完成，采用初始Q=4是工程经验选择，具有最好的适应性。第二次识别采用系统中抗干扰和灵敏度最高的配置参数组合BLF=40kHz、编码=Miller8将场中的一些信号较弱的标签实现盘点，Q=3的初始值是因为剩下未盘点的标签一般数量较小，采用较小的初始Q足够满足需求。

此时再跳转到另外一个天线重复前面的操作，由于所有已经被天线1盘点到的标签已经在Session1跳转到了B状态，新的天线在盘点时不会发出响应，故不会因为重复覆盖而影响盘点速度。当所有天线都完成上述操作后，场内的标签已经全部完成盘点，则进入下一轮反向盘点。最终所有的标签状态又回到了Target A，一次完整的盘点结束。

本节提供的多标签识别综合解决方案是市面上最优的解决方案，如果还要提升系统性能，则需要优化多标签碰撞识别率A和基础动态Q策略，前者可以通过提升阅读器的灵敏度和数字信号处理算法实现，后者可以通过AI学习算法增强也可以使用Matlab多次仿真取最优策略，但这两者投入较大，对于系统的识别率和识别速度提升空间有限。

3.3节中几种基于Gen2的多标签算法是笔者经过多年的研究和许多项目实践经验总结出来的结论，在应用和阅读器的开发中会有帮助。虽然本节有许多计算内容，但都是比较简单的基础计算，如果读者也能自己推导，并根据推导的结果用阅读器和标签进行验证，对这部分知识的理解会更有帮助。