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

(江西財(cái)經(jīng)大學(xué)信息管理學(xué)院 南昌 330013)

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

通常，衡量一個(gè)編碼策略性能指標(biāo)主要有查詢效率、更新開銷及存儲(chǔ)開銷等[7].然而，供應(yīng)鏈環(huán)境中路徑編碼還應(yīng)考慮3個(gè)問題：

1) 環(huán)路問題.物品在供應(yīng)鏈中流通時(shí)，可能多次經(jīng)過同一地點(diǎn)，即在路徑中出現(xiàn)環(huán)路.例如，在路徑A→B→A中，物品2次經(jīng)過地點(diǎn)A.因此，良好的路徑編碼策略應(yīng)能對環(huán)路進(jìn)行描述.

2) 實(shí)時(shí)更新問題.為滿足實(shí)時(shí)查詢需求，編碼策略應(yīng)能及時(shí)將來自RFID讀寫器的原始數(shù)據(jù)轉(zhuǎn)化成編碼數(shù)據(jù)，即能對位置信息進(jìn)行實(shí)時(shí)更新，實(shí)現(xiàn)隨到隨編.

3) 溢出問題.海量RFID數(shù)據(jù)會(huì)導(dǎo)致編碼的碼值超出規(guī)定數(shù)據(jù)類型的表示范圍，稱為溢出現(xiàn)象.一個(gè)好的編碼策略應(yīng)能減緩碼值的增長速率.

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

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

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

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

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

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

1 供應(yīng)鏈下RFID路徑表示及編碼框架

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

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

Fig.1 RFID raw data record圖1 RFID原始數(shù)據(jù)記錄

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

為便于查詢，我們在轉(zhuǎn)換后的數(shù)據(jù)中再添加1個(gè)層級屬性l，用于描述對象在移動(dòng)路徑中的位置序號(hào).例如Tag1:B[4,6,2]表示B是Tag1路徑中第2個(gè)經(jīng)過的位置.

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

Fig.2 RFID data after processing圖2 加工后的RFID數(shù)據(jù)

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

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

首先，各RFID讀寫器將原始數(shù)據(jù)上傳給中央服務(wù)器.然后，中央服務(wù)器對數(shù)據(jù)進(jìn)行轉(zhuǎn)化處理，并對每條時(shí)空信息進(jìn)行編碼.最后，將每個(gè)物品對象，按經(jīng)過的位置順序生成各自路徑信息，且將每條路徑中結(jié)點(diǎn)的編碼根據(jù)時(shí)空順序形成路徑樹，以表的形式存入數(shù)據(jù)庫供應(yīng)用層查詢.

2 偏增向量編碼策略

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

2.1 基本向量編碼

偏增向量編碼仍采用平面直角坐標(biāo)系中的第一象限中的向量進(jìn)行編碼.該方法跳過基本向量編碼中的區(qū)間轉(zhuǎn)化的過程，直接根據(jù)結(jié)點(diǎn)進(jìn)入順序按更新規(guī)則得到向量編碼.

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

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

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

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

(1)

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

(2)

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

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

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

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

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

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

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

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

2.2 偏增向量編碼原理

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

規(guī)則2.路徑編碼樹的根定義為虛結(jié)點(diǎn)，其碼值固定為((1,0)(0,1),0).

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

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

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

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

為了判別結(jié)點(diǎn)之間子親代關(guān)系，有定理4.

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

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

通過編碼樹的生成過程可以知道，偏增向量編碼的本質(zhì)是在一定角度內(nèi)無限地劃分角度來表示結(jié)點(diǎn)，其思想與區(qū)間編碼劃分區(qū)間來表示結(jié)點(diǎn)十分類似.但是，區(qū)間編碼通常是整數(shù)區(qū)間，需等待數(shù)據(jù)到達(dá)后再進(jìn)行編碼，否則會(huì)因整數(shù)不可再分而出現(xiàn)大面積更新.而偏增向量編碼結(jié)點(diǎn)更新時(shí)不會(huì)影響其他結(jié)點(diǎn)，可做到隨到隨編，滿足實(shí)時(shí)更新及查詢需求.

