RFID對(duì)象包含關(guān)系幾何向量編碼優(yōu)化策略

廖國(guó)瓊，段雨薇，楊樂(lè)川

1(江西財(cái)經(jīng)大學(xué) 信息管理學(xué)院，南昌 330032) 2(江西省高校數(shù)據(jù)與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室，南昌 330032)

1 引 言

隨著5G網(wǎng)絡(luò)的推出，競(jìng)爭(zhēng)激烈的市場(chǎng)再次將“萬(wàn)物互聯(lián)”的優(yōu)勢(shì)展示在了人們眼前，利用物聯(lián)網(wǎng)智能化管理供應(yīng)鏈(Supply Chain)，是提高市場(chǎng)監(jiān)管效率的有效手段之一.在眾多物聯(lián)網(wǎng)設(shè)備中，無(wú)線(xiàn)射頻識(shí)別技術(shù)(Radio Frequency Identification，RFID)因其成本低、體積小，可增加物品的追溯性，從而較早被提出[1,2].該系統(tǒng)由電子標(biāo)簽、閱讀器、天線(xiàn)組成，其中電子標(biāo)簽具有唯一性、可實(shí)現(xiàn)多目標(biāo)非接觸自動(dòng)快速識(shí)別，且RFID具有大規(guī)模部署潛力，因此可為實(shí)現(xiàn)物品在供應(yīng)鏈環(huán)境中追溯提供良好的硬件支持[3-5].

供應(yīng)鏈?zhǔn)菍?duì)客戶(hù)訂單有興趣的一組流程和實(shí)體[6].按照ISO規(guī)定標(biāo)準(zhǔn)，追溯是指通過(guò)記錄物品的識(shí)別代碼以實(shí)現(xiàn)追蹤對(duì)象的空間變化[7].文獻(xiàn)[8]按追溯粒度大小將追溯分為單品級(jí)追溯與批次級(jí)追溯；按追溯功能將追溯分為位置追溯、包含關(guān)系追溯.

在供應(yīng)鏈整個(gè)生命周期內(nèi)構(gòu)建完整的包含關(guān)系追溯系統(tǒng)，應(yīng)設(shè)計(jì)合理的追溯模型、編碼機(jī)制及追溯策略等[9].本文主要研究支持包含關(guān)系追溯的編碼機(jī)制，追溯需求主要為向下追溯、向上追溯、平行追溯和包含歷史追溯，而在設(shè)計(jì)編碼時(shí)，應(yīng)考慮供應(yīng)鏈應(yīng)用環(huán)境的以下特征：

標(biāo)簽海量性.存在大量粘貼RFID標(biāo)簽的物品在供應(yīng)鏈中流通.

標(biāo)記對(duì)象數(shù)量已知性.物品流通前需要用RFID標(biāo)簽進(jìn)行標(biāo)記，因此供應(yīng)鏈中標(biāo)記對(duì)象數(shù)量已知.

包含關(guān)系多層級(jí)性.流通對(duì)象可分為物品對(duì)象、容器對(duì)象，因此形成多層級(jí)包含關(guān)系.

單體改變性.物品在流通過(guò)程中，可能會(huì)發(fā)生包裝拆分和包裝重組等操作，單件物品可能從某容器拆分到新的容器對(duì)象之中，改變?cè)械陌P(guān)系.

整體改變性.當(dāng)某容器從其上層容器中拆分到新的容器中時(shí)，該容器中的全部對(duì)象整體跟隨移動(dòng)到新容器中.

包含關(guān)系的本質(zhì)是層次關(guān)系，單體改變性和整體改變性是供應(yīng)鏈中常見(jiàn)的包裝拆裝情況，而目前已有的層次編碼策略較少考慮以上特征.因此本文在基于這些特征，深入研究RFID標(biāo)簽對(duì)象編碼策略，以增強(qiáng)包含關(guān)系的可追溯性.

2 相關(guān)研究

追溯查詢(xún)供應(yīng)鏈中物品的包含關(guān)系，需要對(duì)所有流通在供應(yīng)鏈中的RFID對(duì)象進(jìn)行編碼.包含關(guān)系可表示為樹(shù)形結(jié)構(gòu)，目前涉及層次關(guān)系的編碼有素?cái)?shù)編碼、區(qū)間編碼、前綴編碼、向量編碼及幾何向量編碼等.素?cái)?shù)編碼采用自頂向下的方式依次為編碼樹(shù)的每一層結(jié)點(diǎn)賦予一個(gè)素?cái)?shù)[10,11]，當(dāng)某上層容器中的物品全部拆分到下層新容器中時(shí)需要重新分配素?cái)?shù)且由于標(biāo)簽的海量性容易出現(xiàn)素?cái)?shù)溢出情況，而且追溯查詢(xún)時(shí)同余值的計(jì)算較為復(fù)雜，導(dǎo)致該方法的查詢(xún)效率低，不適用于大型供應(yīng)鏈場(chǎng)景.區(qū)間編碼對(duì)樹(shù)先序遍歷，再對(duì)同一棵樹(shù)后續(xù)遍歷，使得每一個(gè)結(jié)點(diǎn)都可由一對(duì)整數(shù)表示，構(gòu)成一個(gè)區(qū)間.文獻(xiàn)[12]采用區(qū)間編碼以實(shí)現(xiàn)對(duì)RFID對(duì)象的追溯，整數(shù)形式的編碼使得查詢(xún)效率高，但是由于供應(yīng)鏈環(huán)境的單體改變性，當(dāng)某容器中對(duì)象拆分到新容器時(shí)，需要重新遍歷樹(shù)來(lái)獲取新的編碼，因此該編碼方式主要用于包含關(guān)系變化不頻繁的場(chǎng)合.前綴編碼的編碼規(guī)則為父結(jié)點(diǎn)的編碼是子結(jié)點(diǎn)的前綴，利用符號(hào)連接[13].該方法較區(qū)間編碼而言更新代價(jià)小，但由于供應(yīng)鏈環(huán)境下的標(biāo)簽海量性，查詢(xún)時(shí)字符串的匹配時(shí)間長(zhǎng)，導(dǎo)致查詢(xún)效率低，也不適用于大型供應(yīng)鏈場(chǎng)景.

