RFID二進(jìn)制搜索法防碰撞的實(shí)現

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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