低冗余搜索树防碰撞算法范文

《通信学报》2014年第六期

1低冗余搜索树防碰撞算法

基于上文对搜索树防碰撞算法的分析，本算法从阅读器询问次数、询问命令长度、响应时隙数3方面进行改进，进一步减少询问过程中产生的冗余数据。1)“一问两答”询问方式：减少阅读器询问次数在目前的搜索树算法中，当阅读器检测到碰撞并发送询问命令后，只有ID序列最高碰撞位比特为‘0’的碰撞标签响应，ID序列最高碰撞位比特为‘1’的碰撞标签仍需阅读器再次发送一个询问命令进行询问，这里将其称为“一问一答”询问方式。对于所有碰撞标签，ID序列最高碰撞位之前的高位序列是相同的，只是最高碰撞位比特分别是‘0’或‘1’。本文利用这一特点提出一种“一问两答”询问方式。当阅读器检测到碰撞并发送一个询问命令后，ID序列最高碰撞位比特为‘0’的碰撞标签首先在第一个时隙响应，ID序列最高碰撞位比特为‘1’的碰撞标签等待一个时隙后在第二个时隙响应（如图1所示）。这种“一问两答”询问方式不仅可将碰撞标签分为2组，而且这2组标签的响应也仅需一次询问。2)计数器“触发开关”：减少询问命令中标识参数的长度在目前的搜索树算法中，标签接收到询问命令后，根据其ID序列与询问命令中的前缀是否匹配而确定是否响应，标签在响应时将ID序列最高碰撞位之后的低位部分发送给阅读器。因此，标签中的前缀匹配只充当了标签响应的“触发开关”，响应标签只需获得最高碰撞位。为减少询问命令中标识参数的长度，本算法将前缀与最高碰撞位压入“栈”中，只将最高碰撞位作为询问命令的标识参数，用计数器替代前缀匹配电路作为标签响应的“触发开关”。计数器初始值为0，计数器为0的标签才能响应询问命令，计数器不为0的标签处于等待状态。计数器也为标签跟踪前缀在“栈”中的深度，使响应标签的ID与出“栈”的前缀相匹配，从而使阅读器接收到标签发回的ID序列最高碰撞位之后的低位部分后，加上出“栈”的前缀可组成一个完整的ID序列。识别过程中，当阅读器检测到碰撞并发送询问命令后，碰撞标签分别在对应时隙响应。第一个时隙若发生碰撞，将前缀与最高碰撞位压入“栈”中，并发送计数器命令（counter），所有标签的计数器加1（除等待第二个时隙的标签）。第二个时隙若发生碰撞，将新的最高碰撞位作为询问命令的标识参数继续询问（询问命令为query）。第二个时隙若成功识别标签，抛出“栈”顶存放的前缀与最高碰撞位，将最高碰撞位作为询问命令的标识参数进行后退式询问。注意，后退式询问时发送的询问命令为re-query，所有标签的计数器先减1，计数器减1后为0的标签才能在对应时隙响应。因此，计数器的变化规律为：在第一个时隙，若有前缀入“栈”，计数器加1；在第二个时隙，若有前缀出“栈”，计数器减1。3)预测识别：减少标签响应时隙数阅读器对接收到的ID信号经曼彻斯特译码后可逐位识别出碰撞比特。若没有碰撞比特，则直接识别标签；若仅有一个碰撞比特，也可直接预测识别2个标签，可节省这2个标签响应所需的时隙。因为仅有一个碰撞比特时，只有2个标签发生碰撞，这2个标签的ID序列该位比特分别为‘0’和‘1’。文献[7]中的算法，先将ID序列的所有比特进行异或运算，将运算值加在ID序列的最高位组成一个新ID序列。当ID碰撞信号的译码结果只有2个碰撞比特时，阅读器可通过ID序列中所有未碰撞比特的异或值得到这2个碰撞比特。但这2个碰撞比特是由2个标签造成的，该算法中不会出现只有一个碰撞比特的情况。所以，只能在仅有2个碰撞比特的情况下直接识别2个标签。因此，该算法增加了复杂度，效果却与本文算法相同。4)标签屏蔽机制：避免对已被识别的标签再次进行识别在移动阅读器应用中，阅读器扫描完某一区域的标签后，会扫描另一个区域的标签。若这2个区域的重叠部分存在标签，它仍会扫描已被识别的标签（如图2所示）。为避免再次询问已被识别的标签，本文引入一种标签屏蔽机制：标签预留一个存储区，存储已识别该标签的阅读器的序列号（RID）。阅读器扫描标签时，首先发送以该阅读器RID为参数的初始化命令（initial）。收到该命令后，标签将命令中的RID与存储的RID进行比较。若相同，表明它已被该阅读器识别，则进入静默状态不再响应；若不同，表明它未被该阅读器识别，则用接收的RID替换原存储的RID，在初始化计数器后进行响应。通过该机制可屏蔽已被识别的标签，减少对已被识别的标签再次识别而带来的通信开销。为防止在识别过程中到达的标签不能被识别，本算法在一次扫描后进行二次扫描。因为搜索树算法的询问次数与标签数有关，识别过程中的新到标签又是少量的，所以会瞬间完成第二次扫描。二次扫描后，若没有标签响应，便停止扫描；若仍有标签响应，识别完标签后，再次扫描，直到不再有标签响应。

