基于分组机制和跳跃动态二进制识别的多标签防碰撞方法

摘要

本发明公开了一种用于RFID系统中的基于分组机制和跳跃动态二进制识别的多标签防碰撞方法，该方法包括标签估算阶段和标签识别阶段，标签估算阶段对标签随机分组后采用跳跃动态二进制算法识别第一组标签，随后根据每组标签数量服从均匀分布的特性完成对未识别标签数量的估算；标签识别阶段根据估算所得的标签数，确定对剩余各组标签进行第二次分组即最优分组的分组数，识别过程中对碰撞标签采用跳跃动态二进制算法加以识别，进而识别完所有标签。本发明结合了二进制树算法和Aloha算法的优点，大大降低了识别初期和识别后期发生碰撞标签的数量，结构简单，识别速度快，复杂度以及标签功耗低，非常适合应用于RFID系统中。

说明书

技术领域

本发明属于电子、计算机和通信技术等多学科的交叉领域，涉及一种用于物联网技术，特别是一种用于RFID系统中的基于分组机制和跳跃动态二进制识别的多标签防碰撞方法。

背景技术

RFID是一种自动识别技术，即通过无线射频方式进行非接触双向数据通信对目标加以识别。一个典型的RFID系统一般由RFID标签、阅读器以及计算机系统等部分组成。其中RFID标签中一般保存有约定格式的编码数据，用以唯一标识标签所附着的物体。与传统的识别方式相比，RFID技术无需直接接触、无需光学可视、无需人工干预即可完成信息输入和处理，且操作方便快捷。能够广泛应用于生产、物流、交通、运输、医疗、防伪、跟踪、设备和资产管理等需要收集和处理数据的应用领域，并被认为是条形码标签的未来替代品。借助于RFID技术，可以构建全新的“物联网络”。在“物联网络”中，任何物体都可以利用RFID标签进行唯一标识，成为网络中的一个节点，从而能够自动与网络进行连接、交互，并被追踪、定位等等。

目前RFID技术在应用中仍存在着几个需要解决的问题：标签碰撞、RFID安全和隐私保护、天线和RFID定位问题，其中标签碰撞是RFID技术中最常见的问题。在RFID系统中，由于所有标签都使用相同的频率工作，在阅读器的识读范围内，当两个或更多的标签在同一时间都发送自己的数据时，某些数据信号就容易发生叠加，如果没有相应的防碰撞机制，发生叠加的信号不能正确地被接收到，这将使阅读器发生判断错误，认为这个标签不在自己的作用范围内或无法正确读取信息的情况，即发生了标签碰撞。在RFID系统中，防碰撞技术是信号识别和处理的关键技术之一。

现在被业界所推崇的防碰撞算法主要分为两类：一类是基于Aloha协议的随机算法，另一类是基于二进制树的确定算法。这两类算法都存在各自的优缺点：Aloha算法的复杂度及对标签的要求较低，但存在不稳定的工作区间，并且可能导致“标签饥饿问题”，即一些特定的标签可能在很长时间内都无法被识别；二进制树算法的识别率可达100％，即不存在“标签饥饿问题”，但算法比较复杂，识别时间较长。当标签数量较多时，传统防碰撞算法的识别效率通常较低。

发明内容

为了提高系统的识别效率，针对实际应用的RFID系统中标签数目越来越大的情况，本发明的目的是提供一种基于分组机制和跳跃动态二进制识别的RFID系统多标签防碰撞方法。该方法根据标签数目较少时系统识别效率较高的特点，并结合Aloha算法和二进制树算法的优点，算法简单、高效且具有鲁棒性。

本发明的目的是通过以下技术方案来实现的：

一种基于分组机制和跳跃动态二进制识别的多标签防碰撞方法，其特征在于：该方法包括标签估算阶段和标签识别阶段，标签估算阶段对标签随机分组后采用跳跃动态二进制算法识别第一组标签，随后根据每组标签数量服从均匀分布的特性完成对未识别标签数量的估算；标签识别阶段根据估算所得的标签数量，确定对剩余各组标签进行第二次分组即最优分组的分组数，识别过程中对碰撞标签采用跳跃动态二进制算法加以识别，进而识别完所有标签；具体包括以下步骤：