同時(shí)，偏增向量編碼的對象是時(shí)空數(shù)據(jù)結(jié)點(diǎn)，環(huán)路問題也能得以解決，因?yàn)榄h(huán)路的本質(zhì)是物品經(jīng)過同一位置多次.我們可以用編碼中的時(shí)間信息區(qū)分同一位置的每一次經(jīng)過.例如圖5中路徑A[1,2]→B[5,6]→A[7,9]，A[1,2]與A[7,9]表示2個(gè)不同結(jié)點(diǎn)，因?yàn)樗鼈兘?jīng)過A的時(shí)間不同.

然而，偏增向量編碼是通過向量相加的形式得到新結(jié)點(diǎn)的編碼，碼值增長較快.對于海量RFID數(shù)據(jù)，可能會(huì)導(dǎo)致碼值溢出，故需進(jìn)行優(yōu)化.

2.3 向量碼值優(yōu)化

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

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

算法1.優(yōu)化偏增向量編碼算法.

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

輸出：結(jié)點(diǎn)n的編碼code.

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

③ ifn有左兄弟結(jié)點(diǎn)

⑤ else

⑦ end if

⑧ ifn有右兄弟結(jié)點(diǎn)

⑩ else

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

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

從結(jié)果上對比可以看出，OOAVC相比于OAVC，親兄弟結(jié)點(diǎn)中首個(gè)結(jié)點(diǎn)碼值會(huì)略微偏大，但其后所有兄弟結(jié)點(diǎn)的碼值都會(huì)偏小.

2.4 優(yōu)化偏增向量編碼親子代關(guān)系證明

證明.

由1)2)可得：

又由定理2得,G(v1)

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

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

綜上，優(yōu)化偏增向量編碼仍滿足親子關(guān)系.

證畢.

3 路徑追溯查詢

3.1 存儲(chǔ)模式

為了便于查詢，我們將路徑樹轉(zhuǎn)化3個(gè)數(shù)據(jù)庫中的表進(jìn)行存儲(chǔ).

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

Table 1 Tag Table表1 標(biāo)簽表

2) 路徑表(path table).存儲(chǔ)路徑編號(hào)及該路徑當(dāng)前末尾結(jié)點(diǎn)的編碼((VSx,VSy),(VEx,VEy))，用于根據(jù)子親代判斷定理確定整條路徑,如表2所示.

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

為提高查詢和更新效率，在進(jìn)行路徑查詢或更新時(shí)，我們將從表3提取數(shù)據(jù)構(gòu)建編碼樹到內(nèi)存中，再結(jié)合表1～2信息(也存放在內(nèi)存)進(jìn)行查詢.

Table 2 Path Table表2 路徑表

Table 3 Time Table表3 時(shí)間表

3.2 追溯查詢實(shí)現(xiàn)

供應(yīng)鏈中的典型追溯查詢?nèi)绫?所示，大致可分為3類：追蹤查詢?nèi)鏠1、面向路徑查詢Q2和Q3、聚合查詢Q4～Q6，下面對其做具體說明.

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

1) 追蹤查詢

查詢某標(biāo)簽的歷史路徑，包含訪問過的每個(gè)位置及進(jìn)出時(shí)間.首先，在表1中找到對應(yīng)的PathID，通過PathID確定末尾結(jié)點(diǎn)的碼值，然后從根結(jié)點(diǎn)出發(fā)，根據(jù)子親代判定定理查出整條路徑，詳見算法2.從算法2中我們可以看出，追蹤查詢效率的高低關(guān)鍵在于子親代判斷速度的快慢.

算法2.追蹤查詢.

輸入：標(biāo)簽號(hào)TagID、編碼樹的根結(jié)點(diǎn)root;

輸出：TagID所經(jīng)過的路徑P.

① 在標(biāo)簽表中找到TagID對應(yīng)的PathID；

② 在路徑表中找到PathID對應(yīng)的編碼code；

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

i++)

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

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

⑥r(nóng)oot=root.child[i];

⑦ end if

⑧ end for

⑨ ifP≠?

⑩ 將code代表的結(jié)點(diǎn)存入P;

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

查詢訪問過某位置的標(biāo)簽集合.此查詢需先確定位置信息匹配的結(jié)點(diǎn)，再根據(jù)結(jié)點(diǎn)找到路徑和標(biāo)簽號(hào)，詳見算法3.

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

