謝東，肖杰，郭廣軍，江彤

?

可追蹤供應(yīng)鏈中非確定性RFID數(shù)據(jù)處理方法

謝東1, 2，肖杰3，郭廣軍4，江彤1

(1. 湖南人文科技學(xué)院計算機科學(xué)技術(shù)系，湖南婁底，417000；2. 中南大學(xué)信息科學(xué)與工程學(xué)院, 湖南長沙，410083；3. 湖南第一師范信息技術(shù)系，湖南長沙，410205；4. 婁底職業(yè)技術(shù)學(xué)院電子信息工程系, 湖南婁底，417000)

針對可追蹤供應(yīng)鏈應(yīng)用系統(tǒng)中大量非確定性RFID數(shù)據(jù)不能被有效處理的問題，通過分析RFID應(yīng)用的關(guān)鍵特征，根據(jù)非確定性數(shù)據(jù)的比例來調(diào)整滑動窗口，采用不同策略處理不同類型的非確定性數(shù)據(jù)，提出可處理各種類型非確定性數(shù)據(jù)的清洗方法；根據(jù)對象在供應(yīng)鏈中出現(xiàn)的位置及其連續(xù)性來區(qū)分多讀、漏讀和不完整數(shù)據(jù)，基于對象在物流節(jié)點中移動路徑對應(yīng)的有向圖進(jìn)一步提出可適應(yīng)對象分組和獨立移動的處理算法。研究結(jié)果表明：提出的方法具有良好的清洗效果、存儲效率以及查詢性能，在不同參數(shù)條件下能有效地支持對象路徑查詢。

供應(yīng)鏈；無線射頻識別；非確定性數(shù)據(jù)

無線射頻識別(RFID)技術(shù)[1]是對物體貼上具有唯一標(biāo)示符的電子產(chǎn)品標(biāo)簽(electronic product code，EPC)，再進(jìn)行無線識別的方法，能自動被RFID閱讀器識別并生成大量數(shù)據(jù)，被廣泛應(yīng)用于供應(yīng)鏈管理(supply chain management, SCM)中[1]。RFID應(yīng)用跨越多個企業(yè)來獲取RFID對象的屬性和位置數(shù)據(jù)，根據(jù)對象在不同時期的位置信息(數(shù)據(jù)血統(tǒng))來追蹤其歷史軌跡和位置。盡管大多數(shù)RFID數(shù)據(jù)是精確的，但由于RFID閱讀方位感知的敏感、干擾、閱讀部件故障和一些環(huán)境因素，RFID原始數(shù)據(jù)往往是不完整、不精確甚至是錯誤的。非確定性RFID數(shù)據(jù)類型一般包括：1) 由于閱讀角度、信號閉塞、信號盲區(qū)等因素，難以獲取對象確定位置導(dǎo)致漏讀數(shù)據(jù)；2) 由于不同的RFID閱讀器可能存在交叉的閱讀區(qū)域，同一個RFID對象可能被不同的RFID閱讀器讀取，從而具有不同位置的非一致性數(shù)據(jù)；3) 閱讀器在閱讀區(qū)域可能獲取不存在的信號，這種信號被識別為并不存在的RFID對象，導(dǎo)致多讀數(shù)據(jù)；4) 有源的RFID閱讀器可能在不同時間間隔內(nèi)頻繁地讀取沒有移動的RFID對象，從而產(chǎn)生具有不同時間戳但具有相同位置信息的冗余數(shù)據(jù)；5)非完整數(shù)據(jù)表現(xiàn)為RFID對象數(shù)據(jù)沒有出現(xiàn)在供應(yīng)鏈中的某些位置，主要原因為假貨在某個供應(yīng)鏈節(jié)點進(jìn)入供應(yīng)鏈或RFID對象被偷。以上這些問題導(dǎo)致用戶查詢難以直接在非確定性RFID數(shù)據(jù)上進(jìn)行操作。由于傳統(tǒng)的ER模型難以表達(dá)RFID數(shù)據(jù)的時序性，Wang等[2]提出了DRER模型，將RFID數(shù)據(jù)分為基于事件和基于狀態(tài)2種類型，并進(jìn)一步考慮了移動閱讀器，細(xì)化了應(yīng)用場景并建模[3]。然而，這些工作涉及多個相關(guān)位置的路徑查詢，需要對存儲數(shù)據(jù)進(jìn)行多次自連接，導(dǎo)致效率較低，且沒有考慮非確定性數(shù)據(jù)。基于時間平滑的策略[4]通過靜態(tài)窗口來填補漏讀數(shù)據(jù)，但無法根據(jù)數(shù)據(jù)的實時特性去靈活調(diào)整窗口大小。Jeffery等[5]提出了一種自適應(yīng)時空平滑過濾器，但填補效果較差。谷峪等[6]通過監(jiān)控物體所在小組的動態(tài)分析來實現(xiàn)數(shù)據(jù)清洗，但需要先進(jìn)行數(shù)據(jù)清洗才能被RFID應(yīng)用使用。粒子濾波[7]從能直接觀測的明顯狀態(tài)(如RFID閱讀器的位置)推測不能直接觀測的隱藏狀態(tài)(如物流對象位置)，但重采樣階段會損失樣本的有效性和多樣性，導(dǎo)致定位不準(zhǔn)。文獻(xiàn)[8]和[9]分別采用高斯混合分布和時變的圖模型來獲取數(shù)據(jù)的非確定性，但在移動手持機環(huán)境下，仍然定位不準(zhǔn)。上述方法均只針對漏讀，未考慮不一致數(shù)據(jù)。基于可能世界語義的非確定性數(shù)據(jù)管理[10]。PCQA語義[11]建立非一致性數(shù)據(jù)[12]的所有可能世界語義和所有可能一致性的子集，但假定數(shù)據(jù)是獨立的。謝東[14]在可能世界語義基礎(chǔ)上發(fā)展了一種可擴展的非確定性數(shù)據(jù)處理平臺，在高層應(yīng)用上能直接對非確定性數(shù)據(jù)進(jìn)行處理，但這些方法都沒有考慮漏讀數(shù)據(jù)。以上工作均沒有考慮所有類型的非確定性數(shù)據(jù)，在這些數(shù)據(jù)形成的海量可能世界實例上難以有效地進(jìn)行涉及多個相關(guān)位置的路徑追蹤。本文作者考慮所有類型的非確定性數(shù)據(jù)，在基于一階邏輯的非一致性數(shù)據(jù)處理方法[15]和非確定性RFID數(shù)據(jù)模型[16]等工作基礎(chǔ)上，通過分析RFID對象的關(guān)鍵特征，提出一種非確定性數(shù)據(jù)處理方法，根據(jù)漏讀與多讀、冗余和非一致性數(shù)據(jù)的比例來調(diào)整滑動窗口，采用不同策略處理漏讀、多讀、冗余、非一致性和非完整性(假貨與對象被偷)數(shù)據(jù)，并根據(jù)對象在供應(yīng)鏈中出現(xiàn)位置及其連續(xù)性來識別多讀、漏讀和非完整數(shù)據(jù)；通過建立表達(dá)對象路徑的有向圖，進(jìn)一步提出可適應(yīng)對象分組和獨立移動的處理算法，處理后的數(shù)據(jù)在不同參數(shù)條件下能有效地支持包括跟蹤、追蹤、聚集、循環(huán)和長路徑等對象路徑查詢。

