基于布隆过滤器的RFID包含关系追溯查询

眭相杰+廖国琼

摘要：在实际的供应链中，通常会将商品装进包装箱后进行流通，随着供应链规模的增大，需要存储的包含关系数量也随之增大。论文针对供应链中包含关系追溯的需求，提出一种基于布隆过滤器的包含关系存储结构以及相应的追溯算法。首先，根据商品在供应链中的流通特征，将其状态分为成原始状态以及包含状态。然后，基于两种状态设计了相应的包含关系表达方式编码，并将得到的编码利用布隆过滤器存储。最后基于该结构设计了相应的包含关系追溯查询算法。论文所提出的存储结构，相比较于存储原始数据的方法，可有效降低供应链存储压力，具有较好的空间性能。

关键词：RFID；供应链追溯；包含关系；布隆过滤器

中图分类号：TP391 文献标识码：A 文章编号：1007-9416（2017）09-0044-03

1 引言

射频识别技术（Radio Frequency Identification）是近年来兴起的一种自动识别技术，已成为当今物联网大潮中不可或缺的支撑技术之一。RFID技术正被广泛应用于物流与供应链管理、生产制造、交通运输等领域，可大幅度提高企业管理效率和降低运营成本[1]。在供应链环境下进行RFID对象追溯查询已成为研究热点。

供应链环境下RFID对象的追溯查询，按追溯功能，还可以分为位置追溯（查询对象的流通位置）及包含关系追溯（查询对象之间的包含关系）。包含关系在日常生活中普遍存在，反映了不同对象之间的更深层次的位置关联关系。识别这种关系有利于提供高质量的位置服务[2]。而要构建在供应链上整个生命周期内健壮且无缝的追溯系统，需设计合理的追溯模型、编码机制及追溯策略等[3]。

包含关系其本质上是一种层次关系，在设计编码机制的时候应能支持以上的包含关系追溯。同时，还应考虑供应链环境中“多层级性”、“时态变化性”、“整体改变性”的包含特征[4]。文獻[5]在集中式结构下提出了高效的包含关系追溯查询的向量编码方法，并提出供应链环境中包含关系追溯需求主要包括：历史追溯，即物品在流通过程中经历了哪些容器；向上追溯，即物品位于哪个容器内；向下追溯，即容器包含哪些物品；平行追溯，即物品与哪些物品位于同一容器内。在文献[6]中，刘等人提出了在集中式环境下采用区间编码方式的记录包含关系，并验证了其可行性与高效性。目前许多相关研究是基于集中式环境下的，但随着供应链规模增大，集中式存储的方式堆积大规模数据，增大了服务器的压力，不适用于大规模供应链环境。并且，在数据存储方式方面，常采用存储原始数据的方式来记录RFID数据，这种方式将带来存储巨量数据及冗余数据的问题。

本文拟在上述研究基础上改善包含关系追溯模式。为改善集中式的缺陷，引入分布式结构环境，在文献[7]中，分析了分布式结构存储的优势。为改善储原始数据及存储冗余数据的缺陷，引入布隆过滤器结构作为存储结构。在文献[8]中，首次提出利用布隆过滤器作为存储器实现本地存在查询、历史路径查询的方法，具有存储开销小，查询效率高的特点。

本文主要工作如下：研究基于“布隆过滤器”存储结构下的包含关系追溯编码机制；提出相应的追溯策略追溯策略。以实现在低存储开销下RFID对象包含关系的追溯。

2 布隆过滤器

本文基于基本布隆过滤器结构。布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假阳性）。在布隆过滤器中，编码通过Hash映射分散到许多存储单元中，并置这些存储单元的值为1，查询编码是否存在时，编码通过函数映射到对应的存储单元，若这些存储单元值全都为1则存在。由于是多个编码共享同一存储区域，这种存储方式相对于存储原始数据方式的开销减小了。

如图1所示，编码Code1、Code2分别通过4个哈希函数映射到相应的存储单元中，并将这些存储单元置为1。在查询编码Code1是否属于这个集合时，将编码通过4个哈希函数映射，显然所有位置都是1，那么就认为Code1是集合中的元素。但是在存储编码时，由于哈希函数映射的不可逆性，即信息一旦映射入布隆过滤器结构，信息本身销亡，因此不能简单地将物品Tag标签映射，否则所有物品tagID同处于一个布隆过滤器中，不存在层次关系。因此，还需设计相应编码来表达包含关系，我们将在下节介绍编码策略。

运用基本布隆过滤器的查询方式如下：①输入端：包含关系编码；②查询算法：存在查询，若查询成功，则返回编码所示信息（如AB），并根据查询类别决定是否继续查询或转发查询；③输出端：返回的包含关系集合（如集合{AB，BC}）。

3 包含关系编码策略

本节将给出能支持包含关系追溯的编码策略。分析供应链对象状态，对象可分为组合状态、原始状态。原始状态是指供应链中独立的单位个体；组合状态指对象处于容器中或本身是容器，如容器X包含了物品a，则有关系aX。为方便表述，先提出如下几个概念：

