1 RFID技術簡介

　　1．1　基本概念

　　RFID技術是一種非接觸的自動識別技術，其基本原理是利用無線射頻信號的空間耦合(電磁感應或電磁傳播)的傳輸特性，實現對被識別對象的自動識別。

　　RFID系統一般由兩個部分組成，即電子標簽和閱讀器。在RFID技術的實際應用中，電子標簽附著在被識別物體(表面或者內部)上，當帶有電子標簽的被識別物品通過閱讀器的可識讀區域時，閱讀器自動以無接觸的方式將電子標簽中的約定識別信息取出，從而實現自動識別物品或自動收集物品標識信息的功能。閱讀器本身可包括閱讀器模塊和天線兩個部分，有的閱讀器將閱讀器模塊和天線集成在一個設備單元中，即所謂的集成式閱讀器。

　　1．2　RFID標簽防碰撞

　　RFID的一個優點就是多個目標識別。在RFID系統工作是，在閱讀器的作用范圍內，可能會有多個標簽同時存在，即產生標簽碰撞。在這種形式的系統中，存在著兩種基本的通信：由讀寫器到標簽的通信；由標簽到讀寫器的通信。

　　從讀寫器到標簽的通信，類似于無線電廣播方式，多個接收機(標簽)同時接收同一個發射機(讀寫器)發出的信息。這種通信方式也被稱為“無線電廣播”。

　　從標簽到讀寫器的通信稱為多路存取，即在閱讀器的作用范圍內有多個標簽的數據同時傳送給閱讀器。

　　無線電通信系統中，多路存取方法或者標簽防碰撞問題的解決方式一般具有以下幾種形式：空分多路(Space Division Multiple Access，SDMA)法、時分多路(Time Division Multiple Access，TD—MA)法、頻分多路(Frequency Division MultipIe Access，FDMA)法、碼分多路(Code Division Mul—tiple Access，CDMA)法。

　　空分多路(SDMA)法是在分離的空間范圍內進行多個目標識別的技術。SDMA法的缺點是復雜的天線系統和相當高的實施費用，因此采用這種技術的系統一般是在一些特殊的應用場合，如這種方法在大型的馬拉松活動中就獲得了成功。

　　頻分多路(FDMA)法是把若干個使用不同載波頻率的傳輸通路同時供通信用戶使用的技術。FDMA法的一個缺點是閱讀器的成本高，因為每個接收通路必須有自己的單獨接收器供使用，射頻標簽的差異更為麻煩。因此，這種防碰撞方法也限制在少數幾個特殊的應用上。

　　時分多路(TDMA)法是個整個可供使用的通路容量按時間分配給多個用戶的技術。TDMA法由于應用簡單，容易實現大量標簽的讀寫，所以一般的防碰撞算法主要以TDMA方式實現。對RFID系統來說，TDMA構成了防碰撞算法最大的一類。

　　最靈活的和應用最廣泛的是“二進制搜索法”。對這種方法來說，為了從一組標簽中選擇其中之一，讀寫器發出一個請求命令，讀寫器通過合適的信號編碼，能夠確定發生碰撞的準確的比特位置，從而對電子標簽返回的數據做出進一步的判斷，發出另外的請求命令，最終確定讀寫器作用范圍內的所有標簽。本文對基于二進制搜索的算法做了詳
細介紹，包括基本的二進制搜索算法。，動態二進制搜索算法和后退式動態二進制搜索算法。

　　2　基于二進制搜索的算法

　　2．1　基本的二進制搜索算法

　　實現“二進制搜索”算法系統的必要前提是能辨認出在閱讀器中數據碰撞的比特的準確位置。為此，必須有合適的位編碼法。首先要對NRZ編碼和Manchester編碼的碰撞狀況做一個比較。選擇ASK調制副載波的負載調制電感耦合系統作為標簽應答器系統。基帶編碼中的“1”電平使副載波接通，“0”電平是副載波斷開。

　　NRZ編碼：某位之值是在一個位窗(bit window)內由傳輸通路的靜態電平表示的。這種邏輯“1”編碼為靜態“高”電平，邏輯“o”編碼為靜態“低”電平。

　　Manchester編碼：某位之值是在一個位窗內由電平的改變(上升／下降邊)來表示的。這里，邏輯“o”編碼為上升邊，邏輯“1”編碼為下降邊。在數據傳輸過程中“沒有變化”的狀態是不允許的，并且作為錯誤被識別。

　　由兩個(或多個)標簽同時發送的數位有不同之值，則接收的上升邊和下降邊互相抵消，以致在整個位窗的持續時間內接收器接收到的是不間斷的副載波信號。在Manchester編碼中對這種狀態未作規定。因此，這種狀態將導致一種錯誤，從而用這種方法可以按位回溯跟蹤碰撞的出現，如圖1所示。

 圖1　 NRZ編碼和Manchester編碼的碰撞情況

　　為了實現“二進制搜索”算法系統，就要選用Manchester編碼。下面介紹算法系統本身：

　　“二進制搜索”算法系統是由一個閱讀器和多個標簽之間規定的相互作用(命令和應答)順序(規則)構成的。目的在于從較大的一組中選出任一個標簽。