輸入：位置loc、編碼樹的根結(jié)點(diǎn)root；

輸出：查詢到的標(biāo)簽集合T.

① 從root遍歷樹：

② if 結(jié)點(diǎn)曾訪問過loc

③ 將結(jié)點(diǎn)的編碼存進(jìn)codelist中;

④ end if

⑤ 遍歷路徑表，找到PathID對應(yīng)的code：

⑥ ifcode在codelist里

⑦ 將對應(yīng)的PathID存進(jìn)Plist中;

⑧ end if

⑨ 遍歷標(biāo)簽表，對TagID對應(yīng)的PathID：

⑩ ifPathID在Plist里：

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

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

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

4) 聚合查詢

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

算法4.聚合查詢.

輸入：編碼樹的根結(jié)點(diǎn)root、查詢條件condi、聚合函數(shù)aggfunc;

輸出：最后的查詢結(jié)果Q.

① 從root遍歷樹：

② if 結(jié)點(diǎn)滿足查詢條件condi

③ 搜索相關(guān)表，查詢結(jié)點(diǎn)對應(yīng)的記錄;

④ 將記錄存進(jìn)Qlist中;

⑤ end if

⑥Q=aggfunc(Qlist);

⑦ 返回Q.

4 編碼實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)?zāi)康?/h3>

本實(shí)驗(yàn)將從2個(gè)方面進(jìn)行實(shí)驗(yàn).

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

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

② 素?cái)?shù)編碼(prime coding, PC).該編碼給每個(gè)結(jié)點(diǎn)分配唯一的素?cái)?shù)，利用素?cái)?shù)積因式分解唯一性進(jìn)行子親代判斷.

③ 復(fù)合編碼(composite coding, CC).該編碼利用區(qū)間編碼對時(shí)空數(shù)據(jù)結(jié)點(diǎn)進(jìn)行編碼，同時(shí)針對位置信息單獨(dú)再用素?cái)?shù)編碼建立不含時(shí)間的位置路徑樹.對不同查詢，靈活運(yùn)用2棵樹信息進(jìn)行查詢.

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

4.2 數(shù)據(jù)集

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

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

Table 5 Dataset Increases by the Depth of the Tree表5 數(shù)據(jù)集深度遞增

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

Table 6 Dataset Increases by the Width of the Tree
表6 數(shù)據(jù)集寬度遞增

DatasetMNumber of NodesNumber of RecordsND441555528186D5428011059317D6446811520918

4.3 結(jié)果分析

1) 查詢開銷

我們對表4中每種查詢隨機(jī)生成查詢條件，在數(shù)據(jù)集D1～D6中分別重復(fù)實(shí)驗(yàn)，計(jì)算平均時(shí)間，作為查詢開銷的評價(jià)指標(biāo).

圖8為各種編碼策略在數(shù)據(jù)集D1～D6中各類查詢的時(shí)耗圖，其中橫坐標(biāo)為數(shù)據(jù)集類別，縱坐標(biāo)為平均查詢時(shí)耗.

對于Q1而言，OOAVC和OAVC在判斷子親代關(guān)系時(shí)，由于一個(gè)編碼有4個(gè)值要比較，因此會(huì)略慢，但與其他編碼相差不大.

對于Q2，除復(fù)合編碼外，OOAVC和OAVC與其他編碼大致相同.而對于復(fù)合編碼，盡管其額外編碼了位置信息，相當(dāng)于降低了搜索范圍，本應(yīng)在此類查詢上占據(jù)優(yōu)勢，但本實(shí)驗(yàn)數(shù)據(jù)集在位置上存在環(huán)路，一個(gè)位置可能對應(yīng)多個(gè)編碼，導(dǎo)致在解碼時(shí)要遍歷整張表，此外編碼與位置對應(yīng)的表存在外存中，因此整體上表現(xiàn)最差，這也體現(xiàn)出環(huán)路問題會(huì)使只考慮位置信息編碼變得更為復(fù)雜.

對于Q3而言，查詢包含時(shí)間和空間信息，此時(shí)所有編碼的編碼對象都為時(shí)空數(shù)據(jù)結(jié)點(diǎn)，開銷主要影響因素為子親代判斷速度，OOAVC和OAVC盡管子親代判斷過程稍復(fù)雜，但查詢速度與其他編碼相差不大.可以發(fā)現(xiàn)，Q3整體開銷略高于Q2，這是因?yàn)槊看尾樵円啾容^時(shí)間信息，從而開銷增大.

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

