一种多HASH函数多帧耦合型RFID防碰撞(MHMFG)算法

摘要

本发明涉及一种多HASH函数多帧耦合型RFID防碰撞(MHMFG)算法，该发明针对后台服务器已经统计所有标签ID信息的应用环境。MHMFG包含多个识别帧过程，每帧包括两个阶段：内部排序识别过程及外部识别过程。内部排序识别过程读写器根据保存的所有标签的ID利用多个Hash函数进行映射，根据映射结果对所有的标签ID进行预先排序并形成指导标签响应时隙的位图BitMap。外部识别过程则标签根据接收到的指导位图BitMap以确定自己响应的时隙及相应的响应位数。在完成一帧的识别后对未识别标签利用以上每帧的两个阶段继续进行识别。本发明采用内部排序识别过程及外部识别过程相结合的方法以实现对标签的快速识别，其具有实现简单、识别效率高、通信复杂度低及标签性能要求低的特点。

说明书

技术领域

本发明涉及一种多HASH函数多帧耦合型RFID防碰撞(MHMFG)算法，属于物联网架构 下RFID射频识别领域。

背景技术

随着人类步入信息高速发展的时代，获许和处理的数据量越来越大，若采用人工手段对 信息进行录入和处理则会导致系统效率低下，试想在成千上万的物件中人工对目标物件进行 查找不仅劳动强度大，由于人工失误而导致的操作错误也较大，进而造成人力物力的极大浪 费。以近代计算机技术和移动通信技术为基础的自动识别技术可利用RFID、磁卡识别等技术 及时准确的获取、处理有效信息并实时传递给应用层从而实现了物品信息共享，因此，自动 识别技术是物联网底层关键支撑技术之一。自动识别技术经过多年的飞速发展已经日益深入 各行各业并迎来了前所未有的机遇，生物识别技术、射频识别技术快速发展，构成了物联网 感知层的坚强后盾。同时，RFID技术与条形码技术、磁卡识别技术、IC卡识别等自动识别 技术相比，其通过电磁空间耦合实现了物件的自动识别，具有远距离识别、无需接触、批量 读取、抗干扰性能力强、可读写及可适应于恶劣环境等优点，因此，广泛应用于物流、宠物 管理、供应链、航空、门禁、图书管系统、工业生产系统等领域。RFID系统由后台数据库、 读写器、标签组成。读写器通过对贴附在物体上的标签唯一标识(ID)识别进而利用后台数 据库实现对物体信息的获取。RFID系统使用单双工方式利用共用通信信道实现对其大量标签 的识别，多标签同时在共享无线信道中发送信号必然导致信号的混叠，导致读写器不能正确 识别标签，有效的防碰撞算法可以极大的规避标签响应信号之间的冲撞，因此，如何快速、 精确的识别标签是影响其整体系统效能的关键制约因素，提出有效的防碰撞算法以最大化系 统效率是RFID系统大规避推广的必然要求。

目前针对RFID的混淆问题的解决方案包括空分复用、频分复用、码分复用及时分复用 几类，其中，前三类解决方案由于对系统的高要求及适用范围小等特点使得其不具有广泛推 广性，相比之下时分复用将信道链路的容量按时间分配给不同标签使得其在不同时段响应读 写器的，由于对标签及RFID系统的要求较低，因而，时分复用是当前的研究热点进而成为 了发展最为迅速的RFID防碰撞算法。时分复用类防碰撞算法主要分为两类：一类是基于 ALOHA类的算法，该类算法具有操作简单等优点，但是算法性能受标签估算精度影响较大， 普遍吞吐率较低。同时，ALOHA类算法存在严重的“标签饥饿”现象(部分标签长时间得 不到识别)，饥饿标签长时间处于碰撞状态，由此导致浪费了大量时隙及标签漏检的问题；另 一类算法为树型算法，主要包括前缀质询类(QT)算法和二叉树搜索算法(BS)两大类，树 型算法主要通过制定分类规则进而不断将相同特征的标签归为一个集合，而具有不同特征的 标签划归为另一个集合，直到集合中仅仅包含一个标签，从而实现了标签唯一性识别的目标， 该类算法具有识别精度高的优点，解决了ALOHA类算法的漏检问题。然而，目前的大部分 树型算法存在识别时间较长的问题。

