摘要 探索一種解決RFID系統(tǒng)中碰撞問題的方法，具體討論防碰撞算法中的二進(jìn)制搜索算法及其改進(jìn)方法一一動(dòng)態(tài)二進(jìn)制搜索算法。動(dòng)態(tài)二進(jìn)制搜索算法考慮的是在UID位數(shù)不變的情況下，把數(shù)據(jù)分成兩部分，收發(fā)雙方各自傳送其中一部分?jǐn)?shù)據(jù)，可把傳輸?shù)臄?shù)據(jù)量減小到一半，縮短傳送時(shí)間，提高RFID系統(tǒng)的效率。
關(guān)鍵詞 射頻識(shí)剮 讀寫器射頻卡碰撞二進(jìn)制搜索法

1 RFID技術(shù)概述
    射頻識(shí)別技術(shù)RFID(Radio Frequeilcy Identification)是一種非接觸式的自動(dòng)識(shí)別技術(shù)。目前的RFID系統(tǒng)有很多工作頻段：低頻、高頻和超高頻段。工作原理也不盡相同，有的是利用近場(chǎng)的電磁感應(yīng)(所以有人把射頻卡稱為“感應(yīng)卡”)}有的是利用電磁波發(fā)射來實(shí)現(xiàn)非接觸雙向通信，以達(dá)到識(shí)別目的并交換數(shù)據(jù)。RFID技術(shù)由于可實(shí)現(xiàn)非接觸目標(biāo)識(shí)別、多目標(biāo)識(shí)別和運(yùn)動(dòng)目標(biāo)識(shí)別，具有防水、防磁、耐高溫、使用壽命長(zhǎng)、讀取距離大、標(biāo)簽上數(shù)據(jù)可以加密、存儲(chǔ)數(shù)據(jù)容量更大以及存儲(chǔ)信息更改自如等優(yōu)點(diǎn)，廣泛應(yīng)用于工業(yè)自動(dòng)化、商業(yè)自動(dòng)化和交通運(yùn)輸控制管理等眾多領(lǐng)域。

    RFID系統(tǒng)，如圖1所示，主要由射頻卡(又稱為“電子標(biāo)簽”)、讀寫器和計(jì)算機(jī)網(wǎng)絡(luò)組成。其中最重要的是讀寫器(Reader Writer Device)和射頻卡(Transponder)。讀寫器和射頻卡之間采用無線通信方式，因此它們都有無線收發(fā)模塊及天線(或感應(yīng)線圈)。射頻卡芯片上有內(nèi)存部分用來存儲(chǔ)序列號(hào)(識(shí)別號(hào)碼)或其他數(shù)據(jù)。

2 防碰撞方法綜述
    早期的系統(tǒng)中，1次只能讀／寫1個(gè)射頻卡。射頻卡之間要保持一定距離，確保一次只有一個(gè)卡在讀寫區(qū)域內(nèi)，應(yīng)用起來很不方便。很多時(shí)候不可避免地會(huì)出現(xiàn)多個(gè)射頻卡進(jìn)入識(shí)別區(qū)域時(shí)信號(hào)互相干擾的情況，即碰撞。具有防碰撞性能的系統(tǒng)可以同時(shí)識(shí)別進(jìn)人識(shí)別距離的所有射頻卡，其并行工作方式大大提高了系統(tǒng)的效率。

2．1 防碰撞方法的設(shè)計(jì)要求
    防碰撞技術(shù)主要解決RFID系統(tǒng)一次可以完成對(duì)多個(gè)射頻卡的識(shí)別問題。假設(shè)同時(shí)進(jìn)入讀寫器天線區(qū)域的射頻卡共有n個(gè)，防碰撞設(shè)計(jì)要求如下：
    ①當(dāng)1≤n≤N時(shí)，其中N為讀寫器一次可識(shí)別射頻卡數(shù)量的上限，則在碰撞發(fā)生(n>1)的情況下，能識(shí)別n個(gè)射頻卡并依次與它們完成通信。
    ②平均響應(yīng)時(shí)聞τ足夠短，τ為某一時(shí)段內(nèi)完成通信的所有射頻卡在系統(tǒng)內(nèi)的平均停留時(shí)間。τ與算法有關(guān)，允許τ≤τ0。τ0為不同應(yīng)用中所允許的最大時(shí)延。