1 非確定性RFID數(shù)據(jù)的處理方法

1.1 基于RFID的供應(yīng)鏈

基于RFID的供應(yīng)鏈流程如圖1所示。其中，可能是一個多讀數(shù)據(jù)，但并不存在；被重復(fù)讀取，在沒有改變位置的情況下將生成冗余數(shù)據(jù)；被漏讀，需要根據(jù)相關(guān)信息來推斷它的位置；被2個閱讀器同時讀取，具有2個不同的位置；假貨在供應(yīng)鏈中游加入；在倉庫被偷；特別地，多讀、假貨與對象被偷類似，都不存在于供應(yīng)鏈的某些位置。

圖1 基于RFID的供應(yīng)鏈

RFID應(yīng)用是類似的，具有非確定性、不同位置的時序相關(guān)性、相同位置的對象相關(guān)性和粗粒度。基于這些特點，本文給出了如下定義。

定義1 RFID閱讀。RFID閱讀是一個具有唯一EPC的RFID對象tagID在timestamp時間點被閱讀器讀取，表示為rd=(tagID, timestamp,readerID)。

定義2 RFID數(shù)據(jù)流。RFID數(shù)據(jù)流是多個具有唯一EPC的RFID對象tagID在timestamp時間點被readerID閱讀器讀取，表示為=(rd, rd, …, rd)，其中rd=(tagID, timestamp, readerID)。

本文總結(jié)了幾類基本實體：具有唯一EPC的RFID對象、閱讀器和位置。這些實體產(chǎn)生的數(shù)據(jù)分為部署數(shù)據(jù)、閱讀數(shù)據(jù)和概略數(shù)據(jù)。部署數(shù)據(jù)在RFID應(yīng)用部署時就被獲取，這些數(shù)據(jù)相對穩(wěn)定、確定，如位置和閱讀器數(shù)據(jù)等；閱讀數(shù)據(jù)為RFID閱讀器讀取的數(shù)據(jù)；概略數(shù)據(jù)為通過處理閱讀數(shù)據(jù)后生成的面向用戶查詢的數(shù)據(jù)。

1.2 處理框架

圖2所示為非確定性RFID數(shù)據(jù)的處理框架。RFID閱讀器從多個數(shù)據(jù)流讀取EPC數(shù)據(jù)，根據(jù)已存在閱讀數(shù)據(jù)的非確定性比例來指定一個滑動窗口；然后根據(jù)已有的閱讀數(shù)據(jù)推斷讀取的數(shù)據(jù)是否存在漏讀數(shù)據(jù)，存儲RFID對象的EPC、位置和時間戳到RFID數(shù)據(jù)庫中(其中，非一致性、多讀和冗余數(shù)據(jù)也需要被存儲到RFID數(shù)據(jù)庫中)，并進(jìn)一步修改非一致性數(shù)據(jù)，清洗多讀和冗余數(shù)據(jù)。

圖2 非確定性RFID數(shù)據(jù)處理框架

滑動窗口顯著地影響冗余、非一致性、多讀和漏讀數(shù)據(jù)的比例。若選擇大的窗口，則能獲取RFID對象更多的信息，但容易導(dǎo)致更多的冗余、非一致性和多讀數(shù)據(jù)產(chǎn)生；若選擇小的窗口，則可以減少冗余、非一致性和多讀數(shù)據(jù)的產(chǎn)生，但容易產(chǎn)生更多的漏讀數(shù)據(jù)。SMURF[5]難以有效地確定一個自適應(yīng)的窗口，本文提出1個滑動窗口策略去調(diào)整冗余、非一致性、多讀和漏讀數(shù)據(jù)的比例。