以上基于时分复用的防碰撞类算法利用随机时隙响应的概率性算法或者基于树形的防碰 撞算法虽然可以在一定程度上避免标签之间产生碰撞的概率，其全部都基于读写器在未知应 用环境对标签进行识别，即读写器对标签ID信息无先验性的了解。然而，在物流和超市等许 多应用场景下读写器具有应用环境下的所有标签的ID信息，因此，若采用以上的基于树形和 ALOHA型的防碰撞算法则浪费了大量先验的标签ID信息，故而浪费了大量的识别耗时进而 增加了带宽，本发明针对后台服务器已经统计应用环境下所有标签的ID信息进而快速识别标 签情形提出一种多HASH函数多帧耦合型防碰撞算法。

发明内容

本发明旨在提供一种多HASH函数多帧耦合型防碰撞算法。该算法针对后台服务器已经 统计所有标签ID信息进而快速识别标签的应用环境。采用内部排序识别过程及外部识别过程 相结合的方法以实现对标签的快速识别，其具有实现简单、识别效率高、通信复杂度低及标 签性能要求低的特点。

本发明通过以下技术手段进行实现：

MHMFG包含多个识别帧过程，每帧包括两个阶段：内部排序识别过程及外部识别过程。 内部排序识别过程读写器根据保存的所有标签的ID利用多个Hash函数进行映射。根据映射 结果在后台服务器内部对所有的标签ID进行预先排序以确定标签的响应顺序并形成指导标 签响应时隙的位图BitMap。外部识别过程则标签根据接收到的指导位图BitMap以确定自己 响应的时隙及相应的响应位数，若在BitMap中指导标签进行签到识别则标签仅需在规定时隙 响应Bit“1”以证明自己的存在性，若在BitMap中指导标签进行耦合识别时则标签在规定时 隙响应10位的比特串给读写器，其比特串由标签逐10位异或自身的ID而构成。在完成一帧 的识别后对剩余的标签利用以上每帧的两个阶段继续进行识别。

本发明设计了一种多HASH函数多帧耦合型防碰撞算法，适应于需求快速识别的实际应 用环境，其算法示例如图1所示。

本发明的特点在于：

1.利用了后台服务器具有标签ID的特点对标签ID首先在内部进行预排序，以确定标签 响应的顺序并根据内部响应顺序形成指导位图BitMap，其位图规定了标签的响应优先级、响 应时序及响应位数。读写器对未识别标签逐帧构建BitMap以指导未识别标签的响应时隙。

2.标签根据指导位图BitMap以确定自身的响应时序，利用响应“1”进行签到以证明自 身的存在性，标签在规定时隙响应10位的比特串给读写器以进行耦合识别，即利用1个时隙 可以证明两个标签的存在性以对标签进行耦合识别。

附图说明

图1为本发明的多Hash函数多帧签到及耦合的映射过程

图2为当标签数量为5000时利用MHMFG算法进行识别时的耗时

图3为不同应用环境下映射所需标签内部存储空间

图4为利用内部排序后标签的相应顺序

具体实施方式

MHMFG算法包含多个识别帧过程，每帧包括两个阶段：内部排序识别过程及外部识别 过程。内部排序识别过程读写器根据保存的所有标签的ID利用多个Hash函数进行映射。根 据映射结果在后台服务器内部对所有的标签ID进行预先排序以确定标签的响应顺序并形成 指导标签响应时隙的位图BitMap。外部识别过程则标签根据接收到的指导位图BitMap以确 定响应时序及响应位数。

一、MHMFG算法的执行流程

MHMFG算法的映射过程示例如图1所示，MHMFG算法包含多个识别帧过程，每帧包 括两个阶段内部排序识别过程及外部识别过程。以下进行具体阐述。

(1)内部排序识别过程

读写器按照系统预留参数R₁,R₂...R_g进行标签映射进而生成内部位图，读写器根据保存的 所有标签ID利用Hash函数进行映射。