文獻(xiàn)[14]中針對(duì)XML文檔提出向量編碼，利用一對(duì)向量代替區(qū)間編碼的區(qū)間值來(lái)給對(duì)象編碼.向量編碼的向量計(jì)算依賴(lài)于區(qū)間編碼，結(jié)點(diǎn)由一對(duì)向量表示，基于兩個(gè)向量之間可以插入無(wú)限多個(gè)向量的思想，可避免在供應(yīng)鏈環(huán)境下插入新物品時(shí)需重新編碼的情況，以此降低了更新開(kāi)銷(xiāo)，但是出現(xiàn)某容器中物品整體拆分到新容器中時(shí)，還是需重新編碼才能反映正確的包含關(guān)系，并且由于標(biāo)簽的海量性，每一個(gè)對(duì)象都由一對(duì)向量表示導(dǎo)致存儲(chǔ)效率低，存儲(chǔ)開(kāi)銷(xiāo)大.為克服向量編碼的不足，文獻(xiàn)[15]在其基礎(chǔ)上提出了幾何向量編碼策略(后續(xù)詳細(xì)介紹)，可避免重新編碼情況發(fā)生，但該策略中存在數(shù)據(jù)溢出與數(shù)據(jù)碰撞問(wèn)題.因此，本文擬針對(duì)這兩個(gè)問(wèn)題對(duì)幾何向量編碼進(jìn)行優(yōu)化，進(jìn)一步提高編碼及追溯查詢(xún)性能.

3 編碼準(zhǔn)備

本節(jié)主要介紹編碼的基礎(chǔ)工作，包括RFID對(duì)象的包含關(guān)系、信息存儲(chǔ)形式等.

3.1 包含關(guān)系

我們稱(chēng)粘貼RFID標(biāo)簽的對(duì)象為標(biāo)記對(duì)象(Tag Objects，T)，可分為簡(jiǎn)單對(duì)象與容器對(duì)象.

圖1是一個(gè)包含關(guān)系樹(shù)示例，其中TC1，TC2為兩個(gè)包裝箱，IC1，IC2，IC3為包裝盒，S1，S2，S3等為具體物品，樹(shù)中的層次關(guān)系表示了它們之間的包含關(guān)系.其中虛線(xiàn)部分表示供應(yīng)鏈下兩種不同的包含關(guān)系變化，圖1(a)中為向容器IC2中加入物品S3，S4，對(duì)應(yīng)供應(yīng)鏈環(huán)境的單體改變性；圖1(b)為向容器TC2中添加容器IC3及其包含的兩個(gè)物品S5，S6，對(duì)應(yīng)整體改變性.

圖1 包含關(guān)系示例Fig.1 Example of containment relationships

定義1.簡(jiǎn)單對(duì)象是指不能包含其他標(biāo)記對(duì)象的對(duì)象，可由二元組S = 表示，其中id為該對(duì)象的唯一標(biāo)識(shí)，l表示該標(biāo)記對(duì)象所處的層級(jí).

按照追溯粒度的不同，簡(jiǎn)單對(duì)象可為單個(gè)物品或一批產(chǎn)品.考慮到包含關(guān)系追溯的一般性，后文所提的物品均為簡(jiǎn)單對(duì)象.如圖1中簡(jiǎn)單對(duì)象S1，S2，S3等都位于包含關(guān)系的最底(內(nèi))層，設(shè)定其層級(jí)數(shù)l= 0.

定義2.容器對(duì)象是指包含其它標(biāo)記對(duì)象的對(duì)象，可由四元組C =表示，其中n為該容器的最大容量，f為該容器已包含的對(duì)象數(shù)量.

容器對(duì)象可分為頂層容器對(duì)象，如圖1中的頂層包裝盒TC1，TC2，不能被其他容器對(duì)象包含，和中間層容器對(duì)象，如圖1中IC1，IC2，IC3等，可被上層容器包含.

3.2 數(shù)據(jù)記錄