A、阅读器对未识别标签数量进行估算：首先，阅读器设置标签的初始随机分组参数，将标签随机分为预先设定的若干组；随后，阅读器采用跳跃动态二进制算法识别出第一组标签，识别过程中，执行再次分组操作，分组参数与阅读器设置的初始分组参数相同；由于每组标签数量服从均匀分布，据此估算出剩余各组标签的数量，并计算出最优分组的分组参数；

B、阅读器依次发送随机分组命令，对剩余各组标签依次进行识别：在识别任意一组标签的过程中，阅读器再依次发送最优分组命令，对每个时隙状态进行判别，若为无标签的空闲时隙，则直接进入下一时隙，若为单个标签响应时隙，则阅读器直接识别该标签，然后进入下一时隙，若为碰撞时隙，则采用跳跃动态二进制算法识别出该碰撞时隙内所有的标签，然后进入下一时隙，阅读器将最优分组参数减1，直到最优分组参数减至0，至此当前组标签全部被识别；

C、阅读器将随机分组数递减1，并发送最优分组参数开始新一轮识别，依次对当前组中的每个时隙内的标签进行识别，直到随机分组数递减至0。

本发明中，在标签估算阶段，阅读器首先发送一个标签随机分组命令Request(M，1)，所有标签就被随机分成了M组，随后产生随机数“1”的第一组标签向阅读器传送其ID；阅读器识别该组标签，并在识别过程中记录下已经识别的标签数目；若识别第“1”组标签后阅读器记录的标签数目为n，并假设每组中的标签数目都服从均匀随机分布，则总的标签数目约为Mn。

在标签识别阶段，阅读器将分别识别剩余的M-1组共(M-1)n个标签；由于随机数产生过程相互独立，因此不同时刻标签产生[1，M]或[1，p]之间任意一个随机数的概率相同；在识别剩余(M-1)n个标签的过程中，阅读器只需依次发送M-2次Request(M，1)命令和一次Request(M，0)命令，就能确保剩余标签重新被划分为M-1组并依次向阅读器传送其ID，每组标签数目依然满足均匀分布，即每组标签数目都约为n；最后发送一次Request(M，0)命令要求所有剩余标签而不仅是产生随机数1的标签响应，确保识别率为100％。

本发明分为标签估算和标签识别两个阶段。在标签估算阶段，对标签随机分组后只执行一次估算操作，完成对未识别标签数的估算；在标签识别阶段，算法根据估算所得的标签数，确定对剩余各组标签进行第二次分组即最优分组的分组数，识别过程中对碰撞标签采用跳跃动态二进制算法加以识别以提高整个系统的识别效率。

本发明具体算法流程如图1所示。

图1中Request(M，a)为随机分组命令，Request(p，b)为最优分组命令，其中M和p分别为随机分组和最优分组的分组数目参数，并且两种命令的定义如下：

(1)Request(M，a)命令实现的功能是阅读器要求查询区域内所有标签产生一个[1，M]之间的随机数(约定满足均匀分布，下同)，并且选择随机数a的标签回传其ID，而选择其它随机数的标签被暂时“屏蔽”，直到阅读器发送下一个Request(M，a)或Request(M，0)命令时被“唤醒”，这里的Request(M，0)命令约定为阅读器要求查询区域内所有剩余标签回传其ID.

(2)Request(p，b)命令的功能为阅读器要求发生碰撞的标签重新产生一个[1，p]之间的随机数，选择随机数b的标签回传其ID，并暂时“屏蔽”产生其它随机数的标签，直到阅读器发送下一个Request(p，b)或Request(p，0)命令时被“唤醒”，这里约定命令Request(p，0)为阅读器要求某一组内所有剩余标签回传其ID.

在标签估算阶段，阅读器首先发送一个标签随机分组命令Request(M，1)，所有标签就被随机分成了M组，随后产生随机数“1”的第一组标签向阅读器传送其ID。如果没有检测到碰撞发生，阅读器就可以成功识别标签；若发生了碰撞，阅读器则发送Request(p，1)和Request(p，0)命令对碰撞进行识别，并在识别过程中记录下已经识别的标签数目，这里p＝M。若识别第“1”组标签后阅读器记录的标签数目为n，并假设每组中的标签数目都服从均匀随机分布，则总的标签数目约为Mn。

