（长春理工大学 电子信息工程学院，长春 130022）

互联网技术的出现，带动了相关技术的蓬勃发展，这其中对世界发展影响最大的当属物联网［1］。物联网，顾名思义，就是借助于外部识别技术将外界的“物”与互联网联系起来，按照约定好的规则对其进行区分管理。物联网技术的核心是RFID技术，利用RFID技术阅读器能够将标有不同标签的“物”进行区分。但是也由此产生了RFID技术的“致命”缺陷，当阅读器识别范围内存在多个标签，并且这些“物”的标签同时向阅读器发送请求识别信号，可想而知，多个信号之间肯定会出现互相干扰现象，该现象在信号传输领域被称作碰撞。碰撞现象的出现直接降低了阅读器对标签的识别精度。为减少标签碰撞现象对物联网系统的影响。国内外物联网专家开始了长时间的研究。截止到21世纪为止，应对碰撞现象最有效的方法是引入防碰撞机制降低标签的碰撞概率。这些防碰撞机制发展至今可以总的分为四类：时分多址、频分多址、空分多址和码分多址。这其中又以时分多址使用最为普遍［2］。

以时分多址防碰撞机制为基础，又衍生出了许多行之有效的防碰撞算法，这些算法又可以归结为两大类：ALOHA不确定性防碰撞算法和二进制搜索确定性算法。第一种不确定性算法是通过控制应答器间接防止标签碰撞的算法，其优点是投入成本低，系统功耗少，操作简单易实现。缺点是在实际生产环境下伴随着标签数目的增加，应答器控制性能会急剧降低，不适用于标签数目巨大的场合。后一种算法相比于ALOHA算法，缺点是结构复杂，操作难度大，识别过程复杂。优点是识别效率不会随标签数目的急剧增加而降低，非常适合标签数量巨大的场所。该算法在实际生活中的使用也是最为普遍的。由于二进制算法优秀的识别效率，很多专家希望从其他角度可以有效弥补该算法的缺陷，随后产生了许多改进式二进制算法：动态二进制算法、后退式二进制算法等。这些改进式算法都能有效降低RFID系统的标签碰撞概率［3］。

虽然以上改进的二进制算法有效降低了标签的碰撞几率，但改进算法本身还存在各自的缺陷，后续通过对这些算法中存在的问题进行分析总结，在其基础上提出了一个新的改进算法，在接下来的篇幅中会对以上算法进行探讨，并对新的改进算法进行详细阐述，最后通过模拟仿真软件对算法的可行性进行测试。

1 二进制防碰撞算法

1.1 基本二进制防碰撞算法

二进制防碰撞算法的理论核心是二叉树的深度优先遍历理论，具体工作流程如下：RFID系统运行过程中，出现碰撞现象，系统根据反馈信号将碰撞标签划分为两个结点，并分别标记为0和1.然后继续进行识别，如果标记为1的节点中继续出现碰撞现象［4］，再根据反馈信号增加新的结点，以此类推，直到所有标签全部识别为止。具体过程如图1所示.

图1 基本二进制防碰撞算法模型

基本二进制算法是基于二叉树理论最基础算法，它是利用RFID系统中的阅读器在同一时刻发射出的不同的命令字符与被识别标签进行匹配从而确定标签是否出现碰撞现象。为了更好的解释基本二进制算法的工作原理，以实际识别过程为例：

首先设定RFID系统所处环境，射频识别系统阅读器识别范围内存在四个不同的电子标签，分别为：标签A、B、C、D；这些标签内分别存储以下数据：0110101，0010011，0011010，0110110.接下来开始进行识别，阅读器向区域内标签发射请求命令，四个标签同时响应。此时可能出现碰撞现象，启动基本二进制防碰撞算法，直到所有标签准确无误识别为止。具体识别过程如表1所示。

假设基本二进制算法查询次数的均值为Q，该参数的大小需要通过RFID系统中阅读器的识别范围内的标签的数目N决定，由此可得计算公式：

如果需要被检测的标签数目也是为N，则总的查询次数Qsum为：

表1 基本二进制算法的识别过程

综合公式（1）和公式（2）可得：并由此可得基本二进制算法的系统吞吐量S为：

假设该RFID系统标签长度为L，则阅读器与标签之间的交互数据的数量分别为：

由此可得，该RFID系统中，阅读器和标签传输的总信息量Psum为：

根据以上公式可知，基本二进制防碰撞算法能够完全准确识别N个标签，识别一个标签需要log2N+1次发布命令［5］。并且该算法在识别出一个标签后，会从初始点开始识别并发布命令，此时在系统内部会产生大量的数据冗余。解决基本二进制算法的数据冗余问题，也是后续改进二进制算法的主要研究方向。

1.2 动态二进制防碰撞算法

动态二进制防碰撞算法是通过降低传输命令的长度减少通信数据量的。动态二进制算法工作流程与基本二进制算法完全相同，差别在于动态二进制算法中标签反馈回的序列号，只截取了可以识别的部分。具体识别过程如下表2所示。

通过比较表1，表2可以明显看出，相同条件下，两种算法的查询次数相等。动态二进制通过降低反馈信息长度可以有效降低数据通讯数量，降低通讯时间。

假定以上算法的数据交互过程，只交互序列号信息，基本二进制算法需要传输完整序列号，动态二进制算法只需传输可识别位［6］，很明显可以看出，在数据传输量方面动态二进制远低于基本二进制算法。由此可得，动态二进制算法的通信数据总量P为。

其中，N为待识别标签数目，L为标签序列号的长度。

1.3 后退式二进制算法

后退式二进制防碰撞算法也是以基本二进制算法为基础，通过引入退避理论对基本二进制算法进行了优化。后退式二进制算法在阅读器完成一次识别任务后，直接返回上一个父节点，并转向临近分支继续进行识别。具体识别过程如下表3所示.