2.2 RFID中防碰撞的基本原理
    由于射頻卡含有可被識(shí)別的唯一信息(序列號(hào))，RFID系統(tǒng)的目的就是要讀出這些信息。如果只有一個(gè)射頻卡位于閱讀器的可讀范圍內(nèi)，則無需其他的命令形式即可直接進(jìn)行閱讀。如果有多個(gè)射頻卡同時(shí)位于一個(gè)閱讀器的可讀范圍內(nèi)，則射頻卡的應(yīng)答信號(hào)就會(huì)相互干擾形成所謂的數(shù)據(jù)沖突，從而造成閱讀器和射頻卡之間的通信失敗。為了防止這些沖突的產(chǎn)生，RFID系統(tǒng)中需要設(shè)置一定的相關(guān)命令，解決沖突問題，這些命令被稱為“防沖突命令或算法(anti-collision algorithms)”。

    在無線電技術(shù)中，實(shí)現(xiàn)防碰撞基本上有4種不同的方法：時(shí)分多路法、頻分多路法、空分多路法以及碼分多路法。時(shí)分多路(TDMA)法是把整個(gè)可供使用的通路容量按時(shí)間分配給多個(gè)用戶的技術(shù)。TDMA在數(shù)字移動(dòng)無線電系統(tǒng)中得到廣泛應(yīng)用。考慮到RFID系統(tǒng)通信形式、功耗、系統(tǒng)的復(fù)雜性及成本等因素，選擇TCMA來實(shí)現(xiàn)射頻識(shí)別系統(tǒng)的防碰撞機(jī)制是最普遍的方法。

    TDMA法通常被分為兩大類：讀寫器控制防碰撞法和射頻卡控制防碰撞法。
    讀寫器控制防碰撞法是以讀寫器為主動(dòng)控制器，進(jìn)入射頻場(chǎng)的所有射頻卡同時(shí)由讀寫器進(jìn)行控制和檢查。閱讀器依據(jù)射頻卡的ID號(hào)(Identification number)首先向射頻卡發(fā)射不同的詢問信號(hào)或指令，閱讀器依據(jù)選舉方法或二進(jìn)制樹尋找方法，在同一時(shí)間內(nèi)總是建立起一個(gè)通信關(guān)系，并且可以快速地按時(shí)間順序操作射頻卡。

    射頻卡控制法以射頻卡為主控制器，讀寫器對(duì)數(shù)據(jù)傳輸沒有控制。讀寫器發(fā)出指令后，由射頻卡依據(jù)自己的ID號(hào)(每個(gè)射頻卡的ID號(hào)是唯一的)隨機(jī)產(chǎn)生應(yīng)答時(shí)間。這時(shí)閱讀器發(fā)送信息如果有沖突，則射頻卡要等到下一個(gè)時(shí)隙到來時(shí)再重新產(chǎn)生響應(yīng)時(shí)間(即自動(dòng)排隊(duì))，使射頻卡在不同的時(shí)間段發(fā)回?cái)?shù)據(jù)，讀寫器只是被動(dòng)的接收數(shù)據(jù)。若有兩張以上的射頻卡同時(shí)反應(yīng)，則讀寫器認(rèn)為該數(shù)據(jù)無效，會(huì)重發(fā)指令，直到識(shí)別出場(chǎng)中的所有射頻卡。IS015693標(biāo)準(zhǔn)就采用了這種時(shí)隙方法。

    本文主要針對(duì)射頻卡控制法，即基于TDMA的二進(jìn)制搜索防碰撞算法進(jìn)行分析和研究，并分別在性能上作分析。二進(jìn)制搜索算法的思路是：通過定義讀寫器與多個(gè)射頻卡之間一組規(guī)定的指令序列，從中選出一張卡，并完成二者的數(shù)據(jù)交換。

