基于映射分组的改进型碰撞跟踪树算法

刘本超，杨恒新，张 昀

(南京邮电大学 电子科学与工程学院，江苏 南京 210003)

0 引 言

射频识别(RFID)是一种以无线电技术为基础，以对目标物体的自动识别为目的非接触式识别技术，主要由阅读器、标签和中央信息处理系统组成[1]。识别距离较远的超高频射频识别是利用空间电磁反向散射耦合实现无线双向数据传输，从而实现对目标的自动识别[2]。标签与阅读器进行通信时主要有两种形式的碰撞，分别是标签碰撞和阅读器碰撞。阅读器碰撞可通过阅读器间建立的工作协调机制解决冲突问题[3]。由于受成本制约，标签的功能单一、功率低，标签碰撞问题成为制约RFID系统的关键因素。

为解决标签碰撞问题，研究人员提出了许多有效的防碰撞算法。目前，标签防碰撞算法大体可分为两类：确定性防碰撞算法和随机性防碰撞算法。

随机性算法主要是基于ALOHA的算法，这种算法设备简单，花费低，识别速度快。基于ALOHA的算法，包括纯ALOHA算法、时隙ALOHA算法、帧时隙ALOHA算法、动态帧时隙ALOHA算法以及基于ALOHA的各种改进算法[4-5]。但由于ALOHA类算法标签随机选择时隙，因而造成识别的不确定性，即可能出现大量标签“扎堆”碰撞或者出现大量空闲时隙的情况，即“标签饥饿”问题[6]。

确定性算法主要是基于树的算法，它采用了分离的思想，将碰撞的标签连续分为不同的子集，直至成功识别所有标签，所以它避免了“标签饥饿”问题，识别效率高[7]。最基本的基于树的防碰撞算法是二进制防碰撞算法，但其吞吐率较低。查询树(QT)算法[8]是一种无记忆防碰撞算法，极大地促进了树型防碰撞算法的发展。人们在查询树算法的基础上又提出了许多改进算法，例如基于前缀检测的算法[9]，提高了RFID系统工作效率。碰撞跟踪树(collision tracking tree，CTT)[10]算法的核心思想是在查询树算法的基础上通过曼彻斯特编码(Manchester encoding)方式来检测具体的碰撞位，通过只查询非碰撞位来提高查询速度。其改进算法[11]在检测碰撞位的基础上引入多位查询前缀，降低了查询深度。

文中在碰撞跟踪树算法的基础上，通过曼彻斯特编码锁定碰撞位，将碰撞位每3比特为一组进行分组，并进行重新编码，引入映射码。标签端发送第i组映射码，阅读器根据收到的映射码有效地识别标签ID，设置合理的查询前缀。

1 碰撞跟踪树算法

设阅读器端有一堆栈Q，阅读器发送查询指令，查询范围内所有标签；标签返回自身唯一ID信息，阅读器根据曼彻斯特编码的特点得到碰撞信息即具体碰撞位。设标签ID长度为k，首位碰撞位为第i位，阅读器首先将第i位之前的信息r1…ri-1添加0和1组成r1…ri-10和r1…ri-11前缀压入堆栈，阅读器再次发送查询命令，所有匹配查询序列的标签将返回长度为k-r的标签剩余ID。阅读器收到信息后再次检测碰撞位，将碰撞位之前的ID添加0和1再次作为查询前缀压入堆栈，直到没有标签未被识别。当堆栈为空时，阅读器可判定所有标签已被成功识别，结束查询。因为CTT算法是在碰撞位基础上进行的查询，所以避免了空时隙，极大地提高了识别速率。

2 基于映射分组的改进型碰撞跟踪树算法

