引入信息预处理的多状态二进制改进算法

周艳聪，何敏，顾军华，董永峰

1.河北工业大学电气工程学院，天津 300130

2.河北工业大学计算机科学与软件学院，天津 300401

3.天津商业大学信息工程学院，天津 300134

引入信息预处理的多状态二进制改进算法

周艳聪1，3，何敏2，顾军华2，董永峰2

1.河北工业大学电气工程学院，天津 300130

2.河北工业大学计算机科学与软件学院，天津 300401

3.天津商业大学信息工程学院，天津 300134

1 引言

RFID（Radio Frequency Identification，无线射频识别技术）是一种非接触数据自动采集技术，它以空间电磁波为传输媒介进行双向通信和自动识别，已成为目前发展最为迅速、潜力最大的新兴技术之一。RFID系统主要由阅读器和标签两部分组成。当标签进入阅读器天线电磁场后，阅读器通过无线方式实现对标签的数据采集。当多个标签进入阅读器的识读范围时，阅读器不能同时响应多个标签的通讯请求，这时也就产生了标签碰撞问题，从而导致无法进行有效、快速的识别。因此，标签防碰撞算法研究成为RFID的重要研究领域。

目前的RFID防碰撞算法主要分为概率性算法和确定性算法两大类。概率性算法操作简单，便于实际应用，但其随机性大，特性随着标签数量的扩大会急剧恶化。确定性算法电路实现比较复杂，算法识别率较高，识别速度快，识别准确率高[1]，因此很多学者对确定性算法进行了研究。典型的有基本二进制算法、BBT（Bit-by-Bit Tree）算法[2]、Q-Tree算法[3]、ABS（Adaptive Binary Splitting）算法[4]等；文献[5]提出一种EAA算法；文献[6]介绍的基本二进制算法实现简单，但是阅读器与标签间的数据传输量大，交互次数多，效率低；文献[7]提出了一种返回式二进制搜索算法，这种算法利用栈的思想减少了交互次数，在一定程度上降低了通讯量，但仍存在较大数据冗余；针对基本二进制算法中每次都会发送大量冗余信息的情况，文献[8]提出了一种根据部分已知ID动态查询ID的动态二进制算法，阅读器每次只发送从最高位到碰撞位的信息作为搜索前缀，即部分标签的相同前缀，标签发送碰撞位后的信息，从而减少通讯量。文献[9-14]等专门对二进制算法进行了研究和改进。文献[9]提出了一种改进的二进制算法，采用动态方式传输数据，简化了阅读器发送的指令和冲突检测过程；文献[10]对多状态二进制算法进行了改进，通过减少发令次数，进一步减少了交互次数和通讯量；文献[11]针对二进制搜索树所需搜索时隙多，识别效率低的缺点，对发生碰撞的比特位进行深度分解，并调整搜索状态，从而减少了搜索时隙数；文献[12]改进了基于退避思想的动态二进制搜索算法，采用FPGA进行算法实现，用硬件方式进一步提高算法效率；文献[13]提出了一种对碰撞位连续的标签进行识别的新算法，其仅对碰撞位连续情况作了探讨。以上研究均对二进制防碰撞算法进行了某方面的改进，但它们大多都同时传输了碰撞位和非碰撞位数据，虽然文献[10]也采用了预处理的方式，但阅读器与标签之间的通信量仍存在冗余。本文将对多状态二进制防碰撞算法进行进一步改进，通过对非碰撞位和无效数据的屏蔽来减少阅读器的接收数据，通过状态标志变化减少交互次数，从而大大降低整体通讯量，提高了标签识别效率。

2 几种典型二进制算法

在二进制算法研究中，比较典型的算法有基本二进制算法、返回式二进制算法、动态二进制算法、多状态二进制算法，以及基于这些基本典型算法的改进算法。其基本思想是将碰撞标签分成0和1两个子集，先查询子集0，无碰撞，则正确识别；若仍有碰撞，则把0子集继续分裂成00和01两个子集；依次类推，直到识别出子集0中全部标签，再按同样方法查询子集1。

