基于映射序列码的自适应查询树防碰撞算法

薛伟莲，陈 杰，李雪娇，沈 阳

（辽宁师范大学政府管理学院，辽宁大连 116029）

0 引言

射频识别（Radio Frequency Identification，RFID）是一种利用射频信号通过空间电磁耦合实现无接触式自动识别技术。识别系统由3 部分组成：应用系统、阅读器和电子标签，其中应用系统主要包括RFID 中间件和应用系统软件，如图1 所示。其工作原理是阅读器通过天线发射一特定频率的射频信号，当阅读器进入有效识别区时就会产生感应电流，从而获得能量并被激活，再将自身编码信息通过天线发出，此时阅读器便依序接收解读信息，送给应用程序作相应处理。与传统的识别技术相比，RFID 具有非接触式读写、环境适应强、数据容量大、可重复使用、安全性高等优点，被广泛应用于物流盘点、仓库管理、跟踪定位等领域。

Fig.1 Radio frequency identification system图1 无线射频识别系统

目前，RFID 防碰撞算法主要分为两大类：一是基于ALOHA 的随机性算法，主要包括时隙ALOHA（SA）、帧时隙ALOHA（FSA）、动态帧时隙ALOHA（DFSA）等；二是基于树的确定性算法，主要包括基本二进制搜索树（BS）算法、查询树（QT）算法、碰撞树（CT）算法、树分裂（TS）算法等。基于ALOHA 的随机性算法执行过程相对简单，易于实现，但存在标签“饿死”问题。基于树的确定性算法虽然能解决标签“饿死”问题，但存在识别周期长、标签能耗大的问题。

QT算法是一种无记忆算法，阅读器首先初始化查询前缀堆栈为0 和1，阅读器不断发出和更新查询前缀，如果只有一个标签响应则识别该标签；如果多个标签同时响应，即发生标签碰撞，则在该查询前缀后加上0 和1 生成新的查询前缀并入栈；不断循环以上过程直到堆栈为空。QT算法能够识别所有标签但产生大量空闲时隙和碰撞时隙，导致识别效率过低。

为改善QT算法性能，有学者依据碰撞位的特点对四叉树进行改善并提出了自适应四叉修剪查询树（A4PQT）算法。A4PQT算法原理如下：假如阅读器接收到的碰撞译码为

p

p

…

p p

…

p

，

p

为首位碰撞位，当

p

不为碰撞位时产生两条新的查询前缀，这就避免了两个空闲时隙；当

p

也为碰撞位时，则产生4 条新的查询前缀，这就有可能包括空闲时隙。因此，A4PQT算法能够有效减少空闲时隙，但不能避免空闲时隙。

为进一步提升查询树性能，文献［12］提出了一种基于分组机制的位仲裁查询树（GBAQT）算法。该算法根据标签信息特征进行分组，采用3 位仲裁位取代传统1 位仲裁位，将待识别标签分为两组（G=0 和G=1），阅读器根据各组标签特点和接收数据的碰撞位信息得到传输数据，能够避免一些空闲时隙。

A4PQT算法和GBAQT算法都只能达到减少空闲时隙的效果，而并不能完全消除空闲时隙。针对上述研究存在的问题，提出一种基于映射序列码的自适应查询树（Adaptive Query Tree Based on Mapping Sequence Code，MAQT）算法，MAQT算法只关注最高碰撞位为首的连续3个比特位，根据碰撞发生的位数选择不同方法确定精确的查询前缀，能够实现无空闲时隙，且减少碰撞时隙。

假设有7个标签A（000001）、B（000101）、C（011011）、D（011101）、E（010101）、F（111011）、G（100101），则QT算法、A4PQT算法及GBAQT算法查询树结构如图2 所示。

Fig.2 QT algorithm，A4PQT algorithm and GBAQT algorithm tree structure图2 QT算法、A4PQT算法及GBAQT算法树结构

1 算法描述

1.1 基本思想

假设在某次查询中，阅读器接收到的碰撞译码为

p

p

…

p p

p

…

p

，

p

为首位碰撞位，则会存在以下3种情况：（1）K=1。即

p

为碰撞位，但

p

与

p

都不是碰撞位，这时阅读器直接将

p

令为0 和1，生成两条新的查询前缀并压入堆栈。如阅读器收到碰撞译码为PRE+X0011X，则可直接生成PRE+00011 和PRE+10011 这两条新的查询前缀。（2）K=2。即

