一种新型的有源标签防碰撞算法

黄 茂， 张有光

（北京航空航天大学，北京 100191）

0 引言

射频识别（RFID）是一种非接触性自动识别技术，其中有源系统具有读写距离远、可靠性高、数据量大、发射功率低、标签功能更加复杂等特点。与无源 RFID一样，标签防碰撞也是有源系统中需要研究和解决的问题，一方面，有源场景运用比无源场景要复杂，另一方面，由于有源标签带有电池，有源标签再功能比无源标签更强大，这也为设计效率更高的算法提供了可能。

目前，有源标签防碰撞的国际标准 ISO/IEC 18000-7[1]只给出了一个基于帧时隙 ALOHA的最基本的算法，在算法效率上是相当低的。有源标签防碰撞算法都是基于随机竞争机制[2]，算法较为简单，但是容易产生标签饿死现象。DCMA[3]引进了控制信道去解决碰撞，读写器需要在两个信道中进行切换同时，但采用多个信道也增加了硬件开支。在文献[4]中，提出一种基于载波侦听的防碰撞方法，被用来检测在传送数据包之前是否已经有包在传输，并采用一种识别与通信分离机制，这样减少碰撞的概率，但是文章并没有对具体的识别期与收集期的算法进行详细定义。文献[5]提出了一种跟RSSI估计标签数然后来动态控制标签接入概率的方法，在这种算法下清点速率改善很大，但是文章只提出信号强度估计标签数，在实际情况中很难做到精确估计。文献[6]提出一种动态控制标签接入概率并进行多阶段竞争的机制，通过多次竞争提高包被识别的概率，但是这种方法只适用于用标签数较少的时候，文献[7]和文献[8]提出的算法都是基于二进制树搜索，对硬件资源要求高。这里将空闲时隙和碰撞时隙充分的利用起来，提出主从读写器包拯救机制和空闲时隙利用机制。

1 一种新颖的有源标签防碰撞算法

1.1 新协议基本思想

提出的协议将标签识别过程划分为4个阶段，唤醒期，接入期，收集期和会话期，每个阶段系统工作内容如图1所示。

唤醒期，读写器向处于休眠的标签发送一定持续时间的唤醒信号使得标签进入工作状态。标签收到来自读写器的唤醒信号后，进入接收状态并响应读写器命令。

接入期，标签产生16位的随机码作为唯一标识与读写器通信，读写器执行一种aloha与二进制搜索结合算法完成多标签接入。在接入期中有若干帧，只有当全部标签识别完成后才进入收集期，每一帧又有若干逻辑时隙，在当前帧接入的标签随机选择一个时隙，若逻辑时隙成功识别，则读写器发送确认信息(ack)告知标签识别成功，若逻辑时隙空闲则进入下一个逻辑时隙，若逻辑时隙碰撞，则当即让碰撞的多个标签进行二进制搜索(在二进制时隙中进行)，在二进制搜索中成功识别的标签，读写器也回对其发送ack，二进制搜索结束后进入下一个逻辑时隙。

收集期，读写器逐时隙完成对已接入标签信息的收集。标签在收到读写器的收集指令后，按照在接入期获得的序列号，在各自时隙内回复读写器需要的信息，并接收读写器确认命令。

会话期，读写器根据标签身份信息逐个与需要通信的标签完成信息交互。

由于不同的场景和需求唤醒期和会话期的长短会不同，所以在对协议效率评估的过程中，一般只考虑接入期和收集期，所以归一化吞吐量的计算从接入期开始收集期结束。在本协议中，有如下主要思想：

1）接入与收集分离，将标签的识别与数据通信分离开来，避免了较长数据包多次通信浪费掉的时间。

2）Q值调整标签接入概率，并不是所有未识别标签都会在当前帧中接入，而是在[0,2Q-1]之间任意选择，随机值为0才在当前帧中接入，而Q值是有一个初始值，并且动态调整的。

3）Aloha与二进制搜索结合，在逻辑时隙选择上采用 Aloha，在碰撞后的小数量识别中采用二进制搜索。

4）帧动态结束，根据空闲逻辑时隙与已识别标签数作为帧动态结束的评判依据。

1.2 主从读写器包拯救机制

这种机制利用从读写器，在主读写器中发生了碰撞了的包会在这里被挽救，做到每碰撞一次都能挽救一个包。