2.1 基本二进制算法

基本二进制以标签序列号为识别基础.当检测到冲突时，通过将最高冲突位置0，完成标签组的划分。标签只对大于等于自身序列号的阅读器指令回应，阅读器根据得到的回传信息修改下一条指令，直到所有标签被正确识别。

具体实现步骤如下：

（1）阅读器发送全“1”指令，令所有标签回传数据。

（2）阅读器接收标签回传的信息，检测冲突位。

（3）有冲突时，把指令对应最高冲突位置0，以此为新的查询指令，依次排除序列号大于新指令的标签。

（4）无冲突时直接识别。识别后，对其进行去活操作，使其进入“无声”状态，对阅读器发送的查询命令不再进行响应。

（5）重复步骤（1），继续识别标签。

（6）多次检测后完成所有标签的识别。

2.2 返回式二进制算法

返回式二进制算法在整个的搜索流程上和基本二进制算法类似，只是加入了栈的思想，使识别完一个标签后无需返回根节点从头开始新标签的识别，而是从离已识别标签最近的识别命令开始，继续新标签识别，这样使交互次数大大减少。

2.3 动态二进制算法

动态二进制算法的基本思想：设标签有L位，在第X位发生碰撞（从左至右排列），阅读器发送参数（标签的前X位）给区域内标签，与标签前0～X-1位相符的标签发送剩余的X+1～L-1位信息。但是第一次问询时，读写器发送全1指令，处于读写器作用域的所有标签都应答，其余命令与基本二进制搜索算法相同。将动态二进制算法和返回式二进制算法结合，形成的动态返回式二进制算法，其在减少通讯量和交互次数上都有很好的改进。

2.4 多状态二进制算法

算法的主要思想是引入休眠计数的方法，阅读器只发送最高冲突位的位置信息。标签中设状态标志，值为0时该标签为未屏蔽状态，值大于0为屏蔽态，值为-1的去活态标签表示已被识别，不再响应阅读器发送的命令。阅读器检测到最高冲突位（假设为第X位）后，将发送命令Request（B，X），B是0或者1，处于未被屏蔽状态且第X位为0的标签将自身ID号的后X+1～L-1位回传给阅读器，其他标签屏蔽值增加1（不论原来是未屏蔽状态还是屏蔽状态）。阅读器从接收的数据中检测到新的最高冲突位，重复上述过程进行搜索，直到检测到无冲突标签，接着发送一次激活命令，激活屏蔽值为1的标签，将其转为未屏蔽态，并按返回式二进制树形搜索的方法修改B值返回搜索；重复，直到所有标签均被识别。

以4个8位二进制标签（10110010，10100011，10110011，11100011）为例，表1、表2、表3和表4分别展示了基本二进制、返回式二进制、返回式动态二进制和多状态二进制的标签识别过程。

表1 基本二进制识别过程

表2 返回式二进制识别过程

表3 返回式动态二进制识别过程

本文将主要对多状态二进制防碰撞算法进行研究，并针对普通多状态二进制算法通讯数据存在冗余的情况，提出了一种基于信息预处理的多状态二进制改进算法。该算法将引入信息预处理与阅读器部分接收机制，在识别过程只处理冲突位，并融合动态二进制的优点，使阅读器只接收并记录标签部分数据，状态标志根据不同指令变化，减少交互次数，从而降低通讯数据量。

3 加入信息预处理的多状态二进制改进算法

3.1 算法基本思想

