1引言

　　RFID(Radio Frequency Identification)技術是一種非接觸、多目標、移動目標識別的自動識別技術，近年來成為自動識別領域的研究熱點.該技術可以廣泛應用于物流供應鏈、食品安全、防偽、身份識別、軍事等方面.針對大型開環的RFID應用，特別是供應鏈環境下的應用，需要建立跨地區、跨行業的RFID公共服務基礎設施和信息共享機制，作為核心公共服務之一的RFID發現服務，負責收集物品在生命周期內的過程信息，即將分布的物品信息按時問序列整合成完整的物品信息鏈。

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

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

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

　　2相關研究工作

　　目前，國內外對RFID發現服務解決方案的研究可以分為以下三種：

　　(1)集中式倉庫型

　　這種模式中有一個中央的全局數據倉庫，物品在供應鏈中移動時所產生的EPCIS事件的詳細信息不僅存儲在企業本地，還要上傳到全局數據倉庫.盡管這種模式容易實現，但對于海量數據的存儲以及提供有效的查詢響應是相當困難的;此外，這種模式缺乏對私密性的保護。

　　(2)集中式索引型

　　它是EPCglobal提出的一種改進的模式，這種模式有一個全局的中央DS(Discovery Server).當物品在供應鏈中移動時，供應鏈各環節產生的EPCIS事件的詳細信息存儲在企業本地，而本地企業僅將輕量級的事件索引推送給中央Ds.這種模式在一定程度上保護了企業的隱私，并顯著降低了中央DS存儲的信息量，也降低了數據庫的查詢代價.但這種模式提供的用戶接口較為復雜。

　　(3)跟蹤供應鏈型

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

　　通過對上述三種模式的分析，第二種模式是建立在企業愿意共享EPCIS數據(如：事件的索引)的假設之上，一旦這個假設在以后的實際應用中不成立，我們就會發現第三種模式更具可行性.因此，本文以第三種模式為研究重點，研究如何在這種模式的基礎上改進查詢路由策略，以及減少查詢結果返回的轉發次數。

　　3一種分布式RFID發現服務系統

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

　　3.1基本假設

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

　　3.2分布式結構概述

　　RFID發現服務系統由安裝在各個EPCIS節點上的Ds引擎構成，每個DS引擎僅為其所在的供應鏈伙伴節點提供訪問內部EPCIS信息的接口，每個Ds引擎只知道其直接上游和直接下游的節點的訪問接口地址.系統的總體結構和查詢處理流程如圖1所示。

圖1 RFID發現服務系統的分布式結構和查詢處理流程

　　這種分布式結構下的查詢處理流程可分為4個階段，其中這種結構的特點體現在(1)，(3)和(4)。

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

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

　　(3)解決“查詢碰撞”：DS引擎會把它已經處理過的查詢忽略掉，例如，對圖1中的灰色矩形來說，若來自左側的查詢早于來自右側的查詢，并且兩個查詢具有相同的EPC編碼作為參數，則來自右側的查詢將被忽略.處理這種“查詢碰撞”既能避免重復查詢，又可避免在局部節點之間形成死鎖。

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

　　3.3EPCIS模型

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

圖2 EPCIS的數據模型

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

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

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

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

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

　　上述四個派生類事件都通過一個“bizStep”屬性關聯了一個“業務處理步驟類”(BizStep)，它刻畫了事件發生時所處的業務背景。

　　3.4 查詢處理過程和算法

　　下面針對3.2節的每個階段給出具體算法，詳細討論查詢處理過程。首先定義算法中必要的數據結構。

　　(1)發起查詢

　　這是本文對“跟蹤供應鏈”模式的一點重要改進，利用ONS的作用盡可能找到多個查詢入口，這樣在發起查詢時就可以并發執行多個查詢流，下面用算法“startQuery”描述該過程。

　　(2)處理并轉發

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

　　(3)解決“查詢碰撞”

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

　　(4)合并所有查詢結果

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

　　3.5 processAndRoute相關細節

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

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

　　表1 RFID發現服務查詢結果的一個實例

　　3.6 RFID發現服務的查詢結果

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

　　4算法性能分析

　　4.1效率實驗分析

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

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

圖3 Recall查詢的平均執行時間

圖4 BOM查詢的平均執行時間

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

　　4.2網絡消息開銷分析

　　DDS和Theseos兩種方法在網絡消息開銷方面，采用量化分析.設尚待發現的供應鏈實例∞：(n，e>，其中n為供應鏈拓撲結構圖的節點數目，且所有節點均正常工作，e為節點之間的邊數;i為DDS中初始查詢首次分解成的并行查詢數目;X為供應鏈中單次消息轉發的網絡開銷，y為DDS中單次查詢ONS的網絡開銷.因為Theseos中遞歸的查詢轉發過程和結果返回過程相當于2次遍歷陽的所有邊，故網絡消息開銷為cr=2Xe.因為DDS中解決了“查詢碰撞”，避免了重復查詢，所以多個并行查詢流的轉發過程當于遍歷sc的所有邊，而結果返回過程是各節點直接返回給發起初始查詢的節點，再加上查詢ONS和首次發出并行查詢流的網絡開銷，總計

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

　　4.3可用性分析

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

　　5結論

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

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