1引言

　　RFID(Radio Frequency Identification)技術(shù)是一種非接觸、多目標(biāo)、移動(dòng)目標(biāo)識(shí)別的自動(dòng)識(shí)別技術(shù)，近年來成為自動(dòng)識(shí)別領(lǐng)域的研究熱點(diǎn).該技術(shù)可以廣泛應(yīng)用于物流供應(yīng)鏈、食品安全、防偽、身份識(shí)別、軍事等方面.針對(duì)大型開環(huán)的RFID應(yīng)用，特別是供應(yīng)鏈環(huán)境下的應(yīng)用，需要建立跨地區(qū)、跨行業(yè)的RFID公共服務(wù)基礎(chǔ)設(shè)施和信息共享機(jī)制，作為核心公共服務(wù)之一的RFID發(fā)現(xiàn)服務(wù)，負(fù)責(zé)收集物品在生命周期內(nèi)的過程信息，即將分布的物品信息按時(shí)問序列整合成完整的物品信息鏈。

　　EPCglobal網(wǎng)絡(luò)是一種網(wǎng)絡(luò)基礎(chǔ)設(shè)施，負(fù)責(zé)收集、共享和訪問每個(gè)以EPC(Electronic Product Code)標(biāo)記的物品在供應(yīng)鏈中移動(dòng)的相關(guān)動(dòng)態(tài)信息.EPCglobal網(wǎng)絡(luò)所提供的核心服務(wù)主要包括：(1)EPCIS(EPC Information Service)：根據(jù)預(yù)定義的ECSpec(Event Cycle speeitlcation)識(shí)別或檢驗(yàn)與EPC相關(guān)的業(yè)務(wù)事件的發(fā)生，然后存儲(chǔ)這些業(yè)務(wù)事件作為EPCIS事件，并為本地和遠(yuǎn)程的上層應(yīng)用提供查詢接口.對(duì)EPCIS事件的訪問權(quán)限是由每個(gè)EPCIS本地控制的，因而每個(gè)企業(yè)單獨(dú)決定其EPCIS的訪問控制策略.(2)ONS(Object Naming Service)：負(fù)責(zé)將一個(gè)EPC解析為對(duì)應(yīng)的EPCIS或者其他服務(wù)的地址，ONS由EPC的擁有者(通常是物品的生產(chǎn)商)管理和維護(hù).(3)EPCIS Discovery：ONS只是用來獲取EPC的擁有者(通常為生產(chǎn)商)所維護(hù)的EPCIS服務(wù)地址，但是在供應(yīng)鏈中，其它企業(yè)的EPCIS也可能捕獲了與該EPC相關(guān)的物品動(dòng)態(tài)信息，而通過ONS不能獲取這些EPCIS服務(wù)的地址.這種服務(wù)由EPCIS Discovery提供.在多個(gè)參與方組成的供應(yīng)鏈中，某參與方通過EPCIS Discovery可以查詢到某一物品的組成部分/成分，這些組成部分/成分來自于何處，以及該物品如何交付給最終用戶。

　　一般來說，供應(yīng)鏈連接著很多企業(yè)，從原材料的生產(chǎn)商開始，到使用物品的最終客戶結(jié)束.此外，一個(gè)企業(yè)也可能存在于多個(gè)供應(yīng)鏈中.供應(yīng)鏈中的企業(yè)通常會(huì)有如下三種基本查詢請(qǐng)求：(1)Pedigree查詢，追溯物品的完全歷史信息，包括在何處加工或發(fā)生變化，以及原材料來自于何處等.(2)Recall查詢，查明一批物品的當(dāng)前位置.(3)Bill-of-Material(BOM)查詢，識(shí)別物品所有組成部分或原材料的生命周期信息，這種追溯式查詢需要對(duì)物品進(jìn)行遞歸的組裝或分解過程。