簡(jiǎn)單對(duì)象和容器對(duì)象形成了多層級(jí)包含關(guān)系，在物品在流通之前由用戶(hù)定義，存入如表1所示的對(duì)象表中.由于簡(jiǎn)單對(duì)象不能包含其他對(duì)象，因此只記錄其tid與l的值，且其層級(jí)l為0，而包含容器的l值由底向上逐層遞增.

表1 對(duì)象表Table 1 Object table

定義3.每個(gè)標(biāo)記對(duì)象都對(duì)應(yīng)一條包含關(guān)系記錄，可表示為一個(gè)四元組CR = ，其中pid為直接包含該對(duì)象的容器對(duì)象標(biāo)識(shí)，ts為該對(duì)象進(jìn)入pid對(duì)象的時(shí)間，te是指該對(duì)象離開(kāi)pid對(duì)象的時(shí)間.特殊地，當(dāng)一個(gè)對(duì)象進(jìn)入一容器后，包含關(guān)系未發(fā)生變化時(shí)，其ts記為Now.

包含關(guān)系記錄是在物品包裝過(guò)程中動(dòng)態(tài)生成的，存入如表2所示的包含關(guān)系表中.

表2 包含關(guān)系表Table 2 Container table

3.3 建立關(guān)系樹(shù)

為反映標(biāo)記對(duì)象之間的包含關(guān)系和提高編碼效率，我們可利用對(duì)象表和包含關(guān)系表，構(gòu)建一棵滿(mǎn)N叉樹(shù)形式的包含關(guān)系樹(shù)，其中結(jié)點(diǎn)表示標(biāo)記對(duì)象，用于存儲(chǔ)基本信息；邊表示標(biāo)記對(duì)象之間的包含關(guān)系，用于存儲(chǔ)對(duì)象進(jìn)入、離開(kāi)直接容器的時(shí)間.由于簡(jiǎn)單對(duì)象數(shù)量、容器對(duì)象數(shù)量和容器對(duì)象容量等已知，故可對(duì)樹(shù)進(jìn)行統(tǒng)一編碼.

圖2 關(guān)系樹(shù)示例Fig.2 Example of relational trees

以圖1的包含關(guān)系為例，假設(shè)容器的最大容量為2，結(jié)合表1、表2建立的關(guān)系樹(shù)如圖2所示.其中，虛結(jié)點(diǎn)X為頂層容器對(duì)象的父結(jié)點(diǎn).

對(duì)關(guān)系樹(shù)進(jìn)行初始化時(shí)，計(jì)算出所有結(jié)點(diǎn)的編碼.可以看出，容器對(duì)象TC2的容量未滿(mǎn)，仍給出了結(jié)點(diǎn)IC4與其包含的S7、S8的編碼，但儲(chǔ)存的信息為空值.當(dāng)TC2有新對(duì)象加入時(shí)，只需增加時(shí)間信息，無(wú)需重新再編碼，提高了更新效率.

4 幾何向量編碼優(yōu)化策略

文獻(xiàn)[14]提出的向量編碼原理可用于供應(yīng)鏈環(huán)境下的包含關(guān)系編碼，但是不能直接利用其編碼策略給標(biāo)記對(duì)象編碼.文獻(xiàn)[15]在其基礎(chǔ)上提出一種幾何向量編碼策略，解決了原向量編碼存儲(chǔ)空間開(kāi)銷(xiāo)大等問(wèn)題.本節(jié)首先介紹幾何向量編碼基本原理、存在問(wèn)題，然后提出優(yōu)化策略.

4.1 幾何向量編碼及存在問(wèn)題

幾何向量編碼策略[15]是基于兩個(gè)向量間可以插入無(wú)限多個(gè)向量的思想，利用二維坐標(biāo)軸第一象限中的向量進(jìn)行編碼.首先初始化虛結(jié)點(diǎn)為[1，0]，[0，1]，再根據(jù)容器對(duì)象的容量(n)來(lái)等分向量之間的夾角計(jì)算相應(yīng)向量值.向量的插入規(guī)則為，假設(shè)容器對(duì)象A由向量a，b組成，以a向量末端為起點(diǎn)作與b平行的射線(xiàn)c，按照A的容量等分a，b之間的夾角與c的交點(diǎn)為插入向量的末端，由此生成下一層標(biāo)記對(duì)象的向量.容器對(duì)象由一對(duì)向量表示，簡(jiǎn)單對(duì)象由一個(gè)向量表示，編碼計(jì)算公式(1)如下：

(1)

(2)

文獻(xiàn)[15]證明了所有被近似處理后的向量間還保持原有的包含關(guān)系，但是原策略中對(duì)由公式(2)計(jì)算得到的向量值，直接采用向上取整的方式來(lái)得到最終編碼.該策略雖然降低了編碼的計(jì)算、存儲(chǔ)開(kāi)銷(xiāo)，但存在數(shù)據(jù)溢出和數(shù)據(jù)碰撞的問(wèn)題：

問(wèn)題1.數(shù)據(jù)溢出問(wèn)題.根據(jù)幾何向量編碼機(jī)制中向量的插入規(guī)則，當(dāng)容器對(duì)象某一向量的傾斜角越大越靠近y軸，或傾斜角越小越靠近x軸時(shí)，會(huì)導(dǎo)致下一層插入對(duì)象的向量橫、縱坐標(biāo)值過(guò)大，造成數(shù)據(jù)溢出的情況.