表2 动态二进制算法的识别过程

表3 后退式二进制算法的识别过程

通过比较表1和表3可知，两个算法的工作流程前三步是完全一致的，第4步开始发生变化，基本二进制算法直接返回到第一步重新开始，后退式仅返回至上一层父节点处，随后又从临近节点开始进行识别，最终实现了所有标签的识别。实验结果表明，后退式仅仅比基本式二进制算法减少了一次查询，没有大幅度提升算法效率，但在大数目标签场合，后退式的提升效果会更加明显。

同理，假设RFID系统阅读器可识别范围内标签的数量还是N，则对应的后退式算法的查询次数Qs和吞吐量S为：

假设标签序列号长度仍为L，那么系统总传输数据量P为：

2 改进的二进制搜索算法

2.1 算法改进分析

由上一节的分析可知，当识别长序列ID的标签时，基本二进制算法会产生大量的数据冗余，由于查询顺序的固化，该算法每次识别完成新标签后都要重新识别，增加了大量识别时间［7］。通过对比动态二进制和后退式算法的改进机制结合它们存在的缺陷提出了新的改进算法，改进角度从以下两方面入手：

1.降低交互数据的过度冗余

一般情况下，RFID系统发布查询命令后，阅读器识别范围内的标签都会反馈，基础二进制算法反馈全部信息，产生大量信息冗余，动态二进制算法将发生碰撞的标签数据分为两部分［8］，前半部分为碰撞标签信息一致部分不进行传输，后半部分为碰撞标签区分位，最后只反馈区分位的序列信息，有效降低了交互信息的重复传递，在改进算法中继续沿用该模式。

2.有效减少识别时间

根据基本二进制防碰撞算法的工作原理可知，当RFID系统识别完成一个算法后，在进行下一部分识别前，会返回至初始节点，然后重新开始进行识别，增加了太多重复识别路程，浪费了识别时间。后退式算法是返回至上一层的父节点，在一定程度上增加了识别效率［9］。

（1）新改进算法除了返回上一父节点之前，会对上层节点进行判断，选择与现有节点判别序列号接近的节点进行返回，有效减少无用功。

（2）对于阅读器识别内的应答碰撞信号，在进行识别前进行简要判断：

①如果碰撞位的识别区域序列为偶数，则采用四叉树法；

②如果碰撞位的识别区域序列为奇数，则继续采用二叉树法；

③如果碰撞位的识别区域仅有一位特殊数字，则可以直接判断，不进入防碰撞算法功能［10］。

通过以上措施能够有效提升识别效率，降低识别时间。

2.2 改进式二进制防碰撞算法描述

本次测试实验标签为八个，分别为：标签A：0110101；标签B：0010011；标签C：0011010；标签D：0110110；标签E：1001010；标签F：1110101；标签G：1001000；标签H：1110001；识别过程如表4所示。

表4 改进式二进制防碰撞算法的识别过程

接下来对以上识别过程进行简要分析：

首先，第1步的标签信息一致部分为：null，表示没有一致的标签序列，此时，所有标签都会反馈阅读器发布的命令，由于标签碰撞节点位数为八位，所以使用四叉树理论进行识别［11］。第2步发送00命令，反馈参数序列为001X01X，首先将高位碰撞位置0，继续进行识别，识别结束后，返回临近父节点0011继续识别，识别结束返回临近上一级的父节点01，此时反馈序列参数为：01101XX，继续高位置0，发布命令011010X，识别标签返回临近节点，发布命令011011X，识别并返回临近节点10，得到反馈序列10010X0，由于此时仅有一个特殊碰撞位，直接识别即可，分别置0、1。识别出最后的两个标签，识别过程结束。

根据上一节关于其他算法的公式可知，使用其他算法解决相同问题，基本二进制算法和动态二进制算法需要最少进行24次命令发布；后退式算法至少需要15次命令发布。而改进算法只用了9次。运算效率高下立判。此外，还使用了动态二进制算法的仅发送识别序列信息的方式，极大的降低了数据冗余量。

3 算法性能分析

3.1 改进算法公式推导

假设改进算法与其他算法处于相同环境下，可识别标签数为N，由于改进算法存在多种判定情况，此时以不出现单个碰撞位情况作为讨论对象，此时该改进算法的查询次数为：2N-1，如果出现单个碰撞位情况，并设其次数为x，此时总的查询次数Qs为：

并且由此可得，同等条件下，改进算法识别全部标签的数据交互总量P为：

3.2 改进算法模拟仿真对比

通过使用MATALAB仿真软件对上述二进制算法在数据传输量、查询次数两个方面进行仿真得到如图5、图6所示的比较结果［12］。

通过模拟仿真图2可知，在可识别标签的数目一致的前提下，改进算法数据传输量远远低于其他算法，在实际应用场景中，相信改进算法的优势会更加明显。

图2 几种算法的数据传输量比较

图3 三种算法查询次数比较

改进算法不仅在传输数据冗余上远低于其他算法，在查询次数上也远低于基本二进制算法，由图3可知，改进算法的识别效率远高于其他算法，具有实际可行［13］。

4 结束语

通过对现有的基本二进制算法的运行情况进行了研究，以及对改进型的二进制算法进行了对比，沿用其优秀部分，避免其有弊部分，提出了新的改进二进制算法，该算法从多个角度出发降低了传输数据数量，减少了传输时间，有效解决了传输过程数据冗余。最后通过实际模拟实验进行了验证，改进算法同比与其他传统算法具有很高的优势，具有实际推广的可行性，对于物联网背景下的RFID大数目标签场景具有借鉴意义。