定义1：物件码，唯一标识某一对象。物件码（16位）=类别号（3位）+批次号（9位）+编号（4位）；

定义2：包含码（OB），包含关系编码前缀；原始状态码（SC），物件码前缀；区分码，包含码、原始状态码两种码的统称；

定义3：原始状态编码为SC+物件码；组合状态编码为OB+物件码+物件码（容器）。

处理生产批号时，添加了类别号作为后缀，其作用类似于“外码”，将在下节提到。

如上图2所示的编码示例中，商品A、B在环节①中还未装进包装箱，处于原始状态，此时环节①节点存储A、B原始状态编码信息。进入环节②节点后，商品A、B被装入包装箱C中，环节②节点此时应存储三个编码信息，即包装箱C的原始状态编码信息、A与C以及B与C间的组合状态编码信息。endprint

判断编码类型时，首先识别区分码，若为OB则表示包含关系。若为SC则为非包含关系编码，可进行文献[8]中的路径追溯等查询，该模块不详细讨论。

表1为包含关系编码示例。

4 包含关系追溯查询算法

为满足四类包含关系追溯查询：向上追溯、向下追溯、平行追溯、历史追溯，本节设计了相应的追溯查询算法。由于布隆过滤器存储方式的不可逆性，布隆过滤器查询输入端不能得到完整编码。为解决这一问题，我们引入了“次序关系”、“域表”两个结构，如图3所示，其概念如下：

次序关系：次序关系表存储“物品大类”间的包含关系，如“SCA01-SCZZ1”表示存在类别号为A01的物品在类别号ZZ1的容器内。只当次序关系查询存在时才进行下一步布隆查询。当次序关系查询为存在时，其返回内容是容器或物品类别号，返回结果传递给域表。次序关系可以提高查询效率，关系不存在的情况下可提前终止查询。

域表：域表记录了物件码中的生产批号以及相应编号的最小值与最大值（物件码中末4位）。域表得到次序关系查询传递的类别号时，在“生产批号”单元中遍历后3位进行匹配，读取匹配成功所在行的最小值与最大值，在该范围内，将编码拼接成布隆过滤器输入端所需的包含关系编码以获得查询序列。域表使得查询明确了终止条件。

布隆过滤器的作用是将域表提供的查询序列逐一遍历地进行存在查询，并将查询成功的序列按查询需要添加到集合中或将序列转发进行下一步查询，下面根据不同类型的包含关系追溯查询进行详细地算法描述。

4.1 向上追溯查询算法

向上追溯即查询物品在什么容器内。关键点为多层级性，即物品可能被一个或多个容器包含。本文提出如表2所示的向上追溯查询算法。

4.2 向下追溯查询算法

向下追溯即查询容器中包含了些什么物品。与多层级性类似，容器内可能会存在一个或多个物品，并且可能存在容器的容器，即容器内包含其他容器的情况，需进行递归查询。本文提出如表3所示的向下追溯查询算法。

4.3 历史追溯查询算法

历史追溯即查询物品在发起查询节点之前（包括发起查询节点）的流通路径中所经历过的所有容器。历史追溯查询实质是路径查询结合向上查询。本文提出如表4所示的历史追溯查询算法。

4.4 平行追溯查询算法

平行追溯即查询当前节点查询物品和哪些物品放在同一个容器内。实质上是向上追溯与向下追溯结合，本文给出的平行追溯查询算法精度到与查询物品“同一层级”为止，即忽略多层级关系。本文给出的平行追溯查询算法如表5所示。

5 结语

为实现基于布隆过滤器的RFID包含关系追溯查询，本文主要从理论上设计了包含关系编码和相应的包含关系追溯查询算法。该方法的特点是存储消耗较低，主要利用了布隆过滤器压缩数据的功能。

参考文献

[1]Wu Y， Ranasinghe D C， Sheng Q Z， et al.RFID enabled traceability networks： a survey[J].Distributed & Parallel Databases，2011，29（5-6）：397-443.

[2]李晓迪.RFID空间中移动对象包含关系探测技术的研究[D].东北大学，2014.

[3]Lee D， Park J. RFID‐based traceability in the supply chain[J]. Industrial Management & Data Systems，2008，108（6）：713-725.

[4]Gan O P， Zhao Y Z， Luo M， et al. System Architecture and Data Design for RFID-Based Item Level Track and Trace[M].//Engineering Asset Management. Springer London， 2006：1098-1103.

[5]廖國琼，万齐智，蒋剑，等.支持RFID对象包含关系追溯的几何向量编码策略[J].小型微型计算机系统，2014，35（6）：1298-1303.

[6]刘海龙，李战怀，陈群. RFID供应链系统中的在线复杂事件检测方法[C].//ndbc2010中国数据库学术会议.2010：731-741.

[7]Murthy K， Robson C. A Model-based Comparative Study of Traceability Systems[J]. 2012.

[8]Liu J， Xiao B， Bu K， et al. Efficient distributed query processing in large RFID-enabled supply chains[C]// INFOCOM， 2014 Proceedings IEEE. IEEE， 2014：163-171.endprint