　　目前對(duì)RFID發(fā)現(xiàn)服務(wù)的研究存在三個(gè)問題：(1)在大型開環(huán)的RFID應(yīng)用(特別是供應(yīng)鏈環(huán)境)中，物品數(shù)量及物品信息鏈的數(shù)據(jù)量十分龐大，因而服務(wù)器過載問題嚴(yán)重;(2)面對(duì)高強(qiáng)度的查詢壓力，發(fā)現(xiàn)服務(wù)器容易失效，所以在單點(diǎn)失效情況下應(yīng)能繼續(xù)提供有效的服務(wù);(3)企業(yè)的EPCIS信息屬于私有信息，需要有效地對(duì)允許共享的信息和絕對(duì)保密的信息進(jìn)行控制.為了解決這些問題，同時(shí)保持較高的查詢響應(yīng)效率，本文從大規(guī)模實(shí)際應(yīng)用的需求出發(fā)，在企業(yè)對(duì)其EPCIS進(jìn)行完全的訪問控制的基礎(chǔ)上，選擇了一種切實(shí)可行的模式，即“跟蹤供應(yīng)鏈”模式，以該模式為基礎(chǔ)，提出一種新的具有分布式結(jié)構(gòu)的RFID發(fā)現(xiàn)服務(wù);重新為EPCIS事件進(jìn)行建模，使之能夠表達(dá)供應(yīng)鏈活動(dòng)中的絕大多數(shù)事件;結(jié)合分布式和并行處理技術(shù)來改進(jìn)查詢路由并縮減跳步數(shù)。

　　2相關(guān)研究工作

　　目前，國內(nèi)外對(duì)RFID發(fā)現(xiàn)服務(wù)解決方案的研究可以分為以下三種：

　　(1)集中式倉庫型

　　這種模式中有一個(gè)中央的全局?jǐn)?shù)據(jù)倉庫，物品在供應(yīng)鏈中移動(dòng)時(shí)所產(chǎn)生的EPCIS事件的詳細(xì)信息不僅存儲(chǔ)在企業(yè)本地，還要上傳到全局?jǐn)?shù)據(jù)倉庫.盡管這種模式容易實(shí)現(xiàn)，但對(duì)于海量數(shù)據(jù)的存儲(chǔ)以及提供有效的查詢響應(yīng)是相當(dāng)困難的;此外，這種模式缺乏對(duì)私密性的保護(hù)。

　　(2)集中式索引型

　　它是EPCglobal提出的一種改進(jìn)的模式，這種模式有一個(gè)全局的中央DS(Discovery Server).當(dāng)物品在供應(yīng)鏈中移動(dòng)時(shí)，供應(yīng)鏈各環(huán)節(jié)產(chǎn)生的EPCIS事件的詳細(xì)信息存儲(chǔ)在企業(yè)本地，而本地企業(yè)僅將輕量級(jí)的事件索引推送給中央Ds.這種模式在一定程度上保護(hù)了企業(yè)的隱私，并顯著降低了中央DS存儲(chǔ)的信息量，也降低了數(shù)據(jù)庫的查詢代價(jià).但這種模式提供的用戶接口較為復(fù)雜。

　　(3)跟蹤供應(yīng)鏈型

　　這種模式采用分布式結(jié)構(gòu)來代替上述兩種模式中的中央服務(wù)器.IBM和Microsoft公司目前正在從事該模式的研究，研究一種叫做“Theseos”的查詢引擎.這種查詢引擎綁定在每一個(gè)EPCIS上，接收來自本地用戶的查詢請(qǐng)求后，首先根據(jù)本地的數(shù)據(jù)和私密性策略對(duì)查詢請(qǐng)求進(jìn)行處理，然后根據(jù)本地查到的物品移動(dòng)信息修改原查詢請(qǐng)求和識(shí)別出相關(guān)參與方，并將修改后的查詢請(qǐng)求轉(zhuǎn)發(fā)給供應(yīng)鏈上的相關(guān)參與方.上述查詢過程叫做“Process and Forward”，該過程沿著供應(yīng)鏈中每個(gè)相關(guān)的EPCIS遞歸的重復(fù)執(zhí)行.每個(gè)相關(guān)的參與方將本地的查詢結(jié)果和從其它參與方返回的查詢結(jié)果進(jìn)行整合，并將整合的查詢結(jié)果轉(zhuǎn)發(fā)給向它發(fā)出查詢的參與方，最終所有關(guān)于該物品的查詢結(jié)果就會(huì)返回給發(fā)出初始查詢的客戶端.這種模式取消中央Ds，但是查詢響應(yīng)時(shí)間較第二種模式長，這是因?yàn)橐粋€(gè)初始查詢會(huì)衍生出多個(gè)新查詢，而且這些查詢的結(jié)果也需要經(jīng)過多次轉(zhuǎn)發(fā)才能返回到初始客戶端。

　　通過對(duì)上述三種模式的分析，第二種模式是建立在企業(yè)愿意共享EPCIS數(shù)據(jù)(如：事件的索引)的假設(shè)之上，一旦這個(gè)假設(shè)在以后的實(shí)際應(yīng)用中不成立，我們就會(huì)發(fā)現(xiàn)第三種模式更具可行性.因此，本文以第三種模式為研究重點(diǎn)，研究如何在這種模式的基礎(chǔ)上改進(jìn)查詢路由策略，以及減少查詢結(jié)果返回的轉(zhuǎn)發(fā)次數(shù)。