本文算法的主要思想是在多状态二进制算法中引入信息预处理机制，同时对阅读器接收标签数据的过程进行改进，只接收相邻两个冲突位之间的有效信息并记录，尽量避免数据重复发送和接收；同时，通过对状态标志的有效控制减少命令个数，从而减少交互次数。由于实际应用中标签编码存在一定的规律，当大量标签并存时，往往部分位是一致的，即不存在冲突，而防碰撞算法只需要识别冲突位信息，故在标签识别前进行一次预处理，一次性检验出所有冲突位，然后只对冲突位信息进行后继的处理，这样势必大大减少通讯量。经过预处理后的标签根据状态标志对阅读器做不同应答。未屏蔽状态标签回传数据，只传递冲突位信息。阅读器接收时只要检测到有两位及其以上冲突位，则只接收命令中指定位到当前最高冲突位之间的数据，其余数据不接收。检测到有一位冲突时识别两个标签，无冲突时直接识别。有标签被识别后，各标签对应状态标志均作相应变化。

在改进算法中，采用曼彻斯特编码方式，用上升沿表示逻辑0，下降沿表示逻辑1，并且约定每个标签只能拥有唯一的编码，不得重复；所有标签在同一时刻传送数据，即做到标签同步。

3.2 算法流程

具体操作中，每个标签配备两个重要参数：状态标志stateflag和传送位标志startflag。stateflag表示标签被屏蔽情况，0为未屏蔽，大于0为被屏蔽，-1为去活态即标签被识别。startflag表示标签传送数据起始位，即标签从startflag位开始传送。当检测到两位碰撞位时，阅读器将不再对后面数据进行检测，标签传送从startflag开始的数据；标签只有一位碰撞时，两个碰撞的标签可以同时被识别[9]。

标签数据按从高到低，即从左至右的顺序进行传送，最低位即最右位记为0。

预处理过程：

（1）阅读器发送全“1”指令，令所有标签回传数据。

（2）阅读器接收数据，检测碰撞位。

（3）将碰撞位组织成新的标签，记新标签长度为M。

阅读器处理流程：

（1）用0初始化指令参数栈（指令request（0）将令所有标签回传所有数据）。令当前最高冲突位为M-1；阅读器发送Request(M-1)，等待标签回应。

（2）接收标签数据。

（3）若无冲突，识别标签；指令栈非空时指令参数出栈，得到上一个最高冲突位；转（6）。指令栈空则停止。

（4）如果只有一位冲突，同时识别两个标签；指令栈非空时指令参数出栈，得到上一个最高冲突位；转（6）。指令栈空则停止。

（5）如果多于一位冲突，最高冲突位入指令参数栈；记录当前新的最高冲突位及其以前的数据；转（6）。

（6）若仍有未被识别标签，则发送Request（二进制表示的最高冲突位）。

（7）接收当前最高冲突位以后的标签数据，转（3）。

标签：

（1）如果阅读器指令为Request（0），所有标签回传所有数据。

（2）如果阅读器指令为Request（二进制表示的最高冲突位）；处于未被屏蔽状态且对应冲突位为0的标签回传冲突位以后的数据，即从startflag开始传送数据；对应冲突位为1的标签做屏蔽设定，即屏蔽标志加1。

（3）若有标签被识别，被识别标签设为去活状态，不再参与响应，其他标签屏蔽标志减1。

整体算法流程图，如图1所示。

3.3 算法示例

随机选取4个8位标签：10110010，10100011，10110011，11100011。通过预处理，检测出碰撞位为0、4、6三位，将这三位组成一个新的标签进行后续的识别，这时标签新编号为010、001、011、101。将这四个3 bit的标签按照3.2节所述过程进行识别，此时，标签长度M为3，用0初始化指令参数栈，并初始化最高冲突位为2。所有标签的开始传送标志startflag（初始为2）减去1，表示下一次标签将从第1位开始传输数据。由于第2位肯定冲突，所以第一次阅读器发送指令Request（二进制表示的最高冲突位），为Request（2），这时第2位是0的标签响应，传送第1位及其之后的数据；经检测，发现仍存在多于1位的冲突，最高冲突位“2”入栈，当前最高冲突位更新为“1”，记录第1位以前的数据。已识别字串记录第2位的‘0’，并入栈；待识别字串记录第2位的‘1’，在阅读器下一次从此位开始搜索时，这一位的数据将不用再次发送，而是直接取出，减少了标签和阅读器之间的交互。第二次，阅读器发送指令Request（1），这时，第1位为0的只有001这个标签，因此这个标签被识别，对标签做去活处理，即将stateflag位置-1，其余标签的stateflag减1。第三次，阅读器将最高碰撞位（2）出栈，stateflag为0且第2位为0的标签响应并传递数据，阅读器检测到两个标签传递数据且只有一个碰撞位，由于这两个标签上一轮传递的数据已被保存在栈里，将数据出栈，和碰撞位做拼接（一个置0，一个置1），再加上标签本次检测传递过来的数据，这样可以同时识别两个标签。第四次，由于栈非空，指令参数栈出栈，为（0），阅读器发送Request（0），stateflag为0的所有标签传递数据，和待识别字串记录的首位“1”拼接，组成完整的标签被识别。详细识别过程见表5。

