面向供應(yīng)鏈追溯的RFID路徑編碼策略研究

楊樂川 楊仙佩 張海艷 廖國瓊 江西財經(jīng)大學(xué)信息管理學(xué)院

面向供應(yīng)鏈追溯的RFID路徑編碼策略研究

楊樂川 楊仙佩 張海艷 廖國瓊 江西財經(jīng)大學(xué)信息管理學(xué)院

隨著無線射頻技術(shù)(RFID)在供應(yīng)鏈領(lǐng)域的廣泛應(yīng)用，產(chǎn)生了海量的對象位置移動的路徑信息。如何對這些路徑信息進行有效編碼以支持路徑追溯查詢是RFID系統(tǒng)面臨的挑戰(zhàn)性問題。RFID路徑編碼策略主要分為素數(shù)編碼和復(fù)合編碼兩大類。素數(shù)編碼主要用于對路徑的位置信息進行編碼，復(fù)合編碼則是在素數(shù)編碼的基礎(chǔ)上，引入?yún)^(qū)間編碼對時間信息進行編碼，實現(xiàn)面向時間的路徑追溯。本文主要對RFID路徑編碼策略進行分析和討論，并指出未來研究方向。

RFID 供應(yīng)鏈 路徑編碼

1 引言

供應(yīng)鏈?zhǔn)侵府a(chǎn)品生產(chǎn)和流通過程中所涉及的原料供應(yīng)商、生產(chǎn)商、分銷商、零售商以及最終消費者等環(huán)節(jié)通過上下游成員連接組成的網(wǎng)絡(luò)結(jié)構(gòu)。由于供應(yīng)鏈中存在大量移動物品，故會產(chǎn)生海量路徑信息。而RFID技術(shù)擁有自動快速掃描、穿透性無屏障識別等特點，故RFID技術(shù)已廣泛應(yīng)用于供應(yīng)鏈物品跟蹤與監(jiān)控，可有效提高管理效率及降低運營成本。同時，RFID數(shù)據(jù)存儲與管理也逐漸成為一個研究熱點，如何對RFID路徑信息進行有效編碼以支持路徑追溯查詢是RFID系統(tǒng)面臨的挑戰(zhàn)性問題，近年來得到學(xué)者們的關(guān)注，并取得了一定研究成果。

通常，衡量一個編碼策略性能主要考慮因素包括：1)查詢效率。查詢速度要盡可能快，查詢響應(yīng)時間盡量要短；2)更新代價。更新代價指的是在對編碼樹進行插入、刪除結(jié)點時，對時間空間的開銷。好的編碼應(yīng)使各個結(jié)點要相互獨立，從而使得更新某一個結(jié)點時，對其他結(jié)點影響盡量少，且更新速度盡量快；3)存儲空間。存儲空間指的是編碼的碼值長度以及編碼表的硬盤存儲開銷。由于供應(yīng)鏈環(huán)境中的RFID數(shù)據(jù)具有其自身的特點，在進行編碼時，還需考慮以下特殊問題：

①環(huán)路問題。供應(yīng)鏈中的編碼對象多為位置信息，但商品在供應(yīng)鏈中流通時，可能經(jīng)過同一個位置多次，于是形成了環(huán)路，因此編碼應(yīng)考慮環(huán)路情況。

②溢出問題。RFID供應(yīng)鏈會產(chǎn)生海量的時空信息，對于編碼而言對應(yīng)的就會產(chǎn)生大量的結(jié)點。若編碼容量過小，則可能導(dǎo)致結(jié)點的碼值超出其規(guī)定的數(shù)據(jù)類型。因此，良好的編碼應(yīng)具有較大的編碼容量。

③實時更新問題。對象在供應(yīng)鏈環(huán)境中移動時，其路徑是實時產(chǎn)生的，因此良好的編碼策略應(yīng)能對路徑進行實時更新，隨到隨編。

本文將對已有RFID路徑編碼策略進行分析和討論，具體介紹其基本實現(xiàn)原理，并分析其優(yōu)缺點。