　　為了實際實現這個算法系統，需要一組命令。這組命令能由標簽應答器處理。此外，每個標簽擁有一個唯一的序列號。為了舉例說明，這里用8位的序列號；最多可使256個標簽處于運行狀態，這是為了保證序列號的唯一性。

{$page$}

　　REQUEST(SNR)：請求(序列號)。此命令發送一序列號作為參數給標簽應答器。標簽把自己的序列號與接受的序列號比較，如是小于或相等，則此應答器回送其序列號給閱讀器。這樣就可以縮小預選的標簽范圍。

　　SELECT(SNR)：選擇(序列號)。用某個(事先確定的)序列號作為參數發送給標簽。具有相同序列號的標簽將一次作為執行其他命令(例如讀出和寫入數據)的切入開關，即選擇這個標簽。具有其他序列號的標簽只對REQUEST命令應答。

　　READ—DATA：讀出數據。選中的標簽將存儲的數據發送給閱讀器(在實際的系統中，還有鑒別或寫入、出納登帳、取消預定等命令…)。

　　UNSELECT：去選擇。取消一個事先選中的標簽，標簽進入“無聲”狀態，在這種狀態中標簽完全是非激活的，對收到的REQUEST命令不做應答。為了重新活化標簽，必須暫時離開閱讀器的作用范圍(等于沒有供應電壓)以實行復位。

　　在“二進制搜索”算法系統中使用上述命令，現以四個在閱讀器作用范圍內的標簽作演示說明。它們在00～FFh(等于十進制o～255，或者二進制00000000～11111111)的范圍內具有唯一的序列號：

　　標簽1：10110010；標簽2：10100011；標簽3：1011001l；標簽4：11100011。

　　算法系統在重復操作的第一次中由閱讀器發送REQUEST(≤11111111)命令。序列號為11111111b，在本例中的系統最大可能的8位序列號。閱讀器作用范圍內的所有標簽的序列號都小于或等于11111111b，從而此命令被閱讀器作用范圍內的所有標簽應答，如圖2所示。

圖2　二進制搜索算法選擇一個標簽的流程

　　對二進制樹形搜索算法系統功能的可靠性起決定性作用的是所有標簽需準確的同步，使這些標簽準確的在同一時刻開始傳輸它們的序列號。只有這樣，才能按位判定碰撞的發生。

　　在接收序列數的0位、4位和6位時，由于應答的標簽在這些位的不同內容的重疊造成了碰撞。可以就閱讀器作用范圍內的兩個或多個標簽得出結論：在接收的序列號中出現了一次或多次碰撞。更仔細的觀察表明：由于接收的位順序為1XlX001X，從而可以得出所接收的序列號的八種可能性，如表所示。

　　第6位是最高值的位，在重復操作的第一次中此位上出現了碰撞。這意味著：不僅在序列號≥n000000b的范圍內，而且在序列號≤10111111b的范圍內至少各有一個標簽存在。為了能選擇到一個單獨的標簽，必須根據已有的了解限制下一次重復操作的搜索范圍。可隨意區分，例如，在≤10111111b的范圍內進一步搜索。為此，將第6位
置“o”(有碰撞的最高值位)，仍將所有的低位置“1”，從而暫時對所有的低值位置之不理。

　　限制搜索范圍形成的一般規則如下：

　　閱讀器發命令REQUEST(≤10111111)后，所有滿足此條件的標簽都做出應答，并將它們自己的序列號傳輸給閱讀器。本例中，這些標簽是標簽l、2和3，如圖所示。現在接收的序列號的。位和4位上出現了碰撞(x)。可以由此得出結論：在第二次重復操作的搜索范圍內至少還存在有兩個標簽。還需要進一步確定的序列號的四種可能性是從接
收的位順序101X001X中得出的。

　　在第二次重復操作中仍然出現的碰撞要求在第三次重復操作中進一步限制搜索范圍。使用表中形成的規則，把我們引向搜索范圍≤10101111。于是，閱讀器將命令REQUEST(≤10101111)發送給標簽。這個條件只有由標簽2(“10100011”)能滿足，該標簽即單獨對命令作出應答。這樣，終于發現了一個有效的序列號一另外的重復操作就不
需要了。

　　用SELECT命令，在所發現的標簽地址選擇了標簽2，現在可以無干擾地撇開其他標簽，由閱讀器讀出或寫入了。所有其他標簽處于靜止狀態，因為只有一個被選擇的標簽對READ—DATA命令做出應答。

　　在寫入／讀出動作完成后，用UNSELECT命令使標簽2完全去活化，這樣標簽2對后繼的請求命令不再作出應答。加入在閱讀器作用范圍內有許多標簽“等待”著對它們的處理，可以用這種方法使一個單獨的標簽所必需的重復操作次數逐步減少。在本例中，可重復運用上述防碰撞算法自動選擇至今未處理的標簽1、3或4中的一個標簽。

　　為了從較大量的標簽中發現一個單獨的標簽，需要重復操作。其平均次數L取決于閱讀器作用范圍內的標簽總數N，并且很容易得出：