問(wèn)題2.數(shù)據(jù)碰撞問(wèn)題.通過(guò)公式(2)計(jì)算向量得到xc和yc不為整數(shù)，文獻(xiàn)[15]采用向上取整的方式對(duì)數(shù)據(jù)的小數(shù)位進(jìn)行取舍.而直接取整會(huì)產(chǎn)生兩個(gè)或兩個(gè)以上對(duì)象由相同向量表示，因此會(huì)發(fā)生數(shù)據(jù)碰撞的情況.針對(duì)以上兩個(gè)問(wèn)題本文提出優(yōu)化策略并證明其正確性.

4.2 優(yōu)化策略

由公式(2)計(jì)算得到的向量，不直接采用向上取整的方式，而是提出新的數(shù)據(jù)優(yōu)化策略，以解決問(wèn)題1和2.現(xiàn)對(duì)二維坐標(biāo)中第一象限的數(shù)據(jù)做以下處理：

1)擴(kuò)大虛結(jié)點(diǎn)的初始值為[10l，0]，[0，10l]；

2)以坐標(biāo)原點(diǎn)為圓心，畫(huà)與包含層級(jí)l相同個(gè)數(shù)的同心圓，同心圓由內(nèi)層到外層的半徑比為1：10，第l層對(duì)象的向量取與第1個(gè)圓在第一象限的交點(diǎn)坐標(biāo)，第l-1層取與第2個(gè)同心圓的交點(diǎn)，以此類(lèi)推；

3)由步驟2)得到的結(jié)果不為整數(shù)，因此要對(duì)數(shù)據(jù)小數(shù)位進(jìn)行取舍，保留與包含層級(jí)l相關(guān)的有效位數(shù).

以圖1包含關(guān)系中(S1，S2)?IC1?TC1為例，對(duì)其向量編碼進(jìn)行優(yōu)化，如圖3所示.

圖3 向量?jī)?yōu)化示例Fig.3 Examples of optimize vector data

定理1.設(shè)A1[xa，ya]和A2[xb，yb]是某容器對(duì)象某一向量與同心圓O1，O2的兩個(gè)交點(diǎn)坐標(biāo)，ra，rb分別是半徑等比例同心圓O1，O2的半徑.當(dāng)kra=rb(k為實(shí)數(shù))時(shí)，則有kxa=xb，kya=yb.

證明：假設(shè)某過(guò)原點(diǎn)O的向量與同心圓O1，O2分別相交于A1，A2點(diǎn)，此時(shí)向量OA1，OA2與x軸的夾角為θ.因?yàn)橥膱AO1，O2半徑等比例，則有kra=rb.由于

由此可證kxa=xb，kya=yb，成立.

以原點(diǎn)為圓心點(diǎn)，可以保證每層包含層級(jí)對(duì)應(yīng)的圓為同心圓，由定理1可得，容器對(duì)象向量與每一層級(jí)圓的交點(diǎn)坐標(biāo)為等比關(guān)系.由公式(2)計(jì)算后得到xc，yc再對(duì)其進(jìn)行上述處理后得到計(jì)算公式(3)：

(3)

利用同心圓優(yōu)化向量坐標(biāo)，可以保證同層級(jí)對(duì)象向量與同一圓相交，不同層級(jí)對(duì)象向量分別與對(duì)應(yīng)層級(jí)圓相交，借此可以通過(guò)坐標(biāo)大小來(lái)判斷該向量所處的層級(jí).容器P1的兩個(gè)向量與同心圓組中O1相交，當(dāng)往容器P1中增加下一層級(jí)的容器對(duì)象的時(shí)，容器對(duì)象P1的兩個(gè)向量將會(huì)作為下一層級(jí)第一個(gè)容器的始向量，與最后一個(gè)容器對(duì)象的末向量，此時(shí)P1的兩個(gè)向量會(huì)與同心圓組中的O2相交，容器對(duì)象P1的向量與同心圓O1，O2交點(diǎn)的坐標(biāo)成比例，比例與同心圓半徑比有關(guān).

因此，利用公式(3)可以縮小向量末端橫縱坐標(biāo)值，以避免數(shù)據(jù)溢出的情況發(fā)生.

對(duì)于問(wèn)題2，可根據(jù)供應(yīng)鏈環(huán)境特征，確認(rèn)包含關(guān)系的最大包含層級(jí)、容器對(duì)象的容量，根據(jù)實(shí)際調(diào)整虛結(jié)點(diǎn)X的初始值，當(dāng)最大包含層級(jí)為l時(shí)，虛結(jié)點(diǎn)初始向量的始向量為<10l，0>，末向量為<0，10l>.同心圓半徑取值有由內(nèi)到外按照1∶10等例擴(kuò)大.對(duì)由公式(3)得到的數(shù)據(jù)保留與包含關(guān)系層級(jí)有關(guān)的有效位數(shù)，使容器向量易于判斷且可避免數(shù)據(jù)碰撞的情況發(fā)生.

盡管上述解決了數(shù)據(jù)溢出與數(shù)據(jù)碰撞的問(wèn)題，但由于向量與同心圓取交點(diǎn)后做了近似處理，故需要證明所有向量進(jìn)行優(yōu)化后仍然滿(mǎn)足原包含關(guān)系.