　　3一種分布式RFID發(fā)現(xiàn)服務(wù)系統(tǒng)

　　本節(jié)給出了RFID發(fā)現(xiàn)服務(wù)的一種分布式結(jié)構(gòu)，該結(jié)構(gòu)改進(jìn)了“跟蹤供應(yīng)鏈”模式(或者說“Theseos”方法).第一，客戶端的查詢請(qǐng)求不僅提交給本地的EPCIS，還可以提交給被查詢物品的所有生產(chǎn)商的EPCIS，而這些EPCIS可以根據(jù)被查詢物品的EPC編碼來查詢ONS得到.這樣處理以后，一個(gè)查詢就可以分解為多個(gè)并行的查詢流，從而可以提高查詢處理的效率.第二，通過本地緩存機(jī)制來處理并行查詢流之間的“查詢碰撞”.“查詢碰撞”是指由于多條查詢流并行，同一節(jié)點(diǎn)可能先后接收到其直接上下游節(jié)點(diǎn)發(fā)來的相同查詢.為了避免重復(fù)查詢，后來的查詢應(yīng)該被忽略.第三，供應(yīng)鏈中的每個(gè)節(jié)點(diǎn)將其本地查詢結(jié)果直接返回給發(fā)出初始查詢的節(jié)點(diǎn)，從而避免查詢結(jié)果沿著查詢轉(zhuǎn)發(fā)過來的路徑的反方向經(jīng)多次轉(zhuǎn)發(fā)回到客戶端。

　　3.1基本假設(shè)

　　本文提出的方法基于三個(gè)假設(shè)：(1)在同一個(gè)供應(yīng)鏈中，各參與方彼此共享它們的EPCIS數(shù)據(jù).調(diào)查表明，為了降低成本、加強(qiáng)重點(diǎn)業(yè)務(wù)和關(guān)鍵環(huán)節(jié)、尋找增加收入的新機(jī)會(huì)，業(yè)務(wù)伙伴之間是樂于共享業(yè)務(wù)信息的.(2)“one step back.one step forward”原則.ISO/DIS 22005提出了該原則，并詳細(xì)說明了可追溯性的要求，即每一個(gè)交易至少能夠確定它的直接上游(供應(yīng)方)和直接下游(接收方).(3)利用ONS.由于ONS系統(tǒng)已經(jīng)建立起來并投入了實(shí)際應(yīng)用，我們可以利用ONS來獲得物品的生產(chǎn)商的EPCIS地址。

　　3.2分布式結(jié)構(gòu)概述

　　RFID發(fā)現(xiàn)服務(wù)系統(tǒng)由安裝在各個(gè)EPCIS節(jié)點(diǎn)上的Ds引擎構(gòu)成，每個(gè)DS引擎僅為其所在的供應(yīng)鏈伙伴節(jié)點(diǎn)提供訪問內(nèi)部EPCIS信息的接口，每個(gè)Ds引擎只知道其直接上游和直接下游的節(jié)點(diǎn)的訪問接口地址.系統(tǒng)的總體結(jié)構(gòu)和查詢處理流程如圖1所示。

圖1 RFID發(fā)現(xiàn)服務(wù)系統(tǒng)的分布式結(jié)構(gòu)和查詢處理流程

　　這種分布式結(jié)構(gòu)下的查詢處理流程可分為4個(gè)階段，其中這種結(jié)構(gòu)的特點(diǎn)體現(xiàn)在(1)，(3)和(4)。

　　(1)發(fā)起查詢：首先，客戶端生成一個(gè)具有唯一標(biāo)識(shí)querylD的初始查詢，查詢參數(shù)是一組EPC編碼.然后，客戶端查詢現(xiàn)有的ONS服務(wù)，將所有Epc編碼一一交給ONS解析(步驟①).ONS返回EPC編碼對(duì)應(yīng)的生產(chǎn)商節(jié)點(diǎn)的EPCIs(或DS引擎)地址(步驟②).接著，客戶端分別向每個(gè)已知的EllIS并行發(fā)起對(duì)相應(yīng)EPc編碼的查詢，同時(shí)客戶端也將初始查詢交給本地DS引擎處理(步驟③顯示了2條并行查詢流)。

