基于动态位隙分组盲分离的UHF RFID防碰撞算法

栗华，贾智平，王洪君，刘琚,3

（1. 山东大学 计算机科学与技术学院，山东 济南 250100; 2. 山东大学 信息科学与工程学院，山东 济南 250100；3. 西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071）

1 引言

在标签密集的RFID应用系统中，一个阅读器的作用范围内常常同时存在 2个或 2个以上的标签。此时，阅读器所发出的查询命令往往会引起多个标签的同时响应。这些响应信号混叠在一起，就会使标签响应信号难以被阅读器辨识，从而引起多标签冲突(multi-tags collision)[1]。阅读器为完成对所有标签信息的阅读，应将这些冲突的标签逐个区分开来，然后再和它们逐个通信。阅读器完成这类工作所使用的算法就是多标签防碰撞算法（multi-tags anti-collision algorithms）。RFID防碰撞算法的标签识别率（即：阅读器每次阅读操作可以成功读取的标签数，有时也称为防碰撞算法的算法效率）与阅读器的标签吞吐率（阅读器在单位时间内可以成功读取的标签数）密切相关，也与整个RFID应用系统的工作效率密切相关。

目前，常用的UHF RFID标签防碰撞算法有2类，一类是基于Aloha技术的随机性防碰撞算法，另一类是基于二进制树搜索技术的确定性防碰撞算法。前者要求标签在发生碰撞后重新随机选择发送时隙，后者将标签进行树形分类，逐步缩小响应标签群的范围。这2类防碰撞算法的目的都是缩小标签响应范围，最终使同一个时刻只有一个标签对阅读器的查询命令做出响应。为此，阅读器和标签之间需要多次协调通信，从而使得单标签识别时间加长，阅读器的标签识别率降低。如动态帧时隙Aloha算法的最大标签识别率仅为 42.6%[2]，二进制树回退算法的最大标签识别率也低于 50%[2,3]。因此，若想进一步提高阅读器的标签识别率，必须采用新机制的防碰撞算法。

盲源分离(BSS, blind source separation)是20世纪80年代发展起来，并于21世纪流行起来的一种信号处理技术。盲源分离技术不利用任何训练数据，也没有许多先验知识，只是基于源信号的某些最基本的统计特征（如统计独立性），便可将源信号进行盲分离。这项技术已被广泛应用于生物医学工程、语音增强、遥感、雷达与通信系统等领域。

独立分量分析(ICA)[4]是一种常用的盲源分离方法。这种盲源分离技术利用了多源信号之间的统计独立性，并且是基于2个不确定性（即源信号排列顺序的不确定性与源信号幅值和极性的不确定性）假设进行的。

由于多个 RFID标签的反射数据间具有统计独立性，符合ICA算法的源信号独立性要求；标签信号具有超高斯分布特性，符合ICA算法的源信号非高斯特性要求[5]；另外，由RFID编码技术可知，其反向链路的 FM0编码[6,7]标签数据由码元期间信号电平的相对变化情况来决定，而对于信号的符号是不敏感的。Miller编码[6,7]与之类似，即标签信号满足ICA算法的信号幅值不确定性要求；而标签识别的目标就是将各个标签信号能够正确无误地识别出来，至于标签识别的顺序无关紧要，这就满足了ICA算法的信号顺序不确定性要求。由此可见，利用ICA技术将多天线阅读器所接收的观测信号进行盲处理，从而分离出各标签信号，从理论上是可行的。

另外，利用快速ICA（fast ICA）算法对多标签随机混合数据进行了盲分离，具有运算量低，运算速度快，便于硬件实现等优点使其特别适合于多标签数据的盲分离。

本文首先分析了UHF RFID多天线系统的系统模型，据此分析了基于 TDMA技术的多标签混合数据之间的盲分离可行性。在此基础上，提出了基于位隙动态分组的盲分离（BSDBG, blind separation and dynamic bit-slot grouping）多标签防碰撞算法。文中分析了该算法的基本原理、算法性能以及算法性能与天线个数的关系等内容。理论分析和仿真实验证明该算法的标签识别率可超过 1，远远超过了传统随机性和确定性的TDMA RFID防碰撞算法的标签识别率。

2 UHF RFID多天线系统模型及多标签混合数据可分离性分析

多天线 RFID系统中的阅读器具有多天线结构，其系统模型如图1所示。

图1 多天线UHF RFID系统模型

阅读器的多个天线会同时辐射载波信号，标签从这些载波信号接收电磁能量为其自身供电，同时标签对这些载波信号进行反向散射调制，以实现信号的反向传递。