證明：由于

對(duì)于相交于同一個(gè)圓上的向量，經(jīng)過(guò)數(shù)據(jù)優(yōu)化得到的梯度滿(mǎn)足于原來(lái)的梯度關(guān)系，因此當(dāng)原包含關(guān)系滿(mǎn)足G(A)

(4)

(5)

(6)

(7)

C2計(jì)算同理.由于r>0，因此G(C1′)

定理1保證了坐標(biāo)之間的等比關(guān)系.結(jié)合定理2、定理3可知在利用幾何向量?jī)?yōu)化策略解決了問(wèn)題1和2的同時(shí)，向量之間仍然保持原有包含關(guān)系，因此優(yōu)化策略可行.

5 編碼及應(yīng)用

本節(jié)主要內(nèi)容為先編碼關(guān)系樹(shù)中所有結(jié)點(diǎn)，再結(jié)合供應(yīng)鏈環(huán)境下包含關(guān)系追溯需求和文獻(xiàn)[15]中所述的包含關(guān)系變化，提出相應(yīng)追溯查詢(xún)算法.

5.1 編碼結(jié)點(diǎn)

根據(jù)前文編碼原理、向量計(jì)算方式，可對(duì)關(guān)系樹(shù)中的結(jié)點(diǎn)依次編碼.從虛結(jié)點(diǎn)X開(kāi)始深度優(yōu)先遍歷，由上至下逐層編碼.編碼過(guò)程即為向量計(jì)算和分配過(guò)程，將得到的向量對(duì)或向量作為標(biāo)記對(duì)象的tid值.關(guān)系樹(shù)中容器對(duì)象結(jié)點(diǎn)(非葉子結(jié)點(diǎn))的向量計(jì)算和分配方式與簡(jiǎn)單對(duì)象結(jié)點(diǎn)(葉子結(jié)點(diǎn))編碼方式不完全相同.

1)虛結(jié)點(diǎn)X編碼

給虛結(jié)點(diǎn)分配初始向量與最大包含層級(jí)數(shù)l相關(guān)：始向量Vs=[10l，0]，末向量Ve=[0，10l].

2)容器對(duì)象編碼

在關(guān)系樹(shù)中容器對(duì)象由樹(shù)的中間結(jié)點(diǎn)表示，對(duì)其統(tǒng)一編碼.首先根據(jù)父容器的容量按公式(2)計(jì)算分配n-1個(gè)等分向量，再利用公式(3)進(jìn)行數(shù)據(jù)優(yōu)化.根據(jù)實(shí)際包含對(duì)象數(shù)(f)，依次為每個(gè)容器對(duì)象分配兩個(gè)相鄰向量，作為容器對(duì)象的tid.第一個(gè)容器對(duì)象的始向量橫縱坐標(biāo)為其父結(jié)點(diǎn)的始向量與該層級(jí)對(duì)應(yīng)的同心圓交點(diǎn)坐標(biāo)，且第m-1個(gè)容器對(duì)象的末向量與第m個(gè)相鄰容器對(duì)象的始向量相同.容器對(duì)象編碼的具體實(shí)現(xiàn)見(jiàn)算法1.

算法1.容器對(duì)象編碼

輸入：Vs，Ve，n，l

輸出：Tid//所有容器的對(duì)象的編碼

Begin

1.Tid→Vs，Ve；//數(shù)據(jù)初始化

2.r→0，tid=Tid，len=0；

3.for(i=1；i<=l-1；i++)：//容器對(duì)象層級(jí)數(shù)為l-1

4.r=pow(10，i)；//同心圓半徑

5.for(j=0；j<=length(tid)-1；j++)：

6. (xA，yA)→tid[j]；

7. (xB，yB)→tid[j+1]；

8.flag→ [0] ；//清空臨時(shí)存儲(chǔ)對(duì)象

9.for(m=1；m<=n-1；m++)：

14.xc′,yc′→保留與層級(jí)有關(guān)的小數(shù)位數(shù)；

15. //存儲(chǔ)所有容器對(duì)象向量

16.flag.append(xc′,yc′)；

17.Tid.append(flag)；//存儲(chǔ)容器tid

18.len→len+length(tid)；//獲取上層容器數(shù)量

19.tid→Tid[len：-1]；//獲取該層容器對(duì)象tid

End

3)簡(jiǎn)單對(duì)象編碼

在關(guān)系樹(shù)中簡(jiǎn)單對(duì)象由葉子節(jié)點(diǎn)表示，其向量計(jì)算與分配與容器對(duì)象基本相同，其不同之處為：

①將直接容器對(duì)象的向量夾角分成n+1等分后，計(jì)算n個(gè)向量；

②每個(gè)簡(jiǎn)單對(duì)象只分配一個(gè)等分向量.

基于以上編碼規(guī)則，先利用公式(2)計(jì)算，再利用公式(3)進(jìn)行優(yōu)化，得到的向量作為簡(jiǎn)單對(duì)象的tid值.簡(jiǎn)單對(duì)象編碼的具體實(shí)現(xiàn)見(jiàn)算法2.