　　(2)處理并轉(zhuǎn)發(fā)：每個(gè)節(jié)點(diǎn)的DS引擎接收到查詢請(qǐng)求后首先查詢其本地EPCIS的相關(guān)動(dòng)態(tài)信息，然后根據(jù)本地查詢結(jié)果生成與其直接上游和直接下游相關(guān)的若干新查詢請(qǐng)求.然后，每個(gè)DS引擎并發(fā)地向其直接上游或直接下游發(fā)送對(duì)應(yīng)的新查詢請(qǐng)求(步驟④，⑥)，并且每個(gè)Ds引擎并發(fā)的將其本地查詢結(jié)果直接返回給發(fā)起查詢的客戶端(步驟⑤，⑦).這個(gè)過程沿著供應(yīng)鏈上相關(guān)的EPCIS遞歸地進(jìn)行，直到每條查詢流達(dá)到供應(yīng)鏈邊界節(jié)點(diǎn)或與另一條查詢流“碰撞”.圖1用白色“云朵”代表這些過程。

　　(3)解決“查詢碰撞”：DS引擎會(huì)把它已經(jīng)處理過的查詢忽略掉，例如，對(duì)圖1中的灰色矩形來說，若來自左側(cè)的查詢?cè)缬趤碜杂覀?cè)的查詢，并且兩個(gè)查詢具有相同的EPC編碼作為參數(shù)，則來自右側(cè)的查詢將被忽略.處理這種“查詢碰撞”既能避免重復(fù)查詢，又可避免在局部節(jié)點(diǎn)之間形成死鎖。

　　(4)合并所有查詢結(jié)果：客戶端將在預(yù)定的等待時(shí)間內(nèi)把從不同節(jié)點(diǎn)接收到的查詢結(jié)果整合、排序，得到最終查詢結(jié)果.因各節(jié)點(diǎn)是并發(fā)地返回結(jié)果，那么客戶端需分辨哪些結(jié)果屬于同一個(gè)初始查詢，為此，需要保證所有轉(zhuǎn)發(fā)的查詢的queryID與初始查詢保持一致。

　　3.3EPCIS模型

　　圖1 RFID發(fā)現(xiàn)服務(wù)系統(tǒng)的分布式結(jié)構(gòu)和查詢處理流程為了增加供應(yīng)鏈中物品的可跟蹤/追溯性，同時(shí)更加全面地描述供應(yīng)鏈活動(dòng)中產(chǎn)生的各種事件，尤其是對(duì)那些涉及到將原料加工制成新產(chǎn)品的業(yè)務(wù)事件，本節(jié)對(duì)圖1中每個(gè)EPCIS中的數(shù)據(jù)重新進(jìn)行建模.基于EPCglobal EPCIS Spedfieation Ratified Standard中定義的事件類型，我們給出了五種事件類型，其中包括一個(gè)基類事件和四個(gè)派生類事件，如圖2所示.它們可以表達(dá)在各個(gè)行業(yè)的供應(yīng)鏈活動(dòng)中產(chǎn)生的事件.根據(jù)假設(shè)(2)，我們?cè)贓PCIS的數(shù)據(jù)模型中加入了屬性“receiveFrom”和“sendTo”，分別表示某節(jié)點(diǎn)的直接上游(供應(yīng)方)和直接下游(接收方)。

圖2 EPCIS的數(shù)據(jù)模型

　　(1)EPCISEvent是所有事件類型的基類，它描述了EPCIS所捕獲事件的一般特征，包括事件的發(fā)生時(shí)間，發(fā)生地點(diǎn)以及基本的業(yè)務(wù)背景.eventTime是事件的發(fā)生時(shí)間;recordTime是事件的記錄時(shí)間，是一個(gè)可選的屬性：bizStep 是一個(gè)BusinessStepID，它記錄了事件所屬的業(yè)務(wù)步驟，通過該屬性可以實(shí)現(xiàn)業(yè)務(wù)步驟的跟蹤;org記錄了事件在哪個(gè)企業(yè)發(fā)生;bizLocation記錄了事件發(fā)生時(shí)所處的位置，例如，“warehouse #1”;readPoint記錄了事件在哪個(gè)物理位置發(fā)生，通常由物理讀寫器所標(biāo)識(shí)，例如，“dock door #12”。

　　(2)ObservationEvent 描述了“物品僅被觀察到但沒被處理”這樣一類事件.epcList是一個(gè)EPC編碼;receiveFrom記錄了物品的直接上游(供應(yīng)方)，它以GeneralManagerNumber的形式唯一標(biāo)識(shí)一個(gè)企業(yè);sendTo記錄了物品的直接下游(接受方)。在ObservationEvent中，receiveFrom和sendTo兩個(gè)屬性只能有一個(gè)有值。