1)对所有标签执行将每个标签映射到固定时隙内，根 据映射情况读写器统计单标签和两个标签耦合映射时隙个数分别将其记为和定义映 射后时隙中具有1个或2个标签响应的为有效时隙，其余的为无效时隙。

2)将在无效时隙中映射的标签ID转移到集合S₁，随后，继续利用系统参数R₂对S₁内的 标签进行映射将其映射到第一次映射后的无效映射时隙内， 其中，因而经过第二次Hash映射后S₁中的标签继续映射到中进而产 生新的映射位图。

3)如图1所示，若内部排序过程的Hash函数映射次数g＝3则经过第二次映射后分别利 用100,101,000表示单标签\两个标签\多标签及无标签映射时隙，此后，读写器统计单标签和 两个标签映射时隙个数分别将其标记为和并置

由此可见，读写器可以利用预留参数R₁,R₂...R_g类似以上映射过程将标签映射到相应的时 隙内并形成映射位图BitMap，如图1为g＝3的内部映射过程。在g＝3时如图1则生成的BitMap 为001010100100010000110000101000111，经内部映射后标签的排序如图4所示。

4)若经过g次映射后若仍然有标签没有被映射到有效时隙，则继续以上映射1)～3)过 程形成新的位图并对有效映射时隙内的标签进行排序。

(2)外部识别过程

1)读写器广播$<R_1,F_{S_1},C_1^{\left(1\right)},C_1^{\left(2\right)}>,<R_2,F_{S_2},C_2^{\left(1\right)},C_2^{\left(2\right)}>...<R_g,F_{S_g},C_g^{\left(1\right)},C_g^{\left(2\right)}>.$标签接收到 后分别计算$\mathrm{Hash}({\mathrm{ID}}_i,R_1)\mathrm{mod}{F}_{S_1},\mathrm{Hash}({\mathrm{ID}}_i,R_2)\mathrm{mod}{F}_{S_2}...\mathrm{Hash}({\mathrm{ID}}_i,R_g)\mathrm{mod}{F}_{S_g}$并保存。

2)读写器广播内部生成的信息位图BitMap，标签根据位图进而决定响应读写器的时隙。 结合图1进行说明即g＝3的情况。

2.1)这里设置Hash(ID_i,R₁)modF_S1,Hash(ID_i,R₂)modF_S2...Hash(ID_i,R_g)modF_Sg的响应优 先级逐级递减，即若Hash(ID_i,R₁)modF_S1在位图BitMap如果为单标签位图标识则根据自身在 中的位置确定响应读写器的时隙，如果为两个标签位图标识则相应的根据自己映射在 中的位置在时隙响应读写器。以图1为例则标签根据读写器位图 BitMap中001的顺序决定映射到中标签的响应时隙，而010顺序决定映射到中标签 的响应时隙。

2.1)其后将BitMap中由于Hash(ID_i,R₁)modF_S1映射有效的映射位剔除进而构建出 BitMap2，在BitMap中未找到有效响应时隙的标签则在BitMap2中根据Hash(ID_i,R₂)modF_S2查看其在BitMap2[Hash(ID_i,R₂)modF_S2]是否为有效位图标识，若为单标签有效位图标识则根 据其在的位置决定其响应时隙为若为两个标签有效位图标识则其在的 位置决定其响应时隙为对于第j次映射Hashj则若之前的映 射Hash1...Hash(j-1)中未找到有效响应时隙的标签继续根据Hash(ID_i,R_j)modF_Sj查看其在 BitMapj[Hash(ID_i,R_j)modF_Sj]中是否为有效位图标识，若为单标签有效位图标识则根据其在 在位置决定其响应时隙若为两个标签有效位图标识则其在在 位置决定其响应时隙为循环该过程直到Hashj次完 成位图查找，因此，标签根据{Hash(ID_i,R_j)modF_Sj|j∈[1,g]}决定了响应时隙，按照给定时 隙响应读写器进而证明自己的存在性，读写器则在后台按照标签响应顺序在预识别阶段对标 签进行预先排序。

以图1为例可见当g＝3的情况下标签响应时隙如图4所示分别为：