不同比例下的滑動窗口如圖3所示。當(dāng)漏讀頻繁發(fā)生時(從1到2)，Stream A趨向于有1個更大的窗口；而當(dāng)冗余、非一致性和多讀現(xiàn)象頻繁發(fā)生時(從2到3)，Stream C趨向于有1個更小的窗口；Stream B是相對適中的，趨向于平衡2類閱讀。根據(jù)漏讀比例，小窗口需要適當(dāng)放大。根據(jù)冗余、非一致性和多讀比例，大窗口需要適當(dāng)減小。采用如下公式調(diào)整滑動窗口：

1.3 數(shù)據(jù)推斷

閱讀數(shù)據(jù)(,) 一般可生成反映RFID對象狀態(tài)的存儲形式(,,in,out)，其中[in,out]表示EPC在位置的停留時間。不同非確定性數(shù)據(jù)處理的推斷規(guī)則如下：

定義3 推斷規(guī)則(INFERRING RULE)被采用模式(PATTERN)-條件(CONDITION)-操作(ACTION)形式：

其中：為非確定性數(shù)據(jù)類型；為該類型屬于何種具體情況；為執(zhí)行的推斷操作。

推斷不同類型的非確定性數(shù)據(jù)如圖4所示。

(a) 漏讀數(shù)據(jù)；(b) 非一致性數(shù)據(jù)；(c) 多讀數(shù)據(jù)；(d) 冗余數(shù)據(jù)；(e) 非完整性數(shù)據(jù)(假設(shè))；(f) 非完整性數(shù)據(jù)(對象被偷)

1) 漏讀數(shù)據(jù)。對象1通過位置-1，2和3，但在位置2時未檢測到?？梢愿鶕?jù)RFID對象的移動歷史和位置關(guān)系來推斷，若與對象1一起的其他RFID對象從位置1到3必須通過位置2，則可以推斷對象1也通過了位置2，并獲得在位置2的停留時間及概率，如(1,2,2,3,)。

2) 非一致性數(shù)據(jù)。對象1從1到3，可能被2個不同的閱讀器讀取，從而形成具有2個不同位置2和′2的非一致性數(shù)據(jù)。可以采用2種方法推斷：一種是類似于漏讀數(shù)據(jù)的推斷，根據(jù)RFID對象的移動歷史和位置關(guān)系來推斷，如(1,p,2,3,)；另一種是根據(jù)RFID應(yīng)用的粗粒度特點，把包含2個不同位置2和2的上一級位置a代替當(dāng)前非一致性位置，如 (1,a,2,3)。

3) 多讀數(shù)據(jù)。不存在的對象1在位置2被讀取，且1也不會在其他位置出現(xiàn)，可以表示為->->。但如果一個RFID對象在離開生產(chǎn)線后馬上被偷，由于被偷RFID對象也與多讀數(shù)據(jù)一樣都只出現(xiàn)1次，那么可能被誤認(rèn)為是多讀數(shù)據(jù)，因此，需要進(jìn)一步區(qū)分。多讀數(shù)據(jù)需要被定期清洗。

4) 冗余數(shù)據(jù)。位置沒有改變的RFID對象在不同的時間間隔內(nèi)被讀取，如對象1在時間戳2和′2上被讀取2次。由于1可能在下一個位置被漏讀，推斷其漏讀位置需要最近的位置信息，因此，需要保存最近的位置信息，直到對象1到達(dá)新的位置為止。

5) 非完整性數(shù)據(jù)(假貨)。假貨在供應(yīng)鏈中下游混入正常的產(chǎn)品中，但假貨不會出現(xiàn)在生產(chǎn)線上。如假貨1出現(xiàn)在位置2和3，但1沒有在位置1出現(xiàn)，表示為->2->3。在供應(yīng)鏈中只出現(xiàn)1次的假貨沒有意義，假貨進(jìn)入零售商上游就必須被讀取2次，而直接進(jìn)入零售商則不需要貼EPC。由于假貨實際存在，出現(xiàn)2次以上假貨數(shù)據(jù)不會被清洗，此外，克隆假貨的EPC可能出現(xiàn)在生產(chǎn)線上，因此，克隆假貨和正品可能同時出現(xiàn)在供應(yīng)鏈中或者不同時出現(xiàn)，該EPC可能形成2條歷史軌跡，克隆假貨形成的歷史軌跡在位置上往往不連續(xù)。

6) 非完整性數(shù)據(jù)(對象被偷)。圖4(f)顯示RFID對象在某一位置被偷，被偷對象可能重新進(jìn)入該供應(yīng)鏈，也可能永遠(yuǎn)丟失。如對象1出現(xiàn)在位置1，但對象1在位置2被偷，因此，對象1在位置2沒有被讀取，1的軌跡可以表示為1->->(永遠(yuǎn)丟失)，或者重新在位置3進(jìn)入，表示為1->->3。

1.4 多讀、漏讀和非完整性數(shù)據(jù)的區(qū)分

由于多讀、漏讀和非完整性數(shù)據(jù)都是在供應(yīng)鏈中某些節(jié)點缺乏位置信息，而它們的處理方法不同，因此，需要區(qū)分這些數(shù)據(jù)。這些數(shù)據(jù)難以在閱讀器讀取時就立即區(qū)分。例如，對象1出現(xiàn)在位置1，對象1可能是多讀或者假貨。

