基于布隆過濾器的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