1 RFID技術(shù)簡介

　　1．1　基本概念

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

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

　　1．2　RFID標(biāo)簽防碰撞

　　RFID的一個(gè)優(yōu)點(diǎn)就是多個(gè)目標(biāo)識別。在RFID系統(tǒng)工作是，在閱讀器的作用范圍內(nèi)，可能會有多個(gè)標(biāo)簽同時(shí)存在，即產(chǎn)生標(biāo)簽碰撞。在這種形式的系統(tǒng)中，存在著兩種基本的通信：由讀寫器到標(biāo)簽的通信；由標(biāo)簽到讀寫器的通信。

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

　　從標(biāo)簽到讀寫器的通信稱為多路存取，即在閱讀器的作用范圍內(nèi)有多個(gè)標(biāo)簽的數(shù)據(jù)同時(shí)傳送給閱讀器。

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

　　空分多路(SDMA)法是在分離的空間范圍內(nèi)進(jìn)行多個(gè)目標(biāo)識別的技術(shù)。SDMA法的缺點(diǎn)是復(fù)雜的天線系統(tǒng)和相當(dāng)高的實(shí)施費(fèi)用，因此采用這種技術(shù)的系統(tǒng)一般是在一些特殊的應(yīng)用場合，如這種方法在大型的馬拉松活動中就獲得了成功。

　　頻分多路(FDMA)法是把若干個(gè)使用不同載波頻率的傳輸通路同時(shí)供通信用戶使用的技術(shù)。FDMA法的一個(gè)缺點(diǎn)是閱讀器的成本高，因?yàn)槊總€(gè)接收通路必須有自己的單獨(dú)接收器供使用，射頻標(biāo)簽的差異更為麻煩。因此，這種防碰撞方法也限制在少數(shù)幾個(gè)特殊的應(yīng)用上。

　　時(shí)分多路(TDMA)法是個(gè)整個(gè)可供使用的通路容量按時(shí)間分配給多個(gè)用戶的技術(shù)。TDMA法由于應(yīng)用簡單，容易實(shí)現(xiàn)大量標(biāo)簽的讀寫，所以一般的防碰撞算法主要以TDMA方式實(shí)現(xiàn)。對RFID系統(tǒng)來說，TDMA構(gòu)成了防碰撞算法最大的一類。

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

　　2　基于二進(jìn)制搜索的算法

　　2．1　基本的二進(jìn)制搜索算法

　　實(shí)現(xiàn)“二進(jìn)制搜索”算法系統(tǒng)的必要前提是能辨認(rèn)出在閱讀器中數(shù)據(jù)碰撞的比特的準(zhǔn)確位置。為此，必須有合適的位編碼法。首先要對NRZ編碼和Manchester編碼的碰撞狀況做一個(gè)比較。選擇ASK調(diào)制副載波的負(fù)載調(diào)制電感耦合系統(tǒng)作為標(biāo)簽應(yīng)答器系統(tǒng)?；鶐Ь幋a中的“1”電平使副載波接通，“0”電平是副載波斷開。

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

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

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

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

　　為了實(shí)現(xiàn)“二進(jìn)制搜索”算法系統(tǒng)，就要選用Manchester編碼。下面介紹算法系統(tǒng)本身：

　　“二進(jìn)制搜索”算法系統(tǒng)是由一個(gè)閱讀器和多個(gè)標(biāo)簽之間規(guī)定的相互作用(命令和應(yīng)答)順序(規(guī)則)構(gòu)成的。目的在于從較大的一組中選出任一個(gè)標(biāo)簽。

　　為了實(shí)際實(shí)現(xiàn)這個(gè)算法系統(tǒng)，需要一組命令。這組命令能由標(biāo)簽應(yīng)答器處理。此外，每個(gè)標(biāo)簽擁有一個(gè)唯一的序列號。為了舉例說明，這里用8位的序列號；最多可使256個(gè)標(biāo)簽處于運(yùn)行狀態(tài)，這是為了保證序列號的唯一性。

{$page$}

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