圖5所示為多讀、漏讀和非完整性數(shù)據(jù)在供應(yīng)鏈中可能出現(xiàn)的位置。漏讀數(shù)據(jù)可能出現(xiàn)在除生產(chǎn)線的任何位置；假貨只出現(xiàn)了供應(yīng)鏈的中下游，不可能進(jìn)入生產(chǎn)線，假貨也不會直接進(jìn)入零售商，否則假貨無需貼上EPC，可直接銷售給消費者；RFID對象不可能在生產(chǎn)線上被偷，若被偷則一定發(fā)生在被貼簽之前，對象被偷可能發(fā)生在除生產(chǎn)線上的其他位置，也可能被偷后重新進(jìn)入供應(yīng)鏈；多讀數(shù)據(jù)可能發(fā)生在供應(yīng)鏈的任意位置，在生產(chǎn)線上的非確定性數(shù)據(jù)只可能存在多讀數(shù)據(jù)。

圖5 多讀、漏讀和非完整性數(shù)據(jù)在供應(yīng)鏈中出現(xiàn)的位置

圖6所示為多讀、漏讀和非完整性數(shù)據(jù)的3種情況。

1) 情況A顯示1個閱讀數(shù)據(jù)只出現(xiàn)生產(chǎn)線上，這可能是多讀或者對象在離開生產(chǎn)線后馬上被偷。由于RFID對象在生產(chǎn)線寫入產(chǎn)品參數(shù)，因此，可以推斷多讀數(shù)據(jù)沒有相關(guān)參數(shù)，而被偷數(shù)據(jù)有相關(guān)參數(shù)。

2) 情況B顯示普通假貨的EPC在生產(chǎn)線上沒有信息，而克隆假貨在生產(chǎn)線上有相關(guān)信息，但缺乏連續(xù)位置信息。這是因為RFID對象在供應(yīng)鏈中移動是連續(xù)的，具有相鄰的連續(xù)位置信息，而克隆假貨是突然出現(xiàn)在供應(yīng)鏈中，因而缺乏相鄰的連續(xù)位置信息。

3) 情況C顯示RFID對象出現(xiàn)超過1次，但沒有出現(xiàn)在某些位置。這可能是因為RFID對象在某些位置被漏讀或者被偷的RFID對象重新進(jìn)入供應(yīng)鏈。漏讀的RFID對象一般消失在離散的位置，而被偷的RFID對象一般消失在連續(xù)的位置，且被偷的RFID對象將脫離原來的分組。因此，可以通過位置的連續(xù)性和分組情況來區(qū)分這2類情況。

(a) 情況A；(b) 情況B；(c) 情況C

1.5 數(shù)據(jù)模型

本文采用如下的模型存儲非確定性數(shù)據(jù)(圖7)。在部署數(shù)據(jù)中，(,,)存儲閱讀器的EPC、名字和所有者；(,)存儲RFID對象的EPC和類型；(,,)存儲位置ID、名字、上一級位置ID；(,)存儲業(yè)務(wù)類型。在閱讀數(shù)據(jù)中，(,)通過和生成，存儲RFID對象的原始數(shù)據(jù)；為了區(qū)分非確定性數(shù)據(jù)，非克隆假貨、克隆假貨、被偷對象與正常對象的值分別為2, 1, 0和NULL。在概要數(shù)據(jù)中，(,in,out,,)存儲閱讀器在一定時間間隔內(nèi)的業(yè)務(wù)活動；(,)存儲路徑序列；(,in,out)存儲在一定時間間隔內(nèi)的位置；()存儲對象的路徑序列。

圖7 數(shù)據(jù)模型

1.6 算法

基于提出的框架和規(guī)則，本文提出了基于有向圖(定義1)的非確定性數(shù)據(jù)處理算法。

定義4 一個從上游到下游的供應(yīng)鏈可表示為有向圖<,,>，其中表示為的物流節(jié)點，表示為一對物流節(jié)點<,>之間的對象移動，表示為對象移動的權(quán)重。根節(jié)點為對象的制造商，每個節(jié)點是其前驅(qū)節(jié)點的子節(jié)點，也是其后續(xù)節(jié)點的父節(jié)點。

圖8中的有向圖顯示邊<12>和<13>的權(quán)重分別為1和2，表示從1到2和從1到3的概率(即出現(xiàn)漏讀和非一致性數(shù)據(jù)的可能性)，概率為前驅(qū)節(jié)點出發(fā)經(jīng)過該有向邊的歷史移動對象與該前驅(qū)節(jié)點出發(fā)的總歷史移動對象的比例。

圖8 表示對象移動的有向圖

根據(jù)圖4(a)和4(f)，算法1處理多讀、冗余、非完整性、漏讀和非一致性數(shù)據(jù)，調(diào)用算法2，建立有向圖和路徑序列。算法1再根據(jù)閱讀器出現(xiàn)的位置，對清洗多讀和冗余數(shù)據(jù)，并標(biāo)記假貨和被偷對象的數(shù)據(jù)；根據(jù)有向圖中從父節(jié)點到子節(jié)點的路徑權(quán)重，在給定閾值條件下標(biāo)記和處理漏讀和非一致性數(shù)據(jù)，插入漏讀數(shù)據(jù)到或者通過聚集更高層次的時間間隔和位置修改非一致性數(shù)據(jù)；最后，計算滑動窗口尺寸。

算法1首先調(diào)用算法2，由于中的元組數(shù)等于中的元組數(shù)，算法2在第1步開始的循環(huán)次數(shù)為，因此，算法2的時間復(fù)雜度為()。在第3步開始的外循環(huán)次數(shù)為，在第17和24步開始的內(nèi)循環(huán)次數(shù)均為路徑長度(3~22)。由于內(nèi)循環(huán)EPC不可能同時滿足第17和24步開始的2個條件，因此，第3步開始的循環(huán)的時間復(fù)雜度為()，最后得到算法的時間復(fù)雜度為((+1))。