假设在阅读器作用范围内存在N个标签sT1,sT2,…,sTN，阅读器具有M个天线，接收到M个混合信号x1,x2,…,xM，经过阅读器盲分离处理后的输出信号为1y,2y,…,Ny。

这里假定js具有单位功率（实际标签反射功率的不一致可以归结到式中衰减系数ija里面去），ija就是综合考虑了各种因素的阅读器接收功率的衰减因子。

当线性混合系统中的n个源信号s1,s2,… ,sn之间具有统计独立性时，盲源分离技术可以简化为ICA技术。为求解ICA问题，一般需要满足如下几个假设条件[8]。

1) 各个源信号s1,s2,… ,sn都是零均值的实值随机信号，并且在任意时刻这些信号之间都是相互统计独立的。

2) 源信号数目n和观测信号数目m相等，混合矩阵A为n阶未知方阵，且满秩。

3) 不允许有2个以上的源信号是高斯信号，否则源信号不可分。这是由于2个以上的统计独立性高斯信号的混合信号仍然是高斯信号，无法对其进行唯一性分解。

4) 各观测信号引入的噪声很小，甚至可以忽略不计。对于噪声较大的情况，可以将噪声也视为一个信号源，并将它与其他信号源分离开来。

5) 求解 ICA时，需要对各源信号的概率分布有一些基本的先验知识，比如各源信号的概率分布具有超高斯分布特性（如拉普拉斯分布）或者亚高斯分布特性（如均匀分布）。

当式（3）中，M＞N时，A为列满秩的，这时称盲源分离为超定的。当M＜N时，A为行满秩的，这时称盲源分离为欠定的。当MN= 时，A为满秩方阵，这时称盲源分离为正定的。正定盲源分离具有唯一解，超定盲源分离多个观测信号之间往往具有非独立性，利用主成分分析（PCA, principal component analysis）技术，使混合矩阵变为方阵后，可以求出估计信号的唯一解。而对于欠定盲源分离则不具备唯一解，欲求得确定性解，需要其他约束条件，实现起来比较困难。为使用ICA，应使多标签信号为超定或者正定的。

为满足多标签混合信号的超定或正定盲分离要求，阅读器天线的个数应该大于或者等于需要同时读取的标签的个数。在标签密集的应用环境里，在阅读器作用范围之内，同时存在的标签数目可能很多（如零售行业，常常多余10个）。而受成本的制约，阅读器天线的个数不可能很多（一般情况下应少于8个）。为保证同时响应的标签数目少于天线的数目，可利用位隙分组算法对标签进行分组，通过选择合适的组数，使得每个组内的标签个数不多于天线个数，再用盲源分离技术对混合信号进行盲分离。

3 基于位隙动态分组的盲分离 UHF RFID多标签防碰撞算法描述

C. S. Kim等[9]提出了一种利用位隙（bit-slot）来对标签进行分组，实现标签防碰撞的算法。该算法的基本思想就是在标签收到阅读器的盘存命令后，令一个128bit的二进制数任意一比特（随机选择）为 1，而其他的比特为 0，在回答阅读器的提问时，标签将这个128bit的二进制数回答出来，阅读器可以根据这个128bit的数哪一比特是1，来实现标签的分组，如图2所示。

图2 位隙算法工作原理

需要特别说明的是位隙信息0的载波调制方法与普通标签识别码ID及其他信息0的载波调制方法是不同的。对于位隙信息中的0比特，标签不对载波进行任何调制。这样做的目的是防止各标签发送位隙信息时引起0和1的冲突，造成阅读器无法完成对位隙信息中为1的比特的识别。

位隙信息和 ID信息调制方法的对比如图 3所示。

图3 位隙信息调制方法

位隙分组追求的目标是在阅读器天线数量和标签数量确定的情况下选择一个合适的组数。所谓的合适分组数就是采用该分组数进行分组后能够使每个分组内标签的个数刚刚小于或者等于天线数M，刚刚能够满足 ICA算法的正定或者超定要求。如果少于该分组数，则分组后的标签混合数据无法满足正定或超定要求，如果多于该分组数，则每次同时识别的标签数又太少，算法整体效率将有所降低。同时，分组的最终目的是为了正确地分离出数据，至少使得分离出的数据符合编码要求，进而能够识别出每一比特是0还是1。为此，这里采用2次判定决定合适的分组数。将标签混合数据是否满足正定或超定性要求为第一次判定，判定的方法就是查看观测数据阵列的秩（低噪声工作环境）或者观测数据相关矩阵（较强噪声工作环境）的主特征值数是否小于或者等于天线数量（小于为超定，等于为正定）。以分离结果是否清晰可读（即分离信号是否符合 FM0编码规则）为二次判定。只有同时满足这2次判定，但分组数又比较小的情况下，该分组数才是合适的分组数。

