支持RFID供應鏈路徑追溯查詢的偏增向量編碼策略

廖國瓊 楊樂川 張海艷 楊仙佩

(江西財經大學信息管理學院 南昌 330013)

無線射頻識別(radio frequency identification, RFID)技術是一種非接觸性自動識別技術[1].由于具有無需人工干預、批量識別等優點[2-3]，該技術已廣泛應用于供應鏈、圖書館、交通等領域，以實現對物品的全程跟蹤及監控.但如何對物品在流通過程中產生的海量信息進行編碼以支持路徑追溯查詢，是基于RFID供應鏈系統面臨的主要挑戰[4-6].

通常，衡量一個編碼策略性能指標主要有查詢效率、更新開銷及存儲開銷等[7].然而，供應鏈環境中路徑編碼還應考慮3個問題：

1) 環路問題.物品在供應鏈中流通時，可能多次經過同一地點，即在路徑中出現環路.例如，在路徑A→B→A中，物品2次經過地點A.因此，良好的路徑編碼策略應能對環路進行描述.

2) 實時更新問題.為滿足實時查詢需求，編碼策略應能及時將來自RFID讀寫器的原始數據轉化成編碼數據，即能對位置信息進行實時更新，實現隨到隨編.

3) 溢出問題.海量RFID數據會導致編碼的碼值超出規定數據類型的表示范圍，稱為溢出現象.一個好的編碼策略應能減緩碼值的增長速率.

RFID供應鏈中物品最初提出的路徑編碼方法為素數編碼[8-9]，即對路徑中結點分配唯一素數，并利用素數乘積因式分解唯一的特性進行解碼.素數編碼在查詢方面具有較高效率，但其不能解決環路問題，且面對海量RFID數據時，素數增長過快，碼值容易溢出.為解決單一編碼的不足，文獻[10]提出了一種素數編碼與區間編碼相結合的復合編碼(composite coding, CC)策略，即對路徑的位置信息采用素數編碼，時間信息采用區間編碼[11-12]，并針對溢出問題提供了路徑分裂方法，能滿足路徑查詢需求，但此方法不能描述環路，且更新代價較大，不利于實時更新.

針對環路問題，文獻[13]提供了一種在素數編碼下描述環路的方法，其主要思想為將環路中重復的位置給予相同的素數，在計算同余值時按結點重復次數以冪次進行計算區分.此方法有效地編碼了環路，但增加了同余值計算復雜度，且未考慮時間信息.文獻[14]提出一種改進的素數編碼方法，位置信息編碼充分利用值較小的素數，時間信息編碼則利用可持久的區間編碼(durable region based numbering, DRB)方法編碼，能減緩素數溢出，但減緩程度有限，且解碼時耗較大，影響查詢效率.文獻[15]提出了一種路徑分裂策略對路徑編碼樹進行分裂，但查詢會涉及多張表，導致查詢開銷增加.

RFID供應鏈系統還有一類針對減少存儲空間的壓縮編碼策略，如pid編碼[16]和基于T樹的路徑壓縮策略[17].類似前綴編碼，pid編碼存儲會產生較大冗余.基于T樹的策略不涉及具體編碼，而是用T樹來構造編碼樹提升查詢效率，但此方法在構建樹的過程中開銷較大.

綜上所述，已有RFID對象路徑編碼方法都只適用于一定場合，不能完全解決供應鏈環境路徑編碼的環路、實時更新及溢出等問題.

向量編碼(vector coding)是針對XML文檔提出的一種層次編碼方法[18]，該編碼基于2個向量之間可以無限插入向量的思想對一個對象分配一對向量，具有較高的查詢效率和更新效率.但向量編碼的碼值是基于區間編碼產生的，即先對結點進行區間編碼，然后再將區間轉化成向量進行編碼，不能隨到隨編，實現實時更新.而且，不能解決海量RFID數據導致的碼值溢出現象.

本文將在原始向量編碼基礎上，研究一種偏增向量編碼(offset addition vector coding, OAVC)策略及優化策略.該策略可直接對RFID對象的時空信息進行向量編碼，可有效提高編碼效率，且在綜合考慮查詢效率、更新效率及支持環路、溢出等方面具有較好性能.