＜1,Tag1＞\＜2,Tag4＞\＜3,Tag7＞\＜4,Tag8＞\＜5,Tag5,Tag6＞\＜6,Tag9,Tag11＞\ ＜7,Tag10,Tag12＞。

完成根据$<R_1,F_{S_1},C_1^{\left(1\right)},C_1^{\left(2\right)}>,<R_2,F_{S_2},C_2^{\left(1\right)},C_2^{\left(2\right)}>...<R_g,F_{S_g},C_g^{\left(1\right)},C_g^{\left(2\right)}>$映射后的所有标签 的存在性响应识别后，剩余的未验证存在性的标签则进入下一次验证性过程，已经证明自身 存在性的标签在当前帧找到了有效映射位图并响应读写器后则进入Sleep状态在一个识别帧 不再响应。

读写器重复以上的内部排序识别过程与外部识别流程，直到验证完毕所有标签则完成对 标签的识别过程，即重复以上过程直到所有标签完成映射识别，每帧包括内部排序识别过程 与外部识别流程，在下一帧则针对未识别标签执行两个阶段。

说明：

1)在时隙后排序的标签则响应10Bit数据，其对自身ID进行逐10bit异 或以获得响应信息位，在预定时隙发生碰撞则证明该时隙的两个标签全部存在，若只有其中 一个标签存在则读写器可根据标签ID异或进而判断哪个标签存在，若未收到任何响应则证明 其该映射时隙内的两个标签离开了识别范围。

2)在当前帧识别完毕后，若在后台服务器仍然就有标签未映射到相应的时隙内则利用内 部排序识别过程及外部识别过程进行对未识别的标签再识别。其中每帧的参数R₁,R₂...R_g为固 定值，可以这样设置第一帧的R₁,R₂...R_g为1，2…g。第二帧的R₁,R₂...R_g为g+1,g+2…2g。以 后的识别帧可以依次类推，由于执行效率的要求，可以在标签端存储多位Hash(ID_i,R_j)以满 足标签快速响应的要求，由理论部分可见识别全部标签数n_Max＝100000时，所需标签的内部 存储空间为l_sum(n_Max)＝161Bit。

3)每帧初始时，读写器广播的的给定与后台数据库已知的所有位映射到有效时隙中 的标签数量n相关，其具体分析在理论分析部分给出，而到F_Sg的给定 则利用$F_{\mathrm{Sj}}=F_{S(j-1)}-C_{j-1}^{\left(1\right)}-C_{j-1}^{\left(2\right)}$进行设置。

4)依据PHILIPS I-CODE系统且对应具有96位标签ID的系统，传输96位标签ID的t_ID时长为2.4ms，传输10位的数据所需t_l时长为0.8ms，传输1位的数据所需t_s时长为0.4ms， 进而由t_ID可以得其数据传输率为96/2.4ms＝40Kb/s。

本发明中依据EPCGlobalC1G2标准规定，数据传输速率为128Kb/s。进而将本发明中 的t_ID、t_l、t_s的时长分别统一规定为0.75ms，0.25ms，0.125ms。

5)依据说明4)的系统参数设置利用理论推导部分可见当g＝3且时则系 统获得最快的识别速度，本发明采用的MHMFG算法对标签进行识别，其平均识别耗时稳定 在142.6μs。

二、MHMFG算法性能理论分析

由MHMFG算法的执行流程描述可知，其对标签进行识别时，后台数据库进行内部映射 预见多Hash映射后的结果并在后台数据库中按照位图进行排序以识别标签，其利用多次Hash 函数将标签ID映射到位图上并广播生成的位图用于对标签响应时隙的时序进行指导。

(1)当g＝1时，令θ＝n/F_S则：

$I_0^{\left(1\right)}=F_S\left(\begin{array}{c}n\\ 1\end{array}\right){\left(\frac{1}{F_S}\right)}^1{(1-\frac{1}{F_S})}^{n-1}={\mathrm{ne}}^{-\frac{n-1}{F_S}}\approx {\mathrm{ne}}^{-\frac{n}{F_S}}=F_S\theta e^{-\theta }---\left(1\right)$