整个算法的步骤如下。

1) 当标签进入阅读器的工作范围时，阅读器将开始位隙序列（SSNB, start serial number of bitslot）长度初始化为1。

2) 阅读器发出一个 Query (SSNB)。所有的标签在收到该命令后，根据SSNB的大小确定自己的响应位隙（RSNB, response serial number of bit-slot）长度，并随机选择1bit为1，其他比特都是0。然后对该命令作出响应，将它们的标签RSNB传送回阅读器。阅读器检查所收到的标签返回位隙值RSNB。

3) 如果接收的RSNB所有比特都为0，则说明已没有标签存在，转 8)结束。否则，令查询 SNB（QSNB, query serial number of bitslot）为零，找到接收RSNB中为1的最低比特，让QSNB对应的位为1，其他比特保持为0，形成本组的查询QSNB。并将RSNB中这个为1的最低比特清0。

4) 阅读器发出一个位隙盘存命令 QueryRepB(QSNB)，所有标签在收到该命令后将自己的RSNB与QSNB进行比较，若其RSNB等于QSNB则对阅读器的盘存命令作出响应，将它们的 16bit随机数RN16或者32bit随机数RN32传送回阅读器。如果阅读器没有收到标签响应信号，说明本组内已没有标签需要读取，转3)。否则，继续。

5) 阅读器检查观测信号X的秩或者其相关矩阵的主特征值数是否小于阅读器天线数量M，如果小于M，说明符合初步判定要求，进而利用FastICA算法对观测信号X进行解混合，查看每个分离信号是否清晰可辨，如果清晰可辨，则满足二次判定标准，计算出本组的分离矩阵W，转步骤7)。如果初步判定标准或者二次判定标准不满足，则说明分组数量太少ICA无法正确将数据分离，继续执行步骤6)。

6) 阅读器将盘存开始位隙序列长度 SSNB乘2，转步骤2)。

7) 阅读器发出读本组命令Read(QSNB)，本组内标签继续发送自己的PC+EPC+CRC16信息，阅读器利用本组分离矩阵W继续分离所接收的信息，检查无误后，存储这些标签的信息，并将成功读取的标签除掉，转步骤4)。

8) 结束。

4 BSDBG算法性能分析与验证

设标签个数为n，阅读器天线个数为M，分组数SG，系统工作环境符合ICA算法信噪比要求，那么通过位隙分组后，通过动态探索尽量使每个组内的标签个数小于等于M。

为达到这一最佳分组，需要分组探索的次数为

其中，ceil( . )表示向上取整，如ceil( 0 .4)= 1 ，ceil( 1 .6) = 2 。

分组数的调整是以乘2方式进行的，因此计算分组搜索次数的式(4)中存在lb(ceil(n/M) )项。

标签位隙分组数为

通过位隙分组后一个组内没有任何标签的概率为

一个组内有一个或者多个标签选择的概率为

具有单个或者多个标签的组的个数为

分离这些标签数据所需要的查询次数为

总的查询次数为

算法标签识别率（即算法效率）为

假定标签数n=1～256，阅读器天线数为M= 4 ,分组数Gs、总查询次数S(n)以及算法标签识别率E(n)随标签数n变化的规律如图4～图6所示。

图4M=4时标签分组数GS随标签数量n的变化情况

通过图4可以看出分组数是阶跃变化的，这是由于算法为了加快搜索最佳分组数，分组数是采用逐次加倍的方式来变换的，这也就导致了图6中算法标签识别率的阶跃性变化。

图5表示随着标签数的增加，总的查询时间是增加的，但是增加的速度并不快，甚至比标签自身增加的速率还要低，这也正解释了图6中大部分情况下（总标签数远低于天线数时除外）算法的标签识别率都大于1。

本算法和传统随机性 DFSA防碰撞算法以及BTS算法效率的比较如图7所示。

图5M=4时总查询次数S(n)随标签数量n的变化情况

图6M=4时算法标签识别率E(n)随标签数量n的变化情况

图7 BSDBG算法与DFSA和BTS算法标签识别率比较