1 供應鏈下RFID路徑表示及編碼框架

附有RFID標簽的物品在供應鏈上流通時，會被不同位置的閱讀器識別，生成形如(TagID，Loc，Time)形式的原始數據流，其中TagID是標簽對象的唯一標識，Loc和Time分別表示識別地點及時間.圖1是來自不同閱讀器48條未加工原始數據樣例.

通常，RFID讀寫器會以固定周期掃描其探測區域內RFID標簽對象，因此同一個標簽對象可能被同一讀寫器掃描多次，故原始數據中存在大量冗余信息.實際上，我們只需記錄標簽在某位置的進入時間和離開時間，即將同一個標簽對象在同一個位置的多條原始數據轉換成1條數據存儲，即TagID:Loc[ST,ET]，其中ST表示TagID對象進入位置Loc的時間，ET表示TagID離開Loc的時間.

Fig.1 RFID raw data record圖1 RFID原始數據記錄

圖2(a)是圖1中48條原始數據轉換后的數據.可以看出，每條數據可描述某物品在某位置的停留時間.例如Tag1:B[4,6]表示標簽對象Tag1在時刻4進入位置B，時刻6離開，故Tag1在位置B的停留時間為2.

為便于查詢，我們在轉換后的數據中再添加1個層級屬性l，用于描述對象在移動路徑中的位置序號.例如Tag1:B[4,6,2]表示B是Tag1路徑中第2個經過的位置.

于是，我們將屬于同一標簽對象的數據進行組合，即可得到形如TagID：L1[ST1,ET1,l1]→L2[ST2,ET2,l2]→…→Ln[STn,ETn,ln]的路徑信息，如圖2(b)所示.

Fig.2 RFID data after processing圖2 加工后的RFID數據

我們將包含時間和位置信息的每個路徑結點Loc(ST,ET,l)稱為時空數據結點，并以此為編碼對象進行編碼，以支持路徑追溯查詢.本文采用的編碼框架如圖3所示：

Fig.3 Framework of RFID path coding圖3 RFID路徑編碼框架

首先，各RFID讀寫器將原始數據上傳給中央服務器.然后，中央服務器對數據進行轉化處理，并對每條時空信息進行編碼.最后，將每個物品對象，按經過的位置順序生成各自路徑信息，且將每條路徑中結點的編碼根據時空順序形成路徑樹，以表的形式存入數據庫供應用層查詢.

2 偏增向量編碼策略

本節將在文獻[18]所提出的向量編碼上研究一種能支持追溯查詢且溢出速率較低的偏增向量編碼策略.

2.1 基本向量編碼

偏增向量編碼仍采用平面直角坐標系中的第一象限中的向量進行編碼.該方法跳過基本向量編碼中的區間轉化的過程，直接根據結點進入順序按更新規則得到向量編碼.

對于向量編碼，有如下定義及定理[18]：

定義1.一個向量V可表示為平面直角坐標系第一象限中的1個坐標(x,y)，其中x,y都為整數，如圖4(a)所示.

定義2.對于任意2個向量V1(x1,y1)，V2(x2,y2)和1個標量r，則有：

V1+V2=(x1+x2,y1+y2)，

(1)

r×V1=(r×x1,r×y1).

(2)

定義3.設G(V)為向量V(x,y)的傾斜度，則可表示為G(V)=y/x，即圖4(a)中的tanθ.

Fig.4 Vector diagram圖4 向量示意圖

定義4.設GS(V)為向量V(x,y)的粒度，則可表示為GS(V)=x+y.

定理1.給定2個向量V1(x1,y1)和V2(x2,y2)，若y1x2>x1y2，則G(V1)>G(V2).

定理2.給定2個向量V1和V2,若V3=V1+V2且G(V1)>G(V2)，則G(V1)>G(V3)>G(V2).

定理3.給定2個向量V1和V2,則一定存在無數個向量，其傾斜度都在G(V1)和G(V2)之間.

根據定理2和定理3，如圖4(b)，向量2V1+V2，V1+V2，V1+2V2都會在向量V1和V2之間.

