RFID

RFID专题:15 碰撞读取率A

2022-01-05 10:23:38 明申科技 873

3.3.1 基于工程场景的多标签防碰撞算法——碰撞读取率A

01、RFID常见多标签算法简介

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

其中18000-6C采用的是时隙ALOHA算法:应答器(标签)只在规定的同步时隙中才传输数据包。这种情况下,对所有应答器的同步由阅读器控制。本质上时隙ALOHA算法是一种由阅读器控制的随机时分多址(TDMA)算法。它将信道分为很多时隙,每个时隙正好传送一个分组。对于射频系统,标签只在规定的同步时隙内才能传输数据包,对所有的标签所必须的同步由阅读器控制,但发生碰撞后,各标签仍是经过随机延时后分散重发的。

时隙ALOHA算法较为实用,由于时隙ALOHA算法不关注实际冲突的位数,而只关注是否发生冲突,因此实现较为方便。但在实际系统中,其算法效率相对不高。如果应答器数目过多,时隙数量不够,发生冲突的概率增大,需要的时间也过长。因此,当多个应答器在阅读器工作范围内停留时间太短,识别率就会相应变低。

ISO/IEC 14443、15693、18000-6B采用的是二进制树的搜索算法:如果数据包在传输过程中发生碰撞,阅读器使用二进制搜索树的运算法则和一个比特的数据来解决冲突。因为每个标签本身都有一个地址(ID),所以阅读器可以指定一个特定范围内的地址来读取标签,而这些标签必须对阅读器的询问做出应答,其他标签则表示缄默。这时,如果有两个标签由于同时上传数据而发生碰撞,阅读器可以精确的检测出地址发生碰撞的比特位,并找出对应的标签。依靠二进制搜索树的运算理论,阅读器可以读出所有的标签。

基本的二进制搜索算法抗干扰能力差,数据容易误读而造成效率低,难以实现。

02、基于实际工程场景的多标签——清点率介绍

本书中的防碰撞算法结合实际阅读器特性,提出阅读器碰撞读取率这个概念,并结合了实际的工程场景,精确计算标签清点的时间期望值,从而大大提高了阅读器的清点效率有利于推动以物流仓储为代表的超高频RFID多标签场景的广泛应用。

该防碰撞算法的模型包括1个阅读器,0个或者多个应答器(标签)。使用的几个要素:Q(时隙数标识数据),A(碰撞读取率),N(标签的总量)。

在阅读器对标签清点的通信中,阅读器先向所有标签发Query指令,在Query指令中包含参数Q,Q可以取0到15之间的任意数值。

所有标签收到Query指令后会各自从0到中产生一个随机数。若标签的随机数为0则标签立即返回RN16,阅读器可以通过该RN16与这个标签通信。

当阅读器发送Query后,会连续发个Query_rep指令,标签每次收到Query_rep指令后,其随机数减1,直到随机数变为0则返回RN16。

在该通信过程中如果标签数量N比较大(比如100),而Q比较小(比如4),那么100个标签每个从0-15个数字中随机分配一个必然存在相同的随机数,那么当阅读器发Query或者Query_rep指令后两个或多个标签同时返回它们各自的RN16就发生冲突,由于两个或多个标签的数据交叠在一起,阅读器很难分辨数据,就无法和特定的一个标签进行通信,这就是冲突的产生。

发生冲突的标签会在下一轮的Query清点中被清点到,已经被清点过的标签则不响应,直到Session翻转,直到将全部的标签清点完毕。

由于技术的进步,阅读器的灵敏度和解调能力不断提高,当遭遇多标签冲突时,阅读器有一定的概率A正确解调一个标签的RN16,从而完成对一个标签的清点,在这里称这个概率A为碰撞读取率。深入研究碰撞读取率还可以分成2个标签碰撞时读取率A2,3个标签碰撞时读取率A3,或者N个标签碰撞时的读取率AN。当然为了简单分析,在这里对所有的碰撞读取率统一为A,方便大家理解和计算。