算法2.簡(jiǎn)單對(duì)象編碼

輸入：Pid//l-1層容器對(duì)象的tid值

輸出：Tid//所有簡(jiǎn)單對(duì)象的編碼

Begin

1.for(j=0；j<=length(Pid)-1；j++)：

2. (xA，yA)→Pid[j]；

3. (xB，yB)→Pid[j+1]；

4.for(m=1；m<=n-1；m++)：

9.xc′，yc′→保留與層級(jí)有關(guān)的小數(shù)位數(shù)；

10.Tid.append(xc′，yc′)；//存儲(chǔ)所有簡(jiǎn)單對(duì)象向量

End

5.2 追溯查詢(xún)

對(duì)RFID標(biāo)記對(duì)象進(jìn)行編碼的主要目的是實(shí)現(xiàn)對(duì)流通物品的追溯查詢(xún).

定義4.假設(shè)標(biāo)記對(duì)象A、B、C的包含關(guān)系為C?B?A.當(dāng)A.l-B.l=1時(shí)，稱(chēng)A為B的直接包含容器對(duì)象(父容器)；當(dāng)A.l-C.l>1時(shí)，稱(chēng)A為C的間接包含容器對(duì)象(祖先容器).

定義5.如圖1中的包含關(guān)系，稱(chēng)TC1、TC2為同容器對(duì)象，TC1、TC2與TC3為同層級(jí)對(duì)象.

根據(jù)以上定義，分別說(shuō)明供應(yīng)鏈環(huán)境下對(duì)包含關(guān)系追溯的主要需求：

·向上追溯.是指查詢(xún)物品位于哪個(gè)容器內(nèi).

根據(jù)實(shí)際應(yīng)用情況可細(xì)分為以下3種追溯情況：

·追溯祖先容器對(duì)象.先確定被查詢(xún)對(duì)象的tid值，再通過(guò)包含關(guān)系表中對(duì)應(yīng)的pid值來(lái)得到所有祖先容器，完成查詢(xún).

·追溯父容器對(duì)象.先追溯所有祖先容器，計(jì)算對(duì)應(yīng)的l差值為“1”時(shí)，即為父容器，完成查詢(xún).

已知tid判斷A是否為B的容器對(duì)象.根據(jù)編碼規(guī)則，可直接利用tid進(jìn)行判斷.例如容器對(duì)象A的tid由Vs=，Ve=組成，B的tid為分別計(jì)算向量的梯度G=Y/X，當(dāng)G滿(mǎn)足G(Ve)>G(B)>G(Vs)時(shí)，A即為B的容器對(duì)象.

·向下追溯，是指追溯該容器中包含的對(duì)象.

可查找該容器對(duì)象包含的下一層級(jí)對(duì)象，或查找包含的全部對(duì)象.利用梯度關(guān)系可快速得出某一標(biāo)記對(duì)象是否被該容器包含.向下追溯與向上追溯方法相類(lèi)似，查詢(xún)方法不多贅述.

·平行追溯，是指追溯物品與哪些物品位于同一容器內(nèi)或處于同一層級(jí).

·查詢(xún)同容器對(duì)象.利用被查詢(xún)對(duì)象的tid值先實(shí)現(xiàn)向上追溯查找父容器對(duì)象，再利用父容器的tid值來(lái)實(shí)現(xiàn)向下追溯，得到同容器中的全部對(duì)象.

·查詢(xún)同層級(jí)對(duì)象.由于編碼策略的優(yōu)勢(shì)，不同層級(jí)的對(duì)象向量中的橫縱坐標(biāo)值保留與層級(jí)數(shù)有關(guān)的有效位數(shù)，因此可以根據(jù)tid值中橫縱坐標(biāo)的小數(shù)位數(shù)來(lái)得出同層級(jí)對(duì)象的tid值.

·包含關(guān)系歷史追溯，是指物品在供應(yīng)鏈流通時(shí)，隨時(shí)間發(fā)生包含關(guān)系變化后，追溯到它曾經(jīng)存放過(guò)的容器.

供應(yīng)環(huán)境下主要的包含關(guān)系變化有兩種[15].第一種為往容器中添加未編碼的新對(duì)象，由于給關(guān)系樹(shù)編碼時(shí)，已給出了編碼，只需判斷容器是否可以接收新對(duì)象，接收后直接賦予對(duì)象對(duì)應(yīng)編碼，而不影響已有對(duì)象編碼；第二種為發(fā)生包含關(guān)系拆分重組的情況，從某一容器中遷出進(jìn)入新的容器，為避免遷入對(duì)象所包含子孫對(duì)象重新編碼，保持其子孫對(duì)象的編碼不變，重新編碼遷入對(duì)象即可.

當(dāng)發(fā)生包含關(guān)系變化時(shí)，需要更新包含關(guān)系記錄.包含關(guān)系歷史追溯依據(jù)包含關(guān)系記錄表中所有相關(guān)的包含關(guān)系記錄，先利用向上追溯的方法查找查詢(xún)對(duì)象的全部直接容器對(duì)象，然后按包含時(shí)間的先后排序，即可得到其包含關(guān)系的變化歷史.