算法1 main

Input:；閾值；用戶可接受的非確定性數(shù)據(jù)的比例；可調(diào)整的時間間隔；非確定性數(shù)據(jù)比例的調(diào)整參數(shù)和

Output: 清洗多讀和冗余數(shù)據(jù)；標(biāo)記非完整性數(shù)據(jù)；修改漏讀和非一致性數(shù)據(jù)；滑動窗口尺寸w

Begin

1. Builddirectedgraph (EPC);

2. ra ← 0；t ← READING元組數(shù)；

3. For RADING中EPC do

4. If EPC 在節(jié)點上只出現(xiàn)一次

5. 刪除多讀數(shù)據(jù)；

6. Else if EPC在同一節(jié)點出現(xiàn)2次以上

7. 刪除所有時間戳較晚的冗余數(shù)據(jù)；

8. Else if EPC沒有出現(xiàn)在根節(jié)點

9. 區(qū)分EPC為非克隆假貨；

10. Else if EPC出現(xiàn)在根節(jié)點且有完整路徑，但路徑的相鄰節(jié)點不連續(xù)

11. 區(qū)分EPC為非克隆假貨；

12. Else if EPC出現(xiàn)在根節(jié)點但沒有出現(xiàn)在后續(xù)節(jié)點

13. 區(qū)分EPC為被偷對象；

14. Else if EPC 沒有出現(xiàn)在某一節(jié)點

15. ra ++；

16. 區(qū)分EPC為漏讀數(shù)據(jù)；

17. For i =1 to 路徑長度l do

18. {W ← 第i個漏讀節(jié)點路徑的權(quán)重；

19. If W ≥ TV

20. STAY ← EPC的漏讀節(jié)點;

21. Else 通過聚集上級AT和AP修改EPC在STAY的模糊路徑節(jié)點位；}

22. Else if EPC在同一時間出現(xiàn)在2個位置

23. 區(qū)分EPC為非一致性數(shù)據(jù)；

24. For i ← 1 to 路徑長度l do

25. {W ← 第i個非一致性節(jié)點路徑的權(quán)重；

26. If W ≥ TV

27. 修改EPC的非一致性節(jié)點到STAY；

28. Else通過聚集上級AT和AP修改EPC在STAY的非一致性路徑節(jié)點位；}

29. }

30. ra2 ← ra/t；

31. ra1 ← 1 – 已清洗的READING元組數(shù)/t - ra2 ；

32. sw ← adj*(m*(acra–ra1)–n*(acra–ra2)) ；

End

算法2 Builddirectedgraph

Input: EPC

Output: 有向圖；SEQ

Begin

For i ← 1 to STAY中的元組數(shù)do

{parent ← EPC的根節(jié)點；

node = EPC在parent的子節(jié)點；

If node is NULL then

{node ← new node；

node.loc ← EPC.loc；

node.tin ← EPC.tin；

node.tout ← EPC.tout；

parent的子節(jié)點 ← node；

}

加入node.path到PATH；

W ← parent到node邊的權(quán)重；

W ← PATH；

}

End

2 實驗評價

2.1 實驗環(huán)境

本文考慮了所有類型的非確定性數(shù)據(jù)，與以往工作的實驗數(shù)據(jù)不可能一致，因此，無法將本文方法與以往方法進(jìn)行比較。

實驗評價環(huán)境中采用CPU為Core i2 2.00 GHz，內(nèi)存為2 Gb RAM的機器，操作系統(tǒng)為Windows 7，數(shù)據(jù)庫為MYSQL5.6。由于缺乏通用的RFID測試數(shù)據(jù)，本文根據(jù)1個食品物流模型[17]生成數(shù)據(jù)，并建立相應(yīng)的查詢進(jìn)行測試。

對象被生成在進(jìn)口市場和農(nóng)產(chǎn)品供應(yīng)商等根節(jié)點，再通過分組或個別運輸形式移動到下一個位置。采用有向圖并考慮分組因素去生成對象數(shù)據(jù)，分析分組因素對查詢性能的影響。有向圖的每個節(jié)點表示某一位置的一組對象，邊表示對象在位置之間的移動。一般地，靠近根節(jié)點的對象移動往往是更大的組，靠近葉子的對象移動往往是更小的組。分組的尺寸表示為，表示為一起移動的對象數(shù)量。本文根據(jù)有向圖中給定的隨機地生成數(shù)據(jù)，對應(yīng)有向圖中的邊，表示對象移動。

由于非確定性數(shù)據(jù)大部分是漏讀數(shù)據(jù)，考慮如下影響因素：漏讀、冗余和多讀數(shù)據(jù)比例，用戶指定的位置和時間間隔層次(基于這2個層次的路徑序列將自動聚集)，不同數(shù)據(jù)規(guī)模，實驗參數(shù)見表1。

表1 實驗參數(shù)

2.2 數(shù)據(jù)處理

根據(jù)不同參數(shù)比較清洗后的存儲規(guī)模。設(shè)置漏讀數(shù)據(jù)比例=(0.500, 0.250, 0.100, 0.500, 0.025)，冗余和多讀數(shù)據(jù)比例分別為G=(0, 0.333, 0.500, 0.666, 0.750)，對象數(shù)量分別為1 000，2 500，5 000，7 500，10 000的數(shù)據(jù)規(guī)模為=(3 800, 31 700, 135 000, 427 500, 975 000)。本文在表中清洗冗余和多讀數(shù)據(jù)，計算漏讀數(shù)據(jù)且存入該表，也標(biāo)注假貨和被偷對象等非完整性數(shù)據(jù)，并修改非一致性數(shù)據(jù)。