由图7可见，本文所提出的BSDBG算法效率远高于传统的随机性算法DFSA和确定性算法BTS的算法效率。在天线数 4M= 时，BSDBG算法效率的平均值和最大值为

下面调整天线数M，使其从2逐渐变到32，标签数n仍然为1～512，算法平均效率随天线数M变化情况如图8和表1所示。

图8 算法平均标签识别率随天线数量M的变化情况

表1 算法平均效率随天线数量M的变化情况

由表1和图8可见，随着天线数量的增加，算法平均效率基本上是按线性增加的，但增加的速率没有天线数量增加的速率大。

当某个分组的标签个数多于M，使得ICA算法无法将多个信源分开时，算法会自动增加SG使其加倍，然后重新进行分组。

下面分析标签数n及天线数M对动态分组准确度的影响。

一个组内具有多于M个标签的概率为

当标签数n较大时Cn

i的计算比较费时，并且精度难以保证，可以采用递归方法来实现。

设：

那么：

或者：

下面分析povernM随n和M变化的规律。设标签数n仍然为1～512，povernM随标签数n变化的规律如图9（天线数M= 4 ）和图10（天线数M= 8 ）所示。

图9M=4时，组内多于M个标签的概率随标签数量变化的情况

由图9和图10可见，由于采用动态分组，标签个数的增加并没有导致一个组内具有多于M个标签的概率增加。并且天线个数 4M= 时，99.5%以上的分组具有少于M个标签，能够被 ICA算法正确分离。天线个数 8M= 时，99.94%以上的分组具有少于M个标签，能够被ICA算法正确分离。

图10M=8时，组内多于M个标签的概率随标签数量变化的情况

5 结束语

利用现代信号处理技术，特别是多天线技术来实现多标签防碰撞是 RFID防碰撞算法新的发展趋势，也是突破传统算法性能不高的有效途径。本文分析了多天线UHF RFID系统的数学模型，通过对该模型的分析，得出多天线UHF RFID系统多标签混合数据完全符合独立分量分析（ICA）算法的约束条件。为将源信号正确地分离出来，ICA算法要求观测信号的数目应大于或等于源信号的数目。为满足这一要求，本文利用位隙算法对标签进行分组，使每组内的标签数小于阅读器天线数，然后在组内再使用ICA算法进行标签数据分离。据此，提出一种新的位隙动态分组盲分离多标签防碰撞算法（BSDBG算法）。本文从理论上分析和实验上验证了这种算法的标签识别率完全可以超过1，远远超过了传统TDMA类型的防碰撞算法的标签识别率。

[1] FINKENZELLER K. RFID Handbook: Fundamentals and Applications in Contactless Smart Cards and Identification[M]. Chichester:Wiley, 2003.

[2] LIANG B, HU A Q, QIN Z Y. Trends and brief comments on anti-collision techniques in radio frequency identification systems[A].Proceedings of the 6th Int Conf on ITS Telecommunications[C].Chengdu, China, 2006.241-245.

[3] 余松森，詹宜巨，彭卫东. 基于返回式索引的二进制树形搜索反碰撞算法及其实现[J]. 计算机工程与应用, 2004, 40(16): 26-28.YU S S, ZHAN Y J, PENG W D. An anti-collision algorithm based on binary-tree searching of regressive index and its practice[J]. Computer Engineering and Applications, 2004, 40(16) : 26-28.

[4] AAPO H, ERKKI O. Independent component analysis: algorithms and applications[J]. Neural Networks, 2000, 13(4-5): 411-430.

[5] YUAN S, PETER J H, MARLIN H M. Application of ICA in collision resolution for passive RFID communication[A]. Proceedings of the World Congress on Engineering and Computer Science[C]. San Francisco, USA, 2009. 1292-1297.

[6] EPCGLOBAL, EPCTM. Radio Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860MHz～960MHz Version 1.0.9[S]. 2005.

[7] ISO/IEC18000-6. Radio Frequency Identification for Item Management-part 6: Parameters for Air Interface Communications at 860MHz～960MHz[S]. 2010.

[8] 马建仓, 牛奕龙, 陈海洋. 盲信号处理[M]. 北京: 国防工业出版社,2006.MA J C, NIU Y L, CHEN H Y. Blind Signal Processing[M]. Beijing:National Defence Industry Press, 2006.

[9] KIM C S, PARK K L, KIM H C,et al. An efficient stochastic anti-collision algorithm using bit-slot mechanism[A]. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications[C]. Las Vegas, USA, 2004. 652-656.