3 二進(jìn)制搜索算法
    二進(jìn)制搜索算法的方法類似于在天平中采用的逐次比較方法。通過多次比較，不斷篩選出不同的序列號(hào)，時(shí)分復(fù)用地進(jìn)行讀寫器和射頻卡之問的信號(hào)交換，以一個(gè)獨(dú)特的序列號(hào)來識(shí)別射頻卡為基礎(chǔ)。為了從一組射頻卡中選擇其中之一，讀寫器發(fā)出一個(gè)請(qǐng)求命令有意識(shí)地將射頻卡序列號(hào)傳輸時(shí)的數(shù)據(jù)碰撞引導(dǎo)到讀寫器上，即通過讀寫器判斷是否有碰撞發(fā)生。如果有碰撞，則縮小范圍進(jìn)行進(jìn)一步的搜索。

    二進(jìn)制搜索算法由一個(gè)讀寫器和多個(gè)射頻卡之間規(guī)定的一組命令和應(yīng)答規(guī)則構(gòu)成，目的在于從多卡中選出任一個(gè)實(shí)現(xiàn)數(shù)據(jù)通信。

    該算法有3個(gè)關(guān)鍵要素：①選用適當(dāng)?shù)幕鶐Ь幋a(易于識(shí)別碰撞)。②利用射頻卡卡序列號(hào)唯一的特性。③設(shè)計(jì)一組有效的指令規(guī)則，高效、迅速地實(shí)現(xiàn)選卡。

3．1 曼徹斯特編碼
    在二進(jìn)制搜索算法的實(shí)現(xiàn)中，起決定作用的是讀寫器所使用的信號(hào)編碼必須能夠確定碰撞的準(zhǔn)確比特位置。曼徹斯特碼(Mancherster)可在多卡同時(shí)響應(yīng)時(shí)，譯出錯(cuò)誤碼字，可以按位識(shí)別出碰撞。這樣可以根據(jù)碰撞的位置，按一定法則重新搜索射頻卡。

3.2 防碰撞指令規(guī)則
    典型指令規(guī)則：
    ①REQuEST——請(qǐng)求(序列號(hào))。此命令發(fā)送一序列號(hào)作為參數(shù)給射頻卡。應(yīng)答規(guī)則是，射頻卡把自己的序列號(hào)與接收到的序列號(hào)比較，如果自身序列號(hào)小于或等于REQUEST指令序列號(hào)參數(shù)，則此射頻卡回送其序列號(hào)給讀寫器。這樣可以縮小預(yù)選的射頻卡的范圍；如果大于，則不響應(yīng)。
    ②SELECT——選擇(序列號(hào))。用某個(gè)(事先確定的)序列號(hào)作為參數(shù)發(fā)送給射頻卡。具有相同序列號(hào)的射頻卡將以此作為執(zhí)行其他命令(例如讀出和寫入數(shù)據(jù))的切入開關(guān)，即選擇這個(gè)射頻卡。具有其他序列號(hào)的射頻卡只對(duì)REQUEST命令應(yīng)答。
    ③READ-DATA——讀出數(shù)據(jù)。選中的射頻卡將存儲(chǔ)的數(shù)據(jù)發(fā)送給讀寫器。
    ④UNSELECT ——去選擇。取消一個(gè)事先選中的射頻卡，射頻卡進(jìn)入“無聲”狀態(tài)，在這種狀態(tài)下射頻卡完全是非激活的，對(duì)收到的REQUEST命令不作應(yīng)答。為了重新話化射頻卡，必須先將射頻卡移出讀寫器的作用范圍再進(jìn)入，以實(shí)行復(fù)位。

