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

RFID系統，如圖1所示，主要由射頻卡(又稱為“電子標簽”)、讀寫器和計算機網絡組成。其中最重要的是讀寫器(Reader Writer Device)和射頻卡(Transponder)。讀寫器和射頻卡之間采用無線通信方式，因此它們都有無線收發模塊及天線(或感應線圈)。射頻卡芯片上有內存部分用來存儲序列號(識別號碼)或其他數據。

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

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

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

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

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

射頻卡控制法以射頻卡為主控制器，讀寫器對數據傳輸沒有控制。讀寫器發出指令后，由射頻卡依據自己的ID號(每個射頻卡的ID號是唯一的)隨機產生應答時間。這時閱讀器發送信息如果有沖突，則射頻卡要等到下一個時隙到來時再重新產生響應時間(即自動排隊)，使射頻卡在不同的時間段發回數據，讀寫器只是被動的接收數據。若有兩張以上的射頻卡同時反應，則讀寫器認為該數據無效，會重發指令，直到識別出場中的所有射頻卡。IS015693標準就采用了這種時隙方法。

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

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

二進制搜索算法由一個讀寫器和多個射頻卡之間規定的一組命令和應答規則構成，目的在于從多卡中選出任一個實現數據通信。

該算法有3個關鍵要素：①選用適當的基帶編碼(易于識別碰撞)。②利用射頻卡卡序列號唯一的特性。③設計一組有效的指令規則，高效、迅速地實現選卡。

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

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

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

射頻卡工作的特點是，當讀到讀寫器發出的序列號大于自身序列號時，則對系統作出響應。根據這一特點，二進制搜索算法的工作流程是：

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

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

UID的位數越多(如ICODE達64位)，每次傳送的時間加長，數據傳送的時間就會增大。如每次都傳輸完整的UID，每次時間為T，則用于傳輸UID的通信時間為：
t=TN
即終端作用范圍內射頻卡片數越多，UID位數越多，傳送時間越長，總的防碰撞執行時問肯定也就越長。

4.2 動態二進制搜索算法
動態二進制搜索算法考慮的是在UID位數不變的情況下，盡量減少傳輸的數據量，使傳送時間縮短，提高RFID系統的效率。其改進思路是把數據分成兩部分，收發雙方各自傳送其中一部分數據，可把傳輸的數據量減小到一半，達到縮短傳送時間的目的。

通常序列號的規模在8字節以上。為選擇一個單獨的射頻卡，每次都不得不傳輸大量的數據，效率非常低。根據二進制搜索算法的思路進行改良，可以減少每次傳送的位數，也可縮短傳送的時間，從而縮短防碰撞執行時間。下面分析動態二進制搜索算法的工作過程。在例子中，射頻卡有3張，序列號分別是：卡1，11010111；卡2，11010101；卡3，11111101。

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

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

5 總 結
防碰撞是RFID技術中的一項重要技術。二進制搜索算法是基于TDMA的一種適用于閱讀區內射頻卡數量不多的情況。根據這一算法進行編程，結構比較簡單，容易實現防碰撞功能。采用動態二進制搜索方法可提高執行防碰撞的速度，實現高效率的控制。