由于漏讀數(shù)據(jù)比例與冗余和多讀數(shù)據(jù)比例是對立的，因此，采用5組數(shù)據(jù)比例來表示，組1為(=0.5,G=0)，組2為(=0.25,G=0.333)，組3為(=0.1,G=0.5)，組4為(=0.05,G=0.666)，組5為(=0.025,G=0.75)。漏讀數(shù)據(jù)比例從0.500 下降為0.025，冗余和多讀數(shù)據(jù)比例從0 提高為0.75。由圖9可知：沒有清洗過的數(shù)據(jù)在不同和G下呈線性增長。由于漏讀數(shù)據(jù)被推斷計算后插入，而冗余和多讀數(shù)據(jù)在被清洗，被清洗的數(shù)據(jù)規(guī)模在不同和G下是相同的。更高的G可能顯著地增加尺寸。但更小的G可能導(dǎo)致更多的漏讀，而影響漏讀推斷準(zhǔn)確率。因此，根據(jù)滑動窗口調(diào)整G為更小值，且調(diào)整為合適的值。

1—未清洗數(shù)據(jù)；2—清洗數(shù)據(jù)

圖10所示為不同的數(shù)據(jù)規(guī)模，參數(shù)為=0.1，G=0.5。根據(jù)對象數(shù)量(1 000，2 500，5 000，7 500，10 000)分別生成數(shù)據(jù)進(jìn)入表，對應(yīng)的路徑長度分別為(3?4)，(3?7)，(3?9)，(3?17)，(3?22) (每500個對象有相同的路徑長度)。由于G=0.5和長路徑可能導(dǎo)致更多的冗余數(shù)據(jù)，沒有清洗過的數(shù)據(jù)規(guī)模明顯地大于被清洗過的數(shù)據(jù)規(guī)模。生成的數(shù)據(jù)將進(jìn)入表，和。由于表只存儲單一對象對應(yīng)元組的一系列完整路徑序列(一一對應(yīng)中的對象)，表只存儲在2個可調(diào)整的時間間隔的位置，表只存儲基于有向圖的有限路徑，因此，用戶可以通過查詢更小尺寸的表，有效地獲取對象的完整路徑。

1—未清洗數(shù)據(jù)；2—清洗數(shù)據(jù)；3—路徑數(shù)據(jù)

文獻(xiàn)[17]給出的最小路徑為3，最大路徑為9?？紤]循環(huán)和長路徑問題，延長了最大路徑長度到17或22。一般地，大多數(shù)路徑長度為3~9，特別是3~6。本文設(shè)置5個系列的路徑長度：3~4(每5 000個對象有相同路徑長度)；3~7(每2 000個對象有相同路徑長度)；3~9(每1 500個對象有相同路徑長度，第9層為1 000個對象有相同路徑長度)；3~17(從第3層到第9層每1 300個對象有相同路徑長度，從第10層到第17層每90個對象有相同路徑長度)；3~22(從第3層到第9層每1 300個對象有相同路徑長度，從第10層到第22層每90個對象有相同路徑長度)。不同的數(shù)據(jù)規(guī)模(=10 000,=3 600,A=3,=0.1,G=0.5)如圖11所示。由圖11可知：沒有清洗的和清洗過的數(shù)據(jù)規(guī)模在路徑長度增加時顯著增加，而路徑數(shù)據(jù)規(guī)模隨路徑長度增加稍微增長。表明更長的路徑會顯著地影響數(shù)據(jù)規(guī)模，但對路徑數(shù)據(jù)規(guī)模影響不大。

1—未清洗數(shù)據(jù)；2—清洗數(shù)據(jù)；3—路徑數(shù)據(jù)

考慮到對象在很短的時間內(nèi)不可能從一個位置移動到另一個較遠(yuǎn)的位置，因此，每一個位置將對應(yīng)一個合適的時間間隔，如時間間隔=60對應(yīng)于位置間隔A=2。不同的和的數(shù)據(jù)規(guī)模(=10 000,=3?22,=0.1,G=0.5)如圖12所示。由圖12可知：路徑數(shù)據(jù)規(guī)模隨和A的增加而減少(被清洗數(shù)據(jù)的規(guī)模不隨和A的改變而改變)。路徑數(shù)據(jù)規(guī)模的減少對降低路徑查詢的負(fù)載是非常有效的。

1—未清洗數(shù)據(jù)；2—清洗數(shù)據(jù)

2.3 查詢

由于沒有清洗過的數(shù)據(jù)不適合于進(jìn)行查詢評價，本文采用算法清洗數(shù)據(jù)和聚集，并給定查詢進(jìn)行比較。Q1為跟蹤查詢，Q2，Q3，Q6和Q7為追蹤查詢。其中Q4和Q5為聚集查詢，Q6為非完整性數(shù)據(jù)查詢，Q7為循環(huán)和長路徑查詢。

表2 測試查詢