　　(3)AggregationEvent表達(dá)了物品的包裝/組裝與解包裝/拆卸的發(fā)生，例如。“一些零件被裝入箱子中”。parentID標(biāo)識(shí)了包裝物品的容器，或是由多個(gè)部件組裝成的新物品;childEPCs是一個(gè)EPC編碼列表，它記錄了事件所涉及的所有被組裝的部件;action描述了事件中所發(fā)生的動(dòng)作，例如，“ADD”表示包裝/組裝。而“DELETE”表示解包裝/拆卸。

　　(4)QuantityEvent描述的事件只關(guān)注同一類物品的數(shù)量，而不關(guān)注具體的單品。epcClass描述了物品的種類;quantity記錄了該類物品的數(shù)量。

　　(5)TransfromEvent刻畫了多個(gè)物品經(jīng)過加工處理以后生成新物品的事件，例如，“一塊豬肉和一袋面粉加工成一些香腸”。materials是一個(gè)EPC編碼列表，記錄了所有的原材料;products也是一個(gè)EPC編碼列表，記錄了利用原材料加工成的所有物品。

　　上述四個(gè)派生類事件都通過一個(gè)“bizStep”屬性關(guān)聯(lián)了一個(gè)“業(yè)務(wù)處理步驟類”(BizStep)，它刻畫了事件發(fā)生時(shí)所處的業(yè)務(wù)背景。

　　3.4 查詢處理過程和算法

　　下面針對(duì)3.2節(jié)的每個(gè)階段給出具體算法，詳細(xì)討論查詢處理過程。首先定義算法中必要的數(shù)據(jù)結(jié)構(gòu)。

　　(1)發(fā)起查詢

　　這是本文對(duì)“跟蹤供應(yīng)鏈”模式的一點(diǎn)重要改進(jìn)，利用ONS的作用盡可能找到多個(gè)查詢?nèi)肟?，這樣在發(fā)起查詢時(shí)就可以并發(fā)執(zhí)行多個(gè)查詢流，下面用算法“startQuery”描述該過程。

　　(2)處理并轉(zhuǎn)發(fā)

　　該過程用算法“processAndRoute”描述，包括5個(gè)步驟：第一，檢查是否有“查詢碰撞”發(fā)生;第二，在本地EPCIS中執(zhí)行查詢(詳見3.5節(jié)queryLocal);第三，根據(jù)本次查詢和本地查詢的結(jié)果，重新生成若干與直接上下游節(jié)點(diǎn)相關(guān)的查詢(詳見3.5節(jié)rewriteQuery);第四，并行地將每個(gè)新查詢轉(zhuǎn)發(fā)給相應(yīng)的上下游節(jié)點(diǎn);最后，將本地查詢結(jié)果直接返回給初始客戶端。其中，后四步僅在未發(fā)生“查詢碰撞”時(shí)才執(zhí)行。

　　(3)解決“查詢碰撞”

　　采用本地結(jié)果緩存機(jī)制來解決“查詢碰撞”問題，將偶對(duì)(本地收到的查詢，對(duì)應(yīng)的本地查詢結(jié)果)利用某種機(jī)制(如Least Recently Used(LRU)，Time to Live(TTL))緩存起來.DS引擎在處理一個(gè)收到的查詢之前，先通過本地結(jié)果緩存檢查該查詢是否已被處理過，判斷條件是：該查詢與緩存中的某查詢具有同一queryID并且前者的epcList是后者epcList的子集.該過程用算法“cheekIfQueriesCollision”描述如下.

　　(4)合并所有查詢結(jié)果

　　既然每個(gè)DS引擎各自將其本地的查詢結(jié)果直接返回給初始客戶端，那么，經(jīng)過一段預(yù)定義的等待時(shí)間后，客戶端首先從返回的結(jié)果集合中選擇與初始查詢具有相同querylD的結(jié)果，得到一個(gè)結(jié)果子集，然后根據(jù)eventTime對(duì)該子集中所有EPCISEvents排序，形成最終應(yīng)答結(jié)果.該過程用算法“combineResults”描述如下.

　　3.5 processAndRoute相關(guān)細(xì)節(jié)