在标签识别阶段，阅读器将分别识别剩余的M-1组共(M-1)n个标签。由于随机数产生过程相互独立，因此不同时刻标签产生[1，M]或[1，p]之间任意一个随机数的概率相同。在识别剩余(M-1)n个标签的过程中，阅读器只需依次发送M-2次Request(M，1)命令和一次Request(M，0)命令，就能确保剩余标签重新被划分为M-1组并依次向阅读器传送其ID，每组标签数目依然满足均匀分布，即每组标签数目都约为n。最后发送一次Request(M，0)命令要求所有剩余标签而不仅是产生随机数1的标签响应，目的就是确保识别率为100％。发送Request(M，1)命令或Request(M，0)命令后，若有标签响应并检测到碰撞发生，阅读器随即发送最优分组命令Request(p，1)对该组中的标签进行第二次分组，即最优分组。同理，阅读器依次发送p-1次Request(p，1)命令和一次Request(p，0)命令就可以把该组内的标签再次分为p组，这里p＝[0.6n]([·]表示取整)，并依次向阅读器发送其ID，若检测到标签碰撞则利用跳跃动态二进制算法进行处理。

从图1可知，标签识别阶段的核心是对剩余M-1组中的每组标签再次执行最优分组操作，即阅读器发送p-1次Request(p，1)命令和一次Request(p，0)命令把每组中的n个标签再次随机分为p组来分别识别，并借助于跳跃动态二进制算法对碰撞标签进行处理，这与标签估算阶段识别第“1”组标签的过程相同，不同的是在标签识别阶段，对剩余的每组标签进行了最优分组，即p取得最优值p＝[0.6n]，而不是M。

本发明的有益效果如下：

本发明首先对标签进行随机分组并利用跳跃动态二进制算法识别出第一组标签，以便估算出剩余各组标签的数量，随后再依次对剩余各组标签进行最优分组后分别进行识别，从而在最大程度上降低标签发生碰撞的概率。

标签估算阶段阅读器对标签随机分组后只识别第一组标签，随后估算标签数量，对估算精度要求不高。标签识别阶段阅读器对标签进行最优分组，确定最优分组参数为每组标签数量乘以0.6，从而大幅减少了标签响应阅读器的次数。在对标签进行随机分组和最优分组的过程中，阅读器发送标签的分组信息，减少了标签的存储空间。本发明的通信复杂度及识别延迟都比较低，对标签随机分组数的选取具有较强的鲁棒性，并且识别效率不受标签ID长度的影响，可以以软件的形式实现，便于移植到各类阅读器中，作为专门构建物联网软件的一个重要部分。

本发明在提高系统识别性能的同时进行能量优化设计，避免了标签在被识别之前多次重复响应阅读器，降低了成本，并且对标签的识别率可达100％。

本发明结合了二进制树算法和Aloha算法的优点，大大降低了识别初期和识别后期发生碰撞标签的数量，结构简单，识别速度快，复杂度以及标签功耗低，非常适合应用于RFID系统中。

附图说明

图1是本发明的算法流程图。

具体实施方式

一种本发明所述的基于分组机制和跳跃动态二进制识别的多标签防碰撞方法，该方法包括标签估算阶段和标签识别阶段，标签估算阶段对标签随机分组后只执行一次估算操作，完成对未识别标签数量的估算；标签识别阶段根据估算所得的标签数，确定对剩余各组标签进行第二次分组即最优分组的分组数，同时对碰撞标签采用跳跃动态二进制算法加以识别，进而识别完所有标签。具体包括以下步骤：

A、阅读器对未识别标签数量进行估算：首先，阅读器设置标签的初始随机分组参数，将标签随机分为预先设定的若干组；随后，阅读器采用跳跃动态二进制算法识别出第一组标签，识别过程中，执行再次分组操作，分组参数与阅读器设置的初始分组参数相同；由于每组标签数量服从均匀分布，据此估算出剩余各组标签的数量，并计算出最优分组的分组参数；

B、阅读器依次发送随机分组命令，对剩余各组标签依次进行识别：在识别任意一组标签的过程中，阅读器再依次发送最优分组命令，对每个时隙状态进行判别，若为无标签的空闲时隙，则直接进入下一时隙，若为单个标签响应时隙，则阅读器直接识别该标签，然后进入下一时隙，若为碰撞时隙，则采用跳跃动态二进制算法识别出该碰撞时隙内所有的标签，然后进入下一时隙，阅读器将最优分组参数减1，直到最优分组参数减至0，至此当前组标签全部被识别；