2 素數(shù)編碼

2.1 素數(shù)編碼基本原理

素數(shù)編碼（prime_label）是一種充分利用素數(shù)唯一性和獨立性的編碼方式，其具體編碼原理為：①在一棵編碼樹中自頂向下為每個結(jié)點指定唯一素數(shù)（self_label）；②每個結(jié)點的prime_label值為其父結(jié)點的prime_label值與self_label值的乘積（根結(jié)點的prime_label為1）；③用葉子結(jié)點的prime_label值作為該路徑的編碼值。

在素數(shù)編碼中，利用素數(shù)的特性引進了兩個定理：

定理1 算術(shù)基本定理。任何大于1的自然數(shù)都可以由有限個且唯一的素數(shù)相乘得到。

定理2 中國余數(shù)定理。假設(shè)存在n個素數(shù)a1,a2,…,an，則一定存在一個同余值SC使得SC mod a1=1, SC mod a2=2,…,SC mod an=n。

根據(jù)定理1，通過將一結(jié)點的prime_label因式分解得知到達該結(jié)點前經(jīng)過了哪些結(jié)點。根據(jù)定理2中的SC值，可以知道路徑所經(jīng)過結(jié)點的先后順序，因此可以利用素數(shù)對路徑進行編碼。

基于素數(shù)的路徑編碼存儲形式可記為（Element_enc，SC），其中Element_enc表示該路徑中所有位置對應(yīng)self_label的乘積（即一條路徑最后一個結(jié)點的prime_label值）,SC表示同余值，用于計算每個self_label對應(yīng)位置的次序。例如，在圖1中，三個位置A,B,C的self_label分別是2,3,5。可計算得到該路徑的Element_enc值為30，即2×3×5=30；SC順序編碼值為23：23mod2=1；23mod3=2；23mod5=3。通過這兩個值，可以還原出一條路徑經(jīng)過的所有結(jié)點及其順序。

圖1 素數(shù)編碼樣例

由于素數(shù)編碼具有唯一性和獨立性，因此更新較為簡單。但是，每次更新都需重新計算路徑每個結(jié)點的SC和Element_enc。在存儲方面，盡管存儲的是整數(shù)，但素數(shù)容易溢出，且不能表示環(huán)路。

2.2 溢出問題解決方案

當(dāng)供應(yīng)鏈中路徑過長時，素數(shù)的碼值和同余值的數(shù)據(jù)長度將超過其本身的數(shù)據(jù)類型長度，我們將這種問題稱為溢出問題。

假設(shè)存在一條路徑，其每個位置的self_label都使用最小素 數(shù) 來 編 碼：2-＞3-＞5-＞7-＞11-＞13-＞17-＞19-＞…-＞...， 在self_label僅為19的時候，即僅有8個位置長度的路徑時，其編碼值就達到了2×3×5×7×11×13×17×19=9699690。在實際供應(yīng)鏈中，路徑數(shù)量巨大，且起點與路徑總長度各不相同，實際編碼的長度將會更大。溢出問題主要以下有兩類方法。

2.2.1 利用小素數(shù)減緩溢出

文獻[9]在素數(shù)編碼基礎(chǔ)上充分利用小素數(shù)減緩編碼數(shù)據(jù)的增長速率。對于非葉子結(jié)點，它像素數(shù)編碼一樣，為每一個結(jié)點都分配一個素數(shù)，但不同之處于其素數(shù)分配算法優(yōu)先為根結(jié)點的孩子分配較小的素數(shù)，其他的結(jié)點依次分配除此之外的小素數(shù)。因為供應(yīng)鏈大批量物品運動時，越靠近根結(jié)點在路徑中會反復(fù)出現(xiàn)，從而在Element_enc中被反復(fù)計算，分配小素數(shù)給最頻繁計算的結(jié)點能使碼值整體偏小，減緩溢出。

