通過有噪聲空中信道有效讀取具有唯一標識號的一組射頻標識標籤的方法
2023-07-15 00:07:36
專利名稱：通過有噪聲空中信道有效讀取具有唯一標識號的一組射頻標識標籤的方法
技術領域：
本發明涉及在射頻標識(RFID)標籤與RFID讀取器之間進行通信的方法。
背景技術：
在RFID系統中，在給定的通信範圍內，可以要求RFID讀取器區別大量不同RFID標籤並與大量不同RFID標籤通信。如果利用唯一標識號分別識別每個不同RFID標籤，則RFID讀取器必須能夠迅速、準確讀取與每個標籤關聯的標識號。然而，當RFID讀取器與標籤之間的通信信道被噪聲破壞時，可能降低RFID迅速、準確識別RFID標籤的能力。
先前的RFID讀取器通常使用用於讀取一組RFID標籤的算法的某種變型。該算法試圖順序讀取從最強到最弱返回信號排序的標籤。在分別讀取了每個RFID標籤後，它被關閉。從一次標籤讀取到另一次標籤讀取，不傳送信息。儘管該技術容易在RFID讀取器內實現，但是在存在噪聲時，它卻非常脆弱。
RFID系統的一個主要應用是電子庫存。在當今的商業中，維持精確的商品庫存非常重要。過去，完全利用人工方法獲得庫存，因此，速度慢，而且昂貴。在RFID電子庫存系統中，RFID標籤附加在要編入庫存的每個項目(item)上。分別對每個RFID標籤分配唯一的標籤標識號。
在典型應用中，許多有標籤的項目堆垛在貨架上。讀取器位於分配鏈上的各點上，以讀取有標籤的項目並將它們編入庫存。例如，一個或者多個讀取器可以位於裝料場門口。當貨架通過該裝料場門口時，該讀取器詢問位於貨架上的一組標籤。位於該堆垛內部的項目上的標籤的信號比外部標籤的信號弱，因為其信號必須通過的該貨架上的項目比外部標籤要通過的該貨架上的項目多。因此，可能難以讀取內部標籤的信號。此外，許多RFID庫存應用在噪聲RF環境下工作。
因此，需要一種以在讀取過程中或者在讀取過程之前，對噪聲魯棒而且優化使用該RFID讀取器或者其它RFID讀取器或者用於編譯RFID讀取器的信息的其它系統獲得的過去信息的方式，使RFID讀取器有效讀取一組RFID標籤的替換技術。
還需要一種在RFID讀取器與一組RFID標籤進行通信、將讀取速度和弱響應RFID標籤的精度提高到最高的方法。
發明內容
本發明涉及一種通過有噪聲信道利用唯一標識號讀取一組射頻標識(RFID)標籤的系統和方法。根據本發明的各方面，RFID系統包括一個或者多個讀取器，每個讀取器分別具有處理模塊和存儲器。存儲器存儲一組關於二叉樹數據結構(二叉樹)上的每個節點的信息。該組信息包括活動寄存器、「0」位計數器和「1」位計數器。還可以存儲該節點的其它特性，例如，該節點的路徑長度。
根據又一個方面中，處理模塊包括邏輯。該邏輯使RFID讀取器有效讀取二叉樹，該二叉樹特性化在該讀取器的通信範圍內選擇具有唯一標識號的RFID標籤。根據本發明的一個方面，當讀取器從一組標籤接收一個或者多個響應信號時，該讀取器調整對正遍歷的當前節點存儲的信息。如果僅收到「0」，則該讀取器使活動寄存器的值遞增、使「0」計數器遞增而使「1」計數器遞減。如果僅收到「1」，則該讀取器使活動寄存器的值遞增、使「1」計數器遞增而使「0」計數器遞減。如果兩個均收到，則該讀取器使兩個計數器以及活動寄存器遞增。此外，為了優化讀取周期的效率，該讀取器還評估存儲的節點信息，以確定要遍歷二叉樹上的哪個分支。
本發明還涉及一種在存在在利用檢錯碼處理進行二叉樹遍歷期間產生的錯誤時，用於識別有效標籤的系統和方法。根據本發明實施例的一個方面，在二叉樹遍歷期間，讀取器確定標籤標識號上的一個或者多個位位置可能被破壞。利用該信息，讀取器確定一組可能有效標識號。關於每個可能標識號，讀取器計算檢錯碼值。然後，讀取器確定計算的檢錯碼值是否與從被讀取的標籤接收的檢錯碼值匹配。如果計算的值匹配，則關聯標識號是有效標籤標識號。
根據下面對本發明所做的詳細說明，本發明的這些以及其它目的、優點和特徵將變得更加容易理解。
在此，附圖引入本說明書並作為本說明書的一部分，它示出本發明，而且與描述一起進一步說明本發明原理，從而使相關技術領域內的技術人員實現和使用本發明。
圖1是根據本發明實施例其中一個或者多個標籤讀取器與一個或者多個標籤通信的環境的方框圖。
圖2A是根據本發明實施例在一個或者多個讀取器與一個或者多個標籤進行通信的體系結構概況的方框圖。
圖2B是根據本發明實施例的說明性讀取器的方框圖。
圖3是根據本發明實施例具有與每個節點關聯的信息的示例二叉樹的示意圖。
圖4是根據本發明實施例使用從讀取器的觀點出發加權的遍歷路徑的讀取詢問操作的流程圖。
圖5A是示出根據本發明實施例確定下一個讀取器位的方法的流程圖；圖5B是示出根據本發明實施例確定下一個讀取器位的替換方法的流程圖。
圖6是具有被噪聲破壞的位位置的示例標籤的示意圖；圖7是示出根據本發明實施例利用檢錯碼處理識別標籤的方法的流程圖。
圖8是示出根據本發明實施例利用多個檢錯碼過程識別標籤的方法的流程圖。
現在，將參考
本發明。在各圖中，同樣的參考編號可以表示同樣或者功能類似的單元。此外，參考編號最左側(各)數字可以識別參考編號首先出現的附圖。
具體實施例方式
1.前言1.1標籤詢問環境在詳細說明本發明之前，對可以實現本發明的示例環境進行說明是有幫助的。本發明尤其可以用於在噪聲環境下操作的射頻標識(RFID)應用。圖1示出根據本發明其中一個或者多個RFID標籤讀取器104與一組示例(a population of)RFID標籤120通信的環境100。如圖1所示，一組標籤120包括7個標籤102a-102g。根據本發明實施例，一組標籤120可以包括任何數量的標籤102。在某些實施例中，在一組標籤120中可以包括非常多的標籤102，包括幾百、幾千甚或更多。
示例環境100還包括一個或者多個讀取器104，這些讀取器104可以單獨操作，或者可以連接在一起，形成讀取器網絡，如圖2所示。外部應用可以請求讀取器104，以尋址一組標籤120。作為一種選擇，讀取器可以具有用於啟動通信的內部邏輯。在讀取器不與一組標籤通信時，讀取器104通常不發出RF能量。這樣允許其它讀取器從不同的方向對同樣的一組標籤起作用，從而儘可能被進入整個一組標籤的RF信號完全覆蓋。此外，利用不同的頻率，同一個讀取器還可以對同樣的一組標籤起作用，以增大標籤覆蓋面。
根據本發明，根據一個或者多個詢問(interrogation)協議，在讀取器104與標籤102之間交換信號110和112。示例詢問協議是下面描述的二叉樹(binary tree)遍歷協議。信號110和112是無線信號，例如，射頻(RF)發射。在收到信號110時，根據基於時間的圖形或者頻率，利用信號110的交替反射和吸收部分，標籤102可以產生響應信號112。在此，將交替吸收和反射信號110的技術稱為反向散射調製。本發明還可以應用於以其它方式通信的RFID標籤。
圖2A是根據本發明實施例提供一個或者多個讀取器104與標籤102進行通信的示例RFID系統200的方框圖。RFID系統200包括用戶應用域290、讀取器104a-n的網絡以及一個或者多個標籤102。請注意，本發明可以應用於單個讀取器，而且可以應用於多個通過網絡連接的讀取器，如圖2所示。因此，儘管在此通常稱為「讀取器」，但是應該明白，根據特定應用的需要，本發明可以應用於任何配置的任何數量的讀取器。
通過一個或者多個天線210，每個讀取器104分別與標籤102進行通信。可以使用各種天線配置。例如，在實施例中，讀取器104a可以直接連接到至多4個天線(例如，天線210a-210d)。在另一個示例實施例中，讀取器104b連接到復用器，並控制該復用器。復用器可以使更多的天線轉換到讀取器的多個天線埠。這樣，讀取器104b可以容納更多的天線。
用戶應用域290可以包括一個或者多個用戶應用。通過通信網或者數據鏈路，用戶應用可以與一個或者多個讀取器104通信。在高電平，讀取器可以從用戶應用域290接收關於一個或者多個標籤102的請求。例如，應用可以請求讀取器詢問一組標籤。
讀取器104a-n分別包括處理模塊240和存儲器250。圖2B是根據本發明實施例的說明性RFID讀取器104的方框圖。如圖2B的示例實施例所示，處理模塊240可以包括邏輯270以根據存儲在存儲器250內的節點信息確定遍歷路徑。邏輯270使RFID讀取器有效讀取二叉樹，該二叉樹特性化在讀取器的通信範圍內採集的具有唯一標識號的RFID標籤。在讀取周期，讀取標籤組內的所有標籤導致重複通過多個標籤公用的位序列。此外，讀取器通常對一組標籤執行多個讀取周期。因此，甚至標籤的唯一標識號也被讀取多次。本發明的處理邏輯不刪除重複通過二叉樹期間採集的信息。相反，讀取器編譯表示佔用二叉樹上的每個節點的信息。因為特定節點對許多採樣的隨機噪聲的平均值為0，而系統信號的平均值不為0，所以通過對許多試驗計算平均值，可以提高該二叉樹上的任何位的信噪比。在位速率非常高時，該讀取器邏輯可以將標籤讀取速度提高高達一個數量級。
此外，處理模塊240還可以包括邏輯280，以根據檢錯處理識別標籤標識號。
存儲器250存儲與一組標籤120關聯的數據。在實施例中，配置存儲器250，以存儲兩個用於二叉遍歷樹上的各節點的寄存器/計數器。第一計數器260存儲「1」符號的權重，而第二計數器265存儲位於該節點的「0」符號的權重。此外，配置存儲器250，以存儲二叉遍歷樹的每個節點的活動(activity)寄存器230。
在實施例中，配置存儲器250，以僅存儲所使用的二叉樹上的各節點的信息。例如，對於取用路徑(populated path)上的每一節點，配置存儲器250，以存儲一個或者多個計數器。相關技術領域內的技術人員明白，還存在用於將標籤組數據存儲到存儲器250內的其它選擇。
可以根據讀取器104的實現和體系結構，改變用於存儲節點專用信息的方法。實現存儲的例子包括一個或者多個數據陣列或者連結表。相關技術領域內的技術人員明白，存在用於存儲的其它選擇。
此外，請注意，術語「計數器」並不意味著特定實現。可以利用寄存器，或者以包括硬體、軟體、固件或者其任何組合的另一種方式，分別實現每個計數器。
與其它讀取器104或者與其它應用共享與存儲在存儲器250內的一組標籤120有關的數據。例如，讀取器104a可以與讀取器104b共享其與一組標籤120有關的編譯數據(例如，加權樹信息)。還可以將編譯數據存儲到位於用戶域290或者其它位置的資料庫內。在實施例中，將與一組標籤120關聯的編譯知識或者指向含有該知識的地址的索引存儲到諸如標籤102或者條形碼的單獨裝置上。例如，條形碼可以含有指向一組標籤數據的存儲地址的索引。在實施例中，讀取器104(或者應用)可以將與存儲在另一個讀取器104內的一組標籤120有關的數據預先裝載到其存儲器250上的資料庫或者其它裝置上。
圖3示出存儲在存儲器250上的一組示例節點數據的邏輯表示。圖3示出在根層之下具有3層的二叉遍歷樹300的示意圖，其中每層分別對應於標籤標識號的位位置。請注意，為了說明問題，示出3層，但是本發明可以應用於任意大小的節點數據集。該二叉樹具有14個節點310a-o。每個節點分別具有關聯「0」計數器265和「1」計數器260，如上所述。每個節點還可以含有活動寄存器。此外，可以存儲特性化節點的其它參數，例如，該節點的遍歷路徑的長度。除了位於該樹最低層的節點(節點310h-310o)，從每個節點伸出兩個分支。對於每對分支，「0」分支向左遞減，而「1」分支向右遞減。
在實施例中，在遍歷一個節點時，在讀取器每次接收「0」符號時，使該節點上的「0」計數器265的值遞增。在遍歷一個節點時，在讀取器每次不接收「0」符號時，使位於該節點的「0」計數器265的值遞減。同樣，在遍歷一個節點時，在讀取器每次接收「1」符號時，使該節點上的「1」計數器260的值遞增。在遍歷一個節點時，在讀取器每次不接收「1」符號時，使位於該節點的「1」計數器260的值遞減。相關技術領域內的技術人員明白，在變換實施例中，可以以其它方式遞增或者遞減該計數器，以跟蹤接收的符號。
在實施例中，如果存在，則活動寄存器可以用於檢測二叉樹的未使用部分或者待使用部分。例如，在實施例中，在一組標籤的讀取周期期間，在每次遍歷節點時，使活動寄存器遞增。在二叉樹協商之外，在對該應用設置的預定間隔，時該樹上的所有活動寄存器遞減。其活動寄存器降低到低於最小閾值的各節點被標記為死，而且現在可以被重新分配到該樹的新分支或者其它分支。這樣，利用一組RFID，二叉樹和該樹上的信息以連續方式生長和演變。
相關技術領域內的技術人員明白，可以在各種讀取器平臺和讀取器網絡配置上實現本發明。
1.2詢問協議根據本發明實施例，為了在讀取器104與位於該讀取器的通信範圍內的一組標籤120之一進行通信，採用二叉樹遍歷分類。根據這種實施例，利用唯一標識號分別識別每個標籤102。下面示出示例唯一標籤標識號的布局。
每個唯一標籤標識號分別嵌入標籤標識位和檢錯碼位。例如，每個唯一標籤標識號可以分別具有九十六(96)位的標識號和16位的檢錯碼值。然而，本發明可以應用於其它標籤標識號長度和檢錯碼長度。在該文獻中，嵌入的標籤標識號(例如，96位數字)被稱為標籤標識號。
在實施例中，通過要求以頻率分離方式從每個標籤102到讀取器104的傳輸是唯一的，可以避免標籤102之間的爭用，但是也可以以其它方式避免標籤102之間的爭用。通過以破壞性幹擾互相的試傳輸的同樣頻率、時間和/或相位進行多次傳輸，可以將爭用定義為通信。因此，在示例二叉遍歷算法中，在讀取器104與該讀取器尋址的當前一組標籤102之間，在某個時間，協商一位信息。利用一個頻率表示0，另一個頻率表示1的兩個頻率分別確定每個標籤響應。這樣，許多標籤可以同時、非破壞性地傳送數據0。讀取器不能將單個數據0與多個數據0區別開並不重要，只要存在數據0。作為一種選擇，例如，利用一個時間周期用於「0」，另一個時間周期用於「1」的兩個時間周期，可以確定標籤響應。
在實施例中，二叉樹遍歷過程從通信中刪除標籤，直到僅隔離和驗證具有唯一數的一個標籤。如上所述，二叉樹上的每層分別表示標籤標識號上的位位置。由於讀取器繼續通過二叉樹上的節點(和層)，所以它使一個子集的一組標籤的保持活動，使一個子集的一組標籤不活動。例如，最後發送匹配位(matching bit)的標籤保持活動，而最後未發送匹配位的標籤保持不活動。根據統計，在每次進行位交換時，一組標籤的一半是不活動的。該過程繼續，直到讀取器到達二叉樹上的最後一層上的節點，導致唯一標籤隔離和刪除。重複該過程，直到一組標籤內的每個標籤被隔離。
關於二叉樹遍歷分類的更多信息，請參考下面的美國未決專利申請2002年2月12日提交的、標題為「Method，System and Apparatusfor Binary Traversal of a Tag Population」、律師案號為第1689.0210001號、系列號為第10/072,885號專利申請；以及2002年2月12日提交的、標題為「Method，System and Apparatus forCommunication with a RFID Tag Population」、律師案號為第1689.0260000號、系列號為第10/073,000號專利申請。關於RFID讀取器與一組RFID標籤之間的通信的更多信息，請參考標題為「Systemand Method for Electronic Inventory」的美國專利以及1999年6月1日提交的、標題為「System and Method for Electronic Inventory」、律師案號為第1689.0010001號、系列號為第09/323,206號專利申請。
2.採用遍歷路徑加權的二叉樹遍歷圖4是示出根據示例實施例的本發明的操作過程的流程圖400。該流程圖示出為了提高詢問一組標籤的效率，本發明採用的遍歷路徑。本發明與讀取器使用的二叉樹遍歷協議一起工作。上面說明了二叉樹遍歷協議的例子。繼續參考上述圖2所示的示例環境說明流程圖400。然而，本發明並不局限於該環境。請注意，流程圖400所示的某些步驟不必以所示的順序執行。
當讀取器104開始二叉樹遍歷一組標籤120時，流程圖400以步驟410開始。本發明可以與任何二叉樹遍歷詢問技術一起使用。示例的詢問技術包括通用讀取技術(還稱為全場讀取)、專用讀取技術以及成組讀取技術。通用讀取技術包括讀取可以檢測到的一組標籤內的每個標籤。利用特定位圖形，專用讀取技術遍歷一組標籤。成組讀取技術是專用讀取技術和通用讀取技術的混合技術。
在開始二叉樹遍歷後，在步驟415，讀取器進入二叉樹上的節點(例如，圖3所示的節點310a-o之一)。作為二叉遍歷協議的一部分，在該二叉樹上的每個節點，讀取器發送信號以啟動一組標籤發出響應。在示例的二叉樹遍歷協議中，該響應含有表示至少一個標籤的標識號內的位的符號。
在步驟420，讀取器確定是否從一組標籤收到響應。如果未收到響應，則操作進入步驟490。如果已經收到響應，則操作進入步驟430。
在步驟430，讀取器確定遍歷哪個分支(即，收集哪個位作為讀取的標籤標識號的下一位)。作為步驟430的示例實施例，圖5A示出用於確定要遍歷哪個分支的流程圖530A。例如，在確定讀取過程可能受到噪聲影響時，讀取器可以使用流程圖530A所示的方法。在存在噪聲時，流程圖530A利用遍歷路徑加權隔離標籤響應。
在步驟541，讀取器確定當前節點是否是分支節點。分支節點是已經收到「0」響應值和「1」響應值，而且讀取器必須判定遍歷哪個分支的節點。如果該節點不是分支節點(即，僅收到一個響應值)，則操作進入步驟542。如果該節點是分支節點(即，收到兩個響應值)，則操作進入步驟545。
在步驟542，讀取器選擇對應於收到的信號值的分支，然後，操作進入步驟452。
在步驟543，讀取器確定接收信號之一或者二者是否可能或者有可能由噪聲或者某個其它問題引起。讀取器根據存儲在存儲器250內的節點信息的評估進行該確定。例如，因為，在讀取周期，讀取器可以多次通過特定節點，與標籤取用路徑上的各分支關聯的計數器260和265始終具有高值，而未取用分支使計數器260和265始終具有較低的值。因此，在確定步驟，計數器260和265可以用作加權因數。例如，如果「1」計數器260非常正，而「0」計數器265非常負，或者是0，則讀取器104確定「0」符號可能由噪聲引起，因此，選擇正加權「1」分支遍歷。讀取器還可以將該節點的遍歷路徑的長度(即，該節點之前遍歷的節點數)看作錯誤路徑的可能指示。
在步驟549，如果讀取器確定在步驟543兩個信號均不可能或者沒有可能由噪聲引起，則讀取器應用預設首選技術，選擇分支進行遍歷。例如，讀取器可以具有最強信號的預設首選。作為一種選擇，讀取器可以具有特定位(bit)值，例如，位「0」或者位「1」的預設首選。
在步驟544，如果讀取器確定一個接收符號在步驟543可能或者有可能由噪聲引起，則讀取器選擇對應於其它接收信號值的分支。該技術可以提高在該路徑上發現有效標籤的可能性。因為噪聲的瞬變性質，所以在後續遍歷期間，在同一個節點上存在噪聲的可能性非常小。因此，如果在後面的遍歷期間，讀取器到達同一個節點，則在該節點不太可能存在噪聲信號。因此，因為有噪聲，所以通過不錯誤遍歷未取用的路徑，讀取器可以提高效率。
如果讀取器確定接收的符號二者均可能或者有可能由噪聲引起，則該讀取器可以選擇終止遍歷該路徑，而開始遍歷另一個路徑。作為一種選擇，讀取器可以選擇一個分支進行遍歷(與步驟544相似)，然後，控制進入步驟452。如果兩個信號均是噪聲，則在下一個節點，標籤響應將「丟失(drop out)」。
圖5B是示出對於步驟430在本發明的變換實施例中用於確定下一個讀取器位值的流程圖530B。例如，在確定讀取過程受到噪聲影響的可能性小，或者沒有可能時，讀取器可以使用流程圖530B的方法。流程圖530B利用遍歷路徑加權隔離和讀取弱標籤或者未讀取的標籤。弱標籤可能是其信號難以讀取的標籤。
步驟541和542與上面參考流程圖530A描述的步驟541和542相同。在步驟541，讀取器確定當前節點是否是分支節點。如果該節點不是分支節點(即，僅收到一個響應值)，則操作進入步驟542。如果該節點是分支節點(即，兩個響應值均收到)，則操作進入步驟547。
在步驟542，讀取器選擇對應於收到的信號值的分支，然後，操作進入步驟452。
在步驟547，讀取器確定是否可能或者有可能接收信號之一或者二者來自弱標籤或者未讀取標籤。讀取器根據存儲在存儲器250內的節點信息的評估進行該確定。例如，如果「1」計數器260非常正，而「0」計數器非常負，或者是0，則該讀取器確定收到的「0」信號可能是弱標籤發出的，因此，選擇「0」分支進行遍歷。
如果在步驟547，讀取器確定可能或者有可能一個接收符號可能來自弱標籤，則操作進入步驟548。在步驟548，讀取器選擇對應於弱標籤的接收信號值的分支。
如果在步驟547，讀取器確定兩個信號可能或者有可能均不是來自弱標籤，則操作進入步驟549。
在步驟549，讀取器利用預設首選技術選擇分支進行遍歷。例如，讀取器可以具有最強信號的預設首選。作為一種選擇，該讀取器可以具有諸如位「0」或者位「1」的特定位值的預設首選。
在完成流程圖530A或者530B後，操作進入步驟452。在步驟452，讀取器使活動寄存器遞增(如果在步驟420，收到「0」符號或者「1」符號)。
在步驟453，如果收到的位等於0，則操作進入步驟454。在步驟454，讀取器網絡使該節點的「0」計數器265遞增，然後，操作進入步驟456。在步驟453，如果收到的位不等於0，則操作進入步驟455。在步驟455，讀取器網絡使「0」計數器265遞減。然後，操作進入步驟456。
在步驟456，如果收到的位等於1，則操作進入步驟457。在步驟457，讀取器網絡使該節點的「1」計數器260遞減，然後，操作進入步驟460。在步驟456，如果收到的位不等於1，則操作進入步驟458。在步驟458，讀取器網絡使該節點的「1」計數器260遞減，而且操作進入步驟460。
在本發明的實施例中，「1」計數器260和「0」計數器265可以反應負值。在變換實施例中，在遞減步驟可能使地址計數器具有負值時，「1」計數器260和「0」計數器265保持0。請注意，儘管在步驟452至458說明，首先校驗0位，然後，校驗1位，但是，在不脫離本發明實質範圍的情況下，讀取器可以以任何順序，或者並行執行這些步驟。在本發明的變換實施例中，可以在讀取器確定要遍歷哪個分支之前(步驟430)，調整節點信息(步驟450至458)。
在步驟460，讀取器104收集(accumulate)讀取器位，作為標籤標識流的下一位。在成功執行步驟460期間，讀取器104建立當前標籤標識號位流。
在步驟465，讀取器確定是否收集了完整標籤標識號。如果標籤標識號未完，則操作進入步驟498，然後，讀取器繼續進行二叉樹遍歷。
如果收集了完整標識號，則操作進入步驟470。在步驟470，讀取器進行檢錯處理，以確定是否讀取了有效標籤。在本發明的實施例中，檢錯處理是循環冗餘校驗(CRC)處理。CRC是數據通信應用中使用的常規檢錯協議。相關技術領域內的技術人員明白，可以使用其它檢錯協議。
在步驟472，如果標籤標識號有效，則操作進入步驟498。在步驟472，如果標籤標識號無效，則收集無效標籤標識號，然後，操作進入步驟474。儘管步驟470和472被表示為不同的步驟，但是讀取器可以同時執行它們。
在步驟474，讀取器使當前遍歷路徑上的所有先前節點的正確計數器遞減。然後，操作進入步驟498。
在二叉樹遍歷期間，當沒有要讀取的剩餘標籤時，或者如果噪聲主要使二叉樹數據結構的未取用分支表現被取用，則讀取器可以不從一組標籤接收響應。在步驟490，當不從一組標籤接收響應時，在當前遍歷期間，讀取器確定是否收集了任何標籤標識位。如果未收集標籤標識位，則操作進入步驟498。
如果在步驟490，讀取器確定收集了標籤標識位，則讀取器認為讀取器進入二叉樹上的錯誤路徑。由於錯誤路徑的標籤響應的這樣「丟失」最有可能直接發生在取第一錯誤分支上的節點之後。因此，在本發明的實施例中，在步驟495，讀取器使對應於在緊接丟失之前的節點的錯誤路徑上的計數器的權重遞減。在變換實施例中，讀取器可以使遍歷路徑上的附加節點，例如，取錯誤分支之前的節點上的計數器遞減。在調節計數器後，操作進入步驟498。
在步驟498，讀取器104繼續進行二叉樹遍歷。在二叉樹遍歷協議中，可以在各點，繼續進行二叉樹遍歷。例如，在收到完全有效標籤標識號時，讀取器104可以在命令處理點繼續進行二叉樹遍歷。作為一種選擇，當收到無效標籤標識號，或者收到部分標籤標識號時，讀取器可以在開始/根節點重新開始二叉遍歷。當標籤標識號上的附加位仍待收集時，讀取器104還可以進入二叉樹上的下一個節點。
在完成詢問一組標籤時(例如，二叉樹遍歷完成)，讀取器104可以在每個節點清除位計數器。作為一種選擇，讀取器104可以繼續存儲計數器值預定時間，或者固定數量的讀取周期。例如，如果讀取器104在第二次讀同樣的一組標籤，則讀取器104可以使用第一讀取周期的的計數器值，遞增或遞減這些值。在實施例中，讀取器104還可以在處理之前將與一組標籤120關聯的信息裝載到存儲器250上。可以從另一個讀取器104，或者從用戶域290內的資料庫獲得該組標籤信息。
相關技術領域內的技術人員容易明白，可以使根據本發明實施例讀取並跟蹤RFID標籤的上述方法適於請求並接受RFID讀取器場(field)內的所有標籤的唯一ID號(輪詢)的系統，或者試圖確定RFID標籤何時進入RFID讀取器場，何時從RFID讀取器場出來的系統(事件報告)。
有效讀取各標籤的另一種技術識別並存儲在堆垛上的各標籤的標識號之間公用的位序列，將各標籤順序拉離(pull off)堆垛並讀出它。例如，讀取器104可以收集標籤標識號的頭n位。在協商下一個位位置時，讀取器可以從一組標籤接收兩個符號。讀取器可以選擇與一個符號關聯的分支進行遍歷。然後，讀取器存儲與堆垛上的其它符號關聯的位序列。在讀取器每次到達分支節點時，進行這種堆垛(stacking)。因為從堆垛拉離的位序列被強制進行(force out)，所以這些位對誤碼不敏感。該技術複雜，但是對噪聲魯棒。然而，在讀取一組RFID標籤的過程中，該「堆垛」技術未優化使用RFID讀取器獲得的所有信息。
有效讀取標籤的另一種技術是，在二叉樹遍歷期間，在發生標籤響應「丟失」後，使用存儲的遍歷路徑。在該技術中，在響應「丟失」後，讀取器檢索二叉樹遍歷期間收集的被存儲的遍歷路徑。然後，在新「修改的」二叉樹遍歷期間，讀取器將存儲的遍歷路徑的每位傳送到各讀取器。在協商存儲的遍歷路徑上的各位時，讀取器忽略來自各標籤的響應，並通過存儲的遍歷路徑。這繼續進行，直到讀取器遍歷了與存儲的路徑上的所有位關聯的各節點，或者遍歷了與位子集關聯的各節點。然後，讀取器繼續對要收集的剩餘位進行標準二叉樹遍歷。
3.採用檢錯處理的標籤識別在有噪聲的工作環境下，在讀取過程期間，噪聲可能破壞標籤的收集標籤標識號。因此，從標籤接收的檢錯碼值與讀取器利用收集的標籤標識號計算的檢錯碼值不匹配。在公用標籤詢問協議中，讀取器現在不知道標識號內的哪位或者哪些位被破壞。在這些協議中，為了識別該標籤，讀取器丟棄整個標識號，而且必須附加進行一次或者多次標籤讀取處理。
在本發明中，讀取器可以確定哪位或者哪些位可能被噪聲破壞。讀取器可以利用該知識，正確識別單個標籤，而不執行另一個讀取過程。圖6示出具有10位標識號692和檢錯碼值693的示例標籤。在讀取過程中，讀取器已經識別了兩個可能被噪聲破壞的位位置695和696(如圖6所示，具有0值和1值)。因此，讀取器可以確定有效標籤具有4個可能的10位標識號677a-d之一，因為兩個未知位的4種可能組合。4個可能的10位標識號677a-d分別具有關聯檢錯碼值678a-d。讀取器104計算檢錯碼值678a-d。然後，通過使作為讀取過程的一部分從標籤接收的檢錯碼值693與檢錯碼值678a-d匹配，可以識別有效標籤標識號。讀取器指出與該匹配檢錯碼值關聯的標識號677a-d，作為有效標識號。
圖7示出根據本發明實施例，在存在在標籤102與讀取器104進行通信期間產生的錯誤時，利用檢錯碼處理過程識別標籤的流程圖700。在本發明的實施例中，檢錯碼處理是循環冗餘校驗(CRC)處理。相關技術領域內的技術人員明白，利用在此所述的遍歷路徑加權，可以結合一組標籤詢問使用流程圖700。
當讀取器開始與步驟102或者一組標籤120通信時，流程圖700以步驟710開始，在實施例中，通信可以包括讀取過程或者另一個過程，其中在標籤與讀取器通信期間，標籤102或者多個標籤不處於淨音狀態。在步驟720，讀取器識別可能被噪聲破壞的位位置。例如，在讀取器接收「0」符號和「1」符號時，讀取器可以識別可能被破壞的關聯位位置。讀取器還可以利用其它可用信息，例如，該節點的遍歷路徑的長度或者位計數器和活動節點寄存器的值確定該位位置是否被噪聲破壞。
在通信期間，讀取器收集它認為有效的標識號。因此，在步驟720之後，讀取器具有一個被認為正確的標識號，而且它還可以識別一個或者多個可能有效的標識號。在該說明中，被認為正確的標識號被稱為讀取標識號。
在步驟730，讀取器計算讀取標識號和可能有效標識號的檢錯碼值。
然後，在步驟740，讀取器確定從標籤接收的檢錯碼值是否與計算的檢錯碼值匹配。
在步驟745，如果發現匹配，則操作進入步驟750。在步驟750，關聯標籤標識號是有效標識號。在步驟745，如果發現不匹配，則操作進入步驟760。在步驟760，有效標識號未被識別，而且如果需要，可以執行後續讀取過程。
相關技術領域內的技術人員明白，在不脫離本發明實質範圍的情況下，可以採用方法700的各種實現。圖8示出根據本發明實施例採用多個過程的流程圖700的一種可能實現的流程圖800。
在讀取器開始與標籤102或者一組標籤120進行通信時，流程圖800以步驟810開始。在步驟820，讀取器從一組標籤接收一個或者多個響應。
在步驟825，讀取器確定是否收到「0」符號和「1」符號。如果二者均被收到，則讀取器認為當前位位置可能被噪聲破壞。在本發明的變換實施例中，讀取器還可以利用存儲在存儲器內的附加節點信息確定位位置是否被破壞。在兩種實施例之任一中，當讀取器確定位位置可能被噪聲破壞時，操作進入步驟840。
如果僅收到一個符號(或者讀取器確定該位位置未被破壞)，則操作進入步驟830。在步驟830，讀取器收集位於當前位位置的讀取標識號位流內的接收符號。
在步驟832，讀取器確定是否存在檢錯碼過程。檢錯碼過程是對單個可能標識號執行檢錯碼算法的邏輯。因此，對於每個可能標識號存在一個過程。如果一個或者多個過程確實存在，則操作進入步驟834。
在步驟834，讀取器收集讀取符號作為正被每個過程使用的標識號中的下一位。請注意，每個檢錯碼過程分別使用唯一標識號。如果檢錯碼過程不存在，則操作進入步驟850。
在步驟840，讀取器確定哪個接收位有效。在步驟840，一旦進行了確定，則在當前位位置的讀取標識號位流上收集選擇位。
在步驟842，利用其先前位與讀取標識號位相同和具有當前位位置的其它符號的可能標識號，讀取器啟動新檢錯碼過程。
在步驟844，讀取器確定是否存在檢錯碼過程。如果一個或者多個過程確實存在，則操作進入步驟846。在步驟846，讀取器收集一個符號作為每個現有過程中使用的標識號中的下一位。在步驟844，如果不存在過程，則操作進入步驟850。
在步驟848，讀取器啟動由每個現有過程獲得的新過程。每個新過程的標識號具有與母過程的標識號相同的先前位和位於當前位位置的其它符號。
在步驟850，讀取器確定完整標籤標識號是否被收集(在此被稱為讀取標識號)。如果讀取標識號未完成，則操作進入步驟852。在步驟852，讀取器繼續進行通信。如果讀取標識號位流完成，則操作進入步驟854。
在步驟854，讀取器計算已經被收集的當前標籤標識號的檢錯碼值。在變換實施例中，與標籤與讀取器的通信並行，對讀取標籤標識號進行檢錯碼計算。
在步驟855，讀取器試圖使從標籤接收的檢錯碼值與計算的讀取檢錯碼值以及(各)檢錯碼過程的結果匹配。在步驟860，如果發現匹配，則操作進入步驟862。在步驟862，與計算的檢錯碼值關聯的標識號被識別為有效標籤標識號。在步驟860，如果發現不匹配，則操作進入步驟864。然後，在步驟864，未發現有效標識號。儘管利用不同的步驟描述了步驟855和860，但是可以同時實現它們。步驟862和864之後，讀取器可以繼續進行通信。
在流程圖700的變換實施例中，讀取器可以將可能被破壞的每個位位置存儲到存儲器中。在讀取器已經收集了完整標籤標識號時，讀取器可以計算讀取標識號和對應於被破壞的位位置的每個可能標識號的檢錯碼值。然後，讀取器可以將接收的檢錯碼值與計算的檢錯碼值進行比較，以識別有效標籤標識號。
4.結論儘管上面描述了本發明的各種實施例，但是應該明白，僅作為例子而非作為限制說明它們。相關技術領域內的技術人員明白，在不脫離本發明實質範圍的情況下，在此可以在形式和細節方面進行各種修改。因此，上述示例實施例不限制本發明的廣度和範圍，但是應該僅根據下面的權利要求及其等同限定本發明的廣度和範圍。
權利要求
1.一種與多個射頻標識(RFID)標籤通信的方法，包括(a)從多個RFID標籤接收一系列位，並將所述一系列位存儲到二叉樹的相應節點上，其中所述二叉樹上的每個節點與計數器關聯；(b)在從所述多個RFID標籤接收的位與存儲在所述節點上的位匹配時，使與所述二叉樹上的節點關聯的計數器遞增；(c)在從所述多個RFID標籤接收的位與存儲在所述節點上的位不匹配時，使與所述二叉樹上的節點關聯的計數器遞減；以及(d)根據與所述二叉樹上的節點關聯的計數器的值，對從所述多個RFID標籤接收的位分配值。
2.一種在射頻標識(RFID)讀取器上利用二叉樹遍歷協議詢問一組標籤的方法，包括步驟(a)進入二叉樹上的邏輯節點；(b)將符號傳送到一組標籤；(c)確定是否從一組標籤接收了至少一個符號；(d)如果在步驟(c)確定收到至少一個符號，則確定從一組標籤接收的一個符號是否與第一邏輯值對應；(e)如果在步驟(d)確定收到的一個符號與第一邏輯值對應，則使與第一邏輯值關聯的節點計數器的值遞增；(f)如果在步驟(d)確定收到的一個符號與第一邏輯值不對應，則使與第一邏輯值關聯的節點計數器的值遞減；(g)如果在步驟(c)確定收到至少一個符號，則確定從一組標籤接收的一個符號是否與第二邏輯值對應；(h)如果在步驟(g)確定收到的一個符號與第二邏輯值對應，則使與第二邏輯值關聯的節點計數器的值遞增；(i)如果在步驟(g)確定收到的一個符號與第二邏輯值不對應，則使與第一邏輯值關聯的節點計數器的值遞減；(j)選擇邏輯值進行存儲，作為標籤位圖形的位；(k)存儲選擇的邏輯值，作為標籤位圖形的位；(l)確定位圖形是否完成；以及(m)如果位圖形未完成，則進入步驟(a)。
3.根據權利要求2所述的方法，其中步驟(j)包括步驟確定從一組標籤接收的一個符號是否與第一邏輯值對應，而從一組標籤接收的第二個符號是否與第二邏輯值對應；確定任何一個符號是否有可能由噪聲引起；以及如果確定一個接收符號可能由噪聲引起，則選擇與另一個接收符號關聯的邏輯值作為標籤位圖形的位。
4.根據權利要求3所述的方法，其中確定任何一個接收符號由噪聲引起的可能性的步驟包括評估與第一邏輯值關聯的計數器值和與第二邏輯值關聯的計數器值。
5.根據權利要求4所述的方法，該方法進一步包括步驟如果在步驟(c)確定從一組標籤收到至少一個符號，則使節點活動寄存器的值遞增。
6.根據權利要求5所述的方法，其中確定任何一個接收符號由噪聲引起的可能性的步驟進一步包括檢索活動寄存器；以及評估活動寄存器的值。
7.根據權利要求2所述的方法，其中步驟(j)包括步驟確定從一組標籤接收的一個符號是否與第一邏輯值對應，以及從一組標籤接收的第二個符號是否與第二邏輯值對應；確定任何一個接收符號是否有可能是由弱標籤產生的；以及如果確定一個接收符號是由弱標籤產生的，則選擇與所述一個接收符號關聯的邏輯值作為標籤位圖形的位。
8.根據權利要求7所述的方法，其中確定任何一個接收符號由噪聲引起的可能性的步驟包括評估與第一邏輯值關聯的計數器的值和與第二邏輯值關聯的計數器的值。
9.根據權利要求8所述的方法，該方法進一步包括步驟如果在步驟(c)確定從一組標籤收到至少一個符號，則使節點活動寄存器的值遞增。
10.根據權利要求9所述的方法，其中確定任何一個接收符號由噪聲引起的可能性的步驟進一步包括檢索活動寄存器；以及評估活動寄存器的值
11.根據權利要求2所述的方法，其中標籤位圖形含有標籤標識號。
12.根據權利要求11所述的方法，該方法進一步包括如果在步驟(i)確定標籤位圖形完成，則確定存儲的位圖形是否含有有效標籤標識號。
13.根據權利要求12所述的方法，其中標籤位圖形內的每位對應於二叉樹上的邏輯節點。
14.根據權利要求13所述的方法，該方法進一步包括如果該位圖形不含有有效標籤標識號，則使對應於標籤位圖形上的每位的邏輯節點的節點計數器遞減。
15.根據權利要求2所述的方法，該方法進一步包括如果在步驟(c)確定未收到至少一個符號，則使對應於位圖形上的最後存儲的位的節點計數器遞減。
16.根據權利要求2所述的方法，其中第一邏輯值是數據「0」，而第二邏輯值是數據「1」。
17.一種在射頻標識(RFID)讀取器上利用二叉樹遍歷協議詢問一組標籤的方法，包括步驟(a)進入二叉樹上的邏輯節點；(b)將符號傳送到一組標籤；(c)確定是否從一組標籤接收了至少一個符號；(d)如果在步驟(c)確定收到至少一個符號，則調整對該邏輯節點存儲的信息；(e)選擇邏輯值存儲為標籤位圖形的位；(f)存儲選擇的邏輯值作為標籤位圖形的位；(g)確定位圖形是否完成；以及(h)如果位圖形未完成，則進入步驟(a)。
18.根據權利要求17所述的方法，其中步驟(d)包括步驟如果在步驟(c)確定收到至少一個符號，則確定從一組標籤收到的一個符號是否與第一邏輯值對應；如果在該步驟確定收到的一個符號與第一邏輯值對應，則使與第一邏輯值關聯的節點計數器的值遞增；如果在該步驟確定收到的一個符號與第一邏輯值不對應，則使與第一邏輯值關聯的節點計數器的值遞減；如果在步驟(c)確定收到至少一個符號，則確定從一組標籤收到的一個符號是否與第二邏輯值對應；如果在該步驟確定收到的一個符號與第二邏輯值對應，則使與第二邏輯值關聯的節點計數器的值遞增；以及如果在該步驟確定收到的一個符號與第一邏輯值不對應，則使與第二邏輯值關聯的節點計數器的值遞減。
19.根據權利要求18所述的方法，其中步驟(d)進一步包括步驟如果在步驟(c)確定從一組標籤收到至少一個符號，則使節點活動寄存器的值遞增。
20.一種在射頻標識(RFID)讀取器上利用二叉樹遍歷協議詢問一組標籤的方法，包括步驟通過二叉樹遍歷詢問一組標籤上的標籤，讀取標籤標識位圖形；從標籤接收檢錯碼；識別讀取的標籤標識位圖形上的可能被噪聲破壞的一個或者多個位位置；識別在一個或者多個識別的位位置上具有交替位值的可能位圖形；計算收集的標籤標識位圖形的檢錯碼值；計算每個識別的可能位圖形的檢錯碼值；以及確定任何計算的檢錯碼值是否與接收的檢錯碼匹配。
21.根據權利要求14所述的方法，其中檢錯碼值是循環冗餘碼值。
22.一種在射頻標識(RFID)讀取器上利用二叉樹遍歷協議詢問一組標籤的方法，包括步驟存儲與標籤組有關的數據，其中該標籤組數據包括與二叉樹上的每個取用節點關聯的信息；在二叉樹遍歷期間，根據所述標籤組數據，確定遍歷路徑。
23.根據權利要求22所述的方法，其中與二叉樹上的每個取用節點關聯的信息包括節點加權信息，其中存儲步驟包括(l)存儲每個取用節點的節點加權信息。
24.根據權利要求23所述的方法，其中節點加權信息包括與第一邏輯位值關聯的第一存儲計數器值；以及與第二邏輯位值關聯的第二存儲計數器值；其中步驟(l)包括存儲每個取用節點的第一存儲計數器值和第二存儲計數器值。
25.根據權利要求22所述的方法，該方法進一步包括從讀取器的外部獲得標籤組數據的至少一部分。
26.根據權利要求25所述的方法，其中從第二讀取器獲得所述標籤組數據的至少一部分。
27.根據權利要求26所述的方法，其中從資料庫獲得所述標籤組數據的至少一部分。
全文摘要
本發明提供了一種在存在有噪聲空中信道時用於讀取並跟蹤射頻標識(RFID)標籤的方法。根據該方法，二叉樹數據結構用於特性化多個RFID標籤，每個RFID標籤與唯一標識(ID)號關聯。在標籤讀取器與一個或者多個RFID標籤進行通信期間，標籤讀取器遍歷二叉樹，從通信中刪除標籤，直到具有唯一ID號的一個標籤被隔離或者被驗證。在遍歷二叉樹時，根據標籤匹配，使與每個節點關聯的計數器遞增，以致與標籤組裝分支上的各節點關聯的計數器始終趨向於具有高值，而與未組裝樹分支上的各節點關聯的計數器趨向於具有低值。如果讀取過程受到噪聲影響，而且迫使標籤讀取器在分支節點進行判定，根據與每個可能替換分支關聯的節點計數器的當前值，標籤讀取器進行分支預測。
文檔編號G06K7/00GK1706206SQ200380101629
公開日2005年12月7日 申請日期2003年10月20日 優先權日2002年10月18日
發明者韋恩·E·尚克斯, 簡·阿諾德 申請人:賽寶技術公司