　　本節(jié)討論算法“processAndRoute”中兩個(gè)關(guān)鍵過程“queryLocal”和“rewriteQuery”.“queryLocal”負(fù)責(zé)對(duì)本地EPCIS執(zhí)行查詢：首先檢查本地結(jié)果緩存是否緩存了該查詢的結(jié)果.如果沒有緩存結(jié)果，則需要查詢本地EPCIs.因?yàn)锳ggregationEvent和TransformEvent記錄了與查詢的EPC編碼具有“包裝/組裝”、“解包裝/拆卸”或“加工變化”關(guān)系的其它EPC編碼，所以先查詢這兩類事件中與查詢的EPC編碼相關(guān)的事件，并找到與這些事件關(guān)聯(lián)的其他EPC編碼.然后將新發(fā)現(xiàn)的EPC編碼與原查詢的EPC編碼合并成一個(gè)集合，并在ObservationEventQuantityEvent這兩類事件中查詢與該合集中的任何一個(gè)EPC編碼關(guān)聯(lián)的所有事件.最后將本地查詢結(jié)果添加到本地結(jié)果緩存，并返回給初始客戶端.具體算法描述如下。

　　根據(jù)本地的查詢結(jié)果，“rewriteQuery”負(fù)責(zé)將查詢重寫成與其直接上、下游節(jié)點(diǎn)相關(guān)的新查詢請(qǐng)求.因?yàn)镺bservationEvent和QuantityEvent記錄了本地節(jié)點(diǎn)與其直接上、下游節(jié)點(diǎn)之間的物品收發(fā)(from-to)關(guān)系，所以需要對(duì)這兩類事件進(jìn)行分析：若某個(gè)事件具有receiveFrom屬性，則可生成向直接上游節(jié)點(diǎn)轉(zhuǎn)發(fā)的新查詢;若某個(gè)事件具有sendTo屬性，則可生成向直接下游節(jié)點(diǎn)轉(zhuǎn)發(fā)的新查詢.最后對(duì)所得的所有新查詢，將具有相同routeTo的查詢的epcList合并，這樣多個(gè)查詢合并為一個(gè)查詢以減少新查詢的數(shù)量.具體算法描述如下

　　表1 RFID發(fā)現(xiàn)服務(wù)查詢結(jié)果的一個(gè)實(shí)例

　　3.6 RFID發(fā)現(xiàn)服務(wù)的查詢結(jié)果

　　采用3.2-3.5節(jié)給出的RFID發(fā)現(xiàn)服務(wù)，能夠查詢到與給定物品(及其零件、原料)相關(guān)的、發(fā)生在供應(yīng)鏈不同節(jié)點(diǎn)的所有EPCISEvent集合.下面通過一個(gè)典型實(shí)例來描述RFID發(fā)現(xiàn)服務(wù)查詢結(jié)果的結(jié)構(gòu)：一件產(chǎn)品D由10個(gè)零件C組裝而成，每2個(gè)零件C由3件原料A和5件原料曰加工制成.D的制造商，從原料A的供應(yīng)商采購3000件原料A，從原料曰的兩個(gè)供應(yīng)商sal，sB2分別采購3000件和2000件原料B，用原料A，B加工制成一批零件C，然后把每10個(gè)零件C組裝成一件產(chǎn)品D，最后將100件D發(fā)給D的分銷商DD，DD又將50件D發(fā)給一個(gè)零售商%.表1列出了與產(chǎn)品Dl相關(guān)的查詢結(jié)果。

　　4算法性能分析

　　4.1效率實(shí)驗(yàn)分析

　　為了檢驗(yàn)本文提出的分布式發(fā)現(xiàn)服務(wù)的性能，我們實(shí)現(xiàn)了一個(gè)原型系統(tǒng)(DDs)，還實(shí)現(xiàn)了“Theseos”與DDS進(jìn)行對(duì)比.這兩個(gè)系統(tǒng)都是以webservice方式實(shí)現(xiàn)的，采用Java 1.5和JAX.WS 2.1技術(shù).節(jié)點(diǎn)間的所有通訊都以webservice調(diào)用方式進(jìn)行.ONS系統(tǒng)基于Berkeley Internet Name Domain(B帥)實(shí)現(xiàn).每個(gè)服務(wù)單獨(dú)運(yùn)行于一臺(tái)計(jì)算機(jī)上，每臺(tái)計(jì)算機(jī)配置了Pentium(R)Dual-Core2.5GI-Iz處理器、3GB RAM和相同的Windows、Microsoft SQL Server.實(shí)驗(yàn)的測試數(shù)據(jù)是人工生成的，在特定的供應(yīng)鏈網(wǎng)絡(luò)布局下，給出一定數(shù)量的不同物品以及產(chǎn)生這些物品的起始節(jié)點(diǎn)集合，然后采用以下數(shù)據(jù)生成規(guī)則：一個(gè)物品產(chǎn)生后，有四種可能發(fā)生的動(dòng)作(運(yùn)送到鄰居節(jié)點(diǎn)、同另一物品組裝起來或從一個(gè)物品中分離出來、被加工制成新的物品、不再被移動(dòng))，動(dòng)作的選擇是隨機(jī)進(jìn)行的，并且選擇“運(yùn)送到鄰居節(jié)點(diǎn)”的概率隨著該物品路徑長度的增加而減小.為了檢驗(yàn)上述兩個(gè)系統(tǒng)在查詢響應(yīng)時(shí)間上的效果，我們生成的測試數(shù)據(jù)包含一個(gè)最大長度為20的供應(yīng)鏈、0.5-1萬個(gè)物品和2.5-3萬條EPCIS事件。