2低冗余搜索树算法具体实现

图3为低冗余搜索树算法的工作流程，该流程分为3个小流程：阅读器发送initial(RID)初始化命令，上次被成功识别的标签进入静默状态，未被识别的标签初始化计数器并响应；阅读器开始迭代询问过程，直到“栈”为空；当“栈”为空时，再次扫描，直到无标签响应，结束识别。算法主要步骤如下。1)阅读器发送initial(RID)初始化命令，若标签存储的RID与命令中的RID相同，则标签进入静默状态；若不相同，则标签将计数器初始化为0，并发送完整ID序列作为响应。2)阅读器检测是否有标签响应，若无标签响应，结束识别过程；若存在标签响应，则对接收到的ID信号经曼彻斯特译码后，确定最高碰撞位(χ)，发送以最高碰撞位为标识参数的query(χ)询问命令。3)标签检查计数器是否为0，计数器不为0的标签进入等待状态，不做出任何响应；计数器为0的标签检查ID序列的第χ位比特。若为比特‘0’，标签在第一个时隙发送ID序列的第χ位之后的低位部分；若为比特‘1’，等待第一个时隙结束后在第二个时隙发送ID序列的第χ位之后的低位部分。4)在第一个时隙，若接收到的ID序列中多于1个碰撞比特，则将ID序列最高碰撞位之前的高位部分作为前缀与最高碰撞位压入“栈”中，并发送counter命令；否则直接识别标签。在第二个时隙，若接收到的ID序列中多于一个碰撞比特，确定最高碰撞位(χ)后，继续发送query(χ)进行迭代询问(即转到步骤2))；否则直接识别标签。5)若在第二个时隙成功识别标签，阅读器检查“栈”是否为空。若不为空，抛出“栈”顶存放的前缀与最高碰撞位(χ)，发送re-query(χ)进行后退式询问，所有标签的计数器减1后进入步骤3)；若为空，进行二次扫描(即转到步骤1))，直到无标签响应，结束识别。

3算法性能分析

1)标签复杂度标签中计数器的最大值为构建的二叉树深度（即标签ID的长度），因此仅需lbk位的计数器（设标签ID长度为k）。标签中的计数器替代前缀匹配电路充当标签响应询问命令的“触发开关”，相比k位前缀匹配电路，降低了标签复杂度。2)阅读器的询问次数若有n个标签在阅读器的识别区域内，在返回式动态搜索树算法构建的二叉树中（如图4所示），叶子节点（图4中方形）的数量即为标签的个数n，非叶子节点（图4中圆形）的总数代表碰撞的次数C(n)，所有节点的数量则代表阅读器询问总数Q，且有如下公式本算法采用了“一问两答”的询问方式，遇到碰撞时，只需询问一次。因此，询问总数即为碰撞次数（非叶子节点）加第一次初始化询问，且本算法采用了预测识别，在只有一个碰撞比特的碰撞节点（图4中阴影圆形），不必再进行询问即可识别2个标签(图4中阴影方形)。因此，询问总数再减去只有一个碰撞比特的碰撞节点数。若只有一个碰撞比特的碰撞节点数为m(m≤floor(n/2)，floor为向下取整)，则本算法的询问总数为3)询问命令中标识参数的长度当前的算法采用前缀作为询问命令的标识参数，若标签的ID序列为k位，则询问命令中标识参数的平均长度为从式(4)和式(5)可看出L明显小于L，且随着k的增加，它们的差距也随之增大。4)通信开销为公平对比，不考虑在移动阅读器应用中，标签屏蔽机制带来的明显收益。假设除标识参数外询问命令的其他字段为sbit，标签响应时附加的前导码等信息为tbit。因标签在响应时只发送ID序列最高碰撞位之后的低位部分，所以每个响应标签平均发送的ID序列为Lbit(式(4))，则返回式动态搜索树算法识别n个标签所需的通信开销为比对式(6)和式(7)，可看出S小于S，且随n、k的增加，它们的差距也随之增大。因此本算法明显降低了识别标签所需的通信开销。