CTT算法虽然能去除空闲时隙，但由于每次查询仍然采用二叉树的形式，因此查询次数仍然很多。文献[12]提出了一种基于分组码的改进型防碰撞算法(IABC算法)，该算法令标签ID每3比特为一组，以0和1的分布情况进行分类，得到四种类型的分组码。由于分组码01和001分别对应三种标签识别码，因此需要二次发送确定准确的标签识别码。因此，提出一种基于映射分组的改进型碰撞跟踪树算法(improved collision tracking tree algorithm based on mapping grouping，ICTTMG)。该算法可以建立标签识别码与映射码的一一对应关系，因此可以准确地判定所需要的查询前缀，避免了二次发送，提高了识别速率，又降低了系统通信量。

2.1 算法描述

ICTTMG算法主要分为两个阶段：锁定碰撞位和映射识别。

(1)锁定碰撞位。

算法首先利用曼彻斯特编码锁定碰撞位。曼彻斯特编码采用电平的跳变表示信息，从高电平跳变到低电平表示“1”，从低电平跳变到高电平表示“0”，采用该编码方案的优点是当有碰撞发生时，阅读器接收到的信号全为高电平，可确定此时发生碰撞。

(2)映射识别。

首先将标签碰撞ID按每3比特为一组分为k组，因为CTT算法可得到具体碰撞位数，所以我们可确定最后一组的具体位数，不足3比特的按照最高位添加0处理。阅读器发送查询指令，标签返回第i组ID的映射码，映射规则如表1所示。

表1 映射码

为了减少通信量同时能方便地识别映射码，阅读器端设有5个堆栈S1、S2、S3、S4、S5。阅读器根据第i组映射码位数的不同压入不同的查询堆栈：映射码位数为1、2、3、4位的响应信息分别压入堆栈S1、S2、S3、S4。例如：ID为001和101对应的映射码分别为01和10，将其存入堆栈S2，则根据曼彻斯特编码，得到信息xx，x表示无法确定0和1，那么可以很容易地确定出标签返回的信息是10和01，即存在ID为001和101的标签，并将10和01前缀压入堆栈S5，同时记录分组编号i。每个标签都附带一个计数器和存储器RC，用来记录映射码信息。

首先将标签状态分为激活态、等待态和睡眠态。激活态：标签处于激活态时，能够接收阅读器发送查询指令并与之通信。等待态：标签处于等待态时，暂时无法与阅读器通信，直到被激活。睡眠态：标签处于睡眠态，表示标签已经被成功识别，并且不再响应阅读器。

为了更好地描述该算法，引入下列三条指令：

(1)Query_all：阅读器发送该命令，查询范围内所有标签，标签被激活并发送自身ID；

(2)Lock(TID)：标签收到该命令后锁定碰撞位，转换成映射码并存储到寄存器RC中；

(3)Query(prefix，i)：阅读器发送该命令，prefix为查询前缀序列，i表示分组编号。处于激活态的标签需将自己临时ID号中第i组映射码与prefix进行比较，若匹配，响应阅读器；反之，标签转为等待态。

2.2 算法具体步骤

以下为ICTTMG算法的具体执行过程：

(1)初始化堆栈，阅读器发送Query_all指令，所有标签响应并返回ID信息。

(2)阅读器记录能正确识别的比特位，同时记录发生碰撞的位置。假设有四个标签，其ID分别为：11010，10101，10001，11000，那么阅读器收到的信息为：1xxxx，x表示发生碰撞。

(3)阅读器发送Lock(TID)命令，其中碰撞位用1表示，非碰撞位用0表示，标签将收到的信息与自己的ID进行匹配，得到碰撞位信息，根据映射关系表，每3比特为一组，进行映射操作，将映射码存入寄存器RC中，初始化标签计数器i为1。

(4)阅读器发送Query(prefix,i)指令，标签被激活并响应阅读器，标签发送第i组映射码加上剩余ID信息给阅读器，同时标签计数器i值加1。

(5)阅读器将不同位数的响应信息分别压入堆栈S1、S2、S3、S4，进行译码后得到查询前缀，并将前缀压入堆栈S5中，同时记录分组编号i。