当若干个标签选择同一个时隙的时候，通常会发生碰撞，并且这几个包就会退避，在后面时隙中再参与竞争，可以利用这样的机制，即使是碰撞了也能利用主从读写器从碰撞的包中读一个出来，这样用到了2个读写器，一个主读写器，一个从读写器，一般情况下主读写器进行工作，从读写器是在住读写器发送碰撞时才发生工作，这里认为标签是有载波侦听能力的，他能确切感知到信道中发生了碰撞，碰撞的标签随即进行包拯救，在从读写器的时隙上按照一定的机制进行竞争，标签都以 p=1/3的概率发送 RN16，这样从读写器就有可能在每次碰撞后都从碰撞的包中成功的识别出一个包，从读写器与主读写器有半个时隙的间隔，这样避免两个读写器之间的干扰。

1.3 空闲时隙利用机制

在识别期，每一个包被识别后，读写会当即回复一个 Ack，其中包含了标签在收集期的序号，而在空闲逻辑时隙，读写器则不作任何的工作，直到该时隙定时器到时，进入下一时隙，这样浪费了很多时间，这里的机制是读写器中拥有一个 Ack队列，不再是标签识别后当即发送，而是在遇到空闲时隙时，读写器在空闲时隙间隔内发送出Ack队列中最前面的一个，在一帧中所有逻辑时隙结束后再将Ack队列中未发送完的包发送出去。

1.4 协议算法流程

为了方便对协议性能进行对比，算法流程着重在接入期和收集期，在接入期中标签在回复读写器时是以 RN16作为唯一标识的，接入期会有若干个帧，每一帧有N个逻辑时隙，而每一个逻辑时隙中发生碰撞时，就会进行二进制搜索，这样就可能有k个二进制时隙，在识别完全后才在收集期进行标签具体信息的通信。

读写器控制一定数量的标签逐帧参与接入，在帧内的每一逻辑时隙中，标签以二进制树算法接入。读写器设定一个固定的帧长N，并将该帧分成N个逻辑时隙。参与当前帧的标签在该帧的N个逻辑时隙中任意选择一个时隙等候接入。读写器发送命令起始和结束一个逻辑时隙，并逐时隙完成整个帧的接入。标签收到各自的时隙起始命令后，在各自的逻辑时隙内以二进制树算法接入。

1)读写器发送帧起始命令，该命令中包含参数Q和帧长数N。标签收到Q值后，在[0,2Q-1]之间任选一个整数。选择 0的标签参与当前帧的接入，非0的标签等待下一次帧起始命令。选择0的标签在[0，N-1]之间选择一个逻辑时隙数，如图 2所示。

图2 帧起始命令示意

2)读写器发送命令起始一个逻辑时隙，该命令包含逻辑时隙序号信息。标签收到命令后，向读写器发送 RN16随机码，若逻辑时隙碰撞（如s2,s5），不进行二进制搜索，而是进行从读写器包拯救，逻辑时隙成功识别（如s3,s7），不发送Ack，但别识别包进入 Ack队列，逻辑时隙空闲（如s4,s8），则在空闲内发送 ack队列中的 Ack包。在此过程中，若空闲逻辑时隙大于Nmin，或者识别标签大于Nmax，则该帧提前结束并调整Q值，进入下一帧。任何一个标签在成功识别后，都会得到一个值作为该标签在收集期中的序列号m，如图3所示。

图3 接入期逻辑时隙

3)在N个逻辑时隙结束后，主读写器发送二进制搜索命令分别对之前的碰撞包进行二进制搜索，这里被从读写器拯救的包不再进行该环节，最后将Ack队列中未发送的包发送出去，并进入下一帧，如图4所示。

4)二进制树算法：读写器发送逻辑时隙起始命令，标签收到该命令后将各自内部计数器置为 0，并启动随机数发生器。所有生成随机数为 1的标签使计数器加 1；所有生成随机数为 0的标签，计数器值保持不变（计数器值为 0）。计数器值为 0的标签立即回复标签信息。

若读写器检测到碰撞或错误，发送接收错误响应命令 FAIL。标签收到FAIL命令后，若其计数器不等于 0，其计数器值加 1；若其计数器为 0，启动随机数发生器，生成随机数为 1的标签将计数器值加 1，生成随机数为 0的标签保持计数器为 0，并再次发送。

若读写器检测到标签发送成功，读写器发送SUCCESS命令。标签收到 SUCCESS命令后，标签计数器减1。