因此，可以根據結點位置不同，選擇(V1+V2,V1+2V2)或(2V1+V2,V1+V2)進行編碼.因在V1和V2之間可以反復進行向量加法運算，得到無數個不重復向量，故結點更新變得容易.

2.2 偏增向量編碼原理

基于上述原理，給出偏增向量編碼(OAVC)策略的基本規則:

規則2.路徑編碼樹的根定義為虛結點，其碼值固定為((1,0)(0,1),0).

編碼結點按其更新位置分為4類：無兄弟結點、僅有左兄弟結點、僅有右兄弟結點、既有左兄弟結點又有右兄弟結點.根據其位置不同，確定合適的偏置向量進行編碼.

規則3.設編碼結點n，其層級為l，p是其親代結點，cps是最鄰近n的左兄弟結點，cfs是最鄰近n的右兄弟結點，v1和v2為n的偏置向量，則有4種情形：

為盡可能減小碼值，應考慮v1,v2的粒度大小以決定最后的碼值，因此有規則4：

規則4.若GS(v1)>GS(v2),則其編碼為((v1+v2,v1+2v2),l)；反之，則為((2v1+v2,v1+v2),l).

為了判別結點之間子親代關系，有定理4.

在編碼時，若數據全部按時間先后順序,每個結點的ST值從小到大進入服務器，同層級自左向右編碼，則只需進行規則3的情形1)2)編碼.然而，各地閱讀器由于距離與速度等原因，到達中央服務器的時間會不一樣.因此，當到達順序發生錯亂時，可用規則3的情形3)4)調整順序.這樣做的好處在于：一方面能做到任意時刻任意位置進行實時更新；另一方面能保證整棵編碼樹完全按時間先后順序排列，在進行基于時間的查詢時提高查詢效率.

Fig.5 Coding tree of offset addition vectors圖5 偏增向量編碼樹

通過編碼樹的生成過程可以知道，偏增向量編碼的本質是在一定角度內無限地劃分角度來表示結點，其思想與區間編碼劃分區間來表示結點十分類似.但是，區間編碼通常是整數區間，需等待數據到達后再進行編碼，否則會因整數不可再分而出現大面積更新.而偏增向量編碼結點更新時不會影響其他結點，可做到隨到隨編，滿足實時更新及查詢需求.

同時，偏增向量編碼的對象是時空數據結點，環路問題也能得以解決，因為環路的本質是物品經過同一位置多次.我們可以用編碼中的時間信息區分同一位置的每一次經過.例如圖5中路徑A[1,2]→B[5,6]→A[7,9]，A[1,2]與A[7,9]表示2個不同結點，因為它們經過A的時間不同.

然而，偏增向量編碼是通過向量相加的形式得到新結點的編碼，碼值增長較快.對于海量RFID數據，可能會導致碼值溢出，故需進行優化.

2.3 向量碼值優化

Fig.6 The coded graph in different slope order圖6 不同斜率順序排列下編碼示意圖

根據上述優化思想，可得優化偏增向量編碼(optimized offset addition vector coding, OOAVC)算法如算法1所示.

算法1.優化偏增向量編碼算法.

輸入：結點n其父結點、最近鄰左、右兄弟結點的編碼p，cps，cfs；

輸出：結點n的編碼code.

②flag=0; /*斜率如圖6(a)所示排列*/

③ ifn有左兄弟結點

⑤ else

⑦ end if

⑧ ifn有右兄弟結點

⑩ else

根據優化后的算法可以得到新的編碼樹如圖7所示，圖7中結點X的碼值為(4,11),(5,14),2，結點Y的碼值為(5,12),(7,17),2.

Fig.7 OOAVC coding tree圖7 OOAVC編碼樹

從結果上對比可以看出，OOAVC相比于OAVC，親兄弟結點中首個結點碼值會略微偏大，但其后所有兄弟結點的碼值都會偏小.

2.4 優化偏增向量編碼親子代關系證明

證明.

由1)2)可得：

又由定理2得,G(v1)

因2v1+v2=(v1+v2)+v1,得G(v1)

因v1+2v2=(v1+v2)+v2,得G(v1+v2)

綜上，優化偏增向量編碼仍滿足親子關系.

證畢.

3 路徑追溯查詢

3.1 存儲模式

