RFID二進制搜索法防碰撞的實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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