　　SELECT(SNR)：選擇(序列號)。用某個(gè)(事先確定的)序列號作為參數(shù)發(fā)送給標(biāo)簽。具有相同序列號的標(biāo)簽將一次作為執(zhí)行其他命令(例如讀出和寫入數(shù)據(jù))的切入開關(guān)，即選擇這個(gè)標(biāo)簽。具有其他序列號的標(biāo)簽只對REQUEST命令應(yīng)答。

　　READ—DATA：讀出數(shù)據(jù)。選中的標(biāo)簽將存儲的數(shù)據(jù)發(fā)送給閱讀器(在實(shí)際的系統(tǒng)中，還有鑒別或?qū)懭?、出納登帳、取消預(yù)定等命令…)。

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

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

　　標(biāo)簽1：10110010；標(biāo)簽2：10100011；標(biāo)簽3：1011001l；標(biāo)簽4：11100011。

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

圖2　二進(jìn)制搜索算法選擇一個(gè)標(biāo)簽的流程

　　對二進(jìn)制樹形搜索算法系統(tǒng)功能的可靠性起決定性作用的是所有標(biāo)簽需準(zhǔn)確的同步，使這些標(biāo)簽準(zhǔn)確的在同一時(shí)刻開始傳輸它們的序列號。只有這樣，才能按位判定碰撞的發(fā)生。

　　在接收序列數(shù)的0位、4位和6位時(shí)，由于應(yīng)答的標(biāo)簽在這些位的不同內(nèi)容的重疊造成了碰撞?？梢跃烷喿x器作用范圍內(nèi)的兩個(gè)或多個(gè)標(biāo)簽得出結(jié)論：在接收的序列號中出現(xiàn)了一次或多次碰撞。更仔細(xì)的觀察表明：由于接收的位順序?yàn)?XlX001X，從而可以得出所接收的序列號的八種可能性，如表所示。

　　第6位是最高值的位，在重復(fù)操作的第一次中此位上出現(xiàn)了碰撞。這意味著：不僅在序列號≥n000000b的范圍內(nèi)，而且在序列號≤10111111b的范圍內(nèi)至少各有一個(gè)標(biāo)簽存在。為了能選擇到一個(gè)單獨(dú)的標(biāo)簽，必須根據(jù)已有的了解限制下一次重復(fù)操作的搜索范圍?？呻S意區(qū)分，例如，在≤10111111b的范圍內(nèi)進(jìn)一步搜索。為此，將第6位
置“o”(有碰撞的最高值位)，仍將所有的低位置“1”，從而暫時(shí)對所有的低值位置之不理。

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

　　閱讀器發(fā)命令REQUEST(≤10111111)后，所有滿足此條件的標(biāo)簽都做出應(yīng)答，并將它們自己的序列號傳輸給閱讀器。本例中，這些標(biāo)簽是標(biāo)簽l、2和3，如圖所示?，F(xiàn)在接收的序列號的。位和4位上出現(xiàn)了碰撞(x)?？梢杂纱说贸鼋Y(jié)論：在第二次重復(fù)操作的搜索范圍內(nèi)至少還存在有兩個(gè)標(biāo)簽。還需要進(jìn)一步確定的序列號的四種可能性是從接
收的位順序101X001X中得出的。

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

　　用SELECT命令，在所發(fā)現(xiàn)的標(biāo)簽地址選擇了標(biāo)簽2，現(xiàn)在可以無干擾地撇開其他標(biāo)簽，由閱讀器讀出或?qū)懭肓?。所有其他?biāo)簽處于靜止?fàn)顟B(tài)，因?yàn)橹挥幸粋€(gè)被選擇的標(biāo)簽對READ—DATA命令做出應(yīng)答。

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

　　為了從較大量的標(biāo)簽中發(fā)現(xiàn)一個(gè)單獨(dú)的標(biāo)簽，需要重復(fù)操作。其平均次數(shù)L取決于閱讀器作用范圍內(nèi)的標(biāo)簽總數(shù)N，并且很容易得出：