(6)标签接收到前缀prefix和分组编号i，计数器值等于i的标签将前缀与自身映射码做比对，具有相同前缀的标签激活并响应阅读器。若阅读器未检测到碰撞，则直接识别该标签，读取数据并进行灭活操作，堆栈S5弹出下一组前缀，返回步骤4；若检测到碰撞，则令i=i+1，跳转至步骤4。

(7)判断堆栈S5是否为空或者全部标签被识别，结束识别过程。

2.3 算法实例

假设有8个待识别标签分别为：A(10110100)、B(10010110)、C(11010001)、D(11000100)、E(11000000)、F(10000110)、G(10000101)、H(11010110)。阅读器根据标签返回的信息，确定碰撞位，可得1xxx0xxx，即有6个碰撞位，标签根据阅读器发送的碰撞跟踪信息，将自己的碰撞位取出，根据上面的编码规则进行编码，如表2所示。

算法具体查询过程如表3所示。

表2 标签ID映射

表3 ICTTMG算法查询过程

3 算法仿真验证

3.1 时间复杂度

由文献[13]可知，对于八叉树算法识别n个标签所需要的总时隙数为：

n8-L(1-8-L)n-1]

(1)

其中，碰撞时隙数、空闲时隙数和识别效率分别如下：

(2)

(3)

(4)

对于提出的算法，时间复杂度主要由标签数量和非碰撞位数决定。设标签数量为n，非碰撞位数为m(取50)，则总时隙数TICTTMG和吞吐率E经MATLAB[14]仿真验证的结果如图1和图2所示。

图1 五种算法总时隙数比较

图2 五种算法吞吐率比较

由图1可以看出，提出的算法需要的时隙数最少，识别1 000个标签只需要1 416个时隙，比基本CTT算法少用了30%的时隙，比IABC算法也少用了约5%的时隙。由图2可以看出，提出的算法具有最高的吞吐率，比基本CTT算法提高了约22%，明显高于其他算法[15-16]。

3.2 通信复杂度

文中算法的通信复杂度涉及两个阶段。

(1)锁定碰撞位。

阅读器需要发送锁定命令字Lock，标签返回ID信息，ID长度为k，因此总通信量为:

Tra1=2k

(5)

(2)前缀查询。

设标签非碰撞位为m，则碰撞ID长度为k-m，根据表1的编码方案，标签每3比特信息经再编码后平均长度为2.5比特，比原来减少0.5比特，因此降低了系统通信复杂度。阅读器发送查询前缀和分组编号，而标签发送一组映射码加临时ID的剩余位比特信息，其数据位长度取决于标签在八叉树第几层成功识别。假设标签在L层被识别的概率为Ps(L)，则

(6)

标签发送的比特位信息平均期望值为：

(7)

因此，第二阶段标签和阅读器总通信量为：

Tra2=2.5*TICTTMG+CT*TICTTMG

(8)

总通信量为：

Tra=Tra1+Tra2

(9)

根据EPC C1G2协议[17]的规定，标签ID长度k取96位，其中唯一标识序列号长度为36位，非碰撞位数m取值50，据此计算通信量。对各种算法的通信量进行仿真验证，如图3所示。

图3 五种算法通信量比较

因为提出的改进算法使用了合理的映射编码方案，每3比特ID经编码后平均长度变为2.5比特，而且每次查询平均只需查询2.5比特前缀，极大降低了系统的通信量。MATLAB仿真表明，该算法具有最低的通信复杂度，比CTT算法减少了约68%的通信量，随着非碰撞位数m的增大，算法通信复杂度性能进一步提升。

4 结束语

在传统CTT算法的基础上，提出的ICTTMG算法改变了传统CTT算法每次只能识别一位比特的缺点，该算法结合映射识别码，减少了整个识别过程中的查询次数，利用一个查询响应周期对识别码中碰撞位进行锁定，同时平均每次只需发送2.5比特查询前缀，优化了阅读器命令。仿真结果表明，算法在时间复杂度和通信复杂度方面都有明显改善。