3.3 工作流程
    在二進(jìn)制搜索算法中，要能夠檢測(cè)出多張卡的存在，卡片的返回?cái)?shù)據(jù)必須具有唯一性，且卡片在傳輸其UID(Ubiquitous IDentifications，身份識(shí)別標(biāo)簽)時(shí)必須準(zhǔn)確、同步。這樣終端才能在位級(jí)上檢測(cè)出多張卡片的存在，這是防碰撞檢測(cè)的關(guān)鍵。

    射頻卡工作的特點(diǎn)是，當(dāng)讀到讀寫器發(fā)出的序列號(hào)大于自身序列號(hào)時(shí)，則對(duì)系統(tǒng)作出響應(yīng)。根據(jù)這一特點(diǎn)，二進(jìn)制搜索算法的工作流程是：

    ①射頻卡進(jìn)入讀寫器的工作范圍，讀寫器發(fā)出一個(gè)最大序列號(hào)讓所有射頻卡響應(yīng)；同一時(shí)刻開始傳輸它們的序列號(hào)到讀寫器的接收模塊。
    ②讀寫器對(duì)比射頻卡響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)，如果出現(xiàn)不一致的現(xiàn)象(即有的序列號(hào)該位為0，而有的序列號(hào)該位為1)，則可判斷出有碰撞。
    ③確定有碰撞后，把有不一致位的數(shù)從最高位到次低次依次置O再輸出系列號(hào)，即依次排除序列號(hào)大的數(shù)，至讀寫器對(duì)比射頻卡響應(yīng)的序列號(hào)的相同位數(shù)上的數(shù)完全一致時(shí)，說明無碰撞。這時(shí)就選出序列號(hào)最小的數(shù)。
    ④選出序列號(hào)最小的數(shù)后，對(duì)該}進(jìn)行數(shù)據(jù)交換，然后使該卡進(jìn)入“無聲”狀態(tài)，則在讀出器范圍也不再響應(yīng)(移動(dòng)該范圍后移入可再次響應(yīng))。
    ⑤重復(fù)流程①，選出序列號(hào)倒數(shù)第二的射頻卡進(jìn)行數(shù)據(jù)交換。
    ⑥多次循環(huán)后可完成所有射頻卡的讀取。

4 二進(jìn)制搜索算法的改進(jìn)分析
4．1 二進(jìn)制搜索算法的傳輸時(shí)間
    由二進(jìn)制搜索算法的工作流程可知，防碰撞處理是在確認(rèn)有碰撞的情況下，根據(jù)高低位不斷降值的序列號(hào)一次次進(jìn)行篩選出某一射頻卡，從而可知射頻卡的數(shù)量越多，防碰撞執(zhí)行時(shí)間就將越長(zhǎng)。搜索的次數(shù)N可用下式來計(jì)算： 
    N=Integ(1Og M/log2)+1
    式中：M是終端作用范圍內(nèi)射頻卡片數(shù)日；Integ表示數(shù)值取整。

    UID的位數(shù)越多(如ICODE達(dá)64位)，每次傳送的時(shí)間加長(zhǎng)，數(shù)據(jù)傳送的時(shí)間就會(huì)增大。如每次都傳輸完整的UID，每次時(shí)間為T，則用于傳輸U(kuò)ID的通信時(shí)間為：
    t=T×N
    即終端作用范圍內(nèi)射頻卡片數(shù)越多，UID位數(shù)越多，傳送時(shí)間越長(zhǎng)，總的防碰撞執(zhí)行時(shí)問肯定也就越長(zhǎng)。

4.2 動(dòng)態(tài)二進(jìn)制搜索算法
    動(dòng)態(tài)二進(jìn)制搜索算法考慮的是在UID位數(shù)不變的情況下，盡量減少傳輸?shù)臄?shù)據(jù)量，使傳送時(shí)間縮短，提高RFID系統(tǒng)的效率。其改進(jìn)思路是把數(shù)據(jù)分成兩部分，收發(fā)雙方各自傳送其中一部分?jǐn)?shù)據(jù)，可把傳輸?shù)臄?shù)據(jù)量減小到一半，達(dá)到縮短傳送時(shí)間的目的。

    通常序列號(hào)的規(guī)模在8字節(jié)以上。為選擇一個(gè)單獨(dú)的射頻卡，每次都不得不傳輸大量的數(shù)據(jù)，效率非常低。根據(jù)二進(jìn)制搜索算法的思路進(jìn)行改良，可以減少每次傳送的位數(shù)，也可縮短傳送的時(shí)間，從而縮短防碰撞執(zhí)行時(shí)間。下面分析動(dòng)態(tài)二進(jìn)制搜索算法的工作過程。在例子中，射頻卡有3張，序列號(hào)分別是：卡1，11010111；卡2，11010101；卡3，11111101。

