基于反馈机制的RFID防碰撞算法

1.一种基于反馈机制的RFID防碰撞算法，该算法约定标签对象包括随机数产生器TC、计数器GC、标签组号存储器TG，读写器对象包括当前查询维数RN，组数GN，其特征在于，该算法步骤还包括：
步骤1）标签分组：读写器发送命令Req(GN)，初始化组数GN，标签利用标签内的随机数产生器TC生成0－GN之间的随机数，然后将所生成的随机数保存在标签组号存储器TG中，TG的值便是标签所在的组号，标签随机分成GN+1组，读写器对组号为“0”的标签进行识别，完成对“0”组的识别后，其余组号大于“0”的标签均将组号减一，再开始下一轮对新“0”组标签的识别；
步骤2）标签组内分维识别：首先读写器初始化当前查询维数RN，发送查询命令Req(X,RN)，依据标签前缀与计数器GC的对应关系对GC赋值，然后读写器接收数据GC值，发送查询命令Request(X,RN,gc)，最后读写器检测碰撞情况，依据数据碰撞与标签前缀的判断关系获取命令参数，判断堆栈；
步骤3）标签反馈识别：首先读写器求出[M/V]并反馈给标签，令GN=[M/V]-1，然后标签产生0-GN之间的随机数作为标签组号，存于标签组号存储器TG中，选择组号为“0”的标签进行响应，最后检测碰撞情况，算法结束；
所述的当前查询维数RN为将标签ID每四位分成一维，RN对应每一维的编号；
所述的[M/V]中的M为根据已识别的16组标签信息进行反馈得出16组中的已识别标签的最大数M，V为根据已识别的16组标签信息进行反馈得出16组中的已识别标签的平均数V。
2.根据权利要求1所述的基于反馈机制的RFID防碰撞算法，其特征在于，所述的标签其ID号由非“0”即“1”的二进制位组成，每个标签将其ID号从左至右每四个二进制位分为一维。
3.根据权利要求1所述的基于反馈机制的RFID防碰撞算法，其特征在于，所述步骤2）中的标签前缀与计数器GC的对应关系为GC=1时，标签前缀为0001 0010 0100 1000；GC=2时，标签前缀为1010 1001 1100；GC=3时，标签前缀为0111 1011 1110 1101；GC=4时，标签前缀为0000 1111；GC=5时，标签前缀为0011 0110 0101。
4.根据权利要求1所述的基于反馈机制的RFID防碰撞算法，其特征在于，所述步骤2）中的数据碰撞与标签前缀的判断关系为：在GC=1中只有一个二进制位为“1”，若某一位发生碰撞，则分别将该碰撞位置“1”，其余位置“0”，依次获得当前查询维中存在的标签前缀；
在GC=3中只有一个二进制位为“0”，若某一位发生碰撞，则分别将该碰撞位置“0”，其余位置“1”，依次获得当前查询维中存在的标签前缀；
在GC=4中只有当前查询维中前缀是0000或1111的标签，若发生碰撞，即说明同时存在
0000和1111；
在GC=2中1的个数为2，但最左位均为“1”，若某一位发生碰撞，则分别把相应的碰撞位置“1”，其余位置“0”，依次获得当前查询维中存在的标签前缀；
在GC=5中1的个数为2，但最左位为“0”，若某一位发生碰撞，则分别把相应的碰撞位置“0”，其余位置“1”，依次获得当前查询维中存在的标签前缀。