表4 多状态二进制识别过程

图1 改进二进制防碰撞算法流程图

表5 标签识别过程（预处理后）

同时，分别采用基本二进制、动态二进制、返回式二进制、文献[9]算法和文献[10]算法对这四个标签进行识别，其通讯量和交互次数与新算法的对比如表6所示。

表6 算例交互次数和通讯数据量对比表

新算法引入预处理机制后，识别四个标签的交互次数为5，和改进前相比没有提高。有效通讯量为52 bit，较文献[9]算法的83 bit有较大程度下降，较文献[10]算法的64 bit也有一定程度下降。文献[10]虽然都引入了预处理机制，但本文进一步降低了交互次数，因此整体有效通讯量进一步降低了。本案例标签长度较短，仅为8位，阅读器接收有效数据量没有明显优势，随着标签长度的增长，效果将更加显著（详细对比参见图2）。

4 算法仿真与分析

文献[10]算法简化了阅读器的指令，使其只发送碰撞位信息，这样可以减少阅读器发送的数据量。采用免激活指令，减少了交互次数。文献[9]算法虽然阅读器接收的数据量减少了，但是阅读器本身接收的数据包含着非碰撞位信息，仍存在一定的冗余。本文算法，在此基础上加入了预处理机制，即在进行常规识别前，所有标签先发送数据给阅读器，阅读器识别所有标签碰撞位并将这些碰撞位组织成新的标签数据。而且在识别过程中能有效记录接收到的既定信息，尽量避免数据的重复发送和接收，并通过状态标志对不同指令的变化进一步减少交互次数，从而进一步减少了通讯量。

用Java进行算法的模拟仿真，仿真参数如表7所示。随机产生长度为64 bit的若干标签，分别采用基本二进制、动态二进制、返回式二进制、文献[9]算法和文献[10]算法对标签进行识别，识别不同数量的标签时几种算法在有效通讯量上的对比，如图2所示。

表7 仿真参数列表

图2 几种算法识别不同数量标签的通讯量对比

从图2对比数据可以看出，改进算法在有效通讯数据量上有较大优势。假设标签长度为L，待识别标签数目为N，存在M个碰撞位，考虑最复杂情况下，即碰撞标签数目最大的情况，即N=2M。

在通讯数据量方面，基本二进制通讯量为：

本文借鉴了文献[9]中部分思想，因此，先对原算法进行讨论。通常情况下，文献[9]算法对于非冲突部分，即L-M位的处理，当其全部位于第一个冲突位前端时，其重复发送次数最少，每个标签只发送一次，共N次。当其全部位于最后一个冲突位后端时，其重复发送次数最多，发送次数为MN次。

当其位于冲突位中间时，其平均发送次数为(M+1)N/2，共(L-M)(M+1)N/2位。

改进后的二进制，对于非冲突部分，即L-M位，其重复发送次数最少，每个标签只发送一次，共N次，即(L-M)N位，这也是新算法通讯量减少的主要原因。

改进算法的预处理阶段，对于M个冲突位，K=lbM-1+1，标签发送数据K+LN位。