4算法仿真与分析

本文从询问次数、询问命令长度、吞吐率与通信开销4个方面，将LRST算法与RDBST算法[6]和FST算法[7]进行性能比较。为简单起见，仿真中不考虑控制、前后缀和校验冗余等带来的通信开销，而主要将询问命令中的标识参数与标签发送的ID序列作为识别标签所需的通信开销，并定义吞吐率为标签总数与识别标签所需的总时隙数之比。因识别过程与标签群的ID分布有关，分别对16位ID随机分布、连续分布2种情况进行仿真。从图5和图6可看出，标签群的ID无论是随机分布还是连续分布，LRST算法的询问次数都少于其他2种算法，且仅为FST算法的一半。这表明本算法提出的“一问两答”询问方式可使整个询问过程的询问次数减少一半。图7为前缀、最高碰撞位分别作为询问命令标识参数的情况下，标识参数长度的变化曲线。LRST算法采用计数器作为标签响应的“触发开关”，询问命令的标识参数为最高碰撞位。从图7可看出，当ID序列的长度翻倍时，询问命令的标识参数仅需增加一个比特；而其他2种算法采用前缀匹配电路作为标签响应的“触发开关”，则需将前缀作为询问命令的标识参数，当ID序列的长度翻倍时，询问命令的平均标识参数也随之翻倍。当ID序列为16bit时，LRST算法采用最高碰撞位作为询问命令的标识参数仅需4bit，而其他2种算法采用前缀作为标识参数平均需9bit。这表明采用最高碰撞位替代前缀作为询问命令的标识参数可大大减小询问命令的长度。从图8可看出，RDBST算法的吞吐率(u)接近50%，符合理论公式：u=n/(2n−1)。FST算法与LRST算法的吞吐率明显高于RDBST算法的吞吐率,由吞吐率定义可知，预测识别明显减少了时隙数。从图9可看出，RDBST算法的吞吐率仍为50%，LRST算法与FST算法的吞吐率接近1。这说明预测识别可利用标签群ID的分布特性，提高吞吐率。从图8和图9可看出，LRST算法与FST算法的吞吐率曲线基本重合。这表明2种预测识别在减少时隙数方面基本相同，因此，LRST算法中的简单预测识别可替代FST算法中的复杂预测识别。图10和图11为系统识别标签所需的通信开销，通信开销可反映时延与功耗[8,9]。从图10可看出LRST算法的通信开销明显低于其他2种算法。LRST算法的通信开销比RDBST算法降低了约42%，比FST算法降低了约38%。标签群的ID续分布时，LRST算法达到最优。从图11可看出，LRST算法的通信开销比RDBST算法降低了约69%，比FST算法降低了约39%。这表明标签群的ID无论是随机分布还是连续分布，LRST算法都明显降低了通信开销。由仿真可看出，当标签群的ID连续分布时，LRST算法表现出更好的优越性。在很多应用中，标签群的ID是连续分布的，例如仓库管理、生产线等。有些算法加入预处理机制[10]或者锁定发生碰撞的比特后再执行搜索树算法[11]，每次询问后将ID序列中未识别的部分组成一个新ID，以达到减少传输比特的目的。它只能在识别少量标签时，节省某些比特。在识别大量同类商品的标签时，节省的仍是ID序列高位部分的比特。因此，这种机制增加了标签复杂度，却得不到很好的效果。

5结束语

本文研究了RFID系统中的标签防碰撞算法，对搜索树算法及其改进算法进行了分析，并在此基础上提出了一种低冗余搜索树防碰撞算法。该算法能大幅度减少阅读器的询问次数和询问命令中标识参数的长度，从而降低了系统的通信开销，减小了时延，降低了功耗。当接收到的ID序列中只有一个碰撞比特时，可直接识别2个标签，进一步减少了时隙总数，提高了吞吐率。仿真结果表明，标签群的ID无论随机分布还是连续分布，本算法都提高了吞吐率，且明显降低了通信开销。因此，本算法能够迅速有效地识别标签。

作者：黄琼凌江涛张敏阳小龙单位：重庆邮电大学移动通信技术重点实验室北京科技大学先进网络技术与新业务研究所