綜合各類查詢上來看，素?cái)?shù)編碼的效率最高，而OOAVC與OAVC盡管不占優(yōu)勢，但差距并不大，能支持和滿足大多數(shù)查詢.

2) 更新開銷

同樣地，我們隨機(jī)選取樹中的某個(gè)結(jié)點(diǎn)，插入1個(gè)葉子結(jié)點(diǎn)作為其孩子并進(jìn)行編碼，在數(shù)據(jù)集D1～D6中分別重復(fù)操作，計(jì)算平均更新開銷作為評價(jià)指標(biāo)，結(jié)果如圖9所示:

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

由圖9可看到，相比于區(qū)間、素?cái)?shù)、復(fù)合編碼，所提出的2種偏增向量編碼更新開銷幾乎為零.區(qū)間編碼是因?yàn)榫幋a碼值都連續(xù)，沒有空位留給新插入的結(jié)點(diǎn)，1個(gè)結(jié)點(diǎn)的插入會(huì)導(dǎo)致大面積結(jié)點(diǎn)需要重新編碼.素?cái)?shù)編碼是因?yàn)楫?dāng)編碼到一定大小時(shí)，搜索新的素?cái)?shù)也需要花費(fèi)時(shí)間，因此效率也偏低.復(fù)合編碼在查詢時(shí)繼承了2個(gè)編碼缺陷，更新開銷最大.

3) 初始編碼時(shí)間開銷

初始編碼時(shí)間開銷是指給定一棵樹結(jié)構(gòu)，對其每個(gè)結(jié)點(diǎn)進(jìn)行編碼所需要的時(shí)間.同樣，我們在數(shù)據(jù)集D1～D6中統(tǒng)計(jì)編碼平均時(shí)間作為評價(jià)指標(biāo)，得到圖10所示:

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

可以發(fā)現(xiàn)，OOAVC與OAVC的初始編碼開銷均較大程度優(yōu)于其余策略.在數(shù)據(jù)集較小的情況如D1,D2,D4，區(qū)間編碼的開銷是要大于素?cái)?shù)編碼的，但當(dāng)數(shù)據(jù)集變大時(shí)，搜索新素?cái)?shù)導(dǎo)致素?cái)?shù)編碼開銷更大.同時(shí)，復(fù)合編碼由于有2棵樹需要編碼，開銷最大.

4) 最大編碼值

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

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

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

而通過觀察對比，在更深的樹如數(shù)據(jù)集D3上，最大碼值會(huì)比更寬的樹如數(shù)據(jù)集D5上更大，這也與素?cái)?shù)的乘積增長極快相吻合.事實(shí)上，再在數(shù)據(jù)集D3上繼續(xù)提高深度或?qū)挾?，都已?jīng)會(huì)導(dǎo)致超出所定義的數(shù)據(jù)結(jié)構(gòu)，導(dǎo)致溢出錯(cuò)誤.

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

5) 碼值優(yōu)化比較

為了更清晰地觀測不同編碼的碼值，我們將各類編碼具體的碼值表給出，如表7所示.我們可以發(fā)現(xiàn)，盡管同素?cái)?shù)相比，向量編碼的碼值較小，但與區(qū)間編碼相比碼值增長同樣十分迅速，因此對OAVC的碼值進(jìn)行優(yōu)化是十分有必要的，可以發(fā)現(xiàn)，OOAVC碼值得到了一定減少，而當(dāng)數(shù)據(jù)集逐漸變大時(shí)，優(yōu)化的效果也更明顯.

同時(shí)，表7中素?cái)?shù)編碼與復(fù)合編碼的最大編碼值相差有限，說明溢出問題仍是復(fù)合編碼的難點(diǎn)，而相較于復(fù)合編碼的最大編碼值，無論是OOAVC還是OAVC都要小得多.

綜合實(shí)驗(yàn)結(jié)果，我們將各編碼策略整體表現(xiàn)歸納如表8所示.

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

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

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

5 總結(jié)及展望

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

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