6 實(shí)驗(yàn)結(jié)果對(duì)比分析

實(shí)驗(yàn)數(shù)據(jù)由模擬程序生成，首先模擬供應(yīng)鏈環(huán)境下，貼有RFID標(biāo)簽物品的包裝順序，生成包含關(guān)系記錄，再利用對(duì)應(yīng)的對(duì)象表和包含關(guān)系表生成關(guān)系樹(shù)，作為編碼的基礎(chǔ).其中，最大包含層級(jí)數(shù)為4，初始化虛結(jié)點(diǎn)所處的層級(jí)為0，頂層容器對(duì)象個(gè)數(shù)為10.

實(shí)驗(yàn)對(duì)比分析的編碼策略為文獻(xiàn)[14]中提出的原始向量編碼策略(Basic Vector Encoding，BVE)，文獻(xiàn)[15]中提出的近似幾何向量編碼(Approximate Geometry Vector Encoding，AGVE)與本文提出的幾何向量?jī)?yōu)化策略(Geometry Vector Optimization Strategy，GVOS).實(shí)驗(yàn)主要對(duì)比以下4種性能指標(biāo)：編碼初始化時(shí)間、存儲(chǔ)開(kāi)銷(xiāo)、編碼更新時(shí)間、追溯查詢(xún)效率.

6.1 編碼初始化時(shí)間

頂層容器數(shù)量為10的情況下，分別比較每個(gè)容器在容量在不同情況下初始化時(shí)間，圖4是三種編碼機(jī)制的編碼初始化時(shí)間比較結(jié)果.

從圖4中可以看出來(lái)BVE的編碼初始化開(kāi)銷(xiāo)時(shí)間最大，這是因?yàn)锳GVE與GVOS都是在關(guān)系樹(shù)的基礎(chǔ)上直接計(jì)算和分配向量，而B(niǎo)VE則是先區(qū)間編碼，再將區(qū)間編碼轉(zhuǎn)化為向量編碼.AGVE的效率略高于GVOS這是因?yàn)镚VOS在AGVE的基礎(chǔ)上每個(gè)向量與同心圓取了交點(diǎn)，導(dǎo)致效率降低，但是GVOS解決了數(shù)據(jù)碰撞和數(shù)據(jù)溢出的問(wèn)題，且由圖5中可看出GVOS節(jié)省了大量的存儲(chǔ)空間，因此效率差距在可接受范圍內(nèi).

6.2 存儲(chǔ)開(kāi)銷(xiāo)

在頂層容器數(shù)量為10的情況下，分別比較每個(gè)容器在容量不同情況下編碼數(shù)據(jù)存儲(chǔ)開(kāi)銷(xiāo).由圖5可得出幾何向量方法優(yōu)于BVE方法，因?yàn)锽VE編碼時(shí)，無(wú)論是容器對(duì)象還是簡(jiǎn)單對(duì)象都由兩個(gè)向量組成.而使用AGVE和GVOS編碼時(shí)，簡(jiǎn)單對(duì)象僅由一個(gè)向量表示.因此在層級(jí)數(shù)相同的條件下，容器可以存放的簡(jiǎn)單對(duì)象數(shù)量越大，它們之間的存儲(chǔ)開(kāi)銷(xiāo)差距也越大，由圖5可以看出當(dāng)標(biāo)簽達(dá)到百萬(wàn)級(jí)時(shí)BVE所需要的存儲(chǔ)空間近乎是GVOS的3倍.

圖4 編碼初始化時(shí)間比較 圖5 存儲(chǔ)空間比較 圖6 編碼更新時(shí)間比較

6.3 編碼更新時(shí)間

分別比較兩種更新方式(1)添加新容器對(duì)象時(shí)的更新效率；(2)已有容器對(duì)象插入的更新效率.在模擬程序中先構(gòu)建一棵4層的關(guān)系樹(shù)，第1，2層容器容量為10，第3層容器容量為100，最多可編碼1百萬(wàn)個(gè)簡(jiǎn)單對(duì)象.再利用random函數(shù)隨機(jī)生成插入層級(jí)，(1)類(lèi)的對(duì)比結(jié)果如圖6中實(shí)線(xiàn)部分所示.(2)類(lèi)的對(duì)比結(jié)果如圖6中虛線(xiàn)部分所示.

(1)類(lèi)更新方式，結(jié)果如圖6實(shí)線(xiàn)所示，除BVE外其他2種編碼機(jī)制效率相差甚微，原因是添加新對(duì)象時(shí)，幾何向量方法是利用了向下追溯查找可插入容器的位置，再將編碼關(guān)系樹(shù)時(shí)計(jì)算得到的編碼分配給新對(duì)象，而基本向量編碼BVE則需要先尋找父結(jié)點(diǎn)及兄弟結(jié)點(diǎn)，再根據(jù)兄弟結(jié)點(diǎn)的編碼值計(jì)算新編碼，因此更新效率相對(duì)較差.