對于葉子結(jié)點的編碼，使用2的倍數(shù)，且兄弟葉子結(jié)點的編碼是整除關(guān)系。這樣對葉子結(jié)點編碼，可以容易計算父結(jié)點的編碼及判斷兩條路徑有無共同子路徑，有利于追溯查詢和面向路徑查詢。在該編碼中，由于依次使用小素數(shù)，因此也省去了SC值的計算，用素數(shù)編碼計算出的素數(shù)，按大小排序便是每個結(jié)點在路徑中的順序。例如，在圖2中，編碼為3,5,7的結(jié)點全部分布在第一層，因為之后的路徑都要經(jīng)過這些位置，所以給他們分配了較小的素數(shù)，而結(jié)點F的編碼值為66=33×21，因為它是其親代的第一個葉子結(jié)點，所以分配2給它而不是23。同時，若一條路徑的編碼值為260，可將其分解為5,13,2,2。將除2以外數(shù)字從小到大排列可知其先后經(jīng)過了C,B；而有兩個2，代表再經(jīng)過了B的第二個孩子A，由此可推出路徑C-＞B-＞A。

圖2 小素數(shù)減緩溢出

2.2.2 路徑分裂法

為了解決素數(shù)的溢出問題，文獻[10]中提出了一種路徑分裂方法，其基本思想是規(guī)定一個最大長度MAX，當(dāng)路徑的Element_enc值超過了MAX值后，將一條長路徑分裂成幾個片段，使分裂后的路徑片段的Element_enc長度小于MAX值，從而將一條長路徑分割成多條較短路徑，從而緩解溢出問題。

如圖3(a)中路徑的Element_enc=2×3×5×7×11×13=30030。假定MAX=1000，2×3×5×7=210＜MAX；2×3×5×7×11=2310＞MAX。因此路徑從self_label=7的結(jié)點開始分裂，也就是D處，從而得出圖3(b)中的兩條路徑。

圖3 路徑分裂法減緩溢出

利用小素數(shù)的方法在一定程度上緩解了素數(shù)編碼的增長速率，但要做到給根結(jié)點的孩子分配較小的素數(shù)，需要等全部數(shù)據(jù)到達后再進行編碼，難以做到實時更新。雖然路徑分裂方法能較好地解決溢出問題，但由于每條路徑分裂的次數(shù)需計算得出，且可能各不相同，會增加存儲表的復(fù)雜度與不穩(wěn)定性，間接影響查詢效率，且當(dāng)路徑夠長時，單個結(jié)點的self_label有可能超出MAX值，導(dǎo)致一個結(jié)點一條分路徑，此時表的數(shù)據(jù)會更加冗余。

2.3 環(huán)路問題解決方法

設(shè) 物 體 經(jīng) 過 的 路 徑 為 L1-＞L2-＞…-＞Ln,若 存 在i,j(1＜=i＜=j＜=n)使得 Li=Lj，則說明路徑中至少存在一個環(huán)，我們稱此類路徑為帶環(huán)路徑，反之，稱為無環(huán)路徑。例如，存在 一 條 路 徑 A-＞B-＞C-＞A-＞C-＞A。可 以 看 出，L1=L4=L6，L3=L5，構(gòu)成了一個復(fù)雜的嵌套環(huán)路。由于素數(shù)編碼中相同位置的self_label相同，SC值無法計算，因此用原始的素數(shù)編碼無法描述環(huán)路問題。而供應(yīng)鏈中編碼樹結(jié)點的海量性，使得在編碼中不可避免會遇到環(huán)路問題。主要有以下兩種解決方法。

2.3.1 結(jié)點重命名

文獻[11]采用重新命名結(jié)方式解決供應(yīng)鏈中出現(xiàn)的環(huán)路問題，即將物體在不同時間到達的同一個結(jié)點看成是兩個不同的結(jié)點，以此來滿足各種查詢需求，但該解決方法一定程度上加快了溢出的速度，且增加了對帶環(huán)路徑查詢的復(fù)雜度。

如圖4所示，物品重復(fù)經(jīng)過了幾次A和C，但由于經(jīng)過的時間不同，可將A和C當(dāng)做不同的位置看待。因此圖中六個位置的self_label編碼依次為2,3,5,7,11,13；Element_enc為30030，SC值為29243。