$I_0^{\left(2\right)}=F_S\left(\begin{array}{c}n\\ 2\end{array}\right){\left(\frac{1}{F_S}\right)}^2{(1-\frac{1}{F_S})}^{n-2}=\frac{n(n-1)}{{2F}_S}{e}^{-\frac{n-2}{F_S}}\approx \frac{n(n-1)}{2F_S}{e}^{-\frac{n}{F_S}}=0.5F_S{\theta }^2{e}^{-\theta }---\left(2\right)$

其中，及分别为使用第1个Hash函数映射后对应的单个标签及两个标签响应的时 隙数，因此，若g＝1则标签平均识别耗时AvgT₁(θ)如下式：

上式中为发送位图而导致的耗时，为便于与现有标准相统一，这里将位图分 割为96bit逐一发送。

2)当g>1时，则对经过Hash1映射后无标签和多标签>2响应的无效位图标识则再利用 Hash2进行映射，因此有下式：

$n_{\left(1\right)}=n-I_0^{\left(1\right)}-{2I}_0^{\left(2\right)}\approx n-{\mathrm{ne}}^{-\frac{n}{F_S}}-2\frac{n(n-1)}{2F_S}{e}^{-\frac{n}{F_S}}=F_S(\theta -\theta e^{-\theta }-{\theta }^2{e}^{-\theta })---\left(3\right)$

$R_{F_S\left(1\right)}=F_S-I_0^{\left(1\right)}-I_0^{\left(2\right)}\approx F_S(1-\theta e^{-\theta }-0.5{\theta }^2{e}^{-\theta })---\left(4\right)$

其中，n₍₁₎及分别为在经Hash(ID_i,R₁)映射后后台数据库端除有效映射位图标识对应 的标签外剩余的标签数及帧长F_S的剩余时隙数，进一步可知对应Hash(ID_i,R₂)映射的单个标 签响应及两个标签响应的时隙数如下：

$I_1^{\left(1\right)}=n_{\left(1\right)}{e}^{-\frac{n_{\left(1\right)}}{R_{F_S\left(1\right)}}}=F_S(\theta -\theta e^{-\theta }-{\theta }^2{e}^{-\theta })e^{-\frac{\theta -\theta e^{-\theta }-{\theta }^2{e}^{-\theta }}{1-\theta e^{-\theta }(1+0.5\theta )}}---\left(5\right)$

$I_1^{\left(2\right)}=\frac{n_1(n_{\left(1\right)}-1)}{2R_{F_S\left(1\right)}}{e}^{-\frac{n_{\left(1\right)}}{R_{F_S\left(1\right)}}}=\frac{F_S{(\theta -\theta e^{-\theta }-{\theta }^2{e}^{-\theta })}^2}{2(1-\theta e^{-\theta }(1+0.5\theta ))}{e}^{-\frac{\theta -\theta e^{-\theta }-{\theta }^2{e}^{-\theta }}{1-\theta e^{-\theta }(1+0.5\theta )}}---\left(6\right)$

因此，标签平均识别耗时AvgT₂(θ)如下：

其中，AvgT₂(θ)为比例系数θ的函数，在已知标签n的情况下，设定合理的F_S则可使得 RFID系统对其标签识别效率达到最优，因此，可对AvgT₂(θ)求导进而获得θ的最优值使得 AvgT₂(θ)最小。

当g＞2时，类似于以上过程利用Hash函数对剩余的标签及之前HASH函数映射后剩余 的时隙做进一步处理，则：

$I_i^{\left(1\right)}=n_{\left(i\right)}{e}^{-\frac{n_{\left(i\right)}}{R_{F_S\left(i\right)}}}---\left(8\right)$

$I_i^{\left(2\right)}=\frac{n_{\left(i\right)}(n_{\left(i\right)}-1)}{{2R}_{F_S\left(i\right)}}{e}^{-\frac{n_{\left(i\right)}}{R_{F_S\left(i\right)}}}---\left(9\right)$

$n_{\left(i\right)}=n_{(i-1)}-n_{(i-1)}{e}^{-\frac{n_{(i-1)}}{R_{F_S(i-1)}}}-2\frac{n_{(i-1)}(n_{(i-1)}-1)}{2R_{F_S(i-1)}}{e}^{-\frac{n_{(i-1)}}{R_{F_S(i-1)}}}---\left(10\right)$