　　我們測試了Recall查詢的總體運(yùn)行時(shí)間與物品在供應(yīng)鏈中移動(dòng)的最大長度之間的關(guān)系.圖3給出了對(duì)100個(gè)查詢的平均運(yùn)行時(shí)間，每個(gè)查詢都是從供應(yīng)鏈的一個(gè)前端開始尋找10個(gè)不同物品的所有Observation和Quantity事件.實(shí)驗(yàn)結(jié)果與預(yù)期的結(jié)果一致，由于查詢轉(zhuǎn)發(fā)次數(shù)和查詢結(jié)果逆向轉(zhuǎn)發(fā)次數(shù)的增加，Theseos方法的響應(yīng)時(shí)間隨著路徑長度的增加而增長，而DDS方法受此影響較小.在物品移動(dòng)路徑的長度≤6時(shí)，采用Theseos方法的查詢效率高于DDS方法，這是因?yàn)镈DS在將初始查詢分解為多個(gè)并行查詢流之前，需要查詢ONS服務(wù)，相比之下，Theseos方法直接發(fā)出一個(gè)查詢流，沒有訪問ONS的代價(jià)，所以在一定程度上(路徑長度≤6)響應(yīng)時(shí)間反而更短一些.但是隨著路徑的增長，DDS的優(yōu)勢(shì)(多個(gè)并行查詢流、直接返回查詢結(jié)果)越來越明顯，所以其響應(yīng)時(shí)間的增長率低于Theseos.圖4給出了相同實(shí)驗(yàn)配置下對(duì)BOM查詢的測試結(jié)果.在這個(gè)實(shí)驗(yàn)中，物品之間具有2—3層的包含關(guān)系，并且每個(gè)查詢都是尋找與物品相關(guān)的所有Observation，Quantity，Aggregation和Transform事件，因此響應(yīng)時(shí)間總體上大于Recall查詢.Theseos和DIY3在響應(yīng)時(shí)間上的對(duì)比情況同第一個(gè)實(shí)驗(yàn)類似，造成的原因相同。

圖3 Recall查詢的平均執(zhí)行時(shí)間

圖4 BOM查詢的平均執(zhí)行時(shí)間

　　上述兩組實(shí)驗(yàn)表明在物品移動(dòng)路徑較長(>6)時(shí)，DDS比Theseos方法具有較短的響應(yīng)時(shí)間.因而DDS更加適合較大規(guī)模的供應(yīng)鏈應(yīng)用，隨著生產(chǎn)和物流規(guī)模的擴(kuò)大，供應(yīng)鏈將涉及越來越多的屬于不同地區(qū)、國家甚至大洲的企業(yè)，最大路徑長度將很少在6以內(nèi)。

　　4.2網(wǎng)絡(luò)消息開銷分析

　　DDS和Theseos兩種方法在網(wǎng)絡(luò)消息開銷方面，采用量化分析.設(shè)尚待發(fā)現(xiàn)的供應(yīng)鏈實(shí)例∞：(n，e>，其中n為供應(yīng)鏈拓?fù)浣Y(jié)構(gòu)圖的節(jié)點(diǎn)數(shù)目，且所有節(jié)點(diǎn)均正常工作，e為節(jié)點(diǎn)之間的邊數(shù);i為DDS中初始查詢首次分解成的并行查詢數(shù)目;X為供應(yīng)鏈中單次消息轉(zhuǎn)發(fā)的網(wǎng)絡(luò)開銷，y為DDS中單次查詢ONS的網(wǎng)絡(luò)開銷.因?yàn)門heseos中遞歸的查詢轉(zhuǎn)發(fā)過程和結(jié)果返回過程相當(dāng)于2次遍歷陽的所有邊，故網(wǎng)絡(luò)消息開銷為cr=2Xe.因?yàn)镈DS中解決了“查詢碰撞”，避免了重復(fù)查詢，所以多個(gè)并行查詢流的轉(zhuǎn)發(fā)過程當(dāng)于遍歷sc的所有邊，而結(jié)果返回過程是各節(jié)點(diǎn)直接返回給發(fā)起初始查詢的節(jié)點(diǎn)，再加上查詢ONS和首次發(fā)出并行查詢流的網(wǎng)絡(luò)開銷，總計(jì)