为方便后续计算,提出清点效率F这个概念,就是单位时间内识别标签的数量。假设一轮清点过程中清点到的标签数量为M,那么F=M/2.png 。为了提高清点效率,针对不同的标签数量N和当前的阅读器的碰撞读取率A,选择最优的清点参数Q。

如图3-18所示,在清点过程中,每个时隙都可能出现三种情况:

只有一个标签返回RN16,清点到标签;

有多个标签返回RN16,发生冲突,有A的概率清点到标签;

没有标签返回RN16,没有清点到标签。


1.png


图3-18标签清点示意图

这三种情况在个时隙内的期望值分别为:

只有一个标签返回:


3.png(3-2)

有多个标签返回:


4.png(3-3)

没有标签返回:


5.png(3-4)

那么清点效率为a)+b)*A:


6.png(3-5)

03、基于实际的工程场景的多标签——实例分析

假设标签数量分别为N=40、N=100和N=200,3个阅读器碰撞读取率分别为0%、10%和30%即A1=0;A2=0.1;A3=0.3。那么每个阅读器在不同标签环境中所选用的Q的最优值可以用式(3-5)计算出不同的清点效率F,将Q=4到10以及N和A的数值带入后,得到表3-11。

表3-11不同碰撞读取率、Q值、标签数量下的清点效率


N=40

N=100

N=200








A1=0

A2=0.1

A3=0.3

A1=0

A2=0.1

A3=0.3

A1=0

A2=0.1

A3=0.3

Q=4

0.202

0.271

0.419

0.010

0.109

0.307

0

0.100

0.300

Q=5

0.362

0.398

0.469

0.135

0.217

0.382

0.011

0.110

0.307

Q=6

0.338

0.351

0.377

0.329

0.375

0.467

0.136

0.218

0.382

Q=7

0.230

0.234

0.242

0.359

0.377

0.415

0.328

0.374

0.474

Q=8

0.134

0.135

0.137

0.265

0.271

0.283

0.358

0.377

0.414

Q=9

0.072

0.073

0.073

0.161

0.163

0.166

0.265

0.271

0.282

Q=10

0.037

0.038

0.038

0.089

0.089

0.090

0.161

0.162

0.166

在实际应用中根据表3-11选择清点效率最高时所对应的Q(表中斜体为最优清点率)。在传统的算法中,Q的选择依据为表3-12(传统算法中未考虑冲突识别率,可以认为A=0)。

表3-12Q值表


Q=0

Q=1

Q=2

Q=3

Q=4

Q=5

Q=6

Q=7

Q=8

Q=9

Q=10

N

0-1

2

3-4

5-8

9-16

17-32

33-64

65-128

129-256

257-512

513-1024

将传统算法和本书中创新的算法进行对比:

在标签N=40、A=0的情况下,根据表3-11计算选择Q=5,而传统算法选择Q=6,那么创新算法效率比传统增加了7.1%。若选择N=200、A=0.3,创新算法选择Q=7,而传统算法选择Q=8,那么创新算法的效率比传统算法提高了14.5%。

现在的超高频RFID阅读器种类繁多,通过对应设备的测试可以发现,每个阅读器的碰撞读取率是不同的。从阅读器的设计角度来讲,是由阅读器的射频链路性能以及基带的解调能力不同导致的。不同的阅读器在使用不同的调制编码方式时其碰撞读取率是不同的。比如Alien的ALR9900+的碰撞读取率A大概为0.3,而低端分离器件的阅读器的碰撞读取率A约等于0。

在实际应用中,应先由阅读器的协议算法控制部分根据标签个数和阅读器的碰撞读取率生成一张类似表3-11的映射表,然后根据式(3-5)计算Q从0到15所得到的所有清点率,最后选择清点率F最高时所对应的Q,作为这轮清点的Q值;下一轮清点根据剩下的标签数量继续查表选择清点率最高时对应的Q,直到标签全部清点完毕。


首页
产品
新闻
联系