$R_{F_S\left(i\right)}=R_{F_S(i-1)}-I_{i-1}^{\left(1\right)}-I_{i-1}^{\left(2\right)}=R_{F_S(i-1)}-n_{(i-1)}{e}^{-\frac{n_{(i-1)}-1}{R_{F_S(i-1)}}}-\frac{n_{(i-1)}(n_{(i-1)}-1)}{2R_{F_S(i-1)}}{e}^{-\frac{n_{(i-1)}-2}{R_{F_S(i-1)}}}---\left(11\right)$

其中，n_(i)、为分别执行Hash(ID_i,R_i+！)后S中剩余的标签数，及则为利用 Hash(ID_i,R_i+！)映射后读写器可识别的单标签及两个标签响应的时隙。因此，当g≥2对标签进 行识别时，其标签平均识别耗时AvgT_g≥2如下：

上式中是由于每个Hash映射后对应的在映射图中具有三类信息状态即：单标 签映射位图标识、两个标签映射位图标识及无效映射位图标识(对应多标签响应及无标签响 应时隙)，由于无效映射位图标识对于每次Hash过程一样，因此，所有Hash过程映射过程中 仅需利用一个信息状态即可，类似的AvgT_g≥2(g,θ)为g,θ的函数，因此，对AvgT_g≥2(g,θ)利用 拉格朗日乘子法可获得最优的g及其相应的θ以使得AvgT_g≥2(g,θ)达到最快的平均识别速度， 鉴于标签的运算功能等限制g值不宜太大，因此，这里将g限定在一定范围内，限定g∈[1,6]， 进而利用公式12可得理论曲线如图2所示，进而可知在g＝3时在识别5000个标签的情况下， θ＝1.545139时MHMFG算法识别效率达到最优，即帧长F_S设定为时AvgT_g(g,θ) 获得极小值进而获得对标签最快的识别速度。故本发明采用的MHMFG算法对标签进行识别， 其平均识别耗时为142.6μs。以下对在g＝3的情况下MHMFG算法标签需要执行的最大 Hash(ID_i,R_j)次数进行分析，在θ＝1.545139完成第一帧映射识别后剩余的标签数n_s如下：

$\left(\begin{array}{c}{n}_s=n-(I_0^{\left(1\right)}+I_1^{\left(1\right)}+I_2^{\left(1\right)})-2(I_0^{\left(2\right)}+I_1^{\left(2\right)}+I_2^{\left(2\right)})\\ =n_{\left(2\right)}-n_{\left(2\right)}{e}^{-\frac{n_{\left(2\right)}}{R_{F_S\left(2\right)}}}-n_{\left(2\right)}\frac{n_{\left(2\right)}}{R_{F_S\left(2\right)}}{e}^{-\frac{n_{\left(2\right)}}{R_{F_S\left(2\right)}}}\\ =0.138875n\end{array}\right)---\left(13\right)$

由公式13可知，MHMFG算法对标签识别的收敛速度较快，例如在n＝5000的情况下第 一帧识别完毕后剩余695个标签，由此可见MHMFG算法能够在极短的几帧内将标签识别完 毕，由此可见若0.138875^xn≤1时则标签识别完毕，故而帧时则标签识别完毕， 进一步由于θ＝n/F_S，故在第一帧识别时设定在g＝3的情 况下，第一帧映射时每个标签产生的3个Hash(ID,R)在标签数为n的情况下可为 在第i帧时，则因此，完成标签的识别时，需在最 后一帧映射位图中进行识别的标签需产生的映射Hash(ID,R)总长度l_sum(n)如下：

故由上式可知，可根据应用环境下最大的标签数量n_Max进而在标签生产时注入 l_sum(n_Max)bit的Hash(ID,R)以进行MHMFG算法映射响应，而无需标签进行多次Hash运算， 进而可节省标签的大量计算资源。如图3所示，在n_Max＝100000时，l_sum(n_Max)＝161Bit，由此 可见，对标签的快速识别仅需标签内极小的存储空间。