C、阅读器将随机分组数递减1，并发送最优分组参数开始新一轮识别，依次对当前组中的每个时隙内的标签进行识别，直到随机分组数递减至0。

在标签估算阶段，阅读器首先发送一个标签随机分组命令Request(M，1)，所有标签就被随机分成了M组，随后产生随机数“1”的第一组标签向阅读器传送其ID。阅读器识别该组标签，并在识别过程中记录下已经识别的标签数目。若识别第“1”组标签后阅读器记录的标签数目为n，并假设每组中的标签数目都服从均匀随机分布，则总的标签数目约为Mn。

在标签识别阶段，阅读器将分别识别剩余的M-1组共(M-1)n个标签；由于随机数产生过程相互独立，因此不同时刻标签产生[1，M]或[1，p]之间任意一个随机数的概率相同；在识别剩余(M-1)n个标签的过程中，阅读器只需依次发送M-2次Request(M，1)命令和一次Request(M，0)命令，就能确保剩余标签重新被划分为M-1组并依次向阅读器传送其ID，每组标签数目依然满足均匀分布，即每组标签数目都约为n；最后发送一次Request(M，0)命令要求所有剩余标签而不仅是产生随机数1的标签响应，确保识别率为100％。

下面分(1)、(2)两种情况详细阐述标签的识别过程：

(1)标签识别阶段

阅读器首先发送一个标签随机分组命令Request(M，1)，所有处于阅读器查询范围内的标签都产生一个[1，M]之间的随机数，这里把产生相同随机数的标签分为一组，那么所有标签就被随机分成了M组，随后产生随机数1的标签向阅读器传送其ID.如果没有检测到碰撞发生，阅读器就可以成功识别标签；若发生了碰撞，阅读器则发送Request(p，1)和Request(p，0)命令对碰撞进行识别，并在识别过程中记录下已经识别的标签数目，这里假设p的取值为p＝M.若识别第“1”组标签后阅读器记录的标签数目为n，并假设每组中的标签数目都服从均匀随机分布，则总的标签数目约为Mn.当M太大时，每组中的标签数目可能不再服从均匀随机分布，因此适当的M可以根据实际应用环境中标签规模的大小由人工调整设定.即使M选取的过大以至于每组中的标签数目不再满足均匀随机分布，GJDB算法仍然能够获得较高的识别效率，因为该算法对标签数的估算精度要求不高，并且对M的选取具有较强的鲁棒性。

(2)标签识别阶段

A.阅读器发送标签随机分组命令Request(M，1)，要求查询区域内剩余的所有标签产生一个[1，M]之间的随机数，产生随机数1的标签向阅读器传送其ID，并且暂时“屏蔽”选择其它随机数的标签，直到阅读器发送下一个Request(M，1)或Request(M，0)命令时被“唤醒”.

B.阅读器检测有无标签响应，若无响应转到J；若有响应，检测有无标签碰撞发生.

C.若无标签发生碰撞，阅读器直接识别该标签，随后转到J.

D.若有碰撞发生，阅读器发送最优分组命令Request(p，1)，这里p＝[0.6n]，发生碰撞的标签重新产生一个[1，p]之间的随机数，选择随机数1的标签回传其ID，并暂时“屏蔽”产生其它随机数的标签，直到阅读器发送下一个Request(p，1)或Request(p，0)命令时被“唤醒”.

E.阅读器检测有无标签响应，若无响应转到H；若有响应，检测有无标签碰撞发生.

F.若无标签发生碰撞，阅读器成功识别该标签，随后转到H.

G.若发生了标签碰撞，阅读器则利用跳跃动态二进制算法来识别发生碰撞的标签.

H.转到D后顺序执行，并循环p-1次.

I.在第p次时，阅读器发送请求命令Request(p，0)，要求该组中所有剩余标签响应，随后转到(5)，并顺序执行到(7)后转到(10).

J.转到A后顺序执行，并循环M-2次.

K.在第M-1次时，阅读器发送请求命令Request(M，0)，要求整个识别范围内所有剩余标签响应，随后转到(2)，并顺序执行到(9)后可识别所有标签，则整个识别过程结束。