p

为碰撞位，但

p

与

p

中有一位是碰撞位，此时阅读器将Query（PRE，SEQ）指令发送给发生碰撞的标签，要求返回碰撞比特位组成的比特串对应的映射序列码，阅读器根据接收到的信息判断前缀组合。如两个标签A（10101010）和B（10100000）发生碰撞，阅读器接收到碰撞译码为1010X0X0，属于K=2 这种情况，此时阅读器发送Query（1010，101）指令，要求前缀为1010 的标签将D1和D3 比特位组成的比特串对应的映射序列码发送给阅读器，标签A 和B 分别发送1000 和0001，阅读器得到译码结果为X00X，可推断出两位碰撞位为11 和00，即可确定两条新的查询前缀10101010 和10100000。K=2 的映射关系如表1 所示。

Table 1 Mapping relationship表1 映射关系

（3）K=3。即

p

、

p

和

p

都是碰撞位，此时阅读器发送Query（PRE，111）指令，获取该时隙所有可能存在的碰撞前缀的组合。如标签A（10101110）和B（10100001）发生碰撞，阅读器接收到配置译码1010XXXX，属于K=3 这种情况，随即发送Query（1010，111）指令，要求前缀为1010 的标签将D1、D2 及D3 比特位组成的比特串对应的映射序列码发送给阅读器，标签A 和B 分别发送10000000 和00000001，阅读器得到译码结果为X000000X，可推断出3位碰撞位为111 和000，即可确定两条新的查询前缀1010111 和1010000。K=3 的映射关系如表2 所示。

1.2 算法相关指令

Request（ε）：请求指令，用于初始阶段的第一次查询工作，阅读器作用范围内的所有标签作出响应。

Request（PRE）：请求指令，PRE 为查询前缀，符合查询前缀的标签作出响应。

Query（PRE，SEQ）：映射识别指令，PRE为查询前缀，SEQ为0和1组成的序列，如标签A（110101）和标签B（110000）同时响应阅读器发生碰撞，阅读器收到碰撞译码110X0X，为确定准确查询前缀，发送Query（110，101）指令，标签A 和B 作出响应，标签A 将自己的D0 和D2 比特位组成的比特串（11）转化为对应的映射序列码（1000）并发送给阅读器，同理标签B 将00 对应的映射序列码0001 发送给阅读器，阅读器得到译码结果为X00X，即可推断出碰撞位为00 和11，没有01 和10，从而确定两条新的查询前缀，消除空闲时隙。以上是两位碰撞位的情况（K=2），当出现三位碰撞位（K=3）时，阅读器发送Query（PRE，111）指令获取碰撞位准确信息。

Table 2 Mapping relationship表2 映射关系

Push（PRE）：入栈指令，PRE 为查询前缀，发出此指令后，阅读器将此前缀压入堆栈。

Pop（PRE）：出栈指令，PRE 为当前栈顶前缀，发出此指令后，阅读器将此查询前缀弹出堆栈。

Read：读取指令，处于激活状态的唯一标签收到命令后将自身信息发送给阅读器。

Unselect：屏蔽指令，对已经进行读取操作的标签发送屏蔽指令，使其不再响应后续指令。

1.3 算法流程

MAQT算法流程如图3 所示。

Fig.3 MAQT algorithm flow图3 MAQT算法流程

Step1：初始化查询前缀堆栈，阅读器发送Request（ε）请求指令，阅读器作用范围内的所有标签作出响应。

Step2：符合当前查询指令的标签响应。

Step3：判断时隙状态，如果只有一个标签响应，则识别并屏蔽该标签，跳转到Step6；如果多个标签同时响应，则针对碰撞位的位数K 分以下2 种情况：①K=1 时，直接产生两条新的查询前缀，转到Step4；②K=2 或3 时，需要阅读器发送Query（PRE，SEQ）指令，响应的标签将碰撞比特位组成的比特串对应的映射序列码发送给阅读器，阅读器对接收到的映射序列码进行解码以确定新的查询前缀，转到Step4。

Step4：将新的查询前缀压入堆栈。

Step5：阅读器由栈顶至栈底的顺序依次将Request（PRE）指令发送给标签，并返回至Step2。

Step6：判断堆栈是否为空：若堆栈不为空，返回至Step5；若堆栈为空，说明所有标签都被识别，识别过程结束。