圖4 環(huán)路結(jié)點重命名

2.3.2 環(huán)路編碼

對于環(huán)路問題，文獻[12]提出一種考慮環(huán)路的素數(shù)編碼策略，稱為環(huán)路編碼。其給出了一種新的計算同余值（SC）方法，即將計算SC時除數(shù)相同的項合并為一項并把它們的序號（即余數(shù)）信息加入到合并后的公式(1)中：

其中primet表示每個位置的self_label，即唯一的素數(shù)，kt表示該位置在路徑中出現(xiàn)的次數(shù)，its表示該位置在路徑中的序號。考慮素數(shù)編碼中可能出現(xiàn)余數(shù)大于除數(shù)的情況，每個位置分配的素數(shù)應(yīng)大于其在路徑中的次序，primet＞its。

文獻還證明了素數(shù)編碼是其環(huán)路編碼的一種特例，并給出了相應(yīng)的解碼方法，以還原出原路徑的位置和序號。

例如，如圖5所示，C和D重復(fù)出現(xiàn)形成環(huán)路。A、C、D三個位置的self_label編碼依次為2，5，7。路徑的Element_enc值為2×5×7×5×7=2450，SC值滿足：

SC＜Element_enc；

SCmod2=1；

SCmod52=2+4×5；

SCmod72=3+5×7；

于是。可以得出SC=2047。

圖5 環(huán)路編碼示意圖

編碼（2450,2047）的解碼過程如下：

①2450因式分解為2×52×72，得到經(jīng)過位置A,C,D，且兩次經(jīng)過C和D。

②由SC=2047得到A位置對應(yīng)序號SCmod2=1，位置C對應(yīng)序號i1=2047mod5=2，i2=(2047mod52-2047mod5)/5=4。位置D對應(yīng)序號i1=2047mod7=3，i2=(2047mod72-2047mod7)/7=5。

③還原路徑為 A-＞C-＞D-＞C-＞D.

由以上實例可看出，環(huán)路編碼可以很好的解決帶環(huán)路徑問題，且整個編碼解碼的過程中沒有信息丟失。

此外，該文獻在環(huán)路編碼的基礎(chǔ)上給出了針對長路徑編碼溢出的路徑分裂方法。不同的是，在分裂路徑時，對計算每個位置的SC值時，所用的位置結(jié)點序號仍是該位置在長路徑中的絕對位置序號。

3 復(fù)合編碼

素數(shù)編碼是面向路徑的編碼，只能存儲路徑位置信息。然而，在RFID供應(yīng)鏈中不可避免會遇到面向時間的查詢需求。為了應(yīng)對素數(shù)編碼在面向時間的編碼缺失問題，已有文獻給出了面向路徑的素數(shù)編碼和面向時間的區(qū)間編碼的復(fù)合編碼模型。

3.1 素數(shù)與區(qū)間相結(jié)合的復(fù)合編碼

文獻[11]提出了一種素數(shù)編碼和區(qū)間編碼共同使用的復(fù)合編碼，分別建立一棵路徑樹和一棵時間樹，即用素數(shù)編碼方法編碼路徑的位置信息，用區(qū)間編碼方法編碼路徑的時間信息，在區(qū)間編碼中，使用對編碼遍歷的方法給每個結(jié)點一個start值和 end值(圖為后序遍歷)。若A.Start＜B.Start且B.End＜A.End，可以判斷A是B的祖先。

例如要對如下路徑數(shù)據(jù)進行編碼時，采用復(fù)合編碼方案，將路徑里的位置信息抽出來進行素數(shù)編碼，將帶時間的路徑數(shù)據(jù)進行區(qū)間編碼，區(qū)間編碼用后序遍歷產(chǎn)生，生成的編碼樹如圖6，圖7所示。

A[2,3]-＞B[5,7]-＞C[8,9]

A[2,3]-＞B[5,7]-＞D[13,16]