若计数器值为 0的标签启动随机数发生器后，生成随机数均为 1，则没有发送。读写器检测到无数据传输时，发送 SUCCESS命令。检测无数据传输的方法是阅读在接收状态等待一个给定的时间门限，而非一个分组长度。所有标签计数器减 1，之后计数器为0的标签进行发送。

读写器在一次成功接收后发送SUCCESS，若在给定时间门限内未收标签回复，发送新的逻辑时隙起始命令，结束当前逻辑时隙并开始新的逻辑时隙。

5)重复 1)～4)的流程，直达所有标签被识别，这个过程中Q调会进行动态调整，接入过程中帧长数可设置为N=8。Q调整门限值可设置为 1，Nmin=3,Nmax=16.当读写器估计在一帧空闲逻辑时隙大于 3，结束该帧，并将Q值减少 1。当读写器估计在一帧中识别出的标签数数目大于 16时，结束该帧，并将Q值增加1。Q初始值可设为 1。Q范围[0,15]。

6)在接入期结束后，进入收集期，读写器会发送命令，这其中包含了收集期时隙间隔t，标签能计算出自己的应该何时发送标签信息(m-1)t,所有标签完成与读写器通信，收集期结束。

2 仿真与结果

由于成帧二进制树形分解算法通过 Q值控制接入的标签数，通过帧时隙数对标签进行散列，进而减少发生碰撞的标签个数，且可以根据标签碰撞的情况，对 Q值和帧时隙数 N值进行动态调整，同时采取了空闲时隙利用机制和主从读写器包拯救机制，将碰撞时隙和空闲时隙充分利用起来。由图 5可以看到，文中标准采用的防碰撞算法随着标签数的增加逐渐上升，归一化吞吐量最高可达到 0.40左右。相比而言，ISO/IEC 18000-7标签数很少的情况下，归一化吞吐量较高,但标签数的增加，吞吐量逐渐减低，最终分别稳定在0.32左右，与文中协议存在较大差距，在大标签数量的情况下，文中协议的性能较 ISO/IEC 18000-7有30%的提高。

3 结语

文中提出的一种新型的有源标签防碰撞算法，提出了主从读写器包拯救机制和空闲时隙利用机制，在有源标签防碰撞过程中，系统能够敏感的调整标签接入概率和帧长度，并且充分利用了无效时隙，提高了防碰撞效率。在以前的研究场景中，标签数较少，在标签数多的情况下防碰撞效率不高，文中研究主要针对标签数大于100的情况，提高了系统大标签数情况下的效率，在密集标签场景下，这种算法有很好的使用价值。在动态控制标签竞争概率上可以进行进一步研究。

[1] International Organization for Standardization.ISO/IEC TR 24730-2009,Information technology --Radio frequency identification for item management -- Part 7: Parameters for active air interface communications at 433 MHz[S].USA:[s.n.],2009

[2] YU H Y, LI O, ZHANG X Y. A Wireless Sensor Networks Theory Implementation[C]//Technique and Implementation Conferrence of Beijing:National Defense Industry.BeiJing:[s.n.],2008:88-92.

[3] LI N, DUAN X, WU Y. An Anti-Collision Algorithm for Active RFID[C]//International Conference on Wireless Communications,Networking and Mobile Computing 2006.Wuhan: IEEE，2006:22-24.

[4] YOON W J, CHUNG S H, KWON Y G. A Novel Tag Collection Algorithm using an Identified Slot Scan for Active RFID Systems[C]//IEEE.21st Annual IEEE International Symposium on Personal,Indoor and Mobile Radio Communications. Soul:IEEE,2010:26-30.

[5] XIE Z H,LAI S L.Design and Implementation of an Active RFID MAC Protocol[C]//IEEE.International Conference on wireless Communications.Networking and Mobile Computing 2007. Beijing:IEEE,2007:21-25.

[6] PALOMO-LÓPEZ A.CSMA Multi-Stage Anti-collision Protocol for Active RFID Systems[C]//Proceedings of the 4th International Workshop on RFID Technology.Madrid:[s.n.],2010:108-111.

[7] 滕培俊,熊伟,梁青,等.一种基于二进制树的 RFID防冲突算法研究[J].通信技术,2009,42(07):94-96.

[8] 禹士朋,范文兵,李建华,等.超高频 RFID系统中的放碰撞算法研究[J].通信技术，2010，43(09):118-120.