对于预处理之后的识别过程：阅读器N-2次发送指令，每次指令长度为K，则共发送K(N-2)=K(2M-2)位。

动态返回二进制约为返回二进制的1/2，故改进二进制通讯数据量与动态返回二进制的通讯量之比约为：

同样加入预处理过程，本文与文献[10]的主要区别在阅读器接收的有效数据和交互次数上。除去预处理过程，同样考虑最坏情况下，即每位存在冲突且N=2M，文献[10]阅读器接收的数据量近似为本文算法的2倍；文献[10]交互次数为2(2M-1)，每次指令长度为K+1，则共发送2(2M-1)(K+1)位，较本文算法交互次数多出1倍。

随着标签数量不断增加，引入预处理机制的新算法在通讯量上较其他算法仍有较大程度的提高。

当标签碰撞位不连续时，新算法性能提升尤其显著。同样设定标签长度为128 bit，当碰撞位占标签总长度的25%时，本文算法与文献[9]算法、文献[10]算法的传送数据对比如图3所示。其中通讯量统计均为阅读器发送指令数据+阅读器接收数据，文献[10]和本文算法则又加入了预处理过程的通讯量。由此可见本文算法在通讯量上的性能提升，如果忽略预处理过程，本文算法优势将更加明显。

在交互次数上，由于采用的搜索策略都是基于返回式二进制的栈式操作，改进程度不大，故在这方面较文献[9]性能提升不明显。图4进一步探讨了标签碰撞位冲突率，即碰撞位占总数据位数比例对通讯数据量的影响。当标签长度为128 bit，数量为70时，文献[9]算法、文献[10]算法的通讯数据量和本文算法对比，碰撞位占20%以下时，本文算法通讯量减少最为明显，且随着碰撞位数的减少，通讯量随之快速减少。

图3 碰撞位冲突率为25%时各算法通讯量对比

总之，本文算法经仿真验证，其在标签数据不发生完全碰撞，且碰撞位不连续时，通讯量减少的效果尤其显著。在文献[9]算法中，每次都需要对标签未发送的数据进行搜索，如果碰撞位不连续，则会将非碰撞位信息一并发送，而加入预处理操作后，每次只发送碰撞位信息，减少了非碰撞位传送的开销，再加上对交互指令的有效减少，整体通讯量大大降低。由此可见，在标签碰撞位不连续且碰撞位少于标签总比特位数一定比例的情况下，本文算法的通讯量有很大程度的减少。

5 结束语

对几种基本防碰撞算法的原理进行了研究，并进行了实例验证，针对阅读器和标签之间通讯数据量存在冗余的情况进行了重点研究。通过加入信息预处理和阅读器只接收有效标签数据的机制，对文献[9-10]多状态二进制算法进行了改进。本文算法在标签识别过程中只处理冲突位信息，并对识别过程进行了简化，既减少了交互次数又减少了阅读器每次接收标签数据的数量，使过程通讯量大大减少。模拟仿真结果表明，本文算法在标签各数据位不完全碰撞，且碰撞位不连续的情况，降低通讯量的效果尤其明显，结合生产生活实际，提出的算法具有较大应用价值。

图4 通讯量和标签碰撞位冲突率的关系

[1]李世煜，冯全源.分层深度搜索树型RFID防碰撞算法设计[J].计算机工程与应用，2009，45（11）：82-84.

[2]Hush D R，Wood C.Analysis of tree algorithms for RFID arbitration[C]//Proceedings of the IEEE International Symposium on Information Theory，1998：107.

[3]Law C，Lee K，Siu K Y.Efficient memory less protocol for tag identification[C]//Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications，Lyons，2000，4：75-84．

[4]Leong K S，Ng M L，Grasso A R.Synchronization of RFID readers for dense RFID reader environments[C]//Proceedings of the International Symposium on Applications and the Internet Workshops，2006：295-298．

[5]He Mingxing，Hong Shijin，Fan Pingzhi，et al.A fast RFID tag identification algorithmbased on counter and stack[J].Expert Systems with Applications，2011，38：6829-6838.