基于反馈机制的RFID防碰撞算法\n技术领域\n[0001] 本发明属于RFID（射频识别）技术领域。涉及一种捕获效应下基于反馈机制的RFID防碰撞算法。\n背景技术\n[0002] 无线射频识别技术（RFID）是一种自动识别技术，广泛应用于物流、军事、交通、医药等领域。一个基本的RFID系统主要包括阅读器、标签和天线。每个标签中都有唯一标识的ID号，标签与阅读器之间通过射频信号进行通信。同一个RFID系统中所有标签工作在同一频道，当读写器作用范围内存在多个标签时，并在同一时刻可能有多个标签同时与阅读器进行通信，此时标签之间就会产生碰撞，阅读器因不能同时接收所有信息而造成数据丢失，即产生了标签之间的碰撞。\n[0003] 现有的标签防碰撞算法中主要有两类：基于ALOHA的随机算法和基于树的确定性算法。当读写器的作用范围内多个标签应答时，离读写器较近的标签可能因为其信号较强而覆盖其他标签的信号，由此产生了捕获效应。基于ALOHA的随机算法通过随机选择时隙向读写器发送数据，相对来说不能保证整个系统的可靠性，信道的利用率也比较低。基于树的算法通过将冲突节点分成0和1左右两个子集，有序地解决了标签中的冲突问题，但是在识别阶段的初期会产生大量的碰撞，而且对捕获效应的处理比较差。在实际中由于存在捕获效应和信道干扰等造成标签漏读的现象，现有的这两种算法中显然是不能做到对全部标签的识别。\n发明内容\n[0004] 本发明的主要目的是提供一种捕获效应下基于反馈机制的RFID防碰撞算法，用以克服传统防碰撞法可靠性差、信道利用率低，由于大量碰撞，标签与读写器之间的距离不同等造成捕获效应处理差、不能做到对全部标签识别等问题。\n[0005] 本发明的方案是通过这样实现的：一种基于反馈机制的RFID防碰撞算法，该算法约定标签对象包括随机数产生器TC、计数器GC、标签组号存储器TG，读写器对象包括当前查询维数RN，组数GN，该算法步骤还包括：\n[0006] 步骤1）标签分组：读写器发送Req(GN)命令，初始时GN=15，标签利用标签内的随机数产生器TC生成0－GN之间的随机数，然后将所生成的随机数保存在标签组号存储器TG中，TG的值便是标签所在的组号，标签随机分成GN+1组，即16组，读写器对组号为“0”的标签进行识别，完成对“0”组的识别后，其余组号大于“0”的标签均将组号减一，再开始下一轮对新“0”组标签的识别。\n[0007] 步骤2）标签组内分维识别：首先读写器初始化当前查询维数RN，发送查询命令Req(X,RN)，依据标签前缀与计数器GC的对应关系对GC赋值，然后读写器接收数据GC值，发送查询命令Request(X,RN,gc)，最后读写器检测碰撞情况，依据数据碰撞与标签前缀的判断关系获取命令参数，判断堆栈。\n[0008] 步骤3）标签反馈识别：首先读写器求出[M/V],令GN=[M/V] －1并反馈给标签，然后标签产生0-GN之间的随机数作为标签组号，存于标签组号存储器TG中，选择组号为0的标签响应，最后检测碰撞情况，算法结束。\n[0009] 作为本发明的进一步解释说明，所述的标签其ID号由非“0”即“1”的二进制位组成，每个标签将其ID从左至右每四个二进制位分为一维。\n[0010] 作为本发明的进一步改进，所述步骤2）标签组内分维识别其识别过程步骤包括：\n[0011] 步骤2-1，读写器初始化当前查询维数RN=1，查询前缀X=null,当X为null时，组号为0的标签均相应。\n[0012] 步骤2-2，发送查询命令Req(X,RN)，将RN,X告知标签，标签检测其RN中“1”的个数及位置关系，依据标签前缀与计数器GC的对应关系对GC赋值，并向读写器反馈表示GC值的信息序列。\n[0013] 步骤2-3，读写器接收数据GC值，将获知的GC值、X、RN入栈，并获取栈顶元素。\n[0014] 步骤2-4，发送查询命令Request(X,RN,gc)要求前缀与X匹配且GC=gc的标签返回其第RN维及其以后的数据。\n[0015] 步骤2-5，读写器检测碰撞情况，若产生碰撞且RN不是最后一维，则根据查询维中的数据碰撞与标签前缀的判断关系，获取当前存在的标签前缀并将前缀，当前的GC值和查询维数RN=RN+1入栈，获取栈顶元素，返回步骤2-2；若无碰撞或RN为最后一维，则直接识别标签并将其屏蔽后转到步骤2-6。\n[0016] 步骤2-6，判断堆栈，若堆栈为空，则转至步骤2-7；若不为空，则采用后退策略，从堆栈中获取栈顶元素，返回步骤2-4。\n[0017] 步骤2-7，若堆栈为空，其余组号大于“0”的标签均将组号减一，由于漏读的组号为“0”的标签保持组号“0”不变，再对新的“0”组标签进行识别，返回步骤2-1；若所有标签组号为“0”且堆栈为空，则结束步骤2）。\n[0018] 作为本发明的进一步解释说明，所述步骤3）标签反馈识别其识别过程步骤包括：\n[0019] 步骤3-1，读写器用已识别的16组标签信息进行反馈，求出16组中的已识别标签的最大数M和平均数V，求出[M/V]，令GN=[M/V] －1，发送命令Req(GN)。\n[0020] 步骤3-2，标签产生0-[GN]之间的随机数作为标签组号，存于标签组号存储器TG中，读写器选择组号为“0”的标签响应。\n[0021] 步骤3-3，组号为“0”的标签产生“0”、“1”随机数，选择随机数为“0”的标签响应。\n[0022] 步骤3-4，检测碰撞情况，若产生碰撞，则随机数非“0”的标签将其随机数加一，随机数为“0”的标签重新产生“0”、“1”随机数，返回步骤3-4，重新检测碰撞情况；若只有一个标签响应，则识别标签并将其屏蔽后向其他标签反馈其ID，转至步骤3-5；若无标签响应，则读写器要求未识别的标签返回其随机数，检测接收的数据，若有标签响应则转至步骤3-5；\n若无标签返回其随机数，则转至步骤3-6。\n[0023] 步骤3-5，随机数非“0”的标签将随机数减一，返回步骤3-4。\n[0024] 步骤3-6，所有标签组号为“0”，则结束整个识别过程；否则组号非“0”的标签将组号减一，再选择组号为“0”的标签响应返回步骤3-3。\n[0025] 作为本发明的进一步限定，所述步骤2）中的标签前缀与计数器GC的对应关系为GC=1时，标签前缀为0001 0010 0100 1000；GC=2时，标签前缀为1010 1001 1100；GC=3时，标签前缀为0111 1011 1110 1101；GC=4时，标签前缀为0000 1111；GC=5时，标签前缀为0011 \n0110 0101。\n[0026] 作为本发明的进一步限定，所述步骤2）中的数据碰撞与标签前缀的判断关系为：\n[0027] 在GC=1中只有一个二进制位为1，若某一位发生碰撞，则分别将该碰撞位置1，其余位置0，依次获得当前查询维中存在的标签前缀。\n[0028] 在GC=3中只有一个二进制位为0，若某一位发生碰撞，则分别将该碰撞位置0，其余位置1，依次获得当前查询维中存在的标签前缀。\n[0029] 在GC=4中只有当前查询维中前缀是0000或1111的标签，若发生碰撞，即说明同时存在0000和1111。\n[0030] 在GC=2中1的个数为2，但最左位均为1，若某一位发生碰撞，则分别把相应的碰撞位置1，其余位置0，依次获得当前查询维中存在的标签前缀。\n[0031] 在GC=5中1的个数为2，但最左位为0，若某一位发生碰撞，则分别把相应的碰撞位置0，其余位置1，依次获得当前查询维中存在的标签前缀。\n[0032] 本发明具备良好效果和实质性进步：减少了识别初期产生的过多碰撞，通过将标签进行分维识别，加快了标签产生碰撞时的处理速度，在相同条件下，标签产生碰撞时的处理速度平均提高大约25%，识别时间平均减少大约28%，大大减少了识别时间；同时考虑了捕获效应和信道干扰等而产生的标签漏读问题，将已识别的标签信息进行反馈，识别率平均提高到99%以上，大大提高了标签的识别率。\n附图说明\n[0033] 图1.本发明标签分组和标签组内分维识别步骤算法流程图。\n[0034] 图2.本发明标签反馈识别步骤算法流程图。\n具体实施方式\n[0035] 以下结合实施例和附图描述本发明，这些描述并不是对本发明内容作进一步的限定。实施例中算法约定标签对象包括随机数产生器TC、计数器GC、标签组号存储器TG，读写器对象包括当前查询维数RN，组数GN。\n[0036] 实施例1\n[0037] （1）步骤1）标签分组：为减少识别阶段初期因标签数量过多而产生大量的碰撞，首先将标签进行随机分组。本发明中，读写器发送命令Req(GN)，GN=15，标签利用标签内的随机数产生器TC生成0－15之间的随机数，然后将所生成的随机数保存在标签组号存储器TG中，TG的值便是标签所在的组号。读写器选择组号为0的标签进行识别。\n[0038] （2）步骤2) 标签组内分维识别:在组内采用分维识别算法。其具体流程如图1所示，算法分为以下几步：\n[0039] 1）标签ID由非0即1的二进制位组成，唯一标识一个标签，左边为高位。首先标签将其ID从高位到低位每四个二进制位分成一维，由此可将标签分成若干维，如1,2,3维。例如标签ID为0100110001111110，则可以分为四维，其中第1、2、3、4维分别是0100 、1100 、\n0111、 1110 。\n[0040] 2）读写器初始化当前查询维数RN=1，查询前缀X=null，当X=null时，组号为0的所有标签均响应。\n[0041] 3)发送查询命令Req(X,RN)，将X,RN告知标签；读写器根据第RN维中1的个数及位置关系，依据查询维中的标签前缀与计数器GC的对应关系（如表1）对GC赋值，并向读写器反馈表示GC值的信息序列。\n[0042] ①查询维中的标签前缀与GC的关系如下：如当前查询标签的第RN维数据，标签第RN维中1的个数分别为1和3，则相应的GC分别为1和3；1的个数为0或4，则GC=4；1的个数为2且最高位为1，则GC=2,；1的个数为2且最高位为0，则GC=5。\n[0043] ②标签向读写器发送GC值的规则如下：标签将GC值用长度为5的二进制表示，用1的位置表示GC的值。如标签的GC=4，则标签发送的数据为01000。\n[0044] 表1.查询维中的标签前缀与计数器GC的对应关系\n[0045]\n  GC=1 GC=2 GC=3 GC=4 GC=5\n标签前缀 0001 0010 0100 1000 1010 1001 1100 0111 1011 1110 1101 0000 1111 0011 0110 0101 [0046] 4）读写器接收数据，将获知存在的GC值、X、RN入栈，获取栈顶元素。\n[0047] 5）发送查询命令Request(X,RN,gc)，要求前缀与X匹配且GC=gc的标签返回其第RN维及其以后的数据；如X=0100，gc=3，RN=1，则要求标签前缀为0100且计数器GC=3的标签返回其第1维及第1维以后的数据。\n[0048] 6）读写器检测碰撞情况，若产生碰撞且RN不是最后一维，则根据查询维的数据碰撞与标签前缀的判断关系，获取当前存在的标签前缀并将前缀、当前GC值和查询维数RN=RN+1入栈。获取栈顶元素，返回3）；若无碰撞或RN为最后一维，则直接识别标签并将其屏蔽，转到7）。\n[0049] 维数的数据碰撞与标签前缀的判断关系如下：\n[0050] A：在GC=1中因为只有一个二进制位为1，所以如果某一位发生碰撞，则分别将该碰撞位置“1”，其余位置“0”，依次获得当前查询维中存在的标签前缀。如在GC=1中，读写器检测到碰撞位的情况为xxx0,则说明存在前缀1000,0100,0010前缀。\n[0051] B:在GC=3中因为只有一个二进制位为“0”，所以如果某一位发生碰撞，则分别将该碰撞位置“0”，其余位置“1”，依次获得当前查询维中存在的标签前缀。如在GC=1中，读写器检测到碰撞位的情况为xxx0,则说明存在前缀1000,0100,0010前缀。\n[0052] C:在GC=4中，因为只有当前查询维中前缀是0000或1111的标签，所以如果发生碰撞，即xxxx，则说明同时存在0000和1111。\n[0053] D: GC=2和GC=5中“1”的个数均为2，区别在于最高位是“0”或“1”。在GC=2中，最高位均为“1”，且因为“1”的个数为2，所以如果某一位发生碰撞，则分别把相应的碰撞位置“1”，其余位置“0”，依次获得当前查询维中存在的标签前缀。如，在GC=2中，读写器接收到的数据为1x0x，则存在的前缀为1100,和1001。\n[0054] E:在GC=5中，所查询的维数中，最高位均为“0”，因为“1”的个数为2，所以如果某一位发生碰撞，则分别把相应的碰撞位置“0”，其余位置“1”，依次获得当前存在的前缀。\n[0055] 7）若堆栈为空，则转至8）；若不为空，则采用后退策略，，从堆栈中获取栈顶元素，返回5）。\n[0056] 8）若堆栈为空，其余组号大于0的标签均将组号减一，由于漏读的组号为“0”的标签保持组号“0”不变，再对新的0组标签进行识别，返回2－2；若所有标签组号为0且堆栈为空，则结束循环。\n[0057] （3）步骤3）标签反馈识别，其具体流程如图2所示，具体包括以下步骤：\n[0058] 1）读写器用已识别的16组标签信息进行反馈，求出16组中的已识别标签的最大数M和平均数V，求出[M/V]，令GN=[M/V]-1并反馈给标签，令GN=[M/V] －1,读写器发送命令Req(GN)；例如还有6个标签因捕获效应或信道干扰等影响未被识别，读写器求出M和V的比值为2，则将GN=[M/V]-1=1反馈给这6个未被识别的标签。\n[0059] 2）标签产生0-GN之间的随机数，并将随机数作为组号存于TG中，选择组号为0的标签响应；假设这6个标签中，tagA,tagB,tagC的组号均为“0”，tagD,tagE,tagF的组号为“1”，则先识别tagA,tagB,tagC三个标签。\n[0060] 3）组号为0的标签产生“0”、“1”随机数，选择随机数为“0”的标签响应；此处tagA,tagB,tagC分别产生“0”或“1”随机数，这里假设tagA和tagB都产生随机数“0”，而tagC产生随机数“1”，然后tagA和tagB同时向读写器返回其自身ID。\n[0061] 4）检测碰撞情况，若产生碰撞，则随机数非“0”的标签将其随机数加1，随机数为“0”的标签重新产生“0”、“1”随机数，返回4），重新检测碰撞情况；若只有一个标签响应，则识别标签并屏蔽后向其他标签反馈其ID，转至5）；若无标签响应，则则读写器要求未识别的标签返回其随机数，检测接收的数据，若有标签响应则转至步骤5）；若无标签返回其随机数，则转至6）；这里假设由于tagA离读写器较近，虽然与tagB同时传送数据，但因tagA的信号较强，覆盖了tagB的信号，由此理论上应产生碰撞，而此时变成了可读时隙。读写器识别完tagA的信息并将其屏蔽后，将tagA的ID反馈给其余标签，tagB接收反馈信号后发现自身的ID与其不匹配，得知自己信息被漏读。\n[0062] 5）随机数非“0”的标签将随机数减一，返回4）；这里tagB的随机数不变，tagC的随机数减一，然后返回4），读写器重新接收tagB和tagC的数据，检测碰撞情况。这里假设无干扰或捕获效应的影响，tagB和tagC产生了碰撞。因其随机数均为“0”，则重新产生随机数“0”或“1”，如tagB产生“0”，而tagC产生“1”，则下一时隙接收tagB的信息并将其识别进行屏蔽后，tagC的随机数减一，再与读写器进行通信。\n[0063] 6）所有标签组号为“0”，则结束整个识别过程；否则组号非零的标签将组号减一，再选择组号为“0”的标签响应返回3）；这里tagD，tagE，tagF的组号减一后采用同样方法开始下一轮对这三个标签的识别。\n[0064] 本实施例减少了识别初期产生的过多碰撞，通过将标签进行分维识别，加快了标签产生碰撞时的处理速度，在相同条件下，标签产生碰撞时的处理速度平均提高大约25%，识别时间平均减少大约28%，大大减少了识别时间；同时考虑了捕获效应和信道干扰等而产生的标签漏读问题，将已识别的标签信息进行反馈，识别率平均提高到99%以上，大大提高了标签的识别率，具有显著进步和实质性特点。\n[0065] 最后说明的是，以上实施例仅用以说明本发明的技术方案而非限制。尽管参照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，对本发明的技术方案进行修改或者等同替换，都不脱离本发明技术方案的精神和范围，其均应涵盖在本发明的权利要求内。