　　但由于X，Y，是常數(shù)，i通常較小。故開銷相差不會(huì)很大;(2)隨著e變大，必然使co

　　4.3可用性分析

　　在可用性方面，若DDS和Theseos均不采用額外措施，則在某節(jié)點(diǎn)故障時(shí)，當(dāng)前查詢均失敗，但由于DDS中多個(gè)并行查詢流的存在，其它查詢流還可以訪問到更多的節(jié)點(diǎn)，從而獲得比Theseos更豐富的查詢結(jié)果，尚可滿足一定的用戶需求.當(dāng)目標(biāo)節(jié)點(diǎn)故障時(shí)，源節(jié)點(diǎn)可將該查詢轉(zhuǎn)發(fā)到其所知的某個(gè)(些)鄰居節(jié)點(diǎn)，但不能保證查詢能從這個(gè)(些)鄰居節(jié)點(diǎn)延續(xù)下去.由于節(jié)點(diǎn)之間沒有信息冗余備份機(jī)制(這是由EPCIS的私密性決定的)，解決節(jié)點(diǎn)故障的策略尚需進(jìn)一步研究.但可以說，在同等條件下，DDS比Theseos更具有可用性。

　　5結(jié)論

　　本文針對(duì)大規(guī)模的RFID應(yīng)用，提出了一種新的具有分布式結(jié)構(gòu)的RFID發(fā)現(xiàn)服務(wù)，用來在完全分布式的EPCIS節(jié)點(diǎn)中發(fā)現(xiàn)物品在供應(yīng)鏈中發(fā)生的業(yè)務(wù)事件.首先，本文擴(kuò)展的EPCIS事件模型適用于對(duì)供應(yīng)鏈中物品的跟蹤和追溯，并且新增加的事件類型“TransformEvent”進(jìn)一步滿足了實(shí)際應(yīng)用需求，用來對(duì)那些涉及到將原料加工制成新產(chǎn)品的業(yè)務(wù)事件建模.本文提出的分布式RFID發(fā)現(xiàn)服務(wù)(DDs)，綜合了分布式技術(shù)和并行處理技術(shù)，給出了基于ONS的并行查詢模式，改進(jìn)了查詢的轉(zhuǎn)發(fā)機(jī)制并且減少了查詢結(jié)果返回的路由跳數(shù).通過與Theseos方法的對(duì)比實(shí)驗(yàn)表明，供應(yīng)鏈的規(guī)模越大(如最大路徑越長)，DDS方法比Theseos方法具有更高的查詢效率.

　　DDS系統(tǒng)目前已應(yīng)用于酒類防偽，跟蹤產(chǎn)品在生產(chǎn)商、批發(fā)商、零售商等供應(yīng)鏈環(huán)節(jié)的移動(dòng)細(xì)節(jié)，追溯產(chǎn)品來源以達(dá)到防偽目的;還應(yīng)用于志愿者卡管理，將REID編碼嵌入志愿卡證，可實(shí)時(shí)監(jiān)控志愿者所在崗位，以及追溯志愿者從事志愿活動(dòng)的歷史記錄，方便對(duì)志愿活動(dòng)的組織和管理.下一步，我們需要進(jìn)一步研究DDS的服務(wù)質(zhì)量(QoS)模型和控制方法，使發(fā)現(xiàn)服務(wù)的服務(wù)質(zhì)量得以量化和評(píng)估.另外，RFID發(fā)現(xiàn)服務(wù)的最終目的是讓供應(yīng)鏈上的各企業(yè)充分利用發(fā)現(xiàn)的數(shù)據(jù)集，從而改進(jìn)自己的關(guān)鍵業(yè)務(wù)環(huán)節(jié)甚至供應(yīng)鏈結(jié)構(gòu)，因此將來還要研究針對(duì)發(fā)現(xiàn)服務(wù)查詢結(jié)果的分析方法。