A[2,3]-＞B[7,8]-＞D[14,18]

A[2,3]-＞E[6,4]-＞C[7,8]

A[2,3]-＞D[4,5]

A[2,3]-＞D[5,6]

圖6 復(fù)合編碼中的路徑樹

圖7 復(fù)合編碼中的時間樹

查詢實例1（不帶時間的路徑查詢）：查詢經(jīng)過了B的所有路徑。在圖7中，B的self_label為3，找到所有能整除3的Element_enc值即可，于是找到了Element_enc值30和42，從而找出路徑 A-＞B-＞C 和 A-＞B-＞D。

查詢實例2（帶時間的路徑查詢)：查詢在5到7時間內(nèi)經(jīng)過B點的所有路徑。在圖8中，B[5,7]的區(qū)間編碼為(2,7)，查詢所有結(jié)點中Start＜2且End＞7找到B[5,7]的親代結(jié)點A[2,3]，A[2,3]為根節(jié)點，停止追溯。再查詢所有結(jié)點中Start＞2且End＜7的結(jié)點，找到C[8,9]，D[13,16]，都為葉子結(jié)點，停止追溯。由此，查詢出路 徑 A[2,3]-＞B[5,7]-＞C[8,9]和 A[2,3]-＞B[5,7]-＞D[13,16]。

區(qū)間編碼實現(xiàn)了時態(tài)信息查詢，但是一旦有一個結(jié)點發(fā)生改變，可能就會導(dǎo)致其它結(jié)點要重新編碼。如圖7中在C[8,9]與D[13,16]之間插入結(jié)點X，其編碼變?yōu)?5,6)，替代了原先D[13,16]的編碼，使原本的結(jié)點碼值往后移，整棵樹的編碼僅有C[8,9]不用變化，其他結(jié)點的編碼全都要改變，因此更新代價較大。

3.2 DRB編碼

為解決上述問題，文獻[9]在復(fù)合編碼的基礎(chǔ)上，提出一種改進的區(qū)域編碼方法“DRB(Durable Region-Based numbering scheme)編碼”代替上述區(qū)間編碼。DRB編碼方法使用深度遍歷時間樹得到一對整數(shù)值(order,size)。每條路徑的編碼只用該路徑上最后一個位置的編碼來表示。

對于DRB編碼有三個性質(zhì)：

①對于任意一個節(jié)點B，若它的父節(jié)點為A，則必須滿足order(B)＞order(A)且 order(B)+size(B)＜o(jì)rder(A)+size(A)。

②對于任意兩個兄弟節(jié)點B和C，若B是C的前驅(qū)，則必須滿足 order(B)+size(B)＜o(jì)rder(C)。

③對于樹中的任意節(jié)點A，size(A)是一個任意的正整數(shù)值，A的孩子集合為B，則必須滿足size(A)＞=∑B(size(B))。

該編碼方法相比較于區(qū)域編碼方法最大的優(yōu)點在于它的更新代價更低，它為以后要插入的新的路徑結(jié)點預(yù)留了空間。當(dāng)新的路徑插入時，該路徑后面的位置結(jié)點不需要重新編碼。

如圖8中，X結(jié)點是待插入結(jié)點，按DRB編碼的三個性質(zhì)得出如下不等式：

order(X)＞order(B)=10 且 order(X)+size(X)＜o(jì)rder(B)+si ze(B)=40

order(C)+size(C)=16＜o(jì)rder(X)且 order(X)+size(X)＜o(jì)rder(D)=20

size(B)=30＞=size(C)+size(X)+size(D)=10+size(X)

化簡后可得：

10＜o(jì)rder(X);order(X)+size(X)＜40;

16＜o(jì)rder(X);order(X)+size(X)＜20;

size(X)＜=20

X的三個可能取值為：order=17 size=1；order=17 size=2；order=18 size=1；但無論是哪一種，在此例中其他結(jié)點的碼值都不會發(fā)生變化，更新代價較小，但當(dāng)插入位置沒有size和order的可行解時，仍會同區(qū)間編碼一樣產(chǎn)生大面積更新。