在表中存儲對象EPC及其路徑序列，Q1和Q2不需要連接多個表去獲取路徑信息。盡管Q3需要連接2個表去獲取路徑信息，但存儲時間間隔和位置信息的表已經(jīng)被顯著地壓縮。聚集查詢Q4和Q5需要連接2個表，但相當(dāng)多的類似數(shù)據(jù)也通過聚集壓縮，也能顯著地改善查詢性能。由于查詢假貨涉及到表,和，Q6連接這3個表區(qū)分非克隆假貨和克隆假貨。循環(huán)和長路徑查詢也涉及表，和，Q7需要連接這3個表獲取細(xì)節(jié)的路徑信息。

不同分組的執(zhí)行情況如圖13所示，參數(shù)為= 10 000，=3?22，=3 600，A=3。由圖13可知：方法在Q3~Q7的執(zhí)行時間隨著分組的增加而減少。這是因為Q1和Q2只需要查詢表獲取路徑信息，因而Q1和Q2的執(zhí)行時間沒有改變。Q3的執(zhí)行時間隨的增加而減少，這是因為更大的分組可以顯著地壓縮以獲取路徑信息。盡管Q4和Q5需要連接2個表進(jìn)行聚集，隨著的增加，在參數(shù)=3 600和A=3條件下的壓縮比也顯著地增加。類似地，Q6和Q7需要連接3個表(,和)去追蹤假貨和具有循環(huán)和長路徑的對象，壓縮比隨著的增加而增加。

1—Q1；2—Q2；3—Q3；4—Q4；5—Q5；6—Q6；7—Q7

Q1~Q7在不同數(shù)據(jù)規(guī)模時的評價如圖14所示，測試參數(shù)=200，=3~22，=3 600，A=3。數(shù)據(jù)規(guī)模顯著地影響Q3~Q7的執(zhí)行時間。由于Q3~Q7需要連接多個表，其執(zhí)行時間隨的增加而顯著增加。而Q1和Q2只查詢表，數(shù)據(jù)規(guī)模的變化對其執(zhí)行時間影響很小。

1—Q1；2—Q2；3—Q3；4—Q4；5—Q5；6—Q6；7—Q7

由于RFID閱讀器是在連續(xù)的時間段內(nèi)而不是相同的時間戳讀取對象標(biāo)簽，聚集時間間隔和位置，忽略了具體的時間戳和位置，可以顯著地改善存儲和查詢的有效性。圖15所示為在不同聚集層次下的查詢執(zhí)行時間。本文設(shè)置4組不同的聚集層次：Ⅰ組(=0,A=1)，Ⅱ組(=60,A=2)，Ⅲ組(=3 600,A=3)，Ⅳ組(=21 600,A=4)，由這4組聚集層次評價查詢Q1~Q7。其中，Ⅰ組(=0,A=1)是沒有聚集的，因而對Q3~Q7是無效的。隨著聚集時間間隔和位置間隔的延長，Q3~Q7的執(zhí)行時間顯著減少。

1—Q1；2—Q2；3—Q3；4—Q4；5—Q5；6—Q6；7—Q7

一般的路徑長度為3?9[17]，因此，考慮大部分對象的路徑長度為3?9，設(shè)置了4組不同的路徑長度1=3~5，2=3~9，3=3~17，4=3~22來評價Q1~Q7。若路徑長度超過9，則實驗設(shè)置10%的對象的路徑長度為10~22 (每個長度的對象數(shù)量相對平均)，設(shè)置90%的對象的路徑長度為3~9(每個長度的對象數(shù)量相對平均)。圖16所示為Q3~Q7在不同路徑長度的執(zhí)行時間。由圖16可見：Q3~Q7的執(zhí)行時間隨著路徑長度的增加而顯著增加。這是因為短路徑包含大量可以被壓縮的相同路徑信息，而長路徑包含大量難以壓縮的不同路徑信息。由于具有路徑長度10~22的對象較少，執(zhí)行時間的增幅趨緩。

1—Q1；2—Q2；3—Q3；4—Q4；5—Q5；6—Q6；7—Q7

在以上實驗中，Q6和Q7的執(zhí)行時間較長，但由于這2類查詢相對較少，因此，查詢性能也是可以接受的。

3 結(jié)論

1) 考慮了所有類型的非確定性數(shù)據(jù)，通過分析RFID對象的關(guān)鍵特征，根據(jù)漏讀與多讀、冗余和非一致性數(shù)據(jù)的比例來調(diào)整滑動窗口；提出了一種非確定性數(shù)據(jù)處理方法，采用不同策略處理漏讀、多讀、冗余、非一致性和非完整性(假貨與對象被偷)數(shù)據(jù)，并根據(jù)對象在供應(yīng)鏈中出現(xiàn)位置及其連續(xù)性來識別多讀、漏讀和非完整數(shù)據(jù)。

2) 處理后的數(shù)據(jù)在不同參數(shù)條件下具有良好的清洗效果、存儲效率以及查詢性能，能有效地支持對象路徑查詢。

3) 下一步的工作將建立對象移動的主路徑和子路徑，進(jìn)一步壓縮數(shù)據(jù)來提高存儲和查詢性能。

[1] Ilic A, Andersen T, Michahelles F. Increasing supply-chain visibility with rule-based RFID data analysis[J]. IEEE Internet Computing, 2009, 13(1): 31?38.

[2] WANG Fusheng, LIU Shaorong. Temporal management of RFID data[C]// Proceedings of the International Conference on Very Large Data Bases. New York: Association for Computing Machinery, 2005: 1128?1139.

[3] WANG Fusheng, LIU Shaorong, LIU Peiya. A temporal RFID data model for querying physical objects[J]. Pervasive and Mobile Computing, 2010, 6(3): 382?397.