(1)動(dòng)態(tài)二進(jìn)制搜索算法的工作步驟
    ①讀寫器第一次發(fā)出一個(gè)完整的UID位數(shù)碼N，每個(gè)位上的碼全為l，讓所有射頻卡都發(fā)回響應(yīng)。
    ②讀寫器判斷有碰撞的最高位數(shù)X，把該位置O。然后傳輸N～X位的數(shù)據(jù)后即中斷傳輸。射頻卡接到這些數(shù)據(jù)后馬上響應(yīng)，回傳的信號(hào)位是X一1～1。即讀寫器和射頻卡以最高碰撞位為界分別傳送前后信號(hào)。傳遞的總數(shù)據(jù)量可減小一半。
    ③讀寫器檢測(cè)第二次返回的最高碰撞位數(shù)X’是否小于前一次檢測(cè)回傳的次高碰撞位數(shù)。若不是，則直接把該位置“O”；若是，則要把前一次檢測(cè)的次高位也填“O”。然后向射頻卡發(fā)出信號(hào)。發(fā)出信號(hào)的位數(shù)為N～X’，射頻卡接收到信號(hào)這一級(jí)信號(hào)出現(xiàn)小于或等于相應(yīng)數(shù)據(jù)時(shí)后馬上響應(yīng)，回傳的信號(hào)只是序列號(hào)中最高碰撞位后的數(shù)。即X—l～l位。若射頻卡返回信號(hào)表示無碰撞，則對(duì)該序列號(hào)的射頻卡進(jìn)行讀／寫處理，然后使其進(jìn)入“不響應(yīng)狀態(tài)”。
    ④重復(fù)步驟①，多次重復(fù)后可完成射頻卡的交換數(shù)據(jù)工作。

(2)動(dòng)態(tài)二進(jìn)制搜索算法與工作步驟相對(duì)應(yīng)的示例
    ①例如N=8，傳送數(shù)據(jù)為11111111b。最高位為第8位，最低位為l位。根據(jù)響應(yīng)可判斷第6位、第4位、第2位有碰撞。
    ②X=6，即第6位有碰撞，則傳送數(shù)據(jù)變?yōu)?1011111b。傳送時(shí)，只傳送前面3位數(shù)11Ob。這時(shí)卡1和卡2響應(yīng)，其序列號(hào)的前3位與射頻卡相同，不回傳，只回傳各自的后5位數(shù)據(jù)。卡1為lOlllb，卡2為10101b?？膳袛嗟?位有碰撞。
    ③X’=2，根據(jù)要求第4位也要補(bǔ)零，則傳送數(shù)據(jù)變?yōu)?10101O1b，傳送時(shí)只傳送110101Ob。這時(shí)只有卡2響應(yīng)，并返回1b，表明無碰撞。讀寫器選中卡2進(jìn)行數(shù)據(jù)交換，讀／寫完畢后卡2進(jìn)行“休眠”。
    ④重復(fù)步驟①，按序可讀／寫卡1、卡3。
    在動(dòng)態(tài)二進(jìn)制搜索算法的工作過程中，要注意通過附加參數(shù)把有效位的編號(hào)發(fā)送到射頻卡，從而保證每次響應(yīng)的位置是正確的。

5 總 結(jié)
    防碰撞是RFID技術(shù)中的一項(xiàng)重要技術(shù)。二進(jìn)制搜索算法是基于TDMA的一種適用于閱讀區(qū)內(nèi)射頻卡數(shù)量不多的情況。根據(jù)這一算法進(jìn)行編程，結(jié)構(gòu)比較簡(jiǎn)單，容易實(shí)現(xiàn)防碰撞功能。采用動(dòng)態(tài)二進(jìn)制搜索方法可提高執(zhí)行防碰撞的速度，實(shí)現(xiàn)高效率的控制。