[6]Vogt H.Multiple object identification with passive RFID[C]// Proceedings of the IEEE International Conference on Tags Systems，Man and Cybernetics，2002：6-9.

[7]余松森，詹宜巨，彭卫东，等.基于后退式索引的二进制树形搜索反碰撞算法及其实现[J].计算机工程与应用，2004，40（16）：26-28.

[8]李兴鹤，胡咏梅，王华莲，等.基于动态二进制的二叉树搜索结构RFID反碰撞算法[J].山东科学，2006，19（2）：51-55.

[9]江岸，武继雄，黄生叶，等.改进的RFID二进制搜索防碰撞算法[J].计算机工程与应用，2009，45（5）：229-231.

[10]吴跃前，辜大光，范振粤，等.RFID系统防碰撞算法比较分析及其改进算法[J].计算机工程与应用，2009，45（3）：210-213.

[11]萧耀友，胡钢，魏钦伟，等.基于二进制树分解的动态防碰撞算法[J].通信技术，2011，44（1）：99-101.

[12]向垂益，何怡刚，李兵，等.动态二进制树搜索算法的改进[J].计算机工程，2010，36（2）：260-262.

[13]陈冲，徐志，何明华.一种新的RFID防碰撞算法的研究[J].福州大学学报，2009，37（3）：367-371.

[14]孙文胜，刘婷.一种改进的基于二叉树搜索的防碰撞算法[J].计算机工程，2011，37（10）：257-259.

ZHOU Yancong1，3,HE Min2,GU Junhua2,DONG Yongfeng2

1.School of Electrical Engineering,Hebei University of Technology,Tianjin 300130,China
2.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300401,China
3.School of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China

As there is redundant communication data in multi-state binary algorithm of anti-collision,information preprocessing and partly receive mechanisms are introduced for algorithm improvements.Only the collision information is dealing with in the identification process,and reader only receives part data from tags,avoiding data sent and

repeatedly.Different instructions make state flags self-change,thus the interaction times and the communication data are reduced greatly.Simulation for the algorithm is done in Java.The results show that the new algorithm has obvious advantages in reducing the communication data when the collision bits are not continuous,and collision rate is lower 25%.Excluding the information pretreatment,the new algorithm has more significant advantage at any collision rate.

anti-collision;radio frequency identification;pretreatment mechanism;multi-state binary;dynamic binary

针对多状态二进制防碰撞算法通讯数据存在冗余的情况，引入信息预处理与阅读器部分接收机制。在识别过程只处理冲突位，阅读器只接收并记录标签部分数据，尽量避免数据重复发送与接收，状态标志根据不同指令做变化，减少交互次数，从而降低通讯数据量。采用Java进行算法模拟仿真，结果表明，在碰撞位不连续，碰撞位冲突率低于25%时，算法在减少通讯量方面，具有明显优势。若不计入预处理过程，该算法在任何碰撞位冲突率下通讯数据量都有较大优势。

防碰撞；射频识别；预处理机制；多状态二进制；动态二进制

A

TP301.6

10.3778/j.issn.1002-8331.1112-0652

ZHOU Yancong,HE Min,GU Junhua,et al.Improvement of multi-state binary anti-collision algorithm introduced information pretreatment.Computer Engineering and Applications,2013,49（19）：204-209.

河北省自然科学基金应用基础（No.F2010000142）；天津市自然科学基金（No.12JCZDJC21200）。

周艳聪（1978—），女，博士研究生，讲师，研究方向为数据挖掘，智能信息处理，物流优化；何敏（1987—），女，硕士研究生，研究方向为传感器网络；顾军华，男，教授，博士生导师，研究方向为智能信息处理与软计算，图像处理；董永峰（1977—），男，博士，副教授，研究方向为数据挖掘。E-mail：zycong78@126.com

2012-01-09

2012-03-31

1002-8331（2013）19-0204-06

CNKI出版日期：2012-05-21http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1137.002.html