　　如果只有唯一的一個標簽處在閱讀器作用范圍內，那么只需要唯一的一次重復操作，以便發現標簽的序列號一在這種情況下不出現碰撞。如果有一個以上的標簽處在閱讀器作用范圍內，那么重復操作的平均數很快增加。

　　2．2　動態二進制搜索算法

　　上述的二進制搜索算法，不僅搜索的范圍標準，而且標簽的序列號總是一次次完整地傳輸的。然而，在實踐中標簽的序列號不像上例中那樣僅由一個字節組成，而是按系統的規模可能長達10個字節，以致不得不傳輸大量的數據，而僅僅是選擇一個單獨的標簽。如果我們更仔細地研究閱讀器和單個標簽之間的數據流，則立刻可以得出：

　　命令中(X一1)～o各位不包含標簽的補充信息，因為(X一1)～o各位總是被置為“1”的。

　　標簽應答的序列號的N～X各位不包含給閱讀器的補充信息，因為N～X這些位是已知且給定的。

　　由此可見：傳輸的序列號的各自互補的部分是多余的，本來也是不必傳輸的。

　　由此引導我們很快使用一種最佳的算法：代替序列號在兩個方向上完整地傳輸，序列號或搜索的范圍標準的傳輸現在簡單地改變為部分位(X)。

{$page$}

　　閱讀器在REQUEST(請求)命令中只發送要搜索的序列號的已知部分(N～X)作為搜索的依據，然后中斷傳輸。所有在(N～X)位中的序列號與搜索依據相符的標簽，則傳輸的序列號的剩余各位即(X一1)位為應答。在REQUEST命令中的附加參數(有效位的編號)將下余各位的數量通知標簽。

　　一種動態的二進制搜索算法的過程如圖3所示，做了更詳細的說明。標簽都使用了同前例中相同的序列號。由于沒有改動的使用了形成規則，所以重復操作的過程也與前例相同。然而，要傳輸的數據量和所需的時間減少可達50％。

　　2．3　后退式動態二進制搜索算法

　　仔細觀察發現，動態二進制搜索算法的策略是不斷縮小搜索的范圍來一步步識別標簽。在基本的動態二進制搜索算法中，當查詢到第一個標簽后，閱讀器重新發送REQUEST(≤11111111)指令，搜索又從最初的大范圍開始。如果采用后退策略，當識別到第一個標簽后，下一個查詢指令的序列號參數為上一查詢指令的序列號值，則本次查詢的范圍大大減小，可以很快識別到下一個標簽，如此遞歸下去，從而可以大大減少識別所有標簽的搜索總次數。

　　后退式動態二進制搜索算法是目前最高效的算法，識別N個標簽的總查詢次數只需要2N一1，而且用閱讀器記錄發送指令不需要標簽有記憶功能，對標簽的要求低。

　　2．4　算法改進的一些思路

　　在后退式動態二進制搜索算法的基礎上，提出了兩點改進思路：閱讀器碰撞檢測時，增加一位碰撞位的特殊處理；閱讀器發送查詢指令時，不必發送所有的前綴，只發送標識碰撞位的二進制代碼。

　　當閱讀器檢查碰撞位的情況時，如果發現只有一位碰撞位，可以立即識別兩個標簽ID號，而沒必要繼續進行搜索，因此，增加一位碰撞位的特殊處理可以大大減少搜索的總次數。

　　當標簽的序列號很短時，后退式動態二進制搜索算法不會對傳輸時間造成很大的影響，但當標簽的序列號很長時，如64bit，128bit等時，閱讀器每次發送的查詢指令位數將很多，就會較大地影響傳輸效率。以64位標簽為例，如果碰撞位發生在第30位，則進行一次查詢就要發送34位序列號來標識碰撞位。如果直接用一組短的數據包來標識發生碰撞的位置，則可以大大減少發送的數據量，例如，把碰撞位的信息用其二進制代碼表示，則對一個長度為N的序列，只需一個109zN位的序列即可表示所有可能的碰撞位。對于16位的序列號只需要4位數據即可表示，對于64位的序列號則只需6位。如：假設解碼出的數據為1100lx01，碰撞位為D2，則可用2的二進制數10來表示該信息，
而不必傳輸1100lo。標簽應答時，則發送該碰撞位以后的序列號。這樣，當標簽序列號較長時，就可以極大地減少數據傳輸時間，從而提高算法的效率。

　　這兩點思路從理論上可以提高二進制搜索算法的效率，但實現中增加了電路設計的復雜性，有待實踐中進一步驗證研究。

　　3　結語

　　文中介紹了三種基于二進制搜索的算法，包括基本的二進制搜索算法，動態二進制搜索算法和基于后退式的動態二進制搜索算法，并在此基礎上，提出了算法的一些改進思路。通過增加一位碰撞位的特殊處理，可以有效的減少閱讀器搜索的次數；閱讀器發送查詢指令時，只發送標識碰撞位的二進制代碼，可以減少數據傳輸量，從而可以提高算法的效率。但這些改進思路必然增加了電路設計的復雜性，有待實踐中進一步研究，使二進制搜索算法更好的應用于實際。