[4] Rizvi S, Jeffery S R, Krishnamurthy S, et al. Events on the edge[C]// Proceedings of the International Conference on Management of Data. New York: Association for Computing Machinery, 2005: 885?887.

[5] Jeffery S R, Garofalakis M, Franklin M J. Adaptive cleaning for RFID data streams[C]// Proceedings of the International Conference on Very Large Databases. New York: Association for Computing Machinery, 2006: 163?174.

[6] 谷峪, 于戈, 胡小龍, 等. 基于監(jiān)控對象動態(tài)聚簇的高效RFID數(shù)據(jù)清洗模型[J]. 軟件學(xué)報, 2010, 21(4): 632?643. GU Yu, YU Ge, HU Xiaolong, et al. Efficient RFID data cleaning model based on dynamic clusters of monitored objects[J]. Journal of Software, 2010, 21(4): 632?643.

[7] 王永利, 錢江波, 孫淑榮, 等. AMUR: 一種RFID數(shù)據(jù)不確定性的自適應(yīng)度量算法[J]. 電子學(xué)報, 2011, 39(3): 579?584. WANG Yongli, QIAN Jiangbo, SUN Shurong, et al. AMUR: An adaptive measuring algorithm of underlying uncertainty for RFID data [J]. Acta Electronica Sinica, 2011, 39(3): 579?584.

[8] Tran T T L, Peng L P, DIAO Yalei, et al. CLARO: Modeling and processing uncertain data streams[J]. The VLDB Journal, 2012, 21 (5):651-676.

[9] NIE Yanming, Cocci R, ZHAO Cao, et al. SPIRE: Efficient data inference and compression over RFID streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(1): 141?155.

[10] ZHOU Aoying, JIN Cheqing, WANG Guoren, et al. A survey on the management of uncertain data[J]. Chinese Journal of Computers, 2009, 32(1): 1?16.

[11] LIAN Xiang, CHEN Lei, SONG Shaoxu. Consistent query answers in inconsistent probabilistic databases[C]// Proceedings of the International Conference on Management of Data. New York: Association for Computing Machinery, 2010: 303?314.

[12] Arenas M, Bertossi L, Chomicki J. Consistent query answers in inconsistent databases[C]// Proceedings of the Symposium on Principles of Database Systems, 1999: 68?79.

[13] Chen L, Tseng M, Lian X. Development of foundation models for internet of things[J]. Frontiers of Computer Science in China, 2010, 4(3): 376?385.

[14] 謝東. 非確定性關(guān)系數(shù)據(jù)處理研究[R]. 長沙: 中南大學(xué)信息科學(xué)與工程學(xué)院, 2010: 30?55. XIE Dong. Research on uncertain relational data processing[R]. Changsha: Central South University. School of Information Science and Engineering, 2010: 30?55.

[15] XIE Dong, CHEN Xinbo, ZHU Yan. Tackling polytype queries in inconsistent databases: theory and algorithm[J]. Journal of Software, 2012, 7(8): 1861?1866.

[16] XIE Dong, Sheng Q Z, MA Jian-gang. A temporal-based model of uncertain RFID data[C]// Proceedings of the International Conference on Computer Science & Education. New York: Association for Computing Machinery, 2012: 847?850.

[17] Bowersox D J, Closs D J. Logistical management[M]. New York: McGraw-Hill, 1996: 55?80.

Methods for processing uncertain RFID data in traceability supply chains

XIE Dong1, 2, XIAO Jie3, GUO Guangjun4, JIANG Tong1

(1. Department of Computer Science and Technology, Hunan University of Humanities, Science and Technology, Loudi 417000, China; 2. School of Information Science and Engineering, Central South University, Changsha 410083, China; 3. Information Technology Department, Hunan First Normal College, Changsha 410205, China;4. Department of Electronics and Information Engineering, Loudi Vocational and Technical College, Loudi 417000, China)

Considering that massive uncertain radio frequency identification (RFID) data cannot be efficiently processed in application systems of traceability supply chains, key features of RFID applications were analyzed, and different smoothing windows were adjusted according to different rates of uncertain data. Different types of uncertain readings were obtained by employing different strategies, and the methods for efficiently and effectively processing various types of uncertain data were put forward. The methods distinguish between ghost, missing and incomplete data according to their appearing positions and their continuities in supply chains. The processing algorithms that are suitable to group and independent moving of objects were proposed based on the directed graph, which corresponds to moving paths of

objects in logistics nodes. The results show that the proposed methods provide good cleaning effects, storage efficiencies, and query performances, and also efficiently support path-oriented queries of objects under different parameters.

supply chain management; radio frequency identification (RFID); uncertain data

10.11817/j.issn.1672-7207.2015.05.017

TP311

A

1672?7207(2015)05?1688?11

2014?05?14；

2014?07?20

湖南省自然科學(xué)基金資助項目(12JJ3057)；湖南省重點建設(shè)學(xué)科(計算機應(yīng)用技術(shù))資助項目(2011?2015)；湖南省科技計劃項目(2013NK3090)；湖南省教育廳科研基金資助項目(13A046) (Project(12JJ3057) supported by the Hunan Provincial Natural Science Foundation; Project(2011?2015) supported by the Construct Program of the Key Discipline “Computer Application Technology” in Hunan Province; Project(2013NK3090) supported by the Hunan Provincial Science and Technology Plan; Project(13A046) supported by the Research Foundation of Education Committee of Hunan Province)

謝東，博士，副教授，從事物聯(lián)網(wǎng)與數(shù)據(jù)管理研究；E-mail: dong.xie@hotmail.com

(編輯 趙俊)