在(2)類(lèi)更新中，由圖6虛線(xiàn)結(jié)果可得，因?yàn)锳GVE與GVOS只需利用向下追溯獲取可插入位置，并給容器對(duì)象分配的當(dāng)前位置編碼(具體編碼在初始化時(shí)已計(jì)算)，因此AGVE與GVOS效率相差不大，而B(niǎo)VE不僅要對(duì)容器對(duì)象本身重新編碼，還需對(duì)其包含的全部對(duì)象根據(jù)BVE編碼規(guī)則重新編碼，因此隨著更新對(duì)象數(shù)量的增多，性能差距也越明顯，當(dāng)插入10000個(gè)對(duì)象時(shí)BVE耗時(shí)近乎是其他兩個(gè)策略的4倍.

6.4 追溯查詢(xún)性能

在供應(yīng)鏈環(huán)境下主要有4種包含關(guān)系追溯，在模擬程序中構(gòu)建一棵與6.3節(jié)相同的關(guān)系樹(shù)，追溯查詢(xún)性能對(duì)比結(jié)果如表3所示(查詢(xún)結(jié)果單位：second).

6.4.1 向上追溯

對(duì)比追溯父容器對(duì)象的效率，按照5.2節(jié)中的查詢(xún)方式進(jìn)行查詢(xún)，3種編碼機(jī)制的對(duì)比結(jié)果如表3中向上追溯欄所示.由于GVOS的編碼保留了與層級(jí)相關(guān)的有效位數(shù)，降低了查找容器對(duì)象的時(shí)間，提高了追溯查詢(xún)效率.BVE的簡(jiǎn)單對(duì)象和容器對(duì)象都是由兩個(gè)向量組成的，梯度對(duì)比時(shí)間復(fù)雜度高，因此追溯效率低.

6.4.2 向下追溯

獲取隨機(jī)生成的容器對(duì)象的編碼，利用梯度關(guān)系追溯查詢(xún)?cè)撊萜靼乃袑?duì)象以實(shí)現(xiàn)向下追溯.效率對(duì)比結(jié)果如表3中向下追溯欄所示.由于GVOS機(jī)制的編碼方式降低了梯度對(duì)比的時(shí)間復(fù)雜度，所以追溯查詢(xún)效率高，而B(niǎo)VE的簡(jiǎn)單對(duì)象是由兩個(gè)向量表示的，這樣的數(shù)據(jù)結(jié)構(gòu)增加了查詢(xún)所需要的時(shí)間，當(dāng)追溯數(shù)據(jù)越多時(shí)，效率差異越明顯.

表3 追溯查詢(xún)效率對(duì)比Table 3 Trace query efficiency comparisons

6.4.3 包含歷史追溯

AGVE與GVOS可依據(jù)包含關(guān)系記錄，先向上追溯查找被查詢(xún)對(duì)象的全部直接容器對(duì)象，再按包含時(shí)間的先后排序，即可得到其包含關(guān)系的變化歷史.實(shí)驗(yàn)對(duì)比結(jié)果如表3中歷史追溯欄所示，由于包含關(guān)系發(fā)生變化時(shí)，BVE方法需要重新編碼，無(wú)法直接判斷出該容器是否發(fā)生變化，每一次查詢(xún)都需查表，因此追溯查詢(xún)效率低.

6.4.4 平行追溯

查詢(xún)處于同一容器中的所有對(duì)象，先要對(duì)隨機(jī)生成的被查詢(xún)對(duì)象進(jìn)行向上追溯，查找上層容器.在獲取容器對(duì)象的編碼后，再向下追溯，以此來(lái)實(shí)現(xiàn)平行追溯.效率對(duì)比結(jié)果表3中平行追溯欄所示.GVOS的效率最高，因?yàn)槠湎蛏舷蛳碌淖匪菪矢?，而B(niǎo)VE簡(jiǎn)單對(duì)象由兩個(gè)向量表示，因此BVE的效率最低，且當(dāng)容器包含的簡(jiǎn)單對(duì)象越多時(shí)，效率差異越大.

7 總結(jié)與展望

為了提高在供應(yīng)鏈環(huán)境下RFID對(duì)象包含關(guān)系的追溯效率，解決原幾何向量編碼策略中存在的問(wèn)題，本文提出了優(yōu)化策略.基于在從原點(diǎn)出發(fā)的兩向量間可插入無(wú)數(shù)個(gè)向量的特性，提出了一種利用同心圓進(jìn)行優(yōu)化的幾何向量編碼優(yōu)化策略.

該策略的基本思想是，利用坐標(biāo)軸的第一象限，通過(guò)均分兩個(gè)向量之間的夾角進(jìn)行向量的計(jì)算和分配，再利用同心圓上對(duì)應(yīng)的點(diǎn)成比例，且保持原梯度關(guān)系不變的思想來(lái)實(shí)現(xiàn)編碼.與原幾何向量編碼方式相比，該方法降低了編碼開(kāi)銷(xiāo)、提高了追溯效率，并解決了數(shù)據(jù)碰撞、數(shù)據(jù)溢出的問(wèn)題.

通過(guò)實(shí)驗(yàn)對(duì)比分析，驗(yàn)證了所提出編碼策略的可行性及有效性.下一步將基于所提出的編碼策略，深入研究支持包含關(guān)系追溯的時(shí)態(tài)查詢(xún)機(jī)制，進(jìn)一步提高追溯查詢(xún)效率.