為了便于查詢，我們將路徑樹轉化3個數據庫中的表進行存儲.

1) 標簽表(tag table).存儲標簽號(TagID)及路徑編號(PathID)，以方便查詢物品所在路徑,如表1所示：

Table 1 Tag Table表1 標簽表

2) 路徑表(path table).存儲路徑編號及該路徑當前末尾結點的編碼((VSx,VSy),(VEx,VEy))，用于根據子親代判斷定理確定整條路徑,如表2所示.

3) 時間表(time table).存儲編碼值以及結點時空信息，其中((VSx,VSy),(VEx,VEy),Level)表示編碼，Loc(ST,ET)表示時空信息,如表3所示.

為提高查詢和更新效率，在進行路徑查詢或更新時，我們將從表3提取數據構建編碼樹到內存中，再結合表1～2信息(也存放在內存)進行查詢.

Table 2 Path Table表2 路徑表

Table 3 Time Table表3 時間表

3.2 追溯查詢實現

供應鏈中的典型追溯查詢如表4所示，大致可分為3類：追蹤查詢如Q1、面向路徑查詢Q2和Q3、聚合查詢Q4～Q6，下面對其做具體說明.

Table 4 Query Classification Table表4 查詢分類表

1) 追蹤查詢

查詢某標簽的歷史路徑，包含訪問過的每個位置及進出時間.首先，在表1中找到對應的PathID，通過PathID確定末尾結點的碼值，然后從根結點出發，根據子親代判定定理查出整條路徑，詳見算法2.從算法2中我們可以看出，追蹤查詢效率的高低關鍵在于子親代判斷速度的快慢.

算法2.追蹤查詢.

輸入：標簽號TagID、編碼樹的根結點root;

輸出：TagID所經過的路徑P.

① 在標簽表中找到TagID對應的PathID；

② 在路徑表中找到PathID對應的編碼code；

③ for (i=0;root.child[i]的編碼!=code;

i++)

④ ifcode與root.child[i]滿足子親代判定

⑤ 將root.child[i]存入P；

⑥root=root.child[i];

⑦ end if

⑧ end for

⑨ ifP≠?

⑩ 將code代表的結點存入P;

2) 不含時間的面向路徑查詢

查詢訪問過某位置的標簽集合.此查詢需先確定位置信息匹配的結點，再根據結點找到路徑和標簽號，詳見算法3.

算法3.面向路徑查詢(不含時間).

輸入：位置loc、編碼樹的根結點root；

輸出：查詢到的標簽集合T.

① 從root遍歷樹：

② if 結點曾訪問過loc

③ 將結點的編碼存進codelist中;

④ end if

⑤ 遍歷路徑表，找到PathID對應的code：

⑥ ifcode在codelist里

⑦ 將對應的PathID存進Plist中;

⑧ end if

⑨ 遍歷標簽表，對TagID對應的PathID：

⑩ ifPathID在Plist里：

從算法3可知，面向路徑的查詢牽涉到多張表的完全遍歷，因此較于追蹤查詢開銷較大.其次，面向路徑的查詢效率同樣與子親代關系判斷速度有關，且因查詢的只是位置信息，所以也與編碼信息有關.

3) 含時間的面向路徑查詢

與算法3類似，在輸入時增加進入時間和離開時間約束，在算法3的行②增加時間約束即可.因增加了約束，查詢時比較次數會提高，開銷增大.同時因查詢的不是單一信息，而是時空信息，單獨編碼位置的方法會不適用.

4) 聚合查詢

聚合查詢是比前3類查詢更為復雜的查詢，其查詢的條件比較多，且通常需要在查詢結果的基礎上添加聚合函數.

算法4.聚合查詢.

輸入：編碼樹的根結點root、查詢條件condi、聚合函數aggfunc;

輸出：最后的查詢結果Q.

① 從root遍歷樹：

② if 結點滿足查詢條件condi

③ 搜索相關表，查詢結點對應的記錄;

④ 將記錄存進Qlist中;

⑤ end if

⑥Q=aggfunc(Qlist);

⑦ 返回Q.

4 編碼實驗與結果分析

4.1 實驗目的

本實驗將從2個方面進行實驗.