圖8 DRB編碼

可以看出，與區(qū)間編碼相比，DRB編碼更新性能有明顯提升。但由于很難預(yù)測新插入的結(jié)點需要多大的預(yù)留空間，因此可能會導(dǎo)致不必要的空間浪費。

4 工作總結(jié)

從目前來看，RFID路徑編碼中的主要使用的方法有素數(shù)編碼及復(fù)合編碼。素數(shù)編碼在對路徑追溯查詢時有較好的表現(xiàn)。通過對素數(shù)編碼的不斷完善，解決了長路徑溢出問題及供應(yīng)鏈中的環(huán)路編碼問題，使得素數(shù)編碼能較好的滿足供應(yīng)鏈中各種面向路徑的查詢。復(fù)合編碼方法是在素數(shù)編碼的基礎(chǔ)上引入?yún)^(qū)間編碼，存儲路徑中的時間信息，能滿足面向時間的路徑查詢需求。但是，由于素數(shù)編碼和區(qū)間編碼的更新代價較大，不能較好滿足路徑實時更新需求，因此需進一步研究更新代價低、支持實時動態(tài)更新的路徑編碼策略。另外，為保證供應(yīng)鏈環(huán)節(jié)的信息保密需求，分布式編碼策略也是將來研究方向之一。

[1]Derakhshan R, Orlowska M E, Li X. RFID Data Management: Challenges and Opportunities[C]//Proceedings of 2007 IEEE International Conference on RFID. IEEE,2007:175-182.

[2]Want R. An introduction to RFID technology[J]. IEEE Pervasive Computing, 2006, 5(1): 25-33.

[3]Hector G,Han Jiawei, Cheng Hong,et al. Modeling massive RFID data sets:A gateway-based movement graph approach[ J].IEEE Transactions on Knowledge & Data Engineering, 2010, 22(1): 90-104.

[4]Wang Y, Zhang G, Sheng F, et al. A RFID data cache structure based on Dual T-Tree for spatio-temporal query[C]// Proceedings of the 4th International Conference on Information Science and Technology. IEEE, 2011:357-362.

[5]劉敏,李戰(zhàn)懷,陳群,智能超市中在線與離線 RFID數(shù)據(jù)倉庫技術(shù)研究 [ J]. 計算機工程與科學(xué),2011,33 (11):171-176.

[6]Lee C H, Chung C W. Efficient storage scheme and query processing for supply chain management using RFID[C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. ACM,2008: 291-302..

[7]Wu W, Guo W, Tan K L. Distributed Processing of Moving K-Nearest-Neighbor Query on Moving Objects[C]//Proceedings of the 23rd International Conference on Data Engineering. IEEE, 2007:1116-1125.

[8]Li Q, Moon B. Indexing and Querying XML Data for Regular Path Expressions[C]// Proceedings of the 27th VLDB Conference, Roma:University of Arizona.2001:0.

[9]伏楠, 鄭麗英, 朱宇航. RFID路徑數(shù)據(jù)編碼壓縮存儲技術(shù)研究[J]. 蘭州交通大學(xué)學(xué)報, 2013, 32(1):82-87.5.

[10]陳雄, 王笑梅. 基于素數(shù)編碼技術(shù)對供應(yīng)鏈中路徑編碼的研究[J]. 上海師范大學(xué)學(xué)報(自然科學(xué)版), 2012, 41(5): 483-489.

[11]Lee C H, Chung C W. RFID Data Processing in Supply Chain Management Using a Path Encoding Scheme[J]. IEEE Transactions on Knowledge & Data Engineering, 2011,23(5): 742-758.

[12]Lu Y, Chen L. An improved RFID data encoding scheme for cycling path problem[C]// Proceedings of the 4th IEEE International Conference on Software Engineering and Service Science. IEEE, 2013: 611-615.

本研究受江西財經(jīng)大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目（201710421025）和江西省自然科學(xué)基金項目（20151BBG70046）項目資助。