一種基於碰撞樹的多標籤識別防碰撞方法
2023-09-21 03:18:40
專利名稱：一種基於碰撞樹的多標籤識別防碰撞方法
技術領域：
本發明涉及一種應用於射頻識別(RFID)系統中的防碰撞方法，尤其涉及基於樹 形搜索的多標籤識別防碰撞方法。
背景技術：
射頻識別(RadioFrequency Identification，RFID)是一種具有實時、快速、準確 採集等特點的自動識別技術。RFID系統主要由閱讀器(Reader)、標籤(Tag)和應用系統三 部分組成，閱讀器和標籤之間採用無線信道進行通信。標籤可分為主動式標籤和被動式標 籤兩種，其中被動式標籤由於結構簡單，成本較低，體積較小，得到廣泛應用。被動式標籤屬 於無源設備，標籤在接收到閱讀器的指令後會立即響應，發送自己的標號或者數據信息。但 當同一信道中有多個標籤同時響應某個閱讀器時，標籤數據間就會相互幹擾，導致閱讀器 無法正常讀取任何一個標籤數據，即發生所謂的標籤衝突或碰撞。為了解決多個標籤同時 識別的問題，就需要設置防碰撞算法來協調閱讀器和多個標籤之間的通信。標籤防碰撞算法可分為ALOHA算法、樹形算法兩大類。在現行的國際標準 IS018000-6中，採用了 ALOHA算法和Binary Tree ( 二進位樹算法)解決碰撞；EPCClass 1 protocol中採用Query Tree (查詢樹算法)解決碰撞。ALOHA算法的基本特徵是，系統將標籤回復的信道按時間劃分為若干間隔(該間 隔稱為時隙)，並要求標籤選擇其中一個回復。在操作中，閱讀器通過指令給每一個標籤發 送概率(或可選時隙的範圍)，標籤根據收到的時隙範圍，隨機的選擇一個時隙並按時回 復；若發生碰撞，再重新選擇並發送，或者在隨後的時隙內重新選擇或發送，直到完成所有 標籤的識別。經典的ALOHA算法主要包括時隙ALOHA方法(S-ALOHA)和動態時隙ALOHA方 法(DS-ALOHA)。Binary Tree ( 二進位樹，BT)算法的基本特徵是，每個標籤有一個隨機數發生器， 生成0或1 ；每個標籤有一個計數器，當計數器的值為0時，標籤回復。由閱讀器發送指令 使所有標籤開始回復，標籤收到指令後，首先由隨機數發生器生成0或1，這樣將要回復的 標籤分為兩個子集；隨機數為0的標籤立即回復，隨機數為1的標籤將計數器值設為1 ；若 沒有碰撞並回復成功，則閱讀器發送指令確認，並使其它標籤將計數器值減1 ；若沒有返回 信息，閱讀器發送指令確認，並使所有標籤計數器值均減1，直到閱讀器收到標籤的返回信 息；若標籤碰撞，閱讀器發送指令，使碰撞標籤產生隨機數進行分裂，其它標籤計數器值加 1 ；如此循環，直到完成所有標籤的識別。二進位方法的改進方法一動態二進位樹搜索方 法(DBT)，減少了閱讀器和標籤數據傳送中的冗餘數據的傳送，提高了識別的性能，在ISO 18000-6中也得到應用。Query Tree (查詢樹，QT)算法的基本特徵是，閱讀器從查詢前綴池中選擇一個前綴(prefix)進行查詢，初始時前綴池中包括1和0，所有標籤均將收到的前綴與自己的標 籤編號(ID)的起始部分進行比較，如果比較結果相同則以自己的標籤編號進行回復，如果 比較結果不同，則標籤不予回復。如果沒有碰撞，則成功識別到一個標籤，閱讀器從前綴池中選取新的前綴繼續查詢；如果發生碰撞，則閱讀器將將剛剛發送的前綴增加一位1或0， 即prefix+ 「1」和prefix+ 「0」並放入前綴池，等待後續查詢使用；如果沒有回覆，閱讀器 從前綴池中選取新的前綴繼續查詢；如此循環，直到前綴池為空，即完成所有標籤的識別。ALOHA算法以時隙為基礎對標籤進行分組識別，算法複雜度較低，但該算法存在兩 個主要的問題一是，由於時隙編號由標籤隨機產生，致使部分標籤始終無法被識別，即標 籤飢餓現象；二是，由於時隙數目的限制，當標籤數目的增加，算法的性能急劇下降。二進位 樹算法和查詢樹算法確保了標籤的完全識別，但是也增加了算法的複雜度。ALOHA算法和 樹形算法都不可避免的存在空時隙或空搜索的情況，即存在某些時隙或搜索狀態下沒有任 何標籤響應的情況，因此識別算法的性能和效率受到很大的影響。同時，查詢樹算法的性能 還受到標籤編號分布情況的影響。目前很多的改進算法，如回退算法，修剪枝算法，倒置搜 索，估值算法等很多方法，雖然在一定程度上減少了空時隙或空搜索的情況，但同時增加了 算法本身的複雜度，也增加了算法實現的困難程度。以上方法各有優劣，可以根據情況應用於不同的環境。例如當標籤數量較少，識 別時間要求較短時，可以選用ALOHA算法；當標籤編號較短，且重複位叫少時，可以選用查 詢樹算法；當標籤數目較多，而對識別時間要求不高時，可以選用二進位樹算法。目前所要 求的是在較短的時間內完成大量標籤的完全識別。
發明內容
本發明的目的是提供一種用於RFID系統的基於碰撞樹的多標籤識別防碰撞方 法，即碰撞樹算法(Collision Tree)，記為CT算法。該方法以較低的算法複雜度，消除了傳 統樹形算法中的空搜索或空周期，提高了標籤識別效率，降低了識別時間和功耗；同時，該 方法不受標籤編號分布的影響，適用於各種分布的多標籤識別場合。為達到上述目的，本發明通過採取以下技術方案予以實現本發明的基本思想是通過直接根據標籤響應序列中的首位碰撞位的位置來生成 新的搜索前綴，也據此將發生碰撞的標籤分成兩個子集，並分別進行後續識別。該方法改變 了查詢樹中由閱讀器主導的逐位搜索方式，以及二進位樹方法和ALOHA方法中隨機過程帶 來的不確定性，因此消除了傳統方法中的空時隙或空搜索過程(在空時隙或空搜索中，沒 有任何標籤響應閱讀器的請求)。本發明的具體方法如下(1)閱讀器從前綴池中讀取搜索前綴prefix，初始時搜索前綴為空串，發送識別 請求命令。(2)該閱讀器識別域中待識別的標籤，將收到的前綴prefix與自己的編號ID進行 比較，如果編號的前面部分與prefix相一致，則發送各自標籤編號ID中除與prefix相一 致部分之外的餘下部分。(3)閱讀器接收標籤的響應；如果沒有響應，則表明沒有待識別的標籤；如果收到 的編號串中沒有碰撞發生，則成功識別到一個標籤，且該標籤的編號由搜索前綴prefix與 收到的編號串連接構成；如果收到的編號串中發生碰撞，記首位碰撞位為D。，則生成兩個新的搜索前綴，它們末位，即碰撞位D。所在位的值分別設置為0或1，其餘部分由搜索前綴 prefix與接收到的編號串中首位碰撞位之前的部分構成，並將兩個新前綴放入前綴池，等待後續搜索。(4)重複進行上述過程，直到完成所有標籤的識別。本發明方法中的閱讀器搜索流程和標籤的響應流程如圖1所示，圖2給出了採用 本發明方法進行多標籤識別的基本過程和碰撞樹的基本結構。本發明至少具有如下創新或優勢(1)直接根據首位碰撞位生成新的搜索前綴，且搜索前綴隨著碰撞發生的實際位 置動態增長；(2)在根據碰撞位生成新前綴的同時，也將待識別的標籤集合分為了兩個子集，其 中一個子集中所有標籤滿足碰撞位D。的值為0，另一個子集中所有標籤滿足碰撞位D。的值 為1，並且兩個子集均不為空；(3)通過(1)和(2)消除了採用傳統算法進行多標籤識別過程中出現的空時隙或 空搜索狀態，有效減少了搜索次數，提高了搜索效率；理論和實驗均表明本發明算法的效率 超過了 50% ；(4)編號與前綴相匹配的標籤在響應時，只回傳與前綴不相同的編號部分，減少了 信息的傳輸量，降低了系統能耗；(5)本算法對閱讀器和標籤均沒有附加要求，特別是標籤只需要根據收到的前綴 進行決定響應，而不需要記錄歷史的過程，所以本發明算法簡單，可用於無源被動式多標籤 的識別環境；(6)由於算法直接針對碰撞進行處理，理論和實驗均表明算法性能只與標籤數量 有關，而與標籤編號的分布狀況無關，所以本發明算法可應用於各種分布的多標籤識別環境。
圖1是本發明方法的算法流程(a)閱讀器的識別流程，(b)標籤的響應流程。圖2是採用本發明方法(CT)完成五個標籤(0001、0010、0011、1110、1111)識別的 一個實例(a)標籤的識別過程，(b)描述該識別過程的碰撞樹。圖3是採用查詢樹方法(QT)完成與圖2中相同五個標籤識別的例子(a)標籤的 識別過程，(b)描述該識別過程的查詢樹。圖4是採用二進位樹方法(BT)完成與圖2中相同五個標籤識別的例子(a)標籤 的識別過程，(b)描述該識別過程的二進位樹。圖5是本發明方法在識別效率上的優勢曲線。圖6是本發明方法在識別速度上的優勢曲線。圖7是本發明方法應用的典型場景，即單個閱讀器對多個標籤同時識別的環境。圖8是採用曼徹斯特編碼區分碰撞位的原理圖。下面結合附圖和實施例對本發明進一步說明。圖1給出了本發明方法的算法流程。算法採用堆棧結構作為前綴池，算法實現簡單。待識別的標籤只需要接收命令，將命令中的前綴與自身編號的前端部分進行比較，如果 一致，就發送自身編號的餘下部分；如果不一致，則不做任何操作。也就是說，標籤的響應和 處理與過往的識別狀態無關，因此該方法可以應用於無源被動式標籤的識別。
圖2給出了本發明方法的一個識別過程實例和碰撞樹的基本結構。由於是根據 碰撞直接決定生成新的搜索前綴，並據此對待識別標籤進行分組，所以整個識別過程中沒 有空時隙或空搜索的狀態。由本發明方法的目的和算法識別過程的特點，碰撞樹為滿二叉 樹，每一個中間節點至少與兩個標籤相對應，每一個葉子節點僅對應一個識別到的標籤，碰 撞樹中沒有空節點，如圖2(b)所示。由滿二叉樹的性質，對於N個標籤，碰撞樹的葉節點也 為N，碰撞樹的節點總數為2N-1，所以完成N個標籤的識別，總共只需要2N-1次搜索過程， 而單標籤識別的平均搜索次數為(2-1/N)次。所以本發明方法的識別效率(識別標籤數與 完成這些標籤識別的搜索次數之比)超過了 50% .圖2、圖3、圖4給出了分別採用本發明算法(CT)、查詢樹算法(QT)和二進位樹算 法(BT)識別5個標籤(0001、0010、0011、1110、1111)的識別過程，以及相應的碰撞樹、查詢 樹和二進位樹結構。對比圖2、圖3、圖4可以發現，本發明算法消除了空搜索周期和空閒節 點，減少了搜索次數，提高了識別效率。圖5、圖6分別給出了在標籤編號均勻分布環境下，與傳統經典防碰撞方法相比 較，本發明方法在識別效率(識別標籤數與完成這些標籤識別的搜索次數之比)和識別速 度(單位時間內平均識別標籤的數量)上的優勢。其中BT為二進位樹算法，DBT為動態 二進位樹算法，QT為查詢樹算法，S-ALOHA為時隙ALOHA算法，DS-ALOHA為動態時隙ALOHA 算法，CT為本發明的碰撞樹算法。需要說明的是，在S-ALOHA和DS-ALOHA算法的每次實驗 中，時隙數的取值與標籤數目相等。本發明的
具體實施例方式本發明提供了一種基於碰撞樹的多標籤識別防碰撞方法，具體應用於單個閱讀器 和多個標籤組成的多標籤識別環境中，如圖7所示，解決多個標籤同時發送信息所引發的 標籤碰撞問題。本發明方法對於標籤的特點和標籤編號的分布沒有特殊要求，可進行無源 被動式標籤的識別和防碰撞處理。本發明算法中標籤編號採用曼徹斯特編碼(Manchester Coding)進行傳送，因為根據曼徹斯特編碼，閱讀器能夠正確區分出正確的二進位位和發生 碰撞的二進位位，如圖8所示。下面以6個標籤的識別過程為例，結合附圖和具體實施方式
對本發明做進一步的 詳細說明。記這6 個標籤及其編號分別為=Tl =00000100, T2 :11001101，T3 :01101111，T4 00001100，T5 =11000011, T6 :10011011，採用堆棧作為前綴池，存儲後續搜索需要用到的前
綴，根據圖1所示的算法流程，本發明的具體實施過程步驟如下步驟1⑴閱讀器以空串為前綴參數，即prefix = NULL，發查詢命令；(2)6個標籤 均產生響應，各自發送自身的編號(ID) ； (3)閱讀器收到的信號串為「XXXXXXXX」，其中X表 示其所在位發生碰撞，發生碰撞，閱讀器根據前綴生成規則生成兩個新前綴「 1」和「0」，並 依次壓入堆棧(前綴池)；(4)此時堆棧中的值(前綴)，自棧頂開始依次為「0」、「1」.步驟2(1)閱讀從堆棧(前綴池)中彈出一個前綴「0」，prefix =「0」，發查詢命 令；(2)編號與該前綴相匹配的標籤T1、T3、T4產生響應，各自發送自身編號的餘下部分，即 第2位至第8位；(3)閱讀器收到信號串為「ΧΧ0Χ1ΧΧ」，發生碰撞，閱讀器根據前綴生成規則 生成兩個新前綴「01」、「00」，並依次壓入堆棧；(4)此時堆棧中的值，自棧頂開始依次為 「00」、「01」、「1」·
步驟3(1)閱讀從堆棧(前綴池)中彈出一個前綴「00」，prefix =「00」，發查詢 命令；(2)編號與該前綴相匹配的標籤Tl、T4產生響應，各自發送自身編號的餘下部分，即 第3位至第8位；(3)閱讀器收到信號串為「00X100」，發生碰撞，閱讀器根據前綴生成規則 生成兩個新前綴「00001」、「00000」，並依次壓入堆棧；(4)此時堆棧中的值，自棧頂開始依 次為「 00000 」、「 00001 」、「 01 」、「 1 」 .步驟4(1)閱讀從堆棧(前綴池)中彈出一個前綴「00000」，prefix =「00000」， 發查詢命令；(2)編號與該前綴相匹配的標籤Tl產生響應，發送自身編號的餘下部分，即 第6位至第8位；(3)閱讀器收到信號串為「100」，沒有發生碰撞，成功識別到一個標籤，其 編號為「00000100」，即標籤Tl ；⑷此時堆棧中的值，自棧頂開始依次為「00001」、「01」、 「1」. 步驟5(1)閱讀從堆棧(前綴池)中彈出一個前綴"00001", prefix = "00001 發查詢命令；(2)編號與該前綴相匹配的標籤T4產生響應，發送自身編號的餘下部分，即第 6位至第8位；(3)閱讀器收到信號串為「100」，沒有發生碰撞，成功識別到一個標籤，其編 號為「00001100」，即標籤T4; (4)此時堆棧中的值，自棧頂開始依次為:「01」、「1」.步驟6(1)閱讀從堆棧(前綴池)中彈出一個前綴「01」，prefix =「01」，發查詢 命令；(2)編號與該前綴相匹配的標籤T3產生響應，發送自身編號的餘下部分，即第3位至 第8位；(3)閱讀器收到信號串為「101111」，沒有發生碰撞，成功識別到一個標籤，其編號為 「01101111」，即標籤 T3 ；(4)此時堆棧中的值，自棧頂開始依次為「1」.步驟7(1)閱讀從堆棧(前綴池)中彈出一個前綴「1」，prefix =「1」，發查詢命 令；(2)編號與該前綴相匹配的標籤T2、T5、T6產生響應，各自發送自身編號的餘下部分，即 第2位至第8位；(3)閱讀器收到信號串為「Χ0ΧΧΧΧ1」，發生碰撞，閱讀器根據前綴生成規則 生成兩個新前綴「01」、「00」，並依次壓入堆棧；(4)此時堆棧中的值，自棧頂開始依次為 「10」、「11」.步驟8(1)閱讀從堆棧(前綴池)中彈出一個前綴「 10」，prefix =「10」，發查詢 命令；(2)編號與該前綴相匹配的標籤T6產生響應，發送自身編號的餘下部分，即第3位至 第8位；(3)閱讀器收到信號串為「011011」，沒有發生碰撞，成功識別到一個標籤，其編號為 「10011011」，即標籤 T6 ；(4)此時堆棧中的值，自棧頂開始依次為「11」.步驟9(1)閱讀從堆棧(前綴池)中彈出一個前綴「 11」，prefix =「11」，發查詢 命令；(2)編號與該前綴相匹配的標籤T2、T5產生響應，各自發送自身編號的餘下部分，即 第3位至第8位；(3)閱讀器收到信號串為「00ΧΧΧ1」，發生碰撞，閱讀器根據前綴生成規則 生成兩個新前綴「11001」、「11000」，並依次壓入堆棧；(4)此時堆棧中的值，自棧頂開始依 次為「 11000」、「11001」.步驟10⑴閱讀從堆棧(前綴池)中彈出一個前綴「11000」，prefiX =「11000」， 發查詢命令；(2)編號與該前綴相匹配的標籤T5產生響應，發送自身編號的餘下部分，即第 6位至第8位；(3)閱讀器收到信號串為「011」，沒有發生碰撞，成功識別到一個標籤，其編 號為「11000011」，即標籤T5 ;(4)此時堆棧中的值，自棧頂開始依次為:「11001」.步驟11(1)閱讀從堆棧(前綴池)中彈出一個前綴「11001」，prefix =「11001」，發查詢命令；(2)編號與該前綴相匹配的標籤T2產生響應，發送自身編號的餘下部分，即第 6位至第8位；(3)閱讀器收到信號串為「101」，沒有發生碰撞，成功識別到一個標籤，其編 號為「11001101」，即標籤T2 ;(4)此時堆棧為空，表明已經完成全部標籤的 識別。
權利要求
一種基於碰撞樹的多標籤識別防碰撞方法，應用於射頻識別系統中單個閱讀器和多個標籤組成的多標籤識別系統中，解決多個標籤同時與閱讀器通信時所產生的碰撞問題，採用如下工作步驟(1)閱讀器從前綴池中讀取搜索前綴prefix，初始時搜索前綴為空串，發送識別請求命令；(2)該閱讀器識別域中待識別的標籤，將收到的前綴prefix與自己的編號ID進行比較，如果編號ID的前面部分與prefix相一致，則發送各自標籤編號ID中除與prefix相一致部分之外的餘下部分；(3)閱讀器接收標籤的響應；如果沒有響應，則表明沒有待識別的標籤；如果收到的編號串中沒有碰撞發生，則成功識別到一個標籤，且該標籤的編號由搜索前綴prefix與收到的編號串連接構成；如果收到的編號串中發生碰撞，記首位碰撞位為Dc，則生成兩個新的搜索前綴，它們末位，即碰撞位Dc所在位的值分別設置為0或1，其餘部分由搜索前綴prefix與接收到的編號串中首位碰撞位之前的部分構成，並將兩個新前綴放入前綴池，等待後續搜索；(4)重複進行上述過程，直到完成所有標籤的識別。
2.根據權利要求1所述之基於碰撞樹的多標籤識別防碰撞方法，其特徵在於，根據首 位碰撞位生成新的搜索前綴，且搜索前綴隨著碰撞發生的實際位置動態增長。
3.根據權利要求1所述之基於碰撞樹的多標籤識別防碰撞方法，其特徵在於，發生碰 撞的標籤根據首位碰撞位D。的值被分為兩個組，一個組中標籤滿足D。= 0，另一個組中標 籤滿足D。= 1.
4.根據權利要求1所述之基於碰撞樹的多標籤識別防碰撞方法，其特徵在於，響應標 籤只發送各自編號ID中除與prefix相一致部分之外的餘下部分。
5.根據權利要求1所述之基於碰撞樹的多標籤識別防碰撞方法，其特徵在於，所述碰 撞樹為滿二叉樹，且每一個葉子節點對應一個識別到的標籤，每一個中間節點對應一次碰 撞發生。
6.根據權利要求5所述之基於碰撞樹的多標籤識別防碰撞方法，其特徵在於，碰撞樹 中每一個中間節點至少與兩個標籤相對應，每一個葉子節點僅與一個標籤相對應，碰撞樹 中沒有空節點。
全文摘要
本發明公開了一種基於碰撞樹的多標籤識別防碰撞方法，應用於單個閱讀器和多個標籤組成的多標籤識別環境，解決了多個標籤同時與閱讀器通信時所產生的碰撞問題。本發明通過直接根據標籤響應序列中的首位碰撞位的位置來生成新的搜索前綴，也據此將發生碰撞的標籤分成兩個子集，並分別進行後續識別；改變了查詢樹中由閱讀器主導的逐位搜索方式以及二進位樹方法和ALOHA方法中隨機過程帶來的不確定性；消除了傳統方法中的空時隙或空搜索過程。理論和實驗均表明本發明方法的識別效率超過了50％，降低了系統能耗。本發明方法性能不受標籤編號分布的影響，適用於各種分布的多標籤識別場合，以及無源被動式多標籤識別系統。
文檔編號G06K7/00GK101840489SQ20101019040
公開日2010年9月22日 申請日期2010年6月2日 優先權日2010年6月2日
發明者馮全源, 賈小林 申請人:西南交通大學