1) 將所提出的偏增向量編碼及優化策略OAVC,OOAVC與3種近年來RFID路徑編碼方法對時空數據進行編碼，比較查詢開銷、更新開銷、初始編碼時間開銷、最大編碼值等.選用的對比編碼策略為：

① 區間編碼(region coding, RC).該編碼利用先序遍歷的方法，給每一個結點分配2個值，從根結點出發編碼第1個值，編碼孩子結點后回到孩子結點編碼第2個值.2個碼值如同區間的左右，若有結點的碼值在區間范圍內，則為其孩子結點.

② 素數編碼(prime coding, PC).該編碼給每個結點分配唯一的素數，利用素數積因式分解唯一性進行子親代判斷.

③ 復合編碼(composite coding, CC).該編碼利用區間編碼對時空數據結點進行編碼，同時針對位置信息單獨再用素數編碼建立不含時間的位置路徑樹.對不同查詢，靈活運用2棵樹信息進行查詢.

2) 比較OAVC和OOAVC的最大編碼值，分析優化效果.

4.2 數據集

本實驗的數據集通過仿真實驗產生.我們構造一棵深度為M的滿N叉樹，將時空數據結點作為樹的結點，并按一定規律隨機賦值，在位置信息上允許路徑有重復的位置出現，即位置信息有環路.其中：M表示樹的層數(虛結點的孩子結點為第1層)，其含義為路徑長度的最大值，用來控制樹的深度；N代表每個結點的孩子數，以控制樹的寬度.

為分析樹的深度、寬度對不同編碼的影響，我們分別生成數據集D1～D6，如表5～6所示.其中，數據集D1～D3是固定N=5，只增加樹的深度(即3～5)生成；數據集D4～D6是固定M=4，只增加樹的寬度(即6～8)生成.

Table 5 Dataset Increases by the Depth of the Tree表5 數據集深度遞增

Fig.8 Query overhead on the D1～D6圖8 不同編碼在數據集D1～D6上的查詢開銷

Table 6 Dataset Increases by the Width of the Tree
表6 數據集寬度遞增

DatasetMNumber of NodesNumber of RecordsND441555528186D5428011059317D6446811520918

4.3 結果分析

1) 查詢開銷

我們對表4中每種查詢隨機生成查詢條件，在數據集D1～D6中分別重復實驗，計算平均時間，作為查詢開銷的評價指標.

圖8為各種編碼策略在數據集D1～D6中各類查詢的時耗圖，其中橫坐標為數據集類別，縱坐標為平均查詢時耗.

對于Q1而言，OOAVC和OAVC在判斷子親代關系時，由于一個編碼有4個值要比較，因此會略慢，但與其他編碼相差不大.

對于Q2，除復合編碼外，OOAVC和OAVC與其他編碼大致相同.而對于復合編碼，盡管其額外編碼了位置信息，相當于降低了搜索范圍，本應在此類查詢上占據優勢，但本實驗數據集在位置上存在環路，一個位置可能對應多個編碼，導致在解碼時要遍歷整張表，此外編碼與位置對應的表存在外存中，因此整體上表現最差，這也體現出環路問題會使只考慮位置信息編碼變得更為復雜.

對于Q3而言，查詢包含時間和空間信息，此時所有編碼的編碼對象都為時空數據結點，開銷主要影響因素為子親代判斷速度，OOAVC和OAVC盡管子親代判斷過程稍復雜，但查詢速度與其他編碼相差不大.可以發現，Q3整體開銷略高于Q2，這是因為每次查詢要多比較時間信息，從而開銷增大.

對于聚合查詢Q4,Q5涉及到時間信息，因此各編碼整體上與Q3結果類似，而Q6只涉及空間信息，結果與Q2類似.

綜合各類查詢上來看，素數編碼的效率最高，而OOAVC與OAVC盡管不占優勢，但差距并不大，能支持和滿足大多數查詢.

2) 更新開銷

同樣地，我們隨機選取樹中的某個結點，插入1個葉子結點作為其孩子并進行編碼，在數據集D1～D6中分別重復操作，計算平均更新開銷作為評價指標，結果如圖9所示:

Fig.9 Comparison of update cost of each encoding on D1～D6圖9 各編碼在數據集D1～D6上更新開銷比較