本文将举例说明MAQT算法识别标签具体步骤。假设待识别标签仍为上文举例的7个标签，分别为A（000001）、B（000101）、C（011011）、D（011101）、E（010101）、F（111011）、G（100101）。MAQT算法阅读器查询和标签响应情况如表3 所示，对应的查询树结构如图4 所示。

Table 3 Reader queries and tag responses表3 阅读器查询和标签响应情况

Fig.4 MAQT algorithm tree structure图4 MAQT算法树结构

2 算法性能分析

假设待识别标签个数为

m

，对于一棵完整的B 叉树，在第L 层的节点个数为8（设定根节点为第0 层）。由于每个标签的分配相对独立，则

k

个标签选择同一个节点的概率为：

由此可得某节点为空闲节点的概率为：

某节点为成功节点的概率为：

某节点为碰撞节点的概率为：

假设

q

为第L 层的第

i

个节点被查询到的概率；

β

为第L 层的第

i

个节点为碰撞节点的概率。则：

识别所有标签的总时隙数为：

结合式（5）可得：

同理可求得碰撞时隙为：

空闲时隙为：

本文是基于八叉树算法的改进，根据式（8）可知一棵完整八叉树的总时隙数为：

根据式（9）可知一棵完整八叉树的碰撞时隙数为：

根据式（10）可知一棵完整八叉树的空闲时隙数为：

如果碰撞位仅一位，即K=1，则树的结构为二叉树，此时碰撞节点的子节点总数为八叉树的1∕4，假设该碰撞节点有

N

个标签，则没有标签选择两个子节点中一个的概率为：

则在第L 层的碰撞节点执行K=1 的概率为：

根据以上信息可求得总时隙数：

由于MAQT算法能够完全避免空闲时隙，且以最高碰撞位为首的连续3个比特位发生2 位（K=2）或3 位（K=3）碰撞时，阅读器需要发送额外指令以获取碰撞位的准确信息。

根据式（10）可知，多余的空闲时隙数：

综上所述，MAQT算法的总时隙数为：

吞吐率就是识别效率，为待识别标签总数与总时隙的比值，有：

3 仿真及分析

利用MATLAB 平台对QT算法、A4PQT算法、GBAQT算法和MAQT算法进行仿真与比较。标签ID 均匀分布，长度固定为96bit，标签数量为100～1000 区间动态变化，取50 次仿真实验结果的平均值作为最终仿真结果。

图6 为MAQT算法、QT算法、A4PQT算法和GBAQT算法总时隙数的比较，可以看出MAQT算法在识别m个标签时所需的总时隙数明显小于其它3 种算法。当标签数量达到1 000 时，MAQT算法需要1 639个总时隙，比QT算法减少43.8%的总时隙数，比A4PQT算法减少21.5%的总时隙数，比GBAQT算法减少10.8%的总时隙数。MAQT算法根据最高碰撞位为首的连续3个比特位发生碰撞的位数动态选择产生前缀的方法，并通过映射序列码消除空闲时隙从而减少总时隙数。

图7 为MAQT算法、QT算法、A4PQT算法和GBAQT算法吞吐率比较。可以看出，MAQT算法吞吐率明显优于其它3 种算法，可维持在0.61 左右；QT算法的吞吐率维持在0.35 左右，在4 种算法中表现最差；A4PQT算法的吞吐率不超过0.49，GBAQT算法的吞吐率在0.48 左右。

Fig.6 Comparison of total number of slots图6 总时隙数比较

Fig.7 Throughput rate comparison图7 吞吐率比较

4 结语

本文提出了一种基于映射序列码的自适应查询树防碰撞算法（MAQT），根据最高碰撞位为首的连续3个比特位发生碰撞的位数动态选择产生前缀的方法。当以最高碰撞位为首的3个连续比特位中仅有一个碰撞位（K=1）时，直接产生两条查询前缀，采用二叉树方式搜索；当以最高碰撞位为首的3个连续比特位中有2个或3个碰撞位（K=2 或K=3）时，根据唯一的映射关系确定存在的查询前缀，从而消除多叉树的空闲时隙，减少了碰撞时隙。仿真结果表明，MAQT算法在总时隙数和吞吐率方面都有着较好的表现。当待识别标签的ID 过长时，查询树算法的深度会相应增加。基于随机数的查询树算法能够有效降低查询树深度，是未来的一个研究方向。