　　如果只有唯一的一個(gè)標(biāo)簽處在閱讀器作用范圍內(nèi)，那么只需要唯一的一次重復(fù)操作，以便發(fā)現(xiàn)標(biāo)簽的序列號一在這種情況下不出現(xiàn)碰撞。如果有一個(gè)以上的標(biāo)簽處在閱讀器作用范圍內(nèi)，那么重復(fù)操作的平均數(shù)很快增加。

　　2．2　動態(tài)二進(jìn)制搜索算法

　　上述的二進(jìn)制搜索算法，不僅搜索的范圍標(biāo)準(zhǔn)，而且標(biāo)簽的序列號總是一次次完整地傳輸?shù)?。然而，在?shí)踐中標(biāo)簽的序列號不像上例中那樣僅由一個(gè)字節(jié)組成，而是按系統(tǒng)的規(guī)模可能長達(dá)10個(gè)字節(jié)，以致不得不傳輸大量的數(shù)據(jù)，而僅僅是選擇一個(gè)單獨(dú)的標(biāo)簽。如果我們更仔細(xì)地研究閱讀器和單個(gè)標(biāo)簽之間的數(shù)據(jù)流，則立刻可以得出：

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

　　標(biāo)簽應(yīng)答的序列號的N～X各位不包含給閱讀器的補(bǔ)充信息，因?yàn)镹～X這些位是已知且給定的。

　　由此可見：傳輸?shù)男蛄刑柕母髯曰パa(bǔ)的部分是多余的，本來也是不必傳輸?shù)摹?/P>

　　由此引導(dǎo)我們很快使用一種最佳的算法：代替序列號在兩個(gè)方向上完整地傳輸，序列號或搜索的范圍標(biāo)準(zhǔn)的傳輸現(xiàn)在簡單地改變?yōu)椴糠治?X)。

{$page$}

　　閱讀器在REQUEST(請求)命令中只發(fā)送要搜索的序列號的已知部分(N～X)作為搜索的依據(jù)，然后中斷傳輸。所有在(N～X)位中的序列號與搜索依據(jù)相符的標(biāo)簽，則傳輸?shù)男蛄刑柕氖Ｓ喔魑患?X一1)位為應(yīng)答。在REQUEST命令中的附加參數(shù)(有效位的編號)將下余各位的數(shù)量通知標(biāo)簽。

　　一種動態(tài)的二進(jìn)制搜索算法的過程如圖3所示，做了更詳細(xì)的說明。標(biāo)簽都使用了同前例中相同的序列號。由于沒有改動的使用了形成規(guī)則，所以重復(fù)操作的過程也與前例相同。然而，要傳輸?shù)臄?shù)據(jù)量和所需的時(shí)間減少可達(dá)50％。

　　2．3　后退式動態(tài)二進(jìn)制搜索算法

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

　　后退式動態(tài)二進(jìn)制搜索算法是目前最高效的算法，識別N個(gè)標(biāo)簽的總查詢次數(shù)只需要2N一1，而且用閱讀器記錄發(fā)送指令不需要標(biāo)簽有記憶功能，對標(biāo)簽的要求低。

　　2．4　算法改進(jìn)的一些思路

　　在后退式動態(tài)二進(jìn)制搜索算法的基礎(chǔ)上，提出了兩點(diǎn)改進(jìn)思路：閱讀器碰撞檢測時(shí)，增加一位碰撞位的特殊處理；閱讀器發(fā)送查詢指令時(shí)，不必發(fā)送所有的前綴，只發(fā)送標(biāo)識碰撞位的二進(jìn)制代碼。

　　當(dāng)閱讀器檢查碰撞位的情況時(shí)，如果發(fā)現(xiàn)只有一位碰撞位，可以立即識別兩個(gè)標(biāo)簽ID號，而沒必要繼續(xù)進(jìn)行搜索，因此，增加一位碰撞位的特殊處理可以大大減少搜索的總次數(shù)。

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

　　這兩點(diǎn)思路從理論上可以提高二進(jìn)制搜索算法的效率，但實(shí)現(xiàn)中增加了電路設(shè)計(jì)的復(fù)雜性，有待實(shí)踐中進(jìn)一步驗(yàn)證研究。

　　3　結(jié)語

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