由圖9可看到，相比于區間、素數、復合編碼，所提出的2種偏增向量編碼更新開銷幾乎為零.區間編碼是因為編碼碼值都連續，沒有空位留給新插入的結點，1個結點的插入會導致大面積結點需要重新編碼.素數編碼是因為當編碼到一定大小時，搜索新的素數也需要花費時間，因此效率也偏低.復合編碼在查詢時繼承了2個編碼缺陷，更新開銷最大.

3) 初始編碼時間開銷

初始編碼時間開銷是指給定一棵樹結構，對其每個結點進行編碼所需要的時間.同樣，我們在數據集D1～D6中統計編碼平均時間作為評價指標，得到圖10所示:

Fig.10 Comparison of initial cost of each encoding on D1～D6圖10 各編碼在數據集D1～D6上初始編碼開銷比較

可以發現，OOAVC與OAVC的初始編碼開銷均較大程度優于其余策略.在數據集較小的情況如D1,D2,D4，區間編碼的開銷是要大于素數編碼的，但當數據集變大時，搜索新素數導致素數編碼開銷更大.同時，復合編碼由于有2棵樹需要編碼，開銷最大.

4) 最大編碼值

最大編碼值即為路徑編碼的最大值.對于OOAVC，OAVC，RC而言，路徑編碼用路徑中葉子結點的編碼來表示，最大編碼值即為結點編碼的最大值；對于PC，CC而言，路徑編碼由根結點到最后一個葉子結點編碼的乘積得到.

表2中存儲了每條路徑的路徑編碼，可直接從表2中找到最大的碼值.由于不同編碼的碼值差距過大，我們用編碼值的lb對數表示，結果如圖11所示.

由圖11我們可以看到，素數和復合編碼的最大編碼值已經遠遠超過了其他編碼的碼值.理論上，復合編碼的最大碼值應小于等于素數編碼，這取決于位置信息相同的路徑多少，而從圖11中看出，兩者最大編碼值相差并不大，說明都存在嚴重的溢出問題.

而通過觀察對比，在更深的樹如數據集D3上，最大碼值會比更寬的樹如數據集D5上更大，這也與素數的乘積增長極快相吻合.事實上，再在數據集D3上繼續提高深度或寬度，都已經會導致超出所定義的數據結構，導致溢出錯誤.

Fig.11 Maximum coded value of each encoding in dataset D1～D6圖11 各編碼在數據集D1～D6上最大編碼值

5) 碼值優化比較

為了更清晰地觀測不同編碼的碼值，我們將各類編碼具體的碼值表給出，如表7所示.我們可以發現，盡管同素數相比，向量編碼的碼值較小，但與區間編碼相比碼值增長同樣十分迅速，因此對OAVC的碼值進行優化是十分有必要的，可以發現，OOAVC碼值得到了一定減少，而當數據集逐漸變大時，優化的效果也更明顯.

同時，表7中素數編碼與復合編碼的最大編碼值相差有限，說明溢出問題仍是復合編碼的難點，而相較于復合編碼的最大編碼值，無論是OOAVC還是OAVC都要小得多.

綜合實驗結果，我們將各編碼策略整體表現歸納如表8所示.

Table 7 Table of Maximum Encoding Values表7 最大編碼值表

Table 8 Comparison of Comprehensive Performance of Each Code表8 各編碼綜合性能比較

可以看出，所提出的偏增向量編碼能較好地滿足各類追溯查詢要求，具有編碼速度較快、碼值溢出較為緩慢、更新效率高且支持環路的特點，因此是一種效率較高且具有強魯棒性的編碼策略.

5 總結及展望

本文根據基于RFID供應鏈環境中標簽對象路徑追溯查詢需求，提出了一種能支持環路、實時更新的偏增向量編碼策略.同時，對該編碼潛在的碼值溢出問題提出了優化方法，并對其正確性進行了證明.在模擬數據集上完成了實驗，結果表明：所提出的編碼策略能基本滿足大多數查詢需求，且具有健壯、強魯棒的特點，能較好地適應供應鏈復雜環境.

目前，已有編碼策略大多僅在集中式環境下使用，下一步擬研究分布式供應鏈向量編碼策略.